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 76E4AC6379F for ; Thu, 19 Jan 2023 19:25:48 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id CD9826B0072; Thu, 19 Jan 2023 14:25:47 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id C895C6B0073; Thu, 19 Jan 2023 14:25:47 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B03CB6B0074; Thu, 19 Jan 2023 14:25:47 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id A0C6A6B0072 for ; Thu, 19 Jan 2023 14:25:47 -0500 (EST) Received: from smtpin18.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 74B93C0D9D for ; Thu, 19 Jan 2023 19:25:47 +0000 (UTC) X-FDA: 80372528334.18.1B4355D Received: from mail-qt1-f169.google.com (mail-qt1-f169.google.com [209.85.160.169]) by imf14.hostedemail.com (Postfix) with ESMTP id 4C07B100009 for ; Thu, 19 Jan 2023 19:25:45 +0000 (UTC) Authentication-Results: imf14.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=MrwOCC5e; spf=pass (imf14.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.160.169 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=1674156345; 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=xamYJZSiEPy9Mjo2njH+JPn5/UHZCpsx0WYfjjoyGiY=; b=ghO0ATrUMXvSznSgnZ+1d8aqxKkPBeSe2PnUiQGMGDKfFNCWeeuWpg/BivEXfXmJwtBW/+ QMYmN2MG89t3EWQMj2VOQKBW8/6LRn0Qaka8Z0uR40QvfDsp5QGy2YjAmIXBmVjM3cpPCf 51Ej1F5AVfh0VQBGMh4mRhpmXJX+WwA= ARC-Authentication-Results: i=1; imf14.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=MrwOCC5e; spf=pass (imf14.hostedemail.com: domain of boqun.feng@gmail.com designates 209.85.160.169 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=1674156345; a=rsa-sha256; cv=none; b=wHJHop8LPTlRd4ExuvFtfQIX8GaieTCrEn+7sIbGTqFSngsliD/qlzpys0LUv2Li2zgOUc 4Anui7nw+nLFQJiZndwNNr34rybs7dNUvp2xLsoiMsO983WP7LnY6fKcWX+fMeEKQNhPPi QNx3xMqq59YyhTvXM1268l2p3e1dGoM= Received: by mail-qt1-f169.google.com with SMTP id h21so2350469qta.12 for ; Thu, 19 Jan 2023 11:25:45 -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=xamYJZSiEPy9Mjo2njH+JPn5/UHZCpsx0WYfjjoyGiY=; b=MrwOCC5ehcze1hpMjcT+s1KhKEgcE4YPuq3yqI1Cm5uRCIw1PUevaLEC6XkTcNhbT9 Zw0OvgbmLEFdn1tUM2fjgufvEQCRxf9F5A/ADdKpwTfdOwWf/0FqKiy1RuuQeUDtT2r1 WOQNX4WCd5xldt11cYOVTcAYa8grKYNOtlZuJLBY7Hqr8xr25RNCaSO7DWHMR1iJ2wZ4 jILLDKWwZP8GiSLOga1KZkHZ1Quhj6gfAe4Q0cx1AezAz9Aw7s1aRjjoXenbgYqQO8nm QgeiFuARK8oNcrVywEUZQ78eB39jl9apcTRWslHRMXoRBD4K3HuCxamntvSxOTPxK4uE BODA== 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=xamYJZSiEPy9Mjo2njH+JPn5/UHZCpsx0WYfjjoyGiY=; b=Y1C5/iZj+EWDUrOYe84Au8JX6zALYxDIgsOi63cEk4imQiITDLkXrxNzGmVpJTVo9e dr57TBUQraeipqfk8wucFtAmCQ77NBe70gYaSer+wBkQ5ZgmU+FUKh8ybATTFblqrQJY 4RzSFYh9mbF2whG0MIkdFGkTzmulgGE/dLpbKUd3LkqjnN36Hi+ByYr5wTDNFdzt9Ur+ 6AV9tJeUCvO09JmN6af5u7/Imfs20+++SbXT5lW0mFSvqTxTrB+TU/wqZMbnGJ6c6KJ1 yFaskv0OK94Uk+/9fJ1wctm9OO4x4vQ4wx/F3sjEh3d6hcouNFh25OHdL14VZs8r4Emr 0y/g== X-Gm-Message-State: AFqh2krd7LwXmhQWn81vxoMptulhqUoxeRsYziB/r2q3SOy4tvF61SYc dt1tCuA8BwPxxs1QgALnLAY= X-Google-Smtp-Source: AMrXdXsoLGLbfa/acc8BBfWydzzE0cdc7MVdwvIQKEjpx0fPhQGQygjmLuqjO93xlt2Ff3JyRVvFJw== X-Received: by 2002:a05:622a:5c8c:b0:3ab:b632:fa95 with SMTP id ge12-20020a05622a5c8c00b003abb632fa95mr17852071qtb.44.1674156344443; Thu, 19 Jan 2023 11:25:44 -0800 (PST) Received: from auth2-smtp.messagingengine.com (auth2-smtp.messagingengine.com. [66.111.4.228]) by smtp.gmail.com with ESMTPSA id fu28-20020a05622a5d9c00b003a7f3c4dcdfsm19389879qtb.47.2023.01.19.11.25.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 19 Jan 2023 11:25:44 -0800 (PST) Received: from compute6.internal (compute6.nyi.internal [10.202.2.47]) by mailauth.nyi.internal (Postfix) with ESMTP id 20B2C27C0054; Thu, 19 Jan 2023 14:25:42 -0500 (EST) Received: from mailfrontend1 ([10.202.2.162]) by compute6.internal (MEProxy); Thu, 19 Jan 2023 14:25:43 -0500 X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvhedruddutddguddviecutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpeffhffvvefukfhfgggtuggjsehttdertddttddvnecuhfhrohhmpeeuohhq uhhnucfhvghnghcuoegsohhquhhnrdhfvghnghesghhmrghilhdrtghomheqnecuggftrf grthhtvghrnhephedugfduffffteeutddvheeuveelvdfhleelieevtdeguefhgeeuveei udffiedvnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomh epsghoqhhunhdomhgvshhmthhprghuthhhphgvrhhsohhnrghlihhthidqieelvdeghedt ieegqddujeejkeehheehvddqsghoqhhunhdrfhgvnhhgpeepghhmrghilhdrtghomhesfh higihmvgdrnhgrmhgv X-ME-Proxy: Feedback-ID: iad51458e:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Thu, 19 Jan 2023 14:25:40 -0500 (EST) Date: Thu, 19 Jan 2023 11:25:16 -0800 From: Boqun Feng To: Matthew Wilcox Cc: Byungchul Park , 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, 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: <1674109388-6663-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: X-Stat-Signature: wxura4irabpn4sswqt6xfqpowinzi5bk X-Rspam-User: X-Rspamd-Queue-Id: 4C07B100009 X-Rspamd-Server: rspam06 X-HE-Tag: 1674156345-470925 X-HE-Meta: U2FsdGVkX19mYsQwM50NBdvbnPePr28CsqUo5guXVzlzR2uPcAMbgIIQ4Vjdyv6zEmE977vx8SpiBLhwCkAWJReWOHHFtKDBxMlmJi1h3GO3qufFlRT+VqPO9zVIjckzQXovxtjOQYM1j/hOI7FY+hXjcNIDQDY4CxJusSGlPaAjOhwN3MSpLBaCIn9C7vq+kG0fOUyjmutgZ6kjAgW+0/udiq89y2A6BIuCmTiWjKyHJQYRZu9HUXvVga1rJxTzPfuUE3Gnq5TeyLKULtxebvSgx8lanLttt8cD+ga4NYvsJj2W5ozMq79AImbS5OzFpBrCQZvKHK/mNpyZA7IL4eH6gjlRRCd2I3daUZLRrRel5ZCjD3MuWjG8qAnShLKXeb5Nvs4aW3hv4XTaQelMYhrHQk58RhLJfkAtw1boa2RKj93ZW8lQf4ZsXIra3GgxhnZyRRIw/6inzEu44cl3BFOFQt/g+grs5dS+wb1uQju9HSLiaRzCcnJxFQcBIeJzPS/5hW5J170K1uv7rKU+T2SE3L3mMjoYW4tFrN+1eyU1adf1L7IvRMGGy5VRGF1vOXT6CGmzY2SY8ln6qKrP2vG422LY6GbCQuqiGdZzE69QuwYvkMxQXdxktPBj4SNLq7j8rd8cKKXG0LLIof5bEyKQW4/WD6WeJ91VZxJVlPdYrjk1hAr0abxKNITBqXSOxiOTpleVXUxqpHwInbxgm6OYO/DIq8Dd8/j0aIBUE0nDrkNZk0fSQPV1VlDR6HEuK6X13NUvqQBiLI2hqA1dAJIV1D2S245REgHqXse2oTHp2Epi3wFOUA2ZnvIcmRcAz4rBxlDnXKQVnSgAmdHWyGHU5hKqgQhBThA/hL5GsgLltXqPqOVjyX7hyoIys/lUFIKlMIQf6geE9owBoWp116XdG30OX6NSP8guZHAwSZAjyjZInP4oUwGMbn8w+jLUu7/i4Ob7vYIwAD2U0kt U34nhhGB N+JUKmxHG8hZLcE1+fYAc/EovOzO6e3yA3wz5RRgGOViNuPsc8yXrf3GLlNuG3/DvhC2ZINnduMa0bp7wO9Gk3b72392TZRXPywbfzLb8fWmyKn39Pptbkl5QK8jYUsuKbnO9vgkgh2fPYb0eARg/nNuAtF/BIZdH57nhbOszc3kz+hG/SqAVU0Gz4cT8bXDKfeleNd2fnCu1xQMUkrJ2wPvLPe2SSzO4GNjZU1Unih6H0nTjxWtkOyCKfQhLnCZNbNNauBhEonH3+0wjMaGDlwtFpc/6rNJUbg+nt3wlTR4euqL8k0DpKJsowxj65o8SlOz4lmI0Ct/CXy+7yUfZPYkCBZLaBxbiFoMEuFkf3kcxNiTQ8L8w4eU639oowXeLjY8mtVsLRjAGeT08X7XW44IFf/YrmcTpjh43CDX2p2Y7kVJWmzUPoQnhqc4U5vWqQxqaTGEBAmrK7Txg1kRi0ojOgnZmNXrB5QixGiF8KAsEk5Ohks7a1eDOU6JDpii2m6azn7efggwfKtHzN/tFImhFUA== 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 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. 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); 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. 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