1 #include <ccan/tdb/tdb.h>
2 #include <ccan/grab_file/grab_file.h>
3 #include <ccan/hash/hash.h>
4 #include <ccan/talloc/talloc.h>
5 #include <ccan/str_talloc/str_talloc.h>
6 #include <ccan/str/str.h>
11 #define STRINGIFY2(x) #x
12 #define STRINGIFY(x) STRINGIFY2(x)
15 #define try(expr, op) \
19 if (tdb_error(tdb) != -op.ret) \
20 errx(1, "Line %u: " STRINGIFY(expr) \
22 i+1, ret, tdb_errorstr(tdb)); \
23 } else if (ret != op.ret) \
24 errx(1, "Line %u: " STRINGIFY(expr) "= %i: %s", \
25 i+1, ret, tdb_errorstr(tdb)); \
28 /* Try or imitate results. */
29 #define unreliable(expr, expect, force, undo) \
32 if (ret != expect) { \
33 warnx("Line %u: %s gave %i not %i", \
34 i+1, STRINGIFY(expr), ret, expect); \
42 static bool key_eq(TDB_DATA a, TDB_DATA b)
44 if (a.dsize != b.dsize)
46 return memcmp(a.dptr, b.dptr, a.dsize) == 0;
52 OP_TDB_LOCKALL_UNMARK,
53 OP_TDB_LOCKALL_NONBLOCK,
56 OP_TDB_LOCKALL_READ_NONBLOCK,
57 OP_TDB_UNLOCKALL_READ,
59 OP_TDB_CHAINLOCK_NONBLOCK,
60 OP_TDB_CHAINLOCK_MARK,
61 OP_TDB_CHAINLOCK_UNMARK,
63 OP_TDB_CHAINLOCK_READ,
64 OP_TDB_CHAINUNLOCK_READ,
65 OP_TDB_INCREMENT_SEQNUM_NONBLOCK,
72 OP_TDB_TRANSACTION_START,
73 OP_TDB_TRANSACTION_CANCEL,
74 OP_TDB_TRANSACTION_COMMIT,
75 OP_TDB_TRAVERSE_READ_START,
76 OP_TDB_TRAVERSE_START,
92 int flag; /* open and store */
93 struct traverse *trav; /* traverse start */
97 static unsigned char hex_char(unsigned int line, char c)
100 if (c >= 'A' && c <= 'F')
102 if (c >= '0' && c <= '9')
104 errx(1, "Line %u: invalid hex character '%c'", line, c);
107 /* TDB data is <size>:<%02x>* */
108 static TDB_DATA make_tdb_data(const void *ctx,
109 unsigned int line, const char *word)
115 data.dsize = atoi(word);
116 data.dptr = talloc_array(ctx, unsigned char, data.dsize);
117 p = strchr(word, ':');
119 errx(1, "Line %u: Invalid tdb data '%s'", line, word);
121 for (i = 0; i < data.dsize; i++)
122 data.dptr[i] = hex_char(line, p[i*2])*16
123 + hex_char(line, p[i*2+1]);
127 static struct op *add_op(struct op **op, unsigned int i,
128 enum op_type type, const char *key, const char *data,
132 *op = talloc_realloc(NULL, *op, struct op, i+1);
137 new->key = make_tdb_data(*op, i+1, key);
141 new->data = make_tdb_data(*op, i+1, data);
143 new->data = tdb_null;
147 static int get_len(TDB_DATA key, TDB_DATA data, void *private_data)
152 struct traverse_hash {
157 /* A traverse is a hash of keys, each one associated with ops. */
159 /* How many traversal callouts should I do? */
162 /* Where is traversal end op? */
165 /* For trivial traversals. */
166 struct traverse_hash *hash;
169 /* This is based on the hash algorithm from gdbm */
170 static unsigned int hash_key(TDB_DATA *key)
172 uint32_t value; /* Used to compute the hash value. */
173 uint32_t i; /* Used to cycle through random values. */
175 /* Set the initial value from the key size. */
176 for (value = 0x238F13AF ^ key->dsize, i=0; i < key->dsize; i++)
177 value = (value + (key->dptr[i] << (i*5 % 24)));
179 return (1103515243 * value + 12345);
182 /* A trivial traversal is one which doesn't terminate early and only
183 * plays with its own record. We can reliably replay these even if
184 * traverse order changes. */
185 static bool is_trivial_traverse(struct op op[], unsigned int end)
188 TDB_DATA cur = tdb_null;
190 if (op[end].ret != 0)
193 for (i = 0; i < end; i++) {
196 if (op[i].op == OP_TDB_TRAVERSE)
198 if (!key_eq(cur, op[i].key))
204 static void analyze_traverse(struct op op[], unsigned int end)
207 struct traverse *trav = talloc(op, struct traverse);
211 for (i = end-1; i >= 0; i--) {
212 if (op[i].op == OP_TDB_TRAVERSE)
214 if (op[i].op != OP_TDB_TRAVERSE_READ_START
215 && op[i].op != OP_TDB_TRAVERSE_START)
223 errx(1, "Line %u: no traversal start found", end+1);
227 if (is_trivial_traverse(op+i, end-i)) {
228 /* Fill in a plentiful hash table. */
229 op[i].trav->hash = talloc_zero_array(op[i].trav,
230 struct traverse_hash,
232 for (; i < end; i++) {
234 if (op[i].op != OP_TDB_TRAVERSE)
236 h = hash_key(&op[i].key) % (trav->num * 2);
237 while (trav->hash[h].index)
238 h = (h + 1) % (trav->num * 2);
239 trav->hash[h].index = i+1;
240 trav->hash[h].key = op[i].key;
246 static unsigned run_ops(struct tdb_context *tdb, const struct op op[],
247 unsigned int start, unsigned int stop);
249 struct traverse_info {
255 /* Trivial case: do whatever they did for this key. */
256 static int trivial_traverse(struct tdb_context *tdb,
257 TDB_DATA key, TDB_DATA data,
260 struct traverse_info *tinfo = _tinfo;
261 struct traverse *trav = tinfo->op[tinfo->start].trav;
262 unsigned int h = hash_key(&key) % (trav->num * 2);
264 while (trav->hash[h].index) {
265 if (key_eq(trav->hash[h].key, key)) {
266 run_ops(tdb, tinfo->op, trav->hash[h].index, trav->end);
270 h = (h + 1) % (trav->num * 2);
272 errx(1, "Traverse at %u: unexpected key", tinfo->start + 1);
275 /* More complex. Just do whatever's they did at the n'th entry. */
276 static int nontrivial_traverse(struct tdb_context *tdb,
277 TDB_DATA key, TDB_DATA data,
280 struct traverse_info *tinfo = _tinfo;
281 struct traverse *trav = tinfo->op[tinfo->start].trav;
283 if (tinfo->i == trav->end)
284 errx(1, "Transaction starting line %u did not terminate",
287 if (tinfo->op[tinfo->i].op != OP_TDB_TRAVERSE)
288 errx(1, "Transaction starting line %u terminated early",
291 /* Run any normal ops. */
292 tinfo->i = run_ops(tdb, tinfo->op, tinfo->i+1, trav->end);
294 if (tinfo->i == trav->end)
299 static unsigned op_traverse(struct tdb_context *tdb,
300 int (*traversefn)(struct tdb_context *,
301 tdb_traverse_func, void *),
302 const struct op op[],
305 struct traverse *trav = op[start].trav;
306 struct traverse_info tinfo = { op, start, start+1 };
310 int ret = traversefn(tdb, trivial_traverse, &tinfo);
311 if (ret != trav->num)
312 errx(1, "Line %u: short traversal %i", start+1, ret);
316 traversefn(tdb, nontrivial_traverse, &tinfo);
318 /* Traversing in wrong order can have strange effects: eg. if
319 * original traverse went A (delete A), B, we might do B
320 * (delete A). So if we have ops left over, we do it now. */
321 while (tinfo.i != trav->end) {
322 if (op[tinfo.i].op == OP_TDB_TRAVERSE)
325 tinfo.i = run_ops(tdb, op, tinfo.i, trav->end);
330 static __attribute__((noinline))
331 unsigned run_ops(struct tdb_context *tdb, const struct op op[],
332 unsigned int start, unsigned int stop)
337 for (i = start; i < stop; i++) {
340 try(tdb_lockall(tdb), op[i]);
342 case OP_TDB_LOCKALL_MARK:
343 try(tdb_lockall_mark(tdb), op[i]);
345 case OP_TDB_LOCKALL_UNMARK:
346 try(tdb_lockall_unmark(tdb), op[i]);
348 case OP_TDB_LOCKALL_NONBLOCK:
349 unreliable(tdb_lockall_nonblock(tdb), op[i].ret,
350 tdb_lockall(tdb), tdb_unlockall(tdb));
352 case OP_TDB_UNLOCKALL:
353 try(tdb_unlockall(tdb), op[i]);
355 case OP_TDB_LOCKALL_READ:
356 try(tdb_lockall_read(tdb), op[i]);
358 case OP_TDB_LOCKALL_READ_NONBLOCK:
359 unreliable(tdb_lockall_read_nonblock(tdb), op[i].ret,
360 tdb_lockall_read(tdb),
361 tdb_unlockall_read(tdb));
363 case OP_TDB_UNLOCKALL_READ:
364 try(tdb_unlockall_read(tdb), op[i]);
366 case OP_TDB_CHAINLOCK:
367 try(tdb_chainlock(tdb, op[i].key), op[i]);
369 case OP_TDB_CHAINLOCK_NONBLOCK:
370 unreliable(tdb_chainlock_nonblock(tdb, op[i].key),
372 tdb_chainlock(tdb, op[i].key),
373 tdb_chainunlock(tdb, op[i].key));
375 case OP_TDB_CHAINLOCK_MARK:
376 try(tdb_chainlock_mark(tdb, op[i].key), op[i]);
378 case OP_TDB_CHAINLOCK_UNMARK:
379 try(tdb_chainlock_unmark(tdb, op[i].key), op[i]);
381 case OP_TDB_CHAINUNLOCK:
382 try(tdb_chainunlock(tdb, op[i].key), op[i]);
384 case OP_TDB_CHAINLOCK_READ:
385 try(tdb_chainlock_read(tdb, op[i].key), op[i]);
387 case OP_TDB_CHAINUNLOCK_READ:
388 try(tdb_chainunlock_read(tdb, op[i].key), op[i]);
390 case OP_TDB_INCREMENT_SEQNUM_NONBLOCK:
391 tdb_increment_seqnum_nonblock(tdb);
393 case OP_TDB_PARSE_RECORD:
394 try(tdb_parse_record(tdb, op[i].key, get_len, NULL), op[i]);
397 try(tdb_exists(tdb, op[i].key), op[i]);
400 try(tdb_store(tdb, op[i].key, op[i].data, op[i].flag), op[i]);
403 try(tdb_append(tdb, op[i].key, op[i].data), op[i]);
405 case OP_TDB_GET_SEQNUM:
406 try(tdb_get_seqnum(tdb), op[i]);
408 case OP_TDB_WIPE_ALL:
409 try(tdb_wipe_all(tdb), op[i]);
411 case OP_TDB_TRANSACTION_START:
412 try(tdb_transaction_start(tdb), op[i]);
414 case OP_TDB_TRANSACTION_CANCEL:
415 try(tdb_transaction_cancel(tdb), op[i]);
417 case OP_TDB_TRANSACTION_COMMIT:
418 try(tdb_transaction_commit(tdb), op[i]);
420 case OP_TDB_TRAVERSE_READ_START:
421 i = op_traverse(tdb, tdb_traverse_read, op, i);
423 case OP_TDB_TRAVERSE_START:
424 i = op_traverse(tdb, tdb_traverse, op, i);
426 case OP_TDB_TRAVERSE:
427 /* Terminate: we're in a traverse, and we've
430 case OP_TDB_TRAVERSE_END:
431 errx(1, "Line %u: unepxected end traverse\n", i+1);
432 case OP_TDB_FIRSTKEY:
433 data = tdb_firstkey(tdb);
434 if (data.dsize != op[i].data.dsize
435 || memcmp(data.dptr, op[i].data.dptr, data.dsize))
436 errx(1, "Line %u: bad firstkey", i+1);
439 data = tdb_nextkey(tdb, op[i].key);
440 if (data.dsize != op[i].data.dsize
441 || memcmp(data.dptr, op[i].data.dptr, data.dsize))
442 errx(1, "Line %u: bad nextkey", i+1);
445 data = tdb_fetch(tdb, op[i].key);
446 if (data.dsize != op[i].data.dsize
447 || memcmp(data.dptr, op[i].data.dptr, data.dsize))
448 errx(1, "Line %u: bad fetch", i+1);
451 try(tdb_delete(tdb, op[i].key), op[i]);
454 errx(1, "Line %u: unexpected close", i+1);
461 int main(int argc, char *argv[])
466 struct tdb_context *tdb = NULL;
467 struct op *op = talloc_array(NULL, struct op, 1);
468 struct timeval start, end;
471 errx(1, "Usage: %s <tracefile> <tdbfile>", argv[0]);
473 file = grab_file(NULL, argv[1], NULL);
475 err(1, "Reading %s", argv[1]);
477 lines = strsplit(file, file, "\n", NULL);
479 for (i = 0; lines[i]; i++) {
480 char **words = strsplit(lines, lines[i], " ", NULL);
481 if (!tdb && !streq(words[0], "tdb_open"))
482 errx(1, "Line %u is not tdb_open", i+1);
484 if (streq(words[0], "tdb_open")) {
486 errx(1, "Line %u: tdb_open again?", i+1);
487 tdb = tdb_open_ex(argv[2], atoi(words[2]),
488 strtoul(words[3], NULL, 0),
489 strtoul(words[4], NULL, 0), 0600,
492 err(1, "Opening tdb %s", argv[2]);
493 } else if (streq(words[0], "tdb_lockall")) {
494 add_op(&op, i, OP_TDB_LOCKALL, NULL, NULL, 0);
495 } else if (streq(words[0], "tdb_lockall_mark")) {
496 add_op(&op, i, OP_TDB_LOCKALL_MARK, NULL, NULL, 0);
497 } else if (streq(words[0], "tdb_lockall_unmark")) {
498 add_op(&op, i, OP_TDB_LOCKALL_UNMARK, NULL, NULL, 0);
499 } else if (streq(words[0], "tdb_lockall_nonblock")) {
500 add_op(&op, i, OP_TDB_LOCKALL_NONBLOCK, NULL, NULL,
502 } else if (streq(words[0], "tdb_unlockall")) {
503 add_op(&op, i, OP_TDB_UNLOCKALL, NULL, NULL, 0);
504 } else if (streq(words[0], "tdb_lockall_read")) {
505 add_op(&op, i, OP_TDB_LOCKALL_READ, NULL, NULL, 0);
506 } else if (streq(words[0], "tdb_lockall_read_nonblock")) {
507 add_op(&op, i, OP_TDB_LOCKALL_READ_NONBLOCK, NULL, NULL,
509 } else if (streq(words[0], "tdb_unlockall_read\n")) {
510 add_op(&op, i, OP_TDB_UNLOCKALL_READ, NULL, NULL, 0);
511 } else if (streq(words[0], "tdb_chainlock")) {
512 add_op(&op, i, OP_TDB_CHAINLOCK, words[1], NULL, 0);
513 } else if (streq(words[0], "tdb_chainlock_nonblock")) {
514 add_op(&op, i, OP_TDB_CHAINLOCK_NONBLOCK,
515 words[1], NULL, atoi(words[3]));
516 } else if (streq(words[0], "tdb_chainlock_mark")) {
517 add_op(&op, i, OP_TDB_CHAINLOCK_MARK, words[1], NULL,
519 } else if (streq(words[0], "tdb_chainlock_unmark")) {
520 add_op(&op, i, OP_TDB_CHAINLOCK_UNMARK, words[1], NULL,
522 } else if (streq(words[0], "tdb_chainunlock")) {
523 add_op(&op, i, OP_TDB_CHAINUNLOCK, words[1], NULL, 0);
524 } else if (streq(words[0], "tdb_chainlock_read")) {
525 add_op(&op, i, OP_TDB_CHAINLOCK_READ, words[1],
527 } else if (streq(words[0], "tdb_chainunlock_read")) {
528 add_op(&op, i, OP_TDB_CHAINUNLOCK_READ, words[1],
530 } else if (streq(words[0], "tdb_close")) {
531 add_op(&op, i, OP_TDB_CLOSE, NULL, NULL, 0);
532 } else if (streq(words[0], "tdb_increment_seqnum_nonblock")) {
533 add_op(&op, i, OP_TDB_INCREMENT_SEQNUM_NONBLOCK,
535 } else if (streq(words[0], "tdb_fetch")) {
536 if (streq(words[3], "ENOENT"))
537 add_op(&op, i, OP_TDB_FETCH, words[1], NULL,
540 add_op(&op, i, OP_TDB_FETCH, words[1], words[3],
542 } else if (streq(words[0], "tdb_parse_record")) {
543 if (streq(words[3], "ENOENT"))
544 add_op(&op, i, OP_TDB_PARSE_RECORD,
545 words[1], NULL, -TDB_ERR_NOEXIST);
547 add_op(&op, i, OP_TDB_PARSE_RECORD,
548 words[1], NULL, atoi(words[3]));
549 } else if (streq(words[0], "tdb_exists")) {
550 add_op(&op, i, OP_TDB_EXISTS, words[1], NULL,
552 } else if (streq(words[0], "tdb_delete")) {
553 add_op(&op, i, OP_TDB_DELETE, words[1], NULL,
554 streq(words[3], "ENOENT")
555 ? -TDB_ERR_NOEXIST : 0);
556 } else if (streq(words[0], "tdb_store")) {
559 if (streq(words[5], "EEXIST"))
560 new = add_op(&op, i, OP_TDB_STORE, words[2],
561 words[3], -TDB_ERR_EXISTS);
562 else if (streq(words[5], "ENOENT"))
563 new = add_op(&op, i, OP_TDB_STORE, words[2],
564 words[3], -TDB_ERR_NOEXIST);
566 new = add_op(&op, i, OP_TDB_STORE, words[2],
568 if (streq(words[1], "insert"))
569 new->flag = TDB_INSERT;
570 else if (streq(words[1], "modify"))
571 new->flag = TDB_MODIFY;
572 else if (streq(words[1], "normal"))
575 errx(1, "Line %u: invalid tdb_store", i+1);
576 } else if (streq(words[0], "tdb_append")) {
577 add_op(&op, i, OP_TDB_APPEND, words[1], words[2], 0);
578 } else if (streq(words[0], "tdb_get_seqnum")) {
579 add_op(&op, i, OP_TDB_GET_SEQNUM, NULL, NULL,
581 } else if (streq(words[0], "tdb_wipe_all")) {
582 add_op(&op, i, OP_TDB_WIPE_ALL, NULL, NULL, 0);
583 } else if (streq(words[0], "tdb_transaction_start")) {
584 add_op(&op, i, OP_TDB_TRANSACTION_START, NULL, NULL, 0);
585 } else if (streq(words[0], "tdb_transaction_cancel")) {
586 add_op(&op, i, OP_TDB_TRANSACTION_CANCEL, NULL, NULL,
588 } else if (streq(words[0], "tdb_transaction_commit")) {
589 add_op(&op, i, OP_TDB_TRANSACTION_COMMIT, NULL, NULL,
591 } else if (streq(words[0], "tdb_traverse_read_start")) {
592 add_op(&op, i, OP_TDB_TRAVERSE_READ_START, NULL, NULL,
594 } else if (streq(words[0], "tdb_traverse_start")) {
595 add_op(&op, i, OP_TDB_TRAVERSE_START, NULL, NULL, 0)
597 } else if (streq(words[0], "tdb_traverse_end")) {
598 /* = %u means traverse function terminated. */
599 if (words[1] == NULL)
600 add_op(&op, i, OP_TDB_TRAVERSE_END, NULL, NULL,
603 add_op(&op, i, OP_TDB_TRAVERSE_END, NULL, NULL,
605 analyze_traverse(op, i);
606 } else if (streq(words[0], "traverse")) {
607 add_op(&op, i, OP_TDB_TRAVERSE, words[1], words[2], 0);
608 } else if (streq(words[0], "tdb_firstkey")) {
609 if (streq(words[2], "ENOENT"))
610 add_op(&op, i, OP_TDB_FIRSTKEY, NULL, NULL,
613 add_op(&op, i, OP_TDB_FIRSTKEY, NULL, words[2],
615 } else if (streq(words[0], "tdb_nextkey")) {
616 if (streq(words[3], "ENOENT"))
617 add_op(&op, i, OP_TDB_NEXTKEY, words[1], NULL,
620 add_op(&op, i, OP_TDB_NEXTKEY,
621 words[1], words[3], 0);
623 errx(1, "Line %u: unknown op '%s'", i+1, words[0]);
626 printf("Successfully input %u lines\n", i);
627 gettimeofday(&start, NULL);
628 run_ops(tdb, op, 1, i-1);
629 gettimeofday(&end, NULL);
630 if (op[i-1].op != OP_TDB_CLOSE)
631 warnx("Last operation is not tdb_close: incomplete?");
633 end.tv_sec -= start.tv_sec;
634 printf("Time replaying: %lu usec\n",
635 end.tv_sec * 1000000UL + (end.tv_usec - start.tv_usec));