[PATCH] Make tdb record deletion circular-chain safe

Volker Lendecke Volker.Lendecke at SerNet.DE
Thu Oct 25 19:12:44 UTC 2018


Hi!

First a few prereqs, then a bigger patch with a pretty epic commit
message. This goes on top of

https://lists.samba.org/archive/samba-technical/2018-October/130722.html

which is on its way to master thanks to Andreas.

Why all this tdb stuff? My goal is to get rid of the transactions in
gencache_stabilize. This function is a major performance problem in
larger installation that are busy writing into our clear-if-first
tdbs. I've seen user-visible performance problems due to that in more
than one installation.

This means that tdb must be rock solid against corrupt databases,
because after a crash we will re-open a non-transactioned database
that might have been left behind broken.

Review appreciated!

Thanks, Volker

-- 
SerNet GmbH, Bahnhofsallee 1b, 37081 Göttingen
phone: +49-551-370000-0, fax: +49-551-370000-9
AG Göttingen, HRB 2816, GF: Dr. Johannes Loxen
http://www.sernet.de, mailto:kontakt at sernet.de
-------------- next part --------------
From f25f718ae74b1d06a7733455459fd0e9e7680de4 Mon Sep 17 00:00:00 2001
From: Volker Lendecke <vl at samba.org>
Date: Thu, 25 Oct 2018 20:53:52 +0200
Subject: [PATCH 1/6] tdb: Fix a typo

Signed-off-by: Volker Lendecke <vl at samba.org>
---
 lib/tdb/common/lock.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/lib/tdb/common/lock.c b/lib/tdb/common/lock.c
index 9f30c7a4b57..f55184d8be5 100644
--- a/lib/tdb/common/lock.c
+++ b/lib/tdb/common/lock.c
@@ -149,8 +149,8 @@ static int fcntl_unlock(struct tdb_context *tdb, int rw, off_t off, off_t len)
  * This is the memory layout of the hashchain array:
  *
  * FREELIST_TOP + 0 = freelist
- * FREELIST_TOP + 4 = hashtbale list 0
- * FREELIST_TOP + 8 = hashtbale list 1
+ * FREELIST_TOP + 4 = hashtable list 0
+ * FREELIST_TOP + 8 = hashtable list 1
  * ...
  *
  * Otoh lock_offset computes:
-- 
2.11.0


From e3209e43dbc420ef396da4e49991712aab80f852 Mon Sep 17 00:00:00 2001
From: Volker Lendecke <vl at samba.org>
Date: Wed, 24 Oct 2018 07:26:49 +0200
Subject: [PATCH 2/6] tdb: Align an integer type

Signed-off-by: Volker Lendecke <vl at samba.org>
---
 lib/tdb/common/dump.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/tdb/common/dump.c b/lib/tdb/common/dump.c
