[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: grep-2.9 released [stable]
From: |
Jim Meyering |
Subject: |
Re: grep-2.9 released [stable] |
Date: |
Tue, 28 Jun 2011 14:31:31 +0200 |
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