Messages in this thread | | | Subject | Re: [PATCH 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes | From | Thomas Hellstrom <> | Date | Wed, 13 Jun 2018 12:40:29 +0200 |
| |
On 06/13/2018 11:50 AM, Peter Zijlstra wrote: > >> + >> + lockdep_assert_held(&lock->wait_lock); >> + >> + if (owner && hold_ctx && __ww_ctx_stamp_after(hold_ctx, ww_ctx) && >> + ww_ctx->acquired > 0) { >> + WRITE_ONCE(hold_ctx->wounded, true); >> + if (owner != current) { >> + /* >> + * wake_up_process() inserts a write memory barrier to > It does no such thing. But yes, it does ensure the wakee sees all prior > stores IFF the wakeup happened. > >> + * make sure owner sees it is wounded before >> + * TASK_RUNNING in case it's sleeping on another >> + * ww_mutex. Note that owner points to a valid >> + * task_struct as long as we hold the wait_lock. >> + */ > What exactly are you trying to say here ? > > I'm thinking this is the pairing barrier to the smp_mb() below, with > your list_empty() thing? Might make sense to write a single coherent > comment and refer to the other location.
So what I'm trying to say here is that wake_up_process() ensures that the owner, if in !TASK_RUNNING, sees the write to hold_ctx->wounded before the transition to TASK_RUNNING. This was how I interpreted "woken up" in the wake up process documentation.
> >> + wake_up_process(owner); >> + } >> + return true; >> + } >> + >> + return false; >> +} >> + >> /* >> * Wake up any waiters that may have to back off when the lock is held by the >> * given context. >> * >> * Due to the invariants on the wait list, this can only affect the first >> - * waiter with a context. >> + * waiter with a context, unless the Wound-Wait algorithm is used where >> + * also subsequent waiters with a context main wound the lock holder. >> * >> * The current task must not be on the wait list. >> */ >> @@ -303,6 +338,7 @@ static void __sched >> __ww_mutex_wakeup_for_backoff(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) >> { >> struct mutex_waiter *cur; >> + bool is_wait_die = ww_ctx->ww_class->is_wait_die; >> >> lockdep_assert_held(&lock->wait_lock); >> >> @@ -310,13 +346,14 @@ __ww_mutex_wakeup_for_backoff(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) >> if (!cur->ww_ctx) >> continue; >> >> - if (cur->ww_ctx->acquired > 0 && >> + if (is_wait_die && cur->ww_ctx->acquired > 0 && >> __ww_ctx_stamp_after(cur->ww_ctx, ww_ctx)) { >> debug_mutex_wake_waiter(lock, cur); >> wake_up_process(cur->task); >> } >> >> - break; >> + if (is_wait_die || __ww_mutex_wound(lock, cur->ww_ctx, ww_ctx)) >> + break; >> } >> } >> >> @@ -338,12 +375,17 @@ ww_mutex_set_context_fastpath(struct ww_mutex *lock, struct ww_acquire_ctx *ctx) >> * and keep spinning, or it will acquire wait_lock, add itself >> * to waiter list and sleep. >> */ >> - smp_mb(); /* ^^^ */ >> + smp_mb(); /* See comments above and below. */ >> >> /* >> - * Check if lock is contended, if not there is nobody to wake up >> + * Check if lock is contended, if not there is nobody to wake up. >> + * Checking MUTEX_FLAG_WAITERS is not enough here, > That seems like a superfluous thing to say. It makes sense in the > context of this patch because we change the FLAG check into a list > check, but the resulting comment/code looks odd. > >> since we need to >> + * order against the lock->ctx check in __ww_mutex_wound called from >> + * __ww_mutex_add_waiter. We can use list_empty without taking the >> + * wait_lock, given the memory barrier above and the list_empty >> + * documentation. > I don't trust documentation. Please reason about implementation.
Will do.
>> */ >> - if (likely(!(atomic_long_read(&lock->base.owner) & MUTEX_FLAG_WAITERS))) >> + if (likely(list_empty(&lock->base.wait_list))) >> return; >> >> /* >> @@ -653,6 +695,17 @@ __ww_mutex_lock_check_stamp(struct mutex *lock, struct mutex_waiter *waiter, >> struct ww_acquire_ctx *hold_ctx = READ_ONCE(ww->ctx); >> struct mutex_waiter *cur; >> >> + /* >> + * If we miss a wounded == true here, we will have a pending > Explain how we can miss that.
This is actually the pairing location of the wake_up_process() comment / code discussed above. Here we should have !TASK_RUNNING, and let's say ctx->wounded is set by another process immediately after we've read it (we "miss" it). At that point there must be a pending wake-up-process() for us and we'll pick up the set value of wounded on the next iteration after returning from schedule().
> >> + * TASK_RUNNING and pick it up on the next schedule fall-through. >> + */ >> + if (!ctx->ww_class->is_wait_die) { >> + if (READ_ONCE(ctx->wounded)) >> + goto deadlock; >> + else >> + return 0; >> + } >> + >> if (hold_ctx && __ww_ctx_stamp_after(ctx, hold_ctx)) >> goto deadlock; >> >> @@ -683,12 +736,15 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, >> { >> struct mutex_waiter *cur; >> struct list_head *pos; >> + bool is_wait_die; >> >> if (!ww_ctx) { >> list_add_tail(&waiter->list, &lock->wait_list); >> return 0; >> } >> >> + is_wait_die = ww_ctx->ww_class->is_wait_die; >> + >> /* >> * Add the waiter before the first waiter with a higher stamp. >> * Waiters without a context are skipped to avoid starving >> @@ -701,7 +757,7 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, >> >> if (__ww_ctx_stamp_after(ww_ctx, cur->ww_ctx)) { >> /* Back off immediately if necessary. */ >> - if (ww_ctx->acquired > 0) { >> + if (is_wait_die && ww_ctx->acquired > 0) { >> #ifdef CONFIG_DEBUG_MUTEXES >> struct ww_mutex *ww; >> >> @@ -721,13 +777,26 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, >> * Wake up the waiter so that it gets a chance to back >> * off. >> */ >> - if (cur->ww_ctx->acquired > 0) { >> + if (is_wait_die && cur->ww_ctx->acquired > 0) { >> debug_mutex_wake_waiter(lock, cur); >> wake_up_process(cur->task); >> } >> } >> >> list_add_tail(&waiter->list, pos); >> + if (!is_wait_die) { >> + struct ww_mutex *ww = container_of(lock, struct ww_mutex, base); >> + >> + /* >> + * Make sure a racing lock taker sees a non-empty waiting list >> + * before we read ww->ctx, so that if we miss ww->ctx, the >> + * racing lock taker will call __ww_mutex_wake_up_for_backoff() >> + * and wound itself. >> + */ >> + smp_mb(); >> + __ww_mutex_wound(lock, ww_ctx, ww->ctx); >> + } >> + >> return 0; >> } >> >> @@ -750,6 +819,14 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, >> if (use_ww_ctx && ww_ctx) { >> if (unlikely(ww_ctx == READ_ONCE(ww->ctx))) >> return -EALREADY; >> + >> + /* >> + * Reset the wounded flag after a backoff. >> + * No other process can race and wound us here since they >> + * can't have a valid owner pointer at this time >> + */ >> + if (ww_ctx->acquired == 0) >> + ww_ctx->wounded = false; >> } >> >> preempt_disable(); >> @@ -858,6 +935,11 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, >> acquired: >> __set_current_state(TASK_RUNNING); >> >> + /* We stole the lock. Need to check wounded status. */ >> + if (use_ww_ctx && ww_ctx && !ww_ctx->ww_class->is_wait_die && >> + !__mutex_waiter_is_first(lock, &waiter)) >> + __ww_mutex_wakeup_for_backoff(lock, ww_ctx); >> + >> mutex_remove_waiter(lock, &waiter, current); >> if (likely(list_empty(&lock->wait_list))) >> __mutex_clear_flag(lock, MUTEX_FLAGS); > I can't say I'm a fan. I'm already cursing the ww_mutex stuff every time > I have to look at it, and you just made it worse spagethi. > >
Thanks for the review.
Well, I can't speak for the current ww implementation except I didn't think it was too hard to understand for a first time reader.
Admittedly the Wound-Wait path makes it worse since it's a preemptive algorithm and we need to touch other processes a acquire contexts and worry about ordering.
So, assuming your review comments are fixed up, is that a solid NAK or do you have any suggestion that would make you more comfortable with the code? like splitting out ww-stuff to a separate file?
/Thomas
| |