174 lines · c
1/* SPDX-License-Identifier: MIT */2/*3 * Copyright © 2021 Intel Corporation4 */5 6#ifndef __DRM_BUDDY_H__7#define __DRM_BUDDY_H__8 9#include <linux/bitops.h>10#include <linux/list.h>11#include <linux/slab.h>12#include <linux/sched.h>13 14#include <drm/drm_print.h>15 16#define range_overflows(start, size, max) ({ \17 typeof(start) start__ = (start); \18 typeof(size) size__ = (size); \19 typeof(max) max__ = (max); \20 (void)(&start__ == &size__); \21 (void)(&start__ == &max__); \22 start__ >= max__ || size__ > max__ - start__; \23})24 25#define DRM_BUDDY_RANGE_ALLOCATION BIT(0)26#define DRM_BUDDY_TOPDOWN_ALLOCATION BIT(1)27#define DRM_BUDDY_CONTIGUOUS_ALLOCATION BIT(2)28#define DRM_BUDDY_CLEAR_ALLOCATION BIT(3)29#define DRM_BUDDY_CLEARED BIT(4)30#define DRM_BUDDY_TRIM_DISABLE BIT(5)31 32struct drm_buddy_block {33#define DRM_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12)34#define DRM_BUDDY_HEADER_STATE GENMASK_ULL(11, 10)35#define DRM_BUDDY_ALLOCATED (1 << 10)36#define DRM_BUDDY_FREE (2 << 10)37#define DRM_BUDDY_SPLIT (3 << 10)38#define DRM_BUDDY_HEADER_CLEAR GENMASK_ULL(9, 9)39/* Free to be used, if needed in the future */40#define DRM_BUDDY_HEADER_UNUSED GENMASK_ULL(8, 6)41#define DRM_BUDDY_HEADER_ORDER GENMASK_ULL(5, 0)42 u64 header;43 44 struct drm_buddy_block *left;45 struct drm_buddy_block *right;46 struct drm_buddy_block *parent;47 48 void *private; /* owned by creator */49 50 /*51 * While the block is allocated by the user through drm_buddy_alloc*,52 * the user has ownership of the link, for example to maintain within53 * a list, if so desired. As soon as the block is freed with54 * drm_buddy_free* ownership is given back to the mm.55 */56 struct list_head link;57 struct list_head tmp_link;58};59 60/* Order-zero must be at least SZ_4K */61#define DRM_BUDDY_MAX_ORDER (63 - 12)62 63/*64 * Binary Buddy System.65 *66 * Locking should be handled by the user, a simple mutex around67 * drm_buddy_alloc* and drm_buddy_free* should suffice.68 */69struct drm_buddy {70 /* Maintain a free list for each order. */71 struct list_head *free_list;72 73 /*74 * Maintain explicit binary tree(s) to track the allocation of the75 * address space. This gives us a simple way of finding a buddy block76 * and performing the potentially recursive merge step when freeing a77 * block. Nodes are either allocated or free, in which case they will78 * also exist on the respective free list.79 */80 struct drm_buddy_block **roots;81 82 /*83 * Anything from here is public, and remains static for the lifetime of84 * the mm. Everything above is considered do-not-touch.85 */86 unsigned int n_roots;87 unsigned int max_order;88 89 /* Must be at least SZ_4K */90 u64 chunk_size;91 u64 size;92 u64 avail;93 u64 clear_avail;94};95 96static inline u6497drm_buddy_block_offset(struct drm_buddy_block *block)98{99 return block->header & DRM_BUDDY_HEADER_OFFSET;100}101 102static inline unsigned int103drm_buddy_block_order(struct drm_buddy_block *block)104{105 return block->header & DRM_BUDDY_HEADER_ORDER;106}107 108static inline unsigned int109drm_buddy_block_state(struct drm_buddy_block *block)110{111 return block->header & DRM_BUDDY_HEADER_STATE;112}113 114static inline bool115drm_buddy_block_is_allocated(struct drm_buddy_block *block)116{117 return drm_buddy_block_state(block) == DRM_BUDDY_ALLOCATED;118}119 120static inline bool121drm_buddy_block_is_clear(struct drm_buddy_block *block)122{123 return block->header & DRM_BUDDY_HEADER_CLEAR;124}125 126static inline bool127drm_buddy_block_is_free(struct drm_buddy_block *block)128{129 return drm_buddy_block_state(block) == DRM_BUDDY_FREE;130}131 132static inline bool133drm_buddy_block_is_split(struct drm_buddy_block *block)134{135 return drm_buddy_block_state(block) == DRM_BUDDY_SPLIT;136}137 138static inline u64139drm_buddy_block_size(struct drm_buddy *mm,140 struct drm_buddy_block *block)141{142 return mm->chunk_size << drm_buddy_block_order(block);143}144 145int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size);146 147void drm_buddy_fini(struct drm_buddy *mm);148 149struct drm_buddy_block *150drm_get_buddy(struct drm_buddy_block *block);151 152int drm_buddy_alloc_blocks(struct drm_buddy *mm,153 u64 start, u64 end, u64 size,154 u64 min_page_size,155 struct list_head *blocks,156 unsigned long flags);157 158int drm_buddy_block_trim(struct drm_buddy *mm,159 u64 *start,160 u64 new_size,161 struct list_head *blocks);162 163void drm_buddy_free_block(struct drm_buddy *mm, struct drm_buddy_block *block);164 165void drm_buddy_free_list(struct drm_buddy *mm,166 struct list_head *objects,167 unsigned int flags);168 169void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p);170void drm_buddy_block_print(struct drm_buddy *mm,171 struct drm_buddy_block *block,172 struct drm_printer *p);173#endif174