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 struct drm_buddy_block { 26 #define DRM_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12) 27 #define DRM_BUDDY_HEADER_STATE GENMASK_ULL(11, 10) 28 #define DRM_BUDDY_ALLOCATED (1 << 10) 29 #define DRM_BUDDY_FREE (2 << 10) 30 #define DRM_BUDDY_SPLIT (3 << 10) 31 /* Free to be used, if needed in the future */ 32 #define DRM_BUDDY_HEADER_UNUSED GENMASK_ULL(9, 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 struct list_head link; 49 struct list_head tmp_link; 50 }; 51 52 /* Order-zero must be at least PAGE_SIZE */ 53 #define DRM_BUDDY_MAX_ORDER (63 - PAGE_SHIFT) 54 55 /* 56 * Binary Buddy System. 57 * 58 * Locking should be handled by the user, a simple mutex around 59 * drm_buddy_alloc* and drm_buddy_free* should suffice. 60 */ 61 struct drm_buddy { 62 /* Maintain a free list for each order. */ 63 struct list_head *free_list; 64 65 /* 66 * Maintain explicit binary tree(s) to track the allocation of the 67 * address space. This gives us a simple way of finding a buddy block 68 * and performing the potentially recursive merge step when freeing a 69 * block. Nodes are either allocated or free, in which case they will 70 * also exist on the respective free list. 71 */ 72 struct drm_buddy_block **roots; 73 74 /* 75 * Anything from here is public, and remains static for the lifetime of 76 * the mm. Everything above is considered do-not-touch. 77 */ 78 unsigned int n_roots; 79 unsigned int max_order; 80 81 /* Must be at least PAGE_SIZE */ 82 u64 chunk_size; 83 u64 size; 84 u64 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_free(struct drm_buddy_block *block) 113 { 114 return drm_buddy_block_state(block) == DRM_BUDDY_FREE; 115 } 116 117 static inline bool 118 drm_buddy_block_is_split(struct drm_buddy_block *block) 119 { 120 return drm_buddy_block_state(block) == DRM_BUDDY_SPLIT; 121 } 122 123 static inline u64 124 drm_buddy_block_size(struct drm_buddy *mm, 125 struct drm_buddy_block *block) 126 { 127 return mm->chunk_size << drm_buddy_block_order(block); 128 } 129 130 int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size); 131 132 void drm_buddy_fini(struct drm_buddy *mm); 133 134 struct drm_buddy_block * 135 drm_buddy_alloc_blocks(struct drm_buddy *mm, unsigned int order); 136 137 int drm_buddy_alloc_range(struct drm_buddy *mm, 138 struct list_head *blocks, 139 u64 start, u64 size); 140 141 void drm_buddy_free_block(struct drm_buddy *mm, struct drm_buddy_block *block); 142 143 void drm_buddy_free_list(struct drm_buddy *mm, struct list_head *objects); 144 145 void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p); 146 void drm_buddy_block_print(struct drm_buddy *mm, 147 struct drm_buddy_block *block, 148 struct drm_printer *p); 149 150 #endif 151