Re: grep-2.9 released [stable]

[Jim Meyering]

Paolo Bonzini wrote:
> On 06/21/2011 09:04 PM, Jim Meyering wrote:
>> ** Bug fixes
>>
>>    grep no longer clobbers heap for an ERE like '(^| )*( |$)'
>>    [bug introduced in grep-2.6]
>
> I would have thought it had been there "since forever", so I am
> curious. Have you bisected it to a precise commit?

No, but this works fine,

    valgrind grep-2.5.4/bin/grep -Eq '(^| )*(a|b)*(c|d)*( |$)' < /dev/null

while this shows heap corruption:

    valgrind grep-2.6/bin/grep -Eq '(^| )*(a|b)*(c|d)*( |$)' < /dev/null

Even without valgrind, glibc detects it:

    $ grep-2.6/bin/grep -Eq '(^| )*(a|b)*(c|d)*( |$)' < /dev/null
    *** glibc detected *** /p/p/grep-2.6/bin/grep: free(): invalid pointer: 
0x0000000000963df0 ***
    *** glibc detected *** /p/p/grep-2.6/bin/grep: corrupted double-linked 
list: 0x0000000000964760 ***

However, you're right.
It's best to determine precisely where it was introduced, so I did it
(and it was tedious -- several iterations did not build or bootstrap
and required surgery to make things compile).  Here's the offending
commit:

commit 6245829135f68fd77e5ba590650abbe6c350bf42
Author: Paolo Bonzini <address@hidden>
Date:   Wed Dec 23 11:53:46 2009 +0100

    Speed up insert.

    Suggested by Johan Walles <address@hidden> (bug 23354).

    * src/dfa.c (insert): Use binary search.

Studying that and debugging, I discovered the real flaw.
That led me to realize that there was an existing bug
even in the latest dfa.c:

"Positions" were not being sorted!
That means that constraints sometimes were not merged.
I haven't yet tried to construct a case that demonstrates this flaw/fix.
I'll defer pushing this for a day or so in case I find time to add to
the test suite.

I'll add a NEWS entry once I better understand the consequences.


>From 82d5f6e4cf854759fbae3f6d7631209faea03cb1 Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Tue, 28 Jun 2011 14:20:57 +0200
Subject: [PATCH] dfa: fix the root cause of the heap overrun and an
 additional bug

dfa's "insert" function was supposed to be maintaining the position
list sorted on *decreasing* index, but since the 2009-12-09 "Speed
up insert" commit, 62458291, it was using code that assumed the data
were sorted on *increasing* index.  As such, sometimes it would no
longer merge constraints (not finding a match) and would append
entries that normally would have matched and been merged.  These
new, erroneous append operations resulted in the heap overrun fixed
by 2011-06-17 commit 0b91d692 by doubling the array size.
* src/dfa.c (insert): Fix the comparison.
(dfaanalyze): Now that that's fixed, revert commit 0b91d692,
allocating space for only d->nleaves entries, not double that.
---
 src/dfa.c |   10 +++++-----
 1 files changed, 5 insertions(+), 5 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index f2cd198..cdafa41 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -1838,9 +1838,9 @@ copy (position_set const *src, position_set *dst)
   dst->nelem = src->nelem;
 }

-/* Insert a position in a set.  Position sets are maintained in sorted
-   order according to index.  If position already exists in the set with
-   the same index then their constraints are logically or'd together.
+/* Insert position P in set S.  S is maintained in sorted order on
+   decreasing index.  If there is already an entry in S with P.index
+   then merge (logically-OR) P's constraints into the one in S.
    S->elems must point to an array large enough to hold the resulting set. */
 static void
 insert (position p, position_set *s)
@@ -1850,7 +1850,7 @@ insert (position p, position_set *s)
   while (lo < hi)
     {
       int mid = ((unsigned) lo + (unsigned) hi) >> 1;
-      if (s->elems[mid].index < p.index)
+      if (s->elems[mid].index > p.index)
         lo = mid + 1;
       else
         hi = mid;
@@ -2135,7 +2135,7 @@ dfaanalyze (struct dfa *d, int searchflag)
   MALLOC(lastpos, position, d->nleaves);
   o_lastpos = lastpos, lastpos += d->nleaves;
   CALLOC(nalloc, int, d->tindex);
-  MALLOC(merged.elems, position, 2 * d->nleaves);
+  MALLOC(merged.elems, position, d->nleaves);

   CALLOC(d->follows, position_set, d->tindex);

--
1.7.6.rc2.302.gc2115