txmempool: split epoch logic into class #18017

pull ajtowns wants to merge 1 commits into bitcoin:master from ajtowns:202001-epoch changing 4 files +107 −63
  1. ajtowns commented at 4:46 am on January 29, 2020: member

    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.

  2. ajtowns added the label Refactoring on Jan 29, 2020
  3. ajtowns added the label Mempool on Jan 29, 2020
  4. fanquake requested review from JeremyRubin on Jan 29, 2020
  5. JeremyRubin commented at 5:04 am on January 29, 2020: contributor
    Concept ACK. Will need to play around with it a little bit to test that clang actually prevents compiling incorrect uses.
  6. DrahtBot commented at 9:20 am on January 29, 2020: member

    The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

    Conflicts

    No conflicts as of last run.

  7. ajtowns force-pushed on Feb 3, 2020
  8. ajtowns marked this as ready for review on Feb 3, 2020
  9. laanwj commented at 4:21 pm on February 10, 2020: member
    Concept ACK, nice
  10. DrahtBot added the label Needs rebase on Mar 4, 2020
  11. ajtowns force-pushed on Mar 7, 2020
  12. DrahtBot removed the label Needs rebase on Mar 7, 2020
  13. hebasto commented at 8:12 am on May 24, 2020: member
    Concept ACK.
  14. in src/txmempool.h:80 in 7485e0f9db outdated 
    75+private:
76+    uint64_t m_raw_epoch;
77+    bool m_guarded;
78+
79+public:
80+    Epoch() : m_raw_epoch{0}, m_guarded{false} { }
    hebasto commented at 8:37 am on May 24, 2020:
    Mind switching from the member initialization list to the default member initializers?
  15. in src/txmempool.h:92 in 7485e0f9db outdated 
    87+    class Marker {
88+    private:
89+        uint64_t m_marker;
90+
91+    public:
92+        Marker() : m_marker{0} { }
    hebasto commented at 8:39 am on May 24, 2020:
    Mind switching from the member initialization list to the default member initializer?
  16. in src/txmempool.h:83 in 7485e0f9db outdated 
    78+
79+public:
80+    Epoch() : m_raw_epoch{0}, m_guarded{false} { }
81+
82+    Epoch(const Epoch&) = delete; // no copy constructor
83+    Epoch& operator=(const Epoch&) = delete; // not assignable
    hebasto commented at 10:23 am on May 24, 2020:
    micro-nit: These comments are so obvious that seem redundant :)
  17. in src/txmempool.h:73 in 7485e0f9db outdated 
    68+ * traversal should be viewed as a TODO for replacement with an epoch based
69+ * traversal, rather than a preference for std::set over epochs in that
70+ * algorithm.
71+ */
72+
73+class Epoch
    hebasto commented at 11:33 am on May 24, 2020:

    Tested on top of the #18635, and had loads of warnings:

     0./txmempool.h:102:38: warning: 'exclusive_lock_function' attribute requires arguments whose type is annotated with 'capability' attribute; type here is 'Epoch' [-Wthread-safety-attributes]
 1        explicit Guard(Epoch& epoch) EXCLUSIVE_LOCK_FUNCTION(epoch) LOCKS_EXCLUDED(epoch);
 2                                     ^
 3...
 4./txmempool.h:106:40: warning: 'exclusive_locks_required' attribute requires arguments whose type is annotated with 'capability' attribute; type here is 'const Epoch' [-Wthread-safety-attributes]
 5    bool visited(Marker& marker) const EXCLUSIVE_LOCKS_REQUIRED(*this) {
 6                                       ^
 7...
 8./txmempool.h:691:121: warning: 'locks_excluded' attribute requires arguments whose type is annotated with 'capability' attribute; type here is 'Epoch' [-Wthread-safety-attributes]
 9    void UpdateTransactionsFromBlock(const std::vector<uint256>& vHashesToUpdate) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main) LOCKS_EXCLUDED(m_epoch);
