merge
authorRusty Russell <rusty@rustcorp.com.au>
Sun, 19 Jul 2009 01:44:41 +0000 (11:14 +0930)
committerRusty Russell <rusty@rustcorp.com.au>
Sun, 19 Jul 2009 01:44:41 +0000 (11:14 +0930)
42 files changed:
.bzrignore
ccan/short_types/_info [new file with mode: 0644]
ccan/short_types/short_types.h [new file with mode: 0644]
ccan/short_types/test/run.c [new file with mode: 0644]
ccan/talloc/_info
ccan/talloc/talloc.c
ccan/talloc/talloc.h
ccan/talloc_link/_info [new file with mode: 0644]
ccan/talloc_link/talloc_link.c [new file with mode: 0644]
ccan/talloc_link/talloc_link.h [new file with mode: 0644]
ccan/talloc_link/test/run.c [new file with mode: 0644]
ccan/tap/tap.3
ccan/tap/tap.c
ccan/tap/tap.h
ccan/tdb/io.c
ccan/tdb/lock.c
ccan/tdb/open.c
ccan/tdb/tdb.c
ccan/tdb/tdb_private.h
ccan/tdb/test/run-nested-traverse.c [new file with mode: 0644]
ccan/tdb/test/run-traverse-in-transaction.c [new file with mode: 0644]
ccan/tdb/test/run-zero-append.c [new file with mode: 0644]
ccan/tdb/tools/Makefile [new file with mode: 0644]
ccan/tdb/tools/keywords.c [new file with mode: 0644]
ccan/tdb/tools/keywords.gperf [new file with mode: 0644]
ccan/tdb/tools/replay_trace.c [new file with mode: 0644]
ccan/tdb/tools/tdbdump.c [new file with mode: 0644]
ccan/tdb/tools/tdbtorture.c [new file with mode: 0644]
ccan/tdb/tools/tests/1-torture.trace.tar.bz2 [new file with mode: 0644]
ccan/tdb/tools/tests/2-torture.trace.tar.bz2 [new file with mode: 0644]
ccan/tdb/tools/tests/3-torture.trace.tar.bz2 [new file with mode: 0644]
ccan/tdb/tools/tests/4-torture.trace.tar.bz2 [new file with mode: 0644]
ccan/tdb/tools/tests/5-torture.trace.tar.bz2 [new file with mode: 0644]
ccan/tdb/tools/tests/6-torture.trace.tar.bz2 [new file with mode: 0644]
ccan/tdb/tools/tests/7-torture.trace.tar.bz2 [new file with mode: 0644]
ccan/tdb/tools/tests/8-torture.trace.tar.bz2 [new file with mode: 0644]
ccan/tdb/tools/tests/9-torture.trace.tar.bz2 [new file with mode: 0644]
ccan/tdb/transaction.c
ccan/tdb/traverse.c
junkcode/fork0@users.sf.net-bitmaps/bitmaps.h [new file with mode: 0644]
junkcode/fork0@users.sf.net-pathexpand/pathexpand.c [new file with mode: 0644]
junkcode/fork0@users.sf.net-timeout/timeout.c [new file with mode: 0644]

index b513851143d3f69e025e4816c7548df0b63d3c38..3dfba6e9fc4b27c0359ad511533fb44f56ed4f6c 100644 (file)
@@ -1,4 +1,3 @@
-_info
 .depends
 *.d
 *~
diff --git a/ccan/short_types/_info b/ccan/short_types/_info
new file mode 100644 (file)
index 0000000..bc69b1b
--- /dev/null
@@ -0,0 +1,80 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * short_types - shorter names for standard integer types
+ *
+ * "C is a Spartan language, and so should your naming be."
+ *     -- Linus Torvalds
+ *
+ * The short_types header provides for convenient abbreviations for the
+ * posixly-damned uint32_t types.  It also provides be32/le32 for explicitly
+ * annotating types of specific endian.
+ *
+ * Include this header, if only to stop people using these identifiers
+ * for other things!
+ *
+ * Example:
+ *     #include <stdint.h>
+ *     #include <string.h>
+ *     #include <stdio.h>
+ *     #include <ccan/short_types/short_types.h>
+ *     
+ *     // Print nonsensical numerical comparison of POSIX vs. short_types. 
+ *     #define stringify_1(x)  #x
+ *     #define stringify(x)    stringify_1(x)
+ *     
+ *     static void evaluate(size_t size, const char *posix, const char *sht,
+ *                          unsigned int *posix_total, unsigned int *sht_total,
+ *                          unsigned int *size_total)
+ *     {
+ *             printf("\t%ssigned %s: POSIX %i%%, short %i%%\n",
+ *                    sht[0] == 'u' ? "un" : "",
+ *                    sht+1,
+ *                    strlen(posix)*100 / size,
+ *                    strlen(sht)*100 / size);
+ *             *posix_total += strlen(posix);
+ *             *sht_total += strlen(sht);
+ *             *size_total += size;
+ *     }
+ *
+ *     #define EVALUATE(psx, short, pt, st, t)                         \
+ *             evaluate(sizeof(psx), stringify(psx), stringify(sht), pt, st, t)
+ *
+ *     int main(void)
+ *     {
+ *             unsigned int posix_total = 0, sht_total = 0, size_total = 0;
+ *
+ *             printf("Comparing size of type vs size of name:\n");
+ *
+ *             EVALUATE(uint8_t, u8, &posix_total, &sht_total, &size_total);
+ *             EVALUATE(int8_t, s8, &posix_total, &sht_total, &size_total);
+ *             EVALUATE(uint16_t, u16, &posix_total, &sht_total, &size_total);
+ *             EVALUATE(int16_t, s16, &posix_total, &sht_total, &size_total);
+ *             EVALUATE(uint32_t, u32, &posix_total, &sht_total, &size_total);
+ *             EVALUATE(int32_t, s32, &posix_total, &sht_total, &size_total);
+ *             EVALUATE(uint64_t, u64, &posix_total, &sht_total, &size_total);
+ *             EVALUATE(int64_t, s64, &posix_total, &sht_total, &size_total);
+ *
+ *             printf("Conclusion:\n"
+ *                    "\tPOSIX is %u%% LESS efficient than binary.\n"
+ *                    "\tshort_types.h is %u%% MORE efficient than binary.\n",
+ *                    (posix_total - size_total) * 100 / size_total,
+ *                    (size_total - sht_total) * 100 / size_total);
+ *             return 0;
+ *     }
+ *
+ * Licence: LGPL (2 or any later version)
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/short_types/short_types.h b/ccan/short_types/short_types.h
new file mode 100644 (file)
index 0000000..e34efe0
--- /dev/null
@@ -0,0 +1,31 @@
+#ifndef CCAN_SHORT_TYPES_H
+#define CCAN_SHORT_TYPES_H
+#include <stdint.h>
+
+/**
+ * u64/s64/u32/s32/u16/s16/u8/s8 - short names for explicitly-sized types.
+ */
+typedef uint64_t u64;
+typedef int64_t s64;
+typedef uint32_t u32;
+typedef int32_t s32;
+typedef uint16_t u16;
+typedef int16_t s16;
+typedef uint8_t u8;
+typedef int8_t s8;
+
+/**
+ * be64/be32/be16 - 64/32/16 bit big-endian representation.
+ */
+typedef uint64_t be64;
+typedef uint32_t be32;
+typedef uint16_t be16;
+
+/**
+ * le64/le32/le16 - 64/32/16 bit little-endian representation.
+ */
+typedef uint64_t le64;
+typedef uint32_t le32;
+typedef uint16_t le16;
+
+#endif /* CCAN_SHORT_TYPES_H */
diff --git a/ccan/short_types/test/run.c b/ccan/short_types/test/run.c
new file mode 100644 (file)
index 0000000..a78d56c
--- /dev/null
@@ -0,0 +1,38 @@
+#include "short_types/short_types.h"
+#include "tap/tap.h"
+#include <stdlib.h>
+#include <err.h>
+
+int main(int argc, char *argv[])
+{
+       plan_tests(22);
+
+       ok1(sizeof(u64) == 8);
+       ok1(sizeof(s64) == 8);
+       ok1(sizeof(u32) == 4);
+       ok1(sizeof(s32) == 4);
+       ok1(sizeof(u16) == 2);
+       ok1(sizeof(s16) == 2);
+       ok1(sizeof(u8) == 1);
+       ok1(sizeof(s8) == 1);
+
+       ok1(sizeof(be64) == 8);
+       ok1(sizeof(be32) == 4);
+       ok1(sizeof(be16) == 2);
+
+       ok1(sizeof(le64) == 8);
+       ok1(sizeof(le32) == 4);
+       ok1(sizeof(le16) == 2);
+
+       /* Signedness tests. */
+       ok1((u64)-1 > 0);
+       ok1((u32)-1 > 0);
+       ok1((u16)-1 > 0);
+       ok1((u8)-1 > 0);
+       ok1((s64)-1 < 0);
+       ok1((s32)-1 < 0);
+       ok1((s16)-1 < 0);
+       ok1((s8)-1 < 0);
+
+       return exit_status();
+}
index 95c91536b3fafa98d9cac86917d248d7c5bbbbd7..ed1a5dda44fc7d18faa43c874ef1f840db3d0e3c 100644 (file)
@@ -89,7 +89,7 @@
  *             return 0;
  *     }
  *
