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