semaphore-sleepers.c 4.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176
  1. /*
  2. * i386 and x86-64 semaphore implementation.
  3. *
  4. * (C) Copyright 1999 Linus Torvalds
  5. *
  6. * Portions Copyright 1999 Red Hat, Inc.
  7. *
  8. * This program is free software; you can redistribute it and/or
  9. * modify it under the terms of the GNU General Public License
  10. * as published by the Free Software Foundation; either version
  11. * 2 of the License, or (at your option) any later version.
  12. *
  13. * rw semaphores implemented November 1999 by Benjamin LaHaise <bcrl@kvack.org>
  14. */
  15. #include <linux/sched.h>
  16. #include <linux/err.h>
  17. #include <linux/init.h>
  18. #include <asm/semaphore.h>
  19. /*
  20. * Semaphores are implemented using a two-way counter:
  21. * The "count" variable is decremented for each process
  22. * that tries to acquire the semaphore, while the "sleeping"
  23. * variable is a count of such acquires.
  24. *
  25. * Notably, the inline "up()" and "down()" functions can
  26. * efficiently test if they need to do any extra work (up
  27. * needs to do something only if count was negative before
  28. * the increment operation.
  29. *
  30. * "sleeping" and the contention routine ordering is protected
  31. * by the spinlock in the semaphore's waitqueue head.
  32. *
  33. * Note that these functions are only called when there is
  34. * contention on the lock, and as such all this is the
  35. * "non-critical" part of the whole semaphore business. The
  36. * critical part is the inline stuff in <asm/semaphore.h>
  37. * where we want to avoid any extra jumps and calls.
  38. */
  39. /*
  40. * Logic:
  41. * - only on a boundary condition do we need to care. When we go
  42. * from a negative count to a non-negative, we wake people up.
  43. * - when we go from a non-negative count to a negative do we
  44. * (a) synchronize with the "sleeper" count and (b) make sure
  45. * that we're on the wakeup list before we synchronize so that
  46. * we cannot lose wakeup events.
  47. */
  48. fastcall void __up(struct semaphore *sem)
  49. {
  50. wake_up(&sem->wait);
  51. }
  52. fastcall void __sched __down(struct semaphore * sem)
  53. {
  54. struct task_struct *tsk = current;
  55. DECLARE_WAITQUEUE(wait, tsk);
  56. unsigned long flags;
  57. tsk->state = TASK_UNINTERRUPTIBLE;
  58. spin_lock_irqsave(&sem->wait.lock, flags);
  59. add_wait_queue_exclusive_locked(&sem->wait, &wait);
  60. sem->sleepers++;
  61. for (;;) {
  62. int sleepers = sem->sleepers;
  63. /*
  64. * Add "everybody else" into it. They aren't
  65. * playing, because we own the spinlock in
  66. * the wait_queue_head.
  67. */
  68. if (!atomic_add_negative(sleepers - 1, &sem->count)) {
  69. sem->sleepers = 0;
  70. break;
  71. }
  72. sem->sleepers = 1; /* us - see -1 above */
  73. spin_unlock_irqrestore(&sem->wait.lock, flags);
  74. schedule();
  75. spin_lock_irqsave(&sem->wait.lock, flags);
  76. tsk->state = TASK_UNINTERRUPTIBLE;
  77. }
  78. remove_wait_queue_locked(&sem->wait, &wait);
  79. wake_up_locked(&sem->wait);
  80. spin_unlock_irqrestore(&sem->wait.lock, flags);
  81. tsk->state = TASK_RUNNING;
  82. }
  83. fastcall int __sched __down_interruptible(struct semaphore * sem)
  84. {
  85. int retval = 0;
  86. struct task_struct *tsk = current;
  87. DECLARE_WAITQUEUE(wait, tsk);
  88. unsigned long flags;
  89. tsk->state = TASK_INTERRUPTIBLE;
  90. spin_lock_irqsave(&sem->wait.lock, flags);
  91. add_wait_queue_exclusive_locked(&sem->wait, &wait);
  92. sem->sleepers++;
  93. for (;;) {
  94. int sleepers = sem->sleepers;
  95. /*
  96. * With signals pending, this turns into
  97. * the trylock failure case - we won't be
  98. * sleeping, and we* can't get the lock as
  99. * it has contention. Just correct the count
  100. * and exit.
  101. */
  102. if (signal_pending(current)) {
  103. retval = -EINTR;
  104. sem->sleepers = 0;
  105. atomic_add(sleepers, &sem->count);
  106. break;
  107. }
  108. /*
  109. * Add "everybody else" into it. They aren't
  110. * playing, because we own the spinlock in
  111. * wait_queue_head. The "-1" is because we're
  112. * still hoping to get the semaphore.
  113. */
  114. if (!atomic_add_negative(sleepers - 1, &sem->count)) {
  115. sem->sleepers = 0;
  116. break;
  117. }
  118. sem->sleepers = 1; /* us - see -1 above */
  119. spin_unlock_irqrestore(&sem->wait.lock, flags);
  120. schedule();
  121. spin_lock_irqsave(&sem->wait.lock, flags);
  122. tsk->state = TASK_INTERRUPTIBLE;
  123. }
  124. remove_wait_queue_locked(&sem->wait, &wait);
  125. wake_up_locked(&sem->wait);
  126. spin_unlock_irqrestore(&sem->wait.lock, flags);
  127. tsk->state = TASK_RUNNING;
  128. return retval;
  129. }
  130. /*
  131. * Trylock failed - make sure we correct for
  132. * having decremented the count.
  133. *
  134. * We could have done the trylock with a
  135. * single "cmpxchg" without failure cases,
  136. * but then it wouldn't work on a 386.
  137. */
  138. fastcall int __down_trylock(struct semaphore * sem)
  139. {
  140. int sleepers;
  141. unsigned long flags;
  142. spin_lock_irqsave(&sem->wait.lock, flags);
  143. sleepers = sem->sleepers + 1;
  144. sem->sleepers = 0;
  145. /*
  146. * Add "everybody else" and us into it. They aren't
  147. * playing, because we own the spinlock in the
  148. * wait_queue_head.
  149. */
  150. if (!atomic_add_negative(sleepers, &sem->count)) {
  151. wake_up_locked(&sem->wait);
  152. }
  153. spin_unlock_irqrestore(&sem->wait.lock, flags);
  154. return 1;
  155. }