GNU bug report logs - #21513
assertion error in pop_fail_stack

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 21513 in the body.
You can then email your comments to 21513 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Hanno Böck <hanno <at> hboeck.de>
To: bug-grep <at> gnu.org
Subject: assertion error in pop_fail_stack
Date: Fri, 18 Sep 2015 18:37:57 +0200

[Message part 1 (text/plain, inline)]

Hi,

This command
grep -E '0|()0|\1|0'
will cause an assert error:
grep: regexec.c:1401: pop_fail_stack: Assertion `num >= 0' failed.


Happens both in the latest release (2.21) and the latest git code.

(this was found with american fuzzy lop)

cu,
-- 
Hanno Böck
http://hboeck.de/

mail/jabber: hanno <at> hboeck.de
GPG: BBB51E42

[Message part 2 (application/pgp-signature, inline)]

Message #8 received at 21513 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Hanno Böck <hanno <at> hboeck.de>, 21513 <at> debbugs.gnu.org
Subject: Re: bug#21513: assertion error in pop_fail_stack
Date: Sat, 19 Sep 2015 18:46:22 -0700

[Message part 1 (text/plain, inline)]

Thanks for reporting that.  It's a bug in the glibc regular expression matcher, 
and as such will need a glibc fix.  I plan to propose a patch there.  In the 
meantime I fixed the Gnulib replacement for the matcher, here:

http://git.savannah.gnu.org/cgit/gnulib.git/commit/?id=5513b40999149090987a0341c018d05d3eea1272

and have installed the attached patches to GNU grep, so that the bug should be 
fixed if you configure grep using the --with-included-regex option.

[0001-build-update-gnulib-submodule-to-latest.patch (text/plain, attachment)]

[0002-Add-test-for-pop_fail_stack-bug.patch (text/plain, attachment)]

Message #11 received at 21513 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Hanno Böck <hanno <at> hboeck.de>, 21513 <at> debbugs.gnu.org
Subject: Re: bug#21513: assertion error in pop_fail_stack
Date: Sat, 19 Sep 2015 19:17:09 -0700

Paul Eggert wrote:
> It's a bug in the glibc regular expression matcher,
> and as such will need a glibc fix.  I plan to propose a patch there.

I created glibc bug report BZ#18986 about this, and put in a pointer to the 
Gnulib patch.  Hope that's enough to get it fixed in glibc, eventually.

https://sourceware.org/bugzilla/show_bug.cgi?id=18986

Message #18 received at 21513 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: arnold <at> skeeve.com, santiagorr <at> riseup.net, jim <at> meyering.net
Cc: 22793 <at> debbugs.gnu.org, 186568 <at> bugs.debian.org, 21513 <at> debbugs.gnu.org
Subject: Re: bug#22793: grep -E assertion failure with back references
Date: Thu, 25 Feb 2016 00:01:52 -0800

arnold <at> skeeve.com wrote:
> Paul Eggert <eggert <at> cs.ucla.edu> wrote:
>
>> With recent 'grep' you can work around the problem by configuring
>> --with-included-regex.
>
> Not so. I did a fresh
>
> 	./boostrap
> 	./configure --with-included-regex
> 	make
>
> and it still core dumps:
>
> $ echo abc | ./src/grep -E  '(.*)(.*)(.*)\3\2\1'
> grep: regexec.c:1413: pop_fail_stack: Assertion `((Idx) (num) < ((Idx) -2))' failed.
> Aborted (core dumped)
>
> I looked at it in a debugger fs->num before the --fs->num executes looks to
> be -1.

Sorry, you're right. I got confused into thinking that grep Bug#22793 and grep 
Bug#21513 are the same bugs, but they're not. I have unmerged them.

This is still a glibc bug, not a grep bug; it's just that we don't have a fix.

grep Bug#21513 is indeed fixed by configuring --with-included-regex.

Message #23 received at 21513-done <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Hanno Böck <hanno <at> hboeck.de>
Cc: 21513-done <at> debbugs.gnu.org
Subject: Re: assertion error in pop_fail_stack
Date: Sun, 22 Dec 2019 17:09:11 -0800

As Bug#21513 is now fixed both in Gnulib (which grep uses when configured
--with-included-regex) and in Glibc (which grep uses when configured
--without-included-regex) I am marking the bug report as done.

Message #26 received at 21513 <at> debbugs.gnu.org (full text, mbox):

