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 8CCA4C6FD19 for ; Fri, 10 Mar 2023 19:03:33 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id DC0E36B0071; Fri, 10 Mar 2023 14:03:32 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id D498C6B0072; Fri, 10 Mar 2023 14:03:32 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id BE9F58E0001; Fri, 10 Mar 2023 14:03:32 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id A7CB56B0071 for ; Fri, 10 Mar 2023 14:03:32 -0500 (EST) Received: from smtpin21.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 64D051A0AD9 for ; Fri, 10 Mar 2023 19:03:32 +0000 (UTC) X-FDA: 80553912264.21.595FB06 Received: from mail-pf1-f180.google.com (mail-pf1-f180.google.com [209.85.210.180]) by imf30.hostedemail.com (Postfix) with ESMTP id 78E2E8001A for ; Fri, 10 Mar 2023 19:03:28 +0000 (UTC) Authentication-Results: imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=U6L5ZFKK; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.180 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=none) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1678475009; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to: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=7HJMs6+Kdc1OEc2fFSFYRB2EioEoEFo0VUZVVyRVLQY=; b=PPc/5NayAIMh+2b8Dm4G5poNGOGrm/v4CdD4aYoR77+m5mdnZ3HqrXWmvi1HOOlCqHlurH Zfmcc1ayaAmqjbNN5+VWx9om9876srg1YViOpUtE2ZflI95CHMlk/nuHjORPyezonrm2+L 6lxuKZXoYid/pl8xROutV1Ti2e8iBC0= ARC-Authentication-Results: i=1; imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=U6L5ZFKK; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.180 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=none) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1678475009; a=rsa-sha256; cv=none; b=Bb8P3yiYgUAIgfMUaq7YdkGXdY/hQBwYG5Xj6DJy7Xx5ZKyuD/JS1smMONi4KUkd8ABRtz L3WCyiqcLSOmlfQDZ7/IA875Z4D+H+jjFlNEzpafdRdPczZtPjCHMm9fw8A8wc7MWQv+iJ Ul2YBZBQ6VmcD+AjzfcZuLkMXvVQFVw= Received: by mail-pf1-f180.google.com with SMTP id c10so4250477pfv.13 for ; Fri, 10 Mar 2023 11:03:27 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1678475007; h=content-transfer-encoding:in-reply-to:from:references:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=7HJMs6+Kdc1OEc2fFSFYRB2EioEoEFo0VUZVVyRVLQY=; b=U6L5ZFKKloSDynq8esV4PSUbWTgzgRvxnP9nV4e1tfJLsQa9ewl70xQx0CA6gYcZzR QtYgDLLPflhsRVjJ3w9F02eqNwuxCfijFzyjDbtbK5TgU8xzMFN3k+tMjTCbEalDymxn GbBbtoJHObm41datISzyn7VUsLE36L0MUCUl1E+jfxkw8BxYy5x8aZtpNnMcUkToniI7 fRrU7RAuuFf+ao9csKsVUH06uc/eZzGOL+5PAqAvgf8WdNsLN6VMpW5RFdK3c+7K7sld GpoTYZygD7q3LNhrBIryQjy6hddzyGcU3lTbj86lJOeeI5hWARm91moWGxozb6aR2vcj Cl+Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678475007; h=content-transfer-encoding:in-reply-to:from:references:to:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=7HJMs6+Kdc1OEc2fFSFYRB2EioEoEFo0VUZVVyRVLQY=; b=QeJbKbA4eT67MHQYnqho6j6S/PUn8o8V/8gq4wfkpox0MtpnqOHoJBPzTKQvrpnbhB a4yeyRetBZ/Jfs/fZErepKDaYzli0OSos6yv0+PSW/xFfOVJE8wDyUgIhVCxsfhfEpts qbdwxTRHhp3bmqpcJrAuYIUVoAjdt4Q+0/oNEUAvmFoaYRD2ybxo0lWrae2YCdXHjybe M6+8Kw9lhOrQOxHTrWiht3ImBB6esrcaAWPfAjqTHP2JcEJmfUopnwALyP6rpEbrvv1x sIzPCgMCpBK8vGq+zFSXKTgA7SneSck/mt/Bt8FAjAq1/Fxn5He9YqWPPtmxo6qjHrXn N0eg== X-Gm-Message-State: AO0yUKVPc66ySl127wih4f8WhJqPsLPqw0b1EvJeax01630H4QaXhS8E lTr7keWL/tUoC/tktaKafEiF/g== X-Google-Smtp-Source: AK7set/+9lIiHNMBOxf2F7At84dLq8xFZwQ5+D+t77gwK3TUYermJ3ZdrO2BV0Sz2asidHFTKHbAYQ== X-Received: by 2002:a62:4d05:0:b0:5eb:25b2:5f6e with SMTP id a5-20020a624d05000000b005eb25b25f6emr24253725pfb.8.1678475006929; Fri, 10 Mar 2023 11:03:26 -0800 (PST) Received: from [10.200.11.19] ([139.177.225.234]) by smtp.gmail.com with ESMTPSA id j21-20020aa79295000000b005dc70330d9bsm171911pfa.26.2023.03.10.11.03.24 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 10 Mar 2023 11:03:26 -0800 (PST) Message-ID: <1670bc9f-e601-c445-6db1-7c769bb21547@bytedance.com> Date: Sat, 11 Mar 2023 03:03:22 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.8.0 Subject: Re: [PATCH 3/4] maple_tree: Fix a potential concurrency bug in RCU mode To: "Liam R. Howlett" , Peng Zhang , 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> <20230310182717.csx4qgmvfvtc262c@revolver> From: Peng Zhang In-Reply-To: <20230310182717.csx4qgmvfvtc262c@revolver> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Stat-Signature: pbj47mz5k1qm46aqc1sko5s4dendyfzn X-Rspam-User: X-Rspamd-Queue-Id: 78E2E8001A X-Rspamd-Server: rspam06 X-HE-Tag: 1678475008-129897 X-HE-Meta: U2FsdGVkX1/375QAfg0LyPtMWfVGefUPV8BSk7E22KFvsI/mwcUXO8JhMjsVgtAtrZ2jbEWX219d3yLazoK8CSqKVU+uS74tSTBDWS5P9vPWvkFya68O3PVuPBd5KHrIpEP9WraNsmKpeMWv59aFpqZXWXU8qP0U4tjqoyG545yRtdt+AG32I4TSO+zpKImWewKe1ZdVBPcA09s/3kllE0cQYSgXkGXK8SdpHXAM2Q9D3r3RVMHjI0uWemJ69VNBk/xG3SkAqioUoc1ghmQYvEWtfvuSfc1S8r9qA5AE9UHXGYcQ8eB0sTnSJ/I4F+sqy83lsyJ5fmlUmCTIph1dJt5g2OP4gvWBPKotI6quBBwfx7bPstUscmE+jVYqiS7YZgIzn+TLCuL0S1Ztk+xDaLofvtrZVDpPzb3HYpDiIztkiOcOWksDXvaYStjX8W5JZ7I+z4b3dgCJOwV3gvmrDPZA2ED7qO8DAT8HATp/dW94kabAizmxXtYf7yC4bhT2CmthyaiqMwgUTq2iFrqwJmR14FzY9N0kxr6qAZdaaXymYDRCN2CDdcotn+R1KKyMFdxlFAYi618RjP1LtKXQPWnt+tb+aIC4pyLE1mCOxjd3pQGmE6VgdObMNgPpSbB2iKRbFR0gcCgtMxeMNZtnC8mZd0rCLeQKCNLsyD2CVy/T6W/4Jfr/TIpvodmBmsk06JyITrIL4k4srv4pFiGawWmioqdxx3Gd7MDgIh+JfXMTz8G1MImfIvPjGakiVhFt1BPApdQNuXFN4eMQIBaKdmBV4EqfBvuRwvFNV4PnWm2DKauy9epW2G57H0lB3JzeUECL5YUiE9jxf0lBvJ5ZKcNGhcsPBOXnHUVjsFGlLuhQqWZn3wmxyQTAD8g/sSOhhDHa6fmCYSQD6rbErWpBsv/vuDMUfEP0Wo2g2Amvb7GfSnnPNtxYSqjKweIkLOLVhtE9/K8H1Dbr06/sA9D PFaGOsNs tyCusKqILhovcPau/rIg4Okz2Gu1NVwzXZ3Lq5wkvukHNU36wDOhwMZJ6oatIz/cQxsOqHiUtGB2/zf6lqX0zVdBZMfLUrJZHBwyXZfk70hwVSqwCrDbob1nq9iC6VM5JODuRVTyTTRK+HbicZzM6wWHOfs877Y1WeU2B4elMiiKUXIAzoBWs1pwqV+M6MJmqkjwM1dCQbzqtOEjL+CpPAO4I1U2h3+/NBMM4blwcyMJniHK9bKJmYSe+WnOm+njtlVtzBsb2H2V4s9CM3E3DLIOGgZn4o4InDJRzhguJoyNRgt/xhoWjQrH4/G5x88iSIM7aq7PdACf9sLS6rJiU6kGUs2Kd51YB6cRcZcp7pYNkAbFhpmDYBiu2VnoPZFoo+Ud7do5gA2VpSyIY7c8XrBdlhtWyN/hNlhlnCuqXWSve85ZWJccihFpW5jJeCZB/dwSZPD133dl3O6PwrKMpTJK45GUjTLq5tXdqWl/nS6byvit07AP8GFML7g== 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: 在 2023/3/11 02:27, Liam R. Howlett 写道: > * Peng Zhang [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. Yes it's hard to catch. I'll try to think of a test case next week. It is difficult because of the need to expand the competitive area. > >> Signed-off-by: Peng Zhang > Reviewed-by: Liam R. Howlett > >> --- >> 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 >>