* [PATCH v4 2/2] drm/buddy: Add KUnit test for offset-aligned allocations
2026-02-17 11:38 [PATCH v4 1/2] drm/buddy: Improve offset-aligned allocation handling Arunpravin Paneer Selvam
@ 2026-02-17 11:39 ` Arunpravin Paneer Selvam
2026-02-24 17:32 ` Matthew Auld
2026-02-23 7:00 ` [PATCH v4 1/2] drm/buddy: Improve offset-aligned allocation handling Arunpravin Paneer Selvam
` (2 subsequent siblings)
3 siblings, 1 reply; 6+ messages in thread
From: Arunpravin Paneer Selvam @ 2026-02-17 11:39 UTC (permalink / raw)
To: matthew.auld, christian.koenig, dri-devel, intel-gfx, intel-xe,
amd-gfx
Cc: alexander.deucher, Arunpravin Paneer Selvam
Add KUnit test to validate offset-aligned allocations in the DRM buddy
allocator.
Validate offset-aligned allocation:
The test covers allocations with sizes smaller than the alignment constraint
and verifies correct size preservation, offset alignment, and behavior across
multiple allocation sizes. It also exercises fragmentation by freeing
alternating blocks and confirms that allocation fails once all aligned offsets
are consumed.
Stress subtree_max_alignment propagation:
Exercise subtree_max_alignment tracking by allocating blocks with descending
alignment constraints and freeing them in reverse order. This verifies that
free-tree augmentation correctly propagates the maximum offset alignment
present in each subtree at every stage.
v2:
- Move the patch to gpu/tests/gpu_buddy_test.c file.
v3:
- Fixed build warnings reported by kernel test robot <lkp@intel.com>
Signed-off-by: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>
---
drivers/gpu/tests/gpu_buddy_test.c | 167 +++++++++++++++++++++++++++++
1 file changed, 167 insertions(+)
diff --git a/drivers/gpu/tests/gpu_buddy_test.c b/drivers/gpu/tests/gpu_buddy_test.c
index 450e71deed90..2901d43f4bae 100644
--- a/drivers/gpu/tests/gpu_buddy_test.c
+++ b/drivers/gpu/tests/gpu_buddy_test.c
@@ -21,6 +21,171 @@ static inline u64 get_size(int order, u64 chunk_size)
return (1 << order) * chunk_size;
}
+static void gpu_test_buddy_subtree_offset_alignment_stress(struct kunit *test)
+{
+ struct gpu_buddy_block *block;
+ struct rb_node *node = NULL;
+ const u64 mm_size = SZ_2M;
+ const u64 alignments[] = {
+ SZ_1M,
+ SZ_512K,
+ SZ_256K,
+ SZ_128K,
+ SZ_64K,
+ SZ_32K,
+ SZ_16K,
+ SZ_8K,
+ };
+
+ struct list_head allocated[ARRAY_SIZE(alignments)];
+ unsigned int i, order, max_subtree_align = 0;
+ struct gpu_buddy mm;
+ int ret, tree;
+
+ KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K),
+ "buddy_init failed\n");
+
+ for (i = 0; i < ARRAY_SIZE(allocated); i++)
+ INIT_LIST_HEAD(&allocated[i]);
+
+ /*
+ * Exercise subtree_max_alignment tracking by allocating blocks with descending
+ * alignment constraints and freeing them in reverse order. This verifies that
+ * free-tree augmentation correctly propagates the maximum offset alignment
+ * present in each subtree at every stage.
+ */
+
+ for (i = 0; i < ARRAY_SIZE(alignments); i++) {
+ struct gpu_buddy_block *root = NULL;
+ unsigned int expected;
+ u64 align;
+
+ align = alignments[i];
+ expected = ilog2(align) - 1;
+
+ for (;;) {
+ ret = gpu_buddy_alloc_blocks(&mm,
+ 0, mm_size,
+ SZ_4K, align,
+ &allocated[i],
+ 0);
+ if (ret)
+ break;
+
+ block = list_last_entry(&allocated[i],
+ struct gpu_buddy_block,
+ link);
+ KUNIT_EXPECT_EQ(test, gpu_buddy_block_offset(block) & (align - 1), 0ULL);
+ }
+
+ for (order = mm.max_order + 1; order-- > 0 && !root; ) {
+ 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;
+ }
+ }
+ }
+
+ KUNIT_ASSERT_NOT_NULL(test, root);
+ KUNIT_EXPECT_EQ(test, root->subtree_max_alignment, expected);
+ }
+
+ for (i = ARRAY_SIZE(alignments); i-- > 0; ) {
+ 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);
+ }
+ }
+
+ KUNIT_EXPECT_GE(test, max_subtree_align, ilog2(alignments[i]));
+ }
+
+ gpu_buddy_fini(&mm);
+}
+
+static void gpu_test_buddy_offset_aligned_allocation(struct kunit *test)
+{
+ struct gpu_buddy_block *block, *tmp;
+ int num_blocks, i, count = 0;
+ LIST_HEAD(allocated);
+ struct gpu_buddy mm;
+ u64 mm_size = SZ_4M;
+ LIST_HEAD(freed);
+
+ KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K),
+ "buddy_init failed\n");
+
+ num_blocks = mm_size / SZ_256K;
+ /*
+ * Allocate multiple sizes under a fixed offset alignment.
+ * Ensures alignment handling is independent of allocation size and
+ * exercises subtree max-alignment pruning for small requests.
+ */
+ for (i = 0; i < num_blocks; i++)
+ KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_8K, SZ_256K,
+ &allocated, 0),
+ "buddy_alloc hit an error size=%u\n", SZ_8K);
+
+ list_for_each_entry(block, &allocated, link) {
+ /* Ensure the allocated block uses the expected 8 KB size */
+ KUNIT_EXPECT_EQ(test, gpu_buddy_block_size(&mm, block), SZ_8K);
+ /* Ensure the block starts at a 256 KB-aligned offset for proper alignment */
+ KUNIT_EXPECT_EQ(test, gpu_buddy_block_offset(block) & (SZ_256K - 1), 0ULL);
+ }
+ gpu_buddy_free_list(&mm, &allocated, 0);
+
+ for (i = 0; i < num_blocks; i++)
+ KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_16K, SZ_256K,
+ &allocated, 0),
+ "buddy_alloc hit an error size=%u\n", SZ_16K);
+
+ list_for_each_entry(block, &allocated, link) {
+ /* Ensure the allocated block uses the expected 16 KB size */
+ KUNIT_EXPECT_EQ(test, gpu_buddy_block_size(&mm, block), SZ_16K);
+ /* Ensure the block starts at a 256 KB-aligned offset for proper alignment */
+ KUNIT_EXPECT_EQ(test, gpu_buddy_block_offset(block) & (SZ_256K - 1), 0ULL);
+ }
+
+ /*
+ * Free alternating aligned blocks to introduce fragmentation.
+ * Ensures offset-aligned allocations remain valid after frees and
+ * verifies subtree max-alignment metadata is correctly maintained.
+ */
+ list_for_each_entry_safe(block, tmp, &allocated, link) {
+ if (count % 2 == 0)
+ list_move_tail(&block->link, &freed);
+ count++;
+ }
+ gpu_buddy_free_list(&mm, &freed, 0);
+
+ for (i = 0; i < num_blocks / 2; i++)
+ KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_16K, SZ_256K,
+ &allocated, 0),
+ "buddy_alloc hit an error size=%u\n", SZ_16K);
+
+ /*
+ * Allocate with offset alignment after all slots are used; must fail.
+ * Confirms that no aligned offsets remain.
+ */
+ KUNIT_ASSERT_TRUE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_16K, SZ_256K,
+ &allocated, 0),
+ "buddy_alloc hit an error size=%u\n", SZ_16K);
+ gpu_buddy_free_list(&mm, &allocated, 0);
+ gpu_buddy_fini(&mm);
+}
+
static void gpu_test_buddy_fragmentation_performance(struct kunit *test)
{
struct gpu_buddy_block *block, *tmp;
@@ -912,6 +1077,8 @@ static struct kunit_case gpu_buddy_tests[] = {
KUNIT_CASE(gpu_test_buddy_alloc_range_bias),
KUNIT_CASE(gpu_test_buddy_fragmentation_performance),
KUNIT_CASE(gpu_test_buddy_alloc_exceeds_max_order),
+ KUNIT_CASE(gpu_test_buddy_offset_aligned_allocation),
+ KUNIT_CASE(gpu_test_buddy_subtree_offset_alignment_stress),
{}
};
--
2.34.1
^ permalink raw reply related [flat|nested] 6+ messages in thread* Re: [PATCH v4 2/2] drm/buddy: Add KUnit test for offset-aligned allocations
2026-02-17 11:39 ` [PATCH v4 2/2] drm/buddy: Add KUnit test for offset-aligned allocations Arunpravin Paneer Selvam
@ 2026-02-24 17:32 ` Matthew Auld
0 siblings, 0 replies; 6+ messages in thread
From: Matthew Auld @ 2026-02-24 17:32 UTC (permalink / raw)
To: Arunpravin Paneer Selvam, christian.koenig, dri-devel, intel-gfx,
intel-xe, amd-gfx
Cc: alexander.deucher
On 17/02/2026 11:39, Arunpravin Paneer Selvam wrote:
> Add KUnit test to validate offset-aligned allocations in the DRM buddy
> allocator.
>
> Validate offset-aligned allocation:
> The test covers allocations with sizes smaller than the alignment constraint
> and verifies correct size preservation, offset alignment, and behavior across
> multiple allocation sizes. It also exercises fragmentation by freeing
> alternating blocks and confirms that allocation fails once all aligned offsets
> are consumed.
>
> Stress subtree_max_alignment propagation:
> Exercise subtree_max_alignment tracking by allocating blocks with descending
> alignment constraints and freeing them in reverse order. This verifies that
> free-tree augmentation correctly propagates the maximum offset alignment
> present in each subtree at every stage.
>
> v2:
> - Move the patch to gpu/tests/gpu_buddy_test.c file.
>
> v3:
> - Fixed build warnings reported by kernel test robot <lkp@intel.com>
>
> Signed-off-by: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>
> ---
> drivers/gpu/tests/gpu_buddy_test.c | 167 +++++++++++++++++++++++++++++
> 1 file changed, 167 insertions(+)
>
> diff --git a/drivers/gpu/tests/gpu_buddy_test.c b/drivers/gpu/tests/gpu_buddy_test.c
> index 450e71deed90..2901d43f4bae 100644
> --- a/drivers/gpu/tests/gpu_buddy_test.c
> +++ b/drivers/gpu/tests/gpu_buddy_test.c
> @@ -21,6 +21,171 @@ static inline u64 get_size(int order, u64 chunk_size)
> return (1 << order) * chunk_size;
> }
>
> +static void gpu_test_buddy_subtree_offset_alignment_stress(struct kunit *test)
> +{
> + struct gpu_buddy_block *block;
> + struct rb_node *node = NULL;
> + const u64 mm_size = SZ_2M;
> + const u64 alignments[] = {
> + SZ_1M,
> + SZ_512K,
> + SZ_256K,
> + SZ_128K,
> + SZ_64K,
> + SZ_32K,
> + SZ_16K,
> + SZ_8K,
> + };
> +
Nit: extra newline
> + struct list_head allocated[ARRAY_SIZE(alignments)];
> + unsigned int i, order, max_subtree_align = 0;
> + struct gpu_buddy mm;
> + int ret, tree;
> +
> + KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K),
> + "buddy_init failed\n");
> +
> + for (i = 0; i < ARRAY_SIZE(allocated); i++)
> + INIT_LIST_HEAD(&allocated[i]);
> +
> + /*
> + * Exercise subtree_max_alignment tracking by allocating blocks with descending
> + * alignment constraints and freeing them in reverse order. This verifies that
> + * free-tree augmentation correctly propagates the maximum offset alignment
> + * present in each subtree at every stage.
> + */
> +
> + for (i = 0; i < ARRAY_SIZE(alignments); i++) {
> + struct gpu_buddy_block *root = NULL;
> + unsigned int expected;
> + u64 align;
> +
> + align = alignments[i];
> + expected = ilog2(align) - 1;
> +
> + for (;;) {
> + ret = gpu_buddy_alloc_blocks(&mm,
> + 0, mm_size,
> + SZ_4K, align,
> + &allocated[i],
> + 0);
> + if (ret)
> + break;
> +
> + block = list_last_entry(&allocated[i],
> + struct gpu_buddy_block,
> + link);
> + KUNIT_EXPECT_EQ(test, gpu_buddy_block_offset(block) & (align - 1), 0ULL);
Perhaps simpler to use:
IS_ALIGNED(offset, align)
?
> + }
> +
> + for (order = mm.max_order + 1; order-- > 0 && !root; ) {
This is maybe a bit hard to read?
for (order = mm.max_order; order >= 0 && !root; order--)
And make order an int?
> + 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;
> + }
> + }
> + }
> +
> + KUNIT_ASSERT_NOT_NULL(test, root);
> + KUNIT_EXPECT_EQ(test, root->subtree_max_alignment, expected);
> + }
> +
> + for (i = ARRAY_SIZE(alignments); i-- > 0; ) {
> + 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);
> + }
> + }
> +
> + KUNIT_EXPECT_GE(test, max_subtree_align, ilog2(alignments[i]));
> + }
> +
> + gpu_buddy_fini(&mm);
> +}
> +
> +static void gpu_test_buddy_offset_aligned_allocation(struct kunit *test)
> +{
> + struct gpu_buddy_block *block, *tmp;
> + int num_blocks, i, count = 0;
> + LIST_HEAD(allocated);
> + struct gpu_buddy mm;
> + u64 mm_size = SZ_4M;
> + LIST_HEAD(freed);
> +
> + KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K),
> + "buddy_init failed\n");
> +
> + num_blocks = mm_size / SZ_256K;
> + /*
> + * Allocate multiple sizes under a fixed offset alignment.
> + * Ensures alignment handling is independent of allocation size and
> + * exercises subtree max-alignment pruning for small requests.
> + */
> + for (i = 0; i < num_blocks; i++)
> + KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_8K, SZ_256K,
> + &allocated, 0),
> + "buddy_alloc hit an error size=%u\n", SZ_8K);
> +
> + list_for_each_entry(block, &allocated, link) {
> + /* Ensure the allocated block uses the expected 8 KB size */
> + KUNIT_EXPECT_EQ(test, gpu_buddy_block_size(&mm, block), SZ_8K);
> + /* Ensure the block starts at a 256 KB-aligned offset for proper alignment */
> + KUNIT_EXPECT_EQ(test, gpu_buddy_block_offset(block) & (SZ_256K - 1), 0ULL);
IS_ALIGNED() ?
> + }
> + gpu_buddy_free_list(&mm, &allocated, 0);
> +
> + for (i = 0; i < num_blocks; i++)
> + KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_16K, SZ_256K,
> + &allocated, 0),
> + "buddy_alloc hit an error size=%u\n", SZ_16K);
> +
> + list_for_each_entry(block, &allocated, link) {
> + /* Ensure the allocated block uses the expected 16 KB size */
> + KUNIT_EXPECT_EQ(test, gpu_buddy_block_size(&mm, block), SZ_16K);
> + /* Ensure the block starts at a 256 KB-aligned offset for proper alignment */
> + KUNIT_EXPECT_EQ(test, gpu_buddy_block_offset(block) & (SZ_256K - 1), 0ULL);
IS_ALIGNED() ?
Anyway:
Reviewed-by: Matthew Auld <matthew.auld@intel.com>
> + }
> +
> + /*
> + * Free alternating aligned blocks to introduce fragmentation.
> + * Ensures offset-aligned allocations remain valid after frees and
> + * verifies subtree max-alignment metadata is correctly maintained.
> + */
> + list_for_each_entry_safe(block, tmp, &allocated, link) {
> + if (count % 2 == 0)
> + list_move_tail(&block->link, &freed);
> + count++;
> + }
> + gpu_buddy_free_list(&mm, &freed, 0);
> +
> + for (i = 0; i < num_blocks / 2; i++)
> + KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_16K, SZ_256K,
> + &allocated, 0),
> + "buddy_alloc hit an error size=%u\n", SZ_16K);
> +
> + /*
> + * Allocate with offset alignment after all slots are used; must fail.
> + * Confirms that no aligned offsets remain.
> + */
> + KUNIT_ASSERT_TRUE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_16K, SZ_256K,
> + &allocated, 0),
> + "buddy_alloc hit an error size=%u\n", SZ_16K);
> + gpu_buddy_free_list(&mm, &allocated, 0);
> + gpu_buddy_fini(&mm);
> +}
> +
> static void gpu_test_buddy_fragmentation_performance(struct kunit *test)
> {
> struct gpu_buddy_block *block, *tmp;
> @@ -912,6 +1077,8 @@ static struct kunit_case gpu_buddy_tests[] = {
> KUNIT_CASE(gpu_test_buddy_alloc_range_bias),
> KUNIT_CASE(gpu_test_buddy_fragmentation_performance),
> KUNIT_CASE(gpu_test_buddy_alloc_exceeds_max_order),
> + KUNIT_CASE(gpu_test_buddy_offset_aligned_allocation),
> + KUNIT_CASE(gpu_test_buddy_subtree_offset_alignment_stress),
> {}
> };
>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v4 1/2] drm/buddy: Improve offset-aligned allocation handling
2026-02-17 11:38 [PATCH v4 1/2] drm/buddy: Improve offset-aligned allocation handling Arunpravin Paneer Selvam
2026-02-17 11:39 ` [PATCH v4 2/2] drm/buddy: Add KUnit test for offset-aligned allocations Arunpravin Paneer Selvam
@ 2026-02-23 7:00 ` Arunpravin Paneer Selvam
2026-02-23 16:47 ` Matthew Auld
2026-02-24 17:35 ` Matthew Auld
3 siblings, 0 replies; 6+ messages in thread
From: Arunpravin Paneer Selvam @ 2026-02-23 7:00 UTC (permalink / raw)
To: matthew.auld, christian.koenig, dri-devel, intel-gfx, intel-xe,
amd-gfx
Cc: alexander.deucher
Hi Matthew,
Ping ?
Regards,
Arun.
On 2/17/2026 5:08 PM, Arunpravin Paneer Selvam wrote:
> Large alignment requests previously forced the buddy allocator to search by
> alignment order, which often caused higher-order free blocks to be split even
> when a suitably aligned smaller region already existed within them. This led
> to excessive fragmentation, especially for workloads requesting small sizes
> with large alignment constraints.
>
> This change prioritizes the requested allocation size during the search and
> uses an augmented RB-tree field (subtree_max_alignment) to efficiently locate
> free blocks that satisfy both size and offset-alignment requirements. As a
> result, the allocator can directly select an aligned sub-region without
> splitting larger blocks unnecessarily.
>
> A practical example is the VKCTS test
> dEQP-VK.memory.allocation.basic.size_8KiB.reverse.count_4000, which repeatedly
> allocates 8 KiB buffers with a 256 KiB alignment. Previously, such allocations
> caused large blocks to be split aggressively, despite smaller aligned regions
> being sufficient. With this change, those aligned regions are reused directly,
> significantly reducing fragmentation.
>
> This improvement is visible in the amdgpu VRAM buddy allocator state
> (/sys/kernel/debug/dri/1/amdgpu_vram_mm). After the change, higher-order blocks
> are preserved and the number of low-order fragments is substantially reduced.
>
> Before:
> order- 5 free: 1936 MiB, blocks: 15490
> order- 4 free: 967 MiB, blocks: 15486
> order- 3 free: 483 MiB, blocks: 15485
> order- 2 free: 241 MiB, blocks: 15486
> order- 1 free: 241 MiB, blocks: 30948
>
> After:
> order- 5 free: 493 MiB, blocks: 3941
> order- 4 free: 246 MiB, blocks: 3943
> order- 3 free: 123 MiB, blocks: 4101
> order- 2 free: 61 MiB, blocks: 4101
> order- 1 free: 61 MiB, blocks: 8018
>
> By avoiding unnecessary splits, this change improves allocator efficiency and
> helps maintain larger contiguous free regions under heavy offset-aligned
> allocation workloads.
>
> v2:(Matthew)
> - Update augmented information along the path to the inserted node.
>
> v3:
> - Move the patch to gpu/buddy.c file.
>
> v4:(Matthew)
> - Use the helper instead of calling _ffs directly
> - Remove gpu_buddy_block_order(block) >= order check and drop order
> - Drop !node check as all callers handle this already
> - Return larger than any other possible alignment for __ffs64(0)
> - Replace __ffs with __ffs64
>
> Signed-off-by: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>
> Suggested-by: Christian König <christian.koenig@amd.com>
> ---
> drivers/gpu/buddy.c | 275 +++++++++++++++++++++++++++++++-------
> include/linux/gpu_buddy.h | 2 +
> 2 files changed, 232 insertions(+), 45 deletions(-)
>
> diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
> index 603c59a2013a..542131992763 100644
> --- a/drivers/gpu/buddy.c
> +++ b/drivers/gpu/buddy.c
> @@ -14,6 +14,25 @@
>
> static struct kmem_cache *slab_blocks;
>
> +static unsigned int gpu_buddy_block_offset_alignment(struct gpu_buddy_block *block)
> +{
> + u64 offset = gpu_buddy_block_offset(block);
> +
> + if (!offset)
> + /*
> + * __ffs64(0) is undefined; offset 0 is maximally aligned, so return
> + * a value greater than any possible alignment.
> + */
> + return 64 + 1;
> +
> + 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 struct gpu_buddy_block *gpu_block_alloc(struct gpu_buddy *mm,
> struct gpu_buddy_block *parent,
> unsigned int order,
> @@ -31,6 +50,9 @@ static struct gpu_buddy_block *gpu_block_alloc(struct gpu_buddy *mm,
> block->header |= order;
> block->parent = parent;
>
> + block->subtree_max_alignment =
> + gpu_buddy_block_offset_alignment(block);
> +
> RB_CLEAR_NODE(&block->rb);
>
> BUG_ON(block->header & GPU_BUDDY_HEADER_UNUSED);
> @@ -67,26 +89,42 @@ static bool rbtree_is_empty(struct rb_root *root)
> return RB_EMPTY_ROOT(root);
> }
>
> -static bool gpu_buddy_block_offset_less(const struct gpu_buddy_block *block,
> - const struct gpu_buddy_block *node)
> -{
> - return gpu_buddy_block_offset(block) < gpu_buddy_block_offset(node);
> -}
> -
> -static bool rbtree_block_offset_less(struct rb_node *block,
> - const struct rb_node *node)
> -{
> - return gpu_buddy_block_offset_less(rbtree_get_free_block(block),
> - rbtree_get_free_block(node));
> -}
> -
> static void rbtree_insert(struct gpu_buddy *mm,
> struct gpu_buddy_block *block,
> enum gpu_buddy_free_tree tree)
> {
> - rb_add(&block->rb,
> - &mm->free_trees[tree][gpu_buddy_block_order(block)],
> - rbtree_block_offset_less);
> + struct rb_node **link, *parent = NULL;
> + unsigned int block_alignment, order;
> + struct gpu_buddy_block *node;
> + struct rb_root *root;
> +
> + order = gpu_buddy_block_order(block);
> + block_alignment = gpu_buddy_block_offset_alignment(block);
> +
> + root = &mm->free_trees[tree][order];
> + link = &root->rb_node;
> +
> + while (*link) {
> + parent = *link;
> + node = rbtree_get_free_block(parent);
> + /*
> + * 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.
> + */
> + if (node->subtree_max_alignment < block_alignment)
> + node->subtree_max_alignment = block_alignment;
> +
> + if (gpu_buddy_block_offset(block) < gpu_buddy_block_offset(node))
> + link = &parent->rb_left;
> + else
> + link = &parent->rb_right;
> + }
> +
> + block->subtree_max_alignment = block_alignment;
> + rb_link_node(&block->rb, parent, link);
> + rb_insert_augmented(&block->rb, root, &gpu_buddy_augment_cb);
> }
>
> static void rbtree_remove(struct gpu_buddy *mm,
> @@ -99,7 +137,7 @@ static void rbtree_remove(struct gpu_buddy *mm,
> tree = get_block_tree(block);
> root = &mm->free_trees[tree][order];
>
> - rb_erase(&block->rb, root);
> + rb_erase_augmented(&block->rb, root, &gpu_buddy_augment_cb);
> RB_CLEAR_NODE(&block->rb);
> }
>
> @@ -790,6 +828,127 @@ alloc_from_freetree(struct gpu_buddy *mm,
> return ERR_PTR(err);
> }
>
> +static bool
> +gpu_buddy_can_offset_align(u64 size, u64 min_block_size)
> +{
> + return size < min_block_size && is_power_of_2(size);
> +}
> +
> +static bool gpu_buddy_subtree_can_satisfy(struct rb_node *node,
> + unsigned int alignment)
> +{
> + struct gpu_buddy_block *block;
> +
> + block = rbtree_get_free_block(node);
> + return block->subtree_max_alignment >= alignment;
> +}
> +
> +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)
> +{
> + struct rb_root *root = &mm->free_trees[tree][order];
> + struct rb_node *rb = root->rb_node;
> +
> + while (rb) {
> + struct gpu_buddy_block *block = rbtree_get_free_block(rb);
> + struct rb_node *left_node = rb->rb_left, *right_node = rb->rb_right;
> +
> + if (right_node) {
> + if (gpu_buddy_subtree_can_satisfy(right_node, alignment)) {
> + rb = right_node;
> + continue;
> + }
> + }
> +
> + if (gpu_buddy_block_offset_alignment(block) >= alignment)
> + return block;
> +
> + if (left_node) {
> + if (gpu_buddy_subtree_can_satisfy(left_node, alignment)) {
> + rb = left_node;
> + continue;
> + }
> + }
> +
> + break;
> + }
> +
> + return NULL;
> +}
> +
> +static struct gpu_buddy_block *
> +gpu_buddy_offset_aligned_allocation(struct gpu_buddy *mm,
> + u64 size,
> + u64 min_block_size,
> + unsigned long flags)
> +{
> + struct gpu_buddy_block *block = NULL;
> + unsigned int order, tmp, alignment;
> + struct gpu_buddy_block *buddy;
> + enum gpu_buddy_free_tree tree;
> + unsigned long pages;
> + int err;
> +
> + alignment = ilog2(min_block_size);
> + pages = size >> ilog2(mm->chunk_size);
> + order = fls(pages) - 1;
> +
> + tree = (flags & GPU_BUDDY_CLEAR_ALLOCATION) ?
> + GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE;
> +
> + 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);
> + }
> +
> + if (block)
> + break;
> + }
> +
> + if (!block)
> + return ERR_PTR(-ENOSPC);
> +
> + while (gpu_buddy_block_order(block) > order) {
> + struct gpu_buddy_block *left, *right;
> +
> + err = split_block(mm, block);
> + if (unlikely(err))
> + goto err_undo;
> +
> + left = block->left;
> + right = block->right;
> +
> + if (gpu_buddy_block_offset_alignment(right) >= alignment)
> + block = right;
> + else
> + block = left;
> + }
> +
> + return block;
> +
> +err_undo:
> + /*
> + * We really don't want to leave around a bunch of split blocks, since
> + * bigger is better, so make sure we merge everything back before we
> + * free the allocated blocks.
> + */
> + buddy = __get_buddy(block);
> + if (buddy &&
> + (gpu_buddy_block_is_free(block) &&
> + gpu_buddy_block_is_free(buddy)))
> + __gpu_buddy_free(mm, block, false);
> + return ERR_PTR(err);
> +}
> +
> static int __alloc_range(struct gpu_buddy *mm,
> struct list_head *dfs,
> u64 start, u64 size,
> @@ -1059,6 +1218,7 @@ EXPORT_SYMBOL(gpu_buddy_block_trim);
> static struct gpu_buddy_block *
> __gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
> u64 start, u64 end,
> + u64 size, u64 min_block_size,
> unsigned int order,
> unsigned long flags)
> {
> @@ -1066,6 +1226,11 @@ __gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
> /* Allocate traversing within the range */
> return __gpu_buddy_alloc_range_bias(mm, start, end,
> order, flags);
> + else 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);
> @@ -1137,8 +1302,11 @@ int gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
> if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) {
> size = roundup_pow_of_two(size);
> min_block_size = size;
> - /* Align size value to min_block_size */
> - } else if (!IS_ALIGNED(size, min_block_size)) {
> + /*
> + * Normalize the requested size to min_block_size for regular allocations.
> + * Offset-aligned allocations intentionally skip size rounding.
> + */
> + } else if (!gpu_buddy_can_offset_align(size, min_block_size)) {
> size = round_up(size, min_block_size);
> }
>
> @@ -1158,43 +1326,60 @@ int gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
> do {
> order = min(order, (unsigned int)fls(pages) - 1);
> BUG_ON(order > mm->max_order);
> - BUG_ON(order < min_order);
> + /*
> + * Regular allocations must not allocate blocks smaller than min_block_size.
> + * Offset-aligned allocations deliberately bypass this constraint.
> + */
> + BUG_ON(size >= min_block_size && order < min_order);
>
> do {
> + unsigned int fallback_order;
> +
> block = __gpu_buddy_alloc_blocks(mm, start,
> end,
> + size,
> + min_block_size,
> order,
> flags);
> if (!IS_ERR(block))
> break;
>
> - if (order-- == min_order) {
> - /* Try allocation through force merge method */
> - if (mm->clear_avail &&
> - !__force_merge(mm, start, end, min_order)) {
> - block = __gpu_buddy_alloc_blocks(mm, start,
> - end,
> - min_order,
> - flags);
> - if (!IS_ERR(block)) {
> - order = min_order;
> - break;
> - }
> - }
> + if (size < min_block_size) {
> + fallback_order = order;
> + } else if (order == min_order) {
> + fallback_order = min_order;
> + } else {
> + order--;
> + continue;
> + }
>
> - /*
> - * 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);
> - err = -ENOSPC;
> - goto err_free;
> + /* 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);
> + err = -ENOSPC;
> + goto err_free;
> } while (1);
>
> mark_allocated(mm, block);
> diff --git a/include/linux/gpu_buddy.h b/include/linux/gpu_buddy.h
> index 07ac65db6d2e..7ad817c69ec6 100644
> --- a/include/linux/gpu_buddy.h
> +++ b/include/linux/gpu_buddy.h
> @@ -11,6 +11,7 @@
> #include <linux/slab.h>
> #include <linux/sched.h>
> #include <linux/rbtree.h>
> +#include <linux/rbtree_augmented.h>
>
> #define GPU_BUDDY_RANGE_ALLOCATION BIT(0)
> #define GPU_BUDDY_TOPDOWN_ALLOCATION BIT(1)
> @@ -58,6 +59,7 @@ struct gpu_buddy_block {
> };
>
> struct list_head tmp_link;
> + unsigned int subtree_max_alignment;
> };
>
> /* Order-zero must be at least SZ_4K */
>
> base-commit: 0ef1dcf4c16bb6d90e8fbf7b18f3d76b79fcde9d
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH v4 1/2] drm/buddy: Improve offset-aligned allocation handling
2026-02-17 11:38 [PATCH v4 1/2] drm/buddy: Improve offset-aligned allocation handling Arunpravin Paneer Selvam
2026-02-17 11:39 ` [PATCH v4 2/2] drm/buddy: Add KUnit test for offset-aligned allocations Arunpravin Paneer Selvam
2026-02-23 7:00 ` [PATCH v4 1/2] drm/buddy: Improve offset-aligned allocation handling Arunpravin Paneer Selvam
@ 2026-02-23 16:47 ` Matthew Auld
2026-02-24 17:35 ` Matthew Auld
3 siblings, 0 replies; 6+ messages in thread
From: Matthew Auld @ 2026-02-23 16:47 UTC (permalink / raw)
To: Arunpravin Paneer Selvam, christian.koenig, dri-devel, intel-gfx,
intel-xe, amd-gfx
Cc: alexander.deucher
On 17/02/2026 11:38, Arunpravin Paneer Selvam wrote:
> Large alignment requests previously forced the buddy allocator to search by
> alignment order, which often caused higher-order free blocks to be split even
> when a suitably aligned smaller region already existed within them. This led
> to excessive fragmentation, especially for workloads requesting small sizes
> with large alignment constraints.
>
> This change prioritizes the requested allocation size during the search and
> uses an augmented RB-tree field (subtree_max_alignment) to efficiently locate
> free blocks that satisfy both size and offset-alignment requirements. As a
> result, the allocator can directly select an aligned sub-region without
> splitting larger blocks unnecessarily.
>
> A practical example is the VKCTS test
> dEQP-VK.memory.allocation.basic.size_8KiB.reverse.count_4000, which repeatedly
> allocates 8 KiB buffers with a 256 KiB alignment. Previously, such allocations
> caused large blocks to be split aggressively, despite smaller aligned regions
> being sufficient. With this change, those aligned regions are reused directly,
> significantly reducing fragmentation.
>
> This improvement is visible in the amdgpu VRAM buddy allocator state
> (/sys/kernel/debug/dri/1/amdgpu_vram_mm). After the change, higher-order blocks
> are preserved and the number of low-order fragments is substantially reduced.
>
> Before:
> order- 5 free: 1936 MiB, blocks: 15490
> order- 4 free: 967 MiB, blocks: 15486
> order- 3 free: 483 MiB, blocks: 15485
> order- 2 free: 241 MiB, blocks: 15486
> order- 1 free: 241 MiB, blocks: 30948
>
> After:
> order- 5 free: 493 MiB, blocks: 3941
> order- 4 free: 246 MiB, blocks: 3943
> order- 3 free: 123 MiB, blocks: 4101
> order- 2 free: 61 MiB, blocks: 4101
> order- 1 free: 61 MiB, blocks: 8018
>
> By avoiding unnecessary splits, this change improves allocator efficiency and
> helps maintain larger contiguous free regions under heavy offset-aligned
> allocation workloads.
>
> v2:(Matthew)
> - Update augmented information along the path to the inserted node.
>
> v3:
> - Move the patch to gpu/buddy.c file.
>
> v4:(Matthew)
> - Use the helper instead of calling _ffs directly
> - Remove gpu_buddy_block_order(block) >= order check and drop order
> - Drop !node check as all callers handle this already
> - Return larger than any other possible alignment for __ffs64(0)
> - Replace __ffs with __ffs64
>
> Signed-off-by: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>
> Suggested-by: Christian König <christian.koenig@amd.com>
Reviewed-by: Matthew Auld <matthew.auld@intel.com>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v4 1/2] drm/buddy: Improve offset-aligned allocation handling
2026-02-17 11:38 [PATCH v4 1/2] drm/buddy: Improve offset-aligned allocation handling Arunpravin Paneer Selvam
` (2 preceding siblings ...)
2026-02-23 16:47 ` Matthew Auld
@ 2026-02-24 17:35 ` Matthew Auld
3 siblings, 0 replies; 6+ messages in thread
From: Matthew Auld @ 2026-02-24 17:35 UTC (permalink / raw)
To: Arunpravin Paneer Selvam, christian.koenig, dri-devel, intel-gfx,
intel-xe, amd-gfx
Cc: alexander.deucher
On 17/02/2026 11:38, Arunpravin Paneer Selvam wrote:
> Large alignment requests previously forced the buddy allocator to search by
> alignment order, which often caused higher-order free blocks to be split even
> when a suitably aligned smaller region already existed within them. This led
> to excessive fragmentation, especially for workloads requesting small sizes
> with large alignment constraints.
>
> This change prioritizes the requested allocation size during the search and
> uses an augmented RB-tree field (subtree_max_alignment) to efficiently locate
> free blocks that satisfy both size and offset-alignment requirements. As a
> result, the allocator can directly select an aligned sub-region without
> splitting larger blocks unnecessarily.
>
> A practical example is the VKCTS test
> dEQP-VK.memory.allocation.basic.size_8KiB.reverse.count_4000, which repeatedly
> allocates 8 KiB buffers with a 256 KiB alignment. Previously, such allocations
> caused large blocks to be split aggressively, despite smaller aligned regions
> being sufficient. With this change, those aligned regions are reused directly,
> significantly reducing fragmentation.
>
> This improvement is visible in the amdgpu VRAM buddy allocator state
> (/sys/kernel/debug/dri/1/amdgpu_vram_mm). After the change, higher-order blocks
> are preserved and the number of low-order fragments is substantially reduced.
>
> Before:
> order- 5 free: 1936 MiB, blocks: 15490
> order- 4 free: 967 MiB, blocks: 15486
> order- 3 free: 483 MiB, blocks: 15485
> order- 2 free: 241 MiB, blocks: 15486
> order- 1 free: 241 MiB, blocks: 30948
>
> After:
> order- 5 free: 493 MiB, blocks: 3941
> order- 4 free: 246 MiB, blocks: 3943
> order- 3 free: 123 MiB, blocks: 4101
> order- 2 free: 61 MiB, blocks: 4101
> order- 1 free: 61 MiB, blocks: 8018
>
> By avoiding unnecessary splits, this change improves allocator efficiency and
> helps maintain larger contiguous free regions under heavy offset-aligned
> allocation workloads.
>
> v2:(Matthew)
> - Update augmented information along the path to the inserted node.
>
> v3:
> - Move the patch to gpu/buddy.c file.
>
> v4:(Matthew)
> - Use the helper instead of calling _ffs directly
> - Remove gpu_buddy_block_order(block) >= order check and drop order
> - Drop !node check as all callers handle this already
> - Return larger than any other possible alignment for __ffs64(0)
> - Replace __ffs with __ffs64
>
> Signed-off-by: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@amd.com>
> Suggested-by: Christian König <christian.koenig@amd.com>
> ---
> drivers/gpu/buddy.c | 275 +++++++++++++++++++++++++++++++-------
> include/linux/gpu_buddy.h | 2 +
> 2 files changed, 232 insertions(+), 45 deletions(-)
>
> diff --git a/drivers/gpu/buddy.c b/drivers/gpu/buddy.c
> index 603c59a2013a..542131992763 100644
> --- a/drivers/gpu/buddy.c
> +++ b/drivers/gpu/buddy.c
> @@ -14,6 +14,25 @@
>
> static struct kmem_cache *slab_blocks;
>
> +static unsigned int gpu_buddy_block_offset_alignment(struct gpu_buddy_block *block)
> +{
> + u64 offset = gpu_buddy_block_offset(block);
> +
> + if (!offset)
> + /*
> + * __ffs64(0) is undefined; offset 0 is maximally aligned, so return
> + * a value greater than any possible alignment.
> + */
> + return 64 + 1;
> +
> + 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 struct gpu_buddy_block *gpu_block_alloc(struct gpu_buddy *mm,
> struct gpu_buddy_block *parent,
> unsigned int order,
> @@ -31,6 +50,9 @@ static struct gpu_buddy_block *gpu_block_alloc(struct gpu_buddy *mm,
> block->header |= order;
> block->parent = parent;
>
> + block->subtree_max_alignment =
> + gpu_buddy_block_offset_alignment(block);
> +
I think we can drop this now?
^ permalink raw reply [flat|nested] 6+ messages in thread