All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH v8 00/14] lockdep: Implement crossrelease feature
@ 2017-08-07  7:12 ` Byungchul Park
  0 siblings, 0 replies; 152+ messages in thread
From: Byungchul Park @ 2017-08-07  7:12 UTC (permalink / raw)
  To: peterz, mingo
  Cc: tglx, walken, boqun.feng, kirill, linux-kernel, linux-mm, akpm,
	willy, npiggin, kernel-team

Change from v7
	- rebase on latest tip/sched/core (Jul 26 2017)
	- apply peterz's suggestions
	- simplify code of crossrelease_{hist/soft/hard}_{start/end}
	- exclude a patch avoiding redundant links
	- exclude a patch already applied onto the base

Change from v6
	- unwind the ring buffer instead tagging for 'work' context
	- introduce hist_id to distinguish every entry of ring buffer
	- change the point calling crossrelease_work_start()
	- handle cases the ring buffer was overwritten
	- change LOCKDEP_CROSSRELEASE config in Kconfig
	  (select PROVE_LOCKING -> depends on PROVE_LOCKING)
	- rename xhlock_used() -> xhlock_valid()
	- simplify serveral code (e.g. traversal the ring buffer)
	- add/enhance several comments and changelogs

Change from v5
	- force XHLOCKS_SIZE to be power of 2 and simplify code
	- remove nmi check
	- separate an optimization using prev_gen_id with a full changelog
	- separate non(multi)-acquisition handling with a full changelog
	- replace vmalloc with kmallock(GFP_KERNEL) for xhlocks
	- select PROVE_LOCKING when choosing CROSSRELEASE
	- clean serveral code (e.g. loose some ifdefferies)
	- enhance several comments and changelogs

Change from v4
	- rebase on vanilla v4.9 tag
	- re-name pend_lock(plock) to hist_lock(xhlock)
	- allow overwriting ring buffer for hist_lock
	- unwind ring buffer instead of tagging id for each irq
	- introduce lockdep_map_cross embedding cross_lock
	- make each work of workqueue distinguishable
	- enhance comments
	(I will update the document at the next spin.)

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
			wait_for_complete B // DEADLOCK
	mutex_unlock A
	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 (14):
  lockdep: Refactor lookup_chain_cache()
  lockdep: Add a function building a chain between two classes
  lockdep: Change the meaning of check_prev_add()'s return value
  lockdep: Make check_prev_add() able to handle external stack_trace
  lockdep: Implement crossrelease feature
  lockdep: Detect and handle hist_lock ring buffer overwrite
  lockdep: Handle non(or multi)-acquisition of a crosslock
  lockdep: Make print_circular_bug() aware of crossrelease
  lockdep: Apply crossrelease to completions
  pagemap.h: Remove trailing white space
  lockdep: Apply crossrelease to PG_locked locks
  lockdep: Apply lock_acquire(release) on __Set(__Clear)PageLocked
  lockdep: Move data of CONFIG_LOCKDEP_PAGELOCK from page to page_ext
  lockdep: Crossrelease feature documentation

 Documentation/locking/crossrelease.txt | 874 +++++++++++++++++++++++++++++++++
 include/linux/completion.h             | 118 ++++-
 include/linux/irqflags.h               |  24 +-
 include/linux/lockdep.h                | 150 +++++-
 include/linux/mm_types.h               |   4 +
 include/linux/page-flags.h             |  43 +-
 include/linux/page_ext.h               |   4 +
 include/linux/pagemap.h                | 125 ++++-
 include/linux/sched.h                  |  11 +
 kernel/exit.c                          |   1 +
 kernel/fork.c                          |   4 +
 kernel/locking/lockdep.c               | 862 ++++++++++++++++++++++++++++----
 kernel/sched/completion.c              |  56 ++-
 kernel/workqueue.c                     |   2 +
 lib/Kconfig.debug                      |  29 ++
 mm/filemap.c                           |  73 ++-
 mm/page_ext.c                          |   4 +
 17 files changed, 2233 insertions(+), 151 deletions(-)
 create mode 100644 Documentation/locking/crossrelease.txt

-- 
1.9.1

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

end of thread, other threads:[~2017-09-05  1:04 UTC | newest]

Thread overview: 152+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-08-07  7:12 [PATCH v8 00/14] lockdep: Implement crossrelease feature Byungchul Park
2017-08-07  7:12 ` Byungchul Park
2017-08-07  7:12 ` [PATCH v8 01/14] lockdep: Refactor lookup_chain_cache() Byungchul Park
2017-08-07  7:12   ` Byungchul Park
2017-08-10 12:18   ` [tip:locking/core] locking/lockdep: " tip-bot for Byungchul Park
2017-08-07  7:12 ` [PATCH v8 02/14] lockdep: Add a function building a chain between two classes Byungchul Park
2017-08-07  7:12   ` Byungchul Park
2017-08-10 12:18   ` [tip:locking/core] locking/lockdep: " tip-bot for Byungchul Park
2017-08-07  7:12 ` [PATCH v8 03/14] lockdep: Change the meaning of check_prev_add()'s return value Byungchul Park
2017-08-07  7:12   ` Byungchul Park
2017-08-10 12:19   ` [tip:locking/core] locking/lockdep: " tip-bot for Byungchul Park
2017-08-07  7:12 ` [PATCH v8 04/14] lockdep: Make check_prev_add() able to handle external stack_trace Byungchul Park
2017-08-07  7:12   ` Byungchul Park
2017-08-10 12:19   ` [tip:locking/core] locking/lockdep: " tip-bot for Byungchul Park
2017-08-07  7:12 ` [PATCH v8 05/14] lockdep: Implement crossrelease feature Byungchul Park
2017-08-07  7:12   ` Byungchul Park
2017-08-09 14:05   ` Peter Zijlstra
2017-08-09 14:05     ` Peter Zijlstra
2017-08-10  1:30     ` Byungchul Park
2017-08-10  1:30       ` Byungchul Park
2017-08-10  9:21       ` Peter Zijlstra
2017-08-10  9:21         ` Peter Zijlstra
2017-08-10 12:19   ` [tip:locking/core] locking/lockdep: Implement the 'crossrelease' feature tip-bot for Byungchul Park
2017-08-07  7:12 ` [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite Byungchul Park
2017-08-07  7:12   ` Byungchul Park
2017-08-09 14:16   ` Peter Zijlstra
2017-08-09 14:16     ` Peter Zijlstra
2017-08-10  1:32     ` Byungchul Park
2017-08-10  1:32       ` Byungchul Park
2017-08-10  9:22       ` Peter Zijlstra
2017-08-10  9:22         ` Peter Zijlstra
2017-08-10 10:32     ` Byungchul Park
2017-08-10 10:32       ` Byungchul Park
2017-08-10 11:59   ` Boqun Feng
2017-08-10 12:11     ` Byungchul Park
2017-08-10 12:11       ` Byungchul Park
2017-08-10 12:51       ` Boqun Feng
2017-08-10 13:17         ` Boqun Feng
2017-08-10 13:17           ` Boqun Feng
2017-08-11  0:44           ` Byungchul Park
2017-08-11  0:44             ` Byungchul Park
2017-08-11  3:43           ` Byungchul Park
2017-08-11  3:43             ` Byungchul Park
2017-08-11  8:03             ` Boqun Feng
2017-08-11  8:52               ` Byungchul Park
2017-08-11  8:52                 ` Byungchul Park
2017-08-11  9:44                 ` Byungchul Park
2017-08-11  9:44                   ` Byungchul Park
2017-08-11 13:06                   ` Byungchul Park
2017-08-11 13:06                     ` Byungchul Park
2017-08-14  7:05                     ` Boqun Feng
2017-08-14  7:22                       ` Byungchul Park
2017-08-14  7:22                         ` Byungchul Park
2017-08-14  7:29                       ` Byungchul Park
2017-08-14  7:29                         ` Byungchul Park
2017-08-11  0:40         ` Byungchul Park
2017-08-11  0:40           ` Byungchul Park
2017-08-11  1:03           ` Boqun Feng
2017-08-10 12:20   ` [tip:locking/core] locking/lockdep: " tip-bot for Byungchul Park
2017-08-07  7:12 ` [PATCH v8 07/14] lockdep: Handle non(or multi)-acquisition of a crosslock Byungchul Park
2017-08-07  7:12   ` Byungchul Park
2017-08-10 12:20   ` [tip:locking/core] locking/lockdep: " tip-bot for Byungchul Park
2017-08-07  7:12 ` [PATCH v8 08/14] lockdep: Make print_circular_bug() aware of crossrelease Byungchul Park
2017-08-07  7:12   ` Byungchul Park
2017-08-10 12:21   ` [tip:locking/core] locking/lockdep: " tip-bot for Byungchul Park
2017-08-07  7:12 ` [PATCH v8 09/14] lockdep: Apply crossrelease to completions Byungchul Park
2017-08-07  7:12   ` Byungchul Park
2017-08-07 10:20   ` kbuild test robot
2017-08-07 11:45   ` kbuild test robot
2017-08-09  9:51   ` Peter Zijlstra
2017-08-09  9:51     ` Peter Zijlstra
2017-08-09 10:24     ` Peter Zijlstra
2017-08-09 10:24       ` Peter Zijlstra
2017-08-10  1:24       ` Byungchul Park
2017-08-10  1:24         ` Byungchul Park
2017-08-10 12:21   ` [tip:locking/core] locking/lockdep: " tip-bot for Byungchul Park
2017-08-14  8:50   ` [PATCH v8 09/14] lockdep: " Arnd Bergmann
2017-08-14  8:50     ` Arnd Bergmann
2017-08-18 23:43     ` Boqun Feng
2017-08-18 23:43       ` Boqun Feng
2017-08-19 12:51       ` Arnd Bergmann
2017-08-19 12:51         ` Arnd Bergmann
2017-08-19 13:34         ` Arnd Bergmann
2017-08-19 13:34           ` Arnd Bergmann
2017-08-23 14:43           ` Boqun Feng
2017-08-20  3:18         ` Boqun Feng
2017-08-07  7:12 ` [PATCH v8 10/14] pagemap.h: Remove trailing white space Byungchul Park
2017-08-07  7:12   ` Byungchul Park
2017-08-07  7:12 ` [PATCH v8 11/14] lockdep: Apply crossrelease to PG_locked locks Byungchul Park
2017-08-07  7:12   ` Byungchul Park
2017-08-07 10:36   ` kbuild test robot
2017-08-10  1:35   ` Byungchul Park
2017-08-10  1:35     ` Byungchul Park
2017-08-10  9:25     ` Peter Zijlstra
2017-08-10  9:25       ` Peter Zijlstra
2017-09-05  1:03   ` Byungchul Park
2017-09-05  1:03     ` Byungchul Park
2017-08-07  7:12 ` [PATCH v8 12/14] lockdep: Apply lock_acquire(release) on __Set(__Clear)PageLocked Byungchul Park
2017-08-07  7:12   ` Byungchul Park
2017-08-07  7:13 ` [PATCH v8 13/14] lockdep: Move data of CONFIG_LOCKDEP_PAGELOCK from page to page_ext Byungchul Park
2017-08-07  7:13   ` Byungchul Park
2017-08-07 10:43   ` kbuild test robot
2017-08-07  7:13 ` [PATCH v8 14/14] lockdep: Crossrelease feature documentation Byungchul Park
2017-08-07  7:13   ` Byungchul Park
2017-08-07 15:58   ` kbuild test robot
2017-08-10 12:22   ` [tip:locking/core] locking/lockdep: Add 'crossrelease' " tip-bot for Byungchul Park
2017-08-09 15:50 ` [PATCH v8 00/14] lockdep: Implement crossrelease feature Peter Zijlstra
2017-08-09 15:50   ` Peter Zijlstra
2017-08-10  0:55   ` Byungchul Park
2017-08-10  0:55     ` Byungchul Park
2017-08-10  3:47     ` Byungchul Park
2017-08-10  3:47       ` Byungchul Park
2017-08-10 10:52     ` Byungchul Park
2017-08-10 10:52       ` Byungchul Park
2017-08-10  9:37   ` Byungchul Park
2017-08-10  9:37     ` Byungchul Park
2017-08-10 10:52     ` Peter Zijlstra
2017-08-10 10:52       ` Peter Zijlstra
2017-08-10 11:10 ` Ingo Molnar
2017-08-10 11:10   ` Ingo Molnar
2017-08-10 11:45   ` Byungchul Park
2017-08-10 11:45     ` Byungchul Park
2017-08-14 10:57     ` Ingo Molnar
2017-08-14 10:57       ` Ingo Molnar
2017-08-14 11:10       ` Byungchul Park
2017-08-14 11:10         ` Byungchul Park
2017-08-15  8:20 ` Ingo Molnar
2017-08-15  8:20   ` Ingo Molnar
2017-08-16  0:16   ` Byungchul Park
2017-08-16  0:16     ` Byungchul Park
2017-08-16  4:05     ` Boqun Feng
2017-08-16  4:05       ` Boqun Feng
2017-08-16  4:37       ` Byungchul Park
2017-08-16  4:37         ` Byungchul Park
2017-08-16  5:40         ` Boqun Feng
2017-08-16  6:37           ` Byungchul Park
2017-08-16  6:37             ` Byungchul Park
2017-08-16  5:05       ` Byungchul Park
2017-08-16  5:05         ` Byungchul Park
2017-08-16  5:58         ` Boqun Feng
2017-08-16  7:14           ` Byungchul Park
2017-08-16  7:14             ` Byungchul Park
2017-08-16  8:06             ` Byungchul Park
2017-08-16  8:06               ` Byungchul Park
2017-08-16  9:38               ` Byungchul Park
2017-08-16  9:38                 ` Byungchul Park
2017-08-17  7:48       ` Ingo Molnar
2017-08-17  7:48         ` Ingo Molnar
2017-08-17  8:04         ` Boqun Feng
2017-08-17  8:12           ` Ingo Molnar
2017-08-17  8:12             ` Ingo Molnar
2017-08-17  8:33             ` Boqun Feng

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.