blob: 9df3ca56db11455f39c436a6fa79f423b7e35b67 [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
Linus Torvalds1da177e2005-04-16 15:20:36 -070020/*
21 * initialise the semaphore
22 */
Ingo Molnar4ea21762006-07-03 00:24:53 -070023void __init_rwsem(struct rw_semaphore *sem, const char *name,
24 struct lock_class_key *key)
Linus Torvalds1da177e2005-04-16 15:20:36 -070025{
Ingo Molnar4ea21762006-07-03 00:24:53 -070026#ifdef CONFIG_DEBUG_LOCK_ALLOC
27 /*
28 * Make sure we are not reinitializing a held semaphore:
29 */
30 debug_check_no_locks_freed((void *)sem, sizeof(*sem));
Peter Zijlstra4dfbb9d2006-10-11 01:45:14 -040031 lockdep_init_map(&sem->dep_map, name, key, 0);
Ingo Molnar4ea21762006-07-03 00:24:53 -070032#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -070033 sem->activity = 0;
34 spin_lock_init(&sem->wait_lock);
35 INIT_LIST_HEAD(&sem->wait_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -070036}
37
38/*
39 * handle the lock release when processes blocked on it that can now run
40 * - if we come here, then:
41 * - the 'active count' _reached_ zero
42 * - the 'waiting count' is non-zero
43 * - the spinlock must be held by the caller
44 * - woken process blocks are discarded from the list after having task zeroed
45 * - writers are only woken if wakewrite is non-zero
46 */
47static inline struct rw_semaphore *
48__rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)
49{
50 struct rwsem_waiter *waiter;
51 struct task_struct *tsk;
52 int woken;
53
Linus Torvalds1da177e2005-04-16 15:20:36 -070054 waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
55
56 if (!wakewrite) {
57 if (waiter->flags & RWSEM_WAITING_FOR_WRITE)
58 goto out;
59 goto dont_wake_writers;
60 }
61
62 /* if we are allowed to wake writers try to grant a single write lock
63 * if there's a writer at the front of the queue
64 * - we leave the 'waiting count' incremented to signify potential
65 * contention
66 */
67 if (waiter->flags & RWSEM_WAITING_FOR_WRITE) {
68 sem->activity = -1;
69 list_del(&waiter->list);
70 tsk = waiter->task;
71 /* Don't touch waiter after ->task has been NULLed */
akpm@osdl.orgd59dd462005-05-01 08:58:47 -070072 smp_mb();
Linus Torvalds1da177e2005-04-16 15:20:36 -070073 waiter->task = NULL;
74 wake_up_process(tsk);
75 put_task_struct(tsk);
76 goto out;
77 }
78
79 /* grant an infinite number of read locks to the front of the queue */
80 dont_wake_writers:
81 woken = 0;
82 while (waiter->flags & RWSEM_WAITING_FOR_READ) {
83 struct list_head *next = waiter->list.next;
84
85 list_del(&waiter->list);
86 tsk = waiter->task;
akpm@osdl.orgd59dd462005-05-01 08:58:47 -070087 smp_mb();
Linus Torvalds1da177e2005-04-16 15:20:36 -070088 waiter->task = NULL;
89 wake_up_process(tsk);
90 put_task_struct(tsk);
91 woken++;
92 if (list_empty(&sem->wait_list))
93 break;
94 waiter = list_entry(next, struct rwsem_waiter, list);
95 }
96
97 sem->activity += woken;
98
99 out:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700100 return sem;
101}
102
103/*
104 * wake a single writer
105 */
106static inline struct rw_semaphore *
107__rwsem_wake_one_writer(struct rw_semaphore *sem)
108{
109 struct rwsem_waiter *waiter;
110 struct task_struct *tsk;
111
112 sem->activity = -1;
113
114 waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
115 list_del(&waiter->list);
116
117 tsk = waiter->task;
akpm@osdl.orgd59dd462005-05-01 08:58:47 -0700118 smp_mb();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700119 waiter->task = NULL;
120 wake_up_process(tsk);
121 put_task_struct(tsk);
122 return sem;
123}
124
125/*
126 * get a read lock on the semaphore
127 */
Harvey Harrison9f741cb2008-02-08 04:19:55 -0800128void __sched __down_read(struct rw_semaphore *sem)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700129{
130 struct rwsem_waiter waiter;
131 struct task_struct *tsk;
132
Linus Torvalds1da177e2005-04-16 15:20:36 -0700133 spin_lock_irq(&sem->wait_lock);
134
135 if (sem->activity >= 0 && list_empty(&sem->wait_list)) {
136 /* granted */
137 sem->activity++;
138 spin_unlock_irq(&sem->wait_lock);
139 goto out;
140 }
141
142 tsk = current;
143 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
144
145 /* set up my own style of waitqueue */
146 waiter.task = tsk;
147 waiter.flags = RWSEM_WAITING_FOR_READ;
148 get_task_struct(tsk);
149
150 list_add_tail(&waiter.list, &sem->wait_list);
151
152 /* we don't need to touch the semaphore struct anymore */
153 spin_unlock_irq(&sem->wait_lock);
154
155 /* wait to be given the lock */
156 for (;;) {
157 if (!waiter.task)
158 break;
159 schedule();
160 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
161 }
162
163 tsk->state = TASK_RUNNING;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700164 out:
Ingo Molnarc4e05112006-07-03 00:24:29 -0700165 ;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700166}
167
168/*
169 * trylock for reading -- returns 1 if successful, 0 if contention
170 */
Harvey Harrison9f741cb2008-02-08 04:19:55 -0800171int __down_read_trylock(struct rw_semaphore *sem)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700172{
173 unsigned long flags;
174 int ret = 0;
175
Linus Torvalds1da177e2005-04-16 15:20:36 -0700176
177 spin_lock_irqsave(&sem->wait_lock, flags);
178
179 if (sem->activity >= 0 && list_empty(&sem->wait_list)) {
180 /* granted */
181 sem->activity++;
182 ret = 1;
183 }
184
185 spin_unlock_irqrestore(&sem->wait_lock, flags);
186
Linus Torvalds1da177e2005-04-16 15:20:36 -0700187 return ret;
188}
189
190/*
191 * get a write lock on the semaphore
192 * - we increment the waiting count anyway to indicate an exclusive lock
193 */
Harvey Harrison9f741cb2008-02-08 04:19:55 -0800194void __sched __down_write_nested(struct rw_semaphore *sem, int subclass)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700195{
196 struct rwsem_waiter waiter;
197 struct task_struct *tsk;
198
Linus Torvalds1da177e2005-04-16 15:20:36 -0700199 spin_lock_irq(&sem->wait_lock);
200
201 if (sem->activity == 0 && list_empty(&sem->wait_list)) {
202 /* granted */
203 sem->activity = -1;
204 spin_unlock_irq(&sem->wait_lock);
205 goto out;
206 }
207
208 tsk = current;
209 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
210
211 /* set up my own style of waitqueue */
212 waiter.task = tsk;
213 waiter.flags = RWSEM_WAITING_FOR_WRITE;
214 get_task_struct(tsk);
215
216 list_add_tail(&waiter.list, &sem->wait_list);
217
218 /* we don't need to touch the semaphore struct anymore */
219 spin_unlock_irq(&sem->wait_lock);
220
221 /* wait to be given the lock */
222 for (;;) {
223 if (!waiter.task)
224 break;
225 schedule();
226 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
227 }
228
229 tsk->state = TASK_RUNNING;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700230 out:
Ingo Molnarc4e05112006-07-03 00:24:29 -0700231 ;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700232}
233
Harvey Harrison9f741cb2008-02-08 04:19:55 -0800234void __sched __down_write(struct rw_semaphore *sem)
Ingo Molnar4ea21762006-07-03 00:24:53 -0700235{
236 __down_write_nested(sem, 0);
237}
238
Linus Torvalds1da177e2005-04-16 15:20:36 -0700239/*
240 * trylock for writing -- returns 1 if successful, 0 if contention
241 */
Harvey Harrison9f741cb2008-02-08 04:19:55 -0800242int __down_write_trylock(struct rw_semaphore *sem)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700243{
244 unsigned long flags;
245 int ret = 0;
246
Linus Torvalds1da177e2005-04-16 15:20:36 -0700247 spin_lock_irqsave(&sem->wait_lock, flags);
248
249 if (sem->activity == 0 && list_empty(&sem->wait_list)) {
250 /* granted */
251 sem->activity = -1;
252 ret = 1;
253 }
254
255 spin_unlock_irqrestore(&sem->wait_lock, flags);
256
Linus Torvalds1da177e2005-04-16 15:20:36 -0700257 return ret;
258}
259
260/*
261 * release a read lock on the semaphore
262 */
Harvey Harrison9f741cb2008-02-08 04:19:55 -0800263void __up_read(struct rw_semaphore *sem)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700264{
265 unsigned long flags;
266
Linus Torvalds1da177e2005-04-16 15:20:36 -0700267 spin_lock_irqsave(&sem->wait_lock, flags);
268
269 if (--sem->activity == 0 && !list_empty(&sem->wait_list))
270 sem = __rwsem_wake_one_writer(sem);
271
272 spin_unlock_irqrestore(&sem->wait_lock, flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700273}
274
275/*
276 * release a write lock on the semaphore
277 */
Harvey Harrison9f741cb2008-02-08 04:19:55 -0800278void __up_write(struct rw_semaphore *sem)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700279{
280 unsigned long flags;
281
Linus Torvalds1da177e2005-04-16 15:20:36 -0700282 spin_lock_irqsave(&sem->wait_lock, flags);
283
284 sem->activity = 0;
285 if (!list_empty(&sem->wait_list))
286 sem = __rwsem_do_wake(sem, 1);
287
288 spin_unlock_irqrestore(&sem->wait_lock, flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700289}
290
291/*
292 * downgrade a write lock into a read lock
293 * - just wake up any readers at the front of the queue
294 */
Harvey Harrison9f741cb2008-02-08 04:19:55 -0800295void __downgrade_write(struct rw_semaphore *sem)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700296{
297 unsigned long flags;
298
Linus Torvalds1da177e2005-04-16 15:20:36 -0700299 spin_lock_irqsave(&sem->wait_lock, flags);
300
301 sem->activity = 1;
302 if (!list_empty(&sem->wait_list))
303 sem = __rwsem_do_wake(sem, 0);
304
305 spin_unlock_irqrestore(&sem->wait_lock, flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700306}
307
Ingo Molnar4ea21762006-07-03 00:24:53 -0700308EXPORT_SYMBOL(__init_rwsem);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700309EXPORT_SYMBOL(__down_read);
310EXPORT_SYMBOL(__down_read_trylock);
Ingo Molnar4ea21762006-07-03 00:24:53 -0700311EXPORT_SYMBOL(__down_write_nested);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700312EXPORT_SYMBOL(__down_write);
313EXPORT_SYMBOL(__down_write_trylock);
314EXPORT_SYMBOL(__up_read);
315EXPORT_SYMBOL(__up_write);
316EXPORT_SYMBOL(__downgrade_write);