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