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.
+ *
+ */
+
+#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)
-- 
2.20.1

_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/intel-gfx

Reply via email to