index d4e3478469b..adcf591ee0c 100644
--- a/lib/tdb/common/dump.c
+++ b/lib/tdb/common/dump.c
@@ -95,7 +95,7 @@ static int tdb_dump_chain(struct tdb_context *tdb, int i)
 
 _PUBLIC_ void tdb_dump_all(struct tdb_context *tdb)
 {
-	int i;
+	uint32_t i;
 	for (i=0;i<tdb->hash_size;i++) {
 		tdb_dump_chain(tdb, i);
 	}
-- 
2.11.0


From 4e94e0c34f6889697f49919a3f0bf1c4bca3fade Mon Sep 17 00:00:00 2001
From: Volker Lendecke <vl at samba.org>
Date: Tue, 23 Oct 2018 13:40:34 +0200
Subject: [PATCH 3/6] tdb: Don't delete dead records in traverse

The next commit will change the handling of dead records, removing the
"tdb_do_delete" function. As traverses should not happen in normal
operations, dead records from them should be rare, and relying on
traverses to remove them is a very bad idea IMHO.

Signed-off-by: Volker Lendecke <vl at samba.org>
---
 lib/tdb/common/traverse.c | 6 ------
 1 file changed, 6 deletions(-)

diff --git a/lib/tdb/common/traverse.c b/lib/tdb/common/traverse.c
index 7a1d567cc01..a9af1d4b824 100644
--- a/lib/tdb/common/traverse.c
+++ b/lib/tdb/common/traverse.c
@@ -96,7 +96,6 @@ static tdb_off_t tdb_next_lock(struct tdb_context *tdb, struct tdb_traverse_lock
 
 		/* Iterate through chain */
 		while( tlock->off) {
-			tdb_off_t current;
 			if (tdb_rec_read(tdb, tlock->off, rec) == -1)
 				goto fail;
 
@@ -114,12 +113,7 @@ static tdb_off_t tdb_next_lock(struct tdb_context *tdb, struct tdb_traverse_lock
 				return tlock->off;
 			}
 
-			/* Try to clean dead ones from old traverses */
-			current = tlock->off;
 			tlock->off = rec->next;
-			if (!(tdb->read_only || tdb->traverse_read) &&
-			    tdb_do_delete(tdb, current, rec) != 0)
-				goto fail;
 		}
 		tdb_unlock(tdb, tlock->list, tlock->lock_rw);
 		want_next = 0;
-- 
2.11.0


From 4845b28fe1b550841955dbdf20bc4a63febcaadc Mon Sep 17 00:00:00 2001
From: Volker Lendecke <vl at samba.org>
Date: Thu, 25 Oct 2018 15:55:29 +0200
Subject: [PATCH 4/6] tdb: Purge dead records whenever we block the freelist

Signed-off-by: Volker Lendecke <vl at samba.org>
---
 lib/tdb/common/freelist.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/lib/tdb/common/freelist.c b/lib/tdb/common/freelist.c
index 5afd89bc554..5221bf3679e 100644
--- a/lib/tdb/common/freelist.c
+++ b/lib/tdb/common/freelist.c
@@ -619,6 +619,12 @@ blocking_freelist_allocate:
 	if (tdb_lock(tdb, -1, F_WRLCK) == -1) {
 		return 0;
 	}
+	/*
+	 * Dead records can happen even if max_dead_records==0, they
+	 * are older than the max_dead_records concept: They happen if
+	 * tdb_delete happens concurrently with a traverse.
+	 */
+	tdb_purge_dead(tdb, hash);
 	ret = tdb_allocate_from_freelist(tdb, length, rec);
 	tdb_unlock(tdb, -1, F_WRLCK);
 	return ret;
-- 
2.11.0


From 1c270ae00b1f21ff34ebeea42e4e3e0f777d4ca3 Mon Sep 17 00:00:00 2001
From: Volker Lendecke <vl at samba.org>
Date: Thu, 25 Oct 2018 15:59:48 +0200
Subject: [PATCH 5/6] tdb: Do early RDONLY error check for tdb_delete

Signed-off-by: Volker Lendecke <vl at samba.org>
---
 lib/tdb/common/tdb.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/lib/tdb/common/tdb.c b/lib/tdb/common/tdb.c
index 4e433c89e1e..2a6d8977002 100644
--- a/lib/tdb/common/tdb.c
+++ b/lib/tdb/common/tdb.c
@@ -463,6 +463,11 @@ static int tdb_delete_hash(struct tdb_context *tdb, TDB_DATA key, uint32_t hash)
 	struct tdb_record rec;
 	int ret;
 
+	if (tdb->read_only || tdb->traverse_read) {
+		tdb->ecode = TDB_ERR_RDONLY;
+		return -1;
+	}
+
 	rec_ptr = tdb_find_lock_hash(tdb, key, hash, F_WRLCK, &rec);
 	if (rec_ptr == 0) {
 		return -1;
-- 
2.11.0


From a450f1119ab47005ab1db8a2e624eb5ffbbd1d38 Mon Sep 17 00:00:00 2001
From: Volker Lendecke <vl at samba.org>
Date: Wed, 24 Oct 2018 14:31:34 +0200
Subject: [PATCH 6/6] tdb: Make record deletion circular-chain safe

Before this patch we had 3 loops walking a hash chain to delete
records:

tdb_do_delete() to find the predecessor of the record that was to be
deleted. tdb_count_dead(), the name says it all and tdb_purge_dead()
to give back all dead records from a chain to the freelist.

This patch introduces tdb_trim_dead that walks a hash chain just
once. While it does so it counts the number of dead records, and all
records beyond tdb->max_dead_records are moved to the freelist.

Normal record deletion now works by always marking a record as dead in
step 1 and then calling tdb_trim_dead. This is made safe against
circular chains by doing the slow chain walk only in the case when we
did not delete a dead record during our walk.

It changes our dynamics a bit:

When deleting a record with non-zero max_dead_records, now we always
leave that number of records around when deleting, doing a blocking
lock on the freelist when we found too many dead records.

Previously when exceeding max_dead_records we wiped all dead records
to start accumulating them from scratch, assuming we could lock the
freelist in a nonblocking fashion.

The net effect for an uncontended freelist is the same: In
tdb_allocate() we still completely hand over all dead records to the
freelist when we could lock it, it just happens later than without
this patch.

This means for a lightly loaded system we will potentially leave more
dead records around in databases like locking.tdb. However, on a
heavily loaded system we become more predictable: If the freelist is
so heavily contended that across many deletes we can't get hold of it,
previously we accumulated more dead records than max_dead_records
would allow. This is a really lowlevel tradeoff that is likely hard to
measure, but to me becoming more deterministic without sacrificing too
much parallelism (we keep more dead records around) is worth trying.

Signed-off-by: Volker Lendecke <vl at samba.org>
---
 lib/tdb/common/freelist.c    |  11 +++
 lib/tdb/common/tdb.c         | 217 +++++++++++++++++++++++--------------------
 lib/tdb/common/tdb_private.h |   3 +-
 3 files changed, 129 insertions(+), 102 deletions(-)

diff --git a/lib/tdb/common/freelist.c b/lib/tdb/common/freelist.c
index 5221bf3679e..90643862208 100644
--- a/lib/tdb/common/freelist.c
+++ b/lib/tdb/common/freelist.c
@@ -555,6 +555,17 @@ static bool tdb_alloc_dead(
 	return (tdb_ofs_write(tdb, last_ptr, &rec->next) == 0);
 }
 
+static void tdb_purge_dead(struct tdb_context *tdb, uint32_t hash)
+{
+	uint32_t max_dead_records = tdb->max_dead_records;
+
+	tdb->max_dead_records = 0;
+
+	tdb_trim_dead(tdb, hash);
+
+	tdb->max_dead_records = max_dead_records;
+}
+
 /*
  * Chain "hash" is assumed to be locked
  */
diff --git a/lib/tdb/common/tdb.c b/lib/tdb/common/tdb.c
index 2a6d8977002..9c80a36e00a 100644
--- a/lib/tdb/common/tdb.c
+++ b/lib/tdb/common/tdb.c
@@ -357,103 +357,139 @@ _PUBLIC_ int tdb_exists(struct tdb_context *tdb, TDB_DATA key)
 	return ret;
 }
 
-/* actually delete an entry in the database given the offset */
-int tdb_do_delete(struct tdb_context *tdb, tdb_off_t rec_ptr, struct tdb_record *rec)
+/*
+ * Move a dead record to the freelist. The hash chain and freelist
+ * must be locked.
+ */
+static int tdb_del_dead(struct tdb_context *tdb,
+			uint32_t last_ptr,
+			uint32_t rec_ptr,
+			struct tdb_record *rec,
+			bool *deleted)
 {
-	tdb_off_t last_ptr, i;
-	struct tdb_record lastrec;
-
-	if (tdb->read_only || tdb->traverse_read) return -1;
+	int ret;
 
-	if (((tdb->traverse_write != 0) && (!TDB_DEAD(rec))) ||
-	    tdb_write_lock_record(tdb, rec_ptr) == -1) {
-		/* Someone traversing here: mark it as dead */
-		rec->magic = TDB_DEAD_MAGIC;
-		return tdb_rec_write(tdb, rec_ptr, rec);
+	ret = tdb_write_lock_record(tdb, rec_ptr);
+	if (ret == -1) {
+		/* Someone traversing here: Just leave it dead */
+		return 0;
 	}
-	if (tdb_write_unlock_record(tdb, rec_ptr) != 0)
-		return -1;
-
-	/* find previous record in hash chain */
-	if (tdb_ofs_read(tdb, TDB_HASH_TOP(rec->full_hash), &i) == -1)
-		return -1;
-	for (last_ptr = 0; i != rec_ptr; last_ptr = i, i = lastrec.next)
-		if (tdb_rec_read(tdb, i, &lastrec) == -1)
-			return -1;
-
-	/* unlink it: next ptr is at start of record. */
-	if (last_ptr == 0)
-		last_ptr = TDB_HASH_TOP(rec->full_hash);
-	if (tdb_ofs_write(tdb, last_ptr, &rec->next) == -1)
+	ret = tdb_write_unlock_record(tdb, rec_ptr);
+	if (ret == -1) {
 		return -1;
-
-	/* recover the space */
-	if (tdb_free(tdb, rec_ptr, rec) == -1)
+	}
+	ret = tdb_ofs_write(tdb, last_ptr, &rec->next);
+	if (ret == -1) {
 		return -1;
-	return 0;
-}
-
-static int tdb_count_dead(struct tdb_context *tdb, uint32_t hash)
-{
-	int res = 0;
-	tdb_off_t rec_ptr;
-	struct tdb_record rec;
-
-	/* read in the hash top */
-	if (tdb_ofs_read(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1)
-		return 0;
+	}
 
-	while (rec_ptr) {
-		if (tdb_rec_read(tdb, rec_ptr, &rec) == -1)
-			return 0;
+	*deleted = true;
 
-		if (rec.magic == TDB_DEAD_MAGIC) {
-			res += 1;
-		}
-		rec_ptr = rec.next;
-	}
-	return res;
+	ret = tdb_free(tdb, rec_ptr, rec);
+	return ret;
 }
 
 /*
- * Purge all DEAD records from a hash chain
+ * Walk the hash chain and leave tdb->max_dead_records around. Move
+ * the rest of dead records to the freelist.
  */
-int tdb_purge_dead(struct tdb_context *tdb, uint32_t hash)
+int tdb_trim_dead(struct tdb_context *tdb, uint32_t hash)
 {
-	int res = -1;
+	struct tdb_chainwalk_ctx chainwalk;
 	struct tdb_record rec;
-	tdb_off_t rec_ptr;
+	tdb_off_t last_ptr, rec_ptr;
+	bool locked_freelist = false;
+	int num_dead = 0;
+	int ret;
 
-	if (tdb_lock_nonblock(tdb, -1, F_WRLCK) == -1) {
-		/*
-		 * Don't block the freelist if not strictly necessary
-		 */
+	last_ptr = TDB_HASH_TOP(hash);
+
+	/*
+	 * Init chainwalk with the pointer to the hash top. It might
+	 * be that the very first record in the chain is a dead one
+	 * that we have to delete.
+	 */
+	tdb_chainwalk_init(&chainwalk, last_ptr);
+
+	ret = tdb_ofs_read(tdb, last_ptr, &rec_ptr);
+	if (ret == -1) {
 		return -1;
 	}
 
-	/* read in the hash top */
-	if (tdb_ofs_read(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1)
-		goto fail;
-
-	while (rec_ptr) {
-		tdb_off_t next;
+	while (rec_ptr != 0) {
+		bool deleted = false;
+		uint32_t next;
 
-		if (tdb_rec_read(tdb, rec_ptr, &rec) == -1) {
+		ret = tdb_rec_read(tdb, rec_ptr, &rec);
+		if (ret == -1) {
 			goto fail;
 		}
 
+		/*
+		 * Make a copy of rec.next: Further down we might
+		 * delete and put the record on the freelist. Make
+		 * sure that modifications in that code path can't
+		 * break the chainwalk here.
+		 */
 		next = rec.next;
 
-		if (rec.magic == TDB_DEAD_MAGIC
-		    && tdb_do_delete(tdb, rec_ptr, &rec) == -1) {
-			goto fail;
+		if (rec.magic == TDB_DEAD_MAGIC) {
+			num_dead += 1;
+
+			if (num_dead > tdb->max_dead_records) {
+
+				if (!locked_freelist) {
+					/*
+					 * Lock the freelist only if
+					 * it's really required.
+					 */
+					ret = tdb_lock(tdb, -1, F_WRLCK);
+					if (ret == -1) {
+						goto fail;
+					};
+					locked_freelist = true;
+				}
+
+				ret = tdb_del_dead(
+					tdb,
+					last_ptr,
+					rec_ptr,
+					&rec,
+					&deleted);
+
+				if (ret == -1) {
+					goto fail;
+				}
+			}
+		}
+
+		/*
+		 * Don't do the chainwalk check if "rec_ptr" was
+		 * deleted. We reduced the chain, and the chainwalk
+		 * check might catch up early. Imagine a valid chain
+		 * with just dead records: We never can bump the
+		 * "slow" pointer in chainwalk_check, as there isn't
+		 * anything left to jump to and compare.
+		 */
+		if (!deleted) {
+			bool ok;
+
+			last_ptr = rec_ptr;
+
+			ok = tdb_chainwalk_check(tdb, &chainwalk, next);
+			if (!ok) {
+				ret = -1;
+				goto fail;
+			}
 		}
 		rec_ptr = next;
 	}
-	res = 0;
- fail:
-	tdb_unlock(tdb, -1, F_WRLCK);
-	return res;
+	ret = 0;
+fail:
+	if (locked_freelist) {
+		tdb_unlock(tdb, -1, F_WRLCK);
+	}
+	return ret;
 }
 
 /* delete an entry in the database given a key */
@@ -473,38 +509,19 @@ static int tdb_delete_hash(struct tdb_context *tdb, TDB_DATA key, uint32_t hash)
 		return -1;
 	}
 
-	if (tdb->max_dead_records != 0) {
-
-		uint32_t magic = TDB_DEAD_MAGIC;
-
-		/*
-		 * Allow for some dead records per hash chain, mainly for
-		 * tdb's with a very high create/delete rate like locking.tdb.
-		 */
-
-		if (tdb_count_dead(tdb, hash) >= tdb->max_dead_records) {
-			/*
-			 * Don't let the per-chain freelist grow too large,
-			 * delete all existing dead records
-			 */
-			tdb_purge_dead(tdb, hash);
-		}
-
-		/*
-		 * Just mark the record as dead.
-		 */
-		ret = tdb_ofs_write(
-			tdb, rec_ptr + offsetof(struct tdb_record, magic),
-			&magic);
-	}
-	else {
-		ret = tdb_do_delete(tdb, rec_ptr, &rec);
+	/*
+	 * Mark the record dead
+	 */
+	rec.magic = TDB_DEAD_MAGIC;
+	ret = tdb_rec_write(tdb, rec_ptr, &rec);
+	if (ret == -1) {
+		goto done;
 	}
 
-	if (ret == 0) {
-		tdb_increment_seqnum(tdb);
-	}
+	tdb_increment_seqnum(tdb);
 
+	ret = tdb_trim_dead(tdb, hash);
+done:
 	if (tdb_unlock(tdb, BUCKET(hash), F_WRLCK) != 0)
 		TDB_LOG((tdb, TDB_DEBUG_WARNING, "tdb_delete: WARNING tdb_unlock failed!\n"));
 	return ret;
diff --git a/lib/tdb/common/tdb_private.h b/lib/tdb/common/tdb_private.h
index 307cad92c2a..42aaac62f59 100644
--- a/lib/tdb/common/tdb_private.h
+++ b/lib/tdb/common/tdb_private.h
@@ -311,7 +311,6 @@ int tdb_unlock_record(struct tdb_context *tdb, tdb_off_t off);
 bool tdb_needs_recovery(struct tdb_context *tdb);
 int tdb_rec_read(struct tdb_context *tdb, tdb_off_t offset, struct tdb_record *rec);
 int tdb_rec_write(struct tdb_context *tdb, tdb_off_t offset, struct tdb_record *rec);
-int tdb_do_delete(struct tdb_context *tdb, tdb_off_t rec_ptr, struct tdb_record *rec);
 unsigned char *tdb_alloc_read(struct tdb_context *tdb, tdb_off_t offset, tdb_len_t len);
 int tdb_parse_data(struct tdb_context *tdb, TDB_DATA key,
 		   tdb_off_t offset, tdb_len_t len,
@@ -323,7 +322,7 @@ tdb_off_t tdb_find_lock_hash(struct tdb_context *tdb, TDB_DATA key, uint32_t has
 tdb_off_t tdb_find_dead(struct tdb_context *tdb, uint32_t hash,
 			struct tdb_record *r, tdb_len_t length,
 			tdb_off_t *p_last_ptr);
-int tdb_purge_dead(struct tdb_context *tdb, uint32_t hash);
+int tdb_trim_dead(struct tdb_context *tdb, uint32_t hash);
 void tdb_io_init(struct tdb_context *tdb);
 int tdb_expand(struct tdb_context *tdb, tdb_off_t size);
 tdb_off_t tdb_expand_adjust(tdb_off_t map_size, tdb_off_t size, int page_size);
-- 
2.11.0



More information about the samba-technical mailing list