On Thu, 2013-02-28 at 11:25 +0100, Maarten Lankhorst wrote:

+struct ticket_mutex {

•   struct mutex base;
  

•   atomic_long_t reservation_id;
  

+};

I'm not sure this is a good name, esp. due to the potential confusion vs the ticket spinlocks we have.

On Thu, 2013-02-28 at 11:25 +0100, Maarten Lankhorst wrote:

+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, from a +global counter. In case of deadlock while locking all the buffers +associated with a execbuf, the one with the lowest reservation_id +wins, and the one with the higher reservation_id unlocks all of the +buffers that it has already locked, and then tries again.

So the thing that made me cringe inside when I read this was making it all work on -rt, where we also need to take PI into account and ensure the entire thing is deterministic.

It _might_ be 'easy' and we could fall back to PI mutex behaviour in the case the reservation IDs match; however the entire for-all-bufs retry loops do worry me still.

Head hurts, needs more time to ponder. It would be good if someone else (this would probably be you maarten) would also consider this and explore this 'interesting' problem space :-)

On Tue, Apr 2, 2013 at 1:00 PM, Peter Zijlstra a.p.zijlstra@chello.nl wrote:

Also, is there anything in CS literature that comes close to this? I'd think the DBMS people would have something similar with their transactional systems. What do they call it?

I've looked around a bit and in dbms row-locking land this seems to be called the wound-wait deadlock avoidance algorithm. It's the same approach where if you encounter an older ticket (there called transaction timestamp) you drop all locked rows and retry (or abort) the transaction. If you encounter a newer ticket when trying to grab a lock simply do a blocking wait. So ticket/reservation in Maartens patches is the analog of timestamp/transaction. -Daniel

On Tue, Apr 2, 2013 at 6:59 PM, Peter Zijlstra a.p.zijlstra@chello.nl wrote:

...

...

Head hurts, needs more time to ponder. It would be good if someone else (this would probably be you maarten) would also consider this explore this 'interesting' problem space :-)

...

My head too, evil priority stuff!

Hacky but pragmatical workaround for now: use a real mutex around all the reserve_mutex_lock* calls instead of a virtual lock. It can be unlocked as soon as all locks have been taken, before any actual work is done.

It only slightly kills the point of having a reservation in the first place, but at least it won't break completely -rt completely for now.

Yeah, global lock, yay :-(

We've discussed this quite a bit on irc and came up with a bunch of other ideas. The global lock is completely transparent to users, since the lockdep annotations already rely on ticket_init/fini being a virtual lock. So we can always fall back to that option.

For more fancy approaches we need to consider the aim first - do we just want to prevent deadlocks through PI or do we aim for bounded per-reservation_mutex wait block-to-acquire times for the thread with highest rt-prio.

If it's just the former I think we can get by by piggy-packing on top of the existing PI mutex code. Only downside is that threads can lock arbitrary many reservation locks and so we're looking at boosting an entire tree of processes. Otoh common operations done while holding such a lock are swapping buffer objects in or waiting for gpu rendering. And since we can easily queue up a few ms of rendering rt guarantees are out the window ;-)

If that's not good enough and the global lock not scalable enough we could try to limit the fan-out by setting a PI-boost flag in the reservation ticket (in additional to the normal PI boosting for the reservation mutex). Threads which are boosted in that fashion will get a -EAGAIN on the next mutex_reserv_lock call, ensuring that the blocking doesn't spread to further threads. But that requires that we pass around pointers to tickets instead of values, so lifetime fun (atm the ticket is on the stack) and probably tons of races in updating the ticket boost state. I'd like to avoid that until we've demonstrated a need for it ...

In any way I think that all three approaches should fit into the proposed interfaces, so we should be able to do something sane here. But since I have pretty much zero clue about rt I have no idea which of the first two approaches would be preferable.

Cheers, Daniel

I'm sorry, this email ended up quite a bit longer than I had hoped for; please bear with me.

On Tue, 2013-04-02 at 18:59 +0200, Peter Zijlstra wrote:

struct ww_mutex; /* wound/wait */

int mutex_wound_lock(struct ww_mutex *); /* returns -EDEADLK */ int mutex_wait_lock(struct ww_mutex *); /* does not fail */

