mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: William Palacek <William.Palacek@amd.com>
To: <dri-devel@lists.freedesktop.org>
Cc: intel-xe@lists.freedesktop.org,
	"Matthew Auld" <matthew.auld@intel.com>,
	"Arunpravin Paneer Selvam" <Arunpravin.PaneerSelvam@amd.com>,
	"Sanjay Yadav" <sanjay.kumar.yadav@intel.com>,
	"Joel Fernandes" <joelagnelf@nvidia.com>,
	"Christian König" <christian.koenig@amd.com>,
	linux-kernel@vger.kernel.org,
	"William Palacek" <William.Palacek@amd.com>
Subject: [PATCH v3 1/2] gpu/buddy: find range-biased blocks in the free trees
Date: Mon, 16 Nov 2026 11:11:01 -0500	[thread overview]
Message-ID: <17f2a6366ba845edc799dbeb712c12f8d060afad.1794845083.git.William.Palacek@amd.com> (raw)
In-Reply-To: <cover.1794845083.git.William.Palacek@amd.com>

__alloc_range_bias() walks the block tree from the roots and visits
every split block overlapping [start, end) until it finds a suitable
free block, so a range-restricted allocation costs time linear in the
number of live allocations in the range. When both clear and dirty
space exist, a request that the strict pass cannot serve walks the
range twice.

amdgpu pays this on every VRAM allocation when memory is partitioned
(NPS2/NPS4): each BO, including the page-table BOs created when memory
is mapped, is restricted to its partition's range, and KFD requests
cleared VRAM. On MI300X in CPX/NPS4 the compute partitions that share a
memory partition also share the VRAM manager lock, so the walk is
serialised across processes. hipMalloc latency grows linearly with the
number of live allocations, and vLLM piecewise graph capture slows down
with every captured graph.

The free trees are sorted by offset, so find the block there instead.
For each order from the requested one up, look up the highest free
block that can hold the request, then split the highest of them down to
the requested order. The strict pass only takes blocks wholly inside
the range whose class suits the request: subtree_block_state lets a
clear request skip subtrees without a clear or mixed block, and a new
subtree_has_dirty augment lets a dirty request skip subtrees that hold
only clear blocks. The fallback pass takes the highest block of either
class and may split one that straddles the range edge. Each lookup is
O(log n) and the walk is gone.

Placement is unchanged. A seeded random workload of 42218 allocations
mixing range, clear and top-down requests and cleared and dirty frees
places every block at the same offset, order and clear state as the
walk.

Filling 1 GiB of a 4 GiB manager with 64 KiB range-biased allocations
that request cleared memory takes 1103 ms before, 2 ms after (KUnit,
UML). With 8192 free cleared 64 KiB blocks interleaved with allocated
ones in the range, 4096 dirty range allocations take 541 to 567 ms
before and 0 ms after, and 4096 cleared ones 106 to 110 ms before and
0 ms after.

On MI300X in CPX/NPS4, with 8000 live 2 MiB hipMalloc allocations on
one partition, the median latency of the last 800 over the first 800 is
1.56x and 7.97x before and 0.52x and 1.06x after (two runs each; the
first run after loading the driver starts slow). vLLM piecewise graph
capture with tensor parallelism over all 64 partitions stays at 4 to 6 s
per graph for all 51 graphs.

Cc: Matthew Auld <matthew.auld@intel.com>
Cc: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>
Signed-off-by: William Palacek <William.Palacek@amd.com>
---

Notes:
    v3:
    - rebased onto the merged clear/dirty guard (cb0a63f0c96e) (Arun)
    - take Arun's free-tree lookup and drop the walk instead of narrowing it
      (Arun)
    - strict pass O(log n) for both classes: subtree_block_state for clear
      requests, new subtree_has_dirty augment for dirty ones
    - placement now matches the walk exactly, including the guard
    
    v2:
    - rebased onto drm-misc-next (single free tree) (Arun)
    - take the highest contained block, keeping top-down placement (Arun)

 drivers/gpu/buddy.c       | 214 +++++++++++++++++++++++++-------------
 include/linux/gpu_buddy.h |   1 +
 2 files changed, 145 insertions(+), 70 deletions(-)

diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
index e7d2212bcec9..baf17700ffba 100644
--- a/drivers/gpu/buddy.c
+++ b/drivers/gpu/buddy.c
@@ -62,6 +62,8 @@ static struct kmem_cache *slab_extents;
  *     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.
