rtmutex: Spin on owner

Mark the task for later wakeup after the wait_lock has been released. This way, once the next task is awoken, it will have a better chance to of finding the wait_lock free when continuing executing in __rt_mutex_slowlock() when trying to acquire the rtmutex, calling try_to_take_rt_mutex(). Upon contended scenarios, other tasks attempting take the lock may acquire it first, right after the wait_lock is released, but (a) this can also occur with the current code, as it relies on the spinlock fairness, and (b) we are dealing with the top-waiter anyway, so it will always take the lock next.

Signed-off-by Davidlohr Bueso <[email protected]>

Davidlohr, would it work for you to replace that patch #1 from your series with this one?

I prefer having two separate patches, thus keeping their own changelog for the change justification.

wake_futex_pi() wakes the task before releasing the hash bucket lock (HB). The first thing the woken up task usually does is to acquire the lock which requires the HB lock. On SMP Systems this leads to blocking on the HB lock which is released by the owner shortly after. This patch rearranges the unlock path by first releasing the HB lock and then waking up the task.

[bigeasy: redo ontop of lockless wake-queues]

Signed-off-by Thomas Gleixner <[email protected]>

Signed-off-by Sebastian Andrzej Siewior <[email protected]>

Quoted 10 lines · Sebastian Andrzej Siewior

wake_futex_pi() wakes the task before releasing the hash bucket lock (HB). The first thing the woken up task usually does is to acquire the lock which requires the HB lock. On SMP Systems this leads to blocking on the HB lock which is released by the owner shortly after. This patch rearranges the unlock path by first releasing the HB lock and then waking up the task.

[bigeasy: redo ontop of lockless wake-queues]

Signed-off-by Thomas Gleixner <[email protected]>

Signed-off-by Sebastian Andrzej Siewior <[email protected]>

4.1-rc8-rt4 contains this via 4.0-rt4, and seems fine on my 64 core DL980. I ran a few iterations of futextests and stockfish, then mixed two loops of futextest at different rt prios, with stockfish also rt, and ltplight as tossed in as... crack filler. Box is still doing that, is way too busy, but not griping about it.

-Mike

Quoted 12 lines · Mike Galbraith

Quoted 10 lines · Sebastian Andrzej Siewior

wake_futex_pi() wakes the task before releasing the hash bucket lock (HB). The first thing the woken up task usually does is to acquire the lock which requires the HB lock. On SMP Systems this leads to blocking on the HB lock which is released by the owner shortly after. This patch rearranges the unlock path by first releasing the HB lock and then waking up the task.

[bigeasy: redo ontop of lockless wake-queues]

Signed-off-by Thomas Gleixner <[email protected]>

Signed-off-by Sebastian Andrzej Siewior <[email protected]>

Quoted 5 lines

4.1-rc8-rt4 contains this via 4.0-rt4, and seems fine on my 64 core DL980. I ran a few iterations of futextests and stockfish, then mixed two loops of futextest at different rt prios, with stockfish also rt, and ltplight as tossed in as... crack filler. Box is still doing that, is way too busy, but not griping about it.

There are two patches mostly doing the same thing. The patch posted here is a redo ontop of "lockless wake-queues". It does hb-unlock, wakeup, de-boost. The patch merged into -RT is the original approach not using "lockless wake-queues" and performing wakeup, hb-unlock, de-boost.

I plan to get into -RT the final solution once it hits upstream.

Quoted 12 lines · Mike Galbraith

Quoted 10 lines · Sebastian Andrzej Siewior

wake_futex_pi() wakes the task before releasing the hash bucket lock (HB). The first thing the woken up task usually does is to acquire the lock which requires the HB lock. On SMP Systems this leads to blocking on the HB lock which is released by the owner shortly after. This patch rearranges the unlock path by first releasing the HB lock and then waking up the task.

[bigeasy: redo ontop of lockless wake-queues]

Signed-off-by Thomas Gleixner <[email protected]>

Signed-off-by Sebastian Andrzej Siewior <[email protected]>

Quoted 5 lines

