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 4D91EC46467 for ; Sun, 15 Jan 2023 00:19:14 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id AF3938E0002; Sat, 14 Jan 2023 19:19:13 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id A7C918E0001; Sat, 14 Jan 2023 19:19:13 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 8F5E78E0002; Sat, 14 Jan 2023 19:19:13 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 7843A8E0001 for ; Sat, 14 Jan 2023 19:19:13 -0500 (EST) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 46B381205FE for ; Sun, 15 Jan 2023 00:19:13 +0000 (UTC) X-FDA: 80355123786.19.6396B66 Received: from mail-qt1-f175.google.com (mail-qt1-f175.google.com [209.85.160.175]) by imf20.hostedemail.com (Postfix) with ESMTP id 25CE91C0011 for ; Sun, 15 Jan 2023 00:19:10 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=N85udYLK; spf=pass (imf20.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.160.175 as permitted sender) smtp.mailfrom=boqun.feng@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1673741951; 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: in-reply-to:in-reply-to:references:references:dkim-signature; bh=x9NlsPlpNd7WXgq+xHOVgza2BZyYigkU2oTgae9LxSE=; b=MQEkYxqDpp1gnSc2ilZUcyzu+2lZ/Mqc6DKERSNcVsabvVRHatQqY/V0j9UEcPcFvUu34O ytiE0HU9l9BInDI28gpD2PRs0436Oad4UUlbrM++pF90J99WkrEXCljVGVmw9PE6QW6NV5 OU0mu84PJPN6x9dUN/my8nHXXl0rf3w= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=N85udYLK; spf=pass (imf20.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.160.175 as permitted sender) smtp.mailfrom=boqun.feng@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1673741951; a=rsa-sha256; cv=none; b=DENXp5z1ph0i3Fs9wHBSsHLM7Ke7haqB6cmxnnaSM3PCpCa4MsPJelIz9BWyPRoi9HwLFd pApcyzPMNVgFjXKYW3/YvyCWfueFm5NzHDzjLwEAWZEo+UX8wJQ3Qi+xonpYjVaG2P+o8W SFoB7u6JJqUIKEbOw38l14XQUogrMIM= Received: by mail-qt1-f175.google.com with SMTP id s5so17636844qtx.6 for ; Sat, 14 Jan 2023 16:19:10 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:feedback-id:from:to:cc:subject:date :message-id:reply-to; bh=x9NlsPlpNd7WXgq+xHOVgza2BZyYigkU2oTgae9LxSE=; b=N85udYLKFRE92xIWBkwfGphVp4OMvAHnhw5YLiibpwUn46qrpBTBnP1iIqP+Tbunt8 w3L4mFT8bCjMeLB5lYZGtzYSTvJNiIja20pMrmJxKt4O52OGI2FlJ1w/ORLFrCVpdUZF tZuCrE+l/XnHeu4GwHsGMkOnHxR5vCpUC5v1ihlTDL3YWBoAY9wKxGP+SaXy7y9sVEkT x0WKS9vVvcY58NUMy1h8a/4aJA3QmW2mILApSS4KcJXyAMWdrNVwASktUmNUTOxiQ7Ey ChlChka8zsQO3bqMPgMG1e8jWK7v8ifd3NyQrBnOKrODepoQXgVT9Z00daQg6zQUQ1Sn j2yA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:feedback-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=x9NlsPlpNd7WXgq+xHOVgza2BZyYigkU2oTgae9LxSE=; b=5435mz7GGy8uHdK+IilvmdhEzuPFSc4pX31c3qshISEBcpkvoxtylveghthZOb3rGe CCLvrHllDuiUq2+3LwVy5m0ERVzk8WJnb7UC/vI+GJWhPgEOG7porQDdphXfNzoFhfIO TnqUt68wKgilDCCoIqpta55OOYj7xBXa4IS23EsT7qR7XePC3ens3FCxBwCzLl5LRUfW +bQZ75DqpBpZcMypA/k4tr342SzfYu5mcpPSJISamSio4sT9IOuLXCgK3LoCuLGSVgS7 YgYgVdIf7pm/UOlf87BamUEP3E4Prbxpdavxlnq1jQjJXn+DKLFupn7e0XSBLnwqBsgr ec2w== X-Gm-Message-State: AFqh2kqY8zMi+sYVIPCYBmP0H9/T/gk4D0GJcP8ReS4WWfGEwmlL4lwV 2TxALN6iyeUyG11yAs7XdV4= X-Google-Smtp-Source: AMrXdXtv6M25sTMF2oI3BC60FhEW0IjAnvHzamIW9UnlhI3R24tysCrcSVWtn3vFluI+tCRK+Fqp/g== X-Received: by 2002:a05:622a:4c88:b0:3a8:21a5:d93 with SMTP id ez8-20020a05622a4c8800b003a821a50d93mr139131967qtb.39.1673741950267; Sat, 14 Jan 2023 16:19:10 -0800 (PST) Received: from auth1-smtp.messagingengine.com (auth1-smtp.messagingengine.com. [66.111.4.227]) by smtp.gmail.com with ESMTPSA id q6-20020a05620a0d8600b006fa43e139b5sm15306709qkl.59.2023.01.14.16.19.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 14 Jan 2023 16:19:09 -0800 (PST) Received: from compute2.internal (compute2.nyi.internal [10.202.2.46]) by mailauth.nyi.internal (Postfix) with ESMTP id 17A8C27C0054; Sat, 14 Jan 2023 19:19:08 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute2.internal (MEProxy); Sat, 14 Jan 2023 19:19:09 -0500 X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvhedruddtuddgvddvucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmne cujfgurhepfffhvfevuffkfhggtggujgesthdtredttddtvdenucfhrhhomhepuehoqhhu nhcuhfgvnhhguceosghoqhhunhdrfhgvnhhgsehgmhgrihhlrdgtohhmqeenucggtffrrg htthgvrhhnpeehudfgudffffetuedtvdehueevledvhfelleeivedtgeeuhfegueeviedu ffeivdenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpe gsohhquhhnodhmvghsmhhtphgruhhthhhpvghrshhonhgrlhhithihqdeiledvgeehtdei gedqudejjeekheehhedvqdgsohhquhhnrdhfvghngheppehgmhgrihhlrdgtohhmsehfih igmhgvrdhnrghmvg X-ME-Proxy: Feedback-ID: iad51458e:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Sat, 14 Jan 2023 19:19:07 -0500 (EST) Date: Sat, 14 Jan 2023 16:18:57 -0800 From: Boqun Feng To: Hillf Danton Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org, Peter Zijlstra , "Paul E. McKenney" , Paolo Bonzini , Joel Fernandes Subject: Re: [PATCH 2/3] rcu: Equip sleepable RCU with lockdep dependency graph checks Message-ID: References: <20230113065955.815667-1-boqun.feng@gmail.com> <20230113130330.1027-1-hdanton@sina.com> <20230113235809.1085-1-hdanton@sina.com> <20230114071832.1162-1-hdanton@sina.com> <20230114102659.1219-1-hdanton@sina.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20230114102659.1219-1-hdanton@sina.com> X-Rspamd-Queue-Id: 25CE91C0011 X-Stat-Signature: 3hfuqnobwbhun5wt7efd1ascjze3ysod X-Rspam-User: X-Rspamd-Server: rspam08 X-HE-Tag: 1673741950-269195 X-HE-Meta: U2FsdGVkX1+gxcbsnxe+tWk4T0+aTV5JUWLImIRdTrj0Anf54u+BKq1SwOqwUxere5ypSyLCyka0S1SYMNg2V45KaIdnX+Xjk028BO70aejun+7As1bGwFKvCFh7rH+Ewjc1Q1Kg3E8k8Sf47r3jT3isoW+dBaXRVwzuptiakbVP2iy14vo/V+FJAAPFOJHB+GxzF3dTPbW0L/vnh1zRABLkhakx8ZG7s3kj+nsdLQUOaSQSS285XGj1pQg9pnT1iDXZURH73mRzON7jI7v0p7DyqMbtafFS8o5kEGgAc/S6dmDPphC6RsFYjee9z1xIpRP8QBbFvO9O9VI31UZd+SNH6ktpz6RcetIn5ZwjgSMgUb3xLZ/BtOv76H9eEomSaSS9C/UaaESvm6ung0HkWvoQVP1v9ewVJoHL0nYVSD4R+s6r+Zl+McclW+nrpUlnqlqi8Fo1ffnhgQMzmVBU8cmuNKvdlXW/wc4DS2f45meB+M5oOV60PnTWIstRPA907H83vIzJS1Nb4zvlt6fKzRwgjGBtdTc7UJEN152OzdehdVQmcwjSqpQ3zDjTo91JkhFhkG32DX9XYOCqDq8QyhGjViu6hCYmWLm8TyQ9p+KwlY5jsCgkC0GLQE55Un3rfJv39erMf1mW3hIxK6q9vWuUhPuyvlrLDG4wi/cibKgI29Wpeg56GwHdAsF22amc5Vw7SUmae9Q0rh4pWp5CqDtyfFHbFdSOxD1ifL1k0KIvwRcSkdDCMTtAO+jYH5383zOrkA2das7Y3ibH7/w6JbXTbF22W5T3VbGCtELqM78xtU6i823gj600jKy2NB2zbLZeVa5Y/2p6Br22uete2F99IgimCChNBRwbKbPPJuScBuvQ9obcz1wHxh4Cr2hP6KxvosOxzbPdE+ysSy1GK3pqu0OrRmaKf23Eusbnb2SWbIy6wbn85Zmt1Z4mcI2clXWkld20jacRYccXyJL bEzYtn6Q OJEE3UtHlI6HASwCQePMgQ+MWRFfUHvVSQbB80pye9ebj4pbhTb5UWm5X/7MB6X6/5J42g43kUq4/AI1KiZx0GvOCrBv/DRav11sCPk95Q8cp1w2JmA1NB2TyWg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000129, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: On Sat, Jan 14, 2023 at 06:26:59PM +0800, Hillf Danton wrote: > On Fri, 13 Jan 2023 23:32:01 -0800 Boqun Feng > > On Sat, Jan 14, 2023 at 03:18:32PM +0800, Hillf Danton wrote: > > > > > > task X task Y > > > --- --- > > > mutex_lock(A); > > > srcu_read_lock(B); > > > srcu_lock_acquire(&B->dep_map); > > > a) lock_map_acquire_read(&B->dep_map); > > > synchronze_srcu(B); > > > __synchronize_srcu(B); > > > srcu_lock_sync(&B->dep_map); > > > lock_map_sync(&B->dep_map); > > > lock_sync(&B->dep_map); > > > __lock_acquire(&B->dep_map); > > > > At this time, lockdep add dependency A -> B in the dependency graph. > > > > > b) lock_map_acquire_read(&B->dep_map); > > > __lock_release(&B->dep_map); > > > c) lock_map_acquire_read(&B->dep_map); > > > mutex_lock(A); > > > > and here, lockdep will try to add dependency B -> A into the dependency > > graph, and find that A -> B -> A will form a circle (with strong > > dependency), therefore lockdep knows it's a deadlock. > > Is the strong dependency applying to mode c)? > If yes then deadlock should be also detected in the following locking > pattern that has no deadlock. > > cpu0 cpu1 > --- --- > mutex_lock A > mutex_lock B > mutex_unlock B > mutex_lock B > mutex_lock A Well, of course, this is how lockdep works. Lockdep detects the *potential* deadlocks rather than detects the deadlocks when they really happen. Otherwise lockdep is useless. The execution in your example shows the potential deadlocks, i.e. one task acquires A and then acquires B, the other task acquires B and then acquires A. Potential deadlocks mean given a correct timing, a deadlock may happen. Regards, Boqun > > > > > > > > No deadlock could be detected if taskY takes mutexA after taskX releases B, > > > > The timing that taskX releases B doesn't master, since lockdep uses > > graph to detect deadlocks rather than after-fact detection. > > > > > and how taskY acquires B does not matter as per the a), b) and c) modes in > > > the above chart, again because releasing lock can break deadlock in general. > > > > I have test cases showing the above deadlock can be detected, so if you > > think there is a deadlock that may dodge from my change, feel free to > > add a test case in lib/locking-selftest.c ;-) > > > > Regards, > > Boqun