servers/ipc/sem.c

   1 #define __USE_MISC
   2
   3 #include <minix/vm.h>
   4
   5 #include "inc.h"
   6
   7 struct waiting {
   8         endpoint_t who;                 /* who is waiting */
   9         int val;                        /* value he/she is waiting for */
  10 };
  11
  12 struct semaphore {
  13         unsigned short semval;          /* semaphore value */
  14         unsigned short semzcnt;         /* # waiting for zero */
  15         unsigned short semncnt;         /* # waiting for increase */
  16         struct waiting *zlist;          /* process waiting for zero */
  17         struct waiting *nlist;          /* process waiting for increase */
  18         pid_t sempid;                   /* process that did last op */
  19 };
  20
  21 struct sem_struct {
  22         key_t key;
  23         int id;
  24         struct semid_ds semid_ds;
  25         struct semaphore sems[SEMMSL];
  26 };
  27
  28 PRIVATE struct sem_struct sem_list[SEMMNI];
  29 PRIVATE int sem_list_nr = 0;
  30
  31 PRIVATE struct sem_struct *sem_find_key(key_t key)
  32 {
  33         int i;
  34         if (key == IPC_PRIVATE)
  35                 return NULL;
  36         for (i = 0; i < sem_list_nr; i++)
  37                 if (sem_list[i].key == key)
  38                         return sem_list+i;
  39         return NULL;
  40 }
  41
  42 PRIVATE struct sem_struct *sem_find_id(int id)
  43 {
  44         int i;
  45         for (i = 0; i < sem_list_nr; i++)
  46                 if (sem_list[i].id == id)
  47                         return sem_list+i;
  48         return NULL;
  49 }
  50
  51 /*===========================================================================*
  52  *                              do_semget                                    *
  53  *===========================================================================*/
  54 PUBLIC int do_semget(message *m)
  55 {
  56         key_t key;
  57         int nsems, flag, id;
  58         struct sem_struct *sem;
  59
  60         key = m->SEMGET_KEY;
  61         nsems = m->SEMGET_NR;
  62         flag = m->SEMGET_FLAG;
  63
  64         if ((sem = sem_find_key(key))) {
  65                 if ((flag & IPC_CREAT) && (flag & IPC_EXCL))
  66                         return EEXIST;
  67                 if (!check_perm(&sem->semid_ds.sem_perm, who_e, flag))
  68                         return EACCES;
  69                 if (nsems > sem->semid_ds.sem_nsems)
  70                         return EINVAL;
  71                 id = sem->id;
  72         } else {
  73                 if (!(flag & IPC_CREAT))
  74                         return ENOENT;
  75                 if (nsems < 0 || nsems >= SEMMSL)
  76                         return EINVAL;
  77                 if (sem_list_nr == SEMMNI)
  78                         return ENOSPC;
  79
  80                 /* create a new semaphore set */
  81                 sem = &sem_list[sem_list_nr];
  82                 memset(sem, 0, sizeof(struct sem_struct));
  83                 sem->semid_ds.sem_perm.cuid =
  84                         sem->semid_ds.sem_perm.uid = getnuid(who_e);
  85                 sem->semid_ds.sem_perm.cgid =
  86                         sem->semid_ds.sem_perm.gid = getngid(who_e);
  87                 sem->semid_ds.sem_perm.mode = flag & 0777;
  88                 sem->semid_ds.sem_nsems = nsems;
  89                 sem->semid_ds.sem_otime = 0;
  90                 sem->semid_ds.sem_ctime = time(NULL);
  91                 sem->id = id = identifier++;
  92                 sem->key = key;
  93
  94                 sem_list_nr++;
  95         }
  96
  97         m->SEMGET_RETID = id;
  98         return OK;
  99 }
 100
 101 PRIVATE void send_message_to_process(endpoint_t who, int ret, int ignore)
 102 {
 103         message m;
 104         int r;
 105
 106         m.m_type = ret;
 107         sendnb(who, &m);
 108 }
 109
 110 PRIVATE void remove_semaphore(struct sem_struct *sem)
 111 {
 112         int i, nr;
 113
 114         nr = sem->semid_ds.sem_nsems;
 115
 116         for (i = 0; i < nr; i++) {
 117                 if (sem->sems[i].zlist)
 118                         free(sem->sems[i].zlist);
 119                 if (sem->sems[i].nlist)
 120                         free(sem->sems[i].nlist);
 121         }
 122
 123         for (i = 0; i < sem_list_nr; i++) {
 124                 if (&sem_list[i] == sem)
 125                         break;
 126         }
 127
 128         if (i < sem_list_nr && --sem_list_nr != i)
 129                 sem_list[i] = sem_list[sem_list_nr];
 130 }
 131
 132 PRIVATE void show_semaphore(void)
 133 {
 134         int i, j, k;
 135
 136         for (i = 0; i < sem_list_nr; i++) {
 137                 int nr = sem_list[i].semid_ds.sem_nsems;
 138
 139                 printf("===== [%d] =====\n", i);
 140                 for (j = 0; j < nr; j++) {
 141                         struct semaphore *semaphore = &sem_list[i].sems[j];
 142
 143                         if (!semaphore->semzcnt && !semaphore->semncnt)
 144                                 continue;
 145
 146                         printf("  (%d): ", semaphore->semval);
 147                         if (semaphore->semzcnt) {
 148                                 printf("zero(");
 149                                 for (k = 0; k < semaphore->semzcnt; k++)
 150                                         printf("%d,", semaphore->zlist[k].who);
 151                                 printf(")    ");
 152                         }
 153                         if (semaphore->semncnt) {
 154                                 printf("incr(");
 155                                 for (k = 0; k < semaphore->semncnt; k++)
 156                                         printf("%d-%d,",
 157                                                 semaphore->nlist[k].who, semaphore->nlist[k].val);
 158                                 printf(")");
 159                         }
 160                         printf("\n");
 161                 }
 162         }
 163         printf("\n");
 164 }
 165
 166 PRIVATE void remove_process(endpoint_t pt)
 167 {
 168         int i;
 169
 170         for (i = 0; i < sem_list_nr; i++) {
 171                 struct sem_struct *sem = &sem_list[i];
 172                 int nr = sem->semid_ds.sem_nsems;
 173                 int j;
 174
 175                 for (j = 0; j < nr; j++) {
 176                         struct semaphore *semaphore = &sem->sems[j];
 177                         int k;
 178
 179                         for (k = 0; k < semaphore->semzcnt; k++) {
 180                                 endpoint_t who_waiting = semaphore->zlist[k].who;
 181
 182                                 if (who_waiting == pt) {
 183                                         /* remove this slot first */
 184                                         memmove(semaphore->zlist+k, semaphore->zlist+k+1,
 185                                                 sizeof(struct waiting) * (semaphore->semzcnt-k-1));
 186                                         --semaphore->semzcnt;
 187                                         /* then send message to the process */
 188                                         send_message_to_process(who_waiting, EINTR, 1);
 189
 190                                         break;
 191                                 }
 192                         }
 193
 194                         for (k = 0; k < semaphore->semncnt; k++) {
 195                                 endpoint_t who_waiting = semaphore->nlist[k].who;
 196
 197                                 if (who_waiting == pt) {
 198                                         /* remove it first */
 199                                         memmove(semaphore->nlist+k, semaphore->nlist+k+1,
 200                                                 sizeof(struct waiting) * (semaphore->semncnt-k-1));
 201                                         --semaphore->semncnt;
 202                                         /* send the message to the process */
 203                                         send_message_to_process(who_waiting, EINTR, 1);
 204
 205                                         break;
 206                                 }
 207                         }
 208                 }
 209         }
 210 }
 211
 212 PRIVATE void update_one_semaphore(struct sem_struct *sem, int is_remove)
 213 {
 214         int i, j, nr;
 215         struct semaphore *semaphore;
 216         endpoint_t who;
 217
 218         nr = sem->semid_ds.sem_nsems;
 219
 220         if (is_remove) {
 221                 for (i = 0; i < nr; i++) {
 222                         semaphore = &sem->sems[i];
 223
 224                         for (j = 0; j < semaphore->semzcnt; j++)
 225                                 send_message_to_process(semaphore->zlist[j].who, EIDRM, 0);
 226                         for (j = 0; j < semaphore->semncnt; j++)
 227                                 send_message_to_process(semaphore->nlist[j].who, EIDRM, 0);
 228                 }
 229
 230                 remove_semaphore(sem);
 231                 return;
 232         }
 233
 234         for (i = 0; i < nr; i++) {
 235                 semaphore = &sem->sems[i];
 236
 237                 if (semaphore->zlist && !semaphore->semval) {
 238                         /* choose one process, policy: FIFO. */
 239                         who = semaphore->zlist[0].who;
 240
 241                         memmove(semaphore->zlist, semaphore->zlist+1,
 242                                 sizeof(struct waiting) * (semaphore->semzcnt-1));
 243                         --semaphore->semzcnt;
 244
 245                         send_message_to_process(who, OK, 0);
 246                 }
 247
 248                 if (semaphore->nlist) {
 249                         for (j = 0; j < semaphore->semncnt; j++) {
 250                                 if (semaphore->nlist[j].val <= semaphore->semval) {
 251                                         semaphore->semval -= semaphore->nlist[j].val;
 252                                         who = semaphore->nlist[j].who;
 253
 254                                         memmove(semaphore->nlist+j, semaphore->nlist+j+1,
 255                                                 sizeof(struct waiting) * (semaphore->semncnt-j-1));
 256                                         --semaphore->semncnt;
 257
 258                                         send_message_to_process(who, OK, 0);
 259
 260                                         /* choose only one process */
 261                                         break;
 262                                 }
 263                         }
 264                 }
 265         }
 266 }
 267
 268 PRIVATE void update_semaphores(void)
 269 {
 270         int i;
 271
 272         for (i = 0; i < sem_list_nr; i++)
 273                 update_one_semaphore(sem_list+i, 0 /* not remove */);
 274 }
 275
 276 /*===========================================================================*
 277  *                              do_semctl                                    *
 278  *===========================================================================*/
 279 PUBLIC int do_semctl(message *m)
 280 {
 281         int r, i;
 282         long opt;
 283         uid_t uid;
 284         int id, num, cmd, val;
 285         unsigned short *buf;
 286         struct semid_ds *ds, tmp_ds;
 287         struct sem_struct *sem;
 288
 289         id = m->SEMCTL_ID;
 290         num = m->SEMCTL_NUM;
 291         cmd = m->SEMCTL_CMD;
 292
 293         if (cmd == IPC_STAT || cmd == IPC_SET || cmd == IPC_INFO ||
 294                 cmd == SEM_INFO || cmd == SEM_STAT || cmd == GETALL ||
 295                 cmd == SETALL || cmd == SETVAL)
 296                 opt = m->SEMCTL_OPT;
 297
 298         if (!(sem = sem_find_id(id))) {
 299                 return EINVAL;
 300         }
 301
 302         /* IPC_SET and IPC_RMID as its own permission check */
 303         if (cmd != IPC_SET && cmd != IPC_RMID) {
 304                 /* check read permission */
 305                 if (!check_perm(&sem->semid_ds.sem_perm, who_e, 0444))
 306                         return EACCES;
 307         }
 308
 309         switch (cmd) {
 310         case IPC_STAT:
 311                 ds = (struct semid_ds *) opt;
 312                 if (!ds)
 313                         return EFAULT;
 314                 r = sys_datacopy(SELF_E, (vir_bytes) &sem->semid_ds,
 315                         who_e, (vir_bytes) ds, sizeof(struct semid_ds));
 316                 if (r != OK)
 317                         return EINVAL;
 318                 break;
 319         case IPC_SET:
 320                 uid = getnuid(who_e);
 321                 if (uid != sem->semid_ds.sem_perm.cuid &&
 322                         uid != sem->semid_ds.sem_perm.uid &&
 323                         uid != 0)
 324                         return EPERM;
 325                 ds = (struct semid_ds *) opt;
 326                 r = sys_datacopy(who_e, (vir_bytes) ds,
 327                         SELF_E, (vir_bytes) &tmp_ds, sizeof(struct semid_ds));
 328                 if (r != OK)
 329                         return EINVAL;
 330                 sem->semid_ds.sem_perm.uid = tmp_ds.sem_perm.uid;
 331                 sem->semid_ds.sem_perm.gid = tmp_ds.sem_perm.gid;
 332                 sem->semid_ds.sem_perm.mode &= ~0777;
 333                 sem->semid_ds.sem_perm.mode |= tmp_ds.sem_perm.mode & 0666;
 334                 sem->semid_ds.sem_ctime = time(NULL);
 335                 break;
 336         case IPC_RMID:
 337                 uid = getnuid(who_e);
 338                 if (uid != sem->semid_ds.sem_perm.cuid &&
 339                         uid != sem->semid_ds.sem_perm.uid &&
 340                         uid != 0)
 341                         return EPERM;
 342                 /* awaken all processes block in semop
 343                  * and remove the semaphore set.
 344                  */
 345                 update_one_semaphore(sem, 1);
 346                 break;
 347         case IPC_INFO:
 348                 break;
 349         case SEM_INFO:
 350                 break;
 351         case SEM_STAT:
 352                 break;
 353         case GETALL:
 354                 buf = malloc(sizeof(unsigned short) * sem->semid_ds.sem_nsems);
 355                 if (!buf)
 356                         return ENOMEM;
 357                 for (i = 0; i < sem->semid_ds.sem_nsems; i++)
 358                         buf[i] = sem->sems[i].semval;
 359                 r = sys_datacopy(SELF_E, (vir_bytes) buf,
 360                         who_e, (vir_bytes) opt,
 361                         sizeof(unsigned short) * sem->semid_ds.sem_nsems);
 362                 if (r != OK)
 363                         return EINVAL;
 364                 free(buf);
 365                 break;
 366         case GETNCNT:
 367                 if (num < 0 || num >= sem->semid_ds.sem_nsems)
 368                         return EINVAL;
 369                 m->SHMCTL_RET = sem->sems[num].semncnt;
 370                 break;
 371         case GETPID:
 372                 if (num < 0 || num >= sem->semid_ds.sem_nsems)
 373                         return EINVAL;
 374                 m->SHMCTL_RET = sem->sems[num].sempid;
 375                 break;
 376         case GETVAL:
 377                 if (num < 0 || num >= sem->semid_ds.sem_nsems)
 378                         return EINVAL;
 379                 m->SHMCTL_RET = sem->sems[num].semval;
 380                 break;
 381         case GETZCNT:
 382                 if (num < 0 || num >= sem->semid_ds.sem_nsems)
 383                         return EINVAL;
 384                 m->SHMCTL_RET = sem->sems[num].semzcnt;
 385                 break;
 386         case SETALL:
 387                 buf = malloc(sizeof(unsigned short) * sem->semid_ds.sem_nsems);
 388                 if (!buf)
 389                         return ENOMEM;
 390                 r = sys_datacopy(who_e, (vir_bytes) opt,
 391                         SELF_E, (vir_bytes) buf,
 392                         sizeof(unsigned short) * sem->semid_ds.sem_nsems);
 393                 if (r != OK)
 394                         return EINVAL;
 395 #ifdef DEBUG_SEM
 396                 printf("SEMCTL: SETALL: opt: %p\n");
 397                 for (i = 0; i < sem->semid_ds.sem_nsems; i++)
 398                         printf("SEMCTL: SETALL val: [%d] %d\n", i, buf[i]);
 399 #endif
 400                 for (i = 0; i < sem->semid_ds.sem_nsems; i++) {
 401                         if (buf[i] < 0 || buf[i] > SEMVMX) {
 402                                 free(buf);
 403                                 update_semaphores();
 404                                 return ERANGE;
 405                         }
 406                         sem->sems[i].semval = buf[i];
 407                 }
 408                 free(buf);
 409                 /* awaken if possible */
 410                 update_semaphores();
 411                 break;
 412         case SETVAL:
 413                 val = (int) opt;
 414                 /* check write permission */
 415                 if (!check_perm(&sem->semid_ds.sem_perm, who_e, 0222))
 416                         return EACCES;
 417                 if (num < 0 || num >= sem->semid_ds.sem_nsems)
 418                         return EINVAL;
 419                 if (val < 0 || val > SEMVMX)
 420                         return ERANGE;
 421                 sem->sems[num].semval = val;
 422 #ifdef DEBUG_SEM
 423                 printf("SEMCTL: SETVAL: %d %d\n", num, val);
 424 #endif
 425                 sem->semid_ds.sem_ctime = time(NULL);
 426                 /* awaken if possible */
 427                 update_semaphores();
 428                 break;
 429         default:
 430                 return EINVAL;
 431         }
 432
 433         return OK;
 434 }
 435
 436 /*===========================================================================*
 437  *                              do_semop                                     *
 438  *===========================================================================*/
 439 PUBLIC int do_semop(message *m)
 440 {
 441         int id, i, j, r;
 442         struct sembuf *sops;
 443         unsigned int nsops;
 444         struct sem_struct *sem;
 445         int no_reply = 0;
 446
 447         id = m->SEMOP_ID;
 448         nsops = (unsigned int) m->SEMOP_SIZE;
 449
 450         r = EINVAL;
 451         if (!(sem = sem_find_id(id)))
 452                 goto out;
 453
 454         if (nsops <= 0)
 455                 goto out;
 456
 457         r = E2BIG;
 458         if (nsops > SEMOPM)
 459                 goto out;
 460
 461         /* check for read permission */
 462         r = EACCES;
 463         if (!check_perm(&sem->semid_ds.sem_perm, who_e, 0444))
 464                 goto out;
 465
 466         /* get the array from user application */
 467         r = ENOMEM;
 468         sops = malloc(sizeof(struct sembuf) * nsops);
 469         if (!sops)
 470                 goto out_free;
 471         r = sys_datacopy(who_e, (vir_bytes) m->SEMOP_OPS,
 472                         SELF_E, (vir_bytes) sops,
 473                         sizeof(struct sembuf) * nsops);
 474         if (r != OK) {
 475                 r = EINVAL;
 476                 goto out_free;
 477         }
 478
 479 #ifdef DEBUG_SEM
 480         for (i = 0; i < nsops; i++)
 481                 printf("SEMOP: num:%d  op:%d  flg:%d\n",
 482                         sops[i].sem_num, sops[i].sem_op, sops[i].sem_flg);
 483 #endif
 484         /* check for value range */
 485         r = EFBIG;
 486         for (i = 0; i < nsops; i++)
 487                 if (sops[i].sem_num < 0 ||
 488                                 sops[i].sem_num >= sem->semid_ds.sem_nsems)
 489                         goto out_free;
 490
 491         /* check for duplicate number */
 492         r = EINVAL;
 493         for (i = 0; i < nsops; i++)
 494                 for (j = i + 1; j < nsops; j++)
 495                         if (sops[i].sem_num == sops[j].sem_num)
 496                                 goto out_free;
 497
 498         /* check for EAGAIN error */
 499         r = EAGAIN;
 500         for (i = 0; i < nsops; i++) {
 501                 int op_n, val;
 502
 503                 op_n = sops[i].sem_op;
 504                 val = sem->sems[sops[i].sem_num].semval;
 505
 506                 if ((sops[i].sem_flg & IPC_NOWAIT) &&
 507                                 ((!op_n && val) ||
 508                                  (op_n < 0 &&
 509                                   -op_n > val)))
 510                         goto out_free;
 511
 512         }
 513         /* there will be no errors left, so we can go ahead */
 514         for (i = 0; i < nsops; i++) {
 515                 struct semaphore *s;
 516                 int op_n;
 517
 518                 s = &sem->sems[sops[i].sem_num];
 519                 op_n = sops[i].sem_op;
 520
 521                 s->sempid = getnpid(who_e);
 522
 523                 if (op_n > 0) {
 524                         /* check for alter permission */
 525                         r = EACCES;
 526                         if (!check_perm(&sem->semid_ds.sem_perm, who_e, 0222))
 527                                 goto out_free;
 528                         s->semval += sops[i].sem_op;
 529                 } else if (!op_n) {
 530                         if (s->semval) {
 531                                 /* put the process asleep */
 532                                 s->semzcnt++;
 533                                 s->zlist = realloc(s->zlist, sizeof(struct waiting) * s->semzcnt);
 534                                 if (!s->zlist) {
 535                                         printf("IPC: zero waiting list lost...\n");
 536                                         break;
 537                                 }
 538                                 s->zlist[s->semzcnt-1].who = who_e;
 539                                 s->zlist[s->semzcnt-1].val = op_n;
 540
 541 #ifdef DEBUG_SEM
 542                                 printf("SEMOP: Put into sleep... %d\n", who_e);
 543 #endif
 544                                 no_reply++;
 545                         }
 546                 } else {
 547                         /* check for alter permission */
 548                         r = EACCES;
 549                         if (!check_perm(&sem->semid_ds.sem_perm, who_e, 0222))
 550                                 goto out_free;
 551                         if (s->semval >= -op_n)
 552                                 s->semval += op_n;
 553                         else {
 554                                 /* put the process asleep */
 555                                 s->semncnt++;
 556                                 s->nlist = realloc(s->nlist, sizeof(struct waiting) * s->semncnt);
 557                                 if (!s->nlist) {
 558                                         printf("IPC: increase waiting list lost...\n");
 559                                         break;
 560                                 }
 561                                 s->nlist[s->semncnt-1].who = who_e;
 562                                 s->nlist[s->semncnt-1].val = -op_n;
 563
 564                                 no_reply++;
 565                         }
 566                 }
 567         }
 568
 569         r = OK;
 570 out_free:
 571         free(sops);
 572 out:
 573         /* if we reach here by errors
 574          * or with no errors but we should reply back.
 575          */
 576         if (r != OK || !no_reply) {
 577                 m->m_type = r;
 578
 579                 sendnb(who_e, m);
 580         }
 581
 582         /* awaken process if possible */
 583         update_semaphores();
 584
 585         return 0;
 586 }
 587
 588 /*===========================================================================*
 589  *                              is_sem_nil                                   *
 590  *===========================================================================*/
 591 PUBLIC int is_sem_nil(void)
 592 {
 593         return (sem_list_nr == 0);
 594 }
 595
 596 /*===========================================================================*
 597  *                              sem_process_vm_notify                        *
 598  *===========================================================================*/
 599 PUBLIC void sem_process_vm_notify(void)
 600 {
 601         endpoint_t pt;
 602         int r;
 603
 604         while ((r = vm_query_exit(&pt)) >= 0) {
 605                 /* for each enpoint 'pt', check whether it's waiting... */
 606                 remove_process(pt);
 607
 608                 if (r == 0)
 609                         break;
 610         }
 611         if (r < 0)
 612                 printf("IPC: query exit error!\n");
 613 }
 614