tdb2: minor optimization for set_header
[ccan] / ccan / tdb2 / free.c
index 9af6f5d04ebf3afb6673fcaf11694e290e52d6df..e6e77bf616666deed3940b07707616485bd29812 100644 (file)
 */
 #include "private.h"
 #include <ccan/likely/likely.h>
 */
 #include "private.h"
 #include <ccan/likely/likely.h>
+#include <ccan/ilog/ilog.h>
 #include <time.h>
 #include <assert.h>
 #include <limits.h>
 
 #include <time.h>
 #include <assert.h>
 #include <limits.h>
 
-/* We have to be able to fit a free record here. */
-#define MIN_DATA_LEN   \
-       (sizeof(struct tdb_free_record) - sizeof(struct tdb_used_record))
-
 static unsigned fls64(uint64_t val)
 {
 static unsigned fls64(uint64_t val)
 {
-#if HAVE_BUILTIN_CLZL
-       if (val <= ULONG_MAX) {
-               /* This is significantly faster! */
-               return val ? sizeof(long) * CHAR_BIT - __builtin_clzl(val) : 0;
-       } else {
-#endif
-       uint64_t r = 64;
-
-       if (!val)
-               return 0;
-       if (!(val & 0xffffffff00000000ull)) {
-               val <<= 32;
-               r -= 32;
-       }
-       if (!(val & 0xffff000000000000ull)) {
-               val <<= 16;
-               r -= 16;
-       }
-       if (!(val & 0xff00000000000000ull)) {
-               val <<= 8;
-               r -= 8;
-       }
-       if (!(val & 0xf000000000000000ull)) {
-               val <<= 4;
-               r -= 4;
-       }
-       if (!(val & 0xc000000000000000ull)) {
-               val <<= 2;
-               r -= 2;
-       }
-       if (!(val & 0x8000000000000000ull)) {
-               val <<= 1;
-               r -= 1;
-       }
-       return r;
-#if HAVE_BUILTIN_CLZL
-       }
-#endif
+       return ilog64(val);
 }
 
 /* In which bucket would we find a particular record size? (ignoring header) */
 }
 
 /* In which bucket would we find a particular record size? (ignoring header) */
@@ -73,15 +33,15 @@ unsigned int size_to_bucket(unsigned int zone_bits, tdb_len_t data_len)
        unsigned int bucket;
 
        /* We can't have records smaller than this. */
        unsigned int bucket;
 
        /* We can't have records smaller than this. */
-       assert(data_len >= MIN_DATA_LEN);
+       assert(data_len >= TDB_MIN_DATA_LEN);
 
        /* Ignoring the header... */
 
        /* Ignoring the header... */
-       if (data_len - MIN_DATA_LEN <= 64) {
-               /* 0 in bucket 0, 8 in bucket 1... 64 in bucket 6. */
-               bucket = (data_len - MIN_DATA_LEN) / 8;
+       if (data_len - TDB_MIN_DATA_LEN <= 64) {
+               /* 0 in bucket 0, 8 in bucket 1... 64 in bucket 8. */
+               bucket = (data_len - TDB_MIN_DATA_LEN) / 8;
        } else {
                /* After that we go power of 2. */
        } else {
                /* After that we go power of 2. */
-               bucket = fls64(data_len - MIN_DATA_LEN) + 2;
+               bucket = fls64(data_len - TDB_MIN_DATA_LEN) + 2;
        }
 
        if (unlikely(bucket > BUCKETS_FOR_ZONE(zone_bits)))
        }
 
        if (unlikely(bucket > BUCKETS_FOR_ZONE(zone_bits)))
