txmempool: split epoch logic into class #18017

Mind switching from the member initialization list to the default member initializers?

Mind switching from the member initialization list to the default member initializer?

micro-nit: These comments are so obvious that seem redundant :)

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

./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]
        explicit Guard(Epoch& epoch) EXCLUSIVE_LOCK_FUNCTION(epoch) LOCKS_EXCLUDED(epoch);
                                     ^
...
./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]
    bool visited(Marker& marker) const EXCLUSIVE_LOCKS_REQUIRED(*this) {
                                       ^
...
./txmempool.h:691:121: warning: 'locks_excluded' attribute requires arguments whose type is annotated with 'capability' attribute; type here is 'Epoch' [-Wthread-safety-attributes]
    void UpdateTransactionsFromBlock(const std::vector<uint256>& vHashesToUpdate) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main) LOCKS_EXCLUDED(m_epoch);
                                                                                                                        ^
...
./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]
    bool visited(const txiter it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch) {
                                        ^
...
./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]
    bool visited(Optional<txiter> it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch) {
                                            ^

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

class LOCKABLE Epoch

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

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?

Indeed :) IDK why I saw warnings...

From the Thread Safety Analysis docs:

The caller must not hold the given capability on entry

It seems LOCKS_EXCLUDED(epoch) is redundant, no?

Is this used?

(I'm fine leaving it if it isn't used, just curious).

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.

nit: how would you feel about:

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

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

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:

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

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

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.

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.

Maybe best to move this into it's own header-only file/all headers to minimize conflict with #17786?

Moved into util/epochguard.h

micronit: may be worth adding a comment here that the assert is redundant when it != nullopt, but is used for consistency when it == nullopt.

style nit: while touching headers they could be sorted:

#include <random.h>
#include <sync.h>
#include <util/epochguard.h>

Sorted in #20944

style nit, suggested by clang-format:

    bool visited(const txiter it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch)
    {

style nit, suggested by clang-format:

    bool visited(Optional<txiter> it) const EXCLUSIVE_LOCKS_REQUIRED(cs, m_epoch)
    {

style nit, suggested by clang-format:

    Epoch() {}

style nit, suggested by clang-format:

    class Marker
    {

style nit, suggested by clang-format:

    class SCOPED_LOCKABLE Guard
    {

typo, #17925 (review):

 * adds an asymptotic factor of O(log n) to traversals cost and triggers O(n)

        {
            assert(m_epoch.m_guarded);
            ++m_epoch.m_raw_epoch; // ensure clear separation between epochs

 * counter to track the time (or, "epoch") that we began a traversal and

 * traversal should be viewed as a TODO for replacement with an epoch-based