Bug 492504 - infinite loop in boyer_moore() at 0x7fffffff/0x80000000 boundary
Summary: infinite loop in boyer_moore() at 0x7fffffff/0x80000000 boundary
Alias: None
Product: Fedora
Classification: Fedora
Component: emacs
Version: 11
Hardware: All
OS: Linux
Target Milestone: ---
Assignee: Daniel Novotny
QA Contact: Fedora Extras Quality Assurance
Depends On:
TreeView+ depends on / blocked
Reported: 2009-03-27 02:35 UTC by Alexandre Oliva
Modified: 2009-08-11 22:36 UTC (History)
3 users (show)

Fixed In Version: 23.1-1.fc11
Doc Type: Bug Fix
Doc Text:
Clone Of:
Last Closed: 2009-08-11 22:36:41 UTC

Attachments (Terms of Use)

Description Alexandre Oliva 2009-03-27 02:35:02 UTC
Description of problem:
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];
		    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.

Version-Release number of selected component (if applicable):

How reproducible:
Not much.  It happens at random, because of address space randomization.  Most often it hits when splitting a lot of email.

Comment 1 Alexandre Oliva 2009-03-27 03:07:07 UTC
I think adding '&& (EMACS_INT)(cursor + 20000) < (EMACS_INT)cursor', or replacing p_limit for cursor in the test, might fix this.  FWIW, I've got this while searching large buffers interactively too, not only when splitting mail with gnus.  I just hadn't realized it was just different symptoms of the same problem.

Comment 2 Daniel Novotny 2009-03-27 11:17:30 UTC
what about adding "&& (EMACS_INT) cursor < (EMACS_INT) p_limit"
to the first "if" ?

Comment 3 Alexandre Oliva 2009-03-27 14:57:30 UTC
This would certainly fix this particular case, but I'm not entirely sure it wouldn't break others.  I reported this upstream, let's see what upstream maintainers have to say...

Comment 4 Alexandre Oliva 2009-04-18 03:23:00 UTC
I believe the upstream patch that fixes the bug is http://cvs.savannah.gnu.org/viewvc/emacs/src/search.c?root=emacs&r1=1.238&r2=1.239, although http://cvs.savannah.gnu.org/viewvc/emacs/src/search.c?root=emacs&r1=1.239&r2=1.240 might be needed as well.

Comment 5 Alexandre Oliva 2009-07-29 16:30:16 UTC
This still hits Fedora 11, and there's a patch.  Is it too hard to integrate it?  Can I help?

Comment 6 Daniel Novotny 2009-08-03 08:41:05 UTC
hello, I will update F11 emacs to 23.1, which contains the fix for the bug

Comment 7 Fedora Update System 2009-08-03 09:51:30 UTC
emacs-23.1-1.fc11 has been submitted as an update for Fedora 11.

Comment 8 Fedora Update System 2009-08-03 19:24:41 UTC
emacs-23.1-1.fc11 has been pushed to the Fedora 11 testing repository.  If problems still persist, please make note of it in this bug report.
 If you want to test the update, you can install it with 
 su -c 'yum --enablerepo=updates-testing update emacs'.  You can provide feedback for this update here: http://admin.fedoraproject.org/updates/F11/FEDORA-2009-8245

Comment 9 Fedora Update System 2009-08-11 22:36:26 UTC
emacs-23.1-1.fc11 has been pushed to the Fedora 11 stable repository.  If problems still persist, please make note of it in this bug report.

Note You need to log in before you can comment on or make changes to this bug.