tdb2: get rid of zones
[ccan] / ccan / tdb2 / free.c
index f5107fadfbd888efae8094b1ff8d3cc4010c3ca8..3fc8bef68dd97cce9c0b0f3b26052fe3f55c3e39 100644 (file)
@@ -27,46 +27,8 @@ static unsigned fls64(uint64_t val)
        return ilog64(val);
 }
 
-static unsigned ffs64(uint64_t val)
-{
-#if HAVE_BUILTIN_FFSLL
-       return __builtin_ffsll(val);
-#else
-       unsigned r = 0;
-
-       if (!val)
-               return 0;
-
-       if (!(val & 0xffffffff)) {
-               val >>= 32;
-               r += 32;
-       }
-       if (!(val & 0xffff)) {
-               val >>= 16;
-               r += 16;
-       }
-       if (!(val & 0xff)) {
-               val >>= 8;
-               r += 8;
-       }
-       if (!(val & 0xf)) {
-               val >>= 4;
-               r += 4;
-       }
-       if (!(val & 0x3)) {
-               val >>= 2;
-               r += 2;
-       }
-       if (!(val & 0x1)) {
-               val >>= 1;
-               r += 1;
-       }
-       return r;
-#endif
-}
-
 /* In which bucket would we find a particular record size? (ignoring header) */
-unsigned int size_to_bucket(unsigned int zone_bits, tdb_len_t data_len)
+unsigned int size_to_bucket(tdb_len_t data_len)
 {
        unsigned int bucket;
 
@@ -82,72 +44,24 @@ unsigned int size_to_bucket(unsigned int zone_bits, tdb_len_t data_len)
                bucket = fls64(data_len - TDB_MIN_DATA_LEN) + 2;
        }
 
-       if (unlikely(bucket > BUCKETS_FOR_ZONE(zone_bits)))
-               bucket = BUCKETS_FOR_ZONE(zone_bits);
+       if (unlikely(bucket >= TDB_FREE_BUCKETS))
+               bucket = TDB_FREE_BUCKETS - 1;
        return bucket;
 }
 
-/* Binary search for the zone for this offset. */
-static tdb_off_t off_to_zone(struct tdb_context *tdb, tdb_off_t off,
-                            struct free_zone_header *zhdr)
-{
-       tdb_off_t start, end;
-
-       start = sizeof(struct tdb_header);
-       end = start + (1ULL << fls64(tdb->map_size - start));
-
-       for (;;) {
-               if (tdb_read_convert(tdb, start, zhdr, sizeof(*zhdr)) == -1)
-                       return TDB_OFF_ERR;
-
-               /* Is it inside this zone? */
-               if (off < start + (1ULL << zhdr->zone_bits))
-                       return start;
-
-               /* In practice, start + end won't overflow. */
-               if (off >= (start + end) / 2)
-                       start = (start + end) / 2;
-               else
-                       end = (start + end) / 2;
-       }
-}
-
-static tdb_off_t last_zone(struct tdb_context *tdb,
-                          struct free_zone_header *zhdr)
-{
-       return off_to_zone(tdb, tdb->map_size - 1, zhdr);
-}
-
-int tdb_zone_init(struct tdb_context *tdb)
+int tdb_flist_init(struct tdb_context *tdb)
 {
-       unsigned int i;
-       uint64_t randoff = 0;
-
-       /* We start in a random zone, to spread the load. */
-       for (i = 0; i < 64; i += fls64(RAND_MAX))
-               randoff ^= ((uint64_t)random()) << i;
-       randoff = sizeof(struct tdb_header)
-               + (randoff % (tdb->map_size - sizeof(struct tdb_header)));
-
-       tdb->zone_off = off_to_zone(tdb, randoff, &tdb->zhdr);
-       if (tdb->zone_off == TDB_OFF_ERR)
+       tdb->flist_off = tdb_read_off(tdb,
+                                     offsetof(struct tdb_header, free_list));
+       if (tdb->flist_off == TDB_OFF_ERR)
                return -1;
        return 0;
 }
 
-/* Where's the header, given a zone size of 1 << zone_bits? */
-static tdb_off_t zone_off(tdb_off_t off, unsigned int zone_bits)
-{
-       off -= sizeof(struct tdb_header);
-       return (off & ~((1ULL << zone_bits) - 1)) + sizeof(struct tdb_header);
-}
-
 /* Offset of a given bucket. */
