Changeset View
Changeset View
Standalone View
Standalone View
src/miner.cpp
Show First 20 Lines • Show All 255 Lines • ▼ Show 20 Lines | bool BlockAssembler::isStillDependent(CTxMemPool::txiter iter) { | ||||
for (CTxMemPool::txiter parent : mempool->GetMemPoolParents(iter)) { | for (CTxMemPool::txiter parent : mempool->GetMemPoolParents(iter)) { | ||||
if (!inBlock.count(parent->GetTx().GetId())) { | if (!inBlock.count(parent->GetTx().GetId())) { | ||||
return true; | return true; | ||||
} | } | ||||
} | } | ||||
return false; | return false; | ||||
} | } | ||||
void BlockAssembler::onlyUnconfirmed(CTxMemPool::setEntries &testSet) { | |||||
for (CTxMemPool::setEntries::iterator iit = testSet.begin(); | |||||
iit != testSet.end();) { | |||||
// Only test txs not already in the block. | |||||
if (inBlock.count((*iit)->GetTx().GetId())) { | |||||
testSet.erase(iit++); | |||||
} else { | |||||
iit++; | |||||
} | |||||
} | |||||
} | |||||
bool BlockAssembler::TestPackage(uint64_t packageSize, | |||||
int64_t packageSigOps) const { | |||||
auto blockSizeWithPackage = nBlockSize + packageSize; | |||||
if (blockSizeWithPackage >= nMaxGeneratedBlockSize) { | |||||
return false; | |||||
} | |||||
if (nBlockSigOps + packageSigOps >= | |||||
GetMaxBlockSigOpsCount(blockSizeWithPackage)) { | |||||
return false; | |||||
} | |||||
return true; | |||||
} | |||||
/** | |||||
* Perform transaction-level checks before adding to block: | |||||
* - Transaction finality (locktime) | |||||
* - Serialized size (in case -blockmaxsize is in use) | |||||
*/ | |||||
bool BlockAssembler::TestPackageTransactions( | |||||
const CTxMemPool::setEntries &package) { | |||||
uint64_t nPotentialBlockSize = nBlockSize; | |||||
for (const CTxMemPool::txiter it : package) { | |||||
CValidationState state; | |||||
if (!ContextualCheckTransaction(*config, it->GetTx(), state, nHeight, | |||||
nLockTimeCutoff, nMedianTimePast)) { | |||||
return false; | |||||
} | |||||
uint64_t nTxSize = | |||||
::GetSerializeSize(it->GetTx(), SER_NETWORK, PROTOCOL_VERSION); | |||||
if (nPotentialBlockSize + nTxSize >= nMaxGeneratedBlockSize) { | |||||
return false; | |||||
} | |||||
nPotentialBlockSize += nTxSize; | |||||
} | |||||
return true; | |||||
} | |||||
BlockAssembler::TestForBlockResult | BlockAssembler::TestForBlockResult | ||||
BlockAssembler::TestForBlock(CTxMemPool::txiter it) { | BlockAssembler::TestForBlock(CTxMemPool::txiter it) { | ||||
auto blockSizeWithTx = | auto blockSizeWithTx = | ||||
nBlockSize + | nBlockSize + | ||||
::GetSerializeSize(it->GetTx(), SER_NETWORK, PROTOCOL_VERSION); | ::GetSerializeSize(it->GetTx(), SER_NETWORK, PROTOCOL_VERSION); | ||||
if (blockSizeWithTx >= nMaxGeneratedBlockSize) { | if (blockSizeWithTx >= nMaxGeneratedBlockSize) { | ||||
if (nBlockSize > nMaxGeneratedBlockSize - 100 || lastFewTxs > 50) { | if (nBlockSize > nMaxGeneratedBlockSize - 100 || lastFewTxs > 50) { | ||||
return TestForBlockResult::BlockFinished; | return TestForBlockResult::BlockFinished; | ||||
▲ Show 20 Lines • Show All 50 Lines • ▼ Show 20 Lines | if (fPrintPriority) { | ||||
mempool->ApplyDeltas(iter->GetTx().GetId(), dPriority, dummy); | mempool->ApplyDeltas(iter->GetTx().GetId(), dPriority, dummy); | ||||
LogPrintf( | LogPrintf( | ||||
"priority %.1f fee %s txid %s\n", dPriority, | "priority %.1f fee %s txid %s\n", dPriority, | ||||
CFeeRate(iter->GetModifiedFee(), iter->GetTxSize()).ToString(), | CFeeRate(iter->GetModifiedFee(), iter->GetTxSize()).ToString(), | ||||
iter->GetTx().GetId().ToString()); | iter->GetTx().GetId().ToString()); | ||||
} | } | ||||
} | } | ||||
// TODO: Temporary adapter, delete this eventually. | |||||
int BlockAssembler::UpdatePackagesForAdded( | |||||
const TxIdSet &alreadyAdded, | |||||
indexed_modified_transaction_set &mapModifiedTx) { | |||||
CTxMemPool::setEntries entries; | |||||
for (const TxId &id : alreadyAdded) { | |||||
entries.insert(mempool->mapTx.find(id)); | |||||
} | |||||
return UpdatePackagesForAdded(entries, mapModifiedTx); | |||||
} | |||||
int BlockAssembler::UpdatePackagesForAdded( | |||||
const CTxMemPool::setEntries &alreadyAdded, | |||||
indexed_modified_transaction_set &mapModifiedTx) { | |||||
int nDescendantsUpdated = 0; | |||||
for (const CTxMemPool::txiter it : alreadyAdded) { | |||||
CTxMemPool::setEntries descendants; | |||||
mempool->CalculateDescendants(it, descendants); | |||||
// Insert all descendants (not yet in block) into the modified set. | |||||
for (CTxMemPool::txiter desc : descendants) { | |||||
if (alreadyAdded.count(desc)) { | |||||
continue; | |||||
} | |||||
++nDescendantsUpdated; | |||||
modtxiter mit = mapModifiedTx.find(desc); | |||||
if (mit == mapModifiedTx.end()) { | |||||
CTxMemPoolModifiedEntry modEntry(desc); | |||||
modEntry.nSizeWithAncestors -= it->GetTxSize(); | |||||
modEntry.nBillableSizeWithAncestors -= it->GetTxBillableSize(); | |||||
modEntry.nModFeesWithAncestors -= it->GetModifiedFee(); | |||||
modEntry.nSigOpCountWithAncestors -= it->GetSigOpCount(); | |||||
mapModifiedTx.insert(modEntry); | |||||
} else { | |||||
mapModifiedTx.modify(mit, update_for_parent_inclusion(it)); | |||||
} | |||||
} | |||||
} | |||||
return nDescendantsUpdated; | |||||
} | |||||
// Skip entries in mapTx that are already in a block or are present in | |||||
// mapModifiedTx (which implies that the mapTx ancestor state is stale due to | |||||
// ancestor inclusion in the block). Also skip transactions that we've already | |||||
// failed to add. This can happen if we consider a transaction in mapModifiedTx | |||||
// and it fails: we can then potentially consider it again while walking mapTx. | |||||
// It's currently guaranteed to fail again, but as a belt-and-suspenders check | |||||
// we put it in failedTx and avoid re-evaluation, since the re-evaluation would | |||||
// be using cached size/sigops/fee values that are not actually correct. | |||||
bool BlockAssembler::SkipMapTxEntry( | |||||
CTxMemPool::txiter it, indexed_modified_transaction_set &mapModifiedTx, | |||||
const TxIdSet &failedTx) { | |||||
assert(it != mempool->mapTx.end()); | |||||
const TxId &txId = it->GetTx().GetId(); | |||||
return mapModifiedTx.count(it) || inBlock.count(txId) || | |||||
failedTx.count(txId); | |||||
} | |||||
void BlockAssembler::SortForBlock( | |||||
const CTxMemPool::setEntries &package, CTxMemPool::txiter entry, | |||||
std::vector<CTxMemPool::txiter> &sortedEntries) { | |||||
// Sort package by ancestor count. If a transaction A depends on transaction | |||||
// B, then A's ancestor count must be greater than B's. So this is | |||||
// sufficient to validly order the transactions for block inclusion. | |||||
sortedEntries.clear(); | |||||
sortedEntries.insert(sortedEntries.begin(), package.begin(), package.end()); | |||||
std::sort(sortedEntries.begin(), sortedEntries.end(), | |||||
CompareTxIterByAncestorCount()); | |||||
} | |||||
/** | /** | ||||
* addPackageTx includes transactions paying a fee by ensuring that | * addPackageTx includes transactions paying a fee by ensuring that | ||||
* the partial ordering of transactions is maintained. That is to say | * the partial ordering of transactions is maintained. That is to say | ||||
* children come after parents, despite having a potentially larger fee. | * children come after parents, despite having a potentially larger fee. | ||||
* @param[out] nPackagesSelected How many packages were selected | * @param[out] nPackagesSelected How many packages were selected | ||||
* @param[out] nDescendantsUpdated Number of descendant transactions updated | * @param[out] nDescendantsUpdated Number of descendant transactions updated | ||||
*/ | */ | ||||
void BlockAssembler::addPackageTxs(int &nPackagesSelected, | void BlockAssembler::addPackageTxs(int &nPackagesSelected, | ||||
▲ Show 20 Lines • Show All 224 Lines • ▼ Show 20 Lines | invalid: | ||||
break; | break; | ||||
} | } | ||||
} | } | ||||
} | } | ||||
continue; | continue; | ||||
} | } | ||||
} | } | ||||
/** | |||||
* accuratelyAddPackageTxs includes transactions paying a fee by ensuring that | |||||
* the partial ordering of transactions is maintained. That is to say | |||||
* children come after parents, despite having a potentially larger fee. | |||||
* @param[out] nPackagesSelected How many packages were selected | |||||
* @param[out] nDescendantsUpdated Number of descendant transactions updated | |||||
*/ | |||||
void BlockAssembler::accuratelyAddPackageTxs(int &nPackagesSelected, | |||||
int &nDescendantsUpdated) { | |||||
// selection algorithm orders the mempool based on feerate of a | |||||
// transaction including all unconfirmed ancestors. Since we don't remove | |||||
// transactions from the mempool as we select them for block inclusion, we | |||||
// need an alternate method of updating the feerate of a transaction with | |||||
// its not-yet-selected ancestors as we go. This is accomplished by | |||||
// walking the in-mempool descendants of selected transactions and storing | |||||
// a temporary modified state in mapModifiedTxs. Each time through the | |||||
// loop, we compare the best transaction in mapModifiedTxs with the next | |||||
// transaction in the mempool to decide what transaction package to work | |||||
// on next. | |||||
// mapModifiedTx will store sorted packages after they are modified because | |||||
// some of their txs are already in the block. | |||||
indexed_modified_transaction_set mapModifiedTx; | |||||
// Keep track of entries that failed inclusion, to avoid duplicate work. | |||||
TxIdSet failedTx; | |||||
// Start by adding all descendants of previously added txs to mapModifiedTx | |||||
// and modifying them for their already included ancestors. | |||||
UpdatePackagesForAdded(inBlock, mapModifiedTx); | |||||
CTxMemPool::indexed_transaction_set::index<ancestor_score>::type::iterator | |||||
mi = mempool->mapTx.get<ancestor_score>().begin(); | |||||
CTxMemPool::txiter iter; | |||||
// Limit the number of attempts to add transactions to the block when it is | |||||
// close to full; this is just a simple heuristic to finish quickly if the | |||||
// mempool has a lot of entries. | |||||
const int64_t MAX_CONSECUTIVE_FAILURES = 1000; | |||||
int64_t nConsecutiveFailed = 0; | |||||
while (mi != mempool->mapTx.get<ancestor_score>().end() || | |||||
!mapModifiedTx.empty()) { | |||||
// First try to find a new transaction in mapTx to evaluate. | |||||
if (mi != mempool->mapTx.get<ancestor_score>().end() && | |||||
SkipMapTxEntry(mempool->mapTx.project<0>(mi), mapModifiedTx, | |||||
failedTx)) { | |||||
++mi; | |||||
continue; | |||||
} | |||||
// Now that mi is not stale, determine which transaction to evaluate: | |||||
// the next entry from mapTx, or the best from mapModifiedTx? | |||||
bool fUsingModified = false; | |||||
modtxscoreiter modit = mapModifiedTx.get<ancestor_score>().begin(); | |||||
if (mi == mempool->mapTx.get<ancestor_score>().end()) { | |||||
// We're out of entries in mapTx; use the entry from mapModifiedTx | |||||
iter = modit->iter; | |||||
fUsingModified = true; | |||||
} else { | |||||
// Try to compare the mapTx entry to the mapModifiedTx entry. | |||||
iter = mempool->mapTx.project<0>(mi); | |||||
if (modit != mapModifiedTx.get<ancestor_score>().end() && | |||||
CompareModifiedEntry()(*modit, CTxMemPoolModifiedEntry(iter))) { | |||||
// The best entry in mapModifiedTx has higher score than the one | |||||
// from mapTx. Switch which transaction (package) to consider | |||||
iter = modit->iter; | |||||
fUsingModified = true; | |||||
} else { | |||||
// Either no entry in mapModifiedTx, or it's worse than mapTx. | |||||
// Increment mi for the next loop iteration. | |||||
++mi; | |||||
} | |||||
} | |||||
// We skip mapTx entries that are inBlock, and mapModifiedTx shouldn't | |||||
// contain anything that is inBlock. | |||||
assert(!inBlock.count(iter->GetTx().GetId())); | |||||
uint64_t packageSize = iter->GetSizeWithAncestors(); | |||||
Amount packageFees = iter->GetModFeesWithAncestors(); | |||||
int64_t packageSigOps = iter->GetSigOpCountWithAncestors(); | |||||
if (fUsingModified) { | |||||
packageSize = modit->nSizeWithAncestors; | |||||
packageFees = modit->nModFeesWithAncestors; | |||||
packageSigOps = modit->nSigOpCountWithAncestors; | |||||
} | |||||
if (packageFees < blockMinFeeRate.GetFee(packageSize)) { | |||||
// Everything else we might consider has a lower fee rate | |||||
return; | |||||
} | |||||
if (!TestPackage(packageSize, packageSigOps)) { | |||||
if (fUsingModified) { | |||||
// Since we always look at the best entry in mapModifiedTx, we | |||||
// must erase failed entries so that we can consider the next | |||||
// best entry on the next loop iteration | |||||
mapModifiedTx.get<ancestor_score>().erase(modit); | |||||
failedTx.insert(iter->GetTx().GetId()); | |||||
} | |||||
++nConsecutiveFailed; | |||||
if (nConsecutiveFailed > MAX_CONSECUTIVE_FAILURES && | |||||
nBlockSize > nMaxGeneratedBlockSize - 1000) { | |||||
// Give up if we're close to full and haven't succeeded in a | |||||
// while. | |||||
break; | |||||
} | |||||
continue; | |||||
} | |||||
CTxMemPool::setEntries ancestors; | |||||
uint64_t nNoLimit = std::numeric_limits<uint64_t>::max(); | |||||
std::string dummy; | |||||
mempool->CalculateMemPoolAncestors(*iter, ancestors, nNoLimit, nNoLimit, | |||||
nNoLimit, nNoLimit, dummy, false); | |||||
onlyUnconfirmed(ancestors); | |||||
ancestors.insert(iter); | |||||
// Test if all tx's are Final. | |||||
if (!TestPackageTransactions(ancestors)) { | |||||
if (fUsingModified) { | |||||
mapModifiedTx.get<ancestor_score>().erase(modit); | |||||
failedTx.insert(iter->GetTx().GetId()); | |||||
} | |||||
continue; | |||||
} | |||||
// This transaction will make it in; reset the failed counter. | |||||
nConsecutiveFailed = 0; | |||||
// Package can be added. Sort the entries in a valid order. | |||||
std::vector<CTxMemPool::txiter> sortedEntries; | |||||
SortForBlock(ancestors, iter, sortedEntries); | |||||
for (auto &entry : sortedEntries) { | |||||
AddToBlock(entry); | |||||
// Erase from the modified set, if present | |||||
mapModifiedTx.erase(entry); | |||||
} | |||||
++nPackagesSelected; | |||||
// Update transactions that depend on each of these | |||||
nDescendantsUpdated += UpdatePackagesForAdded(ancestors, mapModifiedTx); | |||||
} | |||||
} | |||||
void BlockAssembler::addPriorityTxs() { | void BlockAssembler::addPriorityTxs() { | ||||
// How much of the block should be dedicated to high-priority transactions, | // How much of the block should be dedicated to high-priority transactions, | ||||
// included regardless of the fees they pay. | // included regardless of the fees they pay. | ||||
if (config->GetBlockPriorityPercentage() == 0) { | if (config->GetBlockPriorityPercentage() == 0) { | ||||
return; | return; | ||||
} | } | ||||
uint64_t nBlockPrioritySize = | uint64_t nBlockPrioritySize = | ||||
▲ Show 20 Lines • Show All 120 Lines • Show Last 20 Lines |