src/coins.cpp

   1 // Copyright (c) 2012-2014 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 bool CCoinsView::GetAnchorAt(const uint256 &rt, ZCIncrementalMerkleTree &tree) const { return false; }
  44 bool CCoinsView::GetSerial(const uint256 &serial) const { return false; }
  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 uint256 CCoinsView::GetBestAnchor() const { return uint256(); };
  49 bool CCoinsView::BatchWrite(CCoinsMap &mapCoins,
  50                             const uint256 &hashBlock,
  51                             const uint256 &hashAnchor,
  52                             CAnchorsMap &mapAnchors,
  53                             CSerialsMap &mapSerials) { return false; }
  54 bool CCoinsView::GetStats(CCoinsStats &stats) const { return false; }
  55
  56
  57 CCoinsViewBacked::CCoinsViewBacked(CCoinsView *viewIn) : base(viewIn) { }
  58
  59 bool CCoinsViewBacked::GetAnchorAt(const uint256 &rt, ZCIncrementalMerkleTree &tree) const { return base->GetAnchorAt(rt, tree); }
  60 bool CCoinsViewBacked::GetSerial(const uint256 &serial) const { return base->GetSerial(serial); }
  61 bool CCoinsViewBacked::GetCoins(const uint256 &txid, CCoins &coins) const { return base->GetCoins(txid, coins); }
  62 bool CCoinsViewBacked::HaveCoins(const uint256 &txid) const { return base->HaveCoins(txid); }
  63 uint256 CCoinsViewBacked::GetBestBlock() const { return base->GetBestBlock(); }
  64 uint256 CCoinsViewBacked::GetBestAnchor() const { return base->GetBestAnchor(); }
  65 void CCoinsViewBacked::SetBackend(CCoinsView &viewIn) { base = &viewIn; }
  66 bool CCoinsViewBacked::BatchWrite(CCoinsMap &mapCoins,
  67                                   const uint256 &hashBlock,
  68                                   const uint256 &hashAnchor,
  69                                   CAnchorsMap &mapAnchors,
  70                                   CSerialsMap &mapSerials) { return base->BatchWrite(mapCoins, hashBlock, hashAnchor, mapAnchors, mapSerials); }
  71 bool CCoinsViewBacked::GetStats(CCoinsStats &stats) const { return base->GetStats(stats); }
  72
  73 CCoinsKeyHasher::CCoinsKeyHasher() : salt(GetRandHash()) {}
  74
  75 CCoinsViewCache::CCoinsViewCache(CCoinsView *baseIn) : CCoinsViewBacked(baseIn), hasModifier(false), cachedCoinsUsage(0) { }
  76
  77 CCoinsViewCache::~CCoinsViewCache()
  78 {
  79     assert(!hasModifier);
  80 }
  81
  82 size_t CCoinsViewCache::DynamicMemoryUsage() const {
  83     return memusage::DynamicUsage(cacheCoins) +
  84            memusage::DynamicUsage(cacheAnchors) +
  85            memusage::DynamicUsage(cacheSerials) +
  86            cachedCoinsUsage;
  87 }
  88
  89 CCoinsMap::const_iterator CCoinsViewCache::FetchCoins(const uint256 &txid) const {
  90     CCoinsMap::iterator it = cacheCoins.find(txid);
  91     if (it != cacheCoins.end())
  92         return it;
  93     CCoins tmp;
  94     if (!base->GetCoins(txid, tmp))
  95         return cacheCoins.end();
  96     CCoinsMap::iterator ret = cacheCoins.insert(std::make_pair(txid, CCoinsCacheEntry())).first;
  97     tmp.swap(ret->second.coins);
  98     if (ret->second.coins.IsPruned()) {
  99         // The parent only has an empty entry for this txid; we can consider our
 100         // version as fresh.
 101         ret->second.flags = CCoinsCacheEntry::FRESH;
 102     }
 103     cachedCoinsUsage += memusage::DynamicUsage(ret->second.coins);
 104     return ret;
 105 }
 106
 107
 108 bool CCoinsViewCache::GetAnchorAt(const uint256 &rt, ZCIncrementalMerkleTree &tree) const {
 109     CAnchorsMap::const_iterator it = cacheAnchors.find(rt);
 110     if (it != cacheAnchors.end()) {
 111         if (it->second.entered) {
 112             tree = it->second.tree;
 113             return true;
 114         } else {
 115             return false;
 116         }
 117     }
 118
 119     if (!base->GetAnchorAt(rt, tree)) {
 120         return false;
 121     }
 122
 123     CAnchorsMap::iterator ret = cacheAnchors.insert(std::make_pair(rt, CAnchorsCacheEntry())).first;
 124     ret->second.entered = true;
 125     ret->second.tree = tree;
 126     cachedCoinsUsage += memusage::DynamicUsage(ret->second.tree);
 127
 128     return true;
 129 }
 130
 131 bool CCoinsViewCache::GetSerial(const uint256 &serial) const {
 132     CSerialsMap::iterator it = cacheSerials.find(serial);
 133     if (it != cacheSerials.end())
 134         return it->second.entered;
 135
 136     CSerialsCacheEntry entry;
 137     bool tmp = base->GetSerial(serial);
 138     entry.entered = tmp;
 139
 140     cacheSerials.insert(std::make_pair(serial, entry));
 141
 142     return tmp;
 143 }
 144
 145 void CCoinsViewCache::PushAnchor(const ZCIncrementalMerkleTree &tree) {
 146     uint256 newrt = tree.root();
 147
 148     auto currentRoot = GetBestAnchor();
 149
 150     // We don't want to overwrite an anchor we already have.
 151     // This occurs when a block doesn't modify mapAnchors at all,
 152     // because there are no pours. We could get around this a
 153     // different way (make all blocks modify mapAnchors somehow)
 154     // but this is simpler to reason about.
 155     if (currentRoot != newrt) {
 156         auto insertRet = cacheAnchors.insert(std::make_pair(newrt, CAnchorsCacheEntry()));
 157         CAnchorsMap::iterator ret = insertRet.first;
 158
 159         ret->second.entered = true;
 160         ret->second.tree = tree;
 161         ret->second.flags = CAnchorsCacheEntry::DIRTY;
 162
 163         if (insertRet.second) {
 164             // An insert took place
 165             cachedCoinsUsage += memusage::DynamicUsage(ret->second.tree);
 166         }
 167
 168         hashAnchor = newrt;
 169     }
 170 }
 171
 172 void CCoinsViewCache::PopAnchor(const uint256 &newrt) {
 173     auto currentRoot = GetBestAnchor();
 174
 175     // Blocks might not change the commitment tree, in which
 176     // case restoring the "old" anchor during a reorg must
 177     // have no effect.
 178     if (currentRoot != newrt) {
 179         CAnchorsMap::iterator ret = cacheAnchors.insert(std::make_pair(currentRoot, CAnchorsCacheEntry())).first;
 180
 181         ret->second.entered = false;
 182         ret->second.flags = CAnchorsCacheEntry::DIRTY;
 183
 184         hashAnchor = newrt;
 185     }
 186 }
 187
 188 void CCoinsViewCache::SetSerial(const uint256 &serial, bool spent) {
 189     std::pair<CSerialsMap::iterator, bool> ret = cacheSerials.insert(std::make_pair(serial, CSerialsCacheEntry()));
 190     ret.first->second.entered = spent;
 191     ret.first->second.flags |= CSerialsCacheEntry::DIRTY;
 192 }
 193
 194 bool CCoinsViewCache::GetCoins(const uint256 &txid, CCoins &coins) const {
 195     CCoinsMap::const_iterator it = FetchCoins(txid);
 196     if (it != cacheCoins.end()) {
 197         coins = it->second.coins;
 198         return true;
 199     }
 200     return false;
 201 }
 202
 203 CCoinsModifier CCoinsViewCache::ModifyCoins(const uint256 &txid) {
 204     assert(!hasModifier);
 205     std::pair<CCoinsMap::iterator, bool> ret = cacheCoins.insert(std::make_pair(txid, CCoinsCacheEntry()));
 206     size_t cachedCoinUsage = 0;
 207     if (ret.second) {
 208         if (!base->GetCoins(txid, ret.first->second.coins)) {
 209             // The parent view does not have this entry; mark it as fresh.
 210             ret.first->second.coins.Clear();
 211             ret.first->second.flags = CCoinsCacheEntry::FRESH;
 212         } else if (ret.first->second.coins.IsPruned()) {
 213             // The parent view only has a pruned entry for this; mark it as fresh.
 214             ret.first->second.flags = CCoinsCacheEntry::FRESH;
 215         }
 216     } else {
 217         cachedCoinUsage = memusage::DynamicUsage(ret.first->second.coins);
 218     }
 219     // Assume that whenever ModifyCoins is called, the entry will be modified.
 220     ret.first->second.flags |= CCoinsCacheEntry::DIRTY;
 221     return CCoinsModifier(*this, ret.first, cachedCoinUsage);
 222 }
 223
 224 const CCoins* CCoinsViewCache::AccessCoins(const uint256 &txid) const {
 225     CCoinsMap::const_iterator it = FetchCoins(txid);
 226     if (it == cacheCoins.end()) {
 227         return NULL;
 228     } else {
 229         return &it->second.coins;
 230     }
 231 }
 232
 233 bool CCoinsViewCache::HaveCoins(const uint256 &txid) const {
 234     CCoinsMap::const_iterator it = FetchCoins(txid);
 235     // We're using vtx.empty() instead of IsPruned here for performance reasons,
 236     // as we only care about the case where a transaction was replaced entirely
 237     // in a reorganization (which wipes vout entirely, as opposed to spending
 238     // which just cleans individual outputs).
 239     return (it != cacheCoins.end() && !it->second.coins.vout.empty());
 240 }
 241
 242 uint256 CCoinsViewCache::GetBestBlock() const {
 243     if (hashBlock.IsNull())
 244         hashBlock = base->GetBestBlock();
 245     return hashBlock;
 246 }
 247
 248
 249 uint256 CCoinsViewCache::GetBestAnchor() const {
 250     if (hashAnchor.IsNull())
 251         hashAnchor = base->GetBestAnchor();
 252     return hashAnchor;
 253 }
 254
 255 void CCoinsViewCache::SetBestBlock(const uint256 &hashBlockIn) {
 256     hashBlock = hashBlockIn;
 257 }
 258
 259 bool CCoinsViewCache::BatchWrite(CCoinsMap &mapCoins,
 260                                  const uint256 &hashBlockIn,
 261                                  const uint256 &hashAnchorIn,
 262                                  CAnchorsMap &mapAnchors,
 263                                  CSerialsMap &mapSerials) {
 264     assert(!hasModifier);
 265     for (CCoinsMap::iterator it = mapCoins.begin(); it != mapCoins.end();) {
 266         if (it->second.flags & CCoinsCacheEntry::DIRTY) { // Ignore non-dirty entries (optimization).
 267             CCoinsMap::iterator itUs = cacheCoins.find(it->first);
 268             if (itUs == cacheCoins.end()) {
 269                 if (!it->second.coins.IsPruned()) {
 270                     // The parent cache does not have an entry, while the child
 271                     // cache does have (a non-pruned) one. Move the data up, and
 272                     // mark it as fresh (if the grandparent did have it, we
 273                     // would have pulled it in at first GetCoins).
 274                     assert(it->second.flags & CCoinsCacheEntry::FRESH);
 275                     CCoinsCacheEntry& entry = cacheCoins[it->first];
 276                     entry.coins.swap(it->second.coins);
 277                     cachedCoinsUsage += memusage::DynamicUsage(entry.coins);
 278                     entry.flags = CCoinsCacheEntry::DIRTY | CCoinsCacheEntry::FRESH;
 279                 }
 280             } else {
 281                 if ((itUs->second.flags & CCoinsCacheEntry::FRESH) && it->second.coins.IsPruned()) {
 282                     // The grandparent does not have an entry, and the child is
 283                     // modified and being pruned. This means we can just delete
 284                     // it from the parent.
 285                     cachedCoinsUsage -= memusage::DynamicUsage(itUs->second.coins);
 286                     cacheCoins.erase(itUs);
 287                 } else {
 288                     // A normal modification.
 289                     cachedCoinsUsage -= memusage::DynamicUsage(itUs->second.coins);
 290                     itUs->second.coins.swap(it->second.coins);
 291                     cachedCoinsUsage += memusage::DynamicUsage(itUs->second.coins);
 292                     itUs->second.flags |= CCoinsCacheEntry::DIRTY;
 293                 }
 294             }
 295         }
 296         CCoinsMap::iterator itOld = it++;
 297         mapCoins.erase(itOld);
 298     }
 299
 300     for (CAnchorsMap::iterator child_it = mapAnchors.begin(); child_it != mapAnchors.end();)
 301     {
 302         if (child_it->second.flags & CAnchorsCacheEntry::DIRTY) {
 303             CAnchorsMap::iterator parent_it = cacheAnchors.find(child_it->first);
 304
 305             if (parent_it == cacheAnchors.end()) {
 306                 if (child_it->second.entered) {
 307                     // Parent doesn't have an entry, but child has a new commitment root.
 308
 309                     CAnchorsCacheEntry& entry = cacheAnchors[child_it->first];
 310                     entry.entered = true;
 311                     entry.tree = child_it->second.tree;
 312                     entry.flags = CAnchorsCacheEntry::DIRTY;
 313
 314                     cachedCoinsUsage += memusage::DynamicUsage(entry.tree);
 315                 }
 316             } else {
 317                 if (parent_it->second.entered != child_it->second.entered) {
 318                     // The parent may have removed the entry.
 319                     parent_it->second.entered = child_it->second.entered;
 320                     parent_it->second.flags |= CAnchorsCacheEntry::DIRTY;
 321                 }
 322             }
 323         }
 324
 325         CAnchorsMap::iterator itOld = child_it++;
 326         mapAnchors.erase(itOld);
 327     }
 328
 329     for (CSerialsMap::iterator child_it = mapSerials.begin(); child_it != mapSerials.end();)
 330     {
 331         if (child_it->second.flags & CSerialsCacheEntry::DIRTY) { // Ignore non-dirty entries (optimization).
 332             CSerialsMap::iterator parent_it = cacheSerials.find(child_it->first);
 333
 334             if (parent_it == cacheSerials.end()) {
 335                 if (child_it->second.entered) {
 336                     // Parent doesn't have an entry, but child has a SPENT serial.
 337                     // Move the spent serial up.
 338
 339                     CSerialsCacheEntry& entry = cacheSerials[child_it->first];
 340                     entry.entered = true;
 341                     entry.flags = CSerialsCacheEntry::DIRTY;
 342                 }
 343             } else {
 344                 if (parent_it->second.entered != child_it->second.entered) {
 345                     parent_it->second.entered = child_it->second.entered;
 346                     parent_it->second.flags |= CSerialsCacheEntry::DIRTY;
 347                 }
 348             }
 349         }
 350         CSerialsMap::iterator itOld = child_it++;
 351         mapSerials.erase(itOld);
 352     }
 353
 354     hashAnchor = hashAnchorIn;
 355     hashBlock = hashBlockIn;
 356     return true;
 357 }
 358
 359 bool CCoinsViewCache::Flush() {
 360     bool fOk = base->BatchWrite(cacheCoins, hashBlock, hashAnchor, cacheAnchors, cacheSerials);
 361     cacheCoins.clear();
 362     cacheAnchors.clear();
 363     cacheSerials.clear();
 364     cachedCoinsUsage = 0;
 365     return fOk;
 366 }
 367
 368 unsigned int CCoinsViewCache::GetCacheSize() const {
 369     return cacheCoins.size();
 370 }
 371
 372 const CTxOut &CCoinsViewCache::GetOutputFor(const CTxIn& input) const
 373 {
 374     const CCoins* coins = AccessCoins(input.prevout.hash);
 375     assert(coins && coins->IsAvailable(input.prevout.n));
 376     return coins->vout[input.prevout.n];
 377 }
 378
 379 CAmount CCoinsViewCache::GetValueIn(const CTransaction& tx) const
 380 {
 381     if (tx.IsCoinBase())
 382         return 0;
 383
 384     CAmount nResult = 0;
 385     for (unsigned int i = 0; i < tx.vin.size(); i++)
 386         nResult += GetOutputFor(tx.vin[i]).nValue;
 387
 388     nResult += tx.GetPourValueIn();
 389
 390     return nResult;
 391 }
 392
 393 bool CCoinsViewCache::HavePourRequirements(const CTransaction& tx) const
 394 {
 395     boost::unordered_map<uint256, ZCIncrementalMerkleTree, CCoinsKeyHasher> intermediates;
 396
 397     BOOST_FOREACH(const CPourTx &pour, tx.vpour)
 398     {
 399         BOOST_FOREACH(const uint256& serial, pour.serials)
 400         {
 401             if (GetSerial(serial)) {
 402                 // If the serial is set, this transaction
 403                 // double-spends!
 404                 return false;
 405             }
 406         }
 407
 408         ZCIncrementalMerkleTree tree;
 409         auto it = intermediates.find(pour.anchor);
 410         if (it != intermediates.end()) {
 411             tree = it->second;
 412         } else if (!GetAnchorAt(pour.anchor, tree)) {
 413             return false;
 414         }
 415
 416         BOOST_FOREACH(const uint256& commitment, pour.commitments)
 417         {
 418             tree.append(commitment);
 419         }
 420
 421         intermediates.insert(std::make_pair(tree.root(), tree));
 422     }
 423
 424     return true;
 425 }
 426
 427 bool CCoinsViewCache::HaveInputs(const CTransaction& tx) const
 428 {
 429     if (!tx.IsCoinBase()) {
 430         for (unsigned int i = 0; i < tx.vin.size(); i++) {
 431             const COutPoint &prevout = tx.vin[i].prevout;
 432             const CCoins* coins = AccessCoins(prevout.hash);
 433             if (!coins || !coins->IsAvailable(prevout.n)) {
 434                 return false;
 435             }
 436         }
 437     }
 438     return true;
 439 }
 440
 441 double CCoinsViewCache::GetPriority(const CTransaction &tx, int nHeight) const
 442 {
 443     if (tx.IsCoinBase())
 444         return 0.0;
 445     double dResult = 0.0;
 446     BOOST_FOREACH(const CTxIn& txin, tx.vin)
 447     {
 448         const CCoins* coins = AccessCoins(txin.prevout.hash);
 449         assert(coins);
 450         if (!coins->IsAvailable(txin.prevout.n)) continue;
 451         if (coins->nHeight < nHeight) {
 452             dResult += coins->vout[txin.prevout.n].nValue * (nHeight-coins->nHeight);
 453         }
 454     }
 455     return tx.ComputePriority(dResult);
 456 }
 457
 458 CCoinsModifier::CCoinsModifier(CCoinsViewCache& cache_, CCoinsMap::iterator it_, size_t usage) : cache(cache_), it(it_), cachedCoinUsage(usage) {
 459     assert(!cache.hasModifier);
 460     cache.hasModifier = true;
 461 }
 462
 463 CCoinsModifier::~CCoinsModifier()
 464 {
 465     assert(cache.hasModifier);
 466     cache.hasModifier = false;
 467     it->second.coins.Cleanup();
 468     cache.cachedCoinsUsage -= cachedCoinUsage; // Subtract the old usage
 469     if ((it->second.flags & CCoinsCacheEntry::FRESH) && it->second.coins.IsPruned()) {
 470         cache.cacheCoins.erase(it);
 471     } else {
 472         // If the coin still exists after the modification, add the new usage
 473         cache.cachedCoinsUsage += memusage::DynamicUsage(it->second.coins);
 474     }
 475 }