Bitcoin ABC  0.22.13
P2P Digital Currency
cuckoocache.h
Go to the documentation of this file.
1 // Copyright (c) 2016 Jeremy Rubin
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #ifndef BITCOIN_CUCKOOCACHE_H
6 #define BITCOIN_CUCKOOCACHE_H
7 
8 #include <algorithm> // std::find
9 #include <array>
10 #include <atomic>
11 #include <cmath>
12 #include <cstring>
13 #include <memory>
14 #include <utility>
15 #include <vector>
16 
29 namespace CuckooCache {
44  std::unique_ptr<std::atomic<uint8_t>[]> mem;
45 
46 public:
48  bit_packed_atomic_flags() = delete;
49 
61  explicit bit_packed_atomic_flags(uint32_t size) {
62  // pad out the size if needed
63  size = (size + 7) / 8;
64  mem.reset(new std::atomic<uint8_t>[size]);
65  for (uint32_t i = 0; i < size; ++i) {
66  mem[i].store(0xFF);
67  }
68  };
69 
80  inline void setup(uint32_t b) {
82  std::swap(mem, d.mem);
83  }
84 
92  inline void bit_set(uint32_t s) {
93  mem[s >> 3].fetch_or(1 << (s & 7), std::memory_order_relaxed);
94  }
95 
103  inline void bit_unset(uint32_t s) {
104  mem[s >> 3].fetch_and(~(1 << (s & 7)), std::memory_order_relaxed);
105  }
106 
113  inline bool bit_is_set(uint32_t s) const {
114  return (1 << (s & 7)) & mem[s >> 3].load(std::memory_order_relaxed);
115  }
116 };
117 
162 template <typename Element, typename Hash> class cache {
163 private:
165  std::vector<Element> table;
166 
168  uint32_t size;
169 
175 
181  mutable std::vector<bool> epoch_flags;
182 
190 
200  uint32_t epoch_size;
201 
206  uint8_t depth_limit;
207 
214 
218  using Key = typename Element::KeyType;
219 
264  inline std::array<uint32_t, 8> compute_hashes(const Key &k) const {
265  return {{uint32_t(uint64_t(hash_function.template operator()<0>(k)) *
266  uint64_t(size) >>
267  32),
268  uint32_t(uint64_t(hash_function.template operator()<1>(k)) *
269  uint64_t(size) >>
270  32),
271  uint32_t(uint64_t(hash_function.template operator()<2>(k)) *
272  uint64_t(size) >>
273  32),
274  uint32_t(uint64_t(hash_function.template operator()<3>(k)) *
275  uint64_t(size) >>
276  32),
277  uint32_t(uint64_t(hash_function.template operator()<4>(k)) *
278  uint64_t(size) >>
279  32),
280  uint32_t(uint64_t(hash_function.template operator()<5>(k)) *
281  uint64_t(size) >>
282  32),
283  uint32_t(uint64_t(hash_function.template operator()<6>(k)) *
284  uint64_t(size) >>
285  32),
286  uint32_t(uint64_t(hash_function.template operator()<7>(k)) *
287  uint64_t(size) >>
288  32)}};
289  }
290 
295  constexpr uint32_t invalid() const { return ~uint32_t(0); }
296 
302  inline void allow_erase(uint32_t n) const { collection_flags.bit_set(n); }
303 
309  inline void please_keep(uint32_t n) const { collection_flags.bit_unset(n); }
310 
321  void epoch_check() {
322  if (epoch_heuristic_counter != 0) {
323  --epoch_heuristic_counter;
324  return;
325  }
326  // count the number of elements from the latest epoch which have not
327  // been erased.
328  uint32_t epoch_unused_count = 0;
329  for (uint32_t i = 0; i < size; ++i) {
330  epoch_unused_count +=
331  epoch_flags[i] && !collection_flags.bit_is_set(i);
332  }
333  // If there are more non-deleted entries in the current epoch than the
334  // epoch size, then allow_erase on all elements in the old epoch (marked
335  // false) and move all elements in the current epoch to the old epoch
336  // but do not call allow_erase on their indices.
337  if (epoch_unused_count >= epoch_size) {
338  for (uint32_t i = 0; i < size; ++i) {
339  if (epoch_flags[i]) {
340  epoch_flags[i] = false;
341  } else {
342  allow_erase(i);
343  }
344  }
345  epoch_heuristic_counter = epoch_size;
346  } else {
347  // reset the epoch_heuristic_counter to next do a scan when worst
348  // case behavior (no intermittent erases) would exceed epoch size,
349  // with a reasonable minimum scan size. Ordinarily, we would have to
350  // sanity check std::min(epoch_size, epoch_unused_count), but we
351  // already know that `epoch_unused_count < epoch_size` in this
352  // branch
353  epoch_heuristic_counter = std::max(
354  1u, std::max(epoch_size / 16, epoch_size - epoch_unused_count));
355  }
356  }
357 
358 public:
364  : table(), size(), collection_flags(0), epoch_flags(),
365  epoch_heuristic_counter(), epoch_size(), depth_limit(0),
366  hash_function() {}
367 
377  uint32_t setup(uint32_t new_size) {
378  // depth_limit must be at least one otherwise errors can occur.
379  depth_limit = static_cast<uint8_t>(
380  std::log2(static_cast<float>(std::max((uint32_t)2, new_size))));
381  size = std::max<uint32_t>(2, new_size);
382  table.resize(size);
383  collection_flags.setup(size);
384  epoch_flags.resize(size);
385  // Set to 45% as described above
386  epoch_size = std::max((uint32_t)1, (45 * size) / 100);
387  // Initially set to wait for a whole epoch
388  epoch_heuristic_counter = epoch_size;
389  return size;
390  }
391 
405  uint32_t setup_bytes(size_t bytes) {
406  return setup(bytes / sizeof(Element));
407  }
408 
434  inline void insert(Element e, bool replace = false) {
435  epoch_check();
436  uint32_t last_loc = invalid();
437  bool last_epoch = true;
438  std::array<uint32_t, 8> locs = compute_hashes(e.getKey());
439  // Make sure we have not already inserted this element.
440  // If we have, make sure that it does not get deleted.
441  for (const uint32_t loc : locs) {
442  if (table[loc].getKey() == e.getKey()) {
443  if (replace) {
444  table[loc] = std::move(e);
445  }
446  please_keep(loc);
447  epoch_flags[loc] = last_epoch;
448  return;
449  }
450  }
451  for (uint8_t depth = 0; depth < depth_limit; ++depth) {
452  // First try to insert to an empty slot, if one exists
453  for (const uint32_t loc : locs) {
454  if (!collection_flags.bit_is_set(loc)) {
455  continue;
456  }
457  table[loc] = std::move(e);
458  please_keep(loc);
459  epoch_flags[loc] = last_epoch;
460  return;
461  }
477  last_loc =
478  locs[(1 + (std::find(locs.begin(), locs.end(), last_loc) -
479  locs.begin())) &
480  7];
481  std::swap(table[last_loc], e);
482  // Can't std::swap a std::vector<bool>::reference and a bool&.
483  bool epoch = last_epoch;
484  last_epoch = epoch_flags[last_loc];
485  epoch_flags[last_loc] = epoch;
486 
487  // Recompute the locs -- unfortunately happens one too many times!
488  locs = compute_hashes(e.getKey());
489  }
490  }
491 
520  bool contains(const Key &k, const bool erase) const {
521  return find(k, erase) != nullptr;
522  }
523 
536  bool get(Element &e, const bool erase) const {
537  if (const Element *eptr = find(e.getKey(), erase)) {
538  e = *eptr;
539  return true;
540  }
541 
542  return false;
543  }
544 
545 private:
546  const Element *find(const Key &k, const bool erase) const {
547  std::array<uint32_t, 8> locs = compute_hashes(k);
548  for (const uint32_t loc : locs) {
549  if (table[loc].getKey() == k) {
550  if (erase) {
551  allow_erase(loc);
552  }
553  return &table[loc];
554  }
555  }
556  return nullptr;
557  }
558 };
559 
563 template <typename T> struct KeyOnly : public T {
564  // For contains.
565  using KeyType = T;
566 
567  // Ensure implicit conversion from T.
568  KeyOnly() = default;
569  KeyOnly(const T &x) : T(x) {}
570 
571  // Implement required features.
572  const T &getKey() const { return *this; }
573 };
574 
575 } // namespace CuckooCache
576 
577 #endif // BITCOIN_CUCKOOCACHE_H
typename Element::KeyType Key
Key is the key type for this map or set.
Definition: cuckoocache.h:218
bool bit_is_set(uint32_t s) const
bit_is_set queries the table for discardability at s.
Definition: cuckoocache.h:113
void insert(Element e, bool replace=false)
insert loops at most depth_limit times trying to insert a hash at various locations in the table via ...
Definition: cuckoocache.h:434
void please_keep(uint32_t n) const
please_keep marks the element at index n as an entry that should be kept.
Definition: cuckoocache.h:309
std::unique_ptr< std::atomic< uint8_t >[]> mem
Definition: cuckoocache.h:44
KeyOnly(const T &x)
Definition: cuckoocache.h:569
bit_packed_atomic_flags(uint32_t size)
bit_packed_atomic_flags constructor creates memory to sufficiently keep track of garbage collection i...
Definition: cuckoocache.h:61
cache implements a cache with properties similar to a cuckoo-set.
Definition: cuckoocache.h:162
void bit_set(uint32_t s)
bit_set sets an entry as discardable.
Definition: cuckoocache.h:92
uint32_t epoch_size
epoch_size is set to be the number of elements supposed to be in a epoch.
Definition: cuckoocache.h:200
std::vector< bool > epoch_flags
epoch_flags tracks how recently an element was inserted into the cache.
Definition: cuckoocache.h:181
const Hash hash_function
hash_function is a const instance of the hash function.
Definition: cuckoocache.h:213
const T & getKey() const
Definition: cuckoocache.h:572
bit_packed_atomic_flags implements a container for garbage collection flags that is only thread unsaf...
Definition: cuckoocache.h:43
cache()
You must always construct a cache with some elements via a subsequent call to setup or setup_bytes...
Definition: cuckoocache.h:363
std::array< uint32_t, 8 > compute_hashes(const Key &k) const
compute_hashes is convenience for not having to write out this expression everywhere we use the hash ...
Definition: cuckoocache.h:264
uint32_t size
size stores the total available slots in the hash table
Definition: cuckoocache.h:168
uint8_t depth_limit
depth_limit determines how many elements insert should try to replace.
Definition: cuckoocache.h:206
uint32_t epoch_heuristic_counter
epoch_heuristic_counter is used to determine when an epoch might be aged & an expensive scan should b...
Definition: cuckoocache.h:189
uint256 Hash(const T1 pbegin, const T1 pend)
Compute the 256-bit hash of an object.
Definition: hash.h:72
Helper class used when we only want the cache to be a set rather than a map.
Definition: cuckoocache.h:563
uint32_t setup_bytes(size_t bytes)
setup_bytes is a convenience function which accounts for internal memory usage when deciding how many...
Definition: cuckoocache.h:405
std::vector< Element > table
table stores all the elements
Definition: cuckoocache.h:165
High-performance cache primitives.
Definition: cuckoocache.h:29
void epoch_check()
epoch_check handles the changing of epochs for elements stored in the cache.
Definition: cuckoocache.h:321
void allow_erase(uint32_t n) const
allow_erase marks the element at index n as discardable.
Definition: cuckoocache.h:302
bit_packed_atomic_flags collection_flags
The bit_packed_atomic_flags array is marked mutable because we want garbage collection to be allowed ...
Definition: cuckoocache.h:174
uint32_t setup(uint32_t new_size)
setup initializes the container to store no more than new_size elements.
Definition: cuckoocache.h:377
void bit_unset(uint32_t s)
bit_unset marks an entry as something that should not be overwritten.
Definition: cuckoocache.h:103
bool contains(const Key &k, const bool erase) const
contains iterates through the hash locations for a given element and checks to see if it is present...
Definition: cuckoocache.h:520
constexpr uint32_t invalid() const
invalid returns a special index that can never be inserted to
Definition: cuckoocache.h:295
const Element * find(const Key &k, const bool erase) const
Definition: cuckoocache.h:546
void setup(uint32_t b)
setup marks all entries and ensures that bit_packed_atomic_flags can store at least b entries...
Definition: cuckoocache.h:80
bit_packed_atomic_flags()=delete
No default constructor, as there must be some size.