rtmutex.c 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159
  1. /*
  2. * Copyright (c) 2017 Richard Braun.
  3. *
  4. * This program is free software: you can redistribute it and/or modify
  5. * it under the terms of the GNU General Public License as published by
  6. * the Free Software Foundation, either version 3 of the License, or
  7. * (at your option) any later version.
  8. *
  9. * This program is distributed in the hope that it will be useful,
  10. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. * GNU General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU General Public License
  15. * along with this program. If not, see <http://www.gnu.org/licenses/>.
  16. */
  17. #include <assert.h>
  18. #include <stdbool.h>
  19. #include <stddef.h>
  20. #include <stdint.h>
  21. #include <kern/atomic.h>
  22. #include <kern/init.h>
  23. #include <kern/macros.h>
  24. #include <kern/rtmutex.h>
  25. #include <kern/rtmutex_types.h>
  26. #include <kern/syscnt.h>
  27. #include <kern/thread.h>
  28. #include <kern/turnstile.h>
  29. static struct thread*
  30. rtmutex_get_thread (uintptr_t owner)
  31. {
  32. return ((struct thread *)(owner & RTMUTEX_OWNER_MASK));
  33. }
  34. static void
  35. rtmutex_set_contended (struct rtmutex *rtmutex)
  36. {
  37. atomic_or_rel (&rtmutex->owner, RTMUTEX_CONTENDED);
  38. }
  39. static int
  40. rtmutex_lock_slow_common (struct rtmutex *rtmutex, bool timed, uint64_t ticks)
  41. {
  42. int error = 0;
  43. uintptr_t self = (uintptr_t)thread_self (), bits = RTMUTEX_CONTENDED;
  44. struct turnstile *turnstile = turnstile_lend (rtmutex);
  45. rtmutex_set_contended (rtmutex);
  46. while (1)
  47. {
  48. uintptr_t owner = atomic_cas_acq (&rtmutex->owner, bits, self | bits);
  49. assert ((owner & bits) == bits);
  50. if (owner == bits)
  51. break;
  52. struct thread *thread = rtmutex_get_thread (owner);
  53. if (! timed)
  54. turnstile_wait (turnstile, "rtmutex", thread);
  55. else
  56. {
  57. error = turnstile_timedwait (turnstile, "rtmutex", thread, ticks);
  58. if (error)
  59. break;
  60. }
  61. bits |= RTMUTEX_FORCE_WAIT;
  62. }
  63. if (error)
  64. {
  65. /*
  66. * Keep in mind more than one thread may have timed out on waiting.
  67. * These threads aren't considered waiters, making the turnstile
  68. * potentially empty. The first to reacquire the turnstile clears
  69. * the contention bits, allowing the owner to unlock through the
  70. * fast path.
  71. */
  72. if (turnstile_empty (turnstile))
  73. {
  74. uintptr_t owner = atomic_load_rlx (&rtmutex->owner);
  75. if (owner & RTMUTEX_CONTENDED)
  76. {
  77. owner &= RTMUTEX_OWNER_MASK;
  78. atomic_store_rlx (&rtmutex->owner, owner);
  79. }
  80. }
  81. goto out;
  82. }
  83. turnstile_own (turnstile);
  84. if (turnstile_empty (turnstile))
  85. {
  86. uintptr_t owner = atomic_swap_rlx (&rtmutex->owner, self);
  87. assert (owner == (self | bits));
  88. }
  89. out:
  90. turnstile_return (turnstile);
  91. /*
  92. * A lock owner should never perform priority propagation on itself,
  93. * because this process is done using its own priority, potentially
  94. * introducing unbounded priority inversion.
  95. * Instead, let new waiters do it, using their own priority.
  96. */
  97. return (error);
  98. }
  99. void
  100. rtmutex_lock_slow (struct rtmutex *rtmutex)
  101. {
  102. int error = rtmutex_lock_slow_common (rtmutex, false, 0);
  103. assert (! error);
  104. }
  105. int
  106. rtmutex_timedlock_slow (struct rtmutex *rtmutex, uint64_t ticks)
  107. {
  108. return (rtmutex_lock_slow_common (rtmutex, true, ticks));
  109. }
  110. void
  111. rtmutex_unlock_slow (struct rtmutex *rtmutex)
  112. {
  113. struct turnstile *turnstile;
  114. while (1)
  115. {
  116. turnstile = turnstile_acquire (rtmutex);
  117. if (turnstile)
  118. break;
  119. else if (!(rtmutex_unlock_fast (rtmutex) & RTMUTEX_CONTENDED))
  120. goto out;
  121. }
  122. uintptr_t owner = atomic_swap_rel (&rtmutex->owner,
  123. RTMUTEX_FORCE_WAIT | RTMUTEX_CONTENDED);
  124. assert (rtmutex_get_thread (owner) == thread_self ());
  125. turnstile_disown (turnstile);
  126. turnstile_signal (turnstile);
  127. turnstile_release (turnstile);
  128. out:
  129. thread_propagate_priority ();
  130. }