Skip to contentSkip to conversation

mutex: Fix optimistic spinning vs. BKL

PATCH/RFC Benjamin Herrenschmidt 8 participants 20 messages Apr 28, 2010 – May 19, 2010 Scheduler

lore
Share & tools
lore
#0 lore raw

Currently, we can hit a nasty case with optimistic spinning on mutexes:

CPU A tries to take a mutex, while holding the BKL

CPU B tried to take the BLK while holding the mutex

This looks like a AB-BA scenario but in practice, is allowed and happens due to the auto-release-on-schedule nature of the BKL.

In that case, the optimistic spinning code can get us into a situation where instead of going to sleep, A will spin waiting for B who is spinning waiting for A, and the only way out of that loop is the need_resched() test in mutex_spin_on_owner().

Now, that's bad enough since we may end up having those two processors deadlocked for a while, thus introducing latencies, but I've had cases where it completely stopped making forward progress. I suspect CPU A had nothing else waiting to run, and see need_resched() was never set.

This patch fixes both in a rather crude way. I completely disable spinning if we own the BKL, and I add a safety timeout using jiffies to fallback to sleeping if we end up spinning for more than 1 or 2 jiffies.

Now, we -could- make it a bit smarter about the BKL by introducing a contention counter and only go out if we own the BKL and it is contended, but I didn't feel like this was worth the effort, time is better spent removing the BKL from sensitive code path instead.

Regarding the choice of 1 or 2 jiffies, it's completely arbitrary. I prefer that to an arbitrary number of milliseconds mostly because it's expected that a 1000HZ kernel is run on a workload that expects smaller latencies, and as such reflects better the idea that if we're going to spin for more than a scheduler tick, we may as well schedule (and save power by doing so if we hit the idle thread).

This timeout is also a safeguard in case we find another weird deadlock scenario with optimistic spinning (that's the second one I found so far, the other one was with CPU hotplug). At least we have some kind of forward progress guarantee now.

---

include/linux/sched.h +2 -1
index dad7f66..bc6bd9a 100644
@@ -361,7 +361,8 @@ extern signed long schedule_timeout_interruptible(signed long timeout);
 extern signed long schedule_timeout_killable(signed long timeout);
 extern signed long schedule_timeout_uninterruptible(signed long timeout);
 asmlinkage void schedule(void);
-extern int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner);
+extern int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner,
+			       unsigned long timeout);
 
 struct nsproxy;
 struct user_namespace;
kernel/mutex.c +10 -2
index 632f04c..59adbae 100644
@@ -145,6 +145,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 	struct task_struct *task = current;
 	struct mutex_waiter waiter;
 	unsigned long flags;
+	unsigned long timeout;
 
 	preempt_disable();
 	mutex_acquire(&lock->dep_map, subclass, 0, ip);
@@ -168,15 +169,22 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 	 * to serialize everything.
 	 */
 
