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 46F94C004D4 for ; Fri, 20 Jan 2023 02:24:23 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4B9AB6B0072; Thu, 19 Jan 2023 21:24:22 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 4910C6B0073; Thu, 19 Jan 2023 21:24:22 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2E3636B0074; Thu, 19 Jan 2023 21:24:22 -0500 (EST) 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 1D7026B0072 for ; Thu, 19 Jan 2023 21:24:22 -0500 (EST) Received: from smtpin29.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id D8B55AABBA for ; Fri, 20 Jan 2023 02:24:21 +0000 (UTC) X-FDA: 80373583122.29.0D7195A Received: from mail-qt1-f179.google.com (mail-qt1-f179.google.com [209.85.160.179]) by imf14.hostedemail.com (Postfix) with ESMTP id A159810000D for ; Fri, 20 Jan 2023 02:24:19 +0000 (UTC) Authentication-Results: imf14.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=kDK20ncs; spf=pass (imf14.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.160.179 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=1674181459; 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=nXmrGuDkn2/Eo83iFxWHgNA7AWXWKN7q1/fDzp0dVyE=; b=DTU+K6l89nhsF/YYZFn4e5eFixn4salwro/d3s6kN9KgICgnqyd38OxXeW0oT7RzWwFEfv NxxGN/CppYbeBnU+ooPUeunxACn1tx3pFhG4VT/RBv/2iyYRnx69J2BBx2LliCrhHZhYTS e0CIdozM0Mn9D42+i04JSSMLYm8AhBU= ARC-Authentication-Results: i=1; imf14.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=kDK20ncs; spf=pass (imf14.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.160.179 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=1674181459; a=rsa-sha256; cv=none; b=2reSg+83wEfVZefXXGVjn1o/90opi1eoWRTZK1ISmkkVtG1FF0RaA7T4sBbLFonCrUtqIE OlvFSSIVOBAUkdnSbuo0DYyUDkaP10eHUAuR5ZTejR1THr9JFNpYjZ8MFXgDwt5FSNiOj7 kYqqf5ZCo3SJV5AyQ4MGsVcCsWCNDPc= Received: by mail-qt1-f179.google.com with SMTP id d16so3179545qtw.8 for ; Thu, 19 Jan 2023 18:24:19 -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=nXmrGuDkn2/Eo83iFxWHgNA7AWXWKN7q1/fDzp0dVyE=; b=kDK20ncsOnJblkAwd0Y2Y59cRIL8dXnF51upa4ooOnHX1wQqX5ftBtnDYkiI/Ae06M O9EC9eif/MuMYtFZV1lv6hxt1qW/daZXI84Cfd3fVgwCF5++3HWYeNc8a4AQ1Msd2HgR 0rUk339PKVfWEvaGynHDn/OXou0xTF8O6qWOli6Prs6phF8O6aI9W6ur6Q6wyAXPKq+K xksp6hoTxHm8qWWXSfxa68JNytzXV+AXbFHCcrxnkwiKgbOiNlO63r0xUhy3ZES1LXXy T2k9wPS8tOQGlrAQ9zTZXi98iBbGK+SxyQx/qM2oV0MH8GgY8jwHy7XC5e+3u9TwTHVK vKJw== 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=nXmrGuDkn2/Eo83iFxWHgNA7AWXWKN7q1/fDzp0dVyE=; b=6uBdTGOpqVUXWg+IDKi29swDx3wlpIQPGZfG4aRbCVHU72/er665h/kC6Ibq+iHXPP FdMpol3Ib1ZXe/RWLBl1vnZ5mzb1s9kCanCJv1eB2YXn//bYkQjoNfKDeO7qkQIx05x9 lOMlYYHSf+J1PcPMb4Tsb5gycEbjaQjGUg8ffwdZa2PLMhqOMfjSGvRzJDsLHb+WDeR4 a83vBQJy+NVC8QszuBAiZxeoYu1rjPacvrUo9V2Xx9Wszt18yVrtQZB732Pgp4pYIgC/ luLfcHyDI1F2+Na9EMqCyOmv38xbXVNynM+QdrKd7et69rAdYayIbqQHg0sJTZYuyydf pGfA== X-Gm-Message-State: AFqh2kpGud4KPfz7LJdCEhk+YPaZlv5Ak0B/C3OJ4hiVcJlpDU10CCeF /D6MQRtZ4MUGkN3qq6l79nk= X-Google-Smtp-Source: AMrXdXsiMeOE3GgPAmeagT095UwyXmaB30P7mx2mcshrzV0OcQWmOmSytjDTrXm0e3reQk4vMsGu7A== X-Received: by 2002:ac8:58c3:0:b0:3b6:2e8b:3364 with SMTP id u3-20020ac858c3000000b003b62e8b3364mr22935218qta.38.1674181458748; Thu, 19 Jan 2023 18:24:18 -0800 (PST) Received: from auth1-smtp.messagingengine.com (auth1-smtp.messagingengine.com. [66.111.4.227]) by smtp.gmail.com with ESMTPSA id t20-20020ac865d4000000b003ab7aee56a0sm3430879qto.39.2023.01.19.18.24.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 19 Jan 2023 18:24:18 -0800 (PST) Received: from compute6.internal (compute6.nyi.internal [10.202.2.47]) by mailauth.nyi.internal (Postfix) with ESMTP id 7026227C0054; Thu, 19 Jan 2023 21:24:17 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute6.internal (MEProxy); Thu, 19 Jan 2023 21:24:17 -0500 X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvhedrudduuddggeejucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmne cujfgurhepfffhvfevuffkfhggtggujgesthdtredttddtvdenucfhrhhomhepuehoqhhu nhcuhfgvnhhguceosghoqhhunhdrfhgvnhhgsehgmhgrihhlrdgtohhmqeenucggtffrrg htthgvrhhnpeehudfgudffffetuedtvdehueevledvhfelleeivedtgeeuhfegueeviedu ffeivdenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpe gsohhquhhnodhmvghsmhhtphgruhhthhhpvghrshhonhgrlhhithihqdeiledvgeehtdei gedqudejjeekheehhedvqdgsohhquhhnrdhfvghngheppehgmhgrihhlrdgtohhmsehfih igmhgvrdhnrghmvg X-ME-Proxy: Feedback-ID: iad51458e:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 19 Jan 2023 21:24:14 -0500 (EST) Date: Thu, 19 Jan 2023 18:23:49 -0800 From: Boqun Feng To: Byungchul Park Cc: linux-kernel@vger.kernel.org, torvalds@linux-foundation.org, damien.lemoal@opensource.wdc.com, linux-ide@vger.kernel.org, adilger.kernel@dilger.ca, linux-ext4@vger.kernel.org, mingo@redhat.com, peterz@infradead.org, will@kernel.org, tglx@linutronix.de, rostedt@goodmis.org, joel@joelfernandes.org, sashal@kernel.org, daniel.vetter@ffwll.ch, duyuyang@gmail.com, johannes.berg@intel.com, tj@kernel.org, tytso@mit.edu, willy@infradead.org, david@fromorbit.com, amir73il@gmail.com, gregkh@linuxfoundation.org, kernel-team@lge.com, linux-mm@kvack.org, akpm@linux-foundation.org, mhocko@kernel.org, minchan@kernel.org, hannes@cmpxchg.org, vdavydov.dev@gmail.com, sj@kernel.org, jglisse@redhat.com, dennis@kernel.org, cl@linux.com, penberg@kernel.org, rientjes@google.com, vbabka@suse.cz, ngupta@vflare.org, linux-block@vger.kernel.org, paolo.valente@linaro.org, josef@toxicpanda.com, linux-fsdevel@vger.kernel.org, viro@zeniv.linux.org.uk, jack@suse.cz, jlayton@kernel.org, dan.j.williams@intel.com, hch@infradead.org, djwong@kernel.org, dri-devel@lists.freedesktop.org, rodrigosiqueiramelo@gmail.com, melissa.srw@gmail.com, hamohammed.sa@gmail.com, 42.hyeyoo@gmail.com, chris.p.wilson@intel.com, gwan-gyeong.mun@intel.com, max.byungchul.park@gmail.com, longman@redhat.com Subject: Re: [PATCH RFC v7 00/23] DEPT(Dependency Tracker) Message-ID: References: <1674179505-26987-1-git-send-email-byungchul.park@lge.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1674179505-26987-1-git-send-email-byungchul.park@lge.com> X-Rspamd-Server: rspam05 X-Rspamd-Queue-Id: A159810000D X-Stat-Signature: gnf5kkhbqsc6iubizqb4774our7868ko X-Rspam-User: X-HE-Tag: 1674181459-474491 X-HE-Meta: U2FsdGVkX1+/O3MYR1yaAXwsfjEqA09UrJW/oBEUE+HCLQDQjylCVY7csV3Mp6zxL9RuPkCcU6s6g6TsPlueN7RdHqV0bSVzvwGGqFM8jkwYvWCgWQPZnrfQ8nF6soLTIFjHdywhFDaJ45eCOudmHNc514u++BIY20GhmCyE+WLVHYLWhQ7+GimTUgOYrG0gtyfBxxcoin7R4xGFZA+I1m8EAfGFskLeDRItnGkhlLkL9rvKNdDXqdajQTaijr3WfL6AePewdhnRC5c/VvGs9fHNu19/HGX38cmr/jcd9N+8BkFvoBVokcFDhs7xLdzhTNz6EAxNstre+53AVdZEIsmmLGwba7FcHUbTBlto8iJXAsYM6XaELX/QhKoI4CYbDB7XzAKheGCI5SWM8w1Z06XfR4foRoPXs355DjT+dwoflsvqYLUuiVH1Lo+4LzRGfHhkNz8DZ2XddCrt5iAAeqJojqgqZvP5j09bHY9EWmWO2WwGWO3UylrvRM3FC+zhwBhn5DBHGQ0DjW+qpoIdo1WnJ7hwOaCkF8T/kWojolpHbkVfsGpOg0cDFMEham7x5+yZ8xTRICqDcdhw2QFlQ50hyR+Mcsu8RQw3qNLiNZ7Gv7gsycI3PcvV53dOfrR5zq+YSr2I8SPEG8i8+aTm5Sa8FEc0mxKS0atfY6l+wwUMAQ8VXYnoxjWyy4TsVT4tc0gwUJIkHy7v3krePQPzXXN/X5d32kysDgBn8KQidodRXqUe8xB0i2BAKtDkfel6nbLPNVO+dW4PHmPdgmAP5x65pSkAw/FmvAOWjln6HgFP2IO7g3lrBXeGXpA0i07EP7GwPRN9rqLXgPUwXTKr/AUCRcrnU8OnHHQFkq4q2OxgyM8NeofGdefOjWKJQckeWkS6K9A7wygtpcH3Vc5xIFNOVdJBpq6Yv7vH/oQQbfd5BZQfYVE96mEadt26CQiU6DEW2+/iUwEIIS44yYX 7vgs+4tW FSkRwCjEvUlLIdgliQ6ohfjIte+vGgBd+x8quKjS8g140nXk36Y9xvZZmS5Iv95kcxxrPzQYn+j4tAL+fR5GyawH7mht5Qtd663L3cm6Bb3BiiTh2Zme7PIXk9Bf3qHLGeYPuNnUP7ztk5d544rHYM+MZkaBxpgLUiIP4S/p5iMd1307x5gpkETFJcwrdfvPJa2sGI0oPB6bxFvI5zGYqpDMek2c1qmRNF4+ZKA22bS5Ihu8RjYYV6zOkEfMuYSaq7D5Z3BrJkuly4Fl63EWj/QO3Z8dAUMWQ4fwG8/6eVc6JHF34flYXYKsjKYKrHokMjf+CO8OVBadQvtFHg2AL4o03dSnFkV6ZFp2l46Ho3wSOxC9Coz9uV+30N6w8VyqpTyvAHswtMoZkvg1kk+A7XSbJCqWw2az7tX8tP/VAmIA/1aO1+MLG9ZveTqJlqWzK24Dp+Q2/eBstgZE2aXkBBElMOA6DbI66SPwnhJmyWEOWnSCZIJjDARSfh5pjpU45V36ydm1oL+0OhO7qR02VeWRvWw== 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: On Fri, Jan 20, 2023 at 10:51:45AM +0900, Byungchul Park wrote: > Boqun wrote: > > On Thu, Jan 19, 2023 at 01:33:58PM +0000, Matthew Wilcox wrote: > > > On Thu, Jan 19, 2023 at 03:23:08PM +0900, Byungchul Park wrote: > > > > Boqun wrote: > > > > > *Looks like the DEPT dependency graph doesn't handle the > > > > > fair/unfair readers as lockdep current does. Which bring the > > > > > next question. > > > > > > > > No. DEPT works better for unfair read. It works based on wait/event. So > > > > read_lock() is considered a potential wait waiting on write_unlock() > > > > while write_lock() is considered a potential wait waiting on either > > > > write_unlock() or read_unlock(). DEPT is working perfect for it. > > > > > > > > For fair read (maybe you meant queued read lock), I think the case > > > > should be handled in the same way as normal lock. I might get it wrong. > > > > Please let me know if I miss something. > > > > > > From the lockdep/DEPT point of view, the question is whether: > > > > > > read_lock(A) > > > read_lock(A) > > > > > > can deadlock if a writer comes in between the two acquisitions and > > > sleeps waiting on A to be released. A fair lock will block new > > > readers when a writer is waiting, while an unfair lock will allow > > > new readers even while a writer is waiting. > > > > > > > To be more accurate, a fair reader will wait if there is a writer > > waiting for other reader (fair or not) to unlock, and an unfair reader > > won't. > > What a kind guys, both of you! Thanks. > > I asked to check if there are other subtle things than this. Fortunately, > I already understand what you guys shared. > > > In kernel there are read/write locks that can have both fair and unfair > > readers (e.g. queued rwlock). Regarding deadlocks, > > > > T0 T1 T2 > > -- -- -- > > fair_read_lock(A); > > write_lock(B); > > write_lock(A); > > write_lock(B); > > unfair_read_lock(A); > > With the DEPT's point of view (let me re-write the scenario): > > T0 T1 T2 > -- -- -- > fair_read_lock(A); > write_lock(B); > write_lock(A); > write_lock(B); > unfair_read_lock(A); > write_unlock(B); > read_unlock(A); > read_unlock(A); > write_unlock(B); > write_unlock(A); > > T0: read_unlock(A) cannot happen if write_lock(B) is stuck by a B owner > not doing either write_unlock(B) or read_unlock(B). In other words: > > 1. read_unlock(A) happening depends on write_unlock(B) happening. > 2. read_unlock(A) happening depends on read_unlock(B) happening. > > T1: write_unlock(B) cannot happen if unfair_read_lock(A) is stuck by a A > owner not doing write_unlock(A). In other words: > > 3. write_unlock(B) happening depends on write_unlock(A) happening. > > 1, 2 and 3 give the following dependencies: > > 1. read_unlock(A) -> write_unlock(B) > 2. read_unlock(A) -> read_unlock(B) > 3. write_unlock(B) -> write_unlock(A) > > There's no circular dependency so it's safe. DEPT doesn't report this. > > > the above is not a deadlock, since T1's unfair reader can "steal" the > > lock. However the following is a deadlock: > > > > T0 T1 T2 > > -- -- -- > > unfair_read_lock(A); > > write_lock(B); > > write_lock(A); > > write_lock(B); > > fair_read_lock(A); > > > > , since T'1 fair reader will wait. > > With the DEPT's point of view (let me re-write the scenario): > > T0 T1 T2 > -- -- -- > unfair_read_lock(A); > write_lock(B); > write_lock(A); > write_lock(B); > fair_read_lock(A); > write_unlock(B); > read_unlock(A); > read_unlock(A); > write_unlock(B); > write_unlock(A); > > T0: read_unlock(A) cannot happen if write_lock(B) is stuck by a B owner > not doing either write_unlock(B) or read_unlock(B). In other words: > > 1. read_unlock(A) happening depends on write_unlock(B) happening. > 2. read_unlock(A) happening depends on read_unlock(B) happening. > > T1: write_unlock(B) cannot happen if fair_read_lock(A) is stuck by a A > owner not doing either write_unlock(A) or read_unlock(A). In other > words: > > 3. write_unlock(B) happening depends on write_unlock(A) happening. > 4. write_unlock(B) happening depends on read_unlock(A) happening. > > 1, 2, 3 and 4 give the following dependencies: > > 1. read_unlock(A) -> write_unlock(B) > 2. read_unlock(A) -> read_unlock(B) > 3. write_unlock(B) -> write_unlock(A) > 4. write_unlock(B) -> read_unlock(A) > > With 1 and 4, there's a circular dependency so DEPT definitely report > this as a problem. > > REMIND: DEPT focuses on waits and events. Do you have the test cases showing DEPT can detect this? Regards, Boqun > > > FWIW, lockdep is able to catch this (figuring out which is deadlock and > > which is not) since two years ago, plus other trivial deadlock detection > > for read/write locks. Needless to say, if lib/lock-selftests.c was given > > a try, one could find it out on one's own. > > > > Regards, > > Boqun > >