SkSharedMutex.cpp 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358
  1. /*
  2. * Copyright 2015 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #include "src/core/SkSharedMutex.h"
  8. #include "include/core/SkTypes.h"
  9. #include "include/private/SkSemaphore.h"
  10. #if !defined(__has_feature)
  11. #define __has_feature(x) 0
  12. #endif
  13. #if __has_feature(thread_sanitizer)
  14. /* Report that a lock has been created at address "lock". */
  15. #define ANNOTATE_RWLOCK_CREATE(lock) \
  16. AnnotateRWLockCreate(__FILE__, __LINE__, lock)
  17. /* Report that the lock at address "lock" is about to be destroyed. */
  18. #define ANNOTATE_RWLOCK_DESTROY(lock) \
  19. AnnotateRWLockDestroy(__FILE__, __LINE__, lock)
  20. /* Report that the lock at address "lock" has been acquired.
  21. is_w=1 for writer lock, is_w=0 for reader lock. */
  22. #define ANNOTATE_RWLOCK_ACQUIRED(lock, is_w) \
  23. AnnotateRWLockAcquired(__FILE__, __LINE__, lock, is_w)
  24. /* Report that the lock at address "lock" is about to be released. */
  25. #define ANNOTATE_RWLOCK_RELEASED(lock, is_w) \
  26. AnnotateRWLockReleased(__FILE__, __LINE__, lock, is_w)
  27. #if defined(DYNAMIC_ANNOTATIONS_WANT_ATTRIBUTE_WEAK)
  28. #if defined(__GNUC__)
  29. #define DYNAMIC_ANNOTATIONS_ATTRIBUTE_WEAK __attribute__((weak))
  30. #else
  31. /* TODO(glider): for Windows support we may want to change this macro in order
  32. to prepend __declspec(selectany) to the annotations' declarations. */
  33. #error weak annotations are not supported for your compiler
  34. #endif
  35. #else
  36. #define DYNAMIC_ANNOTATIONS_ATTRIBUTE_WEAK
  37. #endif
  38. extern "C" {
  39. void AnnotateRWLockCreate(
  40. const char *file, int line,
  41. const volatile void *lock) DYNAMIC_ANNOTATIONS_ATTRIBUTE_WEAK;
  42. void AnnotateRWLockDestroy(
  43. const char *file, int line,
  44. const volatile void *lock) DYNAMIC_ANNOTATIONS_ATTRIBUTE_WEAK;
  45. void AnnotateRWLockAcquired(
  46. const char *file, int line,
  47. const volatile void *lock, long is_w) DYNAMIC_ANNOTATIONS_ATTRIBUTE_WEAK;
  48. void AnnotateRWLockReleased(
  49. const char *file, int line,
  50. const volatile void *lock, long is_w) DYNAMIC_ANNOTATIONS_ATTRIBUTE_WEAK;
  51. }
  52. #else
  53. #define ANNOTATE_RWLOCK_CREATE(lock)
  54. #define ANNOTATE_RWLOCK_DESTROY(lock)
  55. #define ANNOTATE_RWLOCK_ACQUIRED(lock, is_w)
  56. #define ANNOTATE_RWLOCK_RELEASED(lock, is_w)
  57. #endif
  58. #ifdef SK_DEBUG
  59. #include "include/private/SkTDArray.h"
  60. #include "include/private/SkThreadID.h"
  61. class SkSharedMutex::ThreadIDSet {
  62. public:
  63. // Returns true if threadID is in the set.
  64. bool find(SkThreadID threadID) const {
  65. for (auto& t : fThreadIDs) {
  66. if (t == threadID) return true;
  67. }
  68. return false;
  69. }
  70. // Returns true if did not already exist.
  71. bool tryAdd(SkThreadID threadID) {
  72. for (auto& t : fThreadIDs) {
  73. if (t == threadID) return false;
  74. }
  75. fThreadIDs.append(1, &threadID);
  76. return true;
  77. }
  78. // Returns true if already exists in Set.
  79. bool tryRemove(SkThreadID threadID) {
  80. for (int i = 0; i < fThreadIDs.count(); ++i) {
  81. if (fThreadIDs[i] == threadID) {
  82. fThreadIDs.remove(i);
  83. return true;
  84. }
  85. }
  86. return false;
  87. }
  88. void swap(ThreadIDSet& other) {
  89. fThreadIDs.swap(other.fThreadIDs);
  90. }
  91. int count() const {
  92. return fThreadIDs.count();
  93. }
  94. private:
  95. SkTDArray<SkThreadID> fThreadIDs;
  96. };
  97. SkSharedMutex::SkSharedMutex()
  98. : fCurrentShared(new ThreadIDSet)
  99. , fWaitingExclusive(new ThreadIDSet)
  100. , fWaitingShared(new ThreadIDSet){
  101. ANNOTATE_RWLOCK_CREATE(this);
  102. }
  103. SkSharedMutex::~SkSharedMutex() { ANNOTATE_RWLOCK_DESTROY(this); }
  104. void SkSharedMutex::acquire() {
  105. SkThreadID threadID(SkGetThreadID());
  106. int currentSharedCount;
  107. int waitingExclusiveCount;
  108. {
  109. SkAutoMutexExclusive l(fMu);
  110. SkASSERTF(!fCurrentShared->find(threadID),
  111. "Thread %lx already has an shared lock\n", threadID);
  112. if (!fWaitingExclusive->tryAdd(threadID)) {
  113. SkDEBUGFAILF("Thread %lx already has an exclusive lock\n", threadID);
  114. }
  115. currentSharedCount = fCurrentShared->count();
  116. waitingExclusiveCount = fWaitingExclusive->count();
  117. }
  118. if (currentSharedCount > 0 || waitingExclusiveCount > 1) {
  119. fExclusiveQueue.wait();
  120. }
  121. ANNOTATE_RWLOCK_ACQUIRED(this, 1);
  122. }
  123. // Implementation Detail:
  124. // The shared threads need two seperate queues to keep the threads that were added after the
  125. // exclusive lock separate from the threads added before.
  126. void SkSharedMutex::release() {
  127. ANNOTATE_RWLOCK_RELEASED(this, 1);
  128. SkThreadID threadID(SkGetThreadID());
  129. int sharedWaitingCount;
  130. int exclusiveWaitingCount;
  131. int sharedQueueSelect;
  132. {
  133. SkAutoMutexExclusive l(fMu);
  134. SkASSERT(0 == fCurrentShared->count());
  135. if (!fWaitingExclusive->tryRemove(threadID)) {
  136. SkDEBUGFAILF("Thread %lx did not have the lock held.\n", threadID);
  137. }
  138. exclusiveWaitingCount = fWaitingExclusive->count();
  139. sharedWaitingCount = fWaitingShared->count();
  140. fWaitingShared.swap(fCurrentShared);
  141. sharedQueueSelect = fSharedQueueSelect;
  142. if (sharedWaitingCount > 0) {
  143. fSharedQueueSelect = 1 - fSharedQueueSelect;
  144. }
  145. }
  146. if (sharedWaitingCount > 0) {
  147. fSharedQueue[sharedQueueSelect].signal(sharedWaitingCount);
  148. } else if (exclusiveWaitingCount > 0) {
  149. fExclusiveQueue.signal();
  150. }
  151. }
  152. void SkSharedMutex::assertHeld() const {
  153. SkThreadID threadID(SkGetThreadID());
  154. SkAutoMutexExclusive l(fMu);
  155. SkASSERT(0 == fCurrentShared->count());
  156. SkASSERT(fWaitingExclusive->find(threadID));
  157. }
  158. void SkSharedMutex::acquireShared() {
  159. SkThreadID threadID(SkGetThreadID());
  160. int exclusiveWaitingCount;
  161. int sharedQueueSelect;
  162. {
  163. SkAutoMutexExclusive l(fMu);
  164. exclusiveWaitingCount = fWaitingExclusive->count();
  165. if (exclusiveWaitingCount > 0) {
  166. if (!fWaitingShared->tryAdd(threadID)) {
  167. SkDEBUGFAILF("Thread %lx was already waiting!\n", threadID);
  168. }
  169. } else {
  170. if (!fCurrentShared->tryAdd(threadID)) {
  171. SkDEBUGFAILF("Thread %lx already holds a shared lock!\n", threadID);
  172. }
  173. }
  174. sharedQueueSelect = fSharedQueueSelect;
  175. }
  176. if (exclusiveWaitingCount > 0) {
  177. fSharedQueue[sharedQueueSelect].wait();
  178. }
  179. ANNOTATE_RWLOCK_ACQUIRED(this, 0);
  180. }
  181. void SkSharedMutex::releaseShared() {
  182. ANNOTATE_RWLOCK_RELEASED(this, 0);
  183. SkThreadID threadID(SkGetThreadID());
  184. int currentSharedCount;
  185. int waitingExclusiveCount;
  186. {
  187. SkAutoMutexExclusive l(fMu);
  188. if (!fCurrentShared->tryRemove(threadID)) {
  189. SkDEBUGFAILF("Thread %lx does not hold a shared lock.\n", threadID);
  190. }
  191. currentSharedCount = fCurrentShared->count();
  192. waitingExclusiveCount = fWaitingExclusive->count();
  193. }
  194. if (0 == currentSharedCount && waitingExclusiveCount > 0) {
  195. fExclusiveQueue.signal();
  196. }
  197. }
  198. void SkSharedMutex::assertHeldShared() const {
  199. SkThreadID threadID(SkGetThreadID());
  200. SkAutoMutexExclusive l(fMu);
  201. SkASSERT(fCurrentShared->find(threadID));
  202. }
  203. #else
  204. // The fQueueCounts fields holds many counts in an int32_t in order to make managing them atomic.
  205. // These three counts must be the same size, so each gets 10 bits. The 10 bits represent
  206. // the log of the count which is 1024.
  207. //
  208. // The three counts held in fQueueCounts are:
  209. // * Shared - the number of shared lock holders currently running.
  210. // * WaitingExclusive - the number of threads waiting for an exclusive lock.
  211. // * WaitingShared - the number of threads waiting to run while waiting for an exclusive thread
  212. // to finish.
  213. static const int kLogThreadCount = 10;
  214. enum {
  215. kSharedOffset = (0 * kLogThreadCount),
  216. kWaitingExlusiveOffset = (1 * kLogThreadCount),
  217. kWaitingSharedOffset = (2 * kLogThreadCount),
  218. kSharedMask = ((1 << kLogThreadCount) - 1) << kSharedOffset,
  219. kWaitingExclusiveMask = ((1 << kLogThreadCount) - 1) << kWaitingExlusiveOffset,
  220. kWaitingSharedMask = ((1 << kLogThreadCount) - 1) << kWaitingSharedOffset,
  221. };
  222. SkSharedMutex::SkSharedMutex() : fQueueCounts(0) { ANNOTATE_RWLOCK_CREATE(this); }
  223. SkSharedMutex::~SkSharedMutex() { ANNOTATE_RWLOCK_DESTROY(this); }
  224. void SkSharedMutex::acquire() {
  225. // Increment the count of exclusive queue waiters.
  226. int32_t oldQueueCounts = fQueueCounts.fetch_add(1 << kWaitingExlusiveOffset,
  227. std::memory_order_acquire);
  228. // If there are no other exclusive waiters and no shared threads are running then run
  229. // else wait.
  230. if ((oldQueueCounts & kWaitingExclusiveMask) > 0 || (oldQueueCounts & kSharedMask) > 0) {
  231. fExclusiveQueue.wait();
  232. }
  233. ANNOTATE_RWLOCK_ACQUIRED(this, 1);
  234. }
  235. void SkSharedMutex::release() {
  236. ANNOTATE_RWLOCK_RELEASED(this, 1);
  237. int32_t oldQueueCounts = fQueueCounts.load(std::memory_order_relaxed);
  238. int32_t waitingShared;
  239. int32_t newQueueCounts;
  240. do {
  241. newQueueCounts = oldQueueCounts;
  242. // Decrement exclusive waiters.
  243. newQueueCounts -= 1 << kWaitingExlusiveOffset;
  244. // The number of threads waiting to acquire a shared lock.
  245. waitingShared = (oldQueueCounts & kWaitingSharedMask) >> kWaitingSharedOffset;
  246. // If there are any move the counts of all the shared waiters to actual shared. They are
  247. // going to run next.
  248. if (waitingShared > 0) {
  249. // Set waiting shared to zero.
  250. newQueueCounts &= ~kWaitingSharedMask;
  251. // Because this is the exclusive release, then there are zero readers. So, the bits
  252. // for shared locks should be zero. Since those bits are zero, we can just |= in the
  253. // waitingShared count instead of clearing with an &= and then |= the count.
  254. newQueueCounts |= waitingShared << kSharedOffset;
  255. }
  256. } while (!fQueueCounts.compare_exchange_strong(oldQueueCounts, newQueueCounts,
  257. std::memory_order_release,
  258. std::memory_order_relaxed));
  259. if (waitingShared > 0) {
  260. // Run all the shared.
  261. fSharedQueue.signal(waitingShared);
  262. } else if ((newQueueCounts & kWaitingExclusiveMask) > 0) {
  263. // Run a single exclusive waiter.
  264. fExclusiveQueue.signal();
  265. }
  266. }
  267. void SkSharedMutex::acquireShared() {
  268. int32_t oldQueueCounts = fQueueCounts.load(std::memory_order_relaxed);
  269. int32_t newQueueCounts;
  270. do {
  271. newQueueCounts = oldQueueCounts;
  272. // If there are waiting exclusives then this shared lock waits else it runs.
  273. if ((newQueueCounts & kWaitingExclusiveMask) > 0) {
  274. newQueueCounts += 1 << kWaitingSharedOffset;
  275. } else {
  276. newQueueCounts += 1 << kSharedOffset;
  277. }
  278. } while (!fQueueCounts.compare_exchange_strong(oldQueueCounts, newQueueCounts,
  279. std::memory_order_acquire,
  280. std::memory_order_relaxed));
  281. // If there are waiting exclusives, then this shared waits until after it runs.
  282. if ((newQueueCounts & kWaitingExclusiveMask) > 0) {
  283. fSharedQueue.wait();
  284. }
  285. ANNOTATE_RWLOCK_ACQUIRED(this, 0);
  286. }
  287. void SkSharedMutex::releaseShared() {
  288. ANNOTATE_RWLOCK_RELEASED(this, 0);
  289. // Decrement the shared count.
  290. int32_t oldQueueCounts = fQueueCounts.fetch_sub(1 << kSharedOffset,
  291. std::memory_order_release);
  292. // If shared count is going to zero (because the old count == 1) and there are exclusive
  293. // waiters, then run a single exclusive waiter.
  294. if (((oldQueueCounts & kSharedMask) >> kSharedOffset) == 1
  295. && (oldQueueCounts & kWaitingExclusiveMask) > 0) {
  296. fExclusiveQueue.signal();
  297. }
  298. }
  299. #endif