[mirror_ubuntu-bionic-kernel.git] / drivers / tty / tty_ldsem.c

/*
 * Ldisc rw semaphore
 *
 * The ldisc semaphore is semantically a rw_semaphore but which enforces
 * an alternate policy, namely:
 *   1) Supports lock wait timeouts
 *   2) Write waiter has priority
 *   3) Downgrading is not supported
 *
 * Implementation notes:
 *   1) Upper half of semaphore count is a wait count (differs from rwsem
 *	in that rwsem normalizes the upper half to the wait bias)
 *   2) Lacks overflow checking
 *
 * The generic counting was copied and modified from include/asm-generic/rwsem.h
 * by Paul Mackerras <paulus@samba.org>.
 *
 * The scheduling policy was copied and modified from lib/rwsem.c
 * Written by David Howells (dhowells@redhat.com).
 *
 * This implementation incorporates the write lock stealing work of
 * Michel Lespinasse <walken@google.com>.
 *
 * Copyright (C) 2013 Peter Hurley <peter@hurleysoftware.com>
 *
 * This file may be redistributed under the terms of the GNU General Public
 * License v2.
 */

#include <linux/list.h>
#include <linux/spinlock.h>
#include <linux/atomic.h>
#include <linux/tty.h>
#include <linux/sched.h>
#include <linux/sched/debug.h>


#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define __acq(l, s, t, r, c, n, i)		\
				lock_acquire(&(l)->dep_map, s, t, r, c, n, i)
# define __rel(l, n, i)				\
				lock_release(&(l)->dep_map, n, i)
#define lockdep_acquire(l, s, t, i)		__acq(l, s, t, 0, 1, NULL, i)
#define lockdep_acquire_nest(l, s, t, n, i)	__acq(l, s, t, 0, 1, n, i)
#define lockdep_acquire_read(l, s, t, i)	__acq(l, s, t, 1, 1, NULL, i)
#define lockdep_release(l, n, i)		__rel(l, n, i)
#else
# define lockdep_acquire(l, s, t, i)		do { } while (0)
# define lockdep_acquire_nest(l, s, t, n, i)	do { } while (0)
# define lockdep_acquire_read(l, s, t, i)	do { } while (0)
# define lockdep_release(l, n, i)		do { } while (0)
#endif

#ifdef CONFIG_LOCK_STAT
# define lock_stat(_lock, stat)		lock_##stat(&(_lock)->dep_map, _RET_IP_)
#else
# define lock_stat(_lock, stat)		do { } while (0)
#endif


#if BITS_PER_LONG == 64
# define LDSEM_ACTIVE_MASK	0xffffffffL
#else
# define LDSEM_ACTIVE_MASK	0x0000ffffL
#endif

#define LDSEM_UNLOCKED		0L
#define LDSEM_ACTIVE_BIAS	1L
#define LDSEM_WAIT_BIAS		(-LDSEM_ACTIVE_MASK-1)
#define LDSEM_READ_BIAS		LDSEM_ACTIVE_BIAS
#define LDSEM_WRITE_BIAS	(LDSEM_WAIT_BIAS + LDSEM_ACTIVE_BIAS)

struct ldsem_waiter {
	struct list_head list;
	struct task_struct *task;
};

static inline long ldsem_atomic_update(long delta, struct ld_semaphore *sem)
{
	return atomic_long_add_return(delta, (atomic_long_t *)&sem->count);
}

/*
 * ldsem_cmpxchg() updates @*old with the last-known sem->count value.
 * Returns 1 if count was successfully changed; @*old will have @new value.
 * Returns 0 if count was not changed; @*old will have most recent sem->count
 */
static inline int ldsem_cmpxchg(long *old, long new, struct ld_semaphore *sem)
{
	long tmp = atomic_long_cmpxchg(&sem->count, *old, new);
	if (tmp == *old) {
		*old = new;
		return 1;
	} else {
		*old = tmp;
		return 0;
	}
}

/*
 * Initialize an ldsem:
 */
