[RFC PATCH] rtmutex: Do not prio boost when timeout is used

[RFC PATCH] rtmutex: Do not prio boost when timeout is used

[Steven Rostedt]

I've been discussing an issue on IRC with deadlock checking and found
something wrong with it. Mainly, if any of the locks have a timeout,
then even if the chain loops, there is no real deadlock. If one of the
locks in the chain times out, then things will move forward again.

Now it may not be nice to have locks that do this, but we can break
applications that use futex priority boosting and may use timeouts to
break deadlocks.

Here's the scenario:

Locks:  L1, L2, L3
Tasks:  A, B, C

C grabs L2

A grabs L1
A tries to grab L2 - blocks

B grabs L3
B grabs L1 with a timeout

C grabs L3 and blocks

deadlock detect kicks in and runs up the chain.

L3 is held by B
B is blocked on L1
L1 is owned by A

(in the mean time B times out and release L3)

A is blocked on L2
L2 is owned by C

 if (lock == orig_lock || rt_mutex_owner(lock) == top_task)

Where top_task is C, this is true. The deadlock is reported back up to
userspace and C exits, killing all other threads and the app dies.

The problem here is that there was no deadlock. If we just ignored
this, as B had timed out and released L3, C could have gotten L3 and
continued normally.

As priority boosting is made to prevent unbounded latencies, and a
timeout grabbing of a lock is a bounded latency, I'm suggesting that we
do not bother boosting the owner or even treating the task as being
blocked.

