GNU bug report logs - #2844
infinite loop in boyer_moore()

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 2844 in the body.
You can then email your comments to 2844 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> emacsbugs.donarmstrong.com (full text, mbox):

From: Alexandre Oliva <oliva <at> gnu.org>
To: bug-gnu-emacs <at> gnu.org
Subject: infinite loop in boyer_moore()
Date: Fri, 27 Mar 2009 00:05:34 -0300

https://bugzilla.redhat.com/show_bug.cgi?id=492504

Gnus has been entering infinite loops for me while splitting mail.  Today I got
a chance to look into it.  The problem is in boyer_moore(), in search.c:

    /* Use signed comparison if appropriate
       to make cursor+infinity sure to be > p_limit.
       Assuming that the buffer lies in a range of addresses
       that are all "positive" (as ints) or all "negative",
       either kind of comparison will work as long
       as we don't step by infinity.  So pick the kind
       that works when we do step by infinity.  */
    if ((EMACS_INT) (p_limit + infinity) > (EMACS_INT) p_limit)
      while ((EMACS_INT) cursor <= (EMACS_INT) p_limit)
        cursor += BM_tab[*cursor];
    else
      while ((EMACS_UINT) cursor <= (EMACS_UINT) p_limit)
        cursor += BM_tab[*cursor];

it takes the signed (EMACS_INT) loop, but that fails because cursor is
(unsigned char *) 0x7fffc440, whereas p_limit is (unsigned char *) 0x80001260.

infinity, computed earlier in that function, is 0x37dac21, but I don't see how
a positive value would have helped.  It seems to me that we have to check that
we won't be crossing this boundary starting at cursor rather than p_limit, or
maybe both.  I haven't thought much about it.

I suppose checking that

  (EMACS_INT)(cursor + 20000) > (EMACS_INT)(cursor)

would also be necessary before choosing the EMACS_INT variant of the loop.

In GNU Emacs 22.3.1 (i386-redhat-linux-gnu, GTK+ Version 2.14.7)
 of 2009-02-09 on x86-5.fedora.phx.redhat.com
Windowing system distributor `The X.Org Foundation', version 11.0.10503000
configured using `configure  '--build=i386-redhat-linux-gnu' '--host=i386-redhat-linux-gnu' '--target=i386-redhat-linux-gnu' '--program-prefix=' '--prefix=/usr' '--exec-prefix=/usr' '--bindir=/usr/bin' '--sbindir=/usr/sbin' '--sysconfdir=/etc' '--datadir=/usr/share' '--includedir=/usr/include' '--libdir=/usr/lib' '--libexecdir=/usr/libexec' '--localstatedir=/var' '--sharedstatedir=/usr/com' '--mandir=/usr/share/man' '--infodir=/usr/share/info' '--with-x-toolkit=gtk' 'build_alias=i386-redhat-linux-gnu' 'host_alias=i386-redhat-linux-gnu' 'target_alias=i386-redhat-linux-gnu' 'CFLAGS=-DMAIL_USE_LOCKF -O2 -g -pipe -Wall -Wp,-D_FORTIFY_SOURCE=2 -fexceptions -fstack-protector --param=ssp-buffer-size=4 -m32 -march=i386 -mtune=generic -fasynchronous-unwind-tables''

Important settings:
  value of $LC_ALL: nil
  value of $LC_COLLATE: nil
  value of $LC_CTYPE: nil
  value of $LC_MESSAGES: nil
  value of $LC_MONETARY: nil
  value of $LC_NUMERIC: nil
  value of $LC_TIME: nil
  value of $LANG: en_US.UTF-8
  locale-coding-system: utf-8
  default-enable-multibyte-characters: t


-- 
Alexandre Oliva           http://www.lsd.ic.unicamp.br/~oliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer

Message #10 received at submit <at> emacsbugs.donarmstrong.com (full text, mbox):

From: Andreas Schwab <schwab <at> linux-m68k.org>
To: Alexandre Oliva <oliva <at> gnu.org>
Cc: 2844 <at> debbugs.gnu.org, bug-gnu-emacs <at> gnu.org
Subject: Re: bug#2844: infinite loop in boyer_moore()
Date: Thu, 02 Apr 2009 09:49:54 +0200

Alexandre Oliva <oliva <at> gnu.org> writes:

> I suppose checking that
>
>   (EMACS_INT)(cursor + 20000) > (EMACS_INT)(cursor)
>
> would also be necessary before choosing the EMACS_INT variant of the loop.

That wouldn't help, the compiler will optimize that to true.

Andreas.

-- 
Andreas Schwab, schwab <at> linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Message #22 received at 2844 <at> emacsbugs.donarmstrong.com (full text, mbox):

