Inside Bitcoin

3001            const auto& quality_clusters = clusterset.m_clusters[qual];
3002            // ... for all clusters in them ...
3003            for (ClusterSetIndex setindex = 0; setindex < quality_clusters.size(); ++setindex) {
3004                const auto& cluster = *quality_clusters[setindex];
3005                live_clusters.insert(&cluster);
3006                // The number of transactions in a Cluster cannot exceed m_max_cluster_count.
3007                assert(cluster.GetTxCount() <= m_max_cluster_count);
3008                // The level must match the Cluster's own idea of what level it is in (but GetLevel
3009                // can only be called for non-empty Clusters).
3010                assert(cluster.GetTxCount() == 0 || level == cluster.GetLevel(*this));
3011                // The sum of their sizes cannot exceed m_max_cluster_size, unless it is an
3012                // individually oversized transaction singleton. Note that groups of to-be-merged
3013                // clusters which would exceed this limit are marked oversized, which means they
3014                // are never applied.
3015                assert(cluster.IsOversized() || cluster.GetTotalTxSize() <= m_max_cluster_size);
3016                // OVERSIZED clusters are singletons.
3017                assert(!cluster.IsOversized() || cluster.GetTxCount() == 1);
3018                // Transaction counts cannot exceed the Cluster implementation's maximum
3019                // supported transactions count.
3020                assert(cluster.GetTxCount() <= cluster.GetMaxTxCount());
3021                // Unless a Split is yet to be applied, the number of transactions must not be
3022                // below the Cluster implementation's intended transaction count.
3023                if (!cluster.NeedsSplitting()) {
3024                    assert(cluster.GetTxCount() >= cluster.GetMinIntendedTxCount());
3025                }
3026
3027                // Check the sequence number.
3028                assert(cluster.m_sequence < m_next_sequence_counter);
3029                assert(!sequences.contains(cluster.m_sequence));
3030                sequences.insert(cluster.m_sequence);
3031                // Remember we saw this Cluster (only if it is non-empty; empty Clusters aren't
3032                // expected to be referenced by the Entry vector).
3033                if (cluster.GetTxCount() != 0) {
3034                    actual_clusters.insert(&cluster);
3035                }
3036                // Sanity check the cluster, according to the Cluster's internal rules.
3037                cluster.SanityCheck(*this, level);
3038                // Check that the cluster's quality and setindex matches its position in the quality list.
3039                assert(cluster.m_quality == quality);
3040                assert(cluster.m_setindex == setindex);
3041                // Count memory usage.
3042                recomputed_cluster_usage += cluster.TotalMemoryUsage();
3043            }
3044        }
3045
3046        // Verify memory usage.
3047        assert(clusterset.m_cluster_usage == recomputed_cluster_usage);
3048
3049        // Verify that all to-be-removed transactions have valid identifiers.
3050        for (GraphIndex idx : clusterset.m_to_remove) {
3051            assert(idx < m_entries.size());
3052            // We cannot assert that all m_to_remove transactions are still present: ~Ref on a
3053            // (P,M) transaction (present in main, inherited in staging) will cause an m_to_remove
3054            // addition in both main and staging, but a subsequence ApplyRemovals in main will
3055            // cause it to disappear from staging too, leaving the m_to_remove in place.
3056        }
3057
3058        // Verify that all to-be-added dependencies have valid identifiers.
3059        for (auto [par_idx, chl_idx] : clusterset.m_deps_to_add) {
3060            assert(par_idx != chl_idx);
3061            assert(par_idx < m_entries.size());
3062            assert(chl_idx < m_entries.size());
3063        }
3064
3065        // Verify that the actually encountered clusters match the ones occurring in Entry vector.
3066        assert(actual_clusters == expected_clusters[level]);
3067
3068        // Validate m_group_data cluster pointers refer to live clusters at this
3069        // level or below (staging group data may reference not-yet-pulled-in
3070        // main clusters).
3071        if (clusterset.m_group_data.has_value()) {
3072            for (const Cluster* cl : clusterset.m_group_data->m_group_clusters) {
3073                assert(live_clusters.contains(cl));
3074                assert(cl->GetTxCount() > 0);
3075                assert(FindCluster(cl->GetClusterEntry(0), level) == cl);
3076            }
3077        }
3078        // Verify that the contents of m_removed matches what was expected based on the Entry vector.
3079        std::set<GraphIndex> actual_removed(clusterset.m_removed.begin(), clusterset.m_removed.end());
3080        for (auto i : expected_unlinked) {
3081            // If a transaction exists in both main and staging, and is removed from staging (adding
3082            // it to m_removed there), and consequently destroyed (wiping the locator completely),
3083            // it can remain in m_removed despite not having an IsRemoved() locator. Exclude those
3084            // transactions from the comparison here.
3085            actual_removed.erase(i);
3086            expected_removed[level].erase(i);
3087        }
3088
3089        assert(actual_removed == expected_removed[level]);
3090
3091        // If any GraphIndex entries remain in this ClusterSet, compact is not possible.
3092        if (!clusterset.m_deps_to_add.empty()) compact_possible = false;
3093        if (!clusterset.m_to_remove.empty()) compact_possible = false;
3094        if (!clusterset.m_removed.empty()) compact_possible = false;
3095
3096        // For non-top levels, m_oversized must be known (as it cannot change until the level
3097        // on top is gone).
3098        if (level < GetTopLevel()) assert(clusterset.m_oversized.has_value());
3099    }
3100
3101    // Verify that the contents of m_unlinked matches what was expected based on the Entry vector.
3102    std::set<GraphIndex> actual_unlinked(m_unlinked.begin(), m_unlinked.end());
3103    assert(actual_unlinked == expected_unlinked);
3104
3105    // If compaction was possible, it should have been performed already, and m_unlinked must be
3106    // empty (to prevent memory leaks due to an ever-growing m_entries vector).
3107    if (compact_possible) {
3108        assert(actual_unlinked.empty());
3109    }
3110
3111    // Finally, check the chunk index.
3112    std::set<GraphIndex> actual_chunkindex;
3113    FeeFrac last_chunk_feerate;
3114    for (const auto& chunk : m_main_chunkindex) {
3115        GraphIndex idx = chunk.m_graph_index;
3116        actual_chunkindex.insert(idx);
3117        auto chunk_feerate = m_entries[idx].m_main_chunk_feerate;
3118        if (!last_chunk_feerate.IsEmpty()) {
3119            assert(ByRatio{last_chunk_feerate} >= ByRatio{FeeFrac{chunk_feerate}});
3120        }
3121        last_chunk_feerate = chunk_feerate;
3122    }
3123    assert(actual_chunkindex == expected_chunkindex);
3124}
3125
3126bool TxGraphImpl::DoWork(uint64_t max_cost) noexcept
3127{
3128    uint64_t cost_done{0};
3129    // First linearize everything in NEEDS_RELINEARIZE to an acceptable level. If more budget
3130    // remains after that, try to make everything optimal.
3131    for (QualityLevel quality : {QualityLevel::NEEDS_FIX, QualityLevel::NEEDS_RELINEARIZE, QualityLevel::ACCEPTABLE}) {
3132        // First linearize staging, if it exists, then main.
3133        for (int level = GetTopLevel(); level >= 0; --level) {
3134            // Do not modify main if it has any observers.
3135            if (level == 0 && m_main_chunkindex_observers != 0) continue;
3136            ApplyDependencies(level);
3137            auto& clusterset = GetClusterSet(level);
3138            // Do not modify oversized levels.
3139            if (clusterset.m_oversized == true) continue;
3140            auto& queue = clusterset.m_clusters[int(quality)];
3141            while (!queue.empty()) {
3142                if (cost_done >= max_cost) return false;
3143                // Randomize the order in which we process, so that if the first cluster somehow
3144                // needs more work than what max_cost allows, we don't keep spending it on the same
3145                // one.
3146                auto pos = m_rng.randrange<size_t>(queue.size());
3147                auto cost_now = max_cost - cost_done;
3148                if (quality == QualityLevel::NEEDS_FIX || quality == QualityLevel::NEEDS_RELINEARIZE) {
3149                    // If we're working with clusters that need relinearization still, only perform
3150                    // up to m_acceptable_cost work. If they become ACCEPTABLE, and we still
3151                    // have budget after all other clusters are ACCEPTABLE too, we'll spend the
3152                    // remaining budget on trying to make them OPTIMAL.
3153                    cost_now = std::min(cost_now, m_acceptable_cost);
3154                }
3155                auto [cost, improved] = queue[pos].get()->Relinearize(*this, level, cost_now);
3156                cost_done += cost;
3157                // If no improvement was made to the Cluster, it means we've essentially run out of
3158                // budget. Even though it may be the case that cost_done < max_cost still, the
3159                // linearizer decided there wasn't enough budget left to attempt anything with.
3160                // To avoid an infinite loop that keeps trying clusters with minuscule budgets,
3161                // stop here too.
3162                if (!improved) return false;
3163            }
3164        }
3165    }
3166    // All possible work has been performed, so we can return true. Note that this does *not* mean
3167    // that all clusters are optimally linearized now. It may be that there is nothing to do left
3168    // because all non-optimal clusters are in oversized and/or observer-bearing levels.
3169    return true;
3170}
3171
3172void BlockBuilderImpl::Next() noexcept
3173{
3174    // Don't do anything if we're already done.
3175    if (m_cur_iter == m_graph->m_main_chunkindex.end()) return;
3176    while (true) {
3177        // Advance the pointer, and stop if we reach the end.
3178        ++m_cur_iter;
3179        m_cur_cluster = nullptr;
3180        if (m_cur_iter == m_graph->m_main_chunkindex.end()) break;
3181        // Find the cluster pointed to by m_cur_iter.
3182        const auto& chunk_data = *m_cur_iter;
3183        const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
3184        m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
3185        m_known_end_of_cluster = false;
3186        // If we previously skipped a chunk from this cluster we cannot include more from it.
3187        if (!m_excluded_clusters.contains(m_cur_cluster->m_sequence)) break;
3188    }
3189}
3190
3191std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> BlockBuilderImpl::GetCurrentChunk() noexcept
3192{
3193    std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> ret;
3194    // Populate the return value if we are not done.
3195    if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
3196        ret.emplace();
3197        const auto& chunk_data = *m_cur_iter;
3198        const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
3199        if (chunk_data.m_chunk_count == LinearizationIndex(-1)) {
3200            // Special case in case just a single transaction remains, avoiding the need to
3201            // dispatch to and dereference Cluster.
3202            ret->first.resize(1);
3203            Assume(chunk_end_entry.m_ref != nullptr);
3204            ret->first[0] = chunk_end_entry.m_ref;
3205            m_known_end_of_cluster = true;
3206        } else {
3207            Assume(m_cur_cluster);
3208            ret->first.resize(chunk_data.m_chunk_count);
3209            auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
3210            m_known_end_of_cluster = m_cur_cluster->GetClusterRefs(*m_graph, ret->first, start_pos);
3211            // If the chunk size was 1 and at end of cluster, then the special case above should
3212            // have been used.
3213            Assume(!m_known_end_of_cluster || chunk_data.m_chunk_count > 1);
3214        }
3215        ret->second = chunk_end_entry.m_main_chunk_feerate;
3216    }
3217    return ret;
3218}
3219
3220BlockBuilderImpl::BlockBuilderImpl(TxGraphImpl& graph) noexcept : m_graph(&graph)
3221{
3222    // Make sure all clusters in main are up to date, and acceptable.
3223    m_graph->MakeAllAcceptable(0);
3224    // There cannot remain any inapplicable dependencies (only possible if main is oversized).
3225    Assume(m_graph->m_main_clusterset.m_deps_to_add.empty());
3226    // Remember that this object is observing the graph's index, so that we can detect concurrent
3227    // modifications.
3228    ++m_graph->m_main_chunkindex_observers;
3229    // Find the first chunk.
3230    m_cur_iter = m_graph->m_main_chunkindex.begin();
3231    m_cur_cluster = nullptr;
3232    if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
3233        // Find the cluster pointed to by m_cur_iter.
3234        const auto& chunk_data = *m_cur_iter;
3235        const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
3236        m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
3237    }
3238}
3239
3240BlockBuilderImpl::~BlockBuilderImpl()
3241{
3242    Assume(m_graph->m_main_chunkindex_observers > 0);
3243    // Permit modifications to the main graph again after destroying the BlockBuilderImpl.
3244    --m_graph->m_main_chunkindex_observers;
3245}
3246
3247void BlockBuilderImpl::Include() noexcept
3248{
3249    // The actual inclusion of the chunk is done by the calling code. All we have to do is switch
3250    // to the next chunk.