| Message ID | 20190627205633.1143-2-matthew.auld@intel.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | Introduce memory region concept (including device local memory) | expand |
Quoting Matthew Auld (2019-06-27 21:55:57) > Simple buddy allocator. We want to allocate properly aligned > power-of-two blocks to promote usage of huge-pages for the GTT, so 64K, > 2M and possibly even 1G. While we do support allocating stuff at a > specific offset, it is more intended for preallocating portions of the > address space, say for an initial framebuffer, for other uses drm_mm is > probably a much better fit. Anyway, hopefully this can all be thrown > away if we eventually move to having the core MM manage device memory. Yeah, I still have no idea why drm_mm doesn't suffice. The advantage of drm_mm_node being embedded and non-allocating is still present, but drm_mm_node has the disadvantage of having grown to accommodate multiple primary keys. A bit more of a detailed discussion on the shortcomings, and measurements for why we should use an intrinsically aligned allocator over an allocator that allows arbitrary alignments. The obvious one being allocation speed for >chunk_size allocations, but numbers :) And just how frequently does it matter? The major downside is the fragmentation penalty. That also needs discussion. (Think of the joys of kcompactd and kmigrated.) That discussion should also be mirrored in a theory of operation documentation. > Signed-off-by: Matthew Auld <matthew.auld@intel.com> > --- > drivers/gpu/drm/i915/Makefile | 1 + > drivers/gpu/drm/i915/i915_buddy.c | 413 +++++++++++++++ > drivers/gpu/drm/i915/i915_buddy.h | 115 ++++ > drivers/gpu/drm/i915/selftests/i915_buddy.c | 491 ++++++++++++++++++ > .../drm/i915/selftests/i915_mock_selftests.h | 1 + > 5 files changed, 1021 insertions(+) > create mode 100644 drivers/gpu/drm/i915/i915_buddy.c > create mode 100644 drivers/gpu/drm/i915/i915_buddy.h > create mode 100644 drivers/gpu/drm/i915/selftests/i915_buddy.c > > diff --git a/drivers/gpu/drm/i915/Makefile b/drivers/gpu/drm/i915/Makefile > index 3bd8f0349a8a..cb66cf1a5a10 100644 > --- a/drivers/gpu/drm/i915/Makefile > +++ b/drivers/gpu/drm/i915/Makefile > @@ -117,6 +117,7 @@ gem-y += \ > i915-y += \ > $(gem-y) \ > i915_active.o \ > + i915_buddy.o \ > i915_cmd_parser.o \ > i915_gem_batch_pool.o \ > i915_gem_evict.o \ > diff --git a/drivers/gpu/drm/i915/i915_buddy.c b/drivers/gpu/drm/i915/i915_buddy.c > new file mode 100644 > index 000000000000..c0ac68d71d94 > --- /dev/null > +++ b/drivers/gpu/drm/i915/i915_buddy.c > @@ -0,0 +1,413 @@ > +// SPDX-License-Identifier: MIT > +/* > + * Copyright © 2019 Intel Corporation > + */ > + > +#include <linux/slab.h> > +#include <linux/list.h> > + > +#include "i915_buddy.h" > + > +#include "i915_gem.h" > +#include "i915_utils.h" > + > +static void mark_allocated(struct i915_buddy_block *block) > +{ > + block->header &= ~I915_BUDDY_HEADER_STATE; > + block->header |= I915_BUDDY_ALLOCATED; > + > + list_del_init(&block->link); > +} > + > +static void mark_free(struct i915_buddy_mm *mm, > + struct i915_buddy_block *block) > +{ > + block->header &= ~I915_BUDDY_HEADER_STATE; > + block->header |= I915_BUDDY_FREE; > + > + list_add(&block->link, > + &mm->free_list[i915_buddy_block_order(block)]); > +} > + > +static void mark_split(struct i915_buddy_block *block) > +{ > + block->header &= ~I915_BUDDY_HEADER_STATE; > + block->header |= I915_BUDDY_SPLIT; > + > + list_del_init(&block->link); > +} > + > +int i915_buddy_init(struct i915_buddy_mm *mm, u64 size, u64 min_size) > +{ > + unsigned int i; > + u64 offset; > + > + if (size < min_size) > + return -EINVAL; > + > + if (min_size < PAGE_SIZE) > + return -EINVAL; > + > + if (!is_power_of_2(min_size)) > + return -EINVAL; > + > + size = round_down(size, min_size); > + > + mm->size = size; > + mm->min_size = min_size; > + mm->max_order = ilog2(rounddown_pow_of_two(size)) - ilog2(min_size); ilog2(rounddown_pow_of_two(size)) is ilog2(size) rounddown_pow_of_two(size): 1 << ilog2(size) so you are saying ilog2(1 << ilog2(size)) fwiw, I still think of min_size as min_chunk_size (or just chunk_size). > + > + GEM_BUG_ON(mm->max_order > I915_BUDDY_MAX_ORDER); > + > + mm->free_list = kmalloc_array(mm->max_order + 1, > + sizeof(struct list_head), > + GFP_KERNEL); > + if (!mm->free_list) > + return -ENOMEM; > + > + for (i = 0; i <= mm->max_order; ++i) > + INIT_LIST_HEAD(&mm->free_list[i]); > + > + mm->blocks = KMEM_CACHE(i915_buddy_block, SLAB_HWCACHE_ALIGN); > + if (!mm->blocks) > + goto out_free_list; Would not one global slab cache will suffice? We would have better reuse, if the kernel hasn't decided to merge slab caches. > + mm->n_roots = hweight64(size); > + > + mm->roots = kmalloc_array(mm->n_roots, > + sizeof(struct i915_buddy_block *), > + GFP_KERNEL); > + if (!mm->roots) > + goto out_free_blocks; > + > + offset = 0; > + i = 0; > + > + /* > + * Split into power-of-two blocks, in case we are given a size that is > + * not itself a power-of-two. > + */ > + do { > + struct i915_buddy_block *root; > + unsigned int order; > + u64 root_size; > + > + root = kmem_cache_zalloc(mm->blocks, GFP_KERNEL); > + if (!root) > + goto out_free_roots; > + > + root_size = rounddown_pow_of_two(size); > + order = ilog2(root_size) - ilog2(min_size); > + > + root->header = offset; > + root->header |= order; > + > + mark_free(mm, root); > + > + GEM_BUG_ON(i > mm->max_order); > + GEM_BUG_ON(i915_buddy_block_size(mm, root) < min_size); > + > + mm->roots[i] = root; > + > + offset += root_size; > + size -= root_size; > + i++; > + } while (size); > + > + return 0; > + > +out_free_roots: > + while (i--) > + kmem_cache_free(mm->blocks, mm->roots[i]); > + kfree(mm->roots); > +out_free_blocks: > + kmem_cache_destroy(mm->blocks); > +out_free_list: > + kfree(mm->free_list); > + return -ENOMEM; > +} > + > +void i915_buddy_fini(struct i915_buddy_mm *mm) > +{ > + int err = 0; > + int i; > + > + for (i = 0; i < mm->n_roots; ++i) { > + if (!i915_buddy_block_free(mm->roots[i])) { > + err = -EBUSY; > + continue; > + } > + > + kmem_cache_free(mm->blocks, mm->roots[i]); > + } > + > + /* > + * XXX: Rather leak memory for now, than hit a potential user-after-free > + */ Bug bug bug est est. > + if (WARN_ON(err)) > + return; > + > + kfree(mm->roots); > + kfree(mm->free_list); > + kmem_cache_destroy(mm->blocks); > +} > + > +static int split_block(struct i915_buddy_mm *mm, > + struct i915_buddy_block *block) > +{ > + unsigned int order = i915_buddy_block_order(block); > + u64 offset = i915_buddy_block_offset(block); > + > + GEM_BUG_ON(!i915_buddy_block_free(block)); > + GEM_BUG_ON(!order); uint order = block_order(block) - 1; > + > + block->left = kmem_cache_zalloc(mm->blocks, GFP_KERNEL); > + if (!block->left) > + return -ENOMEM; > + > + block->left->header = offset; > + block->left->header |= order - 1; > + > + block->left->parent = block; > + > + INIT_LIST_HEAD(&block->left->link); > + INIT_LIST_HEAD(&block->left->tmp_link); > + > + block->right = kmem_cache_zalloc(mm->blocks, GFP_KERNEL); > + if (!block->right) { > + kmem_cache_free(mm->blocks, block->left); > + return -ENOMEM; > + } > + > + block->right->header = offset + (BIT_ULL(order - 1) * mm->min_size); > + block->right->header |= order - 1; > + > + block->right->parent = block; > + > + INIT_LIST_HEAD(&block->right->link); > + INIT_LIST_HEAD(&block->right->tmp_link); Duplicate code? block->left = alloc_block(block, order, offset); block->right = alloc_block(block, order, offset + BIT(order) * mm->min_size); alloc_block: split->parent = block; split->header = offset; split->header |= order - 1; /* XXX having to init this pair is worrisome? */ INIT_LIST_HEAD(&split->link); INIT_LIST_HEAD(&split->tmp_link); mark_free(mm, split); return split; However, isn't one of the joys of buddy allocators that you allocate in pairs, so finding the buddy is just pointer arithmetic? > + mark_free(mm, block->left); > + mark_free(mm, block->right); > + > + mark_split(block); > + > + return 0; > +} > + > +static struct i915_buddy_block * > +get_buddy(struct i915_buddy_block *block) > +{ > + struct i915_buddy_block *parent; > + > + parent = block->parent; > + if (!parent) > + return NULL; > + > + if (parent->left == block) > + return parent->right; > + > + return parent->left; > +} > + > +static void __i915_buddy_free(struct i915_buddy_mm *mm, > + struct i915_buddy_block *block) > +{ > + list_del_init(&block->link); /* We have ownership now */ > + > + while (block->parent) { > + struct i915_buddy_block *buddy; > + > + buddy = get_buddy(block); > + > + if (!i915_buddy_block_free(buddy)) > + break; > + > + list_del(&buddy->link); > + > + kmem_cache_free(mm->blocks, block); > + kmem_cache_free(mm->blocks, buddy); > + > + block = block->parent; > + } > + > + mark_free(mm, block); > +} > + > +void i915_buddy_free(struct i915_buddy_mm *mm, > + struct i915_buddy_block *block) > +{ > + GEM_BUG_ON(!i915_buddy_block_allocated(block)); > + __i915_buddy_free(mm, block); > +} > + > +void i915_buddy_free_list(struct i915_buddy_mm *mm, > + struct list_head *objects) > +{ > + struct i915_buddy_block *block, *on; > + > + list_for_each_entry_safe(block, on, objects, link) > + i915_buddy_free(mm, block); > +} > + > +/* > + * Allocate power-of-two block. The order value here translates to: > + * > + * 0 = 2^0 * mm->min_size > + * 1 = 2^1 * mm->min_size > + * 2 = 2^2 * mm->min_size > + * ... > + */ > +struct i915_buddy_block * > +i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order) > +{ > + struct i915_buddy_block *block = NULL; > + unsigned int i; > + int err; > + > + for (i = order; i <= mm->max_order; ++i) { > + block = list_first_entry_or_null(&mm->free_list[i], > + struct i915_buddy_block, > + link); > + if (block) > + break; > + } > + > + if (!block) > + return ERR_PTR(-ENOSPC); > + > + GEM_BUG_ON(!i915_buddy_block_free(block)); > + > + while (i != order) { > + err = split_block(mm, block); > + if (unlikely(err)) > + goto out_free; > + > + /* Go low */ > + block = block->left; > + i--; > + } > + > + mark_allocated(block); > + return block; > + > +out_free: > + __i915_buddy_free(mm, block); > + return ERR_PTR(err); > +} > + > +static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2) > +{ > + return s1 <= e2 && e1 >= s2; > +} > + > +static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2) > +{ > + return s1 <= s2 && e1 >= e2; > +} > + > +/* > + * Allocate range. Note that it's safe to chain together multiple alloc_ranges > + * with the same blocks list. > + * > + * Intended for pre-allocating portions of the address space, for example to > + * reserve a block for the initial framebuffer or similar, hence the expectation > + * here is that i915_buddy_alloc() is still the main vehicle for > + * allocations, so if that's not the case then the drm_mm range allocator is > + * probably a much better fit, and so you should probably go use that instead. > + */ > +int i915_buddy_alloc_range(struct i915_buddy_mm *mm, > + struct list_head *blocks, > + u64 start, u64 size) > +{ > + struct i915_buddy_block *block; > + struct i915_buddy_block *buddy; > + LIST_HEAD(allocated); > + LIST_HEAD(dfs); > + u64 end; > + int err; > + int i; > + > + if (size < mm->min_size) > + return -EINVAL; > + > + if (!IS_ALIGNED(start, mm->min_size)) > + return -EINVAL; > + > + if (!size || !IS_ALIGNED(size, mm->min_size)) > + return -EINVAL; > + > + if (range_overflows(start, size, mm->size)) > + return -EINVAL; > + > + for (i = 0; i < mm->n_roots; ++i) > + list_add_tail(&mm->roots[i]->tmp_link, &dfs); > + > + end = start + size - 1; > + > + do { > + u64 block_start; > + u64 block_end; > + > + block = list_first_entry_or_null(&dfs, > + struct i915_buddy_block, > + tmp_link); > + if (!block) > + break; > + > + list_del(&block->tmp_link); > + > + block_start = i915_buddy_block_offset(block); > + block_end = block_start + i915_buddy_block_size(mm, block) - 1; > + > + if (!overlaps(start, end, block_start, block_end)) > + continue; > + > + if (i915_buddy_block_allocated(block)) { > + err = -ENOSPC; > + goto err_free; > + } > + > + if (contains(start, end, block_start, block_end)) { > + if (!i915_buddy_block_free(block)) { > + err = -ENOSPC; > + goto err_free; > + } > + > + mark_allocated(block); > + list_add_tail(&block->link, &allocated); > + continue; > + } > + > + if (!i915_buddy_block_split(block)) { > + err = split_block(mm, block); > + if (unlikely(err)) > + goto err_undo; > + } > + > + list_add(&block->right->tmp_link, &dfs); > + list_add(&block->left->tmp_link, &dfs); > + } while (1); > + > + list_splice_tail(&allocated, blocks); > + return 0; > + > +err_undo: > + /* > + * We really don't want to leave around a bunch of split blocks, since > + * bigger is better, so make sure we merge everything back before we > + * free the allocated blocks. > + */ > + buddy = get_buddy(block); > + if (buddy && (i915_buddy_block_free(block) && > + i915_buddy_block_free(buddy))) > + __i915_buddy_free(mm, block); > + > +err_free: > + i915_buddy_free_list(mm, &allocated); > + return err; > +} > + > +#if IS_ENABLED(CONFIG_DRM_I915_SELFTEST) > +#include "selftests/i915_buddy.c" > +#endif > diff --git a/drivers/gpu/drm/i915/i915_buddy.h b/drivers/gpu/drm/i915/i915_buddy.h > new file mode 100644 > index 000000000000..615eecd7cf4a > --- /dev/null > +++ b/drivers/gpu/drm/i915/i915_buddy.h > @@ -0,0 +1,115 @@ > +/* SPDX-License-Identifier: MIT */ > +/* > + * Copyright © 2019 Intel Corporation > + */ > + > +#ifndef __I915_BUDDY_H__ > +#define __I915_BUDDY_H__ > + > +#include <linux/bitops.h> > + > +struct list_head; You need the actual include for embedding the struct. > + > +struct i915_buddy_block { > +#define I915_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12) > +#define I915_BUDDY_HEADER_STATE GENMASK_ULL(11, 10) > +#define I915_BUDDY_ALLOCATED (1<<10) > +#define I915_BUDDY_FREE (2<<10) > +#define I915_BUDDY_SPLIT (3<<10) > +#define I915_BUDDY_HEADER_ORDER GENMASK_ULL(9, 0) > + u64 header; > + > + struct i915_buddy_block *left; > + struct i915_buddy_block *right; > + struct i915_buddy_block *parent; > + > + /* XXX: somwewhat funky */ > + struct list_head link; > + struct list_head tmp_link; > +}; > + > +#define I915_BUDDY_MAX_ORDER I915_BUDDY_HEADER_ORDER > + > +/* Binary Buddy System */ > +struct i915_buddy_mm { > + struct kmem_cache *blocks; > + > + /* 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 i915_buddy_block **roots; > + > + unsigned int n_roots; > + unsigned int max_order; > + > + /* Must be at least PAGE_SIZE */ > + u64 min_size; > + u64 size; > +}; Not one mention that the owner/caller is responsible for locking. > + > +static inline u64 > +i915_buddy_block_offset(struct i915_buddy_block *block) > +{ > + return block->header & I915_BUDDY_HEADER_OFFSET; > +} > + > +static inline unsigned int > +i915_buddy_block_order(struct i915_buddy_block *block) > +{ > + return block->header & I915_BUDDY_HEADER_ORDER; > +} > + > +static inline unsigned int > +i915_buddy_block_state(struct i915_buddy_block *block) > +{ > + return block->header & I915_BUDDY_HEADER_STATE; > +} > + > +static inline bool > +i915_buddy_block_allocated(struct i915_buddy_block *block) > +{ > + return i915_buddy_block_state(block) == I915_BUDDY_ALLOCATED; > +} > + > +static inline bool > +i915_buddy_block_free(struct i915_buddy_block *block) This needs an 'is' as free() is a rather common verb and this is very, very confusing. So is_allocated, is_free, is_split. > +{ > + return i915_buddy_block_state(block) == I915_BUDDY_FREE; > +} > + > +static inline bool > +i915_buddy_block_split(struct i915_buddy_block *block) > +{ > + return i915_buddy_block_state(block) == I915_BUDDY_SPLIT; > +} > + > +static inline u64 > +i915_buddy_block_size(struct i915_buddy_mm *mm, > + struct i915_buddy_block *block) > +{ > + return BIT(i915_buddy_block_order(block)) * mm->min_size; > +} > + > +int i915_buddy_init(struct i915_buddy_mm *mm, u64 size, u64 min_size); > + > +void i915_buddy_fini(struct i915_buddy_mm *mm); > + > +struct i915_buddy_block * > +i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order); > + > +int i915_buddy_alloc_range(struct i915_buddy_mm *mm, > + struct list_head *blocks, > + u64 start, u64 size); > + > +void i915_buddy_free(struct i915_buddy_mm *mm, struct i915_buddy_block *block); > + > +void i915_buddy_free_list(struct i915_buddy_mm *mm, struct list_head *objects); > + > +#endif > diff --git a/drivers/gpu/drm/i915/selftests/i915_buddy.c b/drivers/gpu/drm/i915/selftests/i915_buddy.c > new file mode 100644 > index 000000000000..2159aa9f4867 > --- /dev/null > +++ b/drivers/gpu/drm/i915/selftests/i915_buddy.c > @@ -0,0 +1,491 @@ > +// SPDX-License-Identifier: MIT > +/* > + * Copyright © 2019 Intel Corporation > + */ > + > +#include <linux/prime_numbers.h> > + > +#include "../i915_selftest.h" > +#include "i915_random.h" > + > +#define SZ_8G (1ULL << 33) > + > +static void __igt_dump_block(struct i915_buddy_mm *mm, > + struct i915_buddy_block *block, > + bool buddy) > +{ > + pr_err("block info: header=%llx, state=%u, order=%d, offset=%llx size=%llx root=%s buddy=%s\n", > + block->header, > + i915_buddy_block_state(block), > + i915_buddy_block_order(block), > + i915_buddy_block_offset(block), > + i915_buddy_block_size(mm, block), > + yesno(!block->parent), > + yesno(buddy)); > +} > + > +static void igt_dump_block(struct i915_buddy_mm *mm, > + struct i915_buddy_block *block) > +{ > + struct i915_buddy_block *buddy; > + > + __igt_dump_block(mm, block, false); > + > + buddy = get_buddy(block); > + if (buddy) > + __igt_dump_block(mm, buddy, true); > +} > + > +static int igt_check_block(struct i915_buddy_mm *mm, > + struct i915_buddy_block *block) > +{ > + struct i915_buddy_block *buddy; > + unsigned int block_state; > + u64 block_size; > + u64 offset; > + int err = 0; > + > + block_state = i915_buddy_block_state(block); > + > + if (block_state != I915_BUDDY_ALLOCATED && > + block_state != I915_BUDDY_FREE && > + block_state != I915_BUDDY_SPLIT) { > + pr_err("block state mismatch\n"); > + err = -EINVAL; > + } > + > + block_size = i915_buddy_block_size(mm, block); > + offset = i915_buddy_block_offset(block); > + > + if (block_size < mm->min_size) { > + pr_err("block size smaller than min size\n"); > + err = -EINVAL; > + } > + > + if (!is_power_of_2(block_size)) { > + pr_err("block size not power of two\n"); > + err = -EINVAL; > + } > + > + if (!IS_ALIGNED(block_size, mm->min_size)) { > + pr_err("block size not aligned to min size\n"); > + err = -EINVAL; > + } > + > + if (!IS_ALIGNED(offset, mm->min_size)) { > + pr_err("block offset not aligned to min size\n"); > + err = -EINVAL; > + } > + > + if (!IS_ALIGNED(offset, block_size)) { > + pr_err("block offset not aligned to block size\n"); > + err = -EINVAL; > + } > + > + buddy = get_buddy(block); > + > + if (!buddy && block->parent) { > + pr_err("buddy has gone fishing\n"); > + err = -EINVAL; > + } > + > + if (buddy) { > + if (i915_buddy_block_offset(buddy) != (offset ^ block_size)) { > + pr_err("buddy has wrong offset\n"); > + err = -EINVAL; > + } > + > + if (i915_buddy_block_size(mm, buddy) != block_size) { > + pr_err("buddy size mismatch\n"); > + err = -EINVAL; > + } > + > + if (i915_buddy_block_state(buddy) == block_state && > + block_state == I915_BUDDY_FREE) { > + pr_err("block and its buddy are free\n"); > + err = -EINVAL; > + } > + } > + > + return err; > +} > + > +static int igt_check_blocks(struct i915_buddy_mm *mm, > + struct list_head *blocks, > + u64 expected_size, > + bool is_contiguous) > +{ > + struct i915_buddy_block *block; > + struct i915_buddy_block *prev; > + u64 total; > + int err = 0; > + > + block = NULL; > + prev = NULL; > + total = 0; > + > + list_for_each_entry(block, blocks, link) { > + err = igt_check_block(mm, block); > + > + if (!i915_buddy_block_allocated(block)) { > + pr_err("block not allocated\n"), > + err = -EINVAL; > + } > + > + if (is_contiguous && prev) { > + u64 prev_block_size; > + u64 prev_offset; > + u64 offset; > + > + prev_offset = i915_buddy_block_offset(prev); > + prev_block_size = i915_buddy_block_size(mm, prev); > + offset = i915_buddy_block_offset(block); > + > + if (offset != (prev_offset + prev_block_size)) { > + pr_err("block offset mismatch\n"); > + err = -EINVAL; > + } > + } > + > + if (err) > + break; > + > + total += i915_buddy_block_size(mm, block); > + prev = block; > + } > + > + if (!err) { > + if (total != expected_size) { > + pr_err("size mismatch, expected=%llx, found=%llx\n", > + expected_size, total); > + err = -EINVAL; > + } > + return err; > + } > + > + if (prev) { > + pr_err("prev block, dump:\n"); > + igt_dump_block(mm, prev); > + } > + > + if (block) { > + pr_err("bad block, dump:\n"); > + igt_dump_block(mm, block); > + } > + > + return err; > +} > + > +static int igt_check_mm(struct i915_buddy_mm *mm) > +{ > + struct i915_buddy_block *root; > + struct i915_buddy_block *prev; > + unsigned int i; > + u64 total; > + int err = 0; > + > + if (!mm->n_roots) { > + pr_err("n_roots is zero\n"); > + return -EINVAL; > + } > + > + if (mm->n_roots != hweight64(mm->size)) { > + pr_err("n_roots mismatch, n_roots=%u, expected=%lu\n", > + mm->n_roots, hweight64(mm->size)); > + return -EINVAL; > + } > + > + root = NULL; > + prev = NULL; > + total = 0; > + > + for (i = 0; i < mm->n_roots; ++i) { > + struct i915_buddy_block *block; > + unsigned int order; > + > + root = mm->roots[i]; > + if (!root) { > + pr_err("root(%u) is NULL\n", i); > + err = -EINVAL; > + break; > + } > + > + err = igt_check_block(mm, root); > + > + if (!i915_buddy_block_free(root)) { > + pr_err("root not free\n"); > + err = -EINVAL; > + } > + > + order = i915_buddy_block_order(root); > + > + if (!i) { > + if (order != mm->max_order) { > + pr_err("max order root missing\n"); > + err = -EINVAL; > + } > + } > + > + if (prev) { > + u64 prev_block_size; > + u64 prev_offset; > + u64 offset; > + > + prev_offset = i915_buddy_block_offset(prev); > + prev_block_size = i915_buddy_block_size(mm, prev); > + offset = i915_buddy_block_offset(root); > + > + if (offset != (prev_offset + prev_block_size)) { > + pr_err("root offset mismatch\n"); > + err = -EINVAL; > + } > + } > + > + block = list_first_entry_or_null(&mm->free_list[order], > + struct i915_buddy_block, > + link); > + if (block != root) { > + pr_err("root mismatch at order=%u\n", order); > + err = -EINVAL; > + } > + > + if (err) > + break; > + > + prev = root; > + total += i915_buddy_block_size(mm, root); > + } > + > + if (!err) { > + if (total != mm->size) { > + pr_err("expected mm size=%llx, found=%llx\n", mm->size, > + total); > + err = -EINVAL; > + } > + return err; > + } > + > + if (prev) { > + pr_err("prev root(%u), dump:\n", i - 1); > + igt_dump_block(mm, prev); > + } > + > + if (root) { > + pr_err("bad root(%u), dump:\n", i); > + igt_dump_block(mm, root); > + } > + > + return err; > +} > + > +static void igt_mm_config(u64 *size, u64 *min_size) > +{ > + I915_RND_STATE(prng); > + u64 s, ms; > + > + /* Nothing fancy, just try to get an interesting bit pattern */ > + > + prandom_seed_state(&prng, i915_selftest.random_seed); > + > + s = i915_prandom_u64_state(&prng) & (SZ_8G - 1); > + ms = BIT_ULL(12 + (prandom_u32_state(&prng) % ilog2(s >> 12))); > + s = max(s & -ms, ms); > + > + *min_size = ms; > + *size = s; > +} > + > +static int igt_buddy_alloc(void *arg) > +{ > + struct i915_buddy_mm mm; > + int max_order; > + u64 min_size; > + u64 mm_size; > + int err; > + > + igt_mm_config(&mm_size, &min_size); > + > + pr_info("buddy_init with size=%llx, min_size=%llx\n", mm_size, min_size); > + > + err = i915_buddy_init(&mm, mm_size, min_size); > + if (err) { > + pr_err("buddy_init failed(%d)\n", err); > + return err; > + } > + > + for (max_order = mm.max_order; max_order >= 0; max_order--) { > + struct i915_buddy_block *block; > + int order; > + LIST_HEAD(blocks); > + u64 total; > + > + err = igt_check_mm(&mm); > + if (err) { > + pr_err("pre-mm check failed, abort\n"); > + break; > + } > + > + pr_info("filling from max_order=%u\n", max_order); > + > + order = max_order; > + total = 0; > + > + do { > +retry: > + block = i915_buddy_alloc(&mm, order); > + if (IS_ERR(block)) { > + err = PTR_ERR(block); > + if (err == -ENOMEM) { > + pr_info("buddy_alloc hit -ENOMEM with order=%d\n", > + order); > + } else { > + if (order--) { > + err = 0; > + goto retry; > + } > + > + pr_err("buddy_alloc with order=%d failed(%d)\n", > + order, err); > + } > + > + break; > + } > + > + list_add_tail(&block->link, &blocks); > + > + if (i915_buddy_block_order(block) != order) { > + pr_err("buddy_alloc order mismatch\n"); > + err = -EINVAL; > + break; > + } > + > + total += i915_buddy_block_size(&mm, block); > + } while (total < mm.size); > + > + if (!err) > + err = igt_check_blocks(&mm, &blocks, total, false); > + > + i915_buddy_free_list(&mm, &blocks); > + > + if (!err) { > + err = igt_check_mm(&mm); > + if (err) > + pr_err("post-mm check failed\n"); > + } > + > + if (err) > + break; > + } > + > + if (err == -ENOMEM) > + err = 0; > + > + i915_buddy_fini(&mm); > + > + return err; > +} > + > +static int igt_buddy_alloc_range(void *arg) > +{ > + struct i915_buddy_mm mm; > + unsigned long page_num; > + LIST_HEAD(blocks); > + u64 min_size; > + u64 offset; > + u64 size; > + u64 rem; > + int err; > + > + igt_mm_config(&size, &min_size); > + > + pr_info("buddy_init with size=%llx, min_size=%llx\n", size, min_size); > + > + err = i915_buddy_init(&mm, size, min_size); > + if (err) { > + pr_err("buddy_init failed(%d)\n", err); > + return err; > + } > + > + err = igt_check_mm(&mm); > + if (err) { > + pr_err("pre-mm check failed, abort, abort, abort!\n"); > + goto err_fini; > + } > + > + rem = mm.size; > + offset = 0; > + > + for_each_prime_number_from(page_num, 1, ULONG_MAX - 1) { > + struct i915_buddy_block *block; > + LIST_HEAD(tmp); > + > + size = min(page_num * mm.min_size, rem); > + > + err = i915_buddy_alloc_range(&mm, &tmp, offset, size); > + if (err) { > + if (err == -ENOMEM) { > + pr_info("alloc_range hit -ENOMEM with size=%llx\n", > + size); > + } else { > + pr_err("alloc_range with offset=%llx, size=%llx failed(%d)\n", > + offset, size, err); > + } > + > + break; > + } > + > + block = list_first_entry_or_null(&tmp, > + struct i915_buddy_block, > + link); > + if (!block) { > + pr_err("alloc_range has no blocks\n"); > + err = -EINVAL; > + } > + > + if (i915_buddy_block_offset(block) != offset) { > + pr_err("alloc_range start offset mismatch, found=%llx, expected=%llx\n", > + i915_buddy_block_offset(block), offset); > + err = -EINVAL; > + } > + > + if (!err) > + err = igt_check_blocks(&mm, &tmp, size, true); > + > + list_splice_tail(&tmp, &blocks); > + > + if (err) > + break; > + > + offset += size; > + > + rem -= size; > + if (!rem) > + break; > + } > + > + if (err == -ENOMEM) > + err = 0; > + > + i915_buddy_free_list(&mm, &blocks); > + > + if (!err) { > + err = igt_check_mm(&mm); > + if (err) > + pr_err("post-mm check failed\n"); > + } > + > +err_fini: > + i915_buddy_fini(&mm); > + > + return err; > +} > + > +int i915_buddy_mock_selftests(void) > +{ > + static const struct i915_subtest tests[] = { > + SUBTEST(igt_buddy_alloc), > + SUBTEST(igt_buddy_alloc_range), > + }; > + > + return i915_subtests(tests, NULL); > +} > diff --git a/drivers/gpu/drm/i915/selftests/i915_mock_selftests.h b/drivers/gpu/drm/i915/selftests/i915_mock_selftests.h > index b55da4d9ccba..b88084fe3269 100644 > --- a/drivers/gpu/drm/i915/selftests/i915_mock_selftests.h > +++ b/drivers/gpu/drm/i915/selftests/i915_mock_selftests.h > @@ -25,3 +25,4 @@ selftest(evict, i915_gem_evict_mock_selftests) > selftest(gtt, i915_gem_gtt_mock_selftests) > selftest(hugepages, i915_gem_huge_page_mock_selftests) > selftest(contexts, i915_gem_context_mock_selftests) > +selftest(buddy, i915_buddy_mock_selftests) > -- > 2.20.1 > > _______________________________________________ > Intel-gfx mailing list > Intel-gfx@lists.freedesktop.org > https://lists.freedesktop.org/mailman/listinfo/intel-gfx
Quoting Matthew Auld (2019-06-27 21:55:57) > +static void __i915_buddy_free(struct i915_buddy_mm *mm, > + struct i915_buddy_block *block) > +{ > + list_del_init(&block->link); /* We have ownership now */ That is an important observation. Even more important is that as you didn't own it, you shouldn't touch the previous linkage, and just assume control. The owner relinquished all control of the block upon freeing. -Chris
diff --git a/drivers/gpu/drm/i915/Makefile b/drivers/gpu/drm/i915/Makefile index 3bd8f0349a8a..cb66cf1a5a10 100644 --- a/drivers/gpu/drm/i915/Makefile +++ b/drivers/gpu/drm/i915/Makefile @@ -117,6 +117,7 @@ gem-y += \ i915-y += \ $(gem-y) \ i915_active.o \ + i915_buddy.o \ i915_cmd_parser.o \ i915_gem_batch_pool.o \ i915_gem_evict.o \ diff --git a/drivers/gpu/drm/i915/i915_buddy.c b/drivers/gpu/drm/i915/i915_buddy.c new file mode 100644 index 000000000000..c0ac68d71d94 --- /dev/null +++ b/drivers/gpu/drm/i915/i915_buddy.c @@ -0,0 +1,413 @@ +// SPDX-License-Identifier: MIT +/* + * Copyright © 2019 Intel Corporation + */ + +#include <linux/slab.h> +#include <linux/list.h> + +#include "i915_buddy.h" + +#include "i915_gem.h" +#include "i915_utils.h" + +static void mark_allocated(struct i915_buddy_block *block) +{ + block->header &= ~I915_BUDDY_HEADER_STATE; + block->header |= I915_BUDDY_ALLOCATED; + + list_del_init(&block->link); +} + +static void mark_free(struct i915_buddy_mm *mm, + struct i915_buddy_block *block) +{ + block->header &= ~I915_BUDDY_HEADER_STATE; + block->header |= I915_BUDDY_FREE; + + list_add(&block->link, + &mm->free_list[i915_buddy_block_order(block)]); +} + +static void mark_split(struct i915_buddy_block *block) +{ + block->header &= ~I915_BUDDY_HEADER_STATE; + block->header |= I915_BUDDY_SPLIT; + + list_del_init(&block->link); +} + +int i915_buddy_init(struct i915_buddy_mm *mm, u64 size, u64 min_size) +{ + unsigned int i; + u64 offset; + + if (size < min_size) + return -EINVAL; + + if (min_size < PAGE_SIZE) + return -EINVAL; + + if (!is_power_of_2(min_size)) + return -EINVAL; + + size = round_down(size, min_size); + + mm->size = size; + mm->min_size = min_size; + mm->max_order = ilog2(rounddown_pow_of_two(size)) - ilog2(min_size); + + GEM_BUG_ON(mm->max_order > I915_BUDDY_MAX_ORDER); + + mm->free_list = kmalloc_array(mm->max_order + 1, + sizeof(struct list_head), + GFP_KERNEL); + if (!mm->free_list) + return -ENOMEM; + + for (i = 0; i <= mm->max_order; ++i) + INIT_LIST_HEAD(&mm->free_list[i]); + + mm->blocks = KMEM_CACHE(i915_buddy_block, SLAB_HWCACHE_ALIGN); + if (!mm->blocks) + goto out_free_list; + + mm->n_roots = hweight64(size); + + mm->roots = kmalloc_array(mm->n_roots, + sizeof(struct i915_buddy_block *), + GFP_KERNEL); + if (!mm->roots) + goto out_free_blocks; + + offset = 0; + i = 0; + + /* + * Split into power-of-two blocks, in case we are given a size that is + * not itself a power-of-two. + */ + do { + struct i915_buddy_block *root; + unsigned int order; + u64 root_size; + + root = kmem_cache_zalloc(mm->blocks, GFP_KERNEL); + if (!root) + goto out_free_roots; + + root_size = rounddown_pow_of_two(size); + order = ilog2(root_size) - ilog2(min_size); + + root->header = offset; + root->header |= order; + + mark_free(mm, root); + + GEM_BUG_ON(i > mm->max_order); + GEM_BUG_ON(i915_buddy_block_size(mm, root) < min_size); + + mm->roots[i] = root; + + offset += root_size; + size -= root_size; + i++; + } while (size); + + return 0; + +out_free_roots: + while (i--) + kmem_cache_free(mm->blocks, mm->roots[i]); + kfree(mm->roots); +out_free_blocks: + kmem_cache_destroy(mm->blocks); +out_free_list: + kfree(mm->free_list); + return -ENOMEM; +} + +void i915_buddy_fini(struct i915_buddy_mm *mm) +{ + int err = 0; + int i; + + for (i = 0; i < mm->n_roots; ++i) { + if (!i915_buddy_block_free(mm->roots[i])) { + err = -EBUSY; + continue; + } + + kmem_cache_free(mm->blocks, mm->roots[i]); + } + + /* + * XXX: Rather leak memory for now, than hit a potential user-after-free + */ + if (WARN_ON(err)) + return; + + kfree(mm->roots); + kfree(mm->free_list); + kmem_cache_destroy(mm->blocks); +} + +static int split_block(struct i915_buddy_mm *mm, + struct i915_buddy_block *block) +{ + unsigned int order = i915_buddy_block_order(block); + u64 offset = i915_buddy_block_offset(block); + + GEM_BUG_ON(!i915_buddy_block_free(block)); + GEM_BUG_ON(!order); + + block->left = kmem_cache_zalloc(mm->blocks, GFP_KERNEL); + if (!block->left) + return -ENOMEM; + + block->left->header = offset; + block->left->header |= order - 1; + + block->left->parent = block; + + INIT_LIST_HEAD(&block->left->link); + INIT_LIST_HEAD(&block->left->tmp_link); + + block->right = kmem_cache_zalloc(mm->blocks, GFP_KERNEL); + if (!block->right) { + kmem_cache_free(mm->blocks, block->left); + return -ENOMEM; + } + + block->right->header = offset + (BIT_ULL(order - 1) * mm->min_size); + block->right->header |= order - 1; + + block->right->parent = block; + + INIT_LIST_HEAD(&block->right->link); + INIT_LIST_HEAD(&block->right->tmp_link); + + mark_free(mm, block->left); + mark_free(mm, block->right); + + mark_split(block); + + return 0; +} + +static struct i915_buddy_block * +get_buddy(struct i915_buddy_block *block) +{ + struct i915_buddy_block *parent; + + parent = block->parent; + if (!parent) + return NULL; + + if (parent->left == block) + return parent->right; + + return parent->left; +} + +static void __i915_buddy_free(struct i915_buddy_mm *mm, + struct i915_buddy_block *block) +{ + list_del_init(&block->link); /* We have ownership now */ + + while (block->parent) { + struct i915_buddy_block *buddy; + + buddy = get_buddy(block); + + if (!i915_buddy_block_free(buddy)) + break; + + list_del(&buddy->link); + + kmem_cache_free(mm->blocks, block); + kmem_cache_free(mm->blocks, buddy); + + block = block->parent; + } + + mark_free(mm, block); +} + +void i915_buddy_free(struct i915_buddy_mm *mm, + struct i915_buddy_block *block) +{ + GEM_BUG_ON(!i915_buddy_block_allocated(block)); + __i915_buddy_free(mm, block); +} + +void i915_buddy_free_list(struct i915_buddy_mm *mm, + struct list_head *objects) +{ + struct i915_buddy_block *block, *on; + + list_for_each_entry_safe(block, on, objects, link) + i915_buddy_free(mm, block); +} + +/* + * Allocate power-of-two block. The order value here translates to: + * + * 0 = 2^0 * mm->min_size + * 1 = 2^1 * mm->min_size + * 2 = 2^2 * mm->min_size + * ... + */ +struct i915_buddy_block * +i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order) +{ + struct i915_buddy_block *block = NULL; + unsigned int i; + int err; + + for (i = order; i <= mm->max_order; ++i) { + block = list_first_entry_or_null(&mm->free_list[i], + struct i915_buddy_block, + link); + if (block) + break; + } + + if (!block) + return ERR_PTR(-ENOSPC); + + GEM_BUG_ON(!i915_buddy_block_free(block)); + + while (i != order) { + err = split_block(mm, block); + if (unlikely(err)) + goto out_free; + + /* Go low */ + block = block->left; + i--; + } + + mark_allocated(block); + return block; + +out_free: + __i915_buddy_free(mm, block); + return ERR_PTR(err); +} + +static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2) +{ + return s1 <= e2 && e1 >= s2; +} + +static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2) +{ + return s1 <= s2 && e1 >= e2; +} + +/* + * Allocate range. Note that it's safe to chain together multiple alloc_ranges + * with the same blocks list. + * + * Intended for pre-allocating portions of the address space, for example to + * reserve a block for the initial framebuffer or similar, hence the expectation + * here is that i915_buddy_alloc() is still the main vehicle for + * allocations, so if that's not the case then the drm_mm range allocator is + * probably a much better fit, and so you should probably go use that instead. + */ +int i915_buddy_alloc_range(struct i915_buddy_mm *mm, + struct list_head *blocks, + u64 start, u64 size) +{ + struct i915_buddy_block *block; + struct i915_buddy_block *buddy; + LIST_HEAD(allocated); + LIST_HEAD(dfs); + u64 end; + int err; + int i; + + if (size < mm->min_size) + return -EINVAL; + + if (!IS_ALIGNED(start, mm->min_size)) + return -EINVAL; + + if (!size || !IS_ALIGNED(size, mm->min_size)) + return -EINVAL; + + if (range_overflows(start, size, mm->size)) + return -EINVAL; + + for (i = 0; i < mm->n_roots; ++i) + list_add_tail(&mm->roots[i]->tmp_link, &dfs); + + end = start + size - 1; + + do { + u64 block_start; + u64 block_end; + + block = list_first_entry_or_null(&dfs, + struct i915_buddy_block, + tmp_link); + if (!block) + break; + + list_del(&block->tmp_link); + + block_start = i915_buddy_block_offset(block); + block_end = block_start + i915_buddy_block_size(mm, block) - 1; + + if (!overlaps(start, end, block_start, block_end)) + continue; + + if (i915_buddy_block_allocated(block)) { + err = -ENOSPC; + goto err_free; + } + + if (contains(start, end, block_start, block_end)) { + if (!i915_buddy_block_free(block)) { + err = -ENOSPC; + goto err_free; + } + + mark_allocated(block); + list_add_tail(&block->link, &allocated); + continue; + } + + if (!i915_buddy_block_split(block)) { + err = split_block(mm, block); + if (unlikely(err)) + goto err_undo; + } + + list_add(&block->right->tmp_link, &dfs); + list_add(&block->left->tmp_link, &dfs); + } while (1); + + list_splice_tail(&allocated, blocks); + return 0; + +err_undo: + /* + * We really don't want to leave around a bunch of split blocks, since + * bigger is better, so make sure we merge everything back before we + * free the allocated blocks. + */ + buddy = get_buddy(block); + if (buddy && (i915_buddy_block_free(block) && + i915_buddy_block_free(buddy))) + __i915_buddy_free(mm, block); + +err_free: + i915_buddy_free_list(mm, &allocated); + return err; +} + +#if IS_ENABLED(CONFIG_DRM_I915_SELFTEST) +#include "selftests/i915_buddy.c" +#endif diff --git a/drivers/gpu/drm/i915/i915_buddy.h b/drivers/gpu/drm/i915/i915_buddy.h new file mode 100644 index 000000000000..615eecd7cf4a --- /dev/null +++ b/drivers/gpu/drm/i915/i915_buddy.h @@ -0,0 +1,115 @@ +/* SPDX-License-Identifier: MIT */ +/* + * Copyright © 2019 Intel Corporation + */ + +#ifndef __I915_BUDDY_H__ +#define __I915_BUDDY_H__ + +#include <linux/bitops.h> + +struct list_head; + +struct i915_buddy_block { +#define I915_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12) +#define I915_BUDDY_HEADER_STATE GENMASK_ULL(11, 10) +#define I915_BUDDY_ALLOCATED (1<<10) +#define I915_BUDDY_FREE (2<<10) +#define I915_BUDDY_SPLIT (3<<10) +#define I915_BUDDY_HEADER_ORDER GENMASK_ULL(9, 0) + u64 header; + + struct i915_buddy_block *left; + struct i915_buddy_block *right; + struct i915_buddy_block *parent; + + /* XXX: somwewhat funky */ + struct list_head link; + struct list_head tmp_link; +}; + +#define I915_BUDDY_MAX_ORDER I915_BUDDY_HEADER_ORDER + +/* Binary Buddy System */ +struct i915_buddy_mm { + struct kmem_cache *blocks; + + /* 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 i915_buddy_block **roots; + + unsigned int n_roots; + unsigned int max_order; + + /* Must be at least PAGE_SIZE */ + u64 min_size; + u64 size; +}; + +static inline u64 +i915_buddy_block_offset(struct i915_buddy_block *block) +{ + return block->header & I915_BUDDY_HEADER_OFFSET; +} + +static inline unsigned int +i915_buddy_block_order(struct i915_buddy_block *block) +{ + return block->header & I915_BUDDY_HEADER_ORDER; +} + +static inline unsigned int +i915_buddy_block_state(struct i915_buddy_block *block) +{ + return block->header & I915_BUDDY_HEADER_STATE; +} + +static inline bool +i915_buddy_block_allocated(struct i915_buddy_block *block) +{ + return i915_buddy_block_state(block) == I915_BUDDY_ALLOCATED; +} + +static inline bool +i915_buddy_block_free(struct i915_buddy_block *block) +{ + return i915_buddy_block_state(block) == I915_BUDDY_FREE; +} + +static inline bool +i915_buddy_block_split(struct i915_buddy_block *block) +{ + return i915_buddy_block_state(block) == I915_BUDDY_SPLIT; +} + +static inline u64 +i915_buddy_block_size(struct i915_buddy_mm *mm, + struct i915_buddy_block *block) +{ + return BIT(i915_buddy_block_order(block)) * mm->min_size; +} + +int i915_buddy_init(struct i915_buddy_mm *mm, u64 size, u64 min_size); + +void i915_buddy_fini(struct i915_buddy_mm *mm); + +struct i915_buddy_block * +i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order); + +int i915_buddy_alloc_range(struct i915_buddy_mm *mm, + struct list_head *blocks, + u64 start, u64 size); + +void i915_buddy_free(struct i915_buddy_mm *mm, struct i915_buddy_block *block); + +void i915_buddy_free_list(struct i915_buddy_mm *mm, struct list_head *objects); + +#endif diff --git a/drivers/gpu/drm/i915/selftests/i915_buddy.c b/drivers/gpu/drm/i915/selftests/i915_buddy.c new file mode 100644 index 000000000000..2159aa9f4867 --- /dev/null +++ b/drivers/gpu/drm/i915/selftests/i915_buddy.c @@ -0,0 +1,491 @@ +// SPDX-License-Identifier: MIT +/* + * Copyright © 2019 Intel Corporation + */ + +#include <linux/prime_numbers.h> + +#include "../i915_selftest.h" +#include "i915_random.h" + +#define SZ_8G (1ULL << 33) + +static void __igt_dump_block(struct i915_buddy_mm *mm, + struct i915_buddy_block *block, + bool buddy) +{ + pr_err("block info: header=%llx, state=%u, order=%d, offset=%llx size=%llx root=%s buddy=%s\n", + block->header, + i915_buddy_block_state(block), + i915_buddy_block_order(block), + i915_buddy_block_offset(block), + i915_buddy_block_size(mm, block), + yesno(!block->parent), + yesno(buddy)); +} + +static void igt_dump_block(struct i915_buddy_mm *mm, + struct i915_buddy_block *block) +{ + struct i915_buddy_block *buddy; + + __igt_dump_block(mm, block, false); + + buddy = get_buddy(block); + if (buddy) + __igt_dump_block(mm, buddy, true); +} + +static int igt_check_block(struct i915_buddy_mm *mm, + struct i915_buddy_block *block) +{ + struct i915_buddy_block *buddy; + unsigned int block_state; + u64 block_size; + u64 offset; + int err = 0; + + block_state = i915_buddy_block_state(block); + + if (block_state != I915_BUDDY_ALLOCATED && + block_state != I915_BUDDY_FREE && + block_state != I915_BUDDY_SPLIT) { + pr_err("block state mismatch\n"); + err = -EINVAL; + } + + block_size = i915_buddy_block_size(mm, block); + offset = i915_buddy_block_offset(block); + + if (block_size < mm->min_size) { + pr_err("block size smaller than min size\n"); + err = -EINVAL; + } + + if (!is_power_of_2(block_size)) { + pr_err("block size not power of two\n"); + err = -EINVAL; + } + + if (!IS_ALIGNED(block_size, mm->min_size)) { + pr_err("block size not aligned to min size\n"); + err = -EINVAL; + } + + if (!IS_ALIGNED(offset, mm->min_size)) { + pr_err("block offset not aligned to min size\n"); + err = -EINVAL; + } + + if (!IS_ALIGNED(offset, block_size)) { + pr_err("block offset not aligned to block size\n"); + err = -EINVAL; + } + + buddy = get_buddy(block); + + if (!buddy && block->parent) { + pr_err("buddy has gone fishing\n"); + err = -EINVAL; + } + + if (buddy) { + if (i915_buddy_block_offset(buddy) != (offset ^ block_size)) { + pr_err("buddy has wrong offset\n"); + err = -EINVAL; + } + + if (i915_buddy_block_size(mm, buddy) != block_size) { + pr_err("buddy size mismatch\n"); + err = -EINVAL; + } + + if (i915_buddy_block_state(buddy) == block_state && + block_state == I915_BUDDY_FREE) { + pr_err("block and its buddy are free\n"); + err = -EINVAL; + } + } + + return err; +} + +static int igt_check_blocks(struct i915_buddy_mm *mm, + struct list_head *blocks, + u64 expected_size, + bool is_contiguous) +{ + struct i915_buddy_block *block; + struct i915_buddy_block *prev; + u64 total; + int err = 0; + + block = NULL; + prev = NULL; + total = 0; + + list_for_each_entry(block, blocks, link) { + err = igt_check_block(mm, block); + + if (!i915_buddy_block_allocated(block)) { + pr_err("block not allocated\n"), + err = -EINVAL; + } + + if (is_contiguous && prev) { + u64 prev_block_size; + u64 prev_offset; + u64 offset; + + prev_offset = i915_buddy_block_offset(prev); + prev_block_size = i915_buddy_block_size(mm, prev); + offset = i915_buddy_block_offset(block); + + if (offset != (prev_offset + prev_block_size)) { + pr_err("block offset mismatch\n"); + err = -EINVAL; + } + } + + if (err) + break; + + total += i915_buddy_block_size(mm, block); + prev = block; + } + + if (!err) { + if (total != expected_size) { + pr_err("size mismatch, expected=%llx, found=%llx\n", + expected_size, total); + err = -EINVAL; + } + return err; + } + + if (prev) { + pr_err("prev block, dump:\n"); + igt_dump_block(mm, prev); + } + + if (block) { + pr_err("bad block, dump:\n"); + igt_dump_block(mm, block); + } + + return err; +} + +static int igt_check_mm(struct i915_buddy_mm *mm) +{ + struct i915_buddy_block *root; + struct i915_buddy_block *prev; + unsigned int i; + u64 total; + int err = 0; + + if (!mm->n_roots) { + pr_err("n_roots is zero\n"); + return -EINVAL; + } + + if (mm->n_roots != hweight64(mm->size)) { + pr_err("n_roots mismatch, n_roots=%u, expected=%lu\n", + mm->n_roots, hweight64(mm->size)); + return -EINVAL; + } + + root = NULL; + prev = NULL; + total = 0; + + for (i = 0; i < mm->n_roots; ++i) { + struct i915_buddy_block *block; + unsigned int order; + + root = mm->roots[i]; + if (!root) { + pr_err("root(%u) is NULL\n", i); + err = -EINVAL; + break; + } + + err = igt_check_block(mm, root); + + if (!i915_buddy_block_free(root)) { + pr_err("root not free\n"); + err = -EINVAL; + } + + order = i915_buddy_block_order(root); + + if (!i) { + if (order != mm->max_order) { + pr_err("max order root missing\n"); + err = -EINVAL; + } + } + + if (prev) { + u64 prev_block_size; + u64 prev_offset; + u64 offset; + + prev_offset = i915_buddy_block_offset(prev); + prev_block_size = i915_buddy_block_size(mm, prev); + offset = i915_buddy_block_offset(root); + + if (offset != (prev_offset + prev_block_size)) { + pr_err("root offset mismatch\n"); + err = -EINVAL; + } + } + + block = list_first_entry_or_null(&mm->free_list[order], + struct i915_buddy_block, + link); + if (block != root) { + pr_err("root mismatch at order=%u\n", order); + err = -EINVAL; + } + + if (err) + break; + + prev = root; + total += i915_buddy_block_size(mm, root); + } + + if (!err) { + if (total != mm->size) { + pr_err("expected mm size=%llx, found=%llx\n", mm->size, + total); + err = -EINVAL; + } + return err; + } + + if (prev) { + pr_err("prev root(%u), dump:\n", i - 1); + igt_dump_block(mm, prev); + } + + if (root) { + pr_err("bad root(%u), dump:\n", i); + igt_dump_block(mm, root); + } + + return err; +} + +static void igt_mm_config(u64 *size, u64 *min_size) +{ + I915_RND_STATE(prng); + u64 s, ms; + + /* Nothing fancy, just try to get an interesting bit pattern */ + + prandom_seed_state(&prng, i915_selftest.random_seed); + + s = i915_prandom_u64_state(&prng) & (SZ_8G - 1); + ms = BIT_ULL(12 + (prandom_u32_state(&prng) % ilog2(s >> 12))); + s = max(s & -ms, ms); + + *min_size = ms; + *size = s; +} + +static int igt_buddy_alloc(void *arg) +{ + struct i915_buddy_mm mm; + int max_order; + u64 min_size; + u64 mm_size; + int err; + + igt_mm_config(&mm_size, &min_size); + + pr_info("buddy_init with size=%llx, min_size=%llx\n", mm_size, min_size); + + err = i915_buddy_init(&mm, mm_size, min_size); + if (err) { + pr_err("buddy_init failed(%d)\n", err); + return err; + } + + for (max_order = mm.max_order; max_order >= 0; max_order--) { + struct i915_buddy_block *block; + int order; + LIST_HEAD(blocks); + u64 total; + + err = igt_check_mm(&mm); + if (err) { + pr_err("pre-mm check failed, abort\n"); + break; + } + + pr_info("filling from max_order=%u\n", max_order); + + order = max_order; + total = 0; + + do { +retry: + block = i915_buddy_alloc(&mm, order); + if (IS_ERR(block)) { + err = PTR_ERR(block); + if (err == -ENOMEM) { + pr_info("buddy_alloc hit -ENOMEM with order=%d\n", + order); + } else { + if (order--) { + err = 0; + goto retry; + } + + pr_err("buddy_alloc with order=%d failed(%d)\n", + order, err); + } + + break; + } + + list_add_tail(&block->link, &blocks); + + if (i915_buddy_block_order(block) != order) { + pr_err("buddy_alloc order mismatch\n"); + err = -EINVAL; + break; + } + + total += i915_buddy_block_size(&mm, block); + } while (total < mm.size); + + if (!err) + err = igt_check_blocks(&mm, &blocks, total, false); + + i915_buddy_free_list(&mm, &blocks); + + if (!err) { + err = igt_check_mm(&mm); + if (err) + pr_err("post-mm check failed\n"); + } + + if (err) + break; + } + + if (err == -ENOMEM) + err = 0; + + i915_buddy_fini(&mm); + + return err; +} + +static int igt_buddy_alloc_range(void *arg) +{ + struct i915_buddy_mm mm; + unsigned long page_num; + LIST_HEAD(blocks); + u64 min_size; + u64 offset; + u64 size; + u64 rem; + int err; + + igt_mm_config(&size, &min_size); + + pr_info("buddy_init with size=%llx, min_size=%llx\n", size, min_size); + + err = i915_buddy_init(&mm, size, min_size); + if (err) { + pr_err("buddy_init failed(%d)\n", err); + return err; + } + + err = igt_check_mm(&mm); + if (err) { + pr_err("pre-mm check failed, abort, abort, abort!\n"); + goto err_fini; + } + + rem = mm.size; + offset = 0; + + for_each_prime_number_from(page_num, 1, ULONG_MAX - 1) { + struct i915_buddy_block *block; + LIST_HEAD(tmp); + + size = min(page_num * mm.min_size, rem); + + err = i915_buddy_alloc_range(&mm, &tmp, offset, size); + if (err) { + if (err == -ENOMEM) { + pr_info("alloc_range hit -ENOMEM with size=%llx\n", + size); + } else { + pr_err("alloc_range with offset=%llx, size=%llx failed(%d)\n", + offset, size, err); + } + + break; + } + + block = list_first_entry_or_null(&tmp, + struct i915_buddy_block, + link); + if (!block) { + pr_err("alloc_range has no blocks\n"); + err = -EINVAL; + } + + if (i915_buddy_block_offset(block) != offset) { + pr_err("alloc_range start offset mismatch, found=%llx, expected=%llx\n", + i915_buddy_block_offset(block), offset); + err = -EINVAL; + } + + if (!err) + err = igt_check_blocks(&mm, &tmp, size, true); + + list_splice_tail(&tmp, &blocks); + + if (err) + break; + + offset += size; + + rem -= size; + if (!rem) + break; + } + + if (err == -ENOMEM) + err = 0; + + i915_buddy_free_list(&mm, &blocks); + + if (!err) { + err = igt_check_mm(&mm); + if (err) + pr_err("post-mm check failed\n"); + } + +err_fini: + i915_buddy_fini(&mm); + + return err; +} + +int i915_buddy_mock_selftests(void) +{ + static const struct i915_subtest tests[] = { + SUBTEST(igt_buddy_alloc), + SUBTEST(igt_buddy_alloc_range), + }; + + return i915_subtests(tests, NULL); +} diff --git a/drivers/gpu/drm/i915/selftests/i915_mock_selftests.h b/drivers/gpu/drm/i915/selftests/i915_mock_selftests.h index b55da4d9ccba..b88084fe3269 100644 --- a/drivers/gpu/drm/i915/selftests/i915_mock_selftests.h +++ b/drivers/gpu/drm/i915/selftests/i915_mock_selftests.h @@ -25,3 +25,4 @@ selftest(evict, i915_gem_evict_mock_selftests) selftest(gtt, i915_gem_gtt_mock_selftests) selftest(hugepages, i915_gem_huge_page_mock_selftests) selftest(contexts, i915_gem_context_mock_selftests) +selftest(buddy, i915_buddy_mock_selftests)
Simple buddy allocator. We want to allocate properly aligned power-of-two blocks to promote usage of huge-pages for the GTT, so 64K, 2M and possibly even 1G. While we do support allocating stuff at a specific offset, it is more intended for preallocating portions of the address space, say for an initial framebuffer, for other uses drm_mm is probably a much better fit. Anyway, hopefully this can all be thrown away if we eventually move to having the core MM manage device memory. Signed-off-by: Matthew Auld <matthew.auld@intel.com> --- drivers/gpu/drm/i915/Makefile | 1 + drivers/gpu/drm/i915/i915_buddy.c | 413 +++++++++++++++ drivers/gpu/drm/i915/i915_buddy.h | 115 ++++ drivers/gpu/drm/i915/selftests/i915_buddy.c | 491 ++++++++++++++++++ .../drm/i915/selftests/i915_mock_selftests.h | 1 + 5 files changed, 1021 insertions(+) create mode 100644 drivers/gpu/drm/i915/i915_buddy.c create mode 100644 drivers/gpu/drm/i915/i915_buddy.h create mode 100644 drivers/gpu/drm/i915/selftests/i915_buddy.c