futex: Introducing throughput-optimized futexes

v1->v2:
- Adds an explicit lock hand-off mechanism.
- Adds timeout support.
- Simplifies the required userspace code.
- Fixes a number of problems in the v1 code.

This patchset introduces a new futex implementation called throughput-optimized (TO) futexes. It is similar to PI futexes in its calling convention, but provides better throughput than the wait-wake futexes by encouraging lock stealing and optimistic spinning.

Waiman Long (5):
futex: Add futex_set_timer() helper function
futex: Rename futex_pi_state to futex_state
futex: Throughput-optimized (TO) futexes
futex: Add timeout support to TO futexes
futex, doc: TO futexes document

 Documentation/00-INDEX     |    2 +
 Documentation/to-futex.txt |  140 ++++++++
 include/linux/sched.h      |    4 +-
 include/uapi/linux/futex.h |    4 +
 kernel/futex.c             |  810 +++++++++++++++++++++++++++++++++++++++-----
 5 files changed, 869 insertions(+), 91 deletions(-)
 create mode 100644 Documentation/to-futex.txt

This patch adds a new futex_set_timer() function to consolidate all the sleeping hrtime setup code.

---
 kernel/futex.c |   51 ++++++++++++++++++++++++---------------------------
 1 files changed, 24 insertions(+), 27 deletions(-)

index 46cb3a3..37e61ef 100644
@@ -467,6 +467,25 @@ static void drop_futex_key_refs(union futex_key *key)
 	}
 }
 