4.1-rc8-rt4 contains this via 4.0-rt4, and seems fine on my 64 core DL980. I ran a few iterations of futextests and stockfish, then mixed two loops of futextest at different rt prios, with stockfish also rt, and ltplight as tossed in as... crack filler. Box is still doing that, is way too busy, but not griping about it.

There are two patches mostly doing the same thing. The patch posted here is a redo ontop of "lockless wake-queues". It does hb-unlock, wakeup, de-boost. The patch merged into -RT is the original approach not using "lockless wake-queues" and performing wakeup, hb-unlock, de-boost.

I plan to get into -RT the final solution once it hits upstream.

wake_futex_pi() wakes the task before releasing the hash bucket lock (HB). The first thing the woken up task usually does is to acquire the lock which requires the HB lock. On SMP Systems this leads to blocking on the HB lock which is released by the owner shortly after. This patch rearranges the unlock path by first releasing the HB lock and then waking up the task.

[bigeasy: redo ontop of lockless wake-queues]

Signed-off-by Thomas Gleixner <[email protected]>

Signed-off-by Sebastian Andrzej Siewior <[email protected]>

---

Quoted 2 lines · * Davidlohr Bueso | 2015-06-16 12:50:26 [-0700]:

I prefer having two separate patches, thus keeping their own changelog for the change justification.

okay, here it is on top of #1.

On Wed, Jun 17, 2015 at 1:33 AM, Sebastian Andrzej Siewior A handful of boot test failures on ARM/OMAP were found by kernelci.org in next-20150619[1] and were bisected down to this patch, which hit next-20150619 in the form of commit 881bd58d6e9e (futex: Lower the lock contention on the HB lock during wake up). I confirmed that reverting that patch on top of next-20150619 gets things booting again for the affected platforms.

I haven't debugged this any further, but full boot logs are available for the boot failures[2][3] and the linux-omap list and maintainer are Cc'd here to help investigate further if needed.

Quoted 8 lines · Kevin Hilman

On Wed, Jun 17, 2015 at 1:33 AM, Sebastian Andrzej Siewior A handful of boot test failures on ARM/OMAP were found by kernelci.org in next-20150619[1] and were bisected down to this patch, which hit next-20150619 in the form of commit 881bd58d6e9e (futex: Lower the lock contention on the HB lock during wake up). I confirmed that reverting that patch on top of next-20150619 gets things booting again for the affected platforms.

Quoted 3 lines

I haven't debugged this any further, but full boot logs are available for the boot failures[2][3] and the linux-omap list and maintainer are Cc'd here to help investigate further if needed.

Found it. Dunno, how I missed that one. Fix below.

Avoid unnecessary cmpxchg calls, all of our other locks use it as well.

Signed-off-by Davidlohr Bueso <[email protected]>

---
 kernel/locking/rtmutex.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

kernel/locking/rtmutex.c +0 -0

index 74188d8..1d5cc9d 100644

Quoted 8 lines · Davidlohr Bueso

Avoid unnecessary cmpxchg calls, all of our other locks use it as well.

Signed-off-by Davidlohr Bueso <[email protected]>

---
 kernel/locking/rtmutex.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

kernel/locking/rtmutex.c static void fixup_rt_mutex_waiters(struct rt_mutex *lock) · line 78

Quoted 11 lines

kernel/locking/rtmutex.c +2 -1

index 74188d8..1d5cc9d 100644
@@ -74,7 +74,9 @@ static void fixup_rt_mutex_waiters(struct rt_mutex *lock)
  * set up.
  */
 #ifndef CONFIG_DEBUG_RT_MUTEXES
-# define rt_mutex_cmpxchg(l,c,n)	(cmpxchg(&l->owner, c, n) == c)
+# define rt_mutex_cmpxchg(l,c,n) \
+	(l->owner == c && cmpxchg(&l->owner, c, n) == c)

Errm. How does that improve stuff like rt_mutex_lock() ?

Quoted 10 lines · Thomas Gleixner

Quoted 8 lines · Davidlohr Bueso

Avoid unnecessary cmpxchg calls, all of our other locks use it as well.

Signed-off-by Davidlohr Bueso <[email protected]>

