Branch data Line data Source code
1 : : // Copyright (c) 2012-2022 The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #include <coins.h>
6 : :
7 : : #include <consensus/consensus.h>
8 : : #include <logging.h>
9 : : #include <random.h>
10 : : #include <util/trace.h>
11 : :
12 : 760853 : bool CCoinsView::GetCoin(const COutPoint &outpoint, Coin &coin) const { return false; }
13 : 12656 : uint256 CCoinsView::GetBestBlock() const { return uint256(); }
14 : 8138 : std::vector<uint256> CCoinsView::GetHeadBlocks() const { return std::vector<uint256>(); }
15 : 139405 : bool CCoinsView::BatchWrite(CoinsViewCacheCursor& cursor, const uint256 &hashBlock) { return false; }
16 : 4069 : std::unique_ptr<CCoinsViewCursor> CCoinsView::Cursor() const { return nullptr; }
17 : :
18 : 4069 : bool CCoinsView::HaveCoin(const COutPoint &outpoint) const
19 : : {
20 : 4069 : Coin coin;
21 [ + - ]: 4069 : return GetCoin(outpoint, coin);
22 : 4069 : }
23 : :
24 : 2798833 : CCoinsViewBacked::CCoinsViewBacked(CCoinsView *viewIn) : base(viewIn) { }
25 : 1983488 : bool CCoinsViewBacked::GetCoin(const COutPoint &outpoint, Coin &coin) const { return base->GetCoin(outpoint, coin); }
26 : 0 : bool CCoinsViewBacked::HaveCoin(const COutPoint &outpoint) const { return base->HaveCoin(outpoint); }
27 : 344403 : uint256 CCoinsViewBacked::GetBestBlock() const { return base->GetBestBlock(); }
28 : 4069 : std::vector<uint256> CCoinsViewBacked::GetHeadBlocks() const { return base->GetHeadBlocks(); }
29 : 826671 : void CCoinsViewBacked::SetBackend(CCoinsView &viewIn) { base = &viewIn; }
30 : 169916 : bool CCoinsViewBacked::BatchWrite(CoinsViewCacheCursor& cursor, const uint256 &hashBlock) { return base->BatchWrite(cursor, hashBlock); }
31 : 0 : std::unique_ptr<CCoinsViewCursor> CCoinsViewBacked::Cursor() const { return base->Cursor(); }
32 : 4069 : size_t CCoinsViewBacked::EstimateSize() const { return base->EstimateSize(); }
33 : :
34 [ + - + - ]: 3064676 : CCoinsViewCache::CCoinsViewCache(CCoinsView* baseIn, bool deterministic) :
35 : 3064676 : CCoinsViewBacked(baseIn), m_deterministic(deterministic),
36 : : cacheCoins(0, SaltedOutpointHasher(/*deterministic=*/deterministic), CCoinsMap::key_equal{}, &m_cache_coins_memory_resource)
37 : 1532338 : {
38 : 1532338 : m_sentinel.second.SelfRef(m_sentinel);
39 : 0 : }
40 : :
41 : 3259549 : size_t CCoinsViewCache::DynamicMemoryUsage() const {
42 : 3259549 : return memusage::DynamicUsage(cacheCoins) + cachedCoinsUsage;
43 : : }
44 : :
45 : 43261062 : CCoinsMap::iterator CCoinsViewCache::FetchCoin(const COutPoint &outpoint) const {
46 : 43261062 : const auto [ret, inserted] = cacheCoins.try_emplace(outpoint);
47 [ + + ]: 43261062 : if (inserted) {
48 [ + + + + ]: 16476480 : if (!base->GetCoin(outpoint, ret->second.coin)) {
49 : 8284828 : cacheCoins.erase(ret);
50 : 4142414 : return cacheCoins.end();
51 : : }
52 [ + + ]: 4095826 : if (ret->second.coin.IsSpent()) {
53 : : // The parent only has an empty entry for this outpoint; we can consider our version as fresh.
54 : 99638 : ret->second.AddFlags(CCoinsCacheEntry::FRESH, *ret, m_sentinel);
55 : 49819 : }
56 : 4095826 : cachedCoinsUsage += ret->second.coin.DynamicMemoryUsage();
57 : 4095826 : }
58 : 39118648 : return ret;
59 : 43261062 : }
60 : :
61 : 23395140 : bool CCoinsViewCache::GetCoin(const COutPoint &outpoint, Coin &coin) const {
62 : 23395140 : CCoinsMap::const_iterator it = FetchCoin(outpoint);
63 [ + + ]: 23395140 : if (it != cacheCoins.end()) {
64 : 21203867 : coin = it->second.coin;
65 : 21203867 : return !coin.IsSpent();
66 : : }
67 : 2191273 : return false;
68 : 23395140 : }
69 : :
70 : 3005882 : void CCoinsViewCache::AddCoin(const COutPoint &outpoint, Coin&& coin, bool possible_overwrite) {
71 [ + - ]: 3005882 : assert(!coin.IsSpent());
72 [ + + ]: 3005882 : if (coin.out.scriptPubKey.IsUnspendable()) return;
73 : 2687493 : CCoinsMap::iterator it;
74 : 2687493 : bool inserted;
75 : 2687493 : std::tie(it, inserted) = cacheCoins.emplace(std::piecewise_construct, std::forward_as_tuple(outpoint), std::tuple<>());
76 : 2687493 : bool fresh = false;
77 [ + + ]: 2687493 : if (!inserted) {
78 : 80636 : cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage();
79 : 80636 : }
80 [ + + ]: 2687493 : if (!possible_overwrite) {
81 [ + + ]: 2126303 : if (!it->second.coin.IsSpent()) {
82 [ + - ]: 14866 : throw std::logic_error("Attempted to overwrite an unspent coin (when possible_overwrite is false)");
83 : : }
84 : : // If the coin exists in this cache as a spent coin and is DIRTY, then
85 : : // its spentness hasn't been flushed to the parent cache. We're
86 : : // re-adding the coin to this cache now but we can't mark it as FRESH.
87 : : // If we mark it FRESH and then spend it before the cache is flushed
88 : : // we would remove it from this cache and would never flush spentness
89 : : // to the parent cache.
90 : : //
91 : : // Re-adding a spent coin can happen in the case of a re-org (the coin
92 : : // is 'spent' when the block adding it is disconnected and then
93 : : // re-added when it is also added in a newly connected block).
94 : : //
95 : : // If the coin doesn't exist in the current cache, or is spent but not
96 : : // DIRTY, then it can be marked FRESH.
97 : 2111437 : fresh = !it->second.IsDirty();
98 : 2111437 : }
99 : 2672627 : it->second.coin = std::move(coin);
100 : 2672627 : it->second.AddFlags(CCoinsCacheEntry::DIRTY | (fresh ? CCoinsCacheEntry::FRESH : 0), *it, m_sentinel);
101 : 2672627 : cachedCoinsUsage += it->second.coin.DynamicMemoryUsage();
102 : : TRACE5(utxocache, add,
103 : : outpoint.hash.data(),
104 : : (uint32_t)outpoint.n,
105 : : (uint32_t)it->second.coin.nHeight,
106 : : (int64_t)it->second.coin.out.nValue,
107 : : (bool)it->second.coin.IsCoinBase());
108 : 2991016 : }
109 : :
110 : 43596 : void CCoinsViewCache::EmplaceCoinInternalDANGER(COutPoint&& outpoint, Coin&& coin) {
111 : 43596 : cachedCoinsUsage += coin.DynamicMemoryUsage();
112 : 87192 : auto [it, inserted] = cacheCoins.emplace(
113 : : std::piecewise_construct,
114 : 43596 : std::forward_as_tuple(std::move(outpoint)),
115 : 43596 : std::forward_as_tuple(std::move(coin)));
116 [ + + ]: 43596 : if (inserted) {
117 : 53292 : it->second.AddFlags(CCoinsCacheEntry::DIRTY, *it, m_sentinel);
118 : 26646 : }
119 : 43596 : }
120 : :
121 : 423992 : void AddCoins(CCoinsViewCache& cache, const CTransaction &tx, int nHeight, bool check_for_overwrite) {
122 : 423992 : bool fCoinbase = tx.IsCoinBase();
123 : 423992 : const Txid& txid = tx.GetHash();
124 [ + + ]: 3178694 : for (size_t i = 0; i < tx.vout.size(); ++i) {
125 [ + + ]: 2754702 : bool overwrite = check_for_overwrite ? cache.HaveCoin(COutPoint(txid, i)) : fCoinbase;
126 : : // Coinbase transactions can always be overwritten, in order to correctly
127 : : // deal with the pre-BIP30 occurrences of duplicate coinbase transactions.
128 [ + + ]: 2754702 : cache.AddCoin(COutPoint(txid, i), Coin(tx.vout[i], nHeight, fCoinbase), overwrite);
129 : 2754702 : }
130 : 423998 : }
131 : :
132 : 357652 : bool CCoinsViewCache::SpendCoin(const COutPoint &outpoint, Coin* moveout) {
133 : 357652 : CCoinsMap::iterator it = FetchCoin(outpoint);
134 [ + + ]: 357652 : if (it == cacheCoins.end()) return false;
135 : 302053 : cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage();
136 : : TRACE5(utxocache, spent,
137 : : outpoint.hash.data(),
138 : : (uint32_t)outpoint.n,
139 : : (uint32_t)it->second.coin.nHeight,
140 : : (int64_t)it->second.coin.out.nValue,
141 : : (bool)it->second.coin.IsCoinBase());
142 [ + + ]: 302053 : if (moveout) {
143 : 130851 : *moveout = std::move(it->second.coin);
144 : 130851 : }
145 [ + + ]: 302053 : if (it->second.IsFresh()) {
146 : 59876 : cacheCoins.erase(it);
147 : 59876 : } else {
148 : 242177 : it->second.AddFlags(CCoinsCacheEntry::DIRTY, *it, m_sentinel);
149 : 242177 : it->second.coin.Clear();
150 : : }
151 : 302053 : return true;
152 : 357652 : }
153 : :
154 : 1 : static const Coin coinEmpty;
155 : :
156 : 11369049 : const Coin& CCoinsViewCache::AccessCoin(const COutPoint &outpoint) const {
157 : 11369049 : CCoinsMap::const_iterator it = FetchCoin(outpoint);
158 [ + + ]: 11369049 : if (it == cacheCoins.end()) {
159 : 256421 : return coinEmpty;
160 : : } else {
161 : 11112628 : return it->second.coin;
162 : : }
163 : 11369049 : }
164 : :
165 : 8139221 : bool CCoinsViewCache::HaveCoin(const COutPoint &outpoint) const {
166 : 8139221 : CCoinsMap::const_iterator it = FetchCoin(outpoint);
167 [ + + ]: 8139221 : return (it != cacheCoins.end() && !it->second.coin.IsSpent());
168 : 8139221 : }
169 : :
170 : 4554406 : bool CCoinsViewCache::HaveCoinInCache(const COutPoint &outpoint) const {
171 : 4554406 : CCoinsMap::const_iterator it = cacheCoins.find(outpoint);
172 [ + + ]: 4554406 : return (it != cacheCoins.end() && !it->second.coin.IsSpent());
173 : 4554406 : }
174 : :
175 : 1910305 : uint256 CCoinsViewCache::GetBestBlock() const {
176 [ + + ]: 1910305 : if (hashBlock.IsNull())
177 : 670289 : hashBlock = base->GetBestBlock();
178 : 1910305 : return hashBlock;
179 : : }
180 : :
181 : 131368 : void CCoinsViewCache::SetBestBlock(const uint256 &hashBlockIn) {
182 : 131368 : hashBlock = hashBlockIn;
183 : 131368 : }
184 : :
185 : 245452 : bool CCoinsViewCache::BatchWrite(CoinsViewCacheCursor& cursor, const uint256 &hashBlockIn) {
186 [ + + ]: 633532 : for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) {
187 : : // Ignore non-dirty entries (optimization).
188 [ + + ]: 396781 : if (!it->second.IsDirty()) {
189 : 403 : continue;
190 : : }
191 : 396378 : CCoinsMap::iterator itUs = cacheCoins.find(it->first);
192 [ + + ]: 396378 : if (itUs == cacheCoins.end()) {
193 : : // The parent cache does not have an entry, while the child cache does.
194 : : // We can ignore it if it's both spent and FRESH in the child
195 [ + + + + ]: 319922 : if (!(it->second.IsFresh() && it->second.coin.IsSpent())) {
196 : : // Create the coin in the parent cache, move the data up
197 : : // and mark it as dirty.
198 : 319019 : itUs = cacheCoins.try_emplace(it->first).first;
199 : 319019 : CCoinsCacheEntry& entry{itUs->second};
200 [ + + ]: 319019 : if (cursor.WillErase(*it)) {
201 : : // Since this entry will be erased,
202 : : // we can move the coin into us instead of copying it
203 : 191395 : entry.coin = std::move(it->second.coin);
204 : 191395 : } else {
205 : 127624 : entry.coin = it->second.coin;
206 : : }
207 : 319019 : cachedCoinsUsage += entry.coin.DynamicMemoryUsage();
208 : 319019 : entry.AddFlags(CCoinsCacheEntry::DIRTY, *itUs, m_sentinel);
209 : : // We can mark it FRESH in the parent if it was FRESH in the child
210 : : // Otherwise it might have just been flushed from the parent's cache
211 : : // and already exist in the grandparent
212 [ + + ]: 319019 : if (it->second.IsFresh()) {
213 : 32826 : entry.AddFlags(CCoinsCacheEntry::FRESH, *itUs, m_sentinel);
214 : 32826 : }
215 : 319019 : }
216 : 319922 : } else {
217 : : // Found the entry in the parent cache
218 [ + + + + ]: 76456 : if (it->second.IsFresh() && !itUs->second.coin.IsSpent()) {
219 : : // The coin was marked FRESH in the child cache, but the coin
220 : : // exists in the parent cache. If this ever happens, it means
221 : : // the FRESH flag was misapplied and there is a logic error in
222 : : // the calling code.
223 [ + - ]: 8701 : throw std::logic_error("FRESH flag misapplied to coin that exists in parent cache");
224 : : }
225 : :
226 [ + + + + ]: 67755 : if (itUs->second.IsFresh() && it->second.coin.IsSpent()) {
227 : : // The grandparent cache does not have an entry, and the coin
228 : : // has been spent. We can just delete it from the parent cache.
229 : 3014 : cachedCoinsUsage -= itUs->second.coin.DynamicMemoryUsage();
230 : 3014 : cacheCoins.erase(itUs);
231 : 3014 : } else {
232 : : // A normal modification.
233 : 64741 : cachedCoinsUsage -= itUs->second.coin.DynamicMemoryUsage();
234 [ + + ]: 64741 : if (cursor.WillErase(*it)) {
235 : : // Since this entry will be erased,
236 : : // we can move the coin into us instead of copying it
237 : 41218 : itUs->second.coin = std::move(it->second.coin);
238 : 41218 : } else {
239 : 23523 : itUs->second.coin = it->second.coin;
240 : : }
241 : 64741 : cachedCoinsUsage += itUs->second.coin.DynamicMemoryUsage();
242 : 64741 : itUs->second.AddFlags(CCoinsCacheEntry::DIRTY, *itUs, m_sentinel);
243 : : // NOTE: It isn't safe to mark the coin as FRESH in the parent
244 : : // cache. If it already existed and was spent in the parent
245 : : // cache then marking it FRESH would prevent that spentness
246 : : // from being flushed to the grandparent.
247 : : }
248 : : }
249 : 387677 : }
250 : 236751 : hashBlock = hashBlockIn;
251 : 236751 : return true;
252 : 0 : }
253 : :
254 : 445529 : bool CCoinsViewCache::Flush() {
255 : 445529 : auto cursor{CoinsViewCacheCursor(cachedCoinsUsage, m_sentinel, cacheCoins, /*will_erase=*/true)};
256 : 445529 : bool fOk = base->BatchWrite(cursor, hashBlock);
257 [ + + ]: 445529 : if (fOk) {
258 : 397199 : cacheCoins.clear();
259 : 397199 : ReallocateCache();
260 : 397199 : }
261 : 445529 : cachedCoinsUsage = 0;
262 : 891058 : return fOk;
263 : 445529 : }
264 : :
265 : 160923 : bool CCoinsViewCache::Sync()
266 : : {
267 : 160923 : auto cursor{CoinsViewCacheCursor(cachedCoinsUsage, m_sentinel, cacheCoins, /*will_erase=*/false)};
268 : 160923 : bool fOk = base->BatchWrite(cursor, hashBlock);
269 [ + + ]: 160923 : if (fOk) {
270 [ + - ]: 69848 : if (m_sentinel.second.Next() != &m_sentinel) {
271 : : /* BatchWrite must clear flags of all entries */
272 [ # # ]: 0 : throw std::logic_error("Not all unspent flagged entries were cleared");
273 : : }
274 : 69848 : }
275 : 321846 : return fOk;
276 : 160923 : }
277 : :
278 : 2201139 : void CCoinsViewCache::Uncache(const COutPoint& hash)
279 : : {
280 : 2201139 : CCoinsMap::iterator it = cacheCoins.find(hash);
281 [ + + + + : 2201139 : if (it != cacheCoins.end() && !it->second.IsDirty() && !it->second.IsFresh()) {
+ + ]
282 : 81199 : cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage();
283 : : TRACE5(utxocache, uncache,
284 : : hash.hash.data(),
285 : : (uint32_t)hash.n,
286 : : (uint32_t)it->second.coin.nHeight,
287 : : (int64_t)it->second.coin.out.nValue,
288 : : (bool)it->second.coin.IsCoinBase());
289 : 81199 : cacheCoins.erase(it);
290 : 81199 : }
291 : 2201139 : }
292 : :
293 : 1887325 : unsigned int CCoinsViewCache::GetCacheSize() const {
294 : 1887325 : return cacheCoins.size();
295 : : }
296 : :
297 : 442677 : bool CCoinsViewCache::HaveInputs(const CTransaction& tx) const
298 : : {
299 [ + + ]: 442677 : if (!tx.IsCoinBase()) {
300 [ + + - + : 3061165 : for (unsigned int i = 0; i < tx.vin.size(); i++) {
+ ]
301 [ + + ]: 2618754 : if (!HaveCoin(tx.vin[i].prevout)) {
302 : 10037 : return false;
303 : : }
304 : 2608717 : }
305 : 432374 : }
306 : 432640 : return true;
307 : 442677 : }
308 : :
309 : 440381 : void CCoinsViewCache::ReallocateCache()
310 : : {
311 : : // Cache should be empty when we're calling this.
312 [ + - ]: 440381 : assert(cacheCoins.size() == 0);
313 : 440381 : cacheCoins.~CCoinsMap();
314 : 440381 : m_cache_coins_memory_resource.~CCoinsMapMemoryResource();
315 : 440381 : ::new (&m_cache_coins_memory_resource) CCoinsMapMemoryResource{};
316 : 440381 : ::new (&cacheCoins) CCoinsMap{0, SaltedOutpointHasher{/*deterministic=*/m_deterministic}, CCoinsMap::key_equal{}, &m_cache_coins_memory_resource};
317 : 440381 : }
318 : :
319 : 54503 : void CCoinsViewCache::SanityCheck() const
320 : : {
321 : 54503 : size_t recomputed_usage = 0;
322 : 54503 : size_t count_flagged = 0;
323 [ + + ]: 418935 : for (const auto& [_, entry] : cacheCoins) {
324 : 150050 : unsigned attr = 0;
325 [ + + ]: 150050 : if (entry.IsDirty()) attr |= 1;
326 [ + + ]: 150050 : if (entry.IsFresh()) attr |= 2;
327 [ + + ]: 150050 : if (entry.coin.IsSpent()) attr |= 4;
328 : : // Only 5 combinations are possible.
329 [ + - - + : 150050 : assert(attr != 2 && attr != 4 && attr != 7);
+ - ]
330 : :
331 : : // Recompute cachedCoinsUsage.
332 : 150050 : recomputed_usage += entry.coin.DynamicMemoryUsage();
333 : :
334 : : // Count the number of entries we expect in the linked list.
335 [ + + + + ]: 150050 : if (entry.IsDirty() || entry.IsFresh()) ++count_flagged;
336 : 150050 : }
337 : : // Iterate over the linked list of flagged entries.
338 : 54503 : size_t count_linked = 0;
339 [ + + ]: 84090 : for (auto it = m_sentinel.second.Next(); it != &m_sentinel; it = it->second.Next()) {
340 : : // Verify linked list integrity.
341 [ + - ]: 29587 : assert(it->second.Next()->second.Prev() == it);
342 [ - + ]: 29587 : assert(it->second.Prev()->second.Next() == it);
343 : : // Verify they are actually flagged.
344 [ + + + - ]: 29587 : assert(it->second.IsDirty() || it->second.IsFresh());
345 : : // Count the number of entries actually in the list.
346 : 29587 : ++count_linked;
347 : 29587 : }
348 [ + - ]: 54503 : assert(count_linked == count_flagged);
349 [ + - ]: 54503 : assert(recomputed_usage == cachedCoinsUsage);
350 : 54503 : }
351 : :
352 [ + - ]: 1 : static const size_t MIN_TRANSACTION_OUTPUT_WEIGHT = WITNESS_SCALE_FACTOR * ::GetSerializeSize(CTxOut());
353 : 1 : static const size_t MAX_OUTPUTS_PER_BLOCK = MAX_BLOCK_WEIGHT / MIN_TRANSACTION_OUTPUT_WEIGHT;
354 : :
355 : 0 : const Coin& AccessByTxid(const CCoinsViewCache& view, const Txid& txid)
356 : : {
357 : 0 : COutPoint iter(txid, 0);
358 [ # # ]: 0 : while (iter.n < MAX_OUTPUTS_PER_BLOCK) {
359 : 0 : const Coin& alternate = view.AccessCoin(iter);
360 [ # # ]: 0 : if (!alternate.IsSpent()) return alternate;
361 : 0 : ++iter.n;
362 [ # # ]: 0 : }
363 : 0 : return coinEmpty;
364 : 0 : }
365 : :
366 : : template <typename Func>
367 : 1983488 : static bool ExecuteBackedWrapper(Func func, const std::vector<std::function<void()>>& err_callbacks)
368 : : {
369 : : try {
370 [ + - # # ]: 1983488 : return func();
371 [ # # # # ]: 0 : } catch(const std::runtime_error& e) {
372 [ # # # # ]: 0 : for (const auto& f : err_callbacks) {
373 [ # # # # ]: 0 : f();
374 : 0 : }
375 [ # # # # ]: 0 : LogError("Error reading from database: %s\n", e.what());
376 : : // Starting the shutdown sequence and returning false to the caller would be
377 : : // interpreted as 'entry not found' (as opposed to unable to read data), and
378 : : // could lead to invalid interpretation. Just exit immediately, as we can't
379 : : // continue anyway, and all writes should be atomic.
380 : 0 : std::abort();
381 [ # # # # ]: 0 : }
382 : 0 : }
383 : :
384 : 1983488 : bool CCoinsViewErrorCatcher::GetCoin(const COutPoint &outpoint, Coin &coin) const {
385 : 3966976 : return ExecuteBackedWrapper([&]() { return CCoinsViewBacked::GetCoin(outpoint, coin); }, m_err_callbacks);
386 : : }
387 : :
388 : 0 : bool CCoinsViewErrorCatcher::HaveCoin(const COutPoint &outpoint) const {
389 : 0 : return ExecuteBackedWrapper([&]() { return CCoinsViewBacked::HaveCoin(outpoint); }, m_err_callbacks);
390 : : }
|