No OneTemporary
Actions

Size

70 KB

Subscribers

None

View Options

	diff --git a/src/txmempool.cpp b/src/txmempool.cpp
	index 48fbe56023..ae851621c1 100644
	--- a/src/txmempool.cpp
	+++ b/src/txmempool.cpp
	@@ -1,1018 +1,1035 @@
	// Copyright (c) 2009-2010 Satoshi Nakamoto
	// Copyright (c) 2009-2015 The Bitcoin Core developers
	// Distributed under the MIT software license, see the accompanying
	// file COPYING or http://www.opensource.org/licenses/mit-license.php.

	#include "txmempool.h"

	#include "clientversion.h"
	#include "consensus/consensus.h"
	#include "consensus/validation.h"
	#include "main.h"
	#include "policy/fees.h"
	#include "streams.h"
	#include "timedata.h"
	#include "util.h"
	#include "utilmoneystr.h"
	#include "utiltime.h"
	#include "version.h"

	using namespace std;

	CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
	int64_t _nTime, double _entryPriority, unsigned int _entryHeight,
	bool poolHasNoInputsOf, CAmount _inChainInputValue,
	bool _spendsCoinbase, unsigned int _sigOps):
	tx(_tx), nFee(_nFee), nTime(_nTime), entryPriority(_entryPriority), entryHeight(_entryHeight),
	hadNoDependencies(poolHasNoInputsOf), inChainInputValue(_inChainInputValue),
	spendsCoinbase(_spendsCoinbase), sigOpCount(_sigOps)
	{
	nTxSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION);
	nModSize = tx.CalculateModifiedSize(nTxSize);
	nUsageSize = RecursiveDynamicUsage(tx);

	nCountWithDescendants = 1;
	nSizeWithDescendants = nTxSize;
	nModFeesWithDescendants = nFee;
	CAmount nValueIn = tx.GetValueOut()+nFee;
	assert(inChainInputValue <= nValueIn);

	feeDelta = 0;

	nCountWithAncestors = 1;
	nSizeWithAncestors = nTxSize;
	nModFeesWithAncestors = nFee;
	nSigOpCountWithAncestors = sigOpCount;
	}

	CTxMemPoolEntry::CTxMemPoolEntry(const CTxMemPoolEntry& other)
	{
	*this = other;
	}

	double
	CTxMemPoolEntry::GetPriority(unsigned int currentHeight) const
	{
	double deltaPriority = ((double)(currentHeight-entryHeight)*inChainInputValue)/nModSize;
	double dResult = entryPriority + deltaPriority;
	if (dResult < 0) // This should only happen if it was called with a height below entry height
	dResult = 0;
	return dResult;
	}

	void CTxMemPoolEntry::UpdateFeeDelta(int64_t newFeeDelta)
	{
	nModFeesWithDescendants += newFeeDelta - feeDelta;
	nModFeesWithAncestors += newFeeDelta - feeDelta;
	feeDelta = newFeeDelta;
	}

	// Update the given tx for any in-mempool descendants.
	// Assumes that setMemPoolChildren is correct for the given tx and all
	// descendants.
	void CTxMemPool::UpdateForDescendants(txiter updateIt, cacheMap &cachedDescendants, const std::set<uint256> &setExclude)
	{
	setEntries stageEntries, setAllDescendants;
	stageEntries = GetMemPoolChildren(updateIt);

	while (!stageEntries.empty()) {
	const txiter cit = *stageEntries.begin();
	setAllDescendants.insert(cit);
	stageEntries.erase(cit);
	const setEntries &setChildren = GetMemPoolChildren(cit);
	BOOST_FOREACH(const txiter childEntry, setChildren) {
	cacheMap::iterator cacheIt = cachedDescendants.find(childEntry);
	if (cacheIt != cachedDescendants.end()) {
	// We've already calculated this one, just add the entries for this set
	// but don't traverse again.
	BOOST_FOREACH(const txiter cacheEntry, cacheIt->second) {
	setAllDescendants.insert(cacheEntry);
	}
	} else if (!setAllDescendants.count(childEntry)) {
	// Schedule for later processing
	stageEntries.insert(childEntry);
	}
	}
	}
	// setAllDescendants now contains all in-mempool descendants of updateIt.
	// Update and add to cached descendant map
	int64_t modifySize = 0;
	CAmount modifyFee = 0;
	int64_t modifyCount = 0;
	BOOST_FOREACH(txiter cit, setAllDescendants) {
	if (!setExclude.count(cit->GetTx().GetHash())) {
	modifySize += cit->GetTxSize();
	modifyFee += cit->GetModifiedFee();
	modifyCount++;
	cachedDescendants[updateIt].insert(cit);
	// Update ancestor state for each descendant
	mapTx.modify(cit, update_ancestor_state(updateIt->GetTxSize(), updateIt->GetModifiedFee(), 1, updateIt->GetSigOpCount()));
	}
	}
	mapTx.modify(updateIt, update_descendant_state(modifySize, modifyFee, modifyCount));
	}

	// vHashesToUpdate is the set of transaction hashes from a disconnected block
	// which has been re-added to the mempool.
	// for each entry, look for descendants that are outside hashesToUpdate, and
	// add fee/size information for such descendants to the parent.
	// for each such descendant, also update the ancestor state to include the parent.
	void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256> &vHashesToUpdate)
	{
	LOCK(cs);
	// For each entry in vHashesToUpdate, store the set of in-mempool, but not
	// in-vHashesToUpdate transactions, so that we don't have to recalculate
	// descendants when we come across a previously seen entry.
	cacheMap mapMemPoolDescendantsToUpdate;

	// Use a set for lookups into vHashesToUpdate (these entries are already
	// accounted for in the state of their ancestors)
	std::set<uint256> setAlreadyIncluded(vHashesToUpdate.begin(), vHashesToUpdate.end());

	// Iterate in reverse, so that whenever we are looking at at a transaction
	// we are sure that all in-mempool descendants have already been processed.
	// This maximizes the benefit of the descendant cache and guarantees that
	// setMemPoolChildren will be updated, an assumption made in
	// UpdateForDescendants.
	BOOST_REVERSE_FOREACH(const uint256 &hash, vHashesToUpdate) {
	// we cache the in-mempool children to avoid duplicate updates
	setEntries setChildren;
	// calculate children from mapNextTx
	txiter it = mapTx.find(hash);
	if (it == mapTx.end()) {
	continue;
	}
	std::map<COutPoint, CInPoint>::iterator iter = mapNextTx.lower_bound(COutPoint(hash, 0));
	// First calculate the children, and update setMemPoolChildren to
	// include them, and update their setMemPoolParents to include this tx.
	for (; iter != mapNextTx.end() && iter->first.hash == hash; ++iter) {
	const uint256 &childHash = iter->second.ptx->GetHash();
	txiter childIter = mapTx.find(childHash);
	assert(childIter != mapTx.end());
	// We can skip updating entries we've encountered before or that
	// are in the block (which are already accounted for).
	if (setChildren.insert(childIter).second && !setAlreadyIncluded.count(childHash)) {
	UpdateChild(it, childIter, true);
	UpdateParent(childIter, it, true);
	}
	}
	UpdateForDescendants(it, mapMemPoolDescendantsToUpdate, setAlreadyIncluded);
	}
	}

	-bool CTxMemPool::CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString, bool fSearchForParents /* = true */)
	+bool CTxMemPool::CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString, bool fSearchForParents /* = true */) const
	{
	setEntries parentHashes;
	const CTransaction &tx = entry.GetTx();

	if (fSearchForParents) {
	// Get parents of this transaction that are in the mempool
	// GetMemPoolParents() is only valid for entries in the mempool, so we
	// iterate mapTx to find parents.
	for (unsigned int i = 0; i < tx.vin.size(); i++) {
	txiter piter = mapTx.find(tx.vin[i].prevout.hash);
	if (piter != mapTx.end()) {
	parentHashes.insert(piter);
	if (parentHashes.size() + 1 > limitAncestorCount) {
	errString = strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount);
	return false;
	}
	}
	}
	} else {
	// If we're not searching for parents, we require this to be an
	// entry in the mempool already.
	txiter it = mapTx.iterator_to(entry);
	parentHashes = GetMemPoolParents(it);
	}

	size_t totalSizeWithAncestors = entry.GetTxSize();

	while (!parentHashes.empty()) {
	txiter stageit = *parentHashes.begin();

	setAncestors.insert(stageit);
	parentHashes.erase(stageit);
	totalSizeWithAncestors += stageit->GetTxSize();

	if (stageit->GetSizeWithDescendants() + entry.GetTxSize() > limitDescendantSize) {
	errString = strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantSize);
	return false;
	} else if (stageit->GetCountWithDescendants() + 1 > limitDescendantCount) {
	errString = strprintf("too many descendants for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantCount);
	return false;
	} else if (totalSizeWithAncestors > limitAncestorSize) {
	errString = strprintf("exceeds ancestor size limit [limit: %u]", limitAncestorSize);
	return false;
	}

	const setEntries & setMemPoolParents = GetMemPoolParents(stageit);
	BOOST_FOREACH(const txiter &phash, setMemPoolParents) {
	// If this is a new ancestor, add it.
	if (setAncestors.count(phash) == 0) {
	parentHashes.insert(phash);
	}
	if (parentHashes.size() + setAncestors.size() + 1 > limitAncestorCount) {
	errString = strprintf("too many unconfirmed ancestors [limit: %u]", limitAncestorCount);
	return false;
	}
	}
	}

	return true;
	}

	void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors)
	{
	setEntries parentIters = GetMemPoolParents(it);
	// add or remove this tx as a child of each parent
	BOOST_FOREACH(txiter piter, parentIters) {
	UpdateChild(piter, it, add);
	}
	const int64_t updateCount = (add ? 1 : -1);
	const int64_t updateSize = updateCount * it->GetTxSize();
	const CAmount updateFee = updateCount * it->GetModifiedFee();
	BOOST_FOREACH(txiter ancestorIt, setAncestors) {
	mapTx.modify(ancestorIt, update_descendant_state(updateSize, updateFee, updateCount));
	}
	}

	void CTxMemPool::UpdateEntryForAncestors(txiter it, const setEntries &setAncestors)
	{
	int64_t updateCount = setAncestors.size();
	int64_t updateSize = 0;
	CAmount updateFee = 0;
	int updateSigOps = 0;
	BOOST_FOREACH(txiter ancestorIt, setAncestors) {
	updateSize += ancestorIt->GetTxSize();
	updateFee += ancestorIt->GetModifiedFee();
	updateSigOps += ancestorIt->GetSigOpCount();
	}
	mapTx.modify(it, update_ancestor_state(updateSize, updateFee, updateCount, updateSigOps));
	}

	void CTxMemPool::UpdateChildrenForRemoval(txiter it)
	{
	const setEntries &setMemPoolChildren = GetMemPoolChildren(it);
	BOOST_FOREACH(txiter updateIt, setMemPoolChildren) {
	UpdateParent(updateIt, it, false);
	}
	}

	void CTxMemPool::UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants)
	{
	// For each entry, walk back all ancestors and decrement size associated with this
	// transaction
	const uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
	if (updateDescendants) {
	// updateDescendants should be true whenever we're not recursively
	// removing a tx and all its descendants, eg when a transaction is
	// confirmed in a block.
	// Here we only update statistics and not data in mapLinks (which
	// we need to preserve until we're finished with all operations that
	// need to traverse the mempool).
	BOOST_FOREACH(txiter removeIt, entriesToRemove) {
	setEntries setDescendants;
	CalculateDescendants(removeIt, setDescendants);
	setDescendants.erase(removeIt); // don't update state for self
	int64_t modifySize = -((int64_t)removeIt->GetTxSize());
	CAmount modifyFee = -removeIt->GetModifiedFee();
	int modifySigOps = -removeIt->GetSigOpCount();
	BOOST_FOREACH(txiter dit, setDescendants) {
	mapTx.modify(dit, update_ancestor_state(modifySize, modifyFee, -1, modifySigOps));
	}
	}
	}
	BOOST_FOREACH(txiter removeIt, entriesToRemove) {
	setEntries setAncestors;
	const CTxMemPoolEntry &entry = *removeIt;
	std::string dummy;
	// Since this is a tx that is already in the mempool, we can call CMPA
	// with fSearchForParents = false. If the mempool is in a consistent
	// state, then using true or false should both be correct, though false
	// should be a bit faster.
	// However, if we happen to be in the middle of processing a reorg, then
	// the mempool can be in an inconsistent state. In this case, the set
	// of ancestors reachable via mapLinks will be the same as the set of
	// ancestors whose packages include this transaction, because when we
	// add a new transaction to the mempool in addUnchecked(), we assume it
	// has no children, and in the case of a reorg where that assumption is
	// false, the in-mempool children aren't linked to the in-block tx's
	// until UpdateTransactionsFromBlock() is called.
	// So if we're being called during a reorg, ie before
	// UpdateTransactionsFromBlock() has been called, then mapLinks[] will
	// differ from the set of mempool parents we'd calculate by searching,
	// and it's important that we use the mapLinks[] notion of ancestor
	// transactions as the set of things to update for removal.
	CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false);
	// Note that UpdateAncestorsOf severs the child links that point to
	// removeIt in the entries for the parents of removeIt.
	UpdateAncestorsOf(false, removeIt, setAncestors);
	}
	// After updating all the ancestor sizes, we can now sever the link between each
	// transaction being removed and any mempool children (ie, update setMemPoolParents
	// for each direct child of a transaction being removed).
	BOOST_FOREACH(txiter removeIt, entriesToRemove) {
	UpdateChildrenForRemoval(removeIt);
	}
	}

	void CTxMemPoolEntry::UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount)
	{
	nSizeWithDescendants += modifySize;
	assert(int64_t(nSizeWithDescendants) > 0);
	nModFeesWithDescendants += modifyFee;
	nCountWithDescendants += modifyCount;
	assert(int64_t(nCountWithDescendants) > 0);
	}

	void CTxMemPoolEntry::UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int modifySigOps)
	{
	nSizeWithAncestors += modifySize;
	assert(int64_t(nSizeWithAncestors) > 0);
	nModFeesWithAncestors += modifyFee;
	nCountWithAncestors += modifyCount;
	assert(int64_t(nCountWithAncestors) > 0);
	nSigOpCountWithAncestors += modifySigOps;
	assert(int(nSigOpCountWithAncestors) >= 0);
	}

	CTxMemPool::CTxMemPool(const CFeeRate& _minReasonableRelayFee) :
	nTransactionsUpdated(0)
	{
	_clear(); //lock free clear

	// Sanity checks off by default for performance, because otherwise
	// accepting transactions becomes O(N^2) where N is the number
	// of transactions in the pool
	nCheckFrequency = 0;

	minerPolicyEstimator = new CBlockPolicyEstimator(_minReasonableRelayFee);
	minReasonableRelayFee = _minReasonableRelayFee;
	}

	CTxMemPool::~CTxMemPool()
	{
	delete minerPolicyEstimator;
	}

	void CTxMemPool::pruneSpent(const uint256 &hashTx, CCoins &coins)
	{
	LOCK(cs);

	std::map<COutPoint, CInPoint>::iterator it = mapNextTx.lower_bound(COutPoint(hashTx, 0));

	// iterate over all COutPoints in mapNextTx whose hash equals the provided hashTx
	while (it != mapNextTx.end() && it->first.hash == hashTx) {
	coins.Spend(it->first.n); // and remove those outputs from coins
	it++;
	}
	}

	unsigned int CTxMemPool::GetTransactionsUpdated() const
	{
	LOCK(cs);
	return nTransactionsUpdated;
	}

	void CTxMemPool::AddTransactionsUpdated(unsigned int n)
	{
	LOCK(cs);
	nTransactionsUpdated += n;
	}

	bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, setEntries &setAncestors, bool fCurrentEstimate)
	{
	// Add to memory pool without checking anything.
	// Used by main.cpp AcceptToMemoryPool(), which DOES do
	// all the appropriate checks.
	LOCK(cs);
	indexed_transaction_set::iterator newit = mapTx.insert(entry).first;
	mapLinks.insert(make_pair(newit, TxLinks()));

	// Update transaction for any feeDelta created by PrioritiseTransaction
	// TODO: refactor so that the fee delta is calculated before inserting
	// into mapTx.
	std::map<uint256, std::pair<double, CAmount> >::const_iterator pos = mapDeltas.find(hash);
	if (pos != mapDeltas.end()) {
	const std::pair<double, CAmount> &deltas = pos->second;
	if (deltas.second) {
	mapTx.modify(newit, update_fee_delta(deltas.second));
	}
	}

	// Update cachedInnerUsage to include contained transaction's usage.
	// (When we update the entry for in-mempool parents, memory usage will be
	// further updated.)
	cachedInnerUsage += entry.DynamicMemoryUsage();

	const CTransaction& tx = newit->GetTx();
	std::set<uint256> setParentTransactions;
	for (unsigned int i = 0; i < tx.vin.size(); i++) {
	mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i);
	setParentTransactions.insert(tx.vin[i].prevout.hash);
	}
	// Don't bother worrying about child transactions of this one.
	// Normal case of a new transaction arriving is that there can't be any
	// children, because such children would be orphans.
	// An exception to that is if a transaction enters that used to be in a block.
	// In that case, our disconnect block logic will call UpdateTransactionsFromBlock
	// to clean up the mess we're leaving here.

	// Update ancestors with information about this tx
	BOOST_FOREACH (const uint256 &phash, setParentTransactions) {
	txiter pit = mapTx.find(phash);
	if (pit != mapTx.end()) {
	UpdateParent(newit, pit, true);
	}
	}
	UpdateAncestorsOf(true, newit, setAncestors);
	UpdateEntryForAncestors(newit, setAncestors);

	nTransactionsUpdated++;
	totalTxSize += entry.GetTxSize();
	minerPolicyEstimator->processTransaction(entry, fCurrentEstimate);

	return true;
	}

	void CTxMemPool::removeUnchecked(txiter it)
	{
	const uint256 hash = it->GetTx().GetHash();
	BOOST_FOREACH(const CTxIn& txin, it->GetTx().vin)
	mapNextTx.erase(txin.prevout);

	totalTxSize -= it->GetTxSize();
	cachedInnerUsage -= it->DynamicMemoryUsage();
	cachedInnerUsage -= memusage::DynamicUsage(mapLinks[it].parents) + memusage::DynamicUsage(mapLinks[it].children);
	mapLinks.erase(it);
	mapTx.erase(it);
	nTransactionsUpdated++;
	minerPolicyEstimator->removeTx(hash);
	}

	// Calculates descendants of entry that are not already in setDescendants, and adds to
	// setDescendants. Assumes entryit is already a tx in the mempool and setMemPoolChildren
	// is correct for tx and all descendants.
	// Also assumes that if an entry is in setDescendants already, then all
	// in-mempool descendants of it are already in setDescendants as well, so that we
	// can save time by not iterating over those entries.
	void CTxMemPool::CalculateDescendants(txiter entryit, setEntries &setDescendants)
	{
	setEntries stage;
	if (setDescendants.count(entryit) == 0) {
	stage.insert(entryit);
	}
	// Traverse down the children of entry, only adding children that are not
	// accounted for in setDescendants already (because those children have either
	// already been walked, or will be walked in this iteration).
	while (!stage.empty()) {
	txiter it = *stage.begin();
	setDescendants.insert(it);
	stage.erase(it);

	const setEntries &setChildren = GetMemPoolChildren(it);
	BOOST_FOREACH(const txiter &childiter, setChildren) {
	if (!setDescendants.count(childiter)) {
	stage.insert(childiter);
	}
	}
	}
	}

	void CTxMemPool::removeRecursive(const CTransaction &origTx, std::list<CTransaction>& removed)
	{
	// Remove transaction from memory pool
	{
	LOCK(cs);
	setEntries txToRemove;
	txiter origit = mapTx.find(origTx.GetHash());
	if (origit != mapTx.end()) {
	txToRemove.insert(origit);
	} else {
	// When recursively removing but origTx isn't in the mempool
	// be sure to remove any children that are in the pool. This can
	// happen during chain re-orgs if origTx isn't re-accepted into
	// the mempool for any reason.
	for (unsigned int i = 0; i < origTx.vout.size(); i++) {
	std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
	if (it == mapNextTx.end())
	continue;
	txiter nextit = mapTx.find(it->second.ptx->GetHash());
	assert(nextit != mapTx.end());
	txToRemove.insert(nextit);
	}
	}
	setEntries setAllRemoves;
	BOOST_FOREACH(txiter it, txToRemove) {
	CalculateDescendants(it, setAllRemoves);
	}
	BOOST_FOREACH(txiter it, setAllRemoves) {
	removed.push_back(it->GetTx());
	}
	RemoveStaged(setAllRemoves, false);
	}
	}

	void CTxMemPool::removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags)
	{
	// Remove transactions spending a coinbase which are now immature and no-longer-final transactions
	LOCK(cs);
	list<CTransaction> transactionsToRemove;
	for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
	const CTransaction& tx = it->GetTx();
	if (!CheckFinalTx(tx, flags) \|\| !CheckSequenceLocks(tx, flags)) {
	transactionsToRemove.push_back(tx);
	} else if (it->GetSpendsCoinbase()) {
	BOOST_FOREACH(const CTxIn& txin, tx.vin) {
	indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
	if (it2 != mapTx.end())
	continue;
	const CCoins *coins = pcoins->AccessCoins(txin.prevout.hash);
	if (nCheckFrequency != 0) assert(coins);
	if (!coins \|\| (coins->IsCoinBase() && ((signed long)nMemPoolHeight) - coins->nHeight < COINBASE_MATURITY)) {
	transactionsToRemove.push_back(tx);
	break;
	}
	}
	}
	}
	BOOST_FOREACH(const CTransaction& tx, transactionsToRemove) {
	list<CTransaction> removed;
	removeRecursive(tx, removed);
	}
	}

	void CTxMemPool::removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed)
	{
	// Remove transactions which depend on inputs of tx, recursively
	list<CTransaction> result;
	LOCK(cs);
	BOOST_FOREACH(const CTxIn &txin, tx.vin) {
	std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(txin.prevout);
	if (it != mapNextTx.end()) {
	const CTransaction &txConflict = *it->second.ptx;
	if (txConflict != tx)
	{
	removeRecursive(txConflict, removed);
	ClearPrioritisation(txConflict.GetHash());
	}
	}
	}
	}

	/**
	* Called when a block is connected. Removes from mempool and updates the miner fee estimator.
	*/
	void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight,
	std::list<CTransaction>& conflicts, bool fCurrentEstimate)
	{
	LOCK(cs);
	std::vector<CTxMemPoolEntry> entries;
	BOOST_FOREACH(const CTransaction& tx, vtx)
	{
	uint256 hash = tx.GetHash();

	indexed_transaction_set::iterator i = mapTx.find(hash);
	if (i != mapTx.end())
	entries.push_back(*i);
	}
	BOOST_FOREACH(const CTransaction& tx, vtx)
	{
	txiter it = mapTx.find(tx.GetHash());
	if (it != mapTx.end()) {
	setEntries stage;
	stage.insert(it);
	RemoveStaged(stage, true);
	}
	removeConflicts(tx, conflicts);
	ClearPrioritisation(tx.GetHash());
	}
	// After the txs in the new block have been removed from the mempool, update policy estimates
	minerPolicyEstimator->processBlock(nBlockHeight, entries, fCurrentEstimate);
	lastRollingFeeUpdate = GetTime();
	blockSinceLastRollingFeeBump = true;
	}

	void CTxMemPool::_clear()
	{
	mapLinks.clear();
	mapTx.clear();
	mapNextTx.clear();
	totalTxSize = 0;
	cachedInnerUsage = 0;
	lastRollingFeeUpdate = GetTime();
	blockSinceLastRollingFeeBump = false;
	rollingMinimumFeeRate = 0;
	++nTransactionsUpdated;
	}

	void CTxMemPool::clear()
	{
	LOCK(cs);
	_clear();
	}

	void CTxMemPool::check(const CCoinsViewCache *pcoins) const
	{
	if (nCheckFrequency == 0)
	return;

	if (insecure_rand() >= nCheckFrequency)
	return;

	LogPrint("mempool", "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());

	uint64_t checkTotal = 0;
	uint64_t innerUsage = 0;

	CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(pcoins));

	LOCK(cs);
	list<const CTxMemPoolEntry*> waitingOnDependants;
	for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
	unsigned int i = 0;
	checkTotal += it->GetTxSize();
	innerUsage += it->DynamicMemoryUsage();
	const CTransaction& tx = it->GetTx();
	txlinksMap::const_iterator linksiter = mapLinks.find(it);
	assert(linksiter != mapLinks.end());
	const TxLinks &links = linksiter->second;
	innerUsage += memusage::DynamicUsage(links.parents) + memusage::DynamicUsage(links.children);
	bool fDependsWait = false;
	setEntries setParentCheck;
	int64_t parentSizes = 0;
	unsigned int parentSigOpCount = 0;
	BOOST_FOREACH(const CTxIn &txin, tx.vin) {
	// Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
	indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
	if (it2 != mapTx.end()) {
	const CTransaction& tx2 = it2->GetTx();
	assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
	fDependsWait = true;
	if (setParentCheck.insert(it2).second) {
	parentSizes += it2->GetTxSize();
	parentSigOpCount += it2->GetSigOpCount();
	}
	} else {
	const CCoins* coins = pcoins->AccessCoins(txin.prevout.hash);
	assert(coins && coins->IsAvailable(txin.prevout.n));
	}
	// Check whether its inputs are marked in mapNextTx.
	std::map<COutPoint, CInPoint>::const_iterator it3 = mapNextTx.find(txin.prevout);
	assert(it3 != mapNextTx.end());
	assert(it3->second.ptx == &tx);
	assert(it3->second.n == i);
	i++;
	}
	assert(setParentCheck == GetMemPoolParents(it));
	- // Also check to make sure ancestor size/sigops are >= sum with immediate
	- // parents.
	- assert(it->GetSizeWithAncestors() >= parentSizes + it->GetTxSize());
	- assert(it->GetSigOpCountWithAncestors() >= parentSigOpCount + it->GetSigOpCount());
	+ // Verify ancestor state is correct.
	+ setEntries setAncestors;
	+ uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
	+ std::string dummy;
	+ CalculateMemPoolAncestors(*it, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy);
	+ uint64_t nCountCheck = setAncestors.size() + 1;
	+ uint64_t nSizeCheck = it->GetTxSize();
	+ CAmount nFeesCheck = it->GetModifiedFee();
	+ unsigned int nSigOpCheck = it->GetSigOpCount();
	+
	+ BOOST_FOREACH(txiter ancestorIt, setAncestors) {
	+ nSizeCheck += ancestorIt->GetTxSize();
	+ nFeesCheck += ancestorIt->GetModifiedFee();
	+ nSigOpCheck += ancestorIt->GetSigOpCount();
	+ }
	+
	+ assert(it->GetCountWithAncestors() == nCountCheck);
	+ assert(it->GetSizeWithAncestors() == nSizeCheck);
	+ assert(it->GetSigOpCountWithAncestors() == nSigOpCheck);
	+ assert(it->GetModFeesWithAncestors() == nFeesCheck);
	+
	// Check children against mapNextTx
	CTxMemPool::setEntries setChildrenCheck;
	std::map<COutPoint, CInPoint>::const_iterator iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
	int64_t childSizes = 0;
	for (; iter != mapNextTx.end() && iter->first.hash == it->GetTx().GetHash(); ++iter) {
	txiter childit = mapTx.find(iter->second.ptx->GetHash());
	assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
	if (setChildrenCheck.insert(childit).second) {
	childSizes += childit->GetTxSize();
	}
	}
	assert(setChildrenCheck == GetMemPoolChildren(it));
	// Also check to make sure size is greater than sum with immediate children.
	// just a sanity check, not definitive that this calc is correct...
	assert(it->GetSizeWithDescendants() >= childSizes + it->GetTxSize());

	if (fDependsWait)
	waitingOnDependants.push_back(&(*it));
	else {
	CValidationState state;
	assert(CheckInputs(tx, state, mempoolDuplicate, false, 0, false, NULL));
	UpdateCoins(tx, state, mempoolDuplicate, 1000000);
	}
	}
	unsigned int stepsSinceLastRemove = 0;
	while (!waitingOnDependants.empty()) {
	const CTxMemPoolEntry* entry = waitingOnDependants.front();
	waitingOnDependants.pop_front();
	CValidationState state;
	if (!mempoolDuplicate.HaveInputs(entry->GetTx())) {
	waitingOnDependants.push_back(entry);
	stepsSinceLastRemove++;
	assert(stepsSinceLastRemove < waitingOnDependants.size());
	} else {
	assert(CheckInputs(entry->GetTx(), state, mempoolDuplicate, false, 0, false, NULL));
	UpdateCoins(entry->GetTx(), state, mempoolDuplicate, 1000000);
	stepsSinceLastRemove = 0;
	}
	}
	for (std::map<COutPoint, CInPoint>::const_iterator it = mapNextTx.begin(); it != mapNextTx.end(); it++) {
	uint256 hash = it->second.ptx->GetHash();
	indexed_transaction_set::const_iterator it2 = mapTx.find(hash);
	const CTransaction& tx = it2->GetTx();
	assert(it2 != mapTx.end());
	assert(&tx == it->second.ptx);
	assert(tx.vin.size() > it->second.n);
	assert(it->first == it->second.ptx->vin[it->second.n].prevout);
	}

	assert(totalTxSize == checkTotal);
	assert(innerUsage == cachedInnerUsage);
	}

	void CTxMemPool::queryHashes(vector<uint256>& vtxid)
	{
	vtxid.clear();

	LOCK(cs);
	vtxid.reserve(mapTx.size());
	for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi)
	vtxid.push_back(mi->GetTx().GetHash());
	}

	bool CTxMemPool::lookup(uint256 hash, CTransaction& result) const
	{
	LOCK(cs);
	indexed_transaction_set::const_iterator i = mapTx.find(hash);
	if (i == mapTx.end()) return false;
	result = i->GetTx();
	return true;
	}

	CFeeRate CTxMemPool::estimateFee(int nBlocks) const
	{
	LOCK(cs);
	return minerPolicyEstimator->estimateFee(nBlocks);
	}
	CFeeRate CTxMemPool::estimateSmartFee(int nBlocks, int *answerFoundAtBlocks) const
	{
	LOCK(cs);
	return minerPolicyEstimator->estimateSmartFee(nBlocks, answerFoundAtBlocks, *this);
	}
	double CTxMemPool::estimatePriority(int nBlocks) const
	{
	LOCK(cs);
	return minerPolicyEstimator->estimatePriority(nBlocks);
	}
	double CTxMemPool::estimateSmartPriority(int nBlocks, int *answerFoundAtBlocks) const
	{
	LOCK(cs);
	return minerPolicyEstimator->estimateSmartPriority(nBlocks, answerFoundAtBlocks, *this);
	}

	bool
	CTxMemPool::WriteFeeEstimates(CAutoFile& fileout) const
	{
	try {
	LOCK(cs);
	fileout << 109900; // version required to read: 0.10.99 or later
	fileout << CLIENT_VERSION; // version that wrote the file
	minerPolicyEstimator->Write(fileout);
	}
	catch (const std::exception&) {
	LogPrintf("CTxMemPool::WriteFeeEstimates(): unable to write policy estimator data (non-fatal)\n");
	return false;
	}
	return true;
	}

	bool
	CTxMemPool::ReadFeeEstimates(CAutoFile& filein)
	{
	try {
	int nVersionRequired, nVersionThatWrote;
	filein >> nVersionRequired >> nVersionThatWrote;
	if (nVersionRequired > CLIENT_VERSION)
	return error("CTxMemPool::ReadFeeEstimates(): up-version (%d) fee estimate file", nVersionRequired);

	LOCK(cs);
	minerPolicyEstimator->Read(filein);
	}
	catch (const std::exception&) {
	LogPrintf("CTxMemPool::ReadFeeEstimates(): unable to read policy estimator data (non-fatal)\n");
	return false;
	}
	return true;
	}

	void CTxMemPool::PrioritiseTransaction(const uint256 hash, const string strHash, double dPriorityDelta, const CAmount& nFeeDelta)
	{
	{
	LOCK(cs);
	std::pair<double, CAmount> &deltas = mapDeltas[hash];
	deltas.first += dPriorityDelta;
	deltas.second += nFeeDelta;
	txiter it = mapTx.find(hash);
	if (it != mapTx.end()) {
	mapTx.modify(it, update_fee_delta(deltas.second));
	// Now update all ancestors' modified fees with descendants
	setEntries setAncestors;
	uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
	std::string dummy;
	CalculateMemPoolAncestors(*it, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false);
	BOOST_FOREACH(txiter ancestorIt, setAncestors) {
	mapTx.modify(ancestorIt, update_descendant_state(0, nFeeDelta, 0));
	}
	}
	}
	LogPrintf("PrioritiseTransaction: %s priority += %f, fee += %d\n", strHash, dPriorityDelta, FormatMoney(nFeeDelta));
	}

	void CTxMemPool::ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta) const
	{
	LOCK(cs);
	std::map<uint256, std::pair<double, CAmount> >::const_iterator pos = mapDeltas.find(hash);
	if (pos == mapDeltas.end())
	return;
	const std::pair<double, CAmount> &deltas = pos->second;
	dPriorityDelta += deltas.first;
	nFeeDelta += deltas.second;
	}

	void CTxMemPool::ClearPrioritisation(const uint256 hash)
	{
	LOCK(cs);
	mapDeltas.erase(hash);
	}

	bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const
	{
	for (unsigned int i = 0; i < tx.vin.size(); i++)
	if (exists(tx.vin[i].prevout.hash))
	return false;
	return true;
	}

	CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView *baseIn, CTxMemPool &mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }

	bool CCoinsViewMemPool::GetCoins(const uint256 &txid, CCoins &coins) const {
	// If an entry in the mempool exists, always return that one, as it's guaranteed to never
	// conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
	// transactions. First checking the underlying cache risks returning a pruned entry instead.
	CTransaction tx;
	if (mempool.lookup(txid, tx)) {
	coins = CCoins(tx, MEMPOOL_HEIGHT);
	return true;
	}
	return (base->GetCoins(txid, coins) && !coins.IsPruned());
	}

	bool CCoinsViewMemPool::HaveCoins(const uint256 &txid) const {
	return mempool.exists(txid) \|\| base->HaveCoins(txid);
	}

	size_t CTxMemPool::DynamicMemoryUsage() const {
	LOCK(cs);
	// Estimate the overhead of mapTx to be 15 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
	return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 15 * sizeof(void)) mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + cachedInnerUsage;
	}

	void CTxMemPool::RemoveStaged(setEntries &stage, bool updateDescendants) {
	AssertLockHeld(cs);
	UpdateForRemoveFromMempool(stage, updateDescendants);
	BOOST_FOREACH(const txiter& it, stage) {
	removeUnchecked(it);
	}
	}

	int CTxMemPool::Expire(int64_t time) {
	LOCK(cs);
	indexed_transaction_set::index<entry_time>::type::iterator it = mapTx.get<entry_time>().begin();
	setEntries toremove;
	while (it != mapTx.get<entry_time>().end() && it->GetTime() < time) {
	toremove.insert(mapTx.project<0>(it));
	it++;
	}
	setEntries stage;
	BOOST_FOREACH(txiter removeit, toremove) {
	CalculateDescendants(removeit, stage);
	}
	RemoveStaged(stage, false);
	return stage.size();
	}

	bool CTxMemPool::addUnchecked(const uint256&hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate)
	{
	LOCK(cs);
	setEntries setAncestors;
	uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
	std::string dummy;
	CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy);
	return addUnchecked(hash, entry, setAncestors, fCurrentEstimate);
	}

	void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add)
	{
	setEntries s;
	if (add && mapLinks[entry].children.insert(child).second) {
	cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
	} else if (!add && mapLinks[entry].children.erase(child)) {
	cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
	}
	}

	void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add)
	{
	setEntries s;
	if (add && mapLinks[entry].parents.insert(parent).second) {
	cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
	} else if (!add && mapLinks[entry].parents.erase(parent)) {
	cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
	}
	}

	const CTxMemPool::setEntries & CTxMemPool::GetMemPoolParents(txiter entry) const
	{
	assert (entry != mapTx.end());
	txlinksMap::const_iterator it = mapLinks.find(entry);
	assert(it != mapLinks.end());
	return it->second.parents;
	}

	const CTxMemPool::setEntries & CTxMemPool::GetMemPoolChildren(txiter entry) const
	{
	assert (entry != mapTx.end());
	txlinksMap::const_iterator it = mapLinks.find(entry);
	assert(it != mapLinks.end());
	return it->second.children;
	}

	CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const {
	LOCK(cs);
	if (!blockSinceLastRollingFeeBump \|\| rollingMinimumFeeRate == 0)
	return CFeeRate(rollingMinimumFeeRate);

	int64_t time = GetTime();
	if (time > lastRollingFeeUpdate + 10) {
	double halflife = ROLLING_FEE_HALFLIFE;
	if (DynamicMemoryUsage() < sizelimit / 4)
	halflife /= 4;
	else if (DynamicMemoryUsage() < sizelimit / 2)
	halflife /= 2;

	rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife);
	lastRollingFeeUpdate = time;

	if (rollingMinimumFeeRate < minReasonableRelayFee.GetFeePerK() / 2) {
	rollingMinimumFeeRate = 0;
	return CFeeRate(0);
	}
	}
	return std::max(CFeeRate(rollingMinimumFeeRate), minReasonableRelayFee);
	}

	void CTxMemPool::trackPackageRemoved(const CFeeRate& rate) {
	AssertLockHeld(cs);
	if (rate.GetFeePerK() > rollingMinimumFeeRate) {
	rollingMinimumFeeRate = rate.GetFeePerK();
	blockSinceLastRollingFeeBump = false;
	}
	}

	void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<uint256>* pvNoSpendsRemaining) {
	LOCK(cs);

	unsigned nTxnRemoved = 0;
	CFeeRate maxFeeRateRemoved(0);
	while (DynamicMemoryUsage() > sizelimit) {
	indexed_transaction_set::index<descendant_score>::type::iterator it = mapTx.get<descendant_score>().begin();

	// We set the new mempool min fee to the feerate of the removed set, plus the
	// "minimum reasonable fee rate" (ie some value under which we consider txn
	// to have 0 fee). This way, we don't allow txn to enter mempool with feerate
	// equal to txn which were removed with no block in between.
	CFeeRate removed(it->GetModFeesWithDescendants(), it->GetSizeWithDescendants());
	removed += minReasonableRelayFee;
	trackPackageRemoved(removed);
	maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);

	setEntries stage;
	CalculateDescendants(mapTx.project<0>(it), stage);
	nTxnRemoved += stage.size();

	std::vector<CTransaction> txn;
	if (pvNoSpendsRemaining) {
	txn.reserve(stage.size());
	BOOST_FOREACH(txiter it, stage)
	txn.push_back(it->GetTx());
	}
	RemoveStaged(stage, false);
	if (pvNoSpendsRemaining) {
	BOOST_FOREACH(const CTransaction& tx, txn) {
	BOOST_FOREACH(const CTxIn& txin, tx.vin) {
	if (exists(txin.prevout.hash))
	continue;
	std::map<COutPoint, CInPoint>::iterator it = mapNextTx.lower_bound(COutPoint(txin.prevout.hash, 0));
	if (it == mapNextTx.end() \|\| it->first.hash != txin.prevout.hash)
	pvNoSpendsRemaining->push_back(txin.prevout.hash);
	}
	}
	}
	}

	if (maxFeeRateRemoved > CFeeRate(0))
	LogPrint("mempool", "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString());
	}
	diff --git a/src/txmempool.h b/src/txmempool.h
	index 3f80a6ec24..a82d17c2f8 100644
	--- a/src/txmempool.h
	+++ b/src/txmempool.h
	@@ -1,665 +1,665 @@
	// Copyright (c) 2009-2010 Satoshi Nakamoto
	// Copyright (c) 2009-2015 The Bitcoin Core developers
	// Distributed under the MIT software license, see the accompanying
	// file COPYING or http://www.opensource.org/licenses/mit-license.php.

	#ifndef BITCOIN_TXMEMPOOL_H
	#define BITCOIN_TXMEMPOOL_H

	#include <list>
	#include <set>

	#include "amount.h"
	#include "coins.h"
	#include "primitives/transaction.h"
	#include "sync.h"

	#undef foreach
	#include "boost/multi_index_container.hpp"
	#include "boost/multi_index/ordered_index.hpp"

	class CAutoFile;

	inline double AllowFreeThreshold()
	{
	return COIN * 144 / 250;
	}

	inline bool AllowFree(double dPriority)
	{
	// Large (in bytes) low-priority (new, small-coin) transactions
	// need a fee.
	return dPriority > AllowFreeThreshold();
	}

	/** Fake height value used in CCoins to signify they are only in the memory pool (since 0.8) */
	static const unsigned int MEMPOOL_HEIGHT = 0x7FFFFFFF;

	class CTxMemPool;

	/** \class CTxMemPoolEntry
	*
	* CTxMemPoolEntry stores data about the correponding transaction, as well
	* as data about all in-mempool transactions that depend on the transaction
	* ("descendant" transactions).
	*
	* When a new entry is added to the mempool, we update the descendant state
	* (nCountWithDescendants, nSizeWithDescendants, and nModFeesWithDescendants) for
	* all ancestors of the newly added transaction.
	*
	* If updating the descendant state is skipped, we can mark the entry as
	* "dirty", and set nSizeWithDescendants/nModFeesWithDescendants to equal nTxSize/
	* nFee+feeDelta. (This can potentially happen during a reorg, where we limit the
	* amount of work we're willing to do to avoid consuming too much CPU.)
	*
	*/

	class CTxMemPoolEntry
	{
	private:
	CTransaction tx;
	CAmount nFee; //! Cached to avoid expensive parent-transaction lookups
	size_t nTxSize; //! ... and avoid recomputing tx size
	size_t nModSize; //! ... and modified size for priority
	size_t nUsageSize; //! ... and total memory usage
	int64_t nTime; //! Local time when entering the mempool
	double entryPriority; //! Priority when entering the mempool
	unsigned int entryHeight; //! Chain height when entering the mempool
	bool hadNoDependencies; //! Not dependent on any other txs when it entered the mempool
	CAmount inChainInputValue; //! Sum of all txin values that are already in blockchain
	bool spendsCoinbase; //! keep track of transactions that spend a coinbase
	unsigned int sigOpCount; //! Legacy sig ops plus P2SH sig op count
	int64_t feeDelta; //! Used for determining the priority of the transaction for mining in a block

	// Information about descendants of this transaction that are in the
	// mempool; if we remove this transaction we must remove all of these
	// descendants as well. if nCountWithDescendants is 0, treat this entry as
	// dirty, and nSizeWithDescendants and nModFeesWithDescendants will not be
	// correct.
	uint64_t nCountWithDescendants; //! number of descendant transactions
	uint64_t nSizeWithDescendants; //! ... and size
	CAmount nModFeesWithDescendants; //! ... and total fees (all including us)

	// Analogous statistics for ancestor transactions
	uint64_t nCountWithAncestors;
	uint64_t nSizeWithAncestors;
	CAmount nModFeesWithAncestors;
	unsigned int nSigOpCountWithAncestors;

	public:
	CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
	int64_t _nTime, double _entryPriority, unsigned int _entryHeight,
	bool poolHasNoInputsOf, CAmount _inChainInputValue, bool spendsCoinbase,
	unsigned int nSigOps);
	CTxMemPoolEntry(const CTxMemPoolEntry& other);

	const CTransaction& GetTx() const { return this->tx; }
	/**
	* Fast calculation of lower bound of current priority as update
	* from entry priority. Only inputs that were originally in-chain will age.
	*/
	double GetPriority(unsigned int currentHeight) const;
	const CAmount& GetFee() const { return nFee; }
	size_t GetTxSize() const { return nTxSize; }
	int64_t GetTime() const { return nTime; }
	unsigned int GetHeight() const { return entryHeight; }
	bool WasClearAtEntry() const { return hadNoDependencies; }
	unsigned int GetSigOpCount() const { return sigOpCount; }
	int64_t GetModifiedFee() const { return nFee + feeDelta; }
	size_t DynamicMemoryUsage() const { return nUsageSize; }

	// Adjusts the descendant state, if this entry is not dirty.
	void UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount);
	// Adjusts the ancestor state
	void UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int modifySigOps);
	// Updates the fee delta used for mining priority score, and the
	// modified fees with descendants.
	void UpdateFeeDelta(int64_t feeDelta);

	uint64_t GetCountWithDescendants() const { return nCountWithDescendants; }
	uint64_t GetSizeWithDescendants() const { return nSizeWithDescendants; }
	CAmount GetModFeesWithDescendants() const { return nModFeesWithDescendants; }

	bool GetSpendsCoinbase() const { return spendsCoinbase; }

	uint64_t GetCountWithAncestors() const { return nCountWithAncestors; }
	uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors; }
	CAmount GetModFeesWithAncestors() const { return nModFeesWithAncestors; }
	unsigned int GetSigOpCountWithAncestors() const { return nSigOpCountWithAncestors; }
	};

	// Helpers for modifying CTxMemPool::mapTx, which is a boost multi_index.
	struct update_descendant_state
	{
	update_descendant_state(int64_t _modifySize, CAmount _modifyFee, int64_t _modifyCount) :
	modifySize(_modifySize), modifyFee(_modifyFee), modifyCount(_modifyCount)
	{}

	void operator() (CTxMemPoolEntry &e)
	{ e.UpdateDescendantState(modifySize, modifyFee, modifyCount); }

	private:
	int64_t modifySize;
	CAmount modifyFee;
	int64_t modifyCount;
	};

	struct update_ancestor_state
	{
	update_ancestor_state(int64_t _modifySize, CAmount _modifyFee, int64_t _modifyCount, int _modifySigOps) :
	modifySize(_modifySize), modifyFee(_modifyFee), modifyCount(_modifyCount), modifySigOps(_modifySigOps)
	{}

	void operator() (CTxMemPoolEntry &e)
	{ e.UpdateAncestorState(modifySize, modifyFee, modifyCount, modifySigOps); }

	private:
	int64_t modifySize;
	CAmount modifyFee;
	int64_t modifyCount;
	int modifySigOps;
	};

	struct update_fee_delta
	{
	update_fee_delta(int64_t _feeDelta) : feeDelta(_feeDelta) { }

	void operator() (CTxMemPoolEntry &e) { e.UpdateFeeDelta(feeDelta); }

	private:
	int64_t feeDelta;
	};

	// extracts a TxMemPoolEntry's transaction hash
	struct mempoolentry_txid
	{
	typedef uint256 result_type;
	result_type operator() (const CTxMemPoolEntry &entry) const
	{
	return entry.GetTx().GetHash();
	}
	};

	/** \class CompareTxMemPoolEntryByDescendantScore
	*
	* Sort an entry by max(score/size of entry's tx, score/size with all descendants).
	*/
	class CompareTxMemPoolEntryByDescendantScore
	{
	public:
	bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b)
	{
	bool fUseADescendants = UseDescendantScore(a);
	bool fUseBDescendants = UseDescendantScore(b);

	double aModFee = fUseADescendants ? a.GetModFeesWithDescendants() : a.GetModifiedFee();
	double aSize = fUseADescendants ? a.GetSizeWithDescendants() : a.GetTxSize();

	double bModFee = fUseBDescendants ? b.GetModFeesWithDescendants() : b.GetModifiedFee();
	double bSize = fUseBDescendants ? b.GetSizeWithDescendants() : b.GetTxSize();

	// Avoid division by rewriting (a/b > c/d) as (ad > cb).
	double f1 = aModFee * bSize;
	double f2 = aSize * bModFee;

	if (f1 == f2) {
	return a.GetTime() >= b.GetTime();
	}
	return f1 < f2;
	}

	// Calculate which score to use for an entry (avoiding division).
	bool UseDescendantScore(const CTxMemPoolEntry &a)
	{
	double f1 = (double)a.GetModifiedFee() * a.GetSizeWithDescendants();
	double f2 = (double)a.GetModFeesWithDescendants() * a.GetTxSize();
	return f2 > f1;
	}
	};

	/** \class CompareTxMemPoolEntryByScore
	*
	* Sort by score of entry ((fee+delta)/size) in descending order
	*/
	class CompareTxMemPoolEntryByScore
	{
	public:
	bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b)
	{
	double f1 = (double)a.GetModifiedFee() * b.GetTxSize();
	double f2 = (double)b.GetModifiedFee() * a.GetTxSize();
	if (f1 == f2) {
	return b.GetTx().GetHash() < a.GetTx().GetHash();
	}
	return f1 > f2;
	}
	};

	class CompareTxMemPoolEntryByEntryTime
	{
	public:
	bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b)
	{
	return a.GetTime() < b.GetTime();
	}
	};

	class CompareTxMemPoolEntryByAncestorFee
	{
	public:
	bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b)
	{
	double aFees = a.GetModFeesWithAncestors();
	double aSize = a.GetSizeWithAncestors();

	double bFees = b.GetModFeesWithAncestors();
	double bSize = b.GetSizeWithAncestors();

	// Avoid division by rewriting (a/b > c/d) as (ad > cb).
	double f1 = aFees * bSize;
	double f2 = aSize * bFees;

	if (f1 == f2) {
	return a.GetTx().GetHash() < b.GetTx().GetHash();
	}

	return f1 > f2;
	}
	};

	// Multi_index tag names
	struct descendant_score {};
	struct entry_time {};
	struct mining_score {};
	struct ancestor_score {};

	class CBlockPolicyEstimator;

	/** An inpoint - a combination of a transaction and an index n into its vin */
	class CInPoint
	{
	public:
	const CTransaction* ptx;
	uint32_t n;

	CInPoint() { SetNull(); }
	CInPoint(const CTransaction* ptxIn, uint32_t nIn) { ptx = ptxIn; n = nIn; }
	void SetNull() { ptx = NULL; n = (uint32_t) -1; }
	bool IsNull() const { return (ptx == NULL && n == (uint32_t) -1); }
	size_t DynamicMemoryUsage() const { return 0; }
	};

	/**
	* CTxMemPool stores valid-according-to-the-current-best-chain
	* transactions that may be included in the next block.
	*
	* Transactions are added when they are seen on the network
	* (or created by the local node), but not all transactions seen
	* are added to the pool: if a new transaction double-spends
	* an input of a transaction in the pool, it is dropped,
	* as are non-standard transactions.
	*
	* CTxMemPool::mapTx, and CTxMemPoolEntry bookkeeping:
	*
	* mapTx is a boost::multi_index that sorts the mempool on 4 criteria:
	* - transaction hash
	* - feerate [we use max(feerate of tx, feerate of tx with all descendants)]
	* - time in mempool
	* - mining score (feerate modified by any fee deltas from PrioritiseTransaction)
	*
	* Note: the term "descendant" refers to in-mempool transactions that depend on
	* this one, while "ancestor" refers to in-mempool transactions that a given
	* transaction depends on.
	*
	* In order for the feerate sort to remain correct, we must update transactions
	* in the mempool when new descendants arrive. To facilitate this, we track
	* the set of in-mempool direct parents and direct children in mapLinks. Within
	* each CTxMemPoolEntry, we track the size and fees of all descendants.
	*
	* Usually when a new transaction is added to the mempool, it has no in-mempool
	* children (because any such children would be an orphan). So in
	* addUnchecked(), we:
	* - update a new entry's setMemPoolParents to include all in-mempool parents
	* - update the new entry's direct parents to include the new tx as a child
	* - update all ancestors of the transaction to include the new tx's size/fee
	*
	* When a transaction is removed from the mempool, we must:
	* - update all in-mempool parents to not track the tx in setMemPoolChildren
	* - update all ancestors to not include the tx's size/fees in descendant state
	* - update all in-mempool children to not include it as a parent
	*
	* These happen in UpdateForRemoveFromMempool(). (Note that when removing a
	* transaction along with its descendants, we must calculate that set of
	* transactions to be removed before doing the removal, or else the mempool can
	* be in an inconsistent state where it's impossible to walk the ancestors of
	* a transaction.)
	*
	* In the event of a reorg, the assumption that a newly added tx has no
	* in-mempool children is false. In particular, the mempool is in an
	* inconsistent state while new transactions are being added, because there may
	* be descendant transactions of a tx coming from a disconnected block that are
	* unreachable from just looking at transactions in the mempool (the linking
	* transactions may also be in the disconnected block, waiting to be added).
	* Because of this, there's not much benefit in trying to search for in-mempool
	* children in addUnchecked(). Instead, in the special case of transactions
	* being added from a disconnected block, we require the caller to clean up the
	* state, to account for in-mempool, out-of-block descendants for all the
	* in-block transactions by calling UpdateTransactionsFromBlock(). Note that
	* until this is called, the mempool state is not consistent, and in particular
	* mapLinks may not be correct (and therefore functions like
	* CalculateMemPoolAncestors() and CalculateDescendants() that rely
	* on them to walk the mempool are not generally safe to use).
	*
	* Computational limits:
	*
	* Updating all in-mempool ancestors of a newly added transaction can be slow,
	* if no bound exists on how many in-mempool ancestors there may be.
	* CalculateMemPoolAncestors() takes configurable limits that are designed to
	* prevent these calculations from being too CPU intensive.
	*
	* Adding transactions from a disconnected block can be very time consuming,
	* because we don't have a way to limit the number of in-mempool descendants.
	* To bound CPU processing, we limit the amount of work we're willing to do
	* to properly update the descendant information for a tx being added from
	* a disconnected block. If we would exceed the limit, then we instead mark
	* the entry as "dirty", and set the feerate for sorting purposes to be equal
	* the feerate of the transaction without any descendants.
	*
	*/
	class CTxMemPool
	{
	private:
	uint32_t nCheckFrequency; //! Value n means that n times in 2^32 we check.
	unsigned int nTransactionsUpdated;
	CBlockPolicyEstimator* minerPolicyEstimator;

	uint64_t totalTxSize; //! sum of all mempool tx' byte sizes
	uint64_t cachedInnerUsage; //! sum of dynamic memory usage of all the map elements (NOT the maps themselves)

	CFeeRate minReasonableRelayFee;

	mutable int64_t lastRollingFeeUpdate;
	mutable bool blockSinceLastRollingFeeBump;
	mutable double rollingMinimumFeeRate; //! minimum fee to get into the pool, decreases exponentially

	void trackPackageRemoved(const CFeeRate& rate);

	public:

	static const int ROLLING_FEE_HALFLIFE = 60 * 60 * 12; // public only for testing

	typedef boost::multi_index_container<
	CTxMemPoolEntry,
	boost::multi_index::indexed_by<
	// sorted by txid
	boost::multi_index::ordered_unique<mempoolentry_txid>,
	// sorted by fee rate
	boost::multi_index::ordered_non_unique<
	boost::multi_index::tag<descendant_score>,
	boost::multi_index::identity<CTxMemPoolEntry>,
	CompareTxMemPoolEntryByDescendantScore
	>,
	// sorted by entry time
	boost::multi_index::ordered_non_unique<
	boost::multi_index::tag<entry_time>,
	boost::multi_index::identity<CTxMemPoolEntry>,
	CompareTxMemPoolEntryByEntryTime
	>,
	// sorted by score (for mining prioritization)
	boost::multi_index::ordered_unique<
	boost::multi_index::tag<mining_score>,
	boost::multi_index::identity<CTxMemPoolEntry>,
	CompareTxMemPoolEntryByScore
	>,
	// sorted by fee rate with ancestors
	boost::multi_index::ordered_non_unique<
	boost::multi_index::tag<ancestor_score>,
	boost::multi_index::identity<CTxMemPoolEntry>,
	CompareTxMemPoolEntryByAncestorFee
	>
	>
	> indexed_transaction_set;

	mutable CCriticalSection cs;
	indexed_transaction_set mapTx;
	typedef indexed_transaction_set::nth_index<0>::type::iterator txiter;
	struct CompareIteratorByHash {
	bool operator()(const txiter &a, const txiter &b) const {
	return a->GetTx().GetHash() < b->GetTx().GetHash();
	}
	};
	typedef std::set<txiter, CompareIteratorByHash> setEntries;

	const setEntries & GetMemPoolParents(txiter entry) const;
	const setEntries & GetMemPoolChildren(txiter entry) const;
	private:
	typedef std::map<txiter, setEntries, CompareIteratorByHash> cacheMap;

	struct TxLinks {
	setEntries parents;
	setEntries children;
	};

	typedef std::map<txiter, TxLinks, CompareIteratorByHash> txlinksMap;
	txlinksMap mapLinks;

	void UpdateParent(txiter entry, txiter parent, bool add);
	void UpdateChild(txiter entry, txiter child, bool add);

	public:
	std::map<COutPoint, CInPoint> mapNextTx;
	std::map<uint256, std::pair<double, CAmount> > mapDeltas;

	/** Create a new CTxMemPool.
	* minReasonableRelayFee should be a feerate which is, roughly, somewhere
	* around what it "costs" to relay a transaction around the network and
	* below which we would reasonably say a transaction has 0-effective-fee.
	*/
	CTxMemPool(const CFeeRate& _minReasonableRelayFee);
	~CTxMemPool();

	/**
	* If sanity-checking is turned on, check makes sure the pool is
	* consistent (does not contain two transactions that spend the same inputs,
	* all inputs are in the mapNextTx array). If sanity-checking is turned off,
	* check does nothing.
	*/
	void check(const CCoinsViewCache *pcoins) const;
	void setSanityCheck(double dFrequency = 1.0) { nCheckFrequency = dFrequency * 4294967295.0; }

	// addUnchecked must updated state for all ancestors of a given transaction,
	// to track size/count of descendant transactions. First version of
	// addUnchecked can be used to have it call CalculateMemPoolAncestors(), and
	// then invoke the second version.
	bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate = true);
	bool addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, setEntries &setAncestors, bool fCurrentEstimate = true);

	void removeRecursive(const CTransaction &tx, std::list<CTransaction>& removed);
	void removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags);
	void removeConflicts(const CTransaction &tx, std::list<CTransaction>& removed);
	void removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight,
	std::list<CTransaction>& conflicts, bool fCurrentEstimate = true);
	void clear();
	void _clear(); //lock free
	void queryHashes(std::vector<uint256>& vtxid);
	void pruneSpent(const uint256& hash, CCoins &coins);
	unsigned int GetTransactionsUpdated() const;
	void AddTransactionsUpdated(unsigned int n);
	/**
	* Check that none of this transactions inputs are in the mempool, and thus
	* the tx is not dependent on other mempool transactions to be included in a block.
	*/
	bool HasNoInputsOf(const CTransaction& tx) const;

	/** Affect CreateNewBlock prioritisation of transactions */
	void PrioritiseTransaction(const uint256 hash, const std::string strHash, double dPriorityDelta, const CAmount& nFeeDelta);
	void ApplyDeltas(const uint256 hash, double &dPriorityDelta, CAmount &nFeeDelta) const;
	void ClearPrioritisation(const uint256 hash);

	public:
	/** Remove a set of transactions from the mempool.
	* If a transaction is in this set, then all in-mempool descendants must
	* also be in the set, unless this transaction is being removed for being
	* in a block.
	* Set updateDescendants to true when removing a tx that was in a block, so
	* that any in-mempool descendants have their ancestor state updated.
	*/
	void RemoveStaged(setEntries &stage, bool updateDescendants);

	/** When adding transactions from a disconnected block back to the mempool,
	* new mempool entries may have children in the mempool (which is generally
	* not the case when otherwise adding transactions).
	* UpdateTransactionsFromBlock() will find child transactions and update the
	* descendant state for each transaction in hashesToUpdate (excluding any
	* child transactions present in hashesToUpdate, which are already accounted
	* for). Note: hashesToUpdate should be the set of transactions from the
	* disconnected block that have been accepted back into the mempool.
	*/
	void UpdateTransactionsFromBlock(const std::vector<uint256> &hashesToUpdate);

	/** Try to calculate all in-mempool ancestors of entry.
	* (these are all calculated including the tx itself)
	* limitAncestorCount = max number of ancestors
	* limitAncestorSize = max size of ancestors
	* limitDescendantCount = max number of descendants any ancestor can have
	* limitDescendantSize = max size of descendants any ancestor can have
	* errString = populated with error reason if any limits are hit
	* fSearchForParents = whether to search a tx's vin for in-mempool parents, or
	* look up parents from mapLinks. Must be true for entries not in the mempool
	*/
	- bool CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString, bool fSearchForParents = true);
	+ bool CalculateMemPoolAncestors(const CTxMemPoolEntry &entry, setEntries &setAncestors, uint64_t limitAncestorCount, uint64_t limitAncestorSize, uint64_t limitDescendantCount, uint64_t limitDescendantSize, std::string &errString, bool fSearchForParents = true) const;

	/** Populate setDescendants with all in-mempool descendants of hash.
	* Assumes that setDescendants includes all in-mempool descendants of anything
	* already in it. */
	void CalculateDescendants(txiter it, setEntries &setDescendants);

	/** The minimum fee to get into the mempool, which may itself not be enough
	* for larger-sized transactions.
	* The minReasonableRelayFee constructor arg is used to bound the time it
	* takes the fee rate to go back down all the way to 0. When the feerate
	* would otherwise be half of this, it is set to 0 instead.
	*/
	CFeeRate GetMinFee(size_t sizelimit) const;

	/** Remove transactions from the mempool until its dynamic size is <= sizelimit.
	* pvNoSpendsRemaining, if set, will be populated with the list of transactions
	* which are not in mempool which no longer have any spends in this mempool.
	*/
	void TrimToSize(size_t sizelimit, std::vector<uint256>* pvNoSpendsRemaining=NULL);

	/** Expire all transaction (and their dependencies) in the mempool older than time. Return the number of removed transactions. */
	int Expire(int64_t time);

	unsigned long size()
	{
	LOCK(cs);
	return mapTx.size();
	}

	uint64_t GetTotalTxSize()
	{
	LOCK(cs);
	return totalTxSize;
	}

	bool exists(uint256 hash) const
	{
	LOCK(cs);
	return (mapTx.count(hash) != 0);
	}

	bool lookup(uint256 hash, CTransaction& result) const;

	/** Estimate fee rate needed to get into the next nBlocks
	* If no answer can be given at nBlocks, return an estimate
	* at the lowest number of blocks where one can be given
	*/
	CFeeRate estimateSmartFee(int nBlocks, int *answerFoundAtBlocks = NULL) const;

	/** Estimate fee rate needed to get into the next nBlocks */
	CFeeRate estimateFee(int nBlocks) const;

	/** Estimate priority needed to get into the next nBlocks
	* If no answer can be given at nBlocks, return an estimate
	* at the lowest number of blocks where one can be given
	*/
	double estimateSmartPriority(int nBlocks, int *answerFoundAtBlocks = NULL) const;

	/** Estimate priority needed to get into the next nBlocks */
	double estimatePriority(int nBlocks) const;

	/** Write/Read estimates to disk */
	bool WriteFeeEstimates(CAutoFile& fileout) const;
	bool ReadFeeEstimates(CAutoFile& filein);

	size_t DynamicMemoryUsage() const;

	private:
	/** UpdateForDescendants is used by UpdateTransactionsFromBlock to update
	* the descendants for a single transaction that has been added to the
	* mempool but may have child transactions in the mempool, eg during a
	* chain reorg. setExclude is the set of descendant transactions in the
	* mempool that must not be accounted for (because any descendants in
	* setExclude were added to the mempool after the transaction being
	* updated and hence their state is already reflected in the parent
	* state).
	*
	* cachedDescendants will be updated with the descendants of the transaction
	* being updated, so that future invocations don't need to walk the
	* same transaction again, if encountered in another transaction chain.
	*/
	void UpdateForDescendants(txiter updateIt,
	cacheMap &cachedDescendants,
	const std::set<uint256> &setExclude);
	/** Update ancestors of hash to add/remove it as a descendant transaction. */
	void UpdateAncestorsOf(bool add, txiter hash, setEntries &setAncestors);
	/** Set ancestor state for an entry */
	void UpdateEntryForAncestors(txiter it, const setEntries &setAncestors);
	/** For each transaction being removed, update ancestors and any direct children.
	* If updateDescendants is true, then also update in-mempool descendants'
	* ancestor state. */
	void UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants);
	/** Sever link between specified transaction and direct children. */
	void UpdateChildrenForRemoval(txiter entry);

	/** Before calling removeUnchecked for a given transaction,
	* UpdateForRemoveFromMempool must be called on the entire (dependent) set
	* of transactions being removed at the same time. We use each
	* CTxMemPoolEntry's setMemPoolParents in order to walk ancestors of a
	* given transaction that is removed, so we can't remove intermediate
	* transactions in a chain before we've updated all the state for the
	* removal.
	*/
	void removeUnchecked(txiter entry);
	};

	/**
	* CCoinsView that brings transactions from a memorypool into view.
	* It does not check for spendings by memory pool transactions.
	*/
	class CCoinsViewMemPool : public CCoinsViewBacked
	{
	protected:
	CTxMemPool &mempool;

	public:
	CCoinsViewMemPool(CCoinsView *baseIn, CTxMemPool &mempoolIn);
	bool GetCoins(const uint256 &txid, CCoins &coins) const;
	bool HaveCoins(const uint256 &txid) const;
	};

	// We want to sort transactions by coin age priority
	typedef std::pair<double, CTxMemPool::txiter> TxCoinAgePriority;

	struct TxCoinAgePriorityCompare
	{
	bool operator()(const TxCoinAgePriority& a, const TxCoinAgePriority& b)
	{
	if (a.first == b.first)
	return CompareTxMemPoolEntryByScore()((b.second), (a.second)); //Reverse order to make sort less than
	return a.first < b.first;
	}
	};

	#endif // BITCOIN_TXMEMPOOL_H

File Metadata

Mime Type: text/x-diff
Expires: Sun, Mar 2, 11:12 (1 d, 19 h)
Storage Engine: blob
Storage Format: Raw Data
Storage Handle: 5187541
Default Alt Text: (70 KB)

No OneTemporaryActions

View Options

File Metadata

Event Timeline

No OneTemporary
Actions