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