henrike@webrtc.org | f048872 | 2014-05-13 18:00:26 | [diff] [blame] | 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 | |
Markus Handell | 3cb525b | 2020-07-16 14:16:09 | [diff] [blame] | 11 | #include "rtc_base/deprecated/recursive_critical_section.h" |
Jonas Olsson | a4d8737 | 2019-07-05 17:08:33 | [diff] [blame] | 12 | |
Yves Gerey | 3e70781 | 2018-11-28 15:47:49 | [diff] [blame] | 13 | #include <stddef.h> |
| 14 | #include <stdint.h> |
Jonas Olsson | a4d8737 | 2019-07-05 17:08:33 | [diff] [blame] | 15 | |
jbauch | 555604a | 2016-04-26 10:13:22 | [diff] [blame] | 16 | #include <memory> |
henrike@webrtc.org | f048872 | 2014-05-13 18:00:26 | [diff] [blame] | 17 | #include <set> |
Danil Chapovalov | 5740f3e | 2019-10-10 09:12:15 | [diff] [blame] | 18 | #include <type_traits> |
Yves Gerey | 3e70781 | 2018-11-28 15:47:49 | [diff] [blame] | 19 | #include <utility> |
henrike@webrtc.org | f048872 | 2014-05-13 18:00:26 | [diff] [blame] | 20 | #include <vector> |
| 21 | |
Danil Chapovalov | 5740f3e | 2019-10-10 09:12:15 | [diff] [blame] | 22 | #include "absl/base/attributes.h" |
Mirko Bonadei | 92ea95e | 2017-09-15 04:47:31 | [diff] [blame] | 23 | #include "rtc_base/arraysize.h" |
| 24 | #include "rtc_base/checks.h" |
Mirko Bonadei | 92ea95e | 2017-09-15 04:47:31 | [diff] [blame] | 25 | #include "rtc_base/event.h" |
Mirko Bonadei | 92ea95e | 2017-09-15 04:47:31 | [diff] [blame] | 26 | #include "rtc_base/platform_thread.h" |
| 27 | #include "rtc_base/thread.h" |
Yves Gerey | 3e70781 | 2018-11-28 15:47:49 | [diff] [blame] | 28 | #include "test/gtest.h" |
henrike@webrtc.org | f048872 | 2014-05-13 18:00:26 | [diff] [blame] | 29 | |
| 30 | namespace rtc { |
| 31 | |
| 32 | namespace { |
| 33 | |
Markus Handell | 2cfc1af | 2022-08-19 08:16:48 | [diff] [blame] | 34 | constexpr webrtc::TimeDelta kLongTime = webrtc::TimeDelta::Seconds(10); |
| 35 | constexpr int kNumThreads = 16; |
| 36 | constexpr int kOperationsToRun = 1000; |
henrike@webrtc.org | f048872 | 2014-05-13 18:00:26 | [diff] [blame] | 37 | |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 38 | class UniqueValueVerifier { |
henrike@webrtc.org | f048872 | 2014-05-13 18:00:26 | [diff] [blame] | 39 | public: |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 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 | } |
henrike@webrtc.org | f048872 | 2014-05-13 18:00:26 | [diff] [blame] | 50 | |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 51 | void Finalize() {} |
| 52 | |
| 53 | private: |
| 54 | std::set<int> all_values_; |
| 55 | }; |
| 56 | |
| 57 | class CompareAndSwapVerifier { |
| 58 | public: |
| 59 | CompareAndSwapVerifier() : zero_count_(0) {} |
| 60 | |
| 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 | |
Yves Gerey | 665174f | 2018-06-19 13:03:05 | [diff] [blame] | 72 | void Finalize() { EXPECT_EQ(1, zero_count_); } |
| 73 | |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 74 | private: |
| 75 | int zero_count_; |
| 76 | }; |
| 77 | |
Danil Chapovalov | 1e6965a | 2022-09-05 09:27:57 | [diff] [blame] | 78 | class RunnerBase { |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 79 | public: |
| 80 | explicit RunnerBase(int value) |
| 81 | : threads_active_(0), |
| 82 | start_event_(true, false), |
| 83 | done_event_(true, false), |
| 84 | shared_value_(value) {} |
henrike@webrtc.org | f048872 | 2014-05-13 18:00:26 | [diff] [blame] | 85 | |
| 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 | |
Niels Möller | 7a66900 | 2022-06-27 07:47:02 | [diff] [blame] | 94 | void SetExpectedThreadCount(int count) { threads_active_.store(count); } |
henrike@webrtc.org | f048872 | 2014-05-13 18:00:26 | [diff] [blame] | 95 | |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 96 | int shared_value() const { return shared_value_; } |
| 97 | |
| 98 | protected: |
Yves Gerey | 665174f | 2018-06-19 13:03:05 | [diff] [blame] | 99 | void BeforeStart() { ASSERT_TRUE(start_event_.Wait(kLongTime)); } |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 100 | |
| 101 | // Returns true if all threads have finished. |
| 102 | bool AfterEnd() { |
Niels Möller | 7a66900 | 2022-06-27 07:47:02 | [diff] [blame] | 103 | if (threads_active_.fetch_sub(1) == 1) { |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 104 | done_event_.Set(); |
| 105 | return true; |
| 106 | } |
| 107 | return false; |
| 108 | } |
| 109 | |
Niels Möller | 7a66900 | 2022-06-27 07:47:02 | [diff] [blame] | 110 | std::atomic<int> threads_active_; |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 111 | Event start_event_; |
| 112 | Event done_event_; |
| 113 | int shared_value_; |
| 114 | }; |
| 115 | |
danilchap | 3c6abd2 | 2017-09-06 12:46:29 | [diff] [blame] | 116 | class RTC_LOCKABLE CriticalSectionLock { |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 117 | public: |
danilchap | 3c6abd2 | 2017-09-06 12:46:29 | [diff] [blame] | 118 | void Lock() RTC_EXCLUSIVE_LOCK_FUNCTION() { cs_.Enter(); } |
| 119 | void Unlock() RTC_UNLOCK_FUNCTION() { cs_.Leave(); } |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 120 | |
| 121 | private: |
Markus Handell | 3cb525b | 2020-07-16 14:16:09 | [diff] [blame] | 122 | RecursiveCriticalSection cs_; |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 123 | }; |
| 124 | |
| 125 | template <class Lock> |
| 126 | class LockRunner : public RunnerBase { |
| 127 | public: |
| 128 | LockRunner() : RunnerBase(0) {} |
| 129 | |
Danil Chapovalov | 1e6965a | 2022-09-05 09:27:57 | [diff] [blame] | 130 | void Loop() { |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 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 | |
Danil Chapovalov | 1e6965a | 2022-09-05 09:27:57 | [diff] [blame] | 154 | template <typename Runner> |
nisse | b9c2f7c | 2017-04-20 09:23:08 | [diff] [blame] | 155 | void StartThreads(std::vector<std::unique_ptr<Thread>>* threads, |
Danil Chapovalov | 1e6965a | 2022-09-05 09:27:57 | [diff] [blame] | 156 | Runner* handler) { |
henrike@webrtc.org | f048872 | 2014-05-13 18:00:26 | [diff] [blame] | 157 | for (int i = 0; i < kNumThreads; ++i) { |
tommi | e725159 | 2017-07-14 21:44:46 | [diff] [blame] | 158 | std::unique_ptr<Thread> thread(Thread::Create()); |
henrike@webrtc.org | f048872 | 2014-05-13 18:00:26 | [diff] [blame] | 159 | thread->Start(); |
Danil Chapovalov | 1e6965a | 2022-09-05 09:27:57 | [diff] [blame] | 160 | thread->PostTask([handler] { handler->Loop(); }); |
nisse | b9c2f7c | 2017-04-20 09:23:08 | [diff] [blame] | 161 | threads->push_back(std::move(thread)); |
henrike@webrtc.org | f048872 | 2014-05-13 18:00:26 | [diff] [blame] | 162 | } |
| 163 | } |
| 164 | |
| 165 | } // namespace |
| 166 | |
Markus Handell | 3cb525b | 2020-07-16 14:16:09 | [diff] [blame] | 167 | TEST(RecursiveCriticalSectionTest, Basic) { |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 168 | // Create and start lots of threads. |
| 169 | LockRunner<CriticalSectionLock> runner; |
nisse | b9c2f7c | 2017-04-20 09:23:08 | [diff] [blame] | 170 | std::vector<std::unique_ptr<Thread>> threads; |
Jiayang Liu | bef8d2d | 2015-03-26 21:38:46 | [diff] [blame] | 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()); |
henrike@webrtc.org | f048872 | 2014-05-13 18:00:26 | [diff] [blame] | 177 | } |
| 178 | |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 179 | class PerfTestData { |
| 180 | public: |
| 181 | PerfTestData(int expected_count, Event* event) |
Yves Gerey | 665174f | 2018-06-19 13:03:05 | [diff] [blame] | 182 | : cache_line_barrier_1_(), |
| 183 | cache_line_barrier_2_(), |
| 184 | expected_count_(expected_count), |
| 185 | event_(event) { |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 186 | cache_line_barrier_1_[0]++; // Avoid 'is not used'. |
| 187 | cache_line_barrier_2_[0]++; // Avoid 'is not used'. |
| 188 | } |
| 189 | ~PerfTestData() {} |
| 190 | |
| 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 | |
| 198 | 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]; |
Markus Handell | 3cb525b | 2020-07-16 14:16:09 | [diff] [blame] | 205 | RecursiveCriticalSection lock_; |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 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: |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 214 | void Start(PerfTestData* data, int repeats, int id) { |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 215 | RTC_DCHECK(!data_); |
| 216 | data_ = data; |
| 217 | repeats_ = repeats; |
| 218 | my_id_ = id; |
Markus Handell | ad5037b | 2021-05-07 13:02:36 | [diff] [blame] | 219 | thread_ = PlatformThread::SpawnJoinable( |
| 220 | [this] { |
| 221 | for (int i = 0; i < repeats_; ++i) |
| 222 | data_->AddToCounter(my_id_); |
| 223 | }, |
| 224 | "CsPerf"); |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 225 | } |
| 226 | |
| 227 | void Stop() { |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 228 | RTC_DCHECK(data_); |
Markus Handell | ad5037b | 2021-05-07 13:02:36 | [diff] [blame] | 229 | thread_.Finalize(); |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 230 | repeats_ = 0; |
| 231 | data_ = nullptr; |
| 232 | my_id_ = 0; |
| 233 | } |
| 234 | |
| 235 | private: |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 236 | PlatformThread thread_; |
| 237 | PerfTestData* data_ = nullptr; |
| 238 | int repeats_ = 0; |
| 239 | int my_id_ = 0; |
| 240 | }; |
| 241 | |
Oskar Sundbom | 13471a4 | 2019-03-01 15:11:49 | [diff] [blame] | 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. |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 245 | // |
Oskar Sundbom | 13471a4 | 2019-03-01 15:11:49 | [diff] [blame] | 246 | // Native mutex implementation using fair policy (previously macOS default): |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 247 | // Approximate CPU usage: |
Oskar Sundbom | 13471a4 | 2019-03-01 15:11:49 | [diff] [blame] | 248 | // real 4m54.612s |
| 249 | // user 1m20.575s |
| 250 | // sys 3m48.872s |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 251 | // Unit test output: |
Markus Handell | 3cb525b | 2020-07-16 14:16:09 | [diff] [blame] | 252 | // [ OK ] RecursiveCriticalSectionTest.Performance (294375 ms) |
Oskar Sundbom | 13471a4 | 2019-03-01 15:11:49 | [diff] [blame] | 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: |
Markus Handell | 3cb525b | 2020-07-16 14:16:09 | [diff] [blame] | 260 | // [ OK ] RecursiveCriticalSectionTest.Performance (11444 ms) |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 261 | // |
| 262 | // Special partially spin lock based implementation: |
| 263 | // Approximate CPU usage: |
Oskar Sundbom | 13471a4 | 2019-03-01 15:11:49 | [diff] [blame] | 264 | // real 0m2.113s |
| 265 | // user 0m3.014s |
| 266 | // sys 0m4.495s |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 267 | // Unit test output: |
Markus Handell | 3cb525b | 2020-07-16 14:16:09 | [diff] [blame] | 268 | // [ OK ] RecursiveCriticalSectionTest.Performance (1885 ms) |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 269 | // |
| 270 | // The test is disabled by default to avoid unecessarily loading the bots. |
Markus Handell | 3cb525b | 2020-07-16 14:16:09 | [diff] [blame] | 271 | TEST(RecursiveCriticalSectionTest, DISABLED_Performance) { |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 272 | PerfTestThread threads[8]; |
Niels Möller | c572ff3 | 2018-11-07 07:43:50 | [diff] [blame] | 273 | Event event; |
tommi | ed281e9 | 2016-01-22 07:47:25 | [diff] [blame] | 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 | |
henrike@webrtc.org | f048872 | 2014-05-13 18:00:26 | [diff] [blame] | 288 | } // namespace rtc |