Linux-BTRFS Archive on lore.kernel.org
 help / color / Atom feed
From: Nikolay Borisov <nborisov@suse.com>
To: linux-btrfs@vger.kernel.org
Cc: jeffm@suse.com
Subject: Re: [PATCH 14/15] btrfs: Implement find_first_clear_extent_bit
Date: Mon, 4 Feb 2019 18:57:01 +0200
Message-ID: <0dbc158a-f1d8-47c0-cfbf-b1c5f6f3ff84@suse.com> (raw)
In-Reply-To: <20190130145102.4708-15-nborisov@suse.com>



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

  parent reply index

Thread overview: 36+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-01-30 14:50 [PATCH 00/15] Improvements to fitrim Nikolay Borisov
2019-01-30 14:50 ` [PATCH 01/15] btrfs: Honour FITRIM range constraints during free space trim Nikolay Borisov
2019-01-31 15:21   ` David Sterba
2019-01-31 15:35     ` Nikolay Borisov
2019-01-31 15:48       ` David Sterba
2019-01-31 19:30       ` Jeff Mahoney
2019-01-31 21:45         ` Nikolay Borisov
2019-01-30 14:50 ` [PATCH 02/15] btrfs: Make WARN_ON in a canonical form Nikolay Borisov
2019-01-31 15:22   ` David Sterba
2019-02-04 13:12   ` Johannes Thumshirn
2019-01-30 14:50 ` [PATCH 03/15] btrfs: Remove EXTENT_FIRST_DELALLOC bit Nikolay Borisov
2019-01-31 15:23   ` David Sterba
2019-02-04 13:15   ` Johannes Thumshirn
2019-01-30 14:50 ` [PATCH 04/15] btrfs: combine device update operations during transaction commit Nikolay Borisov
2019-02-04 13:25   ` Johannes Thumshirn
2019-02-04 14:48     ` Nikolay Borisov
2019-02-05  9:21       ` Johannes Thumshirn
2019-01-30 14:50 ` [PATCH 05/15] btrfs: Handle pending/pinned chunks before blockgroup relocation during device shrink Nikolay Borisov
2019-02-04 13:29   ` Johannes Thumshirn
2019-01-30 14:50 ` [PATCH 06/15] btrfs: Rename and export clear_btree_io_tree Nikolay Borisov
2019-02-04 13:31   ` Johannes Thumshirn
2019-01-30 14:50 ` [PATCH 07/15] btrfs: Populate ->orig_block_len during read_one_chunk Nikolay Borisov
2019-01-30 14:50 ` [PATCH 08/15] btrfs: Introduce new bits for device allocation tree Nikolay Borisov
2019-01-30 14:50 ` [PATCH 09/15] btrfs: replace pending/pinned chunks lists with io tree Nikolay Borisov
2019-01-30 14:50 ` [PATCH 10/15] btrfs: Remove 'trans' argument from find_free_dev_extent(_start) Nikolay Borisov
2019-02-04 14:36   ` Johannes Thumshirn
2019-01-30 14:50 ` [PATCH 11/15] btrfs: Factor out in_range macro Nikolay Borisov
2019-02-04 13:57   ` Johannes Thumshirn
2019-01-30 14:50 ` [PATCH 12/15] btrfs: Optimize unallocated chunks discard Nikolay Borisov
2019-01-30 14:51 ` [PATCH 13/15] btrfs: Fix gross misnaming Nikolay Borisov
2019-01-30 14:51 ` [PATCH 14/15] btrfs: Implement find_first_clear_extent_bit Nikolay Borisov
2019-02-04 14:04   ` Johannes Thumshirn
2019-02-04 16:57   ` Nikolay Borisov [this message]
2019-01-30 14:51 ` [PATCH 15/15] btrfs: Switch btrfs_trim_free_extents to find_first_clear_extent_bit Nikolay Borisov
2019-01-31 15:38   ` [PATCH v2] " Nikolay Borisov
2019-01-31 15:41   ` [PATCH v3] " Nikolay Borisov

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=0dbc158a-f1d8-47c0-cfbf-b1c5f6f3ff84@suse.com \
    --to=nborisov@suse.com \
    --cc=jeffm@suse.com \
    --cc=linux-btrfs@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Linux-BTRFS Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-btrfs/0 linux-btrfs/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-btrfs linux-btrfs/ https://lore.kernel.org/linux-btrfs \
		linux-btrfs@vger.kernel.org linux-btrfs@archiver.kernel.org
	public-inbox-index linux-btrfs


Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-btrfs


AGPL code for this site: git clone https://public-inbox.org/ public-inbox