redis-stat.c

/* Redis stat utility.
 *
 * Copyright (c) 2009-2010, Salvatore Sanfilippo <antirez at gmail dot com>
 * All rights reserved.
 *
 * This software is NOT released under a free software license.
 * It is a commercial tool, under the terms of the license you can find in
 * the COPYING file in the Redis-Tools distribution.
 */

#include "fmacros.h"

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdarg.h>
#include <limits.h>
#include <math.h>
#include <sys/time.h>
#include <assert.h>

#include "zmalloc.h"
#include "hiredis.h"
#include "utils.h"

#define REDIS_NOTUSED(V) ((void) V)

#define STAT_VMSTAT 0
#define STAT_VMPAGE 1
#define STAT_OVERVIEW 2
#define STAT_ONDISK_SIZE 3
#define STAT_LATENCY 4

static struct config {
    char *hostip;
    int hostport;
    redisContext *context;
    int delay;
    int stat; /* The kind of output to produce: STAT_* */
    int samplesize;
    int logscale;
} config;

/* Return the specified INFO field from the INFO command output "info".
 * A new buffer is allocated for the result, that needs to be free'd.
 * If the field is not found NULL is returned. */
static char *getInfoField(char *info, char *field) {
    char *p = strstr(info,field);
    char *n1, *n2;
    char *result;

    if (!p) return NULL;
    p += strlen(field)+1;
    n1 = strchr(p,'\r');
    n2 = strchr(p,',');
    if (n2 && n2 < n1) n1 = n2;
    result = malloc(sizeof(char)*(n1-p)+1);
    memcpy(result,p,(n1-p));
    result[n1-p] = '\0';
    return result;
}

/* Like the above function but automatically convert the result into
 * a long. On error (missing field) LONG_MIN is returned. */
static long getLongInfoField(char *info, char *field) {
    char *value = getInfoField(info,field);
    long l;

    if (!value) return LONG_MIN;
    l = strtol(value,NULL,10);
    free(value);
    return l;
}

static redisReply *reconnectingCommand(const char *cmd) {
    redisContext *c = config.context;
    redisReply *reply = NULL;
    int tries = 0;

    assert(!c->err);
    while(reply == NULL) {
        while (c->err & (REDIS_ERR_IO | REDIS_ERR_EOF)) {
            printf("Reconnecting (%d)...\r", ++tries);
            fflush(stdout);

            redisFree(c);
            c = redisConnect(config.hostip,config.hostport);
            usleep(config.delay*1000);
        }

        reply = redisCommand(c,cmd);
        if (c->err && !(c->err & (REDIS_ERR_IO | REDIS_ERR_EOF))) {
            fprintf(stderr, "Error: %s\n", c->errstr);
            exit(1);
        } else if (tries > 0) {
            printf("\n");
        }
    }

    config.context = c;
    return reply;
}

static void overview() {
    redisReply *reply;
    long aux, requests = 0;
    int i = 0;

    while(1) {
        char buf[64];
        int j;

        reply = reconnectingCommand("INFO");
        if (reply->type == REDIS_REPLY_ERROR) {
            printf("ERROR: %s\n", reply->str);
            exit(1);
        }

        if ((i++ % 20) == 0) {
            printf(
"------- data ------ --------------------- load -------------------- - child -\n"
"keys       mem      clients blocked requests            connections          \n");
        }

        /* Keys */
        aux = 0;
        for (j = 0; j < 20; j++) {
            long k;

            sprintf(buf,"db%d:keys",j);
            k = getLongInfoField(reply->str,buf);
            if (k == LONG_MIN) continue;
            aux += k;
        }
        sprintf(buf,"%ld",aux);
        printf("%-11s",buf);

        /* Used memory */
        aux = getLongInfoField(reply->str,"used_memory");
        bytesToHuman(buf,aux);
        printf("%-8s",buf);

        /* Clients */
        aux = getLongInfoField(reply->str,"connected_clients");
        sprintf(buf,"%ld",aux);
        printf(" %-8s",buf);

        /* Blocked (BLPOPPING) Clients */
        aux = getLongInfoField(reply->str,"blocked_clients");
        sprintf(buf,"%ld",aux);
        printf("%-8s",buf);

        /* Requets */
        aux = getLongInfoField(reply->str,"total_commands_processed");
        sprintf(buf,"%ld (+%ld)",aux,requests == 0 ? 0 : aux-requests);
        printf("%-19s",buf);
        requests = aux;

        /* Connections */
        aux = getLongInfoField(reply->str,"total_connections_received");
        sprintf(buf,"%ld",aux);
        printf(" %-12s",buf);

        /* Children */
        aux = getLongInfoField(reply->str,"bgsave_in_progress");
        aux |= getLongInfoField(reply->str,"aof_rewrite_in_progress") << 1;
        switch(aux) {
        case 0: break;
        case 1:
            printf("SAVE");
            break;
        case 2:
            printf("AOF");
            break;
        case 3:
            printf("SAVE+AOF");
            break;
        }

        printf("\n");
        freeReplyObject(reply);
        usleep(config.delay*1000);
    }
}

static void vmstat() {
    redisReply *reply;
    long aux, pagein = 0, pageout = 0, usedpages = 0, usedmemory = 0;
    long swapped = 0;
    int i = 0;

    while(1) {
        char buf[64];

        reply = reconnectingCommand("INFO");
        if (reply->type == REDIS_REPLY_ERROR) {
            fprintf(stderr, "Error: %s\n", reply->str);
            exit(1);
        }

        aux = getLongInfoField(reply->str,"vm_enabled");
        if (aux == LONG_MIN || aux == 0) {
            fprintf(stderr, "Error: Redis instance has VM disabled\n");
            exit(1);
        }

        if ((i++ % 20) == 0) {
            printf(
" --------------- objects --------------- ------ pages ------ ----- memory -----\n"
" load-in  swap-out  swapped   delta      used     delta      used     delta    \n");
        }

        /* pagein */
        aux = getLongInfoField(reply->str,"vm_stats_swappin_count");
        sprintf(buf,"%ld",aux-pagein);
        pagein = aux;
        printf(" %-9s",buf);

        /* pageout */
        aux = getLongInfoField(reply->str,"vm_stats_swappout_count");
        sprintf(buf,"%ld",aux-pageout);
        pageout = aux;
        printf("%-9s",buf);

        /* Swapped objects */
        aux = getLongInfoField(reply->str,"vm_stats_swapped_objects");
        sprintf(buf,"%ld",aux);
        printf(" %-10s",buf);

        sprintf(buf,"%ld",aux-swapped);
        if (aux-swapped == 0) printf(" ");
        else if (aux-swapped > 0) printf("+");
        swapped = aux;
        printf("%-10s",buf);

        /* used pages */
        aux = getLongInfoField(reply->str,"vm_stats_used_pages");
        sprintf(buf,"%ld",aux);
        printf("%-9s",buf);

        sprintf(buf,"%ld",aux-usedpages);
        if (aux-usedpages == 0) printf(" ");
        else if (aux-usedpages > 0) printf("+");
        usedpages = aux;
        printf("%-9s",buf);

        /* Used memory */
        aux = getLongInfoField(reply->str,"used_memory");
        bytesToHuman(buf,aux);
        printf(" %-9s",buf);

        bytesToHuman(buf,aux-usedmemory);
        if (aux-usedmemory == 0) printf(" ");
        else if (aux-usedmemory > 0) printf("+");
        usedmemory = aux;
        printf("%-9s",buf);

        printf("\n");
        freeReplyObject(reply);
        usleep(config.delay*1000);
    }
}

static void latency() {
    redisReply *reply;
    long long start;
    int seq = 1;

    while(1) {
        start = microseconds();
        reply = reconnectingCommand("PING");
        freeReplyObject(reply);
        printf("%d: %.2f ms\n",seq++,(double)(microseconds()-start)/1000);
        usleep(config.delay*1000);
    }
}

size_t getSerializedLen(char *key) {
    redisContext *c = config.context;
    redisReply *reply;
    size_t sl = 0;
    char *p;

    /* The value may be swapped out, try to load it */
    reply = redisCommand(c,"GET %s",key);
    freeReplyObject(reply);

    reply = redisCommand(c,"DEBUG OBJECT %s",key);
    if (reply->type == REDIS_REPLY_STRING) {
        p = strstr(reply->str,"serializedlength:");
        if (p) sl = strtol(p+17,NULL,10);
    } else {
        printf("Expected string reply... exiting.\n");
        exit(1);
    }
    freeReplyObject(reply);
    return sl;
}

