Hi Matthew,
On 6/10/2026 6:36 PM, Arunpravin Paneer Selvam wrote:
On 6/10/2026 2:49 PM, Matthew Auld wrote:
On 01/06/2026 11:51, Arunpravin Paneer Selvam wrote:
On 5/29/2026 11:11 PM, Matthew Auld wrote:
Hi,
On 27/05/2026 12:29, 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.
So is this contig with non power-of-two sizes?
Both power-of-two and non-power-of-two contiguous requests are
affected - in either case, the required higher-order block can't
form when its lower-order buddies are separated by clear/dirty state
across the dual trees. But the core issue we are seeing is VRAM
fragmentation caused by massive small allocations (e.g., thousands
of 4 KiB–8 KiB buffers) that end up split across clear and dirty
trees, preventing buddy coalescing. This leads to allocation
failures and OOM in later workloads even when sufficient total free
VRAM is available.
Do we know if we could force_merge everything in one go or somehow
be more aggressive and do more than needed now, at the first sign
of contention here, instead of doing it piecemeal? Downside would
be losing more of the clear tracking, when this happens, but more
re- merging.
Could we have another per-order list, of all blocks that we failed
to merge, when we did the free step? When doing the force merge
step, we maybe don't need to search blindly and can focus instead
on the stuff tracked in those lists? Maybe it doesn't need to be a
list, but could be another rb-tree?
We know the size of the total allocation, if we trigger
force_merge, could we try to merge enough in one go for the entire
allocation, instead of restarting the entire thing on the next
iteration? Would that help at all?
But I guess these are more for the stalling side, and won't help
much with the contig angle?
The memory is highly fragmented into mostly 4 KiB chunks and small
scattered blocks across the dual trees, so although total free
memory exists, it is split into low-order fragments. The workload
then requests very large contiguous allocations (tens of GBs, e.g.,
~64 GiB), which fail with OOM because the allocator cannot form
sufficiently large high- order blocks from the fragmented space. We
could go with more aggressive merging or merge-in-one-go approaches,
but this might waste more cleared memory. I think fundamentally the
buddy allocator should be allowed to merge unconditionally - the
single-tree approach with unconditional coalescing would improve the
fragmentation and benefit contiguous allocations along with
addressing the stalling and latency issues.
For the extent idea, is there any merit in maybe doing this for all
contig blobs, and not just cleared stuff? Or is the workload you
are seeing only benefit users that want cleared stuff? Wondering if
this would benefit all users that want contig? Like if we
hypothetically kept clear and dirty separate, like we do now, but
with an improved force_merge, and then have extent tracking for all
contig blobs and replace the try_harder stuff? When you do a contig
alloc, the individual clear/dirty is still all there within the
range, so you can skip re-clearing in some cases. I guess downside
is overall more fuzzy contig + clear/free path, but I guess you
would never get allocation failures, when there is sufficient
contig space?
Yes, extending extent tracking to all contig allocations has merit,
but the core problem remains - with the dual-tree design, we still
need force_merge to undo the clear/dirty split before those extents
can form. In cases like heavy small-allocation workloads (thousands
of 4 KiB buffers) running first, the memory ends up massively
fragmented across both trees. When a very large contiguous
allocation (e.g., ~64 GiB) comes in later, the allocator fails with
OOM even though sufficient total free memory exists, because the
extent tracker can't find a contiguous range that was never allowed
to merge in the first place. I think the dirty/clear split is
fundamentally the problem - allowing the buddy allocator to merge
unconditionally removes this barrier, and the clear tracker can then
be layered on top as an optimization without blocking coalescing.
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 clear tracker (gpu_clear_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
Since there is no separate tracking for dirty stuff, is the non-
cleared alloc path a bit more "fuzzy" now, with it potentially
stealing cleared memory, or is it the same behaviour still?
Right, on v4, the dirty and mixed (partially cleared) blocks are
allocated for the non-cleared alloc path, which can end up stealing
cleared memory. On v5, I plan to address this with a three-tier
dirty allocation fallback: dirty → mixed → clear, driven by rbtree
augment bits (subtree_has_dirty, subtree_has_mixed), each pass O(log
N). The split-descent also applies the same preference at every
level when carving a higher-order block, so cleared memory is
preserved as much as possible and only used as a last resort.
Thoughts ?
No objections from me. Do you want me to still look at v4 in depth,
or wait for v5? I only really looked at this from high level.
I will send the v5. Please review the next version.
After evaluating a few alternatives, I moved from a clear tracker to a
dirty tracker. The two-bit dirty + mixed tracking scheme preserves
cleared memory correctly, but selecting blocks based on state rather
than address order causes dirty allocations to spread into the middle of
the pool and increase fragmentation over time. With the dirty tracker,
dirty allocations are satisfied from tracked dirty extents first and
otherwise fall back to the highest-address free block. Cleared
allocations naturally consume the highest-address cleared blocks from
the free tree, creating a natural boundary between dirty and cleared
regions, while mixed blocks can be split so each allocation type
consumes the appropriate portion. The v5 series will follow the
dirty-tracker design. Please let me know if you see any issues with this
approach.
Regards,
Arun.
Thanks,
Arun.
For drivers that don't use free tracking, is there some benefit?
Are there any downsides there? I assume that clear tracker is
always empty.
Correct, for drivers that don't clear memory, the clear tracker is
always empty and they simply allocate from the free_tree[]. Benefits:
Single tree per order instead of dual trees (fewer rbtree operations)
No force_merge path at all (unconditional coalescing at free time)
Simpler code path overall
No real downsides - the clear tracker adds zero overhead when empty,
and the augment bits would simply show all blocks as dirty, so the
walk degenerates to a normal rbtree lookup with no extra cost.
Regards,
Arun.
