1/*
2 * Copyright 2012-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 * AtomicHashArray is the building block for AtomicHashMap. It provides the
19 * core lock-free functionality, but is limited by the fact that it cannot
20 * grow past its initialization size and is a little more awkward (no public
21 * constructor, for example). If you're confident that you won't run out of
22 * space, don't mind the awkardness, and really need bare-metal performance,
23 * feel free to use AHA directly.
24 *
25 * Check out AtomicHashMap.h for more thorough documentation on perf and
26 * general pros and cons relative to other hash maps.
27 *
28 * @author Spencer Ahrens <sahrens@fb.com>
29 * @author Jordan DeLong <delong.j@fb.com>
30 */
31
32#pragma once
33#define FOLLY_ATOMICHASHARRAY_H_
34
35#include <atomic>
36
37#include <boost/iterator/iterator_facade.hpp>
38#include <boost/noncopyable.hpp>
39
40#include <folly/ThreadCachedInt.h>
41#include <folly/Utility.h>
42#include <folly/hash/Hash.h>
43
44namespace folly {
45
46struct AtomicHashArrayLinearProbeFcn {
47 inline size_t operator()(size_t idx, size_t /* numProbes */, size_t capacity)
48 const {
49 idx += 1; // linear probing
50
51 // Avoid modulus because it's slow
52 return LIKELY(idx < capacity) ? idx : (idx - capacity);
53 }
54};
55
56struct AtomicHashArrayQuadraticProbeFcn {
57 inline size_t operator()(size_t idx, size_t numProbes, size_t capacity)
58 const {
59 idx += numProbes; // quadratic probing
60
61 // Avoid modulus because it's slow
62 return LIKELY(idx < capacity) ? idx : (idx - capacity);
63 }
64};
65
66// Enables specializing checkLegalKey without specializing its class.
67namespace detail {
68template <typename NotKeyT, typename KeyT>
69inline void checkLegalKeyIfKeyTImpl(
70 NotKeyT /* ignored */,
71 KeyT /* emptyKey */,
72 KeyT /* lockedKey */,
73 KeyT /* erasedKey */) {}
74
75template <typename KeyT>
76inline void checkLegalKeyIfKeyTImpl(
77 KeyT key_in,
78 KeyT emptyKey,
79 KeyT lockedKey,
80 KeyT erasedKey) {
81 DCHECK_NE(key_in, emptyKey);
82 DCHECK_NE(key_in, lockedKey);
83 DCHECK_NE(key_in, erasedKey);
84}
85} // namespace detail
86
87template <
88 class KeyT,
89 class ValueT,
90 class HashFcn = std::hash<KeyT>,
91 class EqualFcn = std::equal_to<KeyT>,
92 class Allocator = std::allocator<char>,
93 class ProbeFcn = AtomicHashArrayLinearProbeFcn,
94 class KeyConvertFcn = Identity>
95class AtomicHashMap;
96
97template <
98 class KeyT,
99 class ValueT,
100 class HashFcn = std::hash<KeyT>,
101 class EqualFcn = std::equal_to<KeyT>,
102 class Allocator = std::allocator<char>,
103 class ProbeFcn = AtomicHashArrayLinearProbeFcn,
104 class KeyConvertFcn = Identity>
105class AtomicHashArray : boost::noncopyable {
106 static_assert(
107 (std::is_convertible<KeyT, int32_t>::value ||
108 std::is_convertible<KeyT, int64_t>::value ||
109 std::is_convertible<KeyT, const void*>::value),
110 "You are trying to use AtomicHashArray with disallowed key "
111 "types. You must use atomically compare-and-swappable integer "
112 "keys, or a different container class.");
113
114 public:
115 typedef KeyT key_type;
116 typedef ValueT mapped_type;
117 typedef HashFcn hasher;
118 typedef EqualFcn key_equal;
119 typedef KeyConvertFcn key_convert;
120 typedef std::pair<const KeyT, ValueT> value_type;
121 typedef std::size_t size_type;
122 typedef std::ptrdiff_t difference_type;
123 typedef value_type& reference;
124 typedef const value_type& const_reference;
125 typedef value_type* pointer;
126 typedef const value_type* const_pointer;
127
128 const size_t capacity_;
129 const size_t maxEntries_;
130 const KeyT kEmptyKey_;
131 const KeyT kLockedKey_;
132 const KeyT kErasedKey_;
133
134 template <class ContT, class IterVal>
135 struct aha_iterator;
136
137 typedef aha_iterator<const AtomicHashArray, const value_type> const_iterator;
138 typedef aha_iterator<AtomicHashArray, value_type> iterator;
139
140 // You really shouldn't need this if you use the SmartPtr provided by create,
141 // but if you really want to do something crazy like stick the released
142 // pointer into a DescriminatedPtr or something, you'll need this to clean up
143 // after yourself.
144 static void destroy(AtomicHashArray*);
145
146 private:
147 const size_t kAnchorMask_;
148
149 struct Deleter {
150 void operator()(AtomicHashArray* ptr) {
151 AtomicHashArray::destroy(ptr);
152 }
153 };
154
155 public:
156 typedef std::unique_ptr<AtomicHashArray, Deleter> SmartPtr;
157
158 /*
159 * create --
160 *
161 * Creates AtomicHashArray objects. Use instead of constructor/destructor.
162 *
163 * We do things this way in order to avoid the perf penalty of a second
164 * pointer indirection when composing these into AtomicHashMap, which needs
165 * to store an array of pointers so that it can perform atomic operations on
166 * them when growing.
167 *
168 * Instead of a mess of arguments, we take a max size and a Config struct to
169 * simulate named ctor parameters. The Config struct has sensible defaults
170 * for everything, but is overloaded - if you specify a positive capacity,
171 * that will be used directly instead of computing it based on
172 * maxLoadFactor.
173 *
174 * Create returns an AHA::SmartPtr which is a unique_ptr with a custom
175 * deleter to make sure everything is cleaned up properly.
176 */
177 struct Config {
178 KeyT emptyKey;
179 KeyT lockedKey;
180 KeyT erasedKey;
181 double maxLoadFactor;
182 double growthFactor;
183 uint32_t entryCountThreadCacheSize;
184 size_t capacity; // if positive, overrides maxLoadFactor
185
186 // Cannot have constexpr ctor because some compilers rightly complain.
187 Config()
188 : emptyKey((KeyT)-1),
189 lockedKey((KeyT)-2),
190 erasedKey((KeyT)-3),
191 maxLoadFactor(0.8),
192 growthFactor(-1),
193 entryCountThreadCacheSize(1000),
194 capacity(0) {}
195 };
196
197 // Cannot have pre-instantiated const Config instance because of SIOF.
198 static SmartPtr create(size_t maxSize, const Config& c = Config());
199
200 /*
201 * find --
202 *
203 *
204 * Returns the iterator to the element if found, otherwise end().
205 *
206 * As an optional feature, the type of the key to look up (LookupKeyT) is
207 * allowed to be different from the type of keys actually stored (KeyT).
208 *
209 * This enables use cases where materializing the key is costly and usually
210 * redudant, e.g., canonicalizing/interning a set of strings and being able
211 * to look up by StringPiece. To use this feature, LookupHashFcn must take
212 * a LookupKeyT, and LookupEqualFcn must take KeyT and LookupKeyT as first
213 * and second parameter, respectively.
214 *
215 * See folly/test/ArrayHashArrayTest.cpp for sample usage.
216 */
217 template <
218 typename LookupKeyT = key_type,
219 typename LookupHashFcn = hasher,
220 typename LookupEqualFcn = key_equal>
221 iterator find(LookupKeyT k) {
222 return iterator(
223 this, findInternal<LookupKeyT, LookupHashFcn, LookupEqualFcn>(k).idx);
224 }
225
226 template <
227 typename LookupKeyT = key_type,
228 typename LookupHashFcn = hasher,
229 typename LookupEqualFcn = key_equal>
230 const_iterator find(LookupKeyT k) const {
231 return const_cast<AtomicHashArray*>(this)
232 ->find<LookupKeyT, LookupHashFcn, LookupEqualFcn>(k);
233 }
234
235 /*
236 * insert --
237 *
238 * Returns a pair with iterator to the element at r.first and bool success.
239 * Retrieve the index with ret.first.getIndex().
240 *
241 * Fails on key collision (does not overwrite) or if map becomes
242 * full, at which point no element is inserted, iterator is set to end(),
243 * and success is set false. On collisions, success is set false, but the
244 * iterator is set to the existing entry.
245 */
246 std::pair<iterator, bool> insert(const value_type& r) {
247 return emplace(r.first, r.second);
248 }
249 std::pair<iterator, bool> insert(value_type&& r) {
250 return emplace(r.first, std::move(r.second));
251 }
252
253 /*
254 * emplace --
255 *
256 * Same contract as insert(), but performs in-place construction
257 * of the value type using the specified arguments.
258 *
259 * Also, like find(), this method optionally allows 'key_in' to have a type
260 * different from that stored in the table; see find(). If and only if no
261 * equal key is already present, this method converts 'key_in' to a key of
262 * type KeyT using the provided LookupKeyToKeyFcn.
263 */
264 template <
265 typename LookupKeyT = key_type,
266 typename LookupHashFcn = hasher,
267 typename LookupEqualFcn = key_equal,
268 typename LookupKeyToKeyFcn = key_convert,
269 typename... ArgTs>
270 std::pair<iterator, bool> emplace(LookupKeyT key_in, ArgTs&&... vCtorArgs) {
271 SimpleRetT ret = insertInternal<
272 LookupKeyT,
273 LookupHashFcn,
274 LookupEqualFcn,
275 LookupKeyToKeyFcn>(key_in, std::forward<ArgTs>(vCtorArgs)...);
276 return std::make_pair(iterator(this, ret.idx), ret.success);
277 }
278
279 // returns the number of elements erased - should never exceed 1
280 size_t erase(KeyT k);
281
282 // clears all keys and values in the map and resets all counters. Not thread
283 // safe.
284 void clear();
285
286 // Exact number of elements in the map - note that readFull() acquires a
287 // mutex. See folly/ThreadCachedInt.h for more details.
288 size_t size() const {
289 return numEntries_.readFull() - numErases_.load(std::memory_order_relaxed);
290 }
291
292 bool empty() const {
293 return size() == 0;
294 }
295
296 iterator begin() {
297 iterator it(this, 0);
298 it.advancePastEmpty();
299 return it;
300 }
301 const_iterator begin() const {
302 const_iterator it(this, 0);
303 it.advancePastEmpty();
304 return it;
305 }
306
307 iterator end() {
308 return iterator(this, capacity_);
309 }
310 const_iterator end() const {
311 return const_iterator(this, capacity_);
312 }
313
314 // See AtomicHashMap::findAt - access elements directly
315 // WARNING: The following 2 functions will fail silently for hashtable
316 // with capacity > 2^32
317 iterator findAt(uint32_t idx) {
318 DCHECK_LT(idx, capacity_);
319 return iterator(this, idx);
320 }
321 const_iterator findAt(uint32_t idx) const {
322 return const_cast<AtomicHashArray*>(this)->findAt(idx);
323 }
324
325 iterator makeIter(size_t idx) {
326 return iterator(this, idx);
327 }
328 const_iterator makeIter(size_t idx) const {
329 return const_iterator(this, idx);
330 }
331
332 // The max load factor allowed for this map
333 double maxLoadFactor() const {
334 return ((double)maxEntries_) / capacity_;
335 }
336
337 void setEntryCountThreadCacheSize(uint32_t newSize) {
338 numEntries_.setCacheSize(newSize);
339 numPendingEntries_.setCacheSize(newSize);
340 }
341
342 uint32_t getEntryCountThreadCacheSize() const {
343 return numEntries_.getCacheSize();
344 }
345
346 /* Private data and helper functions... */
347
348 private:
349 friend class AtomicHashMap<
350 KeyT,
351 ValueT,
352 HashFcn,
353 EqualFcn,
354 Allocator,
355 ProbeFcn>;
356
357 struct SimpleRetT {
358 size_t idx;
359 bool success;
360 SimpleRetT(size_t i, bool s) : idx(i), success(s) {}
361 SimpleRetT() = default;
362 };
363
364 template <
365 typename LookupKeyT = key_type,
366 typename LookupHashFcn = hasher,
367 typename LookupEqualFcn = key_equal,
368 typename LookupKeyToKeyFcn = Identity,
369 typename... ArgTs>
370 SimpleRetT insertInternal(LookupKeyT key, ArgTs&&... vCtorArgs);
371
372 template <
373 typename LookupKeyT = key_type,
374 typename LookupHashFcn = hasher,
375 typename LookupEqualFcn = key_equal>
376 SimpleRetT findInternal(const LookupKeyT key);
377
378 template <typename MaybeKeyT>
379 void checkLegalKeyIfKey(MaybeKeyT key) {
380 detail::checkLegalKeyIfKeyTImpl(key, kEmptyKey_, kLockedKey_, kErasedKey_);
381 }
382
383 static std::atomic<KeyT>* cellKeyPtr(const value_type& r) {
384 // We need some illegal casting here in order to actually store
385 // our value_type as a std::pair<const,>. But a little bit of
386 // undefined behavior never hurt anyone ...
387 static_assert(
388 sizeof(std::atomic<KeyT>) == sizeof(KeyT),
389 "std::atomic is implemented in an unexpected way for AHM");
390 return const_cast<std::atomic<KeyT>*>(
391 reinterpret_cast<std::atomic<KeyT> const*>(&r.first));
392 }
393
394 static KeyT relaxedLoadKey(const value_type& r) {
395 return cellKeyPtr(r)->load(std::memory_order_relaxed);
396 }
397
398 static KeyT acquireLoadKey(const value_type& r) {
399 return cellKeyPtr(r)->load(std::memory_order_acquire);
400 }
401
402 // Fun with thread local storage - atomic increment is expensive
403 // (relatively), so we accumulate in the thread cache and periodically
404 // flush to the actual variable, and walk through the unflushed counts when
405 // reading the value, so be careful of calling size() too frequently. This
406 // increases insertion throughput several times over while keeping the count
407 // accurate.
408 ThreadCachedInt<uint64_t> numEntries_; // Successful key inserts
409 ThreadCachedInt<uint64_t> numPendingEntries_; // Used by insertInternal
410 std::atomic<int64_t> isFull_; // Used by insertInternal
411 std::atomic<int64_t> numErases_; // Successful key erases
412
413 value_type cells_[0]; // This must be the last field of this class
414
415 // Force constructor/destructor private since create/destroy should be
416 // used externally instead
417 AtomicHashArray(
418 size_t capacity,
419 KeyT emptyKey,
420 KeyT lockedKey,
421 KeyT erasedKey,
422 double maxLoadFactor,
423 uint32_t cacheSize);
424
425 ~AtomicHashArray() = default;
426
427 inline void unlockCell(value_type* const cell, KeyT newKey) {
428 cellKeyPtr(*cell)->store(newKey, std::memory_order_release);
429 }
430
431 inline bool tryLockCell(value_type* const cell) {
432 KeyT expect = kEmptyKey_;
433 return cellKeyPtr(*cell)->compare_exchange_strong(
434 expect, kLockedKey_, std::memory_order_acq_rel);
435 }
436
437 template <class LookupKeyT = key_type, class LookupHashFcn = hasher>
438 inline size_t keyToAnchorIdx(const LookupKeyT k) const {
439 const size_t hashVal = LookupHashFcn()(k);
440 const size_t probe = hashVal & kAnchorMask_;
441 return LIKELY(probe < capacity_) ? probe : hashVal % capacity_;
442 }
443
444}; // AtomicHashArray
445
446} // namespace folly
447
448#include <folly/AtomicHashArray-inl.h>
449