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 $? 1 $ grep -F $(awk '$2=="ssh-rsa"{print $3}' known_hosts) known_hosts; echo $? 1 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] 0 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] 0 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.
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 $? 1
Ran the testcase on FreeBSD 11, 10 7, 6 and all fail in the same way. Whatever this is, it's not new.
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.
(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+.
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.
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.
I cannot reproduce this error on bsdgrep or gnugrep grep) 3.11. Closing.