Skip to contentSkip to conversation

bcachefs: update alloc cursor in early bucket allocator

PATCH In review Brian Foster 2 participants 5 messages Oct 19, 2023 – Oct 20, 2023

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 bcachefs: update alloc cursor in early bucket allocator

A recent bug report uncovered a scenario where a filesystem never runs with freespace_initialized, and therefore the user observes significantly degraded write performance by virtue of running the early bucket allocator. The associated bug aside, the primary cause of the performance drop in this particular instance is that the early bucket allocator does not update the allocation cursor. This means that every allocation walks the alloc btree from the first bucket of the associated device looking for a bucket marked as free space.

Update the early allocator code to set the alloc cursor to the prospectively allocated bucket, similar to how the freelist allocator behaves. This improves performance of the early bucket allocator dramatically (even though it should be bypassed in favor of the freelist allocator in most cases).

---

cshepherd on #bcache originally reported the early bucket allocator problem and helped chase it down to what looks like a members_v2 regression. I believe he was planning to post a patch for that one.

Brian

 fs/bcachefs/alloc_foreground.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
fs/bcachefs/alloc_foreground.c +1 -1
index 3bc4abd3d7d5..be3fc0f38c79 100644
@@ -431,7 +431,7 @@ bch2_bucket_alloc_early(struct btree_trans *trans,
 	}
 	bch2_trans_iter_exit(trans, &iter);
 
-	ca->alloc_cursor = alloc_cursor;
+	ca->alloc_cursor = IS_ERR_OR_NULL(ob) ? alloc_cursor : ob->bucket;
 
 	if (!ob && ret)
 		ob = ERR_PTR(ret);
Signature · 1 line
2.41.0
#1 lore raw
Quoted 33 lines · Brian Foster

A recent bug report uncovered a scenario where a filesystem never runs with freespace_initialized, and therefore the user observes significantly degraded write performance by virtue of running the early bucket allocator. The associated bug aside, the primary cause of the performance drop in this particular instance is that the early bucket allocator does not update the allocation cursor. This means that every allocation walks the alloc btree from the first bucket of the associated device looking for a bucket marked as free space.

Update the early allocator code to set the alloc cursor to the prospectively allocated bucket, similar to how the freelist allocator behaves. This improves performance of the early bucket allocator dramatically (even though it should be bypassed in favor of the freelist allocator in most cases).

---

cshepherd on #bcache originally reported the early bucket allocator problem and helped chase it down to what looks like a members_v2 regression. I believe he was planning to post a patch for that one.

Brian

 fs/bcachefs/alloc_foreground.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
fs/bcachefs/alloc_foreground.c +0 -0
index 3bc4abd3d7d5..be3fc0f38c79 100644

