[PATCH 0/2] futex: requeue_pi lock steal deadlock fixes

[PATCH 0/2] futex: requeue_pi lock steal deadlock fixes

[Darren Hart]

[resend: quilt mail wasn't making it to the lists for some reason]

The following patch series addresses a deadlock and a race related to the
newly introduced requeue_pi futex op codes.  I discovered this while running
I modified version of pthread_cond_many from ltp/testcases/realtime (with a PI
aware mutex) and a patched glibc (for new futex op codes).  These patches fix
the deadlock and close the race window considerably - but not 100%.  My test
case, however, now runs to completion without deadlock, and without triggering
the pi_state related WARN_ON()'s.

-- 
Darren Hart
IBM Linux Technology Center
Real-Time Linux Team

[PATCH 1/2] Update woken requeued futex_q lock_ptr

[Darren Hart]

futex_requeue() can acquire the lock on behalf of a waiter during the requeue
loop in the event of a lock steal or owner died. futex_wait_requeue_pi() cleans
up the pi_state owner, using the lock_ptr to protect against concurrent access
to the pi_state.  The pi_state is found on the requeue target futex hash bucket
so the lock_ptr needs to be updated accordingly.  The problem manifested by
triggering the WARN_ON in lookup_pi_state() about the pid != pi_state->owner
pid. 

The astute reviewer will note that still exists a race between the time
futex_requeue() releases hb2->lock() and the time when futex_wait_requeue_pi()
acquires it.  During this time the pi_state and the futex uaddr are not in sync
with the rt_mutex ownership.  This patch closes the window to the point where
my tests now pass, but we still need to address it.

Note: Please apply to mainline and rt

Signed-off-by: Darren Hart <dvhltc@us.ibm.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Ingo Molnar <mingo@elte.hu>
CC: Dinakar Guniguntala <dino@in.ibm.com>
CC: John Stultz <johnstul@us.ibm.com>
CC: John Kacur <jkacur@redhat.com>

Index: 2.6.31-rc4-rt1/kernel/futex.c
===================================================================
--- 2.6.31-rc4-rt1.orig/kernel/futex.c	2009-08-05 10:00:56.000000000 -0700
+++ 2.6.31-rc4-rt1/kernel/futex.c	2009-08-05 10:29:56.000000000 -0700
@@ -1059,19 +1059,24 @@ void requeue_futex(struct futex_q *q, st
  * requeue_pi_wake_futex() - Wake a task that acquired the lock during requeue
  * q:	the futex_q
  * key:	the key of the requeue target futex
+ * hb:  the hash_bucket of the requeue target futex
  *
  * During futex_requeue, with requeue_pi=1, it is possible to acquire the
  * target futex if it is uncontended or via a lock steal.  Set the futex_q key
  * to the requeue target futex so the waiter can detect the wakeup on the right
  * futex, but remove it from the hb and NULL the rt_waiter so it can detect
- * atomic lock acquisition.  Must be called with the q->lock_ptr held.
+ * atomic lock acquisition.  Set the q->lock_ptr to the requeue target hb->lock
+ * to protect access to the pi_state to fixup the owner later.  Must be called
+ * with the q->lock_ptr held.
  */
 static inline
-void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key)
+void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key,
+			   struct futex_hash_bucket *hb)
 {
 	drop_futex_key_refs(&q->key);
 	get_futex_key_refs(key);
 	q->key = *key;
+	q->lock_ptr = &hb->lock;
 
 	WARN_ON(plist_node_empty(&q->list));
 	plist_del(&q->list, &q->list.plist);
@@ -1137,7 +1142,7 @@ static int futex_proxy_trylock_atomic(u3
 	ret = futex_lock_pi_atomic(pifutex, hb2, key2, ps, top_waiter->task,
 				   set_waiters);
 	if (ret == 1)
-		requeue_pi_wake_futex(top_waiter, key2);
+		requeue_pi_wake_futex(top_waiter, key2, hb2);
 
 	return ret;
 }
@@ -1323,7 +1328,7 @@ retry_private:
 							this->task, 1);
 			if (ret == 1) {
 				/* We got the lock. */
-				requeue_pi_wake_futex(this, &key2);
+				requeue_pi_wake_futex(this, &key2, hb2);
 				continue;
 			} else if (ret) {
 				/* -EDEADLK */

-- 
Darren Hart
IBM Linux Technology Center
Real-Time Linux Team

Re: [PATCH 1/2] Update woken requeued futex_q lock_ptr

[Darren Hart]

Darren Hart wrote:
> futex_requeue() can acquire the lock on behalf of a waiter during the 
> requeue
> loop in the event of a lock steal or owner died. futex_wait_requeue_pi() 
> cleans
> up the pi_state owner, using the lock_ptr to protect against concurrent 
> access
> to the pi_state.  The pi_state is found on the requeue target futex hash 
> bucket
> so the lock_ptr needs to be updated accordingly.  The problem manifested by
> triggering the WARN_ON in lookup_pi_state() about the pid != 
> pi_state->owner
> pid.
> The astute reviewer will note that still exists a race between the time
> futex_requeue() releases hb2->lock() and the time when 
> futex_wait_requeue_pi()
> acquires it.  During this time the pi_state and the futex uaddr are not 
> in sync
> with the rt_mutex ownership.  This patch closes the window to the point 
> where
> my tests now pass, but we still need to address it.
> 
> Note: Please apply to mainline and rt
> 


> static inline
> -void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key)
> +void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key,
> +               struct futex_hash_bucket *hb)
> {
>     drop_futex_key_refs(&q->key);
>     get_futex_key_refs(key);
>     q->key = *key;
> +    q->lock_ptr = &hb->lock;

Hrm... turns out changing this breaks the 
handle_early_requeue_pi_wakeup() logic.  I'll have to respin this patch 
to account for that as well.  Please hold off on this patch.

-- 
Darren Hart
IBM Linux Technology Center
Real-Time Linux Team

Re: [PATCH 1/2] Update woken requeued futex_q lock_ptr

[Darren Hart]

Darren Hart wrote:
> Darren Hart wrote:
>> futex_requeue() can acquire the lock on behalf of a waiter during the 
>> requeue
>> loop in the event of a lock steal or owner died. 
>> futex_wait_requeue_pi() cleans
>> up the pi_state owner, using the lock_ptr to protect against 
>> concurrent access
>> to the pi_state.  The pi_state is found on the requeue target futex 
>> hash bucket
>> so the lock_ptr needs to be updated accordingly.  The problem 
>> manifested by
>> triggering the WARN_ON in lookup_pi_state() about the pid != 
>> pi_state->owner
>> pid.
>> The astute reviewer will note that still exists a race between the time
>> futex_requeue() releases hb2->lock() and the time when 
>> futex_wait_requeue_pi()
>> acquires it.  During this time the pi_state and the futex uaddr are 
>> not in sync
>> with the rt_mutex ownership.  This patch closes the window to the 
>> point where
>> my tests now pass, but we still need to address it.
>>
>> Note: Please apply to mainline and rt
>>
> 
> 
>> static inline
>> -void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key)
>> +void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key,
>> +               struct futex_hash_bucket *hb)
>> {
>>     drop_futex_key_refs(&q->key);
>>     get_futex_key_refs(key);
>>     q->key = *key;
>> +    q->lock_ptr = &hb->lock;
> 
> Hrm... turns out changing this breaks the 
> handle_early_requeue_pi_wakeup() logic.  I'll have to respin this patch 
> to account for that as well.  Please hold off on this patch.

In fact, this doesn't affect the handle_early_requeue_pi_wakeup() code 
in the slightest.  It only needs to hold a hb->lock (either one is 
adequate) to ensure the requeue routine has completed.  By changing the 
q->lock_ptr of the waiter to hb2->lock we ensure the pi_state is 
protected from concurrent access by futex_wait_requeue_pi() and new 
contending threads.

Ingo, please apply to tip/urgent.

Thanks,

-- 
Darren Hart
IBM Linux Technology Center
Real-Time Linux Team

[tip:core/urgent] futex: Update woken requeued futex_q lock_ptr

[tip-bot for Darren Hart]

Commit-ID:  00235fe25eba6d3a13f3349b2e3a2d94b699a414
Gitweb:     http://git.kernel.org/tip/00235fe25eba6d3a13f3349b2e3a2d94b699a414
Author:     Darren Hart <dvhltc@us.ibm.com>
AuthorDate: Wed, 5 Aug 2009 15:02:20 -0700
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Sat, 8 Aug 2009 17:21:49 +0200

futex: Update woken requeued futex_q lock_ptr

futex_requeue() can acquire the lock on behalf of a waiter
during the requeue loop in the event of a lock steal or owner
died. futex_wait_requeue_pi() cleans up the pi_state owner,
using the lock_ptr to protect against concurrent access to the
pi_state.  The pi_state is found on the requeue target futex
hash bucket so the lock_ptr needs to be updated accordingly.

The problem manifested by triggering the WARN_ON in
lookup_pi_state() about the pid != pi_state->owner pid.

The astute reviewer will note that still exists a race between
the time futex_requeue() releases hb2->lock() and the time when
futex_wait_requeue_pi() acquires it.  During this time the
pi_state and the futex uaddr are not in sync with the rt_mutex
ownership.  This patch closes the window to the point where my
tests now pass, but we still need to address it.

Signed-off-by: Darren Hart <dvhltc@us.ibm.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Dinakar Guniguntala <dino@in.ibm.com>
Cc: John Stultz <johnstul@us.ibm.com>
Cc: John Kacur <jkacur@redhat.com>
Cc: <stable@kernel.org>
LKML-Reference: <4A7A016C.1090002@us.ibm.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>


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

diff --git a/kernel/futex.c b/kernel/futex.c
index 0672ff8..57f5a80 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -1010,19 +1010,24 @@ void requeue_futex(struct futex_q *q, struct futex_hash_bucket *hb1,
  * requeue_pi_wake_futex() - Wake a task that acquired the lock during requeue
  * q:	the futex_q
  * key:	the key of the requeue target futex
+ * hb:  the hash_bucket of the requeue target futex
  *
  * During futex_requeue, with requeue_pi=1, it is possible to acquire the
  * target futex if it is uncontended or via a lock steal.  Set the futex_q key
  * to the requeue target futex so the waiter can detect the wakeup on the right
  * futex, but remove it from the hb and NULL the rt_waiter so it can detect
- * atomic lock acquisition.  Must be called with the q->lock_ptr held.
+ * atomic lock acquisition.  Set the q->lock_ptr to the requeue target hb->lock
+ * to protect access to the pi_state to fixup the owner later.  Must be called
+ * with the q->lock_ptr held.
  */
 static inline
-void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key)
+void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key,
+			   struct futex_hash_bucket *hb)
 {
 	drop_futex_key_refs(&q->key);
 	get_futex_key_refs(key);
 	q->key = *key;
+	q->lock_ptr = &hb->lock;
 
 	WARN_ON(plist_node_empty(&q->list));
 	plist_del(&q->list, &q->list.plist);
@@ -1088,7 +1093,7 @@ static int futex_proxy_trylock_atomic(u32 __user *pifutex,
 	ret = futex_lock_pi_atomic(pifutex, hb2, key2, ps, top_waiter->task,
 				   set_waiters);
 	if (ret == 1)
-		requeue_pi_wake_futex(top_waiter, key2);
+		requeue_pi_wake_futex(top_waiter, key2, hb2);
 
 	return ret;
 }
@@ -1273,7 +1278,7 @@ retry_private:
 							this->task, 1);
 			if (ret == 1) {
 				/* We got the lock. */
-				requeue_pi_wake_futex(this, &key2);
+				requeue_pi_wake_futex(this, &key2, hb2);
 				continue;
 			} else if (ret) {
 				/* -EDEADLK */

[tip:core/urgent] futex: Update woken requeued futex_q lock_ptr

[tip-bot for Darren Hart]

Commit-ID:  4047446de8fa83d8d5922e9448eb0cbb7ac3f475
Gitweb:     http://git.kernel.org/tip/4047446de8fa83d8d5922e9448eb0cbb7ac3f475
Author:     Darren Hart <dvhltc@us.ibm.com>
AuthorDate: Wed, 5 Aug 2009 15:02:20 -0700
Committer:  Ingo Molnar <mingo@elte.hu>
CommitDate: Sun, 9 Aug 2009 22:20:07 +0200

futex: Update woken requeued futex_q lock_ptr

futex_requeue() can acquire the lock on behalf of a waiter early on
or during the requeue loop if it is uncontended or in the event of a
lock steal or owner died. On wakeup, the waiter (in
futex_wait_requeue_pi()) cleans up the pi_state owner using the
lock_ptr to protect against concurrent access to the pi_state. The
pi_state is hung off futex_q's on the requeue target futex hash
bucket so the lock_ptr needs to be updated accordingly.

The problem manifested by triggering the WARN_ON in
lookup_pi_state() about the pid != pi_state->owner->pid.  With this
patch, the pi_state is properly guarded against concurrent access
via the requeue target hb lock.

The astute reviewer may notice that there is a window of time
between when futex_requeue() unlocks the hb locks and when
futex_wait_requeue_pi() will acquire hb2->lock.  During this time
the pi_state and uval are not in sync with the underlying rtmutex
owner (but the uval does indicate there are waiters, so no atomic
changes will occur in userspace).  However, this is not a problem.
Should a contending thread enter lookup_pi_state() and acquire
hb2->lock before the ownership is fixed up, it will find the
pi_state hung off a waiter's (possibly the pending owner's) futex_q
and block on the rtmutex.  Once futex_wait_requeue_pi() fixes up the
owner, it will also move the pi_state from the old owner's
task->pi_state_list to its own.

