Dash Core Source Documentation (0.16.0.1)

Find detailed information regarding the Dash Core source code.

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 <array>
9 #include <algorithm>
10 #include <atomic>
11 #include <cstring>
12 #include <cmath>
13 #include <memory>
14 #include <vector>
15 
16 
27 namespace CuckooCache
28 {
43 {
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  {
63  // pad out the size if needed
64  size = (size + 7) / 8;
65  mem.reset(new std::atomic<uint8_t>[size]);
66  for (uint32_t i = 0; i < size; ++i)
67  mem[i].store(0xFF);
68  };
69 
79  inline void setup(uint32_t b)
80  {
82  std::swap(mem, d.mem);
83  }
84 
92  inline void bit_set(uint32_t s)
93  {
94  mem[s >> 3].fetch_or(1 << (s & 7), std::memory_order_relaxed);
95  }
96 
103  inline void bit_unset(uint32_t s)
104  {
105  mem[s >> 3].fetch_and(~(1 << (s & 7)), std::memory_order_relaxed);
106  }
107 
113  inline bool bit_is_set(uint32_t s) const
114  {
115  return (1 << (s & 7)) & mem[s >> 3].load(std::memory_order_relaxed);
116  }
117 };
118 
159 template <typename Element, typename Hash>
160 class cache
161 {
162 private:
164  std::vector<Element> table;
165 
167  uint32_t size;
168 
172 
177  mutable std::vector<bool> epoch_flags;
178 
185 
194  uint32_t epoch_size;
195 
198  uint8_t depth_limit;
199 
205 
243  inline std::array<uint32_t, 8> compute_hashes(const Element& e) const
244  {
245  return {{(uint32_t)((hash_function.template operator()<0>(e) * (uint64_t)size) >> 32),
246  (uint32_t)((hash_function.template operator()<1>(e) * (uint64_t)size) >> 32),
247  (uint32_t)((hash_function.template operator()<2>(e) * (uint64_t)size) >> 32),
248  (uint32_t)((hash_function.template operator()<3>(e) * (uint64_t)size) >> 32),
249  (uint32_t)((hash_function.template operator()<4>(e) * (uint64_t)size) >> 32),
250  (uint32_t)((hash_function.template operator()<5>(e) * (uint64_t)size) >> 32),
251  (uint32_t)((hash_function.template operator()<6>(e) * (uint64_t)size) >> 32),
252  (uint32_t)((hash_function.template operator()<7>(e) * (uint64_t)size) >> 32)}};
253  }
254 
255  /* end
256  * @returns a constexpr index that can never be inserted to */
257  constexpr uint32_t invalid() const
258  {
259  return ~(uint32_t)0;
260  }
261 
266  inline void allow_erase(uint32_t n) const
267  {
269  }
270 
275  inline void please_keep(uint32_t n) const
276  {
278  }
279 
289  void epoch_check()
290  {
291  if (epoch_heuristic_counter != 0) {
293  return;
294  }
295  // count the number of elements from the latest epoch which
296  // have not been erased.
297  uint32_t epoch_unused_count = 0;
298  for (uint32_t i = 0; i < size; ++i)
299  epoch_unused_count += epoch_flags[i] &&
301  // If there are more non-deleted entries in the current epoch than the
302  // epoch size, then allow_erase on all elements in the old epoch (marked
303  // false) and move all elements in the current epoch to the old epoch
304  // but do not call allow_erase on their indices.
305  if (epoch_unused_count >= epoch_size) {
306  for (uint32_t i = 0; i < size; ++i)
307  if (epoch_flags[i])
308  epoch_flags[i] = false;
309  else
310  allow_erase(i);
312  } else
313  // reset the epoch_heuristic_counter to next do a scan when worst
314  // case behavior (no intermittent erases) would exceed epoch size,
315  // with a reasonable minimum scan size.
316  // Ordinarily, we would have to sanity check std::min(epoch_size,
317  // epoch_unused_count), but we already know that `epoch_unused_count
318  // < epoch_size` in this branch
319  epoch_heuristic_counter = std::max(1u, std::max(epoch_size / 16,
320  epoch_size - epoch_unused_count));
321  }
322 
323 public:
329  {
330  }
331 
340  uint32_t setup(uint32_t new_size)
341  {
342  // depth_limit must be at least one otherwise errors can occur.
343  depth_limit = static_cast<uint8_t>(std::log2(static_cast<float>(std::max((uint32_t)2, new_size))));
344  size = std::max<uint32_t>(2, new_size);
345  table.resize(size);
347  epoch_flags.resize(size);
348  // Set to 45% as described above
349  epoch_size = std::max((uint32_t)1, (45 * size) / 100);
350  // Initially set to wait for a whole epoch
352  return size;
353  }
354 
367  uint32_t setup_bytes(size_t bytes)
368  {
369  return setup(bytes/sizeof(Element));
370  }
371 
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 (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 (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 
442  /* contains iterates through the hash locations for a given element
443  * and checks to see if it is present.
444  *
445  * contains does not check garbage collected state (in other words,
446  * garbage is only collected when the space is needed), so:
447  *
448  * insert(x);
449  * if (contains(x, true))
450  * return contains(x, false);
451  * else
452  * return true;
453  *
454  * executed on a single thread will always return true!
455  *
456  * This is a great property for re-org performance for example.
457  *
458  * contains returns a bool set true if the element was found.
459  *
460  * @param e the element to check
461  * @param erase
462  *
463  * @post if erase is true and the element is found, then the garbage collect
464  * flag is set
465  * @returns true if the element is found, false otherwise
466  */
467  inline bool contains(const Element& e, const bool erase) const
468  {
469  std::array<uint32_t, 8> locs = compute_hashes(e);
470  for (uint32_t loc : locs)
471  if (table[loc] == e) {
472  if (erase)
473  allow_erase(loc);
474  return true;
475  }
476  return false;
477  }
478 };
479 } // namespace CuckooCache
480 
481 #endif // BITCOIN_CUCKOOCACHE_H
constexpr auto log2(T x) -> std::enable_if_t<!std::is_same< decltype(clz_(x)), not_supported_t >::value, T >
Definition: util.hpp:100
bool bit_is_set(uint32_t s) const
bit_is_set queries the table for discardability at s
Definition: cuckoocache.h:113
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:275
std::unique_ptr< std::atomic< uint8_t >[]> mem
Definition: cuckoocache.h:44
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:160
void bit_set(uint32_t s)
bit_set sets an entry as discardable.
Definition: cuckoocache.h:92
bool contains(const Element &e, const bool erase) const
Definition: cuckoocache.h:467
uint32_t epoch_size
epoch_size is set to be the number of elements supposed to be in a epoch.
Definition: cuckoocache.h:194
std::vector< bool > epoch_flags
epoch_flags tracks how recently an element was inserted into the cache.
Definition: cuckoocache.h:177
const Hash hash_function
hash_function is a const instance of the hash function.
Definition: cuckoocache.h:204
bit_packed_atomic_flags implements a container for garbage collection flags that is only thread unsaf...
Definition: cuckoocache.h:42
cache()
You must always construct a cache with some elements via a subsequent call to setup or setup_bytes...
Definition: cuckoocache.h:327
uint32_t size
size stores the total available slots in the hash table
Definition: cuckoocache.h:167
uint8_t depth_limit
depth_limit determines how many elements insert should try to replace.
Definition: cuckoocache.h:198
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:184
uint256 Hash(const T1 pbegin, const T1 pend)
Compute the 256-bit hash of an object.
Definition: hash.h:84
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:243
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:367
std::vector< Element > table
table stores all the elements
Definition: cuckoocache.h:164
namespace CuckooCache provides 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:289
void allow_erase(uint32_t n) const
allow_erase marks the element at index n as discardable.
Definition: cuckoocache.h:266
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:171
uint32_t setup(uint32_t new_size)
setup initializes the container to store no more than new_size elements.
Definition: cuckoocache.h:340
void bit_unset(uint32_t s)
bit_unset marks an entry as something that should not be overwritten
Definition: cuckoocache.h:103
constexpr uint32_t invalid() const
Definition: cuckoocache.h:257
void setup(uint32_t b)
setup marks all entries and ensures that bit_packed_atomic_flags can store at least size entries ...
Definition: cuckoocache.h:79
bit_packed_atomic_flags()=delete
No default constructor as there must be some size.
Released under the MIT license