/* * 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 */	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 */	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);	}} /* * 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. * * Carefully guard against sma->complex_count changing between zero * and non-zero while we are spinning for the lock. The value of * sma->complex_count cannot change while we are holding the lock, * so sem_unlock should be fine. * * The global lock path checks that all the local locks have been released, * checking each local lock once. This means that the local lock paths * cannot start their critical sections while the global lock is held. */static inline int sem_lock(struct sem_array *sma, struct sembuf *sops,			      int nsops){	int locknum; again:	if (nsops == 1 && !sma->complex_count) {		struct sem *sem = sma->sem_base + sops->sem_num; 		/* Lock just the semaphore we are interested in. */		spin_lock(&sem->lock); 		/*		 * If sma->complex_count was set while we were spinning,		 * we may need to look at things we did not lock here.		 */		if (unlikely(sma->complex_count)) {			spin_unlock(&sem->lock);			goto lock_array;		} 		/*		 * Another process is holding the global lock on the		 * sem_array; we cannot enter our critical section,		 * but have to wait for the global lock to be released.		 */		if (unlikely(spin_is_locked(&sma->sem_perm.lock))) {			spin_unlock(&sem->lock);			spin_unlock_wait(&sma->sem_perm.lock);			goto again;		} 		locknum = sops->sem_num;	} else {		int i;		/*		 * Lock the semaphore array, and wait for all of the		 * individual semaphore locks to go away.  The code		 * above ensures no new single-lock holders will enter		 * their critical section while the array lock is held.		 */ lock_array:		ipc_lock_object(&sma->sem_perm);		for (i = 0; i < sma->sem_nsems; i++) {			struct sem *sem = sma->sem_base + i;			spin_unlock_wait(&sem->lock);		}		locknum = -1;	}	return locknum;} 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 rw_mutex * 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 (!ipcp->deleted)		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);} static inline void sem_putref(struct sem_array *sma){	ipc_rcu_putref(sma);} 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.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].pending_alter);		INIT_LIST_HEAD(&sma->sem_base[i].pending_const);		spin_lock_init(&sma->sem_base[i].lock);	} 	sma->complex_count = 0;	INIT_LIST_HEAD(&sma->pending_alter);	INIT_LIST_HEAD(&sma->pending_const);	INIT_LIST_HEAD(&sma->list_id);	sma->sem_nsems = nsems;	sma->sem_ctime = get_seconds();	sem_unlock(sma, -1);	rcu_read_unlock(); 	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; 

Lines 1–500 of 2077. Load more