tdb2: more tests, hash collision fixes, attribute support.
authorRusty Russell <rusty@rustcorp.com.au>
Mon, 30 Aug 2010 04:59:08 +0000 (14:29 +0930)
committerRusty Russell <rusty@rustcorp.com.au>
Mon, 30 Aug 2010 04:59:08 +0000 (14:29 +0930)
14 files changed:
ccan/tdb2/lock.c
ccan/tdb2/tdb.c
ccan/tdb2/test/layout.c
ccan/tdb2/test/logging.c
ccan/tdb2/test/logging.h
ccan/tdb2/test/run-coalesce.c
ccan/tdb2/test/run-delete.c [new file with mode: 0644]
ccan/tdb2/test/run-enlarge_hash.c
ccan/tdb2/test/run-expand.c
ccan/tdb2/test/run-new_database.c
ccan/tdb2/test/run-record-expand.c
ccan/tdb2/test/run-simple-delete.c
ccan/tdb2/test/run-simple-fetch.c
ccan/tdb2/test/run-simple-store.c

index 3230b25e383d3b2a3ead9a1ac7ca156b4030f303..c8dbf8267a8f9dab5fc92c9a3e7e810e6d8943d1 100644 (file)
@@ -665,6 +665,8 @@ again:
 
 int tdb_unlock_list(struct tdb_context *tdb, tdb_off_t list, int ltype)
 {
+       list &= ((1ULL << tdb->header.v.hash_bits) - 1);
+
        /* a allrecord lock allows us to avoid per chain locks */
        if (tdb->allrecord_lock.count) {
                if (tdb->allrecord_lock.ltype == F_RDLCK
index 19ebfb4961677f3b0740fa0f07c6f66b5aef1785..915b4c765afe51aa90e32030beb2b8b182390763 100644 (file)
@@ -236,12 +236,24 @@ struct tdb_context *tdb_open(const char *name, int tdb_flags,
        tdb_io_init(tdb);
        tdb_lock_init(tdb);
 
-       /* FIXME */
-       if (attr) {
-               tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
-                        "tdb_open: attributes not yet supported\n");
-               errno = EINVAL;
-               goto fail;
+       while (attr) {
+               switch (attr->base.attr) {
+               case TDB_ATTRIBUTE_LOG:
+                       tdb->log = attr->log.log_fn;
+                       tdb->log_priv = attr->log.log_private;
+                       break;
+               case TDB_ATTRIBUTE_HASH:
+                       tdb->khash = attr->hash.hash_fn;
+                       tdb->hash_priv = attr->hash.hash_private;
+                       break;
+               default:
+                       tdb->log(tdb, TDB_DEBUG_ERROR, tdb->log_priv,
+                                "tdb_open: unknown attribute type %u\n",
+                                attr->base.attr);
+                       errno = EINVAL;
+                       goto fail;
+               }
+               attr = attr->base.next;
        }
 
        if ((open_flags & O_ACCMODE) == O_WRONLY) {
@@ -402,6 +414,8 @@ static tdb_off_t entry_matches(struct tdb_context *tdb,
        uint64_t keylen;
        const unsigned char *rkey;
 
+       list &= ((1ULL << tdb->header.v.hash_bits) - 1);
+
        off = tdb_read_off(tdb, tdb->header.v.hash_off
                           + list * sizeof(tdb_off_t));
        if (off == 0 || off == TDB_OFF_ERR)
@@ -455,7 +469,8 @@ static int lock_lists(struct tdb_context *tdb,
        tdb_off_t i;
 
        for (i = list; i < list + num; i++) {
-               if (tdb_lock_list(tdb, i, ltype, TDB_LOCK_WAIT) != 0) {
+               if (tdb_lock_list(tdb, i, ltype, TDB_LOCK_WAIT)
+                   == TDB_OFF_ERR) {
                        unlock_lists(tdb, list, i - list, ltype);
                        return -1;
                }
@@ -469,7 +484,7 @@ static int lock_lists(struct tdb_context *tdb,
 static tdb_len_t relock_hash_to_zero(struct tdb_context *tdb,
                                     tdb_off_t start, int ltype)
 {
-       tdb_len_t num, len, pre_locks;
+       tdb_len_t num, len;
 
 again:
        num = 1ULL << tdb->header.v.hash_bits;
@@ -477,39 +492,45 @@ again:
        if (unlikely(len == num - start)) {
                /* We hit the end of the hash range.  Drop lock: we have
                   to lock start of hash first. */
+               tdb_len_t pre_locks;
+
                tdb_unlock_list(tdb, start, ltype);
+
                /* Grab something, so header is stable. */
                if (tdb_lock_list(tdb, 0, ltype, TDB_LOCK_WAIT))
                        return TDB_OFF_ERR;
-               len = tdb_find_zero_off(tdb, hash_off(tdb, 0), num);
-               if (lock_lists(tdb, 1, len, ltype) == -1) {
+               pre_locks = tdb_find_zero_off(tdb, hash_off(tdb, 0), num);
+               /* We want to lock the zero entry as well. */
+               pre_locks++;
+               if (lock_lists(tdb, 1, pre_locks - 1, ltype) == -1) {
                        tdb_unlock_list(tdb, 0, ltype);
                        return TDB_OFF_ERR;
                }
-               pre_locks = len;
-               len = num - start;
-       } else {
-               /* We already have lock on start. */
-               start++;
-               pre_locks = 0;
-       }
-       if (unlikely(lock_lists(tdb, start, len, ltype) == -1)) {
-               if (pre_locks)
+
+               /* Now lock later ones. */
+               if (unlikely(lock_lists(tdb, start, len, ltype) == -1)) {
                        unlock_lists(tdb, 0, pre_locks, ltype);
-               else
+                       return TDB_OFF_ERR;
+               }
+               len += pre_locks;
+       } else {
+               /* We want to lock the zero entry as well. */
+               len++;
+               /* But we already have lock on start. */
+               if (unlikely(lock_lists(tdb, start+1, len-1, ltype) == -1)) {
                        tdb_unlock_list(tdb, start, ltype);
-               return TDB_OFF_ERR;
+                       return TDB_OFF_ERR;
+               }
        }
 
        /* Now, did we lose the race, and it's not zero any more? */
-       if (unlikely(tdb_read_off(tdb, hash_off(tdb, pre_locks + len)) != 0)) {
-               unlock_lists(tdb, 0, pre_locks, ltype);
+       if (unlikely(tdb_read_off(tdb, hash_off(tdb, start + len - 1)) != 0)) {
                /* Leave the start locked, as expected. */
                unlock_lists(tdb, start + 1, len - 1, ltype);
                goto again;
        }
 
-       return pre_locks + len;
+       return len;
 }
 
 /* FIXME: modify, don't rewrite! */
@@ -632,13 +653,14 @@ int tdb_store(struct tdb_context *tdb,
                for (i = start; i < start + num_locks; i++) {
                        off = entry_matches(tdb, i, h, &key, &rec);
                        /* Empty entry or we found it? */
-                       if (off == 0 || off != TDB_OFF_ERR) {
-                               old_bucket = i;
+                       if (off == 0 || off != TDB_OFF_ERR)
                                break;
-                       }
                }
                if (i == start + num_locks)
                        off = 0;
+
+               /* Even if not found, this is where we put the new entry. */
+               old_bucket = i;
        }
 
        /* Now we have lock on this hash bucket. */
@@ -707,7 +729,7 @@ write:
 
        /* FIXME: by simple simulation, this approximated 60% full.
         * Check in real case! */
-       if (unlikely(num_locks > 4 * tdb->header.v.hash_bits - 31))
+       if (unlikely(num_locks > 4 * tdb->header.v.hash_bits - 30))
                enlarge_hash(tdb);
 
        return 0;
index f0a2b897e38032b17b8d00b3efe2cfdded708ebd..81238e23180e936bbad877bf0317c2da49d9d1e6 100644 (file)
@@ -3,6 +3,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <assert.h>
+#include "logging.h"
 
 struct tdb_layout *new_tdb_layout(void)
 {
@@ -208,7 +209,7 @@ struct tdb_context *tdb_layout_get(struct tdb_layout *layout)
 
        mem = malloc(len);
        /* Now populate our header, cribbing from a real TDB header. */
-       tdb = tdb_open(NULL, TDB_INTERNAL, O_RDWR, 0, NULL);
+       tdb = tdb_open(NULL, TDB_INTERNAL, O_RDWR, 0, &tap_log_attr);
        hdr = (void *)mem;
        *hdr = tdb->header;
        hdr->v.generation++;
index 8b057bc662786f5b68761765480ded80da32cb2d..7fd3b1f2345e209b347c7a6e5fc380d38d61ec81 100644 (file)
@@ -7,6 +7,11 @@
 
 unsigned tap_log_messages;
 
+union tdb_attribute tap_log_attr = {
+       .log = { .base = { .attr = TDB_ATTRIBUTE_LOG },
+                .log_fn = tap_log_fn }
+};
+
 void tap_log_fn(struct tdb_context *tdb,
                enum tdb_debug_level level, void *priv,
                const char *fmt, ...)
@@ -19,7 +24,8 @@ void tap_log_fn(struct tdb_context *tdb,
                abort();
        diag("tdb log level %u: %s", level, p);
        free(p);
-       tap_log_messages++;
+       if (level != TDB_DEBUG_TRACE)
+               tap_log_messages++;
        va_end(ap);
 }
 
index b8550df9b19157cd149115f81e7f315b59194a2b..510cfb88562024cf20cdd3f3c7431056e586619c 100644 (file)
@@ -4,7 +4,9 @@
 #include <stdbool.h>
 #include <string.h>
 
-unsigned tap_log_messages;
+extern unsigned tap_log_messages;
+
+extern union tdb_attribute tap_log_attr;
 
 void tap_log_fn(struct tdb_context *tdb,
                enum tdb_debug_level level, void *priv,
index 86645a166ba6f2a742467a3d6596e6e80777d6a6..160bfb7969ce72cc9bc863cc3f0ceaa2d20cc43b 100644 (file)
@@ -41,7 +41,6 @@ int main(int argc, char *argv[])
        tdb_layout_add_freetable(layout, 1, 16, 12, 0);
        tdb_layout_add_free(layout, 1024);
        tdb = tdb_layout_get(layout);
-       tdb->log = tap_log_fn;
        ok1(tdb_check(tdb, NULL, NULL) == 0);
        ok1(free_record_length(tdb, layout->elem[2].base.off) == 1024);
 
@@ -64,7 +63,6 @@ int main(int argc, char *argv[])
        tdb_layout_add_free(layout, 1024);
        tdb_layout_add_used(layout, key, data, 6);
        tdb = tdb_layout_get(layout);
-       tdb->log = tap_log_fn;
        ok1(free_record_length(tdb, layout->elem[2].base.off) == 1024);
        ok1(tdb_check(tdb, NULL, NULL) == 0);
 
@@ -87,7 +85,6 @@ int main(int argc, char *argv[])
        tdb_layout_add_free(layout, 1024);
        tdb_layout_add_free(layout, 512);
        tdb = tdb_layout_get(layout);
-       tdb->log = tap_log_fn;
        ok1(free_record_length(tdb, layout->elem[2].base.off) == 1024);
        ok1(free_record_length(tdb, layout->elem[3].base.off) == 512);
        ok1(tdb_check(tdb, NULL, NULL) == 0);
@@ -113,7 +110,6 @@ int main(int argc, char *argv[])
        tdb_layout_add_free(layout, 512);
        tdb_layout_add_used(layout, key, data, 6);
        tdb = tdb_layout_get(layout);
-       tdb->log = tap_log_fn;
        ok1(free_record_length(tdb, layout->elem[2].base.off) == 1024);
        ok1(free_record_length(tdb, layout->elem[3].base.off) == 512);
        ok1(tdb_check(tdb, NULL, NULL) == 0);
@@ -139,7 +135,6 @@ int main(int argc, char *argv[])
        tdb_layout_add_free(layout, 512);
        tdb_layout_add_free(layout, 32);
        tdb = tdb_layout_get(layout);
-       tdb->log = tap_log_fn;
        ok1(free_record_length(tdb, layout->elem[2].base.off) == 1024);
        ok1(free_record_length(tdb, layout->elem[3].base.off) == 512);
        ok1(free_record_length(tdb, layout->elem[4].base.off) == 32);
@@ -166,7 +161,6 @@ int main(int argc, char *argv[])
        tdb_layout_add_free(layout, 32768);
        tdb_layout_add_free(layout, 30000);
        tdb = tdb_layout_get(layout);
-       tdb->log = tap_log_fn;
        ok1(free_record_length(tdb, layout->elem[2].base.off) == 32768);
        ok1(zone_of(tdb, layout->elem[2].base.off) == 0);
        ok1(free_record_length(tdb, layout->elem[3].base.off) == 30000);
@@ -197,7 +191,6 @@ int main(int argc, char *argv[])
        }
        total -= sizeof(struct tdb_used_record);
        tdb = tdb_layout_get(layout);
-       tdb->log = tap_log_fn;
        ok1(free_record_length(tdb, layout->elem[2].base.off) == 1 << 4);
        ok1(tdb_check(tdb, NULL, NULL) == 0);
 
diff --git a/ccan/tdb2/test/run-delete.c b/ccan/tdb2/test/run-delete.c
new file mode 100644 (file)
index 0000000..b506003
--- /dev/null
@@ -0,0 +1,101 @@
+#include <ccan/tdb2/tdb.c>
+#include <ccan/tdb2/free.c>
+#include <ccan/tdb2/lock.c>
+#include <ccan/tdb2/io.c>
+#include <ccan/tdb2/check.c>
+#include <ccan/tap/tap.h>
+#include "logging.h"
+
+/* We rig the hash so adjacent-numbered records always clash. */
+static uint64_t clash(const void *key, size_t len, uint64_t seed, void *priv)
+{
+       return *(unsigned int *)key / 2;
+}
+
+static void test_val(struct tdb_context *tdb, unsigned int val)
+{
+       unsigned int v;
+       struct tdb_data key = { (unsigned char *)&v, sizeof(v) };
+       struct tdb_data data = { (unsigned char *)&v, sizeof(v) };
+
+       /* Insert an entry, then delete it. */
+       v = val;
+       /* Delete should fail. */
+       ok1(tdb_delete(tdb, key) == -1);
+       ok1(tdb_error(tdb) == TDB_ERR_NOEXIST);
+       ok1(tdb_check(tdb, NULL, NULL) == 0);
+
+       /* Insert should succeed. */
+       ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
+       ok1(tdb_check(tdb, NULL, NULL) == 0);
+
+       /* Delete should succeed. */
+       ok1(tdb_delete(tdb, key) == 0);
+       ok1(tdb_check(tdb, NULL, NULL) == 0);
+
+       /* Re-add it, then add collision. */
+       ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
+       v = val + 1;
+       ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
+       ok1(tdb_check(tdb, NULL, NULL) == 0);
+
+       /* Can find both? */
+       ok1(tdb_fetch(tdb, key).dsize == data.dsize);
+       v = val;
+       ok1(tdb_fetch(tdb, key).dsize == data.dsize);
+
+       /* Delete second one. */
+       v = val + 1;
+       ok1(tdb_delete(tdb, key) == 0);
+       ok1(tdb_check(tdb, NULL, NULL) == 0);
+
+       /* Re-add */
+       ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
+       ok1(tdb_check(tdb, NULL, NULL) == 0);
+
+       /* Now, try deleting first one. */
+       v = val;
+       ok1(tdb_delete(tdb, key) == 0);
+       ok1(tdb_check(tdb, NULL, NULL) == 0);
+
+       /* Can still find second? */
+       v = val + 1;
+       ok1(tdb_fetch(tdb, key).dsize == data.dsize);
+
+       /* Delete that, so we are empty. */
+       ok1(tdb_delete(tdb, key) == 0);
+       ok1(tdb_check(tdb, NULL, NULL) == 0);
+}
+
+int main(int argc, char *argv[])
+{
+       unsigned int i;
+       struct tdb_context *tdb;
+       union tdb_attribute hattr = { .hash = { .base = { TDB_ATTRIBUTE_HASH },
+                                               .hash_fn = clash } };
+       int flags[] = { TDB_INTERNAL, TDB_DEFAULT,
+                       TDB_INTERNAL|TDB_CONVERT, TDB_CONVERT };
+
+       hattr.base.next = &tap_log_attr;
+
+       plan_tests(sizeof(flags) / sizeof(flags[0]) * 44 + 1);
+       for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
+               tdb = tdb_open("run-delete.tdb", flags[i],
+                              O_RDWR|O_CREAT|O_TRUNC, 0600, &hattr);
+               ok1(tdb);
+               if (!tdb)
+                       continue;
+
+               /* Check start of hash table. */
+               test_val(tdb, 0);
+
+               /* Check end of hash table (will wrap around!). */
+               test_val(tdb, ((1 << tdb->header.v.hash_bits) - 1) * 2);
+
+               ok1(!tdb_has_locks(tdb));
+               tdb_close(tdb);
+       }
+
+       ok1(tap_log_messages == 0);
+       return exit_status();
+}
index 539ff51075e4e962b63c882c0b1b7726733fa5ec..9a22820fba9b2ed80ba955be6bcbbbdc6ca2680f 100644 (file)
@@ -16,14 +16,14 @@ int main(int argc, char *argv[])
        plan_tests(sizeof(flags) / sizeof(flags[0]) * 2 + 1);
        for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
                tdb = tdb_open("run-enlarge-hash.tdb", flags[i],
-                              O_RDWR|O_CREAT|O_TRUNC, 0600, NULL);
-               tdb->log = tap_log_fn;
+                              O_RDWR|O_CREAT|O_TRUNC, 0600, &tap_log_attr);
                ok1(tdb);
                if (tdb) {
                        enlarge_hash(tdb);
                        ok1(tdb_check(tdb, NULL, NULL) == 0);
                        tdb_close(tdb);
                }
+               /* FIXME: Test enlarging with hash clash. */
        }
        ok1(tap_log_messages == 0);
        return exit_status();
index 2319e91bb5ef8579cf0c0f517c36b349e8abf4e5..181087e0da8244f1a77c119684edce5828c99b53 100644 (file)
@@ -28,8 +28,7 @@ int main(int argc, char *argv[])
        /* First, lower level expansion tests. */
        for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
                tdb = tdb_open("run-expand.tdb", flags[i],
-                              O_RDWR|O_CREAT|O_TRUNC, 0600, NULL);
-               tdb->log = tap_log_fn;
+                              O_RDWR|O_CREAT|O_TRUNC, 0600, &tap_log_attr);
                ok1(tdb);
                if (!tdb)
                        continue;
@@ -102,8 +101,7 @@ int main(int argc, char *argv[])
        /* Now using tdb_expand. */
        for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
                tdb = tdb_open("run-expand.tdb", flags[i],
-                              O_RDWR|O_CREAT|O_TRUNC, 0600, NULL);
-               tdb->log = tap_log_fn;
+                              O_RDWR|O_CREAT|O_TRUNC, 0600, &tap_log_attr);
                ok1(tdb);
                if (!tdb)
                        continue;
index 45675e2e86b4a5ee8b4b87c1a72998369a40bf0b..2f594abab6e935db2c80be26f9357810775826a2 100644 (file)
@@ -16,8 +16,7 @@ int main(int argc, char *argv[])
        plan_tests(sizeof(flags) / sizeof(flags[0]) * 2 + 1);
        for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
                tdb = tdb_open("run-new_database", flags[i],
-                              O_RDWR|O_CREAT|O_TRUNC, 0600, NULL);
-               tdb->log = tap_log_fn;
+                              O_RDWR|O_CREAT|O_TRUNC, 0600, &tap_log_attr);
                ok1(tdb);
                if (tdb) {
                        ok1(tdb_check(tdb, NULL, NULL) == 0);
index 918833d9037f239a70f2b9c85fe3c072d87a55f6..7e07b9345b78fe8d5670aaf6f7fd21f549363581 100644 (file)
@@ -25,8 +25,7 @@ int main(int argc, char *argv[])
                   * (3 + (1 + (MAX_SIZE/SIZE_STEP)) * 2) + 1);
        for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
                tdb = tdb_open("run-record-expand.tdb", flags[i],
-                              O_RDWR|O_CREAT|O_TRUNC, 0600, NULL);
-               tdb->log = tap_log_fn;
+                              O_RDWR|O_CREAT|O_TRUNC, 0600, &tap_log_attr);
                ok1(tdb);
                if (!tdb)
                        continue;
index eb70011124f7b53c501746880842c3e0b5c04453..f920b763fd3b0a4c9034fee686f70219d4c25849 100644 (file)
@@ -18,8 +18,7 @@ int main(int argc, char *argv[])
        plan_tests(sizeof(flags) / sizeof(flags[0]) * 8 + 1);
        for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
                tdb = tdb_open("run-simple-delete.tdb", flags[i],
-                              O_RDWR|O_CREAT|O_TRUNC, 0600, NULL);
-               tdb->log = tap_log_fn;
+                              O_RDWR|O_CREAT|O_TRUNC, 0600, &tap_log_attr);
                ok1(tdb);
                if (tdb) {
                        /* Delete should fail. */
index dd4f7d40eda615d315505502eed80a8683ade180..7333b421b66f8f0b32b58b65df5ba791a85c8783 100644 (file)
@@ -18,8 +18,7 @@ int main(int argc, char *argv[])
        plan_tests(sizeof(flags) / sizeof(flags[0]) * 8 + 1);
        for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
                tdb = tdb_open("run-simple-fetch.tdb", flags[i],
-                              O_RDWR|O_CREAT|O_TRUNC, 0600, NULL);
-               tdb->log = tap_log_fn;
+                              O_RDWR|O_CREAT|O_TRUNC, 0600, &tap_log_attr);
                ok1(tdb);
                if (tdb) {
                        struct tdb_data d;
index 4e340da1b22c92d30c4a3f2237e20f43baf1f6e5..6a6651d61b4ee4ad54814be6b4bb790676d25d08 100644 (file)
@@ -18,8 +18,7 @@ int main(int argc, char *argv[])
        plan_tests(sizeof(flags) / sizeof(flags[0]) * 9 + 1);
        for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
                tdb = tdb_open("run-simple-store.tdb", flags[i],
-                              O_RDWR|O_CREAT|O_TRUNC, 0600, NULL);
-               tdb->log = tap_log_fn;
+                              O_RDWR|O_CREAT|O_TRUNC, 0600, &tap_log_attr);
                ok1(tdb);
                if (tdb) {
                        /* Modify should fail. */