]>
Commit | Line | Data |
---|---|---|
e3b3d0f5 | 1 | // SPDX-License-Identifier: GPL-2.0 |
4898e640 PH |
2 | /* |
3 | * Ldisc rw semaphore | |
4 | * | |
5 | * The ldisc semaphore is semantically a rw_semaphore but which enforces | |
6 | * an alternate policy, namely: | |
7 | * 1) Supports lock wait timeouts | |
8 | * 2) Write waiter has priority | |
9 | * 3) Downgrading is not supported | |
10 | * | |
11 | * Implementation notes: | |
12 | * 1) Upper half of semaphore count is a wait count (differs from rwsem | |
13 | * in that rwsem normalizes the upper half to the wait bias) | |
14 | * 2) Lacks overflow checking | |
15 | * | |
16 | * The generic counting was copied and modified from include/asm-generic/rwsem.h | |
17 | * by Paul Mackerras <paulus@samba.org>. | |
18 | * | |
19 | * The scheduling policy was copied and modified from lib/rwsem.c | |
20 | * Written by David Howells (dhowells@redhat.com). | |
21 | * | |
22 | * This implementation incorporates the write lock stealing work of | |
23 | * Michel Lespinasse <walken@google.com>. | |
24 | * | |
25 | * Copyright (C) 2013 Peter Hurley <peter@hurleysoftware.com> | |
4898e640 PH |
26 | */ |
27 | ||
28 | #include <linux/list.h> | |
29 | #include <linux/spinlock.h> | |
30 | #include <linux/atomic.h> | |
31 | #include <linux/tty.h> | |
32 | #include <linux/sched.h> | |
b17b0153 | 33 | #include <linux/sched/debug.h> |
0881e7bd | 34 | #include <linux/sched/task.h> |
4898e640 PH |
35 | |
36 | ||
37 | #ifdef CONFIG_DEBUG_LOCK_ALLOC | |
38 | # define __acq(l, s, t, r, c, n, i) \ | |
39 | lock_acquire(&(l)->dep_map, s, t, r, c, n, i) | |
40 | # define __rel(l, n, i) \ | |
41 | lock_release(&(l)->dep_map, n, i) | |
fb9edbe9 ON |
42 | #define lockdep_acquire(l, s, t, i) __acq(l, s, t, 0, 1, NULL, i) |
43 | #define lockdep_acquire_nest(l, s, t, n, i) __acq(l, s, t, 0, 1, n, i) | |
44 | #define lockdep_acquire_read(l, s, t, i) __acq(l, s, t, 1, 1, NULL, i) | |
45 | #define lockdep_release(l, n, i) __rel(l, n, i) | |
4898e640 PH |
46 | #else |
47 | # define lockdep_acquire(l, s, t, i) do { } while (0) | |
48 | # define lockdep_acquire_nest(l, s, t, n, i) do { } while (0) | |
49 | # define lockdep_acquire_read(l, s, t, i) do { } while (0) | |
50 | # define lockdep_release(l, n, i) do { } while (0) | |
51 | #endif | |
52 | ||
53 | #ifdef CONFIG_LOCK_STAT | |
54 | # define lock_stat(_lock, stat) lock_##stat(&(_lock)->dep_map, _RET_IP_) | |
55 | #else | |
56 | # define lock_stat(_lock, stat) do { } while (0) | |
57 | #endif | |
58 | ||
59 | ||
60 | #if BITS_PER_LONG == 64 | |
61 | # define LDSEM_ACTIVE_MASK 0xffffffffL | |
62 | #else | |
63 | # define LDSEM_ACTIVE_MASK 0x0000ffffL | |
64 | #endif | |
65 | ||
66 | #define LDSEM_UNLOCKED 0L | |
67 | #define LDSEM_ACTIVE_BIAS 1L | |
68 | #define LDSEM_WAIT_BIAS (-LDSEM_ACTIVE_MASK-1) | |
69 | #define LDSEM_READ_BIAS LDSEM_ACTIVE_BIAS | |
70 | #define LDSEM_WRITE_BIAS (LDSEM_WAIT_BIAS + LDSEM_ACTIVE_BIAS) | |
71 | ||
72 | struct ldsem_waiter { | |
73 | struct list_head list; | |
74 | struct task_struct *task; | |
75 | }; | |
76 | ||
77 | static inline long ldsem_atomic_update(long delta, struct ld_semaphore *sem) | |
78 | { | |
79 | return atomic_long_add_return(delta, (atomic_long_t *)&sem->count); | |
80 | } | |
81 | ||
cf872776 PH |
82 | /* |
83 | * ldsem_cmpxchg() updates @*old with the last-known sem->count value. | |
84 | * Returns 1 if count was successfully changed; @*old will have @new value. | |
85 | * Returns 0 if count was not changed; @*old will have most recent sem->count | |
86 | */ | |
4898e640 PH |
87 | static inline int ldsem_cmpxchg(long *old, long new, struct ld_semaphore *sem) |
88 | { | |
cf872776 PH |
89 | long tmp = atomic_long_cmpxchg(&sem->count, *old, new); |
90 | if (tmp == *old) { | |
91 | *old = new; | |
92 | return 1; | |
93 | } else { | |
94 | *old = tmp; | |
95 | return 0; | |
96 | } | |
4898e640 PH |
97 | } |
98 | ||
99 | /* | |
100 | * Initialize an ldsem: | |
101 | */ | |
102 | void __init_ldsem(struct ld_semaphore *sem, const char *name, | |
103 | struct lock_class_key *key) | |
104 | { | |
105 | #ifdef CONFIG_DEBUG_LOCK_ALLOC | |
106 | /* | |
107 | * Make sure we are not reinitializing a held semaphore: | |
108 | */ | |
109 | debug_check_no_locks_freed((void *)sem, sizeof(*sem)); | |
110 | lockdep_init_map(&sem->dep_map, name, key, 0); | |
111 | #endif | |
112 | sem->count = LDSEM_UNLOCKED; | |
113 | sem->wait_readers = 0; | |
114 | raw_spin_lock_init(&sem->wait_lock); | |
115 | INIT_LIST_HEAD(&sem->read_wait); | |
116 | INIT_LIST_HEAD(&sem->write_wait); | |
117 | } | |
118 | ||
119 | static void __ldsem_wake_readers(struct ld_semaphore *sem) | |
120 | { | |
121 | struct ldsem_waiter *waiter, *next; | |
122 | struct task_struct *tsk; | |
123 | long adjust, count; | |
124 | ||
125 | /* Try to grant read locks to all readers on the read wait list. | |
126 | * Note the 'active part' of the count is incremented by | |
127 | * the number of readers before waking any processes up. | |
128 | */ | |
129 | adjust = sem->wait_readers * (LDSEM_ACTIVE_BIAS - LDSEM_WAIT_BIAS); | |
130 | count = ldsem_atomic_update(adjust, sem); | |
131 | do { | |
132 | if (count > 0) | |
133 | break; | |
134 | if (ldsem_cmpxchg(&count, count - adjust, sem)) | |
135 | return; | |
136 | } while (1); | |
137 | ||
138 | list_for_each_entry_safe(waiter, next, &sem->read_wait, list) { | |
139 | tsk = waiter->task; | |
140 | smp_mb(); | |
141 | waiter->task = NULL; | |
142 | wake_up_process(tsk); | |
143 | put_task_struct(tsk); | |
144 | } | |
145 | INIT_LIST_HEAD(&sem->read_wait); | |
146 | sem->wait_readers = 0; | |
147 | } | |
148 | ||
149 | static inline int writer_trylock(struct ld_semaphore *sem) | |
150 | { | |
151 | /* only wake this writer if the active part of the count can be | |
152 | * transitioned from 0 -> 1 | |
153 | */ | |
154 | long count = ldsem_atomic_update(LDSEM_ACTIVE_BIAS, sem); | |
155 | do { | |
156 | if ((count & LDSEM_ACTIVE_MASK) == LDSEM_ACTIVE_BIAS) | |
157 | return 1; | |
158 | if (ldsem_cmpxchg(&count, count - LDSEM_ACTIVE_BIAS, sem)) | |
159 | return 0; | |
160 | } while (1); | |
161 | } | |
162 | ||
163 | static void __ldsem_wake_writer(struct ld_semaphore *sem) | |
164 | { | |
165 | struct ldsem_waiter *waiter; | |
166 | ||
167 | waiter = list_entry(sem->write_wait.next, struct ldsem_waiter, list); | |
168 | wake_up_process(waiter->task); | |
169 | } | |
170 | ||
171 | /* | |
172 | * handle the lock release when processes blocked on it that can now run | |
173 | * - if we come here from up_xxxx(), then: | |
174 | * - the 'active part' of count (&0x0000ffff) reached 0 (but may have changed) | |
175 | * - the 'waiting part' of count (&0xffff0000) is -ve (and will still be so) | |
176 | * - the spinlock must be held by the caller | |
177 | * - woken process blocks are discarded from the list after having task zeroed | |
178 | */ | |
179 | static void __ldsem_wake(struct ld_semaphore *sem) | |
180 | { | |
181 | if (!list_empty(&sem->write_wait)) | |
182 | __ldsem_wake_writer(sem); | |
183 | else if (!list_empty(&sem->read_wait)) | |
184 | __ldsem_wake_readers(sem); | |
185 | } | |
186 | ||
187 | static void ldsem_wake(struct ld_semaphore *sem) | |
188 | { | |
189 | unsigned long flags; | |
190 | ||
191 | raw_spin_lock_irqsave(&sem->wait_lock, flags); | |
192 | __ldsem_wake(sem); | |
193 | raw_spin_unlock_irqrestore(&sem->wait_lock, flags); | |
194 | } | |
195 | ||
196 | /* | |
197 | * wait for the read lock to be granted | |
198 | */ | |
199 | static struct ld_semaphore __sched * | |
200 | down_read_failed(struct ld_semaphore *sem, long count, long timeout) | |
201 | { | |
202 | struct ldsem_waiter waiter; | |
4898e640 PH |
203 | long adjust = -LDSEM_ACTIVE_BIAS + LDSEM_WAIT_BIAS; |
204 | ||
205 | /* set up my own style of waitqueue */ | |
206 | raw_spin_lock_irq(&sem->wait_lock); | |
207 | ||
208 | /* Try to reverse the lock attempt but if the count has changed | |
209 | * so that reversing fails, check if there are are no waiters, | |
210 | * and early-out if not */ | |
211 | do { | |
212 | if (ldsem_cmpxchg(&count, count + adjust, sem)) | |
213 | break; | |
214 | if (count > 0) { | |
215 | raw_spin_unlock_irq(&sem->wait_lock); | |
216 | return sem; | |
217 | } | |
218 | } while (1); | |
219 | ||
220 | list_add_tail(&waiter.list, &sem->read_wait); | |
221 | sem->wait_readers++; | |
222 | ||
5376f2e7 DB |
223 | waiter.task = current; |
224 | get_task_struct(current); | |
4898e640 PH |
225 | |
226 | /* if there are no active locks, wake the new lock owner(s) */ | |
227 | if ((count & LDSEM_ACTIVE_MASK) == 0) | |
228 | __ldsem_wake(sem); | |
229 | ||
230 | raw_spin_unlock_irq(&sem->wait_lock); | |
231 | ||
232 | /* wait to be given the lock */ | |
233 | for (;;) { | |
642fa448 | 234 | set_current_state(TASK_UNINTERRUPTIBLE); |
4898e640 PH |
235 | |
236 | if (!waiter.task) | |
237 | break; | |
238 | if (!timeout) | |
239 | break; | |
240 | timeout = schedule_timeout(timeout); | |
241 | } | |
242 | ||
642fa448 | 243 | __set_current_state(TASK_RUNNING); |
4898e640 PH |
244 | |
245 | if (!timeout) { | |
246 | /* lock timed out but check if this task was just | |
247 | * granted lock ownership - if so, pretend there | |
248 | * was no timeout; otherwise, cleanup lock wait */ | |
249 | raw_spin_lock_irq(&sem->wait_lock); | |
250 | if (waiter.task) { | |
251 | ldsem_atomic_update(-LDSEM_WAIT_BIAS, sem); | |
252 | list_del(&waiter.list); | |
253 | raw_spin_unlock_irq(&sem->wait_lock); | |
254 | put_task_struct(waiter.task); | |
255 | return NULL; | |
256 | } | |
257 | raw_spin_unlock_irq(&sem->wait_lock); | |
258 | } | |
259 | ||
260 | return sem; | |
261 | } | |
262 | ||
263 | /* | |
264 | * wait for the write lock to be granted | |
265 | */ | |
266 | static struct ld_semaphore __sched * | |
267 | down_write_failed(struct ld_semaphore *sem, long count, long timeout) | |
268 | { | |
269 | struct ldsem_waiter waiter; | |
4898e640 PH |
270 | long adjust = -LDSEM_ACTIVE_BIAS; |
271 | int locked = 0; | |
272 | ||
273 | /* set up my own style of waitqueue */ | |
274 | raw_spin_lock_irq(&sem->wait_lock); | |
275 | ||
276 | /* Try to reverse the lock attempt but if the count has changed | |
277 | * so that reversing fails, check if the lock is now owned, | |
278 | * and early-out if so */ | |
279 | do { | |
280 | if (ldsem_cmpxchg(&count, count + adjust, sem)) | |
281 | break; | |
282 | if ((count & LDSEM_ACTIVE_MASK) == LDSEM_ACTIVE_BIAS) { | |
283 | raw_spin_unlock_irq(&sem->wait_lock); | |
284 | return sem; | |
285 | } | |
286 | } while (1); | |
287 | ||
288 | list_add_tail(&waiter.list, &sem->write_wait); | |
289 | ||
5376f2e7 | 290 | waiter.task = current; |
4898e640 | 291 | |
642fa448 | 292 | set_current_state(TASK_UNINTERRUPTIBLE); |
4898e640 PH |
293 | for (;;) { |
294 | if (!timeout) | |
295 | break; | |
296 | raw_spin_unlock_irq(&sem->wait_lock); | |
297 | timeout = schedule_timeout(timeout); | |
298 | raw_spin_lock_irq(&sem->wait_lock); | |
642fa448 | 299 | set_current_state(TASK_UNINTERRUPTIBLE); |
f9ce5ccf GKH |
300 | locked = writer_trylock(sem); |
301 | if (locked) | |
4898e640 PH |
302 | break; |
303 | } | |
304 | ||
305 | if (!locked) | |
306 | ldsem_atomic_update(-LDSEM_WAIT_BIAS, sem); | |
307 | list_del(&waiter.list); | |
308 | raw_spin_unlock_irq(&sem->wait_lock); | |
309 | ||
642fa448 | 310 | __set_current_state(TASK_RUNNING); |
4898e640 PH |
311 | |
312 | /* lock wait may have timed out */ | |
313 | if (!locked) | |
314 | return NULL; | |
315 | return sem; | |
316 | } | |
317 | ||
318 | ||
319 | ||
fc0285f2 | 320 | static int __ldsem_down_read_nested(struct ld_semaphore *sem, |
4898e640 PH |
321 | int subclass, long timeout) |
322 | { | |
323 | long count; | |
324 | ||
325 | lockdep_acquire_read(sem, subclass, 0, _RET_IP_); | |
326 | ||
327 | count = ldsem_atomic_update(LDSEM_READ_BIAS, sem); | |
328 | if (count <= 0) { | |
329 | lock_stat(sem, contended); | |
330 | if (!down_read_failed(sem, count, timeout)) { | |
331 | lockdep_release(sem, 1, _RET_IP_); | |
332 | return 0; | |
333 | } | |
334 | } | |
335 | lock_stat(sem, acquired); | |
336 | return 1; | |
337 | } | |
338 | ||
5ef6504e | 339 | static int __ldsem_down_write_nested(struct ld_semaphore *sem, |
4898e640 PH |
340 | int subclass, long timeout) |
341 | { | |
342 | long count; | |
343 | ||
344 | lockdep_acquire(sem, subclass, 0, _RET_IP_); | |
345 | ||
346 | count = ldsem_atomic_update(LDSEM_WRITE_BIAS, sem); | |
347 | if ((count & LDSEM_ACTIVE_MASK) != LDSEM_ACTIVE_BIAS) { | |
348 | lock_stat(sem, contended); | |
349 | if (!down_write_failed(sem, count, timeout)) { | |
350 | lockdep_release(sem, 1, _RET_IP_); | |
351 | return 0; | |
352 | } | |
353 | } | |
354 | lock_stat(sem, acquired); | |
355 | return 1; | |
356 | } | |
357 | ||
358 | ||
359 | /* | |
360 | * lock for reading -- returns 1 if successful, 0 if timed out | |
361 | */ | |
362 | int __sched ldsem_down_read(struct ld_semaphore *sem, long timeout) | |
363 | { | |
364 | might_sleep(); | |
365 | return __ldsem_down_read_nested(sem, 0, timeout); | |
366 | } | |
367 | ||
368 | /* | |
369 | * trylock for reading -- returns 1 if successful, 0 if contention | |
370 | */ | |
371 | int ldsem_down_read_trylock(struct ld_semaphore *sem) | |
372 | { | |
373 | long count = sem->count; | |
374 | ||
375 | while (count >= 0) { | |
376 | if (ldsem_cmpxchg(&count, count + LDSEM_READ_BIAS, sem)) { | |
377 | lockdep_acquire_read(sem, 0, 1, _RET_IP_); | |
378 | lock_stat(sem, acquired); | |
379 | return 1; | |
380 | } | |
381 | } | |
382 | return 0; | |
383 | } | |
384 | ||
385 | /* | |
386 | * lock for writing -- returns 1 if successful, 0 if timed out | |
387 | */ | |
388 | int __sched ldsem_down_write(struct ld_semaphore *sem, long timeout) | |
389 | { | |
390 | might_sleep(); | |
391 | return __ldsem_down_write_nested(sem, 0, timeout); | |
392 | } | |
393 | ||
394 | /* | |
395 | * trylock for writing -- returns 1 if successful, 0 if contention | |
396 | */ | |
397 | int ldsem_down_write_trylock(struct ld_semaphore *sem) | |
398 | { | |
399 | long count = sem->count; | |
400 | ||
401 | while ((count & LDSEM_ACTIVE_MASK) == 0) { | |
402 | if (ldsem_cmpxchg(&count, count + LDSEM_WRITE_BIAS, sem)) { | |
403 | lockdep_acquire(sem, 0, 1, _RET_IP_); | |
404 | lock_stat(sem, acquired); | |
405 | return 1; | |
406 | } | |
407 | } | |
408 | return 0; | |
409 | } | |
410 | ||
411 | /* | |
412 | * release a read lock | |
413 | */ | |
414 | void ldsem_up_read(struct ld_semaphore *sem) | |
415 | { | |
416 | long count; | |
417 | ||
418 | lockdep_release(sem, 1, _RET_IP_); | |
419 | ||
420 | count = ldsem_atomic_update(-LDSEM_READ_BIAS, sem); | |
421 | if (count < 0 && (count & LDSEM_ACTIVE_MASK) == 0) | |
422 | ldsem_wake(sem); | |
423 | } | |
424 | ||
425 | /* | |
426 | * release a write lock | |
427 | */ | |
428 | void ldsem_up_write(struct ld_semaphore *sem) | |
429 | { | |
430 | long count; | |
431 | ||
432 | lockdep_release(sem, 1, _RET_IP_); | |
433 | ||
434 | count = ldsem_atomic_update(-LDSEM_WRITE_BIAS, sem); | |
435 | if (count < 0) | |
436 | ldsem_wake(sem); | |
437 | } | |
438 | ||
439 | ||
440 | #ifdef CONFIG_DEBUG_LOCK_ALLOC | |
441 | ||
442 | int ldsem_down_read_nested(struct ld_semaphore *sem, int subclass, long timeout) | |
443 | { | |
444 | might_sleep(); | |
445 | return __ldsem_down_read_nested(sem, subclass, timeout); | |
446 | } | |
447 | ||
448 | int ldsem_down_write_nested(struct ld_semaphore *sem, int subclass, | |
449 | long timeout) | |
450 | { | |
451 | might_sleep(); | |
452 | return __ldsem_down_write_nested(sem, subclass, timeout); | |
453 | } | |
454 | ||
455 | #endif |