Bitcoin Core  0.20.99
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 
17 
27 namespace CuckooCache
28 {
42 {
43  std::unique_ptr<std::atomic<uint8_t>[]> mem;
44 
45 public:
47  bit_packed_atomic_flags() = delete;
48 
60  explicit bit_packed_atomic_flags(uint32_t size)
61  {
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 
78  inline void setup(uint32_t b)
79  {
81  std::swap(mem, d.mem);
82  }
83 
90  inline void bit_set(uint32_t s)
91  {
92  mem[s >> 3].fetch_or(1 << (s & 7), std::memory_order_relaxed);
93  }
94 
101  inline void bit_unset(uint32_t s)
102  {
103  mem[s >> 3].fetch_and(~(1 << (s & 7)), std::memory_order_relaxed);
104  }
105 
111  inline bool bit_is_set(uint32_t s) const
112  {
113  return (1 << (s & 7)) & mem[s >> 3].load(std::memory_order_relaxed);
114  }
115 };
116 
157 template <typename Element, typename Hash>
158 class cache
159 {
160 private:
162  std::vector<Element> table;
163 
165  uint32_t size;
166 
170 
175  mutable std::vector<bool> epoch_flags;
176 
183 
192  uint32_t epoch_size;
193 
197  uint8_t depth_limit;
198 
204 
242  inline std::array<uint32_t, 8> compute_hashes(const Element& e) const
243  {
244  return {{(uint32_t)(((uint64_t)hash_function.template operator()<0>(e) * (uint64_t)size) >> 32),
245  (uint32_t)(((uint64_t)hash_function.template operator()<1>(e) * (uint64_t)size) >> 32),
246  (uint32_t)(((uint64_t)hash_function.template operator()<2>(e) * (uint64_t)size) >> 32),
247  (uint32_t)(((uint64_t)hash_function.template operator()<3>(e) * (uint64_t)size) >> 32),
248  (uint32_t)(((uint64_t)hash_function.template operator()<4>(e) * (uint64_t)size) >> 32),
249  (uint32_t)(((uint64_t)hash_function.template operator()<5>(e) * (uint64_t)size) >> 32),
250  (uint32_t)(((uint64_t)hash_function.template operator()<6>(e) * (uint64_t)size) >> 32),
251  (uint32_t)(((uint64_t)hash_function.template operator()<7>(e) * (uint64_t)size) >> 32)}};
252  }
253 
256  constexpr uint32_t invalid() const
257  {
258  return ~(uint32_t)0;
259  }
260 
265  inline void allow_erase(uint32_t n) const
266  {
267  collection_flags.bit_set(n);
268  }
269 
274  inline void please_keep(uint32_t n) const
275  {
276  collection_flags.bit_unset(n);
277  }
278 
288  void epoch_check()
289  {
290  if (epoch_heuristic_counter != 0) {
291  --epoch_heuristic_counter;
292  return;
293  }
294  // count the number of elements from the latest epoch which
295  // have not been erased.
296  uint32_t epoch_unused_count = 0;
297  for (uint32_t i = 0; i < size; ++i)
298  epoch_unused_count += epoch_flags[i] &&
299  !collection_flags.bit_is_set(i);
300  // If there are more non-deleted entries in the current epoch than the
301  // epoch size, then allow_erase on all elements in the old epoch (marked
302  // false) and move all elements in the current epoch to the old epoch
303  // but do not call allow_erase on their indices.
304  if (epoch_unused_count >= epoch_size) {
305  for (uint32_t i = 0; i < size; ++i)
306  if (epoch_flags[i])
307  epoch_flags[i] = false;
308  else
309  allow_erase(i);
310  epoch_heuristic_counter = epoch_size;
311  } else
312  // reset the epoch_heuristic_counter to next do a scan when worst
313  // case behavior (no intermittent erases) would exceed epoch size,
314  // with a reasonable minimum scan size.
315  // Ordinarily, we would have to sanity check std::min(epoch_size,
316  // epoch_unused_count), but we already know that `epoch_unused_count
317  // < epoch_size` in this branch
318  epoch_heuristic_counter = std::max(1u, std::max(epoch_size / 16,
319  epoch_size - epoch_unused_count));
320  }
321 
322 public:
326  cache() : table(), size(), collection_flags(0), epoch_flags(),
327  epoch_heuristic_counter(), epoch_size(), depth_limit(0), hash_function()
328  {
329  }
330 
339  uint32_t setup(uint32_t new_size)
340  {
341  // depth_limit must be at least one otherwise errors can occur.
342  depth_limit = static_cast<uint8_t>(std::log2(static_cast<float>(std::max((uint32_t)2, new_size))));
343  size = std::max<uint32_t>(2, new_size);
344  table.resize(size);
345  collection_flags.setup(size);
346  epoch_flags.resize(size);
347  // Set to 45% as described above
348  epoch_size = std::max((uint32_t)1, (45 * size) / 100);
349  // Initially set to wait for a whole epoch
350  epoch_heuristic_counter = epoch_size;
351  return size;
352  }
353 
366  uint32_t setup_bytes(size_t bytes)
367  {
368  return setup(bytes/sizeof(Element));
369  }
370 
392  inline void insert(Element e)
393  {
394  epoch_check();
395  uint32_t last_loc = invalid();
396  bool last_epoch = true;
397  std::array<uint32_t, 8> locs = compute_hashes(e);
398  // Make sure we have not already inserted this element
399  // If we have, make sure that it does not get deleted
400  for (const uint32_t loc : locs)
401  if (table[loc] == e) {
402  please_keep(loc);
403  epoch_flags[loc] = last_epoch;
404  return;
405  }
406  for (uint8_t depth = 0; depth < depth_limit; ++depth) {
407  // First try to insert to an empty slot, if one exists
408  for (const uint32_t loc : locs) {
409  if (!collection_flags.bit_is_set(loc))
410  continue;
411  table[loc] = std::move(e);
412  please_keep(loc);
413  epoch_flags[loc] = last_epoch;
414  return;
415  }
430  last_loc = locs[(1 + (std::find(locs.begin(), locs.end(), last_loc) - locs.begin())) & 7];
431  std::swap(table[last_loc], e);
432  // Can't std::swap a std::vector<bool>::reference and a bool&.
433  bool epoch = last_epoch;
434  last_epoch = epoch_flags[last_loc];
435  epoch_flags[last_loc] = epoch;
436 
437  // Recompute the locs -- unfortunately happens one too many times!
438  locs = compute_hashes(e);
439  }
440  }
441 
469  inline bool contains(const Element& e, const bool erase) const
470  {
471  std::array<uint32_t, 8> locs = compute_hashes(e);
472  for (const uint32_t loc : locs)
473  if (table[loc] == e) {
474  if (erase)
475  allow_erase(loc);
476  return true;
477  }
478  return false;
479  }
480 };
481 } // namespace CuckooCache
482 
483 #endif // BITCOIN_CUCKOOCACHE_H
bool bit_is_set(uint32_t s) const
bit_is_set queries the table for discardability at s.
Definition: cuckoocache.h:111
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:274
std::unique_ptr< std::atomic< uint8_t >[]> mem
Definition: cuckoocache.h:43
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:60
cache implements a cache with properties similar to a cuckoo-set.
Definition: cuckoocache.h:158
void bit_set(uint32_t s)
bit_set sets an entry as discardable.
Definition: cuckoocache.h:90
bool contains(const Element &e, 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:469
uint32_t epoch_size
epoch_size is set to be the number of elements supposed to be in a epoch.
Definition: cuckoocache.h:192
std::vector< bool > epoch_flags
epoch_flags tracks how recently an element was inserted into the cache.
Definition: cuckoocache.h:175
const Hash hash_function
hash_function is a const instance of the hash function.
Definition: cuckoocache.h:203
bit_packed_atomic_flags implements a container for garbage collection flags that is only thread unsaf...
Definition: cuckoocache.h:41
cache()
You must always construct a cache with some elements via a subsequent call to setup or setup_bytes...
Definition: cuckoocache.h:326
uint32_t size
size stores the total available slots in the hash table
Definition: cuckoocache.h:165
uint8_t depth_limit
depth_limit determines how many elements insert should try to replace.
Definition: cuckoocache.h:197
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:182
uint256 Hash(const T1 pbegin, const T1 pend)
Compute the 256-bit hash of an object.
Definition: hash.h:71
void insert(Element e)
insert loops at most depth_limit times trying to insert a hash at various locations in the table via ...
Definition: cuckoocache.h:392
std::array< uint32_t, 8 > compute_hashes(const Element &e) const
compute_hashes is convenience for not having to write out this expression everywhere we use the hash ...
Definition: cuckoocache.h:242
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:366
std::vector< Element > table
table stores all the elements
Definition: cuckoocache.h:162
High-performance cache primitives.
Definition: cuckoocache.h:27
void epoch_check()
epoch_check handles the changing of epochs for elements stored in the cache.
Definition: cuckoocache.h:288
void allow_erase(uint32_t n) const
allow_erase marks the element at index n as discardable.
Definition: cuckoocache.h:265
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:169
uint32_t setup(uint32_t new_size)
setup initializes the container to store no more than new_size elements.
Definition: cuckoocache.h:339
void bit_unset(uint32_t s)
bit_unset marks an entry as something that should not be overwritten.
Definition: cuckoocache.h:101
constexpr uint32_t invalid() const
invalid returns a special index that can never be inserted to
Definition: cuckoocache.h:256
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:78
bit_packed_atomic_flags()=delete
No default constructor, as there must be some size.