Rev 697: prevent O(n^2) behaviour for traverse after large numbers of deletes in http://samba.org/~tridge/ctdb

[tridge at samba.org]

------------------------------------------------------------
revno: 697
revision-id:tridge at samba.org-20080104011202-8236ox1e39q8irrf
parent: tridge at samba.org-20080104011129-bsprbhxtczom25gx
committer: Andrew Tridgell <tridge at samba.org>
branch nick: tridge.kantana
timestamp: Fri 2008-01-04 12:12:02 +1100
message:
  prevent O(n^2) behaviour for traverse after large numbers of deletes
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-02 01:04:07 +0000
+++ b/lib/tdb/common/freelist.c	2008-01-04 01:12:02 +0000
@@ -105,6 +105,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 */
+
 	/* Look right first (I'm an Australian, dammit) */
 	right = offset + sizeof(*rec) + rec->rec_len;
 	if (right + sizeof(*rec) <= tdb->map_size) {
@@ -124,6 +128,7 @@
 			rec->rec_len += sizeof(r) + r.rec_len;
 		}
 	}
+#endif
 
 left:
 	/* Look left */
@@ -153,6 +158,23 @@
 
 		/* 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 */
+			l.rec_len += sizeof(*rec) + rec->rec_len;
+			if (tdb_rec_write(tdb, left, &l) == -1) {
+				TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_free: update_left failed at %u\n", left));
+				goto fail;
+			}
+			if (update_tailer(tdb, left, &l) == -1) {
+				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;
@@ -160,6 +182,7 @@
 				offset = left;
 				rec->rec_len += leftsize;
 			}
+#endif
 		}
 	}