---
 kernel/locking/rtmutex.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

Quoted 13 lines

kernel/locking/rtmutex.c static void fixup_rt_mutex_waiters(struct rt_mutex *lock) · line 78

Quoted 11 lines

kernel/locking/rtmutex.c +2 -1

index 74188d8..1d5cc9d 100644
@@ -74,7 +74,9 @@ static void fixup_rt_mutex_waiters(struct rt_mutex *lock)
  * set up.
  */
 #ifndef CONFIG_DEBUG_RT_MUTEXES
-# define rt_mutex_cmpxchg(l,c,n)   (cmpxchg(&l->owner, c, n) == c)
+# define rt_mutex_cmpxchg(l,c,n) \
+   (l->owner == c && cmpxchg(&l->owner, c, n) == c)

Errm. How does that improve stuff like rt_mutex_lock() ?

It just avoids a cmpxchg in the fastpath when locked, at the cost of an extra test when unlocked. CCAS techniques have been proven to boost some workloads for both rwsems and mutexes. That's all.

The CCAS technique was typically used in the slow paths for those other locks, where the chance of the operation returning false is higher.

Quoted 3 lines · Jason Low

The CCAS technique was typically used in the slow paths for those other locks, where the chance of the operation returning false is higher.

That is true. Although I really want to use it in patch 4, I guess I could move the check in there, and thus avoid having it in the fastpath.

... as of fb00aca4744 (rtmutex: Turn the plist into an rb-tree) we no longer use plists for queuing any waiters. Update stale comments.

Signed-off-by Davidlohr Bueso <[email protected]>

(This is pasted as an RFC, so you probably don't want feedback going into detail yet, but I couldn't help spotting this.)

On Tue, 2015-05-19 at 10:24 -0700, Davidlohr Bueso wrote:

kernel/Kconfig.locks config MUTEX_SPIN_ON_OWNER · line 232

Quoted 6 lines

kernel/Kconfig.locks +3 -0

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

s/CONFIG_DEBUG_RT_MUTEXES/DEBUG_RT_MUTEXES/?

Btw, I just realized I had sent a stale patch where the osq was not being initialized, fixed below. Thanks!

+/*
+ * Lockless alternative to rt_mutex_has_waiters() as we do not need the
+ * wait_lock to check if we are in, for instance, a transitional state
+ * after calling mark_rt_mutex_waiters().

+ */

kernel/locking/rtmutex.c +7 -0

