[PATCH v3 0/4] btrfs: Refactor find_free_extent()

[PATCH v3 0/4] btrfs: Refactor find_free_extent()

[Qu Wenruo]

Can be fetched from github:
https://github.com/adam900710/linux/tree/refactor_find_free_extent

Which is based on v4.19-rc1.

extent-tree.c::find_free_extent() could be one of the most
ill-structured functions, it has at least 6 non-exit tags and jumps
between them.

Refactor it into 4 parts:

1) find_free_extent()
   The main entrance, does the main work of block group iteration and
   block group selection.
   Now this function doesn't care nor handles free extent search by
   itself.

2) find_free_extent_clustered()
   Do clustered free extent search.
   May try to build/re-fill cluster.

3) find_free_extent_unclustered()
   Do unclustered free extent search.
   May try to fill free space cache.

4) find_free_extent_update_loop()
   Do the loop based black magic.
   May allocate new chunk.

With this patch, at least we should make find_free_extent() a little
easier to read, and provides the basis for later work on this function.

Current refactor is trying not to touch the original functionality, thus
the helper structure find_free_extent_ctl still contains a lot of
unrelated members.
But it should not change how find_free_extent() works at all.

changelog:
v2:
  Split into 4 patches.
  Minor comment newline change.
v3:
  Mostly cosmetic update.
  Rebased to v4.19-rc1
  Rename find_free_extent_ctrl to find_free_extent_ctl to keep the
  naming scheme the same.
  Fix some comment spelling error.
  Enhance comment for find_free_extent_unclustered().
  Add reviewed-by tag.

Qu Wenruo (4):
  btrfs: Introduce find_free_extent_ctl structure for later rework
  btrfs: Refactor clustered extent allocation into
    find_free_extent_clustered()
  btrfs: Refactor unclustered extent allocation into
    find_free_extent_unclustered()
  btrfs: Refactor find_free_extent() loops update into
    find_free_extent_update_loop()

 fs/btrfs/extent-tree.c | 702 ++++++++++++++++++++++++-----------------
 1 file changed, 404 insertions(+), 298 deletions(-)

-- 
2.19.1

[PATCH v3 1/4] btrfs: Introduce find_free_extent_ctl structure for later rework

[Qu Wenruo]

Instead of tons of different local variables in find_free_extent(),
extract them into find_free_extent_ctl structure, and add better
explanation for them.

Some modification may looks redundant, but will later greatly simplify
function parameter list during find_free_extent() refactor.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 fs/btrfs/extent-tree.c | 253 ++++++++++++++++++++++++++---------------
 1 file changed, 161 insertions(+), 92 deletions(-)

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index de6f75f5547b..dc10f6fd26af 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -7212,6 +7212,55 @@ btrfs_release_block_group(struct btrfs_block_group_cache *cache,
 	btrfs_put_block_group(cache);
 }
 
+/*
+ * Internal used structure for find_free_extent() function.
+ * Wraps needed parameters.
+ */
+struct find_free_extent_ctl {
+	/* Basic allocation info */
+	u64 ram_bytes;
+	u64 num_bytes;
+	u64 empty_size;
+	u64 flags;
+	int delalloc;
+
+	/* Where to start the search inside the bg */
+	u64 search_start;
+
+	/* For clustered allocation */
+	u64 empty_cluster;
+
+	bool have_caching_bg;
+	bool orig_have_caching_bg;
+
+	/* RAID index, converted from flags */
+	int index;
+
+	/* Current loop number */
+	int loop;
+
+	/*
+	 * Whether we're refilling a cluster, if true we need to re-search
+	 * current block group but don't try to refill the cluster again.
+	 */
+	bool retry_clustered;
+
+	/*
+	 * Whether we're updating free space cache, if true we need to re-search
+	 * current block group but don't try updating free space cache again.
+	 */
+	bool retry_unclustered;
+
+	/* If current block group is cached */
+	int cached;
+
+	/* Max extent size found */
+	u64 max_extent_size;
+
+	/* Found result */
+	u64 found_offset;
+};
+
 /*
  * walks the btree of allocated extents and find a hole of a given size.
  * The key ins is changed to record the hole:
@@ -7232,20 +7281,26 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 	struct btrfs_root *root = fs_info->extent_root;
 	struct btrfs_free_cluster *last_ptr = NULL;
 	struct btrfs_block_group_cache *block_group = NULL;
-	u64 search_start = 0;
-	u64 max_extent_size = 0;
-	u64 empty_cluster = 0;
+	struct find_free_extent_ctl ffe_ctl = {0};
 	struct btrfs_space_info *space_info;
-	int loop = 0;
-	int index = btrfs_bg_flags_to_raid_index(flags);
-	bool failed_cluster_refill = false;
-	bool failed_alloc = false;
 	bool use_cluster = true;
-	bool have_caching_bg = false;
-	bool orig_have_caching_bg = false;
 	bool full_search = false;
 
 	WARN_ON(num_bytes < fs_info->sectorsize);
+
+	ffe_ctl.ram_bytes = ram_bytes;
+	ffe_ctl.num_bytes = num_bytes;
+	ffe_ctl.empty_size = empty_size;
+	ffe_ctl.flags = flags;
+	ffe_ctl.search_start = 0;
+	ffe_ctl.retry_clustered = false;
+	ffe_ctl.retry_unclustered = false;
+	ffe_ctl.delalloc = delalloc;
+	ffe_ctl.index = btrfs_bg_flags_to_raid_index(flags);
+	ffe_ctl.have_caching_bg = false;
+	ffe_ctl.orig_have_caching_bg = false;
+	ffe_ctl.found_offset = 0;
+
 	ins->type = BTRFS_EXTENT_ITEM_KEY;
 	ins->objectid = 0;
 	ins->offset = 0;
@@ -7281,7 +7336,8 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 		spin_unlock(&space_info->lock);
 	}
 
-	last_ptr = fetch_cluster_info(fs_info, space_info, &empty_cluster);
+	last_ptr = fetch_cluster_info(fs_info, space_info,
+				      &ffe_ctl.empty_cluster);
 	if (last_ptr) {
 		spin_lock(&last_ptr->lock);
 		if (last_ptr->block_group)
@@ -7298,10 +7354,12 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 		spin_unlock(&last_ptr->lock);
 	}
 
-	search_start = max(search_start, first_logical_byte(fs_info, 0));
-	search_start = max(search_start, hint_byte);
-	if (search_start == hint_byte) {
-		block_group = btrfs_lookup_block_group(fs_info, search_start);
+	ffe_ctl.search_start = max(ffe_ctl.search_start,
+				   first_logical_byte(fs_info, 0));
+	ffe_ctl.search_start = max(ffe_ctl.search_start, hint_byte);
+	if (ffe_ctl.search_start == hint_byte) {
+		block_group = btrfs_lookup_block_group(fs_info,
+						       ffe_ctl.search_start);
 		/*
 		 * we don't want to use the block group if it doesn't match our
 		 * allocation bits, or if its not cached.
@@ -7323,7 +7381,7 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 				btrfs_put_block_group(block_group);
 				up_read(&space_info->groups_sem);
 			} else {
-				index = btrfs_bg_flags_to_raid_index(
+				ffe_ctl.index = btrfs_bg_flags_to_raid_index(
 						block_group->flags);
 				btrfs_lock_block_group(block_group, delalloc);
 				goto have_block_group;
@@ -7333,21 +7391,19 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 		}
 	}
 search:
-	have_caching_bg = false;
-	if (index == 0 || index == btrfs_bg_flags_to_raid_index(flags))
+	ffe_ctl.have_caching_bg = false;
+	if (ffe_ctl.index == btrfs_bg_flags_to_raid_index(flags) ||
+	    ffe_ctl.index == 0)
 		full_search = true;
 	down_read(&space_info->groups_sem);
-	list_for_each_entry(block_group, &space_info->block_groups[index],
-			    list) {
-		u64 offset;
-		int cached;
-
+	list_for_each_entry(block_group,
+			    &space_info->block_groups[ffe_ctl.index], list) {
 		/* If the block group is read-only, we can skip it entirely. */
 		if (unlikely(block_group->ro))
 			continue;
 
 		btrfs_grab_block_group(block_group, delalloc);
