kernel/linux.git/include/drm/drm_buddy.h, branch v6.18.22

drm/buddy: Separate clear and dirty free block trees

2026-01-08T09:17:16+00:00

commit d4cd665c98c144dd6ad5d66d30396e13d23118c9 upstream. Maintain two separate RB trees per order - one for clear (zeroed) blocks and another for dirty (uncleared) blocks. This separation improves code clarity and makes it more obvious which tree is being searched during allocation. It also improves scalability and efficiency when searching for a specific type of block, avoiding unnecessary checks and making the allocator more predictable under fragmentation. The changes have been validated using the existing drm_buddy_test KUnit test cases, along with selected graphics workloads, to ensure correctness and avoid regressions. v2: Missed adding the suggested-by tag. Added it in v2. v3(Matthew): - Remove the double underscores from the internal functions. - Rename the internal functions to have less generic names. - Fix the error handling code. - Pass tree argument for the tree macro. - Use the existing dirty/free bit instead of new tree field. - Make free_trees[] instead of clear_tree and dirty_tree for more cleaner approach. v4: - A bug was reported by Intel CI and it is fixed by Matthew Auld. - Replace the get_root function with &mm->free_trees[tree][order] (Matthew) - Remove the unnecessary rbtree_is_empty() check (Matthew) - Remove the unnecessary get_tree_for_flags() function. - Rename get_tree_for_block() name with get_block_tree() for more clarity. v5(Jani Nikula): - Don't use static inline in .c files. - enum free_tree and enumerator names are quite generic for a header and usage and the whole enum should be an implementation detail. v6: - Rewrite the __force_merge() function using the rb_last() and rb_prev(). v7(Matthew): - Replace the open-coded tree iteration for loops with the for_each_free_tree() macro throughout the code. - Fixed out_free_roots to prevent double decrement of i, addressing potential crash. - Replaced enum drm_buddy_free_tree with unsigned int in for_each_free_tree loops. Cc: stable@vger.kernel.org Fixes: a68c7eaa7a8f ("drm/amdgpu: Enable clear page functionality") Signed-off-by: Arunpravin Paneer Selvam Suggested-by: Matthew Auld Reviewed-by: Matthew Auld Closes: https://gitlab.freedesktop.org/drm/amd/-/issues/4260 Link: https://lore.kernel.org/r/20251006095124.1663-2-Arunpravin.PaneerSelvam@amd.com Signed-off-by: Greg Kroah-Hartman

drm/buddy: Optimize free block management with RB tree

2026-01-08T09:17:16+00:00

commit c178e534fff1d5a74da80ea03b20e2b948a00113 upstream. 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. As the buddy allocator evolves with new features such as clear-page tracking, the resulting fragmentation and complexity have grown. These RB-tree based design changes are introduced to address that growth and ensure the allocator continues to perform efficiently under fragmented conditions. The RB tree implementation with separate clear/dirty trees provides: - O(n log n) aggregate complexity for all operations instead of O(n^2) - Elimination of soft lockups and system instability - Improved code maintainability and clarity - Better scalability for large memory systems - Predictable performance under fragmentation 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. v5: - Remove the inline in a .c file (Jani Nikula). v6(Peter Zijlstra): - Add rb_add() function replacing the existing rbtree_insert() code. v7: - A full walk iteration in rbtree is slower than the list (Peter Zijlstra). - The existing rbtree_postorder_for_each_entry_safe macro should be used in scenarios where traversal order is not a critical factor (Christian). v8(Matthew): - Remove the rbtree_is_empty() check in this patch as well. Cc: stable@vger.kernel.org Fixes: a68c7eaa7a8f ("drm/amdgpu: Enable clear page functionality") Signed-off-by: Arunpravin Paneer Selvam Reviewed-by: Matthew Auld Link: https://lore.kernel.org/r/20251006095124.1663-1-Arunpravin.PaneerSelvam@amd.com Signed-off-by: Greg Kroah-Hartman

Merge drm/drm-next into drm-intel-next

2025-09-10T12:01:42+00:00

Catching up with some display dependencies. Signed-off-by: Rodrigo Vivi

overflow: add range_overflows() and range_end_overflows()

2025-09-08T12:36:19+00:00

Move the range_overflows() and range_end_overflows() along with the _t variants over from drm/i915 and drm/buddy to overflow.h. Cc: Kees Cook Cc: "Gustavo A. R. Silva" Cc: linux-hardening@vger.kernel.org Reviewed-by: Kees Cook Reviewed-by: Jouni Högander Acked-by: Thomas Zimmermann Link: https://lore.kernel.org/r/20250829174601.2163064-3-jani.nikula@intel.com Signed-off-by: Jani Nikula

drm/amdgpu: Reset the clear flag in buddy during resume

2025-07-16T10:50:32+00:00

- Added a handler in DRM buddy manager to reset the cleared flag for the blocks in the freelist. - This is necessary because, upon resuming, the VRAM becomes cluttered with BIOS data, yet the VRAM backend manager believes that everything has been cleared. v2: - Add lock before accessing drm_buddy_clear_reset_blocks()(Matthew Auld) - Force merge the two dirty blocks.(Matthew Auld) - Add a new unit test case for this issue.(Matthew Auld) - Having this function being able to flip the state either way would be good. (Matthew Brost) v3(Matthew Auld): - Do merge step first to avoid the use of extra reset flag. Signed-off-by: Arunpravin Paneer Selvam Suggested-by: Christian König Acked-by: Christian König Reviewed-by: Matthew Auld Cc: stable@vger.kernel.org Fixes: a68c7eaa7a8f ("drm/amdgpu: Enable clear page functionality") Closes: https://gitlab.freedesktop.org/drm/amd/-/issues/3812 Signed-off-by: Christian König Link: https://lore.kernel.org/r/20250716075125.240637-2-Arunpravin.PaneerSelvam@amd.com