@@ -164,18 +124,16 @@ tdb_off_t bucket_off(tdb_off_t zone_off, tdb_off_t bucket)
 /* Returns free_buckets + 1, or list number to search. */
 static tdb_off_t find_free_head(struct tdb_context *tdb, tdb_off_t bucket)
 {
 /* Returns free_buckets + 1, or list number to search. */
 static tdb_off_t find_free_head(struct tdb_context *tdb, tdb_off_t bucket)
 {
-       tdb_off_t b;
-
        /* Speculatively search for a non-zero bucket. */
        /* Speculatively search for a non-zero bucket. */
-       b = tdb_find_nonzero_off(tdb, bucket_off(tdb->zone_off, bucket),
-                                BUCKETS_FOR_ZONE(tdb->zhdr.zone_bits) + 1
-                                - bucket);
-       return bucket + b;
+       return tdb_find_nonzero_off(tdb, bucket_off(tdb->zone_off, 0),
+                                   bucket,
+                                   BUCKETS_FOR_ZONE(tdb->zhdr.zone_bits) + 1);
 }
 
 /* Remove from free bucket. */
 static int remove_from_list(struct tdb_context *tdb,
 }
 
 /* Remove from free bucket. */
 static int remove_from_list(struct tdb_context *tdb,
-                           tdb_off_t b_off, struct tdb_free_record *r)
+                           tdb_off_t b_off, tdb_off_t r_off,
+                           struct tdb_free_record *r)
 {
        tdb_off_t off;
 
 {
        tdb_off_t off;
 
@@ -185,6 +143,16 @@ static int remove_from_list(struct tdb_context *tdb,
        } else {
                off = r->prev + offsetof(struct tdb_free_record, next);
        }
        } else {
                off = r->prev + offsetof(struct tdb_free_record, next);
        }
+
+#ifdef DEBUG
+       if (tdb_read_off(tdb, off) != r_off) {
+               tdb->log(tdb, TDB_DEBUG_FATAL, tdb->log_priv,
+                        "remove_from_list: %llu bad prev in list %llu\n",
+                        (long long)r_off, (long long)b_off);
+               return -1;
+       }
+#endif
+
        /* r->prev->next = r->next */
        if (tdb_write_off(tdb, off, r->next)) {
                return -1;
        /* r->prev->next = r->next */
        if (tdb_write_off(tdb, off, r->next)) {
                return -1;
@@ -193,6 +161,16 @@ static int remove_from_list(struct tdb_context *tdb,
        if (r->next != 0) {
                off = r->next + offsetof(struct tdb_free_record, prev);
                /* r->next->prev = r->prev */
        if (r->next != 0) {
                off = r->next + offsetof(struct tdb_free_record, prev);
                /* r->next->prev = r->prev */
+
+#ifdef DEBUG
+               if (tdb_read_off(tdb, off) != r_off) {
+                       tdb->log(tdb, TDB_DEBUG_FATAL, tdb->log_priv,
+                                "remove_from_list: %llu bad list %llu\n",
+                                (long long)r_off, (long long)b_off);
+                       return -1;
+               }
+#endif
+
                if (tdb_write_off(tdb, off, r->prev)) {
                        return -1;
                }
                if (tdb_write_off(tdb, off, r->prev)) {
                        return -1;
                }
@@ -213,6 +191,17 @@ static int enqueue_in_free(struct tdb_context *tdb,
                return -1;
 
        if (new->next) {
                return -1;
 
        if (new->next) {
+#ifdef DEBUG
+               if (tdb_read_off(tdb,
+                                new->next
+                                + offsetof(struct tdb_free_record, prev))
+                   != 0) {
+                       tdb->log(tdb, TDB_DEBUG_FATAL, tdb->log_priv,
+                                "enqueue_in_free: %llu bad head prev %llu\n",
+                                (long long)new->next, (long long)b_off);
+                       return -1;
+               }
+#endif
                /* next->prev = new. */
                if (tdb_write_off(tdb, new->next
                                  + offsetof(struct tdb_free_record, prev),
                /* next->prev = new. */
                if (tdb_write_off(tdb, new->next
                                  + offsetof(struct tdb_free_record, prev),
@@ -251,6 +240,21 @@ int add_free_record(struct tdb_context *tdb,
        return ret;
 }
 
        return ret;
 }
 
+static size_t adjust_size(size_t keylen, size_t datalen, bool want_extra)
+{
+       size_t size = keylen + datalen;
+
+       /* We want at least 50% growth for data. */
+       if (want_extra)
+               size += datalen/2;
+
+       if (size < TDB_MIN_DATA_LEN)
+               size = TDB_MIN_DATA_LEN;
+
+       /* Round to next uint64_t boundary. */
+       return (size + (sizeof(uint64_t) - 1ULL)) & ~(sizeof(uint64_t) - 1ULL);
+}
+
 /* If we have enough left over to be useful, split that off. */
 static int to_used_record(struct tdb_context *tdb,
                          unsigned int zone_bits,
 /* If we have enough left over to be useful, split that off. */
 static int to_used_record(struct tdb_context *tdb,
                          unsigned int zone_bits,
@@ -315,7 +319,7 @@ static int coalesce(struct tdb_context *tdb,
                        break;
                }
 
                        break;
                }
 
-               if (remove_from_list(tdb, nb_off, r) == -1) {
+               if (remove_from_list(tdb, nb_off, end, r) == -1) {
                        tdb_unlock_free_bucket(tdb, nb_off);
                        goto err;
                }
                        tdb_unlock_free_bucket(tdb, nb_off);
                        goto err;
                }
@@ -341,7 +345,7 @@ static int coalesce(struct tdb_context *tdb,
                goto err;
        }
 
                goto err;
        }
 
-       if (remove_from_list(tdb, b_off, r) == -1)
+       if (remove_from_list(tdb, b_off, off, r) == -1)
                goto err;
 
        /* We have to drop this to avoid deadlocks. */
                goto err;
 
        /* We have to drop this to avoid deadlocks. */
@@ -372,6 +376,9 @@ static tdb_off_t lock_and_alloc(struct tdb_context *tdb,
 again:
        b_off = bucket_off(zone_off, bucket);
 
 again:
        b_off = bucket_off(zone_off, bucket);
 
+       /* FIXME: Try non-blocking wait first, to measure contention.
+        * If we're contented, try switching zones, and don't enlarge zone
+        * next time (we want more zones). */
        /* Lock this bucket. */
        if (tdb_lock_free_bucket(tdb, b_off, TDB_LOCK_WAIT) == -1) {
                return TDB_OFF_ERR;
        /* Lock this bucket. */
        if (tdb_lock_free_bucket(tdb, b_off, TDB_LOCK_WAIT) == -1) {
                return TDB_OFF_ERR;
@@ -428,7 +435,7 @@ again:
        if (best_off) {
        use_best:
                /* We're happy with this size: take it. */
        if (best_off) {
        use_best:
                /* We're happy with this size: take it. */
-               if (remove_from_list(tdb, b_off, &best) != 0)
+               if (remove_from_list(tdb, b_off, best_off, &best) != 0)
                        goto unlock_err;
                tdb_unlock_free_bucket(tdb, b_off);
 
                        goto unlock_err;
                tdb_unlock_free_bucket(tdb, b_off);
 
@@ -466,6 +473,10 @@ static tdb_off_t get_free(struct tdb_context *tdb, size_t size,
        tdb_off_t start_zone = tdb->zone_off, off;
        bool wrapped = false;
 
        tdb_off_t start_zone = tdb->zone_off, off;
        bool wrapped = false;
 
+       /* FIXME: If we don't get a hit in the first bucket we want,
+        * try changing zones for next time.  That should help wear
+        * zones evenly, so we don't need to search all of them before
+        * expanding. */
        while (!wrapped || tdb->zone_off != start_zone) {
                tdb_off_t b;
 
        while (!wrapped || tdb->zone_off != start_zone) {
                tdb_off_t b;
 
@@ -505,15 +516,15 @@ static tdb_off_t get_free(struct tdb_context *tdb, size_t size,
 int set_header(struct tdb_context *tdb,
               struct tdb_used_record *rec,
               uint64_t keylen, uint64_t datalen,
 int set_header(struct tdb_context *tdb,
               struct tdb_used_record *rec,
               uint64_t keylen, uint64_t datalen,
-              uint64_t actuallen, uint64_t hash,
+              uint64_t actuallen, unsigned hashlow,
               unsigned int zone_bits)
 {
        uint64_t keybits = (fls64(keylen) + 1) / 2;
 
               unsigned int zone_bits)
 {
        uint64_t keybits = (fls64(keylen) + 1) / 2;
 
-       /* Use top bits of hash, so it's independent of hash table size. */
+       /* Use bottom bits of hash, so it's independent of hash table size. */
        rec->magic_and_meta
                = zone_bits
        rec->magic_and_meta
                = zone_bits
-               | ((hash >> 59) << 6)
+               | ((hashlow & ((1 << 5)-1)) << 6)
                | ((actuallen - (keylen + datalen)) << 11)
                | (keybits << 43)
                | (TDB_MAGIC << 48);
                | ((actuallen - (keylen + datalen)) << 11)
                | (keybits << 43)
                | (TDB_MAGIC << 48);
@@ -533,53 +544,6 @@ int set_header(struct tdb_context *tdb,
        return 0;
 }
 
        return 0;
 }
 
-static tdb_len_t adjust_size(size_t keylen, size_t datalen, bool growing)
-{
-       tdb_len_t size = keylen + datalen;
-
-       if (size < MIN_DATA_LEN)
-               size = MIN_DATA_LEN;
-
-       /* Overallocate if this is coming from an enlarging store. */
-       if (growing)
-               size += datalen / 2;
-
-       /* Round to next uint64_t boundary. */
-       return (size + (sizeof(uint64_t) - 1ULL)) & ~(sizeof(uint64_t) - 1ULL);
-}
-
-/* If this fails, try tdb_expand. */
-tdb_off_t alloc(struct tdb_context *tdb, size_t keylen, size_t datalen,
-               uint64_t hash, bool growing)
-{
-       tdb_off_t off;
-       tdb_len_t size, actual;
-       struct tdb_used_record rec;
-
-       /* We don't want header to change during this! */
-       assert(tdb->header_uptodate);
-
-       size = adjust_size(keylen, datalen, growing);
-
-       off = get_free(tdb, size, &actual);
-       if (unlikely(off == TDB_OFF_ERR || off == 0))
-               return off;
-
-       /* Some supergiant values can't be encoded. */
-       /* FIXME: Check before, and limit actual in get_free. */
-       if (set_header(tdb, &rec, keylen, datalen, actual, hash,
-                      tdb->zhdr.zone_bits) != 0) {
-               add_free_record(tdb, tdb->zhdr.zone_bits, off,
-                               sizeof(rec) + actual);
-               return TDB_OFF_ERR;
-       }
-
-       if (tdb_write_convert(tdb, off, &rec, sizeof(rec)) != 0)
-               return TDB_OFF_ERR;
-       
-       return off;
-}
-
 static bool zones_happy(struct tdb_context *tdb)
 {
        /* FIXME: look at distribution of zones. */
 static bool zones_happy(struct tdb_context *tdb)
 {
        /* FIXME: look at distribution of zones. */
@@ -594,8 +558,7 @@ static tdb_len_t overhead(unsigned int zone_bits)
 }
 
 /* Expand the database (by adding a zone). */
 }
 
 /* Expand the database (by adding a zone). */
-int tdb_expand(struct tdb_context *tdb, tdb_len_t klen, tdb_len_t dlen,
-              bool growing)
+static int tdb_expand(struct tdb_context *tdb, tdb_len_t size)
 {
        uint64_t old_size;
        tdb_off_t off;
 {
        uint64_t old_size;
        tdb_off_t off;
@@ -606,8 +569,7 @@ int tdb_expand(struct tdb_context *tdb, tdb_len_t klen, tdb_len_t dlen,
        bool enlarge_zone;
 
        /* We need room for the record header too. */
        bool enlarge_zone;
 
        /* We need room for the record header too. */
-       wanted = sizeof(struct tdb_used_record)
-               + (adjust_size(klen, dlen, growing)<<TDB_COMFORT_FACTOR_BITS);
+       wanted = sizeof(struct tdb_used_record) + size;
 
        /* Only one person can expand file at a time. */
        if (tdb_lock_expand(tdb, F_WRLCK) != 0)
 
        /* Only one person can expand file at a time. */
        if (tdb_lock_expand(tdb, F_WRLCK) != 0)
@@ -619,6 +581,7 @@ int tdb_expand(struct tdb_context *tdb, tdb_len_t klen, tdb_len_t dlen,
        if (tdb->map_size != old_size)
                goto success;
 
        if (tdb->map_size != old_size)
                goto success;
 
+       /* FIXME: Tailer is a bogus optimization, remove it. */
        /* zone bits tailer char is protected by EXPAND lock. */
        if (tdb->methods->read(tdb, old_size - 1, &zone_bits, 1) == -1)
                goto fail;
        /* zone bits tailer char is protected by EXPAND lock. */
        if (tdb->methods->read(tdb, old_size - 1, &zone_bits, 1) == -1)
                goto fail;
@@ -645,6 +608,7 @@ int tdb_expand(struct tdb_context *tdb, tdb_len_t klen, tdb_len_t dlen,
        zhdr.zone_bits = zone_bits;
        num_buckets = BUCKETS_FOR_ZONE(zone_bits);
 
        zhdr.zone_bits = zone_bits;
        num_buckets = BUCKETS_FOR_ZONE(zone_bits);
 
+       /* FIXME: I don't think we need to expand to full zone, do we? */
        if (tdb->methods->expand_file(tdb, 1ULL << zone_bits) == -1)
                goto fail;
 
        if (tdb->methods->expand_file(tdb, 1ULL << zone_bits) == -1)
                goto fail;
 
@@ -667,6 +631,10 @@ int tdb_expand(struct tdb_context *tdb, tdb_len_t klen, tdb_len_t dlen,
        if (add_free_record(tdb, zone_bits, off, tdb->map_size-1-off) == -1)
                goto fail;
 
        if (add_free_record(tdb, zone_bits, off, tdb->map_size-1-off) == -1)
                goto fail;
 
+       /* Try allocating from this zone now. */
+       tdb->zone_off = old_size - 1;
+       tdb->zhdr = zhdr;
+
 success:
        tdb_unlock_expand(tdb, F_WRLCK);
        return 0;
 success:
        tdb_unlock_expand(tdb, F_WRLCK);
        return 0;
@@ -675,3 +643,42 @@ fail:
        tdb_unlock_expand(tdb, F_WRLCK);
        return -1;
 }
        tdb_unlock_expand(tdb, F_WRLCK);
        return -1;
 }
+
+/* This won't fail: it will expand the database if it has to. */
+tdb_off_t alloc(struct tdb_context *tdb, size_t keylen, size_t datalen,
+               uint64_t hash, bool growing)
+{
+       tdb_off_t off;
+       tdb_len_t size, actual;
+       struct tdb_used_record rec;
+
+       /* We can't hold pointers during this: we could unmap! */
+       assert(!tdb->direct_access);
+
+       size = adjust_size(keylen, datalen, growing);
+
+again:
+       off = get_free(tdb, size, &actual);
+       if (unlikely(off == TDB_OFF_ERR))
+               return off;
+
+       if (unlikely(off == 0)) {
+               if (tdb_expand(tdb, size) == -1)
+                       return TDB_OFF_ERR;
+               goto again;
+       }
+
+       /* Some supergiant values can't be encoded. */
+       /* FIXME: Check before, and limit actual in get_free. */
+       if (set_header(tdb, &rec, keylen, datalen, actual, hash,
+                      tdb->zhdr.zone_bits) != 0) {
+               add_free_record(tdb, tdb->zhdr.zone_bits, off,
+                               sizeof(rec) + actual);
+               return TDB_OFF_ERR;
+       }
+
+       if (tdb_write_convert(tdb, off, &rec, sizeof(rec)) != 0)
+               return TDB_OFF_ERR;
+       
+       return off;
+}