linux/drivers/gpu/drm/drm_buddy.c
Linus Torvalds 260f6f4fda drm for 6.17-rc1
non-drm:
 rust:
 - make ETIMEDOUT available
 - add size constants up to SZ_2G
 - add DMA coherent allocation bindings
 mtd:
 - driver for Intel GPU non-volatile storage
 i2c
 - designware quirk for Intel xe
 
 core:
 - atomic helpers: tune enable/disable sequences
 - add task info to wedge API
 - refactor EDID quirks
 - connector: move HDR sink to drm_display_info
 - fourcc: half-float and 32-bit float formats
 - mode_config: pass format info to simplify
 
 dma-buf:
 - heaps: Give CMA heap a stable name
 
 ci:
 - add device tree validation and kunit
 
 displayport:
 - change AUX DPCD access probe address
 - add quirk for DPCD probe
 - add panel replay definitions
 - backlight control helpers
 
 fbdev:
 - make CONFIG_FIRMWARE_EDID available on all arches
 
 fence:
 - fix UAF issues
 
 format-helper:
 - improve tests
 
 gpusvm:
 - introduce devmem only flag for allocation
 - add timeslicing support to GPU SVM
 
 ttm:
 - improve eviction
 
 sched:
 - tracing improvements
 - kunit improvements
 - memory leak fixes
 - reset handling improvements
 
 color mgmt:
 - add hardware gamma LUT handling helpers
 
 bridge:
 - add destroy hook
 - switch to reference counted drm_bridge allocations
 - tc358767: convert to devm_drm_bridge_alloc
 - improve CEC handling
 
 panel:
 - switch to reference counter drm_panel allocations
 - fwnode panel lookup
 - Huiling hl055fhv028c support
 - Raspberry Pi 7" 720x1280 support
 - edp: KDC KD116N3730A05, N160JCE-ELL CMN, N116BCJ-EAK
 - simple: AUO P238HAN01
 - st7701: Winstar wf40eswaa6mnn0
 - visionox: rm69299-shift
 - Renesas R61307, Renesas R69328 support
 - DJN HX83112B
 
 hdmi:
 - add CEC handling
 - YUV420 output support
 
 xe:
 - WildCat Lake support
 - Enable PanthorLake by default
 - mark BMG as SRIOV capable
 - update firmware recommendations
 - Expose media OA units
 - aux-bux support for non-volatile memory
 - MTD intel-dg driver for non-volatile memory
 - Expose fan control and voltage regulator in sysfs
 - restructure migration for multi-device
 - Restore GuC submit UAF fix
 - make GEM shrinker drm managed
 - SRIOV VF Post-migration recovery of GGTT nodes
 - W/A additions/reworks
 - Prefetch support for svm ranges
 - Don't allocate managed BO for each policy change
 - HWMON fixes for BMG
 - Create LRC BO without VM
 - PCI ID updates
 - make SLPC debugfs files optional
 - rework eviction rejection of bound external BOs
 - consolidate PAT programming logic for pre/post Xe2
 - init changes for flicker-free boot
 - Enable GuC Dynamic Inhibit Context switch
 
 i915:
 - drm_panic support for i915/xe
 - initial flip queue off by default for LNL/PNL
 - Wildcat Lake Display support
 - Support for DSC fractional link bpp
 - Support for simultaneous Panel Replay and Adaptive sync
 - Support for PTL+ double buffer LUT
 - initial PIPEDMC event handling
 - drm_panel_follower support
 - DPLL interface renames
 - allocate struct intel_display dynamically
 - flip queue preperation
 - abstract DRAM detection better
 - avoid GuC scheduling stalls
 - remove DG1 force probe requirement
 - fix MEI interrupt handler on RT kernels
 - use backlight control helpers for eDP
 - more shared display code refactoring
 
 amdgpu:
 - add userq slot to INFO ioctl
 - SR-IOV hibernation support
 - Suspend improvements
 - Backlight improvements
 - Use scaling for non-native eDP modes
 - cleaner shader updates for GC 9.x
 - Remove fence slab
 - SDMA fw checks for userq support
 - RAS updates
 - DMCUB updates
 - DP tunneling fixes
 - Display idle D3 support
 - Per queue reset improvements
 - initial smartmux support
 
 amdkfd:
 - enable KFD on loongarch
 - mtype fix for ext coherent system memory
 
 radeon:
 - CS validation additional GL extensions
 - drop console lock during suspend/resume
 - bump driver version
 
 msm:
 - VM BIND support
 - CI: infrastructure updates
 - UBWC single source of truth
 - decouple GPU and KMS support
 - DP: rework I/O accessors
 - DPU: SM8750 support
 - DSI: SM8750 support
 - GPU: X1-45 support and speedbin support for X1-85
 - MDSS: SM8750 support
 
 nova:
 - register! macro improvements
 - DMA object abstraction
 - VBIOS parser + fwsec lookup
 - sysmem flush page support
 - falcon: generic falcon boot code and HAL
 - FWSEC-FRTS: fb setup and load/execute
 
 ivpu:
 - Add Wildcat Lake support
 - Add turbo flag
 
 ast:
 - improve hardware generations implementation
 
 imx:
 - IMX8qxq Display Controller support
 
 lima:
 - Rockchip RK3528 GPU support
 
 nouveau:
 - fence handling cleanup
 
 panfrost:
 - MT8370 support
 - bo labeling
 - 64-bit register access
 
 qaic:
 - add RAS support
 
 rockchip:
 - convert inno_hdmi to a bridge
 
 rz-du:
 - add RZ/V2H(P) support
 - MIPI-DSI DCS support
 
 sitronix:
 - ST7567 support
 
 sun4i:
 - add H616 support
 
 tidss:
 - add TI AM62L support
 - AM65x OLDI bridge support
 
 bochs:
 - drm panic support
 
 vkms:
 - YUV and R* format support
 - use faux device
 
 vmwgfx:
 - fence improvements
 
 hyperv:
 - move out of simple
 - add drm_panic support
 -----BEGIN PGP SIGNATURE-----
 
 iQIzBAABCgAdFiEEEKbZHaGwW9KfbeusDHTzWXnEhr4FAmiJM/0ACgkQDHTzWXnE
 hr6MpA/+JJKGdSdrE95QkaMcOZh/3e3areGXZ0V/RrrJXdB4/DoAfQSHhF0H7m7y
 MhBGVLGNMXq7KHrz28p1MjLHrE1mwmvJ6hZ4J076ed4u9naoCD0m6k5w5wiue+KL
 HyPR54ADxN0BYmgV0l/B0wj42KsHyTO4x4hdqPJu02V9Dtmx6FCh2ujkOF3p9nbK
 GMwWDttl4KEKljD0IvQ9YIYJ66crYGx/XmZi7JoWRrS104K/h1u8qZuXBp5jVKTy
 OZRAVyLdmJqdTOLH7l599MBBcEd/bNV37/LVwF4T5iFunEKOAiyN0QY0OR+IeRVh
 ZfOv2/gp4UNyIfyahQ7LKLgEilNPGHoPitvDJPvBZxW2UjwXVNvA1QfdK5DAlVRS
 D5NoFRjlFFCz8/c2hQwlKJ9o7eVgH3/pK0mwR7SPGQTuqzLFCrAfCuzUvg/gV++6
 JFqmGKMHeCoxO2o4GMrwjFttStP41usxtV/D+grcbPteNO9UyKJS4C38n4eamJXM
 a9Sy9APuAb6F0w5+yMItEF7TQifgmhIbm5AZHlxE1KoDQV6TdiIf1Gou5LeDGoL6
 OACbXHJPL52tUnfCRpbfI4tE/IVyYsfL01JnvZ5cZZWItXfcIz76ykJri+E0G60g
 yRl/zkimHKO4B0l/HSzal5xROXr+3VzeWehEiz/ot1VriP5OesA=
 =n9MO
 -----END PGP SIGNATURE-----

