Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Mon, 31 Jul 2023 12:48:54 -0400
From:   "Liam R. Howlett" <Liam.Howlett@Oracle.com>
To:     Peng Zhang <zhangpeng.00@bytedance.com>
Cc:     avagin@gmail.com, npiggin@gmail.com,
        mathieu.desnoyers@efficios.com, peterz@infradead.org,
        michael.christie@oracle.com, surenb@google.com, brauner@kernel.org,
        willy@infradead.org, akpm@linux-foundation.org, corbet@lwn.net,
        linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org,
        linux-mm@kvack.org, linux-doc@vger.kernel.org
Subject: Re: [PATCH 06/11] maple_tree: Introduce mas_replace_entry() to
 directly replace an entry
Message-ID: <20230731164854.vbndc2z2mqpw53in@revolver>
Mail-Followup-To: "Liam R. Howlett" <Liam.Howlett@Oracle.com>,
        Peng Zhang <zhangpeng.00@bytedance.com>, avagin@gmail.com,
        npiggin@gmail.com, mathieu.desnoyers@efficios.com,
        peterz@infradead.org, michael.christie@oracle.com,
        surenb@google.com, brauner@kernel.org, willy@infradead.org,
        akpm@linux-foundation.org, corbet@lwn.net,
        linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org,
        linux-mm@kvack.org, linux-doc@vger.kernel.org
