1/* rwsem-spinlock.c: R/W semaphores: contention handling functions for
  2 * generic spinlock implementation
  3 *
  4 * Copyright (c) 2001   David Howells (dhowells@redhat.com).
  5 * - Derived partially from idea by Andrea Arcangeli <andrea@suse.de>
  6 * - Derived also from comments by Linus
  7 */
  8#include <linux/rwsem.h>
  9#include <linux/sched.h>
 10#include <linux/export.h>
 11
 12enum rwsem_waiter_type {
 13	RWSEM_WAITING_FOR_WRITE,
 14	RWSEM_WAITING_FOR_READ
 15};
 16
 17struct rwsem_waiter {
 18	struct list_head list;
 19	struct task_struct *task;
 20	enum rwsem_waiter_type type;
 21};
 22
 23int rwsem_is_locked(struct rw_semaphore *sem)
 24{
 25	int ret = 1;
 26	unsigned long flags;
 27
 28	if (raw_spin_trylock_irqsave(&sem->wait_lock, flags)) {
 29		ret = (sem->count != 0);
 30		raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
 31	}
 32	return ret;
 33}
 34EXPORT_SYMBOL(rwsem_is_locked);
 35
 36/*
 37 * initialise the semaphore
 38 */
 39void __init_rwsem(struct rw_semaphore *sem, const char *name,
 40		  struct lock_class_key *key)
 41{
 42#ifdef CONFIG_DEBUG_LOCK_ALLOC
 43	/*
 44	 * Make sure we are not reinitializing a held semaphore:
 45	 */
 46	debug_check_no_locks_freed((void *)sem, sizeof(*sem));
 47	lockdep_init_map(&sem->dep_map, name, key, 0);
 48#endif
 49	sem->count = 0;
 50	raw_spin_lock_init(&sem->wait_lock);
 51	INIT_LIST_HEAD(&sem->wait_list);
 52}
 53EXPORT_SYMBOL(__init_rwsem);
 54
 55/*
 56 * handle the lock release when processes blocked on it that can now run
 57 * - if we come here, then:
 58 *   - the 'active count' _reached_ zero
 59 *   - the 'waiting count' is non-zero
 60 * - the spinlock must be held by the caller
 61 * - woken process blocks are discarded from the list after having task zeroed
 62 * - writers are only woken if wakewrite is non-zero
 63 */
 64static inline struct rw_semaphore *
 65__rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)
 66{
 67	struct rwsem_waiter *waiter;
 68	struct task_struct *tsk;
 69	int woken;
 70
 71	waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
 72
 73	if (waiter->type == RWSEM_WAITING_FOR_WRITE) {
 74		if (wakewrite)
 75			/* Wake up a writer. Note that we do not grant it the
 76			 * lock - it will have to acquire it when it runs. */
 77			wake_up_process(waiter->task);
 78		goto out;
 79	}
 80
 81	/* grant an infinite number of read locks to the front of the queue */
 82	woken = 0;
 83	do {
 84		struct list_head *next = waiter->list.next;
 85
 86		list_del(&waiter->list);
 87		tsk = waiter->task;
 88		/*
 89		 * Make sure we do not wakeup the next reader before
 90		 * setting the nil condition to grant the next reader;
 91		 * otherwise we could miss the wakeup on the other
 92		 * side and end up sleeping again. See the pairing
 93		 * in rwsem_down_read_failed().
 94		 */
 95		smp_mb();
 96		waiter->task = NULL;
 97		wake_up_process(tsk);
 98		put_task_struct(tsk);
 99		woken++;
100		if (next == &sem->wait_list)
101			break;
102		waiter = list_entry(next, struct rwsem_waiter, list);
103	} while (waiter->type != RWSEM_WAITING_FOR_WRITE);
104
105	sem->count += woken;
106
107 out:
108	return sem;
109}
110
111/*
112 * wake a single writer
113 */
114static inline struct rw_semaphore *
115__rwsem_wake_one_writer(struct rw_semaphore *sem)
116{
117	struct rwsem_waiter *waiter;
118
119	waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
120	wake_up_process(waiter->task);
121
122	return sem;
123}
124
125/*
126 * get a read lock on the semaphore
127 */
128void __sched __down_read(struct rw_semaphore *sem)
129{
130	struct rwsem_waiter waiter;
131	struct task_struct *tsk;
132	unsigned long flags;
133
134	raw_spin_lock_irqsave(&sem->wait_lock, flags);
135
136	if (sem->count >= 0 && list_empty(&sem->wait_list)) {
137		/* granted */
138		sem->count++;
139		raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
140		goto out;
141	}
142
143	tsk = current;
144	set_task_state(tsk, TASK_UNINTERRUPTIBLE);
145
146	/* set up my own style of waitqueue */
147	waiter.task = tsk;
148	waiter.type = RWSEM_WAITING_FOR_READ;
149	get_task_struct(tsk);
150
151	list_add_tail(&waiter.list, &sem->wait_list);
152
153	/* we don't need to touch the semaphore struct anymore */
154	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
155
156	/* wait to be given the lock */
157	for (;;) {
158		if (!waiter.task)
159			break;
160		schedule();
161		set_task_state(tsk, TASK_UNINTERRUPTIBLE);
162	}
163
164	__set_task_state(tsk, TASK_RUNNING);
165 out:
166	;
167}
168
169/*
170 * trylock for reading -- returns 1 if successful, 0 if contention
171 */
172int __down_read_trylock(struct rw_semaphore *sem)
173{
174	unsigned long flags;
175	int ret = 0;
176
177
178	raw_spin_lock_irqsave(&sem->wait_lock, flags);
179
180	if (sem->count >= 0 && list_empty(&sem->wait_list)) {
181		/* granted */
182		sem->count++;
183		ret = 1;
184	}
185
186	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
187
188	return ret;
189}
190
191/*
192 * get a write lock on the semaphore
193 */
194int __sched __down_write_common(struct rw_semaphore *sem, int state)
195{
196	struct rwsem_waiter waiter;
197	struct task_struct *tsk;
198	unsigned long flags;
199	int ret = 0;
200
201	raw_spin_lock_irqsave(&sem->wait_lock, flags);
202
203	/* set up my own style of waitqueue */
204	tsk = current;
205	waiter.task = tsk;
206	waiter.type = RWSEM_WAITING_FOR_WRITE;
207	list_add_tail(&waiter.list, &sem->wait_list);
208
209	/* wait for someone to release the lock */
210	for (;;) {
211		/*
212		 * That is the key to support write lock stealing: allows the
213		 * task already on CPU to get the lock soon rather than put
214		 * itself into sleep and waiting for system woke it or someone
215		 * else in the head of the wait list up.
216		 */
217		if (sem->count == 0)
218			break;
219		if (signal_pending_state(state, current))
220			goto out_nolock;
221		set_task_state(tsk, state);
222		raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
223		schedule();
224		raw_spin_lock_irqsave(&sem->wait_lock, flags);
225	}
226	/* got the lock */
227	sem->count = -1;
228	list_del(&waiter.list);
229
230	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
231
232	return ret;
233
234out_nolock:
235	list_del(&waiter.list);
236	if (!list_empty(&sem->wait_list))
237		__rwsem_do_wake(sem, 1);
238	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
239
240	return -EINTR;
241}
242
243void __sched __down_write(struct rw_semaphore *sem)
244{
245	__down_write_common(sem, TASK_UNINTERRUPTIBLE);
246}
247
248int __sched __down_write_killable(struct rw_semaphore *sem)
249{
250	return __down_write_common(sem, TASK_KILLABLE);
251}
252
253/*
254 * trylock for writing -- returns 1 if successful, 0 if contention
255 */
256int __down_write_trylock(struct rw_semaphore *sem)
257{
258	unsigned long flags;
259	int ret = 0;
260
261	raw_spin_lock_irqsave(&sem->wait_lock, flags);
262
263	if (sem->count == 0) {
264		/* got the lock */
265		sem->count = -1;
266		ret = 1;
267	}
268
269	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
270
271	return ret;
272}
273
274/*
275 * release a read lock on the semaphore
276 */
277void __up_read(struct rw_semaphore *sem)
278{
279	unsigned long flags;
280
281	raw_spin_lock_irqsave(&sem->wait_lock, flags);
282
283	if (--sem->count == 0 && !list_empty(&sem->wait_list))
284		sem = __rwsem_wake_one_writer(sem);
285
286	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
287}
288
289/*
290 * release a write lock on the semaphore
291 */
292void __up_write(struct rw_semaphore *sem)
293{
294	unsigned long flags;
295
296	raw_spin_lock_irqsave(&sem->wait_lock, flags);
297
298	sem->count = 0;
299	if (!list_empty(&sem->wait_list))
300		sem = __rwsem_do_wake(sem, 1);
301
302	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
303}
304
305/*
306 * downgrade a write lock into a read lock
307 * - just wake up any readers at the front of the queue
308 */
309void __downgrade_write(struct rw_semaphore *sem)
310{
311	unsigned long flags;
312
313	raw_spin_lock_irqsave(&sem->wait_lock, flags);
314
315	sem->count = 1;
316	if (!list_empty(&sem->wait_list))
317		sem = __rwsem_do_wake(sem, 0);
318
319	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
320}
321