+/*
+ * Helper function to set the sleeping hrtimer.
+ */
+static inline void futex_set_timer(ktime_t *time, struct hrtimer_sleeper **pto,
+		struct hrtimer_sleeper *timeout, int flags, u64 range_ns)
+{
+	if (!time)
+		return;
+	*pto = timeout;
+	hrtimer_init_on_stack(&timeout->timer, (flags & FLAGS_CLOCKRT) ?
+			      CLOCK_REALTIME : CLOCK_MONOTONIC,
+			      HRTIMER_MODE_ABS);
+	hrtimer_init_sleeper(timeout, current);
+	if (range_ns)
+		hrtimer_set_expires_range_ns(&timeout->timer, *time, range_ns);
+	else
+		hrtimer_set_expires(&timeout->timer, *time);
+}
+
 /**
  * get_futex_key() - Get parameters which are the keys for a futex
  * @uaddr:	virtual address of the futex

@@ -2403,17 +2422,8 @@ static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
 		return -EINVAL;
 	q.bitset = bitset;
 
-	if (abs_time) {
-		to = &timeout;
-
-		hrtimer_init_on_stack(&to->timer, (flags & FLAGS_CLOCKRT) ?
-				      CLOCK_REALTIME : CLOCK_MONOTONIC,
-				      HRTIMER_MODE_ABS);
-		hrtimer_init_sleeper(to, current);
-		hrtimer_set_expires_range_ns(&to->timer, *abs_time,
-					     current->timer_slack_ns);
-	}
-
+	futex_set_timer(abs_time, &to, &timeout, flags,
+			current->timer_slack_ns);
 retry:
 	/*
 	 * Prepare to wait on uaddr. On success, holds hb lock and increments

@@ -2501,13 +2511,7 @@ static int futex_lock_pi(u32 __user *uaddr, unsigned int flags,
 	if (refill_pi_state_cache())
 		return -ENOMEM;
 
-	if (time) {
-		to = &timeout;
-		hrtimer_init_on_stack(&to->timer, CLOCK_REALTIME,
-				      HRTIMER_MODE_ABS);
-		hrtimer_init_sleeper(to, current);
-		hrtimer_set_expires(&to->timer, *time);
-	}
+	futex_set_timer(time, &to, &timeout, FLAGS_CLOCKRT, 0);
 
 retry:
 	ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q.key, VERIFY_WRITE);

@@ -2816,15 +2820,8 @@ static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
 	if (!bitset)
 		return -EINVAL;
 
-	if (abs_time) {
-		to = &timeout;
-		hrtimer_init_on_stack(&to->timer, (flags & FLAGS_CLOCKRT) ?
-				      CLOCK_REALTIME : CLOCK_MONOTONIC,
-				      HRTIMER_MODE_ABS);
-		hrtimer_init_sleeper(to, current);
-		hrtimer_set_expires_range_ns(&to->timer, *abs_time,
-					     current->timer_slack_ns);
-	}
+	futex_set_timer(abs_time, &to, &timeout, flags,
+			current->timer_slack_ns);
 
 	/*
 	 * The waiter is allocated on our stack, manipulated by the requeue

1.7.1

On Tue, 20 Sep 2016, Waiman Long wrote:

Please be more careful of your subject lines. First thing I thought was that you add a helper which is used in later patches to find out that you actualy consolidate duplicated code. Something like:

futex: Consolidate duplicated timer setup code

would have told me right away what this is about.

Please do not use: "This patch ...". We already know that this is a patch, otherwise it would not be tagged [PATCH n/m] in the subject line.

See Documentation/SubmittingPatches ....

Let me give you a hint:

1: The code has three identical code copies to set up the futex timeout.

2: Add a helper function and consolidate the call sites.

#1 tells precisely what the problem is
#2 tells precisely how it is solved

Can you see the difference?

Thanks for the suggestions. I will fix this patch in the next revision.

Cheers,
Longman

The futex_pi_state structure will be overloaded in later patches to store state information about non-PI futexes. So the structure name itself is no longer a good description of its purpose. This patch renames it to futex_state, a more generic name.

Some of the functions that process the futex states are also renamed.

---
 include/linux/sched.h |    4 +-
 kernel/futex.c        |  107 +++++++++++++++++++++++++------------------------
 2 files changed, 56 insertions(+), 55 deletions(-)

index 62c68e5..fefd7f7 100644
@@ -126,7 +126,7 @@ struct sched_attr {
 	u64 sched_period;
 };
 
-struct futex_pi_state;
+struct futex_state;
 struct robust_list_head;
 struct bio_list;
 struct fs_struct;

@@ -1772,7 +1772,7 @@ struct task_struct {
 	struct compat_robust_list_head __user *compat_robust_list;
 #endif
 	struct list_head pi_state_list;
-	struct futex_pi_state *pi_state_cache;
+	struct futex_state *pi_state_cache;
 #endif
 #ifdef CONFIG_PERF_EVENTS
 	struct perf_event_context *perf_event_ctxp[perf_nr_task_contexts];

1.7.1

This patch introduces a new futex implementation called throughput-optimized (TO) futexes. The goal of this new futex type is to maximize locking throughput at the expense of fairness and deterministic latency. Its throughput is higher than that of the wait-wake futexes especially on systems with a large number of CPUs and the lock owners are unlikely to sleep. The downside is the increase in the response time variance. It also implements a lock hand-off mechanism to make sure that lock starvation won't happen.

Using a futex locking microbenchmark to do 10 millions locking operations with 5 pause instructions as the critical section by 256 threads (10M/256 locking ops each) on a 4-socket 72-core 144-thread Haswell-EX system, the results of the benchmark runs were as follows:

                wait-wake futex     PI futex        TO futex
                ---------------     --------        --------
max time            3.49s            50.91s          2.65s
min time            3.24s            50.84s          0.07s
average time        3.41s            50.90s          1.84s
sys time	  7m22.4s            55.73s        2m32.9s
lock count       3,090,294          9,999,813       698,318
unlock count     3,268,896          9,999,814           134

The lock and unlock counts above show the actual numbers of futex(2) lock and unlock syscalls that were being issued.

---
 include/uapi/linux/futex.h |    4 +
 kernel/futex.c             |  634 +++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 627 insertions(+), 11 deletions(-)

index 0b1f716..e7deaf3 100644
@@ -20,6 +20,8 @@
 #define FUTEX_WAKE_BITSET	10
 #define FUTEX_WAIT_REQUEUE_PI	11
 #define FUTEX_CMP_REQUEUE_PI	12
+#define FUTEX_LOCK_TO		13
+#define FUTEX_UNLOCK_TO		14
 
 #define FUTEX_PRIVATE_FLAG	128
 #define FUTEX_CLOCK_REALTIME	256

@@ -39,6 +41,8 @@
 					 FUTEX_PRIVATE_FLAG)
 #define FUTEX_CMP_REQUEUE_PI_PRIVATE	(FUTEX_CMP_REQUEUE_PI | \
 					 FUTEX_PRIVATE_FLAG)
+#define FUTEX_LOCK_TO_PRIVATE	(FUTEX_LOCK_TO | FUTEX_PRIVATE_FLAG)
+#define FUTEX_UNLOCK_TO_PRIVATE	(FUTEX_UNLOCK_TO | FUTEX_PRIVATE_FLAG)
 
 /*
  * Support for robust futexes: the kernel cleans up held futexes at

1.7.1

nit: 'TO' sounds way too much like timeout... TP? You even use 'to' as shorthand for timeout in the next patch.

nit: comment attracted my eye during high speed scroll-by.

-Mike

I agree. I am not that satisfied with the TO name. So I will change it to TP in my next revision of the patch. Thanks for the suggestion.

Cheers,
Longman

I'd leave out the TO part entirely (or only mention it in changelogs).

That is, I'd call the futex ops: FUTEX_LOCK and FUTEX_UNLOCK.

I was following the convention for the PI futexes where we have FUTEX_LOCK_PI and FUTEX_UNLOCK_PI. If you think it is OK to promote this new futex as default for mutex type locks and use the PI futexes only when needed, I am certainly OK to drop the suffix.

Cheers,
Longman

That brings me to a different question:

How is user space going to support this, i.e. is this some extra magic for code which implements its own locking primitives or is there going to be a wide use via e.g. glibc.

Also what's the reason that we can't do probabilistic spinning for FUTEX_WAIT and have to add yet another specialized variant of futexes?

Thanks,

tglx

Where would this leave the respective FUTEX_WAKE? A nop? Probably have to differentiate the fact that the queue was empty, but there was a spinning, instead of straightforward returning 0.

Thanks,
Davidlohr

Sorry, but I really can't parse this answer.

Can you folks please communicate with proper and coherent explanations instead of throwing a few gnawed off bones in my direction?

Thanks,

tglx

I actually think that FUTEX_WAIT is the better/nicer approach. But my immediate question above was how to handle the FUTEX_WAKE counter-part. If we want to maintain current FIFO ordering for wakeups, now with WAIT spinners this will create lock stealing scenarios (including if we even guard against starvation). Or we could reduce the scope of spinners, due to the restrictions, similar to the top-waiter only being able to spin for rtmutexes. This of course will hurt the effectiveness of spinning in FUTEX_WAIT in the first place.

Another immediate thought was situations where we spinner(s) and the wait queue is empty, the WAKE should also have to acknowledge that situation, as just returning 0 would indicate that there are actually no waiters on the futex.

Thanks,
Davidlohr

Actually, there can be a lot of lock stealing going on with the wait-wake futexes. If the critical section is short enough, many of the lock waiters can be waiting in the hash bucket spinlock queue and not sleeping yet while the futex value changes. As a result, they will exit the futex syscall and back to user space with EAGAIN where one of them may get the lock. So we can't assume that they will get the lock in the FIFO order anyway.

I would say that adding optimistic spinning to FUTEX_WAIT will be a major change and I don't think it will be less complex than adding a new futex type like the TO futexes while introducing a fair amount of risk of breaking existing applications.

Cheers,
Longman

BTW, my initial attempt for the new futex was to use the same workflow as the PI futexes, but use mutex which has optimistic spinning instead of rt_mutex. That version can double the throughput compared with PI futexes but still far short of what can be achieved with wait-wake futex. Looking at the performance figures from the patch:

                wait-wake futex     PI futex        TO futex
                ---------------     --------        --------
max time            3.49s            50.91s          2.65s
min time            3.24s            50.84s          0.07s
average time        3.41s            50.90s          1.84s
sys time          7m22.4s            55.73s        2m32.9s
lock count       3,090,294          9,999,813       698,318
unlock count     3,268,896          9,999,814           134

The problem with a PI futexes like version is that almost all the lock/unlock operations were done in the kernel which added overhead and latency. Now looking at the numbers for the TO futexes, less than 1/10 of the lock operations were done in the kernel, the number of unlock was insignificant. Locking was done mostly by lock stealing. This is where most of the performance benefit comes from, not optimistic spinning.

This is also the reason that a lock handoff mechanism is implemented to prevent lock starvation which is likely to happen without one.

Cheers,
Longman

That's really interesting. Do you have any explanation for this massive system time differences?

How does the lock latency distribution of all this look like and how fair is the whole thing?

Where is that lock handoff mechanism?

Thanks,

tglx

For the wait-wake futexes, the waiters will be kicked out with EAGAIN without sleeping as long as the futex value changes before they acquire the hash bucket spinlock. These waiters will attempt to acquire the lock again in the user space. If that fails, they will call FUTEX_WAIT again.

In the above test case, the critical section is pretty short and about 4/5 of the FUTEX_WAIT calls resulted in an EAGAIN error. So there are a lot more user-space/kernel transitions than the TO futexes. I think the difference in the number of FUTEX_WAIT calls vs. the FUTEX_LOCK_TO calls causes the difference between their sys times. As for the PI futex, it is a strictly sleeping lock and so won't use that much sys time.

The TO futexes are unfair as can be seen from the min/max thread times listed above. It took the fastest thread 0.07s to complete all the locking operations, whereas the slowest one needed 2.65s. However, the situation reverses when I changed the critical section to a 1us sleep. In this case, there will be no optimistic spinning. The performance results for 100k locking operations were listed below.

                wait-wake futex     PI futex        TO futex
                ---------------     --------        --------
max time            0.06s             9.32s          4.76s
min time            5.59s             9.36s          5.62s
average time        3.25s             9.35s          5.41s

In this case, the TO futexes are fairer but perform worse than the wait-wake futexes. That is because the lock handoff mechanism limit the amount of lock stealing in the TO futexes while the wait-wake futexes have no such restriction. When I disabled lock handoff, the TO futexes would then perform similar to the wait-wake futexes.

In the futex_state object, there is a new field handoff_pid. It is set when the threshold count in futex_spin_on_owner() becomes negative When this field is set, the unlocker will change the futex word to that value instead of clearing it to 0 and others can steal it. I will separate out the lock handoff in a separate patch in the next revision to highlight it.

Cheers,
Longman

Ok.

That's clear.

1us sleep is going to add another syscall and therefor scheduling, so what?

Or did you just extend the critical section busy time?

      		      ^^^^ ????			

So the benefit of these new fangled futexes is only there for extreme short critical sections and a gazillion of threads fighting for the same futex, right?

I really wonder how the average programmer should pick the right flavour, not to talk about any useful decision for something like glibc to pick the proper one.

Thanks,

tglx

The 1us sleep will cause the spinning to stop and make all the waiters sleep. This is to simulate the extreme case where TO futex may not have the performance advantage.

Yes, wait-wake futex is the unfair one in this case.

Not really. Lock stealing will help performance when a gazillion of threads fighting for the same futex. Optimistic spinning will help to reduce the lock transfer latency because the waiter isn't sleeping no matter the number of threads. One set of data that I haven't shown so far is that the performance delta between wait-wait and TO futexes actually increases as the critical section is lengthened. This is because for short critical section, the waiters of wait-wake futex may not actually go to sleep because of the latency introduced by the code that has to be run before they do a final check to see if the futex value change before going to sleep. The longer the critical section, the higher the chance that they actually sleep and hence their performance is getting worse relative to the TO futexes.

For example, with the critical section of 50 pause instructions instead of 5, the performance gain is about 5X instead of about 1.6X in the latter case.

I would say that TO futexes will have better performance in most cases. Of course, I still need to run some real world benchmarks to quantify the effect of the new futexes. I am hoping to get suggestion of what is a good set of benchmarks to run.

Cheers,
Longman

Btw, Thomas, do you still have any interest pursuing this for rtmutexes from -rt into mainline? If so I can resend the patches from a while ago.

Thanks,
Davidlohr

Certainly yes. My faint memory tells me that there was some potential issue due to boosting the owner only if it gets scheduled out, but I might be wrong.

Thanks,

tglx

It is tricky to add optimistic spinning to rtmutexes because of the need to observe process priorities. It is certainly possible to make the top waiter spin, but then I am not sure how much performance gain with just that.

Cheers,
Longman

By applying well known spin-on-lock-owner techniques, we can avoid the blocking overhead during the process of when the task is trying to take the rtmutex. The idea is that as long as the owner is running, there is a fair chance it'll release the lock soon, and thus a task trying to acquire the rtmutex will better off spinning instead of blocking immediately after the fastpath. This is similar to what we use for other locks, borrowed from -rt. The main difference (due to the obvious real-time constraints) is that top-waiter spinning must account for any new higher priority waiter, and therefore cannot steal the lock and avoid any pi-dance. As such there will be at most only one spinner waiter upon contended lock.

Conditions to stop spinning and block are simple:

(1) Upon need_resched()
(2) Current lock owner blocks
(3) We are no longer the top-waiter

The unlock side remains unchanged as wake_up_process() can safely deal with calls where the task is not actually blocked (TASK_NORMAL). The biggest concern would perhaps be if we relied on any implicit barriers (in that the wake_up_process call would not imply it anymore since nothing was awoken), but this is not the case. As such, there is only unnecessary overhead dealing with the wake_q, but this allows us not to miss any wakeups between the spinning step and the unlocking side.

Measuring the amount of priority inversions of the pi_stress program, there is some improvement in throughput during a 30 second window. On a 32-core box, with increasing thread-group count:

pistress

			    4.4.3                 4.4.3
			  vanilla           rtmutex-topspinner
Hmean    1   2321586.73 (  0.00%)  2339847.23 (  0.79%)
Hmean    4   8209026.49 (  0.00%)  8597809.55 (  4.74%)
Hmean    7  12655322.45 (  0.00%) 13194896.45 (  4.26%)
Hmean    12  4210477.03 (  0.00%)  4348643.08 (  3.28%)
Hmean    21  2996823.05 (  0.00%)  3104513.47 (  3.59%)
Hmean    30  2463107.53 (  0.00%)  2584275.71 (  4.91%)
Hmean    48  2656668.46 (  0.00%)  2719324.53 (  2.36%)
Hmean    64  2397253.65 (  0.00%)  2471628.92 (  3.10%)
Stddev   1    653473.88 (  0.00%)   527076.59 (-19.34%)
Stddev   4    664995.50 (  0.00%)   359487.15 (-45.94%)
Stddev   7    248476.88 (  0.00%)   278307.31 ( 12.01%)
Stddev   12    74537.42 (  0.00%)    54305.86 (-27.14%)
Stddev   21    72143.80 (  0.00%)    40371.42 (-44.04%)
Stddev   30    31981.43 (  0.00%)    42306.07 ( 32.28%)
Stddev   48    21317.95 (  0.00%)    42608.50 ( 99.87%)
Stddev   64    23433.99 (  0.00%)    21502.56 ( -8.24%)

---

Changes from v1: Stop spinning and block if we are no longer the top-waiter for the lock. This also prevents having more than one spinner at a time, as the old waiter would otherwise still think its next in line for the lock.

kernel/Kconfig.locks            |  4 ++
kernel/locking/rtmutex.c        | 92 ++++++++++++++++++++++++++++++++++-------
kernel/locking/rtmutex_common.h |  4 +-
3 files changed, 82 insertions(+), 18 deletions(-)

index ebdb0043203a..e20790cdc446 100644
@@ -227,6 +227,10 @@ config MUTEX_SPIN_ON_OWNER

	def_bool y
	depends on SMP && !DEBUG_MUTEXES && ARCH_SUPPORTS_ATOMIC_RMW

+config RT_MUTEX_SPIN_ON_OWNER
+ def_bool y
+ depends on SMP && RT_MUTEXES && !DEBUG_RT_MUTEXES && ARCH_SUPPORTS_ATOMIC_RMW
+
config RWSEM_SPIN_ON_OWNER

       def_bool y
       depends on SMP && RWSEM_XCHGADD_ALGORITHM && ARCH_SUPPORTS_ATOMIC_RMW

index 1ec0f48962b3..a789528172c2 100644
@@ -54,13 +54,13 @@ rt_mutex_set_owner(struct rt_mutex *lock, struct task_struct *owner)

	if (rt_mutex_has_waiters(lock))
		val |= RT_MUTEX_HAS_WAITERS;

- lock->owner = (struct task_struct *)val;
+ WRITE_ONCE(lock->owner, (struct task_struct *)val);
}

static inline void clear_rt_mutex_waiters(struct rt_mutex *lock) {
- lock->owner = (struct task_struct *)
- ((unsigned long)lock->owner & ~RT_MUTEX_HAS_WAITERS);
+ WRITE_ONCE(lock->owner, (struct task_struct *)
+ ((unsigned long)lock->owner & ~RT_MUTEX_HAS_WAITERS));
}

static void fixup_rt_mutex_waiters(struct rt_mutex *lock)
@@ -198,7 +198,7 @@ rt_mutex_enqueue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter)

	}

	if (leftmost)

- lock->waiters_leftmost = &waiter->tree_entry;
+ WRITE_ONCE(lock->waiters_leftmost, &waiter->tree_entry);

	rb_link_node(&waiter->tree_entry, parent, link);
	rb_insert_color(&waiter->tree_entry, &lock->waiters);
@@ -210,8 +210,8 @@ rt_mutex_dequeue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter)
	if (RB_EMPTY_NODE(&waiter->tree_entry))
		return;

- if (lock->waiters_leftmost == &waiter->tree_entry)
- lock->waiters_leftmost = rb_next(&waiter->tree_entry);
+ if (READ_ONCE(lock->waiters_leftmost) == &waiter->tree_entry)
+ WRITE_ONCE(lock->waiters_leftmost, rb_next(&waiter->tree_entry));

	rb_erase(&waiter->tree_entry, &lock->waiters);
	RB_CLEAR_NODE(&waiter->tree_entry);
@@ -989,14 +989,17 @@ static void mark_wakeup_next_waiter(struct wake_q_head *wake_q,
	rt_mutex_dequeue_pi(current, waiter);

	/*

- * As we are waking up the top waiter, and the waiter stays
- * queued on the lock until it gets the lock, this lock
- * obviously has waiters. Just set the bit here and this has
- * the added benefit of forcing all new tasks into the
- * slow path making sure no task of lower priority than
- * the top waiter can steal this lock.
+ * As we are potentially waking up the top waiter, and the waiter
+ * stays queued on the lock until it gets the lock, this lock
+ * obviously has waiters. Just set the bit here and this has the
+ * added benefit of forcing all new tasks into the slow path
+ * making sure no task of lower priority than the top waiter can
+ * steal this lock.
+ *
+ * If the top waiter, otoh, is spinning on ->owner, this will also
+ * serve to exit out of the loop and try to acquire the lock.

	 */

