Rev 749: a compromise for freelist scanning - we now will look for other than the first fit, but get exponentially more desperate as we get deeper into the freelist in http://samba.org/~tridge/ctdb

[tridge at samba.org]

------------------------------------------------------------
revno: 749
revision-id:tridge at samba.org-20080109043310-yqlygz55hgcvf0wm
parent: tridge at samba.org-20080109043218-5w222oeozxmkofj6
committer: Andrew Tridgell <tridge at samba.org>
branch nick: tridge.stable
timestamp: Wed 2008-01-09 15:33:10 +1100
message:
  a compromise for freelist scanning - we now will look for other than the first fit, but get exponentially more desperate as we get deeper into the freelist
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-08 06:23:27 +0000
+++ b/lib/tdb/common/freelist.c	2008-01-09 04:33:10 +0000
@@ -280,6 +280,7 @@
 		tdb_off_t rec_ptr, last_ptr;
 		tdb_len_t rec_len;
 	} bestfit;
+	float multiplier = 1.0;
 
 	if (tdb_lock(tdb, -1, F_WRLCK) == -1)
 		return 0;
@@ -314,13 +315,27 @@
 				bestfit.rec_len = rec->rec_len;
 				bestfit.rec_ptr = rec_ptr;
 				bestfit.last_ptr = last_ptr;
-				break;
 			}
 		}
 
 		/* move to the next record */
 		last_ptr = rec_ptr;
 		rec_ptr = rec->next;
+
+		/* if we've found a record that is big enough, then
+		   stop searching if its also not too big. The
+		   definition of 'too big' changes as we scan
+		   through */
+		if (bestfit.rec_len > 0 &&
+		    bestfit.rec_len < length * multiplier) {
+			break;
+		}
+		
+		/* this multiplier means we only extremely rarely
+		   search more than 50 or so records. At 50 records we
+		   accept records up to 11 times larger than what we
+		   want */
+		multiplier *= 1.05;
 	}
 
 	if (bestfit.rec_ptr != 0) {