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