tdb: defragment the freelist in tdb_allocate_from_freelist()

While we are traversing the freelist anyways, merge a record
with the left if it is also a free list record.

That partially makes up for the fragmentation introduced by
the lack of merging with right records in tdb_free().

Note there is a potential slight downside:
If the left record we merge the current record into was earlier
in the chain and has hence already been met in traverse,
then we can not use the enlarged record even if it might be
a new best fit.

Signed-off-by: Michael Adam <obnox@samba.org>
Reviewed-by: Volker Lendecke <vl@samba.org>
Autobuild-User(master): Volker Lendecke <vl@samba.org>
Autobuild-Date(master): Thu Jun 26 12:16:03 CEST 2014 on sn-devel-104

diff --git a/lib/tdb/common/freelist.c b/lib/tdb/common/freelist.c
index 18b5bf1b67b6b18f1ae92449942f968d6d3fda1d..86fac2ff078ba87c82969e7731f58ced7f713e8a 100644 (file)
--- a/lib/tdb/common/freelist.c
+++ b/lib/tdb/common/freelist.c
@@ -449,6 +449,7 @@ static tdb_off_t tdb_allocate_from_freelist(
                tdb_len_t rec_len;
        } bestfit;
        float multiplier = 1.0;
+       bool merge_created_candidate;
 
        /* over-allocate to reduce fragmentation */
        length *= 1.25;
@@ -458,6 +459,7 @@ static tdb_off_t tdb_allocate_from_freelist(
        length = TDB_ALIGN(length, TDB_ALIGNMENT);
 
  again:
+       merge_created_candidate = false;
        last_ptr = FREELIST_TOP;
 
        /* read in the freelist top */
@@ -474,10 +476,59 @@ static tdb_off_t tdb_allocate_from_freelist(
           issues when faced with a slowly increasing record size.
         */
        while (rec_ptr) {
+               int ret;
+               tdb_off_t left_ptr;
+               struct tdb_record left_rec;
+
                if (tdb_rec_free_read(tdb, rec_ptr, rec) == -1) {
                        return 0;
                }
 
+               ret = check_merge_with_left_record(tdb, rec_ptr, rec,
+                                                  &left_ptr, &left_rec);
+               if (ret == -1) {
+                       return 0;
+               }
+               if (ret == 1) {
+                       /* merged */
+                       rec_ptr = rec->next;
+                       ret = tdb_ofs_write(tdb, last_ptr, &rec->next);
+                       if (ret == -1) {
+                               return 0;
+                       }
+
+                       /*
+                        * We have merged the current record into the left
+                        * neighbour. So our traverse of the freelist will
+                        * skip it and consider the next record in the chain.
+                        *
+                        * But the enlarged left neighbour may be a candidate.
+                        * If it is, we can not directly use it, though.
+                        * The only thing we can do and have to do here is to
+                        * update the current best fit size in the chain if the
+                        * current best fit is the left record. (By that we may
+                        * worsen the best fit we already had, bit this is not a
+                        * problem.)
+                        *
+                        * If the current best fit is not the left record,
+                        * all we can do is remember the fact that a merge
+                        * created a new candidate so that we can trigger
+                        * a second walk of the freelist if at the end of
+                        * the first walk we have not found any fit.
+                        * This way we can avoid expanding the database.
+                        */
+
+                       if (bestfit.rec_ptr == left_ptr) {
+                               bestfit.rec_len = left_rec.rec_len;
+                       }
+
+                       if (left_rec.rec_len > length) {
+                               merge_created_candidate = true;
+                       }
+
+                       continue;
+               }
+
                if (rec->rec_len >= length) {
                        if (bestfit.rec_ptr == 0 ||
                            rec->rec_len < bestfit.rec_len) {
@@ -517,6 +568,10 @@ static tdb_off_t tdb_allocate_from_freelist(
                return newrec_ptr;
        }
 
+       if (merge_created_candidate) {
+               goto again;
+       }
+
        /* we didn't find enough space. See if we can expand the
           database and if we can then try again */
        if (tdb_expand(tdb, length + sizeof(*rec)) == 0)