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.paneersel...@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.
