[redis.git] / src / redis-check-dump.c

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <string.h>
#include <arpa/inet.h>
#include <stdint.h>
#include <limits.h>
#include "lzf.h"

/* Object types */
#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4
#define REDIS_HASH_ZIPMAP 9
#define REDIS_LIST_ZIPLIST 10
#define REDIS_SET_INTSET 11
#define REDIS_ZSET_ZIPLIST 12

/* Objects encoding. Some kind of objects like Strings and Hashes can be
 * internally represented in multiple ways. The 'encoding' field of the object
 * is set to one of this fields for this object. */
#define REDIS_ENCODING_RAW 0    /* Raw representation */
#define REDIS_ENCODING_INT 1    /* Encoded as integer */
#define REDIS_ENCODING_ZIPMAP 2 /* Encoded as zipmap */
#define REDIS_ENCODING_HT 3     /* Encoded as an hash table */

/* Object types only used for dumping to disk */
#define REDIS_EXPIRETIME 253
#define REDIS_SELECTDB 254
#define REDIS_EOF 255

/* Defines related to the dump file format. To store 32 bits lengths for short
 * keys requires a lot of space, so we check the most significant 2 bits of
 * the first byte to interpreter the length:
 *
 * 00|000000 => if the two MSB are 00 the len is the 6 bits of this byte
 * 01|000000 00000000 =>  01, the len is 14 byes, 6 bits + 8 bits of next byte
 * 10|000000 [32 bit integer] => if it's 01, a full 32 bit len will follow
 * 11|000000 this means: specially encoded object will follow. The six bits
 *           number specify the kind of object that follows.
 *           See the REDIS_RDB_ENC_* defines.
 *
 * Lenghts up to 63 are stored using a single byte, most DB keys, and may
 * values, will fit inside. */
#define REDIS_RDB_6BITLEN 0
#define REDIS_RDB_14BITLEN 1
#define REDIS_RDB_32BITLEN 2
#define REDIS_RDB_ENCVAL 3
#define REDIS_RDB_LENERR UINT_MAX

/* When a length of a string object stored on disk has the first two bits
 * set, the remaining two bits specify a special encoding for the object
 * accordingly to the following defines: */
#define REDIS_RDB_ENC_INT8 0        /* 8 bit signed integer */
#define REDIS_RDB_ENC_INT16 1       /* 16 bit signed integer */
#define REDIS_RDB_ENC_INT32 2       /* 32 bit signed integer */
#define REDIS_RDB_ENC_LZF 3         /* string compressed with FASTLZ */

#define ERROR(...) { \
    printf(__VA_ARGS__); \
    exit(1); \
}

/* data type to hold offset in file and size */
typedef struct {
    void *data;
    size_t size;
    size_t offset;
} pos;

static unsigned char level = 0;
static pos positions[16];

#define CURR_OFFSET (positions[level].offset)

/* Hold a stack of errors */
typedef struct {
    char error[16][1024];
    size_t offset[16];
    size_t level;
} errors_t;
static errors_t errors;

#define SHIFT_ERROR(provided_offset, ...) { \
    sprintf(errors.error[errors.level], __VA_ARGS__); \
    errors.offset[errors.level] = provided_offset; \
    errors.level++; \
}

/* Data type to hold opcode with optional key name an success status */
typedef struct {
    char* key;
    int type;
    char success;
} entry;

/* Global vars that are actally used as constants. The following double
 * values are used for double on-disk serialization, and are initialized
 * at runtime to avoid strange compiler optimizations. */
static double R_Zero, R_PosInf, R_NegInf, R_Nan;

/* store string types for output */
static char types[256][16];

/* when number of bytes to read is negative, do a peek */
int readBytes(void *target, long num) {
    char peek = (num < 0) ? 1 : 0;
    num = (num < 0) ? -num : num;

    pos p = positions[level];
    if (p.offset + num > p.size) {
        return 0;
    } else {
        memcpy(target, (void*)((size_t)p.data + p.offset), num);
        if (!peek) positions[level].offset += num;
    }
    return 1;
}

int processHeader() {
    char buf[10] = "_________";
    int dump_version;

    if (!readBytes(buf, 9)) {
        ERROR("Cannot read header\n");
    }

    /* expect the first 5 bytes to equal REDIS */
    if (memcmp(buf,"REDIS",5) != 0) {
        ERROR("Wrong signature in header\n");
    }

    dump_version = (int)strtol(buf + 5, NULL, 10);
    if (dump_version < 1 || dump_version > 2) {
        ERROR("Unknown RDB format version: %d\n", dump_version);
    }
    return 1;
}

int loadType(entry *e) {
    uint32_t offset = CURR_OFFSET;

    /* this byte needs to qualify as type */
    unsigned char t;
    if (readBytes(&t, 1)) {
        if (t <= 4 || (t >=9 && t <= 12) || t >= 253) {
            e->type = t;
            return 1;
        } else {
            SHIFT_ERROR(offset, "Unknown type (0x%02x)", t);
        }
    } else {
        SHIFT_ERROR(offset, "Could not read type");
    }

    /* failure */
    return 0;
}

int peekType() {
    unsigned char t;
    if (readBytes(&t, -1) && (t <= 4 || (t >=9 && t <= 12) || t >= 253))
        return t;
    return -1;
}

/* discard time, just consume the bytes */
int processTime() {
    uint32_t offset = CURR_OFFSET;
    unsigned char t[4];
    if (readBytes(t, 4)) {
        return 1;
    } else {
        SHIFT_ERROR(offset, "Could not read time");
    }

    /* failure */
    return 0;
}