Signed-off-by: Darren Hart <dvhltc@us.ibm.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Dinakar Guniguntala <dino@in.ibm.com>
Cc: John Stultz <johnstul@us.ibm.com>
Cc: John Kacur <jkacur@redhat.com>
Cc: <stable@kernel.org>
LKML-Reference: <4A7A016C.1090002@us.ibm.com>
Signed-off-by: Ingo Molnar <mingo@elte.hu>


---
 kernel/futex.c |   17 +++++++++++++----
 1 files changed, 13 insertions(+), 4 deletions(-)

diff --git a/kernel/futex.c b/kernel/futex.c
index 0672ff8..ca99305 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -1010,15 +1010,19 @@ void requeue_futex(struct futex_q *q, struct futex_hash_bucket *hb1,
  * requeue_pi_wake_futex() - Wake a task that acquired the lock during requeue
  * q:	the futex_q
  * key:	the key of the requeue target futex
+ * hb:  the hash_bucket of the requeue target futex
  *
  * During futex_requeue, with requeue_pi=1, it is possible to acquire the
  * target futex if it is uncontended or via a lock steal.  Set the futex_q key
  * to the requeue target futex so the waiter can detect the wakeup on the right
  * futex, but remove it from the hb and NULL the rt_waiter so it can detect
- * atomic lock acquisition.  Must be called with the q->lock_ptr held.
+ * atomic lock acquisition.  Set the q->lock_ptr to the requeue target hb->lock
+ * to protect access to the pi_state to fixup the owner later.  Must be called
+ * with both q->lock_ptr and hb->lock held.
  */
 static inline
-void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key)
+void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key,
+			   struct futex_hash_bucket *hb)
 {
 	drop_futex_key_refs(&q->key);
 	get_futex_key_refs(key);
@@ -1030,6 +1034,11 @@ void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key)
 	WARN_ON(!q->rt_waiter);
 	q->rt_waiter = NULL;
 