From: Andreas Schwab <schwab <at> suse.de>
To: 21513 <at> debbugs.gnu.org
Cc: eggert <at> cs.ucla.edu, hanno <at> hboeck.de
Subject: Re: bug#21513: assertion error in pop_fail_stack
Date: Wed, 08 Jan 2020 15:14:41 +0100

On Dez 22 2019, Paul Eggert wrote:

> As Bug#21513 is now fixed both in Gnulib (which grep uses when configured
> --with-included-regex) and in Glibc (which grep uses when configured
> --without-included-regex) I am marking the bug report as done.

tests/triple-backref now runs forever.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab <at> suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Message #29 received at 21513 <at> debbugs.gnu.org (full text, mbox):

From: Martin Liška <mliska <at> suse.cz>
To: 21513 <at> debbugs.gnu.org
Subject: bug#21513
Date: Sat, 18 Jan 2020 15:44:20 +0100

I can confirm that it never finishes on i586.
I would recommend to replace   DEBUG_ASSERT (num >= 0);
which expands to:
  ((num >= 0) ? (void) 0 : __builtin_unreachable ());

into:

  if (num < 0)
    __builtin_abort ();

From GCC documentation:

If control flow reaches the point of the __builtin_unreachable,
the program is undefined.

In this case it loops forever.

Martin

Message #32 received at 21513 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Martin Liška <mliska <at> suse.cz>
Cc: Andreas Schwab <schwab <at> suse.de>, 21513 <at> debbugs.gnu.org
Subject: Re: bug#21513: (now an infinite loop in grep/tests/triple-backref?)
Date: Sat, 18 Jan 2020 14:16:45 -0800

On 1/18/20 6:44 AM, Martin Liška wrote:
> I can confirm that it never finishes on i586.

I can't reproduce the problem, either on Ubuntu 18.04.3 x86-64 (GCC Ubuntu 
7.4.0-1ubuntu1~18.04.1) or on Fedora 31 (GCC 9.2.1 20190827 x86-64 (Red Hat 
9.2.1-1)). I did what should have been the equivalent of:

git clone https://git.savannah.gnu.org/git/grep.git
# This is commit 23bf27015e0cc45d0012f54b8e24ac19fdca89f7.
cd grep
./bootstrap
./configure --with-included-regex CC='gcc -m32'
make
make check

and it worked for me; the triple-backref test had an XFAIL and did not loop. Can 
you send me more-detailed instructions for how to reproduce the bug?

> I would recommend to replace   DEBUG_ASSERT (num >= 0);
> which expands to:
>    ((num >= 0) ? (void) 0 : __builtin_unreachable ());
> 
> into:
> 
>    if (num < 0)
>      __builtin_abort ();

The regexec.c code doesn't abort, I guess under the theory that one is supposed 
to fix the code than insert runtime assertions that slow things down. You can 
compile with -DDEBUG if you want it to abort, but be prepared for other grep 
tests to fail if you do so. Admittedly this is a messy area.

Message #37 received at 21513 <at> debbugs.gnu.org (full text, mbox):

From: Martin Liška <mliska <at> suse.cz>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: Andreas Schwab <schwab <at> suse.de>, 21513 <at> debbugs.gnu.org
Subject: Re: bug#21513: (now an infinite loop in grep/tests/triple-backref?)
Date: Mon, 20 Jan 2020 11:49:15 +0100

[Message part 1 (text/plain, inline)]

On 1/18/20 11:16 PM, Paul Eggert wrote:
> On 1/18/20 6:44 AM, Martin Liška wrote:
>> I can confirm that it never finishes on i586.
> 
> I can't reproduce the problem, either on Ubuntu 18.04.3 x86-64 (GCC Ubuntu 7.4.0-1ubuntu1~18.04.1) or on Fedora 31 (GCC 9.2.1 20190827 x86-64 (Red Hat 9.2.1-1)). I did what should have been the equivalent of:
> 
> git clone https://git.savannah.gnu.org/git/grep.git
> # This is commit 23bf27015e0cc45d0012f54b8e24ac19fdca89f7.
> cd grep
> ./bootstrap
> ./configure --with-included-regex CC='gcc -m32'
> make
> make check

Hello.

I'm attaching build log that leads to the failure.

