From 70e2153302add72d442d75a9d1ec3abbb2a7f681 Mon Sep 17 00:00:00 2001 From: Zygo Blaxell Date: Tue, 28 Jul 2026 02:26:50 -0400 Subject: [PATCH] btrfs: stripe_alloc: grow the frontier run instead of stranding its tail When an allocation is larger than every open run's remainder, the allocator claims fresh fully-free stripes and opens a separate run, leaving the old run's tail behind. The banded cursors keep that tail open for a while, but a band collision or the commit eventually closes it, and the tail -- perfectly usable space that a misfit merely jumped over -- is stranded in a partially filled stripe. In a forward fill this happens at every size upshift, and measurement shows it is where nearly all of stripe_alloc's trapped space comes from: on a mixed-size fill it strands ~14% of the data written, a figure that band-granularity tuning moves by at most a tenth and commit frequency does not move at all. Grow the frontier run instead. If the freshly claimed stripes directly follow the end of an open run of the same class, extend that run to absorb them and place the allocation at the run's old tail, spilling contiguously into the new stripes. Nothing is stranded, and the extent is physically contiguous. In a forward fill the by-size claim naturally returns the stripes adjacent to the frontier, so the single frontier run just keeps growing -- the allocator packs the way the stock allocator does, while keeping stripe exclusivity: the grown stripes were claimed fully free, the run still closes at the next commit and is never reopened, so every stripe of the run is filled within one open-run lifetime. A grown run keeps its open_seq; it can only still be in a band slot if the retire walk for its window has not yet run, which the open_stripe_lock nesting at the claim site excludes from racing. Measured on a 4-device raid5 with a deterministic interleaved 4K-512K fill (trapped space via the stripe_unusable counter, byte-identical data both sides): 111.1 MiB trapped without growing, 7.2 MiB with -- a 94% reduction, and usable capacity at ENOSPC within 0.5% of the stock allocator (1561 vs 1569 MiB, vs 1421 MiB without growing). The benefit survives churn: with age-correlated deletion the grown runs' contiguous packing lets whole stripes free together, and steady-state usable capacity stays at 1486-1561 MiB versus 1284-1421 MiB without growing across correlated and adversarial small-file deletion patterns. Data integrity verified by scrub and full sha256 read-back over mixed random-content files, and trapped-space accounting still returns to zero when all files are deleted. The open-stripe selftest is updated: the misfit allocation now grows the run and lands at the run's old tail, spanning the stripe boundary, and the relocation-class case doubles as a check that a claim adjacent to another class's run never grows it. Assisted-by: Claude:claude-fable-5 --- fs/btrfs/block-group.c | 45 +++++++++++++++++++++-- fs/btrfs/tests/free-space-tests.c | 60 +++++++++++++++++-------------- 2 files changed, 76 insertions(+), 29 deletions(-) diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c index 6d44a80700a46..74358641ca04b 100644 --- a/fs/btrfs/block-group.c +++ b/fs/btrfs/block-group.c @@ -589,8 +589,11 @@ static u64 stripe_run_place(struct btrfs_block_group *bg, /* * Allocate num_bytes from the block group's open stripe run, opening a new * run via btrfs_claim_free_stripe_run() when there is none or the current - * one does not fit. The allocation counts toward the run's inflight bytes - * until btrfs_open_stripe_write_done() reports its data IO complete. + * one does not fit. If the freshly claimed stripes directly follow an open + * run of the same class, that run grows to absorb them instead (see the + * comment at the claim site). The allocation counts toward the run's + * inflight bytes until btrfs_open_stripe_write_done() reports its data IO + * complete. * * Returns 0 and sets *ret_offset, -ENOSPC if no fully-free stripe run in * this block group can satisfy the allocation, or -ENOMEM. @@ -700,6 +703,44 @@ int btrfs_alloc_from_open_stripe(struct btrfs_block_group *bg, u64 num_bytes, ret = -ENOSPC; goto out; } + /* + * Growable frontier: if the claimed region [start, start+len) directly + * follows the end of an open run of the same class, grow that run to + * absorb it and place this allocation at the run's old tail, spilling + * contiguously into the claimed stripes. Without this, an allocation + * larger than every open run's remainder would open a separate run and + * the old tail -- perfectly usable space the misfit merely jumped over + * -- would sit unfillable until a small allocation happened to find it, + * or be stranded outright when a band collision or commit closed the + * run. Growing preserves stripe exclusivity: the grown stripes were + * claimed fully free, and the run still closes at the next commit and + * is never reopened, so every stripe of the run is filled within one + * open-run lifetime. The run keeps its open_seq: it can only still be + * in a band slot if the retire walk for its window has not run, which + * this lock nesting excludes from racing us. + */ + for (band = 0; band < BTRFS_STRIPE_RUN_NR_BANDS; band++) { + struct btrfs_open_stripe_run *r = bg->open_stripe[class][band]; + + if (!r || r->end != start) + continue; + ASSERT(r->open); + bg->open_stripe[class][band] = NULL; + *ret_offset = r->offset; + r->end = start + len; + r->offset += num_bytes; + r->inflight_bytes += num_bytes; + if (r->offset == r->end) + r->open = false; /* full; drains then is freed */ + else + tail_len = stripe_run_place(bg, r, &tail_start); + spin_unlock_irqrestore(&bg->stripe_run_lock, flags); + spin_unlock(&fs_info->open_stripe_lock); + if (tail_len) + btrfs_add_free_space(bg, tail_start, tail_len); + ret = 0; + goto out; /* frees the unused new_run */ + } new_run->bg = bg; new_run->class = class; new_run->start = start; diff --git a/fs/btrfs/tests/free-space-tests.c b/fs/btrfs/tests/free-space-tests.c index 8dcc4d8aafa2e..1ee9632d7e0b6 100644 --- a/fs/btrfs/tests/free-space-tests.c +++ b/fs/btrfs/tests/free-space-tests.c @@ -1258,41 +1258,43 @@ static int test_open_stripe(struct btrfs_block_group *cache, u32 sectorsize) } /* - * A full-stripe allocation cannot fit the open run's remainder, so it - * opens a fresh stripe. With multiple cursors the old run stays open in - * its remaining-space band (its tail is not trapped); a single cursor - * would have closed it here. + * A full-stripe allocation cannot fit the open run's remainder. The + * claimed stripe #2 directly follows the run's end, so the run GROWS to + * absorb it and the allocation starts at the run's old tail, spanning + * the stripe boundary: nothing is stranded and the extent is placed at + * fsl + 4 * sectorsize, not at the fresh stripe's start. */ ret = btrfs_alloc_from_open_stripe(cache, fsl, BTRFS_STRIPE_RUN_COW, &offset, &avail); - if (ret || offset != 2 * fsl) { - test_err("misfit alloc wrong: ret %d offset %llu", ret, offset); + if (ret || offset != fsl + 4 * sectorsize) { + test_err("grown misfit alloc wrong: ret %d offset %llu", + ret, offset); ret = -EINVAL; goto out; } - /* The old run is still open, so its tail is NOT back in the cache. */ - if (test_check_exists(cache, fsl + 4 * sectorsize, + /* The grown run's new tail is open, NOT back in the free cache. */ + if (test_check_exists(cache, 2 * fsl + 4 * sectorsize, fsl - 4 * sectorsize)) { - test_err("kept-open run tail wrongly freed"); + test_err("grown run tail wrongly freed"); ret = -EINVAL; goto out; } - /* A small allocation backtracks to fill the still-open run. */ + /* A small allocation keeps filling the grown run. */ ret = btrfs_alloc_from_open_stripe(cache, sectorsize, BTRFS_STRIPE_RUN_COW, &offset, &avail); - if (ret || offset != fsl + 4 * sectorsize) { - test_err("backfill alloc wrong: ret %d offset %llu", + if (ret || offset != 2 * fsl + 4 * sectorsize) { + test_err("post-grow alloc wrong: ret %d offset %llu", ret, offset); ret = -EINVAL; goto out; } /* - * A different class never joins the cow run: it opens a fresh stripe. - * Only stripes #1 and #2 have been claimed so far (multi-cursor kept - * #1 open and backfilled it rather than claiming a new stripe for the - * small allocations), so the reloc class claims #3. + * A different class never joins -- or grows -- the cow run. The reloc + * claim of stripe #3 directly follows the cow run's end (the grown run + * covers stripes #1-#2), which is exactly the growable case within a + * class, yet the reloc allocation must open its own fresh run there. */ ret = btrfs_alloc_from_open_stripe(cache, sectorsize, BTRFS_STRIPE_RUN_RELOC, &offset, @@ -1307,7 +1309,7 @@ static int test_open_stripe(struct btrfs_block_group *cache, u32 sectorsize) ret = btrfs_alloc_from_open_stripe(cache, sectorsize, BTRFS_STRIPE_RUN_COW, &offset, &avail); - if (ret || offset != fsl + 5 * sectorsize) { + if (ret || offset != 2 * fsl + 5 * sectorsize) { test_err("cow run lost by class open: ret %d offset %llu", ret, offset); ret = -EINVAL; @@ -1318,20 +1320,23 @@ static int test_open_stripe(struct btrfs_block_group *cache, u32 sectorsize) btrfs_open_stripe_write_done(cache, fsl, 2 * sectorsize); btrfs_open_stripe_write_done(cache, fsl + 2 * sectorsize, 2 * sectorsize); - btrfs_open_stripe_write_done(cache, fsl + 4 * sectorsize, sectorsize); - btrfs_open_stripe_write_done(cache, fsl + 5 * sectorsize, sectorsize); - btrfs_open_stripe_write_done(cache, 2 * fsl, fsl); + btrfs_open_stripe_write_done(cache, fsl + 4 * sectorsize, fsl); + btrfs_open_stripe_write_done(cache, 2 * fsl + 4 * sectorsize, + sectorsize); + btrfs_open_stripe_write_done(cache, 2 * fsl + 5 * sectorsize, + sectorsize); btrfs_open_stripe_write_done(cache, 3 * fsl, sectorsize); /* * Commit-style retirement: closes every open run in every band of both * classes, returns their tails, drains (instantly, all IO reported * done) and drops the block group's membership in - * fs_info->open_stripe_bgs. The cow run filled [fsl, fsl+6*sectorsize) - * and the reloc run filled [3*fsl, 3*fsl+sectorsize); each tail returns. + * fs_info->open_stripe_bgs. The grown cow run covers stripes #1-#2 and + * filled [fsl, 2*fsl+6*sectorsize); the reloc run filled + * [3*fsl, 3*fsl+sectorsize); each tail returns. */ btrfs_retire_open_stripes(fs_info, NULL); - if (!test_check_exists(cache, fsl + 6 * sectorsize, + if (!test_check_exists(cache, 2 * fsl + 6 * sectorsize, fsl - 6 * sectorsize)) { test_err("retired cow run tail missing from free space"); ret = -EINVAL; @@ -1381,16 +1386,17 @@ static int test_open_stripe(struct btrfs_block_group *cache, u32 sectorsize) } /* - * Clean up the partial-stripe remainders: stripe #0's head, stripe #1's - * cow tail (10 sectors), and the 15-sector tails of stripes #3 (reloc), - * #4 and #5. Stripe #2 was filled completely and has no remainder. + * Clean up the partial-stripe remainders: stripe #0's head, the grown + * cow run's 10-sector tail in stripe #2, and the 15-sector tails of + * stripes #3 (reloc), #4 and #5. Stripe #1 was filled completely and + * has no remainder. */ ret = btrfs_remove_free_space(cache, sectorsize, fsl - sectorsize); if (ret) { test_err("error cleaning up head %d", ret); goto out; } - ret = btrfs_remove_free_space(cache, fsl + 6 * sectorsize, + ret = btrfs_remove_free_space(cache, 2 * fsl + 6 * sectorsize, fsl - 6 * sectorsize); if (ret) { test_err("error cleaning up tail 1 %d", ret); -- 2.53.0