- lock->owner = (void *) RT_MUTEX_HAS_WAITERS;
+ WRITE_ONCE(lock->owner, (void *) RT_MUTEX_HAS_WAITERS);

	raw_spin_unlock(&current->pi_lock);

@@ -1089,6 +1092,51 @@ void rt_mutex_adjust_pi(struct task_struct *task)

				   next_lock, NULL, task);
}

+#ifdef CONFIG_RT_MUTEX_SPIN_ON_OWNER
+static bool rt_mutex_spin_on_owner(struct rt_mutex *lock,
+ struct task_struct *owner,
+ struct rt_mutex_waiter *waiter)
+{
+ bool ret = true;
+
+ /*
+ * The last owner could have just released the lock,
+ * immediately try taking it again.
+ */
+ if (!owner)
+ goto done;
+
+ rcu_read_lock();
+ while (rt_mutex_owner(lock) == owner) {
+ /*
+ * Ensure we emit the owner->on_cpu, dereference _after_
+ * checking lock->owner still matches owner. If that fails,
+ * owner might point to freed memory. If it still matches,
+ * the rcu_read_lock() ensures the memory stays valid.
+ */
+ barrier();
+ if (!owner->on_cpu || need_resched() ||
+ rt_mutex_top_waiter(lock) != waiter) {
+ ret = false;
+ break;
+ }
+
+ cpu_relax_lowlatency();
+ }
+ rcu_read_unlock();
+done:
+ return ret;
+}
+
+#else
+static bool rt_mutex_spin_on_owner(struct rt_mutex *lock,
+ struct task_struct *owner,
+ struct rt_mutex_waiter *waiter)
+{
+ return false;
+}
+#endif
+
/**
* __rt_mutex_slowlock() - Perform the wait-wake-try-to-take loop
* @lock: the rt_mutex to take
@@ -1107,6 +1155,8 @@ __rt_mutex_slowlock(struct rt_mutex *lock, int state,

	int ret = 0;

	for (;;) {
+		struct rt_mutex_waiter *top_waiter = NULL;
+
		/* Try to acquire the lock: */
		if (try_to_take_rt_mutex(lock, current, waiter))
			break;
