Inside Bitcoin
Opening the selected file…
Inside Bitcoin
Opening the selected file…
The code behind the network, with room to understand it.
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.
501for (DepGraphIndex i = 0; i < TestBitSet::Size(); ++i) {502if (!sim[i].has_value()) {503assert(idx == i);504break;505}506}507// Update sim.508sim[idx] = {feerate, TestBitSet::Singleton(idx)};509++num_tx_sim;510break;511} else if (num_tx_sim > 0 && command-- == 0) {512// AddDependencies.513DepGraphIndex child = idx_fn();514auto parents = subset_fn();515// Apply to DepGraph.516real.AddDependencies(parents, child);517// Apply to sim.518sim[child]->second |= parents;519break;520} else if (num_tx_sim > 0 && command-- == 0) {521// Remove transactions.522auto del = set_fn();523// Propagate all ancestry information before deleting anything in the simulation (as524// intermediary transactions may be deleted which impact connectivity).525anc_update_fn();526// Compare the state of the transactions being deleted.527for (auto i : del) check_fn(i);528// Apply to DepGraph.529real.RemoveTransactions(del);530// Apply to sim.531for (DepGraphIndex i = 0; i < sim.size(); ++i) {532if (sim[i].has_value()) {533if (del[i]) {534--num_tx_sim;535sim[i] = std::nullopt;536} else {537sim[i]->second -= del;538}539}540}541break;542} else if (command-- == 0) {543// Compact.544const size_t mem_before{real.DynamicMemoryUsage()};545real.Compact();546const size_t mem_after{real.DynamicMemoryUsage()};547assert(real.PositionRange() < last_compaction_pos ? mem_after < mem_before : mem_after <= mem_before);548last_compaction_pos = real.PositionRange();549break;550}551}552}554// Compare the real obtained depgraph against the simulation.555anc_update_fn();556for (DepGraphIndex i = 0; i < sim.size(); ++i) check_fn(i);557assert(real.TxCount() == num_tx_sim);558// Sanity check the result (which includes round-tripping serialization, if applicable).559SanityCheck(real);560}562FUZZ_TARGET(clusterlin_depgraph_serialization)563{564// Verify that any deserialized depgraph is acyclic and roundtrips to an identical depgraph.566// Construct a graph by deserializing.567SpanReader reader(buffer);568DepGraph<TestBitSet> depgraph;569DepGraphIndex par_code{0}, chl_code{0};570try {571reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(par_code) >> VARINT(chl_code);572} catch (const std::ios_base::failure&) {}573SanityCheck(depgraph);575// Verify the graph is a DAG.576assert(depgraph.IsAcyclic());578// Introduce a cycle, and then test that IsAcyclic returns false.579if (depgraph.TxCount() < 2) return;580DepGraphIndex par(0), chl(0);581// Pick any transaction of depgraph as parent.582par_code %= depgraph.TxCount();583for (auto i : depgraph.Positions()) {584if (par_code == 0) {585par = i;586break;587}588--par_code;589}590// Pick any ancestor of par (excluding itself) as child, if any.591auto ancestors = depgraph.Ancestors(par) - TestBitSet::Singleton(par);592if (ancestors.None()) return;593chl_code %= ancestors.Count();594for (auto i : ancestors) {595if (chl_code == 0) {596chl = i;597break;598}599--chl_code;600}601// Add the cycle-introducing dependency.602depgraph.AddDependencies(TestBitSet::Singleton(par), chl);603// Check that we now detect a cycle.604assert(!depgraph.IsAcyclic());605}607FUZZ_TARGET(clusterlin_components)608{609// Verify the behavior of DepGraphs's FindConnectedComponent and IsConnected functions.611// Construct a depgraph.612SpanReader reader(buffer);613DepGraph<TestBitSet> depgraph;614try {615reader >> Using<DepGraphFormatter>(depgraph);616} catch (const std::ios_base::failure&) {}618TestBitSet todo = depgraph.Positions();619while (todo.Any()) {620// Pick a transaction in todo, or nothing.621std::optional<DepGraphIndex> picked;622{623uint64_t picked_num{0};624try {625reader >> VARINT(picked_num);626} catch (const std::ios_base::failure&) {}627if (picked_num < todo.Size() && todo[picked_num]) {628picked = picked_num;629}630}632// Find a connected component inside todo, including picked if any.633auto component = picked ? depgraph.GetConnectedComponent(todo, *picked)634: depgraph.FindConnectedComponent(todo);636// The component must be a subset of todo and non-empty.637assert(component.IsSubsetOf(todo));638assert(component.Any());640// If picked was provided, the component must include it.641if (picked) assert(component[*picked]);643// If todo is the entire graph, and the entire graph is connected, then the component must644// be the entire graph.645if (todo == depgraph.Positions()) {646assert((component == todo) == depgraph.IsConnected());647}649// If subset is connected, then component must match subset.650assert((component == todo) == depgraph.IsConnected(todo));652// The component cannot have any ancestors or descendants outside of component but in todo.653for (auto i : component) {654assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component));655assert((depgraph.Descendants(i) & todo).IsSubsetOf(component));656}658// Starting from any component element, we must be able to reach every element.659for (auto i : component) {660// Start with just i as reachable.661TestBitSet reachable = TestBitSet::Singleton(i);662// Add in-todo descendants and ancestors to reachable until it does not change anymore.663while (true) {664TestBitSet new_reachable = reachable;665for (auto j : new_reachable) {666new_reachable |= depgraph.Ancestors(j) & todo;667new_reachable |= depgraph.Descendants(j) & todo;668}669if (new_reachable == reachable) break;670reachable = new_reachable;671}672// Verify that the result is the entire component.673assert(component == reachable);674}676// Construct an arbitrary subset of todo.677uint64_t subset_bits{0};678try {679reader >> VARINT(subset_bits);680} catch (const std::ios_base::failure&) {}681TestBitSet subset;682for (DepGraphIndex i : depgraph.Positions()) {683if (todo[i]) {684if (subset_bits & 1) subset.Set(i);685subset_bits >>= 1;686}687}688// Which must be non-empty.689if (subset.None()) subset = TestBitSet::Singleton(todo.First());690// Remove it from todo.691todo -= subset;692}694// No components can be found in an empty subset.695assert(depgraph.FindConnectedComponent(todo).None());696}698FUZZ_TARGET(clusterlin_make_connected)699{700// Verify that MakeConnected makes graphs connected.702SpanReader reader(buffer);703DepGraph<TestBitSet> depgraph;704try {705reader >> Using<DepGraphFormatter>(depgraph);706} catch (const std::ios_base::failure&) {}707MakeConnected(depgraph);708SanityCheck(depgraph);709assert(depgraph.IsConnected());710}712FUZZ_TARGET(clusterlin_chunking)713{714// Verify the correctness of the ChunkLinearization function.716// Construct a graph by deserializing.717SpanReader reader(buffer);718DepGraph<TestBitSet> depgraph;719try {720reader >> Using<DepGraphFormatter>(depgraph);721} catch (const std::ios_base::failure&) {}723// Read a valid linearization for depgraph.724auto linearization = ReadLinearization(depgraph, reader);726// Invoke the chunking functions.727auto chunking = ChunkLinearization(depgraph, linearization);728auto chunking_info = ChunkLinearizationInfo(depgraph, linearization);730// Verify consistency between the two functions.731assert(chunking.size() == chunking_info.size());732for (size_t i = 0; i < chunking.size(); ++i) {733assert(chunking[i] == chunking_info[i].feerate);734assert(SetInfo(depgraph, chunking_info[i].transactions) == chunking_info[i]);735}737// Verify that chunk feerates are monotonically non-increasing.738for (size_t i = 1; i < chunking.size(); ++i) {739assert(ByRatio{chunking[i]} <= ByRatio{chunking[i - 1]});740}742// Naively recompute the chunks (each is the highest-feerate prefix of what remains).743auto todo = depgraph.Positions();744for (const auto& [chunk_set, chunk_feerate] : chunking_info) {745assert(todo.Any());746SetInfo<TestBitSet> accumulator, best;747for (DepGraphIndex idx : linearization) {748if (todo[idx]) {749accumulator.Set(depgraph, idx);750if (best.feerate.IsEmpty() || ByRatio{accumulator.feerate} > ByRatio{best.feerate}) {
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.