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.
1002// Determine an upper bound on how many transactions are removed.1003uint32_t max_removed = 0;1004for (auto& cluster : clusters) {1005// Gather all transaction sizes in the to-be-combined cluster.1006std::vector<uint32_t> sizes;1007for (auto i : cluster) sizes.push_back(top_sim.graph.FeeRate(i).size);1008auto sum_sizes = std::accumulate(sizes.begin(), sizes.end(), uint64_t{0});1009// Sort from large to small.1010std::ranges::sort(sizes, std::greater{});1011// In the worst case, only the smallest transactions are removed.1012while (sizes.size() > max_cluster_count || sum_sizes > max_cluster_size) {1013sum_sizes -= sizes.back();1014sizes.pop_back();1015++max_removed;1016}1017}1019// Invoke Trim now on the definitely-oversized txgraph.1020auto removed = real->Trim();1021// Verify that the number of removals is within range.1022assert(removed.size() >= 1);1023assert(removed.size() <= max_removed);1024// The removed set must contain all its own descendants.1025auto removed_set = top_sim.MakeSet(removed);1026for (auto simpos : removed_set) {1027assert(top_sim.graph.Descendants(simpos).IsSubsetOf(removed_set));1028}1029// Something from every oversized cluster should have been removed, and nothing1030// else.1031assert(top_sim.MatchesOversizedClusters(removed_set));1033// Apply all removals to the simulation, and verify the result is no longer1034// oversized. Don't query the real graph for oversizedness; it is compared1035// against the simulation anyway later.1036for (auto simpos : removed_set) {1037top_sim.RemoveTransaction(top_sim.GetRef(simpos));1038}1039assert(!top_sim.IsOversized());1040break;1041} else if (command-- == 0) {1042// GetMainMemoryUsage().1043auto usage = real->GetMainMemoryUsage();1044// Test stability.1045if (alt) {1046auto usage2 = real->GetMainMemoryUsage();1047assert(usage == usage2);1048}1049// Only empty graphs have 0 memory usage.1050if (main_sim.GetTransactionCount() == 0) {1051assert(usage == 0);1052} else {1053assert(usage > 0);1054}1055break;1056}1057}1058}1060// After running all modifications, perform an internal sanity check (before invoking1061// inspectors that may modify the internal state).1062real->SanityCheck();1064if (!sims[0].IsOversized()) {1065// If the main graph is not oversized, verify the total ordering implied by1066// CompareMainOrder.1067// First construct two distinct randomized permutations of the positions in sims[0].1068std::vector<SimTxGraph::Pos> vec1;1069for (auto i : sims[0].graph.Positions()) vec1.push_back(i);1070std::shuffle(vec1.begin(), vec1.end(), rng);1071auto vec2 = vec1;1072std::shuffle(vec2.begin(), vec2.end(), rng);1073if (vec1 == vec2) std::next_permutation(vec2.begin(), vec2.end());1074// Sort both according to CompareMainOrder. By having randomized starting points, the order1075// of CompareMainOrder invocations is somewhat randomized as well.1076auto cmp = [&](SimTxGraph::Pos a, SimTxGraph::Pos b) noexcept {1077return real->CompareMainOrder(*sims[0].GetRef(a), *sims[0].GetRef(b)) < 0;1078};1079std::ranges::sort(vec1, cmp);1080std::ranges::sort(vec2, cmp);1082// Verify the resulting orderings are identical. This could only fail if the ordering was1083// not total.1084assert(vec1 == vec2);1086// Verify that the ordering is topological.1087auto todo = sims[0].graph.Positions();1088for (auto i : vec1) {1089todo.Reset(i);1090assert(!sims[0].graph.Ancestors(i).Overlaps(todo));1091}1092assert(todo.None());1094// If the real graph claims to be optimal (the last DoWork() call returned true), verify1095// that calling Linearize on it does not improve it further.1096if (sims[0].real_is_optimal) {1097auto real_diagram = ChunkLinearization(sims[0].graph, vec1);1098auto fallback_order_sim = [&](DepGraphIndex a, DepGraphIndex b) noexcept {1099auto txid_a = sims[0].GetRef(a)->m_txid;1100auto txid_b = sims[0].GetRef(b)->m_txid;1101return txid_a <=> txid_b;1102};1103auto [sim_lin, sim_optimal, _cost] = Linearize(sims[0].graph, 300000, rng.rand64(), fallback_order_sim, vec1);1104PostLinearize(sims[0].graph, sim_lin);1105auto sim_diagram = ChunkLinearization(sims[0].graph, sim_lin);1106auto cmp = CompareChunks(real_diagram, sim_diagram);1107assert(cmp == 0);1109// Verify consistency of cross-cluster chunk ordering with tie-break (equal-feerate1110// prefix size).1111auto real_chunking = ChunkLinearizationInfo(sims[0].graph, vec1);1112/** Map with one entry per component of the sim main graph. Key is the first Pos of the1113* component. Value is the sum of all chunk sizes from that component seen1114* already, at the current chunk feerate. */1115std::map<SimTxGraph::Pos, int32_t> comp_prefix_sizes;1116/** Current chunk feerate. */1117FeeFrac last_chunk_feerate;1118/** Largest seen (equal-feerate chunk prefix size, max txid). */1119std::pair<int32_t, uint64_t> max_chunk_tiebreak{0, 0};1120for (const auto& chunk : real_chunking) {1121// If this is the first chunk with a strictly lower feerate, reset.1122if (ByRatio{chunk.feerate} < ByRatio{last_chunk_feerate}) {1123comp_prefix_sizes.clear();1124max_chunk_tiebreak = {0, 0};1125}1126last_chunk_feerate = chunk.feerate;1127// Find which sim component this chunk belongs to.1128auto component = sims[0].graph.GetConnectedComponent(sims[0].graph.Positions(), chunk.transactions.First());1129assert(chunk.transactions.IsSubsetOf(component));1130auto comp_key = component.First();1131auto& comp_prefix_size = comp_prefix_sizes[comp_key];1132comp_prefix_size += chunk.feerate.size;1133// Determine the chunk's max txid.1134uint64_t chunk_max_txid{0};1135for (auto tx : chunk.transactions) {1136auto txid = sims[0].GetRef(tx)->m_txid;1137chunk_max_txid = std::max(txid, chunk_max_txid);1138}1139// Verify consistency: within each group of equal-feerate chunks, the1140// (equal-feerate chunk prefix size, max txid) must be increasing.1141std::pair<int32_t, uint64_t> chunk_tiebreak{comp_prefix_size, chunk_max_txid};1142assert(chunk_tiebreak > max_chunk_tiebreak);1143max_chunk_tiebreak = chunk_tiebreak;1144}1146// Verify that within each cluster, the internal ordering matches that of the1147// simulation if that is optimal too, since per-cluster optimal orderings are1148// deterministic. Note that both have been PostLinearize()'ed.1149if (sim_optimal) {1150for (const auto& component : sims[0].GetComponents()) {1151std::vector<DepGraphIndex> sim_chunk_lin, real_chunk_lin;1152for (auto i : sim_lin) {1153if (component[i]) sim_chunk_lin.push_back(i);1154}1155for (auto i : vec1) {1156if (component[i]) real_chunk_lin.push_back(i);1157}1158assert(sim_chunk_lin == real_chunk_lin);1159}1160}1162// Verify that a fresh TxGraph, with the same transactions and txids, but constructed1163// in a different order, and with a different RNG state, recreates the exact same1164// ordering, showing that for optimal graphs, the full mempool ordering is1165// deterministic.1166auto real_redo = MakeTxGraph(1167/*max_cluster_count=*/max_cluster_count,1168/*max_cluster_size=*/max_cluster_size,1169/*acceptable_cost=*/acceptable_cost,1170/*fallback_order=*/fallback_order);1171/** Vector (indexed by SimTxGraph::Pos) of TxObjects in real_redo). */1172std::vector<std::optional<SimTxObject>> txobjects_redo;1173txobjects_redo.resize(sims[0].graph.PositionRange());1174// Recreate the graph's transactions with same feerate and txid.1175std::vector<DepGraphIndex> positions;1176for (auto i : sims[0].graph.Positions()) positions.push_back(i);1177std::shuffle(positions.begin(), positions.end(), rng);1178for (auto i : positions) {1179txobjects_redo[i].emplace(sims[0].GetRef(i)->m_txid);1180real_redo->AddTransaction(*txobjects_redo[i], FeePerWeight::FromFeeFrac(sims[0].graph.FeeRate(i)));1181}1182// Recreate the graph's dependencies.1183std::vector<std::pair<DepGraphIndex, DepGraphIndex>> deps;1184for (auto i : sims[0].graph.Positions()) {1185for (auto j : sims[0].graph.GetReducedParents(i)) {1186deps.emplace_back(j, i);1187}1188}1189std::shuffle(deps.begin(), deps.end(), rng);1190for (auto [parent, child] : deps) {1191real_redo->AddDependency(*txobjects_redo[parent], *txobjects_redo[child]);1192}1193// Do work to reach optimality.1194if (real_redo->DoWork(300000)) {1195// Start from a random permutation.1196auto vec_redo = vec1;1197std::shuffle(vec_redo.begin(), vec_redo.end(), rng);1198if (vec_redo == vec1) std::next_permutation(vec_redo.begin(), vec_redo.end());1199// Sort it according to the main graph order in real_redo.1200auto cmp_redo = [&](SimTxGraph::Pos a, SimTxGraph::Pos b) noexcept {1201return real_redo->CompareMainOrder(*txobjects_redo[a], *txobjects_redo[b]) < 0;1202};1203std::ranges::sort(vec_redo, cmp_redo);1204// Compare with the ordering we got from real.1205assert(vec1 == vec_redo);1206}1207}1209// For every transaction in the total ordering, find a random one before it and after it,1210// and compare their chunk feerates, which must be consistent with the ordering.1211for (size_t pos = 0; pos < vec1.size(); ++pos) {1212auto pos_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[pos]));1213if (pos > 0) {1214size_t before = rng.randrange<size_t>(pos);1215auto before_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[before]));1216assert(ByRatio{before_feerate} >= ByRatio{pos_feerate});1217}1218if (pos + 1 < vec1.size()) {1219size_t after = pos + 1 + rng.randrange<size_t>(vec1.size() - 1 - pos);1220auto after_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[after]));1221assert(ByRatio{after_feerate} <= ByRatio{pos_feerate});1222}1223}1225// The same order should be obtained through a BlockBuilder as implied by CompareMainOrder,1226// if nothing is skipped.1227auto builder = real->GetBlockBuilder();1228std::vector<SimTxGraph::Pos> vec_builder;1229std::vector<TxGraph::Ref*> last_chunk;1230FeePerWeight last_chunk_feerate;1231while (auto chunk = builder->GetCurrentChunk()) {1232FeePerWeight sum;1233for (TxGraph::Ref* ref : chunk->first) {1234// The reported chunk feerate must match the chunk feerate obtained by asking1235// it for each of the chunk's transactions individually.1236assert(real->GetMainChunkFeerate(*ref) == chunk->second);1237// Verify the chunk feerate matches the sum of the reported individual feerates.1238sum += real->GetIndividualFeerate(*ref);1239// Chunks must contain transactions that exist in the graph.1240auto simpos = sims[0].Find(ref);1241assert(simpos != SimTxGraph::MISSING);1242vec_builder.push_back(simpos);1243}1244assert(sum == chunk->second);1245last_chunk = std::move(chunk->first);1246last_chunk_feerate = chunk->second;1247builder->Include();1248}1249assert(vec_builder == vec1);
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.