Loading...
1// SPDX-License-Identifier: MIT
2/*
3 * Copyright © 2019 Intel Corporation
4 */
5
6#include <linux/kmemleak.h>
7#include <linux/slab.h>
8
9#include "i915_buddy.h"
10
11#include "i915_gem.h"
12#include "i915_globals.h"
13#include "i915_utils.h"
14
15static struct i915_global_block {
16 struct i915_global base;
17 struct kmem_cache *slab_blocks;
18} global;
19
20static void i915_global_buddy_shrink(void)
21{
22 kmem_cache_shrink(global.slab_blocks);
23}
24
25static void i915_global_buddy_exit(void)
26{
27 kmem_cache_destroy(global.slab_blocks);
28}
29
30static struct i915_global_block global = { {
31 .shrink = i915_global_buddy_shrink,
32 .exit = i915_global_buddy_exit,
33} };
34
35int __init i915_global_buddy_init(void)
36{
37 global.slab_blocks = KMEM_CACHE(i915_buddy_block, SLAB_HWCACHE_ALIGN);
38 if (!global.slab_blocks)
39 return -ENOMEM;
40
41 return 0;
42}
43
44static struct i915_buddy_block *i915_block_alloc(struct i915_buddy_block *parent,
45 unsigned int order,
46 u64 offset)
47{
48 struct i915_buddy_block *block;
49
50 block = kmem_cache_zalloc(global.slab_blocks, GFP_KERNEL);
51 if (!block)
52 return NULL;
53
54 block->header = offset;
55 block->header |= order;
56 block->parent = parent;
57
58 return block;
59}
60
61static void i915_block_free(struct i915_buddy_block *block)
62{
63 kmem_cache_free(global.slab_blocks, block);
64}
65
66static void mark_allocated(struct i915_buddy_block *block)
67{
68 block->header &= ~I915_BUDDY_HEADER_STATE;
69 block->header |= I915_BUDDY_ALLOCATED;
70
71 list_del(&block->link);
72}
73
74static void mark_free(struct i915_buddy_mm *mm,
75 struct i915_buddy_block *block)
76{
77 block->header &= ~I915_BUDDY_HEADER_STATE;
78 block->header |= I915_BUDDY_FREE;
79
80 list_add(&block->link,
81 &mm->free_list[i915_buddy_block_order(block)]);
82}
83
84static void mark_split(struct i915_buddy_block *block)
85{
86 block->header &= ~I915_BUDDY_HEADER_STATE;
87 block->header |= I915_BUDDY_SPLIT;
88
89 list_del(&block->link);
90}
91
92int i915_buddy_init(struct i915_buddy_mm *mm, u64 size, u64 chunk_size)
93{
94 unsigned int i;
95 u64 offset;
96
97 if (size < chunk_size)
98 return -EINVAL;
99
100 if (chunk_size < PAGE_SIZE)
101 return -EINVAL;
102
103 if (!is_power_of_2(chunk_size))
104 return -EINVAL;
105
106 size = round_down(size, chunk_size);
107
108 mm->size = size;
109 mm->chunk_size = chunk_size;
110 mm->max_order = ilog2(size) - ilog2(chunk_size);
111
112 GEM_BUG_ON(mm->max_order > I915_BUDDY_MAX_ORDER);
113
114 mm->free_list = kmalloc_array(mm->max_order + 1,
115 sizeof(struct list_head),
116 GFP_KERNEL);
117 if (!mm->free_list)
118 return -ENOMEM;
119
120 for (i = 0; i <= mm->max_order; ++i)
121 INIT_LIST_HEAD(&mm->free_list[i]);
122
123 mm->n_roots = hweight64(size);
124
125 mm->roots = kmalloc_array(mm->n_roots,
126 sizeof(struct i915_buddy_block *),
127 GFP_KERNEL);
128 if (!mm->roots)
129 goto out_free_list;
130
131 offset = 0;
132 i = 0;
133
134 /*
135 * Split into power-of-two blocks, in case we are given a size that is
136 * not itself a power-of-two.
137 */
138 do {
139 struct i915_buddy_block *root;
140 unsigned int order;
141 u64 root_size;
142
143 root_size = rounddown_pow_of_two(size);
144 order = ilog2(root_size) - ilog2(chunk_size);
145
146 root = i915_block_alloc(NULL, order, offset);
147 if (!root)
148 goto out_free_roots;
149
150 mark_free(mm, root);
151
152 GEM_BUG_ON(i > mm->max_order);
153 GEM_BUG_ON(i915_buddy_block_size(mm, root) < chunk_size);
154
155 mm->roots[i] = root;
156
157 offset += root_size;
158 size -= root_size;
159 i++;
160 } while (size);
161
162 return 0;
163
164out_free_roots:
165 while (i--)
166 i915_block_free(mm->roots[i]);
167 kfree(mm->roots);
168out_free_list:
169 kfree(mm->free_list);
170 return -ENOMEM;
171}
172
173void i915_buddy_fini(struct i915_buddy_mm *mm)
174{
175 int i;
176
177 for (i = 0; i < mm->n_roots; ++i) {
178 GEM_WARN_ON(!i915_buddy_block_is_free(mm->roots[i]));
179 i915_block_free(mm->roots[i]);
180 }
181
182 kfree(mm->roots);
183 kfree(mm->free_list);
184}
185
186static int split_block(struct i915_buddy_mm *mm,
187 struct i915_buddy_block *block)
188{
189 unsigned int block_order = i915_buddy_block_order(block) - 1;
190 u64 offset = i915_buddy_block_offset(block);
191
192 GEM_BUG_ON(!i915_buddy_block_is_free(block));
193 GEM_BUG_ON(!i915_buddy_block_order(block));
194
195 block->left = i915_block_alloc(block, block_order, offset);
196 if (!block->left)
197 return -ENOMEM;
198
199 block->right = i915_block_alloc(block, block_order,
200 offset + (mm->chunk_size << block_order));
201 if (!block->right) {
202 i915_block_free(block->left);
203 return -ENOMEM;
204 }
205
206 mark_free(mm, block->left);
207 mark_free(mm, block->right);
208
209 mark_split(block);
210
211 return 0;
212}
213
214static struct i915_buddy_block *
215get_buddy(struct i915_buddy_block *block)
216{
217 struct i915_buddy_block *parent;
218
219 parent = block->parent;
220 if (!parent)
221 return NULL;
222
223 if (parent->left == block)
224 return parent->right;
225
226 return parent->left;
227}
228
229static void __i915_buddy_free(struct i915_buddy_mm *mm,
230 struct i915_buddy_block *block)
231{
232 struct i915_buddy_block *parent;
233
234 while ((parent = block->parent)) {
235 struct i915_buddy_block *buddy;
236
237 buddy = get_buddy(block);
238
239 if (!i915_buddy_block_is_free(buddy))
240 break;
241
242 list_del(&buddy->link);
243
244 i915_block_free(block);
245 i915_block_free(buddy);
246
247 block = parent;
248 }
249
250 mark_free(mm, block);
251}
252
253void i915_buddy_free(struct i915_buddy_mm *mm,
254 struct i915_buddy_block *block)
255{
256 GEM_BUG_ON(!i915_buddy_block_is_allocated(block));
257 __i915_buddy_free(mm, block);
258}
259
260void i915_buddy_free_list(struct i915_buddy_mm *mm, struct list_head *objects)
261{
262 struct i915_buddy_block *block, *on;
263
264 list_for_each_entry_safe(block, on, objects, link)
265 i915_buddy_free(mm, block);
266 INIT_LIST_HEAD(objects);
267}
268
269/*
270 * Allocate power-of-two block. The order value here translates to:
271 *
272 * 0 = 2^0 * mm->chunk_size
273 * 1 = 2^1 * mm->chunk_size
274 * 2 = 2^2 * mm->chunk_size
275 * ...
276 */
277struct i915_buddy_block *
278i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order)
279{
280 struct i915_buddy_block *block = NULL;
281 unsigned int i;
282 int err;
283
284 for (i = order; i <= mm->max_order; ++i) {
285 block = list_first_entry_or_null(&mm->free_list[i],
286 struct i915_buddy_block,
287 link);
288 if (block)
289 break;
290 }
291
292 if (!block)
293 return ERR_PTR(-ENOSPC);
294
295 GEM_BUG_ON(!i915_buddy_block_is_free(block));
296
297 while (i != order) {
298 err = split_block(mm, block);
299 if (unlikely(err))
300 goto out_free;
301
302 /* Go low */
303 block = block->left;
304 i--;
305 }
306
307 mark_allocated(block);
308 kmemleak_update_trace(block);
309 return block;
310
311out_free:
312 __i915_buddy_free(mm, block);
313 return ERR_PTR(err);
314}
315
316static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
317{
318 return s1 <= e2 && e1 >= s2;
319}
320
321static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2)
322{
323 return s1 <= s2 && e1 >= e2;
324}
325
326/*
327 * Allocate range. Note that it's safe to chain together multiple alloc_ranges
328 * with the same blocks list.
329 *
330 * Intended for pre-allocating portions of the address space, for example to
331 * reserve a block for the initial framebuffer or similar, hence the expectation
332 * here is that i915_buddy_alloc() is still the main vehicle for
333 * allocations, so if that's not the case then the drm_mm range allocator is
334 * probably a much better fit, and so you should probably go use that instead.
335 */
336int i915_buddy_alloc_range(struct i915_buddy_mm *mm,
337 struct list_head *blocks,
338 u64 start, u64 size)
339{
340 struct i915_buddy_block *block;
341 struct i915_buddy_block *buddy;
342 LIST_HEAD(allocated);
343 LIST_HEAD(dfs);
344 u64 end;
345 int err;
346 int i;
347
348 if (size < mm->chunk_size)
349 return -EINVAL;
350
351 if (!IS_ALIGNED(size | start, mm->chunk_size))
352 return -EINVAL;
353
354 if (range_overflows(start, size, mm->size))
355 return -EINVAL;
356
357 for (i = 0; i < mm->n_roots; ++i)
358 list_add_tail(&mm->roots[i]->tmp_link, &dfs);
359
360 end = start + size - 1;
361
362 do {
363 u64 block_start;
364 u64 block_end;
365
366 block = list_first_entry_or_null(&dfs,
367 struct i915_buddy_block,
368 tmp_link);
369 if (!block)
370 break;
371
372 list_del(&block->tmp_link);
373
374 block_start = i915_buddy_block_offset(block);
375 block_end = block_start + i915_buddy_block_size(mm, block) - 1;
376
377 if (!overlaps(start, end, block_start, block_end))
378 continue;
379
380 if (i915_buddy_block_is_allocated(block)) {
381 err = -ENOSPC;
382 goto err_free;
383 }
384
385 if (contains(start, end, block_start, block_end)) {
386 if (!i915_buddy_block_is_free(block)) {
387 err = -ENOSPC;
388 goto err_free;
389 }
390
391 mark_allocated(block);
392 list_add_tail(&block->link, &allocated);
393 continue;
394 }
395
396 if (!i915_buddy_block_is_split(block)) {
397 err = split_block(mm, block);
398 if (unlikely(err))
399 goto err_undo;
400 }
401
402 list_add(&block->right->tmp_link, &dfs);
403 list_add(&block->left->tmp_link, &dfs);
404 } while (1);
405
406 list_splice_tail(&allocated, blocks);
407 return 0;
408
409err_undo:
410 /*
411 * We really don't want to leave around a bunch of split blocks, since
412 * bigger is better, so make sure we merge everything back before we
413 * free the allocated blocks.
414 */
415 buddy = get_buddy(block);
416 if (buddy &&
417 (i915_buddy_block_is_free(block) &&
418 i915_buddy_block_is_free(buddy)))
419 __i915_buddy_free(mm, block);
420
421err_free:
422 i915_buddy_free_list(mm, &allocated);
423 return err;
424}
425
426#if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)
427#include "selftests/i915_buddy.c"
428#endif
1// SPDX-License-Identifier: MIT
2/*
3 * Copyright © 2019 Intel Corporation
4 */
5
6#include <linux/kmemleak.h>
7#include <linux/slab.h>
8
9#include "i915_buddy.h"
10
11#include "i915_gem.h"
12#include "i915_globals.h"
13#include "i915_utils.h"
14
15static struct i915_global_block {
16 struct i915_global base;
17 struct kmem_cache *slab_blocks;
18} global;
19
20static void i915_global_buddy_shrink(void)
21{
22 kmem_cache_shrink(global.slab_blocks);
23}
24
25static void i915_global_buddy_exit(void)
26{
27 kmem_cache_destroy(global.slab_blocks);
28}
29
30static struct i915_global_block global = { {
31 .shrink = i915_global_buddy_shrink,
32 .exit = i915_global_buddy_exit,
33} };
34
35int __init i915_global_buddy_init(void)
36{
37 global.slab_blocks = KMEM_CACHE(i915_buddy_block, SLAB_HWCACHE_ALIGN);
38 if (!global.slab_blocks)
39 return -ENOMEM;
40
41 i915_global_register(&global.base);
42 return 0;
43}
44
45static struct i915_buddy_block *i915_block_alloc(struct i915_buddy_block *parent,
46 unsigned int order,
47 u64 offset)
48{
49 struct i915_buddy_block *block;
50
51 block = kmem_cache_zalloc(global.slab_blocks, GFP_KERNEL);
52 if (!block)
53 return NULL;
54
55 block->header = offset;
56 block->header |= order;
57 block->parent = parent;
58
59 return block;
60}
61
62static void i915_block_free(struct i915_buddy_block *block)
63{
64 kmem_cache_free(global.slab_blocks, block);
65}
66
67static void mark_allocated(struct i915_buddy_block *block)
68{
69 block->header &= ~I915_BUDDY_HEADER_STATE;
70 block->header |= I915_BUDDY_ALLOCATED;
71
72 list_del(&block->link);
73}
74
75static void mark_free(struct i915_buddy_mm *mm,
76 struct i915_buddy_block *block)
77{
78 block->header &= ~I915_BUDDY_HEADER_STATE;
79 block->header |= I915_BUDDY_FREE;
80
81 list_add(&block->link,
82 &mm->free_list[i915_buddy_block_order(block)]);
83}
84
85static void mark_split(struct i915_buddy_block *block)
86{
87 block->header &= ~I915_BUDDY_HEADER_STATE;
88 block->header |= I915_BUDDY_SPLIT;
89
90 list_del(&block->link);
91}
92
93int i915_buddy_init(struct i915_buddy_mm *mm, u64 size, u64 chunk_size)
94{
95 unsigned int i;
96 u64 offset;
97
98 if (size < chunk_size)
99 return -EINVAL;
100
101 if (chunk_size < PAGE_SIZE)
102 return -EINVAL;
103
104 if (!is_power_of_2(chunk_size))
105 return -EINVAL;
106
107 size = round_down(size, chunk_size);
108
109 mm->size = size;
110 mm->chunk_size = chunk_size;
111 mm->max_order = ilog2(size) - ilog2(chunk_size);
112
113 GEM_BUG_ON(mm->max_order > I915_BUDDY_MAX_ORDER);
114
115 mm->free_list = kmalloc_array(mm->max_order + 1,
116 sizeof(struct list_head),
117 GFP_KERNEL);
118 if (!mm->free_list)
119 return -ENOMEM;
120
121 for (i = 0; i <= mm->max_order; ++i)
122 INIT_LIST_HEAD(&mm->free_list[i]);
123
124 mm->n_roots = hweight64(size);
125
126 mm->roots = kmalloc_array(mm->n_roots,
127 sizeof(struct i915_buddy_block *),
128 GFP_KERNEL);
129 if (!mm->roots)
130 goto out_free_list;
131
132 offset = 0;
133 i = 0;
134
135 /*
136 * Split into power-of-two blocks, in case we are given a size that is
137 * not itself a power-of-two.
138 */
139 do {
140 struct i915_buddy_block *root;
141 unsigned int order;
142 u64 root_size;
143
144 root_size = rounddown_pow_of_two(size);
145 order = ilog2(root_size) - ilog2(chunk_size);
146
147 root = i915_block_alloc(NULL, order, offset);
148 if (!root)
149 goto out_free_roots;
150
151 mark_free(mm, root);
152
153 GEM_BUG_ON(i > mm->max_order);
154 GEM_BUG_ON(i915_buddy_block_size(mm, root) < chunk_size);
155
156 mm->roots[i] = root;
157
158 offset += root_size;
159 size -= root_size;
160 i++;
161 } while (size);
162
163 return 0;
164
165out_free_roots:
166 while (i--)
167 i915_block_free(mm->roots[i]);
168 kfree(mm->roots);
169out_free_list:
170 kfree(mm->free_list);
171 return -ENOMEM;
172}
173
174void i915_buddy_fini(struct i915_buddy_mm *mm)
175{
176 int i;
177
178 for (i = 0; i < mm->n_roots; ++i) {
179 GEM_WARN_ON(!i915_buddy_block_is_free(mm->roots[i]));
180 i915_block_free(mm->roots[i]);
181 }
182
183 kfree(mm->roots);
184 kfree(mm->free_list);
185}
186
187static int split_block(struct i915_buddy_mm *mm,
188 struct i915_buddy_block *block)
189{
190 unsigned int block_order = i915_buddy_block_order(block) - 1;
191 u64 offset = i915_buddy_block_offset(block);
192
193 GEM_BUG_ON(!i915_buddy_block_is_free(block));
194 GEM_BUG_ON(!i915_buddy_block_order(block));
195
196 block->left = i915_block_alloc(block, block_order, offset);
197 if (!block->left)
198 return -ENOMEM;
199
200 block->right = i915_block_alloc(block, block_order,
201 offset + (mm->chunk_size << block_order));
202 if (!block->right) {
203 i915_block_free(block->left);
204 return -ENOMEM;
205 }
206
207 mark_free(mm, block->left);
208 mark_free(mm, block->right);
209
210 mark_split(block);
211
212 return 0;
213}
214
215static struct i915_buddy_block *
216get_buddy(struct i915_buddy_block *block)
217{
218 struct i915_buddy_block *parent;
219
220 parent = block->parent;
221 if (!parent)
222 return NULL;
223
224 if (parent->left == block)
225 return parent->right;
226
227 return parent->left;
228}
229
230static void __i915_buddy_free(struct i915_buddy_mm *mm,
231 struct i915_buddy_block *block)
232{
233 struct i915_buddy_block *parent;
234
235 while ((parent = block->parent)) {
236 struct i915_buddy_block *buddy;
237
238 buddy = get_buddy(block);
239
240 if (!i915_buddy_block_is_free(buddy))
241 break;
242
243 list_del(&buddy->link);
244
245 i915_block_free(block);
246 i915_block_free(buddy);
247
248 block = parent;
249 }
250
251 mark_free(mm, block);
252}
253
254void i915_buddy_free(struct i915_buddy_mm *mm,
255 struct i915_buddy_block *block)
256{
257 GEM_BUG_ON(!i915_buddy_block_is_allocated(block));
258 __i915_buddy_free(mm, block);
259}
260
261void i915_buddy_free_list(struct i915_buddy_mm *mm, struct list_head *objects)
262{
263 struct i915_buddy_block *block, *on;
264
265 list_for_each_entry_safe(block, on, objects, link) {
266 i915_buddy_free(mm, block);
267 cond_resched();
268 }
269 INIT_LIST_HEAD(objects);
270}
271
272/*
273 * Allocate power-of-two block. The order value here translates to:
274 *
275 * 0 = 2^0 * mm->chunk_size
276 * 1 = 2^1 * mm->chunk_size
277 * 2 = 2^2 * mm->chunk_size
278 * ...
279 */
280struct i915_buddy_block *
281i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order)
282{
283 struct i915_buddy_block *block = NULL;
284 unsigned int i;
285 int err;
286
287 for (i = order; i <= mm->max_order; ++i) {
288 block = list_first_entry_or_null(&mm->free_list[i],
289 struct i915_buddy_block,
290 link);
291 if (block)
292 break;
293 }
294
295 if (!block)
296 return ERR_PTR(-ENOSPC);
297
298 GEM_BUG_ON(!i915_buddy_block_is_free(block));
299
300 while (i != order) {
301 err = split_block(mm, block);
302 if (unlikely(err))
303 goto out_free;
304
305 /* Go low */
306 block = block->left;
307 i--;
308 }
309
310 mark_allocated(block);
311 kmemleak_update_trace(block);
312 return block;
313
314out_free:
315 if (i != order)
316 __i915_buddy_free(mm, block);
317 return ERR_PTR(err);
318}
319
320static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
321{
322 return s1 <= e2 && e1 >= s2;
323}
324
325static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2)
326{
327 return s1 <= s2 && e1 >= e2;
328}
329
330/*
331 * Allocate range. Note that it's safe to chain together multiple alloc_ranges
332 * with the same blocks list.
333 *
334 * Intended for pre-allocating portions of the address space, for example to
335 * reserve a block for the initial framebuffer or similar, hence the expectation
336 * here is that i915_buddy_alloc() is still the main vehicle for
337 * allocations, so if that's not the case then the drm_mm range allocator is
338 * probably a much better fit, and so you should probably go use that instead.
339 */
340int i915_buddy_alloc_range(struct i915_buddy_mm *mm,
341 struct list_head *blocks,
342 u64 start, u64 size)
343{
344 struct i915_buddy_block *block;
345 struct i915_buddy_block *buddy;
346 LIST_HEAD(allocated);
347 LIST_HEAD(dfs);
348 u64 end;
349 int err;
350 int i;
351
352 if (size < mm->chunk_size)
353 return -EINVAL;
354
355 if (!IS_ALIGNED(size | start, mm->chunk_size))
356 return -EINVAL;
357
358 if (range_overflows(start, size, mm->size))
359 return -EINVAL;
360
361 for (i = 0; i < mm->n_roots; ++i)
362 list_add_tail(&mm->roots[i]->tmp_link, &dfs);
363
364 end = start + size - 1;
365
366 do {
367 u64 block_start;
368 u64 block_end;
369
370 block = list_first_entry_or_null(&dfs,
371 struct i915_buddy_block,
372 tmp_link);
373 if (!block)
374 break;
375
376 list_del(&block->tmp_link);
377
378 block_start = i915_buddy_block_offset(block);
379 block_end = block_start + i915_buddy_block_size(mm, block) - 1;
380
381 if (!overlaps(start, end, block_start, block_end))
382 continue;
383
384 if (i915_buddy_block_is_allocated(block)) {
385 err = -ENOSPC;
386 goto err_free;
387 }
388
389 if (contains(start, end, block_start, block_end)) {
390 if (!i915_buddy_block_is_free(block)) {
391 err = -ENOSPC;
392 goto err_free;
393 }
394
395 mark_allocated(block);
396 list_add_tail(&block->link, &allocated);
397 continue;
398 }
399
400 if (!i915_buddy_block_is_split(block)) {
401 err = split_block(mm, block);
402 if (unlikely(err))
403 goto err_undo;
404 }
405
406 list_add(&block->right->tmp_link, &dfs);
407 list_add(&block->left->tmp_link, &dfs);
408 } while (1);
409
410 list_splice_tail(&allocated, blocks);
411 return 0;
412
413err_undo:
414 /*
415 * We really don't want to leave around a bunch of split blocks, since
416 * bigger is better, so make sure we merge everything back before we
417 * free the allocated blocks.
418 */
419 buddy = get_buddy(block);
420 if (buddy &&
421 (i915_buddy_block_is_free(block) &&
422 i915_buddy_block_is_free(buddy)))
423 __i915_buddy_free(mm, block);
424
425err_free:
426 i915_buddy_free_list(mm, &allocated);
427 return err;
428}
429
430#if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)
431#include "selftests/i915_buddy.c"
432#endif