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