10                                                                                                                        ^
11...
12./txmempool.h:812:41: warning: 'exclusive_locks_required' attribute requires arguments whose type is annotated with 'capability' attribute; type here is 'Epoch' [-Wthread-safety-attributes]
13    bool visited(const txiter it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch) {
14                                        ^
15...
16./txmempool.h:816:45: warning: 'exclusive_locks_required' attribute requires arguments whose type is annotated with 'capability' attribute; type here is 'Epoch' [-Wthread-safety-attributes]
17    bool visited(Optional<txiter> it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch) {
18                                            ^

    To make the Clang Thread Safety Analysis work as expected I suggest:

    0class LOCKABLE Epoch

    and change the type of the Epoch::Guard::m_epoch from Epoch& to Epoch*.

    ajtowns commented at 11:51 am on May 26, 2020:
    I’m not seeing what benefit changing Epoch::Guard::m_epoch from reference to pointer would have – the analysis shouldn’t (and doesn’t) treat them any different, as far as I can see?
    hebasto commented at 2:59 pm on May 26, 2020:
    Indeed :) IDK why I saw warnings…
  18. in src/txmempool.h:102 in 7485e0f9db outdated 
     97+    class SCOPED_LOCKABLE Guard {
 98+    private:
 99+        Epoch& m_epoch;
100+
101+    public:
102+        explicit Guard(Epoch& epoch) EXCLUSIVE_LOCK_FUNCTION(epoch) LOCKS_EXCLUDED(epoch);
    hebasto commented at 11:37 am on May 24, 2020:

    From the Thread Safety Analysis docs:

    The caller must not hold the given capability on entry

    It seems LOCKS_EXCLUDED(epoch) is redundant, no?

  19. hebasto changes_requested
  20. hebasto commented at 11:41 am on May 24, 2020: member
    A brilliant idea to leverage the Clang Thread Safety Analysis!
  21. ajtowns force-pushed on May 26, 2020
  22. ajtowns commented at 12:07 pm on May 26, 2020: member
    Incorporated @hebasto’s suggested changes
  23. hebasto approved
  24. hebasto commented at 3:52 pm on May 26, 2020: member

    ACK 837d4e4f5aeb2f110143c59b7dd05eac6ae52b63, tested on Linux Mint 19.3: the Clang’s thread safety annotations indeed reduce chances of the Epoch class misuse (verified by different code manipulations).

    May I suggest two additional annotations:

     0--- a/src/txmempool.cpp
 1+++ b/src/txmempool.cpp
 2@@ -107,6 +107,7 @@ void CTxMemPool::UpdateForDescendants(txiter updateIt, cacheMap &cachedDescendan
 3 void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256> &vHashesToUpdate)
 4 {
 5     AssertLockHeld(cs);
 6+    AssertLockNotHeld(m_epoch);
 7     // For each entry in vHashesToUpdate, store the set of in-mempool, but not
 8     // in-vHashesToUpdate transactions, so that we don't have to recalculate
 9     // descendants when we come across a previously seen entry.
10diff --git a/src/txmempool.h b/src/txmempool.h
11index 655afc3b8..b72ad229c 100644
12--- a/src/txmempool.h
13+++ b/src/txmempool.h
14@@ -797,7 +797,7 @@ private:
15      */
16     void UpdateForDescendants(txiter updateIt,
17             cacheMap &cachedDescendants,
18-            const std::set<uint256> &setExclude) EXCLUSIVE_LOCKS_REQUIRED(cs);
19+            const std::set<uint256> &setExclude) EXCLUSIVE_LOCKS_REQUIRED(cs) LOCKS_EXCLUDED(m_epoch);
20     /** Update ancestors of hash to add/remove it as a descendant transaction. */
21     void UpdateAncestorsOf(bool add, txiter hash, setEntries &setAncestors) EXCLUSIVE_LOCKS_REQUIRED(cs);
22     /** Set ancestor state for an entry */

    ?

  25. ajtowns commented at 4:30 pm on May 26, 2020: member
    @hebasto - AssertLockNotHeld(m_epoch) won’t work – epochs aren’t sync.h locks. I think the annotation for UpdateForDescendents would be better made after #18191 is merged?
  26. hebasto commented at 4:36 pm on May 26, 2020: member

    @ajtowns

    @hebasto - AssertLockNotHeld(m_epoch) won’t work – epochs aren’t sync.h locks. I think the annotation for UpdateForDescendents would be better made after #18191 is merged?

    Agree.

  27. DrahtBot added the label Needs rebase on Sep 7, 2020
  28. ajtowns force-pushed on Sep 10, 2020
  29. ajtowns commented at 10:57 pm on September 10, 2020: member
    Rebased
  30. DrahtBot removed the label Needs rebase on Sep 10, 2020
  31. in src/txmempool.h:98 in c95663c935 outdated 
    93+public:
94+    Epoch() { }
95+    Epoch(const Epoch&) = delete;
96+    Epoch& operator=(const Epoch&) = delete;
97+
98+    bool guarded() const { return m_guarded; }
    JeremyRubin commented at 5:41 am on September 11, 2020:
    Is this used?
    JeremyRubin commented at 5:42 am on September 11, 2020:
    (I’m fine leaving it if it isn’t used, just curious).
    ajtowns commented at 1:52 am on September 15, 2020:
    There’s an assert(m_epoch.guarded()); in CTxMemPool::visited(Optional<txiter> it) to check the lock’s held in the case where it->visited isn’t called.
  32. in src/txmempool.h:120 in c95663c935 outdated 
    115+    bool visited(Marker& marker) const EXCLUSIVE_LOCKS_REQUIRED(*this) {
116+        assert(m_guarded);
117+        bool ret = marker.m_marker >= m_raw_epoch;
118+        if (!ret) marker.m_marker = m_raw_epoch;
119+        return ret;
120+    }
    JeremyRubin commented at 5:52 am on September 11, 2020:

    nit: how would you feel about:

    0uint64_t marker_old = marker.m_marker;
1marker.m_marker = std::max(marker.m_marker, m_raw_epoch);
2return marker.m_marker != marker_old;

    for whatever reason I find it easier to read/reason about when we always set it to max.

    ajtowns commented at 2:09 am on September 15, 2020:

    That reverses the logic (ret == false causes m_marker to change originally, but your code returns true if m_marker changed) ? Seems like that’s evidence it’s not that easy to read/reason about? :)

    It might be less confusing to write it out in full:

    0if (marker.m_marker < m_raw_epoch ) {
1    // this entry is from an earlier epoch, so it hasn't been visited
2    marker.m_marker = m_raw_epoch;
3    return false;
4} else {
5    return true;
6}

    I’d guess the compiler will make all these variants essentially the same anyway, so no objection to any variation from me.

    JeremyRubin commented at 2:37 am on September 15, 2020:

    Ah my bad, I’ve made a case against myself – for what it’s worth, I made the proposed version by translating your proposed version, which I have trouble parsing logically, and thought it was equivalent to that logic (and still can’t figure out the concrete reason it’s opposite).

    I’m fine with the completely written out version as it is the most obvious for sleepy brains like mine.

    ajtowns commented at 3:20 am on September 15, 2020:

    I think the translation goes:

    • r = a >= b; if (!r) a = b; return r; (current)
    • o = a; if (! (a >= b)) a = b; return o >= b; (store old value, replace r)
    • o = a; if (a < b) a = b; return !(o < b); (switch to less than)
    • o = a; a = max(a,b); return !(o != a); (o < b iff the if was taken, and a was changed)
    • o = a; a = max(a,b); return o == a; (simplify)

    Anyway, changed to KISS version.

  33. in src/txmempool.cpp:1116 in c95663c935 outdated 
    1112@@ -1113,22 +1113,17 @@ void CTxMemPool::SetIsLoaded(bool loaded)
1113 }
1114 
1115 
1116-CTxMemPool::EpochGuard CTxMemPool::GetFreshEpoch() const
1117+Epoch::Guard::Guard(Epoch& epoch) : m_epoch(epoch)
    JeremyRubin commented at 5:57 am on September 11, 2020:
    Maybe best to move this into it’s own header-only file/all headers to minimize conflict with #17786?
    ajtowns commented at 3:21 am on September 15, 2020:
    Moved into util/epochguard.h
  34. JeremyRubin approved
  35. JeremyRubin commented at 6:03 am on September 11, 2020: contributor
    Code Review ACK.
  36. ajtowns force-pushed on Sep 15, 2020
  37. ajtowns force-pushed on Sep 15, 2020
  38. ajtowns force-pushed on Sep 15, 2020
  39. in src/txmempool.h:831 in 55c1c7e5db outdated 
    864     }
