Kernel bug in futex_wait, cause application hang with NPTL
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
Few weeks ago, I was asked to research a trace of an application which hangs with NPTL but runs with LinuxThread. In the result I found a problem in futex. I made a patch and confirmed that my fix make an application to work with NPTL.
Last week I explained it to Rusty, and today I received following mail from Ingo.
Andrew, please read Ingo's mail and fix this kernel bug in 2.6. (Only 2.4 patchs are here... but port to 2.6 is strongly recommended.)
I sure that this fix would deliver many thread applications from a certain death.
Thank you for your kind cooperation, Rusty, Ingo, Jakub and all concerning experts.
H.Seto
-----
Quoted 85 lines · Ingo Molnar
Seto san, please find Jakub's reply below. He too agrees with your analysis and patch. Please send it to Andrew for upstream inclusion, i think it should get into 2.6.9.
Signed-off-by Ingo Molnar <[email protected]>Ingo
Quoted 1 line · Ingo Molnar
hm, looks like a valid observation?
To my knowledge NPTL never even looks at return value from futex (x,
FUTEX_WAIT, ...).
The problem as I understand from his explanation is not about return value, but a race:CPU0 CPU1 CPU2
FUTEX_WAIT(val = 0)
...
if (curval (== 1) != val (== 0)) {unlock_futex_mm();
ret =-EWOULDBLOCK;
goto out;
}FUTEX_WAIT (val = 1) ... add_wait_queue(&q.waiters, &wait); set_current_state(TASK_INTERRUPTIBLE); if (!list_empty(&q.list)) { unlock_futex_mm(); time = schedule_timeout(time); FUTEX_WAKE (nr = 1) If at this point it is possible that FUTEX_WAKE awakes CPU0's task (which is not really waiting) instead of CPU1's task, there is a kernel bugout:
...
/* Were we woken up anyway? */
if (!unqueue_me(&q))
ret = 0;put_page(q.page);
return ret;When kernel decides a
FUTEX_WAITwill return with-EWOULDBLOCK, it shouldn't be on the futex queue already, as it was already awaken by the curval != val, so it must not be doubly awaken.For RHEL3 the cure ought to be easy, either replace
unlock_futex_mm();
ret =-EWOULDBLOCK;
goto out;with
list_del(&q.list);__detach_vcache(&q.vcache);put_page(q.page);
return-EWOULDBLOCK;or move
__queue_meafter the curval != val check and justput_page(q.page); return-EWOULDBLOCKthere.
futex_lockandvcache_lockare held from before the current__queue_mecall until after this curval != val check, so I believe no FUTEX_WAKE/REQUEUE/CMP_REQUEUE call can make a difference here.Which means his patch looks correct.
What I don't understand at all about RHEL3 code is:
add_wait_queue(&q.waiters, &wait); set_current_state(TASK_INTERRUPTIBLE); if (!list_empty(&q.list)) { unlock_futex_mm(); time = schedule_timeout(time); } set_current_state(TASK_RUNNING);1) I don't imagine how q.list can be empty here, futex_lock/vcache_lock are still held
2) if it for some reason is empty, then we are in bad trouble, asunlock_futex_mm()is not called, so IMHO we get stuck inunqueue_mebecause it tries to acquirevcache_lockwhich is already held by the current task
Quoted 7 lines
2.6.x
futex.cis very different, but I would guess there is similar problem, though not sure which lock protects stuff while doing curval != val check.Jakub
-----------------------------------------------------
My temporary patch for futex(RHEL3) is here:
kernel/futex.c +20 -13
@@ -297,14 +297,20 @@spin_lock (&vcache_lock);spin_lock (&futex_lock); + ret =__unqueue_me (q); +spin_unlock (&futex_lock); +spin_unlock (&vcache_lock); +return ret; +} + +static inline int __unqueue_me (struct futex_q *q) +{if (!list_empty (&q->list)) {list_del (&q->list);__detach_vcache (&q->vcache); - ret =1 ; +return 1 ; } -spin_unlock (&futex_lock); -spin_unlock (&vcache_lock); -return ret; +return 0 ; } static inline int futex_wait(unsigned long uaddr,
@@ -333,13 +339,18 @@* Page is pinned, but may no longer be in this address space. * It cannot schedule, so we access it with the spinlock held. */ -if (!access_ok (VERIFY_READ , uaddr,4 )) - goto out_fault; +if (!access_ok (VERIFY_READ , uaddr,4 )) { +__unqueue_me (&q); +unlock_futex_mm (); + ret = -EFAULT ; + goto out; + } kaddr =kmap_atomic (page,KM_USER0 ); curval = *(int *)(kaddr + offset);kunmap_atomic (kaddr,KM_USER0 );if (curval != val) { +__unqueue_me (&q);unlock_futex_mm (); ret = -EWOULDBLOCK ; goto out;
@@ -364,22 +375,18 @@*/ if (time ==0 ) { ret = -ETIMEDOUT ; - goto out; + goto out_wait; }if (signal_pending (current)) ret = -EINTR ; -out: +out_wait:/* Were we woken up anyway? */ if (!unqueue_me (&q)) ret =0 ; +out:put_page (q.page);return ret; - -out_fault: -unlock_futex_mm (); - ret = -EFAULT ; - goto out; } long do_futex(unsigned long uaddr, int op, int val, unsigned long timeout,
-----------------------------------------------------
Refined version by Jakub:
Quoted 3 lines
Well, I think it would be cheaper to just move the
__queue_mecall down, as in (untested RHEL3 patch below).
The 2.6.9 patch will likely be quite different though.
kernel/futex.c +14 -12
@@ -346,23 +346,26 @@ static inline int futex_wait(unsigned lounlock_futex_mm ();return -EFAULT ; } -__queue_me (&q, page, uaddr, offset,-1 ,NULL );/* * Page is pinned, but may no longer be in this address space. * It cannot schedule, so we access it with the spinlock held. */ -if (!access_ok (VERIFY_READ , uaddr,4 )) - goto out_fault; +if (!access_ok (VERIFY_READ , uaddr,4 )) { + ret = -EFAULT ; + goto out_unlock; + } kaddr =kmap_atomic (page,KM_USER0 ); curval = *(int *)(kaddr + offset);kunmap_atomic (kaddr,KM_USER0 );if (curval != val) { -unlock_futex_mm (); ret = -EWOULDBLOCK ; - goto out; + goto out_unlock; } + +__queue_me (&q, page, uaddr, offset,-1 ,NULL ); +/* * The get_user() above might fault and schedule so we * cannot just set TASK_INTERRUPTIBLE state when queueing
@@ -372,10 +375,9 @@ static inline int futex_wait(unsigned lo*/ add_wait_queue (&q.waiters, &wait);set_current_state (TASK_INTERRUPTIBLE ); -if (!list_empty (&q.list)) { -unlock_futex_mm (); - time =schedule_timeout (time); - } +BUG_ON (list_empty (&q.list)); +unlock_futex_mm (); + time =schedule_timeout (time);set_current_state (TASK_RUNNING );/* * NOTE: we don't remove ourselves from the waitqueue because
@@ -395,10 +397,10 @@ out:return ret; -out_fault: +out_unlock:unlock_futex_mm (); - ret = -EFAULT ; - goto out; +put_page (q.page); +return ret; } long do_futex(unsigned long uaddr, int op, int val, unsigned long timeout,