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