-	for (;;) {
+	for (timeout = jiffies + 2; jiffies < timeout;) {
 		struct thread_info *owner;
 
 		/*
+		 * If we own the BKL, then don't spin. The owner of the mutex
+		 * might be waiting on us to release the BKL.
+		 */
+		if (current->lock_depth >= 0)
+			break;
+
+		/*
 		 * If there's an owner, wait for it to either
 		 * release the lock or go to sleep.
 		 */
 		owner = ACCESS_ONCE(lock->owner);
-		if (owner && !mutex_spin_on_owner(lock, owner))
+		if (owner && !mutex_spin_on_owner(lock, owner, timeout))
 			break;
 
 		if (atomic_cmpxchg(&lock->count, 1, 0) == 1) {
kernel/sched.c +3 -2
index a3dff1f..b582f2e 100644
@@ -3765,7 +3765,8 @@ EXPORT_SYMBOL(schedule);
  * Look out! "owner" is an entirely speculative pointer
  * access and not reliable.
  */
-int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner)
+int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner,
+			unsigned long timeout)
 {
 	unsigned int cpu;
 	struct rq *rq;
@@ -3801,7 +3802,7 @@ int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner)
 
 	rq = cpu_rq(cpu);
 
-	for (;;) {
+	while (jiffies < timeout) {
 		/*
 		 * Owner changed, break to re-assess state.
 		 */
#1 lore raw
Quoted 8 lines · Benjamin Herrenschmidt

Currently, we can hit a nasty case with optimistic spinning on mutexes:

CPU A tries to take a mutex, while holding the BKL

CPU B tried to take the BLK while holding the mutex

This looks like a AB-BA scenario but in practice, is allowed and happens due to the auto-release-on-schedule nature of the BKL.

.../...

BTW. The patch is only compile-tested so far :-) It's going to be hammered with the test case that triggered the original bug hopefully tonight.

Cheers,
Ben.

#2 lore raw
In reply to Benjamin Herrenschmidt
Quoted 4 lines · Benjamin Herrenschmidt

Now, we -could- make it a bit smarter about the BKL by introducing a contention counter and only go out if we own the BKL and it is contended, but I didn't feel like this was worth the effort, time is better spent removing the BKL from sensitive code path instead.

Agreed.

kernel/mutex.c __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,

Quoted 5 lines
kernel/mutex.c +2 -2
-       for (;;) {
+       for (timeout = jiffies + 2; jiffies < timeout;) {
[...]
-       for (;;) {
+       while (jiffies < timeout) {

This needs to use time_before() to avoid problems on jiffies wraparound.

Arnd

#3 lore raw
Quoted 3 lines · Arnd Bergmann

This needs to use time_before() to avoid problems on jiffies wraparound.

Ah right, forgot about that, been a while I didn't use jiffies for anything :-)

I'll respin later today.

Cheers,
Ben.

#4 lore raw
Quoted 9 lines · Benjamin Herrenschmidt
Quoted 3 lines · Arnd Bergmann

This needs to use time_before() to avoid problems on jiffies wraparound.

Ah right, forgot about that, been a while I didn't use jiffies for anything :-)

I'll respin later today.

Like thie perhaps? If this looks good it would be great to get this in .34

include/linux/sched.h +2 -1
index 70abfd3..991d86f 100644
@@ -351,7 +351,8 @@ extern signed long schedule_timeout_killable(signed long timeout);
 extern signed long schedule_timeout_uninterruptible(signed long timeout);
 asmlinkage void __schedule(void);
 asmlinkage void schedule(void);
-extern int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner);
+extern int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner,
+                               unsigned long timeout);
 
 struct nsproxy;
 struct user_namespace;
kernel/mutex.c +10 -2
index 947b3ad..fcf2573 100644
@@ -145,6 +145,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 	struct task_struct *task = current;
 	struct mutex_waiter waiter;
 	unsigned long flags;
+	unsigned long timeout;
 
 	preempt_disable();
 	mutex_acquire(&lock->dep_map, subclass, 0, ip);
@@ -168,15 +169,22 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 	 * to serialize everything.
 	 */
 
-	for (;;) {
+	for (timeout = jiffies + 2; time_before(jiffies, timeout);) {
 		struct thread_info *owner;
 
 		/*
+		 * If we own the BKL, then don't spin. The owner of the mutex
+		 * might be waiting on us to release the BKL.
+		 */
+		if (current->lock_depth >= 0)
+			break;
+
+		/*
 		 * If there's an owner, wait for it to either
 		 * release the lock or go to sleep.
 		 */
 		owner = ACCESS_ONCE(lock->owner);
-		if (owner && !mutex_spin_on_owner(lock, owner))
+		if (owner && !mutex_spin_on_owner(lock, owner, timeout))
 			break;
 
 		if (atomic_cmpxchg(&lock->count, 1, 0) == 1) {
kernel/sched.c +3 -2
index 663a1d0..ef58dc0 100644
@@ -5523,7 +5523,8 @@ EXPORT_SYMBOL(schedule);
  * Look out! "owner" is an entirely speculative pointer
  * access and not reliable.
  */
-int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner)
+int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner,
+			unsigned long timeout)
 {
 	unsigned int cpu;
 	struct rq *rq;
@@ -5559,7 +5560,7 @@ int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner)
 
 	rq = cpu_rq(cpu);
 
-	for (;;) {
+	while (time_before(jiffies, timeout)) {
 		/*
 		 * Owner changed, break to re-assess state.
 		 */

Yours Tony

#5 lore raw
Quoted 52 lines · Tony Breeds
Quoted 9 lines · Benjamin Herrenschmidt
Quoted 3 lines · Arnd Bergmann

This needs to use time_before() to avoid problems on jiffies wraparound.

Ah right, forgot about that, been a while I didn't use jiffies for anything :-)

I'll respin later today.

Like thie perhaps? If this looks good it would be great to get this in .34

include/linux/sched.h +2 -1
index 70abfd3..991d86f 100644
@@ -351,7 +351,8 @@ extern signed long schedule_timeout_killable(signed long timeout);
 extern signed long schedule_timeout_uninterruptible(signed long timeout);
 asmlinkage void __schedule(void);
 asmlinkage void schedule(void);
-extern int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner);
+extern int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner,
+                               unsigned long timeout);
 
 struct nsproxy;
 struct user_namespace;
kernel/mutex.c +6 -1
index 947b3ad..fcf2573 100644
@@ -145,6 +145,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 	struct task_struct *task = current;
 	struct mutex_waiter waiter;
 	unsigned long flags;
+	unsigned long timeout;
 
 	preempt_disable();
 	mutex_acquire(&lock->dep_map, subclass, 0, ip);
@@ -168,15 +169,22 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 	 * to serialize everything.
 	 */
 
-	for (;;) {
+	for (timeout = jiffies + 2; time_before(jiffies, timeout);) {
 		struct thread_info *owner;
 
 		/*
+		 * If we own the BKL, then don't spin. The owner of the mutex
+		 * might be waiting on us to release the BKL.
+		 */
+		if (current->lock_depth >= 0)

kernel/mutex.c __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, · line 188

Quoted 10 lines
kernel/mutex.c +4 -1
+			break;
+
+		/*
 		 * If there's an owner, wait for it to either
 		 * release the lock or go to sleep.
 		 */
 		owner = ACCESS_ONCE(lock->owner);
-		if (owner && !mutex_spin_on_owner(lock, owner))
+		if (owner && !mutex_spin_on_owner(lock, owner, timeout))
 			break;

I like the safeguard against the bkl, it looks indeed like something we should have in .34

But I really don't like the timeout.

This is going to make the things even worse if we have another cause of deadlock by hiding the worst part of the consequences without actually solving the problem.
And since the induced latency or deadlock won't be easily visible anymore, we'll miss there is a problem. So we are going to spin for two jiffies and only someone doing specific latency measurements will notice, if he's lucky enough to meet the bug.

Moreover that adds some unnessary (small) overhead in this path.

May be can we have it as a debugging option, something that would be part of lockdep, which would require CONFIG_DEBUG_MUTEX to support mutex adaptive spinning.

A debugging option that could just dump the held locks and the current one if we spin for an excessive timeslice.

Thanks.

#6 lore raw
Quoted 6 lines · Frederic Weisbecker

I like the safeguard against the bkl, it looks indeed like something we should have in .34

But I really don't like the timeout.

And I hate not having it :-)

Quoted 3 lines

This is going to make the things even worse if we have another cause of deadlock by hiding the worst part of the consequences without actually solving the problem.

Yes and no. There's two reasons why the timeout is good. One is the safeguard part and it's arguable whether it helps hiding bugs or not, but there are very real cases where I believe we should get out and go to sleep as well that aren't bugs.

IE. If the mutex owner is running for a long time and nobody is contending on your CPU, you're simply not going to hit the need_resched() test. That means you will spin, which means you will suck a lot more power as well, not counting the potentially bad effect on rebalance, load average etc...

There's also the fact that 2 CPUs or more trying to obtain it at once may all go into spinning, which can lead to interesting results in term of power consumption (and cpu_relax doesn't help that much).

I really don't think it's a good idea to turns mutex into potential multi-jiffies spinning things like that.

Quoted 4 lines

And since the induced latency or deadlock won't be easily visible anymore, we'll miss there is a problem. So we are going to spin for two jiffies and only someone doing specific latency measurements will notice, if he's lucky enough to meet the bug.

Well, the thing is that it may not be a bug.

The thing is that the actual livelock with the BKL should really only happen with the BKL since that's the only thing we have that allows for AB->BA semantics. Anything else should hopefully be caught by lockdep.

So I don't think there's that much to fear about hidden bugs.

But I -also- don't see the point of spinning potentially for a very long time instead of going to sleep and saving power. The adaptive spinning goal is to have an opportunistic optimization based on the idea that the mutex is likely to be held for a very short period of time by its owner and nobody's waiting for it yet. Ending up doing multi-jiffies spins just doesn't fit in that picture. In fact, I was tempted to make the timeout a lot shorter but decided against calling into clock sources etc... and instead kept it simple with jiffies.

Quoted 1 line

Moreover that adds some unnessary (small) overhead in this path.

Uh ? So ? This is the contended path where we are .. spinning :-) The overhead of reading jiffies and comparing here is simply never going to show on any measurement I bet you :-)

Quoted 3 lines

May be can we have it as a debugging option, something that would be part of lockdep, which would require CONFIG_DEBUG_MUTEX to support mutex adaptive spinning.

No, what I would potentially add as part of lockdep however is a way to instrument how often we get out of the spin via the timeout. That might be a useful information to figure out some of those runaway code path, but they may well happen for very legit reasons and aren't a bug per-se.

Quoted 2 lines

A debugging option that could just dump the held locks and the current one if we spin for an excessive timeslice.

Ben.

#13 lore raw
In reply to Frederic Weisbecker
Quoted 13 lines · Frederic Weisbecker

I like the safeguard against the bkl, it looks indeed like something we should have in .34

But I really don't like the timeout.

This is going to make the things even worse if we have another cause of deadlock by hiding the worst part of the consequences without actually solving the problem.
And since the induced latency or deadlock won't be easily visible anymore, we'll miss there is a problem. So we are going to spin for two jiffies and only someone doing specific latency measurements will notice, if he's lucky enough to meet the bug.

Quoted 8 lines

Moreover that adds some unnessary (small) overhead in this path.

May be can we have it as a debugging option, something that would be part of lockdep, which would require CONFIG_DEBUG_MUTEX to support mutex adaptive spinning.

A debugging option that could just dump the held locks and the current one if we spin for an excessive timeslice.

FYI, there's a case where OWNER_SPIN eats astounding amounts of CPU.

Run virgin AIM7 V1.1 with many many tasks and a nil workfile. When the thing kicks off preparing for test, it forks of these many tasks, who then all try to phone home via pipe. The result it horrible to behold.

There's a fix for AIM7's scalability problem, but the virgin code looks like a decent OWNER_SPIN corner case test. It turns a 32 core smt box into an expensive space heater at sufficiently high task count:)

-Mike

#7 lore raw
In reply to Benjamin Herrenschmidt
Quoted 25 lines · Benjamin Herrenschmidt
Quoted 6 lines · Frederic Weisbecker

I like the safeguard against the bkl, it looks indeed like something we should have in .34

But I really don't like the timeout.

And I hate not having it :-)

Quoted 3 lines

This is going to make the things even worse if we have another cause of deadlock by hiding the worst part of the consequences without actually solving the problem.

Yes and no. There's two reasons why the timeout is good. One is the safeguard part and it's arguable whether it helps hiding bugs or not, but there are very real cases where I believe we should get out and go to sleep as well that aren't bugs.

IE. If the mutex owner is running for a long time and nobody is contending on your CPU, you're simply not going to hit the need_resched() test. That means you will spin, which means you will suck a lot more power as well, not counting the potentially bad effect on rebalance, load average etc...

Quoted 6 lines

There's also the fact that 2 CPUs or more trying to obtain it at once may all go into spinning, which can lead to interesting results in term of power consumption (and cpu_relax doesn't help that much).

