Repository: bitcoin/bitcoin
File: src/validation.cpp (C++)

Code before:
    // Genesis block can't be invalidated
    assert(pindex);
    if (pindex->nHeight == 0) return false;

    CBlockIndex* to_mark_failed = pindex;
    bool pindex_was_in_chain = false;
    int disconnected = 0;

    // We do not allow ActivateBestChain() to run while InvalidateBlock() is
    // running, as that could cause the tip to change while we disconnect
    // blocks.
    LOCK(m_chainstate_mutex);

    // We'll be acquiring and releasing cs_main below, to allow the validation
    // callbacks to run. However, we should keep the block index in a
    // consistent state as we disconnect blocks -- in particular we need to
    // add equal-work blocks to setBlockIndexCandidates as we disconnect.
    // To avoid walking the block index repeatedly in search of candidates,
    // build a map once so that we can look up candidate blocks by chain
    // work as we go.
    std::multimap<const arith_uint256, CBlockIndex *> candidate_blocks_by_work;
    // Map to cache candidates not in the main chain that might need invalidating.
    // Maps fork block in chain to the candidates for invalidation.
    std::multimap<const CBlockIndex*, CBlockIndex*> cand_invalid_descendants;
    // Map to cache candidates for m_best_header
    std::multimap<const arith_uint256, CBlockIndex*> best_header_blocks_by_work;

    {
        LOCK(cs_main);
        for (auto& entry : m_blockman.m_block_index) {
            CBlockIndex* candidate = &entry.second;
            // We don't need to put anything in our active chain into the
            // multimap, because those candidates will be found and considered
            // as we disconnect.
            // Instead, consider only non-active-chain blocks that have at
            // least as much work as where we expect the new tip to end up.
            if (!m_chain.Contains(candidate) &&
                    !CBlockIndexWorkComparator()(candidate, pindex->pprev) &&
                    candidate->IsValid(BLOCK_VALID_TRANSACTIONS) &&
                    candidate->HaveNumChainTxs()) {
                candidate_blocks_by_work.insert(std::make_pair(candidate->nChainWork, candidate));
            }
            // Similarly, populate cache for blocks not in main chain to invalidate
            if (!m_chain.Contains(candidate) &&
                !CBlockIndexWorkComparator()(candidate, pindex->pprev)) {
                cand_invalid_descendants.insert(std::make_pair(m_chain.FindFork(candidate), candidate));
                best_header_blocks_by_work.insert(std::make_pair(candidate->nChainWork, candidate));
            }
        }
    }


Review comment (bug):
Since this map is a superset of `candidate_blocks_by_work `, I think we could just have one, and instead check for `IsValid(BLOCK_VALID_TRANSACTIONS) && HaveNumChainTxs()` further down when we update `setBlockIndexCandidates`? I suspect the memory impllications should be negligible either way, but I think it would clean up the code a bit?

E.g. something like:

<details>
<summary>git diff on 4ba2e480ff</summary>

