diff mbox series

[RFC,03/42] drm/i915: buddy allocator

Message ID 20190214145740.14521-4-matthew.auld@intel.com (mailing list archive)
State New, archived
Headers show
Series Introduce memory region concept (including device local memory) | expand

Commit Message

Matthew Auld Feb. 14, 2019, 2:57 p.m. UTC 
Really simply buddy allocator.

Signed-off-by: Matthew Auld <matthew.auld@intel.com>
Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Cc: Abdiel Janulgue <abdiel.janulgue@linux.intel.com>
---
 drivers/gpu/drm/i915/Makefile                 |   1 +
 drivers/gpu/drm/i915/i915_gem_buddy.c         | 206 +++++++++++++++++
 drivers/gpu/drm/i915/i915_gem_buddy.h         | 118 ++++++++++
 .../gpu/drm/i915/selftests/i915_gem_buddy.c   | 209 ++++++++++++++++++
 .../drm/i915/selftests/i915_mock_selftests.h  |   1 +
 5 files changed, 535 insertions(+)
 create mode 100644 drivers/gpu/drm/i915/i915_gem_buddy.c
 create mode 100644 drivers/gpu/drm/i915/i915_gem_buddy.h
 create mode 100644 drivers/gpu/drm/i915/selftests/i915_gem_buddy.c

Comments

Jani Nikula Feb. 15, 2019, 12:34 p.m. UTC | #1 
On Thu, 14 Feb 2019, Matthew Auld <matthew.auld@intel.com> wrote:
> Really simply buddy allocator.
>
> Signed-off-by: Matthew Auld <matthew.auld@intel.com>
> Cc: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
> Cc: Abdiel Janulgue <abdiel.janulgue@linux.intel.com>
> ---
>  drivers/gpu/drm/i915/Makefile                 |   1 +
>  drivers/gpu/drm/i915/i915_gem_buddy.c         | 206 +++++++++++++++++
>  drivers/gpu/drm/i915/i915_gem_buddy.h         | 118 ++++++++++
>  .../gpu/drm/i915/selftests/i915_gem_buddy.c   | 209 ++++++++++++++++++
>  .../drm/i915/selftests/i915_mock_selftests.h  |   1 +
>  5 files changed, 535 insertions(+)
>  create mode 100644 drivers/gpu/drm/i915/i915_gem_buddy.c
>  create mode 100644 drivers/gpu/drm/i915/i915_gem_buddy.h
>  create mode 100644 drivers/gpu/drm/i915/selftests/i915_gem_buddy.c
>
> diff --git a/drivers/gpu/drm/i915/Makefile b/drivers/gpu/drm/i915/Makefile
> index 1787e1299b1b..e5ce813d1936 100644
> --- a/drivers/gpu/drm/i915/Makefile
> +++ b/drivers/gpu/drm/i915/Makefile
> @@ -61,6 +61,7 @@ i915-y += \
>  	  i915_active.o \
>  	  i915_cmd_parser.o \
>  	  i915_gem_batch_pool.o \
> +	  i915_gem_buddy.o \
>  	  i915_gem_clflush.o \
>  	  i915_gem_context.o \
>  	  i915_gem_dmabuf.o \
> diff --git a/drivers/gpu/drm/i915/i915_gem_buddy.c b/drivers/gpu/drm/i915/i915_gem_buddy.c
> new file mode 100644
> index 000000000000..4dc688c091a2
> --- /dev/null
> +++ b/drivers/gpu/drm/i915/i915_gem_buddy.c
> @@ -0,0 +1,206 @@
> +/*
> + * Copyright © 2018 Intel Corporation
> + *
> + * Permission is hereby granted, free of charge, to any person obtaining a
> + * copy of this software and associated documentation files (the "Software"),
> + * to deal in the Software without restriction, including without limitation
> + * the rights to use, copy, modify, merge, publish, distribute, sublicense,
> + * and/or sell copies of the Software, and to permit persons to whom the
> + * Software is furnished to do so, subject to the following conditions:
> + *
> + * The above copyright notice and this permission notice (including the next
> + * paragraph) shall be included in all copies or substantial portions of the
> + * Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
> + * IN THE SOFTWARE.
> + *
> + */

Please replace the above with

// SPDX-License-Identifier: MIT
/*
 * Copyright © 2019 Intel Corporation
 */

Ditto for all new files being added. (Except .h which will need to have
old style /* ... */ comments around the first line.)

BR,
Jani.


