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 1315BC004D4 for ; Sat, 21 Jan 2023 03:28:52 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 7353B6B0074; Fri, 20 Jan 2023 22:28:51 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 6E4C46B0075; Fri, 20 Jan 2023 22:28:51 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 585FC6B0078; Fri, 20 Jan 2023 22:28:51 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 48D926B0074 for ; Fri, 20 Jan 2023 22:28:51 -0500 (EST) Received: from smtpin06.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 502C4AB2E3 for ; Sat, 21 Jan 2023 03:28:50 +0000 (UTC) X-FDA: 80377374420.06.5997178 Received: from lgeamrelo11.lge.com (lgeamrelo12.lge.com [156.147.23.52]) by imf21.hostedemail.com (Postfix) with ESMTP id 082CF1C000D for ; Sat, 21 Jan 2023 03:28:38 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=none; dmarc=none; spf=pass (imf21.hostedemail.com: domain of byungchul.park@lge.com designates 156.147.23.52 as permitted sender) smtp.mailfrom=byungchul.park@lge.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1674271720; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:in-reply-to: references:references; bh=qSaBkS6SCCdHJ3qKuZoIHFO1XWlu5lTd97ijAEANTa0=; b=12pKp3X32Zt/yVpKSDiaW9CssAlXoSPi4nu8n1gocWQJ0/bUZ/MN7lIuMMmHUS7VYYtCFS TGyw0YwvYEEivrwJXbm/0ds+5/zHS19W3sqF6/7QJscEvLw8Iu5u5w3Bq60T04ofHhmsen 3mWZadJoleu0a2f17Vyv2xO8ex2R+Yg= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=none; dmarc=none; spf=pass (imf21.hostedemail.com: domain of byungchul.park@lge.com designates 156.147.23.52 as permitted sender) smtp.mailfrom=byungchul.park@lge.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1674271720; a=rsa-sha256; cv=none; b=JOayuXRrrmY8YH5RmxQ/O6/NMBcdnL9tfOMvmosVoQSieNS4Q6unpTynNTrkGZgrTJFuTC +jYq/dnf11FsUm0fAFs+zgIMHSKm8+TjVxSjKex3Lscy4yg8Dd1BOoPd5btLg3ZdxqSHIf 9sLtFhQ4436VI3neuu9lklHRjBTF/Mo= Received: from unknown (HELO lgeamrelo02.lge.com) (156.147.1.126) by 156.147.23.52 with ESMTP; 21 Jan 2023 12:28:29 +0900 X-Original-SENDERIP: 156.147.1.126 X-Original-MAILFROM: byungchul.park@lge.com Received: from unknown (HELO localhost.localdomain) (10.177.244.38) by 156.147.1.126 with ESMTP; 21 Jan 2023 12:28:29 +0900 X-Original-SENDERIP: 10.177.244.38 X-Original-MAILFROM: byungchul.park@lge.com From: Byungchul Park To: boqun.feng@gmail.com Cc: linux-kernel@vger.kernel.org, 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, peterz@infradead.org, will@kernel.org, tglx@linutronix.de, rostedt@goodmis.org, joel@joelfernandes.org, sashal@kernel.org, daniel.vetter@ffwll.ch, duyuyang@gmail.com, johannes.berg@intel.com, tj@kernel.org, tytso@mit.edu, willy@infradead.org, david@fromorbit.com, amir73il@gmail.com, 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, jlayton@kernel.org, dan.j.williams@intel.com, hch@infradead.org, djwong@kernel.org, dri-devel@lists.freedesktop.org, rodrigosiqueiramelo@gmail.com, melissa.srw@gmail.com, hamohammed.sa@gmail.com, 42.hyeyoo@gmail.com, chris.p.wilson@intel.com, gwan-gyeong.mun@intel.com, max.byungchul.park@gmail.com, longman@redhat.com Subject: Re: [PATCH RFC v7 00/23] DEPT(Dependency Tracker) Date: Sat, 21 Jan 2023 12:28:14 +0900 Message-Id: <1674271694-18950-1-git-send-email-byungchul.park@lge.com> X-Mailer: git-send-email 1.9.1 In-Reply-To: References: X-Rspam-User: X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 082CF1C000D X-Stat-Signature: cc56s8t845igg4kixexa9fbfozyj1kct X-HE-Tag: 1674271718-29224 X-HE-Meta: U2FsdGVkX1+AK7wpbopRcQxCZE8qOQU/s7w0wCQXG5uRW0w6LAAcdDZ30d9X8C+MgwZyxsJo27HQ3ukBYzZMyUuzrnQ7I3dGxCx+9arirqatKilsQmpaZfDUFlux3PjcabejKfpDq8WjspIgHmRELWQT98SkEdwu1VYH38O4Qn5zTCxfebrFfVBXOOGgjQc01okya8aFs5IlXwONGshHhFmPkPcabNYBc9aezw5z9YNl01xwBRYwdCHJl3IynKgwDNE0wWLXN0mrxy800hrFI5pDyQOEJfma/Jz1UJ/jdH+G4RTqZzWmxaSZukBy6iaXWVthKHMYs7Fvvc80NwyPsx8prgkZuaMISTvJQbiCnBPd4wBWCbVOk1C9YrXbywJBAcnXySRdDkEEclFtKciZ6DEg6E7J2cE5INIus05frL/4BoWUpdh0sBXiWWmBCsJjbIpvrtUyW9meGymSQfidWvnP56oEhTbK8XL7SH9N/rZDNnYXQu0d2YytqUMr6Dcj8RdJCdGxzT8aePJ54cy96QK9tQtQILXi/WIC6xmc6T7AUd5g+R+PujsoZaPXmPibfBLy5I0HzaCO6p1PEqOk6KuKinkPnKQa/9eisKyfSCkUwmVuyQJr2Gc5gWzFFFe5BiQU6HyDUPARQLNSwemRKTvCzdqRnLZabihyowAnTkKuS9I85CuY4wu450N4Xd/hnTomvEAoY5nFH0PXT5XmaFcmKy6o+n/+42AnQ7yZctA+5qvcL8XCRvf4jKyJt72qX5emKijxDLdOa+XJDayL/XnCtXrqAOPvxEdM3WRF0CfLrDfXK2Z64KbLwFftgo9KX180vkt5+skBLCefDUodnEgP9Nmmlo845mftYCNd0u5pzI2LdtFrYNaZTESAND8kHyEh/16wGLGG7b1gkNJS6O+MECE3Z+lIaGWgdJL6FyOL4ArcbDgThOnev5dOlcDg5cvTFa/5GWWF166lCG2 6LsbLk7h qh2h+ZejTTOGQKXjxxx2TpoGIaU36Kwwz90IYt/6NlTepnyjih+F81/X4tv1B89jgbHWgeU3qfGL3j8MmucEajq8S/e6S2ezdsefyKqkshHnslOOytguD/6MrX/ohkDhwPhM6meAyb4IHQTOkS1pkxG070E0xvzIxfyhefJOhx0zb7TTq5jzggJm8CJ/BYdtbGtz30NmLejPe38+br7HaLAibnyQghh8lmNsGIxQYx2julDweJBvU+QQ/jtYcOdZ9iz+/AQq7QSGhVVjbqbxD8qGpsm8camN+0vmXMat4Xl/WyZY= X-Bogosity: Ham, tests=bogofilter, spamicity=0.001203, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: On Thu, Jan 19, 2023 at 07:07:59PM -0800, Boqun Feng wrote: > On Thu, Jan 19, 2023 at 06:23:49PM -0800, Boqun Feng wrote: > > On Fri, Jan 20, 2023 at 10:51:45AM +0900, Byungchul Park wrote: [...] > > > T0 T1 T2 > > > -- -- -- > > > unfair_read_lock(A); > > > write_lock(B); > > > write_lock(A); > > > write_lock(B); > > > fair_read_lock(A); > > > write_unlock(B); > > > read_unlock(A); > > > read_unlock(A); > > > write_unlock(B); > > > write_unlock(A); > > > > > > T0: read_unlock(A) cannot happen if write_lock(B) is stuck by a B owner > > > not doing either write_unlock(B) or read_unlock(B). In other words: > > > > > > 1. read_unlock(A) happening depends on write_unlock(B) happening. > > > 2. read_unlock(A) happening depends on read_unlock(B) happening. > > > > > > T1: write_unlock(B) cannot happen if fair_read_lock(A) is stuck by a A > > > owner not doing either write_unlock(A) or read_unlock(A). In other > > > words: > > > > > > 3. write_unlock(B) happening depends on write_unlock(A) happening. > > > 4. write_unlock(B) happening depends on read_unlock(A) happening. > > > > > > 1, 2, 3 and 4 give the following dependencies: > > > > > > 1. read_unlock(A) -> write_unlock(B) > > > 2. read_unlock(A) -> read_unlock(B) > > > 3. write_unlock(B) -> write_unlock(A) > > > 4. write_unlock(B) -> read_unlock(A) > > > > > > With 1 and 4, there's a circular dependency so DEPT definitely report > > > this as a problem. > > > > > > REMIND: DEPT focuses on waits and events. > > > > Do you have the test cases showing DEPT can detect this? > > > > Just tried the following on your latest GitHub branch, I commented all > but one deadlock case. Lockdep CAN detect it but DEPT CANNOT detect it. > Feel free to double check. I tried the 'queued read lock' test cases with DEPT on. I can see DEPT detect and report it. But yeah.. it's too verbose now. It's because DEPT is not aware of the test environment so it's just working hard to report every case. To make DEPT work with the selftest better, some works are needed. I will work on it later or you please work on it. The corresponding report is the following. --- [ 4.583997] =================================================== [ 4.585094] DEPT: Circular dependency has been detected. [ 4.585620] 6.0.0-00023-g331e0412f735 #2 Tainted: G W [ 4.586347] --------------------------------------------------- [ 4.586942] summary [ 4.587161] --------------------------------------------------- [ 4.587757] *** DEADLOCK *** [ 4.587757] [ 4.588198] context A [ 4.588434] [S] lock(&rwlock_A:0) [ 4.588804] [W] lock(&rwlock_B:0) [ 4.589175] [E] unlock(&rwlock_A:0) [ 4.589565] [ 4.589727] context B [ 4.589963] [S] lock(&rwlock_B:0) [ 4.590375] [W] lock(&rwlock_A:0) [ 4.590749] [E] unlock(&rwlock_B:0) [ 4.591136] [ 4.591295] [S]: start of the event context [ 4.591716] [W]: the wait blocked [ 4.592049] [E]: the event not reachable [ 4.592443] --------------------------------------------------- [ 4.593037] context A's detail [ 4.593351] --------------------------------------------------- [ 4.593944] context A [ 4.594182] [S] lock(&rwlock_A:0) [ 4.594577] [W] lock(&rwlock_B:0) [ 4.594952] [E] unlock(&rwlock_A:0) [ 4.595341] [ 4.595501] [S] lock(&rwlock_A:0): [ 4.595848] [] queued_read_lock_hardirq_ER_rE+0xf4/0x170 [ 4.596547] stacktrace: [ 4.596797] _raw_read_lock+0xcf/0x110 [ 4.597215] queued_read_lock_hardirq_ER_rE+0xf4/0x170 [ 4.597766] dotest+0x30/0x7bc [ 4.598118] locking_selftest+0x2c6f/0x2ead [ 4.598602] start_kernel+0x5aa/0x6d5 [ 4.599017] secondary_startup_64_no_verify+0xe0/0xeb [ 4.599562] [ 4.599721] [W] lock(&rwlock_B:0): [ 4.600064] [] queued_read_lock_hardirq_ER_rE+0x100/0x170 [ 4.600823] stacktrace: [ 4.601075] dept_wait+0x12c/0x1d0 [ 4.601465] _raw_write_lock+0xa0/0xd0 [ 4.601892] queued_read_lock_hardirq_ER_rE+0x100/0x170 [ 4.602496] dotest+0x30/0x7bc [ 4.602854] locking_selftest+0x2c6f/0x2ead [ 4.603333] start_kernel+0x5aa/0x6d5 [ 4.603745] secondary_startup_64_no_verify+0xe0/0xeb [ 4.604298] [ 4.604458] [E] unlock(&rwlock_A:0): [ 4.604820] (N/A) [ 4.605023] --------------------------------------------------- [ 4.605617] context B's detail [ 4.605930] --------------------------------------------------- [ 4.606551] context B [ 4.606790] [S] lock(&rwlock_B:0) [ 4.607163] [W] lock(&rwlock_A:0) [ 4.607534] [E] unlock(&rwlock_B:0) [ 4.607920] [ 4.608080] [S] lock(&rwlock_B:0): [ 4.608427] [] queued_read_lock_hardirq_RE_Er+0xf4/0x170 [ 4.609113] stacktrace: [ 4.609366] _raw_write_lock+0xc3/0xd0 [ 4.609788] queued_read_lock_hardirq_RE_Er+0xf4/0x170 [ 4.610371] dotest+0x30/0x7bc [ 4.610730] locking_selftest+0x2c41/0x2ead [ 4.611195] start_kernel+0x5aa/0x6d5 [ 4.611615] secondary_startup_64_no_verify+0xe0/0xeb [ 4.612164] [ 4.612325] [W] lock(&rwlock_A:0): [ 4.612671] [] queued_read_lock_hardirq_RE_Er+0x100/0x170 [ 4.613369] stacktrace: [ 4.613622] _raw_read_lock+0xac/0x110 [ 4.614047] queued_read_lock_hardirq_RE_Er+0x100/0x170 [ 4.614652] dotest+0x30/0x7bc [ 4.615007] locking_selftest+0x2c41/0x2ead [ 4.615468] start_kernel+0x5aa/0x6d5 [ 4.615879] secondary_startup_64_no_verify+0xe0/0xeb [ 4.616607] [ 4.616769] [E] unlock(&rwlock_B:0): [ 4.617132] (N/A) [ 4.617336] --------------------------------------------------- [ 4.617927] information that might be helpful [ 4.618390] --------------------------------------------------- [ 4.618981] CPU: 0 PID: 0 Comm: swapper/0 Tainted: G W 6.0.0-00023-g331e0412f735 #2 [ 4.619886] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Bochs 01/01/2011 [ 4.620699] Call Trace: [ 4.620958] [ 4.621182] dump_stack_lvl+0x5d/0x81 [ 4.621561] print_circle.cold+0x52b/0x545 [ 4.621983] ? print_circle+0xd0/0xd0 [ 4.622385] cb_check_dl+0x58/0x60 [ 4.622737] bfs+0xba/0x170 [ 4.623029] add_dep+0x85/0x170 [ 4.623355] ? from_pool+0x4c/0x160 [ 4.623714] __dept_wait+0x1fd/0x600 [ 4.624081] ? queued_read_lock_hardirq_ER_rE+0x100/0x170 [ 4.624628] ? rcu_read_lock_held_common+0x9/0x50 [ 4.625108] ? queued_read_lock_hardirq_ER_rE+0x100/0x170 [ 4.625652] dept_wait+0x12c/0x1d0 [ 4.626000] _raw_write_lock+0xa0/0xd0 [ 4.626417] queued_read_lock_hardirq_ER_rE+0x100/0x170 [ 4.626951] dotest+0x30/0x7bc [ 4.627270] locking_selftest+0x2c6f/0x2ead [ 4.627702] start_kernel+0x5aa/0x6d5 [ 4.628081] secondary_startup_64_no_verify+0xe0/0xeb [ 4.628597] --- The most important part is the following. [ 4.588198] context A [ 4.588434] [S] lock(&rwlock_A:0) [ 4.588804] [W] lock(&rwlock_B:0) [ 4.589175] [E] unlock(&rwlock_A:0) [ 4.589565] [ 4.589727] context B [ 4.589963] [S] lock(&rwlock_B:0) [ 4.590375] [W] lock(&rwlock_A:0) [ 4.590749] [E] unlock(&rwlock_B:0) As I told you, DEPT treats a queued lock as a normal type lock, no matter whether it's a read lock. That's why it prints just 'lock(&rwlock_A:0)' instead of 'read_lock(&rwlock_A:0)'. If needed, I'm gonna change the format. I checked the selftest code and found, LOCK(B) is transformed like: LOCK(B) -> WL(B) -> write_lock(&rwlock_B) That's why '&rwlock_B' is printed instead of just 'B', JFYI. Plus, for your information, you should turn on CONFIG_DEPT to use it. Byungchul