- * Licence: GPL (2 or any later version)
+ * Licence: LGPL (2 or any later version)
  */
 int main(int argc, char *argv[])
 {
index 1424748eef7fa9a5b49caabd9fb095914b51cd50..7a2dfab11bd1b7eb493f0ad437bef72b42ac4a97 100644 (file)
@@ -819,12 +819,12 @@ void *talloc_named_const(const void *context, size_t size, const char *name)
    will not be freed if the ref_count is > 1 or the destructor (if
    any) returns non-zero
 */
-int talloc_free(void *ptr)
+int talloc_free(const void *ptr)
 {
        int saved_errno = errno, ret;
 
        lock(ptr);
-       ret = _talloc_free(ptr);
+       ret = _talloc_free(discard_const_p(void, ptr));
        unlock();
        if (ret == 0)
                errno = saved_errno;
index 791c98a2bbd88c6e0e0d5571f6af341f07e007a3..e38d05b8095ca9d55abdbd8e9ac833e31ca08c0c 100644 (file)
  * See Also:
  *     talloc_set_destructor, talloc_unlink
  */
-int talloc_free(void *ptr);
+int talloc_free(const void *ptr);
 
 /**
  * talloc_set_destructor: set a destructor for when this pointer is freed
diff --git a/ccan/talloc_link/_info b/ccan/talloc_link/_info
new file mode 100644 (file)
index 0000000..fe66c24
--- /dev/null
@@ -0,0 +1,146 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * talloc_link - link helper for talloc
+ *
+ * Talloc references can be confusing and buggy.  In the cases where an object
+ * needs multiple parents, all parents need to be aware of the situation; thus
+ * talloc_link is a helper where all "parents" talloc_link an object they
+ * agree to share ownership of.
+ *
+ * Example:
+ *     // Silly program which keeps a cache of uppercased strings.
+ *     // The cache wants to keep strings around even after they may have
+ *     // been "freed" by the caller.
+ *     #include <stdio.h>
+ *     #include <err.h>
+ *     #include <string.h>
+ *     #include <ctype.h>
+ *     #include <ccan/talloc/talloc.h>
+ *     #include <ccan/talloc_link/talloc_link.h>
+ *
+ *     struct upcache {
+ *             const char *str;
+ *             const char *upstr;
+ *     };
+ *
+ *     static struct upcache *cache;
+ *     static unsigned int cache_hits = 0;
+ *     #define CACHE_SIZE 4
+ *     void init_upcase(void)
+ *     {
+ *             cache = talloc_zero_array(NULL, struct upcache, CACHE_SIZE);
+ *     }
+ *
+ *     static struct upcache *lookup_upcase(const char *str)
+ *     {
+ *             unsigned int i;
+ *             for (i = 0; i < CACHE_SIZE; i++)
+ *                     if (cache[i].str && !strcmp(cache[i].str, str)) {
+ *                             cache_hits++;
+ *                             return &cache[i];
+ *                     }
+ *             return NULL;
+ *     }
+ *
+ *     static struct upcache *new_upcase(const char *str)
+ *     {
+ *             unsigned int i;
+ *             char *upstr;
+ *
+ *             upstr = talloc_linked(cache, talloc_strdup(NULL, str));
+ *             if (!upstr)
+ *                     return NULL;
+ *
+ *             i = random() % CACHE_SIZE;
+ *
+ *             // Throw out old: works fine if cache[i].upstr is NULL.
+ *             talloc_delink(cache, cache[i].upstr);
+ *
+ *             // Replace with new.
+ *             cache[i].str = str;
+ *             cache[i].upstr = upstr;
+ *             while (*upstr) {
+ *                     *upstr = toupper(*upstr);
+ *                     upstr++;
+ *             }
+ *             return &cache[i];
+ *     }
+ *
+ *     // If you want to keep the result, talloc_link it.
+ *     const char *get_upcase(const char *str)
+ *     {
+ *             struct upcache *uc = lookup_upcase(str);
+ *             if (!uc)
+ *                     uc = new_upcase(str);
+ *             if (!uc)
+ *                     return NULL;
+ *             return uc->upstr;
+ *     }
+ *
+ *     void exit_upcase(void)
+ *     {
+ *             talloc_free(cache);
+ *             printf("Cache hits: %u\n", cache_hits);
+ *     }
+ *
+ *     int main(int argc, char *argv[])
+ *     {
+ *             unsigned int i;
+ *             const char **values;
+ *
+ *             // Will dump any memory leaks to stderr on exit.
+ *             talloc_enable_leak_report();
+ *
+ *             // Initialize cache.
+ *             init_upcase();
+ *
+ *             // Throw values in.
+ *             values = talloc_array(NULL, const char *, argc);
+ *             for (i = 1; i < argc; i++) {
+ *                     values[i-1] = talloc_link(values, get_upcase(argv[i]));
+ *                     if (!values[i-1])
+ *                             err(1, "Out of memory");
+ *             }
+ *             // This will free all the values, but cache will still work.
+ *             talloc_free(values);
+ *
+ *             // Repeat!
+ *             values = talloc_array(NULL, const char *, argc);
+ *             for (i = 1; i < argc; i++) {
+ *                     values[i-1] = talloc_link(values, get_upcase(argv[i]));
+ *                     if (!values[i-1])
+ *                             err(1, "Out of memory");
+ *             }
+ *
+ *             // This will remove cache links, but we still have a link.
+ *             exit_upcase();
+ *
+ *             // Show values, so we output something.
+ *             for (i = 0; i < argc - 1; i++)
+ *                     printf("%s ", values[i]);
+ *             printf("\n");
+ *
+ *             // This will finally free the upcase strings (last link).
+ *             talloc_free(values);
+ *
+ *             return 0;
+ *     }
+ *
+ * Licence: GPL (2 or any later version)
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               printf("ccan/talloc\n");
+               printf("ccan/list\n");
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/talloc_link/talloc_link.c b/ccan/talloc_link/talloc_link.c
new file mode 100644 (file)
index 0000000..b72b436
--- /dev/null
@@ -0,0 +1,95 @@
+#include <ccan/list/list.h>
+#include <ccan/talloc/talloc.h>
+#include <ccan/talloc_link/talloc_link.h>
+#include <assert.h>
+
+/* Fake parent, if they care. */
+static void *talloc_links = NULL;
+
+/* This is the parent of the linked object, so we can implement delink. */
+struct talloc_linked {
+       struct list_head links;
+       const void *obj;
+};
+
+/* This is a child of the linker, but not a parent of ref. */
+struct talloc_link {
+       struct list_node list;
+       struct talloc_linked *linked;
+};
+
+static int destroy_link(struct talloc_link *link)
+{
+       list_del(&link->list);
+       if (list_empty(&link->linked->links))
+               talloc_free(link->linked);
+       return 0;
+}
+
+static bool add_link(const void *ctx, struct talloc_linked *linked)
+{
+       struct talloc_link *link = talloc(ctx, struct talloc_link);
+       if (!link)
+               return false;
+
+       link->linked = linked;
+       list_add(&linked->links, &link->list);
+       talloc_set_destructor(link, destroy_link);
+       return true;
+}
+
+void *_talloc_linked(const void *ctx, const void *newobj)
+{
+       struct talloc_linked *linked;
+
+       if (talloc_parent(newobj)) {
+               /* Assume leak reporting is on: create dummy parent. */
+               if (!talloc_links)
+                       talloc_links = talloc_named_const(NULL, 0,
+                                                         "talloc_links");
+               /* This should now have same pseudo-NULL parent. */
+               assert(talloc_parent(newobj) == talloc_parent(talloc_links));
+       }
+
+       linked = talloc(talloc_links, struct talloc_linked);
+       if (!linked) {
+               talloc_free(newobj);
+               return NULL;
+       }
+       list_head_init(&linked->links);
+       linked->obj = talloc_steal(linked, newobj);
+
+       if (!add_link(ctx, linked)) {
+               talloc_free(linked);
+               return NULL;
+       }
+
+       return (void *)newobj;
+}
+
+void *_talloc_link(const void *ctx, const void *obj)
+{
+       struct talloc_linked *linked;
+
+       linked = talloc_get_type(talloc_parent(obj), struct talloc_linked);
+       assert(!list_empty(&linked->links));
+       return add_link(ctx, linked) ? (void *)obj : NULL;
+}
+
+void talloc_delink(const void *ctx, const void *obj)
+{
+       struct talloc_linked *linked;
+       struct talloc_link *i;
+
+       if (!obj)
+               return;
+
+       linked = talloc_get_type(talloc_parent(obj), struct talloc_linked);
+       list_for_each(&linked->links, i, list) {
+               if (talloc_is_parent(i, ctx)) {
+                       talloc_free(i);
+                       return;
+               }
+       }
+       abort();
+}
diff --git a/ccan/talloc_link/talloc_link.h b/ccan/talloc_link/talloc_link.h
new file mode 100644 (file)
index 0000000..a51b760
--- /dev/null
@@ -0,0 +1,47 @@
+#ifndef TALLOC_LINK_H
+#define TALLOC_LINK_H
+#include <ccan/talloc/talloc.h>
+
+/**
+ * talloc_linked - set up an object with an initial link.
+ * @ctx - the context to initially link to
+ * @newobj - the newly allocated object (with a NULL parent)
+ *
+ * The object will be freed when @ctx is freed (or talloc_delink(ctx,
+ * newobj) is called), unless more links are added using
+ * talloc_link().
+ *
+ * For convenient chaining, it returns @newobj on success, or frees
+ * @newobj and returns NULL.
+ */
+#define talloc_linked(ctx, newobj) \
+       ((_TALLOC_TYPEOF(newobj))_talloc_linked((ctx), (newobj)))
+
+/**
+ * talloc_link - add another link to a linkable object.
+ * @ctx - the context to link to
+ * @obj - the object previously made linkable with talloc_linked().
+ *
+ * The @obj will only be freed when all contexts linked to it are
+ * freed (or talloc_delink()ed).
+ *
+ * Returns @obj, or NULL on failure (out of memory).
+ */
+#define talloc_link(ctx, obj) \
+       ((_TALLOC_TYPEOF(obj))_talloc_link((ctx), (obj)))
+
+/**
+ * talloc_delink - explicitly remove a link from a linkable object.
+ * @ctx - the context previously used for talloc_link/talloc_linked
+ * @obj - the object previously used for talloc_link/talloc_linked
+ *
+ * Explicitly remove a link: normally it is implied by freeing @ctx.
+ * Removing the last link frees the object.
+ */
+void talloc_delink(const void *ctx, const void *linked);
+
+/* Internal helpers. */
+void *_talloc_link(const void *ctx, const void *linked);
+void *_talloc_linked(const void *ctx, const void *linked);
+
+#endif /* TALLOC_LINK_H */
diff --git a/ccan/talloc_link/test/run.c b/ccan/talloc_link/test/run.c
new file mode 100644 (file)
index 0000000..e095bd9
--- /dev/null
@@ -0,0 +1,116 @@
+#include "talloc_link/talloc_link.h"
+#include "tap/tap.h"
+#include "talloc_link/talloc_link.c"
+#include <stdlib.h>
+#include <err.h>
+
+static unsigned int destroy_count = 0;
+static int destroy_obj(void *obj)
+{
+       destroy_count++;
+       return 0;
+}
+
+int main(int argc, char *argv[])
+{
+       void *obj, *p1, *p2, *p3;
+
+       plan_tests(16);
+
+       talloc_enable_leak_report();
+
+       /* Single parent case. */
+       p1 = talloc(NULL, char);
+       obj = talloc_linked(p1, talloc(NULL, char));
+       talloc_set_destructor(obj, destroy_obj);
+
+       ok(destroy_count == 0, "destroy_count = %u", destroy_count);
+       talloc_free(p1);
+       ok(destroy_count == 1, "destroy_count = %u", destroy_count);
+
+       /* Dual parent case. */
+       p1 = talloc(NULL, char);
+       obj = talloc_linked(p1, talloc(NULL, char));
+       talloc_set_destructor(obj, destroy_obj);
+       p2 = talloc(NULL, char);
+       talloc_link(p2, obj);
+
+       talloc_free(p1);
+       ok(destroy_count == 1, "destroy_count = %u", destroy_count);
+       talloc_free(p2);
+       ok(destroy_count == 2, "destroy_count = %u", destroy_count);
+       
+       /* Triple parent case. */
+       p1 = talloc(NULL, char);
+       obj = talloc_linked(p1, talloc(NULL, char));
+       talloc_set_destructor(obj, destroy_obj);
+
+       p2 = talloc(NULL, char);
+       p3 = talloc(NULL, char);
+
+       talloc_link(p2, obj);
+       talloc_link(p3, obj);
+
+       talloc_free(p1);
+       ok(destroy_count == 2, "destroy_count = %u", destroy_count);
+       talloc_free(p2);
+       ok(destroy_count == 2, "destroy_count = %u", destroy_count);
+       talloc_free(p3);
+       ok(destroy_count == 3, "destroy_count = %u", destroy_count);
+
+       /* Single delink case. */
+       p1 = talloc(NULL, char);
+       obj = talloc_linked(p1, talloc(NULL, char));
+       talloc_set_destructor(obj, destroy_obj);
+
+       ok(destroy_count == 3, "destroy_count = %u", destroy_count);
+       talloc_delink(p1, obj);
+       ok(destroy_count == 4, "destroy_count = %u", destroy_count);
+       talloc_free(p1);
+
+       /* Double delink case. */
+       p1 = talloc(NULL, char);
+       obj = talloc_linked(p1, talloc(NULL, char));
+       talloc_set_destructor(obj, destroy_obj);
+
+       p2 = talloc(NULL, char);
+       talloc_link(p2, obj);
+
+       talloc_delink(p1, obj);
+       ok(destroy_count == 4, "destroy_count = %u", destroy_count);
+       talloc_delink(p2, obj);
+       ok(destroy_count == 5, "destroy_count = %u", destroy_count);
+       talloc_free(p1);
+       talloc_free(p2);
+
+       /* Delink and free. */
+       p1 = talloc(NULL, char);
+       obj = talloc_linked(p1, talloc(NULL, char));
+       talloc_set_destructor(obj, destroy_obj);
+       p2 = talloc(NULL, char);
+       talloc_link(p2, obj);
+
+       talloc_delink(p1, obj);
+       ok(destroy_count == 5, "destroy_count = %u", destroy_count);
+       talloc_free(p2);
+       ok(destroy_count == 6, "destroy_count = %u", destroy_count);
+       talloc_free(p1);
+
+       /* Free and delink. */
+       p1 = talloc(NULL, char);
+       obj = talloc_linked(p1, talloc(NULL, char));
+       talloc_set_destructor(obj, destroy_obj);
+       p2 = talloc(NULL, char);
+       talloc_link(p2, obj);
+
+       talloc_free(p1);
+       ok(destroy_count == 6, "destroy_count = %u", destroy_count);
+       talloc_delink(p2, obj);
+       ok(destroy_count == 7, "destroy_count = %u", destroy_count);
+       talloc_free(p2);
+
+       /* No leaks? */
+       ok1(talloc_total_size(NULL) == 0);
+
+       return exit_status();
+}
index 5395aef7aeb5fa4f8ceb8347e1f8aaee162c585b..0abab740d615b9a7ec218bb6d5fb7ba7c72994c7 100644 (file)
@@ -16,9 +16,9 @@ their success or failure.
 .Ss PRINTF STRINGS
 In the descriptions that follow, for any function that takes as the
 last two parameters
-.Dq Fa char * , Fa ...
+.Dq Fa const char * , Fa ...
 it can be assumed that the
-.Fa char *
+.Fa const char *
 is a
 .Fn printf
 -like format string, and the optional arguments are values to be placed
@@ -35,7 +35,7 @@ in that string.
 .Xc
 .It Xo
 .Ft void
-.Fn plan_skip_all "char *" "..."
+.Fn plan_skip_all "const char *" "..."
 .Xc
 .El
 .Pp
@@ -74,7 +74,7 @@ the tests.
 .Bl -tag -width indent
 .It Xo
 .Ft unsigned int
-.Fn ok "expression" "char *" "..."
+.Fn ok "expression" "const char *" "..."
 .Xc
 .It Xo
 .Ft unsigned int
@@ -82,11 +82,11 @@ the tests.
 .Xc
 .It Xo
 .Ft unsigned int
-.Fn pass "char *" "..."
+.Fn pass "const char *" "..."
 .Xc
 .It Xo
 .Ft unsigned int
-.Fn fail "char *" "..."
+.Fn fail "const char *" "..."
 .Xc
 .El
 .Pp
@@ -161,10 +161,10 @@ These are synonyms for ok(1, ...) and ok(0, ...).
 .Bl -tag -width indent
 .It Xo
 .Ft void
-.Fn skip "unsigned int" "char *" "..."
+.Fn skip "unsigned int" "const char *" "..."
 .Xc
 .It Xo
-.Fn skip_if "expression" "unsigned int" "char *" "..."
+.Fn skip_if "expression" "unsigned int" "const char *" "..."
 .Xc
 .El
 .Pp
@@ -204,7 +204,7 @@ skip_if(getuid() != 0, 1, "because test only works as root") {
 .Bl -tag -width indent
 .It Xo
 .Ft void
-.Fn todo_start "char *" "..."
+.Fn todo_start "const char *" "..."
 .Xc
 .It Xo
 .Ft void
@@ -261,8 +261,8 @@ yet to fix, but want to put tests in your testing script
 .Ss DIAGNOSTIC OUTPUT
 .Bl -tag -width indent
 .It Xo
-.Fr void
-.Fn diag "char *" "..."
+.Fr int
+.Fn diag "const char *" "..."
 .Xc
 .El
 .Pp
@@ -273,6 +273,7 @@ It ensures that the output will not be considered by the TAP test harness.
 adds the necessary trailing
 .Dq \en
 for you.
+It returns the number of characters written.
 .Bd -literal -offset indent
 diag("Expected return code 0, got return code %d", rcode);
 .Ed
index 0eaec9a5f852827d879553cfd50cd8bdf252f2c6..a5156aa194a748ecdf8822d49fde91ce7a0a257f 100644 (file)
@@ -42,7 +42,7 @@ static unsigned int test_count = 0; /* Number of tests that have been run */
 static unsigned int e_tests = 0; /* Expected number of tests to run */
 static unsigned int failures = 0; /* Number of tests that failed */
 static char *todo_msg = NULL;
-static char *todo_msg_fixed = "libtap malloc issue";
+static const char *todo_msg_fixed = "libtap malloc issue";
 static int todo = 0;
 static int test_died = 0;
 static int test_pid;
@@ -68,7 +68,7 @@ _expected_tests(unsigned int tests)
 }
 
 static void
-diagv(char *fmt, va_list ap)
+diagv(const char *fmt, va_list ap)
 {
        fputs("# ", stdout);
        vfprintf(stdout, fmt, ap);
@@ -76,7 +76,7 @@ diagv(char *fmt, va_list ap)
 }
 
 static void
-_diag(char *fmt, ...)
+_diag(const char *fmt, ...)
 {
        va_list ap;
        va_start(ap, fmt);
@@ -92,8 +92,8 @@ _diag(char *fmt, ...)
  * test_comment -- a comment to print afterwards, may be NULL
  */
 unsigned int
-_gen_result(int ok, const char *func, char *file, unsigned int line, 
-           char *test_name, ...)
+_gen_result(int ok, const char *func, const char *file, unsigned int line, 
+           const char *test_name, ...)
 {
        va_list ap;
        char *local_test_name = NULL;
@@ -293,7 +293,7 @@ plan_no_plan(void)
  * Note that the plan is to skip all tests
  */
 void
-plan_skip_all(char *reason)
+plan_skip_all(const char *reason)
 {
 
        LOCK;
@@ -345,7 +345,7 @@ plan_tests(unsigned int tests)
 }
 
 void
-diag(char *fmt, ...)
+diag(const char *fmt, ...)
 {
        va_list ap;
 
@@ -359,7 +359,7 @@ diag(char *fmt, ...)
 }
 
 void
-skip(unsigned int n, char *fmt, ...)
+skip(unsigned int n, const char *fmt, ...)
 {
        va_list ap;
        char *skip_msg;
@@ -384,7 +384,7 @@ skip(unsigned int n, char *fmt, ...)
 }
 
 void
-todo_start(char *fmt, ...)
+todo_start(const char *fmt, ...)
 {
        va_list ap;
 
index f854d3e39035071f736605fb96d0e44d27d0da3d..1dad63650e40a2c26f62f99d90964e6c9bedcd93 100644 (file)
@@ -124,8 +124,8 @@ void plan_tests(unsigned int tests);
 #endif
 #endif
 
-unsigned int _gen_result(int, const char *, char *, unsigned int, char *, ...)
-       PRINTF_ATTRIBUTE(5, 6);
+unsigned int _gen_result(int, const char *, const char *, unsigned int,
+   const char *, ...) PRINTF_ATTRIBUTE(5, 6);
 
 /**
  * diag - print a diagnostic message (use instead of printf/fprintf)
@@ -137,7 +137,7 @@ unsigned int _gen_result(int, const char *, char *, unsigned int, char *, ...)
  * Example:
  *     diag("Now running complex tests");
  */
-void diag(char *fmt, ...) PRINTF_ATTRIBUTE(1, 2);
+void diag(const char *fmt, ...) PRINTF_ATTRIBUTE(1, 2);
 
 /**
  * skip - print a diagnostic message (use instead of printf/fprintf)
@@ -160,7 +160,7 @@ void diag(char *fmt, ...) PRINTF_ATTRIBUTE(1, 2);
  *     skip(1, "Don't have SOME_FEATURE");
  *     #endif
  */
-void skip(unsigned int n, char *fmt, ...) PRINTF_ATTRIBUTE(2, 3);
+void skip(unsigned int n, const char *fmt, ...) PRINTF_ATTRIBUTE(2, 3);
 
 /**
  * todo_start - mark tests that you expect to fail.
@@ -185,7 +185,7 @@ void skip(unsigned int n, char *fmt, ...) PRINTF_ATTRIBUTE(2, 3);
  *     ok(dwim(), "Did what the user wanted");
  *     todo_end();
  */
-void todo_start(char *fmt, ...) PRINTF_ATTRIBUTE(1, 2);
+void todo_start(const char *fmt, ...) PRINTF_ATTRIBUTE(1, 2);
 
 /**
  * todo_end - end of tests you expect to fail.
@@ -241,6 +241,6 @@ void plan_no_plan(void);
  *     }
  *     plan_tests(13);
  */
-void plan_skip_all(char *reason);
+void plan_skip_all(const char *reason);
 
 #endif /* C99 or gcc */
index c25f1cb447f8578ea58ca2a68c81412f311bc38b..d8140fea31d3655146b697a1dd0959502bafa33e 100644 (file)
@@ -383,11 +383,7 @@ unsigned char *tdb_alloc_read(struct tdb_context *tdb, tdb_off_t offset, tdb_len
        unsigned char *buf;
 
        /* some systems don't like zero length malloc */
-       if (len == 0) {
-               len = 1;
-       }
-
-       if (!(buf = (unsigned char *)malloc(len))) {
+       if (!(buf = (unsigned char *)malloc(len ? len : 1))) {
                /* Ensure ecode is set for log fn. */
                tdb->ecode = TDB_ERR_OOM;
                TDB_LOG((tdb, TDB_DEBUG_ERROR,"tdb_alloc_read malloc failed len=%d (%s)\n",
index f156c0fa7b2e548640d47db23df71c9427ec73ce..bcd560d792231ff2defce3430cf6feb7117fa243 100644 (file)
@@ -301,7 +301,11 @@ int tdb_unlock(struct tdb_context *tdb, int list, int ltype)
  */
 int tdb_transaction_lock(struct tdb_context *tdb, int ltype)
 {
-       if (tdb->have_transaction_lock || tdb->global_lock.count) {
+       if (tdb->global_lock.count) {
+               return 0;
+       }
+       if (tdb->have_transaction_lock) {
+               tdb->have_transaction_lock++;
                return 0;
        }
        if (tdb->methods->tdb_brlock(tdb, TRANSACTION_LOCK, ltype, 
@@ -310,7 +314,7 @@ int tdb_transaction_lock(struct tdb_context *tdb, int ltype)
                tdb->ecode = TDB_ERR_LOCK;
                return -1;
        }
-       tdb->have_transaction_lock = 1;
+       tdb->have_transaction_lock++;
        return 0;
 }
 
@@ -319,15 +323,13 @@ int tdb_transaction_lock(struct tdb_context *tdb, int ltype)
  */
 int tdb_transaction_unlock(struct tdb_context *tdb)
 {
-       int ret;
-       if (!tdb->have_transaction_lock) {
+       if (tdb->global_lock.count) {
                return 0;
        }
-       ret = tdb->methods->tdb_brlock(tdb, TRANSACTION_LOCK, F_UNLCK, F_SETLKW, 0, 1);
-       if (ret == 0) {
-               tdb->have_transaction_lock = 0;
+       if (--tdb->have_transaction_lock) {
+               return 0;
        }
-       return ret;
+       return tdb->methods->tdb_brlock(tdb, TRANSACTION_LOCK, F_UNLCK, F_SETLKW, 0, 1);
 }
 
 
@@ -413,48 +415,58 @@ static int _tdb_unlockall(struct tdb_context *tdb, int ltype)
 /* lock entire database with write lock */
 int tdb_lockall(struct tdb_context *tdb)
 {
+       tdb_trace(tdb, "tdb_lockall");
        return _tdb_lockall(tdb, F_WRLCK, F_SETLKW);
 }
 
 /* lock entire database with write lock - mark only */
 int tdb_lockall_mark(struct tdb_context *tdb)
 {
+       tdb_trace(tdb, "tdb_lockall_mark");
        return _tdb_lockall(tdb, F_WRLCK | TDB_MARK_LOCK, F_SETLKW);
 }
 
 /* unlock entire database with write lock - unmark only */
 int tdb_lockall_unmark(struct tdb_context *tdb)
 {
+       tdb_trace(tdb, "tdb_lockall_unmark");
        return _tdb_unlockall(tdb, F_WRLCK | TDB_MARK_LOCK);
 }
 
 /* lock entire database with write lock - nonblocking varient */
 int tdb_lockall_nonblock(struct tdb_context *tdb)
 {
-       return _tdb_lockall(tdb, F_WRLCK, F_SETLK);
+       int ret = _tdb_lockall(tdb, F_WRLCK, F_SETLK);
+       tdb_trace_ret(tdb, "tdb_lockall_nonblock", ret);
+       return ret;
 }
 
 /* unlock entire database with write lock */
 int tdb_unlockall(struct tdb_context *tdb)
 {
+       tdb_trace(tdb, "tdb_unlockall");
        return _tdb_unlockall(tdb, F_WRLCK);
 }
 
 /* lock entire database with read lock */
 int tdb_lockall_read(struct tdb_context *tdb)
 {
+       tdb_trace(tdb, "tdb_lockall_read");
        return _tdb_lockall(tdb, F_RDLCK, F_SETLKW);
 }
 
 /* lock entire database with read lock - nonblock varient */
 int tdb_lockall_read_nonblock(struct tdb_context *tdb)
 {
-       return _tdb_lockall(tdb, F_RDLCK, F_SETLK);
+       int ret = _tdb_lockall(tdb, F_RDLCK, F_SETLK);
+       tdb_trace_ret(tdb, "tdb_lockall_read_nonblock", ret);
+       return ret;
 }
 
 /* unlock entire database with read lock */
 int tdb_unlockall_read(struct tdb_context *tdb)
 {
+       tdb_trace(tdb, "tdb_unlockall_read");
        return _tdb_unlockall(tdb, F_RDLCK);
 }
 
@@ -462,7 +474,9 @@ int tdb_unlockall_read(struct tdb_context *tdb)
    contention - it cannot guarantee how many records will be locked */
 int tdb_chainlock(struct tdb_context *tdb, TDB_DATA key)
 {
-       return tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK);
+       int ret = tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK);
+       tdb_trace_1rec(tdb, "tdb_chainlock", key);
+       return ret;
 }
 
 /* lock/unlock one hash chain, non-blocking. This is meant to be used
@@ -470,38 +484,46 @@ int tdb_chainlock(struct tdb_context *tdb, TDB_DATA key)
    locked */
 int tdb_chainlock_nonblock(struct tdb_context *tdb, TDB_DATA key)
 {
-       return tdb_lock_nonblock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK);
+       int ret = tdb_lock_nonblock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK);
+       tdb_trace_1rec_ret(tdb, "tdb_chainlock_nonblock", key, ret);
+       return ret;
 }
 
 /* mark a chain as locked without actually locking it. Warning! use with great caution! */
 int tdb_chainlock_mark(struct tdb_context *tdb, TDB_DATA key)
 {
-       return tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK | TDB_MARK_LOCK);
+       int ret = tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK | TDB_MARK_LOCK);
+       tdb_trace_1rec(tdb, "tdb_chainlock_mark", key);
+       return ret;
 }
 
 /* unmark a chain as locked without actually locking it. Warning! use with great caution! */
 int tdb_chainlock_unmark(struct tdb_context *tdb, TDB_DATA key)
 {
+       tdb_trace_1rec(tdb, "tdb_chainlock_unmark", key);
        return tdb_unlock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK | TDB_MARK_LOCK);
 }
 
 int tdb_chainunlock(struct tdb_context *tdb, TDB_DATA key)
 {
+       tdb_trace_1rec(tdb, "tdb_chainunlock", key);
        return tdb_unlock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK);
 }
 
 int tdb_chainlock_read(struct tdb_context *tdb, TDB_DATA key)
 {
-       return tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_RDLCK);
+       int ret;
+       ret = tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_RDLCK);
+       tdb_trace_1rec(tdb, "tdb_chainlock_read", key);
+       return ret;
 }
 
 int tdb_chainunlock_read(struct tdb_context *tdb, TDB_DATA key)
 {
+       tdb_trace_1rec(tdb, "tdb_chainunlock_read", key);
        return tdb_unlock(tdb, BUCKET(tdb->hash_fn(&key)), F_RDLCK);
 }
 
-
-
 /* record lock stops delete underneath */
 int tdb_lock_record(struct tdb_context *tdb, tdb_off_t off)
 {
index 8cd25cc5b5bc7802a9ebc3e7ad2ce0b7df4c9c28..69885284c55d6abfce78b4d15d9b126a442d8ea1 100644 (file)
@@ -206,6 +206,10 @@ struct tdb_context *tdb_open_ex(const char *name, int hash_size, int tdb_flags,
                        TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_open_ex: tdb_new_database failed!"));
                        goto fail;
                }
+#ifdef TDB_TRACE
+               /* All tracing will fail.  That's ok. */
+               tdb->tracefd = -1;
+#endif
                goto internal;
        }
 
@@ -314,6 +318,20 @@ struct tdb_context *tdb_open_ex(const char *name, int hash_size, int tdb_flags,
                goto fail;
        }
 
+#ifdef TDB_TRACE
+       {
+               char tracefile[strlen(name) + 32];
+
+               sprintf(tracefile, "%s.trace.%u", name, getpid());
+               tdb->tracefd = open(tracefile, O_WRONLY|O_CREAT|O_EXCL, 0600);
+               if (tdb->tracefd < 0)
+                       goto fail;
+               tdb_enable_seqnum(tdb);
+               tdb_trace_open(tdb, "tdb_open", hash_size, tdb_flags,
+                              open_flags);
+       }
+#endif
+
  internal:
        /* Internal (memory-only) databases skip all the code above to
         * do with disk files, and resume here by releasing their
@@ -329,6 +347,8 @@ struct tdb_context *tdb_open_ex(const char *name, int hash_size, int tdb_flags,
 
        if (!tdb)
                return NULL;
+
+       close(tdb->tracefd);
        
        if (tdb->map_ptr) {
                if (tdb->flags & TDB_INTERNAL)
@@ -365,8 +385,9 @@ int tdb_close(struct tdb_context *tdb)
        struct tdb_context **i;
        int ret = 0;
 
+       tdb_trace(tdb, "tdb_close");
        if (tdb->transaction) {
-               tdb_transaction_cancel(tdb);
+               tdb_transaction_cancel_internal(tdb);
        }
 
        if (tdb->map_ptr) {
@@ -388,6 +409,7 @@ int tdb_close(struct tdb_context *tdb)
                }
        }
 
+       close(tdb->tracefd);
        memset(tdb, 0, sizeof(*tdb));
        SAFE_FREE(tdb);
 
index 767452c9b34b520a51bed6aace888b3f5b2dcd4f..3acf05b96e15fdebc4ef893139a477907d293a30 100644 (file)
@@ -153,7 +153,7 @@ static int tdb_update_hash(struct tdb_context *tdb, TDB_DATA key, uint32_t hash,
  * then the TDB_DATA will have zero length but
  * a non-zero pointer
  */
-TDB_DATA tdb_fetch(struct tdb_context *tdb, TDB_DATA key)
+static TDB_DATA do_tdb_fetch(struct tdb_context *tdb, TDB_DATA key)
 {
        tdb_off_t rec_ptr;
        struct list_struct rec;
@@ -162,9 +162,9 @@ TDB_DATA tdb_fetch(struct tdb_context *tdb, TDB_DATA key)
 
        /* find which hash bucket it is in */
        hash = tdb->hash_fn(&key);
-       if (!(rec_ptr = tdb_find_lock_hash(tdb,key,hash,F_RDLCK,&rec)))
+       if (!(rec_ptr = tdb_find_lock_hash(tdb,key,hash,F_RDLCK,&rec))) {
                return tdb_null;
-
+       }
        ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec) + rec.key_len,
                                  rec.data_len);
        ret.dsize = rec.data_len;
@@ -172,6 +172,14 @@ TDB_DATA tdb_fetch(struct tdb_context *tdb, TDB_DATA key)
        return ret;
 }
 
+TDB_DATA tdb_fetch(struct tdb_context *tdb, TDB_DATA key)
+{
+       TDB_DATA ret = do_tdb_fetch(tdb, key);
+
+       tdb_trace_1rec_retrec(tdb, "tdb_fetch", key, ret);
+       return ret;
+}
+
 /*
  * Find an entry in the database and hand the record's data to a parsing
  * function. The parsing function is executed under the chain read lock, so it
@@ -202,8 +210,11 @@ int tdb_parse_record(struct tdb_context *tdb, TDB_DATA key,
        hash = tdb->hash_fn(&key);
 
        if (!(rec_ptr = tdb_find_lock_hash(tdb,key,hash,F_RDLCK,&rec))) {
+               tdb_trace_1rec_ret(tdb, "tdb_parse_record", key,
+                                  -TDB_ERR_NOEXIST);
                return TDB_ERRCODE(TDB_ERR_NOEXIST, 0);
        }
+       tdb_trace_1rec_ret(tdb, "tdb_parse_record", key, 0);
 
        ret = tdb_parse_data(tdb, key, rec_ptr + sizeof(rec) + rec.key_len,
                             rec.data_len, parser, private_data);
@@ -232,7 +243,11 @@ static int tdb_exists_hash(struct tdb_context *tdb, TDB_DATA key, uint32_t hash)
 int tdb_exists(struct tdb_context *tdb, TDB_DATA key)
 {
        uint32_t hash = tdb->hash_fn(&key);
-       return tdb_exists_hash(tdb, key, hash);
+       int ret;
+
+       ret = tdb_exists_hash(tdb, key, hash);
+       tdb_trace_1rec_ret(tdb, "tdb_exists", key, ret);
+       return ret;
 }
 
 /* actually delete an entry in the database given the offset */
@@ -387,7 +402,11 @@ static int tdb_delete_hash(struct tdb_context *tdb, TDB_DATA key, uint32_t hash)
 int tdb_delete(struct tdb_context *tdb, TDB_DATA key)
 {
        uint32_t hash = tdb->hash_fn(&key);
-       return tdb_delete_hash(tdb, key, hash);
+       int ret;
+
+       ret = tdb_delete_hash(tdb, key, hash);
+       tdb_trace_1rec_ret(tdb, "tdb_delete", key, ret);
+       return ret;
 }
 
 /*
@@ -419,29 +438,14 @@ static tdb_off_t tdb_find_dead(struct tdb_context *tdb, uint32_t hash,
        return 0;
 }
 
-/* store an element in the database, replacing any existing element
-   with the same key 
-
-   return 0 on success, -1 on failure
-*/
-int tdb_store(struct tdb_context *tdb, TDB_DATA key, TDB_DATA dbuf, int flag)
+static int _tdb_store(struct tdb_context *tdb, TDB_DATA key, TDB_DATA dbuf,
+                     int flag, uint32_t hash)
 {
        struct list_struct rec;
-       uint32_t hash;
        tdb_off_t rec_ptr;
        char *p = NULL;
        int ret = -1;
 
-       if (tdb->read_only || tdb->traverse_read) {
-               tdb->ecode = TDB_ERR_RDONLY;
-               return -1;
-       }
-
-       /* find which hash bucket it is in */
-       hash = tdb->hash_fn(&key);
-       if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
-               return -1;
-
        /* check for it existing, on insert. */
        if (flag == TDB_INSERT) {
                if (tdb_exists_hash(tdb, key, hash)) {
@@ -557,6 +561,33 @@ int tdb_store(struct tdb_context *tdb, TDB_DATA key, TDB_DATA dbuf, int flag)
        }
 
        SAFE_FREE(p); 
+       return ret;
+}
+
+/* store an element in the database, replacing any existing element
+   with the same key 
+
+   return 0 on success, -1 on failure
+*/
+int tdb_store(struct tdb_context *tdb, TDB_DATA key, TDB_DATA dbuf, int flag)
+{
+       uint32_t hash;
+       int ret;
+
+       if (tdb->read_only || tdb->traverse_read) {
+               tdb->ecode = TDB_ERR_RDONLY;
+               tdb_trace_2rec_flag_ret(tdb, "tdb_store", key, dbuf, flag,
+                                       -TDB_ERR_RDONLY);
+               return -1;
+       }
+
+       /* find which hash bucket it is in */
+       hash = tdb->hash_fn(&key);
+       if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
+               return -1;
+
+       ret = _tdb_store(tdb, key, dbuf, flag, hash);
+       tdb_trace_2rec_flag_ret(tdb, "tdb_store", key, dbuf, flag, ret);
        tdb_unlock(tdb, BUCKET(hash), F_WRLCK);
        return ret;
 }
@@ -574,13 +605,18 @@ int tdb_append(struct tdb_context *tdb, TDB_DATA key, TDB_DATA new_dbuf)
        if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1)
                return -1;
 
-       dbuf = tdb_fetch(tdb, key);
+       dbuf = do_tdb_fetch(tdb, key);
 
        if (dbuf.dptr == NULL) {
                dbuf.dptr = (unsigned char *)malloc(new_dbuf.dsize);
        } else {
-               unsigned char *new_dptr = (unsigned char *)realloc(dbuf.dptr,
-                                                    dbuf.dsize + new_dbuf.dsize);
+               unsigned int new_len = dbuf.dsize + new_dbuf.dsize;
+               unsigned char *new_dptr;
+
+               /* realloc '0' is special: don't do that. */
+               if (new_len == 0)
+                       new_len = 1;
+               new_dptr = (unsigned char *)realloc(dbuf.dptr, new_len);
                if (new_dptr == NULL) {
                        free(dbuf.dptr);
                }
@@ -595,7 +631,8 @@ int tdb_append(struct tdb_context *tdb, TDB_DATA key, TDB_DATA new_dbuf)
        memcpy(dbuf.dptr + dbuf.dsize, new_dbuf.dptr, new_dbuf.dsize);
        dbuf.dsize += new_dbuf.dsize;
 
-       ret = tdb_store(tdb, key, dbuf, 0);
+       ret = _tdb_store(tdb, key, dbuf, 0, hash);
+       tdb_trace_2rec_retrec(tdb, "tdb_append", key, new_dbuf, dbuf);
        
 failed:
        tdb_unlock(tdb, BUCKET(hash), F_WRLCK);
@@ -648,6 +685,7 @@ int tdb_get_seqnum(struct tdb_context *tdb)
        tdb_off_t seqnum=0;
 
        tdb_ofs_read(tdb, TDB_SEQNUM_OFS, &seqnum);
+       tdb_trace_ret(tdb, "tdb_get_seqnum", seqnum);
        return seqnum;
 }
 
@@ -729,6 +767,8 @@ int tdb_wipe_all(struct tdb_context *tdb)
                return -1;
        }
 
+       tdb_trace(tdb, "tdb_wipe_all");
+
        /* see if the tdb has a recovery area, and remember its size
           if so. We don't want to lose this as otherwise each
           tdb_wipe_all() in a transaction will increase the size of
@@ -800,3 +840,143 @@ failed:
        tdb_unlockall(tdb);
        return -1;
 }
+
+#ifdef TDB_TRACE
+static void tdb_trace_write(struct tdb_context *tdb, const char *str)
+{
+       if (write(tdb->tracefd, str, strlen(str)) != strlen(str)) {
+               close(tdb->tracefd);
+               tdb->tracefd = -1;
+       }
+}
+
+static void tdb_trace_start(struct tdb_context *tdb)
+{
+       tdb_off_t seqnum=0;
+       char msg[sizeof(tdb_off_t) * 4];
+
+       tdb_ofs_read(tdb, TDB_SEQNUM_OFS, &seqnum);
+       sprintf(msg, "%u ", seqnum);
+       tdb_trace_write(tdb, msg);
+}
+
+static void tdb_trace_end(struct tdb_context *tdb)
+{
+       tdb_trace_write(tdb, "\n");
+}
+
+static void tdb_trace_end_ret(struct tdb_context *tdb, int ret)
+{
+       char msg[sizeof(ret) * 4];
+       sprintf(msg, " = %i\n", ret);
+       tdb_trace_write(tdb, msg);
+}
+
+static void tdb_trace_record(struct tdb_context *tdb, TDB_DATA rec)
+{
+       char msg[20];
+       unsigned int i;
+
+       /* We differentiate zero-length records from non-existent ones. */
+       if (rec.dptr == NULL) {
+               tdb_trace_write(tdb, " NULL");
+               return;
+       }
+       sprintf(msg, " %zu:", rec.dsize);
+       tdb_trace_write(tdb, msg);
+       for (i = 0; i < rec.dsize; i++) {
+               sprintf(msg, "%02x", rec.dptr[i]);
+               tdb_trace_write(tdb, msg);
+       }
+}
+
+void tdb_trace(struct tdb_context *tdb, const char *op)
+{
+       tdb_trace_start(tdb);
+       tdb_trace_write(tdb, op);
+       tdb_trace_end(tdb);
+}
+
+void tdb_trace_open(struct tdb_context *tdb, const char *op,
+                   unsigned hash_size, unsigned tdb_flags, unsigned open_flags)
+{
+       char msg[128];
+
+       sprintf(msg, "%s %u %#x %#x", op, hash_size, tdb_flags, open_flags);
+       tdb_trace_start(tdb);
+       tdb_trace_write(tdb, msg);
+       tdb_trace_end(tdb);
+}
+
+void tdb_trace_ret(struct tdb_context *tdb, const char *op, int ret)
+{
+       tdb_trace_start(tdb);
+       tdb_trace_write(tdb, op);
+       tdb_trace_end_ret(tdb, ret);
+}
+
+void tdb_trace_retrec(struct tdb_context *tdb, const char *op, TDB_DATA ret)
+{
+       tdb_trace_start(tdb);
+       tdb_trace_write(tdb, op);
+       tdb_trace_write(tdb, " =");
+       tdb_trace_record(tdb, ret);
+       tdb_trace_end(tdb);
+}
+
+void tdb_trace_1rec(struct tdb_context *tdb, const char *op,
+                   TDB_DATA rec)
+{
+       tdb_trace_start(tdb);
+       tdb_trace_write(tdb, op);
+       tdb_trace_record(tdb, rec);
+       tdb_trace_end(tdb);
+}
+
+void tdb_trace_1rec_ret(struct tdb_context *tdb, const char *op,
+                       TDB_DATA rec, int ret)
+{
+       tdb_trace_start(tdb);
+       tdb_trace_write(tdb, op);
+       tdb_trace_record(tdb, rec);
+       tdb_trace_end_ret(tdb, ret);
+}
+
+void tdb_trace_1rec_retrec(struct tdb_context *tdb, const char *op,
+                          TDB_DATA rec, TDB_DATA ret)
+{
+       tdb_trace_start(tdb);
+       tdb_trace_write(tdb, op);
+       tdb_trace_record(tdb, rec);
+       tdb_trace_write(tdb, " =");
+       tdb_trace_record(tdb, ret);
+       tdb_trace_end(tdb);
+}
+
+void tdb_trace_2rec_flag_ret(struct tdb_context *tdb, const char *op,
+                            TDB_DATA rec1, TDB_DATA rec2, unsigned flag,
+                            int ret)
+{
+       char msg[sizeof(ret) * 4];
+
+       sprintf(msg, " %#x", flag); 
+       tdb_trace_start(tdb);
+       tdb_trace_write(tdb, op);
+       tdb_trace_record(tdb, rec1);
+       tdb_trace_record(tdb, rec2);
+       tdb_trace_write(tdb, msg);
+       tdb_trace_end_ret(tdb, ret);
+}
+
+void tdb_trace_2rec_retrec(struct tdb_context *tdb, const char *op,
+                          TDB_DATA rec1, TDB_DATA rec2, TDB_DATA ret)
+{
+       tdb_trace_start(tdb);
+       tdb_trace_write(tdb, op);
+       tdb_trace_record(tdb, rec1);
+       tdb_trace_record(tdb, rec2);
+       tdb_trace_write(tdb, " =");
+       tdb_trace_record(tdb, ret);
+       tdb_trace_end(tdb);
+}
+#endif
index c460af4e8dd87d0219dab7e5c1a88089488846fd..4836472864006d3cab1f5726553399d7bf4054f3 100644 (file)
@@ -49,6 +49,8 @@
 #endif
 #include "tdb.h"
 
