sem.c 40.4 KB
Newer Older
L
Linus Torvalds 已提交
1 2 3 4 5 6 7 8
/*
 * linux/ipc/sem.c
 * Copyright (C) 1992 Krishna Balasubramanian
 * Copyright (C) 1995 Eric Schenk, Bruno Haible
 *
 * /proc/sysvipc/sem support (c) 1999 Dragos Acostachioaie <dragos@iname.com>
 *
 * SMP-threaded, sysctl's added
9
 * (c) 1999 Manfred Spraul <manfred@colorfullife.com>
L
Linus Torvalds 已提交
10
 * Enforced range limit on SEM_UNDO
A
Alan Cox 已提交
11
 * (c) 2001 Red Hat Inc
L
Linus Torvalds 已提交
12 13
 * Lockless wakeup
 * (c) 2003 Manfred Spraul <manfred@colorfullife.com>
14 15
 * Further wakeup optimizations, documentation
 * (c) 2010 Manfred Spraul <manfred@colorfullife.com>
S
Steve Grubb 已提交
16 17 18
 *
 * support for audit of ipc object properties and permission changes
 * Dustin Kirkland <dustin.kirkland@us.ibm.com>
K
Kirill Korotaev 已提交
19 20 21 22
 *
 * namespaces support
 * OpenVZ, SWsoft Inc.
 * Pavel Emelianov <xemul@openvz.org>
23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
 *
 * Implementation notes: (May 2010)
 * 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
 *   SETALL calls.
 * - two Linux specific semctl() commands: SEM_STAT, SEM_INFO.
 * - undo adjustments at process exit are limited to 0..SEMVMX.
 * - namespace are supported.
 * - SEMMSL, SEMMNS, SEMOPM and SEMMNI can be configured at runtine by writing
 *   to /proc/sys/kernel/sem.
 * - statistics about the usage are reported in /proc/sysvipc/sem.
 *
 * Internals:
 * - scalability:
 *   - all global variables are read-mostly.
 *   - semop() calls and semctl(RMID) are synchronized by RCU.
 *   - most operations do write operations (actually: spin_lock calls) to
 *     the per-semaphore array structure.
 *   Thus: Perfect SMP scaling between independent semaphore arrays.
 *         If multiple semaphores in one array are used, then cache line
 *         trashing on the semaphore array spinlock will limit the scaling.
 * - semncnt and semzcnt are calculated on demand in count_semncnt() and
 *   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())
 * - 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())
 * - All work is done by the waker, the woken up task does not have to do
 *   anything - not even acquiring a lock or dropping a refcount.
 * - A woken up task may not even touch the semaphore array anymore, it may
 *   have been destroyed already by a semctl(RMID).
 * - The synchronizations between wake-ups due to a timeout/signal and a
 *   wake-up due to a completed semaphore operation is achieved by using an
 *   intermediate state (IN_WAKEUP).
 * - UNDO values are stored in an array (one per process and per
 *   semaphore array, lazily allocated). For backwards compatibility, multiple
 *   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.
L
Linus Torvalds 已提交
74 75 76 77 78 79 80 81 82 83
 */

#include <linux/slab.h>
#include <linux/spinlock.h>
#include <linux/init.h>
#include <linux/proc_fs.h>
#include <linux/time.h>
#include <linux/security.h>
#include <linux/syscalls.h>
#include <linux/audit.h>
84
#include <linux/capability.h>
85
#include <linux/seq_file.h>
N
Nadia Derbey 已提交
86
#include <linux/rwsem.h>
K
Kirill Korotaev 已提交
87
#include <linux/nsproxy.h>
88
#include <linux/ipc_namespace.h>
I
Ingo Molnar 已提交
89

L
Linus Torvalds 已提交
90 91 92
#include <asm/uaccess.h>
#include "util.h"

93
#define sem_ids(ns)	((ns)->ids[IPC_SEM_IDS])
K
Kirill Korotaev 已提交
94 95

#define sem_unlock(sma)		ipc_unlock(&(sma)->sem_perm)
N
Nadia Derbey 已提交
96
#define sem_checkid(sma, semid)	ipc_checkid(&sma->sem_perm, semid)
L
Linus Torvalds 已提交
97

N
Nadia Derbey 已提交
98
static int newary(struct ipc_namespace *, struct ipc_params *);
99
static void freeary(struct ipc_namespace *, struct kern_ipc_perm *);
L
Linus Torvalds 已提交
100
#ifdef CONFIG_PROC_FS
101
static int sysvipc_sem_proc_show(struct seq_file *s, void *it);
L
Linus Torvalds 已提交
102 103 104 105 106 107 108 109 110 111 112 113 114 115
#endif

#define SEMMSL_FAST	256 /* 512 bytes on stack */
#define SEMOPM_FAST	64  /* ~ 372 bytes on stack */

/*
 * linked list protection:
 *	sem_undo.id_next,
 *	sem_array.sem_pending{,last},
 *	sem_array.sem_undo: sem_lock() for read/write
 *	sem_undo.proc_next: only "current" is allowed to read/write that field.
 *	
 */

K
Kirill Korotaev 已提交
116 117 118 119 120
#define sc_semmsl	sem_ctls[0]
#define sc_semmns	sem_ctls[1]
#define sc_semopm	sem_ctls[2]
#define sc_semmni	sem_ctls[3]

121
void sem_init_ns(struct ipc_namespace *ns)
K
Kirill Korotaev 已提交
122 123 124 125 126 127
{
	ns->sc_semmsl = SEMMSL;
	ns->sc_semmns = SEMMNS;
	ns->sc_semopm = SEMOPM;
	ns->sc_semmni = SEMMNI;
	ns->used_sems = 0;
128
	ipc_init_ids(&ns->ids[IPC_SEM_IDS]);
K
Kirill Korotaev 已提交
129 130
}

131
#ifdef CONFIG_IPC_NS
K
Kirill Korotaev 已提交
132 133
void sem_exit_ns(struct ipc_namespace *ns)
{
134
	free_ipcs(ns, &sem_ids(ns), freeary);
S
Serge E. Hallyn 已提交
135
	idr_destroy(&ns->ids[IPC_SEM_IDS].ipcs_idr);
K
Kirill Korotaev 已提交
136
}
137
#endif
L
Linus Torvalds 已提交
138 139 140

void __init sem_init (void)
{
141
	sem_init_ns(&init_ipc_ns);
142 143
	ipc_init_proc_interface("sysvipc/sem",
				"       key      semid perms      nsems   uid   gid  cuid  cgid      otime      ctime\n",
K
Kirill Korotaev 已提交
144
				IPC_SEM_IDS, sysvipc_sem_proc_show);
L
Linus Torvalds 已提交
145 146
}

N
Nadia Derbey 已提交
147 148 149 150
/*
 * sem_lock_(check_) routines are called in the paths where the rw_mutex
 * is not held.
 */
151 152
static inline struct sem_array *sem_lock(struct ipc_namespace *ns, int id)
{
N
Nadia Derbey 已提交
153 154
	struct kern_ipc_perm *ipcp = ipc_lock(&sem_ids(ns), id);

155 156 157
	if (IS_ERR(ipcp))
		return (struct sem_array *)ipcp;

N
Nadia Derbey 已提交
158
	return container_of(ipcp, struct sem_array, sem_perm);
159 160 161 162 163
}

static inline struct sem_array *sem_lock_check(struct ipc_namespace *ns,
						int id)
{
N
Nadia Derbey 已提交
164 165
	struct kern_ipc_perm *ipcp = ipc_lock_check(&sem_ids(ns), id);

166 167 168
	if (IS_ERR(ipcp))
		return (struct sem_array *)ipcp;

N
Nadia Derbey 已提交
169
	return container_of(ipcp, struct sem_array, sem_perm);
170 171
}

172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
static inline void sem_lock_and_putref(struct sem_array *sma)
{
	ipc_lock_by_ptr(&sma->sem_perm);
	ipc_rcu_putref(sma);
}

static inline void sem_getref_and_unlock(struct sem_array *sma)
{
	ipc_rcu_getref(sma);
	ipc_unlock(&(sma)->sem_perm);
}

