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 [thread overview]
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
next prev parent reply other threads:[~2019-01-30 14:51 UTC|newest]
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 publicly 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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).