+static inline bool rt_mutex_has_waiters_fast(struct rt_mutex *lock)
+{
+	unsigned long val = (unsigned long)lock->owner;
+
+	if (!val)
+		return false;
+	return val & RT_MUTEX_HAS_WAITERS;

kernel/locking/rtmutex.c +6 -0

+	int ret = true;
 
+static bool rt_mutex_optimistic_spin(struct rt_mutex *lock)
+{
+	bool taken = false;
+
+	preempt_disable();

Quoted 5 lines · Davidlohr Bueso

+/*
+ * Lockless alternative to rt_mutex_has_waiters() as we do not need the
+ * wait_lock to check if we are in, for instance, a transitional state
+ * after calling mark_rt_mutex_waiters().

Before I get into a state of brain melt, could you please explain that in an understandable way?

rt_mutex_has_waiters() looks at the root pointer of the rbtree head whether that's empty. You can do a lockless check of that as well, right? So what's the FAST part of that function and how is that related to a point after we called mark_rt_mutex_waiters()?

Quoted 10 lines

+ */

kernel/locking/rtmutex.c +9 -0

+static inline bool rt_mutex_has_waiters_fast(struct rt_mutex *lock)
+{
+	unsigned long val = (unsigned long)lock->owner;
+
+	if (!val)
+		return false;
+	return val & RT_MUTEX_HAS_WAITERS;
+}
+

kernel/locking/rtmutex.c static void rt_mutex_handle_deadlock(int res, int detect_deadlock, · line 1203

Quoted 7 lines

kernel/locking/rtmutex.c +7 -0

+/*
+ * Initial check for entering the mutex spinning loop
+ */
+static inline bool rt_mutex_can_spin_on_owner(struct rt_mutex *lock)
+{
+	struct task_struct *owner;
+	/* default return to spin: if no owner, the lock is free */

Rather than having a comment in the middle of the variable declaration section, I'd prefer a comment explaing the whole logic of this function.

Quoted 11 lines

kernel/locking/rtmutex.c +10 -0

+	int ret = true;
 
+static bool rt_mutex_optimistic_spin(struct rt_mutex *lock)
+{
+	bool taken = false;
+
+	preempt_disable();
+
+	if (!rt_mutex_can_spin_on_owner(lock))
+		goto done;
+	/*

kernel/locking/rtmutex.c static void rt_mutex_handle_deadlock(int res, int detect_deadlock, · line 1232

Quoted 6 lines

kernel/locking/rtmutex.c +6 -0

+	 * In order to avoid a stampede of mutex spinners trying to
+	 * acquire the mutex all at once, the spinners need to take a
+	 * MCS (queued) lock first before spinning on the owner field.
+	 */
+	if (!osq_lock(&lock->osq))
+		goto done;

Hmm. The queue lock is serializing potential spinners, right?

So that's going to lead to a potential priority ordering problem because if a lower prio task wins the racing to the ocq_lock queue, then the higher prio waiter will be queued behind and blocked from taking the lock first.

Quoted 4 lines · Thomas Gleixner

rt_mutex_has_waiters() looks at the root pointer of the rbtree head whether that's empty. You can do a lockless check of that as well, right? So what's the FAST part of that function and how is that related to a point after we called mark_rt_mutex_waiters()?

You're right, we could use rt_mutex_has_waiters(). When I thought of this originally, I was considering something like:

if (rt_mutex_has_waiters(lock)) {
	if (current->prio >= rt_mutex_top_waiter(lock)->prio)
	...

Which obviously requires the wait_lock, but I did not consider just using the tree. However, the consequence I see in doing this is that we would miss scenarios where mark_rt_mutex_waiters() is called (under nil owner, for example), so we would force tasks to block only when there are truly waiters.

Quoted 9 lines

Quoted 9 lines

kernel/locking/rtmutex.c +9 -0

+static bool rt_mutex_optimistic_spin(struct rt_mutex *lock)
+{
+	bool taken = false;
+
+	preempt_disable();
+
+	if (!rt_mutex_can_spin_on_owner(lock))
+		goto done;
+	/*

Quoted 8 lines

kernel/locking/rtmutex.c static void rt_mutex_handle_deadlock(int res, int detect_deadlock, · line 1232

Quoted 6 lines

kernel/locking/rtmutex.c +6 -0

+	 * In order to avoid a stampede of mutex spinners trying to
+	 * acquire the mutex all at once, the spinners need to take a
+	 * MCS (queued) lock first before spinning on the owner field.
+	 */
+	if (!osq_lock(&lock->osq))
+		goto done;

Hmm. The queue lock is serializing potential spinners, right?

Yes.

Quoted 5 lines

So that's going to lead to a potential priority ordering problem because if a lower prio task wins the racing to the ocq_lock queue, then the higher prio waiter will be queued behind and blocked from taking the lock first.

Hmm yes, ocq is a fair lock. However I believe this is mitigated by (a) the conservative spinning approach, and (b) by osq_lock's need_resched() check, so at least a spinner will abort if a higher prio task comes in. But of course, this only deals with spinners, and we cannot account for a lower prio owner task.

So if this is not acceptable, I guess we'll have to do without the mcs like properties.

If you look at the RT code, then you'll notice that in the slow lock path we queue the incoming waiter (including the PI dance) and then spin only if the waiter is the top waiter on the lock.

Quoted 4 lines · Thomas Gleixner

If you look at the RT code, then you'll notice that in the slow lock path we queue the incoming waiter (including the PI dance) and then spin only if the waiter is the top waiter on the lock.

On a related note; does the RT code still add lock stealing to rtmutex?

We allow higher prio lock stealing, but I seem to remember a longish debate if we should allow equal prio lock stealing.

ping?