From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from esa5.hgst.iphmx.com ([216.71.153.144]:45501 "EHLO esa5.hgst.iphmx.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751003AbdJVOfE (ORCPT ); Sun, 22 Oct 2017 10:35:04 -0400 From: Bart Van Assche To: "max.byungchul.park@gmail.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" , "byungchul.park@lge.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 Date: Sun, 22 Oct 2017 14:34:56 +0000 Message-ID: <1508682894.2564.8.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> In-Reply-To: Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Sender: linux-block-owner@vger.kernel.org List-Id: linux-block@vger.kernel.org T24gU2F0LCAyMDE3LTEwLTIxIGF0IDExOjIzICswOTAwLCBCeXVuZ2NodWwgUGFyayB3cm90ZToN Cj4gT24gU2F0LCBPY3QgMjEsIDIwMTcgYXQgNDo1OCBBTSwgQmFydCBWYW4gQXNzY2hlIDxCYXJ0 LlZhbkFzc2NoZUB3ZGMuY29tPiB3cm90ZToNCj4gPiBBcyBleHBsYWluZWQgaW4gYW5vdGhlciBl LW1haWwgdGhyZWFkLCB1bmxpa2UgdGhlIGxvY2sgaW52ZXJzaW9uIGNoZWNraW5nDQo+ID4gcGVy Zm9ybWVkIGJ5IHRoZSA8PSB2NC4xMyBsb2NrZGVwIGNvZGUsIGNyb3NzLXJlbGVhc2UgY2hlY2tp bmcgaXMgYSBoZXVyaXN0aWMNCj4gPiB0aGF0IGRvZXMgbm90IGhhdmUgYSBzb3VuZCB0aGVvcmV0 aWNhbCBiYXNpcy4gVGhlIGxvY2sgdmFsaWRhdG9yIGlzIGFuDQo+IA0KPiBJdCdzIG5vdCBoZXVy aXN0aWMgYnV0IGJhc2VkIG9uIHRoZSBzYW1lIHRoZW9yZXRpY2FsIGJhc2lzIGFzIDw9NC4xMw0K PiBsb2NrZGVwLiBJIG1lYW4sIHRoZSBrZXkgYmFzaXMgaXM6DQo+IA0KPiAgICAxKSBXaGF0IGNh dXNlcyBkZWFkbG9jaw0KPiAgICAyKSBXaGF0IGlzIGEgZGVwZW5kZW5jeQ0KPiAgICAzKSBCdWls ZCBhIGRlcGVuZGVuY3kgd2hlbiBpZGVudGlmaWVkDQoNClNvcnJ5IGJ1dCBJIGRvdWJ0IHRoYXQg dGhhdCBzdGF0ZW1lbnQgaXMgY29ycmVjdC4gVGhlIHB1YmxpY2F0aW9uIFsxXSBjb250YWlucw0K YSBwcm9vZiB0aGF0IGFuIGFsZ29yaXRobSB0aGF0IGlzIGNsb3NlbHkgcmVsYXRlZCB0byB0aGUg dHJhZGl0aW9uYWwgbG9ja2RlcA0KbG9jayBpbnZlcnNpb24gZGV0ZWN0b3IgaXMgYWJsZSB0byBk ZXRlY3QgYWxsIGRlYWRsb2NrcyBhbmQgZG9lcyBub3QgcmVwb3J0DQpmYWxzZSBwb3NpdGl2ZXMg Zm9yIHByb2dyYW1zIHRoYXQgb25seSB1c2UgbXV0ZXhlcyBhcyBzeW5jaHJvbml6YXRpb24gb2Jq ZWN0cy4NClRoZSBjb21tZW50IG9mIHRoZSBhdXRob3JzIG9mIHRoYXQgcGFwZXIgZm9yIHByb2dy YW1zIHRoYXQgdXNlIG11dGV4ZXMsDQpjb25kaXRpb24gdmFyaWFibGVzIGFuZCBzZW1hcGhvcmVz IGlzIGFzIGZvbGxvd3M6ICJJdCBpcyB1bmNsZWFyIGhvdyB0byBleHRlbmQNCnRoZSBsb2NrLWdy YXBoLWJhc2VkIGFsZ29yaXRobSBpbiBTZWN0aW9uIDMgdG8gZWZmaWNpZW50bHkgY29uc2lkZXIg dGhlIGVmZmVjdHMNCm9mIGNvbmRpdGlvbiB2YXJpYWJsZXMgYW5kIHNlbWFwaG9yZXMuIFRoZXJl Zm9yZSwgd2hlbiBjb25zaWRlcmluZyBhbGwgdGhyZWUNCnN5bmNocm9uaXphdGlvbiBtZWNoYW5p c21zLCB3ZSBjdXJyZW50bHkgdXNlIGEgbmFpdmUgYWxnb3JpdGhtIHRoYXQgY2hlY2tzIGVhY2gN CmZlYXNpYmxlIHBlcm11dGF0aW9uIG9mIHRoZSB0cmFjZSBmb3IgZGVhZGxvY2suIiBJbiBvdGhl ciB3b3JkcywgaWYgeW91IGhhdmUNCmZvdW5kIGFuIGFwcHJvYWNoIGZvciBkZXRlY3RpbmcgcG90 ZW50aWFsIGRlYWRsb2NrcyBmb3IgcHJvZ3JhbXMgdGhhdCB1c2UgdGhlc2UNCnRocmVlIGtpbmRz IG9mIHN5bmNocm9uaXphdGlvbiBvYmplY3RzIGFuZCB0aGF0IGRvZXMgbm90IHJlcG9ydCBmYWxz ZSBwb3NpdGl2ZXMNCnRoZW4gdGhhdCdzIGEgYnJlYWt0aHJvdWdoIHRoYXQncyB3b3J0aCBwdWJs aXNoaW5nIGluIGEgam91cm5hbCBvciBpbiB0aGUNCnByb2NlZWRpbmdzIG9mIGEgc2NpZW50aWZp YyBjb25mZXJlbmNlLg0KDQpCYXJ0Lg0KDQpbMV0gQWdhcndhbCwgUmFodWwsIGFuZCBTY290dCBE LiBTdG9sbGVyLiAiUnVuLXRpbWUgZGV0ZWN0aW9uIG9mIHBvdGVudGlhbA0KZGVhZGxvY2tzIGZv ciBwcm9ncmFtcyB3aXRoIGxvY2tzLCBzZW1hcGhvcmVzLCBhbmQgY29uZGl0aW9uIHZhcmlhYmxl cy4iIEluDQpQcm9jZWVkaW5ncyBvZiB0aGUgMjAwNiB3b3Jrc2hvcCBvbiBQYXJhbGxlbCBhbmQg ZGlzdHJpYnV0ZWQgc3lzdGVtczogdGVzdGluZw0KYW5kIGRlYnVnZ2luZywgcHAuIDUxLTYwLiBB Q00sIDIwMDYuDQooaHR0cHM6Ly9wZGZzLnNlbWFudGljc2Nob2xhci5vcmcvOTMyNC9mYzBiNWQ1 Y2Q1ZTA1ZDU1MWEzZTk4NzU3MTIyMDM5OTQ2YTIucGRmKS4= From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751479AbdJVOfH (ORCPT ); Sun, 22 Oct 2017 10:35:07 -0400 Received: from esa5.hgst.iphmx.com ([216.71.153.144]:45501 "EHLO esa5.hgst.iphmx.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751003AbdJVOfE (ORCPT ); Sun, 22 Oct 2017 10:35:04 -0400 X-IronPort-AV: E=Sophos;i="5.43,417,1503331200"; d="scan'208";a="59142951" From: Bart Van Assche To: "max.byungchul.park@gmail.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" , "byungchul.park@lge.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/ixvRQkSJ6yiAuin4s6Lr0sMAgAB4UQCAAOC2AIAAa5gAgAJejgA= Date: Sun, 22 Oct 2017 14:34:56 +0000 Message-ID: <1508682894.2564.8.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> In-Reply-To: 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: [31.221.87.68] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1;CY1PR0401MB1536;20:tKNMjcHlwNfA2kAXVlsU6dlR6TqadWyJnqMn1664Hcl3u1VJaLlJTswW2f8JfsZgzSbYyqbFF/TMc6RBAJ/Z3PaaT/gcv2UAlIZoSYvEziWKPVHw0p0R0v2IZrRGientZGyti43HjjfyoqvHUGeiJP/P01WGvg2CTSuEqWQiJzc= x-ms-exchange-antispam-srfa-diagnostics: SSOS; x-ms-office365-filtering-correlation-id: 8421d064-d734-4dcc-00f8-08d5195a1113 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:(22001)(48565401081)(4534020)(4602075)(4627075)(201703031133081)(201702281549075)(2017052603199);SRVR:CY1PR0401MB1536; x-ms-traffictypediagnostic: CY1PR0401MB1536: 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)(3231020)(100000703101)(100105400095)(10201501046)(3002001)(93006095)(93001095)(6055026)(6041248)(20161123555025)(20161123562025)(20161123560025)(20161123564025)(20161123558100)(201703131423075)(201702281528075)(201703061421075)(201703061406153)(6072148)(201708071742011)(100000704101)(100105200095)(100000705101)(100105500095);SRVR:CY1PR0401MB1536;BCL:0;PCL:0;RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(100000804101)(100110200095)(100000805101)(100110500095);SRVR:CY1PR0401MB1536; x-forefront-prvs: 0468FE4A2B x-forefront-antispam-report: SFV:NSPM;SFS:(10019020)(6009001)(39860400002)(376002)(346002)(189002)(377424004)(199003)(24454002)(86362001)(81156014)(575784001)(316002)(5660300001)(305945005)(81166006)(53936002)(4001150100001)(2906002)(229853002)(105586002)(6436002)(72206003)(3280700002)(1361003)(66066001)(7416002)(4326008)(7736002)(77096006)(6116002)(3846002)(102836003)(53546010)(97736004)(2501003)(2950100002)(6916009)(5640700003)(93886005)(76176999)(68736007)(101416001)(8676002)(103116003)(6246003)(189998001)(99286003)(6306002)(14454004)(33646002)(2900100001)(50986999)(25786009)(6512007)(3660700001)(39060400002)(8936002)(6506006)(36756003)(54356999)(106356001)(6486002)(54906003)(478600001)(2351001)(217873001);DIR:OUT;SFP:1102;SCL:1;SRVR:CY1PR0401MB1536;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: MIME-Version: 1.0 X-OriginatorOrg: wdc.com X-MS-Exchange-CrossTenant-originalarrivaltime: 22 Oct 2017 14:34:56.3564 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: b61c8803-16f3-4c35-9b17-6f65f441df86 X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY1PR0401MB1536 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 v9MEZDAr019500 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 a proof that an algorithm that is closely related to the traditional lockdep lock inversion detector is able to detect all deadlocks and does not report false positives for programs that only use mutexes as synchronization objects. 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. Bart. [1] Agarwal, Rahul, and Scott D. Stoller. "Run-time detection of potential deadlocks for programs with locks, semaphores, and condition variables." In Proceedings of the 2006 workshop on Parallel and distributed systems: testing and debugging, pp. 51-60. ACM, 2006. (https://pdfs.semanticscholar.org/9324/fc0b5d5cd5e05d551a3e98757122039946a2.pdf).