From: Matthew Auld <matthew.auld@intel.com>
To: Arunpravin Paneer Selvam <arunpravin.paneerselvam@amd.com>,
christian.koenig@amd.com, dri-devel@lists.freedesktop.org,
intel-gfx@lists.freedesktop.org, intel-xe@lists.freedesktop.org,
amd-gfx@lists.freedesktop.org
Cc: alexander.deucher@amd.com, Anand.Raghavendra@amd.com
Subject: Re: [PATCH v9 1/2] gpu/buddy: replace dual-tree/force_merge with decoupled dirty tracker
Date: Mon, 17 Aug 2026 10:57:14 +0100 [thread overview]
Message-ID: <0b92672e-dee7-4ef1-83fd-ea9f31729eca@intel.com> (raw)
In-Reply-To: <767c8eba-56d3-4449-9605-99a3f5e57af8@amd.com>
Hey,
Sorry, was OoO last week. I think you missed some feedback/questions
here:
https://lore.kernel.org/intel-xe/c63399c5-8507-4f4e-9ef1-241efac4d024@intel.com/
Main question was around GPU_DIRTY_EXTENT_POOL_MIN.
On 13/08/2026 14:37, Arunpravin Paneer Selvam wrote:
> Hi Matthew,
>
> Do you have any objections or concerns with the patches? If not, should
> I proceed with merging them,
> or are you still in the process of reviewing/validating them?
>
> Regards,
> Arun.
>
> On 8/11/2026 7:04 PM, 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)
>>
>> Assisted-by: Claude:claude-opus-4-8
>> Cc: Matthew Auld <matthew.auld@intel.com>
>> Cc: Christian König <christian.koenig@amd.com>
>> Signed-off-by: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>
>> ---
>> drivers/gpu/buddy.c | 1370 ++++++++++++++++++++--------
>> drivers/gpu/tests/gpu_buddy_test.c | 32 +-
>> include/linux/gpu_buddy.h | 97 +-
>> 3 files changed, 1083 insertions(+), 416 deletions(-)
>>
>> diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
>> index 4d5ac375a538..7d50156a5bc7 100644
>> --- a/drivers/gpu/buddy.c
>> +++ b/drivers/gpu/buddy.c
>> @@ -8,6 +8,7 @@
>> #include <linux/kmemleak.h>
>> #include <linux/module.h>
>> #include <linux/sizes.h>
>> +#include <linux/slab.h>
>> #include <linux/gpu_buddy.h>
>> @@ -34,6 +35,447 @@
>> #endif
>> static struct kmem_cache *slab_blocks;
>> +static struct kmem_cache *slab_extents;
>> +
>> +/*
>> + * A single reserved extent suffices. Every allocation uses GFP_KERNEL
>> + * from sleepable context and waits for reclaim, so it almost always
>> + * succeeds; the reserve only backstops the rare NULL return without
>> + * __GFP_NOFAIL and need not scale with extents added in one locked
>> + * section (e.g. by gpu_buddy_reset_clear()).
>> + */
>> +#define GPU_DIRTY_EXTENT_POOL_MIN 1
>> +
>> +/*
>> + * Dirty tracker
>> + * -------------
>> + *
>> + * The dirty tracker maintains an augmented interval rbtree of
>> contiguous
>> + * dirty address ranges, decoupled from the buddy free trees.
>> + * Each node covers a maximal coalesced run; adjacent extents are merged
>> + * on insertion so the tree always holds the smallest possible number of
>> + * extents. The augmentation field @subtree_max_size lets the allocator
>> + * locate the largest dirty extent in O(log E).
>> + *
>> + * Free trees (mm->free_tree[])
>> + * ----------------------------
>> + *
>> + * Per-order augmented rbtrees of FREE buddy blocks, keyed by offset.
>> + * Every node carries:
>> + * - subtree_max_alignment: largest natural alignment in the subtree,
>> + * used by aligned/range allocations to skip unsuitable subtrees in
>> + * O(log N).
>> + * - subtree_block_state: the highest clear class (DIRTY < MIXED <
>> CLEAR)
>> + * of any block in the subtree, maintained as a max augment. A
>> value of
>> + * >= MIXED means a clear-or-mixed block exists; == CLEAR means a
>> + * fully-clear block exists.
>> + *
>> + * Block classes
>> + * -------------
>> + *
>> + * Each FREE block falls into one of three classes, determined in
>> + * mark_free() by querying the dirty tracker for the block's range:
>> + *
>> + * clear -- HEADER_CLEAR set; no dirty extent overlaps the range.
>> + * mixed -- HEADER_CLEAR unset; range has both dirty and clear
>> bytes.
>> + * dirty -- HEADER_CLEAR unset; range is fully dirty.
>> + *
>> + * Clear allocation
>> + * ----------------
>> + *
>> + * A clear (CLEAR_ALLOCATION) request prefers clear -> mixed -> dirty.
>> + * Climbing from the requested order up to max_order,
>> rbtree_last_clear_free_block()
>> + * returns, in one O(log N) descent per order, the right-most clear-
>> or-mixed block
>> + * (fully-clear preferred over mixed) at the lowest order whose free
>> tree contains
>> + * such a block. Only if no clear-or-mixed block exists at any order
>> >= the
>> + * requested one does it fall back to a dirty block.
>> + *
>> + * Clear state is reported to the driver per whole block via
>> HEADER_CLEAR, so a
>> + * fully-clear block of the requested order lets the driver skip the
>> clear pass.
>> + *
>> + * The effective allocation preference depends on how the driver handles
>> + * freed blocks:
>> + *
>> + * 1) Never clear on free:
>> + * No free block contains clear bytes, so clear allocations always
>> + * fall back to dirty blocks.
>> + *
>> + * 2) Always clear on free:
>> + * Freed blocks become clear while untouched blocks remain dirty.
>> + * Merging clear and dirty buddies produces mixed blocks, which are
>> + * reclassified when split. Over time, clear blocks become
>> dominant,
>> + * so clear allocations are typically satisfied from clear blocks,
>> + * following a clear -> mixed -> dirty preference.
>> + *
>> + * 3) Selective clear on free:
>> + * For each order examined, fully-clear blocks are preferred over
>> + * mixed blocks, and mixed blocks are preferred over dirty blocks.
>> + * If a clear or mixed block is found at an order, it is selected
>> + * without searching higher orders. Dirty blocks are used only when
>> + * no clear or mixed block exists at any eligible order.
>> + */
>> +
>> +static u64 extent_size(struct gpu_dirty_extent *dirty_extent)
>> +{
>> + return dirty_extent->end - dirty_extent->start;
>> +}
>> +
>> +RB_DECLARE_CALLBACKS_MAX(static, gpu_dirty_augment_cb,
>> + struct gpu_dirty_extent, rb,
>> + u64, subtree_max_size,
>> + extent_size)
>> +
>> +static struct gpu_dirty_extent *extent_alloc(struct gpu_dirty_tracker
>> *dirty_tracker)
>> +{
>> + /*
>> + * The void free/reset paths must record an extent and cannot handle
>> + * failure, so the mempool reserve guarantees a non-NULL return
>> + * without __GFP_NOFAIL. GFP_KERNEL is safe under the buddy lock: no
>> + * driver frees buddy blocks from a shrinker, so reclaim cannot
>> + * recurse into the lock we hold.
>> + */
>> + return mempool_alloc(dirty_tracker->extent_pool, GFP_KERNEL);
>> +}
>> +
>> +static void extent_free(struct gpu_dirty_tracker *dirty_tracker,
>> + struct gpu_dirty_extent *dirty_extent)
>> +{
>> + mempool_free(dirty_extent, dirty_tracker->extent_pool);
>> +}
>> +
>> +/* Return the rightmost extent whose start is strictly below @offset. */
>> +static struct gpu_dirty_extent *
>> +prev_extent(struct gpu_dirty_tracker *dirty_tracker, u64 offset)
>> +{
>> + struct rb_node *rb = dirty_tracker->root.rb_node;
>> + struct gpu_dirty_extent *dirty_extent = NULL;
>> +
>> + while (rb) {
>> + struct gpu_dirty_extent *tmp_extent =
>> + rb_entry(rb, struct gpu_dirty_extent, rb);
>> +
>> + if (tmp_extent->start < offset) {
>> + dirty_extent = tmp_extent;
>> + rb = rb->rb_right;
>> + } else {
>> + rb = rb->rb_left;
>> + }
>> + }
>> +
>> + return dirty_extent;
>> +}
>> +
>> +/* Return the leftmost extent whose start is at or above @offset. */
>> +static struct gpu_dirty_extent *
>> +next_extent(struct gpu_dirty_tracker *dirty_tracker, u64 offset)
>> +{
>> + struct rb_node *rb = dirty_tracker->root.rb_node;
>> + struct gpu_dirty_extent *dirty_extent = NULL;
>> +
>> + while (rb) {
>> + struct gpu_dirty_extent *tmp_extent =
>> + rb_entry(rb, struct gpu_dirty_extent, rb);
>> +
>> + if (tmp_extent->start >= offset) {
>> + dirty_extent = tmp_extent;
>> + rb = rb->rb_left;
>> + } else {
>> + rb = rb->rb_right;
>> + }
>> + }
>> +
>> + return dirty_extent;
>> +}
>> +
>> +static void insert_extent(struct gpu_dirty_tracker *dirty_tracker,
>> + struct gpu_dirty_extent *dirty_extent)
>> +{
>> + struct rb_node **link = &dirty_tracker->root.rb_node;
>> + struct rb_node *parent = NULL;
>> + u64 size = extent_size(dirty_extent);
>> +
>> + while (*link) {
>> + struct gpu_dirty_extent *tmp_extent;
>> +
>> + parent = *link;
>> + tmp_extent = rb_entry(parent, struct gpu_dirty_extent, rb);
>> +
>> + if (tmp_extent->subtree_max_size < size)
>> + tmp_extent->subtree_max_size = size;
>> +
>> + if (dirty_extent->start < tmp_extent->start)
>> + link = &parent->rb_left;
>> + else
>> + link = &parent->rb_right;
>> + }
>> +
>> + dirty_extent->subtree_max_size = size;
>> + rb_link_node(&dirty_extent->rb, parent, link);
>> + rb_insert_augmented(&dirty_extent->rb, &dirty_tracker->root,
>> &gpu_dirty_augment_cb);
>> +}
>> +
>> +static void remove_extent(struct gpu_dirty_tracker *dirty_tracker,
>> + struct gpu_dirty_extent *dirty_extent)
>> +{
>> + rb_erase_augmented(&dirty_extent->rb, &dirty_tracker->root,
>> &gpu_dirty_augment_cb);
>> + RB_CLEAR_NODE(&dirty_extent->rb);
>> +}
>> +
>> +static int gpu_dirty_tracker_init(struct gpu_dirty_tracker
>> *dirty_tracker)
>> +{
>> + dirty_tracker->root = RB_ROOT;
>> + dirty_tracker->total_dirty = 0;
>> +
>> + dirty_tracker->extent_pool =
>> + mempool_create_slab_pool(GPU_DIRTY_EXTENT_POOL_MIN,
>> slab_extents);
>> + if (!dirty_tracker->extent_pool)
>> + return -ENOMEM;
>> +
>> + return 0;
>> +}
>> +
>> +static void gpu_dirty_tracker_empty(struct gpu_dirty_tracker
>> *dirty_tracker)
>> +{
>> + struct rb_node *rb;
>> +
>> + while ((rb = rb_first(&dirty_tracker->root))) {
>> + struct gpu_dirty_extent *dirty_extent =
>> + rb_entry(rb, struct gpu_dirty_extent, rb);
>> +
>> + remove_extent(dirty_tracker, dirty_extent);
>> + extent_free(dirty_tracker, dirty_extent);
>> + }
>> +
>> + dirty_tracker->total_dirty = 0;
>> +}
>> +
>> +static void gpu_dirty_tracker_fini(struct gpu_dirty_tracker
>> *dirty_tracker)
>> +{
>> + gpu_dirty_tracker_empty(dirty_tracker);
>> + mempool_destroy(dirty_tracker->extent_pool);
>> + dirty_tracker->extent_pool = NULL;
>> +}
>> +
>> +/*
>> + * Mark the range [start, start + size] as dirty. Merge with the
>> neighbour on
>> + * each side if they are contiguous, so the tree never holds two
>> adjacent ranges.
>> + */
>> +static void gpu_dirty_tracker_mark_dirty(struct gpu_dirty_tracker
>> *dirty_tracker,
>> + u64 start, u64 size)
>> +{
>> + struct gpu_dirty_extent *left, *right, *dirty_extent;
>> + u64 end = start + size;
>> +
>> + if (!size)
>> + return;
>> +
>> + /* Find contiguous neighbours, if any. */
>> + left = prev_extent(dirty_tracker, start);
>> + if (left && left->end != start)
>> + left = NULL;
>> +
>> + right = next_extent(dirty_tracker, end);
>> + if (right && right->start != end)
>> + right = NULL;
>> +
>> + if (left && right) {
>> + /* Merge left + new + right into a single extent. */
>> + remove_extent(dirty_tracker, left);
>> + remove_extent(dirty_tracker, right);
>> + left->end = right->end;
>> + extent_free(dirty_tracker, right);
>> + insert_extent(dirty_tracker, left);
>> + } else if (left) {
>> + /* Extend left neighbour rightwards. */
>> + remove_extent(dirty_tracker, left);
>> + left->end = end;
>> + insert_extent(dirty_tracker, left);
>> + } else if (right) {
>> + /* Extend right neighbour leftwards. */
>> + remove_extent(dirty_tracker, right);
>> + right->start = start;
>> + insert_extent(dirty_tracker, right);
>> + } else {
>> + /* Standalone extent. */
>> + dirty_extent = extent_alloc(dirty_tracker);
>> + dirty_extent->start = start;
>> + dirty_extent->end = end;
>> + insert_extent(dirty_tracker, dirty_extent);
>> + }
>> +
>> + dirty_tracker->total_dirty += size;
>> +}
>> +
>> +/*
>> + * Remove the range [start, start + size] from the dirty tracker.
>> Punch the
>> + * range out of every overlapping dirty extent, splitting one extent
>> in two if
>> + * the removed range falls strictly inside it.
>> + */
>> +static void gpu_dirty_tracker_remove_range(struct gpu_dirty_tracker
>> *dirty_tracker,
>> + u64 start, u64 size)
>> +{
>> + struct gpu_dirty_extent *dirty_extent, *next;
>> + u64 end = start + size;
>> +
>> + if (!size)
>> + return;
>> +
>> + dirty_extent = prev_extent(dirty_tracker, start + 1);
>> + if (!dirty_extent)
>> + dirty_extent = next_extent(dirty_tracker, start);
>> +
>> + while (dirty_extent && dirty_extent->start < end) {
>> + struct rb_node *next_node = rb_next(&dirty_extent->rb);
>> + u64 extent_start = dirty_extent->start;
>> + u64 extent_end = dirty_extent->end;
>> +
>> + if (next_node)
>> + next = rb_entry(next_node, struct gpu_dirty_extent, rb);
>> + else
>> + next = NULL;
>> +
>> + /* Skip a non-overlapping neighbour returned by
>> prev_extent(). */
>> + if (extent_end <= start) {
>> + dirty_extent = next;
>> + continue;
>> + }
>> +
>> + if (extent_start < start && extent_end > end) {
>> + /*
>> + * Removed range lies strictly inside this dirty extent:
>> + * split it into the dirty left and right halves.
>> + */
>> + struct gpu_dirty_extent *right =
>> extent_alloc(dirty_tracker);
>> +
>> + remove_extent(dirty_tracker, dirty_extent);
>> +
>> + dirty_extent->end = start;
>> + right->start = end;
>> + right->end = extent_end;
>> +
>> + insert_extent(dirty_tracker, dirty_extent);
>> + insert_extent(dirty_tracker, right);
>> +
>> + dirty_tracker->total_dirty -= size;
>> + } else if (extent_start >= start && extent_end <= end) {
>> + /* Extent fully covered: drop it. */
>> + remove_extent(dirty_tracker, dirty_extent);
>> + extent_free(dirty_tracker, dirty_extent);
>> +
>> + dirty_tracker->total_dirty -= (extent_end - extent_start);
>> + } else if (extent_start < start) {
>> + /* Extent overlaps from the left: trim its right end. */
>> + remove_extent(dirty_tracker, dirty_extent);
>> + dirty_extent->end = start;
>> + insert_extent(dirty_tracker, dirty_extent);
>> +
>> + dirty_tracker->total_dirty -= (extent_end - start);
>> + } else {
>> + /* Extent overlaps from the right: trim its left end. */
>> + remove_extent(dirty_tracker, dirty_extent);
>> + dirty_extent->start = end;
>> + insert_extent(dirty_tracker, dirty_extent);
>> +
>> + dirty_tracker->total_dirty -= (end - extent_start);
>> + }
>> +
>> + dirty_extent = next;
>> + }
>> +}
>> +
>> +static enum gpu_block_state
>> +gpu_dirty_range_state(struct gpu_dirty_tracker *dirty_tracker,
>> + u64 start, u64 size)
>> +{
>> + struct gpu_dirty_extent *dirty_extent;
>> + u64 end = start + size;
>> +
>> + dirty_extent = prev_extent(dirty_tracker, start + 1);
>> + if (dirty_extent) {
>> + if (dirty_extent->start <= start && dirty_extent->end >= end)
>> + return GPU_BLOCK_DIRTY;
>> + if (dirty_extent->start < end && dirty_extent->end > start)
>> + return GPU_BLOCK_MIXED;
>> + }
>> +
>> + dirty_extent = next_extent(dirty_tracker, start);
>> + if (dirty_extent && dirty_extent->start < end)
>> + return GPU_BLOCK_MIXED;
>> +
>> + return GPU_BLOCK_CLEAR;
>> +}
>> +
>> +static struct rb_node *
>> +dirty_tracker_descend_right(struct rb_node *node, u64 min_size)
>> +{
>> + while (node->rb_right) {
>> + struct gpu_dirty_extent *tmp_extent;
>> +
>> + tmp_extent = rb_entry(node->rb_right, struct
>> gpu_dirty_extent, rb);
>> +
>> + if (tmp_extent->subtree_max_size < min_size)
>> + break;
>> + node = node->rb_right;
>> + }
>> +
>> + return node;
>> +}
>> +
>> +static struct gpu_dirty_extent *
>> +gpu_dirty_tracker_find(struct gpu_dirty_tracker *dirty_tracker,
>> + u64 min_size, u64 *aligned_start_out)
>> +{
>> + struct rb_node *rb = dirty_tracker->root.rb_node;
>> + struct gpu_dirty_extent *root_extent;
>> + struct rb_node *parent;
>> +
>> + if (!min_size || !is_power_of_2(min_size))
>> + return NULL;
>> +
>> + if (!rb)
>> + return NULL;
>> +
>> + root_extent = rb_entry(rb, struct gpu_dirty_extent, rb);
>> + if (root_extent->subtree_max_size < min_size)
>> + return NULL;
>> +
>> + rb = dirty_tracker_descend_right(rb, min_size);
>> +
>> + while (rb) {
>> + struct gpu_dirty_extent *dirty_extent;
>> + u64 aligned_start;
>> +
>> + dirty_extent = rb_entry(rb, struct gpu_dirty_extent, rb);
>> + aligned_start = ALIGN(dirty_extent->start, min_size);
>> +
>> + /* Check if a min_size block fits after the alignment skip. */
>> + if (aligned_start <= dirty_extent->end &&
>> + dirty_extent->end - aligned_start >= min_size) {
>> + *aligned_start_out = aligned_start;
>> + return dirty_extent;
>> + }
>> +
>> + if (rb->rb_left) {
>> + struct gpu_dirty_extent *tmp_extent;
>> +
>> + tmp_extent = rb_entry(rb->rb_left, struct
>> gpu_dirty_extent, rb);
>> + if (tmp_extent->subtree_max_size >= min_size) {
>> + rb = dirty_tracker_descend_right(rb->rb_left, min_size);
>> + continue;
>> + }
>> + }
>> +
>> + /* Walk up until we exit a node via its right child. */
>> + parent = rb_parent(rb);
>> + while (parent && parent->rb_right != rb) {
>> + rb = parent;
>> + parent = rb_parent(rb);
>> + }
>> + rb = parent;
>> + }
>> +
>> + return NULL;
>> +}
>> static unsigned int
>> gpu_buddy_block_state(struct gpu_buddy_block *block)
>> @@ -67,10 +509,97 @@ static unsigned int
>> gpu_buddy_block_offset_alignment(struct gpu_buddy_block *blo
>> return __ffs64(offset);
>> }
>> -RB_DECLARE_CALLBACKS_MAX(static, gpu_buddy_augment_cb,
>> - struct gpu_buddy_block, rb,
>> - unsigned int, subtree_max_alignment,
>> - gpu_buddy_block_offset_alignment);
>> +static inline enum gpu_block_state
>> +gpu_block_cached_state(struct gpu_buddy_block *block)
>> +{
>> + if (gpu_buddy_block_is_clear(block))
>> + return GPU_BLOCK_CLEAR;
>> + if (block->has_clear)
>> + return GPU_BLOCK_MIXED;
>> + return GPU_BLOCK_DIRTY;
>> +}
>> +
>> +static inline void gpu_buddy_augment_compute(struct gpu_buddy_block
>> *block)
>> +{
>> + enum gpu_block_state block_state;
>> + struct gpu_buddy_block *right;
>> + struct gpu_buddy_block *left;
>> + unsigned int max_align;
>> +
>> + max_align = gpu_buddy_block_offset_alignment(block);
>> + block_state = gpu_block_cached_state(block);
>> +
>> + left = rb_entry_safe(block->rb.rb_left, struct gpu_buddy_block, rb);
>> + if (left) {
>> + if (left->subtree_max_alignment > max_align)
>> + max_align = left->subtree_max_alignment;
>> +
>> + block_state = max(block_state, left->subtree_block_state);
>> + }
>> +
>> + right = rb_entry_safe(block->rb.rb_right, struct gpu_buddy_block,
>> rb);
>> + if (right) {
>> + if (right->subtree_max_alignment > max_align)
>> + max_align = right->subtree_max_alignment;
>> +
>> + block_state = max(block_state, right->subtree_block_state);
>> + }
>> +
>> + block->subtree_max_alignment = max_align;
>> + block->subtree_block_state = block_state;
>> +}
>> +
>> +static void gpu_buddy_augment_propagate(struct rb_node *rb, struct
>> rb_node *stop)
>> +{
>> + while (rb != stop) {
>> + struct gpu_buddy_block *block;
>> + unsigned int old_align;
>> + enum gpu_block_state old_block_state;
>> +
>> + block = rb_entry(rb, struct gpu_buddy_block, rb);
>> + old_align = block->subtree_max_alignment;
>> + old_block_state = block->subtree_block_state;
>> +
>> + gpu_buddy_augment_compute(block);
>> + if (block->subtree_max_alignment == old_align &&
>> + block->subtree_block_state == old_block_state)
>> + break;
>> +
>> + rb = rb_parent(&block->rb);
>> + }
>> +}
>> +
>> +static void gpu_buddy_augment_copy(struct rb_node *rb_old, struct
>> rb_node *rb_new)
>> +{
>> + struct gpu_buddy_block *old;
>> + struct gpu_buddy_block *new;
>> +
>> + old = rb_entry(rb_old, struct gpu_buddy_block, rb);
>> + new = rb_entry(rb_new, struct gpu_buddy_block, rb);
>> +
>> + new->subtree_max_alignment = old->subtree_max_alignment;
>> + new->subtree_block_state = old->subtree_block_state;
>> +}
>> +
>> +static void gpu_buddy_augment_rotate(struct rb_node *rb_old, struct
>> rb_node *rb_new)
>> +{
>> + struct gpu_buddy_block *old;
>> + struct gpu_buddy_block *new;
>> +
>> + old = rb_entry(rb_old, struct gpu_buddy_block, rb);
>> + new = rb_entry(rb_new, struct gpu_buddy_block, rb);
>> +
>> + new->subtree_max_alignment = old->subtree_max_alignment;
>> + new->subtree_block_state = old->subtree_block_state;
>> +
>> + gpu_buddy_augment_compute(old);
>> +}
>> +
>> +static const struct rb_augment_callbacks gpu_buddy_augment_cb = {
>> + .propagate = gpu_buddy_augment_propagate,
>> + .copy = gpu_buddy_augment_copy,
>> + .rotate = gpu_buddy_augment_rotate,
>> +};
>> static struct gpu_buddy_block *gpu_block_alloc(struct gpu_buddy *mm,
>> struct gpu_buddy_block *parent,
>> @@ -81,6 +610,10 @@ static struct gpu_buddy_block
>> *gpu_block_alloc(struct gpu_buddy *mm,
>> BUG_ON(order > GPU_BUDDY_MAX_ORDER);
>> + /*
>> + * GFP_KERNEL is safe under the buddy lock: no consumer runs a
>> + * shrinker that re-enters it during direct reclaim.
>> + */
>> block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL);
>> if (!block)
>> return NULL;
>> @@ -101,13 +634,6 @@ static void gpu_block_free(struct gpu_buddy *mm,
>> kmem_cache_free(slab_blocks, block);
>> }
>> -static enum gpu_buddy_free_tree
>> -get_block_tree(struct gpu_buddy_block *block)
>> -{
>> - return gpu_buddy_block_is_clear(block) ?
>> - GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE;
>> -}
>> -
>> static struct gpu_buddy_block *
>> rbtree_get_free_block(const struct rb_node *node)
>> {
>> @@ -120,24 +646,64 @@ rbtree_last_free_block(struct rb_root *root)
>> return rbtree_get_free_block(rb_last(root));
>> }
>> -static bool rbtree_is_empty(struct rb_root *root)
>> +static struct gpu_buddy_block *
>> +rbtree_last_clear_free_block(struct rb_root *root,
>> + enum gpu_block_state min_block_state)
>> +{
>> + struct rb_node *node = root->rb_node;
>> + struct gpu_buddy_block *block = NULL;
>> + struct gpu_buddy_block *root_block;
>> + enum gpu_block_state target_state;
>> +
>> + root_block = rbtree_get_free_block(node);
>> + if (!root_block || root_block->subtree_block_state <
>> min_block_state)
>> + return NULL;
>> +
>> + target_state = root_block->subtree_block_state;
>> +
>> + while (node) {
>> + struct gpu_buddy_block *right_block;
>> + struct gpu_buddy_block *node_block;
>> +
>> + node_block = rbtree_get_free_block(node);
>> + right_block = rbtree_get_free_block(node->rb_right);
>> +
>> + if (right_block && right_block->subtree_block_state >=
>> target_state) {
>> + node = node->rb_right;
>> + continue;
>> + }
>> +
>> + if (gpu_block_cached_state(node_block) == target_state) {
>> + block = node_block;
>> + break;
>> + }
>> +
>> + node = node->rb_left;
>> + }
>> +
>> + return block;
>> +}
>> +
>> +static inline void gpu_buddy_sync_clear_avail(struct gpu_buddy *mm)
>> {
>> - return RB_EMPTY_ROOT(root);
>> + mm->clear_avail = mm->avail - mm->dirty.total_dirty;
>> }
>> static void rbtree_insert(struct gpu_buddy *mm,
>> - struct gpu_buddy_block *block,
>> - enum gpu_buddy_free_tree tree)
>> + struct gpu_buddy_block *block)
>> {
>> struct rb_node **link, *parent = NULL;
>> - unsigned int block_alignment, order;
>> + enum gpu_block_state block_state;
>> struct gpu_buddy_block *node;
>> + unsigned int block_alignment;
>> struct rb_root *root;
>> + unsigned int order;
>> order = gpu_buddy_block_order(block);
>> block_alignment = gpu_buddy_block_offset_alignment(block);
>> + block_state = gpu_block_cached_state(block);
>> - root = &mm->free_trees[tree][order];
>> + root = &mm->free_tree[order];
>> link = &root->rb_node;
>> while (*link) {
>> @@ -147,10 +713,12 @@ static void rbtree_insert(struct gpu_buddy *mm,
>> * Manual augmentation update during insertion traversal.
>> Required
>> * because rb_insert_augmented() only calls rotate callback
>> during
>> * rotations. This ensures all ancestors on the insertion
>> path have
>> - * correct subtree_max_alignment values.
>> + * correct subtree_max_alignment / subtree_block_state values.
>> */
>> if (node->subtree_max_alignment < block_alignment)
>> node->subtree_max_alignment = block_alignment;
>> + if (node->subtree_block_state < block_state)
>> + node->subtree_block_state = block_state;
>> if (gpu_buddy_block_offset(block) <
>> gpu_buddy_block_offset(node))
>> link = &parent->rb_left;
>> @@ -159,6 +727,7 @@ static void rbtree_insert(struct gpu_buddy *mm,
>> }
>> block->subtree_max_alignment = block_alignment;
>> + block->subtree_block_state = block_state;
>> rb_link_node(&block->rb, parent, link);
>> rb_insert_augmented(&block->rb, root, &gpu_buddy_augment_cb);
>> }
>> @@ -167,53 +736,55 @@ static void rbtree_remove(struct gpu_buddy *mm,
>> struct gpu_buddy_block *block)
>> {
>> unsigned int order = gpu_buddy_block_order(block);
>> - enum gpu_buddy_free_tree tree;
>> - struct rb_root *root;
>> -
>> - tree = get_block_tree(block);
>> - root = &mm->free_trees[tree][order];
>> - rb_erase_augmented(&block->rb, root, &gpu_buddy_augment_cb);
>> + rb_erase_augmented(&block->rb, &mm->free_tree[order],
>> &gpu_buddy_augment_cb);
>> RB_CLEAR_NODE(&block->rb);
>> }
>> -static void clear_reset(struct gpu_buddy_block *block)
>> -{
>> - block->header &= ~GPU_BUDDY_HEADER_CLEAR;
>> -}
>> -
>> -static void mark_cleared(struct gpu_buddy_block *block)
>> -{
>> - block->header |= GPU_BUDDY_HEADER_CLEAR;
>> -}
>> -
>> static void mark_allocated(struct gpu_buddy *mm,
>> struct gpu_buddy_block *block)
>> {
>> block->header &= ~GPU_BUDDY_HEADER_STATE;
>> block->header |= GPU_BUDDY_ALLOCATED;
>> + block->has_clear = false;
>> +
>> mm->free_scoreboard[gpu_buddy_block_order(block)]--;
>> mm->used_scoreboard[gpu_buddy_block_order(block)]++;
>> rbtree_remove(mm, block);
>> }
>> -static void mark_free(struct gpu_buddy *mm,
>> - struct gpu_buddy_block *block)
>> +static void __mark_free(struct gpu_buddy *mm,
>> + struct gpu_buddy_block *block,
>> + enum gpu_block_state block_state)
>> {
>> - enum gpu_buddy_free_tree tree;
>> -
>> if (gpu_buddy_block_is_allocated(block))
>> mm->used_scoreboard[gpu_buddy_block_order(block)]--;
>> block->header &= ~GPU_BUDDY_HEADER_STATE;
>> block->header |= GPU_BUDDY_FREE;
>> + block->header &= ~GPU_BUDDY_HEADER_CLEAR;
>> +
>> + block->has_clear = (block_state != GPU_BLOCK_DIRTY);
>> + if (block_state == GPU_BLOCK_CLEAR)
>> + block->header |= GPU_BUDDY_HEADER_CLEAR;
>> +
>> mm->free_scoreboard[gpu_buddy_block_order(block)]++;
>> - tree = get_block_tree(block);
>> - rbtree_insert(mm, block, tree);
>> + rbtree_insert(mm, block);
>> +}
>> +
>> +static void mark_free(struct gpu_buddy *mm,
>> + struct gpu_buddy_block *block)
>> +{
>> + enum gpu_block_state block_state;
>> +
>> + block_state = gpu_dirty_range_state(&mm->dirty,
>> + gpu_buddy_block_offset(block),
>> + gpu_buddy_block_size(mm, block));
>> + __mark_free(mm, block, block_state);
>> }
>> static void mark_split(struct gpu_buddy *mm,
>> @@ -253,37 +824,31 @@ __get_buddy(struct gpu_buddy_block *block)
>> }
>> static unsigned int __gpu_buddy_free(struct gpu_buddy *mm,
>> - struct gpu_buddy_block *block,
>> - bool force_merge)
>> + struct gpu_buddy_block *block)
>> {
>> + enum gpu_block_state block_state;
>> struct gpu_buddy_block *parent;
>> unsigned int order;
>> - while ((parent = block->parent)) {
>> - struct gpu_buddy_block *buddy;
>> + block_state = gpu_block_cached_state(block);
>> - buddy = __get_buddy(block);
>> + while ((parent = block->parent)) {
>> + struct gpu_buddy_block *buddy = __get_buddy(block);
>> if (!gpu_buddy_block_is_free(buddy))
>> break;
>> - if (!force_merge) {
>> - /*
>> - * Check the block and its buddy clear state and exit
>> - * the loop if they both have the dissimilar state.
>> - */
>> - if (gpu_buddy_block_is_clear(block) !=
>> - gpu_buddy_block_is_clear(buddy))
>> - break;
>> + if (block_state != GPU_BLOCK_MIXED) {
>> + enum gpu_block_state buddy_state;
>> +
>> + buddy_state = gpu_block_cached_state(buddy);
>> - if (gpu_buddy_block_is_clear(block))
>> - mark_cleared(parent);
>> + if (buddy_state != block_state)
>> + block_state = GPU_BLOCK_MIXED;
>> }
>> rbtree_remove(mm, buddy);
>> mm->free_scoreboard[gpu_buddy_block_order(buddy)]--;
>> - if (force_merge && gpu_buddy_block_is_clear(buddy))
>> - mm->clear_avail -= gpu_buddy_block_size(mm, buddy);
>> if (gpu_buddy_block_is_allocated(block))
>> mm->used_scoreboard[gpu_buddy_block_order(block)]--;
>> @@ -295,74 +860,11 @@ static unsigned int __gpu_buddy_free(struct
>> gpu_buddy *mm,
>> }
>> order = gpu_buddy_block_order(block);
>> - mark_free(mm, block);
>> + __mark_free(mm, block, block_state);
>> return order;
>> }
>> -static int __force_merge(struct gpu_buddy *mm,
>> - u64 start,
>> - u64 end,
>> - unsigned int min_order)
>> -{
>> - unsigned int tree, order;
>> - int i;
>> -
>> - if (!min_order)
>> - return -ENOMEM;
>> -
>> - if (min_order > mm->max_order)
>> - return -EINVAL;
>> -
>> - for_each_free_tree(tree) {
>> - for (i = min_order - 1; i >= 0; i--) {
>> - struct rb_node *iter = rb_last(&mm->free_trees[tree][i]);
>> -
>> - while (iter) {
>> - struct gpu_buddy_block *block, *buddy;
>> - u64 block_start, block_end;
>> -
>> - block = rbtree_get_free_block(iter);
>> - iter = rb_prev(iter);
>> -
>> - if (!block || !block->parent)
>> - continue;
>> -
>> - block_start = gpu_buddy_block_offset(block);
>> - block_end = block_start + gpu_buddy_block_size(mm,
>> block) - 1;
>> -
>> - if (!contains(start, end, block_start, block_end))
>> - continue;
>> -
>> - buddy = __get_buddy(block);
>> - if (!gpu_buddy_block_is_free(buddy))
>> - continue;
>> -
>> - gpu_buddy_assert(gpu_buddy_block_is_clear(block) !=
>> - gpu_buddy_block_is_clear(buddy));
>> -
>> - /*
>> - * Advance to the next node when the current node is
>> the buddy,
>> - * as freeing the block will also remove its buddy
>> from the tree.
>> - */
>> - if (iter == &buddy->rb)
>> - iter = rb_prev(iter);
>> -
>> - rbtree_remove(mm, block);
>> - mm->free_scoreboard[gpu_buddy_block_order(block)]--;
>> - if (gpu_buddy_block_is_clear(block))
>> - mm->clear_avail -= gpu_buddy_block_size(mm, block);
>> -
>> - order = __gpu_buddy_free(mm, block, true);
>> - if (order >= min_order)
>> - return 0;
>> - }
>> - }
>> - }
>> -
>> - return -ENOMEM;
>> -}
>> -
>> /**
>> * gpu_buddy_init - init memory manager
>> *
>> @@ -377,7 +879,7 @@ static int __force_merge(struct gpu_buddy *mm,
>> */
>> int gpu_buddy_init(struct gpu_buddy *mm, u64 size, u64 chunk_size)
>> {
>> - unsigned int i, j, root_count = 0;
>> + unsigned int root_count = 0;
>> u64 offset = 0;
>> if (size < chunk_size)
>> @@ -411,22 +913,14 @@ int gpu_buddy_init(struct gpu_buddy *mm, u64
>> size, u64 chunk_size)
>> if (!mm->used_scoreboard)
>> goto out_free_free_scoreboard;
>> - mm->free_trees = kmalloc_array(GPU_BUDDY_MAX_FREE_TREES,
>> - sizeof(*mm->free_trees),
>> - GFP_KERNEL);
>> - if (!mm->free_trees)
>> + mm->free_tree = kcalloc(mm->max_order + 1,
>> + sizeof(struct rb_root),
>> + GFP_KERNEL);
>> + if (!mm->free_tree)
>> goto out_free_used_scoreboard;
>> - for_each_free_tree(i) {
>> - mm->free_trees[i] = kmalloc_array(mm->max_order + 1,
>> - sizeof(struct rb_root),
>> - GFP_KERNEL);
>> - if (!mm->free_trees[i])
>> - goto out_free_tree;
>> -
>> - for (j = 0; j <= mm->max_order; ++j)
>> - mm->free_trees[i][j] = RB_ROOT;
>> - }
>> + if (gpu_dirty_tracker_init(&mm->dirty))
>> + goto out_free_tree;
>> mm->n_roots = hweight64(size);
>> @@ -452,7 +946,8 @@ int gpu_buddy_init(struct gpu_buddy *mm, u64 size,
>> u64 chunk_size)
>> if (!root)
>> goto out_free_roots;
>> - mark_free(mm, root);
>> + gpu_dirty_tracker_mark_dirty(&mm->dirty, offset, root_size);
>> + __mark_free(mm, root, GPU_BLOCK_DIRTY);
>> BUG_ON(root_count > mm->max_order);
>> BUG_ON(gpu_buddy_block_size(mm, root) < chunk_size);
>> @@ -474,9 +969,8 @@ int gpu_buddy_init(struct gpu_buddy *mm, u64 size,
>> u64 chunk_size)
>> gpu_block_free(mm, mm->roots[root_count]);
>> kfree(mm->roots);
>> out_free_tree:
>> - while (i--)
>> - kfree(mm->free_trees[i]);
>> - kfree(mm->free_trees);
>> + gpu_dirty_tracker_fini(&mm->dirty);
>> + kfree(mm->free_tree);
>> out_free_used_scoreboard:
>> kfree(mm->used_scoreboard);
>> out_free_free_scoreboard:
>> @@ -494,7 +988,7 @@ EXPORT_SYMBOL(gpu_buddy_init);
>> */
>> void gpu_buddy_fini(struct gpu_buddy *mm)
>> {
>> - u64 root_size, size, start;
>> + u64 root_size, size;
>> unsigned int order;
>> int i;
>> @@ -502,14 +996,10 @@ void gpu_buddy_fini(struct gpu_buddy *mm)
>> for (i = 0; i < mm->n_roots; ++i) {
>> order = ilog2(size) - ilog2(mm->chunk_size);
>> - start = gpu_buddy_block_offset(mm->roots[i]);
>> - __force_merge(mm, start, start + size, order);
>> + root_size = mm->chunk_size << order;
>> gpu_buddy_assert(gpu_buddy_block_is_free(mm->roots[i]));
>> -
>> gpu_block_free(mm, mm->roots[i]);
>> -
>> - root_size = mm->chunk_size << order;
>> size -= root_size;
>> }
>> @@ -518,9 +1008,8 @@ void gpu_buddy_fini(struct gpu_buddy *mm)
>> for (i = 0; i <= mm->max_order; ++i)
>> gpu_buddy_assert(!mm->used_scoreboard[i]);
>> - for_each_free_tree(i)
>> - kfree(mm->free_trees[i]);
>> - kfree(mm->free_trees);
>> + gpu_dirty_tracker_fini(&mm->dirty);
>> + kfree(mm->free_tree);
>> kfree(mm->roots);
>> kfree(mm->free_scoreboard);
>> kfree(mm->used_scoreboard);
>> @@ -532,6 +1021,7 @@ static int split_block(struct gpu_buddy *mm,
>> {
>> unsigned int block_order = gpu_buddy_block_order(block) - 1;
>> u64 offset = gpu_buddy_block_offset(block);
>> + enum gpu_block_state parent_state;
>> BUG_ON(!gpu_buddy_block_is_free(block));
>> BUG_ON(!gpu_buddy_block_order(block));
>> @@ -547,17 +1037,18 @@ static int split_block(struct gpu_buddy *mm,
>> return -ENOMEM;
>> }
>> + parent_state = gpu_block_cached_state(block);
>> +
>> mark_split(mm, block);
>> - if (gpu_buddy_block_is_clear(block)) {
>> - mark_cleared(block->left);
>> - mark_cleared(block->right);
>> - clear_reset(block);
>> + if (parent_state == GPU_BLOCK_MIXED) {
>> + mark_free(mm, block->left);
>> + mark_free(mm, block->right);
>> + } else {
>> + __mark_free(mm, block->left, parent_state);
>> + __mark_free(mm, block->right, parent_state);
>> }
>> - mark_free(mm, block->left);
>> - mark_free(mm, block->right);
>> -
>> return 0;
>> }
>> @@ -572,45 +1063,55 @@ static int split_block(struct gpu_buddy *mm,
>> */
>> void gpu_buddy_reset_clear(struct gpu_buddy *mm, bool is_clear)
>> {
>> - enum gpu_buddy_free_tree src_tree, dst_tree;
>> - u64 root_size, size, start;
>> - unsigned int order;
>> - int i;
>> + unsigned int i;
>> gpu_buddy_driver_lock_held(mm);
>> - size = mm->size;
>> - for (i = 0; i < mm->n_roots; ++i) {
>> - order = ilog2(size) - ilog2(mm->chunk_size);
>> - start = gpu_buddy_block_offset(mm->roots[i]);
>> - __force_merge(mm, start, start + size, order);
>> - root_size = mm->chunk_size << order;
>> - size -= root_size;
>> - }
>> -
>> - src_tree = is_clear ? GPU_BUDDY_DIRTY_TREE : GPU_BUDDY_CLEAR_TREE;
>> - dst_tree = is_clear ? GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE;
>> + gpu_dirty_tracker_empty(&mm->dirty);
>> for (i = 0; i <= mm->max_order; ++i) {
>> - struct rb_root *root = &mm->free_trees[src_tree][i];
>> struct gpu_buddy_block *block, *tmp;
>> - rbtree_postorder_for_each_entry_safe(block, tmp, root, rb) {
>> - rbtree_remove(mm, block);
>> + rbtree_postorder_for_each_entry_safe(block, tmp,
>> + &mm->free_tree[i], rb) {
>> if (is_clear) {
>> - mark_cleared(block);
>> - mm->clear_avail += gpu_buddy_block_size(mm, block);
>> + if (!gpu_buddy_block_is_clear(block))
>> + block->header |= GPU_BUDDY_HEADER_CLEAR;
>> + block->has_clear = true;
>> + } else if (gpu_buddy_block_is_clear(block)) {
>> + block->header &= ~GPU_BUDDY_HEADER_CLEAR;
>> + block->has_clear = false;
>> + gpu_dirty_tracker_mark_dirty(&mm->dirty,
>> + gpu_buddy_block_offset(block),
>> + gpu_buddy_block_size(mm, block));
>> } else {
>> - clear_reset(block);
>> - mm->clear_avail -= gpu_buddy_block_size(mm, block);
>> + block->has_clear = false;
>> + gpu_dirty_tracker_mark_dirty(&mm->dirty,
>> + gpu_buddy_block_offset(block),
>> + gpu_buddy_block_size(mm, block));
>> }
>> - rbtree_insert(mm, block, dst_tree);
>> + gpu_buddy_augment_compute(block);
>> }
>> }
>> +
>> + gpu_buddy_sync_clear_avail(mm);
>> }
>> EXPORT_SYMBOL(gpu_buddy_reset_clear);
>> +static void __gpu_buddy_free_block_internal(struct gpu_buddy *mm,
>> + struct gpu_buddy_block *block)
>> +{
>> + u64 size = gpu_buddy_block_size(mm, block);
>> +
>> + gpu_buddy_driver_lock_held(mm);
>> + BUG_ON(!gpu_buddy_block_is_allocated(block));
>> +
>> + mm->avail += size;
>> + gpu_buddy_sync_clear_avail(mm);
>> + __gpu_buddy_free(mm, block);
>> +}
>> +
>> /**
>> * gpu_buddy_free_block - free a block
>> *
>> @@ -620,13 +1121,12 @@ EXPORT_SYMBOL(gpu_buddy_reset_clear);
>> void gpu_buddy_free_block(struct gpu_buddy *mm,
>> struct gpu_buddy_block *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);
>> + if (!gpu_buddy_block_is_clear(block))
>> + gpu_dirty_tracker_mark_dirty(&mm->dirty,
>> + gpu_buddy_block_offset(block),
>> + gpu_buddy_block_size(mm, block));
>> - __gpu_buddy_free(mm, block, false);
>> + __gpu_buddy_free_block_internal(mm, block);
>> }
>> EXPORT_SYMBOL(gpu_buddy_free_block);
>> @@ -689,17 +1189,48 @@ static void __gpu_buddy_free_list(struct
>> gpu_buddy *mm,
>> bool mark_dirty)
>> {
>> struct gpu_buddy_block *block, *on;
>> + u64 dirty_start = 0, dirty_size = 0;
>> gpu_buddy_assert(!(mark_dirty && mark_clear));
>> list_for_each_entry_safe(block, on, objects, link) {
>> + u64 offset = gpu_buddy_block_offset(block);
>> + u64 size = gpu_buddy_block_size(mm, block);
>> +
>> if (mark_clear)
>> - mark_cleared(block);
>> + block->header |= GPU_BUDDY_HEADER_CLEAR;
>> else if (mark_dirty)
>> - clear_reset(block);
>> - gpu_buddy_free_block(mm, block);
>> + block->header &= ~GPU_BUDDY_HEADER_CLEAR;
>> +
>> + /*
>> + * Coalesce contiguous dirty blocks into one extent update so
>> + * a multi-block contiguous free costs a single mark_dirty().
>> + * Flush the pending extent and start over on a gap.
>> + */
>> + if (!gpu_buddy_block_is_clear(block)) {
>> + if (dirty_size &&
>> + (dirty_start + dirty_size == offset ||
>> + offset + size == dirty_start)) {
>> + dirty_start = min(dirty_start, offset);
>> + dirty_size += size;
>> + } else {
>> + if (dirty_size)
>> + gpu_dirty_tracker_mark_dirty(&mm->dirty,
>> + dirty_start,
>> + dirty_size);
>> + dirty_start = offset;
>> + dirty_size = size;
>> + }
>> + }
>> +
>> + __gpu_buddy_free_block_internal(mm, block);
>> cond_resched();
>> }
>> +
>> + if (dirty_size)
>> + gpu_dirty_tracker_mark_dirty(&mm->dirty, dirty_start,
>> dirty_size);
>> +
>> + gpu_buddy_sync_clear_avail(mm);
>> INIT_LIST_HEAD(objects);
>> }
>> @@ -732,13 +1263,6 @@ void gpu_buddy_free_list(struct gpu_buddy *mm,
>> }
>> EXPORT_SYMBOL(gpu_buddy_free_list);
>> -static bool block_incompatible(struct gpu_buddy_block *block,
>> unsigned int flags)
>> -{
>> - bool needs_clear = flags & GPU_BUDDY_CLEAR_ALLOCATION;
>> -
>> - return needs_clear != gpu_buddy_block_is_clear(block);
>> -}
>> -
>> static void __gpu_buddy_undo_splits(struct gpu_buddy *mm,
>> struct gpu_buddy_block *block)
>> {
>> @@ -749,7 +1273,7 @@ static void __gpu_buddy_undo_splits(struct
>> gpu_buddy *mm,
>> gpu_buddy_block_is_free(buddy))) {
>> rbtree_remove(mm, block);
>> mm->free_scoreboard[gpu_buddy_block_order(block)]--;
>> - __gpu_buddy_free(mm, block, false);
>> + __gpu_buddy_free(mm, block);
>> }
>> }
>> @@ -757,8 +1281,7 @@ static struct gpu_buddy_block *
>> __alloc_range_bias(struct gpu_buddy *mm,
>> u64 start, u64 end,
>> unsigned int order,
>> - unsigned long flags,
>> - bool fallback)
>> + unsigned long flags)
>> {
>> u64 req_size = mm->chunk_size << order;
>> struct gpu_buddy_block *block;
>> @@ -768,7 +1291,15 @@ __alloc_range_bias(struct gpu_buddy *mm,
>> end = end - 1;
>> - for (i = 0; i < mm->n_roots; ++i)
>> + /*
>> + * This range-constrained search hands back the highest/right-most
>> + * address that satisfies the request: the roots are seeded high-
>> to-low
>> + * and the right (higher-address) child is descended first, making
>> + * top-down the default placement here. A non-top-down clear
>> request is
>> + * the only exception, where the descent is biased towards clear or
>> + * clear-containing subtrees to satisfy the clear preference.
>> + */
>> + for (i = mm->n_roots - 1; i >= 0; --i)
>> list_add_tail(&mm->roots[i]->tmp_link, &dfs);
>> do {
>> @@ -804,9 +1335,6 @@ __alloc_range_bias(struct gpu_buddy *mm,
>> continue;
>> }
>> - if (!fallback && block_incompatible(block, flags))
>> - continue;
>> -
>> if (contains(start, end, block_start, block_end) &&
>> order == gpu_buddy_block_order(block)) {
>> /*
>> @@ -824,8 +1352,38 @@ __alloc_range_bias(struct gpu_buddy *mm,
>> goto err_undo;
>> }
>> - list_add(&block->right->tmp_link, &dfs);
>> - list_add(&block->left->tmp_link, &dfs);
>> + /*
>> + * Top-down is a strict address-placement policy, so when it is
>> + * requested we ignore clear steering and simply descend the
>> + * right (higher-address) child first. Only a non-top-down clear
>> + * request biases the descent towards clear/has_clear subtrees.
>> + */
>> + if ((flags & GPU_BUDDY_CLEAR_ALLOCATION) &&
>> + !(flags & GPU_BUDDY_TOPDOWN_ALLOCATION)) {
>> + struct gpu_buddy_block *prefer;
>> +
>> + if (gpu_buddy_block_is_clear(block->right))
>> + prefer = block->right;
>> + else if (gpu_buddy_block_is_clear(block->left))
>> + prefer = block->left;
>> + else if (block->right->has_clear)
>> + prefer = block->right;
>> + else if (block->left->has_clear)
>> + prefer = block->left;
>> + else
>> + prefer = block->right;
>> +
>> + if (prefer == block->right) {
>> + list_add(&block->left->tmp_link, &dfs);
>> + list_add(&block->right->tmp_link, &dfs);
>> + } else {
>> + list_add(&block->right->tmp_link, &dfs);
>> + list_add(&block->left->tmp_link, &dfs);
>> + }
>> + } else {
>> + list_add(&block->left->tmp_link, &dfs);
>> + list_add(&block->right->tmp_link, &dfs);
>> + }
>> } while (1);
>> return ERR_PTR(-ENOSPC);
>> @@ -840,48 +1398,32 @@ __alloc_range_bias(struct gpu_buddy *mm,
>> return ERR_PTR(err);
>> }
>> -static struct gpu_buddy_block *
>> -__gpu_buddy_alloc_range_bias(struct gpu_buddy *mm,
>> - u64 start, u64 end,
>> - unsigned int order,
>> - unsigned long flags)
>> -{
>> - struct gpu_buddy_block *block;
>> - bool fallback = false;
>> -
>> - block = __alloc_range_bias(mm, start, end, order,
>> - flags, fallback);
>> - if (IS_ERR(block))
>> - return __alloc_range_bias(mm, start, end, order,
>> - flags, !fallback);
>> -
>> - return block;
>> -}
>> -
>> +/* Return the highest-address free block of at least @order. */
>> static struct gpu_buddy_block *
>> get_maxblock(struct gpu_buddy *mm,
>> - unsigned int order,
>> - enum gpu_buddy_free_tree tree)
>> + unsigned int order)
>> {
>> - struct gpu_buddy_block *max_block = NULL, *block = NULL;
>> - struct rb_root *root;
>> + struct gpu_buddy_block *max_block;
>> + struct gpu_buddy_block *block;
>> unsigned int i;
>> + /*
>> + * Top-down allocation is a strict address-placement policy: the
>> block
>> + * is chosen purely by offset, regardless of its clear/dirty state.
>> + * Clear state is re-derived from the dirty tracker once the
>> allocation
>> + * completes, and the driver is responsible for issuing the clear
>> pass
>> + * if a clear region is required.
>> + */
>> + max_block = NULL;
>> +
>> for (i = order; i <= mm->max_order; ++i) {
>> - root = &mm->free_trees[tree][i];
>> - block = rbtree_last_free_block(root);
>> + block = rbtree_last_free_block(&mm->free_tree[i]);
>> if (!block)
>> continue;
>> - if (!max_block) {
>> + if (!max_block ||
>> + gpu_buddy_block_offset(block) >
>> gpu_buddy_block_offset(max_block))
>> max_block = block;
>> - continue;
>> - }
>> -
>> - if (gpu_buddy_block_offset(block) >
>> - gpu_buddy_block_offset(max_block)) {
>> - max_block = block;
>> - }
>> }
>> return max_block;
>> @@ -893,45 +1435,34 @@ alloc_from_freetree(struct gpu_buddy *mm,
>> unsigned long flags)
>> {
>> struct gpu_buddy_block *block = NULL;
>> - struct rb_root *root;
>> - enum gpu_buddy_free_tree tree;
>> unsigned int tmp;
>> int err;
>> - tree = (flags & GPU_BUDDY_CLEAR_ALLOCATION) ?
>> - GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE;
>> -
>> if (flags & GPU_BUDDY_TOPDOWN_ALLOCATION) {
>> - block = get_maxblock(mm, order, tree);
>> + block = get_maxblock(mm, order);
>> if (block)
>> - /* Store the obtained block order */
>> tmp = gpu_buddy_block_order(block);
>> } else {
>> - for (tmp = order; tmp <= mm->max_order; ++tmp) {
>> - /* Get RB tree root for this order and tree */
>> - root = &mm->free_trees[tree][tmp];
>> - block = rbtree_last_free_block(root);
>> - if (block)
>> - break;
>> + if (flags & GPU_BUDDY_CLEAR_ALLOCATION) {
>> + for (tmp = order; tmp <= mm->max_order; ++tmp) {
>> + block = rbtree_last_clear_free_block(&mm-
>> >free_tree[tmp],
>> + GPU_BLOCK_MIXED);
>> + if (block)
>> + break;
>> + }
>> }
>> - }
>> -
>> - if (!block) {
>> - /* Try allocating from the other tree */
>> - tree = (tree == GPU_BUDDY_CLEAR_TREE) ?
>> - GPU_BUDDY_DIRTY_TREE : GPU_BUDDY_CLEAR_TREE;
>> -
>> - for (tmp = order; tmp <= mm->max_order; ++tmp) {
>> - root = &mm->free_trees[tree][tmp];
>> - block = rbtree_last_free_block(root);
>> - if (block)
>> - break;
>> + if (!block) {
>> + for (tmp = order; tmp <= mm->max_order; ++tmp) {
>> + block = rbtree_last_free_block(&mm->free_tree[tmp]);
>> + if (block)
>> + break;
>> + }
>> }
>> -
>> - if (!block)
>> - return ERR_PTR(-ENOSPC);
>> }
>> + if (!block)
>> + return ERR_PTR(-ENOSPC);
>> +
>> BUG_ON(!gpu_buddy_block_is_free(block));
>> while (tmp != order) {
>> @@ -939,7 +1470,26 @@ alloc_from_freetree(struct gpu_buddy *mm,
>> if (unlikely(err))
>> goto err_undo;
>> - block = block->right;
>> + if ((flags & GPU_BUDDY_CLEAR_ALLOCATION) &&
>> + !(flags & GPU_BUDDY_TOPDOWN_ALLOCATION)) {
>> + bool right_clear, left_clear;
>> +
>> + right_clear = gpu_buddy_block_is_clear(block->right);
>> + left_clear = gpu_buddy_block_is_clear(block->left);
>> +
>> + if (right_clear)
>> + block = block->right;
>> + else if (left_clear)
>> + block = block->left;
>> + else if (block->right->has_clear)
>> + block = block->right;
>> + else if (block->left->has_clear)
>> + block = block->left;
>> + else
>> + block = block->right;
>> + } else {
>> + block = block->right;
>> + }
>> tmp--;
>> }
>> return block;
>> @@ -966,12 +1516,10 @@ static bool
>> gpu_buddy_subtree_can_satisfy(struct rb_node *node,
>> static struct gpu_buddy_block *
>> gpu_buddy_find_block_aligned(struct gpu_buddy *mm,
>> - enum gpu_buddy_free_tree tree,
>> unsigned int order,
>> - unsigned int alignment,
>> - unsigned long flags)
>> + unsigned int alignment)
>> {
>> - struct rb_root *root = &mm->free_trees[tree][order];
>> + struct rb_root *root = &mm->free_tree[order];
>> struct rb_node *rb = root->rb_node;
>> while (rb) {
>> @@ -1004,12 +1552,10 @@ gpu_buddy_find_block_aligned(struct gpu_buddy
>> *mm,
>> static struct gpu_buddy_block *
>> gpu_buddy_offset_aligned_allocation(struct gpu_buddy *mm,
>> u64 size,
>> - u64 min_block_size,
>> - unsigned long flags)
>> + u64 min_block_size)
>> {
>> struct gpu_buddy_block *block = NULL;
>> unsigned int order, tmp, alignment;
>> - enum gpu_buddy_free_tree tree;
>> unsigned long pages;
>> int err;
>> @@ -1017,19 +1563,15 @@ gpu_buddy_offset_aligned_allocation(struct
>> gpu_buddy *mm,
>> pages = size >> ilog2(mm->chunk_size);
>> order = fls(pages) - 1;
>> - tree = (flags & GPU_BUDDY_CLEAR_ALLOCATION) ?
>> - GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE;
>> -
>> + /*
>> + * Offset-aligned allocation is a strict address-placement
>> policy: the
>> + * block is chosen purely by its offset alignment, regardless of its
>> + * clear/dirty state. Clear state is re-derived from the dirty
>> tracker
>> + * once the allocation completes, and the driver is responsible for
>> + * issuing the clear pass if a clear region is required.
>> + */
>> for (tmp = order; tmp <= mm->max_order; ++tmp) {
>> - block = gpu_buddy_find_block_aligned(mm, tree, tmp,
>> - alignment, flags);
>> - if (!block) {
>> - tree = (tree == GPU_BUDDY_CLEAR_TREE) ?
>> - GPU_BUDDY_DIRTY_TREE : GPU_BUDDY_CLEAR_TREE;
>> - block = gpu_buddy_find_block_aligned(mm, tree, tmp,
>> - alignment, flags);
>> - }
>> -
>> + block = gpu_buddy_find_block_aligned(mm, tmp, alignment);
>> if (block)
>> break;
>> }
>> @@ -1068,6 +1610,7 @@ gpu_buddy_offset_aligned_allocation(struct
>> gpu_buddy *mm,
>> static int __alloc_range(struct gpu_buddy *mm,
>> struct list_head *dfs,
>> u64 start, u64 size,
>> + unsigned long flags,
>> struct list_head *blocks,
>> u64 *total_allocated_on_err)
>> {
>> @@ -1104,16 +1647,33 @@ static int __alloc_range(struct gpu_buddy *mm,
>> if (contains(start, end, block_start, block_end)) {
>> if (gpu_buddy_block_is_free(block)) {
>> + bool block_clear = false;
>> + u64 block_offset;
>> + u64 block_size;
>> +
>> + block_size = gpu_buddy_block_size(mm, block);
>> + block_offset = gpu_buddy_block_offset(block);
>> +
>> + if (flags & GPU_BUDDY_CLEAR_ALLOCATION)
>> + block_clear = gpu_buddy_block_is_clear(block);
>> +
>> + if (!gpu_buddy_block_is_clear(block))
>> + gpu_dirty_tracker_remove_range(&mm->dirty,
>> + block_offset,
>> + block_size);
>> +
>> mark_allocated(mm, block);
>> - total_allocated += gpu_buddy_block_size(mm, 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);
>> + total_allocated += block_size;
>> + mm->avail -= block_size;
>> +
>> + block->header &= ~GPU_BUDDY_HEADER_CLEAR;
>> + if (block_clear)
>> + block->header |= GPU_BUDDY_HEADER_CLEAR;
>> +
>> + gpu_buddy_sync_clear_avail(mm);
>> +
>> list_add_tail(&block->link, &allocated);
>> continue;
>> - } else if (!mm->clear_avail) {
>> - err = -ENOSPC;
>> - goto err_free;
>> }
>> }
>> @@ -1158,6 +1718,7 @@ static int __alloc_range(struct gpu_buddy *mm,
>> static int __gpu_buddy_alloc_range(struct gpu_buddy *mm,
>> u64 start,
>> u64 size,
>> + unsigned long flags,
>> u64 *total_allocated_on_err,
>> struct list_head *blocks)
>> {
>> @@ -1167,20 +1728,23 @@ static int __gpu_buddy_alloc_range(struct
>> gpu_buddy *mm,
>> for (i = 0; i < mm->n_roots; ++i)
>> list_add_tail(&mm->roots[i]->tmp_link, &dfs);
>> - return __alloc_range(mm, &dfs, start, size,
>> + return __alloc_range(mm, &dfs, start, size, flags,
>> blocks, total_allocated_on_err);
>> }
>> static int __alloc_contig_try_harder(struct gpu_buddy *mm,
>> u64 size,
>> u64 min_block_size,
>> + unsigned long flags,
>> struct list_head *blocks)
>> {
>> u64 rhs_offset, lhs_offset, lhs_size, filled;
>> struct gpu_buddy_block *block;
>> - unsigned int tree, order;
>> LIST_HEAD(blocks_lhs);
>> + struct rb_root *root;
>> + struct rb_node *iter;
>> unsigned long pages;
>> + unsigned int order;
>> u64 modify_size;
>> int err;
>> @@ -1190,45 +1754,40 @@ static int __alloc_contig_try_harder(struct
>> gpu_buddy *mm,
>> if (order == 0)
>> return -ENOSPC;
>> - for_each_free_tree(tree) {
>> - struct rb_root *root;
>> - struct rb_node *iter;
>> -
>> - root = &mm->free_trees[tree][order];
>> - if (rbtree_is_empty(root))
>> - continue;
>> + root = &mm->free_tree[order];
>> + if (RB_EMPTY_ROOT(root))
>> + return -ENOSPC;
>> - iter = rb_last(root);
>> - while (iter) {
>> - block = rbtree_get_free_block(iter);
>> -
>> - /* Allocate blocks traversing RHS */
>> - rhs_offset = gpu_buddy_block_offset(block);
>> - err = __gpu_buddy_alloc_range(mm, rhs_offset, size,
>> - &filled, blocks);
>> - if (!err || err != -ENOSPC)
>> - return err;
>> -
>> - lhs_size = max((size - filled), min_block_size);
>> - if (!IS_ALIGNED(lhs_size, min_block_size))
>> - lhs_size = round_up(lhs_size, min_block_size);
>> -
>> - /* Allocate blocks traversing LHS */
>> - lhs_offset = gpu_buddy_block_offset(block) - lhs_size;
>> - err = __gpu_buddy_alloc_range(mm, lhs_offset, lhs_size,
>> - NULL, &blocks_lhs);
>> - if (!err) {
>> - list_splice(&blocks_lhs, blocks);
>> - return 0;
>> - } else if (err != -ENOSPC) {
>> - gpu_buddy_free_list_internal(mm, blocks);
>> - return err;
>> - }
>> - /* Free blocks for the next iteration */
>> + iter = rb_last(root);
>> + while (iter) {
>> + block = rbtree_get_free_block(iter);
>> +
>> + /* Allocate blocks traversing RHS */
>> + rhs_offset = gpu_buddy_block_offset(block);
>> + err = __gpu_buddy_alloc_range(mm, rhs_offset, size,
>> + flags, &filled, blocks);
>> + if (!err || err != -ENOSPC)
>> + return err;
>> +
>> + lhs_size = max((size - filled), min_block_size);
>> + if (!IS_ALIGNED(lhs_size, min_block_size))
>> + lhs_size = round_up(lhs_size, min_block_size);
>> +
>> + /* Allocate blocks traversing LHS */
>> + lhs_offset = gpu_buddy_block_offset(block) - lhs_size;
>> + err = __gpu_buddy_alloc_range(mm, lhs_offset, lhs_size,
>> + flags, NULL, &blocks_lhs);
>> + if (!err) {
>> + list_splice(&blocks_lhs, blocks);
>> + return 0;
>> + } else if (err != -ENOSPC) {
>> gpu_buddy_free_list_internal(mm, blocks);
>> -
>> - iter = rb_prev(iter);
>> + return err;
>> }
>> + /* Free blocks for the next iteration */
>> + gpu_buddy_free_list_internal(mm, blocks);
>> +
>> + iter = rb_prev(iter);
>> }
>> return -ENOSPC;
>> @@ -1262,6 +1821,7 @@ int gpu_buddy_block_trim(struct gpu_buddy *mm,
>> struct gpu_buddy_block *block;
>> u64 block_start, block_end;
>> LIST_HEAD(dfs);
>> + bool was_clear;
>> u64 new_start;
>> int err;
>> @@ -1304,22 +1864,38 @@ int gpu_buddy_block_trim(struct gpu_buddy *mm,
>> }
>> list_del(&block->link);
>> - mark_free(mm, block);
>> +
>> + was_clear = gpu_buddy_block_is_clear(block);
>> + block->header &= ~GPU_BUDDY_HEADER_CLEAR;
>> +
>> + if (!was_clear)
>> + gpu_dirty_tracker_mark_dirty(&mm->dirty,
>> + gpu_buddy_block_offset(block),
>> + gpu_buddy_block_size(mm, block));
>> +
>> + __mark_free(mm, block, was_clear ? GPU_BLOCK_CLEAR :
>> GPU_BLOCK_DIRTY);
>> 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_sync_clear_avail(mm);
>> /* Prevent recursively freeing this node */
>> parent = block->parent;
>> block->parent = NULL;
>> list_add(&block->tmp_link, &dfs);
>> - err = __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL);
>> + err = __alloc_range(mm, &dfs, new_start, new_size,
>> + was_clear ? GPU_BUDDY_CLEAR_ALLOCATION : 0,
>> + blocks, NULL);
>> if (err) {
>> mark_allocated(mm, 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);
>> + if (!was_clear) {
>> + gpu_dirty_tracker_remove_range(&mm->dirty,
>> + gpu_buddy_block_offset(block),
>> + gpu_buddy_block_size(mm, block));
>> + }
>> + if (was_clear)
>> + block->header |= GPU_BUDDY_HEADER_CLEAR;
>> + gpu_buddy_sync_clear_avail(mm);
>> list_add(&block->link, blocks);
>> }
>> @@ -1328,6 +1904,22 @@ int gpu_buddy_block_trim(struct gpu_buddy *mm,
>> }
>> EXPORT_SYMBOL(gpu_buddy_block_trim);
>> +static bool dirty_steer_window(struct gpu_buddy *mm, u64 req_size,
>> + u64 *start, u64 *end, unsigned long *flags)
>> +{
>> + u64 aligned_start;
>> + struct gpu_dirty_extent *ext =
>> + gpu_dirty_tracker_find(&mm->dirty, req_size, &aligned_start);
>> +
>> + if (!ext)
>> + return false;
>> +
>> + *start = aligned_start;
>> + *end = ext->end;
>> + *flags |= GPU_BUDDY_RANGE_ALLOCATION;
>> + return true;
>> +}
>> +
>> static struct gpu_buddy_block *
>> __gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
>> u64 start, u64 end,
>> @@ -1335,18 +1927,36 @@ __gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
>> unsigned int order,
>> unsigned long flags)
>> {
>> - if (flags & GPU_BUDDY_RANGE_ALLOCATION)
>> + struct gpu_buddy_block *block;
>> + bool steered = false;
>> +
>> + /* Allocate from dirty tracker */
>> + if (!(flags & GPU_BUDDY_RANGE_ALLOCATION) &&
>> + !(flags & GPU_BUDDY_CLEAR_ALLOCATION) &&
>> + size >= min_block_size &&
>> + mm->clear_avail && mm->dirty.total_dirty) {
>> + u64 block_size = mm->chunk_size << order;
>> +
>> + steered = dirty_steer_window(mm, block_size,
>> + &start, &end, &flags);
>> + }
>> +
>> + if (flags & GPU_BUDDY_RANGE_ALLOCATION) {
>> /* Allocate traversing within the range */
>> - return __gpu_buddy_alloc_range_bias(mm, start, end,
>> - order, flags);
>> - else if (size < min_block_size)
>> + block = __alloc_range_bias(mm, start, end, order, flags);
>> + if (!IS_ERR(block) || !steered)
>> + return block;
>> +
>> + flags &= ~GPU_BUDDY_RANGE_ALLOCATION;
>> + }
>> +
>> + if (size < min_block_size)
>> /* Allocate from an offset-aligned region without size
>> rounding */
>> return gpu_buddy_offset_aligned_allocation(mm, size,
>> - min_block_size,
>> - flags);
>> - else
>> - /* Allocate from freetree */
>> - return alloc_from_freetree(mm, order, flags);
>> + min_block_size);
>> +
>> + /* Allocate from freetree */
>> + return alloc_from_freetree(mm, order, flags);
>> }
>> /**
>> @@ -1407,7 +2017,7 @@ int gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
>> if (!IS_ALIGNED(start | end, min_block_size))
>> return -EINVAL;
>> - return __gpu_buddy_alloc_range(mm, start, size, NULL, blocks);
>> + return __gpu_buddy_alloc_range(mm, start, size, flags, NULL,
>> blocks);
>> }
>> original_size = size;
>> @@ -1433,12 +2043,15 @@ int gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
>> if ((flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) &&
>> !(flags & GPU_BUDDY_RANGE_ALLOCATION))
>> return __alloc_contig_try_harder(mm, original_size,
>> - original_min_size, blocks);
>> + original_min_size,
>> + flags, blocks);
>> return -EINVAL;
>> }
>> do {
>> + bool block_clear = false;
>> +
>> order = min(order, (unsigned int)fls(pages) - 1);
>> BUG_ON(order > mm->max_order);
>> /*
>> @@ -1448,8 +2061,6 @@ int gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
>> BUG_ON(size >= min_block_size && order < min_order);
>> do {
>> - unsigned int fallback_order;
>> -
>> block = __gpu_buddy_alloc_blocks(mm, start,
>> end,
>> size,
>> @@ -1459,48 +2070,48 @@ int gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
>> if (!IS_ERR(block))
>> break;
>> - if (size < min_block_size) {
>> - fallback_order = order;
>> - } else if (order == min_order) {
>> - fallback_order = min_order;
>> - } else {
>> + if (size >= min_block_size && order > min_order) {
>> order--;
>> continue;
>> }
>> - /* Try allocation through force merge method */
>> - if (mm->clear_avail &&
>> - !__force_merge(mm, start, end, fallback_order)) {
>> - block = __gpu_buddy_alloc_blocks(mm, start,
>> - end,
>> - size,
>> - min_block_size,
>> - fallback_order,
>> - flags);
>> - if (!IS_ERR(block)) {
>> - order = fallback_order;
>> - break;
>> - }
>> - }
>> -
>> /*
>> * Try contiguous block allocation through
>> * try harder method.
>> */
>> if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION &&
>> - !(flags & GPU_BUDDY_RANGE_ALLOCATION))
>> - return __alloc_contig_try_harder(mm,
>> - original_size,
>> - original_min_size,
>> - blocks);
>> + !(flags & GPU_BUDDY_RANGE_ALLOCATION)) {
>> + err = __alloc_contig_try_harder(mm,
>> + original_size,
>> + original_min_size,
>> + flags,
>> + blocks);
>> + if (!err)
>> + return 0;
>> + if (err != -ENOSPC)
>> + return err;
>> + goto err_free;
>> + }
>> err = -ENOSPC;
>> goto err_free;
>> } while (1);
>> + if (flags & GPU_BUDDY_CLEAR_ALLOCATION)
>> + block_clear = gpu_buddy_block_is_clear(block);
>> +
>> + if (!gpu_buddy_block_is_clear(block))
>> + gpu_dirty_tracker_remove_range(&mm->dirty,
>> + gpu_buddy_block_offset(block),
>> + gpu_buddy_block_size(mm, block));
>> +
>> mark_allocated(mm, 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);
>> +
>> + block->header &= ~GPU_BUDDY_HEADER_CLEAR;
>> + if (block_clear)
>> + block->header |= GPU_BUDDY_HEADER_CLEAR;
>> +
>> + gpu_buddy_sync_clear_avail(mm);
>> kmemleak_update_trace(block);
>> list_add_tail(&block->link, &allocated);
>> @@ -1595,6 +2206,7 @@ EXPORT_SYMBOL(gpu_buddy_print);
>> static void gpu_buddy_module_exit(void)
>> {
>> + kmem_cache_destroy(slab_extents);
>> kmem_cache_destroy(slab_blocks);
>> }
>> @@ -1604,7 +2216,15 @@ static int __init gpu_buddy_module_init(void)
>> if (!slab_blocks)
>> return -ENOMEM;
>> + slab_extents = KMEM_CACHE(gpu_dirty_extent, 0);
>> + if (!slab_extents)
>> + goto err_destroy_blocks;
>> +
>> return 0;
>> +
>> +err_destroy_blocks:
>> + kmem_cache_destroy(slab_blocks);
>> + return -ENOMEM;
>> }
>> module_init(gpu_buddy_module_init);
>> diff --git a/drivers/gpu/tests/gpu_buddy_test.c b/drivers/gpu/tests/
>> gpu_buddy_test.c
>> index ed4c1c3acb3c..198d8dc4e3f0 100644
>> --- a/drivers/gpu/tests/gpu_buddy_test.c
>> +++ b/drivers/gpu/tests/gpu_buddy_test.c
>> @@ -38,7 +38,7 @@ static void
>> gpu_test_buddy_subtree_offset_alignment_stress(struct kunit *test)
>> };
>> struct list_head allocated[ARRAY_SIZE(alignments)];
>> unsigned int i, max_subtree_align = 0;
>> - int ret, tree, order;
>> + int ret, order;
>> struct gpu_buddy mm;
>> KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K),
>> @@ -78,15 +78,11 @@ static void
>> gpu_test_buddy_subtree_offset_alignment_stress(struct kunit *test)
>> }
>> for (order = mm.max_order; order >= 0 && !root; order--) {
>> - for (tree = 0; tree < 2; tree++) {
>> - node = mm.free_trees[tree][order].rb_node;
>> - if (node) {
>> - root = container_of(node,
>> - struct gpu_buddy_block,
>> - rb);
>> - break;
>> - }
>> - }
>> + node = mm.free_tree[order].rb_node;
>> + if (node)
>> + root = container_of(node,
>> + struct gpu_buddy_block,
>> + rb);
>> }
>> KUNIT_ASSERT_NOT_NULL(test, root);
>> @@ -97,15 +93,13 @@ static void
>> gpu_test_buddy_subtree_offset_alignment_stress(struct kunit *test)
>> gpu_buddy_free_list(&mm, &allocated[i], 0);
>> for (order = 0; order <= mm.max_order; order++) {
>> - for (tree = 0; tree < 2; tree++) {
>> - node = mm.free_trees[tree][order].rb_node;
>> - if (!node)
>> - continue;
>> -
>> - block = container_of(node, struct gpu_buddy_block, rb);
>> - max_subtree_align = max(max_subtree_align,
>> - block->subtree_max_alignment);
>> - }
>> + node = mm.free_tree[order].rb_node;
>> + if (!node)
>> + continue;
>> +
>> + block = container_of(node, struct gpu_buddy_block, rb);
>> + max_subtree_align = max(max_subtree_align,
>> + block->subtree_max_alignment);
>> }
>> KUNIT_EXPECT_GE(test, max_subtree_align, ilog2(alignments[i]));
>> diff --git a/include/linux/gpu_buddy.h b/include/linux/gpu_buddy.h
>> index 2c36124bb696..1fe7b61db484 100644
>> --- a/include/linux/gpu_buddy.h
>> +++ b/include/linux/gpu_buddy.h
>> @@ -8,6 +8,7 @@
>> #include <linux/bitops.h>
>> #include <linux/list.h>
>> +#include <linux/mempool.h>
>> #include <linux/slab.h>
>> #include <linux/sched.h>
>> #include <linux/rbtree.h>
>> @@ -43,8 +44,8 @@
>> /**
>> * GPU_BUDDY_CLEAR_ALLOCATION - Prefer pre-cleared (zeroed) memory
>> *
>> - * Attempt to allocate from the clear tree first. If insufficient clear
>> - * memory is available, falls back to dirty memory. Useful when the
>> + * Attempt to allocate outside dirty-tracked ranges first. If
>> insufficient
>> + * clear memory is available, falls back to dirty memory. Useful when
>> the
>> * caller needs zeroed memory and wants to avoid GPU clear operations.
>> */
>> #define GPU_BUDDY_CLEAR_ALLOCATION BIT(3)
>> @@ -53,8 +54,8 @@
>> * GPU_BUDDY_CLEARED - Mark returned blocks as cleared
>> *
>> * Used with gpu_buddy_free_list() to indicate that the memory being
>> - * freed has been cleared (zeroed). The blocks will be placed in the
>> - * clear tree for future GPU_BUDDY_CLEAR_ALLOCATION requests.
>> + * freed has been cleared (zeroed). The blocks will be removed from the
>> + * dirty tracker for future GPU_BUDDY_CLEAR_ALLOCATION requests.
>> */
>> #define GPU_BUDDY_CLEARED BIT(4)
>> @@ -67,15 +68,6 @@
>> */
>> #define GPU_BUDDY_TRIM_DISABLE BIT(5)
>> -enum gpu_buddy_free_tree {
>> - GPU_BUDDY_CLEAR_TREE = 0,
>> - GPU_BUDDY_DIRTY_TREE,
>> - GPU_BUDDY_MAX_FREE_TREES,
>> -};
>> -
>> -#define for_each_free_tree(tree) \
>> - for ((tree) = 0; (tree) < GPU_BUDDY_MAX_FREE_TREES; (tree)++)
>> -
>> /**
>> * struct gpu_buddy_block - Block within a buddy allocator
>> *
>> @@ -88,6 +80,17 @@ enum gpu_buddy_free_tree {
>> * @private: Private data owned by the allocator user (e.g., driver-
>> specific data)
>> * @link: List node for user ownership while block is allocated
>> */
>> +/*
>> + * Clear/dirty state of a free block. Ordered so a numerically larger
>> value
>> + * is "more clear" (DIRTY < MIXED < CLEAR) which lets
>> subtree_block_state be
>> + * maintained as a simple max-augment over the per-order free tree.
>> + */
>> +enum gpu_block_state {
>> + GPU_BLOCK_DIRTY = 0,
>> + GPU_BLOCK_MIXED = 1,
>> + GPU_BLOCK_CLEAR = 2,
>> +};
>> +
>> struct gpu_buddy_block {
>> /* private: */
>> /*
>> @@ -103,6 +106,13 @@ struct gpu_buddy_block {
>> #define GPU_BUDDY_ALLOCATED (1 << 10)
>> #define GPU_BUDDY_FREE (2 << 10)
>> #define GPU_BUDDY_SPLIT (3 << 10)
>> +/*
>> + * GPU_BUDDY_HEADER_CLEAR has two roles:
>> + * - FREE state: set when the block's full range is cleared (dirty
>> + * tracker confirmed no overlap).
>> + * - ALLOCATED state: set when the block was served from cleared
>> memory,
>> + * informing the caller that no GPU clear pass is
>> needed.
>> + */
>> #define GPU_BUDDY_HEADER_CLEAR GENMASK_ULL(9, 9)
>> /* Free to be used, if needed in the future */
>> #define GPU_BUDDY_HEADER_UNUSED GENMASK_ULL(8, 6)
>> @@ -128,13 +138,51 @@ struct gpu_buddy_block {
>> struct list_head link;
>> };
>> /* private: */
>> - struct list_head tmp_link;
>> + enum gpu_block_state subtree_block_state;
>> unsigned int subtree_max_alignment;
>> + struct list_head tmp_link;
>> + bool has_clear;
>> };
>> /* Order-zero must be at least SZ_4K */
>> #define GPU_BUDDY_MAX_ORDER (63 - 12)
>> +/**
>> + * struct gpu_dirty_extent - a contiguous dirty address range
>> + *
>> + * Tracks a single contiguous address range whose memory content is
>> known
>> + * to be dirty. Extents are non-overlapping and stored in an augmented
>> + * red-black tree sorted by @start. The augmented value
>> @subtree_max_size
>> + * allows O(log N) search for an extent of at least a given size.
>> + */
>> +struct gpu_dirty_extent {
>> +/* private: */
>> + struct rb_node rb;
>> + u64 start;
>> + u64 end;
>> + u64 subtree_max_size;
>> +};
>> +
>> +/**
>> + * struct gpu_dirty_tracker - tracks dirty address intervals
>> + *
>> + * Maintains a set of non-overlapping dirty extents as an augmented
>> + * red-black tree.
>> + *
>> + * @total_dirty: Total bytes of dirty memory currently tracked.
>> + * @extent_pool: Mempool backing extent node allocations. sashiko
>> reported
>> + * that a __GFP_NOFAIL allocation on the free path could
>> + * deadlock during memory reclaim, so a per-tracker mempool is
>> + * used to guarantee extent nodes without __GFP_NOFAIL.
>> + */
>> +struct gpu_dirty_tracker {
>> +/* private: */
>> + struct rb_root root;
>> + mempool_t *extent_pool;
>> +/* public: */
>> + u64 total_dirty;
>> +};
>> +
>> /**
>> * struct gpu_buddy - GPU binary buddy allocator
>> *
>> @@ -152,20 +200,25 @@ struct gpu_buddy_block {
>> * @chunk_size: Minimum allocation granularity in bytes. Must be at
>> least SZ_4K.
>> * @size: Total size of the address space managed by this allocator
>> in bytes.
>> * @avail: Total free space currently available for allocation in
>> bytes.
>> - * @clear_avail: Free space available in the clear tree (zeroed
>> memory) in bytes.
>> - * This is a subset of @avail.
>> + * @clear_avail: Free space that is clear (zeroed) in bytes. A subset
>> of @avail.
>> + * Maintained as @avail - dirty.total_dirty, since the
>> tracker
>> + * records the dirty extents. Zero at init, as a fresh
>> pool is
>> + * fully dirty.
>> * @lock_dep_map: Annotates gpu_buddy API with a driver provided lock.
>> */
>> struct gpu_buddy {
>> /* private: */
>> + /* Tracker of dirty address ranges (decoupled from free_tree). */
>> + struct gpu_dirty_tracker dirty;
>> /*
>> - * Array of red-black trees for free block management.
>> - * Indexed as free_trees[clear/dirty][order] where:
>> - * - Index 0 (GPU_BUDDY_CLEAR_TREE): blocks with zeroed content
>> - * - Index 1 (GPU_BUDDY_DIRTY_TREE): blocks with unknown content
>> - * Each tree holds free blocks of the corresponding order.
>> + * One RB-tree per order containing all free blocks (clear and
>> + * dirty alike). The augment field subtree_block_state (a max over
>> + * the subtree of each block's state) lets clear allocations
>> + * find the right-most fully-clear or mixed block in O(log N).
>> + * Dirty free blocks coexist here but are also indexed by the
>> + * @dirty tracker for fast dirty allocation lookups.
>> */
>> - struct rb_root **free_trees;
>> + struct rb_root *free_tree;
>> /*
>> * Array of root blocks representing the top-level blocks of the
>> * binary tree(s). Multiple roots exist when the total size is not
>>
>> base-commit: b961eb36d7b04147104cff2fd8bc0e94f4713324
>
next prev parent reply other threads:[~2026-08-17 9:57 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-08-11 13:34 [PATCH v9 1/2] gpu/buddy: replace dual-tree/force_merge with decoupled dirty tracker Arunpravin Paneer Selvam
2026-08-11 13:34 ` [PATCH v9 2/2] gpu/tests/buddy: add dirty tracker performance KUnit test Arunpravin Paneer Selvam
2026-08-11 14:51 ` ✗ Fi.CI.BUILD: failure for series starting with [v9,1/2] gpu/buddy: replace dual-tree/force_merge with decoupled dirty tracker Patchwork
2026-08-13 13:37 ` [PATCH v9 1/2] " Arunpravin Paneer Selvam
2026-08-17 9:57 ` Matthew Auld [this message]
2026-08-17 12:53 ` Arunpravin Paneer Selvam
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=0b92672e-dee7-4ef1-83fd-ea9f31729eca@intel.com \
--to=matthew.auld@intel.com \
--cc=Anand.Raghavendra@amd.com \
--cc=alexander.deucher@amd.com \
--cc=amd-gfx@lists.freedesktop.org \
--cc=arunpravin.paneerselvam@amd.com \
--cc=christian.koenig@amd.com \
--cc=dri-devel@lists.freedesktop.org \
--cc=intel-gfx@lists.freedesktop.org \
--cc=intel-xe@lists.freedesktop.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox