>From cafb61533f5bfb989698e3924f97471498b2422b Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sun, 13 Sep 2020 18:20:01 -0700 Subject: [PATCH 5/7] dfa: fix dfa-heap-overrun failure * lib/dfa.c (reorder_tokens): When setting map[d->follows[i].elems[j].index], instead of incorrectly assuming that (i < d->follows[i].elems[j].index), use two loops, one to set the map array and the other to use it. The incorrect assumption caused some elements to be missed, and this in turn caused grep's dfa-heap-overrun test to fail on Solaris 10 sparc when compiled with GCC. I found this bug while investigating https://buildfarm.opencsw.org/buildbot/builders/ggrep-solaris10-sparc/builds/183 and I think the bug also occurs on GNU/Linux but with more-subtle symptoms. The bug predates the recent dfa.c changes; perhaps the recent changes make the bug more likely. --- ChangeLog | 15 +++++++++++++++ lib/dfa.c | 12 ++++++------ 2 files changed, 21 insertions(+), 6 deletions(-) diff --git a/ChangeLog b/ChangeLog index a5c14c45e..1b5720761 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,18 @@ +2020-09-13 Paul Eggert + + dfa: fix dfa-heap-overrun failure + * lib/dfa.c (reorder_tokens): When setting + map[d->follows[i].elems[j].index], instead of incorrectly assuming + that (i < d->follows[i].elems[j].index), use two loops, one to set + the map array and the other to use it. The incorrect assumption + caused some elements to be missed, and this in turn caused grep's + dfa-heap-overrun test to fail on Solaris 10 sparc when compiled + with GCC. I found this bug while investigating + https://buildfarm.opencsw.org/buildbot/builders/ggrep-solaris10-sparc/builds/183 + and I think the bug also occurs on GNU/Linux but with more-subtle + symptoms. The bug predates the recent dfa.c changes; perhaps the + recent changes make the bug more likely. + 2020-09-13 Bruno Haible parse-datetime: Make the build rule work with parallel 'make'. diff --git a/lib/dfa.c b/lib/dfa.c index 0f0764887..4992bcaf2 100644 --- a/lib/dfa.c +++ b/lib/dfa.c @@ -2519,6 +2519,11 @@ reorder_tokens (struct dfa *d) else multibyte_prop = NULL; + for (idx_t i = 0; i < d->tindex; i++) + for (idx_t j = 0; j < d->follows[i].nelem; j++) + if (map[d->follows[i].elems[j].index] == -1) + map[d->follows[i].elems[j].index] = nleaves++; + for (idx_t i = 0; i < d->tindex; i++) { if (map[i] == -1) @@ -2537,12 +2542,7 @@ reorder_tokens (struct dfa *d) multibyte_prop[map[i]] = d->multibyte_prop[i]; for (idx_t j = 0; j < d->follows[i].nelem; j++) - { - if (map[d->follows[i].elems[j].index] == -1) - map[d->follows[i].elems[j].index] = nleaves++; - - d->follows[i].elems[j].index = map[d->follows[i].elems[j].index]; - } + d->follows[i].elems[j].index = map[d->follows[i].elems[j].index]; qsort (d->follows[i].elems, d->follows[i].nelem, sizeof *d->follows[i].elems, compare); -- 2.17.1