+/* #define TDB_TRACE 1 */
+
 #if HAVE_GETPAGESIZE
 #define getpagesize() 0x2000
 #endif
@@ -86,6 +88,35 @@ typedef uint32_t tdb_off_t;
  * argument. */
 #define TDB_LOG(x) tdb->log.log_fn x
 
+#ifdef TDB_TRACE
+void tdb_trace(struct tdb_context *tdb, const char *op);
+void tdb_trace_open(struct tdb_context *tdb, const char *op,
+                   unsigned hash_size, unsigned tdb_flags, unsigned open_flags);
+void tdb_trace_ret(struct tdb_context *tdb, const char *op, int ret);
+void tdb_trace_retrec(struct tdb_context *tdb, const char *op, TDB_DATA ret);
+void tdb_trace_1rec(struct tdb_context *tdb, const char *op,
+                   TDB_DATA rec);
+void tdb_trace_1rec_ret(struct tdb_context *tdb, const char *op,
+                       TDB_DATA rec, int ret);
+void tdb_trace_1rec_retrec(struct tdb_context *tdb, const char *op,
+                          TDB_DATA rec, TDB_DATA ret);
+void tdb_trace_2rec_flag_ret(struct tdb_context *tdb, const char *op,
+                            TDB_DATA rec1, TDB_DATA rec2, unsigned flag,
+                            int ret);
+void tdb_trace_2rec_retrec(struct tdb_context *tdb, const char *op,
+                          TDB_DATA rec1, TDB_DATA rec2, TDB_DATA ret);
+#else
+#define tdb_trace(tdb, op)
+#define tdb_trace_open(tdb, op, hash_size, tdb_flags, open_flags)
+#define tdb_trace_ret(tdb, op, ret)
+#define tdb_trace_retrec(tdb, op, ret)
+#define tdb_trace_1rec(tdb, op, rec)
+#define tdb_trace_1rec_ret(tdb, op, rec, ret)
+#define tdb_trace_1rec_retrec(tdb, op, rec, ret)
+#define tdb_trace_2rec_flag_ret(tdb, op, rec1, rec2, flag, ret)
+#define tdb_trace_2rec_retrec(tdb, op, rec1, rec2, ret)
+#endif /* !TDB_TRACE */
+
 /* lock offsets */
 #define GLOBAL_LOCK      0
 #define ACTIVE_LOCK      4
@@ -184,7 +215,8 @@ struct tdb_context {
        struct tdb_transaction *transaction;
        int page_size;
        int max_dead_records;
-       bool have_transaction_lock;
+       int have_transaction_lock;
+       int tracefd;
        volatile sig_atomic_t *interrupt_sig_ptr;
 };
 
@@ -212,6 +244,7 @@ int tdb_ofs_read(struct tdb_context *tdb, tdb_off_t offset, tdb_off_t *d);
 int tdb_ofs_write(struct tdb_context *tdb, tdb_off_t offset, tdb_off_t *d);
 int tdb_lock_record(struct tdb_context *tdb, tdb_off_t off);
 int tdb_unlock_record(struct tdb_context *tdb, tdb_off_t off);
+int tdb_transaction_cancel_internal(struct tdb_context *tdb);
 int tdb_rec_read(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec);
 int tdb_rec_write(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec);
 int tdb_do_delete(struct tdb_context *tdb, tdb_off_t rec_ptr, struct list_struct *rec);
