[v2] grep: fall back to interpreter if JIT memory allocation fails

Commit Message

Mathias Krause Jan. 27, 2023, 3:49 p.m. UTC

Under Linux systems with SELinux's 'deny_execmem' or PaX's MPROTECT
enabled, the allocation of PCRE2's JIT rwx memory may be prohibited,
making pcre2_jit_compile() fail with PCRE2_ERROR_NOMEMORY (-48):

  [user@fedora git]$ git grep -c PCRE2_JIT
  grep.c:1

  [user@fedora git]$ # Enable SELinux's W^X policy
  [user@fedora git]$ sudo semanage boolean -m -1 deny_execmem

  [user@fedora git]$ # JIT memory allocation fails, breaking 'git grep'
  [user@fedora git]$ git grep -c PCRE2_JIT
  fatal: Couldn't JIT the PCRE2 pattern 'PCRE2_JIT', got '-48'

Instead of failing hard in this case and making 'git grep' unusable on
such systems, simply fall back to interpreter mode, leading to a much
better user experience.

As having a functional PCRE2 JIT compiler is a legitimate use case for
performance reasons, we'll only do the fallback if the supposedly
available JIT is found to be non-functional by attempting to JIT compile
a very simple pattern. If this fails, JIT is deemed to be non-functional
and we do the interpreter fallback. For all other cases, i.e. the simple
pattern can be compiled but the user provided cannot, we fail hard as we
do now as the reason for the failure must be the pattern itself.

Cc: Carlo Marcelo Arenas Belón <[e-mail]>
Signed-off-by: Mathias Krause <[e-mail]>
---

This patch is based on a previous attempt proposed by Carlo already 4
years ago[1]. However, it wasn't applied as there were still ongoing
discussions about how to handle and possibly avoid the automatic
fallback.

A follow-up RFC had been posted half a year later[2], adding a config
option and, after some more discussion, even command line switches[3].
But, after all, it was agreed on that this is far too much and Junio
suggested to simply revert back to the initial RFC and implement the
automatic fallback[4], basically merging it with a proper changelog[5].
As that never happened, I took up the work and tried to do just that.

This, again, lead to some discussion but, fortunately, less about the
config knobs, but more about the implications of such a change. I tried
to address Ævar's concerns about always falling back to the interpreter
and limited it to the problematic case I want to get solved.

1. https://lore.kernel.org/r/[e-mail]
2. https://lore.kernel.org/git/[e-mail]/
3. https://lore.kernel.org/git/[e-mail]/
4. https://lore.kernel.org/git/[e-mail]/
5. https://lore.kernel.org/git/[e-mail]/

Changes in v2:

The current version takes a conservative approach by only implementing
the fallback to interpreter mode when the runtime test for basic JIT
support fails as well, indicating the inability of PCRE2's memory
allocator to acquire a W|X mappings for runtime code generation.

pcre2_jit_functional() very much intentional calls pcre2_compile()
without making use of the context set up in compile_pcre2_pattern() to
exclude any errors related to that -- a wrong combination of options
making pcre2_jit_compile() fail for these reasons instead of the memory
mapping error we try to detect. This ensures we're doing a dumb simple
JIT compile test to probe its general runtime availability and not
wrongly fall back to interpreter mode because the option combination
we're trying to make use of isn't supported by the JIT.

I also changed the author to myself as the current state has little in
common with what Carlo once proposed.
---
 grep.c | 42 +++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 41 insertions(+), 1 deletion(-)

Comments

Junio C Hamano Jan. 27, 2023, 4:34 p.m. UTC | #1

Mathias Krause <[e-mail]> writes:

> As having a functional PCRE2 JIT compiler is a legitimate use case for
> performance reasons, we'll only do the fallback if the supposedly
> available JIT is found to be non-functional by attempting to JIT compile
> a very simple pattern. If this fails, JIT is deemed to be non-functional
> and we do the interpreter fallback. For all other cases, i.e. the simple
> pattern can be compiled but the user provided cannot, we fail hard as we
> do now as the reason for the failure must be the pattern itself.

I do not know if it is a good idea to rely on the "very simple
pattern".  The implementation of JIT could devise various ways to
succeed for such simple patterns without having writable-executable
piece of memory.  What happened to the earlier idea of falling back
to the interpreted codepath, which will catch any bad pattern that
has "the reason for the failure" by failing anyway?

