Binarization can produce stack overflows

[Krzmbrzl]

Since binarization uses recursion, this can (and does under some circumstances) produce stack overflows. We'll want to replace the recursive implementation with a loop-based one.

[Krzmbrzl]

Obviously, this only appears with very long expressions (for me df-icMRCC2-LR) but interestingly only with -O3 with GCC 14.2. With -O2 it's fine… I suppose this is the point where I should add that I am not 100% sure that this really is a stack overflow (I couldn't run e.g. valgrind on the problem) but it surely does look like it to me (the crash happens with a backtrace that is > 14k levels of nesting of binarize).

[evaleev]

Does it go away if you increase the stack size manualy?

[Krzmbrzl]

Will have to try that… Interestingly, this issue does not seem to occur on my PC at university. Weird 🤔

[Krzmbrzl]

Never mind - using sanitizers I was able to reproduce the issue with Clang, which now definitely confirms that this is a stack-overflow. Increasing the stack size via ulimit -s makes the problem go away. However, I think the real solution would still be to get rid of the recursive implementation instead.

==36912==ERROR: AddressSanitizer: stack-overflow on address 0x7ffdf0f20ff8 (pc 0x641b680c7c54 bp 0x641b69366148 sp 0x7ffdf0f21000 T0)
    #0 0x641b680c7c54 in __asan::Allocator::Allocate(unsigned long, unsigned long, __sanitizer::BufferedStackTrace*, __asan::AllocType, bool) (/home/adam/Documents/Git/SeQuant/build/external_interface+0x475c54) (BuildId: 76ede3217143cf53ee38c644243e97af42d27bd7)
    #1 0x641b680c8997 in __asan::asan_memalign(unsigned long, unsigned long, __sanitizer::BufferedStackTrace*, __asan::AllocType) (/home/adam/Documents/Git/SeQuant/build/external_interface+0x476997) (BuildId: 76ede3217143cf53ee38c644243e97af42d27bd7)
    #2 0x641b6819eb08 in operator new(unsigned long) (/home/adam/Documents/Git/SeQuant/build/external_interface+0x54cb08) (BuildId: 76ede3217143cf53ee38c644243e97af42d27bd7)
    #3 0x641b68254a5c in std::__new_allocator<sequant::Index>::allocate(unsigned long, void const*) /usr/bin/../lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/bits/new_allocator.h:151:27
    #4 0x641b68254a5c in std::allocator<sequant::Index>::allocate(unsigned long) /usr/bin/../lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/bits/allocator.h:196:32
    #5 0x641b68254a5c in std::allocator_traits<std::allocator<sequant::Index>>::allocate(std::allocator<sequant::Index>&, unsigned long) /usr/bin/../lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/bits/alloc_traits.h:478:20
    #6 0x641b68254a5c in std::_Vector_base<sequant::Index, std::allocator<sequant::Index>>::_M_allocate(unsigned long) /usr/bin/../lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/bits/stl_vector.h:380:20
    #7 0x641b68254a5c in std::_Vector_base<sequant::Index, std::allocator<sequant::Index>>::_M_create_storage(unsigned long) /usr/bin/../lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/bits/stl_vector.h:398:33
    #8 0x641b6858b2c1 in std::_Vector_base<sequant::Index, std::allocator<sequant::Index>>::_Vector_base(unsigned long, std::allocator<sequant::Index> const&) /usr/bin/../lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/bits/stl_vector.h:334:9
    #9 0x641b6858b2c1 in std::vector<sequant::Index, std::allocator<sequant::Index>>::vector(std::vector<sequant::Index, std::allocator<sequant::Index>> const&) /usr/bin/../lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/bits/stl_vector.h:602:9
    #10 0x641b6858b2c1 in sequant::EvalExpr::EvalExpr(sequant::EvalExpr const&) /home/adam/Documents/Git/SeQuant/SeQuant/core/eval_expr.hpp:54:7
    #11 0x641b6858b2c1 in sequant::ExportExpr::ExportExpr(sequant::EvalExpr const&) /home/adam/Documents/Git/SeQuant/SeQuant/core/export/export_expr.cpp:17:49
    #12 0x641b68374ee1 in auto sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&)::operator()<sequant::EvalExpr const&>(T&&) const /home/adam/Documents/Git/SeQuant/SeQuant/core/eval_expr.hpp:373:49
    #13 0x641b68374ee1 in auto sequant::transform_node<sequant::EvalExpr, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&), void>(sequant::FullBinaryNode<T> const&, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&)) /home/adam/Documents/Git/SeQuant/SeQuant/core/binary_node.hpp:638:27
    #14 0x641b68374efe in auto sequant::transform_node<sequant::EvalExpr, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&), void>(sequant::FullBinaryNode<T> const&, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&)) /home/adam/Documents/Git/SeQuant/SeQuant/core/binary_node.hpp:638:39
    #15 0x641b68374efe in auto sequant::transform_node<sequant::EvalExpr, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&), void>(sequant::FullBinaryNode<T> const&, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&)) /home/adam/Documents/Git/SeQuant/SeQuant/core/binary_node.hpp:638:39
    #16 0x641b68374efe in auto sequant::transform_node<sequant::EvalExpr, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&), void>(sequant::FullBinaryNode<T> const&, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&)) /home/adam/Documents/Git/SeQuant/SeQuant/core/binary_node.hpp:638:39
    #17 0x641b68374efe in auto sequant::transform_node<sequant::EvalExpr, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&), void>(sequant::FullBinaryNode<T> const&, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&)) /home/adam/Documents/Git/SeQuant/SeQuant/core/binary_node.hpp:638:39
    #18 0x641b68374efe in auto sequant::transform_node<sequant::EvalExpr, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&), void>(sequant::FullBinaryNode<T> const&, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&)) /home/adam/Documents/Git/SeQuant/SeQuant/core/binary_node.hpp:638:39
    #19 0x641b68374efe in auto sequant::transform_node<sequant::EvalExpr, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&), void>(sequant::FullBinaryNode<T> const&, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&)) /home/adam/Documents/Git/SeQuant/SeQuant/core/binary_node.hpp:638:39
    #20 0x641b68374efe in auto sequant::transform_node<sequant::EvalExpr, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&), void>(sequant::FullBinaryNode<T> const&, sequant::FullBinaryNode<T> sequant::binarize<sequant::ExportExpr>(sequant::ExprPtr const&)::'lambda'(T&&)) /home/adam/Documents/Git/SeQuant/SeQuant/core/binary_node.hpp:638:39
…

[evaleev]

amazing ... how big was the expression?

[Krzmbrzl]

I'm not entirely sure which of the expressions is crashing (didn't bother to check) but I have an expression that is a sum of 2884 individual tensor contractions (each containing about 4 tensors and a scalar factor).

I have run into a similar issue before with the visit functions, hence the existence of 3a82548

[bimalgaudel]

In production code (mpqc4), we do not binarize such Sum expressions with numerous summands into a single binary evaluation tree. Instead, we construct a vector of the trees corresponding to each summand.

[Krzmbrzl]

I need it for exporting the expression though