Hmm.. thinking about that,.. you only need that second variant because you don't have a clear lock to wait for the 'older' process to complete; but having the unconditional wait makes the entire thing prone to accidents and deadlocks when the 'user' (read your fellow programmers) make a mistake.

Ideally we'd only have the one primitive that returns -EDEADLK and use a 'proper' mutex to wait on or somesuch.. let me ponder this a bit more.

So I had me a little ponder..

Its all really about breaking the symmetry (equivalence of both sides) of the deadlock. Lets start with the simplest AB-BA deadlock:

task-O task-Y A B A <-- blocks on O B <-- blocks on Y

In this case the wound-wait algorithm says that the older task (O) has precedence over the younger task (Y) and we'll 'kill' Y to allow progress for O.

Now clearly we don't really want to kill Y, instead we'll allow its lock operation to return -EDEADLK.

This would suggest that our 'new' mutex implementation (ww_mutex henceforth) has owner tracking -- so O acquiring B can find Y to 'kill' -- and that we have a new wakeup state TASK_DEADLOCK similar to TASK_WAKEKILL (can we avoid this by using the extra state required below? I don't think so since we'd have the risk of waking Y while it would be blocked on a !ww_mutex)

Now this gets a little more interesting if we change the scenario a little:

task-O task-Y A B B <-- blocks on Y * <-- could be A

In this case when O blocks Y isn't actually blocked, so our TASK_DEADLOCK wakeup doesn't actually achieve anything.

This means we also have to track (task) state so that once Y tries to acquire A (creating the actual deadlock) we'll not wait so our TASK_DEADLOCK wakeup doesn't actually achieve anything.

Note that Y doesn't need to acquire A in order to return -EDEADLK, any acquisition from the same set (see below) would return -EDEADLK even if there isn't an actual deadlock. This is the cost of heuristic; we could walk the actual block graph but that would be prohibitively expensive since we'd have to do this on every acquire.

This raises the point of what would happen if Y were to acquire a 'regular' mutex in between the series of ww_mutexes. In this case we'd clearly have an actual deadlock scenario. However lockdep would catch this for we'd clearly invert the lock class order:

ww_mutex -> other -> ww_mutex

For the more complex scenarios there's the case of multiple waiters. In this case its desirable to order the waiters in age order so that we don't introduce age inversion -- this minimizes the amount of -EDEADLK occurrences, but also allows doing away with the unconditional wait.

With the lock queue ordering we can simply immediately re-try the lock acquisition sequence. Since the older task is already queued it will obtain the lock, even if we re-queue ourselves before the lock is assigned.

Now the one thing I've so far 'ignored' is how to assign age. Forward progress guarantees demand that the age doesn't get reset on retries; doing so would mean you're always pushing yourself fwd, decreasing your 'priority', never getting to be the most eligible. However it also means that we should (re)set the time every time we start a 'new' acquisition sequence. If we'd use a static (per task) age the task with the lowest age would be able to 'starve' all other.

This means we need means to mark the start of an acquisition sequence; one that is not included in the restart loop.

Having a start suggests having an end marker too, and indeed we can find a reason for having one; suppose our second scenario above, where Y has already acquired all locks it needs to proceed. In this case we would have marked Y to fail on another acquisition. This doesn't seem like a problem until you consider the case where we nest different mm_mutex sets. In this case Y would -EDEADLK on the first of the second (nested) set, even though re-trying that set is pointless, O doesn't care.

Furthermore, considering the first scenario, O could block on a lock of the first set when Y is blocked on a lock of the second (nested) set; we need means of discerning the different lock sets. This cannot be done by local means, that is, any context created by the start/end markers would be local to that task and would not be recognizable by another as to belong to the same group.

Instead we'd need to create a set-class, much like lockdep has and somehow ensure all locks in a set are of that class.

One thing I'm not entirely sure of is the strict need for a local context it could be used to track the set-class, but I'm not entirely sure we need that to clean up state at the end marker. I haven't been creative enough to construct a fail case where both O and Y nest and a pending EDEADLK state could cross the end marker wrongly.

However, having a local context, even if empty, does put a few constraints on the API usage, which as per below, is a good thing.

To recap, we now have:

struct ww_mutex_key { }; struct ww_mutex; struct ww_mutex_ctx;

void __ww_mutex_init(struct ww_mutex *, void *);

#define ww_mutex_init(ww_mutex) \ do { \ static struct ww_mutex_key __key; \ __ww_mutex_init(ww_mutex, &__key); \ } while (0)

void ww_mutex_acquire_start(struct ww_mutex_ctx *); void ww_mutex_acquire_end (struct ww_mutex_ctx *);

int ww_mutex_lock(struct ww_mutex_ctx *, struct ww_mutex *); void ww_mutex_unlock(struct ww_mutex *);

Which are to be used like:

int bufs_lock(bufs) { struct ww_mutex_ctx ww_ctx;

ww_mutex_acquire_start(&ww_ctx); retry: for-all-buffers(buf, bufs) { err = ww_mutex_lock(&ww_ctx, &buf->lock); if (err) goto error; }

ww_mutex_acquire_end(&ww_ctx);

return 0; /* success */

error: for-all-buffers(buf2, bufs) { if (buf2 == buf) break; ww_mutex_unlock(&buf->lock); } if (err == -EDEADLK) goto again;

return err; /* other error */ }

void bufs_unlock(bufs) { for-all-buffers(buf, bufs) ww_mutex_unlock(&buf->lock); }

This API has a few problems as per Rusty's API guidelines, it is fairly trivial to use it wrong; mostly the placement of the start and end markers are easy to get wrong, but of course one can get all kinds of badness from doing the retry wrong. At least having the local context forces one to use the start/end markers.

The only remaining 'problem' left is RT, however the above suggests a very clean solution; change the lock queueing order to first sort on priority (be it the SCHED_FIFO/RR static priority or SCHED_DEADLINE dynamic priority) and secondly on the age.

Note that (re)setting the age at every acquisition set is really only a means to provide FIFO fairness between tasks, RT tasks don't strictly require this, they have their own ordering.

With all that this locking scheme should be deterministic; and in cases where the older task would block (the young task has passed the end marker) we can apply PI and push Y's priority.

Did I miss something?

Anyway, I haven't actually looked at the details of your implementation yet, I'll get to that next, but I think something like the above should be what we want to aim for.

*phew* thanks for reading this far ! :-)

On Thu, 2013-04-04 at 15:31 +0200, Daniel Vetter wrote:

We do add some form of owner tracking by storing the reservation ticket of the current holder into every ww_mutex. So when task-Y in your above example tries to acquire lock A it notices that it's behind in the global queue and immedieately returns -EAGAIN to indicate the deadlock.

Aside, there's a bit of fun in that ttm uses -EDEADLCK for when you try to reserve the same buffer twice - it can easily detect that by comparing the lock owner ticket with the provided one and if it matches bail out.

Sure, but this should bear no influence on the design of the mutex primitive. At most we should ensure this situation is recognizable.

Hence we've kept the special -EDEADLCK semantics even for the ww_mutex stuff.

There's EDEADLK and EDEADLOCK, EDEADLCK does alas not exist :-)

...

Now this gets a little more interesting if we change the scenario a little:

  task-O  task-Y
    A
          B
    B <-- blocks on Y
          * <-- could be A

The current code at least simple blocks task-O on B until task-Y unlocks B. Deadlocks cannot happen since if task-Y ever tries to acquire a lock which is held by an older task (e.g. lock A) it will bail out with -EAGAIN.

Agreed, O would have to wait until Y unlocks B. It was a 'detail' I skimped over for the sake of brevity. I was merely trying to illustrate the ways in which we must bring Y to return -EDEADLK (or -EAGAIN in your version).

On Thu, 2013-04-04 at 15:31 +0200, Daniel Vetter wrote:

The trick with the current code is that the oldest task will never see an -EAGAIN ever and hence is guaranteed to make forward progress. If the task is really unlucky though it might be forced to wait for a younger task for every ww_mutex it tries to acquire.

Agreed on that.. while I didn't state this my proposed thing should behave the same. It follows from the symmetry breaking in that only younger tasks can get 'kill'ed.

On Thu, 2013-04-04 at 15:31 +0200, Daniel Vetter wrote:

Another big reason for having a start/end marker like you've describe is lockdep support.

