From patchwork Thu Feb 14 14:57:01 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Matthew Auld X-Patchwork-Id: 10812899 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 65C4713B4 for ; Thu, 14 Feb 2019 14:57:51 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 511702E900 for ; Thu, 14 Feb 2019 14:57:51 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 45AB52E907; Thu, 14 Feb 2019 14:57:51 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-5.2 required=2.0 tests=BAYES_00,MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 Received: from gabe.freedesktop.org (gabe.freedesktop.org [131.252.210.177]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 47AA82E906 for ; Thu, 14 Feb 2019 14:57:50 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id C75E76E913; Thu, 14 Feb 2019 14:57:48 +0000 (UTC) X-Original-To: intel-gfx@lists.freedesktop.org Delivered-To: intel-gfx@lists.freedesktop.org Received: from mga03.intel.com (mga03.intel.com [134.134.136.65]) by gabe.freedesktop.org (Postfix) with ESMTPS id 7A8596E90E for ; Thu, 14 Feb 2019 14:57:46 +0000 (UTC) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga007.jf.intel.com ([10.7.209.58]) by orsmga103.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 14 Feb 2019 06:57:46 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.58,369,1544515200"; d="scan'208";a="114920426" Received: from jhbrinke-mobl3.amr.corp.intel.com (HELO mwahaha.ger.corp.intel.com) ([10.252.11.151]) by orsmga007.jf.intel.com with ESMTP; 14 Feb 2019 06:57:45 -0800 From: Matthew Auld To: intel-gfx@lists.freedesktop.org Date: Thu, 14 Feb 2019 14:57:01 +0000 Message-Id: <20190214145740.14521-4-matthew.auld@intel.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20190214145740.14521-1-matthew.auld@intel.com> References: <20190214145740.14521-1-matthew.auld@intel.com> MIME-Version: 1.0 Subject: [Intel-gfx] [RFC PATCH 03/42] drm/i915: buddy allocator X-BeenThere: intel-gfx@lists.freedesktop.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Intel graphics driver community testing & development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: intel-gfx-bounces@lists.freedesktop.org Sender: "Intel-gfx" X-Virus-Scanned: ClamAV using ClamSMTP Really simply buddy allocator. Signed-off-by: Matthew Auld Cc: Joonas Lahtinen Cc: Abdiel Janulgue --- 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 +#include + +#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 + +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)