static inline void sem_putref(struct sem_array *sma)
{
	ipc_lock_by_ptr(&sma->sem_perm);
	ipc_rcu_putref(sma);
	ipc_unlock(&(sma)->sem_perm);
}

N
Nadia Derbey 已提交
191 192 193 194 195
static inline void sem_rmid(struct ipc_namespace *ns, struct sem_array *s)
{
	ipc_rmid(&sem_ids(ns), &s->sem_perm);
}

L
Linus Torvalds 已提交
196 197 198 199 200 201 202 203 204 205 206 207 208 209 210
/*
 * Lockless wakeup algorithm:
 * Without the check/retry algorithm a lockless wakeup is possible:
 * - queue.status is initialized to -EINTR before blocking.
 * - wakeup is performed by
 *	* unlinking the queue entry from sma->sem_pending
 *	* setting queue.status to IN_WAKEUP
 *	  This is the notification for the blocked thread that a
 *	  result value is imminent.
 *	* call wake_up_process
 *	* set queue.status to the final value.
 * - the previously blocked thread checks queue.status:
 *   	* if it's IN_WAKEUP, then it must wait until the value changes
 *   	* if it's not -EINTR, then the operation was completed by
 *   	  update_queue. semtimedop can return queue.status without
I
Ingo Molnar 已提交
211
 *   	  performing any operation on the sem array.
L
Linus Torvalds 已提交
212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229
 *   	* otherwise it must acquire the spinlock and check what's up.
 *
 * The two-stage algorithm is necessary to protect against the following
 * races:
 * - if queue.status is set after wake_up_process, then the woken up idle
 *   thread could race forward and try (and fail) to acquire sma->lock
 *   before update_queue had a chance to set queue.status
 * - if queue.status is written before wake_up_process and if the
 *   blocked process is woken up by a signal between writing
 *   queue.status and the wake_up_process, then the woken up
 *   process could return from semtimedop and die by calling
 *   sys_exit before wake_up_process is called. Then wake_up_process
 *   will oops, because the task structure is already invalid.
 *   (yes, this happened on s390 with sysv msg).
 *
 */
#define IN_WAKEUP	1

N
Nadia Derbey 已提交
230 231 232 233 234
/**
 * newary - Create a new semaphore set
 * @ns: namespace
 * @params: ptr to the structure that contains key, semflg and nsems
 *
N
Nadia Derbey 已提交
235
 * Called with sem_ids.rw_mutex held (as a writer)
N
Nadia Derbey 已提交
236 237
 */

N
Nadia Derbey 已提交
238
static int newary(struct ipc_namespace *ns, struct ipc_params *params)
L
Linus Torvalds 已提交
239 240 241 242 243
{
	int id;
	int retval;
	struct sem_array *sma;
	int size;
N
Nadia Derbey 已提交
244 245 246
	key_t key = params->key;
	int nsems = params->u.nsems;
	int semflg = params->flg;
247
	int i;
L
Linus Torvalds 已提交
248 249 250

	if (!nsems)
		return -EINVAL;
K
Kirill Korotaev 已提交
251
	if (ns->used_sems + nsems > ns->sc_semmns)
L
Linus Torvalds 已提交
252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270
		return -ENOSPC;

	size = sizeof (*sma) + nsems * sizeof (struct sem);
	sma = ipc_rcu_alloc(size);
	if (!sma) {
		return -ENOMEM;
	}
	memset (sma, 0, size);

	sma->sem_perm.mode = (semflg & S_IRWXUGO);
	sma->sem_perm.key = key;

	sma->sem_perm.security = NULL;
	retval = security_sem_alloc(sma);
	if (retval) {
		ipc_rcu_putref(sma);
		return retval;
	}

K
Kirill Korotaev 已提交
271
	id = ipc_addid(&sem_ids(ns), &sma->sem_perm, ns->sc_semmni);
272
	if (id < 0) {
L
Linus Torvalds 已提交
273 274
		security_sem_free(sma);
		ipc_rcu_putref(sma);
275
		return id;
L
Linus Torvalds 已提交
276
	}
K
Kirill Korotaev 已提交
277
	ns->used_sems += nsems;
L
Linus Torvalds 已提交
278 279

	sma->sem_base = (struct sem *) &sma[1];
280 281 282 283 284

	for (i = 0; i < nsems; i++)
		INIT_LIST_HEAD(&sma->sem_base[i].sem_pending);

	sma->complex_count = 0;
285
	INIT_LIST_HEAD(&sma->sem_pending);
286
	INIT_LIST_HEAD(&sma->list_id);
L
Linus Torvalds 已提交
287 288 289 290
	sma->sem_nsems = nsems;
	sma->sem_ctime = get_seconds();
	sem_unlock(sma);

N
Nadia Derbey 已提交
291
	return sma->sem_perm.id;
L
Linus Torvalds 已提交
292 293
}

N
Nadia Derbey 已提交
294

N
Nadia Derbey 已提交
295
/*
N
Nadia Derbey 已提交
296
 * Called with sem_ids.rw_mutex and ipcp locked.
N
Nadia Derbey 已提交
297
 */
N
Nadia Derbey 已提交
298
static inline int sem_security(struct kern_ipc_perm *ipcp, int semflg)
N
Nadia Derbey 已提交
299
{
N
Nadia Derbey 已提交
300 301 302 303
	struct sem_array *sma;

	sma = container_of(ipcp, struct sem_array, sem_perm);
	return security_sem_associate(sma, semflg);
N
Nadia Derbey 已提交
304 305
}

N
Nadia Derbey 已提交
306
/*
N
Nadia Derbey 已提交
307
 * Called with sem_ids.rw_mutex and ipcp locked.
N
Nadia Derbey 已提交
308
 */
N
Nadia Derbey 已提交
309 310
static inline int sem_more_checks(struct kern_ipc_perm *ipcp,
				struct ipc_params *params)
N
Nadia Derbey 已提交
311
{
N
Nadia Derbey 已提交
312 313 314 315
	struct sem_array *sma;

	sma = container_of(ipcp, struct sem_array, sem_perm);
	if (params->u.nsems > sma->sem_nsems)
N
Nadia Derbey 已提交
316 317 318 319 320
		return -EINVAL;

	return 0;
}

321
SYSCALL_DEFINE3(semget, key_t, key, int, nsems, int, semflg)
L
Linus Torvalds 已提交
322
{
K
Kirill Korotaev 已提交
323
	struct ipc_namespace *ns;
N
Nadia Derbey 已提交
324 325
	struct ipc_ops sem_ops;
	struct ipc_params sem_params;
K
Kirill Korotaev 已提交
326 327

	ns = current->nsproxy->ipc_ns;
L
Linus Torvalds 已提交
328

K
Kirill Korotaev 已提交
329
	if (nsems < 0 || nsems > ns->sc_semmsl)
L
Linus Torvalds 已提交
330
		return -EINVAL;
N
Nadia Derbey 已提交
331

N
Nadia Derbey 已提交
332 333 334 335 336 337 338
	sem_ops.getnew = newary;
	sem_ops.associate = sem_security;
	sem_ops.more_checks = sem_more_checks;

	sem_params.key = key;
	sem_params.flg = semflg;
	sem_params.u.nsems = nsems;
L
Linus Torvalds 已提交
339

N
Nadia Derbey 已提交
340
	return ipcget(ns, &sem_ids(ns), &sem_ops, &sem_params);
L
Linus Torvalds 已提交
341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408
}

/*
 * Determine whether a sequence of semaphore operations would succeed
 * all at once. Return 0 if yes, 1 if need to sleep, else return error code.
 */

