From: Byungchul Park <byungchul.park@lge.com> To: peterz@infradead.org, mingo@kernel.org Cc: tglx@linutronix.de, npiggin@kernel.dk, walken@google.com, boqun.feng@gmail.com, kirill@shutemov.name, linux-kernel@vger.kernel.org, linux-mm@kvack.org Subject: [RFC v2 00/13] lockdep: Implement crossrelease feature Date: Thu, 7 Jul 2016 18:29:50 +0900 [thread overview] Message-ID: <1467883803-29132-1-git-send-email-byungchul.park@lge.com> (raw) Change from v1 - enhanced the document - removed save_stack_trace() optimizing patch - made this based on the seperated save_stack_trace patchset https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg1182242.html Can we detect deadlocks descriped below, with lockdep? No. Example 1) PROCESS X PROCESS Y -------------- -------------- mutext_lock A lock_page B lock_page B mutext_lock A // DEADLOCK unlock_page B mutext_unlock A mutex_unlock A unlock_page B We are not checking the dependency for lock_page() at all now. Example 2) PROCESS X PROCESS Y PROCESS Z -------------- -------------- -------------- mutex_lock A lock_page B lock_page B mutext_lock A // DEADLOCK mutext_unlock A unlock_page B (B was held by PROCESS X) unlock_page B mutex_unlock A We cannot detect this kind of deadlock with lockdep, even though we apply the dependency check using lockdep on lock_page(). Example 3) PROCESS X PROCESS Y -------------- -------------- mutex_lock A mutex_lock A mutex_unlock A wait_for_complete B // DEADLOCK complete B mutex_unlock A wait_for_complete() and complete() also can cause a deadlock, however we cannot detect it with lockdep, either. Not only lock operations, but also any operations causing to wait or spin for something can cause deadlock unless it's eventually *released* by someone. The important point here is that the waiting or spinning must be *released* by someone. In other words, we have to focus whether the waiting or spinning can be *released* or not to check a deadlock possibility, rather than the waiting or spinning itself. In this point of view, typical lock is a special case where the acquire context is same as the release context, so no matter in which context the checking is performed for typical lock. Of course, in order to be able to report deadlock imediately at the time real deadlock actually occures, the checking must be performed before actual blocking or spinning happens when acquiring it. However, deadlock *possibility* can be detected and reported even the checking is done when releasing it, which means the time we can identify the release context. Given that the assumption the current lockdep has is relaxed, we can check dependency and detect deadlock possibility not only for typical lock, but also for lock_page() using PG_locked, wait_for_xxx() and so on, which might be released by different context from the context which held the lock. My implementation makes it possible. See the last patch including the document for more information. --- Byungchul Park (13): lockdep: Refactor lookup_chain_cache() lockdep: Add a function building a chain between two hlocks lockdep: Make check_prev_add can use a stack_trace of other context lockdep: Make save_trace can copy from other stack_trace lockdep: Implement crossrelease feature lockdep: Apply crossrelease to completion pagemap.h: Remove trailing white space lockdep: Apply crossrelease to PG_locked lock cifs/file.c: Remove trailing white space mm/swap_state.c: Remove trailing white space lockdep: Call lock_acquire(release) when accessing PG_locked manually lockdep: Make crossrelease use save_stack_trace_norm() instead lockdep: Add a document describing crossrelease feature Documentation/locking/crossrelease.txt | 457 ++++++++++++++++++ fs/cifs/file.c | 6 +- include/linux/completion.h | 121 ++++- include/linux/irqflags.h | 16 +- include/linux/lockdep.h | 139 ++++++ include/linux/mm_types.h | 9 + include/linux/pagemap.h | 104 +++- include/linux/sched.h | 5 + kernel/fork.c | 4 + kernel/locking/lockdep.c | 852 ++++++++++++++++++++++++++++++--- kernel/sched/completion.c | 55 ++- lib/Kconfig.debug | 30 ++ mm/filemap.c | 10 +- mm/ksm.c | 1 + mm/migrate.c | 1 + mm/page_alloc.c | 3 + mm/shmem.c | 2 + mm/swap_state.c | 12 +- mm/vmscan.c | 1 + 19 files changed, 1706 insertions(+), 122 deletions(-) create mode 100644 Documentation/locking/crossrelease.txt -- 1.9.1
WARNING: multiple messages have this Message-ID (diff)
From: Byungchul Park <byungchul.park@lge.com> To: peterz@infradead.org, mingo@kernel.org Cc: tglx@linutronix.de, npiggin@kernel.dk, walken@google.com, boqun.feng@gmail.com, kirill@shutemov.name, linux-kernel@vger.kernel.org, linux-mm@kvack.org Subject: [RFC v2 00/13] lockdep: Implement crossrelease feature Date: Thu, 7 Jul 2016 18:29:50 +0900 [thread overview] Message-ID: <1467883803-29132-1-git-send-email-byungchul.park@lge.com> (raw) Change from v1 - enhanced the document - removed save_stack_trace() optimizing patch - made this based on the seperated save_stack_trace patchset https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg1182242.html Can we detect deadlocks descriped below, with lockdep? No. Example 1) PROCESS X PROCESS Y -------------- -------------- mutext_lock A lock_page B lock_page B mutext_lock A // DEADLOCK unlock_page B mutext_unlock A mutex_unlock A unlock_page B We are not checking the dependency for lock_page() at all now. Example 2) PROCESS X PROCESS Y PROCESS Z -------------- -------------- -------------- mutex_lock A lock_page B lock_page B mutext_lock A // DEADLOCK mutext_unlock A unlock_page B (B was held by PROCESS X) unlock_page B mutex_unlock A We cannot detect this kind of deadlock with lockdep, even though we apply the dependency check using lockdep on lock_page(). Example 3) PROCESS X PROCESS Y -------------- -------------- mutex_lock A mutex_lock A mutex_unlock A wait_for_complete B // DEADLOCK complete B mutex_unlock A wait_for_complete() and complete() also can cause a deadlock, however we cannot detect it with lockdep, either. Not only lock operations, but also any operations causing to wait or spin for something can cause deadlock unless it's eventually *released* by someone. The important point here is that the waiting or spinning must be *released* by someone. In other words, we have to focus whether the waiting or spinning can be *released* or not to check a deadlock possibility, rather than the waiting or spinning itself. In this point of view, typical lock is a special case where the acquire context is same as the release context, so no matter in which context the checking is performed for typical lock. Of course, in order to be able to report deadlock imediately at the time real deadlock actually occures, the checking must be performed before actual blocking or spinning happens when acquiring it. However, deadlock *possibility* can be detected and reported even the checking is done when releasing it, which means the time we can identify the release context. Given that the assumption the current lockdep has is relaxed, we can check dependency and detect deadlock possibility not only for typical lock, but also for lock_page() using PG_locked, wait_for_xxx() and so on, which might be released by different context from the context which held the lock. My implementation makes it possible. See the last patch including the document for more information. --- Byungchul Park (13): lockdep: Refactor lookup_chain_cache() lockdep: Add a function building a chain between two hlocks lockdep: Make check_prev_add can use a stack_trace of other context lockdep: Make save_trace can copy from other stack_trace lockdep: Implement crossrelease feature lockdep: Apply crossrelease to completion pagemap.h: Remove trailing white space lockdep: Apply crossrelease to PG_locked lock cifs/file.c: Remove trailing white space mm/swap_state.c: Remove trailing white space lockdep: Call lock_acquire(release) when accessing PG_locked manually lockdep: Make crossrelease use save_stack_trace_norm() instead lockdep: Add a document describing crossrelease feature Documentation/locking/crossrelease.txt | 457 ++++++++++++++++++ fs/cifs/file.c | 6 +- include/linux/completion.h | 121 ++++- include/linux/irqflags.h | 16 +- include/linux/lockdep.h | 139 ++++++ include/linux/mm_types.h | 9 + include/linux/pagemap.h | 104 +++- include/linux/sched.h | 5 + kernel/fork.c | 4 + kernel/locking/lockdep.c | 852 ++++++++++++++++++++++++++++++--- kernel/sched/completion.c | 55 ++- lib/Kconfig.debug | 30 ++ mm/filemap.c | 10 +- mm/ksm.c | 1 + mm/migrate.c | 1 + mm/page_alloc.c | 3 + mm/shmem.c | 2 + mm/swap_state.c | 12 +- mm/vmscan.c | 1 + 19 files changed, 1706 insertions(+), 122 deletions(-) create mode 100644 Documentation/locking/crossrelease.txt -- 1.9.1 -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
next reply other threads:[~2016-07-07 9:32 UTC|newest] Thread overview: 40+ messages / expand[flat|nested] mbox.gz Atom feed top 2016-07-07 9:29 Byungchul Park [this message] 2016-07-07 9:29 ` [RFC v2 00/13] lockdep: Implement crossrelease feature Byungchul Park 2016-07-07 9:29 ` [RFC v2 01/13] lockdep: Refactor lookup_chain_cache() Byungchul Park 2016-07-07 9:29 ` Byungchul Park 2016-07-07 9:29 ` [RFC v2 02/13] lockdep: Add a function building a chain between two hlocks Byungchul Park 2016-07-07 9:29 ` Byungchul Park 2016-07-07 9:29 ` [RFC v2 03/13] lockdep: Make check_prev_add can use a stack_trace of other context Byungchul Park 2016-07-07 9:29 ` Byungchul Park 2016-07-07 9:29 ` [RFC v2 04/13] lockdep: Make save_trace can copy from other stack_trace Byungchul Park 2016-07-07 9:29 ` Byungchul Park 2016-07-07 9:29 ` [RFC v2 05/13] lockdep: Implement crossrelease feature Byungchul Park 2016-07-07 9:29 ` Byungchul Park 2016-07-07 9:29 ` [RFC v2 06/13] lockdep: Apply crossrelease to completion Byungchul Park 2016-07-07 9:29 ` Byungchul Park 2016-07-07 9:29 ` [RFC v2 07/13] pagemap.h: Remove trailing white space Byungchul Park 2016-07-07 9:29 ` Byungchul Park 2016-07-07 9:29 ` [RFC v2 08/13] lockdep: Apply crossrelease to PG_locked lock Byungchul Park 2016-07-07 9:29 ` Byungchul Park 2016-07-07 9:29 ` [RFC v2 09/13] cifs/file.c: Remove trailing white space Byungchul Park 2016-07-07 9:29 ` Byungchul Park 2016-07-07 9:30 ` [RFC v2 10/13] mm/swap_state.c: " Byungchul Park 2016-07-07 9:30 ` Byungchul Park 2016-07-07 9:30 ` [RFC v2 11/13] lockdep: Call lock_acquire(release) when accessing PG_locked manually Byungchul Park 2016-07-07 9:30 ` Byungchul Park 2016-07-07 9:30 ` [RFC v2 12/13] lockdep: Make crossrelease use save_stack_trace_norm() instead Byungchul Park 2016-07-07 9:30 ` Byungchul Park 2016-07-07 9:30 ` [RFC v2 13/13] lockdep: Add a document describing crossrelease feature Byungchul Park 2016-07-07 9:30 ` Byungchul Park 2016-07-18 1:39 ` Byungchul Park 2016-07-18 1:39 ` Byungchul Park 2016-07-18 7:01 ` Byungchul Park 2016-07-18 7:01 ` Byungchul Park 2016-07-07 10:16 ` [RFC v2 00/13] lockdep: Implement " Byungchul Park 2016-07-07 10:16 ` Byungchul Park 2016-08-19 12:39 ` [Revised document] Crossrelease lockdep Byungchul Park 2016-08-19 12:39 ` Byungchul Park 2016-08-22 4:13 ` Byungchul Park 2016-08-22 4:13 ` Byungchul Park 2016-08-23 5:55 ` Byungchul Park 2016-08-23 5:55 ` Byungchul Park
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=1467883803-29132-1-git-send-email-byungchul.park@lge.com \ --to=byungchul.park@lge.com \ --cc=boqun.feng@gmail.com \ --cc=kirill@shutemov.name \ --cc=linux-kernel@vger.kernel.org \ --cc=linux-mm@kvack.org \ --cc=mingo@kernel.org \ --cc=npiggin@kernel.dk \ --cc=peterz@infradead.org \ --cc=tglx@linutronix.de \ --cc=walken@google.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.