I really don't think it's a good idea to turns mutex into potential multi-jiffies spinning things like that.

Yeah, I was considering only the deadlock issue.

Ok it's an problem on power consumption. That said I wonder if we have so much places where a task can hold a mutex for two jiffies without sleeping in-between, since when the owner goes to sleep, spinning is stopped.

If that's an issue for power saving, it means we have places to fix. Also I wonder if we should disable adaptive spinning for people who want agressive power saving. At least it would be worth the test to check the result.

Also, to solve this problem when several cpus may spin on the owner, I wonder adaptive spinning is doing the right thing here. We should have only one spinner I think, and the rest should go to sleep as the time to spin on several subsequent owners would be much better gained to do something else (schedule something else or power saving). In fact, that too could deserve some tests.

Quoted 13 lines
Quoted 4 lines

And since the induced latency or deadlock won't be easily visible anymore, we'll miss there is a problem. So we are going to spin for two jiffies and only someone doing specific latency measurements will notice, if he's lucky enough to meet the bug.

Well, the thing is that it may not be a bug.

The thing is that the actual livelock with the BKL should really only happen with the BKL since that's the only thing we have that allows for AB->BA semantics. Anything else should hopefully be caught by lockdep.

So I don't think there's that much to fear about hidden bugs.

Quoted 8 lines

