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