diff --git a/ccan/tdb/test/run-nested-traverse.c b/ccan/tdb/test/run-nested-traverse.c
new file mode 100644 (file)
index 0000000..f4a36b6
--- /dev/null
@@ -0,0 +1,71 @@
+#define _XOPEN_SOURCE 500
+#include "tdb/tdb.h"
+#include "tdb/io.c"
+#include "tdb/tdb.c"
+#include "tdb/lock.c"
+#include "tdb/freelist.c"
+#include "tdb/traverse.c"
+#include "tdb/transaction.c"
+#include "tdb/error.c"
+#include "tdb/open.c"
+#include "tap/tap.h"
+#include <stdlib.h>
+#include <stdbool.h>
+#include <err.h>
+
+static bool correct_key(TDB_DATA key)
+{
+       return key.dsize == strlen("hi")
+               && memcmp(key.dptr, "hi", key.dsize) == 0;
+}
+
+static bool correct_data(TDB_DATA data)
+{
+       return data.dsize == strlen("world")
+               && memcmp(data.dptr, "world", data.dsize) == 0;
+}
+
+static int traverse2(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data,
+                    void *p)
+{
+       ok1(correct_key(key));
+       ok1(correct_data(data));
+       return 0;
+}
+
+static int traverse1(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data,
+                    void *p)
+{
+       ok1(correct_key(key));
+       ok1(correct_data(data));
+       ok1(tdb->have_transaction_lock);
+       tdb_traverse(tdb, traverse2, NULL);
+
+       /* That should *not* release the transaction lock! */
+       ok1(tdb->have_transaction_lock);
+       return 0;
+}
+
+int main(int argc, char *argv[])
+{
+       struct tdb_context *tdb;
+       TDB_DATA key, data;
+
+       plan_tests(14);
+       tdb = tdb_open("/tmp/test.tdb", 1024, TDB_CLEAR_IF_FIRST,
+                      O_CREAT|O_TRUNC|O_RDWR, 0600);
+       ok1(tdb);
+
+       /* Tickle bug on appending zero length buffer to zero length buffer. */
+       key.dsize = strlen("hi");
+       key.dptr = (void *)"hi";
+       data.dptr = (void *)"world";
+       data.dsize = strlen("world");
+
+       ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
+       tdb_traverse(tdb, traverse1, NULL);
+       tdb_traverse_read(tdb, traverse1, NULL);
+       tdb_close(tdb);
+
+       return exit_status();
+}
diff --git a/ccan/tdb/test/run-traverse-in-transaction.c b/ccan/tdb/test/run-traverse-in-transaction.c
new file mode 100644 (file)
index 0000000..b184474
--- /dev/null
@@ -0,0 +1,70 @@
+#define _XOPEN_SOURCE 500
+#include "tdb/tdb.h"
+#include "tdb/io.c"
+#include "tdb/tdb.c"
+#include "tdb/lock.c"
+#include "tdb/freelist.c"
+#include "tdb/traverse.c"
+#include "tdb/transaction.c"
+#include "tdb/error.c"
+#include "tdb/open.c"
+#include "tap/tap.h"
+#include <stdlib.h>
+#include <stdbool.h>
+#include <err.h>
+
+static bool correct_key(TDB_DATA key)
+{
+       return key.dsize == strlen("hi")
+               && memcmp(key.dptr, "hi", key.dsize) == 0;
+}
+
+static bool correct_data(TDB_DATA data)
+{
+       return data.dsize == strlen("world")
+               && memcmp(data.dptr, "world", data.dsize) == 0;
+}
+
+static int traverse(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data,
+                    void *p)
+{
+       ok1(correct_key(key));
+       ok1(correct_data(data));
+       return 0;
+}
+
+int main(int argc, char *argv[])
+{
+       struct tdb_context *tdb;
+       TDB_DATA key, data;
+
+       plan_tests(12);
+       tdb = tdb_open("/tmp/test.tdb", 1024, TDB_CLEAR_IF_FIRST,
+                      O_CREAT|O_TRUNC|O_RDWR, 0600);
+       ok1(tdb);
+
+       /* Tickle bug on appending zero length buffer to zero length buffer. */
+       key.dsize = strlen("hi");
+       key.dptr = (void *)"hi";
+       data.dptr = (void *)"world";
+       data.dsize = strlen("world");
+
+       ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
+
+       ok1(tdb_transaction_start(tdb) == 0);
+       ok(tdb->have_transaction_lock, "Transaction lock in transaction");
+       tdb_traverse(tdb, traverse, NULL);
+
+       /* That should *not* release the transaction lock! */
+       ok(tdb->have_transaction_lock, "Transaction lock after traverse");
+       tdb_traverse_read(tdb, traverse, NULL);
+
+       /* That should *not* release the transaction lock! */
+       ok(tdb->have_transaction_lock, "Transaction lock after traverse_read");
+       ok1(tdb_transaction_commit(tdb) == 0);
+       ok(!tdb->have_transaction_lock, "Transaction unlock");
+
+       tdb_close(tdb);
+
+       return exit_status();
+}
diff --git a/ccan/tdb/test/run-zero-append.c b/ccan/tdb/test/run-zero-append.c
new file mode 100644 (file)
index 0000000..287d74c
--- /dev/null
@@ -0,0 +1,37 @@
+#define _XOPEN_SOURCE 500
+#include "tdb/tdb.h"
+#include "tdb/io.c"
+#include "tdb/tdb.c"
+#include "tdb/lock.c"
+#include "tdb/freelist.c"
+#include "tdb/traverse.c"
+#include "tdb/transaction.c"
+#include "tdb/error.c"
+#include "tdb/open.c"
+#include "tap/tap.h"
+#include <stdlib.h>
+#include <err.h>
+
+int main(int argc, char *argv[])
+{
+       struct tdb_context *tdb;
+       TDB_DATA key, data;
+
+       plan_tests(4);
+       tdb = tdb_open(NULL, 1024, TDB_INTERNAL, O_CREAT|O_TRUNC|O_RDWR, 0600);
+       ok1(tdb);
+
+       /* Tickle bug on appending zero length buffer to zero length buffer. */
+       key.dsize = strlen("hi");
+       key.dptr = (void *)"hi";
+       data.dptr = (void *)"world";
+       data.dsize = 0;
+
+       ok1(tdb_append(tdb, key, data) == 0);
+       ok1(tdb_append(tdb, key, data) == 0);
+       data = tdb_fetch(tdb, key);
+       ok1(data.dsize == 0);
+       tdb_close(tdb);
+
+       return exit_status();
+}
diff --git a/ccan/tdb/tools/Makefile b/ccan/tdb/tools/Makefile
new file mode 100644 (file)
index 0000000..d52b9f3
--- /dev/null
@@ -0,0 +1,29 @@
+LDLIBS:=-lccan
+CFLAGS:=-I../../.. -Wall -O3 #-g -pg
+LDFLAGS:=-L../../..
+
+default: replay_trace tdbtorture tdbdump
+
+replay_trace: replay_trace.c keywords.c
+       $(LINK.c) $< $(LOADLIBES) $(LDLIBS) -o $@
+
+keywords.c: keywords.gperf
+       gperf $< > $@
+
+check: replay_trace
+       @rm -f *.reduced_trace
+       @set -e; for f in tests/*.trace.tar.bz2; do             \
+               tar xvfj $$f;                                   \
+               ./replay_trace replay.tdb *.reduced_trace;      \
+               rm -f *.reduced_trace;                          \
+       done
+
+# Usage: make mytest.trace.tar.bz2 TRACEFILES=*.trace
+%.trace.tar.bz2: $(patsubst %.trace,%.reduced_trace,$(wildcard $(TRACEFILES)))
+       tar cvfj $@ $^
+
+%.reduced_trace: %.trace
+       @sed 's/\(^[0-9]* traverse\) .*/\1fn/' < $^ > $@
+
+clean:
+       rm -f replay_trace tdbtorture tdbdump *.o
diff --git a/ccan/tdb/tools/keywords.c b/ccan/tdb/tools/keywords.c
new file mode 100644 (file)
index 0000000..461a61e
--- /dev/null
@@ -0,0 +1,197 @@
+/* ANSI-C code produced by gperf version 3.0.3 */
+/* Command-line: gperf keywords.gperf  */
+/* Computed positions: -k'5,$' */
+
+#if !((' ' == 32) && ('!' == 33) && ('"' == 34) && ('#' == 35) \
+      && ('%' == 37) && ('&' == 38) && ('\'' == 39) && ('(' == 40) \
+      && (')' == 41) && ('*' == 42) && ('+' == 43) && (',' == 44) \
+      && ('-' == 45) && ('.' == 46) && ('/' == 47) && ('0' == 48) \
+      && ('1' == 49) && ('2' == 50) && ('3' == 51) && ('4' == 52) \
+      && ('5' == 53) && ('6' == 54) && ('7' == 55) && ('8' == 56) \
+      && ('9' == 57) && (':' == 58) && (';' == 59) && ('<' == 60) \
+      && ('=' == 61) && ('>' == 62) && ('?' == 63) && ('A' == 65) \
+      && ('B' == 66) && ('C' == 67) && ('D' == 68) && ('E' == 69) \
+      && ('F' == 70) && ('G' == 71) && ('H' == 72) && ('I' == 73) \
+      && ('J' == 74) && ('K' == 75) && ('L' == 76) && ('M' == 77) \
+      && ('N' == 78) && ('O' == 79) && ('P' == 80) && ('Q' == 81) \
+      && ('R' == 82) && ('S' == 83) && ('T' == 84) && ('U' == 85) \
+      && ('V' == 86) && ('W' == 87) && ('X' == 88) && ('Y' == 89) \
+      && ('Z' == 90) && ('[' == 91) && ('\\' == 92) && (']' == 93) \
+      && ('^' == 94) && ('_' == 95) && ('a' == 97) && ('b' == 98) \
+      && ('c' == 99) && ('d' == 100) && ('e' == 101) && ('f' == 102) \
+      && ('g' == 103) && ('h' == 104) && ('i' == 105) && ('j' == 106) \
+      && ('k' == 107) && ('l' == 108) && ('m' == 109) && ('n' == 110) \
+      && ('o' == 111) && ('p' == 112) && ('q' == 113) && ('r' == 114) \
+      && ('s' == 115) && ('t' == 116) && ('u' == 117) && ('v' == 118) \
+      && ('w' == 119) && ('x' == 120) && ('y' == 121) && ('z' == 122) \
+      && ('{' == 123) && ('|' == 124) && ('}' == 125) && ('~' == 126))
+/* The character set is not based on ISO-646.  */
+#error "gperf generated tables don't work with this execution character set. Please report a bug to <bug-gnu-gperf@gnu.org>."
+#endif
+
+#line 1 "keywords.gperf"
+
+#line 4 "keywords.gperf"
+struct op_table {
+       const char *name;
+       enum op_type type;
+       void (*enhance_op)(const char *filename,
+                          struct op op[], unsigned int op_num, char *words[]);
+};
+/* maximum key range = 43, duplicates = 0 */
+
+#ifdef __GNUC__
+__inline
+#else
+#ifdef __cplusplus
+inline
+#endif
+#endif
+static unsigned int
+hash_keyword (register const char *str, register unsigned int len)
+{
+  static const unsigned char asso_values[] =
+    {
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 20, 51, 25,
+       5,  0,  0,  5,  5, 51, 51,  0,  0,  0,
+      20, 51, 20, 51, 51,  0,  5,  0, 51,  0,
+      51,  5, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
+      51, 51, 51, 51, 51, 51
+    };
+  return len + asso_values[(unsigned char)str[4]] + asso_values[(unsigned char)str[len - 1]];
+}
+
+#ifdef __GNUC__
+__inline
+#ifdef __GNUC_STDC_INLINE__
+__attribute__ ((__gnu_inline__))
+#endif
+#endif
+const struct op_table *
+find_keyword (register const char *str, register unsigned int len)
+{
+  enum
+    {
+      TOTAL_KEYWORDS = 33,
+      MIN_WORD_LENGTH = 8,
+      MAX_WORD_LENGTH = 25,
+      MIN_HASH_VALUE = 8,
+      MAX_HASH_VALUE = 50
+    };
+
+  static const struct op_table wordlist[] =
+    {
+      {""}, {""}, {""}, {""}, {""}, {""}, {""}, {""},
+#line 43 "keywords.gperf"
+      {"traverse", OP_TDB_TRAVERSE, op_add_traverse,},
+#line 33 "keywords.gperf"
+      {"tdb_store", OP_TDB_STORE, op_add_store,},
+#line 32 "keywords.gperf"
+      {"tdb_exists", OP_TDB_EXISTS, op_add_key_ret,},
+#line 16 "keywords.gperf"
+      {"tdb_lockall", OP_TDB_LOCKALL, op_add_nothing,},
+#line 36 "keywords.gperf"
+      {"tdb_wipe_all", OP_TDB_WIPE_ALL, op_add_nothing,},
+#line 20 "keywords.gperf"
+      {"tdb_unlockall", OP_TDB_UNLOCKALL, op_add_nothing,},
+#line 47 "keywords.gperf"
+      {"tdb_fetch", OP_TDB_FETCH, op_add_key_data,},
+#line 48 "keywords.gperf"
+      {"tdb_delete", OP_TDB_DELETE, op_add_key_ret,},
+#line 17 "keywords.gperf"
+      {"tdb_lockall_mark", OP_TDB_LOCKALL_MARK, op_add_nothing,},
+#line 45 "keywords.gperf"
+      {"tdb_firstkey", OP_TDB_FIRSTKEY, op_add_key,},
+#line 18 "keywords.gperf"
+      {"tdb_lockall_unmark", OP_TDB_LOCKALL_UNMARK, op_add_nothing,},
+#line 35 "keywords.gperf"
+      {"tdb_get_seqnum", OP_TDB_GET_SEQNUM, op_add_seqnum,},
+#line 19 "keywords.gperf"
+      {"tdb_lockall_nonblock", OP_TDB_LOCKALL_NONBLOCK, op_add_nothing,},
+#line 21 "keywords.gperf"
+      {"tdb_lockall_read", OP_TDB_LOCKALL_READ, op_add_nothing,},
+      {""},
+#line 23 "keywords.gperf"
+      {"tdb_unlockall_read", OP_TDB_UNLOCKALL_READ, op_add_nothing,},
+      {""},
+#line 22 "keywords.gperf"
+      {"tdb_lockall_read_nonblock", OP_TDB_LOCKALL_READ_NONBLOCK, op_add_nothing,},
+#line 42 "keywords.gperf"
+      {"tdb_traverse_end", OP_TDB_TRAVERSE_END, op_analyze_traverse,},
+#line 38 "keywords.gperf"
+      {"tdb_transaction_cancel", OP_TDB_TRANSACTION_CANCEL, op_analyze_transaction,},
+#line 41 "keywords.gperf"
+      {"tdb_traverse_start", OP_TDB_TRAVERSE_START, op_add_traverse_start,},
+      {""},
+#line 44 "keywords.gperf"
+      {"traversefn", OP_TDB_TRAVERSE, op_add_traversefn,},
+#line 37 "keywords.gperf"
+      {"tdb_transaction_start", OP_TDB_TRANSACTION_START, op_add_transaction,},
+#line 39 "keywords.gperf"
+      {"tdb_transaction_commit", OP_TDB_TRANSACTION_COMMIT, op_analyze_transaction,},
+#line 40 "keywords.gperf"
+      {"tdb_traverse_read_start", OP_TDB_TRAVERSE_READ_START, op_add_traverse_start,},
+      {""},
+#line 34 "keywords.gperf"
+      {"tdb_append", OP_TDB_APPEND, op_add_append,},
+#line 46 "keywords.gperf"
+      {"tdb_nextkey", OP_TDB_NEXTKEY, op_add_key_data,},
+      {""},
+#line 24 "keywords.gperf"
+      {"tdb_chainlock", OP_TDB_CHAINLOCK, op_add_chainlock,},
+      {""},
+#line 28 "keywords.gperf"
+      {"tdb_chainunlock", OP_TDB_CHAINUNLOCK, op_analyze_chainlock,},
+#line 31 "keywords.gperf"
+      {"tdb_parse_record", OP_TDB_PARSE_RECORD, op_add_key_ret,},
+      {""},
+#line 26 "keywords.gperf"
+      {"tdb_chainlock_mark", OP_TDB_CHAINLOCK_MARK, op_add_key,},
+      {""},
+#line 27 "keywords.gperf"
+      {"tdb_chainlock_unmark", OP_TDB_CHAINLOCK_UNMARK, op_add_key,},
+      {""},
+#line 25 "keywords.gperf"
+      {"tdb_chainlock_nonblock", OP_TDB_CHAINLOCK_NONBLOCK, op_add_chainlock_ret,},
+#line 29 "keywords.gperf"
+      {"tdb_chainlock_read", OP_TDB_CHAINLOCK_READ, op_add_chainlock,},
+      {""},
+#line 30 "keywords.gperf"
+      {"tdb_chainunlock_read", OP_TDB_CHAINUNLOCK_READ, op_analyze_chainlock,}
+    };
+
+  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)
+    {
+      register int key = hash_keyword (str, len);
+
+      if (key <= MAX_HASH_VALUE && key >= 0)
+        {
+          register const char *s = wordlist[key].name;
+
+          if (*str == *s && !strcmp (str + 1, s + 1))
+            return &wordlist[key];
+        }
+    }
+  return 0;
+}
diff --git a/ccan/tdb/tools/keywords.gperf b/ccan/tdb/tools/keywords.gperf
new file mode 100644 (file)
index 0000000..676b64e
--- /dev/null
@@ -0,0 +1,48 @@
+%{
+%}
+%language=ANSI-C
+struct op_table {
+       const char *name;
+       enum op_type type;
+       void (*enhance_op)(const char *filename,
+                          struct op op[], unsigned int op_num, char *words[]);
+};
+%define hash-function-name hash_keyword
+%define lookup-function-name find_keyword
+%readonly-tables
+%struct-type
+%enum
+%%
+tdb_lockall, OP_TDB_LOCKALL, op_add_nothing,
+tdb_lockall_mark, OP_TDB_LOCKALL_MARK, op_add_nothing,
+tdb_lockall_unmark, OP_TDB_LOCKALL_UNMARK, op_add_nothing,
+tdb_lockall_nonblock, OP_TDB_LOCKALL_NONBLOCK, op_add_nothing,
+tdb_unlockall, OP_TDB_UNLOCKALL, op_add_nothing,
+tdb_lockall_read, OP_TDB_LOCKALL_READ, op_add_nothing,
+tdb_lockall_read_nonblock, OP_TDB_LOCKALL_READ_NONBLOCK, op_add_nothing,
+tdb_unlockall_read, OP_TDB_UNLOCKALL_READ, op_add_nothing,
+tdb_chainlock, OP_TDB_CHAINLOCK, op_add_chainlock,
+tdb_chainlock_nonblock, OP_TDB_CHAINLOCK_NONBLOCK, op_add_chainlock_ret,
+tdb_chainlock_mark, OP_TDB_CHAINLOCK_MARK, op_add_key,
+tdb_chainlock_unmark, OP_TDB_CHAINLOCK_UNMARK, op_add_key,
+tdb_chainunlock, OP_TDB_CHAINUNLOCK, op_analyze_chainlock,
+tdb_chainlock_read, OP_TDB_CHAINLOCK_READ, op_add_chainlock,
+tdb_chainunlock_read, OP_TDB_CHAINUNLOCK_READ, op_analyze_chainlock,
+tdb_parse_record, OP_TDB_PARSE_RECORD, op_add_key_ret,
+tdb_exists, OP_TDB_EXISTS, op_add_key_ret,
+tdb_store, OP_TDB_STORE, op_add_store,
+tdb_append, OP_TDB_APPEND, op_add_append,
+tdb_get_seqnum, OP_TDB_GET_SEQNUM, op_add_seqnum,
+tdb_wipe_all, OP_TDB_WIPE_ALL, op_add_nothing,
+tdb_transaction_start, OP_TDB_TRANSACTION_START, op_add_transaction,
+tdb_transaction_cancel, OP_TDB_TRANSACTION_CANCEL, op_analyze_transaction,
+tdb_transaction_commit, OP_TDB_TRANSACTION_COMMIT, op_analyze_transaction,
+tdb_traverse_read_start, OP_TDB_TRAVERSE_READ_START, op_add_traverse_start,
+tdb_traverse_start, OP_TDB_TRAVERSE_START, op_add_traverse_start,
+tdb_traverse_end, OP_TDB_TRAVERSE_END, op_analyze_traverse,
+traverse, OP_TDB_TRAVERSE, op_add_traverse,
+traversefn, OP_TDB_TRAVERSE, op_add_traversefn,
+tdb_firstkey, OP_TDB_FIRSTKEY, op_add_key,
+tdb_nextkey, OP_TDB_NEXTKEY, op_add_key_data,
+tdb_fetch, OP_TDB_FETCH, op_add_key_data,
+tdb_delete, OP_TDB_DELETE, op_add_key_ret,
diff --git a/ccan/tdb/tools/replay_trace.c b/ccan/tdb/tools/replay_trace.c
new file mode 100644 (file)
index 0000000..67809d8
--- /dev/null
@@ -0,0 +1,1795 @@
+#include <ccan/tdb/tdb.h>
+#include <ccan/grab_file/grab_file.h>
+#include <ccan/hash/hash.h>
+#include <ccan/talloc/talloc.h>
+#include <ccan/str_talloc/str_talloc.h>
+#include <ccan/str/str.h>
+#include <ccan/list/list.h>
+#include <err.h>
+#include <ctype.h>
+#include <string.h>
+#include <unistd.h>
+#include <sys/types.h>
+#include <sys/wait.h>
+#include <sys/time.h>
+#include <errno.h>
+#include <signal.h>
+#include <assert.h>
+#include <fcntl.h>
+
+#define STRINGIFY2(x) #x
+#define STRINGIFY(x) STRINGIFY2(x)
+
+/* Avoid mod by zero */
+static unsigned int total_keys = 1;
+
+/* #define DEBUG_DEPS 1 */
+
+/* Traversals block transactions in the current implementation. */
+#define TRAVERSALS_TAKE_TRANSACTION_LOCK 1
+
+struct pipe {
+       int fd[2];
+};
+static struct pipe *pipes;
+static int backoff_fd = -1;
+
+static void __attribute__((noreturn)) fail(const char *filename,
+                                          unsigned int line,
+                                          const char *fmt, ...)
+{
+       va_list ap;
+
+       va_start(ap, fmt);
+       fprintf(stderr, "%s:%u: FAIL: ", filename, line);
+       vfprintf(stderr, fmt, ap);
+       fprintf(stderr, "\n");
+       va_end(ap);
+       exit(1);
+}
+       
+/* Try or die. */
+#define try(expr, expect)                                              \
+       do {                                                            \
+               int ret = (expr);                                       \
+               if (ret != (expect))                                    \
+                       fail(filename[file], i+1,                       \
+                            STRINGIFY(expr) "= %i", ret);              \
+       } while (0)
+
+/* Try or imitate results. */
+#define unreliable(expr, expect, force, undo)                          \
+       do {                                                            \
+               int ret = expr;                                         \
+               if (ret != expect) {                                    \
+                       fprintf(stderr, "%s:%u: %s gave %i not %i",     \
+                               filename[file], i+1, STRINGIFY(expr),   \
+                               ret, expect);                           \
+                       if (expect == 0)                                \
+                               force;                                  \
+                       else                                            \
+                               undo;                                   \
+               }                                                       \
+       } while (0)
+
+static bool key_eq(TDB_DATA a, TDB_DATA b)
+{
+       if (a.dsize != b.dsize)
+               return false;
+       return memcmp(a.dptr, b.dptr, a.dsize) == 0;
+}
+
+/* This is based on the hash algorithm from gdbm */
+static unsigned int hash_key(TDB_DATA *key)
+{
+       uint32_t value; /* Used to compute the hash value.  */
+       uint32_t   i;   /* Used to cycle through random values. */
+
+       /* Set the initial value from the key size. */
+       for (value = 0x238F13AF ^ key->dsize, i=0; i < key->dsize; i++)
+               value = (value + (key->dptr[i] << (i*5 % 24)));
+
+       return (1103515243 * value + 12345);  
+}
+
+enum op_type {
+       OP_TDB_LOCKALL,
+       OP_TDB_LOCKALL_MARK,
+       OP_TDB_LOCKALL_UNMARK,
+       OP_TDB_LOCKALL_NONBLOCK,
+       OP_TDB_UNLOCKALL,
+       OP_TDB_LOCKALL_READ,
+       OP_TDB_LOCKALL_READ_NONBLOCK,
+       OP_TDB_UNLOCKALL_READ,
+       OP_TDB_CHAINLOCK,
+       OP_TDB_CHAINLOCK_NONBLOCK,
+       OP_TDB_CHAINLOCK_MARK,
+       OP_TDB_CHAINLOCK_UNMARK,
+       OP_TDB_CHAINUNLOCK,
+       OP_TDB_CHAINLOCK_READ,
+       OP_TDB_CHAINUNLOCK_READ,
+       OP_TDB_PARSE_RECORD,
+       OP_TDB_EXISTS,
+       OP_TDB_STORE,
+       OP_TDB_APPEND,
+       OP_TDB_GET_SEQNUM,
+       OP_TDB_WIPE_ALL,
+       OP_TDB_TRANSACTION_START,
+       OP_TDB_TRANSACTION_CANCEL,
+       OP_TDB_TRANSACTION_COMMIT,
+       OP_TDB_TRAVERSE_READ_START,
+       OP_TDB_TRAVERSE_START,
+       OP_TDB_TRAVERSE_END,
+       OP_TDB_TRAVERSE,
+       OP_TDB_TRAVERSE_END_EARLY,
+       OP_TDB_FIRSTKEY,
+       OP_TDB_NEXTKEY,
+       OP_TDB_FETCH,
+       OP_TDB_DELETE,
+};
+
+struct op {
+       unsigned int seqnum;
+       enum op_type type;
+       TDB_DATA key;
+       TDB_DATA data;
+       int ret;
+
+       /* Who is waiting for us? */
+       struct list_head post;
+       /* What are we waiting for? */
+       struct list_head pre;
+
+       /* If I'm part of a group (traverse/transaction) where is
+        * start?  (Otherwise, 0) */
+       unsigned int group_start;
+
+       union {
+               int flag; /* open and store */
+               struct {  /* append */
+                       TDB_DATA pre;
+                       TDB_DATA post;
+               } append;
+               /* transaction/traverse start/chainlock */
+               unsigned int group_len;
+       };
+};
+
+struct op_desc {
+       unsigned int file;
+       unsigned int op_num;
+};
+
+static unsigned char hex_char(const char *filename, unsigned int line, char c)
+{
+       c = toupper(c);
+       if (c >= 'A' && c <= 'F')
+               return c - 'A' + 10;
+       if (c >= '0' && c <= '9')
+               return c - '0';
+       fail(filename, line, "invalid hex character '%c'", c);
+}
+
+/* TDB data is <size>:<%02x>* */
+static TDB_DATA make_tdb_data(const void *ctx,
+                             const char *filename, unsigned int line,
+                             const char *word)
+{
+       TDB_DATA data;
+       unsigned int i;
+       const char *p;
+
+       if (streq(word, "NULL"))
+               return tdb_null;
+
+       data.dsize = atoi(word);
+       data.dptr = talloc_array(ctx, unsigned char, data.dsize);
+       p = strchr(word, ':');
+       if (!p)
+               fail(filename, line, "invalid tdb data '%s'", word);
+       p++;
+       for (i = 0; i < data.dsize; i++)
+               data.dptr[i] = hex_char(filename, line, p[i*2])*16
+                       + hex_char(filename, line, p[i*2+1]);
+
+       return data;
+}
+
+static void add_op(const char *filename, struct op **op, unsigned int i,
+                  unsigned int seqnum, enum op_type type)
+{
+       struct op *new;
+       *op = talloc_realloc(NULL, *op, struct op, i+1);
+       new = (*op) + i;
+       new->type = type;
+       new->seqnum = seqnum;
+       new->ret = 0;
+       new->group_start = 0;
+}
+
+static void op_add_nothing(const char *filename,
+                          struct op op[], unsigned int op_num, char *words[])
+{
+       if (words[2])
+               fail(filename, op_num+1, "Expected no arguments");
+       op[op_num].key = tdb_null;
+}
+
+static void op_add_key(const char *filename,
+                      struct op op[], unsigned int op_num, char *words[])
+{
+       if (words[2] == NULL || words[3])
+               fail(filename, op_num+1, "Expected just a key");
+
+       op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]);
+       total_keys++;
+}
+
+static void op_add_key_ret(const char *filename,
+                          struct op op[], unsigned int op_num, char *words[])
+{
+       if (!words[2] || !words[3] || !words[4] || words[5]
+           || !streq(words[3], "="))
+               fail(filename, op_num+1, "Expected <key> = <ret>");
+       op[op_num].ret = atoi(words[4]);
+       op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]);
+       /* May only be a unique key if it fails */
+       if (op[op_num].ret != 0)
+               total_keys++;
+}
+
+static void op_add_key_data(const char *filename,
+                           struct op op[], unsigned int op_num, char *words[])
+{
+       if (!words[2] || !words[3] || !words[4] || words[5]
+           || !streq(words[3], "="))
+               fail(filename, op_num+1, "Expected <key> = <data>");
+       op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]);
+       op[op_num].data = make_tdb_data(op, filename, op_num+1, words[4]);
+       /* May only be a unique key if it fails */
+       if (!op[op_num].data.dptr)
+               total_keys++;
+}
+
+/* We don't record the keys or data for a traverse, as we don't use them. */
+static void op_add_traverse(const char *filename,
+                           struct op op[], unsigned int op_num, char *words[])
+{
+       if (!words[2] || !words[3] || !words[4] || words[5]
+           || !streq(words[3], "="))
+               fail(filename, op_num+1, "Expected <key> = <data>");
+       op[op_num].key = tdb_null;
+}
+
+/* Full traverse info is useful for debugging, but changing it to
+ * "traversefn" without the data makes the traces *much* smaller! */
+static void op_add_traversefn(const char *filename,
+                           struct op op[], unsigned int op_num, char *words[])
+{
+       if (words[2])
+               fail(filename, op_num+1, "Expected no values");
+       op[op_num].key = tdb_null;
+}
+
+/* <seqnum> tdb_store <rec> <rec> <flag> = <ret> */
+static void op_add_store(const char *filename,
+                        struct op op[], unsigned int op_num, char *words[])
+{
+       if (!words[2] || !words[3] || !words[4] || !words[5] || !words[6]
+           || words[7] || !streq(words[5], "="))
+               fail(filename, op_num+1, "Expect <key> <data> <flag> = <ret>");
+
+       op[op_num].flag = strtoul(words[4], NULL, 0);
+       op[op_num].ret = atoi(words[6]);
+       op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]);
+       op[op_num].data = make_tdb_data(op, filename, op_num+1, words[3]);
+       total_keys++;
+}
+
+/* <seqnum> tdb_append <rec> <rec> = <rec> */
+static void op_add_append(const char *filename,
+                         struct op op[], unsigned int op_num, char *words[])
+{
+       if (!words[2] || !words[3] || !words[4] || !words[5] || words[6]
+           || !streq(words[4], "="))
+               fail(filename, op_num+1, "Expect <key> <data> = <rec>");
+
+       op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]);
+       op[op_num].data = make_tdb_data(op, filename, op_num+1, words[3]);
+
+       op[op_num].append.post
+               = make_tdb_data(op, filename, op_num+1, words[5]);
+
+       /* By subtraction, figure out what previous data was. */
+       op[op_num].append.pre.dptr = op[op_num].append.post.dptr;
+       op[op_num].append.pre.dsize
+               = op[op_num].append.post.dsize - op[op_num].data.dsize;
+       total_keys++;
+}
+
+/* <seqnum> tdb_get_seqnum = <ret> */
+static void op_add_seqnum(const char *filename,
+                         struct op op[], unsigned int op_num, char *words[])
+{
+       if (!words[2] || !words[3] || words[4] || !streq(words[2], "="))
+               fail(filename, op_num+1, "Expect = <ret>");
+
+       op[op_num].key = tdb_null;
+       op[op_num].ret = atoi(words[3]);
+}
+
+static void op_add_traverse_start(const char *filename,
+                                 struct op op[],
+                                 unsigned int op_num, char *words[])
+{
+       if (words[2])
+               fail(filename, op_num+1, "Expect no arguments");
+
+       op[op_num].key = tdb_null;
+       op[op_num].group_len = 0;
+}
+
+static void op_add_transaction(const char *filename, struct op op[],
+                              unsigned int op_num, char *words[])
+{
+       if (words[2])
+               fail(filename, op_num+1, "Expect no arguments");
+
+       op[op_num].key = tdb_null;
+       op[op_num].group_len = 0;
+}
+
+static void op_add_chainlock(const char *filename,
+                            struct op op[], unsigned int op_num, char *words[])
+{
+       if (words[2] == NULL || words[3])
+               fail(filename, op_num+1, "Expected just a key");
+
+       /* A chainlock key isn't a key in the normal sense; it doesn't
+        * have to be in the db at all.  Also, we don't want to hash this op. */
+       op[op_num].data = make_tdb_data(op, filename, op_num+1, words[2]);
+       op[op_num].key = tdb_null;
+       op[op_num].group_len = 0;
+}
+
+static void op_add_chainlock_ret(const char *filename,
+                                struct op op[], unsigned int op_num,
+                                char *words[])
+{
+       if (!words[2] || !words[3] || !words[4] || words[5]
+           || !streq(words[3], "="))
+               fail(filename, op_num+1, "Expected <key> = <ret>");
+       op[op_num].ret = atoi(words[4]);
+       op[op_num].data = make_tdb_data(op, filename, op_num+1, words[2]);
+       op[op_num].key = tdb_null;
+       op[op_num].group_len = 0;
+       total_keys++;
+}
+
+static int op_find_start(struct op op[], unsigned int op_num, enum op_type type)
+{
+       unsigned int i;
+
+       for (i = op_num-1; i > 0; i--) {
+               if (op[i].type == type && !op[i].group_len)
+                       return i;
+       }
+       return 0;
+}
+
+static void op_analyze_transaction(const char *filename,
+                                  struct op op[], unsigned int op_num,
+                                  char *words[])
+{
+       unsigned int start, i;
+
+       op[op_num].key = tdb_null;
+
+       if (words[2])
+               fail(filename, op_num+1, "Expect no arguments");
+
+       start = op_find_start(op, op_num, OP_TDB_TRANSACTION_START);
+       if (!start)
+               fail(filename, op_num+1, "no transaction start found");
+
+       op[start].group_len = op_num - start;
+
+       /* This rolls in nested transactions.  I think that's right. */
+       for (i = start; i <= op_num; i++)
+               op[i].group_start = start;
+}
+
+/* We treat chainlocks a lot like transactions, even though that's overkill */
+static void op_analyze_chainlock(const char *filename,
+                                struct op op[], unsigned int op_num,
+                                char *words[])
+{
+       unsigned int i, start;
+
+       if (words[2] == NULL || words[3])
+               fail(filename, op_num+1, "Expected just a key");
+
+       op[op_num].data = make_tdb_data(op, filename, op_num+1, words[2]);
+       op[op_num].key = tdb_null;
+       total_keys++;
+
+       start = op_find_start(op, op_num, OP_TDB_CHAINLOCK);
+       if (!start)
+               start = op_find_start(op, op_num, OP_TDB_CHAINLOCK_READ);
+       if (!start)
+               fail(filename, op_num+1, "no initial chainlock found");
+
+       /* FIXME: We'd have to do something clever to make this work
+        * vs. deadlock. */
+       if (!key_eq(op[start].data, op[op_num].data))
+               fail(filename, op_num+1, "nested chainlock calls?");
+
+       op[start].group_len = op_num - start;
+       for (i = start; i <= op_num; i++)
+               op[i].group_start = start;
+}
+
+static void op_analyze_traverse(const char *filename,
+                               struct op op[], unsigned int op_num,
+                               char *words[])
+{
+       int i, start;
+
+       op[op_num].key = tdb_null;
+
+       /* = %u means traverse function terminated. */
+       if (words[2]) {
+               if (!streq(words[2], "=") || !words[3] || words[4])
+                       fail(filename, op_num+1, "expect = <num>");
+               op[op_num].ret = atoi(words[3]);
+       } else
+               op[op_num].ret = 0;
+
+       start = op_find_start(op, op_num, OP_TDB_TRAVERSE_START);
+       if (!start)
+               start = op_find_start(op, op_num, OP_TDB_TRAVERSE_READ_START);
+       if (!start)
+               fail(filename, op_num+1, "no traversal start found");
+
+       op[start].group_len = op_num - start;
+
+       /* Don't roll in nested traverse/chainlock */
+       for (i = start; i <= op_num; i++)
+               if (!op[i].group_start)
+                       op[i].group_start = start;
+}
+
+/* Keep -Wmissing-declarations happy: */
+const struct op_table *
+find_keyword (register const char *str, register unsigned int len);
+
+#include "keywords.c"
+
+struct depend {
+       /* We can have more than one */
+       struct list_node pre_list;
+       struct list_node post_list;
+       struct op_desc needs;
+       struct op_desc prereq;
+};
+
+static void check_deps(const char *filename, struct op op[], unsigned int num)
+{
+#ifdef DEBUG_DEPS
+       unsigned int i;
+
+       for (i = 1; i < num; i++)
+               if (!list_empty(&op[i].pre))
+                       fail(filename, i+1, "Still has dependencies");
+#endif
+}
+
+static void dump_pre(char *filename[], struct op *op[],
+                    unsigned int file, unsigned int i)
+{
+       struct depend *dep;
+
+       printf("%s:%u (%u) still waiting for:\n", filename[file], i+1,
+               op[file][i].seqnum);
+       list_for_each(&op[file][i].pre, dep, pre_list)
+               printf("    %s:%u (%u)\n",
+                      filename[dep->prereq.file], dep->prereq.op_num+1,
+                      op[dep->prereq.file][dep->prereq.op_num].seqnum);
+       check_deps(filename[file], op[file], i);
+}
+
+/* We simply read/write pointers, since we all are children. */
+static bool do_pre(struct tdb_context *tdb,
+                  char *filename[], struct op *op[],
+                  unsigned int file, int pre_fd, unsigned int i,
+                  bool backoff)
+{
+       while (!list_empty(&op[file][i].pre)) {
+               struct depend *dep;
+
+#if DEBUG_DEPS
+               printf("%s:%u:waiting for pre\n", filename[file], i+1);
+               fflush(stdout);
+#endif
+               if (backoff)
+                       alarm(2);
+               else
+                       alarm(10);
+               while (read(pre_fd, &dep, sizeof(dep)) != sizeof(dep)) {
+                       if (errno == EINTR) {
+                               if (backoff) {
+                                       struct op_desc desc = { file,i };
+                                       warnx("%s:%u:avoiding deadlock",
+                                             filename[file], i+1);
+                                       if (write(backoff_fd, &desc,
+                                                 sizeof(desc)) != sizeof(desc))
+                                               err(1, "writing backoff_fd");
+                                       return false;
+                               }
+                               dump_pre(filename, op, file, i);
+                               exit(1);
+                       } else
+                               errx(1, "Reading from pipe");
+               }
+               alarm(0);
+
+#if DEBUG_DEPS
+               printf("%s:%u:got pre %u from %s:%u\n", filename[file], i+1,
+                      dep->needs.op_num+1, filename[dep->prereq.file],
+                      dep->prereq.op_num+1);
+               fflush(stdout);
+#endif
+               /* This could be any op, not just this one. */
+               talloc_free(dep);
+       }
+       return true;
+}
+
+static void do_post(char *filename[], struct op *op[],
+                   unsigned int file, unsigned int i)
+{
+       struct depend *dep;
+
+       list_for_each(&op[file][i].post, dep, post_list) {
+#if DEBUG_DEPS
+               printf("%s:%u:sending to file %s:%u\n", filename[file], i+1,
+                      filename[dep->needs.file], dep->needs.op_num+1);
+#endif
+               if (write(pipes[dep->needs.file].fd[1], &dep, sizeof(dep))
+                   != sizeof(dep))
+                       err(1, "%s:%u failed to tell file %s",
+                           filename[file], i+1, filename[dep->needs.file]);
+       }
+}
+
+static int get_len(TDB_DATA key, TDB_DATA data, void *private_data)
+{
+       return data.dsize;
+}
+
+static unsigned run_ops(struct tdb_context *tdb,
+                       int pre_fd,
+                       char *filename[],
+                       struct op *op[],
+                       unsigned int file,
+                       unsigned int start, unsigned int stop,
+                       bool backoff);
+
+struct traverse_info {
+       struct op **op;
+       char **filename;
+       unsigned file;
+       int pre_fd;
+       unsigned int start;
+       unsigned int i;
+};
+
+/* More complex.  Just do whatever's they did at the n'th entry. */
+static int nontrivial_traverse(struct tdb_context *tdb,
+                              TDB_DATA key, TDB_DATA data,
+                              void *_tinfo)
+{
+       struct traverse_info *tinfo = _tinfo;
+       unsigned int trav_len = tinfo->op[tinfo->file][tinfo->start].group_len;
+       bool avoid_deadlock = false;
+
+       if (tinfo->i == tinfo->start + trav_len) {
+               /* This can happen if traverse expects to be empty. */
+               if (trav_len == 1)
+                       return 1;
+               fail(tinfo->filename[tinfo->file], tinfo->start + 1,
+                    "traverse did not terminate");
+       }
+
+       if (tinfo->op[tinfo->file][tinfo->i].type != OP_TDB_TRAVERSE)
+               fail(tinfo->filename[tinfo->file], tinfo->start + 1,
+                    "%s:%u:traverse terminated early");
+
+#if TRAVERSALS_TAKE_TRANSACTION_LOCK
+       avoid_deadlock = true;
+#endif
+
+       /* Run any normal ops. */
+       tinfo->i = run_ops(tdb, tinfo->pre_fd, tinfo->filename, tinfo->op,
+                          tinfo->file, tinfo->i+1, tinfo->start + trav_len,
+                          avoid_deadlock);
+
+       /* We backed off, or we hit OP_TDB_TRAVERSE_END/EARLY. */
+       if (tinfo->op[tinfo->file][tinfo->i].type != OP_TDB_TRAVERSE)
+               return 1;
+
+       return 0;
+}
+
+static unsigned op_traverse(struct tdb_context *tdb,
+                           int pre_fd,
+                           char *filename[],
+                           unsigned int file,
+                           int (*traversefn)(struct tdb_context *,
+                                             tdb_traverse_func, void *),
+                           struct op *op[],
+                           unsigned int start)
+{
+       struct traverse_info tinfo = { op, filename, file, pre_fd,
+                                      start, start+1 };
+
+       traversefn(tdb, nontrivial_traverse, &tinfo);
+
+       /* Traversing in wrong order can have strange effects: eg. if
+        * original traverse went A (delete A), B, we might do B
+        * (delete A).  So if we have ops left over, we do it now. */
+       while (tinfo.i != start + op[file][start].group_len) {
+               if (op[file][tinfo.i].type == OP_TDB_TRAVERSE
+                   || op[file][tinfo.i].type == OP_TDB_TRAVERSE_END_EARLY)
+                       tinfo.i++;
+               else
+                       tinfo.i = run_ops(tdb, pre_fd, filename, op, file,
+                                         tinfo.i,
+                                         start + op[file][start].group_len,
+                                         false);
+       }
+
+       return tinfo.i;
+}
+
+static void break_out(int sig)
+{
+}
+
+static __attribute__((noinline))
+unsigned run_ops(struct tdb_context *tdb,
+                int pre_fd,
+                char *filename[],
+                struct op *op[],
+                unsigned int file,
+                unsigned int start, unsigned int stop,
+                bool backoff)
+{
+       unsigned int i;
+       struct sigaction sa;
+
+       sa.sa_handler = break_out;
+       sa.sa_flags = 0;
+
+       sigaction(SIGALRM, &sa, NULL);
+       for (i = start; i < stop; i++) {
+               if (!do_pre(tdb, filename, op, file, pre_fd, i, backoff))
+                       return i;
+
+               switch (op[file][i].type) {
+               case OP_TDB_LOCKALL:
+                       try(tdb_lockall(tdb), op[file][i].ret);
+                       break;
+               case OP_TDB_LOCKALL_MARK:
+                       try(tdb_lockall_mark(tdb), op[file][i].ret);
+                       break;
+               case OP_TDB_LOCKALL_UNMARK:
+                       try(tdb_lockall_unmark(tdb), op[file][i].ret);
+                       break;
+               case OP_TDB_LOCKALL_NONBLOCK:
+                       unreliable(tdb_lockall_nonblock(tdb), op[file][i].ret,
+                                  tdb_lockall(tdb), tdb_unlockall(tdb));
+                       break;
+               case OP_TDB_UNLOCKALL:
+                       try(tdb_unlockall(tdb), op[file][i].ret);
+                       break;
+               case OP_TDB_LOCKALL_READ:
+                       try(tdb_lockall_read(tdb), op[file][i].ret);
+                       break;
+               case OP_TDB_LOCKALL_READ_NONBLOCK:
+                       unreliable(tdb_lockall_read_nonblock(tdb),
+                                  op[file][i].ret,
+                                  tdb_lockall_read(tdb),
+                                  tdb_unlockall_read(tdb));
+                       break;
+               case OP_TDB_UNLOCKALL_READ:
+                       try(tdb_unlockall_read(tdb), op[file][i].ret);
+                       break;
+               case OP_TDB_CHAINLOCK:
+                       try(tdb_chainlock(tdb, op[file][i].key),
+                           op[file][i].ret);
+                       break;
+               case OP_TDB_CHAINLOCK_NONBLOCK:
+                       unreliable(tdb_chainlock_nonblock(tdb, op[file][i].key),
+                                  op[file][i].ret,
+                                  tdb_chainlock(tdb, op[file][i].key),
+                                  tdb_chainunlock(tdb, op[file][i].key));
+                       break;
+               case OP_TDB_CHAINLOCK_MARK:
+                       try(tdb_chainlock_mark(tdb, op[file][i].key),
+                           op[file][i].ret);
+                       break;
+               case OP_TDB_CHAINLOCK_UNMARK:
+                       try(tdb_chainlock_unmark(tdb, op[file][i].key),
+                           op[file][i].ret);
+                       break;
+               case OP_TDB_CHAINUNLOCK:
+                       try(tdb_chainunlock(tdb, op[file][i].key),
+                           op[file][i].ret);
+                       break;
+               case OP_TDB_CHAINLOCK_READ:
+                       try(tdb_chainlock_read(tdb, op[file][i].key),
+                           op[file][i].ret);
+                       break;
+               case OP_TDB_CHAINUNLOCK_READ:
+                       try(tdb_chainunlock_read(tdb, op[file][i].key),
+                           op[file][i].ret);
+                       break;
+               case OP_TDB_PARSE_RECORD:
+                       try(tdb_parse_record(tdb, op[file][i].key, get_len,
+                                            NULL),
+                           op[file][i].ret);
+                       break;
+               case OP_TDB_EXISTS:
+                       try(tdb_exists(tdb, op[file][i].key), op[file][i].ret);
+                       break;
+               case OP_TDB_STORE:
+                       try(tdb_store(tdb, op[file][i].key, op[file][i].data,
+                                     op[file][i].flag),
+                           op[file][i].ret);
+                       break;
+               case OP_TDB_APPEND:
+                       try(tdb_append(tdb, op[file][i].key, op[file][i].data),
+                           op[file][i].ret);
+                       break;
+               case OP_TDB_GET_SEQNUM:
+                       try(tdb_get_seqnum(tdb), op[file][i].ret);
+                       break;
+               case OP_TDB_WIPE_ALL:
+                       try(tdb_wipe_all(tdb), op[file][i].ret);
+                       break;
+               case OP_TDB_TRANSACTION_START:
+                       try(tdb_transaction_start(tdb), op[file][i].ret);
+                       break;
+               case OP_TDB_TRANSACTION_CANCEL:
+                       try(tdb_transaction_cancel(tdb), op[file][i].ret);
+                       break;
+               case OP_TDB_TRANSACTION_COMMIT:
+                       try(tdb_transaction_commit(tdb), op[file][i].ret);
+                       break;
+               case OP_TDB_TRAVERSE_READ_START:
+                       i = op_traverse(tdb, pre_fd, filename, file,
+                                       tdb_traverse_read, op, i);
+                       break;
+               case OP_TDB_TRAVERSE_START:
+                       i = op_traverse(tdb, pre_fd, filename, file,
+                                       tdb_traverse, op, i);
+                       break;
+               case OP_TDB_TRAVERSE:
+               case OP_TDB_TRAVERSE_END_EARLY:
+                       /* Terminate: we're in a traverse, and we've
+                        * done our ops. */
+                       return i;
+               case OP_TDB_TRAVERSE_END:
+                       fail(filename[file], i+1, "unexpected end traverse");
+               /* FIXME: These must be treated like traverse. */
+               case OP_TDB_FIRSTKEY:
+                       if (!key_eq(tdb_firstkey(tdb), op[file][i].data))
+                               fail(filename[file], i+1, "bad firstkey");
+                       break;
+               case OP_TDB_NEXTKEY:
+                       if (!key_eq(tdb_nextkey(tdb, op[file][i].key),
+                                   op[file][i].data))
+                               fail(filename[file], i+1, "bad nextkey");
+                       break;
+               case OP_TDB_FETCH: {
+                       TDB_DATA f = tdb_fetch(tdb, op[file][i].key);
+                       if (!key_eq(f, op[file][i].data))
+                               fail(filename[file], i+1, "bad fetch %u",
+                                    f.dsize);
+                       break;
+               }
+               case OP_TDB_DELETE:
+                       try(tdb_delete(tdb, op[file][i].key), op[file][i].ret);
+                       break;
+               }
+               do_post(filename, op, file, i);
+       }
+       return i;
+}
+
+/* tdbtorture, in particular, can do a tdb_close with a transaction in
+ * progress. */
+static struct op *maybe_cancel_transaction(const char *filename,
+                                          struct op *op, unsigned int *num)
+{
+       unsigned int start = op_find_start(op, *num, OP_TDB_TRANSACTION_START);
+
+       if (start) {
+               char *words[] = { "<unknown>", "tdb_close", NULL };
+               add_op(filename, &op, *num, op[start].seqnum,
+                      OP_TDB_TRANSACTION_CANCEL);
+               op_analyze_transaction(filename, op, *num, words);
+               (*num)++;
+       }
+       return op;
+}
+
+static struct op *load_tracefile(const char *filename, unsigned int *num,
+                                unsigned int *hashsize,
+                                unsigned int *tdb_flags,
+                                unsigned int *open_flags)
+{
+       unsigned int i;
+       struct op *op = talloc_array(NULL, struct op, 1);
+       char **words;
+       char **lines;
+       char *file;
+
+       file = grab_file(NULL, filename, NULL);
+       if (!file)
+               err(1, "Reading %s", filename);
+
+       lines = strsplit(file, file, "\n", NULL);
+       if (!lines[0])
+               errx(1, "%s is empty", filename);
+
+       words = strsplit(lines, lines[0], " ", NULL);
+       if (!streq(words[1], "tdb_open"))
+               fail(filename, 1, "does not start with tdb_open");
+
+       *hashsize = atoi(words[2]);
+       *tdb_flags = strtoul(words[3], NULL, 0);
+       *open_flags = strtoul(words[4], NULL, 0);
+
+       for (i = 1; lines[i]; i++) {
+               const struct op_table *opt;
+
+               words = strsplit(lines, lines[i], " ", NULL);
+               if (!words[0] || !words[1])
+                       fail(filename, i+1, "Expected seqnum number and op");
+              
+               opt = find_keyword(words[1], strlen(words[1]));
+               if (!opt) {
+                       if (streq(words[1], "tdb_close")) {
+                               if (lines[i+1])
+                                       fail(filename, i+2,
+                                            "lines after tdb_close");
+                               *num = i;
+                               talloc_free(lines);
+                               return maybe_cancel_transaction(filename,
+                                                               op, num);
+                       }
+                       fail(filename, i+1, "Unknown operation '%s'", words[1]);
+               }
+
+               add_op(filename, &op, i, atoi(words[0]), opt->type);
+               opt->enhance_op(filename, op, i, words);
+       }
+
+       fprintf(stderr, "%s:%u:last operation is not tdb_close: incomplete?",
+             filename, i);
+       talloc_free(lines);
+       *num = i - 1;
+       return maybe_cancel_transaction(filename, op, num);
+}
+
+/* We remember all the keys we've ever seen, and who has them. */
+struct keyinfo {
+       TDB_DATA key;
+       unsigned int num_users;
+       struct op_desc *user;
+};
+
+static const TDB_DATA must_not_exist;
+static const TDB_DATA must_exist;
+static const TDB_DATA not_exists_or_empty;
+
+/* NULL means doesn't care if it exists or not, &must_exist means
+ * it must exist but we don't care what, &must_not_exist means it must
+ * not exist, otherwise the data it needs. */
+static const TDB_DATA *needs(const struct op *op)
+{
+       switch (op->type) {
+       /* FIXME: Pull forward deps, since we can deadlock */
+       case OP_TDB_CHAINLOCK:
+       case OP_TDB_CHAINLOCK_NONBLOCK:
+       case OP_TDB_CHAINLOCK_MARK:
+       case OP_TDB_CHAINLOCK_UNMARK:
+       case OP_TDB_CHAINUNLOCK:
+       case OP_TDB_CHAINLOCK_READ:
+       case OP_TDB_CHAINUNLOCK_READ:
+               return NULL;
+
+       case OP_TDB_APPEND:
+               if (op->append.pre.dsize == 0)
+                       return &not_exists_or_empty;
+               return &op->append.pre;
+
+       case OP_TDB_STORE:
+               if (op->flag == TDB_INSERT) {
+                       if (op->ret < 0)
+                               return &must_exist;
+                       else
+                               return &must_not_exist;
+               } else if (op->flag == TDB_MODIFY) {
+                       if (op->ret < 0)
+                               return &must_not_exist;
+                       else
+                               return &must_exist;
+               }
+               /* No flags?  Don't care */
+               return NULL;
+
+       case OP_TDB_EXISTS:
+               if (op->ret == 1)
+                       return &must_exist;
+               else
+                       return &must_not_exist;
+
+       case OP_TDB_PARSE_RECORD:
+               if (op->ret < 0)
+                       return &must_not_exist;
+               return &must_exist;
+
+       /* FIXME: handle these. */
+       case OP_TDB_WIPE_ALL:
+       case OP_TDB_FIRSTKEY:
+       case OP_TDB_NEXTKEY:
+       case OP_TDB_GET_SEQNUM:
+       case OP_TDB_TRAVERSE:
+       case OP_TDB_TRANSACTION_COMMIT:
+       case OP_TDB_TRANSACTION_CANCEL:
+       case OP_TDB_TRANSACTION_START:
+               return NULL;
+
+       case OP_TDB_FETCH:
+               if (!op->data.dptr)
+                       return &must_not_exist;
+               return &op->data;
+
+       case OP_TDB_DELETE:
+               if (op->ret < 0)
+                       return &must_not_exist;
+               return &must_exist;
+
+       default:
+               errx(1, "Unexpected op type %i", op->type);
+       }
+       
+}
+
+static bool starts_transaction(const struct op *op)
+{
+       return op->type == OP_TDB_TRANSACTION_START;
+}
+
+static bool in_transaction(const struct op op[], unsigned int i)
+{
+       return op[i].group_start && starts_transaction(&op[op[i].group_start]);
+}
+
+static bool successful_transaction(const struct op *op)
+{
+       return starts_transaction(op)
+               && op[op->group_len].type == OP_TDB_TRANSACTION_COMMIT;
+}
+
+static bool starts_traverse(const struct op *op)
+{
+       return op->type == OP_TDB_TRAVERSE_START
+               || op->type == OP_TDB_TRAVERSE_READ_START;
+}
+
+static bool in_traverse(const struct op op[], unsigned int i)
+{
+       return op[i].group_start && starts_traverse(&op[op[i].group_start]);
+}
+
+static bool starts_chainlock(const struct op *op)
+{
+       return op->type == OP_TDB_CHAINLOCK_READ
+               || op->type == OP_TDB_CHAINLOCK;
+}
+
+static bool in_chainlock(const struct op op[], unsigned int i)
+{
+       return op[i].group_start && starts_chainlock(&op[op[i].group_start]);
+}
+
+/* What's the data after this op?  pre if nothing changed. */
+static const TDB_DATA *gives(const TDB_DATA *key, const TDB_DATA *pre,
+                            const struct op *op)
+{
+       if (starts_transaction(op) || starts_chainlock(op)) {
+               unsigned int i;
+
+               /* Cancelled transactions don't change anything. */
+               if (op[op->group_len].type == OP_TDB_TRANSACTION_CANCEL)
+                       return pre;
+               assert(op[op->group_len].type == OP_TDB_TRANSACTION_COMMIT
+                      || op[op->group_len].type == OP_TDB_CHAINUNLOCK_READ
+                      || op[op->group_len].type == OP_TDB_CHAINUNLOCK);
+
+               for (i = 1; i < op->group_len; i++) {
+                       /* This skips nested transactions, too */
+                       if (key_eq(op[i].key, *key))
+                               pre = gives(key, pre, &op[i]);
+               }
+               return pre;
+       }
+
+       /* Failed ops don't change state of db. */
+       if (op->ret < 0)
+               return pre;
+
+       if (op->type == OP_TDB_DELETE || op->type == OP_TDB_WIPE_ALL)
+               return &tdb_null;
+
+       if (op->type == OP_TDB_APPEND)
+               return &op->append.post;
+
+       if (op->type == OP_TDB_STORE)
+               return &op->data;
+
+       return pre;
+}
+
+static struct keyinfo *hash_ops(struct op *op[], unsigned int num_ops[],
+                               unsigned int num)
+{
+       unsigned int i, j, h;
+       struct keyinfo *hash;
+
+       hash = talloc_zero_array(op[0], struct keyinfo, total_keys*2);
+       for (i = 0; i < num; i++) {
+               for (j = 1; j < num_ops[i]; j++) {
+                       /* We can't do this on allocation, due to realloc. */
+                       list_head_init(&op[i][j].post);
+                       list_head_init(&op[i][j].pre);
+
+                       if (!op[i][j].key.dptr)
+                               continue;
+
+                       h = hash_key(&op[i][j].key) % (total_keys * 2);
+                       while (!key_eq(hash[h].key, op[i][j].key)) {
+                               if (!hash[h].key.dptr) {
+                                       hash[h].key = op[i][j].key;
+                                       break;
+                               }
+                               h = (h + 1) % (total_keys * 2);
+                       }
+                       /* Might as well save some memory if we can. */
+                       if (op[i][j].key.dptr != hash[h].key.dptr) {
+                               talloc_free(op[i][j].key.dptr);
+                               op[i][j].key.dptr = hash[h].key.dptr;
+                       }
+                       hash[h].user = talloc_realloc(hash, hash[h].user,
+                                                    struct op_desc,
+                                                    hash[h].num_users+1);
+
+                       /* If it's in a transaction, it's the transaction which
+                        * matters from an analysis POV. */
+                       if (in_transaction(op[i], j)
+                           || in_chainlock(op[i], j)) {
+                               unsigned start = op[i][j].group_start;
+
+                               /* Don't include twice. */
+                               if (hash[h].num_users
+                                   && hash[h].user[hash[h].num_users-1].file
+                                       == i
+                                   && hash[h].user[hash[h].num_users-1].op_num
+                                       == start)
+                                       continue;
+
+                               hash[h].user[hash[h].num_users].op_num = start;
+                       } else
+                               hash[h].user[hash[h].num_users].op_num = j;
+                       hash[h].user[hash[h].num_users].file = i;
+                       hash[h].num_users++;
+               }
+       }
+
+       return hash;
+}
+
+static bool satisfies(const TDB_DATA *key, const TDB_DATA *data,
+                     const struct op *op)
+{
+       const TDB_DATA *need = NULL;
+
+       if (starts_transaction(op) || starts_chainlock(op)) {
+               unsigned int i;
+
+               /* Look through for an op in this transaction which
+                * needs this key. */
+               for (i = 1; i < op->group_len; i++) {
+                       if (key_eq(op[i].key, *key)) {
+                               need = needs(&op[i]);
+                               /* tdb_exists() is special: there might be
+                                * something in the transaction with more
+                                * specific requirements.  Other ops don't have
+                                * specific requirements (eg. store or delete),
+                                * but they change the value so we can't get
+                                * more information from future ops. */
+                               if (op[i].type != OP_TDB_EXISTS)
+                                       break;
+                       }
+               }
+       } else
+               need = needs(op);
+
+       /* Don't need anything?  Cool. */
+       if (!need)
+               return true;
+
+       /* This should be tdb_null or a real value. */
+       assert(data != &must_exist);
+       assert(data != &must_not_exist);
+       assert(data != &not_exists_or_empty);
+
+       /* Must not exist?  data must not exist. */
+       if (need == &must_not_exist)
+               return data == &tdb_null;
+
+       /* Must exist? */
+       if (need == &must_exist)
+               return data != &tdb_null;
+
+       /* Either noexist or empty. */
+       if (need == &not_exists_or_empty)
+               return data->dsize == 0;
+
+       /* Needs something specific. */
+       return key_eq(*data, *need);
+}
+
+static void move_to_front(struct op_desc res[], unsigned off, unsigned elem)
+{
+       if (elem != off) {
+               struct op_desc tmp = res[elem];
+               memmove(res + off + 1, res + off, (elem - off)*sizeof(res[0]));
+               res[off] = tmp;
+       }
+}
+
+static void restore_to_pos(struct op_desc res[], unsigned off, unsigned elem)
+{
+       if (elem != off) {
+               struct op_desc tmp = res[off];
+               memmove(res + off, res + off + 1, (elem - off)*sizeof(res[0]));
+               res[elem] = tmp;
+       }
+}
+
+static bool sort_deps(char *filename[], struct op *op[],
+                     struct op_desc res[],
+                     unsigned off, unsigned num,
+                     const TDB_DATA *key, const TDB_DATA *data,
+                     unsigned num_files, unsigned fuzz)
+{
+       unsigned int i, files_done;
+       struct op *this_op;
+       bool done[num_files];
+
+       /* None left?  We're sorted. */
+       if (off == num)
+               return true;
+
+       /* Does this make sequence number go backwards?  Allow a little fuzz. */
+       if (off > 0) {
+               int seqnum1 = op[res[off-1].file][res[off-1].op_num].seqnum;
+               int seqnum2 = op[res[off].file][res[off].op_num].seqnum;
+
+               if (seqnum1 - seqnum2 > (int)fuzz) {
+#if DEBUG_DEPS
+                       printf("Seqnum jump too far (%u -> %u)\n",
+                              seqnum1, seqnum2);
+#endif
+                       return false;
+               }
+       }
+
+       memset(done, 0, sizeof(done));
+
+       /* Since ops within a trace file are ordered, we just need to figure
+        * out which file to try next.  Since we don't take into account
+        * inter-key relationships (which exist by virtue of trace file order),
+        * we minimize the chance of harm by trying to keep in seqnum order. */
+       for (files_done = 0, i = off; i < num && files_done < num_files; i++) {
+               if (done[res[i].file])
+                       continue;
+
+               this_op = &op[res[i].file][res[i].op_num];
+
+               /* Is what we have good enough for this op? */
+               if (satisfies(key, data, this_op)) {
+                       move_to_front(res, off, i);
+                       if (sort_deps(filename, op, res, off+1, num,
+                                     key, gives(key, data, this_op),
+                                     num_files, fuzz))
+                               return true;
+                       restore_to_pos(res, off, i);
+               }
+               done[res[i].file] = true;
+               files_done++;
+       }
+
+       /* No combination worked. */
+       return false;
+}
+
+static void check_dep_sorting(struct op_desc user[], unsigned num_users,
+                             unsigned num_files)
+{
+#if DEBUG_DEPS
+       unsigned int i;
+       unsigned minima[num_files];
+
+       memset(minima, 0, sizeof(minima));
+       for (i = 0; i < num_users; i++) {
+               assert(minima[user[i].file] < user[i].op_num);
+               minima[user[i].file] = user[i].op_num;
+       }
+#endif
+}
+
+/* All these ops happen on the same key.  Which comes first?
+ *
+ * This can happen both because read ops or failed write ops don't
+ * change sequence number, and also due to race since we access the
+ * number unlocked (the race can cause less detectable ordering problems,
+ * in which case we'll deadlock and report: fix manually in that case).
+ */
+static void figure_deps(char *filename[], struct op *op[],
+                       const TDB_DATA *key, struct op_desc user[],
+                       unsigned num_users, unsigned num_files)
+{
+       /* We assume database starts empty. */
+       const struct TDB_DATA *data = &tdb_null;
+       unsigned int fuzz;
+
+       /* We prefer to keep strict seqnum order if possible: it's the
+        * most likely.  We get more lax if that fails. */
+       for (fuzz = 0; fuzz < 100; fuzz = (fuzz + 1)*2) {
+               if (sort_deps(filename, op, user, 0, num_users, key, data,
+                             num_files, fuzz))
+                       break;
+       }
+
+       if (fuzz >= 100)
+               fail(filename[user[0].file], user[0].op_num+1,
+                    "Could not resolve inter-dependencies");
+
+       check_dep_sorting(user, num_users, num_files);
+}
+
+static void sort_ops(struct keyinfo hash[], char *filename[], struct op *op[],
+                    unsigned int num)
+{
+       unsigned int h;
+
+       /* Gcc nexted function extension.  How cool is this? */
+       int compare_seqnum(const void *_a, const void *_b)
+       {
+               const struct op_desc *a = _a, *b = _b;
+
+               /* First, maintain order within any trace file. */
+               if (a->file == b->file)
+                       return a->op_num - b->op_num;
+
+               /* Otherwise, arrange by seqnum order. */
+               if (op[a->file][a->op_num].seqnum !=
+                   op[b->file][b->op_num].seqnum)
+                       return op[a->file][a->op_num].seqnum
+                               - op[b->file][b->op_num].seqnum;
+
+               /* Cancelled transactions are assumed to happen first. */
+               if (starts_transaction(&op[a->file][a->op_num])
+                   && !successful_transaction(&op[a->file][a->op_num]))
+                       return -1;
+               if (starts_transaction(&op[b->file][b->op_num])
+                   && !successful_transaction(&op[b->file][b->op_num]))
+                       return 1;
+
+               /* No idea. */
+               return 0;
+       }
+
+       /* Now sort into seqnum order. */
+       for (h = 0; h < total_keys * 2; h++) {
+               struct op_desc *user = hash[h].user;
+
+               qsort(user, hash[h].num_users, sizeof(user[0]), compare_seqnum);
+               figure_deps(filename, op, &hash[h].key, user, hash[h].num_users,
+                           num);
+       }
+}
+
+static int destroy_depend(struct depend *dep)
+{
+       list_del(&dep->pre_list);
+       list_del(&dep->post_list);
+       return 0;
+}
+
+static void add_dependency(void *ctx,
+                          struct op *op[],
+                          char *filename[],
+                          const struct op_desc *needs,
+                          const struct op_desc *prereq)
+{
+       struct depend *dep;
+
+       /* We don't depend on ourselves. */
+       if (needs->file == prereq->file) {
+               assert(prereq->op_num < needs->op_num);
+               return;
+       }
+
+#if DEBUG_DEPS
+       printf("%s:%u: depends on %s:%u\n",
+              filename[needs->file], needs->op_num+1,
+              filename[prereq->file], prereq->op_num+1);
+#endif
+
+       dep = talloc(ctx, struct depend);
+       dep->needs = *needs;
+       dep->prereq = *prereq;
+
+#if TRAVERSALS_TAKE_TRANSACTION_LOCK
+       /* If something in a traverse depends on something in another
+        * traverse/transaction, it creates a dependency between the
+        * two groups. */
+       if ((in_traverse(op[prereq->file], prereq->op_num)
+            && (starts_transaction(&op[needs->file][needs->op_num])
+                || starts_traverse(&op[needs->file][needs->op_num])))
+           || (in_traverse(op[needs->file], needs->op_num)
+               && (starts_transaction(&op[prereq->file][prereq->op_num])
+                   || starts_traverse(&op[prereq->file][prereq->op_num])))) {
+               unsigned int start;
+
+               /* We are satisfied by end of group. */
+               start = op[prereq->file][prereq->op_num].group_start;
+               dep->prereq.op_num = start + op[prereq->file][start].group_len;
+               /* And we need that done by start of our group. */
+               dep->needs.op_num = op[needs->file][needs->op_num].group_start;
+       }
+
+       /* There is also this case:
+        *  <traverse> <read foo> ...
+        *  <transaction> ... </transaction> <create foo>
+        * Where if we start the traverse then wait, we could block
+        * the transaction and deadlock.
+        *
+        * We try to address this by ensuring that where seqnum indicates it's
+        * possible, we wait for <create foo> before *starting* traverse.
+        */
+       else if (in_traverse(op[needs->file], needs->op_num)) {
+               struct op *need = &op[needs->file][needs->op_num];
+               if (op[needs->file][need->group_start].seqnum >
+                   op[prereq->file][prereq->op_num].seqnum) {
+                       dep->needs.op_num = need->group_start;
+               }
+       }
+#endif
+
+       /* If you depend on a transaction or chainlock, you actually
+        * depend on it ending. */
+       if (starts_transaction(&op[prereq->file][dep->prereq.op_num])
+           || starts_chainlock(&op[prereq->file][dep->prereq.op_num])) {
+               dep->prereq.op_num
+                       += op[dep->prereq.file][dep->prereq.op_num].group_len;
+#if DEBUG_DEPS
+               printf("-> Actually end of transaction %s:%u\n",
+                      filename[dep->prereq->file], dep->prereq->op_num+1);
+#endif
+       } else
+               /* We should never create a dependency from middle of
+                * a transaction. */
+               assert(!in_transaction(op[prereq->file], dep->prereq.op_num)
+                      || op[prereq->file][dep->prereq.op_num].type
+                      == OP_TDB_TRANSACTION_COMMIT
+                      || op[prereq->file][dep->prereq.op_num].type
+                      == OP_TDB_TRANSACTION_CANCEL);
+
+       list_add(&op[dep->prereq.file][dep->prereq.op_num].post,
+                &dep->post_list);
+       list_add(&op[dep->needs.file][dep->needs.op_num].pre,
+                &dep->pre_list);
+       talloc_set_destructor(dep, destroy_depend);
+}
+
+static bool changes_db(const TDB_DATA *key, const struct op *op)
+{
+       return gives(key, NULL, op) != NULL;
+}
+
+static void depend_on_previous(struct op *op[],
+                              char *filename[],
+                              unsigned int num,
+                              struct op_desc user[],
+                              unsigned int i,
+                              int prev)
+{
+       bool deps[num];
+       int j;
+
+       if (i == 0)
+               return;
+
+       if (prev == i - 1) {
+               /* Just depend on previous. */
+               add_dependency(NULL, op, filename, &user[i], &user[prev]);
+               return;
+       }
+
+       /* We have to wait for the readers.  Find last one in *each* file. */
+       memset(deps, 0, sizeof(deps));
+       deps[user[i].file] = true;
+       for (j = i - 1; j > prev; j--) {
+               if (!deps[user[j].file]) {
+                       add_dependency(NULL, op, filename, &user[i], &user[j]);
+                       deps[user[j].file] = true;
+               }
+       }
+}
+
+/* This is simple, but not complete.  We don't take into account
+ * indirect dependencies. */
+static void optimize_dependencies(struct op *op[], unsigned int num_ops[],
+                                 unsigned int num)
+{
+       unsigned int i, j;
+
+       /* There can only be one real dependency on each file */
+       for (i = 0; i < num; i++) {
+               for (j = 1; j < num_ops[i]; j++) {
+                       struct depend *dep, *next;
+                       struct depend *prev[num];
+
+                       memset(prev, 0, sizeof(prev));
+
+                       list_for_each_safe(&op[i][j].pre, dep, next, pre_list) {
+                               if (!prev[dep->prereq.file]) {
+                                       prev[dep->prereq.file] = dep;
+                                       continue;
+                               }
+                               if (prev[dep->prereq.file]->prereq.op_num
+                                   < dep->prereq.op_num) {
+                                       talloc_free(prev[dep->prereq.file]);
+                                       prev[dep->prereq.file] = dep;
+                               } else
+                                       talloc_free(dep);
+                       }
+               }
+       }
+
+       for (i = 0; i < num; i++) {
+               int deps[num];
+
+               for (j = 0; j < num; j++)
+                       deps[j] = -1;
+
+               for (j = 1; j < num_ops[i]; j++) {
+                       struct depend *dep, *next;
+
+                       list_for_each_safe(&op[i][j].pre, dep, next, pre_list) {
+                               if (deps[dep->prereq.file]
+                                   >= (int)dep->prereq.op_num)
+                                       talloc_free(dep);
+                               else
+                                       deps[dep->prereq.file]
+                                               = dep->prereq.op_num;
+                       }
+               }
+       }
+}
+
+#if TRAVERSALS_TAKE_TRANSACTION_LOCK
+/* Force an order among the traversals, so they don't deadlock (as much) */
+static void make_traverse_depends(char *filename[],
+                                 struct op *op[], unsigned int num_ops[],
+                                 unsigned int num)
+{
+       unsigned int i, num_traversals = 0;
+       int j;
+       struct op_desc *desc;
+
+       /* Sort by which one runs first. */
+       int compare_traverse_desc(const void *_a, const void *_b)
+       {
+               const struct op_desc *da = _a, *db = _b;
+               const struct op *a = &op[da->file][da->op_num],
+                       *b = &op[db->file][db->op_num];
+
+               if (a->seqnum != b->seqnum)
+                       return a->seqnum - b->seqnum;
+
+               /* If they have same seqnum, it means one didn't make any
+                * changes.  Thus sort by end in that case. */
+               return a[a->group_len].seqnum - b[b->group_len].seqnum;
+       }
+
+       desc = talloc_array(NULL, struct op_desc, 1);
+
+       /* Count them. */
+       for (i = 0; i < num; i++) {
+               for (j = 1; j < num_ops[i]; j++) {
+                       /* Traverse start (ignore those in
+                        * transactions; they're already covered by
+                        * transaction dependencies). */
+                       if (starts_traverse(&op[i][j])
+                           && !in_transaction(op[i], j)) {
+                               desc = talloc_realloc(NULL, desc,
+                                                     struct op_desc,
+                                                     num_traversals+1);
+                               desc[num_traversals].file = i;
+                               desc[num_traversals].op_num = j;
+                               num_traversals++;
+                       }
+               }
+       }
+       qsort(desc, num_traversals, sizeof(desc[0]), compare_traverse_desc);
+
+       for (i = 1; i < num_traversals; i++) {
+               const struct op *prev = &op[desc[i-1].file][desc[i-1].op_num];
+               const struct op *curr = &op[desc[i].file][desc[i].op_num];
+
+               /* Read traverses don't depend on each other (read lock). */
+               if (prev->type == OP_TDB_TRAVERSE_READ_START
+                   && curr->type == OP_TDB_TRAVERSE_READ_START)
+                       continue;
+
+               /* Only make dependency if it's clear. */
+               if (compare_traverse_desc(&desc[i], &desc[i-1])) {
+                       /* i depends on end of traverse i-1. */
+                       struct op_desc end = desc[i-1];
+                       end.op_num += prev->group_len;
+                       add_dependency(NULL, op, filename, &desc[i], &end);
+               }
+       }
+       talloc_free(desc);
+}
+
+static void set_nonblock(int fd)
+{
+       if (fcntl(fd, F_SETFL, fcntl(fd, F_GETFL)|O_NONBLOCK) != 0)
+               err(1, "Setting pipe nonblocking");
+}
+
+static bool handle_backoff(struct op *op[], int fd)
+{
+       struct op_desc desc;
+       bool handled = false;
+
+       /* Sloppy coding: we assume PIPEBUF never fills. */
+       while (read(fd, &desc, sizeof(desc)) != -1) {
+               unsigned int i;
+               handled = true;
+               for (i = desc.op_num; i > 0; i--) {
+                       if (op[desc.file][i].type == OP_TDB_TRAVERSE) {
+                               /* We insert a fake end here. */
+                               op[desc.file][i].type
+                                       = OP_TDB_TRAVERSE_END_EARLY;
+                               break;
+                       } else if (starts_traverse(&op[desc.file][i])) {
+                               unsigned int start = i;
+                               struct op tmp = op[desc.file][i];
+                               /* Move the ops outside traverse. */
+                               memmove(&op[desc.file][i],
+                                       &op[desc.file][i+1],
+                                       (desc.op_num-i-1) * sizeof(op[0][0]));
+                               op[desc.file][desc.op_num] = tmp;
+                               while (op[desc.file][i].group_start == start) {
+                                       op[desc.file][i++].group_start
+                                               = desc.op_num;
+                               }
+                               break;
+                       }
+               }
+       }
+       return handled;
+}
+
+#else /* !TRAVERSALS_TAKE_TRANSACTION_LOCK */
+static bool handle_backoff(struct op *op[], int fd)
+{
+       return false;
+}
+#endif
+
+static void derive_dependencies(char *filename[],
+                               struct op *op[], unsigned int num_ops[],
+                               unsigned int num)
+{
+       struct keyinfo *hash;
+       unsigned int h, i;
+
+       /* Create hash table for faster key lookup. */
+       hash = hash_ops(op, num_ops, num);
+
+       /* Sort them by sequence number. */
+       sort_ops(hash, filename, op, num);
+
+       /* Create dependencies back to the last change, rather than
+        * creating false dependencies by naively making each one
+        * depend on the previous.  This has two purposes: it makes
+        * later optimization simpler, and it also avoids deadlock with
+        * same sequence number ops inside traversals (if one
+        * traversal doesn't write anything, two ops can have the same
+        * sequence number yet we can create a traversal dependency
+        * the other way). */
+       for (h = 0; h < total_keys * 2; h++) {
+               int prev = -1;
+
+               if (hash[h].num_users < 2)
+                       continue;
+
+               for (i = 0; i < hash[h].num_users; i++) {
+                       if (changes_db(&hash[h].key, &op[hash[h].user[i].file]
+                                      [hash[h].user[i].op_num])) {
+                               depend_on_previous(op, filename, num,
+                                                  hash[h].user, i, prev);
+                               prev = i;
+                       } else if (prev >= 0)
+                               add_dependency(hash, op, filename,
+                                              &hash[h].user[i],
+                                              &hash[h].user[prev]);
+               }
+       }
+
+#if TRAVERSALS_TAKE_TRANSACTION_LOCK
+       make_traverse_depends(filename, op, num_ops, num);
+#endif
+
+       optimize_dependencies(op, num_ops, num);
+}
+
+static struct timeval run_test(char *argv[],
+                              unsigned int num_ops[],
+                              unsigned int hashsize[],
+                              unsigned int tdb_flags[],
+                              unsigned int open_flags[],
+                              struct op *op[],
+                              int fds[2])
+{
+       unsigned int i;
+       struct timeval start, end, diff;
+       bool ok = true;
+
+       for (i = 0; argv[i+2]; i++) {
+               struct tdb_context *tdb;
+               char c;
+
+               switch (fork()) {
+               case -1:
+                       err(1, "fork failed");
+               case 0:
+                       close(fds[1]);
+                       tdb = tdb_open_ex(argv[1], hashsize[i],
+                                         tdb_flags[i]|TDB_NOSYNC,
+                                         open_flags[i], 0600, NULL, hash_key);
+                       if (!tdb)
+                               err(1, "Opening tdb %s", argv[1]);
+
+                       /* This catches parent exiting. */
+                       if (read(fds[0], &c, 1) != 1)
+                               exit(1);
+                       run_ops(tdb, pipes[i].fd[0], argv+2, op, i, 1,
+                               num_ops[i], false);
+                       check_deps(argv[2+i], op[i], num_ops[i]);
+                       exit(0);
+               default:
+                       break;
+               }
+       }
+
+       /* Let everything settle. */
+       sleep(1);
+
+       printf("Starting run...");
+       fflush(stdout);
+       gettimeofday(&start, NULL);
+       /* Tell them all to go!  Any write of sufficient length will do. */
+       if (write(fds[1], hashsize, i) != i)
+               err(1, "Writing to wakeup pipe");
+
+       for (i = 0; argv[i + 2]; i++) {
+               int status;
+               wait(&status);
+               if (!WIFEXITED(status)) {
+                       warnx("Child died with signal %i", WTERMSIG(status));
+                       ok = false;
+               } else if (WEXITSTATUS(status) != 0)
+                       /* Assume child spat out error. */
+                       ok = false;
+       }
+       if (!ok)
+               exit(1);
+
+       gettimeofday(&end, NULL);
+       printf("done\n");
+
+       if (end.tv_usec < start.tv_usec) {
+               end.tv_usec += 1000000;
+               end.tv_sec--;
+       }
+       diff.tv_sec = end.tv_sec - start.tv_sec;
+       diff.tv_usec = end.tv_usec - start.tv_usec;
+       return diff;
+}
+
+int main(int argc, char *argv[])
+{
+       struct timeval diff;
+       unsigned int i, num_ops[argc], hashsize[argc], tdb_flags[argc], open_flags[argc];
+       struct op *op[argc];
+       int fds[2];
+
+       if (argc < 3)
+               errx(1, "Usage: %s <tdbfile> <tracefile>...", argv[0]);
+
+       pipes = talloc_array(NULL, struct pipe, argc - 1);
+       for (i = 0; i < argc - 2; i++) {
+               printf("Loading tracefile %s...", argv[2+i]);
+               fflush(stdout);
+               op[i] = load_tracefile(argv[2+i], &num_ops[i], &hashsize[i],
+                                      &tdb_flags[i], &open_flags[i]);
+               if (pipe(pipes[i].fd) != 0)
+                       err(1, "creating pipe");
+               printf("done\n");
+       }
+
+       printf("Calculating inter-dependencies...");
+       fflush(stdout);
+       derive_dependencies(argv+2, op, num_ops, i);
+       printf("done\n");
+
+       /* Don't fork for single arg case: simple debugging. */
+       if (argc == 3) {
+               struct tdb_context *tdb;
+               tdb = tdb_open_ex(argv[1], hashsize[0], tdb_flags[0]|TDB_NOSYNC,
+                                 open_flags[0], 0600, NULL, hash_key);
+               printf("Single threaded run...");
+               fflush(stdout);
+
+               run_ops(tdb, pipes[0].fd[0], argv+2, op, 0, 1, num_ops[0],
+                       false);
+               check_deps(argv[2], op[0], num_ops[0]);
+
+               printf("done\n");
+               exit(0);
+       }
+
+       if (pipe(fds) != 0)
+               err(1, "creating pipe");
+
+#if TRAVERSALS_TAKE_TRANSACTION_LOCK
+       if (pipe(pipes[argc-2].fd) != 0)
+               err(1, "creating pipe");
+       backoff_fd = pipes[argc-2].fd[1];
+       set_nonblock(pipes[argc-2].fd[1]);
+       set_nonblock(pipes[argc-2].fd[0]);
+#endif
+
+       do {
+               diff = run_test(argv, num_ops, hashsize, tdb_flags, open_flags,
+                               op, fds);
+       } while (handle_backoff(op, pipes[argc-2].fd[0]));
+
+       printf("Time replaying: %lu usec\n",
+              diff.tv_sec * 1000000UL + diff.tv_usec);
+       
+       exit(0);
+}
diff --git a/ccan/tdb/tools/tdbdump.c b/ccan/tdb/tools/tdbdump.c
new file mode 100644 (file)
index 0000000..38f3de9
--- /dev/null
@@ -0,0 +1,120 @@
+/* 
+   Unix SMB/CIFS implementation.
+   simple tdb dump util
+   Copyright (C) Andrew Tridgell              2001
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+   
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include <ccan/tdb/tdb.h>
+#include <stdlib.h>
+#include <getopt.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <string.h>
+#include <unistd.h>
+#include <sys/types.h>
+#include <fcntl.h>
+#include <ctype.h>
+
+static void print_data(TDB_DATA d)
+{
+       unsigned char *p = (unsigned char *)d.dptr;
+       int len = d.dsize;
+       while (len--) {
+               if (isprint(*p) && !strchr("\"\\", *p)) {
+                       fputc(*p, stdout);
+               } else {
+                       printf("\\%02X", *p);
+               }
+               p++;
+       }
+}
+
+static int traverse_fn(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, void *state)
+{
+       printf("{\n");
+       printf("key(%d) = \"", (int)key.dsize);
+       print_data(key);
+       printf("\"\n");
+       printf("data(%d) = \"", (int)dbuf.dsize);
+       print_data(dbuf);
+       printf("\"\n");
+       printf("}\n");
+       return 0;
+}
+
+static int dump_tdb(const char *fname, const char *keyname)
+{
+       TDB_CONTEXT *tdb;
+       TDB_DATA key, value;
+       
+       tdb = tdb_open(fname, 0, 0, O_RDONLY, 0);
+       if (!tdb) {
+               printf("Failed to open %s\n", fname);
+               return 1;
+       }
+
+       if (!keyname) {
+               tdb_traverse(tdb, traverse_fn, NULL);
+       } else {
+               key.dptr = (void *)keyname;
+               key.dsize = strlen( keyname);
+               value = tdb_fetch(tdb, key);
+               if (!value.dptr) {
+                       return 1;
+               } else {
+                       print_data(value);
+                       free(value.dptr);
+               }
+       }
+
+       return 0;
+}
+
+static void usage( void)
+{
+       printf( "Usage: tdbdump [options] <filename>\n\n");
+       printf( "   -h          this help message\n");
+       printf( "   -k keyname  dumps value of keyname\n");
+}
+
+ int main(int argc, char *argv[])
+{
+       char *fname, *keyname=NULL;
+       int c;
+
+       if (argc < 2) {
+               printf("Usage: tdbdump <fname>\n");
+               exit(1);
+       }
+
+       while ((c = getopt( argc, argv, "hk:")) != -1) {
+               switch (c) {
+               case 'h':
+                       usage();
+                       exit( 0);
+               case 'k':
+                       keyname = optarg;
+                       break;
+               default:
+                       usage();
+                       exit( 1);
+               }
+       }
+
+       fname = argv[optind];
+
+       return dump_tdb(fname, keyname);
+}
diff --git a/ccan/tdb/tools/tdbtorture.c b/ccan/tdb/tools/tdbtorture.c
new file mode 100644 (file)
index 0000000..796fe26
--- /dev/null
@@ -0,0 +1,353 @@
+/* this tests tdb by doing lots of ops from several simultaneous
+   writers - that stresses the locking code. 
+*/
+
+#include <ccan/tdb/tdb.h>
+#include <stdlib.h>
+#include <err.h>
+#include <getopt.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <string.h>
+#include <errno.h>
+#include <unistd.h>
+#include <sys/types.h>
+#include <fcntl.h>
+#include <time.h>
+#include <sys/wait.h>
+
+#define REOPEN_PROB 30
+#define DELETE_PROB 8
+#define STORE_PROB 4
+#define APPEND_PROB 6
+#define TRANSACTION_PROB 10
+#define TRANSACTION_PREPARE_PROB 2
+#define LOCKSTORE_PROB 5
+#define TRAVERSE_PROB 20
+#define TRAVERSE_READ_PROB 20
+#define TRAVERSE_MOD_PROB 100
+#define TRAVERSE_ABORT_PROB 500
+#define CULL_PROB 100
+#define KEYLEN 3
+#define DATALEN 100
+
+static struct tdb_context *db;
+static int in_transaction;
+static int in_traverse;
+static int error_count;
+
+#ifdef PRINTF_ATTRIBUTE
+static void tdb_log(struct tdb_context *tdb, enum tdb_debug_level level, const char *format, ...) PRINTF_ATTRIBUTE(3,4);
+#endif
+static void tdb_log(struct tdb_context *tdb, enum tdb_debug_level level, const char *format, ...)
+{
+       va_list ap;
+    
+       error_count++;
+
+       va_start(ap, format);
+       vfprintf(stdout, format, ap);
+       va_end(ap);
+       fflush(stdout);
+#if 0
+       {
+               char *ptr;
+               asprintf(&ptr,"xterm -e gdb /proc/%d/exe %d", getpid(), getpid());
+               system(ptr);
+               free(ptr);
+       }
+#endif 
+}
+
+static void fatal(const char *why)
+{
+       perror(why);
+       error_count++;
+}
+
+static char *randbuf(int len)
+{
+       char *buf;
+       int i;
+       buf = (char *)malloc(len+1);
+
+       for (i=0;i<len;i++) {
+               buf[i] = 'a' + (rand() % 26);
+       }
+       buf[i] = 0;
+       return buf;
+}
+
+static void addrec_db(void);
+static int modify_traverse(struct tdb_context *tdb, TDB_DATA key, TDB_DATA dbuf,
+                          void *state)
+{
+#if CULL_PROB
+       if (random() % CULL_PROB == 0) {
+               tdb_delete(tdb, key);
+       }
+#endif
+
+#if TRAVERSE_MOD_PROB
+       if (random() % TRAVERSE_MOD_PROB == 0) {
+               addrec_db();
+       }
+#endif
+
+#if TRAVERSE_ABORT_PROB
+       if (random() % TRAVERSE_ABORT_PROB == 0)
+               return 1;
+#endif
+
+       return 0;
+}
+
+static void addrec_db(void)
+{
+       int klen, dlen;
+       char *k, *d;
+       TDB_DATA key, data;
+
+       klen = 1 + (rand() % KEYLEN);
+       dlen = 1 + (rand() % DATALEN);
+
+       k = randbuf(klen);
+       d = randbuf(dlen);
+
+       key.dptr = (unsigned char *)k;
+       key.dsize = klen+1;
+
+       data.dptr = (unsigned char *)d;
+       data.dsize = dlen+1;
+
+#if TRANSACTION_PROB
+       if (in_traverse == 0 && in_transaction == 0 && random() % TRANSACTION_PROB == 0) {
+               if (tdb_transaction_start(db) != 0) {
+                       fatal("tdb_transaction_start failed");
+               }
+               in_transaction++;
+               goto next;
+       }
+       if (in_traverse == 0 && in_transaction && random() % TRANSACTION_PROB == 0) {
+#if 0
+               if (random() % TRANSACTION_PREPARE_PROB == 0) {
+                       if (tdb_transaction_prepare_commit(db) != 0) {
+                               fatal("tdb_transaction_prepare_commit failed");
+                       }
+               }
+#endif
+               if (tdb_transaction_commit(db) != 0) {
+                       fatal("tdb_transaction_commit failed");
+               }
+               in_transaction--;
+               goto next;
+       }
+
+       if (in_traverse == 0 && in_transaction && random() % TRANSACTION_PROB == 0) {
+               if (tdb_transaction_cancel(db) != 0) {
+                       fatal("tdb_transaction_cancel failed");
+               }
+               in_transaction--;
+               goto next;
+       }
+#endif
+
+#if REOPEN_PROB
+       if (in_traverse == 0 && in_transaction == 0 && random() % REOPEN_PROB == 0) {
+               tdb_reopen_all(0);
+               goto next;
+       } 
+#endif
+
+#if DELETE_PROB
+       if (random() % DELETE_PROB == 0) {
+               tdb_delete(db, key);
+               goto next;
+       }
+#endif
+
+#if STORE_PROB
+       if (random() % STORE_PROB == 0) {
+               if (tdb_store(db, key, data, TDB_REPLACE) != 0) {
+                       fatal("tdb_store failed");
+               }
+               goto next;
+       }
+#endif
+
+#if APPEND_PROB
+       if (random() % APPEND_PROB == 0) {
+               if (tdb_append(db, key, data) != 0) {
+                       fatal("tdb_append failed");
+               }
+               goto next;
+       }
+#endif
+
+#if LOCKSTORE_PROB
+       if (random() % LOCKSTORE_PROB == 0) {
+               tdb_chainlock(db, key);
+               data = tdb_fetch(db, key);
+               if (tdb_store(db, key, data, TDB_REPLACE) != 0) {
+                       fatal("tdb_store failed");
+               }
+               if (data.dptr) free(data.dptr);
+               tdb_chainunlock(db, key);
+               goto next;
+       } 
+#endif
+
+#if TRAVERSE_PROB
+       /* FIXME: recursive traverses break transactions? */
+       if (in_traverse == 0 && random() % TRAVERSE_PROB == 0) {
+               in_traverse++;
+               tdb_traverse(db, modify_traverse, NULL);
+               in_traverse--;
+               goto next;
+       }
+#endif
+
+#if TRAVERSE_READ_PROB
+       if (in_traverse == 0 && random() % TRAVERSE_READ_PROB == 0) {
+               in_traverse++;
+               tdb_traverse_read(db, NULL, NULL);
+               in_traverse--;
+               goto next;
+       }
+#endif
+
+       data = tdb_fetch(db, key);
+       if (data.dptr) free(data.dptr);
+
+next:
+       free(k);
+       free(d);
+}
+
+static int traverse_fn(struct tdb_context *tdb, TDB_DATA key, TDB_DATA dbuf,
+                       void *state)
+{
+       tdb_delete(tdb, key);
+       return 0;
+}
+
+static void usage(void)
+{
+       printf("Usage: tdbtorture [-n NUM_PROCS] [-l NUM_LOOPS] [-s SEED] [-H HASH_SIZE]\n");
+       exit(0);
+}
+
+int main(int argc, char * const *argv)
+{
+       int i, seed = -1;
+       int num_procs = 3;
+       int num_loops = 5000;
+       int hash_size = 2;
+       int c;
+       extern char *optarg;
+       pid_t *pids;
+
+       struct tdb_logging_context log_ctx;
+       log_ctx.log_fn = tdb_log;
+
+       while ((c = getopt(argc, argv, "n:l:s:H:h")) != -1) {
+               switch (c) {
+               case 'n':
+                       num_procs = strtol(optarg, NULL, 0);
+                       break;
+               case 'l':
+                       num_loops = strtol(optarg, NULL, 0);
+                       break;
+               case 'H':
+                       hash_size = strtol(optarg, NULL, 0);
+                       break;
+               case 's':
+                       seed = strtol(optarg, NULL, 0);
+                       break;
+               default:
+                       usage();
+               }
+       }
+
+       unlink("torture.tdb");
+
+       pids = (pid_t *)calloc(sizeof(pid_t), num_procs);
+       pids[0] = getpid();
+
+       for (i=0;i<num_procs-1;i++) {
+               if ((pids[i+1]=fork()) == 0) break;
+       }
+
+       db = tdb_open_ex("torture.tdb", hash_size, TDB_CLEAR_IF_FIRST, 
+                        O_RDWR | O_CREAT, 0600, &log_ctx, NULL);
+       if (!db) {
+               fatal("db open failed");
+       }
+
+       if (seed == -1) {
+               seed = (getpid() + time(NULL)) & 0x7FFFFFFF;
+       }
+
+       if (i == 0) {
+               printf("testing with %d processes, %d loops, %d hash_size, seed=%d\n", 
+                      num_procs, num_loops, hash_size, seed);
+       }
+
+       srand(seed + i);
+       srandom(seed + i);
+
+       for (i=0;i<num_loops && error_count == 0;i++) {
+               addrec_db();
+       }
+
+       if (error_count == 0) {
+               tdb_traverse_read(db, NULL, NULL);
+               tdb_traverse(db, traverse_fn, NULL);
+               tdb_traverse(db, traverse_fn, NULL);
+       }
+
+       tdb_close(db);
+
+       if (getpid() != pids[0]) {
+               return error_count;
+       }
+
+       for (i=1;i<num_procs;i++) {
+               int status, j;
+               pid_t pid;
+               if (error_count != 0) {
+                       /* try and stop the test on any failure */
+                       for (j=1;j<num_procs;j++) {
+                               if (pids[j] != 0) {
+                                       kill(pids[j], SIGTERM);
+                               }
+                       }
+               }
+               pid = waitpid(-1, &status, 0);
+               if (pid == -1) {
+                       perror("failed to wait for child\n");
+                       exit(1);
+               }
+               for (j=1;j<num_procs;j++) {
+                       if (pids[j] == pid) break;
+               }
+               if (j == num_procs) {
+                       printf("unknown child %d exited!?\n", (int)pid);
+                       exit(1);
+               }
+               if (WEXITSTATUS(status) != 0) {
+                       printf("child %d exited with status %d\n",
+                              (int)pid, WEXITSTATUS(status));
+                       error_count++;
+               }
+               pids[j] = 0;
+       }
+
+       free(pids);
+
+       if (error_count == 0) {
+               printf("OK\n");
+       }
+
+       return error_count;
+}
diff --git a/ccan/tdb/tools/tests/1-torture.trace.tar.bz2 b/ccan/tdb/tools/tests/1-torture.trace.tar.bz2
new file mode 100644 (file)
index 0000000..272ea29
Binary files /dev/null and b/ccan/tdb/tools/tests/1-torture.trace.tar.bz2 differ
diff --git a/ccan/tdb/tools/tests/2-torture.trace.tar.bz2 b/ccan/tdb/tools/tests/2-torture.trace.tar.bz2
new file mode 100644 (file)
index 0000000..20bd5d3
Binary files /dev/null and b/ccan/tdb/tools/tests/2-torture.trace.tar.bz2 differ
diff --git a/ccan/tdb/tools/tests/3-torture.trace.tar.bz2 b/ccan/tdb/tools/tests/3-torture.trace.tar.bz2
new file mode 100644 (file)
index 0000000..b039ca0
Binary files /dev/null and b/ccan/tdb/tools/tests/3-torture.trace.tar.bz2 differ
diff --git a/ccan/tdb/tools/tests/4-torture.trace.tar.bz2 b/ccan/tdb/tools/tests/4-torture.trace.tar.bz2
new file mode 100644 (file)
index 0000000..e2307f7
Binary files /dev/null and b/ccan/tdb/tools/tests/4-torture.trace.tar.bz2 differ
diff --git a/ccan/tdb/tools/tests/5-torture.trace.tar.bz2 b/ccan/tdb/tools/tests/5-torture.trace.tar.bz2
new file mode 100644 (file)
index 0000000..a3d590e
Binary files /dev/null and b/ccan/tdb/tools/tests/5-torture.trace.tar.bz2 differ
diff --git a/ccan/tdb/tools/tests/6-torture.trace.tar.bz2 b/ccan/tdb/tools/tests/6-torture.trace.tar.bz2
new file mode 100644 (file)
index 0000000..dc55cc9
Binary files /dev/null and b/ccan/tdb/tools/tests/6-torture.trace.tar.bz2 differ
diff --git a/ccan/tdb/tools/tests/7-torture.trace.tar.bz2 b/ccan/tdb/tools/tests/7-torture.trace.tar.bz2
new file mode 100644 (file)
index 0000000..e77abaf
Binary files /dev/null and b/ccan/tdb/tools/tests/7-torture.trace.tar.bz2 differ
diff --git a/ccan/tdb/tools/tests/8-torture.trace.tar.bz2 b/ccan/tdb/tools/tests/8-torture.trace.tar.bz2
new file mode 100644 (file)
index 0000000..5358d1a
Binary files /dev/null and b/ccan/tdb/tools/tests/8-torture.trace.tar.bz2 differ
diff --git a/ccan/tdb/tools/tests/9-torture.trace.tar.bz2 b/ccan/tdb/tools/tests/9-torture.trace.tar.bz2
new file mode 100644 (file)
index 0000000..edd88ea
Binary files /dev/null and b/ccan/tdb/tools/tests/9-torture.trace.tar.bz2 differ
index d6db8b01329913e09dbd55e6cec82aa61b0d4f9f..a23bb60427c574a5ac9c7f25ef7c82f32c9c6e0c 100644 (file)
@@ -398,6 +398,58 @@ static const struct tdb_methods transaction_methods = {
        transaction_brlock
 };
 