+ *   - subtree_has_dirty: some block in the subtree is not fully clear,
+ *     so range allocations can skip all-clear subtrees for dirty requests.
  *
  * Block classes
  * -------------
@@ -510,9 +512,11 @@ static inline void gpu_buddy_augment_compute(struct gpu_buddy_block *block)
 	struct gpu_buddy_block *right;
 	struct gpu_buddy_block *left;
 	unsigned int max_align;
+	bool has_dirty;
 
 	max_align = gpu_buddy_block_offset_alignment(block);
 	block_state = gpu_block_cached_state(block);
+	has_dirty = block_state != GPU_BLOCK_CLEAR;
 
 	left = rb_entry_safe(block->rb.rb_left, struct gpu_buddy_block, rb);
 	if (left) {
@@ -520,6 +524,7 @@ static inline void gpu_buddy_augment_compute(struct gpu_buddy_block *block)
 			max_align = left->subtree_max_alignment;
 
 		block_state = max(block_state, left->subtree_block_state);
+		has_dirty |= left->subtree_has_dirty;
 	}
 
 	right = rb_entry_safe(block->rb.rb_right, struct gpu_buddy_block, rb);
@@ -528,10 +533,12 @@ static inline void gpu_buddy_augment_compute(struct gpu_buddy_block *block)
 			max_align = right->subtree_max_alignment;
 
 		block_state = max(block_state, right->subtree_block_state);
+		has_dirty |= right->subtree_has_dirty;
 	}
 
 	block->subtree_max_alignment = max_align;
 	block->subtree_block_state = block_state;
+	block->subtree_has_dirty = has_dirty;
 }
 
 static void gpu_buddy_augment_propagate(struct rb_node *rb, struct rb_node *stop)
@@ -540,14 +547,17 @@ static void gpu_buddy_augment_propagate(struct rb_node *rb, struct rb_node *stop
 		struct gpu_buddy_block *block;
 		unsigned int old_align;
 		enum gpu_block_state old_block_state;
+		bool old_has_dirty;
 
 		block = rb_entry(rb, struct gpu_buddy_block, rb);
 		old_align = block->subtree_max_alignment;
 		old_block_state = block->subtree_block_state;
+		old_has_dirty = block->subtree_has_dirty;
 
 		gpu_buddy_augment_compute(block);
 		if (block->subtree_max_alignment == old_align &&
-		    block->subtree_block_state == old_block_state)
+		    block->subtree_block_state == old_block_state &&
+		    block->subtree_has_dirty == old_has_dirty)
 			break;
 
 		rb = rb_parent(&block->rb);
@@ -564,6 +574,7 @@ static void gpu_buddy_augment_copy(struct rb_node *rb_old, struct rb_node *rb_ne
 
 	new->subtree_max_alignment = old->subtree_max_alignment;
 	new->subtree_block_state = old->subtree_block_state;
+	new->subtree_has_dirty = old->subtree_has_dirty;
 }
 
 static void gpu_buddy_augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new)
@@ -576,6 +587,7 @@ static void gpu_buddy_augment_rotate(struct rb_node *rb_old, struct rb_node *rb_
 
 	new->subtree_max_alignment = old->subtree_max_alignment;
 	new->subtree_block_state = old->subtree_block_state;
+	new->subtree_has_dirty = old->subtree_has_dirty;
 
 	gpu_buddy_augment_compute(old);
 }