void __init_ldsem(struct ld_semaphore *sem, const char *name,
		  struct lock_class_key *key)
{
#ifdef CONFIG_DEBUG_LOCK_ALLOC
	/*
	 * Make sure we are not reinitializing a held semaphore:
	 */
	debug_check_no_locks_freed((void *)sem, sizeof(*sem));
	lockdep_init_map(&sem->dep_map, name, key, 0);
#endif
	sem->count = LDSEM_UNLOCKED;
	sem->wait_readers = 0;
	raw_spin_lock_init(&sem->wait_lock);
	INIT_LIST_HEAD(&sem->read_wait);
	INIT_LIST_HEAD(&sem->write_wait);
}

static void __ldsem_wake_readers(struct ld_semaphore *sem)
{
	struct ldsem_waiter *waiter, *next;
	struct task_struct *tsk;
	long adjust, count;

	/* Try to grant read locks to all readers on the read wait list.
	 * Note the 'active part' of the count is incremented by
	 * the number of readers before waking any processes up.
	 */
	adjust = sem->wait_readers * (LDSEM_ACTIVE_BIAS - LDSEM_WAIT_BIAS);
	count = ldsem_atomic_update(adjust, sem);
	do {
		if (count > 0)
			break;
		if (ldsem_cmpxchg(&count, count - adjust, sem))
			return;
	} while (1);

	list_for_each_entry_safe(waiter, next, &sem->read_wait, list) {
		tsk = waiter->task;
		smp_mb();
		waiter->task = NULL;
		wake_up_process(tsk);
		put_task_struct(tsk);
	}
	INIT_LIST_HEAD(&sem->read_wait);
	sem->wait_readers = 0;
}

static inline int writer_trylock(struct ld_semaphore *sem)
{
	/* only wake this writer if the active part of the count can be
	 * transitioned from 0 -> 1
	 */
	long count = ldsem_atomic_update(LDSEM_ACTIVE_BIAS, sem);
	do {
		if ((count & LDSEM_ACTIVE_MASK) == LDSEM_ACTIVE_BIAS)
			return 1;
		if (ldsem_cmpxchg(&count, count - LDSEM_ACTIVE_BIAS, sem))
			return 0;
	} while (1);
}

static void __ldsem_wake_writer(struct ld_semaphore *sem)
{
	struct ldsem_waiter *waiter;

	waiter = list_entry(sem->write_wait.next, struct ldsem_waiter, list);
	wake_up_process(waiter->task);
}

/*
 * handle the lock release when processes blocked on it that can now run
 * - if we come here from up_xxxx(), then:
 *   - the 'active part' of count (&0x0000ffff) reached 0 (but may have changed)
 *   - the 'waiting part' of count (&0xffff0000) is -ve (and will still be so)
 * - the spinlock must be held by the caller
 * - woken process blocks are discarded from the list after having task zeroed
 */
static void __ldsem_wake(struct ld_semaphore *sem)
{
	if (!list_empty(&sem->write_wait))
		__ldsem_wake_writer(sem);
	else if (!list_empty(&sem->read_wait))
		__ldsem_wake_readers(sem);
}

static void ldsem_wake(struct ld_semaphore *sem)
{
	unsigned long flags;

	raw_spin_lock_irqsave(&sem->wait_lock, flags);
	__ldsem_wake(sem);
	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
}

/*
 * wait for the read lock to be granted
 */
