Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1430244 > unrolled thread

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

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [RFC 00/12] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2016-06-24 01:40 +0200
    Re: [RFC 00/12] lockdep: Implement crossrelease feature Peter Zijlstra <peterz@infradead.org> - 2016-06-24 09:10 +0200
      Re: [RFC 00/12] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2016-06-24 13:20 +0200
    Re: [RFC 00/12] lockdep: Implement crossrelease feature Nikolay Borisov <kernel@kyup.com> - 2016-06-24 13:30 +0200
      Re: [RFC 00/12] lockdep: Implement crossrelease feature Byungchul Park <byungchul.park@lge.com> - 2016-06-27 03:40 +0200

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

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

[toc] | [next] | [standalone]

#1430410

On Fri, Jun 24, 2016 at 08:37:13AM +0900, Byungchul Park wrote:
> 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. 

I have not had time to look at this at all..

[toc] | [prev] | [next] | [standalone]

#1430582

On Fri, Jun 24, 2016 at 09:08:44AM +0200, Peter Zijlstra wrote:
> On Fri, Jun 24, 2016 at 08:37:13AM +0900, Byungchul Park wrote:
> > 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. 
> 
> I have not had time to look at this at all..

I can wait until you become available.

Thank you for letting me know that.

[toc] | [prev] | [next] | [standalone]

#1430589

On 06/24/2016 02:37 AM, Byungchul Park wrote:
> 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

Am I correct in assuming that in ex2 PROCESS Z holds page B lock? If so
can you make it a bit more explicit if this is going to go into the
documentation, that is.

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

[toc] | [prev] | [next] | [standalone]

#1431667

On Fri, Jun 24, 2016 at 02:26:45PM +0300, Nikolay Borisov wrote:
> 
> 
> On 06/24/2016 02:37 AM, Byungchul Park wrote:
> > 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
> 
> Am I correct in assuming that in ex2 PROCESS Z holds page B lock? If so

In this example, PROCESS Z does not hold page B lock. The page B lock
being unlocked by PROCESS Z was held by PROCESS X.

> can you make it a bit more explicit if this is going to go into the
> documentation, that is.
> 
> > 
> > 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

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web