xref: /minix/minix/servers/ipc/sem.c (revision 7f5f010b) 
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 static struct sem_struct sem_list[SEMMNI];
29 static int sem_list_nr = 0;
30 
31 static 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 static 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 int do_semget(message *m)
55 {
56 	key_t key;
57 	int nsems, flag, id;
58 	struct sem_struct *sem;
59 
60 	key = m->m_lc_ipc_semget.key;
61 	nsems = m->m_lc_ipc_semget.nr;
62 	flag = m->m_lc_ipc_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->m_lc_ipc_semget.retid = id;
98 	return OK;
99 }
100 
101 static void send_message_to_process(endpoint_t who, int ret, int ignore)
102 {
103 	message m;
104 
105 	m.m_type = ret;
106 	ipc_sendnb(who, &m);
107 }
108 
109 static void remove_semaphore(struct sem_struct *sem)
110 {
111 	int i, nr;
112 
113 	nr = sem->semid_ds.sem_nsems;
114 
115 	for (i = 0; i < nr; i++) {
116 		if (sem->sems[i].zlist)
117 			free(sem->sems[i].zlist);
118 		if (sem->sems[i].nlist)
119 			free(sem->sems[i].nlist);
120 	}
121 
122 	for (i = 0; i < sem_list_nr; i++) {
123 		if (&sem_list[i] == sem)
124 			break;
125 	}
126 
127 	if (i < sem_list_nr && --sem_list_nr != i)
128 		sem_list[i] = sem_list[sem_list_nr];
129 }
130 
131 #if 0
132 static 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 #endif
166 
167 static void remove_process(endpoint_t pt)
168 {
169 	int i;
170 
171 	for (i = 0; i < sem_list_nr; i++) {
172 		struct sem_struct *sem = &sem_list[i];
173 		int nr = sem->semid_ds.sem_nsems;
174 		int j;
175 
176 		for (j = 0; j < nr; j++) {
177 			struct semaphore *semaphore = &sem->sems[j];
178 			int k;
179 
180 			for (k = 0; k < semaphore->semzcnt; k++) {
181 				endpoint_t who_waiting = semaphore->zlist[k].who;
182 
183 				if (who_waiting == pt) {
184 					/* remove this slot first */
185 					memmove(semaphore->zlist+k, semaphore->zlist+k+1,
186 						sizeof(struct waiting) * (semaphore->semzcnt-k-1));
187 					--semaphore->semzcnt;
188 					/* then send message to the process */
189 					send_message_to_process(who_waiting, EINTR, 1);
190 
191 					break;
192 				}
193 			}
194 
195 			for (k = 0; k < semaphore->semncnt; k++) {
196 				endpoint_t who_waiting = semaphore->nlist[k].who;
197 
198 				if (who_waiting == pt) {
199 					/* remove it first */
200 					memmove(semaphore->nlist+k, semaphore->nlist+k+1,
201 						sizeof(struct waiting) * (semaphore->semncnt-k-1));
202 					--semaphore->semncnt;
203 					/* send the message to the process */
204 					send_message_to_process(who_waiting, EINTR, 1);
205 
206 					break;
207 				}
208 			}
209 		}
210 	}
211 }
212 
213 static void update_one_semaphore(struct sem_struct *sem, int is_remove)
214 {
215 	int i, j, nr;
216 	struct semaphore *semaphore;
217 	endpoint_t who;
218 
219 	nr = sem->semid_ds.sem_nsems;
220 
221 	if (is_remove) {
222 		for (i = 0; i < nr; i++) {
223 			semaphore = &sem->sems[i];
224 
225 			for (j = 0; j < semaphore->semzcnt; j++)
226 				send_message_to_process(semaphore->zlist[j].who, EIDRM, 0);
227 			for (j = 0; j < semaphore->semncnt; j++)
228 				send_message_to_process(semaphore->nlist[j].who, EIDRM, 0);
229 		}
230 
231 		remove_semaphore(sem);
232 		return;
233 	}
234 
235 	for (i = 0; i < nr; i++) {
236 		semaphore = &sem->sems[i];
237 
238 		if (semaphore->zlist && !semaphore->semval) {
239 			/* choose one process, policy: FIFO. */
240 			who = semaphore->zlist[0].who;
241 
242 			memmove(semaphore->zlist, semaphore->zlist+1,
243 				sizeof(struct waiting) * (semaphore->semzcnt-1));
244 			--semaphore->semzcnt;
245 
246 			send_message_to_process(who, OK, 0);
247 		}
248 
249 		if (semaphore->nlist) {
250 			for (j = 0; j < semaphore->semncnt; j++) {
251 				if (semaphore->nlist[j].val <= semaphore->semval) {
252 					semaphore->semval -= semaphore->nlist[j].val;
253 					who = semaphore->nlist[j].who;
254 
255 					memmove(semaphore->nlist+j, semaphore->nlist+j+1,
256 						sizeof(struct waiting) * (semaphore->semncnt-j-1));
257 					--semaphore->semncnt;
258 
259 					send_message_to_process(who, OK, 0);
260 
261 					/* choose only one process */
262 					break;
263 				}
264 			}
265 		}
266 	}
267 }
268 
269 static void update_semaphores(void)
270 {
271 	int i;
272 
273 	for (i = 0; i < sem_list_nr; i++)
274 		update_one_semaphore(sem_list+i, 0 /* not remove */);
275 }
276 
277 /*===========================================================================*
278  *				do_semctl		     		     *
279  *===========================================================================*/
280 int do_semctl(message *m)
281 {
282 	int r, i;
283 	long opt = 0;
284 	uid_t uid;
285 	int id, num, cmd, val;
286 	unsigned short *buf;
287 	struct semid_ds *ds, tmp_ds;
288 	struct sem_struct *sem;
289 
290 	id = m->m_lc_ipc_semctl.id;
291 	num = m->m_lc_ipc_semctl.num;
292 	cmd = m->m_lc_ipc_semctl.cmd;
293 
294 	if (cmd == IPC_STAT || cmd == IPC_SET || cmd == IPC_INFO ||
295 		cmd == SEM_INFO || cmd == SEM_STAT || cmd == GETALL ||
296 		cmd == SETALL || cmd == SETVAL)
297 		opt = m->m_lc_ipc_semctl.opt;
298 
299 	if (!(sem = sem_find_id(id))) {
300 		return EINVAL;
301 	}
302 
303 	/* IPC_SET and IPC_RMID as its own permission check */
304 	if (cmd != IPC_SET && cmd != IPC_RMID) {
305 		/* check read permission */
306 		if (!check_perm(&sem->semid_ds.sem_perm, who_e, 0444))
307 			return EACCES;
308 	}
309 
310 	switch (cmd) {
311 	case IPC_STAT:
312 		ds = (struct semid_ds *) opt;
313 		if (!ds)
314 			return EFAULT;
315 		r = sys_datacopy(SELF, (vir_bytes) &sem->semid_ds,
316 			who_e, (vir_bytes) ds, sizeof(struct semid_ds));
317 		if (r != OK)
318 			return EINVAL;
319 		break;
320 	case IPC_SET:
321 		uid = getnuid(who_e);
322 		if (uid != sem->semid_ds.sem_perm.cuid &&
323 			uid != sem->semid_ds.sem_perm.uid &&
324 			uid != 0)
325 			return EPERM;
326 		ds = (struct semid_ds *) opt;
327 		r = sys_datacopy(who_e, (vir_bytes) ds,
328 			SELF, (vir_bytes) &tmp_ds, sizeof(struct semid_ds));
329 		if (r != OK)
330 			return EINVAL;
331 		sem->semid_ds.sem_perm.uid = tmp_ds.sem_perm.uid;
332 		sem->semid_ds.sem_perm.gid = tmp_ds.sem_perm.gid;
333 		sem->semid_ds.sem_perm.mode &= ~0777;
334 		sem->semid_ds.sem_perm.mode |= tmp_ds.sem_perm.mode & 0666;
335 		sem->semid_ds.sem_ctime = time(NULL);
336 		break;
337 	case IPC_RMID:
338 		uid = getnuid(who_e);
339 		if (uid != sem->semid_ds.sem_perm.cuid &&
340 			uid != sem->semid_ds.sem_perm.uid &&
341 			uid != 0)
342 			return EPERM;
343 		/* awaken all processes block in semop
344 		 * and remove the semaphore set.
345 		 */
346 		update_one_semaphore(sem, 1);
347 		break;
348 	case IPC_INFO:
349 		break;
350 	case SEM_INFO:
351 		break;
352 	case SEM_STAT:
353 		break;
354 	case GETALL:
355 		buf = malloc(sizeof(unsigned short) * sem->semid_ds.sem_nsems);
356 		if (!buf)
357 			return ENOMEM;
358 		for (i = 0; i < sem->semid_ds.sem_nsems; i++)
359 			buf[i] = sem->sems[i].semval;
360 		r = sys_datacopy(SELF, (vir_bytes) buf,
361 			who_e, (vir_bytes) opt,
362 			sizeof(unsigned short) * sem->semid_ds.sem_nsems);
363 		if (r != OK)
364 			return EINVAL;
365 		free(buf);
366 		break;
367 	case GETNCNT:
368 		if (num < 0 || num >= sem->semid_ds.sem_nsems)
369 			return EINVAL;
370 		m->m_lc_ipc_semctl.ret = sem->sems[num].semncnt;
371 		break;
372 	case GETPID:
373 		if (num < 0 || num >= sem->semid_ds.sem_nsems)
374 			return EINVAL;
375 		m->m_lc_ipc_semctl.ret = sem->sems[num].sempid;
376 		break;
377 	case GETVAL:
378 		if (num < 0 || num >= sem->semid_ds.sem_nsems)
379 			return EINVAL;
380 		m->m_lc_ipc_semctl.ret = sem->sems[num].semval;
381 		break;
382 	case GETZCNT:
383 		if (num < 0 || num >= sem->semid_ds.sem_nsems)
384 			return EINVAL;
385 		m->m_lc_ipc_semctl.ret = sem->sems[num].semzcnt;
386 		break;
387 	case SETALL:
388 		buf = malloc(sizeof(unsigned short) * sem->semid_ds.sem_nsems);
389 		if (!buf)
390 			return ENOMEM;
391 		r = sys_datacopy(who_e, (vir_bytes) opt,
392 			SELF, (vir_bytes) buf,
393 			sizeof(unsigned short) * sem->semid_ds.sem_nsems);
394 		if (r != OK)
395 			return EINVAL;
396 #ifdef DEBUG_SEM
397 		printf("SEMCTL: SETALL: opt: %lu\n", (vir_bytes) opt);
398 		for (i = 0; i < sem->semid_ds.sem_nsems; i++)
399 			printf("SEMCTL: SETALL val: [%d] %d\n", i, buf[i]);
400 #endif
401 		for (i = 0; i < sem->semid_ds.sem_nsems; i++) {
402 			if (buf[i] > SEMVMX) {
403 				free(buf);
404 				update_semaphores();
405 				return ERANGE;
406 			}
407 			sem->sems[i].semval = buf[i];
408 		}
409 		free(buf);
410 		/* awaken if possible */
411 		update_semaphores();
412 		break;
413 	case SETVAL:
414 		val = (int) opt;
415 		/* check write permission */
416 		if (!check_perm(&sem->semid_ds.sem_perm, who_e, 0222))
417 			return EACCES;
418 		if (num < 0 || num >= sem->semid_ds.sem_nsems)
419 			return EINVAL;
420 		if (val < 0 || val > SEMVMX)
421 			return ERANGE;
422 		sem->sems[num].semval = val;
423 #ifdef DEBUG_SEM
424 		printf("SEMCTL: SETVAL: %d %d\n", num, val);
425 #endif
426 		sem->semid_ds.sem_ctime = time(NULL);
427 		/* awaken if possible */
428 		update_semaphores();
429 		break;
430 	default:
431 		return EINVAL;
432 	}
433 
434 	return OK;
435 }
436 
437 /*===========================================================================*
438  *				do_semop		     		     *
439  *===========================================================================*/
440 int do_semop(message *m)
441 {
442 	int id, i, j, r;
443 	struct sembuf *sops;
444 	unsigned int nsops;
445 	struct sem_struct *sem;
446 	int no_reply = 0;
447 
448 	id = m->m_lc_ipc_semop.id;
449 	nsops = m->m_lc_ipc_semop.size;
450 
451 	r = EINVAL;
452 	if (!(sem = sem_find_id(id)))
453 		goto out;
454 
455 	if (nsops <= 0)
456 		goto out;
457 
458 	r = E2BIG;
459 	if (nsops > SEMOPM)
460 		goto out;
461 
462 	/* check for read permission */
463 	r = EACCES;
464 	if (!check_perm(&sem->semid_ds.sem_perm, who_e, 0444))
465 		goto out;
466 
467 	/* get the array from user application */
468 	r = ENOMEM;
469 	sops = malloc(sizeof(struct sembuf) * nsops);
470 	if (!sops)
471 		goto out_free;
472 	r = sys_datacopy(who_e, (vir_bytes) m->m_lc_ipc_semop.ops,
473 			SELF, (vir_bytes) sops,
474 			sizeof(struct sembuf) * nsops);
475 	if (r != OK) {
476 		r = EINVAL;
477 		goto out_free;
478 	}
479 
480 #ifdef DEBUG_SEM
481 	for (i = 0; i < nsops; i++)
482 		printf("SEMOP: num:%d  op:%d  flg:%d\n",
483 			sops[i].sem_num, sops[i].sem_op, sops[i].sem_flg);
484 #endif
485 	/* check for value range */
486 	r = EFBIG;
487 	for (i = 0; i < nsops; i++)
488 		if (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 		ipc_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 int is_sem_nil(void)
592 {
593 	return (sem_list_nr == 0);
594 }
595 
596 /*===========================================================================*
597  *				sem_process_vm_notify	     		     *
598  *===========================================================================*/
599 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 
615