btrfs: cache extent state records for fiemapfiemap_speedup

TODO

Signed-off-by: Filipe Manana <fdmanana@suse.com>

5 files changed, 74 insertions, 20 deletions

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 9d8b9badbca70e..33fda7004231b8 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -3272,7 +3272,8 @@ unsigned int btrfs_verify_data_csum(struct btrfs_bio *bbio,
 				    u32 bio_offset, struct page *page,
 				    u64 start, u64 end);
 struct extent_map *btrfs_get_extent_fiemap(struct btrfs_inode *inode,
-					   u64 start, u64 len);
+					   u64 start, u64 len,
+					   struct extent_state **cached_state);
 noinline int can_nocow_extent(struct inode *inode, u64 offset, u64 *len,
 			      u64 *orig_start, u64 *orig_block_len,
 			      u64 *ram_bytes, bool strict);
diff --git a/fs/btrfs/extent-io-tree.h b/fs/btrfs/extent-io-tree.h
index c3eb52dbe61cc1..0954463303de8c 100644
--- a/fs/btrfs/extent-io-tree.h
+++ b/fs/btrfs/extent-io-tree.h
@@ -119,7 +119,8 @@ void __cold extent_io_exit(void);
 
 u64 count_range_bits(struct extent_io_tree *tree,
 		     u64 *start, u64 search_end,
-		     u64 max_bytes, u32 bits, int contig);
+		     u64 max_bytes, u32 bits, int contig,
+		     struct extent_state **cached_state);
 
 void free_extent_state(struct extent_state *state);
 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end,
diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 9fd11468302734..80e3a1d25519de 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -2103,9 +2103,10 @@ void extent_clear_unlock_delalloc(struct btrfs_inode *inode, u64 start, u64 end,
  */
 u64 count_range_bits(struct extent_io_tree *tree,
 		     u64 *start, u64 search_end, u64 max_bytes,
-		     u32 bits, int contig)
+		     u32 bits, int contig,
+		     struct extent_state **cached_state)
 {
-	struct rb_node *node;
+	struct rb_node *node = NULL;
 	struct extent_state *state;
 	u64 cur_start = *start;
 	u64 total_bytes = 0;
@@ -2120,13 +2121,51 @@ u64 count_range_bits(struct extent_io_tree *tree,
 		total_bytes = tree->dirty_bytes;
 		goto out;
 	}
-	/*
-	 * this search will find all the extents that end after
-	 * our range starts.
-	 */
-	node = tree_search(tree, cur_start);
-	if (!node)
-		goto out;
+
+	if (cached_state && *cached_state) {
+		struct extent_state *cached = *cached_state;
+		bool free_cached_state = true;
+
+		if (extent_state_in_tree(cached)) {
+			if (cached->start <= cur_start) {
+				node = &cached->rb_node;
+				free_cached_state = false;
+			} else {
+				struct rb_node *prev;
+
+				/*
+				 * The cached state starts after the desired
+				 * range's start. Check if the previous state
+				 * record starts at or before the desired start,
+				 * and if so use it - this is a common case when
+				 * we have holes.
+				 */
+				prev = rb_prev(&cached->rb_node);
+				if (prev) {
+					state = rb_entry(prev,
+							 struct extent_state,
+							 rb_node);
+					if (state->start <= cur_start)
+						node = prev;
+				}
+			}
+		}
+
+		if (free_cached_state) {
+			free_extent_state(cached);
+			*cached_state = NULL;
+		}
+	}
+
+	if (!node) {
+		/*
+		 * This search will find all the extents that end after
+		 * our range starts.
+		 */
+		node = tree_search(tree, cur_start);
+		if (!node)
+			goto out;
+	}
 
 	while (1) {
 		state = rb_entry(node, struct extent_state, rb_node);
@@ -2151,6 +2190,12 @@ u64 count_range_bits(struct extent_io_tree *tree,
 		if (!node)
 			break;
 	}
+
+	if (cached_state) {
+		free_extent_state(*cached_state);
+		*cached_state = state;
+		refcount_inc(&state->refs);
+	}
 out:
 	spin_unlock(&tree->lock);
 	return total_bytes;
@@ -2427,7 +2472,7 @@ int clean_io_failure(struct btrfs_fs_info *fs_info,
 
 	private = 0;
 	ret = count_range_bits(failure_tree, &private, (u64)-1, 1,
-			       EXTENT_DIRTY, 0);
+			       EXTENT_DIRTY, 0, NULL);
 	if (!ret)
 		return 0;
 
@@ -5368,7 +5413,8 @@ next:
  * This maps until we find something past 'last'
  */
 static struct extent_map *get_extent_skip_holes(struct btrfs_inode *inode,
-						u64 offset, u64 last)
+						u64 offset, u64 last,
+						struct extent_state **cached_state)
 {
 	u64 sectorsize = btrfs_inode_sectorsize(inode);
 	struct extent_map *em;
@@ -5382,7 +5428,7 @@ static struct extent_map *get_extent_skip_holes(struct btrfs_inode *inode,
 		if (len == 0)
 			break;
 		len = ALIGN(len, sectorsize);
-		em = btrfs_get_extent_fiemap(inode, offset, len);
+		em = btrfs_get_extent_fiemap(inode, offset, len, cached_state);
 		if (IS_ERR(em))
 			return em;
 
@@ -5526,6 +5572,7 @@ int extent_fiemap(struct btrfs_inode *inode, struct fiemap_extent_info *fieinfo,
 	struct btrfs_key found_key;
 	struct extent_map *em = NULL;
 	struct extent_state *cached_state = NULL;
+	struct extent_state *search_cached_state = NULL;
 	struct btrfs_path *path;
 	struct btrfs_root *root = inode->root;
 	struct fiemap_cache cache = { 0 };
@@ -5606,7 +5653,8 @@ int extent_fiemap(struct btrfs_inode *inode, struct fiemap_extent_info *fieinfo,
 	lock_extent_bits(&inode->io_tree, start, start + len - 1,
 			 &cached_state);
 
-	em = get_extent_skip_holes(inode, start, last_for_get_extent);
+	em = get_extent_skip_holes(inode, start, last_for_get_extent,
+				   &search_cached_state);
 	if (!em)
 		goto out;
 	if (IS_ERR(em)) {
@@ -5694,7 +5742,8 @@ int extent_fiemap(struct btrfs_inode *inode, struct fiemap_extent_info *fieinfo,
 		}
 
 		/* now scan forward to see if this is really the last extent. */
-		em = get_extent_skip_holes(inode, off, last_for_get_extent);
+		em = get_extent_skip_holes(inode, off, last_for_get_extent,
+					   &search_cached_state);
 		if (IS_ERR(em)) {
 			ret = PTR_ERR(em);
 			goto out;
@@ -5718,6 +5767,7 @@ out_free:
 out:
 	unlock_extent_cached(&inode->io_tree, start, start + len - 1,
 			     &cached_state);
+	free_extent_state(search_cached_state);
 
 out_free_ulist:
 	btrfs_free_path(path);
diff --git a/fs/btrfs/file.c b/fs/btrfs/file.c
index 1528b8edc7a9a5..bfbed753955338 100644
--- a/fs/btrfs/file.c
+++ b/fs/btrfs/file.c
@@ -3636,7 +3636,7 @@ static loff_t find_desired_extent(struct btrfs_inode *inode, loff_t offset,
 	lock_extent_bits(&inode->io_tree, lockstart, lockend, &cached_state);
 
 	while (start < i_size) {
-		em = btrfs_get_extent_fiemap(inode, start, len);
+		em = btrfs_get_extent_fiemap(inode, start, len, NULL);
 		if (IS_ERR(em)) {
 			ret = PTR_ERR(em);
 			em = NULL;
diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c
index 3e10a2d1b4a581..8e6a2bfe140055 100644
--- a/fs/btrfs/inode.c
+++ b/fs/btrfs/inode.c
@@ -1623,7 +1623,7 @@ static int fallback_to_cow(struct btrfs_inode *inode, struct page *locked_page,
 	 * when starting writeback.
 	 */
 	count = count_range_bits(io_tree, &range_start, end, range_bytes,
-				 EXTENT_NORESERVE, 0);
+				 EXTENT_NORESERVE, 0, NULL);
 	if (count > 0 || is_space_ino || is_reloc_ino) {
 		u64 bytes = count;
 		struct btrfs_fs_info *fs_info = inode->root->fs_info;
@@ -6969,7 +6969,8 @@ out:
 }
 
 struct extent_map *btrfs_get_extent_fiemap(struct btrfs_inode *inode,
-					   u64 start, u64 len)
+					   u64 start, u64 len,
+					   struct extent_state **cached_state)
 {
 	struct extent_map *em;
 	struct extent_map *hole_em = NULL;
@@ -7005,7 +7006,8 @@ struct extent_map *btrfs_get_extent_fiemap(struct btrfs_inode *inode,
 
 	/* ok, we didn't find anything, lets look for delalloc */
 	delalloc_len = count_range_bits(&inode->io_tree, &delalloc_start,
-				 end, len, EXTENT_DELALLOC, 1);
+					end, len, EXTENT_DELALLOC, 1,
+					cached_state);
 	delalloc_end = delalloc_start + delalloc_len;
 	if (delalloc_end < delalloc_start)
 		delalloc_end = (u64)-1;