src/coins.cpp

   1 // Copyright (c) 2012-2016 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 "memusage.h"
   9 #include "random.h"
  10
  11 #include <assert.h>
  12
  13 /**
  14  * calculate number of bytes for the bitmask, and its number of non-zero bytes
  15  * each bit in the bitmask represents the availability of one output, but the
  16  * availabilities of the first two outputs are encoded separately
  17  */
  18 void CCoins::CalcMaskSize(unsigned int &nBytes, unsigned int &nNonzeroBytes) const {
  19     unsigned int nLastUsedByte = 0;
  20     for (unsigned int b = 0; 2+b*8 < vout.size(); b++) {
  21         bool fZero = true;
  22         for (unsigned int i = 0; i < 8 && 2+b*8+i < vout.size(); i++) {
  23             if (!vout[2+b*8+i].IsNull()) {
  24                 fZero = false;
  25                 continue;
  26             }
  27         }
  28         if (!fZero) {
  29             nLastUsedByte = b + 1;
  30             nNonzeroBytes++;
  31         }
  32     }
  33     nBytes += nLastUsedByte;
  34 }
  35
  36 bool CCoins::Spend(uint32_t nPos)
  37 {
  38     if (nPos >= vout.size() || vout[nPos].IsNull())
  39         return false;
  40     vout[nPos].SetNull();
  41     Cleanup();
  42     return true;
  43 }
  44
  45 bool CCoinsView::GetCoins(const uint256 &txid, CCoins &coins) const { return false; }
  46 bool CCoinsView::HaveCoins(const uint256 &txid) const { return false; }
  47 uint256 CCoinsView::GetBestBlock() const { return uint256(); }
  48 bool CCoinsView::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) { return false; }
  49 CCoinsViewCursor *CCoinsView::Cursor() const { return 0; }
  50
  51
  52 CCoinsViewBacked::CCoinsViewBacked(CCoinsView *viewIn) : base(viewIn) { }
  53 bool CCoinsViewBacked::GetCoins(const uint256 &txid, CCoins &coins) const { return base->GetCoins(txid, coins); }
  54 bool CCoinsViewBacked::HaveCoins(const uint256 &txid) const { return base->HaveCoins(txid); }
  55 uint256 CCoinsViewBacked::GetBestBlock() const { return base->GetBestBlock(); }
  56 void CCoinsViewBacked::SetBackend(CCoinsView &viewIn) { base = &viewIn; }
  57 bool CCoinsViewBacked::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) { return base->BatchWrite(mapCoins, hashBlock); }
  58 CCoinsViewCursor *CCoinsViewBacked::Cursor() const { return base->Cursor(); }
  59 size_t CCoinsViewBacked::EstimateSize() const { return base->EstimateSize(); }
  60
  61 SaltedTxidHasher::SaltedTxidHasher() : k0(GetRand(std::numeric_limits<uint64_t>::max())), k1(GetRand(std::numeric_limits<uint64_t>::max())) {}
  62
  63 CCoinsViewCache::CCoinsViewCache(CCoinsView *baseIn) : CCoinsViewBacked(baseIn), hasModifier(false), cachedCoinsUsage(0) { }
  64
  65 CCoinsViewCache::~CCoinsViewCache()
  66 {
  67     assert(!hasModifier);
  68 }
  69
  70 size_t CCoinsViewCache::DynamicMemoryUsage() const {
  71     return memusage::DynamicUsage(cacheCoins) + cachedCoinsUsage;
  72 }
  73
  74 CCoinsMap::iterator CCoinsViewCache::FetchCoins(const uint256 &txid) const {
  75     CCoinsMap::iterator it = cacheCoins.find(txid);
  76     if (it != cacheCoins.end())
  77         return it;
  78     CCoins tmp;
  79     if (!base->GetCoins(txid, tmp))
  80         return cacheCoins.end();
  81     CCoinsMap::iterator ret = cacheCoins.insert(std::make_pair(txid, CCoinsCacheEntry())).first;
  82     tmp.swap(ret->second.coins);
  83     if (ret->second.coins.IsPruned()) {
  84         // The parent only has an empty entry for this txid; we can consider our
  85         // version as fresh.
  86         ret->second.flags = CCoinsCacheEntry::FRESH;
  87     }
  88     cachedCoinsUsage += ret->second.coins.DynamicMemoryUsage();
  89     return ret;
  90 }
  91
  92 bool CCoinsViewCache::GetCoins(const uint256 &txid, CCoins &coins) const {
  93     CCoinsMap::const_iterator it = FetchCoins(txid);
  94     if (it != cacheCoins.end()) {
  95         coins = it->second.coins;
  96         return true;
  97     }
  98     return false;
  99 }
 100
 101 CCoinsModifier CCoinsViewCache::ModifyCoins(const uint256 &txid) {
 102     assert(!hasModifier);
 103     std::pair<CCoinsMap::iterator, bool> ret = cacheCoins.insert(std::make_pair(txid, CCoinsCacheEntry()));
 104     size_t cachedCoinUsage = 0;
 105     if (ret.second) {
 106         if (!base->GetCoins(txid, ret.first->second.coins)) {
 107             // The parent view does not have this entry; mark it as fresh.
 108             ret.first->second.coins.Clear();
 109             ret.first->second.flags = CCoinsCacheEntry::FRESH;
 110         } else if (ret.first->second.coins.IsPruned()) {
 111             // The parent view only has a pruned entry for this; mark it as fresh.
 112             ret.first->second.flags = CCoinsCacheEntry::FRESH;
 113         }
 114     } else {
 115         cachedCoinUsage = ret.first->second.coins.DynamicMemoryUsage();
 116     }
 117     // Assume that whenever ModifyCoins is called, the entry will be modified.
 118     ret.first->second.flags |= CCoinsCacheEntry::DIRTY;
 119     return CCoinsModifier(*this, ret.first, cachedCoinUsage);
 120 }
 121
 122 /* ModifyNewCoins allows for faster coin modification when creating the new
 123  * outputs from a transaction.  It assumes that BIP 30 (no duplicate txids)
 124  * applies and has already been tested for (or the test is not required due to
 125  * BIP 34, height in coinbase).  If we can assume BIP 30 then we know that any
 126  * non-coinbase transaction we are adding to the UTXO must not already exist in
 127  * the utxo unless it is fully spent.  Thus we can check only if it exists DIRTY
 128  * at the current level of the cache, in which case it is not safe to mark it
 129  * FRESH (b/c then its spentness still needs to flushed).  If it's not dirty and
 130  * doesn't exist or is pruned in the current cache, we know it either doesn't
 131  * exist or is pruned in parent caches, which is the definition of FRESH.  The
 132  * exception to this is the two historical violations of BIP 30 in the chain,
 133  * both of which were coinbases.  We do not mark these fresh so we we can ensure
 134  * that they will still be properly overwritten when spent.
 135  */
 136 CCoinsModifier CCoinsViewCache::ModifyNewCoins(const uint256 &txid, bool coinbase) {
 137     assert(!hasModifier);
 138     std::pair<CCoinsMap::iterator, bool> ret = cacheCoins.insert(std::make_pair(txid, CCoinsCacheEntry()));
 139     if (!coinbase) {
 140         // New coins must not already exist.
 141         if (!ret.first->second.coins.IsPruned())
 142             throw std::logic_error("ModifyNewCoins should not find pre-existing coins on a non-coinbase unless they are pruned!");
 143
 144         if (!(ret.first->second.flags & CCoinsCacheEntry::DIRTY)) {
 145             // If the coin is known to be pruned (have no unspent outputs) in
 146             // the current view and the cache entry is not dirty, we know the
 147             // coin also must be pruned in the parent view as well, so it is safe
 148             // to mark this fresh.
 149             ret.first->second.flags |= CCoinsCacheEntry::FRESH;
 150         }
 151     }
 152     ret.first->second.coins.Clear();
 153     ret.first->second.flags |= CCoinsCacheEntry::DIRTY;
 154     return CCoinsModifier(*this, ret.first, 0);
 155 }
 156
 157 void CCoinsViewCache::AddCoin(const COutPoint &outpoint, Coin&& coin, bool possible_overwrite) {
 158     assert(!coin.IsPruned());
 159     if (coin.out.scriptPubKey.IsUnspendable()) return;
 160     CCoinsMap::iterator it;
 161     bool inserted;
 162     std::tie(it, inserted) = cacheCoins.emplace(std::piecewise_construct, std::forward_as_tuple(outpoint.hash), std::tuple<>());
 163     bool fresh = false;
 164     if (!inserted) {
 165         cachedCoinsUsage -= it->second.coins.DynamicMemoryUsage();
 166     }
 167     if (!possible_overwrite) {
 168         if (it->second.coins.IsAvailable(outpoint.n)) {
 169             throw std::logic_error("Adding new coin that replaces non-pruned entry");
 170         }
 171         fresh = it->second.coins.IsPruned() && !(it->second.flags & CCoinsCacheEntry::DIRTY);
 172     }
 173     if (it->second.coins.vout.size() <= outpoint.n) {
 174         it->second.coins.vout.resize(outpoint.n + 1);
 175     }
 176     it->second.coins.vout[outpoint.n] = std::move(coin.out);
 177     it->second.coins.nHeight = coin.nHeight;
 178     it->second.coins.fCoinBase = coin.fCoinBase;
 179     it->second.flags |= CCoinsCacheEntry::DIRTY | (fresh ? CCoinsCacheEntry::FRESH : 0);
 180     cachedCoinsUsage += it->second.coins.DynamicMemoryUsage();
 181 }
 182
 183 void AddCoins(CCoinsViewCache& cache, const CTransaction &tx, int nHeight) {
 184     bool fCoinbase = tx.IsCoinBase();
 185     const uint256& txid = tx.GetHash();
 186     for (size_t i = 0; i < tx.vout.size(); ++i) {
 187         // Pass fCoinbase as the possible_overwrite flag to AddCoin, in order to correctly
 188         // deal with the pre-BIP30 occurrances of duplicate coinbase transactions.
 189         cache.AddCoin(COutPoint(txid, i), Coin(tx.vout[i], nHeight, fCoinbase), fCoinbase);
 190     }
 191 }
 192
 193 void CCoinsViewCache::SpendCoin(const COutPoint &outpoint, Coin* moveout) {
 194     CCoinsMap::iterator it = FetchCoins(outpoint.hash);
 195     if (it == cacheCoins.end()) return;
 196     cachedCoinsUsage -= it->second.coins.DynamicMemoryUsage();
 197     if (moveout && it->second.coins.IsAvailable(outpoint.n)) {
 198         *moveout = Coin(it->second.coins.vout[outpoint.n], it->second.coins.nHeight, it->second.coins.fCoinBase);
 199     }
 200     it->second.coins.Spend(outpoint.n); // Ignore return value: SpendCoin has no effect if no UTXO found.
 201     if (it->second.coins.IsPruned() && it->second.flags & CCoinsCacheEntry::FRESH) {
 202         cacheCoins.erase(it);
 203     } else {
 204         cachedCoinsUsage += it->second.coins.DynamicMemoryUsage();
 205         it->second.flags |= CCoinsCacheEntry::DIRTY;
 206     }
 207 }
 208
 209 const CCoins* CCoinsViewCache::AccessCoins(const uint256 &txid) const {
 210     CCoinsMap::const_iterator it = FetchCoins(txid);
 211     if (it == cacheCoins.end()) {
 212         return NULL;
 213     } else {
 214         return &it->second.coins;
 215     }
 216 }
 217
 218 static const Coin coinEmpty;
 219
 220 const Coin CCoinsViewCache::AccessCoin(const COutPoint &outpoint) const {
 221     CCoinsMap::const_iterator it = FetchCoins(outpoint.hash);
 222     if (it == cacheCoins.end() || !it->second.coins.IsAvailable(outpoint.n)) {
 223         return coinEmpty;
 224     } else {
 225         return Coin(it->second.coins.vout[outpoint.n], it->second.coins.nHeight, it->second.coins.fCoinBase);
 226     }
 227 }
 228
 229
 230 bool CCoinsViewCache::HaveCoins(const uint256 &txid) const {
 231     CCoinsMap::const_iterator it = FetchCoins(txid);
 232     // We're using vtx.empty() instead of IsPruned here for performance reasons,
 233     // as we only care about the case where a transaction was replaced entirely
 234     // in a reorganization (which wipes vout entirely, as opposed to spending
 235     // which just cleans individual outputs).
 236     return (it != cacheCoins.end() && !it->second.coins.vout.empty());
 237 }
 238
 239 bool CCoinsViewCache::HaveCoins(const COutPoint &outpoint) const {
 240     CCoinsMap::const_iterator it = FetchCoins(outpoint.hash);
 241     return (it != cacheCoins.end() && it->second.coins.IsAvailable(outpoint.n));
 242 }
 243
 244 bool CCoinsViewCache::HaveCoinsInCache(const uint256 &txid) const {
 245     CCoinsMap::const_iterator it = cacheCoins.find(txid);
 246     return it != cacheCoins.end();
 247 }
 248
 249 uint256 CCoinsViewCache::GetBestBlock() const {
 250     if (hashBlock.IsNull())
 251         hashBlock = base->GetBestBlock();
 252     return hashBlock;
 253 }
 254
 255 void CCoinsViewCache::SetBestBlock(const uint256 &hashBlockIn) {
 256     hashBlock = hashBlockIn;
 257 }
 258
 259 bool CCoinsViewCache::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlockIn) {
 260     assert(!hasModifier);
 261     for (CCoinsMap::iterator it = mapCoins.begin(); it != mapCoins.end();) {
 262         if (it->second.flags & CCoinsCacheEntry::DIRTY) { // Ignore non-dirty entries (optimization).
 263             CCoinsMap::iterator itUs = cacheCoins.find(it->first);
 264             if (itUs == cacheCoins.end()) {
 265                 // The parent cache does not have an entry, while the child does
 266                 // We can ignore it if it's both FRESH and pruned in the child
 267                 if (!(it->second.flags & CCoinsCacheEntry::FRESH && it->second.coins.IsPruned())) {
 268                     // Otherwise we will need to create it in the parent
 269                     // and move the data up and mark it as dirty
 270                     CCoinsCacheEntry& entry = cacheCoins[it->first];
 271                     entry.coins.swap(it->second.coins);
 272                     cachedCoinsUsage += entry.coins.DynamicMemoryUsage();
 273                     entry.flags = CCoinsCacheEntry::DIRTY;
 274                     // We can mark it FRESH in the parent if it was FRESH in the child
 275                     // Otherwise it might have just been flushed from the parent's cache
 276                     // and already exist in the grandparent
 277                     if (it->second.flags & CCoinsCacheEntry::FRESH)
 278                         entry.flags |= CCoinsCacheEntry::FRESH;
 279                 }
 280             } else {
 281                 // Assert that the child cache entry was not marked FRESH if the
 282                 // parent cache entry has unspent outputs. If this ever happens,
 283                 // it means the FRESH flag was misapplied and there is a logic
 284                 // error in the calling code.
 285                 if ((it->second.flags & CCoinsCacheEntry::FRESH) && !itUs->second.coins.IsPruned())
 286                     throw std::logic_error("FRESH flag misapplied to cache entry for base transaction with spendable outputs");
 287
 288                 // Found the entry in the parent cache
 289                 if ((itUs->second.flags & CCoinsCacheEntry::FRESH) && it->second.coins.IsPruned()) {
 290                     // The grandparent does not have an entry, and the child is
 291                     // modified and being pruned. This means we can just delete
 292                     // it from the parent.
 293                     cachedCoinsUsage -= itUs->second.coins.DynamicMemoryUsage();
 294                     cacheCoins.erase(itUs);
 295                 } else {
 296                     // A normal modification.
 297                     cachedCoinsUsage -= itUs->second.coins.DynamicMemoryUsage();
 298                     itUs->second.coins.swap(it->second.coins);
 299                     cachedCoinsUsage += itUs->second.coins.DynamicMemoryUsage();
 300                     itUs->second.flags |= CCoinsCacheEntry::DIRTY;
 301                     // NOTE: It is possible the child has a FRESH flag here in
 302                     // the event the entry we found in the parent is pruned. But
 303                     // we must not copy that FRESH flag to the parent as that
 304                     // pruned state likely still needs to be communicated to the
 305                     // grandparent.
 306                 }
 307             }
 308         }
 309         CCoinsMap::iterator itOld = it++;
 310         mapCoins.erase(itOld);
 311     }
 312     hashBlock = hashBlockIn;
 313     return true;
 314 }
 315
 316 bool CCoinsViewCache::Flush() {
 317     bool fOk = base->BatchWrite(cacheCoins, hashBlock);
 318     cacheCoins.clear();
 319     cachedCoinsUsage = 0;
 320     return fOk;
 321 }
 322
 323 void CCoinsViewCache::Uncache(const uint256& hash)
 324 {
 325     CCoinsMap::iterator it = cacheCoins.find(hash);
 326     if (it != cacheCoins.end() && it->second.flags == 0) {
 327         cachedCoinsUsage -= it->second.coins.DynamicMemoryUsage();
 328         cacheCoins.erase(it);
 329     }
 330 }
 331
 332 unsigned int CCoinsViewCache::GetCacheSize() const {
 333     return cacheCoins.size();
 334 }
 335
 336 const CTxOut &CCoinsViewCache::GetOutputFor(const CTxIn& input) const
 337 {
 338     const CCoins* coins = AccessCoins(input.prevout.hash);
 339     assert(coins && coins->IsAvailable(input.prevout.n));
 340     return coins->vout[input.prevout.n];
 341 }
 342
 343 CAmount CCoinsViewCache::GetValueIn(const CTransaction& tx) const
 344 {
 345     if (tx.IsCoinBase())
 346         return 0;
 347
 348     CAmount nResult = 0;
 349     for (unsigned int i = 0; i < tx.vin.size(); i++)
 350         nResult += GetOutputFor(tx.vin[i]).nValue;
 351
 352     return nResult;
 353 }
 354
 355 bool CCoinsViewCache::HaveInputs(const CTransaction& tx) const
 356 {
 357     if (!tx.IsCoinBase()) {
 358         for (unsigned int i = 0; i < tx.vin.size(); i++) {
 359             const COutPoint &prevout = tx.vin[i].prevout;
 360             const CCoins* coins = AccessCoins(prevout.hash);
 361             if (!coins || !coins->IsAvailable(prevout.n)) {
 362                 return false;
 363             }
 364         }
 365     }
 366     return true;
 367 }
 368
 369 CCoinsModifier::CCoinsModifier(CCoinsViewCache& cache_, CCoinsMap::iterator it_, size_t usage) : cache(cache_), it(it_), cachedCoinUsage(usage) {
 370     assert(!cache.hasModifier);
 371     cache.hasModifier = true;
 372 }
 373
 374 CCoinsModifier::~CCoinsModifier()
 375 {
 376     assert(cache.hasModifier);
 377     cache.hasModifier = false;
 378     it->second.coins.Cleanup();
 379     cache.cachedCoinsUsage -= cachedCoinUsage; // Subtract the old usage
 380     if ((it->second.flags & CCoinsCacheEntry::FRESH) && it->second.coins.IsPruned()) {
 381         cache.cacheCoins.erase(it);
 382     } else {
 383         // If the coin still exists after the modification, add the new usage
 384         cache.cachedCoinsUsage += it->second.coins.DynamicMemoryUsage();
 385     }
 386 }
 387
 388 CCoinsViewCursor::~CCoinsViewCursor()
 389 {
 390 }
 391
 392 static const size_t MAX_OUTPUTS_PER_BLOCK = MAX_BLOCK_BASE_SIZE /  ::GetSerializeSize(CTxOut(), SER_NETWORK, PROTOCOL_VERSION); // TODO: merge with similar definition in undo.h.
 393
 394 const Coin AccessByTxid(const CCoinsViewCache& view, const uint256& txid)
 395 {
 396     COutPoint iter(txid, 0);
 397     while (iter.n < MAX_OUTPUTS_PER_BLOCK) {
 398         const Coin& alternate = view.AccessCoin(iter);
 399         if (!alternate.IsPruned()) return alternate;
 400         ++iter.n;
 401     }
 402     return coinEmpty;
 403 }