[refactor] rewrite DisconnectedBlockTransactions to not use boost #28385

The comment here about insertion_order needs updating.

Done, thanks

This is only used in validation.cpp, and one unit test, so I wonder if it makes sense to move it to a separate header?

makes sense to me. kernel/disconnected_transactions.h?

Done

nit: would suggest reserving to avoid rehashing the set

        std::unordered_set<uint256, SaltedTxidHasher> txids;
        txids.reserve(vtx.size());

This line went away with the list + map approach so marking as resolved

nit: could avoid creating it_next

            if (txids.count((*it)->GetHash()) > 0) {
                cachedInnerUsage -= RecursiveDynamicUsage(*it);
                it = queuedTx.erase(it);
            } else {
                ++it;
            }

Or actually, could use std::list::remove_if. Quickly conveys the intent of the code imo, and looks like it speeds up the bench a tiny bit, going from

| ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 7,204,642.33 | 138.80 | 0.2% | 0.87 | AddAndRemoveDisconnectedBlockTransactions10 | 5,293,310.64 | 188.92 | 0.4% | 0.64 | AddAndRemoveDisconnectedBlockTransactions100 | 6,931,825.73 | 144.26 | 0.9% | 0.84 | AddAndRemoveDisconnectedBlockTransactions90

to

| ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 6,971,191.70 | 143.45 | 0.8% | 0.84 | AddAndRemoveDisconnectedBlockTransactions10 | 4,991,280.27 | 200.35 | 0.7% | 0.60 | AddAndRemoveDisconnectedBlockTransactions100 | 6,632,837.50 | 150.77 | 0.6% | 0.80 | AddAndRemoveDisconnectedBlockTransactions90

<details> <summary>git diff</summary>

