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