Merge tag 'drm-next-2025-07-30' of https://gitlab.freedesktop.org/drm/kernel

Pull drm updates from Dave Airlie:
 "Highlights:

   - Intel xe enable Panthor Lake, started adding WildCat Lake

   - amdgpu has a bunch of reset improvments along with the usual IP
     updates

   - msm got VM_BIND support which is important for vulkan sparse memory

   - more drm_panic users

   - gpusvm common code to handle a bunch of core SVM work outside
     drivers.

  Detail summary:

  Changes outside drm subdirectory:
   - 'shrink_shmem_memory()' for better shmem/hibernate interaction
   - Rust support infrastructure:
      - make ETIMEDOUT available
      - add size constants up to SZ_2G
      - add DMA coherent allocation bindings
   - mtd driver for Intel GPU non-volatile storage
   - i2c designware quirk for Intel xe

  core:
   - atomic helpers: tune enable/disable sequences
   - add task info to wedge API
   - refactor EDID quirks
   - connector: move HDR sink to drm_display_info
   - fourcc: half-float and 32-bit float formats
   - mode_config: pass format info to simplify

  dma-buf:
   - heaps: Give CMA heap a stable name

  ci:
   - add device tree validation and kunit

  displayport:
   - change AUX DPCD access probe address
   - add quirk for DPCD probe
   - add panel replay definitions
   - backlight control helpers

  fbdev:
   - make CONFIG_FIRMWARE_EDID available on all arches

  fence:
   - fix UAF issues

  format-helper:
   - improve tests

  gpusvm:
   - introduce devmem only flag for allocation
   - add timeslicing support to GPU SVM

  ttm:
   - improve eviction

  sched:
   - tracing improvements
   - kunit improvements
   - memory leak fixes
   - reset handling improvements

  color mgmt:
   - add hardware gamma LUT handling helpers

  bridge:
   - add destroy hook
   - switch to reference counted drm_bridge allocations
   - tc358767: convert to devm_drm_bridge_alloc
   - improve CEC handling

  panel:
   - switch to reference counter drm_panel allocations
   - fwnode panel lookup
   - Huiling hl055fhv028c support
   - Raspberry Pi 7" 720x1280 support
   - edp: KDC KD116N3730A05, N160JCE-ELL CMN, N116BCJ-EAK
   - simple: AUO P238HAN01
   - st7701: Winstar wf40eswaa6mnn0
   - visionox: rm69299-shift
   - Renesas R61307, Renesas R69328 support
   - DJN HX83112B

  hdmi:
   - add CEC handling
   - YUV420 output support

  xe:
   - WildCat Lake support
   - Enable PanthorLake by default
   - mark BMG as SRIOV capable
   - update firmware recommendations
   - Expose media OA units
   - aux-bux support for non-volatile memory
   - MTD intel-dg driver for non-volatile memory
   - Expose fan control and voltage regulator in sysfs
   - restructure migration for multi-device
   - Restore GuC submit UAF fix
   - make GEM shrinker drm managed
   - SRIOV VF Post-migration recovery of GGTT nodes
   - W/A additions/reworks
   - Prefetch support for svm ranges
   - Don't allocate managed BO for each policy change
   - HWMON fixes for BMG
   - Create LRC BO without VM
   - PCI ID updates
   - make SLPC debugfs files optional
   - rework eviction rejection of bound external BOs
   - consolidate PAT programming logic for pre/post Xe2
   - init changes for flicker-free boot
   - Enable GuC Dynamic Inhibit Context switch

  i915:
   - drm_panic support for i915/xe
   - initial flip queue off by default for LNL/PNL
   - Wildcat Lake Display support
   - Support for DSC fractional link bpp
   - Support for simultaneous Panel Replay and Adaptive sync
   - Support for PTL+ double buffer LUT
   - initial PIPEDMC event handling
   - drm_panel_follower support
   - DPLL interface renames
   - allocate struct intel_display dynamically
   - flip queue preperation
   - abstract DRAM detection better
   - avoid GuC scheduling stalls
   - remove DG1 force probe requirement
   - fix MEI interrupt handler on RT kernels
   - use backlight control helpers for eDP
   - more shared display code refactoring

  amdgpu:
   - add userq slot to INFO ioctl
   - SR-IOV hibernation support
   - Suspend improvements
   - Backlight improvements
   - Use scaling for non-native eDP modes
   - cleaner shader updates for GC 9.x
   - Remove fence slab
   - SDMA fw checks for userq support
   - RAS updates
   - DMCUB updates
   - DP tunneling fixes
   - Display idle D3 support
   - Per queue reset improvements
   - initial smartmux support

  amdkfd:
   - enable KFD on loongarch
   - mtype fix for ext coherent system memory

  radeon:
   - CS validation additional GL extensions
   - drop console lock during suspend/resume
   - bump driver version

  msm:
   - VM BIND support
   - CI: infrastructure updates
   - UBWC single source of truth
   - decouple GPU and KMS support
   - DP: rework I/O accessors
   - DPU: SM8750 support
   - DSI: SM8750 support
   - GPU: X1-45 support and speedbin support for X1-85
   - MDSS: SM8750 support

  nova:
   - register! macro improvements
   - DMA object abstraction
   - VBIOS parser + fwsec lookup
   - sysmem flush page support
   - falcon: generic falcon boot code and HAL
   - FWSEC-FRTS: fb setup and load/execute

  ivpu:
   - Add Wildcat Lake support
   - Add turbo flag

  ast:
   - improve hardware generations implementation

  imx:
   - IMX8qxq Display Controller support

  lima:
   - Rockchip RK3528 GPU support

  nouveau:
   - fence handling cleanup

  panfrost:
   - MT8370 support
   - bo labeling
   - 64-bit register access

  qaic:
   - add RAS support

  rockchip:
   - convert inno_hdmi to a bridge

  rz-du:
   - add RZ/V2H(P) support
   - MIPI-DSI DCS support

  sitronix:
   - ST7567 support

  sun4i:
   - add H616 support

  tidss:
   - add TI AM62L support
   - AM65x OLDI bridge support

  bochs:
   - drm panic support

  vkms:
   - YUV and R* format support
   - use faux device

  vmwgfx:
   - fence improvements

  hyperv:
   - move out of simple
   - add drm_panic support"

