Re: [PATCH] cex: fix a crash

Akim Demaille <[email protected]>
Newsgroups gmane.comp.parsers.bison.patches
Message-ID <[email protected]> 

> Le 16 mai 2020 à 20:51, Vincent Imbimbo <[email protected]> a écrit :
> 
> * src/parse-simulation.c: Replace reference counting with parse_state_retain everywhere.
> (free_parse_state): Make this function iterative instead of recursive. Long parse_state chains were causing stack exhaustion.
> 
> * tests/counterexample.at: fix expectations
> 
> It's possible for the search to do a rapid infinite descent through productions, which is one of the reasons there's a timeout. I had never thought of the chance a path would be deep enough to cause stack exhaustion.
> 
> I'll be taking a deeper look into the actual results of these tests soon. I'm curious as to what causes the unifying search to fail on the first example from this test.

Hi Vincent,

This does not seem right.  You should try to use clang with address sanitizer (see .travis.yml for one way to set it up).  For instance, that's one failure on my machine, caused by this commit.

Cheers!
testsuite.log (application/octet-stream, 6.1 KB) 
#                             -*- compilation -*-
243. counterexample.at:56: testing Deep Unifying S/R ...
/Users/akim/src/gnu/bison/tests/counterexample.at:80: COLUMNS=1000; export COLUMNS;  bison --color=no -fno-caret -Wcounterexample input.y
--- -	2020-05-16 22:35:12.651221000 +0200
+++ /Users/akim/src/gnu/bison/_build/c9a/tests/testsuite.dir/at-groups/243/stderr	2020-05-16 22:35:12.585501291 +0200
@@ -1,11 +1,91 @@
+/Users/akim/src/gnu/bison/_build/c9a/tests/bison: line 42: 71604 Abort trap: 6           $PREBISON "$abs_top_builddir/src/bison" ${1+"$@"} 2> "$stderr"
 Shift-Reduce Conflict:
 1:    7 a: A .
 1:    5 b: . B
 On Symbol: B
-Example  A  •  B  C
-First  derivation  s ::=[ a ::=[ A  • ]  bc ::=[ B  C ] ]
-Second derivation  s ::=[ ac ::=[ A  ac ::=[ b ::=[ •  B ] ]  C ] ]
+=================================================================
+==71604==ERROR: AddressSanitizer: heap-use-after-free on address 0x6080000019e0 at pc 0x00010d1d3afc bp 0x7ffee2afd880 sp 0x7ffee2afd878
+READ of size 8 at 0x6080000019e0 thread T0
+    #0 0x10d1d3afb in free_parse_state (bison:x86_64+0x1000d2afb)
+    #1 0x10d12b887 in search_state_free_children (bison:x86_64+0x10002a887)
+    #2 0x10d127214 in search_state_free (bison:x86_64+0x100026214)
+    #3 0x10d29d410 in hash_free (bison:x86_64+0x10019c410)
+    #4 0x10d126c14 in unifying_example (bison:x86_64+0x100025c14)
+    #5 0x10d1294fc in counterexample_report (bison:x86_64+0x1000284fc)
+    #6 0x10d128e9d in counterexample_report_shift_reduce (bison:x86_64+0x100027e9d)
+    #7 0x10d1203ca in report_state_counterexamples (bison:x86_64+0x10001f3ca)
+    #8 0x10d11f2d0 in report_counterexamples (bison:x86_64+0x10001e2d0)
+    #9 0x10d11b785 in rule_conflicts_print (bison:x86_64+0x10001a785)
+    #10 0x10d11b21c in conflicts_print (bison:x86_64+0x10001a21c)
+    #11 0x10d16eca9 in main (bison:x86_64+0x10006dca9)
+    #12 0x7fff6df8d3d4 in start (/usr/lib/system/libdyld.dylib:x86_64+0x163d4)
 
