Bug 175314 - [regression] bsdgrep(1) broken multidot escaping since r225435
Summary: [regression] bsdgrep(1) broken multidot escaping since r225435
Status: Closed FIXED
Alias: None
Product: Base System
Classification: Unclassified
Component: bin (show other bugs)
Version: 10.0-CURRENT
Hardware: Any Any
: Normal Affects Only Me
Assignee: Kyle Evans
URL:
Keywords: patch, regression
Depends on:
Blocks:
 
Reported: 2013-01-15 04:00 UTC by Jan Beich
Modified: 2017-08-24 14:18 UTC (History)
2 users (show)

See Also:


Attachments
Proposed patch to address bsdgrep abusing memory (2.72 KB, patch)
2017-01-21 00:09 UTC, Kyle Evans
no flags Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Jan Beich freebsd_committer freebsd_triage 2013-01-15 04:00:00 UTC
(originally reported to gabor@ on 04 Dec 2011)

After r225435 bsdgrep built WITHOUT_NLS became sensitive to whether
allocated memory but not initalized memory is set to NULL or junk. In
particular, this leads to false positives on MALLOC_PRODUCTION when
matching a pattern with multiple dots some of which may be escaped.

http://svnweb.freebsd.org/changeset/base/225435 (merged into /head)

How-To-Repeat: $ make all install WITHOUT_NLS= -C/usr/src/usr.bin/grep

$ echo 'f.oo' | env -i MALLOC_CONF=junk:true bsdgrep -o 'f.o\.'
Exit 1
$ echo 'f.oo' | env -i MALLOC_CONF=junk:false bsdgrep -o 'f.o\.'
f.oo

$ echo 'f.oo' | env -i MALLOC_CONF=junk:true gnugrep -o 'f.o\.'
Exit 1
$ echo 'f.oo' | env -i MALLOC_CONF=junk:false gnugrep -o 'f.o\.'
Exit 1
Comment 1 Kyle Evans freebsd_committer freebsd_triage 2017-01-21 00:09:38 UTC
Created attachment 179167 [details]
Proposed patch to address bsdgrep abusing memory

This was irritating to track down. There were two major problems here:

1.) wescmap was being built on top of uninitialized memory -- therefore, every dot was theoretically escaped with junk=true
2.) The pre-processed pattern never makes it to fg->pattern, so escmap (also uninitialized memory) was being built based on the processed pattern (without escapes)

This caused mass-hilarity and there's no way this could have worked since import. Attached patch addresses both issues by switching both xmalloc()'s to xcalloc and making a copy of the original pat (sans start marker at least) to examine for escapes.

I also touched formatting a bit in the area that I had to make more changes to, because it was difficult to parse through at first.
Comment 2 commit-hook freebsd_committer freebsd_triage 2017-04-05 18:42:02 UTC
A commit references this bug:

Author: emaste
Date: Wed Apr  5 18:41:46 UTC 2017
New revision: 316536
URL: https://svnweb.freebsd.org/changeset/base/316536

Log:
  bsdgrep: create additional tests for coverage on recent fixes

  Create additional tests to cover regressions that were discovered by
  PRs linked to reviews D10098, D10102, and D10104.

  It is worth noting that neither bsdgrep(1) nor gnugrep(1) in the base
  system currently pass all of these tests, and gnugrep(1) not quite being
  up to snuff was also noted in at least one of the PRs.

  PR:		175314 202022 195763 180990 197555 197531 181263 209116
  Submitted by:	Kyle Evans <kevans91@ksu.edu>
  Reviewed by:	cem, ngie, emaste
  MFC after:	1 month
  Differential Revision:	https://reviews.freebsd.org/D10112

Changes:
  head/contrib/netbsd-tests/usr.bin/grep/d_color_a.in
  head/contrib/netbsd-tests/usr.bin/grep/d_color_a.out
  head/contrib/netbsd-tests/usr.bin/grep/d_color_b.in
  head/contrib/netbsd-tests/usr.bin/grep/d_color_b.out
  head/contrib/netbsd-tests/usr.bin/grep/d_color_c.out
  head/contrib/netbsd-tests/usr.bin/grep/d_escmap.in
  head/contrib/netbsd-tests/usr.bin/grep/d_f_file_empty.in
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_a.in
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_a.out
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_b.in
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_b.out
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_c.in
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_c.out
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_d.in
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_e.in
  head/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_e.out
  head/contrib/netbsd-tests/usr.bin/grep/t_grep.sh
  head/usr.bin/grep/tests/Makefile
Comment 3 commit-hook freebsd_committer freebsd_triage 2017-04-21 14:36:22 UTC
A commit references this bug:

Author: emaste
Date: Fri Apr 21 14:36:10 UTC 2017
New revision: 317254
URL: https://svnweb.freebsd.org/changeset/base/317254

Log:
  bsdgrep: add BSD_GREP_FASTMATCH knob for built-in fastmatch

  Bugs have been found in the fastmatch implementation as used in bsdgrep.
  Some have been fixed (r316495) while fixes for others are in review
  (D10098).

  In comparison with the fastmatch implementation, Kyle Evans found that:

  - regex(3)'s performance with literal expressions offers a speed
    improvement over fastmatch

  - regex(3)'s performance, both with simple BREs and EREs, seems to be
    comparable

  The regex implementation was imported in r226035, and the commit message
  reports:

      This is a temporary solution until the whole regex library is
      not replaced so that BSD grep development can continue and the
      backported code gets some review and testing. This change only
      improves scalability slightly, there is no big performance boost
      yet but several minor bugs have been found and fixed.

  Introduce a WITH_/WITHOUT_BSD_GREP_FASTMATCH knob to support testing
  of both approaches.

  PR:		175314, 194823
  Submitted by:	Kyle Evans <kevans91 at ksu.edu>
  Reviewed by:	bdrewery (in part)
  Differential Revision:	https://reviews.freebsd.org/D10282

