diff --git a/src/miner.h b/src/miner.h --- a/src/miner.h +++ b/src/miner.h @@ -112,103 +112,6 @@ std::vector entries; }; -// Container for tracking updates to ancestor feerate as we include (parent) -// transactions in a block -struct CTxMemPoolModifiedEntry { - explicit CTxMemPoolModifiedEntry(CTxMemPool::txiter entry) { - iter = entry; - nSizeWithAncestors = entry->GetSizeWithAncestors(); - nBillableSizeWithAncestors = entry->GetBillableSizeWithAncestors(); - nModFeesWithAncestors = entry->GetModFeesWithAncestors(); - nSigOpCountWithAncestors = entry->GetSigOpCountWithAncestors(); - } - - CTxMemPool::txiter iter; - uint64_t nSizeWithAncestors; - uint64_t nBillableSizeWithAncestors; - Amount nModFeesWithAncestors; - int64_t nSigOpCountWithAncestors; -}; - -/** - * Comparator for CTxMemPool::txiter objects. - * It simply compares the internal memory address of the CTxMemPoolEntry object - * pointed to. This means it has no meaning, and is only useful for using them - * as key in other indexes. - */ -struct CompareCTxMemPoolIter { - bool operator()(const CTxMemPool::txiter &a, - const CTxMemPool::txiter &b) const { - return &(*a) < &(*b); - } -}; - -struct modifiedentry_iter { - typedef CTxMemPool::txiter result_type; - result_type operator()(const CTxMemPoolModifiedEntry &entry) const { - return entry.iter; - } -}; - -// This matches the calculation in CompareTxMemPoolEntryByAncestorFee, -// except operating on CTxMemPoolModifiedEntry. -// TODO: refactor to avoid duplication of this logic. -struct CompareModifiedEntry { - bool operator()(const CTxMemPoolModifiedEntry &a, - const CTxMemPoolModifiedEntry &b) const { - double f1 = b.nSizeWithAncestors * (a.nModFeesWithAncestors / SATOSHI); - double f2 = a.nSizeWithAncestors * (b.nModFeesWithAncestors / SATOSHI); - if (f1 == f2) { - return CTxMemPool::CompareIteratorByHash()(a.iter, b.iter); - } - return f1 > f2; - } -}; - -// A comparator that sorts transactions based on number of ancestors. -// This is sufficient to sort an ancestor package in an order that is valid -// to appear in a block. -struct CompareTxIterByAncestorCount { - bool operator()(const CTxMemPool::txiter &a, - const CTxMemPool::txiter &b) const { - if (a->GetCountWithAncestors() != b->GetCountWithAncestors()) { - return a->GetCountWithAncestors() < b->GetCountWithAncestors(); - } - return CTxMemPool::CompareIteratorByHash()(a, b); - } -}; - -typedef boost::multi_index_container< - CTxMemPoolModifiedEntry, - boost::multi_index::indexed_by< - boost::multi_index::ordered_unique, - // sorted by modified ancestor fee rate - boost::multi_index::ordered_non_unique< - // Reuse same tag from CTxMemPool's similar index - boost::multi_index::tag, - boost::multi_index::identity, - CompareModifiedEntry>>> - indexed_modified_transaction_set; - -typedef indexed_modified_transaction_set::nth_index<0>::type::iterator - modtxiter; -typedef indexed_modified_transaction_set::index::type::iterator - modtxscoreiter; - -struct update_for_parent_inclusion { - explicit update_for_parent_inclusion(CTxMemPool::txiter it) : iter(it) {} - - void operator()(CTxMemPoolModifiedEntry &e) { - e.nModFeesWithAncestors -= iter->GetFee(); - e.nSizeWithAncestors -= iter->GetTxSize(); - e.nBillableSizeWithAncestors -= iter->GetTxBillableSize(); - e.nSigOpCountWithAncestors -= iter->GetSigOpCount(); - } - - CTxMemPool::txiter iter; -}; - /** Generate a new block, without valid proof-of-work */ class BlockAssembler { private: @@ -263,10 +166,6 @@ * Increments nPackagesSelected / nDescendantsUpdated with corresponding * statistics from the package selection (for logging statistics). */ void addPackageTxs(int &nPackagesSelected, int &nDescendantsUpdated); - // Old version of addPackageTxs - // TODO: DELET THIS ONII-CHAN - void accuratelyAddPackageTxs(int &nPackagesSelected, - int &nDescendantsUpdated); /** Enum for the results from TestForBlock */ enum class TestForBlockResult : uint8_t { @@ -280,33 +179,6 @@ TestForBlockResult TestForBlock(CTxMemPool::txiter iter); /** Test if tx still has unconfirmed parents not yet in block */ bool isStillDependent(CTxMemPool::txiter iter); - - // helper functions for addPackageTxs() - /** Remove confirmed (inBlock) entries from given set */ - void onlyUnconfirmed(CTxMemPool::setEntries &testSet); - /** Test if a new package would "fit" in the block */ - bool TestPackage(uint64_t packageSize, int64_t packageSigOpsCost) const; - /** Perform checks on each transaction in a package: - * locktime, serialized size (if necessary) - * These checks should always succeed, and they're here - * only as an extra check in case of suboptimal node configuration */ - bool TestPackageTransactions(const CTxMemPool::setEntries &package); - /** Return true if given transaction from mapTx has already been evaluated, - * or if the transaction's cached data in mapTx is incorrect. */ - bool SkipMapTxEntry(CTxMemPool::txiter it, - indexed_modified_transaction_set &mapModifiedTx, - const TxIdSet &failedTx); - /** Sort the package in an order that is valid to appear in a block */ - void SortForBlock(const CTxMemPool::setEntries &package, - CTxMemPool::txiter entry, - std::vector &sortedEntries); - /** Add descendants of given transactions to mapModifiedTx with ancestor - * state updated assuming given transactions are inBlock. Returns number - * of updated descendants. */ - int UpdatePackagesForAdded(const CTxMemPool::setEntries &alreadyAdded, - indexed_modified_transaction_set &mapModifiedTx); - int UpdatePackagesForAdded(const TxIdSet &alreadyAdded, - indexed_modified_transaction_set &mapModifiedTx); }; /** Modify the extranonce in a block */ diff --git a/src/miner.cpp b/src/miner.cpp --- a/src/miner.cpp +++ b/src/miner.cpp @@ -261,60 +261,6 @@ 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::TestForBlock(CTxMemPool::txiter it) { auto blockSizeWithTx = @@ -381,77 +327,6 @@ } } -// 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 &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 * the partial ordering of transactions is maintained. That is to say @@ -692,159 +567,6 @@ } } -/** - * 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::type::iterator - mi = mempool->mapTx.get().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().end() || - !mapModifiedTx.empty()) { - // First try to find a new transaction in mapTx to evaluate. - if (mi != mempool->mapTx.get().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().begin(); - if (mi == mempool->mapTx.get().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().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().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::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().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 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() { // How much of the block should be dedicated to high-priority transactions, // included regardless of the fees they pay.