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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
|
// Copyright (c) 2012-2022 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include <coins.h>
#include <consensus/consensus.h>
#include <logging.h>
#include <random.h>
#include <util/trace.h>
#include <version.h>
bool CCoinsView::GetCoin(const COutPoint &outpoint, Coin &coin) const { return false; }
uint256 CCoinsView::GetBestBlock() const { return uint256(); }
std::vector<uint256> CCoinsView::GetHeadBlocks() const { return std::vector<uint256>(); }
bool CCoinsView::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock, bool erase) { return false; }
std::unique_ptr<CCoinsViewCursor> CCoinsView::Cursor() const { return nullptr; }
bool CCoinsView::HaveCoin(const COutPoint &outpoint) const
{
Coin coin;
return GetCoin(outpoint, coin);
}
CCoinsViewBacked::CCoinsViewBacked(CCoinsView *viewIn) : base(viewIn) { }
bool CCoinsViewBacked::GetCoin(const COutPoint &outpoint, Coin &coin) const { return base->GetCoin(outpoint, coin); }
bool CCoinsViewBacked::HaveCoin(const COutPoint &outpoint) const { return base->HaveCoin(outpoint); }
uint256 CCoinsViewBacked::GetBestBlock() const { return base->GetBestBlock(); }
std::vector<uint256> CCoinsViewBacked::GetHeadBlocks() const { return base->GetHeadBlocks(); }
void CCoinsViewBacked::SetBackend(CCoinsView &viewIn) { base = &viewIn; }
bool CCoinsViewBacked::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock, bool erase) { return base->BatchWrite(mapCoins, hashBlock, erase); }
std::unique_ptr<CCoinsViewCursor> CCoinsViewBacked::Cursor() const { return base->Cursor(); }
size_t CCoinsViewBacked::EstimateSize() const { return base->EstimateSize(); }
CCoinsViewCache::CCoinsViewCache(CCoinsView* baseIn, bool deterministic) :
CCoinsViewBacked(baseIn), m_deterministic(deterministic),
cacheCoins(0, SaltedOutpointHasher(/*deterministic=*/deterministic), CCoinsMap::key_equal{}, &m_cache_coins_memory_resource)
{}
size_t CCoinsViewCache::DynamicMemoryUsage() const {
return memusage::DynamicUsage(cacheCoins) + cachedCoinsUsage;
}
CCoinsMap::iterator CCoinsViewCache::FetchCoin(const COutPoint &outpoint) const {
CCoinsMap::iterator it = cacheCoins.find(outpoint);
if (it != cacheCoins.end())
return it;
Coin tmp;
if (!base->GetCoin(outpoint, tmp))
return cacheCoins.end();
CCoinsMap::iterator ret = cacheCoins.emplace(std::piecewise_construct, std::forward_as_tuple(outpoint), std::forward_as_tuple(std::move(tmp))).first;
if (ret->second.coin.IsSpent()) {
// The parent only has an empty entry for this outpoint; we can consider our
// version as fresh.
ret->second.flags = CCoinsCacheEntry::FRESH;
}
cachedCoinsUsage += ret->second.coin.DynamicMemoryUsage();
return ret;
}
bool CCoinsViewCache::GetCoin(const COutPoint &outpoint, Coin &coin) const {
CCoinsMap::const_iterator it = FetchCoin(outpoint);
if (it != cacheCoins.end()) {
coin = it->second.coin;
return !coin.IsSpent();
}
return false;
}
void CCoinsViewCache::AddCoin(const COutPoint &outpoint, Coin&& coin, bool possible_overwrite) {
assert(!coin.IsSpent());
if (coin.out.scriptPubKey.IsUnspendable()) return;
CCoinsMap::iterator it;
bool inserted;
std::tie(it, inserted) = cacheCoins.emplace(std::piecewise_construct, std::forward_as_tuple(outpoint), std::tuple<>());
bool fresh = false;
if (!inserted) {
cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage();
}
if (!possible_overwrite) {
if (!it->second.coin.IsSpent()) {
throw std::logic_error("Attempted to overwrite an unspent coin (when possible_overwrite is false)");
}
// If the coin exists in this cache as a spent coin and is DIRTY, then
// its spentness hasn't been flushed to the parent cache. We're
// re-adding the coin to this cache now but we can't mark it as FRESH.
// If we mark it FRESH and then spend it before the cache is flushed
// we would remove it from this cache and would never flush spentness
// to the parent cache.
//
// Re-adding a spent coin can happen in the case of a re-org (the coin
// is 'spent' when the block adding it is disconnected and then
// re-added when it is also added in a newly connected block).
//
// If the coin doesn't exist in the current cache, or is spent but not
// DIRTY, then it can be marked FRESH.
fresh = !(it->second.flags & CCoinsCacheEntry::DIRTY);
}
it->second.coin = std::move(coin);
it->second.flags |= CCoinsCacheEntry::DIRTY | (fresh ? CCoinsCacheEntry::FRESH : 0);
cachedCoinsUsage += it->second.coin.DynamicMemoryUsage();
TRACE5(utxocache, add,
outpoint.hash.data(),
(uint32_t)outpoint.n,
(uint32_t)it->second.coin.nHeight,
(int64_t)it->second.coin.out.nValue,
(bool)it->second.coin.IsCoinBase());
}
void CCoinsViewCache::EmplaceCoinInternalDANGER(COutPoint&& outpoint, Coin&& coin) {
cachedCoinsUsage += coin.DynamicMemoryUsage();
cacheCoins.emplace(
std::piecewise_construct,
std::forward_as_tuple(std::move(outpoint)),
std::forward_as_tuple(std::move(coin), CCoinsCacheEntry::DIRTY));
}
void AddCoins(CCoinsViewCache& cache, const CTransaction &tx, int nHeight, bool check_for_overwrite) {
bool fCoinbase = tx.IsCoinBase();
const uint256& txid = tx.GetHash();
for (size_t i = 0; i < tx.vout.size(); ++i) {
bool overwrite = check_for_overwrite ? cache.HaveCoin(COutPoint(txid, i)) : fCoinbase;
// Coinbase transactions can always be overwritten, in order to correctly
// deal with the pre-BIP30 occurrences of duplicate coinbase transactions.
cache.AddCoin(COutPoint(txid, i), Coin(tx.vout[i], nHeight, fCoinbase), overwrite);
}
}
bool CCoinsViewCache::SpendCoin(const COutPoint &outpoint, Coin* moveout) {
CCoinsMap::iterator it = FetchCoin(outpoint);
if (it == cacheCoins.end()) return false;
cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage();
TRACE5(utxocache, spent,
outpoint.hash.data(),
(uint32_t)outpoint.n,
(uint32_t)it->second.coin.nHeight,
(int64_t)it->second.coin.out.nValue,
(bool)it->second.coin.IsCoinBase());
if (moveout) {
*moveout = std::move(it->second.coin);
}
if (it->second.flags & CCoinsCacheEntry::FRESH) {
cacheCoins.erase(it);
} else {
it->second.flags |= CCoinsCacheEntry::DIRTY;
it->second.coin.Clear();
}
return true;
}
static const Coin coinEmpty;
const Coin& CCoinsViewCache::AccessCoin(const COutPoint &outpoint) const {
CCoinsMap::const_iterator it = FetchCoin(outpoint);
if (it == cacheCoins.end()) {
return coinEmpty;
} else {
return it->second.coin;
}
}
bool CCoinsViewCache::HaveCoin(const COutPoint &outpoint) const {
CCoinsMap::const_iterator it = FetchCoin(outpoint);
return (it != cacheCoins.end() && !it->second.coin.IsSpent());
}
bool CCoinsViewCache::HaveCoinInCache(const COutPoint &outpoint) const {
CCoinsMap::const_iterator it = cacheCoins.find(outpoint);
return (it != cacheCoins.end() && !it->second.coin.IsSpent());
}
uint256 CCoinsViewCache::GetBestBlock() const {
if (hashBlock.IsNull())
hashBlock = base->GetBestBlock();
return hashBlock;
}
void CCoinsViewCache::SetBestBlock(const uint256 &hashBlockIn) {
hashBlock = hashBlockIn;
}
bool CCoinsViewCache::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlockIn, bool erase) {
for (CCoinsMap::iterator it = mapCoins.begin();
it != mapCoins.end();
it = erase ? mapCoins.erase(it) : std::next(it)) {
// Ignore non-dirty entries (optimization).
if (!(it->second.flags & CCoinsCacheEntry::DIRTY)) {
continue;
}
CCoinsMap::iterator itUs = cacheCoins.find(it->first);
if (itUs == cacheCoins.end()) {
// The parent cache does not have an entry, while the child cache does.
// We can ignore it if it's both spent and FRESH in the child
if (!(it->second.flags & CCoinsCacheEntry::FRESH && it->second.coin.IsSpent())) {
// Create the coin in the parent cache, move the data up
// and mark it as dirty.
CCoinsCacheEntry& entry = cacheCoins[it->first];
if (erase) {
// The `move` call here is purely an optimization; we rely on the
// `mapCoins.erase` call in the `for` expression to actually remove
// the entry from the child map.
entry.coin = std::move(it->second.coin);
} else {
entry.coin = it->second.coin;
}
cachedCoinsUsage += entry.coin.DynamicMemoryUsage();
entry.flags = CCoinsCacheEntry::DIRTY;
// We can mark it FRESH in the parent if it was FRESH in the child
// Otherwise it might have just been flushed from the parent's cache
// and already exist in the grandparent
if (it->second.flags & CCoinsCacheEntry::FRESH) {
entry.flags |= CCoinsCacheEntry::FRESH;
}
}
} else {
// Found the entry in the parent cache
if ((it->second.flags & CCoinsCacheEntry::FRESH) && !itUs->second.coin.IsSpent()) {
// The coin was marked FRESH in the child cache, but the coin
// exists in the parent cache. If this ever happens, it means
// the FRESH flag was misapplied and there is a logic error in
// the calling code.
throw std::logic_error("FRESH flag misapplied to coin that exists in parent cache");
}
if ((itUs->second.flags & CCoinsCacheEntry::FRESH) && it->second.coin.IsSpent()) {
// The grandparent cache does not have an entry, and the coin
// has been spent. We can just delete it from the parent cache.
cachedCoinsUsage -= itUs->second.coin.DynamicMemoryUsage();
cacheCoins.erase(itUs);
} else {
// A normal modification.
cachedCoinsUsage -= itUs->second.coin.DynamicMemoryUsage();
if (erase) {
// The `move` call here is purely an optimization; we rely on the
// `mapCoins.erase` call in the `for` expression to actually remove
// the entry from the child map.
itUs->second.coin = std::move(it->second.coin);
} else {
itUs->second.coin = it->second.coin;
}
cachedCoinsUsage += itUs->second.coin.DynamicMemoryUsage();
itUs->second.flags |= CCoinsCacheEntry::DIRTY;
// NOTE: It isn't safe to mark the coin as FRESH in the parent
// cache. If it already existed and was spent in the parent
// cache then marking it FRESH would prevent that spentness
// from being flushed to the grandparent.
}
}
}
hashBlock = hashBlockIn;
return true;
}
bool CCoinsViewCache::Flush() {
bool fOk = base->BatchWrite(cacheCoins, hashBlock, /*erase=*/true);
if (fOk) {
if (!cacheCoins.empty()) {
/* BatchWrite must erase all cacheCoins elements when erase=true. */
throw std::logic_error("Not all cached coins were erased");
}
ReallocateCache();
}
cachedCoinsUsage = 0;
return fOk;
}
bool CCoinsViewCache::Sync()
{
bool fOk = base->BatchWrite(cacheCoins, hashBlock, /*erase=*/false);
// Instead of clearing `cacheCoins` as we would in Flush(), just clear the
// FRESH/DIRTY flags of any coin that isn't spent.
for (auto it = cacheCoins.begin(); it != cacheCoins.end(); ) {
if (it->second.coin.IsSpent()) {
cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage();
it = cacheCoins.erase(it);
} else {
it->second.flags = 0;
++it;
}
}
return fOk;
}
void CCoinsViewCache::Uncache(const COutPoint& hash)
{
CCoinsMap::iterator it = cacheCoins.find(hash);
if (it != cacheCoins.end() && it->second.flags == 0) {
cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage();
TRACE5(utxocache, uncache,
hash.hash.data(),
(uint32_t)hash.n,
(uint32_t)it->second.coin.nHeight,
(int64_t)it->second.coin.out.nValue,
(bool)it->second.coin.IsCoinBase());
cacheCoins.erase(it);
}
}
unsigned int CCoinsViewCache::GetCacheSize() const {
return cacheCoins.size();
}
bool CCoinsViewCache::HaveInputs(const CTransaction& tx) const
{
if (!tx.IsCoinBase()) {
for (unsigned int i = 0; i < tx.vin.size(); i++) {
if (!HaveCoin(tx.vin[i].prevout)) {
return false;
}
}
}
return true;
}
void CCoinsViewCache::ReallocateCache()
{
// Cache should be empty when we're calling this.
assert(cacheCoins.size() == 0);
cacheCoins.~CCoinsMap();
m_cache_coins_memory_resource.~CCoinsMapMemoryResource();
::new (&m_cache_coins_memory_resource) CCoinsMapMemoryResource{};
::new (&cacheCoins) CCoinsMap{0, SaltedOutpointHasher{/*deterministic=*/m_deterministic}, CCoinsMap::key_equal{}, &m_cache_coins_memory_resource};
}
void CCoinsViewCache::SanityCheck() const
{
size_t recomputed_usage = 0;
for (const auto& [_, entry] : cacheCoins) {
unsigned attr = 0;
if (entry.flags & CCoinsCacheEntry::DIRTY) attr |= 1;
if (entry.flags & CCoinsCacheEntry::FRESH) attr |= 2;
if (entry.coin.IsSpent()) attr |= 4;
// Only 5 combinations are possible.
assert(attr != 2 && attr != 4 && attr != 7);
// Recompute cachedCoinsUsage.
recomputed_usage += entry.coin.DynamicMemoryUsage();
}
assert(recomputed_usage == cachedCoinsUsage);
}
static const size_t MIN_TRANSACTION_OUTPUT_WEIGHT = WITNESS_SCALE_FACTOR * ::GetSerializeSize(CTxOut());
static const size_t MAX_OUTPUTS_PER_BLOCK = MAX_BLOCK_WEIGHT / MIN_TRANSACTION_OUTPUT_WEIGHT;
const Coin& AccessByTxid(const CCoinsViewCache& view, const uint256& txid)
{
COutPoint iter(txid, 0);
while (iter.n < MAX_OUTPUTS_PER_BLOCK) {
const Coin& alternate = view.AccessCoin(iter);
if (!alternate.IsSpent()) return alternate;
++iter.n;
}
return coinEmpty;
}
template <typename Func>
static bool ExecuteBackedWrapper(Func func, const std::vector<std::function<void()>>& err_callbacks)
{
try {
return func();
} catch(const std::runtime_error& e) {
for (const auto& f : err_callbacks) {
f();
}
LogPrintf("Error reading from database: %s\n", e.what());
// Starting the shutdown sequence and returning false to the caller would be
// interpreted as 'entry not found' (as opposed to unable to read data), and
// could lead to invalid interpretation. Just exit immediately, as we can't
// continue anyway, and all writes should be atomic.
std::abort();
}
}
bool CCoinsViewErrorCatcher::GetCoin(const COutPoint &outpoint, Coin &coin) const {
return ExecuteBackedWrapper([&]() { return CCoinsViewBacked::GetCoin(outpoint, coin); }, m_err_callbacks);
}
bool CCoinsViewErrorCatcher::HaveCoin(const COutPoint &outpoint) const {
return ExecuteBackedWrapper([&]() { return CCoinsViewBacked::HaveCoin(outpoint); }, m_err_callbacks);
}
|