[PATCH v3 1/2] drm/buddy: Optimize free block management with RB tree

[Matthew Auld]

On 22/08/2025 09:37, Matthew Auld wrote:
> On 21/08/2025 16:06, Arunpravin Paneer Selvam wrote:
>> Replace the freelist (O(n)) used for free block management with a
>> red-black tree, providing more efficient O(log n) search, insert,
>> and delete operations. This improves scalability and performance
>> when managing large numbers of free blocks per order (e.g., hundreds
>> or thousands).
>>
>> In the VK-CTS memory stress subtest, the buddy manager merges
>> fragmented memory and inserts freed blocks into the freelist. Since
>> freelist insertion is O(n), this becomes a bottleneck as fragmentation
>> increases. Benchmarking shows list_insert_sorted() consumes ~52.69% CPU
>> with the freelist, compared to just 0.03% with the RB tree
>> (rbtree_insert.isra.0), despite performing the same sorted insert.
>>
>> This also improves performance in heavily fragmented workloads,
>> such as games or graphics tests that stress memory.
>>
>> v3(Matthew):
>>    - Remove RB_EMPTY_NODE check in force_merge function.
>>    - Rename rb for loop macros to have less generic names and move to
>>      .c file.
>>    - Make the rb node rb and link field as union.
>>
>> Signed-off-by: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam at amd.com>
> 
> CI is reporting a crash in rb_erase when running the drm_buddy kunit, 
> somewhere in drm_test_buddy_alloc_clear it seems.

Found one bug in the second patch:

--- a/drivers/gpu/drm/drm_buddy.c
+++ b/drivers/gpu/drm/drm_buddy.c
@@ -507,6 +507,8 @@ static int split_block(struct drm_buddy *mm,
                 return -ENOMEM;
         }

+       mark_split(mm, block);
+
         if (drm_buddy_block_is_clear(block)) {
                 mark_cleared(block->left);
                 mark_cleared(block->right);
@@ -516,8 +518,6 @@ static int split_block(struct drm_buddy *mm,
         mark_free(mm, block->left);
         mark_free(mm, block->right);

-       mark_split(mm, block);
-
         return 0;
  }

Otherwise the mark_split might get the wrong rb root if we reset the 
clear state first. Might help with this crash.