static int try_atomic_semop (struct sem_array * sma, struct sembuf * sops,
			     int nsops, struct sem_undo *un, int pid)
{
	int result, sem_op;
	struct sembuf *sop;
	struct sem * curr;

	for (sop = sops; sop < sops + nsops; sop++) {
		curr = sma->sem_base + sop->sem_num;
		sem_op = sop->sem_op;
		result = curr->semval;
  
		if (!sem_op && result)
			goto would_block;

		result += sem_op;
		if (result < 0)
			goto would_block;
		if (result > SEMVMX)
			goto out_of_range;
		if (sop->sem_flg & SEM_UNDO) {
			int undo = un->semadj[sop->sem_num] - sem_op;
			/*
	 		 *	Exceeding the undo range is an error.
			 */
			if (undo < (-SEMAEM - 1) || undo > SEMAEM)
				goto out_of_range;
		}
		curr->semval = result;
	}

	sop--;
	while (sop >= sops) {
		sma->sem_base[sop->sem_num].sempid = pid;
		if (sop->sem_flg & SEM_UNDO)
			un->semadj[sop->sem_num] -= sop->sem_op;
		sop--;
	}
	
	return 0;

out_of_range:
	result = -ERANGE;
	goto undo;

would_block:
	if (sop->sem_flg & IPC_NOWAIT)
		result = -EAGAIN;
	else
		result = 1;

undo:
	sop--;
	while (sop >= sops) {
		sma->sem_base[sop->sem_num].semval -= sop->sem_op;
		sop--;
	}

	return result;
}

409 410 411 412 413
/** wake_up_sem_queue_prepare(q, error): Prepare wake-up
 * @q: queue entry that must be signaled
 * @error: Error value for the signal
 *
 * Prepare the wake-up of the queue entry q.
N
Nick Piggin 已提交
414
 */
415 416
static void wake_up_sem_queue_prepare(struct list_head *pt,
				struct sem_queue *q, int error)
N
Nick Piggin 已提交
417
{
418 419 420 421 422 423 424
	if (list_empty(pt)) {
		/*
		 * Hold preempt off so that we don't get preempted and have the
		 * wakee busy-wait until we're scheduled back on.
		 */
		preempt_disable();
	}
N
Nick Piggin 已提交
425
	q->status = IN_WAKEUP;
426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453
	q->pid = error;

	list_add_tail(&q->simple_list, pt);
}

/**
 * wake_up_sem_queue_do(pt) - do the actual wake-up
 * @pt: list of tasks to be woken up
 *
 * Do the actual wake-up.
 * The function is called without any locks held, thus the semaphore array
 * could be destroyed already and the tasks can disappear as soon as the
 * status is set to the actual return code.
 */
static void wake_up_sem_queue_do(struct list_head *pt)
{
	struct sem_queue *q, *t;
	int did_something;

	did_something = !list_empty(pt);
	list_for_each_entry_safe(q, t, pt, simple_list) {
		wake_up_process(q->sleeper);
		/* q can disappear immediately after writing q->status. */
		smp_wmb();
		q->status = q->pid;
	}
	if (did_something)
		preempt_enable();
N
Nick Piggin 已提交
454 455
}

456 457 458 459 460 461 462 463 464
static void unlink_queue(struct sem_array *sma, struct sem_queue *q)
{
	list_del(&q->list);
	if (q->nsops == 1)
		list_del(&q->simple_list);
	else
		sma->complex_count--;
}

465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527
/** check_restart(sma, q)
 * @sma: semaphore array
 * @q: the operation that just completed
 *
 * update_queue 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.
 */
static int check_restart(struct sem_array *sma, struct sem_queue *q)
{
	struct sem *curr;
	struct sem_queue *h;

	/* if the operation didn't modify the array, then no restart */
	if (q->alter == 0)
		return 0;

	/* pending complex operations are too difficult to analyse */
	if (sma->complex_count)
		return 1;

	/* we were a sleeping complex operation. Too difficult */
	if (q->nsops > 1)
		return 1;

	curr = sma->sem_base + q->sops[0].sem_num;

	/* No-one waits on this queue */
	if (list_empty(&curr->sem_pending))
		return 0;

	/* the new semaphore value */
	if (curr->semval) {
		/* It is impossible that someone waits for the new value:
		 * - q is a previously sleeping simple operation that
		 *   altered the array. It must be a decrement, because
		 *   simple increments never sleep.
		 * - The value is not 0, thus wait-for-zero won't proceed.
		 * - If there are older (higher priority) decrements
		 *   in the queue, then they have observed the original
		 *   semval value and couldn't proceed. The operation
		 *   decremented to value - thus they won't proceed either.
		 */
		BUG_ON(q->sops[0].sem_op >= 0);
		return 0;
	}
	/*
	 * semval is 0. Check if there are wait-for-zero semops.
	 * They must be the first entries in the per-semaphore simple queue
	 */
	h = list_first_entry(&curr->sem_pending, struct sem_queue, simple_list);
	BUG_ON(h->nsops != 1);
	BUG_ON(h->sops[0].sem_num != q->sops[0].sem_num);

	/* Yes, there is a wait-for-zero semop. Restart */
	if (h->sops[0].sem_op == 0)
		return 1;

	/* Again - no-one is waiting for the new value. */
	return 0;
}

528 529 530 531 532

/**
 * update_queue(sma, semnum): Look for tasks that can be completed.
 * @sma: semaphore array.
 * @semnum: semaphore that was modified.
533
 * @pt: list head for the tasks that must be woken up.
534 535 536 537
 *
 * update_queue must be called after a semaphore in a semaphore array
 * was modified. If multiple semaphore were modified, then @semnum
 * must be set to -1.
538 539 540
 * The tasks that must be woken up are added to @pt. The return code
 * is stored in q->pid.
 * The function return 1 if at least one semop was completed successfully.
L
Linus Torvalds 已提交
541
 */
542
static int update_queue(struct sem_array *sma, int semnum, struct list_head *pt)
L
Linus Torvalds 已提交
543
{
544 545 546 547
	struct sem_queue *q;
	struct list_head *walk;
	struct list_head *pending_list;
	int offset;
548
	int semop_completed = 0;
549 550 551 552 553 554 555 556 557 558 559 560 561 562 563

	/* if there are complex operations around, then knowing the semaphore
	 * that was modified doesn't help us. Assume that multiple semaphores
	 * were modified.
	 */
	if (sma->complex_count)
		semnum = -1;

	if (semnum == -1) {
		pending_list = &sma->sem_pending;
		offset = offsetof(struct sem_queue, list);
	} else {
		pending_list = &sma->sem_base[semnum].sem_pending;
		offset = offsetof(struct sem_queue, simple_list);
	}
N
Nick Piggin 已提交
564 565

again:
566 567
	walk = pending_list->next;
	while (walk != pending_list) {
568
		int error, restart;
569 570 571

		q = (struct sem_queue *)((char *)walk - offset);
		walk = walk->next;
L
Linus Torvalds 已提交
572

573 574 575 576 577 578 579 580 581 582 583
		/* If we are scanning the single sop, per-semaphore list of
		 * one semaphore and that semaphore is 0, then it is not
		 * necessary to scan the "alter" entries: simple increments
		 * that affect only one entry succeed immediately and cannot
		 * be in the  per semaphore pending queue, and decrements
		 * cannot be successful if the value is already 0.
		 */
		if (semnum != -1 && sma->sem_base[semnum].semval == 0 &&
				q->alter)
			break;

L
Linus Torvalds 已提交
584 585 586 587
		error = try_atomic_semop(sma, q->sops, q->nsops,
					 q->undo, q->pid);

		/* Does q->sleeper still need to sleep? */
N
Nick Piggin 已提交
588 589 590
		if (error > 0)
			continue;

591
		unlink_queue(sma, q);
N
Nick Piggin 已提交
592

593
		if (error) {
594
			restart = 0;
595 596
		} else {
			semop_completed = 1;
597
			restart = check_restart(sma, q);
598
		}
599

600
		wake_up_sem_queue_prepare(pt, q, error);
601
		if (restart)
N
Nick Piggin 已提交
602
			goto again;
L
Linus Torvalds 已提交
603
	}
604
	return semop_completed;
L
Linus Torvalds 已提交
605 606
}

607 608
/**
 * do_smart_update(sma, sops, nsops, otime, pt) - optimized update_queue
609 610 611
 * @sma: semaphore array
 * @sops: operations that were performed
 * @nsops: number of operations
612 613
 * @otime: force setting otime
 * @pt: list head of the tasks that must be woken up.
614 615 616
 *
 * do_smart_update() does the required called to update_queue, based on the
 * actual changes that were performed on the semaphore array.
617 618 619
 * Note that the function does not do the actual wake-up: the caller is
 * responsible for calling wake_up_sem_queue_do(@pt).
 * It is safe to perform this call after dropping all locks.
620
 */
