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