-
Notifications
You must be signed in to change notification settings - Fork 38.7k
test: Increase stack size for "Debug" builds with MSVC #32349
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Conversation
This change accommodates the deep recursion in the `FindChallenges()` function used in `test/miniscript_tests.cpp`.
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. Code Coverage & BenchmarksFor details see: https://corecheck.dev/bitcoin/bitcoin/pulls/32349. ReviewsSee the guideline for information on the review process. ConflictsNo conflicts as of last run. |
| target_link_options(core_interface INTERFACE | ||
| # Increase stack size to accommodate the deep recursion | ||
| # in the FindChallenges() function used in miniscript_tests. | ||
| $<$<CONFIG:Debug>:/STACK:2097152> |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Where does this reserve value come from?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Determined empirically—this value was found to be sufficient during testing.
|
I'm not against increasing the Windows stack depth, but the underlying problem may be that we're ignoring warnings such as
diff --git a/src/test/miniscript_tests.cpp b/src/test/miniscript_tests.cpp
index f253562a2f..14ac44e2c6 100644
--- a/src/test/miniscript_tests.cpp
+++ b/src/test/miniscript_tests.cpp
@@ -323,6 +323,35 @@ std::set<Challenge> FindChallenges(const NodeRef& ref) {
return chal;
}
+std::set<Challenge> FindChallenges_no_recursion(const NodeRef& root)
+{
+ std::set<Challenge> chal;
+ std::vector<const Node*> stack;
+ stack.push_back(root.get());
+
+ while (!stack.empty()) {
+ const Node* ref{stack.back()};
+ stack.pop_back();
+
+ for (const auto& key : ref->keys) {
+ chal.emplace(ChallengeType::PK, ChallengeNumber(key));
+ }
+ switch (ref->fragment) {
+ case Fragment::OLDER: chal.emplace(ChallengeType::OLDER, ref->k); break;
+ case Fragment::AFTER: chal.emplace(ChallengeType::AFTER, ref->k); break;
+ case Fragment::SHA256: chal.emplace(ChallengeType::SHA256, ChallengeNumber(ref->data)); break;
+ case Fragment::RIPEMD160: chal.emplace(ChallengeType::RIPEMD160, ChallengeNumber(ref->data)); break;
+ case Fragment::HASH256: chal.emplace(ChallengeType::HASH256, ChallengeNumber(ref->data)); break;
+ case Fragment::HASH160: chal.emplace(ChallengeType::HASH160, ChallengeNumber(ref->data)); break;
+ default: break;
+ }
+ for (const auto& sub : ref->subs) {
+ stack.push_back(sub.get());
+ }
+ }
+ return chal;
+}
+
//! The spk for this script under the given context. If it's a Taproot output also record the spend data.
CScript ScriptPubKey(miniscript::MiniscriptContext ctx, const CScript& script, TaprootBuilder& builder)
{
@@ -348,6 +377,8 @@ struct MiniScriptTest : BasicTestingSetup {
void TestSatisfy(const KeyConverter& converter, const std::string& testcase, const NodeRef& node) {
auto script = node->ToScript(converter);
auto challenges = FindChallenges(node); // Find all challenges in the generated miniscript.
+ auto challenges_no_recursion = FindChallenges_no_recursion(node); // Find all challenges in the generated miniscript.
+ BOOST_CHECK(std::vector{challenges} == std::vector{challenges_no_recursion});
std::vector<Challenge> challist(challenges.begin(), challenges.end());
for (int iter = 0; iter < 3; ++iter) {
std::shuffle(challist.begin(), challist.end(), m_rng); |
|
|
That sounds sensible, can you open a PR with this patch and tag me? |
|
Closing in favour of #32351. |
The original recursive `FindChallenges` explores the Miniscript node tree using depth-first search. Specifically, it performs a pre-order traversal (processing the node's data, then recursively visiting children from left-to-right). This recursion uses the call stack, which can lead to stack overflows on platforms with limited stack space, particularly noticeable in Windows debug builds. This change replaces the recursive implementation with an iterative version using an explicit stack. The iterative version also performs a depth-first search and processes the node's data before exploring children (preserving pre-order characteristics), although the children are explored in right-to-left order due to the LIFO nature of the explicit stack. Critically, both versions collect challenges into a `std::set`, which automatically deduplicates and sorts elements. This ensures that not only the final result, but the actual state of the set at any equivalent point in traversal remains identical, despite the difference in insertion order. This iterative approach is an alternative to increasing the default stack size (as proposed in bitcoin#32349) and directly addresses the stack overflow issue reported in bitcoin#32341 by avoiding deep recursion. The change is done in two commits: * add a new iterative `FindChallenges` method and rename the old method to `*_recursive` (to simplify removal in the next commit), asserting that its result matches the original; * Remove the original recursive implementation. This approach avoids needing to suppress `misc-no-recursion` warnings and provides a portable, low-risk fix. Using a `std::set` is necessary for deduplication, matching the original function's behavior. An experiment using an `std::vector` showed duplicate challenges being added, confirming the need for the set: Example failure with vector: Recursive (set): (6, 9070746) (6, 19532513) (6, 3343376967) Iterative (vector attempt): (6, 19532513) (6, 9070746) (6, 3343376967) (6, 9070746) // Duplicate Co-authored-by: Hennadii Stepanov <32963518+hebasto@users.noreply.github.com>
…al iteration 7e8ef95 refactor: Fix Sonar rule `cpp:S4998` - avoid unique_ptr const& as parameter (Lőrinc) e400ac5 refactor: simplify repeated comparisons in `FindChallenges` (Lőrinc) f670836 test: remove old recursive `FindChallenges_recursive` implementation (Lőrinc) b80d0bd test: avoid stack overflow in `FindChallenges` via manual iteration (Lőrinc) Pull request description: `FindChallenges` explores the `Miniscript` node tree by going deep into the first child's subtree, then the second, and so on - effectively performing a pre-order Traversal (Depth-First Search) recursively, using the call stack which can result in stack overflows on Windows debug builds. This change replaces the recursive implementation with an iterative version using an explicit stack. The new implementation also performs a pre-order depth-first traversal, though it processes children in right-to-left order (rather than left-to-right) due to the LIFO nature of the stack. Since both versions store results in a `std::set`, which automatically sorts and deduplicates elements, the exact traversal order doesn't affect the final result. It is an alternative to increasing the Windows stack size, as proposed in #32349, and addresses the issue raised in #32341 by avoiding deep recursion altogether. The change is done in two commits: * add a new iterative `FindChallenges` method and rename the old method to `*_recursive` (to simplify the next commit where we remove it), asserting that its result matches the original; * remove the original recursive implementation. This approach avoids ignoring the `misc-no-recursion` warning as well. I tried modifying the new method to store results in a vector instead, but it demonstrated that the deduplication provided by `std::set` was necessary. One example showing the need for deduplication: Recursive (using set): ``` (6, 9070746) (6, 19532513) (6, 3343376967) ``` Iterative (using vector attempt): ``` (6, 19532513) (6, 9070746) (6, 3343376967) (6, 9070746) // Duplicate entry ``` The performance of the test is the same as before, with the recursive method. Fixes #32341 ACKs for top commit: achow101: ACK 7e8ef95 sipa: utACK 7e8ef95 hodlinator: re-ACK 7e8ef95 Tree-SHA512: 9e52eff82a7d76f5d37e3b74c508f08e5fced5386dad504bed111b27ed2b529008a6dd12a5116f009609a94c7ee7ebe3e80a759dda55dd1cb3ae52078f65ec71
The original recursive `FindChallenges` explores the Miniscript node tree using depth-first search. Specifically, it performs a pre-order traversal (processing the node's data, then recursively visiting children from left-to-right). This recursion uses the call stack, which can lead to stack overflows on platforms with limited stack space, particularly noticeable in Windows debug builds. This change replaces the recursive implementation with an iterative version using an explicit stack. The iterative version also performs a depth-first search and processes the node's data before exploring children (preserving pre-order characteristics), although the children are explored in right-to-left order due to the LIFO nature of the explicit stack. Critically, both versions collect challenges into a `std::set`, which automatically deduplicates and sorts elements. This ensures that not only the final result, but the actual state of the set at any equivalent point in traversal remains identical, despite the difference in insertion order. This iterative approach is an alternative to increasing the default stack size (as proposed in bitcoin#32349) and directly addresses the stack overflow issue reported in bitcoin#32341 by avoiding deep recursion. The change is done in two commits: * add a new iterative `FindChallenges` method and rename the old method to `*_recursive` (to simplify removal in the next commit), asserting that its result matches the original; * Remove the original recursive implementation. This approach avoids needing to suppress `misc-no-recursion` warnings and provides a portable, low-risk fix. Using a `std::set` is necessary for deduplication, matching the original function's behavior. An experiment using an `std::vector` showed duplicate challenges being added, confirming the need for the set: Example failure with vector: Recursive (set): (6, 9070746) (6, 19532513) (6, 3343376967) Iterative (vector attempt): (6, 19532513) (6, 9070746) (6, 3343376967) (6, 9070746) // Duplicate Co-authored-by: Hennadii Stepanov <32963518+hebasto@users.noreply.github.com> Github-Pull: bitcoin#32351 Rebased-From: b80d0bd
This PR accommodates the deep recursion in the
FindChallenges()function used intest/miniscript_tests.cpp.Fixes #32341 (comment).
CI log: https://github.com/hebasto/bitcoin/actions/runs/14664806617/job/41156972137