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 29struct drm_buddy_block { 30#define DRM_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12) 31#define DRM_BUDDY_HEADER_STATE GENMASK_ULL(11, 10) 32#define DRM_BUDDY_ALLOCATED (1 << 10) 33#define DRM_BUDDY_FREE (2 << 10) 34#define DRM_BUDDY_SPLIT (3 << 10) 35/* Free to be used, if needed in the future */ 36#define DRM_BUDDY_HEADER_UNUSED GENMASK_ULL(9, 6) 37#define DRM_BUDDY_HEADER_ORDER GENMASK_ULL(5, 0) 38 u64 header; 39 40 struct drm_buddy_block *left; 41 struct drm_buddy_block *right; 42 struct drm_buddy_block *parent; 43 44 void *private; /* owned by creator */ 45 46 /* 47 * While the block is allocated by the user through drm_buddy_alloc*, 48 * the user has ownership of the link, for example to maintain within 49 * a list, if so desired. As soon as the block is freed with 50 * drm_buddy_free* ownership is given back to the mm. 51 */ 52 struct list_head link; 53 struct list_head tmp_link; 54}; 55 56/* Order-zero must be at least PAGE_SIZE */ 57#define DRM_BUDDY_MAX_ORDER (63 - PAGE_SHIFT) 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 */ 65struct drm_buddy { 66 /* Maintain a free list for each order. */ 67 struct list_head *free_list; 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 PAGE_SIZE */ 86 u64 chunk_size; 87 u64 size; 88 u64 avail; 89}; 90 91static inline u64 92drm_buddy_block_offset(struct drm_buddy_block *block) 93{ 94 return block->header & DRM_BUDDY_HEADER_OFFSET; 95} 96 97static inline unsigned int 98drm_buddy_block_order(struct drm_buddy_block *block) 99{ 100 return block->header & DRM_BUDDY_HEADER_ORDER; 101} 102 103static inline unsigned int 104drm_buddy_block_state(struct drm_buddy_block *block) 105{ 106 return block->header & DRM_BUDDY_HEADER_STATE; 107} 108 109static inline bool 110drm_buddy_block_is_allocated(struct drm_buddy_block *block) 111{ 112 return drm_buddy_block_state(block) == DRM_BUDDY_ALLOCATED; 113} 114 115static inline bool 116drm_buddy_block_is_free(struct drm_buddy_block *block) 117{ 118 return drm_buddy_block_state(block) == DRM_BUDDY_FREE; 119} 120 121static inline bool 122drm_buddy_block_is_split(struct drm_buddy_block *block) 123{ 124 return drm_buddy_block_state(block) == DRM_BUDDY_SPLIT; 125} 126 127static inline u64 128drm_buddy_block_size(struct drm_buddy *mm, 129 struct drm_buddy_block *block) 130{ 131 return mm->chunk_size << drm_buddy_block_order(block); 132} 133 134int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size); 135 136void drm_buddy_fini(struct drm_buddy *mm); 137 138struct drm_buddy_block * 139drm_get_buddy(struct drm_buddy_block *block); 140 141int drm_buddy_alloc_blocks(struct drm_buddy *mm, 142 u64 start, u64 end, u64 size, 143 u64 min_page_size, 144 struct list_head *blocks, 145 unsigned long flags); 146 147int drm_buddy_block_trim(struct drm_buddy *mm, 148 u64 new_size, 149 struct list_head *blocks); 150 151void drm_buddy_free_block(struct drm_buddy *mm, struct drm_buddy_block *block); 152 153void drm_buddy_free_list(struct drm_buddy *mm, struct list_head *objects); 154 155void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p); 156void drm_buddy_block_print(struct drm_buddy *mm, 157 struct drm_buddy_block *block, 158 struct drm_printer *p); 159#endif 160