src/txmempool.cpp

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2016 The Bitcoin Core developers
   3 // Distributed under the MIT software license, see the accompanying
   4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   5
   6 #include "txmempool.h"
   7
   8 #include "consensus/consensus.h"
   9 #include "consensus/tx_verify.h"
  10 #include "consensus/validation.h"
  11 #include "validation.h"
  12 #include "policy/policy.h"
  13 #include "policy/fees.h"
  14 #include "reverse_iterator.h"
  15 #include "streams.h"
  16 #include "timedata.h"
  17 #include "util.h"
  18 #include "utilmoneystr.h"
  19 #include "utiltime.h"
  20
  21 CTxMemPoolEntry::CTxMemPoolEntry(const CTransactionRef& _tx, const CAmount& _nFee,
  22                                  int64_t _nTime, unsigned int _entryHeight,
  23                                  bool _spendsCoinbase, int64_t _sigOpsCost, LockPoints lp):
  24     tx(_tx), nFee(_nFee), nTime(_nTime), entryHeight(_entryHeight),
  25     spendsCoinbase(_spendsCoinbase), sigOpCost(_sigOpsCost), lockPoints(lp)
  26 {
  27     nTxWeight = GetTransactionWeight(*tx);
  28     nUsageSize = RecursiveDynamicUsage(tx);
  29
  30     nCountWithDescendants = 1;
  31     nSizeWithDescendants = GetTxSize();
  32     nModFeesWithDescendants = nFee;
  33
  34     feeDelta = 0;
  35
  36     nCountWithAncestors = 1;
  37     nSizeWithAncestors = GetTxSize();
  38     nModFeesWithAncestors = nFee;
  39     nSigOpCostWithAncestors = sigOpCost;
  40 }
  41
  42 CTxMemPoolEntry::CTxMemPoolEntry(const CTxMemPoolEntry& other)
  43 {
  44     *this = other;
  45 }
  46
  47 void CTxMemPoolEntry::UpdateFeeDelta(int64_t newFeeDelta)
  48 {
  49     nModFeesWithDescendants += newFeeDelta - feeDelta;
  50     nModFeesWithAncestors += newFeeDelta - feeDelta;
  51     feeDelta = newFeeDelta;
  52 }
  53
  54 void CTxMemPoolEntry::UpdateLockPoints(const LockPoints& lp)
  55 {
  56     lockPoints = lp;
  57 }
  58
  59 size_t CTxMemPoolEntry::GetTxSize() const
  60 {
  61     return GetVirtualTransactionSize(nTxWeight, sigOpCost);
  62 }
  63
  64 // Update the given tx for any in-mempool descendants.
  65 // Assumes that setMemPoolChildren is correct for the given tx and all
  66 // descendants.
  67 void CTxMemPool::UpdateForDescendants(txiter updateIt, cacheMap &cachedDescendants, const std::set<uint256> &setExclude)
  68 {
  69     setEntries stageEntries, setAllDescendants;
  70     stageEntries = GetMemPoolChildren(updateIt);
  71
  72     while (!stageEntries.empty()) {
  73         const txiter cit = *stageEntries.begin();
  74         setAllDescendants.insert(cit);
  75         stageEntries.erase(cit);
  76         const setEntries &setChildren = GetMemPoolChildren(cit);
  77         for (const txiter childEntry : setChildren) {
  78             cacheMap::iterator cacheIt = cachedDescendants.find(childEntry);
  79             if (cacheIt != cachedDescendants.end()) {
  80                 // We've already calculated this one, just add the entries for this set
  81                 // but don't traverse again.
  82                 for (const txiter cacheEntry : cacheIt->second) {
  83                     setAllDescendants.insert(cacheEntry);
  84                 }
  85             } else if (!setAllDescendants.count(childEntry)) {
  86                 // Schedule for later processing
  87                 stageEntries.insert(childEntry);
  88             }
  89         }
  90     }
  91     // setAllDescendants now contains all in-mempool descendants of updateIt.
  92     // Update and add to cached descendant map
  93     int64_t modifySize = 0;
  94     CAmount modifyFee = 0;
  95     int64_t modifyCount = 0;
  96     for (txiter cit : setAllDescendants) {
  97         if (!setExclude.count(cit->GetTx().GetHash())) {
  98             modifySize += cit->GetTxSize();
  99             modifyFee += cit->GetModifiedFee();
 100             modifyCount++;
 101             cachedDescendants[updateIt].insert(cit);
 102             // Update ancestor state for each descendant
 103             mapTx.modify(cit, update_ancestor_state(updateIt->GetTxSize(), updateIt->GetModifiedFee(), 1, updateIt->GetSigOpCost()));
 104         }
 105     }
 106     mapTx.modify(updateIt, update_descendant_state(modifySize, modifyFee, modifyCount));
 107 }
 108
 109 // vHashesToUpdate is the set of transaction hashes from a disconnected block
 110 // which has been re-added to the mempool.
 111 // for each entry, look for descendants that are outside vHashesToUpdate, and
 112 // add fee/size information for such descendants to the parent.
 113 // for each such descendant, also update the ancestor state to include the parent.
 114 void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256> &vHashesToUpdate)
 115 {
 116     LOCK(cs);
 117     // For each entry in vHashesToUpdate, store the set of in-mempool, but not
 118     // in-vHashesToUpdate transactions, so that we don't have to recalculate
 119     // descendants when we come across a previously seen entry.
 120     cacheMap mapMemPoolDescendantsToUpdate;
 121
 122     // Use a set for lookups into vHashesToUpdate (these entries are already
 123     // accounted for in the state of their ancestors)
 124     std::set<uint256> setAlreadyIncluded(vHashesToUpdate.begin(), vHashesToUpdate.end());
 125
 126     // Iterate in reverse, so that whenever we are looking at a transaction
 127     // we are sure that all in-mempool descendants have already been processed.
 128     // This maximizes the benefit of the descendant cache and guarantees that
 129     // setMemPoolChildren will be updated, an assumption made in
 130     // UpdateForDescendants.
 131     for (const uint256 &hash : reverse_iterate(vHashesToUpdate)) {
 132         // we cache the in-mempool children to avoid duplicate updates
 133         setEntries setChildren;
 134         // calculate children from mapNextTx
 135         txiter it = mapTx.find(hash);
 136         if (it == mapTx.end()) {
 137             continue;
 138         }
 139         auto iter = mapNextTx.lower_bound(COutPoint(hash, 0));
 140         // First calculate the children, and update setMemPoolChildren to
 141         // include them, and update their setMemPoolParents to include this tx.
 142         for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
 143             const uint256 &childHash = iter->second->GetHash();
 144             txiter childIter = mapTx.find(childHash);
 145             assert(childIter != mapTx.end());
 146             // We can skip updating entries we've encountered before or that
 147             // are in the block (which are already accounted for).
 148             if (setChildren.insert(childIter).second && !setAlreadyIncluded.count(childHash)) {
 149                 UpdateChild(it, childIter, true);
 150                 UpdateParent(childIter, it, true);
 151             }
 152         }
 153         UpdateForDescendants(it, mapMemPoolDescendantsToUpdate, setAlreadyIncluded);
 154     }
 155 }
 156
 157 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
 158 {
 159     LOCK(cs);
 160
 161     setEntries parentHashes;
 162     const CTransaction &tx = entry.GetTx();
 163
 164     if (fSearchForParents) {
 165         // Get parents of this transaction that are in the mempool
 166         // GetMemPoolParents() is only valid for entries in the mempool, so we
 167         // iterate mapTx to find parents.
 168         for (unsigned int i = 0; i < tx.vin.size(); i++) {
 169             txiter piter = mapTx.find(tx.vin[i].prevout.hash);
 170             if (piter != mapTx.end()) {
 171                 parentHashes.insert(piter);
 172                 if (parentHashes.size() + 1 > limitAncestorCount) {
 173                     errString = strprintf("too many unconfirmed parents [limit: %u]", limitAncestorCount);
 174                     return false;
 175                 }
 176             }
 177         }
 178     } else {
 179         // If we're not searching for parents, we require this to be an
 180         // entry in the mempool already.
 181         txiter it = mapTx.iterator_to(entry);
 182         parentHashes = GetMemPoolParents(it);
 183     }
 184
 185     size_t totalSizeWithAncestors = entry.GetTxSize();
 186
 187     while (!parentHashes.empty()) {
 188         txiter stageit = *parentHashes.begin();
 189
 190         setAncestors.insert(stageit);
 191         parentHashes.erase(stageit);
 192         totalSizeWithAncestors += stageit->GetTxSize();
 193
 194         if (stageit->GetSizeWithDescendants() + entry.GetTxSize() > limitDescendantSize) {
 195             errString = strprintf("exceeds descendant size limit for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantSize);
 196             return false;
 197         } else if (stageit->GetCountWithDescendants() + 1 > limitDescendantCount) {
 198             errString = strprintf("too many descendants for tx %s [limit: %u]", stageit->GetTx().GetHash().ToString(), limitDescendantCount);
 199             return false;
 200         } else if (totalSizeWithAncestors > limitAncestorSize) {
 201             errString = strprintf("exceeds ancestor size limit [limit: %u]", limitAncestorSize);
 202             return false;
 203         }
 204
 205         const setEntries & setMemPoolParents = GetMemPoolParents(stageit);
 206         for (const txiter &phash : setMemPoolParents) {
 207             // If this is a new ancestor, add it.
 208             if (setAncestors.count(phash) == 0) {
 209                 parentHashes.insert(phash);
 210             }
 211             if (parentHashes.size() + setAncestors.size() + 1 > limitAncestorCount) {
 212                 errString = strprintf("too many unconfirmed ancestors [limit: %u]", limitAncestorCount);
 213                 return false;
 214             }
 215         }
 216     }
 217
 218     return true;
 219 }
 220
 221 void CTxMemPool::UpdateAncestorsOf(bool add, txiter it, setEntries &setAncestors)
 222 {
 223     setEntries parentIters = GetMemPoolParents(it);
 224     // add or remove this tx as a child of each parent
 225     for (txiter piter : parentIters) {
 226         UpdateChild(piter, it, add);
 227     }
 228     const int64_t updateCount = (add ? 1 : -1);
 229     const int64_t updateSize = updateCount * it->GetTxSize();
 230     const CAmount updateFee = updateCount * it->GetModifiedFee();
 231     for (txiter ancestorIt : setAncestors) {
 232         mapTx.modify(ancestorIt, update_descendant_state(updateSize, updateFee, updateCount));
 233     }
 234 }
 235
 236 void CTxMemPool::UpdateEntryForAncestors(txiter it, const setEntries &setAncestors)
 237 {
 238     int64_t updateCount = setAncestors.size();
 239     int64_t updateSize = 0;
 240     CAmount updateFee = 0;
 241     int64_t updateSigOpsCost = 0;
 242     for (txiter ancestorIt : setAncestors) {
 243         updateSize += ancestorIt->GetTxSize();
 244         updateFee += ancestorIt->GetModifiedFee();
 245         updateSigOpsCost += ancestorIt->GetSigOpCost();
 246     }
 247     mapTx.modify(it, update_ancestor_state(updateSize, updateFee, updateCount, updateSigOpsCost));
 248 }
 249
 250 void CTxMemPool::UpdateChildrenForRemoval(txiter it)
 251 {
 252     const setEntries &setMemPoolChildren = GetMemPoolChildren(it);
 253     for (txiter updateIt : setMemPoolChildren) {
 254         UpdateParent(updateIt, it, false);
 255     }
 256 }
 257
 258 void CTxMemPool::UpdateForRemoveFromMempool(const setEntries &entriesToRemove, bool updateDescendants)
 259 {
 260     // For each entry, walk back all ancestors and decrement size associated with this
 261     // transaction
 262     const uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
 263     if (updateDescendants) {
 264         // updateDescendants should be true whenever we're not recursively
 265         // removing a tx and all its descendants, eg when a transaction is
 266         // confirmed in a block.
 267         // Here we only update statistics and not data in mapLinks (which
 268         // we need to preserve until we're finished with all operations that
 269         // need to traverse the mempool).
 270         for (txiter removeIt : entriesToRemove) {
 271             setEntries setDescendants;
 272             CalculateDescendants(removeIt, setDescendants);
 273             setDescendants.erase(removeIt); // don't update state for self
 274             int64_t modifySize = -((int64_t)removeIt->GetTxSize());
 275             CAmount modifyFee = -removeIt->GetModifiedFee();
 276             int modifySigOps = -removeIt->GetSigOpCost();
 277             for (txiter dit : setDescendants) {
 278                 mapTx.modify(dit, update_ancestor_state(modifySize, modifyFee, -1, modifySigOps));
 279             }
 280         }
 281     }
 282     for (txiter removeIt : entriesToRemove) {
 283         setEntries setAncestors;
 284         const CTxMemPoolEntry &entry = *removeIt;
 285         std::string dummy;
 286         // Since this is a tx that is already in the mempool, we can call CMPA
 287         // with fSearchForParents = false.  If the mempool is in a consistent
 288         // state, then using true or false should both be correct, though false
 289         // should be a bit faster.
 290         // However, if we happen to be in the middle of processing a reorg, then
 291         // the mempool can be in an inconsistent state.  In this case, the set
 292         // of ancestors reachable via mapLinks will be the same as the set of
 293         // ancestors whose packages include this transaction, because when we
 294         // add a new transaction to the mempool in addUnchecked(), we assume it
 295         // has no children, and in the case of a reorg where that assumption is
 296         // false, the in-mempool children aren't linked to the in-block tx's
 297         // until UpdateTransactionsFromBlock() is called.
 298         // So if we're being called during a reorg, ie before
 299         // UpdateTransactionsFromBlock() has been called, then mapLinks[] will
 300         // differ from the set of mempool parents we'd calculate by searching,
 301         // and it's important that we use the mapLinks[] notion of ancestor
 302         // transactions as the set of things to update for removal.
 303         CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false);
 304         // Note that UpdateAncestorsOf severs the child links that point to
 305         // removeIt in the entries for the parents of removeIt.
 306         UpdateAncestorsOf(false, removeIt, setAncestors);
 307     }
 308     // After updating all the ancestor sizes, we can now sever the link between each
 309     // transaction being removed and any mempool children (ie, update setMemPoolParents
 310     // for each direct child of a transaction being removed).
 311     for (txiter removeIt : entriesToRemove) {
 312         UpdateChildrenForRemoval(removeIt);
 313     }
 314 }
 315
 316 void CTxMemPoolEntry::UpdateDescendantState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount)
 317 {
 318     nSizeWithDescendants += modifySize;
 319     assert(int64_t(nSizeWithDescendants) > 0);
 320     nModFeesWithDescendants += modifyFee;
 321     nCountWithDescendants += modifyCount;
 322     assert(int64_t(nCountWithDescendants) > 0);
 323 }
 324
 325 void CTxMemPoolEntry::UpdateAncestorState(int64_t modifySize, CAmount modifyFee, int64_t modifyCount, int modifySigOps)
 326 {
 327     nSizeWithAncestors += modifySize;
 328     assert(int64_t(nSizeWithAncestors) > 0);
 329     nModFeesWithAncestors += modifyFee;
 330     nCountWithAncestors += modifyCount;
 331     assert(int64_t(nCountWithAncestors) > 0);
 332     nSigOpCostWithAncestors += modifySigOps;
 333     assert(int(nSigOpCostWithAncestors) >= 0);
 334 }
 335
 336 CTxMemPool::CTxMemPool(CBlockPolicyEstimator* estimator) :
 337     nTransactionsUpdated(0), minerPolicyEstimator(estimator)
 338 {
 339     _clear(); //lock free clear
 340
 341     // Sanity checks off by default for performance, because otherwise
 342     // accepting transactions becomes O(N^2) where N is the number
 343     // of transactions in the pool
 344     nCheckFrequency = 0;
 345 }
 346
 347 bool CTxMemPool::isSpent(const COutPoint& outpoint)
 348 {
 349     LOCK(cs);
 350     return mapNextTx.count(outpoint);
 351 }
 352
 353 unsigned int CTxMemPool::GetTransactionsUpdated() const
 354 {
 355     LOCK(cs);
 356     return nTransactionsUpdated;
 357 }
 358
 359 void CTxMemPool::AddTransactionsUpdated(unsigned int n)
 360 {
 361     LOCK(cs);
 362     nTransactionsUpdated += n;
 363 }
 364
 365 bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, setEntries &setAncestors, bool validFeeEstimate)
 366 {
 367     NotifyEntryAdded(entry.GetSharedTx());
 368     // Add to memory pool without checking anything.
 369     // Used by AcceptToMemoryPool(), which DOES do
 370     // all the appropriate checks.
 371     LOCK(cs);
 372     indexed_transaction_set::iterator newit = mapTx.insert(entry).first;
 373     mapLinks.insert(make_pair(newit, TxLinks()));
 374
 375     // Update transaction for any feeDelta created by PrioritiseTransaction
 376     // TODO: refactor so that the fee delta is calculated before inserting
 377     // into mapTx.
 378     std::map<uint256, CAmount>::const_iterator pos = mapDeltas.find(hash);
 379     if (pos != mapDeltas.end()) {
 380         const CAmount &delta = pos->second;
 381         if (delta) {
 382             mapTx.modify(newit, update_fee_delta(delta));
 383         }
 384     }
 385
 386     // Update cachedInnerUsage to include contained transaction's usage.
 387     // (When we update the entry for in-mempool parents, memory usage will be
 388     // further updated.)
 389     cachedInnerUsage += entry.DynamicMemoryUsage();
 390
 391     const CTransaction& tx = newit->GetTx();
 392     std::set<uint256> setParentTransactions;
 393     for (unsigned int i = 0; i < tx.vin.size(); i++) {
 394         mapNextTx.insert(std::make_pair(&tx.vin[i].prevout, &tx));
 395         setParentTransactions.insert(tx.vin[i].prevout.hash);
 396     }
 397     // Don't bother worrying about child transactions of this one.
 398     // Normal case of a new transaction arriving is that there can't be any
 399     // children, because such children would be orphans.
 400     // An exception to that is if a transaction enters that used to be in a block.
 401     // In that case, our disconnect block logic will call UpdateTransactionsFromBlock
 402     // to clean up the mess we're leaving here.
 403
 404     // Update ancestors with information about this tx
 405     for (const uint256 &phash : setParentTransactions) {
 406         txiter pit = mapTx.find(phash);
 407         if (pit != mapTx.end()) {
 408             UpdateParent(newit, pit, true);
 409         }
 410     }
 411     UpdateAncestorsOf(true, newit, setAncestors);
 412     UpdateEntryForAncestors(newit, setAncestors);
 413
 414     nTransactionsUpdated++;
 415     totalTxSize += entry.GetTxSize();
 416     if (minerPolicyEstimator) {minerPolicyEstimator->processTransaction(entry, validFeeEstimate);}
 417
 418     vTxHashes.emplace_back(tx.GetWitnessHash(), newit);
 419     newit->vTxHashesIdx = vTxHashes.size() - 1;
 420
 421     return true;
 422 }
 423
 424 void CTxMemPool::removeUnchecked(txiter it, MemPoolRemovalReason reason)
 425 {
 426     NotifyEntryRemoved(it->GetSharedTx(), reason);
 427     const uint256 hash = it->GetTx().GetHash();
 428     for (const CTxIn& txin : it->GetTx().vin)
 429         mapNextTx.erase(txin.prevout);
 430
 431     if (vTxHashes.size() > 1) {
 432         vTxHashes[it->vTxHashesIdx] = std::move(vTxHashes.back());
 433         vTxHashes[it->vTxHashesIdx].second->vTxHashesIdx = it->vTxHashesIdx;
 434         vTxHashes.pop_back();
 435         if (vTxHashes.size() * 2 < vTxHashes.capacity())
 436             vTxHashes.shrink_to_fit();
 437     } else
 438         vTxHashes.clear();
 439
 440     totalTxSize -= it->GetTxSize();
 441     cachedInnerUsage -= it->DynamicMemoryUsage();
 442     cachedInnerUsage -= memusage::DynamicUsage(mapLinks[it].parents) + memusage::DynamicUsage(mapLinks[it].children);
 443     mapLinks.erase(it);
 444     mapTx.erase(it);
 445     nTransactionsUpdated++;
 446     if (minerPolicyEstimator) {minerPolicyEstimator->removeTx(hash, false);}
 447 }
 448
 449 // Calculates descendants of entry that are not already in setDescendants, and adds to
 450 // setDescendants. Assumes entryit is already a tx in the mempool and setMemPoolChildren
 451 // is correct for tx and all descendants.
 452 // Also assumes that if an entry is in setDescendants already, then all
 453 // in-mempool descendants of it are already in setDescendants as well, so that we
 454 // can save time by not iterating over those entries.
 455 void CTxMemPool::CalculateDescendants(txiter entryit, setEntries &setDescendants)
 456 {
 457     setEntries stage;
 458     if (setDescendants.count(entryit) == 0) {
 459         stage.insert(entryit);
 460     }
 461     // Traverse down the children of entry, only adding children that are not
 462     // accounted for in setDescendants already (because those children have either
 463     // already been walked, or will be walked in this iteration).
 464     while (!stage.empty()) {
 465         txiter it = *stage.begin();
 466         setDescendants.insert(it);
 467         stage.erase(it);
 468
 469         const setEntries &setChildren = GetMemPoolChildren(it);
 470         for (const txiter &childiter : setChildren) {
 471             if (!setDescendants.count(childiter)) {
 472                 stage.insert(childiter);
 473             }
 474         }
 475     }
 476 }
 477
 478 void CTxMemPool::removeRecursive(const CTransaction &origTx, MemPoolRemovalReason reason)
 479 {
 480     // Remove transaction from memory pool
 481     {
 482         LOCK(cs);
 483         setEntries txToRemove;
 484         txiter origit = mapTx.find(origTx.GetHash());
 485         if (origit != mapTx.end()) {
 486             txToRemove.insert(origit);
 487         } else {
 488             // When recursively removing but origTx isn't in the mempool
 489             // be sure to remove any children that are in the pool. This can
 490             // happen during chain re-orgs if origTx isn't re-accepted into
 491             // the mempool for any reason.
 492             for (unsigned int i = 0; i < origTx.vout.size(); i++) {
 493                 auto it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
 494                 if (it == mapNextTx.end())
 495                     continue;
 496                 txiter nextit = mapTx.find(it->second->GetHash());
 497                 assert(nextit != mapTx.end());
 498                 txToRemove.insert(nextit);
 499             }
 500         }
 501         setEntries setAllRemoves;
 502         for (txiter it : txToRemove) {
 503             CalculateDescendants(it, setAllRemoves);
 504         }
 505
 506         RemoveStaged(setAllRemoves, false, reason);
 507     }
 508 }
 509
 510 void CTxMemPool::removeForReorg(const CCoinsViewCache *pcoins, unsigned int nMemPoolHeight, int flags)
 511 {
 512     // Remove transactions spending a coinbase which are now immature and no-longer-final transactions
 513     LOCK(cs);
 514     setEntries txToRemove;
 515     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 516         const CTransaction& tx = it->GetTx();
 517         LockPoints lp = it->GetLockPoints();
 518         bool validLP =  TestLockPointValidity(&lp);
 519         if (!CheckFinalTx(tx, flags) || !CheckSequenceLocks(tx, flags, &lp, validLP)) {
 520             // Note if CheckSequenceLocks fails the LockPoints may still be invalid
 521             // So it's critical that we remove the tx and not depend on the LockPoints.
 522             txToRemove.insert(it);
 523         } else if (it->GetSpendsCoinbase()) {
 524             for (const CTxIn& txin : tx.vin) {
 525                 indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
 526                 if (it2 != mapTx.end())
 527                     continue;
 528                 const Coin &coin = pcoins->AccessCoin(txin.prevout);
 529                 if (nCheckFrequency != 0) assert(!coin.IsSpent());
 530                 if (coin.IsSpent() || (coin.IsCoinBase() && ((signed long)nMemPoolHeight) - coin.nHeight < COINBASE_MATURITY)) {
 531                     txToRemove.insert(it);
 532                     break;
 533                 }
 534             }
 535         }
 536         if (!validLP) {
 537             mapTx.modify(it, update_lock_points(lp));
 538         }
 539     }
 540     setEntries setAllRemoves;
 541     for (txiter it : txToRemove) {
 542         CalculateDescendants(it, setAllRemoves);
 543     }
 544     RemoveStaged(setAllRemoves, false, MemPoolRemovalReason::REORG);
 545 }
 546
 547 void CTxMemPool::removeConflicts(const CTransaction &tx)
 548 {
 549     // Remove transactions which depend on inputs of tx, recursively
 550     LOCK(cs);
 551     for (const CTxIn &txin : tx.vin) {
 552         auto it = mapNextTx.find(txin.prevout);
 553         if (it != mapNextTx.end()) {
 554             const CTransaction &txConflict = *it->second;
 555             if (txConflict != tx)
 556             {
 557                 ClearPrioritisation(txConflict.GetHash());
 558                 removeRecursive(txConflict, MemPoolRemovalReason::CONFLICT);
 559             }
 560         }
 561     }
 562 }
 563
 564 /**
 565  * Called when a block is connected. Removes from mempool and updates the miner fee estimator.
 566  */
 567 void CTxMemPool::removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight)
 568 {
 569     LOCK(cs);
 570     std::vector<const CTxMemPoolEntry*> entries;
 571     for (const auto& tx : vtx)
 572     {
 573         uint256 hash = tx->GetHash();
 574
 575         indexed_transaction_set::iterator i = mapTx.find(hash);
 576         if (i != mapTx.end())
 577             entries.push_back(&*i);
 578     }
 579     // Before the txs in the new block have been removed from the mempool, update policy estimates
 580     if (minerPolicyEstimator) {minerPolicyEstimator->processBlock(nBlockHeight, entries);}
 581     for (const auto& tx : vtx)
 582     {
 583         txiter it = mapTx.find(tx->GetHash());
 584         if (it != mapTx.end()) {
 585             setEntries stage;
 586             stage.insert(it);
 587             RemoveStaged(stage, true, MemPoolRemovalReason::BLOCK);
 588         }
 589         removeConflicts(*tx);
 590         ClearPrioritisation(tx->GetHash());
 591     }
 592     lastRollingFeeUpdate = GetTime();
 593     blockSinceLastRollingFeeBump = true;
 594 }
 595
 596 void CTxMemPool::_clear()
 597 {
 598     mapLinks.clear();
 599     mapTx.clear();
 600     mapNextTx.clear();
 601     totalTxSize = 0;
 602     cachedInnerUsage = 0;
 603     lastRollingFeeUpdate = GetTime();
 604     blockSinceLastRollingFeeBump = false;
 605     rollingMinimumFeeRate = 0;
 606     ++nTransactionsUpdated;
 607 }
 608
 609 void CTxMemPool::clear()
 610 {
 611     LOCK(cs);
 612     _clear();
 613 }
 614
 615 void CTxMemPool::check(const CCoinsViewCache *pcoins) const
 616 {
 617     if (nCheckFrequency == 0)
 618         return;
 619
 620     if (GetRand(std::numeric_limits<uint32_t>::max()) >= nCheckFrequency)
 621         return;
 622
 623     LogPrint(BCLog::MEMPOOL, "Checking mempool with %u transactions and %u inputs\n", (unsigned int)mapTx.size(), (unsigned int)mapNextTx.size());
 624
 625     uint64_t checkTotal = 0;
 626     uint64_t innerUsage = 0;
 627
 628     CCoinsViewCache mempoolDuplicate(const_cast<CCoinsViewCache*>(pcoins));
 629     const int64_t nSpendHeight = GetSpendHeight(mempoolDuplicate);
 630
 631     LOCK(cs);
 632     std::list<const CTxMemPoolEntry*> waitingOnDependants;
 633     for (indexed_transaction_set::const_iterator it = mapTx.begin(); it != mapTx.end(); it++) {
 634         unsigned int i = 0;
 635         checkTotal += it->GetTxSize();
 636         innerUsage += it->DynamicMemoryUsage();
 637         const CTransaction& tx = it->GetTx();
 638         txlinksMap::const_iterator linksiter = mapLinks.find(it);
 639         assert(linksiter != mapLinks.end());
 640         const TxLinks &links = linksiter->second;
 641         innerUsage += memusage::DynamicUsage(links.parents) + memusage::DynamicUsage(links.children);
 642         bool fDependsWait = false;
 643         setEntries setParentCheck;
 644         int64_t parentSizes = 0;
 645         int64_t parentSigOpCost = 0;
 646         for (const CTxIn &txin : tx.vin) {
 647             // Check that every mempool transaction's inputs refer to available coins, or other mempool tx's.
 648             indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
 649             if (it2 != mapTx.end()) {
 650                 const CTransaction& tx2 = it2->GetTx();
 651                 assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
 652                 fDependsWait = true;
 653                 if (setParentCheck.insert(it2).second) {
 654                     parentSizes += it2->GetTxSize();
 655                     parentSigOpCost += it2->GetSigOpCost();
 656                 }
 657             } else {
 658                 assert(pcoins->HaveCoin(txin.prevout));
 659             }
 660             // Check whether its inputs are marked in mapNextTx.
 661             auto it3 = mapNextTx.find(txin.prevout);
 662             assert(it3 != mapNextTx.end());
 663             assert(it3->first == &txin.prevout);
 664             assert(it3->second == &tx);
 665             i++;
 666         }
 667         assert(setParentCheck == GetMemPoolParents(it));
 668         // Verify ancestor state is correct.
 669         setEntries setAncestors;
 670         uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
 671         std::string dummy;
 672         CalculateMemPoolAncestors(*it, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy);
 673         uint64_t nCountCheck = setAncestors.size() + 1;
 674         uint64_t nSizeCheck = it->GetTxSize();
 675         CAmount nFeesCheck = it->GetModifiedFee();
 676         int64_t nSigOpCheck = it->GetSigOpCost();
 677
 678         for (txiter ancestorIt : setAncestors) {
 679             nSizeCheck += ancestorIt->GetTxSize();
 680             nFeesCheck += ancestorIt->GetModifiedFee();
 681             nSigOpCheck += ancestorIt->GetSigOpCost();
 682         }
 683
 684         assert(it->GetCountWithAncestors() == nCountCheck);
 685         assert(it->GetSizeWithAncestors() == nSizeCheck);
 686         assert(it->GetSigOpCostWithAncestors() == nSigOpCheck);
 687         assert(it->GetModFeesWithAncestors() == nFeesCheck);
 688
 689         // Check children against mapNextTx
 690         CTxMemPool::setEntries setChildrenCheck;
 691         auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
 692         int64_t childSizes = 0;
 693         for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetHash(); ++iter) {
 694             txiter childit = mapTx.find(iter->second->GetHash());
 695             assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
 696             if (setChildrenCheck.insert(childit).second) {
 697                 childSizes += childit->GetTxSize();
 698             }
 699         }
 700         assert(setChildrenCheck == GetMemPoolChildren(it));
 701         // Also check to make sure size is greater than sum with immediate children.
 702         // just a sanity check, not definitive that this calc is correct...
 703         assert(it->GetSizeWithDescendants() >= childSizes + it->GetTxSize());
 704
 705         if (fDependsWait)
 706             waitingOnDependants.push_back(&(*it));
 707         else {
 708             CValidationState state;
 709             bool fCheckResult = tx.IsCoinBase() ||
 710                 Consensus::CheckTxInputs(tx, state, mempoolDuplicate, nSpendHeight);
 711             assert(fCheckResult);
 712             UpdateCoins(tx, mempoolDuplicate, 1000000);
 713         }
 714     }
 715     unsigned int stepsSinceLastRemove = 0;
 716     while (!waitingOnDependants.empty()) {
 717         const CTxMemPoolEntry* entry = waitingOnDependants.front();
 718         waitingOnDependants.pop_front();
 719         CValidationState state;
 720         if (!mempoolDuplicate.HaveInputs(entry->GetTx())) {
 721             waitingOnDependants.push_back(entry);
 722             stepsSinceLastRemove++;
 723             assert(stepsSinceLastRemove < waitingOnDependants.size());
 724         } else {
 725             bool fCheckResult = entry->GetTx().IsCoinBase() ||
 726                 Consensus::CheckTxInputs(entry->GetTx(), state, mempoolDuplicate, nSpendHeight);
 727             assert(fCheckResult);
 728             UpdateCoins(entry->GetTx(), mempoolDuplicate, 1000000);
 729             stepsSinceLastRemove = 0;
 730         }
 731     }
 732     for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) {
 733         uint256 hash = it->second->GetHash();
 734         indexed_transaction_set::const_iterator it2 = mapTx.find(hash);
 735         const CTransaction& tx = it2->GetTx();
 736         assert(it2 != mapTx.end());
 737         assert(&tx == it->second);
 738     }
 739
 740     assert(totalTxSize == checkTotal);
 741     assert(innerUsage == cachedInnerUsage);
 742 }
 743
 744 bool CTxMemPool::CompareDepthAndScore(const uint256& hasha, const uint256& hashb)
 745 {
 746     LOCK(cs);
 747     indexed_transaction_set::const_iterator i = mapTx.find(hasha);
 748     if (i == mapTx.end()) return false;
 749     indexed_transaction_set::const_iterator j = mapTx.find(hashb);
 750     if (j == mapTx.end()) return true;
 751     uint64_t counta = i->GetCountWithAncestors();
 752     uint64_t countb = j->GetCountWithAncestors();
 753     if (counta == countb) {
 754         return CompareTxMemPoolEntryByScore()(*i, *j);
 755     }
 756     return counta < countb;
 757 }
 758
 759 namespace {
 760 class DepthAndScoreComparator
 761 {
 762 public:
 763     bool operator()(const CTxMemPool::indexed_transaction_set::const_iterator& a, const CTxMemPool::indexed_transaction_set::const_iterator& b)
 764     {
 765         uint64_t counta = a->GetCountWithAncestors();
 766         uint64_t countb = b->GetCountWithAncestors();
 767         if (counta == countb) {
 768             return CompareTxMemPoolEntryByScore()(*a, *b);
 769         }
 770         return counta < countb;
 771     }
 772 };
 773 } // namespace
 774
 775 std::vector<CTxMemPool::indexed_transaction_set::const_iterator> CTxMemPool::GetSortedDepthAndScore() const
 776 {
 777     std::vector<indexed_transaction_set::const_iterator> iters;
 778     AssertLockHeld(cs);
 779
 780     iters.reserve(mapTx.size());
 781
 782     for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) {
 783         iters.push_back(mi);
 784     }
 785     std::sort(iters.begin(), iters.end(), DepthAndScoreComparator());
 786     return iters;
 787 }
 788
 789 void CTxMemPool::queryHashes(std::vector<uint256>& vtxid)
 790 {
 791     LOCK(cs);
 792     auto iters = GetSortedDepthAndScore();
 793
 794     vtxid.clear();
 795     vtxid.reserve(mapTx.size());
 796
 797     for (auto it : iters) {
 798         vtxid.push_back(it->GetTx().GetHash());
 799     }
 800 }
 801
 802 static TxMempoolInfo GetInfo(CTxMemPool::indexed_transaction_set::const_iterator it) {
 803     return TxMempoolInfo{it->GetSharedTx(), it->GetTime(), CFeeRate(it->GetFee(), it->GetTxSize()), it->GetModifiedFee() - it->GetFee()};
 804 }
 805
 806 std::vector<TxMempoolInfo> CTxMemPool::infoAll() const
 807 {
 808     LOCK(cs);
 809     auto iters = GetSortedDepthAndScore();
 810
 811     std::vector<TxMempoolInfo> ret;
 812     ret.reserve(mapTx.size());
 813     for (auto it : iters) {
 814         ret.push_back(GetInfo(it));
 815     }
 816
 817     return ret;
 818 }
 819
 820 CTransactionRef CTxMemPool::get(const uint256& hash) const
 821 {
 822     LOCK(cs);
 823     indexed_transaction_set::const_iterator i = mapTx.find(hash);
 824     if (i == mapTx.end())
 825         return nullptr;
 826     return i->GetSharedTx();
 827 }
 828
 829 TxMempoolInfo CTxMemPool::info(const uint256& hash) const
 830 {
 831     LOCK(cs);
 832     indexed_transaction_set::const_iterator i = mapTx.find(hash);
 833     if (i == mapTx.end())
 834         return TxMempoolInfo();
 835     return GetInfo(i);
 836 }
 837
 838 void CTxMemPool::PrioritiseTransaction(const uint256& hash, const CAmount& nFeeDelta)
 839 {
 840     {
 841         LOCK(cs);
 842         CAmount &delta = mapDeltas[hash];
 843         delta += nFeeDelta;
 844         txiter it = mapTx.find(hash);
 845         if (it != mapTx.end()) {
 846             mapTx.modify(it, update_fee_delta(delta));
 847             // Now update all ancestors' modified fees with descendants
 848             setEntries setAncestors;
 849             uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
 850             std::string dummy;
 851             CalculateMemPoolAncestors(*it, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy, false);
 852             for (txiter ancestorIt : setAncestors) {
 853                 mapTx.modify(ancestorIt, update_descendant_state(0, nFeeDelta, 0));
 854             }
 855             // Now update all descendants' modified fees with ancestors
 856             setEntries setDescendants;
 857             CalculateDescendants(it, setDescendants);
 858             setDescendants.erase(it);
 859             for (txiter descendantIt : setDescendants) {
 860                 mapTx.modify(descendantIt, update_ancestor_state(0, nFeeDelta, 0, 0));
 861             }
 862             ++nTransactionsUpdated;
 863         }
 864     }
 865     LogPrintf("PrioritiseTransaction: %s feerate += %s\n", hash.ToString(), FormatMoney(nFeeDelta));
 866 }
 867
 868 void CTxMemPool::ApplyDelta(const uint256 hash, CAmount &nFeeDelta) const
 869 {
 870     LOCK(cs);
 871     std::map<uint256, CAmount>::const_iterator pos = mapDeltas.find(hash);
 872     if (pos == mapDeltas.end())
 873         return;
 874     const CAmount &delta = pos->second;
 875     nFeeDelta += delta;
 876 }
 877
 878 void CTxMemPool::ClearPrioritisation(const uint256 hash)
 879 {
 880     LOCK(cs);
 881     mapDeltas.erase(hash);
 882 }
 883
 884 bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const
 885 {
 886     for (unsigned int i = 0; i < tx.vin.size(); i++)
 887         if (exists(tx.vin[i].prevout.hash))
 888             return false;
 889     return true;
 890 }
 891
 892 CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
 893
 894 bool CCoinsViewMemPool::GetCoin(const COutPoint &outpoint, Coin &coin) const {
 895     // If an entry in the mempool exists, always return that one, as it's guaranteed to never
 896     // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
 897     // transactions. First checking the underlying cache risks returning a pruned entry instead.
 898     CTransactionRef ptx = mempool.get(outpoint.hash);
 899     if (ptx) {
 900         if (outpoint.n < ptx->vout.size()) {
 901             coin = Coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false);
 902             return true;
 903         } else {
 904             return false;
 905         }
 906     }
 907     return base->GetCoin(outpoint, coin);
 908 }
 909
 910 size_t CTxMemPool::DynamicMemoryUsage() const {
 911     LOCK(cs);
 912     // Estimate the overhead of mapTx to be 15 pointers + an allocation, as no exact formula for boost::multi_index_contained is implemented.
 913     return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 15 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(mapLinks) + memusage::DynamicUsage(vTxHashes) + cachedInnerUsage;
 914 }
 915
 916 void CTxMemPool::RemoveStaged(setEntries &stage, bool updateDescendants, MemPoolRemovalReason reason) {
 917     AssertLockHeld(cs);
 918     UpdateForRemoveFromMempool(stage, updateDescendants);
 919     for (const txiter& it : stage) {
 920         removeUnchecked(it, reason);
 921     }
 922 }
 923
 924 int CTxMemPool::Expire(int64_t time) {
 925     LOCK(cs);
 926     indexed_transaction_set::index<entry_time>::type::iterator it = mapTx.get<entry_time>().begin();
 927     setEntries toremove;
 928     while (it != mapTx.get<entry_time>().end() && it->GetTime() < time) {
 929         toremove.insert(mapTx.project<0>(it));
 930         it++;
 931     }
 932     setEntries stage;
 933     for (txiter removeit : toremove) {
 934         CalculateDescendants(removeit, stage);
 935     }
 936     RemoveStaged(stage, false, MemPoolRemovalReason::EXPIRY);
 937     return stage.size();
 938 }
 939
 940 bool CTxMemPool::addUnchecked(const uint256&hash, const CTxMemPoolEntry &entry, bool validFeeEstimate)
 941 {
 942     LOCK(cs);
 943     setEntries setAncestors;
 944     uint64_t nNoLimit = std::numeric_limits<uint64_t>::max();
 945     std::string dummy;
 946     CalculateMemPoolAncestors(entry, setAncestors, nNoLimit, nNoLimit, nNoLimit, nNoLimit, dummy);
 947     return addUnchecked(hash, entry, setAncestors, validFeeEstimate);
 948 }
 949
 950 void CTxMemPool::UpdateChild(txiter entry, txiter child, bool add)
 951 {
 952     setEntries s;
 953     if (add && mapLinks[entry].children.insert(child).second) {
 954         cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
 955     } else if (!add && mapLinks[entry].children.erase(child)) {
 956         cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
 957     }
 958 }
 959
 960 void CTxMemPool::UpdateParent(txiter entry, txiter parent, bool add)
 961 {
 962     setEntries s;
 963     if (add && mapLinks[entry].parents.insert(parent).second) {
 964         cachedInnerUsage += memusage::IncrementalDynamicUsage(s);
 965     } else if (!add && mapLinks[entry].parents.erase(parent)) {
 966         cachedInnerUsage -= memusage::IncrementalDynamicUsage(s);
 967     }
 968 }
 969
 970 const CTxMemPool::setEntries & CTxMemPool::GetMemPoolParents(txiter entry) const
 971 {
 972     assert (entry != mapTx.end());
 973     txlinksMap::const_iterator it = mapLinks.find(entry);
 974     assert(it != mapLinks.end());
 975     return it->second.parents;
 976 }
 977
 978 const CTxMemPool::setEntries & CTxMemPool::GetMemPoolChildren(txiter entry) const
 979 {
 980     assert (entry != mapTx.end());
 981     txlinksMap::const_iterator it = mapLinks.find(entry);
 982     assert(it != mapLinks.end());
 983     return it->second.children;
 984 }
 985
 986 CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const {
 987     LOCK(cs);
 988     if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0)
 989         return CFeeRate(rollingMinimumFeeRate);
 990
 991     int64_t time = GetTime();
 992     if (time > lastRollingFeeUpdate + 10) {
 993         double halflife = ROLLING_FEE_HALFLIFE;
 994         if (DynamicMemoryUsage() < sizelimit / 4)
 995             halflife /= 4;
 996         else if (DynamicMemoryUsage() < sizelimit / 2)
 997             halflife /= 2;
 998
 999         rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife);
