search

koka-lang / koka

Koka language compiler and interpreter
http://koka-lang.org
Other
3.25k stars 160 forks source link

Koka program crashes randomly #188

Closed anfelor closed 8 months ago

anfelor commented 3 years ago

You can find a fairly short Koka implementation of heapsort based on Binomial Heaps (as discussed by Okasaki) here: https://gist.github.com/anfelor/f6d6e437d9d47f77534cace1904bbe5e (I couldn't reduce this further; this is a tricky bug!)

When run (Koka v2.1.9, macOS with M1 processor), this will sometimes print the correct answer [1,2,3]; but often crash. I modified Koka to call asan without the 'leak' option (which doesn't work on M1 macs) and got:

=================================================================
==8130==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x603000001ac8 at pc 0x00010af7a300 bp 0x000308a9e4b0 sp 0x000308a9dc78
READ of size 8 at 0x603000001ac8 thread T0
    #0 0x10af7a2ff in __asan_memcpy+0x1af (libclang_rt.asan_osx_dynamic.dylib:x86_64+0x432ff)
    #1 0x102531af1 in kk_block_field kklib.h:219
    #2 0x10253559f in kk_block_dropn kklib.h:618
    #3 0x1025352e0 in kk_datatype_dropn kklib.h:781
    #4 0x10250db69 in kk_std_core__list_dropn std_core.h:818
    #5 0x10250c0c3 in kk_test_perf_heaps_binomial_dash_heaps_dash_okasaki_insert_tree test_perf_heaps_binomial_dash_heaps_dash_okasaki.c:191
    #6 0x10250ed91 in kk_test_perf_heaps_binomial_dash_heaps_dash_okasaki_insert test_perf_heaps_binomial_dash_heaps_dash_okasaki.c:235
    #7 0x10250fb01 in kk_test_perf_heaps_binomial_dash_heaps_dash_okasaki_from_list test_perf_heaps_binomial_dash_heaps_dash_okasaki.c:257
    #8 0x102529552 in kk_test_perf_heaps_binomial_dash_heaps_dash_okasaki_main test_perf_heaps_binomial_dash_heaps_dash_okasaki.c:1094
    #9 0x10253aa18 in kk_test_perf_heaps_binomial_dash_heaps_dash_okasaki__hmain_fun5426 test_perf_heaps_binomial_dash_heaps_dash_okasaki.c:1121
    #10 0x1024c3e57 in kk_std_core__default_exn_fun24601 std_core.c:4177
    #11 0x102347dd2 in kk_std_core_hnd__hhandle std_core_hnd.c:1042
    #12 0x1023b3b0c in kk_std_core__handle_exn std_core.c:508
    #13 0x10240f37b in kk_std_core__default_exn std_core.c:4186
    #14 0x10252a490 in kk_test_perf_heaps_binomial_dash_heaps_dash_okasaki__hmain test_perf_heaps_binomial_dash_heaps_dash_okasaki.c:1125
    #15 0x10252fe86 in main test_perf_heaps_binomial_dash_heaps_dash_okasaki.c:1415
    #16 0x7fff204a5f3c in start+0x0 (libdyld.dylib:x86_64+0x15f3c)

0x603000001ac8 is located 0 bytes to the right of 24-byte region [0x603000001ab0,0x603000001ac8)
allocated by thread T0 here:
    #0 0x10af7c230 in wrap_malloc+0xa0 (libclang_rt.asan_osx_dynamic.dylib:x86_64+0x45230)
    #1 0x1025325b8 in kk_malloc kklib.h:407
    #2 0x1025324ac in kk_malloc_small kklib.h:411
    #3 0x102532452 in kk_block_alloc_at kklib.h:462
    #4 0x10250a8ce in kk_std_core__new_Cons std_core.h:785
    #5 0x10250b6ec in kk_test_perf_heaps_binomial_dash_heaps_dash_okasaki_insert_tree test_perf_heaps_binomial_dash_heaps_dash_okasaki.c:162
    #6 0x10250ed91 in kk_test_perf_heaps_binomial_dash_heaps_dash_okasaki_insert test_perf_heaps_binomial_dash_heaps_dash_okasaki.c:235
    #7 0x10250fb01 in kk_test_perf_heaps_binomial_dash_heaps_dash_okasaki_from_list test_perf_heaps_binomial_dash_heaps_dash_okasaki.c:257
    #8 0x102529552 in kk_test_perf_heaps_binomial_dash_heaps_dash_okasaki_main test_perf_heaps_binomial_dash_heaps_dash_okasaki.c:1094
    #9 0x10253aa18 in kk_test_perf_heaps_binomial_dash_heaps_dash_okasaki__hmain_fun5426 test_perf_heaps_binomial_dash_heaps_dash_okasaki.c:1121
    #10 0x1024c3e57 in kk_std_core__default_exn_fun24601 std_core.c:4177
    #11 0x102347dd2 in kk_std_core_hnd__hhandle std_core_hnd.c:1042
    #12 0x1023b3b0c in kk_std_core__handle_exn std_core.c:508
    #13 0x10240f37b in kk_std_core__default_exn std_core.c:4186
    #14 0x10252a490 in kk_test_perf_heaps_binomial_dash_heaps_dash_okasaki__hmain test_perf_heaps_binomial_dash_heaps_dash_okasaki.c:1125
    #15 0x10252fe86 in main test_perf_heaps_binomial_dash_heaps_dash_okasaki.c:1415
    #16 0x7fff204a5f3c in start+0x0 (libdyld.dylib:x86_64+0x15f3c)

SUMMARY: AddressSanitizer: heap-buffer-overflow (libclang_rt.asan_osx_dynamic.dylib:x86_64+0x432ff) in __asan_memcpy+0x1af
Shadow bytes around the buggy address:
  0x1c0600000300: fa fa 00 00 00 00 fa fa 00 00 00 00 fa fa 00 00
  0x1c0600000310: 00 00 fa fa 00 00 00 00 fa fa 00 00 00 00 fa fa
  0x1c0600000320: 00 00 00 00 fa fa 00 00 00 00 fa fa 00 00 00 fa
  0x1c0600000330: fa fa fd fd fd fa fa fa 00 00 00 fa fa fa fd fd
  0x1c0600000340: fd fa fa fa fd fd fd fa fa fa 00 00 00 fa fa fa
=>0x1c0600000350: fd fd fd fa fa fa 00 00 00[fa]fa fa 00 00 00 fa
  0x1c0600000360: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c0600000370: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c0600000380: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c0600000390: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c06000003a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==8130==ABORTING
failure during program run:

   "out/v2.1.9/gcc-asan-debug/test_perf_heaps_binomial_dash_heaps_dash_okasaki"

EDIT: The '--fasan' output is the same each run under both gcc and clang and it seems like the program will always crash with this option enabled.

anfelor commented 3 years ago

Weirdly, the asan output suggests that something goes wrong when inserting elements into the heap in the from-list function. But when I tested the code on the Koka shell, the from-list function never segfaulted, while the to-list function segfaulted roughly as often as the heapsort function. But when I minimized this example to contain only the to-list function no segfaults appeared.

Also, if you play around with this enough on the Koka shell it will start printing garbage and some of the programs code at some point; which suggests that some overflow happens and raw heap contents are printed into the shell.

stevenfontanella commented 3 years ago

I compiled with -O-1 to disable all gcc optimizations and see that this assertion fails:

home_steven_Downloads_binomial_dash_heaps_dash_okasaki: /usr/local/share/koka/v2.1.9/kklib/include/kklib.h:616: kk_block_dropn: Assertion `scan_fsize == kk_block_scan_fsize(b)' failed.
Aborted (core dumped)
TimWhiting commented 8 months ago

Both debug and optimized builds run fine for me now.