Bitcoin Core  22.99.0
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 <util/fastrange.h>
9 
10 #include <algorithm> // std::find
11 #include <array>
12 #include <atomic>
13 #include <cmath>
14 #include <cstring>
15 #include <memory>
16 #include <utility>
17 #include <vector>
18 
19 
29 namespace CuckooCache
30 {
44 {
45  std::unique_ptr<std::atomic<uint8_t>[]> mem;
46 
47 public:
49  bit_packed_atomic_flags() = delete;
50 
62  explicit bit_packed_atomic_flags(uint32_t size)
63  {
64  // pad out the size if needed
65  size = (size + 7) / 8;
66  mem.reset(new std::atomic<uint8_t>[size]);
67  for (uint32_t i = 0; i < size; ++i)
68  mem[i].store(0xFF);
69  };
70 
80  inline void setup(uint32_t b)
81  {
83  std::swap(mem, d.mem);
84  }
85 
92  inline void bit_set(uint32_t s)
93  {
94  mem[s >> 3].fetch_or(uint8_t(1 << (s & 7)), std::memory_order_relaxed);
95  }
96 
103  inline void bit_unset(uint32_t s)
104  {
105  mem[s >> 3].fetch_and(uint8_t(~(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 
199  uint8_t depth_limit;
200 
206 
239  inline std::array<uint32_t, 8> compute_hashes(const Element& e) const
240  {
241  return {{FastRange32(hash_function.template operator()<0>(e), size),
242  FastRange32(hash_function.template operator()<1>(e), size),
243  FastRange32(hash_function.template operator()<2>(e), size),
244  FastRange32(hash_function.template operator()<3>(e), size),
245  FastRange32(hash_function.template operator()<4>(e), size),
246  FastRange32(hash_function.template operator()<5>(e), size),
247  FastRange32(hash_function.template operator()<6>(e), size),
248  FastRange32(hash_function.template operator()<7>(e), size)}};
249  }
250 
253  constexpr uint32_t invalid() const
254  {
255  return ~(uint32_t)0;
256  }
257 
262  inline void allow_erase(uint32_t n) const
263  {
265  }
266 
271  inline void please_keep(uint32_t n) const
272  {
274  }
275 
285  void epoch_check()
286  {
287  if (epoch_heuristic_counter != 0) {
289  return;
290  }
291  // count the number of elements from the latest epoch which
292  // have not been erased.
293  uint32_t epoch_unused_count = 0;
294  for (uint32_t i = 0; i < size; ++i)
295  epoch_unused_count += epoch_flags[i] &&
297  // If there are more non-deleted entries in the current epoch than the
298  // epoch size, then allow_erase on all elements in the old epoch (marked
299  // false) and move all elements in the current epoch to the old epoch
300  // but do not call allow_erase on their indices.
301  if (epoch_unused_count >= epoch_size) {
302  for (uint32_t i = 0; i < size; ++i)
303  if (epoch_flags[i])
304  epoch_flags[i] = false;
305  else
306  allow_erase(i);
308  } else
309  // reset the epoch_heuristic_counter to next do a scan when worst
310  // case behavior (no intermittent erases) would exceed epoch size,
311  // with a reasonable minimum scan size.
312  // Ordinarily, we would have to sanity check std::min(epoch_size,
313  // epoch_unused_count), but we already know that `epoch_unused_count
314  // < epoch_size` in this branch
315  epoch_heuristic_counter = std::max(1u, std::max(epoch_size / 16,
316  epoch_size - epoch_unused_count));
317  }
318 
319 public:
325  {
326  }
327 
336  uint32_t setup(uint32_t new_size)
337  {
338  // depth_limit must be at least one otherwise errors can occur.
339  depth_limit = static_cast<uint8_t>(std::log2(static_cast<float>(std::max((uint32_t)2, new_size))));
340  size = std::max<uint32_t>(2, new_size);
341  table.resize(size);
343  epoch_flags.resize(size);
344  // Set to 45% as described above
345  epoch_size = std::max((uint32_t)1, (45 * size) / 100);
346  // Initially set to wait for a whole epoch
348  return size;
349  }
350 
363  uint32_t setup_bytes(size_t bytes)
364  {
365  return setup(bytes/sizeof(Element));
366  }
367 
389  inline void insert(Element e)
390  {
391  epoch_check();
392  uint32_t last_loc = invalid();
393  bool last_epoch = true;
394  std::array<uint32_t, 8> locs = compute_hashes(e);
395  // Make sure we have not already inserted this element
396  // If we have, make sure that it does not get deleted
397  for (const uint32_t loc : locs)
398  if (table[loc] == e) {
399  please_keep(loc);
400  epoch_flags[loc] = last_epoch;
401  return;
402  }
403  for (uint8_t depth = 0; depth < depth_limit; ++depth) {
404  // First try to insert to an empty slot, if one exists
405  for (const uint32_t loc : locs) {
406  if (!collection_flags.bit_is_set(loc))
407  continue;
408  table[loc] = std::move(e);
409  please_keep(loc);
410  epoch_flags[loc] = last_epoch;
411  return;
412  }
427  last_loc = locs[(1 + (std::find(locs.begin(), locs.end(), last_loc) - locs.begin())) & 7];
428  std::swap(table[last_loc], e);
429  // Can't std::swap a std::vector<bool>::reference and a bool&.
430  bool epoch = last_epoch;
431  last_epoch = epoch_flags[last_loc];
432  epoch_flags[last_loc] = epoch;
433 
434  // Recompute the locs -- unfortunately happens one too many times!
435  locs = compute_hashes(e);
436  }
437  }
438 
466  inline bool contains(const Element& e, const bool erase) const
467  {
468  std::array<uint32_t, 8> locs = compute_hashes(e);
469  for (const uint32_t loc : locs)
470  if (table[loc] == e) {
471  if (erase)
472  allow_erase(loc);
473  return true;
474  }
475  return false;
476  }
477 };
478 } // namespace CuckooCache
479 
480 #endif // BITCOIN_CUCKOOCACHE_H
CuckooCache::cache::please_keep
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:271
CuckooCache::cache
cache implements a cache with properties similar to a cuckoo-set.
Definition: cuckoocache.h:160
CuckooCache::bit_packed_atomic_flags::bit_set
void bit_set(uint32_t s)
bit_set sets an entry as discardable.
Definition: cuckoocache.h:92
CuckooCache::cache::epoch_size
uint32_t epoch_size
epoch_size is set to be the number of elements supposed to be in a epoch.
Definition: cuckoocache.h:194
CuckooCache::bit_packed_atomic_flags::mem
std::unique_ptr< std::atomic< uint8_t >[]> mem
Definition: cuckoocache.h:45
CuckooCache
High-performance cache primitives.
Definition: cuckoocache.h:29
CuckooCache::cache::contains
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:466
CuckooCache::bit_packed_atomic_flags::bit_packed_atomic_flags
bit_packed_atomic_flags()=delete
No default constructor, as there must be some size.
Hash
uint256 Hash(const T &in1)
Compute the 256-bit hash of an object.
Definition: hash.h:75
CuckooCache::cache::hash_function
const Hash hash_function
hash_function is a const instance of the hash function.
Definition: cuckoocache.h:205
CuckooCache::bit_packed_atomic_flags::bit_packed_atomic_flags
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:62
CuckooCache::cache::cache
cache()
You must always construct a cache with some elements via a subsequent call to setup or setup_bytes,...
Definition: cuckoocache.h:323
CuckooCache::bit_packed_atomic_flags::setup
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
CuckooCache::cache::size
uint32_t size
size stores the total available slots in the hash table
Definition: cuckoocache.h:167
CuckooCache::cache::depth_limit
uint8_t depth_limit
depth_limit determines how many elements insert should try to replace.
Definition: cuckoocache.h:199
CuckooCache::cache::epoch_flags
std::vector< bool > epoch_flags
epoch_flags tracks how recently an element was inserted into the cache.
Definition: cuckoocache.h:177
CuckooCache::cache::insert
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:389
CuckooCache::bit_packed_atomic_flags::bit_is_set
bool bit_is_set(uint32_t s) const
bit_is_set queries the table for discardability at s.
Definition: cuckoocache.h:113
CuckooCache::bit_packed_atomic_flags
bit_packed_atomic_flags implements a container for garbage collection flags that is only thread unsaf...
Definition: cuckoocache.h:43
CuckooCache::cache::allow_erase
void allow_erase(uint32_t n) const
allow_erase marks the element at index n as discardable.
Definition: cuckoocache.h:262
CuckooCache::cache::epoch_heuristic_counter
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
CuckooCache::cache::table
std::vector< Element > table
table stores all the elements
Definition: cuckoocache.h:164
fastrange.h
CuckooCache::cache::setup
uint32_t setup(uint32_t new_size)
setup initializes the container to store no more than new_size elements.
Definition: cuckoocache.h:336
FastRange32
static uint32_t FastRange32(uint32_t x, uint32_t n)
Fast range reduction with 32-bit input and 32-bit range.
Definition: fastrange.h:19
CuckooCache::cache::collection_flags
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
CuckooCache::cache::epoch_check
void epoch_check()
epoch_check handles the changing of epochs for elements stored in the cache.
Definition: cuckoocache.h:285
CuckooCache::cache::setup_bytes
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:363
CuckooCache::cache::compute_hashes
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:239
CuckooCache::cache::invalid
constexpr uint32_t invalid() const
invalid returns a special index that can never be inserted to
Definition: cuckoocache.h:253
CuckooCache::bit_packed_atomic_flags::bit_unset
void bit_unset(uint32_t s)
bit_unset marks an entry as something that should not be overwritten.
Definition: cuckoocache.h:103