summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorNikolay Borisov <nborisov@suse.com>2019-03-27 14:24:17 +0200
committerDavid Sterba <dsterba@suse.com>2019-04-29 19:02:38 +0200
commit45bfcfc168f84f498d9825ec20ff3f4ee9208e04 (patch)
tree6b0edd5cf7e333b87bbc69921425fbc25f540e0e
parent8811133d8a982d3cef5d25eef54a8dca9e8e6ded (diff)
downloadlinux-45bfcfc168f84f498d9825ec20ff3f4ee9208e04.tar.bz2
btrfs: Implement find_first_clear_extent_bit
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> Signed-off-by: David Sterba <dsterba@suse.com>
-rw-r--r--fs/btrfs/extent_io.c73
-rw-r--r--fs/btrfs/extent_io.h2
2 files changed, 75 insertions, 0 deletions
diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index ff1f7b4ac02c..828708f6510c 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -1542,6 +1542,79 @@ out:
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
+ *
+ * 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.
+ */
+void 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;
+
+ 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;
+ 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;
+ } else {
+ *end_ret = state->start - 1;
+ break;
+ }
+
+ node = rb_next(node);
+ if (!node)
+ break;
+ }
+out:
+ spin_unlock(&tree->lock);
+}
+
/*
* 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 1680832d2c88..f7ca1516f70b 100644
--- a/fs/btrfs/extent_io.h
+++ b/fs/btrfs/extent_io.h
@@ -403,6 +403,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);
+void 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);