@@ -1125,11 +1175,21 @@ __rt_mutex_slowlock(struct rt_mutex *lock, int state,
				break;
		}

+ top_waiter = rt_mutex_top_waiter(lock);
+

		raw_spin_unlock_irq(&lock->wait_lock);

		debug_rt_mutex_print_deadlock(waiter);

- schedule();
+ /*
+ * At this point the PI-dance is done, and, as the top waiter,
+ * we are next in line for the lock. Try to spin on the current
+ * owner for a while, in the hope that the lock will be released
+ * soon. Otherwise fallback and block.
+ */
+ if (top_waiter != waiter ||
+ !rt_mutex_spin_on_owner(lock, rt_mutex_owner(lock), waiter))
+ schedule();

		raw_spin_lock_irq(&lock->wait_lock);
		set_current_state(state);

@@ -1555,7 +1615,7 @@ EXPORT_SYMBOL_GPL(__rt_mutex_init);
* rt_mutex_init_proxy_locked - initialize and lock a rt_mutex on behalf of a
* proxy owner
*
- * @lock: the rt_mutex to be locked
+ * @lock: the rt_mutex to be locked
* @proxy_owner:the task to set as owner
*
* No locking. Caller has to do serializing itself
@@ -1573,7 +1633,7 @@ void rt_mutex_init_proxy_locked(struct rt_mutex *lock, /**
* rt_mutex_proxy_unlock - release a lock on behalf of owner
*
- * @lock: the rt_mutex to be locked
+ * @lock: the rt_mutex to be locked
*
* No locking. Caller has to do serializing itself
* Special API call for PI-futex support

index 4f5f83c7d2d3..dc80fce3b407 100644
@@ -48,7 +48,7 @@ rt_mutex_top_waiter(struct rt_mutex *lock)

{
	struct rt_mutex_waiter *w;

- w = rb_entry(lock->waiters_leftmost, struct rt_mutex_waiter,
+ w = rb_entry(READ_ONCE(lock->waiters_leftmost), struct rt_mutex_waiter,

		     tree_entry);
	BUG_ON(w->lock != lock);

@@ -76,7 +76,7 @@ task_top_pi_waiter(struct task_struct *p) static inline struct task_struct *rt_mutex_owner(struct rt_mutex *lock) {
return (struct task_struct *)
- ((unsigned long)lock->owner & ~RT_MUTEX_OWNER_MASKALL);
+ ((unsigned long)READ_ONCE(lock->owner) & ~RT_MUTEX_OWNER_MASKALL);
}

/*

2.6.6

Any comments? can this make it for v4.10?

Thanks,
Davidlohr

We need to fry the futex/rtmutex fish first....

By applying well known spin-on-lock-owner techniques, we can avoid the blocking overhead during the process of when the task is trying to take the rtmutex. The idea is that as long as the owner is running, there is a fair chance it'll release the lock soon, and thus a task trying to acquire the rtmutex will better off spinning instead of blocking immediately after the fastpath. This is similar to what we use for other locks, borrowed from -rt. The main difference (due to the obvious real-time constraints) is that top-waiter spinning must account for any new higher priority waiter, and therefore cannot steal the lock and avoid any pi-dance. As such there will be at most only one spinner waiter upon contended lock.

Conditions to stop spinning and block are simple:

(1) Upon need_resched()
(2) Current lock owner blocks

The unlock side remains unchanged as wake_up_process() can safely deal with calls where the task is not actually blocked (TASK_NORMAL). The biggest concern would perhaps be if we relied on any implicit barriers (in that the wake_up_process call would not imply it anymore since nothing was awoken), but this is not the case. As such, there is only unnecessary overhead dealing with the wake_q, but this allows us not to miss any wakeups between the spinning step and the unlocking side.

Measuring the amount of priority inversions of the pi_stress program, there is some improvement in throughput during a 30 second window. On a 32-core box, with increasing thread-group count:

pistress

			    4.4.3                 4.4.3
			  vanilla           rtmutex-topspinner
Hmean    1   2321586.73 (  0.00%)  2339847.23 (  0.79%)
Hmean    4   8209026.49 (  0.00%)  8597809.55 (  4.74%)
Hmean    7  12655322.45 (  0.00%) 13194896.45 (  4.26%)
Hmean    12  4210477.03 (  0.00%)  4348643.08 (  3.28%)
Hmean    21  2996823.05 (  0.00%)  3104513.47 (  3.59%)
Hmean    30  2463107.53 (  0.00%)  2584275.71 (  4.91%)
Hmean    48  2656668.46 (  0.00%)  2719324.53 (  2.36%)
Hmean    64  2397253.65 (  0.00%)  2471628.92 (  3.10%)
Stddev   1    653473.88 (  0.00%)   527076.59 (-19.34%)
Stddev   4    664995.50 (  0.00%)   359487.15 (-45.94%)
Stddev   7    248476.88 (  0.00%)   278307.31 ( 12.01%)
Stddev   12    74537.42 (  0.00%)    54305.86 (-27.14%)
Stddev   21    72143.80 (  0.00%)    40371.42 (-44.04%)
Stddev   30    31981.43 (  0.00%)    42306.07 ( 32.28%)
Stddev   48    21317.95 (  0.00%)    42608.50 ( 99.87%)
Stddev   64    23433.99 (  0.00%)    21502.56 ( -8.24%)

---

Hi, so I've rebased the patch against -tip, and has survived about a full day
of pistress pounding. That said, I don't have any interesting boxes available for performance tests, so I'm keeping the results I obtained originally; which should obviously not matter. The other difference from the previous post was that
I've sprinkled READ/WRITE_ONCE around lock->owner, as now we're playing with it
without the wait_lock.

kernel/Kconfig.locks            |  4 ++
kernel/locking/rtmutex.c        | 83 ++++++++++++++++++++++++++++++++++-------
kernel/locking/rtmutex_common.h |  2 +-
3 files changed, 75 insertions(+), 14 deletions(-)

index ebdb0043203a..e20790cdc446 100644
@@ -227,6 +227,10 @@ config MUTEX_SPIN_ON_OWNER

	def_bool y
	depends on SMP && !DEBUG_MUTEXES && ARCH_SUPPORTS_ATOMIC_RMW

+config RT_MUTEX_SPIN_ON_OWNER
+ def_bool y
+ depends on SMP && RT_MUTEXES && !DEBUG_RT_MUTEXES && ARCH_SUPPORTS_ATOMIC_RMW
+
config RWSEM_SPIN_ON_OWNER

       def_bool y
       depends on SMP && RWSEM_XCHGADD_ALGORITHM && ARCH_SUPPORTS_ATOMIC_RMW

index 1ec0f48962b3..282a773d1563 100644
@@ -54,13 +54,13 @@ rt_mutex_set_owner(struct rt_mutex *lock, struct task_struct *owner)

	if (rt_mutex_has_waiters(lock))
		val |= RT_MUTEX_HAS_WAITERS;

- lock->owner = (struct task_struct *)val;
+ WRITE_ONCE(lock->owner, (struct task_struct *)val);
}

static inline void clear_rt_mutex_waiters(struct rt_mutex *lock) {
- lock->owner = (struct task_struct *)
- ((unsigned long)lock->owner & ~RT_MUTEX_HAS_WAITERS);
+ WRITE_ONCE(lock->owner, (struct task_struct *)
+ ((unsigned long)lock->owner & ~RT_MUTEX_HAS_WAITERS));
}

static void fixup_rt_mutex_waiters(struct rt_mutex *lock)
@@ -989,14 +989,17 @@ static void mark_wakeup_next_waiter(struct wake_q_head *wake_q,

	rt_mutex_dequeue_pi(current, waiter);

	/*

- * As we are waking up the top waiter, and the waiter stays
- * queued on the lock until it gets the lock, this lock
- * obviously has waiters. Just set the bit here and this has
- * the added benefit of forcing all new tasks into the
- * slow path making sure no task of lower priority than
- * the top waiter can steal this lock.
+ * As we are potentially waking up the top waiter, and the waiter
+ * stays queued on the lock until it gets the lock, this lock
+ * obviously has waiters. Just set the bit here and this has the
+ * added benefit of forcing all new tasks into the slow path
+ * making sure no task of lower priority than the top waiter can
+ * steal this lock.
+ *
+ * If the top waiter, otoh, is spinning on ->owner, this will also
+ * serve to exit out of the loop and try to acquire the lock.

	 */

- lock->owner = (void *) RT_MUTEX_HAS_WAITERS;
+ WRITE_ONCE(lock->owner, (void *) RT_MUTEX_HAS_WAITERS);

	raw_spin_unlock(&current->pi_lock);

@@ -1089,6 +1092,48 @@ void rt_mutex_adjust_pi(struct task_struct *task)

				   next_lock, NULL, task);
}

