Electroneum
block_queue.cpp
Go to the documentation of this file.
1 // Copyright (c) 2017-Present, Electroneum
2 // Copyright (c) 2017-2019, The Monero Project
3 //
4 // All rights reserved.
5 //
6 // Redistribution and use in source and binary forms, with or without modification, are
7 // permitted provided that the following conditions are met:
8 //
9 // 1. Redistributions of source code must retain the above copyright notice, this list of
10 // conditions and the following disclaimer.
11 //
12 // 2. Redistributions in binary form must reproduce the above copyright notice, this list
13 // of conditions and the following disclaimer in the documentation and/or other
14 // materials provided with the distribution.
15 //
16 // 3. Neither the name of the copyright holder nor the names of its contributors may be
17 // used to endorse or promote products derived from this software without specific
18 // prior written permission.
19 //
20 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
21 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
22 // MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
23 // THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
27 // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
28 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // Parts of this file are originally copyright (c) 2012-2013 The Cryptonote developers
31 
32 #include <vector>
33 #include <unordered_map>
34 #include <boost/uuid/nil_generator.hpp>
35 #include <boost/uuid/uuid_io.hpp>
36 #include "string_tools.h"
38 #include "common/pruning.h"
39 #include "block_queue.h"
40 
41 #undef ELECTRONEUM_DEFAULT_LOG_CATEGORY
42 #define ELECTRONEUM_DEFAULT_LOG_CATEGORY "cn.block_queue"
43 
44 namespace std {
45  static_assert(sizeof(size_t) <= sizeof(boost::uuids::uuid), "boost::uuids::uuid too small");
46  template<> struct hash<boost::uuids::uuid> {
47  std::size_t operator()(const boost::uuids::uuid &_v) const {
48  return reinterpret_cast<const std::size_t &>(_v);
49  }
50  };
51 }
52 
53 namespace cryptonote
54 {
55 
56 void block_queue::add_blocks(uint64_t height, std::vector<cryptonote::block_complete_entry> bcel, const boost::uuids::uuid &connection_id, float rate, size_t size)
57 {
58  boost::unique_lock<boost::recursive_mutex> lock(mutex);
59  std::vector<crypto::hash> hashes;
60  bool has_hashes = remove_span(height, &hashes);
61  blocks.insert(span(height, std::move(bcel), connection_id, rate, size));
62  if (has_hashes)
63  {
64  for (const crypto::hash &h: hashes)
65  {
66  requested_hashes.insert(h);
67  have_blocks.insert(h);
68  }
69  set_span_hashes(height, connection_id, hashes);
70  }
71 }
72 
73 void block_queue::add_blocks(uint64_t height, uint64_t nblocks, const boost::uuids::uuid &connection_id, boost::posix_time::ptime time)
74 {
75  CHECK_AND_ASSERT_THROW_MES(nblocks > 0, "Empty span");
76  boost::unique_lock<boost::recursive_mutex> lock(mutex);
77  blocks.insert(span(height, nblocks, connection_id, time));
78 }
79 
80 void block_queue::flush_spans(const boost::uuids::uuid &connection_id, bool all)
81 {
82  boost::unique_lock<boost::recursive_mutex> lock(mutex);
83  block_map::iterator i = blocks.begin();
84  while (i != blocks.end())
85  {
86  block_map::iterator j = i++;
87  if (j->connection_id == connection_id && (all || j->blocks.size() == 0))
88  {
89  erase_block(j);
90  }
91  }
92 }
93 
94 void block_queue::erase_block(block_map::iterator j)
95 {
96  CHECK_AND_ASSERT_THROW_MES(j != blocks.end(), "Invalid iterator");
97  for (const crypto::hash &h: j->hashes)
98  {
99  requested_hashes.erase(h);
100  have_blocks.erase(h);
101  }
102  blocks.erase(j);
103 }
104 
105 void block_queue::flush_stale_spans(const std::set<boost::uuids::uuid> &live_connections)
106 {
107  boost::unique_lock<boost::recursive_mutex> lock(mutex);
108  block_map::iterator i = blocks.begin();
109  while (i != blocks.end())
110  {
111  block_map::iterator j = i++;
112  if (j->blocks.empty() && live_connections.find(j->connection_id) == live_connections.end())
113  {
114  erase_block(j);
115  }
116  }
117 }
118 
119 bool block_queue::remove_span(uint64_t start_block_height, std::vector<crypto::hash> *hashes)
120 {
121  boost::unique_lock<boost::recursive_mutex> lock(mutex);
122  for (block_map::iterator i = blocks.begin(); i != blocks.end(); ++i)
123  {
124  if (i->start_block_height == start_block_height)
125  {
126  if (hashes)
127  *hashes = std::move(i->hashes);
128  erase_block(i);
129  return true;
130  }
131  }
132  return false;
133 }
134 
135 void block_queue::remove_spans(const boost::uuids::uuid &connection_id, uint64_t start_block_height)
136 {
137  boost::unique_lock<boost::recursive_mutex> lock(mutex);
138  for (block_map::iterator i = blocks.begin(); i != blocks.end(); )
139  {
140  block_map::iterator j = i++;
141  if (j->connection_id == connection_id && j->start_block_height <= start_block_height)
142  {
143  erase_block(j);
144  }
145  }
146 }
147 
149 {
150  boost::unique_lock<boost::recursive_mutex> lock(mutex);
151  uint64_t height = 0;
152  for (const auto &span: blocks)
153  {
154  const uint64_t h = span.start_block_height + span.nblocks - 1;
155  if (h > height)
156  height = h;
157  }
158  return height;
159 }
160 
162 {
163  boost::unique_lock<boost::recursive_mutex> lock(mutex);
164  if (blocks.empty())
165  return blockchain_height;
166  uint64_t last_needed_height = blockchain_height;
167  bool first = true;
168  for (const auto &span: blocks)
169  {
170  if (span.start_block_height + span.nblocks - 1 < blockchain_height)
171  continue;
172  if (span.start_block_height != last_needed_height || (first && span.blocks.empty()))
173  return last_needed_height;
174  last_needed_height = span.start_block_height + span.nblocks;
175  first = false;
176  }
177  return last_needed_height;
178 }
179 
180 void block_queue::print() const
181 {
182  boost::unique_lock<boost::recursive_mutex> lock(mutex);
183  MDEBUG("Block queue has " << blocks.size() << " spans");
184  for (const auto &span: blocks)
185  MDEBUG(" " << span.start_block_height << " - " << (span.start_block_height+span.nblocks-1) << " (" << span.nblocks << ") - " << (span.blocks.empty() ? "scheduled" : "filled ") << " " << span.connection_id << " (" << ((unsigned)(span.rate*10/1024.f))/10.f << " kB/s)");
186 }
187 
189 {
190  boost::unique_lock<boost::recursive_mutex> lock(mutex);
191  if (blocks.empty())
192  return "[]";
193  block_map::const_iterator i = blocks.begin();
194  std::string s = std::string("[");
195  uint64_t expected = blockchain_height;
196  while (i != blocks.end())
197  {
198  if (expected > i->start_block_height)
199  {
200  s += "<";
201  }
202  else
203  {
204  if (expected < i->start_block_height)
205  s += std::string(std::max((uint64_t)1, (i->start_block_height - expected) / (i->nblocks ? i->nblocks : 1)), '_');
206  s += i->blocks.empty() ? "." : i->start_block_height == blockchain_height ? "m" : "o";
207  expected = i->start_block_height + i->nblocks;
208  }
209  ++i;
210  }
211  s += "]";
212  return s;
213 }
214 
215 inline bool block_queue::requested_internal(const crypto::hash &hash) const
216 {
217  return requested_hashes.find(hash) != requested_hashes.end();
218 }
219 
221 {
222  boost::unique_lock<boost::recursive_mutex> lock(mutex);
223  return requested_internal(hash);
224 }
225 
227 {
228  boost::unique_lock<boost::recursive_mutex> lock(mutex);
229  return have_blocks.find(hash) != have_blocks.end();
230 }
231 
232 std::pair<uint64_t, uint64_t> block_queue::reserve_span(uint64_t first_block_height, uint64_t last_block_height, uint64_t max_blocks, const boost::uuids::uuid &connection_id, uint32_t pruning_seed, uint64_t blockchain_height, const std::vector<crypto::hash> &block_hashes, boost::posix_time::ptime time)
233 {
234  boost::unique_lock<boost::recursive_mutex> lock(mutex);
235 
236  MDEBUG("reserve_span: first_block_height " << first_block_height << ", last_block_height " << last_block_height
237  << ", max " << max_blocks << ", seed " << epee::string_tools::to_string_hex(pruning_seed) << ", blockchain_height " <<
238  blockchain_height << ", block hashes size " << block_hashes.size());
239  if (last_block_height < first_block_height || max_blocks == 0)
240  {
241  MDEBUG("reserve_span: early out: first_block_height " << first_block_height << ", last_block_height " << last_block_height << ", max_blocks " << max_blocks);
242  return std::make_pair(0, 0);
243  }
244  if (block_hashes.size() > last_block_height)
245  {
246  MDEBUG("reserve_span: more block hashes than fit within last_block_height: " << block_hashes.size() << " and " << last_block_height);
247  return std::make_pair(0, 0);
248  }
249 
250  // skip everything we've already requested
251  uint64_t span_start_height = last_block_height - block_hashes.size() + 1;
252  std::vector<crypto::hash>::const_iterator i = block_hashes.begin();
253  while (i != block_hashes.end() && requested_internal(*i))
254  {
255  ++i;
256  ++span_start_height;
257  }
258 
259  // if the peer's pruned for the starting block and its unpruned stripe comes next, start downloading from there
260  const uint32_t next_unpruned_height = tools::get_next_unpruned_block_height(span_start_height, blockchain_height, pruning_seed);
261  MDEBUG("reserve_span: next_unpruned_height " << next_unpruned_height << " from " << span_start_height << " and seed "
262  << epee::string_tools::to_string_hex(pruning_seed) << ", limit " << span_start_height + CRYPTONOTE_PRUNING_STRIPE_SIZE);
263  if (next_unpruned_height > span_start_height && next_unpruned_height < span_start_height + CRYPTONOTE_PRUNING_STRIPE_SIZE)
264  {
265  MDEBUG("We can download from next span: ideal height " << span_start_height << ", next unpruned height " << next_unpruned_height <<
266  "(+" << next_unpruned_height - span_start_height << "), current seed " << pruning_seed);
267  span_start_height = next_unpruned_height;
268  }
269  MDEBUG("span_start_height: " <<span_start_height);
270  const uint64_t block_hashes_start_height = last_block_height - block_hashes.size() + 1;
271  if (span_start_height >= block_hashes.size() + block_hashes_start_height)
272  {
273  MDEBUG("Out of hashes, cannot reserve");
274  return std::make_pair(0, 0);
275  }
276 
277  i = block_hashes.begin() + span_start_height - block_hashes_start_height;
278  while (i != block_hashes.end() && requested_internal(*i))
279  {
280  ++i;
281  ++span_start_height;
282  }
283 
284  uint64_t span_length = 0;
285  std::vector<crypto::hash> hashes;
286  while (i != block_hashes.end() && span_length < max_blocks && tools::has_unpruned_block(span_start_height + span_length, blockchain_height, pruning_seed))
287  {
288  hashes.push_back(*i);
289  ++i;
290  ++span_length;
291  }
292  if (span_length == 0)
293  {
294  MDEBUG("span_length 0, cannot reserve");
295  return std::make_pair(0, 0);
296  }
297  MDEBUG("Reserving span " << span_start_height << " - " << (span_start_height + span_length - 1) << " for " << connection_id);
298  add_blocks(span_start_height, span_length, connection_id, time);
299  set_span_hashes(span_start_height, connection_id, hashes);
300  return std::make_pair(span_start_height, span_length);
301 }
302 
303 std::pair<uint64_t, uint64_t> block_queue::get_next_span_if_scheduled(std::vector<crypto::hash> &hashes, boost::uuids::uuid &connection_id, boost::posix_time::ptime &time) const
304 {
305  boost::unique_lock<boost::recursive_mutex> lock(mutex);
306  if (blocks.empty())
307  return std::make_pair(0, 0);
308  block_map::const_iterator i = blocks.begin();
309  if (i == blocks.end())
310  return std::make_pair(0, 0);
311  if (!i->blocks.empty())
312  return std::make_pair(0, 0);
313  hashes = i->hashes;
314  connection_id = i->connection_id;
315  time = i->time;
316  return std::make_pair(i->start_block_height, i->nblocks);
317 }
318 
319 void block_queue::reset_next_span_time(boost::posix_time::ptime t)
320 {
321  boost::unique_lock<boost::recursive_mutex> lock(mutex);
322  CHECK_AND_ASSERT_THROW_MES(!blocks.empty(), "No next span to reset time");
323  block_map::iterator i = blocks.begin();
324  CHECK_AND_ASSERT_THROW_MES(i != blocks.end(), "No next span to reset time");
325  CHECK_AND_ASSERT_THROW_MES(i->blocks.empty(), "Next span is not empty");
326  (boost::posix_time::ptime&)i->time = t; // sod off, time doesn't influence sorting
327 }
328 
329 void block_queue::set_span_hashes(uint64_t start_height, const boost::uuids::uuid &connection_id, std::vector<crypto::hash> hashes)
330 {
331  boost::unique_lock<boost::recursive_mutex> lock(mutex);
332  for (block_map::iterator i = blocks.begin(); i != blocks.end(); ++i)
333  {
334  if (i->start_block_height == start_height && i->connection_id == connection_id)
335  {
336  span s = *i;
337  erase_block(i);
338  s.hashes = std::move(hashes);
339  for (const crypto::hash &h: s.hashes)
340  requested_hashes.insert(h);
341  blocks.insert(s);
342  return;
343  }
344  }
345 }
346 
347 bool block_queue::get_next_span(uint64_t &height, std::vector<cryptonote::block_complete_entry> &bcel, boost::uuids::uuid &connection_id, bool filled) const
348 {
349  boost::unique_lock<boost::recursive_mutex> lock(mutex);
350  if (blocks.empty())
351  return false;
352  block_map::const_iterator i = blocks.begin();
353  for (; i != blocks.end(); ++i)
354  {
355  if (!filled || !i->blocks.empty())
356  {
357  height = i->start_block_height;
358  bcel = i->blocks;
359  connection_id = i->connection_id;
360  return true;
361  }
362  }
363  return false;
364 }
365 
366 bool block_queue::has_next_span(const boost::uuids::uuid &connection_id, bool &filled, boost::posix_time::ptime &time) const
367 {
368  boost::unique_lock<boost::recursive_mutex> lock(mutex);
369  if (blocks.empty())
370  return false;
371  block_map::const_iterator i = blocks.begin();
372  if (i == blocks.end())
373  return false;
374  if (i->connection_id != connection_id)
375  return false;
376  filled = !i->blocks.empty();
377  time = i->time;
378  return true;
379 }
380 
381 bool block_queue::has_next_span(uint64_t height, bool &filled, boost::posix_time::ptime &time, boost::uuids::uuid &connection_id) const
382 {
383  boost::unique_lock<boost::recursive_mutex> lock(mutex);
384  if (blocks.empty())
385  return false;
386  block_map::const_iterator i = blocks.begin();
387  if (i == blocks.end())
388  return false;
389  if (i->start_block_height > height)
390  return false;
391  filled = !i->blocks.empty();
392  time = i->time;
393  connection_id = i->connection_id;
394  return true;
395 }
396 
398 {
399  boost::unique_lock<boost::recursive_mutex> lock(mutex);
400  size_t size = 0;
401  for (const auto &span: blocks)
402  size += span.size;
403  return size;
404 }
405 
407 {
408  boost::unique_lock<boost::recursive_mutex> lock(mutex);
409 
410  if (blocks.empty())
411  return 0;
412  block_map::const_iterator i = blocks.begin();
413  size_t size = 0;
414  while (i != blocks.end() && !i->blocks.empty())
415  {
416  ++i;
417  ++size;
418  }
419  return size;
420 }
421 
423 {
424  boost::unique_lock<boost::recursive_mutex> lock(mutex);
425  size_t size = 0;
426  for (const auto &span: blocks)
427  if (!span.blocks.empty())
428  ++size;
429  return size;
430 }
431 
433 {
434  boost::unique_lock<boost::recursive_mutex> lock(mutex);
435  crypto::hash hash = crypto::null_hash;
436  uint64_t highest_height = 0;
437  for (const auto &span: blocks)
438  {
439  if (span.connection_id != connection_id)
440  continue;
442  if (h > highest_height && span.hashes.size() == span.nblocks)
443  {
444  hash = span.hashes.back();
445  highest_height = h;
446  }
447  }
448  return hash;
449 }
450 
451 bool block_queue::has_spans(const boost::uuids::uuid &connection_id) const
452 {
453  for (const auto &span: blocks)
454  {
455  if (span.connection_id == connection_id)
456  return true;
457  }
458  return false;
459 }
460 
461 float block_queue::get_speed(const boost::uuids::uuid &connection_id) const
462 {
463  boost::unique_lock<boost::recursive_mutex> lock(mutex);
464  std::unordered_map<boost::uuids::uuid, float> speeds;
465  for (const auto &span: blocks)
466  {
467  if (span.blocks.empty())
468  continue;
469  // note that the average below does not average over the whole set, but over the
470  // previous pseudo average and the latest rate: this gives much more importance
471  // to the latest measurements, which is fine here
472  std::unordered_map<boost::uuids::uuid, float>::iterator i = speeds.find(span.connection_id);
473  if (i == speeds.end())
474  speeds.insert(std::make_pair(span.connection_id, span.rate));
475  else
476  i->second = (i->second + span.rate) / 2;
477  }
478  float conn_rate = -1, best_rate = 0;
479  for (const auto &i: speeds)
480  {
481  if (i.first == connection_id)
482  conn_rate = i.second;
483  if (i.second > best_rate)
484  best_rate = i.second;
485  }
486 
487  if (conn_rate <= 0)
488  return 1.0f; // not found, assume good speed
489  if (best_rate == 0)
490  return 1.0f; // everything dead ? Can't happen, but let's trap anyway
491 
492  const float speed = conn_rate / best_rate;
493  MTRACE(" Relative speed for " << connection_id << ": " << speed << " (" << conn_rate << "/" << best_rate);
494  return speed;
495 }
496 
497 float block_queue::get_download_rate(const boost::uuids::uuid &connection_id) const
498 {
499  boost::unique_lock<boost::recursive_mutex> lock(mutex);
500  float conn_rate = -1.f;
501  for (const auto &span: blocks)
502  {
503  if (span.blocks.empty())
504  continue;
505  if (span.connection_id != connection_id)
506  continue;
507  // note that the average below does not average over the whole set, but over the
508  // previous pseudo average and the latest rate: this gives much more importance
509  // to the latest measurements, which is fine here
510  if (conn_rate < 0.f)
511  conn_rate = span.rate;
512  else
513  conn_rate = (conn_rate + span.rate) / 2;
514  }
515 
516  if (conn_rate < 0)
517  conn_rate = 0.0f;
518  MTRACE("Download rate for " << connection_id << ": " << conn_rate << " b/s");
519  return conn_rate;
520 }
521 
522 bool block_queue::foreach(std::function<bool(const span&)> f) const
523 {
524  boost::unique_lock<boost::recursive_mutex> lock(mutex);
525  block_map::const_iterator i = blocks.begin();
526  while (i != blocks.end())
527  if (!f(*i++))
528  return false;
529  return true;
530 }
531 
532 }
size_t get_data_size() const
#define CHECK_AND_ASSERT_THROW_MES(expr, message)
Definition: misc_log_ex.h:173
uint64_t get_next_needed_height(uint64_t blockchain_height) const
std::pair< uint64_t, uint64_t > reserve_span(uint64_t first_block_height, uint64_t last_block_height, uint64_t max_blocks, const boost::uuids::uuid &connection_id, uint32_t pruning_seed, uint64_t blockchain_height, const std::vector< crypto::hash > &block_hashes, boost::posix_time::ptime time=boost::posix_time::microsec_clock::universal_time())
#define MTRACE(x)
Definition: misc_log_ex.h:77
boost::uuids::uuid uuid
::std::string string
Definition: gtest-port.h:1097
size_t get_num_filled_spans() const
bool foreach(std::function< bool(const span &)> f) const
uint64_t height
Definition: blockchain.cpp:91
void flush_spans(const boost::uuids::uuid &connection_id, bool all=false)
Definition: block_queue.cpp:80
STL namespace.
struct hash_func hashes[]
size_t get_num_filled_spans_prefix() const
void reset_next_span_time(boost::posix_time::ptime t=boost::posix_time::microsec_clock::universal_time())
float get_download_rate(const boost::uuids::uuid &connection_id) const
std::vector< crypto::hash > hashes
Definition: block_queue.h:54
#define MDEBUG(x)
Definition: misc_log_ex.h:76
void remove_spans(const boost::uuids::uuid &connection_id, uint64_t start_block_height)
Holds cryptonote related classes and helpers.
Definition: ban.cpp:40
#define CRYPTONOTE_PRUNING_STRIPE_SIZE
time_t time
Definition: blockchain.cpp:93
void flush_stale_spans(const std::set< boost::uuids::uuid > &live_connections)
std::string get_overview(uint64_t blockchain_height) const
void add_blocks(uint64_t height, std::vector< cryptonote::block_complete_entry > bcel, const boost::uuids::uuid &connection_id, float rate, size_t size)
Definition: block_queue.cpp:56
unsigned int uint32_t
Definition: stdint.h:126
uint64_t get_next_unpruned_block_height(uint64_t block_height, uint64_t blockchain_height, uint32_t pruning_seed)
Definition: pruning.cpp:69
bool have(const crypto::hash &hash) const
float get_speed(const boost::uuids::uuid &connection_id) const
unsigned __int64 uint64_t
Definition: stdint.h:136
std::pair< uint64_t, uint64_t > get_next_span_if_scheduled(std::vector< crypto::hash > &hashes, boost::uuids::uuid &connection_id, boost::posix_time::ptime &time) const
bool get_next_span(uint64_t &height, std::vector< cryptonote::block_complete_entry > &bcel, boost::uuids::uuid &connection_id, bool filled=true) const
bool remove_span(uint64_t start_block_height, std::vector< crypto::hash > *hashes=NULL)
bool has_spans(const boost::uuids::uuid &connection_id) const
std::string to_string_hex(uint32_t val)
Definition: string_tools.h:211
const T & move(const T &t)
Definition: gtest-port.h:1317
uint64_t get_max_block_height() const
bool has_unpruned_block(uint64_t block_height, uint64_t blockchain_height, uint32_t pruning_seed)
Definition: pruning.cpp:44
boost::uuids::uuid connection_id
Definition: block_queue.h:56
crypto::hash get_last_known_hash(const boost::uuids::uuid &connection_id) const
POD_CLASS hash
Definition: hash.h:50
bool has_next_span(const boost::uuids::uuid &connection_id, bool &filled, boost::posix_time::ptime &time) const
bool requested(const crypto::hash &hash) const
void set_span_hashes(uint64_t start_height, const boost::uuids::uuid &connection_id, std::vector< crypto::hash > hashes)
std::size_t operator()(const boost::uuids::uuid &_v) const
Definition: block_queue.cpp:47
std::vector< cryptonote::block_complete_entry > blocks
Definition: block_queue.h:55