1 // Copyright 2019 The SwiftShader Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 // This file contains a number of synchronization primitives for concurrency.
16 //
17 // You may be tempted to change this code to unlock the mutex before calling
18 // std::condition_variable::notify_[one,all]. Please read
19 // https://issuetracker.google.com/issues/133135427 before making this sort of
20 // change.
21
22 #ifndef sw_Synchronization_hpp
23 #define sw_Synchronization_hpp
24
25 #include <assert.h>
26 #include <chrono>
27 #include <condition_variable>
28 #include <mutex>
29 #include <queue>
30
31 namespace sw {
32
33 // TaskEvents is an interface for notifying when tasks begin and end.
34 // Tasks can be nested and/or overlapping.
35 // TaskEvents is used for task queue synchronization.
36 class TaskEvents
37 {
38 public:
39 // start() is called before a task begins.
40 virtual void start() = 0;
41 // finish() is called after a task ends. finish() must only be called after
42 // a corresponding call to start().
43 virtual void finish() = 0;
44 // complete() is a helper for calling start() followed by finish().
complete()45 inline void complete()
46 {
47 start();
48 finish();
49 }
50
51 protected:
52 virtual ~TaskEvents() = default;
53 };
54
55 // WaitGroup is a synchronization primitive that allows you to wait for
56 // collection of asynchronous tasks to finish executing.
57 // Call add() before each task begins, and then call done() when after each task
58 // is finished.
59 // At the same time, wait() can be used to block until all tasks have finished.
60 // WaitGroup takes its name after Golang's sync.WaitGroup.
61 class WaitGroup : public TaskEvents
62 {
63 public:
64 // add() begins a new task.
add()65 void add()
66 {
67 std::unique_lock<std::mutex> lock(mutex);
68 ++count_;
69 }
70
71 // done() is called when a task of the WaitGroup has been completed.
72 // Returns true if there are no more tasks currently running in the
73 // WaitGroup.
done()74 bool done()
75 {
76 std::unique_lock<std::mutex> lock(mutex);
77 assert(count_ > 0);
78 --count_;
79 if(count_ == 0)
80 {
81 condition.notify_all();
82 }
83 return count_ == 0;
84 }
85
86 // wait() blocks until all the tasks have been finished.
wait()87 void wait()
88 {
89 std::unique_lock<std::mutex> lock(mutex);
90 condition.wait(lock, [this] { return count_ == 0; });
91 }
92
93 // wait() blocks until all the tasks have been finished or the timeout
94 // has been reached, returning true if all tasks have been completed, or
95 // false if the timeout has been reached.
96 template<class CLOCK, class DURATION>
wait(const std::chrono::time_point<CLOCK,DURATION> & timeout)97 bool wait(const std::chrono::time_point<CLOCK, DURATION> &timeout)
98 {
99 std::unique_lock<std::mutex> lock(mutex);
100 return condition.wait_until(lock, timeout, [this] { return count_ == 0; });
101 }
102
103 // count() returns the number of times add() has been called without a call
104 // to done().
105 // Note: No lock is held after count() returns, so the count may immediately
106 // change after returning.
count()107 int32_t count()
108 {
109 std::unique_lock<std::mutex> lock(mutex);
110 return count_;
111 }
112
113 // TaskEvents compliance
start()114 void start() override { add(); }
finish()115 void finish() override { done(); }
116
117 private:
118 int32_t count_ = 0; // guarded by mutex
119 std::mutex mutex;
120 std::condition_variable condition;
121 };
122
123 // Chan is a thread-safe FIFO queue of type T.
124 // Chan takes its name after Golang's chan.
125 template<typename T>
126 class Chan
127 {
128 public:
129 Chan();
130
131 // take returns the next item in the chan, blocking until an item is
132 // available.
133 T take();
134
135 // tryTake returns a <T, bool> pair.
136 // If the chan is not empty, then the next item and true are returned.
137 // If the chan is empty, then a default-initialized T and false are returned.
138 std::pair<T, bool> tryTake();
139
140 // put places an item into the chan, blocking if the chan is bounded and
141 // full.
142 void put(const T &v);
143
144 // Returns the number of items in the chan.
145 // Note: that this may change as soon as the function returns, so should
146 // only be used for debugging.
147 size_t count();
148
149 private:
150 std::queue<T> queue;
151 std::mutex mutex;
152 std::condition_variable added;
153 };
154
155 template<typename T>
Chan()156 Chan<T>::Chan()
157 {}
158
159 template<typename T>
take()160 T Chan<T>::take()
161 {
162 std::unique_lock<std::mutex> lock(mutex);
163 // Wait for item to be added.
164 added.wait(lock, [this] { return queue.size() > 0; });
165 T out = queue.front();
166 queue.pop();
167 return out;
168 }
169
170 template<typename T>
tryTake()171 std::pair<T, bool> Chan<T>::tryTake()
172 {
173 std::unique_lock<std::mutex> lock(mutex);
174 if(queue.size() == 0)
175 {
176 return std::make_pair(T{}, false);
177 }
178 T out = queue.front();
179 queue.pop();
180 return std::make_pair(out, true);
181 }
182
183 template<typename T>
put(const T & item)184 void Chan<T>::put(const T &item)
185 {
186 std::unique_lock<std::mutex> lock(mutex);
187 queue.push(item);
188 added.notify_one();
189 }
190
191 template<typename T>
count()192 size_t Chan<T>::count()
193 {
194 std::unique_lock<std::mutex> lock(mutex);
195 return queue.size();
196 }
197
198 } // namespace sw
199
200 #endif // sw_Synchronization_hpp
201