Inside Bitcoin

1251    // Update memory usage.
1252    graph.GetClusterSet(/*level=*/1).m_cluster_usage += ptr->TotalMemoryUsage();
1253    return ptr;
1254}
1255
1256void GenericClusterImpl::ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept
1257{
1258    // Iterate over the prefix of to_remove that applies to this cluster.
1259    Assume(!to_remove.empty());
1260    SetType todo;
1261    graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1262    do {
1263        GraphIndex idx = to_remove.front();
1264        Assume(idx < graph.m_entries.size());
1265        auto& entry = graph.m_entries[idx];
1266        auto& locator = entry.m_locator[level];
1267        // Stop once we hit an entry that applies to another Cluster.
1268        if (locator.cluster != this) break;
1269        // - Remember it in a set of to-remove DepGraphIndexes.
1270        todo.Set(locator.index);
1271        // - Remove from m_mapping. This isn't strictly necessary as unused positions in m_mapping
1272        //   are just never accessed, but set it to -1 here to increase the ability to detect a bug
1273        //   that causes it to be accessed regardless.
1274        m_mapping[locator.index] = GraphIndex(-1);
1275        // - Remove its linearization index from the Entry (if in main).
1276        if (level == 0) {
1277            entry.m_main_lin_index = LinearizationIndex(-1);
1278        }
1279        // - Mark it as missing/removed in the Entry's locator.
1280        graph.ClearLocator(level, idx, m_quality == QualityLevel::OVERSIZED_SINGLETON);
1281        to_remove = to_remove.subspan(1);
1282    } while(!to_remove.empty());
1283
1284    Assume(todo.Any());
1285    // Wipe from the Cluster's DepGraph (this is O(n) regardless of the number of entries
1286    // removed, so we benefit from batching all the removals).
1287    m_depgraph.RemoveTransactions(todo);
1288    m_mapping.resize(m_depgraph.PositionRange());
1289
1290    // Filter removed transactions out of m_linearization.
1291    m_linearization.erase(std::remove_if(m_linearization.begin(), m_linearization.end(),
1292                                         [&](auto pos) { return todo[pos]; }),
1293                          m_linearization.end());
1294
1295    Compact();
1296    graph.GetClusterSet(level).m_cluster_usage += TotalMemoryUsage();
1297    auto new_quality = IsTopological() ? QualityLevel::NEEDS_SPLIT : QualityLevel::NEEDS_SPLIT_FIX;
1298    graph.SetClusterQuality(level, m_quality, m_setindex, new_quality);
1299    Updated(graph, /*level=*/level, /*rename=*/false);
1300}
1301
1302void SingletonClusterImpl::ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept
1303{
1304    // We can only remove the one transaction this Cluster has.
1305    Assume(!to_remove.empty());
1306    Assume(GetTxCount());
1307    Assume(to_remove.front() == m_graph_index);
1308    // Pop all copies of m_graph_index from the front of to_remove (at least one, but there may be
1309    // multiple).
1310    do {
1311        to_remove = to_remove.subspan(1);
1312    } while (!to_remove.empty() && to_remove.front() == m_graph_index);
1313    // Clear this cluster.
1314    graph.ClearLocator(level, m_graph_index, m_quality == QualityLevel::OVERSIZED_SINGLETON);
1315    m_graph_index = NO_GRAPH_INDEX;
1316    graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT);
1317    // No need to account for m_cluster_usage changes here, as SingletonClusterImpl has constant
1318    // memory usage.
1319}
1320
1321void GenericClusterImpl::Clear(TxGraphImpl& graph, int level) noexcept
1322{
1323    Assume(GetTxCount());
1324    graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1325    for (auto i : m_linearization) {
1326        graph.ClearLocator(level, m_mapping[i], m_quality == QualityLevel::OVERSIZED_SINGLETON);
1327    }
1328    m_depgraph = {};
1329    m_linearization.clear();
1330    m_mapping.clear();
1331}
1332
1333void SingletonClusterImpl::Clear(TxGraphImpl& graph, int level) noexcept
1334{
1335    Assume(GetTxCount());
1336    graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1337    graph.ClearLocator(level, m_graph_index, m_quality == QualityLevel::OVERSIZED_SINGLETON);
1338    m_graph_index = NO_GRAPH_INDEX;
1339}
1340
1341void GenericClusterImpl::MoveToMain(TxGraphImpl& graph) noexcept
1342{
1343    for (auto i : m_linearization) {
1344        GraphIndex idx = m_mapping[i];
1345        auto& entry = graph.m_entries[idx];
1346        entry.m_locator[1].SetMissing();
1347    }
1348    auto quality = m_quality;
1349    // Subtract memory usage from staging and add it to main.
1350    graph.GetClusterSet(/*level=*/1).m_cluster_usage -= TotalMemoryUsage();
1351    graph.GetClusterSet(/*level=*/0).m_cluster_usage += TotalMemoryUsage();
1352    // Remove cluster itself from staging and add it to main.
1353    auto cluster = graph.ExtractCluster(1, quality, m_setindex);
1354    graph.InsertCluster(/*level=*/0, std::move(cluster), quality);
1355    Updated(graph, /*level=*/0, /*rename=*/false);
1356}
1357
1358void SingletonClusterImpl::MoveToMain(TxGraphImpl& graph) noexcept
1359{
1360    if (GetTxCount()) {
1361        auto& entry = graph.m_entries[m_graph_index];
1362        entry.m_locator[1].SetMissing();
1363    }
1364    auto quality = m_quality;
1365    graph.GetClusterSet(/*level=*/1).m_cluster_usage -= TotalMemoryUsage();
1366    auto cluster = graph.ExtractCluster(/*level=*/1, quality, m_setindex);
1367    graph.InsertCluster(/*level=*/0, std::move(cluster), quality);
1368    graph.GetClusterSet(/*level=*/0).m_cluster_usage += TotalMemoryUsage();
1369    Updated(graph, /*level=*/0, /*rename=*/false);
1370}
1371
1372void GenericClusterImpl::Compact() noexcept
1373{
1374    m_linearization.shrink_to_fit();
1375    m_mapping.shrink_to_fit();
1376    m_depgraph.Compact();
1377}
1378
1379void SingletonClusterImpl::Compact() noexcept
1380{
1381    // Nothing to compact; SingletonClusterImpl is constant size.
1382}
1383
1384void GenericClusterImpl::AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept
1385{
1386    auto chunk_feerates = ChunkLinearization(m_depgraph, m_linearization);
1387    ret.reserve(ret.size() + chunk_feerates.size());
1388    ret.insert(ret.end(), chunk_feerates.begin(), chunk_feerates.end());
1389}
1390
1391void SingletonClusterImpl::AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept
1392{
1393    if (GetTxCount()) {
1394        ret.push_back(m_feerate);
1395    }
1396}
1397
1398uint64_t GenericClusterImpl::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept
1399{
1400    Assume(IsAcceptable());
1401    auto linchunking = ChunkLinearizationInfo(m_depgraph, m_linearization);
1402    LinearizationIndex pos{0};
1403    uint64_t size{0};
1404    auto prev_index = GraphIndex(-1);
1405    // Iterate over the chunks of this cluster's linearization.
1406    for (const auto& [chunk, chunk_feerate] : linchunking) {
1407        // Iterate over the transactions of that chunk, in linearization order.
1408        auto chunk_tx_count = chunk.Count();
1409        for (unsigned j = 0; j < chunk_tx_count; ++j) {
1410            auto cluster_idx = m_linearization[pos];
1411            // The transaction must appear in the chunk.
1412            Assume(chunk[cluster_idx]);
1413            // Construct a new element in ret.
1414            auto& entry = ret.emplace_back();
1415            entry.m_chunk_feerate = FeePerWeight::FromFeeFrac(chunk_feerate);
1416            entry.m_index = m_mapping[cluster_idx];
1417            // If this is not the first transaction of the cluster linearization, it has an
1418            // implicit dependency on its predecessor.
1419            if (pos != 0) deps.emplace_back(prev_index, entry.m_index);
1420            prev_index = entry.m_index;
1421            entry.m_tx_size = m_depgraph.FeeRate(cluster_idx).size;
1422            size += entry.m_tx_size;
1423            ++pos;
1424        }
1425    }
1426    return size;
1427}
1428
1429uint64_t SingletonClusterImpl::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept
1430{
1431    if (!GetTxCount()) return 0;
1432    auto& entry = ret.emplace_back();
1433    entry.m_chunk_feerate = m_feerate;
1434    entry.m_index = m_graph_index;
1435    entry.m_tx_size = m_feerate.size;
1436    return m_feerate.size;
1437}
1438
1439bool GenericClusterImpl::Split(TxGraphImpl& graph, int level) noexcept
1440{
1441    // This function can only be called when the Cluster needs splitting.
1442    Assume(NeedsSplitting());
1443    // Determine the new quality the split-off Clusters will have.
1444    QualityLevel new_quality = IsTopological() ? QualityLevel::NEEDS_RELINEARIZE : QualityLevel::NEEDS_FIX;
1445    /** Which positions are still left in this Cluster. */
1446    auto todo = m_depgraph.Positions();
1447    /** Mapping from transaction positions in this Cluster to the Cluster where it ends up, and
1448     *  its position therein. */
1449    std::vector<std::pair<Cluster*, DepGraphIndex>> remap(m_depgraph.PositionRange());
1450    std::vector<Cluster*> new_clusters;
1451    bool first{true};
1452    // Iterate over the connected components of this Cluster's m_depgraph.
1453    while (todo.Any()) {
1454        auto component = m_depgraph.FindConnectedComponent(todo);
1455        auto component_size = component.Count();
1456        auto split_quality = component_size <= 1 ? QualityLevel::OPTIMAL : new_quality;
1457        if (first && component == todo && SetType::Fill(component_size) == component && component_size >= MIN_INTENDED_TX_COUNT) {
1458            // The existing Cluster is an entire component, without holes. Leave it be, but update
1459            // its quality. If there are holes, we continue, so that the Cluster is reconstructed
1460            // without holes, reducing memory usage. If the component's size is below the intended
1461            // transaction count for this Cluster implementation, continue so that it can get
1462            // converted.
1463            Assume(todo == m_depgraph.Positions());
1464            graph.SetClusterQuality(level, m_quality, m_setindex, split_quality);
1465            // If this made the quality ACCEPTABLE or OPTIMAL, we need to compute and cache its
1466            // chunking.
1467            Updated(graph, /*level=*/level, /*rename=*/false);
1468            return false;
1469        }
1470        first = false;
1471        // Construct a new Cluster to hold the found component.
1472        auto new_cluster = graph.CreateEmptyCluster(component_size);
1473        new_clusters.push_back(new_cluster.get());
1474        // Remember that all the component's transactions go to this new Cluster. The positions
1475        // will be determined below, so use -1 for now.
1476        for (auto i : component) {
1477            remap[i] = {new_cluster.get(), DepGraphIndex(-1)};
1478        }
1479        graph.InsertCluster(level, std::move(new_cluster), split_quality);
1480        todo -= component;
1481    }
1482    // We have to split the Cluster up. Remove accounting for the existing one first.
1483    graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1484    // Redistribute the transactions.
1485    for (auto i : m_linearization) {
1486        /** The cluster which transaction originally in position i is moved to. */
1487        Cluster* new_cluster = remap[i].first;
1488        // Copy the transaction to the new cluster's depgraph, and remember the position.
1489        remap[i].second = new_cluster->AppendTransaction(m_mapping[i], FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(i)));
1490    }
1491    // Redistribute the dependencies.
1492    for (auto i : m_linearization) {
1493        /** The cluster transaction in position i is moved to. */
1494        Cluster* new_cluster = remap[i].first;
1495        // Copy its parents, translating positions.
1496        SetType new_parents;
1497        for (auto par : m_depgraph.GetReducedParents(i)) new_parents.Set(remap[par].second);
1498        new_cluster->AddDependencies(new_parents, remap[i].second);
1499    }
1500    // Update all the Locators of moved transactions, and memory usage.