+	q->lock_ptr = &hb->lock;
+#ifdef CONFIG_DEBUG_PI_LIST
+	q->list.plist.slock = &hb->lock;
+#endif
+
 	wake_up_state(q->task, TASK_NORMAL);
 }
 
@@ -1088,7 +1097,7 @@ static int futex_proxy_trylock_atomic(u32 __user *pifutex,
 	ret = futex_lock_pi_atomic(pifutex, hb2, key2, ps, top_waiter->task,
 				   set_waiters);
 	if (ret == 1)
-		requeue_pi_wake_futex(top_waiter, key2);
+		requeue_pi_wake_futex(top_waiter, key2, hb2);
 
 	return ret;
 }
@@ -1273,7 +1282,7 @@ retry_private:
 							this->task, 1);
 			if (ret == 1) {
 				/* We got the lock. */
-				requeue_pi_wake_futex(this, &key2);
+				requeue_pi_wake_futex(this, &key2, hb2);
 				continue;
 			} else if (ret) {
 				/* -EDEADLK */

Re: [tip:core/urgent] futex: Update woken requeued futex_q lock_ptr

[Ingo Molnar]

* tip-bot for Darren Hart <dvhltc@us.ibm.com> wrote:

> @@ -1030,6 +1034,11 @@ void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key)
>  	WARN_ON(!q->rt_waiter);
>  	q->rt_waiter = NULL;
>  
> +	q->lock_ptr = &hb->lock;
> +#ifdef CONFIG_DEBUG_PI_LIST
> +	q->list.plist.slock = &hb->lock;
> +#endif
> +
>  	wake_up_state(q->task, TASK_NORMAL);
>  }
>  

