X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftdb2%2Ffree.c;h=e6e77bf616666deed3940b07707616485bd29812;hp=9af6f5d04ebf3afb6673fcaf11694e290e52d6df;hb=8afb9681b3be7149cf8913a5aefe915194fd20f7;hpb=1a24a8708494668c07e5c02284bfc2ef3b09603b;ds=inline diff --git a/ccan/tdb2/free.c b/ccan/tdb2/free.c index 9af6f5d0..e6e77bf6 100644 --- a/ccan/tdb2/free.c +++ b/ccan/tdb2/free.c @@ -17,54 +17,14 @@ */ #include "private.h" #include +#include #include #include #include -/* 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) { -#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) */ @@ -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. */ - assert(data_len >= MIN_DATA_LEN); + assert(data_len >= TDB_MIN_DATA_LEN); /* 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. */ - 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))) @@ -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) { - tdb_off_t b; - /* 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, - 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; @@ -185,6 +143,16 @@ static int remove_from_list(struct tdb_context *tdb, } 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; @@ -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 */ + +#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; } @@ -213,6 +191,17 @@ static int enqueue_in_free(struct tdb_context *tdb, 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), @@ -251,6 +240,21 @@ int add_free_record(struct tdb_context *tdb, 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, @@ -315,7 +319,7 @@ static int coalesce(struct tdb_context *tdb, 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; } @@ -341,7 +345,7 @@ static int coalesce(struct tdb_context *tdb, 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. */ @@ -372,6 +376,9 @@ static tdb_off_t lock_and_alloc(struct tdb_context *tdb, 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; @@ -428,7 +435,7 @@ again: 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); @@ -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; + /* 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; @@ -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, - uint64_t actuallen, uint64_t hash, + uint64_t actuallen, unsigned hashlow, 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 - | ((hash >> 59) << 6) + | ((hashlow & ((1 << 5)-1)) << 6) | ((actuallen - (keylen + datalen)) << 11) | (keybits << 43) | (TDB_MAGIC << 48); @@ -533,53 +544,6 @@ int set_header(struct tdb_context *tdb, 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. */ @@ -594,8 +558,7 @@ static tdb_len_t overhead(unsigned int zone_bits) } /* 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; @@ -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. */ - wanted = sizeof(struct tdb_used_record) - + (adjust_size(klen, dlen, growing)<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; @@ -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); + /* 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; @@ -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; + /* Try allocating from this zone now. */ + tdb->zone_off = old_size - 1; + tdb->zhdr = zhdr; + success: tdb_unlock_expand(tdb, F_WRLCK); return 0; @@ -675,3 +643,42 @@ fail: 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; +}