X-Git-Url: http://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Ftdb2%2Ffree.c;h=9c2bcac70e5366ad44e3d7240091abbb923a85f6;hb=4dc29a338fadeac805b369b4b0851c02f1b152c7;hp=7482daa2153de5f61773353a4607eb8646a895d8;hpb=024a5647e6c81735a93d826b56db0db4bf86fab8;p=ccan

diff --git a/ccan/tdb2/free.c b/ccan/tdb2/free.c
index 7482daa2..9c2bcac7 100644
--- a/ccan/tdb2/free.c
+++ b/ccan/tdb2/free.c
@@ -370,8 +370,10 @@ static tdb_len_t coalesce(struct tdb_context *tdb,
 		}
 
 		/* Did we just mess up a record you were hoping to use? */
-		if (end == *protect)
+		if (end == *protect) {
+			tdb->stats.alloc_coalesce_iterate_clash++;
 			*protect = TDB_ERR_NOEXIST;
+		}
 
 		ecode = remove_from_list(tdb, nb_off, end, &rec);
 		check_list(tdb, nb_off);
@@ -390,8 +392,10 @@ static tdb_len_t coalesce(struct tdb_context *tdb,
 		return 0;
 
 	/* Before we expand, check this isn't one you wanted protected? */
-	if (off == *protect)
+	if (off == *protect) {
 		*protect = TDB_ERR_EXISTS;
+		tdb->stats.alloc_coalesce_iterate_clash++;
+	}
 
 	/* OK, expand initial record */
 	ecode = tdb_read_convert(tdb, off, &rec, sizeof(rec));
@@ -416,6 +420,7 @@ static tdb_len_t coalesce(struct tdb_context *tdb,
 	ecode = add_free_record(tdb, off, end - off, TDB_LOCK_NOWAIT, false);
 	if (ecode != TDB_SUCCESS) {
 		/* Need to drop lock.  Can't rely on anything stable. */
+		tdb->stats.alloc_coalesce_lockfail++;
 		*protect = TDB_ERR_CORRUPT;
 
 		/* We have to drop this to avoid deadlocks, so make sure record
@@ -431,7 +436,6 @@ static tdb_len_t coalesce(struct tdb_context *tdb,
 			goto err;
 		}
 
-		tdb->stats.alloc_coalesce_succeeded++;
 		tdb_unlock_free_bucket(tdb, b_off);
 
 		ecode = add_free_record(tdb, off, end - off, TDB_LOCK_WAIT,
@@ -443,6 +447,7 @@ static tdb_len_t coalesce(struct tdb_context *tdb,
 		/* For simplicity, we always drop lock if they can't continue */
 		tdb_unlock_free_bucket(tdb, b_off);
 	}
+	tdb->stats.alloc_coalesce_succeeded++;
 
 	/* Return usable length. */
 	return end - off - sizeof(struct tdb_used_record);
@@ -455,7 +460,9 @@ err:
 
 /* List is locked: we unlock it. */
 static enum TDB_ERROR coalesce_list(struct tdb_context *tdb,
-				    tdb_off_t ftable_off, tdb_off_t b_off)
+				    tdb_off_t ftable_off,
+				    tdb_off_t b_off,
+				    unsigned int limit)
 {
 	enum TDB_ERROR ecode;
 	tdb_off_t off;
@@ -465,10 +472,10 @@ static enum TDB_ERROR coalesce_list(struct tdb_context *tdb,
 		ecode = off;
 		goto unlock_err;
 	}
-	/* A little bit of paranoia */
+	/* A little bit of paranoia: counter should be 0. */
 	off &= TDB_OFF_MASK;
 
-	while (off) {
+	while (off && limit--) {
 		struct tdb_free_record rec;
 		tdb_len_t coal;
 		tdb_off_t next;
@@ -487,9 +494,85 @@ static enum TDB_ERROR coalesce_list(struct tdb_context *tdb,
 			/* Coalescing had to unlock, so stop. */
 			return TDB_SUCCESS;
 		}
+		/* Keep going if we're doing well... */
+		limit += size_to_bucket(coal / 16 + TDB_MIN_DATA_LEN);
 		off = next;
 	}
 
+	/* Now, move those elements to the tail of the list so we get something
+	 * else next time. */
+	if (off) {
+		struct tdb_free_record oldhrec, newhrec, oldtrec, newtrec;
+		tdb_off_t oldhoff, oldtoff, newtoff;
+
+		/* The record we were up to is the new head. */
+		ecode = tdb_read_convert(tdb, off, &newhrec, sizeof(newhrec));
+		if (ecode != TDB_SUCCESS)
+			goto unlock_err;
+
+		/* Get the new tail. */
+		newtoff = frec_prev(&newhrec);
+		ecode = tdb_read_convert(tdb, newtoff, &newtrec,
+					 sizeof(newtrec));
+		if (ecode != TDB_SUCCESS)
+			goto unlock_err;
+
+		/* Get the old head. */
+		oldhoff = tdb_read_off(tdb, b_off);
+		if (TDB_OFF_IS_ERR(oldhoff)) {
+			ecode = oldhoff;
+			goto unlock_err;
+		}
+
+		/* This could happen if they all coalesced away. */
+		if (oldhoff == off)
+			goto out;
+
+		ecode = tdb_read_convert(tdb, oldhoff, &oldhrec,
+					 sizeof(oldhrec));
+		if (ecode != TDB_SUCCESS)
+			goto unlock_err;
+
+		/* Get the old tail. */
+		oldtoff = frec_prev(&oldhrec);
+		ecode = tdb_read_convert(tdb, oldtoff, &oldtrec,
+					 sizeof(oldtrec));
+		if (ecode != TDB_SUCCESS)
+			goto unlock_err;
+
+		/* Old tail's next points to old head. */
+		oldtrec.next = oldhoff;
+
+		/* Old head's prev points to old tail. */
+		oldhrec.magic_and_prev
+			= (TDB_FREE_MAGIC << (64 - TDB_OFF_UPPER_STEAL))
+			| oldtoff;
+
+		/* New tail's next is 0. */
+		newtrec.next = 0;
+
+		/* Write out the modified versions. */
+		ecode = tdb_write_convert(tdb, oldtoff, &oldtrec,
+					  sizeof(oldtrec));
+		if (ecode != TDB_SUCCESS)
+			goto unlock_err;
+
+		ecode = tdb_write_convert(tdb, oldhoff, &oldhrec,
+					  sizeof(oldhrec));
+		if (ecode != TDB_SUCCESS)
+			goto unlock_err;
+
+		ecode = tdb_write_convert(tdb, newtoff, &newtrec,
+					  sizeof(newtrec));
+		if (ecode != TDB_SUCCESS)
+			goto unlock_err;
+		
+		/* And finally link in new head. */
+		ecode = tdb_write_off(tdb, b_off, off);
+		if (ecode != TDB_SUCCESS)
+			goto unlock_err;
+	}
+out:
 	tdb_unlock_free_bucket(tdb, b_off);
 	return TDB_SUCCESS;
 
@@ -523,7 +606,7 @@ enum TDB_ERROR add_free_record(struct tdb_context *tdb,
 
 	/* Coalescing unlocks free list. */
 	if (!ecode && coalesce)
-		ecode = coalesce_list(tdb, tdb->ftable_off, b_off);
+		ecode = coalesce_list(tdb, tdb->ftable_off, b_off, 2);
 	else
 		tdb_unlock_free_bucket(tdb, b_off);
 	return ecode;