From patchwork Fri Oct 18 02:39:42 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13841028 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 450D2D3C53F for ; Fri, 18 Oct 2024 02:40:13 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D4A4C6B0093; Thu, 17 Oct 2024 22:40:12 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id CF9B56B0095; Thu, 17 Oct 2024 22:40:12 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id BC0CB6B0096; Thu, 17 Oct 2024 22:40:12 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 9C9746B0093 for ; Thu, 17 Oct 2024 22:40:12 -0400 (EDT) Received: from smtpin26.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 51A961C70A9 for ; Fri, 18 Oct 2024 02:39:59 +0000 (UTC) X-FDA: 82685168328.26.75F14D1 Received: from mail-ej1-f43.google.com (mail-ej1-f43.google.com [209.85.218.43]) by imf26.hostedemail.com (Postfix) with ESMTP id ADEA214000F for ; Fri, 18 Oct 2024 02:40:02 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=ez3KOF69; spf=pass (imf26.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.43 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=1729219162; 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=6NOQnU7l/vxZduKt4YJrTIL/mTO/1Bx4jBBaczXOYH4=; b=7GIRcDz6laHGQLg+Axjy1ZmO3OAQDdmYrfbaGf9teIQ6QcAZ6Xrjw6IQxAS73OBZjc6fz0 aQ/ac9absiqkhDPYqL6COvS4PvXlYcNhnMCoITmWYKwLD/5VzVSCqA9U84qKpKkswPbRjv aexMHlNj6I44Di14WQbx7/9/xUQEiVE= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=ez3KOF69; spf=pass (imf26.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.43 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729219162; a=rsa-sha256; cv=none; b=xDkwY6XXFKNKSfobylbOVc1EhxdGWlKFZCP3tG7Zkj976baBTq2lOGp5AoQmRI0PF7abns QTayjw84TXyTN5Cvms6nIyuOW90cgd6UsZi7wBKJFnylWoMeYPgymrgJ9yd56OJw8rF4rG G4GAcQ6J35Kd8672HK5FwqG+IeD6G3E= Received: by mail-ej1-f43.google.com with SMTP id a640c23a62f3a-a9a0474e70eso217153366b.0 for ; Thu, 17 Oct 2024 19:40:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729219209; x=1729824009; 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=6NOQnU7l/vxZduKt4YJrTIL/mTO/1Bx4jBBaczXOYH4=; b=ez3KOF699MQ55fPdAibdVRU/BqZ3h2WUmodhadP8OV2pQUaE+ozp+kH0Meu4vMzgOH WbD2f+ufb7MhB1UzclqJTIXLokB3ZhRnZ9ISaUQZ5PEQua5a5fBObPuw+cTgXpKGPI3h 9fLuZLz6pbDrclld8Zo/gWpVPKE6Qrt447rpQhx9oihm5WK3jpIcdwq83DH6AT/+d4D0 yGQQSxcmukoKiFfsOmIJSYHMV6rTo2sMG3kTIpRmn56QMm0NcoIMB4jJAd0JeL6pTyeZ a8vw/QLWqbQUqV5vEkGyGwaw3OlKoCJpMG8kbi2hz/yVWjygX8Xo4/r1cKjvPTN/LmtS vomw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729219209; x=1729824009; 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=6NOQnU7l/vxZduKt4YJrTIL/mTO/1Bx4jBBaczXOYH4=; b=v2bK716tGiZUwssVtX46Vsk6V8U3D0zQBi5+uk61p9KlabNiNpgIFc9e8Nie2uFM8a ASGk6HvC9ZhHJbppqYaKVwcTy7rX8oZcQiKYDz/46+ipIQW2/hTMrhe11EK1VPuraJSg qniL82xk992ZkVqHj/eES3enaSgAbC7+r06qjRXJKsiKY7aUbA1ytHn7o5AtJagf+0Z2 5kBl1Ggo3TErHXGkZ3WishuZGqJdbHHjnQBOSjHvNGy5Y2BDZ1pAk8q6GkVM/Tr7elOE SkAEbeZX5quTfw5kC9Ig4+Ktmq+omfWgoswDRV/osjxpaB4RYj35Cfz5xR10LBn2mFVa 6Ayw== X-Forwarded-Encrypted: i=1; AJvYcCXfj8pZ8bjTkv2FpK0dVsY2pc+IdVdSMyy2CFFaJG/BSHusE74LAZ1dT0gXjZQQTrQ3e5MalU6R3Q==@kvack.org X-Gm-Message-State: AOJu0YzRHnysLtnn3xjQhchhDuRUa8mmuIC9C+jRFx1AYQUeH62zEQRR jlWlT+dp4Gx2OpSihpIKAEOkD9sPCBoRSfQEDczEG6a96i/GGgTq X-Google-Smtp-Source: AGHT+IHcZZSRDhGOSRfEKtfaBUoyY6i5MzyoGnGZyCyxVrgYQoLDmxmMhvH6sNkCgDgHtkdlNOoCYw== X-Received: by 2002:a17:907:989:b0:a99:40e3:23e8 with SMTP id a640c23a62f3a-a9a69ccf8afmr62279866b.51.1729219208870; Thu, 17 Oct 2024 19:40:08 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9a68ad3ebbsm34661066b.50.2024.10.17.19.40.06 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Thu, 17 Oct 2024 19:40:07 -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 v3 4/5] maple_tree: refine mas_store_root() on storing NULL Date: Fri, 18 Oct 2024 02:39:42 +0000 Message-Id: <20241018023943.13860-5-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20241018023943.13860-1-richard.weiyang@gmail.com> References: <20241018023943.13860-1-richard.weiyang@gmail.com> X-Rspam-User: X-Stat-Signature: drmkioomsg1diop8a6uocj9hekqqi18w X-Rspamd-Queue-Id: ADEA214000F X-Rspamd-Server: rspam11 X-HE-Tag: 1729219202-208846 X-HE-Meta: U2FsdGVkX1/RwWGVDwcVk/stFIqg0LQ6TW2bpZFyerNA501T9L6Fu1Gb6C1NLEmDeKsRyAGCrlUeXRlK+w/hNg4p/kCeOZVIGzHTP19mZ/2Z/+Ozcyy9o33mAV4nOmrYxtSwp9HqfFubwZBfhFtdUm5HG6fMtDfAg1lk8ggG5zzL9u447zjDKY44OfrbGJJrZCvYXvLYRr8l0ccqjZ9Dx11lHvDij/e8bjWDdj6f06Y+6bVp78G7SX/1qJWiQXj2szpXfmdU91m01tX4hQl2cwuB9IagFfRavENt7dcu0PTH3ybyhWB37qKF45AQFtzsa/dId9v9a2dTWCsaASw+D5NreJXkL6P+24OKHT0iNPtnFM747XDuvVFvDCZBPMNAqgTEqIjEnQda308uIqWLN+lBPlgJPOgXtdBR3gdlG+/iMwJO+mybqluhpZkybDHfhU0WgradIaB50Yr14VUKs1GFPoOTeKN2i1Rayfs3NdmIbT5SHSCoHDTk6j6y0AVb5cZfIz9ch7kEgGKrPGnpADgQN1Z3Fpyc8tOa9CJROUwMASk5PePcO6ARtu7cJO5Gou+acj4y8vxPZyVZVa/TV22WsHQvflaa+vo7AM+zSEk+OnUYUgBQuohimMYE4Xr02JRcXGwcZOdtogJCsOi3MSXfQlQBVxfN8KTSGjxTSC5hsNkl/tkYjGrk89xfSYu9ouxt2RW5feJhK8frvNgFFuzq/UsVUASqvrmobQq2J8VilGwcIndNjFUkcb0Cw566EnZEE1mqRD+uvPWxTsKzoFINO99TxjCiYA8Fh5itca2M7MAMyIyx1H34oxM5r63yMyvX7QlbOsgKbnLAdfiR/NP+OYz06JVMR45jgnC3szf+/5xWuC1JhhP6FHBE4jJ46lawxIjsA5x0Dhwl/EGfyJ+oDxro/W0zZSEcG4TbJ4ZJ/7vEGAAdTnews6wBsqMILdsFjVaHgm/modtP4x1 KChJDfcE IJ1FbT6kf3DPB0Rpg7ZpWUfltLtwTZ7V0fp+BiWBkJI2qWcGhzkUbnGo7ZStlDK4ek0k02jzmkoRBDmbbs4pkT7Q12WPkKXAAZbsJ+ZspKxjPiCNnh37AX9T3YPybDUTN7SH8GY8jtkgj3648lu+zgzWanUyd0vBwYS8IIaY92XFHYL9AFobHqbLYAtYrRZZiRv8At1RGsr51PEMVbjKhV4CgiTfyhvJ9rcO0IU3lVsnsw0NEICtnYaMoTXsobM1smUn76VbC2tWOvqCYWNW3eRCZl9OFmYynF776IEB6k3lNvucwVmX5Q0e5joh0flq9RpVJfhEIf5NDcfNw8XeD3ajJGt2XLxAHZVsieNnvwxCRWmTFmB8FN7aLc9bDAareAubaA9SODk5nDAONC8htskbyBVfyxQMuydesL+VOdBinwSk6KlTt+4clxbn0rNXHEvdGUsi3Bwhv8NFhF4NIlmRO+3MCu6BJB2KlLlzJKd358fuwv8sWgl9GkVLGCyTaFgAq 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 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() --- lib/maple_tree.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index db8b89487c98..03fbee9880eb 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3439,7 +3439,11 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry) static inline void mas_store_root(struct ma_state *mas, void *entry) { - if (likely((mas->last != 0) || (mas->index != 0))) + if (!entry) { + void *contents = mas_root_locked(mas); + + if (!mas->index && contents) + 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);