rwsem.c 6.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265
  1. /* rwsem.c: R/W semaphores: contention handling functions
  2. *
  3. * Written by David Howells (dhowells@redhat.com).
  4. * Derived from arch/i386/kernel/semaphore.c
  5. */
  6. #include <linux/rwsem.h>
  7. #include <linux/sched.h>
  8. #include <linux/init.h>
  9. #include <linux/module.h>
  10. /*
  11. * Initialize an rwsem:
  12. */
  13. void __init_rwsem(struct rw_semaphore *sem, const char *name,
  14. struct lock_class_key *key)
  15. {
  16. #ifdef CONFIG_DEBUG_LOCK_ALLOC
  17. /*
  18. * Make sure we are not reinitializing a held semaphore:
  19. */
  20. debug_check_no_locks_freed((void *)sem, sizeof(*sem));
  21. lockdep_init_map(&sem->dep_map, name, key, 0);
  22. #endif
  23. sem->count = RWSEM_UNLOCKED_VALUE;
  24. spin_lock_init(&sem->wait_lock);
  25. INIT_LIST_HEAD(&sem->wait_list);
  26. }
  27. EXPORT_SYMBOL(__init_rwsem);
  28. struct rwsem_waiter {
  29. struct list_head list;
  30. struct task_struct *task;
  31. unsigned int flags;
  32. #define RWSEM_WAITING_FOR_READ 0x00000001
  33. #define RWSEM_WAITING_FOR_WRITE 0x00000002
  34. };
  35. /*
  36. * handle the lock release when processes blocked on it that can now run
  37. * - if we come here from up_xxxx(), then:
  38. * - the 'active part' of count (&0x0000ffff) reached 0 (but may have changed)
  39. * - the 'waiting part' of count (&0xffff0000) is -ve (and will still be so)
  40. * - there must be someone on the queue
  41. * - the spinlock must be held by the caller
  42. * - woken process blocks are discarded from the list after having task zeroed
  43. * - writers are only woken if downgrading is false
  44. */
  45. static inline struct rw_semaphore *
  46. __rwsem_do_wake(struct rw_semaphore *sem, int downgrading)
  47. {
  48. struct rwsem_waiter *waiter;
  49. struct task_struct *tsk;
  50. struct list_head *next;
  51. signed long oldcount, woken, loop;
  52. waiter = list_entry(sem->wait_list.next, struct rwsem_waiter, list);
  53. if (!(waiter->flags & RWSEM_WAITING_FOR_WRITE))
  54. goto readers_only;
  55. if (downgrading)
  56. goto out;
  57. /* There's a writer at the front of the queue - try to grant it the
  58. * write lock. However, we only wake this writer if we can transition
  59. * the active part of the count from 0 -> 1
  60. */
  61. try_again_write:
  62. oldcount = rwsem_atomic_update(RWSEM_ACTIVE_BIAS, sem)
  63. - RWSEM_ACTIVE_BIAS;
  64. if (oldcount & RWSEM_ACTIVE_MASK)
  65. /* Someone grabbed the sem already */
  66. goto undo_write;
  67. /* We must be careful not to touch 'waiter' after we set ->task = NULL.
  68. * It is an allocated on the waiter's stack and may become invalid at
  69. * any time after that point (due to a wakeup from another source).
  70. */
  71. list_del(&waiter->list);
  72. tsk = waiter->task;
  73. smp_mb();
  74. waiter->task = NULL;
  75. wake_up_process(tsk);
  76. put_task_struct(tsk);
  77. goto out;
  78. readers_only:
  79. if (downgrading)
  80. goto wake_readers;
  81. /* if we came through an up_xxxx() call, we only only wake someone up
  82. * if we can transition the active part of the count from 0 -> 1 */
  83. try_again_read:
  84. oldcount = rwsem_atomic_update(RWSEM_ACTIVE_BIAS, sem)
  85. - RWSEM_ACTIVE_BIAS;
  86. if (oldcount & RWSEM_ACTIVE_MASK)
  87. /* Someone grabbed the sem already */
  88. goto undo_read;
  89. wake_readers:
  90. /* Grant an infinite number of read locks to the readers at the front
  91. * of the queue. Note we increment the 'active part' of the count by
  92. * the number of readers before waking any processes up.
  93. */
  94. woken = 0;
  95. do {
  96. woken++;
  97. if (waiter->list.next == &sem->wait_list)
  98. break;
  99. waiter = list_entry(waiter->list.next,
  100. struct rwsem_waiter, list);
  101. } while (waiter->flags & RWSEM_WAITING_FOR_READ);
  102. loop = woken;
  103. woken *= RWSEM_ACTIVE_BIAS - RWSEM_WAITING_BIAS;
  104. if (!downgrading)
  105. /* we'd already done one increment earlier */
  106. woken -= RWSEM_ACTIVE_BIAS;
  107. rwsem_atomic_add(woken, sem);
  108. next = sem->wait_list.next;
  109. for (; loop > 0; loop--) {
  110. waiter = list_entry(next, struct rwsem_waiter, list);
  111. next = waiter->list.next;
  112. tsk = waiter->task;
  113. smp_mb();
  114. waiter->task = NULL;
  115. wake_up_process(tsk);
  116. put_task_struct(tsk);
  117. }
  118. sem->wait_list.next = next;
  119. next->prev = &sem->wait_list;
  120. out:
  121. return sem;
  122. /* undo the change to the active count, but check for a transition
  123. * 1->0 */
  124. undo_write:
  125. if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) & RWSEM_ACTIVE_MASK)
  126. goto out;
  127. goto try_again_write;
  128. undo_read:
  129. if (rwsem_atomic_update(-RWSEM_ACTIVE_BIAS, sem) & RWSEM_ACTIVE_MASK)
  130. goto out;
  131. goto try_again_read;
  132. }
  133. /*
  134. * wait for a lock to be granted
  135. */
  136. static struct rw_semaphore __sched *
  137. rwsem_down_failed_common(struct rw_semaphore *sem,
  138. struct rwsem_waiter *waiter, signed long adjustment)
  139. {
  140. struct task_struct *tsk = current;
  141. signed long count;
  142. set_task_state(tsk, TASK_UNINTERRUPTIBLE);
  143. /* set up my own style of waitqueue */
  144. spin_lock_irq(&sem->wait_lock);
  145. waiter->task = tsk;
  146. get_task_struct(tsk);
  147. list_add_tail(&waiter->list, &sem->wait_list);
  148. /* we're now waiting on the lock, but no longer actively read-locking */
  149. count = rwsem_atomic_update(adjustment, sem);
  150. /* if there are no active locks, wake the front queued process(es) up */
  151. if (!(count & RWSEM_ACTIVE_MASK))
  152. sem = __rwsem_do_wake(sem, 0);
  153. spin_unlock_irq(&sem->wait_lock);
  154. /* wait to be given the lock */
  155. for (;;) {
  156. if (!waiter->task)
  157. break;
  158. schedule();
  159. set_task_state(tsk, TASK_UNINTERRUPTIBLE);
  160. }
  161. tsk->state = TASK_RUNNING;
  162. return sem;
  163. }
  164. /*
  165. * wait for the read lock to be granted
  166. */
  167. asmregparm struct rw_semaphore __sched *
  168. rwsem_down_read_failed(struct rw_semaphore *sem)
  169. {
  170. struct rwsem_waiter waiter;
  171. waiter.flags = RWSEM_WAITING_FOR_READ;
  172. rwsem_down_failed_common(sem, &waiter,
  173. RWSEM_WAITING_BIAS - RWSEM_ACTIVE_BIAS);
  174. return sem;
  175. }
  176. /*
  177. * wait for the write lock to be granted
  178. */
  179. asmregparm struct rw_semaphore __sched *
  180. rwsem_down_write_failed(struct rw_semaphore *sem)
  181. {
  182. struct rwsem_waiter waiter;
  183. waiter.flags = RWSEM_WAITING_FOR_WRITE;
  184. rwsem_down_failed_common(sem, &waiter, -RWSEM_ACTIVE_BIAS);
  185. return sem;
  186. }
  187. /*
  188. * handle waking up a waiter on the semaphore
  189. * - up_read/up_write has decremented the active part of count if we come here
  190. */
  191. asmregparm struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)
  192. {
  193. unsigned long flags;
  194. spin_lock_irqsave(&sem->wait_lock, flags);
  195. /* do nothing if list empty */
  196. if (!list_empty(&sem->wait_list))
  197. sem = __rwsem_do_wake(sem, 0);
  198. spin_unlock_irqrestore(&sem->wait_lock, flags);
  199. return sem;
  200. }
  201. /*
  202. * downgrade a write lock into a read lock
  203. * - caller incremented waiting part of count and discovered it still negative
  204. * - just wake up any readers at the front of the queue
  205. */
  206. asmregparm struct rw_semaphore *rwsem_downgrade_wake(struct rw_semaphore *sem)
  207. {
  208. unsigned long flags;
  209. spin_lock_irqsave(&sem->wait_lock, flags);
  210. /* do nothing if list empty */
  211. if (!list_empty(&sem->wait_list))
  212. sem = __rwsem_do_wake(sem, 1);
  213. spin_unlock_irqrestore(&sem->wait_lock, flags);
  214. return sem;
  215. }
  216. EXPORT_SYMBOL(rwsem_down_read_failed);
  217. EXPORT_SYMBOL(rwsem_down_write_failed);
  218. EXPORT_SYMBOL(rwsem_wake);
  219. EXPORT_SYMBOL(rwsem_downgrade_wake);