Re: [PATCH 1/2] locking: Implement an algorithm choice for Wound-Wait mutexes

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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





[Index of Archives]     [Linux Input]     [Video for Linux]     [Gstreamer Embedded]     [Mplayer Users]     [Linux USB Devel]     [Linux Audio Users]     [Linux Kernel]     [Linux SCSI]     [Yosemite Backpacking]

  Powered by Linux