diff --git a/src/validation.h b/src/validation.h
index 3e1a024d09..c81331f950 100644
--- a/src/validation.h
+++ b/src/validation.h
@@ -283,15 +283,13 @@ struct DisconnectedBlockTransactions {
         std::unordered_set<uint256, SaltedTxidHasher> txids;
         std::transform(vtx.cbegin(), vtx.cend(), std::inserter(txids, txids.end()), [](const auto& tx) { return tx->GetHash(); });
         // Iterate through entire list once, removing any transactions in the block.
-        auto it = queuedTx.begin();
-        while (it != queuedTx.end()) {
-            auto it_next = std::next(it);
-            if (txids.count((*it)->GetHash()) > 0) {
-                cachedInnerUsage -= RecursiveDynamicUsage(*it);
-                queuedTx.erase(it);
+        queuedTx.remove_if([&](const CTransactionRef& tx) {
+            if (txids.count(tx->GetHash()) > 0) {
+                cachedInnerUsage -= RecursiveDynamicUsage(tx);
+                return true;
             }
-            it = it_next;
-        }
+            return false;
+        });
     }
 
     // Remove the earliest-inserted transaction.

</details>

remove_if doesn't change the size of the container, so your patch is incomplete, no?

queuedTx is not a vector but a list, so I think just removing it from the list is sufficient?

Why would the container make a difference? If I print std::list::size(), it remains unchanged.

#include <algorithm>
#include <iostream>
#include <list>
  
int main()
{
    std::list<char> str1 {'T', ' ', 't'};

 
    auto noSpaceEnd = std::remove(str1.begin(), str1.end(), ' ');
 
         std::cout  << " size: " << str1.size() << '\n';

    str1.erase(noSpaceEnd, str1.end());
 
     std::cout  << " size: " << str1.size() << '\n';
 
  
}

 size: 3

 size: 2

Ah, sorry, you are using std::list::remove_if, not std::remove_if.

Yeah, I didn't realize they behaved differently but with std::list::remove_if the items are indeed removed from the container, as opposed to just shifted:

#include <algorithm>
#include <iostream>
#include <list>
  
int main()
{
    std::list<char> str1 {'T', ' ', 't'};

    str1.remove(' ');
         std::cout  << " size: " << str1.size() << '\n';
  
}

size: 2

This line went away with the list + map approach so marking as resolved

Since the dynamic memory usage of queuedTx now changed, I think this is behaviour change as we'll be dropping entries less frequently?

Perhaps (I think it's negligible compared to the transactions themselves), and would probably be an improvement.

Perhaps worth adding an assert(!disconnectpool->queuedTx.empty()) here? I know we already assume that's the case because disconnectpool is non-nullptr and because of the dynamic memory usage check, but i think adding an assertion may make this more robust, since for an empty vector we have UB here and two lines down.

Added in the while loop condition, feels a bit more robust than crashing

this comment still needs updating

Wow, I just realized I was pushing changes to the wrong branch 🤦 I have changed this now

I think this should be included in validation.cpp instead.

moved

In 5a1233c0:

Small idea: what about having an always increasing lock_time number?. It will ensure different tx ids and let you remove the unique_set_num as well as the fast RNG for the prevout hash which doesn't seems to be used anywhere.

E.g.

static BlockTxns CreateRandomTransactions(size_t num_txns)
{
    static uint32_t next_locktime{0};

    BlockTxns txns;
    txns.reserve(num_txns);
    // Simplest spk for every tx
    CScript spk = CScript() << OP_TRUE;
    for (uint32_t i = 0; i < num_txns; ++i) {
        CMutableTransaction tx;
        tx.vin.resize(1);
        tx.vout.resize(1);
        tx.vout.emplace_back(CTxOut{CENT, spk});
        tx.nLockTime = next_locktime++;
        txns.emplace_back(MakeTransactionRef(tx));
    }
    return txns;
}

Good point about using a static var. I've simplified this but instead of using locktime or prevout n, I'm just having each tx spend the previous one. Should be sufficient to ensure we don't get any duplicates, so that gets rid of unique_set_num and the rng.

In In 5a1233c0:

Unused testing_setup arg

deleted

I see how this happened here, but calling this list a Queue is super confusing :)

:sweat_smile: renamed to List

Any reason not to add std::list to memusage.h instead?

~This could look a little cleaner using extract()~.

for (const auto& tx : vtx) {
    if (auto node = iters_by_txid.extract(tx->GetHash())) {
        auto& list_iter = node.mapped();
        cachedInnerUsage -= RecursiveDynamicUsage(*list_iter);
        queuedTx.erase(list_iter);
    }
}

Edit: Ignore this. I benched and performance is worse.

Hmm, why no addTransactions(const std::vector<CTransactionRef>& vtx) to match removeForBlock() ?

Is it because the tx order needs to be reversed?

That would allow a iters_by_txid.reserve(vtx.size()); which gets me a ~10% speedup in the benches.

Edit: removed snark after finding the comment I needed.

Edit2: I suppose this is a potential optimization unrelated to this PR, but an addTransactionsForBlock(const CBlock&) would be unambiguous as to tx order if this is interesting.

Hmm, why no addTransactions(const std::vector<CTransactionRef>& vtx) to match removeForBlock() ?

I had been trying to keep the diff as small as possible

That would allow a iters_by_txid.reserve(vtx.size()); which gets me a ~10% speedup in the benches.

This is worth it though, so I've done this now - thanks!

Edit: removed snark after finding the comment I needed.

Added a comment as I agree it wasn't super obvious why we reverse vtx

Thanks for catching my problem here!

I realize this came from my patch but..

I think we still want to disconnectpool.clear() here just in case. Otherwise it's potentially a change of behavior as we're keeping these tx's alive longer (until disconnectpool goes out of scope) than before.

disconnectpool is cleared as part of take() though?

Yes, sorry! I meant queuedTx.clear().

Added a local scope for queuedTx to go out of

Why prefer take() here? Seems like that's relying on the side-effect, as opposed to clear() which does the thing we want.

It just seemed like slightly more realistic usage but that doesn't seem to be a concern here, so changed to clear() now.

Nit: With private members and a ctor, I'd call this a class now. But that's arbitrary and I don't think we have any guidelines for it.

True, changed

This could potentially be done more efficiently by iterating to find the number to evict, then doing a single splice() rather than multiple emplace_back(). I doubt it's worth the code complexity though.

Didn't end up doing this as it requires knowing how much the memory usage will change and I'm not sure if I'd implement it 100% accurately...

nit: TxList seems like a more appropriate name. But I'd be equally happy just inlining it, just as readable imo.

    std::unordered_map<uint256, decltype(queuedTx)::iterator, SaltedTxidHasher> iters_by_txid;

called it TxList

"Blocks are disconnected in descending order by block height." I think this should be in the function docstring as it's not an implementation detail but an important part of its interface? We expect the caller to:

• call this function for the outermost/highest block first
• keep vtx in the same order as they appear in the block (the reversion is an implementation detail and not relevant for this function's docstring imo, although we do want to document take's behaviour as per my other comment)
• ensure all tx ids provided are unique, even across multiple calls

(ideally using structured "pre" doxygen tags?)

Added notes about order of queuedTx in the class description and stated that the callers should go descending order by block height in the comment for this function.

Note: DynamicMemoryUsage in the boost implementation was returning a fixed estimate (+80B) for usage per entry, so the "before" size here would be 720 for 1 tx, 72000 for 100 (I'm not sure how accurate this is but those are the numbers).

This means the number has increased so we'd drop more stuff now than before (in the rare case of a multi-block reorg).

Maybe I'm misunderstanding things, but I find this language quite unintuitive and if my understanding is correct - misleading. Assume we have a chaintip at height 100, and we reorged the last 2 blocks, i.e. 100 and 99 (in that order) are disconnected.

• "from oldest to newest": I would call a tx in block 99 older than a tx in block 100, but disconnectpool.take() returns txs from block 100 before block 99
• "the latest mined block that was disconnected" could mean (and this was my first intuition) "the latest block that was disconnected", i.e. block 99, or "the highest of the block(s) that were disconnected", i.e. the previous chaintip, which I think is what is meant here.

Suggested rephrasing, which (imo) removes that ambiguity and also highlights the intent a bit more:

    // disconnectpool.take() returns entries first sorted by descending blockheight (i.e. txs from
    // the previous chaintip appear first) and then by reversed in-block order.
    // For example, if blocks 100 and 99 are disconnected, disconnectpool.take() returns 
    // [100:n, 100:n-1, ..., 100:0, 99:m, 99:m-1, ..., 99:0]
    // Iterate disconnectpool.take(( in reverse, so that we ensure first adding parent transactions
    // before children are added (if any).

Actually, I think moving the first lines that describe the .take() return value to the DisconnectedBlockTransactions::take docstring makes probably more sense, and then just reference that here?

Er, I found this a bit hard to parse too, so I've reworded the comment but a bit differently.

nit: can be const

        const auto queuedTx = disconnectpool.take();

done

For readability, would you consider moving this to its own private function?

<details> <summary>git diff</summary>

diff --git a/src/kernel/disconnected_transactions.h b/src/kernel/disconnected_transactions.h
index 6e12059874..d1a8b5e989 100644
--- a/src/kernel/disconnected_transactions.h
+++ b/src/kernel/disconnected_transactions.h
@@ -37,6 +37,20 @@ private:
     using List = decltype(queuedTx);
     std::unordered_map<uint256, List::iterator, SaltedTxidHasher> iters_by_txid;
 
+    // Trim and return the earliest-added entries until we are within memory bounds.
+    std::vector<CTransactionRef> EvictTransactionsIfNeeded()
+    {
+        std::vector<CTransactionRef> evicted;
+        while (!queuedTx.empty() && DynamicMemoryUsage() > m_max_mem_usage) {
+            evicted.emplace_back(queuedTx.front());
+            cachedInnerUsage -= RecursiveDynamicUsage(queuedTx.front());
+            iters_by_txid.erase(queuedTx.front()->GetHash());
+            queuedTx.pop_front();
+        }
+
+        return evicted;
+    }
+
 public:
     DisconnectedBlockTransactions(size_t max_mem_usage) : m_max_mem_usage{max_mem_usage} {}
 
@@ -64,7 +78,6 @@ public:
     // Returns vector of transactions that were evicted for size-limiting.
     [[nodiscard]] std::vector<CTransactionRef> AddTransactionsFromBlock(const std::vector<CTransactionRef>& vtx)
     {
-        std::vector<CTransactionRef> evicted;
         // Blocks are disconnected in descending order by block height. Within each block, add
         // transactions in reverse order so that transactions with dependencies on other
         // transactions (if any) are at the beginning. If this data structure grows too large, we
@@ -77,13 +90,7 @@ public:
             cachedInnerUsage += RecursiveDynamicUsage(*block_it);
         }
 
-        // Trim the earliest-added entries until we are within memory bounds.
-        while (!queuedTx.empty() && DynamicMemoryUsage() > m_max_mem_usage) {
-            evicted.emplace_back(queuedTx.front());
-            cachedInnerUsage -= RecursiveDynamicUsage(queuedTx.front());
-            iters_by_txid.erase(queuedTx.front()->GetHash());
-            queuedTx.pop_front();
-        }
+        const auto evicted{EvictTransactionsIfNeeded()};
         return evicted;
     }
 

</details>

Sure, moved

nit

static const unsigned int MAX_DISCONNECTED_TX_POOL_SIZE = 20'000;

Done

nit: less abbreviations if not necessary

    // DisconnectedBlockTransactions with a comfortable maximum memory usage so that nothing is evicted.

done

Yes!

Here list_iter can never be deduced as a reference to iter->second which would then be erased right?

An alternative to avoid having to ask this question could be to simply erase from iters_by_txid last:

cachedInnerUsage -= RecursiveDynamicUsage(*iter->second);
queuedTx.erase(iter->second);
iters_by_txid.erase(iter);

Doesn't this invalidate iter, as it would point to something that's since been erased from queuedTx?

Currently, by inheriting from X, we're accounting for the size of X (as this will be included in sizeof(list_node<X>). I think that makes sense - X is owned by the list.

I'm not familiar with std::list implementations, but I'm not sure if accounting for both X as well as void* ptr_val makes sense. I think the node owning X is plenty, I don't see the need for an additional pointer?

Finally, by inheriting from private X we cannot use this on non-class/struct types, e.g. it wouldn't work for std::list<int>. A suggestion to address both problems (and it seems the same approach was taken for e.g. stl_tree_node:

struct list_node
{
private:
    void* ptr_next;
    void* ptr_prev;
    X val;

I was looking into this yesterday and arrived at both of the same conclusions.

Poked at libstdc++'s impl with gdb:

(gdb) print -pretty off -raw-values -- queuedTx ... _M_node = {<std::__detail::_List_node_base> = {_M_next = 0x55555556aeb0, _M_prev = 0x55555556aed0}, _M_size = 2}}} ...