+int tdb_transaction_cancel_internal(struct tdb_context *tdb)
+{
+       int i;
+
+       if (tdb->transaction == NULL) {
+               TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_transaction_cancel: no transaction\n"));
+               return -1;
+       }
+
+       if (tdb->transaction->nesting != 0) {
+               tdb->transaction->transaction_error = 1;
+               tdb->transaction->nesting--;
+               return 0;
+       }               
+
+       tdb->map_size = tdb->transaction->old_map_size;
+
+       /* free all the transaction blocks */
+       for (i=0;i<tdb->transaction->num_blocks;i++) {
+               if (tdb->transaction->blocks[i] != NULL) {
+                       free(tdb->transaction->blocks[i]);
+               }
+       }
+       SAFE_FREE(tdb->transaction->blocks);
+
+       /* remove any global lock created during the transaction */
+       if (tdb->global_lock.count != 0) {
+               tdb_brlock(tdb, FREELIST_TOP, F_UNLCK, F_SETLKW, 0, 4*tdb->header.hash_size);
+               tdb->global_lock.count = 0;
+       }
+
+       /* remove any locks created during the transaction */
+       if (tdb->num_locks != 0) {
+               for (i=0;i<tdb->num_lockrecs;i++) {
+                       tdb_brlock(tdb,FREELIST_TOP+4*tdb->lockrecs[i].list,
+                                  F_UNLCK,F_SETLKW, 0, 1);
+               }
+               tdb->num_locks = 0;
+               tdb->num_lockrecs = 0;
+               SAFE_FREE(tdb->lockrecs);
+       }
+
+       /* restore the normal io methods */
+       tdb->methods = tdb->transaction->io_methods;
+
+       tdb_brlock(tdb, FREELIST_TOP, F_UNLCK, F_SETLKW, 0, 0);
+       tdb_transaction_unlock(tdb);
+       SAFE_FREE(tdb->transaction->hash_heads);
+       SAFE_FREE(tdb->transaction);
+       
+       return 0;
+}
 
 /*
   start a tdb transaction. No token is returned, as only a single
@@ -414,13 +466,14 @@ int tdb_transaction_start(struct tdb_context *tdb)
 
        /* cope with nested tdb_transaction_start() calls */
        if (tdb->transaction != NULL) {
+               tdb_trace(tdb, "tdb_transaction_start");
                if (!tdb->flags & TDB_NO_NESTING) {
                        tdb->transaction->nesting++;
                        TDB_LOG((tdb, TDB_DEBUG_TRACE, "tdb_transaction_start: nesting %d\n", 
                                 tdb->transaction->nesting));
                        return 0;
                } else {
-                       tdb_transaction_cancel(tdb);
+                       tdb_transaction_cancel_internal(tdb);
                        TDB_LOG((tdb, TDB_DEBUG_TRACE, "tdb_transaction_start: cancelling previous transaction\n"));
                }
        }
