Skip to contentSkip to conversation

dm persistent-data: detect btree cycles and record space-map errors

RFC PATCH New Ye Bin 1 participant 3 messages Aug 20 Device mapper

lore
Share & tools
lore

Ye Bin

author
#0 lore raw

cover dm persistent-data: detect btree cycles and record space-map errors

From: Ye Bin <[email protected]>

This series hardens dm-persistent-data against metadata corruption that can leave the kernel hung in an uninterruptible state. The two patches attack the same class of problem from both sides: symptom detection and root-cause prevention.

Patch 1 adds a depth limit (DM_BTREE_MAX_DEPTH = 16) to every unbounded btree traversal loop (lookup, insert, overwrite, remove, find_key). When metadata is corrupted such that a node's value points back to an ancestor or to itself, these loops currently never terminate, hanging the kernel. With the limit in place the traversal returns -ELOOP instead, and dm-thin handles this error by aborting the transaction and downgrading the pool to read-only mode so no further writes hit the corrupted metadata.

Patch 2 addresses a root cause of such corruption. The transaction manager's dm_tm_inc/dm_tm_dec/dm_tm_inc_range/dm_tm_dec_range wrappers have void return types, so when the underlying space-map operations fail the error is silently swallowed and the transaction is committed with inconsistent reference counts. This can produce permanent space leaks, premature refcount drops, and -- critically -- self-referencing btree nodes that trigger the very infinite loops that patch 1 catches. The fix records the first space-map failure in a sticky error flag (sm_error in the transaction manager, data_sm_error in dm_pool_metadata) and refuses to commit while the flag is set, all without changing any function signatures.

Ye Bin (2):
dm persistent-data: add btree traversal depth limit to detect metadata
corruption
dm persistent-data: record space-map errors in transaction manager

 drivers/md/dm-thin-metadata.c                 | 65 +++++++++++++---
 drivers/md/dm-thin.c                          |  9 +++
 drivers/md/persistent-data/dm-btree-remove.c  | 14 ++++
 drivers/md/persistent-data/dm-btree.c         | 28 +++++++
 drivers/md/persistent-data/dm-btree.h         |  8 ++
 .../persistent-data/dm-transaction-manager.c  | 74 ++++++++++++++++++-
 .../persistent-data/dm-transaction-manager.h  |  6 ++
 7 files changed, 191 insertions(+), 13 deletions(-)
Signature · 1 line
2.34.1
author
#1 lore raw

RFC PATCH 1/2 dm persistent-data: add btree traversal depth limit to detect metadata corruption

From: Ye Bin <[email protected]>

The btree traversal loops in dm-persistent-data are unbounded do/while or for(;;) loops. When metadata is corrupted such that a node's value points back to an ancestor (or to itself), these loops never terminate, leaving the kernel hung in an uninterruptible state.

Add a DM_BTREE_MAX_DEPTH (16) counter to all unbounded traversal loops:

  - btree_lookup_raw()             (read path)
  - btree_insert_raw()             (insert path)
  - __btree_get_overwrite_leaf()   (overwrite path)
  - remove_raw()                   (remove path)
  - remove_nearest()               (remove_leaves path)
  - find_key()                     (find_highest/lowest_key path)

When the depth limit is exceeded, return -ELOOP and log a rate-limited error indicating possible metadata corruption.

The cursor path (find_leaf) is already protected by DM_BTREE_CURSOR_MAX_DEPTH in push_node(). The dm_btree_del() path is already protected by MAX_SPINE_DEPTH (64) and __check_holder().

In dm-thin.c, handle -ELOOP from dm_thin_find_block() in all three call sites (process_cell, __process_bio_read_only, and thin_bio_map) by calling metadata_operation_failed() to abort the transaction and downgrade the pool to read-only mode, preventing further writes to the corrupted metadata.

16 levels can address well over 200^16 entries, far exceeding any practical thin pool size, so the limit never affects valid metadata.

---
 drivers/md/dm-thin.c                         |  9 +++++++
 drivers/md/persistent-data/dm-btree-remove.c | 14 ++++++++++
 drivers/md/persistent-data/dm-btree.c        | 28 ++++++++++++++++++++
 drivers/md/persistent-data/dm-btree.h        |  8 ++++++
 4 files changed, 59 insertions(+)
