X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftdb2%2Ffree.c;h=3fc8bef68dd97cce9c0b0f3b26052fe3f55c3e39;hp=f5107fadfbd888efae8094b1ff8d3cc4010c3ca8;hb=d70577b6aff24ccf6815896509dabb8c9ac07904;hpb=2ecf943a99c427b10a998f0285dd184b1a25ac65 diff --git a/ccan/tdb2/free.c b/ccan/tdb2/free.c index f5107fad..3fc8bef6 100644 --- a/ccan/tdb2/free.c +++ b/ccan/tdb2/free.c @@ -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. */