@@ -495,6 +548,8 @@ int tdb_transaction_start(struct tdb_context *tdb)
        tdb->transaction->io_methods = tdb->methods;
        tdb->methods = &transaction_methods;
 
+       /* Trace at the end, so we get sequence number correct. */
+       tdb_trace(tdb, "tdb_transaction_start");
        return 0;
        
 fail:
@@ -512,57 +567,9 @@ fail:
 */
 int tdb_transaction_cancel(struct tdb_context *tdb)
 {      
-       int i;
-
-       if (tdb->transaction == NULL) {
-               TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_transaction_cancel: no transaction\n"));
-               return -1;
-       }
-
-       if (tdb->transaction->nesting != 0) {
-               tdb->transaction->transaction_error = 1;
-               tdb->transaction->nesting--;
-               return 0;
-       }               
-
-       tdb->map_size = tdb->transaction->old_map_size;
-
-       /* free all the transaction blocks */
-       for (i=0;i<tdb->transaction->num_blocks;i++) {
-               if (tdb->transaction->blocks[i] != NULL) {
-                       free(tdb->transaction->blocks[i]);
-               }
-       }
-       SAFE_FREE(tdb->transaction->blocks);
-
-       /* remove any global lock created during the transaction */
-       if (tdb->global_lock.count != 0) {
-               tdb_brlock(tdb, FREELIST_TOP, F_UNLCK, F_SETLKW, 0, 4*tdb->header.hash_size);
-               tdb->global_lock.count = 0;
-       }
-
-       /* remove any locks created during the transaction */
-       if (tdb->num_locks != 0) {
-               for (i=0;i<tdb->num_lockrecs;i++) {
-                       tdb_brlock(tdb,FREELIST_TOP+4*tdb->lockrecs[i].list,
-                                  F_UNLCK,F_SETLKW, 0, 1);
-               }
-               tdb->num_locks = 0;
-               tdb->num_lockrecs = 0;
-               SAFE_FREE(tdb->lockrecs);
-       }
-
-       /* restore the normal io methods */
-       tdb->methods = tdb->transaction->io_methods;
-
-       tdb_brlock(tdb, FREELIST_TOP, F_UNLCK, F_SETLKW, 0, 0);
-       tdb_transaction_unlock(tdb);
-       SAFE_FREE(tdb->transaction->hash_heads);
-       SAFE_FREE(tdb->transaction);
-       
-       return 0;
+       tdb_trace(tdb, "tdb_transaction_cancel");
+       return tdb_transaction_cancel_internal(tdb);
 }
