85 int64_t time,
unsigned int entry_height,
86 bool spends_coinbase, int64_t sigops_cost,
LockPoints lp)
92 entryHeight{entry_height},
96 nSizeWithDescendants{GetTxSize()},
97 nModFeesWithDescendants{nFee},
98 nSizeWithAncestors{GetTxSize()},
99 nModFeesWithAncestors{nFee},
120 const std::set<uint256>& setExclude, std::set<uint256>& descendants_to_remove,
121 uint64_t ancestor_size_limit, uint64_t ancestor_count_limit)
124 stageEntries = updateIt->GetMemPoolChildrenConst();
126 while (!stageEntries.empty()) {
128 descendants.insert(descendant);
129 stageEntries.erase(descendant);
132 cacheMap::iterator cacheIt = cachedDescendants.find(mapTx.iterator_to(childEntry));
133 if (cacheIt != cachedDescendants.end()) {
136 for (
txiter cacheEntry : cacheIt->second) {
137 descendants.insert(*cacheEntry);
139 }
else if (!descendants.count(childEntry)) {
141 stageEntries.insert(childEntry);
147 int64_t modifySize = 0;
149 int64_t modifyCount = 0;
151 if (!setExclude.count(descendant.GetTx().GetHash())) {
152 modifySize += descendant.GetTxSize();
153 modifyFee += descendant.GetModifiedFee();
155 cachedDescendants[updateIt].insert(mapTx.iterator_to(descendant));
157 mapTx.modify(mapTx.iterator_to(descendant),
update_ancestor_state(updateIt->GetTxSize(), updateIt->GetModifiedFee(), 1, updateIt->GetSigOpCost()));
161 if (descendant.GetCountWithAncestors() > ancestor_count_limit || descendant.GetSizeWithAncestors() > ancestor_size_limit) {
162 descendants_to_remove.insert(descendant.GetTx().GetHash());
175 cacheMap mapMemPoolDescendantsToUpdate;
179 std::set<uint256> setAlreadyIncluded(vHashesToUpdate.begin(), vHashesToUpdate.end());
181 std::set<uint256> descendants_to_remove;
191 if (
it == mapTx.end()) {
194 auto iter = mapNextTx.lower_bound(
COutPoint(hash, 0));
200 for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
201 const uint256 &childHash = iter->second->GetHash();
202 txiter childIter = mapTx.find(childHash);
203 assert(childIter != mapTx.end());
206 if (!
visited(childIter) && !setAlreadyIncluded.count(childHash)) {
212 UpdateForDescendants(
it, mapMemPoolDescendantsToUpdate, setAlreadyIncluded, descendants_to_remove, ancestor_size_limit, ancestor_count_limit);
215 for (
const auto& txid : descendants_to_remove) {
228 uint64_t limitAncestorCount,
229 uint64_t limitAncestorSize,
230 uint64_t limitDescendantCount,
231 uint64_t limitDescendantSize,
232 std::string &errString)
const
234 size_t totalSizeWithAncestors = entry_size;
236 while (!staged_ancestors.empty()) {
238 txiter stageit = mapTx.iterator_to(stage);
240 setAncestors.insert(stageit);
241 staged_ancestors.erase(stage);
242 totalSizeWithAncestors += stageit->
GetTxSize();
244 if (stageit->GetSizeWithDescendants() + entry_size > limitDescendantSize) {
245 errString =
strprintf(
"exceeds descendant size limit for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantSize);
247 }
else if (stageit->GetCountWithDescendants() + entry_count > limitDescendantCount) {
248 errString =
strprintf(
"too many descendants for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantCount);
250 }
else if (totalSizeWithAncestors > limitAncestorSize) {
251 errString =
strprintf(
"exceeds ancestor size limit [limit: %u]", limitAncestorSize);
257 txiter parent_it = mapTx.iterator_to(parent);
260 if (setAncestors.count(parent_it) == 0) {
261 staged_ancestors.insert(parent);
263 if (staged_ancestors.size() + setAncestors.size() + entry_count > limitAncestorCount) {
264 errString =
strprintf(
"too many unconfirmed ancestors [limit: %u]", limitAncestorCount);
274 uint64_t limitAncestorCount,
275 uint64_t limitAncestorSize,
276 uint64_t limitDescendantCount,
277 uint64_t limitDescendantSize,
278 std::string &errString)
const
281 size_t total_size = 0;
282 for (
const auto& tx : package) {
284 for (
const auto& input : tx->vin) {
285 std::optional<txiter> piter =
GetIter(input.prevout.hash);
287 staged_ancestors.insert(**piter);
288 if (staged_ancestors.size() + package.size() > limitAncestorCount) {
289 errString =
strprintf(
"too many unconfirmed parents [limit: %u]", limitAncestorCount);
300 setAncestors, staged_ancestors,
301 limitAncestorCount, limitAncestorSize,
302 limitDescendantCount, limitDescendantSize, errString);
304 if (!ret) errString.insert(0,
"possibly ");
310 uint64_t limitAncestorCount,
311 uint64_t limitAncestorSize,
312 uint64_t limitDescendantCount,
313 uint64_t limitDescendantSize,
314 std::string &errString,
315 bool fSearchForParents )
const
320 if (fSearchForParents) {
324 for (
unsigned int i = 0; i < tx.
vin.size(); i++) {
325 std::optional<txiter> piter =
GetIter(tx.
vin[i].prevout.hash);
327 staged_ancestors.insert(**piter);
328 if (staged_ancestors.size() + 1 > limitAncestorCount) {
329 errString =
strprintf(
"too many unconfirmed parents [limit: %u]", limitAncestorCount);
337 txiter it = mapTx.iterator_to(entry);
338 staged_ancestors =
it->GetMemPoolParentsConst();
342 setAncestors, staged_ancestors,
343 limitAncestorCount, limitAncestorSize,
344 limitDescendantCount, limitDescendantSize, errString);
354 const int64_t updateCount = (add ? 1 : -1);
355 const int64_t updateSize = updateCount *
it->GetTxSize();
356 const CAmount updateFee = updateCount *
it->GetModifiedFee();
357 for (
txiter ancestorIt : setAncestors) {
364 int64_t updateCount = setAncestors.size();
365 int64_t updateSize = 0;
367 int64_t updateSigOpsCost = 0;
368 for (
txiter ancestorIt : setAncestors) {
369 updateSize += ancestorIt->GetTxSize();
370 updateFee += ancestorIt->GetModifiedFee();
371 updateSigOpsCost += ancestorIt->GetSigOpCost();
388 const uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
389 if (updateDescendants) {
396 for (
txiter removeIt : entriesToRemove) {
399 setDescendants.erase(removeIt);
400 int64_t modifySize = -((int64_t)removeIt->GetTxSize());
401 CAmount modifyFee = -removeIt->GetModifiedFee();
402 int modifySigOps = -removeIt->GetSigOpCost();
403 for (
txiter dit : setDescendants) {
408 for (
txiter removeIt : entriesToRemove) {
439 for (
txiter removeIt : entriesToRemove) {
465 : m_check_ratio(check_ratio), minerPolicyEstimator(estimator)
473 return mapNextTx.count(outpoint);
491 indexed_transaction_set::iterator newit = mapTx.insert(entry).first;
508 std::set<uint256> setParentTransactions;
509 for (
unsigned int i = 0; i < tx.
vin.size(); i++) {
510 mapNextTx.insert(std::make_pair(&tx.
vin[i].prevout, &tx));
511 setParentTransactions.insert(tx.
vin[i].prevout.hash);
521 for (
const auto& pit :
GetIterSet(setParentTransactions)) {
529 m_total_fee += entry.
GetFee();
535 newit->vTxHashesIdx = vTxHashes.size() - 1;
552 const uint256 hash =
it->GetTx().GetHash();
553 for (
const CTxIn& txin :
it->GetTx().vin)
554 mapNextTx.erase(txin.prevout);
558 if (vTxHashes.size() > 1) {
559 vTxHashes[
it->vTxHashesIdx] = std::move(vTxHashes.back());
560 vTxHashes[
it->vTxHashesIdx].second->vTxHashesIdx =
it->vTxHashesIdx;
561 vTxHashes.pop_back();
562 if (vTxHashes.size() * 2 < vTxHashes.capacity())
563 vTxHashes.shrink_to_fit();
567 totalTxSize -=
it->GetTxSize();
568 m_total_fee -=
it->GetFee();
569 cachedInnerUsage -=
it->DynamicMemoryUsage();
585 if (setDescendants.count(entryit) == 0) {
586 stage.insert(entryit);
591 while (!stage.empty()) {
593 setDescendants.insert(
it);
598 txiter childiter = mapTx.iterator_to(child);
599 if (!setDescendants.count(childiter)) {
600 stage.insert(childiter);
612 if (origit != mapTx.end()) {
613 txToRemove.insert(origit);
619 for (
unsigned int i = 0; i < origTx.
vout.size(); i++) {
621 if (
it == mapNextTx.end())
623 txiter nextit = mapTx.find(
it->second->GetHash());
624 assert(nextit != mapTx.end());
625 txToRemove.insert(nextit);
643 for (indexed_transaction_set::const_iterator
it = mapTx.begin();
it != mapTx.end();
it++) {
644 if (check_final_and_mature(
it)) txToRemove.insert(
it);
651 for (indexed_transaction_set::const_iterator
it = mapTx.begin();
it != mapTx.end();
it++) {
662 if (
it != mapNextTx.end()) {
664 if (txConflict != tx)
679 std::vector<const CTxMemPoolEntry*> entries;
680 for (
const auto& tx : vtx)
684 indexed_transaction_set::iterator i = mapTx.find(hash);
685 if (i != mapTx.end())
686 entries.push_back(&*i);
690 for (
const auto& tx : vtx)
693 if (
it != mapTx.end()) {
701 lastRollingFeeUpdate =
GetTime();
702 blockSinceLastRollingFeeBump =
true;
711 cachedInnerUsage = 0;
712 lastRollingFeeUpdate =
GetTime();
713 blockSinceLastRollingFeeBump =
false;
714 rollingMinimumFeeRate = 0;
724 void CTxMemPool::check(
const CCoinsViewCache& active_coins_tip, int64_t spendheight)
const
732 LogPrint(
BCLog::MEMPOOL,
"Checking mempool with %u transactions and %u inputs\n", (
unsigned int)mapTx.size(), (
unsigned int)mapNextTx.size());
734 uint64_t checkTotal = 0;
736 uint64_t innerUsage = 0;
737 uint64_t prev_ancestor_count{0};
742 checkTotal +=
it->GetTxSize();
743 check_total_fee +=
it->GetFee();
744 innerUsage +=
it->DynamicMemoryUsage();
750 indexed_transaction_set::const_iterator it2 = mapTx.find(txin.
prevout.
hash);
751 if (it2 != mapTx.end()) {
754 setParentCheck.insert(*it2);
761 auto it3 = mapNextTx.find(txin.
prevout);
762 assert(it3 != mapNextTx.end());
764 assert(it3->second == &tx);
769 assert(setParentCheck.size() ==
it->GetMemPoolParentsConst().size());
770 assert(std::equal(setParentCheck.begin(), setParentCheck.end(),
it->GetMemPoolParentsConst().begin(), comp));
773 uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
776 uint64_t nCountCheck = setAncestors.size() + 1;
777 uint64_t nSizeCheck =
it->GetTxSize();
778 CAmount nFeesCheck =
it->GetModifiedFee();
779 int64_t nSigOpCheck =
it->GetSigOpCost();
781 for (
txiter ancestorIt : setAncestors) {
782 nSizeCheck += ancestorIt->GetTxSize();
783 nFeesCheck += ancestorIt->GetModifiedFee();
784 nSigOpCheck += ancestorIt->GetSigOpCost();
787 assert(
it->GetCountWithAncestors() == nCountCheck);
788 assert(
it->GetSizeWithAncestors() == nSizeCheck);
789 assert(
it->GetSigOpCostWithAncestors() == nSigOpCheck);
790 assert(
it->GetModFeesWithAncestors() == nFeesCheck);
792 assert(prev_ancestor_count <= it->GetCountWithAncestors());
793 prev_ancestor_count =
it->GetCountWithAncestors();
797 auto iter = mapNextTx.lower_bound(
COutPoint(
it->GetTx().GetHash(), 0));
798 uint64_t child_sizes = 0;
799 for (; iter != mapNextTx.end() && iter->first->hash ==
it->GetTx().GetHash(); ++iter) {
800 txiter childit = mapTx.find(iter->second->GetHash());
801 assert(childit != mapTx.end());
802 if (setChildrenCheck.insert(*childit).second) {
803 child_sizes += childit->GetTxSize();
806 assert(setChildrenCheck.size() ==
it->GetMemPoolChildrenConst().size());
807 assert(std::equal(setChildrenCheck.begin(), setChildrenCheck.end(),
it->GetMemPoolChildrenConst().begin(), comp));
810 assert(
it->GetSizeWithDescendants() >= child_sizes +
it->GetTxSize());
816 for (
const auto& input: tx.
vin) mempoolDuplicate.SpendCoin(input.prevout);
817 AddCoins(mempoolDuplicate, tx, std::numeric_limits<int>::max());
819 for (
auto it = mapNextTx.cbegin();
it != mapNextTx.cend();
it++) {
821 indexed_transaction_set::const_iterator it2 = mapTx.find(hash);
823 assert(it2 != mapTx.end());
827 assert(totalTxSize == checkTotal);
828 assert(m_total_fee == check_total_fee);
829 assert(innerUsage == cachedInnerUsage);
835 indexed_transaction_set::const_iterator i = wtxid ?
get_iter_from_wtxid(hasha) : mapTx.find(hasha);
836 if (i == mapTx.end())
return false;
837 indexed_transaction_set::const_iterator j = wtxid ?
get_iter_from_wtxid(hashb) : mapTx.find(hashb);
838 if (j == mapTx.end())
return true;
839 uint64_t counta = i->GetCountWithAncestors();
840 uint64_t countb = j->GetCountWithAncestors();
841 if (counta == countb) {
844 return counta < countb;
848 class DepthAndScoreComparator
851 bool operator()(
const CTxMemPool::indexed_transaction_set::const_iterator& a,
const CTxMemPool::indexed_transaction_set::const_iterator& b)
853 uint64_t counta = a->GetCountWithAncestors();
854 uint64_t countb = b->GetCountWithAncestors();
855 if (counta == countb) {
858 return counta < countb;
865 std::vector<indexed_transaction_set::const_iterator> iters;
868 iters.reserve(mapTx.size());
870 for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) {
873 std::sort(iters.begin(), iters.end(), DepthAndScoreComparator());
883 vtxid.reserve(mapTx.size());
885 for (
auto it : iters) {
886 vtxid.push_back(
it->GetTx().GetHash());
891 return TxMempoolInfo{it->GetSharedTx(), it->GetTime(), it->GetFee(), it->GetTxSize(), it->GetModifiedFee() - it->GetFee()};
899 std::vector<TxMempoolInfo> ret;
900 ret.reserve(mapTx.size());
901 for (
auto it : iters) {
911 indexed_transaction_set::const_iterator i = mapTx.find(hash);
912 if (i == mapTx.end())
914 return i->GetSharedTx();
921 if (i == mapTx.end())
930 CAmount &delta = mapDeltas[hash];
933 if (
it != mapTx.end()) {
937 uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
940 for (
txiter ancestorIt : setAncestors) {
946 setDescendants.erase(
it);
947 for (
txiter descendantIt : setDescendants) {
959 std::map<uint256, CAmount>::const_iterator pos = mapDeltas.find(hash);
960 if (pos == mapDeltas.end())
962 const CAmount &delta = pos->second;
969 mapDeltas.erase(hash);
974 const auto it = mapNextTx.find(prevout);
975 return it == mapNextTx.end() ? nullptr :
it->second;
980 auto it = mapTx.find(txid);
981 if (
it != mapTx.end())
return it;
988 for (
const auto& h : hashes) {
990 if (mi) ret.insert(*mi);
997 for (
unsigned int i = 0; i < tx.
vin.size(); i++)
1018 if (outpoint.
n < ptx->vout.size()) {
1030 for (
unsigned int n = 0; n < tx->vout.size(); ++n) {
1044 if (m_unbroadcast_txids.erase(txid))
1046 LogPrint(
BCLog::MEMPOOL,
"Removed %i from set of unbroadcast txns%s\n", txid.
GetHex(), (unchecked ?
" before confirmation that txn was sent out" :
""));
1061 indexed_transaction_set::index<entry_time>::type::iterator
it = mapTx.get<
entry_time>().begin();
1063 while (
it != mapTx.get<
entry_time>().end() &&
it->GetTime() < time) {
1064 toremove.insert(mapTx.project<0>(
it));
1068 for (
txiter removeit : toremove) {
1072 return stage.size();
1078 uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
1081 return addUnchecked(entry, setAncestors, validFeeEstimate);
1088 if (add && entry->GetMemPoolChildren().insert(*child).second) {
1090 }
else if (!add && entry->GetMemPoolChildren().erase(*child)) {
1099 if (add && entry->GetMemPoolParents().insert(*parent).second) {
1101 }
else if (!add && entry->GetMemPoolParents().erase(*parent)) {
1108 if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0)
1109 return CFeeRate(llround(rollingMinimumFeeRate));
1112 if (time > lastRollingFeeUpdate + 10) {
1119 rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife);
1120 lastRollingFeeUpdate = time;
1123 rollingMinimumFeeRate = 0;
1132 if (rate.
GetFeePerK() > rollingMinimumFeeRate) {
1134 blockSinceLastRollingFeeBump =
false;
1141 unsigned nTxnRemoved = 0;
1144 indexed_transaction_set::index<descendant_score>::type::iterator
it = mapTx.get<
descendant_score>().begin();
1150 CFeeRate removed(
it->GetModFeesWithDescendants(),
it->GetSizeWithDescendants());
1153 maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
1157 nTxnRemoved += stage.size();
1159 std::vector<CTransaction> txn;
1160 if (pvNoSpendsRemaining) {
1161 txn.reserve(stage.size());
1162 for (
txiter iter : stage)
1163 txn.push_back(iter->GetTx());
1166 if (pvNoSpendsRemaining) {
1170 pvNoSpendsRemaining->push_back(txin.
prevout);
1176 if (maxFeeRateRemoved >
CFeeRate(0)) {
1183 std::vector<txiter> candidates;
1185 candidates.push_back(entry);
1186 uint64_t maximum = 0;
1187 while (candidates.size()) {
1188 txiter candidate = candidates.back();
1189 candidates.pop_back();
1190 if (!counted.insert(candidate).second)
continue;
1192 if (parents.size() == 0) {
1193 maximum = std::max(maximum, candidate->GetCountWithDescendants());
1196 candidates.push_back(mapTx.iterator_to(i));
1205 auto it = mapTx.find(txid);
1206 ancestors = descendants = 0;
1207 if (
it != mapTx.end()) {
1208 ancestors =
it->GetCountWithAncestors();
1209 if (ancestorsize) *ancestorsize =
it->GetSizeWithAncestors();
1210 if (ancestorfees) *ancestorfees =
it->GetModFeesWithAncestors();
1224 m_is_loaded = loaded;