Date:   Fri, 10 Mar 2023 13:27:17 -0500
From:   "Liam R. Howlett" <Liam.Howlett@Oracle.com>
To:     Peng Zhang <zhangpeng.00@bytedance.com>
Cc:     linux-mm@kvack.org, linux-kernel@vger.kernel.org,
        maple-tree@lists.infradead.org
Subject: Re: [PATCH 3/4] maple_tree: Fix a potential concurrency bug in RCU
 mode
Message-ID: <20230310182717.csx4qgmvfvtc262c@revolver>
Mail-Followup-To: "Liam R. Howlett" <Liam.Howlett@Oracle.com>,
        Peng Zhang <zhangpeng.00@bytedance.com>, linux-mm@kvack.org,
        linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org
References: <20230310140848.94485-1-zhangpeng.00@bytedance.com>
 <20230310140848.94485-4-zhangpeng.00@bytedance.com>
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20230310140848.94485-4-zhangpeng.00@bytedance.com>
User-Agent: NeoMutt/20220429
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?9VKiYyRM1C9/UjfLVLTJX2I2gLQAcLj47dFXEeavYEGbDkoikXwe2kdPd5Bw?=
 =?us-ascii?Q?XfsQ3WrTBgDGaYnySaMuDmVFWTYnAWR7cPTO21ZhYr7wwGmZnZCbUVkqj/ZG?=
 =?us-ascii?Q?5l87EaRV+/vsVsuIW4xnYTwSumWfPF0Pv13L5JEkHixMx70GYP2SwzSGZ3vf?=
 =?us-ascii?Q?6UIsZAlOC86QAHsmKaTLvkha0GlIfARyLh508NnbQYQnlnx9rXsCJDGygKeI?=
 =?us-ascii?Q?O1GZzINUDaHA40Gx3azASNRJIrXvniXAo3ha/QUReZLvY6MWSmjW9mmzwVV9?=
 =?us-ascii?Q?OTmuGSdTYBbj1dKAIsmUAV3JWvoSGs5MRby9C69qZFZz4RU3NlIkkXaG80OQ?=
 =?us-ascii?Q?mMB2VN4wmhShl2CKKapX2MaSMCzyDzwpupCeq1SEBnevfvNv/ObxpvoyQXMQ?=
 =?us-ascii?Q?q+wchz+b0Dm7K7j3GMQV21NRSU9A8VQlZ4/Q9ddUuwhWfYTctY0iWg7vqooh?=
 =?us-ascii?Q?UTeitc6AI1Ph62Zx1cx/oUmG9Hwm2kUXSQ6guhFSX1D0sgKoIYjIPkiDZuZv?=
 =?us-ascii?Q?oPZhDpIxKPudIX4gjBtA/6dTLiwVVcH5avGFzKPlZmHzCzL6863rgTjk1iRm?=
 =?us-ascii?Q?sU/mDVgDDfCvDNHOMJ/1qT6KP9yiNyAIL8TbZtzNNyKPVxy+TM+bQZEZGwOw?=
 =?us-ascii?Q?LVYxxaKvGvSjE1XHstqPmBXzWkKbhYSuwJJAtheGLg+30wswV3cFZZrWIKX3?=
 =?us-ascii?Q?57/SnlN8yKc3EwSR9I2+RuqUQhOap9jmPLBxwYTNzbwqfw+3gMPUhharDGTA?=
 =?us-ascii?Q?IFdNkzD7hkD9nIpK4exmpYAAV3fg1b5FT9sDlZr33FNSHwam7tQyXze6OhAD?=
 =?us-ascii?Q?+5LAz2Oew5zKrfi5VxDVWYfFQtURIRPYtDKVz1T0qDyvNIUkRGCM5VYPKi0L?=
 =?us-ascii?Q?THUNyUWauACK0WmdJndPV2UryqiSPTtnl+Yz7TEy29Zr3Lis2Lg7kUrP828M?=
 =?us-ascii?Q?YzxF7peyF1MbO2e5LtYat4hldBhP1ccMv3e7KU3lRItWheN0ImRZh1OW0bia?=
 =?us-ascii?Q?NKXRKNjVfuYftBxdWQZQoxnKeLsi43Jl7KFKPDMV/nAAKcnK+q251FpXp7BJ?=
 =?us-ascii?Q?Hr2lfvExIDgToZwQs9Mm8Ah9xT+IwT7/zLM4Ule5W/4U8AEKKd0pm3fP3a/E?=
 =?us-ascii?Q?Rd9H14vitgWJT+/Gyv0wOmDBp3dFYH043Sy51s0mGz30UNxDjCjrbzMdNH/A?=
 =?us-ascii?Q?emIhBwIXiay8dakau4I2jdA/xmm4t0m+IWExioRoyn9+X5LzYyoG87DnPCmV?=
 =?us-ascii?Q?XtWX9PRxmKpXeLUDXh7XBK52NUFmFWsRMXTrHOHDBB1GRNPoX60I81KuCyvw?=
 =?us-ascii?Q?Otar8HKB/qj4suxEZQQ0A37bONlZ8hCAdxzIXk5I5wFEDKY98B/zLtvE0n3z?=
 =?us-ascii?Q?5ukP3hZeiKw0/QKYFPJLTOcWME4RpCfB7autqL6uQScwBTEEIy3Vs/PQaJ30?=
 =?us-ascii?Q?o7QuzRlt34eKnNpJDnCB0tlVckKlgioDj4fvqtLybBZ9FBZtN9zrI/XAbUjd?=
 =?us-ascii?Q?TRwfiDSyFkv/Xctnd7Tea/0XnKafWgySpfBKJb7bjHLSy3vMN2UIvUcjLV/M?=
 =?us-ascii?Q?hFXRNSKtAEysLTDiTHFWmfrKn6Du6ZxaFTxhrcGkQnjwn05ncOjTbKDW1DCc?=
 =?us-ascii?Q?uA=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: QZel6agyFqGFztpxj9HQ7jRR1H6j9CDQI0BAoM3stwDMqtahbxMTB32vYfRh+cabG3PFUgyV44RMxehugT7eCByNu5+Ba2PtWQf87m6WcfHSYUzLm1udx/Yg7WzzYbmwwXHreNZghD6RHIhMcQ6GHwoTQDLooWxM9GyCK3OWehXk7MUtySjmkFcv63iMFzfB/zmhpqKxIjQPWZiyvdPEXxziI93CDKA5g58lRj5B1Qma9b53pABK2zrdMIR1jj2hJZs84gpfoY1jgMyvhrQTKoYbx4UItROsv4jbUtoy63S/lIZpN0TH2R7+98cAqUWWe8/taz8wJjAaqu28CBmjFYKKS13PbxSkYYKWJpsF2wCHko98DPsK9Zgllv6lckKsRp8AF6kkKGRKfX3747RuDFStSJs0vDGMOppq8FmnbUcboHKHlE3zK/cN2oSSMjY/j0CTgbQZwn5BfswYmioJbogLBcef4gUceKw/Sks5NLYkqn+WbXR4tUTu+rg1ny6X+wVk3Y0fvfG2gO5TTfUYJyv94iMagdXR1dkiuSh0ksmuI6ZjbiBYwDiu86O3bBsrCk23biWnST5t92um5lWsZKFsBmJdVcKvJZ4uRw9dPZXjx6cXbJhK7t4GALo57z47PnYHPrPf/AFeNZqgEAmo0qTDas8vl/SQUMStAhuqg6Wqx8ELtiadT6w7+xbD0mfEdC3qZpcHmJuyO7JTKY2qSFgn2pkk4N+YVp0CkXbtKNxrY3LFxKhEx2wAFCNCKpiDv9l4FwyKEfVxH3I7wmPTl5cITDjOdcAKhWPfinsjZd/lbgCClW0lsTQGU4dXqBc9q4pwP/30UX+POi3fg3CsYhJbTHMfDpdQnQlHKdC81zzUIBv5Zt3MuoZJtP3RzcAg
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: c790ae19-59d4-4d28-9b33-08db21951608
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 10 Mar 2023 18:27:20.7657
 (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: zy9nTlqvd9hiLjD70hAjKvEIqAwPfBVl21TcBKkVXXah7MrSX0vLyFDGQ9uqYXC4uFUcqGG0Y3CJtdEhB6CFfw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR10MB4365
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.254,Aquarius:18.0.942,Hydra:6.0.573,FMLib:17.11.170.22
 definitions=2023-03-10_09,2023-03-10_01,2023-02-09_01
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 spamscore=0 mlxscore=0
 mlxlogscore=952 adultscore=0 bulkscore=0 phishscore=0 malwarescore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2212070000
 definitions=main-2303100146
X-Proofpoint-GUID: 2EATcetvp6MBGMSWc3MzDjPaV_AMslFO
X-Proofpoint-ORIG-GUID: 2EATcetvp6MBGMSWc3MzDjPaV_AMslFO
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

* Peng Zhang <zhangpeng.00@bytedance.com> [230310 09:09]:
> There is a concurrency bug that may cause the wrong value to be loaded
> when a CPU is modifying the maple tree.
> 
> CPU1:
> mtree_insert_range()
>   mas_insert()
>     mas_store_root()
>       ...
>       mas_root_expand()
>         ...
>         rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
>         ma_set_meta(node, maple_leaf_64, 0, slot);    <---IP
> 
> CPU2:
> mtree_load()
>   mtree_lookup_walk()
>     ma_data_end();
> 
> When CPU1 is about to execute the instruction pointed to by IP,
> the ma_data_end() executed by CPU2 may return the wrong end position,
> which will cause the value loaded by mtree_load() to be wrong.
> 
> An example of triggering the bug:
> 
> Add mdelay(100) between rcu_assign_pointer() and ma_set_meta() in
> mas_root_expand().
> 
> static DEFINE_MTREE(tree);
> int work(void *p) {
> 	unsigned long val;
> 	for (int i = 0 ; i< 30; ++i) {
> 		val = (unsigned long)mtree_load(&tree, 8);
> 		mdelay(5);
> 		pr_info("%lu",val);
> 	}
> 	return 0;
> }
> 
> mt_init_flags(&tree, MT_FLAGS_USE_RCU);
> mtree_insert(&tree, 0, (void*)12345, GFP_KERNEL);
> run_thread(work)
> mtree_insert(&tree, 1, (void*)56789, GFP_KERNEL);
> 
> In RCU mode, mtree_load() should always return the value before or after
> the data structure is modified, and in this example mtree_load(&tree, 8)
> may return 56789 which is not expected, it should always return NULL.
> Fix it by put ma_set_meta() before rcu_assign_pointer().

Are you able to write a test case for this issue?  I understand it's a
race so it may be difficult to catch.

> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>

Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>

> ---
>  lib/maple_tree.c | 3 +--
>  1 file changed, 1 insertion(+), 2 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 4d15202a0692..de43ff19da72 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3635,10 +3635,9 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry)
>  		slot++;
>  	mas->depth = 1;
>  	mas_set_height(mas);
> -
> +	ma_set_meta(node, maple_leaf_64, 0, slot);
>  	/* swap the new root into the tree */
>  	rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
> -	ma_set_meta(node, maple_leaf_64, 0, slot);
>  	return slot;
>  }
>  
> -- 
> 2.20.1
>