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