From patchwork Wed Feb 21 09:49:33 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Byungchul Park X-Patchwork-Id: 13565304 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 72CD1C48BC3 for ; Wed, 21 Feb 2024 09:50:47 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id EAA5F6B00A2; Wed, 21 Feb 2024 04:50:09 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id E108B6B00A5; Wed, 21 Feb 2024 04:50:09 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B4DFD6B00A2; Wed, 21 Feb 2024 04:50:09 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id 95FEE6B00A0 for ; Wed, 21 Feb 2024 04:50:09 -0500 (EST) Received: from smtpin06.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 6F4E780A00 for ; Wed, 21 Feb 2024 09:50:09 +0000 (UTC) X-FDA: 81815340138.06.E70245D Received: from invmail4.hynix.com (exvmail4.hynix.com [166.125.252.92]) by imf01.hostedemail.com (Postfix) with ESMTP id 9489140003 for ; Wed, 21 Feb 2024 09:50:07 +0000 (UTC) Authentication-Results: imf01.hostedemail.com; dkim=none; spf=pass (imf01.hostedemail.com: domain of byungchul@sk.com designates 166.125.252.92 as permitted sender) smtp.mailfrom=byungchul@sk.com; dmarc=none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1708509007; 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=lqQKl1QbMFiApJxxUbhttXaNF5Aclg433q+p5cQ+jWo=; b=iUu8UeVQyBAPAzmPfjv5Th7ew145+VnRUKy0RmOgpZecxVclhwZrWWSobA3wmJNi2ddQPe DzeUqgbMJLC6WTSRkkDiLS+BzmqUFTldYHlNzPzlZkxaUVfqPQg0hQ8hrU4OjmlBdWh7Qi 7WcAbRNKYnAD2EWkyNE3TbxIZ1WzCwg= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1708509007; a=rsa-sha256; cv=none; b=efUJDWijkqr2UmDdPvY86UWBQg5D3fp4dHg9xJIsR91ieh64rf6AIy2KCuw/f51Wp3VuXO XDk57HaLcH7qgr9UQdaRGiArm+HGu+hbif6SXJGZn2jyPN2632Rdf7IiyubxIWRwejZPyK dRjSkg5RTgvZbTWrSJX1PctDQ1FCvOU= ARC-Authentication-Results: i=1; imf01.hostedemail.com; dkim=none; spf=pass (imf01.hostedemail.com: domain of byungchul@sk.com designates 166.125.252.92 as permitted sender) smtp.mailfrom=byungchul@sk.com; dmarc=none X-AuditID: a67dfc5b-d85ff70000001748-39-65d5c73b28e7 From: Byungchul Park To: linux-kernel@vger.kernel.org Cc: kernel_team@skhynix.com, 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, 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, boqun.feng@gmail.com, longman@redhat.com, hdanton@sina.com, her0gyugyu@gmail.com Subject: [PATCH v12 27/27] dept: Add 'Dept' documentation Date: Wed, 21 Feb 2024 18:49:33 +0900 Message-Id: <20240221094933.36348-28-byungchul@sk.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20240221094933.36348-1-byungchul@sk.com> References: <20240221094933.36348-1-byungchul@sk.com> X-Brightmail-Tracker: H4sIAAAAAAAAAzWSa0yTZxTHfZ73SrX4ppr4Tkw0TRSnUUFBj4aZGW+PRqOJyT64LVrlVRoL aLlZEw1qqaUV4yUFFdQCpnaFTXyLERQMQgCRqKDlogGizKjEIhfXuo46bDF+Ofnl/z/n9+nw lKqamclrU9IlfYpGp2YVtGJwSvGihOYOKSZQo4Bzp2PA94+ZhqKb5Sy0/VWGoLzyOIaBxo3Q 5fciGHv8lIICWxuC4te9FFQ29SGodZ5g4fmbSPD4hlhosVlZOFl6k4X2D0EMPfnnMZTJW6H1 bAmGusA7GgoGWCgsOIlD4z2GgMPFgSN7LvQ7L3MQfB0LLX2dDNS+XAiXrvawUFPbQkNTVT+G 53eLWOgrH2egtekhDW3n8hj482MJCx/8DgocviEOntXZMVQYQyLTp/8ZaM6rw2C6fguD58U9 BPfNrzDI5Z0sNPi8GNyyjYL/bjQi6D8zyEHO6QAHhcfPILDm5NPw9EszA8aeeBj7t4j9eRVp 8A5RxOjOIrV+O00elYik+nIvR4z3X3LELmcQt3MBKa0ZwKR41McQ2ZXLEnn0PEcsgx5MPj55 wpGHF8do8sZTgLdH7VQkJEo6baakX7J6tyLJbsvhDl5JOFz2aYzKRv75FhTBi0Kc+O5EF2tB /AT33tgVjlkhWuzuDlBhni7MEd15bxkLUvCUcGqy6Bx+zIaLacJKsaG7kQkzLcwV3WYbFfYo heXiSNDwTT9bLKuom/BEhOI/Cr0T6yohXuxov02FnaJgjRCDX4LMt4MfxAfObvosUtrRJBdS aVMykzVaXdziJEOK9vDivanJMgo9lONo8NcqNNq2ox4JPFJPUSbd8UgqRpOZZkiuRyJPqacr 6axQpEzUGI5I+tRd+gydlFaPonhaPUO51J+VqBL2a9KlA5J0UNJ/bzEfMTMbWa3pOuO63MgX yzrhWK7DZP5pXqTBFF3zi4tq31waG1c1Lm8iK9S/Y8ucuGXT/OmpFZptJRuK46fuyV+zNnl9 QsaI9UhFx7PhWzuv7Zv/+ULPYGrr+G8xZmZ0+Me/7V3qjspFs2YsbdZbho9dz66WmY2ZnUf3 ZXk/LxyZbDrkitqSqKbTkjSxCyh9muYrda9QDUwDAAA= X-Brightmail-Tracker: H4sIAAAAAAAAAzWSa0hTcRjG+5/L/xxXi8M0PHShGEplZUZab2jXD3WIjAgqsg866uCW17ay DALzUmZZai0tLTarZWqlm91TlkvnutjMeUnU0qQSV+u2kWmXLejLy8Pvefh9ellSVkpPZVXJ e0V1siJRjiWUZGNk1oJIa4cYVtAdAoUnwsD9PZeCspvVGOw3qhBU1x0mYLhpHXR5nAjGnr8g oVhrR6Af6COhrrkfQX1FJob2ocngcLsw2LTHMWRduomhbWScgN6zRQRUGaPhaUE5AebR9xQU D2MoLc4ivOcDAaOGSgYMGcEwWHGegfGBRWDr76TBcsFGQ33PPDh3sRfDw3obBc13Bwlov1+G ob/6Dw1Pm1sosBfm03D9UzmGEY+BBIPbxcBLs46Ammyv7ci33zRY880EHLlcS4Dj1QMEDblv CDBWd2KwuJ0EmIxaEn5ebUIwePIjAzknRhkoPXwSwfGcsxS8+GWlIbs3AsZ+lOFVkYLF6SKF bNN+od6jo4Qn5bxw73wfI2Q39DCCzrhPMFWECJceDhOC/qubFoyVx7Bg/FrECHkfHYTwqbWV EVpKxihhyFFMbJoeI4naJSaq0kT1whVxEqVOm8OkXog6UPVtjMxAnjl5iGV5Lpzvuxqbh/xY zM3mu7tHSV8O4Gbxpvx3dB6SsCR3dCJf8fk59hX+3DLe0t1E+zLFBfOmXC3p80i5JfyX8XQf 5rmZfFWN+Z/Hz4uvlTr/zWVcBN/RdossQBIdmlCJAlTJaUkKVWJEqCZBmZ6sOhC6MyXJiLwv Yzg0XngXfW9f14g4FsknSZV3HKKMVqRp0pMaEc+S8gAptd+LpLsU6QdFdUqsel+iqGlE01hK Hihdv02Mk3Hxir1igiimiur/LcH6Tc1At/ccTIr3hEWx5dH2GF2tNefU0pYdrctbn1Hro+ML uWDnmgHuypTw0BlKw7z78wNjUiKCFk/yo3dbA7Uul/6aJXBD0Gv/npIZNtPcrCsjAz+3rDwz f1rDlu2bM1eTRTsrgx6/HXqvV5q/RIfiTP3prV11a2NluCShJffBoyZ7nP8POaVRKhaFkGqN 4i+4H0qqLgMAAA== X-CFilter-Loop: Reflected X-Stat-Signature: 75jrgqwwptd85anw8g83186qwpgsfmmh X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: 9489140003 X-Rspam-User: X-HE-Tag: 1708509007-738667 X-HE-Meta: U2FsdGVkX18TT1Vqp852nHnViCCZtYdm6GPVnooCsGy17m/noAcS3iUo6jnzGGEHgYamgfWNw+kC8NaZOVCKzADQoPXuv5zeeVX4K4mUKasx46N8xvAlPzYsv3fgie0Usb1eWLI03LspmMNcNo31X2OAcGElFGgol47zXvfRBc8LSBW3Y7SxX/TJ0emO808c6tJ/5HfTP7ehIZEFkMXyMz/a8asunkwRytWWP4rhxtRgs/oQzs/8f892hLw7Cat0r808cDwLqspNIE/vSkBlmq7/0M8aCvlBQcTsUOO6D336vbWjWiIfM+rL1FJKdDvQ8Oo4PbN/xQlNq+H9jY4LyZBBInzAJohwOLNPRF5BRoRn3WakGpv2Z6G3CoaT50bpss6YFL6k9a6Z2pBPjTcDXuAim8KQAvK/xj0tn0B/RKCFTH4Kq3NRJHww+HifML0zHYG3Cv9hxbN/e6jiHPSro1jVXw+HwgT3ILBGocuau+tvbmY+C4jvWzpLLAmFDKif/f6LvQQ3gn0IVqpQGvwCdDP3UrGaoG3KD+FwX9UOjMzriewmFUTjY7k30reB1M4p/KTZiTsPa0KM5HalSa8Dl/atYqlmo6veBp0mibsltUATyAbGJfn2QnAD+QxF1tLRkegxSLBfY3Bz66wKLLr88SwQMbKA5ZRLjiurm+C0jD9sBR7rrX/bHfJu6/CO7IDk+XD8hBKS5aA/cyrs/v5a1n73HdCr/y74EQ47OswalU617Xs4nNLB4Ho2ZEeGal6ZqfT3PCn49R6INo9nRPa3VA9c64slKZIaw0HM1be/Q9ThhfoKDpqhY6RnaHnrTVJJMydnk1PCuHN8jwFJ0L3BhmfNd3aS3ezSyR3RJCC3d3ZCpOshMTEw2jYHHzkzFMces1Gf7BreOoeUJRaN6IF0YzgBS8CkgCTsxtbeccBpjQyioFfkaMeutlgzXIwbfLG9mFTfPUyLzZzY2ZLIYTm Jbehl9ff KaAs7T0m0v9uvRtexUiUtFbnrakBu7N3YE8OSMqaZKPI3MD5mdRve4mjhgkQRR0IsoPqC 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: List-Subscribe: List-Unsubscribe: This document describes the concept of Dept. Signed-off-by: Byungchul Park --- Documentation/dependency/dept.txt | 283 ++++++++++++++++++++++++++++++ 1 file changed, 283 insertions(+) create mode 100644 Documentation/dependency/dept.txt diff --git a/Documentation/dependency/dept.txt b/Documentation/dependency/dept.txt new file mode 100644 index 000000000000..7efe3bc59b2d --- /dev/null +++ b/Documentation/dependency/dept.txt @@ -0,0 +1,283 @@ +DEPT(DEPendency Tracker) +======================== + +Started by Byungchul Park + +How lockdep works +----------------- + +Lockdep tries to detect a deadlock by checking lock acquisition order. +For example, consider a graph built by lockdep like: + + A -> B - + \ + -> E + / + C -> D - + + where 'A -> B' means that acquisition A is prior to acquisition B + with A still held. + +Lockdep keeps adding each new acquisition order into the graph in +runtime. For example, 'E -> C' will be added when it's recognized that +the two locks have been acquired in that order like: + + A -> B - + \ + -> E - + / \ + -> C -> D - \ + / / + \ / + ------------------ + + where 'A -> B' means that acquisition A is prior to acquisition B + with A still held. + +This graph contains a subgraph that demonstrates a loop like: + + -> E - + / \ + -> C -> D - \ + / / + \ / + ------------------ + + where 'A -> B' means that acquisition A is prior to acquisition B + with A still held. + +Lockdep reports it as a deadlock on detection of a loop. + +CONCLUSION + +Lockdep detects a deadlock by checking if a loop has been created after +expanding the graph. + + +Limitation of lockdep +--------------------- + +Lockdep works on typical lock e.g. spinlock and mutex, that are supposed +to be released within the acquisition context. However, a deadlock by +folio lock or other synchronization mechanisms cannot be detected by +lockdep that basically tracks lock acquisition order. + +Can we detect the following deadlock? + + CONTEXT X CONTEXT Y CONTEXT Z + + mutex_lock A + folio_lock B + folio_lock B + mutex_lock A /* DEADLOCK */ + folio_unlock B + folio_unlock B + mutex_unlock A + mutex_unlock A + +No, we can't. What about the following? + + CONTEXT X CONTEXT Y + + mutex_lock A + mutex_lock A + wait_for_complete B /* DEADLOCK */ + complete B + mutex_unlock A + mutex_unlock A + +No, we can't. + +CONCLUSION + +Given the limitation, lockdep cannot detect a deadlock by folio lock or +other synchronization mechanisms. + + +What leads a deadlock +--------------------- + +A deadlock occurs when one or multi contexts are waiting for events that +will never happen. For example: + + CONTEXT X CONTEXT Y CONTEXT Z + + | | | + v | | + (1) wait for A v | + . (2) wait for C v + event C . (3) wait for B + event B . + event A + +Event C cannot be triggered because context X is stuck at (1), event B +cannot be triggered because context Y is stuck at (2), and event A +cannot be triggered because context Z is stuck at (3). All the contexts +are stuck. We call the situation a *deadlock*. + +If an event occurrence is a prerequisite to reaching another event, we +call it *dependency*. In the example above: + + Event A occurrence is a prerequisite to reaching event C. + Event C occurrence is a prerequisite to reaching event B. + Event B occurrence is a prerequisite to reaching event A. + +In terms of dependency: + + Event C depends on event A. + Event B depends on event C. + Event A depends on event B. + +Dependencies in a graph look like: + + -> C -> A -> B - + / \ + \ / + ---------------- + + where 'A -> B' means that event A depends on event B. + +A circular dependency exists. Such a circular dependency leads a +deadlock since no waiters can have desired events triggered. + +CONCLUSION + +A circular dependency leads a deadlock. + + +Introduce DEPT +-------------- + +DEPT(DEPendency Tracker) tracks wait and event instead of lock +acquisition order so as to recognize the following situation: + + CONTEXT X CONTEXT Y CONTEXT Z + + | | | + v | | + wait for A v | + . wait for C v + event C . wait for B + event B . + event A + +and builds up a dependency graph in runtime, similar to lockdep. The +graph would look like: + + -> C -> A -> B - + / \ + \ / + ---------------- + + where 'A -> B' means that event A depends on event B. + +DEPT keeps adding each new dependency into the graph in runtime. For +example, 'B -> D' will be added when it's recognized that event D +occurrence is a prerequisite to reaching event B, in other words, event +B depends on event D like: + + | + v + wait for D + . + event B + +After adding 'B -> D' dependency into the graph, the graph would look +like: + + -> D + / + -> C -> A -> B - + / \ + \ / + ---------------- + + where 'A -> B' means that event A depends on event B. + +DEPT is going to report a deadlock on detection of a new loop. + +CONCLUSION + +DEPT works on wait and event so as to theoretically detect all the +potential deadlocks. + + +How DEPT works +-------------- + +Let's take a look how DEPT works with an example that was mentioned in +the section 'Limitation of lockdep'. + + CONTEXT X CONTEXT Y CONTEXT Z + + mutex_lock A + folio_lock B + folio_lock B + mutex_lock A /* DEADLOCK */ + folio_unlock B + folio_unlock B + mutex_unlock A + mutex_unlock A + +Add comments to describe DEPT's view using terms of wait and event. + + CONTEXT X CONTEXT Y CONTEXT Z + + mutex_lock A + /* start to take into account event A context */ + folio_lock B + /* start to take into account event B context */ + + folio_lock B + /* wait for B */ + (1) + mutex_lock A /* DEADLOCK */ + /* wait for A */ + (2) + + folio_unlock B + /* event B */ + folio_unlock B + /* not interest until reaching (1) */ + + mutex_unlock A + /* event A */ + mutex_unlock A + /* not interest until reaching (2) */ + +Focusing on wait and event, the example can be simplified like: + + CONTEXT X CONTEXT Y CONTEXT Z + + | | + | | + v | + wait for B v + . wait for A + . . + . event B + event A + +Event A occurrence is a prerequisite to reaching event B, and event B +occurrence is a prerequisite to reaching event A. + +In terms of dependency: + + Event B depends on event A. + Event A depends on event B. + +Dependencies in the dependency graph look like: + + -> A -> B - + / \ + \ / + ----------- + + where 'A -> B' means that event A depends on event B. + +A loop has been created. So DEPT can report it as a deadlock. + +CONCLUSION + +DEPT works well with any synchronization mechanisms by focusing on wait +and event.