On 2019/6/3 下午6:06, Nikolay Borisov wrote:
> Currently find_first_clear_extent_bit always returns a range whose
> starting value is >= passed 'start'. This implicit trimming behavior is
> somewhat subtle and an implementation detail. Instead, this patch
> modifies the function such that now it always returns the range which
> contains passed 'start' and has the given bits unset. This range could
> either be due to presence of existing records which contains 'start'
> but have the bits unset or because there are no records that contain
> the given starting offset.
>
> This patch also adds test cases which cover find_first_clear_extent_bit
> since they were missing up until now.
>
> Signed-off-by: Nikolay Borisov <nborisov@xxxxxxxx>
> ---
> fs/btrfs/extent_io.c | 51 +++++++++++++++---
> fs/btrfs/tests/extent-io-tests.c | 89 ++++++++++++++++++++++++++++++++
> 2 files changed, 134 insertions(+), 6 deletions(-)
>
> diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
> index d5979558c96f..1dd900cfb7ea 100644
> --- a/fs/btrfs/extent_io.c
> +++ b/fs/btrfs/extent_io.c
> @@ -1553,8 +1553,8 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
> }
>
> /**
> - * find_first_clear_extent_bit - finds the first range that has @bits not set
> - * and that starts after @start
> + * find_first_clear_extent_bit - finds the first range that has @bits not set.
> + * This range could start before @start.
What about using the same expression of previous patches? E.g.
Such range would have range->start <= start && range->start +
range->len > start.
Despite that, I think the ascii chart is pretty good, along with
selftest case it should be OK.
Reviewed-by: Qu Wenruo <wqu@xxxxxxxx>
Thanks,
Qu
> *
> * @tree - the tree to search
> * @start - the offset at/after which the found extent should start
> @@ -1594,12 +1594,51 @@ void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,
> goto out;
> }
> }
> + /*
> + * At this point 'node' either contains 'start' or start is
> + * before 'node'
> + */
> state = rb_entry(node, struct extent_state, rb_node);
> - if (in_range(start, state->start, state->end - state->start + 1) &&
> - (state->state & bits)) {
> - start = state->end + 1;
> +
> + if (in_range(start, state->start, state->end - state->start + 1)) {
> + if (state->state & bits) {
> + /*
> + * |--range with bits sets--|
> + * |
> + * start
> + */
> + start = state->end + 1;
> + } else {
> + /*
> + * 'start' falls within a range that doesn't
> + * have the bits set, so take its start as
> + * the beginning of the desire range
> + *
> + * |--range with bits cleared----|
> + * |
> + * start
> + */
> + *start_ret = state->start;
> + break;
> + }
> } else {
> - *start_ret = start;
> + /*
> + * |---prev range---|---hole/unset---|---node range---|
> + * |
> + * start
> + *
> + * or
> + *
> + * |---hole/unset--||--first node--|
> + * 0 |
> + * start
> + */
> + if (prev) {
> + state = rb_entry(prev, struct extent_state, rb_node);
> + *start_ret = state->end + 1;
> + } else {
> + *start_ret = 0;
> + }
> break;
> }
> }
> diff --git a/fs/btrfs/tests/extent-io-tests.c b/fs/btrfs/tests/extent-io-tests.c
> index 7bf4d5734dbe..36fe720fc823 100644
> --- a/fs/btrfs/tests/extent-io-tests.c
> +++ b/fs/btrfs/tests/extent-io-tests.c
> @@ -432,6 +432,91 @@ static int test_eb_bitmaps(u32 sectorsize, u32 nodesize)
> return ret;
> }
>
> +static int test_find_first_clear_extent_bit(void)
> +{
> +
> + struct extent_io_tree tree;
> + u64 start, end;
> +
> + test_msg("Running find_first_clear_extent_bit test");
> + extent_io_tree_init(NULL, &tree, IO_TREE_SELFTEST, NULL);
> +
> + /*
> + * Set 1m-4m alloc/discard and 32m-64m thus leaving a hole
> + * between 4m-32m
> + */
> + set_extent_bits(&tree, SZ_1M, SZ_4M - 1,
> + CHUNK_TRIMMED | CHUNK_ALLOCATED);
> +
> +
> + find_first_clear_extent_bit(&tree, SZ_512K, &start, &end,
> + CHUNK_TRIMMED | CHUNK_ALLOCATED);
> +
> + if (start != 0 || end != SZ_1M -1)
> + test_err("Error finding beginning range: start: %llu end: %llu\n",
> + start, end);
> +
> + /* Now add 32m-64m so that we have a hole between 4m-32m */
> + set_extent_bits(&tree, SZ_32M, SZ_64M - 1,
> + CHUNK_TRIMMED | CHUNK_ALLOCATED);
> +
> + /*
> + * Request first hole starting at 12m, we should get 4m-32m
> + */
> + find_first_clear_extent_bit(&tree, 12 * SZ_1M, &start, &end,
> + CHUNK_TRIMMED | CHUNK_ALLOCATED);
> +
> + if (start != SZ_4M || end != SZ_32M - 1)
> + test_err("Error finding trimmed range: start: %llu end: %llu",
> + start, end);
> +
> + /*
> + * Search in the middle of allocated range, should get next available,
> + * which happens to be unallocated -> 4m-32m
> + */
> + find_first_clear_extent_bit(&tree, SZ_2M, &start, &end,
> + CHUNK_TRIMMED | CHUNK_ALLOCATED);
> +
> + if (start != SZ_4M || end != SZ_32M -1)
> + test_err("Error finding next unalloc range: start: %llu end: %llu",
> + start, end);
> +
> + /*
> + * Set 64M-72M with CHUNK_ALLOC flag, then search for CHUNK_TRIMMED flag
> + * being unset in this range, we should get the entry in range 64m-72M
> + */
> + set_extent_bits(&tree, SZ_64M, SZ_64M + SZ_8M - 1, CHUNK_ALLOCATED);
> + find_first_clear_extent_bit(&tree, SZ_64M + SZ_1M, &start, &end,
> + CHUNK_TRIMMED);
> +
> + if (start != SZ_64M || end != SZ_64M + SZ_8M - 1)
> + test_err("Error finding exact range: start: %llu end: %llu",
> + start, end);
> +
> + find_first_clear_extent_bit(&tree, SZ_64M - SZ_8M, &start, &end,
> + CHUNK_TRIMMED);
> +
> + /*
> + * Search in the middle of set range whose immediate neighbour doesn't
> + * have the bits set so it must be returned
> + */
> + if (start != SZ_64M || end != SZ_64M + SZ_8M - 1)
> + test_err("Error finding next alloc range: start: %llu end: %llu",
> + start, end);
> +
> + /*
> + * Search beyond any known range, shall return after last known range
> + * and end should be -1
> + */
> + find_first_clear_extent_bit(&tree, -1, &start, &end, CHUNK_TRIMMED);
> + if (start != SZ_64M+SZ_8M || end != -1)
> + test_err("Error handling beyond end of range search: start: %llu"
> + " end: %llu\n", start, end);
> +
> + return 0;
> +
> +}
> +
> int btrfs_test_extent_io(u32 sectorsize, u32 nodesize)
> {
> int ret;
> @@ -442,6 +527,10 @@ int btrfs_test_extent_io(u32 sectorsize, u32 nodesize)
> if (ret)
> goto out;
>
> + ret = test_find_first_clear_extent_bit();
> + if (ret)
> + goto out;
> +
> ret = test_eb_bitmaps(sectorsize, nodesize);
> out:
> return ret;
>