621 622
static void do_smart_update(struct sem_array *sma, struct sembuf *sops, int nsops,
			int otime, struct list_head *pt)
623 624 625 626
{
	int i;

	if (sma->complex_count || sops == NULL) {
627 628 629
		if (update_queue(sma, -1, pt))
			otime = 1;
		goto done;
630 631 632 633 634 635
	}

	for (i = 0; i < nsops; i++) {
		if (sops[i].sem_op > 0 ||
			(sops[i].sem_op < 0 &&
				sma->sem_base[sops[i].sem_num].semval == 0))
636 637
			if (update_queue(sma, sops[i].sem_num, pt))
				otime = 1;
638
	}
639 640 641
done:
	if (otime)
		sma->sem_otime = get_seconds();
642 643 644
}


L
Linus Torvalds 已提交
645 646 647 648 649 650 651 652 653 654 655 656 657 658 659
/* The following counts are associated to each semaphore:
 *   semncnt        number of tasks waiting on semval being nonzero
 *   semzcnt        number of tasks waiting on semval being zero
 * This model assumes that a task waits on exactly one semaphore.
 * Since semaphore operations are to be performed atomically, tasks actually
 * wait on a whole sequence of semaphores simultaneously.
 * The counts we return here are a rough approximation, but still
 * warrant that semncnt+semzcnt>0 if the task is on the pending queue.
 */
static int count_semncnt (struct sem_array * sma, ushort semnum)
{
	int semncnt;
	struct sem_queue * q;

	semncnt = 0;
660
	list_for_each_entry(q, &sma->sem_pending, list) {
L
Linus Torvalds 已提交
661 662 663 664 665 666 667 668 669 670 671
		struct sembuf * sops = q->sops;
		int nsops = q->nsops;
		int i;
		for (i = 0; i < nsops; i++)
			if (sops[i].sem_num == semnum
			    && (sops[i].sem_op < 0)
			    && !(sops[i].sem_flg & IPC_NOWAIT))
				semncnt++;
	}
	return semncnt;
}
672

L
Linus Torvalds 已提交
673 674 675 676 677 678
static int count_semzcnt (struct sem_array * sma, ushort semnum)
{
	int semzcnt;
	struct sem_queue * q;

	semzcnt = 0;
679
	list_for_each_entry(q, &sma->sem_pending, list) {
L
Linus Torvalds 已提交
680 681 682 683 684 685 686 687 688 689 690 691
		struct sembuf * sops = q->sops;
		int nsops = q->nsops;
		int i;
		for (i = 0; i < nsops; i++)
			if (sops[i].sem_num == semnum
			    && (sops[i].sem_op == 0)
			    && !(sops[i].sem_flg & IPC_NOWAIT))
				semzcnt++;
	}
	return semzcnt;
}

N
Nadia Derbey 已提交
692 693 694
/* Free a semaphore set. freeary() is called with sem_ids.rw_mutex locked
 * as a writer and the spinlock for this semaphore set hold. sem_ids.rw_mutex
 * remains locked on exit.
L
Linus Torvalds 已提交
695
 */
696
static void freeary(struct ipc_namespace *ns, struct kern_ipc_perm *ipcp)
L
Linus Torvalds 已提交
697
{
698 699
	struct sem_undo *un, *tu;
	struct sem_queue *q, *tq;
700
	struct sem_array *sma = container_of(ipcp, struct sem_array, sem_perm);
701
	struct list_head tasks;
L
Linus Torvalds 已提交
702

703
	/* Free the existing undo structures for this semaphore set.  */
704
	assert_spin_locked(&sma->sem_perm.lock);
705 706 707
	list_for_each_entry_safe(un, tu, &sma->list_id, list_id) {
		list_del(&un->list_id);
		spin_lock(&un->ulp->lock);
L
Linus Torvalds 已提交
708
		un->semid = -1;
709 710
		list_del_rcu(&un->list_proc);
		spin_unlock(&un->ulp->lock);
711
		kfree_rcu(un, rcu);
712
	}
L
Linus Torvalds 已提交
713 714

	/* Wake up all pending processes and let them fail with EIDRM. */
715
	INIT_LIST_HEAD(&tasks);
716
	list_for_each_entry_safe(q, tq, &sma->sem_pending, list) {
717
		unlink_queue(sma, q);
718
		wake_up_sem_queue_prepare(&tasks, q, -EIDRM);
L
Linus Torvalds 已提交
719 720
	}

N
Nadia Derbey 已提交
721 722
	/* Remove the semaphore set from the IDR */
	sem_rmid(ns, sma);
L
Linus Torvalds 已提交
723 724
	sem_unlock(sma);

725
	wake_up_sem_queue_do(&tasks);
K
Kirill Korotaev 已提交
726
	ns->used_sems -= sma->sem_nsems;
L
Linus Torvalds 已提交
727 728 729 730 731 732 733 734 735 736 737 738 739
	security_sem_free(sma);
	ipc_rcu_putref(sma);
}

static unsigned long copy_semid_to_user(void __user *buf, struct semid64_ds *in, int version)
{
	switch(version) {
	case IPC_64:
		return copy_to_user(buf, in, sizeof(*in));
	case IPC_OLD:
	    {
		struct semid_ds out;

740 741
		memset(&out, 0, sizeof(out));

L
Linus Torvalds 已提交
742 743 744 745 746 747 748 749 750 751 752 753 754
		ipc64_perm_to_ipc_perm(&in->sem_perm, &out.sem_perm);

		out.sem_otime	= in->sem_otime;
		out.sem_ctime	= in->sem_ctime;
		out.sem_nsems	= in->sem_nsems;

		return copy_to_user(buf, &out, sizeof(out));
	    }
	default:
		return -EINVAL;
	}
}

755 756
static int semctl_nolock(struct ipc_namespace *ns, int semid,
			 int cmd, int version, union semun arg)
L
Linus Torvalds 已提交
757
{
758
	int err;
L
Linus Torvalds 已提交
759 760 761 762 763 764 765 766 767 768 769 770 771 772
	struct sem_array *sma;

	switch(cmd) {
	case IPC_INFO:
	case SEM_INFO:
	{
		struct seminfo seminfo;
		int max_id;

		err = security_sem_semctl(NULL, cmd);
		if (err)
			return err;
		
		memset(&seminfo,0,sizeof(seminfo));
K
Kirill Korotaev 已提交
773 774 775 776
		seminfo.semmni = ns->sc_semmni;
		seminfo.semmns = ns->sc_semmns;
		seminfo.semmsl = ns->sc_semmsl;
		seminfo.semopm = ns->sc_semopm;
L
Linus Torvalds 已提交
777 778 779 780
		seminfo.semvmx = SEMVMX;
		seminfo.semmnu = SEMMNU;
		seminfo.semmap = SEMMAP;
		seminfo.semume = SEMUME;
N
Nadia Derbey 已提交
781
		down_read(&sem_ids(ns).rw_mutex);
L
Linus Torvalds 已提交
782
		if (cmd == SEM_INFO) {
K
Kirill Korotaev 已提交
783 784
			seminfo.semusz = sem_ids(ns).in_use;
			seminfo.semaem = ns->used_sems;
L
Linus Torvalds 已提交
785 786 787 788
		} else {
			seminfo.semusz = SEMUSZ;
			seminfo.semaem = SEMAEM;
		}
N
Nadia Derbey 已提交
789
		max_id = ipc_get_maxid(&sem_ids(ns));
N
Nadia Derbey 已提交
790
		up_read(&sem_ids(ns).rw_mutex);
L
Linus Torvalds 已提交
791 792 793 794
		if (copy_to_user (arg.__buf, &seminfo, sizeof(struct seminfo))) 
			return -EFAULT;
		return (max_id < 0) ? 0: max_id;
	}
795
	case IPC_STAT:
L
Linus Torvalds 已提交
796 797 798 799 800
	case SEM_STAT:
	{
		struct semid64_ds tbuf;
		int id;

801 802 803 804 805 806 807 808 809 810 811
		if (cmd == SEM_STAT) {
			sma = sem_lock(ns, semid);
			if (IS_ERR(sma))
				return PTR_ERR(sma);
			id = sma->sem_perm.id;
		} else {
			sma = sem_lock_check(ns, semid);
			if (IS_ERR(sma))
				return PTR_ERR(sma);
			id = 0;
		}
L
Linus Torvalds 已提交
812 813

		err = -EACCES;
814
		if (ipcperms(ns, &sma->sem_perm, S_IRUGO))
L
Linus Torvalds 已提交
815 816 817 818 819 820
			goto out_unlock;

		err = security_sem_semctl(sma, cmd);
		if (err)
			goto out_unlock;

821 822
		memset(&tbuf, 0, sizeof(tbuf));

L
Linus Torvalds 已提交
823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839
		kernel_to_ipc64_perm(&sma->sem_perm, &tbuf.sem_perm);
		tbuf.sem_otime  = sma->sem_otime;
		tbuf.sem_ctime  = sma->sem_ctime;
		tbuf.sem_nsems  = sma->sem_nsems;
		sem_unlock(sma);
		if (copy_semid_to_user (arg.buf, &tbuf, version))
			return -EFAULT;
		return id;
	}
	default:
		return -EINVAL;
	}
out_unlock:
	sem_unlock(sma);
	return err;
}