References: <20230726080916.17454-1-zhangpeng.00@bytedance.com>
 <20230726080916.17454-7-zhangpeng.00@bytedance.com>
 <20230726160843.hpl4razxiikqbuxy@revolver>
 <20aab1af-c183-db94-90d7-5e5425e3fd80@bytedance.com>
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
In-Reply-To: <20aab1af-c183-db94-90d7-5e5425e3fd80@bytedance.com>
User-Agent: NeoMutt/20220429
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?VDNFYmQ5cDRXNUVNUnlwUnhMYmdjamkvS0xJY09MZG9FTDB3RG5NSy9ZL1lU?=
 =?utf-8?B?OThtYU1TSmdGVE9CWlloZzMzcmQxZkUzSVNmOTVWUXdhRnFqNHB4aElwTlNC?=
 =?utf-8?B?SERYbWN3b3M4SFN1enBnbWxGbXRMT1pWUXBST0o4N1lpUXh3NVVyOTlEd0Ft?=
 =?utf-8?B?WjNxZUNZVllhOTdsNXI5dlplaFlnSmNMK3lXelBWNnNWRjVPUDE1NHZ6VWRF?=
 =?utf-8?B?ejhFRzEyTlZCMFJDRTcxRTY5d3Z2NFBYT012bXJpblF6ZmMwZWQrVUVnVjJN?=
 =?utf-8?B?SmlWOTEzd1Q2SlpLaUtRLy9oNUVvNzBmMjlVMytIRWJJMjRGaEc5ODEzUGdB?=
 =?utf-8?B?NlNIalJnTUl3cEd2WThFTXhveGtPZzc0ekZ0eEFjSS82VzFwcnNWZ2MzVkJC?=
 =?utf-8?B?YVdsR2tzQTlMQkYrZkZrS0txVVlPTTNKUFdvSWFoRnhobVVadDVQUXQzU084?=
 =?utf-8?B?MGFGcDFDdmJVaEVJL0xja0V2YnNVVzc1MTNoR29leWJGN290Q1JGZ3NXN282?=
 =?utf-8?B?Tm1Jc3JaU1plSFVpTTBpSVZCRHFjYXY3R3hZKzJaS3dVWkI0S0NFMCsvR2pi?=
 =?utf-8?B?QXN4WDlBQm5KdmZaaEpLdmFxQldBdXU4SjZPV1ZINTZ4WkV4QktaUkpuK3Zu?=
 =?utf-8?B?MEsyTVZRZ1BpSzJWaTh3S2w2ckc0aGZud2ZDN0VISklZWUt2RnZ5WjFOL3F6?=
 =?utf-8?B?NGY0M3ZXc3BlWWRPQStzbkZjYUFGd2xIRGF4cHZpRFV6WC9DQStZWkZZaXo2?=
 =?utf-8?B?MGlodTRNSDhNaG5ieC82MFpWcStoQVNoNmREU2lRYTM1aDJlOVRXT2crYUVy?=
 =?utf-8?B?elkzdjQyUXFMd3JQaWt4VE01Yml1bUt1VHM3cVg4WUdQelJWM1JxMjlsS1pr?=
 =?utf-8?B?bCtzK2Q0MkdyZjVTTk1YYmJNZS85NXFYRGt0TEVybDJGQXRKSEwwNUFhWHRP?=
 =?utf-8?B?ZUNKNTdYNiswSVUyalNNNDNrSGxSV0pUNTg3eFNyTW5ZSG5GNTFWMnVDejBt?=
 =?utf-8?B?dlF6U1ZXZ2VWNnhJK0lpMlZpeHZiMy9LMWlKYVIrcERxdUp0MmM3Y2dpRWhi?=
 =?utf-8?B?U3VPS0NHczE0SFlaMkNCYVdrMENHdzcwdW1XQnhWaytrVkRnR3lDcHQ4S09W?=
 =?utf-8?B?bVhQdUgwUTJlZU5idFVxa0RvL3FkRmtYWHdZdXZZcTVVbDFNQnJIbFhENXJY?=
 =?utf-8?B?SEdmNzhscWZPSnlTb1g3R3ZJdW5rMU1UU3FLQXp5WFJESTgyUXc3cHVWS250?=
 =?utf-8?B?M2cvS3FhanpDeGJJbk1LWmJHVkY3ZUFBcklDYnkrcVN2RWVwdDk1UTgrc1Y5?=
 =?utf-8?B?K0VCM2VCbVFKajdydUUzYm1EaExzdnRYMFF4amVNV0tNMW1WeVpNamJZZW9X?=
 =?utf-8?B?T1JWZTZJQ2wyRXlrN0ZaaHZyclBCeFBINUcvSzd1S0lMbjFpM0krcFhuVldt?=
 =?utf-8?B?OTViZmpQWVFOMjlCUFpwOG9jbTlJckQyVVY5WWxIMkhNcXB0dllPdWdDTVh2?=
 =?utf-8?B?cW5uNU1vL0wrcE9hTW5tY2d6RXFvUVF3TWtGOXM0L3lMUEtoRkFROWtUTDk3?=
 =?utf-8?B?bHY4WG51UmVvUmdyVHN3K005MDJnQmx3bzhDcW9CVktpR3NNdXQvdS9EeEg3?=
 =?utf-8?B?aFhoMUgvUmszVTB5YVlFRWtVTTZQSzFBb082Q3lKS3Z6djBMUm14VTFTaTR6?=
 =?utf-8?B?V1VYS3FPdXVnaERsNWgzN1hEb1RUUm9HRDg0ck1qRnBZZWVHa3NBNDB1WmFp?=
 =?utf-8?B?blJJRlFNM3lBVFl2NnRrcXI4cGhMV3g2c3Vnbm0zM1JseCtjN2VGVjg0MHZG?=
 =?utf-8?B?U1JRMGJaV3U2MFp5bVZQbVAyaU1QSE9oTEtDU3VGS0JRbGJPbmViVHcrdnlH?=
 =?utf-8?B?bEZJS25pTm50UGpmQUI0OXVaaFNnTUdoejlseGZnNHpWZG1BWFFVZzd3ZjRr?=
 =?utf-8?B?d2NXLytJOEJRNWRxZG1mZDVnNU51dXZtb0wzaHFzOXd0TzJndmpMYWVob0Zm?=
 =?utf-8?B?SSs4QTZBdlBZOXUyczJldUI0UHpsVUV5OTQzUVAwbTFVdFd1aG9wZnNja05H?=
 =?utf-8?B?cWVyeWxGVGozK29NZGExcjRNTkh6WStMY3VvQ2l1SDRwWURPUTRCYTI4QUlU?=
 =?utf-8?B?WHVSbk0vRzZuMjNKT0J1MzRXUGczVXpJTmx6enJEd1dSd21XcnlxQmxONVRz?=
 =?utf-8?B?MXc9PQ==?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?utf-8?B?YVc0VkhqeDJyUlpDMVVIbVVJUWt5TGU2Nnh6alFXY3Rjdnl1ajBsam0wdGlT?=
 =?utf-8?B?RlpvaFByVlYvdFVhR2N1bElnVnYwOWhkRlFQTVV1dS8xUzRXeEhPSVB4YTc2?=
 =?utf-8?B?YmovRk5HM0JZZzk4NkI2KzQ5L1JXbGRadmMzYTFiUlBqaE5xUXRvNnpOWkt6?=
 =?utf-8?B?cDBJbTA0SGd5OE8yUHA0ZS81dnpwYno2b2lKcXBTT0NDNG4yVStBT3RJTWd2?=
 =?utf-8?B?N2dIdjJpVUk0Vk42K3BqdDNTaUlYa2oxV2lZWEladkFiaWtlNWsyeVhNaVBJ?=
 =?utf-8?B?bHM1T1Z4OTgrdTJCRVdzTGJvbWZiWmZBcklyN0JDVnpsQ0lrMEJhMVo4OW5o?=
 =?utf-8?B?clpGQVU3cWJLSG15d3dXQjRPbFkvVTBwMElSTVZRM3k5MnBpMVcrTHo0SDhW?=
 =?utf-8?B?eFFoVlFaeVgvR0VhbFlSbFhYYVNTb1VNYk03akZnZGpJK0VzVnBJbWxUQSsv?=
 =?utf-8?B?RGxOOEhWT1NRNy9XZkhaMUVZV0ZWTjZwUEN3cUNyZFlSTU5TZG5mZFVYM1FB?=
 =?utf-8?B?RzVJZHc3R0ZsajhxVGVSckt4K1ZtRmQ1WXE1RWkvZzZ0WnBvR3FQY0tzMUVC?=
 =?utf-8?B?Q0RsRGZzL2NhWkRTL2RKNm80NlJ3NTRld0w1bEJPaXVTamM5K0FRTVh1N0M1?=
 =?utf-8?B?SUk2ZFkzWGJxRVppTXJmYjAwV2pPZlBqMWpqR1ppLzl4YVljazNuUFlzTWR0?=
 =?utf-8?B?NEMxMkErR3I1M1JiWlplekhka3N6YXpEQ1FFMnEwQTR5K01IaUROc1NHNjhF?=
 =?utf-8?B?aUlkUXhDcklqWjJZU0FjZVphL3lGZno4eExnbkJaOWhlaDR2REN4ejBUOGc4?=
 =?utf-8?B?K25YeW5JdDdHOE9zRGs1eklNQXNSNjcrRndiZjFWZFV6c21RMjBHT2Y5VDY5?=
 =?utf-8?B?a2JWYlFpNko1ZGxIbGN4STNIbjhEVzV4Zi9zUGJHUG1DaEF5a2o5Z1p3ejcx?=
 =?utf-8?B?ZDlZcjRWUDlYd05CRnRxOUR4MUZkcU03NWNpeFVJVWJ6Z1duOVVQWG5kZGVi?=
 =?utf-8?B?RVhBQittc1dwZEZLdVlqZ1BmZ29SRXc1aU0zdzNQWHdERFlEeGxNbDBuWjFa?=
 =?utf-8?B?N2twbEdNOFRHbUFGY3Bhd2NIOHRmTGlNUVAwR2M5RG5abzVmYjY4ODhxYU90?=
 =?utf-8?B?cDFITE9ObkdOUi96NVhFSXZlQXg2bmMyREVoWkI4M2lpcVYyTmlseE12RXF1?=
 =?utf-8?B?TWg3S1R5aVlJTUV5K081ZythVWdnK3hUSXJtZ2RlbGVJbUkySzliTEl5dlM3?=
 =?utf-8?B?ZEZYOGlWQzhUUGJwQXgycVlMWEVzaitDVW05aDRBVS9rRlNVWlVYSTlCYjZr?=
 =?utf-8?B?d0xkd051a3FiaU94NjN6M3Q1UEd1Qi9vZDV6T3NtMDY4OUgwV1lwMFFPbHU4?=
 =?utf-8?B?MGwxaVpHM29aamhLMTE2ZFhVZUJhQ1g5N3ZndCtxZVJtOEZkRWFvQjQ3Zlls?=
 =?utf-8?Q?bSorgzqZ?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 7da95960-3a1e-414f-f7af-08db91e608cd
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 31 Jul 2023 16:48:58.2524
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: l8lvle6COPYrsn7SIMoRbHsm2nXwAAfG0HViyJ2yoTUxLamYv8TkZ4Qpj/qgdQPsZxtCreAW6r/SPAXxqa1dog==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SJ0PR10MB6375
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.254,Aquarius:18.0.957,Hydra:6.0.591,FMLib:17.11.176.26
 definitions=2023-07-31_09,2023-07-31_02,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0 phishscore=0 malwarescore=0
 adultscore=0 mlxscore=0 suspectscore=0 mlxlogscore=999 bulkscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2306200000
 definitions=main-2307310151