Which agrees with (on 64bit):

(gdb) print sizeof(queuedTx)
$7 = 24

So it appears to me that in general a list will be: A structure with pointer to its head and tail nodes, plus an additional int for size. Plus for each node: a pointer to prev, next, and the data itself.

I'm still working on confirming those numbers fully with an implementation though.

Thanks! I think this is correct (for future reference I'm looking at https://github.com/gcc-mirror/gcc/blob/releases/gcc-13.2.0/libstdc%2B%2B-v3/include/bits/stl_list.h#L232-L245), changed.

Do we not also need to account for sizeof(l) for the list overhead?

    return MallocUsage(sizeof(l)) + MallocUsage(sizeof(list_node<X>)) * l.size();

I don't think that part is dynamically allocated...?

Ah yes the hint is in the function name, woops 🙃

I think cachedInnerUsage shouldn't account for the memory usage of the shared_ptr<CTransaction>, only for the CTransaction. We already account for the shared_ptr in DisconnectedBlockTransactions::DynamicMemoryUsage (as I think it should be).

<details> <summary>git diff</summary>

diff --git a/src/kernel/disconnected_transactions.h b/src/kernel/disconnected_transactions.h
index 0c170e7a4b..a3bc77b6fc 100644
--- a/src/kernel/disconnected_transactions.h
+++ b/src/kernel/disconnected_transactions.h
@@ -50,7 +50,7 @@ private:
 
         while (!queuedTx.empty() && DynamicMemoryUsage() > m_max_mem_usage) {
             evicted.emplace_back(queuedTx.front());
-            cachedInnerUsage -= RecursiveDynamicUsage(queuedTx.front());
+            cachedInnerUsage -= RecursiveDynamicUsage(*queuedTx.front());
             iters_by_txid.erase(queuedTx.front()->GetHash());
             queuedTx.pop_front();
         }
@@ -91,7 +91,7 @@ public:
         for (auto block_it = vtx.rbegin(); block_it != vtx.rend(); ++block_it) {
             auto it = queuedTx.insert(queuedTx.end(), *block_it);
             iters_by_txid.emplace((*block_it)->GetHash(), it);
-            cachedInnerUsage += RecursiveDynamicUsage(*block_it);
+            cachedInnerUsage += RecursiveDynamicUsage(**block_it);
         }
         return LimitMemoryUsage();
     }