uint32_t loadLength(int *isencoded) {
    unsigned char buf[2];
    uint32_t len;
    int type;

    if (isencoded) *isencoded = 0;
    if (!readBytes(buf, 1)) return REDIS_RDB_LENERR;
    type = (buf[0] & 0xC0) >> 6;
    if (type == REDIS_RDB_6BITLEN) {
        /* Read a 6 bit len */
        return buf[0] & 0x3F;
    } else if (type == REDIS_RDB_ENCVAL) {
        /* Read a 6 bit len encoding type */
        if (isencoded) *isencoded = 1;
        return buf[0] & 0x3F;
    } else if (type == REDIS_RDB_14BITLEN) {
        /* Read a 14 bit len */
        if (!readBytes(buf+1,1)) return REDIS_RDB_LENERR;
        return ((buf[0] & 0x3F) << 8) | buf[1];
    } else {
        /* Read a 32 bit len */
        if (!readBytes(&len, 4)) return REDIS_RDB_LENERR;
        return (unsigned int)ntohl(len);
    }
}

char *loadIntegerObject(int enctype) {
    uint32_t offset = CURR_OFFSET;
    unsigned char enc[4];
    long long val;

    if (enctype == REDIS_RDB_ENC_INT8) {
        uint8_t v;
        if (!readBytes(enc, 1)) return NULL;
        v = enc[0];
        val = (int8_t)v;
    } else if (enctype == REDIS_RDB_ENC_INT16) {
        uint16_t v;
        if (!readBytes(enc, 2)) return NULL;
        v = enc[0]|(enc[1]<<8);
        val = (int16_t)v;
    } else if (enctype == REDIS_RDB_ENC_INT32) {
        uint32_t v;
        if (!readBytes(enc, 4)) return NULL;
        v = enc[0]|(enc[1]<<8)|(enc[2]<<16)|(enc[3]<<24);
        val = (int32_t)v;
    } else {
        SHIFT_ERROR(offset, "Unknown integer encoding (0x%02x)", enctype);
        return NULL;
    }

    /* convert val into string */
    char *buf;
    buf = malloc(sizeof(char) * 128);
    sprintf(buf, "%lld", val);
    return buf;
}

char* loadLzfStringObject() {
    unsigned int slen, clen;
    char *c, *s;

    if ((clen = loadLength(NULL)) == REDIS_RDB_LENERR) return NULL;
    if ((slen = loadLength(NULL)) == REDIS_RDB_LENERR) return NULL;

    c = malloc(clen);
    if (!readBytes(c, clen)) {
        free(c);
        return NULL;
    }

    s = malloc(slen+1);
    if (lzf_decompress(c,clen,s,slen) == 0) {
        free(c); free(s);
        return NULL;
    }

    free(c);
    return s;
}

/* returns NULL when not processable, char* when valid */
char* loadStringObject() {
    uint32_t offset = CURR_OFFSET;
    int isencoded;
    uint32_t len;

    len = loadLength(&isencoded);
    if (isencoded) {
        switch(len) {
        case REDIS_RDB_ENC_INT8:
        case REDIS_RDB_ENC_INT16:
        case REDIS_RDB_ENC_INT32:
            return loadIntegerObject(len);
        case REDIS_RDB_ENC_LZF:
            return loadLzfStringObject();
        default:
            /* unknown encoding */
            SHIFT_ERROR(offset, "Unknown string encoding (0x%02x)", len);
            return NULL;
        }
    }

    if (len == REDIS_RDB_LENERR) return NULL;

    char *buf = malloc(sizeof(char) * (len+1));
    buf[len] = '\0';
    if (!readBytes(buf, len)) {
        free(buf);
        return NULL;
    }
    return buf;
}

int processStringObject(char** store) {
    unsigned long offset = CURR_OFFSET;
    char *key = loadStringObject();
    if (key == NULL) {
        SHIFT_ERROR(offset, "Error reading string object");
        free(key);
        return 0;
    }

    if (store != NULL) {
        *store = key;
    } else {
        free(key);
    }
    return 1;
}

double* loadDoubleValue() {
    char buf[256];
    unsigned char len;
    double* val;

    if (!readBytes(&len,1)) return NULL;

    val = malloc(sizeof(double));
    switch(len) {
    case 255: *val = R_NegInf;  return val;
    case 254: *val = R_PosInf;  return val;
    case 253: *val = R_Nan;     return val;
    default:
        if (!readBytes(buf, len)) {
            free(val);
            return NULL;
        }
        buf[len] = '\0';
        sscanf(buf, "%lg", val);
        return val;
    }
}

int processDoubleValue(double** store) {
    unsigned long offset = CURR_OFFSET;
    double *val = loadDoubleValue();
    if (val == NULL) {
        SHIFT_ERROR(offset, "Error reading double value");
        free(val);
        return 0;
    }

    if (store != NULL) {
        *store = val;
    } else {
        free(val);
    }
    return 1;
}