* tag 'drm-next-2025-07-30' of https://gitlab.freedesktop.org/drm/kernel: (1479 commits)
  drm/tidss: oldi: convert to devm_drm_bridge_alloc() API
  drm/tidss: encoder: convert to devm_drm_bridge_alloc()
  drm/amdgpu: move reset support type checks into the caller
  drm/amdgpu/sdma7: re-emit unprocessed state on ring reset
  drm/amdgpu/sdma6: re-emit unprocessed state on ring reset
  drm/amdgpu/sdma5.2: re-emit unprocessed state on ring reset
  drm/amdgpu/sdma5: re-emit unprocessed state on ring reset
  drm/amdgpu/gfx12: re-emit unprocessed state on ring reset
  drm/amdgpu/gfx11: re-emit unprocessed state on ring reset
  drm/amdgpu/gfx10: re-emit unprocessed state on ring reset
  drm/amdgpu/gfx9.4.3: re-emit unprocessed state on kcq reset
  drm/amdgpu/gfx9: re-emit unprocessed state on kcq reset
  drm/amdgpu: Add WARN_ON to the resource clear function
  drm/amd/pm: Use cached metrics data on SMUv13.0.6
  drm/amd/pm: Use cached data for min/max clocks
  gpu: nova-core: fix bounds check in PmuLookupTableEntry::new
  drm/amdgpu: Replace HQD terminology with slots naming
  drm/amdgpu: Add user queue instance count in HW IP info
  drm/amd/amdgpu: Add helper functions for isp buffers
  drm/amd/amdgpu: Initialize swnode for ISP MFD device
  ...
2025-07-30 19:26:49 -07:00

1244 lines
28 KiB
C