-
 /*
   sync to disk
 */
@@ -845,6 +852,7 @@ int tdb_transaction_commit(struct tdb_context *tdb)
        uint32_t zero = 0;
        int i;
 
+       tdb_trace(tdb, "tdb_transaction_commit");
        if (tdb->transaction == NULL) {
                TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_transaction_commit: no transaction\n"));
                return -1;
@@ -852,7 +860,7 @@ int tdb_transaction_commit(struct tdb_context *tdb)
 
        if (tdb->transaction->transaction_error) {
                tdb->ecode = TDB_ERR_IO;
-               tdb_transaction_cancel(tdb);
+               tdb_transaction_cancel_internal(tdb);
                TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_transaction_commit: transaction error pending\n"));
                return -1;
        }
@@ -865,7 +873,7 @@ int tdb_transaction_commit(struct tdb_context *tdb)
 
        /* check for a null transaction */
        if (tdb->transaction->blocks == NULL) {
-               tdb_transaction_cancel(tdb);
+               tdb_transaction_cancel_internal(tdb);
                return 0;
        }
 
@@ -876,7 +884,7 @@ int tdb_transaction_commit(struct tdb_context *tdb)
        if (tdb->num_locks || tdb->global_lock.count) {
                tdb->ecode = TDB_ERR_LOCK;
                TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_transaction_commit: locks pending on commit\n"));
-               tdb_transaction_cancel(tdb);
+               tdb_transaction_cancel_internal(tdb);
                return -1;
        }
 
@@ -884,7 +892,7 @@ int tdb_transaction_commit(struct tdb_context *tdb)
        if (tdb_brlock_upgrade(tdb, FREELIST_TOP, 0) == -1) {
                TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_transaction_start: failed to upgrade hash locks\n"));
                tdb->ecode = TDB_ERR_LOCK;
-               tdb_transaction_cancel(tdb);
+               tdb_transaction_cancel_internal(tdb);
                return -1;
        }
 
@@ -893,7 +901,7 @@ int tdb_transaction_commit(struct tdb_context *tdb)
        if (tdb_brlock(tdb, GLOBAL_LOCK, F_WRLCK, F_SETLKW, 0, 1) == -1) {
                TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_transaction_commit: failed to get global lock\n"));
                tdb->ecode = TDB_ERR_LOCK;
-               tdb_transaction_cancel(tdb);
+               tdb_transaction_cancel_internal(tdb);
                return -1;
        }
 
@@ -902,7 +910,7 @@ int tdb_transaction_commit(struct tdb_context *tdb)
                if (transaction_setup_recovery(tdb, &magic_offset) == -1) {
                        TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_transaction_commit: failed to setup recovery data\n"));
                        tdb_brlock(tdb, GLOBAL_LOCK, F_UNLCK, F_SETLKW, 0, 1);
-                       tdb_transaction_cancel(tdb);
+                       tdb_transaction_cancel_internal(tdb);
                        return -1;
                }
        }