X-Proofpoint-GUID: n-JfErZZyFwKj_a8ibwfwgArcx1j2UkP
X-Proofpoint-ORIG-GUID: n-JfErZZyFwKj_a8ibwfwgArcx1j2UkP
X-Spam-Status: No, score=-3.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_BLOCKED,
        RCVD_IN_MSPIKE_H5,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,
        T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

* Peng Zhang <zhangpeng.00@bytedance.com> [230731 08:39]:
>=20
>=20
> =E5=9C=A8 2023/7/27 00:08, Liam R. Howlett =E5=86=99=E9=81=93:
> > * Peng Zhang <zhangpeng.00@bytedance.com> [230726 04:10]:
> > > If mas has located a specific entry, it may be need to replace this
> > > entry, so introduce mas_replace_entry() to do this. mas_replace_entry=
()
> > > will be more efficient than mas_store*() because it doesn't do many
> > > unnecessary checks.
> > >=20
> > > This function should be inline, but more functions need to be moved t=
o
> > > the header file, so I didn't do it for the time being.
> >=20
> > I am really nervous having no checks here.  I get that this could be
> > used for duplicating the tree more efficiently, but having a function
> > that just swaps a value in is very dangerous - especially since it is
> > decoupled from the tree duplication code.
> I've thought about this, and I feel like this is something the user
> should be guaranteed. If the user is not sure whether to use it,
> mas_store() can be used instead.