+#ifdef CONFIG_RT_MUTEX_SPIN_ON_OWNER
+static bool rt_mutex_spin_on_owner(struct rt_mutex *lock,
+ struct task_struct *owner)
+{
+ bool ret = true;
+
+ /*
+ * The last owner could have just released the lock,
+ * immediately try taking it again.
+ */
+ if (!owner)
+ goto done;
+
+ rcu_read_lock();
+ while (rt_mutex_owner(lock) == owner) {
+ /*
+ * Ensure we emit the owner->on_cpu, dereference _after_
+ * checking lock->owner still matches owner. If that fails,
+ * owner might point to freed memory. If it still matches,
+ * the rcu_read_lock() ensures the memory stays valid.
+ */
+ barrier();
+ if (!owner->on_cpu || need_resched()) {
+ ret = false;
+ break;
+ }
+
+ cpu_relax_lowlatency();
+ }
+ rcu_read_unlock();
+done:
+ return ret;
+}
+
+#else
+static bool rt_mutex_spin_on_owner(struct rt_mutex *lock,
+ struct task_struct *owner)
+{
+ return false;
+}
+#endif
+
/**
* __rt_mutex_slowlock() - Perform the wait-wake-try-to-take loop
* @lock: the rt_mutex to take
@@ -1107,6 +1152,8 @@ __rt_mutex_slowlock(struct rt_mutex *lock, int state,

	int ret = 0;

	for (;;) {
+		struct rt_mutex_waiter *top_waiter = NULL;
+
		/* Try to acquire the lock: */
		if (try_to_take_rt_mutex(lock, current, waiter))
			break;