int loadPair(entry *e) {
    uint32_t offset = CURR_OFFSET;
    uint32_t i;

    /* read key first */
    char *key;
    if (processStringObject(&key)) {
        e->key = key;
    } else {
        SHIFT_ERROR(offset, "Error reading entry key");
        return 0;
    }

    uint32_t length = 0;
    if (e->type == REDIS_LIST ||
        e->type == REDIS_SET  ||
        e->type == REDIS_ZSET ||
        e->type == REDIS_HASH) {
        if ((length = loadLength(NULL)) == REDIS_RDB_LENERR) {
            SHIFT_ERROR(offset, "Error reading %s length", types[e->type]);
            return 0;
        }
    }

    switch(e->type) {
    case REDIS_STRING:
    case REDIS_HASH_ZIPMAP:
    case REDIS_LIST_ZIPLIST:
    case REDIS_SET_INTSET:
    case REDIS_ZSET_ZIPLIST:
        if (!processStringObject(NULL)) {
            SHIFT_ERROR(offset, "Error reading entry value");
            return 0;
        }
    break;
    case REDIS_LIST:
    case REDIS_SET:
        for (i = 0; i < length; i++) {
            offset = CURR_OFFSET;
            if (!processStringObject(NULL)) {
                SHIFT_ERROR(offset, "Error reading element at index %d (length: %d)", i, length);
                return 0;
            }
        }
    break;
    case REDIS_ZSET:
        for (i = 0; i < length; i++) {
            offset = CURR_OFFSET;
            if (!processStringObject(NULL)) {
                SHIFT_ERROR(offset, "Error reading element key at index %d (length: %d)", i, length);
                return 0;
            }
            offset = CURR_OFFSET;
            if (!processDoubleValue(NULL)) {
                SHIFT_ERROR(offset, "Error reading element value at index %d (length: %d)", i, length);
                return 0;
            }
        }
    break;
    case REDIS_HASH:
        for (i = 0; i < length; i++) {
            offset = CURR_OFFSET;
            if (!processStringObject(NULL)) {
                SHIFT_ERROR(offset, "Error reading element key at index %d (length: %d)", i, length);
                return 0;
            }
            offset = CURR_OFFSET;
            if (!processStringObject(NULL)) {
                SHIFT_ERROR(offset, "Error reading element value at index %d (length: %d)", i, length);
                return 0;
            }
        }
    break;
    default:
        SHIFT_ERROR(offset, "Type not implemented");
        return 0;
    }
    /* because we're done, we assume success */
    e->success = 1;
    return 1;
}

entry loadEntry() {
    entry e = { NULL, -1, 0 };
    uint32_t length, offset[4];

    /* reset error container */
    errors.level = 0;

    offset[0] = CURR_OFFSET;
    if (!loadType(&e)) {
        return e;
    }

    offset[1] = CURR_OFFSET;
    if (e.type == REDIS_SELECTDB) {
        if ((length = loadLength(NULL)) == REDIS_RDB_LENERR) {
            SHIFT_ERROR(offset[1], "Error reading database number");
            return e;
        }
        if (length > 63) {
            SHIFT_ERROR(offset[1], "Database number out of range (%d)", length);
            return e;
        }
    } else if (e.type == REDIS_EOF) {
        if (positions[level].offset < positions[level].size) {
            SHIFT_ERROR(offset[0], "Unexpected EOF");
        } else {
            e.success = 1;
        }
        return e;
    } else {
        /* optionally consume expire */
        if (e.type == REDIS_EXPIRETIME) {
            if (!processTime()) return e;
            if (!loadType(&e)) return e;
        }

        offset[1] = CURR_OFFSET;
        if (!loadPair(&e)) {
            SHIFT_ERROR(offset[1], "Error for type %s", types[e.type]);
            return e;
        }
    }

    /* all entries are followed by a valid type:
     * e.g. a new entry, SELECTDB, EXPIRE, EOF */
    offset[2] = CURR_OFFSET;
    if (peekType() == -1) {
        SHIFT_ERROR(offset[2], "Followed by invalid type");
        SHIFT_ERROR(offset[0], "Error for type %s", types[e.type]);
        e.success = 0;
    } else {
        e.success = 1;
    }

    return e;
}

void printCentered(int indent, int width, char* body) {
    char head[256], tail[256];
    memset(head, '\0', 256);
    memset(tail, '\0', 256);

    memset(head, '=', indent);
    memset(tail, '=', width - 2 - indent - strlen(body));
    printf("%s %s %s\n", head, body, tail);
}

void printValid(uint64_t ops, uint64_t bytes) {
    char body[80];
    sprintf(body, "Processed %llu valid opcodes (in %llu bytes)",
        (unsigned long long) ops, (unsigned long long) bytes);
    printCentered(4, 80, body);
}

void printSkipped(uint64_t bytes, uint64_t offset) {
    char body[80];
    sprintf(body, "Skipped %llu bytes (resuming at 0x%08llx)",
        (unsigned long long) bytes, (unsigned long long) offset);
    printCentered(4, 80, body);
}

void printErrorStack(entry *e) {
    unsigned int i;
    char body[64];

    if (e->type == -1) {
        sprintf(body, "Error trace");
    } else if (e->type >= 253) {
        sprintf(body, "Error trace (%s)", types[e->type]);
    } else if (!e->key) {
        sprintf(body, "Error trace (%s: (unknown))", types[e->type]);
    } else {
        char tmp[41];
        strncpy(tmp, e->key, 40);

        /* display truncation at the last 3 chars */
        if (strlen(e->key) > 40) {
            memset(&tmp[37], '.', 3);
        }

        /* display unprintable characters as ? */
        for (i = 0; i < strlen(tmp); i++) {
            if (tmp[i] <= 32) tmp[i] = '?';
        }
        sprintf(body, "Error trace (%s: %s)", types[e->type], tmp);
    }

    printCentered(4, 80, body);

    /* display error stack */
    for (i = 0; i < errors.level; i++) {
        printf("0x%08lx - %s\n",
            (unsigned long) errors.offset[i], errors.error[i]);
    }
}

