[PATCH] Make tdb a bit more robust against corrupt tdbs
Volker Lendecke
Volker.Lendecke at SerNet.DE
Fri Oct 5 13:24:03 UTC 2018
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?
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 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