Branch data Line data Source code
1 : : // Copyright (c) 2012-present 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 : : TRACEPOINT_SEMAPHORE(utxocache, add);
13 : : TRACEPOINT_SEMAPHORE(utxocache, spent);
14 : : TRACEPOINT_SEMAPHORE(utxocache, uncache);
15 : :
16 : 28 : std::optional<Coin> CCoinsView::GetCoin(const COutPoint& outpoint) const { return std::nullopt; }
17 : 0 : uint256 CCoinsView::GetBestBlock() const { return uint256(); }
18 : 0 : std::vector<uint256> CCoinsView::GetHeadBlocks() const { return std::vector<uint256>(); }
19 : 0 : void CCoinsView::BatchWrite(CoinsViewCacheCursor& cursor, const uint256& hashBlock)
20 : : {
21 [ # # ]: 0 : for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) { }
22 : 0 : }
23 : :
24 : 0 : std::unique_ptr<CCoinsViewCursor> CCoinsView::Cursor() const { return nullptr; }
25 : :
26 : 0 : bool CCoinsView::HaveCoin(const COutPoint &outpoint) const
27 : : {
28 : 0 : return GetCoin(outpoint).has_value();
29 : : }
30 : :
31 : 577351 : CCoinsViewBacked::CCoinsViewBacked(CCoinsView *viewIn) : base(viewIn) { }
32 : 1334500 : std::optional<Coin> CCoinsViewBacked::GetCoin(const COutPoint& outpoint) const { return base->GetCoin(outpoint); }
33 : 0 : bool CCoinsViewBacked::HaveCoin(const COutPoint &outpoint) const { return base->HaveCoin(outpoint); }
34 : 34390 : uint256 CCoinsViewBacked::GetBestBlock() const { return base->GetBestBlock(); }
35 : 0 : std::vector<uint256> CCoinsViewBacked::GetHeadBlocks() const { return base->GetHeadBlocks(); }
36 : 70520 : void CCoinsViewBacked::SetBackend(CCoinsView &viewIn) { base = &viewIn; }
37 : 3495 : void CCoinsViewBacked::BatchWrite(CoinsViewCacheCursor& cursor, const uint256& hashBlock) { base->BatchWrite(cursor, hashBlock); }
38 : 0 : std::unique_ptr<CCoinsViewCursor> CCoinsViewBacked::Cursor() const { return base->Cursor(); }
39 : 0 : size_t CCoinsViewBacked::EstimateSize() const { return base->EstimateSize(); }
40 : :
41 : 535874 : CCoinsViewCache::CCoinsViewCache(CCoinsView* baseIn, bool deterministic) :
42 : 535874 : CCoinsViewBacked(baseIn), m_deterministic(deterministic),
43 [ + - + - ]: 535874 : cacheCoins(0, SaltedOutpointHasher(/*deterministic=*/deterministic), CCoinsMap::key_equal{}, &m_cache_coins_memory_resource)
44 : : {
45 : 535874 : m_sentinel.second.SelfRef(m_sentinel);
46 : 535874 : }
47 : :
48 : 1165552 : size_t CCoinsViewCache::DynamicMemoryUsage() const {
49 : 1165552 : return memusage::DynamicUsage(cacheCoins) + cachedCoinsUsage;
50 : : }
51 : :
52 : 100700443 : CCoinsMap::iterator CCoinsViewCache::FetchCoin(const COutPoint &outpoint) const {
53 [ + + ]: 100700443 : const auto [ret, inserted] = cacheCoins.try_emplace(outpoint);
54 [ + + ]: 100700443 : if (inserted) {
55 [ + + ]: 42834021 : if (auto coin{base->GetCoin(outpoint)}) {
56 : 14653416 : ret->second.coin = std::move(*coin);
57 [ + + ]: 14653416 : cachedCoinsUsage += ret->second.coin.DynamicMemoryUsage();
58 [ + + ]: 14653416 : if (ret->second.coin.IsSpent()) { // TODO GetCoin cannot return spent coins
59 : : // The parent only has an empty entry for this outpoint; we can consider our version as fresh.
60 : 177109 : CCoinsCacheEntry::SetFresh(*ret, m_sentinel);
61 : : }
62 : : } else {
63 : 28180605 : cacheCoins.erase(ret);
64 : 28180605 : return cacheCoins.end();
65 : 42834021 : }
66 : : }
67 : 72519838 : return ret;
68 : : }
69 : :
70 : 30632940 : std::optional<Coin> CCoinsViewCache::GetCoin(const COutPoint& outpoint) const
71 : : {
72 [ + + + + ]: 30632940 : if (auto it{FetchCoin(outpoint)}; it != cacheCoins.end() && !it->second.coin.IsSpent()) return it->second.coin;
73 : 16328223 : return std::nullopt;
74 : : }
75 : :
76 : 22118713 : void CCoinsViewCache::AddCoin(const COutPoint &outpoint, Coin&& coin, bool possible_overwrite) {
77 [ - + ]: 22118713 : assert(!coin.IsSpent());
78 [ + + ]: 22118713 : if (coin.out.scriptPubKey.IsUnspendable()) return;
79 : 21792057 : CCoinsMap::iterator it;
80 : 21792057 : bool inserted;
81 [ + + ]: 21792057 : std::tie(it, inserted) = cacheCoins.emplace(std::piecewise_construct, std::forward_as_tuple(outpoint), std::tuple<>());
82 : 21792057 : bool fresh = false;
83 [ + + ]: 21792057 : if (!possible_overwrite) {
84 [ + + ]: 21564159 : if (!it->second.coin.IsSpent()) {
85 [ + - ]: 17 : throw std::logic_error("Attempted to overwrite an unspent coin (when possible_overwrite is false)");
86 : : }
87 : : // If the coin exists in this cache as a spent coin and is DIRTY, then
88 : : // its spentness hasn't been flushed to the parent cache. We're
89 : : // re-adding the coin to this cache now but we can't mark it as FRESH.
90 : : // If we mark it FRESH and then spend it before the cache is flushed
91 : : // we would remove it from this cache and would never flush spentness
92 : : // to the parent cache.
93 : : //
94 : : // Re-adding a spent coin can happen in the case of a re-org (the coin
95 : : // is 'spent' when the block adding it is disconnected and then
96 : : // re-added when it is also added in a newly connected block).
97 : : //
98 : : // If the coin doesn't exist in the current cache, or is spent but not
99 : : // DIRTY, then it can be marked FRESH.
100 : 21564142 : fresh = !it->second.IsDirty();
101 : : }
102 [ + + ]: 21792040 : if (!inserted) {
103 [ + + ]: 16709 : cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage();
104 : : }
105 : 21792040 : it->second.coin = std::move(coin);
106 : 21792040 : CCoinsCacheEntry::SetDirty(*it, m_sentinel);
107 [ + + ]: 21792040 : if (fresh) CCoinsCacheEntry::SetFresh(*it, m_sentinel);
108 [ + + ]: 21886930 : cachedCoinsUsage += it->second.coin.DynamicMemoryUsage();
109 : : TRACEPOINT(utxocache, add,
110 : : outpoint.hash.data(),
111 : : (uint32_t)outpoint.n,
112 : : (uint32_t)it->second.coin.nHeight,
113 : : (int64_t)it->second.coin.out.nValue,
114 : 22118696 : (bool)it->second.coin.IsCoinBase());
115 : : }
116 : :
117 : 6349 : void CCoinsViewCache::EmplaceCoinInternalDANGER(COutPoint&& outpoint, Coin&& coin) {
118 [ + + ]: 6349 : const auto mem_usage{coin.DynamicMemoryUsage()};
119 [ + + ]: 6349 : auto [it, inserted] = cacheCoins.try_emplace(std::move(outpoint), std::move(coin));
120 [ + + ]: 6349 : if (inserted) {
121 : 6348 : CCoinsCacheEntry::SetDirty(*it, m_sentinel);
122 : 6348 : cachedCoinsUsage += mem_usage;
123 : : }
124 : 6349 : }
125 : :
126 : 11109679 : void AddCoins(CCoinsViewCache& cache, const CTransaction &tx, int nHeight, bool check_for_overwrite) {
127 : 11109679 : bool fCoinbase = tx.IsCoinBase();
128 : 11109679 : const Txid& txid = tx.GetHash();
129 [ - + + + ]: 33101218 : for (size_t i = 0; i < tx.vout.size(); ++i) {
130 [ - + ]: 21991539 : bool overwrite = check_for_overwrite ? cache.HaveCoin(COutPoint(txid, i)) : fCoinbase;
131 : : // Coinbase transactions can always be overwritten, in order to correctly
132 : : // deal with the pre-BIP30 occurrences of duplicate coinbase transactions.
133 [ + - ]: 43983078 : cache.AddCoin(COutPoint(txid, i), Coin(tx.vout[i], nHeight, fCoinbase), overwrite);
134 : : }
135 : 11109679 : }
136 : :
137 : 14126059 : bool CCoinsViewCache::SpendCoin(const COutPoint &outpoint, Coin* moveout) {
138 : 14126059 : CCoinsMap::iterator it = FetchCoin(outpoint);
139 [ + + ]: 14126059 : if (it == cacheCoins.end()) return false;
140 [ + + ]: 14126053 : cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage();
141 : : TRACEPOINT(utxocache, spent,
142 : : outpoint.hash.data(),
143 : : (uint32_t)outpoint.n,
144 : : (uint32_t)it->second.coin.nHeight,
145 : : (int64_t)it->second.coin.out.nValue,
146 : 14126053 : (bool)it->second.coin.IsCoinBase());
147 [ + + ]: 14126053 : if (moveout) {
148 : 168576 : *moveout = std::move(it->second.coin);
149 : : }
150 [ + + ]: 14126053 : if (it->second.IsFresh()) {
151 : 240777 : cacheCoins.erase(it);
152 : : } else {
153 : 13885276 : CCoinsCacheEntry::SetDirty(*it, m_sentinel);
154 : 13885276 : it->second.coin.Clear();
155 : : }
156 : : return true;
157 : : }
158 : :
159 : : static const Coin coinEmpty;
160 : :
161 : 26188572 : const Coin& CCoinsViewCache::AccessCoin(const COutPoint &outpoint) const {
162 [ + + ]: 26188572 : CCoinsMap::const_iterator it = FetchCoin(outpoint);
163 [ + + ]: 26188572 : if (it == cacheCoins.end()) {
164 : : return coinEmpty;
165 : : } else {
166 : 15270353 : return it->second.coin;
167 : : }
168 : : }
169 : :
170 : 29752872 : bool CCoinsViewCache::HaveCoin(const COutPoint &outpoint) const {
171 [ + + ]: 29752872 : CCoinsMap::const_iterator it = FetchCoin(outpoint);
172 [ + + + + ]: 29752872 : return (it != cacheCoins.end() && !it->second.coin.IsSpent());
173 : : }
174 : :
175 : 297942 : bool CCoinsViewCache::HaveCoinInCache(const COutPoint &outpoint) const {
176 [ + + ]: 297942 : CCoinsMap::const_iterator it = cacheCoins.find(outpoint);
177 [ + + + + ]: 297942 : return (it != cacheCoins.end() && !it->second.coin.IsSpent());
178 : : }
179 : :
180 : 508240 : uint256 CCoinsViewCache::GetBestBlock() const {
181 [ + + ]: 1016480 : if (hashBlock.IsNull())
182 : 233042 : hashBlock = base->GetBestBlock();
183 : 508240 : return hashBlock;
184 : : }
185 : :
186 : 573674 : void CCoinsViewCache::SetBestBlock(const uint256 &hashBlockIn) {
187 : 573674 : hashBlock = hashBlockIn;
188 : 573674 : }
189 : :
190 : 147974 : void CCoinsViewCache::BatchWrite(CoinsViewCacheCursor& cursor, const uint256& hashBlockIn)
191 : : {
192 [ + + ]: 668422 : for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) {
193 [ + + ]: 520456 : if (!it->second.IsDirty()) { // TODO a cursor can only contain dirty entries
194 : 18 : continue;
195 : : }
196 [ + + ]: 520438 : auto [itUs, inserted]{cacheCoins.try_emplace(it->first)};
197 [ + + ]: 520438 : if (inserted) {
198 [ + + + + ]: 407376 : if (it->second.IsFresh() && it->second.coin.IsSpent()) {
199 : 1 : cacheCoins.erase(itUs); // TODO fresh coins should have been removed at spend
200 : : } else {
201 : : // The parent cache does not have an entry, while the child cache does.
202 : : // Move the data up and mark it as dirty.
203 [ - + ]: 407375 : CCoinsCacheEntry& entry{itUs->second};
204 [ - + - - ]: 407375 : assert(entry.coin.DynamicMemoryUsage() == 0);
205 [ + + ]: 407375 : if (cursor.WillErase(*it)) {
206 : : // Since this entry will be erased,
207 : : // we can move the coin into us instead of copying it
208 : 394156 : entry.coin = std::move(it->second.coin);
209 : : } else {
210 : 13219 : entry.coin = it->second.coin;
211 : : }
212 [ + + ]: 407375 : cachedCoinsUsage += entry.coin.DynamicMemoryUsage();
213 : 407375 : CCoinsCacheEntry::SetDirty(*itUs, m_sentinel);
214 : : // We can mark it FRESH in the parent if it was FRESH in the child
215 : : // Otherwise it might have just been flushed from the parent's cache
216 : : // and already exist in the grandparent
217 [ + + ]: 407375 : if (it->second.IsFresh()) CCoinsCacheEntry::SetFresh(*itUs, m_sentinel);
218 : : }
219 : : } else {
220 : : // Found the entry in the parent cache
221 [ + + + + ]: 113062 : if (it->second.IsFresh() && !itUs->second.coin.IsSpent()) {
222 : : // The coin was marked FRESH in the child cache, but the coin
223 : : // exists in the parent cache. If this ever happens, it means
224 : : // the FRESH flag was misapplied and there is a logic error in
225 : : // the calling code.
226 [ + - ]: 8 : throw std::logic_error("FRESH flag misapplied to coin that exists in parent cache");
227 : : }
228 : :
229 [ + + + + ]: 113054 : if (itUs->second.IsFresh() && it->second.coin.IsSpent()) {
230 : : // The grandparent cache does not have an entry, and the coin
231 : : // has been spent. We can just delete it from the parent cache.
232 [ + + ]: 39112 : cachedCoinsUsage -= itUs->second.coin.DynamicMemoryUsage();
233 : 39112 : cacheCoins.erase(itUs);
234 : : } else {
235 : : // A normal modification.
236 [ + + ]: 73942 : cachedCoinsUsage -= itUs->second.coin.DynamicMemoryUsage();
237 [ + + ]: 73942 : if (cursor.WillErase(*it)) {
238 : : // Since this entry will be erased,
239 : : // we can move the coin into us instead of copying it
240 : 71617 : itUs->second.coin = std::move(it->second.coin);
241 : : } else {
242 : 2325 : itUs->second.coin = it->second.coin;
243 : : }
244 [ + + ]: 73942 : cachedCoinsUsage += itUs->second.coin.DynamicMemoryUsage();
245 : 73942 : CCoinsCacheEntry::SetDirty(*itUs, m_sentinel);
246 : : // NOTE: It isn't safe to mark the coin as FRESH in the parent
247 : : // cache. If it already existed and was spent in the parent
248 : : // cache then marking it FRESH would prevent that spentness
249 : : // from being flushed to the grandparent.
250 : : }
251 : : }
252 : : }
253 : 147966 : hashBlock = hashBlockIn;
254 : 147966 : }
255 : :
256 : 151323 : void CCoinsViewCache::Flush(bool will_reuse_cache)
257 : : {
258 : 151323 : auto cursor{CoinsViewCacheCursor(m_sentinel, cacheCoins, /*will_erase=*/true)};
259 : 151323 : base->BatchWrite(cursor, hashBlock);
260 : 151323 : cacheCoins.clear();
261 [ + + ]: 151323 : if (will_reuse_cache) {
262 : 4287 : ReallocateCache();
263 : : }
264 : 151323 : cachedCoinsUsage = 0;
265 : 151323 : }
266 : :
267 : 285 : void CCoinsViewCache::Sync()
268 : : {
269 : 285 : auto cursor{CoinsViewCacheCursor(m_sentinel, cacheCoins, /*will_erase=*/false)};
270 : 285 : base->BatchWrite(cursor, hashBlock);
271 [ - + ]: 285 : if (m_sentinel.second.Next() != &m_sentinel) {
272 : : /* BatchWrite must clear flags of all entries */
273 [ # # ]: 0 : throw std::logic_error("Not all unspent flagged entries were cleared");
274 : : }
275 : 285 : }
276 : :
277 : 27760 : void CCoinsViewCache::Uncache(const COutPoint& hash)
278 : : {
279 : 27760 : CCoinsMap::iterator it = cacheCoins.find(hash);
280 [ + + + + : 27760 : if (it != cacheCoins.end() && !it->second.IsDirty() && !it->second.IsFresh()) {
+ + ]
281 [ + + ]: 11627 : cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage();
282 : : TRACEPOINT(utxocache, uncache,
283 : : hash.hash.data(),
284 : : (uint32_t)hash.n,
285 : : (uint32_t)it->second.coin.nHeight,
286 : : (int64_t)it->second.coin.out.nValue,
287 : 11627 : (bool)it->second.coin.IsCoinBase());
288 : 11627 : cacheCoins.erase(it);
289 : : }
290 : 27760 : }
291 : :
292 : 596422 : unsigned int CCoinsViewCache::GetCacheSize() const {
293 : 596422 : return cacheCoins.size();
294 : : }
295 : :
296 : 10920651 : bool CCoinsViewCache::HaveInputs(const CTransaction& tx) const
297 : : {
298 [ + - ]: 10920651 : if (!tx.IsCoinBase()) {
299 [ - + + + ]: 24997773 : for (unsigned int i = 0; i < tx.vin.size(); i++) {
300 [ + + ]: 14077449 : if (!HaveCoin(tx.vin[i].prevout)) {
301 : : return false;
302 : : }
303 : : }
304 : : }
305 : : return true;
306 : : }
307 : :
308 : 4287 : void CCoinsViewCache::ReallocateCache()
309 : : {
310 : : // Cache should be empty when we're calling this.
311 [ - + ]: 4287 : assert(cacheCoins.size() == 0);
312 : 4287 : cacheCoins.~CCoinsMap();
313 : 4287 : m_cache_coins_memory_resource.~CCoinsMapMemoryResource();
314 : 4287 : ::new (&m_cache_coins_memory_resource) CCoinsMapMemoryResource{};
315 : 4287 : ::new (&cacheCoins) CCoinsMap{0, SaltedOutpointHasher{/*deterministic=*/m_deterministic}, CCoinsMap::key_equal{}, &m_cache_coins_memory_resource};
316 : 4287 : }
317 : :
318 : 337 : void CCoinsViewCache::SanityCheck() const
319 : : {
320 : 337 : size_t recomputed_usage = 0;
321 : 337 : size_t count_flagged = 0;
322 [ + + + + ]: 576214 : for (const auto& [_, entry] : cacheCoins) {
323 : 575877 : unsigned attr = 0;
324 [ + + ]: 575877 : if (entry.IsDirty()) attr |= 1;
325 [ + + ]: 575877 : if (entry.IsFresh()) attr |= 2;
326 [ + + ]: 575877 : if (entry.coin.IsSpent()) attr |= 4;
327 : : // Only 5 combinations are possible.
328 [ + - - + ]: 575877 : assert(attr != 2 && attr != 4 && attr != 7);
329 : :
330 : : // Recompute cachedCoinsUsage.
331 [ + + ]: 575877 : recomputed_usage += entry.coin.DynamicMemoryUsage();
332 : :
333 : : // Count the number of entries we expect in the linked list.
334 [ + + + + ]: 575877 : if (entry.IsDirty() || entry.IsFresh()) ++count_flagged;
335 : : }
336 : : // Iterate over the linked list of flagged entries.
337 : 337 : size_t count_linked = 0;
338 [ + + ]: 98763 : for (auto it = m_sentinel.second.Next(); it != &m_sentinel; it = it->second.Next()) {
339 : : // Verify linked list integrity.
340 [ - + ]: 98426 : assert(it->second.Next()->second.Prev() == it);
341 [ - + ]: 98426 : assert(it->second.Prev()->second.Next() == it);
342 : : // Verify they are actually flagged.
343 [ + + - + ]: 98426 : assert(it->second.IsDirty() || it->second.IsFresh());
344 : : // Count the number of entries actually in the list.
345 : 98426 : ++count_linked;
346 : : }
347 [ - + ]: 337 : assert(count_linked == count_flagged);
348 [ - + ]: 337 : assert(recomputed_usage == cachedCoinsUsage);
349 : 337 : }
350 : :
351 : : static const uint64_t MIN_TRANSACTION_OUTPUT_WEIGHT{WITNESS_SCALE_FACTOR * ::GetSerializeSize(CTxOut())};
352 : : static const uint64_t MAX_OUTPUTS_PER_BLOCK{MAX_BLOCK_WEIGHT / MIN_TRANSACTION_OUTPUT_WEIGHT};
353 : :
354 : 182 : const Coin& AccessByTxid(const CCoinsViewCache& view, const Txid& txid)
355 : : {
356 : 182 : COutPoint iter(txid, 0);
357 [ + + ]: 10111283 : while (iter.n < MAX_OUTPUTS_PER_BLOCK) {
358 : 10111192 : const Coin& alternate = view.AccessCoin(iter);
359 [ + + ]: 10111192 : if (!alternate.IsSpent()) return alternate;
360 : 10111101 : ++iter.n;
361 : : }
362 : : return coinEmpty;
363 : : }
364 : :
365 : : template <typename ReturnType, typename Func>
366 : 1334500 : static ReturnType ExecuteBackedWrapper(Func func, const std::vector<std::function<void()>>& err_callbacks)
367 : : {
368 : : try {
369 : 1334500 : return func();
370 [ - - ]: 0 : } catch(const std::runtime_error& e) {
371 [ - - ]: 0 : for (const auto& f : err_callbacks) {
372 [ - - ]: 0 : f();
373 : : }
374 [ - - ]: 0 : LogError("Error reading from database: %s\n", e.what());
375 : : // Starting the shutdown sequence and returning false to the caller would be
376 : : // interpreted as 'entry not found' (as opposed to unable to read data), and
377 : : // could lead to invalid interpretation. Just exit immediately, as we can't
378 : : // continue anyway, and all writes should be atomic.
379 : 0 : std::abort();
380 : : }
381 : : }
382 : :
383 : 1334500 : std::optional<Coin> CCoinsViewErrorCatcher::GetCoin(const COutPoint& outpoint) const
384 : : {
385 [ + - ]: 2669000 : return ExecuteBackedWrapper<std::optional<Coin>>([&]() { return CCoinsViewBacked::GetCoin(outpoint); }, m_err_callbacks);
386 : : }
387 : :
388 : 0 : bool CCoinsViewErrorCatcher::HaveCoin(const COutPoint& outpoint) const
389 : : {
390 [ # # ]: 0 : return ExecuteBackedWrapper<bool>([&]() { return CCoinsViewBacked::HaveCoin(outpoint); }, m_err_callbacks);
391 : : }
|