-		search_start = block_group->key.objectid;
+		ffe_ctl.search_start = block_group->key.objectid;
 
 		/*
 		 * this can happen if we end up cycling through all the
@@ -7371,9 +7427,9 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 		}
 
 have_block_group:
-		cached = block_group_cache_done(block_group);
-		if (unlikely(!cached)) {
-			have_caching_bg = true;
+		ffe_ctl.cached = block_group_cache_done(block_group);
+		if (unlikely(!ffe_ctl.cached)) {
+			ffe_ctl.have_caching_bg = true;
 			ret = cache_block_group(block_group, 0);
 			BUG_ON(ret < 0);
 			ret = 0;
@@ -7401,20 +7457,23 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 
 			if (used_block_group != block_group &&
 			    (used_block_group->ro ||
-			     !block_group_bits(used_block_group, flags)))
+			     !block_group_bits(used_block_group,
+				     	       ffe_ctl.flags)))
 				goto release_cluster;
 
-			offset = btrfs_alloc_from_cluster(used_block_group,
+			ffe_ctl.found_offset = btrfs_alloc_from_cluster(
+						used_block_group,
 						last_ptr,
 						num_bytes,
 						used_block_group->key.objectid,
-						&max_extent_size);
-			if (offset) {
+						&ffe_ctl.max_extent_size);
+			if (ffe_ctl.found_offset) {
 				/* we have a block, we're done */
 				spin_unlock(&last_ptr->refill_lock);
 				trace_btrfs_reserve_extent_cluster(
 						used_block_group,
-						search_start, num_bytes);
+						ffe_ctl.search_start,
+						num_bytes);
 				if (used_block_group != block_group) {
 					btrfs_release_block_group(block_group,
 								  delalloc);
@@ -7440,7 +7499,7 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 			 * first, so that we stand a better chance of
 			 * succeeding in the unclustered
 			 * allocation.  */
-			if (loop >= LOOP_NO_EMPTY_SIZE &&
+			if (ffe_ctl.loop >= LOOP_NO_EMPTY_SIZE &&
 			    used_block_group != block_group) {
 				spin_unlock(&last_ptr->refill_lock);
 				btrfs_release_block_group(used_block_group,
@@ -7458,18 +7517,19 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 				btrfs_release_block_group(used_block_group,
 							  delalloc);
 refill_cluster:
-			if (loop >= LOOP_NO_EMPTY_SIZE) {
+			if (ffe_ctl.loop >= LOOP_NO_EMPTY_SIZE) {
 				spin_unlock(&last_ptr->refill_lock);
 				goto unclustered_alloc;
 			}
 
 			aligned_cluster = max_t(unsigned long,
-						empty_cluster + empty_size,
-					      block_group->full_stripe_len);
+					ffe_ctl.empty_cluster + empty_size,
+					block_group->full_stripe_len);
 
 			/* allocate a cluster in this block group */
 			ret = btrfs_find_space_cluster(fs_info, block_group,
-						       last_ptr, search_start,
+						       last_ptr,
+						       ffe_ctl.search_start,
 						       num_bytes,
 						       aligned_cluster);
 			if (ret == 0) {
@@ -7477,26 +7537,28 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 				 * now pull our allocation out of this
 				 * cluster
 				 */
-				offset = btrfs_alloc_from_cluster(block_group,
-							last_ptr,
-							num_bytes,
-							search_start,
-							&max_extent_size);
-				if (offset) {
+				ffe_ctl.found_offset = btrfs_alloc_from_cluster(
+						block_group, last_ptr,
+						num_bytes, ffe_ctl.search_start,
+						&ffe_ctl.max_extent_size);
+				if (ffe_ctl.found_offset) {
 					/* we found one, proceed */
 					spin_unlock(&last_ptr->refill_lock);
 					trace_btrfs_reserve_extent_cluster(
-						block_group, search_start,
+						block_group,
+						ffe_ctl.search_start,
 						num_bytes);
 					goto checks;
 				}
-			} else if (!cached && loop > LOOP_CACHING_NOWAIT
-				   && !failed_cluster_refill) {
+			} else if (!ffe_ctl.cached && ffe_ctl.loop >
+				   LOOP_CACHING_NOWAIT
+				   && !ffe_ctl.retry_clustered) {
 				spin_unlock(&last_ptr->refill_lock);
 
-				failed_cluster_refill = true;
+				ffe_ctl.retry_clustered = true;
 				wait_block_group_cache_progress(block_group,
-				       num_bytes + empty_cluster + empty_size);
+				       num_bytes + ffe_ctl.empty_cluster +
+				       empty_size);
 				goto have_block_group;
 			}
 
@@ -7522,89 +7584,96 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 			last_ptr->fragmented = 1;
 			spin_unlock(&last_ptr->lock);
 		}
-		if (cached) {
+		if (ffe_ctl.cached) {
 			struct btrfs_free_space_ctl *ctl =
 				block_group->free_space_ctl;
 
 			spin_lock(&ctl->tree_lock);
 			if (ctl->free_space <
-			    num_bytes + empty_cluster + empty_size) {
-				if (ctl->free_space > max_extent_size)
-					max_extent_size = ctl->free_space;
+			    num_bytes + ffe_ctl.empty_cluster + empty_size) {
+				if (ctl->free_space > ffe_ctl.max_extent_size)
+					ffe_ctl.max_extent_size = ctl->free_space;
 				spin_unlock(&ctl->tree_lock);
 				goto loop;
 			}
 			spin_unlock(&ctl->tree_lock);
 		}
 
-		offset = btrfs_find_space_for_alloc(block_group, search_start,
-						    num_bytes, empty_size,
-						    &max_extent_size);
+		ffe_ctl.found_offset = btrfs_find_space_for_alloc(block_group,
+				ffe_ctl.search_start, num_bytes, empty_size,
+				&ffe_ctl.max_extent_size);
 		/*
 		 * If we didn't find a chunk, and we haven't failed on this
 		 * block group before, and this block group is in the middle of
 		 * caching and we are ok with waiting, then go ahead and wait
-		 * for progress to be made, and set failed_alloc to true.
+		 * for progress to be made, and set ffe_ctl.retry_unclustered to
+		 * true.
 		 *
-		 * If failed_alloc is true then we've already waited on this
-		 * block group once and should move on to the next block group.
+		 * If ffe_ctl.retry_unclustered is true then we've already
+		 * waited on this block group once and should move on to the
+		 * next block group.
 		 */
-		if (!offset && !failed_alloc && !cached &&
-		    loop > LOOP_CACHING_NOWAIT) {
+		if (!ffe_ctl.found_offset && !ffe_ctl.retry_unclustered &&
+		    !ffe_ctl.cached && ffe_ctl.loop > LOOP_CACHING_NOWAIT) {
 			wait_block_group_cache_progress(block_group,
 						num_bytes + empty_size);
-			failed_alloc = true;
+			ffe_ctl.retry_unclustered = true;
 			goto have_block_group;
-		} else if (!offset) {
+		} else if (!ffe_ctl.found_offset) {
 			goto loop;
 		}
 checks:
-		search_start = round_up(offset, fs_info->stripesize);
+		ffe_ctl.search_start = round_up(ffe_ctl.found_offset,
+					     fs_info->stripesize);
 
 		/* move on to the next group */
-		if (search_start + num_bytes >
+		if (ffe_ctl.search_start + num_bytes >
 		    block_group->key.objectid + block_group->key.offset) {
-			btrfs_add_free_space(block_group, offset, num_bytes);
+			btrfs_add_free_space(block_group, ffe_ctl.found_offset,
+					     num_bytes);
 			goto loop;
 		}
 
-		if (offset < search_start)
-			btrfs_add_free_space(block_group, offset,
-					     search_start - offset);
+		if (ffe_ctl.found_offset < ffe_ctl.search_start)
+			btrfs_add_free_space(block_group, ffe_ctl.found_offset,
+				ffe_ctl.search_start - ffe_ctl.found_offset);
 
 		ret = btrfs_add_reserved_bytes(block_group, ram_bytes,
 				num_bytes, delalloc);
 		if (ret == -EAGAIN) {
-			btrfs_add_free_space(block_group, offset, num_bytes);
+			btrfs_add_free_space(block_group, ffe_ctl.found_offset,
+					     num_bytes);
 			goto loop;
 		}
 		btrfs_inc_block_group_reservations(block_group);
 
 		/* we are all good, lets return */
-		ins->objectid = search_start;
+		ins->objectid = ffe_ctl.search_start;
 		ins->offset = num_bytes;
 
-		trace_btrfs_reserve_extent(block_group, search_start, num_bytes);
+		trace_btrfs_reserve_extent(block_group, ffe_ctl.search_start,
+					   num_bytes);
 		btrfs_release_block_group(block_group, delalloc);
 		break;
 loop:
-		failed_cluster_refill = false;
-		failed_alloc = false;
+		ffe_ctl.retry_clustered = false;
+		ffe_ctl.retry_unclustered = false;
 		BUG_ON(btrfs_bg_flags_to_raid_index(block_group->flags) !=
-		       index);
+		       ffe_ctl.index);
 		btrfs_release_block_group(block_group, delalloc);
 		cond_resched();
 	}
 	up_read(&space_info->groups_sem);
 
-	if ((loop == LOOP_CACHING_NOWAIT) && have_caching_bg
-		&& !orig_have_caching_bg)
-		orig_have_caching_bg = true;
+	if ((ffe_ctl.loop == LOOP_CACHING_NOWAIT) && ffe_ctl.have_caching_bg
+		&& !ffe_ctl.orig_have_caching_bg)
+		ffe_ctl.orig_have_caching_bg = true;
 
-	if (!ins->objectid && loop >= LOOP_CACHING_WAIT && have_caching_bg)
+	if (!ins->objectid && ffe_ctl.loop >= LOOP_CACHING_WAIT &&
+	    ffe_ctl.have_caching_bg)
 		goto search;
 
-	if (!ins->objectid && ++index < BTRFS_NR_RAID_TYPES)
+	if (!ins->objectid && ++ffe_ctl.index < BTRFS_NR_RAID_TYPES)
 		goto search;
 
 	/*
@@ -7615,23 +7684,23 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 	 * LOOP_NO_EMPTY_SIZE, set empty_size and empty_cluster to 0 and try
 	 *			again
 	 */
-	if (!ins->objectid && loop < LOOP_NO_EMPTY_SIZE) {
-		index = 0;
-		if (loop == LOOP_CACHING_NOWAIT) {
+	if (!ins->objectid && ffe_ctl.loop < LOOP_NO_EMPTY_SIZE) {
+		ffe_ctl.index = 0;
+		if (ffe_ctl.loop == LOOP_CACHING_NOWAIT) {
 			/*
 			 * We want to skip the LOOP_CACHING_WAIT step if we
 			 * don't have any uncached bgs and we've already done a
 			 * full search through.
 			 */
-			if (orig_have_caching_bg || !full_search)
-				loop = LOOP_CACHING_WAIT;
+			if (ffe_ctl.orig_have_caching_bg || !full_search)
+				ffe_ctl.loop = LOOP_CACHING_WAIT;
 			else
-				loop = LOOP_ALLOC_CHUNK;
+				ffe_ctl.loop = LOOP_ALLOC_CHUNK;
 		} else {
-			loop++;
+			ffe_ctl.loop++;
 		}
 
-		if (loop == LOOP_ALLOC_CHUNK) {
+		if (ffe_ctl.loop == LOOP_ALLOC_CHUNK) {
 			struct btrfs_trans_handle *trans;
 			int exist = 0;
 
@@ -7654,7 +7723,7 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 			 * case.
 			 */
 			if (ret == -ENOSPC)
-				loop = LOOP_NO_EMPTY_SIZE;
+				ffe_ctl.loop = LOOP_NO_EMPTY_SIZE;
 
 			/*
 			 * Do not bail out on ENOSPC since we
@@ -7670,18 +7739,18 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 				goto out;
 		}
 
-		if (loop == LOOP_NO_EMPTY_SIZE) {
+		if (ffe_ctl.loop == LOOP_NO_EMPTY_SIZE) {
 			/*
 			 * Don't loop again if we already have no empty_size and
 			 * no empty_cluster.
 			 */
 			if (empty_size == 0 &&
-			    empty_cluster == 0) {
+			    ffe_ctl.empty_cluster == 0) {
 				ret = -ENOSPC;
 				goto out;
 			}
 			empty_size = 0;
-			empty_cluster = 0;
+			ffe_ctl.empty_cluster = 0;
 		}
 
 		goto search;
@@ -7698,9 +7767,9 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 out:
 	if (ret == -ENOSPC) {
 		spin_lock(&space_info->lock);
-		space_info->max_extent_size = max_extent_size;
+		space_info->max_extent_size = ffe_ctl.max_extent_size;
 		spin_unlock(&space_info->lock);
-		ins->offset = max_extent_size;
+		ins->offset = ffe_ctl.max_extent_size;
 	}
 	return ret;
 }
-- 
2.19.1

[PATCH v3 2/4] btrfs: Refactor clustered extent allocation into find_free_extent_clustered()

[Qu Wenruo]

We have two main methods to find free extents inside a block group:
1) clustered allocation
2) unclustered allocation

This patch will extract the clustered allocation into
find_free_extent_clustered() to make it a little easier to read.

Instead of jumping between different labels in find_free_extent(), the
helper function will use return value to indicate different behavior.

Signed-off-by: Qu Wenruo <wqu@suse.com>
Reviewed-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
 fs/btrfs/extent-tree.c | 244 ++++++++++++++++++++---------------------
 1 file changed, 121 insertions(+), 123 deletions(-)

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index dc10f6fd26af..896d54b3c554 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -7261,6 +7261,115 @@ struct find_free_extent_ctl {
 	u64 found_offset;
 };
 
+
+/*
+ * Helper function for find_free_extent().
+ *
+ * Return -ENOENT to inform caller that we need fallback to unclustered mode.
+ * Return -EAGAIN to inform caller that we need to re-search this block group
+ * Return >0 to inform caller that we find nothing
+ * Return 0 means we have found a location and set ffe_ctl->found_offset.
+ */
+static int find_free_extent_clustered(struct btrfs_block_group_cache *bg,
+		struct btrfs_free_cluster *last_ptr,
+		struct find_free_extent_ctl *ffe_ctl,
+		struct btrfs_block_group_cache **cluster_bg_ret)
+{
+	struct btrfs_fs_info *fs_info = bg->fs_info;
+	struct btrfs_block_group_cache *cluster_bg;
+	u64 aligned_cluster;
+	u64 offset;
+	int ret;
+
+	cluster_bg = btrfs_lock_cluster(bg, last_ptr, ffe_ctl->delalloc);
+	if (!cluster_bg)
+		goto refill_cluster;
+	if (cluster_bg != bg && (cluster_bg->ro ||
+	    !block_group_bits(cluster_bg, ffe_ctl->flags)))
+		goto release_cluster;
+
+	offset = btrfs_alloc_from_cluster(cluster_bg, last_ptr,
+			ffe_ctl->num_bytes, cluster_bg->key.objectid,
+			&ffe_ctl->max_extent_size);
+	if (offset) {
+		/* we have a block, we're done */
+		spin_unlock(&last_ptr->refill_lock);
+		trace_btrfs_reserve_extent_cluster(cluster_bg,
+				ffe_ctl->search_start, ffe_ctl->num_bytes);
+		*cluster_bg_ret = cluster_bg;
+		ffe_ctl->found_offset = offset;
+		return 0;
+	}
+	WARN_ON(last_ptr->block_group != cluster_bg);
+release_cluster:
+	/* If we are on LOOP_NO_EMPTY_SIZE, we can't set up a new clusters, so
+	 * lets just skip it and let the allocator find whatever block it can
+	 * find. If we reach this point, we will have tried the cluster
+	 * allocator plenty of times and not have found anything, so we are
+	 * likely way too fragmented for the clustering stuff to find anything.
+	 *
+	 * However, if the cluster is taken from the current block group,
+	 * release the cluster first, so that we stand a better chance of
+	 * succeeding in the unclustered allocation.
+	 */
+	if (ffe_ctl->loop >= LOOP_NO_EMPTY_SIZE && cluster_bg != bg) {
+		spin_unlock(&last_ptr->refill_lock);
+		btrfs_release_block_group(cluster_bg, ffe_ctl->delalloc);
+		return -ENOENT;
+	}
+
+	/* This cluster didn't work out, free it and start over */
+	btrfs_return_cluster_to_free_space(NULL, last_ptr);
+
+	if (cluster_bg != bg)
+		btrfs_release_block_group(cluster_bg, ffe_ctl->delalloc);
+
+refill_cluster:
+	if (ffe_ctl->loop >= LOOP_NO_EMPTY_SIZE) {
+		spin_unlock(&last_ptr->refill_lock);
+		return -ENOENT;
+	}
+
+	aligned_cluster = max_t(u64,
+			ffe_ctl->empty_cluster + ffe_ctl->empty_size,
+			bg->full_stripe_len);
+	ret = btrfs_find_space_cluster(fs_info, bg, last_ptr,
+			ffe_ctl->search_start, ffe_ctl->num_bytes,
+			aligned_cluster);
+	if (ret == 0) {
+		/* now pull our allocation out of this cluster */
+		offset = btrfs_alloc_from_cluster(bg, last_ptr,
+				ffe_ctl->num_bytes,
+				ffe_ctl->search_start,
+				&ffe_ctl->max_extent_size);
+		if (offset) {
+			/* we found one, proceed */
+			spin_unlock(&last_ptr->refill_lock);
+			trace_btrfs_reserve_extent_cluster(bg,
+					ffe_ctl->search_start, ffe_ctl->num_bytes);
+			ffe_ctl->found_offset = offset;
+			return 0;
+		}
+	} else if (!ffe_ctl->cached && ffe_ctl->loop > LOOP_CACHING_NOWAIT &&
+		   !ffe_ctl->retry_clustered) {
+		spin_unlock(&last_ptr->refill_lock);
+
+		ffe_ctl->retry_clustered = true;
+		wait_block_group_cache_progress(bg, ffe_ctl->num_bytes +
+				ffe_ctl->empty_cluster + ffe_ctl->empty_size);
+		return -EAGAIN;
+	}
+	/*
+	 * at this point we either didn't find a cluster or we weren't able to
+	 * allocate a block from our cluster.
+	 * Free the cluster we've been trying to use, and go to the next block
+	 * group.
+	 */
+	btrfs_return_cluster_to_free_space(NULL, last_ptr);
+	spin_unlock(&last_ptr->refill_lock);
+	return 1;
+}
+
 /*
  * walks the btree of allocated extents and find a hole of a given size.
  * The key ins is changed to record the hole:
@@ -7443,137 +7552,26 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 		 * lets look there
 		 */
 		if (last_ptr && use_cluster) {
-			struct btrfs_block_group_cache *used_block_group;
-			unsigned long aligned_cluster;
-			/*
-			 * the refill lock keeps out other
-			 * people trying to start a new cluster
-			 */
-			used_block_group = btrfs_lock_cluster(block_group,
-							      last_ptr,
-							      delalloc);
-			if (!used_block_group)
-				goto refill_cluster;
-
-			if (used_block_group != block_group &&
-			    (used_block_group->ro ||
-			     !block_group_bits(used_block_group,
-				     	       ffe_ctl.flags)))
-				goto release_cluster;
-
-			ffe_ctl.found_offset = btrfs_alloc_from_cluster(
-						used_block_group,
-						last_ptr,
-						num_bytes,
-						used_block_group->key.objectid,
-						&ffe_ctl.max_extent_size);
-			if (ffe_ctl.found_offset) {
-				/* we have a block, we're done */
-				spin_unlock(&last_ptr->refill_lock);
-				trace_btrfs_reserve_extent_cluster(
-						used_block_group,
-						ffe_ctl.search_start,
-						num_bytes);
-				if (used_block_group != block_group) {
-					btrfs_release_block_group(block_group,
-								  delalloc);
-					block_group = used_block_group;
-				}
-				goto checks;
-			}
-
-			WARN_ON(last_ptr->block_group != used_block_group);
-release_cluster:
-			/* If we are on LOOP_NO_EMPTY_SIZE, we can't
-			 * set up a new clusters, so lets just skip it
-			 * and let the allocator find whatever block
-			 * it can find.  If we reach this point, we
-			 * will have tried the cluster allocator
-			 * plenty of times and not have found
-			 * anything, so we are likely way too
-			 * fragmented for the clustering stuff to find
-			 * anything.
-			 *
-			 * However, if the cluster is taken from the
-			 * current block group, release the cluster
-			 * first, so that we stand a better chance of
-			 * succeeding in the unclustered
-			 * allocation.  */
-			if (ffe_ctl.loop >= LOOP_NO_EMPTY_SIZE &&
-			    used_block_group != block_group) {
-				spin_unlock(&last_ptr->refill_lock);
-				btrfs_release_block_group(used_block_group,
-							  delalloc);
-				goto unclustered_alloc;
-			}
-
-			/*
-			 * this cluster didn't work out, free it and
-			 * start over
-			 */
-			btrfs_return_cluster_to_free_space(NULL, last_ptr);
-
-			if (used_block_group != block_group)
-				btrfs_release_block_group(used_block_group,
-							  delalloc);
-refill_cluster:
-			if (ffe_ctl.loop >= LOOP_NO_EMPTY_SIZE) {
-				spin_unlock(&last_ptr->refill_lock);
-				goto unclustered_alloc;
-			}
+			struct btrfs_block_group_cache *cluster_bg = NULL;
 
-			aligned_cluster = max_t(unsigned long,
-					ffe_ctl.empty_cluster + empty_size,
-					block_group->full_stripe_len);
+			ret = find_free_extent_clustered(block_group, last_ptr,
+							 &ffe_ctl, &cluster_bg);
 
-			/* allocate a cluster in this block group */
-			ret = btrfs_find_space_cluster(fs_info, block_group,
-						       last_ptr,
-						       ffe_ctl.search_start,
-						       num_bytes,
-						       aligned_cluster);
 			if (ret == 0) {
-				/*
-				 * now pull our allocation out of this
-				 * cluster
-				 */
-				ffe_ctl.found_offset = btrfs_alloc_from_cluster(
-						block_group, last_ptr,
-						num_bytes, ffe_ctl.search_start,
-						&ffe_ctl.max_extent_size);
-				if (ffe_ctl.found_offset) {
-					/* we found one, proceed */
-					spin_unlock(&last_ptr->refill_lock);
-					trace_btrfs_reserve_extent_cluster(
-						block_group,
-						ffe_ctl.search_start,
-						num_bytes);
-					goto checks;
+				if (cluster_bg && cluster_bg != block_group) {
+					btrfs_release_block_group(block_group,
+								  delalloc);
+					block_group = cluster_bg;
 				}
-			} else if (!ffe_ctl.cached && ffe_ctl.loop >
-				   LOOP_CACHING_NOWAIT
-				   && !ffe_ctl.retry_clustered) {
-				spin_unlock(&last_ptr->refill_lock);
-
-				ffe_ctl.retry_clustered = true;
-				wait_block_group_cache_progress(block_group,
-				       num_bytes + ffe_ctl.empty_cluster +
-				       empty_size);
+				goto checks;
+			} else if (ret == -EAGAIN) {
 				goto have_block_group;
+			} else if (ret > 0) {
+				goto loop;
 			}
-
-			/*
-			 * at this point we either didn't find a cluster
-			 * or we weren't able to allocate a block from our
-			 * cluster.  Free the cluster we've been trying
-			 * to use, and go to the next block group
-			 */
-			btrfs_return_cluster_to_free_space(NULL, last_ptr);
-			spin_unlock(&last_ptr->refill_lock);
-			goto loop;
+			/* ret == -ENOENT case falls through */
 		}
 
-unclustered_alloc:
 		/*
 		 * We are doing an unclustered alloc, set the fragmented flag so
 		 * we don't bother trying to setup a cluster again until we get
-- 
2.19.1

[PATCH v3 3/4] btrfs: Refactor unclustered extent allocation into find_free_extent_unclustered()

[Qu Wenruo]

This patch will extract unclsutered extent allocation code into
find_free_extent_unclustered().

And this helper function will use return value to indicate what to do
next.

This should make find_free_extent() a little easier to read.

Signed-off-by: Qu Wenruo <wqu@suse.com>
Reviewed-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
 fs/btrfs/extent-tree.c | 114 ++++++++++++++++++++++++-----------------
 1 file changed, 68 insertions(+), 46 deletions(-)

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 896d54b3c554..e6bfa91af41c 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -7370,6 +7370,69 @@ static int find_free_extent_clustered(struct btrfs_block_group_cache *bg,
 	return 1;
 }
 
+/*
+ * Return >0 to inform caller that we find nothing
+ * Return 0 when we found an free extent and set ffe_ctrl->found_offset
+ * Return -EAGAIN to inform caller that we need to re-search this block group
+ */
+static int find_free_extent_unclustered(struct btrfs_block_group_cache *bg,
+		struct btrfs_free_cluster *last_ptr,
+		struct find_free_extent_ctl *ffe_ctl)
+{
+	u64 offset;
+
+	/*
+	 * We are doing an unclustered alloc, set the fragmented flag so we
+	 * don't bother trying to setup a cluster again until we get more space.
+	 */
+	if (unlikely(last_ptr)) {
+		spin_lock(&last_ptr->lock);
+		last_ptr->fragmented = 1;
+		spin_unlock(&last_ptr->lock);
+	}
+	if (ffe_ctl->cached) {
+		struct btrfs_free_space_ctl *free_space_ctl;
+
+		free_space_ctl = bg->free_space_ctl;
+		spin_lock(&free_space_ctl->tree_lock);
+		if (free_space_ctl->free_space <
+		    ffe_ctl->num_bytes + ffe_ctl->empty_cluster +
+		    ffe_ctl->empty_size) {
+			ffe_ctl->max_extent_size = max_t(u64,
+					ffe_ctl->max_extent_size,
+					free_space_ctl->free_space);
+			spin_unlock(&free_space_ctl->tree_lock);
+			return 1;
+		}
+		spin_unlock(&free_space_ctl->tree_lock);
+	}
+
+	offset = btrfs_find_space_for_alloc(bg, ffe_ctl->search_start,
+			ffe_ctl->num_bytes, ffe_ctl->empty_size,
+			&ffe_ctl->max_extent_size);
+
+	/*
+	 * If we didn't find a chunk, and we haven't failed on this block group
+	 * before, and this block group is in the middle of caching and we are
+	 * ok with waiting, then go ahead and wait for progress to be made, and
+	 * set @retry_unclustered to true.
+	 *
+	 * If @retry_unclustered is true then we've already waited on this block
+	 * group once and should move on to the next block group.
+	 */
+	if (!offset && !ffe_ctl->retry_unclustered && !ffe_ctl->cached &&
+	    ffe_ctl->loop > LOOP_CACHING_NOWAIT) {
+		wait_block_group_cache_progress(bg, ffe_ctl->num_bytes +
+						ffe_ctl->empty_size);
+		ffe_ctl->retry_unclustered = true;
+		return -EAGAIN;
+	} else if (!offset) {
+		return 1;
+	}
+	ffe_ctl->found_offset = offset;
+	return 0;
+}
+
 /*
  * walks the btree of allocated extents and find a hole of a given size.
  * The key ins is changed to record the hole:
@@ -7572,54 +7635,13 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 			/* ret == -ENOENT case falls through */
 		}
 
-		/*
-		 * We are doing an unclustered alloc, set the fragmented flag so
-		 * we don't bother trying to setup a cluster again until we get
-		 * more space.
-		 */
-		if (unlikely(last_ptr)) {
-			spin_lock(&last_ptr->lock);
-			last_ptr->fragmented = 1;
-			spin_unlock(&last_ptr->lock);
-		}
-		if (ffe_ctl.cached) {
-			struct btrfs_free_space_ctl *ctl =
-				block_group->free_space_ctl;
-
-			spin_lock(&ctl->tree_lock);
-			if (ctl->free_space <
-			    num_bytes + ffe_ctl.empty_cluster + empty_size) {
-				if (ctl->free_space > ffe_ctl.max_extent_size)
-					ffe_ctl.max_extent_size = ctl->free_space;
-				spin_unlock(&ctl->tree_lock);
-				goto loop;
-			}
-			spin_unlock(&ctl->tree_lock);
-		}
-
-		ffe_ctl.found_offset = btrfs_find_space_for_alloc(block_group,
-				ffe_ctl.search_start, num_bytes, empty_size,
-				&ffe_ctl.max_extent_size);
-		/*
-		 * If we didn't find a chunk, and we haven't failed on this
-		 * block group before, and this block group is in the middle of
-		 * caching and we are ok with waiting, then go ahead and wait
-		 * for progress to be made, and set ffe_ctl.retry_unclustered to
-		 * true.
-		 *
-		 * If ffe_ctl.retry_unclustered is true then we've already
-		 * waited on this block group once and should move on to the
-		 * next block group.
-		 */
-		if (!ffe_ctl.found_offset && !ffe_ctl.retry_unclustered &&
-		    !ffe_ctl.cached && ffe_ctl.loop > LOOP_CACHING_NOWAIT) {
-			wait_block_group_cache_progress(block_group,
-						num_bytes + empty_size);
-			ffe_ctl.retry_unclustered = true;
+		ret = find_free_extent_unclustered(block_group, last_ptr,
+						   &ffe_ctl);
+		if (ret == -EAGAIN)
 			goto have_block_group;
-		} else if (!ffe_ctl.found_offset) {
+		else if (ret > 0)
 			goto loop;
-		}
+		/* ret == 0 case falls through */
 checks:
 		ffe_ctl.search_start = round_up(ffe_ctl.found_offset,
 					     fs_info->stripesize);
-- 
2.19.1

[PATCH v3 4/4] btrfs: Refactor find_free_extent() loops update into find_free_extent_update_loop()

[Qu Wenruo]

We have a complex loop design for find_free_extent(), that has different
behavior for each loop, some even includes new chunk allocation.

Instead of putting such a long code into find_free_extent() and makes it
harder to read, just extract them into find_free_extent_update_loop().

With all the cleanups, the main find_free_extent() should be pretty
barebone:

find_free_extent()
|- Iterate through all block groups
|  |- Get a valid block group
|  |- Try to do clustered allocation in that block group
|  |- Try to do unclustered allocation in that block group
|  |- Check if the result is valid
|  |  |- If valid, then exit
|  |- Jump to next block group
|
|- Push harder to find free extents
   |- If not found, re-iterate all block groups

Signed-off-by: Qu Wenruo <wqu@suse.com>
Reviewed-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
 fs/btrfs/extent-tree.c | 217 ++++++++++++++++++++++-------------------
 1 file changed, 117 insertions(+), 100 deletions(-)

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index e6bfa91af41c..938569d2c583 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -7236,7 +7236,9 @@ struct find_free_extent_ctl {
 	/* RAID index, converted from flags */
 	int index;
 
-	/* Current loop number */
+	/*
+	 * Current loop number, check find_free_extent_update_loop() for details
+	 */
 	int loop;
 
 	/*
@@ -7433,6 +7435,117 @@ static int find_free_extent_unclustered(struct btrfs_block_group_cache *bg,
 	return 0;
 }
 
+/*
+ * Return >0 means caller needs to re-search for free extent
+ * Return 0 means we have the needed free extent.
+ * Return <0 means we failed to locate any free extent.
+ */
+static int find_free_extent_update_loop(struct btrfs_fs_info *fs_info,
+					struct btrfs_free_cluster *last_ptr,
+					struct btrfs_key *ins,
+					struct find_free_extent_ctl *ffe_ctl,
+					int full_search, bool use_cluster)
+{
+	struct btrfs_root *root = fs_info->extent_root;
+	int ret;
+
+	if ((ffe_ctl->loop == LOOP_CACHING_NOWAIT) &&
+	    ffe_ctl->have_caching_bg && !ffe_ctl->orig_have_caching_bg)
+		ffe_ctl->orig_have_caching_bg = true;
+
+	if (!ins->objectid && ffe_ctl->loop >= LOOP_CACHING_WAIT &&
+	     ffe_ctl->have_caching_bg)
+		return 1;
+
+	if (!ins->objectid && ++(ffe_ctl->index) < BTRFS_NR_RAID_TYPES)
+		return 1;
+
+	/*
+	 * LOOP_CACHING_NOWAIT, search partially cached block groups, kicking
+	 *			caching kthreads as we move along
+	 * LOOP_CACHING_WAIT, search everything, and wait if our bg is caching
+	 * LOOP_ALLOC_CHUNK, force a chunk allocation and try again
+	 * LOOP_NO_EMPTY_SIZE, set empty_size and empty_cluster to 0 and try
+	 *			again
+	 */
+	if (!ins->objectid && ffe_ctl->loop < LOOP_NO_EMPTY_SIZE) {
+		ffe_ctl->index = 0;
+		if (ffe_ctl->loop == LOOP_CACHING_NOWAIT) {
+			/*
+			 * We want to skip the LOOP_CACHING_WAIT step if we
+			 * don't have any uncached bgs and we've already done a
+			 * full search through.
+			 */
+			if (ffe_ctl->orig_have_caching_bg || !full_search)
+				ffe_ctl->loop = LOOP_CACHING_WAIT;
+			else
+				ffe_ctl->loop = LOOP_ALLOC_CHUNK;
+		} else {
+			ffe_ctl->loop++;
+		}
+
+		if (ffe_ctl->loop == LOOP_ALLOC_CHUNK) {
+			struct btrfs_trans_handle *trans;
+			int exist = 0;
+
+			trans = current->journal_info;
+			if (trans)
+				exist = 1;
+			else
+				trans = btrfs_join_transaction(root);
+
+			if (IS_ERR(trans)) {
+				ret = PTR_ERR(trans);
+				return ret;
+			}
+
+			ret = do_chunk_alloc(trans, ffe_ctl->flags,
+					     CHUNK_ALLOC_FORCE);
+
+			/*
+			 * If we can't allocate a new chunk we've already looped
+			 * through at least once, move on to the NO_EMPTY_SIZE
+			 * case.
+			 */
+			if (ret == -ENOSPC)
+				ffe_ctl->loop = LOOP_NO_EMPTY_SIZE;
+
+			/* Do not bail out on ENOSPC since we can do more. */
+			if (ret < 0 && ret != -ENOSPC)
+				btrfs_abort_transaction(trans, ret);
+			else
+				ret = 0;
+			if (!exist)
+				btrfs_end_transaction(trans);
+			if (ret)
+				return ret;
+		}
+
+		if (ffe_ctl->loop == LOOP_NO_EMPTY_SIZE) {
+			/*
+			 * Don't loop again if we already have no empty_size and
+			 * no empty_cluster.
+			 */
+			if (ffe_ctl->empty_size == 0 &&
+			    ffe_ctl->empty_cluster == 0)
+				return -ENOSPC;
+			ffe_ctl->empty_size = 0;
+			ffe_ctl->empty_cluster = 0;
+		}
+		return 1;
+	} else if (!ins->objectid) {
+		ret = -ENOSPC;
+	} else if (ins->objectid) {
+		if (!use_cluster && last_ptr) {
+			spin_lock(&last_ptr->lock);
+			last_ptr->window_start = ins->objectid;
+			spin_unlock(&last_ptr->lock);
+		}
+		ret = 0;
+	}
+	return ret;
+}
+
 /*
  * walks the btree of allocated extents and find a hole of a given size.
  * The key ins is changed to record the hole:
@@ -7450,7 +7563,6 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 				u64 flags, int delalloc)
 {
 	int ret = 0;
-	struct btrfs_root *root = fs_info->extent_root;
 	struct btrfs_free_cluster *last_ptr = NULL;
 	struct btrfs_block_group_cache *block_group = NULL;
 	struct find_free_extent_ctl ffe_ctl = {0};
@@ -7685,106 +7797,11 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
 	}
 	up_read(&space_info->groups_sem);
 
-	if ((ffe_ctl.loop == LOOP_CACHING_NOWAIT) && ffe_ctl.have_caching_bg
-		&& !ffe_ctl.orig_have_caching_bg)
-		ffe_ctl.orig_have_caching_bg = true;
-
-	if (!ins->objectid && ffe_ctl.loop >= LOOP_CACHING_WAIT &&
-	    ffe_ctl.have_caching_bg)
-		goto search;
-
-	if (!ins->objectid && ++ffe_ctl.index < BTRFS_NR_RAID_TYPES)
+	ret = find_free_extent_update_loop(fs_info, last_ptr, ins, &ffe_ctl,
+					   full_search, use_cluster);
+	if (ret > 0)
 		goto search;
 
-	/*
-	 * LOOP_CACHING_NOWAIT, search partially cached block groups, kicking
-	 *			caching kthreads as we move along
-	 * LOOP_CACHING_WAIT, search everything, and wait if our bg is caching
-	 * LOOP_ALLOC_CHUNK, force a chunk allocation and try again
-	 * LOOP_NO_EMPTY_SIZE, set empty_size and empty_cluster to 0 and try
-	 *			again
-	 */
-	if (!ins->objectid && ffe_ctl.loop < LOOP_NO_EMPTY_SIZE) {
-		ffe_ctl.index = 0;
-		if (ffe_ctl.loop == LOOP_CACHING_NOWAIT) {
-			/*
-			 * We want to skip the LOOP_CACHING_WAIT step if we
-			 * don't have any uncached bgs and we've already done a
-			 * full search through.
-			 */
-			if (ffe_ctl.orig_have_caching_bg || !full_search)
-				ffe_ctl.loop = LOOP_CACHING_WAIT;
-			else
-				ffe_ctl.loop = LOOP_ALLOC_CHUNK;
-		} else {
-			ffe_ctl.loop++;
-		}
-
-		if (ffe_ctl.loop == LOOP_ALLOC_CHUNK) {
-			struct btrfs_trans_handle *trans;
-			int exist = 0;
-
-			trans = current->journal_info;
-			if (trans)
-				exist = 1;
-			else
-				trans = btrfs_join_transaction(root);
-
-			if (IS_ERR(trans)) {
-				ret = PTR_ERR(trans);
-				goto out;
-			}
-
-			ret = do_chunk_alloc(trans, flags, CHUNK_ALLOC_FORCE);
-
-			/*
-			 * If we can't allocate a new chunk we've already looped
-			 * through at least once, move on to the NO_EMPTY_SIZE
-			 * case.
-			 */
-			if (ret == -ENOSPC)
-				ffe_ctl.loop = LOOP_NO_EMPTY_SIZE;
-
-			/*
-			 * Do not bail out on ENOSPC since we
-			 * can do more things.
-			 */
-			if (ret < 0 && ret != -ENOSPC)
-				btrfs_abort_transaction(trans, ret);
-			else
-				ret = 0;
-			if (!exist)
-				btrfs_end_transaction(trans);
-			if (ret)
-				goto out;
-		}
-
-		if (ffe_ctl.loop == LOOP_NO_EMPTY_SIZE) {
-			/*
-			 * Don't loop again if we already have no empty_size and
-			 * no empty_cluster.
-			 */
-			if (empty_size == 0 &&
-			    ffe_ctl.empty_cluster == 0) {
-				ret = -ENOSPC;
-				goto out;
-			}
-			empty_size = 0;
-			ffe_ctl.empty_cluster = 0;
-		}
-
-		goto search;
-	} else if (!ins->objectid) {
-		ret = -ENOSPC;
-	} else if (ins->objectid) {
-		if (!use_cluster && last_ptr) {
-			spin_lock(&last_ptr->lock);
-			last_ptr->window_start = ins->objectid;
-			spin_unlock(&last_ptr->lock);
-		}
-		ret = 0;
-	}
-out:
 	if (ret == -ENOSPC) {
 		spin_lock(&space_info->lock);
 		space_info->max_extent_size = ffe_ctl.max_extent_size;
-- 
2.19.1

Re: [PATCH v3 1/4] btrfs: Introduce find_free_extent_ctl structure for later rework

[Su Yue]

On 10/12/18 2:18 PM, Qu Wenruo wrote:
> Instead of tons of different local variables in find_free_extent(),
> extract them into find_free_extent_ctl structure, and add better
> explanation for them.
> 
> Some modification may looks redundant, but will later greatly simplify
> function parameter list during find_free_extent() refactor.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>

Reviewed-by: Su Yue <suy.fnst@cn.fujitsu.com>
> ---
>   fs/btrfs/extent-tree.c | 253 ++++++++++++++++++++++++++---------------
>   1 file changed, 161 insertions(+), 92 deletions(-)
> 
> diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
> index de6f75f5547b..dc10f6fd26af 100644
> --- a/fs/btrfs/extent-tree.c
> +++ b/fs/btrfs/extent-tree.c
> @@ -7212,6 +7212,55 @@ btrfs_release_block_group(struct btrfs_block_group_cache *cache,
>   	btrfs_put_block_group(cache);
>   }
>   
> +/*
> + * Internal used structure for find_free_extent() function.
> + * Wraps needed parameters.
> + */
> +struct find_free_extent_ctl {
> +	/* Basic allocation info */
> +	u64 ram_bytes;
> +	u64 num_bytes;
> +	u64 empty_size;
> +	u64 flags;
> +	int delalloc;
> +
> +	/* Where to start the search inside the bg */
> +	u64 search_start;
> +
> +	/* For clustered allocation */
> +	u64 empty_cluster;
> +
> +	bool have_caching_bg;
> +	bool orig_have_caching_bg;
> +
> +	/* RAID index, converted from flags */
> +	int index;
> +
> +	/* Current loop number */
> +	int loop;
> +
> +	/*
> +	 * Whether we're refilling a cluster, if true we need to re-search
> +	 * current block group but don't try to refill the cluster again.
> +	 */
> +	bool retry_clustered;
> +
> +	/*
> +	 * Whether we're updating free space cache, if true we need to re-search
> +	 * current block group but don't try updating free space cache again.
> +	 */
> +	bool retry_unclustered;
> +
> +	/* If current block group is cached */
> +	int cached;
> +
> +	/* Max extent size found */
> +	u64 max_extent_size;
> +
> +	/* Found result */
> +	u64 found_offset;
> +};
> +
>   /*
>    * walks the btree of allocated extents and find a hole of a given size.
>    * The key ins is changed to record the hole:
> @@ -7232,20 +7281,26 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   	struct btrfs_root *root = fs_info->extent_root;
>   	struct btrfs_free_cluster *last_ptr = NULL;
>   	struct btrfs_block_group_cache *block_group = NULL;
> -	u64 search_start = 0;
> -	u64 max_extent_size = 0;
> -	u64 empty_cluster = 0;
> +	struct find_free_extent_ctl ffe_ctl = {0};
>   	struct btrfs_space_info *space_info;
> -	int loop = 0;
> -	int index = btrfs_bg_flags_to_raid_index(flags);
> -	bool failed_cluster_refill = false;
> -	bool failed_alloc = false;
>   	bool use_cluster = true;
> -	bool have_caching_bg = false;
> -	bool orig_have_caching_bg = false;
>   	bool full_search = false;
>   
>   	WARN_ON(num_bytes < fs_info->sectorsize);
> +
> +	ffe_ctl.ram_bytes = ram_bytes;
> +	ffe_ctl.num_bytes = num_bytes;
> +	ffe_ctl.empty_size = empty_size;
> +	ffe_ctl.flags = flags;
> +	ffe_ctl.search_start = 0;
> +	ffe_ctl.retry_clustered = false;
> +	ffe_ctl.retry_unclustered = false;
> +	ffe_ctl.delalloc = delalloc;
> +	ffe_ctl.index = btrfs_bg_flags_to_raid_index(flags);
> +	ffe_ctl.have_caching_bg = false;
> +	ffe_ctl.orig_have_caching_bg = false;
> +	ffe_ctl.found_offset = 0;
> +
>   	ins->type = BTRFS_EXTENT_ITEM_KEY;
>   	ins->objectid = 0;
>   	ins->offset = 0;
> @@ -7281,7 +7336,8 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   		spin_unlock(&space_info->lock);
>   	}
>   
> -	last_ptr = fetch_cluster_info(fs_info, space_info, &empty_cluster);
> +	last_ptr = fetch_cluster_info(fs_info, space_info,
> +				      &ffe_ctl.empty_cluster);
>   	if (last_ptr) {
>   		spin_lock(&last_ptr->lock);
>   		if (last_ptr->block_group)
> @@ -7298,10 +7354,12 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   		spin_unlock(&last_ptr->lock);
>   	}
>   
> -	search_start = max(search_start, first_logical_byte(fs_info, 0));
> -	search_start = max(search_start, hint_byte);
> -	if (search_start == hint_byte) {
> -		block_group = btrfs_lookup_block_group(fs_info, search_start);
> +	ffe_ctl.search_start = max(ffe_ctl.search_start,
> +				   first_logical_byte(fs_info, 0));
> +	ffe_ctl.search_start = max(ffe_ctl.search_start, hint_byte);
> +	if (ffe_ctl.search_start == hint_byte) {
> +		block_group = btrfs_lookup_block_group(fs_info,
> +						       ffe_ctl.search_start);
>   		/*
>   		 * we don't want to use the block group if it doesn't match our
>   		 * allocation bits, or if its not cached.
> @@ -7323,7 +7381,7 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   				btrfs_put_block_group(block_group);
>   				up_read(&space_info->groups_sem);
>   			} else {
> -				index = btrfs_bg_flags_to_raid_index(
> +				ffe_ctl.index = btrfs_bg_flags_to_raid_index(
>   						block_group->flags);
>   				btrfs_lock_block_group(block_group, delalloc);
>   				goto have_block_group;
> @@ -7333,21 +7391,19 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   		}
>   	}
>   search:
> -	have_caching_bg = false;
> -	if (index == 0 || index == btrfs_bg_flags_to_raid_index(flags))
> +	ffe_ctl.have_caching_bg = false;
> +	if (ffe_ctl.index == btrfs_bg_flags_to_raid_index(flags) ||
> +	    ffe_ctl.index == 0)
>   		full_search = true;
>   	down_read(&space_info->groups_sem);
> -	list_for_each_entry(block_group, &space_info->block_groups[index],
> -			    list) {
> -		u64 offset;
> -		int cached;
> -
> +	list_for_each_entry(block_group,
> +			    &space_info->block_groups[ffe_ctl.index], list) {
>   		/* If the block group is read-only, we can skip it entirely. */
>   		if (unlikely(block_group->ro))
>   			continue;
>   
>   		btrfs_grab_block_group(block_group, delalloc);
> -		search_start = block_group->key.objectid;
> +		ffe_ctl.search_start = block_group->key.objectid;
>   
>   		/*
>   		 * this can happen if we end up cycling through all the
> @@ -7371,9 +7427,9 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   		}
>   
>   have_block_group:
> -		cached = block_group_cache_done(block_group);
> -		if (unlikely(!cached)) {
> -			have_caching_bg = true;
> +		ffe_ctl.cached = block_group_cache_done(block_group);
> +		if (unlikely(!ffe_ctl.cached)) {
> +			ffe_ctl.have_caching_bg = true;
>   			ret = cache_block_group(block_group, 0);
>   			BUG_ON(ret < 0);
>   			ret = 0;
> @@ -7401,20 +7457,23 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   
>   			if (used_block_group != block_group &&
>   			    (used_block_group->ro ||
> -			     !block_group_bits(used_block_group, flags)))
> +			     !block_group_bits(used_block_group,
> +				     	       ffe_ctl.flags)))
>   				goto release_cluster;
>   
> -			offset = btrfs_alloc_from_cluster(used_block_group,
> +			ffe_ctl.found_offset = btrfs_alloc_from_cluster(
> +						used_block_group,
>   						last_ptr,
>   						num_bytes,
>   						used_block_group->key.objectid,
> -						&max_extent_size);
> -			if (offset) {
> +						&ffe_ctl.max_extent_size);
> +			if (ffe_ctl.found_offset) {
>   				/* we have a block, we're done */
>   				spin_unlock(&last_ptr->refill_lock);
>   				trace_btrfs_reserve_extent_cluster(
>   						used_block_group,
> -						search_start, num_bytes);
> +						ffe_ctl.search_start,
> +						num_bytes);
>   				if (used_block_group != block_group) {
>   					btrfs_release_block_group(block_group,
>   								  delalloc);
> @@ -7440,7 +7499,7 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   			 * first, so that we stand a better chance of
>   			 * succeeding in the unclustered
>   			 * allocation.  */
> -			if (loop >= LOOP_NO_EMPTY_SIZE &&
> +			if (ffe_ctl.loop >= LOOP_NO_EMPTY_SIZE &&
>   			    used_block_group != block_group) {
>   				spin_unlock(&last_ptr->refill_lock);
>   				btrfs_release_block_group(used_block_group,
> @@ -7458,18 +7517,19 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   				btrfs_release_block_group(used_block_group,
>   							  delalloc);
>   refill_cluster:
> -			if (loop >= LOOP_NO_EMPTY_SIZE) {
> +			if (ffe_ctl.loop >= LOOP_NO_EMPTY_SIZE) {
>   				spin_unlock(&last_ptr->refill_lock);
>   				goto unclustered_alloc;
>   			}
>   
>   			aligned_cluster = max_t(unsigned long,
> -						empty_cluster + empty_size,
> -					      block_group->full_stripe_len);
> +					ffe_ctl.empty_cluster + empty_size,
> +					block_group->full_stripe_len);
>   
>   			/* allocate a cluster in this block group */
>   			ret = btrfs_find_space_cluster(fs_info, block_group,
> -						       last_ptr, search_start,
> +						       last_ptr,
> +						       ffe_ctl.search_start,
>   						       num_bytes,
>   						       aligned_cluster);
>   			if (ret == 0) {
> @@ -7477,26 +7537,28 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   				 * now pull our allocation out of this
>   				 * cluster
>   				 */
> -				offset = btrfs_alloc_from_cluster(block_group,
> -							last_ptr,
> -							num_bytes,
> -							search_start,
> -							&max_extent_size);
> -				if (offset) {
> +				ffe_ctl.found_offset = btrfs_alloc_from_cluster(
> +						block_group, last_ptr,
> +						num_bytes, ffe_ctl.search_start,
> +						&ffe_ctl.max_extent_size);
> +				if (ffe_ctl.found_offset) {
>   					/* we found one, proceed */
>   					spin_unlock(&last_ptr->refill_lock);
>   					trace_btrfs_reserve_extent_cluster(
> -						block_group, search_start,
> +						block_group,
> +						ffe_ctl.search_start,
>   						num_bytes);
>   					goto checks;
>   				}
> -			} else if (!cached && loop > LOOP_CACHING_NOWAIT
> -				   && !failed_cluster_refill) {
> +			} else if (!ffe_ctl.cached && ffe_ctl.loop >
> +				   LOOP_CACHING_NOWAIT
> +				   && !ffe_ctl.retry_clustered) {
>   				spin_unlock(&last_ptr->refill_lock);
>   
> -				failed_cluster_refill = true;
> +				ffe_ctl.retry_clustered = true;
>   				wait_block_group_cache_progress(block_group,
> -				       num_bytes + empty_cluster + empty_size);
> +				       num_bytes + ffe_ctl.empty_cluster +
> +				       empty_size);
>   				goto have_block_group;
>   			}
>   
> @@ -7522,89 +7584,96 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   			last_ptr->fragmented = 1;
>   			spin_unlock(&last_ptr->lock);
>   		}
> -		if (cached) {
> +		if (ffe_ctl.cached) {
>   			struct btrfs_free_space_ctl *ctl =
>   				block_group->free_space_ctl;
>   
>   			spin_lock(&ctl->tree_lock);
>   			if (ctl->free_space <
> -			    num_bytes + empty_cluster + empty_size) {
> -				if (ctl->free_space > max_extent_size)
> -					max_extent_size = ctl->free_space;
> +			    num_bytes + ffe_ctl.empty_cluster + empty_size) {
> +				if (ctl->free_space > ffe_ctl.max_extent_size)
> +					ffe_ctl.max_extent_size = ctl->free_space;
>   				spin_unlock(&ctl->tree_lock);
>   				goto loop;
>   			}
>   			spin_unlock(&ctl->tree_lock);
>   		}
>   
> -		offset = btrfs_find_space_for_alloc(block_group, search_start,
> -						    num_bytes, empty_size,
> -						    &max_extent_size);
> +		ffe_ctl.found_offset = btrfs_find_space_for_alloc(block_group,
> +				ffe_ctl.search_start, num_bytes, empty_size,
> +				&ffe_ctl.max_extent_size);
>   		/*
>   		 * If we didn't find a chunk, and we haven't failed on this
>   		 * block group before, and this block group is in the middle of
>   		 * caching and we are ok with waiting, then go ahead and wait
> -		 * for progress to be made, and set failed_alloc to true.
> +		 * for progress to be made, and set ffe_ctl.retry_unclustered to
> +		 * true.
>   		 *
> -		 * If failed_alloc is true then we've already waited on this
> -		 * block group once and should move on to the next block group.
> +		 * If ffe_ctl.retry_unclustered is true then we've already
> +		 * waited on this block group once and should move on to the
> +		 * next block group.
>   		 */
> -		if (!offset && !failed_alloc && !cached &&
> -		    loop > LOOP_CACHING_NOWAIT) {
> +		if (!ffe_ctl.found_offset && !ffe_ctl.retry_unclustered &&
> +		    !ffe_ctl.cached && ffe_ctl.loop > LOOP_CACHING_NOWAIT) {
>   			wait_block_group_cache_progress(block_group,
>   						num_bytes + empty_size);
> -			failed_alloc = true;
> +			ffe_ctl.retry_unclustered = true;
>   			goto have_block_group;
> -		} else if (!offset) {
> +		} else if (!ffe_ctl.found_offset) {
>   			goto loop;
>   		}
>   checks:
> -		search_start = round_up(offset, fs_info->stripesize);
> +		ffe_ctl.search_start = round_up(ffe_ctl.found_offset,
> +					     fs_info->stripesize);
>   
>   		/* move on to the next group */
> -		if (search_start + num_bytes >
> +		if (ffe_ctl.search_start + num_bytes >
>   		    block_group->key.objectid + block_group->key.offset) {
> -			btrfs_add_free_space(block_group, offset, num_bytes);
> +			btrfs_add_free_space(block_group, ffe_ctl.found_offset,
> +					     num_bytes);
>   			goto loop;
>   		}
>   
> -		if (offset < search_start)
> -			btrfs_add_free_space(block_group, offset,
> -					     search_start - offset);
> +		if (ffe_ctl.found_offset < ffe_ctl.search_start)
> +			btrfs_add_free_space(block_group, ffe_ctl.found_offset,
> +				ffe_ctl.search_start - ffe_ctl.found_offset);
>   
>   		ret = btrfs_add_reserved_bytes(block_group, ram_bytes,
>   				num_bytes, delalloc);
>   		if (ret == -EAGAIN) {
> -			btrfs_add_free_space(block_group, offset, num_bytes);
> +			btrfs_add_free_space(block_group, ffe_ctl.found_offset,
> +					     num_bytes);
>   			goto loop;
>   		}
>   		btrfs_inc_block_group_reservations(block_group);
>   
>   		/* we are all good, lets return */
> -		ins->objectid = search_start;
> +		ins->objectid = ffe_ctl.search_start;
>   		ins->offset = num_bytes;
>   
> -		trace_btrfs_reserve_extent(block_group, search_start, num_bytes);
> +		trace_btrfs_reserve_extent(block_group, ffe_ctl.search_start,
> +					   num_bytes);
>   		btrfs_release_block_group(block_group, delalloc);
>   		break;
>   loop:
> -		failed_cluster_refill = false;
> -		failed_alloc = false;
> +		ffe_ctl.retry_clustered = false;
> +		ffe_ctl.retry_unclustered = false;
>   		BUG_ON(btrfs_bg_flags_to_raid_index(block_group->flags) !=
> -		       index);
> +		       ffe_ctl.index);
>   		btrfs_release_block_group(block_group, delalloc);
>   		cond_resched();
>   	}
>   	up_read(&space_info->groups_sem);
>   
> -	if ((loop == LOOP_CACHING_NOWAIT) && have_caching_bg
> -		&& !orig_have_caching_bg)
> -		orig_have_caching_bg = true;
> +	if ((ffe_ctl.loop == LOOP_CACHING_NOWAIT) && ffe_ctl.have_caching_bg
> +		&& !ffe_ctl.orig_have_caching_bg)
> +		ffe_ctl.orig_have_caching_bg = true;
>   
> -	if (!ins->objectid && loop >= LOOP_CACHING_WAIT && have_caching_bg)
> +	if (!ins->objectid && ffe_ctl.loop >= LOOP_CACHING_WAIT &&
> +	    ffe_ctl.have_caching_bg)
>   		goto search;
>   
> -	if (!ins->objectid && ++index < BTRFS_NR_RAID_TYPES)
> +	if (!ins->objectid && ++ffe_ctl.index < BTRFS_NR_RAID_TYPES)
>   		goto search;
>   
>   	/*
> @@ -7615,23 +7684,23 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   	 * LOOP_NO_EMPTY_SIZE, set empty_size and empty_cluster to 0 and try
>   	 *			again
>   	 */
> -	if (!ins->objectid && loop < LOOP_NO_EMPTY_SIZE) {
> -		index = 0;
> -		if (loop == LOOP_CACHING_NOWAIT) {
> +	if (!ins->objectid && ffe_ctl.loop < LOOP_NO_EMPTY_SIZE) {
> +		ffe_ctl.index = 0;
> +		if (ffe_ctl.loop == LOOP_CACHING_NOWAIT) {
>   			/*
>   			 * We want to skip the LOOP_CACHING_WAIT step if we
>   			 * don't have any uncached bgs and we've already done a
>   			 * full search through.
>   			 */
> -			if (orig_have_caching_bg || !full_search)
> -				loop = LOOP_CACHING_WAIT;
> +			if (ffe_ctl.orig_have_caching_bg || !full_search)
> +				ffe_ctl.loop = LOOP_CACHING_WAIT;
>   			else
> -				loop = LOOP_ALLOC_CHUNK;
> +				ffe_ctl.loop = LOOP_ALLOC_CHUNK;
>   		} else {
> -			loop++;
> +			ffe_ctl.loop++;
>   		}
>   
> -		if (loop == LOOP_ALLOC_CHUNK) {
> +		if (ffe_ctl.loop == LOOP_ALLOC_CHUNK) {
>   			struct btrfs_trans_handle *trans;
>   			int exist = 0;
>   
> @@ -7654,7 +7723,7 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   			 * case.
>   			 */
>   			if (ret == -ENOSPC)
> -				loop = LOOP_NO_EMPTY_SIZE;
> +				ffe_ctl.loop = LOOP_NO_EMPTY_SIZE;
>   
>   			/*
>   			 * Do not bail out on ENOSPC since we
> @@ -7670,18 +7739,18 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   				goto out;
>   		}
>   
> -		if (loop == LOOP_NO_EMPTY_SIZE) {
> +		if (ffe_ctl.loop == LOOP_NO_EMPTY_SIZE) {
>   			/*
>   			 * Don't loop again if we already have no empty_size and
>   			 * no empty_cluster.
>   			 */
>   			if (empty_size == 0 &&
> -			    empty_cluster == 0) {
> +			    ffe_ctl.empty_cluster == 0) {
>   				ret = -ENOSPC;
>   				goto out;
>   			}
>   			empty_size = 0;
> -			empty_cluster = 0;
> +			ffe_ctl.empty_cluster = 0;
>   		}
>   
>   		goto search;
> @@ -7698,9 +7767,9 @@ static noinline int find_free_extent(struct btrfs_fs_info *fs_info,
>   out:
>   	if (ret == -ENOSPC) {
>   		spin_lock(&space_info->lock);
> -		space_info->max_extent_size = max_extent_size;
> +		space_info->max_extent_size = ffe_ctl.max_extent_size;
>   		spin_unlock(&space_info->lock);
> -		ins->offset = max_extent_size;
> +		ins->offset = ffe_ctl.max_extent_size;
>   	}
>   	return ret;
>   }
> 

Re: [PATCH v3 4/4] btrfs: Refactor find_free_extent() loops update into find_free_extent_update_loop()

[Josef Bacik]

On Fri, Oct 12, 2018 at 02:18:19PM +0800, Qu Wenruo wrote:
> We have a complex loop design for find_free_extent(), that has different
> behavior for each loop, some even includes new chunk allocation.
> 
> Instead of putting such a long code into find_free_extent() and makes it
> harder to read, just extract them into find_free_extent_update_loop().
> 
> With all the cleanups, the main find_free_extent() should be pretty
> barebone:
> 
> find_free_extent()
> |- Iterate through all block groups
> |  |- Get a valid block group
> |  |- Try to do clustered allocation in that block group
> |  |- Try to do unclustered allocation in that block group
> |  |- Check if the result is valid
> |  |  |- If valid, then exit
> |  |- Jump to next block group
> |
> |- Push harder to find free extents
>    |- If not found, re-iterate all block groups
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>
> Reviewed-by: Su Yue <suy.fnst@cn.fujitsu.com>
> ---
>  fs/btrfs/extent-tree.c | 217 ++++++++++++++++++++++-------------------
>  1 file changed, 117 insertions(+), 100 deletions(-)
> 
> diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
> index e6bfa91af41c..938569d2c583 100644
> --- a/fs/btrfs/extent-tree.c
> +++ b/fs/btrfs/extent-tree.c
> @@ -7236,7 +7236,9 @@ struct find_free_extent_ctl {
>  	/* RAID index, converted from flags */
>  	int index;
>  
> -	/* Current loop number */
> +	/*
> +	 * Current loop number, check find_free_extent_update_loop() for details
> +	 */
>  	int loop;
>  
>  	/*
> @@ -7433,6 +7435,117 @@ static int find_free_extent_unclustered(struct btrfs_block_group_cache *bg,
>  	return 0;
>  }
>  
> +/*
> + * Return >0 means caller needs to re-search for free extent
> + * Return 0 means we have the needed free extent.
> + * Return <0 means we failed to locate any free extent.
> + */
> +static int find_free_extent_update_loop(struct btrfs_fs_info *fs_info,
> +					struct btrfs_free_cluster *last_ptr,
> +					struct btrfs_key *ins,
> +					struct find_free_extent_ctl *ffe_ctl,
> +					int full_search, bool use_cluster)
> +{
> +	struct btrfs_root *root = fs_info->extent_root;
> +	int ret;
> +
> +	if ((ffe_ctl->loop == LOOP_CACHING_NOWAIT) &&
> +	    ffe_ctl->have_caching_bg && !ffe_ctl->orig_have_caching_bg)
> +		ffe_ctl->orig_have_caching_bg = true;
> +
> +	if (!ins->objectid && ffe_ctl->loop >= LOOP_CACHING_WAIT &&
> +	     ffe_ctl->have_caching_bg)
> +		return 1;
> +
> +	if (!ins->objectid && ++(ffe_ctl->index) < BTRFS_NR_RAID_TYPES)
> +		return 1;
> +
> +	/*
> +	 * LOOP_CACHING_NOWAIT, search partially cached block groups, kicking
> +	 *			caching kthreads as we move along
> +	 * LOOP_CACHING_WAIT, search everything, and wait if our bg is caching
> +	 * LOOP_ALLOC_CHUNK, force a chunk allocation and try again
> +	 * LOOP_NO_EMPTY_SIZE, set empty_size and empty_cluster to 0 and try
> +	 *			again
> +	 */
> +	if (!ins->objectid && ffe_ctl->loop < LOOP_NO_EMPTY_SIZE) {
> +		ffe_ctl->index = 0;
> +		if (ffe_ctl->loop == LOOP_CACHING_NOWAIT) {
> +			/*
> +			 * We want to skip the LOOP_CACHING_WAIT step if we
> +			 * don't have any uncached bgs and we've already done a
> +			 * full search through.
> +			 */
> +			if (ffe_ctl->orig_have_caching_bg || !full_search)
> +				ffe_ctl->loop = LOOP_CACHING_WAIT;
> +			else
> +				ffe_ctl->loop = LOOP_ALLOC_CHUNK;
> +		} else {
> +			ffe_ctl->loop++;
> +		}
> +
> +		if (ffe_ctl->loop == LOOP_ALLOC_CHUNK) {
> +			struct btrfs_trans_handle *trans;
> +			int exist = 0;
> +
> +			trans = current->journal_info;
> +			if (trans)
> +				exist = 1;
> +			else
> +				trans = btrfs_join_transaction(root);
> +
> +			if (IS_ERR(trans)) {
> +				ret = PTR_ERR(trans);
> +				return ret;
> +			}
> +
> +			ret = do_chunk_alloc(trans, ffe_ctl->flags,
> +					     CHUNK_ALLOC_FORCE);
> +
> +			/*
> +			 * If we can't allocate a new chunk we've already looped
> +			 * through at least once, move on to the NO_EMPTY_SIZE
> +			 * case.
> +			 */
> +			if (ret == -ENOSPC)
> +				ffe_ctl->loop = LOOP_NO_EMPTY_SIZE;
> +
> +			/* Do not bail out on ENOSPC since we can do more. */
> +			if (ret < 0 && ret != -ENOSPC)
> +				btrfs_abort_transaction(trans, ret);
> +			else
> +				ret = 0;
> +			if (!exist)
> +				btrfs_end_transaction(trans);
> +			if (ret)
> +				return ret;
> +		}
> +
> +		if (ffe_ctl->loop == LOOP_NO_EMPTY_SIZE) {
> +			/*
> +			 * Don't loop again if we already have no empty_size and
> +			 * no empty_cluster.
> +			 */
> +			if (ffe_ctl->empty_size == 0 &&
> +			    ffe_ctl->empty_cluster == 0)
> +				return -ENOSPC;
> +			ffe_ctl->empty_size = 0;
> +			ffe_ctl->empty_cluster = 0;
> +		}
> +		return 1;
> +	} else if (!ins->objectid) {
> +		ret = -ENOSPC;
> +	} else if (ins->objectid) {
> +		if (!use_cluster && last_ptr) {
> +			spin_lock(&last_ptr->lock);
> +			last_ptr->window_start = ins->objectid;
> +			spin_unlock(&last_ptr->lock);
> +		}
> +		ret = 0;
> +	}
> +	return ret;
> +}

Rework this so the

if (ins->objectid)
	blah

is the first thing, that way you don't have to do the

if (!ins->objectid && <other things>)

for all the other if statements here.  The fast path should be the first thing,
then we can deal with all of the other crap last.  Thanks,

Josef

Re: [PATCH v3 1/4] btrfs: Introduce find_free_extent_ctl structure for later rework

[Josef Bacik]

On Fri, Oct 12, 2018 at 02:18:16PM +0800, Qu Wenruo wrote:
> Instead of tons of different local variables in find_free_extent(),
> extract them into find_free_extent_ctl structure, and add better
> explanation for them.
> 
> Some modification may looks redundant, but will later greatly simplify
> function parameter list during find_free_extent() refactor.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>

Reviewed-by: Josef Bacik <josef@toxicpanda.com>

Thanks,

Josef

Re: [PATCH v3 2/4] btrfs: Refactor clustered extent allocation into find_free_extent_clustered()

[Josef Bacik]

On Fri, Oct 12, 2018 at 02:18:17PM +0800, Qu Wenruo wrote:
> We have two main methods to find free extents inside a block group:
> 1) clustered allocation
> 2) unclustered allocation
> 
> This patch will extract the clustered allocation into
> find_free_extent_clustered() to make it a little easier to read.
> 
> Instead of jumping between different labels in find_free_extent(), the
> helper function will use return value to indicate different behavior.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>
> Reviewed-by: Su Yue <suy.fnst@cn.fujitsu.com>

Reviewed-by: Josef Bacik <josef@toxicpanda.com>

Thanks,

Josef

Re: [PATCH v3 3/4] btrfs: Refactor unclustered extent allocation into find_free_extent_unclustered()

[Josef Bacik]

On Fri, Oct 12, 2018 at 02:18:18PM +0800, Qu Wenruo wrote:
> This patch will extract unclsutered extent allocation code into
> find_free_extent_unclustered().
> 
> And this helper function will use return value to indicate what to do
> next.
> 
> This should make find_free_extent() a little easier to read.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>
> Reviewed-by: Su Yue <suy.fnst@cn.fujitsu.com>

Reviewed-by: Josef Bacik <josef@toxicpanda.com>

Thanks,

Josef

Re: [PATCH v3 4/4] btrfs: Refactor find_free_extent() loops update into find_free_extent_update_loop()

[Qu Wenruo]

[-- Attachment #1.1: Type: text/plain, Size: 5682 bytes --]



On 2018/10/12 下午9:52, Josef Bacik wrote:
> On Fri, Oct 12, 2018 at 02:18:19PM +0800, Qu Wenruo wrote:
>> We have a complex loop design for find_free_extent(), that has different
>> behavior for each loop, some even includes new chunk allocation.
>>
>> Instead of putting such a long code into find_free_extent() and makes it
>> harder to read, just extract them into find_free_extent_update_loop().
>>
>> With all the cleanups, the main find_free_extent() should be pretty
>> barebone:
>>
>> find_free_extent()
>> |- Iterate through all block groups
>> |  |- Get a valid block group
>> |  |- Try to do clustered allocation in that block group
>> |  |- Try to do unclustered allocation in that block group
>> |  |- Check if the result is valid
>> |  |  |- If valid, then exit
>> |  |- Jump to next block group
>> |
>> |- Push harder to find free extents
>>    |- If not found, re-iterate all block groups
>>
>> Signed-off-by: Qu Wenruo <wqu@suse.com>
>> Reviewed-by: Su Yue <suy.fnst@cn.fujitsu.com>
>> ---
>>  fs/btrfs/extent-tree.c | 217 ++++++++++++++++++++++-------------------
>>  1 file changed, 117 insertions(+), 100 deletions(-)
>>
>> diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
>> index e6bfa91af41c..938569d2c583 100644
>> --- a/fs/btrfs/extent-tree.c
>> +++ b/fs/btrfs/extent-tree.c
>> @@ -7236,7 +7236,9 @@ struct find_free_extent_ctl {
>>  	/* RAID index, converted from flags */
>>  	int index;
>>  
>> -	/* Current loop number */
>> +	/*
>> +	 * Current loop number, check find_free_extent_update_loop() for details
>> +	 */
>>  	int loop;
>>  
>>  	/*
>> @@ -7433,6 +7435,117 @@ static int find_free_extent_unclustered(struct btrfs_block_group_cache *bg,
>>  	return 0;
>>  }
>>  
>> +/*
>> + * Return >0 means caller needs to re-search for free extent
>> + * Return 0 means we have the needed free extent.
>> + * Return <0 means we failed to locate any free extent.
>> + */
>> +static int find_free_extent_update_loop(struct btrfs_fs_info *fs_info,
>> +					struct btrfs_free_cluster *last_ptr,
>> +					struct btrfs_key *ins,
>> +					struct find_free_extent_ctl *ffe_ctl,
>> +					int full_search, bool use_cluster)
>> +{
>> +	struct btrfs_root *root = fs_info->extent_root;
>> +	int ret;
>> +
>> +	if ((ffe_ctl->loop == LOOP_CACHING_NOWAIT) &&
>> +	    ffe_ctl->have_caching_bg && !ffe_ctl->orig_have_caching_bg)
>> +		ffe_ctl->orig_have_caching_bg = true;
>> +
>> +	if (!ins->objectid && ffe_ctl->loop >= LOOP_CACHING_WAIT &&
>> +	     ffe_ctl->have_caching_bg)
>> +		return 1;
>> +
>> +	if (!ins->objectid && ++(ffe_ctl->index) < BTRFS_NR_RAID_TYPES)
>> +		return 1;
>> +
>> +	/*
>> +	 * LOOP_CACHING_NOWAIT, search partially cached block groups, kicking
>> +	 *			caching kthreads as we move along
>> +	 * LOOP_CACHING_WAIT, search everything, and wait if our bg is caching
>> +	 * LOOP_ALLOC_CHUNK, force a chunk allocation and try again
>> +	 * LOOP_NO_EMPTY_SIZE, set empty_size and empty_cluster to 0 and try
>> +	 *			again
>> +	 */
>> +	if (!ins->objectid && ffe_ctl->loop < LOOP_NO_EMPTY_SIZE) {
>> +		ffe_ctl->index = 0;
>> +		if (ffe_ctl->loop == LOOP_CACHING_NOWAIT) {
>> +			/*
>> +			 * We want to skip the LOOP_CACHING_WAIT step if we
>> +			 * don't have any uncached bgs and we've already done a
>> +			 * full search through.
>> +			 */
>> +			if (ffe_ctl->orig_have_caching_bg || !full_search)
>> +				ffe_ctl->loop = LOOP_CACHING_WAIT;
>> +			else
>> +				ffe_ctl->loop = LOOP_ALLOC_CHUNK;
>> +		} else {
>> +			ffe_ctl->loop++;
>> +		}
>> +
>> +		if (ffe_ctl->loop == LOOP_ALLOC_CHUNK) {
>> +			struct btrfs_trans_handle *trans;
>> +			int exist = 0;
>> +
>> +			trans = current->journal_info;
>> +			if (trans)
>> +				exist = 1;
>> +			else
>> +				trans = btrfs_join_transaction(root);
>> +
>> +			if (IS_ERR(trans)) {
>> +				ret = PTR_ERR(trans);
>> +				return ret;
>> +			}
>> +
>> +			ret = do_chunk_alloc(trans, ffe_ctl->flags,
>> +					     CHUNK_ALLOC_FORCE);
>> +
>> +			/*
>> +			 * If we can't allocate a new chunk we've already looped
>> +			 * through at least once, move on to the NO_EMPTY_SIZE
>> +			 * case.
>> +			 */
>> +			if (ret == -ENOSPC)
>> +				ffe_ctl->loop = LOOP_NO_EMPTY_SIZE;
>> +
>> +			/* Do not bail out on ENOSPC since we can do more. */
>> +			if (ret < 0 && ret != -ENOSPC)
>> +				btrfs_abort_transaction(trans, ret);
>> +			else
>> +				ret = 0;
>> +			if (!exist)
>> +				btrfs_end_transaction(trans);
>> +			if (ret)
>> +				return ret;
>> +		}
>> +
>> +		if (ffe_ctl->loop == LOOP_NO_EMPTY_SIZE) {
>> +			/*
>> +			 * Don't loop again if we already have no empty_size and
>> +			 * no empty_cluster.
>> +			 */
>> +			if (ffe_ctl->empty_size == 0 &&
>> +			    ffe_ctl->empty_cluster == 0)
>> +				return -ENOSPC;
>> +			ffe_ctl->empty_size = 0;
>> +			ffe_ctl->empty_cluster = 0;
>> +		}
>> +		return 1;
>> +	} else if (!ins->objectid) {
>> +		ret = -ENOSPC;
>> +	} else if (ins->objectid) {
>> +		if (!use_cluster && last_ptr) {
>> +			spin_lock(&last_ptr->lock);
>> +			last_ptr->window_start = ins->objectid;
>> +			spin_unlock(&last_ptr->lock);
>> +		}
>> +		ret = 0;
>> +	}
>> +	return ret;
>> +}
> 
> Rework this so the
> 
> if (ins->objectid)
> 	blah
> 
> is the first thing, that way you don't have to do the
> 
> if (!ins->objectid && <other things>)
> 
> for all the other if statements here.  The fast path should be the first thing,
> then we can deal with all of the other crap last.  Thanks,

Indeed, the ENOSPC should be in the last else branch.

Thanks,
Qu

> 
> Josef
> 


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]