drm/buddy: Add start address support to trim function

2024-08-07T22:19:00+00:00

- Add a new start parameter in trim function to specify exact address from where to start the trimming. This would help us in situations like if drivers would like to do address alignment for specific requirements. - Add a new flag DRM_BUDDY_TRIM_DISABLE. Drivers can use this flag to disable the allocator trimming part. This patch enables the drivers control trimming and they can do it themselves based on the application requirements. v1:(Matthew) - check new_start alignment with min chunk_size - use range_overflows() Signed-off-by: Arunpravin Paneer Selvam Acked-by: Alex Deucher Acked-by: Christian König Signed-off-by: Alex Deucher (cherry picked from commit db65eb46de135338d6177f8853e0fd208f19d63e)

Merge tag 'drm-misc-fixes-2024-05-23' of https://gitlab.freedesktop.org/drm/misc/kernel into drm-fixes

2024-05-27T03:47:14+00:00

Short summary of fixes pull: buddy: - stop using PAGE_SIZE shmem-helper: - avoid kernel panic in mmap() tests: - buddy: fix PAGE_SIZE dependency Signed-off-by: Dave Airlie From: Thomas Zimmermann Link: https://patchwork.freedesktop.org/patch/msgid/20240523184745.GA11363@localhost.localdomain

drm/buddy: stop using PAGE_SIZE

2024-05-17T10:56:42+00:00

The drm_buddy minimum page-size requirements should be distinct from the CPU PAGE_SIZE. Only restriction is that the minimum page-size is at least 4K. Signed-off-by: Matthew Auld Cc: Arunpravin Paneer Selvam Cc: Christian König Cc: Arnd Bergmann Reviewed-by: Arunpravin Paneer Selvam Acked-by: Arnd Bergmann Link: https://patchwork.freedesktop.org/patch/msgid/20240229105112.250077-3-matthew.auld@intel.com Signed-off-by: Christian König

drm/buddy: Implement tracking clear page feature

2024-04-22T17:44:16+00:00

- Add tracking clear page feature. - Driver should enable the DRM_BUDDY_CLEARED flag if it successfully clears the blocks in the free path. On the otherhand, DRM buddy marks each block as cleared. - Track the available cleared pages size - If driver requests cleared memory we prefer cleared memory but fallback to uncleared if we can't find the cleared blocks. when driver requests uncleared memory we try to use uncleared but fallback to cleared memory if necessary. - When a block gets freed we clear it and mark the freed block as cleared, when there are buddies which are cleared as well we can merge them. Otherwise, we prefer to keep the blocks as separated. - Add a function to support defragmentation. v1: - Depends on the flag check DRM_BUDDY_CLEARED, enable the block as cleared. Else, reset the clear flag for each block in the list(Christian) - For merging the 2 cleared blocks compare as below, drm_buddy_is_clear(block) != drm_buddy_is_clear(buddy)(Christian) - Defragment the memory beginning from min_order till the required memory space is available. v2: (Matthew) - Add a wrapper drm_buddy_free_list_internal for the freeing of blocks operation within drm buddy. - Write a macro block_incompatible() to allocate the required blocks. - Update the xe driver for the drm_buddy_free_list change in arguments. - add a warning if the two blocks are incompatible on defragmentation - call full defragmentation in the fini() function - place a condition to test if min_order is equal to 0 - replace the list with safe_reverse() variant as we might remove the block from the list. v3: - fix Gitlab user reported lockup issue. - Keep DRM_BUDDY_HEADER_CLEAR define sorted(Matthew) - modify to pass the root order instead max_order in fini() function(Matthew) - change bool 1 to true(Matthew) - add check if min_block_size is power of 2(Matthew) - modify the min_block_size datatype to u64(Matthew) v4: - rename the function drm_buddy_defrag with __force_merge. - Include __force_merge directly in drm buddy file and remove the defrag use in amdgpu driver. - Remove list_empty() check(Matthew) - Remove unnecessary space, headers and placement of new variables(Matthew) - Add a unit test case(Matthew) v5: - remove force merge support to actual range allocation and not to bail out when contains && split(Matthew) - add range support to force merge function. v6: - modify the alloc_range() function clear page non merged blocks allocation(Matthew) - correct the list_insert function name(Matthew). Signed-off-by: Arunpravin Paneer Selvam Signed-off-by: Matthew Auld Suggested-by: Christian König Suggested-by: Matthew Auld Reviewed-by: Matthew Auld Link: https://patchwork.freedesktop.org/patch/msgid/20240419063538.11957-1-Arunpravin.PaneerSelvam@amd.com Signed-off-by: Christian König

drm/buddy: Improve contiguous memory allocation

2023-09-11T18:18:00+00:00

Problem statement: The current method roundup_power_of_two() to allocate contiguous address triggers -ENOSPC in some cases even though we have enough free spaces and so to help with that we introduce a try harder mechanism. In case of -ENOSPC, the new try harder mechanism rounddown the original size to power of 2 and iterating over the round down sized freelist blocks to allocate the required size traversing RHS and LHS. As part of the above new method implementation we moved contiguous/alignment size computation part and trim function to the drm buddy file. v2: Modify the alloc_range() function to return total allocated size on -ENOSPC err and traverse RHS/LHS to allocate the required size (Matthew). Signed-off-by: Arunpravin Paneer Selvam Link: https://patchwork.freedesktop.org/patch/msgid/20230909160902.15644-1-Arunpravin.PaneerSelvam@amd.com Reviewed-by: Matthew Auld Signed-off-by: Christian König