From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751468AbcA0ACh (ORCPT ); Tue, 26 Jan 2016 19:02:37 -0500 Received: from mail-bl2on0090.outbound.protection.outlook.com ([65.55.169.90]:44256 "EHLO na01-bl2-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1750826AbcA0ACe (ORCPT ); Tue, 26 Jan 2016 19:02:34 -0500 Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=Felix.Kuehling@amd.com; From: Felix Kuehling Subject: Re: Lockdep incorrectly complaining about circular dependencies involving read-locks To: References: <56A159C0.2020000@amd.com> X-Enigmail-Draft-Status: N1110 Organization: AMD Inc. Message-ID: <56A805D2.20903@amd.com> Date: Tue, 26 Jan 2016 18:48:34 -0500 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.5.1 MIME-Version: 1.0 In-Reply-To: <56A159C0.2020000@amd.com> Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit X-Originating-IP: [165.204.55.251] X-ClientProxiedBy: SN1PR18CA0015.namprd18.prod.outlook.com (25.163.219.153) To BY2PR1201MB1000.namprd12.prod.outlook.com (25.164.167.142) X-Microsoft-Exchange-Diagnostics: 1;BY2PR1201MB1000;2:QeiWyyd9xDX+1SEKCREkKNbifL08lXTsU1EvDayjUYvFj2qx0dO1PVqqk8cRq1qc1t4zNeBzORW89yoiK5iqyI/PB1yhO8WrApwu9diqTX276QwiCCJUFoAQ0HJ30BTo1echTl+fWhMQITjpDL7hPw==;3:htGrTDRHqegRxPNDH2LPuipSf7KAy+5JRrwN+7ZtsiU7dndEq0C5RnpAbcpTsO3x6L7QIV4jJO29mJZasOanw+ElGYYInOOXjzi1c/0uiULedX3ZkYLENWZlSluEnD4E;25:Qo+QKr7CF+wD96WZZhP/KcYlQ6wTCyq7GADfrG8HSeWbXWpaYR98RqsuARR00YpFvwtJ/wgaM1eObpO8bjOzF+x4avuyPMXLF/oFPiVaTxpd9Ax2xCUxOMjXIvoZ7Y+JGMeA9aZFwgE1wnq17KBC+h7Ovm/vMrVcH2HuTtSDTrgoCD+cgEDQ5G4mSn+O7oGien24aqvZ7WDcXpYGztmjQFjm2wW2nt8WijtHO76FctYxL7GHtHBfGOJbdiCbwslD X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:BY2PR1201MB1000; X-MS-Office365-Filtering-Correlation-Id: 84cd194f-8685-43bd-3962-08d326ab23eb X-Microsoft-Exchange-Diagnostics: 1;BY2PR1201MB1000;20:9L+9FPNC6Typ0T4y0JtcXh5qB8OMzt09wv0l8oke9WmUNWvbUcbkR1aKVnLost2tfFqG0E+wxq8DQDwEGNXDFZXNqnAbKbzcXKBRphE/I7n9y31MX2flA3GfZKjfqnnUMdTff/TlRtHrlyaNzBpB1B7rDwBl5paK8EICGTLF3/kwpOFQtTPqFsKvF2UIEWSD25nSeMOj95nUNu2/l9CwB2Kwpjtc0ZKwXmEY+X74mcfLMN6clzEz/xwpY4AiSV7hNLfeOJjNJq1CPdpNVFRVGZlvclQGptEb2xjjgwJuHqAqESQUX4XL/ijoDBjsU3LDQcnHHPH+kgwrxFYtK4JDyj/TWv05ModZC8saCp13WBGBidIIFlZOncwXdxPv5q8qePwkit0FHIKexEZaWqQIOXdNGx4pEGk3Zzq1C4db01tJiyz/XyF5G2CL+czoWyhYm/KmXCyPcX/jFc6s4BPdAEgtoo6G50/rZrVvy0QAz3FcibLNN74FsXE7UDOAH6Af;4:VGmdKjai0IrO7r+8WkUgO+zOtcirCr5etLLsH2lFle9nMnT8AsWVQcTQTLGoASJDRKDiuBYGmDvHj3PBNJJyEeCNPMzO8RlPo0Ys2If6YWY5dEw5mg3mKhVCwyjDOD8FKhWhHYLxVNf4VdwJfdouZFX0W/Z/YsLek9hL35odv2U6AmHcSrZ6srBU+Q7IviooDbRccFKOyp5tgDlTsbGO94+dcjAjm31aBS64B6pniom/dJMtSAE3r7NjFrOToHxufUlrNDjJkFS1ta2QsZ+mC6Wqf/gfwkH8O3qFKEZpe8G2SEPbDM8OEuHWfEv07fDXM620HRPYQsu7s0GHsUSHShRrjPOaG+ai61Wpm4U7A9Es520IwIfiZIxKEyhRhA5HuC6uPIsUFvP414LqlZzJ5vBvoQL+9Fx0rsgRDFfDsNQ= X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:(767451399110); X-Exchange-Antispam-Report-CFA-Test: BCL:0;PCL:0;RULEID:(601004)(2401047)(5005006)(8121501046)(10201501046)(3002001);SRVR:BY2PR1201MB1000;BCL:0;PCL:0;RULEID:;SRVR:BY2PR1201MB1000; X-Forefront-PRVS: 08331F819E X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10009020)(6049001)(6009001)(377454003)(189002)(377424004)(24454002)(199003)(87976001)(50466002)(122386002)(2906002)(83506001)(92566002)(40100003)(64126003)(86362001)(23676002)(3470700001)(450100001)(42186005)(5004730100002)(77096005)(110136002)(107886002)(2351001)(5001960100002)(54356999)(230700001)(3846002)(2950100001)(65956001)(47776003)(19580395003)(189998001)(33656002)(81156007)(6116002)(66066001)(97736004)(65806001)(36756003)(50986999)(106356001)(5008740100001)(105586002)(586003)(65816999)(76176999)(101416001)(4001350100001)(1096002);DIR:OUT;SFP:1101;SCL:1;SRVR:BY2PR1201MB1000;H:[172.27.225.16];FPR:;SPF:None;PTR:InfoNoRecords;MX:1;A:1;LANG:en; X-Microsoft-Exchange-Diagnostics: =?utf-8?B?MTtCWTJQUjEyMDFNQjEwMDA7MjM6MUFySG1DWWM1YkFsVTIrdjBKSys5Uk9R?= =?utf-8?B?bGhQVDNLR3lPK20wSURtVk53SStRbjU1a2xlZUt5SXc3Q2dCVjlxTjFCRjdh?= =?utf-8?B?ZXVLNHV6cldqV0hsbFhzRGN5WU9Vbnl1N1lTcFNMMitlbXFVUDRpSWU2S2o1?= =?utf-8?B?Q3cydG9sSXJBL0VmWW1wdElybjFBMXF3RG9CbGdjS1A1ZmI5QWVaRTFINTdQ?= =?utf-8?B?MFNma0p0ckd1STZYMlpYN1NXUlNNcTZ6cVlzZjUxVlVkV01CMjJjM3NQVVgx?= =?utf-8?B?R0lFZTl2dFQ5MmY0MXpmUTF2Y1pHdGJsZ3kzTWZRdFNxbWFsYy9YNWpBWkFN?= =?utf-8?B?RjBWcUVST3NNZkQxdHZveVhPNVk2azluLzVCS0V3NGQ5QnBFdlBGWFNBUGRC?= =?utf-8?B?Ujduckd4T0tPRWFLaTRXRTdZZ1FkTTIyclROSW1KSEZQZFdKT3h3SE1jcnBx?= =?utf-8?B?UjBxSkxPWEdTN1U4dlIvRFJVK29oSDhKcDBSd3NOM0tGTm1vZmpXZnlhclUx?= =?utf-8?B?MmZxdXB1VGY3RDRWekJVOVZMb1dkUDQzcWtFV2lPNWNUTkRCOStxOFJJOTlJ?= =?utf-8?B?WDVqMnoxUTQrUFpFK2hLUUU1OFJTdHFHVXVEcVlveTdkVTV0b3E5aDFSNE9i?= =?utf-8?B?NTlHcUdQT1RCNmt2OFptV0FxTU5JN1NOZEtzaTBHM3M5RFZUT1RzdzdYNmZC?= =?utf-8?B?M282dUxqOVd6UHVhS1RKZ09rZjc2VlMzSFJzSzdaMVFUSERsSE5CUHo0V2Nj?= =?utf-8?B?ZmVxME9PZkNwZkRmZ0ErQ2h0QmVkTFBvYjd2Z1d1RGhSMUJ2R0ZnbmU1SlJa?= =?utf-8?B?ZXFENURrS3hrZU4xSXBEUlZEL2wxMkdMcmIvaFU3Qi8vK1ZzcnQxNDAyUVVj?= =?utf-8?B?TEJsYzFyYUlKbTFBTEhaWWFUaFJScE45N0hQZlVjdStKZXYzbDBDRXFjeC95?= =?utf-8?B?eXJDbzdSUFhGOEhhSWlsZUZHZVMrTGs5U2NFS3NUZkl3SUF6Rk5wYTVRUDI5?= =?utf-8?B?RWtnR2YzYURqenZNRmRhOVkrY3luZXpTL3UrMjdpaUNobm9RS0xjKzkxKzJV?= =?utf-8?B?OWZjL1FsYk5LR3dxOUF6Ylhtb1N3MnBkeXZmRytKc2hzVmhmNkFwbmMyck5Q?= =?utf-8?B?MzhLK1ZsNTNzVVllMFZhMnA0Nkl3cmtVZGRtTW5IS2VxQzR5V0k1dUlLRDN0?= =?utf-8?B?clhsUVBPK2FvL1FMeDNaSEJURmZxV01Bdyt4eFo0T1ZsUmVQV0FST0ZCTktR?= =?utf-8?B?NjdKYjcyVGdwa004QTNFZEFuZFAyalgwaFNqZkJPZUVSMHhuZlM5Y0d6dndB?= =?utf-8?B?enY3OTlKQkNnTjRrcVF0WlhNRkduam9RWEZpbjlrZlg0bmd5aFpQTlFTbG5j?= =?utf-8?B?S1laUzhrK0hUWmZ1STFDWjFvL3F4dzd0Rm10ZlJlRkJRQVM2MWZ4U2pDVU13?= =?utf-8?B?TGZBU0FUVzlXM1E2SGprVEZlTUNlN2xrcGp0UlZTNFd1d0Yvc20xNG9XRitn?= =?utf-8?B?MDRSamtVU2k3WjNUeXkwRFRLbUVqdkFZVFFtVFRoQURJME8rZnl5VnZXMGZk?= =?utf-8?B?VklZYTh2NkZBVTRXM2RGV05YMU1rczFGNFV2cXNiMFk3VmhnMWpzUGRzZitJ?= =?utf-8?B?dXV1U0Z0V0NNQ0o4aHlTN1owT2psOXdkMlFxSFJkUmtETThhYU1jN0xCM0wv?= =?utf-8?B?TVkzc1BOK3RHSmcrOVc3ZVRDcjJpbXhhR2RhWTB5VFRCUWJOb1VhRlRNNjNq?= =?utf-8?B?ZkRIUWpoN2pUcmVaTUovTFN3PT0=?= X-Microsoft-Exchange-Diagnostics: 1;BY2PR1201MB1000;5:xRT87bQSn0oXfJeZj/rQDU9YDEV8vGbmP0a7HRlg6rrE9ZICV3ew3/h/iR0ifJ5+KSOCEDty137BFUbDz6E35ZSg2xkqjl+CKTK0Iyu+IEZxkYV9CdyMOYZ9onPqid6+XQ0MPkF6FTWGvjelTbdQJg==;24:lYkfyFUoGGmx39+DlYUnNhAE2KOf33P2H1C9/RSlk0TMfvpyny19RgN92PMS0auCFp0x7fVGIoWyCwirH7OymUfDoCEY8zy8rod9MJnNT58=;20:xGE3HSzr8ibxD4/6zBYihWOZ4NAsctEE5acjkWXSJ3EbRMv7sHXANFUL/qc+7mRoFZPYRLfeSf5oGEFRPBZONdmCB8W/PxUrn00PiNNuuwZJbK5D3yGRtOhahjCgI7OuThLDffJnAMd6fzXNWopJr2zEymQbQuKmP7SiD3zDgHTXZYQ9iX1QDqpvi5AnkW3e/OI1bAyVEgjA+DhsW0KKw4btMi/nBNft2jRWMuWDfy0v1hASCJMynvFjm/SbEj4/ SpamDiagnosticOutput: 1:23 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: amd.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 26 Jan 2016 23:48:07.0753 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY2PR1201MB1000 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 16-01-21 05:20 PM, Felix Kuehling wrote: > I'm running into circular lock dependencies reported by lockdep that > involve read-locks and should not be flagged as deadlocks at all. I > wrote a very simple test function that demonstrates the problem: [snip] > It sets up a circular lock dependency between a mutex and a read-write > semaphore. However, the semaphore is only ever locked for reading. The same expirement with a spinlock and an rwlock works correctly. The difference is that the rwlock allows recursive read-locks, whereas the rw semaphore does not. Recursive read-locks are not added to the lock dependency graph at all, hence they don't trip the circular lock checks. I think this handling of recursive read locks is actually incorrect, because it fails to notice potential circular deadlocks like this: > spinlock_t fktest_sp; > rwlock_t fktest_rw; > > spin_lock_init(&fktest_sp); > rwlock_init(&fktest_rw); > > read_lock(&fktest_rw); > spin_lock(&fktest_sp); > spin_unlock(&fktest_sp); > read_unlock(&fktest_rw); > > spin_lock(&fktest_sp); > write_lock(&fktest_rw); > write_unlock(&fktest_rw); > spin_unlock(&fktest_sp); In a possible deadlock scenario thread A takes read lock, thread B takes spin lock, thread A blocks trying to take spin lock, thread B blocks trying to take write lock. The read-lock depending on the spinlock is never entered into the dependency graph. Hence the circular dependency is not seen when the write lock is taken. I think the whole handling of read-locks needs to be revamped for proper detection of circular lock dependencies without false positives or false negatives (I have demonstrated one example of each with the current implementation). A dependency chain must be able to distinguish, whether a lock is taken for reading or for writing. That means, read locks need their own lock (sub-)class. A new write dependency (a lock that depends on holding a write-lock) creates a dependency on both the read and write-lock classes, because both cases can lead to a potential deadlock. A new read dependency (a lock that depends on holding a read-lock) only creates a dependency on the write-lock class, because read locks don't block each other. I'm going to prototype my idea. I can use sub-classes for making separate read and write lock classes. But that means, effectively I only have half as many usable lock sub-classes left available for nesting annotations on lock primitives that support read-locking. I hope that's not a problem. Feedback welcome. Regards, Felix -- F e l i x K u e h l i n g SMTS Software Development Engineer | Vertical Workstation/Compute 1 Commerce Valley Dr. East, Markham, ON L3T 7X6 Canada (O) +1(289)695-1597 _ _ _ _____ _____ / \ | \ / | | _ \ \ _ | / A \ | \M/ | | |D) ) /|_| | /_/ \_\ |_| |_| |_____/ |__/ \| facebook.com/AMD | amd.com