K
Kirill Korotaev 已提交
840 841
static int semctl_main(struct ipc_namespace *ns, int semid, int semnum,
		int cmd, int version, union semun arg)
L
Linus Torvalds 已提交
842 843 844 845 846 847 848
{
	struct sem_array *sma;
	struct sem* curr;
	int err;
	ushort fast_sem_io[SEMMSL_FAST];
	ushort* sem_io = fast_sem_io;
	int nsems;
849
	struct list_head tasks;
L
Linus Torvalds 已提交
850

851 852 853
	sma = sem_lock_check(ns, semid);
	if (IS_ERR(sma))
		return PTR_ERR(sma);
L
Linus Torvalds 已提交
854

855
	INIT_LIST_HEAD(&tasks);
L
Linus Torvalds 已提交
856 857 858
	nsems = sma->sem_nsems;

	err = -EACCES;
859 860
	if (ipcperms(ns, &sma->sem_perm,
			(cmd == SETVAL || cmd == SETALL) ? S_IWUGO : S_IRUGO))
L
Linus Torvalds 已提交
861 862 863 864 865 866 867 868 869 870 871 872 873 874
		goto out_unlock;

	err = security_sem_semctl(sma, cmd);
	if (err)
		goto out_unlock;

	err = -EACCES;
	switch (cmd) {
	case GETALL:
	{
		ushort __user *array = arg.array;
		int i;

		if(nsems > SEMMSL_FAST) {
875
			sem_getref_and_unlock(sma);
L
Linus Torvalds 已提交
876 877 878

			sem_io = ipc_alloc(sizeof(ushort)*nsems);
			if(sem_io == NULL) {
879
				sem_putref(sma);
L
Linus Torvalds 已提交
880 881 882
				return -ENOMEM;
			}

883
			sem_lock_and_putref(sma);
L
Linus Torvalds 已提交
884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903
			if (sma->sem_perm.deleted) {
				sem_unlock(sma);
				err = -EIDRM;
				goto out_free;
			}
		}

		for (i = 0; i < sma->sem_nsems; i++)
			sem_io[i] = sma->sem_base[i].semval;
		sem_unlock(sma);
		err = 0;
		if(copy_to_user(array, sem_io, nsems*sizeof(ushort)))
			err = -EFAULT;
		goto out_free;
	}
	case SETALL:
	{
		int i;
		struct sem_undo *un;

904
		sem_getref_and_unlock(sma);
L
Linus Torvalds 已提交
905 906 907 908

		if(nsems > SEMMSL_FAST) {
			sem_io = ipc_alloc(sizeof(ushort)*nsems);
			if(sem_io == NULL) {
909
				sem_putref(sma);
L
Linus Torvalds 已提交
910 911 912 913 914
				return -ENOMEM;
			}
		}

		if (copy_from_user (sem_io, arg.array, nsems*sizeof(ushort))) {
915
			sem_putref(sma);
L
Linus Torvalds 已提交
916 917 918 919 920 921
			err = -EFAULT;
			goto out_free;
		}

		for (i = 0; i < nsems; i++) {
			if (sem_io[i] > SEMVMX) {
922
				sem_putref(sma);
L
Linus Torvalds 已提交
923 924 925 926
				err = -ERANGE;
				goto out_free;
			}
		}
927
		sem_lock_and_putref(sma);
L
Linus Torvalds 已提交
928 929 930 931 932 933 934 935
		if (sma->sem_perm.deleted) {
			sem_unlock(sma);
			err = -EIDRM;
			goto out_free;
		}

		for (i = 0; i < nsems; i++)
			sma->sem_base[i].semval = sem_io[i];
936 937 938

		assert_spin_locked(&sma->sem_perm.lock);
		list_for_each_entry(un, &sma->list_id, list_id) {
L
Linus Torvalds 已提交
939 940
			for (i = 0; i < nsems; i++)
				un->semadj[i] = 0;
941
		}
L
Linus Torvalds 已提交
942 943
		sma->sem_ctime = get_seconds();
		/* maybe some queued-up processes were waiting for this */
944
		do_smart_update(sma, NULL, 0, 0, &tasks);
L
Linus Torvalds 已提交
945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972
		err = 0;
		goto out_unlock;
	}
	/* GETVAL, GETPID, GETNCTN, GETZCNT, SETVAL: fall-through */
	}
	err = -EINVAL;
	if(semnum < 0 || semnum >= nsems)
		goto out_unlock;

	curr = &sma->sem_base[semnum];

	switch (cmd) {
	case GETVAL:
		err = curr->semval;
		goto out_unlock;
	case GETPID:
		err = curr->sempid;
		goto out_unlock;
	case GETNCNT:
		err = count_semncnt(sma,semnum);
		goto out_unlock;
	case GETZCNT:
		err = count_semzcnt(sma,semnum);
		goto out_unlock;
	case SETVAL:
	{
		int val = arg.val;
		struct sem_undo *un;
973

L
Linus Torvalds 已提交
974 975 976 977
		err = -ERANGE;
		if (val > SEMVMX || val < 0)
			goto out_unlock;

978 979
		assert_spin_locked(&sma->sem_perm.lock);
		list_for_each_entry(un, &sma->list_id, list_id)
L
Linus Torvalds 已提交
980
			un->semadj[semnum] = 0;
981

L
Linus Torvalds 已提交
982
		curr->semval = val;
983
		curr->sempid = task_tgid_vnr(current);
L
Linus Torvalds 已提交
984 985
		sma->sem_ctime = get_seconds();
		/* maybe some queued-up processes were waiting for this */
986
		do_smart_update(sma, NULL, 0, 0, &tasks);
L
Linus Torvalds 已提交
987 988 989 990 991 992
		err = 0;
		goto out_unlock;
	}
	}
out_unlock:
	sem_unlock(sma);
993 994
	wake_up_sem_queue_do(&tasks);

L
Linus Torvalds 已提交
995 996 997 998 999 1000
out_free:
	if(sem_io != fast_sem_io)
		ipc_free(sem_io, sizeof(ushort)*nsems);
	return err;
}

1001 1002
static inline unsigned long
copy_semid_from_user(struct semid64_ds *out, void __user *buf, int version)
L
Linus Torvalds 已提交
1003 1004 1005
{
	switch(version) {
	case IPC_64:
1006
		if (copy_from_user(out, buf, sizeof(*out)))
L
Linus Torvalds 已提交
1007 1008 1009 1010 1011 1012 1013 1014 1015
			return -EFAULT;
		return 0;
	case IPC_OLD:
	    {
		struct semid_ds tbuf_old;

		if(copy_from_user(&tbuf_old, buf, sizeof(tbuf_old)))
			return -EFAULT;

1016 1017 1018
		out->sem_perm.uid	= tbuf_old.sem_perm.uid;
		out->sem_perm.gid	= tbuf_old.sem_perm.gid;
		out->sem_perm.mode	= tbuf_old.sem_perm.mode;
L
Linus Torvalds 已提交
1019 1020 1021 1022 1023 1024 1025 1026

		return 0;
	    }
	default:
		return -EINVAL;
	}
}