-tip testing found a build error with v2 of the patch:

kernel/futex.c: In function ‘requeue_pi_wake_futex’:
kernel/futex.c:1039: error: ‘struct plist_head’ has no member named ‘slock’

	Ingo

Re: [tip:core/urgent] futex: Update woken requeued futex_q lock_ptr

[Darren Hart]

Ingo Molnar wrote:
> * tip-bot for Darren Hart <dvhltc@us.ibm.com> wrote:
> 
>> @@ -1030,6 +1034,11 @@ void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key)
>>  	WARN_ON(!q->rt_waiter);
>>  	q->rt_waiter = NULL;
>>  
>> +	q->lock_ptr = &hb->lock;
>> +#ifdef CONFIG_DEBUG_PI_LIST
>> +	q->list.plist.slock = &hb->lock;
>> +#endif
>> +
>>  	wake_up_state(q->task, TASK_NORMAL);
>>  }
>>  
> 
> -tip testing found a build error with v2 of the patch:
> 
> kernel/futex.c: In function ‘requeue_pi_wake_futex’:
> kernel/futex.c:1039: error: ‘struct plist_head’ has no member named ‘slock’

I've been developing on -rt, and the plist implementation changed with:

34ca9f9b  spinlocks: Create atomic_spinlock and convert rq->lock