Documentation often isn't up to date and even more rarely read.
mas_replace_entry() does not give a hint of a requirement for a specific
state to the mas.  This is not acceptable.

The description of the function also doesn't say anything about a
requirement of the maple state, just that it replaces an already
existing entry.  You have to read the notes to find out that 'mas must
already locate an existing entry'.

>And we should provide this interface
> because it has better performance.

How much better is the performance?  There's always a trade off but
without numbers, this is hard to justify.

> >=20
> > >=20
> > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> > > ---
> > >   include/linux/maple_tree.h |  1 +
> > >   lib/maple_tree.c           | 25 +++++++++++++++++++++++++
> > >   2 files changed, 26 insertions(+)
> > >=20
> > > diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> > > index 229fe78e4c89..a05e9827d761 100644
> > > --- a/include/linux/maple_tree.h
> > > +++ b/include/linux/maple_tree.h
> > > @@ -462,6 +462,7 @@ struct ma_wr_state {
> > >   void *mas_walk(struct ma_state *mas);
> > >   void *mas_store(struct ma_state *mas, void *entry);
> > > +void mas_replace_entry(struct ma_state *mas, void *entry);
> > >   void *mas_erase(struct ma_state *mas);
> > >   int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp);
> > >   void mas_store_prealloc(struct ma_state *mas, void *entry);
> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > index efac6761ae37..d58572666a00 100644
> > > --- a/lib/maple_tree.c
> > > +++ b/lib/maple_tree.c
> > > @@ -5600,6 +5600,31 @@ void *mas_store(struct ma_state *mas, void *en=
try)
> > >   }
> > >   EXPORT_SYMBOL_GPL(mas_store);
> > > +/**
> > > + * mas_replace_entry() - Replace an entry that already exists in the=
 maple tree
> > > + * @mas: The maple state
> > > + * @entry: The entry to store
> > > + *
> > > + * Please note that mas must already locate an existing entry, and t=
he new entry
> > > + * must not be NULL. If these two points cannot be guaranteed, pleas=
e use
> > > + * mas_store*() instead, otherwise it will cause an internal error i=
n the maple
> > > + * tree. This function does not need to allocate memory, so it must =
succeed.
> > > + */
> > > +void mas_replace_entry(struct ma_state *mas, void *entry)
> > > +{
> > > +	void __rcu **slots;
> > > +
> > > +#ifdef CONFIG_DEBUG_MAPLE_TREE
> > > +	MAS_WARN_ON(mas, !mte_is_leaf(mas->node));
> > > +	MAS_WARN_ON(mas, !entry);
> > > +	MAS_WARN_ON(mas, mas->offset >=3D mt_slots[mte_node_type(mas->node)=
]);
> > > +#endif
> > > +
> > > +	slots =3D ma_slots(mte_to_node(mas->node), mte_node_type(mas->node)=
);
> > > +	rcu_assign_pointer(slots[mas->offset], entry);
> > > +}
> > > +EXPORT_SYMBOL_GPL(mas_replace_entry);
> > > +
> > >   /**
> > >    * mas_store_gfp() - Store a value into the tree.
> > >    * @mas: The maple state
> > > --=20
> > > 2.20.1
> > >=20