But I -also- don't see the point of spinning potentially for a very long time instead of going to sleep and saving power. The adaptive spinning goal is to have an opportunistic optimization based on the idea that the mutex is likely to be held for a very short period of time by its owner and nobody's waiting for it yet. Ending up doing multi-jiffies spins just doesn't fit in that picture. In fact, I was tempted to make the timeout a lot shorter but decided against calling into clock sources etc... and instead kept it simple with jiffies.

Ok. But even under this power saving angle, I think this heuristic based on timeout is still only hidding the problem. Or it lowers it more than it solves it, which is quite better than keeping the things as is of course. But if the real source is in places that hold mutexes without sleeping for too much time, I think we should rather identify these places and solve the ugly locking there.

Plus may be allowing only one spinner at the time.

But yeah until we reach a good solution for that, may be this timeout would be worth.

Quoted 5 lines
Quoted 1 line

Moreover that adds some unnessary (small) overhead in this path.

Uh ? So ? This is the contended path where we are .. spinning :-) The overhead of reading jiffies and comparing here is simply never going to show on any measurement I bet you :-)

Yeah, probably in fact :)

Quoted 8 lines
Quoted 3 lines

May be can we have it as a debugging option, something that would be part of lockdep, which would require CONFIG_DEBUG_MUTEX to support mutex adaptive spinning.

No, what I would potentially add as part of lockdep however is a way to instrument how often we get out of the spin via the timeout. That might be a useful information to figure out some of those runaway code path, but they may well happen for very legit reasons and aren't a bug per-se.

We could make a trace event for that.

Thanks.

#8 lore raw
Quoted 8 lines

Yeah, I was considering only the deadlock issue.

Ok it's an problem on power consumption. That said I wonder if we have so much places where a task can hold a mutex for two jiffies without sleeping in-between, since when the owner goes to sleep, spinning is stopped.

Quoted 4 lines

If that's an issue for power saving, it means we have places to fix. Also I wonder if we should disable adaptive spinning for people who want agressive power saving. At least it would be worth the test to check the result.

I don't think it's only about agressive power saving. I'm not sure this is directly related but somebody recently reported a case where pretty much every CPU in the machine gets to spin on one holding the mutex, the power consumption skyrockets and everything heats up at once. Not nice even on servers on workloads where otherwise everybody would have gone to sleep.

My feeling is that spinning should last only a very small amount of time, ideally using a better clock than jiffies, maybe a few dozen ms at max. But I decided to compromise for code simplicity and less overhead by using jiffies instead. Maybe 1 jiffy delta would have been enough, not two tho (which means a random timeout between 0 and 1 jiffie).