-input.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
-input.y:6.4: warning: rule useless in parser due to conflicts [-Wother]
+0x6080000019e0 is located 64 bytes inside of 88-byte region [0x6080000019a0,0x6080000019f8)
+freed by thread T0 here:
+    #0 0x10d555076 in wrap_free (/opt/local/libexec/llvm-9.0/lib/clang/9.0.1/lib/darwin/libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x45076)
+    #1 0x10d1d3aad in free_parse_state (bison:x86_64+0x1000d2aad)
+    #2 0x10d12b887 in search_state_free_children (bison:x86_64+0x10002a887)
+    #3 0x10d127214 in search_state_free (bison:x86_64+0x100026214)
+    #4 0x10d29d410 in hash_free (bison:x86_64+0x10019c410)
+    #5 0x10d126c14 in unifying_example (bison:x86_64+0x100025c14)
+    #6 0x10d1294fc in counterexample_report (bison:x86_64+0x1000284fc)
+    #7 0x10d128e9d in counterexample_report_shift_reduce (bison:x86_64+0x100027e9d)
+    #8 0x10d1203ca in report_state_counterexamples (bison:x86_64+0x10001f3ca)
+    #9 0x10d11f2d0 in report_counterexamples (bison:x86_64+0x10001e2d0)
+    #10 0x10d11b785 in rule_conflicts_print (bison:x86_64+0x10001a785)
+    #11 0x10d11b21c in conflicts_print (bison:x86_64+0x10001a21c)
+    #12 0x10d16eca9 in main (bison:x86_64+0x10006dca9)
+    #13 0x7fff6df8d3d4 in start (/usr/lib/system/libdyld.dylib:x86_64+0x163d4)
+
+previously allocated by thread T0 here:
+    #0 0x10d554f2d in wrap_malloc (/opt/local/libexec/llvm-9.0/lib/clang/9.0.1/lib/darwin/libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x44f2d)
+    #1 0x10d2ca204 in xmalloc (bison:x86_64+0x1001c9204)
+    #2 0x10d1d5c00 in copy_parse_state (bison:x86_64+0x1000d4c00)
+    #3 0x10d1d86df in parser_prepend (bison:x86_64+0x1000d76df)
+    #4 0x10d1250c0 in search_state_prepend (bison:x86_64+0x1000240c0)
+    #5 0x10d128959 in generate_next_states (bison:x86_64+0x100027959)
+    #6 0x10d126ae2 in unifying_example (bison:x86_64+0x100025ae2)
+    #7 0x10d1294fc in counterexample_report (bison:x86_64+0x1000284fc)
+    #8 0x10d128e9d in counterexample_report_shift_reduce (bison:x86_64+0x100027e9d)
+    #9 0x10d1203ca in report_state_counterexamples (bison:x86_64+0x10001f3ca)
+    #10 0x10d11f2d0 in report_counterexamples (bison:x86_64+0x10001e2d0)
+    #11 0x10d11b785 in rule_conflicts_print (bison:x86_64+0x10001a785)
+    #12 0x10d11b21c in conflicts_print (bison:x86_64+0x10001a21c)
+    #13 0x10d16eca9 in main (bison:x86_64+0x10006dca9)
+    #14 0x7fff6df8d3d4 in start (/usr/lib/system/libdyld.dylib:x86_64+0x163d4)
+
+SUMMARY: AddressSanitizer: heap-use-after-free (bison:x86_64+0x1000d2afb) in free_parse_state
+Shadow bytes around the buggy address:
+  0x1c10000002e0: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 fa
+  0x1c10000002f0: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 fa
+  0x1c1000000300: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 fa
+  0x1c1000000310: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 fa
+  0x1c1000000320: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 fa
+=>0x1c1000000330: fa fa fa fa fd fd fd fd fd fd fd fd[fd]fd fd fa
+  0x1c1000000340: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 fa
+  0x1c1000000350: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 fa
+  0x1c1000000360: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 fa
+  0x1c1000000370: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 fa
+  0x1c1000000380: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 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
+==71604==ABORTING
 
/Users/akim/src/gnu/bison/tests/counterexample.at:80: exit code was 134, expected 0
243. counterexample.at:56: 243. Deep Unifying S/R (counterexample.at:56): FAILED (counterexample.at:80)
lmpx.com only provides a reader for public news (NNTP) servers. It is not affiliated with the servers or forums shown here and is not responsible for the content of articles, which is written by their respective authors.