ipc/sem: Fix race between to-be-woken task and waker
PATCH 1/1 ipc/sem: Fix race between to-be-woken task and waker
While looking at a customr bug report about potential missed wakeup in the system V semaphore code, I spot a potential problem. The fact that semaphore waiter stays in TASK_RUNNING state while checking queue status may lead to missed wakeup if a spurious wakeup happens in the right moment as try_to_wake_up() will do nothing if the task state isn't right.
To eliminate this possibility, the task state is now reset to TASK_INTERRUPTIBLE immediately after wakeup before checking the queue status. This should eliminate the race condition on the interaction between the queue status and the task state and fix the potential missed wakeup problem.
--- ipc/sem.c | 21 ++++++++++++++++++++- 1 file changed, 20 insertions(+), 1 deletion(-)
ipc/sem.c +20 -1
@@ -2146,11 +2146,11 @@ static long do_semtimedop(int semid, struct sembuf __user *tsops, sma->complex_count++; } +__set_current_state (TASK_INTERRUPTIBLE ); do { WRITE_ONCE(queue.status, -EINTR); queue.sleeper = current; - __set_current_state(TASK_INTERRUPTIBLE); sem_unlock(sma, locknum); rcu_read_unlock();
@@ -2159,6 +2159,24 @@ static long do_semtimedop(int semid, struct sembuf __user *tsops,else schedule (); +/* +* A spurious wakeup at the right moment can cause race +* between the to-be-woken task and the waker leading to +* missed wakeup. Setting state back to TASK_INTERRUPTIBLE +* before checking queue.status will ensure that the race +* won't happen. +* +* CPU0 CPU1 +* +* <spurious wakeup> wake_up_sem_queue_prepare(): +* state = TASK_INTERRUPTIBLE status = error +* try_to_wake_up(): +* smp_mb() smp_mb() +* if (status == -EINTR) if (!(p->state & state)) +* schedule() goto out +*/ +set_current_state (TASK_INTERRUPTIBLE ); +/* * fastpath: the semop has completed, either successfully or * not, from the syscall pov, is quite irrelevant to us at this
@@ -2210,6 +2228,7 @@ static long do_semtimedop(int semid, struct sembuf __user *tsops,sem_unlock (sma, locknum);rcu_read_unlock (); out_free: +__set_current_state (TASK_RUNNING );if (sops != fast_sops)kvfree (sops);return error;
Signature · 1 line
2.18.1
Quoted 11 lines · Waiman Long
While looking at a customr bug report about potential missed wakeup in the system V semaphore code, I spot a potential problem. The fact that semaphore waiter stays in
TASK_RUNNINGstate while checking queue status may lead to missed wakeup if a spurious wakeup happens in the right moment astry_to_wake_up()will do nothing if the task state isn't right.To eliminate this possibility, the task state is now reset to
TASK_INTERRUPTIBLEimmediately after wakeup before checking the queue status. This should eliminate the race condition on the interaction between the queue status and the task state and fix the potential missed wakeup problem.
Bah, this code always makes my head hurt.
Yes, AFAICT the pattern it uses has been broken since 0a2b9d4c7967, since that removed doing the actual wakeup from under the sem_lock(), which is what it relies on.
Quoted 10 lines
Signed-off-by Waiman Long <[email protected]>--- ipc/sem.c | 21 ++++++++++++++++++++- 1 file changed, 20 insertions(+), 1 deletion(-)ipc/sem.c +0
-0
ipc/sem.c static long do_semtimedop(int semid, struct sembuf __user *tsops, · line 2149
Quoted 4 lines
ipc/sem.c +1
-0@@ -2146,11 +2146,11 @@ static long do_semtimedop(int semid, struct sembuf __user *tsops, sma->complex_count++; } +__set_current_state (TASK_INTERRUPTIBLE );
This can use a comment; this relies on the fact that this is in the same sem_lock() section that added us to the queue.
Quoted 44 lines
ipc/sem.c +19
-1do { WRITE_ONCE(queue.status, -EINTR); queue.sleeper = current; - __set_current_state(TASK_INTERRUPTIBLE); sem_unlock(sma, locknum); rcu_read_unlock();@@ -2159,6 +2159,24 @@ static long do_semtimedop(int semid, struct sembuf __user *tsops,else schedule (); +/* +* A spurious wakeup at the right moment can cause race +* between the to-be-woken task and the waker leading to +* missed wakeup. Setting state back to TASK_INTERRUPTIBLE +* before checking queue.status will ensure that the race +* won't happen. +* +* CPU0 CPU1 +* +* <spurious wakeup> wake_up_sem_queue_prepare(): +* state = TASK_INTERRUPTIBLE status = error +* try_to_wake_up(): +* smp_mb() smp_mb() +* if (status == -EINTR) if (!(p->state & state)) +* schedule() goto out +*/ +set_current_state (TASK_INTERRUPTIBLE ); +/* * fastpath: the semop has completed, either successfully or * not, from the syscall pov, is quite irrelevant to us at this @@ -2210,6 +2228,7 @@ static long do_semtimedop(int semid, struct sembuf __user *tsops,sem_unlock (sma, locknum);rcu_read_unlock (); out_free: +__set_current_state (TASK_RUNNING );if (sops != fast_sops)kvfree (sops);return error;Signature · 1 line
2.18.1
Quoted 12 lines · Peter Zijlstra
Quoted 11 lines · Waiman Long
While looking at a customr bug report about potential missed wakeup in the system V semaphore code, I spot a potential problem. The fact that semaphore waiter stays in
TASK_RUNNINGstate while checking queue status may lead to missed wakeup if a spurious wakeup happens in the right moment astry_to_wake_up()will do nothing if the task state isn't right.To eliminate this possibility, the task state is now reset to
TASK_INTERRUPTIBLEimmediately after wakeup before checking the queue status. This should eliminate the race condition on the interaction between the queue status and the task state and fix the potential missed wakeup problem.
Quoted 5 lines
Bah, this code always makes my head hurt.
Yes, AFAICT the pattern it uses has been broken since
0a2b9d4c7967, since that removed doing the actual wakeup from under thesem_lock(), which is what it relies on.
After having a second look at the code again, I probably misread the code the first time around. In the sleeping path, there is a check of queue.status and setting of task state both under the sem lock in the sleeping path. So as long as setting of queue status is under lock, they should synchronize properly.
It looks like queue status setting is under lock, but I can't use lockdep to confirm that as the locking can be done by either the array lock or in one of the spinlocks in the array. Are you aware of a way of doing that?
Anyway, I do think we need to add some comment to clarify the situation to avoid future confusion.
Cheers,
Longman
Hi,
Quoted 8 lines · Waiman Long
Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · Waiman Long
While looking at a customr bug report about potential missed wakeup in the system V semaphore code, I spot a potential problem. The fact that semaphore waiter stays in
TASK_RUNNINGstate while checking queue status may lead to missed wakeup if a spurious wakeup happens in the right moment astry_to_wake_up()will do nothing if the task state isn't right.
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
To eliminate this possibility, the task state is now reset to
TASK_INTERRUPTIBLEimmediately after wakeup before checking the queue status. This should eliminate the race condition on the interaction between the queue status and the task state and fix the potential missed wakeup problem.
You are obviously right, there is a huge race condition.
Quoted 5 lines
Quoted 5 lines
Bah, this code always makes my head hurt.
Yes, AFAICT the pattern it uses has been broken since
0a2b9d4c7967, since that removed doing the actual wakeup from under thesem_lock(), which is what it relies on.
Correct - I've overlooked that.
First, theory:
setting queue->status, reading queue->status, setting current->state=TASK_INTERRUPTIBLE are all under the correct spinlock.
(there is an opportunistic read of queue->status without locks, but it is retried when the lock got acquired)
setting current->state=RUNNING is outside of any lock.
So as far as current->state is concerned, the lock doesn't exist. And if the lock doesn't exist, we must follow the rules applicable for set_current_state().
I'll try to check the code this week.
And we should check the remaining wake-queue users, the logic is everywhere identical.
Quoted 10 lines
After having a second look at the code again, I probably misread the code the first time around. In the sleeping path, there is a check of queue.status and setting of task state both under the sem lock in the sleeping path. So as long as setting of queue status is under lock, they should synchronize properly.
It looks like queue status setting is under lock, but I can't use lockdep to confirm that as the locking can be done by either the array lock or in one of the spinlocks in the array. Are you aware of a way of doing that?
For testing? Have you considered just always using the global lock?
(untested):
ipc/sem.c +0 -0
@@ -370,7 +370,7 @@ static inline int sem_lock(struct sem_array *sma, struct sembuf *sops,
struct sem *sem;
int idx;
- if (nsops != 1) {
+ if (nsops != 1 || 1) {
/* Complex operation - acquire a full lock */ ipc_lock_object(&sma->sem_perm);
Quoted 2 lines
Anyway, I do think we need to add some comment to clarify the situation to avoid future confusion.
Around line 190 is the comment that explains locking & memory ordering.
I have only documented the content of sem_undo and sem_array, but neither queue nor current->state :-(
--
Manfred