X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Ftdb2%2Ffree.c;h=3917fdaa9333c4eea47fbbffa578b4068fbdaacb;hp=361171902680ece2441e698a3b960df6ddb781de;hb=d1383862ad9a74e713dc915d351b74da4db35078;hpb=48038e705f87e54176d76bdcb7a6512a4bfa1a4a diff --git a/ccan/tdb2/free.c b/ccan/tdb2/free.c index 36117190..3917fdaa 100644 --- a/ccan/tdb2/free.c +++ b/ccan/tdb2/free.c @@ -17,53 +17,51 @@ */ #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; + 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 & 0xffffffff00000000ull)) { - val <<= 32; - r -= 32; + + if (!(val & 0xffffffff)) { + val >>= 32; + r += 32; } - if (!(val & 0xffff000000000000ull)) { - val <<= 16; - r -= 16; + if (!(val & 0xffff)) { + val >>= 16; + r += 16; } - if (!(val & 0xff00000000000000ull)) { - val <<= 8; - r -= 8; + if (!(val & 0xff)) { + val >>= 8; + r += 8; } - if (!(val & 0xf000000000000000ull)) { - val <<= 4; - r -= 4; + if (!(val & 0xf)) { + val >>= 4; + r += 4; } - if (!(val & 0xc000000000000000ull)) { - val <<= 2; - r -= 2; + if (!(val & 0x3)) { + val >>= 2; + r += 2; } - if (!(val & 0x8000000000000000ull)) { - val <<= 1; - r -= 1; + if (!(val & 0x1)) { + val >>= 1; + r += 1; } return r; -#if HAVE_BUILTIN_CLZL - } #endif } @@ -73,15 +71,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))) @@ -89,59 +87,51 @@ unsigned int size_to_bucket(unsigned int zone_bits, tdb_len_t data_len) return bucket; } -/* Subtract 1-byte tailer and header. Then round up to next power of 2. */ -static unsigned max_zone_bits(struct tdb_context *tdb) +/* 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) { - return fls64(tdb->map_size-1-sizeof(struct tdb_header)-1) + 1; -} + tdb_off_t start, end; -/* Start by using a random zone to spread the load: returns the offset. */ -static uint64_t random_zone(struct tdb_context *tdb) -{ - struct free_zone_header zhdr; - tdb_off_t off = sizeof(struct tdb_header); - tdb_len_t half_bits; - uint64_t randbits = 0; - unsigned int i; + start = sizeof(struct tdb_header); + end = start + (1ULL << fls64(tdb->map_size - start)); - for (i = 0; i < 64; i += fls64(RAND_MAX)) - randbits ^= ((uint64_t)random()) << i; - - /* FIXME: Does this work? Test! */ - half_bits = max_zone_bits(tdb) - 1; - do { - /* Pick left or right side (not outside file) */ - if ((randbits & 1) - && !tdb->methods->oob(tdb, off + (1ULL << half_bits) - + sizeof(zhdr), true)) { - off += 1ULL << half_bits; - } - randbits >>= 1; - - if (tdb_read_convert(tdb, off, &zhdr, sizeof(zhdr)) == -1) + for (;;) { + if (tdb_read_convert(tdb, start, zhdr, sizeof(*zhdr)) == -1) return TDB_OFF_ERR; - if (zhdr.zone_bits == half_bits) - return off; + /* Is it inside this zone? */ + if (off < start + (1ULL << zhdr->zone_bits)) + return start; - half_bits--; - } while (half_bits >= INITIAL_ZONE_BITS); + /* In practice, start + end won't overflow. */ + if (off >= (start + end) / 2) + start = (start + end) / 2; + else + end = (start + end) / 2; + } +} - tdb->ecode = TDB_ERR_CORRUPT; - tdb->log(tdb, TDB_DEBUG_FATAL, tdb->log_priv, - "random_zone: zone at %llu smaller than %u bits?", - (long long)off, INITIAL_ZONE_BITS); - return TDB_OFF_ERR; +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) { - tdb->zone_off = random_zone(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) return -1; - if (tdb_read_convert(tdb, tdb->zone_off, - &tdb->zhdr, sizeof(tdb->zhdr)) == -1) - return -1; return 0; } @@ -172,7 +162,8 @@ static tdb_off_t find_free_head(struct tdb_context *tdb, tdb_off_t bucket) /* 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; @@ -182,6 +173,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; @@ -190,6 +191,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; } @@ -210,6 +221,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), @@ -233,7 +255,7 @@ int add_free_record(struct tdb_context *tdb, int ret; assert(len_with_header >= sizeof(new)); - assert(zone_bits < (1 << 6)); + assert(zone_bits < 64); new.magic_and_meta = TDB_FREE_MAGIC | zone_bits; new.data_len = len_with_header - sizeof(struct tdb_used_record); @@ -248,30 +270,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. */ @@ -280,9 +309,15 @@ static int coalesce(struct tdb_context *tdb, tdb_off_t off, tdb_off_t b_off, tdb_len_t data_len) { struct tdb_free_record pad, *r; - tdb_off_t end = off + sizeof(struct tdb_used_record) + data_len; + tdb_off_t zone_end, 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_off + (1ULL << zone_bits))) { + while (end < zone_end) { tdb_off_t nb_off; /* FIXME: do tdb_get here and below really win? */ @@ -312,7 +347,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; } @@ -338,10 +380,20 @@ 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; + + r = tdb_access_write(tdb, off, sizeof(*r), true); + if (!r) + goto err; + + /* 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->data_len = end - off - sizeof(struct tdb_used_record); + if (tdb_access_commit(tdb, r) != 0) goto err; - /* We have to drop this to avoid deadlocks. */ tdb_unlock_free_bucket(tdb, b_off); if (add_free_record(tdb, zone_bits, off, end - off) == -1) @@ -359,16 +411,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; @@ -376,8 +433,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. */ @@ -404,7 +465,7 @@ again: } if (best.data_len < size * multiplier && best_off) - goto use_best; + break; multiplier *= 1.01; @@ -423,15 +484,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; } @@ -457,18 +537,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); @@ -478,7 +568,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) @@ -486,6 +577,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; @@ -502,7 +594,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; @@ -510,7 +602,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); @@ -530,10 +622,9 @@ int set_header(struct tdb_context *tdb, return 0; } -static bool zones_happy(struct tdb_context *tdb) +static bool zones_contended(struct tdb_context *tdb) { - /* FIXME: look at distribution of zones. */ - return true; + return false; } /* Assume we want buckets up to the comfort factor. */ @@ -548,11 +639,9 @@ static int tdb_expand(struct tdb_context *tdb, tdb_len_t size) { uint64_t old_size; tdb_off_t off; - uint8_t zone_bits; - unsigned int num_buckets; - tdb_len_t wanted; + unsigned int num_buckets, zone_bits; + tdb_len_t wanted, expand; struct free_zone_header zhdr; - bool enlarge_zone; /* We need room for the record header too. */ wanted = sizeof(struct tdb_used_record) + size; @@ -567,41 +656,63 @@ static int tdb_expand(struct tdb_context *tdb, tdb_len_t size) if (tdb->map_size != old_size) goto success; - /* zone bits tailer char is protected by EXPAND lock. */ - if (tdb->methods->read(tdb, old_size - 1, &zone_bits, 1) == -1) + /* Treat last zone as minimum reasonable zone size. */ + off = last_zone(tdb, &zhdr); + if (off == TDB_OFF_ERR) goto fail; - /* If zones aren't working well, add larger zone if possible. */ - enlarge_zone = !zones_happy(tdb); + /* 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. */ + 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); + } - /* New zone can be between zone_bits or larger if we're on the right - * boundary. */ - for (;;) { - /* Does this fit the allocation comfortably? */ - if ((1ULL << zone_bits) >= overhead(zone_bits) + wanted) { - /* Only let enlarge_zone enlarge us once. */ - if (!enlarge_zone) - break; - enlarge_zone = false; - } - if ((old_size - 1 - sizeof(struct tdb_header)) - & (1 << zone_bits)) - break; - zone_bits++; + /* 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; } zhdr.zone_bits = zone_bits; num_buckets = BUCKETS_FOR_ZONE(zone_bits); - if (tdb->methods->expand_file(tdb, 1ULL << zone_bits) == -1) - goto fail; + /* 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); - /* Write new tailer. */ - if (tdb->methods->write(tdb, tdb->map_size - 1, &zone_bits, 1) == -1) + if (tdb->methods->expand_file(tdb, expand) == -1) goto fail; - /* Write new zone header (just before old tailer). */ - off = old_size - 1; + /* Write new zone header (at old end). */ + off = old_size; if (tdb_write_convert(tdb, off, &zhdr, sizeof(zhdr)) == -1) goto fail; @@ -612,11 +723,12 @@ static int tdb_expand(struct tdb_context *tdb, tdb_len_t size) off += (num_buckets+1) * sizeof(tdb_off_t); /* Now add the rest as our free record. */ - if (add_free_record(tdb, zone_bits, off, tdb->map_size-1-off) == -1) + 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 - 1; + tdb->zone_off = old_size; tdb->zhdr = zhdr; success: @@ -628,56 +740,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; }