1027 1028 1029 1030 1031
/*
 * This function handles some semctl commands which require the rw_mutex
 * to be held in write mode.
 * NOTE: no locks must be held, the rw_mutex is taken inside this function.
 */
1032 1033
static int semctl_down(struct ipc_namespace *ns, int semid,
		       int cmd, int version, union semun arg)
L
Linus Torvalds 已提交
1034 1035 1036
{
	struct sem_array *sma;
	int err;
1037
	struct semid64_ds semid64;
L
Linus Torvalds 已提交
1038 1039 1040
	struct kern_ipc_perm *ipcp;

	if(cmd == IPC_SET) {
1041
		if (copy_semid_from_user(&semid64, arg.buf, version))
L
Linus Torvalds 已提交
1042 1043
			return -EFAULT;
	}
S
Steve Grubb 已提交
1044

1045 1046
	ipcp = ipcctl_pre_down(ns, &sem_ids(ns), semid, cmd,
			       &semid64.sem_perm, 0);
1047 1048
	if (IS_ERR(ipcp))
		return PTR_ERR(ipcp);
S
Steve Grubb 已提交
1049

1050
	sma = container_of(ipcp, struct sem_array, sem_perm);
L
Linus Torvalds 已提交
1051 1052 1053 1054 1055 1056 1057

	err = security_sem_semctl(sma, cmd);
	if (err)
		goto out_unlock;

	switch(cmd){
	case IPC_RMID:
1058
		freeary(ns, ipcp);
1059
		goto out_up;
L
Linus Torvalds 已提交
1060
	case IPC_SET:
1061
		ipc_update_perm(&semid64.sem_perm, ipcp);
L
Linus Torvalds 已提交
1062 1063 1064 1065 1066 1067 1068 1069
		sma->sem_ctime = get_seconds();
		break;
	default:
		err = -EINVAL;
	}

out_unlock:
	sem_unlock(sma);
1070 1071
out_up:
	up_write(&sem_ids(ns).rw_mutex);
L
Linus Torvalds 已提交
1072 1073 1074
	return err;
}

1075
SYSCALL_DEFINE(semctl)(int semid, int semnum, int cmd, union semun arg)
L
Linus Torvalds 已提交
1076 1077 1078
{
	int err = -EINVAL;
	int version;
K
Kirill Korotaev 已提交
1079
	struct ipc_namespace *ns;
L
Linus Torvalds 已提交
1080 1081 1082 1083 1084

	if (semid < 0)
		return -EINVAL;

	version = ipc_parse_version(&cmd);
K
Kirill Korotaev 已提交
1085
	ns = current->nsproxy->ipc_ns;
L
Linus Torvalds 已提交
1086 1087 1088 1089

	switch(cmd) {
	case IPC_INFO:
	case SEM_INFO:
1090
	case IPC_STAT:
L
Linus Torvalds 已提交
1091
	case SEM_STAT:
1092
		err = semctl_nolock(ns, semid, cmd, version, arg);
L
Linus Torvalds 已提交
1093 1094 1095 1096 1097 1098 1099 1100
		return err;
	case GETALL:
	case GETVAL:
	case GETPID:
	case GETNCNT:
	case GETZCNT:
	case SETVAL:
	case SETALL:
K
Kirill Korotaev 已提交
1101
		err = semctl_main(ns,semid,semnum,cmd,version,arg);
L
Linus Torvalds 已提交
1102 1103 1104
		return err;
	case IPC_RMID:
	case IPC_SET:
1105
		err = semctl_down(ns, semid, cmd, version, arg);
L
Linus Torvalds 已提交
1106 1107 1108 1109 1110
		return err;
	default:
		return -EINVAL;
	}
}
1111 1112 1113 1114 1115 1116 1117
#ifdef CONFIG_HAVE_SYSCALL_WRAPPERS
asmlinkage long SyS_semctl(int semid, int semnum, int cmd, union semun arg)
{
	return SYSC_semctl((int) semid, (int) semnum, (int) cmd, arg);
}
SYSCALL_ALIAS(sys_semctl, SyS_semctl);
#endif
L
Linus Torvalds 已提交
1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135

/* If the task doesn't already have a undo_list, then allocate one
 * here.  We guarantee there is only one thread using this undo list,
 * and current is THE ONE
 *
 * If this allocation and assignment succeeds, but later
 * portions of this code fail, there is no need to free the sem_undo_list.
 * Just let it stay associated with the task, and it'll be freed later
 * at exit time.
 *
 * This can block, so callers must hold no locks.
 */
static inline int get_undo_list(struct sem_undo_list **undo_listp)
{
	struct sem_undo_list *undo_list;

	undo_list = current->sysvsem.undo_list;
	if (!undo_list) {
1136
		undo_list = kzalloc(sizeof(*undo_list), GFP_KERNEL);
L
Linus Torvalds 已提交
1137 1138
		if (undo_list == NULL)
			return -ENOMEM;
I
Ingo Molnar 已提交
1139
		spin_lock_init(&undo_list->lock);
L
Linus Torvalds 已提交
1140
		atomic_set(&undo_list->refcnt, 1);
1141 1142
		INIT_LIST_HEAD(&undo_list->list_proc);

L
Linus Torvalds 已提交
1143 1144 1145 1146 1147 1148
		current->sysvsem.undo_list = undo_list;
	}
	*undo_listp = undo_list;
	return 0;
}

1149
static struct sem_undo *__lookup_undo(struct sem_undo_list *ulp, int semid)
L
Linus Torvalds 已提交
1150
{
1151
	struct sem_undo *un;
1152

1153 1154 1155
	list_for_each_entry_rcu(un, &ulp->list_proc, list_proc) {
		if (un->semid == semid)
			return un;
L
Linus Torvalds 已提交
1156
	}
1157
	return NULL;
L
Linus Torvalds 已提交
1158 1159
}

1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173
static struct sem_undo *lookup_undo(struct sem_undo_list *ulp, int semid)
{
	struct sem_undo *un;

  	assert_spin_locked(&ulp->lock);

	un = __lookup_undo(ulp, semid);
	if (un) {
		list_del_rcu(&un->list_proc);
		list_add_rcu(&un->list_proc, &ulp->list_proc);
	}
	return un;
}

1174 1175 1176 1177 1178 1179 1180 1181
/**
 * find_alloc_undo - Lookup (and if not present create) undo array
 * @ns: namespace
 * @semid: semaphore array id
 *
 * The function looks up (and if not present creates) the undo structure.
 * The size of the undo structure depends on the size of the semaphore
 * array, thus the alloc path is not that straightforward.
1182 1183
 * Lifetime-rules: sem_undo is rcu-protected, on success, the function
 * performs a rcu_read_lock().
1184 1185
 */
static struct sem_undo *find_alloc_undo(struct ipc_namespace *ns, int semid)
L
Linus Torvalds 已提交
1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196
{
	struct sem_array *sma;
	struct sem_undo_list *ulp;
	struct sem_undo *un, *new;
	int nsems;
	int error;

	error = get_undo_list(&ulp);
	if (error)
		return ERR_PTR(error);

1197
	rcu_read_lock();
1198
	spin_lock(&ulp->lock);
L
Linus Torvalds 已提交
1199
	un = lookup_undo(ulp, semid);
1200
	spin_unlock(&ulp->lock);
L
Linus Torvalds 已提交
1201 1202
	if (likely(un!=NULL))
		goto out;
1203
	rcu_read_unlock();
L
Linus Torvalds 已提交
1204 1205

	/* no undo structure around - allocate one. */
1206
	/* step 1: figure out the size of the semaphore array */
1207 1208
	sma = sem_lock_check(ns, semid);
	if (IS_ERR(sma))
J
Julia Lawall 已提交
1209
		return ERR_CAST(sma);
1210

L
Linus Torvalds 已提交
1211
	nsems = sma->sem_nsems;
1212
	sem_getref_and_unlock(sma);
L
Linus Torvalds 已提交
1213

1214
	/* step 2: allocate new undo structure */
1215
	new = kzalloc(sizeof(struct sem_undo) + sizeof(short)*nsems, GFP_KERNEL);
L
Linus Torvalds 已提交
1216
	if (!new) {
1217
		sem_putref(sma);
L
Linus Torvalds 已提交
1218 1219 1220
		return ERR_PTR(-ENOMEM);
	}

1221
	/* step 3: Acquire the lock on semaphore array */
1222
	sem_lock_and_putref(sma);
L
Linus Torvalds 已提交
1223 1224 1225 1226 1227 1228
	if (sma->sem_perm.deleted) {
		sem_unlock(sma);
		kfree(new);
		un = ERR_PTR(-EIDRM);
		goto out;
	}
1229 1230 1231 1232 1233 1234 1235 1236 1237 1238
	spin_lock(&ulp->lock);

	/*
	 * step 4: check for races: did someone else allocate the undo struct?
	 */
	un = lookup_undo(ulp, semid);
	if (un) {
		kfree(new);
		goto success;
	}
1239 1240
	/* step 5: initialize & link new undo structure */
	new->semadj = (short *) &new[1];
1241
	new->ulp = ulp;
1242 1243
	new->semid = semid;
	assert_spin_locked(&ulp->lock);
1244
	list_add_rcu(&new->list_proc, &ulp->list_proc);
1245 1246
	assert_spin_locked(&sma->sem_perm.lock);
	list_add(&new->list_id, &sma->list_id);
1247
	un = new;
1248

1249
success:
1250
	spin_unlock(&ulp->lock);
1251 1252
	rcu_read_lock();
	sem_unlock(sma);
L
Linus Torvalds 已提交
1253 1254 1255 1256
out:
	return un;
}

