tdb2: fix traversal bug in free list lock_and_alloc()
authorRusty Russell <rusty@rustcorp.com.au>
Fri, 25 Mar 2011 05:39:05 +0000 (16:09 +1030)
committerRusty Russell <rusty@rustcorp.com.au>
Fri, 25 Mar 2011 05:39:05 +0000 (16:09 +1030)
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

index 7ede24616efc78df4e16eda260ace518bbd88755..631eeb3051a2babc71c72c3ed9081c35e9b82417 100644 (file)
@@ -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;
                }