Branch data     Line data    Source code

#       1                 :            : // Copyright (c) 2009-2010 Satoshi Nakamoto
#       2                 :            : // Copyright (c) 2009-2021 The Bitcoin Core 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 BITCOIN_UTIL_EPOCHGUARD_H
#       7                 :            : #define BITCOIN_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                 :       6734 :     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                 :          0 :     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                 :      90980 :         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                 :        294 :         {
#      75                 :        294 :             assert(!m_epoch.m_guarded);
#      76                 :          0 :             ++m_epoch.m_raw_epoch;
#      77                 :        294 :             m_epoch.m_guarded = true;
#      78                 :        294 :         }
#      79                 :            :         ~Guard() UNLOCK_FUNCTION()
#      80                 :        294 :         {
#      81                 :        294 :             assert(m_epoch.m_guarded);
#      82                 :          0 :             ++m_epoch.m_raw_epoch; // ensure clear separation between epochs
#      83                 :        294 :             m_epoch.m_guarded = false;
#      84                 :        294 :         }
#      85                 :            :     };
#      86                 :            : 
#      87                 :            :     bool visited(Marker& marker) const EXCLUSIVE_LOCKS_REQUIRED(*this)
#      88                 :       4733 :     {
#      89                 :       4733 :         assert(m_guarded);
#      90         [ +  + ]:       4733 :         if (marker.m_marker < m_raw_epoch) {
#      91                 :            :             // marker is from a previous epoch, so this is its first visit
#      92                 :       4727 :             marker.m_marker = m_raw_epoch;
#      93                 :       4727 :             return false;
#      94                 :       4727 :         } else {
#      95                 :          6 :             return true;
#      96                 :          6 :         }
#      97                 :       4733 :     }
#      98                 :            : };
#      99                 :            : 
#     100                 :        294 : #define WITH_FRESH_EPOCH(epoch) const Epoch::Guard UNIQUE_NAME(epoch_guard_)(epoch)
#     101                 :            : 
#     102                 :            : #endif // BITCOIN_UTIL_EPOCHGUARD_H