/* * 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 * (c) 1999 Manfred Spraul <manfred@colorfullife.com> * Enforced range limit on SEM_UNDO * (c) 2001 Red Hat Inc * Lockless wakeup * (c) 2003 Manfred Spraul <manfred@colorfullife.com> * Further wakeup optimizations, documentation * (c) 2010 Manfred Spraul <manfred@colorfullife.com> * * support for audit of ipc object properties and permission changes * Dustin Kirkland <dustin.kirkland@us.ibm.com> * * namespaces support * OpenVZ, SWsoft Inc. * Pavel Emelianov <xemul@openvz.org> * * 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. */ #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>#include <linux/capability.h>#include <linux/seq_file.h>#include <linux/rwsem.h>#include <linux/nsproxy.h>#include <linux/ipc_namespace.h> #include <asm/uaccess.h>#include "util.h" /* One semaphore structure for each semaphore in the system. */struct sem {	int	semval;		/* current value */	int	sempid;		/* pid of last operation */	struct list_head sem_pending; /* pending single-sop operations */}; /* One queue for each sleeping process in the system. */struct sem_queue {	struct list_head	simple_list; /* queue of pending operations */	struct list_head	list;	 /* queue of pending operations */	struct task_struct	*sleeper; /* this process */	struct sem_undo		*undo;	 /* undo structure */	int			pid;	 /* process id of requesting process */	int			status;	 /* completion status of operation */	struct sembuf		*sops;	 /* array of pending operations */	int			nsops;	 /* number of operations */	int			alter;	 /* does *sops alter the array? */}; /* Each task has a list of undo requests. They are executed automatically * when the process exits. */struct sem_undo {	struct list_head	list_proc;	/* per-process list: *						 * all undos from one process						 * rcu protected */	struct rcu_head		rcu;		/* rcu struct for sem_undo */	struct sem_undo_list	*ulp;		/* back ptr to sem_undo_list */	struct list_head	list_id;	/* per semaphore array list:						 * all undos for one array */	int			semid;		/* semaphore set identifier */	short			*semadj;	/* array of adjustments */						/* one per semaphore */}; /* sem_undo_list controls shared access to the list of sem_undo structures * that may be shared among all a CLONE_SYSVSEM task group. */struct sem_undo_list {	atomic_t		refcnt;	spinlock_t		lock;	struct list_head	list_proc;};  #define sem_ids(ns)	((ns)->ids[IPC_SEM_IDS]) #define sem_unlock(sma)		ipc_unlock(&(sma)->sem_perm)#define sem_checkid(sma, semid)	ipc_checkid(&sma->sem_perm, semid) static int newary(struct ipc_namespace *, struct ipc_params *);static void freeary(struct ipc_namespace *, struct kern_ipc_perm *);#ifdef CONFIG_PROC_FSstatic int sysvipc_sem_proc_show(struct seq_file *s, void *it);#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. *	 */ #define sc_semmsl	sem_ctls[0]#define sc_semmns	sem_ctls[1]#define sc_semopm	sem_ctls[2]#define sc_semmni	sem_ctls[3] void sem_init_ns(struct ipc_namespace *ns){	ns->sc_semmsl = SEMMSL;	ns->sc_semmns = SEMMNS;	ns->sc_semopm = SEMOPM;	ns->sc_semmni = SEMMNI;	ns->used_sems = 0;	ipc_init_ids(&ns->ids[IPC_SEM_IDS]);} #ifdef CONFIG_IPC_NSvoid sem_exit_ns(struct ipc_namespace *ns){	free_ipcs(ns, &sem_ids(ns), freeary);	idr_destroy(&ns->ids[IPC_SEM_IDS].ipcs_idr);}#endif void __init sem_init (void){	sem_init_ns(&init_ipc_ns);	ipc_init_proc_interface("sysvipc/sem",				"       key      semid perms      nsems   uid   gid  cuid  cgid      otime      ctime\n",				IPC_SEM_IDS, sysvipc_sem_proc_show);} /* * sem_lock_(check_) routines are called in the paths where the rw_mutex * is not held. */static inline struct sem_array *sem_lock(struct ipc_namespace *ns, int id){	struct kern_ipc_perm *ipcp = ipc_lock(&sem_ids(ns), id); 	if (IS_ERR(ipcp))		return (struct sem_array *)ipcp; 	return container_of(ipcp, struct sem_array, sem_perm);} static inline struct sem_array *sem_lock_check(struct ipc_namespace *ns,						int id){	struct kern_ipc_perm *ipcp = ipc_lock_check(&sem_ids(ns), id); 	if (IS_ERR(ipcp))		return (struct sem_array *)ipcp; 	return container_of(ipcp, struct sem_array, sem_perm);} 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);} static inline void sem_rmid(struct ipc_namespace *ns, struct sem_array *s){	ipc_rmid(&sem_ids(ns), &s->sem_perm);} /* * 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 *   	  performing any operation on the sem array. *   	* 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 /** * newary - Create a new semaphore set * @ns: namespace * @params: ptr to the structure that contains key, semflg and nsems * * Called with sem_ids.rw_mutex held (as a writer) */ static int newary(struct ipc_namespace *ns, struct ipc_params *params){	int id;	int retval;	struct sem_array *sma;	int size;	key_t key = params->key;	int nsems = params->u.nsems;	int semflg = params->flg;	int i; 	if (!nsems)		return -EINVAL;	if (ns->used_sems + nsems > ns->sc_semmns)		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;	} 	id = ipc_addid(&sem_ids(ns), &sma->sem_perm, ns->sc_semmni);	if (id < 0) {		security_sem_free(sma);		ipc_rcu_putref(sma);		return id;	}	ns->used_sems += nsems; 	sma->sem_base = (struct sem *) &sma[1]; 	for (i = 0; i < nsems; i++)		INIT_LIST_HEAD(&sma->sem_base[i].sem_pending); 	sma->complex_count = 0;	INIT_LIST_HEAD(&sma->sem_pending);	INIT_LIST_HEAD(&sma->list_id);	sma->sem_nsems = nsems;	sma->sem_ctime = get_seconds();	sem_unlock(sma); 	return sma->sem_perm.id;}  /* * Called with sem_ids.rw_mutex and ipcp locked. */static inline int sem_security(struct kern_ipc_perm *ipcp, int semflg){	struct sem_array *sma; 	sma = container_of(ipcp, struct sem_array, sem_perm);	return security_sem_associate(sma, semflg);} /* * Called with sem_ids.rw_mutex and ipcp locked. */static inline int sem_more_checks(struct kern_ipc_perm *ipcp,				struct ipc_params *params){	struct sem_array *sma; 	sma = container_of(ipcp, struct sem_array, sem_perm);	if (params->u.nsems > sma->sem_nsems)		return -EINVAL; 	return 0;} SYSCALL_DEFINE3(semget, key_t, key, int, nsems, int, semflg){	struct ipc_namespace *ns;	struct ipc_ops sem_ops;	struct ipc_params sem_params; 	ns = current->nsproxy->ipc_ns; 	if (nsems < 0 || nsems > ns->sc_semmsl)		return -EINVAL; 	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; 	return ipcget(ns, &sem_ids(ns), &sem_ops, &sem_params);} /* * 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;} /** 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. */static void wake_up_sem_queue_prepare(struct list_head *pt,				struct sem_queue *q, int error){	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();	}	q->status = IN_WAKEUP;	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();}

Lines 1–500 of 1695. Load more