-/* FIXME: bucket can be "unsigned" everywhere, or even uint8/16. */
-tdb_off_t bucket_off(tdb_off_t zone_off, tdb_off_t bucket)
+tdb_off_t bucket_off(tdb_off_t flist_off, unsigned bucket)
 {
-       return zone_off
-               + sizeof(struct free_zone_header)
+       return flist_off + offsetof(struct tdb_freelist, buckets)
                + bucket * sizeof(tdb_off_t);
 }
 
@@ -155,9 +69,8 @@ tdb_off_t bucket_off(tdb_off_t zone_off, tdb_off_t bucket)
 static tdb_off_t find_free_head(struct tdb_context *tdb, tdb_off_t bucket)
 {
        /* Speculatively search for a non-zero bucket. */
-       return tdb_find_nonzero_off(tdb, bucket_off(tdb->zone_off, 0),
-                                   bucket,
-                                   BUCKETS_FOR_ZONE(tdb->zhdr.zone_bits) + 1);
+       return tdb_find_nonzero_off(tdb, bucket_off(tdb->flist_off, 0),
+                                   bucket, TDB_FREE_BUCKETS);
 }
 
 /* Remove from free bucket. */
@@ -247,7 +160,6 @@ static int enqueue_in_free(struct tdb_context *tdb,
 
 /* List need not be locked. */
 int add_free_record(struct tdb_context *tdb,
-                   unsigned int zone_bits,
                    tdb_off_t off, tdb_len_t len_with_header)
 {
        struct tdb_free_record new;
@@ -255,13 +167,11 @@ int add_free_record(struct tdb_context *tdb,
        int ret;
 
        assert(len_with_header >= sizeof(new));
-       assert(zone_bits < 64);
 
-       new.magic_and_meta = TDB_FREE_MAGIC | zone_bits;
+       new.magic_and_meta = TDB_FREE_MAGIC;
        new.data_len = len_with_header - sizeof(struct tdb_used_record);
 
-       b_off = bucket_off(zone_off(off, zone_bits),
-                          size_to_bucket(zone_bits, new.data_len));
+       b_off = bucket_off(tdb->flist_off, size_to_bucket(new.data_len));
        if (tdb_lock_free_bucket(tdb, b_off, TDB_LOCK_WAIT) != 0)
                return -1;
 
@@ -299,19 +209,14 @@ static size_t record_leftover(size_t keylen, size_t datalen,
 
 /* Note: we unlock the current bucket if we coalesce or fail. */
 static int coalesce(struct tdb_context *tdb,
-                   tdb_off_t zone_off, unsigned zone_bits,
                    tdb_off_t off, tdb_off_t b_off, tdb_len_t data_len)
 {
        struct tdb_free_record pad, *r;
-       tdb_off_t zone_end, end;
+       tdb_off_t end;
 
        end = off + sizeof(struct tdb_used_record) + data_len;
-       zone_end = zone_off + (1ULL << zone_bits);
-
-       if (tdb->methods->oob(tdb, zone_end, true))
-               zone_end = tdb->map_size;
 
-       while (end < zone_end) {
+       while (end < tdb->map_size) {
                tdb_off_t nb_off;
 
                /* FIXME: do tdb_get here and below really win? */
@@ -322,8 +227,8 @@ static int coalesce(struct tdb_context *tdb,
                if (frec_magic(r) != TDB_FREE_MAGIC)
                        break;
 
-               nb_off = bucket_off(zone_off,
-                                   size_to_bucket(zone_bits, r->data_len));
+               /* FIXME: Use flist from record */
+               nb_off = bucket_off(tdb->flist_off,size_to_bucket(r->data_len));
 
                /* We may be violating lock order here, so best effort. */
                if (tdb_lock_free_bucket(tdb, nb_off, TDB_LOCK_NOWAIT) == -1)
@@ -341,8 +246,8 @@ static int coalesce(struct tdb_context *tdb,
                        break;
                }
 
-               if (unlikely(bucket_off(zone_off,
-                                       size_to_bucket(zone_bits, r->data_len))
+               if (unlikely(bucket_off(tdb->flist_off,
+                                       size_to_bucket(r->data_len))
                             != nb_off)) {
                        tdb_unlock_free_bucket(tdb, nb_off);
                        break;
@@ -383,14 +288,14 @@ static int coalesce(struct tdb_context *tdb,
 
        /* We have to drop this to avoid deadlocks, so make sure record
         * doesn't get coalesced by someone else! */
-       r->magic_and_meta = TDB_COALESCING_MAGIC | zone_bits;
+       r->magic_and_meta = TDB_COALESCING_MAGIC;
        r->data_len = end - off - sizeof(struct tdb_used_record);
        if (tdb_access_commit(tdb, r) != 0)
                goto err;
 
        tdb_unlock_free_bucket(tdb, b_off);
 
-       if (add_free_record(tdb, zone_bits, off, end - off) == -1)
+       if (add_free_record(tdb, off, end - off) == -1)
                return -1;
        return 1;
 
@@ -402,8 +307,7 @@ err:
 
 /* We need size bytes to put our key and data in. */
 static tdb_off_t lock_and_alloc(struct tdb_context *tdb,
-                               tdb_off_t zone_off,
-                               unsigned zone_bits,
+                               tdb_off_t flist_off,
                                tdb_off_t bucket,
                                size_t keylen, size_t datalen,
                                bool want_extra,
@@ -415,11 +319,9 @@ static tdb_off_t lock_and_alloc(struct tdb_context *tdb,
        size_t size = adjust_size(keylen, datalen);
 
 again:
-       b_off = bucket_off(zone_off, bucket);
+       b_off = bucket_off(flist_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). */
+       /* FIXME: Try non-blocking wait first, to measure contention. */
        /* Lock this bucket. */
        if (tdb_lock_free_bucket(tdb, b_off, TDB_LOCK_WAIT) == -1) {
                return TDB_OFF_ERR;
@@ -464,8 +366,7 @@ again:
                multiplier *= 1.01;
 
                /* Since we're going slow anyway, try coalescing here. */
-               switch (coalesce(tdb, zone_off, zone_bits, off, b_off,
-                                r->data_len)) {
+               switch (coalesce(tdb, off, b_off, r->data_len)) {
                case -1:
                        /* This has already unlocked on error. */
                        return -1;
@@ -493,7 +394,7 @@ again:
                 * coalesce() could try to merge it! */
                if (set_header(tdb, &rec, keylen, datalen,
                               best.data_len - leftover,
-                              hashlow, zone_bits) != 0)
+                              hashlow) != 0)
                        goto unlock_err;
 
                if (tdb_write_convert(tdb, best_off, &rec, sizeof(rec)) != 0)
@@ -502,7 +403,7 @@ again:
                tdb_unlock_free_bucket(tdb, b_off);
 
                if (leftover) {
-                       if (add_free_record(tdb, zone_bits,
+                       if (add_free_record(tdb,
                                            best_off + sizeof(rec)
                                            + best.data_len - leftover,
                                            leftover))
@@ -519,69 +420,34 @@ unlock_err:
        return TDB_OFF_ERR;
 }
 
-static bool next_zone(struct tdb_context *tdb)
-{
-       tdb_off_t next = tdb->zone_off + (1ULL << tdb->zhdr.zone_bits);
-
-       /* We must have a header. */
-       if (tdb->methods->oob(tdb, next + sizeof(tdb->zhdr), true))
-               return false;
-
-       tdb->zone_off = next;
-       return tdb_read_convert(tdb, next, &tdb->zhdr, sizeof(tdb->zhdr)) == 0;
-}
-
-/* Offset returned is within current zone (which it may alter). */
+/* Get a free block from current free list, or 0 if none. */
 static tdb_off_t get_free(struct tdb_context *tdb,
                          size_t keylen, size_t datalen, bool want_extra,
                          unsigned hashlow)
 {
-       tdb_off_t start_zone = tdb->zone_off, off;
-       bool wrapped = false;
-       size_t size = adjust_size(keylen, datalen);
+       tdb_off_t off;
+       unsigned start_b, b;
 
        /* If they are growing, add 50% to get to higher bucket. */
        if (want_extra)
-               size += datalen / 2;
-
-       /* 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;
-
-               /* Shortcut for really huge allocations... */
-               if ((size >> tdb->zhdr.zone_bits) != 0)
-                       goto next;
-
-               /* Start at exact size bucket, and search up... */
-               b = size_to_bucket(tdb->zhdr.zone_bits, size);
-               for (b = find_free_head(tdb, b);
-                    b <= BUCKETS_FOR_ZONE(tdb->zhdr.zone_bits);
-                    b = find_free_head(tdb, b + 1)) {
-                       /* Try getting one from list. */
-                       off = lock_and_alloc(tdb, tdb->zone_off,
-                                            tdb->zhdr.zone_bits,
-                                            b, keylen, datalen, want_extra,
-                                            hashlow);
-                       if (off == TDB_OFF_ERR)
-                               return TDB_OFF_ERR;
-                       if (off != 0)
-                               return off;
-                       /* Didn't work.  Try next bucket. */
-               }
-
-       next:
-               /* Didn't work, try next zone, if it exists. */
-               if (!next_zone(tdb)) {
-                       wrapped = true;
-                       tdb->zone_off = sizeof(struct tdb_header);
-                       if (tdb_read_convert(tdb, tdb->zone_off,
-                                            &tdb->zhdr, sizeof(tdb->zhdr))) {
-                               return TDB_OFF_ERR;
-                       }
-               }
+               start_b = size_to_bucket(adjust_size(keylen,
+                                                    datalen + datalen / 2));
+       else
+               start_b = size_to_bucket(adjust_size(keylen, datalen));
+
+       /* Start at exact size bucket, and search up... */
+       for (b = find_free_head(tdb, start_b);
+            b < TDB_FREE_BUCKETS;
+            b = find_free_head(tdb, b + 1)) {
+               /* Try getting one from list. */
+               off = lock_and_alloc(tdb, tdb->flist_off,
+                                    b, keylen, datalen, want_extra,
+                                    hashlow);
+               if (off == TDB_OFF_ERR)
+                       return TDB_OFF_ERR;
+               if (off != 0)
+                       return off;
+               /* Didn't work.  Try next bucket. */
        }
        return 0;
 }
@@ -589,15 +455,12 @@ static tdb_off_t get_free(struct tdb_context *tdb,
 int set_header(struct tdb_context *tdb,
               struct tdb_used_record *rec,
               uint64_t keylen, uint64_t datalen,
-              uint64_t actuallen, unsigned hashlow,
-              unsigned int zone_bits)
+              uint64_t actuallen, unsigned hashlow)
 {
        uint64_t keybits = (fls64(keylen) + 1) / 2;
 
        /* Use bottom bits of hash, so it's independent of hash table size. */
-       rec->magic_and_meta
-               = zone_bits
-               | ((hashlow & ((1 << 5)-1)) << 6)
+       rec->magic_and_meta = (hashlow & ((1 << 11)-1))
                | ((actuallen - (keylen + datalen)) << 11)
                | (keybits << 43)
                | (TDB_MAGIC << 48);
@@ -617,26 +480,11 @@ int set_header(struct tdb_context *tdb,
        return 0;
 }
 
-static bool zones_contended(struct tdb_context *tdb)
-{
-       return false;
-}
-
-/* Assume we want buckets up to the comfort factor. */
-static tdb_len_t overhead(unsigned int zone_bits)
-{
-       return sizeof(struct free_zone_header)
-               + (BUCKETS_FOR_ZONE(zone_bits) + 1) * sizeof(tdb_off_t);
-}
-
-/* Expand the database (by adding a zone). */
+/* Expand the database. */
 static int tdb_expand(struct tdb_context *tdb, tdb_len_t size)
 {
        uint64_t old_size;
-       tdb_off_t off;
-       unsigned int num_buckets, zone_bits;
-       tdb_len_t wanted, expand;
-       struct free_zone_header zhdr;
+       tdb_len_t wanted;
 
        /* We need room for the record header too. */
        wanted = sizeof(struct tdb_used_record) + size;
@@ -648,91 +496,20 @@ static int tdb_expand(struct tdb_context *tdb, tdb_len_t size)
        /* Someone else may have expanded the file, so retry. */
        old_size = tdb->map_size;
        tdb->methods->oob(tdb, tdb->map_size + 1, true);
-       if (tdb->map_size != old_size)
-               goto success;
-
-       /* Treat last zone as minimum reasonable zone size. */
-       off = last_zone(tdb, &zhdr);
-       if (off == TDB_OFF_ERR)
-               goto fail;
-
-       /* Zone isn't fully expanded? */
-       if (tdb->map_size < off + (1ULL << zhdr.zone_bits)) {
-               expand = off + (1ULL << zhdr.zone_bits) - tdb->map_size;
-               /* Expand more than we want. */
-               if (expand > (wanted << TDB_COMFORT_FACTOR_BITS))
-                       expand = (wanted << TDB_COMFORT_FACTOR_BITS);
-               if (tdb->methods->expand_file(tdb, expand) == -1)
-                       goto fail;
-               /* We need to drop this lock before adding free record. */
+       if (tdb->map_size != old_size) {
                tdb_unlock_expand(tdb, F_WRLCK);
-
-               /* Allocate from here. */
-               tdb->zone_off = off;
-               tdb->zhdr = zhdr;
-
-               /* FIXME: If this isn't sufficient, we search again... */
-               return add_free_record(tdb, zhdr.zone_bits,
-                                      tdb->map_size - expand, expand);
+               return 0;
        }
 
-       /* We are never allowed to cross a power-of-two boundary, and our
-        * minimum zone size is 1 << INITIAL_ZONE_BITS.
-        *
-        * If our filesize is 128k, we can add a 64k or a 128k zone.  If it's
-        * 192k, we can only add a 64k zone.
-        *
-        * In other words, our max zone size is (1 << (ffs(filesize) - 1)) */
-       zone_bits = ffs64(old_size - sizeof(struct tdb_header)) - 1;
-       assert(zone_bits >= INITIAL_ZONE_BITS);
-
-       /* Big zones generally good, but more zones wanted if contended. */
-       if (zones_contended(tdb)) {
-               /* If it suffices, make zone same size as last one. */
-               if (zhdr.zone_bits < zone_bits
-                   && (1ULL << zhdr.zone_bits) >= overhead(zone_bits)+wanted)
-                       zone_bits = zhdr.zone_bits;
+       if (tdb->methods->expand_file(tdb, wanted*TDB_EXTENSION_FACTOR) == -1) {
+               tdb_unlock_expand(tdb, F_WRLCK);
+               return -1;
        }
 
-       zhdr.zone_bits = zone_bits;
-       num_buckets = BUCKETS_FOR_ZONE(zone_bits);
-
-       /* Expand the file by more than we need right now. */
-       expand = 1ULL << zone_bits;
-       if (expand > overhead(zone_bits) + (wanted << TDB_COMFORT_FACTOR_BITS))
-               expand = overhead(zone_bits)
-                       + (wanted << TDB_COMFORT_FACTOR_BITS);
-
-       if (tdb->methods->expand_file(tdb, expand) == -1)
-               goto fail;
-
-       /* Write new zone header (at old end). */
-       off = old_size;
-       if (tdb_write_convert(tdb, off, &zhdr, sizeof(zhdr)) == -1)
-               goto fail;
-
-       /* Now write empty buckets. */
-       off += sizeof(zhdr);
-       if (zero_out(tdb, off, (num_buckets+1) * sizeof(tdb_off_t)) == -1)
-               goto fail;
-       off += (num_buckets+1) * sizeof(tdb_off_t);
-
-       /* Now add the rest as our free record. */
-       if (add_free_record(tdb, zone_bits, off, expand - overhead(zone_bits))
-           == -1)
-               goto fail;
-
-       /* Try allocating from this zone now. */
-       tdb->zone_off = old_size;
-       tdb->zhdr = zhdr;
-
-success:
+       /* We need to drop this lock before adding free record. */
        tdb_unlock_expand(tdb, F_WRLCK);
-       return 0;
 
-fail:
-       tdb_unlock_expand(tdb, F_WRLCK);
-       return -1;
+       return add_free_record(tdb, old_size, wanted * TDB_EXTENSION_FACTOR);
 }
 
 /* This won't fail: it will expand the database if it has to. */