db_mutex.c 5.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217
  1. /* -*- mode:c; c-file-style:"k&r"; c-basic-offset: 4; tab-width:4; indent-tabs-mode:nil; mode:auto-fill; fill-column:78; -*- */
  2. /* vim: set ts=4 sw=4 et tw=78 fo=cqt wm=0: */
  3. /* Copyright (C) 2014 Stony Brook University
  4. This file is part of Graphene Library OS.
  5. Graphene Library OS is free software: you can redistribute it and/or
  6. modify it under the terms of the GNU Lesser General Public License
  7. as published by the Free Software Foundation, either version 3 of the
  8. License, or (at your option) any later version.
  9. Graphene Library OS 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 Lesser General Public License for more details.
  13. You should have received a copy of the GNU Lesser General Public License
  14. along with this program. If not, see <http://www.gnu.org/licenses/>. */
  15. /*
  16. * db_mutex.c
  17. *
  18. * This file contains APIs that provide operations of (futex based) mutexes.
  19. * Based on "Mutexes and Condition Variables using Futexes"
  20. * (http://locklessinc.com/articles/mutex_cv_futex)
  21. */
  22. #include "pal_defs.h"
  23. #include "pal_linux_defs.h"
  24. #include "pal.h"
  25. #include "pal_internal.h"
  26. #include "pal_linux.h"
  27. #include "pal_error.h"
  28. #include "api.h"
  29. #include <linux/futex.h>
  30. #include <limits.h>
  31. #include <atomic.h>
  32. #include <asm/errno.h>
  33. #include <linux/time.h>
  34. #include <unistd.h>
  35. #ifdef __x86_64__
  36. # include <unistd.h>
  37. #endif
  38. #define MUTEX_SPINLOCK_TIMES 100
  39. #define MUTEX_UNLOCKED 0
  40. #define MUTEX_LOCKED 1
  41. /* Interplay between locked and nwaiters:
  42. *
  43. * If lock is unlocked and uncontended, just set the locked state.
  44. *
  45. * Important possible interleavings of lock and unlock:
  46. *
  47. * Case 1:
  48. *
  49. * Owner: Locker:
  50. * Try lock and fail; increment nwaiters; sleep
  51. * Set state to unlocked
  52. * Read nwaiters; wake
  53. * Try again and succeed.
  54. *
  55. * ***************************************************
  56. *
  57. * Case 2:
  58. *
  59. * Owner: Locker:
  60. * Try lock and fail
  61. * Set state to unlocked
  62. * Read nwaiters (=0)
  63. * Increment nwaiters.
  64. * Can't go to sleep here; will cmpxchg locked and succeed
  65. * Don't wake anyone
  66. */
  67. int
  68. _DkMutexCreate (PAL_HANDLE * handle, int initialCount)
  69. {
  70. PAL_HANDLE mut = malloc(HANDLE_SIZE(mutex));
  71. SET_HANDLE_TYPE(mut, mutex);
  72. atomic_set(&mut->mutex.mut.nwaiters, 0);
  73. mut->mutex.mut.locked = initialCount;
  74. *handle = mut;
  75. return 0;
  76. }
  77. int _DkMutexLockTimeout (struct mutex_handle * m, uint64_t timeout)
  78. {
  79. int i, ret = 0;
  80. #ifdef DEBUG_MUTEX
  81. int tid = INLINE_SYSCALL(gettid, 0);
  82. #endif
  83. /* If this is a trylock-style call, break more quickly. */
  84. int iterations = (timeout == 0) ? 1 : MUTEX_SPINLOCK_TIMES;
  85. /* Spin and try to take lock. Ignore any contribution this makes toward
  86. * the timeout.*/
  87. for (i = 0; i < iterations; i++) {
  88. if (MUTEX_UNLOCKED == cmpxchg(&m->locked, MUTEX_UNLOCKED, MUTEX_LOCKED))
  89. goto success;
  90. CPU_RELAX();
  91. }
  92. if (timeout == 0) {
  93. ret = -PAL_ERROR_TRYAGAIN;
  94. goto out;
  95. }
  96. // Bump up the waiters count; we are probably going to block
  97. atomic_inc(&m->nwaiters);
  98. while (MUTEX_LOCKED == cmpxchg(&m->locked, MUTEX_UNLOCKED, MUTEX_LOCKED)) {
  99. struct timespec waittime, *waittimep = NULL;
  100. if (timeout != NO_TIMEOUT) {
  101. long sec = timeout / 1000000;
  102. long microsec = timeout - (sec * 1000000);
  103. waittime.tv_sec = sec;
  104. waittime.tv_nsec = microsec * 1000;
  105. waittimep = &waittime;
  106. }
  107. ret = INLINE_SYSCALL(futex, 6, m, FUTEX_WAIT, MUTEX_LOCKED, waittimep, NULL, 0);
  108. if (IS_ERR(ret)) {
  109. if (ERRNO(ret) == EWOULDBLOCK) {
  110. if (timeout != NO_TIMEOUT) {
  111. ret = -PAL_ERROR_TRYAGAIN;
  112. atomic_dec(&m->nwaiters);
  113. goto out;
  114. }
  115. } else {
  116. #ifdef DEBUG_MUTEX
  117. printf("futex failed (err = %d)\n", ERRNO(ret));
  118. #endif
  119. ret = unix_to_pal_error(ERRNO(ret));
  120. atomic_dec(&m->nwaiters);
  121. goto out;
  122. }
  123. }
  124. }
  125. atomic_dec(&m->nwaiters);
  126. success:
  127. #ifdef DEBUG_MUTEX
  128. m->owner = tid;
  129. #endif
  130. ret = 0;
  131. out:
  132. #ifdef DEBUG_MUTEX
  133. if (ret < 0)
  134. printf("mutex failed (%s, tid = %d)\n", PAL_STRERROR(ret), tid);
  135. #endif
  136. return ret;
  137. }
  138. int _DkMutexLock (struct mutex_handle * m)
  139. {
  140. return _DkMutexLockTimeout(m, -1);
  141. }
  142. int _DkMutexAcquireTimeout (PAL_HANDLE handle, int timeout)
  143. {
  144. return _DkMutexLockTimeout(&handle->mutex.mut, timeout);
  145. }
  146. int _DkMutexUnlock (struct mutex_handle * m)
  147. {
  148. int ret = 0;
  149. int need_wake;
  150. #ifdef DEBUG_MUTEX
  151. m->owner = 0;
  152. #endif
  153. /* Unlock */
  154. m->locked = 0;
  155. /* We need to make sure the write to locked is visible to lock-ers
  156. * before we read the waiter count. */
  157. MB();
  158. need_wake = atomic_read(&m->nwaiters);
  159. /* If we need to wake someone up... */
  160. if (need_wake)
  161. INLINE_SYSCALL(futex, 6, m, FUTEX_WAKE, 1, NULL, NULL, 0);
  162. return ret;
  163. }
  164. void _DkMutexRelease (PAL_HANDLE handle)
  165. {
  166. _DkMutexUnlock(&handle->mutex.mut);
  167. return;
  168. }
  169. int _DkInternalLock (PAL_LOCK* lock) {
  170. while (_DkMutexLock(lock) < 0); // Retry the lock if being interrupted by signals
  171. return 0;
  172. }
  173. int _DkInternalUnlock (PAL_LOCK* lock) {
  174. _DkMutexUnlock(lock);
  175. return 0;
  176. }
  177. static int mutex_wait (PAL_HANDLE handle, uint64_t timeout)
  178. {
  179. return _DkMutexAcquireTimeout(handle, timeout);
  180. }
  181. struct handle_ops mutex_ops = {
  182. .wait = &mutex_wait,
  183. };