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

[Arunpravin Paneer Selvam]

On 8/22/2025 5:58 PM, Matthew Auld wrote:
> 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.

Thanks, I think I missed updating here when we removed the new tree 
field and modified it to use the existing dirty/free bit in the 
drm_buddy_block struct in v3 patches.

I will add this fix in v4.

Regards,

Arun.