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