linux-kernel - Re: [PATCH v5 1/2] drm/buddy: Optimize free block management with RB tree

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <091729c2-dc64-49d1-9f41-32e67509ade6@amd.com>
Date: Tue, 2 Sep 2025 16:05:42 +0530
From: Arunpravin Paneer Selvam <arunpravin.paneerselvam@....com>
To: Jani Nikula <jani.nikula@...ux.intel.com>, christian.koenig@....com,
 matthew.auld@...el.com, peterz@...radead.org,
 dri-devel@...ts.freedesktop.org, amd-gfx@...ts.freedesktop.org,
 intel-gfx@...ts.freedesktop.org, intel-xe@...ts.freedesktop.org,
 linux-kernel@...r.kernel.org, stable@...r.kernel.org
Cc: alexander.deucher@....com
Subject: Re: [PATCH v5 1/2] drm/buddy: Optimize free block management with RB
 tree



On 9/2/2025 3:53 PM, Jani Nikula wrote:
> On Tue, 02 Sep 2025, Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@....com> 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.
>>
>> v4(Jani Nikula):
>>    - The kernel-doc comment should be "/**"
>>    - Move all the rbtree macros to rbtree.h and add parens to ensure
>>      correct precedence.
>>
>> Signed-off-by: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@....com>
>> ---
>>   drivers/gpu/drm/drm_buddy.c | 142 ++++++++++++++++++++++--------------
>>   include/drm/drm_buddy.h     |   9 ++-
>>   include/linux/rbtree.h      |  56 ++++++++++++++
>>   3 files changed, 152 insertions(+), 55 deletions(-)
>>
>> diff --git a/drivers/gpu/drm/drm_buddy.c b/drivers/gpu/drm/drm_buddy.c
>> index a94061f373de..978cabfbcf0f 100644
>> --- a/drivers/gpu/drm/drm_buddy.c
>> +++ b/drivers/gpu/drm/drm_buddy.c
> ...
>
>> +static inline struct drm_buddy_block *
>> +rbtree_last_entry(struct drm_buddy *mm, unsigned int order)
> Drive-by reminder that "inline" in a .c file is, in absense of evidence
> to the contrary, superfluous. Please just let the compiler do its job.
Ah, I missed taking out the inline. Thanks for catching that.

Thanks,
Arun.
>
> BR,
> Jani.
>
>