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

Byungchul Park
2017-08-07T07:14:14Z

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