// SPDX-License-Identifier: MIT
/*
* Copyright © 2021 Intel Corporation
*/
#include <kunit/test-bug.h>
#include <linux/export.h>
#include <linux/kmemleak.h>
#include <linux/module.h>
#include <linux/sizes.h>
#include <drm/drm_buddy.h>
static struct kmem_cache *slab_blocks;
static struct drm_buddy_block *drm_block_alloc(struct drm_buddy *mm,
struct drm_buddy_block *parent,
unsigned int order,
u64 offset)
{
struct drm_buddy_block *block;
BUG_ON(order > DRM_BUDDY_MAX_ORDER);
block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL);
if (!block)
return NULL;
block->header = offset;
block->header |= order;
block->parent = parent;
BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED);
return block;
}
static void drm_block_free(struct drm_buddy *mm,
struct drm_buddy_block *block)
{
kmem_cache_free(slab_blocks, block);
}
static void list_insert_sorted(struct drm_buddy *mm,
struct drm_buddy_block *block)
{
struct drm_buddy_block *node;
struct list_head *head;
head = &mm->free_list[drm_buddy_block_order(block)];
if (list_empty(head)) {
list_add(&block->link, head);
return;
}
list_for_each_entry(node, head, link)
if (drm_buddy_block_offset(block) < drm_buddy_block_offset(node))
break;
__list_add(&block->link, node->link.prev, &node->link);
}
static void clear_reset(struct drm_buddy_block *block)
{
block->header &= ~DRM_BUDDY_HEADER_CLEAR;
}
static void mark_cleared(struct drm_buddy_block *block)
{
block->header |= DRM_BUDDY_HEADER_CLEAR;
}
static void mark_allocated(struct drm_buddy_block *block)
{
block->header &= ~DRM_BUDDY_HEADER_STATE;
block->header |= DRM_BUDDY_ALLOCATED;
list_del(&block->link);
}
static void mark_free(struct drm_buddy *mm,
struct drm_buddy_block *block)
{
block->header &= ~DRM_BUDDY_HEADER_STATE;
block->header |= DRM_BUDDY_FREE;
list_insert_sorted(mm, block);
}
static void mark_split(struct drm_buddy_block *block)
{
block->header &= ~DRM_BUDDY_HEADER_STATE;
block->header |= DRM_BUDDY_SPLIT;
list_del(&block->link);
}
static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
{
return s1 <= e2 && e1 >= s2;
}
static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2)
{
return s1 <= s2 && e1 >= e2;
}
static struct drm_buddy_block *
__get_buddy(struct drm_buddy_block *block)
{
struct drm_buddy_block *parent;
parent = block->parent;
if (!parent)
return NULL;
if (parent->left == block)
return parent->right;
return parent->left;
}
static unsigned int __drm_buddy_free(struct drm_buddy *mm,
struct drm_buddy_block *block,
bool force_merge)
{
struct drm_buddy_block *parent;
unsigned int order;
while ((parent = block->parent)) {
struct drm_buddy_block *buddy;
buddy = __get_buddy(block);
if (!drm_buddy_block_is_free(buddy))
break;
if (!force_merge) {
/*
* Check the block and its buddy clear state and exit
* the loop if they both have the dissimilar state.
*/
if (drm_buddy_block_is_clear(block) !=
drm_buddy_block_is_clear(buddy))
break;
if (drm_buddy_block_is_clear(block))
mark_cleared(parent);
}
list_del(&buddy->link);
if (force_merge && drm_buddy_block_is_clear(buddy))
mm->clear_avail -= drm_buddy_block_size(mm, buddy);
drm_block_free(mm, block);
drm_block_free(mm, buddy);
block = parent;
}
order = drm_buddy_block_order(block);
mark_free(mm, block);
return order;
}
static int __force_merge(struct drm_buddy *mm,
u64 start,
u64 end,
unsigned int min_order)
{
unsigned int order;
int i;
if (!min_order)
return -ENOMEM;
if (min_order > mm->max_order)
return -EINVAL;
for (i = min_order - 1; i >= 0; i--) {
struct drm_buddy_block *block, *prev;
list_for_each_entry_safe_reverse(block, prev, &mm->free_list[i], link) {
struct drm_buddy_block *buddy;
u64 block_start, block_end;
if (!block->parent)
continue;
block_start = drm_buddy_block_offset(block);
block_end = block_start + drm_buddy_block_size(mm, block) - 1;
if (!contains(start, end, block_start, block_end))
continue;
buddy = __get_buddy(block);
if (!drm_buddy_block_is_free(buddy))
continue;
WARN_ON(drm_buddy_block_is_clear(block) ==
drm_buddy_block_is_clear(buddy));
/*
* If the prev block is same as buddy, don't access the
* block in the next iteration as we would free the
* buddy block as part of the free function.
*/
if (prev == buddy)
prev = list_prev_entry(prev, link);
list_del(&block->link);
if (drm_buddy_block_is_clear(block))
mm->clear_avail -= drm_buddy_block_size(mm, block);
order = __drm_buddy_free(mm, block, true);
if (order >= min_order)
return 0;
}
}
return -ENOMEM;
}
/**
* drm_buddy_init - init memory manager
*
* @mm: DRM buddy manager to initialize
* @size: size in bytes to manage
* @chunk_size: minimum page size in bytes for our allocations
*
* Initializes the memory manager and its resources.
*
* Returns:
* 0 on success, error code on failure.
*/
int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size)
{
unsigned int i;
u64 offset;
if (size < chunk_size)
return -EINVAL;
if (chunk_size < SZ_4K)
return -EINVAL;
if (!is_power_of_2(chunk_size))
return -EINVAL;
size = round_down(size, chunk_size);
mm->size = size;
mm->avail = size;
mm->clear_avail = 0;
mm->chunk_size = chunk_size;
mm->max_order = ilog2(size) - ilog2(chunk_size);
BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER);
mm->free_list = kmalloc_array(mm->max_order + 1,
sizeof(struct list_head),
GFP_KERNEL);
if (!mm->free_list)
return -ENOMEM;
for (i = 0; i <= mm->max_order; ++i)
INIT_LIST_HEAD(&mm->free_list[i]);
mm->n_roots = hweight64(size);
mm->roots = kmalloc_array(mm->n_roots,
sizeof(struct drm_buddy_block *),
GFP_KERNEL);
if (!mm->roots)
goto out_free_list;
offset = 0;
i = 0;
/*
* Split into power-of-two blocks, in case we are given a size that is
* not itself a power-of-two.
*/
do {
struct drm_buddy_block *root;
unsigned int order;
u64 root_size;
order = ilog2(size) - ilog2(chunk_size);
root_size = chunk_size << order;
root = drm_block_alloc(mm, NULL, order, offset);
if (!root)
goto out_free_roots;
mark_free(mm, root);
BUG_ON(i > mm->max_order);
BUG_ON(drm_buddy_block_size(mm, root) < chunk_size);
mm->roots[i] = root;
offset += root_size;
size -= root_size;
i++;
} while (size);
return 0;
out_free_roots:
while (i--)
drm_block_free(mm, mm->roots[i]);
kfree(mm->roots);
out_free_list:
kfree(mm->free_list);
return -ENOMEM;
}
EXPORT_SYMBOL(drm_buddy_init);
/**
* drm_buddy_fini - tear down the memory manager
*
* @mm: DRM buddy manager to free
*
* Cleanup memory manager resources and the freelist
*/
void drm_buddy_fini(struct drm_buddy *mm)
{
u64 root_size, size, start;
unsigned int order;
int i;
size = mm->size;
for (i = 0; i < mm->n_roots; ++i) {
order = ilog2(size) - ilog2(mm->chunk_size);
start = drm_buddy_block_offset(mm->roots[i]);
__force_merge(mm, start, start + size, order);
if (WARN_ON(!drm_buddy_block_is_free(mm->roots[i])))
kunit_fail_current_test("buddy_fini() root");
drm_block_free(mm, mm->roots[i]);
root_size = mm->chunk_size << order;
size -= root_size;
}
WARN_ON(mm->avail != mm->size);
kfree(mm->roots);
kfree(mm->free_list);
}
EXPORT_SYMBOL(drm_buddy_fini);
static int split_block(struct drm_buddy *mm,
struct drm_buddy_block *block)
{
unsigned int block_order = drm_buddy_block_order(block) - 1;
u64 offset = drm_buddy_block_offset(block);
BUG_ON(!drm_buddy_block_is_free(block));
BUG_ON(!drm_buddy_block_order(block));
block->left = drm_block_alloc(mm, block, block_order, offset);
if (!block->left)
return -ENOMEM;
block->right = drm_block_alloc(mm, block, block_order,
offset + (mm->chunk_size << block_order));
if (!block->right) {
drm_block_free(mm, block->left);
return -ENOMEM;
}
mark_free(mm, block->left);
mark_free(mm, block->right);
if (drm_buddy_block_is_clear(block)) {
mark_cleared(block->left);
mark_cleared(block->right);
clear_reset(block);
}
mark_split(block);
return 0;
}
/**
* drm_get_buddy - get buddy address
*
* @block: DRM buddy block
*
* Returns the corresponding buddy block for @block, or NULL
* if this is a root block and can't be merged further.
* Requires some kind of locking to protect against
* any concurrent allocate and free operations.
*/
struct drm_buddy_block *
drm_get_buddy(struct drm_buddy_block *block)
{
return __get_buddy(block);
}
EXPORT_SYMBOL(drm_get_buddy);
/**
* drm_buddy_reset_clear - reset blocks clear state
*
* @mm: DRM buddy manager
* @is_clear: blocks clear state
*
* Reset the clear state based on @is_clear value for each block
* in the freelist.
*/
void drm_buddy_reset_clear(struct drm_buddy *mm, bool is_clear)
{
u64 root_size, size, start;
unsigned int order;
int i;
size = mm->size;
for (i = 0; i < mm->n_roots; ++i) {
order = ilog2(size) - ilog2(mm->chunk_size);
start = drm_buddy_block_offset(mm->roots[i]);
__force_merge(mm, start, start + size, order);
root_size = mm->chunk_size << order;
size -= root_size;
}
for (i = 0; i <= mm->max_order; ++i) {
struct drm_buddy_block *block;
list_for_each_entry_reverse(block, &mm->free_list[i], link) {
if (is_clear != drm_buddy_block_is_clear(block)) {
if (is_clear) {
mark_cleared(block);
mm->clear_avail += drm_buddy_block_size(mm, block);
} else {
clear_reset(block);
mm->clear_avail -= drm_buddy_block_size(mm, block);
}
}
}
}
}
EXPORT_SYMBOL(drm_buddy_reset_clear);
/**
* drm_buddy_free_block - free a block
*
* @mm: DRM buddy manager
* @block: block to be freed
*/
void drm_buddy_free_block(struct drm_buddy *mm,
struct drm_buddy_block *block)
{
BUG_ON(!drm_buddy_block_is_allocated(block));
mm->avail += drm_buddy_block_size(mm, block);
if (drm_buddy_block_is_clear(block))
mm->clear_avail += drm_buddy_block_size(mm, block);
__drm_buddy_free(mm, block, false);
}
EXPORT_SYMBOL(drm_buddy_free_block);
static void __drm_buddy_free_list(struct drm_buddy *mm,
struct list_head *objects,
bool mark_clear,
bool mark_dirty)
{
struct drm_buddy_block *block, *on;
WARN_ON(mark_dirty && mark_clear);
list_for_each_entry_safe(block, on, objects, link) {
if (mark_clear)
mark_cleared(block);
else if (mark_dirty)
clear_reset(block);
drm_buddy_free_block(mm, block);
cond_resched();
}
INIT_LIST_HEAD(objects);
}
static void drm_buddy_free_list_internal(struct drm_buddy *mm,
struct list_head *objects)
{
/*
* Don't touch the clear/dirty bit, since allocation is still internal
* at this point. For example we might have just failed part of the
* allocation.
*/
__drm_buddy_free_list(mm, objects, false, false);
}
/**
* drm_buddy_free_list - free blocks
*
* @mm: DRM buddy manager
* @objects: input list head to free blocks
* @flags: optional flags like DRM_BUDDY_CLEARED
*/
void drm_buddy_free_list(struct drm_buddy *mm,
struct list_head *objects,
unsigned int flags)
{
bool mark_clear = flags & DRM_BUDDY_CLEARED;
__drm_buddy_free_list(mm, objects, mark_clear, !mark_clear);
}
EXPORT_SYMBOL(drm_buddy_free_list);
static bool block_incompatible(struct drm_buddy_block *block, unsigned int flags)
{
bool needs_clear = flags & DRM_BUDDY_CLEAR_ALLOCATION;
return needs_clear != drm_buddy_block_is_clear(block);
}
static struct drm_buddy_block *
__alloc_range_bias(struct drm_buddy *mm,
u64 start, u64 end,
unsigned int order,
unsigned long flags,
bool fallback)
{
u64 req_size = mm->chunk_size << order;
struct drm_buddy_block *block;
struct drm_buddy_block *buddy;
LIST_HEAD(dfs);
int err;
int i;
end = end - 1;
for (i = 0; i < mm->n_roots; ++i)
list_add_tail(&mm->roots[i]->tmp_link, &dfs);
do {
u64 block_start;
u64 block_end;
block = list_first_entry_or_null(&dfs,
struct drm_buddy_block,
tmp_link);
if (!block)
break;
list_del(&block->tmp_link);
if (drm_buddy_block_order(block) < order)
continue;
block_start = drm_buddy_block_offset(block);
block_end = block_start + drm_buddy_block_size(mm, block) - 1;
if (!overlaps(start, end, block_start, block_end))
continue;
if (drm_buddy_block_is_allocated(block))
continue;
if (block_start < start || block_end > end) {
u64 adjusted_start = max(block_start, start);
u64 adjusted_end = min(block_end, end);
if (round_down(adjusted_end + 1, req_size) <=
round_up(adjusted_start, req_size))
continue;
}
if (!fallback && block_incompatible(block, flags))
continue;
if (contains(start, end, block_start, block_end) &&
order == drm_buddy_block_order(block)) {
/*
* Find the free block within the range.
*/
if (drm_buddy_block_is_free(block))
return block;
continue;
}
if (!drm_buddy_block_is_split(block)) {
err = split_block(mm, block);
if (unlikely(err))
goto err_undo;
}
list_add(&block->right->tmp_link, &dfs);
list_add(&block->left->tmp_link, &dfs);
} while (1);
return ERR_PTR(-ENOSPC);
err_undo:
/*
* We really don't want to leave around a bunch of split blocks, since
* bigger is better, so make sure we merge everything back before we
* free the allocated blocks.
*/
buddy = __get_buddy(block);
if (buddy &&
(drm_buddy_block_is_free(block) &&
drm_buddy_block_is_free(buddy)))
__drm_buddy_free(mm, block, false);
return ERR_PTR(err);
}
static struct drm_buddy_block *
__drm_buddy_alloc_range_bias(struct drm_buddy *mm,
u64 start, u64 end,
unsigned int order,
unsigned long flags)
{
struct drm_buddy_block *block;
bool fallback = false;
block = __alloc_range_bias(mm, start, end, order,
flags, fallback);
if (IS_ERR(block))
return __alloc_range_bias(mm, start, end, order,
flags, !fallback);
return block;
}
static struct drm_buddy_block *
get_maxblock(struct drm_buddy *mm, unsigned int order,
unsigned long flags)
{
struct drm_buddy_block *max_block = NULL, *block = NULL;
unsigned int i;
for (i = order; i <= mm->max_order; ++i) {
struct drm_buddy_block *tmp_block;
list_for_each_entry_reverse(tmp_block, &mm->free_list[i], link) {
if (block_incompatible(tmp_block, flags))
continue;
block = tmp_block;
break;
}
if (!block)
continue;
if (!max_block) {
max_block = block;
continue;
}
if (drm_buddy_block_offset(block) >
drm_buddy_block_offset(max_block)) {
max_block = block;
}
}
return max_block;
}
static struct drm_buddy_block *
alloc_from_freelist(struct drm_buddy *mm,
unsigned int order,
unsigned long flags)
{
struct drm_buddy_block *block = NULL;
unsigned int tmp;
int err;
if (flags & DRM_BUDDY_TOPDOWN_ALLOCATION) {
block = get_maxblock(mm, order, flags);
if (block)
/* Store the obtained block order */
tmp = drm_buddy_block_order(block);
} else {
for (tmp = order; tmp <= mm->max_order; ++tmp) {
struct drm_buddy_block *tmp_block;
list_for_each_entry_reverse(tmp_block, &mm->free_list[tmp], link) {
if (block_incompatible(tmp_block, flags))
continue;
block = tmp_block;
break;
}
if (block)
break;
}
}
if (!block) {
/* Fallback method */
for (tmp = order; tmp <= mm->max_order; ++tmp) {
if (!list_empty(&mm->free_list[tmp])) {
block = list_last_entry(&mm->free_list[tmp],
struct drm_buddy_block,
link);
if (block)
break;
}
}
if (!block)
return ERR_PTR(-ENOSPC);
}
BUG_ON(!drm_buddy_block_is_free(block));
while (tmp != order) {
err = split_block(mm, block);
if (unlikely(err))
goto err_undo;
block = block->right;
tmp--;
}
return block;
err_undo:
if (tmp != order)
__drm_buddy_free(mm, block, false);
return ERR_PTR(err);
}
static int __alloc_range(struct drm_buddy *mm,
struct list_head *dfs,
u64 start, u64 size,
struct list_head *blocks,
u64 *total_allocated_on_err)
{
struct drm_buddy_block *block;
struct drm_buddy_block *buddy;
u64 total_allocated = 0;
LIST_HEAD(allocated);
u64 end;
int err;
end = start + size - 1;
do {
u64 block_start;
u64 block_end;
block = list_first_entry_or_null(dfs,
struct drm_buddy_block,
tmp_link);
if (!block)
break;
list_del(&block->tmp_link);
block_start = drm_buddy_block_offset(block);
block_end = block_start + drm_buddy_block_size(mm, block) - 1;
if (!overlaps(start, end, block_start, block_end))
continue;
if (drm_buddy_block_is_allocated(block)) {
err = -ENOSPC;
goto err_free;
}
if (contains(start, end, block_start, block_end)) {
if (drm_buddy_block_is_free(block)) {
mark_allocated(block);
total_allocated += drm_buddy_block_size(mm, block);
mm->avail -= drm_buddy_block_size(mm, block);
if (drm_buddy_block_is_clear(block))
mm->clear_avail -= drm_buddy_block_size(mm, block);
list_add_tail(&block->link, &allocated);
continue;
} else if (!mm->clear_avail) {
err = -ENOSPC;
goto err_free;
}
}
if (!drm_buddy_block_is_split(block)) {
err = split_block(mm, block);
if (unlikely(err))
goto err_undo;
}
list_add(&block->right->tmp_link, dfs);
list_add(&block->left->tmp_link, dfs);
} while (1);
if (total_allocated < size) {
err = -ENOSPC;
goto err_free;
}
list_splice_tail(&allocated, blocks);
return 0;
err_undo:
/*
* We really don't want to leave around a bunch of split blocks, since
* bigger is better, so make sure we merge everything back before we
* free the allocated blocks.
*/
buddy = __get_buddy(block);
if (buddy &&
(drm_buddy_block_is_free(block) &&
drm_buddy_block_is_free(buddy)))
__drm_buddy_free(mm, block, false);
err_free:
if (err == -ENOSPC && total_allocated_on_err) {
list_splice_tail(&allocated, blocks);
*total_allocated_on_err = total_allocated;
} else {
drm_buddy_free_list_internal(mm, &allocated);
}
return err;
}
static int __drm_buddy_alloc_range(struct drm_buddy *mm,
u64 start,
u64 size,
u64 *total_allocated_on_err,
struct list_head *blocks)
{
LIST_HEAD(dfs);
int i;
for (i = 0; i < mm->n_roots; ++i)
list_add_tail(&mm->roots[i]->tmp_link, &dfs);
return __alloc_range(mm, &dfs, start, size,
blocks, total_allocated_on_err);
}
static int __alloc_contig_try_harder(struct drm_buddy *mm,
u64 size,
u64 min_block_size,
struct list_head *blocks)
{
u64 rhs_offset, lhs_offset, lhs_size, filled;
struct drm_buddy_block *block;
struct list_head *list;
LIST_HEAD(blocks_lhs);
unsigned long pages;
unsigned int order;
u64 modify_size;
int err;
modify_size = rounddown_pow_of_two(size);
pages = modify_size >> ilog2(mm->chunk_size);
order = fls(pages) - 1;
if (order == 0)
return -ENOSPC;
list = &mm->free_list[order];
if (list_empty(list))
return -ENOSPC;
list_for_each_entry_reverse(block, list, link) {
/* Allocate blocks traversing RHS */
rhs_offset = drm_buddy_block_offset(block);
err = __drm_buddy_alloc_range(mm, rhs_offset, size,
&filled, blocks);
if (!err || err != -ENOSPC)
return err;
lhs_size = max((size - filled), min_block_size);
if (!IS_ALIGNED(lhs_size, min_block_size))
lhs_size = round_up(lhs_size, min_block_size);
/* Allocate blocks traversing LHS */
lhs_offset = drm_buddy_block_offset(block) - lhs_size;
err = __drm_buddy_alloc_range(mm, lhs_offset, lhs_size,
NULL, &blocks_lhs);
if (!err) {
list_splice(&blocks_lhs, blocks);
return 0;
} else if (err != -ENOSPC) {
drm_buddy_free_list_internal(mm, blocks);
return err;
}
/* Free blocks for the next iteration */
drm_buddy_free_list_internal(mm, blocks);
}
return -ENOSPC;
}
/**
* drm_buddy_block_trim - free unused pages
*
* @mm: DRM buddy manager
* @start: start address to begin the trimming.
* @new_size: original size requested
* @blocks: Input and output list of allocated blocks.
* MUST contain single block as input to be trimmed.
* On success will contain the newly allocated blocks
* making up the @new_size. Blocks always appear in
* ascending order
*
* For contiguous allocation, we round up the size to the nearest
* power of two value, drivers consume *actual* size, so remaining
* portions are unused and can be optionally freed with this function
*
* Returns:
* 0 on success, error code on failure.
*/
int drm_buddy_block_trim(struct drm_buddy *mm,
u64 *start,
u64 new_size,
struct list_head *blocks)
{
struct drm_buddy_block *parent;
struct drm_buddy_block *block;
u64 block_start, block_end;
LIST_HEAD(dfs);
u64 new_start;
int err;
if (!list_is_singular(blocks))
return -EINVAL;
block = list_first_entry(blocks,
struct drm_buddy_block,
link);
block_start = drm_buddy_block_offset(block);
block_end = block_start + drm_buddy_block_size(mm, block);
if (WARN_ON(!drm_buddy_block_is_allocated(block)))
return -EINVAL;
if (new_size > drm_buddy_block_size(mm, block))
return -EINVAL;
if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size))
return -EINVAL;
if (new_size == drm_buddy_block_size(mm, block))
return 0;
new_start = block_start;
if (start) {
new_start = *start;
if (new_start < block_start)
return -EINVAL;
if (!IS_ALIGNED(new_start, mm->chunk_size))
return -EINVAL;
if (range_overflows(new_start, new_size, block_end))
return -EINVAL;
}
list_del(&block->link);
mark_free(mm, block);
mm->avail += drm_buddy_block_size(mm, block);
if (drm_buddy_block_is_clear(block))
mm->clear_avail += drm_buddy_block_size(mm, block);
/* Prevent recursively freeing this node */
parent = block->parent;
block->parent = NULL;
list_add(&block->tmp_link, &dfs);
err = __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL);
if (err) {
mark_allocated(block);
mm->avail -= drm_buddy_block_size(mm, block);
if (drm_buddy_block_is_clear(block))
mm->clear_avail -= drm_buddy_block_size(mm, block);
list_add(&block->link, blocks);
}
block->parent = parent;
return err;
}
EXPORT_SYMBOL(drm_buddy_block_trim);
static struct drm_buddy_block *
__drm_buddy_alloc_blocks(struct drm_buddy *mm,
u64 start, u64 end,
unsigned int order,
unsigned long flags)
{
if (flags & DRM_BUDDY_RANGE_ALLOCATION)
/* Allocate traversing within the range */
return __drm_buddy_alloc_range_bias(mm, start, end,
order, flags);
else
/* Allocate from freelist */
return alloc_from_freelist(mm, order, flags);
}
/**
* drm_buddy_alloc_blocks - allocate power-of-two blocks
*
* @mm: DRM buddy manager to allocate from
* @start: start of the allowed range for this block
* @end: end of the allowed range for this block
* @size: size of the allocation in bytes
* @min_block_size: alignment of the allocation
* @blocks: output list head to add allocated blocks
* @flags: DRM_BUDDY_*_ALLOCATION flags
*
* alloc_range_bias() called on range limitations, which traverses
* the tree and returns the desired block.
*
* alloc_from_freelist() called when *no* range restrictions
* are enforced, which picks the block from the freelist.
*
* Returns:
* 0 on success, error code on failure.
*/
int drm_buddy_alloc_blocks(struct drm_buddy *mm,
u64 start, u64 end, u64 size,
u64 min_block_size,
struct list_head *blocks,
unsigned long flags)
{
struct drm_buddy_block *block = NULL;
u64 original_size, original_min_size;
unsigned int min_order, order;
LIST_HEAD(allocated);
unsigned long pages;
int err;
if (size < mm->chunk_size)
return -EINVAL;
if (min_block_size < mm->chunk_size)
return -EINVAL;
if (!is_power_of_2(min_block_size))
return -EINVAL;
if (!IS_ALIGNED(start | end | size, mm->chunk_size))
return -EINVAL;
if (end > mm->size)
return -EINVAL;
if (range_overflows(start, size, mm->size))
return -EINVAL;
/* Actual range allocation */
if (start + size == end) {
if (!IS_ALIGNED(start | end, min_block_size))
return -EINVAL;
return __drm_buddy_alloc_range(mm, start, size, NULL, blocks);
}
original_size = size;
original_min_size = min_block_size;
/* Roundup the size to power of 2 */
if (flags & DRM_BUDDY_CONTIGUOUS_ALLOCATION) {
size = roundup_pow_of_two(size);
min_block_size = size;
/* Align size value to min_block_size */
} else if (!IS_ALIGNED(size, min_block_size)) {
size = round_up(size, min_block_size);
}
pages = size >> ilog2(mm->chunk_size);
order = fls(pages) - 1;
min_order = ilog2(min_block_size) - ilog2(mm->chunk_size);
do {
order = min(order, (unsigned int)fls(pages) - 1);
BUG_ON(order > mm->max_order);
BUG_ON(order < min_order);
do {
block = __drm_buddy_alloc_blocks(mm, start,
end,
order,
flags);
if (!IS_ERR(block))
break;
if (order-- == min_order) {
/* Try allocation through force merge method */
if (mm->clear_avail &&
!__force_merge(mm, start, end, min_order)) {
block = __drm_buddy_alloc_blocks(mm, start,
end,
min_order,
flags);
if (!IS_ERR(block)) {
order = min_order;
break;
}
}
/*
* Try contiguous block allocation through
* try harder method.
*/
if (flags & DRM_BUDDY_CONTIGUOUS_ALLOCATION &&
!(flags & DRM_BUDDY_RANGE_ALLOCATION))
return __alloc_contig_try_harder(mm,
original_size,
original_min_size,
blocks);
err = -ENOSPC;
goto err_free;
}
} while (1);
mark_allocated(block);
mm->avail -= drm_buddy_block_size(mm, block);
if (drm_buddy_block_is_clear(block))
mm->clear_avail -= drm_buddy_block_size(mm, block);
kmemleak_update_trace(block);
list_add_tail(&block->link, &allocated);
pages -= BIT(order);
if (!pages)
break;
} while (1);
/* Trim the allocated block to the required size */
if (!(flags & DRM_BUDDY_TRIM_DISABLE) &&
original_size != size) {
struct list_head *trim_list;
LIST_HEAD(temp);
u64 trim_size;
trim_list = &allocated;
trim_size = original_size;
if (!list_is_singular(&allocated)) {
block = list_last_entry(&allocated, typeof(*block), link);
list_move(&block->link, &temp);
trim_list = &temp;
trim_size = drm_buddy_block_size(mm, block) -
(size - original_size);
}
drm_buddy_block_trim(mm,
NULL,
trim_size,
trim_list);
if (!list_empty(&temp))
list_splice_tail(trim_list, &allocated);
}
list_splice_tail(&allocated, blocks);
return 0;
err_free:
drm_buddy_free_list_internal(mm, &allocated);
return err;
}
EXPORT_SYMBOL(drm_buddy_alloc_blocks);
/**
* drm_buddy_block_print - print block information
*
* @mm: DRM buddy manager
* @block: DRM buddy block
* @p: DRM printer to use
*/
void drm_buddy_block_print(struct drm_buddy *mm,
struct drm_buddy_block *block,
struct drm_printer *p)
{
u64 start = drm_buddy_block_offset(block);
u64 size = drm_buddy_block_size(mm, block);
drm_printf(p, "%#018llx-%#018llx: %llu\n", start, start + size, size);
}
EXPORT_SYMBOL(drm_buddy_block_print);
/**
* drm_buddy_print - print allocator state
*
* @mm: DRM buddy manager
* @p: DRM printer to use
*/
void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p)
{
int order;
drm_printf(p, "chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB, clear_free: %lluMiB\n",
mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20, mm->clear_avail >> 20);
for (order = mm->max_order; order >= 0; order--) {
struct drm_buddy_block *block;
u64 count = 0, free;
list_for_each_entry(block, &mm->free_list[order], link) {
BUG_ON(!drm_buddy_block_is_free(block));
count++;
}
drm_printf(p, "order-%2d ", order);
free = count * (mm->chunk_size << order);
if (free < SZ_1M)
drm_printf(p, "free: %8llu KiB", free >> 10);
else
drm_printf(p, "free: %8llu MiB", free >> 20);
drm_printf(p, ", blocks: %llu\n", count);
}
}
EXPORT_SYMBOL(drm_buddy_print);
static void drm_buddy_module_exit(void)
{
kmem_cache_destroy(slab_blocks);
}
static int __init drm_buddy_module_init(void)
{
slab_blocks = KMEM_CACHE(drm_buddy_block, 0);
if (!slab_blocks)
return -ENOMEM;
return 0;
}
module_init(drm_buddy_module_init);
module_exit(drm_buddy_module_exit);
MODULE_DESCRIPTION("DRM Buddy Allocator");
MODULE_LICENSE("Dual MIT/GPL");