idle: Remove GENERIC_IDLE_LOOP config switch
[linux-3.10.git] / lib / rwsem-spinlock.c
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 struct 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 int rwsem_is_locked(struct rw_semaphore *sem)
21 {
22         int ret = 1;
23         unsigned long flags;
24
25         if (raw_spin_trylock_irqsave(&sem->wait_lock, flags)) {
26                 ret = (sem->activity != 0);
27                 raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
28         }
29         return ret;
30 }
31 EXPORT_SYMBOL(rwsem_is_locked);
32
33 /*
34  * initialise the semaphore
35  */
36 void __init_rwsem(struct rw_semaphore *sem, const char *name,
37                   struct lock_class_key *key)
38 {
39 #ifdef CONFIG_DEBUG_LOCK_ALLOC
40         /*
41          * Make sure we are not reinitializing a held semaphore:
42          */
43         debug_check_no_locks_freed((void *)sem, sizeof(*sem));
44         lockdep_init_map(&sem->dep_map, name, key, 0);
45 #endif
46         sem->activity = 0;
47         raw_spin_lock_init(&sem->wait_lock);
48         INIT_LIST_HEAD(&sem->wait_list);
49 }
50 EXPORT_SYMBOL(__init_rwsem);
51
52 /*
53  * handle the lock release when processes blocked on it that can now run
54  * - if we come here, then:
55  *   - the 'active count' _reached_ zero
56  *   - the 'waiting count' is non-zero
57  * - the spinlock must be held by the caller
58  * - woken process blocks are discarded from the list after having task zeroed
59  * - writers are only woken if wakewrite is non-zero
60  */
61 static inline struct rw_semaphore *
62 __rwsem_do_wake(struct rw_semaphore *sem, int wakewrite)
63 {
64         struct rwsem_waiter *waiter;
65         struct task_struct *tsk;
66         int woken;
67
68         waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
69
70         if (!wakewrite) {
71                 if (waiter->flags & RWSEM_WAITING_FOR_WRITE)
72                         goto out;
73                 goto dont_wake_writers;
74         }
75
76         /*
77          * as we support write lock stealing, we can't set sem->activity
78          * to -1 here to indicate we get the lock. Instead, we wake it up
79          * to let it go get it again.
80          */
81         if (waiter->flags & RWSEM_WAITING_FOR_WRITE) {
82                 wake_up_process(waiter->task);
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                 smp_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         return sem;
108 }
109
110 /*
111  * wake a single writer
112  */
113 static inline struct rw_semaphore *
114 __rwsem_wake_one_writer(struct rw_semaphore *sem)
115 {
116         struct rwsem_waiter *waiter;
117
118         waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
119         wake_up_process(waiter->task);
120
121         return sem;
122 }
123
124 /*
125  * get a read lock on the semaphore
126  */
127 void __sched __down_read(struct rw_semaphore *sem)
128 {
129         struct rwsem_waiter waiter;
130         struct task_struct *tsk;
131         unsigned long flags;
132
133         raw_spin_lock_irqsave(&sem->wait_lock, flags);
134
135         if (sem->activity >= 0 && list_empty(&sem->wait_list)) {
136                 /* granted */
137                 sem->activity++;
138                 raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
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         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
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;
164  out:
165         ;
166 }
167
168 /*
169  * trylock for reading -- returns 1 if successful, 0 if contention
170  */
171 int __down_read_trylock(struct rw_semaphore *sem)
172 {
173         unsigned long flags;
174         int ret = 0;
175
176
177         raw_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         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
186
187         return ret;
188 }
189
190 /*
191  * get a write lock on the semaphore
192  */
193 void __sched __down_write_nested(struct rw_semaphore *sem, int subclass)
194 {
195         struct rwsem_waiter waiter;
196         struct task_struct *tsk;
197         unsigned long flags;
198
199         raw_spin_lock_irqsave(&sem->wait_lock, flags);
200
201         /* set up my own style of waitqueue */
202         tsk = current;
203         waiter.task = tsk;
204         waiter.flags = RWSEM_WAITING_FOR_WRITE;
205         list_add_tail(&waiter.list, &sem->wait_list);
206
207         /* wait for someone to release the lock */
208         for (;;) {
209                 /*
210                  * That is the key to support write lock stealing: allows the
211                  * task already on CPU to get the lock soon rather than put
212                  * itself into sleep and waiting for system woke it or someone
213                  * else in the head of the wait list up.
214                  */
215                 if (sem->activity == 0)
216                         break;
217                 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
218                 raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
219                 schedule();
220                 raw_spin_lock_irqsave(&sem->wait_lock, flags);
221         }
222         /* got the lock */
223         sem->activity = -1;
224         list_del(&waiter.list);
225
226         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
227 }
228
229 void __sched __down_write(struct rw_semaphore *sem)
230 {
231         __down_write_nested(sem, 0);
232 }
233
234 /*
235  * trylock for writing -- returns 1 if successful, 0 if contention
236  */
237 int __down_write_trylock(struct rw_semaphore *sem)
238 {
239         unsigned long flags;
240         int ret = 0;
241
242         raw_spin_lock_irqsave(&sem->wait_lock, flags);
243
244         if (sem->activity == 0) {
245                 /* got the lock */
246                 sem->activity = -1;
247                 ret = 1;
248         }
249
250         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
251
252         return ret;
253 }
254
255 /*
256  * release a read lock on the semaphore
257  */
258 void __up_read(struct rw_semaphore *sem)
259 {
260         unsigned long flags;
261
262         raw_spin_lock_irqsave(&sem->wait_lock, flags);
263
264         if (--sem->activity == 0 && !list_empty(&sem->wait_list))
265                 sem = __rwsem_wake_one_writer(sem);
266
267         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
268 }
269
270 /*
271  * release a write lock on the semaphore
272  */
273 void __up_write(struct rw_semaphore *sem)
274 {
275         unsigned long flags;
276
277         raw_spin_lock_irqsave(&sem->wait_lock, flags);
278
279         sem->activity = 0;
280         if (!list_empty(&sem->wait_list))
281                 sem = __rwsem_do_wake(sem, 1);
282
283         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
284 }
285
286 /*
287  * downgrade a write lock into a read lock
288  * - just wake up any readers at the front of the queue
289  */
290 void __downgrade_write(struct rw_semaphore *sem)
291 {
292         unsigned long flags;
293
294         raw_spin_lock_irqsave(&sem->wait_lock, flags);
295
296         sem->activity = 1;
297         if (!list_empty(&sem->wait_list))
298                 sem = __rwsem_do_wake(sem, 0);
299
300         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
301 }
302