static struct ld_semaphore __sched *
down_read_failed(struct ld_semaphore *sem, long count, long timeout)
{
	struct ldsem_waiter waiter;
	long adjust = -LDSEM_ACTIVE_BIAS + LDSEM_WAIT_BIAS;

	/* set up my own style of waitqueue */
	raw_spin_lock_irq(&sem->wait_lock);

	/* Try to reverse the lock attempt but if the count has changed
	 * so that reversing fails, check if there are are no waiters,
	 * and early-out if not */
	do {
		if (ldsem_cmpxchg(&count, count + adjust, sem))
			break;
		if (count > 0) {
			raw_spin_unlock_irq(&sem->wait_lock);
			return sem;
		}
	} while (1);

	list_add_tail(&waiter.list, &sem->read_wait);
	sem->wait_readers++;

	waiter.task = current;
	get_task_struct(current);

	/* if there are no active locks, wake the new lock owner(s) */
	if ((count & LDSEM_ACTIVE_MASK) == 0)
		__ldsem_wake(sem);

	raw_spin_unlock_irq(&sem->wait_lock);

	/* wait to be given the lock */
	for (;;) {
		set_current_state(TASK_UNINTERRUPTIBLE);

		if (!waiter.task)
			break;
		if (!timeout)
			break;
		timeout = schedule_timeout(timeout);
	}

	__set_current_state(TASK_RUNNING);

	if (!timeout) {
		/* lock timed out but check if this task was just
		 * granted lock ownership - if so, pretend there
		 * was no timeout; otherwise, cleanup lock wait */
		raw_spin_lock_irq(&sem->wait_lock);
		if (waiter.task) {
			ldsem_atomic_update(-LDSEM_WAIT_BIAS, sem);
			list_del(&waiter.list);
			raw_spin_unlock_irq(&sem->wait_lock);
			put_task_struct(waiter.task);
			return NULL;
		}
		raw_spin_unlock_irq(&sem->wait_lock);
	}

	return sem;
}

/*
 * wait for the write lock to be granted
 */
static struct ld_semaphore __sched *
down_write_failed(struct ld_semaphore *sem, long count, long timeout)
{
	struct ldsem_waiter waiter;
	long adjust = -LDSEM_ACTIVE_BIAS;
	int locked = 0;

	/* set up my own style of waitqueue */
	raw_spin_lock_irq(&sem->wait_lock);

	/* Try to reverse the lock attempt but if the count has changed
	 * so that reversing fails, check if the lock is now owned,
	 * and early-out if so */
	do {
		if (ldsem_cmpxchg(&count, count + adjust, sem))
			break;
		if ((count & LDSEM_ACTIVE_MASK) == LDSEM_ACTIVE_BIAS) {
			raw_spin_unlock_irq(&sem->wait_lock);
			return sem;
		}
	} while (1);

	list_add_tail(&waiter.list, &sem->write_wait);

	waiter.task = current;

	set_current_state(TASK_UNINTERRUPTIBLE);
	for (;;) {
		if (!timeout)
			break;
		raw_spin_unlock_irq(&sem->wait_lock);
		timeout = schedule_timeout(timeout);
		raw_spin_lock_irq(&sem->wait_lock);
		set_current_state(TASK_UNINTERRUPTIBLE);
		locked = writer_trylock(sem);
		if (locked)
			break;
	}

	if (!locked)
		ldsem_atomic_update(-LDSEM_WAIT_BIAS, sem);
	list_del(&waiter.list);
	raw_spin_unlock_irq(&sem->wait_lock);

	__set_current_state(TASK_RUNNING);

	/* lock wait may have timed out */
	if (!locked)
		return NULL;
	return sem;
}


static int __ldsem_down_read_nested(struct ld_semaphore *sem,
					   int subclass, long timeout)
{
	long count;

	lockdep_acquire_read(sem, subclass, 0, _RET_IP_);

	count = ldsem_atomic_update(LDSEM_READ_BIAS, sem);
	if (count <= 0) {
		lock_stat(sem, contended);
		if (!down_read_failed(sem, count, timeout)) {
			lockdep_release(sem, 1, _RET_IP_);
			return 0;
		}
	}
	lock_stat(sem, acquired);
	return 1;
}

static int __ldsem_down_write_nested(struct ld_semaphore *sem,
					    int subclass, long timeout)
{
	long count;

	lockdep_acquire(sem, subclass, 0, _RET_IP_);

	count = ldsem_atomic_update(LDSEM_WRITE_BIAS, sem);
	if ((count & LDSEM_ACTIVE_MASK) != LDSEM_ACTIVE_BIAS) {
		lock_stat(sem, contended);
		if (!down_write_failed(sem, count, timeout)) {
			lockdep_release(sem, 1, _RET_IP_);
			return 0;
		}
	}
	lock_stat(sem, acquired);
	return 1;
}


/*
 * lock for reading -- returns 1 if successful, 0 if timed out
 */