void process() {
    uint64_t num_errors = 0, num_valid_ops = 0, num_valid_bytes = 0;
    entry entry;
    processHeader();

    level = 1;
    while(positions[0].offset < positions[0].size) {
        positions[1] = positions[0];

        entry = loadEntry();
        if (!entry.success) {
            printValid(num_valid_ops, num_valid_bytes);
            printErrorStack(&entry);
            num_errors++;
            num_valid_ops = 0;
            num_valid_bytes = 0;

            /* search for next valid entry */
            uint64_t offset = positions[0].offset + 1;
            int i = 0;

            while (!entry.success && offset < positions[0].size) {
                positions[1].offset = offset;

                /* find 3 consecutive valid entries */
                for (i = 0; i < 3; i++) {
                    entry = loadEntry();
                    if (!entry.success) break;
                }
                /* check if we found 3 consecutive valid entries */
                if (i < 3) {
                    offset++;
                }
            }

            /* print how many bytes we have skipped to find a new valid opcode */
            if (offset < positions[0].size) {
                printSkipped(offset - positions[0].offset, offset);
            }

            positions[0].offset = offset;
        } else {
            num_valid_ops++;
            num_valid_bytes += positions[1].offset - positions[0].offset;

            /* advance position */
            positions[0] = positions[1];
        }
    }

    /* because there is another potential error,
     * print how many valid ops we have processed */
    printValid(num_valid_ops, num_valid_bytes);

    /* expect an eof */
    if (entry.type != REDIS_EOF) {
        /* last byte should be EOF, add error */
        errors.level = 0;
        SHIFT_ERROR(positions[0].offset, "Expected EOF, got %s", types[entry.type]);

        /* this is an EOF error so reset type */
        entry.type = -1;
        printErrorStack(&entry);

        num_errors++;
    }

    /* print summary on errors */
    if (num_errors) {
        printf("\n");
        printf("Total unprocessable opcodes: %llu\n",
            (unsigned long long) num_errors);
    }
}

int main(int argc, char **argv) {
    /* expect the first argument to be the dump file */
    if (argc <= 1) {
        printf("Usage: %s <dump.rdb>\n", argv[0]);
        exit(0);
    }

    int fd;
    off_t size;
    struct stat stat;
    void *data;

    fd = open(argv[1], O_RDONLY);
    if (fd < 1) {
        ERROR("Cannot open file: %s\n", argv[1]);
    }
    if (fstat(fd, &stat) == -1) {
        ERROR("Cannot stat: %s\n", argv[1]);
    } else {
        size = stat.st_size;
    }

    if (sizeof(size_t) == sizeof(int32_t) && size >= INT_MAX) {
        ERROR("Cannot check dump files >2GB on a 32-bit platform\n");
    }

    data = mmap(NULL, size, PROT_READ, MAP_SHARED, fd, 0);
    if (data == MAP_FAILED) {
        ERROR("Cannot mmap: %s\n", argv[1]);
    }

    /* Initialize static vars */
    positions[0].data = data;
    positions[0].size = size;
    positions[0].offset = 0;
    errors.level = 0;

    /* Object types */
    sprintf(types[REDIS_STRING], "STRING");
    sprintf(types[REDIS_LIST], "LIST");
    sprintf(types[REDIS_SET], "SET");
    sprintf(types[REDIS_ZSET], "ZSET");
    sprintf(types[REDIS_HASH], "HASH");

    /* Object types only used for dumping to disk */
    sprintf(types[REDIS_EXPIRETIME], "EXPIRETIME");
    sprintf(types[REDIS_SELECTDB], "SELECTDB");
    sprintf(types[REDIS_EOF], "EOF");

    /* Double constants initialization */
    R_Zero = 0.0;
    R_PosInf = 1.0/R_Zero;
    R_NegInf = -1.0/R_Zero;
    R_Nan = R_Zero/R_Zero;

    process();

    munmap(data, size);
    close(fd);
    return 0;
}
Commit	Line	Data
08af4d5c PN	1	#include <stdlib.h>
	2	#include <stdio.h>
	3	#include <unistd.h>
	4	#include <fcntl.h>
	5	#include <sys/stat.h>
	6	#include <sys/mman.h>
	7	#include <string.h>
	8	#include <arpa/inet.h>
	9	#include <stdint.h>
	10	#include <limits.h>
	11	#include "lzf.h"
	12
	13	/* Object types */
	14	#define REDIS_STRING 0
	15	#define REDIS_LIST 1
	16	#define REDIS_SET 2
	17	#define REDIS_ZSET 3
	18	#define REDIS_HASH 4
2e63cfe2	19	#define REDIS_HASH_ZIPMAP 9
	20	#define REDIS_LIST_ZIPLIST 10
	21	#define REDIS_SET_INTSET 11
	22	#define REDIS_ZSET_ZIPLIST 12
