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 */
194void __sched __down_write_nested(struct rw_semaphore *sem, int subclass)
195{
196	struct rwsem_waiter waiter;
197	struct task_struct *tsk;
198	unsigned long flags;
199
200	raw_spin_lock_irqsave(&sem->wait_lock, flags);
201
202	/* set up my own style of waitqueue */
203	tsk = current;
204	waiter.task = tsk;
205	waiter.type = RWSEM_WAITING_FOR_WRITE;
206	list_add_tail(&waiter.list, &sem->wait_list);
207
208	/* wait for someone to release the lock */
209	for (;;) {
210		/*
211		 * That is the key to support write lock stealing: allows the
212		 * task already on CPU to get the lock soon rather than put
213		 * itself into sleep and waiting for system woke it or someone
214		 * else in the head of the wait list up.
215		 */
216		if (sem->count == 0)
217			break;
218		set_task_state(tsk, TASK_UNINTERRUPTIBLE);
219		raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
220		schedule();
221		raw_spin_lock_irqsave(&sem->wait_lock, flags);
222	}
223	/* got the lock */
224	sem->count = -1;
225	list_del(&waiter.list);
226
227	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
228}
229
230void __sched __down_write(struct rw_semaphore *sem)
231{
232	__down_write_nested(sem, 0);
233}
234
235/*
236 * trylock for writing -- returns 1 if successful, 0 if contention
237 */
238int __down_write_trylock(struct rw_semaphore *sem)
239{
240	unsigned long flags;
241	int ret = 0;
242
243	raw_spin_lock_irqsave(&sem->wait_lock, flags);
244
245	if (sem->count == 0) {
246		/* got the lock */
247		sem->count = -1;
248		ret = 1;
249	}
250
251	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
252
253	return ret;
254}
255
256/*
257 * release a read lock on the semaphore
258 */
259void __up_read(struct rw_semaphore *sem)
260{
261	unsigned long flags;
262
263	raw_spin_lock_irqsave(&sem->wait_lock, flags);
264
265	if (--sem->count == 0 && !list_empty(&sem->wait_list))
266		sem = __rwsem_wake_one_writer(sem);
267
268	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
269}
270
271/*
272 * release a write lock on the semaphore
273 */
274void __up_write(struct rw_semaphore *sem)
275{
276	unsigned long flags;
277
278	raw_spin_lock_irqsave(&sem->wait_lock, flags);
279
280	sem->count = 0;
281	if (!list_empty(&sem->wait_list))
282		sem = __rwsem_do_wake(sem, 1);
283
284	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
285}
286
287/*
288 * downgrade a write lock into a read lock
289 * - just wake up any readers at the front of the queue
290 */
291void __downgrade_write(struct rw_semaphore *sem)
292{
293	unsigned long flags;
294
295	raw_spin_lock_irqsave(&sem->wait_lock, flags);
296
297	sem->count = 1;
298	if (!list_empty(&sem->wait_list))
299		sem = __rwsem_do_wake(sem, 0);
300
301	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
302}
303
304