int __sched ldsem_down_read(struct ld_semaphore *sem, long timeout)
{
	might_sleep();
	return __ldsem_down_read_nested(sem, 0, timeout);
}

/*
 * trylock for reading -- returns 1 if successful, 0 if contention
 */
int ldsem_down_read_trylock(struct ld_semaphore *sem)
{
	long count = sem->count;

	while (count >= 0) {
		if (ldsem_cmpxchg(&count, count + LDSEM_READ_BIAS, sem)) {
			lockdep_acquire_read(sem, 0, 1, _RET_IP_);
			lock_stat(sem, acquired);
			return 1;
		}
	}
	return 0;
}

/*
 * lock for writing -- returns 1 if successful, 0 if timed out
 */
int __sched ldsem_down_write(struct ld_semaphore *sem, long timeout)
{
	might_sleep();
	return __ldsem_down_write_nested(sem, 0, timeout);
}

/*
 * trylock for writing -- returns 1 if successful, 0 if contention
 */
int ldsem_down_write_trylock(struct ld_semaphore *sem)
{
	long count = sem->count;

	while ((count & LDSEM_ACTIVE_MASK) == 0) {
		if (ldsem_cmpxchg(&count, count + LDSEM_WRITE_BIAS, sem)) {
			lockdep_acquire(sem, 0, 1, _RET_IP_);
			lock_stat(sem, acquired);
			return 1;
		}
	}
	return 0;
}

/*
 * release a read lock
 */
void ldsem_up_read(struct ld_semaphore *sem)
{
	long count;

	lockdep_release(sem, 1, _RET_IP_);

	count = ldsem_atomic_update(-LDSEM_READ_BIAS, sem);
	if (count < 0 && (count & LDSEM_ACTIVE_MASK) == 0)
		ldsem_wake(sem);
}

/*
 * release a write lock
 */
void ldsem_up_write(struct ld_semaphore *sem)
{
	long count;

	lockdep_release(sem, 1, _RET_IP_);

	count = ldsem_atomic_update(-LDSEM_WRITE_BIAS, sem);
	if (count < 0)
		ldsem_wake(sem);
}


#ifdef CONFIG_DEBUG_LOCK_ALLOC

int ldsem_down_read_nested(struct ld_semaphore *sem, int subclass, long timeout)
{
	might_sleep();
	return __ldsem_down_read_nested(sem, subclass, timeout);
}

int ldsem_down_write_nested(struct ld_semaphore *sem, int subclass,
			    long timeout)
{
	might_sleep();
	return __ldsem_down_write_nested(sem, subclass, timeout);
}

#endif
Commit	Line	Data
4898e640 PH	1	/*
	2	* Ldisc rw semaphore
	3	*
	4	* The ldisc semaphore is semantically a rw_semaphore but which enforces
	5	* an alternate policy, namely:
	6	* 1) Supports lock wait timeouts
	7	* 2) Write waiter has priority
	8	* 3) Downgrading is not supported
	9	*
	10	* Implementation notes:
	11	* 1) Upper half of semaphore count is a wait count (differs from rwsem
	12	* in that rwsem normalizes the upper half to the wait bias)
	13	* 2) Lacks overflow checking
	14	*
	15	* The generic counting was copied and modified from include/asm-generic/rwsem.h
	16	* by Paul Mackerras <paulus@samba.org>.
	17	*
	18	* The scheduling policy was copied and modified from lib/rwsem.c
	19	* Written by David Howells (dhowells@redhat.com).
	20	*
	21	* This implementation incorporates the write lock stealing work of
	22	* Michel Lespinasse <walken@google.com>.
	23	*
	24	* Copyright (C) 2013 Peter Hurley <peter@hurleysoftware.com>
	25	*
	26	* This file may be redistributed under the terms of the GNU General Public
	27	* License v2.
	28	*/
	29
	30	#include <linux/list.h>
	31	#include <linux/spinlock.h>
	32	#include <linux/atomic.h>
	33	#include <linux/tty.h>
	34	#include <linux/sched.h>
