X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Ftdb2%2Ffree.c;h=df2792ecf19da0841e732bb764cdfd40bafa1880;hb=d2a4d6b49bc260bd0979965f4e4ef62b40b19efe;hp=565bc69e03570d5393dd45c0dcec43f8cf7a2ef5;hpb=6804501c350181dea8f531142b28c620b70edbd9;p=ccan diff --git a/ccan/tdb2/free.c b/ccan/tdb2/free.c index 565bc69e..df2792ec 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,30 +240,37 @@ 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, - tdb_off_t off, - tdb_len_t needed, - tdb_len_t total_len, - tdb_len_t *actual) +static size_t record_leftover(size_t keylen, size_t datalen, + bool want_extra, size_t total_len) { - struct tdb_used_record used; - tdb_len_t leftover; + ssize_t leftover; - leftover = total_len - needed; - if (leftover < sizeof(struct tdb_free_record)) - leftover = 0; + /* We might *want* extra, but not have it, so leftover is negative. */ + leftover = total_len - adjust_size(keylen, datalen, want_extra); + if (leftover < (ssize_t)sizeof(struct tdb_free_record)) + return 0; - *actual = total_len - leftover; + /* If we want extra anwyay, don't split unless we have 2x size. */ + if (want_extra && leftover <= datalen / 2) + return 0; - if (leftover) { - if (add_free_record(tdb, zone_bits, - off + sizeof(used) + *actual, - total_len - needed)) - return -1; - } - return 0; + return leftover; } /* Note: we unlock the current bucket if we coalesce or fail. */ @@ -315,7 +311,14 @@ static int coalesce(struct tdb_context *tdb, break; } - if (remove_from_list(tdb, nb_off, r) == -1) { + if (unlikely(bucket_off(zone_off, + size_to_bucket(zone_bits, r->data_len)) + != nb_off)) { + tdb_unlock_free_bucket(tdb, nb_off); + break; + } + + if (remove_from_list(tdb, nb_off, end, r) == -1) { tdb_unlock_free_bucket(tdb, nb_off); goto err; } @@ -341,7 +344,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. */ @@ -362,16 +365,21 @@ static tdb_off_t lock_and_alloc(struct tdb_context *tdb, tdb_off_t zone_off, unsigned zone_bits, tdb_off_t bucket, - size_t size, - tdb_len_t *actual) + size_t keylen, size_t datalen, + bool want_extra, + unsigned hashlow) { tdb_off_t off, b_off,best_off; struct tdb_free_record pad, best = { 0 }, *r; double multiplier; + size_t size = keylen + datalen; 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; @@ -379,8 +387,12 @@ again: best.data_len = -1ULL; best_off = 0; - /* FIXME: Start with larger multiplier if we're growing. */ - multiplier = 1.0; + + /* Get slack if we're after extra. */ + if (want_extra) + multiplier = 1.5; + else + multiplier = 1.0; /* Walk the list to see if any are large enough, getting less fussy * as we go. */ @@ -407,7 +419,7 @@ again: } if (best.data_len < size * multiplier && best_off) - goto use_best; + break; multiplier *= 1.01; @@ -426,15 +438,34 @@ again: /* If we found anything at all, use it. */ if (best_off) { - use_best: + struct tdb_used_record rec; + size_t leftover; + /* 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; + + leftover = record_leftover(keylen, datalen, want_extra, + best.data_len); + + /* We need to mark non-free before we drop lock, otherwise + * coalesce() could try to merge it! */ + if (set_header(tdb, &rec, keylen, datalen, + best.data_len - leftover, + hashlow, zone_bits) != 0) + goto unlock_err; + + if (tdb_write_convert(tdb, best_off, &rec, sizeof(rec)) != 0) + goto unlock_err; + tdb_unlock_free_bucket(tdb, b_off); - if (to_used_record(tdb, zone_bits, best_off, size, - best.data_len, actual)) { - return -1; + if (leftover) { + if (add_free_record(tdb, zone_bits, + best_off + sizeof(rec) + + best.data_len - leftover, + leftover)) + return TDB_OFF_ERR; } return best_off; } @@ -460,18 +491,28 @@ static bool next_zone(struct tdb_context *tdb) } /* Offset returned is within current zone (which it may alter). */ -static tdb_off_t get_free(struct tdb_context *tdb, size_t size, - tdb_len_t *actual) +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, want_extra); + + /* 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) - continue; + goto next; /* Start at exact size bucket, and search up... */ b = size_to_bucket(tdb->zhdr.zone_bits, size); @@ -481,7 +522,8 @@ static tdb_off_t get_free(struct tdb_context *tdb, size_t size, /* Try getting one from list. */ off = lock_and_alloc(tdb, tdb->zone_off, tdb->zhdr.zone_bits, - b, size, actual); + b, keylen, datalen, want_extra, + hashlow); if (off == TDB_OFF_ERR) return TDB_OFF_ERR; if (off != 0) @@ -489,6 +531,7 @@ static tdb_off_t get_free(struct tdb_context *tdb, size_t size, /* Didn't work. Try next bucket. */ } + next: /* Didn't work, try next zone, if it exists. */ if (!next_zone(tdb)) { wrapped = true; @@ -505,7 +548,7 @@ 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; @@ -513,7 +556,7 @@ int set_header(struct tdb_context *tdb, /* Use bottom bits of hash, so it's independent of hash table size. */ rec->magic_and_meta = zone_bits - | ((hash & ((1 << 5)-1)) << 6) + | ((hashlow & ((1 << 5)-1)) << 6) | ((actuallen - (keylen + datalen)) << 11) | (keybits << 43) | (TDB_MAGIC << 48); @@ -570,6 +613,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 +640,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,56 +676,23 @@ 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) { 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; + for (;;) { + off = get_free(tdb, keylen, datalen, growing, hash); + if (likely(off != 0)) + break; - if (unlikely(off == 0)) { - if (tdb_expand(tdb, size) == -1) + if (tdb_expand(tdb, adjust_size(keylen, datalen, growing))) 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; }