1 /*
2 * Copyright (c) Facebook, Inc. and its affiliates.
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 <array>
20 #include <atomic>
21 #include <cassert>
22 #include <cstddef>
23 #include <limits>
24
25 #include <folly/Portability.h>
26
27 namespace folly {
28
29 /**
30 * An atomic bitset of fixed size (specified at compile time).
31 *
32 * Formerly known as AtomicBitSet. It was renamed while fixing a bug
33 * to avoid any silent breakages during run time.
34 */
35 template <size_t N>
36 class ConcurrentBitSet {
37 public:
38 /**
39 * Construct a ConcurrentBitSet; all bits are initially false.
40 */
41 ConcurrentBitSet();
42
43 ConcurrentBitSet(const ConcurrentBitSet&) = delete;
44 ConcurrentBitSet& operator=(const ConcurrentBitSet&) = delete;
45
46 /**
47 * Set bit idx to true, using the given memory order. Returns the
48 * previous value of the bit.
49 *
50 * Note that the operation is a read-modify-write operation due to the use
51 * of fetch_or.
52 */
53 bool set(size_t idx, std::memory_order order = std::memory_order_seq_cst);
54
55 /**
56 * Set bit idx to false, using the given memory order. Returns the
57 * previous value of the bit.
58 *
59 * Note that the operation is a read-modify-write operation due to the use
60 * of fetch_and.
61 */
62 bool reset(size_t idx, std::memory_order order = std::memory_order_seq_cst);
63
64 /**
65 * Set bit idx to the given value, using the given memory order. Returns
66 * the previous value of the bit.
67 *
68 * Note that the operation is a read-modify-write operation due to the use
69 * of fetch_and or fetch_or.
70 *
71 * Yes, this is an overload of set(), to keep as close to std::bitset's
72 * interface as possible.
73 */
74 bool set(
75 size_t idx,
76 bool value,
77 std::memory_order order = std::memory_order_seq_cst);
78
79 /**
80 * Read bit idx.
81 */
82 bool test(
83 size_t idx, std::memory_order order = std::memory_order_seq_cst) const;
84
85 /**
86 * Same as test() with the default memory order.
87 */
88 bool operator[](size_t idx) const;
89
90 /**
91 * Return the size of the bitset.
92 */
size()93 constexpr size_t size() const { return N; }
94
95 private:
96 // Pick the largest lock-free type available
97 #if (ATOMIC_LLONG_LOCK_FREE == 2)
98 typedef unsigned long long BlockType;
99 #elif (ATOMIC_LONG_LOCK_FREE == 2)
100 typedef unsigned long BlockType;
101 #else
102 // Even if not lock free, what can we do?
103 typedef unsigned int BlockType;
104 #endif
105 typedef std::atomic<BlockType> AtomicBlockType;
106
107 static constexpr size_t kBitsPerBlock =
108 std::numeric_limits<BlockType>::digits;
109
blockIndex(size_t bit)110 static constexpr size_t blockIndex(size_t bit) { return bit / kBitsPerBlock; }
111
bitOffset(size_t bit)112 static constexpr size_t bitOffset(size_t bit) { return bit % kBitsPerBlock; }
113
114 // avoid casts
115 static constexpr BlockType kOne = 1;
116 static constexpr size_t kNumBlocks = (N + kBitsPerBlock - 1) / kBitsPerBlock;
117 std::array<AtomicBlockType, kNumBlocks> data_;
118 };
119
120 // value-initialize to zero
121 template <size_t N>
ConcurrentBitSet()122 inline ConcurrentBitSet<N>::ConcurrentBitSet() : data_() {}
123
124 template <size_t N>
set(size_t idx,std::memory_order order)125 inline bool ConcurrentBitSet<N>::set(size_t idx, std::memory_order order) {
126 assert(idx < N);
127 BlockType mask = kOne << bitOffset(idx);
128 return data_[blockIndex(idx)].fetch_or(mask, order) & mask;
129 }
130
131 template <size_t N>
reset(size_t idx,std::memory_order order)132 inline bool ConcurrentBitSet<N>::reset(size_t idx, std::memory_order order) {
133 assert(idx < N);
134 BlockType mask = kOne << bitOffset(idx);
135 return data_[blockIndex(idx)].fetch_and(~mask, order) & mask;
136 }
137
138 template <size_t N>
set(size_t idx,bool value,std::memory_order order)139 inline bool ConcurrentBitSet<N>::set(
140 size_t idx, bool value, std::memory_order order) {
141 return value ? set(idx, order) : reset(idx, order);
142 }
143
144 template <size_t N>
test(size_t idx,std::memory_order order)145 inline bool ConcurrentBitSet<N>::test(
146 size_t idx, std::memory_order order) const {
147 assert(idx < N);
148 BlockType mask = kOne << bitOffset(idx);
149 return data_[blockIndex(idx)].load(order) & mask;
150 }
151
152 template <size_t N>
153 inline bool ConcurrentBitSet<N>::operator[](size_t idx) const {
154 return test(idx);
155 }
156
157 } // namespace folly
158