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.
projects / linux / commit