[PATCH] btrfs: bound free space runs by extent count in remap tree setup

[PATCH] btrfs: bound free space runs by extent count in remap tree setup

[Xingyuan Mo]

create_remap_tree_entries() sizes the space_runs array with the extent
count read from the FREE_SPACE_INFO item of the block group, then fills
it while walking the free space tree.  Nothing on this path cross-checks
that count against the items that follow, and the only guards in the
walk are two ASSERTs, compiled out unless CONFIG_BTRFS_ASSERT is set:
the FREE_SPACE_BITMAP branch hands the array to parse_bitmap(), which
appends one struct space_run per run of set bits without any bound at
all.

A crafted (or corrupted) filesystem that advertises a smaller extent
count than the number of runs its free space items describe therefore
gets a heap out-of-bounds write with disk-controlled contents during
relocation, e.g. through BTRFS_IOC_BALANCE.  The free space tree load
path validates the same count when it caches a block group, but that
check runs lazily and only leaves the block group in
BTRFS_CACHE_ERROR, which does not stop the remap path from re-reading
and trusting the item.

Bound the writes by the extent count: make parse_bitmap() take the
array size and return -EUCLEAN when a bitmap would overflow it, and
replace the ASSERT in the FREE_SPACE_EXTENT branch with the same
check.  This also covers an extent count of 0 (ZERO_SIZE_PTR) and
keeps the downstream entries array, sized extent_count + 2 and filled
with at most num_space_runs + 1 entries, within bounds.  Consistent
filesystems are unaffected, as merging adjacent runs can only shrink
the number of runs below the recorded extent count.

Validated with a crafted image on a KASAN kernel: an info item
claiming one extent next to a bitmap encoding 40 runs makes an
unpatched kernel write up to 624 bytes past the 16-byte allocation in
parse_bitmap() during balance:

  BUG: KASAN: slab-out-of-bounds in btrfs_relocate_block_group+0x2a46/0x3600
  Write of size 8 at addr ffff88800c992550 by task balance/278
  __asan_store8+0x85/0xb0
  btrfs_relocate_block_group+0x2a46/0x3600
  btrfs_relocate_chunk+0x82/0x320
  btrfs_balance+0x1071/0x2e30
  btrfs_ioctl+0x2943/0x3c60
  __x64_sys_ioctl+0xd1/0x120
  The buggy address is located 0 bytes to the right of
  allocated 16-byte region [ffff88800c992540, ffff88800c992550)

with create_remap_tree_entries() and parse_bitmap() inlined into
btrfs_relocate_block_group, while with this patch the same image fails
balance with -EUCLEAN and an image with a matching count still
relocates cleanly.

Fixes: b56f35560b82 ("btrfs: handle setting up relocation of block group with remap-tree")
Signed-off-by: Xingyuan Mo <hdthky0@gmail.com>
---
 fs/btrfs/relocation.c | 34 ++++++++++++++++++++++------------
 1 file changed, 22 insertions(+), 12 deletions(-)

diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index b2ac5b836b217..d57522cc7f386 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -4013,16 +4013,16 @@ struct space_run {
 	u64 end;
 };
 
-static void parse_bitmap(u64 block_size, const unsigned long *bitmap,
-			 unsigned long size, u64 address, struct space_run *space_runs,
-			 unsigned int *num_space_runs)
+static int parse_bitmap(u64 block_size, const unsigned long *bitmap,
+			unsigned long size, u64 address, struct space_run *space_runs,
+			unsigned int *num_space_runs, u32 max_space_runs)
 {
 	unsigned long pos, end;
 	u64 run_start, run_length;
 
 	pos = find_first_bit(bitmap, size);
 	if (pos == size)
-		return;
+		return 0;
 
 	while (true) {
 		end = find_next_zero_bit(bitmap, size, pos);
@@ -4034,6 +4034,9 @@ static void parse_bitmap(u64 block_size, const unsigned long *bitmap,
 		    space_runs[*num_space_runs - 1].end == run_start) {
 			space_runs[*num_space_runs - 1].end += run_length;
 		} else {
+			if (*num_space_runs >= max_space_runs)
+				return -EUCLEAN;
+
 			space_runs[*num_space_runs].start = run_start;
 			space_runs[*num_space_runs].end = run_start + run_length;
 
@@ -4047,6 +4050,8 @@ static void parse_bitmap(u64 block_size, const unsigned long *bitmap,
 		if (pos == size)
 			break;
 	}
+
+	return 0;
 }
 
 static void adjust_block_group_remap_bytes(struct btrfs_trans_handle *trans,
@@ -4608,7 +4613,11 @@ static int create_remap_tree_entries(struct btrfs_trans_handle *trans,
 				space_runs[num_space_runs - 1].end =
 					found_key.objectid + found_key.offset;
 			} else {
-				ASSERT(num_space_runs < extent_count);
+				if (num_space_runs >= extent_count) {
+					mutex_unlock(&bg->free_space_lock);
+					ret = -EUCLEAN;
+					goto out;
+				}
 
 				space_runs[num_space_runs].start = found_key.objectid;
 				space_runs[num_space_runs].end =
@@ -4634,14 +4643,15 @@ static int create_remap_tree_entries(struct btrfs_trans_handle *trans,
 
 				read_extent_buffer(leaf, bitmap, offset, data_size);
 
-				parse_bitmap(fs_info->sectorsize, bitmap,
-					     data_size * BITS_PER_BYTE,
-					     found_key.objectid, space_runs,
-					     &num_space_runs);
-
-				ASSERT(num_space_runs <= extent_count);
-
+				ret = parse_bitmap(fs_info->sectorsize, bitmap,
+						   data_size * BITS_PER_BYTE,
+						   found_key.objectid, space_runs,
+						   &num_space_runs, extent_count);
 				kfree(bitmap);
+				if (ret) {
+					mutex_unlock(&bg->free_space_lock);
+					goto out;
+				}
 			}
 		}
 
-- 
2.43.0