Segfault in `Horner_tree()` when optimizing a large polynomial

[magv]

Hi, all. I'm trying to use FORM's expression optimizer, and it crashes on some (large) expressions for me. Here's a GDB transcript:

gdb ./sources/vorm 
GNU gdb (GDB; openSUSE Leap 15.2) 10.1
[...]
(gdb) run -q formbug.frm
Starting program: ./sources/vorm -q formbug.frm

Time =       6.17 sec    Generated terms =    1581391
            EXPR         Terms in output =    1581391
                         Bytes used      =   95332332

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff6d7fc7d in __memcpy_ssse3 () from /lib64/libc.so.6
(gdb) bt
#0  0x00007ffff6d7fc7d in __memcpy_ssse3 () from /lib64/libc.so.6
#1  0x0000000000479881 in Horner_tree (expr=<optimized out>, order=std::vector of length 7, capacity 7 = {...}) at optimize.cc:872
#2  0x000000000047a028 in optimize_expression_given_Horner () at optimize.cc:4038
#3  0x000000000047c38f in Optimize (exprnr=0, do_print=do_print@entry=0) at optimize.cc:4701
#4  0x00000000004b13c6 in DoOptimize (s=<optimized out>) at pre.c:6653
#5  0x00000000004b6463 in PreProInstruction () at pre.c:1160
#6  0x00000000004b7133 in PreProcessor () at pre.c:936
#7  0x00000000004f1eb9 in main (argc=3, argv=0x7fffffffdc48) at startup.c:1621

The program in question is:

Symbols d,mt2,s12,s23,s34,s45,s51;
Local EXPR=(1010526973670375638589373164092212667719775430*mt2^8*s12^10*s34^3*s45^5*s51+<115MB polynomial>);
Format O1;
.sort
Format Mathematica;
ExtraSymbols underscore,XTMP;
#optimize EXPR
#write <formbug.frm.m> "%O"
#write <formbug.frm.m> "XRESULT=%e", EXPR
.end

Same problem with O2 optimization level. With O3 the backtrace is:

(gdb) bt
#0  0x00007ffff6d7fc7d in __memcpy_ssse3 () from /lib64/libc.so.6
#1  0x0000000000479881 in Horner_tree (expr=<optimized out>, order=std::vector of length 7, capacity 7 = {...}) at optimize.cc:872
#2  0x000000000047b4dd in try_MCTS_scheme (pnum_oper=<synthetic pointer>, scheme=std::vector of length 7, capacity 7 = {...}) at optimize.cc:1953
#3  find_Horner_MCTS_expand_tree () at optimize.cc:2029
#4  0x000000000047bda9 in find_Horner_MCTS () at optimize.cc:2278
#5  0x000000000047c2aa in Optimize (exprnr=0, do_print=do_print@entry=0) at optimize.cc:4661
#6  0x00000000004b13c6 in DoOptimize (s=<optimized out>) at pre.c:6653
#7  0x00000000004b6463 in PreProInstruction () at pre.c:1160
#8  0x00000000004b7133 in PreProcessor () at pre.c:936
#9  0x00000000004f1eb9 in main (argc=3, argv=0x7fffffffdc48) at startup.c:1621

With O4:

(gdb) bt
#0  0x00007ffff6d7fc7d in __memcpy_ssse3 () from /lib64/libc.so.6
#1  0x0000000000479881 in Horner_tree (expr=<optimized out>, order=std::vector of length 7, capacity 8 = {...}) at optimize.cc:872
#2  0x0000000000479d3e in simulated_annealing () at optimize.cc:1650
#3  0x000000000047c142 in Optimize (exprnr=0, do_print=do_print@entry=0) at optimize.cc:4650
#4  0x00000000004b13c6 in DoOptimize (s=<optimized out>) at pre.c:6653
#5  0x00000000004b6463 in PreProInstruction () at pre.c:1160
#6  0x00000000004b7133 in PreProcessor () at pre.c:936
#7  0x00000000004f1eb9 in main (argc=3, argv=0x7fffffffdc48) at startup.c:1621

