Re: [RFC 00/12] lockdep: Implement crossrelease feature

From: Byungchul Park
Date: Thu Jun 23 2016 - 19:38:55 EST


On Mon, Jun 20, 2016 at 01:55:15PM +0900, Byungchul Park wrote:

Hello,

I have a plan to resend this patchset after reinforcement of
documentation. However I am wondering what you think about the
main concept of this. A main motivation is to be able to detect
several problems which I describes with examples below.

ex.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

ex.2)

PROCESS X PROCESS Y PROCESS Z
--------- --------- ---------
lock_page B mutex_lock A

lock_page B
mutext_lock A // DEADLOCK
mutext_unlock A
unlock_page B
mutex_unlock A

ex.3)

PROCESS X PROCESS Y
--------- ---------
mutex_lock A
mutex_lock A
mutex_unlock A wait_for_complete B // DEADLOCK

complete B
mutex_unlock A

and so on...

Whatever lockdep can detect can be detected by my implementation
except AA deadlock in a context, which is of course not a deadlock
by nature, for locks releasable by difference context. Fortunately,
current kernel code is robust enough not to be detected on my machine,
I am sure this can be a good navigator to developers.

Thank you.
Byungchul

> Crossrelease feature calls a lock which is releasable by a
> different context from the context having acquired the lock,
> crosslock. For crosslock, all locks having been held in the
> context unlocking the crosslock, until eventually the crosslock
> will be unlocked, have dependency with the crosslock. That's a
> key idea to implement crossrelease feature.
>
> Crossrelease feature introduces 2 new data structures.
>
> 1. pend_lock (== plock)
>
> This is for keeping locks waiting to commit those so
> that an actual dependency chain is built, when commiting
> a crosslock.
>
> Every task_struct has an array of this pending lock to
> keep those locks. These pending locks will be added
> whenever lock_acquire() is called for normal(non-crosslock)
> lock and will be flushed(committed) at proper time.
>
> 2. cross_lock (== xlock)
>
> This keeps some additional data only for crosslock. There
> is one cross_lock per one lockdep_map for crosslock.
> lockdep_init_map_crosslock() should be used instead of
> lockdep_init_map() to use the lock as a crosslock.
>
> Acquiring and releasing sequence for crossrelease feature:
>
> 1. Acquire
>
> All validation check is performed for all locks.
>
> 1) For non-crosslock (normal lock)
>
> The hlock will be added not only to held_locks
> of the current's task_struct, but also to
> pend_lock array of the task_struct, so that
> a dependency chain can be built with the lock
> when doing commit.
>
> 2) For crosslock
>
> The hlock will be added only to the cross_lock
> of the lock's lockdep_map instead of held_locks,
> so that a dependency chain can be built with
> the lock when doing commit. And this lock is
> added to the xlocks_head list.
>
> 2. Commit (only for crosslock)
>
> This establishes a dependency chain between the lock
> unlocking it now and all locks having held in the context
> unlocking it since the lock was held, even though it tries
> to avoid building a chain unnecessarily as far as possible.
>
> 3. Release
>
> 1) For non-crosslock (normal lock)
>
> No change.
>
> 2) For crosslock
>
> Just Remove the lock from xlocks_head list. Release
> operation should be used with commit operation
> together for crosslock, in order to build a
> dependency chain properly.
>
> Byungchul Park (12):
> 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
> x86/dumpstack: Optimize save_stack_trace
>
> arch/x86/include/asm/stacktrace.h | 1 +
> arch/x86/kernel/dumpstack.c | 2 +
> arch/x86/kernel/dumpstack_32.c | 2 +
> arch/x86/kernel/stacktrace.c | 7 +
> 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 | 846 +++++++++++++++++++++++++++++++++++---
> 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 +
> 22 files changed, 1255 insertions(+), 122 deletions(-)
>
> --
> 1.9.1