1 | /* |
2 | * Copyright 2016-present Facebook, Inc. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | #pragma once |
18 | |
19 | #include <cassert> |
20 | #include <climits> |
21 | #include <cstdint> |
22 | |
23 | #include <folly/Portability.h> |
24 | #include <folly/detail/Futex.h> |
25 | |
26 | #if defined(__clang__) |
27 | #define NO_SANITIZE_ADDRESS __attribute__((no_sanitize_address)) |
28 | #else |
29 | #define NO_SANITIZE_ADDRESS |
30 | #endif |
31 | |
32 | namespace folly { |
33 | |
34 | /** |
35 | * Tiny exclusive lock that packs four lock slots into a single |
36 | * byte. Each slot is an independent real, sleeping lock. The default |
37 | * lock and unlock functions operate on slot zero, which modifies only |
38 | * the low two bits of the host byte. |
39 | * |
40 | * You should zero-initialize the bits of a MicroLock that you intend |
41 | * to use. |
42 | * |
43 | * If you're not space-constrained, prefer std::mutex, which will |
44 | * likely be faster, since it has more than two bits of information to |
45 | * work with. |
46 | * |
47 | * You are free to put a MicroLock in a union with some other object. |
48 | * If, for example, you want to use the bottom two bits of a pointer |
49 | * as a lock, you can put a MicroLock in a union with the pointer and |
50 | * limit yourself to MicroLock slot zero, which will use the two |
51 | * least-significant bits in the bottom byte. |
52 | * |
53 | * (Note that such a union is safe only because MicroLock is based on |
54 | * a character type, and even under a strict interpretation of C++'s |
55 | * aliasing rules, character types may alias anything.) |
56 | * |
57 | * MicroLock uses a dirty trick: it actually operates on the full |
58 | * 32-bit, four-byte-aligned bit of memory into which it is embedded. |
59 | * It never modifies bits outside the ones it's defined to modify, but |
60 | * it _accesses_ all the bits in the 32-bit memory location for |
61 | * purposes of futex management. |
62 | * |
63 | * The MaxSpins template parameter controls the number of times we |
64 | * spin trying to acquire the lock. MaxYields controls the number of |
65 | * times we call sched_yield; once we've tried to acquire the lock |
66 | * MaxSpins + MaxYields times, we sleep on the lock futex. |
67 | * By adjusting these parameters, you can make MicroLock behave as |
68 | * much or as little like a conventional spinlock as you'd like. |
69 | * |
70 | * Performance |
71 | * ----------- |
72 | * |
73 | * With the default template options, the timings for uncontended |
74 | * acquire-then-release come out as follows on Intel(R) Xeon(R) CPU |
75 | * E5-2660 0 @ 2.20GHz, in @mode/opt, as of the master tree at Tue, 01 |
76 | * Mar 2016 19:48:15. |
77 | * |
78 | * ======================================================================== |
79 | * folly/test/SmallLocksBenchmark.cpp relative time/iter iters/s |
80 | * ======================================================================== |
81 | * MicroSpinLockUncontendedBenchmark 13.46ns 74.28M |
82 | * PicoSpinLockUncontendedBenchmark 14.99ns 66.71M |
83 | * MicroLockUncontendedBenchmark 27.06ns 36.96M |
84 | * StdMutexUncontendedBenchmark 25.18ns 39.72M |
85 | * VirtualFunctionCall 1.72ns 579.78M |
86 | * ======================================================================== |
87 | * |
88 | * (The virtual dispatch benchmark is provided for scale.) |
89 | * |
90 | * While the uncontended case for MicroLock is competitive with the |
91 | * glibc 2.2.0 implementation of std::mutex, std::mutex is likely to be |
92 | * faster in the contended case, because we need to wake up all waiters |
93 | * when we release. |
94 | * |
95 | * Make sure to benchmark your particular workload. |
96 | * |
97 | */ |
98 | |
99 | class MicroLockCore { |
100 | protected: |
101 | #if defined(__SANITIZE_ADDRESS__) && !defined(__clang__) && \ |
102 | (defined(__GNUC__) || defined(__GNUG__)) |
103 | uint32_t lock_; |
104 | #else |
105 | uint8_t lock_; |
106 | #endif |
107 | inline detail::Futex<>* word() const; // Well, halfword on 64-bit systems |
108 | inline uint32_t baseShift(unsigned slot) const; |
109 | inline uint32_t heldBit(unsigned slot) const; |
110 | inline uint32_t waitBit(unsigned slot) const; |
111 | static void lockSlowPath( |
112 | uint32_t oldWord, |
113 | detail::Futex<>* wordPtr, |
114 | uint32_t slotHeldBit, |
115 | unsigned maxSpins, |
116 | unsigned maxYields); |
117 | |
118 | public: |
119 | inline void unlock(unsigned slot) NO_SANITIZE_ADDRESS; |
120 | inline void unlock() { |
121 | unlock(0); |
122 | } |
123 | // Initializes all the slots. |
124 | inline void init() { |
125 | lock_ = 0; |
126 | } |
127 | }; |
128 | |
129 | inline detail::Futex<>* MicroLockCore::word() const { |
130 | uintptr_t lockptr = (uintptr_t)&lock_; |
131 | lockptr &= ~(sizeof(uint32_t) - 1); |
132 | return (detail::Futex<>*)lockptr; |
133 | } |
134 | |
135 | inline unsigned MicroLockCore::baseShift(unsigned slot) const { |
136 | assert(slot < CHAR_BIT / 2); |
137 | |
138 | unsigned offset_bytes = (unsigned)((uintptr_t)&lock_ - (uintptr_t)word()); |
139 | |
140 | return ( |
141 | unsigned)(kIsLittleEndian ? offset_bytes * CHAR_BIT + slot * 2 : CHAR_BIT * (sizeof(uint32_t) - offset_bytes - 1) + slot * 2); |
142 | } |
143 | |
144 | inline uint32_t MicroLockCore::heldBit(unsigned slot) const { |
145 | return 1U << (baseShift(slot) + 0); |
146 | } |
147 | |
148 | inline uint32_t MicroLockCore::waitBit(unsigned slot) const { |
149 | return 1U << (baseShift(slot) + 1); |
150 | } |
151 | |
152 | void MicroLockCore::unlock(unsigned slot) { |
153 | detail::Futex<>* wordPtr = word(); |
154 | uint32_t oldWord; |
155 | uint32_t newWord; |
156 | |
157 | oldWord = wordPtr->load(std::memory_order_relaxed); |
158 | do { |
159 | assert(oldWord & heldBit(slot)); |
160 | newWord = oldWord & ~(heldBit(slot) | waitBit(slot)); |
161 | } while (!wordPtr->compare_exchange_weak( |
162 | oldWord, newWord, std::memory_order_release, std::memory_order_relaxed)); |
163 | |
164 | if (oldWord & waitBit(slot)) { |
165 | detail::futexWake(wordPtr, 1, heldBit(slot)); |
166 | } |
167 | } |
168 | |
169 | template <unsigned MaxSpins = 1000, unsigned MaxYields = 0> |
170 | class MicroLockBase : public MicroLockCore { |
171 | public: |
172 | inline void lock(unsigned slot) NO_SANITIZE_ADDRESS; |
173 | inline void lock() { |
174 | lock(0); |
175 | } |
176 | inline bool try_lock(unsigned slot) NO_SANITIZE_ADDRESS; |
177 | inline bool try_lock() { |
178 | return try_lock(0); |
179 | } |
180 | }; |
181 | |
182 | template <unsigned MaxSpins, unsigned MaxYields> |
183 | bool MicroLockBase<MaxSpins, MaxYields>::try_lock(unsigned slot) { |
184 | // N.B. You might think that try_lock is just the fast path of lock, |
185 | // but you'd be wrong. Keep in mind that other parts of our host |
186 | // word might be changing while we take the lock! We're not allowed |
187 | // to fail spuriously if the lock is in fact not held, even if other |
188 | // people are concurrently modifying other parts of the word. |
189 | // |
190 | // We need to loop until we either see firm evidence that somebody |
191 | // else has the lock (by looking at heldBit) or see our CAS succeed. |
192 | // A failed CAS by itself does not indicate lock-acquire failure. |
193 | |
194 | detail::Futex<>* wordPtr = word(); |
195 | uint32_t oldWord = wordPtr->load(std::memory_order_relaxed); |
196 | do { |
197 | if (oldWord & heldBit(slot)) { |
198 | return false; |
199 | } |
200 | } while (!wordPtr->compare_exchange_weak( |
201 | oldWord, |
202 | oldWord | heldBit(slot), |
203 | std::memory_order_acquire, |
204 | std::memory_order_relaxed)); |
205 | |
206 | return true; |
207 | } |
208 | |
209 | template <unsigned MaxSpins, unsigned MaxYields> |
210 | void MicroLockBase<MaxSpins, MaxYields>::lock(unsigned slot) { |
211 | static_assert(MaxSpins + MaxYields < (unsigned)-1, "overflow" ); |
212 | |
213 | detail::Futex<>* wordPtr = word(); |
214 | uint32_t oldWord; |
215 | oldWord = wordPtr->load(std::memory_order_relaxed); |
216 | if ((oldWord & heldBit(slot)) == 0 && |
217 | wordPtr->compare_exchange_weak( |
218 | oldWord, |
219 | oldWord | heldBit(slot), |
220 | std::memory_order_acquire, |
221 | std::memory_order_relaxed)) { |
222 | // Fast uncontended case: memory_order_acquire above is our barrier |
223 | } else { |
224 | // lockSlowPath doesn't have any slot-dependent computation; it |
225 | // just shifts the input bit. Make sure its shifting produces the |
226 | // same result a call to waitBit for our slot would. |
227 | assert(heldBit(slot) << 1 == waitBit(slot)); |
228 | // lockSlowPath emits its own memory barrier |
229 | lockSlowPath(oldWord, wordPtr, heldBit(slot), MaxSpins, MaxYields); |
230 | } |
231 | } |
232 | |
233 | typedef MicroLockBase<> MicroLock; |
234 | } // namespace folly |
235 | |