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 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 32 struct 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 within 53 * a list, if so desired. As soon as the block is freed with 54 * 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 around 67 * drm_buddy_alloc* and drm_buddy_free* should suffice. 68 */ 69 struct 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 the 75 * address space. This gives us a simple way of finding a buddy block 76 * and performing the potentially recursive merge step when freeing a 77 * block. Nodes are either allocated or free, in which case they will 78 * 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 of 84 * 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 96 static inline u64 97 drm_buddy_block_offset(struct drm_buddy_block *block) 98 { 99 return block->header & DRM_BUDDY_HEADER_OFFSET; 100 } 101 102 static inline unsigned int 103 drm_buddy_block_order(struct drm_buddy_block *block) 104 { 105 return block->header & DRM_BUDDY_HEADER_ORDER; 106 } 107 108 static inline unsigned int 109 drm_buddy_block_state(struct drm_buddy_block *block) 110 { 111 return block->header & DRM_BUDDY_HEADER_STATE; 112 } 113 114 static inline bool 115 drm_buddy_block_is_allocated(struct drm_buddy_block *block) 116 { 117 return drm_buddy_block_state(block) == DRM_BUDDY_ALLOCATED; 118 } 119 120 static inline bool 121 drm_buddy_block_is_clear(struct drm_buddy_block *block) 122 { 123 return block->header & DRM_BUDDY_HEADER_CLEAR; 124 } 125 126 static inline bool 127 drm_buddy_block_is_free(struct drm_buddy_block *block) 128 { 129 return drm_buddy_block_state(block) == DRM_BUDDY_FREE; 130 } 131 132 static inline bool 133 drm_buddy_block_is_split(struct drm_buddy_block *block) 134 { 135 return drm_buddy_block_state(block) == DRM_BUDDY_SPLIT; 136 } 137 138 static inline u64 139 drm_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 145 int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size); 146 147 void drm_buddy_fini(struct drm_buddy *mm); 148 149 struct drm_buddy_block * 150 drm_get_buddy(struct drm_buddy_block *block); 151 152 int 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 158 int drm_buddy_block_trim(struct drm_buddy *mm, 159 u64 *start, 160 u64 new_size, 161 struct list_head *blocks); 162 163 void drm_buddy_free_block(struct drm_buddy *mm, struct drm_buddy_block *block); 164 165 void drm_buddy_free_list(struct drm_buddy *mm, 166 struct list_head *objects, 167 unsigned int flags); 168 169 void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p); 170 void drm_buddy_block_print(struct drm_buddy *mm, 171 struct drm_buddy_block *block, 172 struct drm_printer *p); 173 #endif 174