From patchwork Fri Mar 10 14:08:46 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13169300 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 A7897C742A7 for ; Fri, 10 Mar 2023 14:09:46 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 17BCF8E0005; Fri, 10 Mar 2023 09:09:46 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 12CF08E0001; Fri, 10 Mar 2023 09:09:46 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id EE86B8E0005; Fri, 10 Mar 2023 09:09:45 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id DCBA38E0001 for ; Fri, 10 Mar 2023 09:09:45 -0500 (EST) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 9DDB0801F8 for ; Fri, 10 Mar 2023 14:09:45 +0000 (UTC) X-FDA: 80553171930.20.6A3F864 Received: from mail-pl1-f174.google.com (mail-pl1-f174.google.com [209.85.214.174]) by imf03.hostedemail.com (Postfix) with ESMTP id C699020018 for ; Fri, 10 Mar 2023 14:09:43 +0000 (UTC) Authentication-Results: imf03.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=R7ouu0Wk; spf=pass (imf03.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.174 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=1678457383; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=ZI1NTxNQsncsBuSARtQ7gY1qx/Kaxg/acZj9mrc75oo=; b=8NeHoi2bVPwe9/gcCC1z6VslmTCPOIO0M5GTHgTkozqMtkgcf/WFwVkX/9cMEauVgB+xje HqHeukOck4uTJEYMAITiQ7CPcUVBZW6rF+izupnPIPsCCW6SYTCLpwEV+9Yutfr17FX0GI tNanawKfKUq2oxFfP1DryR0I1RoX82Q= ARC-Authentication-Results: i=1; imf03.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=R7ouu0Wk; spf=pass (imf03.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.174 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=1678457383; a=rsa-sha256; cv=none; b=mUsyn5MDelm1hrBTbaI71xtEYeFsMIa3OAATEqyisNyWPloMrnoEZ9iDrEPYL9E1E+gbTE RNELY1Cxd+oRWOE8TEV8AxH1UyycHKe+91AoZdAQUf6Bgl6m/8AZgbb1sL7t8CwHpji2MU xPz/uHcLxFyP4a7uRBjBLfLT8OA06H0= Received: by mail-pl1-f174.google.com with SMTP id p6so5713165plf.0 for ; Fri, 10 Mar 2023 06:09:43 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1678457382; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=ZI1NTxNQsncsBuSARtQ7gY1qx/Kaxg/acZj9mrc75oo=; b=R7ouu0Wktvvy/0biANU6/CsFYdvyqaelWm1/tm2k3z1xn1E58V6YQdhsRRE48Ukl0D xouTlAcz47ET0Gx71OmdRdZ1QQB46Fe9vBCaiXaGfk/dAdNoNJMwJmdyFhZ7pV/S7KcT qq/41cVbpI0VXpk7WAC/xbEO208+6SIYdhxXL+q7/v3/pnmJ5yey3oRrE45ykNAf9O+h 86/msFcANeTG0J4YQf4v66JfUdAcaAPu7V0w346WgpHPq+5Ozy9K7ywU+iLrHj5ieiIP /YBouzChgTtzGJRoD3jWioB/xzQHKJGT8lMCdNM7tcG+wvmYMAxcNNKEWgFrBZeD2ZvQ Cx/A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678457382; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=ZI1NTxNQsncsBuSARtQ7gY1qx/Kaxg/acZj9mrc75oo=; b=BtIprtdNKEUIGpugFoHXhqw6jw6RdqHBxFCrA0x/YyuwE1DoRrG3iVlvJMOCXnFD9Z 86VdIj140bq0xG+l1mFJEqRBtjXUTmEjwoIHJqNt1HhZR2SaHr1byc/TYBKM1SrSaUtb 3/oYn7Eb/N44kp/uBvAJ5ZgVNBVDarjBvYi8ai7m0UO/b9aQGP+2SLKaOwL9sPNSc3iS FUVz5TkDNtqZ38aCxOltHUcVHOUJ9ExChZkEv4Kp/Ps2rNLwhuJt0b2JMUkgmmmEcvIw of/WFCaDbVTt+KjR4ASNOLJehyE4NNkqnT23Rn/gHWH7HIndMNtaNcLSsfGaNXgAZiV0 U7rQ== X-Gm-Message-State: AO0yUKVP3sGPC9fMVMydPAAkQ5Wdd3qju+1Uq4EyBwTcqv+pH47O5zkH TyObyKDsDdbmRKSv1GhRc1scYA== X-Google-Smtp-Source: AK7set8Z8bAhdNtk0KoMAdSO1/VatXK5WhDtaRNgSmexkSBtrCjRc8k4A5zuJ+DkJF+bE84k83di4A== X-Received: by 2002:a17:90b:33c4:b0:234:bf0:86bc with SMTP id lk4-20020a17090b33c400b002340bf086bcmr25736949pjb.31.1678457382536; Fri, 10 Mar 2023 06:09:42 -0800 (PST) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.234]) by smtp.gmail.com with ESMTPSA id fu11-20020a17090ad18b00b002375c356b0csm6753pjb.19.2023.03.10.06.09.40 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 10 Mar 2023 06:09:42 -0800 (PST) From: Peng Zhang To: Liam.Howlett@oracle.com Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang Subject: [PATCH 3/4] maple_tree: Fix a potential concurrency bug in RCU mode Date: Fri, 10 Mar 2023 22:08:46 +0800 Message-Id: <20230310140848.94485-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230310140848.94485-1-zhangpeng.00@bytedance.com> References: <20230310140848.94485-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: C699020018 X-Stat-Signature: snsgg1h5byaijf63yu9x9dzsd17ifdf8 X-Rspam-User: X-Rspamd-Server: rspam08 X-HE-Tag: 1678457383-393170 X-HE-Meta: U2FsdGVkX18oI1ul2vkr+/TK7s0JNE3lUNrkQaSfkucg8YKIdq32VYMekfwWGbZoEh0Oy0a4c84bReqWyuMIDrfYVVocrKZD9z4sx87P88Vjybk1IWQtKCL5966niDChog+M8VBK8pvdHQ0UYZpLjNm0aPBT2vjhLCRmSZrRCXOxG0kxVx7N5EWyoByojrP2r8iJdCO00gEpOEBif11KwuAu3zWMq777+owrgwZZVOUoAWy9wLkOCHxc3ZtfuqUAYt7QzrxLTGUJJqZFIKUUH21aJL8KKlN4zLh2STNAOaX9thyGBIccYvNyzdKmLVWUm2S267ErSkjt6lrSoYRjUrLOATJ2z4xQ4HPUD5brp8sCoy6sZXDNtsbTSevccichuWnidVcFbaRQ8/SkyzRI07OxnCdawpry4VMHHLiCCKHlE2+j1eA2xfkZeotFD404G4kcFVsxeHYz3Q/T7GaAttP/Pi8EaG/jfvxipjpjqvrJXwn/fTKlo91XFFt4eD3MHIxblFNi8H162I9/xCtRss8lJMbmxpBcrj9YjknpI1+m1fO+msKsy6M4U8umSbfmjwnxCQB/j9UP7zTjlYAGKU+s2cQxvbr0FkQEuTW5wGetCYQY1tguJ4s8HL3hHceQlu05ABSvpwiGneYbNZYnBDPpKoYVdEovsOOXISyU2ZobVmo8/bUILyoVPrernYZnGuQ5mt7y9c5BEkzK/rijO1EW+bW684Tsrqu06xi+cVR2znOGgEZfZzPRHQbf1oYzw9QNRM8+XTL9rFd1li4g8blf6Yd6/K/geDEecaHS0c9OgQgZEiBDtS1k3nd0gSUmwk8TBpyu5PfVW9QlQiW32HCsuQy94kiuvp44HGRReYeRNmNweKzHTdHqxkO+qLzUhCnL0TDPUwiL4J5EdBaeJidtaBzIhUZ2mSk2WuxhhaVzw+eDGocnoXRhCF0KCLBtSq/K5GffnYuZExYNhkr S917KSiz 3tk7C4YdaWAFApNfDahrTGe6p86h43UE646x+8Ny9bjBcMLsQEsQ1rX4KacV1tWmufONl5ixAWz8YNlsp9DKNXJxMHrLKBXEAK6LEs/BLP9mDcrr+8aad87IuKTcfcucjuHql4+cYtCuzj66uStaVGO/c1OJZzPqAihbVVKCYpsj8IbWjmMeNDk7/7++FO/ICv0xrX2gG+p2Bu0ZiLs+2U9dyO6jPRDY8AfUjr4Ik2A/d752vFhkjSwfNBjW2pAPf92Fi+yzTYQXjNZZfKv5yF6z8E9xXKRcbFW0FM8sEBJ2UqzPxPHR2R8dD2LZ9VRErdiObqoFGQ1J8VmZKxI0K34S4SQNZF2EOTs53TUchrm1v/+F1I7SCND5fUu12ctIuE6XojF4CW5ZeYipMsBvfLYpsLZDms5g8OvoPY+hj/wp8V8O94eJMGsnmrqEBbACb2c0Pj9HJ+dSSV7BfBQtObWkQFw== 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: 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(). 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; }