epochguard.h raw

   1  // Copyright (c) 2009-2010 Satoshi Nakamoto
   2  // Copyright (c) 2009-2022 The Limenka developers
   3  // Distributed under the MIT software license, see the accompanying
   4  // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   5  
   6  #ifndef LIMENKA_UTIL_EPOCHGUARD_H
   7  #define LIMENKA_UTIL_EPOCHGUARD_H
   8  
   9  #include <threadsafety.h>
  10  #include <util/macros.h>
  11  
  12  #include <cassert>
  13  
  14  /** Epoch: RAII-style guard for using epoch-based graph traversal algorithms.
  15   *     When walking ancestors or descendants, we generally want to avoid
  16   * visiting the same transactions twice. Some traversal algorithms use
  17   * std::set (or setEntries) to deduplicate the transaction we visit.
  18   * However, use of std::set is algorithmically undesirable because it both
  19   * adds an asymptotic factor of O(log n) to traversals cost and triggers O(n)
  20   * more dynamic memory allocations.
  21   *     In many algorithms we can replace std::set with an internal mempool
  22   * counter to track the time (or, "epoch") that we began a traversal, and
  23   * check + update a per-transaction epoch for each transaction we look at to
  24   * determine if that transaction has not yet been visited during the current
  25   * traversal's epoch.
  26   *     Algorithms using std::set can be replaced on a one by one basis.
  27   * Both techniques are not fundamentally incompatible across the codebase.
  28   * Generally speaking, however, the remaining use of std::set for mempool
  29   * traversal should be viewed as a TODO for replacement with an epoch based
  30   * traversal, rather than a preference for std::set over epochs in that
  31   * algorithm.
  32   */
  33  
  34  class LOCKABLE Epoch
  35  {
  36  private:
  37      uint64_t m_raw_epoch = 0;
  38      bool m_guarded = false;
  39  
  40  public:
  41      Epoch() = default;
  42      Epoch(const Epoch&) = delete;
  43      Epoch& operator=(const Epoch&) = delete;
  44      Epoch(Epoch&&) = delete;
  45      Epoch& operator=(Epoch&&) = delete;
  46      ~Epoch() = default;
  47  
  48      bool guarded() const { return m_guarded; }
  49  
  50      class Marker
  51      {
  52      private:
  53          uint64_t m_marker = 0;
  54  
  55          // only allow modification via Epoch member functions
  56          friend class Epoch;
  57          Marker& operator=(const Marker&) = delete;
  58  
  59      public:
  60          Marker() = default;
  61          Marker(const Marker&) = default;
  62          Marker(Marker&&) = delete;
  63          Marker& operator=(Marker&&) = delete;
  64          ~Marker() = default;
  65      };
  66  
  67      class SCOPED_LOCKABLE Guard
  68      {
  69      private:
  70          Epoch& m_epoch;
  71  
  72      public:
  73          explicit Guard(Epoch& epoch) EXCLUSIVE_LOCK_FUNCTION(epoch) : m_epoch(epoch)
  74          {
  75              assert(!m_epoch.m_guarded);
  76              ++m_epoch.m_raw_epoch;
  77              m_epoch.m_guarded = true;
  78          }
  79          ~Guard() UNLOCK_FUNCTION()
  80          {
  81              assert(m_epoch.m_guarded);
  82              ++m_epoch.m_raw_epoch; // ensure clear separation between epochs
  83              m_epoch.m_guarded = false;
  84          }
  85      };
  86  
  87      bool visited(Marker& marker) const EXCLUSIVE_LOCKS_REQUIRED(*this)
  88      {
  89          assert(m_guarded);
  90          if (marker.m_marker < m_raw_epoch) {
  91              // marker is from a previous epoch, so this is its first visit
  92              marker.m_marker = m_raw_epoch;
  93              return false;
  94          } else {
  95              return true;
  96          }
  97      }
  98  };
  99  
 100  #define WITH_FRESH_EPOCH(epoch) const Epoch::Guard UNIQUE_NAME(epoch_guard_)(epoch)
 101  
 102  #endif // LIMENKA_UTIL_EPOCHGUARD_H
 103