@@ -108,7 +108,7 @@ public:
             if (iter != iters_by_txid.end()) {
                 auto list_iter = iter->second;
                 iters_by_txid.erase(iter);
-                cachedInnerUsage -= RecursiveDynamicUsage(*list_iter);
+                cachedInnerUsage -= RecursiveDynamicUsage(**list_iter);
                 queuedTx.erase(list_iter);
             }
         }

</details>

I agree, changed (but in the rewrite commit instead of here)

Revisiting this again, I think my suggestion was wrong and we're now underestimating memory usage.

In DisconnectedBlockTransactions::DynamicMemoryUsage, with memusage::DynamicUsage(queuedTx) we account only for the dynamic allocation of queuedTx, which is (2 ptrs + sizeof(CTransactionRef)) * size. This corresponds to 2+2 pointers per item, and does not include the managed CTransaction object or the control block.

In AddTransactionsFromBlock (and other places where we modify cachedInnerUsage), when we calculate RecursiveDynamicUsage(**block_it) (i.e. on a CTransaction) as I suggested here, we only account for the vins and vouts of the transaction, and not for the CTransaction object nor the control block.

So effectively, we do need to account for the CTransactionRef in both places, because in DynamicMemoryUsage we account for the 2 pointers, and in AddTransactionRef we account for the managed object and the control block. In the current implementation, we are not accounting for the CTransaction or the control block, even though everything is allocated on the heap.

