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).