descriptor: Add proper Clone function to miniscript::Node

achow101 commented at 7:52 pm on September 10, 2024: member

Multipath descriptors requires performing a deep copy, so a Clone function that does that is added to miniscript::Node instead of the current shallow copy.

Fixes #30864

DrahtBot commented at 7:52 pm on September 10, 2024: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/30866.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	darosior

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

DrahtBot added the label CI failed on Sep 11, 2024

DrahtBot commented at 9:28 am on September 11, 2024: contributor

🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/29955732210

Make sure to run all tests locally, according to the documentation.

The failure may happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

fanquake requested review from darosior on Sep 12, 2024

fanquake commented at 3:12 pm on September 12, 2024: member

https://github.com/bitcoin/bitcoin/pull/30866/checks?check_run_id=29955732214:

0In file included from /ci_container_base/src/script/descriptor.cpp:10:
1/ci_container_base/src/script/miniscript.h: In instantiation of ‘miniscript::Node<Key> miniscript::Node<Key>::Clone() const [with Key = unsigned int]’:
2/ci_container_base/src/script/descriptor.cpp:1363:124:   required from here
3/ci_container_base/src/script/miniscript.h:535:33: error: moving a local object in a return statement prevents copy elision [-Werror=pessimizing-move]
4  535 |             return std::move(ret);
5      |                                 ^
6/ci_container_base/src/script/miniscript.h:535:33: note: remove ‘std::move’ call
7cc1plus: all warnings being treated as errors

achow101 force-pushed on Sep 12, 2024

DrahtBot removed the label CI failed on Sep 15, 2024

in src/script/descriptor.cpp:1363 in c343af67a8 outdated

1359@@ -1360,7 +1360,7 @@ class MiniscriptDescriptor final : public DescriptorImpl
1360         for (const auto& arg : m_pubkey_args) {
1361             providers.push_back(arg->Clone());
1362         }
1363-        return std::make_unique<MiniscriptDescriptor>(std::move(providers), miniscript::MakeNodeRef<uint32_t>(*m_node));
1364+        return std::make_unique<MiniscriptDescriptor>(std::move(providers), miniscript::MakeNodeRef<uint32_t>(m_node->Clone()));

hodlinator commented at 10:11 pm on October 4, 2024:

The PR description asserts:

Multipath descriptors requires performing a deep copy

Would be happy if you cared to add an elaboration on why that is.

It seemed to me like it should be safe to just have another shared_ptr point to the same const Node. Unless something on the outside could own a non-const reference into the node hierarchy and mutate it that way? In that case maybe it would be more robust for the MiniscriptDescriptor-ctor to be the one ensuring it holds a unique reference by doing the node->Clone() there instead (if .use_count() > 1).

Was able to avoid the crash in #30864 using only this on top of the parent commit of this PR:

0        return std::make_unique<MiniscriptDescriptor>(std::move(providers), m_node);

Probably causes other bugs that are obvious for those who understand more of the context. Change passes both unit and non-extended functional tests though.

achow101 commented at 11:53 pm on October 4, 2024:

It’s not strictly necessary but I decided to do it this way to follow the pattern used for all other descriptors. The multipath expanded descriptors are treated as separate descriptors everywhere, and doing a deep copy retains that behavior which will allow for future changes that may modify specific descriptors.

hodlinator commented at 7:51 pm on October 5, 2024:

How come the shallow copy in the version before the PR is causing a problem in this case though?

It seems the default-generated copy-ctor for Node used before was somehow ending up with corrupt/leaked data, but I’ve been unable to spot what it is. Can’t see any slicing going on. Is something funky being done to the shared_ptrs?

Regardless, it might be worth adding:

0    Node(const Node&) = delete;
1    Node(Node&&) = delete;
2    Node& operator=(const Node&) = delete;
3    Node& operator=(Node&&) = delete;

achow101 commented at 10:05 am on October 16, 2024:

