1 /* SPDX-License-Identifier: MIT */
2 /*
3 * Copyright © 2021 Intel Corporation
4 */
5
6 #ifndef __I915_BUDDY_H__
7 #define __I915_BUDDY_H__
8
9 #include <linux/bitops.h>
10 #include <linux/list.h>
11 #include <linux/slab.h>
12
13 #include <drm/drm_print.h>
14
15 struct i915_buddy_block {
16 #define I915_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12)
17 #define I915_BUDDY_HEADER_STATE GENMASK_ULL(11, 10)
18 #define I915_BUDDY_ALLOCATED (1 << 10)
19 #define I915_BUDDY_FREE (2 << 10)
20 #define I915_BUDDY_SPLIT (3 << 10)
21 /* Free to be used, if needed in the future */
22 #define I915_BUDDY_HEADER_UNUSED GENMASK_ULL(9, 6)
23 #define I915_BUDDY_HEADER_ORDER GENMASK_ULL(5, 0)
24 u64 header;
25
26 struct i915_buddy_block *left;
27 struct i915_buddy_block *right;
28 struct i915_buddy_block *parent;
29
30 void *private; /* owned by creator */
31
32 /*
33 * While the block is allocated by the user through i915_buddy_alloc*,
34 * the user has ownership of the link, for example to maintain within
35 * a list, if so desired. As soon as the block is freed with
36 * i915_buddy_free* ownership is given back to the mm.
37 */
38 struct list_head link;
39 struct list_head tmp_link;
40 };
41
42 /* Order-zero must be at least PAGE_SIZE */
43 #define I915_BUDDY_MAX_ORDER (63 - PAGE_SHIFT)
44
45 /*
46 * Binary Buddy System.
47 *
48 * Locking should be handled by the user, a simple mutex around
49 * i915_buddy_alloc* and i915_buddy_free* should suffice.
50 */
51 struct i915_buddy_mm {
52 /* Maintain a free list for each order. */
53 struct list_head *free_list;
54
55 /*
56 * Maintain explicit binary tree(s) to track the allocation of the
57 * address space. This gives us a simple way of finding a buddy block
58 * and performing the potentially recursive merge step when freeing a
59 * block. Nodes are either allocated or free, in which case they will
60 * also exist on the respective free list.
61 */
62 struct i915_buddy_block **roots;
63
64 /*
65 * Anything from here is public, and remains static for the lifetime of
66 * the mm. Everything above is considered do-not-touch.
67 */
68 unsigned int n_roots;
69 unsigned int max_order;
70
71 /* Must be at least PAGE_SIZE */
72 u64 chunk_size;
73 u64 size;
74 u64 avail;
75 };
76
77 static inline u64
i915_buddy_block_offset(struct i915_buddy_block * block)78 i915_buddy_block_offset(struct i915_buddy_block *block)
79 {
80 return block->header & I915_BUDDY_HEADER_OFFSET;
81 }
82
83 static inline unsigned int
i915_buddy_block_order(struct i915_buddy_block * block)84 i915_buddy_block_order(struct i915_buddy_block *block)
85 {
86 return block->header & I915_BUDDY_HEADER_ORDER;
87 }
88
89 static inline unsigned int
i915_buddy_block_state(struct i915_buddy_block * block)90 i915_buddy_block_state(struct i915_buddy_block *block)
91 {
92 return block->header & I915_BUDDY_HEADER_STATE;
93 }
94
95 static inline bool
i915_buddy_block_is_allocated(struct i915_buddy_block * block)96 i915_buddy_block_is_allocated(struct i915_buddy_block *block)
97 {
98 return i915_buddy_block_state(block) == I915_BUDDY_ALLOCATED;
99 }
100
101 static inline bool
i915_buddy_block_is_free(struct i915_buddy_block * block)102 i915_buddy_block_is_free(struct i915_buddy_block *block)
103 {
104 return i915_buddy_block_state(block) == I915_BUDDY_FREE;
105 }
106
107 static inline bool
i915_buddy_block_is_split(struct i915_buddy_block * block)108 i915_buddy_block_is_split(struct i915_buddy_block *block)
109 {
110 return i915_buddy_block_state(block) == I915_BUDDY_SPLIT;
111 }
112
113 static inline u64
i915_buddy_block_size(struct i915_buddy_mm * mm,struct i915_buddy_block * block)114 i915_buddy_block_size(struct i915_buddy_mm *mm,
115 struct i915_buddy_block *block)
116 {
117 return mm->chunk_size << i915_buddy_block_order(block);
118 }
119
120 int i915_buddy_init(struct i915_buddy_mm *mm, u64 size, u64 chunk_size);
121
122 void i915_buddy_fini(struct i915_buddy_mm *mm);
123
124 struct i915_buddy_block *
125 i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order);
126
127 int i915_buddy_alloc_range(struct i915_buddy_mm *mm,
128 struct list_head *blocks,
129 u64 start, u64 size);
130
131 void i915_buddy_free(struct i915_buddy_mm *mm, struct i915_buddy_block *block);
132
133 void i915_buddy_free_list(struct i915_buddy_mm *mm, struct list_head *objects);
134
135 void i915_buddy_print(struct i915_buddy_mm *mm, struct drm_printer *p);
136 void i915_buddy_block_print(struct i915_buddy_mm *mm,
137 struct i915_buddy_block *block,
138 struct drm_printer *p);
139
140 void i915_buddy_module_exit(void);
141 int i915_buddy_module_init(void);
142
143 #endif
144