From efca42cb6bfea91b57ea9ec21f067fe360209d46 Mon Sep 17 00:00:00 2001 From: Zygo Blaxell Date: Sun, 16 Aug 2026 03:54:18 -0400 Subject: [PATCH] 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. Assisted-by: Claude:claude-fable-5 --- fs/btrfs/block-group.c | 1 + fs/btrfs/block-group.h | 12 ++++++++++++ fs/btrfs/free-space-cache.c | 37 ++++++++++++++++++++++++++++++++++++- 3 files changed, 49 insertions(+), 1 deletion(-) diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c index 8e15181d99b3d..ef883040d8b9d 100644 --- a/fs/btrfs/block-group.c +++ b/fs/btrfs/block-group.c @@ -4355,6 +4355,7 @@ static struct btrfs_block_group *btrfs_create_block_group_cache( cache->fs_info = fs_info; cache->full_stripe_len = btrfs_full_stripe_len(fs_info, start); + cache->max_claimable_run = (u64)-1; cache->discard_index = BTRFS_DISCARD_INDEX_UNUSED; diff --git a/fs/btrfs/block-group.h b/fs/btrfs/block-group.h index 38c14cbd08acf..cc83402c46ad5 100644 --- a/fs/btrfs/block-group.h +++ b/fs/btrfs/block-group.h @@ -292,6 +292,18 @@ struct btrfs_block_group { * write()-time ENOSPC), corrected upward by the commit rescan. */ u64 stripe_claimable; + /* + * Upper bound on the longest run btrfs_claim_free_stripe_run() can + * find, learned from actual scans: (u64)-1 means unknown, 0 means an + * exhaustive scan proved there is no claimable run. Claims fail in + * O(1) while the bound is below one full stripe; adding free space + * resets it to unknown. Unlike stripe_claimable (an accounting + * estimate), this caches what the scan itself proved, so it stays + * correct even when the accounting errs high. Protected by + * free_space_ctl->tree_lock; only meaningful once the block group is + * fully cached. + */ + u64 max_claimable_run; bool stripe_unusable_ready; /* diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c index c6011fdbfccd0..c5c1b0349efe2 100644 --- a/fs/btrfs/free-space-cache.c +++ b/fs/btrfs/free-space-cache.c @@ -2651,6 +2651,12 @@ static int __btrfs_add_free_space(struct btrfs_block_group *block_group, spin_lock(&ctl->tree_lock); + /* + * New free space may merge into a claimable stripe run; forget any + * cached "no claimable run" verdict (see btrfs_claim_free_stripe_run()). + */ + block_group->max_claimable_run = (u64)-1; + if (try_merge_free_space(ctl, info, true)) goto link; @@ -3905,6 +3911,26 @@ int btrfs_claim_free_stripe_run(struct btrfs_block_group *block_group, spin_lock(&ctl->tree_lock); + /* + * Fail fast without scanning when a previous exhaustive scan proved + * this block group has no claimable run (max_claimable_run == 0, set + * below): only adding free space can create one, and + * __btrfs_add_free_space() resets the bound when it does. Also skip + * when the total free space cannot possibly hold one full stripe. + * Without this, a fragmented block group costs a full O(size) scan + * under ctl->tree_lock for EVERY failed claim - one per small + * allocation - which starves the delalloc workers at 100% CPU on + * large aged filesystems. Only trust the bound once the block group + * is fully cached: cache loading links entries directly, bypassing + * __btrfs_add_free_space(), so the reset would be missed. + */ + if (btrfs_block_group_done(block_group) && + (block_group->max_claimable_run < fsl || + ctl->free_space < fsl)) { + spin_unlock(&ctl->tree_lock); + return -ENOSPC; + } + entry = find_free_stripe_run(block_group, want_bytes, &run_start, &run_len); if (!entry) { /* @@ -3919,8 +3945,17 @@ int btrfs_claim_free_stripe_run(struct btrfs_block_group *block_group, return -ENOMEM; spin_lock(&ctl->tree_lock); if (!find_free_stripe_run_slow(block_group, want_bytes, - &run_start, &run_len)) + &run_start, &run_len)) { + /* + * The exhaustive scan found no claimable run at all + * (the slow path accepts any run of at least one full + * stripe). Cache that verdict so subsequent claims + * fail in O(1) until free space is added. + */ + if (btrfs_block_group_done(block_group)) + block_group->max_claimable_run = 0; goto out; + } spare_used = claim_stripe_run_pieces(block_group, run_start, run_len, spare); stripe_claimable_mod(block_group, -(s64)run_len); -- 2.53.0