> 
> and it worked for me; the triple-backref test had an XFAIL and did not loop. Can you send me more-detailed instructions for how to reproduce the bug?
> 
>> I would recommend to replace   DEBUG_ASSERT (num >= 0);
>> which expands to:
>>    ((num >= 0) ? (void) 0 : __builtin_unreachable ());
>>
>> into:
>>
>>    if (num < 0)
>>      __builtin_abort ();
> 
> The regexec.c code doesn't abort, I guess under the theory that one is supposed to fix the code than insert runtime assertions that slow things down. You can compile with -DDEBUG if you want it to abort, but be prepared for other grep tests to fail if you do so. Admittedly this is a messy area.

In this case an infinite loop is highly undesirable. That can justify why the assert
should be transformed into abort. Note that we don't want -DDEBUG for a release
package build of grep.

Thanks,
Martin

[stuck_log.txt.bz2 (application/x-bzip, attachment)]

Message #40 received at 21513 <at> debbugs.gnu.org (full text, mbox):

From: Andreas Schwab <schwab <at> suse.de>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: Martin Liška <mliska <at> suse.cz>, 21513 <at> debbugs.gnu.org
Subject: Re: bug#21513: (now an infinite loop in grep/tests/triple-backref?)
Date: Mon, 20 Jan 2020 12:06:42 +0100

That appears to be a GCC bug with -fprofile-generate.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab <at> suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Message #43 received at 21513 <at> debbugs.gnu.org (full text, mbox):

From: Martin Liška <mliska <at> suse.cz>
To: Andreas Schwab <schwab <at> suse.de>, Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 21513 <at> debbugs.gnu.org
Subject: Re: bug#21513: (now an infinite loop in grep/tests/triple-backref?)
Date: Mon, 20 Jan 2020 12:08:07 +0100

On 1/20/20 12:06 PM, Andreas Schwab wrote:
> That appears to be a GCC bug with -fprofile-generate.

Or a co-incidence of usage of __builtin_unreachable that
can lead to any code optimization (segfault, infinite loop, ...).

Martin

> 
> Andreas.
> 

Message #48 received at 21513-done <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Martin Liška <mliska <at> suse.cz>
Cc: 21513-done <at> debbugs.gnu.org, Andreas Schwab <schwab <at> suse.de>
Subject: Re: bug#21513: (now an infinite loop in grep/tests/triple-backref?)
Date: Mon, 20 Jan 2020 09:50:23 -0800

[Message part 1 (text/plain, inline)]

On 1/20/20 2:49 AM, Martin Liška wrote:
> 
> In this case an infinite loop is highly undesirable.

Sure, but the regex code is littered with highly undesirable code like this, as 
it's easy to use a weird regexp to make the code explode exponentially and 
there's little practical difference between that an infinite loop.

Come to think of it, the grep test infrastructure already has a way to deal with 
this sort of thing, so all we need to do to fix this particular glitch is adjust 
triple-backref to use timeout, which I did by installing the attached patch.

Thanks Andreas for diagnosing the problem. I hope there's a gcc bug report about 
it somewhere. I could not use Martin's recipe on Fedora 31 x86-64 because gcc 
-m32 -flto didn't look inside the .a files that the grep build procedure creates 
and uses. I've never had much luck with -flto anyway as it has a habit of 
running into compiler bugs. I now also see that Red Hat has qualms about the 
GOLD linker <https://fedoraproject.org/wiki/Changes/BINUTILS_GOLD> which the 
recipe relies on, as Google has decided not to continue GOLD development (which 
was news to me).

I'll mark Bug#21513 as done again, since the original report is fixed. The 
triple-backref bug is Bug#22793 and also glibc bug 11053, both of which are 
still open.

[0001-tests-work-around-GCC-fprofile-generate-bug.patch (text/x-patch, attachment)]

Message #51 received at 21513-done <at> debbugs.gnu.org (full text, mbox):

From: Andreas Schwab <schwab <at> suse.de>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 21513-done <at> debbugs.gnu.org, Martin Liška <mliska <at> suse.cz>
Subject: Re: bug#21513: (now an infinite loop in grep/tests/triple-backref?)
Date: Tue, 21 Jan 2020 10:26:58 +0100

On Jan 20 2020, Paul Eggert wrote:

> Thanks Andreas for diagnosing the problem. I hope there's a gcc bug report
> about it somewhere.

It won't, because it's not a GCC bug.  The code invokes undefined
behaviour, so the compiler is entitled to do anything.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab <at> suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.