Signed-off-by: Steven Rostedt <rostedt@goodmis.org>
---
diff --git a/kernel/locking/rtmutex.c b/kernel/locking/rtmutex.c
index aa4dff0..c8f2681 100644
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -520,6 +520,7 @@ static int try_to_take_rt_mutex(struct rt_mutex *lock, struct task_struct *task,
 static int task_blocks_on_rt_mutex(struct rt_mutex *lock,
 				   struct rt_mutex_waiter *waiter,
 				   struct task_struct *task,
+				   void *timeout,
 				   int detect_deadlock)
 {
 	struct task_struct *owner = rt_mutex_owner(lock);
@@ -538,7 +539,9 @@ static int task_blocks_on_rt_mutex(struct rt_mutex *lock,
 		top_waiter = rt_mutex_top_waiter(lock);
 	rt_mutex_enqueue(lock, waiter);
 
-	task->pi_blocked_on = waiter;
+	/* Treat locks with timeouts as not being blocked */
+	if (likely(!timeout))
+		task->pi_blocked_on = waiter;
 
 	raw_spin_unlock_irqrestore(&task->pi_lock, flags);
 
@@ -558,6 +561,13 @@ static int task_blocks_on_rt_mutex(struct rt_mutex *lock,
 	else if (debug_rt_mutex_detect_deadlock(waiter, detect_deadlock))
 		chain_walk = 1;
 
+	/*
+	 * If blocking with a timeout, then it's already bounded.
+	 * No priority boosting necessary.
+	 */
+	if (unlikely(timeout))
+		return 0;
+
 	if (!chain_walk)
 		return 0;
 
@@ -771,7 +781,8 @@ rt_mutex_slowlock(struct rt_mutex *lock, int state,
 			timeout->task = NULL;
 	}
 
-	ret = task_blocks_on_rt_mutex(lock, &waiter, current, detect_deadlock);
+	ret = task_blocks_on_rt_mutex(lock, &waiter, current, timeout,
+				      detect_deadlock);
 
 	if (likely(!ret))
 		ret = __rt_mutex_slowlock(lock, state, timeout, &waiter);
@@ -1088,7 +1099,7 @@ int rt_mutex_start_proxy_lock(struct rt_mutex *lock,
 		return 1;
 	}
 
-	ret = task_blocks_on_rt_mutex(lock, waiter, task, detect_deadlock);
+	ret = task_blocks_on_rt_mutex(lock, waiter, task, NULL, detect_deadlock);
 
 	if (ret && !rt_mutex_owner(lock)) {
 		/*

Re: [RFC PATCH] rtmutex: Do not prio boost when timeout is used

[Peter Zijlstra]

On Fri, Apr 25, 2014 at 04:28:48PM -0400, Steven Rostedt wrote:
> I've been discussing an issue on IRC with deadlock checking and found
> something wrong with it. Mainly, if any of the locks have a timeout,
> then even if the chain loops, there is no real deadlock. If one of the
> locks in the chain times out, then things will move forward again.


POSIX (opengroup):

 http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_mutex_timedlock.html

Explicitly states that pthread_mutex_timedlock() should participate in
the PI chain, it also states that its perfectly valid for this function
to return -EDEADLK.

Therefore, there's nothing wrong. If this behaviour breaks userspace,
its already broken for not actually expecting the right thing.

Re: [RFC PATCH] rtmutex: Do not prio boost when timeout is used

[Steven Rostedt]

On Sat, 26 Apr 2014 13:04:37 +0200
Peter Zijlstra <peterz@infradead.org> wrote:

> On Fri, Apr 25, 2014 at 04:28:48PM -0400, Steven Rostedt wrote:
> > I've been discussing an issue on IRC with deadlock checking and found
> > something wrong with it. Mainly, if any of the locks have a timeout,
> > then even if the chain loops, there is no real deadlock. If one of the
> > locks in the chain times out, then things will move forward again.
> 
> 
> POSIX (opengroup):
> 
>  http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_mutex_timedlock.html
> 
> Explicitly states that pthread_mutex_timedlock() should participate in
> the PI chain, it also states that its perfectly valid for this function
> to return -EDEADLK.
> 
> Therefore, there's nothing wrong. If this behaviour breaks userspace,
> its already broken for not actually expecting the right thing.

Fair enough. Thanks for the link.

-- Steve

Re: [RFC PATCH] rtmutex: Do not prio boost when timeout is used

[Thomas Gleixner]

On Fri, 25 Apr 2014, Steven Rostedt wrote:

> I've been discussing an issue on IRC with deadlock checking and found
> something wrong with it. Mainly, if any of the locks have a timeout,
> then even if the chain loops, there is no real deadlock. If one of the
> locks in the chain times out, then things will move forward again.
> 
> Now it may not be nice to have locks that do this, but we can break
> applications that use futex priority boosting and may use timeouts to
> break deadlocks.

And we rightfully break them. Using timeouts to work around potential
deadlocks is broken by definition.

We did forbid that forever, so no application developer can claim that
he had been using that before with PI futexes. It simply never worked.

If that application was using non PI futexes and worked around the
deadlock with timeouts and now decided to switch that broken code to
use PI, it's none of our problems and we are not going to change a
single line of code to support that brainfart.

> As priority boosting is made to prevent unbounded latencies, and a
> timeout grabbing of a lock is a bounded latency, I'm suggesting that we
> do not bother boosting the owner or even treating the task as being
> blocked.

That's complete and utter bullsh*it.

T1 holds A and tries to grab B

T2 holds B and tries to grab A with a timeout T. 

So T1 prevents T2 for time T to grab the lock, i.e. a (temporary)
deadlock. Depending on the requirements of T1, T might be well outside
the bounds which are critical for T1. That's still bounded by some
definition, but violates the bounds of T1.

Even the most basic "locking for dummies" cookbook will tell you that
if you need to take locks in reverse order the only sane thing is to
use trylock.

Aside of that you would penalize legitimate and sane users of timeouts
which suddenly would run into priority inversions for no good reason.

We really have better things to do, than changing the rules just to
please some random (probably commercial) application which has been
programmed along the coding rules from hell.

Thanks,

	tglx

Re: [RFC PATCH] rtmutex: Do not prio boost when timeout is used

[Steven Rostedt]

Glad I put on my shark repellent.

On Sun, 27 Apr 2014 20:20:26 +0200 (CEST)
Thomas Gleixner <tglx@linutronix.de> wrote:
> 
> We really have better things to do, than changing the rules just to
> please some random (probably commercial) application which has been
> programmed along the coding rules from hell.
> 

Peter had already pointed out that the current behavior is actually
specified by the standards. This patch is thus NULL and void. I only
posted this patch because you haven't bitched at me in a while and I
figured I was due.

I just noticed this when we were trying to debug why an application is
reporting EDEADLOCK on a lock. This was a side discussion as there were
no timeout locks in the application.

It looks more like a bug in the glibc implementation, as they have
both RECURSIVE and PRIO_INHERIT set on the mutex, and it seems that it
is deadlocking on a lock it already owns when it tries to retake it.

-- Steve