To illustrate, for a coinbase transaction, the difference in AddTransactionsFromBlock is:

(lldb) p (size_t) RecursiveDynamicUsage(*block_it)
(size_t) 640
(lldb) p (size_t) RecursiveDynamicUsage(**block_it)
(size_t) 448

cc @ismaelsadeeq perhaps something to include in #28530?

Fixed in https://github.com/stickies-v/bitcoin/commit/87f3f28b3acfc329eaed0b0cce6ff589271bfefd - happy to open a separate pull if you prefer though.

Thanks @stickies-v happy to add it to #28530, I f I understand you correctly, you mean that we are not accounting for the shared_ptr and the CTransaction object before only the vins and vouts.

In DisconnectedBlockTransactions::DynamicMemoryUsage, with memusage::DynamicUsage(queuedTx) we account only for the dynamic allocation of queuedTx, which is (2 ptrs + sizeof(CTransactionRef)) * size. This corresponds to 2+2 pointers per item.

I think this is correct. We only account for the vins and vouts, hence the CTransaction Object itself and the shared_ptr that makes up CTransactionRef are not accounted.

With https://github.com/stickies-v/bitcoin/commit/87f3f28b3acfc329eaed0b0cce6ff589271bfefd we are now accounting for the shared_ptr CTransaction Object, its inputs and outputs and the dynamic allocation of queuedTx in DynamicMemoryUsage.

because we pass shared_ptr<CTransaction> which executes the below version of RecursiveDynamicUsage

template<typename X>
static inline size_t RecursiveDynamicUsage(const std::shared_ptr<X>& p) {
    return p ? memusage::DynamicUsage(p) + RecursiveDynamicUsage(*p) : 0;
}

