Merge #18017: txmempool: split epoch logic into class

fd6580e405699ccb051fd2a34525e48d3253673d [refactor] txmempool: split epoch logic into class (Anthony Towns)

Pull request description:

  Splits the epoch logic introduced in #17925 into a separate class.

  Uses clang's thread safety annotations and encapsulates the data more strongly to reduce chances of bugs from API misuse.

ACKs for top commit:
  jonatack:
    ACK fd6580e405699ccb051fd2a34525e48d3253673d using clang thread safety annotations looks like a very good idea, and the encapsulation this change adds should improve robustness (and possible unit test-ability) of the code. Verified that changing some of the locking duly provoked build-time warnings with Clang 9 on Debian and that small changes in the new `Epoch` class were covered by failing functional test assertions in `mempool_updatefromblock.py`, `mempool_resurrect.py`, and `mempool_reorg.py`
  hebasto:
    re-ACK fd6580e405699ccb051fd2a34525e48d3253673d, since my [previous](https://github.com/bitcoin/bitcoin/pull/18017#pullrequestreview-569619362) review:

Tree-SHA512: 7004623faa02b56639aa05ab7a078320a6d8d54ec62d8022876221e33f350f47df51ddff056c0de5be798f8eb39b5c03c2d3f035698555d70abc218e950f2f8c

1 files changed, 91 insertions, 0 deletions

diff --git a/src/util/epochguard.h b/src/util/epochguard.h
new file mode 100644
index 0000000000..1570ec4eb4
--- /dev/null
+++ b/src/util/epochguard.h
@@ -0,0 +1,91 @@
+// Copyright (c) 2009-2010 Satoshi Nakamoto
+// Copyright (c) 2009-2020 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_UTIL_EPOCHGUARD_H
+#define BITCOIN_UTIL_EPOCHGUARD_H
+
+#include <threadsafety.h>
+
+#include <cassert>
+
+/** Epoch: RAII-style guard for using epoch-based graph traversal algorithms.
+ *     When walking ancestors or descendants, we generally want to avoid
+ * visiting the same transactions twice. Some traversal algorithms use
+ * std::set (or setEntries) to deduplicate the transaction we visit.
+ * However, use of std::set is algorithmically undesirable because it both
+ * adds an asymptotic factor of O(log n) to traversals cost and triggers O(n)
+ * more dynamic memory allocations.
+ *     In many algorithms we can replace std::set with an internal mempool
+ * counter to track the time (or, "epoch") that we began a traversal, and
+ * check + update a per-transaction epoch for each transaction we look at to
+ * determine if that transaction has not yet been visited during the current
+ * traversal's epoch.
+ *     Algorithms using std::set can be replaced on a one by one basis.
+ * Both techniques are not fundamentally incompatible across the codebase.
+ * Generally speaking, however, the remaining use of std::set for mempool
+ * traversal should be viewed as a TODO for replacement with an epoch based
+ * traversal, rather than a preference for std::set over epochs in that
+ * algorithm.
+ */
+
+class LOCKABLE Epoch
+{
+private:
+    uint64_t m_raw_epoch = 0;
+    bool m_guarded = false;
+
+public:
+    Epoch() = default;
+    Epoch(const Epoch&) = delete;
+    Epoch& operator=(const Epoch&) = delete;
+
+    bool guarded() const { return m_guarded; }
+
+    class Marker
+    {
+    private:
+        uint64_t m_marker = 0;
+
+        // only allow modification via Epoch member functions
+        friend class Epoch;
+        Marker& operator=(const Marker&) = delete;
+    };
+
+    class SCOPED_LOCKABLE Guard
+    {
+    private:
+        Epoch& m_epoch;
+
+    public:
+        explicit Guard(Epoch& epoch) EXCLUSIVE_LOCK_FUNCTION(epoch) : m_epoch(epoch)
+        {
+            assert(!m_epoch.m_guarded);
+            ++m_epoch.m_raw_epoch;
+            m_epoch.m_guarded = true;
+        }
+        ~Guard() UNLOCK_FUNCTION()
+        {
+            assert(m_epoch.m_guarded);
+            ++m_epoch.m_raw_epoch; // ensure clear separation between epochs
+            m_epoch.m_guarded = false;
+        }
+    };
+
+    bool visited(Marker& marker) const EXCLUSIVE_LOCKS_REQUIRED(*this)
+    {
+        assert(m_guarded);
+        if (marker.m_marker < m_raw_epoch) {
+            // marker is from a previous epoch, so this is its first visit
+            marker.m_marker = m_raw_epoch;
+            return false;
+        } else {
+            return true;
+        }
+    }
+};
+
+#define WITH_FRESH_EPOCH(epoch) const Epoch::Guard PASTE2(epoch_guard_, __COUNTER__)(epoch)
+
+#endif // BITCOIN_UTIL_EPOCHGUARD_H