1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283

/**
 * get_queue_result - Retrieve the result code from sem_queue
 * @q: Pointer to queue structure
 *
 * Retrieve the return code from the pending queue. If IN_WAKEUP is found in
 * q->status, then we must loop until the value is replaced with the final
 * value: This may happen if a task is woken up by an unrelated event (e.g.
 * signal) and in parallel the task is woken up by another task because it got
 * the requested semaphores.
 *
 * The function can be called with or without holding the semaphore spinlock.
 */
static int get_queue_result(struct sem_queue *q)
{
	int error;

	error = q->status;
	while (unlikely(error == IN_WAKEUP)) {
		cpu_relax();
		error = q->status;
	}

	return error;
}


1284 1285
SYSCALL_DEFINE4(semtimedop, int, semid, struct sembuf __user *, tsops,
		unsigned, nsops, const struct timespec __user *, timeout)
L
Linus Torvalds 已提交
1286 1287 1288 1289 1290 1291
{
	int error = -EINVAL;
	struct sem_array *sma;
	struct sembuf fast_sops[SEMOPM_FAST];
	struct sembuf* sops = fast_sops, *sop;
	struct sem_undo *un;
1292
	int undos = 0, alter = 0, max;
L
Linus Torvalds 已提交
1293 1294
	struct sem_queue queue;
	unsigned long jiffies_left = 0;
K
Kirill Korotaev 已提交
1295
	struct ipc_namespace *ns;
1296
	struct list_head tasks;
K
Kirill Korotaev 已提交
1297 1298

	ns = current->nsproxy->ipc_ns;
L
Linus Torvalds 已提交
1299 1300 1301

	if (nsops < 1 || semid < 0)
		return -EINVAL;
K
Kirill Korotaev 已提交
1302
	if (nsops > ns->sc_semopm)
L
Linus Torvalds 已提交
1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330
		return -E2BIG;
	if(nsops > SEMOPM_FAST) {
		sops = kmalloc(sizeof(*sops)*nsops,GFP_KERNEL);
		if(sops==NULL)
			return -ENOMEM;
	}
	if (copy_from_user (sops, tsops, nsops * sizeof(*tsops))) {
		error=-EFAULT;
		goto out_free;
	}
	if (timeout) {
		struct timespec _timeout;
		if (copy_from_user(&_timeout, timeout, sizeof(*timeout))) {
			error = -EFAULT;
			goto out_free;
		}
		if (_timeout.tv_sec < 0 || _timeout.tv_nsec < 0 ||
			_timeout.tv_nsec >= 1000000000L) {
			error = -EINVAL;
			goto out_free;
		}
		jiffies_left = timespec_to_jiffies(&_timeout);
	}
	max = 0;
	for (sop = sops; sop < sops + nsops; sop++) {
		if (sop->sem_num >= max)
			max = sop->sem_num;
		if (sop->sem_flg & SEM_UNDO)
1331 1332
			undos = 1;
		if (sop->sem_op != 0)
L
Linus Torvalds 已提交
1333 1334 1335 1336
			alter = 1;
	}

	if (undos) {
1337
		un = find_alloc_undo(ns, semid);
L
Linus Torvalds 已提交
1338 1339 1340 1341 1342 1343 1344
		if (IS_ERR(un)) {
			error = PTR_ERR(un);
			goto out_free;
		}
	} else
		un = NULL;

1345 1346
	INIT_LIST_HEAD(&tasks);

1347 1348
	sma = sem_lock_check(ns, semid);
	if (IS_ERR(sma)) {
1349 1350
		if (un)
			rcu_read_unlock();
1351
		error = PTR_ERR(sma);
L
Linus Torvalds 已提交
1352
		goto out_free;
1353 1354
	}

L
Linus Torvalds 已提交
1355
	/*
1356
	 * semid identifiers are not unique - find_alloc_undo may have
L
Linus Torvalds 已提交
1357
	 * allocated an undo structure, it was invalidated by an RMID
1358
	 * and now a new array with received the same id. Check and fail.
L
Lucas De Marchi 已提交
1359
	 * This case can be detected checking un->semid. The existence of
1360
	 * "un" itself is guaranteed by rcu.
L
Linus Torvalds 已提交
1361
	 */
1362
	error = -EIDRM;
1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378
	if (un) {
		if (un->semid == -1) {
			rcu_read_unlock();
			goto out_unlock_free;
		} else {
			/*
			 * rcu lock can be released, "un" cannot disappear:
			 * - sem_lock is acquired, thus IPC_RMID is
			 *   impossible.
			 * - exit_sem is impossible, it always operates on
			 *   current (or a dead task).
			 */

			rcu_read_unlock();
		}
	}
1379

L
Linus Torvalds 已提交
1380 1381 1382 1383 1384
	error = -EFBIG;
	if (max >= sma->sem_nsems)
		goto out_unlock_free;

	error = -EACCES;
1385
	if (ipcperms(ns, &sma->sem_perm, alter ? S_IWUGO : S_IRUGO))
L
Linus Torvalds 已提交
1386 1387 1388 1389 1390 1391
		goto out_unlock_free;

	error = security_sem_semop(sma, sops, nsops, alter);
	if (error)
		goto out_unlock_free;

1392
	error = try_atomic_semop (sma, sops, nsops, un, task_tgid_vnr(current));
L
Linus Torvalds 已提交
1393 1394
	if (error <= 0) {
		if (alter && error == 0)
1395
			do_smart_update(sma, sops, nsops, 1, &tasks);
1396

L
Linus Torvalds 已提交
1397 1398 1399 1400 1401 1402 1403 1404 1405 1406
		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.
	 */
		
	queue.sops = sops;
	queue.nsops = nsops;
	queue.undo = un;
1407
	queue.pid = task_tgid_vnr(current);
L
Linus Torvalds 已提交
1408 1409
	queue.alter = alter;
	if (alter)
1410
		list_add_tail(&queue.list, &sma->sem_pending);
L
Linus Torvalds 已提交
1411
	else
1412
		list_add(&queue.list, &sma->sem_pending);
L
Linus Torvalds 已提交
1413

1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426
	if (nsops == 1) {
		struct sem *curr;
		curr = &sma->sem_base[sops->sem_num];

		if (alter)
			list_add_tail(&queue.simple_list, &curr->sem_pending);
		else
			list_add(&queue.simple_list, &curr->sem_pending);
	} else {
		INIT_LIST_HEAD(&queue.simple_list);
		sma->complex_count++;
	}

L
Linus Torvalds 已提交
1427 1428 1429 1430 1431 1432 1433 1434 1435 1436
	queue.status = -EINTR;
	queue.sleeper = current;
	current->state = TASK_INTERRUPTIBLE;
	sem_unlock(sma);

	if (timeout)
		jiffies_left = schedule_timeout(jiffies_left);
	else
		schedule();

1437
	error = get_queue_result(&queue);
L
Linus Torvalds 已提交
1438 1439 1440

	if (error != -EINTR) {
		/* fast path: update_queue already obtained all requested
1441 1442 1443 1444 1445 1446 1447 1448
		 * resources.
		 * Perform a smp_mb(): User space could assume that semop()
		 * is a memory barrier: Without the mb(), the cpu could
		 * speculatively read in user space stale data that was
		 * overwritten by the previous owner of the semaphore.
		 */
		smp_mb();

L
Linus Torvalds 已提交
1449 1450 1451
		goto out_free;
	}

K
Kirill Korotaev 已提交
1452
	sma = sem_lock(ns, semid);
1453 1454 1455 1456 1457 1458 1459 1460 1461

	/*
	 * Wait until it's guaranteed that no wakeup_sem_queue_do() is ongoing.
	 */
	error = get_queue_result(&queue);

	/*
	 * Array removed? If yes, leave without sem_unlock().
	 */
1462
	if (IS_ERR(sma)) {
L
Linus Torvalds 已提交
1463 1464 1465
		goto out_free;
	}

1466

L
Linus Torvalds 已提交
1467
	/*
1468 1469
	 * If queue.status != -EINTR we are woken up by another process.
	 * Leave without unlink_queue(), but with sem_unlock().
L
Linus Torvalds 已提交
1470
	 */
1471

L
Linus Torvalds 已提交
1472 1473 1474 1475 1476 1477 1478 1479 1480
	if (error != -EINTR) {
		goto out_unlock_free;
	}

	/*
	 * If an interrupt occurred we have to clean up the queue
	 */
	if (timeout && jiffies_left == 0)
		error = -EAGAIN;
1481
	unlink_queue(sma, &queue);
L
Linus Torvalds 已提交
1482 1483 1484

out_unlock_free:
	sem_unlock(sma);
1485 1486

	wake_up_sem_queue_do(&tasks);
L
Linus Torvalds 已提交
1487 1488 1489 1490 1491 1492
out_free:
	if(sops != fast_sops)
		kfree(sops);
	return error;
}

1493 1494
SYSCALL_DEFINE3(semop, int, semid, struct sembuf __user *, tsops,
		unsigned, nsops)
L
Linus Torvalds 已提交
1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533
{
	return sys_semtimedop(semid, tsops, nsops, NULL);
}

/* If CLONE_SYSVSEM is set, establish sharing of SEM_UNDO state between
 * parent and child tasks.
 */

int copy_semundo(unsigned long clone_flags, struct task_struct *tsk)
{
	struct sem_undo_list *undo_list;
	int error;

	if (clone_flags & CLONE_SYSVSEM) {
		error = get_undo_list(&undo_list);
		if (error)
			return error;
		atomic_inc(&undo_list->refcnt);
		tsk->sysvsem.undo_list = undo_list;
	} else 
		tsk->sysvsem.undo_list = NULL;

	return 0;
}

/*
 * add semadj values to semaphores, free undo structures.
 * undo structures are not freed when semaphore arrays are destroyed
 * so some of them may be out of date.
 * IMPLEMENTATION NOTE: There is some confusion over whether the
 * set of adjustments that needs to be done should be done in an atomic
 * manner or not. That is, if we are attempting to decrement the semval
 * should we queue up and wait until we can do so legally?
 * The original implementation attempted to do this (queue and wait).
 * The current implementation does not do so. The POSIX standard
 * and SVID should be consulted to determine what behavior is mandated.
 */
void exit_sem(struct task_struct *tsk)
{
1534
	struct sem_undo_list *ulp;
L
Linus Torvalds 已提交
1535

1536 1537
	ulp = tsk->sysvsem.undo_list;
	if (!ulp)
L
Linus Torvalds 已提交
1538
		return;
1539
	tsk->sysvsem.undo_list = NULL;
L
Linus Torvalds 已提交
1540

1541
	if (!atomic_dec_and_test(&ulp->refcnt))
L
Linus Torvalds 已提交
1542 1543
		return;

1544
	for (;;) {
L
Linus Torvalds 已提交
1545
		struct sem_array *sma;
1546
		struct sem_undo *un;
1547
		struct list_head tasks;
1548
		int semid;
1549 1550
		int i;

1551
		rcu_read_lock();
1552 1553
		un = list_entry_rcu(ulp->list_proc.next,
				    struct sem_undo, list_proc);
1554 1555 1556 1557 1558
		if (&un->list_proc == &ulp->list_proc)
			semid = -1;
		 else
			semid = un->semid;
		rcu_read_unlock();
1559

1560 1561
		if (semid == -1)
			break;
L
Linus Torvalds 已提交
1562

1563
		sma = sem_lock_check(tsk->nsproxy->ipc_ns, un->semid);
L
Linus Torvalds 已提交
1564

1565 1566 1567
		/* exit_sem raced with IPC_RMID, nothing to do */
		if (IS_ERR(sma))
			continue;
L
Linus Torvalds 已提交
1568

1569
		un = __lookup_undo(ulp, semid);
1570 1571 1572 1573 1574 1575 1576 1577 1578
		if (un == NULL) {
			/* exit_sem raced with IPC_RMID+semget() that created
			 * exactly the same semid. Nothing to do.
			 */
			sem_unlock(sma);
			continue;
		}

		/* remove un from the linked lists */
1579 1580 1581
		assert_spin_locked(&sma->sem_perm.lock);
		list_del(&un->list_id);

1582 1583 1584 1585
		spin_lock(&ulp->lock);
		list_del_rcu(&un->list_proc);
		spin_unlock(&ulp->lock);

1586 1587
		/* perform adjustments registered in un */
		for (i = 0; i < sma->sem_nsems; i++) {
I
Ingo Molnar 已提交
1588
			struct sem * semaphore = &sma->sem_base[i];
1589 1590
			if (un->semadj[i]) {
				semaphore->semval += un->semadj[i];
L
Linus Torvalds 已提交
1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603
				/*
				 * Range checks of the new semaphore value,
				 * not defined by sus:
				 * - Some unices ignore the undo entirely
				 *   (e.g. HP UX 11i 11.22, Tru64 V5.1)
				 * - some cap the value (e.g. FreeBSD caps
				 *   at 0, but doesn't enforce SEMVMX)
				 *
				 * Linux caps the semaphore value, both at 0
				 * and at SEMVMX.
				 *
				 * 	Manfred <manfred@colorfullife.com>
				 */
I
Ingo Molnar 已提交
1604 1605 1606 1607
				if (semaphore->semval < 0)
					semaphore->semval = 0;
				if (semaphore->semval > SEMVMX)
					semaphore->semval = SEMVMX;
1608
				semaphore->sempid = task_tgid_vnr(current);
L
Linus Torvalds 已提交
1609 1610 1611
			}
		}
		/* maybe some queued-up processes were waiting for this */
1612 1613
		INIT_LIST_HEAD(&tasks);
		do_smart_update(sma, NULL, 0, 1, &tasks);
L
Linus Torvalds 已提交
1614
		sem_unlock(sma);
1615
		wake_up_sem_queue_do(&tasks);
1616

1617
		kfree_rcu(un, rcu);
L
Linus Torvalds 已提交
1618
	}
1619
	kfree(ulp);
L
Linus Torvalds 已提交
1620 1621 1622
}

#ifdef CONFIG_PROC_FS
1623
static int sysvipc_sem_proc_show(struct seq_file *s, void *it)
L
Linus Torvalds 已提交
1624
{
1625 1626 1627
	struct sem_array *sma = it;

	return seq_printf(s,
1628
			  "%10d %10d  %4o %10u %5u %5u %5u %5u %10lu %10lu\n",
1629
			  sma->sem_perm.key,
N
Nadia Derbey 已提交
1630
			  sma->sem_perm.id,
1631 1632 1633 1634 1635 1636 1637 1638
			  sma->sem_perm.mode,
			  sma->sem_nsems,
			  sma->sem_perm.uid,
			  sma->sem_perm.gid,
			  sma->sem_perm.cuid,
			  sma->sem_perm.cgid,
			  sma->sem_otime,
			  sma->sem_ctime);
L
Linus Torvalds 已提交
1639 1640
}
#endif