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 BF27CD3E1AC for ; Sat, 19 Oct 2024 02:38:34 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4698B8D0002; Fri, 18 Oct 2024 22:38:34 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 3F2A08D0001; Fri, 18 Oct 2024 22:38:34 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 26C658D0002; Fri, 18 Oct 2024 22:38:34 -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 0521B8D0001 for ; Fri, 18 Oct 2024 22:38:33 -0400 (EDT) Received: from smtpin26.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 5D74A140642 for ; Sat, 19 Oct 2024 02:38:20 +0000 (UTC) X-FDA: 82688792928.26.5B95528 Received: from mail-ed1-f53.google.com (mail-ed1-f53.google.com [209.85.208.53]) by imf05.hostedemail.com (Postfix) with ESMTP id 2C773100009 for ; Sat, 19 Oct 2024 02:38:08 +0000 (UTC) Authentication-Results: imf05.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=V4rvvGBh; spf=pass (imf05.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.53 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=1729305364; 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=bt1asNcqS3yesOsf9Qnyug06XSMVhZj2Zqpuq22hNfY=; b=ZNbtxb0CzwVfBdPmsTRfYpmgKP8h0/V6sb8v3qr/b5C3kdM54ZTyNShxtr3Z9a9EbJ7/Yu 41Nfus4JUlGkGqNCo6QzcTVtQR0P9i1Fg0lm7Thx+0jHHWldkDkPon9L5qJ/+Ocqzw26qj GhUgTSZlw6LaFksryKLVRVRydUc+KdU= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729305364; a=rsa-sha256; cv=none; b=bFgD2K8mFG8fIWl2lv350fHTEt4yYOAe2RKBCuFrz6uv8V+l02fOxTNtul1ZqjjWHd40kR wbmIathLcXn151Lw5J5pqeGRNf4bEMhyu/XhFNoBoT5PCpNdDxB2UgGOuQnem8OystUu47 d4JpVk/SV1qRVqhkhN8I1CDveyVYt6g= ARC-Authentication-Results: i=1; imf05.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=V4rvvGBh; spf=pass (imf05.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.53 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-ed1-f53.google.com with SMTP id 4fb4d7f45d1cf-5c9552d02e6so3160187a12.2 for ; Fri, 18 Oct 2024 19:38:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729305510; x=1729910310; 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=bt1asNcqS3yesOsf9Qnyug06XSMVhZj2Zqpuq22hNfY=; b=V4rvvGBhLpD7oqLFyJZqbculKBrFVkpV6l01iGweLocVyLWBR2hiI87c4UZo8lByXz bB83NHGSDHfpSPxq6Pr6yblsyqa/nF8M9Vs7hODNl3nJ1V7O+6uhMJ4PcEtke2m61Nxu PMvBAEKxir9gofo6JirIa8Jlgk/B/FYVOYqzkmOgTXgnyeoujxpJbfOCoIyBJesvqSnj /cz7aizf6sfjSvIBs6s7rNGcMeE0PimSLJgY/CtdybsP7EpreOSj7dTyCj71lUlr76GK 0JrlqhbJjKSDyLIfS9gDBnkock0qBh0bo/rqv2Fj6dlppRLYyq9Q0+qvnTFWyHpgpJkb z6SQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729305510; x=1729910310; 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=bt1asNcqS3yesOsf9Qnyug06XSMVhZj2Zqpuq22hNfY=; b=U97TAu8uQ43QPYJArP/70dSh1E8nMuPFbc64b5UHTYJZ0kj3yNqIu6KP+jdv6k2ZEs eVnPyc0CM2EkHkkX0rJE4kX5gwEmDgObKvgfF2YOMsMDj+wq7htvXtiudDaT2kKuN0d7 Q8U3v1umhGAz+IPAVaelOZGcAPAWl7iwL4CMPzxEpn21NtjEGRYP1t/d4ojOUhfxXRqq CeF3/3DxBRBNMzVPEHf4/6cj0+dvzeSWQpsNmMRKx1sfGLKV3uupH3Nef+XkTT2rEku1 R6LY4En1TsW/aiPk2n8q+p14VWcn647PyDgyYVVj2DJcSY/wmHlj+o5JKnNC0nbcHv9N 00rg== X-Forwarded-Encrypted: i=1; AJvYcCWomvJc+ZMYHf34FOZi2xfid3tV9aiXDAoacvdzE2Gh7I3zyi+MP9fxFp4EclnqjVDLg7y1delYLA==@kvack.org X-Gm-Message-State: AOJu0Ywrs5wuQlnExMB5h2mbDOdmf2PWwUlKbn8hv+YUXoqleEQM78p/ uYeUFwk2raUm0sFdW4fbXu5tSUERwl2eu6UI7ym7WboSkJcvpQCX X-Google-Smtp-Source: AGHT+IFwwVxXHEHDxf8gVX5JhId326uj7MVRG+ChkS8GK/EaGRlzebtH85iRTRKwx3CvkekUocoNzg== X-Received: by 2002:a17:906:c113:b0:a9a:1092:b10d with SMTP id a640c23a62f3a-a9a69b7af5dmr384190666b.33.1729305510030; Fri, 18 Oct 2024 19:38:30 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a9a68bf4141sm162958766b.148.2024.10.18.19.38.27 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Fri, 18 Oct 2024 19:38:28 -0700 (PDT) Date: Sat, 19 Oct 2024 02:38:26 +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: <20241019023826.67jn4khvein72343@master> Reply-To: Wei Yang References: <20241018023943.13860-1-richard.weiyang@gmail.com> <20241018023943.13860-5-richard.weiyang@gmail.com> <20241019005929.ed5wuhbvdhtfqk2o@master> 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-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 2C773100009 X-Stat-Signature: buhgcai3xokwadezyr3zznhupih4w4m7 X-HE-Tag: 1729305488-168383 X-HE-Meta: U2FsdGVkX1+b+WmQx+ruPkkf5fJlxjeKde0UlFSmLhe2M0ifTrLvY84Bo3geKw/VDBPCXUPmzI7wA/LKzQc96+yNvN4/ySPjHkV9Qy9AijgDXh2wxZ7ZHN1Qx1TbDKeSzcyJZ0EQ7nZxjpHimuG6LITrxSnB00Gqvg3HiGBu4YT8XVcBDV4C3ZNpweiXNEg4hMWLESF5KQGPHhHQ2S+yU0+EyLGxFTPdg7AEJB332PAw5LJu81g6zr7MHO/89jMy/d/YohvMZ7n5xWxXljoK1teW5/UjIyYpA3dP1U9FvaidzTajJsyHrGdc7psT02qyS93R4EvOGtBY4vHVYQzIrCmhAcS7r4klMXTKJ4NEIGsKHFNepf243k1RoxOaotITQ3uAg9v3jRvGh/29eVVmh1sLjxWZ29Gg8Qfi+e4ZDPgxVfWwcc9PNDjPctwPSQIYGuVS7IM2CAwpTRou0TP1DNPSB2F7Qk2gt5/M/8xmsSFvNNB6jxryw5auMXP+IvGkP2IbZY4/Bhy5zLsGVL7s3ywPuHHQm5sS4rDMudkKjdPrcLfpgpxwO4F6jAJnGgMotPxY2MKoVphYxJ0WI6Omn2nBwdmCdniXD4Lj7ZH/FdFl2ny2uGq07cqFwzmC9BDfSiAZQUzUg0hLXLTuWyznftGDIt5lDDE+jtARwbG4FayE/vBmN4aBlg/03ZE0vS9iasVdaA9PBfF33gO3YfeTzA4pCXPywF3j/itKyi+QQmNUUlJ7kqQuXDHx9OiXUxHt4hcscvvrr7PfR3yvu+9y4+70Fs9bHdNJxMCP/GfdQao5myRNfpt76f4mvWgQWoEbO1jOsVuBt+Xpb+NwPiuj0QgZct82qo/hS6UBvpc1jcREeG5/cCg+5uLyIsu6EP1QuThSo6NJzYem5LgbJRsCWfqwKS83Ddl9rZ+qFdSJD+cloUQg9k6UhfWdur2bwPPmuw6TGP3AjeILX67pYud DC7ODuD0 rfW/Na+LcWD1Fg9uzVt2Tpn9J+namVNfPcOGkIb5KKH0z4ELWWUnjM5+rleMnEtZalAwOqShjNhtGDA2UXzwlopjoUVcsEvqrTFXqHgYRnQh2qJa+Q+sHmtUn3io1eod0C0tdcnIoMGQ/mCDlo2oBN3tPcz/2+m8EiR9SKIoLIes7a8oczllbPM+vMt4ll80IbZvB1Clgx59Oct99bNuvvZuYxwAWjCGEJThcS99/ZMehj3mBqtPEpLGZklQOqOD3j+Zv5uMSwE3Uw5menhrXD49UjDm5qNIPfthifeFh3vft0PUjF6TQ8RNYXRUIe7xxWxa2R9jqp1AxiIBF4vWkcttijU19vj+J1dbPac/I5mqJMpg0z5WV5oB5t1vEKnLiniBmvXxkY1akdS3xMC1x5tAEXRfLdCMH+jqCIiJH4I6zi7e1xG5s3BAKbUdeDedkvIhBp+9RFNndLIdy28+N9/8h3IzWkrnVeDXaZ71FnP2c/Pi7v7EMZrFAhcM0FA9WNqFXtCDMucLnbuzW9FRNdY3BXZGfef/EEIDqYYpvpotjD44CLdzj2tO28rhB4FQbCOhaGXrtKlng9hIoBNwZNH5xCZulrqzJfKHSOwgswvYXXnJqctKtMmhCChY2dvFOZBXxwni0rMvEBuMFbMovm1VWru5d/SBZz6UMObhTy+5jHrz/XiYuERS67ixVCc+HTu0aRD9WmsoGl7Dy2LsTQufp4A== 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: On Fri, Oct 18, 2024 at 09:55:53PM -0400, Liam R. Howlett wrote: >* Wei Yang [241018 20:59]: >> 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. > >Oh. This needs to be backported. > >> >> Maybe we can put this examples in change log for clarifying? > >No, state that mas_store_root() allows for multiple NULL entries by >expanding root to store NULLs to an empty tree. > > >> >> >> > > >> >> > > 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. > >This makes sense. Maybe we need a comment about what mas_store_root() >means? That is, there is no root node and we are storing a value into >the root - this function either assigns the pointer or expands into a >node. > >Then when people see the above, we can say either we are storing NULL to >an existing NULL or overwriting an value at 0, so just write it if it's >overwriting index 0. > I have spin another round. If I miss or misunderstand you, just let me know. -- Wei Yang Help you, Help me