[PATCH] Make tdb record deletion circular-chain safe
Jeremy Allison
jra at samba.org
Mon Oct 29 21:37:04 UTC 2018
On Thu, Oct 25, 2018 at 09:12:44PM +0200, Volker Lendecke via samba-technical wrote:
> 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!
OK, went through this *really* carefully, and LGTM !
RB+ and pushed.
The only possible tweak I could see was in the
last patch, where you have:
> + int num_dead = 0;
and are comparing it to tdb->max_dead_records,
which is a uint32_t. However tdb->max_dead_records
is only ever initialized as follows:
lib/tdb/common/open.c: tdb->max_dead_records = (tdb_flags & TDB_VOLATILE) ? 5 : 0;
so I can't see any chance of integer wrap or overflow
here (there'll never be UINT_32_MAX dead records :-).
If you later decide on integer matching we might
change num_dead to uint32_t with a wrap check but
that would only be for tidyness-sake, I can't see
any practical issues with int here.
Cheers,
Jeremy.
> --
> 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
> 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