From unknown Sat Aug 09 15:54:57 2025 X-Loop: help-debbugs@gnu.org Subject: bug#23983: [PATCH] grep: fix crash with a pattern of alternation of two same characters Resent-From: Norihiro Tanaka Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Thu, 14 Jul 2016 15:08:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 23983 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: 23983@debbugs.gnu.org X-Debbugs-Original-To: Received: via spool by submit@debbugs.gnu.org id=B.146850886612935 (code B ref -1); Thu, 14 Jul 2016 15:08:01 +0000 Received: (at submit) by debbugs.gnu.org; 14 Jul 2016 15:07:46 +0000 Received: from localhost ([127.0.0.1]:51572 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bNiEr-0003MY-Km for submit@debbugs.gnu.org; Thu, 14 Jul 2016 11:07:45 -0400 Received: from eggs.gnu.org ([208.118.235.92]:59789) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bNiEq-0003ML-0R for submit@debbugs.gnu.org; Thu, 14 Jul 2016 11:07:44 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bNiEh-0005lP-NI for submit@debbugs.gnu.org; Thu, 14 Jul 2016 11:07:38 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:60123) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bNiEh-0005l3-KX for submit@debbugs.gnu.org; Thu, 14 Jul 2016 11:07:35 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:50715) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bNiEc-0003qu-Uq for bug-grep@gnu.org; Thu, 14 Jul 2016 11:07:33 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bNiEX-0005hX-OQ for bug-grep@gnu.org; Thu, 14 Jul 2016 11:07:29 -0400 Received: from mailgw01.kcn.ne.jp ([61.86.7.208]:35616) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bNiEX-0005fr-7n for bug-grep@gnu.org; Thu, 14 Jul 2016 11:07:25 -0400 Received: from mxs01-s (mailgw1.kcn.ne.jp [61.86.15.233]) by mailgw01.kcn.ne.jp (Postfix) with ESMTP id 11C6A4A0831 for ; Fri, 15 Jul 2016 00:07:14 +0900 (JST) X-matriXscan-loop-detect: 722934c84a705b8d72b04fef7c04bec65a8895b7 Received: from mail02.kcn.ne.jp ([61.86.6.181]) by mxs01-s with ESMTP; Fri, 15 Jul 2016 00:07:13 +0900 (JST) Received: from [10.120.1.7] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail02.kcn.ne.jp (Postfix) with ESMTPA id B4BC2BE8001 for ; Fri, 15 Jul 2016 00:07:13 +0900 (JST) Date: Fri, 15 Jul 2016 00:07:13 +0900 From: Norihiro Tanaka Message-Id: <20160715000700.D850.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_5787A8F300000000D844_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-matriXscan-Sophos-AV: Clean X-matriXscan-Action: Approve X-matriXscan: Uncategorized X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.0 (----) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -4.0 (----) --------_5787A8F300000000D844_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Current master crashes with below. $ printf '0\n0' >pat $ printf '0\n' >in $ env LC_ALL=C grep -F pat in grep -F uses memchr2() for each character in this pattern, but if two characters is same, the trie has no child. --------_5787A8F300000000D844_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="0001-grep-fix-crash-with-a-pattern-of-alternation-of-two-.patch" Content-Disposition: attachment; filename="0001-grep-fix-crash-with-a-pattern-of-alternation-of-two-.patch" Content-Transfer-Encoding: base64 RnJvbSAzYjAwNGE2NmNjOWRjNjZhZDYyMTExYmMzOGIyYzVhMmI4YmIwODJjIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBUaHUsIDE0IEp1bCAyMDE2IDIzOjQ1OjQ1ICswOTAwClN1YmplY3Q6IFtQQVRDSF0gZ3Jl cDogZml4IGNyYXNoIHdpdGggYSBwYXR0ZXJuIG9mIGFsdGVybmF0aW9uIG9mIHR3byBzYW1lIGNo YXJhY3RlcnMKCmdyZXAgLUYgY3Jhc2hlcyB3aXRoIHBhdHRlcm4gYXMgMFxuMC4gIFRoaXMgYnVn IGlzIGludHJvZHVjZWQgaW4KOTY2ZjY1ODZmYmNlMzA4MWNlNmU1ZTJmOWI1NTMwMWIwZWMzZDJi NC4KCiogc3JjL2t3c2V0LmMgKG1lbW9mZjJfa3dzZXQpOiBJZiB0d28gY2hhcmFjdGVycyBpcyBz YW1lLCBtZW1jaHIgaW5zdGVhZApvZiBtZW1jaHIyLgoqIHRlc3RzL3R3by1jaGFyczogTmV3IHRl c3QuCiogdGVzdHMvTWFrZWZpbGUuYW0gKFRFU1RTKTogQWRkIGl0LgotLS0KIHNyYy9rd3NldC5j ICAgICAgIHwgICAgNyArKysrKystCiB0ZXN0cy9NYWtlZmlsZS5hbSB8ICAgIDEgKwogdGVzdHMv dHdvLWNoYXJzICAgfCAgIDI1ICsrKysrKysrKysrKysrKysrKysrKysrKysKIDMgZmlsZXMgY2hh bmdlZCwgMzIgaW5zZXJ0aW9ucygrKSwgMSBkZWxldGlvbnMoLSkKIGNyZWF0ZSBtb2RlIDEwMDc1 NSB0ZXN0cy90d28tY2hhcnMKCmRpZmYgLS1naXQgYS9zcmMva3dzZXQuYyBiL3NyYy9rd3NldC5j CmluZGV4IDczOTE5OTAuLjgwZGY3NTIgMTAwNjQ0Ci0tLSBhL3NyYy9rd3NldC5jCisrKyBiL3Ny Yy9rd3NldC5jCkBAIC02NDMsOCArNjQzLDEzIEBAIG1lbW9mZjJfa3dzZXQgKGNoYXIgY29uc3Qg KnMsIHNpemVfdCBuLCBrd3NldF90IGt3c2V0LAogewogICBzdHJ1Y3QgdHJlZSBjb25zdCAqbGlu ayA9IGt3c2V0LT50cmllLT5saW5rczsKICAgc3RydWN0IHRyZWUgY29uc3QgKmNsaW5rID0gbGlu ay0+bGxpbmsgPyBsaW5rLT5sbGluayA6IGxpbmstPnJsaW5rOworICBjaGFyIGNvbnN0ICptY2g7 CisKKyAgaWYgKGNsaW5rKQorICAgIG1jaCA9IG1lbWNocjIgKHMsIGxpbmstPmxhYmVsLCBjbGlu ay0+bGFiZWwsIG4pOworICBlbHNlCisgICAgbWNoID0gbWVtY2hyIChzLCBsaW5rLT5sYWJlbCwg bik7CiAKLSAgY2hhciBjb25zdCAqbWNoID0gbWVtY2hyMiAocywgbGluay0+bGFiZWwsIGNsaW5r LT5sYWJlbCwgbik7CiAgIGlmICghIG1jaCkKICAgICByZXR1cm4gU0laRV9NQVg7CiAgIGVsc2UK ZGlmZiAtLWdpdCBhL3Rlc3RzL01ha2VmaWxlLmFtIGIvdGVzdHMvTWFrZWZpbGUuYW0KaW5kZXgg MzhiMGUzMi4uYjI5MzI4YiAxMDA2NDQKLS0tIGEvdGVzdHMvTWFrZWZpbGUuYW0KKysrIGIvdGVz dHMvTWFrZWZpbGUuYW0KQEAgLTEzNCw2ICsxMzQsNyBAQCBURVNUUyA9CQkJCQkJXAogICB0dXJr aXNoLUkJCQkJCVwKICAgdHVya2lzaC1JLXdpdGhvdXQtZG90CQkJCVwKICAgdHVya2lzaC1leWVz CQkJCQlcCisgIHR3by1jaGFycwkJCQkJXAogICB0d28tZmlsZXMJCQkJCVwKICAgdW5pYnl0ZS1i aW5hcnkJCQkJXAogICB1bmlieXRlLWJyYWNrZXQtZXhwcgkJCQlcCmRpZmYgLS1naXQgYS90ZXN0 cy90d28tY2hhcnMgYi90ZXN0cy90d28tY2hhcnMKbmV3IGZpbGUgbW9kZSAxMDA3NTUKaW5kZXgg MDAwMDAwMC4uNDNhMTQxOAotLS0gL2Rldi9udWxsCisrKyBiL3Rlc3RzL3R3by1jaGFycwpAQCAt MCwwICsxLDI1IEBACisjISAvYmluL3NoCisjIFJlYWQgdHdvIGZpbGVzLCBvZiBpbmNyZWFzaW5n IHNpemUuCisjIFdpdGggQVNBTiwgdGhpcyB3b3VsZCBoYXZlIHRyaWdnZXJlZCBhIGZhbHNlLXBv c2l0aXZlIHJlYWQgb2YgcG9pc29uZWQgbWVtb3J5LgorIworIyBDb3B5cmlnaHQgKEMpIDIwMTQt MjAxNiBGcmVlIFNvZnR3YXJlIEZvdW5kYXRpb24sIEluYy4KKyMKKyMgQ29weWluZyBhbmQgZGlz dHJpYnV0aW9uIG9mIHRoaXMgZmlsZSwgd2l0aCBvciB3aXRob3V0IG1vZGlmaWNhdGlvbiwKKyMg YXJlIHBlcm1pdHRlZCBpbiBhbnkgbWVkaXVtIHdpdGhvdXQgcm95YWx0eSBwcm92aWRlZCB0aGUg Y29weXJpZ2h0CisjIG5vdGljZSBhbmQgdGhpcyBub3RpY2UgYXJlIHByZXNlcnZlZC4KKworLiAi JHtzcmNkaXI9Ln0vaW5pdC5zaCI7IHBhdGhfcHJlcGVuZF8gLi4vc3JjCisKK3JlcXVpcmVfZW5f dXRmOF9sb2NhbGVfCisKK2ZhaWw9MAorCitmb3IgTE9DIGluIGVuX1VTLlVURi04ICR6aCAkTE9D QUxFX0ZSX1VURjg7IGRvCisgIHByaW50ZiAnMFxuMFxuJyA+cGF0CisgIHByaW50ZiAnMFxuJyA+ aW4KKyAgb3V0PW91dC0kTE9DCisgIExDX0FMTD0kTE9DIGdyZXAgLUZmIHBhdCBpbiA+JG91dCB8 fCBmYWlsPTEKKyAgY29tcGFyZSBpbiAkb3V0IHx8IGZhaWw9MQorZG9uZQorCitFeGl0ICRmYWls Ci0tIAoxLjcuMQoK --------_5787A8F300000000D844_MULTIPART_MIXED_-- From unknown Sat Aug 09 15:54:57 2025 X-Loop: help-debbugs@gnu.org Subject: bug#23983: [PATCH] grep: fix crash with a pattern of alternation of two same characters Resent-From: Eric Blake Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Thu, 14 Jul 2016 17:30:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 23983 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Norihiro Tanaka , 23983@debbugs.gnu.org Received: via spool by 23983-submit@debbugs.gnu.org id=B23983.146851734328314 (code B ref 23983); Thu, 14 Jul 2016 17:30:02 +0000 Received: (at 23983) by debbugs.gnu.org; 14 Jul 2016 17:29:03 +0000 Received: from localhost ([127.0.0.1]:51686 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bNkRb-0007Mb-JZ for submit@debbugs.gnu.org; Thu, 14 Jul 2016 13:29:03 -0400 Received: from mx1.redhat.com ([209.132.183.28]:52482) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bNkRZ-0007Lm-Rm for 23983@debbugs.gnu.org; Thu, 14 Jul 2016 13:29:02 -0400 Received: from int-mx14.intmail.prod.int.phx2.redhat.com (int-mx14.intmail.prod.int.phx2.redhat.com [10.5.11.27]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id BED6337E64; Thu, 14 Jul 2016 17:28:57 +0000 (UTC) Received: from [10.3.116.64] (ovpn-116-64.phx2.redhat.com [10.3.116.64]) by int-mx14.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u6EHSvap022677; Thu, 14 Jul 2016 13:28:57 -0400 References: <20160715000700.D850.27F6AC2D@kcn.ne.jp> From: Eric Blake Openpgp: url=http://people.redhat.com/eblake/eblake.gpg Organization: Red Hat, Inc. Message-ID: <5787CBD8.7080403@redhat.com> Date: Thu, 14 Jul 2016 11:28:56 -0600 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.3.0 MIME-Version: 1.0 In-Reply-To: <20160715000700.D850.27F6AC2D@kcn.ne.jp> Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="9w8gFUC8AXcRVNV68RcBEVD7kNXv3weda" X-Scanned-By: MIMEDefang 2.68 on 10.5.11.27 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.29]); Thu, 14 Jul 2016 17:28:58 +0000 (UTC) X-Spam-Score: -6.3 (------) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -6.3 (------) This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --9w8gFUC8AXcRVNV68RcBEVD7kNXv3weda Content-Type: multipart/mixed; boundary="hnkH1pkclBaOphLcH7GuvFQo7D6Q90BfL" From: Eric Blake To: Norihiro Tanaka , 23983@debbugs.gnu.org Message-ID: <5787CBD8.7080403@redhat.com> Subject: Re: bug#23983: [PATCH] grep: fix crash with a pattern of alternation of two same characters References: <20160715000700.D850.27F6AC2D@kcn.ne.jp> In-Reply-To: <20160715000700.D850.27F6AC2D@kcn.ne.jp> --hnkH1pkclBaOphLcH7GuvFQo7D6Q90BfL Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable On 07/14/2016 09:07 AM, Norihiro Tanaka wrote: > Current master crashes with below. >=20 > $ printf '0\n0' >pat > $ printf '0\n' >in > $ env LC_ALL=3DC grep -F pat in >=20 > grep -F uses memchr2() for each character in this pattern, but if two > characters is same, the trie has no child. memchr2() should already be handling the special case of the same character requested twice, without clients having to code around it. --=20 Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org --hnkH1pkclBaOphLcH7GuvFQo7D6Q90BfL-- --9w8gFUC8AXcRVNV68RcBEVD7kNXv3weda Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 Comment: Public key at http://people.redhat.com/eblake/eblake.gpg Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQEcBAEBCAAGBQJXh8vYAAoJEKeha0olJ0NqbjUH/0CGFbXpn23QrbE9Yw7DXDus uhk2aagkG3PGAriw05Jjqxiy/aaeldRzG/ypjdFaiT++sKfZ5FSP5xr8qmqR7bab km5H9ooIHWiZnQRYbQZb0LDgcpF+5DXctXa1uQ4YyR0lV6RRG4J1GxTcT7vgUH/m Y1StlHDbJqkFYgKsADQtlS25beHfNzvpULcyAaIdKAKC6/ez3dRwpodbqrJFnBed ZU8DKHRps2UD3Fs3g3v0kKArbihMo8GndOCRLIYAmRG1E8BOoCNviQL+rPeGMXiU UBXFOiU0ezu1rGeDdP2gooYre6zD6S3kj3td/YwqfsA2h7JGjR4dGzF/qCdl0JM= =/wCy -----END PGP SIGNATURE----- --9w8gFUC8AXcRVNV68RcBEVD7kNXv3weda-- From unknown Sat Aug 09 15:54:57 2025 X-Loop: help-debbugs@gnu.org Subject: bug#23983: [PATCH] grep: fix crash with a pattern of alternation of two same characters Resent-From: Eric Blake Original-Sender: "Debbugs-submit" Resent-CC: bug-grep@gnu.org Resent-Date: Thu, 14 Jul 2016 17:33:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 23983 X-GNU-PR-Package: grep X-GNU-PR-Keywords: patch To: Norihiro Tanaka , 23983@debbugs.gnu.org Received: via spool by 23983-submit@debbugs.gnu.org id=B23983.14685175545168 (code B ref 23983); Thu, 14 Jul 2016 17:33:01 +0000 Received: (at 23983) by debbugs.gnu.org; 14 Jul 2016 17:32:34 +0000 Received: from localhost ([127.0.0.1]:51697 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bNkV0-0001LE-1Q for submit@debbugs.gnu.org; Thu, 14 Jul 2016 13:32:34 -0400 Received: from mx1.redhat.com ([209.132.183.28]:52487) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bNkUy-0001KK-4B for 23983@debbugs.gnu.org; Thu, 14 Jul 2016 13:32:32 -0400 Received: from int-mx14.intmail.prod.int.phx2.redhat.com (int-mx14.intmail.prod.int.phx2.redhat.com [10.5.11.27]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 7D7ABC04D2A4; Thu, 14 Jul 2016 17:32:31 +0000 (UTC) Received: from [10.3.116.64] (ovpn-116-64.phx2.redhat.com [10.3.116.64]) by int-mx14.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u6EHWV2M025639; Thu, 14 Jul 2016 13:32:31 -0400 References: <20160715000700.D850.27F6AC2D@kcn.ne.jp> From: Eric Blake Openpgp: url=http://people.redhat.com/eblake/eblake.gpg Organization: Red Hat, Inc. Message-ID: <5787CCAE.7070602@redhat.com> Date: Thu, 14 Jul 2016 11:32:30 -0600 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.3.0 MIME-Version: 1.0 In-Reply-To: <20160715000700.D850.27F6AC2D@kcn.ne.jp> Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="rsmSusJ93vwpiFf9L5l4CEkfMmEIxelCM" X-Scanned-By: MIMEDefang 2.68 on 10.5.11.27 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.31]); Thu, 14 Jul 2016 17:32:31 +0000 (UTC) X-Spam-Score: -6.3 (------) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -6.3 (------) This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --rsmSusJ93vwpiFf9L5l4CEkfMmEIxelCM Content-Type: multipart/mixed; boundary="s0NvMLJ6cWn4VPhKpvUU9CVReDRGMuLr0" From: Eric Blake To: Norihiro Tanaka , 23983@debbugs.gnu.org Message-ID: <5787CCAE.7070602@redhat.com> Subject: Re: bug#23983: [PATCH] grep: fix crash with a pattern of alternation of two same characters References: <20160715000700.D850.27F6AC2D@kcn.ne.jp> In-Reply-To: <20160715000700.D850.27F6AC2D@kcn.ne.jp> --s0NvMLJ6cWn4VPhKpvUU9CVReDRGMuLr0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable On 07/14/2016 09:07 AM, Norihiro Tanaka wrote: > Current master crashes with below. >=20 > $ printf '0\n0' >pat > $ printf '0\n' >in > $ env LC_ALL=3DC grep -F pat in >=20 > grep -F uses memchr2() for each character in this pattern, but if two > characters is same, the trie has no child. >=20 > +++ b/src/kwset.c > @@ -643,8 +643,13 @@ memoff2_kwset (char const *s, size_t n, kwset_t kw= set, > { > struct tree const *link =3D kwset->trie->links; > struct tree const *clink =3D link->llink ? link->llink : link->rlink= ; > + char const *mch; > + > + if (clink) > + mch =3D memchr2 (s, link->label, clink->label, n); > + else > + mch =3D memchr (s, link->label, n); So the crash is because clink can be NULL, not because memchr2() is faulty. Could you instead do: struct tree const *clink =3D link->llink ? link->llink : link->rlink ? link->rlink : link; > =20 > - char const *mch =3D memchr2 (s, link->label, clink->label, n); so that you end up passing link->label to both parameters of memchr2() when there are no further children in the trie? --=20 Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org --s0NvMLJ6cWn4VPhKpvUU9CVReDRGMuLr0-- --rsmSusJ93vwpiFf9L5l4CEkfMmEIxelCM Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 Comment: Public key at http://people.redhat.com/eblake/eblake.gpg Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQEcBAEBCAAGBQJXh8yuAAoJEKeha0olJ0NqNmcH/1bRKxJ13xFLunH5wFldv4ll IDlr1xZqzF7T+cWzA2cRPSP5cIsclD1kvxeoMKX7OqHEIZSaI0KSGOqo8kyfqJ6E nptqBOt2GWvOkZgUJZ11452ONndR5k7qocBM/DHeCEjA8RQ+5I3y/nX4BVV59wIi ltDLdVzw5Njulyi2OUndfZVINc0j1c67Dtd7hktuYwA1pJtni2jPRf8L6mk/XGH2 l+A9CP00VEZgmsV7r6C/DFlY74TBzBgkJ0M26ZLVutsLyisnW8hPXJxWsMHugQNU gl2/LKEdWBjwuQXyXWLGmJp/jMWa1AyCF6Ue9UI6oGcqkolw8EJlNOT2uo3cF6Y= =Nh2T -----END PGP SIGNATURE----- --rsmSusJ93vwpiFf9L5l4CEkfMmEIxelCM-- From unknown Sat Aug 09 15:54:57 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.505 (Entity 5.505) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: Norihiro Tanaka Subject: bug#23983: closed (Re: bug#23983: [PATCH] grep: fix crash with a pattern of alternation of two same characters) Message-ID: References: <5787D343.4080208@cs.ucla.edu> <20160715000700.D850.27F6AC2D@kcn.ne.jp> X-Gnu-PR-Message: they-closed 23983 X-Gnu-PR-Package: grep X-Gnu-PR-Keywords: patch Reply-To: 23983@debbugs.gnu.org Date: Thu, 14 Jul 2016 18:01:02 +0000 Content-Type: multipart/mixed; boundary="----------=_1468519262-8202-1" This is a multi-part message in MIME format... ------------=_1468519262-8202-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #23983: [PATCH] grep: fix crash with a pattern of alternation of two same c= haracters which was filed against the grep package, has been closed. The explanation is attached below, along with your original report. If you require more details, please reply to 23983@debbugs.gnu.org. --=20 23983: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D23983 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1468519262-8202-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 23983-done) by debbugs.gnu.org; 14 Jul 2016 18:00:55 +0000 Received: from localhost ([127.0.0.1]:51713 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bNkwQ-00027r-Mt for submit@debbugs.gnu.org; Thu, 14 Jul 2016 14:00:54 -0400 Received: from zimbra.cs.ucla.edu ([131.179.128.68]:33603) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bNkwO-00027f-Tj for 23983-done@debbugs.gnu.org; Thu, 14 Jul 2016 14:00:53 -0400 Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 1691E161560; Thu, 14 Jul 2016 11:00:47 -0700 (PDT) Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id 0-l-B4qew_sC; Thu, 14 Jul 2016 11:00:46 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 0DD5116155D; Thu, 14 Jul 2016 11:00:46 -0700 (PDT) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id n35Zgmte3Q4N; Thu, 14 Jul 2016 11:00:45 -0700 (PDT) Received: from [192.168.1.64] (171.213.196.77.rev.sfr.net [77.196.213.171]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id 6D0A0161560; Thu, 14 Jul 2016 11:00:42 -0700 (PDT) Subject: Re: bug#23983: [PATCH] grep: fix crash with a pattern of alternation of two same characters To: Eric Blake , Norihiro Tanaka , 23983-done@debbugs.gnu.org References: <20160715000700.D850.27F6AC2D@kcn.ne.jp> <5787CCAE.7070602@redhat.com> From: Paul Eggert Message-ID: <5787D343.4080208@cs.ucla.edu> Date: Thu, 14 Jul 2016 20:00:35 +0200 User-Agent: Mozilla/5.0 (X11; Linux i686; rv:38.0) Gecko/20100101 Thunderbird/38.8.0 MIME-Version: 1.0 In-Reply-To: <5787CCAE.7070602@redhat.com> Content-Type: multipart/mixed; boundary="------------030100040900010408080500" X-Spam-Score: -1.3 (-) X-Debbugs-Envelope-To: 23983-done X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.3 (-) This is a multi-part message in MIME format. --------------030100040900010408080500 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit On 07/14/2016 07:32 PM, Eric Blake wrote: > Could you instead do: Something like that should work, but the original patch seems more straightforward. As it happens I installed the attached before seeing your email. The first is the original patch but with comments spruced up a bit, mostly for English. The second is a minor style change. --------------030100040900010408080500 Content-Type: text/x-patch; name="0001-grep-fix-F-crash-when-alternating-duplicates.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0001-grep-fix-F-crash-when-alternating-duplicates.patch" >From 96daaf5b8df02171f609b17edbf1ece17edc2736 Mon Sep 17 00:00:00 2001 From: Norihiro Tanaka Date: Thu, 14 Jul 2016 23:45:45 +0900 Subject: [PATCH 1/2] grep: fix -F crash when alternating duplicates grep -F crashes with a pattern like 0\n0. This bug was introduced in 966f6586fbce3081ce6e5e2f9b55301b0ec3d2b4. * src/kwset.c (memoff2_kwset): If two characters are the same, use memchr instead of memchr2. * tests/two-chars: New test. * tests/Makefile.am (TESTS): Add it. --- src/kwset.c | 7 ++++++- tests/Makefile.am | 1 + tests/two-chars | 24 ++++++++++++++++++++++++ 3 files changed, 31 insertions(+), 1 deletion(-) create mode 100755 tests/two-chars diff --git a/src/kwset.c b/src/kwset.c index 7391990..80df752 100644 --- a/src/kwset.c +++ b/src/kwset.c @@ -643,8 +643,13 @@ memoff2_kwset (char const *s, size_t n, kwset_t kwset, { struct tree const *link = kwset->trie->links; struct tree const *clink = link->llink ? link->llink : link->rlink; + char const *mch; + + if (clink) + mch = memchr2 (s, link->label, clink->label, n); + else + mch = memchr (s, link->label, n); - char const *mch = memchr2 (s, link->label, clink->label, n); if (! mch) return SIZE_MAX; else diff --git a/tests/Makefile.am b/tests/Makefile.am index 38b0e32..b29328b 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -134,6 +134,7 @@ TESTS = \ turkish-I \ turkish-I-without-dot \ turkish-eyes \ + two-chars \ two-files \ unibyte-binary \ unibyte-bracket-expr \ diff --git a/tests/two-chars b/tests/two-chars new file mode 100755 index 0000000..7ce7216 --- /dev/null +++ b/tests/two-chars @@ -0,0 +1,24 @@ +#! /bin/sh +# Check for grep -F with two patterns consisting of the same char. +# +# Copyright 2016 Free Software Foundation, Inc. +# +# Copying and distribution of this file, with or without modification, +# are permitted in any medium without royalty provided the copyright +# notice and this notice are preserved. + +. "${srcdir=.}/init.sh"; path_prepend_ ../src + +require_en_utf8_locale_ + +fail=0 + +for LOC in en_US.UTF-8 $zh $LOCALE_FR_UTF8; do + printf '0\n0\n' >pat + printf '0\n' >in + out=out-$LOC + LC_ALL=$LOC grep -Ff pat in >$out || fail=1 + compare in $out || fail=1 +done + +Exit $fail -- 2.5.5 --------------030100040900010408080500 Content-Type: text/x-patch; name="0002-grep-minor-style-changes-for-F-crash-fix.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0002-grep-minor-style-changes-for-F-crash-fix.patch" >From 01f728d0e10ad6483ac785d1963e46b544db5948 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Thu, 14 Jul 2016 19:38:01 +0200 Subject: [PATCH 2/2] grep: minor style changes for -F crash fix * src/kwset.c (memoff2_kwset): Use ?: instead of if-else. --- src/kwset.c | 10 +++------- 1 file changed, 3 insertions(+), 7 deletions(-) diff --git a/src/kwset.c b/src/kwset.c index 80df752..264ef22 100644 --- a/src/kwset.c +++ b/src/kwset.c @@ -643,13 +643,9 @@ memoff2_kwset (char const *s, size_t n, kwset_t kwset, { struct tree const *link = kwset->trie->links; struct tree const *clink = link->llink ? link->llink : link->rlink; - char const *mch; - - if (clink) - mch = memchr2 (s, link->label, clink->label, n); - else - mch = memchr (s, link->label, n); - + char const *mch = (clink + ? memchr2 (s, link->label, clink->label, n) + : memchr (s, link->label, n)); if (! mch) return SIZE_MAX; else -- 2.5.5 --------------030100040900010408080500-- ------------=_1468519262-8202-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by debbugs.gnu.org; 14 Jul 2016 15:07:46 +0000 Received: from localhost ([127.0.0.1]:51572 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bNiEr-0003MY-Km for submit@debbugs.gnu.org; Thu, 14 Jul 2016 11:07:45 -0400 Received: from eggs.gnu.org ([208.118.235.92]:59789) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bNiEq-0003ML-0R for submit@debbugs.gnu.org; Thu, 14 Jul 2016 11:07:44 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bNiEh-0005lP-NI for submit@debbugs.gnu.org; Thu, 14 Jul 2016 11:07:38 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:60123) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bNiEh-0005l3-KX for submit@debbugs.gnu.org; Thu, 14 Jul 2016 11:07:35 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:50715) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bNiEc-0003qu-Uq for bug-grep@gnu.org; Thu, 14 Jul 2016 11:07:33 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bNiEX-0005hX-OQ for bug-grep@gnu.org; Thu, 14 Jul 2016 11:07:29 -0400 Received: from mailgw01.kcn.ne.jp ([61.86.7.208]:35616) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bNiEX-0005fr-7n for bug-grep@gnu.org; Thu, 14 Jul 2016 11:07:25 -0400 Received: from mxs01-s (mailgw1.kcn.ne.jp [61.86.15.233]) by mailgw01.kcn.ne.jp (Postfix) with ESMTP id 11C6A4A0831 for ; Fri, 15 Jul 2016 00:07:14 +0900 (JST) X-matriXscan-loop-detect: 722934c84a705b8d72b04fef7c04bec65a8895b7 Received: from mail02.kcn.ne.jp ([61.86.6.181]) by mxs01-s with ESMTP; Fri, 15 Jul 2016 00:07:13 +0900 (JST) Received: from [10.120.1.7] (i118-21-128-66.s30.a048.ap.plala.or.jp [118.21.128.66]) by mail02.kcn.ne.jp (Postfix) with ESMTPA id B4BC2BE8001 for ; Fri, 15 Jul 2016 00:07:13 +0900 (JST) Date: Fri, 15 Jul 2016 00:07:13 +0900 From: Norihiro Tanaka To: Subject: [PATCH] grep: fix crash with a pattern of alternation of two same characters Message-Id: <20160715000700.D850.27F6AC2D@kcn.ne.jp> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------_5787A8F300000000D844_MULTIPART_MIXED_" Content-Transfer-Encoding: 7bit X-Mailer: Becky! ver. 2.65.07 [ja] X-matriXscan-Sophos-AV: Clean X-matriXscan-Action: Approve X-matriXscan: Uncategorized X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -4.0 (----) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -4.0 (----) --------_5787A8F300000000D844_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit Current master crashes with below. $ printf '0\n0' >pat $ printf '0\n' >in $ env LC_ALL=C grep -F pat in grep -F uses memchr2() for each character in this pattern, but if two characters is same, the trie has no child. --------_5787A8F300000000D844_MULTIPART_MIXED_ Content-Type: text/plain; charset="US-ASCII"; name="0001-grep-fix-crash-with-a-pattern-of-alternation-of-two-.patch" Content-Disposition: attachment; filename="0001-grep-fix-crash-with-a-pattern-of-alternation-of-two-.patch" Content-Transfer-Encoding: base64 RnJvbSAzYjAwNGE2NmNjOWRjNjZhZDYyMTExYmMzOGIyYzVhMmI4YmIwODJjIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBOb3JpaGlybyBUYW5ha2EgPG5vcml0bmtAa2NuLm5lLmpwPgpE YXRlOiBUaHUsIDE0IEp1bCAyMDE2IDIzOjQ1OjQ1ICswOTAwClN1YmplY3Q6IFtQQVRDSF0gZ3Jl cDogZml4IGNyYXNoIHdpdGggYSBwYXR0ZXJuIG9mIGFsdGVybmF0aW9uIG9mIHR3byBzYW1lIGNo YXJhY3RlcnMKCmdyZXAgLUYgY3Jhc2hlcyB3aXRoIHBhdHRlcm4gYXMgMFxuMC4gIFRoaXMgYnVn IGlzIGludHJvZHVjZWQgaW4KOTY2ZjY1ODZmYmNlMzA4MWNlNmU1ZTJmOWI1NTMwMWIwZWMzZDJi NC4KCiogc3JjL2t3c2V0LmMgKG1lbW9mZjJfa3dzZXQpOiBJZiB0d28gY2hhcmFjdGVycyBpcyBz YW1lLCBtZW1jaHIgaW5zdGVhZApvZiBtZW1jaHIyLgoqIHRlc3RzL3R3by1jaGFyczogTmV3IHRl c3QuCiogdGVzdHMvTWFrZWZpbGUuYW0gKFRFU1RTKTogQWRkIGl0LgotLS0KIHNyYy9rd3NldC5j ICAgICAgIHwgICAgNyArKysrKystCiB0ZXN0cy9NYWtlZmlsZS5hbSB8ICAgIDEgKwogdGVzdHMv dHdvLWNoYXJzICAgfCAgIDI1ICsrKysrKysrKysrKysrKysrKysrKysrKysKIDMgZmlsZXMgY2hh bmdlZCwgMzIgaW5zZXJ0aW9ucygrKSwgMSBkZWxldGlvbnMoLSkKIGNyZWF0ZSBtb2RlIDEwMDc1 NSB0ZXN0cy90d28tY2hhcnMKCmRpZmYgLS1naXQgYS9zcmMva3dzZXQuYyBiL3NyYy9rd3NldC5j CmluZGV4IDczOTE5OTAuLjgwZGY3NTIgMTAwNjQ0Ci0tLSBhL3NyYy9rd3NldC5jCisrKyBiL3Ny Yy9rd3NldC5jCkBAIC02NDMsOCArNjQzLDEzIEBAIG1lbW9mZjJfa3dzZXQgKGNoYXIgY29uc3Qg KnMsIHNpemVfdCBuLCBrd3NldF90IGt3c2V0LAogewogICBzdHJ1Y3QgdHJlZSBjb25zdCAqbGlu ayA9IGt3c2V0LT50cmllLT5saW5rczsKICAgc3RydWN0IHRyZWUgY29uc3QgKmNsaW5rID0gbGlu ay0+bGxpbmsgPyBsaW5rLT5sbGluayA6IGxpbmstPnJsaW5rOworICBjaGFyIGNvbnN0ICptY2g7 CisKKyAgaWYgKGNsaW5rKQorICAgIG1jaCA9IG1lbWNocjIgKHMsIGxpbmstPmxhYmVsLCBjbGlu ay0+bGFiZWwsIG4pOworICBlbHNlCisgICAgbWNoID0gbWVtY2hyIChzLCBsaW5rLT5sYWJlbCwg bik7CiAKLSAgY2hhciBjb25zdCAqbWNoID0gbWVtY2hyMiAocywgbGluay0+bGFiZWwsIGNsaW5r LT5sYWJlbCwgbik7CiAgIGlmICghIG1jaCkKICAgICByZXR1cm4gU0laRV9NQVg7CiAgIGVsc2UK ZGlmZiAtLWdpdCBhL3Rlc3RzL01ha2VmaWxlLmFtIGIvdGVzdHMvTWFrZWZpbGUuYW0KaW5kZXgg MzhiMGUzMi4uYjI5MzI4YiAxMDA2NDQKLS0tIGEvdGVzdHMvTWFrZWZpbGUuYW0KKysrIGIvdGVz dHMvTWFrZWZpbGUuYW0KQEAgLTEzNCw2ICsxMzQsNyBAQCBURVNUUyA9CQkJCQkJXAogICB0dXJr aXNoLUkJCQkJCVwKICAgdHVya2lzaC1JLXdpdGhvdXQtZG90CQkJCVwKICAgdHVya2lzaC1leWVz CQkJCQlcCisgIHR3by1jaGFycwkJCQkJXAogICB0d28tZmlsZXMJCQkJCVwKICAgdW5pYnl0ZS1i aW5hcnkJCQkJXAogICB1bmlieXRlLWJyYWNrZXQtZXhwcgkJCQlcCmRpZmYgLS1naXQgYS90ZXN0 cy90d28tY2hhcnMgYi90ZXN0cy90d28tY2hhcnMKbmV3IGZpbGUgbW9kZSAxMDA3NTUKaW5kZXgg MDAwMDAwMC4uNDNhMTQxOAotLS0gL2Rldi9udWxsCisrKyBiL3Rlc3RzL3R3by1jaGFycwpAQCAt MCwwICsxLDI1IEBACisjISAvYmluL3NoCisjIFJlYWQgdHdvIGZpbGVzLCBvZiBpbmNyZWFzaW5n IHNpemUuCisjIFdpdGggQVNBTiwgdGhpcyB3b3VsZCBoYXZlIHRyaWdnZXJlZCBhIGZhbHNlLXBv c2l0aXZlIHJlYWQgb2YgcG9pc29uZWQgbWVtb3J5LgorIworIyBDb3B5cmlnaHQgKEMpIDIwMTQt MjAxNiBGcmVlIFNvZnR3YXJlIEZvdW5kYXRpb24sIEluYy4KKyMKKyMgQ29weWluZyBhbmQgZGlz dHJpYnV0aW9uIG9mIHRoaXMgZmlsZSwgd2l0aCBvciB3aXRob3V0IG1vZGlmaWNhdGlvbiwKKyMg YXJlIHBlcm1pdHRlZCBpbiBhbnkgbWVkaXVtIHdpdGhvdXQgcm95YWx0eSBwcm92aWRlZCB0aGUg Y29weXJpZ2h0CisjIG5vdGljZSBhbmQgdGhpcyBub3RpY2UgYXJlIHByZXNlcnZlZC4KKworLiAi JHtzcmNkaXI9Ln0vaW5pdC5zaCI7IHBhdGhfcHJlcGVuZF8gLi4vc3JjCisKK3JlcXVpcmVfZW5f dXRmOF9sb2NhbGVfCisKK2ZhaWw9MAorCitmb3IgTE9DIGluIGVuX1VTLlVURi04ICR6aCAkTE9D QUxFX0ZSX1VURjg7IGRvCisgIHByaW50ZiAnMFxuMFxuJyA+cGF0CisgIHByaW50ZiAnMFxuJyA+ aW4KKyAgb3V0PW91dC0kTE9DCisgIExDX0FMTD0kTE9DIGdyZXAgLUZmIHBhdCBpbiA+JG91dCB8 fCBmYWlsPTEKKyAgY29tcGFyZSBpbiAkb3V0IHx8IGZhaWw9MQorZG9uZQorCitFeGl0ICRmYWls Ci0tIAoxLjcuMQoK --------_5787A8F300000000D844_MULTIPART_MIXED_-- ------------=_1468519262-8202-1--