> +
> +#include <linux/slab.h>
> +#include <linux/list.h>
> +
> +#include "i915_gem_buddy.h"
> +#include "i915_gem.h"
> +
> +int i915_gem_buddy_init(struct i915_gem_buddy_mm *mm, u64 size, u64 min_size)
> +{
> +	unsigned int i;
> +
> +	/*
> +	 * XXX: if not a power of 2, maybe split into power of 2 blocks,
> +	 * effectively having multiple roots, similar to if we had a global
> +	 * MAX_ORDER.
> +	 */
> +	size = rounddown_pow_of_two(size);
> +	min_size = roundup_pow_of_two(min_size);
> +
> +	if (size < min_size)
> +		return -EINVAL;
> +
> +	if (min_size < PAGE_SIZE)
> +		return -EINVAL;
> +
> +	mm->max_order = ilog2(size) - ilog2(min_size);
> +	mm->min_size = min_size;
> +
> +	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_gem_buddy_block, SLAB_HWCACHE_ALIGN);
> +	if (!mm->blocks)
> +		goto out_free_list;
> +
> +	mm->root = kmem_cache_zalloc(mm->blocks, GFP_KERNEL);
> +	if (!mm->root)
> +		goto out_free_blocks;
> +
> +	mm->root->header = mm->max_order;
> +
> +	list_add(&mm->root->link, &mm->free_list[mm->max_order]);
> +
> +	return 0;
> +
> +out_free_blocks:
> +	kmem_cache_destroy(mm->blocks);
> +out_free_list:
> +	kfree(mm->free_list);
> +
> +	return -ENOMEM;
> +}
> +
> +void i915_gem_buddy_fini(struct i915_gem_buddy_mm *mm)
> +{
> +	if (WARN_ON(i915_gem_buddy_block_allocated(mm->root)))
> +		return;
> +
> +	kfree(mm->free_list);
> +	kmem_cache_free(mm->blocks, mm->root);
> +	kmem_cache_destroy(mm->blocks);
> +}
> +
> +/*
> + * The 'order' here means:
> + *
> + * 0 = 2^0 * mm->min_size
> + * 1 = 2^1 * mm->min_size
> + * 2 = 2^2 * mm->min_size
> + * ...
> + */
> +struct i915_gem_buddy_block *
> +i915_gem_buddy_alloc(struct i915_gem_buddy_mm *mm, unsigned int order)
> +{
> +	struct i915_gem_buddy_block *block = NULL;
> +	struct i915_gem_buddy_block *root;
> +	unsigned int i;
> +
> +	for (i = order; i <= mm->max_order; ++i) {
> +		block = list_first_entry_or_null(&mm->free_list[i],
> +						 struct i915_gem_buddy_block,
> +						 link);
> +		if (block)
> +			break;
> +	}
> +
> +	if (!block)
> +		return ERR_PTR(-ENOSPC);
> +
> +	GEM_BUG_ON(i915_gem_buddy_block_allocated(block));
> +
> +	root = block;
> +
> +	while (i != order) {
> +		u64 offset = i915_gem_buddy_block_offset(block);
> +
> +		block->left = kmem_cache_zalloc(mm->blocks, GFP_KERNEL);
> +		if (!block->left)
> +			goto out_free_blocks;
> +
> +		block->left->header = offset;
> +		block->left->header |= I915_GEM_BUDDY_HEADER_ALLOCATED;
> +		block->left->header |= i - 1;
> +		block->left->parent = block;
> +
> +		INIT_LIST_HEAD(&block->left->link);
> +
> +		block->right = kmem_cache_zalloc(mm->blocks, GFP_KERNEL);
> +		if (!block->right) {
> +			kmem_cache_free(mm->blocks, block->left);
> +			goto out_free_blocks;
> +		}
> +
> +		block->right->header = offset + (BIT(i - 1) * mm->min_size);
> +		block->right->header |= i - 1;
> +		block->right->parent = block;
> +
> +		list_add(&block->right->link, &mm->free_list[i - 1]);
> +
> +		block = block->left;
> +		i--;
> +	}
> +
> +	root->header |= I915_GEM_BUDDY_HEADER_ALLOCATED;
> +	list_del(&root->link);
> +
> +	return block;
> +
> +out_free_blocks:
> +	while (block != root) {
> +		if (block->right)
> +			list_del(&block->right->link);
> +
> +		kmem_cache_free(mm->blocks, block->left);
> +		kmem_cache_free(mm->blocks, block->right);
> +
> +		block = block->parent;
> +	}
> +
> +	return ERR_PTR(-ENOMEM);
> +}
> +
> +void i915_gem_buddy_free(struct i915_gem_buddy_mm *mm,
> +			 struct i915_gem_buddy_block *block)
> +{
> +	GEM_BUG_ON(!i915_gem_buddy_block_allocated(block));
> +
> +	while (block->parent) {
> +		struct i915_gem_buddy_block *buddy;
> +		struct i915_gem_buddy_block *parent;
> +
> +		parent = block->parent;
> +
> +		if (parent->left == block)
> +			buddy = parent->right;
> +		else
> +			buddy = parent->left;
> +
> +		if (i915_gem_buddy_block_allocated(buddy))
> +			break;
> +
> +		list_del(&buddy->link);
> +
> +		kmem_cache_free(mm->blocks, block);
> +		kmem_cache_free(mm->blocks, buddy);
> +
> +		block = parent;
> +	}
> +
> +	block->header &= ~I915_GEM_BUDDY_HEADER_ALLOCATED;
> +	list_add(&block->link,
> +		 &mm->free_list[i915_gem_buddy_block_order(block)]);
> +}
> +
> +#if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)
> +#include "selftests/i915_gem_buddy.c"
> +#endif
> diff --git a/drivers/gpu/drm/i915/i915_gem_buddy.h b/drivers/gpu/drm/i915/i915_gem_buddy.h
> new file mode 100644
> index 000000000000..b3f06e9086b3
> --- /dev/null
> +++ b/drivers/gpu/drm/i915/i915_gem_buddy.h
> @@ -0,0 +1,118 @@
> +/*
> + * Copyright © 2018 Intel Corporation
> + *
> + * Permission is hereby granted, free of charge, to any person obtaining a
> + * copy of this software and associated documentation files (the "Software"),
> + * to deal in the Software without restriction, including without limitation
> + * the rights to use, copy, modify, merge, publish, distribute, sublicense,
> + * and/or sell copies of the Software, and to permit persons to whom the
> + * Software is furnished to do so, subject to the following conditions:
> + *
> + * The above copyright notice and this permission notice (including the next
> + * paragraph) shall be included in all copies or substantial portions of the
> + * Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
> + * IN THE SOFTWARE.
> + *
> + */
> +
> +#ifndef __I915_GEM_BUDDY_H__
> +#define __I915_GEM_BUDDY_H__
> +
> +#include <linux/bitops.h>
> +
> +struct list_head;
> +
> +struct i915_gem_buddy_block {
> +#define I915_GEM_BUDDY_HEADER_OFFSET (~(BIT(12) - 1))
> +#define I915_GEM_BUDDY_HEADER_ALLOCATED BIT(11)
> +#define I915_GEM_BUDDY_HEADER_ORDER (BIT(11) - 1)
> +	u64 header;
> +
> +	struct i915_gem_buddy_block *left;
> +	struct i915_gem_buddy_block *right;
> +	struct i915_gem_buddy_block *parent;
> +
> +	/* Always safe to reuse once the block is allocated */
> +	struct list_head link;
> +};
> +
> +/*
> + * Binary Buddy System
> + *
> + * XXX: Idealy we would just use the intrusive version of the buddy system i.e
> + * the classical version, where we store the block info in the free blocks, but
> + * if we are dealing with something like stolen memory, this would very quickly
> + * turn into a dumbster fire with having to memremap/ioremap parts of stolen in
> + * the allocator.
> + */
> +struct i915_gem_buddy_mm {
> +	unsigned int max_order;
> +	/* Must be at least PAGE_SIZE */
> +	u64 min_size;
> +
> +	struct kmem_cache *blocks;
> +
> +	/* Maintain a free list for each order. */
> +	struct list_head *free_list;
> +
> +	/*
> +	 * Maintain an explicit binary tree 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_gem_buddy_block *root;
> +};
> +
> +static inline u64
> +i915_gem_buddy_block_offset(struct i915_gem_buddy_block *block)
> +{
> +	return block->header & I915_GEM_BUDDY_HEADER_OFFSET;
> +}
> +
> +static inline unsigned int
> +i915_gem_buddy_block_order(struct i915_gem_buddy_block *block)
> +{
> +	return block->header & I915_GEM_BUDDY_HEADER_ORDER;
> +}
> +
> +static inline bool
> +i915_gem_buddy_block_allocated(struct i915_gem_buddy_block *block)
> +{
> +	return block->header & I915_GEM_BUDDY_HEADER_ALLOCATED;
> +}
> +
> +static inline u64
> +i915_gem_buddy_block_size(struct i915_gem_buddy_mm *mm,
> +		          struct i915_gem_buddy_block *block)
> +{
> +	return BIT(i915_gem_buddy_block_order(block)) * mm->min_size;
> +}
> +
> +static inline u64 i915_gem_buddy_size(struct i915_gem_buddy_mm *mm)
> +{
> +	return i915_gem_buddy_block_size(mm, mm->root);
> +}
> +
> +int i915_gem_buddy_init(struct i915_gem_buddy_mm *mm,
> +			u64 size,
> +			u64 min_size);
> +
> +void i915_gem_buddy_fini(struct i915_gem_buddy_mm *mm);
> +
> +struct i915_gem_buddy_block *
> +i915_gem_buddy_alloc(struct i915_gem_buddy_mm *mm,
> +		     unsigned int order);
> +
> +void i915_gem_buddy_free(struct i915_gem_buddy_mm *mm,
> +			 struct i915_gem_buddy_block *block);
> +
> +#endif
> diff --git a/drivers/gpu/drm/i915/selftests/i915_gem_buddy.c b/drivers/gpu/drm/i915/selftests/i915_gem_buddy.c
> new file mode 100644
> index 000000000000..c6782a39a1e9
> --- /dev/null
> +++ b/drivers/gpu/drm/i915/selftests/i915_gem_buddy.c
> @@ -0,0 +1,209 @@
> +/*
> + * Copyright © 2018 Intel Corporation
> + *
> + * Permission is hereby granted, free of charge, to any person obtaining a
> + * copy of this software and associated documentation files (the "Software"),
> + * to deal in the Software without restriction, including without limitation
> + * the rights to use, copy, modify, merge, publish, distribute, sublicense,
> + * and/or sell copies of the Software, and to permit persons to whom the
> + * Software is furnished to do so, subject to the following conditions:
> + *
> + * The above copyright notice and this permission notice (including the next
> + * paragraph) shall be included in all copies or substantial portions of the
> + * Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
> + * IN THE SOFTWARE.
> + *
> + */
> +
> +#include "../i915_selftest.h"
> +
> +#define SZ_64G (1ULL << 36)
> +
> +static int igt_buddy_init(void *arg)
> +{
> +	struct i915_gem_buddy_mm mm;
> +	u64 size;
> +	int err = 0;
> +
> +	for (size = PAGE_SIZE; size <= SZ_64G; size <<= 1) {
> +		struct i915_gem_buddy_block *block;
> +
> +		err = i915_gem_buddy_init(&mm, size, PAGE_SIZE);
> +		if (err) {
> +			pr_err("buddy_init with size=%llx\n failed(%d)\n",
> +			       size, err);
> +			return err;
> +		}
> +
> +		block = i915_gem_buddy_alloc(&mm, mm.max_order);
> +		if (IS_ERR(block)) {
> +			err = PTR_ERR(block);
> +			pr_err("buddy_alloc with size=%llx\n failed(%d)\n",
> +			       size, err);
> +			goto out_buddy_fini;
> +		}
> +
> +		if (i915_gem_buddy_block_order(block) != mm.max_order) {
> +			pr_err("buddy_alloc size mismatch\n");
> +			err = -EINVAL;
> +		}
> +
> +		if (i915_gem_buddy_block_offset(block) != 0) {
> +			pr_err("buddy_alloc offset mismatch\n");
> +			err = -EINVAL;
> +		}
> +
> +		if (!list_empty(&mm.free_list[mm.max_order])) {
> +			pr_err("buddy_alloc state mismatch, block is on free list\n");
> +			err = -EINVAL;
> +		}
> +
> +		if (block != mm.root) {
> +			pr_err("buddy_alloc state mismatch, block != root\n");
> +			err = -EINVAL;
> +		}
> +
> +		if (block->left || block->right) {
> +			pr_err("buddy_alloc state mismatch, block is not leaf\n");
> +			err = -EINVAL;
> +		}
> +
> +		i915_gem_buddy_free(&mm, block);
> +
> +		if (list_empty(&mm.free_list[mm.max_order])) {
> +			pr_err("buddy_free state mismatch, block not on free list\n");
> +			err = -EINVAL;
> +		}
> +
> +		i915_gem_buddy_fini(&mm);
> +
> +		if (err)
> +			return err;
> +	}
> +
> +	return 0;
> +
> +out_buddy_fini:
> +	i915_gem_buddy_fini(&mm);
> +
> +	return err;
> +}
> +
> +static int igt_buddy_alloc(void *arg)
> +{
> +	struct i915_gem_buddy_mm mm;
> +	u64 size;
> +	int order;
> +	int err;
> +
> +	err = i915_gem_buddy_init(&mm, SZ_64G, PAGE_SIZE);
> +	if (err) {
> +		pr_err("buddy_init with size=%llx\n failed(%d)\n", SZ_64G, err);
> +		return err;
> +	}
> +
> +	for (order = mm.max_order; order >= 0; order--) {
> +		struct i915_gem_buddy_block *block, *on;
> +		struct list_head blocks;
> +		u64 block_size;
> +		u64 offset;
> +		u64 prev_offset;
> +		u64 n_blocks;
> +
> +		size = i915_gem_buddy_size(&mm);
> +		if (size != SZ_64G) {
> +			pr_err("buddy_size mismatch\n");
> +			err = -EINVAL;
> +			break;
> +		}
> +
> +		if (list_empty(&mm.free_list[mm.max_order])) {
> +			pr_err("root not on the free list\n");
> +			err = -EINVAL;
> +			break;
> +		}
> +
> +		pr_info("filling address space(%llx) with order=%d\n",
> +			i915_gem_buddy_size(&mm), order);
> +
> +		prev_offset = 0;
> +		n_blocks = div64_u64(size, BIT(order) * mm.min_size);
> +		INIT_LIST_HEAD(&blocks);
> +
> +		while (n_blocks--) {
> +			block = i915_gem_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 {
> +					pr_err("buddy_alloc with order=%d failed(%d)\n",
> +					       order, err);
> +				}
> +
> +				break;
> +			}
> +
> +			list_add(&block->link, &blocks);
> +
> +			if (i915_gem_buddy_block_order(block) != order) {
> +				pr_err("buddy_alloc order mismatch\n");
> +				err = -EINVAL;
> +				break;
> +			}
> +
> +			block_size = i915_gem_buddy_block_size(&mm, block);
> +			offset = i915_gem_buddy_block_offset(block);
> +
> +			if (!IS_ALIGNED(offset, block_size)) {
> +				pr_err("buddy_alloc offset misaligned, offset=%llx, block_size=%llu\n",
> +					offset, block_size);
> +				err = -EINVAL;
> +				break;
> +			}
> +
> +			if (offset && offset != (prev_offset + block_size)) {
> +				pr_err("buddy_alloc offset mismatch, prev_offset=%llx, offset=%llx\n",
> +				       prev_offset, offset);
> +				err = -EINVAL;
> +				break;
> +			}
> +
> +			prev_offset = offset;
> +		}
> +
> +		list_for_each_entry_safe(block, on, &blocks, link) {
> +			list_del(&block->link);
> +			i915_gem_buddy_free(&mm, block);
> +		}
> +
> +		if (err)
> +			break;
> +	}
> +
> +	i915_gem_buddy_fini(&mm);
> +
> +	if (err == -ENOMEM)
> +		err = 0;
> +
> +	return err;
> +}
> +
> +int i915_gem_buddy_mock_selftests(void)
> +{
> +	static const struct i915_subtest tests[] = {
> +		SUBTEST(igt_buddy_init),
> +		SUBTEST(igt_buddy_alloc),
> +	};
> +
> +	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 88e5ab586337..984e07ed65e5 100644
> --- a/drivers/gpu/drm/i915/selftests/i915_mock_selftests.h
> +++ b/drivers/gpu/drm/i915/selftests/i915_mock_selftests.h
> @@ -24,3 +24,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_gem_buddy_mock_selftests)
Chris Wilson Feb. 15, 2019, 3:03 p.m. UTC | #2 
Quoting Jani Nikula (2019-02-15 12:34:02)
> Please replace the above with
> 
> // SPDX-License-Identifier: MIT
> /*
>  * Copyright © 2019 Intel Corporation
>  */
> 
> Ditto for all new files being added. (Except .h which will need to have
> old style /* ... */ comments around the first line.)

