[PATCH] Make tdb a bit more robust against corrupt tdbs

[Douglas Bagnall]

Over two years ago, on 2018-10-16, Volker Lendecke 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?

Through fuzzing I found a couple of the other cases Volker mentions. I
wasn't actually aware of this work, and I decided against the two-speed
algorithm on the grounds of performance and fiddliness (though as
implemented in Volker's patches, it doesn't look that bad).

The patch I have for a loop in the freelist that relies on the fact that
we are already counting bytes, which is certain to overflow if and only
if there is a loop. I think this works well there because it is almost
free in the common case, and you only count to 4 billion in the sad
case, which takes no time at all these days. You can wait a second to be
told your database was in ruins but was perhaps fixed by a repack.

Then I tried something similar for traverse, about which I am utterly
unconvinced. I only show it below to provoke discussion.

What I wonder is whether something like a per-chain count of bytes, as
in the freelist, work for traverse? There's the chance of a false
positive if a chain changes enough times to seem like it contains
4Gbytes, but seems to me like a sign that you've got pathologically
unbalanced chains anyway. Is seems-like-forever close enough to forever
to abandon the search?

I'm not very familiar with tdb.

cheers,
Douglas
-------------- next part --------------
From d5f7dead46c1cd0312d965065b003551fc74a712 Mon Sep 17 00:00:00 2001
From: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Wed, 27 Jan 2021 12:51:30 +1300
Subject: [PATCH 1/2] tdb: notice freelist loops in transaction

repacking is probably a good idea in this situation

Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
---
 lib/tdb/common/transaction.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/lib/tdb/common/transaction.c b/lib/tdb/common/transaction.c
index 4f8d1f8cdcc..e1f17538aee 100644
--- a/lib/tdb/common/transaction.c
+++ b/lib/tdb/common/transaction.c
@@ -1097,7 +1097,13 @@ static bool repack_worthwhile(struct tdb_context *tdb)
 	}
 
 	while (ptr != 0 && tdb_rec_free_read(tdb, ptr, &rec) == 0) {
-		total += rec.rec_len;
+		tdb_len_t tmp = total + rec.rec_len;
+		if (tmp < total) {
+			TDB_LOG((tdb, TDB_DEBUG_ERROR,
+				 "free list total overflow (probable loop in list)\n"));
+			return true;
+		}
+		total = tmp;
 		if (rec.rec_len > largest) {
 			largest = rec.rec_len;
 		}
-- 
2.25.1


From b5e45f2494ebed7b51e5196947a0a30bf1d45f56 Mon Sep 17 00:00:00 2001
From: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
Date: Sat, 30 Jan 2021 13:42:18 +1300
Subject: [PATCH 2/2] tdb: traverse will (eventually) notice chain loops

If there is a loop in a chain (e.g. A->next points to B an B->next
points to A), a traverse will not stop.

We already defend against the shortest loops (A->next points to A) in
tdb_next_lock(), but longer loops are not detected.

In other places we use the two speed walk algorithm, which is faster
in the loop case, but slower in ordinary uncorrupted case. We avoid
that here because we don't want to pay the cost for somethng that
should hardly ever happen.

Signed-off-by: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
---
 lib/tdb/common/traverse.c | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/lib/tdb/common/traverse.c b/lib/tdb/common/traverse.c
index d69e7dff285..c494326cb8d 100644
--- a/lib/tdb/common/traverse.c
+++ b/lib/tdb/common/traverse.c
@@ -197,6 +197,21 @@ static int tdb_traverse_internal(struct tdb_context *tdb,
 		}
 
 		count++;
+		if (count > tdb->map_size / sizeof(rec)) {
+			/* we can only get anywhere near this upper bound if
+			 * there is a loop in the linked list */
+			tdb->ecode = TDB_ERR_CORRUPT;
+			TDB_LOG((tdb, TDB_DEBUG_FATAL,
+				 "tdb_traverse: there is a loop in a chain "
+				 "(count %u, map_size %u).\n",
+				 (unsigned)count,
+				 (unsigned)tdb->map_size));
+			if (tdb_unlock_record(tdb, tl->off) != 0) {
+				TDB_LOG((tdb, TDB_DEBUG_FATAL,
+					 "tdb_traverse: post-loop unlock failed\n"));
+			}
+			goto out;
+		}
 		/* now read the full record */
 		nread = tdb->methods->tdb_read(tdb, tl->off + sizeof(rec),
 					       key.dptr, full_len, 0);
-- 
2.25.1