[PATCH v5 2/7] mutex: add support for wound/wait style locks, v5
Changes since RFC patch v1: - Updated to use atomic_long instead of atomic, since the reservation_id was a long. - added mutex_reserve_lock_slow and mutex_reserve_lock_intr_slow - removed mutex_locked_set_reservation_id (or w/e it was called) Changes since RFC patch v2: - remove use of __mutex_lock_retval_arg, add warnings when using wrong combination of mutex_(,reserve_)lock/unlock. Changes since v1: - Add __always_inline to __mutex_lock_common, otherwise reservation paths can be triggered from normal locks, because __builtin_constant_p might evaluate to false for the constant 0 in that case. Tests for this have been added in the next patch. - Updated documentation slightly. Changes since v2: - Renamed everything to ww_mutex. (mlankhorst) - Added ww_acquire_ctx and ww_class. (mlankhorst) - Added a lot of checks for wrong api usage. (mlankhorst) - Documentation updates. (danvet) Changes since v3: - Small documentation fixes (robclark) - Memory barrier fix (danvet) Changes since v4: - Remove ww_mutex_unlock_single and ww_mutex_lock_single. - Rename ww_mutex_trylock_single to ww_mutex_trylock. - Remove separate implementations of ww_mutex_lock_slow*, normal functions can be used. Inline versions still exist for extra debugging. - Cleanup unneeded memory barriers, add comment to the remaining smp_mb(). Signed-off-by: Maarten Lankhorst maarten.lankho...@canonical.com Signed-off-by: Daniel Vetter daniel.vet...@ffwll.ch Signed-off-by: Rob Clark robdcl...@gmail.com --- Documentation/ww-mutex-design.txt | 343 include/linux/mutex-debug.h |1 include/linux/mutex.h | 355 + kernel/mutex.c| 318 +++-- lib/debug_locks.c |2 5 files changed, 1002 insertions(+), 17 deletions(-) create mode 100644 Documentation/ww-mutex-design.txt diff --git a/Documentation/ww-mutex-design.txt b/Documentation/ww-mutex-design.txt new file mode 100644 index 000..379739c --- /dev/null +++ b/Documentation/ww-mutex-design.txt @@ -0,0 +1,343 @@ +Wait/Wound Deadlock-Proof Mutex Design +== + +Please read mutex-design.txt first, as it applies to wait/wound mutexes too. + +Motivation for WW-Mutexes +- + +GPU's do operations that commonly involve many buffers. Those buffers +can be shared across contexts/processes, exist in different memory +domains (for example VRAM vs system memory), and so on. And with +PRIME / dmabuf, they can even be shared across devices. So there are +a handful of situations where the driver needs to wait for buffers to +become ready. If you think about this in terms of waiting on a buffer +mutex for it to become available, this presents a problem because +there is no way to guarantee that buffers appear in a execbuf/batch in +the same order in all contexts. That is directly under control of +userspace, and a result of the sequence of GL calls that an application +makes. Which results in the potential for deadlock. The problem gets +more complex when you consider that the kernel may need to migrate the +buffer(s) into VRAM before the GPU operates on the buffer(s), which +may in turn require evicting some other buffers (and you don't want to +evict other buffers which are already queued up to the GPU), but for a +simplified understanding of the problem you can ignore this. + +The algorithm that TTM came up with for dealing with this problem is quite +simple. For each group of buffers (execbuf) that need to be locked, the caller +would be assigned a unique reservation id/ticket, from a global counter. In +case of deadlock while locking all the buffers associated with a execbuf, the +one with the lowest reservation ticket (i.e. the oldest task) wins, and the one +with the higher reservation id (i.e. the younger task) unlocks all of the +buffers that it has already locked, and then tries again. + +In the RDBMS literature this deadlock handling approach is called wait/wound: +The older tasks waits until it can acquire the contended lock. The younger tasks +needs to back off and drop all the locks it is currently holding, i.e. the +younger task is wounded. + +Concepts + + +Compared to normal mutexes two additional concepts/objects show up in the lock +interface for w/w mutexes: + +Acquire context: To ensure eventual forward progress it is important the a task +trying to acquire locks doesn't grab a new reservation id, but keeps the one it +acquired when starting the lock acquisition. This ticket is stored in the +acquire context. Furthermore the acquire context keeps track of debugging state +to catch w/w mutex interface abuse. + +W/w class: In contrast to normal mutexes the lock class needs to be explicit for +w/w mutexes, since it is required to initialize the acquire context. + +Furthermore there are three different class of w/w lock
Re: [PATCH v5 2/7] mutex: add support for wound/wait style locks, v5
* Maarten Lankhorst maarten.lankho...@canonical.com wrote: Changes since RFC patch v1: - Updated to use atomic_long instead of atomic, since the reservation_id was a long. - added mutex_reserve_lock_slow and mutex_reserve_lock_intr_slow - removed mutex_locked_set_reservation_id (or w/e it was called) Changes since RFC patch v2: - remove use of __mutex_lock_retval_arg, add warnings when using wrong combination of mutex_(,reserve_)lock/unlock. Changes since v1: - Add __always_inline to __mutex_lock_common, otherwise reservation paths can be triggered from normal locks, because __builtin_constant_p might evaluate to false for the constant 0 in that case. Tests for this have been added in the next patch. - Updated documentation slightly. Changes since v2: - Renamed everything to ww_mutex. (mlankhorst) - Added ww_acquire_ctx and ww_class. (mlankhorst) - Added a lot of checks for wrong api usage. (mlankhorst) - Documentation updates. (danvet) Changes since v3: - Small documentation fixes (robclark) - Memory barrier fix (danvet) Changes since v4: - Remove ww_mutex_unlock_single and ww_mutex_lock_single. - Rename ww_mutex_trylock_single to ww_mutex_trylock. - Remove separate implementations of ww_mutex_lock_slow*, normal functions can be used. Inline versions still exist for extra debugging. - Cleanup unneeded memory barriers, add comment to the remaining smp_mb(). That's not a proper changelog. It should be a short description of what it does, possibly referring to the new Documentation/ww-mutex-design.txt file for more details. Signed-off-by: Maarten Lankhorst maarten.lankho...@canonical.com Signed-off-by: Daniel Vetter daniel.vet...@ffwll.ch Signed-off-by: Rob Clark robdcl...@gmail.com That's not a valid signoff chain: the last signoff in the chain is the person sending me the patch. The first signoff is the person who wrote the patch. The other two gents should be Acked-by I suspect? Thanks, Ingo -- To unsubscribe from this list: send the line unsubscribe linux-media in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 2/7] mutex: add support for wound/wait style locks, v5
* Maarten Lankhorst maarten.lankho...@canonical.com wrote: +The algorithm that TTM came up with for dealing with this problem is quite +simple. [...] 'TTM' here reads like a person - but in reality it's the TTM graphics subsystem, right? Please clarify this portion of the text. Thanks, Ingo -- To unsubscribe from this list: send the line unsubscribe linux-media in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 2/7] mutex: add support for wound/wait style locks, v5
Op 20-06-13 13:55, Ingo Molnar schreef: * Maarten Lankhorst maarten.lankho...@canonical.com wrote: Changes since RFC patch v1: - Updated to use atomic_long instead of atomic, since the reservation_id was a long. - added mutex_reserve_lock_slow and mutex_reserve_lock_intr_slow - removed mutex_locked_set_reservation_id (or w/e it was called) Changes since RFC patch v2: - remove use of __mutex_lock_retval_arg, add warnings when using wrong combination of mutex_(,reserve_)lock/unlock. Changes since v1: - Add __always_inline to __mutex_lock_common, otherwise reservation paths can be triggered from normal locks, because __builtin_constant_p might evaluate to false for the constant 0 in that case. Tests for this have been added in the next patch. - Updated documentation slightly. Changes since v2: - Renamed everything to ww_mutex. (mlankhorst) - Added ww_acquire_ctx and ww_class. (mlankhorst) - Added a lot of checks for wrong api usage. (mlankhorst) - Documentation updates. (danvet) Changes since v3: - Small documentation fixes (robclark) - Memory barrier fix (danvet) Changes since v4: - Remove ww_mutex_unlock_single and ww_mutex_lock_single. - Rename ww_mutex_trylock_single to ww_mutex_trylock. - Remove separate implementations of ww_mutex_lock_slow*, normal functions can be used. Inline versions still exist for extra debugging. - Cleanup unneeded memory barriers, add comment to the remaining smp_mb(). That's not a proper changelog. It should be a short description of what it does, possibly referring to the new Documentation/ww-mutex-design.txt file for more details. Well they've helped me with some of the changes and contributed some code and/or fixes, but if acked-by is preferred I'll use that.. Signed-off-by: Maarten Lankhorst maarten.lankho...@canonical.com Signed-off-by: Daniel Vetter daniel.vet...@ffwll.ch Signed-off-by: Rob Clark robdcl...@gmail.com That's not a valid signoff chain: the last signoff in the chain is the person sending me the patch. The first signoff is the person who wrote the patch. The other two gents should be Acked-by I suspect? I guess so. -- To unsubscribe from this list: send the line unsubscribe linux-media in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v5 2/7] mutex: add support for wound/wait style locks, v5
* Maarten Lankhorst maarten.lankho...@canonical.com wrote: Well they've helped me with some of the changes and contributed some code and/or fixes, but if acked-by is preferred I'll use that.. Such contributions can be credited in the changelog, and/or copyright notices, and/or the code itself. The signoff chain on the other hand is strictly defined as a 'route the patch took', with a single point of origin, the main author. See Documentation/SubmittingPatches, pt 12. [ A signoff chain _can_ signal multi-authored code where the code got written by someone and then further fixed/developed by someone else - who adds a SOB to the end - but in that case I expect to get the patch from the last person in the signoff chain. ] Thanks, Ingo -- To unsubscribe from this list: send the line unsubscribe linux-media in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
