Branch data Line data Source code
# 1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto
# 2 : : // Copyright (c) 2009-2021 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 <policy/fees.h>
# 7 : :
# 8 : : #include <clientversion.h>
# 9 : : #include <fs.h>
# 10 : : #include <logging.h>
# 11 : : #include <streams.h>
# 12 : : #include <txmempool.h>
# 13 : : #include <util/serfloat.h>
# 14 : : #include <util/system.h>
# 15 : :
# 16 : : static const char* FEE_ESTIMATES_FILENAME = "fee_estimates.dat";
# 17 : :
# 18 : : static constexpr double INF_FEERATE = 1e99;
# 19 : :
# 20 : : std::string StringForFeeEstimateHorizon(FeeEstimateHorizon horizon)
# 21 : 381 : {
# 22 [ - + ]: 381 : switch (horizon) {
# 23 [ + + ]: 75 : case FeeEstimateHorizon::SHORT_HALFLIFE: return "short";
# 24 [ + + ]: 153 : case FeeEstimateHorizon::MED_HALFLIFE: return "medium";
# 25 [ + + ]: 153 : case FeeEstimateHorizon::LONG_HALFLIFE: return "long";
# 26 : 381 : } // no default case, so the compiler can warn about missing cases
# 27 : 0 : assert(false);
# 28 : 0 : }
# 29 : :
# 30 : : namespace {
# 31 : :
# 32 : : struct EncodedDoubleFormatter
# 33 : : {
# 34 : : template<typename Stream> void Ser(Stream &s, double v)
# 35 : 23260723 : {
# 36 : 23260723 : s << EncodeDouble(v);
# 37 : 23260723 : }
# 38 : :
# 39 : : template<typename Stream> void Unser(Stream& s, double& v)
# 40 : 10190117 : {
# 41 : 10190117 : uint64_t encoded;
# 42 : 10190117 : s >> encoded;
# 43 : 10190117 : v = DecodeDouble(encoded);
# 44 : 10190117 : }
# 45 : : };
# 46 : :
# 47 : : } // namespace
# 48 : :
# 49 : : /**
# 50 : : * We will instantiate an instance of this class to track transactions that were
# 51 : : * included in a block. We will lump transactions into a bucket according to their
# 52 : : * approximate feerate and then track how long it took for those txs to be included in a block
# 53 : : *
# 54 : : * The tracking of unconfirmed (mempool) transactions is completely independent of the
# 55 : : * historical tracking of transactions that have been confirmed in a block.
# 56 : : */
# 57 : : class TxConfirmStats
# 58 : : {
# 59 : : private:
# 60 : : //Define the buckets we will group transactions into
# 61 : : const std::vector<double>& buckets; // The upper-bound of the range for the bucket (inclusive)
# 62 : : const std::map<double, unsigned int>& bucketMap; // Map of bucket upper-bound to index into all vectors by bucket
# 63 : :
# 64 : : // For each bucket X:
# 65 : : // Count the total # of txs in each bucket
# 66 : : // Track the historical moving average of this total over blocks
# 67 : : std::vector<double> txCtAvg;
# 68 : :
# 69 : : // Count the total # of txs confirmed within Y blocks in each bucket
# 70 : : // Track the historical moving average of these totals over blocks
# 71 : : std::vector<std::vector<double>> confAvg; // confAvg[Y][X]
# 72 : :
# 73 : : // Track moving avg of txs which have been evicted from the mempool
# 74 : : // after failing to be confirmed within Y blocks
# 75 : : std::vector<std::vector<double>> failAvg; // failAvg[Y][X]
# 76 : :
# 77 : : // Sum the total feerate of all tx's in each bucket
# 78 : : // Track the historical moving average of this total over blocks
# 79 : : std::vector<double> m_feerate_avg;
# 80 : :
# 81 : : // Combine the conf counts with tx counts to calculate the confirmation % for each Y,X
# 82 : : // Combine the total value with the tx counts to calculate the avg feerate per bucket
# 83 : :
# 84 : : double decay;
# 85 : :
# 86 : : // Resolution (# of blocks) with which confirmations are tracked
# 87 : : unsigned int scale;
# 88 : :
# 89 : : // Mempool counts of outstanding transactions
# 90 : : // For each bucket X, track the number of transactions in the mempool
# 91 : : // that are unconfirmed for each possible confirmation value Y
# 92 : : std::vector<std::vector<int> > unconfTxs; //unconfTxs[Y][X]
# 93 : : // transactions still unconfirmed after GetMaxConfirms for each bucket
# 94 : : std::vector<int> oldUnconfTxs;
# 95 : :
# 96 : : void resizeInMemoryCounters(size_t newbuckets);
# 97 : :
# 98 : : public:
# 99 : : /**
# 100 : : * Create new TxConfirmStats. This is called by BlockPolicyEstimator's
# 101 : : * constructor with default values.
# 102 : : * @param defaultBuckets contains the upper limits for the bucket boundaries
# 103 : : * @param maxPeriods max number of periods to track
# 104 : : * @param decay how much to decay the historical moving average per block
# 105 : : */
# 106 : : TxConfirmStats(const std::vector<double>& defaultBuckets, const std::map<double, unsigned int>& defaultBucketMap,
# 107 : : unsigned int maxPeriods, double decay, unsigned int scale);
# 108 : :
# 109 : : /** Roll the circular buffer for unconfirmed txs*/
# 110 : : void ClearCurrent(unsigned int nBlockHeight);
# 111 : :
# 112 : : /**
# 113 : : * Record a new transaction data point in the current block stats
# 114 : : * @param blocksToConfirm the number of blocks it took this transaction to confirm
# 115 : : * @param val the feerate of the transaction
# 116 : : * @warning blocksToConfirm is 1-based and has to be >= 1
# 117 : : */
# 118 : : void Record(int blocksToConfirm, double val);
# 119 : :
# 120 : : /** Record a new transaction entering the mempool*/
# 121 : : unsigned int NewTx(unsigned int nBlockHeight, double val);
# 122 : :
# 123 : : /** Remove a transaction from mempool tracking stats*/
# 124 : : void removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight,
# 125 : : unsigned int bucketIndex, bool inBlock);
# 126 : :
# 127 : : /** Update our estimates by decaying our historical moving average and updating
# 128 : : with the data gathered from the current block */
# 129 : : void UpdateMovingAverages();
# 130 : :
# 131 : : /**
# 132 : : * Calculate a feerate estimate. Find the lowest value bucket (or range of buckets
# 133 : : * to make sure we have enough data points) whose transactions still have sufficient likelihood
# 134 : : * of being confirmed within the target number of confirmations
# 135 : : * @param confTarget target number of confirmations
# 136 : : * @param sufficientTxVal required average number of transactions per block in a bucket range
# 137 : : * @param minSuccess the success probability we require
# 138 : : * @param nBlockHeight the current block height
# 139 : : */
# 140 : : double EstimateMedianVal(int confTarget, double sufficientTxVal,
# 141 : : double minSuccess, unsigned int nBlockHeight,
# 142 : : EstimationResult *result = nullptr) const;
# 143 : :
# 144 : : /** Return the max number of confirms we're tracking */
# 145 : 1449806509 : unsigned int GetMaxConfirms() const { return scale * confAvg.size(); }
# 146 : :
# 147 : : /** Write state of estimation data to a file*/
# 148 : : void Write(CAutoFile& fileout) const;
# 149 : :
# 150 : : /**
# 151 : : * Read saved state of estimation data from a file and replace all internal data structures and
# 152 : : * variables with this state.
# 153 : : */
# 154 : : void Read(CAutoFile& filein, int nFileVersion, size_t numBuckets);
# 155 : : };
# 156 : :
# 157 : :
# 158 : : TxConfirmStats::TxConfirmStats(const std::vector<double>& defaultBuckets,
# 159 : : const std::map<double, unsigned int>& defaultBucketMap,
# 160 : : unsigned int maxPeriods, double _decay, unsigned int _scale)
# 161 : : : buckets(defaultBuckets), bucketMap(defaultBucketMap), decay(_decay), scale(_scale)
# 162 : 3858 : {
# 163 : 3858 : assert(_scale != 0 && "_scale must be non-zero");
# 164 : 0 : confAvg.resize(maxPeriods);
# 165 : 3858 : failAvg.resize(maxPeriods);
# 166 [ + + ]: 104166 : for (unsigned int i = 0; i < maxPeriods; i++) {
# 167 : 100308 : confAvg[i].resize(buckets.size());
# 168 : 100308 : failAvg[i].resize(buckets.size());
# 169 : 100308 : }
# 170 : :
# 171 : 3858 : txCtAvg.resize(buckets.size());
# 172 : 3858 : m_feerate_avg.resize(buckets.size());
# 173 : :
# 174 : 3858 : resizeInMemoryCounters(buckets.size());
# 175 : 3858 : }
# 176 : :
# 177 : 4845 : void TxConfirmStats::resizeInMemoryCounters(size_t newbuckets) {
# 178 : : // newbuckets must be passed in because the buckets referred to during Read have not been updated yet.
# 179 : 4845 : unconfTxs.resize(GetMaxConfirms());
# 180 [ + + ]: 1729665 : for (unsigned int i = 0; i < unconfTxs.size(); i++) {
# 181 : 1724820 : unconfTxs[i].resize(newbuckets);
# 182 : 1724820 : }
# 183 : 4845 : oldUnconfTxs.resize(newbuckets);
# 184 : 4845 : }
# 185 : :
# 186 : : // Roll the unconfirmed txs circular buffer
# 187 : : void TxConfirmStats::ClearCurrent(unsigned int nBlockHeight)
# 188 : 171810 : {
# 189 [ + + ]: 32815710 : for (unsigned int j = 0; j < buckets.size(); j++) {
# 190 : 32643900 : oldUnconfTxs[j] += unconfTxs[nBlockHeight % unconfTxs.size()][j];
# 191 : 32643900 : unconfTxs[nBlockHeight%unconfTxs.size()][j] = 0;
# 192 : 32643900 : }
# 193 : 171810 : }
# 194 : :
# 195 : :
# 196 : : void TxConfirmStats::Record(int blocksToConfirm, double feerate)
# 197 : 194622 : {
# 198 : : // blocksToConfirm is 1-based
# 199 [ - + ]: 194622 : if (blocksToConfirm < 1)
# 200 : 0 : return;
# 201 : 194622 : int periodsToConfirm = (blocksToConfirm + scale - 1) / scale;
# 202 : 194622 : unsigned int bucketindex = bucketMap.lower_bound(feerate)->second;
# 203 [ + + ]: 5106382 : for (size_t i = periodsToConfirm; i <= confAvg.size(); i++) {
# 204 : 4911760 : confAvg[i - 1][bucketindex]++;
# 205 : 4911760 : }
# 206 : 194622 : txCtAvg[bucketindex]++;
# 207 : 194622 : m_feerate_avg[bucketindex] += feerate;
# 208 : 194622 : }
# 209 : :
# 210 : : void TxConfirmStats::UpdateMovingAverages()
# 211 : 171810 : {
# 212 : 171810 : assert(confAvg.size() == failAvg.size());
# 213 [ + + ]: 32815710 : for (unsigned int j = 0; j < buckets.size(); j++) {
# 214 [ + + ]: 881385300 : for (unsigned int i = 0; i < confAvg.size(); i++) {
# 215 : 848741400 : confAvg[i][j] *= decay;
# 216 : 848741400 : failAvg[i][j] *= decay;
# 217 : 848741400 : }
# 218 : 32643900 : m_feerate_avg[j] *= decay;
# 219 : 32643900 : txCtAvg[j] *= decay;
# 220 : 32643900 : }
# 221 : 171810 : }
# 222 : :
# 223 : : // returns -1 on error conditions
# 224 : : double TxConfirmStats::EstimateMedianVal(int confTarget, double sufficientTxVal,
# 225 : : double successBreakPoint, unsigned int nBlockHeight,
# 226 : : EstimationResult *result) const
# 227 : 39672 : {
# 228 : : // Counters for a bucket (or range of buckets)
# 229 : 39672 : double nConf = 0; // Number of tx's confirmed within the confTarget
# 230 : 39672 : double totalNum = 0; // Total number of tx's that were ever confirmed
# 231 : 39672 : int extraNum = 0; // Number of tx's still in mempool for confTarget or longer
# 232 : 39672 : double failNum = 0; // Number of tx's that were never confirmed but removed from the mempool after confTarget
# 233 : 39672 : const int periodTarget = (confTarget + scale - 1) / scale;
# 234 : 39672 : const int maxbucketindex = buckets.size() - 1;
# 235 : :
# 236 : : // We'll combine buckets until we have enough samples.
# 237 : : // The near and far variables will define the range we've combined
# 238 : : // The best variables are the last range we saw which still had a high
# 239 : : // enough confirmation rate to count as success.
# 240 : : // The cur variables are the current range we're counting.
# 241 : 39672 : unsigned int curNearBucket = maxbucketindex;
# 242 : 39672 : unsigned int bestNearBucket = maxbucketindex;
# 243 : 39672 : unsigned int curFarBucket = maxbucketindex;
# 244 : 39672 : unsigned int bestFarBucket = maxbucketindex;
# 245 : :
# 246 : 39672 : bool foundAnswer = false;
# 247 : 39672 : unsigned int bins = unconfTxs.size();
# 248 : 39672 : bool newBucketRange = true;
# 249 : 39672 : bool passing = true;
# 250 : 39672 : EstimatorBucket passBucket;
# 251 : 39672 : EstimatorBucket failBucket;
# 252 : :
# 253 : : // Start counting from highest feerate transactions
# 254 [ + + ]: 7577352 : for (int bucket = maxbucketindex; bucket >= 0; --bucket) {
# 255 [ + + ]: 7537680 : if (newBucketRange) {
# 256 : 88599 : curNearBucket = bucket;
# 257 : 88599 : newBucketRange = false;
# 258 : 88599 : }
# 259 : 7537680 : curFarBucket = bucket;
# 260 : 7537680 : nConf += confAvg[periodTarget - 1][bucket];
# 261 : 7537680 : totalNum += txCtAvg[bucket];
# 262 : 7537680 : failNum += failAvg[periodTarget - 1][bucket];
# 263 [ + + ]: 1449611080 : for (unsigned int confct = confTarget; confct < GetMaxConfirms(); confct++)
# 264 : 1442073400 : extraNum += unconfTxs[(nBlockHeight - confct) % bins][bucket];
# 265 : 7537680 : extraNum += oldUnconfTxs[bucket];
# 266 : : // If we have enough transaction data points in this range of buckets,
# 267 : : // we can test for success
# 268 : : // (Only count the confirmed data points, so that each confirmation count
# 269 : : // will be looking at the same amount of data and same bucket breaks)
# 270 [ + + ]: 7537680 : if (totalNum >= sufficientTxVal / (1 - decay)) {
# 271 : 128170 : double curPct = nConf / (totalNum + failNum + extraNum);
# 272 : :
# 273 : : // Check to see if we are no longer getting confirmed at the success rate
# 274 [ + + ]: 128170 : if (curPct < successBreakPoint) {
# 275 [ + + ]: 78531 : if (passing == true) {
# 276 : : // First time we hit a failure record the failed bucket
# 277 : 1182 : unsigned int failMinBucket = std::min(curNearBucket, curFarBucket);
# 278 : 1182 : unsigned int failMaxBucket = std::max(curNearBucket, curFarBucket);
# 279 [ + + ]: 1182 : failBucket.start = failMinBucket ? buckets[failMinBucket - 1] : 0;
# 280 : 1182 : failBucket.end = buckets[failMaxBucket];
# 281 : 1182 : failBucket.withinTarget = nConf;
# 282 : 1182 : failBucket.totalConfirmed = totalNum;
# 283 : 1182 : failBucket.inMempool = extraNum;
# 284 : 1182 : failBucket.leftMempool = failNum;
# 285 : 1182 : passing = false;
# 286 : 1182 : }
# 287 : 78531 : continue;
# 288 : 78531 : }
# 289 : : // Otherwise update the cumulative stats, and the bucket variables
# 290 : : // and reset the counters
# 291 : 49639 : else {
# 292 : 49639 : failBucket = EstimatorBucket(); // Reset any failed bucket, currently passing
# 293 : 49639 : foundAnswer = true;
# 294 : 49639 : passing = true;
# 295 : 49639 : passBucket.withinTarget = nConf;
# 296 : 49639 : nConf = 0;
# 297 : 49639 : passBucket.totalConfirmed = totalNum;
# 298 : 49639 : totalNum = 0;
# 299 : 49639 : passBucket.inMempool = extraNum;
# 300 : 49639 : passBucket.leftMempool = failNum;
# 301 : 49639 : failNum = 0;
# 302 : 49639 : extraNum = 0;
# 303 : 49639 : bestNearBucket = curNearBucket;
# 304 : 49639 : bestFarBucket = curFarBucket;
# 305 : 49639 : newBucketRange = true;
# 306 : 49639 : }
# 307 : 128170 : }
# 308 : 7537680 : }
# 309 : :
# 310 : 39672 : double median = -1;
# 311 : 39672 : double txSum = 0;
# 312 : :
# 313 : : // Calculate the "average" feerate of the best bucket range that met success conditions
# 314 : : // Find the bucket with the median transaction and then report the average feerate from that bucket
# 315 : : // This is a compromise between finding the median which we can't since we don't save all tx's
# 316 : : // and reporting the average which is less accurate
# 317 : 39672 : unsigned int minBucket = std::min(bestNearBucket, bestFarBucket);
# 318 : 39672 : unsigned int maxBucket = std::max(bestNearBucket, bestFarBucket);
# 319 [ + + ]: 2765340 : for (unsigned int j = minBucket; j <= maxBucket; j++) {
# 320 : 2725668 : txSum += txCtAvg[j];
# 321 : 2725668 : }
# 322 [ + + ][ + - ]: 39672 : if (foundAnswer && txSum != 0) {
# 323 : 24225 : txSum = txSum / 2;
# 324 [ + - ]: 42814 : for (unsigned int j = minBucket; j <= maxBucket; j++) {
# 325 [ + + ]: 42814 : if (txCtAvg[j] < txSum)
# 326 : 18589 : txSum -= txCtAvg[j];
# 327 : 24225 : else { // we're in the right bucket
# 328 : 24225 : median = m_feerate_avg[j] / txCtAvg[j];
# 329 : 24225 : break;
# 330 : 24225 : }
# 331 : 42814 : }
# 332 : :
# 333 [ + + ]: 24225 : passBucket.start = minBucket ? buckets[minBucket-1] : 0;
# 334 : 24225 : passBucket.end = buckets[maxBucket];
# 335 : 24225 : }
# 336 : :
# 337 : : // If we were passing until we reached last few buckets with insufficient data, then report those as failed
# 338 [ + + ][ + + ]: 39672 : if (passing && !newBucketRange) {
# 339 : 37982 : unsigned int failMinBucket = std::min(curNearBucket, curFarBucket);
# 340 : 37982 : unsigned int failMaxBucket = std::max(curNearBucket, curFarBucket);
# 341 [ - + ]: 37982 : failBucket.start = failMinBucket ? buckets[failMinBucket - 1] : 0;
# 342 : 37982 : failBucket.end = buckets[failMaxBucket];
# 343 : 37982 : failBucket.withinTarget = nConf;
# 344 : 37982 : failBucket.totalConfirmed = totalNum;
# 345 : 37982 : failBucket.inMempool = extraNum;
# 346 : 37982 : failBucket.leftMempool = failNum;
# 347 : 37982 : }
# 348 : :
# 349 : 39672 : float passed_within_target_perc = 0.0;
# 350 : 39672 : float failed_within_target_perc = 0.0;
# 351 [ + + ]: 39672 : if ((passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool)) {
# 352 : 24225 : passed_within_target_perc = 100 * passBucket.withinTarget / (passBucket.totalConfirmed + passBucket.inMempool + passBucket.leftMempool);
# 353 : 24225 : }
# 354 [ + + ]: 39672 : if ((failBucket.totalConfirmed + failBucket.inMempool + failBucket.leftMempool)) {
# 355 : 20730 : failed_within_target_perc = 100 * failBucket.withinTarget / (failBucket.totalConfirmed + failBucket.inMempool + failBucket.leftMempool);
# 356 : 20730 : }
# 357 : :
# 358 [ + - ]: 39672 : LogPrint(BCLog::ESTIMATEFEE, "FeeEst: %d > %.0f%% decay %.5f: feerate: %g from (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n",
# 359 : 39672 : confTarget, 100.0 * successBreakPoint, decay,
# 360 : 39672 : median, passBucket.start, passBucket.end,
# 361 : 39672 : passed_within_target_perc,
# 362 : 39672 : passBucket.withinTarget, passBucket.totalConfirmed, passBucket.inMempool, passBucket.leftMempool,
# 363 : 39672 : failBucket.start, failBucket.end,
# 364 : 39672 : failed_within_target_perc,
# 365 : 39672 : failBucket.withinTarget, failBucket.totalConfirmed, failBucket.inMempool, failBucket.leftMempool);
# 366 : :
# 367 : :
# 368 [ + + ]: 39672 : if (result) {
# 369 : 39496 : result->pass = passBucket;
# 370 : 39496 : result->fail = failBucket;
# 371 : 39496 : result->decay = decay;
# 372 : 39496 : result->scale = scale;
# 373 : 39496 : }
# 374 : 39672 : return median;
# 375 : 39672 : }
# 376 : :
# 377 : : void TxConfirmStats::Write(CAutoFile& fileout) const
# 378 : 2253 : {
# 379 : 2253 : fileout << Using<EncodedDoubleFormatter>(decay);
# 380 : 2253 : fileout << scale;
# 381 : 2253 : fileout << Using<VectorFormatter<EncodedDoubleFormatter>>(m_feerate_avg);
# 382 : 2253 : fileout << Using<VectorFormatter<EncodedDoubleFormatter>>(txCtAvg);
# 383 : 2253 : fileout << Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(confAvg);
# 384 : 2253 : fileout << Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(failAvg);
# 385 : 2253 : }
# 386 : :
# 387 : : void TxConfirmStats::Read(CAutoFile& filein, int nFileVersion, size_t numBuckets)
# 388 : 987 : {
# 389 : : // Read data file and do some very basic sanity checking
# 390 : : // buckets and bucketMap are not updated yet, so don't access them
# 391 : : // If there is a read failure, we'll just discard this entire object anyway
# 392 : 987 : size_t maxConfirms, maxPeriods;
# 393 : :
# 394 : : // The current version will store the decay with each individual TxConfirmStats and also keep a scale factor
# 395 : 987 : filein >> Using<EncodedDoubleFormatter>(decay);
# 396 [ - + ][ - + ]: 987 : if (decay <= 0 || decay >= 1) {
# 397 : 0 : throw std::runtime_error("Corrupt estimates file. Decay must be between 0 and 1 (non-inclusive)");
# 398 : 0 : }
# 399 : 987 : filein >> scale;
# 400 [ - + ]: 987 : if (scale == 0) {
# 401 : 0 : throw std::runtime_error("Corrupt estimates file. Scale must be non-zero");
# 402 : 0 : }
# 403 : :
# 404 : 987 : filein >> Using<VectorFormatter<EncodedDoubleFormatter>>(m_feerate_avg);
# 405 [ - + ]: 987 : if (m_feerate_avg.size() != numBuckets) {
# 406 : 0 : throw std::runtime_error("Corrupt estimates file. Mismatch in feerate average bucket count");
# 407 : 0 : }
# 408 : 987 : filein >> Using<VectorFormatter<EncodedDoubleFormatter>>(txCtAvg);
# 409 [ - + ]: 987 : if (txCtAvg.size() != numBuckets) {
# 410 : 0 : throw std::runtime_error("Corrupt estimates file. Mismatch in tx count bucket count");
# 411 : 0 : }
# 412 : 987 : filein >> Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(confAvg);
# 413 : 987 : maxPeriods = confAvg.size();
# 414 : 987 : maxConfirms = scale * maxPeriods;
# 415 : :
# 416 [ - + ][ - + ]: 987 : if (maxConfirms <= 0 || maxConfirms > 6 * 24 * 7) { // one week
# 417 : 0 : throw std::runtime_error("Corrupt estimates file. Must maintain estimates for between 1 and 1008 (one week) confirms");
# 418 : 0 : }
# 419 [ + + ]: 26649 : for (unsigned int i = 0; i < maxPeriods; i++) {
# 420 [ - + ]: 25662 : if (confAvg[i].size() != numBuckets) {
# 421 : 0 : throw std::runtime_error("Corrupt estimates file. Mismatch in feerate conf average bucket count");
# 422 : 0 : }
# 423 : 25662 : }
# 424 : :
# 425 : 987 : filein >> Using<VectorFormatter<VectorFormatter<EncodedDoubleFormatter>>>(failAvg);
# 426 [ - + ]: 987 : if (maxPeriods != failAvg.size()) {
# 427 : 0 : throw std::runtime_error("Corrupt estimates file. Mismatch in confirms tracked for failures");
# 428 : 0 : }
# 429 [ + + ]: 26649 : for (unsigned int i = 0; i < maxPeriods; i++) {
# 430 [ - + ]: 25662 : if (failAvg[i].size() != numBuckets) {
# 431 : 0 : throw std::runtime_error("Corrupt estimates file. Mismatch in one of failure average bucket counts");
# 432 : 0 : }
# 433 : 25662 : }
# 434 : :
# 435 : : // Resize the current block variables which aren't stored in the data file
# 436 : : // to match the number of confirms and buckets
# 437 : 987 : resizeInMemoryCounters(numBuckets);
# 438 : :
# 439 [ + - ]: 987 : LogPrint(BCLog::ESTIMATEFEE, "Reading estimates: %u buckets counting confirms up to %u blocks\n",
# 440 : 987 : numBuckets, maxConfirms);
# 441 : 987 : }
# 442 : :
# 443 : : unsigned int TxConfirmStats::NewTx(unsigned int nBlockHeight, double val)
# 444 : 198498 : {
# 445 : 198498 : unsigned int bucketindex = bucketMap.lower_bound(val)->second;
# 446 : 198498 : unsigned int blockIndex = nBlockHeight % unconfTxs.size();
# 447 : 198498 : unconfTxs[blockIndex][bucketindex]++;
# 448 : 198498 : return bucketindex;
# 449 : 198498 : }
# 450 : :
# 451 : : void TxConfirmStats::removeTx(unsigned int entryHeight, unsigned int nBestSeenHeight, unsigned int bucketindex, bool inBlock)
# 452 : 198459 : {
# 453 : : //nBestSeenHeight is not updated yet for the new block
# 454 : 198459 : int blocksAgo = nBestSeenHeight - entryHeight;
# 455 [ - + ]: 198459 : if (nBestSeenHeight == 0) // the BlockPolicyEstimator hasn't seen any blocks yet
# 456 : 0 : blocksAgo = 0;
# 457 [ - + ]: 198459 : if (blocksAgo < 0) {
# 458 [ # # ]: 0 : LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error, blocks ago is negative for mempool tx\n");
# 459 : 0 : return; //This can't happen because we call this with our best seen height, no entries can have higher
# 460 : 0 : }
# 461 : :
# 462 [ + + ]: 198459 : if (blocksAgo >= (int)unconfTxs.size()) {
# 463 [ + - ]: 3715 : if (oldUnconfTxs[bucketindex] > 0) {
# 464 : 3715 : oldUnconfTxs[bucketindex]--;
# 465 : 3715 : } else {
# 466 [ # # ]: 0 : LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error, mempool tx removed from >25 blocks,bucketIndex=%u already\n",
# 467 : 0 : bucketindex);
# 468 : 0 : }
# 469 : 3715 : }
# 470 : 194744 : else {
# 471 : 194744 : unsigned int blockIndex = entryHeight % unconfTxs.size();
# 472 [ + - ]: 194744 : if (unconfTxs[blockIndex][bucketindex] > 0) {
# 473 : 194744 : unconfTxs[blockIndex][bucketindex]--;
# 474 : 194744 : } else {
# 475 [ # # ]: 0 : LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error, mempool tx removed from blockIndex=%u,bucketIndex=%u already\n",
# 476 : 0 : blockIndex, bucketindex);
# 477 : 0 : }
# 478 : 194744 : }
# 479 [ + + ][ + + ]: 198459 : if (!inBlock && (unsigned int)blocksAgo >= scale) { // Only counts as a failure if not confirmed for entire period
# 480 : 649 : assert(scale != 0);
# 481 : 0 : unsigned int periodsAgo = blocksAgo / scale;
# 482 [ + + ][ + - ]: 1430 : for (size_t i = 0; i < periodsAgo && i < failAvg.size(); i++) {
# 483 : 781 : failAvg[i][bucketindex]++;
# 484 : 781 : }
# 485 : 649 : }
# 486 : 198459 : }
# 487 : :
# 488 : : // This function is called from CTxMemPool::removeUnchecked to ensure
# 489 : : // txs removed from the mempool for any reason are no longer
# 490 : : // tracked. Txs that were part of a block have already been removed in
# 491 : : // processBlockTx to ensure they are never double tracked, but it is
# 492 : : // of no harm to try to remove them again.
# 493 : : bool CBlockPolicyEstimator::removeTx(uint256 hash, bool inBlock)
# 494 : 68476 : {
# 495 : 68476 : LOCK(m_cs_fee_estimator);
# 496 : 68476 : return _removeTx(hash, inBlock);
# 497 : 68476 : }
# 498 : :
# 499 : : bool CBlockPolicyEstimator::_removeTx(const uint256& hash, bool inBlock)
# 500 : 135692 : {
# 501 : 135692 : AssertLockHeld(m_cs_fee_estimator);
# 502 : 135692 : std::map<uint256, TxStatsInfo>::iterator pos = mapMemPoolTxs.find(hash);
# 503 [ + + ]: 135692 : if (pos != mapMemPoolTxs.end()) {
# 504 : 66153 : feeStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
# 505 : 66153 : shortStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
# 506 : 66153 : longStats->removeTx(pos->second.blockHeight, nBestSeenHeight, pos->second.bucketIndex, inBlock);
# 507 : 66153 : mapMemPoolTxs.erase(hash);
# 508 : 66153 : return true;
# 509 : 69539 : } else {
# 510 : 69539 : return false;
# 511 : 69539 : }
# 512 : 135692 : }
# 513 : :
# 514 : : CBlockPolicyEstimator::CBlockPolicyEstimator()
# 515 : : : nBestSeenHeight(0), firstRecordedHeight(0), historicalFirst(0), historicalBest(0), trackedTxs(0), untrackedTxs(0)
# 516 : 957 : {
# 517 : 957 : static_assert(MIN_BUCKET_FEERATE > 0, "Min feerate must be nonzero");
# 518 : 957 : size_t bucketIndex = 0;
# 519 : :
# 520 [ + + ]: 181830 : for (double bucketBoundary = MIN_BUCKET_FEERATE; bucketBoundary <= MAX_BUCKET_FEERATE; bucketBoundary *= FEE_SPACING, bucketIndex++) {
# 521 : 180873 : buckets.push_back(bucketBoundary);
# 522 : 180873 : bucketMap[bucketBoundary] = bucketIndex;
# 523 : 180873 : }
# 524 : 957 : buckets.push_back(INF_FEERATE);
# 525 : 957 : bucketMap[INF_FEERATE] = bucketIndex;
# 526 : 957 : assert(bucketMap.size() == buckets.size());
# 527 : :
# 528 : 0 : feeStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, MED_BLOCK_PERIODS, MED_DECAY, MED_SCALE));
# 529 : 957 : shortStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, SHORT_BLOCK_PERIODS, SHORT_DECAY, SHORT_SCALE));
# 530 : 957 : longStats = std::unique_ptr<TxConfirmStats>(new TxConfirmStats(buckets, bucketMap, LONG_BLOCK_PERIODS, LONG_DECAY, LONG_SCALE));
# 531 : :
# 532 : : // If the fee estimation file is present, read recorded estimations
# 533 : 957 : fs::path est_filepath = gArgs.GetDataDirNet() / FEE_ESTIMATES_FILENAME;
# 534 : 957 : CAutoFile est_file(fsbridge::fopen(est_filepath, "rb"), SER_DISK, CLIENT_VERSION);
# 535 [ + + ][ - + ]: 957 : if (est_file.IsNull() || !Read(est_file)) {
# 536 : 628 : LogPrintf("Failed to read fee estimates from %s. Continue anyway.\n", fs::PathToString(est_filepath));
# 537 : 628 : }
# 538 : 957 : }
# 539 : :
# 540 : : CBlockPolicyEstimator::~CBlockPolicyEstimator()
# 541 : 957 : {
# 542 : 957 : }
# 543 : :
# 544 : : void CBlockPolicyEstimator::processTransaction(const CTxMemPoolEntry& entry, bool validFeeEstimate)
# 545 : 73508 : {
# 546 : 73508 : LOCK(m_cs_fee_estimator);
# 547 : 73508 : unsigned int txHeight = entry.GetHeight();
# 548 : 73508 : uint256 hash = entry.GetTx().GetHash();
# 549 [ + + ]: 73508 : if (mapMemPoolTxs.count(hash)) {
# 550 [ + - ]: 4 : LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error mempool tx %s already being tracked\n",
# 551 : 4 : hash.ToString());
# 552 : 4 : return;
# 553 : 4 : }
# 554 : :
# 555 [ + + ]: 73504 : if (txHeight != nBestSeenHeight) {
# 556 : : // Ignore side chains and re-orgs; assuming they are random they don't
# 557 : : // affect the estimate. We'll potentially double count transactions in 1-block reorgs.
# 558 : : // Ignore txs if BlockPolicyEstimator is not in sync with ActiveChain().Tip().
# 559 : : // It will be synced next time a block is processed.
# 560 : 4745 : return;
# 561 : 4745 : }
# 562 : :
# 563 : : // Only want to be updating estimates when our blockchain is synced,
# 564 : : // otherwise we'll miscalculate how many blocks its taking to get included.
# 565 [ + + ]: 68759 : if (!validFeeEstimate) {
# 566 : 2593 : untrackedTxs++;
# 567 : 2593 : return;
# 568 : 2593 : }
# 569 : 66166 : trackedTxs++;
# 570 : :
# 571 : : // Feerates are stored and reported as BTC-per-kb:
# 572 : 66166 : CFeeRate feeRate(entry.GetFee(), entry.GetTxSize());
# 573 : :
# 574 : 66166 : mapMemPoolTxs[hash].blockHeight = txHeight;
# 575 : 66166 : unsigned int bucketIndex = feeStats->NewTx(txHeight, (double)feeRate.GetFeePerK());
# 576 : 66166 : mapMemPoolTxs[hash].bucketIndex = bucketIndex;
# 577 : 66166 : unsigned int bucketIndex2 = shortStats->NewTx(txHeight, (double)feeRate.GetFeePerK());
# 578 : 66166 : assert(bucketIndex == bucketIndex2);
# 579 : 0 : unsigned int bucketIndex3 = longStats->NewTx(txHeight, (double)feeRate.GetFeePerK());
# 580 : 66166 : assert(bucketIndex == bucketIndex3);
# 581 : 66166 : }
# 582 : :
# 583 : : bool CBlockPolicyEstimator::processBlockTx(unsigned int nBlockHeight, const CTxMemPoolEntry* entry)
# 584 : 66760 : {
# 585 : 66760 : AssertLockHeld(m_cs_fee_estimator);
# 586 [ + + ]: 66760 : if (!_removeTx(entry->GetTx().GetHash(), true)) {
# 587 : : // This transaction wasn't being tracked for fee estimation
# 588 : 1886 : return false;
# 589 : 1886 : }
# 590 : :
# 591 : : // How many blocks did it take for miners to include this transaction?
# 592 : : // blocksToConfirm is 1-based, so a transaction included in the earliest
# 593 : : // possible block has confirmation count of 1
# 594 : 64874 : int blocksToConfirm = nBlockHeight - entry->GetHeight();
# 595 [ - + ]: 64874 : if (blocksToConfirm <= 0) {
# 596 : : // This can't happen because we don't process transactions from a block with a height
# 597 : : // lower than our greatest seen height
# 598 [ # # ]: 0 : LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy error Transaction had negative blocksToConfirm\n");
# 599 : 0 : return false;
# 600 : 0 : }
# 601 : :
# 602 : : // Feerates are stored and reported as BTC-per-kb:
# 603 : 64874 : CFeeRate feeRate(entry->GetFee(), entry->GetTxSize());
# 604 : :
# 605 : 64874 : feeStats->Record(blocksToConfirm, (double)feeRate.GetFeePerK());
# 606 : 64874 : shortStats->Record(blocksToConfirm, (double)feeRate.GetFeePerK());
# 607 : 64874 : longStats->Record(blocksToConfirm, (double)feeRate.GetFeePerK());
# 608 : 64874 : return true;
# 609 : 64874 : }
# 610 : :
# 611 : : void CBlockPolicyEstimator::processBlock(unsigned int nBlockHeight,
# 612 : : std::vector<const CTxMemPoolEntry*>& entries)
# 613 : 63149 : {
# 614 : 63149 : LOCK(m_cs_fee_estimator);
# 615 [ + + ]: 63149 : if (nBlockHeight <= nBestSeenHeight) {
# 616 : : // Ignore side chains and re-orgs; assuming they are random
# 617 : : // they don't affect the estimate.
# 618 : : // And if an attacker can re-org the chain at will, then
# 619 : : // you've got much bigger problems than "attacker can influence
# 620 : : // transaction fees."
# 621 : 5879 : return;
# 622 : 5879 : }
# 623 : :
# 624 : : // Must update nBestSeenHeight in sync with ClearCurrent so that
# 625 : : // calls to removeTx (via processBlockTx) correctly calculate age
# 626 : : // of unconfirmed txs to remove from tracking.
# 627 : 57270 : nBestSeenHeight = nBlockHeight;
# 628 : :
# 629 : : // Update unconfirmed circular buffer
# 630 : 57270 : feeStats->ClearCurrent(nBlockHeight);
# 631 : 57270 : shortStats->ClearCurrent(nBlockHeight);
# 632 : 57270 : longStats->ClearCurrent(nBlockHeight);
# 633 : :
# 634 : : // Decay all exponential averages
# 635 : 57270 : feeStats->UpdateMovingAverages();
# 636 : 57270 : shortStats->UpdateMovingAverages();
# 637 : 57270 : longStats->UpdateMovingAverages();
# 638 : :
# 639 : 57270 : unsigned int countedTxs = 0;
# 640 : : // Update averages with data points from current block
# 641 [ + + ]: 66760 : for (const auto& entry : entries) {
# 642 [ + + ]: 66760 : if (processBlockTx(nBlockHeight, entry))
# 643 : 64874 : countedTxs++;
# 644 : 66760 : }
# 645 : :
# 646 [ + + ][ + + ]: 57270 : if (firstRecordedHeight == 0 && countedTxs > 0) {
# 647 : 219 : firstRecordedHeight = nBestSeenHeight;
# 648 [ + - ]: 219 : LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy first recorded height %u\n", firstRecordedHeight);
# 649 : 219 : }
# 650 : :
# 651 : :
# 652 [ + - ][ + + ]: 57270 : LogPrint(BCLog::ESTIMATEFEE, "Blockpolicy estimates updated by %u of %u block txs, since last block %u of %u tracked, mempool map size %u, max target %u from %s\n",
# 653 : 57270 : countedTxs, entries.size(), trackedTxs, trackedTxs + untrackedTxs, mapMemPoolTxs.size(),
# 654 : 57270 : MaxUsableEstimate(), HistoricalBlockSpan() > BlockSpan() ? "historical" : "current");
# 655 : :
# 656 : 57270 : trackedTxs = 0;
# 657 : 57270 : untrackedTxs = 0;
# 658 : 57270 : }
# 659 : :
# 660 : : CFeeRate CBlockPolicyEstimator::estimateFee(int confTarget) const
# 661 : 188 : {
# 662 : : // It's not possible to get reasonable estimates for confTarget of 1
# 663 [ + + ]: 188 : if (confTarget <= 1)
# 664 : 12 : return CFeeRate(0);
# 665 : :
# 666 : 176 : return estimateRawFee(confTarget, DOUBLE_SUCCESS_PCT, FeeEstimateHorizon::MED_HALFLIFE);
# 667 : 188 : }
# 668 : :
# 669 : : CFeeRate CBlockPolicyEstimator::estimateRawFee(int confTarget, double successThreshold, FeeEstimateHorizon horizon, EstimationResult* result) const
# 670 : 557 : {
# 671 : 557 : TxConfirmStats* stats = nullptr;
# 672 : 557 : double sufficientTxs = SUFFICIENT_FEETXS;
# 673 [ - + ]: 557 : switch (horizon) {
# 674 [ + + ]: 75 : case FeeEstimateHorizon::SHORT_HALFLIFE: {
# 675 : 75 : stats = shortStats.get();
# 676 : 75 : sufficientTxs = SUFFICIENT_TXS_SHORT;
# 677 : 75 : break;
# 678 : 0 : }
# 679 [ + + ]: 329 : case FeeEstimateHorizon::MED_HALFLIFE: {
# 680 : 329 : stats = feeStats.get();
# 681 : 329 : break;
# 682 : 0 : }
# 683 [ + + ]: 153 : case FeeEstimateHorizon::LONG_HALFLIFE: {
# 684 : 153 : stats = longStats.get();
# 685 : 153 : break;
# 686 : 0 : }
# 687 : 557 : } // no default case, so the compiler can warn about missing cases
# 688 : 557 : assert(stats);
# 689 : :
# 690 : 557 : LOCK(m_cs_fee_estimator);
# 691 : : // Return failure if trying to analyze a target we're not tracking
# 692 [ - + ][ - + ]: 557 : if (confTarget <= 0 || (unsigned int)confTarget > stats->GetMaxConfirms())
# 693 : 0 : return CFeeRate(0);
# 694 [ - + ]: 557 : if (successThreshold > 1)
# 695 : 0 : return CFeeRate(0);
# 696 : :
# 697 : 557 : double median = stats->EstimateMedianVal(confTarget, sufficientTxs, successThreshold, nBestSeenHeight, result);
# 698 : :
# 699 [ + + ]: 557 : if (median < 0)
# 700 : 41 : return CFeeRate(0);
# 701 : :
# 702 : 516 : return CFeeRate(llround(median));
# 703 : 557 : }
# 704 : :
# 705 : : unsigned int CBlockPolicyEstimator::HighestTargetTracked(FeeEstimateHorizon horizon) const
# 706 : 6286 : {
# 707 : 6286 : LOCK(m_cs_fee_estimator);
# 708 [ - + ]: 6286 : switch (horizon) {
# 709 [ + + ]: 153 : case FeeEstimateHorizon::SHORT_HALFLIFE: {
# 710 : 153 : return shortStats->GetMaxConfirms();
# 711 : 0 : }
# 712 [ + + ]: 153 : case FeeEstimateHorizon::MED_HALFLIFE: {
# 713 : 153 : return feeStats->GetMaxConfirms();
# 714 : 0 : }
# 715 [ + + ]: 5980 : case FeeEstimateHorizon::LONG_HALFLIFE: {
# 716 : 5980 : return longStats->GetMaxConfirms();
# 717 : 0 : }
# 718 : 6286 : } // no default case, so the compiler can warn about missing cases
# 719 : 0 : assert(false);
# 720 : 0 : }
# 721 : :
# 722 : : unsigned int CBlockPolicyEstimator::BlockSpan() const
# 723 : 125293 : {
# 724 [ + + ]: 125293 : if (firstRecordedHeight == 0) return 0;
# 725 : 28499 : assert(nBestSeenHeight >= firstRecordedHeight);
# 726 : :
# 727 : 0 : return nBestSeenHeight - firstRecordedHeight;
# 728 : 125293 : }
# 729 : :
# 730 : : unsigned int CBlockPolicyEstimator::HistoricalBlockSpan() const
# 731 : 125293 : {
# 732 [ + + ]: 125293 : if (historicalFirst == 0) return 0;
# 733 : 1323 : assert(historicalBest >= historicalFirst);
# 734 : :
# 735 [ - + ]: 1323 : if (nBestSeenHeight - historicalBest > OLDEST_ESTIMATE_HISTORY) return 0;
# 736 : :
# 737 : 1323 : return historicalBest - historicalFirst;
# 738 : 1323 : }
# 739 : :
# 740 : : unsigned int CBlockPolicyEstimator::MaxUsableEstimate() const
# 741 : 67272 : {
# 742 : : // Block spans are divided by 2 to make sure there are enough potential failing data points for the estimate
# 743 : 67272 : return std::min(longStats->GetMaxConfirms(), std::max(BlockSpan(), HistoricalBlockSpan()) / 2);
# 744 : 67272 : }
# 745 : :
# 746 : : /** Return a fee estimate at the required successThreshold from the shortest
# 747 : : * time horizon which tracks confirmations up to the desired target. If
# 748 : : * checkShorterHorizon is requested, also allow short time horizon estimates
# 749 : : * for a lower target to reduce the given answer */
# 750 : : double CBlockPolicyEstimator::estimateCombinedFee(unsigned int confTarget, double successThreshold, bool checkShorterHorizon, EstimationResult *result) const
# 751 : 22815 : {
# 752 : 22815 : double estimate = -1;
# 753 [ + - ][ + - ]: 22815 : if (confTarget >= 1 && confTarget <= longStats->GetMaxConfirms()) {
# 754 : : // Find estimate from shortest time horizon possible
# 755 [ + + ]: 22815 : if (confTarget <= shortStats->GetMaxConfirms()) { // short horizon
# 756 : 18167 : estimate = shortStats->EstimateMedianVal(confTarget, SUFFICIENT_TXS_SHORT, successThreshold, nBestSeenHeight, result);
# 757 : 18167 : }
# 758 [ + + ]: 4648 : else if (confTarget <= feeStats->GetMaxConfirms()) { // medium horizon
# 759 : 1830 : estimate = feeStats->EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, result);
# 760 : 1830 : }
# 761 : 2818 : else { // long horizon
# 762 : 2818 : estimate = longStats->EstimateMedianVal(confTarget, SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, result);
# 763 : 2818 : }
# 764 [ + + ]: 22815 : if (checkShorterHorizon) {
# 765 : 19447 : EstimationResult tempResult;
# 766 : : // If a lower confTarget from a more recent horizon returns a lower answer use it.
# 767 [ + + ]: 19447 : if (confTarget > feeStats->GetMaxConfirms()) {
# 768 : 2816 : double medMax = feeStats->EstimateMedianVal(feeStats->GetMaxConfirms(), SUFFICIENT_FEETXS, successThreshold, nBestSeenHeight, &tempResult);
# 769 [ + + ][ + + ]: 2816 : if (medMax > 0 && (estimate == -1 || medMax < estimate)) {
# [ + + ]
# 770 : 1166 : estimate = medMax;
# 771 [ + - ]: 1166 : if (result) *result = tempResult;
# 772 : 1166 : }
# 773 : 2816 : }
# 774 [ + + ]: 19447 : if (confTarget > shortStats->GetMaxConfirms()) {
# 775 : 4553 : double shortMax = shortStats->EstimateMedianVal(shortStats->GetMaxConfirms(), SUFFICIENT_TXS_SHORT, successThreshold, nBestSeenHeight, &tempResult);
# 776 [ + + ][ + + ]: 4553 : if (shortMax > 0 && (estimate == -1 || shortMax < estimate)) {
# [ + + ]
# 777 : 332 : estimate = shortMax;
# 778 [ + - ]: 332 : if (result) *result = tempResult;
# 779 : 332 : }
# 780 : 4553 : }
# 781 : 19447 : }
# 782 : 22815 : }
# 783 : 22815 : return estimate;
# 784 : 22815 : }
# 785 : :
# 786 : : /** Ensure that for a conservative estimate, the DOUBLE_SUCCESS_PCT is also met
# 787 : : * at 2 * target for any longer time horizons.
# 788 : : */
# 789 : : double CBlockPolicyEstimator::estimateConservativeFee(unsigned int doubleTarget, EstimationResult *result) const
# 790 : 4963 : {
# 791 : 4963 : double estimate = -1;
# 792 : 4963 : EstimationResult tempResult;
# 793 [ + + ]: 4963 : if (doubleTarget <= shortStats->GetMaxConfirms()) {
# 794 : 4324 : estimate = feeStats->EstimateMedianVal(doubleTarget, SUFFICIENT_FEETXS, DOUBLE_SUCCESS_PCT, nBestSeenHeight, result);
# 795 : 4324 : }
# 796 [ + + ]: 4963 : if (doubleTarget <= feeStats->GetMaxConfirms()) {
# 797 : 4607 : double longEstimate = longStats->EstimateMedianVal(doubleTarget, SUFFICIENT_FEETXS, DOUBLE_SUCCESS_PCT, nBestSeenHeight, &tempResult);
# 798 [ + + ]: 4607 : if (longEstimate > estimate) {
# 799 : 230 : estimate = longEstimate;
# 800 [ + - ]: 230 : if (result) *result = tempResult;
# 801 : 230 : }
# 802 : 4607 : }
# 803 : 4963 : return estimate;
# 804 : 4963 : }
# 805 : :
# 806 : : /** estimateSmartFee returns the max of the feerates calculated with a 60%
# 807 : : * threshold required at target / 2, an 85% threshold required at target and a
# 808 : : * 95% threshold required at 2 * target. Each calculation is performed at the
# 809 : : * shortest time horizon which tracks the required target. Conservative
# 810 : : * estimates, however, required the 95% threshold at 2 * target be met for any
# 811 : : * longer time horizons also.
# 812 : : */
# 813 : : CFeeRate CBlockPolicyEstimator::estimateSmartFee(int confTarget, FeeCalculation *feeCalc, bool conservative) const
# 814 : 10002 : {
# 815 : 10002 : LOCK(m_cs_fee_estimator);
# 816 : :
# 817 [ + + ]: 10002 : if (feeCalc) {
# 818 : 4421 : feeCalc->desiredTarget = confTarget;
# 819 : 4421 : feeCalc->returnedTarget = confTarget;
# 820 : 4421 : }
# 821 : :
# 822 : 10002 : double median = -1;
# 823 : 10002 : EstimationResult tempResult;
# 824 : :
# 825 : : // Return failure if trying to analyze a target we're not tracking
# 826 [ - + ][ - + ]: 10002 : if (confTarget <= 0 || (unsigned int)confTarget > longStats->GetMaxConfirms()) {
# 827 : 0 : return CFeeRate(0); // error condition
# 828 : 0 : }
# 829 : :
# 830 : : // It's not possible to get reasonable estimates for confTarget of 1
# 831 [ + + ]: 10002 : if (confTarget == 1) confTarget = 2;
# 832 : :
# 833 : 10002 : unsigned int maxUsableEstimate = MaxUsableEstimate();
# 834 [ + + ]: 10002 : if ((unsigned int)confTarget > maxUsableEstimate) {
# 835 : 7911 : confTarget = maxUsableEstimate;
# 836 : 7911 : }
# 837 [ + + ]: 10002 : if (feeCalc) feeCalc->returnedTarget = confTarget;
# 838 : :
# 839 [ + + ]: 10002 : if (confTarget <= 1) return CFeeRate(0); // error condition
# 840 : :
# 841 : 7605 : assert(confTarget > 0); //estimateCombinedFee and estimateConservativeFee take unsigned ints
# 842 : : /** true is passed to estimateCombined fee for target/2 and target so
# 843 : : * that we check the max confirms for shorter time horizons as well.
# 844 : : * This is necessary to preserve monotonically increasing estimates.
# 845 : : * For non-conservative estimates we do the same thing for 2*target, but
# 846 : : * for conservative estimates we want to skip these shorter horizons
# 847 : : * checks for 2*target because we are taking the max over all time
# 848 : : * horizons so we already have monotonically increasing estimates and
# 849 : : * the purpose of conservative estimates is not to let short term
# 850 : : * fluctuations lower our estimates by too much.
# 851 : : */
# 852 : 0 : double halfEst = estimateCombinedFee(confTarget/2, HALF_SUCCESS_PCT, true, &tempResult);
# 853 [ + + ]: 7605 : if (feeCalc) {
# 854 : 3454 : feeCalc->est = tempResult;
# 855 : 3454 : feeCalc->reason = FeeReason::HALF_ESTIMATE;
# 856 : 3454 : }
# 857 : 7605 : median = halfEst;
# 858 : 7605 : double actualEst = estimateCombinedFee(confTarget, SUCCESS_PCT, true, &tempResult);
# 859 [ + + ]: 7605 : if (actualEst > median) {
# 860 : 40 : median = actualEst;
# 861 [ + - ]: 40 : if (feeCalc) {
# 862 : 40 : feeCalc->est = tempResult;
# 863 : 40 : feeCalc->reason = FeeReason::FULL_ESTIMATE;
# 864 : 40 : }
# 865 : 40 : }
# 866 : 7605 : double doubleEst = estimateCombinedFee(2 * confTarget, DOUBLE_SUCCESS_PCT, !conservative, &tempResult);
# 867 [ + + ]: 7605 : if (doubleEst > median) {
# 868 : 1 : median = doubleEst;
# 869 [ - + ]: 1 : if (feeCalc) {
# 870 : 0 : feeCalc->est = tempResult;
# 871 : 0 : feeCalc->reason = FeeReason::DOUBLE_ESTIMATE;
# 872 : 0 : }
# 873 : 1 : }
# 874 : :
# 875 [ + + ][ + + ]: 7605 : if (conservative || median == -1) {
# 876 : 4963 : double consEst = estimateConservativeFee(2 * confTarget, &tempResult);
# 877 [ + + ]: 4963 : if (consEst > median) {
# 878 : 151 : median = consEst;
# 879 [ + - ]: 151 : if (feeCalc) {
# 880 : 151 : feeCalc->est = tempResult;
# 881 : 151 : feeCalc->reason = FeeReason::CONSERVATIVE;
# 882 : 151 : }
# 883 : 151 : }
# 884 : 4963 : }
# 885 : :
# 886 [ + + ]: 7605 : if (median < 0) return CFeeRate(0); // error condition
# 887 : :
# 888 : 5094 : return CFeeRate(llround(median));
# 889 : 7605 : }
# 890 : :
# 891 : 751 : void CBlockPolicyEstimator::Flush() {
# 892 : 751 : FlushUnconfirmed();
# 893 : :
# 894 : 751 : fs::path est_filepath = gArgs.GetDataDirNet() / FEE_ESTIMATES_FILENAME;
# 895 : 751 : CAutoFile est_file(fsbridge::fopen(est_filepath, "wb"), SER_DISK, CLIENT_VERSION);
# 896 [ - + ][ - + ]: 751 : if (est_file.IsNull() || !Write(est_file)) {
# 897 : 0 : LogPrintf("Failed to write fee estimates to %s. Continue anyway.\n", fs::PathToString(est_filepath));
# 898 : 0 : }
# 899 : 751 : }
# 900 : :
# 901 : : bool CBlockPolicyEstimator::Write(CAutoFile& fileout) const
# 902 : 751 : {
# 903 : 751 : try {
# 904 : 751 : LOCK(m_cs_fee_estimator);
# 905 : 751 : fileout << 149900; // version required to read: 0.14.99 or later
# 906 : 751 : fileout << CLIENT_VERSION; // version that wrote the file
# 907 : 751 : fileout << nBestSeenHeight;
# 908 [ + + ]: 751 : if (BlockSpan() > HistoricalBlockSpan()/2) {
# 909 : 172 : fileout << firstRecordedHeight << nBestSeenHeight;
# 910 : 172 : }
# 911 : 579 : else {
# 912 : 579 : fileout << historicalFirst << historicalBest;
# 913 : 579 : }
# 914 : 751 : fileout << Using<VectorFormatter<EncodedDoubleFormatter>>(buckets);
# 915 : 751 : feeStats->Write(fileout);
# 916 : 751 : shortStats->Write(fileout);
# 917 : 751 : longStats->Write(fileout);
# 918 : 751 : }
# 919 : 751 : catch (const std::exception&) {
# 920 : 0 : LogPrintf("CBlockPolicyEstimator::Write(): unable to write policy estimator data (non-fatal)\n");
# 921 : 0 : return false;
# 922 : 0 : }
# 923 : 751 : return true;
# 924 : 751 : }
# 925 : :
# 926 : : bool CBlockPolicyEstimator::Read(CAutoFile& filein)
# 927 : 329 : {
# 928 : 329 : try {
# 929 : 329 : LOCK(m_cs_fee_estimator);
# 930 : 329 : int nVersionRequired, nVersionThatWrote;
# 931 : 329 : filein >> nVersionRequired >> nVersionThatWrote;
# 932 [ - + ]: 329 : if (nVersionRequired > CLIENT_VERSION) {
# 933 : 0 : throw std::runtime_error(strprintf("up-version (%d) fee estimate file", nVersionRequired));
# 934 : 0 : }
# 935 : :
# 936 : : // Read fee estimates file into temporary variables so existing data
# 937 : : // structures aren't corrupted if there is an exception.
# 938 : 329 : unsigned int nFileBestSeenHeight;
# 939 : 329 : filein >> nFileBestSeenHeight;
# 940 : :
# 941 [ - + ]: 329 : if (nVersionRequired < 149900) {
# 942 : 0 : LogPrintf("%s: incompatible old fee estimation data (non-fatal). Version: %d\n", __func__, nVersionRequired);
# 943 : 329 : } else { // New format introduced in 149900
# 944 : 329 : unsigned int nFileHistoricalFirst, nFileHistoricalBest;
# 945 : 329 : filein >> nFileHistoricalFirst >> nFileHistoricalBest;
# 946 [ - + ][ - + ]: 329 : if (nFileHistoricalFirst > nFileHistoricalBest || nFileHistoricalBest > nFileBestSeenHeight) {
# 947 : 0 : throw std::runtime_error("Corrupt estimates file. Historical block range for estimates is invalid");
# 948 : 0 : }
# 949 : 329 : std::vector<double> fileBuckets;
# 950 : 329 : filein >> Using<VectorFormatter<EncodedDoubleFormatter>>(fileBuckets);
# 951 : 329 : size_t numBuckets = fileBuckets.size();
# 952 [ - + ][ - + ]: 329 : if (numBuckets <= 1 || numBuckets > 1000) {
# 953 : 0 : throw std::runtime_error("Corrupt estimates file. Must have between 2 and 1000 feerate buckets");
# 954 : 0 : }
# 955 : :
# 956 : 329 : std::unique_ptr<TxConfirmStats> fileFeeStats(new TxConfirmStats(buckets, bucketMap, MED_BLOCK_PERIODS, MED_DECAY, MED_SCALE));
# 957 : 329 : std::unique_ptr<TxConfirmStats> fileShortStats(new TxConfirmStats(buckets, bucketMap, SHORT_BLOCK_PERIODS, SHORT_DECAY, SHORT_SCALE));
# 958 : 329 : std::unique_ptr<TxConfirmStats> fileLongStats(new TxConfirmStats(buckets, bucketMap, LONG_BLOCK_PERIODS, LONG_DECAY, LONG_SCALE));
# 959 : 329 : fileFeeStats->Read(filein, nVersionThatWrote, numBuckets);
# 960 : 329 : fileShortStats->Read(filein, nVersionThatWrote, numBuckets);
# 961 : 329 : fileLongStats->Read(filein, nVersionThatWrote, numBuckets);
# 962 : :
# 963 : : // Fee estimates file parsed correctly
# 964 : : // Copy buckets from file and refresh our bucketmap
# 965 : 329 : buckets = fileBuckets;
# 966 : 329 : bucketMap.clear();
# 967 [ + + ]: 62839 : for (unsigned int i = 0; i < buckets.size(); i++) {
# 968 : 62510 : bucketMap[buckets[i]] = i;
# 969 : 62510 : }
# 970 : :
# 971 : : // Destroy old TxConfirmStats and point to new ones that already reference buckets and bucketMap
# 972 : 329 : feeStats = std::move(fileFeeStats);
# 973 : 329 : shortStats = std::move(fileShortStats);
# 974 : 329 : longStats = std::move(fileLongStats);
# 975 : :
# 976 : 329 : nBestSeenHeight = nFileBestSeenHeight;
# 977 : 329 : historicalFirst = nFileHistoricalFirst;
# 978 : 329 : historicalBest = nFileHistoricalBest;
# 979 : 329 : }
# 980 : 329 : }
# 981 : 329 : catch (const std::exception& e) {
# 982 : 0 : LogPrintf("CBlockPolicyEstimator::Read(): unable to read policy estimator data (non-fatal): %s\n",e.what());
# 983 : 0 : return false;
# 984 : 0 : }
# 985 : 329 : return true;
# 986 : 329 : }
# 987 : :
# 988 : 751 : void CBlockPolicyEstimator::FlushUnconfirmed() {
# 989 : 751 : int64_t startclear = GetTimeMicros();
# 990 : 751 : LOCK(m_cs_fee_estimator);
# 991 : 751 : size_t num_entries = mapMemPoolTxs.size();
# 992 : : // Remove every entry in mapMemPoolTxs
# 993 [ + + ]: 1207 : while (!mapMemPoolTxs.empty()) {
# 994 : 456 : auto mi = mapMemPoolTxs.begin();
# 995 : 456 : _removeTx(mi->first, false); // this calls erase() on mapMemPoolTxs
# 996 : 456 : }
# 997 : 751 : int64_t endclear = GetTimeMicros();
# 998 [ + - ]: 751 : LogPrint(BCLog::ESTIMATEFEE, "Recorded %u unconfirmed txs from mempool in %gs\n", num_entries, (endclear - startclear)*0.000001);
# 999 : 751 : }
# 1000 : :
# 1001 : : FeeFilterRounder::FeeFilterRounder(const CFeeRate& minIncrementalFee)
# 1002 : 418 : {
# 1003 : 418 : CAmount minFeeLimit = std::max(CAmount(1), minIncrementalFee.GetFeePerK() / 2);
# 1004 : 418 : feeset.insert(0);
# 1005 [ + + ]: 43890 : for (double bucketBoundary = minFeeLimit; bucketBoundary <= MAX_FILTER_FEERATE; bucketBoundary *= FEE_FILTER_SPACING) {
# 1006 : 43472 : feeset.insert(bucketBoundary);
# 1007 : 43472 : }
# 1008 : 418 : }
# 1009 : :
# 1010 : : CAmount FeeFilterRounder::round(CAmount currentMinFee)
# 1011 : 2085 : {
# 1012 : 2085 : std::set<double>::iterator it = feeset.lower_bound(currentMinFee);
# 1013 [ + + ][ + + ]: 2085 : if ((it != feeset.begin() && insecure_rand.rand32() % 3 != 0) || it == feeset.end()) {
# [ + + ][ + + ]
# 1014 : 716 : it--;
# 1015 : 716 : }
# 1016 : 2085 : return static_cast<CAmount>(*it);
# 1017 : 2085 : }
|
