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