Quoted 6 lines

Also, to solve this problem when several cpus may spin on the owner, I wonder adaptive spinning is doing the right thing here. We should have only one spinner I think, and the rest should go to sleep as the time to spin on several subsequent owners would be much better gained to do something else (schedule something else or power saving). In fact, that too could deserve some tests.

Right, the problem is due to the fact that we skip spinning if there's already a waiter but we don't know that there is already a spinner so we can end up with multiple spinners.

I don't see a non invasive way to fix that.. we could add a spinner counter to the mutex but that sucks a bit. Might still be worthwhile, not sure. Peter, what do you reckon ?

Quoted 6 lines

Ok. But even under this power saving angle, I think this heuristic based on timeout is still only hidding the problem. Or it lowers it more than it solves it, which is quite better than keeping the things as is of course. But if the real source is in places that hold mutexes without sleeping for too much time, I think we should rather identify these places and solve the ugly locking there.

That's a job for lockdep or something similar :-) Doing so is orthogonal, I don't see this contradicting with limiting the spinning time. Again, I tend to have a different "view" of it as: spinning is an oportunistic optimization based on the idea that the owner will release the mutex soon, I don't see the point of spinning for a long time :-)

Note that power management is one side of the story. Another one is relinguishing the CPU to the hypervisor so some other partition gets some time. Etc... There's more than one consequence to ending up with CPUs spinning instead of sleeping and they are not all trivial, so by letting mutexes spin for potentially a "long time", we quite fundamentally change the semantics of those mutexes with impacts in othe areas that we don't necessarily see. This goes beyond the scope of a simple optimization and becomes problematic.

Yes, we can to try to find all of these areas and address them one by one, or we can use my simpler approach which is to keep the overall semantic of mutexes which is to sleep ... and bound the optimisation to what it should be: a short term spin to speed up short lived contention cases.

But yeah, the argument is very valid that maybe we should spin even less long and that maybe we should use a finer grained clock to limit the spin to a few microseconds at most. The exact number remains to be determined :-)

Quoted 4 lines

Plus may be allowing only one spinner at the time.

But yeah until we reach a good solution for that, may be this timeout would be worth.

Cheers,
Ben.

Quoted 34 lines
Quoted 7 lines
Quoted 3 lines

Moreover that adds some unnessary (small) overhead in this path.

Uh ? So ? This is the contended path where we are .. spinning :-) The overhead of reading jiffies and comparing here is simply never going to show on any measurement I bet you :-)

Yeah, probably in fact :)

Quoted 8 lines
Quoted 3 lines

May be can we have it as a debugging option, something that would be part of lockdep, which would require CONFIG_DEBUG_MUTEX to support mutex adaptive spinning.

No, what I would potentially add as part of lockdep however is a way to instrument how often we get out of the spin via the timeout. That might be a useful information to figure out some of those runaway code path, but they may well happen for very legit reasons and aren't a bug per-se.

We could make a trace event for that.

Thanks.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

maintainer
#9 lore raw
Quoted 7 lines · Benjamin Herrenschmidt
Quoted 6 lines

Also, to solve this problem when several cpus may spin on the owner, I wonder adaptive spinning is doing the right thing here. We should have only one spinner I think, and the rest should go to sleep as the time to spin on several subsequent owners would be much better gained to do something else (schedule something else or power saving). In fact, that too could deserve some tests.

Quoted 7 lines

Right, the problem is due to the fact that we skip spinning if there's already a waiter but we don't know that there is already a spinner so we can end up with multiple spinners.

I don't see a non invasive way to fix that.. we could add a spinner counter to the mutex but that sucks a bit. Might still be worthwhile, not sure. Peter, what do you reckon ?

If its a large problem the lock is overly contended and _that_ needs fixing. I don't at all feel like adding atomic ops to the spin loop to try and detect this.

As to the 2 jiffy spin timeout, I guess we should add a lockdep warning for that, because anybody holding a mutex for longer than 2 jiffies and not sleeping does need fixing anyway.

#14 lore raw
In reply to Tony Breeds
Commit-ID:  227945799cc10d77c6ef812f3eb8a61a78689454
Gitweb:     http://git.kernel.org/tip/227945799cc10d77c6ef812f3eb8a61a78689454
Author:     Tony Breeds <[email protected]>
AuthorDate: Fri, 7 May 2010 14:20:10 +1000
Committer:  Ingo Molnar <[email protected]>
CommitDate: Tue, 11 May 2010 17:07:24 +0200

mutex: Fix optimistic spinning vs. BKL

Currently, we can hit a nasty case with optimistic spinning on mutexes:

CPU A tries to take a mutex, while holding the BKL

CPU B tried to take the BLK while holding the mutex

This looks like a AB-BA scenario but in practice, is allowed and happens due to the auto-release-on-schedule nature of the BKL.

In that case, the optimistic spinning code can get us into a situation where instead of going to sleep, A will spin waiting for B who is spinning waiting for A, and the only way out of that loop is the need_resched() test in mutex_spin_on_owner().

