Bug 258616 - fgrep fails to find string that is present
Summary: fgrep fails to find string that is present
Status: New
Alias: None
Product: Base System
Classification: Unclassified
Component: bin (show other bugs)
Version: 12.2-STABLE
Hardware: amd64 Any
: --- Affects Some People
Assignee: freebsd-bugs (Nobody)
Depends on:
Reported: 2021-09-20 01:13 UTC by Darren Tucker
Modified: 2021-09-26 12:58 UTC (History)
2 users (show)

See Also:

known_hosts file demonstrating fgrep problem (2.29 KB, text/plain)
2021-09-20 01:13 UTC, Darren Tucker
no flags Details
reduced fgrep test case (808 bytes, text/plain)
2021-09-20 01:18 UTC, Darren Tucker
no flags Details

Note You need to log in before you can comment on or make changes to this bug.
Description Darren Tucker 2021-09-20 01:13:55 UTC
Created attachment 228028 [details]
known_hosts file demonstrating fgrep problem

I think I've discovered a case where fgrep fails to find a string that is in fact present in the input file.

I have been seeing intermittent test failures in OpenSSH's regress tests on at least FreeBSD 12.2 and NetBSD 9 (which seems to be based on FreeBSD's code).  The test fails maybe 1 in 100 times when fgrep fails to match a string (an SSH host key in this case) that is in the input file.

It seems to be (a) data-dependent and (b) consistent.  I captured one of the failure cases (attached), and if I select the key from the file with awk then fgrep for it, fgrep does not find it:

$ uname -a
FreeBSD fbsd12 12.2-RELEASE-p3 FreeBSD 12.2-RELEASE-p3 GENERIC  amd64
$ fgrep $(awk '$2=="ssh-rsa"{print $3}' known_hosts) known_hosts; echo $?
$ grep -F $(awk '$2=="ssh-rsa"{print $3}' known_hosts) known_hosts; echo $?

but the equivalent awk will find it:

$ a=$(awk '$2=="ssh-rsa"{print $3}' known_hosts)           
$ awk '$3=="'$a'"' known_hosts
localhost-with-alias ssh-rsa [key elided]

and if I reduce the size of the file fgrep then also works:

$ grep ssh-rsa known_hosts >known_hosts2
$ fgrep $(awk '$2=="ssh-rsa"{print $3}' known_hosts2) known_hosts2; echo $?
localhost-with-alias ssh-rsa [key elided]

Deleting the first few lines from the file will also make it work.  Further weirdness: I built grep from the 12.2 branch it worked as expected:

$ ./grep -F $(awk '$2=="ssh-rsa"{print $3}' known_hosts) known_hosts; echo $?
localhost-with-alias ssh-rsa [key elided]

Same file works as expected on at least Linux and OpenBSD.  One of the other developers reproduced this and reduced the size of the test case which I will also attach.
Comment 1 Darren Tucker 2021-09-20 01:18:13 UTC
Created attachment 228029 [details]
reduced fgrep test case

Reduced fgrep testcase from Damien Miller.

$ uname -a
FreeBSD freebsd121-amd64 12.1-RELEASE FreeBSD 12.1-RELEASE r354233 GENERIC  amd64
$ fgrep "$(awk '$2=="YYYYYYY"{print $3}' fgrep_testcase)" fgrep_tescase; echo $?
Comment 2 Darren Tucker 2021-09-20 03:19:29 UTC
Ran the testcase on FreeBSD 11, 10 7, 6 and all fail in the same way.  Whatever this is, it's not new.
Comment 3 Darren Tucker 2021-09-20 08:27:21 UTC
oh, it looks like /usr/bin/grep is gnu/usr.bin/grep and not usr.bin/grep:

$ grep --version
grep (GNU grep) 2.5.1-FreeBSD [...]

building gnu/usr.bin/grep does indeed reproduce the problem.

I reproduced the problem with stock GNU grep v2.5.1 and found that it was fixed between 2.18 and 2.19 in this upstream commit:

commit 757381e58d669729510a89c323d4698f9a81f6c0
Author: Norihiro Tanaka <noritnk@kcn.ne.jp>
Date:   Sat Mar 15 14:41:52 2014 +0900

    grep: use the Galil rule for Boyer-Moore algorithm in KWSet
    The Boyer-Moore algorithm is O(m*n), which means it may be much
    slower than the DFA.  Its Galil rule variant is O(n) and increases
    efficiency in the typical case; it skips sections that are known
    to match and does not compare more than once for a position in the text.
    To use the Galil rule, look for the delta2 shift at each position
    from the trie instead of the 'mind2' value.
    * src/kwset.c (struct kwset): Replace member 'mind2' with 'shift'.
    (kwsprep): Look for the delta2 shift.
    (bmexec): Use it.
Comment 4 Ed Maste freebsd_committer 2021-09-22 14:19:07 UTC
(As expected) testcase works correctly on FreeBSD 13+ with BSD grep. It should be available on FreeBSD 12 as /usr/bin/bsdgrep and you could use that in a script, or install it as /usr/bin/grep if that's feasible for you. I will see about making sure all of the build infrastructure to support WITH_BSD_GREP is available in 12.x.

It's a bit of an unfortunate situation to fix GNU grep in the tree for 12.x though; GNU grep in the base system is not expected to receive an update, and GNU grep is GPLv3+. Assuming the change you identified would apply to the older grep version we have (without needing significant extra work) we could see if it is possible to obtain that change licensed as GPLv2+.
Comment 5 Darren Tucker 2021-09-23 22:04:09 UTC
Replacing the binary would help my system, but we want anyone to be able to run the test suite on their system.

Given how widespread this is I think we'll have to work around it in the scripts.
Comment 6 Darren Tucker 2021-09-24 01:31:16 UTC
I've put a workaround in our regress tests to fall back to awk any time one of these potentially buggy greps is detected.  From my perspective the matter is mitigated so please feel free to do with this bug report whatever you see fit.