On Thu, 14 Feb 2019, Matthew Auld <matthew.a...@intel.com> wrote:
> Really simply buddy allocator.
>
> Signed-off-by: Matthew Auld <matthew.a...@intel.com>
> Cc: Joonas Lahtinen <joonas.lahti...@linux.intel.com>
> Cc: Abdiel Janulgue <abdiel.janul...@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)

-- 
Jani Nikula, Intel Open Source Graphics Center
_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/intel-gfx

Reply via email to