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

Ye Bin <[email protected]>
Newsgroups dev.linux.lists.dm-devel
Message-ID <[email protected]> 
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.

Signed-off-by: Ye Bin <[email protected]>
---
 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(+)

diff --git a/drivers/md/dm-thin.c b/drivers/md/dm-thin.c
index 59392de7a477..6492c6c3852d 100644
--- a/drivers/md/dm-thin.c
+++ b/drivers/md/dm-thin.c
@@ -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;
diff --git a/drivers/md/persistent-data/dm-btree-remove.c b/drivers/md/persistent-data/dm-btree-remove.c
index aeec5b9a1dd5..7e0560f71729 100644
--- a/drivers/md/persistent-data/dm-btree-remove.c
+++ b/drivers/md/persistent-data/dm-btree-remove.c
@@ -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;
diff --git a/drivers/md/persistent-data/dm-btree.c b/drivers/md/persistent-data/dm-btree.c
index dd02eee4a23c..3004537c75a1 100644
--- a/drivers/md/persistent-data/dm-btree.c
+++ b/drivers/md/persistent-data/dm-btree.c
@@ -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;
diff --git a/drivers/md/persistent-data/dm-btree.h b/drivers/md/persistent-data/dm-btree.h
index 1b92acd7823d..617d808ca8dd 100644
--- a/drivers/md/persistent-data/dm-btree.h
+++ b/drivers/md/persistent-data/dm-btree.h
@@ -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
-- 
2.34.1
lmpx.com only provides a reader for public news (NNTP) servers. It is not affiliated with the servers or forums shown here and is not responsible for the content of articles, which is written by their respective authors.