@@ -915,7 +923,7 @@ int tdb_transaction_commit(struct tdb_context *tdb)
                        tdb->ecode = TDB_ERR_IO;
                        TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_transaction_commit: expansion failed\n"));
                        tdb_brlock(tdb, GLOBAL_LOCK, F_UNLCK, F_SETLKW, 0, 1);
-                       tdb_transaction_cancel(tdb);
+                       tdb_transaction_cancel_internal(tdb);
                        return -1;
                }
                tdb->map_size = tdb->transaction->old_map_size;
@@ -946,7 +954,7 @@ int tdb_transaction_commit(struct tdb_context *tdb)
                        tdb->methods = methods;
                        tdb_transaction_recover(tdb); 
 
-                       tdb_transaction_cancel(tdb);
+                       tdb_transaction_cancel_internal(tdb);
                        tdb_brlock(tdb, GLOBAL_LOCK, F_UNLCK, F_SETLKW, 0, 1);
 
                        TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_transaction_commit: write failed\n"));
@@ -995,7 +1003,7 @@ int tdb_transaction_commit(struct tdb_context *tdb)
 
        /* use a transaction cancel to free memory and remove the
           transaction locks */
-       tdb_transaction_cancel(tdb);
+       tdb_transaction_cancel_internal(tdb);
 
        return 0;
 }
index 07b0c238587eb85fe3945b61b71dbd9dd0729d58..d8b15aff4aa39f22f76fd6080e8e251404be4d75 100644 (file)
@@ -169,6 +169,8 @@ static int tdb_traverse_internal(struct tdb_context *tdb,
                dbuf.dptr = key.dptr + rec.key_len;
                dbuf.dsize = rec.data_len;
 
+               tdb_trace_1rec_retrec(tdb, "traverse", key, dbuf);
+
                /* Drop chain lock, call out */
                if (tdb_unlock(tdb, tl->hash, tl->lock_rw) != 0) {
                        ret = -1;
@@ -177,6 +179,7 @@ static int tdb_traverse_internal(struct tdb_context *tdb,
                }
                if (fn && fn(tdb, key, dbuf, private_data)) {
                        /* They want us to terminate traversal */
+                       tdb_trace_ret(tdb, "tdb_traverse_end", count);
                        ret = count;
                        if (tdb_unlock_record(tdb, tl->off) != 0) {
                                TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_traverse: unlock_record failed!\n"));;
@@ -187,6 +190,7 @@ static int tdb_traverse_internal(struct tdb_context *tdb,
                }
                SAFE_FREE(key.dptr);
        }
+       tdb_trace(tdb, "tdb_traverse_end");
 out:
        tdb->travlocks.next = tl->next;
        if (ret < 0)
@@ -212,6 +216,7 @@ int tdb_traverse_read(struct tdb_context *tdb,
        }
 
        tdb->traverse_read++;
+       tdb_trace(tdb, "tdb_traverse_read_start");
        ret = tdb_traverse_internal(tdb, fn, private_data, &tl);
        tdb->traverse_read--;
 
@@ -236,12 +241,13 @@ int tdb_traverse(struct tdb_context *tdb,
        if (tdb->read_only || tdb->traverse_read) {
                return tdb_traverse_read(tdb, fn, private_data);
        }
-       
+
        if (tdb_transaction_lock(tdb, F_WRLCK)) {
                return -1;
        }
 
        tdb->traverse_write++;
+       tdb_trace(tdb, "tdb_traverse_start");
        ret = tdb_traverse_internal(tdb, fn, private_data, &tl);
        tdb->traverse_write--;
 
@@ -264,12 +270,16 @@ TDB_DATA tdb_firstkey(struct tdb_context *tdb)
        tdb->travlocks.lock_rw = F_RDLCK;
 
        /* Grab first record: locks chain and returned record. */
-       if (tdb_next_lock(tdb, &tdb->travlocks, &rec) <= 0)
+       if (tdb_next_lock(tdb, &tdb->travlocks, &rec) <= 0) {
+               tdb_trace_retrec(tdb, "tdb_firstkey", tdb_null);
                return tdb_null;
+       }
        /* now read the key */
        key.dsize = rec.key_len;
        key.dptr =tdb_alloc_read(tdb,tdb->travlocks.off+sizeof(rec),key.dsize);
 
+       tdb_trace_retrec(tdb, "tdb_firstkey", key);
+
        /* Unlock the hash chain of the record we just read. */
        if (tdb_unlock(tdb, tdb->travlocks.hash, tdb->travlocks.lock_rw) != 0)
                TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_firstkey: error occurred while tdb_unlocking!\n"));
@@ -294,6 +304,8 @@ TDB_DATA tdb_nextkey(struct tdb_context *tdb, TDB_DATA oldkey)
                    || memcmp(k, oldkey.dptr, oldkey.dsize) != 0) {
                        /* No, it wasn't: unlock it and start from scratch */
                        if (tdb_unlock_record(tdb, tdb->travlocks.off) != 0) {
+                               tdb_trace_1rec_retrec(tdb, "tdb_nextkey",
+                                                     oldkey, tdb_null);
                                SAFE_FREE(k);
                                return tdb_null;
                        }
@@ -310,8 +322,10 @@ TDB_DATA tdb_nextkey(struct tdb_context *tdb, TDB_DATA oldkey)
        if (!tdb->travlocks.off) {
                /* No previous element: do normal find, and lock record */
                tdb->travlocks.off = tdb_find_lock_hash(tdb, oldkey, tdb->hash_fn(&oldkey), tdb->travlocks.lock_rw, &rec);
-               if (!tdb->travlocks.off)
+               if (!tdb->travlocks.off) {
+                       tdb_trace_1rec_retrec(tdb, "tdb_nextkey", oldkey, tdb_null);
                        return tdb_null;
+               }
                tdb->travlocks.hash = BUCKET(rec.full_hash);
                if (tdb_lock_record(tdb, tdb->travlocks.off) != 0) {
                        TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_nextkey: lock_record failed (%s)!\n", strerror(errno)));
@@ -333,6 +347,7 @@ TDB_DATA tdb_nextkey(struct tdb_context *tdb, TDB_DATA oldkey)
        /* Unlock the chain of old record */
        if (tdb_unlock(tdb, BUCKET(oldhash), tdb->travlocks.lock_rw) != 0)
                TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_nextkey: WARNING tdb_unlock failed!\n"));
+       tdb_trace_1rec_retrec(tdb, "tdb_nextkey", oldkey, key);
        return key;
 }
 
diff --git a/junkcode/fork0@users.sf.net-bitmaps/bitmaps.h b/junkcode/fork0@users.sf.net-bitmaps/bitmaps.h
new file mode 100644 (file)
index 0000000..05ecd96
--- /dev/null
@@ -0,0 +1,78 @@
+/* bitmaps and bitmap operations */
+#ifndef _BITMAPS_H_
+#define _BITMAPS_H_
+
+/*
+ * Bitmaps are arrays of unsigned ints, filled with bits in most-
+ * significant-first order. So bitmap[0] shall contain the bits from
+ * 0 to 31 on a 32bit architecture, bitmap[1] - 32-63, and so forth.
+ *
+ * The callers are responsible to do all the bounds-checking.
+ */
+enum { BITS_PER_BITMAP_ELEM = 8 * sizeof(unsigned) };
+
+typedef unsigned bitmap_elem_t;
+
+/* returned is the unshifted bit state. IOW: NOT 0 or 1, but something
+ * like 0x00001000 or 0x40000000 */
+static inline
+bitmap_elem_t bitmap_test_bit(const bitmap_elem_t* bits, unsigned bit)
+{
+    if ( sizeof(*bits) == 4 )
+       return bits[bit >> 5] & (0x80000000 >> (bit & 0x1f));
+    else if ( sizeof(*bits) == 8 )
+       return bits[bit >> 6] & (0x8000000000000000ull >> (bit & 0x3f));
+    else
+    {
+       return bits[bit / BITS_PER_BITMAP_ELEM] &
+           1 << ((BITS_PER_BITMAP_ELEM - bit % BITS_PER_BITMAP_ELEM) - 1);
+    }
+}
+
+static inline
+bitmap_elem_t bitmap_set_bit(bitmap_elem_t* bits, unsigned bit)
+{
+    if ( sizeof(*bits) == 4 )
+       return bits[bit >> 5] |= (0x80000000 >> (bit & 0x1f));
+    else if ( sizeof(*bits) == 8 )
+       return bits[bit >> 6] |= (0x8000000000000000ull >> (bit & 0x3f));
+    else
+    {
+       return bits[bit / BITS_PER_BITMAP_ELEM] |=
+           1 << ((BITS_PER_BITMAP_ELEM - bit % BITS_PER_BITMAP_ELEM) - 1);
+    }
+}
+
+/* pos must position the bits inside of a bitmap element, otherwise
+ * the index shift puts the bits in the wrong word (for simplicity).
+ * Only low 8 bits of b8 shall be used */
+static inline
+void bitmap_set_8bits_fast(bitmap_elem_t* bits, unsigned pos, unsigned b8)
+{
+    if ( sizeof(*bits) == 4 )
+       bits[pos >> 5] |= b8 << (24 - (pos & 0x1f));
+    else if ( sizeof(*bits) == 8 )
+       bits[pos >> 6] |= b8 << (56 - (pos & 0x3f));
+    else
+    {
+       bits[pos / BITS_PER_BITMAP_ELEM] |=
+           b8 << (BITS_PER_BITMAP_ELEM - 8 - pos % BITS_PER_BITMAP_ELEM);
+    }
+}
+
+static inline
+bitmap_elem_t bitmap_clear_bit(bitmap_elem_t* bits, unsigned bit)
+{
+    if ( sizeof(*bits) == 4 )
+       return bits[bit >> 5] &= ~(0x80000000 >> (bit & 0x1f));
+    else if ( sizeof(*bits) == 8 )
+       return bits[bit >> 6] &= ~(0x8000000000000000ull >> (bit & 0x3f));
+    else
+    {
+       return bits[bit / BITS_PER_BITMAP_ELEM] &=
+           ~(1 << ((BITS_PER_BITMAP_ELEM - bit % BITS_PER_BITMAP_ELEM) - 1));
+    }
+}
+
+#endif /* _BITMAPS_H_ */
+
diff --git a/junkcode/fork0@users.sf.net-pathexpand/pathexpand.c b/junkcode/fork0@users.sf.net-pathexpand/pathexpand.c
new file mode 100644 (file)
index 0000000..4b8bcf0
--- /dev/null
@@ -0,0 +1,96 @@
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/*
+ * Returns the analog of "cd path" from a directory "cwd".
+ * The root is defined as empty path (instead of "/")
+ * An attempt to go past the root (with "..") leaves the path at root.
+ * The cwd is not expanded.
+ */
+char *pathexpand(const char *cwd, const char *path)
+{
+       static const char SEP[] = "/";
+       if (!*path) /* empty path -> "." (don't move) */
+               path = ".";
+       if (!*cwd || *SEP == *path) /* no cwd, or path begins with "/" */
+               cwd = "";
+
+       while (*cwd && *SEP == *cwd)
+               ++cwd;
+
+       size_t len = strlen(cwd);
+       char *out = malloc(len + 1 + strlen(path) + 1);
+       char *p = strcpy(out, cwd) + len;
+
+       for (; *path; ++path)
+       {
+               char *pl;
+               if (p > out && p[-1] != *SEP)
+                       *p++ = *SEP;
+               pl = p;
+               while (*path && *SEP != *path)
+                       *p++ = *path++;
+               *p = '\0';
+               /* ..."//"... */
+               if (p == pl)
+                       ; /* just ignore */
+               /* ..."/./"...  */
+               else if ( p - pl == 1 && '.' == *pl )
+                       --p; /* just ignore */
+               /* ..."/../"...  */
+               else if ( p - pl == 2 && '.' == pl[0] && '.' == pl[1] )
+               {
+                       /* drop the last element of the resulting path */
+                       if (pl > out && --pl > out)
+                               for (--pl; pl > out && *SEP != *pl; --pl)
+                                       ;
+                       p = pl > out ? ++pl: out;
+               }
+               /* ..."/path/"...  */
+               else if (*path)
+                       *p++ = *path; /* just add the separator */
+
+               if (!*path)
+                       break;
+       }
+       if (p > out+1 && *SEP == p[-1])
+               --p;
+       *p = '\0';
+       return out;
+}
+
+#ifdef CHECK_PATHEXPAND
+static void check(const char *cwd, const char *path, const char *good)
+{
+       static int n = 0;
+       printf("%-2d: %10s$ cd %s", ++n, cwd, path);
+       char *t = pathexpand(cwd, path);
+       if ( strcmp(t, good) )
+               printf(" ____________________failed(%s)\n", t);
+       else
+               printf(" \033[32m%s\033[0m\n", t);
+       free(t);
+}
+
+int main(int argc, char **argv)
+{
+       /* 1 */ check("/onelevel", "aa", "onelevel/aa");
+       /* 2 */ check("/", "..", "");
+       /* 3 */ check("/", "../..", "");
+       /* 4 */ check("/one", "aa/../bb", "one/bb");
+       /* 5 */ check("/one/two", "aa//bb", "one/two/aa/bb");
+       /* 6 */ check("", "/aa//bb", "aa/bb");
+       /* 7 */ check("/one/two", "", "one/two");
+       /* 8 */ check("/one/two", "aa/..bb/x/../cc/", "one/two/aa/..bb/cc");
+       /* 9 */ check("/one/two", "aa/x/././cc////", "one/two/aa/x/cc");
+       /* 10 */ check("/one/two", "../../../../aa", "aa");
+       /* 11 */ check("one/", "../one/two", "one/two");
+       /* 12 */ check("", "../../two", "two");
+       /* 13 */ check("a/b/c", "../../two", "a/two");
+       /* 14 */ check("a/b/", "../two", "a/two");
+       /* 15 */ check("///", "../two", "two");
+       return 0;
+}
+#endif
+
diff --git a/junkcode/fork0@users.sf.net-timeout/timeout.c b/junkcode/fork0@users.sf.net-timeout/timeout.c
new file mode 100644 (file)
index 0000000..290e427
--- /dev/null
@@ -0,0 +1,173 @@
+/* execute a program with a timeout by alarm(2) */
+#define _GNU_SOURCE
+#include <unistd.h>
+#include <sys/types.h>
+#include <sys/wait.h>
+#include <signal.h>
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <errno.h>
+
+static const char *argv0;
+static char **prgargv;
+static pid_t pid;
+static int signo;
+static unsigned int timeout;
+
+static void timedout(int sig)
+{
+       fprintf(stderr, "%s[%d]: %s[%d] timed out after %u sec\n",
+               argv0, getpid(), *prgargv, pid, timeout);
+       if (pid)
+               kill(-pid, signo);
+}
+
+static void interrupted(int sig)
+{
+       alarm(0);
+       if (pid)
+               kill(-pid, sig);
+}
+
+static void usage()
+{
+       fprintf(stderr, "%s <timeout-seconds> [-<signal>] program ...\n"
+               "Where <signal> is a signal number (see kill -l).\n"
+               "Some symbolic names recognized. KILL used by default\n",
+               argv0);
+       exit(1);
+}
+
+static struct {
+       const char *name;
+       int signo;
+} known[] = {
+       {"HUP",     SIGHUP},
+       {"INT",     SIGINT},
+       {"QUIT",    SIGQUIT},
+       {"ILL",     SIGILL},
+       {"TRAP",    SIGTRAP},
+       {"ABRT",    SIGABRT},
+       {"BUS",     SIGBUS},
+       {"FPE",     SIGFPE},
+       {"KILL",    SIGKILL},
+       {"USR1",    SIGUSR1},
+       {"SEGV",    SIGSEGV},
+       {"USR2",    SIGUSR2},
+       {"PIPE",    SIGPIPE},
+       {"ALRM",    SIGALRM},
+       {"TERM",    SIGTERM},
+       {"STKFLT",  SIGSTKFLT},
+       {"CHLD",    SIGCHLD},
+       {"CONT",    SIGCONT},
+       {"STOP",    SIGSTOP},
+       {"TSTP",    SIGTSTP},
+       {"TTIN",    SIGTTIN},
+       {"TTOU",    SIGTTOU},
+       {"URG",     SIGURG},
+       {"XCPU",    SIGXCPU},
+       {"XFSZ",    SIGXFSZ},
+       {"VTALRM",  SIGVTALRM},
+       {"PROF",    SIGPROF},
+       {"WINCH",   SIGWINCH},
+       {"IO",      SIGIO},
+       {"PWR",     SIGPWR},
+       {"SYS",     SIGSYS},
+};
+
+static int signo_arg(const char *arg)
+{
+       if (*arg == '-') {
+               char *p;
+               int s = strtol(++arg, &p, 10);
+               if (!*p && p > arg && s > 0 && s < _NSIG) {
+                       signo = s;
+                       return 1;
+               }
+               if (!strncasecmp(arg, "SIG", 3))
+                       arg += 3;
+               for (s = 0; s < sizeof(known)/sizeof(*known); ++s)
+                       if (!strcasecmp(arg, known[s].name)) {
+                               signo = known[s].signo;
+                               return 1;
+                       }
+       }
+       return 0;
+}
+
+int main(int argc, char** argv)
+{
+       argv0 = strrchr(*argv, '/');
+       if (argv0)
+               ++argv0;
+       else
+               argv0 = *argv;
+
+       signal(SIGALRM, timedout);
+       signal(SIGINT, interrupted);
+       signal(SIGHUP, interrupted);
+
+       ++argv;
+
+       if (!*argv)
+               usage();
+
+       if (signo_arg(*argv))
+               ++argv;
+       if (sscanf(*argv, "%u", &timeout) == 1)
+               ++argv;
+       else
+               usage();
+       if (!signo && signo_arg(*argv))
+               ++argv;
+       if (!signo)
+               signo = SIGKILL;
+
+       if (!*argv)
+               usage();
+
+       prgargv = argv;
+       alarm(timeout);
+       pid = fork();
+
+       if (!pid) {
+               signal(SIGALRM, SIG_DFL);
+               signal(SIGCHLD, SIG_DFL);
+               signal(SIGINT, SIG_DFL);
+               signal(SIGHUP, SIG_DFL);
+               setpgid(0, 0);
+               execvp(*prgargv, prgargv);
+               fprintf(stderr, "%s: %s: %s\n",
+                       argv0, *prgargv, strerror(errno));
+               _exit(2);
+       } else if (pid < 0) {
+               fprintf(stderr, "%s: %s\n", argv0, strerror(errno));
+       } else {
+               int status;
+               while (waitpid(pid, &status, 0) < 0 && EINTR == errno)
+                       ;
+               alarm(0);
+               if (WIFEXITED(status))
+                       return WEXITSTATUS(status);
+               if (WIFSIGNALED(status)) {
+                       /*
+                        * Some signals are special, lets die with
+                        * the same signal as child process
+                        */
+                       if (WTERMSIG(status) == SIGHUP  ||
+                           WTERMSIG(status) == SIGINT  ||
+                           WTERMSIG(status) == SIGTERM ||
+                           WTERMSIG(status) == SIGQUIT ||
+                           WTERMSIG(status) == SIGKILL) {
+                               signal(WTERMSIG(status), SIG_DFL);
+                               raise(WTERMSIG(status));
+                       }
+                       fprintf(stderr, "%s: %s: %s\n",
+                               argv0, *prgargv, strsignal(WTERMSIG(status)));
+               }
+               else
+                       fprintf(stderr, "%s died\n", *prgargv);
+       }
+       return 2;
+}