linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH v4 00/15] lockdep: Implement crossrelease feature
@ 2016-12-09  5:11 Byungchul Park
  2016-12-09  5:11 ` [PATCH v4 01/15] x86/dumpstack: Optimize save_stack_trace Byungchul Park
                   ` (15 more replies)
  0 siblings, 16 replies; 55+ messages in thread
From: Byungchul Park @ 2016-12-09  5:11 UTC (permalink / raw)
  To: peterz, mingo
  Cc: tglx, walken, boqun.feng, kirill, linux-kernel, linux-mm,
	iamjoonsoo.kim, akpm, npiggin

I checked if crossrelease feature works well on my qemu-i386 machine.
There's no problem at all to work on mine. But I wonder if it's also
true even on other machines. Especially, on large system. Could you
let me know if it doesn't work on yours? Or Could you let me know if
crossrelease feature is useful? Please let me know if you need to
backport it to another version but it's not easy. Then I can provide
the backported version after working it.

I added output text of 'cat /proc/lockdep' on my machine applying
crossrelease feature, showing dependencies of lockdep. You can check
what kind of dependencies are added by crossrelease feature. Please
use '(complete)' or '(PG_locked)' as a keyword to find dependencies
added by this patch set.

And I still keep the base unchanged (v4.7). I will rebase it on the
latest once you have a consensus on it. Your opinions?

-----8<-----

Change from v3
	- reviced document

Change from v2
	- rebase on vanilla v4.7 tag
	- move lockdep data for page lock from struct page to page_ext
	- allocate plocks buffer via vmalloc instead of in struct task
	- enhanced comments and document
	- optimize performance
	- make reporting function crossrelease-aware

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 below with original lockdep?

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

where A and B are different lock classes.

No, we cannot.

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

where A and B are different lock classes.

No, we cannot.

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

where A is a lock class and B is a completion variable.

No, we cannot.

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.

Using crossrelease feature, we can check dependency and detect deadlock
possibility not only for typical lock, but also for lock_page(),
wait_for_xxx() and so on, which might be released in any context.

See the last patch including the document for more information.

Byungchul Park (15):
  x86/dumpstack: Optimize save_stack_trace
  x86/dumpstack: Add save_stack_trace()_fast()
  lockdep: Refactor lookup_chain_cache()
  lockdep: Add a function building a chain between two classes
  lockdep: Make check_prev_add can use a separate stack_trace
  lockdep: Make save_trace can skip stack tracing of the current
  lockdep: Implement crossrelease feature
  lockdep: Make crossrelease use save_stack_trace_fast()
  lockdep: Make print_circular_bug() crosslock-aware
  lockdep: Apply crossrelease to completion operation
  pagemap.h: Remove trailing white space
  lockdep: Apply crossrelease to PG_locked lock
  lockdep: Apply lock_acquire(release) on __Set(__Clear)PageLocked
  lockdep: Move data used in CONFIG_LOCKDEP_PAGELOCK from page to
    page_ext
  lockdep: Crossrelease feature documentation

 Documentation/locking/crossrelease.txt | 1053 ++++++++++++++++++++++++++++++++
 arch/x86/include/asm/stacktrace.h      |    1 +
 arch/x86/kernel/dumpstack.c            |    4 +
 arch/x86/kernel/dumpstack_32.c         |    2 +
 arch/x86/kernel/stacktrace.c           |   32 +
 include/linux/completion.h             |  121 +++-
 include/linux/irqflags.h               |   12 +-
 include/linux/lockdep.h                |  122 ++++
 include/linux/mm_types.h               |    4 +
 include/linux/page-flags.h             |   43 +-
 include/linux/page_ext.h               |    5 +
 include/linux/pagemap.h                |  124 +++-
 include/linux/sched.h                  |    5 +
 include/linux/stacktrace.h             |    2 +
 kernel/exit.c                          |    9 +
 kernel/fork.c                          |   20 +
 kernel/locking/lockdep.c               |  804 +++++++++++++++++++++---
 kernel/sched/completion.c              |   54 +-
 lib/Kconfig.debug                      |   30 +
 mm/filemap.c                           |   76 ++-
 mm/page_ext.c                          |    4 +
 21 files changed, 2392 insertions(+), 135 deletions(-)
 create mode 100644 Documentation/locking/crossrelease.txt

-- 
1.9.1

^ permalink raw reply	[flat|nested] 55+ messages in thread

end of thread, other threads:[~2017-01-19  3:18 UTC | newest]

