aboutsummaryrefslogtreecommitdiff
path: root/src/txmempool.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/txmempool.cpp')
-rw-r--r--src/txmempool.cpp382
1 files changed, 29 insertions, 353 deletions
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index 85ea3f77b5..53992b80da 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -7,28 +7,27 @@
#include "clientversion.h"
#include "main.h"
+#include "policy/fees.h"
#include "streams.h"
#include "util.h"
#include "utilmoneystr.h"
#include "version.h"
-#include <boost/circular_buffer.hpp>
-
using namespace std;
CTxMemPoolEntry::CTxMemPoolEntry():
- nFee(0), nTxSize(0), nModSize(0), nTime(0), dPriority(0.0)
+ nFee(0), nTxSize(0), nModSize(0), nTime(0), dPriority(0.0), hadNoDependencies(false)
{
nHeight = MEMPOOL_HEIGHT;
}
CTxMemPoolEntry::CTxMemPoolEntry(const CTransaction& _tx, const CAmount& _nFee,
int64_t _nTime, double _dPriority,
- unsigned int _nHeight):
- tx(_tx), nFee(_nFee), nTime(_nTime), dPriority(_dPriority), nHeight(_nHeight)
+ unsigned int _nHeight, bool poolHasNoInputsOf):
+ tx(_tx), nFee(_nFee), nTime(_nTime), dPriority(_dPriority), nHeight(_nHeight),
+ hadNoDependencies(poolHasNoInputsOf)
{
nTxSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION);
-
nModSize = tx.CalculateModifiedSize(nTxSize);
}
@@ -46,346 +45,15 @@ CTxMemPoolEntry::GetPriority(unsigned int currentHeight) const
return dResult;
}
-/**
- * Keep track of fee/priority for transactions confirmed within N blocks
- */
-class CBlockAverage
-{
-private:
- boost::circular_buffer<CFeeRate> feeSamples;
- boost::circular_buffer<double> prioritySamples;
-
- template<typename T> std::vector<T> buf2vec(boost::circular_buffer<T> buf) const
- {
- std::vector<T> vec(buf.begin(), buf.end());
- return vec;
- }
-
-public:
- CBlockAverage() : feeSamples(100), prioritySamples(100) { }
-
- void RecordFee(const CFeeRate& feeRate) {
- feeSamples.push_back(feeRate);
- }
-
- void RecordPriority(double priority) {
- prioritySamples.push_back(priority);
- }
-
- size_t FeeSamples() const { return feeSamples.size(); }
- size_t GetFeeSamples(std::vector<CFeeRate>& insertInto) const
- {
- BOOST_FOREACH(const CFeeRate& f, feeSamples)
- insertInto.push_back(f);
- return feeSamples.size();
- }
- size_t PrioritySamples() const { return prioritySamples.size(); }
- size_t GetPrioritySamples(std::vector<double>& insertInto) const
- {
- BOOST_FOREACH(double d, prioritySamples)
- insertInto.push_back(d);
- return prioritySamples.size();
- }
-
- /**
- * Used as belt-and-suspenders check when reading to detect
- * file corruption
- */
- static bool AreSane(const CFeeRate fee, const CFeeRate& minRelayFee)
- {
- if (fee < CFeeRate(0))
- return false;
- if (fee.GetFeePerK() > minRelayFee.GetFeePerK() * 10000)
- return false;
- return true;
- }
- static bool AreSane(const std::vector<CFeeRate>& vecFee, const CFeeRate& minRelayFee)
- {
- BOOST_FOREACH(CFeeRate fee, vecFee)
- {
- if (!AreSane(fee, minRelayFee))
- return false;
- }
- return true;
- }
- static bool AreSane(const double priority)
- {
- return priority >= 0;
- }
- static bool AreSane(const std::vector<double> vecPriority)
- {
- BOOST_FOREACH(double priority, vecPriority)
- {
- if (!AreSane(priority))
- return false;
- }
- return true;
- }
-
- void Write(CAutoFile& fileout) const
- {
- std::vector<CFeeRate> vecFee = buf2vec(feeSamples);
- fileout << vecFee;
- std::vector<double> vecPriority = buf2vec(prioritySamples);
- fileout << vecPriority;
- }
-
- void Read(CAutoFile& filein, const CFeeRate& minRelayFee) {
- std::vector<CFeeRate> vecFee;
- filein >> vecFee;
- if (AreSane(vecFee, minRelayFee))
- feeSamples.insert(feeSamples.end(), vecFee.begin(), vecFee.end());
- else
- throw runtime_error("Corrupt fee value in estimates file.");
- std::vector<double> vecPriority;
- filein >> vecPriority;
- if (AreSane(vecPriority))
- prioritySamples.insert(prioritySamples.end(), vecPriority.begin(), vecPriority.end());
- else
- throw runtime_error("Corrupt priority value in estimates file.");
- if (feeSamples.size() + prioritySamples.size() > 0)
- LogPrint("estimatefee", "Read %d fee samples and %d priority samples\n",
- feeSamples.size(), prioritySamples.size());
- }
-};
-
-class CMinerPolicyEstimator
-{
-private:
- /**
- * Records observed averages transactions that confirmed within one block, two blocks,
- * three blocks etc.
- */
- std::vector<CBlockAverage> history;
- std::vector<CFeeRate> sortedFeeSamples;
- std::vector<double> sortedPrioritySamples;
-
- int nBestSeenHeight;
-
- /**
- * nBlocksAgo is 0 based, i.e. transactions that confirmed in the highest seen block are
- * nBlocksAgo == 0, transactions in the block before that are nBlocksAgo == 1 etc.
- */
- void seenTxConfirm(const CFeeRate& feeRate, const CFeeRate& minRelayFee, double dPriority, int nBlocksAgo)
- {
- // Last entry records "everything else".
- int nBlocksTruncated = min(nBlocksAgo, (int) history.size() - 1);
- assert(nBlocksTruncated >= 0);
-
- // We need to guess why the transaction was included in a block-- either
- // because it is high-priority or because it has sufficient fees.
- bool sufficientFee = (feeRate > minRelayFee);
- bool sufficientPriority = AllowFree(dPriority);
- const char* assignedTo = "unassigned";
- if (sufficientFee && !sufficientPriority && CBlockAverage::AreSane(feeRate, minRelayFee))
- {
- history[nBlocksTruncated].RecordFee(feeRate);
- assignedTo = "fee";
- }
- else if (sufficientPriority && !sufficientFee && CBlockAverage::AreSane(dPriority))
- {
- history[nBlocksTruncated].RecordPriority(dPriority);
- assignedTo = "priority";
- }
- else
- {
- // Neither or both fee and priority sufficient to get confirmed:
- // don't know why they got confirmed.
- }
- LogPrint("estimatefee", "Seen TX confirm: %s: %s fee/%g priority, took %d blocks\n",
- assignedTo, feeRate.ToString(), dPriority, nBlocksAgo);
- }
-
-public:
- CMinerPolicyEstimator(int nEntries) : nBestSeenHeight(0)
- {
- history.resize(nEntries);
- }
-
- void seenBlock(const std::vector<CTxMemPoolEntry>& entries, int nBlockHeight, const CFeeRate minRelayFee)
- {
- if (nBlockHeight <= nBestSeenHeight)
- {
- // Ignore side chains and re-orgs; assuming they are random
- // they don't affect the estimate.
- // And if an attacker can re-org the chain at will, then
- // you've got much bigger problems than "attacker can influence
- // transaction fees."
- return;
- }
- nBestSeenHeight = nBlockHeight;
-
- // Fill up the history buckets based on how long transactions took
- // to confirm.
- std::vector<std::vector<const CTxMemPoolEntry*> > entriesByConfirmations;
- entriesByConfirmations.resize(history.size());
- BOOST_FOREACH(const CTxMemPoolEntry& entry, entries)
- {
- // How many blocks did it take for miners to include this transaction?
- int delta = nBlockHeight - entry.GetHeight();
- if (delta <= 0)
- {
- // Re-org made us lose height, this should only happen if we happen
- // to re-org on a difficulty transition point: very rare!
- continue;
- }
- if ((delta-1) >= (int)history.size())
- delta = history.size(); // Last bucket is catch-all
- entriesByConfirmations.at(delta-1).push_back(&entry);
- }
- for (size_t i = 0; i < entriesByConfirmations.size(); i++)
- {
- std::vector<const CTxMemPoolEntry*> &e = entriesByConfirmations.at(i);
- // Insert at most 10 random entries per bucket, otherwise a single block
- // can dominate an estimate:
- if (e.size() > 10) {
- std::random_shuffle(e.begin(), e.end());
- e.resize(10);
- }
- BOOST_FOREACH(const CTxMemPoolEntry* entry, e)
- {
- // Fees are stored and reported as BTC-per-kb:
- CFeeRate feeRate(entry->GetFee(), entry->GetTxSize());
- double dPriority = entry->GetPriority(entry->GetHeight()); // Want priority when it went IN
- seenTxConfirm(feeRate, minRelayFee, dPriority, i);
- }
- }
-
- // After new samples are added, we have to clear the sorted lists,
- // so they'll be resorted the next time someone asks for an estimate
- sortedFeeSamples.clear();
- sortedPrioritySamples.clear();
-
- for (size_t i = 0; i < history.size(); i++) {
- if (history[i].FeeSamples() + history[i].PrioritySamples() > 0)
- LogPrint("estimatefee", "estimates: for confirming within %d blocks based on %d/%d samples, fee=%s, prio=%g\n",
- i,
- history[i].FeeSamples(), history[i].PrioritySamples(),
- estimateFee(i+1).ToString(), estimatePriority(i+1));
- }
- }
-
- /**
- * Can return CFeeRate(0) if we don't have any data for that many blocks back. nBlocksToConfirm is 1 based.
- */
- CFeeRate estimateFee(int nBlocksToConfirm)
- {
- nBlocksToConfirm--;
-
- if (nBlocksToConfirm < 0 || nBlocksToConfirm >= (int)history.size())
- return CFeeRate(0);
-
- if (sortedFeeSamples.size() == 0)
- {
- for (size_t i = 0; i < history.size(); i++)
- history.at(i).GetFeeSamples(sortedFeeSamples);
- std::sort(sortedFeeSamples.begin(), sortedFeeSamples.end(),
- std::greater<CFeeRate>());
- }
- if (sortedFeeSamples.size() < 11)
- {
- // Eleven is Gavin's Favorite Number
- // ... but we also take a maximum of 10 samples per block so eleven means
- // we're getting samples from at least two different blocks
- return CFeeRate(0);
- }
-
- int nBucketSize = history.at(nBlocksToConfirm).FeeSamples();
-
- // Estimates should not increase as number of confirmations goes up,
- // but the estimates are noisy because confirmations happen discretely
- // in blocks. To smooth out the estimates, use all samples in the history
- // and use the nth highest where n is (number of samples in previous bucket +
- // half the samples in nBlocksToConfirm bucket):
- size_t nPrevSize = 0;
- for (int i = 0; i < nBlocksToConfirm; i++)
- nPrevSize += history.at(i).FeeSamples();
- size_t index = min(nPrevSize + nBucketSize/2, sortedFeeSamples.size()-1);
- return sortedFeeSamples[index];
- }
- double estimatePriority(int nBlocksToConfirm)
- {
- nBlocksToConfirm--;
-
- if (nBlocksToConfirm < 0 || nBlocksToConfirm >= (int)history.size())
- return -1;
-
- if (sortedPrioritySamples.size() == 0)
- {
- for (size_t i = 0; i < history.size(); i++)
- history.at(i).GetPrioritySamples(sortedPrioritySamples);
- std::sort(sortedPrioritySamples.begin(), sortedPrioritySamples.end(),
- std::greater<double>());
- }
- if (sortedPrioritySamples.size() < 11)
- return -1.0;
-
- int nBucketSize = history.at(nBlocksToConfirm).PrioritySamples();
-
- // Estimates should not increase as number of confirmations needed goes up,
- // but the estimates are noisy because confirmations happen discretely
- // in blocks. To smooth out the estimates, use all samples in the history
- // and use the nth highest where n is (number of samples in previous buckets +
- // half the samples in nBlocksToConfirm bucket).
- size_t nPrevSize = 0;
- for (int i = 0; i < nBlocksToConfirm; i++)
- nPrevSize += history.at(i).PrioritySamples();
- size_t index = min(nPrevSize + nBucketSize/2, sortedPrioritySamples.size()-1);
- return sortedPrioritySamples[index];
- }
-
- void Write(CAutoFile& fileout) const
- {
- fileout << nBestSeenHeight;
- fileout << (uint32_t)history.size();
- BOOST_FOREACH(const CBlockAverage& entry, history)
- {
- entry.Write(fileout);
- }
- }
-
- void Read(CAutoFile& filein, const CFeeRate& minRelayFee)
- {
- int nFileBestSeenHeight;
- filein >> nFileBestSeenHeight;
- uint32_t numEntries;
- filein >> numEntries;
- if (numEntries <= 0 || numEntries > 10000)
- throw runtime_error("Corrupt estimates file. Must have between 1 and 10k entries.");
-
- std::vector<CBlockAverage> fileHistory;
-
- for (size_t i = 0; i < numEntries; i++)
- {
- CBlockAverage entry;
- entry.Read(filein, minRelayFee);
- fileHistory.push_back(entry);
- }
-
- // Now that we've processed the entire fee estimate data file and not
- // thrown any errors, we can copy it to our history
- nBestSeenHeight = nFileBestSeenHeight;
- history = fileHistory;
- assert(history.size() > 0);
- }
-};
-
-
CTxMemPool::CTxMemPool(const CFeeRate& _minRelayFee) :
- nTransactionsUpdated(0),
- minRelayFee(_minRelayFee)
+ nTransactionsUpdated(0)
{
// Sanity checks off by default for performance, because otherwise
// accepting transactions becomes O(N^2) where N is the number
// of transactions in the pool
fSanityCheck = false;
- // 25 blocks is a compromise between using a lot of disk/memory and
- // trying to give accurate estimates to people who might be willing
- // to wait a day or two to save a fraction of a penny in fees.
- // Confirmation times for very-low-fee transactions that take more
- // than an hour or three to confirm are highly variable.
- minerPolicyEstimator = new CMinerPolicyEstimator(25);
+ minerPolicyEstimator = new CBlockPolicyEstimator(_minRelayFee);
}
CTxMemPool::~CTxMemPool()
@@ -419,20 +87,20 @@ void CTxMemPool::AddTransactionsUpdated(unsigned int n)
}
-bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry)
+bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry, bool fCurrentEstimate)
{
// Add to memory pool without checking anything.
// Used by main.cpp AcceptToMemoryPool(), which DOES do
// all the appropriate checks.
LOCK(cs);
- {
- mapTx[hash] = entry;
- const CTransaction& tx = mapTx[hash].GetTx();
- for (unsigned int i = 0; i < tx.vin.size(); i++)
- mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i);
- nTransactionsUpdated++;
- totalTxSize += entry.GetTxSize();
- }
+ mapTx[hash] = entry;
+ const CTransaction& tx = mapTx[hash].GetTx();
+ for (unsigned int i = 0; i < tx.vin.size(); i++)
+ mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i);
+ nTransactionsUpdated++;
+ totalTxSize += entry.GetTxSize();
+ minerPolicyEstimator->processTransaction(entry, fCurrentEstimate);
+
return true;
}
@@ -478,6 +146,7 @@ void CTxMemPool::remove(const CTransaction &origTx, std::list<CTransaction>& rem
totalTxSize -= mapTx[hash].GetTxSize();
mapTx.erase(hash);
nTransactionsUpdated++;
+ minerPolicyEstimator->removeTx(hash);
}
}
}
@@ -528,7 +197,7 @@ void CTxMemPool::removeConflicts(const CTransaction &tx, std::list<CTransaction>
* Called when a block is connected. Removes from mempool and updates the miner fee estimator.
*/
void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned int nBlockHeight,
- std::list<CTransaction>& conflicts)
+ std::list<CTransaction>& conflicts, bool fCurrentEstimate)
{
LOCK(cs);
std::vector<CTxMemPoolEntry> entries;
@@ -538,7 +207,6 @@ void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned i
if (mapTx.count(hash))
entries.push_back(mapTx[hash]);
}
- minerPolicyEstimator->seenBlock(entries, nBlockHeight, minRelayFee);
BOOST_FOREACH(const CTransaction& tx, vtx)
{
std::list<CTransaction> dummy;
@@ -546,9 +214,10 @@ void CTxMemPool::removeForBlock(const std::vector<CTransaction>& vtx, unsigned i
removeConflicts(tx, conflicts);
ClearPrioritisation(tx.GetHash());
}
+ // After the txs in the new block have been removed from the mempool, update policy estimates
+ minerPolicyEstimator->processBlock(nBlockHeight, entries, fCurrentEstimate);
}
-
void CTxMemPool::clear()
{
LOCK(cs);
@@ -665,7 +334,7 @@ CTxMemPool::WriteFeeEstimates(CAutoFile& fileout) const
{
try {
LOCK(cs);
- fileout << 99900; // version required to read: 0.9.99 or later
+ fileout << 109900; // version required to read: 0.10.99 or later
fileout << CLIENT_VERSION; // version that wrote the file
minerPolicyEstimator->Write(fileout);
}
@@ -686,7 +355,7 @@ CTxMemPool::ReadFeeEstimates(CAutoFile& filein)
return error("CTxMemPool::ReadFeeEstimates(): up-version (%d) fee estimate file", nVersionRequired);
LOCK(cs);
- minerPolicyEstimator->Read(filein, minRelayFee);
+ minerPolicyEstimator->Read(filein);
}
catch (const std::exception&) {
LogPrintf("CTxMemPool::ReadFeeEstimates(): unable to read policy estimator data (non-fatal)");
@@ -723,6 +392,13 @@ void CTxMemPool::ClearPrioritisation(const uint256 hash)
mapDeltas.erase(hash);
}
+bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const
+{
+ for (unsigned int i = 0; i < tx.vin.size(); i++)
+ if (exists(tx.vin[i].prevout.hash))
+ return false;
+ return true;
+}
CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView *baseIn, CTxMemPool &mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }