Fabcoin Core  0.16.2
P2P Digital Currency
BlockQueue.cpp
Go to the documentation of this file.
1 /*
2  This file is part of cpp-ethereum.
3 
4  cpp-ethereum is free software: you can redistribute it and/or modify
5  it under the terms of the GNU General Public License as published by
6  the Free Software Foundation, either version 3 of the License, or
7  (at your option) any later version.
8 
9  cpp-ethereum is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  GNU General Public License for more details.
13 
14  You should have received a copy of the GNU General Public License
15  along with cpp-ethereum. If not, see <http://www.gnu.org/licenses/>.
16 */
22 #include "BlockQueue.h"
23 #include <thread>
24 #include <sstream>
25 #include <libdevcore/Log.h>
26 #include <libethcore/Exceptions.h>
27 #include <libethcore/BlockHeader.h>
28 #include "BlockChain.h"
29 #include "VerifiedBlock.h"
30 #include "State.h"
31 using namespace std;
32 using namespace dev;
33 using namespace dev::eth;
34 
35 #if defined(_WIN32)
36 const char* BlockQueueChannel::name() { return EthOrange "[]>"; }
37 #else
38 const char* BlockQueueChannel::name() { return EthOrange "▣┅▶"; }
39 #endif
40 const char* BlockQueueTraceChannel::name() { return EthOrange "▣ ▶"; }
41 
42 size_t const c_maxKnownCount = 100000;
43 size_t const c_maxKnownSize = 128 * 1024 * 1024;
44 size_t const c_maxUnknownCount = 100000;
45 size_t const c_maxUnknownSize = 512 * 1024 * 1024; // Block size can be ~50kb
46 
47 BlockQueue::BlockQueue()
48 {
49  // Allow some room for other activity
50  unsigned verifierThreads = std::max(thread::hardware_concurrency(), 3U) - 2U;
51  for (unsigned i = 0; i < verifierThreads; ++i)
52  m_verifiers.emplace_back([=](){
53  setThreadName("verifier" + toString(i));
54  this->verifierBody();
55  });
56 }
57 
58 BlockQueue::~BlockQueue()
59 {
60  stop();
61 }
62 
64 {
65  DEV_GUARDED(m_verification)
66  m_deleting = true;
67 
68  m_moreToVerify.notify_all();
69  for (auto& i: m_verifiers)
70  i.join();
71  m_verifiers.clear();
72 }
73 
74 void BlockQueue::clear()
75 {
76  WriteGuard l(m_lock);
78  Guard l2(m_verification);
79  m_readySet.clear();
80  m_drainingSet.clear();
81  m_verified.clear();
82  m_unverified.clear();
83  m_verifying.clear();
84  m_unknownSet.clear();
85  m_unknown.clear();
86  m_future.clear();
87  m_difficulty = 0;
88  m_drainingDifficulty = 0;
89 }
90 
91 void BlockQueue::verifierBody()
92 {
93  while (!m_deleting)
94  {
95  UnverifiedBlock work;
96 
97  {
98  unique_lock<Mutex> l(m_verification);
99  m_moreToVerify.wait(l, [&](){ return !m_unverified.isEmpty() || m_deleting; });
100  if (m_deleting)
101  return;
102  work = m_unverified.dequeue();
103 
104  BlockHeader bi;
105  bi.setSha3Uncles(work.hash);
106  bi.setParentHash(work.parentHash);
107  m_verifying.enqueue(move(bi));
108  }
109 
110  VerifiedBlock res;
111  swap(work.blockData, res.blockData);
112  try
113  {
114  res.verified = m_bc->verifyBlock(&res.blockData, m_onBad, ImportRequirements::OutOfOrderChecks);
115  }
116  catch (std::exception const& _ex)
117  {
118  // bad block.
119  // has to be this order as that's how invariants() assumes.
120  WriteGuard l2(m_lock);
121  unique_lock<Mutex> l(m_verification);
122  m_readySet.erase(work.hash);
123  m_knownBad.insert(work.hash);
124  if (!m_verifying.remove(work.hash))
125  cwarn << "Unexpected exception when verifying block: " << _ex.what();
126  drainVerified_WITH_BOTH_LOCKS();
127  continue;
128  }
129 
130  bool ready = false;
131  {
132  WriteGuard l2(m_lock);
133  unique_lock<Mutex> l(m_verification);
134  if (!m_verifying.isEmpty() && m_verifying.nextHash() == work.hash)
135  {
136  // we're next!
137  m_verifying.dequeue();
138  if (m_knownBad.count(res.verified.info.parentHash()))
139  {
140  m_readySet.erase(res.verified.info.hash());
141  m_knownBad.insert(res.verified.info.hash());
142  }
143  else
144  m_verified.enqueue(move(res));
145 
146  drainVerified_WITH_BOTH_LOCKS();
147  ready = true;
148  }
149  else
150  {
151  if (!m_verifying.replace(work.hash, move(res)))
152  cwarn << "BlockQueue missing our job: was there a GM?";
153  }
154  }
155  if (ready)
156  m_onReady();
157  }
158 }
159 
160 void BlockQueue::drainVerified_WITH_BOTH_LOCKS()
161 {
162  while (!m_verifying.isEmpty() && !m_verifying.next().blockData.empty())
163  {
164  VerifiedBlock block = m_verifying.dequeue();
165  if (m_knownBad.count(block.verified.info.parentHash()))
166  {
167  m_readySet.erase(block.verified.info.hash());
168  m_knownBad.insert(block.verified.info.hash());
169  }
170  else
171  m_verified.enqueue(move(block));
172  }
173 }
174 
175 ImportResult BlockQueue::import(bytesConstRef _block, bool _isOurs)
176 {
177  clog(BlockQueueTraceChannel) << std::this_thread::get_id();
178  // Check if we already know this block.
179  h256 h = BlockHeader::headerHashFromBlock(_block);
180 
181  clog(BlockQueueTraceChannel) << "Queuing block" << h << "for import...";
182 
183  UpgradableGuard l(m_lock);
184 
185  if (m_readySet.count(h) || m_drainingSet.count(h) || m_unknownSet.count(h) || m_knownBad.count(h))
186  {
187  // Already know about this one.
188  clog(BlockQueueTraceChannel) << "Already known.";
189  return ImportResult::AlreadyKnown;
190  }
191 
192  BlockHeader bi;
193  try
194  {
195  // TODO: quick verification of seal - will require BlockQueue to be templated on SealEngine
196  // VERIFY: populates from the block and checks the block is internally coherent.
197  bi = m_bc->verifyBlock(_block, m_onBad, ImportRequirements::PostGenesis).info;
198  }
199  catch (Exception const& _e)
200  {
201  cwarn << "Ignoring malformed block: " << diagnostic_information(_e);
202  return ImportResult::Malformed;
203  }
204 
205  clog(BlockQueueTraceChannel) << "Block" << h << "is" << bi.number() << "parent is" << bi.parentHash();
206 
207  // Check block doesn't already exist first!
208  if (m_bc->isKnown(h))
209  {
210  cblockq << "Already known in chain.";
211  return ImportResult::AlreadyInChain;
212  }
213 
214  UpgradeGuard ul(l);
216 
217  // Check it's not in the future
218  if (bi.timestamp() > utcTime() && !_isOurs)
219  {
220  m_future.insert(static_cast<time_t>(bi.timestamp()), h, _block.toBytes());
221  char buf[24];
222  time_t bit = static_cast<time_t>(bi.timestamp());
223  if (strftime(buf, 24, "%X", localtime(&bit)) == 0)
224  buf[0] = '\0'; // empty if case strftime fails
225  clog(BlockQueueTraceChannel) << "OK - queued for future [" << bi.timestamp() << "vs" << utcTime() << "] - will wait until" << buf;
226  m_difficulty += bi.difficulty();
227  bool unknown = !m_readySet.count(bi.parentHash()) && !m_drainingSet.count(bi.parentHash()) && !m_bc->isKnown(bi.parentHash());
228  return unknown ? ImportResult::FutureTimeUnknown : ImportResult::FutureTimeKnown;
229  }
230  else
231  {
232  // We now know it.
233  if (m_knownBad.count(bi.parentHash()))
234  {
235  m_knownBad.insert(bi.hash());
236  updateBad_WITH_LOCK(bi.hash());
237  // bad parent; this is bad too, note it as such
238  return ImportResult::BadChain;
239  }
240  else if (!m_readySet.count(bi.parentHash()) && !m_drainingSet.count(bi.parentHash()) && !m_bc->isKnown(bi.parentHash()))
241  {
242  // We don't know the parent (yet) - queue it up for later. It'll get resent to us if we find out about its ancestry later on.
243  clog(BlockQueueTraceChannel) << "OK - queued as unknown parent:" << bi.parentHash();
244  m_unknown.insert(bi.parentHash(), h, _block.toBytes());
245  m_unknownSet.insert(h);
246  m_difficulty += bi.difficulty();
247 
248  return ImportResult::UnknownParent;
249  }
250  else
251  {
252  // If valid, append to blocks.
253  clog(BlockQueueTraceChannel) << "OK - ready for chain insertion.";
254  DEV_GUARDED(m_verification)
255  m_unverified.enqueue(UnverifiedBlock { h, bi.parentHash(), _block.toBytes() });
256  m_moreToVerify.notify_one();
257  m_readySet.insert(h);
258  m_difficulty += bi.difficulty();
259 
260  noteReady_WITH_LOCK(h);
261 
262  return ImportResult::Success;
263  }
264  }
265 }
266 
267 void BlockQueue::updateBad_WITH_LOCK(h256 const& _bad)
268 {
270  DEV_GUARDED(m_verification)
271  {
272  collectUnknownBad_WITH_BOTH_LOCKS(_bad);
273  bool moreBad = true;
274  while (moreBad)
275  {
276  moreBad = false;
277  std::vector<VerifiedBlock> badVerified = m_verified.removeIf([this](VerifiedBlock const& _b)
278  {
279  return m_knownBad.count(_b.verified.info.parentHash()) || m_knownBad.count(_b.verified.info.hash());
280  });
281  for (auto& b: badVerified)
282  {
283  m_knownBad.insert(b.verified.info.hash());
284  m_readySet.erase(b.verified.info.hash());
285  collectUnknownBad_WITH_BOTH_LOCKS(b.verified.info.hash());
286  moreBad = true;
287  }
288 
289  std::vector<UnverifiedBlock> badUnverified = m_unverified.removeIf([this](UnverifiedBlock const& _b)
290  {
291  return m_knownBad.count(_b.parentHash) || m_knownBad.count(_b.hash);
292  });
293  for (auto& b: badUnverified)
294  {
295  m_knownBad.insert(b.hash);
296  m_readySet.erase(b.hash);
297  collectUnknownBad_WITH_BOTH_LOCKS(b.hash);
298  moreBad = true;
299  }
300 
301  std::vector<VerifiedBlock> badVerifying = m_verifying.removeIf([this](VerifiedBlock const& _b)
302  {
303  return m_knownBad.count(_b.verified.info.parentHash()) || m_knownBad.count(_b.verified.info.sha3Uncles());
304  });
305  for (auto& b: badVerifying)
306  {
307  h256 const& h = b.blockData.size() != 0 ? b.verified.info.hash() : b.verified.info.sha3Uncles();
308  m_knownBad.insert(h);
309  m_readySet.erase(h);
310  collectUnknownBad_WITH_BOTH_LOCKS(h);
311  moreBad = true;
312  }
313  }
314  }
315 }
316 
317 void BlockQueue::collectUnknownBad_WITH_BOTH_LOCKS(h256 const& _bad)
318 {
319  list<h256> badQueue(1, _bad);
320  while (!badQueue.empty())
321  {
322  vector<pair<h256, bytes>> const removed = m_unknown.removeByKeyEqual(badQueue.front());
323  badQueue.pop_front();
324  for (auto& newBad: removed)
325  {
326  m_unknownSet.erase(newBad.first);
327  m_knownBad.insert(newBad.first);
328  badQueue.push_back(newBad.first);
329  }
330  }
331 }
332 
333 bool BlockQueue::doneDrain(h256s const& _bad)
334 {
335  WriteGuard l(m_lock);
337  m_drainingSet.clear();
338  m_difficulty -= m_drainingDifficulty;
339  m_drainingDifficulty = 0;
340  if (_bad.size())
341  {
342  // at least one of them was bad.
343  m_knownBad += _bad;
344  for (h256 const& b: _bad)
345  updateBad_WITH_LOCK(b);
346  }
347  return !m_readySet.empty();
348 }
349 
350 void BlockQueue::tick()
351 {
352  vector<pair<h256, bytes>> todo;
353  {
354  UpgradableGuard l(m_lock);
355  if (m_future.isEmpty())
356  return;
357 
358  cblockq << "Checking past-future blocks...";
359 
360  time_t t = utcTime();
361  if (t < m_future.firstKey())
362  return;
363 
364  cblockq << "Past-future blocks ready.";
365 
366  {
367  UpgradeGuard l2(l);
369  todo = m_future.removeByKeyNotGreater(t);
370  }
371  }
372  cblockq << "Importing" << todo.size() << "past-future blocks.";
373 
374  for (auto const& b: todo)
375  import(&b.second);
376 }
377 
378 BlockQueueStatus BlockQueue::status() const
379 {
380  ReadGuard l(m_lock);
381  Guard l2(m_verification);
382  return BlockQueueStatus{ m_drainingSet.size(), m_verified.count(), m_verifying.count(), m_unverified.count(),
383  m_future.count(), m_unknown.count(), m_knownBad.size() };
384 }
385 
386 QueueStatus BlockQueue::blockStatus(h256 const& _h) const
387 {
388  ReadGuard l(m_lock);
389  return
390  m_readySet.count(_h) ?
391  QueueStatus::Ready :
392  m_drainingSet.count(_h) ?
393  QueueStatus::Importing :
394  m_unknownSet.count(_h) ?
395  QueueStatus::UnknownParent :
396  m_knownBad.count(_h) ?
397  QueueStatus::Bad :
398  QueueStatus::Unknown;
399 }
400 
401 bool BlockQueue::knownFull() const
402 {
403  Guard l(m_verification);
404  return knownSize() > c_maxKnownSize || knownCount() > c_maxKnownCount;
405 }
406 
407 std::size_t BlockQueue::knownSize() const
408 {
409  return m_verified.size() + m_unverified.size() + m_verifying.size();
410 }
411 
412 std::size_t BlockQueue::knownCount() const
413 {
414  return m_verified.count() + m_unverified.count() + m_verifying.count();
415 }
416 
417 bool BlockQueue::unknownFull() const
418 {
419  ReadGuard l(m_lock);
420  return unknownSize() > c_maxUnknownSize || unknownCount() > c_maxUnknownCount;
421 }
422 
423 std::size_t BlockQueue::unknownSize() const
424 {
425  return m_future.size() + m_unknown.size();
426 }
427 
428 std::size_t BlockQueue::unknownCount() const
429 {
430  return m_future.count() + m_unknown.count();
431 }
432 
433 void BlockQueue::drain(VerifiedBlocks& o_out, unsigned _max)
434 {
435  bool wasFull = false;
436  DEV_WRITE_GUARDED(m_lock)
437  {
439  wasFull = knownFull();
440  if (m_drainingSet.empty())
441  {
442  m_drainingDifficulty = 0;
443  DEV_GUARDED(m_verification)
444  o_out = m_verified.dequeueMultiple(min<unsigned>(_max, m_verified.count()));
445 
446  for (auto const& bs: o_out)
447  {
448  // TODO: @optimise use map<h256, bytes> rather than vector<bytes> & set<h256>.
449  auto h = bs.verified.info.hash();
450  m_drainingSet.insert(h);
451  m_drainingDifficulty += bs.verified.info.difficulty();
452  m_readySet.erase(h);
453  }
454  }
455  }
456  if (wasFull && !knownFull())
457  m_onRoomAvailable();
458 }
459 
460 bool BlockQueue::invariants() const
461 {
462  Guard l(m_verification);
463  if (m_readySet.size() != knownCount())
464  {
465  std::stringstream s;
466  s << "Failed BlockQueue invariant: m_readySet: " << m_readySet.size() << " m_verified: " << m_verified.count() << " m_unverified: " << m_unverified.count() << " m_verifying" << m_verifying.count();
467  BOOST_THROW_EXCEPTION(FailedInvariant() << errinfo_comment(s.str()));
468  }
469  return true;
470 }
471 
472 void BlockQueue::noteReady_WITH_LOCK(h256 const& _good)
473 {
475  list<h256> goodQueue(1, _good);
476  bool notify = false;
477  while (!goodQueue.empty())
478  {
479  h256 const parent = goodQueue.front();
480  vector<pair<h256, bytes>> const removed = m_unknown.removeByKeyEqual(parent);
481  goodQueue.pop_front();
482  for (auto& newReady: removed)
483  {
484  DEV_GUARDED(m_verification)
485  m_unverified.enqueue(UnverifiedBlock { newReady.first, parent, move(newReady.second) });
486  m_unknownSet.erase(newReady.first);
487  m_readySet.insert(newReady.first);
488  goodQueue.push_back(newReady.first);
489  notify = true;
490  }
491  }
492  if (notify)
493  m_moreToVerify.notify_all();
494 }
495 
496 void BlockQueue::retryAllUnknown()
497 {
498  WriteGuard l(m_lock);
500  while (!m_unknown.isEmpty())
501  {
502  h256 parent = m_unknown.firstKey();
503  vector<pair<h256, bytes>> removed = m_unknown.removeByKeyEqual(parent);
504  for (auto& newReady: removed)
505  {
506  DEV_GUARDED(m_verification)
507  m_unverified.enqueue(UnverifiedBlock{ newReady.first, parent, move(newReady.second) });
508  m_unknownSet.erase(newReady.first);
509  m_readySet.insert(newReady.first);
510  m_moreToVerify.notify_one();
511  }
512  }
513  m_moreToVerify.notify_all();
514 }
515 
516 std::ostream& dev::eth::operator<<(std::ostream& _out, BlockQueueStatus const& _bqs)
517 {
518  _out << "importing: " << _bqs.importing << endl;
519  _out << "verified: " << _bqs.verified << endl;
520  _out << "verifying: " << _bqs.verifying << endl;
521  _out << "unverified: " << _bqs.unverified << endl;
522  _out << "future: " << _bqs.future << endl;
523  _out << "unknown: " << _bqs.unknown << endl;
524  _out << "bad: " << _bqs.bad << endl;
525 
526  return _out;
527 }
528 
529 u256 BlockQueue::difficulty() const
530 {
531  UpgradableGuard l(m_lock);
532  return m_difficulty;
533 }
534 
535 bool BlockQueue::isActive() const
536 {
537  UpgradableGuard l(m_lock);
538  if (m_readySet.empty() && m_drainingSet.empty())
539  DEV_GUARDED(m_verification)
540  if (m_verified.isEmpty() && m_verifying.isEmpty() && m_unverified.isEmpty())
541  return false;
542  return true;
543 }
544 
545 std::ostream& dev::eth::operator<< (std::ostream& os, QueueStatus const& obj)
546 {
548  return os;
549 }
size_t const c_maxUnknownCount
Definition: BlockQueue.cpp:44
Adapted from code found on http://stackoverflow.com/questions/180947/base64-decode-snippet-in-c Origi...
Definition: Arith256.cpp:15
u256 const & number() const
Definition: BlockHeader.h:162
void swap(dev::eth::Watch &_a, dev::eth::Watch &_b)
Definition: Interface.h:284
h256 hash(IncludeSeal _i=WithSeal) const
Definition: BlockHeader.cpp:64
uint64_t utcTime()
Get the current time in seconds since the epoch in UTC.
Definition: Common.cpp:64
Encapsulation of a block header.
Definition: BlockHeader.h:95
std::ostream & operator<<(std::ostream &_out, BlockHeader const &_bi)
Definition: BlockHeader.h:194
#define h(i)
Definition: sha.cpp:736
boost::upgrade_to_unique_lock< boost::shared_mutex > UpgradeGuard
Definition: Guards.h:46
std::hash for asio::adress
Definition: Common.h:323
h256 const & sha3Uncles() const
Definition: BlockHeader.h:155
#define EthOrange
Definition: Terminal.h:124
#define cblockq
Definition: BlockQueue.h:46
boost::upgrade_lock< boost::shared_mutex > UpgradableGuard
Definition: Guards.h:45
VerifiedBlockRef verified
Verified block structures.
Definition: VerifiedBlock.h:68
Verified block info, combines block data and verified info/transactions.
Definition: VerifiedBlock.h:44
void setParentHash(h256 const &_v)
Definition: BlockHeader.h:140
h256 const & parentHash() const
Definition: BlockHeader.h:154
ImportResult
Definition: Common.h:97
void setSha3Uncles(h256 const &_v)
Definition: BlockHeader.h:141
#define DEV_GUARDED(MUTEX)
Simple block guard.
Definition: Guards.h:144
#define DEV_INVARIANT_CHECK
Scope guard for invariant check in a class derived from HasInvariants.
Definition: Common.h:257
Base class for all exceptions.
Definition: Exceptions.h:39
std::lock_guard< std::mutex > Guard
Definition: Guards.h:41
const char * name
Definition: rest.cpp:36
#define DEV_WRITE_GUARDED(MUTEX)
Definition: Guards.h:148
std::vector< unsigned char > toBytes() const
Definition: vector_ref.h:45
bytes blockData
Block data.
Definition: VerifiedBlock.h:69
#define cwarn
Definition: Log.h:304
boost::multiprecision::number< boost::multiprecision::cpp_int_backend< 256, 256, boost::multiprecision::unsigned_magnitude, boost::multiprecision::unchecked, void >> u256
Definition: Common.h:125
boost::shared_lock< boost::shared_mutex > ReadGuard
Definition: Guards.h:44
#define b(i, j)
boost::unique_lock< boost::shared_mutex > WriteGuard
Definition: Guards.h:47
u256 const & timestamp() const
Definition: BlockHeader.h:156
size_t const c_maxKnownSize
Definition: BlockQueue.cpp:43
size_t const c_maxKnownCount
Definition: BlockQueue.cpp:42
PlatformStyle::TableColorType type
Definition: rpcconsole.cpp:61
boost::error_info< struct tag_comment, std::string > errinfo_comment
Definition: Assertions.h:78
std::vector< VerifiedBlock > VerifiedBlocks
Definition: VerifiedBlock.h:76
#define clog(X)
Definition: Log.h:295
dev::WithExisting max(dev::WithExisting _a, dev::WithExisting _b)
Definition: Common.h:326
std::vector< h256 > h256s
Definition: FixedHash.h:345
BlockHeader info
Prepopulated block info.
Definition: VerifiedBlock.h:39
u256 const & difficulty() const
Definition: BlockHeader.h:166
UniValue stop(const JSONRPCRequest &jsonRequest)
Definition: server.cpp:237
size_t const c_maxUnknownSize
Definition: BlockQueue.cpp:45