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

On 8/6/2026 10:54 PM, Matthew Auld wrote:
> On 06/08/2026 17:45, Matthew Auld wrote:
>> On 31/07/2026 08:07, 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[].
>>>
>>> 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]>
>>
>> <snip>
>>
>>> @@ -620,13 +1100,18 @@ EXPORT_SYMBOL(gpu_buddy_reset_clear);
>>>   void gpu_buddy_free_block(struct gpu_buddy *mm,
>>>                 struct gpu_buddy_block *block)
>>>   {
>>> +    u64 size = gpu_buddy_block_size(mm, block);
>>> +    u64 offset = gpu_buddy_block_offset(block);
>>> +
>>>       gpu_buddy_driver_lock_held(mm);
>>>       BUG_ON(!gpu_buddy_block_is_allocated(block));
>>> -    mm->avail += gpu_buddy_block_size(mm, block);
>>> -    if (gpu_buddy_block_is_clear(block))
>>> -        mm->clear_avail += gpu_buddy_block_size(mm, block);
>>> -    __gpu_buddy_free(mm, block, false);
>>> +    mm->avail += size;
>>> +    if (!gpu_buddy_block_is_clear(block))
>>> +        gpu_dirty_tracker_mark_dirty(&mm->dirty, offset, size);
>>> +
>>> +    gpu_buddy_sync_clear_avail(mm);
>>> +    __gpu_buddy_free(mm, block);
>>>   }
>>>   EXPORT_SYMBOL(gpu_buddy_free_block);
>>> @@ -641,9 +1126,9 @@ static void __gpu_buddy_free_list(struct 
>>> gpu_buddy *mm,
>>>       list_for_each_entry_safe(block, on, objects, link) {
>>>           if (mark_clear)
>>> -            mark_cleared(block);
>>> +            block->header |= GPU_BUDDY_HEADER_CLEAR;
>>>           else if (mark_dirty)
>>> -            clear_reset(block);
>>> +            block->header &= ~GPU_BUDDY_HEADER_CLEAR;
>>>           gpu_buddy_free_block(mm, block);
>>
>> Just a thought, not a blocker or anything. It looks possible that as 
>> you loop through the blocks here you could easily extend the extent 
>> range if you keep finding something contig to the current extent, and 
>> then turn that into fewer mark_dirty() calls. If you ever encounter 
>> something non- contig you call mark_dirty() with whatever extent 
>> range you have now, and then start again. Obvious case is if you had 
>> a contig allocation which is more than one block, which could be 
>> turned into one mark_dirty().
>
> For example: 
> https://gitlab.freedesktop.org/mwa/kernel/-/commit/f58b83b638fd2203de6d06a0eb0994fbe4ec046a 
>
I added in v8 and sent for the review.

Thanks,
Arun.
>
>>
>