System V semaphore bug in kernel 2.6

System V semaphore bug in kernel 2.6

[Michael Kerrisk]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="us-ascii", Size: 6703 bytes --]

Hello Manfred, Alan,

I assume you are still the relevant people to know about 
this nowadays...

Somewhere in the reworking of the System V semaphore code 
(ipc/sem.c or nearby) in Linux 2.6, a bug appears to have 
been introduced.  

This bug means that in some cases, a process that 
is blocked waiting for a semaphore's value to become 
zero is not woken up, even when that semaphore's value 
does become zero (perhaps the problem is more general, 
but this is the example that I've observed).

I have not spotted where the problem is in the code, but 
have attached a program that demonstrates the error.  
This program does the following:

-- Creates a semaphore set containing two members, and 
   initialises them to 1 and 0 using SETALL.

-- Creates a series of children that perform the 
   following operations:

             operation on 
           sem 0       sem 1     

Child 1     -1          -1       (blocks)
Child 2  wait-for-0    [none]
Child 3    [none]       +1       (child 1 and 2 should now unblock)
Child 4  wait-for-0    [none]       


What happens on Linux 2.6.9 is that the operation 
performed by child 3 does NOT unblock child 1.  Furthermore, 
child 4's operation, which is just the same as child 2's, 
proceeds without blocking, while child 2 remains blocked.


On Linux 2.6.9 (2.6.1 gave the same results), my program 
shows the following:

==
$ ./sem_2.6_bug_demo
Thu Dec  9 16:52:02 CET 2004
Linux tekapo 2.6.9 #3 SMP Tue Oct 19 10:19:40 CEST 2004 i686 i686 i386
GNU/Linux
semid = 0
Semaphore values changed (PID=8462)
8466: Child 1 about to semop
8467: Child 2 about to semop
8468: Child 3 about to semop
8468: Child 3 semop COMPLETED
8466: Child 1 semop COMPLETED
Sem #  Value  SEMPID  SEMNCNT  SEMZCNT
  0       0    8466      0        1
  1       0    8466      0        0
8469: Child 4 about to semop
8469: Child 4 semop COMPLETED
Waited on PID 8466 successfully
Waited on PID 8468 successfully
Waited on PID 8469 successfully
==

Note the absence of any message saying that child 2 completed, 
and that only 3 children were waited on.

On Linux 2.4.24, I see the following:

==
$ ./sem_2.6_bug_demo
Thu Dec  9 17:05:00 CET 2004
Linux tekapo 2.4.28 #2 SMP Wed Dec 1 07:02:01 CET 2004 i686 i686 i386
GNU/Linux
semid = 65538
Semaphore values changed (PID=2288)
2292: Child 1 about to semop
2293: Child 2 about to semop
2294: Child 3 about to semop
2292: Child 1 semop COMPLETED
2294: Child 3 semop COMPLETED
2293: Child 2 semop COMPLETED
Sem #  Value  SEMPID  SEMNCNT  SEMZCNT
  0       0    2293      0        0
  1       0    2292      0        0
2295: Child 4 about to semop
2295: Child 4 semop COMPLETED
Waited on PID 2295 successfully
Waited on PID 2294 successfully
Waited on PID 2293 successfully
Waited on PID 2292 successfully
==

Cheers,

Michael



/* sem_2.6_bug_demo.c

   Michael Kerrisk, Dec 2004
*/
#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/stat.h>

#define errExit(msg)            { perror(msg); exit(EXIT_FAILURE); }

union semun {   /* Used in calls to semctl() */
    int                 val;
    struct semid_ds *   buf;
    unsigned short *    array;
#if defined(__linux__)
    struct seminfo *    __buf;
#endif
};

#define NOOP -999999

/* Create a child process that performs an operation on the
   semaphores in the set referred to by 'semid', which must
   contain exactly two semaphores.

   'cnum' is just a number used in messages printed by the 
   function.

   'op0' specifies the sem_op value for semaphore 0 in the set;
   'op1' specifies the sem_op value for semaphore 1 in the set.
   If 'op0' or 'op1' is NOOP then no operation is performed on
   the corresponding semaphore.  */

static void
child(int cnum, int semid, int op0, int op1)
{
    struct sembuf sops[2];
    pid_t pid;
    int nsops;

    pid = fork();
    if (pid == -1) errExit("fork1");

    if (pid == 0) {
        nsops = 0;

        if (op0 != NOOP) {
            sops[nsops].sem_num = 0;
            sops[nsops].sem_flg = 0;
            sops[nsops].sem_op = op0;
            nsops ++;
        } 

        if (op1 != NOOP) {
            sops[nsops].sem_num = 1;
            sops[nsops].sem_flg = 0;
            sops[nsops].sem_op = op1;
            nsops ++;
        } 

        printf("%ld: Child %d about to semop\n", (long) getpid(), cnum);
        if (semop(semid, sops, nsops) == -1)
            errExit("semop");
        printf("%ld: Child %d semop COMPLETED\n", (long) getpid(), cnum);

        exit(EXIT_SUCCESS);
    } /* if */

    /* Parent returns */
} /* child */

int
main(int argc, char *argv[])
{
    union semun arg, dummy;
    int semid;
    pid_t pid;
    int j;

    system("date; uname -a");

    setbuf(stdout, NULL);

    semid = semget(IPC_PRIVATE, 2,
            IPC_CREAT | IPC_EXCL | S_IRUSR | S_IWUSR);
    if (semid == -1) errExit("semget");

    printf("semid = %d\n", semid);

    /* Initialise set */

    arg.array = calloc(2, sizeof(arg.array[0]));
    if (arg.array == NULL) errExit("calloc");

    arg.array[0] = 1;
    arg.array[1] = 0;

    /* State of semaphores is now { 1, 0 } */

    if (semctl(semid, 0, SETALL, arg) == -1) errExit("semctl-SETALL");
    printf("Semaphore values changed (PID=%ld)\n", (long) getpid());

    child(1, semid, -1, -1);    /* Decrease both sems */
    sleep(1);
    child(2, semid, 0, NOOP);   /* Wait for sem 0 to equal 0 */
    sleep(1);
    child(3, semid, NOOP, 1);   /* Increase sem 1 */
    sleep(1);

                /* This SHOULD allow child 1 and child 2 to complete,
                   but on Linux 2.6, child 2 is not woken up. */

    /* State of semaphores is now { 0, 0 } */

    /* Display current state of semaphores */

    if (semctl(semid, 0, GETALL, arg) == -1) errExit("semctl-GETALL");
    printf("Sem #  Value  SEMPID  SEMNCNT  SEMZCNT\n");
    for (j = 0; j < 2; j++)
        printf("%3d   %5d   %5d  %5d    %5d\n", j, arg.array[j],
                semctl(semid, j, GETPID, dummy),
                semctl(semid, j, GETNCNT, dummy),
                semctl(semid, j, GETZCNT, dummy));

    /* The following is exactly the same as child 2; on Linux 2.6
       this child succeeds in waiting for semaphore 0 to be 0, even
       while child 2 is blocked on the same operation.  */

    child(4, semid, 0, NOOP);   /* Wait for sem 0 to equal 0 */
    sleep(1);

    while ((pid = waitpid(0, NULL, WNOHANG)) > 0)
        printf("Waited on PID %ld successfully\n", (long) pid);

    exit(EXIT_SUCCESS);
} /* main */

-- 
NEU +++ DSL Komplett von GMX +++ http://www.gmx.net/de/go/dsl
GMX DSL-Netzanschluss + Tarif zum supergünstigen Komplett-Preis!

Re: System V semaphore bug in kernel 2.6

[Manfred Spraul]

Michael Kerrisk wrote:

>Hello Manfred, Alan,
>
>I assume you are still the relevant people to know about 
>this nowadays...
>
>Somewhere in the reworking of the System V semaphore code 
>(ipc/sem.c or nearby) in Linux 2.6, a bug appears to have 
>been introduced.  
>
>  
>
ipc/sem.c. The change that now semaphores are actively given to the 
waiting task broke your test.

What happens is:

child 3 does a semaphore operation. It succeeds. update_queue is called:
- try_atomic_semop checks if it can wake up child 2. Answer: No.
- try_atomic_semop(): kernel checks if it can wake up child 1. Answer: Yes.

Bug: It must now check again if there is a thread that is waiting for 
semaphore value==0. This check is now missing. In 2.4, there was another 
round of update_queue calls just before child 1 returns to user space. 
That call then wakes up child 1. This call was removed.

One approach to fix that is a loop in update_queue: If a 
try_atomic_semop call from within update_queue modified the array, then 
check again from the beginning of the queue.

What do you think? I'll write a patch.

--
    Manfred

[PATCH] fix missing wakeup in ipc/sem

[Manfred Spraul]

[-- Attachment #1: Type: text/plain, Size: 658 bytes --]

Hi Andrew,

My patch that removed the spin_lock calls from the tail of
sys_semtimedop introduced a bug:
Before my patch was merged, every operation that altered an array called
update_queue. That call woke up threads that were waiting until a
semaphore value becomes 0. I've accidentially removed that call.

The attached patch fixes that by modifying update_queue: the function
now loops internally and wakes up all threads. The patch also removes
update_queue calls from the error path of sys_semtimedop: failed
operations do not modify the array, no need to rescan the list of
waiting threads.

Signed-Off-By: Manfred Spraul <manfred@colorfullife.com>




[-- Attachment #2: patch-ipcsem-wakeupfix --]
[-- Type: text/plain, Size: 2201 bytes --]

// $Header$
// Kernel Version:
//  VERSION = 2
//  PATCHLEVEL = 6
//  SUBLEVEL = 10
//  EXTRAVERSION =-rc2-mm4
--- 2.6/include/linux/sem.h	2004-12-05 16:20:31.000000000 +0100
+++ build-2.6/include/linux/sem.h	2004-12-09 18:39:58.000000000 +0100
@@ -109,6 +109,7 @@ struct sem_queue {
 	int			id;	 /* internal sem id */
 	struct sembuf *		sops;	 /* array of pending operations */
 	int			nsops;	 /* number of operations */
+	int			alter;   /* does the operation alter the array? */
 };
 
 /* Each task has a list of undo requests. They are executed automatically
--- 2.6/ipc/sem.c	2004-12-05 16:21:39.000000000 +0100
+++ build-2.6/ipc/sem.c	2004-12-09 19:13:19.000000000 +0100
@@ -358,8 +358,22 @@ static void update_queue (struct sem_arr
 		if (error <= 0) {
 			struct sem_queue *n;
 			remove_from_queue(sma,q);
-			n = q->next;
 			q->status = IN_WAKEUP;
+			/*
+			 * Continue scanning. The next operation
+			 * that must be checked depends on the type of the
+			 * completed operation:
+			 * - if the operation modified the array, then
+			 *   restart from the head of the queue and
+			 *   check for threads that might be waiting
+			 *   for semaphore values to become 0.
+			 * - if the operation didn't modify the array,
+			 *   then just continue.
+			 */
+			if (q->alter)
+				n = sma->sem_pending;
+			else
+				n = q->next;
 			wake_up_process(q->sleeper);
 			/* hands-off: q will disappear immediately after
 			 * writing q->status.
@@ -1119,8 +1133,11 @@ retry_undos:
 		goto out_unlock_free;
 
 	error = try_atomic_semop (sma, sops, nsops, un, current->tgid);
-	if (error <= 0)
-		goto update;
+	if (error <= 0) {
+		if (alter && error == 0)
+			update_queue (sma);
+		goto out_unlock_free;
+	}
 
 	/* We need to sleep on this operation, so we put the current
 	 * task into the pending queue and go to sleep.
@@ -1132,6 +1149,7 @@ retry_undos:
 	queue.undo = un;
 	queue.pid = current->tgid;
 	queue.id = semid;
+	queue.alter = alter;
 	if (alter)
 		append_to_queue(sma ,&queue);
 	else
@@ -1183,9 +1201,6 @@ retry_undos:
 	remove_from_queue(sma,&queue);
 	goto out_unlock_free;
 
-update:
-	if (alter)
-		update_queue (sma);
 out_unlock_free:
 	sem_unlock(sma);
 out_free:

Re: [PATCH] fix missing wakeup in ipc/sem

[Michael Kerrisk]

Manfred,

> My patch that removed the spin_lock calls from the tail of
> sys_semtimedop introduced a bug:
> Before my patch was merged, every operation that altered an array called
> update_queue. That call woke up threads that were waiting until a
> semaphore value becomes 0. I've accidentially removed that call.
> 
> The attached patch fixes that by modifying update_queue: the function
> now loops internally and wakes up all threads. The patch also removes
> update_queue calls from the error path of sys_semtimedop: failed
> operations do not modify the array, no need to rescan the list of
> waiting threads.

Thanks -- tested on 2.6.10-rc3 and it works for me.

Cheers,

Michael

-- 
GMX ProMail mit bestem Virenschutz http://www.gmx.net/de/go/mail
+++ Empfehlung der Redaktion +++ Internet Professionell 10/04 +++