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