1 // Copyright 2020 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "partition_alloc/spinning_mutex.h"
6
7 #include "build/build_config.h"
8 #include "partition_alloc/partition_alloc_base/compiler_specific.h"
9 #include "partition_alloc/partition_alloc_check.h"
10
11 #if BUILDFLAG(IS_WIN)
12 #include <windows.h>
13 #endif
14
15 #if BUILDFLAG(IS_POSIX)
16 #include <pthread.h>
17 #endif
18
19 #if PA_CONFIG(HAS_LINUX_KERNEL)
20 #include <linux/futex.h>
21 #include <sys/syscall.h>
22 #include <unistd.h>
23
24 #include <cerrno>
25 #endif // PA_CONFIG(HAS_LINUX_KERNEL)
26
27 #if !PA_CONFIG(HAS_FAST_MUTEX)
28 #include "partition_alloc/partition_alloc_base/threading/platform_thread.h"
29
30 #if BUILDFLAG(IS_POSIX)
31 #include <sched.h>
32
33 #define PA_YIELD_THREAD sched_yield()
34
35 #else // Other OS
36
37 #warning "Thread yield not supported on this OS."
38 #define PA_YIELD_THREAD ((void)0)
39 #endif
40
41 #endif // !PA_CONFIG(HAS_FAST_MUTEX)
42
43 namespace partition_alloc::internal {
44
Reinit()45 void SpinningMutex::Reinit() {
46 #if !BUILDFLAG(IS_APPLE)
47 // On most platforms, no need to re-init the lock, can just unlock it.
48 Release();
49 #else
50 unfair_lock_ = OS_UNFAIR_LOCK_INIT;
51 #endif // BUILDFLAG(IS_APPLE)
52 }
53
AcquireSpinThenBlock()54 void SpinningMutex::AcquireSpinThenBlock() {
55 int tries = 0;
56 int backoff = 1;
57 do {
58 if (PA_LIKELY(Try())) {
59 return;
60 }
61 // Note: Per the intel optimization manual
62 // (https://software.intel.com/content/dam/develop/public/us/en/documents/64-ia-32-architectures-optimization-manual.pdf),
63 // the "pause" instruction is more costly on Skylake Client than on previous
64 // architectures. The latency is found to be 141 cycles
65 // there (from ~10 on previous ones, nice 14x).
66 //
67 // According to Agner Fog's instruction tables, the latency is still >100
68 // cycles on Ice Lake, and from other sources, seems to be high as well on
69 // Adler Lake. Separately, it is (from
70 // https://agner.org/optimize/instruction_tables.pdf) also high on AMD Zen 3
71 // (~65). So just assume that it's this way for most x86_64 architectures.
72 //
73 // Also, loop several times here, following the guidelines in section 2.3.4
74 // of the manual, "Pause latency in Skylake Client Microarchitecture".
75 for (int yields = 0; yields < backoff; yields++) {
76 PA_YIELD_PROCESSOR;
77 tries++;
78 }
79 constexpr int kMaxBackoff = 16;
80 backoff = std::min(kMaxBackoff, backoff << 1);
81 } while (tries < kSpinCount);
82
83 LockSlow();
84 }
85
86 #if PA_CONFIG(HAS_FAST_MUTEX)
87
88 #if PA_CONFIG(HAS_LINUX_KERNEL)
89
FutexWait()90 void SpinningMutex::FutexWait() {
91 // Save and restore errno.
92 int saved_errno = errno;
93 // Don't check the return value, as we will not be awaken by a timeout, since
94 // none is specified.
95 //
96 // Ignoring the return value doesn't impact correctness, as this acts as an
97 // immediate wakeup. For completeness, the possible errors for FUTEX_WAIT are:
98 // - EACCES: state_ is not readable. Should not happen.
99 // - EAGAIN: the value is not as expected, that is not |kLockedContended|, in
100 // which case retrying the loop is the right behavior.
101 // - EINTR: signal, looping is the right behavior.
102 // - EINVAL: invalid argument.
103 //
104 // Note: not checking the return value is the approach used in bionic and
105 // glibc as well.
106 //
107 // Will return immediately if |state_| is no longer equal to
108 // |kLockedContended|. Otherwise, sleeps and wakes up when |state_| may not be
109 // |kLockedContended| anymore. Note that even without spurious wakeups, the
110 // value of |state_| is not guaranteed when this returns, as another thread
111 // may get the lock before we get to run.
112 int err = syscall(SYS_futex, &state_, FUTEX_WAIT | FUTEX_PRIVATE_FLAG,
113 kLockedContended, nullptr, nullptr, 0);
114
115 if (err) {
116 // These are programming error, check them.
117 PA_DCHECK(errno != EACCES);
118 PA_DCHECK(errno != EINVAL);
119 }
120 errno = saved_errno;
121 }
122
FutexWake()123 void SpinningMutex::FutexWake() {
124 int saved_errno = errno;
125 long retval = syscall(SYS_futex, &state_, FUTEX_WAKE | FUTEX_PRIVATE_FLAG,
126 1 /* wake up a single waiter */, nullptr, nullptr, 0);
127 PA_CHECK(retval != -1);
128 errno = saved_errno;
129 }
130
LockSlow()131 void SpinningMutex::LockSlow() {
132 // If this thread gets awaken but another one got the lock first, then go back
133 // to sleeping. See comments in |FutexWait()| to see why a loop is required.
134 while (state_.exchange(kLockedContended, std::memory_order_acquire) !=
135 kUnlocked) {
136 FutexWait();
137 }
138 }
139
140 #elif BUILDFLAG(IS_WIN)
141
LockSlow()142 void SpinningMutex::LockSlow() {
143 ::AcquireSRWLockExclusive(reinterpret_cast<PSRWLOCK>(&lock_));
144 }
145
146 #elif BUILDFLAG(IS_APPLE)
147
LockSlow()148 void SpinningMutex::LockSlow() {
149 return os_unfair_lock_lock(&unfair_lock_);
150 }
151
152 #elif BUILDFLAG(IS_POSIX)
153
LockSlow()154 void SpinningMutex::LockSlow() {
155 int retval = pthread_mutex_lock(&lock_);
156 PA_DCHECK(retval == 0);
157 }
158
159 #elif BUILDFLAG(IS_FUCHSIA)
160
LockSlow()161 void SpinningMutex::LockSlow() {
162 sync_mutex_lock(&lock_);
163 }
164
165 #endif
166
167 #else // PA_CONFIG(HAS_FAST_MUTEX)
168
LockSlowSpinLock()169 void SpinningMutex::LockSlowSpinLock() {
170 int yield_thread_count = 0;
171 do {
172 if (yield_thread_count < 10) {
173 PA_YIELD_THREAD;
174 yield_thread_count++;
175 } else {
176 // At this point, it's likely that the lock is held by a lower priority
177 // thread that is unavailable to finish its work because of higher
178 // priority threads spinning here. Sleeping should ensure that they make
179 // progress.
180 base::PlatformThread::Sleep(base::Milliseconds(1));
181 }
182 } while (!TrySpinLock());
183 }
184
185 #endif // PA_CONFIG(HAS_FAST_MUTEX)
186
187 } // namespace partition_alloc::internal
188