b17b0153	35	#include <linux/sched/debug.h>
4898e640 PH	36
	37
	38	#ifdef CONFIG_DEBUG_LOCK_ALLOC
	39	# define __acq(l, s, t, r, c, n, i) \
	40	lock_acquire(&(l)->dep_map, s, t, r, c, n, i)
	41	# define __rel(l, n, i) \
	42	lock_release(&(l)->dep_map, n, i)
fb9edbe9 ON	43	#define lockdep_acquire(l, s, t, i) __acq(l, s, t, 0, 1, NULL, i)
	44	#define lockdep_acquire_nest(l, s, t, n, i) __acq(l, s, t, 0, 1, n, i)
	45	#define lockdep_acquire_read(l, s, t, i) __acq(l, s, t, 1, 1, NULL, i)
	46	#define lockdep_release(l, n, i) __rel(l, n, i)
4898e640 PH	47	#else
	48	# define lockdep_acquire(l, s, t, i) do { } while (0)
	49	# define lockdep_acquire_nest(l, s, t, n, i) do { } while (0)
	50	# define lockdep_acquire_read(l, s, t, i) do { } while (0)
	51	# define lockdep_release(l, n, i) do { } while (0)
	52	#endif
	53
	54	#ifdef CONFIG_LOCK_STAT
	55	# define lock_stat(_lock, stat) lock_##stat(&(_lock)->dep_map, _RET_IP_)
	56	#else
	57	# define lock_stat(_lock, stat) do { } while (0)
	58	#endif
	59
	60
	61	#if BITS_PER_LONG == 64
	62	# define LDSEM_ACTIVE_MASK 0xffffffffL
	63	#else
	64	# define LDSEM_ACTIVE_MASK 0x0000ffffL
	65	#endif
	66
	67	#define LDSEM_UNLOCKED 0L
	68	#define LDSEM_ACTIVE_BIAS 1L
	69	#define LDSEM_WAIT_BIAS (-LDSEM_ACTIVE_MASK-1)
	70	#define LDSEM_READ_BIAS LDSEM_ACTIVE_BIAS
	71	#define LDSEM_WRITE_BIAS (LDSEM_WAIT_BIAS + LDSEM_ACTIVE_BIAS)
	72
	73	struct ldsem_waiter {
	74	struct list_head list;
	75	struct task_struct *task;
	76	};
	77
	78	static inline long ldsem_atomic_update(long delta, struct ld_semaphore *sem)
	79	{
	80	return atomic_long_add_return(delta, (atomic_long_t *)&sem->count);
	81	}
	82
cf872776 PH	83	/*
	84	* ldsem_cmpxchg() updates @*old with the last-known sem->count value.
	85	* Returns 1 if count was successfully changed; @*old will have @new value.
	86	* Returns 0 if count was not changed; @*old will have most recent sem->count
	87	*/
