Re: [PATCH] regexec: work around macOS TRE memory leak on invalid UTF-8

[Junio C Hamano <gitster@pobox.com>]

Chungmin Lee <chungmin@chungminlee.com> writes:

> This came out of a real incident: "git grep -i" over a repository that
> contains PDFs exhausted memory on an otherwise idle Mac mini and took the
> machine down with a kernel watchdog panic ("no checkins from watchdogd").
> The leak is in the system regex engine, not in git, but git is what
> drives it into the leaking path, once per line.
>
> Why this belongs in regexec_buf():

Why does this belong to Git, not macOS, in the first place?

> diff --git a/compat/regexec.c b/compat/regexec.c
> new file mode 100644
> index 000000000..0677162a8
> --- /dev/null
> +++ b/compat/regexec.c
> @@ -0,0 +1,108 @@
> +#include "git-compat-util.h"
> +
> +#ifdef REGEXEC_MAY_LEAK_ON_ILLSEQ
> +
> +#include <wchar.h>
> +
> +/*
> + * macOS's libc regex engine (TRE) leaks the buffer it allocates for a
> + * match whenever regexec() encounters an invalid multibyte sequence in
> + * a multibyte locale: it returns REG_ILLSEQ without freeing that buffer.
> + * A single "git grep" over a file with binary data can call regexec()
> + * once per line and leak gigabytes, which has been observed to exhaust
> + * memory and trigger a kernel watchdog panic.
> + *
> + * The leak happens inside regexec() before it returns, so reacting to
> + * REG_ILLSEQ cannot avoid it: the invalid bytes must never reach the
> + * matcher.  Split the buffer at each invalid sequence and search the
> + * surrounding runs of valid text separately.  A match on either side of
> + * the invalid bytes is still found (the same result the matcher gives on
> + * valid input), but the leaking REG_ILLSEQ path is never reached.
> + *
> + * Use mbrtowc() to decide where to split, so that we split at exactly the
> + * bytes the platform's own decoder -- and thus the regex engine, which
> + * decodes the same way -- rejects.  A hand-rolled validator would
> + * have to guess that boundary; being too lenient reintroduces the leak.
> + */

This clearly seems to be a workaround for a platform bug.  Do we
know how long we will need to keep it?