08af4d5c PN	23
	24	/* Objects encoding. Some kind of objects like Strings and Hashes can be
	25	* internally represented in multiple ways. The 'encoding' field of the object
	26	* is set to one of this fields for this object. */
	27	#define REDIS_ENCODING_RAW 0 /* Raw representation */
	28	#define REDIS_ENCODING_INT 1 /* Encoded as integer */
	29	#define REDIS_ENCODING_ZIPMAP 2 /* Encoded as zipmap */
	30	#define REDIS_ENCODING_HT 3 /* Encoded as an hash table */
	31
	32	/* Object types only used for dumping to disk */
	33	#define REDIS_EXPIRETIME 253
	34	#define REDIS_SELECTDB 254
	35	#define REDIS_EOF 255
	36
	37	/* Defines related to the dump file format. To store 32 bits lengths for short
	38	* keys requires a lot of space, so we check the most significant 2 bits of
	39	* the first byte to interpreter the length:
	40	*
	41	* 00\|000000 => if the two MSB are 00 the len is the 6 bits of this byte
	42	* 01\|000000 00000000 => 01, the len is 14 byes, 6 bits + 8 bits of next byte
	43	* 10\|000000 [32 bit integer] => if it's 01, a full 32 bit len will follow
	44	* 11\|000000 this means: specially encoded object will follow. The six bits
	45	* number specify the kind of object that follows.
	46	* See the REDIS_RDB_ENC_* defines.
	47	*
	48	* Lenghts up to 63 are stored using a single byte, most DB keys, and may
	49	* values, will fit inside. */
	50	#define REDIS_RDB_6BITLEN 0
	51	#define REDIS_RDB_14BITLEN 1
	52	#define REDIS_RDB_32BITLEN 2
	53	#define REDIS_RDB_ENCVAL 3
	54	#define REDIS_RDB_LENERR UINT_MAX
	55
	56	/* When a length of a string object stored on disk has the first two bits
	57	* set, the remaining two bits specify a special encoding for the object
	58	* accordingly to the following defines: */
	59	#define REDIS_RDB_ENC_INT8 0 /* 8 bit signed integer */
	60	#define REDIS_RDB_ENC_INT16 1 /* 16 bit signed integer */
	61	#define REDIS_RDB_ENC_INT32 2 /* 32 bit signed integer */
	62	#define REDIS_RDB_ENC_LZF 3 /* string compressed with FASTLZ */
	63
	64	#define ERROR(...) { \
	65	printf(__VA_ARGS__); \
	66	exit(1); \
	67	}
	68
	69	/* data type to hold offset in file and size */
	70	typedef struct {
	71	void *data;
f85202c3 PN	72	size_t size;
f85202c3 PN	73	size_t offset;
08af4d5c PN	74	} pos;
	75
	76	static unsigned char level = 0;
	77	static pos positions[16];
	78
	79	#define CURR_OFFSET (positions[level].offset)
	80
	81	/* Hold a stack of errors */
	82	typedef struct {
	83	char error[16][1024];
f85202c3 PN	84	size_t offset[16];
f85202c3 PN	85	size_t level;
08af4d5c PN	86	} errors_t;
	87	static errors_t errors;
	88
	89	#define SHIFT_ERROR(provided_offset, ...) { \
	90	sprintf(errors.error[errors.level], __VA_ARGS__); \
	91	errors.offset[errors.level] = provided_offset; \
	92	errors.level++; \
	93	}
	94
	95	/* Data type to hold opcode with optional key name an success status */
	96	typedef struct {
	97	char* key;
	98	int type;
	99	char success;
	100	} entry;
	101
	102	/* Global vars that are actally used as constants. The following double
	103	* values are used for double on-disk serialization, and are initialized
	104	* at runtime to avoid strange compiler optimizations. */
	105	static double R_Zero, R_PosInf, R_NegInf, R_Nan;
	106
	107	/* store string types for output */
	108	static char types[256][16];
	109
	110	/* when number of bytes to read is negative, do a peek */
	111	int readBytes(void *target, long num) {
	112	char peek = (num < 0) ? 1 : 0;
	113	num = (num < 0) ? -num : num;
	114
	115	pos p = positions[level];
	116	if (p.offset + num > p.size) {
	117	return 0;
	118	} else {
f85202c3	119	memcpy(target, (void*)((size_t)p.data + p.offset), num);
08af4d5c PN	120	if (!peek) positions[level].offset += num;
	121	}
	122	return 1;
	123	}
	124
	125	int processHeader() {
	126	char buf[10] = "_________";
	127	int dump_version;
	128
	129	if (!readBytes(buf, 9)) {
	130	ERROR("Cannot read header\n");
	131	}
	132
	133	/* expect the first 5 bytes to equal REDIS */
	134	if (memcmp(buf,"REDIS",5) != 0) {
	135	ERROR("Wrong signature in header\n");
	136	}
	137
	138	dump_version = (int)strtol(buf + 5, NULL, 10);
2e63cfe2	139	if (dump_version < 1 \|\| dump_version > 2) {
08af4d5c PN	140	ERROR("Unknown RDB format version: %d\n", dump_version);
	141	}
	142	return 1;
	143	}
	144
	145	int loadType(entry *e) {
	146	uint32_t offset = CURR_OFFSET;
	147
	148	/* this byte needs to qualify as type */
	149	unsigned char t;
	150	if (readBytes(&t, 1)) {
2e63cfe2	151	if (t <= 4 \|\| (t >=9 && t <= 12) \|\| t >= 253) {
08af4d5c PN	152	e->type = t;
	153	return 1;
	154	} else {
	155	SHIFT_ERROR(offset, "Unknown type (0x%02x)", t);
	156	}
	157	} else {
	158	SHIFT_ERROR(offset, "Could not read type");
	159	}
	160
	161	/* failure */
	162	return 0;
	163	}
	164
	165	int peekType() {
	166	unsigned char t;
2e63cfe2	167	if (readBytes(&t, -1) && (t <= 4 \|\| (t >=9 && t <= 12) \|\| t >= 253))
2e63cfe2	168	return t;
08af4d5c PN	169	return -1;
	170	}
	171
	172	/* discard time, just consume the bytes */
	173	int processTime() {
	174	uint32_t offset = CURR_OFFSET;
	175	unsigned char t[4];
	176	if (readBytes(t, 4)) {
	177	return 1;
	178	} else {
	179	SHIFT_ERROR(offset, "Could not read time");
	180	}
	181
	182	/* failure */
	183	return 0;
	184	}
	185
	186	uint32_t loadLength(int *isencoded) {
	187	unsigned char buf[2];
	188	uint32_t len;
	189	int type;
	190
	191	if (isencoded) *isencoded = 0;
	192	if (!readBytes(buf, 1)) return REDIS_RDB_LENERR;
	193	type = (buf[0] & 0xC0) >> 6;
	194	if (type == REDIS_RDB_6BITLEN) {
	195	/* Read a 6 bit len */
	196	return buf[0] & 0x3F;
	197	} else if (type == REDIS_RDB_ENCVAL) {
	198	/* Read a 6 bit len encoding type */
	199	if (isencoded) *isencoded = 1;
	200	return buf[0] & 0x3F;
	201	} else if (type == REDIS_RDB_14BITLEN) {
	202	/* Read a 14 bit len */
	203	if (!readBytes(buf+1,1)) return REDIS_RDB_LENERR;
	204	return ((buf[0] & 0x3F) << 8) \| buf[1];
	205	} else {
	206	/* Read a 32 bit len */
	207	if (!readBytes(&len, 4)) return REDIS_RDB_LENERR;
	208	return (unsigned int)ntohl(len);
	209	}
	210	}
	211
	212	char *loadIntegerObject(int enctype) {
	213	uint32_t offset = CURR_OFFSET;
	214	unsigned char enc[4];
	215	long long val;
	216
	217	if (enctype == REDIS_RDB_ENC_INT8) {
	218	uint8_t v;
	219	if (!readBytes(enc, 1)) return NULL;
	220	v = enc[0];
	221	val = (int8_t)v;
	222	} else if (enctype == REDIS_RDB_ENC_INT16) {
	223	uint16_t v;
	224	if (!readBytes(enc, 2)) return NULL;
	225	v = enc[0]\|(enc[1]<<8);
	226	val = (int16_t)v;
	227	} else if (enctype == REDIS_RDB_ENC_INT32) {
	228	uint32_t v;
	229	if (!readBytes(enc, 4)) return NULL;
	230	v = enc[0]\|(enc[1]<<8)\|(enc[2]<<16)\|(enc[3]<<24);
	231	val = (int32_t)v;
	232	} else {
233	SHIFT_ERROR(offset, "Unknown integer encoding (0x%02x)", enctype);
234	return NULL;
235	}
236
237	/* convert val into string */
238	char *buf;
239	buf = malloc(sizeof(char) * 128);
240	sprintf(buf, "%lld", val);
241	return buf;
242	}
243
244	char* loadLzfStringObject() {
245	unsigned int slen, clen;
246	char c, s;
247
248	if ((clen = loadLength(NULL)) == REDIS_RDB_LENERR) return NULL;
249	if ((slen = loadLength(NULL)) == REDIS_RDB_LENERR) return NULL;
250
251	c = malloc(clen);
252	if (!readBytes(c, clen)) {
253	free(c);
254	return NULL;
255	}
256
257	s = malloc(slen+1);
258	if (lzf_decompress(c,clen,s,slen) == 0) {
259	free(c); free(s);
260	return NULL;
261	}
262
263	free(c);
264	return s;
265	}
266
267	/* returns NULL when not processable, char* when valid */
268	char* loadStringObject() {
269	uint32_t offset = CURR_OFFSET;
270	int isencoded;
271	uint32_t len;
272
273	len = loadLength(&isencoded);
274	if (isencoded) {
275	switch(len) {
276	case REDIS_RDB_ENC_INT8:
277	case REDIS_RDB_ENC_INT16:
278	case REDIS_RDB_ENC_INT32:
279	return loadIntegerObject(len);
280	case REDIS_RDB_ENC_LZF:
281	return loadLzfStringObject();
282	default:
283	/* unknown encoding */
284	SHIFT_ERROR(offset, "Unknown string encoding (0x%02x)", len);
285	return NULL;
286	}
287	}
288
289	if (len == REDIS_RDB_LENERR) return NULL;
290
291	char buf = malloc(sizeof(char) (len+1));
292	buf[len] = '\0';
293	if (!readBytes(buf, len)) {
294	free(buf);
295	return NULL;
296	}
297	return buf;
298	}
299
300	int processStringObject(char** store) {
301	unsigned long offset = CURR_OFFSET;
302	char *key = loadStringObject();
303	if (key == NULL) {
304	SHIFT_ERROR(offset, "Error reading string object");
305	free(key);
306	return 0;
307	}
308
309	if (store != NULL) {
310	*store = key;
311	} else {
312	free(key);
313	}
314	return 1;
315	}
316
317	double* loadDoubleValue() {
318	char buf[256];
319	unsigned char len;
320	double* val;
321
322	if (!readBytes(&len,1)) return NULL;
323
324	val = malloc(sizeof(double));
325	switch(len) {
326	case 255: *val = R_NegInf; return val;
327	case 254: *val = R_PosInf; return val;
328	case 253: *val = R_Nan; return val;
329	default:
330	if (!readBytes(buf, len)) {
331	free(val);
332	return NULL;
333	}
334	buf[len] = '\0';
335	sscanf(buf, "%lg", val);
336	return val;
337	}
338	}
339
340	int processDoubleValue(double** store) {
341	unsigned long offset = CURR_OFFSET;
342	double *val = loadDoubleValue();
343	if (val == NULL) {
344	SHIFT_ERROR(offset, "Error reading double value");
345	free(val);
346	return 0;
347	}
348
349	if (store != NULL) {
350	*store = val;
351	} else {
352	free(val);
353	}
354	return 1;
355	}
356
357	int loadPair(entry *e) {
358	uint32_t offset = CURR_OFFSET;
359	uint32_t i;
360
361	/* read key first */
362	char *key;
363	if (processStringObject(&key)) {
364	e->key = key;
365	} else {
366	SHIFT_ERROR(offset, "Error reading entry key");
367	return 0;
368	}
369
370	uint32_t length = 0;
371	if (e->type == REDIS_LIST \|\|
372	e->type == REDIS_SET \|\|
373	e->type == REDIS_ZSET \|\|
374	e->type == REDIS_HASH) {
375	if ((length = loadLength(NULL)) == REDIS_RDB_LENERR) {
376	SHIFT_ERROR(offset, "Error reading %s length", types[e->type]);
377	return 0;
378	}
379	}
380
381	switch(e->type) {
382	case REDIS_STRING:
2e63cfe2	383	case REDIS_HASH_ZIPMAP:
	384	case REDIS_LIST_ZIPLIST:
	385	case REDIS_SET_INTSET:
	386	case REDIS_ZSET_ZIPLIST:
08af4d5c PN	387	if (!processStringObject(NULL)) {
	388	SHIFT_ERROR(offset, "Error reading entry value");
	389	return 0;
	390	}
	391	break;
	392	case REDIS_LIST:
	393	case REDIS_SET:
	394	for (i = 0; i < length; i++) {
	395	offset = CURR_OFFSET;
	396	if (!processStringObject(NULL)) {
	397	SHIFT_ERROR(offset, "Error reading element at index %d (length: %d)", i, length);
	398	return 0;
	399	}
	400	}
	401	break;
	402	case REDIS_ZSET:
	403	for (i = 0; i < length; i++) {
	404	offset = CURR_OFFSET;
	405	if (!processStringObject(NULL)) {
	406	SHIFT_ERROR(offset, "Error reading element key at index %d (length: %d)", i, length);
	407	return 0;
	408	}
	409	offset = CURR_OFFSET;
	410	if (!processDoubleValue(NULL)) {
	411	SHIFT_ERROR(offset, "Error reading element value at index %d (length: %d)", i, length);
	412	return 0;
	413	}
	414	}
	415	break;
	416	case REDIS_HASH:
	417	for (i = 0; i < length; i++) {
	418	offset = CURR_OFFSET;
	419	if (!processStringObject(NULL)) {
	420	SHIFT_ERROR(offset, "Error reading element key at index %d (length: %d)", i, length);
	421	return 0;
	422	}
	423	offset = CURR_OFFSET;
	424	if (!processStringObject(NULL)) {
	425	SHIFT_ERROR(offset, "Error reading element value at index %d (length: %d)", i, length);
	426	return 0;
	427	}
	428	}
	429	break;
	430	default:
	431	SHIFT_ERROR(offset, "Type not implemented");
	432	return 0;
	433	}
	434	/* because we're done, we assume success */
	435	e->success = 1;
	436	return 1;
	437	}
	438
	439	entry loadEntry() {
	440	entry e = { NULL, -1, 0 };
	441	uint32_t length, offset[4];
	442
	443	/* reset error container */
	444	errors.level = 0;
	445
	446	offset[0] = CURR_OFFSET;
	447	if (!loadType(&e)) {
	448	return e;
	449	}
	450
451	offset[1] = CURR_OFFSET;
452	if (e.type == REDIS_SELECTDB) {
453	if ((length = loadLength(NULL)) == REDIS_RDB_LENERR) {
454	SHIFT_ERROR(offset[1], "Error reading database number");
455	return e;
456	}
457	if (length > 63) {
458	SHIFT_ERROR(offset[1], "Database number out of range (%d)", length);
459	return e;
460	}
461	} else if (e.type == REDIS_EOF) {
462	if (positions[level].offset < positions[level].size) {
463	SHIFT_ERROR(offset[0], "Unexpected EOF");
464	} else {
465	e.success = 1;
466	}
467	return e;
468	} else {
469	/* optionally consume expire */
470	if (e.type == REDIS_EXPIRETIME) {
471	if (!processTime()) return e;
472	if (!loadType(&e)) return e;
473	}
474
475	offset[1] = CURR_OFFSET;
476	if (!loadPair(&e)) {
477	SHIFT_ERROR(offset[1], "Error for type %s", types[e.type]);
478	return e;
479	}
480	}
481
482	/* all entries are followed by a valid type:
483	* e.g. a new entry, SELECTDB, EXPIRE, EOF */
484	offset[2] = CURR_OFFSET;
485	if (peekType() == -1) {
486	SHIFT_ERROR(offset[2], "Followed by invalid type");
487	SHIFT_ERROR(offset[0], "Error for type %s", types[e.type]);
488	e.success = 0;
489	} else {
490	e.success = 1;
491	}
492
493	return e;
494	}
495
496	void printCentered(int indent, int width, char* body) {
497	char head[256], tail[256];
498	memset(head, '\0', 256);
499	memset(tail, '\0', 256);
500
501	memset(head, '=', indent);
502	memset(tail, '=', width - 2 - indent - strlen(body));
503	printf("%s %s %s\n", head, body, tail);
504	}
505
7b30cc3a	506	void printValid(uint64_t ops, uint64_t bytes) {
08af4d5c	507	char body[80];
a047bf52	508	sprintf(body, "Processed %llu valid opcodes (in %llu bytes)",
a047bf52	509	(unsigned long long) ops, (unsigned long long) bytes);
08af4d5c PN	510	printCentered(4, 80, body);
	511	}
	512
