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