/* * 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_semcnt() * - 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 <linux/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 */	spinlock_t	lock;	/* spinlock for fine-grained semtimedop */	struct list_head pending_alter; /* pending single-sop operations */					/* that alter the semaphore */	struct list_head pending_const; /* pending single-sop operations */					/* that do not alter the semaphore*/	time_t	sem_otime;	/* candidate for sem_otime */} ____cacheline_aligned_in_smp; /* One queue for each sleeping process in the system. */struct sem_queue {	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 */	struct sembuf		*blocking; /* the operation that blocked */	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_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 */ /* * Locking: *	sem_undo.id_next, *	sem_array.complex_count, *	sem_array.pending{_alter,_cont}, *	sem_array.sem_undo: global sem_lock() for read/write *	sem_undo.proc_next: only "current" is allowed to read/write that field. * *	sem_array.sem_base[i].pending_{const,alter}: *		global or semaphore sem_lock() for read/write */ #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);} /** * unmerge_queues - unmerge queues, if possible. * @sma: semaphore array * * The function unmerges the wait queues if complex_count is 0. * It must be called prior to dropping the global semaphore array lock. */static void unmerge_queues(struct sem_array *sma){	struct sem_queue *q, *tq; 	/* complex operations still around? */	if (sma->complex_count)		return;	/*	 * We will switch back to simple mode.	 * Move all pending operation back into the per-semaphore	 * queues.	 */	list_for_each_entry_safe(q, tq, &sma->pending_alter, list) {		struct sem *curr;		curr = &sma->sem_base[q->sops[0].sem_num]; 		list_add_tail(&q->list, &curr->pending_alter);	}	INIT_LIST_HEAD(&sma->pending_alter);} /** * merge_queues - merge single semop queues into global queue * @sma: semaphore array * * This function merges all per-semaphore queues into the global queue. * It is necessary to achieve FIFO ordering for the pending single-sop * operations when a multi-semop operation must sleep. * Only the alter operations must be moved, the const operations can stay. */static void merge_queues(struct sem_array *sma){	int i;	for (i = 0; i < sma->sem_nsems; i++) {		struct sem *sem = sma->sem_base + i; 		list_splice_init(&sem->pending_alter, &sma->pending_alter);	}} static void sem_rcu_free(struct rcu_head *head){	struct ipc_rcu *p = container_of(head, struct ipc_rcu, rcu);	struct sem_array *sma = ipc_rcu_to_struct(p); 	security_sem_free(sma);	ipc_rcu_free(head);} /* * Wait until all currently ongoing simple ops have completed. * Caller must own sem_perm.lock. * New simple ops cannot start, because simple ops first check * that sem_perm.lock is free. * that a) sem_perm.lock is free and b) complex_count is 0. */static void sem_wait_array(struct sem_array *sma){	int i;	struct sem *sem; 	if (sma->complex_count)  {		/* The thread that increased sma->complex_count waited on		 * all sem->lock locks. Thus we don't need to wait again.		 */		return;	} 	for (i = 0; i < sma->sem_nsems; i++) {		sem = sma->sem_base + i;		spin_unlock_wait(&sem->lock);	}} /* * If the request contains only one semaphore operation, and there are * no complex transactions pending, lock only the semaphore involved. * Otherwise, lock the entire semaphore array, since we either have * multiple semaphores in our own semops, or we need to look at * semaphores from other pending complex operations. */static inline int sem_lock(struct sem_array *sma, struct sembuf *sops,			      int nsops){	struct sem *sem; 	if (nsops != 1) {		/* Complex operation - acquire a full lock */		ipc_lock_object(&sma->sem_perm); 		/* And wait until all simple ops that are processed		 * right now have dropped their locks.		 */		sem_wait_array(sma);		return -1;	} 	/*	 * Only one semaphore affected - try to optimize locking.	 * The rules are:	 * - optimized locking is possible if no complex operation	 *   is either enqueued or processed right now.	 * - The test for enqueued complex ops is simple:	 *      sma->complex_count != 0	 * - Testing for complex ops that are processed right now is	 *   a bit more difficult. Complex ops acquire the full lock	 *   and first wait that the running simple ops have completed.	 *   (see above)	 *   Thus: If we own a simple lock and the global lock is free	 *	and complex_count is now 0, then it will stay 0 and	 *	thus just locking sem->lock is sufficient.	 */	sem = sma->sem_base + sops->sem_num; 	if (sma->complex_count == 0) {		/*		 * It appears that no complex operation is around.		 * Acquire the per-semaphore lock.		 */		spin_lock(&sem->lock); 		/* Then check that the global lock is free */		if (!spin_is_locked(&sma->sem_perm.lock)) {			/*			 * The ipc object lock check must be visible on all			 * cores before rechecking the complex count.  Otherwise			 * we can race with  another thread that does:			 *	complex_count++;			 *	spin_unlock(sem_perm.lock);			 */			smp_rmb(); 			/*			 * Now repeat the test of complex_count:			 * It can't change anymore until we drop sem->lock.			 * Thus: if is now 0, then it will stay 0.			 */			if (sma->complex_count == 0) {				/* fast path successful! */				return sops->sem_num;			}		}		spin_unlock(&sem->lock);	} 	/* slow path: acquire the full lock */	ipc_lock_object(&sma->sem_perm); 	if (sma->complex_count == 0) {		/* False alarm:		 * There is no complex operation, thus we can switch		 * back to the fast path.		 */		spin_lock(&sem->lock);		ipc_unlock_object(&sma->sem_perm);		return sops->sem_num;	} else {		/* Not a false alarm, thus complete the sequence for a		 * full lock.		 */		sem_wait_array(sma);		return -1;	}} static inline void sem_unlock(struct sem_array *sma, int locknum){	if (locknum == -1) {		unmerge_queues(sma);		ipc_unlock_object(&sma->sem_perm);	} else {		struct sem *sem = sma->sem_base + locknum;		spin_unlock(&sem->lock);	}} /* * sem_lock_(check_) routines are called in the paths where the rwsem * is not held. * * The caller holds the RCU read lock. */static inline struct sem_array *sem_obtain_lock(struct ipc_namespace *ns,			int id, struct sembuf *sops, int nsops, int *locknum){	struct kern_ipc_perm *ipcp;	struct sem_array *sma; 	ipcp = ipc_obtain_object(&sem_ids(ns), id);	if (IS_ERR(ipcp))		return ERR_CAST(ipcp); 	sma = container_of(ipcp, struct sem_array, sem_perm);	*locknum = sem_lock(sma, sops, nsops); 	/* ipc_rmid() may have already freed the ID while sem_lock	 * was spinning: verify that the structure is still valid	 */	if (ipc_valid_object(ipcp))		return container_of(ipcp, struct sem_array, sem_perm); 	sem_unlock(sma, *locknum);	return ERR_PTR(-EINVAL);} static inline struct sem_array *sem_obtain_object(struct ipc_namespace *ns, int id){	struct kern_ipc_perm *ipcp = ipc_obtain_object(&sem_ids(ns), id); 	if (IS_ERR(ipcp))		return ERR_CAST(ipcp); 	return container_of(ipcp, struct sem_array, sem_perm);} static inline struct sem_array *sem_obtain_object_check(struct ipc_namespace *ns,							int id){	struct kern_ipc_perm *ipcp = ipc_obtain_object_check(&sem_ids(ns), id); 	if (IS_ERR(ipcp))		return ERR_CAST(ipcp); 	return container_of(ipcp, struct sem_array, sem_perm);} static inline void sem_lock_and_putref(struct sem_array *sma){	sem_lock(sma, NULL, -1);	ipc_rcu_putref(sma, ipc_rcu_free);} 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 the pending list *	* 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.rwsem 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);

Lines 1–500 of 2186. Load more