1 | // SPDX-License-Identifier: GPL-2.0 |
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> |
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> |
33 | #include <linux/sched/debug.h> |
34 | #include <linux/sched/task.h> |
35 | |
36 | |
37 | #if BITS_PER_LONG == 64 |
38 | # define LDSEM_ACTIVE_MASK 0xffffffffL |
39 | #else |
40 | # define LDSEM_ACTIVE_MASK 0x0000ffffL |
41 | #endif |
42 | |
43 | #define LDSEM_UNLOCKED 0L |
44 | #define LDSEM_ACTIVE_BIAS 1L |
45 | #define LDSEM_WAIT_BIAS (-LDSEM_ACTIVE_MASK-1) |
46 | #define LDSEM_READ_BIAS LDSEM_ACTIVE_BIAS |
47 | #define LDSEM_WRITE_BIAS (LDSEM_WAIT_BIAS + LDSEM_ACTIVE_BIAS) |
48 | |
49 | struct ldsem_waiter { |
50 | struct list_head list; |
51 | struct task_struct *task; |
52 | }; |
53 | |
54 | /* |
55 | * Initialize an ldsem: |
56 | */ |
57 | void __init_ldsem(struct ld_semaphore *sem, const char *name, |
58 | struct lock_class_key *key) |
59 | { |
60 | #ifdef CONFIG_DEBUG_LOCK_ALLOC |
61 | /* |
62 | * Make sure we are not reinitializing a held semaphore: |
63 | */ |
64 | debug_check_no_locks_freed(from: (void *)sem, len: sizeof(*sem)); |
65 | lockdep_init_map(lock: &sem->dep_map, name, key, subclass: 0); |
66 | #endif |
67 | atomic_long_set(v: &sem->count, LDSEM_UNLOCKED); |
68 | sem->wait_readers = 0; |
69 | raw_spin_lock_init(&sem->wait_lock); |
70 | INIT_LIST_HEAD(list: &sem->read_wait); |
71 | INIT_LIST_HEAD(list: &sem->write_wait); |
72 | } |
73 | |
74 | static void __ldsem_wake_readers(struct ld_semaphore *sem) |
75 | { |
76 | struct ldsem_waiter *waiter, *next; |
77 | struct task_struct *tsk; |
78 | long adjust, count; |
79 | |
80 | /* |
81 | * Try to grant read locks to all readers on the read wait list. |
82 | * Note the 'active part' of the count is incremented by |
83 | * the number of readers before waking any processes up. |
84 | */ |
85 | adjust = sem->wait_readers * (LDSEM_ACTIVE_BIAS - LDSEM_WAIT_BIAS); |
86 | count = atomic_long_add_return(i: adjust, v: &sem->count); |
87 | do { |
88 | if (count > 0) |
89 | break; |
90 | if (atomic_long_try_cmpxchg(v: &sem->count, old: &count, new: count - adjust)) |
91 | return; |
92 | } while (1); |
93 | |
94 | list_for_each_entry_safe(waiter, next, &sem->read_wait, list) { |
95 | tsk = waiter->task; |
96 | smp_store_release(&waiter->task, NULL); |
97 | wake_up_process(tsk); |
98 | put_task_struct(t: tsk); |
99 | } |
100 | INIT_LIST_HEAD(list: &sem->read_wait); |
101 | sem->wait_readers = 0; |
102 | } |
103 | |
104 | static inline int writer_trylock(struct ld_semaphore *sem) |
105 | { |
106 | /* |
107 | * Only wake this writer if the active part of the count can be |
108 | * transitioned from 0 -> 1 |
109 | */ |
110 | long count = atomic_long_add_return(LDSEM_ACTIVE_BIAS, v: &sem->count); |
111 | do { |
112 | if ((count & LDSEM_ACTIVE_MASK) == LDSEM_ACTIVE_BIAS) |
113 | return 1; |
114 | if (atomic_long_try_cmpxchg(v: &sem->count, old: &count, new: count - LDSEM_ACTIVE_BIAS)) |
115 | return 0; |
116 | } while (1); |
117 | } |
118 | |
119 | static void __ldsem_wake_writer(struct ld_semaphore *sem) |
120 | { |
121 | struct ldsem_waiter *waiter; |
122 | |
123 | waiter = list_entry(sem->write_wait.next, struct ldsem_waiter, list); |
124 | wake_up_process(tsk: waiter->task); |
125 | } |
126 | |
127 | /* |
128 | * handle the lock release when processes blocked on it that can now run |
129 | * - if we come here from up_xxxx(), then: |
130 | * - the 'active part' of count (&0x0000ffff) reached 0 (but may have changed) |
131 | * - the 'waiting part' of count (&0xffff0000) is -ve (and will still be so) |
132 | * - the spinlock must be held by the caller |
133 | * - woken process blocks are discarded from the list after having task zeroed |
134 | */ |
135 | static void __ldsem_wake(struct ld_semaphore *sem) |
136 | { |
137 | if (!list_empty(head: &sem->write_wait)) |
138 | __ldsem_wake_writer(sem); |
139 | else if (!list_empty(head: &sem->read_wait)) |
140 | __ldsem_wake_readers(sem); |
141 | } |
142 | |
143 | static void ldsem_wake(struct ld_semaphore *sem) |
144 | { |
145 | unsigned long flags; |
146 | |
147 | raw_spin_lock_irqsave(&sem->wait_lock, flags); |
148 | __ldsem_wake(sem); |
149 | raw_spin_unlock_irqrestore(&sem->wait_lock, flags); |
150 | } |
151 | |
152 | /* |
153 | * wait for the read lock to be granted |
154 | */ |
155 | static struct ld_semaphore __sched * |
156 | down_read_failed(struct ld_semaphore *sem, long count, long timeout) |
157 | { |
158 | struct ldsem_waiter waiter; |
159 | long adjust = -LDSEM_ACTIVE_BIAS + LDSEM_WAIT_BIAS; |
160 | |
161 | /* set up my own style of waitqueue */ |
162 | raw_spin_lock_irq(&sem->wait_lock); |
163 | |
164 | /* |
165 | * Try to reverse the lock attempt but if the count has changed |
166 | * so that reversing fails, check if there are no waiters, |
167 | * and early-out if not |
168 | */ |
169 | do { |
170 | if (atomic_long_try_cmpxchg(v: &sem->count, old: &count, new: count + adjust)) { |
171 | count += adjust; |
172 | break; |
173 | } |
174 | if (count > 0) { |
175 | raw_spin_unlock_irq(&sem->wait_lock); |
176 | return sem; |
177 | } |
178 | } while (1); |
179 | |
180 | list_add_tail(new: &waiter.list, head: &sem->read_wait); |
181 | sem->wait_readers++; |
182 | |
183 | waiter.task = current; |
184 | get_task_struct(current); |
185 | |
186 | /* if there are no active locks, wake the new lock owner(s) */ |
187 | if ((count & LDSEM_ACTIVE_MASK) == 0) |
188 | __ldsem_wake(sem); |
189 | |
190 | raw_spin_unlock_irq(&sem->wait_lock); |
191 | |
192 | /* wait to be given the lock */ |
193 | for (;;) { |
194 | set_current_state(TASK_UNINTERRUPTIBLE); |
195 | |
196 | if (!smp_load_acquire(&waiter.task)) |
197 | break; |
198 | if (!timeout) |
199 | break; |
200 | timeout = schedule_timeout(timeout); |
201 | } |
202 | |
203 | __set_current_state(TASK_RUNNING); |
204 | |
205 | if (!timeout) { |
206 | /* |
207 | * Lock timed out but check if this task was just |
208 | * granted lock ownership - if so, pretend there |
209 | * was no timeout; otherwise, cleanup lock wait. |
210 | */ |
211 | raw_spin_lock_irq(&sem->wait_lock); |
212 | if (waiter.task) { |
213 | atomic_long_add_return(i: -LDSEM_WAIT_BIAS, v: &sem->count); |
214 | sem->wait_readers--; |
215 | list_del(entry: &waiter.list); |
216 | raw_spin_unlock_irq(&sem->wait_lock); |
217 | put_task_struct(t: waiter.task); |
218 | return NULL; |
219 | } |
220 | raw_spin_unlock_irq(&sem->wait_lock); |
221 | } |
222 | |
223 | return sem; |
224 | } |
225 | |
226 | /* |
227 | * wait for the write lock to be granted |
228 | */ |
229 | static struct ld_semaphore __sched * |
230 | down_write_failed(struct ld_semaphore *sem, long count, long timeout) |
231 | { |
232 | struct ldsem_waiter waiter; |
233 | long adjust = -LDSEM_ACTIVE_BIAS; |
234 | int locked = 0; |
235 | |
236 | /* set up my own style of waitqueue */ |
237 | raw_spin_lock_irq(&sem->wait_lock); |
238 | |
239 | /* |
240 | * Try to reverse the lock attempt but if the count has changed |
241 | * so that reversing fails, check if the lock is now owned, |
242 | * and early-out if so. |
243 | */ |
244 | do { |
245 | if (atomic_long_try_cmpxchg(v: &sem->count, old: &count, new: count + adjust)) |
246 | break; |
247 | if ((count & LDSEM_ACTIVE_MASK) == LDSEM_ACTIVE_BIAS) { |
248 | raw_spin_unlock_irq(&sem->wait_lock); |
249 | return sem; |
250 | } |
251 | } while (1); |
252 | |
253 | list_add_tail(new: &waiter.list, head: &sem->write_wait); |
254 | |
255 | waiter.task = current; |
256 | |
257 | set_current_state(TASK_UNINTERRUPTIBLE); |
258 | for (;;) { |
259 | if (!timeout) |
260 | break; |
261 | raw_spin_unlock_irq(&sem->wait_lock); |
262 | timeout = schedule_timeout(timeout); |
263 | raw_spin_lock_irq(&sem->wait_lock); |
264 | set_current_state(TASK_UNINTERRUPTIBLE); |
265 | locked = writer_trylock(sem); |
266 | if (locked) |
267 | break; |
268 | } |
269 | |
270 | if (!locked) |
271 | atomic_long_add_return(i: -LDSEM_WAIT_BIAS, v: &sem->count); |
272 | list_del(entry: &waiter.list); |
273 | |
274 | /* |
275 | * In case of timeout, wake up every reader who gave the right of way |
276 | * to writer. Prevent separation readers into two groups: |
277 | * one that helds semaphore and another that sleeps. |
278 | * (in case of no contention with a writer) |
279 | */ |
280 | if (!locked && list_empty(head: &sem->write_wait)) |
281 | __ldsem_wake_readers(sem); |
282 | |
283 | raw_spin_unlock_irq(&sem->wait_lock); |
284 | |
285 | __set_current_state(TASK_RUNNING); |
286 | |
287 | /* lock wait may have timed out */ |
288 | if (!locked) |
289 | return NULL; |
290 | return sem; |
291 | } |
292 | |
293 | |
294 | |
295 | static int __ldsem_down_read_nested(struct ld_semaphore *sem, |
296 | int subclass, long timeout) |
297 | { |
298 | long count; |
299 | |
300 | rwsem_acquire_read(&sem->dep_map, subclass, 0, _RET_IP_); |
301 | |
302 | count = atomic_long_add_return(LDSEM_READ_BIAS, v: &sem->count); |
303 | if (count <= 0) { |
304 | lock_contended(lock: &sem->dep_map, _RET_IP_); |
305 | if (!down_read_failed(sem, count, timeout)) { |
306 | rwsem_release(&sem->dep_map, _RET_IP_); |
307 | return 0; |
308 | } |
309 | } |
310 | lock_acquired(lock: &sem->dep_map, _RET_IP_); |
311 | return 1; |
312 | } |
313 | |
314 | static int __ldsem_down_write_nested(struct ld_semaphore *sem, |
315 | int subclass, long timeout) |
316 | { |
317 | long count; |
318 | |
319 | rwsem_acquire(&sem->dep_map, subclass, 0, _RET_IP_); |
320 | |
321 | count = atomic_long_add_return(LDSEM_WRITE_BIAS, v: &sem->count); |
322 | if ((count & LDSEM_ACTIVE_MASK) != LDSEM_ACTIVE_BIAS) { |
323 | lock_contended(lock: &sem->dep_map, _RET_IP_); |
324 | if (!down_write_failed(sem, count, timeout)) { |
325 | rwsem_release(&sem->dep_map, _RET_IP_); |
326 | return 0; |
327 | } |
328 | } |
329 | lock_acquired(lock: &sem->dep_map, _RET_IP_); |
330 | return 1; |
331 | } |
332 | |
333 | |
334 | /* |
335 | * lock for reading -- returns 1 if successful, 0 if timed out |
336 | */ |
337 | int __sched ldsem_down_read(struct ld_semaphore *sem, long timeout) |
338 | { |
339 | might_sleep(); |
340 | return __ldsem_down_read_nested(sem, subclass: 0, timeout); |
341 | } |
342 | |
343 | /* |
344 | * trylock for reading -- returns 1 if successful, 0 if contention |
345 | */ |
346 | int ldsem_down_read_trylock(struct ld_semaphore *sem) |
347 | { |
348 | long count = atomic_long_read(v: &sem->count); |
349 | |
350 | while (count >= 0) { |
351 | if (atomic_long_try_cmpxchg(v: &sem->count, old: &count, new: count + LDSEM_READ_BIAS)) { |
352 | rwsem_acquire_read(&sem->dep_map, 0, 1, _RET_IP_); |
353 | lock_acquired(lock: &sem->dep_map, _RET_IP_); |
354 | return 1; |
355 | } |
356 | } |
357 | return 0; |
358 | } |
359 | |
360 | /* |
361 | * lock for writing -- returns 1 if successful, 0 if timed out |
362 | */ |
363 | int __sched ldsem_down_write(struct ld_semaphore *sem, long timeout) |
364 | { |
365 | might_sleep(); |
366 | return __ldsem_down_write_nested(sem, subclass: 0, timeout); |
367 | } |
368 | |
369 | /* |
370 | * trylock for writing -- returns 1 if successful, 0 if contention |
371 | */ |
372 | int ldsem_down_write_trylock(struct ld_semaphore *sem) |
373 | { |
374 | long count = atomic_long_read(v: &sem->count); |
375 | |
376 | while ((count & LDSEM_ACTIVE_MASK) == 0) { |
377 | if (atomic_long_try_cmpxchg(v: &sem->count, old: &count, new: count + LDSEM_WRITE_BIAS)) { |
378 | rwsem_acquire(&sem->dep_map, 0, 1, _RET_IP_); |
379 | lock_acquired(lock: &sem->dep_map, _RET_IP_); |
380 | return 1; |
381 | } |
382 | } |
383 | return 0; |
384 | } |
385 | |
386 | /* |
387 | * release a read lock |
388 | */ |
389 | void ldsem_up_read(struct ld_semaphore *sem) |
390 | { |
391 | long count; |
392 | |
393 | rwsem_release(&sem->dep_map, _RET_IP_); |
394 | |
395 | count = atomic_long_add_return(i: -LDSEM_READ_BIAS, v: &sem->count); |
396 | if (count < 0 && (count & LDSEM_ACTIVE_MASK) == 0) |
397 | ldsem_wake(sem); |
398 | } |
399 | |
400 | /* |
401 | * release a write lock |
402 | */ |
403 | void ldsem_up_write(struct ld_semaphore *sem) |
404 | { |
405 | long count; |
406 | |
407 | rwsem_release(&sem->dep_map, _RET_IP_); |
408 | |
409 | count = atomic_long_add_return(i: -LDSEM_WRITE_BIAS, v: &sem->count); |
410 | if (count < 0) |
411 | ldsem_wake(sem); |
412 | } |
413 | |
414 | |
415 | #ifdef CONFIG_DEBUG_LOCK_ALLOC |
416 | |
417 | int ldsem_down_read_nested(struct ld_semaphore *sem, int subclass, long timeout) |
418 | { |
419 | might_sleep(); |
420 | return __ldsem_down_read_nested(sem, subclass, timeout); |
421 | } |
422 | |
423 | int ldsem_down_write_nested(struct ld_semaphore *sem, int subclass, |
424 | long timeout) |
425 | { |
426 | might_sleep(); |
427 | return __ldsem_down_write_nested(sem, subclass, timeout); |
428 | } |
429 | |
430 | #endif |
431 | |