1000         lastRollingFeeUpdate = time;
1001
1002         if (rollingMinimumFeeRate < (double)incrementalRelayFee.GetFeePerK() / 2) {
1003             rollingMinimumFeeRate = 0;
1004             return CFeeRate(0);
1005         }
1006     }
1007     return std::max(CFeeRate(rollingMinimumFeeRate), incrementalRelayFee);
1008 }
1009
1010 void CTxMemPool::trackPackageRemoved(const CFeeRate& rate) {
1011     AssertLockHeld(cs);
1012     if (rate.GetFeePerK() > rollingMinimumFeeRate) {
1013         rollingMinimumFeeRate = rate.GetFeePerK();
1014         blockSinceLastRollingFeeBump = false;
1015     }
1016 }
1017
1018 void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining) {
1019     LOCK(cs);
1020
1021     unsigned nTxnRemoved = 0;
1022     CFeeRate maxFeeRateRemoved(0);
1023     while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) {
1024         indexed_transaction_set::index<descendant_score>::type::iterator it = mapTx.get<descendant_score>().begin();
1025
1026         // We set the new mempool min fee to the feerate of the removed set, plus the
1027         // "minimum reasonable fee rate" (ie some value under which we consider txn
1028         // to have 0 fee). This way, we don't allow txn to enter mempool with feerate
1029         // equal to txn which were removed with no block in between.
1030         CFeeRate removed(it->GetModFeesWithDescendants(), it->GetSizeWithDescendants());
1031         removed += incrementalRelayFee;
1032         trackPackageRemoved(removed);
1033         maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
1034
1035         setEntries stage;
1036         CalculateDescendants(mapTx.project<0>(it), stage);
1037         nTxnRemoved += stage.size();
1038
1039         std::vector<CTransaction> txn;
1040         if (pvNoSpendsRemaining) {
1041             txn.reserve(stage.size());
1042             for (txiter iter : stage)
1043                 txn.push_back(iter->GetTx());
1044         }
1045         RemoveStaged(stage, false, MemPoolRemovalReason::SIZELIMIT);
1046         if (pvNoSpendsRemaining) {
1047             for (const CTransaction& tx : txn) {
1048                 for (const CTxIn& txin : tx.vin) {
1049                     if (exists(txin.prevout.hash)) continue;
1050                     pvNoSpendsRemaining->push_back(txin.prevout);
1051                 }
1052             }
1053         }
1054     }
1055
1056     if (maxFeeRateRemoved > CFeeRate(0)) {
1057         LogPrint(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString());
1058     }
1059 }
1060
1061 bool CTxMemPool::TransactionWithinChainLimit(const uint256& txid, size_t chainLimit) const {
1062     LOCK(cs);
1063     auto it = mapTx.find(txid);
1064     return it == mapTx.end() || (it->GetCountWithAncestors() < chainLimit &&
1065        it->GetCountWithDescendants() < chainLimit);
1066 }
1067
1068 SaltedTxidHasher::SaltedTxidHasher() : k0(GetRand(std::numeric_limits<uint64_t>::max())), k1(GetRand(std::numeric_limits<uint64_t>::max())) {}