The form in question identifies as "FORM 4.2.1 (Nov 10 2020, v4.2.1-30-gb0e72a8) 64-bits", even though it was built from the latest commit (b0e72a834eb5d1d057e91202201ff21013838be4). An older "FORM 4.2 (Mar 15 2019) 64-bits" also crashes similarly. Before crash at most ~3GB of memory is used. There is no form.set (but a form.set produced by formset.py -n4 -H --total-cpus=4 --total-mem=10G -p 100 shows a similar crash).

I can provide the full source file, if you want -- just tell me how. I can also provide any additional information, maybe try changing some parameters if you have some sort of ideas on what to try.

[vermaseren]

My first impression is that maybe you are running out of the WorkSpace. Giving it a sifficiently big value for the WorkSpace in the setup might do the job... I hope….

Jos

On 14 Mar 2021, at 19:54, Vitaly Magerya @.***> wrote:

Hi, all. I'm trying to use FORM's expression optimizer, and it crashes on some (large) expressions for me. Here's a GDB transcript:

gdb ./sources/vorm GNU gdb (GDB; openSUSE Leap 15.2) 10.1 [...] (gdb) run -q formbug.frm Starting program: ./sources/vorm -q formbug.frm

Time = 6.17 sec Generated terms = 1581391 EXPR Terms in output = 1581391 Bytes used = 95332332

Program received signal SIGSEGV, Segmentation fault. 0x00007ffff6d7fc7d in __memcpy_ssse3 () from /lib64/libc.so.6 (gdb) bt

0 0x00007ffff6d7fc7d in __memcpy_ssse3 () from /lib64/libc.so.6

1 0x0000000000479881 in Horner_tree (expr=, order=std::vector of length 7, capacity 7 = {...}) at optimize.cc:872

2 0x000000000047a028 in optimize_expression_given_Horner () at optimize.cc:4038

3 0x000000000047c38f in Optimize (exprnr=0, @.***=0) at optimize.cc:4701

4 0x00000000004b13c6 in DoOptimize (s=) at pre.c:6653

5 0x00000000004b6463 in PreProInstruction () at pre.c:1160

6 0x00000000004b7133 in PreProcessor () at pre.c:936

7 0x00000000004f1eb9 in main (argc=3, argv=0x7fffffffdc48) at startup.c:1621

The program in question is:

Symbols d,mt2,s12,s23,s34,s45,s51; Local EXPR=(1010526973670375638589373164092212667719775430mt2^8s12^10s34^3s45^5*s51+<115MB polynomial>); Format O1; .sort Format Mathematica; ExtraSymbols underscore,XTMP;

optimize EXPR

write "%O"

write "XRESULT=%e", EXPR

.end Same problem with O2 optimization level. With O3 the backtrace is:

(gdb) bt

0 0x00007ffff6d7fc7d in __memcpy_ssse3 () from /lib64/libc.so.6

1 0x0000000000479881 in Horner_tree (expr=, order=std::vector of length 7, capacity 7 = {...}) at optimize.cc:872

2 0x000000000047b4dd in try_MCTS_scheme (pnum_oper=, scheme=std::vector of length 7, capacity 7 = {...}) at optimize.cc:1953

3 find_Horner_MCTS_expand_tree () at optimize.cc:2029

4 0x000000000047bda9 in find_Horner_MCTS () at optimize.cc:2278

5 0x000000000047c2aa in Optimize (exprnr=0, @.***=0) at optimize.cc:4661

6 0x00000000004b13c6 in DoOptimize (s=) at pre.c:6653

7 0x00000000004b6463 in PreProInstruction () at pre.c:1160

8 0x00000000004b7133 in PreProcessor () at pre.c:936

9 0x00000000004f1eb9 in main (argc=3, argv=0x7fffffffdc48) at startup.c:1621

With O4:

(gdb) bt

0 0x00007ffff6d7fc7d in __memcpy_ssse3 () from /lib64/libc.so.6

1 0x0000000000479881 in Horner_tree (expr=, order=std::vector of length 7, capacity 8 = {...}) at optimize.cc:872

2 0x0000000000479d3e in simulated_annealing () at optimize.cc:1650

3 0x000000000047c142 in Optimize (exprnr=0, @.***=0) at optimize.cc:4650

4 0x00000000004b13c6 in DoOptimize (s=) at pre.c:6653

5 0x00000000004b6463 in PreProInstruction () at pre.c:1160

6 0x00000000004b7133 in PreProcessor () at pre.c:936

7 0x00000000004f1eb9 in main (argc=3, argv=0x7fffffffdc48) at startup.c:1621

The form in question identifies as "FORM 4.2.1 (Nov 10 2020, v4.2.1-30-gb0e72a8) 64-bits", even though it was built from the latest commit (b0e72a8 https://github.com/vermaseren/form/commit/b0e72a834eb5d1d057e91202201ff21013838be4). An older "FORM 4.2 (Mar 15 2019) 64-bits" also crashes similarly. Before crash at most ~3GB of memory is used. There is no form.set (but a form.set produced by formset.py -n4 -H --total-cpus=4 --total-mem=10G -p 100 shows a similar crash).

I can provide the full source file, if you want -- just tell me how. I can also provide any additional information, maybe try changing some parameters if you have some sort of ideas on what to try.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/vermaseren/form/issues/379, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABJPCETHEQ6NUYYJIS2OMI3TDUA7VANCNFSM4ZFIK3SA.

[magv]

Yes, increasing WorkSpace does seem to help (FORM didn't finish yet, but at least it did not immediately crash). Thanks, Jos. Is there a way to predict how much WorkSpace is needed?

I guess my request is then to fix Horner_tree() so that it would ask the user to increase WorkSpace, and exits gracefully.

[vermaseren]

If this solves indeed the problem, then the consideration is the folllowing: You mention that the expression has > 100Mbytes. This is all put in the WorkSpace, but since I did not write that code myself I do not know whether there is a multiplicative factor. Usually there is, like 2 or 4 or 8. And there may be more in the WorkSpace, although probably not of that order of magnitude. If I would have made this code, I might not have used the WorkSpace for it, but on the other hand, I never had expressions that large either. Just a few Mbytes. We run here into a typical problem: once something works, sooner or later people make things bigger and bigger and one runs into the limitations, and work is needed to solve those limitations. Much of Form development has been like that. Probably the first thing to do is have it check before raising this variable sorted in line 900, that it is not running out of the WorkSpace and if so, give an error message and a suggestion. Alternatively, have it first see how much the whole thing needs, then check and only then start copying and sorting things. This seems the preferred method. But let us first see how your programs go.

Jos

On 14 Mar 2021, at 20:23, Vitaly Magerya @.***> wrote:

Yes, increasing WorkSpace does seem to help (FORM didn't finish yet, but at least it did not immediately crash). Thanks, Jos. Is there a way to predict how much WorkSpace is needed?

I guess my request is then to fix Horner_tree() so that it would ask the user to increase WorkSpace, and exits gracefully.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/vermaseren/form/issues/379#issuecomment-798964198, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABJPCETHTHZTE7RKXS2IAG3TDUEJRANCNFSM4ZFIK3SA.

[magv]

Upping WorkSpace to 1G worked; 35 minutes of optimization in total (at O2). Anything below 50M, and FORM crashed in under 10 seconds.

[vermaseren]

That is good news. I will try to ‘repair’ this in the sense that it will give an error message and a suggestion. May not be immediate though.

Jos

On 14 Mar 2021, at 21:59, Vitaly Magerya @.***> wrote:

Upping WorkSpace to 1G worked; 35 minutes of optimization in total (at O2). Anything below 50M, and FORM crashed in under 10 seconds.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/vermaseren/form/issues/379#issuecomment-798978733, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABJPCET3MDILJBB76K26CWDTDUPT7ANCNFSM4ZFIK3SA.

[magv]

Thanks.

[tueda]

@magv Could you give it a try to see whether it is fixed? "Workspace overflow" should be detected and FORM must terminate without a segfault.

[magv]

Right now I'm seeing

=== Workspace overflow. 40000000 bytes is not enough.
=== Change parameter WorkSpace in form.set
=== At least 162951872 bytes are needed.

... which is much, much better. The last line is especially great. Thanks a lot. I think I'll close this bug.