From patchwork Thu Oct 31 23:16:26 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13858439 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 25C03E6748F for ; Thu, 31 Oct 2024 23:17:06 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 2302B6B009C; Thu, 31 Oct 2024 19:17:02 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 0FF396B009D; Thu, 31 Oct 2024 19:17:02 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E3C3A6B009E; Thu, 31 Oct 2024 19:17:01 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id B785B6B009C for ; Thu, 31 Oct 2024 19:17:01 -0400 (EDT) Received: from smtpin13.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 7B58EAD920 for ; Thu, 31 Oct 2024 23:17:01 +0000 (UTC) X-FDA: 82735458456.13.AE3FE22 Received: from mail-ej1-f46.google.com (mail-ej1-f46.google.com [209.85.218.46]) by imf07.hostedemail.com (Postfix) with ESMTP id 492214001C for ; Thu, 31 Oct 2024 23:16:21 +0000 (UTC) Authentication-Results: imf07.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=N2zPQqoV; spf=pass (imf07.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.46 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1730416538; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:in-reply-to: references:references:dkim-signature; bh=oMVXV57zFNyKC6hSUbXS6uwPipyiopxuXakojloGh0Y=; b=3pJ8ITuKptsK353KEw7CfZbp/KXWO55SwJ2/0xZQiHwOsCzSLpeRD4s5hZtWfhzAh82dPd LwKUQqFoH+vc8IubTc9v45Q8Aklf8ACF1HEvpRpoixy3BZcew8mACIO3TjxPEeAIXtxq68 ROKiu5C8XkKO4a9uJsiczc49DWqsnGM= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1730416538; a=rsa-sha256; cv=none; b=y88QclKoy0gAPaOV19jlFrSR4CfyZqwAYmdjdRg7UQPYWXYTGfH4/YMbj6fcnzb6NP+cLK t4Cx4+JURgP+MO3m1vtuCbAnYNzWI85kRXdZY355ToQtjtb+yJbLFrs77gCE8jAENsj4nT Smqz0OKkpNw5GziHAxrjPd9sX+sahjM= ARC-Authentication-Results: i=1; imf07.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=N2zPQqoV; spf=pass (imf07.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.46 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-ej1-f46.google.com with SMTP id a640c23a62f3a-a9a26a5d6bfso213893866b.1 for ; Thu, 31 Oct 2024 16:16:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1730416618; x=1731021418; darn=kvack.org; h=references:in-reply-to:message-id:date:subject:cc:to:from:from:to :cc:subject:date:message-id:reply-to; bh=oMVXV57zFNyKC6hSUbXS6uwPipyiopxuXakojloGh0Y=; b=N2zPQqoVjG1y8qM12AMAYQATE5VD0wqLkmfyv4yjPP0d2uHmasKKOSatK19jDhl07s CUiqrE7LG+rG5WfuKZgJiY4FWjcQaz6IwNAYie+kxQV7OE7m+yhHmT6vPLgSph+jbseW jiyexfmX8sJEkJOx/EmPVt0n5RkBmGzFAzQFgq2yJlw0Ac0Y+iQ6s2bMx/z3HxS//I9a FniT9oIdnf6kNDibs5cYV2+Hs0psI/+yUB6hlos9Ke0K07dUf6bRWQhq7aYctOM453Sn m3ncTADJf5lBspG4av6WfMme8gE1FXQORm2Y4WN1cz/ETEWBb7LiQTb9K5H0WvTyzHgJ uTGQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1730416618; x=1731021418; h=references:in-reply-to:message-id:date:subject:cc:to:from :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=oMVXV57zFNyKC6hSUbXS6uwPipyiopxuXakojloGh0Y=; b=wGPylW20mJTuph2bZaNeGJY3nPov1PEC0yvzGIaviS7r4xXGPWy0/K7JX1YfldjnSX HamObM3YFaOHw6r6rRAu2q0O45c8Gy66C2R5bJpmCmaVl7fyI9GCstqRJBNuCtALXh7P im4cJNUhmyAqm3IjYH+Uh/Pjm0l59MugpRneGVq6jeiIpm4pN/c5Wox1bJWE/Uz6h7es NFpj0N/mCFogZA65yWhI8iGX5fTOLBXkrQkInoy/RwxmevX0dvbRVOsrc5buAUqdAenY NkrZDN96YRF2gIJVwNse8rq90wMr2BnpnDLjVLEq++w6LA1rHp+ixX9IoEnVuQSdFU7b waYA== X-Forwarded-Encrypted: i=1; AJvYcCXf4ejUL1gBnyVWOXbs/4H7s+Fu8RIBDfYk+mMqNgv97TUMIl0LDYA9WNfiOZk6obBUUK0H7L51tA==@kvack.org X-Gm-Message-State: AOJu0Yz9rJs4COdYTLGciAuHit1cY9n5Hk3sNzAFrNjdS/L7mp04+PmK ZYoFc9J2Q4QvjAs1GBnyiHzf8BZLwUvtL2+YI0ZG+bfmJRcFl3RYpjC7dA== X-Google-Smtp-Source: AGHT+IEdYHF6rz8qzh0nA6nPkS0yzoExsZJUeLNX6F3y+CNyUQTmzJjR9k+lqrh/i61OAOJa+7FEIw== X-Received: by 2002:a17:907:2dac:b0:a99:6791:5449 with SMTP id a640c23a62f3a-a9e6587df7fmr162789966b.52.1730416618160; Thu, 31 Oct 2024 16:16:58 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9e566435d9sm116909266b.171.2024.10.31.16.16.57 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Thu, 31 Oct 2024 16:16:57 -0700 (PDT) From: Wei Yang To: Liam.Howlett@oracle.com, akpm@linux-foundation.org Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, Wei Yang , "Liam R . Howlett" , Sidhartha Kumar , Lorenzo Stoakes Subject: [PATCH v5 4/5] maple_tree: refine mas_store_root() on storing NULL Date: Thu, 31 Oct 2024 23:16:26 +0000 Message-Id: <20241031231627.14316-5-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20241031231627.14316-1-richard.weiyang@gmail.com> References: <20241031231627.14316-1-richard.weiyang@gmail.com> X-Rspamd-Server: rspam10 X-Stat-Signature: ugrkxju71hxhnt6a71k8r18x9ru4gcfo X-Rspamd-Queue-Id: 492214001C X-Rspam-User: X-HE-Tag: 1730416581-192776 X-HE-Meta: U2FsdGVkX19dIjpQxAn1dqK28O2v1M5DDTn23CigAdXhJ02IOj6tmMTjHx3Fe770FDRLweb+d/XJTel1r5DOxTDtbjkCEEUC1EEIcolz+QxVf+vxzX/nwDRn7g5CmZ4w+PxB5+2toNWZgZ6ifJSxvip0zSDea4cpIZXsCzzzqEEpEAYacAQLtNe2ER0R3cmyrFXhlWN48TeEpfdqbrtsNu9I/pMWcPvPai3Gagso3L6Ls93HjLSXZwkxZqmLATZzIxd5mx3Z6ZA8nEzPn6FS2NQcLbcdDmhVVS6e2xmzgHUehU7vt8I9hosxk9scOz8pIAY5xYfqRd4cHNbz7KYzs0fLWW8Oenp91KV91prUwa5zH7l9sKgk31BT9ddfw61wBdpxjji3bv8tOoiav7j5uodnNzWH2f7EQbgSLp7zE6vrWWcK0ZP39kWftdupivUdrzsSAmOsX5Nho6pWpGESdaWpFU1VlYqahcAoedb6RnTmKVaE6/x22NU2r9bzjlIma/pWAlK/57l+LPcJYPO+xcCjZ95Zn3DkQseZhnsifnZKgFByZ6MP60x8sTMRHtv/d8sTOmTSsI1EjR8h1F4/nn5RRCzcE74cmONu4Y8JTtUWnSimCzgeFn0Qk1sBjD78CFV/MPrvfmvmx5WHwGwGbgijE+imk+MkhOFATfXF+CWXN4wKeQMLaH3KrE3YQNq1RV25HLJF1aEeK9GaPttpYXm1Pc8522F7k3xoCm+Pc/bOBXiuVxtcYh2U/t90m2xTavUsis2rlIPvFpZs6B7Lw5+9cHBcS3yiUMKVHMdsVxodhwD1K6CxzvDGxcjhdOmqp21E+qgZ8uD8zZQwgniXeAyV5S7qryqidJMDHgMs5ihp1u6izN+s3JbpE+hv1oiGO32ReKCF6dlLsEBoxZMY1XGkgDICzq/2tocVNL8M1VJcKHm3SBv/WdcQ/Wrgy9c997UqjrCK3CoCC7WMTM7 8ay7rjms SOKm9uu2V5QZ0vdj5rTf+YrRf0VRM1Wez2L7gOu/FRkT73tAs3N0omWZctDfmVpvzXIJlJAX+wn6aQtBEHaZNWlsbwDDw/4upN88asNixp7kfsPas4kbgWUOeXB/uP0JORPEFRdhUi0/CgQ2w/19Q+QZOnhuBhiES6vvN44VnEuRrfdnJRR668YddYIaIAFOm9KF+UbjwsT54Z0RJiDVWelon6947OEcKhsqPuN9FOsuP3JsqJsMpayzmNqKCdRys/N+2U33rEIHFQrVN6ckNtO5Nx67lMJ7Yv6En4OSSxVqGBlNJcJ4Q/xNj0ZLw+1Ztep3bz2Socmij4lzWWkB6ely0P0O3aWsix/vjP5eaRU8geFmaBp4s78x8tJfVBWdiVXMKhOnfJ/Akb9uwRHG86Y/2NTXTRD/LX2ZHQRqwKoeJmnsr8C4hMsf+XUAKQCg2hSxQunRG3lrU7KOgnLLL+N9hI+GRp6EcFnE4IFkxaT7/I+aZ292c/z3Ca6CyFL/ymsNZ 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: Currently, when storing NULL on mas_store_root(), the behavior could be improved. For example possible cases are: * store NULL at any range result a new node * store NULL at range [m, n] where m > 0 to a single entry tree result a new node with range [m, n] set to NULL * store NULL at range [m, n] where m > 0 to an empty tree result consecutive NULL slot * it allows for multiple NULL entries by expanding root to store NULLs to an empty tree This patch tries to improve in: * memory efficient by setting to empty tree instead of using a node * remove the possibility of consecutive NULL slot which will prohibit extended null in later operation Signed-off-by: Wei Yang CC: Liam R. Howlett CC: Sidhartha Kumar CC: Lorenzo Stoakes Reviewed-by: Liam R. Howlett --- v3: move change into mas_store_root() v4: add a comment and simplify the logic a little adjust the change log a little --- lib/maple_tree.c | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 4900f182e99d..d0ae808f3a14 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3447,9 +3447,20 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry) return; } +/* + * mas_store_root() - Storing value into root. + * @mas: The maple state + * @entry: The entry to store. + * + * There is no root node now and we are storing a value into the root - this + * function either assigns the pointer or expands into a node. + */ static inline void mas_store_root(struct ma_state *mas, void *entry) { - if (likely((mas->last != 0) || (mas->index != 0))) + if (!entry) { + if (!mas->index) + rcu_assign_pointer(mas->tree->ma_root, NULL); + } else if (likely((mas->last != 0) || (mas->index != 0))) mas_root_expand(mas, entry); else if (((unsigned long) (entry) & 3) == 2) mas_root_expand(mas, entry);