1 /*
2 * Copyright 2014 The WebRTC Project Authors. All rights reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #include "rtc_base/deprecated/recursive_critical_section.h"
12
13 #include <stddef.h>
14 #include <stdint.h>
15
16 #include <memory>
17 #include <set>
18 #include <type_traits>
19 #include <utility>
20 #include <vector>
21
22 #include "absl/base/attributes.h"
23 #include "rtc_base/arraysize.h"
24 #include "rtc_base/checks.h"
25 #include "rtc_base/event.h"
26 #include "rtc_base/platform_thread.h"
27 #include "rtc_base/thread.h"
28 #include "test/gtest.h"
29
30 namespace rtc {
31
32 namespace {
33
34 constexpr webrtc::TimeDelta kLongTime = webrtc::TimeDelta::Seconds(10);
35 constexpr int kNumThreads = 16;
36 constexpr int kOperationsToRun = 1000;
37
38 class UniqueValueVerifier {
39 public:
Verify(const std::vector<int> & values)40 void Verify(const std::vector<int>& values) {
41 for (size_t i = 0; i < values.size(); ++i) {
42 std::pair<std::set<int>::iterator, bool> result =
43 all_values_.insert(values[i]);
44 // Each value should only be taken by one thread, so if this value
45 // has already been added, something went wrong.
46 EXPECT_TRUE(result.second)
47 << " Thread=" << Thread::Current() << " value=" << values[i];
48 }
49 }
50
Finalize()51 void Finalize() {}
52
53 private:
54 std::set<int> all_values_;
55 };
56
57 class CompareAndSwapVerifier {
58 public:
CompareAndSwapVerifier()59 CompareAndSwapVerifier() : zero_count_(0) {}
60
Verify(const std::vector<int> & values)61 void Verify(const std::vector<int>& values) {
62 for (auto v : values) {
63 if (v == 0) {
64 EXPECT_EQ(0, zero_count_) << "Thread=" << Thread::Current();
65 ++zero_count_;
66 } else {
67 EXPECT_EQ(1, v) << " Thread=" << Thread::Current();
68 }
69 }
70 }
71
Finalize()72 void Finalize() { EXPECT_EQ(1, zero_count_); }
73
74 private:
75 int zero_count_;
76 };
77
78 class RunnerBase {
79 public:
RunnerBase(int value)80 explicit RunnerBase(int value)
81 : threads_active_(0),
82 start_event_(true, false),
83 done_event_(true, false),
84 shared_value_(value) {}
85
Run()86 bool Run() {
87 // Signal all threads to start.
88 start_event_.Set();
89
90 // Wait for all threads to finish.
91 return done_event_.Wait(kLongTime);
92 }
93
SetExpectedThreadCount(int count)94 void SetExpectedThreadCount(int count) { threads_active_.store(count); }
95
shared_value() const96 int shared_value() const { return shared_value_; }
97
98 protected:
BeforeStart()99 void BeforeStart() { ASSERT_TRUE(start_event_.Wait(kLongTime)); }
100
101 // Returns true if all threads have finished.
AfterEnd()102 bool AfterEnd() {
103 if (threads_active_.fetch_sub(1) == 1) {
104 done_event_.Set();
105 return true;
106 }
107 return false;
108 }
109
110 std::atomic<int> threads_active_;
111 Event start_event_;
112 Event done_event_;
113 int shared_value_;
114 };
115
116 class RTC_LOCKABLE CriticalSectionLock {
117 public:
Lock()118 void Lock() RTC_EXCLUSIVE_LOCK_FUNCTION() { cs_.Enter(); }
Unlock()119 void Unlock() RTC_UNLOCK_FUNCTION() { cs_.Leave(); }
120
121 private:
122 RecursiveCriticalSection cs_;
123 };
124
125 template <class Lock>
126 class LockRunner : public RunnerBase {
127 public:
LockRunner()128 LockRunner() : RunnerBase(0) {}
129
Loop()130 void Loop() {
131 BeforeStart();
132
133 lock_.Lock();
134
135 EXPECT_EQ(0, shared_value_);
136 int old = shared_value_;
137
138 // Use a loop to increase the chance of race.
139 for (int i = 0; i < kOperationsToRun; ++i) {
140 ++shared_value_;
141 }
142 EXPECT_EQ(old + kOperationsToRun, shared_value_);
143 shared_value_ = 0;
144
145 lock_.Unlock();
146
147 AfterEnd();
148 }
149
150 private:
151 Lock lock_;
152 };
153
154 template <typename Runner>
StartThreads(std::vector<std::unique_ptr<Thread>> * threads,Runner * handler)155 void StartThreads(std::vector<std::unique_ptr<Thread>>* threads,
156 Runner* handler) {
157 for (int i = 0; i < kNumThreads; ++i) {
158 std::unique_ptr<Thread> thread(Thread::Create());
159 thread->Start();
160 thread->PostTask([handler] { handler->Loop(); });
161 threads->push_back(std::move(thread));
162 }
163 }
164
165 } // namespace
166
TEST(RecursiveCriticalSectionTest,Basic)167 TEST(RecursiveCriticalSectionTest, Basic) {
168 // Create and start lots of threads.
169 LockRunner<CriticalSectionLock> runner;
170 std::vector<std::unique_ptr<Thread>> threads;
171 StartThreads(&threads, &runner);
172 runner.SetExpectedThreadCount(kNumThreads);
173
174 // Release the hounds!
175 EXPECT_TRUE(runner.Run());
176 EXPECT_EQ(0, runner.shared_value());
177 }
178
179 class PerfTestData {
180 public:
PerfTestData(int expected_count,Event * event)181 PerfTestData(int expected_count, Event* event)
182 : cache_line_barrier_1_(),
183 cache_line_barrier_2_(),
184 expected_count_(expected_count),
185 event_(event) {
186 cache_line_barrier_1_[0]++; // Avoid 'is not used'.
187 cache_line_barrier_2_[0]++; // Avoid 'is not used'.
188 }
~PerfTestData()189 ~PerfTestData() {}
190
AddToCounter(int add)191 void AddToCounter(int add) {
192 rtc::CritScope cs(&lock_);
193 my_counter_ += add;
194 if (my_counter_ == expected_count_)
195 event_->Set();
196 }
197
total() const198 int64_t total() const {
199 // Assume that only one thread is running now.
200 return my_counter_;
201 }
202
203 private:
204 uint8_t cache_line_barrier_1_[64];
205 RecursiveCriticalSection lock_;
206 uint8_t cache_line_barrier_2_[64];
207 int64_t my_counter_ = 0;
208 const int expected_count_;
209 Event* const event_;
210 };
211
212 class PerfTestThread {
213 public:
Start(PerfTestData * data,int repeats,int id)214 void Start(PerfTestData* data, int repeats, int id) {
215 RTC_DCHECK(!data_);
216 data_ = data;
217 repeats_ = repeats;
218 my_id_ = id;
219 thread_ = PlatformThread::SpawnJoinable(
220 [this] {
221 for (int i = 0; i < repeats_; ++i)
222 data_->AddToCounter(my_id_);
223 },
224 "CsPerf");
225 }
226
Stop()227 void Stop() {
228 RTC_DCHECK(data_);
229 thread_.Finalize();
230 repeats_ = 0;
231 data_ = nullptr;
232 my_id_ = 0;
233 }
234
235 private:
236 PlatformThread thread_;
237 PerfTestData* data_ = nullptr;
238 int repeats_ = 0;
239 int my_id_ = 0;
240 };
241
242 // Comparison of output of this test as tested on a MacBook Pro, 13-inch,
243 // 2017, 3,5 GHz Intel Core i7, 16 GB 2133 MHz LPDDR3,
244 // running macOS Mojave, 10.14.3.
245 //
246 // Native mutex implementation using fair policy (previously macOS default):
247 // Approximate CPU usage:
248 // real 4m54.612s
249 // user 1m20.575s
250 // sys 3m48.872s
251 // Unit test output:
252 // [ OK ] RecursiveCriticalSectionTest.Performance (294375 ms)
253 //
254 // Native mutex implementation using first fit policy (current macOS default):
255 // Approximate CPU usage:
256 // real 0m11.535s
257 // user 0m12.738s
258 // sys 0m31.207s
259 // Unit test output:
260 // [ OK ] RecursiveCriticalSectionTest.Performance (11444 ms)
261 //
262 // Special partially spin lock based implementation:
263 // Approximate CPU usage:
264 // real 0m2.113s
265 // user 0m3.014s
266 // sys 0m4.495s
267 // Unit test output:
268 // [ OK ] RecursiveCriticalSectionTest.Performance (1885 ms)
269 //
270 // The test is disabled by default to avoid unecessarily loading the bots.
TEST(RecursiveCriticalSectionTest,DISABLED_Performance)271 TEST(RecursiveCriticalSectionTest, DISABLED_Performance) {
272 PerfTestThread threads[8];
273 Event event;
274
275 static const int kThreadRepeats = 10000000;
276 static const int kExpectedCount = kThreadRepeats * arraysize(threads);
277 PerfTestData test_data(kExpectedCount, &event);
278
279 for (auto& t : threads)
280 t.Start(&test_data, kThreadRepeats, 1);
281
282 event.Wait(Event::kForever);
283
284 for (auto& t : threads)
285 t.Stop();
286 }
287
288 } // namespace rtc
289