tdb: add tdb_freelist_merge_adjacent()

This is intended to be called to reduce the fragmentation in the
freelist. This is to make up the deficiency of the freelist
to be not doubly linked. If the freelist were doubly linked,
we could easily avoid the creation of adjacent freelist entries.
But with the current singly linked list, it is only possible
to cheaply merge a new free record into a freelist entry on the left,
not on the right...

This can be called periodically, e.g. in the vacuuming process
of a ctdb cluster.

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

1 files changed, 59 insertions, 0 deletions

diff --git a/lib/tdb/common/freelist.c b/lib/tdb/common/freelist.c
index 9b508757eb..89ea371cbb 100644
--- a/lib/tdb/common/freelist.c
+++ b/lib/tdb/common/freelist.c
@@ -611,6 +611,65 @@ blocking_freelist_allocate:
 	return ret;
 }
 
+/**
+ * Merge adjacent records in the freelist.
+ */
+static int tdb_freelist_merge_adjacent(struct tdb_context *tdb,
+				       int *count_records, int *count_merged)
+{
+	tdb_off_t cur, next;
+	int count = 0;
+	int merged = 0;
+	int ret;
+
+	ret = tdb_lock(tdb, -1, F_RDLCK);
+	if (ret == -1) {
+		return -1;
+	}
+
+	cur = FREELIST_TOP;
+	while (tdb_ofs_read(tdb, cur, &next) == 0 && next != 0) {
+		tdb_off_t next2;
+
+		count++;
+
+		ret = check_merge_ptr_with_left_record(tdb, next, &next2);
+		if (ret == -1) {
+			goto done;
+		}
+		if (ret == 1) {
+			/*
+			 * merged:
+			 * now let cur->next point to next2 instead of next
+			 */
+
+			ret = tdb_ofs_write(tdb, cur, &next2);
+			if (ret != 0) {
+				goto done;
+			}
+
+			next = next2;
+			merged++;
+		}
+
+		cur = next;
+	}
+
+	if (count_records != NULL) {
+		*count_records = count;
+	}
+
+	if (count_merged != NULL) {
+		*count_merged = merged;
+	}
+
+	ret = 0;
+
+done:
+	tdb_unlock(tdb, -1, F_RDLCK);
+	return ret;
+}
+
 /*
    return the size of the freelist - used to decide if we should repack
 */