aboutsummaryrefslogtreecommitdiff
path: root/src/miner.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/miner.cpp')
-rw-r--r--src/miner.cpp206
1 files changed, 205 insertions, 1 deletions
diff --git a/src/miner.cpp b/src/miner.cpp
index 99eb0a2ebd..989ad11a26 100644
--- a/src/miner.cpp
+++ b/src/miner.cpp
@@ -25,6 +25,7 @@
#include "utilmoneystr.h"
#include "validationinterface.h"
+#include <algorithm>
#include <boost/thread.hpp>
#include <boost/tuple/tuple.hpp>
#include <queue>
@@ -134,7 +135,7 @@ CBlockTemplate* BlockAssembler::CreateNewBlock(const CScript& scriptPubKeyIn)
: pblock->GetBlockTime();
addPriorityTxs();
- addScoreTxs();
+ addPackageTxs();
nLastBlockTx = nBlockTx;
nLastBlockSize = nBlockSize;
@@ -177,7 +178,38 @@ bool BlockAssembler::isStillDependent(CTxMemPool::txiter iter)
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)) {
+ testSet.erase(iit++);
+ }
+ else {
+ iit++;
+ }
+ }
+}
+
+bool BlockAssembler::TestPackage(uint64_t packageSize, unsigned int packageSigOps)
+{
+ if (nBlockSize + packageSize >= nBlockMaxSize)
+ return false;
+ if (nBlockSigOps + packageSigOps >= MAX_BLOCK_SIGOPS)
+ return false;
+ return true;
+}
+// Block size and sigops have already been tested. Check that all transactions
+// are final.
+bool BlockAssembler::TestPackageFinality(const CTxMemPool::setEntries& package)
+{
+ BOOST_FOREACH (const CTxMemPool::txiter it, package) {
+ if (!IsFinalTx(it->GetTx(), nHeight, nLockTimeCutoff))
+ return false;
+ }
+ return true;
+}
bool BlockAssembler::TestForBlock(CTxMemPool::txiter iter)
{
@@ -297,6 +329,178 @@ void BlockAssembler::addScoreTxs()
}
}
+void BlockAssembler::UpdatePackagesForAdded(const CTxMemPool::setEntries& alreadyAdded,
+ indexed_modified_transaction_set &mapModifiedTx)
+{
+ BOOST_FOREACH(const CTxMemPool::txiter it, alreadyAdded) {
+ CTxMemPool::setEntries descendants;
+ mempool.CalculateDescendants(it, descendants);
+ // Insert all descendants (not yet in block) into the modified set
+ BOOST_FOREACH(CTxMemPool::txiter desc, descendants) {
+ if (alreadyAdded.count(desc))
+ continue;
+ modtxiter mit = mapModifiedTx.find(desc);
+ if (mit == mapModifiedTx.end()) {
+ CTxMemPoolModifiedEntry modEntry(desc);
+ modEntry.nSizeWithAncestors -= it->GetTxSize();
+ modEntry.nModFeesWithAncestors -= it->GetModifiedFee();
+ modEntry.nSigOpCountWithAncestors -= it->GetSigOpCount();
+ mapModifiedTx.insert(modEntry);
+ } else {
+ mapModifiedTx.modify(mit, update_for_parent_inclusion(it));
+ }
+ }
+ }
+}
+
+// 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, CTxMemPool::setEntries &failedTx)
+{
+ assert (it != mempool.mapTx.end());
+ if (mapModifiedTx.count(it) || inBlock.count(it) || failedTx.count(it))
+ return true;
+ return false;
+}
+
+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());
+}
+
+// This transaction 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.
+void BlockAssembler::addPackageTxs()
+{
+ // 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
+ CTxMemPool::setEntries 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;
+ 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));
+
+ uint64_t packageSize = iter->GetSizeWithAncestors();
+ CAmount packageFees = iter->GetModFeesWithAncestors();
+ unsigned int packageSigOps = iter->GetSigOpCountWithAncestors();
+ if (fUsingModified) {
+ packageSize = modit->nSizeWithAncestors;
+ packageFees = modit->nModFeesWithAncestors;
+ packageSigOps = modit->nSigOpCountWithAncestors;
+ }
+
+ if (packageFees < ::minRelayTxFee.GetFee(packageSize) && nBlockSize >= nBlockMinSize) {
+ // 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);
+ }
+ 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 (!TestPackageFinality(ancestors)) {
+ if (fUsingModified) {
+ mapModifiedTx.get<ancestor_score>().erase(modit);
+ failedTx.insert(iter);
+ }
+ continue;
+ }
+
+ // Package can be added. Sort the entries in a valid order.
+ vector<CTxMemPool::txiter> sortedEntries;
+ SortForBlock(ancestors, iter, sortedEntries);
+
+ for (size_t i=0; i<sortedEntries.size(); ++i) {
+ AddToBlock(sortedEntries[i]);
+ // Erase from the modified set, if present
+ mapModifiedTx.erase(sortedEntries[i]);
+ }
+
+ // Update transactions that depend on each of these
+ UpdatePackagesForAdded(ancestors, mapModifiedTx);
+ }
+}
+
void BlockAssembler::addPriorityTxs()
{
// How much of the block should be dedicated to high-priority transactions,