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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
/* SPDX-License-Identifier: MIT */
/*
* Copyright © 2021 Intel Corporation
*/
#ifndef __DRM_BUDDY_H__
#define __DRM_BUDDY_H__
#include <linux/bitops.h>
#include <linux/list.h>
#include <linux/slab.h>
#include <linux/sched.h>
#include <drm/drm_print.h>
#define range_overflows(start, size, max) ({ \
typeof(start) start__ = (start); \
typeof(size) size__ = (size); \
typeof(max) max__ = (max); \
(void)(&start__ == &size__); \
(void)(&start__ == &max__); \
start__ >= max__ || size__ > max__ - start__; \
})
#define DRM_BUDDY_RANGE_ALLOCATION BIT(0)
#define DRM_BUDDY_TOPDOWN_ALLOCATION BIT(1)
#define DRM_BUDDY_CONTIGUOUS_ALLOCATION BIT(2)
#define DRM_BUDDY_CLEAR_ALLOCATION BIT(3)
#define DRM_BUDDY_CLEARED BIT(4)
struct drm_buddy_block {
#define DRM_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12)
#define DRM_BUDDY_HEADER_STATE GENMASK_ULL(11, 10)
#define DRM_BUDDY_ALLOCATED (1 << 10)
#define DRM_BUDDY_FREE (2 << 10)
#define DRM_BUDDY_SPLIT (3 << 10)
#define DRM_BUDDY_HEADER_CLEAR GENMASK_ULL(9, 9)
/* Free to be used, if needed in the future */
#define DRM_BUDDY_HEADER_UNUSED GENMASK_ULL(8, 6)
#define DRM_BUDDY_HEADER_ORDER GENMASK_ULL(5, 0)
u64 header;
struct drm_buddy_block *left;
struct drm_buddy_block *right;
struct drm_buddy_block *parent;
void *private; /* owned by creator */
/*
* While the block is allocated by the user through drm_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
* drm_buddy_free* ownership is given back to the mm.
*/
struct list_head link;
struct list_head tmp_link;
};
/* Order-zero must be at least SZ_4K */
#define DRM_BUDDY_MAX_ORDER (63 - 12)
/*
* Binary Buddy System.
*
* Locking should be handled by the user, a simple mutex around
* drm_buddy_alloc* and drm_buddy_free* should suffice.
*/
struct drm_buddy {
/* 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 drm_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 SZ_4K */
u64 chunk_size;
u64 size;
u64 avail;
u64 clear_avail;
};
static inline u64
drm_buddy_block_offset(struct drm_buddy_block *block)
{
return block->header & DRM_BUDDY_HEADER_OFFSET;
}
static inline unsigned int
drm_buddy_block_order(struct drm_buddy_block *block)
{
return block->header & DRM_BUDDY_HEADER_ORDER;
}
static inline unsigned int
drm_buddy_block_state(struct drm_buddy_block *block)
{
return block->header & DRM_BUDDY_HEADER_STATE;
}
static inline bool
drm_buddy_block_is_allocated(struct drm_buddy_block *block)
{
return drm_buddy_block_state(block) == DRM_BUDDY_ALLOCATED;
}
static inline bool
drm_buddy_block_is_clear(struct drm_buddy_block *block)
{
return block->header & DRM_BUDDY_HEADER_CLEAR;
}
static inline bool
drm_buddy_block_is_free(struct drm_buddy_block *block)
{
return drm_buddy_block_state(block) == DRM_BUDDY_FREE;
}
static inline bool
drm_buddy_block_is_split(struct drm_buddy_block *block)
{
return drm_buddy_block_state(block) == DRM_BUDDY_SPLIT;
}
static inline u64
drm_buddy_block_size(struct drm_buddy *mm,
struct drm_buddy_block *block)
{
return mm->chunk_size << drm_buddy_block_order(block);
}
int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size);
void drm_buddy_fini(struct drm_buddy *mm);
struct drm_buddy_block *
drm_get_buddy(struct drm_buddy_block *block);
int drm_buddy_alloc_blocks(struct drm_buddy *mm,
u64 start, u64 end, u64 size,
u64 min_page_size,
struct list_head *blocks,
unsigned long flags);
int drm_buddy_block_trim(struct drm_buddy *mm,
u64 new_size,
struct list_head *blocks);
void drm_buddy_free_block(struct drm_buddy *mm, struct drm_buddy_block *block);
void drm_buddy_free_list(struct drm_buddy *mm,
struct list_head *objects,
unsigned int flags);
void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p);
void drm_buddy_block_print(struct drm_buddy *mm,
struct drm_buddy_block *block,
struct drm_printer *p);
#endif
|
