Rev 713: cleanup the new freelist code in http://samba.org/~tridge/ctdb

[tridge at samba.org]

------------------------------------------------------------
revno: 713
revision-id:tridge at samba.org-20080105010900-5c7uv6cs1f761q1g
parent: tridge at samba.org-20080105010841-n49gmcacwn2x1fdc
committer: Andrew Tridgell <tridge at samba.org>
branch nick: tridge.stable
timestamp: Sat 2008-01-05 12:09:00 +1100
message:
  cleanup the new freelist code
modified:
  lib/tdb/common/freelist.c      freelist.c-20070220022425-m1wibgjq7n5hahs6-4
=== modified file 'lib/tdb/common/freelist.c'
--- a/lib/tdb/common/freelist.c	2008-01-04 01:12:02 +0000
+++ b/lib/tdb/common/freelist.c	2008-01-05 01:09:00 +0000
@@ -27,6 +27,12 @@
 
 #include "tdb_private.h"
 
+/* 'right' merges can involve O(n^2) cost when combined with a
+   traverse, so they are disabled until we find a way to do them in 
+   O(1) time
+*/
+#define USE_RIGHT_MERGES 0
+
 /* read a freelist record and check for simple errors */
 int tdb_rec_free_read(struct tdb_context *tdb, tdb_off_t off, struct list_struct *rec)
 {
@@ -56,7 +62,7 @@
 }
 
 
-
+#if USE_RIGHT_MERGES
 /* Remove an element from the freelist.  Must have alloc lock. */
 static int remove_from_freelist(struct tdb_context *tdb, tdb_off_t off, tdb_off_t next)
 {
@@ -75,6 +81,7 @@
 	TDB_LOG((tdb, TDB_DEBUG_FATAL,"remove_from_freelist: not on list at off=%d\n", off));
 	return TDB_ERRCODE(TDB_ERR_CORRUPT, -1);
 }
+#endif
 
 
 /* update a record tailer (must hold allocation lock) */
@@ -93,8 +100,6 @@
    neccessary. */
 int tdb_free(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec)
 {
-	tdb_off_t right, left;
-
 	/* Allocation and tailer lock */
 	if (tdb_lock(tdb, -1, F_WRLCK) != 0)
 		return -1;
@@ -105,13 +110,10 @@
 		goto fail;
 	}
 
-#if 0
-	/* (tridge) disable 'right' merges for now as they give rise to a O(n^2) behaviour during
-	   traverse which is freeing old dead records */
-
+#if USE_RIGHT_MERGES
 	/* Look right first (I'm an Australian, dammit) */
-	right = offset + sizeof(*rec) + rec->rec_len;
-	if (right + sizeof(*rec) <= tdb->map_size) {
+	if (offset + sizeof(*rec) + rec->rec_len + sizeof(*rec) <= tdb->map_size) {
+		tdb_off_t right = offset + sizeof(*rec) + rec->rec_len;
 		struct list_struct r;
 
 		if (tdb->methods->tdb_read(tdb, right, &r, sizeof(r), DOCONV()) == -1) {
@@ -126,14 +128,18 @@
 				goto left;
 			}
 			rec->rec_len += sizeof(r) + r.rec_len;
+			if (update_tailer(tdb, offset, rec) == -1) {
+				TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed at %u\n", offset));
+				goto fail;
+			}
 		}
 	}
-#endif
-
 left:
+#endif
+
 	/* Look left */
-	left = offset - sizeof(tdb_off_t);
-	if (left > TDB_DATA_START(tdb->header.hash_size)) {
+	if (offset - sizeof(tdb_off_t) >= TDB_DATA_START(tdb->header.hash_size)) {
+		tdb_off_t left = offset - sizeof(tdb_off_t);
 		struct list_struct l;
 		tdb_off_t leftsize;
 		
@@ -150,7 +156,11 @@
 
 		left = offset - leftsize;
 
-		/* Now read in record */
+		if (left < TDB_DATA_START(tdb->header.hash_size)) {
+			goto update;
+		}
+
+		/* Now read in the left record */
 		if (tdb->methods->tdb_read(tdb, left, &l, sizeof(l), DOCONV()) == -1) {
 			TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: left read failed at %u (%u)\n", left, leftsize));
 			goto update;
@@ -158,7 +168,6 @@
 
 		/* If it's free, expand to include it. */
 		if (l.magic == TDB_FREE_MAGIC) {
-#if 1
 			/* we now merge the new record into the left record, rather than the other 
 			   way around. This makes the operation O(1) instead of O(n). This change
 			   prevents traverse from being O(n^2) after a lot of deletes */
@@ -171,26 +180,12 @@
 				TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed at %u\n", offset));
 				goto fail;
 			}
-			/* we're done. */
 			tdb_unlock(tdb, -1, F_WRLCK);
-			return 0;			
-#else
-			if (remove_from_freelist(tdb, left, l.next) == -1) {
-				TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: left free failed at %u\n", left));
-				goto update;
-			} else {
-				offset = left;
-				rec->rec_len += leftsize;
-			}
-#endif
+			return 0;
 		}
 	}
 
 update:
-	if (update_tailer(tdb, offset, rec) == -1) {
-		TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_tailer failed at %u\n", offset));
-		goto fail;
-	}
 
 	/* Now, prepend to free list */
 	rec->magic = TDB_FREE_MAGIC;