Changes:
  head/share/man/man5/src.conf.5
  head/share/mk/src.opts.mk
  head/tools/build/options/WITHOUT_BSD_GREP_FASTMATCH
  head/usr.bin/grep/Makefile
  head/usr.bin/grep/grep.c
  head/usr.bin/grep/grep.h
  head/usr.bin/grep/util.c
Comment 4 commit-hook freebsd_committer freebsd_triage 2017-08-16 00:12:34 UTC
A commit references this bug:

Author: kevans
Date: Wed Aug 16 00:12:24 UTC 2017
New revision: 322555
URL: https://svnweb.freebsd.org/changeset/base/322555

Log:
  bsdgrep: Fix matching behavior and add regression tests

  MFC r316477: bsdgrep: fix matching behaviour

  - Set REG_NOTBOL if we've already matched beginning of line and we're
    examining later parts

  - For each pattern we examine, apply it to the remaining bits of the
    line rather than (potentially) smaller subsets

  - Check for REG_NOSUB after we've looked at all patterns initially
    matching the line

  - Keep track of the last match we made to later determine if we're
    simply not matching any longer or if we need to proceed another byte
    because we hit a zero-length match

  - Match the earliest and longest bit of each line before moving the
    beginning of what we match to further in the line, past the end of the
    longest match; this generally matches how gnugrep(1) seems to behave,
    and seems like pretty good behavior to me

  - Finally, bail out of printing any matches if we were set to print all
    (empty pattern) but -o (output matches) was set

  MFC r316489: bsdgrep: Initialize vars to avoid a false positive GCC warning

  MFC r316491: bsdgrep: revert color changes from r316477

  r316477 changed the color output to match exactly the in-tree GNU grep,
  but introduces unnecessary escape sequences.

  MFC r316536: bsdgrep: create additional tests for coverage on recent fixes

  Create additional tests to cover regressions that were discovered by
  PRs linked to reviews D10098, D10102, and D10104.

  It is worth noting that neither bsdgrep(1) nor gnugrep(1) in the base
  system currently pass all of these tests, and gnugrep(1) not quite being
  up to snuff was also noted in at least one of the PRs.

  MFC r317052: bsdgrep: fix zero-length matches without the -o flag

  r316477 broke zero-length matches when not using the -o flag, by
  skipping over them entirely.

  Add a regression test so that it doesn't break again in the future.

  PR:		175314, 180990, 181263, 195763, 197531, 197555, 202022, 209116
  Approved by:	emaste (mentor, blanket MFC)
  Relnotes:	yes

Changes:
_U  stable/11/
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_color_a.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_color_a.out
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_color_b.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_color_b.out
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_color_c.out
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_escmap.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_f_file_empty.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_a.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_a.out
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_b.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_b.out
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_c.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_c.out
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_d.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_e.in
  stable/11/contrib/netbsd-tests/usr.bin/grep/d_oflag_zerolen_e.out
  stable/11/contrib/netbsd-tests/usr.bin/grep/t_grep.sh
  stable/11/usr.bin/grep/tests/Makefile
  stable/11/usr.bin/grep/util.c
Comment 5 commit-hook freebsd_committer freebsd_triage 2017-08-16 17:38:45 UTC
A commit references this bug:

Author: kevans
Date: Wed Aug 16 17:38:38 UTC 2017
New revision: 322582
URL: https://svnweb.freebsd.org/changeset/base/322582

Log:
  MFC r317254: bsdgrep: add BSD_GREP_FASTMATCH knob for built-in fastmatch

  Bugs have been found in the fastmatch implementation as used in bsdgrep.
  Some have been fixed (r316495) while fixes for others are in review
  (D10098).

  In comparison with the fastmatch implementation, Kyle Evans found that:

  - regex(3)'s performance with literal expressions offers a speed
    improvement over fastmatch

  - regex(3)'s performance, both with simple BREs and EREs, seems to be
    comparable

  The regex implementation was imported in r226035, and the commit message
  reports:

      This is a temporary solution until the whole regex library is
      not replaced so that BSD grep development can continue and the
      backported code gets some review and testing. This change only
      improves scalability slightly, there is no big performance boost
      yet but several minor bugs have been found and fixed.

  Introduce a WITH_/WITHOUT_BSD_GREP_FASTMATCH knob to support testing
  of both approaches.

  Regenerate src.conf(5) as per the original commit

  PR:		175314, 194823
  Approved by:	emaste (mentor, blanket MFC)

Changes:
_U  stable/11/
  stable/11/share/man/man5/src.conf.5
  stable/11/share/mk/src.opts.mk
  stable/11/tools/build/options/WITHOUT_BSD_GREP_FASTMATCH
  stable/11/usr.bin/grep/Makefile
  stable/11/usr.bin/grep/grep.c
  stable/11/usr.bin/grep/grep.h
  stable/11/usr.bin/grep/util.c
Comment 6 Mark Linimon freebsd_committer freebsd_triage 2017-08-24 14:18:36 UTC
MFCed Wed Aug 16 17:38:38 UTC 2017.