ipc/sem.c

   1 /*
   2  * linux/ipc/sem.c
   3  * Copyright (C) 1992 Krishna Balasubramanian
   4  * Copyright (C) 1995 Eric Schenk, Bruno Haible
   5  *
   6  * IMPLEMENTATION NOTES ON CODE REWRITE (Eric Schenk, January 1995):
   7  * This code underwent a massive rewrite in order to solve some problems
   8  * with the original code. In particular the original code failed to
   9  * wake up processes that were waiting for semval to go to 0 if the
  10  * value went to 0 and was then incremented rapidly enough. In solving
  11  * this problem I have also modified the implementation so that it
  12  * processes pending operations in a FIFO manner, thus give a guarantee
  13  * that processes waiting for a lock on the semaphore won't starve
  14  * unless another locking process fails to unlock.
  15  * In addition the following two changes in behavior have been introduced:
  16  * - The original implementation of semop returned the value
  17  *   last semaphore element examined on success. This does not
  18  *   match the manual page specifications, and effectively
  19  *   allows the user to read the semaphore even if they do not
  20  *   have read permissions. The implementation now returns 0
  21  *   on success as stated in the manual page.
  22  * - There is some confusion over whether the set of undo adjustments
  23  *   to be performed at exit should be done in an atomic manner.
  24  *   That is, if we are attempting to decrement the semval should we queue
  25  *   up and wait until we can do so legally?
  26  *   The original implementation attempted to do this.
  27  *   The current implementation does not do so. This is because I don't
  28  *   think it is the right thing (TM) to do, and because I couldn't
  29  *   see a clean way to get the old behavior with the new design.
  30  *   The POSIX standard and SVID should be consulted to determine
  31  *   what behavior is mandated.
  32  *
  33  * Further notes on refinement (Christoph Rohland, December 1998):
  34  * - The POSIX standard says, that the undo adjustments simply should
  35  *   redo. So the current implementation is o.K.
  36  * - The previous code had two flaws:
  37  *   1) It actively gave the semaphore to the next waiting process
  38  *      sleeping on the semaphore. Since this process did not have the
  39  *      cpu this led to many unnecessary context switches and bad
  40  *      performance. Now we only check which process should be able to
  41  *      get the semaphore and if this process wants to reduce some
  42  *      semaphore value we simply wake it up without doing the
  43  *      operation. So it has to try to get it later. Thus e.g. the
  44  *      running process may reaquire the semaphore during the current
  45  *      time slice. If it only waits for zero or increases the semaphore,
  46  *      we do the operation in advance and wake it up.
  47  *   2) It did not wake up all zero waiting processes. We try to do
  48  *      better but only get the semops right which only wait for zero or
  49  *      increase. If there are decrement operations in the operations
  50  *      array we do the same as before.
  51  */
  52
  53 #include <linux/malloc.h>
  54 #include <linux/smp_lock.h>
  55 #include <linux/init.h>
  56
  57 #include <asm/uaccess.h>
  58
  59 extern int ipcperms (struct ipc_perm *ipcp, short semflg);
  60 static int newary (key_t, int, int);
  61 static int findkey (key_t key);
  62 static void freeary (int id);
  63
  64 static struct semid_ds *semary[SEMMNI];
  65 static int used_sems = 0, used_semids = 0;
  66 static DECLARE_WAIT_QUEUE_HEAD(sem_lock);
  67 static int max_semid = 0;
  68
  69 static unsigned short sem_seq = 0;
  70
  71 void __init sem_init (void)
  72 {
  73         int i;
  74
  75         init_waitqueue_head(&sem_lock);
  76         used_sems = used_semids = max_semid = sem_seq = 0;
  77         for (i = 0; i < SEMMNI; i++)
  78                 semary[i] = (struct semid_ds *) IPC_UNUSED;
  79         return;
  80 }
  81
  82 static int findkey (key_t key)
  83 {
  84         int id;
  85         struct semid_ds *sma;
  86
  87         for (id = 0; id <= max_semid; id++) {
  88                 while ((sma = semary[id]) == IPC_NOID)
  89                         interruptible_sleep_on (&sem_lock);
  90                 if (sma == IPC_UNUSED)
  91                         continue;
  92                 if (key == sma->sem_perm.key)
  93                         return id;
  94         }
  95         return -1;
  96 }
  97
  98 static int newary (key_t key, int nsems, int semflg)
  99 {
 100         int id;
 101         struct semid_ds *sma;
 102         struct ipc_perm *ipcp;
 103         int size;
 104
 105         if (!nsems)
 106                 return -EINVAL;
 107         if (used_sems + nsems > SEMMNS)
 108                 return -ENOSPC;
 109         for (id = 0; id < SEMMNI; id++)
 110                 if (semary[id] == IPC_UNUSED) {
 111                         semary[id] = (struct semid_ds *) IPC_NOID;
 112                         goto found;
 113                 }
 114         return -ENOSPC;
 115 found:
 116         size = sizeof (*sma) + nsems * sizeof (struct sem);
 117         used_sems += nsems;
 118         sma = (struct semid_ds *) kmalloc (size, GFP_KERNEL);
 119         if (!sma) {
 120                 semary[id] = (struct semid_ds *) IPC_UNUSED;
 121                 used_sems -= nsems;
 122                 wake_up (&sem_lock);
 123                 return -ENOMEM;
 124         }
 125         memset (sma, 0, size);
 126         sma->sem_base = (struct sem *) &sma[1];
 127         ipcp = &sma->sem_perm;
 128         ipcp->mode = (semflg & S_IRWXUGO);
 129         ipcp->key = key;
 130         ipcp->cuid = ipcp->uid = current->euid;
 131         ipcp->gid = ipcp->cgid = current->egid;
 132         sma->sem_perm.seq = sem_seq;
 133         /* sma->sem_pending = NULL; */
 134         sma->sem_pending_last = &sma->sem_pending;
 135         /* sma->undo = NULL; */
 136         sma->sem_nsems = nsems;
 137         sma->sem_ctime = CURRENT_TIME;
 138         if (id > max_semid)
 139                 max_semid = id;
 140         used_semids++;
 141         semary[id] = sma;
 142         wake_up (&sem_lock);
 143         return (unsigned int) sma->sem_perm.seq * SEMMNI + id;
 144 }
 145
 146 asmlinkage int sys_semget (key_t key, int nsems, int semflg)
 147 {
 148         int id, err = -EINVAL;
 149         struct semid_ds *sma;
 150
 151         lock_kernel();
 152         if (nsems < 0 || nsems > SEMMSL)
 153                 goto out;
 154         if (key == IPC_PRIVATE) {
 155                 err = newary(key, nsems, semflg);
 156         } else if ((id = findkey (key)) == -1) {  /* key not used */
 157                 if (!(semflg & IPC_CREAT))
 158                         err = -ENOENT;
 159                 else
 160                         err = newary(key, nsems, semflg);
 161         } else if (semflg & IPC_CREAT && semflg & IPC_EXCL) {
 162                 err = -EEXIST;
 163         } else {
 164                 sma = semary[id];
 165                 if (nsems > sma->sem_nsems)
 166                         err = -EINVAL;
 167                 else if (ipcperms(&sma->sem_perm, semflg))
 168                         err = -EACCES;
 169                 else
 170                         err = (int) sma->sem_perm.seq * SEMMNI + id;
 171         }
 172 out:
 173         unlock_kernel();
 174         return err;
 175 }
 176
 177 /* Manage the doubly linked list sma->sem_pending as a FIFO:
 178  * insert new queue elements at the tail sma->sem_pending_last.
 179  */
 180 static inline void append_to_queue (struct semid_ds * sma,
 181                                     struct sem_queue * q)
 182 {
 183         *(q->prev = sma->sem_pending_last) = q;
 184         *(sma->sem_pending_last = &q->next) = NULL;
 185 }
 186
 187 static inline void prepend_to_queue (struct semid_ds * sma,
 188                                      struct sem_queue * q)
 189 {
 190         q->next = sma->sem_pending;
 191         *(q->prev = &sma->sem_pending) = q;
 192         if (q->next)
 193                 q->next->prev = &q->next;
 194         else /* sma->sem_pending_last == &sma->sem_pending */
 195                 sma->sem_pending_last = &q->next;
 196 }
 197
 198 static inline void remove_from_queue (struct semid_ds * sma,
 199                                       struct sem_queue * q)
 200 {
 201         *(q->prev) = q->next;
 202         if (q->next)
 203                 q->next->prev = q->prev;
 204         else /* sma->sem_pending_last == &q->next */
 205                 sma->sem_pending_last = q->prev;
 206         q->prev = NULL; /* mark as removed */
 207 }
 208
 209 /*
 210  * Determine whether a sequence of semaphore operations would succeed
 211  * all at once. Return 0 if yes, 1 if need to sleep, else return error code.
 212  */
 213
 214 static int try_atomic_semop (struct semid_ds * sma, struct sembuf * sops,
 215                              int nsops, struct sem_undo *un, int pid,
 216                              int do_undo)
 217 {
 218         int result, sem_op;
 219         struct sembuf *sop;
 220         struct sem * curr;
 221
 222         for (sop = sops; sop < sops + nsops; sop++) {
 223                 curr = sma->sem_base + sop->sem_num;
 224                 sem_op = sop->sem_op;
 225
 226                 if (!sem_op && curr->semval)
 227                         goto would_block;
 228
 229                 curr->sempid = (curr->sempid << 16) | pid;
 230                 curr->semval += sem_op;
 231                 if (sop->sem_flg & SEM_UNDO)
 232                         un->semadj[sop->sem_num] -= sem_op;
 233
 234                 if (curr->semval < 0)
 235                         goto would_block;
 236                 if (curr->semval > SEMVMX)
 237                         goto out_of_range;
 238         }
 239
 240         if (do_undo)
 241         {
 242                 sop--;
 243                 result = 0;
 244                 goto undo;
 245         }
 246
 247         sma->sem_otime = CURRENT_TIME;
 248         return 0;
 249
 250 out_of_range:
 251         result = -ERANGE;
 252         goto undo;
 253
 254 would_block:
 255         if (sop->sem_flg & IPC_NOWAIT)
 256                 result = -EAGAIN;
 257         else
 258                 result = 1;
 259
 260 undo:
 261         while (sop >= sops) {
 262                 curr = sma->sem_base + sop->sem_num;
 263                 curr->semval -= sop->sem_op;
 264                 curr->sempid >>= 16;
 265
 266                 if (sop->sem_flg & SEM_UNDO)
 267                         un->semadj[sop->sem_num] += sop->sem_op;
 268                 sop--;
 269         }
 270
 271         return result;
 272 }
 273
 274 /* Go through the pending queue for the indicated semaphore
 275  * looking for tasks that can be completed.
 276  */
 277 static void update_queue (struct semid_ds * sma)
 278 {
 279         int error;
 280         struct sem_queue * q;
 281
 282         for (q = sma->sem_pending; q; q = q->next) {
 283
 284                 if (q->status == 1)
 285                         return; /* wait for other process */
 286
 287                 error = try_atomic_semop(sma, q->sops, q->nsops,
 288                                          q->undo, q->pid, q->alter);
 289
 290                 /* Does q->sleeper still need to sleep? */
 291                 if (error <= 0) {
 292                                 /* Found one, wake it up */
 293                         wake_up_interruptible(&q->sleeper);
 294                         if (error == 0 && q->alter) {
 295                                 /* if q-> alter let it self try */
 296                                 q->status = 1;
 297                                 return;
 298                         }
 299                         q->status = error;
 300                         remove_from_queue(sma,q);
 301                 }
 302         }
 303 }
 304
 305 /* The following counts are associated to each semaphore:
 306  *   semncnt        number of tasks waiting on semval being nonzero
 307  *   semzcnt        number of tasks waiting on semval being zero
 308  * This model assumes that a task waits on exactly one semaphore.
 309  * Since semaphore operations are to be performed atomically, tasks actually
 310  * wait on a whole sequence of semaphores simultaneously.
 311  * The counts we return here are a rough approximation, but still
 312  * warrant that semncnt+semzcnt>0 if the task is on the pending queue.
 313  */
 314 static int count_semncnt (struct semid_ds * sma, ushort semnum)
 315 {
 316         int semncnt;
 317         struct sem_queue * q;
 318
 319         semncnt = 0;
 320         for (q = sma->sem_pending; q; q = q->next) {
 321                 struct sembuf * sops = q->sops;
 322                 int nsops = q->nsops;
 323                 int i;
 324                 for (i = 0; i < nsops; i++)
 325                         if (sops[i].sem_num == semnum
 326                             && (sops[i].sem_op < 0)
 327                             && !(sops[i].sem_flg & IPC_NOWAIT))
 328                                 semncnt++;
 329         }
 330         return semncnt;
 331 }
 332 static int count_semzcnt (struct semid_ds * sma, ushort semnum)
 333 {
 334         int semzcnt;
 335         struct sem_queue * q;
 336
 337         semzcnt = 0;
 338         for (q = sma->sem_pending; q; q = q->next) {
 339                 struct sembuf * sops = q->sops;
 340                 int nsops = q->nsops;
 341                 int i;
 342                 for (i = 0; i < nsops; i++)
 343                         if (sops[i].sem_num == semnum
 344                             && (sops[i].sem_op == 0)
 345                             && !(sops[i].sem_flg & IPC_NOWAIT))
 346                                 semzcnt++;
 347         }
 348         return semzcnt;
 349 }
 350
 351 /* Free a semaphore set. */
 352 static void freeary (int id)
 353 {
 354         struct semid_ds *sma = semary[id];
 355         struct sem_undo *un;
 356         struct sem_queue *q;
 357
 358         /* Invalidate this semaphore set */
 359         sma->sem_perm.seq++;
 360         sem_seq = (sem_seq+1) % ((unsigned)(1<<31)/SEMMNI); /* increment, but avoid overflow */
 361         used_sems -= sma->sem_nsems;
 362         if (id == max_semid)
 363                 while (max_semid && (semary[--max_semid] == IPC_UNUSED));
 364         semary[id] = (struct semid_ds *) IPC_UNUSED;
 365         used_semids--;
 366
 367         /* Invalidate the existing undo structures for this semaphore set.
 368          * (They will be freed without any further action in sem_exit().)
 369          */
 370         for (un = sma->undo; un; un = un->id_next)
 371                 un->semid = -1;
 372
 373         /* Wake up all pending processes and let them fail with EIDRM. */
 374         for (q = sma->sem_pending; q; q = q->next) {
 375                 q->status = -EIDRM;
 376                 q->prev = NULL;
 377                 wake_up_interruptible(&q->sleeper); /* doesn't sleep! */
 378         }
 379
 380         kfree(sma);
 381 }
 382
 383 asmlinkage int sys_semctl (int semid, int semnum, int cmd, union semun arg)
 384 {
 385         struct semid_ds *buf = NULL;
 386         struct semid_ds tbuf;
 387         int i, id, val = 0;
 388         struct semid_ds *sma;
 389         struct ipc_perm *ipcp;
 390         struct sem *curr = NULL;
 391         struct sem_undo *un;
 392         unsigned int nsems;
 393         ushort *array = NULL;
 394         ushort sem_io[SEMMSL];
 395         int err = -EINVAL;
 396
 397         lock_kernel();
 398         if (semid < 0 || semnum < 0 || cmd < 0)
 399                 goto out;
 400
 401         switch (cmd) {
 402         case IPC_INFO:
 403         case SEM_INFO:
 404         {
 405                 struct seminfo seminfo, *tmp = arg.__buf;
 406                 seminfo.semmni = SEMMNI;
 407                 seminfo.semmns = SEMMNS;
 408                 seminfo.semmsl = SEMMSL;
 409                 seminfo.semopm = SEMOPM;
 410                 seminfo.semvmx = SEMVMX;
 411                 seminfo.semmnu = SEMMNU;
 412                 seminfo.semmap = SEMMAP;
 413                 seminfo.semume = SEMUME;
 414                 seminfo.semusz = SEMUSZ;
 415                 seminfo.semaem = SEMAEM;
 416                 if (cmd == SEM_INFO) {
 417                         seminfo.semusz = used_semids;
 418                         seminfo.semaem = used_sems;
 419                 }
 420                 err = -EFAULT;
 421                 if (copy_to_user (tmp, &seminfo, sizeof(struct seminfo)))
 422                         goto out;
 423                 err = max_semid;
 424                 goto out;
 425         }
 426
 427         case SEM_STAT:
 428                 buf = arg.buf;
 429                 err = -EINVAL;
 430                 if (semid > max_semid)
 431                         goto out;
 432                 sma = semary[semid];
 433                 if (sma == IPC_UNUSED || sma == IPC_NOID)
 434                         goto out;
 435                 err = -EACCES;
 436                 if (ipcperms (&sma->sem_perm, S_IRUGO))
 437                         goto out;
 438                 id = (unsigned int) sma->sem_perm.seq * SEMMNI + semid;
 439                 tbuf.sem_perm   = sma->sem_perm;
 440                 tbuf.sem_otime  = sma->sem_otime;
 441                 tbuf.sem_ctime  = sma->sem_ctime;
 442                 tbuf.sem_nsems  = sma->sem_nsems;
 443                 err = -EFAULT;
 444                 if (copy_to_user (buf, &tbuf, sizeof(*buf)) == 0)
 445                         err = id;
 446                 goto out;
 447         }
 448
 449         id = (unsigned int) semid % SEMMNI;
 450         sma = semary [id];
 451         err = -EINVAL;
 452         if (sma == IPC_UNUSED || sma == IPC_NOID)
 453                 goto out;
 454         ipcp = &sma->sem_perm;
 455         nsems = sma->sem_nsems;
 456         err = -EIDRM;
 457         if (sma->sem_perm.seq != (unsigned int) semid / SEMMNI)
 458                 goto out;
 459
 460         switch (cmd) {
 461         case GETVAL:
 462         case GETPID:
 463         case GETNCNT:
 464         case GETZCNT:
 465         case SETVAL:
 466                 err = -EINVAL;
 467                 if (semnum >= nsems)
 468                         goto out;
 469                 curr = &sma->sem_base[semnum];
 470                 break;
 471         }
 472
 473         switch (cmd) {
 474         case GETVAL:
 475         case GETPID:
 476         case GETNCNT:
 477         case GETZCNT:
 478         case GETALL:
 479                 err = -EACCES;
 480                 if (ipcperms (ipcp, S_IRUGO))
 481                         goto out;
 482                 switch (cmd) {
 483                 case GETVAL : err = curr->semval; goto out;
 484                 case GETPID : err = curr->sempid & 0xffff; goto out;
 485                 case GETNCNT: err = count_semncnt(sma,semnum); goto out;
 486                 case GETZCNT: err = count_semzcnt(sma,semnum); goto out;
 487                 case GETALL:
 488                         array = arg.array;
 489                         break;
 490                 }
 491                 break;
 492         case SETVAL:
 493                 val = arg.val;
 494                 err = -ERANGE;
 495                 if (val > SEMVMX || val < 0)
 496                         goto out;
 497                 break;
 498         case IPC_RMID:
 499                 if (current->euid == ipcp->cuid ||
 500                     current->euid == ipcp->uid || capable(CAP_SYS_ADMIN)) {
 501                         freeary (id);
 502                         err = 0;
 503                         goto out;
 504                 }
 505                 err = -EPERM;
 506                 goto out;
 507         case SETALL: /* arg is a pointer to an array of ushort */
 508                 array = arg.array;
 509                 err = -EFAULT;
 510                 if (copy_from_user (sem_io, array, nsems*sizeof(ushort)))
 511                        goto out;
 512                 err = 0;
 513                 for (i = 0; i < nsems; i++)
 514                         if (sem_io[i] > SEMVMX) {
 515                                 err = -ERANGE;
 516                                 goto out;
 517                         }
 518                 break;
 519         case IPC_STAT:
 520                 buf = arg.buf;
 521                 break;
 522         case IPC_SET:
 523                 buf = arg.buf;
 524                 err = copy_from_user (&tbuf, buf, sizeof (*buf));
 525                 if (err)
 526                         err = -EFAULT;
 527                 break;
 528         }
 529
 530         err = -EIDRM;
 531         if (semary[id] == IPC_UNUSED || semary[id] == IPC_NOID)
 532                 goto out;
 533         if (sma->sem_perm.seq != (unsigned int) semid / SEMMNI)
 534                 goto out;
 535
 536         switch (cmd) {
 537         case GETALL:
 538                 err = -EACCES;
 539                 if (ipcperms (ipcp, S_IRUGO))
 540                         goto out;
 541                 for (i = 0; i < sma->sem_nsems; i++)
 542                         sem_io[i] = sma->sem_base[i].semval;
 543                 if (copy_to_user (array, sem_io, nsems*sizeof(ushort)))
 544                         err = -EFAULT;
 545                 break;
 546         case SETVAL:
 547                 err = -EACCES;
 548                 if (ipcperms (ipcp, S_IWUGO))
 549                         goto out;
 550                 for (un = sma->undo; un; un = un->id_next)
 551                         un->semadj[semnum] = 0;
 552                 curr->semval = val;
 553                 sma->sem_ctime = CURRENT_TIME;
 554                 /* maybe some queued-up processes were waiting for this */
 555                 update_queue(sma);
 556                 break;
 557         case IPC_SET:
 558                 if (current->euid == ipcp->cuid ||
 559                     current->euid == ipcp->uid || capable(CAP_SYS_ADMIN)) {
 560                         ipcp->uid = tbuf.sem_perm.uid;
 561                         ipcp->gid = tbuf.sem_perm.gid;
 562                         ipcp->mode = (ipcp->mode & ~S_IRWXUGO)
 563                                 | (tbuf.sem_perm.mode & S_IRWXUGO);
 564                         sma->sem_ctime = CURRENT_TIME;
 565                         err = 0;
 566                         goto out;
 567                 }
 568                 err = -EPERM;
 569                 goto out;
 570         case IPC_STAT:
 571                 err = -EACCES;
 572                 if (ipcperms (ipcp, S_IRUGO))
 573                         goto out;
 574                 tbuf.sem_perm   = sma->sem_perm;
 575                 tbuf.sem_otime  = sma->sem_otime;
 576                 tbuf.sem_ctime  = sma->sem_ctime;
 577                 tbuf.sem_nsems  = sma->sem_nsems;
 578                 if (copy_to_user (buf, &tbuf, sizeof(*buf)))
 579                         err = -EFAULT;
 580                 break;
 581         case SETALL:
 582                 err = -EACCES;
 583                 if (ipcperms (ipcp, S_IWUGO))
 584                         goto out;
 585                 for (i = 0; i < nsems; i++)
 586                         sma->sem_base[i].semval = sem_io[i];
 587                 for (un = sma->undo; un; un = un->id_next)
 588                         for (i = 0; i < nsems; i++)
 589                                 un->semadj[i] = 0;
 590                 sma->sem_ctime = CURRENT_TIME;
 591                 /* maybe some queued-up processes were waiting for this */
 592                 update_queue(sma);
 593                 break;
 594         default:
 595                 err = -EINVAL;
 596                 goto out;
 597         }
 598         err = 0;
 599 out:
 600         unlock_kernel();
 601         return err;
 602 }
 603
 604 asmlinkage int sys_semop (int semid, struct sembuf *tsops, unsigned nsops)
 605 {
 606         int id, size, error = -EINVAL;
 607         struct semid_ds *sma;
 608         struct sembuf sops[SEMOPM], *sop;
 609         struct sem_undo *un;
 610         int undos = 0, decrease = 0, alter = 0;
 611         struct sem_queue queue;
 612
 613         lock_kernel();
 614         if (nsops < 1 || semid < 0)
 615                 goto out;
 616         error = -E2BIG;
 617         if (nsops > SEMOPM)
 618                 goto out;
 619         error = -EFAULT;
 620         if (copy_from_user (sops, tsops, nsops * sizeof(*tsops)))
 621                 goto out;
 622         id = (unsigned int) semid % SEMMNI;
 623         error = -EINVAL;
 624         if ((sma = semary[id]) == IPC_UNUSED || sma == IPC_NOID)
 625                 goto out;
 626         error = -EIDRM;
 627         if (sma->sem_perm.seq != (unsigned int) semid / SEMMNI)
 628                 goto out;
 629
 630                 error = -EFBIG;
 631         for (sop = sops; sop < sops + nsops; sop++) {
 632                 if (sop->sem_num >= sma->sem_nsems)
 633                         goto out;
 634                 if (sop->sem_flg & SEM_UNDO)
 635                         undos++;
 636                 if (sop->sem_op < 0)
 637                         decrease = 1;
 638                 if (sop->sem_op > 0)
 639                         alter = 1;
 640         }
 641         alter |= decrease;
 642
 643         error = -EACCES;
 644         if (ipcperms(&sma->sem_perm, alter ? S_IWUGO : S_IRUGO))
 645                 goto out;
 646         if (undos) {
 647                 /* Make sure we have an undo structure
 648                  * for this process and this semaphore set.
 649                  */
 650                 for (un = current->semundo; un; un = un->proc_next)
 651                         if (un->semid == semid)
 652                                 break;
 653                 if (!un) {
 654                         size = sizeof(struct sem_undo) + sizeof(short)*sma->sem_nsems;
 655                         un = (struct sem_undo *) kmalloc(size, GFP_ATOMIC);
 656                         if (!un) {
 657                                 error = -ENOMEM;
 658                                 goto out;
 659                         }
 660                         memset(un, 0, size);
 661                         un->semadj = (short *) &un[1];
 662                         un->semid = semid;
 663                         un->proc_next = current->semundo;
 664                         current->semundo = un;
 665                         un->id_next = sma->undo;
 666                         sma->undo = un;
 667                 }
 668         } else
 669                 un = NULL;
 670
 671         error = try_atomic_semop (sma, sops, nsops, un, current->pid, 0);
 672         if (error <= 0)
 673                 goto update;
 674
 675         /* We need to sleep on this operation, so we put the current
 676          * task into the pending queue and go to sleep.
 677          */
 678
 679         queue.sma = sma;
 680         queue.sops = sops;
 681         queue.nsops = nsops;
 682         queue.undo = un;
 683         queue.pid = current->pid;
 684         queue.alter = decrease;
 685         current->semsleeping = &queue;
 686         if (alter)
 687                 append_to_queue(sma ,&queue);
 688         else
 689                 prepend_to_queue(sma ,&queue);
 690
 691         for (;;) {
 692                 queue.status = -EINTR;
 693                 init_waitqueue_head(&queue.sleeper);
 694                 interruptible_sleep_on(&queue.sleeper);
 695
 696                 /*
 697                  * If queue.status == 1 we where woken up and
 698                  * have to retry else we simply return.
 699                  * If an interrupt occurred we have to clean up the
 700                  * queue
 701                  *
 702                  */
 703                 if (queue.status == 1)
 704                 {
 705                         error = try_atomic_semop (sma, sops, nsops, un,
 706                                                   current->pid,0);
 707                         if (error <= 0)
 708                                 break;
 709                 } else {
 710                         error = queue.status;;
 711                         if (queue.prev) /* got Interrupt */
 712                                 break;
 713                         /* Everything done by update_queue */
 714                         current->semsleeping = NULL;
 715                         goto out;
 716                 }
 717         }
 718         current->semsleeping = NULL;
 719         remove_from_queue(sma,&queue);
 720 update:
 721         if (alter)
 722                 update_queue (sma);
 723 out:
 724         unlock_kernel();
 725         return error;
 726 }
 727
 728 /*
 729  * add semadj values to semaphores, free undo structures.
 730  * undo structures are not freed when semaphore arrays are destroyed
 731  * so some of them may be out of date.
 732  * IMPLEMENTATION NOTE: There is some confusion over whether the
 733  * set of adjustments that needs to be done should be done in an atomic
 734  * manner or not. That is, if we are attempting to decrement the semval
 735  * should we queue up and wait until we can do so legally?
 736  * The original implementation attempted to do this (queue and wait).
 737  * The current implementation does not do so. The POSIX standard
 738  * and SVID should be consulted to determine what behavior is mandated.
 739  */
 740 void sem_exit (void)
 741 {
 742         struct sem_queue *q;
 743         struct sem_undo *u, *un = NULL, **up, **unp;
 744         struct semid_ds *sma;
 745         int nsems, i;
 746
 747         /* If the current process was sleeping for a semaphore,
 748          * remove it from the queue.
 749          */
 750         if ((q = current->semsleeping)) {
 751                 if (q->prev)
 752                         remove_from_queue(q->sma,q);
 753                 current->semsleeping = NULL;
 754         }
 755
 756         for (up = &current->semundo; (u = *up); *up = u->proc_next, kfree(u)) {
 757                 if (u->semid == -1)
 758                         continue;
 759                 sma = semary[(unsigned int) u->semid % SEMMNI];
 760                 if (sma == IPC_UNUSED || sma == IPC_NOID)
 761                         continue;
 762                 if (sma->sem_perm.seq != (unsigned int) u->semid / SEMMNI)
 763                         continue;
 764                 /* remove u from the sma->undo list */
 765                 for (unp = &sma->undo; (un = *unp); unp = &un->id_next) {
 766                         if (u == un)
 767                                 goto found;
 768                 }
 769                 printk ("sem_exit undo list error id=%d\n", u->semid);
 770                 break;
 771 found:
 772                 *unp = un->id_next;
 773                 /* perform adjustments registered in u */
 774                 nsems = sma->sem_nsems;
 775                 for (i = 0; i < nsems; i++) {
 776                         struct sem * sem = &sma->sem_base[i];
 777                         sem->semval += u->semadj[i];
 778                         if (sem->semval < 0)
 779                                 sem->semval = 0; /* shouldn't happen */
 780                         sem->sempid = current->pid;
 781                 }
 782                 sma->sem_otime = CURRENT_TIME;
 783                 /* maybe some queued-up processes were waiting for this */
 784                 update_queue(sma);
 785         }
 786         current->semundo = NULL;
 787 }