Re: [PATCH v3 2/3] mutex: add support for wound/wait style locks, v3
On Wed, May 22, 2013 at 07:24:38PM +0200, Maarten Lankhorst wrote: +- Functions to only acquire a single w/w mutex, which results in the exact same + semantics as a normal mutex. These functions have the _single postfix. This is missing rationale. trylock_single is useful when iterating over a list, and you want to evict a bo, but only the first one that can be acquired. lock_single is useful when only a single bo needs to be acquired, for example to lock a buffer during mmap. OK, so given that its still early, monday and I haven't actually spend much time thinking on this; would it be possible to make: ww_mutex_lock(.ctx=NULL) act like ww_mutex_lock_single()? The idea is that if we don't provide a ctx, we'll get a different lockdep annotation; mutex_lock() vs mutex_lock_nest_lock(). So if we then go and make a mistake, lockdep should warn us. Would that work or should I stock up on morning juice? -- 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 v3 2/3] mutex: add support for wound/wait style locks, v3
Op 27-05-13 10:00, Peter Zijlstra schreef: On Wed, May 22, 2013 at 07:24:38PM +0200, Maarten Lankhorst wrote: +- Functions to only acquire a single w/w mutex, which results in the exact same + semantics as a normal mutex. These functions have the _single postfix. This is missing rationale. trylock_single is useful when iterating over a list, and you want to evict a bo, but only the first one that can be acquired. lock_single is useful when only a single bo needs to be acquired, for example to lock a buffer during mmap. OK, so given that its still early, monday and I haven't actually spend much time thinking on this; would it be possible to make: ww_mutex_lock(.ctx=NULL) act like ww_mutex_lock_single()? The idea is that if we don't provide a ctx, we'll get a different lockdep annotation; mutex_lock() vs mutex_lock_nest_lock(). So if we then go and make a mistake, lockdep should warn us. Would that work or should I stock up on morning juice? It's easy to merge unlock_single and unlock, which I did in the next version I'll post. Lockdep will already warn if ww_mutex_lock and ww_mutex_lock_single are both used. ww_test_block_context and ww_test_context_block in lib/locking-selftest.c are the testcases for this. The locking paths are too different, it will end up with doing if (ctx == NULL) mutex_lock(); else ww_mutex_lock(); ~Maarten -- 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 v3 2/3] mutex: add support for wound/wait style locks, v3
On Wed, May 22, 2013 at 06:49:04PM +0200, Daniel Vetter wrote: - _slow functions can check whether all acquire locks have been released and whether the caller is indeed blocking on the contending lock. Not doing so could either result in needless spinning instead of blocking (when blocking on the wrong lock) or in deadlocks (when not dropping all acquired). We could add ww_mutex_assert_context_empty() or somesuch so that paranoid people have a means of expressing themselves :-) -- 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 v3 2/3] mutex: add support for wound/wait style locks, v3
On Mon, May 27, 2013 at 10:26:39AM +0200, Maarten Lankhorst wrote:
Op 27-05-13 10:00, Peter Zijlstra schreef:
On Wed, May 22, 2013 at 07:24:38PM +0200, Maarten Lankhorst wrote:
+- Functions to only acquire a single w/w mutex, which results in the
exact same
+ semantics as a normal mutex. These functions have the _single postfix.
This is missing rationale.
trylock_single is useful when iterating over a list, and you want to evict
a bo, but only the first one that can be acquired.
lock_single is useful when only a single bo needs to be acquired, for
example to lock a buffer during mmap.
OK, so given that its still early, monday and I haven't actually spend
much time thinking on this; would it be possible to make:
ww_mutex_lock(.ctx=NULL) act like ww_mutex_lock_single()?
The idea is that if we don't provide a ctx, we'll get a different
lockdep annotation; mutex_lock() vs mutex_lock_nest_lock(). So if we
then go and make a mistake, lockdep should warn us.
Would that work or should I stock up on morning juice?
It's easy to merge unlock_single and unlock, which I did in the next version
I'll post.
Lockdep will already warn if ww_mutex_lock and ww_mutex_lock_single are both
used. ww_test_block_context and ww_test_context_block in
lib/locking-selftest.c
are the testcases for this.
The locking paths are too different, it will end up with doing if (ctx ==
NULL) mutex_lock(); else ww_mutex_lock();
I was more thinking like:
int __sched ww_mutex_lock(struct ww_mutex *lock, struct ww_acquire_ctx *ctx)
{
might_sleep();
return __mutex_lock_common(lock-base, TASK_UNINTERRUPTIBLE, 0,
ctx ? ctx-dep_map : NULL, _RET_IP_,
ctx, 0);
}
That should make ww_mutex_lock(.ctx=NULL) equivalent to
mutex_lock(lock-base), no?
Anyway, implementation aside, it would again reduce the interface some.
--
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 v3 2/3] mutex: add support for wound/wait style locks, v3
Op 27-05-13 11:13, Peter Zijlstra schreef:
On Mon, May 27, 2013 at 10:26:39AM +0200, Maarten Lankhorst wrote:
Op 27-05-13 10:00, Peter Zijlstra schreef:
On Wed, May 22, 2013 at 07:24:38PM +0200, Maarten Lankhorst wrote:
+- Functions to only acquire a single w/w mutex, which results in the
exact same
+ semantics as a normal mutex. These functions have the _single postfix.
This is missing rationale.
trylock_single is useful when iterating over a list, and you want to evict
a bo, but only the first one that can be acquired.
lock_single is useful when only a single bo needs to be acquired, for
example to lock a buffer during mmap.
OK, so given that its still early, monday and I haven't actually spend
much time thinking on this; would it be possible to make:
ww_mutex_lock(.ctx=NULL) act like ww_mutex_lock_single()?
The idea is that if we don't provide a ctx, we'll get a different
lockdep annotation; mutex_lock() vs mutex_lock_nest_lock(). So if we
then go and make a mistake, lockdep should warn us.
Would that work or should I stock up on morning juice?
It's easy to merge unlock_single and unlock, which I did in the next version
I'll post.
Lockdep will already warn if ww_mutex_lock and ww_mutex_lock_single are both
used. ww_test_block_context and ww_test_context_block in
lib/locking-selftest.c
are the testcases for this.
The locking paths are too different, it will end up with doing if (ctx ==
NULL) mutex_lock(); else ww_mutex_lock();
I was more thinking like:
int __sched ww_mutex_lock(struct ww_mutex *lock, struct ww_acquire_ctx *ctx)
{
might_sleep();
return __mutex_lock_common(lock-base, TASK_UNINTERRUPTIBLE, 0,
ctx ? ctx-dep_map : NULL, _RET_IP_,
ctx, 0);
}
That should make ww_mutex_lock(.ctx=NULL) equivalent to
mutex_lock(lock-base), no?
Anyway, implementation aside, it would again reduce the interface some.
It doesn't work like that. __builtin_constant_p(ctx == NULL) will evaluate to
false in __mutex_lock_common, even if you call ww_mutex_lock(lock, NULL);
gcc cannot prove at compile time whether ctx == NULL is true or false for the
__mutex_lock_common inlining here, so __builtin_constant_p() will return false.
And again, that's just saying
ww_mutex_lock() {
if (ctx)
original ww_mutex_lock's slowpath(lock, ctx);
else
mutex_lock's slowpath(lock-base);
}
And the next version will already remove unlock_single, and this is the
implementation for lock_single currently:
static inline void ww_mutex_lock_single(struct ww_mutex *lock)
{
mutex_lock(lock-base);
}
So why do you want to merge it?
~Maarten
--
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 v3 2/3] mutex: add support for wound/wait style locks, v3
Op 27-05-13 10:21, Peter Zijlstra schreef:
On Wed, May 22, 2013 at 07:24:38PM +0200, Maarten Lankhorst wrote:
+static inline void ww_acquire_init(struct ww_acquire_ctx *ctx,
+ struct ww_class *ww_class)
+{
+ ctx-task = current;
+ do {
+ ctx-stamp = atomic_long_inc_return(ww_class-stamp);
+ } while (unlikely(!ctx-stamp));
I suppose we'll figure something out when this becomes a bottleneck. Ideally
we'd do something like:
ctx-stamp = local_clock();
but for now we cannot guarantee that's not jiffies, and I suppose that's a
tad
too coarse to work for this.
This might mess up when 2 cores happen to return exactly the same time, how
do you choose a winner in that case?
EDIT: Using pointer address like you suggested below is fine with me. ctx
pointer would be static enough.
Right, but for now I suppose the 'global' atomic is ok, if/when we find
it hurts performance we can revisit. I was just spewing ideas :-)
If accurate timers are available it wouldn't be a bad idea. I fixed up the
code to at least support this case should it happen.
For now the source of the stamp is still a single atomic_long.
Also, why is 0 special?
Oops, 0 is no longer special.
I used to set the samp directly on the lock, so 0 used to mean no ctx set.
Ah, ok :-)
+static inline int __must_check ww_mutex_trylock_single(struct ww_mutex
*lock)
+{
+ return mutex_trylock(lock-base);
+}
trylocks can never deadlock they don't block per definition, I don't see the
point of the _single() thing here.
I called it single because they weren't annotated into any ctx. I can drop
the _single suffix though,
but you'd still need to unlock with unlock_single, or we need to remove that
distinction altogether,
lose a few lockdep checks and only have a one unlock function.
Again, early.. monday.. would a trylock, even if successful still need
the ctx?
No ctx for trylock is supported. You can still do a trylock while holding a
context, but the mutex won't be
a part of the context. Normal lockdep rules apply. lib/locking-selftest.c:
context + ww_mutex_lock first, then a trylock:
dotest(ww_test_context_try, SUCCESS, LOCKTYPE_WW);
trylock first, then context + ww_mutex_lock:
dotest(ww_test_try_context, FAILURE, LOCKTYPE_WW);
For now I don't want to add support for a trylock with context, I'm very glad I
managed to fix ttm locking
to not require this any more, and it was needed there only because it was a
workaround for the locking
being wrong. There was no annotation for the buffer locking it was using, so
the real problem wasn't easy to spot.
~Maarten
--
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 v3 2/3] mutex: add support for wound/wait style locks, v3
On Mon, May 27, 2013 at 12:01:50PM +0200, Maarten Lankhorst wrote: Again, early.. monday.. would a trylock, even if successful still need the ctx? No ctx for trylock is supported. You can still do a trylock while holding a context, but the mutex won't be a part of the context. Normal lockdep rules apply. lib/locking-selftest.c: context + ww_mutex_lock first, then a trylock: dotest(ww_test_context_try, SUCCESS, LOCKTYPE_WW); trylock first, then context + ww_mutex_lock: dotest(ww_test_try_context, FAILURE, LOCKTYPE_WW); For now I don't want to add support for a trylock with context, I'm very glad I managed to fix ttm locking to not require this any more, and it was needed there only because it was a workaround for the locking being wrong. There was no annotation for the buffer locking it was using, so the real problem wasn't easy to spot. Ah, ok. My question really was whether there even was sense for a trylock with context. I couldn't come up with a case for it; but I think I see one now. The thing is; if there could exist something like: ww_mutex_trylock(struct ww_mutex *, struct ww_acquire_ctx *ctx); Then we should not now take away that name and make it mean something else; namely: ww_mutex_trylock_single(). Unless we want to allow .ctx=NULL to mean _single. As to why I proposed that (.ctx=NULL meaning _single); I suppose because I'm a minimalist at heart. -- 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 v3 2/3] mutex: add support for wound/wait style locks, v3
Op 27-05-13 12:24, Peter Zijlstra schreef: On Mon, May 27, 2013 at 12:01:50PM +0200, Maarten Lankhorst wrote: Again, early.. monday.. would a trylock, even if successful still need the ctx? No ctx for trylock is supported. You can still do a trylock while holding a context, but the mutex won't be a part of the context. Normal lockdep rules apply. lib/locking-selftest.c: context + ww_mutex_lock first, then a trylock: dotest(ww_test_context_try, SUCCESS, LOCKTYPE_WW); trylock first, then context + ww_mutex_lock: dotest(ww_test_try_context, FAILURE, LOCKTYPE_WW); For now I don't want to add support for a trylock with context, I'm very glad I managed to fix ttm locking to not require this any more, and it was needed there only because it was a workaround for the locking being wrong. There was no annotation for the buffer locking it was using, so the real problem wasn't easy to spot. Ah, ok. My question really was whether there even was sense for a trylock with context. I couldn't come up with a case for it; but I think I see one now. The reason ttm needed it was because there was another lock that interacted with the ctx lock in a weird way. The ww lock it was using was inverted with another lock, so it had to grab that lock first, perform a trylock on the ww lock, and if that failed unlock the lock, wait for it to be unlocked, then retry the same thing again. I'm so glad I managed to fix that mess, if you really need ww_mutex_trylock with a ctx, it's an indication your locking is wrong. For ww_mutex_trylock with a context to be of any use you would also need to return 0 or a -errno, (-EDEADLK, -EBUSY (already locked by someone else), or -EALREADY). This would make the trylock very different from other trylocks, and very confusing because if (ww_mutex_trylock(lock, ctx)) would not do what you would think it would do. The thing is; if there could exist something like: ww_mutex_trylock(struct ww_mutex *, struct ww_acquire_ctx *ctx); Then we should not now take away that name and make it mean something else; namely: ww_mutex_trylock_single(). Unless we want to allow .ctx=NULL to mean _single. As to why I proposed that (.ctx=NULL meaning _single); I suppose because I'm a minimalist at heart. Minimalism isn't bad, it's just knowing when to sto -- 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 v3 2/3] mutex: add support for wound/wait style locks, v3
On Mon, May 27, 2013 at 12:52:00PM +0200, Maarten Lankhorst wrote: The reason ttm needed it was because there was another lock that interacted with the ctx lock in a weird way. The ww lock it was using was inverted with another lock, so it had to grab that lock first, perform a trylock on the ww lock, and if that failed unlock the lock, wait for it to be unlocked, then retry the same thing again. I'm so glad I managed to fix that mess, if you really need ww_mutex_trylock with a ctx, it's an indication your locking is wrong. For ww_mutex_trylock with a context to be of any use you would also need to return 0 or a -errno, (-EDEADLK, -EBUSY (already locked by someone else), or -EALREADY). This would make the trylock very different from other trylocks, and very confusing because if (ww_mutex_trylock(lock, ctx)) would not do what you would think it would do. Yuck ;-) Anyway, what I was thinking of is something like: T0 T1 try A lock B lock B lock A Now, if for some reason T1 won the lottery such that T0 would have to be wounded, T0's context would indicate its the first entry and not return -EDEADLK. OTOH, anybody doing creative things like that might well deserve whatever they get ;-) The thing is; if there could exist something like: ww_mutex_trylock(struct ww_mutex *, struct ww_acquire_ctx *ctx); Then we should not now take away that name and make it mean something else; namely: ww_mutex_trylock_single(). Unless we want to allow .ctx=NULL to mean _single. As to why I proposed that (.ctx=NULL meaning _single); I suppose because I'm a minimalist at heart. Minimalism isn't bad, it's just knowing when to sto :-) -- 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 v3 2/3] mutex: add support for wound/wait style locks, v3
Op 27-05-13 13:15, Peter Zijlstra schreef: On Mon, May 27, 2013 at 12:52:00PM +0200, Maarten Lankhorst wrote: The reason ttm needed it was because there was another lock that interacted with the ctx lock in a weird way. The ww lock it was using was inverted with another lock, so it had to grab that lock first, perform a trylock on the ww lock, and if that failed unlock the lock, wait for it to be unlocked, then retry the same thing again. I'm so glad I managed to fix that mess, if you really need ww_mutex_trylock with a ctx, it's an indication your locking is wrong. For ww_mutex_trylock with a context to be of any use you would also need to return 0 or a -errno, (-EDEADLK, -EBUSY (already locked by someone else), or -EALREADY). This would make the trylock very different from other trylocks, and very confusing because if (ww_mutex_trylock(lock, ctx)) would not do what you would think it would do. Yuck ;-) Anyway, what I was thinking of is something like: T0 T1 try A lock B lock B lock A Now, if for some reason T1 won the lottery such that T0 would have to be wounded, T0's context would indicate its the first entry and not return -EDEADLK. And this sounds like something lockdep is designed to complain about. Nothing stops you from doing try A then doing try B, which would be the correct way to deal with this situation. Why would you trylock one, and then not do the same for another? OTOH, anybody doing creative things like that might well deserve whatever they get ;-) Indeed! The thing is; if there could exist something like: ww_mutex_trylock(struct ww_mutex *, struct ww_acquire_ctx *ctx); Then we should not now take away that name and make it mean something else; namely: ww_mutex_trylock_single(). Unless we want to allow .ctx=NULL to mean _single. As to why I proposed that (.ctx=NULL meaning _single); I suppose because I'm a minimalist at heart. Minimalism isn't bad, it's just knowing when to sto :-) -- 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 v3 2/3] mutex: add support for wound/wait style locks, v3
On Mon, May 27, 2013 at 10:21 AM, Peter Zijlstra pet...@infradead.org wrote:
On Wed, May 22, 2013 at 07:24:38PM +0200, Maarten Lankhorst wrote:
+static inline void ww_acquire_init(struct ww_acquire_ctx *ctx,
+ struct ww_class *ww_class)
+{
+ ctx-task = current;
+ do {
+ ctx-stamp = atomic_long_inc_return(ww_class-stamp);
+ } while (unlikely(!ctx-stamp));
I suppose we'll figure something out when this becomes a bottleneck.
Ideally
we'd do something like:
ctx-stamp = local_clock();
but for now we cannot guarantee that's not jiffies, and I suppose that's a
tad
too coarse to work for this.
This might mess up when 2 cores happen to return exactly the same time, how
do you choose a winner in that case?
EDIT: Using pointer address like you suggested below is fine with me. ctx
pointer would be static enough.
Right, but for now I suppose the 'global' atomic is ok, if/when we find
it hurts performance we can revisit. I was just spewing ideas :-)
We could do a simple
ctx-stamp = (local_clock() nr_cpu_shift) | local_processor_id()
to work around any bad luck in grabbing the ticket. With sufficient
fine clocks the bias towards smaller cpu ids would be rather
irrelevant. Just wanted to drop this idea before I'll forget about it
again ;-)
-Daniel
--
Daniel Vetter
Software Engineer, Intel Corporation
+41 (0) 79 365 57 48 - http://blog.ffwll.ch
--
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 v3 2/3] mutex: add support for wound/wait style locks, v3
On Mon, May 27, 2013 at 4:47 PM, Daniel Vetter dan...@ffwll.ch wrote:
On Mon, May 27, 2013 at 10:21 AM, Peter Zijlstra pet...@infradead.org wrote:
On Wed, May 22, 2013 at 07:24:38PM +0200, Maarten Lankhorst wrote:
+static inline void ww_acquire_init(struct ww_acquire_ctx *ctx,
+ struct ww_class *ww_class)
+{
+ ctx-task = current;
+ do {
+ ctx-stamp = atomic_long_inc_return(ww_class-stamp);
+ } while (unlikely(!ctx-stamp));
I suppose we'll figure something out when this becomes a bottleneck.
Ideally
we'd do something like:
ctx-stamp = local_clock();
but for now we cannot guarantee that's not jiffies, and I suppose that's
a tad
too coarse to work for this.
This might mess up when 2 cores happen to return exactly the same time, how
do you choose a winner in that case?
EDIT: Using pointer address like you suggested below is fine with me. ctx
pointer would be static enough.
Right, but for now I suppose the 'global' atomic is ok, if/when we find
it hurts performance we can revisit. I was just spewing ideas :-)
We could do a simple
ctx-stamp = (local_clock() nr_cpu_shift) | local_processor_id()
to work around any bad luck in grabbing the ticket. With sufficient
fine clocks the bias towards smaller cpu ids would be rather
irrelevant. Just wanted to drop this idea before I'll forget about it
again ;-)
Not a good idea to throw around random ideas right after a work-out.
This is broken since different threads could end up with the same low
bits. Comparing ctx pointers otoh on top of the timestamp should work.
-Daniel
--
Daniel Vetter
Software Engineer, Intel Corporation
+41 (0) 79 365 57 48 - http://blog.ffwll.ch
--
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 v3 2/3] mutex: add support for wound/wait style locks, v3
Op 22-05-13 19:24, Maarten Lankhorst schreef: Hey, Op 22-05-13 18:18, Peter Zijlstra schreef: On Wed, May 22, 2013 at 01:18:14PM +0200, Maarten Lankhorst wrote: Lacking the actual msg atm, I'm going to paste in here... Thanks for taking the time to review. Subject: [PATCH v3 2/3] mutex: add support for wound/wait style locks, v3 From: Maarten Lankhorst maarten.lankhorst@x 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) Signed-off-by: Maarten Lankhorst maarten.lankhorst@x Signed-off-by: Daniel Vetter daniel.vetter@ --- Documentation/ww-mutex-design.txt | 322 +++ include/linux/mutex-debug.h |1 include/linux/mutex.h | 257 + kernel/mutex.c| 445 - lib/debug_locks.c |2 5 files changed, 1010 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..154bae3 --- /dev/null +++ b/Documentation/ww-mutex-design.txt @@ -0,0 +1,322 @@ +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 classe of w/w
Re: [Linaro-mm-sig] [PATCH v3 2/3] mutex: add support for wound/wait style locks, v3
On Thu, May 23, 2013 at 11:13 AM, Maarten Lankhorst maarten.lankho...@canonical.com wrote: 2. Do you really want to drop the *_slow variants? Doing so might reduce debugging slightly. I like method #2 in ww-mutex-design.txt, it makes it very clear why you would handle the *_slow case differently anyway. As you pointed out, we wouldn't lose much debugging information. The same checks could be done in the normal variant with WARN_ON(ctx-lock ctx-lock != lock); WARN_ON(ctx-lock ctx-acquired 0); s/lock/contending_lock/ I guess. But yeah, I should have more carefully read Peter's suggestion to fold in some of the ww_slow debug checks, we can indeed keep the important debug checks even when dropping slow. Silly me should be less sloppy. But it boils down to ww_mutex_lock_slow returning void instead of int __must_check from ww_mutex_lock. Maybe add inlines for *_slow, that use the ww_mutex_lock functions, and check ctx-lock == lock in debugging mode? So either we keep the _slow versions or drop the __must_check for ww_mutex_lock. In both cases the ww mutex user needs to think a bit what to do, and I don't there's much we can do in the implementation (beside all the existing debug support we have) to help. So now I'm leaning more towards dropping the _slow variants to avoid interface proliferation. -Daniel -- Daniel Vetter Software Engineer, Intel Corporation +41 (0) 79 365 57 48 - http://blog.ffwll.ch -- 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 v3 2/3] mutex: add support for wound/wait style locks, v3
Hey,
Op 30-04-13 21:14, Daniel Vetter schreef:
On Sun, Apr 28, 2013 at 07:04:07PM +0200, Maarten Lankhorst 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)
While writing the kerneldoc I've carefully check that all restrictions are
enforced through debug checks somehow. I think that with full mutex debug
(including lockdep) enabled, plus the slowpath injector patch I've just
posted, _all_ interface abuse will be catched at runtime as long as all
the single-threaded/uncontended cases are exercises sufficiently.
So I think we've fully achieved level 5 on the Rusty API safety scale
here. Higher levels seem pretty hard given that the concepts are rather
fancy, but I think with the new (and much more consitent) naming, plus the
explicit introduction as (more abstruct) structures for ww_class and
ww_acquire_context the interface is about as intuitive as it gets.
So all together I'm pretty happy with what the interface looks like. And
one quick bikeshed below on the implementation.
-Daniel
I included your fix below. I'm hoping to get this included in 3.11 through the
drm tree, so
I can convert ttm to use it, but I haven't received any further reply on the
patch series.
The 3.10 mutex improvement patches don't seem to cause any conflicts when
merging
linus' tree, so I'll use drm-next as a base.
Are there any issues left? I included the patch you wrote for injecting
-EDEADLK too
in my tree. The overwhelming silence makes me think there are either none, or
nobody cared enough to review it. :(
+/*
+ * after acquiring lock with fastpath or when we lost out in contested
+ * slowpath, set ctx and wake up any waiters so they can recheck.
+ *
+ * This function is never called when CONFIG_DEBUG_LOCK_ALLOC is set,
+ * as the fastpath and opportunistic spinning are disabled in that case.
+ */
+static __always_inline void
+ww_mutex_set_context_fastpath(struct ww_mutex *lock,
+ struct ww_acquire_ctx *ctx)
+{
+unsigned long flags;
+struct mutex_waiter *cur;
+
+ww_mutex_lock_acquired(lock, ctx, false);
+
+lock-ctx = ctx;
+smp_mb__after_atomic_dec();
I think this should be
+ smp_mb__after_atomic_dec();
+ lock-ctx = ctx;
+ smp_mb();
Also I wonder a bit how much this hurts the fastpath, and whether we
should just shovel the ctx into the atomic field with a cmpxcht, like the
rt mutex code does with the current pointer.
Fixed. I'm not sure if the second smp_mb is really needed. If there was a
smp_mb__before_atomic_read it would have been sufficient.
~Maarten
--
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 v3 2/3] mutex: add support for wound/wait style locks, v3
Are there any issues left? I included the patch you wrote for injecting -EDEADLK too in my tree. The overwhelming silence makes me think there are either none, or nobody cared enough to review it. :( It didn't manage to reach my inbox it seems,.. I can only find a debug patch in this thread. -- 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 v3 2/3] mutex: add support for wound/wait style locks, v3
Op 22-05-13 13:37, Peter Zijlstra schreef: Are there any issues left? I included the patch you wrote for injecting -EDEADLK too in my tree. The overwhelming silence makes me think there are either none, or nobody cared enough to review it. :( It didn't manage to reach my inbox it seems,.. I can only find a debug patch in this thread. Odd, maybe in your spam folder? It arrived on all mailing lists, so I have no idea why you were left out. http://www.spinics.net/lists/linux-arch/msg21425.html ~Maarten -- 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 v3 2/3] mutex: add support for wound/wait style locks, v3
On Wed, May 22, 2013 at 01:47:42PM +0200, Maarten Lankhorst wrote: Op 22-05-13 13:37, Peter Zijlstra schreef: Are there any issues left? I included the patch you wrote for injecting -EDEADLK too in my tree. The overwhelming silence makes me think there are either none, or nobody cared enough to review it. :( It didn't manage to reach my inbox it seems,.. I can only find a debug patch in this thread. Odd, maybe in your spam folder? Couldn't spot it there either.. weird. It arrived on all mailing lists, I should both clean up my one huge lkml maildir and hack notmuch into submission so I can read LKML again :/ so I have no idea why you were left out. http://www.spinics.net/lists/linux-arch/msg21425.html Thanks, I'll go stare at it. -- 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 v3 2/3] mutex: add support for wound/wait style locks, v3
On Wed, May 22, 2013 at 01:18:14PM +0200, Maarten Lankhorst wrote: Lacking the actual msg atm, I'm going to paste in here... Subject: [PATCH v3 2/3] mutex: add support for wound/wait style locks, v3 From: Maarten Lankhorst maarten.lankhorst@x 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) Signed-off-by: Maarten Lankhorst maarten.lankhorst@x Signed-off-by: Daniel Vetter daniel.vetter@ --- Documentation/ww-mutex-design.txt | 322 +++ include/linux/mutex-debug.h |1 include/linux/mutex.h | 257 + kernel/mutex.c| 445 - lib/debug_locks.c |2 5 files changed, 1010 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..154bae3 --- /dev/null +++ b/Documentation/ww-mutex-design.txt @@ -0,0 +1,322 @@ +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 classe of w/w lock acquire functions: +- Normal lock acquisition with a context, using ww_mutex_lock +- Slowpath lock acquisition
Re: [PATCH v3 2/3] mutex: add support for wound/wait style locks, v3
On Wed, May 22, 2013 at 6:18 PM, Peter Zijlstra pet...@infradead.org wrote: On Wed, May 22, 2013 at 01:18:14PM +0200, Maarten Lankhorst wrote: Lacking the actual msg atm, I'm going to paste in here... Just replying to the interface/doc comments, Maarten's the guy for the gory details ;-) Subject: [PATCH v3 2/3] mutex: add support for wound/wait style locks, v3 From: Maarten Lankhorst maarten.lankhorst@x 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) Signed-off-by: Maarten Lankhorst maarten.lankhorst@x Signed-off-by: Daniel Vetter daniel.vetter@ --- Documentation/ww-mutex-design.txt | 322 +++ include/linux/mutex-debug.h |1 include/linux/mutex.h | 257 + kernel/mutex.c| 445 - lib/debug_locks.c |2 5 files changed, 1010 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..154bae3 --- /dev/null +++ b/Documentation/ww-mutex-design.txt @@ -0,0 +1,322 @@ +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
Re: [PATCH v3 2/3] mutex: add support for wound/wait style locks, v3
Hey, Op 22-05-13 18:18, Peter Zijlstra schreef: On Wed, May 22, 2013 at 01:18:14PM +0200, Maarten Lankhorst wrote: Lacking the actual msg atm, I'm going to paste in here... Thanks for taking the time to review. Subject: [PATCH v3 2/3] mutex: add support for wound/wait style locks, v3 From: Maarten Lankhorst maarten.lankhorst@x 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) Signed-off-by: Maarten Lankhorst maarten.lankhorst@x Signed-off-by: Daniel Vetter daniel.vetter@ --- Documentation/ww-mutex-design.txt | 322 +++ include/linux/mutex-debug.h |1 include/linux/mutex.h | 257 + kernel/mutex.c| 445 - lib/debug_locks.c |2 5 files changed, 1010 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..154bae3 --- /dev/null +++ b/Documentation/ww-mutex-design.txt @@ -0,0 +1,322 @@ +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 classe of w/w lock acquire functions: +- Normal lock acquisition
Re: [PATCH v3 2/3] mutex: add support for wound/wait style locks, v3
On Sun, Apr 28, 2013 at 07:04:07PM +0200, Maarten Lankhorst 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)
While writing the kerneldoc I've carefully check that all restrictions are
enforced through debug checks somehow. I think that with full mutex debug
(including lockdep) enabled, plus the slowpath injector patch I've just
posted, _all_ interface abuse will be catched at runtime as long as all
the single-threaded/uncontended cases are exercises sufficiently.
So I think we've fully achieved level 5 on the Rusty API safety scale
here. Higher levels seem pretty hard given that the concepts are rather
fancy, but I think with the new (and much more consitent) naming, plus the
explicit introduction as (more abstruct) structures for ww_class and
ww_acquire_context the interface is about as intuitive as it gets.
So all together I'm pretty happy with what the interface looks like. And
one quick bikeshed below on the implementation.
-Daniel
Signed-off-by: Maarten Lankhorst maarten.lankho...@canonical.com
Signed-off-by: Daniel Vetter daniel.vet...@ffwll.ch
---
Documentation/ww-mutex-design.txt | 322 +++
include/linux/mutex-debug.h |1
include/linux/mutex.h | 257 +
kernel/mutex.c| 445
-
lib/debug_locks.c |2
5 files changed, 1010 insertions(+), 17 deletions(-)
create mode 100644 Documentation/ww-mutex-design.txt
[snip]
+/*
+ * after acquiring lock with fastpath or when we lost out in contested
+ * slowpath, set ctx and wake up any waiters so they can recheck.
+ *
+ * This function is never called when CONFIG_DEBUG_LOCK_ALLOC is set,
+ * as the fastpath and opportunistic spinning are disabled in that case.
+ */
+static __always_inline void
+ww_mutex_set_context_fastpath(struct ww_mutex *lock,
+struct ww_acquire_ctx *ctx)
+{
+ unsigned long flags;
+ struct mutex_waiter *cur;
+
+ ww_mutex_lock_acquired(lock, ctx, false);
+
+ lock-ctx = ctx;
+ smp_mb__after_atomic_dec();
I think this should be
+ smp_mb__after_atomic_dec();
+ lock-ctx = ctx;
+ smp_mb();
Also I wonder a bit how much this hurts the fastpath, and whether we
should just shovel the ctx into the atomic field with a cmpxcht, like the
rt mutex code does with the current pointer.
+
+ /*
+ * Check if lock is contended, if not there is nobody to wake up
+ */
+ if (likely(atomic_read(lock-base.count) == 0))
+ return;
+
+ /*
+ * Uh oh, we raced in fastpath, wake up everyone in this case,
+ * so they can see the new ctx
+ */
+ spin_lock_mutex(lock-base.wait_lock, flags);
+ list_for_each_entry(cur, lock-base.wait_list, list) {
+ debug_mutex_wake_waiter(lock-base, cur);
+ wake_up_process(cur-task);
+ }
+ spin_unlock_mutex(lock-base.wait_lock, flags);
+}
+
--
Daniel Vetter
Software Engineer, Intel Corporation
+41 (0) 79 365 57 48 - http://blog.ffwll.ch
--
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
[PATCH v3 2/3] mutex: add support for wound/wait style locks, v3
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) Signed-off-by: Maarten Lankhorst maarten.lankho...@canonical.com Signed-off-by: Daniel Vetter daniel.vet...@ffwll.ch --- Documentation/ww-mutex-design.txt | 322 +++ include/linux/mutex-debug.h |1 include/linux/mutex.h | 257 + kernel/mutex.c| 445 - lib/debug_locks.c |2 5 files changed, 1010 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..154bae3 --- /dev/null +++ b/Documentation/ww-mutex-design.txt @@ -0,0 +1,322 @@ +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 classe of w/w lock acquire functions: +- Normal lock acquisition with a context, using ww_mutex_lock +- Slowpath lock acquisition on the contending lock, used by the wounded task + after having dropped all already acquired locks. These functions have the + _slow postfix. +- Functions to only acquire a single w/w mutex, which results in the exact same + semantics as a normal mutex. These functions have the _single postfix. + +Of course, all the usual variants for handling wake-ups due to signals are also +provided. + +Usage