865 
866-    bool visited(Optional<txiter> it) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
867-        assert(m_has_epoch_guard);
868+    bool visited(Optional<txiter> it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch) {
869+        assert(m_epoch.guarded());
    JeremyRubin commented at 4:04 pm on September 15, 2020:
    micronit: may be worth adding a comment here that the assert is redundant when it != nullopt, but is used for consistency when it == nullopt.
  40. JeremyRubin commented at 4:05 pm on September 15, 2020: contributor
    re CR-ACK
  41. ajtowns force-pushed on Sep 16, 2020
  42. ajtowns force-pushed on Sep 17, 2020
  43. jonatack commented at 8:37 am on September 18, 2020: member
    Concept ACK, the code looks like a nice refactoring.
  44. DrahtBot added the label Needs rebase on Dec 1, 2020
  45. ajtowns force-pushed on Dec 2, 2020
  46. DrahtBot removed the label Needs rebase on Dec 2, 2020
  47. DrahtBot added the label Needs rebase on Dec 2, 2020
  48. ajtowns force-pushed on Dec 4, 2020
  49. DrahtBot removed the label Needs rebase on Dec 4, 2020
  50. DrahtBot added the label Needs rebase on Jan 13, 2021
  51. ajtowns force-pushed on Jan 14, 2021
  52. ajtowns commented at 11:14 am on January 14, 2021: member
    Rebased to deal with adjacent lines changed in #19935
  53. DrahtBot removed the label Needs rebase on Jan 14, 2021
  54. felipsoarez commented at 8:03 pm on January 15, 2021: none
    utACK
  55. in src/txmempool.h:24 in 88019f9a18 outdated 
    20@@ -21,6 +21,7 @@
21 #include <primitives/transaction.h>
22 #include <sync.h>
23 #include <random.h>
24+#include <util/epochguard.h>
    hebasto commented at 9:09 pm on January 15, 2021:

    style nit: while touching headers they could be sorted:

    0#include <random.h>
1#include <sync.h>
2#include <util/epochguard.h>
    ajtowns commented at 4:53 am on February 9, 2021:
    Sorted in #20944
  56. in src/txmempool.h:831 in 88019f9a18 outdated 
    862-    bool visited(txiter it) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
863-        assert(m_has_epoch_guard);
864-        bool ret = it->m_epoch >= m_epoch;
865-        it->m_epoch = std::max(it->m_epoch, m_epoch);
866-        return ret;
867+    bool visited(const txiter it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch) {
    hebasto commented at 9:13 pm on January 15, 2021:

    style nit, suggested by clang-format:

    0    bool visited(const txiter it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch)
1    {
  57. in src/txmempool.h:835 in 88019f9a18 outdated 
    868+        return m_epoch.visited(it->m_epoch_marker);
869     }
870 
871-    bool visited(Optional<txiter> it) const EXCLUSIVE_LOCKS_REQUIRED(cs) {
872-        assert(m_has_epoch_guard);
873+    bool visited(Optional<txiter> it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch) {
    hebasto commented at 9:14 pm on January 15, 2021:

    style nit, suggested by clang-format:

    0    bool visited(Optional<txiter> it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch)
1    {
  58. in src/util/epochguard.h:40 in 88019f9a18 outdated 
    35+private:
36+    uint64_t m_raw_epoch = 0;
37+    bool m_guarded = false;
38+
39+public:
40+    Epoch() { }
    hebasto commented at 9:14 pm on January 15, 2021:

    style nit, suggested by clang-format:

    0    Epoch() {}
  59. in src/util/epochguard.h:46 in 88019f9a18 outdated 
    41+    Epoch(const Epoch&) = delete;
42+    Epoch& operator=(const Epoch&) = delete;
43+
44+    bool guarded() const { return m_guarded; }
45+
46+    class Marker {
    hebasto commented at 9:14 pm on January 15, 2021:

    style nit, suggested by clang-format:

    0    class Marker
1    {
  60. in src/util/epochguard.h:55 in 88019f9a18 outdated 
    50+        // only allow modification via Epoch member functions
51+        friend class Epoch;
52+        Marker& operator=(const Marker&) = delete;
53+    };
54+
55+    class SCOPED_LOCKABLE Guard {
    hebasto commented at 9:15 pm on January 15, 2021:

    style nit, suggested by clang-format:

    0    class SCOPED_LOCKABLE Guard
1    {
  61. in src/util/epochguard.h:18 in 88019f9a18 outdated 
    13+/** Epoch: RAII-style guard for using epoch-based graph traversal algorithms.
14+ *     When walking ancestors or descendants, we generally want to avoid
15+ * visiting the same transactions twice. Some traversal algorithms use
16+ * std::set (or setEntries) to deduplicate the transaction we visit.
17+ * However, use of std::set is algorithmically undesirable because it both
18+ * adds an asymptotic factor of O(log n) to traverals cost and triggers O(n)
    hebasto commented at 9:17 pm on January 15, 2021:

    typo, #17925 (review):

    0 * adds an asymptotic factor of O(log n) to traversals cost and triggers O(n)
  62. in src/util/epochguard.h:71 in 88019f9a18 outdated 
    63+            ++m_epoch.m_raw_epoch;
64+            m_epoch.m_guarded = true;
65+        }
66+        ~Guard() UNLOCK_FUNCTION()
67+        {
68+            ++m_epoch.m_raw_epoch; // ensure clear separation between epochs
    hebasto commented at 9:40 pm on January 15, 2021: 
    0        {
1            assert(m_epoch.m_guarded);
2            ++m_epoch.m_raw_epoch; // ensure clear separation between epochs
  63. hebasto commented at 9:46 pm on January 15, 2021: member

    ACK 88019f9a183d396713fd357604a6e472c5ed8807

    It seems both CTxMemPool::visited member functions could be private.

  64. DrahtBot added the label Needs rebase on Feb 8, 2021
  65. [refactor] txmempool: split epoch logic into class fd6580e405
  66. ajtowns force-pushed on Feb 9, 2021
  67. ajtowns commented at 5:41 am on February 9, 2021: member

    :birthday: This PR turned 1 the other week! Rebased on top of #20944 due to header reordering, and addressed @hebasto’s nits.

    (I think the mempool visited methods are public deliberately, so that they could be used by external functions if desired; so haven’t made them private)

  68. DrahtBot removed the label Needs rebase on Feb 9, 2021
  69. JeremyRubin commented at 4:42 am on February 10, 2021: contributor
    Yes this is correct; IIRC there’s some stalled out patches which require them to be visible :)
  70. in src/util/epochguard.h:21 in fd6580e405 
    16+ * std::set (or setEntries) to deduplicate the transaction we visit.
17+ * However, use of std::set is algorithmically undesirable because it both
18+ * adds an asymptotic factor of O(log n) to traversals cost and triggers O(n)
19+ * more dynamic memory allocations.
20+ *     In many algorithms we can replace std::set with an internal mempool
21+ * counter to track the time (or, "epoch") that we began a traversal, and
    jonatack commented at 6:10 pm on February 10, 2021: 
    0 * counter to track the time (or, "epoch") that we began a traversal and
  71. in src/util/epochguard.h:28 in fd6580e405 
    23+ * determine if that transaction has not yet been visited during the current
24+ * traversal's epoch.
25+ *     Algorithms using std::set can be replaced on a one by one basis.
26+ * Both techniques are not fundamentally incompatible across the codebase.
27+ * Generally speaking, however, the remaining use of std::set for mempool
28+ * traversal should be viewed as a TODO for replacement with an epoch based
    jonatack commented at 6:10 pm on February 10, 2021: 
    0 * traversal should be viewed as a TODO for replacement with an epoch-based
  72. jonatack approved
  73. jonatack commented at 7:02 pm on February 10, 2021: member

    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

    example clang warning

    0/txmempool.h:840:24: warning: calling function 'visited' requires holding mutex 'm_epoch' exclusively [-Wthread-safety-analysis]
1        return m_epoch.visited(it->m_epoch_marker);

    Ignore the two comments below unless you need to retouch anything (the documentation was move-only anyway).

  74. hebasto approved
  75. hebasto commented at 8:12 am on February 24, 2021: member

    re-ACK fd6580e405699ccb051fd2a34525e48d3253673d, since my previous review:

    • rebased
    • style nits and typo addressed
    • added assert(m_epoch.m_guarded); as suggested
    • the Epoch ctor is default now (was empty)
  76. laanwj merged this on Feb 24, 2021
  77. laanwj closed this on Feb 24, 2021
  78. sidhujag referenced this in commit 866b0fef80 on Feb 24, 2021
  79. Fabcien referenced this in commit d4e83e3031 on Apr 6, 2022
  80. DrahtBot locked this on Aug 16, 2022


ajtowns JeremyRubin DrahtBot laanwj hebasto jonatack felipsoarez

Labels
Refactoring Mempool

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-12-18 18:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me