Yeah, I saw how you did that.. but there's other ways of making it work too, you could for instance create a new validation state for this type of lock.

That said, I didn't consider lockdep too much, I first want the regular semantics clear.

On Thu, 2013-04-04 at 15:31 +0200, Daniel Vetter wrote:

We've discussed this approach of using (rt-prio, age) instead of just age to determine the the "oldness" of a task for deadlock-breaking with -EAGAIN. The problem is that through PI boosting or normal rt-prio changes while tasks are trying to acquire ww_mutexes you can create acyclic loops in the blocked-on graph of ww_mutexes after the fact and so cause deadlocks. So we've convinced ourselves that this approche doesn't work.

Could you pretty please draw me a picture, I'm having trouble seeing what you mean.

AFAICT as long as you boost Y while its the lock owner things should work out, no?

On Thu, Apr 4, 2013 at 3:31 PM, Daniel Vetter daniel@ffwll.ch wrote:

...

In this case when O blocks Y isn't actually blocked, so our TASK_DEADLOCK wakeup doesn't actually achieve anything.

This means we also have to track (task) state so that once Y tries to acquire A (creating the actual deadlock) we'll not wait so our TASK_DEADLOCK wakeup doesn't actually achieve anything.

Note that Y doesn't need to acquire A in order to return -EDEADLK, any acquisition from the same set (see below) would return -EDEADLK even if there isn't an actual deadlock. This is the cost of heuristic; we could walk the actual block graph but that would be prohibitively expensive since we'd have to do this on every acquire.

Hm, I guess your aim with the TASK_DEADLOCK wakeup is to bound the wait times of older task. This could be interesting for RT, but I'm unsure of the implications. The trick with the current code is that the oldest task will never see an -EAGAIN ever and hence is guaranteed to make forward progress. If the task is really unlucky though it might be forced to wait for a younger task for every ww_mutex it tries to acquire.

[Aside: I'm writing this while your replies trickle in, but I think it's not yet answered already.]

Ok, I've discussed this a lot with Maarten on irc and I think I see a bit clearer now what's the aim with the new sleep state. Or at least I have an illusion about it ;-) So let me try to recap my understanding to check whether we're talking roughly about the same idea.

I think for starters we need to have a slightly more interesting example:

3 threads O, M, Y: O has the oldest ww_age/ticket, Y the youngest, M is in between. 2 ww_mutexes: A, B

Y has already acquired ww_mutex A, M has already acquired ww_mutex B.

Now O wants to acquire B and M wants to acquire A (let's ignore detailed ordering for now), resulting in O blocking on M (M holds B already, but O is older) and M blocking on Y (same for lock B).

Now first question to check my understanding: Your aim with that special wakeup is to kick M so that it backs off and drops B? That way O does not need to wait for Y to complete whatever it's currently doing, unlock A and then in turn M to complete whatever it's doing so that it can unlock A&B and finally allows O to grab the lock.

Presuming I'm still following we should be able to fix this with the new sleep state TASK_DEADLOCK and a flag somewhere in the thread info (let's call it PF_GTFO for simplicity). Then every time a task does a blocking wait on a ww_mutex it would set this special sleep state and also check the PF_GTFO bit. If the later is set, it bails out with -EAGAIN (so that all locks are dropped).

Now if a task wants to take a lock and notices that it's held by a younger locker it can set that flag and wake the thread up (need to think about all the races a bit, but we should be able to make this work). Then it can do the normal blocking mutex slowpath and wait for the unlock.