4898e640 PH	88	static inline int ldsem_cmpxchg(long old, long new, struct ld_semaphore sem)
4898e640 PH	89	{
cf872776 PH	90	long tmp = atomic_long_cmpxchg(&sem->count, *old, new);
	91	if (tmp == *old) {
	92	*old = new;
	93	return 1;
	94	} else {
	95	*old = tmp;
	96	return 0;
	97	}
4898e640 PH	98	}
	99
	100	/*
	101	* Initialize an ldsem:
	102	*/
	103	void __init_ldsem(struct ld_semaphore sem, const char name,
	104	struct lock_class_key *key)
	105	{
	106	#ifdef CONFIG_DEBUG_LOCK_ALLOC
	107	/*
	108	* Make sure we are not reinitializing a held semaphore:
	109	*/
	110	debug_check_no_locks_freed((void )sem, sizeof(sem));
	111	lockdep_init_map(&sem->dep_map, name, key, 0);
	112	#endif
	113	sem->count = LDSEM_UNLOCKED;
	114	sem->wait_readers = 0;
	115	raw_spin_lock_init(&sem->wait_lock);
	116	INIT_LIST_HEAD(&sem->read_wait);
	117	INIT_LIST_HEAD(&sem->write_wait);
	118	}
	119
	120	static void __ldsem_wake_readers(struct ld_semaphore *sem)
	121	{
	122	struct ldsem_waiter waiter, next;
	123	struct task_struct *tsk;
	124	long adjust, count;
	125
	126	/* Try to grant read locks to all readers on the read wait list.
	127	* Note the 'active part' of the count is incremented by
	128	* the number of readers before waking any processes up.
	129	*/
	130	adjust = sem->wait_readers * (LDSEM_ACTIVE_BIAS - LDSEM_WAIT_BIAS);
	131	count = ldsem_atomic_update(adjust, sem);
	132	do {
	133	if (count > 0)
	134	break;
	135	if (ldsem_cmpxchg(&count, count - adjust, sem))
	136	return;
	137	} while (1);
	138
	139	list_for_each_entry_safe(waiter, next, &sem->read_wait, list) {
	140	tsk = waiter->task;
	141	smp_mb();
	142	waiter->task = NULL;
	143	wake_up_process(tsk);
	144	put_task_struct(tsk);
	145	}
	146	INIT_LIST_HEAD(&sem->read_wait);
	147	sem->wait_readers = 0;
	148	}
	149
	150	static inline int writer_trylock(struct ld_semaphore *sem)
	151	{
	152	/* only wake this writer if the active part of the count can be
	153	* transitioned from 0 -> 1
	154	*/
	155	long count = ldsem_atomic_update(LDSEM_ACTIVE_BIAS, sem);
	156	do {
	157	if ((count & LDSEM_ACTIVE_MASK) == LDSEM_ACTIVE_BIAS)
	158	return 1;
	159	if (ldsem_cmpxchg(&count, count - LDSEM_ACTIVE_BIAS, sem))
	160	return 0;
	161	} while (1);
162	}
163
164	static void __ldsem_wake_writer(struct ld_semaphore *sem)
165	{
166	struct ldsem_waiter *waiter;
167
168	waiter = list_entry(sem->write_wait.next, struct ldsem_waiter, list);
169	wake_up_process(waiter->task);
170	}
171
172	/*
173	* handle the lock release when processes blocked on it that can now run
174	* - if we come here from up_xxxx(), then:
175	* - the 'active part' of count (&0x0000ffff) reached 0 (but may have changed)
176	* - the 'waiting part' of count (&0xffff0000) is -ve (and will still be so)
177	* - the spinlock must be held by the caller
178	* - woken process blocks are discarded from the list after having task zeroed
179	*/
180	static void __ldsem_wake(struct ld_semaphore *sem)
181	{
182	if (!list_empty(&sem->write_wait))
183	__ldsem_wake_writer(sem);
184	else if (!list_empty(&sem->read_wait))
185	__ldsem_wake_readers(sem);
186	}
187
188	static void ldsem_wake(struct ld_semaphore *sem)
189	{
190	unsigned long flags;
191
192	raw_spin_lock_irqsave(&sem->wait_lock, flags);
193	__ldsem_wake(sem);
194	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
195	}
196
197	/*
198	* wait for the read lock to be granted
199	*/
200	static struct ld_semaphore __sched *
201	down_read_failed(struct ld_semaphore *sem, long count, long timeout)
202	{
203	struct ldsem_waiter waiter;
4898e640 PH	204	long adjust = -LDSEM_ACTIVE_BIAS + LDSEM_WAIT_BIAS;
	205
	206	/* set up my own style of waitqueue */
	207	raw_spin_lock_irq(&sem->wait_lock);
	208
	209	/* Try to reverse the lock attempt but if the count has changed
	210	* so that reversing fails, check if there are are no waiters,
	211	* and early-out if not */
	212	do {
	213	if (ldsem_cmpxchg(&count, count + adjust, sem))
	214	break;
	215	if (count > 0) {
	216	raw_spin_unlock_irq(&sem->wait_lock);
	217	return sem;
	218	}
	219	} while (1);
	220
	221	list_add_tail(&waiter.list, &sem->read_wait);
	222	sem->wait_readers++;
	223
5376f2e7 DB	224	waiter.task = current;
5376f2e7 DB	225	get_task_struct(current);
4898e640 PH	226
	227	/* if there are no active locks, wake the new lock owner(s) */
	228	if ((count & LDSEM_ACTIVE_MASK) == 0)
	229	__ldsem_wake(sem);
	230
	231	raw_spin_unlock_irq(&sem->wait_lock);
	232
	233	/* wait to be given the lock */
	234	for (;;) {
642fa448	235	set_current_state(TASK_UNINTERRUPTIBLE);
4898e640 PH	236
	237	if (!waiter.task)
	238	break;
	239	if (!timeout)
	240	break;
	241	timeout = schedule_timeout(timeout);
	242	}
	243
642fa448	244	__set_current_state(TASK_RUNNING);
4898e640 PH	245
	246	if (!timeout) {
	247	/* lock timed out but check if this task was just
	248	* granted lock ownership - if so, pretend there
	249	* was no timeout; otherwise, cleanup lock wait */
	250	raw_spin_lock_irq(&sem->wait_lock);
	251	if (waiter.task) {
	252	ldsem_atomic_update(-LDSEM_WAIT_BIAS, sem);
	253	list_del(&waiter.list);
	254	raw_spin_unlock_irq(&sem->wait_lock);
	255	put_task_struct(waiter.task);
	256	return NULL;
	257	}
	258	raw_spin_unlock_irq(&sem->wait_lock);
	259	}
	260
	261	return sem;
	262	}
	263
	264	/*
	265	* wait for the write lock to be granted
	266	*/
	267	static struct ld_semaphore __sched *
	268	down_write_failed(struct ld_semaphore *sem, long count, long timeout)
	269	{
	270	struct ldsem_waiter waiter;
4898e640 PH	271	long adjust = -LDSEM_ACTIVE_BIAS;
	272	int locked = 0;
	273
	274	/* set up my own style of waitqueue */
	275	raw_spin_lock_irq(&sem->wait_lock);
	276
	277	/* Try to reverse the lock attempt but if the count has changed
	278	* so that reversing fails, check if the lock is now owned,
	279	* and early-out if so */
	280	do {
	281	if (ldsem_cmpxchg(&count, count + adjust, sem))
	282	break;
	283	if ((count & LDSEM_ACTIVE_MASK) == LDSEM_ACTIVE_BIAS) {
	284	raw_spin_unlock_irq(&sem->wait_lock);
	285	return sem;
	286	}
	287	} while (1);
	288
	289	list_add_tail(&waiter.list, &sem->write_wait);
	290
5376f2e7	291	waiter.task = current;
4898e640	292
642fa448	293	set_current_state(TASK_UNINTERRUPTIBLE);
4898e640 PH	294	for (;;) {
	295	if (!timeout)
	296	break;
	297	raw_spin_unlock_irq(&sem->wait_lock);
	298	timeout = schedule_timeout(timeout);
	299	raw_spin_lock_irq(&sem->wait_lock);
642fa448	300	set_current_state(TASK_UNINTERRUPTIBLE);
f9ce5ccf GKH	301	locked = writer_trylock(sem);
f9ce5ccf GKH	302	if (locked)
4898e640 PH	303	break;
	304	}
	305
	306	if (!locked)
	307	ldsem_atomic_update(-LDSEM_WAIT_BIAS, sem);
	308	list_del(&waiter.list);
	309	raw_spin_unlock_irq(&sem->wait_lock);
	310
642fa448	311	__set_current_state(TASK_RUNNING);
4898e640 PH	312
	313	/* lock wait may have timed out */
	314	if (!locked)
	315	return NULL;
	316	return sem;
	317	}
	318
	319
	320
