Re: [RFC 00/12] lockdep: Implement crossrelease feature
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 bu
Re: [RFC 00/12] lockdep: Implement crossrelease feature
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 Await_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 l
Re: [RFC 00/12] lockdep: Implement crossrelease feature
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.
Re: [RFC 00/12] lockdep: Implement crossrelease feature
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..
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/
