]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
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 | #include <linux/rwsem.h> | |
7 | #include <linux/sched.h> | |
8 | #include <linux/init.h> | |
9 | #include <linux/module.h> | |
10 | ||
11 | struct rwsem_waiter { | |
12 | struct list_head list; | |
13 | struct task_struct *task; | |
14 | unsigned int flags; | |
15 | #define RWSEM_WAITING_FOR_READ 0x00000001 | |
16 | #define RWSEM_WAITING_FOR_WRITE 0x00000002 | |
17 | }; | |
18 | ||
1da177e4 LT |
19 | /* |
20 | * handle the lock release when processes blocked on it that can now run | |
21 | * - if we come here from up_xxxx(), then: | |
22 | * - the 'active part' of count (&0x0000ffff) reached 0 (but may have changed) | |
23 | * - the 'waiting part' of count (&0xffff0000) is -ve (and will still be so) | |
24 | * - there must be someone on the queue | |
25 | * - the spinlock must be held by the caller | |
26 | * - woken process blocks are discarded from the list after having task zeroed | |
27 | * - writers are only woken if downgrading is false | |
28 | */ | |
29 | static inline struct rw_semaphore * | |
30 | __rwsem_do_wake(struct rw_semaphore *sem, int downgrading) | |
31 | { | |
32 | struct rwsem_waiter *waiter; | |
33 | struct task_struct *tsk; | |
34 | struct list_head *next; | |
35 | signed long oldcount, woken, loop; | |
36 | ||
1da177e4 LT |
37 | if (downgrading) |
38 | goto dont_wake_writers; | |
39 | ||
40 | /* if we came through an up_xxxx() call, we only only wake someone up | |
41 | * if we can transition the active part of the count from 0 -> 1 | |
42 | */ | |
43 | try_again: | |
44 | oldcount = rwsem_atomic_update(RWSEM_ACTIVE_BIAS, sem) | |
45 | - RWSEM_ACTIVE_BIAS; | |
46 | if (oldcount & RWSEM_ACTIVE_MASK) | |
47 | goto undo; | |
48 | ||
49 | waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list); | |
50 | ||
51 | /* try to grant a single write lock if there's a writer at the front | |
52 | * of the queue - note we leave the 'active part' of the count | |
53 | * incremented by 1 and the waiting part incremented by 0x00010000 | |
54 | */ | |
55 | if (!(waiter->flags & RWSEM_WAITING_FOR_WRITE)) | |
56 | goto readers_only; | |
57 | ||
58 | /* We must be careful not to touch 'waiter' after we set ->task = NULL. | |
59 | * It is an allocated on the waiter's stack and may become invalid at | |
60 | * any time after that point (due to a wakeup from another source). | |
61 | */ | |
62 | list_del(&waiter->list); | |
63 | tsk = waiter->task; | |
d59dd462 | 64 | smp_mb(); |
1da177e4 LT |
65 | waiter->task = NULL; |
66 | wake_up_process(tsk); | |
67 | put_task_struct(tsk); | |
68 | goto out; | |
69 | ||
70 | /* don't want to wake any writers */ | |
71 | dont_wake_writers: | |
72 | waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list); | |
73 | if (waiter->flags & RWSEM_WAITING_FOR_WRITE) | |
74 | goto out; | |
75 | ||
76 | /* grant an infinite number of read locks to the readers at the front | |
77 | * of the queue | |
78 | * - note we increment the 'active part' of the count by the number of | |
79 | * readers before waking any processes up | |
80 | */ | |
81 | readers_only: | |
82 | woken = 0; | |
83 | do { | |
84 | woken++; | |
85 | ||
86 | if (waiter->list.next == &sem->wait_list) | |
87 | break; | |
88 | ||
89 | waiter = list_entry(waiter->list.next, | |
90 | struct rwsem_waiter, list); | |
91 | ||
92 | } while (waiter->flags & RWSEM_WAITING_FOR_READ); | |
93 | ||
94 | loop = woken; | |
95 | woken *= RWSEM_ACTIVE_BIAS - RWSEM_WAITING_BIAS; | |
96 | if (!downgrading) | |
97 | /* we'd already done one increment earlier */ | |
98 | woken -= RWSEM_ACTIVE_BIAS; | |
99 | ||
100 | rwsem_atomic_add(woken, sem); | |
101 | ||
102 | next = sem->wait_list.next; | |
103 | for (; loop > 0; loop--) { | |
104 | waiter = list_entry(next, struct rwsem_waiter, list); | |
105 | next = waiter->list.next; | |
106 | tsk = waiter->task; | |
d59dd462 | 107 | smp_mb(); |
1da177e4 LT |
108 | waiter->task = NULL; |
109 | wake_up_process(tsk); | |
110 | put_task_struct(tsk); | |
111 | } | |
112 | ||
113 | sem->wait_list.next = next; | |
114 | next->prev = &sem->wait_list; | |
115 | ||
116 | out: | |
1da177e4 LT |
117 | return sem; |
118 | ||
119 | /* undo the change to count, but check for a transition 1->0 */ | |
120 | undo: | |
121 | if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) != 0) | |
122 | goto out; | |
123 | goto try_again; | |
124 | } | |
125 | ||
126 | /* | |
127 | * wait for a lock to be granted | |
128 | */ | |
129 | static inline struct rw_semaphore * | |
130 | rwsem_down_failed_common(struct rw_semaphore *sem, | |
131 | struct rwsem_waiter *waiter, signed long adjustment) | |
132 | { | |
133 | struct task_struct *tsk = current; | |
134 | signed long count; | |
135 | ||
136 | set_task_state(tsk, TASK_UNINTERRUPTIBLE); | |
137 | ||
138 | /* set up my own style of waitqueue */ | |
139 | spin_lock_irq(&sem->wait_lock); | |
140 | waiter->task = tsk; | |
141 | get_task_struct(tsk); | |
142 | ||
143 | list_add_tail(&waiter->list, &sem->wait_list); | |
144 | ||
145 | /* we're now waiting on the lock, but no longer actively read-locking */ | |
146 | count = rwsem_atomic_update(adjustment, sem); | |
147 | ||
148 | /* if there are no active locks, wake the front queued process(es) up */ | |
149 | if (!(count & RWSEM_ACTIVE_MASK)) | |
150 | sem = __rwsem_do_wake(sem, 0); | |
151 | ||
152 | spin_unlock_irq(&sem->wait_lock); | |
153 | ||
154 | /* wait to be given the lock */ | |
155 | for (;;) { | |
156 | if (!waiter->task) | |
157 | break; | |
158 | schedule(); | |
159 | set_task_state(tsk, TASK_UNINTERRUPTIBLE); | |
160 | } | |
161 | ||
162 | tsk->state = TASK_RUNNING; | |
163 | ||
164 | return sem; | |
165 | } | |
166 | ||
167 | /* | |
168 | * wait for the read lock to be granted | |
169 | */ | |
170 | struct rw_semaphore fastcall __sched * | |
171 | rwsem_down_read_failed(struct rw_semaphore *sem) | |
172 | { | |
173 | struct rwsem_waiter waiter; | |
174 | ||
1da177e4 LT |
175 | waiter.flags = RWSEM_WAITING_FOR_READ; |
176 | rwsem_down_failed_common(sem, &waiter, | |
177 | RWSEM_WAITING_BIAS - RWSEM_ACTIVE_BIAS); | |
1da177e4 LT |
178 | return sem; |
179 | } | |
180 | ||
181 | /* | |
182 | * wait for the write lock to be granted | |
183 | */ | |
184 | struct rw_semaphore fastcall __sched * | |
185 | rwsem_down_write_failed(struct rw_semaphore *sem) | |
186 | { | |
187 | struct rwsem_waiter waiter; | |
188 | ||
1da177e4 LT |
189 | waiter.flags = RWSEM_WAITING_FOR_WRITE; |
190 | rwsem_down_failed_common(sem, &waiter, -RWSEM_ACTIVE_BIAS); | |
191 | ||
1da177e4 LT |
192 | return sem; |
193 | } | |
194 | ||
195 | /* | |
196 | * handle waking up a waiter on the semaphore | |
197 | * - up_read/up_write has decremented the active part of count if we come here | |
198 | */ | |
199 | struct rw_semaphore fastcall *rwsem_wake(struct rw_semaphore *sem) | |
200 | { | |
201 | unsigned long flags; | |
202 | ||
1da177e4 LT |
203 | spin_lock_irqsave(&sem->wait_lock, flags); |
204 | ||
205 | /* do nothing if list empty */ | |
206 | if (!list_empty(&sem->wait_list)) | |
207 | sem = __rwsem_do_wake(sem, 0); | |
208 | ||
209 | spin_unlock_irqrestore(&sem->wait_lock, flags); | |
210 | ||
1da177e4 LT |
211 | return sem; |
212 | } | |
213 | ||
214 | /* | |
215 | * downgrade a write lock into a read lock | |
216 | * - caller incremented waiting part of count and discovered it still negative | |
217 | * - just wake up any readers at the front of the queue | |
218 | */ | |
219 | struct rw_semaphore fastcall *rwsem_downgrade_wake(struct rw_semaphore *sem) | |
220 | { | |
221 | unsigned long flags; | |
222 | ||
1da177e4 LT |
223 | spin_lock_irqsave(&sem->wait_lock, flags); |
224 | ||
225 | /* do nothing if list empty */ | |
226 | if (!list_empty(&sem->wait_list)) | |
227 | sem = __rwsem_do_wake(sem, 1); | |
228 | ||
229 | spin_unlock_irqrestore(&sem->wait_lock, flags); | |
230 | ||
1da177e4 LT |
231 | return sem; |
232 | } | |
233 | ||
234 | EXPORT_SYMBOL(rwsem_down_read_failed); | |
235 | EXPORT_SYMBOL(rwsem_down_write_failed); | |
236 | EXPORT_SYMBOL(rwsem_wake); | |
237 | EXPORT_SYMBOL(rwsem_downgrade_wake); |