coins.cpp raw
1 // Copyright (c) 2012-2022 The Limenka 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 std::optional<Coin> CCoinsView::GetCoin(const COutPoint& outpoint) const { return std::nullopt; }
17 uint256 CCoinsView::GetBestBlock() const { return uint256(); }
18 std::vector<uint256> CCoinsView::GetHeadBlocks() const { return std::vector<uint256>(); }
19 bool CCoinsView::BatchWrite(CoinsViewCacheCursor& cursor, const uint256 &hashBlock) { return false; }
20 std::unique_ptr<CCoinsViewCursor> CCoinsView::Cursor() const { return nullptr; }
21
22 bool CCoinsView::HaveCoin(const COutPoint &outpoint) const
23 {
24 return GetCoin(outpoint).has_value();
25 }
26
27 CCoinsViewBacked::CCoinsViewBacked(CCoinsView *viewIn) : base(viewIn) { }
28 std::optional<Coin> CCoinsViewBacked::GetCoin(const COutPoint& outpoint) const { return base->GetCoin(outpoint); }
29 bool CCoinsViewBacked::HaveCoin(const COutPoint &outpoint) const { return base->HaveCoin(outpoint); }
30 uint256 CCoinsViewBacked::GetBestBlock() const { return base->GetBestBlock(); }
31 std::vector<uint256> CCoinsViewBacked::GetHeadBlocks() const { return base->GetHeadBlocks(); }
32 void CCoinsViewBacked::SetBackend(CCoinsView &viewIn) { base = &viewIn; }
33 bool CCoinsViewBacked::BatchWrite(CoinsViewCacheCursor& cursor, const uint256 &hashBlock) { return base->BatchWrite(cursor, hashBlock); }
34 std::unique_ptr<CCoinsViewCursor> CCoinsViewBacked::Cursor() const { return base->Cursor(); }
35 size_t CCoinsViewBacked::EstimateSize() const { return base->EstimateSize(); }
36
37 CCoinsViewCache::CCoinsViewCache(CCoinsView* baseIn, bool deterministic) :
38 CCoinsViewBacked(baseIn), m_deterministic(deterministic),
39 cacheCoins(0, SaltedOutpointHasher(/*deterministic=*/deterministic), CCoinsMap::key_equal{}, &m_cache_coins_memory_resource)
40 {
41 m_sentinel.second.SelfRef(m_sentinel);
42 }
43
44 size_t CCoinsViewCache::DynamicMemoryUsage() const {
45 return memusage::DynamicUsage(cacheCoins) + cachedCoinsUsage;
46 }
47
48 CCoinsMap::iterator CCoinsViewCache::FetchCoin(const COutPoint &outpoint) const {
49 const auto [ret, inserted] = cacheCoins.try_emplace(outpoint);
50 if (inserted) {
51 if (auto coin{base->GetCoin(outpoint)}) {
52 ret->second.coin = std::move(*coin);
53 cachedCoinsUsage += ret->second.coin.DynamicMemoryUsage();
54 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 CCoinsCacheEntry::SetFresh(*ret, m_sentinel);
57 }
58 } else {
59 cacheCoins.erase(ret);
60 return cacheCoins.end();
61 }
62 }
63 return ret;
64 }
65
66 std::optional<Coin> CCoinsViewCache::GetCoin(const COutPoint& outpoint) const
67 {
68 if (auto it{FetchCoin(outpoint)}; it != cacheCoins.end() && !it->second.coin.IsSpent()) return it->second.coin;
69 return std::nullopt;
70 }
71
72 void CCoinsViewCache::AddCoin(const COutPoint &outpoint, Coin&& coin, bool possible_overwrite) {
73 assert(!coin.IsSpent());
74 if (coin.out.scriptPubKey.IsUnspendable()) return;
75 CCoinsMap::iterator it;
76 bool inserted;
77 std::tie(it, inserted) = cacheCoins.emplace(std::piecewise_construct, std::forward_as_tuple(outpoint), std::tuple<>());
78 bool fresh = false;
79 if (!inserted) {
80 cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage();
81 }
82 if (!possible_overwrite) {
83 if (!it->second.coin.IsSpent()) {
84 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 fresh = !it->second.IsDirty();
100 }
101 it->second.coin = std::move(coin);
102 CCoinsCacheEntry::SetDirty(*it, m_sentinel);
103 if (fresh) CCoinsCacheEntry::SetFresh(*it, m_sentinel);
104 cachedCoinsUsage += it->second.coin.DynamicMemoryUsage();
105 TRACEPOINT(utxocache, add,
106 outpoint.hash.data(),
107 (uint32_t)outpoint.n,
108 (uint32_t)it->second.coin.nHeight,
109 (int64_t)it->second.coin.out.nValue,
110 (bool)it->second.coin.IsCoinBase());
111 }
112
113 void CCoinsViewCache::EmplaceCoinInternalDANGER(COutPoint&& outpoint, Coin&& coin) {
114 cachedCoinsUsage += coin.DynamicMemoryUsage();
115 auto [it, inserted] = cacheCoins.try_emplace(std::move(outpoint), std::move(coin));
116 if (inserted) CCoinsCacheEntry::SetDirty(*it, m_sentinel);
117 }
118
119 void AddCoins(CCoinsViewCache& cache, const CTransaction &tx, int nHeight, bool check_for_overwrite) {
120 bool fCoinbase = tx.IsCoinBase();
121 const Txid& txid = tx.GetHash();
122 for (size_t i = 0; i < tx.vout.size(); ++i) {
123 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 cache.AddCoin(COutPoint(txid, i), Coin(tx.vout[i], nHeight, fCoinbase), overwrite);
127 }
128 }
129
130 bool CCoinsViewCache::SpendCoin(const COutPoint &outpoint, Coin* moveout) {
131 CCoinsMap::iterator it = FetchCoin(outpoint);
132 if (it == cacheCoins.end()) return false;
133 cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage();
134 TRACEPOINT(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 (bool)it->second.coin.IsCoinBase());
140 if (moveout) {
141 *moveout = std::move(it->second.coin);
142 }
143 if (it->second.IsFresh()) {
144 cacheCoins.erase(it);
145 } else {
146 CCoinsCacheEntry::SetDirty(*it, m_sentinel);
147 it->second.coin.Clear();
148 }
149 return true;
150 }
151
152 static const Coin coinEmpty;
153
154 const Coin& CCoinsViewCache::AccessCoin(const COutPoint &outpoint) const {
155 CCoinsMap::const_iterator it = FetchCoin(outpoint);
156 if (it == cacheCoins.end()) {
157 return coinEmpty;
158 } else {
159 return it->second.coin;
160 }
161 }
162
163 bool CCoinsViewCache::HaveCoin(const COutPoint &outpoint) const {
164 CCoinsMap::const_iterator it = FetchCoin(outpoint);
165 return (it != cacheCoins.end() && !it->second.coin.IsSpent());
166 }
167
168 bool CCoinsViewCache::HaveCoinInCache(const COutPoint &outpoint) const {
169 CCoinsMap::const_iterator it = cacheCoins.find(outpoint);
170 return (it != cacheCoins.end() && !it->second.coin.IsSpent());
171 }
172
173 uint256 CCoinsViewCache::GetBestBlock() const {
174 if (hashBlock.IsNull())
175 hashBlock = base->GetBestBlock();
176 return hashBlock;
177 }
178
179 void CCoinsViewCache::SetBestBlock(const uint256 &hashBlockIn) {
180 hashBlock = hashBlockIn;
181 }
182
183 bool CCoinsViewCache::BatchWrite(CoinsViewCacheCursor& cursor, const uint256 &hashBlockIn) {
184 for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) {
185 // Ignore non-dirty entries (optimization).
186 if (!it->second.IsDirty()) {
187 continue;
188 }
189 CCoinsMap::iterator itUs = cacheCoins.find(it->first);
190 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 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 itUs = cacheCoins.try_emplace(it->first).first;
197 CCoinsCacheEntry& entry{itUs->second};
198 if (cursor.WillErase(*it)) {
199 // Since this entry will be erased,
200 // we can move the coin into us instead of copying it
201 entry.coin = std::move(it->second.coin);
202 } else {
203 entry.coin = it->second.coin;
204 }
205 cachedCoinsUsage += entry.coin.DynamicMemoryUsage();
206 CCoinsCacheEntry::SetDirty(*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 if (it->second.IsFresh()) CCoinsCacheEntry::SetFresh(*itUs, m_sentinel);
211 }
212 } else {
213 // Found the entry in the parent cache
214 if (it->second.IsFresh() && !itUs->second.coin.IsSpent()) {
215 // The coin was marked FRESH in the child cache, but the coin
216 // exists in the parent cache. If this ever happens, it means
217 // the FRESH flag was misapplied and there is a logic error in
218 // the calling code.
219 throw std::logic_error("FRESH flag misapplied to coin that exists in parent cache");
220 }
221
222 if (itUs->second.IsFresh() && it->second.coin.IsSpent()) {
223 // The grandparent cache does not have an entry, and the coin
224 // has been spent. We can just delete it from the parent cache.
225 cachedCoinsUsage -= itUs->second.coin.DynamicMemoryUsage();
226 cacheCoins.erase(itUs);
227 } else {
228 // A normal modification.
229 cachedCoinsUsage -= itUs->second.coin.DynamicMemoryUsage();
230 if (cursor.WillErase(*it)) {
231 // Since this entry will be erased,
232 // we can move the coin into us instead of copying it
233 itUs->second.coin = std::move(it->second.coin);
234 } else {
235 itUs->second.coin = it->second.coin;
236 }
237 cachedCoinsUsage += itUs->second.coin.DynamicMemoryUsage();
238 CCoinsCacheEntry::SetDirty(*itUs, m_sentinel);
239 // NOTE: It isn't safe to mark the coin as FRESH in the parent
240 // cache. If it already existed and was spent in the parent
241 // cache then marking it FRESH would prevent that spentness
242 // from being flushed to the grandparent.
243 }
244 }
245 }
246 hashBlock = hashBlockIn;
247 return true;
248 }
249
250 bool CCoinsViewCache::Flush() {
251 auto cursor{CoinsViewCacheCursor(cachedCoinsUsage, m_sentinel, cacheCoins, /*will_erase=*/true)};
252 bool fOk = base->BatchWrite(cursor, hashBlock);
253 if (fOk) {
254 cacheCoins.clear();
255 ReallocateCache();
256 }
257 cachedCoinsUsage = 0;
258 return fOk;
259 }
260
261 bool CCoinsViewCache::Sync()
262 {
263 auto cursor{CoinsViewCacheCursor(cachedCoinsUsage, m_sentinel, cacheCoins, /*will_erase=*/false)};
264 bool fOk = base->BatchWrite(cursor, hashBlock);
265 if (fOk) {
266 if (m_sentinel.second.Next() != &m_sentinel) {
267 /* BatchWrite must clear flags of all entries */
268 throw std::logic_error("Not all unspent flagged entries were cleared");
269 }
270 }
271 return fOk;
272 }
273
274 void CCoinsViewCache::Uncache(const COutPoint& hash)
275 {
276 CCoinsMap::iterator it = cacheCoins.find(hash);
277 if (it != cacheCoins.end() && !it->second.IsDirty() && !it->second.IsFresh()) {
278 cachedCoinsUsage -= it->second.coin.DynamicMemoryUsage();
279 TRACEPOINT(utxocache, uncache,
280 hash.hash.data(),
281 (uint32_t)hash.n,
282 (uint32_t)it->second.coin.nHeight,
283 (int64_t)it->second.coin.out.nValue,
284 (bool)it->second.coin.IsCoinBase());
285 cacheCoins.erase(it);
286 }
287 }
288
289 unsigned int CCoinsViewCache::GetCacheSize() const {
290 return cacheCoins.size();
291 }
292
293 bool CCoinsViewCache::HaveInputs(const CTransaction& tx) const
294 {
295 if (!tx.IsCoinBase()) {
296 for (unsigned int i = 0; i < tx.vin.size(); i++) {
297 if (!HaveCoin(tx.vin[i].prevout)) {
298 return false;
299 }
300 }
301 }
302 return true;
303 }
304
305 void CCoinsViewCache::ReallocateCache()
306 {
307 // Cache should be empty when we're calling this.
308 assert(cacheCoins.size() == 0);
309 cacheCoins.~CCoinsMap();
310 m_cache_coins_memory_resource.~CCoinsMapMemoryResource();
311 ::new (&m_cache_coins_memory_resource) CCoinsMapMemoryResource{};
312 ::new (&cacheCoins) CCoinsMap{0, SaltedOutpointHasher{/*deterministic=*/m_deterministic}, CCoinsMap::key_equal{}, &m_cache_coins_memory_resource};
313 }
314
315 void CCoinsViewCache::SanityCheck() const
316 {
317 size_t recomputed_usage = 0;
318 size_t count_flagged = 0;
319 for (const auto& [_, entry] : cacheCoins) {
320 unsigned attr = 0;
321 if (entry.IsDirty()) attr |= 1;
322 if (entry.IsFresh()) attr |= 2;
323 if (entry.coin.IsSpent()) attr |= 4;
324 // Only 5 combinations are possible.
325 assert(attr != 2 && attr != 4 && attr != 7);
326
327 // Recompute cachedCoinsUsage.
328 recomputed_usage += entry.coin.DynamicMemoryUsage();
329
330 // Count the number of entries we expect in the linked list.
331 if (entry.IsDirty() || entry.IsFresh()) ++count_flagged;
332 }
333 // Iterate over the linked list of flagged entries.
334 size_t count_linked = 0;
335 for (auto it = m_sentinel.second.Next(); it != &m_sentinel; it = it->second.Next()) {
336 // Verify linked list integrity.
337 assert(it->second.Next()->second.Prev() == it);
338 assert(it->second.Prev()->second.Next() == it);
339 // Verify they are actually flagged.
340 assert(it->second.IsDirty() || it->second.IsFresh());
341 // Count the number of entries actually in the list.
342 ++count_linked;
343 }
344 assert(count_linked == count_flagged);
345 assert(recomputed_usage == cachedCoinsUsage);
346 }
347
348 static const size_t MIN_TRANSACTION_OUTPUT_WEIGHT = WITNESS_SCALE_FACTOR * ::GetSerializeSize(CTxOut());
349 static const size_t MAX_OUTPUTS_PER_BLOCK = MAX_BLOCK_WEIGHT / MIN_TRANSACTION_OUTPUT_WEIGHT;
350
351 const Coin& AccessByTxid(const CCoinsViewCache& view, const Txid& txid)
352 {
353 COutPoint iter(txid, 0);
354 while (iter.n < MAX_OUTPUTS_PER_BLOCK) {
355 const Coin& alternate = view.AccessCoin(iter);
356 if (!alternate.IsSpent()) return alternate;
357 ++iter.n;
358 }
359 return coinEmpty;
360 }
361
362 template <typename ReturnType, typename Func>
363 static ReturnType ExecuteBackedWrapper(Func func, const std::vector<std::function<void()>>& err_callbacks)
364 {
365 try {
366 return func();
367 } catch(const std::runtime_error& e) {
368 for (const auto& f : err_callbacks) {
369 f();
370 }
371 LogError("Error reading from database: %s\n", e.what());
372 // Starting the shutdown sequence and returning false to the caller would be
373 // interpreted as 'entry not found' (as opposed to unable to read data), and
374 // could lead to invalid interpretation. Just exit immediately, as we can't
375 // continue anyway, and all writes should be atomic.
376 std::abort();
377 }
378 }
379
380 std::optional<Coin> CCoinsViewErrorCatcher::GetCoin(const COutPoint& outpoint) const
381 {
382 return ExecuteBackedWrapper<std::optional<Coin>>([&]() { return CCoinsViewBacked::GetCoin(outpoint); }, m_err_callbacks);
383 }
384
385 bool CCoinsViewErrorCatcher::HaveCoin(const COutPoint& outpoint) const
386 {
387 return ExecuteBackedWrapper<bool>([&]() { return CCoinsViewBacked::HaveCoin(outpoint); }, m_err_callbacks);
388 }
389