Rebel against the overlords imposing C++ comments upon us; we will
remain clean! I really do not see the point in using C++ for this one
instance, the perl regex is not any harder to write...
-Chris
Jani Nikula Feb. 18, 2019, 11:35 a.m. UTC | #3 
On Fri, 15 Feb 2019, Chris Wilson <chris@chris-wilson.co.uk> wrote:
> Quoting Jani Nikula (2019-02-15 12:34:02)
>> Please replace the above with
>> 
>> // SPDX-License-Identifier: MIT
>> /*
>>  * Copyright © 2019 Intel Corporation
>>  */
>> 
>> Ditto for all new files being added. (Except .h which will need to have
>> old style /* ... */ comments around the first line.)
>
> Rebel against the overlords imposing C++ comments upon us; we will
> remain clean! I really do not see the point in using C++ for this one
> instance, the perl regex is not any harder to write...

In this case, I'd rather not leave people any wiggle room. Accept any
deviation, and it'll get copy-pasted and deviated more. I want the
message to be clear, put this in verbatim and don't come up with clever
ideas. (Yeah, I see there's deviation already, and I've already
contemplated patches to fix them.)

Perhaps my sentiments are amplified by my annoyance at the combinatorial
explosion of subtly different MIT license texts we already have, making
what's supposed to be a trivial switch to SPDX rather more complicated.

