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 <random.h>
9 : : #include <uint256.h>
10 : : #include <util/log.h>
11 : : #include <util/trace.h>
12 : :
13 : : TRACEPOINT_SEMAPHORE(utxocache, add);
14 : : TRACEPOINT_SEMAPHORE(utxocache, spent);
15 : : TRACEPOINT_SEMAPHORE(utxocache, uncache);
16 : :
17 : 588 : CoinsViewEmpty& CoinsViewEmpty::Get()
18 : : {
19 [ + + + - ]: 588 : static CoinsViewEmpty instance;
20 : 588 : return instance;
21 : : }
22 : :
23 : 18579 : std::optional<Coin> CCoinsViewCache::PeekCoin(const COutPoint& outpoint) const
24 : : {
25 [ + + ]: 18579 : if (auto it{cacheCoins.find(outpoint)}; it != cacheCoins.end()) {
26 [ + + ]: 460 : return it->second.coin.IsSpent() ? std::nullopt : std::optional{it->second.coin};
27 : : }
28 : 18119 : return base->PeekCoin(outpoint);
29 : : }
30 : :
31 : 158240 : CCoinsViewCache::CCoinsViewCache(CCoinsView* in_base, bool deterministic) :
32 : 158240 : CCoinsViewBacked(in_base), m_deterministic(deterministic),
33 [ + - + - ]: 158240 : cacheCoins(0, SaltedOutpointHasher(/*deterministic=*/deterministic), CCoinsMap::key_equal{}, &m_cache_coins_memory_resource)
34 : : {
35 : 158240 : m_sentinel.second.SelfRef(m_sentinel);
36 : 158240 : }
37 : :
38 : 176144 : size_t CCoinsViewCache::DynamicMemoryUsage() const {
39 : 176144 : return memusage::DynamicUsage(cacheCoins) + cachedCoinsUsage;
40 : : }
41 : :
42 : 22122042 : std::optional<Coin> CCoinsViewCache::FetchCoinFromBase(const COutPoint& outpoint) const
43 : : {
44 : 22122042 : return base->GetCoin(outpoint);
45 : : }
46 : :
47 : 22703255 : CCoinsMap::iterator CCoinsViewCache::FetchCoin(const COutPoint &outpoint) const {
48 [ + + ]: 22703255 : const auto [ret, inserted] = cacheCoins.try_emplace(outpoint);
49 [ + + ]: 22703255 : if (inserted) {
50 [ + + ]: 22140618 : if (auto coin{FetchCoinFromBase(outpoint)}) {
51 : 493720 : ret->second.coin = std::move(*coin);
52 [ + + ]: 493720 : cachedCoinsUsage += ret->second.coin.DynamicMemoryUsage();
53 [ - + ]: 493720 : Assert(!ret->second.coin.IsSpent());
54 : : } else {
55 : 21646898 : cacheCoins.erase(ret);
56 : 21646898 : return cacheCoins.end();
57 : 22140618 : }
58 : : }
59 : 1056357 : return ret;
60 : : }
61 : :
62 : 11667826 : std::optional<Coin> CCoinsViewCache::GetCoin(const COutPoint& outpoint) const
63 : : {
64 [ + + + + ]: 11667826 : if (auto it{FetchCoin(outpoint)}; it != cacheCoins.end() && !it->second.coin.IsSpent()) return it->second.coin;
65 : 11365972 : return std::nullopt;
66 : : }
67 : :
68 : 163874 : void CCoinsViewCache::AddCoin(const COutPoint &outpoint, Coin&& coin, bool possible_overwrite) {
69 [ - + ]: 163874 : assert(!coin.IsSpent());
70 [ + + ]: 163874 : if (coin.out.scriptPubKey.IsUnspendable()) return;
71 : 144858 : CCoinsMap::iterator it;
72 : 144858 : bool inserted;
73 [ + + ]: 144858 : std::tie(it, inserted) = cacheCoins.emplace(std::piecewise_construct, std::forward_as_tuple(outpoint), std::tuple<>());
74 : 144858 : bool fresh = false;
75 [ + + ]: 144858 : if (!possible_overwrite) {
76 [ + + ]: 95837 : if (!it->second.coin.IsSpent()) {
77 [ + - ]: 17 : throw std::logic_error("Attempted to overwrite an unspent coin (when possible_overwrite is false)");
78 : : }
79 : : // If the coin exists in this cache as a spent coin and is DIRTY, then
80 : : // its spentness hasn't been flushed to the parent cache. We're
81 : : // re-adding the coin to this cache now but we can't mark it as FRESH.
82 : : // If we mark it FRESH and then spend it before the cache is flushed
83 : : // we would remove it from this cache and would never flush spentness
84 : : // to the parent cache.
85 : : //
86 : : // Re-adding a spent coin can happen in the case of a re-org (the coin
87 : : // is 'spent' when the block adding it is disconnected and then
88 : : // re-added when it is also added in a newly connected block).
89 : : //
90 : : // If the coin doesn't exist in the current cache, or is spent but not
91 : : // DIRTY, then it can be marked FRESH.
92 : 95820 : fresh = !it->second.IsDirty();
93 : : }
94 [ + + ]: 144841 : if (!inserted) {
95 [ + - + + ]: 20910 : Assume(TrySub(m_dirty_count, it->second.IsDirty()));
96 [ + + + - ]: 24259 : Assume(TrySub(cachedCoinsUsage, it->second.coin.DynamicMemoryUsage()));
97 : : }
98 : 144841 : it->second.coin = std::move(coin);
99 : 144841 : CCoinsCacheEntry::SetDirty(*it, m_sentinel);
100 : 144841 : ++m_dirty_count;
101 [ + + ]: 144841 : if (fresh) CCoinsCacheEntry::SetFresh(*it, m_sentinel);
102 [ + + ]: 231356 : cachedCoinsUsage += it->second.coin.DynamicMemoryUsage();
103 : : TRACEPOINT(utxocache, add,
104 : : outpoint.hash.data(),
105 : : (uint32_t)outpoint.n,
106 : : (uint32_t)it->second.coin.nHeight,
107 : : (int64_t)it->second.coin.out.nValue,
108 : 163857 : (bool)it->second.coin.IsCoinBase());
109 : : }
110 : :
111 : 20283 : void CCoinsViewCache::EmplaceCoinInternalDANGER(COutPoint&& outpoint, Coin&& coin) {
112 [ + + ]: 20283 : const auto mem_usage{coin.DynamicMemoryUsage()};
113 [ + + ]: 20283 : auto [it, inserted] = cacheCoins.try_emplace(std::move(outpoint), std::move(coin));
114 [ + + ]: 20283 : if (inserted) {
115 : 20282 : CCoinsCacheEntry::SetDirty(*it, m_sentinel);
116 : 20282 : ++m_dirty_count;
117 : 20282 : cachedCoinsUsage += mem_usage;
118 : : }
119 : 20283 : }
120 : :
121 : 55407 : void AddCoins(CCoinsViewCache& cache, const CTransaction &tx, int nHeight, bool check_for_overwrite) {
122 : 55407 : bool fCoinbase = tx.IsCoinBase();
123 : 55407 : const Txid& txid = tx.GetHash();
124 [ - + + + ]: 129512 : for (size_t i = 0; i < tx.vout.size(); ++i) {
125 [ - + ]: 74105 : 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 [ + - ]: 148210 : cache.AddCoin(COutPoint(txid, i), Coin(tx.vout[i], nHeight, fCoinbase), overwrite);
129 : : }
130 : 55407 : }
131 : :
132 : 69393 : bool CCoinsViewCache::SpendCoin(const COutPoint &outpoint, Coin* moveout) {
133 : 69393 : CCoinsMap::iterator it = FetchCoin(outpoint);
134 [ + + ]: 69393 : if (it == cacheCoins.end()) return false;
135 [ + - + + ]: 138774 : Assume(TrySub(m_dirty_count, it->second.IsDirty()));
136 [ + + + - : 167481 : Assume(TrySub(cachedCoinsUsage, it->second.coin.DynamicMemoryUsage()));
+ + ]
137 : : TRACEPOINT(utxocache, spent,
138 : : outpoint.hash.data(),
139 : : (uint32_t)outpoint.n,
140 : : (uint32_t)it->second.coin.nHeight,
141 : : (int64_t)it->second.coin.out.nValue,
142 : 69387 : (bool)it->second.coin.IsCoinBase());
143 [ + + ]: 69387 : if (moveout) {
144 : 34522 : *moveout = std::move(it->second.coin);
145 : : }
146 [ + + ]: 69387 : if (it->second.IsFresh()) {
147 : 8007 : cacheCoins.erase(it);
148 : : } else {
149 : 61380 : CCoinsCacheEntry::SetDirty(*it, m_sentinel);
150 : 61380 : ++m_dirty_count;
151 : 61380 : it->second.coin.Clear();
152 : : }
153 : : return true;
154 : : }
155 : :
156 : : static const Coin coinEmpty;
157 : :
158 : 9929293 : const Coin& CCoinsViewCache::AccessCoin(const COutPoint &outpoint) const {
159 [ + + ]: 9929293 : CCoinsMap::const_iterator it = FetchCoin(outpoint);
160 [ + + ]: 9929293 : if (it == cacheCoins.end()) {
161 : : return coinEmpty;
162 : : } else {
163 : 325029 : return it->second.coin;
164 : : }
165 : : }
166 : :
167 : 1036743 : bool CCoinsViewCache::HaveCoin(const COutPoint& outpoint) const
168 : : {
169 [ + + ]: 1036743 : CCoinsMap::const_iterator it = FetchCoin(outpoint);
170 [ + + + + ]: 1036743 : return (it != cacheCoins.end() && !it->second.coin.IsSpent());
171 : : }
172 : :
173 : 206604 : bool CCoinsViewCache::HaveCoinInCache(const COutPoint &outpoint) const {
174 [ + + ]: 206604 : CCoinsMap::const_iterator it = cacheCoins.find(outpoint);
175 [ + + + + ]: 206604 : return (it != cacheCoins.end() && !it->second.coin.IsSpent());
176 : : }
177 : :
178 : 35068 : uint256 CCoinsViewCache::GetBestBlock() const {
179 [ + + ]: 70136 : if (m_block_hash.IsNull())
180 : 17703 : m_block_hash = base->GetBestBlock();
181 : 35068 : return m_block_hash;
182 : : }
183 : :
184 : 447750 : void CCoinsViewCache::SetBestBlock(const uint256& in_block_hash)
185 : : {
186 : 447750 : m_block_hash = in_block_hash;
187 : 447750 : }
188 : :
189 : 9899 : void CCoinsViewCache::BatchWrite(CoinsViewCacheCursor& cursor, const uint256& in_block_hash)
190 : : {
191 [ + + ]: 185883 : for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) {
192 [ + + ]: 175992 : if (!it->second.IsDirty()) { // TODO a cursor can only contain dirty entries
193 : 18 : continue;
194 : : }
195 [ + + ]: 175974 : auto [itUs, inserted]{cacheCoins.try_emplace(it->first)};
196 [ + + ]: 175974 : if (inserted) {
197 [ + + + + ]: 132739 : if (it->second.IsFresh() && it->second.coin.IsSpent()) {
198 : 1 : cacheCoins.erase(itUs); // TODO fresh coins should have been removed at spend
199 : : } else {
200 : : // The parent cache does not have an entry, while the child cache does.
201 : : // Move the data up and mark it as dirty.
202 [ - + ]: 132738 : CCoinsCacheEntry& entry{itUs->second};
203 [ - + - - ]: 132738 : assert(entry.coin.DynamicMemoryUsage() == 0);
204 [ + + ]: 132738 : if (cursor.WillErase(*it)) {
205 : : // Since this entry will be erased,
206 : : // we can move the coin into us instead of copying it
207 : 122582 : entry.coin = std::move(it->second.coin);
208 : : } else {
209 : 10156 : entry.coin = it->second.coin;
210 : : }
211 : 132738 : CCoinsCacheEntry::SetDirty(*itUs, m_sentinel);
212 : 132738 : ++m_dirty_count;
213 [ + + ]: 132738 : cachedCoinsUsage += entry.coin.DynamicMemoryUsage();
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 [ + + ]: 132738 : if (it->second.IsFresh()) CCoinsCacheEntry::SetFresh(*itUs, m_sentinel);
218 : : }
219 : : } else {
220 : : // Found the entry in the parent cache
221 [ + + + + ]: 43235 : 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 [ + + + + ]: 43227 : 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 [ + - + + ]: 7010 : Assume(TrySub(m_dirty_count, itUs->second.IsDirty()));
233 [ + + + - ]: 8532 : Assume(TrySub(cachedCoinsUsage, itUs->second.coin.DynamicMemoryUsage()));
234 : 3505 : cacheCoins.erase(itUs);
235 : : } else {
236 : : // A normal modification.
237 [ + + + - : 95433 : Assume(TrySub(cachedCoinsUsage, itUs->second.coin.DynamicMemoryUsage()));
+ + ]
238 [ + + ]: 39722 : if (cursor.WillErase(*it)) {
239 : : // Since this entry will be erased,
240 : : // we can move the coin into us instead of copying it
241 : 38367 : itUs->second.coin = std::move(it->second.coin);
242 : : } else {
243 : 1355 : itUs->second.coin = it->second.coin;
244 : : }
245 [ + + ]: 39722 : cachedCoinsUsage += itUs->second.coin.DynamicMemoryUsage();
246 [ + + ]: 39722 : if (!itUs->second.IsDirty()) {
247 : 35520 : CCoinsCacheEntry::SetDirty(*itUs, m_sentinel);
248 : 35520 : ++m_dirty_count;
249 : : }
250 : : // NOTE: It isn't safe to mark the coin as FRESH in the parent
251 : : // cache. If it already existed and was spent in the parent
252 : : // cache then marking it FRESH would prevent that spentness
253 : : // from being flushed to the grandparent.
254 : : }
255 : : }
256 : : }
257 : 9891 : SetBestBlock(in_block_hash);
258 : 9891 : }
259 : :
260 : 9962 : void CCoinsViewCache::Flush(bool reallocate_cache)
261 : : {
262 : 9962 : auto cursor{CoinsViewCacheCursor(m_dirty_count, m_sentinel, cacheCoins, /*will_erase=*/true)};
263 : 9962 : base->BatchWrite(cursor, m_block_hash);
264 : 9962 : Assume(m_dirty_count == 0);
265 : 9962 : cacheCoins.clear();
266 [ + + ]: 9962 : if (reallocate_cache) {
267 : 942 : ReallocateCache();
268 : : }
269 : 9962 : cachedCoinsUsage = 0;
270 : 9962 : }
271 : :
272 : 223 : void CCoinsViewCache::Sync()
273 : : {
274 : 223 : auto cursor{CoinsViewCacheCursor(m_dirty_count, m_sentinel, cacheCoins, /*will_erase=*/false)};
275 : 223 : base->BatchWrite(cursor, m_block_hash);
276 [ - + ]: 223 : Assume(m_dirty_count == 0);
277 [ - + ]: 223 : if (m_sentinel.second.Next() != &m_sentinel) {
278 : : /* BatchWrite must clear flags of all entries */
279 [ # # ]: 0 : throw std::logic_error("Not all unspent flagged entries were cleared");
280 : : }
281 : 223 : }
282 : :
283 : 8613 : void CCoinsViewCache::Reset() noexcept
284 : : {
285 : 8613 : cacheCoins.clear();
286 : 8613 : cachedCoinsUsage = 0;
287 : 8613 : m_dirty_count = 0;
288 : 8613 : SetBestBlock(uint256::ZERO);
289 : 8613 : }
290 : :
291 : 11855 : void CCoinsViewCache::Uncache(const COutPoint& hash)
292 : : {
293 : 11855 : CCoinsMap::iterator it = cacheCoins.find(hash);
294 [ + + + + ]: 11855 : if (it != cacheCoins.end() && !it->second.IsDirty()) {
295 [ + + + - ]: 2830 : Assume(TrySub(cachedCoinsUsage, it->second.coin.DynamicMemoryUsage()));
296 : : TRACEPOINT(utxocache, uncache,
297 : : hash.hash.data(),
298 : : (uint32_t)hash.n,
299 : : (uint32_t)it->second.coin.nHeight,
300 : : (int64_t)it->second.coin.out.nValue,
301 : 1177 : (bool)it->second.coin.IsCoinBase());
302 : 1177 : cacheCoins.erase(it);
303 : : }
304 : 11855 : }
305 : :
306 : 35238 : unsigned int CCoinsViewCache::GetCacheSize() const {
307 : 35238 : return cacheCoins.size();
308 : : }
309 : :
310 : 1175 : bool CCoinsViewCache::HaveInputs(const CTransaction& tx) const
311 : : {
312 [ + - ]: 1175 : if (!tx.IsCoinBase()) {
313 [ - + + + ]: 2352 : for (unsigned int i = 0; i < tx.vin.size(); i++) {
314 [ + + ]: 1181 : if (!HaveCoin(tx.vin[i].prevout)) {
315 : : return false;
316 : : }
317 : : }
318 : : }
319 : : return true;
320 : : }
321 : :
322 : 942 : void CCoinsViewCache::ReallocateCache()
323 : : {
324 : : // Cache should be empty when we're calling this.
325 [ - + ]: 942 : assert(cacheCoins.size() == 0);
326 : 942 : cacheCoins.~CCoinsMap();
327 : 942 : m_cache_coins_memory_resource.~CCoinsMapMemoryResource();
328 : 942 : ::new (&m_cache_coins_memory_resource) CCoinsMapMemoryResource{};
329 : 942 : ::new (&cacheCoins) CCoinsMap{0, SaltedOutpointHasher{/*deterministic=*/m_deterministic}, CCoinsMap::key_equal{}, &m_cache_coins_memory_resource};
330 : 942 : }
331 : :
332 : 278 : void CCoinsViewCache::SanityCheck() const
333 : : {
334 : 278 : size_t recomputed_usage = 0;
335 : 278 : size_t count_dirty = 0;
336 [ + + + + ]: 433538 : for (const auto& [_, entry] : cacheCoins) {
337 [ + + ]: 433260 : if (entry.coin.IsSpent()) {
338 [ + - - + ]: 20690 : assert(entry.IsDirty() && !entry.IsFresh()); // A spent coin must be dirty and cannot be fresh
339 : : } else {
340 [ + + - + ]: 412570 : assert(entry.IsDirty() || !entry.IsFresh()); // An unspent coin must not be fresh if not dirty
341 : : }
342 : :
343 : : // Recompute cachedCoinsUsage.
344 [ + + ]: 433260 : recomputed_usage += entry.coin.DynamicMemoryUsage();
345 : :
346 : : // Count the number of entries we expect in the linked list.
347 [ + + ]: 433260 : if (entry.IsDirty()) ++count_dirty;
348 : : }
349 : : // Iterate over the linked list of flagged entries.
350 : 278 : size_t count_linked = 0;
351 [ + + ]: 49804 : for (auto it = m_sentinel.second.Next(); it != &m_sentinel; it = it->second.Next()) {
352 : : // Verify linked list integrity.
353 [ - + ]: 49526 : assert(it->second.Next()->second.Prev() == it);
354 [ - + ]: 49526 : assert(it->second.Prev()->second.Next() == it);
355 : : // Verify they are actually flagged.
356 [ - + ]: 49526 : assert(it->second.IsDirty());
357 : : // Count the number of entries actually in the list.
358 : 49526 : ++count_linked;
359 : : }
360 [ + - - + ]: 278 : assert(count_dirty == count_linked && count_dirty == m_dirty_count);
361 [ - + ]: 278 : assert(recomputed_usage == cachedCoinsUsage);
362 : 278 : }
363 : :
364 : : static const uint64_t MIN_TRANSACTION_OUTPUT_WEIGHT{WITNESS_SCALE_FACTOR * ::GetSerializeSize(CTxOut())};
365 : : static const uint64_t MAX_OUTPUTS_PER_BLOCK{MAX_BLOCK_WEIGHT / MIN_TRANSACTION_OUTPUT_WEIGHT};
366 : :
367 : 155 : const Coin& AccessByTxid(const CCoinsViewCache& view, const Txid& txid)
368 : : {
369 : 155 : COutPoint iter(txid, 0);
370 [ + + ]: 8889035 : while (iter.n < MAX_OUTPUTS_PER_BLOCK) {
371 : 8888955 : const Coin& alternate = view.AccessCoin(iter);
372 [ + + ]: 8888955 : if (!alternate.IsSpent()) return alternate;
373 : 8888880 : ++iter.n;
374 : : }
375 : : return coinEmpty;
376 : : }
377 : :
378 : : template <typename ReturnType, typename Func>
379 : 36299 : static ReturnType ExecuteBackedWrapper(Func func, const std::vector<std::function<void()>>& err_callbacks)
380 : : {
381 : : try {
382 [ + - ]: 36299 : return func();
383 [ - - ]: 0 : } catch(const std::runtime_error& e) {
384 [ - - ]: 0 : for (const auto& f : err_callbacks) {
385 [ - - ]: 0 : f();
386 : : }
387 [ - - ]: 0 : LogError("Error reading from database: %s\n", e.what());
388 : : // Starting the shutdown sequence and returning false to the caller would be
389 : : // interpreted as 'entry not found' (as opposed to unable to read data), and
390 : : // could lead to invalid interpretation. Just exit immediately, as we can't
391 : : // continue anyway, and all writes should be atomic.
392 : 0 : std::abort();
393 : : }
394 : : }
395 : :
396 : 18583 : std::optional<Coin> CCoinsViewErrorCatcher::GetCoin(const COutPoint& outpoint) const
397 : : {
398 : 37166 : return ExecuteBackedWrapper<std::optional<Coin>>([&]() { return CCoinsViewBacked::GetCoin(outpoint); }, m_err_callbacks);
399 : : }
400 : :
401 : 0 : bool CCoinsViewErrorCatcher::HaveCoin(const COutPoint& outpoint) const
402 : : {
403 : 0 : return ExecuteBackedWrapper<bool>([&]() { return CCoinsViewBacked::HaveCoin(outpoint); }, m_err_callbacks);
404 : : }
405 : :
406 : 17716 : std::optional<Coin> CCoinsViewErrorCatcher::PeekCoin(const COutPoint& outpoint) const
407 : : {
408 : 35432 : return ExecuteBackedWrapper<std::optional<Coin>>([&]() { return CCoinsViewBacked::PeekCoin(outpoint); }, m_err_callbacks);
409 : : }
|
