[PATCH v8 00/14] lockdep: Implement crossrelease feature

From	Byungchul Park <byungchul.park@lge.com>
Newsgroups	linux.kernel
Subject	[PATCH v8 00/14] lockdep: Implement crossrelease feature
Date	2017-08-07 09:20 +0200
Message-ID	<ubKut-59V-3@gated-at.bofh.it> (permalink)
Organization	linux.* mail to news gateway

Show all headers | View raw

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

Back to linux.kernel | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

[PATCH v8 00/14] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2017-08-07 09:20 +0200
  [PATCH v8 08/14] lockdep: Make print_circular_bug() aware of crossrelease Byungchul Park <byungchul.park@lge.com> - 2017-08-07 09:20 +0200
    [tip:locking/core] locking/lockdep: Make print_circular_bug() aware  of crossrelease tip-bot for Byungchul Park <tipbot@zytor.com> - 2017-08-10 14:30 +0200
  [PATCH v8 05/14] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2017-08-07 09:20 +0200
    Re: [PATCH v8 05/14] lockdep: Implement crossrelease feature Peter Zijlstra <peterz@infradead.org> - 2017-08-09 16:10 +0200
      Re: [PATCH v8 05/14] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2017-08-10 03:40 +0200
        Re: [PATCH v8 05/14] lockdep: Implement crossrelease feature Peter Zijlstra <peterz@infradead.org> - 2017-08-10 11:30 +0200
    [tip:locking/core] locking/lockdep: Implement the 'crossrelease'  feature tip-bot for Byungchul Park <tipbot@zytor.com> - 2017-08-10 14:30 +0200
  [PATCH v8 11/14] lockdep: Apply crossrelease to PG_locked locks Byungchul Park <byungchul.park@lge.com> - 2017-08-07 09:20 +0200
    Re: [PATCH v8 11/14] lockdep: Apply crossrelease to PG_locked locks Byungchul Park <byungchul.park@lge.com> - 2017-08-10 03:40 +0200
      Re: [PATCH v8 11/14] lockdep: Apply crossrelease to PG_locked locks Peter Zijlstra <peterz@infradead.org> - 2017-08-10 11:30 +0200
  [PATCH v8 10/14] pagemap.h: Remove trailing white space Byungchul Park <byungchul.park@lge.com> - 2017-08-07 09:20 +0200
  [PATCH v8 07/14] lockdep: Handle non(or multi)-acquisition of a crosslock Byungchul Park <byungchul.park@lge.com> - 2017-08-07 09:20 +0200
    [tip:locking/core] locking/lockdep: Handle non(or  multi)-acquisition of a crosslock tip-bot for Byungchul Park <tipbot@zytor.com> - 2017-08-10 14:30 +0200
  [PATCH v8 12/14] lockdep: Apply lock_acquire(release) on __Set(__Clear)PageLocked Byungchul Park <byungchul.park@lge.com> - 2017-08-07 09:20 +0200
  [PATCH v8 14/14] lockdep: Crossrelease feature documentation Byungchul Park <byungchul.park@lge.com> - 2017-08-07 09:20 +0200
    [tip:locking/core] locking/lockdep: Add 'crossrelease' feature  documentation tip-bot for Byungchul Park <tipbot@zytor.com> - 2017-08-10 14:30 +0200
  [PATCH v8 09/14] lockdep: Apply crossrelease to completions Byungchul Park <byungchul.park@lge.com> - 2017-08-07 09:20 +0200
    Re: [PATCH v8 09/14] lockdep: Apply crossrelease to completions Peter Zijlstra <peterz@infradead.org> - 2017-08-09 12:00 +0200
      Re: [PATCH v8 09/14] lockdep: Apply crossrelease to completions Peter Zijlstra <peterz@infradead.org> - 2017-08-09 12:30 +0200
        Re: [PATCH v8 09/14] lockdep: Apply crossrelease to completions Byungchul Park <byungchul.park@lge.com> - 2017-08-10 03:30 +0200
    [tip:locking/core] locking/lockdep: Apply crossrelease to  completions tip-bot for Byungchul Park <tipbot@zytor.com> - 2017-08-10 14:30 +0200
  [PATCH v8 04/14] lockdep: Make check_prev_add() able to handle external stack_trace Byungchul Park <byungchul.park@lge.com> - 2017-08-07 09:20 +0200
    [tip:locking/core] locking/lockdep: Make check_prev_add() able to  handle external stack_trace tip-bot for Byungchul Park <tipbot@zytor.com> - 2017-08-10 14:30 +0200
  Re: [PATCH v8 00/14] lockdep: Implement crossrelease feature Peter Zijlstra <peterz@infradead.org> - 2017-08-09 18:00 +0200
    Re: [PATCH v8 00/14] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2017-08-10 03:00 +0200
      Re: [PATCH v8 00/14] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2017-08-10 05:50 +0200
      Re: [PATCH v8 00/14] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2017-08-10 13:00 +0200
    Re: [PATCH v8 00/14] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2017-08-10 11:40 +0200
      Re: [PATCH v8 00/14] lockdep: Implement crossrelease feature Peter Zijlstra <peterz@infradead.org> - 2017-08-10 13:00 +0200
  Re: [PATCH v8 00/14] lockdep: Implement crossrelease feature Ingo Molnar <mingo@kernel.org> - 2017-08-10 13:20 +0200
    Re: [PATCH v8 00/14] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2017-08-10 13:50 +0200

csiph-web