blob: 21f0db2c97113451de1eac3751cf8f63e5a3541e [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/* 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/module.h>
11
12struct rwsem_waiter {
13 struct list_head list;
14 struct task_struct *task;
15 unsigned int flags;
16#define RWSEM_WAITING_FOR_READ 0x00000001
17#define RWSEM_WAITING_FOR_WRITE 0x00000002
18};
19
20#if RWSEM_DEBUG
21void rwsemtrace(struct rw_semaphore *sem, const char *str)
22{
23 if (sem->debug)
24 printk("[%d] %s({%d,%d})\n",
25 current->pid, str, sem->activity,
26 list_empty(&sem->wait_list) ? 0 : 1);
27}
28#endif
29
30/*
31 * initialise the semaphore
32 */
33void fastcall init_rwsem(struct rw_semaphore *sem)
34{
35 sem->activity = 0;
36 spin_lock_init(&sem->wait_lock);
37 INIT_LIST_HEAD(&sem->wait_list);
38#if RWSEM_DEBUG
39 sem->debug = 0;
40#endif
41}
42
43/*
44 * handle the lock release when processes blocked on it that can now run
45 * - if we come here, then:
46 * - the 'active count' _reached_ zero
47 * - the 'waiting count' is non-zero
48 * - the spinlock must be held by the caller
49 * - woken process blocks are discarded from the list after having task zeroed
50 * - writers are only woken if wakewrite is non-zero
51 */
52static inline struct rw_semaphore *
53__rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)
54{
55 struct rwsem_waiter *waiter;
56 struct task_struct *tsk;
57 int woken;
58
59 rwsemtrace(sem, "Entering __rwsem_do_wake");
60
61 waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
62
63 if (!wakewrite) {
64 if (waiter->flags & RWSEM_WAITING_FOR_WRITE)
65 goto out;
66 goto dont_wake_writers;
67 }
68
69 /* if we are allowed to wake writers try to grant a single write lock
70 * if there's a writer at the front of the queue
71 * - we leave the 'waiting count' incremented to signify potential
72 * contention
73 */
74 if (waiter->flags & RWSEM_WAITING_FOR_WRITE) {
75 sem->activity = -1;
76 list_del(&waiter->list);
77 tsk = waiter->task;
78 /* Don't touch waiter after ->task has been NULLed */
79 mb();
80 waiter->task = NULL;
81 wake_up_process(tsk);
82 put_task_struct(tsk);
83 goto out;
84 }
85
86 /* grant an infinite number of read locks to the front of the queue */
87 dont_wake_writers:
88 woken = 0;
89 while (waiter->flags & RWSEM_WAITING_FOR_READ) {
90 struct list_head *next = waiter->list.next;
91
92 list_del(&waiter->list);
93 tsk = waiter->task;
94 mb();
95 waiter->task = NULL;
96 wake_up_process(tsk);
97 put_task_struct(tsk);
98 woken++;
99 if (list_empty(&sem->wait_list))
100 break;
101 waiter = list_entry(next, struct rwsem_waiter, list);
102 }
103
104 sem->activity += woken;
105
106 out:
107 rwsemtrace(sem, "Leaving __rwsem_do_wake");
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 struct task_struct *tsk;
119
120 sem->activity = -1;
121
122 waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
123 list_del(&waiter->list);
124
125 tsk = waiter->task;
126 mb();
127 waiter->task = NULL;
128 wake_up_process(tsk);
129 put_task_struct(tsk);
130 return sem;
131}
132
133/*
134 * get a read lock on the semaphore
135 */
136void fastcall __sched __down_read(struct rw_semaphore *sem)
137{
138 struct rwsem_waiter waiter;
139 struct task_struct *tsk;
140
141 rwsemtrace(sem, "Entering __down_read");
142
143 spin_lock_irq(&sem->wait_lock);
144
145 if (sem->activity >= 0 && list_empty(&sem->wait_list)) {
146 /* granted */
147 sem->activity++;
148 spin_unlock_irq(&sem->wait_lock);
149 goto out;
150 }
151
152 tsk = current;
153 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
154
155 /* set up my own style of waitqueue */
156 waiter.task = tsk;
157 waiter.flags = RWSEM_WAITING_FOR_READ;
158 get_task_struct(tsk);
159
160 list_add_tail(&waiter.list, &sem->wait_list);
161
162 /* we don't need to touch the semaphore struct anymore */
163 spin_unlock_irq(&sem->wait_lock);
164
165 /* wait to be given the lock */
166 for (;;) {
167 if (!waiter.task)
168 break;
169 schedule();
170 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
171 }
172
173 tsk->state = TASK_RUNNING;
174
175 out:
176 rwsemtrace(sem, "Leaving __down_read");
177}
178
179/*
180 * trylock for reading -- returns 1 if successful, 0 if contention
181 */
182int fastcall __down_read_trylock(struct rw_semaphore *sem)
183{
184 unsigned long flags;
185 int ret = 0;
186
187 rwsemtrace(sem, "Entering __down_read_trylock");
188
189 spin_lock_irqsave(&sem->wait_lock, flags);
190
191 if (sem->activity >= 0 && list_empty(&sem->wait_list)) {
192 /* granted */
193 sem->activity++;
194 ret = 1;
195 }
196
197 spin_unlock_irqrestore(&sem->wait_lock, flags);
198
199 rwsemtrace(sem, "Leaving __down_read_trylock");
200 return ret;
201}
202
203/*
204 * get a write lock on the semaphore
205 * - we increment the waiting count anyway to indicate an exclusive lock
206 */
207void fastcall __sched __down_write(struct rw_semaphore *sem)
208{
209 struct rwsem_waiter waiter;
210 struct task_struct *tsk;
211
212 rwsemtrace(sem, "Entering __down_write");
213
214 spin_lock_irq(&sem->wait_lock);
215
216 if (sem->activity == 0 && list_empty(&sem->wait_list)) {
217 /* granted */
218 sem->activity = -1;
219 spin_unlock_irq(&sem->wait_lock);
220 goto out;
221 }
222
223 tsk = current;
224 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
225
226 /* set up my own style of waitqueue */
227 waiter.task = tsk;
228 waiter.flags = RWSEM_WAITING_FOR_WRITE;
229 get_task_struct(tsk);
230
231 list_add_tail(&waiter.list, &sem->wait_list);
232
233 /* we don't need to touch the semaphore struct anymore */
234 spin_unlock_irq(&sem->wait_lock);
235
236 /* wait to be given the lock */
237 for (;;) {
238 if (!waiter.task)
239 break;
240 schedule();
241 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
242 }
243
244 tsk->state = TASK_RUNNING;
245
246 out:
247 rwsemtrace(sem, "Leaving __down_write");
248}
249
250/*
251 * trylock for writing -- returns 1 if successful, 0 if contention
252 */
253int fastcall __down_write_trylock(struct rw_semaphore *sem)
254{
255 unsigned long flags;
256 int ret = 0;
257
258 rwsemtrace(sem, "Entering __down_write_trylock");
259
260 spin_lock_irqsave(&sem->wait_lock, flags);
261
262 if (sem->activity == 0 && list_empty(&sem->wait_list)) {
263 /* granted */
264 sem->activity = -1;
265 ret = 1;
266 }
267
268 spin_unlock_irqrestore(&sem->wait_lock, flags);
269
270 rwsemtrace(sem, "Leaving __down_write_trylock");
271 return ret;
272}
273
274/*
275 * release a read lock on the semaphore
276 */
277void fastcall __up_read(struct rw_semaphore *sem)
278{
279 unsigned long flags;
280
281 rwsemtrace(sem, "Entering __up_read");
282
283 spin_lock_irqsave(&sem->wait_lock, flags);
284
285 if (--sem->activity == 0 && !list_empty(&sem->wait_list))
286 sem = __rwsem_wake_one_writer(sem);
287
288 spin_unlock_irqrestore(&sem->wait_lock, flags);
289
290 rwsemtrace(sem, "Leaving __up_read");
291}
292
293/*
294 * release a write lock on the semaphore
295 */
296void fastcall __up_write(struct rw_semaphore *sem)
297{
298 unsigned long flags;
299
300 rwsemtrace(sem, "Entering __up_write");
301
302 spin_lock_irqsave(&sem->wait_lock, flags);
303
304 sem->activity = 0;
305 if (!list_empty(&sem->wait_list))
306 sem = __rwsem_do_wake(sem, 1);
307
308 spin_unlock_irqrestore(&sem->wait_lock, flags);
309
310 rwsemtrace(sem, "Leaving __up_write");
311}
312
313/*
314 * downgrade a write lock into a read lock
315 * - just wake up any readers at the front of the queue
316 */
317void fastcall __downgrade_write(struct rw_semaphore *sem)
318{
319 unsigned long flags;
320
321 rwsemtrace(sem, "Entering __downgrade_write");
322
323 spin_lock_irqsave(&sem->wait_lock, flags);
324
325 sem->activity = 1;
326 if (!list_empty(&sem->wait_list))
327 sem = __rwsem_do_wake(sem, 0);
328
329 spin_unlock_irqrestore(&sem->wait_lock, flags);
330
331 rwsemtrace(sem, "Leaving __downgrade_write");
332}
333
334EXPORT_SYMBOL(init_rwsem);
335EXPORT_SYMBOL(__down_read);
336EXPORT_SYMBOL(__down_read_trylock);
337EXPORT_SYMBOL(__down_write);
338EXPORT_SYMBOL(__down_write_trylock);
339EXPORT_SYMBOL(__up_read);
340EXPORT_SYMBOL(__up_write);
341EXPORT_SYMBOL(__downgrade_write);
342#if RWSEM_DEBUG
343EXPORT_SYMBOL(rwsemtrace);
344#endif