From 453d3fe2bdec8e430b85f4cd595a9ad2f8ebcbb3 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Fri, 27 Aug 2010 15:03:41 +0930 Subject: [PATCH] tdb2: split expand into functions and test separately. --- ccan/tdb2/free.c | 198 ++++++++++++++++++++---------------- ccan/tdb2/test/run-expand.c | 120 +++++++++++++++++++--- 2 files changed, 217 insertions(+), 101 deletions(-) diff --git a/ccan/tdb2/free.c b/ccan/tdb2/free.c index f9e81ca4..be2b91f1 100644 --- a/ccan/tdb2/free.c +++ b/ccan/tdb2/free.c @@ -559,92 +559,39 @@ static bool zones_happy(struct tdb_context *tdb) return true; } -/* Expand the database. */ -int tdb_expand(struct tdb_context *tdb, tdb_len_t klen, tdb_len_t dlen, - bool growing) +/* Returns how much extra room we get, or TDB_OFF_ERR. */ +static tdb_len_t expand_to_fill_zones(struct tdb_context *tdb) { - uint64_t new_num_buckets, new_num_zones, new_zone_bits; - uint64_t i, old_num_total, old_num_zones, old_size, old_zone_bits; - tdb_len_t add, freebucket_size, needed; - tdb_off_t off, old_free_off; - const tdb_off_t *oldf; - struct tdb_used_record fhdr; - - /* We need room for the record header too. */ - needed = sizeof(struct tdb_used_record) - + adjust_size(klen, dlen, growing); - - /* tdb_allrecord_lock will update header; did zones change? */ - old_zone_bits = tdb->header.v.zone_bits; - old_num_zones = tdb->header.v.num_zones; - - /* FIXME: this is overkill. An expand lock? */ - if (tdb_allrecord_lock(tdb, F_WRLCK, TDB_LOCK_WAIT, false) == -1) - return -1; - - /* Someone may have expanded for us. */ - if (old_zone_bits != tdb->header.v.zone_bits - || old_num_zones != tdb->header.v.num_zones) - goto success; - - /* They may have also expanded the underlying size (otherwise we'd - * have expanded our mmap to look at those offsets already). */ - old_size = tdb->map_size; - tdb->methods->oob(tdb, tdb->map_size + 1, true); - if (tdb->map_size != old_size) - goto success; - - /* Did we enlarge zones without enlarging file? */ - if (tdb->map_size < tdb->header.v.num_zones<header.v.zone_bits) { - add = (tdb->header.v.num_zones<header.v.zone_bits) - - tdb->map_size; - /* Updates tdb->map_size. */ - if (tdb->methods->expand_file(tdb, add) == -1) - goto fail; - if (add_free_record(tdb, tdb->map_size - add, add) == -1) - goto fail; - if (add >= needed) { - /* Allocate from this zone. */ - tdb->last_zone = zone_of(tdb, tdb->map_size - add); - goto success; - } - } - - /* Slow path. Should we increase the number of buckets? */ - new_num_buckets = tdb->header.v.free_buckets; - if (larger_buckets_might_help(tdb)) - new_num_buckets++; + tdb_len_t add; - /* Now we'll need room for the new free buckets, too. Assume - * worst case (zones expand). */ - needed += sizeof(fhdr) - + ((tdb->header.v.num_zones+1) - * (new_num_buckets+1) * sizeof(tdb_off_t)); + /* We can enlarge zones without enlarging file to match. */ + add = (tdb->header.v.num_zones<header.v.zone_bits) + - tdb->map_size; + if (add <= sizeof(struct tdb_free_record)) + return 0; - /* If we need less that one zone, and they're working well, just add - * another one. */ - if (needed < (1UL<header.v.zone_bits) && zones_happy(tdb)) { - new_num_zones = tdb->header.v.num_zones+1; - new_zone_bits = tdb->header.v.zone_bits; - add = 1ULL << tdb->header.v.zone_bits; - } else { - /* Increase the zone size. */ - new_num_zones = tdb->header.v.num_zones; - new_zone_bits = tdb->header.v.zone_bits+1; - while ((new_num_zones << new_zone_bits) - < tdb->map_size + needed) { - new_zone_bits++; - } + /* Updates tdb->map_size. */ + if (tdb->methods->expand_file(tdb, add) == -1) + return TDB_OFF_ERR; + if (add_free_record(tdb, tdb->map_size - add, add) == -1) + return TDB_OFF_ERR; + return add; +} - /* We expand by enough full zones to meet the need. */ - add = ((tdb->map_size + needed + (1ULL << new_zone_bits)-1) - & ~((1ULL << new_zone_bits)-1)) - - tdb->map_size; - } +static int update_zones(struct tdb_context *tdb, + uint64_t new_num_zones, + uint64_t new_zone_bits, + uint64_t new_num_buckets, + tdb_len_t add) +{ + tdb_len_t freebucket_size; + const tdb_off_t *oldf; + tdb_off_t i, off, old_num_total, old_free_off; + struct tdb_used_record fhdr; /* Updates tdb->map_size. */ if (tdb->methods->expand_file(tdb, add) == -1) - goto fail; + return -1; /* Use first part as new free bucket array. */ off = tdb->map_size - add; @@ -653,9 +600,9 @@ int tdb_expand(struct tdb_context *tdb, tdb_len_t klen, tdb_len_t dlen, /* Write header. */ if (set_header(tdb, &fhdr, 0, freebucket_size, freebucket_size, 0)) - goto fail; + return -1; if (tdb_write_convert(tdb, off, &fhdr, sizeof(fhdr)) == -1) - goto fail; + return -1; /* Adjust off to point to start of buckets, add to be remainder. */ add -= freebucket_size + sizeof(fhdr); @@ -667,7 +614,7 @@ int tdb_expand(struct tdb_context *tdb, tdb_len_t klen, tdb_len_t dlen, oldf = tdb_access_read(tdb, old_free_off, old_num_total * sizeof(tdb_off_t), true); if (!oldf) - goto fail; + return -1; /* Switch to using our new zone. */ if (zero_out(tdb, off, freebucket_size) == -1) @@ -716,14 +663,95 @@ int tdb_expand(struct tdb_context *tdb, tdb_len_t klen, tdb_len_t dlen, /* Start allocating from where the new space is. */ tdb->last_zone = zone_of(tdb, tdb->map_size - add); tdb_access_release(tdb, oldf); - if (write_header(tdb) == -1) + return write_header(tdb); + +fail_release: + tdb_access_release(tdb, oldf); + return -1; +} + +/* Expand the database. */ +int tdb_expand(struct tdb_context *tdb, tdb_len_t klen, tdb_len_t dlen, + bool growing) +{ + uint64_t new_num_buckets, new_num_zones, new_zone_bits; + uint64_t old_num_zones, old_size, old_zone_bits; + tdb_len_t add, needed; + + /* We need room for the record header too. */ + needed = sizeof(struct tdb_used_record) + + adjust_size(klen, dlen, growing); + + /* tdb_allrecord_lock will update header; did zones change? */ + old_zone_bits = tdb->header.v.zone_bits; + old_num_zones = tdb->header.v.num_zones; + + /* FIXME: this is overkill. An expand lock? */ + if (tdb_allrecord_lock(tdb, F_WRLCK, TDB_LOCK_WAIT, false) == -1) + return -1; + + /* Someone may have expanded for us. */ + if (old_zone_bits != tdb->header.v.zone_bits + || old_num_zones != tdb->header.v.num_zones) + goto success; + + /* They may have also expanded the underlying size (otherwise we'd + * have expanded our mmap to look at those offsets already). */ + old_size = tdb->map_size; + tdb->methods->oob(tdb, tdb->map_size + 1, true); + if (tdb->map_size != old_size) + goto success; + + add = expand_to_fill_zones(tdb); + if (add == TDB_OFF_ERR) goto fail; + + if (add >= needed) { + /* Allocate from this zone. */ + tdb->last_zone = zone_of(tdb, tdb->map_size - add); + goto success; + } + + /* Slow path. Should we increase the number of buckets? */ + new_num_buckets = tdb->header.v.free_buckets; + if (larger_buckets_might_help(tdb)) + new_num_buckets++; + + /* Now we'll need room for the new free buckets, too. Assume + * worst case (zones expand). */ + needed += sizeof(struct tdb_used_record) + + ((tdb->header.v.num_zones+1) + * (new_num_buckets+1) * sizeof(tdb_off_t)); + + /* If we need less that one zone, and they're working well, just add + * another one. */ + if (needed < (1UL<header.v.zone_bits) && zones_happy(tdb)) { + new_num_zones = tdb->header.v.num_zones+1; + new_zone_bits = tdb->header.v.zone_bits; + add = 1ULL << tdb->header.v.zone_bits; + } else { + /* Increase the zone size. */ + new_num_zones = tdb->header.v.num_zones; + new_zone_bits = tdb->header.v.zone_bits+1; + while ((new_num_zones << new_zone_bits) + < tdb->map_size + needed) { + new_zone_bits++; + } + + /* We expand by enough full zones to meet the need. */ + add = ((tdb->map_size + needed + (1ULL << new_zone_bits)-1) + & ~((1ULL << new_zone_bits)-1)) + - tdb->map_size; + } + + if (update_zones(tdb, new_num_zones, new_zone_bits, new_num_buckets, + add) == -1) + goto fail; + success: tdb_allrecord_unlock(tdb, F_WRLCK); return 0; -fail_release: - tdb_access_release(tdb, oldf); fail: tdb_allrecord_unlock(tdb, F_WRLCK); return -1; diff --git a/ccan/tdb2/test/run-expand.c b/ccan/tdb2/test/run-expand.c index ef2955cb..7785969c 100644 --- a/ccan/tdb2/test/run-expand.c +++ b/ccan/tdb2/test/run-expand.c @@ -6,35 +6,123 @@ #include #include "logging.h" +/* Release lock to check db. */ +static void check(struct tdb_context *tdb) +{ + tdb_allrecord_unlock(tdb, F_WRLCK); + ok1(tdb_check(tdb, NULL, NULL) == 0); + ok1(tdb_allrecord_lock(tdb, F_WRLCK, TDB_LOCK_WAIT, false) == 0); +} + int main(int argc, char *argv[]) { unsigned int i; + tdb_off_t off; + uint64_t val, buckets; struct tdb_context *tdb; int flags[] = { TDB_INTERNAL, TDB_DEFAULT, TDB_INTERNAL|TDB_CONVERT, TDB_CONVERT }; - plan_tests(sizeof(flags) / sizeof(flags[0]) * 10 + 1); + plan_tests(sizeof(flags) / sizeof(flags[0]) * 40 + 1); + + /* First, lower level expansion tests. */ + for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) { + tdb = tdb_open("/tmp/run-new_database.tdb", flags[i], + O_RDWR|O_CREAT|O_TRUNC, 0600, NULL); + tdb->log = tap_log_fn; + ok1(tdb); + if (!tdb) + continue; + + ok1(tdb_allrecord_lock(tdb, F_WRLCK, TDB_LOCK_WAIT, false) + == 0); + + /* Expanding file is pretty easy. */ + off = expand_to_fill_zones(tdb); + ok1(off > 0 && off != TDB_OFF_ERR); + check(tdb); + + /* Second expand should do nothing. */ + ok1(expand_to_fill_zones(tdb) == 0); + check(tdb); + + /* Now, try adding a zone. */ + val = tdb->header.v.num_zones + 1; + ok1(update_zones(tdb, val, + tdb->header.v.zone_bits, + tdb->header.v.free_buckets, + 1ULL << tdb->header.v.zone_bits) == 0); + ok1(tdb->header.v.num_zones == val); + check(tdb); + + /* Now, try doubling zone size. */ + val = tdb->header.v.zone_bits + 1; + ok1(update_zones(tdb, tdb->header.v.num_zones, + val, + tdb->header.v.free_buckets, + 1ULL << val) == 0); + ok1(tdb->header.v.zone_bits == val); + check(tdb); + + /* Now, try adding a zone, and a bucket. */ + val = tdb->header.v.num_zones + 1; + buckets = tdb->header.v.free_buckets + 1; + ok1(update_zones(tdb, val, + tdb->header.v.zone_bits, + buckets, + 1ULL << tdb->header.v.zone_bits) == 0); + ok1(tdb->header.v.num_zones == val); + ok1(tdb->header.v.free_buckets == buckets); + check(tdb); + + /* Now, try doubling zone size, and adding a bucket. */ + val = tdb->header.v.zone_bits + 1; + buckets = tdb->header.v.free_buckets + 1; + ok1(update_zones(tdb, tdb->header.v.num_zones, + val, + buckets, + 1ULL << val) == 0); + ok1(tdb->header.v.zone_bits == val); + ok1(tdb->header.v.free_buckets == buckets); + check(tdb); + + /* Now, try massive zone increase. */ + val = tdb->header.v.zone_bits + 4; + ok1(update_zones(tdb, tdb->header.v.num_zones, + val, + tdb->header.v.free_buckets, + 1ULL << val) == 0); + ok1(tdb->header.v.zone_bits == val); + check(tdb); + + tdb_allrecord_unlock(tdb, F_WRLCK); + tdb_close(tdb); + } + + /* Now using tdb_expand. */ for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) { tdb = tdb_open("/tmp/run-new_database.tdb", flags[i], O_RDWR|O_CREAT|O_TRUNC, 0600, NULL); tdb->log = tap_log_fn; ok1(tdb); - if (tdb) { - /* First expand (expand file to fill zone). */ - ok1(tdb_expand(tdb, 1, 1, false) == 0); - ok1(tdb->header.v.num_zones == 1); - ok1(tdb_check(tdb, NULL, NULL) == 0); - /* Little expand (extra zone). */ - ok1(tdb_expand(tdb, 1, 1, false) == 0); - ok1(tdb->header.v.num_zones == 2); - ok1(tdb_check(tdb, NULL, NULL) == 0); - /* Big expand (enlarge zones) */ - ok1(tdb_expand(tdb, 1, 4096, false) == 0); - ok1(tdb->header.v.num_zones == 2); - ok1(tdb_check(tdb, NULL, NULL) == 0); - tdb_close(tdb); - } + if (!tdb) + continue; + + /* First expand (expand file to fill zone). */ + ok1(tdb_expand(tdb, 1, 1, false) == 0); + ok1(tdb->header.v.num_zones == 1); + ok1(tdb_check(tdb, NULL, NULL) == 0); + /* Little expand (extra zone). */ + ok1(tdb_expand(tdb, 1, 1, false) == 0); + ok1(tdb->header.v.num_zones == 2); + ok1(tdb_check(tdb, NULL, NULL) == 0); + /* Big expand (enlarge zones) */ + ok1(tdb_expand(tdb, 1, 4096, false) == 0); + ok1(tdb->header.v.num_zones == 2); + ok1(tdb_check(tdb, NULL, NULL) == 0); + tdb_close(tdb); } + ok1(tap_log_messages == 0); return exit_status(); } -- 2.39.2