--- common/lock.c.old	2013-06-04 15:21:30.000000000 +0100
+++ common/lock.c	2013-11-28 12:04:04.552298720 +0000
@@ -552,6 +552,45 @@
 	return 1;
 }
 
+static int tdb_allrecord_newlock(struct tdb_context *tdb,
+				 int ltype,
+				 size_t off, size_t len)
+{
+	struct tdb_lock_type *new_lck;
+
+	new_lck = (struct tdb_lock_type *)realloc(
+		tdb->allrecord_locks,
+		sizeof(*tdb->allrecord_locks) * (tdb->num_allrecord_locks+1));
+	if (new_lck == NULL) {
+		errno = ENOMEM;
+		return -1;
+	}
+
+	tdb->allrecord_locks = new_lck;
+	tdb->allrecord_locks[tdb->num_allrecord_locks].off = off;
+	tdb->allrecord_locks[tdb->num_allrecord_locks].count = 1;
+	tdb->allrecord_locks[tdb->num_allrecord_locks].ltype = ltype;
+	tdb->allrecord_locks[tdb->num_allrecord_locks].len = len;
+	tdb->num_allrecord_locks++;
+
+	return 0;
+}
+
+static int tdb_chainunlock_gradual(struct tdb_context *tdb)
+{
+	unsigned i;
+
+	for (i = 0; i < tdb->num_allrecord_locks; i++) {
+		struct tdb_lock_type *lck = &tdb->allrecord_locks[i];
+		if (tdb_brunlock(tdb, lck->ltype, lck->off, lck->len)) {
+			TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_unlockall failed (%s)\n", strerror(errno)));
+			return -1;
+		}
+	}
+
+	return 0;
+}
+             
 /* We only need to lock individual bytes, but Linux merges consecutive locks
  * so we lock in contiguous ranges. */
 static int tdb_chainlock_gradual(struct tdb_context *tdb,
@@ -563,12 +602,23 @@
 
 	if (len <= 4) {
 		/* Single record.  Just do blocking lock. */
-		return tdb_brlock(tdb, ltype, off, len, flags);
+		ret = tdb_brlock(tdb, ltype, off, len, flags);
+		if (ret == 0) {
+			if (tdb_allrecord_newlock(tdb, ltype, off, len) == -1) {
+				tdb_brunlock(tdb, ltype, off, len);
+				return -1;
+			}
+		}
+		return ret;
 	}
 
 	/* First we try non-blocking. */
 	ret = tdb_brlock(tdb, ltype, off, len, nb_flags);
 	if (ret == 0) {
+		if (tdb_allrecord_newlock(tdb, ltype, off, len) == -1) {
+			tdb_brunlock(tdb, ltype, off, len);
+			return -1;
+		}
 		return 0;
 	}
 
@@ -583,6 +633,7 @@
 		tdb_brunlock(tdb, ltype, off, len / 2);
 		return -1;
 	}
+
 	return 0;
 }
 
@@ -606,6 +657,7 @@
 	 *
 	 * It is (1) which cause the starvation problem, so we're only
 	 * gradual for that. */
+	tdb->num_allrecord_locks = 0;
 	if (tdb_chainlock_gradual(tdb, ltype, flags, FREELIST_TOP,
 				  tdb->hash_size * 4) == -1) {
 		return -1;
@@ -614,8 +666,7 @@
 	/* Grab individual record locks. */
 	if (tdb_brlock(tdb, ltype, lock_offset(tdb->hash_size), 0,
 		       flags) == -1) {
-		tdb_brunlock(tdb, ltype, FREELIST_TOP,
-			     tdb->hash_size * 4);
+		tdb_chainunlock_gradual(tdb);
 		return -1;
 	}
 
@@ -671,9 +722,13 @@
 		return 0;
 	}
 
-	if (!mark_lock && tdb_brunlock(tdb, ltype, FREELIST_TOP, 0)) {
-		TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_unlockall failed (%s)\n", strerror(errno)));
-		return -1;
+	if (!mark_lock) {
+		tdb_chainunlock_gradual(tdb);
+
+		if (tdb_brunlock(tdb, ltype, lock_offset(tdb->hash_size), 0)) {
+			TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_unlockall failed (%s)\n", strerror(errno)));
+			return -1;
+		}
 	}
 
 	tdb->allrecord_lock.count = 0;
--- common/tdb_private.h.old	2013-11-28 12:05:11.401178664 +0000
+++ common/tdb_private.h	2013-11-28 11:22:39.432877680 +0000
@@ -195,6 +195,8 @@
 	int read_only; /* opened read-only */
 	int traverse_read; /* read-only traversal */
 	int traverse_write; /* read-write traversal */
+	int num_allrecord_locks;
+	struct tdb_lock_type *allrecord_locks;
 	struct tdb_lock_type allrecord_lock; /* .offset == upgradable */
 	int num_lockrecs;
 	struct tdb_lock_type *lockrecs; /* only real locks, all with count>0 */