From: Chong Yidong <cyd <at> stupidchicken.com>
To: emacs-devel <at> gnu.org
Cc: 2844 <at> debbugs.gnu.org
Subject: Re: infinite loop in boyer_moore()
Date: Thu, 02 Apr 2009 18:26:38 -0400

> Gnus has been entering infinite loops for me while splitting mail.
> Today I got a chance to look into it.  The problem is in
> boyer_moore(), in search.c:

>     /* Use signed comparison if appropriate
>        to make cursor+infinity sure to be > p_limit.
>        Assuming that the buffer lies in a range of addresses
>        that are all "positive" (as ints) or all "negative",
>        either kind of comparison will work as long
>        as we don't step by infinity.  So pick the kind
>        that works when we do step by infinity.  */
>     if ((EMACS_INT) (p_limit + infinity) > (EMACS_INT) p_limit)
>       while ((EMACS_INT) cursor <= (EMACS_INT) p_limit)
>         cursor += BM_tab[*cursor];
>     else
>       while ((EMACS_UINT) cursor <= (EMACS_UINT) p_limit)
>         cursor += BM_tab[*cursor];

> it takes the signed (EMACS_INT) loop, but that fails because cursor is
> (unsigned char *) 0x7fffc440, whereas p_limit is (unsigned char *)
> 0x80001260.

> infinity, computed earlier in that function, is 0x37dac21, but I don't
> see how a positive value would have helped.  It seems to me that we
> have to check that we won't be crossing this boundary starting at
> cursor rather than p_limit, or maybe both.  I haven't thought much
> about it.

Checking with cursor as well as p_limit sounds about right to be, but I
am far from familiar with this part of the code.  Does anyone one this
list have an opinion?

Message #27 received at 2844 <at> emacsbugs.donarmstrong.com (full text, mbox):

From: Chong Yidong <cyd <at> stupidchicken.com>
To: emacs-devel <at> gnu.org
Cc: 2844 <at> debbugs.gnu.org
Subject: Re: infinite loop in boyer_moore()
Date: Thu, 16 Apr 2009 00:51:45 -0400

Ping.  Anyone have an opinion?

>> Gnus has been entering infinite loops for me while splitting mail.
>> Today I got a chance to look into it.  The problem is in
>> boyer_moore(), in search.c:
>
>>     /* Use signed comparison if appropriate
>>        to make cursor+infinity sure to be > p_limit.
>>        Assuming that the buffer lies in a range of addresses
>>        that are all "positive" (as ints) or all "negative",
>>        either kind of comparison will work as long
>>        as we don't step by infinity.  So pick the kind
>>        that works when we do step by infinity.  */
>>     if ((EMACS_INT) (p_limit + infinity) > (EMACS_INT) p_limit)
>>       while ((EMACS_INT) cursor <= (EMACS_INT) p_limit)
>>         cursor += BM_tab[*cursor];
>>     else
>>       while ((EMACS_UINT) cursor <= (EMACS_UINT) p_limit)
>>         cursor += BM_tab[*cursor];
>
>> it takes the signed (EMACS_INT) loop, but that fails because cursor is
>> (unsigned char *) 0x7fffc440, whereas p_limit is (unsigned char *)
>> 0x80001260.
>
>> infinity, computed earlier in that function, is 0x37dac21, but I don't
>> see how a positive value would have helped.  It seems to me that we
>> have to check that we won't be crossing this boundary starting at
>> cursor rather than p_limit, or maybe both.  I haven't thought much
>> about it.
>
> Checking with cursor as well as p_limit sounds about right to be, but I
> am far from familiar with this part of the code.  Does anyone one this
> list have an opinion?

Message #32 received at 2844 <at> emacsbugs.donarmstrong.com (full text, mbox):

From: Andreas Schwab <schwab <at> linux-m68k.org>
To: Chong Yidong <cyd <at> stupidchicken.com>
Cc: emacs-devel <at> gnu.org, 2844 <at> debbugs.gnu.org
Subject: Re: infinite loop in boyer_moore()
Date: Thu, 16 Apr 2009 11:32:38 +0200

Chong Yidong <cyd <at> stupidchicken.com> writes:

> Ping.  Anyone have an opinion?

I've now checked in a fix.

Andreas.

-- 
Andreas Schwab, schwab <at> linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Message #37 received at 2844-done <at> emacsbugs.donarmstrong.com (full text, mbox):

From: Chong Yidong <cyd <at> stupidchicken.com>
To: Andreas Schwab <schwab <at> linux-m68k.org>
Cc: emacs-devel <at> gnu.org, 2844-done <at> debbugs.gnu.org
Subject: Re: infinite loop in boyer_moore()
Date: Thu, 16 Apr 2009 09:42:24 -0400

Andreas Schwab <schwab <at> linux-m68k.org> writes:

>> Ping.  Anyone have an opinion?
>
> I've now checked in a fix.
>
> Andreas.

Thanks.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.