@@ -695,6 +707,8 @@ static void rbtree_insert(struct gpu_buddy *mm,
 			node->subtree_max_alignment = block_alignment;
 		if (node->subtree_block_state < block_state)
 			node->subtree_block_state = block_state;
+		if (block_state != GPU_BLOCK_CLEAR)
+			node->subtree_has_dirty = true;
 
 		if (gpu_buddy_block_offset(block) < gpu_buddy_block_offset(node))
 			link = &parent->rb_left;
@@ -704,6 +718,7 @@ static void rbtree_insert(struct gpu_buddy *mm,
 
 	block->subtree_max_alignment = block_alignment;
 	block->subtree_block_state = block_state;
+	block->subtree_has_dirty = block_state != GPU_BLOCK_CLEAR;
 	rb_link_node(&block->rb, parent, link);
 	rb_insert_augmented(&block->rb, root, &gpu_buddy_augment_cb);
 }
@@ -1247,96 +1262,155 @@ static bool block_incompatible(struct gpu_buddy_block *block, unsigned int flags
 			     gpu_buddy_block_is_clear(block);
 }
 
-static struct gpu_buddy_block *
-__alloc_range_bias(struct gpu_buddy *mm,
-		   u64 start, u64 end,
-		   unsigned int order,
-		   unsigned long flags,
-		   bool fallback)
+/* Does the subtree at @node hold a block the strict pass may take? */
+static bool range_subtree_ok(struct rb_node *node, unsigned long flags)
 {
-	u64 req_size = mm->chunk_size << order;
-	struct gpu_buddy_block *block;
-	LIST_HEAD(dfs);
-	int err;
-	int i;
+	struct gpu_buddy_block *block = rbtree_get_free_block(node);
 
-	end = end - 1;
+	if (!block)
+		return false;
+	if (flags & GPU_BUDDY_CLEAR_ALLOCATION)
+		return block->subtree_block_state >= GPU_BLOCK_MIXED;
+	return block->subtree_has_dirty;
+}
 
-	/*
-	 * 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.
-	 */
-	for (i = mm->n_roots - 1; i >= 0; --i)
-		list_add_tail(&mm->roots[i]->tmp_link, &dfs);
+/*
+ * Highest-offset free block in @root with offset < @limit that the strict
+ * pass may take (any block when @fallback). Subtrees without such a block
+ * are skipped through the augments, so this is O(log n) per call.
+ */
+static struct gpu_buddy_block *
+rbtree_last_range_block(struct rb_root *root, u64 limit,
+			unsigned long flags, bool fallback)
+{
+	struct rb_node *node = root->rb_node;
+	struct rb_node *prev = NULL;
 
-	do {
-		u64 block_start;
-		u64 block_end;
+	while (node) {
+		if (gpu_buddy_block_offset(rbtree_get_free_block(node)) < limit) {
+			prev = node;
+			node = node->rb_right;
+		} else {
+			node = node->rb_left;
+		}
+	}
 
-		block = list_first_entry_or_null(&dfs,
-						 struct gpu_buddy_block,
-						 tmp_link);
-		if (!block)
-			break;
+	for (node = prev; node; node = rb_parent(node)) {
+		if (fallback ||
+		    !block_incompatible(rbtree_get_free_block(node), flags))
+			return rbtree_get_free_block(node);
 
-		list_del(&block->tmp_link);
+		if (range_subtree_ok(node->rb_left, flags)) {
+			/* The left subtree holds one: take its highest. */
+			node = node->rb_left;
+			while (node) {
+				struct gpu_buddy_block *block = rbtree_get_free_block(node);
 
-		if (gpu_buddy_block_order(block) < order)
-			continue;
+				if (range_subtree_ok(node->rb_right, flags)) {
+					node = node->rb_right;
+					continue;
+				}
+				if (!block_incompatible(block, flags))
+					return block;
+				node = node->rb_left;
+			}
+			return NULL;
+		}
 
-		block_start = gpu_buddy_block_offset(block);
-		block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
+		/* Climb to the next lower ancestor. */
+		while (rb_parent(node) && node == rb_parent(node)->rb_left)
+			node = rb_parent(node);
+	}
 
-		if (!overlaps(start, end, block_start, block_end))
-			continue;
+	return NULL;
+}
 
-		if (gpu_buddy_block_is_allocated(block))
-			continue;
+/*
+ * Return the order-@order block at the highest @req_size-aligned offset in
+ * [@start, @end) that lies inside a free block, splitting as needed. The
+ * strict pass only takes free blocks wholly inside the range whose class
+ * suits @flags; splitting a block that straddles the range edge is left to
+ * the fallback pass, which takes either class.
+ */
+static struct gpu_buddy_block *
+__alloc_range_bias(struct gpu_buddy *mm,
+		   u64 start, u64 end,
+		   unsigned int order,
+		   unsigned long flags,
+		   bool fallback)
+{
+	u64 req_size = mm->chunk_size << order;
+	struct gpu_buddy_block *block = NULL;
+	u64 best = 0;
+	unsigned int i;
+	int err;
 
-		if (block_start < start || block_end > end) {
-			u64 adjusted_start = max(block_start, start);
-			u64 adjusted_end = min(block_end, end);
+	for (i = order; i <= mm->max_order; i++) {
+		struct rb_root *root = &mm->free_tree[i];
+		u64 size = mm->chunk_size << i;
+		struct gpu_buddy_block *found;
+		u64 offset = 0;
 
-			if (round_down(adjusted_end + 1, req_size) <=
-			    round_up(adjusted_start, req_size))
-				continue;
+		if (!fallback) {
+			if (end - start < size)
+				break;
 
-			/*
-			 * Strict pass: don't split a partially-overlapping free
-			 * block; rejecting its child would strand the split. Let
-			 * the fallback pass consume it (either class accepted).
-			 */
-			if (!fallback && gpu_buddy_block_is_free(block))
+			found = rbtree_last_range_block(root, end - size + 1,
+							flags, false);
+			if (!found || gpu_buddy_block_offset(found) < start)
 				continue;
-		}
-
-		if (!fallback && block_incompatible(block, flags))
-			continue;
 
-		if (contains(start, end, block_start, block_end) &&
-		    order == gpu_buddy_block_order(block)) {
-			/*
-			 * Find the free block within the range.
-			 */
-			if (gpu_buddy_block_is_free(block))
-				return block;
+			offset = gpu_buddy_block_offset(found) + size - req_size;
+		} else {
+			/* At most the blocks straddling @end and @start miss. */
+			for (found = rbtree_last_range_block(root, end, flags, true);
+			     found;
+			     found = rbtree_get_free_block(rb_prev(&found->rb))) {
+				u64 lo = max(gpu_buddy_block_offset(found), start);
+				u64 hi = min(gpu_buddy_block_offset(found) + size, end);
+
+				if (hi <= start) {
+					found = NULL;
+					break;
+				}
 
-			continue;
+				if (hi >= lo + req_size) {
+					offset = round_down(hi - req_size, req_size);
+					if (offset >= lo)
+						break;
+				}
+			}
+			if (!found)
+				continue;
 		}
 
-		if (!gpu_buddy_block_is_split(block)) {
-			err = split_block(mm, block);
-			if (unlikely(err))
-				goto err_undo;
+		if (!block || offset > best) {
+			block = found;
+			best = offset;
 		}
+	}
 
-		list_add(&block->left->tmp_link, &dfs);
-		list_add(&block->right->tmp_link, &dfs);
-	} while (1);
+	if (!block)
+		return ERR_PTR(-ENOSPC);
+
+	while (gpu_buddy_block_order(block) > order) {
+		err = split_block(mm, block);
+		if (unlikely(err))
+			goto err_undo;
 
-	return ERR_PTR(-ENOSPC);
+		/*
+		 * Fallback: the child holding @best. Strict: the higher child
+		 * unless its class does not suit, as the old walk did.
+		 */
+		if (fallback)
+			block = best >= gpu_buddy_block_offset(block->right) ?
+				block->right : block->left;
+		else
+			block = block_incompatible(block->right, flags) ?
+				block->left : block->right;
+	}
+
+	return block;
 
 err_undo:
 	/*
diff --git a/include/linux/gpu_buddy.h b/include/linux/gpu_buddy.h
index ddc4eca84175..6abc66125935 100644
--- a/include/linux/gpu_buddy.h
+++ b/include/linux/gpu_buddy.h
@@ -141,6 +141,7 @@ struct gpu_buddy_block {
 	unsigned int subtree_max_alignment;
 	struct list_head tmp_link;
 	bool has_clear;
+	bool subtree_has_dirty;
 };
 
 /* Order-zero must be at least SZ_4K */
-- 
2.43.0


  reply	other threads:[~2026-11-16 16:12 UTC|newest]

Thread overview: 3+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-16 16:11 [PATCH v3 0/2] " William Palacek
2026-11-16 16:11 ` William Palacek [this message]
2026-11-16 16:11 ` [PATCH v3 2/2] gpu/tests/buddy: add range-biased allocation performance test William Palacek

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=17f2a6366ba845edc799dbeb712c12f8d060afad.1794845083.git.William.Palacek@amd.com \
    --to=william.palacek@amd.com \
    --cc=Arunpravin.PaneerSelvam@amd.com \
    --cc=christian.koenig@amd.com \
    --cc=dri-devel@lists.freedesktop.org \
    --cc=intel-xe@lists.freedesktop.org \
    --cc=joelagnelf@nvidia.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=matthew.auld@intel.com \
    --cc=sanjay.kumar.yadav@intel.com \
    /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

all inboxes | Powered by JetHome®