* bug#2844: infinite loop in boyer_moore()
@ 2009-03-27 3:05 Alexandre Oliva
2009-04-02 7:49 ` Andreas Schwab
0 siblings, 1 reply; 5+ messages in thread
From: Alexandre Oliva @ 2009-03-27 3:05 UTC (permalink / raw)
To: bug-gnu-emacs
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
^ permalink raw reply [flat|nested] 5+ messages in thread
* bug#2844: infinite loop in boyer_moore()
2009-03-27 3:05 Alexandre Oliva
@ 2009-04-02 7:49 ` Andreas Schwab
0 siblings, 0 replies; 5+ messages in thread
From: Andreas Schwab @ 2009-04-02 7:49 UTC (permalink / raw)
To: Alexandre Oliva; +Cc: 2844, bug-gnu-emacs
Alexandre Oliva <oliva@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@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756 01D3 44D5 214B 8276 4ED5
"And now for something completely different."
^ permalink raw reply [flat|nested] 5+ messages in thread
* bug#2844: infinite loop in boyer_moore()
@ 2009-04-02 22:26 Chong Yidong
0 siblings, 0 replies; 5+ messages in thread
From: Chong Yidong @ 2009-04-02 22:26 UTC (permalink / raw)
To: emacs-devel; +Cc: 2844
> 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?
^ permalink raw reply [flat|nested] 5+ messages in thread
* bug#2844: infinite loop in boyer_moore()
[not found] <87eiwaheu9.fsf@cyd.mit.edu>
@ 2009-04-16 4:51 ` Chong Yidong
[not found] ` <87prfdp5em.fsf@cyd.mit.edu>
1 sibling, 0 replies; 5+ messages in thread
From: Chong Yidong @ 2009-04-16 4:51 UTC (permalink / raw)
To: emacs-devel; +Cc: 2844
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?
^ permalink raw reply [flat|nested] 5+ messages in thread
* bug#2844: infinite loop in boyer_moore()
[not found] ` <87prfdp5em.fsf@cyd.mit.edu>
@ 2009-04-16 9:32 ` Andreas Schwab
0 siblings, 0 replies; 5+ messages in thread
From: Andreas Schwab @ 2009-04-16 9:32 UTC (permalink / raw)
To: Chong Yidong; +Cc: 2844, emacs-devel
Chong Yidong <cyd@stupidchicken.com> writes:
> Ping. Anyone have an opinion?
I've now checked in a fix.
Andreas.
--
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756 01D3 44D5 214B 8276 4ED5
"And now for something completely different."
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2009-04-16 9:32 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
[not found] <87eiwaheu9.fsf@cyd.mit.edu>
2009-04-16 4:51 ` bug#2844: infinite loop in boyer_moore() Chong Yidong
[not found] ` <87prfdp5em.fsf@cyd.mit.edu>
2009-04-16 9:32 ` Andreas Schwab
2009-04-02 22:26 Chong Yidong
-- strict thread matches above, loose matches on Subject: below --
2009-03-27 3:05 Alexandre Oliva
2009-04-02 7:49 ` Andreas Schwab
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).