fc0285f2	321	static int __ldsem_down_read_nested(struct ld_semaphore *sem,
4898e640 PH	322	int subclass, long timeout)
	323	{
	324	long count;
	325
	326	lockdep_acquire_read(sem, subclass, 0, _RET_IP_);
	327
	328	count = ldsem_atomic_update(LDSEM_READ_BIAS, sem);
	329	if (count <= 0) {
	330	lock_stat(sem, contended);
	331	if (!down_read_failed(sem, count, timeout)) {
	332	lockdep_release(sem, 1, _RET_IP_);
	333	return 0;
	334	}
	335	}
	336	lock_stat(sem, acquired);
	337	return 1;
	338	}
	339
5ef6504e	340	static int __ldsem_down_write_nested(struct ld_semaphore *sem,
4898e640 PH	341	int subclass, long timeout)
	342	{
	343	long count;
	344
	345	lockdep_acquire(sem, subclass, 0, _RET_IP_);
	346
	347	count = ldsem_atomic_update(LDSEM_WRITE_BIAS, sem);
	348	if ((count & LDSEM_ACTIVE_MASK) != LDSEM_ACTIVE_BIAS) {
	349	lock_stat(sem, contended);
	350	if (!down_write_failed(sem, count, timeout)) {
	351	lockdep_release(sem, 1, _RET_IP_);
	352	return 0;
	353	}
	354	}
	355	lock_stat(sem, acquired);
	356	return 1;
	357	}
	358
	359
	360	/*
	361	* lock for reading -- returns 1 if successful, 0 if timed out
	362	*/
	363	int __sched ldsem_down_read(struct ld_semaphore *sem, long timeout)
	364	{
	365	might_sleep();
	366	return __ldsem_down_read_nested(sem, 0, timeout);
	367	}
	368
	369	/*
	370	* trylock for reading -- returns 1 if successful, 0 if contention
	371	*/
	372	int ldsem_down_read_trylock(struct ld_semaphore *sem)
	373	{
	374	long count = sem->count;
	375
	376	while (count >= 0) {
	377	if (ldsem_cmpxchg(&count, count + LDSEM_READ_BIAS, sem)) {
	378	lockdep_acquire_read(sem, 0, 1, _RET_IP_);
	379	lock_stat(sem, acquired);
	380	return 1;
	381	}
	382	}
	383	return 0;
	384	}
	385
	386	/*
	387	* lock for writing -- returns 1 if successful, 0 if timed out
	388	*/
	389	int __sched ldsem_down_write(struct ld_semaphore *sem, long timeout)
	390	{
	391	might_sleep();
	392	return __ldsem_down_write_nested(sem, 0, timeout);
	393	}
	394
	395	/*
	396	* trylock for writing -- returns 1 if successful, 0 if contention
	397	*/
	398	int ldsem_down_write_trylock(struct ld_semaphore *sem)
	399	{
	400	long count = sem->count;
	401
	402	while ((count & LDSEM_ACTIVE_MASK) == 0) {
	403	if (ldsem_cmpxchg(&count, count + LDSEM_WRITE_BIAS, sem)) {
	404	lockdep_acquire(sem, 0, 1, _RET_IP_);
405	lock_stat(sem, acquired);
406	return 1;
407	}
408	}
409	return 0;
410	}
411
412	/*
413	* release a read lock
414	*/
415	void ldsem_up_read(struct ld_semaphore *sem)
416	{
417	long count;
418
419	lockdep_release(sem, 1, _RET_IP_);
420
421	count = ldsem_atomic_update(-LDSEM_READ_BIAS, sem);
422	if (count < 0 && (count & LDSEM_ACTIVE_MASK) == 0)
423	ldsem_wake(sem);
424	}
425
426	/*
427	* release a write lock
428	*/
429	void ldsem_up_write(struct ld_semaphore *sem)
430	{
431	long count;
432
433	lockdep_release(sem, 1, _RET_IP_);
434
435	count = ldsem_atomic_update(-LDSEM_WRITE_BIAS, sem);
436	if (count < 0)
437	ldsem_wake(sem);
438	}
439
440
441	#ifdef CONFIG_DEBUG_LOCK_ALLOC
442
443	int ldsem_down_read_nested(struct ld_semaphore *sem, int subclass, long timeout)
444	{
445	might_sleep();
446	return __ldsem_down_read_nested(sem, subclass, timeout);
447	}
448
449	int ldsem_down_write_nested(struct ld_semaphore *sem, int subclass,
450	long timeout)
451	{
452	might_sleep();
453	return __ldsem_down_write_nested(sem, subclass, timeout);
454	}
455
456	#endif