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