// SPDX-License-Identifier: GPL-2.0/* * 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> * (c) 2016 Davidlohr Bueso <dave@stgolabs.net> * 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()) * - 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). * - 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/compat.h>#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/sched/wake_q.h>#include <linux/nospec.h>#include <linux/rhashtable.h> #include <linux/uaccess.h>#include "util.h" /* One semaphore structure for each semaphore in the system. */struct sem {	int	semval;		/* current value */	/*	 * PID of the process that last modified the semaphore. For	 * Linux, specifically these are:	 *  - semop	 *  - semctl, via SETVAL and SETALL.	 *  - at task exit when performing undo adjustments (see exit_sem).	 */	struct pid *sempid;	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*/	time64_t	 sem_otime;	/* candidate for sem_otime */} ____cacheline_aligned_in_smp; /* One sem_array data structure for each set of semaphores in the system. */struct sem_array {	struct kern_ipc_perm	sem_perm;	/* permissions .. see ipc.h */	time64_t		sem_ctime;	/* create/last semctl() time */	struct list_head	pending_alter;	/* pending operations */						/* that alter the array */	struct list_head	pending_const;	/* pending complex operations */						/* that do not alter semvals */	struct list_head	list_id;	/* undo requests on this array */	int			sem_nsems;	/* no. of semaphores in array */	int			complex_count;	/* pending complex operations */	unsigned int		use_global_lock;/* >0: global lock required */ 	struct sem		sems[];} __randomize_layout; /* 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 */	struct pid		*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 */	bool			alter;	 /* does *sops alter the array? */	bool                    dupsop;	 /* sops on more than one sem_num */}; /* 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 {	refcount_t		refcnt;	spinlock_t		lock;	struct list_head	list_proc;};  #define sem_ids(ns)	((ns)->ids[IPC_SEM_IDS]) 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 */ /* * Switching from the mode suitable for simple ops * to the mode for complex ops is costly. Therefore: * use some hysteresis */#define USE_GLOBAL_LOCK_HYSTERESIS	10 /* * Locking: * a) global sem_lock() for read/write *	sem_undo.id_next, *	sem_array.complex_count, *	sem_array.pending{_alter,_const}, *	sem_array.sem_undo * * b) global or semaphore sem_lock() for read/write: *	sem_array.sems[i].pending_{const,alter}: * * c) special: *	sem_undo_list.list_proc: *	* undo_list->lock for write *	* rcu for read *	use_global_lock: *	* global sem_lock() for write *	* either local or global sem_lock() for read. * * Memory ordering: * Most ordering is enforced by using spin_lock() and spin_unlock(). * * Exceptions: * 1) use_global_lock: (SEM_BARRIER_1) * Setting it from non-zero to 0 is a RELEASE, this is ensured by * using smp_store_release(): Immediately after setting it to 0, * a simple op can start. * Testing if it is non-zero is an ACQUIRE, this is ensured by using * smp_load_acquire(). * Setting it from 0 to non-zero must be ordered with regards to * this smp_load_acquire(), this is guaranteed because the smp_load_acquire() * is inside a spin_lock() and after a write from 0 to non-zero a * spin_lock()+spin_unlock() is done. * * 2) queue.status: (SEM_BARRIER_2) * Initialization is done while holding sem_lock(), so no further barrier is * required. * Setting it to a result code is a RELEASE, this is ensured by both a * smp_store_release() (for case a) and while holding sem_lock() * (for case b). * The AQUIRE when reading the result code without holding sem_lock() is * achieved by using READ_ONCE() + smp_acquire__after_ctrl_dep(). * (case a above). * Reading the result code while holding sem_lock() needs no further barriers, * the locks inside sem_lock() enforce ordering (case b above) * * 3) current->state: * current->state is set to TASK_INTERRUPTIBLE while holding sem_lock(). * The wakeup is handled using the wake_q infrastructure. wake_q wakeups may * happen immediately after calling wake_q_add. As wake_q_add_safe() is called * when holding sem_lock(), no further barriers are required. * * See also ipc/mqueue.c for more details on the covered races. */ #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);	rhashtable_destroy(&ns->ids[IPC_SEM_IDS].key_ht);}#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->sems[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->sems[i]; 		list_splice_init(&sem->pending_alter, &sma->pending_alter);	}} static void sem_rcu_free(struct rcu_head *head){	struct kern_ipc_perm *p = container_of(head, struct kern_ipc_perm, rcu);	struct sem_array *sma = container_of(p, struct sem_array, sem_perm); 	security_sem_free(&sma->sem_perm);	kvfree(sma);} /* * Enter the mode suitable for non-simple operations: * Caller must own sem_perm.lock. */static void complexmode_enter(struct sem_array *sma){	int i;	struct sem *sem; 	if (sma->use_global_lock > 0)  {		/*		 * We are already in global lock mode.		 * Nothing to do, just reset the		 * counter until we return to simple mode.		 */		sma->use_global_lock = USE_GLOBAL_LOCK_HYSTERESIS;		return;	}	sma->use_global_lock = USE_GLOBAL_LOCK_HYSTERESIS; 	for (i = 0; i < sma->sem_nsems; i++) {		sem = &sma->sems[i];		spin_lock(&sem->lock);		spin_unlock(&sem->lock);	}} /* * Try to leave the mode that disallows simple operations: * Caller must own sem_perm.lock. */static void complexmode_tryleave(struct sem_array *sma){	if (sma->complex_count)  {		/* Complex ops are sleeping.		 * We must stay in complex mode		 */		return;	}	if (sma->use_global_lock == 1) { 		/* See SEM_BARRIER_1 for purpose/pairing */		smp_store_release(&sma->use_global_lock, 0);	} else {		sma->use_global_lock--;	}} #define SEM_GLOBAL_LOCK	(-1)/* * 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;	int idx; 	if (nsops != 1) {		/* Complex operation - acquire a full lock */		ipc_lock_object(&sma->sem_perm); 		/* Prevent parallel simple ops */		complexmode_enter(sma);		return SEM_GLOBAL_LOCK;	} 	/*	 * Only one semaphore affected - try to optimize locking.	 * Optimized locking is possible if no complex operation	 * is either enqueued or processed right now.	 *	 * Both facts are tracked by use_global_mode.	 */	idx = array_index_nospec(sops->sem_num, sma->sem_nsems);	sem = &sma->sems[idx]; 	/*	 * Initial check for use_global_lock. Just an optimization,	 * no locking, no memory barrier.	 */	if (!sma->use_global_lock) {		/*		 * It appears that no complex operation is around.		 * Acquire the per-semaphore lock.		 */		spin_lock(&sem->lock); 		/* see SEM_BARRIER_1 for purpose/pairing */		if (!smp_load_acquire(&sma->use_global_lock)) {			/* 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->use_global_lock == 0) {		/*		 * The use_global_lock mode ended while we waited for		 * sma->sem_perm.lock. Thus we must switch to locking		 * with sem->lock.		 * Unlike in the fast path, there is no need to recheck		 * sma->use_global_lock after we have acquired sem->lock:		 * We own sma->sem_perm.lock, thus use_global_lock cannot		 * change.		 */		spin_lock(&sem->lock); 		ipc_unlock_object(&sma->sem_perm);		return sops->sem_num;	} else {		/*		 * Not a false alarm, thus continue to use the global lock		 * mode. No need for complexmode_enter(), this was done by		 * the caller that has set use_global_mode to non-zero.		 */		return SEM_GLOBAL_LOCK;	}} static inline void sem_unlock(struct sem_array *sma, int locknum){	if (locknum == SEM_GLOBAL_LOCK) {		unmerge_queues(sma);		complexmode_tryleave(sma);		ipc_unlock_object(&sma->sem_perm);	} else {		struct sem *sem = &sma->sems[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_object(struct ipc_namespace *ns, int id){	struct kern_ipc_perm *ipcp = ipc_obtain_object_idr(&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->sem_perm, sem_rcu_free);}

Lines 1–500 of 2461. Load more