]>
git.proxmox.com Git - mirror_ubuntu-hirsute-kernel.git/blob - lib/rwsem.c
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
)
148 long oldcount
, adjustment
;
150 adjustment
= RWSEM_ACTIVE_WRITE_BIAS
;
151 if (list_is_singular(&sem
->wait_list
))
152 adjustment
-= RWSEM_WAITING_BIAS
;
155 oldcount
= rwsem_atomic_update(adjustment
, sem
) - adjustment
;
156 if (!(oldcount
& RWSEM_ACTIVE_MASK
))
158 /* some one grabbed the sem already */
159 if (rwsem_atomic_update(-adjustment
, sem
) & RWSEM_ACTIVE_MASK
)
161 goto try_again_write
;
165 * wait for the read lock to be granted
167 struct rw_semaphore __sched
*rwsem_down_read_failed(struct rw_semaphore
*sem
)
169 signed long adjustment
= -RWSEM_ACTIVE_READ_BIAS
;
170 struct rwsem_waiter waiter
;
171 struct task_struct
*tsk
= current
;
174 /* set up my own style of waitqueue */
176 waiter
.type
= RWSEM_WAITING_FOR_READ
;
177 get_task_struct(tsk
);
179 raw_spin_lock_irq(&sem
->wait_lock
);
180 if (list_empty(&sem
->wait_list
))
181 adjustment
+= RWSEM_WAITING_BIAS
;
182 list_add_tail(&waiter
.list
, &sem
->wait_list
);
184 /* we're now waiting on the lock, but no longer actively locking */
185 count
= rwsem_atomic_update(adjustment
, sem
);
187 /* If there are no active locks, wake the front queued process(es). */
188 if (count
== RWSEM_WAITING_BIAS
)
189 sem
= __rwsem_do_wake(sem
, RWSEM_WAKE_NO_ACTIVE
);
191 raw_spin_unlock_irq(&sem
->wait_lock
);
193 /* wait to be given the lock */
195 set_task_state(tsk
, TASK_UNINTERRUPTIBLE
);
201 tsk
->state
= TASK_RUNNING
;
207 * wait until we successfully acquire the write lock
209 struct rw_semaphore __sched
*rwsem_down_write_failed(struct rw_semaphore
*sem
)
211 signed long adjustment
= -RWSEM_ACTIVE_WRITE_BIAS
;
212 struct rwsem_waiter waiter
;
213 struct task_struct
*tsk
= current
;
216 /* set up my own style of waitqueue */
218 waiter
.type
= RWSEM_WAITING_FOR_WRITE
;
220 raw_spin_lock_irq(&sem
->wait_lock
);
221 if (list_empty(&sem
->wait_list
))
222 adjustment
+= RWSEM_WAITING_BIAS
;
223 list_add_tail(&waiter
.list
, &sem
->wait_list
);
225 /* we're now waiting on the lock, but no longer actively locking */
226 count
= rwsem_atomic_update(adjustment
, sem
);
228 /* If there were already threads queued before us and there are no
229 * active writers, the lock must be read owned; so we try to wake
230 * any read locks that were queued ahead of us. */
231 if (count
> RWSEM_WAITING_BIAS
&&
232 adjustment
== -RWSEM_ACTIVE_WRITE_BIAS
)
233 sem
= __rwsem_do_wake(sem
, RWSEM_WAKE_READ_OWNED
);
235 /* wait until we successfully acquire the lock */
237 set_task_state(tsk
, TASK_UNINTERRUPTIBLE
);
239 if (try_get_writer_sem(sem
))
242 raw_spin_unlock_irq(&sem
->wait_lock
);
244 raw_spin_lock_irq(&sem
->wait_lock
);
247 list_del(&waiter
.list
);
248 raw_spin_unlock_irq(&sem
->wait_lock
);
249 tsk
->state
= TASK_RUNNING
;
255 * handle waking up a waiter on the semaphore
256 * - up_read/up_write has decremented the active part of count if we come here
258 struct rw_semaphore
*rwsem_wake(struct rw_semaphore
*sem
)
262 raw_spin_lock_irqsave(&sem
->wait_lock
, flags
);
264 /* do nothing if list empty */
265 if (!list_empty(&sem
->wait_list
))
266 sem
= __rwsem_do_wake(sem
, RWSEM_WAKE_ANY
);
268 raw_spin_unlock_irqrestore(&sem
->wait_lock
, flags
);
274 * downgrade a write lock into a read lock
275 * - caller incremented waiting part of count and discovered it still negative
276 * - just wake up any readers at the front of the queue
278 struct rw_semaphore
*rwsem_downgrade_wake(struct rw_semaphore
*sem
)
282 raw_spin_lock_irqsave(&sem
->wait_lock
, flags
);
284 /* do nothing if list empty */
285 if (!list_empty(&sem
->wait_list
))
286 sem
= __rwsem_do_wake(sem
, RWSEM_WAKE_READ_OWNED
);
288 raw_spin_unlock_irqrestore(&sem
->wait_lock
, flags
);
293 EXPORT_SYMBOL(rwsem_down_read_failed
);
294 EXPORT_SYMBOL(rwsem_down_write_failed
);
295 EXPORT_SYMBOL(rwsem_wake
);
296 EXPORT_SYMBOL(rwsem_downgrade_wake
);