It turns out that the deadlock that I found last week was already implicitly fixed during the lock->owner redesign, by checking the WAITERS bit in the w/w lock fast path. However, since I had already started looking into sorting the wait list, here goes.
The basic idea is to make sure that: 1. All waiters that have a ww_ctx appear in stamp order in the wait list. Waiters without a ww_ctx are still supported and appear in FIFO order as before. 2. At most one of the waiters can be in a state where it has to check for back off (i.e., ww_ctx->acquire > 0). Technically, there are short time windows in which more than one such waiter can be on the list, but all but the first one are running. This happens when a new waiter with ww_ctx->acquire > 0 adds itself at the front of the list and wakes up the previous head of the list, and of course multiple such chained cases can be in-flight simultaneously. Then we only ever have to wake up one task at a time. This is _not_ always the head of the wait list, since there may be waiters without a context. But among waiters with a context, we only ever have to wake the first one. To achieve all this, the series adds a new field to mutex_waiter which is only used for the w/w lock case. As a consequence, calling mutex_lock directly on w/w locks is now definitely incorrect. That was likely the intention previously anyway, but grepping through the source I did find one place that had slipped through. I've included timings taken from a contention-heavy stress test to some of the patches. The stress test performs actual GPU operations which take a good chunk of the wall time, but even so, the series still manages to improve the wall time quite a bit. Cheers, Nicolai