From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: owner@emacsbugs.donarmstrong.com (Emacs bug Tracking System) Newsgroups: gmane.emacs.bugs Subject: bug#2844: marked as done (infinite loop in boyer_moore()) Date: Thu, 16 Apr 2009 13:50:07 +0000 Message-ID: References: <87fxg8btq7.fsf@cyd.mit.edu> <200903270305.n2R35Y8N032009@livre.oliva.athome.lsd.ic.unicamp.br> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----------=_1239889807-17455-0" X-Trace: ger.gmane.org 1239890712 587 80.91.229.12 (16 Apr 2009 14:05:12 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 16 Apr 2009 14:05:12 +0000 (UTC) To: Chong Yidong Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Thu Apr 16 16:06:31 2009 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1LuSDd-0000gQ-FJ for geb-bug-gnu-emacs@m.gmane.org; Thu, 16 Apr 2009 16:05:57 +0200 Original-Received: from localhost ([127.0.0.1]:48838 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1LuSCD-0002bO-JH for geb-bug-gnu-emacs@m.gmane.org; Thu, 16 Apr 2009 10:04:05 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1LuSC9-0002ax-5q for bug-gnu-emacs@gnu.org; Thu, 16 Apr 2009 10:04:01 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1LuSC4-0002ZH-F6 for bug-gnu-emacs@gnu.org; Thu, 16 Apr 2009 10:04:00 -0400 Original-Received: from [199.232.76.173] (port=58223 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1LuSC4-0002ZA-6e for bug-gnu-emacs@gnu.org; Thu, 16 Apr 2009 10:03:56 -0400 Original-Received: from rzlab.ucr.edu ([138.23.92.77]:54475) by monty-python.gnu.org with esmtps (TLS-1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1LuSC3-0001p2-9i for bug-gnu-emacs@gnu.org; Thu, 16 Apr 2009 10:03:55 -0400 Original-Received: from rzlab.ucr.edu (rzlab.ucr.edu [127.0.0.1]) by rzlab.ucr.edu (8.13.8/8.13.8/Debian-3) with ESMTP id n3GE3pak021217; Thu, 16 Apr 2009 07:03:52 -0700 Original-Received: (from debbugs@localhost) by rzlab.ucr.edu (8.13.8/8.13.8/Submit) id n3GDo7at017602; Thu, 16 Apr 2009 06:50:07 -0700 X-Mailer: MIME-tools 5.420 (Entity 5.420) X-Loop: owner@emacsbugs.donarmstrong.com X-Emacs-PR-Message: closed 2844 X-Emacs-PR-Package: emacs X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 3) X-BeenThere: bug-gnu-emacs@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:27236 Archived-At: This is a multi-part message in MIME format... ------------=_1239889807-17455-0 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 Your message dated Thu, 16 Apr 2009 09:42:24 -0400 with message-id <87fxg8btq7.fsf@cyd.mit.edu> and subject line Re: infinite loop in boyer_moore() has caused the Emacs bug report #2844, regarding infinite loop in boyer_moore() to be marked as done. This means that you claim that the problem has been dealt with. If this is not the case it is now your responsibility to reopen the bug report if necessary, and/or fix the problem forthwith. (NB: If you are a system administrator and have no idea what this message is talking about, this may indicate a serious mail system misconfiguration somewhere. Please contact owner@emacsbugs.donarmstrong.com immediately.) --=20 2844: http://emacsbugs.donarmstrong.com/cgi-bin/bugreport.cgi?bug=3D2844 Emacs Bug Tracking System Contact owner@emacsbugs.donarmstrong.com with problems ------------=_1239889807-17455-0 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by emacsbugs.donarmstrong.com; 1 Apr 2009 20:10:45 +0000 X-Spam-Checker-Version: SpamAssassin 3.2.5-bugs.debian.org_2005_01_02 (2008-06-10) on rzlab.ucr.edu X-Spam-Level: * X-Spam-Bayes: score:0.5 Bayes not run. spammytokens:Tokens not available. hammytokens:Tokens not available. X-Spam-Status: No, score=1.1 required=4.0 tests=FOURLA,IMPRONONCABLE_2 autolearn=no version=3.2.5-bugs.debian.org_2005_01_02 Received: from lists.gnu.org (lists.gnu.org [199.232.76.165]) by rzlab.ucr.edu (8.13.8/8.13.8/Debian-3) with ESMTP id n31KAfRA021259 for ; Wed, 1 Apr 2009 13:10:43 -0700 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1Lp6lk-00042r-Js for bug-gnu-emacs@gnu.org; Wed, 01 Apr 2009 16:10:40 -0400 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1Lp6lg-00040D-1r for bug-gnu-emacs@gnu.org; Wed, 01 Apr 2009 16:10:40 -0400 Received: from [199.232.76.173] (port=39057 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Lp6lf-000409-Sa for bug-gnu-emacs@gnu.org; Wed, 01 Apr 2009 16:10:35 -0400 Received: from lsd-gw.ic.unicamp.br ([143.106.7.165]:59811 helo=boneca.lsd.ic.unicamp.br) by monty-python.gnu.org with esmtps (TLS-1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1Lp6lb-0005eS-EH; Wed, 01 Apr 2009 16:10:32 -0400 Received: from freie.oliva.athome.lsd.ic.unicamp.br (gw-to-emilia.oliva.athome.lsd.ic.unicamp.br [172.31.160.17] (may be forged)) by boneca.lsd.ic.unicamp.br (8.14.2/8.14.2) with ESMTP id n31KAQBs016894; Wed, 1 Apr 2009 17:10:26 -0300 Received: from localhost.localdomain (free.oliva.athome.lsd.ic.unicamp.br [172.31.160.1]) by freie.oliva.athome.lsd.ic.unicamp.br (8.14.3/8.14.3) with ESMTP id n31KAQld032298; Wed, 1 Apr 2009 17:10:26 -0300 Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by localhost.localdomain (8.14.3/8.14.3) with ESMTP id n31KAQ64031785; Wed, 1 Apr 2009 17:10:26 -0300 Received: (from aoliva@localhost) by localhost.localdomain (8.14.3/8.14.3/Submit) id n31KAQtL031784; Wed, 1 Apr 2009 17:10:26 -0300 Resent-To: bug-gnu-emacs@gnu.org, oliva@gnu.org Resent-From: Alexandre Oliva Resent-Date: Wed, 01 Apr 2009 17:10:25 -0300 Resent-Message-ID: Received: from livre.oliva.athome.lsd.ic.unicamp.br (localhost.localdomain [127.0.0.1]) by livre.oliva.athome.lsd.ic.unicamp.br (8.14.3/8.14.3) with ESMTP id n2R35YKi032013; Fri, 27 Mar 2009 00:05:35 -0300 Received: (from aoliva@localhost) by livre.oliva.athome.lsd.ic.unicamp.br (8.14.3/8.14.3/Submit) id n2R35Y8N032009; Fri, 27 Mar 2009 00:05:34 -0300 Date: Fri, 27 Mar 2009 00:05:34 -0300 Message-Id: <200903270305.n2R35Y8N032009@livre.oliva.athome.lsd.ic.unicamp.br> From: Alexandre Oliva To: bug-gnu-emacs@gnu.org Subject: infinite loop in boyer_moore() MIME-Version: 1.0 X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 3) Resent-Date: Wed, 01 Apr 2009 16:10:40 -0400 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 ------------=_1239889807-17455-0 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 2844-done) by emacsbugs.donarmstrong.com; 16 Apr 2009 13:40:38 +0000 X-Spam-Checker-Version: SpamAssassin 3.2.5-bugs.debian.org_2005_01_02 (2008-06-10) on rzlab.ucr.edu X-Spam-Level: X-Spam-Bayes: score:0.5 Bayes not run. spammytokens:Tokens not available. hammytokens:Tokens not available. X-Spam-Status: No, score=0.0 required=4.0 tests=none autolearn=ham version=3.2.5-bugs.debian.org_2005_01_02 Received: from cyd.mit.edu (CYD.MIT.EDU [18.115.2.24]) by rzlab.ucr.edu (8.13.8/8.13.8/Debian-3) with ESMTP id n3GDeZXd015434 for <2844-done@emacsbugs.donarmstrong.com>; Thu, 16 Apr 2009 06:40:36 -0700 Received: by cyd.mit.edu (Postfix, from userid 1000) id 3474A57E247; Thu, 16 Apr 2009 09:42:24 -0400 (EDT) From: Chong Yidong To: Andreas Schwab Cc: emacs-devel@gnu.org, 2844-done@emacsbugs.donarmstrong.com Subject: Re: infinite loop in boyer_moore() References: <87eiwaheu9.fsf@cyd.mit.edu> <87prfdp5em.fsf@cyd.mit.edu> Date: Thu, 16 Apr 2009 09:42:24 -0400 In-Reply-To: (Andreas Schwab's message of "Thu, 16 Apr 2009 11:32:38 +0200") Message-ID: <87fxg8btq7.fsf@cyd.mit.edu> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.91 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Andreas Schwab writes: >> Ping. Anyone have an opinion? > > I've now checked in a fix. > > Andreas. Thanks. ------------=_1239889807-17455-0--