Not entirely sure either.

darosior commented at 5:01 pm on November 6, 2024:

The shallow copy in the version before this PR is causing a problem because we mess with a Node’s subs in the destructor to avoid a recursion stack overflow: https://github.com/bitcoin/bitcoin/blob/2c90f8e08c4cf44d4c1ef3dde0e7f7991b8b9390/src/script/miniscript.h#L513-L524

In the scriptpubkeyman fuzz target using the seed from #30864 we would Parse the tr(%17/<2;3>,l:pk(%08)) multipath descriptor into a parsed_descs vector of 2 Descriptor pointers. We would use the first of those descriptors (tr(xpub..../2,l:pk(4bdf....))#jmgpm0u8) and move it into a WalletDescriptor. When exiting the CreateWalletDescriptor function the parsed_descs vector would be destructed, along with the second Descriptor pointer it contains. The destructor of the Node (l:pk(xpub...)) it contains would in turn be called, moving out all its subs that are also pointed to by the first Descriptor’s Node. As soon as you try to perform an operation on it it will try to access moved structures.

DrahtBot added the label CI failed on Oct 22, 2024

achow101 force-pushed on Oct 24, 2024

DrahtBot removed the label CI failed on Oct 25, 2024

darosior commented at 5:02 pm on November 6, 2024: member

Concept ACK.

darosior commented at 4:12 pm on November 7, 2024: member

I wrote a regression unit test for this: https://github.com/darosior/bitcoin/commit/d23ffe08ef42475dcd40a13857cd775ac98e0270. It’s failing on master but also on this PR. Curiously i had to introduce a new test case with a descriptor close to the one from the fuzzer input as the test is not failing on the existing multipath miniscript descriptor.

in src/script/miniscript.h:538 in 12e2550622 outdated

533+                ret.subs.push_back(MakeNodeRef<Key>(sub));
534+            }
535+            return ret;
536+        };
537+        return TreeEval<Node<Key>>(upfn);
538+    }

darosior commented at 10:14 pm on November 7, 2024:

More smartpointy less segfaulty:

 0diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
 1index 6053c853bb..b099fdfc3f 100644
 2--- a/src/script/descriptor.cpp
 3+++ b/src/script/descriptor.cpp
 4@@ -1360,7 +1360,7 @@ public:
 5         for (const auto& arg : m_pubkey_args) {
 6             providers.push_back(arg->Clone());
 7         }
 8-        return std::make_unique<MiniscriptDescriptor>(std::move(providers), miniscript::MakeNodeRef<uint32_t>(m_node->Clone()));
 9+        return std::make_unique<MiniscriptDescriptor>(std::move(providers), m_node->Clone());