BR,
Jani.
diff mbox series

Patch

diff --git a/drivers/gpu/drm/i915/Makefile b/drivers/gpu/drm/i915/Makefile
index 1787e1299b1b..e5ce813d1936 100644
--- a/drivers/gpu/drm/i915/Makefile
+++ b/drivers/gpu/drm/i915/Makefile
@@ -61,6 +61,7 @@  i915-y += \
 	  i915_active.o \
 	  i915_cmd_parser.o \
 	  i915_gem_batch_pool.o \
+	  i915_gem_buddy.o \
 	  i915_gem_clflush.o \
 	  i915_gem_context.o \
 	  i915_gem_dmabuf.o \
diff --git a/drivers/gpu/drm/i915/i915_gem_buddy.c b/drivers/gpu/drm/i915/i915_gem_buddy.c
new file mode 100644
index 000000000000..4dc688c091a2
--- /dev/null
+++ b/drivers/gpu/drm/i915/i915_gem_buddy.c
@@ -0,0 +1,206 @@ 
+/*
+ * Copyright © 2018 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ *
+ */
+
+#include <linux/slab.h>
+#include <linux/list.h>
+
+#include "i915_gem_buddy.h"
+#include "i915_gem.h"
+
+int i915_gem_buddy_init(struct i915_gem_buddy_mm *mm, u64 size, u64 min_size)
+{
+	unsigned int i;
+
+	/*
+	 * XXX: if not a power of 2, maybe split into power of 2 blocks,
+	 * effectively having multiple roots, similar to if we had a global
+	 * MAX_ORDER.
+	 */
+	size = rounddown_pow_of_two(size);
+	min_size = roundup_pow_of_two(min_size);
+
+	if (size < min_size)
+		return -EINVAL;
+
+	if (min_size < PAGE_SIZE)
+		return -EINVAL;
+
+	mm->max_order = ilog2(size) - ilog2(min_size);
+	mm->min_size = min_size;
+
+	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_gem_buddy_block, SLAB_HWCACHE_ALIGN);
+	if (!mm->blocks)
+		goto out_free_list;
+
+	mm->root = kmem_cache_zalloc(mm->blocks, GFP_KERNEL);
+	if (!mm->root)
+		goto out_free_blocks;
+
+	mm->root->header = mm->max_order;
+
+	list_add(&mm->root->link, &mm->free_list[mm->max_order]);
+
+	return 0;
+
+out_free_blocks:
+	kmem_cache_destroy(mm->blocks);
+out_free_list:
+	kfree(mm->free_list);
+
+	return -ENOMEM;
+}
+
+void i915_gem_buddy_fini(struct i915_gem_buddy_mm *mm)
+{
+	if (WARN_ON(i915_gem_buddy_block_allocated(mm->root)))
+		return;
+
+	kfree(mm->free_list);
+	kmem_cache_free(mm->blocks, mm->root);
+	kmem_cache_destroy(mm->blocks);
+}
+
+/*
+ * The 'order' here means:
+ *
+ * 0 = 2^0 * mm->min_size
+ * 1 = 2^1 * mm->min_size
+ * 2 = 2^2 * mm->min_size
+ * ...
+ */
+struct i915_gem_buddy_block *
+i915_gem_buddy_alloc(struct i915_gem_buddy_mm *mm, unsigned int order)
+{
+	struct i915_gem_buddy_block *block = NULL;
+	struct i915_gem_buddy_block *root;
+	unsigned int i;
+
+	for (i = order; i <= mm->max_order; ++i) {
+		block = list_first_entry_or_null(&mm->free_list[i],
+						 struct i915_gem_buddy_block,
+						 link);
+		if (block)
+			break;
+	}
+
+	if (!block)
+		return ERR_PTR(-ENOSPC);
+
+	GEM_BUG_ON(i915_gem_buddy_block_allocated(block));
+
+	root = block;
+
+	while (i != order) {
+		u64 offset = i915_gem_buddy_block_offset(block);
+
+		block->left = kmem_cache_zalloc(mm->blocks, GFP_KERNEL);
+		if (!block->left)
+			goto out_free_blocks;
+
+		block->left->header = offset;
+		block->left->header |= I915_GEM_BUDDY_HEADER_ALLOCATED;
+		block->left->header |= i - 1;
+		block->left->parent = block;
+
+		INIT_LIST_HEAD(&block->left->link);
+
+		block->right = kmem_cache_zalloc(mm->blocks, GFP_KERNEL);
+		if (!block->right) {
+			kmem_cache_free(mm->blocks, block->left);
+			goto out_free_blocks;
+		}
+
+		block->right->header = offset + (BIT(i - 1) * mm->min_size);
+		block->right->header |= i - 1;
+		block->right->parent = block;
+
+		list_add(&block->right->link, &mm->free_list[i - 1]);
+
+		block = block->left;
+		i--;
+	}
+
+	root->header |= I915_GEM_BUDDY_HEADER_ALLOCATED;
+	list_del(&root->link);
+
+	return block;
+
+out_free_blocks:
+	while (block != root) {
+		if (block->right)
+			list_del(&block->right->link);
+
+		kmem_cache_free(mm->blocks, block->left);
+		kmem_cache_free(mm->blocks, block->right);
+
+		block = block->parent;
+	}
+
+	return ERR_PTR(-ENOMEM);
+}
+
+void i915_gem_buddy_free(struct i915_gem_buddy_mm *mm,
+			 struct i915_gem_buddy_block *block)
+{
+	GEM_BUG_ON(!i915_gem_buddy_block_allocated(block));
+
+	while (block->parent) {
+		struct i915_gem_buddy_block *buddy;
+		struct i915_gem_buddy_block *parent;
+
+		parent = block->parent;
+
+		if (parent->left == block)
+			buddy = parent->right;
+		else
+			buddy = parent->left;
+
+		if (i915_gem_buddy_block_allocated(buddy))
+			break;
+
+		list_del(&buddy->link);
+
+		kmem_cache_free(mm->blocks, block);
+		kmem_cache_free(mm->blocks, buddy);
+
+		block = parent;
+	}
+
+	block->header &= ~I915_GEM_BUDDY_HEADER_ALLOCATED;
+	list_add(&block->link,
+		 &mm->free_list[i915_gem_buddy_block_order(block)]);
+}
+
+#if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)
+#include "selftests/i915_gem_buddy.c"
+#endif
diff --git a/drivers/gpu/drm/i915/i915_gem_buddy.h b/drivers/gpu/drm/i915/i915_gem_buddy.h
new file mode 100644
index 000000000000..b3f06e9086b3
--- /dev/null
+++ b/drivers/gpu/drm/i915/i915_gem_buddy.h
@@ -0,0 +1,118 @@ 
+/*
+ * Copyright © 2018 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ *
+ */
+
+#ifndef __I915_GEM_BUDDY_H__
+#define __I915_GEM_BUDDY_H__
+
+#include <linux/bitops.h>
+
+struct list_head;
+
+struct i915_gem_buddy_block {
+#define I915_GEM_BUDDY_HEADER_OFFSET (~(BIT(12) - 1))
+#define I915_GEM_BUDDY_HEADER_ALLOCATED BIT(11)
+#define I915_GEM_BUDDY_HEADER_ORDER (BIT(11) - 1)
+	u64 header;
+
+	struct i915_gem_buddy_block *left;
+	struct i915_gem_buddy_block *right;
+	struct i915_gem_buddy_block *parent;
+
+	/* Always safe to reuse once the block is allocated */
+	struct list_head link;
+};
+
+/*
+ * Binary Buddy System
+ *
+ * XXX: Idealy we would just use the intrusive version of the buddy system i.e
+ * the classical version, where we store the block info in the free blocks, but
+ * if we are dealing with something like stolen memory, this would very quickly
+ * turn into a dumbster fire with having to memremap/ioremap parts of stolen in
+ * the allocator.
+ */
+struct i915_gem_buddy_mm {
+	unsigned int max_order;
+	/* Must be at least PAGE_SIZE */
+	u64 min_size;
+
+	struct kmem_cache *blocks;
+
+	/* Maintain a free list for each order. */
+	struct list_head *free_list;
+
+	/*
+	 * Maintain an explicit binary tree 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_gem_buddy_block *root;
+};
+
+static inline u64
+i915_gem_buddy_block_offset(struct i915_gem_buddy_block *block)
+{
+	return block->header & I915_GEM_BUDDY_HEADER_OFFSET;
+}
+
+static inline unsigned int
+i915_gem_buddy_block_order(struct i915_gem_buddy_block *block)
+{
+	return block->header & I915_GEM_BUDDY_HEADER_ORDER;
+}
+
+static inline bool
+i915_gem_buddy_block_allocated(struct i915_gem_buddy_block *block)
+{
+	return block->header & I915_GEM_BUDDY_HEADER_ALLOCATED;
+}
+
+static inline u64
+i915_gem_buddy_block_size(struct i915_gem_buddy_mm *mm,
+		          struct i915_gem_buddy_block *block)
+{
+	return BIT(i915_gem_buddy_block_order(block)) * mm->min_size;
+}
+
+static inline u64 i915_gem_buddy_size(struct i915_gem_buddy_mm *mm)
+{
+	return i915_gem_buddy_block_size(mm, mm->root);
+}
+
+int i915_gem_buddy_init(struct i915_gem_buddy_mm *mm,
+			u64 size,
+			u64 min_size);
+
+void i915_gem_buddy_fini(struct i915_gem_buddy_mm *mm);
+
+struct i915_gem_buddy_block *
+i915_gem_buddy_alloc(struct i915_gem_buddy_mm *mm,
+		     unsigned int order);
+
+void i915_gem_buddy_free(struct i915_gem_buddy_mm *mm,
+			 struct i915_gem_buddy_block *block);
+
+#endif
diff --git a/drivers/gpu/drm/i915/selftests/i915_gem_buddy.c b/drivers/gpu/drm/i915/selftests/i915_gem_buddy.c
new file mode 100644
index 000000000000..c6782a39a1e9
--- /dev/null
+++ b/drivers/gpu/drm/i915/selftests/i915_gem_buddy.c
@@ -0,0 +1,209 @@ 
+/*
+ * Copyright © 2018 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ *
+ */
+
+#include "../i915_selftest.h"
+
+#define SZ_64G (1ULL << 36)
+
+static int igt_buddy_init(void *arg)
+{
+	struct i915_gem_buddy_mm mm;
+	u64 size;
+	int err = 0;
+
+	for (size = PAGE_SIZE; size <= SZ_64G; size <<= 1) {
+		struct i915_gem_buddy_block *block;
+
+		err = i915_gem_buddy_init(&mm, size, PAGE_SIZE);
+		if (err) {
+			pr_err("buddy_init with size=%llx\n failed(%d)\n",
+			       size, err);
+			return err;
+		}
+
+		block = i915_gem_buddy_alloc(&mm, mm.max_order);
+		if (IS_ERR(block)) {
+			err = PTR_ERR(block);
+			pr_err("buddy_alloc with size=%llx\n failed(%d)\n",
+			       size, err);
+			goto out_buddy_fini;
+		}
+
+		if (i915_gem_buddy_block_order(block) != mm.max_order) {
+			pr_err("buddy_alloc size mismatch\n");
+			err = -EINVAL;
+		}
+
+		if (i915_gem_buddy_block_offset(block) != 0) {
+			pr_err("buddy_alloc offset mismatch\n");
+			err = -EINVAL;
+		}
+
+		if (!list_empty(&mm.free_list[mm.max_order])) {
+			pr_err("buddy_alloc state mismatch, block is on free list\n");
+			err = -EINVAL;
+		}
+
+		if (block != mm.root) {
+			pr_err("buddy_alloc state mismatch, block != root\n");
+			err = -EINVAL;
+		}
+
+		if (block->left || block->right) {
+			pr_err("buddy_alloc state mismatch, block is not leaf\n");
+			err = -EINVAL;
+		}
+
+		i915_gem_buddy_free(&mm, block);
+
+		if (list_empty(&mm.free_list[mm.max_order])) {
+			pr_err("buddy_free state mismatch, block not on free list\n");
+			err = -EINVAL;
+		}
+
+		i915_gem_buddy_fini(&mm);
+
+		if (err)
+			return err;
+	}
+
+	return 0;
+
+out_buddy_fini:
+	i915_gem_buddy_fini(&mm);
+
+	return err;
+}
+
+static int igt_buddy_alloc(void *arg)
+{
+	struct i915_gem_buddy_mm mm;
+	u64 size;
+	int order;
+	int err;
+
+	err = i915_gem_buddy_init(&mm, SZ_64G, PAGE_SIZE);
+	if (err) {
+		pr_err("buddy_init with size=%llx\n failed(%d)\n", SZ_64G, err);
+		return err;
+	}
+
+	for (order = mm.max_order; order >= 0; order--) {
+		struct i915_gem_buddy_block *block, *on;
+		struct list_head blocks;
+		u64 block_size;
+		u64 offset;
+		u64 prev_offset;
+		u64 n_blocks;
+
+		size = i915_gem_buddy_size(&mm);
+		if (size != SZ_64G) {
+			pr_err("buddy_size mismatch\n");
+			err = -EINVAL;
+			break;
+		}
+
+		if (list_empty(&mm.free_list[mm.max_order])) {
+			pr_err("root not on the free list\n");
+			err = -EINVAL;
+			break;
+		}
+
+		pr_info("filling address space(%llx) with order=%d\n",
+			i915_gem_buddy_size(&mm), order);
+
+		prev_offset = 0;
+		n_blocks = div64_u64(size, BIT(order) * mm.min_size);
+		INIT_LIST_HEAD(&blocks);
+
+		while (n_blocks--) {
+			block = i915_gem_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 {
+					pr_err("buddy_alloc with order=%d failed(%d)\n",
+					       order, err);
+				}
+
+				break;
+			}
+
+			list_add(&block->link, &blocks);
+
+			if (i915_gem_buddy_block_order(block) != order) {
+				pr_err("buddy_alloc order mismatch\n");
+				err = -EINVAL;
+				break;
+			}
+
+			block_size = i915_gem_buddy_block_size(&mm, block);
+			offset = i915_gem_buddy_block_offset(block);
+
+			if (!IS_ALIGNED(offset, block_size)) {
+				pr_err("buddy_alloc offset misaligned, offset=%llx, block_size=%llu\n",
+					offset, block_size);
+				err = -EINVAL;
+				break;
+			}
+
+			if (offset && offset != (prev_offset + block_size)) {
+				pr_err("buddy_alloc offset mismatch, prev_offset=%llx, offset=%llx\n",
+				       prev_offset, offset);
+				err = -EINVAL;
+				break;
+			}
+
+			prev_offset = offset;
+		}
+
+		list_for_each_entry_safe(block, on, &blocks, link) {
+			list_del(&block->link);
+			i915_gem_buddy_free(&mm, block);
+		}
+
+		if (err)
+			break;
+	}
+
+	i915_gem_buddy_fini(&mm);
+
+	if (err == -ENOMEM)
+		err = 0;
+
+	return err;
+}
+
+int i915_gem_buddy_mock_selftests(void)
+{
+	static const struct i915_subtest tests[] = {
+		SUBTEST(igt_buddy_init),
+		SUBTEST(igt_buddy_alloc),
+	};
+
+	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 88e5ab586337..984e07ed65e5 100644
--- a/drivers/gpu/drm/i915/selftests/i915_mock_selftests.h
+++ b/drivers/gpu/drm/i915/selftests/i915_mock_selftests.h
@@ -24,3 +24,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_gem_buddy_mock_selftests)