> +static int pcre2_jit_functional(void)
> +{
> +	static int jit_working = -1;
> +	pcre2_code *code;
> +	size_t off;
> +	int err;
> +
> +	if (jit_working != -1)
> +		return jit_working;
> +
> +	/*
> +	 * Try to JIT compile a simple pattern to probe if the JIT is
> +	 * working in general. It might fail for systems where creating
> +	 * memory mappings for runtime code generation is restricted.
> +	 */
> +	code = pcre2_compile((PCRE2_SPTR)".", 1, 0, &err, &off, NULL);
> +	if (!code)
> +		return 0;
> +
> +	jit_working = pcre2_jit_compile(code, PCRE2_JIT_COMPLETE) == 0;
> +	pcre2_code_free(code);

I'd prefer not having to worry about: Or it might not fail for such
systems, as the pattern is too simple and future versions of
pcre2_compile() could have special case code.

> @@ -317,8 +342,23 @@ static void compile_pcre2_pattern(struct grep_pat *p, const struct grep_opt *opt
>  	pcre2_config(PCRE2_CONFIG_JIT, &p->pcre2_jit_on);
>  	if (p->pcre2_jit_on) {
>  		jitret = pcre2_jit_compile(p->pcre2_pattern, PCRE2_JIT_COMPLETE);
> -		if (jitret)
> +		if (jitret == PCRE2_ERROR_NOMEMORY && !pcre2_jit_functional()) {
> +			/*
> +			 * Even though pcre2_config(PCRE2_CONFIG_JIT, ...)
> +			 * indicated JIT support, the library might still
> +			 * fail to generate JIT code for various reasons,
> +			 * e.g. when SELinux's 'deny_execmem' or PaX's
> +			 * MPROTECT prevent creating W|X memory mappings.
> +			 *
> +			 * Instead of faling hard, fall back to interpreter
> +			 * mode, just as if the pattern was prefixed with
> +			 * '(*NO_JIT)'.
> +			 */
> +			p->pcre2_jit_on = 0;
> +			return;

Yes, the "instead of failing hard, fall back" makes sense.  Just
that I do not see why the runtime test is a good thing to have.  In
short, we are not in the business of catching bugs in pcre2_jit
implementations, so if they say they cannot compile the pattern (I
would even say I doubt the point of checking the return code to
ensure it is NOMEMORY), it would be fine to let the interpreter
codepath to inspect the pattern and diagnose problems with it, or
take the slow match without JIT.

What am I missing?

Junio C Hamano Jan. 27, 2023, 5:39 p.m. UTC | #2

Junio C Hamano <[e-mail]> writes:

> Yes, the "instead of failing hard, fall back" makes sense.  Just
> that I do not see why the runtime test is a good thing to have.  In
> short, we are not in the business of catching bugs in pcre2_jit
> implementations, so if they say they cannot compile the pattern (I
> would even say I doubt the point of checking the return code to
> ensure it is NOMEMORY), it would be fine to let the interpreter
> codepath to inspect the pattern and diagnose problems with it, or
> take the slow match without JIT.
>
> What am I missing?

Note that I've seen and recently re-read the discussion that leads to
https://lore.kernel.org/git/[e-mail]/

I suspect that this auto-probe is related to solving "the user
thinks JIT is in use but because of failing JIT the user's pattern
is getting horrible performance" somehow.  But I do not think a hard
failure is a good approach to help users in such a situation.

After such a failure, the user can prefix "(*NO_JIT)" to the pattern
and retry, or give up the operation altogether and not get a useful
result, but wouldn't it be far more helpful to just fallback as if
(*NO_JIT) was on from the beginning?

Also I notice that p->pcre2_jit_on is per "struct grep_pat", so it
is not like "once we see a pathological pattern, we turn off JIT
completely for other patterns", right?  That is, if you have

    git grep -P -e "$A" -e "$B"

and we fail to compile "$A" (for whatever reason), we could still
(attempt to) compile "$B".  Perhaps $A was too complex or was
incompatible with JIT combined with other options, but $B may be
easy enough to still be JITtable, in which case we would match with
the JITted version of $B with interpreted version of $A, instead of
failing, right?

THanks.

Junio C Hamano Jan. 27, 2023, 6:46 p.m. UTC | #3

Junio C Hamano <[e-mail]> writes:

>> What am I missing?
>
> Note that I've seen and recently re-read the discussion that leads to
> https://lore.kernel.org/git/[e-mail]/
>
> I suspect that this auto-probe is related to solving "the user
> thinks JIT is in use but because of failing JIT the user's pattern
> is getting horrible performance" somehow.  But I do not think a hard
> failure is a good approach to help users in such a situation.

I guess what I am saying is that the previous one that has been
queued on 'seen' may be better.  It should cover your original
"SELinux and other mechanisms can render JIT unusable because they
do not allow dynamic generation of code" use case.

Thanks.

Mathias Krause Jan. 29, 2023, 12:28 p.m. UTC | #4

On 27.01.23 17:34, Junio C Hamano wrote:
> Mathias Krause <[e-mail]> writes:
> 
>> As having a functional PCRE2 JIT compiler is a legitimate use case for
>> performance reasons, we'll only do the fallback if the supposedly
>> available JIT is found to be non-functional by attempting to JIT compile
>> a very simple pattern. If this fails, JIT is deemed to be non-functional
>> and we do the interpreter fallback. For all other cases, i.e. the simple
>> pattern can be compiled but the user provided cannot, we fail hard as we
>> do now as the reason for the failure must be the pattern itself.
> 
> I do not know if it is a good idea to rely on the "very simple
> pattern".  The implementation of JIT could devise various ways to
> succeed for such simple patterns without having writable-executable
> piece of memory.

Well, if PCRE2 JIT ever changes to optimize this case, we would be back
to the error I'm seeing right now. But I doubt that PCRE2 will be doing
optimizations like that. The current implementation does the JIT memory
allocation test very early, even before looking at the pattern:

https://github.com/PCRE2Project/pcre2/blob/pcre2-10.42/src/pcre2_jit_compile.c#L14450-L14465

But I can add a call to pcre2_pattern_info(PCRE2_INFO_JITSIZE) if you
really like me to, but IMHO it's not needed.

>                   What happened to the earlier idea of falling back
> to the interpreted codepath, which will catch any bad pattern that
> has "the reason for the failure" by failing anyway?

Ævar's concerns about always falling back to the interpreter mode made
me change the patch like this. Basically what he's concerned about are
two things:
1/ "Crazy patterns" that fail the JIT but will work for the interpreter
can be a serve performance regression.
2/ Always falling back to interpreter mode might mask JIT API usage
errors, we'd like to see.

While 1/ could also be seen as a limitation of current 'git grep', I
share Ævar's extended runtime regression concerns. If, for example, some
web interface offers users to supply arbitrary grep patterns, abusing
the interpreter mode fallback will consume significant more CPU
resources than it does right now (which simply fails with an error).

> 
>> +static int pcre2_jit_functional(void)
>> +{
>> +	static int jit_working = -1;
>> +	pcre2_code *code;
>> +	size_t off;
>> +	int err;
>> +
>> +	if (jit_working != -1)
>> +		return jit_working;
>> +
>> +	/*
>> +	 * Try to JIT compile a simple pattern to probe if the JIT is
>> +	 * working in general. It might fail for systems where creating
>> +	 * memory mappings for runtime code generation is restricted.
>> +	 */
>> +	code = pcre2_compile((PCRE2_SPTR)".", 1, 0, &err, &off, NULL);
>> +	if (!code)
>> +		return 0;
>> +
>> +	jit_working = pcre2_jit_compile(code, PCRE2_JIT_COMPLETE) == 0;
>> +	pcre2_code_free(code);
> 
> I'd prefer not having to worry about: Or it might not fail for such
> systems, as the pattern is too simple and future versions of
> pcre2_compile() could have special case code.

See above, it's unlikely to happen.

> 
>> @@ -317,8 +342,23 @@ static void compile_pcre2_pattern(struct grep_pat *p, const struct grep_opt *opt
>>  	pcre2_config(PCRE2_CONFIG_JIT, &p->pcre2_jit_on);
>>  	if (p->pcre2_jit_on) {
>>  		jitret = pcre2_jit_compile(p->pcre2_pattern, PCRE2_JIT_COMPLETE);
>> -		if (jitret)
>> +		if (jitret == PCRE2_ERROR_NOMEMORY && !pcre2_jit_functional()) {
>> +			/*
>> +			 * Even though pcre2_config(PCRE2_CONFIG_JIT, ...)
>> +			 * indicated JIT support, the library might still
>> +			 * fail to generate JIT code for various reasons,
>> +			 * e.g. when SELinux's 'deny_execmem' or PaX's
>> +			 * MPROTECT prevent creating W|X memory mappings.
>> +			 *
>> +			 * Instead of faling hard, fall back to interpreter
>> +			 * mode, just as if the pattern was prefixed with
>> +			 * '(*NO_JIT)'.
>> +			 */
>> +			p->pcre2_jit_on = 0;
>> +			return;
> 
> Yes, the "instead of failing hard, fall back" makes sense.  Just
> that I do not see why the runtime test is a good thing to have.

It prevents the fallback from being abused and introducing new
regressions. So it's good to have.

>                                                                  In
> short, we are not in the business of catching bugs in pcre2_jit
> implementations, so if they say they cannot compile the pattern (I
> would even say I doubt the point of checking the return code to
> ensure it is NOMEMORY), it would be fine to let the interpreter
> codepath to inspect the pattern and diagnose problems with it, or
> take the slow match without JIT.

Yeah, unfortunately they're not gonna fix what's a bug, IMHO. They think
it's a feature: https://github.com/PCRE2Project/pcre2/pull/157

Anyhow, the error code is very well documented, see pcre2_jit_compile(3)
"""
          [...]  The  function can also return PCRE2_ERROR_NOMEMORY if
       JIT is unable to allocate executable memory for  the  compiler,
       even if it was because of a system security restriction.
"""

And that's very much in line with what the test in pcre2_jit_compile()'s
current implementation does.

> What am I missing?

Please have a look at Ævar's reasoning here:
https://lore.kernel.org/git/[e-mail]/

Thanks,
Mathias

Mathias Krause Jan. 29, 2023, 1:36 p.m. UTC | #5

On 27.01.23 18:39, Junio C Hamano wrote:
> Junio C Hamano <[e-mail]> writes:
> 
>> Yes, the "instead of failing hard, fall back" makes sense.  Just
>> that I do not see why the runtime test is a good thing to have.  In
>> short, we are not in the business of catching bugs in pcre2_jit
>> implementations, so if they say they cannot compile the pattern (I
>> would even say I doubt the point of checking the return code to
>> ensure it is NOMEMORY), it would be fine to let the interpreter
>> codepath to inspect the pattern and diagnose problems with it, or
>> take the slow match without JIT.
>>
>> What am I missing?
> 
> Note that I've seen and recently re-read the discussion that leads to
> https://lore.kernel.org/git/[e-mail]/

Ahh, so ignore my last advise in the previous Email. You already read it.

> I suspect that this auto-probe is related to solving "the user
> thinks JIT is in use but because of failing JIT the user's pattern
> is getting horrible performance" somehow.  But I do not think a hard
> failure is a good approach to help users in such a situation.

Yes, it's exactly trying to detect this case and not cause a regression
for users expecting 'git grep' to make use of the JIT.

So, beside the W|X memory allocation error, other errors are likely only
to point out limitations of the JIT compiler, e.g. the example I gave in
https://lore.kernel.org/all/[e-mail]/,
which is, admitted, a made up example that can easily be worked around
by manually prefixing it with '(*NO_JIT)'. It would be a pain having to
do that for *every* pattern, but only doing it for the pathological
cases should be fine. Otherwise more users would have run into it
already and complained about it, no?

> After such a failure, the user can prefix "(*NO_JIT)" to the pattern
> and retry, or give up the operation altogether and not get a useful
> result, but wouldn't it be far more helpful to just fallback as if
> (*NO_JIT) was on from the beginning?

Sure, if it would be required for *every*, i.e. "normal" patterns. But
always doing it even for abusive ones doesn't feel right.

> Also I notice that p->pcre2_jit_on is per "struct grep_pat", so it
> is not like "once we see a pathological pattern, we turn off JIT
> completely for other patterns", right?  That is, if you have
> 
>     git grep -P -e "$A" -e "$B"
> 
> and we fail to compile "$A" (for whatever reason), we could still
> (attempt to) compile "$B".  Perhaps $A was too complex or was
> incompatible with JIT combined with other options, but $B may be
> easy enough to still be JITtable, in which case we would match with
> the JITted version of $B with interpreted version of $A, instead of
> failing, right?

The current version of git would fail hard if it fails to JIT compile
"$A". My patch doesn't change that behavior and that's intentional, as I
share Ævar's thinking about falling back to the interpreter mode for
"complex patterns" (which means pathological cases, really) is a bad
idea. While we might be able to compile the pattern and run it in
interpreter mode, it'll likely have a *much* higher runtime.

Just to get you a glimpse of how much longer, this is what it takes
running the pathological pattern from above's example on git.git:

  $ time git grep -P "(*NO_JIT)$(perl -e 'print "(.)" x 4000')"
  Binary file git-gui/macosx/git-gui.icns matches
  Binary file t/t5000/pax.tar matches
  Binary file t/t5004/big-pack.zip matches
  Binary file t/t5004/empty-with-pax-header.tar matches

  real	44m42,150s
  user	577m14,623s
  sys	0m46,210s


So this grep run eat up ~9.5 *hours* of CPU time. Do we really want to
fall back to something like this for the pathological cases? ...Yeah, I
don't think so either.

Thanks,
Mathias

Mathias Krause Jan. 29, 2023, 1:37 p.m. UTC | #6

On 27.01.23 19:46, Junio C Hamano wrote:
> Junio C Hamano <[e-mail]> writes:
> 
>>> What am I missing?
>>
>> Note that I've seen and recently re-read the discussion that leads to
>> https://lore.kernel.org/git/[e-mail]/
>>
>> I suspect that this auto-probe is related to solving "the user
>> thinks JIT is in use but because of failing JIT the user's pattern
>> is getting horrible performance" somehow.  But I do not think a hard
>> failure is a good approach to help users in such a situation.
> 
> I guess what I am saying is that the previous one that has been
> queued on 'seen' may be better.  It should cover your original
> "SELinux and other mechanisms can render JIT unusable because they
> do not allow dynamic generation of code" use case.

It clearly does cover my use case but it has a bad impact on the runtime
of pathological patterns. But if you think that's not an issue, I'll
update the changelog of v1 accordingly and resent it.

Thanks,
Mathias

Junio C Hamano Jan. 29, 2023, 5:15 p.m. UTC | #7

Mathias Krause <[e-mail]> writes:

> ... While we might be able to compile the pattern and run it in
> interpreter mode, it'll likely have a *much* higher runtime.
> ...
> So this grep run eat up ~9.5 *hours* of CPU time. Do we really want to
> fall back to something like this for the pathological cases? ...Yeah, I
> don't think so either.

You may not, but I do not agree with you at all.  The code should
not outsmart the user in such a case.

Even if the pattern the user came up with is impossible to grok for
a working JIT compiler, and it might be hard to grok for the
interpreter, what is the next step you recommend the user if you
refuse to fall back on the interprete?  "Rewrite it to please the
JIT compiler"?

If that is the best pattern the user can produce to solve the
problem at hand, being able to give the user an answer in 9 hours is
much better than not being able to give anything at all.  

Maybe after waiting for 5 minutes, the user gets bored and ^C, or
without killing it, open another terminal and try a different
patern, and in 9 hours, perhaps comes up with an equivalent (or
different but close enough) pattern that happens to run much faster,
at which time the user may kill the original one.  In any of these
cases, by refusing to run, the code is not doing any service to the
user.

Ævar Arnfjörð Bjarmason Jan. 30, 2023, 10:56 a.m. UTC | #8

On Sun, Jan 29 2023, Junio C Hamano wrote:

> Mathias Krause <[e-mail]> writes:
>
>> ... While we might be able to compile the pattern and run it in
>> interpreter mode, it'll likely have a *much* higher runtime.
>> ...
>> So this grep run eat up ~9.5 *hours* of CPU time. Do we really want to
>> fall back to something like this for the pathological cases? ...Yeah, I
>> don't think so either.
>
> You may not, but I do not agree with you at all.  The code should
> not outsmart the user in such a case.

It's the falling back in the nominal case that would be outsmarting the
user.

If I compile libpcre2 with JIT support I'm expecting Git to use that,
and not fall back in those cases where the JIT engine would give up.

> Even if the pattern the user came up with is impossible to grok for
> a working JIT compiler, and it might be hard to grok for the
> interpreter, what is the next step you recommend the user if you
> refuse to fall back on the interprete?  "Rewrite it to please the
> JIT compiler"?

I'd argue that it's pretty much impossible to unintentionally write such
pathological patterns, the edge cases where e.g. the JIT would run out
of resources v.s. the normal engine are a non-issue for any "normal"
use.

Pathological regexes are pretty much only interesting to anyone in the
context of DoS attacks where they're being used to cause intentional
slowdowns.

Here we're discussing an orthagonal case where the "JIT fails", but
rather than some pathological pattern it's because SELinux has made it
not work at runtime, and we're trying to tease the two cases apart.

> If that is the best pattern the user can produce to solve the
> problem at hand, being able to give the user an answer in 9 hours is
> much better than not being able to give anything at all.

Speed is a feature in itself, and in a lot of cases (e.g. user-supplied
patterns vulnerable to a DoS attack) continuing on the slow path is much
worse.

Even just using my terminal for ad-hoc "git grep", I'd *much* rather get
an early error about the pattern exceeding JIT resources than continuing
on the fallback path.

If I had somehow written one by accident (and this is stretching
credulity) you can usually apply some minor tweaks to the pattern, and
then execute it in seconds instead of minutes/hours.

> Maybe after waiting for 5 minutes, the user gets bored and ^C, or
> without killing it, open another terminal and try a different
> patern, and in 9 hours, perhaps comes up with an equivalent (or
> different but close enough) pattern that happens to run much faster,
> at which time the user may kill the original one.  In any of these
> cases, by refusing to run, the code is not doing any service to the
> user.

I don't think this is plausible at all per the above, and that we
shouldn't harm realistic use-cases to satisfy hypothetical ones.

Mathias Krause Jan. 30, 2023, 11:08 a.m. UTC | #9

On 29.01.23 18:15, Junio C Hamano wrote:
> Mathias Krause <[e-mail]> writes:
> 
>> ... While we might be able to compile the pattern and run it in
>> interpreter mode, it'll likely have a *much* higher runtime.
>> ...
>> So this grep run eat up ~9.5 *hours* of CPU time. Do we really want to
>> fall back to something like this for the pathological cases? ...Yeah, I
>> don't think so either.
> 
> You may not, but I do not agree with you at all.  The code should
> not outsmart the user in such a case.

It doesn't. My rhetoric question was just missing "automatically" to
state that I would dislike an *automatic* fallback to the interpreter
for *pathological cases.* But I'm fine with (and that's what this patch
is all about!) a fallback to the interpreter for patterns that simply
fail the JIT because it's broken. Sorry for the confusion.

> Even if the pattern the user came up with is impossible to grok for
> a working JIT compiler, and it might be hard to grok for the
> interpreter, what is the next step you recommend the user if you
> refuse to fall back on the interprete?  "Rewrite it to please the
> JIT compiler"?

Not at all. A user is still free to disable the JIT and enforce using
the interpreter by using the "(*NO_JIT)" prefix. My patch doesn't
disable this behavior. My patch only tries to avoid having to specify it
for "regular" patterns when the JIT is broken anyways.

The key here is that this would be a manual step (in contrast to an
automatic fallback), i.e. we require explicit user consent to accept the
worse runtime performance. And, IMHO, that should be acceptable from a
usability point of view as this would only be required for the
pathological cases an otherwise functional JIT simply cannot handle.

> If that is the best pattern the user can produce to solve the
> problem at hand, being able to give the user an answer in 9 hours is
> much better than not being able to give anything at all.

Sure, fully agree.

> Maybe after waiting for 5 minutes, the user gets bored and ^C, or
> without killing it, open another terminal and try a different
> patern, and in 9 hours, perhaps comes up with an equivalent (or
> different but close enough) pattern that happens to run much faster,
> at which time the user may kill the original one.  In any of these
> cases, by refusing to run, the code is not doing any service to the
> user.

My patch doesn't make it worse than what 'git grep' would currently be
doing. On the contrary, actually. It allows me to use PaX's MPROTECT and
have a functional 'git grep' as well.

Maybe the missing piece here is simply something like below to make
users more aware of the possibility to disable the JIT for the more
complex cases?:

diff --git a/grep.c b/grep.c
index 59afc3f07fc9..1422f168b087 100644
--- a/grep.c
+++ b/grep.c
@@ -357,7 +357,8 @@ static void compile_pcre2_pattern(struct grep_pat
*p, const struct grep_opt *opt
                        p->pcre2_jit_on = 0;
                        return;
                } else if (jitret) {
-                       die("Couldn't JIT the PCRE2 pattern '%s', got
'%d'\n", p->pattern, jitret);
+                       die("Couldn't JIT the PCRE2 pattern '%s', got
'%d'%s\n", p->pattern, jitret,
+                           pcre2_jit_functional() ? "\nYou might retry
by prefixing the pattern with '(*NO_JIT)'" : "");
                }

                /*

(Sorry about the wrapped lines, my mailer is just broken. I'll make it a
proper patch, if such functionality is indeed wanted.)

Thanks,
Mathias

Junio C Hamano Jan. 30, 2023, 6:49 p.m. UTC | #10

Ævar Arnfjörð Bjarmason <[e-mail]> writes:

> If I compile libpcre2 with JIT support I'm expecting Git to use that,
> and not fall back in those cases where the JIT engine would give up.

The thing is, the reason why their Git has JIT enabled pcre2 for
many users is not because they choose to compile their own Git for
themselves because they wanted to play with JIT.  To them, their
distro and/or their employer gave a precompiled Git, in the hope
that with JIT would be faster than without JIT when JIT is usable.

In that context, "Speed is a feature in itself" is correct but
"failing fast, forcing the user to try different things" is not a
"Speed" feature at all.  It may be interesting only for those who
are curious to see what pattern was rejected by JIT.  It is
especially true as (1) we are willing to fall back to interpreter in
the SELinux senario, and (2) for normal users who want to use Git,
and not necessarily interested in playing with JIT, there is no
other recourse than prefixing "I do not want this JITted" to their
pattern ANYWAY.  Why fail fast and force the user to take the only
recourse manually, when the machinery already knows what the user's
only viable alternative is (i.e. falling back to the interpreter)?

> Pathological regexes are pretty much only interesting to anyone in the
> context of DoS attacks where they're being used to cause intentional
> slowdowns.

Exactly.

> Here we're discussing an orthagonal case where the "JIT fails", but
> rather than some pathological pattern it's because SELinux has made it
> not work at runtime, and we're trying to tease the two cases apart.

s/and we're/but you're/.  And I do not think you want to.

> I don't think this is plausible at all per the above, and that we
> shouldn't harm realistic use-cases to satisfy hypothetical ones.

To me, what you are advocating is exactly the hypothetical ones that
harm end-users who did not choose to enable JIT themselves.  When JIT
fails for whatever reason (including the SELinux senario) for them,
they do not need to be told by Git failing, when the interpreter can
give them the correct answer.  Wanting to see the result of the
operation they asked Git to do, while allowing Git to use clever
optimizations WHEN ABLE, is what I see as realistic use-cases.

Junio C Hamano Jan. 30, 2023, 6:54 p.m. UTC | #11

Mathias Krause <[e-mail]> writes:

> My patch doesn't make it worse than what 'git grep' would currently be
> doing. On the contrary, actually. It allows me to use PaX's MPROTECT and
> have a functional 'git grep' as well.

I know.  But then without the "why did it fail?" logic (i.e. the v1
patch), it does not make it worse than the current code, either, and
of course allows you to use JIT-enabled pcre2 even where JIT is
impossible due to MPROTECT and whatever reasson.

> Maybe the missing piece here is simply something like below to make
> users more aware of the possibility to disable the JIT for the more
> complex cases?:

If we were to keep that "die", it is absolutely required, I would
think.  Users who got their Git with JIT-enabled pcre2 may be
viewing JIT merely as "a clever optimization the implementation is
allowed to use when able", without knowing and more importantly
without wanting to know how to disable it from within their
patterns.

But can't we drop that die() if we took the v1 route?

> diff --git a/grep.c b/grep.c
> index 59afc3f07fc9..1422f168b087 100644
> --- a/grep.c
> +++ b/grep.c
> @@ -357,7 +357,8 @@ static void compile_pcre2_pattern(struct grep_pat
> *p, const struct grep_opt *opt
>                         p->pcre2_jit_on = 0;
>                         return;
>                 } else if (jitret) {
> -                       die("Couldn't JIT the PCRE2 pattern '%s', got
> '%d'\n", p->pattern, jitret);
> +                       die("Couldn't JIT the PCRE2 pattern '%s', got
> '%d'%s\n", p->pattern, jitret,
> +                           pcre2_jit_functional() ? "\nYou might retry
> by prefixing the pattern with '(*NO_JIT)'" : "");
>                 }
>
>                 /*
>
> (Sorry about the wrapped lines, my mailer is just broken. I'll make it a
> proper patch, if such functionality is indeed wanted.)
>
> Thanks,
> Mathias

Junio C Hamano Jan. 30, 2023, 8:08 p.m. UTC | #12

Junio C Hamano <[e-mail]> writes:

> If we were to keep that "die", it is absolutely required, I would
> think.  Users who got their Git with JIT-enabled pcre2 may be
> viewing JIT merely as "a clever optimization the implementation is
> allowed to use when able", without knowing and more importantly
> without wanting to know how to disable it from within their
> patterns.
>
> But can't we drop that die() if we took the v1 route?

Having said all that, I do not mind queuing v2 if the "use *NO_JIT
to disable" is added to the message to help users who are forced to
redo the query.

And in practice, it shouldn't make that much difference, because the
only scenario (other than the SELinux-like situation where JIT is
compiled in but does not work at all) that the difference may matter
would happen when a non-trivial portion of the patterns users use
are not workable with JIT, but if that were the case, we would have
written JIT off as not mature enough and not yet usable long time
ago.  So, in practice, patterns refused by JIT would be a very tiny
minority to matter in real life, and "failing fast to inconvenience
users" would not be too bad.

So while I still think v1's simplicity is the right thing to have
here, I think it is waste of our braincell to compare v1 vs v2.  As
v2 gives smaller incremental behaviour change perceived by end
users, if somebody really wanted to, I'd expect that a low-hanging
fruit #leftoverbit on top of such a patch, after the dust settles,
would be to

 (1) rename pcre2_jit_functional() to fall_back_to_interpreter() or
     something,

 (2) add a configuration variable to tell fall_back_to_interpreter()
     that any form of JIT error is allowed to fall back to
     interpreter().

and such a patch will essentially give back the simplicity of v1 to
folks who opt into the configuration.

Thanks.

Junio C Hamano Jan. 30, 2023, 9:21 p.m. UTC | #13

Junio C Hamano <[e-mail]> writes:

> Having said all that, I do not mind queuing v2 if the "use *NO_JIT
> to disable" is added to the message to help users who are forced to
> redo the query.

In the meantime, here is what I plan to apply on top of v2 while
queuing it.  The message given to die() should lack the terminating
LF, and the overlong line can and should be split at operator
boundary.

Thanks.

 grep.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git c/grep.c w/grep.c
index 59afc3f07f..42f184bd09 100644
--- c/grep.c
+++ w/grep.c
@@ -357,7 +357,11 @@ static void compile_pcre2_pattern(struct grep_pat *p, const struct grep_opt *opt
 			p->pcre2_jit_on = 0;
 			return;
 		} else if (jitret) {
-			die("Couldn't JIT the PCRE2 pattern '%s', got '%d'\n", p->pattern, jitret);
+			die("Couldn't JIT the PCRE2 pattern '%s', got '%d'%s",
+			    p->pattern, jitret,
+			    pcre2_jit_functional() 
+			    ? "\nPerhaps prefix (*NO_GIT) to your pattern?" 
+			    : "");
 		}
 
 		/*

Ramsay Jones Jan. 30, 2023, 10:30 p.m. UTC | #14

On 30/01/2023 21:21, Junio C Hamano wrote:
> Junio C Hamano <[e-mail]> writes:
> 
>> Having said all that, I do not mind queuing v2 if the "use *NO_JIT
>> to disable" is added to the message to help users who are forced to
>> redo the query.
> 
> In the meantime, here is what I plan to apply on top of v2 while
> queuing it.  The message given to die() should lack the terminating
> LF, and the overlong line can and should be split at operator
> boundary.
> 
> Thanks.
> 
>  grep.c | 6 +++++-
>  1 file changed, 5 insertions(+), 1 deletion(-)
> 
> diff --git c/grep.c w/grep.c
> index 59afc3f07f..42f184bd09 100644
> --- c/grep.c
> +++ w/grep.c
> @@ -357,7 +357,11 @@ static void compile_pcre2_pattern(struct grep_pat *p, const struct grep_opt *opt
>  			p->pcre2_jit_on = 0;
>  			return;
>  		} else if (jitret) {
> -			die("Couldn't JIT the PCRE2 pattern '%s', got '%d'\n", p->pattern, jitret);
> +			die("Couldn't JIT the PCRE2 pattern '%s', got '%d'%s",
> +			    p->pattern, jitret,
> +			    pcre2_jit_functional() 
> +			    ? "\nPerhaps prefix (*NO_GIT) to your pattern?" 

s/NO_GIT/NO_JIT/ ? :)

ATB,
Ramsay Jones

> +			    : "");
>  		}
>  
>  		/*

Junio C Hamano Jan. 30, 2023, 11:27 p.m. UTC | #15

Ramsay Jones <[e-mail]> writes:

>> +			die("Couldn't JIT the PCRE2 pattern '%s', got '%d'%s",
>> +			    p->pattern, jitret,
>> +			    pcre2_jit_functional() 
>> +			    ? "\nPerhaps prefix (*NO_GIT) to your pattern?" 
>
> s/NO_GIT/NO_JIT/ ? :)

Indeed.  Thanks.

Mathias Krause Jan. 31, 2023, 7:30 a.m. UTC | #16

On 30.01.23 21:08, Junio C Hamano wrote:
> Junio C Hamano <[e-mail]> writes:
> 
>> If we were to keep that "die", it is absolutely required, I would
>> think.  Users who got their Git with JIT-enabled pcre2 may be
>> viewing JIT merely as "a clever optimization the implementation is
>> allowed to use when able", without knowing and more importantly
>> without wanting to know how to disable it from within their
>> patterns.
>>
>> But can't we drop that die() if we took the v1 route?
> 
> Having said all that, I do not mind queuing v2 if the "use *NO_JIT
> to disable" is added to the message to help users who are forced to
> redo the query.
> 
> And in practice, it shouldn't make that much difference, because the
> only scenario (other than the SELinux-like situation where JIT is
> compiled in but does not work at all) that the difference may matter
> would happen when a non-trivial portion of the patterns users use
> are not workable with JIT, but if that were the case, we would have
> written JIT off as not mature enough and not yet usable long time
> ago.  So, in practice, patterns refused by JIT would be a very tiny
> minority to matter in real life, and "failing fast to inconvenience
> users" would not be too bad.

Exactly!

> So while I still think v1's simplicity is the right thing to have
> here, I think it is waste of our braincell to compare v1 vs v2.  As
> v2 gives smaller incremental behaviour change perceived by end
> users, if somebody really wanted to, I'd expect that a low-hanging
> fruit #leftoverbit on top of such a patch, after the dust settles,
> would be to
> 
>  (1) rename pcre2_jit_functional() to fall_back_to_interpreter() or
>      something,
> 
>  (2) add a configuration variable to tell fall_back_to_interpreter()
>      that any form of JIT error is allowed to fall back to
>      interpreter().
> 
> and such a patch will essentially give back the simplicity of v1 to
> folks who opt into the configuration.

Fair enough. But aside from the W|X memory allocation denial exception
is the likelihood to run into the limitations of PCRE2's JIT requiring
the interpreter fallback so little (as otherwise we'd see it in the past
already), I think, the demand for such a knob is basically nonexistent.

Thanks,
Mathias

Mathias Krause Jan. 31, 2023, 7:48 a.m. UTC | #17

On 30.01.23 22:21, Junio C Hamano wrote:
> Junio C Hamano <[e-mail]> writes:
> 
>> Having said all that, I do not mind queuing v2 if the "use *NO_JIT
>> to disable" is added to the message to help users who are forced to
>> redo the query.
> 
> In the meantime, here is what I plan to apply on top of v2 while
> queuing it.  The message given to die() should lack the terminating
> LF, and the overlong line can and should be split at operator
> boundary.
> 
> Thanks.
> 
>  grep.c | 6 +++++-
>  1 file changed, 5 insertions(+), 1 deletion(-)
> 
> diff --git c/grep.c w/grep.c
> index 59afc3f07f..42f184bd09 100644
> --- c/grep.c
> +++ w/grep.c
> @@ -357,7 +357,11 @@ static void compile_pcre2_pattern(struct grep_pat *p, const struct grep_opt *opt
>  			p->pcre2_jit_on = 0;
>  			return;
>  		} else if (jitret) {
> -			die("Couldn't JIT the PCRE2 pattern '%s', got '%d'\n", p->pattern, jitret);
> +			die("Couldn't JIT the PCRE2 pattern '%s', got '%d'%s",
> +			    p->pattern, jitret,
> +			    pcre2_jit_functional() 
> +			    ? "\nPerhaps prefix (*NO_GIT) to your pattern?" 
> +			    : "");
>  		}
>  
>  		/*

Looks sensible, but maybe something like below would be even better?

diff --git a/grep.c b/grep.c
index 59afc3f07fc9..e0144ba77e7a 100644
--- a/grep.c
+++ b/grep.c
@@ -357,7 +357,13 @@ static void compile_pcre2_pattern(struct grep_pat *p, const struct grep_opt *opt
 			p->pcre2_jit_on = 0;
 			return;
 		} else if (jitret) {
-			die("Couldn't JIT the PCRE2 pattern '%s', got '%d'\n", p->pattern, jitret);
+			int do_clip = p->patternlen > 64;
+			int clip_len = do_clip ? 64 : p->patternlen;
+			die("Couldn't JIT the PCRE2 pattern '%.*s'%s, got '%d'%s",
+			    clip_len, p->pattern, do_clip ? "..." : "", jitret,
+			    pcre2_jit_functional()
+			    ? "\nPerhaps prefix (*NO_JIT) to your pattern?"
+			    : "");
 		}
 
 		/*

It'll ensure, git will be printing the hint even for very long patterns,
like the one I was testing this with ("$(perl -e 'print "(.)" x 4000')").

Thanks,
Mathias

Ævar Arnfjörð Bjarmason Jan. 31, 2023, 8:34 a.m. UTC | #18

On Mon, Jan 30 2023, Junio C Hamano wrote:

> Ævar Arnfjörð Bjarmason <[e-mail]> writes:
>
>> If I compile libpcre2 with JIT support I'm expecting Git to use that,
>> and not fall back in those cases where the JIT engine would give up.
>
> The thing is, the reason why their Git has JIT enabled pcre2 for
> many users is not because they choose to compile their own Git for
> themselves because they wanted to play with JIT.  To them, their
> distro and/or their employer gave a precompiled Git, in the hope
> that with JIT would be faster than without JIT when JIT is usable.
>
> In that context, "Speed is a feature in itself" is correct but
> "failing fast, forcing the user to try different things" is not a
> "Speed" feature at all.  It may be interesting only for those who
> are curious to see what pattern was rejected by JIT.  It is
> especially true as (1) we are willing to fall back to interpreter in
> the SELinux senario, and (2) for normal users who want to use Git,
> and not necessarily interested in playing with JIT, there is no
> other recourse than prefixing "I do not want this JITted" to their
> pattern ANYWAY.  Why fail fast and force the user to take the only
> recourse manually, when the machinery already knows what the user's
> only viable alternative is (i.e. falling back to the interpreter)?

Because we have an issue with (1), but not (2). How would (2) happen? So
far I've only seen intentionally pathological patterns designed to
trigger the JIT's limits. I don't think it's worth DWYM-ing that path,
when we're having to assume a lot about the "M" part of that.

>> Pathological regexes are pretty much only interesting to anyone in the
>> context of DoS attacks where they're being used to cause intentional
>> slowdowns.
>
> Exactly.
>
>> Here we're discussing an orthagonal case where the "JIT fails", but
>> rather than some pathological pattern it's because SELinux has made it
>> not work at runtime, and we're trying to tease the two cases apart.
>
> s/and we're/but you're/.  And I do not think you want to.

That s/// is fair, but brings me back to my question above of why we're
trying to solve (2) here.

>> I don't think this is plausible at all per the above, and that we
>> shouldn't harm realistic use-cases to satisfy hypothetical ones.
>
> To me, what you are advocating is exactly the hypothetical ones that
> harm end-users who did not choose to enable JIT themselves.  When JIT
> fails for whatever reason (including the SELinux senario) for them,
> they do not need to be told by Git failing, when the interpreter can
> give them the correct answer.  Wanting to see the result of the
> operation they asked Git to do, while allowing Git to use clever
> optimizations WHEN ABLE, is what I see as realistic use-cases.

I'm saying that the "JIT fails for whatever reason" is
hypothetical. It'll fail because of:

 - The (1) case, where we're categorically unable to run the JIT. Then
   we should proceed as if the JIT isn't available (as we do when it's
   e.g. not compiled into PCRE).

 - The pattern is pathological enough that it's about to take eons to
   execute it (2).

   The lack of bug reports about "hey, my existing 'git grep' pattern
   failed" when the JIT was shipped with v2.14.0 shows that this doesn't
   happen in practice.

 - The case where the API is returning some new error code that's
   unknown to us, let's call that (3).

Junio C Hamano Jan. 31, 2023, 4:41 p.m. UTC | #19

Mathias Krause <[e-mail]> writes:

> Looks sensible, but maybe something like below would be even better?

When I say "in the meantime", I expect it not to be the final one.
This time, it was meant as a mere reminder to me while I wait for
the (hopefully final) reroll.

Thanks.

Mathias Krause Jan. 31, 2023, 6:34 p.m. UTC | #20

On 31.01.23 17:41, Junio C Hamano wrote:
> Mathias Krause <[e-mail]> writes:
> 
>> Looks sensible, but maybe something like below would be even better?
> 
> When I say "in the meantime", I expect it not to be the final one.
> This time, it was meant as a mere reminder to me while I wait for
> the (hopefully final) reroll.

Got it, will send v3 (the final one, as three times is the charm, they
say) integrating the change to die() in a moment.

Thanks,
Mathias

Patch

diff --git a/grep.c b/grep.c
index 06eed694936c..59afc3f07fc9 100644
--- a/grep.c
+++ b/grep.c
@@ -262,6 +262,31 @@  static void pcre2_free(void *pointer, MAYBE_UNUSED void *memory_data)
 	free(pointer);
 }
 
+static int pcre2_jit_functional(void)
+{
+	static int jit_working = -1;
+	pcre2_code *code;
+	size_t off;
+	int err;
+
+	if (jit_working != -1)
+		return jit_working;
+
+	/*
+	 * Try to JIT compile a simple pattern to probe if the JIT is
+	 * working in general. It might fail for systems where creating
+	 * memory mappings for runtime code generation is restricted.
+	 */
+	code = pcre2_compile((PCRE2_SPTR)".", 1, 0, &err, &off, NULL);
+	if (!code)
+		return 0;
+
+	jit_working = pcre2_jit_compile(code, PCRE2_JIT_COMPLETE) == 0;
+	pcre2_code_free(code);
+
+	return jit_working;
+}
+
 static void compile_pcre2_pattern(struct grep_pat *p, const struct grep_opt *opt)
 {
 	int error;
@@ -317,8 +342,23 @@  static void compile_pcre2_pattern(struct grep_pat *p, const struct grep_opt *opt
 	pcre2_config(PCRE2_CONFIG_JIT, &p->pcre2_jit_on);
 	if (p->pcre2_jit_on) {
 		jitret = pcre2_jit_compile(p->pcre2_pattern, PCRE2_JIT_COMPLETE);
-		if (jitret)
+		if (jitret == PCRE2_ERROR_NOMEMORY && !pcre2_jit_functional()) {
+			/*
+			 * Even though pcre2_config(PCRE2_CONFIG_JIT, ...)
+			 * indicated JIT support, the library might still
+			 * fail to generate JIT code for various reasons,
+			 * e.g. when SELinux's 'deny_execmem' or PaX's
+			 * MPROTECT prevent creating W|X memory mappings.
+			 *
+			 * Instead of faling hard, fall back to interpreter
+			 * mode, just as if the pattern was prefixed with
+			 * '(*NO_JIT)'.
+			 */
+			p->pcre2_jit_on = 0;
+			return;
+		} else if (jitret) {
 			die("Couldn't JIT the PCRE2 pattern '%s', got '%d'\n", p->pattern, jitret);
+		}
 
 		/*
 		 * The pcre2_config(PCRE2_CONFIG_JIT, ...) call just