Thread overview: 55+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-12-09  5:11 [PATCH v4 00/15] lockdep: Implement crossrelease feature Byungchul Park
2016-12-09  5:11 ` [PATCH v4 01/15] x86/dumpstack: Optimize save_stack_trace Byungchul Park
2016-12-09  5:11 ` [PATCH v4 02/15] x86/dumpstack: Add save_stack_trace()_fast() Byungchul Park
2016-12-09  5:11 ` [PATCH v4 03/15] lockdep: Refactor lookup_chain_cache() Byungchul Park
2016-12-09  5:12 ` [PATCH v4 04/15] lockdep: Add a function building a chain between two classes Byungchul Park
2017-01-10 21:00   ` Peter Zijlstra
2017-01-12  1:41     ` Byungchul Park
2016-12-09  5:12 ` [PATCH v4 05/15] lockdep: Make check_prev_add can use a separate stack_trace Byungchul Park
2017-01-12 16:16   ` Peter Zijlstra
2017-01-13  2:45     ` Byungchul Park
2017-01-13  4:09     ` [PATCH] lockdep: Make a stack_trace instance passed to check_prev_add as an arg Byungchul Park
2017-01-13  4:38       ` Byungchul Park
2017-01-13 10:11     ` [PATCH v4 05/15] lockdep: Make check_prev_add can use a separate stack_trace Byungchul Park
2017-01-13 10:17       ` [PATCH 1/2] lockdep: Refactor save_trace() Byungchul Park
2017-01-13 10:17       ` [PATCH 2/2] lockdep: Pass a callback arg to check_prev_add() to handle stack_trace Byungchul Park
2017-01-17 15:54       ` [PATCH v4 05/15] lockdep: Make check_prev_add can use a separate stack_trace Peter Zijlstra
2017-01-18  2:04         ` Byungchul Park
2017-01-18 15:10           ` Peter Zijlstra
2017-01-19  2:47             ` Byungchul Park
2016-12-09  5:12 ` [PATCH v4 06/15] lockdep: Make save_trace can skip stack tracing of the current Byungchul Park
2017-01-12 16:37   ` Peter Zijlstra
2017-01-13  0:18     ` Byungchul Park
2016-12-09  5:12 ` [PATCH v4 07/15] lockdep: Implement crossrelease feature Byungchul Park
2017-01-13  4:39   ` Lai Jiangshan
2017-01-13  5:02     ` Byungchul Park
2017-01-16 15:10   ` Peter Zijlstra
2017-01-17  2:05     ` Byungchul Park
2017-01-17  7:12       ` Peter Zijlstra
2017-01-17  7:49         ` Byungchul Park
2017-01-17  7:14       ` Peter Zijlstra
2017-01-17  7:45         ` Byungchul Park
2017-01-16 15:13   ` Peter Zijlstra
2017-01-17  2:33     ` Byungchul Park
2017-01-17  6:24       ` Boqun Feng
2017-01-17  7:43         ` Byungchul Park
2016-12-09  5:12 ` [PATCH v4 08/15] lockdep: Make crossrelease use save_stack_trace_fast() Byungchul Park
2016-12-09  5:12 ` [PATCH v4 09/15] lockdep: Make print_circular_bug() crosslock-aware Byungchul Park
2016-12-09  5:12 ` [PATCH v4 10/15] lockdep: Apply crossrelease to completion operation Byungchul Park
2016-12-09  5:12 ` [PATCH v4 11/15] pagemap.h: Remove trailing white space Byungchul Park
2016-12-09  5:12 ` [PATCH v4 12/15] lockdep: Apply crossrelease to PG_locked lock Byungchul Park
2016-12-09  5:12 ` [PATCH v4 13/15] lockdep: Apply lock_acquire(release) on __Set(__Clear)PageLocked Byungchul Park
2016-12-09  5:12 ` [PATCH v4 14/15] lockdep: Move data used in CONFIG_LOCKDEP_PAGELOCK from page to page_ext Byungchul Park
2016-12-09  5:12 ` [PATCH v4 15/15] lockdep: Crossrelease feature documentation Byungchul Park
2017-01-10 20:08   ` Peter Zijlstra
2017-01-11  1:29     ` Byungchul Park
2017-01-18  6:42   ` Boqun Feng
2017-01-18 10:53     ` Byungchul Park
2017-01-18 11:03       ` Peter Zijlstra
2017-01-18 11:54         ` Byungchul Park
2017-01-18 12:07           ` Peter Zijlstra
2017-01-18 12:14             ` byungchul.park
2017-01-18 14:12               ` Peter Zijlstra
2017-01-19  1:54                 ` Byungchul Park
2017-01-18 12:49             ` byungchul.park
2016-12-09  5:21 ` [FYI] Output of 'cat /proc/lockdep' after applying crossrelease Byungchul Park

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).