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
12 enum rwsem_waiter_type {
13 RWSEM_WAITING_FOR_WRITE,
14 RWSEM_WAITING_FOR_READ
15 };
16
17 struct rwsem_waiter {
18 struct list_head list;
19 struct task_struct *task;
20 enum rwsem_waiter_type type;
21 };
22
rwsem_is_locked(struct rw_semaphore * sem)23 int 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 }
34 EXPORT_SYMBOL(rwsem_is_locked);
35
36 /*
37 * initialise the semaphore
38 */
__init_rwsem(struct rw_semaphore * sem,const char * name,struct lock_class_key * key)39 void __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 }
53 EXPORT_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 */
64 static inline struct rw_semaphore *
__rwsem_do_wake(struct rw_semaphore * sem,int wakewrite)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 */
114 static inline struct rw_semaphore *
__rwsem_wake_one_writer(struct rw_semaphore * sem)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 */
__down_read(struct rw_semaphore * sem)128 void __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 */
__down_read_trylock(struct rw_semaphore * sem)172 int __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 */
__down_write_common(struct rw_semaphore * sem,int state)194 int __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
234 out_nolock:
235 list_del(&waiter.list);
236 if (!list_empty(&sem->wait_list) && sem->count >= 0)
237 __rwsem_do_wake(sem, 0);
238 raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
239
240 return -EINTR;
241 }
242
__down_write(struct rw_semaphore * sem)243 void __sched __down_write(struct rw_semaphore *sem)
244 {
245 __down_write_common(sem, TASK_UNINTERRUPTIBLE);
246 }
247
__down_write_killable(struct rw_semaphore * sem)248 int __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 */
__down_write_trylock(struct rw_semaphore * sem)256 int __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 */
__up_read(struct rw_semaphore * sem)277 void __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 */
__up_write(struct rw_semaphore * sem)292 void __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 */
__downgrade_write(struct rw_semaphore * sem)309 void __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
322