#define SAMPLE_SERIALIZEDLEN 0
#define SAMPLE_TYPE 1
#define SAMPLE_REFCOUNT 2
#if 0
static size_t *sampleDataset(int fd, int type) {
    redisReply *r;
    size_t *samples = zmalloc(config.samplesize*sizeof(size_t));
    size_t totsl = 0, deltasum, avg;
    int j;

    printf("Sampling %d random keys from DB 0...\n", config.samplesize);
    for (j = 0; j < config.samplesize; j++) {
        size_t sl = 0;

        /* Select a RANDOM key */
        r = redisCommand(fd,"RANDOMKEY");
        if (r->type == REDIS_REPLY_NIL) {
            printf("Sorry but DB 0 is empty\n");
            exit(1);
        } else if (r->type == REDIS_REPLY_ERROR) {
            printf("Error: %s\n", r->reply);
            exit(1);
        }
        /* Store the lenght of this object in our sampling vector */
        if (type == SAMPLE_SERIALIZEDLEN) {
            sl = getSerializedLen(fd, r->reply);
            freeReplyObject(r);

            if (sl == 0) {
                /* Problem getting the  length of this object, don't count
                 * this try. */
                j--;
                continue;
            }
        }

        samples[j] = sl;
        totsl += sl;
    }
    printf("  Average: %zu\n", totsl/config.samplesize);

    deltasum = 0, avg = totsl/config.samplesize;
    for (j = 0; j < config.samplesize; j++) {
        long delta = avg-samples[j];

        deltasum += delta*delta;
    }
    printf("  Standard deviation: %.2lf\n\n",
        sqrt(deltasum/config.samplesize));
    return samples;
}
#else
static size_t *sampleDataset(redisContext *c, int type) {
REDIS_NOTUSED(c); REDIS_NOTUSED(type);
static size_t samples[10000] = {35,2,2,11,8,2,2,2,264,13,62,7,324,91,62,312,8,6,3,7,7,2,3,20,64,107,272,2,91,272,8,2,62,77,7,10,100,53,24,272,44,6,2,11,24,7,5,34,62,7,62,7,48,47,7,24,24,8,15,111,5,7,268,24,320,16,21,1,11,6,24,7,2,195,7,6,24,2,2,2,4,15,29,62,24,62,195,2,2,6,62,7,5,5,138,8,97,64,24,20,7,2,24,11,8,7,2,2,2,64,91,2,3,89,2,20,2,2,6,7,324,14,5,1,7,47,103,113,13,7,24,2,3,62,90,272,2,264,7,7,8,2,62,264,20,2,11,8,62,2,1,268,7,272,272,50,7,8,2,6,9,2,2,6,62,64,59,334,9,13,60,9,24,7,6,2,272,13,7,43,11,62,276,2,8,5,35,24,10,2,2,1,272,64,11,7,344,2,2,2,24,6,3,6,11,24,62,62,2,20,20,12,272,24,2,2,272,2,58,3,24,1,2,2,45,8,51,272,2,11,320,3,59,8,62,64,24,13,7,344,20,60,24,11,6,25,5,14,276,62,5,24,62,7,7,92,24,24,6,24,2,24,64,24,85,7,2,85,12,83,7,24,19,272,2,191,10,7,272,87,20,60,6,47,24,20,2,2,6,58,24,8,264,64,2,276,352,7,64,344,2,195,67,24,5,2,2,24,24,6,24,9,62,91,22,11,62,8,62,62,24,24,132,62,24,24,276,272,20,12,2,11,62,13,115,3,2,24,24,13,59,11,2,22,58,7,7,13,24,47,8,8,64,2,272,24,62,7,47,195,2,24,2,51,20,62,2,11,7,2,24,3,2,62,2,6,12,344,11,191,6,64,24,6,60,8,2,13,9,2,244,2,62,64,11,58,20,9,11,13,24,191,5,100,6,9,2,61,89,2,24,62,7,56,2,142,2,87,113,2,320,64,2,191,6,2,248,20,64,62,2,11,9,383,7,62,24,4,106,8,59,9,6,13,8,24,7,6,24,5,3,2,64,272,2,6,1,62,272,5,2,45,7,9,8,64,87,80,24,6,62,7,2,6,6,62,11,29,24,8,62,49,7,24,64,24,64,2,22,56,25,3,61,2,62,71,2,13,7,58,356,2,60,7,50,7,58,2,11,60,64,62,5,34,7,24,62,2,7,102,2,2,2,6,5,2,62,264,2,90,5,2,2,35,191,64,62,20,20,2,8,91,7,105,476,272,272,16,64,1,2,55,11,24,1,7,205,86,46,260,62,24,8,61,2,64,97,59,6,2,63,60,62,96,47,24,24,58,94,5,20,24,62,9,49,11,272,64,24,5,20,7,24,276,2,272,6,2,3,24,272,107,92,11,56,11,62,11,15,5,6,6,272,6,14764,20,272,24,9,27,31,5,7,2,8,62,195,59,6,62,24,7,6,8,3,2,195,2,7,2,62,64,5,2,64,64,8,64,2,64,2,20,24,2,2,2,47,59,195,24,62,87,7,395,24,6,272,2,13,344,64,24,276,195,4,195,50,191,19,2,6,64,7,2,2,24,7,272,66,24,61,23,11,11,7,2,5,2,50,58,5,64,11,59,8,62,48,276,2,2,320,6,92,43,20,11,2,24,24,20,60,272,260,3,195,5,31,264,2,2,2,13,24,62,276,260,11,2,8,2,52,2,10,332,6,14,19,3,62,37,24,14,4,2,12,9,24,62,5,44,24,2,8,20,272,44,24,58,14,24,51,51,59,63,60,8,2,24,89,49,2,9,7,4902,24,61,6,268,24,2,2,6,24,2,6,24,2,6,32,13,2,11,2,320,91,6,2,64,9,6,11,5,2,268,6,89,1,272,89,191,272,59,7,7,7,24,4,2,7,7,24,11,2,6,61,328,2,11,61,3,13,272,2,46,62,24,2,13,9,64,24,59,6,14,24,11,8,89,2,2,2,49,62,6,191,92,3,3,24,62,268,102,24,13,62,13,106,14,2,2,9,272,24,1,62,6,7,13,60,89,2,2,6,51,11,16,24,64,24,99,13,2,24,9,11,6,89,7,89,56,7,7,20,340,24,58,21,2,11,324,13,2,11,5,2,93,2,264,87,11,59,24,91,64,2,6,20,2,64,2,272,191,60,2,115,2,2,48,98,6,6,272,2,11,276,272,11,7,2,272,5,11,2,24,91,61,6,60,7,2,6,62,7,272,2,5,8,62,11,8,2,10,6,2,2,24,24,2,6,62,24,24,6,24,2,87,23,9,62,24,11,49,20,7,8,24,6,4,89,5,23,2,272,24,52,191,9,2,11,58,2,14,9,11,2,11,24,62,6,272,2,2,2,11,2,2,29,10,60,7,9,24,24,24,70,20,26,344,2,2,9,272,64,10,5,24,13,5,2,9,62,6,23,64,8,58,2,2,2,14,195,64,3,94,2,9,3,58,11,89,56,6,11,11,24,8,272,24,6,13,5,24,24,7,16,6,11,191,2,2,191,58,268,276,9,24,1,7,20,62,7,276,2,5,8,2,11,7,7,60,268,7,2,2,59,20,6,272,56,131,89,2,100,8,62,24,13,328,272,24,320,6,2,7,12,121,64,7,7,7,33,24,58,2,2,107,2,11,62,89,2,9,8,62,2,111,6,24,62,121,60,7,6,43,264,6,90,40,2,276,18,24,272,2,272,2,24,24,10,59,15,2,59,2,2,24,2,2,8,7,24,89,2,64,24,2,9,11,2,62,6,507,8,62,20,24,12,61,24,96,2,20,316,13,8,2,2,89,62,11,2,6,191,23,5,24,2,58,272,11,2,324,2,58,13,191,191,96,62,5,6,20,91,7,8,2,46,2,24,39,62,11,6,2,32,6,9,13,24,5,8,24,13,5,6,268,64,5,103,7,89,3,5,6,64,47,2,21,62,2,5,2,6,2,56,7,7,320,24,7,62,104,191,11,15,5,272,64,2,24,3,62,268,9,9,13,6,5,7,60,11,7,60,2,6,2,24,20,94,7,6,272,9,2,6,62,24,320,320,59,50,5,3,2,2,61,6,62,58,20,2,2,2,62,40,7,191,62,2,276,2,2,62,2,131,11,86,86,2,7,13,276,272,5,11,2,11,2,24,24,11,2,2,24,264,135,6,11,16,320,17,24,5,6,52,20,2,320,11,16,9,91,2,64,20,324,24,24,24,13,16,56,6,320,8,142,24,352,2,7,24,13,2,4,2,9,2,4,191,2,264,215,11,23,11,2,62,64,62,6,272,344,7,6,64,6,5,89,45,11,69,6,6,24,66,11,20,320,2,13,62,62,64,2,2,13,272,24,11,2,11,58,2,64,58,2,24,1,15,2,2,6,272,272,95,62,11,62,58,7,3,2,2,2,2,62,2,5,24,56,64,2,62,20,20,24,7,91,20,24,11,24,2,7,5,6,272,24,9,2,8,2,2,24,7,2,56,58,95,51,2,1,2,4,20,186,2,2,9,2,11,2,58,272,38,320,24,272,2,2,6,5,3,20,24,24,2,91,6,64,8,6,90,3,8,24,45,24,91,6,7,2,74,91,24,24,24,15,6,64,13,2,24,4,103,135,91,2,40,6,2,52,11,5,2,2,24,8,260,2,2,2,24,24,3,11,2,7,2,2,60,11,13,344,24,6,24,11,7,24,62,24,1,14,191,60,2,7,62,6,60,268,7,2,6,9,183,195,2,191,86,20,62,62,5,11,6,340,6,276,50,6,6,2,2,5,2,24,89,20,2,12,34,11,62,2,11,6,20,2,2007,11,9,324,23,2,11,324,2,6,24,62,59,24,7,109,272,67,5,103,276,34,2,28,47,11,64,268,48,15,4,5,24,1,9,2,66,87,9,11,20,3,9,11,11,11,2,24,7,272,2,101,6,2,61,11,24,5,8,4,11,8,59,68,85,104,24,7,7,62,4,24,48,24,2,2,272,2,5,20,93,13,2,58,348,6,7,62,8,60,272,9,6,2,2,139,20,16,44,11,62,3,6,64,5,90,24,2,328,8,14,13,2,24,7,320,11,8,62,11,244,24,89,3,11,13,24,3,24,276,62,2,62,5,4,272,1,59,96,64,2,7,24,20,13,45,6,6,24,13,63,8,60,268,24,5,11,7,2,191,2,11,2,2,13,15,24,2,24,6,253,13,2,7,44,3,64,50,4,20,89,11,19,62,2,2,58,2,276,272,9,264,6,59,2,50,2,46,6,2,86,3,29,56,14,67,20,2,11,49,2,24,49,87,260,24,97,7,6,62,2,272,6,348,4,11,2,13,2,59,11,17,48,264,91,24,11,24,62,2,24,13,11,11,64,2,62,3,7,2,2,7,2,7,7,94,20,35,2,11,8,14,18,2,8,2,62,2,24,62,6,89,11,20,24,2,2,11,5,14,2,11,11,2,11,48,6,13,1,2,24,31,187,2,61,91,24,11,46,6,20,2,2,328,2,8,46,7,11,110,8,24,2,6,59,51,60,320,6,2,24,2,34,32,53,5,59,2,7,44,24,207,8,2,9,62,2,11,4,21,11,24,8,11,4,8,24,11,20,7,9,91,5,62,195,8,8,24,61,45,88,111,24,5,2,2,2,2,3,7,59,6,59,2,7,195,3,89,6,2,59,35,11,191,112,25,272,95,2,6,98,2,2,87,316,6,64,7,89,24,24,195,5,62,220,4,320,13,8,104,43,20,9,59,8,2,9,11,2,2,13,58,2,272,89,20,104,111,8,6,191,2,2,2,1,9,2,18,2,62,2,2,2,203,20,5,11,62,24,11,6,47,24,60,60,187,2,260,62,59,20,7,60,5,3,8,2,24,2,107,58,4,24,272,6,11,9,64,89,60,9,2,2,58,20,20,195,24,49,3,2,11,24,20,13,142,91,118,11,264,89,2,7,24,61,7,60,7,47,11,43,62,24,2,12,24,24,67,2,64,24,272,24,6,2,89,272,61,5,2,60,2,7,2,13,11,62,2,62,24,24,276,12,49,95,44,20,48,28,2,3,2,60,89,7,9,1769,86,5,191,60,24,11,13,60,5,5,191,11,89,9,8,272,89,20,272,140,5,7,23,7,9,276,272,2,6,89,24,272,2,64,50,31,276,10,5,7,61,2,2,11,64,8,31,2,24,44,17,62,11,2,2,6,8,62,62,24,6,56,20,272,2,2,20,3,264,2,7,5,7,61,2,45,9,20,8,11,24,320,11,24,62,3,113,91,11,115,6,9,6,24,6,268,6,7,3,64,187,2,2,191,2,64,2,320,101,6,195,13,15,2,8,2,64,191,272,62,11,6,62,45,11,5,24,7,5,5,89,96,24,24,62,3,264,2,59,11,13,141,2,61,6,7,11,64,8,2,2,2,2,7,2,90,7,2,11,49,20,46,50,46,64,191,272,64,62,8,8,59,10,60,268,24,2,320,2,5,8,20,15,2,12,24,11,3,7,7,92,2,64,5,24,6,62,2,2,119,63,64,91,24,8,112,2,108,62,89,320,2,5,68,3,2,15,9,119,62,6,276,96,89,10,272,2,272,2,62,11,7,20,64,7,2,6,24,105,20,272,56,2,2,2,11,7,2,2,62,8,62,62,64,6,62,6,90,6,6,20,62,2,3,2,11,2,87,272,2,2,5,61,13,272,7,122,6,2,58,62,11,3,5,2,2,6,62,24,20,2,2,62,20,2,5,24,2,62,3,6,91,62,2,334,7,7,6,59,7,6,67,54,2,11,268,5,49,20,91,2,48,2,191,7,24,61,191,2,2,12,7,59,6,62,2,11,2,59,472,10,11,13,9,87,11,24,62,13,1,102,107,58,7,7,14,2,33,24,9,11,81,45,3,11,2,62,272,20,62,2,24,60,20,260,56,24,6,62,18,272,64,11,7,6,64,2,2,14,3,24,48,5,195,11,8,7,61,24,7,2,24,13,2,62,7,2,60,24,11,60,2,6,7,62,2,91,7,11,7,2,2,2,2,24,320,24,2,50,62,3,6,5,20,11,6,2,2,6,24,58,9,2,62,195,6,2,2,60,3,195,2,20,84,24,7,272,60,2,3,187,2,24,62,7,11,3,6,2,13,2,20,3,62,2,62,264,2,2,24,91,2,2,64,58,24,24,2,58,11,2,2,11,6,24,2,62,62,107,20,324,6,8,24,89,7,2,89,24,6,191,272,2,17,2,11,16,59,20,2,272,63,2,2,6,7,5,3,24,2,13,2,24,50,8,24,64,58,2,2,47,60,64,8,10,14,13,24,195,18,7,24,324,2,1,2,89,2,24,191,62,6,56,2,2,62,11,56,276,1143,62,91,7,2,7,2,272,24,62,13,2,139,6,7,11,268,2,62,24,49,89,2,264,2,2,20,7,60,11,62,67,24,24,23,5,24,24,148,2,5,6,24,85,8,272,105,5,64,276,13,64,62,2,5,3,85,15,50,49,5,2,11,24,2,104,24,24,59,6,272,4,2,344,11,6,312,2,5,87,11,87,8,86,1,94,24,272,7,17,5,11,264,8,122,13,2,20,272,62,24,1,2,24,61,2,24,5,264,63,2,58,13,11,3,67,59,13,8,24,2,58,344,2,209,2,20,64,60,19,47,6,142,2,7,99,24,8,332,2,2,13,2,2,195,8,20,6,107,6,11,20,40,2,8,5,7,68,2,13,9,88,2,13,6,4,11,11,5,66,5,205,3,6,8,2,11,58,13,2,93,24,60,8,2,27,6,62,6,24,40,52,6,62,320,24,320,11,2,11,24,7,24,191,5,2,24,59,2,2,338,59,20,2,24,191,53,10,61,24,5,62,6,1,24,2,89,2,62,24,6,62,272,24,87,62,8,195,2,20,20,50,8,2,2,6,7,11,2,24,8,66,17,2,59,2,2,3,2,2,11,60,19,328,62,13,2,2,6,90,2,191,344,7,60,62,20,334,25,26,24,2,83,268,7,59,2,46,8,24,20,6,2,60,2,17,62,2,60,23,191,61,39,62,2,272,11,272,60,6,3,2,195,2,89,8,24,320,24,32,8,2,11,59,89,13,11,13,320,88,62,272,137,11,272,91,7,8,84,2,320,8,4,58,11,6,24,62,93,6,2,13,58,11,272,2,80,20,63,360,316,62,59,2,8,11,24,6,134,5,24,6,2,64,24,272,5,569,7,89,7,2,13,71,24,191,62,7,87,2,8,24,60,62,11,14,88,24,272,5,24,2,81,24,2,13,62,87,8,64,7,7,7,38,7,2,179,24,8,260,272,6,191,13,8,2,24,91,9,69,58,185,7,89,195,24,5,6,89,64,2,2,4,6,6,16,24,2,61,11,6,5,6,5,11,46,7,24,6,60,21,62,11,272,58,88,272,62,24,7,191,24,15,62,59,20,88,2,7,91,12,24,62,24,7,95,3,320,6,272,62,7,312,6,2,91,64,7,2,272,58,11,6,62,11,7,9,2,116,62,12,11,3,56,64,11,7,2,191,6,20,328,476,8,31,24,3,3,59,60,191,20,9,6,8,7,98,7,15,58,195,2,272,56,2,24,11,86,20,320,2,9,24,62,17,9,2,2,89,24,2,11,13,8,5,24,5,195,15,24,13,8,11,272,7,24,11,7,2,62,7,5,272,2,24,2,11,24,6,2,20,139,7,5,2,24,6,6,2,7,2,276,86,14,264,2,2,85,35,8,12,2,7,2,14,24,272,62,7,2,19,24,1,2,24,64,272,97,5,9,109,20,106,27,11,7,18,98,24,9,272,24,62,2,62,8,62,20,40,24,53,2,8,11,7,15,91,6,58,2,24,2,2,6,320,24,24,20,24,2,6,24,5,2,6,14,13,2,24,7,2,6,91,8,320,272,7,11,49,2,3,187,24,241,268,24,2,2,348,48,142,24,62,8,24,64,56,62,3,11,2,187,24,13,13,62,11,2,24,7,7,320,7,2,2,7,6,59,8,2,59,5,62,2,91,6,2,324,7,52,24,344,7,11,10,272,2,320,569,6,33,47,7,45,11,11,476,7,20,46,24,12,6,7,13,2,13,6,62,2,25,11,7,7,2,62,2,77,272,10,62,5,11,2,62,11,191,11,24,2,22,6,272,20,138,87,5,53,59,11,2,11,2,62,89,5,62,338,2,62,10,63,71,16,4,77,11,13,20,11,48,24,2,191,2,6,13,56,128,11,2,58,99,867,12,11,13,5,2,11,2,11,2,11,8,20,11,20,69,5,96,187,2,49,60,5,20,45,7,13,195,11,6,187,13,60,11,6,62,91,2,2,9,24,7,24,24,272,272,272,11,8,89,8,320,11,62,6,24,320,62,24,320,59,6,5,64,24,2,30,8,2,8,272,11,62,2,14,191,91,2,24,66,66,11,2,109,6,264,3,62,58,11,2,2,6,7,21,77,24,52,9,1,2,46,2,100,103,6,6,11,59,17,7,272,7,48,5,2,24,52,7,11,102,8,15,2,268,11,24,122,11,195,7,24,2,8,7,7,2,2,62,64,272,11,20,6,2,21,31,89,11,91,2,340,62,53,24,6,62,62,46,24,75,312,8,2,2,134,11,94,21,13,6,6,8,91,24,2,6,11,88,24,24,264,24,10,62,62,24,6,11,11,24,10,276,324,7,89,24,24,89,2,10,83,63,3,58,24,62,187,104,320,11,2,191,272,60,2,24,187,6,24,2,13,7,7,272,2,62,20,195,7,7,264,272,2,64,62,3,24,2,20,58,60,9,24,2,24,195,2,264,2,4,62,272,5,6,244,24,11,5,6,86,24,6,6,7,187,20,89,24,328,2,7,7,6,24,48,24,62,24,11,11,338,11,8,7,11,2,59,2,61,2,2,2,62,11,11,260,62,13,20,5,89,62,5,2,108,47,20,15,62,11,100,24,2,24,2,9,7,2,6,62,5,2,1,268,94,8,89,48,195,2,8,62,2,2,2,24,24,320,2,24,324,7,29,2,6,34,7,328,62,24,58,61,62,191,272,5,9,62,20,13,24,24,9,2,20,62,24,64,7,7,64,46,2,272,89,2,40,6,51,101,2,7,11,11,7,64,62,7,11,24,59,62,191,58,58,62,8,5,6,11,24,100,2,24,2,8,187,356,34,97,4,11,89,2,191,8,62,5,89,93,244,9,13,64,20,7,34,11,7,195,64,6,46,2,24,2,13,2,34,2,260,4,91,4,2,10,60,62,62,17,48,24,2,63,24,69,24,7,332,2,95,272,6,6,7,7,5,2,14,64,62,7,3,91,84,268,2,2,24,11,195,11,60,8,2,13,8,8,13,59,13,24,2,2,320,62,2,2,2,127,126,91,11,11,142,59,7,61,4,24,272,191,24,344,144,11,2,11,56,2,7,272,320,20,5,13,21,332,24,44,7,264,6,195,24,2,6,62,64,2,332,2,18,74,2,24,2,61,2,2,40,20,332,2,62,9,12,2,260,4,15,24,29,8,60,24,5,4,268,6,6,2,11,23,272,8,2,13,7,2,11,5,272,6,276,195,272,2,2,8,24,7,272,2,58,272,187,2,6,2,62,6,24,24,2,24,62,4,11,272,320,6,62,7,13,24,62,272,86,6,191,2,348,49,2,9,11,6,9,24,90,59,2,6,24,64,244,2,7,48,20,328,2,2,6,6,24,2,3,2,20,7,6,62,90,24,137,20,268,62,62,6,24,264,344,8,268,56,2,23,24,2,62,19,336,2,2,2,16,5,11,2,24,24,9,8,2,8,2,8,52,5,48,64,23,64,46,6,244,320,2,2,2,24,24,60,60,76,11,20,320,7,7,7,62,62,2,191,272,2,59,2,20,64,11,8,59,5,2,9,2,5,86,63,8,2,2,34,3,101,107,2,18,24,11,64,5,2,2,7,2,9,272,2,7,8,24,49,59,11,100,11,2,56,58,16,13,2,12,6,2,24,268,316,195,64,10,24,24,11,91,100,7,328,11,61,11,2,24,11,13,24,11,20,3,2,24,2,2,62,8,80,13,2,24,91,24,58,89,9,24,264,191,11,6,2,64,9,37,87,103,59,11,13,11,2,11,20,191,58,11,6,5,7,64,7,13,24,62,2,49,7,62,62,320,9,91,24,24,2,17,320,24,11,3,9,195,11,24,62,24,13,64,2,5,52,2,6,6,6,45,62,6,2,7,88,272,62,195,58,24,272,6,40,58,8,20,11,62,58,44,7,7,24,2,5,59,5,2,24,58,62,2,4,56,24,24,4,11,89,24,9,11,9,332,7,60,59,272,24,332,60,8,24,320,6,11,24,264,28,11,9,20,24,24,6,11,2,11,52,56,8,2,3,24,56,2,64,1,2,50,2,24,24,91,24,64,191,2,6,89,264,7,12,24,2,324,111,12,20,59,62,17,62,44,56,10,12,20,7,5,86,2,5,11,195,64,13,15,48,5,3,2,334,6,352,2,62,2,20,60,58,2,75,7,57,13,64,191,11,2,43,24,219,18,92,383,13,18,62,272,2,11,64,11,62,2,91,5,272,64,264,11,2,17,51,268,11,2,2,5,24,2,27,9,2,272,8,58,276,51,96,9,2,106,7,24,5,8,24,7,12,11,3,56,20,24,5,7,2,20,11,2,8,64,11,62,272,8,20,3,320,62,24,96,62,24,46,191,6,11,62,7,320,20,191,85,18,7,5,4,10,61,62,56,24,8,7,24,320,49,10,73,20,8,8,62,336,56,83,58,118,62,2,11,11,7,24,16,11,13,27,5,2,7,8,11,2,11,6,11,2,2,2,6,7,5,2,260,320,2,8,22,21,5,62,16,64,2,5,13,7,2,9,8,7,45,44,62,332,8,11,24,6,5,268,7,2,2,7,7,24,62,7,13,67,109,18,13,58,2,11,8,6,8,59,12,2,268,103,24,6,24,24,2,17,59,11,85,6,6,86,2,11,7,2,11,2,7,24,7,2,7,24,2,3,11,7,5,24,91,3,7,7,64,2,1,2,5,62,5,13,5,268,2,187,2,157,24,2,324,20,11,2,24,2,80,260,2,8,16,3,64,68,87,2,2,64,60,29,11,11,24,10207,24,115,24,268,20,95,5,24,62,6,7,2,2,62,64,2,46,103,6,19,2,195,62,2,13,13,62,2,7,46,272,191,332,2,276,24,264,2,20,8,91,13,62,191,64,11,62,52,24,62,64,320,8,215,24,24,2,2,13,12,260,5,62,90,24,2,7,11,2,64,50,24,24,2,6,59,264,72,2,48,2,24,272,24,272,64,11,20,11,64,6,276,73,109,3,48,187,22,62,2,60,272,7,67,24,64,13,11,2,2,5,2,2,64,7,11,62,11,62,61,2,272,61,2,62,89,8,24,272,24,9,131,6,11,24,11,17,9,24,2,272,2,5,2,207,272,7,191,60,2,87,5,2,59,2,13,272,64,3,89,24,20,56,11,107,191,3,24,3,2,24,7,3,6,7,6,43,2,23,16,60,13,38,2,13,2,6,7,2,328,89,64,41,64,276,59,24,64,2,6,7,8,2,91,24,13,2,272,11,18,6,62,5,64,240,7,89,324,8,320,5,10,20,2,64,11,129,2,67,2,20,64,2,5,2,2,7,264,5,272,24,7,62,24,20,48,2,24,62,272,5,24,2,5,20,62,2,11,6,11,60,24,13,24,324,9,62,58,89,11,46,109,195,336,24,24,5,89,13,8,2,6,64,8,61,81,59,13,97,2,7,4,7,49,64,24,2,2,60,5,7,44,25,187,11,64,24,2,24,61,24,86,2,24,31,6,7,340,2,24,195,3,2,5,47,8,92,5,61,24,62,64,62,120,12,20,61,2,1,11,64,44,92,13,20,2,50,3,5,6,14,2,62,2,97,5,13,3,62,352,272,2,59,9,19,6,7,7,11,62,6,87,32,62,98,20,62,62,11,62,2,60,5,45,2,272,2,62,89,20,2,5,2,1,138,64,57,64,62,20,24,6,3,11,2,24,2,11,142,62,56,62,62,64,6,24,91,11,62,2,272,58,141,2,195,5,24,62,2,191,207,2,272,46,121,264,5,244,268,2,44,5,58,64,9,2,272,11,320,24,2,2,2,11,2,2,24,52,95,2,2,2,9,5,191,3,191,59,9,13,89,2,264,195,2,64,33,20,32,9,7,324,9,5,48,7,9,2,272,11,276,2,272,89,2,11,9,62,6,6,2,2,272,58,6,272,46,11,328,272,4,20,7,61,11,24,62,56,260,11,272,60,62,24,2,10,61,7,2,24,10,112,62,6,13,2,11,64,59,272,2,62,13,11,2,2,62,20,58,8,2,48,9,8,2,105,49,11,13,11,2,2,89,272,232,91,2,24,2,2,64,2,56,24,63,6,13,24,7,3,340,11,24,4,14,191,272,334,45,7,24,62,6,8,62,1,13,56,8,2,332,64,20,9,24,9,7,272,60,62,62,195,7,7,2,60,5,272,11,328,7,24,328,24,46,24,24,2,328,24,11,2,64,62,24,7,2,2,45,2,6,2,11,191,2,89,60,88,5,44,2,8,24,60,62,2,2,2,11,13,62,187,2,2,62,11,6,264,320,60,2,47,2,71,6,11,264,6,115,2,61,2,7,2,6,191,2,324,5,2,260,15,7,2,191,272,191,51,5,11,2,20,2,7,64,7,20,125,2,89,2,324,24,103,272,14,64,7,62,191,24,2,7,6,3,6,62,89,3,2,7,13,56,91,62,3,2,31,6,24,99,61,7,236,108,5,11,58,8,24,320,272,7,7,8,24,191,120,352,26,24,316,58,6,2,24,8,5,2,272,62,272,16,191,8,6,24,191,11,11,22,268,20,2,64,59,6,12,17,62,11,11,6,20,195,8,2,62,64,92,6,63,7,24,7,2,20,62,99,70,7,3,50,62,62,272,9,2,62,6,4,2,92,24,7,62,2,2,9,11,36,2,264,195,91,2,6,13,7,2,3,20,64,62,6,24,64,53,13,13,7,5,133,56,13,5,2,272,2,2,64,2,66,6,5,50,24,2,6,24,8,62,131,91,272,63,2,6,24,11,145,7,9,195,24,24,11,6,195,24,11,62,24,2,64,8,24,272,108,6,6,48,95,2,89,7,24,9,13,2,7,2,2,2,13,2,2,5,191,320,11,24,92,332,59,191,31,24,7,24,11,13,62,340,82,6,24,24,24,7,11,7,20,2,7,1,272,2,2,48,11,8,7,98,2,13,2,20,7,6,2,24,77,24,2,89,62,2,11,3,272,35,91,6,2,320,60,61,24,2,62,20,64,195,24,13,195,2,9,24,5,2,5,24,2,2,56,25,11,62,11,12,14,2,2,15,2,15,2,13,2,8,91,272,62,191,142,52,2,24,335,195,268,24,7,2,9,2,102,11,2,62,24,24,62,352,11,6,45,61,195,87,49,24,45,2,195,62,20,7,17,320,13,20,62,3,191,24,60,3,5,27,6,64,2,24,46,6,324,20,2,24,61,5,64,62,2,11,268,2,6,13,24,312,58,2,4,7,24,62,52,64,320,5,61,91,8,2,2,2,2,2,64,64,143,11,81,2,7,2,2,20,272,2,7,312,24,57,24,6,324,2,7,2,2,24,2,17,191,272,2,100,64,272,51,59,24,62,320,3,62,272,2,272,2,89,16,2,41,7,2,24,17,276,6,24,62,272,62,6,92,89,8,62,20,3,2,7,7,8,320,276,84,5,2,89,60,24,11,1,62,6,7,58,3,24,26,11,11,67,24,272,11,272,64,20,1,62,272,11,272,97,24,58,91,11,62,20,2,8,62,187,24,9,272,5,2,272,9,20,14,11,2,91,7,7,7,59,1,11,64,20,40,62,3,9,276,2,2,61,24,3,2,24,8,59,11,2,2,20,11,7,20,2,59,2,5,2,99,191,2,11,2,2,24,6,34,66,91,11,2,11,1,11,10,24,24,2,268,13,195,2,99,2,7,191,8,62,2,2,2,9,59,62,272,63,24,8,5,2,2,62,8,2,8,24,7,62,11,8,91,5,272,7,2,2,11,272,114,11,8,24,15,2,5,64,6,272,11,24,2,4,2,20,8,6,6,8,272,64,40,3,6,46,59,54,30,2,272,8,6,13,98,5,11,57,6,12,11,276,37,6,6,2,13,90,11,2,9,11,328,62,62,26,2,22,6,11,62,272,7,1,2,24,58,24,40,61,20,6,10,5,2,62,11,62,272,2,3,260,13,2,85,29,16,142,64,62,7,24,7,4,2,11,24,8,112,2,268,2,20,2,9,191,11,24,9,11,62,64,2,100,59,320,24,7,11,13,2,24,2,28,11,11,5,187,5,59,16,7,13,13,2,24,3,96,103,3,98,62,24,11,7,11,9,8,2,59,24,2,320,24,2,86,2,2,47,191,8,21,140,61,2,8,10,24,328,1,2,12,6,24,11,11,7,2,7,142,2,2,13,14,58,24,6,13,2,59,11,13,24,2,2,24,61,2,9,320,24,62,2,24,91,40,13,2,2,61,49,2,12,26,24,24,7,8,1,272,138,13,320,8,2,24,24,7,60,7,87,5,272,89,45,89,16,46,135,336,62,7,2,62,2,91,20,2,5,89,7,8,24,2,13,64,11,5,195,24,11,64,2,24,3,13,11,2,8,2,11,2,6,2,6,62,62,268,9,7,1,8,58,2,2,24,24,7,11,7,24,2,9,2,7,24,5,8,5,6,13,264,2,272,24,6,20,191,2,2,2,64,2,11,91,24,20,272,24,13,59,7,24,114,503,63,90,2,2,11,6,340,49,2,135,113,2,62,5,46,9,2,7,5,24,24,195,87,195,191,51,13,27,12,64,24,5,6,8,91,59,96,5,89,91,2,20,58,15,11,11,74,62,61,7,64,58,24,24,2,328,320,2,89,11,6,24,7,7,6,89,2,24,195,62,51,348,58,48,62,24,11,2,24,56,2,7,116,13,11,24,24,7,20,64,59,6,62,24,91,64,4,8,3,2,2,272,36,2,24,272,59,3,9,272,88,2,7,3,7,4,2,17,6,191,6,195,69,4,60,8,8,2,320,2,2,2,128,108,61,2,20,47,3,191,24,2,272,9,24,12,6,58,2,2,8,9,13,6,31,62,11,64,7,11,13,87,21,61,11,320,7,272,139,49,2,2,64,63,6,8,58,47,2,2,11,91,20,2,268,324,3,8,64,40,228,17,264,89,2,91,6,11,2,11,7,191,49,2,62,11,2,13,191,11,7,24,101,11,2,87,6,5,7,272,272,2,64,195,5,187,74,59,11,27,272,62,195,272,11,8,6,67,2,59,62,2,24,62,2,7,24,2,11,91,3,4,7,272,20,49,62,62,5,5,20,13,6,2,64,62,2,9,95,24,2,2,27,117,215,2,24,24,61,20,2,2,3,2,8,24,24,64,139,7,21,7,62,2,2,58,5,7,2,344,98,6,62,115,268,5,320,62,7,15,24,11,6,24,5,64,344,11,24,62,324,62,24,2,13,7,6,268,5,2,2,24,8,46,10,7,30,6,2,2,89,20,2,64,62,34,24,2,62,2,320,62,7,215,272,16,24,9,44,5,7,9,9,20,24,58,2,5,11,272,2,61,29,62,24,90,268,24,37,8,272,20,20,24,3,6,7,8,320,20,11,2,62,9,7,62,272,62,91,2,2,320,8,272,13,276,264,2,58,45,11,2,24,8,11,2,11,2,6,7,6,2,40,11,2,320,45,20,2,9,264,62,2,24,20,2,11,24,7,7,89,2,11,8,185,64,62,11,7,24,11,6,62,19,10,11,62,22,17,2,8,11,77,191,45,7,24,195,3,64,24,2,272,62,191,89,60,24,91,24,97,7,276,6,63,6,272,2,5,116,91,272,59,2,109,24,5,74,142,24,6,2,2,11,15,268,64,5,4,59,102,2,8,195,7,11,8,24,268,2,62,2,272,11,103,13,326,6,62,38,89,17,2,11,56,264,24,2,7,24,2,24,2,11,2,6,62,20,11,17,24,24,64,38,95,20,7,13,56,264,58,2,62,24,60,24,20,3,272,24,3,86,85,89,3,12,191,32,7,2,272,5,24,334,5,7,129,7,62,61,24,2,7,104,58,64,4,130,2,11,24,195,3,88,24,3,344,56,61,89,21,7,68,91,272,2,92,20,2,2,12,2,6,58,13,3,191,7,62,272,62,2,11,62,2,428,24,11,324,195,62,7,11,2,2,6,324,62,6,61,13,20,9,62,5,24,16,8,24,2,3,2,62,344,60,2,11,11,24,13,5,20,91,61,20,60,24,24,64,272,5,7,8,272,62,46,11,191,62,3,64,6,130,24,2,219,11,7,2,11,2,62,126,61,2,64,24,6,24,3,272,60,2,8,64,8,5,272,11,6,5,24,22,13,89,5,11,59,11,6,24,62,272,11,2,6,6,5,24,7,5,8,272,19,195,272,15,2,20,3,348,2,4,13,8,24,24,24,62,48,2,11,49,59,43,4,20,272,62,59,59,91,11,16,48,11,6,16,272,24,62,13,2,62,8,6,24,20,24,11,7,272,73,13,191,13,24,2,8,34,2,352,103,64,20,24,11,7,61,11,11,11,3,62,60,2,7,24,8,1,15,24,24,13,24,64,24,2,5,11,8,5,6,14,62,2,276,2,20,5,24,25,2,20,16,11,2,2,2,7,98,13,2,8,2,191,11,2,7,56,20,77,62,24,58,6,8,91,24,5,60,7,272,11,332,43,2,90,4,11,20,5,7,62,58,187,51,2,61,48,7,2,62,7,244,6,62,62,332,335,56,24,2,17,7,67,191,11,11,2,62,7,2,24,14,2,5,11,48,6,324,24,61,2,115,6,24,8,7,2,13,62,11,62,52,49,2,5,7,2,7,62,320,24,39,89,62,49,44,20,2,4,11,191,2,195,2,3,320,2,2,58,24,58,2,268,6,24,64,7,47,8,89,2,7,2,11,6,8,3,87,2,24,6,324,2,24,20,24,96,64,9,7,20,2,2,2,7,2,2,2,60,20,24,20,8,34,8,320,9,272,11,8,191,2,24,58,62,272,24,6,64,2,272,64,64,7,11,3,8,8,91,20,11,62,46,89,20,195,62,2,328,60,3,86,320,142,18,20,7,20,272,272,64,232,26,60,89,62,62,2,9,2,13,2,13,7,20,2,20,62,7,89,36,58,97,24,2,4,117,8,60,9,7,58,64,91,11,14,195,11,24,40,48,324,24,9,60,59,9,2,2,272,2,6,2,11,191,24,105,181,6,272,2,91,60,60,24,23,24,272,348,2,13,6,43,91,64,7,13,272,11,6,11,64,195,7,62,9,24,7,569,2,2,195,91,5,55,101,71,6,64,2,43,13,5,2,18,64,61,2,62,89,260,3,272,11,5,7,60,24,62,15,19,47,40,6,24,6,324,51,6,6,264,7,24,6,7,64,272,24,324,24,104,2,62,91,2,56,7,24,276,11,11,53,7,8,272,24,11,2,24,24,7,338,24,272,7,62,69,62,191,11,2,7,18,3,89,11,320,2,348,7,7,272,64,2,6,2,2,4,62,94,91,187,8,11,7,2,11,2,11,92,272,62,11,5,7,272,62,11,105,13,20,104,24,8,5,2,328,11,11,2,2,11,11,11,2,8,24,58,58,98,17,2,276,7,62,51,5,2,2,20,24,2,60,20,11,5,2,62,11,7,60,6,276,2,59,2,7,2,2,2,86,24,13,2,118,2,11,6,260,2,62,2,2,91,6,6,6,5,2,3,13,24,11,104,320,244,2,24,340,2,9,11,35,9,89,11,7,2,24,7,2,122,6,46,7,268,272,2,16,24,85,118,24,215,52,24,191,260,2,2,62,272,2,11,39,2,16,2,272,20,48,6,7,64,64,2,5,6,348,24,5,2,2,2,11,13,87,24,5,332,64,13,24,5,2,13,4,47,62,64,268,8,91,195,24,64,7,5,62,89,260,64,21,2,93,24,34,60,3,62,2,272,2,89,98,49,8,3,11,59,62,13,64,320,62,64,6,7,96,3,195,64,191,11,5,24,47,62,20,62,3,272,272,24,2,191,16,102,2,59,2,7,56,24,11,2,11,11,15,2,6,24,62,24,11,9,187,91,2,58,320,6,20,7,2,5,316,6,2,24,8,22,6,59,46,2,2,24,11,191,86,61,91,272,91,85,320,2,59,8,207,24,2,2,24,24,106,6,56,31,2,5,6,38,6,187,5,6,10,64,11,4,13,11,8,2,24,344,2,106,8,91,86,336,69,5,187,11,8,272,13,24,7,5,61,11,86,2,62,264,2,7,11,11,272,7,383,22,7,13,7,62,7,320,2,62,6,58,2,7,58,13,2,2,191,12,2,6,13,272,2,2,6,48,9,6,31,61,332,6,2,44,272,24,49,7,2,2,59,20,276,2,2,7,2,6,62,24,20,2,7,7,58,24,5,7,6,2,2,195,10,6,2,69,7,24,24,11,2,8,46,7,13,24,24,8,7,14,2,2,2,89,24,6,44,2,64,2,2,48,2,62,7,2,2,2,7,6,191,11,35,2,91,8,8,2,183,61,2,62,2,9,60,2,7,2,89,9,24,24,24,11,64,2,11,11,2,48,2,11,56,11,2,7,64,5,7,62,24,24,191,24,24,91,4,7,24,62,6,11,7,92,2,2,2,2,44,2,276,2,2,332,2,133,46,2,941,272,11,2,8,8,59,24,10,24,2,2,272,6,195,2,7,191,8,5,64,91,5,62,2,20,48,7,2,264,20,89,58,7,45,7,61,24,11,5,15,2,11,15,272,24,12,5,11,6,2,24,64,7,272,268,11,24,13,20,62,24,62,48,272,9,44,11,3,332,11,105,2,89,62,105,24,58,7,2,272,7,24,30,138,11,62,11,2,2,24,62,7,2,7,8,24,104,6,13,20,9,2,272,6,2,268,24,38,6,24,2,62,272,5,6,11,2,24,13,8,272,62,276,24,58,2,24,89,91,2,64,272,2,2,69,6,272,24,24,24,2,50,30,2,62,13,6,272,64,6,86,20,2,98,7,60,3,2,17,3,127,13,7,11,7,24,6,62,8,316,7,62,61,268,7,100,62,11,2,2,2,13,2,24,191,2,56,43,2,62,5,356,58,59,299,14,62,138,6,5,11,191,3,272,15,320,11,2,276,2,91,11,2,16,2,11,2,22,62,64,7,2,13,58,49,320,9,2,52,13,7,2,13,2,2,7,2,2,3,8,2,11,12,320,11,24,6,6,6,35,324,7,20,43,2,11,20,60,2,8,59,108,13,13,13,6,264,89,11,24,8,87,72,24,191,2,45,6,6,59,13,16,2,191,13,7,2,8,24,18,3,62,272,11,6,276,8,3,116,272,58,62,99,2,4,2,2,62,6,2,59,7,73,6,320,12,24,49,264,15,12,20,2,3,59,8,24,4,20,324,2,195,13,105,13,100,11,272,24,328,62,2,13,11,15,2,11,2,62,272,7,7,6,24,3,6,62,13,324,11,109,11,20,24,2,7,11,24,62,11,13,6,63,13,11,24,2,2,4,6,264,2,191,24,2,138,7,7,2,24,2,64,6,74,13,272,2,191,2,3,5,2,5,6,62,3,11,2,195,8,6,195,7,62,17,14,93,348,56,2,5,6,191,64,8,6,2,91,264,18,62,27,9,6,2,1,20,48,2,2,24,29,11,2,20,8,2,2,328,76,2,67,7,24,7,7,2,2,12,2,2,9,96,2,62,17,5,13,344,13,24,8,48,7,2,60,59,2,24,2,91,92,8,2,2,7,272,32,2,7,2,11,9,24,2,20,11,276,24,11,88,24,2,24,59,87,6,11,2,24,2,191,2,24,60,20,11,58,62,62,2,16,5,2,62,61,2,108,8,62,24,24,89,2,11,11,91,2,24,87,3,7,6,8,24,2,38,5,11,62,13,24,6,191,2,6,11,20,6,7,99,91,191,8,24,58,2,20,7,9,10,2,7,2,2,5,58,6,3,272,2,63,12,14,2,24,348,62,6,272,24,6,24,91,272,320,7,6,276,2,2,24,60,84,8,2,22,324,58,7,12,11,272,14,62,2,187,2,13,2,6,24,5,104,11,89,272,46,6,3,268,11,3,91,110,328,2,268,60,2,2,7,60,2,11,24,51,2,7,9,24,102,13,13,62,3,6,272,6,2,2,60,8,272,13,91,64,14,60,2,6,45,7,89,24,8,58,24,268,2,59,62,8,11,6,272,11,8,62,6,2,2,344,6,13,62,62,260,62,62,2,2,6,16,4,24,7,195,15,10,64,7,11,6,89,2,11,58,4,89,24,114,272,2,5,17,13,272,62,11,6,6,2,276,64,24,2,24,8,56,62,2,91,2,24,272,272,2,107,121,24,13,64,47,59,15,24,2,2,24,103,312,24,3,62,11,272,191,2,10,6,2,320,268,12,64,260,91,2,51,64,2,16,25,7,276,26,13,245,272,108,187,6,93,276,6,24,2,264,11,24,11,2,20,328,4,11,2,2,24,9,272,3,6,45,6,2,272,2,2,64,7,11,62,89,6,272,264,7,49,64,62,6,7,24,6,3,2,2,191,6,2,45,62,26,2,89,20,24,2,272,24,8,268,24,8,7,195,120,24,2,264,27,272,24,2,24,58,15,2,62,102,16,7,24,40,8,17,24,2,24,7,6,316,1,4,62,11,7,2,2,2,2,86,272,61,24,7,11,272,89,5,5,91,11,8,62,24,2,2,98,2,64,24,3,91,2,8,20,62,24,2,11,8,62,70,5,324,63,2,2,2,62,8,2,5,24,24,20,7,191,59,22,2,89,11,89,11,8,8,93,53,7,11,13,11,25,2,15,24,62,2,5,272,2,270,20,7,6,18,24,9,191,191,2,62,291,2,62,2,91,6,272,24,6,2,2,18,2,24,264,2,7,272,272,24,2,24,24,2,62,24,62,11,62,59,24,260,6,24,24,62,60,11,2,62,62,24,38,6,9,332,90,5,11,6,8,2,62,5,3,2,16,17,10,20,2,6,2,113,62,62,7,17,328,18,2,11,59,2,2,45,328,7,8,51,2,2,64,11,2,89,16,47,64,195,272,2,8,11,59,20,62,5,2,24,20,2,1,9,4,24,191,2,48,11,8,11,24,2,272,62,20,268,3,6,7,62,2,71,272,268,95,24,24,24,62,62,62,5,20,11,7,13,7,6,195,22,7,62,2,2,34,2,58,2,5,24,61,82,5,2,24,107,2,272,62,5,20,2,24,2,8,64,91,2,2,6,83,2,64,2,45,2,195,276,4,10,60,10,16,9,24,264,25,11,59,24,6,62,8,48,13,11,2,60,59,2,13,20,11,2,8,6,64,24,52,89,11,2,2,6,2,2,8,272,55,272,20,2,6,1,24,7,7,7,12,14,62,24,320,2,191,2,48,13,2,9,43,60,6,112,191,137,24,11,2,272,62,5,40,2,88,7,272,2,60,13,24,6,58,24,13,6,272,272,2,56,24,272,62,24,2,6,7,62,5,13,3,7,24,4,58,3,47,268,7,272,64,5,62,58,92,2,11,62,24,58,9,90,6,59,13,11,11,2,24,7,2,2,13,105,2,13,24,5,8,8,59,20,118,8,8,59,2,11,24,13,2,62,2,13,268,264,24,24,20,24,11,5,10,7,58,59,93,11,2,24,24,11,91,52,62,2,2,272,344,3,61,24,3,88,13,2,2,3,1,2,1,324,24,2,100,2,64,92,89,97,7,7,11,11,13,6,8,91,272,51,24,62,62,58,340,58,1,2,60,272,7,79,29,2,8,59,6,6,2,24,8,2,46,6,24,11,24,24,2,195,320,24,6,118,6,272,6,14,64,89,96,2,11,24,476,7,1,69,332,24,44,18,11,11,7,8,2,272,12,17,2,84,2,91,62,2,11,2,320,8,6,58,2,42,24,4,6,2,13,91,24,2,328,62,5,2,1,64,2,6,64,11,244,47,7,98,320,2,62,11,91,2,61,20,89,24,46,62,2,2,2,272,4,60,7,2,6,24,24,61,2,18,272,2,59,2,2,24,2,8,96,71,64,24,2,26,2,2,11,8,11,2,2,7,91,332,2,2,109,4,9,8,8,64,56,64,11,62,11,24,272,47,3,7,6,24,2,272,9,272,24,2,41,6,348,7,17,6,2,11,5,11,11,4,2,276,191,9,2,7,8,62,2,13,9,276,272,2,334,24,6,2,24,2,2,24,24,4,59,7,58,24,7,2,20,6,2,272,24,2,5,89,1,20,11,64,91,2,7,11,13,62,2,7,72,2,5,59,2,62,2,61,2,18,114,11,24,7,49,3,64,59,58,89,2,16,272,5,2,6,24,7,312,5,4,2,13,8,2,62,44,8,2,91,316,7,2,15,97,8,69,20,9,62,62,62,2,13,5,7,352,8,11,85,2,9,6,43,272,6,2,33,50,2,11,3,1,50,2,10,2,60,59,7,64,56,2,24,24,40,89,24,13,11706,103,6,48,2,62,64,64,2,3,2,62};
size_t *s = zmalloc(sizeof(samples));
memcpy(s,samples,sizeof(samples));
srandom(time(NULL));
return s;
}
#endif

