From patchwork Sat Oct 19 02:37:15 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13842543 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 149FFD3E1AC for ; Sat, 19 Oct 2024 02:37:41 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8FE136B00A3; Fri, 18 Oct 2024 22:37:40 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 885BD6B00A5; Fri, 18 Oct 2024 22:37:40 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 6B1636B00A6; Fri, 18 Oct 2024 22:37:40 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 3F9C96B00A3 for ; Fri, 18 Oct 2024 22:37:40 -0400 (EDT) Received: from smtpin13.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 20ECA802A1 for ; Sat, 19 Oct 2024 02:37:29 +0000 (UTC) X-FDA: 82688790534.13.06B8479 Received: from mail-ed1-f50.google.com (mail-ed1-f50.google.com [209.85.208.50]) by imf21.hostedemail.com (Postfix) with ESMTP id 8BED71C0006 for ; Sat, 19 Oct 2024 02:37:15 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=QPUZeo7B; spf=pass (imf21.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.50 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=1729305311; 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=ILIvXac03VpEeGiJ70TROZ/Uw1YlHeBhyIST3O8KQTk=; b=Y/XCC2VSU9Dn0zL/lqo1LH6Kq0myI35Cuts/Q7vg0WI5vnt8/3B+hP7aBzXgkPW59dMxRU zqNvEbIu89omFaVdY0ftjMq8UU6yuWN9FDfspRaDl9Hd1dMDjhXD8H8Bx1iVWWmxcovciK V6B8RjRWemQvoHPnheS5EUMFC1xrClo= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729305311; a=rsa-sha256; cv=none; b=YnqlWt/8WtaJT9Udp3qPf2sM0A/kWl7fLDdWgY+6W8OmJL+aa2Jt7XdVCI2jHrDI6mV54K I4UTPr5W+OYQsuSiC7XK9lHIHXC+7x4NF3PEUS9jhX6Ddu9JwWDGZGQ84xTFPWMzqQxrA0 l2VUk6mKzAW9A9aa/7nupbJ0wGHy2gc= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=QPUZeo7B; spf=pass (imf21.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.50 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-ed1-f50.google.com with SMTP id 4fb4d7f45d1cf-5c962c3e97dso3077692a12.0 for ; Fri, 18 Oct 2024 19:37:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729305457; x=1729910257; 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=ILIvXac03VpEeGiJ70TROZ/Uw1YlHeBhyIST3O8KQTk=; b=QPUZeo7Bi72nzov2avNq9guyQHuLNy2V4OHcdRsPWQllJ0yQe40un3QAbIFWVZ2s83 ypOSuTIfSEo03vLEvEvyknWsYnr/EMf3NM0pSZ6xPcoUmUjZIwD+MQhQN70/pvYOJWbN U5XOZ9WaC2qAmvJx03+sT4s4KHBEMtxzCiJ68TPzDY2Va+UqktWHj/WgvqnuZ9Bh1kpK R42X23chHMx2k2kyR+jmpVLhW/bJLOMUKCY7jOaZ8bSdk6F8NK9FsDpRey/gKurK4TK7 MxH3zdbJcT+XJHpR3soKiLxie3J/+DzvkEqmtAbKt2F6bzLeLg3z8v86fuavfYIg9nwZ i2OA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729305457; x=1729910257; 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=ILIvXac03VpEeGiJ70TROZ/Uw1YlHeBhyIST3O8KQTk=; b=uOmktMIVQDSwZGrmLS7gciXkTwwe54BfbSD+KRUd7J+L6QiQUaixR0qASaFTHvfR+C 7cEHYu2jB9MaBwio64sRILUDrDyfQLzm5ll6211wpGp7PvSKHMa9SFfh6y/Jx4dCgyXy HDwyxOLjjapNee+L7A4HKzeNv4hJguOnRio6z+gic1SGJWiy+O4yGcdiJKSZ3yrbyuM/ ZwUqRkQqzVuzXlYBEQm8EoTcBo0K8176TlWlbaYlYMC0EX+vUrVGuIL3cZpHehiH6w/8 R/RUvceLeBSZAoMbN8jWm4JsB8VlunjBSH1THK8bnJ5e1m6tH7JLQsX1+2ZGm87/PgOF ED9g== X-Forwarded-Encrypted: i=1; AJvYcCWP2MH0V2afLKn0pZKXmyeq9nvbuZtvSEWZCiogf6bJFqRpJJILgEvTLBjH85gzg5gst95XyaXb5Q==@kvack.org X-Gm-Message-State: AOJu0YycH8F7aV0lUQmmp88+vd0CfCZkN2vljP4mOaP3IIzndBX2MsDL eac/UoStiyDjdJuiaawNjmcUhsPRZtvBNGL+sQONqHTRN772ht5Z X-Google-Smtp-Source: AGHT+IFlHjix7wS46i/6BDpKOsFLLemDZtu9UIE+/BGFSZx7YeAqH1r/3ADKC4uZTAVkOhIxOvQQLQ== X-Received: by 2002:a05:6402:51c7:b0:5c9:7e10:4fc5 with SMTP id 4fb4d7f45d1cf-5ca0ae874c7mr3116877a12.30.1729305456686; Fri, 18 Oct 2024 19:37:36 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5ca0b0e6d1dsm1329498a12.60.2024.10.18.19.37.33 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Fri, 18 Oct 2024 19:37:35 -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 v4 4/5] maple_tree: refine mas_store_root() on storing NULL Date: Sat, 19 Oct 2024 02:37:15 +0000 Message-Id: <20241019023716.4516-5-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20241019023716.4516-1-richard.weiyang@gmail.com> References: <20241019023716.4516-1-richard.weiyang@gmail.com> X-Rspam-User: X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 8BED71C0006 X-Stat-Signature: uddjwgexwhxtjysmqueapw1a17raqaqz X-HE-Tag: 1729305435-472251 X-HE-Meta: U2FsdGVkX1+agkcbGzv/nV76p3e/2CkSao0WdnOcskwdVm9AUMdvXCYGtrFUQ4CugV2TXknznfZD07sH5KGLPKMvLPzEanfFV7r/K00J3/hpVM1R02rIdHFneCJY4/xDw9tzCwN5EM7CEPtF78z0L/JF4wKUsCke8T5pD7G5Fr/B8Njy9qcukrQ7wD8783F2THZ2AuvoTJIRJ6aTvHDr5Wc70uOuu3Lq0busgOYLNqAQM8PgI5Tq9lwmKTOAs6+awviNbFXsK5EXzPdu/XwqhX5c4EN7Lcr1Z98jU3aylLdgC3tfs5Ll28kJGpMkJ2unNY1CxBLnsr1kbAxB+93PN2xqM6AP6ka6j1CaWn/dAlaimQvp0SB0VFhz0X+U4tWZa+qnH5BAkCiJAEeR6fDlTNvVtuAfBN2VS1YwTrdNZ8z2wOeKqDd+4tUVA5Enh/3Oi1QxbRyF3zfO7r0Igdf64dq2BYDVVh3D/KmaRP57Gyc0dH+rzaUVl/G5yr8Oc+lqbYYrMDDdWtrMDDsM/raDx3CYe+mZatYvoqfbG7YOOqRMfMnO2YlB79H2owwScomn4zYVnQ+SzF5msHl42K+V4Zpugh+5CorN8XlRt8fXPgSVpWSSlXZjPLXH/QNUe95hOJzq9oKgbRZLCX5e5YeXhSsCz44ZfDkMKUhEWso9qxmSQwea5Nq2ovxIia+Ed3uaYXuuNPtqfKhcyAnJPhjDVJncTGVgfONOGOwJ5Hxl9P4atIJpVyx2I7JGb1XWbiKAKnpHXwuPxsbvUbdqQc9AU0Uvvc1PTur0E4Z7EtGpebx+e7GqRCp67B96a7CgtBOjNtxy+Ad3dKNYSC8fftUyVLo/deETa8TW9l0vWx/dZX468jgQkyr9Dgq9VP9sShbQ1U1teaf+OFD9tpQwBUu7I5Xn2u2Kl7oFjusv1u9qQHMlXkEPbfHknU1n9Rrw/rt7JsXcdZtTK7F/syo8Z9s XXAT23zU 3e1z2NRXjfJWY83O8fZawd3fSU+frCCqbMZzcSrKtxBRjlylVhH8Hc+r/GEwyoZsZnu2YLZDfr1Rg6+9iF3jeq2zhsd2j+NIr+kR64CD/sASR1JFoJLahJdp2oMgQdWtSYMu+KLf/ccOmY9cKc3nsh6s2anTjg3Uol/Ej9FiTduVyyTC5jEsaeC8A4m/96oOUPPauwWCcFsmXARlgPt2DG3he72T40Y+NatE2nrHEnjp2mpdlXFPZJ2wTfjH78zm3F5Bpuys9swazjbVOaeRuZB1Mynih3oLRrKbOe1CbCv7mp/b4koTG2s7qxnhhnMxxTMKvqJvLuXIPswaR4JtTcE2GfCTbyqY+QlRp1KvnDOIWBzKZd0rOqfXzY9ea7OcbBpFYiD7nmX5l0WgAwUrzESmxUxC+2+X/3+H3mq9yEeNwJQxfM6FAYPTodVojQIJdMxopZI6s+pZmr+hvNWcMonF5hfHUNkn5FAqZYgRiUbyw1ek/JyCcgtKKnTjsOtbJcnv+ 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 --- 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 2226e77c00cb..1205a5208cfe 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3439,9 +3439,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);