r452: move from first-fit to best-fit in tdb record allocation. For a

situation where we are continually increasing the size of a record
(such as ldb index records) this reduces the resulting tdb size by a
factor of over 100x, due to reductions in fragmentation. It appears to
have no noticable effect on the speed in other cases.
(This used to be commit b61d7f8bbc0c01d648ce204ffb6ea657e0b04c03)

1 files changed, 97 insertions, 48 deletions

diff --git a/source4/lib/tdb/tdb.c b/source4/lib/tdb/tdb.c
index 47ba2cb52c..c8ac7babad 100644
--- a/source4/lib/tdb/tdb.c
+++ b/source4/lib/tdb/tdb.c
@@ -530,7 +530,7 @@ static tdb_off tdb_dump_record(TDB_CONTEXT *tdb, tdb_off offset)
 		return 0;
 	}
 
-	printf(" rec: offset=%u next=%d rec_len=%d key_len=%d data_len=%d full_hash=0x%x magic=0x%x\n",
+	printf(" rec: offset=0x%08x next=0x%08x rec_len=%d key_len=%d data_len=%d full_hash=0x%x magic=0x%x\n",
 	       offset, rec.next, rec.rec_len, rec.key_len, rec.data_len, rec.full_hash, rec.magic);
 
 	tailer_ofs = offset + sizeof(rec) + rec.rec_len - sizeof(tdb_off);
@@ -609,7 +609,8 @@ int tdb_printfreelist(TDB_CONTEXT *tdb)
 			return -1;
 		}
 
-		printf("entry offset=[0x%08x], rec.rec_len = [0x%08x (%d)]\n", rec.next, rec.rec_len, rec.rec_len );
+		printf("entry offset=[0x%08x], rec.rec_len = [0x%08x (%d)] (end = 0x%08x)\n", 
+		       rec_ptr, rec.rec_len, rec.rec_len, rec_ptr + rec.rec_len);
 		total_free += rec.rec_len;
 
 		/* move to the next record */
@@ -850,6 +851,66 @@ static int tdb_expand(TDB_CONTEXT *tdb, tdb_off size)
 	return -1;
 }
 
