Bitcoin ABC  0.26.3
P2P Digital Currency
blockfilterindex.cpp
Go to the documentation of this file.
1 // Copyright (c) 2018 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 <dbwrapper.h>
7 #include <node/blockstorage.h>
8 #include <primitives/blockhash.h>
9 #include <util/system.h>
10 
11 #include <map>
12 
14 
34 constexpr char DB_BLOCK_HASH = 's';
35 constexpr char DB_BLOCK_HEIGHT = 't';
36 constexpr char DB_FILTER_POS = 'P';
37 
38 // 16 MiB
39 constexpr unsigned int MAX_FLTR_FILE_SIZE = 0x1000000;
41 // 1 MiB
42 constexpr unsigned int FLTR_FILE_CHUNK_SIZE = 0x100000;
43 
51 constexpr size_t CF_HEADERS_CACHE_MAX_SZ{2000};
52 
53 namespace {
54 
55 struct DBVal {
56  uint256 hash;
57  uint256 header;
58  FlatFilePos pos;
59 
60  SERIALIZE_METHODS(DBVal, obj) { READWRITE(obj.hash, obj.header, obj.pos); }
61 };
62 
63 struct DBHeightKey {
64  int height;
65 
66  DBHeightKey() : height(0) {}
67  explicit DBHeightKey(int height_in) : height(height_in) {}
68 
69  template <typename Stream> void Serialize(Stream &s) const {
71  ser_writedata32be(s, height);
72  }
73 
74  template <typename Stream> void Unserialize(Stream &s) {
75  char prefix = ser_readdata8(s);
76  if (prefix != DB_BLOCK_HEIGHT) {
77  throw std::ios_base::failure(
78  "Invalid format for block filter index DB height key");
79  }
80  height = ser_readdata32be(s);
81  }
82 };
83 
84 struct DBHashKey {
85  BlockHash hash;
86 
87  explicit DBHashKey(const BlockHash &hash_in) : hash(hash_in) {}
88 
89  SERIALIZE_METHODS(DBHashKey, obj) {
90  char prefix = DB_BLOCK_HASH;
92  if (prefix != DB_BLOCK_HASH) {
93  throw std::ios_base::failure(
94  "Invalid format for block filter index DB hash key");
95  }
96 
97  READWRITE(obj.hash);
98  }
99 };
100 
101 }; // namespace
102 
103 static std::map<BlockFilterType, BlockFilterIndex> g_filter_indexes;
104 
106  size_t n_cache_size, bool f_memory,
107  bool f_wipe)
108  : m_filter_type(filter_type) {
109  const std::string &filter_name = BlockFilterTypeName(filter_type);
110  if (filter_name.empty()) {
111  throw std::invalid_argument("unknown filter_type");
112  }
113 
114  fs::path path =
115  gArgs.GetDataDirNet() / "indexes" / "blockfilter" / filter_name;
116  fs::create_directories(path);
117 
118  m_name = filter_name + " block filter index";
119  m_db = std::make_unique<BaseIndex::DB>(path / "db", n_cache_size, f_memory,
120  f_wipe);
121  m_filter_fileseq = std::make_unique<FlatFileSeq>(std::move(path), "fltr",
123 }
124 
126  if (!m_db->Read(DB_FILTER_POS, m_next_filter_pos)) {
127  // Check that the cause of the read failure is that the key does not
128  // exist. Any other errors indicate database corruption or a disk
129  // failure, and starting the index would cause further corruption.
130  if (m_db->Exists(DB_FILTER_POS)) {
131  return error(
132  "%s: Cannot read current %s state; index may be corrupted",
133  __func__, GetName());
134  }
135 
136  // If the DB_FILTER_POS is not set, then initialize to the first
137  // location.
140  }
141  return BaseIndex::Init();
142 }
143 
145  const FlatFilePos &pos = m_next_filter_pos;
146 
147  // Flush current filter file to disk.
149  if (file.IsNull()) {
150  return error("%s: Failed to open filter file %d", __func__, pos.nFile);
151  }
152  if (!FileCommit(file.Get())) {
153  return error("%s: Failed to commit filter file %d", __func__,
154  pos.nFile);
155  }
156 
157  batch.Write(DB_FILTER_POS, pos);
158  return BaseIndex::CommitInternal(batch);
159 }
160 
162  BlockFilter &filter) const {
163  CAutoFile filein(m_filter_fileseq->Open(pos, true), SER_DISK,
165  if (filein.IsNull()) {
166  return false;
167  }
168 
169  BlockHash block_hash;
170  std::vector<uint8_t> encoded_filter;
171  try {
172  filein >> block_hash >> encoded_filter;
173  filter =
174  BlockFilter(GetFilterType(), block_hash, std::move(encoded_filter));
175  } catch (const std::exception &e) {
176  return error("%s: Failed to deserialize block filter from disk: %s",
177  __func__, e.what());
178  }
179 
180  return true;
181 }
182 
184  const BlockFilter &filter) {
185  assert(filter.GetFilterType() == GetFilterType());
186 
187  size_t data_size =
190 
191  // If writing the filter would overflow the file, flush and move to the next
192  // one.
193  if (pos.nPos + data_size > MAX_FLTR_FILE_SIZE) {
194  CAutoFile last_file(m_filter_fileseq->Open(pos), SER_DISK,
196  if (last_file.IsNull()) {
197  LogPrintf("%s: Failed to open filter file %d\n", __func__,
198  pos.nFile);
199  return 0;
200  }
201  if (!TruncateFile(last_file.Get(), pos.nPos)) {
202  LogPrintf("%s: Failed to truncate filter file %d\n", __func__,
203  pos.nFile);
204  return 0;
205  }
206  if (!FileCommit(last_file.Get())) {
207  LogPrintf("%s: Failed to commit filter file %d\n", __func__,
208  pos.nFile);
209  return 0;
210  }
211 
212  pos.nFile++;
213  pos.nPos = 0;
214  }
215 
216  // Pre-allocate sufficient space for filter data.
217  bool out_of_space;
218  m_filter_fileseq->Allocate(pos, data_size, out_of_space);
219  if (out_of_space) {
220  LogPrintf("%s: out of disk space\n", __func__);
221  return 0;
222  }
223 
224  CAutoFile fileout(m_filter_fileseq->Open(pos), SER_DISK, CLIENT_VERSION);
225  if (fileout.IsNull()) {
226  LogPrintf("%s: Failed to open filter file %d\n", __func__, pos.nFile);
227  return 0;
228  }
229 
230  fileout << filter.GetBlockHash() << filter.GetEncodedFilter();
231  return data_size;
232 }
233 
235  const CBlockIndex *pindex) {
236  CBlockUndo block_undo;
237  uint256 prev_header;
238 
239  if (pindex->nHeight > 0) {
240  if (!UndoReadFromDisk(block_undo, pindex)) {
241  return false;
242  }
243 
244  std::pair<BlockHash, DBVal> read_out;
245  if (!m_db->Read(DBHeightKey(pindex->nHeight - 1), read_out)) {
246  return false;
247  }
248 
249  BlockHash expected_block_hash = pindex->pprev->GetBlockHash();
250  if (read_out.first != expected_block_hash) {
251  return error("%s: previous block header belongs to unexpected "
252  "block %s; expected %s",
253  __func__, read_out.first.ToString(),
254  expected_block_hash.ToString());
255  }
256 
257  prev_header = read_out.second.header;
258  }
259 
260  BlockFilter filter(m_filter_type, block, block_undo);
261 
262  size_t bytes_written = WriteFilterToDisk(m_next_filter_pos, filter);
263  if (bytes_written == 0) {
264  return false;
265  }
266 
267  std::pair<BlockHash, DBVal> value;
268  value.first = pindex->GetBlockHash();
269  value.second.hash = filter.GetHash();
270  value.second.header = filter.ComputeHeader(prev_header);
271  value.second.pos = m_next_filter_pos;
272 
273  if (!m_db->Write(DBHeightKey(pindex->nHeight), value)) {
274  return false;
275  }
276 
277  m_next_filter_pos.nPos += bytes_written;
278  return true;
279 }
280 
282  const std::string &index_name,
283  int start_height, int stop_height) {
284  DBHeightKey key(start_height);
285  db_it.Seek(key);
286 
287  for (int height = start_height; height <= stop_height; ++height) {
288  if (!db_it.GetKey(key) || key.height != height) {
289  return error("%s: unexpected key in %s: expected (%c, %d)",
290  __func__, index_name, DB_BLOCK_HEIGHT, height);
291  }
292 
293  std::pair<BlockHash, DBVal> value;
294  if (!db_it.GetValue(value)) {
295  return error("%s: unable to read value in %s at key (%c, %d)",
296  __func__, index_name, DB_BLOCK_HEIGHT, height);
297  }
298 
299  batch.Write(DBHashKey(value.first), std::move(value.second));
300 
301  db_it.Next();
302  }
303  return true;
304 }
305 
306 bool BlockFilterIndex::Rewind(const CBlockIndex *current_tip,
307  const CBlockIndex *new_tip) {
308  assert(current_tip->GetAncestor(new_tip->nHeight) == new_tip);
309 
310  CDBBatch batch(*m_db);
311  std::unique_ptr<CDBIterator> db_it(m_db->NewIterator());
312 
313  // During a reorg, we need to copy all filters for blocks that are getting
314  // disconnected from the height index to the hash index so we can still find
315  // them when the height index entries are overwritten.
316  if (!CopyHeightIndexToHashIndex(*db_it, batch, m_name, new_tip->nHeight,
317  current_tip->nHeight)) {
318  return false;
319  }
320 
321  // The latest filter position gets written in Commit by the call to the
322  // BaseIndex::Rewind. But since this creates new references to the filter,
323  // the position should get updated here atomically as well in case Commit
324  // fails.
326  if (!m_db->WriteBatch(batch)) {
327  return false;
328  }
329 
330  return BaseIndex::Rewind(current_tip, new_tip);
331 }
332 
333 static bool LookupOne(const CDBWrapper &db, const CBlockIndex *block_index,
334  DBVal &result) {
335  // First check if the result is stored under the height index and the value
336  // there matches the block hash. This should be the case if the block is on
337  // the active chain.
338  std::pair<BlockHash, DBVal> read_out;
339  if (!db.Read(DBHeightKey(block_index->nHeight), read_out)) {
340  return false;
341  }
342  if (read_out.first == block_index->GetBlockHash()) {
343  result = std::move(read_out.second);
344  return true;
345  }
346 
347  // If value at the height index corresponds to an different block, the
348  // result will be stored in the hash index.
349  return db.Read(DBHashKey(block_index->GetBlockHash()), result);
350 }
351 
352 static bool LookupRange(CDBWrapper &db, const std::string &index_name,
353  int start_height, const CBlockIndex *stop_index,
354  std::vector<DBVal> &results) {
355  if (start_height < 0) {
356  return error("%s: start height (%d) is negative", __func__,
357  start_height);
358  }
359  if (start_height > stop_index->nHeight) {
360  return error("%s: start height (%d) is greater than stop height (%d)",
361  __func__, start_height, stop_index->nHeight);
362  }
363 
364  size_t results_size =
365  static_cast<size_t>(stop_index->nHeight - start_height + 1);
366  std::vector<std::pair<BlockHash, DBVal>> values(results_size);
367 
368  DBHeightKey key(start_height);
369  std::unique_ptr<CDBIterator> db_it(db.NewIterator());
370  db_it->Seek(DBHeightKey(start_height));
371  for (int height = start_height; height <= stop_index->nHeight; ++height) {
372  if (!db_it->Valid() || !db_it->GetKey(key) || key.height != height) {
373  return false;
374  }
375 
376  size_t i = static_cast<size_t>(height - start_height);
377  if (!db_it->GetValue(values[i])) {
378  return error("%s: unable to read value in %s at key (%c, %d)",
379  __func__, index_name, DB_BLOCK_HEIGHT, height);
380  }
381 
382  db_it->Next();
383  }
384 
385  results.resize(results_size);
386 
387  // Iterate backwards through block indexes collecting results in order to
388  // access the block hash of each entry in case we need to look it up in the
389  // hash index.
390  for (const CBlockIndex *block_index = stop_index;
391  block_index && block_index->nHeight >= start_height;
392  block_index = block_index->pprev) {
393  BlockHash block_hash = block_index->GetBlockHash();
394 
395  size_t i = static_cast<size_t>(block_index->nHeight - start_height);
396  if (block_hash == values[i].first) {
397  results[i] = std::move(values[i].second);
398  continue;
399  }
400 
401  if (!db.Read(DBHashKey(block_hash), results[i])) {
402  return error("%s: unable to read value in %s at key (%c, %s)",
403  __func__, index_name, DB_BLOCK_HASH,
404  block_hash.ToString());
405  }
406  }
407 
408  return true;
409 }
410 
412  BlockFilter &filter_out) const {
413  DBVal entry;
414  if (!LookupOne(*m_db, block_index, entry)) {
415  return false;
416  }
417 
418  return ReadFilterFromDisk(entry.pos, filter_out);
419 }
420 
422  uint256 &header_out) {
424 
425  bool is_checkpoint{block_index->nHeight % CFCHECKPT_INTERVAL == 0};
426 
427  if (is_checkpoint) {
428  // Try to find the block in the headers cache if this is a checkpoint
429  // height.
430  auto header = m_headers_cache.find(block_index->GetBlockHash());
431  if (header != m_headers_cache.end()) {
432  header_out = header->second;
433  return true;
434  }
435  }
436 
437  DBVal entry;
438  if (!LookupOne(*m_db, block_index, entry)) {
439  return false;
440  }
441 
442  if (is_checkpoint && m_headers_cache.size() < CF_HEADERS_CACHE_MAX_SZ) {
443  // Add to the headers cache if this is a checkpoint height.
444  m_headers_cache.emplace(block_index->GetBlockHash(), entry.header);
445  }
446 
447  header_out = entry.header;
448  return true;
449 }
450 
452  int start_height, const CBlockIndex *stop_index,
453  std::vector<BlockFilter> &filters_out) const {
454  std::vector<DBVal> entries;
455  if (!LookupRange(*m_db, m_name, start_height, stop_index, entries)) {
456  return false;
457  }
458 
459  filters_out.resize(entries.size());
460  auto filter_pos_it = filters_out.begin();
461  for (const auto &entry : entries) {
462  if (!ReadFilterFromDisk(entry.pos, *filter_pos_it)) {
463  return false;
464  }
465  ++filter_pos_it;
466  }
467 
468  return true;
469 }
470 
472  int start_height, const CBlockIndex *stop_index,
473  std::vector<uint256> &hashes_out) const
474 
475 {
476  std::vector<DBVal> entries;
477  if (!LookupRange(*m_db, m_name, start_height, stop_index, entries)) {
478  return false;
479  }
480 
481  hashes_out.clear();
482  hashes_out.reserve(entries.size());
483  for (const auto &entry : entries) {
484  hashes_out.push_back(entry.hash);
485  }
486  return true;
487 }
488 
490  auto it = g_filter_indexes.find(filter_type);
491  return it != g_filter_indexes.end() ? &it->second : nullptr;
492 }
493 
494 void ForEachBlockFilterIndex(std::function<void(BlockFilterIndex &)> fn) {
495  for (auto &entry : g_filter_indexes) {
496  fn(entry.second);
497  }
498 }
499 
500 bool InitBlockFilterIndex(BlockFilterType filter_type, size_t n_cache_size,
501  bool f_memory, bool f_wipe) {
502  auto result = g_filter_indexes.emplace(
503  std::piecewise_construct, std::forward_as_tuple(filter_type),
504  std::forward_as_tuple(filter_type, n_cache_size, f_memory, f_wipe));
505  return result.second;
506 }
507 
509  return g_filter_indexes.erase(filter_type);
510 }
511 
513  g_filter_indexes.clear();
514 }
const std::string & BlockFilterTypeName(BlockFilterType filter_type)
Get the human-readable name for a filter type.
BlockFilterType
Definition: blockfilter.h:88
constexpr char DB_BLOCK_HASH
The index database stores three items for each block: the disk location of the encoded filter,...
constexpr unsigned int FLTR_FILE_CHUNK_SIZE
The pre-allocation chunk size for fltr?????.dat files.
bool DestroyBlockFilterIndex(BlockFilterType filter_type)
Destroy the block filter index with the given type.
void DestroyAllBlockFilterIndexes()
Destroy all open block filter indexes.
constexpr char DB_BLOCK_HEIGHT
static bool CopyHeightIndexToHashIndex(CDBIterator &db_it, CDBBatch &batch, const std::string &index_name, int start_height, int stop_height)
static bool LookupOne(const CDBWrapper &db, const CBlockIndex *block_index, DBVal &result)
BlockFilterIndex * GetBlockFilterIndex(BlockFilterType filter_type)
Get a block filter index by type.
constexpr unsigned int MAX_FLTR_FILE_SIZE
void ForEachBlockFilterIndex(std::function< void(BlockFilterIndex &)> fn)
Iterate over all running block filter indexes, invoking fn on each.
constexpr size_t CF_HEADERS_CACHE_MAX_SZ
Maximum size of the cfheaders cache.
static bool LookupRange(CDBWrapper &db, const std::string &index_name, int start_height, const CBlockIndex *stop_index, std::vector< DBVal > &results)
constexpr char DB_FILTER_POS
bool InitBlockFilterIndex(BlockFilterType filter_type, size_t n_cache_size, bool f_memory, bool f_wipe)
Initialize a block filter index for the given type if one does not already exist.
static std::map< BlockFilterType, BlockFilterIndex > g_filter_indexes
static constexpr int CFCHECKPT_INTERVAL
Interval between compact filter checkpoints.
const fs::path & GetDataDirNet() const
Get data directory path with appended network identifier.
Definition: system.h:260
virtual bool Init()
Initialize internal state from the database and block index.
Definition: base.cpp:58
virtual bool CommitInternal(CDBBatch &batch)
Virtual method called internally by Commit that can be overridden to atomically commit more index sta...
Definition: base.cpp:218
virtual bool Rewind(const CBlockIndex *current_tip, const CBlockIndex *new_tip)
Rewind index to an earlier chain tip during a chain reorg.
Definition: base.cpp:230
Complete block filter struct as defined in BIP 157.
Definition: blockfilter.h:111
const BlockHash & GetBlockHash() const
Definition: blockfilter.h:131
uint256 ComputeHeader(const uint256 &prev_header) const
Compute the filter header given the previous one.
BlockFilterType GetFilterType() const
Definition: blockfilter.h:130
const std::vector< uint8_t > & GetEncodedFilter() const
Definition: blockfilter.h:134
uint256 GetHash() const
Compute the filter hash.
BlockFilterIndex is used to store and retrieve block filters, hashes, and headers for a range of bloc...
std::unique_ptr< BaseIndex::DB > m_db
bool CommitInternal(CDBBatch &batch) override
Virtual method called internally by Commit that can be overridden to atomically commit more index sta...
bool Rewind(const CBlockIndex *current_tip, const CBlockIndex *new_tip) override
Rewind index to an earlier chain tip during a chain reorg.
bool ReadFilterFromDisk(const FlatFilePos &pos, BlockFilter &filter) const
bool LookupFilterRange(int start_height, const CBlockIndex *stop_index, std::vector< BlockFilter > &filters_out) const
Get a range of filters between two heights on a chain.
BlockFilterType GetFilterType() const
bool LookupFilterHeader(const CBlockIndex *block_index, uint256 &header_out)
Get a single filter header by block.
BlockFilterType m_filter_type
bool Init() override
Initialize internal state from the database and block index.
bool WriteBlock(const CBlock &block, const CBlockIndex *pindex) override
Write update index entries for a newly connected block.
BlockFilterIndex(BlockFilterType filter_type, size_t n_cache_size, bool f_memory=false, bool f_wipe=false)
Constructs the index, which becomes available to be queried.
std::unique_ptr< FlatFileSeq > m_filter_fileseq
bool LookupFilter(const CBlockIndex *block_index, BlockFilter &filter_out) const
Get a single filter by block.
bool LookupFilterHashRange(int start_height, const CBlockIndex *stop_index, std::vector< uint256 > &hashes_out) const
Get a range of filter hashes between two heights on a chain.
const char * GetName() const override
Get the name of the index for display in logs.
size_t WriteFilterToDisk(FlatFilePos &pos, const BlockFilter &filter)
std::string m_name
FlatFilePos m_next_filter_pos
Non-refcounted RAII wrapper for FILE*.
Definition: streams.h:581
FILE * Get() const
Get wrapped FILE* without transfer of ownership.
Definition: streams.h:624
bool IsNull() const
Return true if the wrapped FILE* is nullptr, false otherwise.
Definition: streams.h:627
Definition: block.h:55
The block chain is a tree shaped structure starting with the genesis block at the root,...
Definition: blockindex.h:26
CBlockIndex * pprev
pointer to the index of the predecessor of this block
Definition: blockindex.h:33
CBlockIndex * GetAncestor(int height)
Efficiently find an ancestor of this block.
Definition: blockindex.cpp:71
BlockHash GetBlockHash() const
Definition: blockindex.h:147
int nHeight
height of the entry in the chain. The genesis block has height 0
Definition: blockindex.h:39
Undo information for a CBlock.
Definition: undo.h:73
Batch of changes queued to be written to a CDBWrapper.
Definition: dbwrapper.h:48
void Write(const K &key, const V &value)
Definition: dbwrapper.h:73
bool GetValue(V &value)
Definition: dbwrapper.h:155
bool GetKey(K &key)
Definition: dbwrapper.h:143
void Seek(const K &key)
Definition: dbwrapper.h:133
void Next()
Definition: dbwrapper.cpp:252
std::string ToString() const
Definition: uint256.h:78
Path class wrapper to prepare application code for transition from boost::filesystem library to std::...
Definition: fs.h:33
256-bit opaque blob.
Definition: uint256.h:127
static constexpr int CLIENT_VERSION
bitcoind-res.rc includes this file, but it cannot cope with real c++ code.
Definition: clientversion.h:38
#define LogPrintf(...)
Definition: logging.h:204
bool UndoReadFromDisk(CBlockUndo &blockundo, const CBlockIndex *pindex)
const char * prefix
Definition: rest.cpp:821
CAddrDb db
Definition: main.cpp:34
uint8_t ser_readdata8(Stream &s)
Definition: serialize.h:98
void ser_writedata32be(Stream &s, uint32_t obj)
Definition: serialize.h:89
#define SERIALIZE_METHODS(cls, obj)
Implement the Serialize and Unserialize methods by delegating to a single templated static method tha...
Definition: serialize.h:227
void Serialize(Stream &s, char a)
Definition: serialize.h:242
@ SER_DISK
Definition: serialize.h:167
void Unserialize(Stream &s, char &a)
Definition: serialize.h:294
void ser_writedata8(Stream &s, uint8_t obj)
Lowest-level serialization and conversion.
Definition: serialize.h:70
size_t GetSerializeSize(const T &t, int nVersion=0)
Definition: serialize.h:1259
uint32_t ser_readdata32be(Stream &s)
Definition: serialize.h:118
#define READWRITE(...)
Definition: serialize.h:180
A BlockHash is a unqiue identifier for a block.
Definition: blockhash.h:13
int nFile
Definition: flatfile.h:15
unsigned int nPos
Definition: flatfile.h:16
#define LOCK(cs)
Definition: sync.h:243
ArgsManager gArgs
Definition: system.cpp:77
bool TruncateFile(FILE *file, unsigned int length)
Definition: system.cpp:1189
bool FileCommit(FILE *file)
Definition: system.cpp:1153
bool error(const char *fmt, const Args &...args)
Definition: system.h:46
assert(!tx.IsCoinBase())