fs/bcachefs/alloc_foreground.c bch2_bucket_alloc_early(struct btree_trans *trans, · line 434

Quoted 5 lines
fs/bcachefs/alloc_foreground.c +1 -1
@@ -431,7 +431,7 @@ bch2_bucket_alloc_early(struct btree_trans *trans,
 	}
 	bch2_trans_iter_exit(trans, &iter);
 
-	ca->alloc_cursor = alloc_cursor;
+	ca->alloc_cursor = IS_ERR_OR_NULL(ob) ? alloc_cursor : ob->bucket;

Oh, this code is broken. The local alloc_cursor never gets updated, and it needs to for where we check if we need to loop around.

The proper fix would be to add

  alloc_cursor = iter.pos.offset;

before the line you changed

#2 lore raw
Quoted 37 lines · Kent Overstreet
Quoted 36 lines · Brian Foster

A recent bug report uncovered a scenario where a filesystem never runs with freespace_initialized, and therefore the user observes significantly degraded write performance by virtue of running the early bucket allocator. The associated bug aside, the primary cause of the performance drop in this particular instance is that the early bucket allocator does not update the allocation cursor. This means that every allocation walks the alloc btree from the first bucket of the associated device looking for a bucket marked as free space.

Update the early allocator code to set the alloc cursor to the prospectively allocated bucket, similar to how the freelist allocator behaves. This improves performance of the early bucket allocator dramatically (even though it should be bypassed in favor of the freelist allocator in most cases).

---

cshepherd on #bcache originally reported the early bucket allocator problem and helped chase it down to what looks like a members_v2 regression. I believe he was planning to post a patch for that one.

Brian

 fs/bcachefs/alloc_foreground.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
fs/bcachefs/alloc_foreground.c +0 -0
index 3bc4abd3d7d5..be3fc0f38c79 100644
@@ -431,7 +431,7 @@ bch2_bucket_alloc_early(struct btree_trans *trans,
 	}
 	bch2_trans_iter_exit(trans, &iter);
 
Quoted 6 lines

fs/bcachefs/alloc_foreground.c bch2_bucket_alloc_early(struct btree_trans *trans, · line 434

Quoted 2 lines
fs/bcachefs/alloc_foreground.c +1 -1
-	ca->alloc_cursor = alloc_cursor;
+	ca->alloc_cursor = IS_ERR_OR_NULL(ob) ? alloc_cursor : ob->bucket;

Oh, this code is broken. The local alloc_cursor never gets updated, and it needs to for where we check if we need to loop around.

Ah, good point.

Quoted 6 lines

The proper fix would be to add

  alloc_cursor = iter.pos.offset;

before the line you changed

Thanks. I'll give that a whirl.

BTW, should this code be protected from no free space situations at a higher level, or should we consider a max retry count or something? I want to be cautious about things like prospective livelocks (particularly if this path is less common) if this retry was effectively dead code due to not updating alloc_cursor.

Brian

#3 lore raw
Quoted 5 lines · Brian Foster

BTW, should this code be protected from no free space situations at a higher level, or should we consider a max retry count or something? I want to be cautious about things like prospective livelocks (particularly if this path is less common) if this retry was effectively dead code due to not updating alloc_cursor.

It should be limiting itself to a single retry already: on retry, we set alloc_cursor = alloc_start, so we won't retry again. Just make sure that still works :)

#4 lore raw
Quoted 11 lines · Kent Overstreet
Quoted 5 lines · Brian Foster

BTW, should this code be protected from no free space situations at a higher level, or should we consider a max retry count or something? I want to be cautious about things like prospective livelocks (particularly if this path is less common) if this retry was effectively dead code due to not updating alloc_cursor.

It should be limiting itself to a single retry already: on retry, we set alloc_cursor = alloc_start, so we won't retry again. Just make sure that still works :)

I don't think that actually works due to the whole alloc_cursor not updating thing, but regardless the "single retry from the beginning" logic makes a lot more sense to me. With that, here's what I'm currently playing with:

fs/bcachefs/alloc_foreground.c +6 -4
index 3bc4abd3d7d5..41a7bf24c440 100644
@@ -402,8 +402,9 @@ bch2_bucket_alloc_early(struct btree_trans *trans,
 	struct btree_iter iter;
 	struct bkey_s_c k;
 	struct open_bucket *ob = NULL;
-	u64 alloc_start = max_t(u64, ca->mi.first_bucket, ca->new_fs_bucket_idx);
-	u64 alloc_cursor = max(alloc_start, READ_ONCE(ca->alloc_cursor));
+	u64 first_bucket = max_t(u64, ca->mi.first_bucket, ca->new_fs_bucket_idx);
+	u64 alloc_start = max(first_bucket, READ_ONCE(ca->alloc_cursor));
+	u64 alloc_cursor = alloc_start;
 	int ret;
 again:
 	for_each_btree_key_norestart(trans, iter, BTREE_ID_alloc, POS(ca->dev_idx, alloc_cursor),
@@ -431,13 +432,14 @@ bch2_bucket_alloc_early(struct btree_trans *trans,
 	}
 	bch2_trans_iter_exit(trans, &iter);
 
+	alloc_cursor = iter.pos.offset;
 	ca->alloc_cursor = alloc_cursor;
 
 	if (!ob && ret)
 		ob = ERR_PTR(ret);
 
-	if (!ob && alloc_cursor > alloc_start) {
-		alloc_cursor = alloc_start;
+	if (!ob && alloc_start > first_bucket) {
+		alloc_cursor = alloc_start = first_bucket;
 		goto again;
 	}