Bitcoin ABC  0.28.12
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;
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.
148  AutoFile file{m_filter_fileseq->Open(pos)};
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  AutoFile filein{m_filter_fileseq->Open(pos, true)};
164  if (filein.IsNull()) {
165  return false;
166  }
167 
168  BlockHash block_hash;
169  std::vector<uint8_t> encoded_filter;
170  try {
171  filein >> block_hash >> encoded_filter;
172  filter =
173  BlockFilter(GetFilterType(), block_hash, std::move(encoded_filter));
174  } catch (const std::exception &e) {
175  return error("%s: Failed to deserialize block filter from disk: %s",
176  __func__, e.what());
177  }
178 
179  return true;
180 }
181 
183  const BlockFilter &filter) {
184  assert(filter.GetFilterType() == GetFilterType());
185 
186  size_t data_size =
189 
190  // If writing the filter would overflow the file, flush and move to the next
191  // one.
192  if (pos.nPos + data_size > MAX_FLTR_FILE_SIZE) {
193  AutoFile last_file{m_filter_fileseq->Open(pos)};
194  if (last_file.IsNull()) {
195  LogPrintf("%s: Failed to open filter file %d\n", __func__,
196  pos.nFile);
197  return 0;
198  }
199  if (!TruncateFile(last_file.Get(), pos.nPos)) {
200  LogPrintf("%s: Failed to truncate filter file %d\n", __func__,
201  pos.nFile);
202  return 0;
203  }
204  if (!FileCommit(last_file.Get())) {
205  LogPrintf("%s: Failed to commit filter file %d\n", __func__,
206  pos.nFile);
207  return 0;
208  }
209 
210  pos.nFile++;
211  pos.nPos = 0;
212  }
213 
214  // Pre-allocate sufficient space for filter data.
215  bool out_of_space;
216  m_filter_fileseq->Allocate(pos, data_size, out_of_space);
217  if (out_of_space) {
218  LogPrintf("%s: out of disk space\n", __func__);
219  return 0;
220  }
221 
222  AutoFile fileout{m_filter_fileseq->Open(pos)};
223  if (fileout.IsNull()) {
224  LogPrintf("%s: Failed to open filter file %d\n", __func__, pos.nFile);
225  return 0;
226  }
227 
228  fileout << filter.GetBlockHash() << filter.GetEncodedFilter();
229  return data_size;
230 }
231 
233  const CBlockIndex *pindex) {
234  CBlockUndo block_undo;
235  uint256 prev_header;
236 
237  if (pindex->nHeight > 0) {
238  if (!UndoReadFromDisk(block_undo, pindex)) {
239  return false;
240  }
241 
242  std::pair<BlockHash, DBVal> read_out;
243  if (!m_db->Read(DBHeightKey(pindex->nHeight - 1), read_out)) {
244  return false;
245  }
246 
247  BlockHash expected_block_hash = pindex->pprev->GetBlockHash();
248  if (read_out.first != expected_block_hash) {
249  return error("%s: previous block header belongs to unexpected "
250  "block %s; expected %s",
251  __func__, read_out.first.ToString(),
252  expected_block_hash.ToString());
253  }
254 
255  prev_header = read_out.second.header;
256  }
257 
258  BlockFilter filter(m_filter_type, block, block_undo);
259 
260  size_t bytes_written = WriteFilterToDisk(m_next_filter_pos, filter);
261  if (bytes_written == 0) {
262  return false;
263  }
264 
265  std::pair<BlockHash, DBVal> value;
266  value.first = pindex->GetBlockHash();
267  value.second.hash = filter.GetHash();
268  value.second.header = filter.ComputeHeader(prev_header);
269  value.second.pos = m_next_filter_pos;
270 
271  if (!m_db->Write(DBHeightKey(pindex->nHeight), value)) {
272  return false;
273  }
274 
275  m_next_filter_pos.nPos += bytes_written;
276  return true;
277 }
278 
280  const std::string &index_name,
281  int start_height, int stop_height) {
282  DBHeightKey key(start_height);
283  db_it.Seek(key);
284 
285  for (int height = start_height; height <= stop_height; ++height) {
286  if (!db_it.GetKey(key) || key.height != height) {
287  return error("%s: unexpected key in %s: expected (%c, %d)",
288  __func__, index_name, DB_BLOCK_HEIGHT, height);
289  }
290 
291  std::pair<BlockHash, DBVal> value;
292  if (!db_it.GetValue(value)) {
293  return error("%s: unable to read value in %s at key (%c, %d)",
294  __func__, index_name, DB_BLOCK_HEIGHT, height);
295  }
296 
297  batch.Write(DBHashKey(value.first), std::move(value.second));
298 
299  db_it.Next();
300  }
301  return true;
302 }
303 
304 bool BlockFilterIndex::Rewind(const CBlockIndex *current_tip,
305  const CBlockIndex *new_tip) {
306  assert(current_tip->GetAncestor(new_tip->nHeight) == new_tip);
307 
308  CDBBatch batch(*m_db);
309  std::unique_ptr<CDBIterator> db_it(m_db->NewIterator());
310 
311  // During a reorg, we need to copy all filters for blocks that are getting
312  // disconnected from the height index to the hash index so we can still find
313  // them when the height index entries are overwritten.
314  if (!CopyHeightIndexToHashIndex(*db_it, batch, m_name, new_tip->nHeight,
315  current_tip->nHeight)) {
316  return false;
317  }
318 
319  // The latest filter position gets written in Commit by the call to the
320  // BaseIndex::Rewind. But since this creates new references to the filter,
321  // the position should get updated here atomically as well in case Commit
322  // fails.
324  if (!m_db->WriteBatch(batch)) {
325  return false;
326  }
327 
328  return BaseIndex::Rewind(current_tip, new_tip);
329 }
330 
331 static bool LookupOne(const CDBWrapper &db, const CBlockIndex *block_index,
332  DBVal &result) {
333  // First check if the result is stored under the height index and the value
334  // there matches the block hash. This should be the case if the block is on
335  // the active chain.
336  std::pair<BlockHash, DBVal> read_out;
337  if (!db.Read(DBHeightKey(block_index->nHeight), read_out)) {
338  return false;
339  }
340  if (read_out.first == block_index->GetBlockHash()) {
341  result = std::move(read_out.second);
342  return true;
343  }
344 
345  // If value at the height index corresponds to an different block, the
346  // result will be stored in the hash index.
347  return db.Read(DBHashKey(block_index->GetBlockHash()), result);
348 }
349 
350 static bool LookupRange(CDBWrapper &db, const std::string &index_name,
351  int start_height, const CBlockIndex *stop_index,
352  std::vector<DBVal> &results) {
353  if (start_height < 0) {
354  return error("%s: start height (%d) is negative", __func__,
355  start_height);
356  }
357  if (start_height > stop_index->nHeight) {
358  return error("%s: start height (%d) is greater than stop height (%d)",
359  __func__, start_height, stop_index->nHeight);
360  }
361 
362  size_t results_size =
363  static_cast<size_t>(stop_index->nHeight - start_height + 1);
364  std::vector<std::pair<BlockHash, DBVal>> values(results_size);
365 
366  DBHeightKey key(start_height);
367  std::unique_ptr<CDBIterator> db_it(db.NewIterator());
368  db_it->Seek(DBHeightKey(start_height));
369  for (int height = start_height; height <= stop_index->nHeight; ++height) {
370  if (!db_it->Valid() || !db_it->GetKey(key) || key.height != height) {
371  return false;
372  }
373 
374  size_t i = static_cast<size_t>(height - start_height);
375  if (!db_it->GetValue(values[i])) {
376  return error("%s: unable to read value in %s at key (%c, %d)",
377  __func__, index_name, DB_BLOCK_HEIGHT, height);
378  }
379 
380  db_it->Next();
381  }
382 
383  results.resize(results_size);
384 
385  // Iterate backwards through block indexes collecting results in order to
386  // access the block hash of each entry in case we need to look it up in the
387  // hash index.
388  for (const CBlockIndex *block_index = stop_index;
389  block_index && block_index->nHeight >= start_height;
390  block_index = block_index->pprev) {
391  BlockHash block_hash = block_index->GetBlockHash();
392 
393  size_t i = static_cast<size_t>(block_index->nHeight - start_height);
394  if (block_hash == values[i].first) {
395  results[i] = std::move(values[i].second);
396  continue;
397  }
398 
399  if (!db.Read(DBHashKey(block_hash), results[i])) {
400  return error("%s: unable to read value in %s at key (%c, %s)",
401  __func__, index_name, DB_BLOCK_HASH,
402  block_hash.ToString());
403  }
404  }
405 
406  return true;
407 }
408 
410  BlockFilter &filter_out) const {
411  DBVal entry;
412  if (!LookupOne(*m_db, block_index, entry)) {
413  return false;
414  }
415 
416  return ReadFilterFromDisk(entry.pos, filter_out);
417 }
418 
420  uint256 &header_out) {
422 
423  bool is_checkpoint{block_index->nHeight % CFCHECKPT_INTERVAL == 0};
424 
425  if (is_checkpoint) {
426  // Try to find the block in the headers cache if this is a checkpoint
427  // height.
428  auto header = m_headers_cache.find(block_index->GetBlockHash());
429  if (header != m_headers_cache.end()) {
430  header_out = header->second;
431  return true;
432  }
433  }
434 
435  DBVal entry;
436  if (!LookupOne(*m_db, block_index, entry)) {
437  return false;
438  }
439 
440  if (is_checkpoint && m_headers_cache.size() < CF_HEADERS_CACHE_MAX_SZ) {
441  // Add to the headers cache if this is a checkpoint height.
442  m_headers_cache.emplace(block_index->GetBlockHash(), entry.header);
443  }
444 
445  header_out = entry.header;
446  return true;
447 }
448 
450  int start_height, const CBlockIndex *stop_index,
451  std::vector<BlockFilter> &filters_out) const {
452  std::vector<DBVal> entries;
453  if (!LookupRange(*m_db, m_name, start_height, stop_index, entries)) {
454  return false;
455  }
456 
457  filters_out.resize(entries.size());
458  auto filter_pos_it = filters_out.begin();
459  for (const auto &entry : entries) {
460  if (!ReadFilterFromDisk(entry.pos, *filter_pos_it)) {
461  return false;
462  }
463  ++filter_pos_it;
464  }
465 
466  return true;
467 }
468 
470  int start_height, const CBlockIndex *stop_index,
471  std::vector<uint256> &hashes_out) const
472 
473 {
474  std::vector<DBVal> entries;
475  if (!LookupRange(*m_db, m_name, start_height, stop_index, entries)) {
476  return false;
477  }
478 
479  hashes_out.clear();
480  hashes_out.reserve(entries.size());
481  for (const auto &entry : entries) {
482  hashes_out.push_back(entry.hash);
483  }
484  return true;
485 }
486 
488  auto it = g_filter_indexes.find(filter_type);
489  return it != g_filter_indexes.end() ? &it->second : nullptr;
490 }
491 
492 void ForEachBlockFilterIndex(std::function<void(BlockFilterIndex &)> fn) {
493  for (auto &entry : g_filter_indexes) {
494  fn(entry.second);
495  }
496 }
497 
498 bool InitBlockFilterIndex(BlockFilterType filter_type, size_t n_cache_size,
499  bool f_memory, bool f_wipe) {
500  auto result = g_filter_indexes.emplace(
501  std::piecewise_construct, std::forward_as_tuple(filter_type),
502  std::forward_as_tuple(filter_type, n_cache_size, f_memory, f_wipe));
503  return result.second;
504 }
505 
507  return g_filter_indexes.erase(filter_type);
508 }
509 
511  g_filter_indexes.clear();
512 }
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:268
Non-refcounted RAII wrapper for FILE*.
Definition: streams.h:545
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:217
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:228
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
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)
bool LookupFilterHeader(const CBlockIndex *block_index, uint256 &header_out) EXCLUSIVE_LOCKS_REQUIRED(!m_cs_headers_cache)
Get a single filter header by block.
std::string m_name
FlatFilePos m_next_filter_pos
Definition: block.h:60
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:54
void Write(const K &key, const V &value)
Definition: dbwrapper.h:79
bool GetValue(V &value)
Definition: dbwrapper.h:160
bool GetKey(K &key)
Definition: dbwrapper.h:149
void Seek(const K &key)
Definition: dbwrapper.h:139
void Next()
Definition: dbwrapper.cpp:257
std::string ToString() const
Definition: uint256.h:78
Path class wrapper to block calls to the fs::path(std::string) implicit constructor and the fs::path:...
Definition: fs.h:30
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:206
static bool create_directories(const std::filesystem::path &p)
Create directory (and if necessary its parents), unless the leaf directory already exists or is a sym...
Definition: fs.h:179
bool UndoReadFromDisk(CBlockUndo &blockundo, const CBlockIndex *pindex)
const char * prefix
Definition: rest.cpp:819
CAddrDb db
Definition: main.cpp:35
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
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:1276
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:306
ArgsManager gArgs
Definition: system.cpp:80
bool TruncateFile(FILE *file, unsigned int length)
Definition: system.cpp:1267
bool FileCommit(FILE *file)
Definition: system.cpp:1231
bool error(const char *fmt, const Args &...args)
Definition: system.h:45
assert(!tx.IsCoinBase())