addition-removal-mempool.adoc

links-onepage.adoc == Addition to the mempool

Transactions are added to the mempool via addUnchecked() as part of the AcceptToMemoryPool() flow. See Transaction validation for more information on how this flow is entered.

Warning

The function name addUnchecked specifically refers to the fact that no checks are being performed, so this must not be called until policy checks have passed.

This function is called from within validation.cpp (MemPoolAccept::Finalize()) where the appropriate consensus and policy checks have already been performed on the transaction. The transaction is added to the primary index mapTx before any fee prioritisation ("delta") is applied to it.

Next any links to parent transactions are generated by looping through the inputs and mapping the COutPoint of the input to this transaction CTransaction in the mapNextTx map. Additionally the tx input is added to a set which is used to update parent transactions if they are still in the mempool.

After all inputs have been considered, UpdateAncestorsOf() is called which will add this transaction as a descendant to any ancestors in the mempool. This is followed by UpdateEntryForAncestors() which will re-calculate and apply descendant count, size, fee and sigOpCost of the ancestors with the new descendant being accounted for.

Finally update totalTxSize and totalFee (both sum totals of the mempool) to account for this new transaction.

Removal from the mempool

Transactions are removed from the mempool for a number of reasons:

1. A new block has been connected removeForBlock()

2. A re-org is taking place removeForReorg()

3. The transaction has expired Expire()

4. The transaction is being replaced by a higher-fee version MemPoolAccept::Finalize()

5. The mempool must be trimmed back down below its maximum size TrimToSize()

Removal from the mempool

flowchart LR
    remove_staged["RemoveStaged()"]
    remove_recursive["removeRecursive()"]
    remove_reorg["removeForReorg()"]
    remove_block["removeForBlock()"]
    expire["Expire()"]
    trim_to_size["TrimToSize()"]
    finalize["MemPoolAccept::Finalize()"]
    calculate_ancestors["CalculateMemPoolAncestors()"]
    update_ancestors["UpdateAncestorsOf()"]
    update_children["UpdateChildrenForRemoval()"]
    remove_unchecked["removeUnchecked()"]

    remove_recursive --> remove_staged
    remove_reorg --> remove_staged
    remove_block --> remove_staged
    expire --> remove_staged
    trim_to_size --> remove_staged
    finalize ---> remove_staged

    remove_staged --> update_for_remove

    update_for_remove --> remove_unchecked

    subgraph validation.cpp
        finalize
    end

    subgraph txmempool.cpp
        remove_recursive
        remove_reorg
        remove_block
        expire
        trim_to_size
    end

    subgraph update_for_remove["UpdateForRemoveFromMempool()"]
        calculate_ancestors --> update_ancestors --> update_children
    end

RemoveStaged() takes a set of transactions referenced by their txid along with their removal reason, and removes them sequentially. It does this by first updating the ancestors of the transaction, followed by the descendants. After calculating and updating related transaction information it calls removeUnchecked() which actions the removal from the mempool.

removeUnchecked() starts by notifying the validation interface that a transaction has been removed from the mempool for all reasons other than a new block arriving, as there is a different BlockConnected signal which can be used for that.

Next it loops over the txins of the transaction, and removes each prevout of each txin from the mapNextTx map.

Tip

mapNextTx is used to map a COutPoint to the unconfirmed transaction spending it. This way there is a quick lookup available to check that a new transaction being added to the mempool is not trying to double spend a UTXO. You can see the map being created as new transactions are learned about in addUnchecked().

If the node has upgraded to SegWit the vTxHashes vector, which stores wtxids is then updated. As vTxHashes stores the wtxids in random order, first we move the transaction’s entry to the back, and then pop it off, resizing the vector if needed.

Finally, as with addUnchecked() we update the mempool sum totals for txSize and fee and erase the transaction from the primary mempool index mapTx.

Tip	Both adding and removing transactions increment the mempool_seqence counter. This is used by the getrawmempool RPC (via MempoolToJSON) in tracking the number of mempool database transaction operations.