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