]> git.saurik.com Git - redis.git/blob - src/redis-check-dump.c
Compare integers in ziplist regardless of encoding
[redis.git] / 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 /* Prototypes */
112 uint64_t crc64(uint64_t crc, const unsigned char *s, uint64_t l);
113
114 /* when number of bytes to read is negative, do a peek */
115 int readBytes(void *target, long num) {
116 char peek = (num < 0) ? 1 : 0;
117 num = (num < 0) ? -num : num;
118
119 pos p = positions[level];
120 if (p.offset + num > p.size) {
121 return 0;
122 } else {
123 memcpy(target, (void*)((size_t)p.data + p.offset), num);
124 if (!peek) positions[level].offset += num;
125 }
126 return 1;
127 }
128
129 int processHeader() {
130 char buf[10] = "_________";
131 int dump_version;
132
133 if (!readBytes(buf, 9)) {
134 ERROR("Cannot read header\n");
135 }
136
137 /* expect the first 5 bytes to equal REDIS */
138 if (memcmp(buf,"REDIS",5) != 0) {
139 ERROR("Wrong signature in header\n");
140 }
141
142 dump_version = (int)strtol(buf + 5, NULL, 10);
143 if (dump_version < 1 || dump_version > 6) {
144 ERROR("Unknown RDB format version: %d\n", dump_version);
145 }
146 return dump_version;
147 }
148
149 int loadType(entry *e) {
150 uint32_t offset = CURR_OFFSET;
151
152 /* this byte needs to qualify as type */
153 unsigned char t;
154 if (readBytes(&t, 1)) {
155 if (t <= 4 || (t >=9 && t <= 12) || t >= 253) {
156 e->type = t;
157 return 1;
158 } else {
159 SHIFT_ERROR(offset, "Unknown type (0x%02x)", t);
160 }
161 } else {
162 SHIFT_ERROR(offset, "Could not read type");
163 }
164
165 /* failure */
166 return 0;
167 }
168
169 int peekType() {
170 unsigned char t;
171 if (readBytes(&t, -1) && (t <= 4 || (t >=9 && t <= 12) || t >= 253))
172 return t;
173 return -1;
174 }
175
176 /* discard time, just consume the bytes */
177 int processTime() {
178 uint32_t offset = CURR_OFFSET;
179 unsigned char t[4];
180 if (readBytes(t, 4)) {
181 return 1;
182 } else {
183 SHIFT_ERROR(offset, "Could not read time");
184 }
185
186 /* failure */
187 return 0;
188 }
189
190 uint32_t loadLength(int *isencoded) {
191 unsigned char buf[2];
192 uint32_t len;
193 int type;
194
195 if (isencoded) *isencoded = 0;
196 if (!readBytes(buf, 1)) return REDIS_RDB_LENERR;
197 type = (buf[0] & 0xC0) >> 6;
198 if (type == REDIS_RDB_6BITLEN) {
199 /* Read a 6 bit len */
200 return buf[0] & 0x3F;
201 } else if (type == REDIS_RDB_ENCVAL) {
202 /* Read a 6 bit len encoding type */
203 if (isencoded) *isencoded = 1;
204 return buf[0] & 0x3F;
205 } else if (type == REDIS_RDB_14BITLEN) {
206 /* Read a 14 bit len */
207 if (!readBytes(buf+1,1)) return REDIS_RDB_LENERR;
208 return ((buf[0] & 0x3F) << 8) | buf[1];
209 } else {
210 /* Read a 32 bit len */
211 if (!readBytes(&len, 4)) return REDIS_RDB_LENERR;
212 return (unsigned int)ntohl(len);
213 }
214 }
215
216 char *loadIntegerObject(int enctype) {
217 uint32_t offset = CURR_OFFSET;
218 unsigned char enc[4];
219 long long val;
220
221 if (enctype == REDIS_RDB_ENC_INT8) {
222 uint8_t v;
223 if (!readBytes(enc, 1)) return NULL;
224 v = enc[0];
225 val = (int8_t)v;
226 } else if (enctype == REDIS_RDB_ENC_INT16) {
227 uint16_t v;
228 if (!readBytes(enc, 2)) return NULL;
229 v = enc[0]|(enc[1]<<8);
230 val = (int16_t)v;
231 } else if (enctype == REDIS_RDB_ENC_INT32) {
232 uint32_t v;
233 if (!readBytes(enc, 4)) return NULL;
234 v = enc[0]|(enc[1]<<8)|(enc[2]<<16)|(enc[3]<<24);
235 val = (int32_t)v;
236 } else {
237 SHIFT_ERROR(offset, "Unknown integer encoding (0x%02x)", enctype);
238 return NULL;
239 }
240
241 /* convert val into string */
242 char *buf;
243 buf = malloc(sizeof(char) * 128);
244 sprintf(buf, "%lld", val);
245 return buf;
246 }
247
248 char* loadLzfStringObject() {
249 unsigned int slen, clen;
250 char *c, *s;
251
252 if ((clen = loadLength(NULL)) == REDIS_RDB_LENERR) return NULL;
253 if ((slen = loadLength(NULL)) == REDIS_RDB_LENERR) return NULL;
254
255 c = malloc(clen);
256 if (!readBytes(c, clen)) {
257 free(c);
258 return NULL;
259 }
260
261 s = malloc(slen+1);
262 if (lzf_decompress(c,clen,s,slen) == 0) {
263 free(c); free(s);
264 return NULL;
265 }
266
267 free(c);
268 return s;
269 }
270
271 /* returns NULL when not processable, char* when valid */
272 char* loadStringObject() {
273 uint32_t offset = CURR_OFFSET;
274 int isencoded;
275 uint32_t len;
276
277 len = loadLength(&isencoded);
278 if (isencoded) {
279 switch(len) {
280 case REDIS_RDB_ENC_INT8:
281 case REDIS_RDB_ENC_INT16:
282 case REDIS_RDB_ENC_INT32:
283 return loadIntegerObject(len);
284 case REDIS_RDB_ENC_LZF:
285 return loadLzfStringObject();
286 default:
287 /* unknown encoding */
288 SHIFT_ERROR(offset, "Unknown string encoding (0x%02x)", len);
289 return NULL;
290 }
291 }
292
293 if (len == REDIS_RDB_LENERR) return NULL;
294
295 char *buf = malloc(sizeof(char) * (len+1));
296 buf[len] = '\0';
297 if (!readBytes(buf, len)) {
298 free(buf);
299 return NULL;
300 }
301 return buf;
302 }
303
304 int processStringObject(char** store) {
305 unsigned long offset = CURR_OFFSET;
306 char *key = loadStringObject();
307 if (key == NULL) {
308 SHIFT_ERROR(offset, "Error reading string object");
309 free(key);
310 return 0;
311 }
312
313 if (store != NULL) {
314 *store = key;
315 } else {
316 free(key);
317 }
318 return 1;
319 }
320
321 double* loadDoubleValue() {
322 char buf[256];
323 unsigned char len;
324 double* val;
325
326 if (!readBytes(&len,1)) return NULL;
327
328 val = malloc(sizeof(double));
329 switch(len) {
330 case 255: *val = R_NegInf; return val;
331 case 254: *val = R_PosInf; return val;
332 case 253: *val = R_Nan; return val;
333 default:
334 if (!readBytes(buf, len)) {
335 free(val);
336 return NULL;
337 }
338 buf[len] = '\0';
339 sscanf(buf, "%lg", val);
340 return val;
341 }
342 }
343
344 int processDoubleValue(double** store) {
345 unsigned long offset = CURR_OFFSET;
346 double *val = loadDoubleValue();
347 if (val == NULL) {
348 SHIFT_ERROR(offset, "Error reading double value");
349 free(val);
350 return 0;
351 }
352
353 if (store != NULL) {
354 *store = val;
355 } else {
356 free(val);
357 }
358 return 1;
359 }
360
361 int loadPair(entry *e) {
362 uint32_t offset = CURR_OFFSET;
363 uint32_t i;
364
365 /* read key first */
366 char *key;
367 if (processStringObject(&key)) {
368 e->key = key;
369 } else {
370 SHIFT_ERROR(offset, "Error reading entry key");
371 return 0;
372 }
373
374 uint32_t length = 0;
375 if (e->type == REDIS_LIST ||
376 e->type == REDIS_SET ||
377 e->type == REDIS_ZSET ||
378 e->type == REDIS_HASH) {
379 if ((length = loadLength(NULL)) == REDIS_RDB_LENERR) {
380 SHIFT_ERROR(offset, "Error reading %s length", types[e->type]);
381 return 0;
382 }
383 }
384
385 switch(e->type) {
386 case REDIS_STRING:
387 case REDIS_HASH_ZIPMAP:
388 case REDIS_LIST_ZIPLIST:
389 case REDIS_SET_INTSET:
390 case REDIS_ZSET_ZIPLIST:
391 case REDIS_HASH_ZIPLIST:
392 if (!processStringObject(NULL)) {
393 SHIFT_ERROR(offset, "Error reading entry value");
394 return 0;
395 }
396 break;
397 case REDIS_LIST:
398 case REDIS_SET:
399 for (i = 0; i < length; i++) {
400 offset = CURR_OFFSET;
401 if (!processStringObject(NULL)) {
402 SHIFT_ERROR(offset, "Error reading element at index %d (length: %d)", i, length);
403 return 0;
404 }
405 }
406 break;
407 case REDIS_ZSET:
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 (!processDoubleValue(NULL)) {
416 SHIFT_ERROR(offset, "Error reading element value at index %d (length: %d)", i, length);
417 return 0;
418 }
419 }
420 break;
421 case REDIS_HASH:
422 for (i = 0; i < length; i++) {
423 offset = CURR_OFFSET;
424 if (!processStringObject(NULL)) {
425 SHIFT_ERROR(offset, "Error reading element key at index %d (length: %d)", i, length);
426 return 0;
427 }
428 offset = CURR_OFFSET;
429 if (!processStringObject(NULL)) {
430 SHIFT_ERROR(offset, "Error reading element value at index %d (length: %d)", i, length);
431 return 0;
432 }
433 }
434 break;
435 default:
436 SHIFT_ERROR(offset, "Type not implemented");
437 return 0;
438 }
439 /* because we're done, we assume success */
440 e->success = 1;
441 return 1;
442 }
443
444 entry loadEntry() {
445 entry e = { NULL, -1, 0 };
446 uint32_t length, offset[4];
447
448 /* reset error container */
449 errors.level = 0;
450
451 offset[0] = CURR_OFFSET;
452 if (!loadType(&e)) {
453 return e;
454 }
455
456 offset[1] = CURR_OFFSET;
457 if (e.type == REDIS_SELECTDB) {
458 if ((length = loadLength(NULL)) == REDIS_RDB_LENERR) {
459 SHIFT_ERROR(offset[1], "Error reading database number");
460 return e;
461 }
462 if (length > 63) {
463 SHIFT_ERROR(offset[1], "Database number out of range (%d)", length);
464 return e;
465 }
466 } else if (e.type == REDIS_EOF) {
467 if (positions[level].offset < positions[level].size) {
468 SHIFT_ERROR(offset[0], "Unexpected EOF");
469 } else {
470 e.success = 1;
471 }
472 return e;
473 } else {
474 /* optionally consume expire */
475 if (e.type == REDIS_EXPIRETIME) {
476 if (!processTime()) return e;
477 if (!loadType(&e)) return e;
478 }
479
480 offset[1] = CURR_OFFSET;
481 if (!loadPair(&e)) {
482 SHIFT_ERROR(offset[1], "Error for type %s", types[e.type]);
483 return e;
484 }
485 }
486
487 /* all entries are followed by a valid type:
488 * e.g. a new entry, SELECTDB, EXPIRE, EOF */
489 offset[2] = CURR_OFFSET;
490 if (peekType() == -1) {
491 SHIFT_ERROR(offset[2], "Followed by invalid type");
492 SHIFT_ERROR(offset[0], "Error for type %s", types[e.type]);
493 e.success = 0;
494 } else {
495 e.success = 1;
496 }
497
498 return e;
499 }
500
501 void printCentered(int indent, int width, char* body) {
502 char head[256], tail[256];
503 memset(head, '\0', 256);
504 memset(tail, '\0', 256);
505
506 memset(head, '=', indent);
507 memset(tail, '=', width - 2 - indent - strlen(body));
508 printf("%s %s %s\n", head, body, tail);
509 }
510
511 void printValid(uint64_t ops, uint64_t bytes) {
512 char body[80];
513 sprintf(body, "Processed %llu valid opcodes (in %llu bytes)",
514 (unsigned long long) ops, (unsigned long long) bytes);
515 printCentered(4, 80, body);
516 }
517
518 void printSkipped(uint64_t bytes, uint64_t offset) {
519 char body[80];
520 sprintf(body, "Skipped %llu bytes (resuming at 0x%08llx)",
521 (unsigned long long) bytes, (unsigned long long) offset);
522 printCentered(4, 80, body);
523 }
524
525 void printErrorStack(entry *e) {
526 unsigned int i;
527 char body[64];
528
529 if (e->type == -1) {
530 sprintf(body, "Error trace");
531 } else if (e->type >= 253) {
532 sprintf(body, "Error trace (%s)", types[e->type]);
533 } else if (!e->key) {
534 sprintf(body, "Error trace (%s: (unknown))", types[e->type]);
535 } else {
536 char tmp[41];
537 strncpy(tmp, e->key, 40);
538
539 /* display truncation at the last 3 chars */
540 if (strlen(e->key) > 40) {
541 memset(&tmp[37], '.', 3);
542 }
543
544 /* display unprintable characters as ? */
545 for (i = 0; i < strlen(tmp); i++) {
546 if (tmp[i] <= 32) tmp[i] = '?';
547 }
548 sprintf(body, "Error trace (%s: %s)", types[e->type], tmp);
549 }
550
551 printCentered(4, 80, body);
552
553 /* display error stack */
554 for (i = 0; i < errors.level; i++) {
555 printf("0x%08lx - %s\n",
556 (unsigned long) errors.offset[i], errors.error[i]);
557 }
558 }
559
560 void process() {
561 uint64_t num_errors = 0, num_valid_ops = 0, num_valid_bytes = 0;
562 entry entry;
563 int dump_version = processHeader();
564
565 /* Exclude the final checksum for RDB >= 5. Will be checked at the end. */
566 if (dump_version >= 5) {
567 if (positions[0].size < 8) {
568 printf("RDB version >= 5 but no room for checksum.\n");
569 exit(1);
570 }
571 positions[0].size -= 8;;
572 }
573
574 level = 1;
575 while(positions[0].offset < positions[0].size) {
576 positions[1] = positions[0];
577
578 entry = loadEntry();
579 if (!entry.success) {
580 printValid(num_valid_ops, num_valid_bytes);
581 printErrorStack(&entry);
582 num_errors++;
583 num_valid_ops = 0;
584 num_valid_bytes = 0;
585
586 /* search for next valid entry */
587 uint64_t offset = positions[0].offset + 1;
588 int i = 0;
589
590 while (!entry.success && offset < positions[0].size) {
591 positions[1].offset = offset;
592
593 /* find 3 consecutive valid entries */
594 for (i = 0; i < 3; i++) {
595 entry = loadEntry();
596 if (!entry.success) break;
597 }
598 /* check if we found 3 consecutive valid entries */
599 if (i < 3) {
600 offset++;
601 }
602 }
603
604 /* print how many bytes we have skipped to find a new valid opcode */
605 if (offset < positions[0].size) {
606 printSkipped(offset - positions[0].offset, offset);
607 }
608
609 positions[0].offset = offset;
610 } else {
611 num_valid_ops++;
612 num_valid_bytes += positions[1].offset - positions[0].offset;
613
614 /* advance position */
615 positions[0] = positions[1];
616 }
617 free(entry.key);
618 }
619
620 /* because there is another potential error,
621 * print how many valid ops we have processed */
622 printValid(num_valid_ops, num_valid_bytes);
623
624 /* expect an eof */
625 if (entry.type != REDIS_EOF) {
626 /* last byte should be EOF, add error */
627 errors.level = 0;
628 SHIFT_ERROR(positions[0].offset, "Expected EOF, got %s", types[entry.type]);
629
630 /* this is an EOF error so reset type */
631 entry.type = -1;
632 printErrorStack(&entry);
633
634 num_errors++;
635 }
636
637 /* Verify checksum */
638 if (dump_version >= 5) {
639 uint64_t crc = crc64(0,positions[0].data,positions[0].size);
640 uint64_t crc2;
641 unsigned char *p = (unsigned char*)positions[0].data+positions[0].size;
642 crc2 = ((uint64_t)p[0] << 0) |
643 ((uint64_t)p[1] << 8) |
644 ((uint64_t)p[2] << 16) |
645 ((uint64_t)p[3] << 24) |
646 ((uint64_t)p[4] << 32) |
647 ((uint64_t)p[5] << 40) |
648 ((uint64_t)p[6] << 48) |
649 ((uint64_t)p[7] << 56);
650 if (crc != crc2) {
651 SHIFT_ERROR(positions[0].offset, "RDB CRC64 does not match.");
652 } else {
653 printf("CRC64 checksum is OK\n");
654 }
655 }
656
657 /* print summary on errors */
658 if (num_errors) {
659 printf("\n");
660 printf("Total unprocessable opcodes: %llu\n",
661 (unsigned long long) num_errors);
662 }
663 }
664
665 int main(int argc, char **argv) {
666 /* expect the first argument to be the dump file */
667 if (argc <= 1) {
668 printf("Usage: %s <dump.rdb>\n", argv[0]);
669 exit(0);
670 }
671
672 int fd;
673 off_t size;
674 struct stat stat;
675 void *data;
676
677 fd = open(argv[1], O_RDONLY);
678 if (fd < 1) {
679 ERROR("Cannot open file: %s\n", argv[1]);
680 }
681 if (fstat(fd, &stat) == -1) {
682 ERROR("Cannot stat: %s\n", argv[1]);
683 } else {
684 size = stat.st_size;
685 }
686
687 if (sizeof(size_t) == sizeof(int32_t) && size >= INT_MAX) {
688 ERROR("Cannot check dump files >2GB on a 32-bit platform\n");
689 }
690
691 data = mmap(NULL, size, PROT_READ, MAP_SHARED, fd, 0);
692 if (data == MAP_FAILED) {
693 ERROR("Cannot mmap: %s\n", argv[1]);
694 }
695
696 /* Initialize static vars */
697 positions[0].data = data;
698 positions[0].size = size;
699 positions[0].offset = 0;
700 errors.level = 0;
701
702 /* Object types */
703 sprintf(types[REDIS_STRING], "STRING");
704 sprintf(types[REDIS_LIST], "LIST");
705 sprintf(types[REDIS_SET], "SET");
706 sprintf(types[REDIS_ZSET], "ZSET");
707 sprintf(types[REDIS_HASH], "HASH");
708
709 /* Object types only used for dumping to disk */
710 sprintf(types[REDIS_EXPIRETIME], "EXPIRETIME");
711 sprintf(types[REDIS_SELECTDB], "SELECTDB");
712 sprintf(types[REDIS_EOF], "EOF");
713
714 /* Double constants initialization */
715 R_Zero = 0.0;
716 R_PosInf = 1.0/R_Zero;
717 R_NegInf = -1.0/R_Zero;
718 R_Nan = R_Zero/R_Zero;
719
720 process();
721
722 munmap(data, size);
723 close(fd);
724 return 0;
725 }