+
+/* 
+   the core of tdb_allocate - called when we have decided which
+   free list entry to use
+ */
+static tdb_off tdb_allocate_ofs(TDB_CONTEXT *tdb, tdb_len length, tdb_off rec_ptr,
+				struct list_struct *rec, tdb_off last_ptr)
+{
+	struct list_struct newrec;
+	tdb_off newrec_ptr;
+
+	memset(&newrec, '\0', sizeof(newrec));
+
+	/* found it - now possibly split it up  */
+	if (rec->rec_len > length + MIN_REC_SIZE) {
+		/* Length of left piece */
+		length = TDB_ALIGN(length, TDB_ALIGNMENT);
+		
+		/* Right piece to go on free list */
+		newrec.rec_len = rec->rec_len - (sizeof(*rec) + length);
+		newrec_ptr = rec_ptr + sizeof(*rec) + length;
+		
+		/* And left record is shortened */
+		rec->rec_len = length;
+	} else {
+		newrec_ptr = 0;
+	}
+	
+	/* Remove allocated record from the free list */
+	if (ofs_write(tdb, last_ptr, &rec->next) == -1) {
+		return 0;
+	}
+	
+	/* Update header: do this before we drop alloc
+	   lock, otherwise tdb_free() might try to
+	   merge with us, thinking we're free.
+	   (Thanks Jeremy Allison). */
+	rec->magic = TDB_MAGIC;
+	if (rec_write(tdb, rec_ptr, rec) == -1) {
+		return 0;
+	}
+	
+	/* Did we create new block? */
+	if (newrec_ptr) {
+		/* Update allocated record tailer (we
+		   shortened it). */
+		if (update_tailer(tdb, rec_ptr, rec) == -1) {
+			return 0;
+		}
+		
+		/* Free new record */
+		if (tdb_free(tdb, newrec_ptr, &newrec) == -1) {
+			return 0;
+		}
+	}
+	
+	/* all done - return the new record offset */
+	return rec_ptr;
+}
+
 /* allocate some space from the free list. The offset returned points
    to a unconnected list_struct within the database with room for at
    least length bytes of total data
@@ -860,9 +921,10 @@ static tdb_off tdb_allocate(TDB_CONTEXT *tdb, tdb_len length,
 			    struct list_struct *rec)
 {
 	tdb_off rec_ptr, last_ptr, newrec_ptr;
-	struct list_struct newrec;
-
-	memset(&newrec, '\0', sizeof(newrec));
+	struct {
+		tdb_off rec_ptr, last_ptr;
+		tdb_len rec_len;
+	} bestfit;
 
 	if (tdb_lock(tdb, -1, F_WRLCK) == -1)
 		return 0;
@@ -877,59 +939,46 @@ static tdb_off tdb_allocate(TDB_CONTEXT *tdb, tdb_len length,
 	if (ofs_read(tdb, FREELIST_TOP, &rec_ptr) == -1)
 		goto fail;
 
-	/* keep looking until we find a freelist record big enough */
+	bestfit.rec_ptr = 0;
+
+	/* 
+	   this is a best fit allocation strategy. Originally we used
+	   a first fit strategy, but it suffered from massive fragmentation
+	   issues when faced with a slowly increasing record size.
+	 */
 	while (rec_ptr) {
-		if (rec_free_read(tdb, rec_ptr, rec) == -1)
+		if (rec_free_read(tdb, rec_ptr, rec) == -1) {
 			goto fail;
+		}
 
 		if (rec->rec_len >= length) {
-			/* found it - now possibly split it up  */
-			if (rec->rec_len > length + MIN_REC_SIZE) {
-				/* Length of left piece */
-				length = TDB_ALIGN(length, TDB_ALIGNMENT);
-
-				/* Right piece to go on free list */
-				newrec.rec_len = rec->rec_len
-					- (sizeof(*rec) + length);
-				newrec_ptr = rec_ptr + sizeof(*rec) + length;
-
-				/* And left record is shortened */
-				rec->rec_len = length;
-			} else
-				newrec_ptr = 0;
-
-			/* Remove allocated record from the free list */
-			if (ofs_write(tdb, last_ptr, &rec->next) == -1)
-				goto fail;
-
-			/* Update header: do this before we drop alloc
-                           lock, otherwise tdb_free() might try to
-                           merge with us, thinking we're free.
-                           (Thanks Jeremy Allison). */
-			rec->magic = TDB_MAGIC;
-			if (rec_write(tdb, rec_ptr, rec) == -1)
-				goto fail;
-
-			/* Did we create new block? */
-			if (newrec_ptr) {
-				/* Update allocated record tailer (we
-                                   shortened it). */
-				if (update_tailer(tdb, rec_ptr, rec) == -1)
-					goto fail;
-
-				/* Free new record */
-				if (tdb_free(tdb, newrec_ptr, &newrec) == -1)
-					goto fail;
+			if (bestfit.rec_ptr == 0 ||
+			    rec->rec_len < bestfit.rec_len) {
+				bestfit.rec_len = rec->rec_len;
+				bestfit.rec_ptr = rec_ptr;
+				bestfit.last_ptr = last_ptr;
+				/* consider a fit to be good enough if we aren't wasting more than half the space */
+				if (bestfit.rec_len < 2*length) {
+					break;
+				}
 			}
-
-			/* all done - return the new record offset */
-			tdb_unlock(tdb, -1, F_WRLCK);
-			return rec_ptr;
 		}
+
 		/* move to the next record */
 		last_ptr = rec_ptr;
 		rec_ptr = rec->next;
 	}
+
+	if (bestfit.rec_ptr != 0) {
+		if (rec_free_read(tdb, bestfit.rec_ptr, rec) == -1) {
+			goto fail;
+		}
+
+		newrec_ptr = tdb_allocate_ofs(tdb, length, bestfit.rec_ptr, rec, bestfit.last_ptr);
+		tdb_unlock(tdb, -1, F_WRLCK);
+		return newrec_ptr;
+	}
+
 	/* 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)