Re: Clang-built Gawk 5.2.1 regex oddity

Re: Clang-built Gawk 5.2.1 regex oddity

[arnold]

Hi Sam,

Thanks for the further info.

Looking at both bits of dfa.c code, I don't see how either can be
undefined behavior.

In any case, dfa.c is copied directly from GNULIB, so I am cc-ing
bug-gnulib.

Paul & Jim, for background, please see the thread at
https://lists.gnu.org/archive/html/bug-gawk/2022-12/msg00010.html.

This still smells like "compiler bug" to me, but even if not,
the GNULIB folks need to look at it.

I will take a look at testdfa; it's been a while since I've had to
use it, so maybe something has gotten out of sync.

Thanks,

Arnold

Sam James <sam@gentoo.org> wrote:

> > On 30 Dec 2022, at 09:13, arnold@skeeve.com wrote:
> > 
> > Hi.
> > 
> > Thanks for the report.
> > 
> > Although the dfa and regex code changed some between releases,
> > this smells strongly like a compiler issue and not a gawk issue.
> > 
> > I suggest first that you try compiling with clang but without
> > optimization. After running configure, edit the top level Makefile *and*
> > support/Makefile and remove any -O flags.  Then build.
>
> Kenton mentioned to me that with no optimisation, it works okay.
>
> > If the bug goes away, it's definitely a clang issue.
>
> It _probably_ is, but it's also possible it's UB. I tried building with UBSAN
> (as did Kenton) and we both got this when running the command he posted
> when built with Clang:
> ```
> $ ./configure CC=clang CFLAGS="-O2 -fsanitize=undefined -ggdb3" LDFLAGS="-fsanitize=undefined -ggdb3"
> $ make
> $ export UBSAN_OPTIONS=print_stacktrace=1
> $ ./gawk 'BEGIN { RS="[[][:blank:]]" }'
> dfa.c:1141:6: runtime error: execution reached an unreachable program point
>     #0 0x5db652 in parse_bracket_exp /tmp/gawk/support/dfa.c:1141:6
>     #1 0x5c241a in lex /tmp/gawk/support/dfa.c:1543:37
>     #2 0x5dc8f1 in atom /tmp/gawk/support/dfa.c:1888:24
>     #3 0x5dc8f1 in closure /tmp/gawk/support/dfa.c:1961:3
>     #4 0x5dc022 in branch /tmp/gawk/support/dfa.c:2002:3
>     #5 0x5c7082 in regexp /tmp/gawk/support/dfa.c:2014:3
>     #6 0x5c0e32 in dfaparse /tmp/gawk/support/dfa.c:2042:3
>     #7 0x5c76c2 in dfacomp /tmp/gawk/support/dfa.c:3812:5
>     #8 0x5abb33 in make_regexp /tmp/gawk/re.c:272:3
>     #9 0x56dffd in set_RS /tmp/gawk/io.c:4092:14
>     #10 0x50510b in r_interpret /tmp/gawk/./interpret.h
>     #11 0x5754d7 in main /tmp/gawk/main.c:538:3
>     #12 0x7f7bb5df464f in __libc_start_call_main /var/tmp/portage/sys-libs/glibc-2.36-r6/work/glibc-2.36/csu/../sysdeps/nptl/libc_start_call_main.h:58:16
>     #13 0x7f7bb5df4708 in __libc_start_main@GLIBC_2.2.5 /var/tmp/portage/sys-libs/glibc-2.36-r6/work/glibc-2.36/csu/../csu/libc-start.c:381:3
>     #14 0x4092a4 in _start /var/tmp/portage/sys-libs/glibc-2.36-r6/work/glibc-2.36/csu/../sysdeps/x86_64/start.S:115
>
> SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior dfa.c:1141:6 in # (yes, this is cut off, I don't know why!)
> ```
>
> If I build with ASAN instead with Clang:
> ```
> $ ./configure CC=clang CFLAGS="-O2 -fsanitize=address -ggdb3" LDFLAGS="-fsanitize=address -ggdb3"
> $ make
> $ ./gawk 'BEGIN { RS="[[][:blank:]]" }'
> =================================================================
> ==1517313==ERROR: AddressSanitizer: unknown-crash on address 0x7fa647137000 at pc 0x000000658214 bp 0x7ffe59482ad0 sp 0x7ffe59482ac8
> READ of size 8 at 0x7fa647137000 thread T0
>     #0 0x658213 in setbit /tmp/gawk/support/dfa.c:746:33
>     #1 0x658213 in setbit_case_fold_c /tmp/gawk/support/dfa.c:868:7
>     #2 0x658213 in parse_bracket_exp /tmp/gawk/support/dfa.c:1095:27
>     #3 0x64b6d0 in lex /tmp/gawk/support/dfa.c:1543:37
>     #4 0x6588dd in atom /tmp/gawk/support/dfa.c:1888:24
>     #5 0x6588dd in closure /tmp/gawk/support/dfa.c:1961:3
>     #6 0x64d84c in branch /tmp/gawk/support/dfa.c:2002:3
>     #7 0x64d84c in regexp /tmp/gawk/support/dfa.c:2014:3
>     #8 0x64aad6 in dfaparse /tmp/gawk/support/dfa.c:2042:3
>     #9 0x64dbb7 in dfacomp /tmp/gawk/support/dfa.c:3812:5
>     #10 0x6404df in make_regexp /tmp/gawk/re.c:272:3
>     #11 0x611b66 in set_RS /tmp/gawk/io.c:4092:14
>     #12 0x5c693b in r_interpret /tmp/gawk/./interpret.h
>     #13 0x616e6b in main /tmp/gawk/main.c:538:3
>     #14 0x7fa646ccc64f in __libc_start_call_main /var/tmp/portage/sys-libs/glibc-2.36-r6/work/glibc-2.36/csu/../sysdeps/nptl/libc_start_call_main.h:58:16
>     #15 0x7fa646ccc708 in __libc_start_main@GLIBC_2.2.5 /var/tmp/portage/sys-libs/glibc-2.36-r6/work/glibc-2.36/csu/../csu/libc-start.c:381:3
>     #16 0x420df4 in _start /var/tmp/portage/sys-libs/glibc-2.36-r6/work/glibc-2.36/csu/../sysdeps/x86_64/start.S:115
>
> Address 0x7fa647137000 is a wild pointer inside of access range of size 0x000000000008.
> SUMMARY: AddressSanitizer: unknown-crash /tmp/gawk/support/dfa.c:746:33 in setbit
> Shadow bytes around the buggy address:
>   0x7fa647136d80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
>   0x7fa647136e00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
>   0x7fa647136e80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
>   0x7fa647136f00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
>   0x7fa647136f80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
> =>0x7fa647137000:[00]00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
>   0x7fa647137080: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
>   0x7fa647137100: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
>   0x7fa647137180: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
>   0x7fa647137200: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
>   0x7fa647137280: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
> 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
> ==1517313==ABORTING
> ``
>
> I'm testing with Clang from git (LLVM 16, dfc20708bcdf7b4c4bea8595fc4ac8674634d5e6)
> but when I tried Clang 15, I got the same. I'm pretty sure Kenton is using Clang 15 as well.
>
> Of course, this might still be a Clang bug though. I don't see this with
> GCC but that's not proof either way. So if this all looks impossible, one
> of us can forward it up to Clang and see what they say.
>
> > In any case, in the gawk repo in helpers/testdfa.c is a program that
> > may be useful for further isolating the problem, since it extracts
> > the regex building and matching from the rest of gawk's code. If
> > the problem persists with that program, it will be of more use
> > in making a bug report to the clang team.
> > 
>
> Unfortunately, no matter what input I give to testdfa,
> it seems to say "malloc failed", e.g.
> ```
> $ ./testdfa 'a'
> Ignorecase: false
> Syntax: RE_BACKSLASH_ESCAPE_IN_LISTS|RE_CHAR_CLASSES|RE_CONTEXT_INDEP_ANCHORS|RE_DOT_NEWLINE|RE_INTERVALS|RE_NO_BK_BRACES|RE_NO_BK_PARENS|RE_NO_BK_VBAR|RE_NO_EMPTY_RANGES|RE_UNMATCHED_RIGHT_PAREN_ORD|RE_INVALID_INTERVAL_ORD
> Pattern: /a/, len = 1
> setup_pattern: malloc failed
> ```
>
> This happens even if testdfa is built with GCC (12.2.1_20221224).
>
> Best,
> sam

Re: Clang-built Gawk 5.2.1 regex oddity

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 2142 bytes --]

This is a serious bug in Clang: it generates incorrect machine code.

The code that Clang generates for the following (gawk/support/dfa.c 
lines 1141-1143):

     ((dfa->syntax.dfaopts & DFA_CONFUSING_BRACKETS_ERROR
       ? dfaerror : dfawarn)
      (_("character class syntax is [[:space:]], not [:space:]")));

is immediately followed by the code generated for the following 
(gawk/support/dfa.c line 1015):

                     dfaerror (_("invalid character class"));

and this is incorrect because the two source code regions are not 
connected with each other.

You can see the bug in the attached (compressed) file dfa.s which 
contains the assembly language output. Here's the dfa.s file starting 
with line 6975:

   6975		testb	$4, 456(%r12)
   6976		movl	$dfawarn, %eax
   6977		movl	$dfaerror, %ebx
   6978		cmoveq	%rax, %rbx
   6979		movl	$.L.str.26, %esi
   6980		xorl	%edi, %edi
   6981		movl	$5, %edx
   6982		callq	dcgettext
   6983		movq	%rax, %rdi
   6984		callq	*%rbx
   6985	.LBB34_144:
   6986		movl	$.L.str.25, %esi
   6987		xorl	%edi, %edi
   6988		movl	$5, %edx
   6989		callq	dcgettext
   6990		movq	%rax, %rdi
   6991		callq	dfaerror

Line 6984, which is source lines 1141-1143 call to either dfaerror or 
dfawarn, is immediately followed by the code for source line 1015. This 
means that at runtime when dfawarn returns the code immediately calls 
dfaerror, which is incorrect.

My guess is that Clang got confused because dfaerror is declared 
_Noreturn, so Clang mistakenly assumed that dfawarn is also _Noreturn, 
which it is not.

I worked around the Clang bug by installed the attached patch into 
Gnulib. Please give it a try with Gawk.

Incorrect code generation is a serious bug in Clang; can you please 
report it to the Clang folks? I am considering using a bigger hammer, 
and doing this:

    #define _Noreturn /*empty*/

whenever Clang is used, until the bug is fixed.

This is because if the bug occurs here it's likely that similar bugs 
will occur elsewhere and this sort of thing can be really subtle and 
hard to catch or work around in general. Clang really needs to get this 
fixed.

Thanks.

[-- Attachment #2: dfa.s.gz --]
[-- Type: application/gzip, Size: 37979 bytes --]

[-- Attachment #3: 0001-dfa-work-around-Clang-15-bug.patch --]
[-- Type: text/x-patch, Size: 2032 bytes --]

From 8805a44cf04253f63bce160054e2fbf21ab9beb1 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sun, 1 Jan 2023 22:06:10 -0800
Subject: [PATCH] dfa: work around Clang 15 bug

Problem reported by Kenton Groombridge in:
https://lists.gnu.org/archive/html/bug-gawk/2022-12/msg00010.html
On x86-64, Clang 15 gets confused by a call (X ? dfaerror :
dfawarn) (Y) and generates the wrong code, presumably because
dfaerror is _Noreturn and dfawarn is not.
* lib/dfa.c (parse_bracket_exp): Reword to have one call for
dfaerror, the other for dfawarn.
---
 ChangeLog | 11 +++++++++++
 lib/dfa.c | 11 ++++++++---
 2 files changed, 19 insertions(+), 3 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 59500558e4..ac3d388c2b 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,14 @@
+2023-01-01  Paul Eggert  <eggert@cs.ucla.edu>
+
+	dfa: work around Clang 15 bug
+	Problem reported by Kenton Groombridge in:
+	https://lists.gnu.org/archive/html/bug-gawk/2022-12/msg00010.html
+	On x86-64, Clang 15 gets confused by a call (X ? dfaerror :
+	dfawarn) (Y) and generates the wrong code, presumably because
+	dfaerror is _Noreturn and dfawarn is not.
+	* lib/dfa.c (parse_bracket_exp): Reword to have one call for
+	dfaerror, the other for dfawarn.
+
 2023-01-01  Bruno Haible  <bruno@clisp.org>
 
 	doc: Update regarding stable branches.
diff --git a/lib/dfa.c b/lib/dfa.c
index 57df1e0421..211e1ed18f 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -1138,9 +1138,14 @@ parse_bracket_exp (struct dfa *dfa)
   while ((wc = wc1, (c = c1) != ']'));
 
   if (colon_warning_state == 7)
-    ((dfa->syntax.dfaopts & DFA_CONFUSING_BRACKETS_ERROR
-      ? dfaerror : dfawarn)
-     (_("character class syntax is [[:space:]], not [:space:]")));
+    {
+      char const *msg
+        = _("character class syntax is [[:space:]], not [:space:]");
+      if (dfa->syntax.dfaopts & DFA_CONFUSING_BRACKETS_ERROR)
+        dfaerror (msg);
+      else
+        dfawarn (msg);
+    }
 
   if (! known_bracket_exp)
     return BACKREF;
-- 
2.37.2

Re: Clang-built Gawk 5.2.1 regex oddity

[Sam James]

[-- Attachment #1: Type: text/plain, Size: 1111 bytes --]



> On 2 Jan 2023, at 06:10, Paul Eggert <eggert@cs.ucla.edu> wrote:
> 
> This is a serious bug in Clang: it generates incorrect machine code.
> 
> [snip]
> 
> My guess is that Clang got confused because dfaerror is declared _Noreturn, so Clang mistakenly assumed that dfawarn is also _Noreturn, which it is not.
> 
> I worked around the Clang bug by installed the attached patch into Gnulib. Please give it a try with Gawk.

Confirmed this mitigates the problem. I had to apply it manually to support/ as I couldn't immediately see how to sync gnulib myself, but that's no big deal.

> 
> Incorrect code generation is a serious bug in Clang; can you please report it to the Clang folks? I am considering using a bigger hammer, and doing this:
> 

Kenton's done this at https://github.com/llvm/llvm-project/issues/59792 now.

>   #define _Noreturn /*empty*/
> 
> whenever Clang is used, until the bug is fixed.
> 

maskray's analysis so far at https://github.com/llvm/llvm-project/issues/59792#issuecomment-1369314436 agrees with yours, which would mean
this is likely a good idea.


[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 358 bytes --]

Re: Clang-built Gawk 5.2.1 regex oddity

[Sam James]

[-- Attachment #1: Type: text/plain, Size: 1598 bytes --]



> On 3 Jan 2023, at 02:14, Sam James <sam@gentoo.org> wrote:
> 
> 
> 
>> On 2 Jan 2023, at 06:10, Paul Eggert <eggert@cs.ucla.edu> wrote:
>> 
>> This is a serious bug in Clang: it generates incorrect machine code.
>> 
>> [snip]
>> 
>> My guess is that Clang got confused because dfaerror is declared _Noreturn, so Clang mistakenly assumed that dfawarn is also _Noreturn, which it is not.
>> 
>> I worked around the Clang bug by installed the attached patch into Gnulib. Please give it a try with Gawk.
> 
> Confirmed this mitigates the problem. I had to apply it manually to support/ as I couldn't immediately see how to sync gnulib myself, but that's no big deal.
> 
>> 
>> Incorrect code generation is a serious bug in Clang; can you please report it to the Clang folks? I am considering using a bigger hammer, and doing this:
>> 
> 
> Kenton's done this at https://github.com/llvm/llvm-project/issues/59792 now.
> 
>>  #define _Noreturn /*empty*/
>> 
>> whenever Clang is used, until the bug is fixed.
>> 
> 
> maskray's analysis so far at https://github.com/llvm/llvm-project/issues/59792#issuecomment-1369314436 agrees with yours, which would mean
> this is likely a good idea.
> 

By the way, when I ran gnulib's test suite following https://sourceware.org/glibc/wiki/Testing/Gnulib, I didn't get any failures
with Clang. I was expecting to get one (before your commit) for DFA.

Maybe we should shoehorn a similar ternary expression into tests/test-dfa-match-aux.c so we're guaranteed
a test failure with bad compilers if someone uses the DFA module?

[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 358 bytes --]

Re: Clang-built Gawk 5.2.1 regex oddity

[Arsen Arsenović]

[-- Attachment #1: Type: text/plain, Size: 797 bytes --]

Hi,

Paul Eggert <eggert@cs.ucla.edu> writes:

> This is a serious bug in Clang: it generates incorrect machine code.
>
> The code that Clang generates for the following (gawk/support/dfa.c lines
> 1141-1143):
>
>     ((dfa->syntax.dfaopts & DFA_CONFUSING_BRACKETS_ERROR
>       ? dfaerror : dfawarn)
>      (_("character class syntax is [[:space:]], not [:space:]")));
>
> is immediately followed by the code generated for the following
> (gawk/support/dfa.c line 1015):
>
>                     dfaerror (_("invalid character class"));
>
> and this is incorrect because the two source code regions are not connected
> with each other.

This is now fixed in Clang:
https://reviews.llvm.org/rGcf8fd210a35c8e93136cb8edc5c6a2e818dc1b1d

Happy hacking!
-- 
Arsen Arsenović

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 251 bytes --]

Re: Clang-built Gawk 5.2.1 regex oddity

[arnold]

Thanks for the update.

Paul, let's leave dfa.c as is, with the modified code.
It's much easier to read anyway.

Thanks,

Arnold

Arsen Arsenović <arsen@aarsen.me> wrote:

> Hi,
>
> Paul Eggert <eggert@cs.ucla.edu> writes:
>
> > This is a serious bug in Clang: it generates incorrect machine code.
> >
> > The code that Clang generates for the following (gawk/support/dfa.c lines
> > 1141-1143):
> >
> >     ((dfa->syntax.dfaopts & DFA_CONFUSING_BRACKETS_ERROR
> >       ? dfaerror : dfawarn)
> >      (_("character class syntax is [[:space:]], not [:space:]")));
> >
> > is immediately followed by the code generated for the following
> > (gawk/support/dfa.c line 1015):
> >
> >                     dfaerror (_("invalid character class"));
> >
> > and this is incorrect because the two source code regions are not connected
> > with each other.
>
> This is now fixed in Clang:
> https://reviews.llvm.org/rGcf8fd210a35c8e93136cb8edc5c6a2e818dc1b1d
>
> Happy hacking!
> -- 
> Arsen Arsenović

Re: Clang-built Gawk 5.2.1 regex oddity

[Sam James]

[-- Attachment #1: Type: text/plain, Size: 1126 bytes --]



> On 5 Jan 2023, at 23:06, Arsen Arsenović <arsen@aarsen.me> wrote:
> 
> Hi,
> 
> Paul Eggert <eggert@cs.ucla.edu> writes:
> 
>> This is a serious bug in Clang: it generates incorrect machine code.
>> 
>> The code that Clang generates for the following (gawk/support/dfa.c lines
>> 1141-1143):
>> 
>>    ((dfa->syntax.dfaopts & DFA_CONFUSING_BRACKETS_ERROR
>>      ? dfaerror : dfawarn)
>>     (_("character class syntax is [[:space:]], not [:space:]")));
>> 
>> is immediately followed by the code generated for the following
>> (gawk/support/dfa.c line 1015):
>> 
>>                    dfaerror (_("invalid character class"));
>> 
>> and this is incorrect because the two source code regions are not connected
>> with each other.
> 
> This is now fixed in Clang:
> https://reviews.llvm.org/rGcf8fd210a35c8e93136cb8edc5c6a2e818dc1b1d

This is not in 15.0.7 and there won't be any further 15.x releases as there's
an ABI break caused by it. We've backported it in Gentoo but others may not.

It will be in 16.x.

I think gnulib should probably make that #define change for Clang < 16.



[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 358 bytes --]