A problem with the Unbalanced Tree Search Benchmark

[adnan4791]

I ported the UTS written in OpenMP to Opencilk code. The program is here
I have tested the OpenCilk program using two input files. For the first input file (test.input), which contains the smallest tree, the UTS Opencilk program can run properly and produce the correct output. However, when I tested it with the second input file (tiny.input) which is the tall but tiny, the UTS Opencilk program experienced a segmentation fault. At first I thought there was a stack size problem, but when I increased the stack size to almost 1GB, the segmentation fault still occurred. Is there something wrong with this UTS program?
Here is the environment where i tested the UTS
CPU : core i7 1260P,
RAM : 16 GB
OS : Ubuntu 22.0
OpenCilk install : binary install .

Thank you

[neboat]

Let me ask a few questions to try and diagnose the issue:

1. Can you replicate the segmentation fault when you run with 1 Cilk worker?

• You can set the environment variable CILK_NWORKERS=1 to tell OpenCilk to run with just 1 worker, e.g., CILK_NWORKERS=1 ./a.out.

2. Have you checked the program for memory errors using valgrind or AddressSanitizer?

• To use AddressSanitizer, recompile the program adding the flag -fsanitize=address when compiling and when linking, then run the program normally. If there are no memory issues, I would expect AddressSanitizer to report no issues when you run the program either on 1 worker or multiple workers.
• If valgrind is installed on your system, you can run the program compiled normally using the valgrind command, e.g., CILK_NWORKERS=1 valgrind ./a.out. Like AddressSanitizer, valgrind will report any memory errors it detects. I have found that valgrind doesn't work reliably when running with multiple Cilk workers, so I recommend running it with just 1 Cilk worker.
• If either tool reports memory errors in the program, I recommend compiling the program with debug symbols, to relate the error output to the source code. To compile the program with debug symbols, compile the program with the additional flags -g -gdwarf-4.

3. Are you compiling the Cilk program with compiler optimizations enabled? I have seen some Cilk programs that require compiler optimizations to use memory efficiently and avoid segfaults when run on larger inputs.

• To enable compiler optimizations, add one of the flags -O1, -O2, or -O3 to your compiler flags when you build the program.

4. Have you checked the program for races using Cilksan?

• To use Cilksan, compile the program with the additional flag -fsanitize=cilk and then run the program normally. Running with Cilksan can be slow, but it will report races if it detects any.

Give those suggestions a try and let us know how it goes.

[adnan4791]

Hi @neboat

Thank you very much for you valuable answer and suggestions.

Here is the report from the AddressSanitizer :

adnan@adnan-HP-Laptop-14s-dq5xxx:~/uts_cilk$ CILK_NWORKERS=1 ./utscilk -f tiny.input
AddressSanitizer:DEADLYSIGNAL

==5533==ERROR: AddressSanitizer: stack-overflow on address 0x7f083e8fee98 (pc 0x00000049e596 bp 0x7f083e8ff6d0 sp 0x7f083e8feea0 T0)
#0 0x49e596 in __asan_memcpy /home/neboat/opencilk/compiler-rt/lib/asan/asan_interceptors_memintrinsics.cpp:22:3
#1 0x4dd5e2 in rng_spawn (/home/adnan/uts_cilk/utscilk+0x4dd5e2)

2. I recompiled with -g -gdwarf-4
   Then the debugger output like this

adnan@adnan-HP-Laptop-14s-dq5xxx:/uts_cilk$ export CILK_NWORKERS=1
adnan@adnan-HP-Laptop-14s-dq5xxx:/uts_cilk$ gdb utscilk
GNU gdb (Ubuntu 12.1-0ubuntu1~22.04) 12.1
Copyright (C) 2022 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later http://gnu.org/licenses/gpl.html
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
https://www.gnu.org/software/gdb/bugs/.
Find the GDB manual and other documentation resources online at:
http://www.gnu.org/software/gdb/documentation/.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from utscilk...
(gdb) run -f tiny.input
Starting program: /home/adnan/uts_cilk/utscilk -f tiny.input
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Program received signal SIGSEGV, Segmentation fault.
0x0000000000402d6b in rng_spawn (mystate=0x0, newstate=0x0, spawnnumber=0) at brg_sha1.c:74
74 {
(gdb)

3. I have compiled the program with -O3 flag

[neboat]

It does indeed look like the program is overflowing the stack.

How did you try changing the stack size before? Note that Cilk programs use a custom stack implementation, which uses its own mechanism to adjust the stack size.

[adnan4791]

I see..

I set stack size in .bashrc file using ulimit command. So how should i set the stack size for the OpenCilk program?

[neboat]

You can set Cilk’s stack size using the CILK_STACKSIZE environment variable.

[adnan4791]

thank you very much
after doing a bit of research i found the problem was with the size of the cilk's dequeu, i solved the problem by set the CILK_DEQDEPTH environment variable.