1 /* rwsem.c: R/W semaphores: contention handling functions
3 * Written by David Howells (dhowells@redhat.com).
4 * Derived from arch/i386/kernel/semaphore.c
6 * Writer lock-stealing by Alex Shi <alex.shi@intel.com>
8 #include <linux/rwsem.h>
9 #include <linux/sched.h>
10 #include <linux/init.h>
11 #include <linux/export.h>
14 * Initialize an rwsem:
16 void __init_rwsem(struct rw_semaphore *sem, const char *name,
17 struct lock_class_key *key)
19 #ifdef CONFIG_DEBUG_LOCK_ALLOC
21 * Make sure we are not reinitializing a held semaphore:
23 debug_check_no_locks_freed((void *)sem, sizeof(*sem));
24 lockdep_init_map(&sem->dep_map, name, key, 0);
26 sem->count = RWSEM_UNLOCKED_VALUE;
27 raw_spin_lock_init(&sem->wait_lock);
28 INIT_LIST_HEAD(&sem->wait_list);
31 EXPORT_SYMBOL(__init_rwsem);
33 enum rwsem_waiter_type {
34 RWSEM_WAITING_FOR_WRITE,
35 RWSEM_WAITING_FOR_READ
39 struct list_head list;
40 struct task_struct *task;
41 enum rwsem_waiter_type type;
44 /* Wake types for __rwsem_do_wake(). Note that RWSEM_WAKE_NO_ACTIVE and
45 * RWSEM_WAKE_READ_OWNED imply that the spinlock must have been kept held
46 * since the rwsem value was observed.
48 #define RWSEM_WAKE_ANY 0 /* Wake whatever's at head of wait list */
49 #define RWSEM_WAKE_NO_ACTIVE 1 /* rwsem was observed with no active thread */
50 #define RWSEM_WAKE_READ_OWNED 2 /* rwsem was observed to be read owned */
53 * handle the lock release when processes blocked on it that can now run
54 * - if we come here from up_xxxx(), then:
55 * - the 'active part' of count (&0x0000ffff) reached 0 (but may have changed)
56 * - the 'waiting part' of count (&0xffff0000) is -ve (and will still be so)
57 * - there must be someone on the queue
58 * - the spinlock must be held by the caller
59 * - woken process blocks are discarded from the list after having task zeroed
60 * - writers are only woken if downgrading is false
62 static struct rw_semaphore *
63 __rwsem_do_wake(struct rw_semaphore *sem, int wake_type)
65 struct rwsem_waiter *waiter;
66 struct task_struct *tsk;
67 struct list_head *next;
68 signed long woken, loop, adjustment;
70 waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
71 if (waiter->type != RWSEM_WAITING_FOR_WRITE)
74 if (wake_type == RWSEM_WAKE_READ_OWNED)
75 /* Another active reader was observed, so wakeup is not
76 * likely to succeed. Save the atomic op.
80 /* Wake up the writing waiter and let the task grab the sem: */
81 wake_up_process(waiter->task);
85 /* If we come here from up_xxxx(), another thread might have reached
86 * rwsem_down_failed_common() before we acquired the spinlock and
87 * woken up a waiter, making it now active. We prefer to check for
88 * this first in order to not spend too much time with the spinlock
89 * held if we're not going to be able to wake up readers in the end.
91 * Note that we do not need to update the rwsem count: any writer
92 * trying to acquire rwsem will run rwsem_down_write_failed() due
93 * to the waiting threads and block trying to acquire the spinlock.
95 * We use a dummy atomic update in order to acquire the cache line
96 * exclusively since we expect to succeed and run the final rwsem
97 * count adjustment pretty soon.
99 if (wake_type == RWSEM_WAKE_ANY &&
100 rwsem_atomic_update(0, sem) < RWSEM_WAITING_BIAS)
101 /* Someone grabbed the sem for write already */
104 /* Grant an infinite number of read locks to the readers at the front
105 * of the queue. Note we increment the 'active part' of the count by
106 * the number of readers before waking any processes up.
112 if (waiter->list.next == &sem->wait_list)
115 waiter = list_entry(waiter->list.next,
116 struct rwsem_waiter, list);
118 } while (waiter->type != RWSEM_WAITING_FOR_WRITE);
120 adjustment = woken * RWSEM_ACTIVE_READ_BIAS;
121 if (waiter->type != RWSEM_WAITING_FOR_WRITE)
122 /* hit end of list above */
123 adjustment -= RWSEM_WAITING_BIAS;
125 rwsem_atomic_add(adjustment, sem);
127 next = sem->wait_list.next;
128 for (loop = woken; loop > 0; loop--) {
129 waiter = list_entry(next, struct rwsem_waiter, list);
130 next = waiter->list.next;
134 wake_up_process(tsk);
135 put_task_struct(tsk);
138 sem->wait_list.next = next;
139 next->prev = &sem->wait_list;
145 /* Try to get write sem, caller holds sem->wait_lock: */
146 static int try_get_writer_sem(struct rw_semaphore *sem,
147 struct rwsem_waiter *waiter)
149 struct rwsem_waiter *fwaiter;
150 long oldcount, adjustment;
152 /* only steal when first waiter is writing */
153 fwaiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
154 if (fwaiter->type != RWSEM_WAITING_FOR_WRITE)
157 adjustment = RWSEM_ACTIVE_WRITE_BIAS;
158 /* Only one waiter in the queue: */
159 if (fwaiter == waiter && waiter->list.next == &sem->wait_list)
160 adjustment -= RWSEM_WAITING_BIAS;
163 oldcount = rwsem_atomic_update(adjustment, sem) - adjustment;
164 if (!(oldcount & RWSEM_ACTIVE_MASK)) {
165 /* No active lock: */
166 struct task_struct *tsk = waiter->task;
168 list_del(&waiter->list);
170 put_task_struct(tsk);
171 tsk->state = TASK_RUNNING;
174 /* some one grabbed the sem already */
175 if (rwsem_atomic_update(-adjustment, sem) & RWSEM_ACTIVE_MASK)
177 goto try_again_write;
181 * wait for a lock to be granted
183 static struct rw_semaphore __sched *
184 rwsem_down_failed_common(struct rw_semaphore *sem,
185 enum rwsem_waiter_type type, signed long adjustment)
187 struct rwsem_waiter waiter;
188 struct task_struct *tsk = current;
191 /* set up my own style of waitqueue */
194 get_task_struct(tsk);
196 raw_spin_lock_irq(&sem->wait_lock);
197 if (list_empty(&sem->wait_list))
198 adjustment += RWSEM_WAITING_BIAS;
199 list_add_tail(&waiter.list, &sem->wait_list);
201 /* we're now waiting on the lock, but no longer actively locking */
202 count = rwsem_atomic_update(adjustment, sem);
204 /* If there are no active locks, wake the front queued process(es) up.
206 * Alternatively, if we're called from a failed down_write(), there
207 * were already threads queued before us and there are no active
208 * writers, the lock must be read owned; so we try to wake any read
209 * locks that were queued ahead of us. */
210 if (count == RWSEM_WAITING_BIAS)
211 sem = __rwsem_do_wake(sem, RWSEM_WAKE_NO_ACTIVE);
212 else if (count > RWSEM_WAITING_BIAS &&
213 adjustment == -RWSEM_ACTIVE_WRITE_BIAS)
214 sem = __rwsem_do_wake(sem, RWSEM_WAKE_READ_OWNED);
216 raw_spin_unlock_irq(&sem->wait_lock);
218 /* wait to be given the lock */
220 set_task_state(tsk, TASK_UNINTERRUPTIBLE);
224 raw_spin_lock_irq(&sem->wait_lock);
225 /* Try to get the writer sem, may steal from the head writer: */
226 if (type == RWSEM_WAITING_FOR_WRITE)
227 if (try_get_writer_sem(sem, &waiter)) {
228 raw_spin_unlock_irq(&sem->wait_lock);
231 raw_spin_unlock_irq(&sem->wait_lock);
235 tsk->state = TASK_RUNNING;
241 * wait for the read lock to be granted
243 struct rw_semaphore __sched *rwsem_down_read_failed(struct rw_semaphore *sem)
245 return rwsem_down_failed_common(sem, RWSEM_WAITING_FOR_READ,
246 -RWSEM_ACTIVE_READ_BIAS);
250 * wait for the write lock to be granted
252 struct rw_semaphore __sched *rwsem_down_write_failed(struct rw_semaphore *sem)
254 return rwsem_down_failed_common(sem, RWSEM_WAITING_FOR_WRITE,
255 -RWSEM_ACTIVE_WRITE_BIAS);
259 * handle waking up a waiter on the semaphore
260 * - up_read/up_write has decremented the active part of count if we come here
262 struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)
266 raw_spin_lock_irqsave(&sem->wait_lock, flags);
268 /* do nothing if list empty */
269 if (!list_empty(&sem->wait_list))
270 sem = __rwsem_do_wake(sem, RWSEM_WAKE_ANY);
272 raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
278 * downgrade a write lock into a read lock
279 * - caller incremented waiting part of count and discovered it still negative
280 * - just wake up any readers at the front of the queue
282 struct rw_semaphore *rwsem_downgrade_wake(struct rw_semaphore *sem)
286 raw_spin_lock_irqsave(&sem->wait_lock, flags);
288 /* do nothing if list empty */
289 if (!list_empty(&sem->wait_list))
290 sem = __rwsem_do_wake(sem, RWSEM_WAKE_READ_OWNED);
292 raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
297 EXPORT_SYMBOL(rwsem_down_read_failed);
298 EXPORT_SYMBOL(rwsem_down_write_failed);
299 EXPORT_SYMBOL(rwsem_wake);
300 EXPORT_SYMBOL(rwsem_downgrade_wake);