From patchwork Thu Oct 17 13:46:06 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13840069 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 00C98D37495 for ; Thu, 17 Oct 2024 13:46:36 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id E706B6B008A; Thu, 17 Oct 2024 09:46:33 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id DF8EC6B0092; Thu, 17 Oct 2024 09:46:33 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C4B156B0093; Thu, 17 Oct 2024 09:46:33 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 9A2EF6B008A for ; Thu, 17 Oct 2024 09:46:33 -0400 (EDT) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 0B31016143F for ; Thu, 17 Oct 2024 13:46:21 +0000 (UTC) X-FDA: 82683218478.20.274B586 Received: from mail-ed1-f52.google.com (mail-ed1-f52.google.com [209.85.208.52]) by imf10.hostedemail.com (Postfix) with ESMTP id 15D80C0019 for ; Thu, 17 Oct 2024 13:46:26 +0000 (UTC) Authentication-Results: imf10.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=HkthxkUf; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf10.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729172758; a=rsa-sha256; cv=none; b=Gf3M5o0vSGt50DHL75YJ2+h0Q+QTQmxIPeRVsB7lBoYpzWZOY95eUqaSuNeTNMRBxxoLMq 9cUPAny2wwluqnw+3QAZCa+rAUB75gAQWjHKWhSONuELf9mhepSFa30sx245BkBfGi+4Dg 5bhTiC1ORQVl0rRDKgeVb9APn3b5HjA= ARC-Authentication-Results: i=1; imf10.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=HkthxkUf; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf10.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1729172758; 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=l4KlshdcAGBITRxoNc7cGIOi3SZuuj5B9eyadiG0Uzo=; b=B9ParPIB131eMuZ6XQFwQWSyxDI7ziCMFtXkvqOB8vgORxh9HBzuozZ0REDZyB50uc4zd+ 8uwe9etq8hQ3FXUyh7JBQJ0wS017Wj+2wemdT24lRiCpw2Y9nozqh/vb4MXDCNVDthIgzD twTJDfaRpFVV42jzTRucjFyXU2tJ+N4= Received: by mail-ed1-f52.google.com with SMTP id 4fb4d7f45d1cf-5c948c41edeso1218663a12.1 for ; Thu, 17 Oct 2024 06:46:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729172790; x=1729777590; 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=l4KlshdcAGBITRxoNc7cGIOi3SZuuj5B9eyadiG0Uzo=; b=HkthxkUfMvrzK4rqFEUNPJHdolTB7+LX5BeRo9OY0WI/uc99vESeJi3kzVIKLK9Gq7 2nbUgQwhw1jCk0lJFBsKL/D3WfPy+2rX9xx0jr9XlX4LZ5P0oUY/g2ARBHqJ9SuT0GDp o3d4lD0iz1Qj0DBTEi6s4QL0EiNHhcqQR4ZdAZocYWAZEo2zuajozqazBMLBerj4W3MM BHM0frWlGeyARCAP0aLXRnDLpN6GV7leoNV8SIUtF15BTtl2Nne0nF2BtmSXCh6HQAdV LxJEbKFVQRgj6x6hMnjpoeSYfXsCk+hHoetjiQMhhCAra0gqmKYvYwuw6wSb6DVskyrA Wd4Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729172790; x=1729777590; 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=l4KlshdcAGBITRxoNc7cGIOi3SZuuj5B9eyadiG0Uzo=; b=gjW22dhqxd8OMn5YU8d3FghhvN5Ctzz4LvDFEHHT/UA8XbBsInEIgeh85k9JvMlNk1 f3IonyRHSuYv0Lb4ssTo+UFVjllijJ6zHpRb+xJbc2yiNXtoxIYdNcfeZ3JTlZmXyut2 3zOICmQ2KM0tWM89hu8OdLBnkJ6K9ATbgp/bv+HEh2Xb9xdcs7LxwnlnBYUw5nlL2vwo i8Nyp3ByxxVk7So9L7BPgr5+PRGthpadakdN6K2L+dIyoM8OJ+U0pfhW1Ihz+M4i+O6c ljmLTXXLiyeeu/cD6PitSewmPAvl+xqP5ik8yJ8cuQ2wgDuANncBRQvR5kKrA+yR0++a zwag== X-Forwarded-Encrypted: i=1; AJvYcCUrsVHmqJacL/02zeQcjhSEQGPoEg6aDqFhRrNLKN5gPlLPe8IPHgYgXX1Uq6tnmkwaf0h1OOqkbg==@kvack.org X-Gm-Message-State: AOJu0YzoM9FVN5ig6v7YUmjeRsmyW3Am54QqBMDyKHFxNYB3e9zL1mRD rgk+gaB4hfaiXqRTzrDEyjfiOW3HTOMPVbXpmUP1eaF4LfO1B4SWRyBKT2gP X-Google-Smtp-Source: AGHT+IHImx1d1O/6cwAX3TWmEzp/CgNdlPdgMg6RM+qOfS/QWKac/K/5fKxRq3Y/S0iyB2UMwiuEdg== X-Received: by 2002:a05:6402:13c3:b0:5c9:2a8c:8961 with SMTP id 4fb4d7f45d1cf-5c948d48286mr18272009a12.22.1729172789814; Thu, 17 Oct 2024 06:46:29 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5c98d4f9dc2sm2787071a12.38.2024.10.17.06.46.28 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Thu, 17 Oct 2024 06:46:28 -0700 (PDT) From: Wei Yang To: akpm@linux-foundation.org, Liam.Howlett@oracle.com Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org, Wei Yang , "Liam R . Howlett" , Sidhartha Kumar , Lorenzo Stoakes Subject: [PATCH v2 4/5] maple_tree: refine mas_root_expand() on storing NULL Date: Thu, 17 Oct 2024 13:46:06 +0000 Message-Id: <20241017134607.30206-5-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20241017134607.30206-1-richard.weiyang@gmail.com> References: <20241017134607.30206-1-richard.weiyang@gmail.com> X-Rspam-User: X-Stat-Signature: b6s6dh6xanwwngrt5emtk3p1ym56uikh X-Rspamd-Queue-Id: 15D80C0019 X-Rspamd-Server: rspam02 X-HE-Tag: 1729172786-331491 X-HE-Meta: U2FsdGVkX1+Po1uJvJlJIgQLUkXpyd3NlUjgWAsPluSM36eMUKIjRZoZFjO9jShC+mRm8oCO1ODGGO0d281GNvB4QO7320ptiF6W/wm8Da3Vkvdka9Qm7U34QN8pKgNdX8vA0NiTC6uUaaitedam8eEjUcWV0+8xePLg/3mYYqmggssyajVzjXShNCnSSRcFizkxsRI8gHxLRWiLkjII236HiUMvZr8u80uDOBqZsDFQtWza5p6igr29fdVx1X8Q3BHD/pfqD25LrJPA9hbw34pv6F738MMluKfeWogLrBxAVc2idv9sHlc78zal2AGA4oy+NXQ0ySzVj7lMyAWhbpPTnOKRBWcu3odNFY8V4PQr1i8ER7GqXtOfjlLGGFX5f1slw8Oz6DgeFdyv6nq1uQYt5yaazSxq6t78Mh5qYYrc9mPr8wBSmHmrlDhhB1QvBBnj7mPraBinmCItvct6gzS9v+adzCWQBGmiclYVp51SfmxAP8t/Kf7l7PFgqPayuZmhoNia2B4Tag0j7NEKsKBKTAp4S5GILBFdEih+jQpumocwVOFSjXQGs5Ql1l5zmKqxrclT8NHzeaX5HYDkSj4aJsYROBE76fyGM66Il4Ia6p7rwAkWs5LOO1iL0StoQm6n4E6RZsl+h/bqxLFkEoizGn4yIVrFyQ+W0AJoP7rzCtGS6UmKYxqoX+ikyl3C8c7kbirydbet4HBPpBaVsAhYUCdhcf5azWZiwI23jD+KBIuuKWmftMxgjEK/OvlEUJf6fkbfYUjei1hRrETssYB0Bn0SeWmafbW+acLCVo9Ns7wq3kzzBCd9c41gosgCgxNL5ZJwuBvaxNXtwS4KJznbZe8ObvBzagF0w4vjIfUb9s2q+jDDMQsiCHrdaIb89kOfGtpSN3M3kxNJHr0MbF6/yPHLVrnTviY5UOUFUChpQ7zTILI+uS0CRmQRcKLGcxUr+8Ff/B7GpyIFQJz 7V+xLYpO eH69UyaOvY2TDUVVaossTUPHWXz/nUjqSVeFgwlR7MoF/E66Wm0fLP+A3SE/rTN8XngPkmdWICnOjyItXDshLrzXwP6l43+iFJ80hZM38ubQTVnstsOMYcGwd6w4djS5VlNIf19dGxc6OSnbIejd5jqMICI06hR9dW1OtG36Cr4gUeKaYRDehrBXXRf38nXfLNukw5+4VZO4VvG/etulbtvZlPhTe8T4rKzpOHEJa5+8jd77o0aWDMlJJ+0wC8A7Lg/SvuFm+udxlyBjcmwiD9+k83QM8zCkiSMAIplHDUtOBYUvG7evpH4hohKphixrqhUC7ZWN7Na6wtWU3VNJrQRoVH6JgnwMINSss/Y+tS8WM+FGR84GMpLQlv3Se2RYyRFx7AdCQJGPqgsagY+byosbIvI8xJ1PeF6kUOXnd8I9fQYFMTmBVY1TQiBhRIZ/E5CVaAdSnrmBVcThipIisdi+lv5zv/T1E0ndpW998AFoKI250A5xMdw0nzF0stSdSmj+g 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_root_expand(), 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 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 --- lib/maple_tree.c | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index a90c29156fe2..15d2124acc36 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3335,6 +3335,24 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry) unsigned long *pivots; int slot = 0; + if (!entry) { + /* + * We come here in two cases: + * 1. This is an empty tree + * 2. This is a single entry tree with range [0, 0] + * + * If this is an empty tree, the result should still be an + * empty tree no matter what the range is. + * + * If this is a single entry tree, we should set it to an + * empty tree if the range cover [0, 0]. Otherwise, we don't + * need to change it. + */ + if (!mas->index && contents) + rcu_assign_pointer(mas->tree->ma_root, NULL); + return; + } + node = mas_pop_node(mas); pivots = ma_pivots(node, type); slots = ma_slots(node, type);