From patchwork Sat Feb 17 20:24:01 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chuck Lever X-Patchwork-Id: 13561589 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 704E6C48BC4 for ; Sat, 17 Feb 2024 20:24:07 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D9ED28D0009; Sat, 17 Feb 2024 15:24:06 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id D4F7F8D0001; Sat, 17 Feb 2024 15:24:06 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C17DF8D0009; Sat, 17 Feb 2024 15:24:06 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id AC1028D0001 for ; Sat, 17 Feb 2024 15:24:06 -0500 (EST) Received: from smtpin27.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 641151A0321 for ; Sat, 17 Feb 2024 20:24:06 +0000 (UTC) X-FDA: 81802422492.27.9B40CEE Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by imf11.hostedemail.com (Postfix) with ESMTP id DE37640014 for ; Sat, 17 Feb 2024 20:24:04 +0000 (UTC) Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=LKKwFZ37; spf=pass (imf11.hostedemail.com: domain of cel@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=cel@kernel.org; dmarc=pass (policy=none) header.from=kernel.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1708201445; a=rsa-sha256; cv=none; b=zZ71Zj/odW47DeSttzjBpUk5WQi65tnlm9lsbeb40occSu6ndpY2jaihx2OTSx4w4P0+uH bCCQ5V9LnijgG3hisWD393lBK9op7V+fI/3FL06xg0PGX0utBeSgfE0Gh3E6Lls9jp+KLo Qo1N0J/JzXkvp+pRb9MrPZ3gs8SC+nM= ARC-Authentication-Results: i=1; imf11.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=LKKwFZ37; spf=pass (imf11.hostedemail.com: domain of cel@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=cel@kernel.org; dmarc=pass (policy=none) header.from=kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1708201445; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=SMUmZcMQoKBIp6RbfLcR8dux0Zzz6xVP4+GW5vJ+kwE=; b=mpvHtnUOzRSdkzdSu5oTfHp6r9we6FR9oEZnSYUpve+Mv08Bx4fgJzvSja8GO+ikG4brur +NvHOSgkkwSuWeFDICeoyK1pXeq/BmeeoI1vin0iR9B+cnK7znYb/5MWmfHElGGpvghAWN 5OwWzMEH8yIgAeFwEYktQoqcFJvKs/M= Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by dfw.source.kernel.org (Postfix) with ESMTP id 1431B608D6; Sat, 17 Feb 2024 20:24:04 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id B44EAC43390; Sat, 17 Feb 2024 20:24:02 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1708201443; bh=B9f3lBdgCzE5vmYqmwo7dByZImNHwFkUKnKEUUxLAe8=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=LKKwFZ378z7nftyteopcpFImAvTgQDtbs6xRUS2AQ1HltVj6RhcqOIUwjYinyg1U0 GDDicWz5fjRAz4dbG9+0SL6K5hMzvUbHJ35XkN5ywzAsR9cfQwY7TiXSjSZ5oW5sit undKjeWvGc1a7gM6AwMn9yB8nc1zUm8pz2QzWsQo05o28qpCqLf2sWiKayXQCsipgw jNNOwjHB+9U8UjoIo9pD7Bo4l23YoRl2ygwooQhBOhzIhhnzp4mn5QrKSRmh/jZqPz q+XtUJWAzB7Cp2QTyfet6z7B5fjdWN0dgaLuOaU6PxCE6WYPA56RHSrvUhzJQpBufG lsiQTs4cxaUfA== Subject: [PATCH v2 4/6] maple_tree: Add mtree_alloc_cyclic() From: Chuck Lever To: viro@zeniv.linux.org.uk, brauner@kernel.org, jack@suse.cz, hughd@google.com, akpm@linux-foundation.org, Liam.Howlett@oracle.com, oliver.sang@intel.com, feng.tang@intel.com Cc: linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, lkp@intel.com Date: Sat, 17 Feb 2024 15:24:01 -0500 Message-ID: <170820144179.6328.12838600511394432325.stgit@91.116.238.104.host.secureserver.net> In-Reply-To: <170820083431.6328.16233178852085891453.stgit@91.116.238.104.host.secureserver.net> References: <170820083431.6328.16233178852085891453.stgit@91.116.238.104.host.secureserver.net> User-Agent: StGit/1.5 MIME-Version: 1.0 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: DE37640014 X-Stat-Signature: i6qghuaokrb8grddmfyby6reem6j5xsw X-Rspam-User: X-HE-Tag: 1708201444-20106 X-HE-Meta: U2FsdGVkX18R4QlkLZ9jG6fiwphfgm7+7kBWhaXyS5BMs6kNbgneWisYAGpwpPXquPW8eGgov+JqUbEf0VMr2RSIWPc/MyU9NFBTywrh9/8ngmOTqd4vRqrEqppHk+1RJg7PEzTw3lv6SCWgU5rRwhBznN7FhaP5onxTx4+gT6A7wKHwJ5hnOMnVDbEAU4AK3NVI4gELZvhgoNR4lLi9gB+bmaxzkyyMCaPhPumZ5TV57oUM+J4rIdQzGhwqXOOuh/Fm+OGd+faGWqE0esqeUoLFel5kErign5KkMrUs/JjSNWL88sHc10t3Cq69Q+H7m0Ymnd5mJZhS8udZziO9JV9/+P6Md7kV4styatAHgq8sRLTYy4MgmIaIhYuq5trnbq97DE5fvgHqArf8m+TyHw85XacJ2lnNWq6kZ+eKK2v+O/ykiMhGHgr2deocdq3DQroo1YD0wrEJnisZ/izoqnaAFjwjmuQGrxHWe0KyDQpjmCjdbbJWP++iV+8Oi8eXN+bIiFvTa3mD8tpWU4wDJpSbBKujfX0m1ZJA6xRuwWIYweXe68mVYQpoDR0P+RcQHsKOIOxl7NgCzUWrcf3vzrGtvy9fkxO/Atj+4XfzndrJtIAtKCv4lGBrUTcNXMWq9vDvIYpyzBExUbdGiVSmfGlpSLf8a4N34CboHVugEM62PUrnKq3i8nsrzDTWfjFZuzJ5xUftnUZrPray80NtwtKJY/rQk1LuzDHXNabw4El9sqeGe1VspFV9JN1X0i8IGtj1UGh7gPjcF1Dyy47qJlEzYFw/JRSZYMt+/U/U+sD0S/B7nYXsghYnsqjkGw9olrsNE7RLdI2J/9GobWdSog2CPglFQze3mmwoSGKQStluTcpupxISoHU/7hjJLoDFJPIUSg+xJcOnQtWDLwcZTCpJW6/1B3mQUsCU3CgsqNhyA1dUnglgMa5ULYgStC4xgEF5lJAAmEw= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: From: Chuck Lever I need a cyclic allocator for the simple_offset implementation in fs/libfs.c. Signed-off-by: Chuck Lever --- include/linux/maple_tree.h | 7 +++ lib/maple_tree.c | 93 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 100 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index b3d63123b945..a53ad4dabd7e 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -171,6 +171,7 @@ enum maple_type { #define MT_FLAGS_LOCK_IRQ 0x100 #define MT_FLAGS_LOCK_BH 0x200 #define MT_FLAGS_LOCK_EXTERN 0x300 +#define MT_FLAGS_ALLOC_WRAPPED 0x0800 #define MAPLE_HEIGHT_MAX 31 @@ -319,6 +320,9 @@ int mtree_insert_range(struct maple_tree *mt, unsigned long first, int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, void *entry, unsigned long size, unsigned long min, unsigned long max, gfp_t gfp); +int mtree_alloc_cyclic(struct maple_tree *mt, unsigned long *startp, + void *entry, unsigned long range_lo, unsigned long range_hi, + unsigned long *next, gfp_t gfp); int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp, void *entry, unsigned long size, unsigned long min, unsigned long max, gfp_t gfp); @@ -499,6 +503,9 @@ void *mas_find_range(struct ma_state *mas, unsigned long max); void *mas_find_rev(struct ma_state *mas, unsigned long min); void *mas_find_range_rev(struct ma_state *mas, unsigned long max); int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp); +int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp, + void *entry, unsigned long range_lo, unsigned long range_hi, + unsigned long *next, gfp_t gfp); bool mas_nomem(struct ma_state *mas, gfp_t gfp); void mas_pause(struct ma_state *mas); diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6f241bb38799..af0970288727 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4290,6 +4290,56 @@ static inline void *mas_insert(struct ma_state *mas, void *entry) } +/** + * mas_alloc_cyclic() - Internal call to find somewhere to store an entry + * @mas: The maple state. + * @startp: Pointer to ID. + * @range_lo: Lower bound of range to search. + * @range_hi: Upper bound of range to search. + * @entry: The entry to store. + * @next: Pointer to next ID to allocate. + * @gfp: The GFP_FLAGS to use for allocations. + * + * Return: 0 if the allocation succeeded without wrapping, 1 if the + * allocation succeeded after wrapping, or -EBUSY if there are no + * free entries. + */ +int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp, + void *entry, unsigned long range_lo, unsigned long range_hi, + unsigned long *next, gfp_t gfp) +{ + unsigned long min = range_lo; + int ret = 0; + + range_lo = max(min, *next); + ret = mas_empty_area(mas, range_lo, range_hi, 1); + if ((mas->tree->ma_flags & MT_FLAGS_ALLOC_WRAPPED) && ret == 0) { + mas->tree->ma_flags &= ~MT_FLAGS_ALLOC_WRAPPED; + ret = 1; + } + if (ret < 0 && range_lo > min) { + ret = mas_empty_area(mas, min, range_hi, 1); + if (ret == 0) + ret = 1; + } + if (ret < 0) + return ret; + + do { + mas_insert(mas, entry); + } while (mas_nomem(mas, gfp)); + if (mas_is_err(mas)) + return xa_err(mas->node); + + *startp = mas->index; + *next = *startp + 1; + if (*next == 0) + mas->tree->ma_flags |= MT_FLAGS_ALLOC_WRAPPED; + + return ret; +} +EXPORT_SYMBOL(mas_alloc_cyclic); + static __always_inline void mas_rewalk(struct ma_state *mas, unsigned long index) { retry: @@ -6443,6 +6493,49 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, } EXPORT_SYMBOL(mtree_alloc_range); +/** + * mtree_alloc_cyclic() - Find somewhere to store this entry in the tree. + * @mt: The maple tree. + * @startp: Pointer to ID. + * @range_lo: Lower bound of range to search. + * @range_hi: Upper bound of range to search. + * @entry: The entry to store. + * @next: Pointer to next ID to allocate. + * @gfp: The GFP_FLAGS to use for allocations. + * + * Finds an empty entry in @mt after @next, stores the new index into + * the @id pointer, stores the entry at that index, then updates @next. + * + * @mt must be initialized with the MT_FLAGS_ALLOC_RANGE flag. + * + * Context: Any context. Takes and releases the mt.lock. May sleep if + * the @gfp flags permit. + * + * Return: 0 if the allocation succeeded without wrapping, 1 if the + * allocation succeeded after wrapping, -ENOMEM if memory could not be + * allocated, -EINVAL if @mt cannot be used, or -EBUSY if there are no + * free entries. + */ +int mtree_alloc_cyclic(struct maple_tree *mt, unsigned long *startp, + void *entry, unsigned long range_lo, unsigned long range_hi, + unsigned long *next, gfp_t gfp) +{ + int ret; + + MA_STATE(mas, mt, 0, 0); + + if (!mt_is_alloc(mt)) + return -EINVAL; + if (WARN_ON_ONCE(mt_is_reserved(entry))) + return -EINVAL; + mtree_lock(mt); + ret = mas_alloc_cyclic(&mas, startp, entry, range_lo, range_hi, + next, gfp); + mtree_unlock(mt); + return ret; +} +EXPORT_SYMBOL(mtree_alloc_cyclic); + int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp, void *entry, unsigned long size, unsigned long min, unsigned long max, gfp_t gfp)