[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <23142157adbc54a6e2f03a2ebaf209c9bd89439e@intel.com>
Date: Tue, 02 Sep 2025 13:23:20 +0300
From: Jani Nikula <jani.nikula@...ux.intel.com>
To: Arunpravin Paneer Selvam <Arunpravin.PaneerSelvam@....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, Arunpravin Paneer Selvam
<Arunpravin.PaneerSelvam@....com>
Subject: Re: [PATCH v5 1/2] drm/buddy: Optimize free block management with
RB tree
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.
BR,
Jani.
--
Jani Nikula, Intel
Powered by blists - more mailing lists