tdb: Do a best fit search for dead records

Hash chains are (or can be made) short enough that a full search for the
best-fitting dead record is feasible. The freelist can become much longer,
there we don't do the full search but accept records which are too large.

Signed-off-by: Volker Lendecke <vl@samba.org>
Reviewed-by: Michael Adam <obnox@samba.org>
Reviewed-by: Stefan Metzmacher <metze@samba.org>

diff --git a/lib/tdb/common/tdb.c b/lib/tdb/common/tdb.c
index 634a5526d71893ecfd8b4f99ab540c0279bb3707..8242d2bb3fd3dda7989abe5689cf37a764a6eeee 100644 (file)
--- a/lib/tdb/common/tdb.c
+++ b/lib/tdb/common/tdb.c
@@ -449,6 +449,8 @@ static tdb_off_t tdb_find_dead(struct tdb_context *tdb, uint32_t hash,
                               struct tdb_record *r, tdb_len_t length)
 {
        tdb_off_t rec_ptr;
+       tdb_off_t best_rec_ptr = 0;
+       struct tdb_record best = { .rec_len = UINT32_MAX };
 
        /* read in the hash top */
        if (tdb_ofs_read(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1)
@@ -459,16 +461,20 @@ static tdb_off_t tdb_find_dead(struct tdb_context *tdb, uint32_t hash,
                if (tdb_rec_read(tdb, rec_ptr, r) == -1)
                        return 0;
 
-               if (TDB_DEAD(r) && r->rec_len >= length) {
-                       /*
-                        * First fit for simple coding, TODO: change to best
-                        * fit
-                        */
-                       return rec_ptr;
+               if (TDB_DEAD(r) && (r->rec_len >= length) &&
+                   (r->rec_len < best.rec_len)) {
+                       best_rec_ptr = rec_ptr;
+                       best = *r;
                }
                rec_ptr = r->next;
        }
-       return 0;
+
+       if (best.rec_len == UINT32_MAX) {
+               return 0;
+       }
+
+       *r = best;
+       return best_rec_ptr;
 }
 
 static int _tdb_store(struct tdb_context *tdb, TDB_DATA key,