READ THE CODE

Inside Bitcoin

The code behind the network, with room to understand it.

Stable release v32.1bitcoin/bitcoin · f0de87f04062 ↗3,020 source files · 47.5 MB stored on the server440 file guides

Release published 2026-10-28 · Snapshot fetched 2026-11-01. Latest stable release at fetch time; development branches and Git history are excluded. Only the selected code window and visible folders load here.

51,207 bytes · SHA-256 c22cd591a0ffa154… · View upstream ↗

1// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file. See the AUTHORS file for names of contributors.
4
5#include "db/version_set.h"
6
7#include <stdio.h>
8
9#include <algorithm>
10
11#include "db/filename.h"
12#include "db/log_reader.h"
13#include "db/log_writer.h"
14#include "db/memtable.h"
15#include "db/table_cache.h"
16#include "leveldb/env.h"
17#include "leveldb/table_builder.h"
18#include "table/merger.h"
19#include "table/two_level_iterator.h"
20#include "util/coding.h"
21#include "util/logging.h"
22
23namespace leveldb {
24
25static size_t TargetFileSize(const Options* options) {
26  return options->max_file_size;
27}
28
29// Maximum bytes of overlaps in grandparent (i.e., level+2) before we
30// stop building a single file in a level->level+1 compaction.
31static int64_t MaxGrandParentOverlapBytes(const Options* options) {
32  return 10 * TargetFileSize(options);
33}
34
35// Maximum number of bytes in all compacted files.  We avoid expanding
36// the lower level file set of a compaction if it would make the
37// total compaction cover more than this many bytes.
38static int64_t ExpandedCompactionByteSizeLimit(const Options* options) {
39  return 25 * TargetFileSize(options);
40}
41
42static double MaxBytesForLevel(const Options* options, int level) {
43  // Note: the result for level zero is not really used since we set
44  // the level-0 compaction threshold based on number of files.
45
46  // Result for both level-0 and level-1
47  double result = 10. * 1048576.0;
48  while (level > 1) {
49    result *= 10;
50    level--;
51  }
52  return result;
53}
54
55static uint64_t MaxFileSizeForLevel(const Options* options, int level) {
56  // We could vary per level to reduce number of files?
57  return TargetFileSize(options);
58}
59
60static int64_t TotalFileSize(const std::vector<FileMetaData*>& files) {
61  int64_t sum = 0;
62  for (size_t i = 0; i < files.size(); i++) {
63    sum += files[i]->file_size;
64  }
65  return sum;
66}
67
68Version::~Version() {
69  assert(refs_ == 0);
70
71  // Remove from linked list
72  prev_->next_ = next_;
73  next_->prev_ = prev_;
74
75  // Drop references to files
76  for (int level = 0; level < config::kNumLevels; level++) {
77    for (size_t i = 0; i < files_[level].size(); i++) {
78      FileMetaData* f = files_[level][i];
79      assert(f->refs > 0);
80      f->refs--;
81      if (f->refs <= 0) {
82        delete f;
83      }
84    }
85  }
86}
87
88int FindFile(const InternalKeyComparator& icmp,
89             const std::vector<FileMetaData*>& files, const Slice& key) {
90  uint32_t left = 0;
91  uint32_t right = files.size();
92  while (left < right) {
93    uint32_t mid = (left + right) / 2;
94    const FileMetaData* f = files[mid];
95    if (icmp.InternalKeyComparator::Compare(f->largest.Encode(), key) < 0) {
96      // Key at "mid.largest" is < "target".  Therefore all
97      // files at or before "mid" are uninteresting.
98      left = mid + 1;
99    } else {
100      // Key at "mid.largest" is >= "target".  Therefore all files
101      // after "mid" are uninteresting.
102      right = mid;
103    }
104  }
105  return right;
106}
107
108static bool AfterFile(const Comparator* ucmp, const Slice* user_key,
109                      const FileMetaData* f) {
110  // null user_key occurs before all keys and is therefore never after *f
111  return (user_key != nullptr &&
112          ucmp->Compare(*user_key, f->largest.user_key()) > 0);
113}
114
115static bool BeforeFile(const Comparator* ucmp, const Slice* user_key,
116                       const FileMetaData* f) {
117  // null user_key occurs after all keys and is therefore never before *f
118  return (user_key != nullptr &&
119          ucmp->Compare(*user_key, f->smallest.user_key()) < 0);
120}
121
122bool SomeFileOverlapsRange(const InternalKeyComparator& icmp,
123                           bool disjoint_sorted_files,
124                           const std::vector<FileMetaData*>& files,
125                           const Slice* smallest_user_key,
126                           const Slice* largest_user_key) {
127  const Comparator* ucmp = icmp.user_comparator();
128  if (!disjoint_sorted_files) {
129    // Need to check against all files
130    for (size_t i = 0; i < files.size(); i++) {
131      const FileMetaData* f = files[i];
132      if (AfterFile(ucmp, smallest_user_key, f) ||
133          BeforeFile(ucmp, largest_user_key, f)) {
134        // No overlap
135      } else {
136        return true;  // Overlap
137      }
138    }
139    return false;
140  }
141
142  // Binary search over file list
143  uint32_t index = 0;
144  if (smallest_user_key != nullptr) {
145    // Find the earliest possible internal key for smallest_user_key
146    InternalKey small_key(*smallest_user_key, kMaxSequenceNumber,
147                          kValueTypeForSeek);
148    index = FindFile(icmp, files, small_key.Encode());
149  }
150
151  if (index >= files.size()) {
152    // beginning of range is after all files, so no overlap.
153    return false;
154  }
155
156  return !BeforeFile(ucmp, largest_user_key, files[index]);
157}
158
159// An internal iterator.  For a given version/level pair, yields
160// information about the files in the level.  For a given entry, key()
161// is the largest key that occurs in the file, and value() is an
162// 16-byte value containing the file number and file size, both
163// encoded using EncodeFixed64.
164class Version::LevelFileNumIterator : public Iterator {
165 public:
166  LevelFileNumIterator(const InternalKeyComparator& icmp,
167                       const std::vector<FileMetaData*>* flist)
168      : icmp_(icmp), flist_(flist), index_(flist->size()) {  // Marks as invalid
169  }
170  bool Valid() const override { return index_ < flist_->size(); }
171  void Seek(const Slice& target) override {
172    index_ = FindFile(icmp_, *flist_, target);
173  }
174  void SeekToFirst() override { index_ = 0; }
175  void SeekToLast() override {
176    index_ = flist_->empty() ? 0 : flist_->size() - 1;
177  }
178  void Next() override {
179    assert(Valid());
180    index_++;
181  }
182  void Prev() override {
183    assert(Valid());
184    if (index_ == 0) {
185      index_ = flist_->size();  // Marks as invalid
186    } else {
187      index_--;
188    }
189  }
190  Slice key() const override {
191    assert(Valid());
192    return (*flist_)[index_]->largest.Encode();
193  }
194  Slice value() const override {
195    assert(Valid());
196    EncodeFixed64(value_buf_, (*flist_)[index_]->number);
197    EncodeFixed64(value_buf_ + 8, (*flist_)[index_]->file_size);
198    return Slice(value_buf_, sizeof(value_buf_));
199  }
200  Status status() const override { return Status::OK(); }
201
202 private:
203  const InternalKeyComparator icmp_;
204  const std::vector<FileMetaData*>* const flist_;
205  uint32_t index_;
206
207  // Backing store for value().  Holds the file number and size.
208  mutable char value_buf_[16];
209};
210
211static Iterator* GetFileIterator(void* arg, const ReadOptions& options,
212                                 const Slice& file_value) {
213  TableCache* cache = reinterpret_cast<TableCache*>(arg);
214  if (file_value.size() != 16) {
215    return NewErrorIterator(
216        Status::Corruption("FileReader invoked with unexpected value"));
217  } else {
218    return cache->NewIterator(options, DecodeFixed64(file_value.data()),
219                              DecodeFixed64(file_value.data() + 8));
220  }
221}
222
223Iterator* Version::NewConcatenatingIterator(const ReadOptions& options,
224                                            int level) const {
225  return NewTwoLevelIterator(
226      new LevelFileNumIterator(vset_->icmp_, &files_[level]), &GetFileIterator,
227      vset_->table_cache_, options);
228}
229
230void Version::AddIterators(const ReadOptions& options,
231                           std::vector<Iterator*>* iters) {
232  // Merge all level zero files together since they may overlap
233  for (size_t i = 0; i < files_[0].size(); i++) {
234    iters->push_back(vset_->table_cache_->NewIterator(
235        options, files_[0][i]->number, files_[0][i]->file_size));
236  }
237
238  // For levels > 0, we can use a concatenating iterator that sequentially
239  // walks through the non-overlapping files in the level, opening them
240  // lazily.
241  for (int level = 1; level < config::kNumLevels; level++) {
242    if (!files_[level].empty()) {
243      iters->push_back(NewConcatenatingIterator(options, level));
244    }
245  }
246}
247
248// Callback from TableCache::Get()
249namespace {
250enum SaverState {

src/wallet/receive.cpp

src/wallet/coinselection.cpp

src/consensus/validation.h

src/primitives/transaction.cpp

src/script/descriptor.cpp

src/bitcoin-cli.cpp

src/rpc/blockchain.cpp

src/rpc/rawtransaction.cpp

src/init.cpp

src/crypto/sha256.cpp

src/consensus/merkle.h

src/consensus/tx_check.h

src/consensus/tx_verify.h

src/policy/feerate.h

src/policy/feerate.cpp

src/primitives/transaction_identifier.h

src/chainparamsbase.h

src/chainparamsbase.cpp

src/util/moneystr.cpp

src/crypto/ripemd160.h

src/crypto/sha1.h

src/crypto/sha512.h

src/crypto/hmac_sha256.h

src/crypto/hmac_sha512.h

src/crypto/hmac_sha256.cpp

src/crypto/hmac_sha512.cpp

src/crypto/hkdf_sha256_32.h

src/crypto/hkdf_sha256_32.cpp

src/support/cleanse.h

src/support/cleanse.cpp

src/crypto/siphash.cpp

src/crypto/muhash.h

src/crypto/chacha20.h

src/crypto/poly1305.h

src/crypto/chacha20poly1305.h

src/crypto/chacha20poly1305.cpp

src/util/chaintype.cpp

src/util/obfuscation.h

src/util/byte_units.h

src/util/overflow.h

src/blockencodings.cpp

src/net_permissions.cpp

src/policy/packages.cpp

src/policy/rbf.cpp

src/policy/truc_policy.cpp

src/policy/ephemeral_policy.cpp

src/policy/settings.cpp

src/policy/policy.cpp

src/node/transaction.cpp

src/node/coin.cpp

src/rpc/client.cpp

src/rpc/external_signer.cpp

src/rpc/request.cpp

src/rpc/server_util.cpp

src/rpc/fees.cpp

src/rpc/output_script.cpp

src/rpc/rawtransaction_util.cpp

src/rpc/rawtransaction_util.h

src/rpc/register.h

src/rpc/request.h

src/rpc/server_util.h

src/rpc/protocol.h

src/rpc/server.h

src/rpc/signmessage.cpp

src/rpc/txoutproof.cpp

src/rpc/util.cpp

src/rpc/util.h

src/wallet/rpc/addresses.cpp

src/wallet/rpc/backup.cpp

src/wallet/rpc/coins.cpp

src/wallet/rpc/encrypt.cpp

src/wallet/rpc/signmessage.cpp

src/wallet/rpc/util.cpp

src/wallet/rpc/util.h

src/wallet/coincontrol.cpp

src/wallet/coincontrol.h

src/wallet/context.cpp

src/wallet/context.h

src/wallet/crypter.cpp

src/wallet/crypter.h

src/wallet/db.cpp

src/wallet/export.cpp

src/wallet/external_signer_scriptpubkeyman.cpp

src/wallet/rpc/spend.cpp

src/wallet/rpc/transactions.cpp

src/wallet/rpc/wallet.cpp

src/wallet/feebumper.cpp

src/wallet/feebumper.h

src/index/base.h

src/index/base.cpp

src/index/txindex.h

src/index/txindex.cpp

src/index/txindex_key.h

src/index/txospenderindex.h

src/index/txospenderindex.cpp

src/index/blockfilterindex.h

src/index/blockfilterindex.cpp

src/index/coinstatsindex.h

src/index/coinstatsindex.cpp

src/index/db_key.h

src/index/disktxpos.h

src/kernel/chain.cpp

src/kernel/chain.h

src/kernel/checks.cpp

src/kernel/checks.h

src/kernel/context.cpp

src/kernel/context.h

src/kernel/cs_main.cpp

src/kernel/cs_main.h

src/kernel/disconnected_transactions.cpp

src/kernel/disconnected_transactions.h

src/kernel/mempool_removal_reason.cpp

src/kernel/mempool_removal_reason.h

src/kernel/coinstats.cpp

src/kernel/coinstats.h

src/kernel/chainparams.cpp

src/kernel/chainparams.h

src/wallet/sqlite.cpp

src/wallet/sqlite.h

src/wallet/transaction.cpp

src/wallet/transaction.h

src/wallet/dump.cpp

src/wallet/dump.h

src/wallet/init.cpp

src/wallet/walletutil.cpp

src/wallet/walletutil.h

src/wallet/wallettool.cpp

src/wallet/wallettool.h

src/wallet/export.h

src/wallet/migrate.cpp

src/wallet/migrate.h

src/wallet/db.h

src/wallet/walletdb.cpp

src/wallet/interfaces.cpp

src/wallet/scriptpubkeyman.cpp

src/wallet/scriptpubkeyman.h

src/kernel/bitcoinkernel.cpp

src/kernel/bitcoinkernel.h

src/kernel/bitcoinkernel_wrapper.h

src/node/chainstate.cpp

src/node/chainstate.h

src/node/blockstorage.cpp

src/node/blockstorage.h

src/node/mempool_persist.cpp

src/node/mempool_persist.h

src/node/utxo_snapshot.cpp

src/node/utxo_snapshot.h

src/node/kernel_notifications.cpp

src/node/kernel_notifications.h

src/node/blockmanager_args.cpp

src/kernel/blockmanager_opts.h

src/util/expected.cpp

src/policy/settings.h

src/util/types.h

src/kernel/messagestartchars.h

src/kernel/warning.h

src/util/exception.h

src/common/license_info.h

src/node/coins_view_args.h

src/node/database_args.h

src/util/batchpriority.h

src/util/ui_change_type.h

src/node/coins_view_args.cpp

src/node/peerman_args.h

src/util/serfloat.h

src/node/blockmanager_args.h

src/node/database_args.cpp

src/util/overloaded.h

src/interfaces/types.h

src/node/chainstatemanager_args.h

src/node/minisketchwrapper.h

src/util/macros.h

src/util/syserror.h

src/common/run_command.h

src/util/bytevectorhash.cpp

src/node/mempool_persist_args.cpp

src/util/exec.h

src/util/rbf.h

src/crypto/hex_base.h

src/node/mempool_persist_args.h

src/interfaces/echo.h

src/util/any.h

src/util/batchpriority.cpp

src/util/threadnames.h

src/node/coin.h

src/node/mempool_args.h

src/util/asmap.h

src/util/bytevectorhash.h

src/node/context.cpp

src/util/insert.h

src/util/readwritefile.h

src/node/peerman_args.cpp

src/node/interface_ui.cpp

src/interfaces/handler.h

src/node/mining_args.h

src/util/hasher.cpp

src/common/init.h

src/kernel/mempool_limits.h

src/common/system.h

src/crypto/sha3.h

src/util/threadinterrupt.cpp

src/node/protocol_version.h

src/util/exception.cpp

src/common/messages.h

src/node/connection_types.cpp

src/util/bip32.h

src/common/license_info.cpp

src/util/stdmutex.h

src/common/run_command.cpp

src/util/check.cpp

src/util/golombrice.h

src/node/types.h

src/node/timeoffsets.h

src/util/readwritefile.cpp

src/util/fastrange.h

src/util/signalinterrupt.h

src/util/task_runner.h

src/util/syserror.cpp

src/common/interfaces.cpp

src/common/types.h

src/util/threadinterrupt.h

src/kernel/chainstatemanager_opts.h

src/node/psbt.h

src/policy/ephemeral_policy.h

src/util/trace.h

src/common/url.cpp

src/kernel/mempool_options.h

src/util/serfloat.cpp

src/kernel/notifications_interface.h

src/node/timeoffsets.cpp

src/node/warnings.cpp

src/util/hash_type.h

src/crypto/hex_base.cpp

src/node/eviction.h

src/util/tokenbucket.h

src/crypto/aes.h

src/common/pcp.h

src/util/feefrac.cpp

src/node/transaction.h

src/util/threadnames.cpp

src/common/signmessage.h

src/util/exec.cpp

src/util/signalinterrupt.cpp

src/clientversion.cpp

src/common/signmessage.cpp

src/compat/assumptions.h

src/compat/byteswap.h

src/deploymentinfo.cpp

src/deploymentinfo.h

src/deploymentstatus.cpp

src/deploymentstatus.h

src/dummywallet.cpp

src/external_signer.h

src/init/bitcoin-gui.cpp

src/init/bitcoin-node.cpp

src/init/bitcoin-qt.cpp

src/init/bitcoin-wallet.cpp

src/init/bitcoind.cpp

src/init/common.h

src/interfaces/init.h

src/interfaces/ipc.h

src/key_io.h

src/logging/categories.h

src/logging/timer.h

src/mapport.h

src/musig.h

src/net_permissions.h

src/netgroup.h

src/netmessagemaker.h

src/node/chainstatemanager_args.cpp

src/node/connection_types.h

src/node/context.h

src/node/interface_ui.h

src/node/mempool_args.cpp

src/node/mining_args.cpp

src/node/minisketchwrapper.cpp

src/node/txreconciliation.h

src/policy/fees/estimator_args.cpp

src/policy/fees/estimator_args.h

src/policy/fees/estimator_man.cpp

src/policy/fees/estimator_man.h

src/policy/packages.h

src/policy/rbf.h

src/policy/truc_policy.h

src/pow.h

src/primitives/block.cpp

src/randomenv.h

src/rest.h

src/script/keyorigin.h

src/script/parsing.cpp

src/script/parsing.h

src/script/script_error.h

src/script/sigcache.cpp

src/script/sigcache.h

src/script/solver.h

src/script/verify_flags.h

src/semaphore_grant.h

src/signet.h

src/span.h

src/support/allocators/secure.h

src/support/allocators/zeroafterfree.h

src/util/tokenpipe.cpp

src/util/translation.h

src/util/vector.h

src/versionbits.h

src/versionbits_impl.h

src/wallet/external_signer_scriptpubkeyman.h

src/wallet/fees.h

src/wallet/load.h

src/wallet/receive.h

src/wallet/rpc/wallet.h

src/wallet/types.h

src/walletinitinterface.h

src/zmq/zmqabstractnotifier.cpp

Independent explanations by MyBitcoinExplorer. Not affiliated with or endorsed by Bitcoin Core. Guides are educational and do not replace the source or its tests.

Bitcoin Core source © its contributors, distributed under the MIT license. Original notices and bundled third-party licenses are retained in the source tree.