[RFC PATCH 10/12] futex: Optimistic spinning for PING futexes.

[Suleiman Souhlal <suleiman@google.com>]

This allows a thread to spin on the owner of the futex instead of
unconditionally spinning, if the owner is currently running on
another CPU.

TODO: Currently allows every task to attempt to spin at the same time.
In the future, spinning will probably either use an osq or only the
top waiter will be allowed to wait. We've seen some long latencies
when using an osq that we still need to investigate.

Signed-off-by: Suleiman Souhlal <suleiman@google.com>
---
 kernel/futex/ping.c | 80 +++++++++++++++++++++++++++++++++++++--------
 1 file changed, 67 insertions(+), 13 deletions(-)

diff --git a/kernel/futex/ping.c b/kernel/futex/ping.c
index df701b437f16..e5765b2d3834 100644
--- a/kernel/futex/ping.c
+++ b/kernel/futex/ping.c
@@ -301,6 +301,50 @@ static int futex_lock_ping_atomic(u32 __user *uaddr,
 	return attach_to_pi_owner(uaddr, newval, key, ps, exiting, true);
 }
 
+/*
+ * Returns >0 on successfully having taken the lock, <0 on error
+ */
+static int ping_spin_or_trylock(u32 __user *uaddr,
+				struct futex_pi_state *ping_state,
+				bool handoff)
+{
+	struct task_struct *owner = ping_mutex_owner(&ping_state->ping_mutex);
+	struct task_struct *new;
+	int ret;
+
+	if (owner && !owner_on_cpu(owner))
+		return 0;
+
+	/*
+	 * XXX We'll want to try to limit spinning either with an osq or
+	 * by only allowing the top waiter to spin.
+	 */
+
+	while (1) {
+		new = ping_mutex_owner(&ping_state->ping_mutex);
+		ret = 0;
+		if (!owner || !new || new == current) {
+			ret = futex_trylock_ping_state(uaddr, ping_state,
+			    handoff);
+			if (ret != 0)
+				break;
+			/* Spin on new owner if we didn't get the lock */
+			owner = ping_mutex_owner(&ping_state->ping_mutex);
+			goto next;
+		}
+		if (new != owner) {
+			owner = ping_mutex_owner(&ping_state->ping_mutex);
+			goto next;
+		}
+		if (!owner_on_cpu(owner) || need_resched())
+			break;
+next:
+		cpu_relax();
+	}
+
+	return ret;
+}
+
 /*
  * Return values:
  *     < 0: error.
@@ -387,9 +431,6 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
 		queued = false;
 		should_handoff = false;
 		while (1) {
-			set_task_blocked_on(current, &q.ping_state->ping_mutex,
-					    BO_T_PING_FUTEX);
-
 			set_current_state(TASK_INTERRUPTIBLE|TASK_FREEZABLE);
 			if (!queued) {
 				futex_queue(&q, hb, current);
@@ -400,6 +441,26 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
 				__release(q->lock_ptr);
 			}
 
+			preempt_disable();
+			set_current_state(TASK_INTERRUPTIBLE|TASK_FREEZABLE);
+			ret = ping_spin_or_trylock(uaddr, q.ping_state,
+						   should_handoff);
+			if (ret > 0) {
+				/* Got the futex */
+				ret = 0;
+				preempt_enable();
+				futex_q_lockptr_lock(&q);
+				goto out_unqueue;
+			} else if (ret < 0) {
+				preempt_enable();
+				futex_q_lockptr_lock(&q);
+				goto out_unqueue;
+			}
+			preempt_enable();
+
+			set_task_blocked_on(current, &q.ping_state->ping_mutex,
+					    BO_T_PING_FUTEX);
+
 			futex_do_wait(&q, to);
 
 			clear_task_blocked_on(current,
@@ -414,19 +475,12 @@ int futex_lock_ping(u32 __user *uaddr, unsigned int flags, ktime_t *time,
 				ret = -EINTR;
 				goto out_unqueue;
 			}
-
-			ret = futex_trylock_ping_state(uaddr, q.ping_state,
-						       should_handoff);
-			if (ret > 0) {
-				/* Got the futex */
-				ret = 0;
-				goto out_unqueue;
-			} else if (ret < 0)
-				goto out_unqueue;
 			should_handoff = true;
 		}
 
 out_unqueue:
+		__set_current_state(TASK_RUNNING);
+
 		/*
 		 * We got a pending signal or timeout, but the futex was handed
 		 * off to us. Fix up the return value to indicate success.
@@ -581,7 +635,7 @@ int futex_unlock_ping(u32 __user *uaddr, unsigned int flags)
 	 * no top_waiter.
 	 */
 	new = FUTEX_WAITERS;
-	if (ping_state->handoff) {
+	if (ping_state->handoff) { /* Don't handoff to donor */
 		new |= task_pid_vnr(next);
 		ping_state->handoff = 0;
 		ping_state->pickup = 1;
-- 
2.55.0.1082.g2b9226bbc0-goog