tty_ldsem.c 11 KB

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