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