From: Rusty Russell <rusty@rustcorp.com.au>
Date: Wed, 17 Nov 2010 09:52:19 +0000 (+1030)
Subject: tdb2: only adjust size once when growing
X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=e984ef661368582f7b6e7a8d2a2d709356ac7963

tdb2: only adjust size once when growing

We were adding 50% to datalen twice, so move it out of adjust_size and
make the callers do it.

We also add a test that the heuristic is working at all.
---

diff --git a/ccan/tdb2/free.c b/ccan/tdb2/free.c
index 3917fdaa..48cd9c31 100644
--- a/ccan/tdb2/free.c
+++ b/ccan/tdb2/free.c
@@ -270,14 +270,10 @@ int add_free_record(struct tdb_context *tdb,
 	return ret;
 }
 
-static size_t adjust_size(size_t keylen, size_t datalen, bool want_extra)
+static size_t adjust_size(size_t keylen, size_t datalen)
 {
 	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;
 
@@ -291,13 +287,11 @@ static size_t record_leftover(size_t keylen, size_t datalen,
 {
 	ssize_t leftover;
 
-	/* 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;
+	if (want_extra)
+		datalen += datalen / 2;
+	leftover = total_len - adjust_size(keylen, datalen);
 
-	/* If we want extra anwyay, don't split unless we have 2x size. */
-	if (want_extra && leftover <= datalen / 2)
+	if (leftover < (ssize_t)sizeof(struct tdb_free_record))
 		return 0;
 
 	return leftover;
@@ -418,7 +412,7 @@ static tdb_off_t lock_and_alloc(struct tdb_context *tdb,
 	tdb_off_t off, b_off,best_off;
 	struct tdb_free_record pad, best = { 0 }, *r;
 	double multiplier;
-	size_t size = keylen + datalen;
+	size_t size = adjust_size(keylen, datalen);
 
 again:
 	b_off = bucket_off(zone_off, bucket);
@@ -494,6 +488,7 @@ again:
 		leftover = record_leftover(keylen, datalen, want_extra,
 					   best.data_len);
 
+		assert(keylen + datalen + leftover <= 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,
@@ -543,7 +538,7 @@ static tdb_off_t get_free(struct tdb_context *tdb,
 {
 	tdb_off_t start_zone = tdb->zone_off, off;
 	bool wrapped = false;
-	size_t size = adjust_size(keylen, datalen, want_extra);
+	size_t size = adjust_size(keylen, datalen);
 
 	/* If they are growing, add 50% to get to higher bucket. */
 	if (want_extra)
@@ -754,7 +749,7 @@ tdb_off_t alloc(struct tdb_context *tdb, size_t keylen, size_t datalen,
 		if (likely(off != 0))
 			break;
 
-		if (tdb_expand(tdb, adjust_size(keylen, datalen, growing)))
+		if (tdb_expand(tdb, adjust_size(keylen, datalen)))
 			return TDB_OFF_ERR;
 	}
 
diff --git a/ccan/tdb2/test/run-15-append.c b/ccan/tdb2/test/run-15-append.c
index 3f1fb5b3..51d4ddef 100644
--- a/ccan/tdb2/test/run-15-append.c
+++ b/ccan/tdb2/test/run-15-append.c
@@ -5,16 +5,31 @@
 #include <ccan/tdb2/hash.c>
 #include <ccan/tdb2/check.c>
 #include <ccan/tap/tap.h>
+#include <ccan/ilog/ilog.h>
 #include "logging.h"
 
 #define MAX_SIZE 13100
 #define SIZE_STEP 131
 
+static tdb_off_t tdb_offset(struct tdb_context *tdb, struct tdb_data key)
+{
+	tdb_off_t off;
+	struct tdb_used_record rec;
+	struct hash_info h;
+
+	off = find_and_lock(tdb, key, F_RDLCK, &h, &rec, NULL);
+	if (unlikely(off == TDB_OFF_ERR))
+		return 0;
+	tdb_unlock_hashes(tdb, h.hlock_start, h.hlock_range, F_RDLCK);
+	return off;
+}
+
 int main(int argc, char *argv[])
 {
-	unsigned int i, j;
+	unsigned int i, j, moves;
 	struct tdb_context *tdb;
 	unsigned char *buffer;
+	tdb_off_t oldoff = 0, newoff;
 	int flags[] = { TDB_INTERNAL, TDB_DEFAULT, TDB_NOMMAP,
 			TDB_INTERNAL|TDB_CONVERT, TDB_CONVERT, 
 			TDB_NOMMAP|TDB_CONVERT };
@@ -26,7 +41,7 @@ int main(int argc, char *argv[])
 		buffer[i] = i;
 
 	plan_tests(sizeof(flags) / sizeof(flags[0])
-		   * ((2 + MAX_SIZE/SIZE_STEP * 4) * 2 + 6)
+		   * ((3 + MAX_SIZE/SIZE_STEP * 4) * 2 + 6)
 		   + 1);
 
 	/* Using tdb_store. */
@@ -37,6 +52,7 @@ int main(int argc, char *argv[])
 		if (!tdb)
 			continue;
 
+		moves = 0;
 		for (j = 0; j < MAX_SIZE; j += SIZE_STEP) {
 			data.dptr = buffer;
 			data.dsize = j;
@@ -46,8 +62,14 @@ int main(int argc, char *argv[])
 			ok1(data.dsize == j);
 			ok1(memcmp(data.dptr, buffer, data.dsize) == 0);
 			free(data.dptr);
+			newoff = tdb_offset(tdb, key);
+			if (newoff != oldoff)
+				moves++;
+			oldoff = newoff;
 		}
 		ok1(!tdb_has_locks(tdb));
+		/* We should increase by 50% each time... */
+		ok(moves <= ilog64(j / SIZE_STEP)*2, "Moved %u times", moves);
 		tdb_close(tdb);
 	}
 
@@ -60,6 +82,7 @@ int main(int argc, char *argv[])
 		if (!tdb)
 			continue;
 
+		moves = 0;
 		for (j = 0; j < MAX_SIZE; j += SIZE_STEP) {
 			data.dptr = buffer + prev_len;
 			data.dsize = j - prev_len;
@@ -70,8 +93,14 @@ int main(int argc, char *argv[])
 			ok1(memcmp(data.dptr, buffer, data.dsize) == 0);
 			free(data.dptr);
 			prev_len = data.dsize;
+			newoff = tdb_offset(tdb, key);
+			if (newoff != oldoff)
+				moves++;
+			oldoff = newoff;
 		}
 		ok1(!tdb_has_locks(tdb));
+		/* We should increase by 50% each time... */
+		ok(moves <= ilog64(j / SIZE_STEP)*2, "Moved %u times", moves);
 		tdb_close(tdb);
 	}