1/*
2 * Copyright 2015-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/*
18 * N.B. You most likely do _not_ want to use PicoSpinLock or any other
19 * kind of spinlock. Consider MicroLock instead.
20 *
21 * In short, spinlocks in preemptive multi-tasking operating systems
22 * have serious problems and fast mutexes like std::mutex are almost
23 * certainly the better choice, because letting the OS scheduler put a
24 * thread to sleep is better for system responsiveness and throughput
25 * than wasting a timeslice repeatedly querying a lock held by a
26 * thread that's blocked, and you can't prevent userspace
27 * programs blocking.
28 *
29 * Spinlocks in an operating system kernel make much more sense than
30 * they do in userspace.
31 */
32
33#pragma once
34#define FOLLY_PICO_SPIN_LOCK_H_
35
36/*
37 * @author Keith Adams <kma@fb.com>
38 * @author Jordan DeLong <delong.j@fb.com>
39 */
40
41#include <array>
42#include <atomic>
43#include <cinttypes>
44#include <cstdlib>
45#include <mutex>
46#include <type_traits>
47
48#include <glog/logging.h>
49
50#include <folly/Portability.h>
51#include <folly/synchronization/AtomicUtil.h>
52#include <folly/synchronization/detail/Sleeper.h>
53
54namespace folly {
55
56/*
57 * Spin lock on a single bit in an integral type. You can use this
58 * with 16, 32, or 64-bit integral types.
59 *
60 * This is useful if you want a small lock and already have an int
61 * with a bit in it that you aren't using. But note that it can't be
62 * as small as MicroSpinLock (1 byte), if you don't already have a
63 * convenient int with an unused bit lying around to put it on.
64 *
65 * To construct these, either use init() or zero initialize. We don't
66 * have a real constructor because we want this to be a POD type so we
67 * can put it into packed structs.
68 */
69template <class IntType, int Bit = sizeof(IntType) * 8 - 1>
70struct PicoSpinLock {
71 // Internally we deal with the unsigned version of the type.
72 typedef typename std::make_unsigned<IntType>::type UIntType;
73
74 static_assert(
75 std::is_integral<IntType>::value,
76 "PicoSpinLock needs an integral type");
77 static_assert(
78 sizeof(IntType) == 2 || sizeof(IntType) == 4 || sizeof(IntType) == 8,
79 "PicoSpinLock can't work on integers smaller than 2 bytes");
80
81 public:
82 static const UIntType kLockBitMask_ = UIntType(1) << Bit;
83 mutable UIntType lock_;
84
85 /*
86 * You must call this function before using this class, if you
87 * default constructed it. If you zero-initialized it you can
88 * assume the PicoSpinLock is in a valid unlocked state with
89 * getData() == 0.
90 *
91 * (This doesn't use a constructor because we want to be a POD.)
92 */
93 void init(IntType initialValue = 0) {
94 CHECK(!(initialValue & kLockBitMask_));
95 reinterpret_cast<std::atomic<UIntType>*>(&lock_)->store(
96 UIntType(initialValue), std::memory_order_release);
97 }
98
99 /*
100 * Returns the value of the integer we using for our lock, except
101 * with the bit we are using as a lock cleared, regardless of
102 * whether the lock is held.
103 *
104 * It is 'safe' to call this without holding the lock. (As in: you
105 * get the same guarantees for simultaneous accesses to an integer
106 * as you normally get.)
107 */
108 IntType getData() const {
109 auto res = reinterpret_cast<std::atomic<UIntType>*>(&lock_)->load(
110 std::memory_order_relaxed) &
111 ~kLockBitMask_;
112 return res;
113 }
114
115 /*
116 * Set the value of the other bits in our integer.
117 *
118 * Don't use this when you aren't holding the lock, unless it can be
119 * guaranteed that no other threads may be trying to use this.
120 */
121 void setData(IntType w) {
122 CHECK(!(w & kLockBitMask_));
123 auto l = reinterpret_cast<std::atomic<UIntType>*>(&lock_);
124 l->store(
125 (l->load(std::memory_order_relaxed) & kLockBitMask_) | w,
126 std::memory_order_relaxed);
127 }
128
129 /*
130 * Try to get the lock without blocking: returns whether or not we
131 * got it.
132 */
133 bool try_lock() const {
134 auto previous = atomic_fetch_set(
135 *reinterpret_cast<std::atomic<UIntType>*>(&lock_),
136 Bit,
137 std::memory_order_acquire);
138 return !previous;
139 }
140
141 /*
142 * Block until we can acquire the lock. Uses Sleeper to wait.
143 */
144 void lock() const {
145 detail::Sleeper sleeper;
146 while (!try_lock()) {
147 sleeper.wait();
148 }
149 }
150
151 /*
152 * Release the lock, without changing the value of the rest of the
153 * integer.
154 */
155 void unlock() const {
156 auto previous = atomic_fetch_reset(
157 *reinterpret_cast<std::atomic<UIntType>*>(&lock_),
158 Bit,
159 std::memory_order_release);
160 DCHECK(previous);
161 }
162};
163
164} // namespace folly
165