From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752075AbdJYHH3 (ORCPT ); Wed, 25 Oct 2017 03:07:29 -0400 Received: from esa1.hgst.iphmx.com ([68.232.141.245]:47854 "EHLO esa1.hgst.iphmx.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751421AbdJYHH0 (ORCPT ); Wed, 25 Oct 2017 03:07:26 -0400 X-IronPort-AV: E=Sophos;i="5.43,430,1503331200"; d="scan'208";a="162106781" From: Bart Van Assche To: "byungchul.park@lge.com" CC: "mingo@kernel.org" , "linux-kernel@vger.kernel.org" , "peterz@infradead.org" , "hch@infradead.org" , "amir73il@gmail.com" , "linux-xfs@vger.kernel.org" , "tglx@linutronix.de" , "linux-mm@kvack.org" , "oleg@redhat.com" , "linux-block@vger.kernel.org" , "darrick.wong@oracle.com" , "johannes.berg@intel.com" , "max.byungchul.park@gmail.com" , "linux-fsdevel@vger.kernel.org" , "idryomov@gmail.com" , "tj@kernel.org" , "kernel-team@lge.com" , "david@fromorbit.com" Subject: Re: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map Thread-Topic: [RESEND PATCH 1/3] completion: Add support for initializing completion with lockdep_map Thread-Index: AQHTR/T3eL1/ixvRQkSJ6yiAuin4s6Lr0sMAgAB4UQCAAOC2AIAAa5gAgAJejgCAAMHAAIADeBwA Date: Wed, 25 Oct 2017 07:07:06 +0000 Message-ID: <1508915222.2947.15.camel@wdc.com> References: <1508319532-24655-1-git-send-email-byungchul.park@lge.com> <1508319532-24655-2-git-send-email-byungchul.park@lge.com> <1508455438.4542.4.camel@wdc.com> <1508529532.3029.15.camel@wdc.com> <1508682894.2564.8.camel@wdc.com> <20171023020822.GI3310@X58A-UD3R> In-Reply-To: <20171023020822.GI3310@X58A-UD3R> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Bart.VanAssche@wdc.com; x-originating-ip: [147.75.100.161] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1;CY1PR0401MB1535;20:T0WP3r0pEx9EP65uhiOiejNemjT0hPJ0XPAk/2PP9rOMXbbzzyIa9oef2LgclecPSglQW9Mqw45xxqyphACHKMm9uDcIxelJY+z76F8OJH7aNAZj8sFqMXmxCsegUgEKQT7ZfOyynkiP5/hYE2lr647+yAEnbnnNoqVJXk9U+1g= x-ms-exchange-antispam-srfa-diagnostics: SSOS; x-ms-office365-filtering-correlation-id: 96f6f695-9d0e-4c6e-7c29-08d51b770098 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:(22001)(48565401081)(4534020)(4602075)(4627075)(201703031133081)(201702281549075)(2017052603199);SRVR:CY1PR0401MB1535; x-ms-traffictypediagnostic: CY1PR0401MB1535: wdcipoutbound: EOP-TRUE x-exchange-antispam-report-test: UriScan:; x-microsoft-antispam-prvs: x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(6040450)(2401047)(8121501046)(5005006)(93006095)(93001095)(100000703101)(100105400095)(3231020)(3002001)(10201501046)(6055026)(6041248)(20161123558100)(20161123564025)(20161123555025)(20161123562025)(20161123560025)(201703131423075)(201702281528075)(201703061421075)(201703061406153)(6072148)(201708071742011)(100000704101)(100105200095)(100000705101)(100105500095);SRVR:CY1PR0401MB1535;BCL:0;PCL:0;RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(100000804101)(100110200095)(100000805101)(100110500095);SRVR:CY1PR0401MB1535; x-forefront-prvs: 0471B73328 x-forefront-antispam-report: SFV:NSPM;SFS:(10019020)(6009001)(39860400002)(346002)(376002)(189002)(377424004)(199003)(24454002)(54906003)(2900100001)(3846002)(50986999)(103116003)(4326008)(3280700002)(54356999)(105586002)(229853002)(101416001)(4001150100001)(8936002)(36756003)(77096006)(81166006)(6436002)(68736007)(7736002)(97736004)(102836003)(81156014)(76176999)(6246003)(25786009)(6116002)(6506006)(189998001)(6486002)(5640700003)(3660700001)(305945005)(8676002)(106356001)(86362001)(72206003)(99286003)(7416002)(39060400002)(53546010)(5660300001)(316002)(478600001)(53936002)(6512007)(2906002)(66066001)(2351001)(14454004)(2950100002)(6916009)(93886005)(33646002)(2501003)(217873001);DIR:OUT;SFP:1102;SCL:1;SRVR:CY1PR0401MB1535;H:CY1PR0401MB1536.namprd04.prod.outlook.com;FPR:;SPF:None;PTR:InfoNoRecords;MX:1;A:1;LANG:en; spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="utf-8" Content-ID: <53F10DDA73D0334D8FA30A344F17E505@namprd04.prod.outlook.com> MIME-Version: 1.0 X-OriginatorOrg: wdc.com X-MS-Exchange-CrossTenant-Network-Message-Id: 96f6f695-9d0e-4c6e-7c29-08d51b770098 X-MS-Exchange-CrossTenant-originalarrivaltime: 25 Oct 2017 07:07:06.6438 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: b61c8803-16f3-4c35-9b17-6f65f441df86 X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY1PR0401MB1535 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by nfs id v9P77XjM030672 On Mon, 2017-10-23 at 11:08 +0900, Byungchul Park wrote: > On Sun, Oct 22, 2017 at 02:34:56PM +0000, Bart Van Assche wrote: > > On Sat, 2017-10-21 at 11:23 +0900, Byungchul Park wrote: > > > On Sat, Oct 21, 2017 at 4:58 AM, Bart Van Assche wrote: > > > > As explained in another e-mail thread, unlike the lock inversion checking > > > > performed by the <= v4.13 lockdep code, cross-release checking is a heuristic > > > > that does not have a sound theoretical basis. The lock validator is an > > > > > > It's not heuristic but based on the same theoretical basis as <=4.13 > > > lockdep. I mean, the key basis is: > > > > > > 1) What causes deadlock > > > 2) What is a dependency > > > 3) Build a dependency when identified > > > > Sorry but I doubt that that statement is correct. The publication [1] contains > > IMHO, the paper is talking about totally different things wrt > deadlocks by wait_for_event/event, that is, lost events. Please reread the paper title. The authors of the paper explain that their algorithm can detect lost events but the most significant contribution of the paper is deadlock detection. > > false positives for programs that only use mutexes as synchronization objects. > > I want to ask you. What makes false positives avoidable in the paper? The algorithm used to detect deadlocks. That algorithm has been explained clearly in the paper. > > The comment of the authors of that paper for programs that use mutexes, > > condition variables and semaphores is as follows: "It is unclear how to extend > > the lock-graph-based algorithm in Section 3 to efficiently consider the effects > > of condition variables and semaphores. Therefore, when considering all three > > synchronization mechanisms, we currently use a naive algorithm that checks each > > feasible permutation of the trace for deadlock." In other words, if you have > > found an approach for detecting potential deadlocks for programs that use these > > three kinds of synchronization objects and that does not report false positives > > then that's a breakthrough that's worth publishing in a journal or in the > > proceedings of a scientific conference. > > Please, point out logical problems of cross-release than saying it's > impossbile according to the paper. Isn't that the same? If it's impossible to use lock-graphs for detecting deadlocks in programs that use mutexes, semaphores and condition variables without triggering false positives that means that every approach that tries to detect deadlocks and that is based on lock graphs, including cross-release, must report false positives for certain programs. Bart.