[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