// 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_FS

static 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().

 * The special case is use_global_lock:

 * Setting it from non-zero to 0 is a RELEASE, this is ensured by

 * using smp_store_release().

 * 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.

 */

#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_NS

void 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) {

		/*

		 * Immediately after setting use_global_lock to 0,

		 * a simple op can start. Thus: all memory writes

		 * performed by the current operation must be visible

		 * before we set use_global_lock to 0.

		 */

		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);

		/* pairs with smp_store_release() */

		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);

}

static inline void sem_rmid(struct ipc_namespace *ns, struct sem_array *s)

{

	ipc_rmid(&sem_ids(ns), &s->sem_perm);

}

static struct sem_array *sem_alloc(size_t nsems)

{

	struct sem_array *sma;

	size_t size;

	if (nsems > (INT_MAX - sizeof(*sma)) / sizeof(sma->sems[0]))

		return NULL;

	size = sizeof(*sma) + nsems * sizeof(sma->sems[0]);

	sma = kvmalloc(size, GFP_KERNEL);

	if (unlikely(!sma))

		return NULL;

	memset(sma, 0, size);

	return sma;

}

/**

 * 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 retval;

	struct sem_array *sma;

	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;

	sma = sem_alloc(nsems);

	if (!sma)

		return -ENOMEM;

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

	sma->sem_perm.key = key;

	sma->sem_perm.security = NULL;

	retval = security_sem_alloc(&sma->sem_perm);

	if (retval) {

		kvfree(sma);

		return retval;

	}

	for (i = 0; i < nsems; i++) {

		INIT_LIST_HEAD(&sma->sems[i].pending_alter);

		INIT_LIST_HEAD(&sma->sems[i].pending_const);

		spin_lock_init(&sma->sems[i].lock);

	}

	sma->complex_count = 0;

	sma->use_global_lock = USE_GLOBAL_LOCK_HYSTERESIS;

	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 = ktime_get_real_seconds();

	/* ipc_addid() locks sma upon success. */

	retval = ipc_addid(&sem_ids(ns), &sma->sem_perm, ns->sc_semmni);

	if (retval < 0) {

		ipc_rcu_putref(&sma->sem_perm, sem_rcu_free);

		return retval;

	}

	ns->used_sems += nsems;

	sem_unlock(sma, -1);

	rcu_read_unlock();

	return sma->sem_perm.id;

}

/*

 * Called with sem_ids.rwsem 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;

}

long ksys_semget(key_t key, int nsems, int semflg)

{

	struct ipc_namespace *ns;

	static const struct ipc_ops sem_ops = {

		.getnew = newary,

		.associate = security_sem_associate,

		.more_checks = sem_more_checks,

	};

	struct ipc_params sem_params;

	ns = current->nsproxy->ipc_ns;

	if (nsems < 0 || nsems > ns->sc_semmsl)

		return -EINVAL;

	sem_params.key = key;

	sem_params.flg = semflg;

	sem_params.u.nsems = nsems;

	return ipcget(ns, &sem_ids(ns), &sem_ops, &sem_params);

}

SYSCALL_DEFINE3(semget, key_t, key, int, nsems, int, semflg)

{

	return ksys_semget(key, nsems, semflg);

}

/**

 * perform_atomic_semop[_slow] - Attempt to perform semaphore

 *                               operations on a given array.

 * @sma: semaphore array

 * @q: struct sem_queue that describes the operation

 *

 * Caller blocking are as follows, based the value

 * indicated by the semaphore operation (sem_op):

 *

 *  (1) >0 never blocks.

 *  (2)  0 (wait-for-zero operation): semval is non-zero.

 *  (3) <0 attempting to decrement semval to a value smaller than zero.

 *

 * Returns 0 if the operation was possible.

 * Returns 1 if the operation is impossible, the caller must sleep.

 * Returns <0 for error codes.

 */

static int perform_atomic_semop_slow(struct sem_array *sma, struct sem_queue *q)

{

	int result, sem_op, nsops;

	struct pid *pid;

	struct sembuf *sop;

	struct sem *curr;

	struct sembuf *sops;

	struct sem_undo *un;

	sops = q->sops;

	nsops = q->nsops;

	un = q->undo;

	for (sop = sops; sop < sops + nsops; sop++) {

		int idx = array_index_nospec(sop->sem_num, sma->sem_nsems);

		curr = &sma->sems[idx];

		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;

			un->semadj[sop->sem_num] = undo;

		}

		curr->semval = result;

	}

	sop--;

	pid = q->pid;

	while (sop >= sops) {

		ipc_update_pid(&sma->sems[sop->sem_num].sempid, pid);

		sop--;

	}

	return 0;

out_of_range:

	result = -ERANGE;

	goto undo;

would_block:

	q->blocking = sop;

	if (sop->sem_flg & IPC_NOWAIT)

		result = -EAGAIN;

	else

		result = 1;

undo:

	sop--;

	while (sop >= sops) {

		sem_op = sop->sem_op;

		sma->sems[sop->sem_num].semval -= sem_op;

		if (sop->sem_flg & SEM_UNDO)

			un->semadj[sop->sem_num] += sem_op;

		sop--;

	}

	return result;

}

static int perform_atomic_semop(struct sem_array *sma, struct sem_queue *q)

{

	int result, sem_op, nsops;

	struct sembuf *sop;

	struct sem *curr;

	struct sembuf *sops;

	struct sem_undo *un;

	sops = q->sops;

	nsops = q->nsops;

	un = q->undo;

	if (unlikely(q->dupsop))

		return perform_atomic_semop_slow(sma, q);

	/*

	 * We scan the semaphore set twice, first to ensure that the entire

	 * operation can succeed, therefore avoiding any pointless writes

	 * to shared memory and having to undo such changes in order to block