From mboxrd@z Thu Jan 1 00:00:00 1970 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 093C9D3E195 for ; Sat, 19 Oct 2024 00:59:37 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 584776B009B; Fri, 18 Oct 2024 20:59:37 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 534276B00AE; Fri, 18 Oct 2024 20:59:37 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 3D5CF6B00AF; Fri, 18 Oct 2024 20:59:37 -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 1C26A6B009B for ; Fri, 18 Oct 2024 20:59:37 -0400 (EDT) Received: from smtpin13.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id BC7B2A043A for ; Sat, 19 Oct 2024 00:59:13 +0000 (UTC) X-FDA: 82688543448.13.9C1A208 Received: from mail-ej1-f41.google.com (mail-ej1-f41.google.com [209.85.218.41]) by imf06.hostedemail.com (Postfix) with ESMTP id 6FF3D180013 for ; Sat, 19 Oct 2024 00:59:26 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=bccR4W64; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf06.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.41 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729299540; a=rsa-sha256; cv=none; b=GK2oX7O0Wp2sUwfHKLk4BUZ/M0uWDpPmrXUoVnHGCAEVluYtd9ZX93hDBO6RUJtNBe1KfM RJjjPatLNg/8GS7oe3fJwrxfhxKBxxxZLtyWWMcgavtVdue5nV12MhdjW/+dHrqHe2KRwy 38uW/zPSaxHrEpEJNUh35H+Vl191lf8= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=bccR4W64; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf06.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.41 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=1729299540; h=from:from:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=ssmS0hVSKAFHfoJzMbHdDNw8Yqe+WswyQdDBVet6xxo=; b=Bx+MF8ODKqa0JfOwYHzjgxjqO0niAXsZ3Ggr5eE3QVrdjfuPvY75p3NqcufFS5Zy5VK16m 7HoWw3OQzkqwJFjP//xuqgWhyiPp8P69xNnwhKo/FLCCSdIC+kfmTT8HBxNmx28YR5D+Wr aWxlDpUSJFNrrCXH1GXmFciYWLZ4QH8= Received: by mail-ej1-f41.google.com with SMTP id a640c23a62f3a-a9a0474e70eso357613866b.0 for ; Fri, 18 Oct 2024 17:59:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729299573; x=1729904373; darn=kvack.org; h=user-agent:in-reply-to:content-disposition:mime-version:references :reply-to:message-id:subject:to:from:date:from:to:cc:subject:date :message-id:reply-to; bh=ssmS0hVSKAFHfoJzMbHdDNw8Yqe+WswyQdDBVet6xxo=; b=bccR4W64C6euSgxWr9Ap7VCeHNJX6tScZIbWZZjaD2Tl8ySrQFc7wP9y/dLx5sYkke zMmoziopg3XspG+wFwTuNk6kN0aJPQmz6m66kuLyWY4At99eIxDiRD5IEGJHkJ3hsVH/ Q3ITk4t6HEI+PEg5Z7vWfJZve7WZkFxt3FvQwCWVR+AcAvuAHSyAlmLHgfpHZrQdo/cy Or9pXjF2HSV0jm1GNbNAwLRJEmhF+h5vkBWd53FXBl79c/lAaiIhupW+nhXiYWge95aI 475NASqgAdRrr2sZx/YoddF8ltTPVdU/pD/3pFiSKKPRPYZrQQViHhUIGVSq1cCrHGcp 7FNA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729299573; x=1729904373; h=user-agent:in-reply-to:content-disposition:mime-version:references :reply-to:message-id:subject:to:from:date:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=ssmS0hVSKAFHfoJzMbHdDNw8Yqe+WswyQdDBVet6xxo=; b=V4zc6yePA1C+T2lif6gy9B6fHQmCmze5X4lxaVpJk73QCwWFYmaH3RR/diWGKt+NAu CYC/7fAZllF2AeoljJNt2enATnU8iVwel7ABfd2Nt4tnxyeCC2vRhpLnNhztLIYkL4IK 6NLmzeYyVK4UkXSql2LSNm2I5fHRP6eH06YBSg54b4LgalCo2aSxOOz3d9++Ja35Dttz sRLMBqqv0MwaOxrC9AOQlur1Nt6EkuK7TOzHqDwqKj4qjq5GeEhDApmkIJeqtxRi1+1c CTsDtWOZO6uoqpVgFddRJSQ37S+R+k4Nw+Fwl2zzgohz+gRYE5wJt608bMXe0PRcp7vh KLsw== X-Forwarded-Encrypted: i=1; AJvYcCXh1C8LXLmGUSG7GdG1XKiQVfqtWIJgjKyLZgWfjUXbk8Pcs9yyothWVMkjYh/U7qYxX4H/uao6bQ==@kvack.org X-Gm-Message-State: AOJu0Yw+16U1kE7+z2f46yl/ig2O4IsFthycmJnDV/9Xrz9pNEdrcRKa cLVi4oL9XQpCW1Esw1mCpONURA0dypuFu3b8xvM6kEFoAa3pyA49 X-Google-Smtp-Source: AGHT+IHGCBgMewlbP+6HCWS9NwEA+DvzRKyiNL+W3f89XKPU2SVGXYc+HrsGJpk2AzkFOiAkJNjAmw== X-Received: by 2002:a17:907:94d2:b0:a99:3318:e7c3 with SMTP id a640c23a62f3a-a9a69cccefbmr390605166b.43.1729299572940; Fri, 18 Oct 2024 17:59:32 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9a68c2e62fsm153589666b.220.2024.10.18.17.59.30 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Fri, 18 Oct 2024 17:59:31 -0700 (PDT) Date: Sat, 19 Oct 2024 00:59:29 +0000 From: Wei Yang To: "Liam R. Howlett" , Wei Yang , akpm@linux-foundation.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, Sidhartha Kumar , Lorenzo Stoakes Subject: Re: [PATCH v3 4/5] maple_tree: refine mas_store_root() on storing NULL Message-ID: <20241019005929.ed5wuhbvdhtfqk2o@master> Reply-To: Wei Yang References: <20241018023943.13860-1-richard.weiyang@gmail.com> <20241018023943.13860-5-richard.weiyang@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: NeoMutt/20170113 (1.7.2) X-Rspam-User: X-Stat-Signature: mj3uzrsddbf8io8h31ehzitez5me5asp X-Rspamd-Queue-Id: 6FF3D180013 X-Rspamd-Server: rspam02 X-HE-Tag: 1729299566-140059 X-HE-Meta: U2FsdGVkX184Kf2l8TyPLqHuKim6lKplR04AWfn/AB5OyEwah20c5lIOJ9g80KD3/OSU6F3dXWKrnn/4cvChcS9oC0ZblSfGAK7FgSkyT+OH+3f1WPTt5RElIqHalKIcwj3JURCcMby+tczZvEh1NkHxyz5jP1D4gVx6Cn+Ul8/rPZzxTyLAMGVzA+4Qrrjoe7gniTS5yBujmATF6QlgwrgAc+3Mvk9oKjwgyoHkAIBF87ScNSs/PklxX/Z2qpGaBVx7rZtU8iwmNQIIbmhHC4zkfWMP9Pygw4YeQhC+SoVnaERzw3ty7fNuvHspgowuwpHexb84rUuzq2ihC3VFvaznYib+3FKFjz2cbL+LRHuP5JiBRmJaytr/7gpgOqBHguu8vIgEVecjJPGYB5ucqz2cr8WYSSL11Sk8qvgE1iQrQLVinS98x9UhWjYA4qmCm1OlBhNVXh5KCZbHV2NMnST4DObbzgN7fJ0FTyc7PGiQC/ICHHq52VANIf6b56lVSn3WB9m4WRoY2hxAsiKwK+IkgrTs6vKnGCPsacpGTUgNLSkMNjsg/vlUjdPskjskaByMKf/gdDOuqyis1x/ffgvauCktn16cA5XglmSs+5Eys2N7RjNnHjdOoSxIOO+TTSzUtqqI7/1MT1L7xim01P6uZ3tHHG2dsBaxl1p0MXF6LUNzZ42K/VT7Yj64oUW9rLkv6Bmwk8ahoaK0a63J6m31TCzAPbmKmStxVb69ix7Fps1tZLI7tX47MsXahaLDj+Z7nfUE+BwgaOEqGW9ZLcXLMcKfvHORaX6gcEdCZfSFWKnie6Unzm8VQPfLTf496mr1pmtYeC+DPY8IT3bwaKTy2GDbCvPpxiQuOlk1EpphD298nHYxIuMfn39+dCiUGHhv6ohockLxQ5125mA4j5gSGWAfiMRZtiIFjB6+Arc5MZkqVLeHzUOJOunM3t8GLi2gd39j8k5IsXUX4mq iL6ARycv bhD+9vspLJ54z10WcxbZYrgJCDOKDdDkr0OzALTEBpOCUc7dZYs/52RaSYFaagdJ6Et0hQe/bDwcZWTWcc8U2RDoUQeWcchqow27gVOvQM6NyhEF/JXVYqYMNckljgpVhq2S9L9U4pM8fY+/JR4jsz77gH0nR/g/KigSd5+O6FnlftfbX96ZGSdR3AlSLUmfWFmdzSd4BDhEWv9wdJCt/WZBI4DFuR6yz00vji+dhGq4wf5AHbiQDsgxVoIwXl4F/685Bs30pyreRK2LyMCje9xxSq77IgPiRoZKFox1ouWd4To+JC9oIsopAx+QTMeJgeySBpTgif3tu6Qo5yPfzpEJaGNMxpM/WJdgazu4E5MNYdLaOZ3CFOVDTeNY1sckuJ0OrErNGxb+09lyPEFMzEXvr451kLNKHQm3KJny01iRcSJRFxLKFUOqxLvXMwOgqWmX3e6hJJPKEM+No44W79thEQoysBH7nAb4K5DQo1Nh40L66NKZpWF1TuBlbA2NB3QAPVAVBFzrIzXnd1cbAwFMQp9W3G4u41Fy+x+FeaD97K8nKt5Knam4Uq5/K7Xyd7/B45yDgUU9dckw/2cvaONGGnkF3tzukZ5EpOQgxHC261Adq5CP7uMfOXGR5VKfr7N4tOojkm1WnqWctu9HBDzIQ5+etCLwhgee6QDfMpzufWpAcc9Jay+OsbDyDJHfYQ10brcTYzAcgSMrRw2KMtIIF+w== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000271, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: On Fri, Oct 18, 2024 at 02:12:08PM -0400, Liam R. Howlett wrote: >* Liam R. Howlett [241018 14:00]: >> * Liam R. Howlett [241018 13:57]: >> > * Wei Yang [241017 22:40]: >> > > 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 >> > >> > I don't understand this. Do we actually store consecutive NULLs now? >> > >> > This is a very odd change log for fixing an optimisation. Maybe start >> > by explaining how we end up with a node with a single value now, then >> > state how this code changes that? >> > Let me reply all at here. We may have some cases to result in consecutive NULL slots now. For example, we store NULL at range [3, 10] to an empty tree. maple_tree(0x7fff2b797170) flags 5, height 1 root 0x615000000d0e 0-18446744073709551615: node 0x615000000d00 depth 0 type 1 parent 0x7fff2b797171 contents: (nil) 2 (nil) 10 (nil) 18446744073709551615 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 0x2 0-2: (nil) 3-10: (nil) 11-18446744073709551615: (nil) Or we first store an element to [0, 0] and then store NULL at range [2, 5] maple_tree(0x7fff2b797170) flags 5, height 1 root 0x61500000150e 0-18446744073709551615: node 0x615000001500 depth 0 type 1 parent 0x7fff2b797171 contents: 0x7fff2b797000 0 (nil) 1 (nil) 5 (nil) 18446744073709551615 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 0x3 0: 0x7fff2b797000 1: (nil) 2-5: (nil) 6-18446744073709551615: (nil) These are the cases to be checked in new test cases in patch 5. Maybe we can put this examples in change log for clarifying? >> > > >> > > 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); >> > >> > You are changing what used to handle any range that wasn't 0 to handle >> > storing NULL. >> > >> > This seems really broken. > >I understand now. You don't need to get the contents though > >if (!mas->index && mas_is_ptr(mas)) will work > >But it's probably faster to just assign the NULL and not check anything. > We should at least check the new range cover [0, 0]. Otherwise it will overwrite it if it is originally a single entry tree. This works fine: if (!mas->index) rcu_assign_pointer(mas->tree->ma_root, NULL); I would change to this, if you are ok with it. >> > >> > > + } else if (likely((mas->last != 0) || (mas->index != 0))) >> > >> > Isn't this exactly what you have above in the if statement? >> >> Oh, I see. It's the same as the line you deleted above. >> >> > >> > > mas_root_expand(mas, entry); >> > > else if (((unsigned long) (entry) & 3) == 2) >> > > mas_root_expand(mas, entry); >> > > -- >> > > 2.34.1 >> > > -- Wei Yang Help you, Help me