X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftdb2%2Ffree.c;h=e6e77bf616666deed3940b07707616485bd29812;hp=efc29e884ea2078c54ed28616b9d0cdce1228ac1;hb=8afb9681b3be7149cf8913a5aefe915194fd20f7;hpb=84a19b9bada57df46adc76d46672546a675b00a7 diff --git a/ccan/tdb2/free.c b/ccan/tdb2/free.c index efc29e88..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); @@ -570,6 +581,7 @@ static int tdb_expand(struct tdb_context *tdb, tdb_len_t size) 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; @@ -596,6 +608,7 @@ static int tdb_expand(struct tdb_context *tdb, tdb_len_t size) 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; @@ -631,21 +644,6 @@ fail: return -1; } -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); -} - /* 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) @@ -654,8 +652,8 @@ tdb_off_t alloc(struct tdb_context *tdb, size_t keylen, size_t datalen, tdb_len_t size, actual; struct tdb_used_record rec; - /* We don't want header to change during this! */ - assert(tdb->header_uptodate); + /* We can't hold pointers during this: we could unmap! */ + assert(!tdb->direct_access); size = adjust_size(keylen, datalen, growing);