[14/15] btrfs: Implement find_first_clear_extent_bit
diff mbox series

Message ID 20190130145102.4708-15-nborisov@suse.com
State New
Headers show
Series
  • Improvements to fitrim
Related show

Commit Message

Nikolay Borisov Jan. 30, 2019, 2:51 p.m. UTC
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(+)

Comments

Johannes Thumshirn Feb. 4, 2019, 2:04 p.m. UTC | #1
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?
Nikolay Borisov Feb. 4, 2019, 4:57 p.m. UTC | #2
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);
>

Patch
diff mbox series

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);