From bb424029459af691c4d07988f3d76afeaee21644 Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 09:48:52 -0400 Subject: doc: fix comment about non-existing CompareFeeFrac --- src/util/feefrac.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/util/feefrac.h b/src/util/feefrac.h index 48bd287c7c..7102f85f88 100644 --- a/src/util/feefrac.h +++ b/src/util/feefrac.h @@ -31,7 +31,7 @@ * A FeeFrac is considered "better" if it sorts after another, by this ordering. All standard * comparison operators (<=>, ==, !=, >, <, >=, <=) respect this ordering. * - * The CompareFeeFrac, and >> and << operators only compare feerate and treat equal feerate but + * The FeeRateCompare, and >> and << operators only compare feerate and treat equal feerate but * different size as equivalent. The empty FeeFrac is neither lower or higher in feerate than any * other. */ -- cgit v1.2.3 From b62e2c0fa5f6010ff1fc60c59418d0796b83c5de Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 09:50:03 -0400 Subject: ImprovesFeerateDiagram: Spelling fix and removal of unused diagram vectors --- src/policy/rbf.cpp | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) diff --git a/src/policy/rbf.cpp b/src/policy/rbf.cpp index a2c6990657..84c3352b9d 100644 --- a/src/policy/rbf.cpp +++ b/src/policy/rbf.cpp @@ -190,9 +190,7 @@ std::optional> ImprovesFeerateDiagram( CAmount replacement_fees, int64_t replacement_vsize) { - // Require that the replacement strictly improve the mempool's feerate diagram. - std::vector old_diagram, new_diagram; - + // Require that the replacement strictly improves the mempool's feerate diagram. const auto diagram_results{pool.CalculateFeerateDiagramsForRBF(replacement_fees, replacement_vsize, direct_conflicts, all_conflicts)}; if (!diagram_results.has_value()) { -- cgit v1.2.3 From c0c37f07eb0fb4027faa04e5457f8421264e8ad5 Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 09:55:41 -0400 Subject: unit test: have CompareFeerateDiagram tested with diagrams both ways --- src/test/rbf_tests.cpp | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) diff --git a/src/test/rbf_tests.cpp b/src/test/rbf_tests.cpp index 961fd62fe4..62549232f3 100644 --- a/src/test/rbf_tests.cpp +++ b/src/test/rbf_tests.cpp @@ -503,18 +503,21 @@ BOOST_AUTO_TEST_CASE(feerate_diagram_utilities) std::vector new_diagram{{FeeFrac{0, 0}, FeeFrac{1000, 300}, FeeFrac{1050, 400}}}; BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram))); + BOOST_CHECK(std::is_gt(CompareFeerateDiagram(new_diagram, old_diagram))); // Incomparable diagrams old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}}; new_diagram = {FeeFrac{0, 0}, FeeFrac{1000, 300}, FeeFrac{1000, 400}}; BOOST_CHECK(CompareFeerateDiagram(old_diagram, new_diagram) == std::partial_ordering::unordered); + BOOST_CHECK(CompareFeerateDiagram(new_diagram, old_diagram) == std::partial_ordering::unordered); // Strictly better but smaller size. old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}}; new_diagram = {FeeFrac{0, 0}, FeeFrac{1100, 300}}; BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram))); + BOOST_CHECK(std::is_gt(CompareFeerateDiagram(new_diagram, old_diagram))); // New diagram is strictly better due to the first chunk, even though // second chunk contributes no fees @@ -522,24 +525,28 @@ BOOST_AUTO_TEST_CASE(feerate_diagram_utilities) new_diagram = {FeeFrac{0, 0}, FeeFrac{1100, 100}, FeeFrac{1100, 200}}; BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram))); + BOOST_CHECK(std::is_gt(CompareFeerateDiagram(new_diagram, old_diagram))); // Feerate of first new chunk is better with, but second chunk is worse old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}}; new_diagram = {FeeFrac{0, 0}, FeeFrac{750, 100}, FeeFrac{999, 350}, FeeFrac{1150, 1000}}; BOOST_CHECK(CompareFeerateDiagram(old_diagram, new_diagram) == std::partial_ordering::unordered); + BOOST_CHECK(CompareFeerateDiagram(new_diagram, old_diagram) == std::partial_ordering::unordered); // If we make the second chunk slightly better, the new diagram now wins. old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}}; new_diagram = {FeeFrac{0, 0}, FeeFrac{750, 100}, FeeFrac{1000, 350}, FeeFrac{1150, 500}}; BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram))); + BOOST_CHECK(std::is_gt(CompareFeerateDiagram(new_diagram, old_diagram))); // Identical diagrams, cannot be strictly better old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}}; new_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}}; BOOST_CHECK(std::is_eq(CompareFeerateDiagram(old_diagram, new_diagram))); + BOOST_CHECK(std::is_eq(CompareFeerateDiagram(new_diagram, old_diagram))); // Same aggregate fee, but different total size (trigger single tail fee check step) old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 399}}; @@ -547,8 +554,6 @@ BOOST_AUTO_TEST_CASE(feerate_diagram_utilities) // No change in evaluation when tail check needed. BOOST_CHECK(std::is_gt(CompareFeerateDiagram(old_diagram, new_diagram))); - - // Padding works on either argument BOOST_CHECK(std::is_lt(CompareFeerateDiagram(new_diagram, old_diagram))); // Trigger multiple tail fee check steps @@ -561,6 +566,7 @@ BOOST_AUTO_TEST_CASE(feerate_diagram_utilities) // Multiple tail fee check steps, unordered result new_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}, FeeFrac{1050, 401}, FeeFrac{1050, 402}, FeeFrac{1051, 403}}; BOOST_CHECK(CompareFeerateDiagram(old_diagram, new_diagram) == std::partial_ordering::unordered); + BOOST_CHECK(CompareFeerateDiagram(new_diagram, old_diagram) == std::partial_ordering::unordered); } BOOST_AUTO_TEST_SUITE_END() -- cgit v1.2.3 From 69bd18ca80007584be4089b3f42650d351854bb3 Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 09:59:10 -0400 Subject: unit test: check tx4 conflict error message --- src/test/rbf_tests.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/test/rbf_tests.cpp b/src/test/rbf_tests.cpp index 62549232f3..9940c8b6e4 100644 --- a/src/test/rbf_tests.cpp +++ b/src/test/rbf_tests.cpp @@ -261,7 +261,7 @@ BOOST_FIXTURE_TEST_CASE(rbf_helper_functions, TestChain100Setup) // Tests for CheckConflictTopology // Tx4 has 23 descendants - BOOST_CHECK(pool.CheckConflictTopology(set_34_cpfp).has_value()); + BOOST_CHECK_EQUAL(pool.CheckConflictTopology(set_34_cpfp).value(), strprintf("%s has 23 descendants, max 1 allowed", entry4_high->GetSharedTx()->GetHash().ToString())); // No descendants yet BOOST_CHECK(pool.CheckConflictTopology({entry9_unchained}) == std::nullopt); -- cgit v1.2.3 From a80d80936a8de487569d00755d0fbcd058a94823 Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 10:23:47 -0400 Subject: unit test: add CheckConflictTopology case for not the only child --- src/test/rbf_tests.cpp | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 58 insertions(+) diff --git a/src/test/rbf_tests.cpp b/src/test/rbf_tests.cpp index 9940c8b6e4..8fe2db1a7f 100644 --- a/src/test/rbf_tests.cpp +++ b/src/test/rbf_tests.cpp @@ -37,6 +37,37 @@ static inline CTransactionRef make_tx(const std::vector& inputs return MakeTransactionRef(tx); } +// Make two child transactions from parent (which must have at least 2 outputs). +// Each tx will have the same outputs, using the amounts specified in output_values. +static inline std::pair make_two_siblings(const CTransactionRef parent, + const std::vector& output_values) +{ + assert(parent->vout.size() >= 2); + + // First tx takes first parent output + CMutableTransaction tx1 = CMutableTransaction(); + tx1.vin.resize(1); + tx1.vout.resize(output_values.size()); + + tx1.vin[0].prevout.hash = parent->GetHash(); + tx1.vin[0].prevout.n = 0; + // Add a witness so wtxid != txid + CScriptWitness witness; + witness.stack.emplace_back(10); + tx1.vin[0].scriptWitness = witness; + + for (size_t i = 0; i < output_values.size(); ++i) { + tx1.vout[i].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx1.vout[i].nValue = output_values[i]; + } + + // Second tx takes second parent output + CMutableTransaction tx2 = tx1; + tx2.vin[0].prevout.n = 1; + + return std::make_pair(MakeTransactionRef(tx1), MakeTransactionRef(tx2)); +} + static CTransactionRef add_descendants(const CTransactionRef& tx, int32_t num_descendants, CTxMemPool& pool) EXCLUSIVE_LOCKS_REQUIRED(::cs_main, pool.cs) { @@ -67,6 +98,20 @@ static CTransactionRef add_descendant_to_parents(const std::vector add_children_to_parent(const CTransactionRef parent, CTxMemPool& pool) + EXCLUSIVE_LOCKS_REQUIRED(::cs_main, pool.cs) +{ + AssertLockHeld(::cs_main); + AssertLockHeld(pool.cs); + TestMemPoolEntryHelper entry; + // Assumes this isn't already spent in mempool + auto children_tx = make_two_siblings(/*parent=*/parent, /*output_values=*/{50 * CENT}); + pool.addUnchecked(entry.FromTx(children_tx.first)); + pool.addUnchecked(entry.FromTx(children_tx.second)); + return children_tx; +} + BOOST_FIXTURE_TEST_CASE(rbf_helper_functions, TestChain100Setup) { CTxMemPool& pool = *Assert(m_node.mempool); @@ -116,6 +161,10 @@ BOOST_FIXTURE_TEST_CASE(rbf_helper_functions, TestChain100Setup) const auto tx12 = make_tx(/*inputs=*/ {m_coinbase_txns[8]}, /*output_values=*/ {995 * CENT}); pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx12)); + // Will make two children of this single parent + const auto tx13 = make_tx(/*inputs=*/ {m_coinbase_txns[9]}, /*output_values=*/ {995 * CENT, 995 * CENT}); + pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx13)); + const auto entry1_normal = pool.GetIter(tx1->GetHash()).value(); const auto entry2_normal = pool.GetIter(tx2->GetHash()).value(); const auto entry3_low = pool.GetIter(tx3->GetHash()).value(); @@ -128,6 +177,7 @@ BOOST_FIXTURE_TEST_CASE(rbf_helper_functions, TestChain100Setup) const auto entry10_unchained = pool.GetIter(tx10->GetHash()).value(); const auto entry11_unchained = pool.GetIter(tx11->GetHash()).value(); const auto entry12_unchained = pool.GetIter(tx12->GetHash()).value(); + const auto entry13_unchained = pool.GetIter(tx13->GetHash()).value(); BOOST_CHECK_EQUAL(entry1_normal->GetFee(), normal_fee); BOOST_CHECK_EQUAL(entry2_normal->GetFee(), normal_fee); @@ -292,6 +342,14 @@ BOOST_FIXTURE_TEST_CASE(rbf_helper_functions, TestChain100Setup) BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry11_unchained}).value(), strprintf("%s is not the only parent of child %s", entry11_unchained->GetSharedTx()->GetHash().ToString(), entry_two_parent_child->GetSharedTx()->GetHash().ToString())); BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry12_unchained}).value(), strprintf("%s is not the only parent of child %s", entry12_unchained->GetSharedTx()->GetHash().ToString(), entry_two_parent_child->GetSharedTx()->GetHash().ToString())); BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry_two_parent_child}).value(), strprintf("%s has 2 ancestors, max 1 allowed", entry_two_parent_child->GetSharedTx()->GetHash().ToString())); + + // Single parent with two children, we will conflict with the siblings directly only + const auto two_siblings = add_children_to_parent(tx13, pool); + const auto entry_sibling_1 = pool.GetIter(two_siblings.first->GetHash()).value(); + const auto entry_sibling_2 = pool.GetIter(two_siblings.second->GetHash()).value(); + BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry_sibling_1}).value(), strprintf("%s is not the only child of parent %s", entry_sibling_1->GetSharedTx()->GetHash().ToString(), entry13_unchained->GetSharedTx()->GetHash().ToString())); + BOOST_CHECK_EQUAL(pool.CheckConflictTopology({entry_sibling_2}).value(), strprintf("%s is not the only child of parent %s", entry_sibling_2->GetSharedTx()->GetHash().ToString(), entry13_unchained->GetSharedTx()->GetHash().ToString())); + } BOOST_FIXTURE_TEST_CASE(improves_feerate, TestChain100Setup) -- cgit v1.2.3 From 216d5ff1627be6562312b5afb477078ed8495999 Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 10:32:54 -0400 Subject: unit test: add coverage showing priority affects diagram check results --- src/test/rbf_tests.cpp | 8 ++++++++ 1 file changed, 8 insertions(+) diff --git a/src/test/rbf_tests.cpp b/src/test/rbf_tests.cpp index 8fe2db1a7f..ddfb6a9a87 100644 --- a/src/test/rbf_tests.cpp +++ b/src/test/rbf_tests.cpp @@ -385,6 +385,14 @@ BOOST_FIXTURE_TEST_CASE(improves_feerate, TestChain100Setup) // With one more satoshi it does BOOST_CHECK(ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee + 1, tx1_size + tx2_size) == std::nullopt); + // With prioritisation of in-mempool conflicts, it affects the results of the comparison using the same args as just above + pool.PrioritiseTransaction(entry1->GetSharedTx()->GetHash(), /*nFeeDelta=*/1); + const auto res2 = ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee + 1, tx1_size + tx2_size); + BOOST_CHECK(res2.has_value()); + BOOST_CHECK(res2.value().first == DiagramCheckError::FAILURE); + BOOST_CHECK(res2.value().second == "insufficient feerate: does not improve feerate diagram"); + pool.PrioritiseTransaction(entry1->GetSharedTx()->GetHash(), /*nFeeDelta=*/-1); + // Adding a grandchild makes the cluster size 3, which is uncalculable const auto tx3 = make_tx(/*inputs=*/ {tx2}, /*output_values=*/ {995 * CENT}); pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx3)); -- cgit v1.2.3 From defe023f6ec49dd64c6e03880cee0e9299b45762 Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 10:34:31 -0400 Subject: fuzz: add PrioritiseTransaction coverage in diagram checks --- src/test/fuzz/rbf.cpp | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/src/test/fuzz/rbf.cpp b/src/test/fuzz/rbf.cpp index 42008c6ad9..a3138629e2 100644 --- a/src/test/fuzz/rbf.cpp +++ b/src/test/fuzz/rbf.cpp @@ -127,6 +127,10 @@ FUZZ_TARGET(package_rbf, .init = initialize_package_rbf) } mempool_txs.emplace_back(*child); pool.addUnchecked(ConsumeTxMemPoolEntry(fuzzed_data_provider, mempool_txs.back())); + + if (fuzzed_data_provider.ConsumeBool()) { + pool.PrioritiseTransaction(mempool_txs.back().GetHash().ToUint256(), fuzzed_data_provider.ConsumeIntegralInRange(-100000, 100000)); + } } // Pick some transactions at random to be the direct conflicts -- cgit v1.2.3 From d2bf923eb19f6330bad673b71faadec582780aa1 Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 10:46:17 -0400 Subject: unit test: make calc_feerate_diagram_rbf less brittle --- src/test/rbf_tests.cpp | 141 ++++++++++++++++++++++--------------------------- 1 file changed, 62 insertions(+), 79 deletions(-) diff --git a/src/test/rbf_tests.cpp b/src/test/rbf_tests.cpp index ddfb6a9a87..a683bf84d5 100644 --- a/src/test/rbf_tests.cpp +++ b/src/test/rbf_tests.cpp @@ -420,31 +420,25 @@ BOOST_FIXTURE_TEST_CASE(calc_feerate_diagram_rbf, TestChain100Setup) const auto entry_low = pool.GetIter(low_tx->GetHash()).value(); const auto low_size = entry_low->GetTxSize(); - std::vector old_diagram, new_diagram; - // Replacement of size 1 - const auto replace_one{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/0, /*replacement_vsize=*/1, {entry_low}, {entry_low})}; - BOOST_CHECK(replace_one.has_value()); - old_diagram = replace_one->first; - new_diagram = replace_one->second; - BOOST_CHECK(old_diagram.size() == 2); - BOOST_CHECK(new_diagram.size() == 2); - BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0)); - BOOST_CHECK(old_diagram[1] == FeeFrac(low_fee, low_size)); - BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0)); - BOOST_CHECK(new_diagram[1] == FeeFrac(0, 1)); + { + const auto replace_one{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/0, /*replacement_vsize=*/1, {entry_low}, {entry_low})}; + BOOST_CHECK(replace_one.has_value()); + std::vector expected_old_diagram{FeeFrac(0, 0), FeeFrac(low_fee, low_size)}; + BOOST_CHECK(replace_one->first == expected_old_diagram); + std::vector expected_new_diagram{FeeFrac(0, 0), FeeFrac(0, 1)}; + BOOST_CHECK(replace_one->second == expected_new_diagram); + } // Non-zero replacement fee/size - const auto replace_one_fee{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_low}, {entry_low})}; - BOOST_CHECK(replace_one_fee.has_value()); - old_diagram = replace_one_fee->first; - new_diagram = replace_one_fee->second; - BOOST_CHECK(old_diagram.size() == 2); - BOOST_CHECK(new_diagram.size() == 2); - BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0)); - BOOST_CHECK(old_diagram[1] == FeeFrac(low_fee, low_size)); - BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0)); - BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size)); + { + const auto replace_one_fee{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_low}, {entry_low})}; + BOOST_CHECK(replace_one_fee.has_value()); + std::vector expected_old_diagram{FeeFrac(0, 0), FeeFrac(low_fee, low_size)}; + BOOST_CHECK(replace_one_fee->first == expected_old_diagram); + std::vector expected_new_diagram{FeeFrac(0, 0), FeeFrac(high_fee, low_size)}; + BOOST_CHECK(replace_one_fee->second == expected_new_diagram); + } // Add a second transaction to the cluster that will make a single chunk, to be evicted in the RBF const auto high_tx = make_tx(/*inputs=*/ {low_tx}, /*output_values=*/ {995 * CENT}); @@ -452,29 +446,24 @@ BOOST_FIXTURE_TEST_CASE(calc_feerate_diagram_rbf, TestChain100Setup) const auto entry_high = pool.GetIter(high_tx->GetHash()).value(); const auto high_size = entry_high->GetTxSize(); - const auto replace_single_chunk{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_low}, {entry_low, entry_high})}; - BOOST_CHECK(replace_single_chunk.has_value()); - old_diagram = replace_single_chunk->first; - new_diagram = replace_single_chunk->second; - BOOST_CHECK(old_diagram.size() == 2); - BOOST_CHECK(new_diagram.size() == 2); - BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0)); - BOOST_CHECK(old_diagram[1] == FeeFrac(low_fee + high_fee, low_size + high_size)); - BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0)); - BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size)); + { + const auto replace_single_chunk{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_low}, {entry_low, entry_high})}; + BOOST_CHECK(replace_single_chunk.has_value()); + std::vector expected_old_diagram{FeeFrac(0, 0), FeeFrac(low_fee + high_fee, low_size + high_size)}; + BOOST_CHECK(replace_single_chunk->first == expected_old_diagram); + std::vector expected_new_diagram{FeeFrac(0, 0), FeeFrac(high_fee, low_size)}; + BOOST_CHECK(replace_single_chunk->second == expected_new_diagram); + } // Conflict with the 2nd tx, resulting in new diagram with three entries - const auto replace_cpfp_child{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_high}, {entry_high})}; - BOOST_CHECK(replace_cpfp_child.has_value()); - old_diagram = replace_cpfp_child->first; - new_diagram = replace_cpfp_child->second; - BOOST_CHECK(old_diagram.size() == 2); - BOOST_CHECK(new_diagram.size() == 3); - BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0)); - BOOST_CHECK(old_diagram[1] == FeeFrac(low_fee + high_fee, low_size + high_size)); - BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0)); - BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size)); - BOOST_CHECK(new_diagram[2] == FeeFrac(low_fee + high_fee, low_size + low_size)); + { + const auto replace_cpfp_child{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_high}, {entry_high})}; + BOOST_CHECK(replace_cpfp_child.has_value()); + std::vector expected_old_diagram{FeeFrac(0, 0), FeeFrac(low_fee + high_fee, low_size + high_size)}; + BOOST_CHECK(replace_cpfp_child->first == expected_old_diagram); + std::vector expected_new_diagram{FeeFrac(0, 0), FeeFrac(high_fee, low_size), FeeFrac(low_fee + high_fee, low_size + low_size)}; + BOOST_CHECK(replace_cpfp_child->second == expected_new_diagram); + } // third transaction causes the topology check to fail const auto normal_tx = make_tx(/*inputs=*/ {high_tx}, /*output_values=*/ {995 * CENT}); @@ -482,11 +471,11 @@ BOOST_FIXTURE_TEST_CASE(calc_feerate_diagram_rbf, TestChain100Setup) const auto entry_normal = pool.GetIter(normal_tx->GetHash()).value(); const auto normal_size = entry_normal->GetTxSize(); - const auto replace_too_large{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/normal_fee, /*replacement_vsize=*/normal_size, {entry_low}, {entry_low, entry_high, entry_normal})}; - BOOST_CHECK(!replace_too_large.has_value()); - BOOST_CHECK_EQUAL(util::ErrorString(replace_too_large).original, strprintf("%s has 2 descendants, max 1 allowed", low_tx->GetHash().GetHex())); - old_diagram.clear(); - new_diagram.clear(); + { + const auto replace_too_large{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/normal_fee, /*replacement_vsize=*/normal_size, {entry_low}, {entry_low, entry_high, entry_normal})}; + BOOST_CHECK(!replace_too_large.has_value()); + BOOST_CHECK_EQUAL(util::ErrorString(replace_too_large).original, strprintf("%s has 2 descendants, max 1 allowed", low_tx->GetHash().GetHex())); + } // Make a size 2 cluster that is itself two chunks; evict both txns const auto high_tx_2 = make_tx(/*inputs=*/ {m_coinbase_txns[1]}, /*output_values=*/ {10 * COIN}); @@ -499,17 +488,14 @@ BOOST_FIXTURE_TEST_CASE(calc_feerate_diagram_rbf, TestChain100Setup) const auto entry_low_2 = pool.GetIter(low_tx_2->GetHash()).value(); const auto low_size_2 = entry_low_2->GetTxSize(); - const auto replace_two_chunks_single_cluster{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_high_2}, {entry_high_2, entry_low_2})}; - BOOST_CHECK(replace_two_chunks_single_cluster.has_value()); - old_diagram = replace_two_chunks_single_cluster->first; - new_diagram = replace_two_chunks_single_cluster->second; - BOOST_CHECK(old_diagram.size() == 3); - BOOST_CHECK(new_diagram.size() == 2); - BOOST_CHECK(old_diagram[0] == FeeFrac(0, 0)); - BOOST_CHECK(old_diagram[1] == FeeFrac(high_fee, high_size_2)); - BOOST_CHECK(old_diagram[2] == FeeFrac(low_fee + high_fee, low_size_2 + high_size_2)); - BOOST_CHECK(new_diagram[0] == FeeFrac(0, 0)); - BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size_2)); + { + const auto replace_two_chunks_single_cluster{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {entry_high_2}, {entry_high_2, entry_low_2})}; + BOOST_CHECK(replace_two_chunks_single_cluster.has_value()); + std::vector expected_old_diagram{FeeFrac(0, 0), FeeFrac(high_fee, high_size_2), FeeFrac(low_fee + high_fee, low_size_2 + high_size_2)}; + BOOST_CHECK(replace_two_chunks_single_cluster->first == expected_old_diagram); + std::vector expected_new_diagram{FeeFrac(0, 0), FeeFrac(high_fee, low_size_2)}; + BOOST_CHECK(replace_two_chunks_single_cluster->second == expected_new_diagram); + } // You can have more than two direct conflicts if the there are multiple effected clusters, all of size 2 or less const auto conflict_1 = make_tx(/*inputs=*/ {m_coinbase_txns[2]}, /*output_values=*/ {10 * COIN}); @@ -524,40 +510,37 @@ BOOST_FIXTURE_TEST_CASE(calc_feerate_diagram_rbf, TestChain100Setup) pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_3)); const auto conflict_3_entry = pool.GetIter(conflict_3->GetHash()).value(); - const auto replace_multiple_clusters{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_entry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry})}; - - BOOST_CHECK(replace_multiple_clusters.has_value()); - old_diagram = replace_multiple_clusters->first; - new_diagram = replace_multiple_clusters->second; - BOOST_CHECK(old_diagram.size() == 4); - BOOST_CHECK(new_diagram.size() == 2); + { + const auto replace_multiple_clusters{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_entry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry})}; + BOOST_CHECK(replace_multiple_clusters.has_value()); + BOOST_CHECK(replace_multiple_clusters->first.size() == 4); + BOOST_CHECK(replace_multiple_clusters->second.size() == 2); + } // Add a child transaction to conflict_1 and make it cluster size 2, still one chunk due to same feerate const auto conflict_1_child = make_tx(/*inputs=*/{conflict_1}, /*output_values=*/ {995 * CENT}); pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_1_child)); const auto conflict_1_child_entry = pool.GetIter(conflict_1_child->GetHash()).value(); - const auto replace_multiple_clusters_2{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_entry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry, conflict_1_child_entry})}; + { + const auto replace_multiple_clusters_2{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_entry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry, conflict_1_child_entry})}; - BOOST_CHECK(replace_multiple_clusters_2.has_value()); - old_diagram = replace_multiple_clusters_2->first; - new_diagram = replace_multiple_clusters_2->second; - BOOST_CHECK(old_diagram.size() == 4); - BOOST_CHECK(new_diagram.size() == 2); - old_diagram.clear(); - new_diagram.clear(); + BOOST_CHECK(replace_multiple_clusters_2.has_value()); + BOOST_CHECK(replace_multiple_clusters_2->first.size() == 4); + BOOST_CHECK(replace_multiple_clusters_2->second.size() == 2); + } // Add another descendant to conflict_1, making the cluster size > 2 should fail at this point. const auto conflict_1_grand_child = make_tx(/*inputs=*/{conflict_1_child}, /*output_values=*/ {995 * CENT}); pool.addUnchecked(entry.Fee(high_fee).FromTx(conflict_1_grand_child)); const auto conflict_1_grand_child_entry = pool.GetIter(conflict_1_child->GetHash()).value(); - const auto replace_cluster_size_3{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_entry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry, conflict_1_child_entry, conflict_1_grand_child_entry})}; + { + const auto replace_cluster_size_3{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_entry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry, conflict_1_child_entry, conflict_1_grand_child_entry})}; - BOOST_CHECK(!replace_cluster_size_3.has_value()); - BOOST_CHECK_EQUAL(util::ErrorString(replace_cluster_size_3).original, strprintf("%s has 2 descendants, max 1 allowed", conflict_1->GetHash().GetHex())); - BOOST_CHECK(old_diagram.empty()); - BOOST_CHECK(new_diagram.empty()); + BOOST_CHECK(!replace_cluster_size_3.has_value()); + BOOST_CHECK_EQUAL(util::ErrorString(replace_cluster_size_3).original, strprintf("%s has 2 descendants, max 1 allowed", conflict_1->GetHash().GetHex())); + } } BOOST_AUTO_TEST_CASE(feerate_diagram_utilities) -- cgit v1.2.3 From c377ae9ba08150c467e8b6cfaac7865f4d31457c Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 10:48:29 -0400 Subject: unit test: improve ImprovesFeerateDiagram coverage with one less vb case --- src/test/rbf_tests.cpp | 3 +++ 1 file changed, 3 insertions(+) diff --git a/src/test/rbf_tests.cpp b/src/test/rbf_tests.cpp index a683bf84d5..992f2087f3 100644 --- a/src/test/rbf_tests.cpp +++ b/src/test/rbf_tests.cpp @@ -393,6 +393,9 @@ BOOST_FIXTURE_TEST_CASE(improves_feerate, TestChain100Setup) BOOST_CHECK(res2.value().second == "insufficient feerate: does not improve feerate diagram"); pool.PrioritiseTransaction(entry1->GetSharedTx()->GetHash(), /*nFeeDelta=*/-1); + // With one less vB it does + BOOST_CHECK(ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee, tx1_size + tx2_size - 1) == std::nullopt); + // Adding a grandchild makes the cluster size 3, which is uncalculable const auto tx3 = make_tx(/*inputs=*/ {tx2}, /*output_values=*/ {995 * CENT}); pool.addUnchecked(entry.Fee(normal_fee).FromTx(tx3)); -- cgit v1.2.3 From 2a3ada8b2181b45165608947c7c42b341d0a54dd Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 10:50:17 -0400 Subject: fuzz: finer grained ImprovesFeerateDiagram check on error result --- src/test/fuzz/rbf.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/test/fuzz/rbf.cpp b/src/test/fuzz/rbf.cpp index a3138629e2..64eceb6017 100644 --- a/src/test/fuzz/rbf.cpp +++ b/src/test/fuzz/rbf.cpp @@ -178,5 +178,5 @@ FUZZ_TARGET(package_rbf, .init = initialize_package_rbf) // If internals report error, wrapper should too auto err_tuple{ImprovesFeerateDiagram(pool, direct_conflicts, all_conflicts, replacement_fees, replacement_vsize)}; - if (!calc_results.has_value()) assert(err_tuple.has_value()); + if (!calc_results.has_value()) assert(err_tuple.value().first == DiagramCheckError::UNCALCULABLE); } -- cgit v1.2.3 From b684d82d7e093889a8dc7678c6d6605ca4cd9fa4 Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 12:01:32 -0400 Subject: fuzz: Add more invariant checks for package_rbf --- src/test/fuzz/rbf.cpp | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-) diff --git a/src/test/fuzz/rbf.cpp b/src/test/fuzz/rbf.cpp index 64eceb6017..754aff4e70 100644 --- a/src/test/fuzz/rbf.cpp +++ b/src/test/fuzz/rbf.cpp @@ -178,5 +178,16 @@ FUZZ_TARGET(package_rbf, .init = initialize_package_rbf) // If internals report error, wrapper should too auto err_tuple{ImprovesFeerateDiagram(pool, direct_conflicts, all_conflicts, replacement_fees, replacement_vsize)}; - if (!calc_results.has_value()) assert(err_tuple.value().first == DiagramCheckError::UNCALCULABLE); + if (!calc_results.has_value()) { + assert(err_tuple.value().first == DiagramCheckError::UNCALCULABLE); + } else { + // Diagram check succeeded + if (!err_tuple.has_value()) { + // New diagram's final fee should always match or exceed old diagram's + assert(calc_results->first.back().fee <= calc_results->second.back().fee); + } else if (calc_results->first.back().fee > calc_results->second.back().fee) { + // Or it failed, and if old diagram had higher fees, it should be a failure + assert(err_tuple.value().first == DiagramCheckError::FAILURE); + } + } } -- cgit v1.2.3 From d9391ec0952920bdbb10d3f6e9e706e85f717ec0 Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 12:04:53 -0400 Subject: CalculateFeerateDiagramsForRBF: remove size tie-breaking from chunking conflicts --- src/test/rbf_tests.cpp | 4 ++-- src/txmempool.cpp | 2 +- 2 files changed, 3 insertions(+), 3 deletions(-) diff --git a/src/test/rbf_tests.cpp b/src/test/rbf_tests.cpp index 992f2087f3..c3ece99925 100644 --- a/src/test/rbf_tests.cpp +++ b/src/test/rbf_tests.cpp @@ -520,7 +520,7 @@ BOOST_FIXTURE_TEST_CASE(calc_feerate_diagram_rbf, TestChain100Setup) BOOST_CHECK(replace_multiple_clusters->second.size() == 2); } - // Add a child transaction to conflict_1 and make it cluster size 2, still one chunk due to same feerate + // Add a child transaction to conflict_1 and make it cluster size 2, two chunks due to same feerate const auto conflict_1_child = make_tx(/*inputs=*/{conflict_1}, /*output_values=*/ {995 * CENT}); pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_1_child)); const auto conflict_1_child_entry = pool.GetIter(conflict_1_child->GetHash()).value(); @@ -529,7 +529,7 @@ BOOST_FIXTURE_TEST_CASE(calc_feerate_diagram_rbf, TestChain100Setup) const auto replace_multiple_clusters_2{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_entry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry, conflict_1_child_entry})}; BOOST_CHECK(replace_multiple_clusters_2.has_value()); - BOOST_CHECK(replace_multiple_clusters_2->first.size() == 4); + BOOST_CHECK(replace_multiple_clusters_2->first.size() == 5); BOOST_CHECK(replace_multiple_clusters_2->second.size() == 2); } diff --git a/src/txmempool.cpp b/src/txmempool.cpp index 4047ceda3c..9adad694a9 100644 --- a/src/txmempool.cpp +++ b/src/txmempool.cpp @@ -1317,7 +1317,7 @@ util::Result, std::vector>> CTxMemPool:: // We'll add chunks for either the ancestor by itself and this tx // by itself, or for a combined package. FeeFrac package{txiter->GetModFeesWithAncestors(), static_cast(txiter->GetSizeWithAncestors())}; - if (individual > package) { + if (individual >> package) { // The individual feerate is higher than the package, and // therefore higher than the parent's fee. Chunk these // together. -- cgit v1.2.3 From 890cb015f3b99c4f2f57a1bbc69e5cf2045c2739 Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 12:08:48 -0400 Subject: s/effected/affected/ --- src/test/rbf_tests.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/test/rbf_tests.cpp b/src/test/rbf_tests.cpp index c3ece99925..88f1b34284 100644 --- a/src/test/rbf_tests.cpp +++ b/src/test/rbf_tests.cpp @@ -500,7 +500,7 @@ BOOST_FIXTURE_TEST_CASE(calc_feerate_diagram_rbf, TestChain100Setup) BOOST_CHECK(replace_two_chunks_single_cluster->second == expected_new_diagram); } - // You can have more than two direct conflicts if the there are multiple effected clusters, all of size 2 or less + // You can have more than two direct conflicts if the there are multiple affected clusters, all of size 2 or less const auto conflict_1 = make_tx(/*inputs=*/ {m_coinbase_txns[2]}, /*output_values=*/ {10 * COIN}); pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_1)); const auto conflict_1_entry = pool.GetIter(conflict_1->GetHash()).value(); -- cgit v1.2.3 From a0376e106182075634e50c14da00e84b4069b985 Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 12:09:47 -0400 Subject: unit test: clarify unstated assumption for calc_feerate_diagram_rbf chunking --- src/test/rbf_tests.cpp | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/src/test/rbf_tests.cpp b/src/test/rbf_tests.cpp index 88f1b34284..ed33969710 100644 --- a/src/test/rbf_tests.cpp +++ b/src/test/rbf_tests.cpp @@ -416,7 +416,8 @@ BOOST_FIXTURE_TEST_CASE(calc_feerate_diagram_rbf, TestChain100Setup) const CAmount normal_fee{CENT/10}; const CAmount high_fee{CENT}; - // low -> high -> medium fee transactions that would result in two chunks together + // low -> high -> medium fee transactions that would result in two chunks together since they + // are all same size const auto low_tx = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {10 * COIN}); pool.addUnchecked(entry.Fee(low_fee).FromTx(low_tx)); -- cgit v1.2.3 From cebcced65e8fdbd54893d4852d5ed6b85a8b0c45 Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Mon, 25 Mar 2024 12:11:18 -0400 Subject: remove erroneous CompareFeerateDiagram comment about slope --- src/util/feefrac.cpp | 1 - 1 file changed, 1 deletion(-) diff --git a/src/util/feefrac.cpp b/src/util/feefrac.cpp index a271fe585e..215498f287 100644 --- a/src/util/feefrac.cpp +++ b/src/util/feefrac.cpp @@ -53,7 +53,6 @@ std::partial_ordering CompareFeerateDiagram(Span dia0, Span 0); std::weak_ordering cmp = std::weak_ordering::equivalent; -- cgit v1.2.3 From a9d42b9aa579f54922ffd17fdeb61e704539b92c Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Tue, 26 Mar 2024 08:41:06 -0400 Subject: CompareFeerateDiagram: short-circuit comparison when detected as incomparable --- src/util/feefrac.cpp | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/src/util/feefrac.cpp b/src/util/feefrac.cpp index 215498f287..68fb836936 100644 --- a/src/util/feefrac.cpp +++ b/src/util/feefrac.cpp @@ -76,10 +76,12 @@ std::partial_ordering CompareFeerateDiagram(Span dia0, Span better_somewhere[1]; } -- cgit v1.2.3 From ee1b9b231a0a7e89b77cbf8ea54e0534f0970dd0 Mon Sep 17 00:00:00 2001 From: Greg Sanders Date: Tue, 26 Mar 2024 08:42:20 -0400 Subject: CalculateFeerateDiagramsForRBF: update misleading description of old diagram contents --- src/txmempool.cpp | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/src/txmempool.cpp b/src/txmempool.cpp index 9adad694a9..82eec6241f 100644 --- a/src/txmempool.cpp +++ b/src/txmempool.cpp @@ -1294,9 +1294,10 @@ util::Result, std::vector>> CTxMemPool:: // direct_conflicts that is at its own fee/size, along with the replacement // tx/package at its own fee/size - // old diagram will consist of each element of all_conflicts either at - // its own feerate (followed by any descendant at its own feerate) or as a - // single chunk at its descendant's ancestor feerate. + // old diagram will consist of the ancestors and descendants of each element of + // all_conflicts. every such transaction will either be at its own feerate (followed + // by any descendant at its own feerate), or as a single chunk at the descendant's + // ancestor feerate. std::vector old_chunks; // Step 1: build the old diagram. -- cgit v1.2.3