@@ -1125,11 +1172,21 @@ __rt_mutex_slowlock(struct rt_mutex *lock, int state,
				break;
		}

+ top_waiter = rt_mutex_top_waiter(lock);
+

		raw_spin_unlock_irq(&lock->wait_lock);

		debug_rt_mutex_print_deadlock(waiter);

- schedule();
+ /*
+ * At this point the PI-dance is done, and, as the top waiter,
+ * we are next in line for the lock. Try to spin on the current
+ * owner for a while, in the hope that the lock will be released
+ * soon. Otherwise fallback and block.
+ */
+ if (top_waiter != waiter ||
+ !rt_mutex_spin_on_owner(lock, rt_mutex_owner(lock)))
+ schedule();

		raw_spin_lock_irq(&lock->wait_lock);
		set_current_state(state);

@@ -1555,7 +1612,7 @@ EXPORT_SYMBOL_GPL(__rt_mutex_init);
* rt_mutex_init_proxy_locked - initialize and lock a rt_mutex on behalf of a
* proxy owner
*
- * @lock: the rt_mutex to be locked
+ * @lock: the rt_mutex to be locked
* @proxy_owner:the task to set as owner
*
* No locking. Caller has to do serializing itself
@@ -1573,7 +1630,7 @@ void rt_mutex_init_proxy_locked(struct rt_mutex *lock, /**
* rt_mutex_proxy_unlock - release a lock on behalf of owner
*
- * @lock: the rt_mutex to be locked
+ * @lock: the rt_mutex to be locked
*
* No locking. Caller has to do serializing itself
* Special API call for PI-futex support

index 4f5f83c7d2d3..d30fc4797fe1 100644
@@ -76,7 +76,7 @@ task_top_pi_waiter(struct task_struct *p)

static inline struct task_struct *rt_mutex_owner(struct rt_mutex *lock) {
return (struct task_struct *)
- ((unsigned long)lock->owner & ~RT_MUTEX_OWNER_MASKALL);
+ ((unsigned long)READ_ONCE(lock->owner) & ~RT_MUTEX_OWNER_MASKALL);
}

/*

2.6.6

There are some applications that use futex(2) directly to implement their synchronization primitives. For those applications, they will need to modify their code to detect the presence of the new futexes. They can then use the new futexes if available and use wait-wake futexes if not.

I am also planning to take a look at the pthread_mutex* APIs to see if they can be modified to use the new futexes later on when the patch becomes more mature.

The main reason is that a FUTEX_WAIT waiter has no idea who the owner of the futex is. We usually do spinning when the lock owner is running and abort when it goes to sleep. We can't do that for FUTEX_WAIT.

Cheers,
Longman

That's what I suspected. Did you talk to the other folks who complain about futex performance (database, JVM, etc.) and play their own games with user space spinlocks and whatever?

Please involve glibc people who are interested in the futex stuff early and discuss the concept before it's set in stone for your particular usecase.

Fair enough. This wants to be spelled out in the changelog and explained a bit more detailed.

Thanks,

tglx

I am also part of the team that help large application vendors to tune their application performance on our large SMP systems. Those application vendors tend to use futex directly instead of relying on glibc. We had seen spinlock contention in the futex could sometimes be a significant portion of the CPU cycles consumed depending on the workloads that were being run. We had been providing suggestions on the best practice of how to use futexes. But there is only so much you can do with tuning their locking code implementation. That is why I am also looking for way to improve the performance of the futex code in the kernel.

Sure, I will start to do some prototyping and performance testing with glibc and then engage those folks about that.

I will.

Cheers,
Longman

These thresholds are not paravirt related. They are there to determine when we should activate explicit lock handoff when the waiter is waiting for too long. Yes, it is arbitrary. The numbers are on the high side as setting them too low will limit lock stealing and hence overall performance. The FUTEX_WAITERS bit is only turned on when either the top waiter is sleeping or a lock handoff is needed. Otherwise, it is off to encourage lock stealing in the userspace as well as in the kernel.

Cheers,
Longman

This patch adds the timeout support in other futex types to TO futexes. However, the timeout isn't as precise as the other futex types due to the fact timer expiration can't currently be detected when the thread is waiting in the serialization mutex.

---
 kernel/futex.c |   40 +++++++++++++++++++++++++++++++---------
 1 files changed, 31 insertions(+), 9 deletions(-)

index 7daba56..c73be79 100644
@@ -3423,7 +3423,8 @@ static inline int futex_set_waiters_unlocked(u32 __user *uaddr, u32 *puval)
  * Return: 0 if futex acquired, < 0 if an error happens.
  */
 static int futex_spin_on_owner(u32 __user *uaddr, u32 vpid,
-			       struct futex_state *state)
+			       struct futex_state *state,
+			       struct hrtimer_sleeper *timeout)
 {
 	int ret, loop = TO_SPIN_THRESHOLD;
 	u32 uval, curval;

@@ -3483,8 +3484,11 @@ static int futex_spin_on_owner(u32 __user *uaddr, u32 vpid,
 			continue;
 		}
 
-		/* Check for signal */
-		if (signal_pending(current)) {
+		/* Check for timeout & signal */
+		if (timeout && !timeout->task) {
+			ret = -ETIMEDOUT;
+			break;
+		} else if (signal_pending(current)) {
 			ret = -EINTR;
 			break;
 		}

@@ -3594,6 +3598,12 @@ efault:
  * This function is not inlined so that it can show up in stack trace for
  * analysis purpose.
  *
+ * The timeout functionality isn't as precise as other other futex types
+ * as timer expiration will not be detected while waiting in the
+ * serialization mutex. One possible solution is to modify the expiration
+ * function to send out a signal as well so as to break the thread out of
+ * the mutex code if we really want more precise timeout.
+ *
  * Return:
  *  < 0 - an error happens
  *  0   - acquires the lock via futex_spin_on_owner()

@@ -3601,8 +3611,9 @@ efault:
  *  2   - lock handed off from unlocker
  */
 static noinline int
-futex_lock_to(u32 __user *uaddr, unsigned int flags)
+futex_lock_to(u32 __user *uaddr, unsigned int flags, ktime_t *time)
 {
+	struct hrtimer_sleeper timeout, *to = NULL;
 	struct futex_hash_bucket *hb;
 	union futex_key key = FUTEX_KEY_INIT;
 	struct futex_state *state;

@@ -3627,6 +3638,8 @@ futex_lock_to(u32 __user *uaddr, unsigned int flags)
 	if (refill_futex_state_cache())
 		return -ENOMEM;
 
+	futex_set_timer(time, &to, &timeout, flags, current->timer_slack_ns);
+
 	ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key, VERIFY_WRITE);
 	if (unlikely(ret))
 		goto out;

@@ -3651,10 +3664,15 @@ futex_lock_to(u32 __user *uaddr, unsigned int flags)
 	/*
 	 * Acquiring the serialization mutex.
 	 */
-	if (state->type != TYPE_TO)
+	if (state->type != TYPE_TO) {
 		ret = -EINVAL;
-	else
+	} else {
+		if (to)
+			hrtimer_start_expires(&to->timer, HRTIMER_MODE_ABS);
 		ret = mutex_lock_interruptible(&state->mutex);
+		if (ret && to && !timeout.task)
+			ret = -ETIMEDOUT;
+	}
 
 	if (unlikely(ret))
 		/*

@@ -3667,7 +3685,7 @@ futex_lock_to(u32 __user *uaddr, unsigned int flags)
 	 * As the mutex owner, we can now spin on the futex word as well as
 	 * the active-ness of the futex owner.
 	 */
-	ret = futex_spin_on_owner(uaddr, vpid, state);
+	ret = futex_spin_on_owner(uaddr, vpid, state, to ? &timeout : NULL);
 
 	mutex_unlock(&state->mutex);
 

@@ -3684,6 +3702,10 @@ out_put_state_key:
 	put_futex_key(&key);
 
 out:
+	if (to) {
+		hrtimer_cancel(&to->timer);
+		destroy_hrtimer_on_stack(&to->timer);
+	}
 	return ret;
 }
 

@@ -3831,7 +3853,7 @@ long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
 		return futex_requeue(uaddr, flags, uaddr2, val, val2, &val3, 1);
 #ifdef CONFIG_SMP
 	case FUTEX_LOCK_TO:
-		return futex_lock_to(uaddr, flags);
+		return futex_lock_to(uaddr, flags, timeout);
 	case FUTEX_UNLOCK_TO:
 		return futex_unlock_to(uaddr, flags);
 #endif

@@ -3850,7 +3872,7 @@ SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
 	int cmd = op & FUTEX_CMD_MASK;
 
 	if (utime && (cmd == FUTEX_WAIT || cmd == FUTEX_LOCK_PI ||
-		      cmd == FUTEX_WAIT_BITSET ||
+		      cmd == FUTEX_WAIT_BITSET || cmd == FUTEX_LOCK_TO ||
 		      cmd == FUTEX_WAIT_REQUEUE_PI)) {
 		if (unlikely(should_fail_futex(!(op & FUTEX_PRIVATE_FLAG))))
 			return -EFAULT;

1.7.1

This patch adds a new document file on how to use the TO futexes.

---
 Documentation/00-INDEX     |    2 +
 Documentation/to-futex.txt |  140 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 142 insertions(+), 0 deletions(-)
 create mode 100644 Documentation/to-futex.txt

index cb9a6c6..a39f020 100644
@@ -439,6 +439,8 @@ this_cpu_ops.txt
 	- List rationale behind and the way to use this_cpu operations.
 thermal/
 	- directory with information on managing thermal issues (CPU/temp)
+to-futex.txt
+	- Documentation on lightweight throughput-optimized futexes.
 trace/
 	- directory with info on tracing technologies within linux
 unaligned-memory-access.txt

1.7.1