* 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 <egg...@cs.ucla.edu> + + 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 <br...@clisp.org> 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