7b30cc3a	513	void printSkipped(uint64_t bytes, uint64_t offset) {
08af4d5c	514	char body[80];
a047bf52	515	sprintf(body, "Skipped %llu bytes (resuming at 0x%08llx)",
a047bf52	516	(unsigned long long) bytes, (unsigned long long) offset);
08af4d5c PN	517	printCentered(4, 80, body);
	518	}
	519
	520	void printErrorStack(entry *e) {
	521	unsigned int i;
	522	char body[64];
	523
	524	if (e->type == -1) {
	525	sprintf(body, "Error trace");
	526	} else if (e->type >= 253) {
	527	sprintf(body, "Error trace (%s)", types[e->type]);
	528	} else if (!e->key) {
	529	sprintf(body, "Error trace (%s: (unknown))", types[e->type]);
	530	} else {
	531	char tmp[41];
	532	strncpy(tmp, e->key, 40);
	533
	534	/* display truncation at the last 3 chars */
	535	if (strlen(e->key) > 40) {
	536	memset(&tmp[37], '.', 3);
	537	}
	538
	539	/* display unprintable characters as ? */
	540	for (i = 0; i < strlen(tmp); i++) {
	541	if (tmp[i] <= 32) tmp[i] = '?';
	542	}
	543	sprintf(body, "Error trace (%s: %s)", types[e->type], tmp);
	544	}
	545
	546	printCentered(4, 80, body);
	547
	548	/* display error stack */
	549	for (i = 0; i < errors.level; i++) {
10c12171	550	printf("0x%08lx - %s\n",
10c12171	551	(unsigned long) errors.offset[i], errors.error[i]);
08af4d5c PN	552	}
	553	}
	554
	555	void process() {
7b30cc3a	556	uint64_t num_errors = 0, num_valid_ops = 0, num_valid_bytes = 0;
08af4d5c PN	557	entry entry;
	558	processHeader();
	559
	560	level = 1;
	561	while(positions[0].offset < positions[0].size) {
	562	positions[1] = positions[0];
	563
	564	entry = loadEntry();
	565	if (!entry.success) {
	566	printValid(num_valid_ops, num_valid_bytes);
	567	printErrorStack(&entry);
	568	num_errors++;
	569	num_valid_ops = 0;
	570	num_valid_bytes = 0;
	571
	572	/* search for next valid entry */
7b30cc3a PN	573	uint64_t offset = positions[0].offset + 1;
	574	int i = 0;
	575
08af4d5c PN	576	while (!entry.success && offset < positions[0].size) {
	577	positions[1].offset = offset;
	578
	579	/* find 3 consecutive valid entries */
	580	for (i = 0; i < 3; i++) {
	581	entry = loadEntry();
	582	if (!entry.success) break;
	583	}
	584	/* check if we found 3 consecutive valid entries */
	585	if (i < 3) {
	586	offset++;
	587	}
	588	}
	589
	590	/* print how many bytes we have skipped to find a new valid opcode */
	591	if (offset < positions[0].size) {
	592	printSkipped(offset - positions[0].offset, offset);
	593	}
	594
	595	positions[0].offset = offset;
	596	} else {
	597	num_valid_ops++;
	598	num_valid_bytes += positions[1].offset - positions[0].offset;
	599
	600	/* advance position */
	601	positions[0] = positions[1];
	602	}
	603	}
	604
	605	/* because there is another potential error,
	606	* print how many valid ops we have processed */
	607	printValid(num_valid_ops, num_valid_bytes);
	608
	609	/* expect an eof */
	610	if (entry.type != REDIS_EOF) {
	611	/* last byte should be EOF, add error */
	612	errors.level = 0;
	613	SHIFT_ERROR(positions[0].offset, "Expected EOF, got %s", types[entry.type]);
	614
	615	/* this is an EOF error so reset type */
	616	entry.type = -1;
	617	printErrorStack(&entry);
	618
	619	num_errors++;
	620	}
	621
	622	/* print summary on errors */
7b30cc3a	623	if (num_errors) {
08af4d5c	624	printf("\n");
a047bf52	625	printf("Total unprocessable opcodes: %llu\n",
a047bf52	626	(unsigned long long) num_errors);
08af4d5c PN	627	}
	628	}
	629
	630	int main(int argc, char **argv) {
	631	/* expect the first argument to be the dump file */
	632	if (argc <= 1) {
	633	printf("Usage: %s <dump.rdb>\n", argv[0]);
	634	exit(0);
	635	}
	636
	637	int fd;
f85202c3	638	off_t size;
08af4d5c PN	639	struct stat stat;
	640	void *data;
	641
	642	fd = open(argv[1], O_RDONLY);
	643	if (fd < 1) {
	644	ERROR("Cannot open file: %s\n", argv[1]);
	645	}
	646	if (fstat(fd, &stat) == -1) {
	647	ERROR("Cannot stat: %s\n", argv[1]);
	648	} else {
	649	size = stat.st_size;
	650	}
	651
f85202c3 PN	652	if (sizeof(size_t) == sizeof(int32_t) && size >= INT_MAX) {
	653	ERROR("Cannot check dump files >2GB on a 32-bit platform\n");
	654	}
	655
08af4d5c PN	656	data = mmap(NULL, size, PROT_READ, MAP_SHARED, fd, 0);
	657	if (data == MAP_FAILED) {
	658	ERROR("Cannot mmap: %s\n", argv[1]);
	659	}
	660
	661	/* Initialize static vars */
	662	positions[0].data = data;
	663	positions[0].size = size;
	664	positions[0].offset = 0;
	665	errors.level = 0;
	666
	667	/* Object types */
	668	sprintf(types[REDIS_STRING], "STRING");
	669	sprintf(types[REDIS_LIST], "LIST");
	670	sprintf(types[REDIS_SET], "SET");
	671	sprintf(types[REDIS_ZSET], "ZSET");
	672	sprintf(types[REDIS_HASH], "HASH");
	673
	674	/* Object types only used for dumping to disk */
	675	sprintf(types[REDIS_EXPIRETIME], "EXPIRETIME");
	676	sprintf(types[REDIS_SELECTDB], "SELECTDB");
	677	sprintf(types[REDIS_EOF], "EOF");
	678
	679	/* Double constants initialization */
	680	R_Zero = 0.0;
	681	R_PosInf = 1.0/R_Zero;
	682	R_NegInf = -1.0/R_Zero;
	683	R_Nan = R_Zero/R_Zero;
	684
	685	process();
	686
	687	munmap(data, size);
	688	close(fd);
	689	return 0;
	690	}