ipc/sem.c: Lockup with complex ops, comments not updated
Hi Rik,
I like your change to the ipc/sem locking:
A scheme with a per-semaphore lock and without the overhead of always acquiring both the global and the per-semaphore lock.
But:
1) I found one bug with your sem locking changes:
If
- a complex operation is sleeping [would be woken up by update_queue(,-1)]
- a simple op is sleeping
- the success of the simple op would allow the complex op to complete [i.e.: update_queue(,sem_num) changes the semaphore value to the
value that the complex op waits on]
- an operation wakes up the simple op.
then the complex op is not woken up.
One fix would be a loop in do_smart_update():
- first check the global queue
- then the per-semaphore queues
- if one of the per-semaphore queues made progress: check the global queue again
- if the global queue made progress: check the per semaphore queues again
...
2) Your patches remove FIFO ordering of the wakeups:
As far as I can see complex ops are now preferred over simple ops. It's not a bug, noone exept linux implements FIFO.
But the comment it line 28 should be updated
Should I write a patch, do you want to fix it yourself?
--
Manfred
PATCH 1/1 ipc,sem: move restart loop to do_smart_update
Quoted 6 lines · On Sat, 18 May 2013 15:48:06 +0200 Manfred Spraul <[email protected]>…
Hi Rik,
I like your change to the ipc/sem locking:
A scheme with a per-semaphore lock and without the overhead of always acquiring both the global and the per-semaphore lock.
Quoted 9 lines
But:
1) I found one bug with your sem locking changes:
If
- a complex operation is sleeping [would be woken up byupdate_queue(,-1)]
- a simple op is sleeping
- the success of the simple op would allow the complex op to complete [i.e.:update_queue(,sem_num)changes the semaphore value to the
value that the complex op waits on]
- an operation wakes up the simple op.
Are you referring to eg. a complex operation that waits for several semaphores to turn 0, and a simple op that subtracts 1 from a semaphore, turning it into 0?
Quoted 9 lines
then the complex op is not woken up.
One fix would be a loop in
do_smart_update():
- first check the global queue
- then the per-semaphore queues
- if one of the per-semaphore queues made progress: check the global queue again
- if the global queue made progress: check the per semaphore queues again
...
Would that be as simple as making do_smart_update() loop back to the top if update_queue on a single semaphore's queue returns a non-zero value (something was changed), and there are complex operations pending?
I implemented that in the patch below.
Quoted 6 lines
2) Your patches remove FIFO ordering of the wakeups:
As far as I can see complex ops are now preferred over simple ops. It's not a bug, noone exept linux implements FIFO.
But the comment it line 28 should be updatedShould I write a patch, do you want to fix it yourself?
You seem to have looked at this problem more closely than I have, so I would appreciate it if you could review this patch :)
---8<---
Subject: ipc,sem: move restart loop to do_smart_update
A complex operation may be sleeping on a semaphore to become a certain value. A sleeping simple operation may turn the semaphore into that value.
Having the restart loop inside update_queue means we may be missing the complex operation (which lives on a different queue), and result in a semaphore lockup.
The lockup can be avoided by moving the restart loop into do_smart_update, so the list of pending complex operations will also be checked if required.
--- ipc/sem.c | 44 +++++++++++++++++++++----------------------- 1 file changed, 21 insertions(+), 23 deletions(-)
ipc/sem.c +21 -23
@@ -25,8 +25,6 @@* This file implements System V semaphores. * * User space visible behavior: -* - FIFO ordering for semop() operations (just FIFO, not starvation -* protection) * - multiple semaphore operations that alter the same semaphore in * one semop() are handled. * - sem_ctime (time of last semctl()) is updated in the IPC_SET, SETVAL and
@@ -51,8 +49,7 @@* count_semzcnt() * - the task that performs a successful semop() scans the list of all * sleeping tasks and completes any pending operations that can be fulfilled. -* Semaphores are actively given to waiting tasks (necessary for FIFO). -* (see update_queue()) +* Semaphores are actively given to waiting tasks (see update_queue()). * - To improve the scalability, the actual wake-up calls are performed after * dropping all locks. (see wake_up_sem_queue_prepare(), * wake_up_sem_queue_do())
@@ -68,9 +65,9 @@* modes for the UNDO variables are supported (per process, per thread) * (see copy_semundo, CLONE_SYSVSEM) * - There are two lists of the pending operations: a per-array list -* and per-semaphore list (stored in the array). This allows to achieve FIFO -* ordering without always scanning all pending operations. -* The worst-case behavior is nevertheless O(N^2) for N wakeups. +* and per-semaphore list (stored in the array). The per-array list is +* used for calls that do multiple semaphore operations in one semop call. +* The worst-case behavior is O(N^2) for N wakeups. */ #include <linux/slab.h>
@@ -606,7 +603,7 @@ static void unlink_queue(struct sem_array *sma, struct sem_queue *q)* @sma: semaphore array * @q: the operation that just completed * -* update_queue is O(N^2) when it restarts scanning the whole queue of +* do_smart_update is O(N^2) when it restarts scanning the whole queue of * waiting operations. Therefore this function checks if the restart is * really necessary. It is called after a previously waiting operation * was completed.
@@ -671,6 +668,7 @@ static int check_restart(struct sem_array *sma, struct sem_queue *q)* @sma: semaphore array. * @semnum: semaphore that was modified. * @pt: list head for the tasks that must be woken up. +* @restart: did a semop change something that may require a restart? * * update_queue must be called after a semaphore in a semaphore array * was modified. If multiple semaphores were modified, update_queue must
@@ -680,7 +678,8 @@ static int check_restart(struct sem_array *sma, struct sem_queue *q)* is stored in q->pid. * The function return 1 if at least one semop was completed successfully. */ -static int update_queue (struct sem_array *sma,int semnum,struct list_head *pt) +static int update_queue (struct sem_array *sma,int semnum, +struct list_head *pt,int *restart) {struct sem_queue *q;struct list_head *walk;
@@ -692,10 +691,9 @@ static int update_queue(struct sem_array *sma, int semnum, struct list_head *pt)else pending_list = &sma->sem_base[semnum].sem_pending; -again: walk = pending_list->next;while (walk != pending_list) { -int error, restart; +int error; q = container_of(walk, struct sem_queue, list); walk = walk->next;
@@ -720,16 +718,11 @@ static int update_queue(struct sem_array *sma, int semnum, struct list_head *pt)unlink_queue (sma, q); -if (error) { - restart =0 ; - }else { - semop_completed =1 ; - restart =check_restart (sma, q); - } + semop_completed =1 ; +if (check_restart (sma, q)) + *restart =1 ;wake_up_sem_queue_prepare (pt, q, error); -if (restart) - goto again; }return semop_completed; }
@@ -751,17 +744,19 @@ static int update_queue(struct sem_array *sma, int semnum, struct list_head *pt)static void do_smart_update (struct sem_array *sma,struct sembuf *sops,int nsops,int otime,struct list_head *pt) { -int i; +int i, restart; + again: + restart =0 ;if (sma->complex_count || sops ==NULL ) { -if (update_queue (sma,-1 , pt)) +if (update_queue (sma,-1 , pt, &restart)) otime =1 ; }if (!sops) {/* No semops; something special is going on. */ for (i =0 ; i < sma->sem_nsems; i++) { -if (update_queue (sma, i, pt)) +if (update_queue (sma, i, pt, &restart)) otime =1 ; } goto done;
@@ -772,9 +767,12 @@ static void do_smart_update(struct sem_array *sma, struct sembuf *sops, int nsopif (sops[i].sem_op >0 || (sops[i].sem_op <0 && sma->sem_base[sops[i].sem_num].semval ==0 )) -if (update_queue (sma, sops[i].sem_num, pt)) +if (update_queue (sma, sops[i].sem_num, pt, &restart)) otime =1 ; } + +if (restart) + goto again; done:if (otime) sma->sem_otime =get_seconds ();
Re: [PATCH] ipc,sem: move restart loop to do_smart_update
Quoted 9 lines · Rik van Riel
Quoted 8 lines
One fix would be a loop in
do_smart_update():
- first check the global queue
- then the per-semaphore queues
- if one of the per-semaphore queues made progress: check the global queue again
- if the global queue made progress: check the per semaphore queues again
...
Quoted 4 lines
Would that be as simple as making
do_smart_update()loop back to the top ifupdate_queueon a single semaphore's queue returns a non-zero value (something was changed), and there are complex operations pending?
I've been looking at the code for a while and this approach seems quite reasonable. I'd still like Manfred's feedback though. I ran pgbench and your semop-multi program, nothing suspicious.
Quoted 12 lines
---8<---
Subject: ipc,sem: move restart loop to
do_smart_updateA complex operation may be sleeping on a semaphore to become a certain value. A sleeping simple operation may turn the semaphore into that value.
Having the restart loop inside
update_queuemeans we may be missing the complex operation (which lives on a different queue), and result in a semaphore lockup.
Quoted 6 lines
The lockup can be avoided by moving the restart loop into
do_smart_update, so the list of pending complex operations will also be checked if required.Signed-off-by Rik van Riel <[email protected]>Reported-by Manfred Spraul <[email protected]>
Re: [PATCH] ipc,sem: move restart loop to do_smart_update
In reply to Rik van RielHi Rik,
Quoted 4 lines · Rik van Riel
ipc/sem.c +0
-0@@ -751,17 +744,19 @@ static int update_queue(struct sem_array *sma, int semnum, struct list_head *pt)static void do_smart_update (struct sem_array *sma,struct sembuf *sops,int nsops,int otime,struct list_head *pt) {
ipc/sem.c static int update_queue(struct sem_array *sma, int semnum, struct list_head *pt) · line 754
Quoted 10 lines
ipc/sem.c +4
-2-int i; +int i, restart; + again: + restart =0 ;if (sma->complex_count || sops ==NULL ) { -if (update_queue (sma,-1 , pt)) +if (update_queue (sma,-1 , pt, &restart)) otime =1 ; }
I didn't notice it immediately, this is insufficient:
Complex operations may affect all semaphores in the array.
Thus it is not sufficient to scan the per-semaphore queues of the semaphores that were touched by *sops, all must be scanned.
Perhaps something like:
ipc/sem.c static int update_queue(struct sem_array *sma, int semnum, struct list_head *pt) · line 754
Quoted 4 lines
ipc/sem.c +2
-0+if (update_queue (sma,-1 , pt, &restart)) + sops =NULL ; otime =1 ; }
(untested!)
Test case:
1: semop(<key>, {{1, -1, 0}, {2, 1, 0}}, 2 <unfinished ...> 2: semop(<key>, {{2, -1, 0}}, 1 <unfinished ...>
3: semop(<key>, {{1, 1, 0}}, 1) = 0
[3] is able to run, calls do_smart_update().
The global queue is scanned and [1] is released Without the "sops = NULL", [2] sleeps forever.
--
Manfred