From 5341c98450df7cf8dacc907a80e3362f3155c847 Mon Sep 17 00:00:00 2001 From: Boris Burkov Date: Thu, 29 Jan 2026 16:11:22 -0800 Subject: [PATCH] btrfs: tests: add unit tests for pending extent walking functions I ran into another sort of trivial bug in v1 of the patch and concluded that these functions really ought to be unit tested. These two functions form the core of searching the chunk allocation pending extent bitmap and have relatively easily definable semantics, so unit testing them can help ensure the correctness of chunk allocation. I also made a minor unrelated fix in volumes.h to properly forward declare btrfs_space_info. Because of the order of the includes in the new test, this was actually hitting a latent build warning. Note: This is an early example for me of a commit authored in part by an AI agent, so I wanted to more clear about what I did. I defined a trivial test and explained the set of tests I wanted to the agent and it produced the large set of test cases seen here. I then checked each test case to make sure it matched the description and simplified the constants and numbers until they looked reasonable to me. I then checked the looping logic to make sure it made sense to the original spirit of the trivial test. Finally, carefully combed over all the lines it wrote to loop over the tests it generated to make sure they followed our code style guide. Assisted-by: Claude:claude-opus-4-5 Signed-off-by: Boris Burkov Signed-off-by: David Sterba --- fs/btrfs/Makefile | 3 +- fs/btrfs/tests/btrfs-tests.c | 3 + fs/btrfs/tests/btrfs-tests.h | 1 + fs/btrfs/tests/chunk-allocation-tests.c | 476 ++++++++++++++++++++++++ fs/btrfs/volumes.c | 14 +- fs/btrfs/volumes.h | 6 + 6 files changed, 495 insertions(+), 8 deletions(-) create mode 100644 fs/btrfs/tests/chunk-allocation-tests.c diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile index 743d7677b175d..975104b744869 100644 --- a/fs/btrfs/Makefile +++ b/fs/btrfs/Makefile @@ -44,4 +44,5 @@ btrfs-$(CONFIG_BTRFS_FS_RUN_SANITY_TESTS) += tests/free-space-tests.o \ tests/extent-buffer-tests.o tests/btrfs-tests.o \ tests/extent-io-tests.o tests/inode-tests.o tests/qgroup-tests.o \ tests/free-space-tree-tests.o tests/extent-map-tests.o \ - tests/raid-stripe-tree-tests.o tests/delayed-refs-tests.o + tests/raid-stripe-tree-tests.o tests/delayed-refs-tests.o \ + tests/chunk-allocation-tests.o diff --git a/fs/btrfs/tests/btrfs-tests.c b/fs/btrfs/tests/btrfs-tests.c index b576897d71cc4..7f13c05d37366 100644 --- a/fs/btrfs/tests/btrfs-tests.c +++ b/fs/btrfs/tests/btrfs-tests.c @@ -301,6 +301,9 @@ int btrfs_run_sanity_tests(void) ret = btrfs_test_delayed_refs(sectorsize, nodesize); if (ret) goto out; + ret = btrfs_test_chunk_allocation(sectorsize, nodesize); + if (ret) + goto out; } } ret = btrfs_test_extent_map(); diff --git a/fs/btrfs/tests/btrfs-tests.h b/fs/btrfs/tests/btrfs-tests.h index 4307bdaa67497..b0e4b98bdc3d9 100644 --- a/fs/btrfs/tests/btrfs-tests.h +++ b/fs/btrfs/tests/btrfs-tests.h @@ -45,6 +45,7 @@ int btrfs_test_free_space_tree(u32 sectorsize, u32 nodesize); int btrfs_test_raid_stripe_tree(u32 sectorsize, u32 nodesize); int btrfs_test_extent_map(void); int btrfs_test_delayed_refs(u32 sectorsize, u32 nodesize); +int btrfs_test_chunk_allocation(u32 sectorsize, u32 nodesize); struct inode *btrfs_new_test_inode(void); struct btrfs_fs_info *btrfs_alloc_dummy_fs_info(u32 nodesize, u32 sectorsize); void btrfs_free_dummy_fs_info(struct btrfs_fs_info *fs_info); diff --git a/fs/btrfs/tests/chunk-allocation-tests.c b/fs/btrfs/tests/chunk-allocation-tests.c new file mode 100644 index 0000000000000..9beb0602fc8cc --- /dev/null +++ b/fs/btrfs/tests/chunk-allocation-tests.c @@ -0,0 +1,476 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (C) 2026 Meta. All rights reserved. + */ + +#include +#include "btrfs-tests.h" +#include "../volumes.h" +#include "../disk-io.h" +#include "../extent-io-tree.h" + +/* + * Tests for chunk allocator pending extent internals. + * These two functions form the core of searching the chunk allocation pending + * extent bitmap and have relatively easily definable semantics, so unit + * testing them can help ensure the correctness of chunk allocation. + */ + +/* + * Describes the inputs to the system and expected results + * when testing btrfs_find_hole_in_pending_extents(). + */ +struct pending_extent_test_case { + const char *name; + /* Input range to search. */ + u64 hole_start; + u64 hole_len; + /* The size of hole we are searching for. */ + u64 min_hole_size; + /* + * Pending extents to set up (up to 2 for up to 3 holes) + * If len == 0, then it is skipped. + */ + struct { + u64 start; + u64 len; + } pending_extents[2]; + /* Expected outputs. */ + bool expected_found; + u64 expected_start; + u64 expected_len; +}; + +static const struct pending_extent_test_case find_hole_tests[] = { + { + .name = "no pending extents", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .min_hole_size = SZ_1G, + .pending_extents = { }, + .expected_found = true, + .expected_start = 0, + .expected_len = 10ULL * SZ_1G, + }, + { + .name = "pending extent at start of range", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .min_hole_size = SZ_1G, + .pending_extents = { + { .start = 0, .len = SZ_1G }, + }, + .expected_found = true, + .expected_start = SZ_1G, + .expected_len = 9ULL * SZ_1G, + }, + { + .name = "pending extent overlapping start of range", + .hole_start = SZ_1G, + .hole_len = 9ULL * SZ_1G, + .min_hole_size = SZ_1G, + .pending_extents = { + { .start = 0, .len = SZ_2G }, + }, + .expected_found = true, + .expected_start = SZ_2G, + .expected_len = 8ULL * SZ_1G, + }, + { + .name = "two holes; first hole is exactly big enough", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .min_hole_size = SZ_1G, + .pending_extents = { + { .start = SZ_1G, .len = SZ_1G }, + }, + .expected_found = true, + .expected_start = 0, + .expected_len = SZ_1G, + }, + { + .name = "two holes; first hole is big enough", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .min_hole_size = SZ_1G, + .pending_extents = { + { .start = SZ_2G, .len = SZ_1G }, + }, + .expected_found = true, + .expected_start = 0, + .expected_len = SZ_2G, + }, + { + .name = "two holes; second hole is big enough", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .min_hole_size = SZ_2G, + .pending_extents = { + { .start = SZ_1G, .len = SZ_1G }, + }, + .expected_found = true, + .expected_start = SZ_2G, + .expected_len = 8ULL * SZ_1G, + }, + { + .name = "three holes; first hole big enough", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .min_hole_size = SZ_2G, + .pending_extents = { + { .start = SZ_2G, .len = SZ_1G }, + { .start = 4ULL * SZ_1G, .len = SZ_1G }, + }, + .expected_found = true, + .expected_start = 0, + .expected_len = SZ_2G, + }, + { + .name = "three holes; second hole big enough", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .min_hole_size = SZ_2G, + .pending_extents = { + { .start = SZ_1G, .len = SZ_1G }, + { .start = 5ULL * SZ_1G, .len = SZ_1G }, + }, + .expected_found = true, + .expected_start = SZ_2G, + .expected_len = 3ULL * SZ_1G, + }, + { + .name = "three holes; third hole big enough", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .min_hole_size = SZ_2G, + .pending_extents = { + { .start = SZ_1G, .len = SZ_1G }, + { .start = 3ULL * SZ_1G, .len = 5ULL * SZ_1G }, + }, + .expected_found = true, + .expected_start = 8ULL * SZ_1G, + .expected_len = SZ_2G, + }, + { + .name = "three holes; all holes too small", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .min_hole_size = SZ_2G, + .pending_extents = { + { .start = SZ_1G, .len = SZ_1G }, + { .start = 3ULL * SZ_1G, .len = 6ULL * SZ_1G }, + }, + .expected_found = false, + .expected_start = 0, + .expected_len = SZ_1G, + }, + { + .name = "three holes; all holes too small; first biggest", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .min_hole_size = 3ULL * SZ_1G, + .pending_extents = { + { .start = SZ_2G, .len = SZ_1G }, + { .start = 4ULL * SZ_1G, .len = 5ULL * SZ_1G }, + }, + .expected_found = false, + .expected_start = 0, + .expected_len = SZ_2G, + }, + { + .name = "three holes; all holes too small; second biggest", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .min_hole_size = 3ULL * SZ_1G, + .pending_extents = { + { .start = SZ_1G, .len = SZ_1G }, + { .start = 4ULL * SZ_1G, .len = 5ULL * SZ_1G }, + }, + .expected_found = false, + .expected_start = SZ_2G, + .expected_len = SZ_2G, + }, + { + .name = "three holes; all holes too small; third biggest", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .min_hole_size = 3ULL * SZ_1G, + .pending_extents = { + { .start = SZ_1G, .len = SZ_1G }, + { .start = 3ULL * SZ_1G, .len = 5ULL * SZ_1G }, + }, + .expected_found = false, + .expected_start = 8ULL * SZ_1G, + .expected_len = SZ_2G, + }, + { + .name = "hole entirely allocated by pending", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .min_hole_size = SZ_1G, + .pending_extents = { + { .start = 0, .len = 10ULL * SZ_1G }, + }, + .expected_found = false, + .expected_start = 10ULL * SZ_1G, + .expected_len = 0, + }, + { + .name = "pending extent at end of range", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .min_hole_size = SZ_1G, + .pending_extents = { + { .start = 9ULL * SZ_1G, .len = SZ_2G }, + }, + .expected_found = true, + .expected_start = 0, + .expected_len = 9ULL * SZ_1G, + }, + { + .name = "zero length input", + .hole_start = SZ_1G, + .hole_len = 0, + .min_hole_size = SZ_1G, + .pending_extents = { }, + .expected_found = false, + .expected_start = SZ_1G, + .expected_len = 0, + }, +}; + +static int test_find_hole_in_pending(u32 sectorsize, u32 nodesize) +{ + struct btrfs_fs_info *fs_info; + struct btrfs_device *device; + int ret = 0; + + test_msg("running find_hole_in_pending_extents tests"); + + fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize); + if (!fs_info) { + test_std_err(TEST_ALLOC_FS_INFO); + return -ENOMEM; + } + + device = btrfs_alloc_dummy_device(fs_info); + if (IS_ERR(device)) { + test_err("failed to allocate dummy device"); + ret = PTR_ERR(device); + goto out_free_fs_info; + } + device->fs_info = fs_info; + + for (int i = 0; i < ARRAY_SIZE(find_hole_tests); i++) { + const struct pending_extent_test_case *test_case = &find_hole_tests[i]; + u64 hole_start = test_case->hole_start; + u64 hole_len = test_case->hole_len; + bool found; + + for (int j = 0; j < ARRAY_SIZE(test_case->pending_extents); j++) { + u64 start = test_case->pending_extents[j].start; + u64 len = test_case->pending_extents[j].len; + + if (!len) + continue; + btrfs_set_extent_bit(&device->alloc_state, + start, start + len - 1, + CHUNK_ALLOCATED, NULL); + } + + mutex_lock(&fs_info->chunk_mutex); + found = btrfs_find_hole_in_pending_extents(device, &hole_start, &hole_len, + test_case->min_hole_size); + mutex_unlock(&fs_info->chunk_mutex); + + if (found != test_case->expected_found) { + test_err("%s: expected found=%d, got found=%d", + test_case->name, test_case->expected_found, found); + ret = -EINVAL; + goto out_clear_pending_extents; + } + if (hole_start != test_case->expected_start || + hole_len != test_case->expected_len) { + test_err("%s: expected [%llu, %llu), got [%llu, %llu)", + test_case->name, test_case->expected_start, + test_case->expected_start + + test_case->expected_len, + hole_start, hole_start + hole_len); + ret = -EINVAL; + goto out_clear_pending_extents; + } +out_clear_pending_extents: + btrfs_clear_extent_bit(&device->alloc_state, 0, (u64)-1, + CHUNK_ALLOCATED, NULL); + if (ret) + break; + } + +out_free_fs_info: + btrfs_free_dummy_fs_info(fs_info); + return ret; +} + +/* + * Describes the inputs to the system and expected results + * when testing btrfs_first_pending_extent(). + */ +struct first_pending_test_case { + const char *name; + /* The range to look for a pending extent in. */ + u64 hole_start; + u64 hole_len; + /* The pending extent to look for. */ + struct { + u64 start; + u64 len; + } pending_extent; + /* Expected outputs. */ + bool expected_found; + u64 expected_pending_start; + u64 expected_pending_end; +}; + +static const struct first_pending_test_case first_pending_tests[] = { + { + .name = "no pending extent", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .pending_extent = { 0, 0 }, + .expected_found = false, + }, + { + .name = "pending extent at search start", + .hole_start = SZ_1G, + .hole_len = 9ULL * SZ_1G, + .pending_extent = { SZ_1G, SZ_1G }, + .expected_found = true, + .expected_pending_start = SZ_1G, + .expected_pending_end = SZ_2G - 1, + }, + { + .name = "pending extent overlapping search start", + .hole_start = SZ_1G, + .hole_len = 9ULL * SZ_1G, + .pending_extent = { 0, SZ_2G }, + .expected_found = true, + .expected_pending_start = 0, + .expected_pending_end = SZ_2G - 1, + }, + { + .name = "pending extent inside search range", + .hole_start = 0, + .hole_len = 10ULL * SZ_1G, + .pending_extent = { SZ_2G, SZ_1G }, + .expected_found = true, + .expected_pending_start = SZ_2G, + .expected_pending_end = 3ULL * SZ_1G - 1, + }, + { + .name = "pending extent outside search range", + .hole_start = 0, + .hole_len = SZ_1G, + .pending_extent = { SZ_2G, SZ_1G }, + .expected_found = false, + }, + { + .name = "pending extent overlapping end of search range", + .hole_start = 0, + .hole_len = SZ_2G, + .pending_extent = { SZ_1G, SZ_2G }, + .expected_found = true, + .expected_pending_start = SZ_1G, + .expected_pending_end = 3ULL * SZ_1G - 1, + }, +}; + +static int test_first_pending_extent(u32 sectorsize, u32 nodesize) +{ + struct btrfs_fs_info *fs_info; + struct btrfs_device *device; + int ret = 0; + + test_msg("running first_pending_extent tests"); + + fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize); + if (!fs_info) { + test_std_err(TEST_ALLOC_FS_INFO); + return -ENOMEM; + } + + device = btrfs_alloc_dummy_device(fs_info); + if (IS_ERR(device)) { + test_err("failed to allocate dummy device"); + ret = PTR_ERR(device); + goto out_free_fs_info; + } + + device->fs_info = fs_info; + + for (int i = 0; i < ARRAY_SIZE(first_pending_tests); i++) { + const struct first_pending_test_case *test_case = &first_pending_tests[i]; + u64 start = test_case->pending_extent.start; + u64 len = test_case->pending_extent.len; + u64 pending_start, pending_end; + bool found; + + if (len) { + btrfs_set_extent_bit(&device->alloc_state, + start, start + len - 1, + CHUNK_ALLOCATED, NULL); + } + + mutex_lock(&fs_info->chunk_mutex); + found = btrfs_first_pending_extent(device, test_case->hole_start, + test_case->hole_len, + &pending_start, &pending_end); + mutex_unlock(&fs_info->chunk_mutex); + + if (found != test_case->expected_found) { + test_err("%s: expected found=%d, got found=%d", + test_case->name, test_case->expected_found, found); + ret = -EINVAL; + goto out_clear_pending_extents; + } + if (!found) + goto out_clear_pending_extents; + + if (pending_start != test_case->expected_pending_start || + pending_end != test_case->expected_pending_end) { + test_err("%s: expected pending [%llu, %llu], got [%llu, %llu]", + test_case->name, + test_case->expected_pending_start, + test_case->expected_pending_end, + pending_start, pending_end); + ret = -EINVAL; + goto out_clear_pending_extents; + } + +out_clear_pending_extents: + btrfs_clear_extent_bit(&device->alloc_state, 0, (u64)-1, + CHUNK_ALLOCATED, NULL); + if (ret) + break; + } + +out_free_fs_info: + btrfs_free_dummy_fs_info(fs_info); + return ret; +} + +int btrfs_test_chunk_allocation(u32 sectorsize, u32 nodesize) +{ + int ret; + + test_msg("running chunk allocation tests"); + + ret = test_first_pending_extent(sectorsize, nodesize); + if (ret) + return ret; + + ret = test_find_hole_in_pending(sectorsize, nodesize); + if (ret) + return ret; + + return 0; +} diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c index 329a922893b4f..f281d113519b9 100644 --- a/fs/btrfs/volumes.c +++ b/fs/btrfs/volumes.c @@ -1526,8 +1526,8 @@ error_bdev_put: * may still be modified, to something outside the range and should not * be used. */ -static bool first_pending_extent(struct btrfs_device *device, u64 start, u64 len, - u64 *pending_start, u64 *pending_end) +bool btrfs_first_pending_extent(struct btrfs_device *device, u64 start, u64 len, + u64 *pending_start, u64 *pending_end) { lockdep_assert_held(&device->fs_info->chunk_mutex); @@ -1566,8 +1566,8 @@ static bool first_pending_extent(struct btrfs_device *device, u64 start, u64 len * If there are no holes at all, then *start is set to the end of the range and * *len is set to 0. */ -static bool find_hole_in_pending_extents(struct btrfs_device *device, u64 *start, - u64 *len, u64 min_hole_size) +bool btrfs_find_hole_in_pending_extents(struct btrfs_device *device, u64 *start, + u64 *len, u64 min_hole_size) { u64 pending_start, pending_end; u64 end; @@ -1588,7 +1588,7 @@ static bool find_hole_in_pending_extents(struct btrfs_device *device, u64 *start * At the end of the iteration, set the output variables to the max hole. */ while (true) { - if (first_pending_extent(device, *start, *len, &pending_start, &pending_end)) { + if (btrfs_first_pending_extent(device, *start, *len, &pending_start, &pending_end)) { /* * Case 1: the pending extent overlaps the start of * candidate hole. That means the true hole is after the @@ -1758,7 +1758,7 @@ static bool dev_extent_hole_check(struct btrfs_device *device, u64 *hole_start, again: *hole_size = hole_end - *hole_start + 1; - found = find_hole_in_pending_extents(device, hole_start, hole_size, num_bytes); + found = btrfs_find_hole_in_pending_extents(device, hole_start, hole_size, num_bytes); if (!found) return found; ASSERT(*hole_size >= num_bytes); @@ -5190,7 +5190,7 @@ int btrfs_shrink_device(struct btrfs_device *device, u64 new_size) * in-memory chunks are synced to disk so that the loop below sees them * and relocates them accordingly. */ - if (first_pending_extent(device, start, diff, &pending_start, &pending_end)) { + if (btrfs_first_pending_extent(device, start, diff, &pending_start, &pending_end)) { mutex_unlock(&fs_info->chunk_mutex); ret = btrfs_commit_transaction(trans); if (ret) diff --git a/fs/btrfs/volumes.h b/fs/btrfs/volumes.h index e4644352314ad..ebc85bf53ee7e 100644 --- a/fs/btrfs/volumes.h +++ b/fs/btrfs/volumes.h @@ -30,6 +30,7 @@ struct btrfs_block_group; struct btrfs_trans_handle; struct btrfs_transaction; struct btrfs_zoned_device_info; +struct btrfs_space_info; #define BTRFS_MAX_DATA_CHUNK_SIZE (10ULL * SZ_1G) @@ -892,6 +893,11 @@ const u8 *btrfs_sb_fsid_ptr(const struct btrfs_super_block *sb); int btrfs_update_device(struct btrfs_trans_handle *trans, struct btrfs_device *device); void btrfs_chunk_map_device_clear_bits(struct btrfs_chunk_map *map, unsigned int bits); +bool btrfs_first_pending_extent(struct btrfs_device *device, u64 start, u64 len, + u64 *pending_start, u64 *pending_end); +bool btrfs_find_hole_in_pending_extents(struct btrfs_device *device, + u64 *start, u64 *len, u64 min_hole_size); + #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS struct btrfs_io_context *alloc_btrfs_io_context(struct btrfs_fs_info *fs_info, u64 logical, u16 total_stripes); -- 2.47.3