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
drm_buddy_block_offset(struct drm_buddy_block * block)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
drm_buddy_block_order(struct drm_buddy_block * block)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
drm_buddy_block_state(struct drm_buddy_block * block)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
drm_buddy_block_is_allocated(struct drm_buddy_block * block)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
drm_buddy_block_is_free(struct drm_buddy_block * block)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
drm_buddy_block_is_split(struct drm_buddy_block * block)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
drm_buddy_block_size(struct drm_buddy * mm,struct drm_buddy_block * block)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