forked from cculianu/Fulcrum
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathMempool.h
146 lines (130 loc) · 7.48 KB
/
Mempool.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
//
// Fulcrum - A fast & nimble SPV Server for Bitcoin Cash
// Copyright (C) 2019-2020 Calin A. Culianu <calin.culianu@gmail.com>
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program (see LICENSE.txt). If not, see
// <https://www.gnu.org/licenses/>.
//
#pragma once
#include "BlockProcTypes.h"
#include "TXO.h"
#include "bitcoin/amount.h"
#include "robin_hood/robin_hood.h"
#include <list>
#include <map>
#include <memory>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
/// Models the mempool -- WIP
struct Mempool
{
/// This info, with the exception of `hashXs` comes from bitcoind via the "getrawmempool true" RPC call.
struct Tx
{
TxHash hash; ///< in reverse bitcoind order (ready for hex encode), fixed value.
unsigned ordinal = 0; ///< used to keep track of the order this tx appeared in the mempool from bitcoind. Not particularly useful.
unsigned sizeBytes = 0;
bitcoin::Amount fee{bitcoin::Amount::zero()}; ///< we calculate this fee ourselves since in the past I noticed we get a funny value sometimes that's off by 1 or 2 sats -- which I suspect is due limitations of doubles, perhaps?
int64_t time = 0; ///< fixed (does not change during lifetime of a Tx instance)
BlockHeight height = 0; ///< is usually == chain tip height, but not always; fixed (does not change during lifetime of instance)
unsigned descendantCount = 1; ///< In-mempool descendant count, including this. Is always at least 1. May increase as mempool gets refreshed.
unsigned ancestorCount = 1; ///< In-mempool ancestor count, including this. Is always at least 1. This is fixed.
/// These are all the txos in this tx. Once set-up, this doesn't change (unlike IOInfo.utxo).
/// Note that this vector is always sized to the number of txouts in the tx. It may, however, contain !isValid
/// txo entries if an entry was an OP_RETURN (and thus was not indexed with a scripthash). Code using this
/// vector should check if txos[i].isValid().
std::vector<TXOInfo> txos;
struct IOInfo {
/// spends. .confirmedSpends here affects get_balance. We use unordered_map here because it wastes less space than robin_hood on fixed-sized maps
std::unordered_map<TXO, TXOInfo, std::hash<TXO>>
/// Spends of txo's from the db (confirmed) utxoset.
/// - Items here get _subtracted_ from the "unconfirmed" in RPC get_balance.
confirmedSpends,
/// spends of mempool ancestor txos. Items appearing here will not appear in the ancestor's
/// IOInfo::utxo map (their insertion here accompanies a deletion of those ancestor items).
unconfirmedSpends;
/// UNSPENT outs, this is used to modify listunspent and get_balance. This map may get items deleted as
/// the mempool evolves if new descendants appear that spend these txos (those descendants will list the
/// item that gets deleted from here in their own IOInfo::unconfirmedSpends map).
/// + Items here get _added_ to the "unconfirmed" balance in RPC get_balance.
std::unordered_set<IONum> utxo; ///< IONums which are indices into the txos vector declared above. We use an unordered_set here because it's more efficient than a regular set, and we don't care about order anyway.
};
bool operator<(const Tx &o) const {
/*if (ordinal != o.ordinal) // <-- this doesn't seem to do anything useful, so disabled.
return ordinal < o.ordinal;
else*/
if (ancestorCount != o.ancestorCount)
return ancestorCount < o.ancestorCount;
else if (height != o.height)
return height < o.height;
else if (time != o.time)
return time < o.time;
return hash < o.hash;
}
/// This should always contain all the HashX's involved in this tx. Note the use of unordered_map which can
/// save space vs. robin_hood for immutable maps (which this is, once built)
std::unordered_map<HashX, IOInfo, HashHasher> hashXs;
};
using TxRef = std::shared_ptr<Tx>;
/// master mapping of TxHash -> TxRef
using TxMap = robin_hood::unordered_flat_map<TxHash, TxRef, HashHasher>;
/// ensures an ordering of TxRefs for the set below that are from fewest ancestors -> most ancestors
struct TxRefOrdering {
bool operator()(const TxRef &a, const TxRef &b) const {
if (a && b) {
if (UNLIKELY(a == b))
return false;
return *a < *b;
}
else if (!a && b)
return true;
return false;
}
};
/// Note: The TxRefs here here point to the same object as the mapped_type in the TxMap above
/// Note that while the mapped_type is a vector, it is guaranteed to contain unique TxRefs, ordered by
/// TxRefOrdering above. This invariant is maintained in Controller.cpp, SynchMempoolTask::processResults().
using HashXTxMap = robin_hood::unordered_node_map<HashX, std::vector<TxRef>, HashHasher>;
// -- Data members of struct Mempool --
TxMap txs;
HashXTxMap hashXTxs;
unsigned nextOrdinal = 0; ///< used to keep track of the order of new tx's appearing from bitcoind for possible sorting based on natural bitcoind order
inline void clear() {
// Enforce a little hysteresis about what sizes we may need in the future; reserve 75% of the last size we saw.
// This means if mempool was full with thousands of txs, we do indeed maintain a largeish hash table for a
// few blocks, decaying memory usage over time. We do it this way to eventually recover memory, but to also
// leave space in case we are in a situation where many tx's are coming in quickly.
// Note that the default implementation of robin_hood clear() never shrinks its hashtables, and requires
// explicit calles to reserve() even after a clear().
const auto txsSize = txs.size(), hxSize = hashXTxs.size();
txs.clear();
hashXTxs.clear();
txs.reserve(size_t(txsSize*0.75));
hashXTxs.reserve(size_t(hxSize*0.75));
nextOrdinal = 0;
}
// -- Fee histogram support (used by mempool.get_fee_histogram RPC) --
struct FeeHistogramItem {
unsigned feeRate = 0; // in sats/B, quotient truncated to uint.
unsigned cumulativeSize = 0; // bin size, cumulative bytes
};
using FeeHistogramVec = std::vector<FeeHistogramItem>;
/// This function is potentially going to take a couple of ms at worst on very large mempools. Even a 1.5k tx
/// mempool takes under 1 ms on average hardware, so it's very fast. Storage calls this in refreshMempoolHistogram
/// from a periodic background task kicked off in Controller.
FeeHistogramVec calcCompactFeeHistogram(double binSize = 1e5 /* binSize in bytes */) const;
};