Now, that's bad enough since we may end up having those two processors deadlocked for a while, thus introducing latencies, but I've had cases where it completely stopped making forward progress. I suspect CPU A had nothing else waiting to run, and see need_resched() was never set.

This patch fixes both in a rather crude way. I completely disable spinning if we own the BKL, and I add a safety timeout using jiffies to fallback to sleeping if we end up spinning for more than 1 or 2 jiffies.

Now, we -could- make it a bit smarter about the BKL by introducing a contention counter and only go out if we own the BKL and it is contended, but I didn't feel like this was worth the effort, time is better spent removing the BKL from sensitive code path instead.

Regarding the choice of 1 or 2 jiffies, it's completely arbitrary. I prefer that to an arbitrary number of milliseconds mostly because it's expected that a 1000HZ kernel is run on a workload that expects smaller latencies, and as such reflects better the idea that if we're going to spin for more than a scheduler tick, we may as well schedule (and save power by doing so if we hit the idle thread).

This timeout is also a safeguard in case we find another weird deadlock scenario with optimistic spinning (that's the second one I found so far, the other one was with CPU hotplug). At least we have some kind of forward progress guarantee now.

LKML-Reference: <[email protected]>

---
 include/linux/sched.h |    3 ++-
 kernel/mutex.c        |   12 ++++++++++--
 kernel/sched.c        |    5 +++--
 3 files changed, 15 insertions(+), 5 deletions(-)
include/linux/sched.h +2 -1
index dad7f66..bc6bd9a 100644
@@ -361,7 +361,8 @@ extern signed long schedule_timeout_interruptible(signed long timeout);
 extern signed long schedule_timeout_killable(signed long timeout);
 extern signed long schedule_timeout_uninterruptible(signed long timeout);
 asmlinkage void schedule(void);
-extern int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner);
+extern int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner,
+			       unsigned long timeout);
 
 struct nsproxy;
 struct user_namespace;
kernel/mutex.c +10 -2
index 632f04c..7d4626b 100644
@@ -145,6 +145,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 	struct task_struct *task = current;
 	struct mutex_waiter waiter;
 	unsigned long flags;
+	unsigned long timeout;
 
 	preempt_disable();
 	mutex_acquire(&lock->dep_map, subclass, 0, ip);
@@ -168,15 +169,22 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 	 * to serialize everything.
 	 */
 
-	for (;;) {
+	for (timeout = jiffies + 2; time_before(jiffies, timeout);) {
 		struct thread_info *owner;
 
 		/*
+		 * If we own the BKL, then don't spin. The owner of the mutex
+		 * might be waiting on us to release the BKL.
+		 */
+		if (current->lock_depth >= 0)
+			break;
+
+		/*
 		 * If there's an owner, wait for it to either
 		 * release the lock or go to sleep.
 		 */
 		owner = ACCESS_ONCE(lock->owner);
-		if (owner && !mutex_spin_on_owner(lock, owner))
+		if (owner && !mutex_spin_on_owner(lock, owner, timeout))
 			break;
 
 		if (atomic_cmpxchg(&lock->count, 1, 0) == 1) {
kernel/sched.c +3 -2
index 3c2a54f..e613160 100644
@@ -3775,7 +3775,8 @@ EXPORT_SYMBOL(schedule);
  * Look out! "owner" is an entirely speculative pointer
  * access and not reliable.
  */
-int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner)
+int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner,
+			unsigned long timeout)
 {
 	unsigned int cpu;
 	struct rq *rq;
@@ -3811,7 +3812,7 @@ int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner)
 
 	rq = cpu_rq(cpu);
 
-	for (;;) {
+	while (time_before(jiffies, timeout)) {
 		/*
 		 * Owner changed, break to re-assess state.
 		 */
#10 lore raw
In reply to Peter Zijlstra
Quoted 4 lines · Peter Zijlstra

As to the 2 jiffy spin timeout, I guess we should add a lockdep warning for that, because anybody holding a mutex for longer than 2 jiffies and not sleeping does need fixing anyway.

I really hate the jiffies thing, but looking at the optimistic spinning, I do wonder about two things..

First - we check "need_resched()" only if owner is NULL. That sounds wrong. If we need to reschedule, we need to stop spinning _regardless_ of whether the owner may have been preempted before setting the owner field.

Second: we allow "owner" to change, and we'll continue spinning. This is how you can end up spinning for a long time - not because anybody holds the mutex for longer than 2 jiffies, but because a lot of other threads _together_ hold the mutex for longer than 2 jiffies.

Now, I think we do want some limited "continue spinning even if somebody else ended up getting it instead", but I think we should at least limit it. Otherwise we end up being potentially rather unfair, since we don't have any fair queueing logic for the optimistic spinning phase.

Now, we could just count the number of times "owner" has changed, and I suspect that would be sufficient. Now, that trivial counting sceme would fail if "owner" stays the same (ie the same process re-takes the lock over and over again, possibly due to hot cacheline things being very unfair to the person who already owns it), but quite frankly, I don't think we can get into that kind of situation.

Why? Mutexes may end up being very heavily contended, but they can't be contended by just _one_ thread. So if we're really in a starvation issue, the thread that is waiting _will_ see multiple different owners.

So once you have seen X number of other owners, you just say "screw it, this spinning thing isn't working for me, I'll go to the sleeping case".

Of course, that is _really_ unfair. It will make it all that easier for the other spinners to just get the lock by spinning. We used to have some logic to say "we won't spin if there are proper waiters", but that was horrible for performance. See commit ac6e60ee405.

Of course, it's quite possible that as long as "need_resched()" isn't set, spinning really _is_ the right thing to do. Maybe it causes horrible CPU load on some odd "everybody synchronize" loads, but maybe that really is the best we can do.

Linus

maintainer
#11 lore raw
Quoted 7 lines · Linus Torvalds
Quoted 4 lines · Peter Zijlstra

As to the 2 jiffy spin timeout, I guess we should add a lockdep warning for that, because anybody holding a mutex for longer than 2 jiffies and not sleeping does need fixing anyway.

Quoted 6 lines

I really hate the jiffies thing, but looking at the optimistic spinning, I do wonder about two things..

First - we check "need_resched()" only if owner is NULL. That sounds wrong. If we need to reschedule, we need to stop spinning _regardless_ of whether the owner may have been preempted before setting the owner field.

There is a second need_resched() in the inner spin loop in kernel/sched.c:mutex_spin_on_owner().

Quoted 4 lines

Second: we allow "owner" to change, and we'll continue spinning. This is how you can end up spinning for a long time - not because anybody holds the mutex for longer than 2 jiffies, but because a lot of other threads _together_ hold the mutex for longer than 2 jiffies.

Granted.

Quoted 12 lines

Now, I think we do want some limited "continue spinning even if somebody else ended up getting it instead", but I think we should at least limit it. Otherwise we end up being potentially rather unfair, since we don't have any fair queueing logic for the optimistic spinning phase.

Now, we could just count the number of times "owner" has changed, and I suspect that would be sufficient. Now, that trivial counting sceme would fail if "owner" stays the same (ie the same process re-takes the lock over and over again, possibly due to hot cacheline things being very unfair to the person who already owns it), but quite frankly, I don't think we can get into that kind of situation.

Quoted 6 lines

Why? Mutexes may end up being very heavily contended, but they can't be contended by just _one_ thread. So if we're really in a starvation issue, the thread that is waiting _will_ see multiple different owners.

So once you have seen X number of other owners, you just say "screw it, this spinning thing isn't working for me, I'll go to the sleeping case".

Right, so basically count the number of mutex_spin_on_owner() calls and bail when >N.

Quoted 4 lines

Of course, it's quite possible that as long as "need_resched()" isn't set, spinning really _is_ the right thing to do. Maybe it causes horrible CPU load on some odd "everybody synchronize" loads, but maybe that really is the best we can do.

Ben's argument was that spinning for a long time wrecks power usage.

That said, I'd still like a counter/event/warning to see if someone actually manages to hold onto a mutex for long (2 jiffies) without scheduling at all. If we ever run into something like that, that needs to get fixed regardless.

#12 lore raw
In reply to Linus Torvalds
Quoted 7 lines · Linus Torvalds
Quoted 4 lines · Peter Zijlstra

As to the 2 jiffy spin timeout, I guess we should add a lockdep warning for that, because anybody holding a mutex for longer than 2 jiffies and not sleeping does need fixing anyway.

Quoted 6 lines

I really hate the jiffies thing, but looking at the optimistic spinning, I do wonder about two things..

First - we check "need_resched()" only if owner is NULL. That sounds wrong. If we need to reschedule, we need to stop spinning _regardless_ of whether the owner may have been preempted before setting the owner field.

The inner call mutex_spin_on_owner() checks it regardless (yeah, I tripped on that too initially).

.../...

Quoted 6 lines

Now, we could just count the number of times "owner" has changed, and I suspect that would be sufficient. Now, that trivial counting sceme would fail if "owner" stays the same (ie the same process re-takes the lock over and over again, possibly due to hot cacheline things being very unfair to the person who already owns it), but quite frankly, I don't think we can get into that kind of situation.

I've observed cases where owner didn't appear to change but we also didn't trip on need_resched(), which leads me to wonder, if nobody is contending to run on that processor, we may never set need_resched() and end up spinning as long as the target is running.

This cause the deadlock with the BKL (which I fixed) but it also means we may spend a long time without going to sleep, which means CPU not dozed or returned to the hypervisor etc... for longer than needed.

That's the reasoning behind the jiffy timeout. It's not great but it will get us out in some amount of time, which I wanted to guarantee.

.../...

Quoted 4 lines

Of course, it's quite possible that as long as "need_resched()" isn't set, spinning really _is_ the right thing to do. Maybe it causes horrible CPU load on some odd "everybody synchronize" loads, but maybe that really is the best we can do.

Well, that happens at least occasionally but if you think that can be safely ignored, then drop the jiffy timeout.

Cheers,
Ben.

Quoted 6 lines

Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

#16 lore raw
In reply to tip-bot for Tony Breeds
Quoted 8 lines · tip-bot for Tony Breeds
Commit-ID:  227945799cc10d77c6ef812f3eb8a61a78689454
Gitweb:     http://git.kernel.org/tip/227945799cc10d77c6ef812f3eb8a61a78689454
Author:     Tony Breeds <[email protected]>
AuthorDate: Fri, 7 May 2010 14:20:10 +1000
Committer:  Ingo Molnar <[email protected]>
CommitDate: Tue, 11 May 2010 17:07:24 +0200

mutex: Fix optimistic spinning vs. BKL

Tony, mind sending a version of this patch that does not include a jiffies based spinning loop?

Thanks,

Ingo

#17 lore raw
Quoted 3 lines · Ingo Molnar

Tony, mind sending a version of this patch that does not include a jiffies based spinning loop?

I think it should just be the two-liner

	if (current->lock_depth >= 0)
		break;

in that loop. Plus comment.

Linus

#18 lore raw
In reply to Ingo Molnar
Quoted 10 lines · Ingo Molnar
Quoted 7 lines · tip-bot for Tony Breeds
Commit-ID:  227945799cc10d77c6ef812f3eb8a61a78689454
Gitweb:     http://git.kernel.org/tip/227945799cc10d77c6ef812f3eb8a61a78689454
Author:     Tony Breeds <[email protected]>
AuthorDate: Fri, 7 May 2010 14:20:10 +1000
Committer:  Ingo Molnar <[email protected]>
CommitDate: Tue, 11 May 2010 17:07:24 +0200
Quoted 4 lines
Quoted 1 line

mutex: Fix optimistic spinning vs. BKL

Tony, mind sending a version of this patch that does not include a jiffies based spinning loop?

Subject: [PATCH] mutex: Fix optimistic spinning vs. BKL

Currently, we can hit a nasty case with optimistic spinning on mutexes:

CPU A tries to take a mutex, while holding the BKL

CPU B tried to take the BLK while holding the mutex

This looks like a AB-BA scenario but in practice, is allowed and happens due to the auto-release-on-schedule nature of the BKL.

In that case, the optimistic spinning code can get us into a situation where instead of going to sleep, A will spin waiting for B who is spinning waiting for A, and the only way out of that loop is the need_resched() test in mutex_spin_on_owner().

This patch fixes both in a rather crude way. I completely disable spinning if we own the BKL, and I add a safety timeout using jiffies to fallback to sleeping if we end up spinning for more than 1 or 2 jiffies.

Cc Benjamin Herrenschmidt <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 kernel/mutex.c |    7 +++++++
 1 files changed, 7 insertions(+), 0 deletions(-)
kernel/mutex.c +7 -0
index 632f04c..c38d302 100644
@@ -172,6 +172,13 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 		struct thread_info *owner;
 
 		/*
+		 * If we own the BKL, then don't spin. The owner of the mutex
+		 * might be waiting on us to release the BKL.
+		 */
+		if (current->lock_depth >= 0)
+			break;
+
+		/*
 		 * If there's an owner, wait for it to either
 		 * release the lock or go to sleep.
 		 */
Signature · 4 lines
1.6.6.1


Yours Tony
#19 lore raw
Commit-ID:  fd6be105b883244127a734ac9f14ae94a022dcc0
Gitweb:     http://git.kernel.org/tip/fd6be105b883244127a734ac9f14ae94a022dcc0
Author:     Tony Breeds <[email protected]>
AuthorDate: Wed, 19 May 2010 15:46:36 +1000
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 19 May 2010 08:18:44 +0200

mutex: Fix optimistic spinning vs. BKL

Currently, we can hit a nasty case with optimistic spinning on mutexes:

CPU A tries to take a mutex, while holding the BKL

CPU B tried to take the BLK while holding the mutex

This looks like a AB-BA scenario but in practice, is allowed and happens due to the auto-release on schedule() nature of the BKL.

In that case, the optimistic spinning code can get us into a situation where instead of going to sleep, A will spin waiting for B who is spinning waiting for A, and the only way out of that loop is the need_resched() test in mutex_spin_on_owner().

This patch fixes it by completely disabling spinning if we own the BKL. This adds one more detail to the extensive list of reasons why it's a bad idea for kernel code to be holding the BKL.

LKML-Reference: <[email protected]>

[ added an unlikely() attribute to the branch ]
---
 kernel/mutex.c |    7 +++++++
 1 files changed, 7 insertions(+), 0 deletions(-)
kernel/mutex.c +7 -0
index 632f04c..4c0b7b3 100644
@@ -172,6 +172,13 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 		struct thread_info *owner;
 
 		/*
+		 * If we own the BKL, then don't spin. The owner of
+		 * the mutex might be waiting on us to release the BKL.
+		 */
+		if (unlikely(current->lock_depth >= 0))
+			break;
+
+		/*
 		 * If there's an owner, wait for it to either
 		 * release the lock or go to sleep.
 		 */