Inside Bitcoin

2001        for (size_t i = 0; i < partition_data.size(); ++i) {
2002            auto& data = partition_data[i];
2003            // Find the sequence of the representative of the partition Cluster i is in, and store
2004            // it with the Cluster.
2005            auto rep_seq = find_root_fn(&data)->sequence;
2006            an_clusters[i].second = rep_seq;
2007            // Find all dependencies whose child Cluster is Cluster i, and annotate them with rep.
2008            while (deps_it != an_deps.end()) {
2009                auto [par, chl] = deps_it->first;
2010                auto chl_cluster = FindCluster(chl, level);
2011                Assume(chl_cluster != nullptr);
2012                if (chl_cluster->m_sequence > data.sequence) break;
2013                deps_it->second = rep_seq;
2014                ++deps_it;
2015            }
2016        }
2017    }
2018
2019    // Sort both an_clusters and an_deps by sequence number of the representative of the
2020    // partition they are in, grouping all those applying to the same partition together.
2021    std::ranges::sort(an_deps, [](auto& a, auto& b) noexcept { return a.second < b.second; });
2022    std::ranges::sort(an_clusters, [](auto& a, auto& b) noexcept { return a.second < b.second; });
2023
2024    // Translate the resulting cluster groups to the m_group_data structure, and the dependencies
2025    // back to m_deps_to_add.
2026    clusterset.m_group_data = GroupData{};
2027    clusterset.m_group_data->m_group_clusters.reserve(an_clusters.size());
2028    clusterset.m_deps_to_add.clear();
2029    clusterset.m_deps_to_add.reserve(an_deps.size());
2030    clusterset.m_oversized = false;
2031    auto an_deps_it = an_deps.begin();
2032    auto an_clusters_it = an_clusters.begin();
2033    while (an_clusters_it != an_clusters.end()) {
2034        // Process all clusters/dependencies belonging to the partition with representative rep.
2035        auto rep = an_clusters_it->second;
2036        // Create and initialize a new GroupData entry for the partition.
2037        auto& new_entry = clusterset.m_group_data->m_groups.emplace_back();
2038        new_entry.m_cluster_offset = clusterset.m_group_data->m_group_clusters.size();
2039        new_entry.m_cluster_count = 0;
2040        new_entry.m_deps_offset = clusterset.m_deps_to_add.size();
2041        new_entry.m_deps_count = 0;
2042        uint32_t total_count{0};
2043        uint64_t total_size{0};
2044        // Add all its clusters to it (copying those from an_clusters to m_group_clusters).
2045        while (an_clusters_it != an_clusters.end() && an_clusters_it->second == rep) {
2046            clusterset.m_group_data->m_group_clusters.push_back(an_clusters_it->first);
2047            total_count += an_clusters_it->first->GetTxCount();
2048            total_size += an_clusters_it->first->GetTotalTxSize();
2049            ++an_clusters_it;
2050            ++new_entry.m_cluster_count;
2051        }
2052        // Add all its dependencies to it (copying those back from an_deps to m_deps_to_add).
2053        while (an_deps_it != an_deps.end() && an_deps_it->second == rep) {
2054            clusterset.m_deps_to_add.push_back(an_deps_it->first);
2055            ++an_deps_it;
2056            ++new_entry.m_deps_count;
2057        }
2058        // Detect oversizedness.
2059        if (total_count > m_max_cluster_count || total_size > m_max_cluster_size) {
2060            clusterset.m_oversized = true;
2061        }
2062    }
2063    Assume(an_deps_it == an_deps.end());
2064    Assume(an_clusters_it == an_clusters.end());
2065    Compact();
2066}
2067
2068void TxGraphImpl::Merge(std::span<Cluster*> to_merge, int level) noexcept
2069{
2070    Assume(!to_merge.empty());
2071    // Nothing to do if a group consists of just a single Cluster.
2072    if (to_merge.size() == 1) return;
2073
2074    // Move the largest Cluster to the front of to_merge. As all transactions in other to-be-merged
2075    // Clusters will be moved to that one, putting the largest one first minimizes the number of
2076    // moves.
2077    size_t max_size_pos{0};
2078    DepGraphIndex max_size = to_merge[max_size_pos]->GetTxCount();
2079    GetClusterSet(level).m_cluster_usage -= to_merge[max_size_pos]->TotalMemoryUsage();
2080    DepGraphIndex total_size = max_size;
2081    for (size_t i = 1; i < to_merge.size(); ++i) {
2082        GetClusterSet(level).m_cluster_usage -= to_merge[i]->TotalMemoryUsage();
2083        DepGraphIndex size = to_merge[i]->GetTxCount();
2084        total_size += size;
2085        if (size > max_size) {
2086            max_size_pos = i;
2087            max_size = size;
2088        }
2089    }
2090    if (max_size_pos != 0) std::swap(to_merge[0], to_merge[max_size_pos]);
2091
2092    size_t start_idx = 1;
2093    Cluster* into_cluster = to_merge[0];
2094    if (total_size > into_cluster->GetMaxTxCount()) {
2095        // The into_merge cluster is too small to fit all transactions being merged. Construct a
2096        // a new Cluster using an implementation that matches the total size, and merge everything
2097        // in there.
2098        auto new_cluster = CreateEmptyCluster(total_size);
2099        into_cluster = new_cluster.get();
2100        InsertCluster(level, std::move(new_cluster), QualityLevel::OPTIMAL);
2101        start_idx = 0;
2102    }
2103
2104    // Merge all further Clusters in the group into the result (first one, or new one), and delete
2105    // them.
2106    for (size_t i = start_idx; i < to_merge.size(); ++i) {
2107        into_cluster->Merge(*this, level, *to_merge[i]);
2108        DeleteCluster(*to_merge[i], level);
2109    }
2110    into_cluster->Compact();
2111    GetClusterSet(level).m_cluster_usage += into_cluster->TotalMemoryUsage();
2112}
2113
2114void TxGraphImpl::ApplyDependencies(int level) noexcept
2115{
2116    auto& clusterset = GetClusterSet(level);
2117    // Do not bother computing groups if we already know the result will be oversized.
2118    if (clusterset.m_oversized == true) return;
2119    // Compute the groups of to-be-merged Clusters (which also applies all removals, and splits).
2120    GroupClusters(level);
2121    Assume(clusterset.m_group_data.has_value());
2122    // Nothing to do if there are no dependencies to be added.
2123    if (clusterset.m_deps_to_add.empty()) return;
2124    // Dependencies cannot be applied if it would result in oversized clusters.
2125    if (clusterset.m_oversized == true) return;
2126
2127    // For each group of to-be-merged Clusters.
2128    for (const auto& group_entry : clusterset.m_group_data->m_groups) {
2129        auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
2130                                .subspan(group_entry.m_cluster_offset, group_entry.m_cluster_count);
2131        // Pull in all the Clusters that contain dependencies.
2132        if (level == 1) {
2133            for (Cluster*& cluster : cluster_span) {
2134                cluster = PullIn(cluster, cluster->GetLevel(*this));
2135            }
2136        }
2137        // Invoke Merge() to merge them into a single Cluster.
2138        Merge(cluster_span, level);
2139        // Actually apply all to-be-added dependencies (all parents and children from this grouping
2140        // belong to the same Cluster at this point because of the merging above).
2141        auto deps_span = std::span{clusterset.m_deps_to_add}
2142                             .subspan(group_entry.m_deps_offset, group_entry.m_deps_count);
2143        Assume(!deps_span.empty());
2144        const auto& loc = m_entries[deps_span[0].second].m_locator[level];
2145        Assume(loc.IsPresent());
2146        loc.cluster->ApplyDependencies(*this, level, deps_span);
2147    }
2148
2149    // Wipe the list of to-be-added dependencies now that they are applied.
2150    clusterset.m_deps_to_add.clear();
2151    Compact();
2152    // Also no further Cluster mergings are needed (note that we clear, but don't set to
2153    // std::nullopt, as that would imply the groupings are unknown).
2154    clusterset.m_group_data = GroupData{};
2155}
2156
2157std::pair<uint64_t, bool> GenericClusterImpl::Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept
2158{
2159    // We can only relinearize Clusters that do not need splitting.
2160    Assume(!NeedsSplitting());
2161    // No work is required for Clusters which are already optimally linearized.
2162    if (IsOptimal()) return {0, false};
2163    // Invoke the actual linearization algorithm (passing in the existing one).
2164    uint64_t rng_seed = graph.m_rng.rand64();
2165    const auto fallback_order = [&](DepGraphIndex a, DepGraphIndex b) noexcept {
2166        const auto ref_a = graph.m_entries[m_mapping[a]].m_ref;
2167        const auto ref_b = graph.m_entries[m_mapping[b]].m_ref;
2168        return graph.m_fallback_order(*ref_a, *ref_b);
2169    };
2170    auto [linearization, optimal, cost] = Linearize(
2171        /*depgraph=*/m_depgraph,
2172        /*max_cost=*/max_cost,
2173        /*rng_seed=*/rng_seed,
2174        /*fallback_order=*/fallback_order,
2175        /*old_linearization=*/m_linearization,
2176        /*is_topological=*/IsTopological());
2177    // Postlinearize to improve the linearization (if optimal, only the sub-chunk order).
2178    // This also guarantees that all chunks are connected (even when non-optimal).
2179    PostLinearize(m_depgraph, linearization);
2180    // Update the linearization.
2181    m_linearization = std::move(linearization);
2182    // Update the Cluster's quality.
2183    bool improved = false;
2184    if (optimal) {
2185        graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::OPTIMAL);
2186        improved = true;
2187    } else if (max_cost >= graph.m_acceptable_cost && !IsAcceptable()) {
2188        graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::ACCEPTABLE);
2189        improved = true;
2190    } else if (!IsTopological()) {
2191        graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
2192        improved = true;
2193    }
2194    // Update the Entry objects.
2195    Updated(graph, /*level=*/level, /*rename=*/false);
2196    return {cost, improved};
2197}
2198
2199std::pair<uint64_t, bool> SingletonClusterImpl::Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept
2200{
2201    // All singletons are optimal, oversized, or need splitting. Each of these precludes
2202    // Relinearize from being called.
2203    assert(false);
2204    return {0, false};
2205}
2206
2207void TxGraphImpl::MakeAcceptable(Cluster& cluster, int level) noexcept
2208{
2209    // Relinearize the Cluster if needed.
2210    if (!cluster.NeedsSplitting() && !cluster.IsAcceptable() && !cluster.IsOversized()) {
2211        cluster.Relinearize(*this, level, m_acceptable_cost);
2212    }
2213}
2214
2215void TxGraphImpl::MakeAllAcceptable(int level) noexcept
2216{
2217    ApplyDependencies(level);
2218    auto& clusterset = GetClusterSet(level);
2219    if (clusterset.m_oversized == true) return;
2220    for (auto quality : {QualityLevel::NEEDS_FIX, QualityLevel::NEEDS_RELINEARIZE}) {
2221        auto& queue = clusterset.m_clusters[int(quality)];
2222        while (!queue.empty()) {
2223            MakeAcceptable(*queue.back().get(), level);
2224        }
2225    }
2226}
2227
2228GenericClusterImpl::GenericClusterImpl(uint64_t sequence) noexcept : Cluster{sequence} {}
2229
2230void TxGraphImpl::AddTransaction(Ref& arg, const FeePerWeight& feerate) noexcept
2231{
2232    Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
2233    Assume(feerate.size > 0);
2234    Assume(GetRefGraph(arg) == nullptr);
2235    // Construct a new Entry, and link it with the Ref.
2236    auto idx = m_entries.size();
2237    m_entries.emplace_back();
2238    auto& entry = m_entries.back();
2239    entry.m_main_chunkindex_iterator = m_main_chunkindex.end();
2240    entry.m_ref = &arg;
2241    GetRefGraph(arg) = this;
2242    GetRefIndex(arg) = idx;
2243    // Construct a new singleton Cluster (which is necessarily optimally linearized).
2244    bool oversized = uint64_t(feerate.size) > m_max_cluster_size;
2245    auto cluster = CreateEmptyCluster(1);
2246    cluster->AppendTransaction(idx, feerate);
2247    auto cluster_ptr = cluster.get();
2248    int level = GetTopLevel();
2249    auto& clusterset = GetClusterSet(level);
2250    InsertCluster(level, std::move(cluster), oversized ? QualityLevel::OVERSIZED_SINGLETON : QualityLevel::OPTIMAL);