/* The following function implements the "vmpage" statistic, that is,
 * it tries to perform a few simulations with data gained from the dataset
 * in order to understand what's the best vm-page-size for your dataset.
 *
 * How dows it work? We use VMPAGE_PAGES pages of different sizes, and simulate
 * adding data with sizes sampled from the real dataset, in a random way.
 * While doing this we take stats about how efficiently our application is
 * using the swap file with every given page size. The best will win.
 *
 * Why the thing we take "fixed" is the number of pages? It's our constant
 * as Redis will use one bit of RAM for every page in the swap file, so we
 * want to optimized page size while the number of pages is taken fixed. */
#define VMPAGE_PAGES 1000000
static void vmpage() {
    redisContext *c = config.context;
    int j, pagesize, bestpagesize = 0;
    double bestscore = 0;
    size_t *samples;

    samples = sampleDataset(c,SAMPLE_SERIALIZEDLEN);
    printf("Simulate fragmentation with different page sizes...\n");
    for (pagesize = 8; pagesize <= 1024*64; pagesize*=2) {
        size_t totpages = VMPAGE_PAGES;
        unsigned char *pages = zmalloc(totpages);
        size_t stored_bytes, used_pages;
        double score;

        printf("%d: ",pagesize);
        fflush(stdout);
        stored_bytes = used_pages = 0;
        memset(pages,0,totpages);
        while(1) {
            int r = random() % config.samplesize;
            size_t bytes_needed = samples[r];
            size_t pages_needed = (bytes_needed+(pagesize-1))/pagesize;

            for(j = 0; j < 200; j++) {
                size_t off = random()%(totpages-(pages_needed-1));
                size_t i;

                for (i = off; i < off+pages_needed; i++)
                    if (pages[i] != 0) break;
                if (i == off+pages_needed) {
                    memset(pages+off,1,pages_needed);
                    used_pages += pages_needed;
                    stored_bytes += bytes_needed;
                    break;
                }
            }
            if (j == 200) break;
        }
        printf("bytes per page: %.2lf, space efficiency: %.2lf%%\n",
            (double)stored_bytes/totpages,
            ((double)stored_bytes*100)/(totpages*pagesize));
        score = ((double)stored_bytes/totpages)*
                (((double)stored_bytes*100)/(totpages*pagesize));
        if (bestpagesize == 0 || bestscore < score) {
            bestpagesize = pagesize;
            bestscore = score;
        }
        zfree(pages);
    }
    printf("\nThe best compromise between bytes per page and swap file size: %d\n", bestpagesize);
    zfree(samples);
}

