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 A9A49C433EF for ; Thu, 3 Mar 2022 12:38:54 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D191D8D0002; Thu, 3 Mar 2022 07:38:53 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id CA1B68D0001; Thu, 3 Mar 2022 07:38:53 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B42CA8D0002; Thu, 3 Mar 2022 07:38:53 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (relay.a.hostedemail.com [64.99.140.24]) by kanga.kvack.org (Postfix) with ESMTP id A47318D0001 for ; Thu, 3 Mar 2022 07:38:53 -0500 (EST) Received: from smtpin06.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay12.hostedemail.com (Postfix) with ESMTP id 66FC41206B7 for ; Thu, 3 Mar 2022 12:38:53 +0000 (UTC) X-FDA: 79203029346.06.1C146D7 Received: from mail-pj1-f42.google.com (mail-pj1-f42.google.com [209.85.216.42]) by imf31.hostedemail.com (Postfix) with ESMTP id DE0602000F for ; Thu, 3 Mar 2022 12:38:52 +0000 (UTC) Received: by mail-pj1-f42.google.com with SMTP id m13-20020a17090aab0d00b001bbe267d4d1so6088294pjq.0 for ; Thu, 03 Mar 2022 04:38:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to; bh=Xw1t8RJEBLs6nNo618ULi5yqJsMgKqz1ONvJ2a5MT3c=; b=BzrkK1hJiQ+JPPG9UrxzPIeXGct5pIgTB7o+w9LPLZpdlhw7yhoWA1GMh5N61uZfF/ PncBXmid0UFMAuiub2OnBJ72eeoETL66hxSZhF+f6FXTMhgAP82GWSXHwZEIimpTW2Qq 7c61woZrDZKYd5zhfndnPY5TegWp8YItlyVknSXTgeVSZ+T6iyQLaEJqoglIo/hdtHs4 Z8HVrCi7NFr6cs8zHgPcouRaNQ7Lab/z+IYkC5z/RIoeNT2FKku0gTGOQnu+pzm7NStv unipj1p2yZj7cPNJekdxtvWRdtz5+OLkobNPxtRBn30IJ2Tc5sJpjX6tA+yZp7pogBRh YbOA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=Xw1t8RJEBLs6nNo618ULi5yqJsMgKqz1ONvJ2a5MT3c=; b=3R080R57vlRte1dQSIQvV02R7vbKAuiWMuqvJ7YiOFsQsJR6SCvBsSeny3d5B1e65R gUKuTZ3xpWHiJMj40RC4Lxkr59XfAofmWyI+WELmBl26ZxiR//YY8YAd2wQ3I1KXHT0p OFpFek1PdpjE+7qnIP7bsut++cHdlD1kYl24BFH9qVnoO/n/Nde9Q3IvHuPTCWKcOOBD Vx/3rXuNnnlWBnN8Jk3bdXsuQfP+n/lZCqaEgeLc+syqrF1kTj3T8XcYM4VoJMuKWbC+ PX75+el9erSdLfcsBVIbO9WwKmnhRUXdH4et8a7KvkYDRg+1JUzQvHU69nqRCnKnV8wH szLA== X-Gm-Message-State: AOAM530oqKoeKb+bP/bqBNYQWwx3hqSr18m0N1PA5mGP8vPaJD2PeUR2 NhT5tvAM+xKEW7iKhnhB+j4= X-Google-Smtp-Source: ABdhPJz17qOFmFlBrNJNUqYdHV9n7lTWYbm2jjytljRWsyBIk/kiynuY77vwBHskQjfvfh0lM0uI3g== X-Received: by 2002:a17:90a:430d:b0:1bc:f340:8096 with SMTP id q13-20020a17090a430d00b001bcf3408096mr5017886pjg.93.1646311131665; Thu, 03 Mar 2022 04:38:51 -0800 (PST) Received: from ip-172-31-19-208.ap-northeast-1.compute.internal (ec2-18-181-137-102.ap-northeast-1.compute.amazonaws.com. [18.181.137.102]) by smtp.gmail.com with ESMTPSA id d2-20020a056a0010c200b004f102a13040sm2550047pfu.19.2022.03.03.04.38.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 03 Mar 2022 04:38:51 -0800 (PST) Date: Thu, 3 Mar 2022 12:38:39 +0000 From: Hyeonggon Yoo <42.hyeyoo@gmail.com> To: Byungchul Park Cc: 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, linux-kernel@vger.kernel.org, peterz@infradead.org, will@kernel.org, tglx@linutronix.de, rostedt@goodmis.org, joel@joelfernandes.org, sashal@kernel.org, daniel.vetter@ffwll.ch, chris@chris-wilson.co.uk, duyuyang@gmail.com, johannes.berg@intel.com, tj@kernel.org, tytso@mit.edu, willy@infradead.org, david@fromorbit.com, amir73il@gmail.com, bfields@fieldses.org, 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, jack@suse.com, jlayton@kernel.org, dan.j.williams@intel.com, hch@infradead.org, djwong@kernel.org, dri-devel@lists.freedesktop.org, airlied@linux.ie, rodrigosiqueiramelo@gmail.com, melissa.srw@gmail.com, hamohammed.sa@gmail.com, Catalin Marinas Subject: Re: [PATCH v3 00/21] DEPT(Dependency Tracker) Message-ID: References: <1646042220-28952-1-git-send-email-byungchul.park@lge.com> <20220303001812.GA20752@X58A-UD3R> <20220303094824.GA24977@X58A-UD3R> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20220303094824.GA24977@X58A-UD3R> X-Rspam-User: X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: DE0602000F X-Stat-Signature: 51j3n6ext6rrtwyyqk6y6f1hozk9j7uy Authentication-Results: imf31.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=BzrkK1hJ; spf=pass (imf31.hostedemail.com: domain of 42.hyeyoo@gmail.com designates 209.85.216.42 as permitted sender) smtp.mailfrom=42.hyeyoo@gmail.com; dmarc=pass (policy=none) header.from=gmail.com X-HE-Tag: 1646311132-36445 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, Mar 03, 2022 at 06:48:24PM +0900, Byungchul Park wrote: > On Thu, Mar 03, 2022 at 08:03:21AM +0000, Hyeonggon Yoo wrote: > > On Thu, Mar 03, 2022 at 09:18:13AM +0900, Byungchul Park wrote: > > > Hi Hyeonggon, > > > > > > Dept also allows the following scenario when an user guarantees that > > > each lock instance is different from another at a different depth: > > > > > > lock A0 with depth > > > lock A1 with depth + 1 > > > lock A2 with depth + 2 > > > lock A3 with depth + 3 > > > (and so on) > > > .. > > > unlock A3 > > > unlock A2 > > > unlock A1 > > > unlock A0 > [+Cc kmemleak maintainer] > Look at this. Dept allows object->lock -> other_object->lock (with a > different depth using *_lock_nested()) so won't report it. > No, It did. S: object->lock ( _raw_spin_lock_irqsave) W: other_object->lock (_raw_spin_lock_nested) DEPT reported this as AA deadlock. =================================================== DEPT: Circular dependency has been detected. 5.17.0-rc1+ #1 Tainted: G W --------------------------------------------------- summary --------------------------------------------------- *** AA DEADLOCK *** context A [S] __raw_spin_lock_irqsave(&object->lock:0) [W] _raw_spin_lock_nested(&object->lock:0) [E] spin_unlock(&object->lock:0) [S]: start of the event context [W]: the wait blocked [E]: the event not reachable --------------------------------------------------- context A's detail --------------------------------------------------- context A [S] __raw_spin_lock_irqsave(&object->lock:0) [W] _raw_spin_lock_nested(&object->lock:0) [E] spin_unlock(&object->lock:0) --------------------------------------------------- context A's detail --------------------------------------------------- context A [S] __raw_spin_lock_irqsave(&object->lock:0) [W] _raw_spin_lock_nested(&object->lock:0) [E] spin_unlock(&object->lock:0) [S] __raw_spin_lock_irqsave(&object->lock:0): [] scan_gray_list+0x84/0x13c stacktrace: dept_ecxt_enter+0x88/0xf4 _raw_spin_lock_irqsave+0xf0/0x1c4 scan_gray_list+0x84/0x13c kmemleak_scan+0x2d8/0x54c kmemleak_scan_thread+0xac/0xd4 kthread+0xd4/0xe4 ret_from_fork+0x10/0x20 [W] _raw_spin_lock_nested(&object->lock:0): [] scan_block+0xb4/0x128 stacktrace: __dept_wait+0x8c/0xa4 dept_wait+0x6c/0x88 _raw_spin_lock_nested+0xa8/0x1b0 scan_block+0xb4/0x128 scan_gray_list+0xc4/0x13c kmemleak_scan+0x2d8/0x54c kmemleak_scan_thread+0xac/0xd4 kthread+0xd4/0xe4 ret_from_fork+0x10/0x20 [E] spin_unlock(&object->lock:0): [] scan_block+0x60/0x128 --------------------------------------------------- information that might be helpful --------------------------------------------------- CPU: 2 PID: 38 Comm: kmemleak Tainted: G W 5.17.0-rc1+ #1 Hardware name: linux,dummy-virt (DT) Call trace: dump_backtrace.part.0+0x9c/0xc4 show_stack+0x14/0x28 dump_stack_lvl+0x9c/0xcc dump_stack+0x14/0x2c print_circle+0x2d4/0x438 cb_check_dl+0x44/0x70 bfs+0x60/0x168 add_dep+0x88/0x11c add_wait+0x2d0/0x2dc __dept_wait+0x8c/0xa4 dept_wait+0x6c/0x88 _raw_spin_lock_nested+0xa8/0x1b0 scan_block+0xb4/0x128 scan_gray_list+0xc4/0x13c kmemleak_scan+0x2d8/0x54c kmemleak_scan_thread+0xac/0xd4 kthread+0xd4/0xe4 ret_from_fork+0x10/0x20 > > > However, Dept does not allow the following scenario where another lock > > > class cuts in the dependency chain: > > > > > > lock A0 with depth > > > lock B > > > lock A1 with depth + 1 > > > lock A2 with depth + 2 > > > lock A3 with depth + 3 > > > (and so on) > > > .. > > > unlock A3 > > > unlock A2 > > > unlock A1 > > > unlock B > > > unlock A0 > > > > > > This scenario is clearly problematic. What do you think is going to > > > happen with another context running the following? > > > > > > > First of all, I want to say I'm not expert at locking primitives. > > I may be wrong. > > It's okay. Thanks anyway for your feedback. > Thanks. > > > > 45 * scan_mutex [-> object->lock] -> kmemleak_lock -> other_object->lock (SINGLE_DEPTH_NESTING) > > > > 46 * > > > > 47 * No kmemleak_lock and object->lock nesting is allowed outside scan_mutex > > > > 48 * regions. > > > > lock order in kmemleak is described above. > > > > and DEPT detects two cases as deadlock: > > > > 1) object->lock -> other_object->lock > > It's not a deadlock *IF* two have different depth using *_lock_nested(). > Dept also allows this case. So Dept wouldn't report it. > > > 2) object->lock -> kmemleak_lock, kmemleak_lock -> other_object->lock > > But this usage is risky. I already explained it in the mail you replied > to. I copied it. See the below. > I understand why you said this is risky. Its lock ordering is not good. > context A > > > lock A0 with depth > > > lock B > > > lock A1 with depth + 1 > > > lock A2 with depth + 2 > > > lock A3 with depth + 3 > > > (and so on) > > > .. > > > unlock A3 > > > unlock A2 > > > unlock A1 > > > unlock B > > > unlock A0 > > ... > > context B > > > lock A1 with depth > > > lock B > > > lock A2 with depth + 1 > > > lock A3 with depth + 2 > > > (and so on) > > > .. > > > unlock A3 > > > unlock A2 > > > unlock B > > > unlock A1 > > where Ax : object->lock, B : kmemleak_lock. > > A deadlock might occur if the two contexts run at the same time. > But I want to say kmemleak is getting things under control. No two contexts can run at same time. > > And in kmemleak case, 1) and 2) is not possible because it must hold > > scan_mutex first. > > This is another issue. Let's focus on whether the order is okay for now. > Why is it another issue? > > I think the author of kmemleak intended lockdep to treat object->lock > > and other_object->lock as different class, using raw_spin_lock_nested(). > > Yes. The author meant to assign a different class according to its depth > using a Lockdep API. Strictly speaking, those are the same class anyway > but we assign a different class to each depth to avoid Lockdep splats > *IF* the user guarantees the nesting lock usage is safe, IOW, guarantees > each lock instance is different at a different depth. Then why DEPT reports 1) and 2) as deadlock? Does DEPT assign same class unlike Lockdep? > I was fundamentally asking you... so... is the nesting lock usage safe > for real? I don't get what the point is. I agree it's not a good lock ordering. But in kmemleak case, I think kmemleak is getting things under control. -- Thank you, You are awesome! Hyeonggon :-) > I hope you distinguish between the safe case and the risky > case when *_lock_nested() is involved. Thoughts? > > Thanks, > Byungchul > > > Am I missing something? > > > > Thanks. > > > > > lock A1 with depth > > > lock B > > > lock A2 with depth + 1 > > > lock A3 with depth + 2 > > > (and so on) > > > .. > > > unlock A3 > > > unlock A2 > > > unlock B > > > unlock A1 > > > > > > It's a deadlock. That's why Dept reports this case as a problem. Or am I > > > missing something? > > > > > > Thanks, > > > Byungchul > > > > > > > --------------------------------------------------- > > > > context A's detail > > > > --------------------------------------------------- > > > > context A > > > > [S] __raw_spin_lock_irqsave(&object->lock:0) > > > > [W] __raw_spin_lock_irqsave(kmemleak_lock:0) > > > > [E] spin_unlock(&object->lock:0) > > > > > > > > [S] __raw_spin_lock_irqsave(&object->lock:0): > > > > [] scan_gray_list+0x84/0x13c > > > > stacktrace: > > > > dept_ecxt_enter+0x88/0xf4 > > > > _raw_spin_lock_irqsave+0xf0/0x1c4 > > > > scan_gray_list+0x84/0x13c > > > > kmemleak_scan+0x2d8/0x54c > > > > kmemleak_scan_thread+0xac/0xd4 > > > > kthread+0xd4/0xe4 > > > > ret_from_fork+0x10/0x20 > > > > > > > > [W] __raw_spin_lock_irqsave(kmemleak_lock:0): > > > > [] scan_block+0x3c/0x128 > > > > stacktrace: > > > > __dept_wait+0x8c/0xa4 > > > > dept_wait+0x6c/0x88 > > > > _raw_spin_lock_irqsave+0xb8/0x1c4 > > > > scan_block+0x3c/0x128 > > > > scan_gray_list+0xc4/0x13c > > > > kmemleak_scan+0x2d8/0x54c > > > > kmemleak_scan_thread+0xac/0xd4 > > > > kthread+0xd4/0xe4 > > > > ret_from_fork+0x10/0x20 > > > > > > > > [E] spin_unlock(&object->lock:0): > > > > [] scan_block+0x60/0x128 > > > > > > > > --------------------------------------------------- > > > > context B's detail > > > > --------------------------------------------------- > > > > context B > > > > [S] __raw_spin_lock_irqsave(kmemleak_lock:0) > > > > [W] _raw_spin_lock_nested(&object->lock:0) > > > > [E] spin_unlock(kmemleak_lock:0) > > > > > > > > [S] __raw_spin_lock_irqsave(kmemleak_lock:0): > > > > [] scan_block+0x3c/0x128 > > > > stacktrace: > > > > dept_ecxt_enter+0x88/0xf4 > > > > _raw_spin_lock_irqsave+0xf0/0x1c4 > > > > scan_block+0x3c/0x128 > > > > kmemleak_scan+0x19c/0x54c > > > > kmemleak_scan_thread+0xac/0xd4 > > > > kthread+0xd4/0xe4 > > > > ret_from_fork+0x10/0x20 > > > > > > > > [W] _raw_spin_lock_nested(&object->lock:0): > > > > [] scan_block+0xb4/0x128 > > > > stacktrace: > > > > dept_wait+0x74/0x88 > > > > _raw_spin_lock_nested+0xa8/0x1b0 > > > > scan_block+0xb4/0x128 > > > > kmemleak_scan+0x19c/0x54c > > > > kmemleak_scan_thread+0xac/0xd4 > > > > kthread+0xd4/0xe4 > > > > ret_from_fork+0x10/0x20 > > > > [E] spin_unlock(kmemleak_lock:0): > > > > [] scan_block+0x60/0x128 > > > > stacktrace: > > > > dept_event+0x7c/0xfc > > > > _raw_spin_unlock_irqrestore+0x8c/0x120 > > > > scan_block+0x60/0x128 > > > > kmemleak_scan+0x19c/0x54c > > > > kmemleak_scan_thread+0xac/0xd4 > > > > kthread+0xd4/0xe4 > > > > ret_from_fork+0x10/0x20 > > > > --------------------------------------------------- > > > > information that might be helpful > > > > --------------------------------------------------- > > > > CPU: 1 PID: 38 Comm: kmemleak Tainted: G W 5.17.0-rc1+ #1 > > > > Hardware name: linux,dummy-virt (DT) > > > > Call trace: > > > > dump_backtrace.part.0+0x9c/0xc4 > > > > show_stack+0x14/0x28 > > > > dump_stack_lvl+0x9c/0xcc > > > > dump_stack+0x14/0x2c > > > > print_circle+0x2d4/0x438 > > > > cb_check_dl+0x6c/0x70 > > > > bfs+0xc0/0x168 > > > > add_dep+0x88/0x11c > > > > add_wait+0x2d0/0x2dc > > > > __dept_wait+0x8c/0xa4 > > > > dept_wait+0x6c/0x88 > > > > _raw_spin_lock_irqsave+0xb8/0x1c4 > > > > scan_block+0x3c/0x128 > > > > scan_gray_list+0xc4/0x13c > > > > kmemleak_scan+0x2d8/0x54c > > > > kmemleak_scan_thread+0xac/0xd4 > > > > kthread+0xd4/0xe4 > > > > ret_from_fork+0x10/0x20 > > > > > > > > > =================================================== > > > > > DEPT: Circular dependency has been detected. > > > > > 5.17.0-rc1+ #1 Tainted: G W > > > > > --------------------------------------------------- > > > > > summary > > > > > --------------------------------------------------- > > > > > *** AA DEADLOCK *** > > > > > > > > > > context A > > > > > [S] __raw_spin_lock_irqsave(&object->lock:0) > > > > > [W] _raw_spin_lock_nested(&object->lock:0) > > > > > [E] spin_unlock(&object->lock:0) > > > > > > > > > > [S]: start of the event context > > > > > [W]: the wait blocked > > > > > [E]: the event not reachable > > > > > --------------------------------------------------- > > > > > context A's detail > > > > > --------------------------------------------------- > > > > > context A > > > > > [S] __raw_spin_lock_irqsave(&object->lock:0) > > > > > [W] _raw_spin_lock_nested(&object->lock:0) > > > > > [E] spin_unlock(&object->lock:0) > > > > > > > > > > [S] __raw_spin_lock_irqsave(&object->lock:0): > > > > > [] scan_gray_list+0x84/0x13c > > > > > stacktrace: > > > > > dept_ecxt_enter+0x88/0xf4 > > > > > _raw_spin_lock_irqsave+0xf0/0x1c4 > > > > > scan_gray_list+0x84/0x13c > > > > > kmemleak_scan+0x2d8/0x54c > > > > > kmemleak_scan_thread+0xac/0xd4 > > > > > kthread+0xd4/0xe4 > > > > > ret_from_fork+0x10/0x20 > > > > > > > > > > [E] spin_unlock(&object->lock:0): > > > > > [] scan_block+0x60/0x128 > > > > > --------------------------------------------------- > > > > > information that might be helpful > > > > > --------------------------------------------------- > > > > > CPU: 1 PID: 38 Comm: kmemleak Tainted: G W 5.17.0-rc1+ #1 > > > > > Hardware name: linux,dummy-virt (DT) > > > > > Call trace: > > > > > dump_backtrace.part.0+0x9c/0xc4 > > > > > show_stack+0x14/0x28 > > > > > dump_stack_lvl+0x9c/0xcc > > > > > dump_stack+0x14/0x2c > > > > > print_circle+0x2d4/0x438 > > > > > cb_check_dl+0x44/0x70 > > > > > bfs+0x60/0x168 > > > > > add_dep+0x88/0x11c > > > > > add_wait+0x2d0/0x2dc > > > > > __dept_wait+0x8c/0xa4 > > > > > dept_wait+0x6c/0x88 > > > > > _raw_spin_lock_nested+0xa8/0x1b0 > > > > > scan_block+0xb4/0x128 > > > > > scan_gray_list+0xc4/0x13c > > > > > kmemleak_scan+0x2d8/0x54c > > > > > kmemleak_scan_thread+0xac/0xd4 > > > > > kthread+0xd4/0xe4 > > > > > ret_from_fork+0x10/0x20 > > > > > > > > > [...] > > > > > > > > -- > > > > Thank you, You are awesome! > > > > Hyeonggon :-) > > > > -- > > Thank you, You are awesome! > > Hyeonggon :-)