On Sun, 13 Sep 2020 18:41:49 -0700 Paul Eggert <egg...@cs.ucla.edu> wrote:
> * 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 > Thanks for adjusting and fixing. I don't know why your patch fixes the bug. When setting map[d->follows[i].elems[j].index], the assumption that (i < d->follows[i].elems[j].index) is incorrect. However when (i >= d->follows[i].elems[j].index), it seems that map[d->follows[i].elems[j].index] has been already set a value more than 0. What case violates this assumption? In fact, in dfa-heap-overrun test, assign as following sequencely. It seems that follows the assumption and it does not crush. 0:BEG 1:BEGLINE 2:0x20 3:OR 4:STAR 5:0x61 6:0x62 7:OR 8:STAR 9:CAT 10:0x63 11:0x64 12:OR 13:STAR 14:CAT 15:0x20 16:ENDLINE 17:OR 18:CAT 19:END 20:CAT 21:CAT at i = 0 d->follows[0].elems[0].index = 2 -> map[2] = 1 d->follows[0].elems[1].index = 5 -> map[5] = 2 d->follows[0].elems[2].index = 6 -> map[6] = 3 d->follows[0].elems[3].index = 10 -> map[10] = 4 d->follows[0].elems[4].index = 11 -> map[11] = 5 d->follows[0].elems[5].index = 15 -> map[15] = 6 Thanks, Norihiro
