btrfs: stripe_alloc: keep an open run per size band to trap less
A single open stripe run per class forces every allocation that does not
fit the current run's remainder to close that run -- trapping its
unallocated tail in a now partially filled stripe -- and claim a fresh
fully-free stripe. A workload that interleaves small and large extents
(the common case) therefore strands a tail on every size change, even
though a later small allocation could have filled it.
Keep one open run per power-of-two band of remaining free space instead
(band k holds a run with remaining in [2^k, 2^(k+1)) sectors), per class.
An allocation takes the run in the smallest band that still fits --
segregated best fit -- so a small write lands in an already-open, nearly
full stripe rather than opening a new one, while a large write that no
open run can hold opens a fresh stripe and leaves the smaller runs open
for the small writes that do fit them. After each allocation the run is
re-placed into the band its new remainder falls in; when two runs collide
in a band the fuller one is kept -- it can serve larger future
allocations, and closing it would trap more -- and the other is closed,
its tail returned to the free space cache.
16 bands cover a full stripe of up to 2^16 sectors, far more than any
raid56 geometry (nr_data_stripes * stripe_len / sectorsize is 158 sectors
at 10 data stripes and a 64K stripe). Commit-time retirement and the
read-only / removal paths now walk every band of every class; only the
bg->open_stripe[][] slots can ever hold an open run, so one pass still
suffices, and the obsolete single-slot assertions are dropped.
This does not touch the write-hole guarantee: every run is still a
contiguous fill of fully-free stripes, closed at commit and never
reopened. It only changes which open run an allocation joins, reducing
the free space trapped in partial stripes -- and thus stripe_unusable --
for mixed-size workloads.
The open-stripe selftest is rewritten to the multi-cursor contract: a
misfit allocation now keeps the old run open (its tail is not returned to
the cache) and a later small allocation backfills it, so fewer stripes are
claimed before the free space is exhausted.
projects / linux / commit