> +/*
> + * Search buf[start, end) for a match.  REG_STARTEND reports offsets
> + * relative to buf, so a hit needs no translation.  ^ may only match at
> + * the real start of the buffer and $ only at its real end, so suppress
> + * them when this segment does not reach those boundaries.
> + */
> +static int regexec_segment(const regex_t *preg, const char *buf,
> +			   size_t start, size_t end, size_t size,
> +			   size_t nmatch, regmatch_t pmatch[], int eflags)
> +{
> +	eflags |= REG_STARTEND;
> +	if (start > 0)
> +		eflags |= REG_NOTBOL;
> +	if (end < size)
> +		eflags |= REG_NOTEOL;
> +	pmatch[0].rm_so = start;
> +	pmatch[0].rm_eo = end;
> +	return regexec(preg, buf, nmatch, pmatch, eflags);
> +}
> +
> +int regexec_buf(const regex_t *preg, const char *buf, size_t size,
> +		size_t nmatch, regmatch_t pmatch[], int eflags)
> +{
> +	size_t seg_start = 0, i = 0;
> +	mbstate_t mbs;
> +
> +	assert(nmatch > 0 && pmatch);
> +
> +	/*
> +	 * Only a multibyte locale drives TRE through the leaking multibyte
> +	 * path.  In a single-byte locale (MB_CUR_MAX == 1) no byte is
> +	 * invalid, so search the whole buffer as before.  MB_CUR_MAX
> +	 * reflects the current LC_CTYPE, the same locale mbrtowc() below
> +	 * decodes against.
> +	 */
> +	if (MB_CUR_MAX == 1) {
> +		pmatch[0].rm_so = 0;
> +		pmatch[0].rm_eo = size;
> +		return regexec(preg, buf, nmatch, pmatch, eflags | REG_STARTEND);
> +	}
> +
> +	memset(&mbs, 0, sizeof(mbs));
> +	while (i < size) {
> +		unsigned char c = (unsigned char)buf[i];
> +		size_t n;
> +
> +		if (c < 0x80) {		/* ASCII fast path */
> +			i++;
> +			continue;
> +		}
> +
> +		n = mbrtowc(NULL, buf + i, size - i, &mbs);
> +		if (!n)			/* embedded NUL decodes to one byte */
> +			n = 1;
> +		if (n != (size_t)-1 && n != (size_t)-2) {
> +			i += n;
> +			continue;
> +		}

OK.  I wonder if we want to document what -1 and -2 signify (in
other words, why we stop only when the call returns one of these
two values), or is it too obvious for users of mbrtowc()?

In any case, if control reaches here, we saw either an invalid
sequence (-1) or not enough bytes to complete a whole multi-byte
character (-2), i.e., the case where regexec() would have trouble
matching starting at offset 'i'.  The bytes before that position
make an OK substring.

> +		/* buf[i] begins an invalid sequence; search the run before it */
> +		if (i > seg_start) {
> +			int ret = regexec_segment(preg, buf, seg_start, i, size,
> +						  nmatch, pmatch, eflags);
> +			if (ret != REG_NOMATCH)
> +				return ret;
> +		}

Naturally, this "check the OK prefix string" approach makes readers
wonder what happens when the pattern is "right anchored$" and the OK
prefix would match if the string truly ended at 'i' (or, if this is a
second or subsequent segment, the pattern is "^left anchored", and
the segment would match if the string started at 'seg_start').  The
use of 'REG_STARTEND' in regexec_segment() above, combined with
'REG_NOTBOL'/'REG_NOTEOL', is a clever way to work around it cleanly.

> diff --git a/git-compat-util.h b/git-compat-util.h
> index 880977640..3861c9353 100644
> --- a/git-compat-util.h
> +++ b/git-compat-util.h
> @@ -992,6 +992,10 @@ static inline int strtol_i(char const *s, int base, int *result)
>  #error "Git requires REG_STARTEND support. Compile with NO_REGEX=NeedsStartEnd"
>  #endif
>  
> +#ifdef REGEXEC_MAY_LEAK_ON_ILLSEQ

Hmph, how many different symbols do we need to deal with this?  The
Makefile has DARWIN_TRE_REGEXEC_LEAK_WORKAROUND and CPP macro is
REGEXEC_MAY_LEAK_ON_ILLSEQ?

> +int regexec_buf(const regex_t *preg, const char *buf, size_t size,
> +		size_t nmatch, regmatch_t pmatch[], int eflags);
> +#else
>  static inline int regexec_buf(const regex_t *preg, const char *buf, size_t size,
>  			      size_t nmatch, regmatch_t pmatch[], int eflags)
>  {
> @@ -1000,6 +1004,7 @@ static inline int regexec_buf(const regex_t *preg, const char *buf, size_t size,
>  	pmatch[0].rm_eo = size;
>  	return regexec(preg, buf, nmatch, pmatch, eflags | REG_STARTEND);
>  }
> +#endif

It is a bit awkward that the next platform needing its own
implementation of regexec_buf() to work around a different platform
bug would have to do:

	#if defined(REGEXEC_MAY_LEAK_ON_ILLSEQ) || defined(SOME_OTHER_PLATFORM_BUG)
	int regexec_buf(.....);
	#else
	static inline int regexec_buf(.....)
	... the current definition comes here ...
	#endif

I thought it was more common to:

 * Have each platform with such a need define an override in its own
   platform header file:

    int darwin_regexec_buf(.....);
    #define regexec_buf darwin_regexec_buf

 * Have a header file like 'git-compat-util.h' include such a header
   file (conditionally on relevant platforms, of course); and

 * Have the common header file do this:

        #ifndef regexec_buf
        static inline int regexec_buf(.....)
        ... the current definition comes here ...
        #endif

Right now, macOS is the only platform that needs an override, so the
result would be about the same amount of code.  However, in the long
run, this structure may give us a better organization, no?

> diff --git a/t/t7810-grep.sh b/t/t7810-grep.sh
> ...
> +test_expect_success MACOS,MB_REGEX 'grep anchors ^ and $ at true line ends past invalid UTF-8' '

Do we need to allow this test to fail on non macOS hosts?  Why?

> +	LC_ALL=en_US.UTF-8 git grep -h "^before" invalid-utf8-embedded >actual &&
> +	test_cmp invalid-utf8-embedded actual &&
> +	LC_ALL=en_US.UTF-8 git grep -h "world\$" invalid-utf8-embedded >actual &&
> +	test_cmp invalid-utf8-embedded actual
> +'
> +

Thanks.