memusage::DynamicUsage(p) accounts for the size of p which is CTransaction and then accounts for the shared pointer size.

It is unclear to me what

does not include the managed CTransaction object or the control block.

mean

Do you mean the shared_ptr and CTransaction Object ?

Do you mean the shared_ptr and CTransaction Object ?

No. When instantiating a shared_ptr<CTransaction>, typically we would allocate:

1. 2 raw pointers on the stack
2. an instance of CTransaction and a control block on the heap

This is why memusage::DynamicUsage(const std::shared_ptr<X>& p) does not include 2 raw pointers in its calculation. However, since in our case the shared_ptrs are managed by a vector, the 2 raw pointers (from 1.) are also allocated on the heap, and we account for this in DisconnectedBlockTransactions::DynamicMemoryUsage when calling memusage::DynamicUsage(queuedTx).

Thanks for the explanation.

So In memusage::DynamicUsage(const std::shared_ptr<X>& p),

• memusage::DynamicUsage(p) accounts for the CTransaction Class and the control block.
• RecursiveDynamicUsage(*p) accounts for the vins and vouts,
• whereas the two raw pointers are being accounted in cachedInnerUsage.

Will add https://github.com/stickies-v/bitcoin/commit/87f3f28b3acfc329eaed0b0cce6ff589271bfefd in next push

RecursiveDynamicUsage(*p) accounts for the vins and vouts,

We don't want to call RecursiveDynamicUsage(*p) anymore, only RecursiveDynamicUsage(p) as per my suggested fix

whereas the two raw pointers are being accounted in cachedInnerUsage.

Not quite: the raw pointers are accounted for in DisconnectedBlockTransactions::DynamicMemoryUsage when calling memusage::DynamicUsage(queuedTx).

Yeah But calling RecursiveDynamicUsage(p) means calling

template<typename X>
static inline size_t RecursiveDynamicUsage(const std::shared_ptr<X>& p) {
    return p ? memusage::DynamicUsage(p) + RecursiveDynamicUsage(*p) : 0;
}

which brings to my point that

• memusage::DynamicUsage(p) accounts for the CTransaction Class and the control block.
• RecursiveDynamicUsage(*p) accounts for the vins and vouts,

Not quite: the raw pointers are accounted for in DisconnectedBlockTransactions::DynamicMemoryUsage when calling memusage::DynamicUsage(queuedTx).

Yes.

nit: A docstring would be helpful I think:

    //! Memory usage of the CTransaction objects to which queuedTx holds references
    uint64_t cachedInnerUsage = 0;

Added

What's the purpose of these resizes? Do we want two vins and two vouts?

Removed

nit

/** Creates 1 disconnected block and 2 connected blocks, each with BLOCK_VTX_COUNT transactions. Between the disconnected and the first connected block, there will be num_not_shared
 * transactions that are different, all other transactions the exact same. This is to simulate a
 * reorg in which all but num_not_shared transactions are confirmed in the new chain. */

(mostly) taken, some of the documentation lives on the Reorg definition.

nit: docstrings seems to be from a previous version of this PR. Would suggest updating to e.g.:

/** Reorg scenario where all of the transactions in the newly connected block existed in the disconnected block. */

It's the other way around actually, but added.

What do you mean with the other way around?

Still nit, but, I think the first part of the new description (i.e. "Add transactions from DisconnectedBlockTransactions, remove all but one (the disconnected block's coinbase transaction) of them, and then pop from the front until empty.") is too much of an implementation detail for this docstring. And the other 2 benches would probably benefit from a consistent docstring. So new suggestion:

"Test DisconnectedBlockTransactions in a reorg in which {*all*, *90%*, *10%*} of the non-coinbase transactions in the disconnected chain also exist in the new chain."

What do you mean with the other way around?

It's not that all of the transactions in the newly connected block existed in the disconnected block; it's that all of the transactions in the disconnected block are in the new connected chain. I assumed the suggestion was to add a "real world scenario" explanation for what's being tested?

Ah yes, subset and superset and all that. I see what you mean now, your phrasing is better indeed, mine assumes both blocks to be the same size (which they are, but still).