Apologies for not catching that.  I'll send out V3 of this patch, one 
for mainline, and one for -rt.  Is prefacing the patch with [RT] the 
preferred way to distinguish mainline and -rt patches?

Thanks,

-- 
Darren Hart
IBM Linux Technology Center
Real-Time Linux Team

Re: [tip:core/urgent] futex: Update woken requeued futex_q lock_ptr

[Darren Hart]

Ingo Molnar wrote:
> * tip-bot for Darren Hart <dvhltc@us.ibm.com> wrote:
> 
>> @@ -1030,6 +1034,11 @@ void requeue_pi_wake_futex(struct futex_q *q, union futex_key *key)
>>  	WARN_ON(!q->rt_waiter);
>>  	q->rt_waiter = NULL;
>>  
>> +	q->lock_ptr = &hb->lock;
>> +#ifdef CONFIG_DEBUG_PI_LIST
>> +	q->list.plist.slock = &hb->lock;
>> +#endif
>> +
>>  	wake_up_state(q->task, TASK_NORMAL);
>>  }
>>  
> 
> -tip testing found a build error with v2 of the patch:
> 
> kernel/futex.c: In function ‘requeue_pi_wake_futex’:
> kernel/futex.c:1039: error: ‘struct plist_head’ has no member named ‘slock’

Ingo,

I'm finding myself confused by the tip branches.  I was going to prepare 
you a "mainline" version of this patch, but tip/core-for-linus-2 doesn't 
have the original requeue_pi support in futex.c, while tag v2.6.31-rc5 
does have that support.

I'll prepare a patch against v2.6.31-rc5, but can you explain how you 
would prefer for people to send patches that are needed in both mainline 
and rt, but have slightly different implementations?

-- 
Darren Hart
IBM Linux Technology Center
Real-Time Linux Team

[PATCH 2/2][RT] Avoid deadlock in rt_mutex_start_proxy_lock()

[Darren Hart]

In the event of a lock steal or owner died, rt_mutex_start_proxy_lock() will
give the rt_mutex to the waiting task, but it fails to release the wait_lock.
This leads to subsequent deadlocks when other tasks try to acquire the
rt_mutex.

I also removed a few extra blank lines that really spaced this routine out.
I must have been high on the \n when I wrote this originally...

Note: this is the -rt version, I'll send another for mainline.

Signed-off-by: Darren Hart <dvhltc@us.ibm.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Ingo Molnar <mingo@elte.hu>
CC: Dinakar Guniguntala <dino@in.ibm.com>
CC: John Stultz <johnstul@us.ibm.com>
CC: John Kacur <jkacur@redhat.com>

Index: 2.6.31-rc4-rt1/kernel/rtmutex.c
===================================================================
--- 2.6.31-rc4-rt1.orig/kernel/rtmutex.c	2009-08-05 10:29:39.000000000 -0700
+++ 2.6.31-rc4-rt1/kernel/rtmutex.c	2009-08-05 11:10:22.000000000 -0700
@@ -1517,9 +1517,8 @@ int rt_mutex_start_proxy_lock(struct rt_
 	    try_to_steal_lock(lock, task, STEAL_NORMAL)) {
 		/* We got the lock for task. */
 		debug_rt_mutex_lock(lock);
-
 		rt_mutex_set_owner(lock, task, 0);
-
+		atomic_spin_unlock_irqrestore(&lock->wait_lock, flags);
 		rt_mutex_deadlock_account_lock(lock, task);
 		return 1;
 	}
@@ -1527,7 +1526,6 @@ int rt_mutex_start_proxy_lock(struct rt_
 	ret = task_blocks_on_rt_mutex(lock, waiter, task, detect_deadlock,
 				      flags);
 
-
 	if (ret && !waiter->task) {
 		/*
 		 * Reset the return value. We might have

-- 
Darren Hart
IBM Linux Technology Center
Real-Time Linux Team