Re: [PATCH v10 1/2] gpu/buddy: replace dual-tree/force_merge with decoupled dirty tracker

On 19/08/2026 11:42, Arunpravin Paneer Selvam wrote:
> The current buddy allocator maintains separate clear_tree[] and
> dirty_tree[] rbtrees per order, preventing coalescing between cleared
> and dirty buddies. Under mixed workloads, this creates a merge barrier:
> adjacent buddies frequently end up split across trees, forcing reliance
> on __force_merge() during allocation.
> 
> __force_merge() performs an O(N x max_order) scan under the VRAM manager
> lock, leading to allocation stalls and failures for large contiguous
> requests even when sufficient total free memory is available.
> 
> Solution
> 
> Replace the dual-tree design with:
> - A single free_tree[order] rbtree for dirty and mixed free blocks
>    (fully cleared free blocks float outside this tree)
> - A lightweight out-of-band dirty tracker (gpu_dirty_tracker)
> 
> Fully cleared free blocks are tracked outside the buddy trees using an
> augmented interval rbtree, enabling O(log E) lookup of the largest
> cleared extents.
> 
> Buddy coalescing is now unconditional in __gpu_buddy_free(), regardless
> of clear/dirty state. This removes the merge barrier and eliminates the
> need for __force_merge().
> 
> Benefits
> 
> - Correct high-order allocations after mixed clear/dirty workloads
> - Elimination of O(N x max_order) merge cost from the allocation path
> - O(log E) cleared-extent lookup replacing O(N) scans
> - Predictable allocation latency under fragmentation
> - Reduced complexity with a single tree per order
> 
> Test:
> dEQP-VK.memory.allocation.basic.size_8KiB.reverse.count_4000
> 
> Below data is from /sys/kernel/debug/dri/1/amdgpu_vram_mm:
> 
> Base (dual-tree), before VKCTS test:
>    order- 6 free:   6 MiB,  blocks: 26
>    order- 5 free:   1 MiB,  blocks: 15
>    order- 4 free: 960 KiB,  blocks: 15
>    order- 3 free:   5 MiB,  blocks: 171
>    order- 2 free:   2 MiB,  blocks: 176
>    order- 1 free:   1 MiB,  blocks: 165
>    order- 0 free:  16 KiB,  blocks: 4
> 
> Base (dual-tree), after VKCTS test:
>    order- 6 free: 768 KiB,  blocks: 3
>    order- 5 free: 499 MiB,  blocks: 3999
>    order- 4 free: 250 MiB,  blocks: 4001
>    order- 3 free: 129 MiB,  blocks: 4157
>    order- 2 free:  65 MiB,  blocks: 4161
>    order- 1 free:  63 MiB,  blocks: 8138
>    order- 0 free:  20 KiB,  blocks: 5
> 
> Dirty tracker, before VKCTS test:
>    order- 6 free:   4 MiB,  blocks: 19
>    order- 5 free:   2 MiB,  blocks: 18
>    order- 4 free: 704 KiB,  blocks: 11
>    order- 3 free:   5 MiB,  blocks: 168
>    order- 2 free:   2 MiB,  blocks: 174
>    order- 1 free:   1 MiB,  blocks: 167
>    order- 0 free:  32 KiB,  blocks: 8
> 
> Dirty tracker, after VKCTS test:
>    order- 6 free:   4 MiB,  blocks: 19
>    order- 5 free:   2 MiB,  blocks: 18
>    order- 4 free: 704 KiB,  blocks: 11
>    order- 3 free:   5 MiB,  blocks: 168
>    order- 2 free:   2 MiB,  blocks: 174
>    order- 1 free:   1 MiB,  blocks: 167
>    order- 0 free:  28 KiB,  blocks: 7
> 
> v2:
>   - Code-style cleanup and minor refactoring
>   - Renamed locals for clarity
> 
> v3:
>   - Keep cleared blocks inside free_tree[] instead of floating them.
>   - Add subtree_has_dirty rbtree augment for O(log N) dirty-first walk.
> 
> v4:
>   - Fixed checkpatch warnings.
>   - Optimized gpu_buddy_reset_clear() to a single post-order walk that
>     flips block headers and recomputes the rbtree augment in one pass.
>   - Propagate subtree_max_size top-down in insert_extent() so ancestors
>     are not left with stale values on no-rotation inserts. (sashiko)
>   - Drop the whole extent in gpu_dirty_tracker_mark_dirty() when the
>     inside-split allocation fails, avoiding a stale clear claim. (sashiko)
>   - Make gpu_dirty_tracker_find() alignment-aware and fall back to the
>     dirty tree on steered failure to avoid spurious -ENOSPC. (sashiko)
> 
> v5:
>   - Track dirty extents instead of cleared ones: steer dirty allocs onto
>     tracked dirty windows and pick clear allocs via a free-tree augment,
>     avoiding clear-memory wastage by keeping cleared free blocks untouched
>     during dirty allocation.
> 
> v6:
>   - Make __alloc_range_bias() return the highest/right-most address by
>     default, establishing top-down as the intended placement for
>     range-biased allocations.
>   - Honour GPU_BUDDY_CLEAR_ALLOCATION in __alloc_range_bias() by steering
>     the descent towards clear subtrees for non-top-down clear
>     requests. (sashiko)
>   - Skip dirty-tracker steering for offset-aligned requests so they keep
>     their min_block_size alignment. (sashiko)
>   - sashiko reported that the __GFP_NOFAIL dirty-extent allocations on
>     the free path could deadlock during memory reclaim, since that is a
>     GFP_KERNEL allocation on the free path; move to a per-tracker
>     mempool so extent nodes are guaranteed without __GFP_NOFAIL.
>     (sashiko)
>   - Derive each free block's clear/dirty class from the blocks already
>     in hand on split, free, alloc, trim and init instead of querying the
>     dirty tracker, removing the tracker lookups from the hot paths.
> 
> v7:
>   - Preserve mixed-block clear state in __gpu_buddy_free() when a mixed
>     split child is re-merged after an undone split. (sashiko)
>   - Prefer a fully-clear block over a mixed one of the same order via a
>     single ordered clear-state max augment on free_tree[].
> 
> v8:
>   - Coalesce contiguous dirty blocks in __gpu_buddy_free_list() into one
>     dirty extent update instead of one mark_dirty() per block. (Matthew)
> 
> v9:
>   - Reset has_clear on allocation so a mixed block taken whole and later
>     freed fully dirty is not re-tracked as mixed. (sashiko)
> 
> v10:
>   - Use a plain slab allocation for dirty extents; skip and log once on
>     failure. (Matthew)
>   - Assert a non-zero size in the dirty-tracker range helpers. (Matthew)
>   - Drop the cached clear_avail member; derive it on demand. (Matthew)
>   - Collapse the two dirty branches of gpu_buddy_reset_clear(). (Matthew)
>   - Move the gpu_block_state enum above the gpu_buddy_block kernel-doc
>     so the doc directly precedes its struct. (Matthew)
>   - Mark the gpu_dirty_tracker struct private. (Matthew)
>   - Preserve a block's clear state on non-clear allocation instead of
>     force-dirtying it. (Matthew)
>   - Drop the redundant header clear in gpu_buddy_block_trim(). (Matthew)
> 
> Assisted-by: Claude:claude-opus-4-8
> Cc: Matthew Auld <[email protected]>
> Cc: Christian König <[email protected]>
> Signed-off-by: Arunpravin Paneer Selvam <[email protected]>
> Reviewed-by: Matthew Auld <[email protected]>
> ---

<snip>

>   
> +/**
> + * gpu_buddy_clear_avail - free space that is clear (zeroed), in bytes
> + * @mm: gpu buddy allocator
> + *
> + * A subset of @mm->avail. Derived on demand as @mm->avail minus the bytes
> + * the dirty tracker records as dirty, so it is always consistent with the
> + * tracker without a cached field to keep in sync. Zero for a fresh pool,
> + * which is fully dirty.
> + */
> +static inline u64 gpu_buddy_clear_avail(const struct gpu_buddy *mm)
> +{

gpu_buddy_driver_lock_held(mm);

Just to make it clear that avail & total_dirty need to be in-sync to 
always get something sane here?

Can be tweaked when merging.

> +	return mm->avail - mm->dirty.total_dirty;
> +}
> +
>   #ifdef CONFIG_LOCKDEP
>   /**
>    * gpu_buddy_driver_set_lock() - Set the lock protecting accesses to GPU BUDDY
> 
> base-commit: 063019ac51afffda4ab3d658701b086caa0c8e9e