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

If a hash chain has a loop, eventually the next_ptr
will cycle around and be identical to the 'slow' pointer.

Signed-off-by: Volker Lendecke <vl@samba.org>
Reviewed-by: Jeremy Allison <jra@samba.org>

2 files changed, 39 insertions, 0 deletions

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,