| Message ID | 20190130145102.4708-15-nborisov@suse.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | Improvements to fitrim | expand |
On 30/01/2019 15:51, Nikolay Borisov wrote: [...] > > +/* find_first_clear_extent_bit - finds the first range that has @bits not set > + * and that starts after @start > + * NIT: Shouldn't kerneldoc comments start with a /** and a newline afterwards?
On 30.01.19 г. 16:51 ч., Nikolay Borisov wrote: > This function is very similar to find_first_extent_bit except that it > locates the first contiguous span of space which does not have bits set. > It's intended use is in the freespace trimming code. > > Signed-off-by: Nikolay Borisov <nborisov@suse.com> > --- > fs/btrfs/extent_io.c | 78 ++++++++++++++++++++++++++++++++++++++++++++ > fs/btrfs/extent_io.h | 2 ++ > 2 files changed, 80 insertions(+) > > diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c > index d5525d18803d..542eaab9c0c1 100644 > --- a/fs/btrfs/extent_io.c > +++ b/fs/btrfs/extent_io.c > @@ -1474,6 +1474,84 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start, > return ret; > } > > +/* find_first_clear_extent_bit - finds the first range that has @bits not set > + * and that starts after @start > + * > + * @tree - the tree to search > + * @start - the offset at/after which the found extent should start > + * @start_ret - records the beginning of the range > + * @end_ret - records the end of the range (inclusive) > + * @bits - the set of bits which must be unset > + * > + * Returns 0 when a range is found and @start_ret/@end_ret are initialised > + * accordingly, 1 otherwise. Since unallocated range is also considered one > + * which doesn't have the bits set it's possible that @end_ret contains -1, this > + * happens in case the range spans (last_range_end, end of device]. In this case > + * it's up to the caller to trim @end_ret to the appropriate size. > + */ > +int find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start, > + u64 *start_ret, u64 *end_ret, unsigned bits) > +{ > + struct extent_state *state; > + struct rb_node *node, *prev = NULL, *next; > + int ret = 1; > + > + spin_lock(&tree->lock); > + > + /* Find first extent with bits cleared */ > + while (1) { > + node = __etree_search(tree, start, &next, &prev, NULL, NULL); > + if (!node) { > + node = next; > + if (!node) { > + /* > + * We are past the last allocated chunk, > + * set start at the end of the last extent. The > + * device alloc tree should never be empty so > + * prev is always set. > + */ > + ASSERT(prev); > + state = rb_entry(prev, struct extent_state, rb_node); > + *start_ret = state->end + 1; > + *end_ret = -1; > + ret = 0; > + goto out; Bummer this is not working as expected. For example, for a fs which doesn't have any holes it will return 0 but in fact it should return 1 and terminate the search. Have to figure how to distinguish between "everything after last extent until -1 is not allocated" VS "there is no extent which satisfies the condition so just return 1/failure" > + } > + } > + 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; > + } else { > + *start_ret = start; > + break; > + } > + } > + > + /* > + * Find the longest stretch from start until an entry which has the > + * bits set > + */ > + while (1) { > + state = rb_entry(node, struct extent_state, rb_node); > + if (state->end >= start && !(state->state & bits)) { > + *end_ret = state->end; > + ret = 0; > + } else { > + *end_ret = state->start - 1; > + ret = 0; > + break; > + } > + > + node = rb_next(node); > + if (!node) > + break; > + } > +out: > + spin_unlock(&tree->lock); > + return ret; > +} > + > /* > * find a contiguous range of bytes in the file marked as delalloc, not > * more than 'max_bytes'. start and end are used to return the range, > diff --git a/fs/btrfs/extent_io.h b/fs/btrfs/extent_io.h > index d238efd628cf..7ddb3ec70023 100644 > --- a/fs/btrfs/extent_io.h > +++ b/fs/btrfs/extent_io.h > @@ -391,6 +391,8 @@ static inline int set_extent_uptodate(struct extent_io_tree *tree, u64 start, > int find_first_extent_bit(struct extent_io_tree *tree, u64 start, > u64 *start_ret, u64 *end_ret, unsigned bits, > struct extent_state **cached_state); > +int find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start, > + u64 *start_ret, u64 *end_ret, unsigned bits); > int extent_invalidatepage(struct extent_io_tree *tree, > struct page *page, unsigned long offset); > int extent_write_full_page(struct page *page, struct writeback_control *wbc); >
diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c index d5525d18803d..542eaab9c0c1 100644 --- a/fs/btrfs/extent_io.c +++ b/fs/btrfs/extent_io.c @@ -1474,6 +1474,84 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start, return ret; } +/* find_first_clear_extent_bit - finds the first range that has @bits not set + * and that starts after @start + * + * @tree - the tree to search + * @start - the offset at/after which the found extent should start + * @start_ret - records the beginning of the range + * @end_ret - records the end of the range (inclusive) + * @bits - the set of bits which must be unset + * + * Returns 0 when a range is found and @start_ret/@end_ret are initialised + * accordingly, 1 otherwise. Since unallocated range is also considered one + * which doesn't have the bits set it's possible that @end_ret contains -1, this + * happens in case the range spans (last_range_end, end of device]. In this case + * it's up to the caller to trim @end_ret to the appropriate size. + */ +int find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start, + u64 *start_ret, u64 *end_ret, unsigned bits) +{ + struct extent_state *state; + struct rb_node *node, *prev = NULL, *next; + int ret = 1; + + spin_lock(&tree->lock); + + /* Find first extent with bits cleared */ + while (1) { + node = __etree_search(tree, start, &next, &prev, NULL, NULL); + if (!node) { + node = next; + if (!node) { + /* + * We are past the last allocated chunk, + * set start at the end of the last extent. The + * device alloc tree should never be empty so + * prev is always set. + */ + ASSERT(prev); + state = rb_entry(prev, struct extent_state, rb_node); + *start_ret = state->end + 1; + *end_ret = -1; + ret = 0; + goto out; + } + } + 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; + } else { + *start_ret = start; + break; + } + } + + /* + * Find the longest stretch from start until an entry which has the + * bits set + */ + while (1) { + state = rb_entry(node, struct extent_state, rb_node); + if (state->end >= start && !(state->state & bits)) { + *end_ret = state->end; + ret = 0; + } else { + *end_ret = state->start - 1; + ret = 0; + break; + } + + node = rb_next(node); + if (!node) + break; + } +out: + spin_unlock(&tree->lock); + return ret; +} + /* * find a contiguous range of bytes in the file marked as delalloc, not * more than 'max_bytes'. start and end are used to return the range, diff --git a/fs/btrfs/extent_io.h b/fs/btrfs/extent_io.h index d238efd628cf..7ddb3ec70023 100644 --- a/fs/btrfs/extent_io.h +++ b/fs/btrfs/extent_io.h @@ -391,6 +391,8 @@ static inline int set_extent_uptodate(struct extent_io_tree *tree, u64 start, int find_first_extent_bit(struct extent_io_tree *tree, u64 start, u64 *start_ret, u64 *end_ret, unsigned bits, struct extent_state **cached_state); +int find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start, + u64 *start_ret, u64 *end_ret, unsigned bits); int extent_invalidatepage(struct extent_io_tree *tree, struct page *page, unsigned long offset); int extent_write_full_page(struct page *page, struct writeback_control *wbc);
This function is very similar to find_first_extent_bit except that it locates the first contiguous span of space which does not have bits set. It's intended use is in the freespace trimming code. Signed-off-by: Nikolay Borisov <nborisov@suse.com> --- fs/btrfs/extent_io.c | 78 ++++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/extent_io.h | 2 ++ 2 files changed, 80 insertions(+)