#define SCALE_POWEROFTWO 0
#define SCALE_LINEAR_SMALL 1
#define SCALE_LINEAR_MED 2
#define SCALE_LINEAR_LARGE 3
#define SCALE_LINEAR_AUTO 4
#define GRAPH_ROWS 20
#define GRAPH_BAR_LEN 50
static void samplesToGraph(size_t *samples, int scaletype) {
    size_t freq[GRAPH_ROWS];
    size_t scale[GRAPH_ROWS];
    size_t max = 0, sum = 0;
    int j, i, high;

    /* Best linear scale auto detection */
    if (scaletype == SCALE_LINEAR_AUTO) {
        scaletype = SCALE_LINEAR_SMALL;
        for (j = 0; j < config.samplesize; j++) {
            if (scaletype == SCALE_LINEAR_SMALL && samples[j] > 1*GRAPH_ROWS)
                scaletype = SCALE_LINEAR_MED;
            if (scaletype == SCALE_LINEAR_MED && samples[j] > 5*GRAPH_ROWS) {
                scaletype = SCALE_LINEAR_LARGE;
                break; /* there is no scale bigger than this. */
            }
        }
    }

    /* Initialize the frequency table and the scale. */
    memset(freq,0,sizeof(freq));
    for (j = 0; j < GRAPH_ROWS; j++) {
        switch(scaletype) {
        case SCALE_POWEROFTWO:
            scale[j] = (size_t) pow(2,j);
            break;
        case SCALE_LINEAR_SMALL:
            scale[j] = j+1;
            break;
        case SCALE_LINEAR_MED:
            scale[j] = (j+1)*5;
            break;
        case SCALE_LINEAR_LARGE:
            scale[j] = (j+1)*50;
            break;
        }
    }
    /* Increment the frequency table accordingly to the sample value */
    for (j = 0; j < config.samplesize; j++) {
        i = GRAPH_ROWS-1;
        while (i > 0 && scale[i-1] >= samples[j]) i--;
        freq[i]++;
        printf("SAMPLE: %ld\n", samples[j]);
    }
    /* Check what's the highest non-zero frequency element, so we can avoid
     * printing the part of the histogram that's empty. We also need the
     * max value in the freq table. */
    for (high = GRAPH_ROWS-1; high > 0; high--)
        if (freq[high]) break;
    for (j = 0; j <= high; j++) {
        if (max < freq[j]) max = freq[j];
        sum += freq[j];
    }
    /* Our ASCII art business can start */
    for (j = 0; j <= high; j++) {
        char buf[64];
        char bar[GRAPH_BAR_LEN+1];
        int barlen;

        if (j != high)
            sprintf(buf,"<= %ld",(long)scale[j]);
        else
            sprintf(buf,">  %ld",(long)scale[j-1]);
        barlen = (freq[j]*GRAPH_BAR_LEN)/max;
        memset(bar,'-',barlen);
        bar[barlen] = '\0';
        printf("%-13s |%s (%.2f%%)\n", buf, bar,
            (float)freq[j]*100/sum);
    }
    zfree(samples);
}