```diff
diff --git a/src/validation.cpp b/src/validation.cpp
index f9c900ef27..ead0454f7b 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -3689,12 +3689,10 @@ bool Chainstate::InvalidateBlock(BlockValidationState& state, CBlockIndex* pinde
     // To avoid walking the block index repeatedly in search of candidates,
     // build a map once so that we can look up candidate blocks by chain
     // work as we go.
-    std::multimap<const arith_uint256, CBlockIndex *> candidate_blocks_by_work;
+    std::multimap<const arith_uint256, CBlockIndex *> highpow_outofchain_headers;
     // Map to cache candidates not in the main chain that might need invalidating.
     // Maps fork block in chain to the candidates for invalidation.
     std::multimap<const CBlockIndex*, CBlockIndex*> cand_invalid_descendants;
-    // Map to cache candidates for m_best_header
-    std::multimap<const arith_uint256, CBlockIndex*> best_header_blocks_by_work;
 
     {
         LOCK(cs_main);
@@ -3706,16 +3704,9 @@ bool Chainstate::InvalidateBlock(BlockValidationState& state, CBlockIndex* pinde
             // Instead, consider only non-active-chain blocks that have at
             // least as much work as where we expect the new tip to end up.
             if (!m_chain.Contains(candidate) &&
-                    !CBlockIndexWorkComparator()(candidate, pindex->pprev) &&
-                    candidate->IsValid(BLOCK_VALID_TRANSACTIONS) &&
-                    candidate->HaveNumChainTxs()) {
-                candidate_blocks_by_work.insert(std::make_pair(candidate->nChainWork, candidate));
-            }
-            // Similarly, populate cache for blocks not in main chain to invalidate
-            if (!m_chain.Contains(candidate) &&
-                !CBlockIndexWorkComparator()(candidate, pindex->pprev)) {
+                    !CBlockIndexWorkComparator()(candidate, pindex->pprev)) {
+                highpow_outofchain_headers.insert(std::make_pair(candidate->nChainWork, candidate));
                 cand_invalid_descendants.insert(std::make_pair(m_chain.FindFork(candidate), candidate));
-                best_header_blocks_by_work.insert(std::make_pair(candidate->nChainWork, candidate));
             }
         }
     }
@@ -3774,11 +3765,9 @@ bool Chainstate::InvalidateBlock(BlockValidationState& state, CBlockIndex* pinde
         // Determine new best header
         if (m_chainman.m_best_header->nStatus & BLOCK_FAILED_MASK) {
             m_chainman.m_best_header = invalid_walk_tip->pprev;
-            auto best_header_it = best_header_blocks_by_work.lower_bound(m_chainman.m_best_header->nChainWork);
-            while (best_header_it != best_header_blocks_by_work.end()) {
-                if (best_header_it->second->nStatus & BLOCK_FAILED_MASK) {
-                    best_header_it = best_header_blocks_by_work.erase(best_header_it);
-                } else {
+            auto best_header_it = highpow_outofchain_headers.lower_bound(m_chainman.m_best_header->nChainWork);
+            while (best_header_it != highpow_outofchain_headers.end()) {
+                if (!(best_header_it->second->nStatus & BLOCK_FAILED_MASK)) {
                     if (!CBlockIndexWorkComparator()(best_header_it->second, m_chainman.m_best_header)) {
                         m_chainman.m_best_header = best_header_it->second;
                     }
@@ -3788,11 +3777,12 @@ bool Chainstate::InvalidateBlock(BlockValidationState& state, CBlockIndex* pinde
         }
 
         // Add any equal or more work headers to setBlockIndexCandidates
-        auto candidate_it = candidate_blocks_by_work.lower_bound(invalid_walk_tip->pprev->nChainWork);
-        while (candidate_it != candidate_blocks_by_work.end()) {
-            if (!CBlockIndexWorkComparator()(candidate_it->second, invalid_walk_tip->pprev)) {
-                setBlockIndexCandidates.insert(candidate_it->second);
-                candidate_it = candidate_blocks_by_work.erase(candidate_it);
+        auto candidate_it = highpow_outofchain_headers.lower_bound(invalid_walk_tip->pprev->nChainWork);
+        while (candidate_it != highpow_outofchain_headers.end()) {
+            if (!CBlockIndexWorkComparator()(candidate_it->second, invalid_walk_tip->pprev) &&
+                candidate_it->second->IsValid(BLOCK_VALID_TRANSACTIONS) &&
+                candidate_it->second->HaveNumChainTxs()) {
+                    setBlockIndexCandidates.insert(candidate_it->second);
             } else {
                 ++candidate_it;
             }

```
</details>


Code after:
    // Genesis block can't be invalidated
    assert(pindex);
    if (pindex->nHeight == 0) return false;

    CBlockIndex* to_mark_failed = pindex;
    bool pindex_was_in_chain = false;
    int disconnected = 0;

    // We do not allow ActivateBestChain() to run while InvalidateBlock() is
    // running, as that could cause the tip to change while we disconnect
    // blocks.
    LOCK(m_chainstate_mutex);

    // We'll be acquiring and releasing cs_main below, to allow the validation
    // callbacks to run. However, we should keep the block index in a
    // consistent state as we disconnect blocks -- in particular we need to
    // add equal-work blocks to setBlockIndexCandidates as we disconnect.
    // To avoid walking the block index repeatedly in search of candidates,
    // build a map once so that we can look up candidate blocks by chain
    // work as we go.
    std::multimap<const arith_uint256, CBlockIndex*> highpow_outofchain_headers;

    {
        LOCK(cs_main);
        for (auto& entry : m_blockman.m_block_index) {
            CBlockIndex* candidate = &entry.second;
            // We don't need to put anything in our active chain into the
            // multimap, because those candidates will be found and considered
            // as we disconnect.
            // Instead, consider only non-active-chain blocks that score
            // at least as good with CBlockIndexWorkComparator as the new tip.
            if (!m_chain.Contains(candidate) &&
                !CBlockIndexWorkComparator()(candidate, pindex->pprev) &&
                !(candidate->nStatus & BLOCK_FAILED_MASK)) {
                highpow_outofchain_headers.insert({candidate->nChainWork, candidate});
            }
        }
    }

    // Disconnect (descendants of) pindex, and mark them invalid.
    while (true) {
        if (m_chainman.m_interrupt) break;

        // Make sure the queue of validation callbacks doesn't grow unboundedly.
        if (m_chainman.m_options.signals) LimitValidationInterfaceQueue(*m_chainman.m_options.signals);

        LOCK(cs_main);
        // Lock for as long as disconnectpool is in scope to make sure MaybeUpdateMempoolForReorg is
        // called after DisconnectTip without unlocking in between
        LOCK(MempoolMutex());
        if (!m_chain.Contains(pindex)) break;