[PATCH] Make tdb a bit more robust against corrupt tdbs
Jeremy Allison
jra at samba.org
Mon Oct 8 19:00:15 UTC 2018
On Fri, Oct 05, 2018 at 03:24:03PM +0200, Volker Lendecke via samba-technical wrote:
> Hi!
>
> Attached find a few patches that make tdb a bit more robust against
> tdbs that contain circular hash chains. I did not cover all instances
> where we walk chains, but this might be a step in the right direction.
> Without these patches we sit in 100% cpu loops when we hit such a
> condition.
>
> The main one I did not touch yet is tdb_traverse. This is particularly
> difficult as the hash chain can change while we are traversing it. So
> we can't use the trick from rescue.c with the slow ptr.
>
> To enable imprecise, but safe traverse for a limited set of use cases
> I'm considering to write a function that will just marshall a complete
> hash chain into a predefined buffer. This should be really, really
> fast and should be good for background cleanup tasks. The main target
> here is gencache, which we don't clean up at all yet.
>
> Comments?
This code is really clever, thanks for the out-of-band explaination !
RB+ and pushed with an addition to the first commit message to help
me understand it later :-).
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 67f7326c92a21be03fa0bd2b079fdcbf49217a74 Mon Sep 17 00:00:00 2001
> From: Volker Lendecke <vl at samba.org>
> Date: Thu, 4 Oct 2018 15:20:10 +0200
> Subject: [PATCH 1/9] tdb: Add tdb_chainwalk_check
>
> This captures the tdb_rescue protection against circular hash chains
> with a slow pointer updated only on every other record traverse
>
> Signed-off-by: Volker Lendecke <vl at samba.org>
> ---
> lib/tdb/common/tdb.c | 29 +++++++++++++++++++++++++++++
> lib/tdb/common/tdb_private.h | 10 ++++++++++
> 2 files changed, 39 insertions(+)
>
> diff --git a/lib/tdb/common/tdb.c b/lib/tdb/common/tdb.c
> index 04f7f97eade..62df8eb1d32 100644
> --- a/lib/tdb/common/tdb.c
> +++ b/lib/tdb/common/tdb.c
> @@ -79,6 +79,35 @@ static int tdb_key_compare(TDB_DATA key, TDB_DATA data, void *private_data)
> return memcmp(data.dptr, key.dptr, data.dsize);
> }
>
> +void tdb_chainwalk_init(struct tdb_chainwalk_ctx *ctx, tdb_off_t ptr)
> +{
> + *ctx = (struct tdb_chainwalk_ctx) { .slow_ptr = ptr };
> +}
> +
> +bool tdb_chainwalk_check(struct tdb_context *tdb,
> + struct tdb_chainwalk_ctx *ctx,
> + tdb_off_t next_ptr)
> +{
> + int ret;
> +
> + if (ctx->slow_chase) {
> + ret = tdb_ofs_read(tdb, ctx->slow_ptr, &ctx->slow_ptr);
> + if (ret == -1) {
> + return false;
> + }
> + }
> + ctx->slow_chase = !ctx->slow_chase;
> +
> + if (next_ptr == ctx->slow_ptr) {
> + tdb->ecode = TDB_ERR_CORRUPT;
> + TDB_LOG((tdb, TDB_DEBUG_ERROR,
> + "tdb_chainwalk_check: circular chain\n"));
> + return false;
> + }
> +
> + return true;
> +}
> +
> /* Returns 0 on fail. On success, return offset of record, and fills
> in rec */
> static tdb_off_t tdb_find(struct tdb_context *tdb, TDB_DATA key, uint32_t hash,
> diff --git a/lib/tdb/common/tdb_private.h b/lib/tdb/common/tdb_private.h
> index eeac10a49ad..307cad92c2a 100644
> --- a/lib/tdb/common/tdb_private.h
> +++ b/lib/tdb/common/tdb_private.h
> @@ -191,6 +191,11 @@ struct tdb_lock_type {
> uint32_t ltype;
> };
>
> +struct tdb_chainwalk_ctx {
> + tdb_off_t slow_ptr;
> + bool slow_chase;
> +};
> +
> struct tdb_traverse_lock {
> struct tdb_traverse_lock *next;
> uint32_t off;
> @@ -198,6 +203,11 @@ struct tdb_traverse_lock {
> int lock_rw;
> };
>
> +void tdb_chainwalk_init(struct tdb_chainwalk_ctx *ctx, tdb_off_t ptr);
> +bool tdb_chainwalk_check(struct tdb_context *tdb,
> + struct tdb_chainwalk_ctx *ctx,
> + tdb_off_t next_ptr);
> +
> enum tdb_lock_flags {
> /* WAIT == F_SETLKW, NOWAIT == F_SETLK */
> TDB_LOCK_NOWAIT = 0,
> --
> 2.17.1
>
>
> From 94fe593c45ee7ee4c5f19f48aa9eb2e44c5d4ef8 Mon Sep 17 00:00:00 2001
> From: Volker Lendecke <vl at samba.org>
> Date: Thu, 4 Oct 2018 15:21:01 +0200
> Subject: [PATCH 2/9] tdb: Make tdb_find circular-safe
>
> Signed-off-by: Volker Lendecke <vl at samba.org>
> ---
> lib/tdb/common/tdb.c | 14 +++++++++-----
> 1 file changed, 9 insertions(+), 5 deletions(-)
>
> diff --git a/lib/tdb/common/tdb.c b/lib/tdb/common/tdb.c
> index 62df8eb1d32..c16e5779b87 100644
> --- a/lib/tdb/common/tdb.c
> +++ b/lib/tdb/common/tdb.c
> @@ -114,13 +114,18 @@ static tdb_off_t tdb_find(struct tdb_context *tdb, TDB_DATA key, uint32_t hash,
> struct tdb_record *r)
> {
> tdb_off_t rec_ptr;
> + struct tdb_chainwalk_ctx chainwalk;
>
> /* read in the hash top */
> if (tdb_ofs_read(tdb, TDB_HASH_TOP(hash), &rec_ptr) == -1)
> return 0;
>
> + tdb_chainwalk_init(&chainwalk, rec_ptr);
> +
> /* keep looking until we find the right record */
> while (rec_ptr) {
> + bool ok;
> +
> if (tdb_rec_read(tdb, rec_ptr, r) == -1)
> return 0;
>
> @@ -131,13 +136,12 @@ static tdb_off_t tdb_find(struct tdb_context *tdb, TDB_DATA key, uint32_t hash,
> NULL) == 0) {
> return rec_ptr;
> }
> - /* detect tight infinite loop */
> - if (rec_ptr == r->next) {
> - tdb->ecode = TDB_ERR_CORRUPT;
> - TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_find: loop detected.\n"));
> + rec_ptr = r->next;
> +
> + ok = tdb_chainwalk_check(tdb, &chainwalk, rec_ptr);
> + if (!ok) {
> return 0;
> }
> - rec_ptr = r->next;
> }
> tdb->ecode = TDB_ERR_NOEXIST;
> return 0;
> --
> 2.17.1
>
>
> From 167707e0dd1e78c217b3d877ddbf819eb7993550 Mon Sep 17 00:00:00 2001
> From: Volker Lendecke <vl at samba.org>
> Date: Thu, 4 Oct 2018 15:00:15 +0200
> Subject: [PATCH 3/9] tdb: Make tdb_dump_chain circular-list safe
>
> Signed-off-by: Volker Lendecke <vl at samba.org>
> ---
> lib/tdb/common/dump.c | 9 +++++++++
> 1 file changed, 9 insertions(+)
>
> diff --git a/lib/tdb/common/dump.c b/lib/tdb/common/dump.c
> index 73286b87350..d4e3478469b 100644
> --- a/lib/tdb/common/dump.c
> +++ b/lib/tdb/common/dump.c
> @@ -60,6 +60,7 @@ static tdb_off_t tdb_dump_record(struct tdb_context *tdb, int hash,
>
> static int tdb_dump_chain(struct tdb_context *tdb, int i)
> {
> + struct tdb_chainwalk_ctx chainwalk;
> tdb_off_t rec_ptr, top;
>
> if (i == -1) {
> @@ -74,11 +75,19 @@ static int tdb_dump_chain(struct tdb_context *tdb, int i)
> if (tdb_ofs_read(tdb, top, &rec_ptr) == -1)
> return tdb_unlock(tdb, i, F_WRLCK);
>
> + tdb_chainwalk_init(&chainwalk, rec_ptr);
> +
> if (rec_ptr)
> printf("hash=%d\n", i);
>
> while (rec_ptr) {
> + bool ok;
> rec_ptr = tdb_dump_record(tdb, i, rec_ptr);
> + ok = tdb_chainwalk_check(tdb, &chainwalk, rec_ptr);
> + if (!ok) {
> + printf("circular hash chain %d\n", i);
> + break;
> + }
> }
>
> return tdb_unlock(tdb, i, F_WRLCK);
> --
> 2.17.1
>
>
> From 0efd0245739c6cf0374e26416f305cb0d0b4e199 Mon Sep 17 00:00:00 2001
> From: Volker Lendecke <vl at samba.org>
> Date: Thu, 4 Oct 2018 15:25:59 +0200
> Subject: [PATCH 4/9] tdb: Make tdb_find_dead circular-safe
>
> Signed-off-by: Volker Lendecke <vl at samba.org>
> ---
> lib/tdb/common/tdb.c | 10 ++++++++++
> 1 file changed, 10 insertions(+)
>
> diff --git a/lib/tdb/common/tdb.c b/lib/tdb/common/tdb.c
> index c16e5779b87..4e433c89e1e 100644
> --- a/lib/tdb/common/tdb.c
> +++ b/lib/tdb/common/tdb.c
> @@ -523,6 +523,7 @@ tdb_off_t tdb_find_dead(struct tdb_context *tdb, uint32_t hash,
> tdb_off_t *p_last_ptr)
> {
> tdb_off_t rec_ptr, last_ptr;
> + struct tdb_chainwalk_ctx chainwalk;
> tdb_off_t best_rec_ptr = 0;
> tdb_off_t best_last_ptr = 0;
> struct tdb_record best = { .rec_len = UINT32_MAX };
> @@ -535,8 +536,12 @@ tdb_off_t tdb_find_dead(struct tdb_context *tdb, uint32_t hash,
> if (tdb_ofs_read(tdb, last_ptr, &rec_ptr) == -1)
> return 0;
>
> + tdb_chainwalk_init(&chainwalk, rec_ptr);
> +
> /* keep looking until we find the right record */
> while (rec_ptr) {
> + bool ok;
> +
> if (tdb_rec_read(tdb, rec_ptr, r) == -1)
> return 0;
>
> @@ -548,6 +553,11 @@ tdb_off_t tdb_find_dead(struct tdb_context *tdb, uint32_t hash,
> }
> last_ptr = rec_ptr;
> rec_ptr = r->next;
> +
> + ok = tdb_chainwalk_check(tdb, &chainwalk, rec_ptr);
> + if (!ok) {
> + return 0;
> + }
> }
>
> if (best.rec_len == UINT32_MAX) {
> --
> 2.17.1
>
>
> From f04a2ddb3ca4040cb4fb10b62ba944a5b2c6509d Mon Sep 17 00:00:00 2001
> From: Volker Lendecke <vl at samba.org>
> Date: Thu, 4 Oct 2018 16:42:45 +0200
> Subject: [PATCH 5/9] tdb: Make get_hash_length circular-safe
>
> Signed-off-by: Volker Lendecke <vl at samba.org>
> ---
> lib/tdb/common/summary.c | 8 ++++++++
> 1 file changed, 8 insertions(+)
>
> diff --git a/lib/tdb/common/summary.c b/lib/tdb/common/summary.c
> index c9b5bc4c1d0..a93eb93e734 100644
> --- a/lib/tdb/common/summary.c
> +++ b/lib/tdb/common/summary.c
> @@ -72,18 +72,26 @@ static size_t tally_mean(const struct tally *tally)
> static size_t get_hash_length(struct tdb_context *tdb, unsigned int i)
> {
> tdb_off_t rec_ptr;
> + struct tdb_chainwalk_ctx chainwalk;
> size_t count = 0;
>
> if (tdb_ofs_read(tdb, TDB_HASH_TOP(i), &rec_ptr) == -1)
> return 0;
>
> + tdb_chainwalk_init(&chainwalk, rec_ptr);
> +
> /* keep looking until we find the right record */
> while (rec_ptr) {
> struct tdb_record r;
> + bool ok;
> ++count;
> if (tdb_rec_read(tdb, rec_ptr, &r) == -1)
> return 0;
> rec_ptr = r.next;
> + ok = tdb_chainwalk_check(tdb, &chainwalk, rec_ptr);
> + if (!ok) {
> + return SIZE_MAX;
> + }
> }
> return count;
> }
> --
> 2.17.1
>
>
> From 691f9d1e957f0478fa2a982dc2953aea7ee02885 Mon Sep 17 00:00:00 2001
> From: Volker Lendecke <vl at samba.org>
> Date: Thu, 4 Oct 2018 17:12:25 +0200
> Subject: [PATCH 6/9] tdb: Align integer types
>
> Signed-off-by: Volker Lendecke <vl at samba.org>
> ---
> lib/tdb/common/freelist.c | 2 +-
> 1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/lib/tdb/common/freelist.c b/lib/tdb/common/freelist.c
> index 86fac2ff078..a19289a399c 100644
> --- a/lib/tdb/common/freelist.c
> +++ b/lib/tdb/common/freelist.c
> @@ -605,7 +605,7 @@ tdb_off_t tdb_allocate(struct tdb_context *tdb, int hash, tdb_len_t length,
> struct tdb_record *rec)
> {
> tdb_off_t ret;
> - int i;
> + uint32_t i;
>
> if (tdb->max_dead_records == 0) {
> /*
> --
> 2.17.1
>
>
> From 410040ff423a905ea1441144ff8216afead67245 Mon Sep 17 00:00:00 2001
> From: Volker Lendecke <vl at samba.org>
> Date: Thu, 4 Oct 2018 17:12:42 +0200
> Subject: [PATCH 7/9] tdb: Make the freelist walk circular-safe
>
> We can't really do the full check while the freelist is modified on the
> fly. As long as we don't merge any freelist entries, we should be good
> to apply this check.
>
> Signed-off-by: Volker Lendecke <vl at samba.org>
> ---
> lib/tdb/common/freelist.c | 15 +++++++++++++++
> 1 file changed, 15 insertions(+)
>
> diff --git a/lib/tdb/common/freelist.c b/lib/tdb/common/freelist.c
> index a19289a399c..8870a418328 100644
> --- a/lib/tdb/common/freelist.c
> +++ b/lib/tdb/common/freelist.c
> @@ -444,6 +444,8 @@ static tdb_off_t tdb_allocate_from_freelist(
> struct tdb_context *tdb, tdb_len_t length, struct tdb_record *rec)
> {
> tdb_off_t rec_ptr, last_ptr, newrec_ptr;
> + struct tdb_chainwalk_ctx chainwalk;
> + bool modified;
> struct {
> tdb_off_t rec_ptr, last_ptr;
> tdb_len_t rec_len;
> @@ -466,6 +468,9 @@ static tdb_off_t tdb_allocate_from_freelist(
> if (tdb_ofs_read(tdb, FREELIST_TOP, &rec_ptr) == -1)
> return 0;
>
> + modified = false;
> + tdb_chainwalk_init(&chainwalk, rec_ptr);
> +
> bestfit.rec_ptr = 0;
> bestfit.last_ptr = 0;
> bestfit.rec_len = 0;
> @@ -526,6 +531,8 @@ static tdb_off_t tdb_allocate_from_freelist(
> merge_created_candidate = true;
> }
>
> + modified = true;
> +
> continue;
> }
>
> @@ -542,6 +549,14 @@ static tdb_off_t tdb_allocate_from_freelist(
> last_ptr = rec_ptr;
> rec_ptr = rec->next;
>
> + if (!modified) {
> + bool ok;
> + ok = tdb_chainwalk_check(tdb, &chainwalk, rec_ptr);
> + if (!ok) {
> + return 0;
> + }
> + }
> +
> /* if we've found a record that is big enough, then
> stop searching if its also not too big. The
> definition of 'too big' changes as we scan
> --
> 2.17.1
>
>
> From b8178067aaf461d9a62023031aa03948dfd58bea Mon Sep 17 00:00:00 2001
> From: Volker Lendecke <vl at samba.org>
> Date: Thu, 4 Oct 2018 21:41:27 +0200
> Subject: [PATCH 8/9] tdb: Basic test for circular hash chain fix
>
> This just walks tdb_find by searching for a nonexistent record
>
> Signed-off-by: Volker Lendecke <vl at samba.org>
> ---
> lib/tdb/test/circular_chain.tdb | Bin 0 -> 272 bytes
> lib/tdb/test/run-circular-chain.c | 42 ++++++++++++++++++++++++++++++
> lib/tdb/wscript | 1 +
> 3 files changed, 43 insertions(+)
> create mode 100644 lib/tdb/test/circular_chain.tdb
> create mode 100644 lib/tdb/test/run-circular-chain.c
>
> diff --git a/lib/tdb/test/circular_chain.tdb b/lib/tdb/test/circular_chain.tdb
> new file mode 100644
> index 0000000000000000000000000000000000000000..1e143d347af21eb3cf717ae6b4b67502a2d4eca8
> GIT binary patch
> literal 272
> zcmWG>aZ*Uj%t_^9zz%XH8Pyokq<H7oepC4Q&k9YL=G+fJ8!iAb2M~kY1i~+iyf|k9
> n-I$ofz at Px+ZvbLs`ThLYdqDEZDG+&d{ZrQ at 3xMQP(;)Hy`vn#B
>
> literal 0
> HcmV?d00001
>
> diff --git a/lib/tdb/test/run-circular-chain.c b/lib/tdb/test/run-circular-chain.c
> new file mode 100644
> index 00000000000..4fb32a26e0f
> --- /dev/null
> +++ b/lib/tdb/test/run-circular-chain.c
> @@ -0,0 +1,42 @@
> +#include "../common/tdb_private.h"
> +#include "../common/io.c"
> +#include "../common/tdb.c"
> +#include "../common/lock.c"
> +#include "../common/freelist.c"
> +#include "../common/traverse.c"
> +#include "../common/transaction.c"
> +#include "../common/error.c"
> +#include "../common/open.c"
> +#include "../common/check.c"
> +#include "../common/hash.c"
> +#include "../common/mutex.c"
> +#include "tap-interface.h"
> +#include <stdlib.h>
> +#include "logging.h"
> +
> +int main(int argc, char *argv[])
> +{
> + struct tdb_context *tdb;
> + TDB_DATA key;
> +
> + plan_tests(3);
> + tdb = tdb_open_ex(
> + "test/circular_chain.tdb",
> + 0,
> + TDB_DEFAULT,
> + O_RDONLY,
> + 0600,
> + &taplogctx,
> + NULL);
> +
> + ok1(tdb);
> + key.dsize = strlen("x");
> + key.dptr = discard_const_p(uint8_t, "x");
> +
> + ok1(tdb_exists(tdb, key) == 0);
> + ok1(tdb_error(tdb) == TDB_ERR_CORRUPT);
> +
> + tdb_close(tdb);
> +
> + return exit_status();
> +}
> diff --git a/lib/tdb/wscript b/lib/tdb/wscript
> index 6ffca9e34b7..7a08c80f466 100644
> --- a/lib/tdb/wscript
> +++ b/lib/tdb/wscript
> @@ -55,6 +55,7 @@ tdb1_unit_tests = [
> 'run-mutex-transaction1',
> 'run-mutex-die',
> 'run-mutex1',
> + 'run-circular-chain',
> ]
>
> def options(opt):
> --
> 2.17.1
>
>
> From bbdf7e8810470870631513aea659b8f92202c5c4 Mon Sep 17 00:00:00 2001
> From: Volker Lendecke <vl at samba.org>
> Date: Thu, 4 Oct 2018 17:42:09 +0200
> Subject: [PATCH 9/9] tdb: Basic test for circular freelist fix
>
> Try to store a record for which the (circular) freelist does not have
> any entry.
>
> Signed-off-by: Volker Lendecke <vl at samba.org>
> ---
> lib/tdb/test/circular_freelist.tdb | Bin 0 -> 400 bytes
> lib/tdb/test/run-circular-freelist.c | 50 +++++++++++++++++++++++++++
> lib/tdb/wscript | 1 +
> 3 files changed, 51 insertions(+)
> create mode 100644 lib/tdb/test/circular_freelist.tdb
> create mode 100644 lib/tdb/test/run-circular-freelist.c
>
> diff --git a/lib/tdb/test/circular_freelist.tdb b/lib/tdb/test/circular_freelist.tdb
> new file mode 100644
> index 0000000000000000000000000000000000000000..f1c85e5c311886be154b0b33b73c6a607ce53b70
> GIT binary patch
> literal 400
> zcmWG>aZ*Uj%t_^9zz%XH8Pyokq<H7oepC4Q&k9YLrrZFaBMP7n;Q-nMVuJ9?A}`LF
> zKsP2PGB79r`5<-3@*xKWywjfjyP1>(k>3DRgDk(F|9THde{wQJ{sNl3R@~fkApI#R
> u5cv;i@>AC&3xM>erb6Te(ClaUtr-N;pOyxZH$aom_WUpzq(40!A`bw1o-39B
>
> literal 0
> HcmV?d00001
>
> diff --git a/lib/tdb/test/run-circular-freelist.c b/lib/tdb/test/run-circular-freelist.c
> new file mode 100644
> index 00000000000..f1bec87b7ba
> --- /dev/null
> +++ b/lib/tdb/test/run-circular-freelist.c
> @@ -0,0 +1,50 @@
> +#include "../common/tdb_private.h"
> +#include "../common/io.c"
> +#include "../common/tdb.c"
> +#include "../common/lock.c"
> +#include "../common/freelist.c"
> +#include "../common/traverse.c"
> +#include "../common/transaction.c"
> +#include "../common/error.c"
> +#include "../common/open.c"
> +#include "../common/check.c"
> +#include "../common/hash.c"
> +#include "../common/mutex.c"
> +#include "tap-interface.h"
> +#include <stdlib.h>
> +#include "logging.h"
> +
> +int main(int argc, char *argv[])
> +{
> + struct tdb_context *tdb;
> + TDB_DATA key, data;
> +
> + plan_tests(3);
> + tdb = tdb_open_ex(
> + "test/circular_freelist.tdb",
> + 0,
> + TDB_DEFAULT,
> + O_RDWR,
> + 0600,
> + &taplogctx,
> + NULL);
> +
> + ok1(tdb);
> +
> + /*
> + * All freelist records are just 1 byte key and value. Insert
> + * something that will walk the whole freelist and hit the
> + * circle.
> + */
> + key.dsize = strlen("x");
> + key.dptr = discard_const_p(uint8_t, "x");
> + data.dsize = strlen("too long");
> + data.dptr = discard_const_p(uint8_t, "too long");
> +
> + ok1(tdb_store(tdb, key, data, TDB_INSERT) == -1);
> + ok1(tdb_error(tdb) == TDB_ERR_CORRUPT);
> +
> + tdb_close(tdb);
> +
> + return exit_status();
> +}
> diff --git a/lib/tdb/wscript b/lib/tdb/wscript
> index 7a08c80f466..3ab21fcebc1 100644
> --- a/lib/tdb/wscript
> +++ b/lib/tdb/wscript
> @@ -56,6 +56,7 @@ tdb1_unit_tests = [
> 'run-mutex-die',
> 'run-mutex1',
> 'run-circular-chain',
> + 'run-circular-freelist',
> ]
>
> def options(opt):
> --
> 2.17.1
>
More information about the samba-technical
mailing list