Now if O and M race a bit against each another M should either get woken (if it's already blocked on Y) and back off, or notice that the thread flag is set before it even tries to grab another mutex (and so before the block tree can extend further to Y). And the special sleep state is to make sure we don't cause any other spurious interrupts. -Daniel -- Daniel Vetter Software Engineer, Intel Corporation +41 (0) 79 365 57 48 - http://blog.ffwll.ch

On Thu, Apr 4, 2013 at 6:49 PM, Peter Zijlstra peterz@infradead.org wrote:

On Thu, 2013-04-04 at 15:31 +0200, Daniel Vetter wrote:

...

We've discussed this approach of using (rt-prio, age) instead of just age to determine the the "oldness" of a task for deadlock-breaking with -EAGAIN. The problem is that through PI boosting or normal rt-prio changes while tasks are trying to acquire ww_mutexes you can create acyclic loops in the blocked-on graph of ww_mutexes after the fact and so cause deadlocks. So we've convinced ourselves that this approche doesn't work.

Could you pretty please draw me a picture, I'm having trouble seeing what you mean.

AFAICT as long as you boost Y while its the lock owner things should work out, no?

So this one here took a bit of pondering. But I think you'll like the conclusion.

Now the deadlock detection works because it impose a dag onto all lockers which clearly denotes who'll wait and who will get wounded. The problem with using (rt_prio, ww_age/ticket) instead of just the ticket si that it's ambigous in the face of PI boosting. E.g. - rt_prio of A > rt_prio of B, but - task A is younger than task B

Before boosting task A wins, but after boosting (when only the age matters) task B wins, since it's now older. So now when B comes around and tries to grab a lock A currently holds, it'll also block.

Now the cool thing with TASK_KILLABLE (hey, I start to appreciate it, bear with me!) is that this is no problem - it limits the length of any chain of blocked tasks to just one link of blocked tasks: - If the length is currently one it cannot be extended - the blocked task will set the PF_GTFO flag on the current holder, and since that would be checked before blocking on another ww_mutex the chain can't grow past one blocked task. - If the current holder itself is blocked on another ww_mutex it'll be in TASK_DEADLOCK state and get woken up.

In both case the current holder of the lock will either continue with what it's been doing (PI-boosted ofc) until it unlocks everything or hits the PF_GTFO check and backs off from all currently held locks. RT mission accomplished I think since the wait time for the highest-prio task for grabbing a lock is bounded by the lock hold time for the completely uncontended case. And within a given rt-prio the normal wait/wound algorithm will resolve conflicts (and ensure forward progress).

So I'm now rather convinced that with the TASK_DEADLOCK implementation we can make (rt_prio, age) lock ordering work. But it's not an artifact of consistent PI boosting (I've raced down that alley first trying to prove it to no avail), but the fact that lock holder kicking through PF_GTFO naturally limits blocked task chains on ww_mutexes to just one link. That in turn makes any post-PI-boosted considerations moot and so can't result in havoc due to a PI-boost having flipped an edge in the lock_er_ ordering DAG (we sort tasks with wait/wound, not locks, hence it's not a lock ordering DAG).

Please poke holes into this argument, I've probably missed a sublety somewhere ... -Daniel -- Daniel Vetter Software Engineer, Intel Corporation +41 (0) 79 365 57 48 - http://blog.ffwll.ch

On Mon, Apr 08, 2013 at 12:39:24PM +0200, Peter Zijlstra wrote:

On Thu, 2013-04-04 at 18:56 +0200, Daniel Vetter wrote:

...

Presuming I'm still following we should be able to fix this with the new sleep state TASK_DEADLOCK and a flag somewhere in the thread info (let's call it PF_GTFO for simplicity).

I'm reading "Get The F*ck Out" ? I like the name, except PF_flags are unsuitable since they are not atomic and we'd need to set it from another thread.

I think the PF_ flag is a non-starter for a different reason, too. To make different clases of ww_mutexes nest properly, we need to make sure that we don't dead/live-lock trying to wake up a task holdinga ww_mutex of class A, while that task is trying to acquire ww_mutexes of class B. Picture:

task 1 task 2 task 3 holds lock B ticket_A = acquire_start(class A) ww_mutex_lock(lock A, ticket_A) busy doing something

ticket_B = acquire_start(class B) ww_mutex_lock(lock B, ticket_B) -> contention with task 3 ticket_task2 = acquire_start(class A) ww_mutex_lock(lock A, ticket_task2) -> contention with task 1

If we go with the PF_GTFO task flag, task 2 will set it on task 1 (handwave locking/atomicity again here ;-). But taks 1 will only back off from any locks in class B. Or at least I think we should impose that restriction, since otherwise a ww_mutex acquire loop will leak out badly abstraction-wise and making nesting pretty much impossible in practice.

But if we really want nesting to work transparently, then task 1 should be allowed to continue taking locks from class A (after an acquire_end(class B) call ofc). But then it will have missed the wakeup from task 2, so task 2 blocks for too long and task 1 doesn't back off from further acquiring locks in class A.

Presuming my reasoning for the rt case isn't broken, this break deadlock avoidance if we sort by (rt_prio, ticket).

So I think we need to move the PF_GTFO flag to the ticket to make sure that task1 will notice that there's contention with one of the locks it holds from class A and that it better gtfo asap (i.e. back off, drop all currently held locks in class A and go into the slowpath).

But I still need to think the nesting case through a bit more (and draw some diagrams), so not sure yet. One thing I still need to ponder is how to best stack tickets (for tasks doing nested ww_mutex locking) and where all we need a pointer to relevant tickets and what kind of fun this entails ... I need to ponder this some more.

...

Then every time a task does a blocking wait on a ww_mutex it would set this special sleep state and also check the PF_GTFO bit.

So its the contending task (O for B) setting PF_GTFO on the owning task (M for B), right?

Yeah, the idea is that the contending task sets this bit on the current holder (whether we put that bit into the task or the ticket), so that the current owner can back off and drop all currently held locks at the next opportunity (either due to being woken up in TASK_DEADLCOK state or in the next ww_mutex_lock call).

But yeah, all ww_mutex sleep states should have the new TASK_DEADLOCK sleep state added.

...

If the later is set, it bails out with -EAGAIN (so that all locks are dropped).

I would really rather see -EDEADLK for that..

I agree it makes more sense for a general api (outside of ttm), but I struggle a bit to come up with a good errno for the "you hold this lock already" case. Best I could do is -EBUSY ...

Hm, looking through errno.h I've just spotted -EALREADY. Seems to be used all over (not just networking), so I guess we could extend it's meaning a bit?

...

Now if a task wants to take a lock and notices that it's held by a younger locker it can set that flag and wake the thread up (need to think about all the races a bit, but we should be able to make this work). Then it can do the normal blocking mutex slowpath and wait for the unlock.

Right.

...

Now if O and M race a bit against each another M should either get woken (if it's already blocked on Y) and back off, or notice that the thread flag is set before it even tries to grab another mutex

ww_mutex, it should block just fine on regular mutexes and other primitives.

Yes, that special behaviour should only apply to ww_mutexes not to any other locking. I've not been terribly careful here ... -Daniel

On Thu, Apr 04, 2013 at 06:38:36PM +0200, Peter Zijlstra wrote:

On Thu, 2013-04-04 at 15:31 +0200, Daniel Vetter wrote:

...

Hm, I guess your aim with the TASK_DEADLOCK wakeup is to bound the wait times of older task.

No, imagine the following:

struct ww_mutex A, B; struct mutex C;

task-O task-Y task-X A B C C B

At this point O finds that Y owns B and thus we want to make Y 'yield' B to make allow B progress. Since Y is blocked, we'll send a wakeup. However Y is blocked on a different locking primitive; one that doesn't collaborate in the -EDEADLK scheme therefore we don't want the wakeup to succeed.

I'm confused to why the above is a problem. Task-X will eventually release C, and then Y will release B and O will get to continue. Do we have to drop them once the owner is blocked? Can't we follow the chain like the PI code does?

-- Steve

On Thu, Apr 04, 2013 at 06:56:58PM +0200, Daniel Vetter wrote:

I think for starters we need to have a slightly more interesting example:

3 threads O, M, Y: O has the oldest ww_age/ticket, Y the youngest, M is in between. 2 ww_mutexes: A, B

Y has already acquired ww_mutex A, M has already acquired ww_mutex B.

Now I probably missed it in the thread somewhere, but what makes task O the oldest and Y the youngest? Is it the actual time from when the task was created? What about setting an age as soon as it starts the process of grabbing one of these locks? And it keeps the age until it successfully grabs and releases all the locks again. It wont reset if it had to drop the locks and start over.

Or am I totally not understanding what's going on here? Which could also be the case ;-)

-- Steve

On Wed, Apr 10, 2013 at 12:27 AM, Steven Rostedt rostedt@goodmis.org wrote:

On Thu, Apr 04, 2013 at 06:38:36PM +0200, Peter Zijlstra wrote:

...

On Thu, 2013-04-04 at 15:31 +0200, Daniel Vetter wrote:

...

Hm, I guess your aim with the TASK_DEADLOCK wakeup is to bound the wait times of older task.

No, imagine the following:

struct ww_mutex A, B; struct mutex C;

  task-O  task-Y  task-X
          A
          B
                  C
          C
  B

At this point O finds that Y owns B and thus we want to make Y 'yield' B to make allow B progress. Since Y is blocked, we'll send a wakeup. However Y is blocked on a different locking primitive; one that doesn't collaborate in the -EDEADLK scheme therefore we don't want the wakeup to succeed.

I'm confused to why the above is a problem. Task-X will eventually release C, and then Y will release B and O will get to continue. Do we have to drop them once the owner is blocked? Can't we follow the chain like the PI code does?

Just waiting until every task already holding a lock completes and unlucks it is indeed a viable solution - it's the currently implemented algorithm in ttm and Maarten's current patches.

The nice thing with Peter's wakeup idea on top is: - It bounds blocked times. - And (at least I think so) it's the key thing making PI boosting possible without any ugly PI inversion deadlocks happening. See

Message-ID: CAKMK7uEUdtiDDCRPwpiumkrST6suFY7YuQcPAXR_nJ0XHKzsAw@mail.gmail.com

for my current reasoning about this (I have not yet managed to poke a hole into it). -Daniel -- Daniel Vetter Software Engineer, Intel Corporation +41 (0) 79 365 57 48 - http://blog.ffwll.ch

On Mon, Apr 08, 2013 at 01:50:26PM +0200, Daniel Vetter wrote:

On Mon, Apr 08, 2013 at 12:39:24PM +0200, Peter Zijlstra wrote:

...

On Thu, 2013-04-04 at 18:56 +0200, Daniel Vetter wrote:

...

Presuming I'm still following we should be able to fix this with the new sleep state TASK_DEADLOCK and a flag somewhere in the thread info (let's call it PF_GTFO for simplicity).

I'm reading "Get The F*ck Out" ? I like the name, except PF_flags are unsuitable since they are not atomic and we'd need to set it from another thread.

I think the PF_ flag is a non-starter for a different reason, too. To make different clases of ww_mutexes nest properly, we need to make sure that we don't dead/live-lock trying to wake up a task holdinga ww_mutex of class A, while that task is trying to acquire ww_mutexes of class B. Picture:

task 1 task 2 task 3 holds lock B ticket_A = acquire_start(class A) ww_mutex_lock(lock A, ticket_A) busy doing something

ticket_B = acquire_start(class B) ww_mutex_lock(lock B, ticket_B) -> contention with task 3 ticket_task2 = acquire_start(class A) ww_mutex_lock(lock A, ticket_task2) -> contention with task 1

If we go with the PF_GTFO task flag, task 2 will set it on task 1 (handwave locking/atomicity again here ;-). But taks 1 will only back off from any locks in class B. Or at least I think we should impose that restriction, since otherwise a ww_mutex acquire loop will leak out badly abstraction-wise and making nesting pretty much impossible in practice.

But if we really want nesting to work transparently, then task 1 should be allowed to continue taking locks from class A (after an acquire_end(class B) call ofc). But then it will have missed the wakeup from task 2, so task 2 blocks for too long and task 1 doesn't back off from further acquiring locks in class A.

Presuming my reasoning for the rt case isn't broken, this break deadlock avoidance if we sort by (rt_prio, ticket).

So I think we need to move the PF_GTFO flag to the ticket to make sure that task1 will notice that there's contention with one of the locks it holds from class A and that it better gtfo asap (i.e. back off, drop all currently held locks in class A and go into the slowpath).

But I still need to think the nesting case through a bit more (and draw some diagrams), so not sure yet. One thing I still need to ponder is how to best stack tickets (for tasks doing nested ww_mutex locking) and where all we need a pointer to relevant tickets and what kind of fun this entails ... I need to ponder this some more.

Ok, so I think the nesting case should all work if we have a per-task/ticket flag to signal contention. The point I've mused over a bit is how to get at both the flag and the corresponding task to do the wakeup. I think for non-rt the simplest way is to store a pointer to the ticket in the ww_mutex, and the ticket the holds both the contention flag and a pointer to the task. Lifetime of that stuff would be protected by the wait_lock from disappearing untimely, which should allow the lock/unlock fastpaths to set/clear it non-atomically - only careful places is in the contented unlock slowpath. So rough api sketch for nesting ww_mutexes:

struct ww_class { atomic_t next_ticket; /* virtual lock to annotate the acquire_start/end sections. */ struct lock_class_key acquire_key; /* lockdep class of all ww_mutexes in this class */ struct lock_class_key mutex_key; /* for debug/tracepts */ const char *name };

DEFINE_WW_CLASS(name) /* ... and all the other usual magic init funcitons */

struct ww_acquire_ctx { struct task_struct *task; /* invariant */ usinged ticket; /* invariant */ /* atomic is probably overkill, but need to review the resulting * code with all the barriers first. */ atomic_t contention; }

void ww_acquire_start(struct ww_acuire_ctx *ctx, struct ww_class *class); void ww_acquire_end(struct ww_acuire_ctx *ctx);

Originally I've thought we could store the pointer to the current acquire ctx in task_struct (since we need that handy for PI boosting anyway), but that makes things a bit ugly with nesting. Having a (somewhat) redundant pointer to the acquiring taks in the ctx seemed less evil.

struct ww_mutex { struct mutex base; struct ww_acquire_ctx *holding_ctx; }

I've considered whether we should try to pull clever tricks like with lockdep keys and make the ww_class more implicit (by auto-instantiating it somewhere and adding a pointer to it in each ww_mutex). But I think we should not hide this complexity, but instead make it explicit.

All the ww_mutex_(un)lock* variants would then also need to take the context instead of the ticket. Besides the usual return codes matching the normal mutex functions we'd have:

-EDEADLK: Deadlock detected (or got kicked by a higher-prio task in RT), drop all currently held locks (of the same class) and block on this lock (since it's the contention point) with ww_mutex_lock_slow.

-EALREADY: Lock already held by the same acquire context. We need this to be able to efficiently yell at evil userspace.

If ww_mutex_lock goes into the slowpath and it's not one of the above cases (i.e. wait, not wound) then it sets the contention flag (unconditionally) and wakes up the current holder iff the current holder is in the TASK_DEADLOCK state.

If ww_mutex_lock gets woken up it checks the contextion flag on the acquire context. If it is set it backs off and returns -EDEADLK. Obviously it also needs to check that before blocking, and we might even want to check unconditionally before attempting any lock operation (to ensure we get out of the way of higher-prio tasks quicker).

One thing we probably need is to make TASK_DEADLOCK a flag, since we still want the different interruptible types of blocking. At least i915 goes to great lengths to make sure that we take every lock which could be held while waiting for the gpu with interruptible sleeps (or at least killable).

Did I miss anything? -Daniel

On Wed, Apr 17, 2013 at 09:08:17PM +0200, Daniel Vetter wrote:

On Wed, Apr 10, 2013 at 12:28 AM, Steven Rostedt rostedt@goodmis.org wrote:

...

On Thu, Apr 04, 2013 at 06:41:02PM +0200, Peter Zijlstra wrote:

...

On Thu, 2013-04-04 at 15:31 +0200, Daniel Vetter wrote:

...

The thing is now that you're not expected to hold these locks for a long time - if you need to synchronously stall while holding a lock performance will go down the gutters anyway. And since most current gpus/co-processors still can't really preempt fairness isn't that high a priority, either. So we didn't think too much about that.

Yeah but you're proposing a new synchronization primitive for the core kernel.. all such 'fun' details need to be considered, not only those few that bear on the one usecase.

Which bares the question, what other use cases are there?

Just stumbled over one I think: If we have a big graph of connected things (happens really often for video pipelines). And we want multiple users to use them in parallel. But sometimes a configuration change could take way too long and so would unduly stall a 2nd thread with just a global mutex, then per-object ww_mutexes would be a fit: You'd start with grabbing all the locks for the objects you want to change anything with, then grab anything in the graph that you also need to check. Thanks to loop detection and self-recursion this would all nicely work out, even for cyclic graphs of objects.

Indeed, that would make the locking for atomic modeset/page flip very easy to handle, while still allowing the use of suitable fine grained locks. I like the idea.