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 BCF45E6F07D for ; Fri, 1 Nov 2024 18:41:07 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 5BAF06B0096; Fri, 1 Nov 2024 14:41:07 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 56A4F6B0098; Fri, 1 Nov 2024 14:41:07 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 45C386B0099; Fri, 1 Nov 2024 14:41:07 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 212776B0096 for ; Fri, 1 Nov 2024 14:41:07 -0400 (EDT) Received: from smtpin04.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id CCC46A0C95 for ; Fri, 1 Nov 2024 18:41:06 +0000 (UTC) X-FDA: 82738392786.04.51D695E Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by imf05.hostedemail.com (Postfix) with ESMTP id 1B727100025 for ; Fri, 1 Nov 2024 18:40:10 +0000 (UTC) Authentication-Results: imf05.hostedemail.com; dkim=pass header.d=linux-foundation.org header.s=korg header.b=YYJkmXXv; spf=pass (imf05.hostedemail.com: domain of akpm@linux-foundation.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=akpm@linux-foundation.org; dmarc=none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1730486286; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=CL1QEjO9+Tz40qqhzGessYoKJl703lTbEueXgqrMxP4=; b=ARXOC5FqJ192v2ydRFgJYy2W1jJCVnRmGla9722/C4CQEhwQcjm4nTTrOep1j64xtQ5YPq cAkC4KHtxlGbyPTb/5m5mkTgZcPoKuIx/0RfS8hkxb9AJotMNaqr/6GcOceTl95dItlnsD EcHvvDLQWcUJ801C8IX4CeZnQWDqk8E= ARC-Authentication-Results: i=1; imf05.hostedemail.com; dkim=pass header.d=linux-foundation.org header.s=korg header.b=YYJkmXXv; spf=pass (imf05.hostedemail.com: domain of akpm@linux-foundation.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=akpm@linux-foundation.org; dmarc=none ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1730486286; a=rsa-sha256; cv=none; b=DSbfxb4Lo75KJNGZCm/4i+ACdRf4xOTCZ4MDXfD42TLsuEeDc4TNSqGPrrtXEHmi+ShxpZ s1D0lzHKBFUCgzEw2NB9+DUyO//AnnBfx9ChIQQG7GN1xkjud0+6tLs0VI+9AiHBgjM59v G+jYhT6e2aUoViU/oMlCrS2PyA9bj7I= Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by dfw.source.kernel.org (Postfix) with ESMTP id 3E9165C54A5; Fri, 1 Nov 2024 18:40:19 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 95B52C4CECD; Fri, 1 Nov 2024 18:41:03 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=linux-foundation.org; s=korg; t=1730486463; bh=A9jRxC7fi7R51oiDGiPxAPcEE/LC/0voK1RVi0h3LVQ=; h=Date:From:To:Cc:Subject:In-Reply-To:References:From; b=YYJkmXXvE0AHBiiGR0oRn/2FKFHQiaLYBU5yNrJJ1rs+f/XZ4w/6/B5/3/ysbw3JS G3Csk/8Nx3Eiu74RF6mKNQh7tKjW+ddhxuiD+hn2TnYxCC0iVqtcrWaoDACMbGvq16 ShlJfp1Ub6qGsYiWvUolZmq22KMJzmjxzRkdpBjk= Date: Fri, 1 Nov 2024 11:41:02 -0700 From: Andrew Morton To: "Liam R. Howlett" Cc: Wei Yang , maple-tree@lists.infradead.org, linux-mm@kvack.org, Sidhartha Kumar , Lorenzo Stoakes Subject: Re: [PATCH v5 4/5] maple_tree: refine mas_store_root() on storing NULL Message-Id: <20241101114102.64c98ba675c5c8dfa4b295da@linux-foundation.org> In-Reply-To: References: <20241031231627.14316-1-richard.weiyang@gmail.com> <20241031231627.14316-5-richard.weiyang@gmail.com> X-Mailer: Sylpheed 3.7.0 (GTK+ 2.24.33; x86_64-pc-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 1B727100025 X-Stat-Signature: 4r7ccnrch9mrnj3enf9ryj78srr9a49z X-Rspam-User: X-HE-Tag: 1730486410-717129 X-HE-Meta: U2FsdGVkX19pSBsNVPpvxtlQQVm0wWKzJMIKniMbdoHtuhfrZyZSl0sK7BYQPctcZDpozf6p0Jwc0bK4psp9boDaeqISUkrKmCUFwKtkd2C5gX+eQP+yXMK2B6UQmnzfp/anbPtQcCxV5C8OPscSzmEPVStBDo/YRhQ1lzw2d7nEYPaxoPk0qAJZQg6fQ09wS4hZr9+WNYKPFuQXcPYGzNH+eIdSHTYTpDqge7zicBB2CfCAlULVxE6Lr1UIQaNk+DCWRk4RMfPO7JplEsYeLOpsaPXFHFegDRBaEMwrZ9tuGayFC5xA2zLrLjnYWSluPYqW+vivBZbuI0ONWnpqUWhc174n439yC9MIUtlFDKG+6Xx9kjV+9gMisdAu70JED5eviI57zvmdg4HW1INdNXXxX6lFIjuNfa3tD5om87DEmItOJKlAfvQEtDLaJnqTFV1+/nntN3Lp0x6NxB/KY5Gjcjlz+HACXU/dhp2nV7ffSwgxalO8wIuYXG9ViklsH+3TZaA42GlKaiZcDA0cKXcMZppv4mEL7HLRZTPYZ32klENNMcVFCiHy2x4VcM3XLpA3spa5GnvyW3CtAKZwwEAsDoS5/07koD3odjhQTg54p0F2g8aqnrdC/P7rObev/wr0xcn4Kw5a9lIRxGMSzOnQOcpbFGoydzseGDVXlShn2U4WBIn+/J3220J81huil57FWCROoHRstQvJdEuaYajFQlJnMugdXem+ac4UuqsIpU0M0H0GWcJQAw1OcJ9rcNblVhdVyDSJYrgB2IhXV6X4fQ45dYHJPkzPcNAu3H7q3w8R8ehV37rqxmKml83y56LPQ07OjahaxUZws6iuopBDetERUheQxU+5bx94P9M0k3gf/UeaRcZN8zDw0in7CgQNTOhqudL1hathSW3qIAiWpB1nQV7Jcsi22khl77NWJeRgSdPQ94hfoC0N+sP1HheyDp5mVHYEKJHR2og zSWRuMD7 oPxZFZffEGv2r6q+AePYFnzTtuHAQoRwdIML7VbHd6ml1WsTipSo0rSM1v0zqeR0VEtZo6fXLeSUsEk6AvwKjfm/y4JvOjtJ0STPEuhKo01I+1VfCHjUcIBzMMQBdDp8rCv8myjVR4af9IiFcPZjzqfuLGwMkKmOzrHQx3y9eORS2Klxy0WXpVY5h8j+RlkHdRmOdfdKIaJbbG3rQLjzKYOyrN4xnQvYKb8BylTsiAlnqiq7oKJaLZepgsF9eUWofsbq3b2SSCCChzwj20BtqQMP6Wpc+2eSwPp/LilxD4m9qDgrnqM36aAA8rXFkAeYq1wH3wf8TciYsMDes34ixQKLSy6uknMc5soXEYcap9WuMtH+HgkDYbm1FEU1cZYlXCmdXaKQOfjgDPSFdNDqVkEVGfmwIfxYejJ3urRBgmJMqPXXKmwjwW1FGyQ== 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, 1 Nov 2024 10:59:24 -0400 "Liam R. Howlett" wrote: > * Wei Yang [241031 19:17]: > > Currently, when storing NULL on mas_store_root(), the behavior could be > > improved. > > Storing NULLs over the entire tree may result in a node being used to > store a single range. Further stores of NULL may cause the node and > tree to be corrupt and cause incorrect behaviour. Fixing the store to > the root null fixes the issue by ensuring that a range of 0 - ULONG_MAX > results in an empty tree. > > Users of the tree may experience incorrect values returned if the tree > was expanded to store values, then overwritten by all NULLS, then > continued to store NULLs over the empty area. I pasted that into the changelog. > > > > 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 > > Reviewed-by: Liam R. Howlett > > Please add stable to Cc list, and fixes tag. This needs to be > backported, probably to v6.1 I added Fixes: 54a611b60590 ("Maple Tree: add new data structure") Cc: