btrfs: stripe_alloc: cache a failed stripe run scan per block group
On a large aged filesystem (85 TiB, mostly legacy pre-stripe_alloc data,
heavily fragmented free space), the delalloc workers spin at 100% CPU
while commits crawl at KiB/s. NMI backtraces put the time in
btrfs_claim_free_stripe_run() called from btrfs_alloc_from_open_stripe()
for every small compressed extent allocation.
The cost is in find_free_stripe_run_slow(): when the single-entry fast
path misses (always, on fragmented block groups), the slow path walks
candidate stripes from the START of the block group, doing an rbtree
lookup per free-space piece, all under ctl->tree_lock. When the block
group has no claimable run at all - the common case for block groups
filled with legacy data - the scan traverses the entire block group,
returns -ENOSPC, and remembers nothing: the next 4K allocation repeats
the whole scan. Per-allocation cost is O(block group size) in the
fragmented worst case, multiplied by every block group find_free_extent
visits.
The stock allocator avoids exactly this pathology by caching the largest
extent a failed search saw (max_extent_size); the stripe claim path is a
new search primitive built beside it and never inherited the idea. The
per-block-group stripe_claimable counter cannot serve this role: it is a
commit-scan-granular byte estimate that can err high (block groups where
the accounting promises claimable bytes but the scan finds no aligned,
usable run are precisely where the scan storm happens).
Add bg->max_claimable_run, an upper bound learned from the scans
themselves: (u64)-1 unknown, 0 after an exhaustive scan proved no
claimable run exists (find_free_stripe_run_slow() accepts any run of at
least one full stripe, so its failure is that proof). Claims fail in
O(1) while the bound is below one full stripe, or when total free space
in the block group is smaller than a full stripe. Adding free space
resets the bound to unknown in __btrfs_add_free_space(), which covers
all paths that can create a run: frees, unpins, and stripe run returns.
The bound is only trusted and only set once the block group is fully
cached, because cache loading links entries directly and would bypass
the reset.
projects / linux / commit