From unknown Sun Jun 15 08:43:06 2025 X-Loop: owner@emacsbugs.donarmstrong.com Subject: bug#2844: infinite loop in boyer_moore() Reply-To: Alexandre Oliva , 2844@debbugs.gnu.org Resent-From: Alexandre Oliva Resent-To: bug-submit-list@lists.donarmstrong.com Resent-CC: Emacs Bugs Resent-Date: Wed, 01 Apr 2009 20:15:03 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-Emacs-PR-Message: report 2844 X-Emacs-PR-Package: emacs X-Emacs-PR-Keywords: Received: via spool by submit@emacsbugs.donarmstrong.com id=B.123861664521265 (code B ref -1); Wed, 01 Apr 2009 20:15:03 +0000 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 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 From unknown Sun Jun 15 08:43:06 2025 X-Loop: owner@emacsbugs.donarmstrong.com Subject: bug#2844: infinite loop in boyer_moore() Reply-To: Andreas Schwab , 2844@debbugs.gnu.org Resent-From: Andreas Schwab Resent-To: bug-submit-list@lists.donarmstrong.com Resent-CC: Emacs Bugs Resent-Date: Thu, 02 Apr 2009 07:55:05 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-Emacs-PR-Message: followup 2844 X-Emacs-PR-Package: emacs X-Emacs-PR-Keywords: Received: via spool by submit@emacsbugs.donarmstrong.com id=B.123865861318312 (code B ref -1); Thu, 02 Apr 2009 07:55:05 +0000 Received: (at submit) by emacsbugs.donarmstrong.com; 2 Apr 2009 07:50:13 +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=-3.0 required=4.0 tests=HAS_BUG_NUMBER autolearn=ham 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 n327o9dT017946 for ; Thu, 2 Apr 2009 00:50:10 -0700 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1LpHgf-0004Eq-1l for bug-gnu-emacs@gnu.org; Thu, 02 Apr 2009 03:50:09 -0400 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1LpHgZ-0004Dp-CE for bug-gnu-emacs@gnu.org; Thu, 02 Apr 2009 03:50:07 -0400 Received: from [199.232.76.173] (port=37123 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1LpHgZ-0004Df-0F for bug-gnu-emacs@gnu.org; Thu, 02 Apr 2009 03:50:03 -0400 Received: from mail-out.m-online.net ([212.18.0.9]:59743) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1LpHgU-0004sH-Hz; Thu, 02 Apr 2009 03:49:58 -0400 Received: from mail01.m-online.net (mail.m-online.net [192.168.3.149]) by mail-out.m-online.net (Postfix) with ESMTP id A5E561C15301; Thu, 2 Apr 2009 09:53:04 +0200 (CEST) Received: from localhost (dynscan2.mnet-online.de [192.168.1.215]) by mail.m-online.net (Postfix) with ESMTP id B899E901A7; Thu, 2 Apr 2009 09:49:56 +0200 (CEST) X-Virus-Scanned: amavisd-new at mnet-online.de Received: from mail.mnet-online.de ([192.168.3.149]) by localhost (dynscan2.mnet-online.de [192.168.1.215]) (amavisd-new, port 10024) with ESMTP id WQ4RorOP4tpL; Thu, 2 Apr 2009 09:49:55 +0200 (CEST) Received: from igel.home (DSL01.83.171.170.81.ip-pool.NEFkom.net [83.171.170.81]) by mail.mnet-online.de (Postfix) with ESMTP; Thu, 2 Apr 2009 09:49:55 +0200 (CEST) Received: by igel.home (Postfix, from userid 501) id 8103810D832; Thu, 2 Apr 2009 09:49:54 +0200 (CEST) From: Andreas Schwab To: Alexandre Oliva Cc: 2844@debbugs.gnu.org, bug-gnu-emacs@gnu.org References: <200903270305.n2R35Y8N032009@livre.oliva.athome.lsd.ic.unicamp.br> X-Yow: CHUBBY CHECKER owns my BUILDING! Date: Thu, 02 Apr 2009 09:49:54 +0200 In-Reply-To: <200903270305.n2R35Y8N032009@livre.oliva.athome.lsd.ic.unicamp.br> (Alexandre Oliva's message of "Fri, 27 Mar 2009 00:05:34 -0300") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.92 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6, seldom 2.4 (older, 4) Alexandre Oliva 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." From cyd@stupidchicken.com Thu Apr 2 06:27:44 2009 Received: (at control) by emacsbugs.donarmstrong.com; 2 Apr 2009 13:27:44 +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=-2.0 required=4.0 tests=VALID_BTS_CONTROL 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 n32DRgql014970 for ; Thu, 2 Apr 2009 06:27:43 -0700 Received: by cyd.mit.edu (Postfix, from userid 1000) id 0DB9A57E21E; Thu, 2 Apr 2009 09:29:18 -0400 (EDT) From: Chong Yidong To: control@debbugs.gnu.org Subject: severity 2844 serious Date: Thu, 02 Apr 2009 09:29:18 -0400 Message-ID: <8763hnmbf5.fsf@cyd.mit.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii severity 2844 serious thanks From unknown Sun Jun 15 08:43:06 2025 X-Loop: owner@emacsbugs.donarmstrong.com Subject: bug#2844: infinite loop in boyer_moore() Reply-To: Chong Yidong , 2844@debbugs.gnu.org Resent-From: Chong Yidong Resent-To: bug-submit-list@lists.donarmstrong.com Resent-CC: Emacs Bugs Resent-Date: Thu, 02 Apr 2009 22:30:03 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-Emacs-PR-Message: followup 2844 X-Emacs-PR-Package: emacs X-Emacs-PR-Keywords: Received: via spool by 2844-submit@emacsbugs.donarmstrong.com id=B2844.12387111066074 (code B ref 2844); Thu, 02 Apr 2009 22:30:03 +0000 Received: (at 2844) by emacsbugs.donarmstrong.com; 2 Apr 2009 22:25:06 +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.0 required=4.0 tests=IMPRONONCABLE_2 autolearn=no 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 n32MP2De005799 for <2844@emacsbugs.donarmstrong.com>; Thu, 2 Apr 2009 15:25:03 -0700 Received: by cyd.mit.edu (Postfix, from userid 1000) id E650457E21E; Thu, 2 Apr 2009 18:26:38 -0400 (EDT) From: Chong Yidong To: emacs-devel@gnu.org Cc: 2844@debbugs.gnu.org Date: Thu, 02 Apr 2009 18:26:38 -0400 Message-ID: <87eiwaheu9.fsf@cyd.mit.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii > 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? From unknown Sun Jun 15 08:43:06 2025 X-Loop: owner@emacsbugs.donarmstrong.com Subject: bug#2844: infinite loop in boyer_moore() Reply-To: Chong Yidong , 2844@debbugs.gnu.org Resent-From: Chong Yidong Resent-To: bug-submit-list@lists.donarmstrong.com Resent-CC: Emacs Bugs Resent-Date: Thu, 16 Apr 2009 04:55:05 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-Emacs-PR-Message: followup 2844 X-Emacs-PR-Package: emacs X-Emacs-PR-Keywords: Received: via spool by 2844-submit@emacsbugs.donarmstrong.com id=B2844.123985739928190 (code B ref 2844); Thu, 16 Apr 2009 04:55:05 +0000 Received: (at 2844) by emacsbugs.donarmstrong.com; 16 Apr 2009 04:49:59 +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.0 required=4.0 tests=IMPRONONCABLE_2 autolearn=no 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 n3G4numC028184 for <2844@emacsbugs.donarmstrong.com>; Wed, 15 Apr 2009 21:49:58 -0700 Received: by cyd.mit.edu (Postfix, from userid 1000) id 51DAD57E245; Thu, 16 Apr 2009 00:51:45 -0400 (EDT) From: Chong Yidong To: emacs-devel@gnu.org Cc: 2844@debbugs.gnu.org References: <87eiwaheu9.fsf@cyd.mit.edu> Date: Thu, 16 Apr 2009 00:51:45 -0400 In-Reply-To: <87eiwaheu9.fsf@cyd.mit.edu> (Chong Yidong's message of "Thu, 02 Apr 2009 18:26:38 -0400") Message-ID: <87prfdp5em.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 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? From unknown Sun Jun 15 08:43:06 2025 X-Loop: owner@emacsbugs.donarmstrong.com Subject: bug#2844: infinite loop in boyer_moore() Reply-To: Andreas Schwab , 2844@debbugs.gnu.org Resent-From: Andreas Schwab Resent-To: bug-submit-list@lists.donarmstrong.com Resent-CC: Emacs Bugs Resent-Date: Thu, 16 Apr 2009 09:40:06 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-Emacs-PR-Message: followup 2844 X-Emacs-PR-Package: emacs X-Emacs-PR-Keywords: Received: via spool by 2844-submit@emacsbugs.donarmstrong.com id=B2844.12398743716478 (code B ref 2844); Thu, 16 Apr 2009 09:40:06 +0000 Received: (at 2844) by emacsbugs.donarmstrong.com; 16 Apr 2009 09:32:51 +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 mail-out.m-online.net (mail-out.m-online.net [212.18.0.9]) by rzlab.ucr.edu (8.13.8/8.13.8/Debian-3) with ESMTP id n3G9WluR006472 for <2844@emacsbugs.donarmstrong.com>; Thu, 16 Apr 2009 02:32:49 -0700 Received: from mail01.m-online.net (mail.m-online.net [192.168.3.149]) by mail-out.m-online.net (Postfix) with ESMTP id 10D811C153B6; Thu, 16 Apr 2009 11:36:55 +0200 (CEST) Received: from localhost (dynscan2.mnet-online.de [192.168.1.215]) by mail.m-online.net (Postfix) with ESMTP id 7B317901A1; Thu, 16 Apr 2009 11:32:41 +0200 (CEST) X-Virus-Scanned: amavisd-new at mnet-online.de Received: from mail.mnet-online.de ([192.168.3.149]) by localhost (dynscan2.mnet-online.de [192.168.1.215]) (amavisd-new, port 10024) with ESMTP id KNP5JY3xDktf; Thu, 16 Apr 2009 11:32:40 +0200 (CEST) Received: from igel.home (DSL01.83.171.182.115.ip-pool.NEFkom.net [83.171.182.115]) by mail.mnet-online.de (Postfix) with ESMTP; Thu, 16 Apr 2009 11:32:40 +0200 (CEST) Received: by igel.home (Postfix, from userid 501) id A396410D91E; Thu, 16 Apr 2009 11:32:38 +0200 (CEST) From: Andreas Schwab To: Chong Yidong Cc: emacs-devel@gnu.org, 2844@debbugs.gnu.org References: <87eiwaheu9.fsf@cyd.mit.edu> <87prfdp5em.fsf@cyd.mit.edu> X-Yow: I want a VEGETARIAN BURRITO to go.. with EXTRA MSG!! Date: Thu, 16 Apr 2009 11:32:38 +0200 In-Reply-To: <87prfdp5em.fsf@cyd.mit.edu> (Chong Yidong's message of "Thu, 16 Apr 2009 00:51:45 -0400") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.92 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Chong Yidong 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." From unknown Sun Jun 15 08:43:06 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.420 (Entity 5.420) X-Loop: owner@emacsbugs.donarmstrong.com From: help-debbugs@gnu.org (Emacs bug Tracking System) To: Alexandre Oliva Subject: bug#2844 closed by Chong Yidong (Re: infinite loop in boyer_moore()) Message-ID: References: <87fxg8btq7.fsf@cyd.mit.edu> <200903270305.n2R35Y8N032009@livre.oliva.athome.lsd.ic.unicamp.br> X-Emacs-PR-Message: they-closed 2844 X-Emacs-PR-Package: emacs Reply-To: 2844@debbugs.gnu.org Date: Thu, 16 Apr 2009 13:50:07 +0000 Content-Type: multipart/mixed; boundary="----------=_1239889807-17455-1" This is a multi-part message in MIME format... ------------=_1239889807-17455-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" This is an automatic notification regarding your bug report which was filed against the emacs package: #2844: infinite loop in boyer_moore() It has been closed by Chong Yidong . Their explanation is attached below along with your original report. If this explanation is unsatisfactory and you have not received a better one in a separate message then please contact Chong Yidong by replying to this email. --=20 2844: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D2844 Emacs Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1239889807-17455-1 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@debbugs.gnu.org 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-1 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-1--