redis-check-dump.c

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