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