10     }
11 };
12 
13diff --git a/src/script/miniscript.h b/src/script/miniscript.h
14index a74e312e79..1472c9ac4f 100644
15--- a/src/script/miniscript.h
16+++ b/src/script/miniscript.h
17@@ -523,18 +523,18 @@ struct Node {
18         }
19     }
20 
21-    Node<Key> Clone() const
22+    NodeRef<Key> Clone() const
23     {
24         // Use TreeEval() to avoid a stack-overflow due to recursion
25-        auto upfn = [](const Node& node, Span<Node> subs) {
26-            Node<Key> ret(node);
27-            ret.subs.clear();
28+        auto upfn = [](const Node& node, Span<NodeRef<Key>> subs) {
29+            auto ret(MakeNodeRef<Key>(node));
30+            ret->subs.clear();
31             for (const auto& sub : subs) {
32-                ret.subs.push_back(MakeNodeRef<Key>(sub));
33+                ret->subs.push_back(sub);
34             }
35             return ret;
36         };
37-        return TreeEval<Node<Key>>(upfn);
38+        return TreeEval<NodeRef<Key>>(upfn);
39     }
40 
41 private:

achow101 commented at 10:20 pm on November 7, 2024:

Thanks, taken.

achow101 force-pushed on Nov 7, 2024

achow101 commented at 10:20 pm on November 7, 2024: member

I wrote a regression unit test for this: darosior@d23ffe0.

Added the test commit as well.

in src/script/miniscript.h:650 in 9178f8cf58 outdated

643@@ -630,7 +644,10 @@ struct Node {
644             // If evaluation returns std::nullopt, abort immediately.
645             if (!result) return {};
646             // Replace the last node.subs.size() elements of results with the new result.
647-            results.erase(results.end() - node.subs.size(), results.end());
648+            // Use pop_back to truncate results to avoid MoveAssignable requirement of erase().
649+            for (size_t i = 0; i < node.subs.size(); ++i) {
650+                results.pop_back();
651+            }

darosior commented at 2:32 pm on November 8, 2024:

This is not necessary anymore.

achow101 commented at 4:50 pm on November 8, 2024:

Removed

descriptor: Add proper Clone function to miniscript::Node

Multipath descriptors requires performing a deep copy, so a Clone
function that does that is added to miniscript::Node instead of the
current shallow copy.

Co-Authored-By: Antoine Poinsot <darosior@protonmail.com>

76653fec1d

qa: check parsed multipath descriptors dont share references 6a00ea17c1

achow101 force-pushed on Nov 8, 2024

darosior approved

darosior commented at 9:22 pm on November 8, 2024: member

ACK 6a00ea17c136e67a66f3558dd2d02a07860b0afe

fanquake added this to the milestone 29.0 on Nov 11, 2024

hodlinator commented at 11:53 pm on November 13, 2024: contributor

I’ve experimented with a change on top of this PR that removes shared_ptr usage from src/script/ altogether in order to clarify ownership.

My change is in 80fca845b5f28677207a8fea4a173baaef23036f. It helped uncover another place where the node needs to be cloned (at the bottom of the outer loop):

 0diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
 1index b099fdfc3f..f0294df72a 100644
 2--- a/src/script/descriptor.cpp
 3+++ b/src/script/descriptor.cpp
 4@@ -2154,7 +2154,7 @@ std::vector<std::unique_ptr<DescriptorImpl>> ParseScript(uint32_t& key_exp_index
 5                 for (auto& pub : parser.m_keys) {
 6                     pubs.emplace_back(std::move(pub.at(i)));
 7                 }
 8-                ret.emplace_back(std::make_unique<MiniscriptDescriptor>(std::move(pubs), node));
 9+                ret.emplace_back(std::make_unique<MiniscriptDescriptor>(std::move(pubs), node->Clone()));
10             }
11             return ret;
12         }

It would be preferable to add that one-line fix to this PR, but I’m also interested to hear if there is any chance of my shared_ptr-removal getting any review as a separate PR. I understand Wallet needs more review of existing PRs, so I’m open to leaving it as draft for a while.

achow101 commented at 0:37 am on November 14, 2024: member

My change is in 80fca84. It helped uncover another place where the node needs to be cloned (at the bottom of the outer loop):

Good catch, added that.

Do you have a particular test case that triggered there?

hodlinator commented at 1:42 pm on November 14, 2024: contributor

Do you have a particular test case that triggered there?

Worked through several iterations of the shared_ptr-removal over a couple of days, at some point I had:

0ret.emplace_back(std::make_unique<MiniscriptDescriptor>(std::move(pubs), std::move(*node)));

‘cause I wasn’t paying attention to the statement being inside a loop. The second descriptor created in the loop ended up with already-moved-from values, which resulted in an this test failing:

https://github.com/bitcoin/bitcoin/blob/6a00ea17c136e67a66f3558dd2d02a07860b0afe/src/test/descriptor_tests.cpp#L799-L823

An OR_D node we were trying to convert into a string was failing because subs was empty (already moved away from).

descriptor: Add proper Clone function to miniscript::Node #30866

Code Coverage & Benchmarks

Reviews