static void ondiskSize() {
    redisContext *c = config.context;
    size_t *samples;

    samples = sampleDataset(c,SAMPLE_SERIALIZEDLEN);
    if (config.logscale) {
        samplesToGraph(samples, SCALE_POWEROFTWO);
    } else {
        samplesToGraph(samples, SCALE_LINEAR_AUTO);
    }
}

static void usage(char *wrong) {
    if (wrong)
        printf("Wrong option '%s' or option argument missing\n\n",wrong);
    printf(
"Usage: redis-stat <type> ... options ...\n\n"
"Statistic types:\n"
" overview (default)   Print general information about a Redis instance.\n"
" vmstat               Print information about Redis VM activity.\n"
" vmpage               Try to guess the best vm-page-size for your dataset.\n"
" ondisk-size          Stats and graphs about values len once stored on disk.\n"
" latency              Measure Redis server latency.\n"
"\n"
"Options:\n"
" host <hostname>      Server hostname (default 127.0.0.1)\n"
" port <hostname>      Server port (default 6379)\n"
" delay <milliseconds> Delay between requests (default: 1000 ms, 1 second).\n"
" samplesize <keys>    Number of keys to sample for 'vmpage' stat.\n"
" logscale             User power-of-two logarithmic scale in graphs.\n"
);
    exit(1);
}

