rwsem: implement support for write lock stealing on the fastpath
[linux-3.10.git] / lib / rwsem.c
1 /* rwsem.c: R/W semaphores: contention handling functions
2  *
3  * Written by David Howells (dhowells@redhat.com).
4  * Derived from arch/i386/kernel/semaphore.c
5  *
6  * Writer lock-stealing by Alex Shi <alex.shi@intel.com>
7  * and Michel Lespinasse <walken@google.com>
8  */
9 #include <linux/rwsem.h>
10 #include <linux/sched.h>
11 #include <linux/init.h>
12 #include <linux/export.h>
13
14 /*
15  * Initialize an rwsem:
16  */
17 void __init_rwsem(struct rw_semaphore *sem, const char *name,
18                   struct lock_class_key *key)
19 {
20 #ifdef CONFIG_DEBUG_LOCK_ALLOC
21         /*
22          * Make sure we are not reinitializing a held semaphore:
23          */
24         debug_check_no_locks_freed((void *)sem, sizeof(*sem));
25         lockdep_init_map(&sem->dep_map, name, key, 0);
26 #endif
27         sem->count = RWSEM_UNLOCKED_VALUE;
28         raw_spin_lock_init(&sem->wait_lock);
29         INIT_LIST_HEAD(&sem->wait_list);
30 }
31
32 EXPORT_SYMBOL(__init_rwsem);
33
34 enum rwsem_waiter_type {
35         RWSEM_WAITING_FOR_WRITE,
36         RWSEM_WAITING_FOR_READ
37 };
38
39 struct rwsem_waiter {
40         struct list_head list;
41         struct task_struct *task;
42         enum rwsem_waiter_type type;
43 };
44
45 enum rwsem_wake_type {
46         RWSEM_WAKE_ANY,         /* Wake whatever's at head of wait list */
47         RWSEM_WAKE_READERS,     /* Wake readers only */
48         RWSEM_WAKE_READ_OWNED   /* Waker thread holds the read lock */
49 };
50
51 /*
52  * handle the lock release when processes blocked on it that can now run
53  * - if we come here from up_xxxx(), then:
54  *   - the 'active part' of count (&0x0000ffff) reached 0 (but may have changed)
55  *   - the 'waiting part' of count (&0xffff0000) is -ve (and will still be so)
56  * - there must be someone on the queue
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 downgrading is false
60  */
61 static struct rw_semaphore *
62 __rwsem_do_wake(struct rw_semaphore *sem, enum rwsem_wake_type wake_type)
63 {
64         struct rwsem_waiter *waiter;
65         struct task_struct *tsk;
66         struct list_head *next;
67         signed long oldcount, woken, loop, adjustment;
68
69         waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
70         if (waiter->type == RWSEM_WAITING_FOR_WRITE) {
71                 if (wake_type == RWSEM_WAKE_ANY)
72                         /* Wake writer at the front of the queue, but do not
73                          * grant it the lock yet as we want other writers
74                          * to be able to steal it.  Readers, on the other hand,
75                          * will block as they will notice the queued writer.
76                          */
77                         wake_up_process(waiter->task);
78                 goto out;
79         }
80
81         /* Writers might steal the lock before we grant it to the next reader.
82          * We prefer to do the first reader grant before counting readers
83          * so we can bail out early if a writer stole the lock.
84          */
85         adjustment = 0;
86         if (wake_type != RWSEM_WAKE_READ_OWNED) {
87                 adjustment = RWSEM_ACTIVE_READ_BIAS;
88  try_reader_grant:
89                 oldcount = rwsem_atomic_update(adjustment, sem) - adjustment;
90                 if (unlikely(oldcount < RWSEM_WAITING_BIAS)) {
91                         /* A writer stole the lock. Undo our reader grant. */
92                         if (rwsem_atomic_update(-adjustment, sem) &
93                                                 RWSEM_ACTIVE_MASK)
94                                 goto out;
95                         /* Last active locker left. Retry waking readers. */
96                         goto try_reader_grant;
97                 }
98         }
99
100         /* Grant an infinite number of read locks to the readers at the front
101          * of the queue.  Note we increment the 'active part' of the count by
102          * the number of readers before waking any processes up.
103          */
104         woken = 0;
105         do {
106                 woken++;
107
108                 if (waiter->list.next == &sem->wait_list)
109                         break;
110
111                 waiter = list_entry(waiter->list.next,
112                                         struct rwsem_waiter, list);
113
114         } while (waiter->type != RWSEM_WAITING_FOR_WRITE);
115
116         adjustment = woken * RWSEM_ACTIVE_READ_BIAS - adjustment;
117         if (waiter->type != RWSEM_WAITING_FOR_WRITE)
118                 /* hit end of list above */
119                 adjustment -= RWSEM_WAITING_BIAS;
120
121         if (adjustment)
122                 rwsem_atomic_add(adjustment, sem);
123
124         next = sem->wait_list.next;
125         loop = woken;
126         do {
127                 waiter = list_entry(next, struct rwsem_waiter, list);
128                 next = waiter->list.next;
129                 tsk = waiter->task;
130                 smp_mb();
131                 waiter->task = NULL;
132                 wake_up_process(tsk);
133                 put_task_struct(tsk);
134         } while (--loop);
135
136         sem->wait_list.next = next;
137         next->prev = &sem->wait_list;
138
139  out:
140         return sem;
141 }
142
143 /*
144  * wait for the read lock to be granted
145  */
146 struct rw_semaphore __sched *rwsem_down_read_failed(struct rw_semaphore *sem)
147 {
148         signed long adjustment = -RWSEM_ACTIVE_READ_BIAS;
149         struct rwsem_waiter waiter;
150         struct task_struct *tsk = current;
151         signed long count;
152
153         /* set up my own style of waitqueue */
154         waiter.task = tsk;
155         waiter.type = RWSEM_WAITING_FOR_READ;
156         get_task_struct(tsk);
157
158         raw_spin_lock_irq(&sem->wait_lock);
159         if (list_empty(&sem->wait_list))
160                 adjustment += RWSEM_WAITING_BIAS;
161         list_add_tail(&waiter.list, &sem->wait_list);
162
163         /* we're now waiting on the lock, but no longer actively locking */
164         count = rwsem_atomic_update(adjustment, sem);
165
166         /* If there are no active locks, wake the front queued process(es). */
167         if (!(count & RWSEM_ACTIVE_MASK))
168                 sem = __rwsem_do_wake(sem, RWSEM_WAKE_ANY);
169
170         raw_spin_unlock_irq(&sem->wait_lock);
171
172         /* wait to be given the lock */
173         while (true) {
174                 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
175                 if (!waiter.task)
176                         break;
177                 schedule();
178         }
179
180         tsk->state = TASK_RUNNING;
181
182         return sem;
183 }
184
185 /*
186  * wait until we successfully acquire the write lock
187  */
188 struct rw_semaphore __sched *rwsem_down_write_failed(struct rw_semaphore *sem)
189 {
190         signed long adjustment = -RWSEM_ACTIVE_WRITE_BIAS;
191         struct rwsem_waiter waiter;
192         struct task_struct *tsk = current;
193         signed long count;
194
195         /* set up my own style of waitqueue */
196         waiter.task = tsk;
197         waiter.type = RWSEM_WAITING_FOR_WRITE;
198
199         raw_spin_lock_irq(&sem->wait_lock);
200         if (list_empty(&sem->wait_list))
201                 adjustment += RWSEM_WAITING_BIAS;
202         list_add_tail(&waiter.list, &sem->wait_list);
203
204         /* we're now waiting on the lock, but no longer actively locking */
205         count = rwsem_atomic_update(adjustment, sem);
206
207         /* If there were already threads queued before us and there are no
208          * active writers, the lock must be read owned; so we try to wake
209          * any read locks that were queued ahead of us. */
210         if (count > RWSEM_WAITING_BIAS &&
211             adjustment == -RWSEM_ACTIVE_WRITE_BIAS)
212                 sem = __rwsem_do_wake(sem, RWSEM_WAKE_READERS);
213
214         /* wait until we successfully acquire the lock */
215         set_task_state(tsk, TASK_UNINTERRUPTIBLE);
216         while (true) {
217                 if (!(count & RWSEM_ACTIVE_MASK)) {
218                         /* Try acquiring the write lock. */
219                         count = RWSEM_ACTIVE_WRITE_BIAS;
220                         if (!list_is_singular(&sem->wait_list))
221                                 count += RWSEM_WAITING_BIAS;
222                         if (cmpxchg(&sem->count, RWSEM_WAITING_BIAS, count) ==
223                                                         RWSEM_WAITING_BIAS)
224                                 break;
225                 }
226
227                 raw_spin_unlock_irq(&sem->wait_lock);
228
229                 /* Block until there are no active lockers. */
230                 do {
231                         schedule();
232                         set_task_state(tsk, TASK_UNINTERRUPTIBLE);
233                 } while ((count = sem->count) & RWSEM_ACTIVE_MASK);
234
235                 raw_spin_lock_irq(&sem->wait_lock);
236         }
237
238         list_del(&waiter.list);
239         raw_spin_unlock_irq(&sem->wait_lock);
240         tsk->state = TASK_RUNNING;
241
242         return sem;
243 }
244
245 /*
246  * handle waking up a waiter on the semaphore
247  * - up_read/up_write has decremented the active part of count if we come here
248  */
249 struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)
250 {
251         unsigned long flags;
252
253         raw_spin_lock_irqsave(&sem->wait_lock, flags);
254
255         /* do nothing if list empty */
256         if (!list_empty(&sem->wait_list))
257                 sem = __rwsem_do_wake(sem, RWSEM_WAKE_ANY);
258
259         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
260
261         return sem;
262 }
263
264 /*
265  * downgrade a write lock into a read lock
266  * - caller incremented waiting part of count and discovered it still negative
267  * - just wake up any readers at the front of the queue
268  */
269 struct rw_semaphore *rwsem_downgrade_wake(struct rw_semaphore *sem)
270 {
271         unsigned long flags;
272
273         raw_spin_lock_irqsave(&sem->wait_lock, flags);
274
275         /* do nothing if list empty */
276         if (!list_empty(&sem->wait_list))
277                 sem = __rwsem_do_wake(sem, RWSEM_WAKE_READ_OWNED);
278
279         raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
280
281         return sem;
282 }
283
284 EXPORT_SYMBOL(rwsem_down_read_failed);
285 EXPORT_SYMBOL(rwsem_down_write_failed);
286 EXPORT_SYMBOL(rwsem_wake);
287 EXPORT_SYMBOL(rwsem_downgrade_wake);