From 1444b09cd357c145b6e3fdb1bce3b6ace6862f56 Mon Sep 17 00:00:00 2001
From: Rusty Russell <rusty@rustcorp.com.au>
Date: Fri, 25 Mar 2011 16:09:05 +1030
Subject: [PATCH 1/1] tdb2: fix traversal bug in free list lock_and_alloc()

We keep looking even if the current best is exactly right.  This is
really bad, because our smaller free lists hold exactly one size: with
this bug we iterate to the end of the list before hitting the end and
deciding we can use it after all.

Before:
	$ ./speed --transaction --no-sync 2000000
	Adding 2000000 records:  1179 ns (93594224 bytes)
	Finding 2000000 records:  694 ns (93594224 bytes)
	Missing 2000000 records:  429 ns (93594224 bytes)
	Traversing 2000000 records:  519 ns (93594224 bytes)
	Deleting 2000000 records:  896 ns (93594224 bytes)
	Re-adding 2000000 records:  1129 ns (93594224 bytes)
	Appending 2000000 records:  1713 ns (182801232 bytes)
	Churning 2000000 records:  32612 ns (182801232 bytes)

After:
	$ ./speed --transaction --no-sync 2000000
	Adding 2000000 records:  1195 ns (93594224 bytes)
	Finding 2000000 records:  719 ns (93594224 bytes)
	Missing 2000000 records:  429 ns (93594224 bytes)
	Traversing 2000000 records:  523 ns (93594224 bytes)
	Deleting 2000000 records:  901 ns (93594224 bytes)
	Re-adding 2000000 records:  1032 ns (93594224 bytes)
	Appending 2000000 records:  1711 ns (182801232 bytes)
	Churning 2000000 records:  3233 ns (182801232 bytes)
---
 ccan/tdb2/free.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/ccan/tdb2/free.c b/ccan/tdb2/free.c
index 7ede2461..631eeb30 100644
--- a/ccan/tdb2/free.c
+++ b/ccan/tdb2/free.c
@@ -471,7 +471,7 @@ again:
 			best = *r;
 		}
 
-		if (frec_len(&best) < size * multiplier && best_off) {
+		if (frec_len(&best) <= size * multiplier && best_off) {
 			tdb_access_release(tdb, r);
 			break;
 		}
-- 
2.39.2