]>
git.proxmox.com Git - mirror_ubuntu-zesty-kernel.git/blob - drivers/tty/tty_ldsem.c
4 * The ldisc semaphore is semantically a rw_semaphore but which enforces
5 * an alternate policy, namely:
6 * 1) Supports lock wait timeouts
7 * 2) Write waiter has priority
8 * 3) Downgrading is not supported
10 * Implementation notes:
11 * 1) Upper half of semaphore count is a wait count (differs from rwsem
12 * in that rwsem normalizes the upper half to the wait bias)
13 * 2) Lacks overflow checking
15 * The generic counting was copied and modified from include/asm-generic/rwsem.h
16 * by Paul Mackerras <paulus@samba.org>.
18 * The scheduling policy was copied and modified from lib/rwsem.c
19 * Written by David Howells (dhowells@redhat.com).
21 * This implementation incorporates the write lock stealing work of
22 * Michel Lespinasse <walken@google.com>.
24 * Copyright (C) 2013 Peter Hurley <peter@hurleysoftware.com>
26 * This file may be redistributed under the terms of the GNU General Public
30 #include <linux/list.h>
31 #include <linux/spinlock.h>
32 #include <linux/atomic.h>
33 #include <linux/tty.h>
34 #include <linux/sched.h>
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)
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)
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)
53 #ifdef CONFIG_LOCK_STAT
54 # define lock_stat(_lock, stat) lock_##stat(&(_lock)->dep_map, _RET_IP_)
56 # define lock_stat(_lock, stat) do { } while (0)
60 #if BITS_PER_LONG == 64
61 # define LDSEM_ACTIVE_MASK 0xffffffffL
63 # define LDSEM_ACTIVE_MASK 0x0000ffffL
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)
73 struct list_head list
;
74 struct task_struct
*task
;
77 static inline long ldsem_atomic_update(long delta
, struct ld_semaphore
*sem
)
79 return atomic_long_add_return(delta
, (atomic_long_t
*)&sem
->count
);
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
87 static inline int ldsem_cmpxchg(long *old
, long new, struct ld_semaphore
*sem
)
89 long tmp
= atomic_long_cmpxchg(&sem
->count
, *old
, new);
100 * Initialize an ldsem:
102 void __init_ldsem(struct ld_semaphore
*sem
, const char *name
,
103 struct lock_class_key
*key
)
105 #ifdef CONFIG_DEBUG_LOCK_ALLOC
107 * Make sure we are not reinitializing a held semaphore:
109 debug_check_no_locks_freed((void *)sem
, sizeof(*sem
));
110 lockdep_init_map(&sem
->dep_map
, name
, key
, 0);
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
);
119 static void __ldsem_wake_readers(struct ld_semaphore
*sem
)
121 struct ldsem_waiter
*waiter
, *next
;
122 struct task_struct
*tsk
;
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.
129 adjust
= sem
->wait_readers
* (LDSEM_ACTIVE_BIAS
- LDSEM_WAIT_BIAS
);
130 count
= ldsem_atomic_update(adjust
, sem
);
134 if (ldsem_cmpxchg(&count
, count
- adjust
, sem
))
138 list_for_each_entry_safe(waiter
, next
, &sem
->read_wait
, list
) {
142 wake_up_process(tsk
);
143 put_task_struct(tsk
);
145 INIT_LIST_HEAD(&sem
->read_wait
);
146 sem
->wait_readers
= 0;
149 static inline int writer_trylock(struct ld_semaphore
*sem
)
151 /* only wake this writer if the active part of the count can be
152 * transitioned from 0 -> 1
154 long count
= ldsem_atomic_update(LDSEM_ACTIVE_BIAS
, sem
);
156 if ((count
& LDSEM_ACTIVE_MASK
) == LDSEM_ACTIVE_BIAS
)
158 if (ldsem_cmpxchg(&count
, count
- LDSEM_ACTIVE_BIAS
, sem
))
163 static void __ldsem_wake_writer(struct ld_semaphore
*sem
)
165 struct ldsem_waiter
*waiter
;
167 waiter
= list_entry(sem
->write_wait
.next
, struct ldsem_waiter
, list
);
168 wake_up_process(waiter
->task
);
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
179 static void __ldsem_wake(struct ld_semaphore
*sem
)
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
);
187 static void ldsem_wake(struct ld_semaphore
*sem
)
191 raw_spin_lock_irqsave(&sem
->wait_lock
, flags
);
193 raw_spin_unlock_irqrestore(&sem
->wait_lock
, flags
);
197 * wait for the read lock to be granted
199 static struct ld_semaphore __sched
*
200 down_read_failed(struct ld_semaphore
*sem
, long count
, long timeout
)
202 struct ldsem_waiter waiter
;
203 struct task_struct
*tsk
= current
;
204 long adjust
= -LDSEM_ACTIVE_BIAS
+ LDSEM_WAIT_BIAS
;
206 /* set up my own style of waitqueue */
207 raw_spin_lock_irq(&sem
->wait_lock
);
209 /* Try to reverse the lock attempt but if the count has changed
210 * so that reversing fails, check if there are are no waiters,
211 * and early-out if not */
213 if (ldsem_cmpxchg(&count
, count
+ adjust
, sem
))
216 raw_spin_unlock_irq(&sem
->wait_lock
);
221 list_add_tail(&waiter
.list
, &sem
->read_wait
);
225 get_task_struct(tsk
);
227 /* if there are no active locks, wake the new lock owner(s) */
228 if ((count
& LDSEM_ACTIVE_MASK
) == 0)
231 raw_spin_unlock_irq(&sem
->wait_lock
);
233 /* wait to be given the lock */
235 set_task_state(tsk
, TASK_UNINTERRUPTIBLE
);
241 timeout
= schedule_timeout(timeout
);
244 __set_task_state(tsk
, TASK_RUNNING
);
247 /* lock timed out but check if this task was just
248 * granted lock ownership - if so, pretend there
249 * was no timeout; otherwise, cleanup lock wait */
250 raw_spin_lock_irq(&sem
->wait_lock
);
252 ldsem_atomic_update(-LDSEM_WAIT_BIAS
, sem
);
253 list_del(&waiter
.list
);
254 raw_spin_unlock_irq(&sem
->wait_lock
);
255 put_task_struct(waiter
.task
);
258 raw_spin_unlock_irq(&sem
->wait_lock
);
265 * wait for the write lock to be granted
267 static struct ld_semaphore __sched
*
268 down_write_failed(struct ld_semaphore
*sem
, long count
, long timeout
)
270 struct ldsem_waiter waiter
;
271 struct task_struct
*tsk
= current
;
272 long adjust
= -LDSEM_ACTIVE_BIAS
;
275 /* set up my own style of waitqueue */
276 raw_spin_lock_irq(&sem
->wait_lock
);
278 /* Try to reverse the lock attempt but if the count has changed
279 * so that reversing fails, check if the lock is now owned,
280 * and early-out if so */
282 if (ldsem_cmpxchg(&count
, count
+ adjust
, sem
))
284 if ((count
& LDSEM_ACTIVE_MASK
) == LDSEM_ACTIVE_BIAS
) {
285 raw_spin_unlock_irq(&sem
->wait_lock
);
290 list_add_tail(&waiter
.list
, &sem
->write_wait
);
294 set_task_state(tsk
, TASK_UNINTERRUPTIBLE
);
298 raw_spin_unlock_irq(&sem
->wait_lock
);
299 timeout
= schedule_timeout(timeout
);
300 raw_spin_lock_irq(&sem
->wait_lock
);
301 set_task_state(tsk
, TASK_UNINTERRUPTIBLE
);
302 if ((locked
= writer_trylock(sem
)))
307 ldsem_atomic_update(-LDSEM_WAIT_BIAS
, sem
);
308 list_del(&waiter
.list
);
309 raw_spin_unlock_irq(&sem
->wait_lock
);
311 __set_task_state(tsk
, TASK_RUNNING
);
313 /* lock wait may have timed out */
321 static inline int __ldsem_down_read_nested(struct ld_semaphore
*sem
,
322 int subclass
, long timeout
)
326 lockdep_acquire_read(sem
, subclass
, 0, _RET_IP_
);
328 count
= ldsem_atomic_update(LDSEM_READ_BIAS
, sem
);
330 lock_stat(sem
, contended
);
331 if (!down_read_failed(sem
, count
, timeout
)) {
332 lockdep_release(sem
, 1, _RET_IP_
);
336 lock_stat(sem
, acquired
);
340 static inline int __ldsem_down_write_nested(struct ld_semaphore
*sem
,
341 int subclass
, long timeout
)
345 lockdep_acquire(sem
, subclass
, 0, _RET_IP_
);
347 count
= ldsem_atomic_update(LDSEM_WRITE_BIAS
, sem
);
348 if ((count
& LDSEM_ACTIVE_MASK
) != LDSEM_ACTIVE_BIAS
) {
349 lock_stat(sem
, contended
);
350 if (!down_write_failed(sem
, count
, timeout
)) {
351 lockdep_release(sem
, 1, _RET_IP_
);
355 lock_stat(sem
, acquired
);
361 * lock for reading -- returns 1 if successful, 0 if timed out
363 int __sched
ldsem_down_read(struct ld_semaphore
*sem
, long timeout
)
366 return __ldsem_down_read_nested(sem
, 0, timeout
);
370 * trylock for reading -- returns 1 if successful, 0 if contention
372 int ldsem_down_read_trylock(struct ld_semaphore
*sem
)
374 long count
= sem
->count
;
377 if (ldsem_cmpxchg(&count
, count
+ LDSEM_READ_BIAS
, sem
)) {
378 lockdep_acquire_read(sem
, 0, 1, _RET_IP_
);
379 lock_stat(sem
, acquired
);
387 * lock for writing -- returns 1 if successful, 0 if timed out
389 int __sched
ldsem_down_write(struct ld_semaphore
*sem
, long timeout
)
392 return __ldsem_down_write_nested(sem
, 0, timeout
);
396 * trylock for writing -- returns 1 if successful, 0 if contention
398 int ldsem_down_write_trylock(struct ld_semaphore
*sem
)
400 long count
= sem
->count
;
402 while ((count
& LDSEM_ACTIVE_MASK
) == 0) {
403 if (ldsem_cmpxchg(&count
, count
+ LDSEM_WRITE_BIAS
, sem
)) {
404 lockdep_acquire(sem
, 0, 1, _RET_IP_
);
405 lock_stat(sem
, acquired
);
413 * release a read lock
415 void ldsem_up_read(struct ld_semaphore
*sem
)
419 lockdep_release(sem
, 1, _RET_IP_
);
421 count
= ldsem_atomic_update(-LDSEM_READ_BIAS
, sem
);
422 if (count
< 0 && (count
& LDSEM_ACTIVE_MASK
) == 0)
427 * release a write lock
429 void ldsem_up_write(struct ld_semaphore
*sem
)
433 lockdep_release(sem
, 1, _RET_IP_
);
435 count
= ldsem_atomic_update(-LDSEM_WRITE_BIAS
, sem
);
441 #ifdef CONFIG_DEBUG_LOCK_ALLOC
443 int ldsem_down_read_nested(struct ld_semaphore
*sem
, int subclass
, long timeout
)
446 return __ldsem_down_read_nested(sem
, subclass
, timeout
);
449 int ldsem_down_write_nested(struct ld_semaphore
*sem
, int subclass
,
453 return __ldsem_down_write_nested(sem
, subclass
, timeout
);