static int parseOptions(int argc, char **argv) {
    int i;

    for (i = 1; i < argc; i++) {
        int lastarg = (i == (argc-1));

        if (!strcmp(argv[i],"host") && !lastarg) {
            config.hostip = argv[i+1];
            i++;
        } else if (!strcmp(argv[i],"port") && !lastarg) {
            config.hostport = atoi(argv[i+1]);
            i++;
        } else if (!strcmp(argv[i],"delay") && !lastarg) {
            config.delay = atoi(argv[i+1]);
            i++;
        } else if (!strcmp(argv[i],"samplesize") && !lastarg) {
            config.samplesize = atoi(argv[i+1]);
            i++;
        } else if (!strcmp(argv[i],"vmstat")) {
            config.stat = STAT_VMSTAT;
        } else if (!strcmp(argv[i],"vmpage")) {
            config.stat = STAT_VMPAGE;
        } else if (!strcmp(argv[i],"overview")) {
            config.stat = STAT_OVERVIEW;
        } else if (!strcmp(argv[i],"ondisk-size")) {
            config.stat = STAT_ONDISK_SIZE;
        } else if (!strcmp(argv[i],"latency")) {
            config.stat = STAT_LATENCY;
        } else if (!strcmp(argv[i],"logscale")) {
            config.logscale = 1;
        } else if (!strcmp(argv[i],"help")) {
            usage(NULL);
        } else {
            usage(argv[i]);
        }
    }
    return i;
}

int main(int argc, char **argv) {
    redisContext *c;

    config.hostip = "127.0.0.1";
    config.hostport = 6379;
    config.stat = STAT_OVERVIEW;
    config.delay = 1000;
    config.samplesize = 10000;
    config.logscale = 0;

    parseOptions(argc,argv);

    c = config.context = redisConnect(config.hostip,config.hostport);
    if (c->err) {
        fprintf(stderr, "Error connecting to Redis: %s\n", c->errstr);
        exit(1);
    }

    switch(config.stat) {
    case STAT_VMSTAT:
        vmstat();
        break;
    case STAT_VMPAGE:
        vmpage();
        break;
    case STAT_OVERVIEW:
        overview();
        break;
    case STAT_ONDISK_SIZE:
        ondiskSize();
        break;
    case STAT_LATENCY:
        latency();
        break;
    }
    return 0;
}