I assumed the suggestion was to add a "real world scenario" explanation for what's being tested?

Yes, the "popping from the front" etc seems not useful to me here, describing what we're testing much more so.

tidy nit

    std::list<CTransactionRef> take()
    {

Done

nit: I think adding take_first() and then removing it in the next non-move commit is not ideal and seems like it could be avoided by moving the memory management commit to come before the boost removal commit, but (I didn't check) it's probably not worth the rebase hell.

I agree it's not worth it as it's still an interface change + implementation change on separate commits, so resolving this.

nit

        // Save transactions to re-add to mempool at end of reorg. If any entries are evicted for exceeding memory limits,
        // remove them and their descendants from the mempool.
        for (auto&& evicted_tx : disconnectpool->AddTransactionsFromBlock(block.vtx)) {
            m_mempool->removeRecursive(*evicted_tx, MemPoolRemovalReason::REORG);
        }

Done

nit: #include <vector>

added

I don't think this is correct. reserve makes sure the buckets are allocated, but the map's size remains unchanged. So MAP_100 significantly underestimates the dynamic usage I think?

This estimation was meant to be for overhead of just the hashmap (see comment above) rather than the full container. I was just trying to make the estimate more accurate as I couldn't get there just by multiplying an entry usage x number of elements.

It's not immediately obvious to me why this is expected behaviour, when we instantiated disconnectpool to the memory usage of a map of 2 + overhead. At the moment, I think this is the case because (as per my previous comment) the MAP_x vars don't include the map nodes, but that seems unintuitive/unexpected?

Why not use CTransactionRef here so we can better estimate the shared_ptr overhead?

    std::unordered_map<uint256, CTransactionRef, SaltedTxidHasher> temp_map;

I felt that a raw pointer would be more accurate as the map is from txids to iterators

Ah yes, you're right.

Nit (clang-format) in commit 79ce9f0aa46de8ff742be83fd6f68eab40e073ec: s/template</template </ - here and just below.

Nit (clang-format) in commit 2765d6f3434c101fe2d46e9313e540aa680fbd77, open brace on newline. Here and for the methods.

Nit in commit 925bb723ca71aa76380b769d8926c7c2ad9bbb7b: This renders with a weird indent on my terminal:

	    /** Add transactions from the block, iterating through vtx in reverse order. Callers should call
     * this function for blocks in descending order by block height.

It is fixed a few commits later, but that line should not need to be re-touched.

Nit: It is just moved here, but everywhere this is used we multiply by 1000, so why define it in kilobytes in the first place?

Also, if you do this, how about replacing _SIZE with _BYTES ?

Agree that the fact that it's kb should be documented / baked in. Going to say out of scope for this PR. Should be easy to do in a followup.

nit: We are always passing the same MAX_DISCONNECTED_TX_POOL_SIZE * 1000 as the constructor argument. We can just declare a default value for it

    DisconnectedBlockTransactions(const size_t max_mem_usage = MAX_DISCONNECTED_TX_POOL_SIZE * 1000) : m_max_mem_usage{max_mem_usage} {}

I'm not a fan of default arguments as it makes it easier to misuse functions. I think it's useful to keep this configurable and would prefer that a caller be aware of / explicit about bounding the memusage.

nit: I think all of the NO_THREAD_SAFETY_ANALYSIS can just be removed from this file, no?

See #28557.

Nit: This looks like a potential null-pointer dereference, but it's safe to assume that disconnectpool is non-empty while we're in the loop. assert(ptx) would make it clear that it's not an oversight.

Nevermind, this is removed in a later commit.

According to the comment: We assume that callers never pass multiple transactions with the same txid.

IMO we should either commit to that and enforce it:

auto emplace_result = iters_by_txid.emplace((*block_it)->GetHash(), it);
assert(emplace_result.second);

or remove the restriction:

// Ignore duplicates
iters_by_txid.try_emplace((*block_it)->GetHash(), it);

Agreed, I like the first option. Maybe @ismaelsadeeq might be interested in adding it to the followup?

Added to #28530