src/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 #define REDIS_HASH_ZIPMAP 9
  20 #define REDIS_LIST_ZIPLIST 10
  21 #define REDIS_SET_INTSET 11
  22 #define REDIS_ZSET_ZIPLIST 12
  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;
  72     size_t size;
  73     size_t offset;
  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];
  84     size_t offset[16];
  85     size_t level;
  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 {
 119         memcpy(target, (void*)((size_t)p.data + p.offset), num);
 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);
 139     if (dump_version < 1 || dump_version > 2) {
 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)) {
 151         if (t <= 4 || (t >=9 && t <= 12) || t >= 253) {
 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;
 167     if (readBytes(&t, -1) && (t <= 4 || (t >=9 && t <= 12) || t >= 253))
 168         return t;
 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:
 383     case REDIS_HASH_ZIPMAP:
 384     case REDIS_LIST_ZIPLIST:
 385     case REDIS_SET_INTSET:
 386     case REDIS_ZSET_ZIPLIST:
 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
 506 void printValid(uint64_t ops, uint64_t bytes) {
 507     char body[80];
 508     sprintf(body, "Processed %llu valid opcodes (in %llu bytes)",
 509         (unsigned long long) ops, (unsigned long long) bytes);
 510     printCentered(4, 80, body);
 511 }
 512
 513 void printSkipped(uint64_t bytes, uint64_t offset) {
 514     char body[80];
 515     sprintf(body, "Skipped %llu bytes (resuming at 0x%08llx)",
 516         (unsigned long long) bytes, (unsigned long long) offset);
 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++) {
 550         printf("0x%08lx - %s\n",
 551             (unsigned long) errors.offset[i], errors.error[i]);
 552     }
 553 }
 554
 555 void process() {
 556     uint64_t num_errors = 0, num_valid_ops = 0, num_valid_bytes = 0;
 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 */
 573             uint64_t offset = positions[0].offset + 1;
 574             int i = 0;
 575
 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 */
 623     if (num_errors) {
 624         printf("\n");
 625         printf("Total unprocessable opcodes: %llu\n",
 626             (unsigned long long) num_errors);
 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;
 638     off_t size;
 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
 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
 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 }