drivers/md/dm-thin.c +9 -0
index 59392de7a477..6492c6c3852d 100644
@@ -1997,6 +1997,9 @@ static void process_cell(struct thin_c *tc, struct dm_bio_prison_cell *cell)
 	default:
 		DMERR_LIMIT("%s: dm_thin_find_block() failed: error = %d",
 			    __func__, r);
+		if (r == -ELOOP)
+			metadata_operation_failed(pool,
+						  "btree cycle detected", r);
 		cell_defer_no_holder(tc, cell);
 		bio_io_error(bio);
 		break;
@@ -2065,6 +2068,9 @@ static void __process_bio_read_only(struct thin_c *tc, struct bio *bio,
 	default:
 		DMERR_LIMIT("%s: dm_thin_find_block() failed: error = %d",
 			    __func__, r);
+		if (r == -ELOOP)
+			metadata_operation_failed(tc->pool,
+						  "btree cycle detected", r);
 		if (cell)
 			cell_defer_no_holder(tc, cell);
 		bio_io_error(bio);
@@ -2802,6 +2808,9 @@ static int thin_bio_map(struct dm_target *ti, struct bio *bio)
 		 * dm_thin_find_block can fail with -EINVAL if the
 		 * pool is switched to fail-io mode.
 		 */
+		if (r == -ELOOP)
+			metadata_operation_failed(tc->pool,
+						  "btree cycle detected", r);
 		bio_io_error(bio);
 		cell_defer_no_holder(tc, virt_cell);
 		return DM_MAPIO_SUBMITTED;
drivers/md/persistent-data/dm-btree-remove.c +14 -0
index aeec5b9a1dd5..7e0560f71729 100644
@@ -555,8 +555,15 @@ static int remove_raw(struct shadow_spine *s, struct dm_btree_info *info,
 {
 	int i = *index, r;
 	struct btree_node *n;
+	unsigned int depth = 0;
 
 	for (;;) {
+		if (depth++ >= DM_BTREE_MAX_DEPTH) {
+			DMERR_LIMIT("%s: exceeded max depth (%u), possible metadata corruption",
+				    __func__, DM_BTREE_MAX_DEPTH);
+			return -ELOOP;
+		}
+
 		r = shadow_step(s, root, vt);
 		if (r < 0)
 			break;
@@ -649,8 +656,15 @@ static int remove_nearest(struct shadow_spine *s, struct dm_btree_info *info,
 {
 	int i = *index, r;
 	struct btree_node *n;
+	unsigned int depth = 0;
 
 	for (;;) {
+		if (depth++ >= DM_BTREE_MAX_DEPTH) {
+			DMERR_LIMIT("%s: exceeded max depth (%u), possible metadata corruption",
+				    __func__, DM_BTREE_MAX_DEPTH);
+			return -ELOOP;
+		}
+
 		r = shadow_step(s, root, vt);
 		if (r < 0)
 			break;
drivers/md/persistent-data/dm-btree.c +28 -0
index dd02eee4a23c..3004537c75a1 100644
@@ -346,8 +346,15 @@ static int btree_lookup_raw(struct ro_spine *s, dm_block_t block, uint64_t key,
 {
 	int i, r;
 	uint32_t flags, nr_entries;
+	unsigned int depth = 0;
 
 	do {
+		if (depth++ >= DM_BTREE_MAX_DEPTH) {
+			DMERR_LIMIT("%s: exceeded max depth (%u), possible metadata corruption",
+				    __func__, DM_BTREE_MAX_DEPTH);
+			return -ELOOP;
+		}
+
 		r = ro_step(s, block);
 		if (r < 0)
 			return r;
@@ -1095,8 +1102,15 @@ static int btree_insert_raw(struct shadow_spine *s, dm_block_t root,
 {
 	int r, i = *index, top = 1;
 	struct btree_node *node;
+	unsigned int depth = 0;
 
 	for (;;) {
+		if (depth++ >= DM_BTREE_MAX_DEPTH) {
+			DMERR_LIMIT("%s: exceeded max depth (%u), possible metadata corruption",
+				    __func__, DM_BTREE_MAX_DEPTH);
+			return -ELOOP;
+		}
+
 		r = shadow_step(s, root, vt);
 		if (r < 0)
 			return r;
@@ -1158,9 +1172,16 @@ static int __btree_get_overwrite_leaf(struct shadow_spine *s, dm_block_t root,
 {
 	int r, i = -1;
 	struct btree_node *node;
+	unsigned int depth = 0;
 
 	*index = 0;
 	for (;;) {
+		if (depth++ >= DM_BTREE_MAX_DEPTH) {
+			DMERR_LIMIT("%s: exceeded max depth (%u), possible metadata corruption",
+				    __func__, DM_BTREE_MAX_DEPTH);
+			return -ELOOP;
+		}
+
 		r = shadow_step(s, root, &s->info->value_type);
 		if (r < 0)
 			return r;
@@ -1342,8 +1363,15 @@ static int find_key(struct ro_spine *s, dm_block_t block, bool find_highest,
 {
 	int i, r;
 	uint32_t flags;
+	unsigned int depth = 0;
 
 	do {
+		if (depth++ >= DM_BTREE_MAX_DEPTH) {
+			DMERR_LIMIT("%s: exceeded max depth (%u), possible metadata corruption",
+				    __func__, DM_BTREE_MAX_DEPTH);
+			return -ELOOP;
+		}
+
 		r = ro_step(s, block);
 		if (r < 0)
 			return r;
drivers/md/persistent-data/dm-btree.h +8 -0
index 1b92acd7823d..617d808ca8dd 100644
@@ -180,6 +180,14 @@ int dm_btree_walk(struct dm_btree_info *info, dm_block_t root,
 
 /*----------------------------------------------------------------*/
 
+/*
+ * Maximum depth of btree traversal.  Used to detect cycles caused by
+ * metadata corruption (e.g. a node whose value points back to itself).
+ * 16 levels can address well over 200^16 entries, far exceeding any
+ * practical thin pool size.
+ */
+#define DM_BTREE_MAX_DEPTH 16
+
 /*
  * Cursor API.  This does not follow the rolling lock convention.  Since we
  * know the order that values are required we can issue prefetches to speed
Signature · 1 line
2.34.1
author
#2 lore raw

RFC PATCH 2/2 dm persistent-data: record space-map errors in transaction manager

In reply to Ye Bin

From: Ye Bin <[email protected]>

dm_tm_inc(), dm_tm_dec(), dm_tm_inc_range(), and dm_tm_dec_range() have void return types, so when the underlying space-map operations (dm_sm_inc_block/dec_block/inc_blocks/dec_blocks) fail, the error is silently swallowed. The transaction proceeds and may be committed with inconsistent reference counts, leading to:

1. data_block_dec failure during device deletion: a data block's refcount is not decremented, causing a permanent space leak that is silently persisted on commit.

2. inc_children failure during shadow of a shared node: a child node's refcount is not incremented. When the old shared parent is later released, the child's refcount drops to zero prematurely. The block allocator can then reuse that child block as a shadow copy of the parent (which still contains a pointer to it), creating a self-referencing node that causes infinite loops in all btree traversal paths (mitigated by the depth-limit patch, but the underlying corruption remains).

3. dm_tm_dec failure during rebalance merge: an internal node is not freed, causing a metadata space leak.

Fix this without changing any function signatures:

- Add a sticky int sm_error field to struct dm_transaction_manager. dm_tm_inc/dm_tm_dec/dm_tm_inc_range/dm_tm_dec_range record the first error in sm_error. Since all kernel error return values are non-zero, sm_error == 0 unambiguously means "no error".

- dm_tm_pre_commit() and dm_tm_commit() check sm_error and refuse to commit if it is non-zero, returning the recorded error.

- dm_tm_clear_error() resets sm_error to 0. Called in __begin_transaction() at the start of each new transaction so a fresh transaction can proceed after the previous one was aborted.

Similarly, the data space-map operations (data_block_inc/data_block_dec in dm-thin-metadata.c) call dm_sm_inc_blocks/dm_sm_dec_blocks() directly via with_runs(), bypassing the transaction manager entirely. Add a parallel int data_sm_error field to struct dm_pool_metadata:

- with_runs() is changed to return int so errors propagate.
- data_block_inc/data_block_dec record the first error in data_sm_error.
- __commit_transaction() checks data_sm_error and refuses to commit if it is non-zero.
- __begin_transaction() and dm_pool_abort_metadata() clear data_sm_error so a fresh transaction can proceed after an abort.

The sm_error and data_sm_error fields are accessed only under pmd->root_lock (write-locked for commit/abort, read-locked for inc/dec during metadata operations), so no additional locking is needed.

---
 drivers/md/dm-thin-metadata.c                 | 65 +++++++++++++---
 .../persistent-data/dm-transaction-manager.c  | 74 ++++++++++++++++++-
 .../persistent-data/dm-transaction-manager.h  |  6 ++
 3 files changed, 132 insertions(+), 13 deletions(-)
drivers/md/dm-thin-metadata.c +56 -9
index e60e1326376a..e7e7facc8d89 100644
@@ -227,6 +227,16 @@ struct dm_pool_metadata {
 	 */
 	__u8 data_space_map_root[SPACE_MAP_ROOT_SIZE];
 	__u8 metadata_space_map_root[SPACE_MAP_ROOT_SIZE];
+
+	/*
+	 * Sticky error flag for data space-map operations (inc/dec)
+	 * that were silently swallowed by the void value_type inc/dec
+	 * callbacks.  A non-zero value indicates the data space map is
+	 * inconsistent and the transaction must not be committed.
+	 * Checked in __commit_transaction(); cleared in
+	 * __begin_transaction() and dm_pool_abort_metadata().
+	 */
+	int data_sm_error;
 };
 
 struct dm_thin_device {
@@ -324,12 +334,13 @@ static void unpack_block_time(uint64_t v, dm_block_t *b, uint32_t *t)
  */
 typedef int (*run_fn)(struct dm_space_map *, dm_block_t, dm_block_t);
 
-static void with_runs(struct dm_space_map *sm, const __le64 *value_le, unsigned int count, run_fn fn)
+static int with_runs(struct dm_space_map *sm, const __le64 *value_le, unsigned int count, run_fn fn)
 {
 	uint64_t b, begin, end;
 	uint32_t t;
 	bool in_run = false;
 	unsigned int i;
+	int r = 0;
 
 	for (i = 0; i < count; i++, value_le++) {
 		/* We know value_le is 8 byte aligned */
@@ -339,7 +350,9 @@ static void with_runs(struct dm_space_map *sm, const __le64 *value_le, unsigned
 			if (b == end) {
 				end++;
 			} else {
-				fn(sm, begin, end);
+				r = fn(sm, begin, end);
+				if (r)
+					return r;
 				begin = b;
 				end = b + 1;
 			}
@@ -351,19 +364,35 @@ static void with_runs(struct dm_space_map *sm, const __le64 *value_le, unsigned
 	}
 
 	if (in_run)
-		fn(sm, begin, end);
+		r = fn(sm, begin, end);
+
+	return r;
 }
 
 static void data_block_inc(void *context, const void *value_le, unsigned int count)
 {
-	with_runs((struct dm_space_map *) context,
-		  (const __le64 *) value_le, count, dm_sm_inc_blocks);
+	struct dm_pool_metadata *pmd = context;
+	int r;
+
+	r = with_runs(pmd->data_sm, (const __le64 *) value_le,
+		      count, dm_sm_inc_blocks);
+	if (r && !pmd->data_sm_error) {
+		DMERR_LIMIT("data_block_inc failed: error %d", r);
+		pmd->data_sm_error = r;
+	}
 }
 
 static void data_block_dec(void *context, const void *value_le, unsigned int count)
 {
-	with_runs((struct dm_space_map *) context,
-		  (const __le64 *) value_le, count, dm_sm_dec_blocks);
+	struct dm_pool_metadata *pmd = context;
+	int r;
+
+	r = with_runs(pmd->data_sm, (const __le64 *) value_le,
+		      count, dm_sm_dec_blocks);
+	if (r && !pmd->data_sm_error) {
+		DMERR_LIMIT("data_block_dec failed: error %d", r);
+		pmd->data_sm_error = r;
+	}
 }
 
 static int data_block_equal(void *context, const void *value1_le, const void *value2_le)
@@ -485,7 +514,7 @@ static void __setup_btree_details(struct dm_pool_metadata *pmd)
 {
 	pmd->info.tm = pmd->tm;
 	pmd->info.levels = 2;
-	pmd->info.value_type.context = pmd->data_sm;
+	pmd->info.value_type.context = pmd;
 	pmd->info.value_type.size = sizeof(__le64);
 	pmd->info.value_type.inc = data_block_inc;
 	pmd->info.value_type.dec = data_block_dec;
@@ -504,7 +533,7 @@ static void __setup_btree_details(struct dm_pool_metadata *pmd)
 
 	pmd->bl_info.tm = pmd->tm;
 	pmd->bl_info.levels = 1;
-	pmd->bl_info.value_type.context = pmd->data_sm;
+	pmd->bl_info.value_type.context = pmd;
 	pmd->bl_info.value_type.size = sizeof(__le64);
 	pmd->bl_info.value_type.inc = data_block_inc;
 	pmd->bl_info.value_type.dec = data_block_dec;
@@ -846,6 +875,15 @@ static int __begin_transaction(struct dm_pool_metadata *pmd)
 	pmd->data_block_size = le32_to_cpu(disk_super->data_block_size);
 
 	dm_bm_unlock(sblock);
+
+	/*
+	 * Start the new transaction with a clean error slate.  Any
+	 * space-map errors from the previous (aborted) transaction
+	 * must not carry over.
+	 */
+	dm_tm_clear_error(pmd->tm);
+	pmd->data_sm_error = 0;
+
 	return 0;
 }
 
@@ -899,6 +937,12 @@ static int __commit_transaction(struct dm_pool_metadata *pmd)
 	if (unlikely(!pmd->in_service))
 		return 0;
 
+	if (pmd->data_sm_error) {
+		DMERR("aborting commit due to earlier data space-map error: %d",
+		      pmd->data_sm_error);
+		return pmd->data_sm_error;
+	}
+
 	if (pmd->pre_commit_fn) {
 		r = pmd->pre_commit_fn(pmd->pre_commit_context);
 		if (r < 0) {
@@ -976,6 +1020,7 @@ struct dm_pool_metadata *dm_pool_metadata_open(struct block_device *bdev,
 	pmd->data_block_size = data_block_size;
 	pmd->pre_commit_fn = NULL;
 	pmd->pre_commit_context = NULL;
+	pmd->data_sm_error = 0;
 
 	r = __create_persistent_data_objects(pmd, format_device);
 	if (r) {
@@ -1894,6 +1939,8 @@ int dm_pool_abort_metadata(struct dm_pool_metadata *pmd)
 	r = __open_or_format_metadata(pmd, false);
 	if (r)
 		pmd->fail_io = true;
+	else
+		pmd->data_sm_error = 0;
 	pmd_write_unlock(pmd);
 	return r;
 }
drivers/md/persistent-data/dm-transaction-manager.c +70 -4

139 lines not on this page · raw message

drivers/md/persistent-data/dm-transaction-manager.h +6 -0
index 61a8d10825ca..f3c50c3f9964 100644
@@ -105,6 +105,12 @@ void dm_tm_inc_range(struct dm_transaction_manager *tm, dm_block_t b, dm_block_t
 void dm_tm_dec(struct dm_transaction_manager *tm, dm_block_t b);
 void dm_tm_dec_range(struct dm_transaction_manager *tm, dm_block_t b, dm_block_t e);
 
+/*
+ * Clear the sticky space-map error flag.  Should be called at the start
+ * of each new transaction.
+ */
+void dm_tm_clear_error(struct dm_transaction_manager *tm);
+
 /*
  * Builds up runs of adjacent blocks, and then calls the given fn
  * (typically dm_tm_inc/dec).  Very useful when you have to perform
Signature · 1 line
2.34.1