tty_ldsem.c 10 KB

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