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, Nikolay Borisov <nborisov@suse.com>
Subject: [PATCH 14/15] btrfs: Implement find_first_clear_extent_bit
Date: Wed, 30 Jan 2019 16:51:01 +0200
Message-ID: <20190130145102.4708-15-nborisov@suse.com> (raw)
In-Reply-To: <20190130145102.4708-1-nborisov@suse.com>

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;
+			}
+		}
+		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);
-- 
2.17.1


  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 ` Nikolay Borisov [this message]
2019-02-04 14:04   ` [PATCH 14/15] btrfs: Implement find_first_clear_extent_bit Johannes Thumshirn
2019-02-04 16:57   ` Nikolay Borisov
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=20190130145102.4708-15-nborisov@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