]> git.saurik.com Git - redis.git/blame_incremental - src/redis-check-dump.c
Code style hack.
[redis.git] / src / redis-check-dump.c
... / ...
CommitLineData
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 */
71typedef struct {
72 void *data;
73 size_t size;
74 size_t offset;
75} pos;
76
77static unsigned char level = 0;
78static pos positions[16];
79
80#define CURR_OFFSET (positions[level].offset)
81
82/* Hold a stack of errors */
83typedef struct {
84 char error[16][1024];
85 size_t offset[16];
86 size_t level;
87} errors_t;
88static 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 */
97typedef 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. */
106static double R_Zero, R_PosInf, R_NegInf, R_Nan;
107
108/* store string types for output */
109static char types[256][16];
110
111/* when number of bytes to read is negative, do a peek */
112int 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
126int 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
146int 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
166int 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 */
174int 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
187uint32_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
213char *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
245char* 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 */
269char* 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
301int 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
318double* 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
341int 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
358int 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
441entry 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
498void 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
508void 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
515void 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
522void 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
557void 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
633int 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}