btrfs: add btrfs_claim_free_stripe_run() for stripe-exclusive allocation
Add a free space cache primitive that finds and removes a contiguous,
fully-free, stripe-aligned run of full stripes from a block group. This
is the building block for a raid56 allocation policy that never issues
sub-stripe writes into stripes containing committed data, closing the
raid56 write hole for datacow writes: because a partially-filled stripe
can never satisfy the fully-free requirement, stripes retired at commit
time become unallocatable without any persistent allocator state.
The search walks the by-size free space index (largest max contiguous
free run first) rather than the by-offset tree: an entry whose largest
contiguous free run is smaller than a full stripe cannot contain a
fully-free stripe, and every following entry is no larger, so the search
stops at the first such entry. Near-full, where the free space
degenerates into many sub-stripe holes, that is an O(1) fast fail
instead of a scan of the whole free space tree on every allocation --
the dominant cost of the known raid56 near-full allocation slowdown.
Full stripe geometry is relative to the block group start and supports
non-power-of-two stripe widths. Unaligned head and tail remainders are
returned to the free space cache with their trim state preserved. Runs
are found within a single free space entry; a fully-free stripe split
across an extent entry and a bitmap neighbour is deliberately not found,
which errs toward missing a claimable stripe, never toward claiming a
non-free byte.
The function is exercised by new sanity self-tests covering aligned and
capped claims, partial-stripe exclusion, head/tail carving, block-group-
relative geometry, bitmap entries, and non-power-of-two stripe widths.
The raid56 stripe allocation policy will be its first non-test user.
projects / linux / commit