Horton

Thread

Commits

  1. Check the size in COPY_POINTER_FIELD

  2. Rethink regexp engine's backref-related compilation state.

  3. Fix use-after-free issue in regexp engine.

  4. Make regexp engine's backref-related compilation state more bulletproof.

  5. Really fix the ambiguity in REFRESH MATERIALIZED VIEW CONCURRENTLY.

  6. Avoid generating extra subre tree nodes for capturing parentheses.

  1. Assert triggered during RE_compile_and_cache

    Mark Dilger <mark.dilger@enterprisedb.com> — 2021-08-05T20:38:58Z

    Tom,

while testing your patch in [1], I stumbled upon the following assert in master, without your patch applied:

+select 'vyrlvyrlwvqko' ~ '(?:(?:((.))))((\2)\1.){0,0}?';
+server closed the connection unexpectedly
+   This probably means the server terminated abnormally
+   before or while processing the request.
+connection to server was lost


The assert itself dates back to a commit of yours from 2003.  I don't think you did anything wrong here, but I wonder if you might understand the code better than anyone else?

The relevant bit of the stack trace is:

    frame #3: 0x00000001020eff7d postgres`ExceptionalCondition(conditionName=<unavailable>, errorType=<unavailable>, fileName=<unavailable>, lineNumber=<unavailable>) at assert.c:69:2 [opt]
    frame #4: 0x0000000101e2c682 postgres`delsub(nfa=0x00007fc7e8407360, lp=0x00007fc7e8831010, rp=0x00007fc7e8827328) at regc_nfa.c:1265:2 [opt]
    frame #5: 0x0000000101e28dd8 postgres`parsebranch [inlined] parseqatom(v=<unavailable>, stopper=101, type=112, lp=<unavailable>, rp=0x00007fc7e8827328, top=<unavailable>) at regcomp.c:1084:3 [opt]
    frame #6: 0x0000000101e27de9 postgres`parsebranch(v=0x00007ffeee0a80b8, stopper=101, type=<unavailable>, left=<unavailable>, right=<unavailable>, partial=<unavailable>) at regcomp.c:759 [opt]
    frame #7: 0x0000000101e29719 postgres`parsebranch [inlined] parseqatom(v=<unavailable>, stopper=101, type=112, lp=<unavailable>, rp=0x00007fc7e8827328, top=<unavailable>) at regcomp.c:1282:23 [opt]
    frame #8: 0x0000000101e29639 postgres`parsebranch(v=0x00007ffeee0a80b8, stopper=101, type=<unavailable>, left=<unavailable>, right=<unavailable>, partial=<unavailable>) at regcomp.c:759 [opt]
    frame #9: 0x0000000101e2457b postgres`parse(v=0x00007ffeee0a80b8, stopper=101, type=112, init=0x00007fc7e8827280, final=0x00007fc7e88272b8) at regcomp.c:691:12 [opt]
    frame #10: 0x0000000101e234d2 postgres`pg_regcomp(re=0x00007ffeee0a8208, string=<unavailable>, len=<unavailable>, flags=<unavailable>, collation=<unavailable>) at regcomp.c:418:12 [opt]
    frame #11: 0x0000000101f75790 postgres`RE_compile_and_cache(text_re=<unavailable>, cflags=<unavailable>, collation=100) at regexp.c:186:19 [opt]
    frame #12: 0x0000000101f75b90 postgres`textregexeq [inlined] RE_compile_and_execute(text_re=<unavailable>, dat=<unavailable>, dat_len=13, cflags=3, collation=<unavailable>, nmatch=0, pmatch=<unavailable>) at regexp.c:351:7 [opt]

[1] https://www.postgresql.org/message-id/2219936.1628115334%40sss.pgh.pa.us

—
Mark Dilger
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

  2. Re: Assert triggered during RE_compile_and_cache

    Mark Dilger <mark.dilger@enterprisedb.com> — 2021-08-05T20:49:00Z

    
> On Aug 5, 2021, at 1:38 PM, Mark Dilger <mark.dilger@enterprisedb.com> wrote:
> 
> +select 'vyrlvyrlwvqko' ~ '(?:(?:((.))))((\2)\1.){0,0}?';

I've boiled it down a bit more:

+select '' ~ '()\1{0}';
+ ?column? 
+----------
+ t
+(1 row)
+
+select '' ~ '()(\1){0}';
+ ?column? 
+----------
+ t
+(1 row)
+
+select '' ~ '(())\2{0}';
+ ?column? 
+----------
+ t
+(1 row)
+
+select '' ~ '(())(\2){0}';
+server closed the connection unexpectedly
+   This probably means the server terminated abnormally
+   before or while processing the request.
+connection to server was lost

Any ideas?

—
Mark Dilger
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

  3. Re: Assert triggered during RE_compile_and_cache

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-08-05T22:15:27Z

    Mark Dilger <mark.dilger@enterprisedb.com> writes:
> +select '' ~ '(())(\2){0}';
> +server closed the connection unexpectedly

> Any ideas?

Huh.  This seems like some deficiency in the part of parseqatom
starting with

	/* annoying special case:  {0} or {0,0} cancels everything */
	if (m == 0 && n == 0)

but I don't immediately see what's different about your failing case
versus the not-failing ones.

			regards, tom lane

  4. Re: Assert triggered during RE_compile_and_cache

    Mark Dilger <mark.dilger@enterprisedb.com> — 2021-08-05T22:22:57Z

    
> On Aug 5, 2021, at 3:15 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> 
> I don't immediately see what's different about your failing case
> versus the not-failing ones.

I have now found lots of cases of this failure.  I *believe* the backreference is always greater than 1, and it is always in a capture group which then has the {0} or {0,0} applied to it.

You can find lots of cases using the attached regex generating script I whipped up for testing your work.  (Note this is just a quick and dirty tool for hacking, not anything refined.)

  5. Re: Assert triggered during RE_compile_and_cache

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-08-05T23:16:22Z

    Mark Dilger <mark.dilger@enterprisedb.com> writes:
> I have now found lots of cases of this failure.  I *believe* the backreference is always greater than 1, and it is always in a capture group which then has the {0} or {0,0} applied to it.

Hm.  I thought that this might be an old issue, but I'm not seeing the
crash in pre-v14 branches.  That means it's some bug introduced in
the performance improvements I did a few months ago.  Open item added.

			regards, tom lane

  6. Re: Assert triggered during RE_compile_and_cache

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-08-06T00:13:03Z

    I wrote:
> Hm.  I thought that this might be an old issue, but I'm not seeing the
> crash in pre-v14 branches.  That means it's some bug introduced in
> the performance improvements I did a few months ago.  Open item added.

git bisect says the trouble started with

ea1268f6301cc7adce571cc9c5ebe8d9342a2ef4 is the first bad commit
commit ea1268f6301cc7adce571cc9c5ebe8d9342a2ef4
Author: Tom Lane <tgl@sss.pgh.pa.us>
Date:   Sat Feb 20 19:26:41 2021 -0500

    Avoid generating extra subre tree nodes for capturing parentheses.

I probably won't be able to dig deeper for a little while.

			regards, tom lane

  7. Re: Assert triggered during RE_compile_and_cache

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-08-07T21:44:39Z

    I wrote:
>> Hm.  I thought that this might be an old issue, but I'm not seeing the
>> crash in pre-v14 branches.  That means it's some bug introduced in
>> the performance improvements I did a few months ago.  Open item added.

> git bisect says the trouble started with
> ea1268f6301cc7adce571cc9c5ebe8d9342a2ef4 is the first bad commit

Here's a draft fix for this.  The issue seems to be that parseqatom
records where a previous capture group is by saving a pointer to
the "subre" that parse() returned for it.  That was okay before
said commit because we didn't do anything further to that subre:
we immediately wrapped it into a parent subre, and then any further
hacking that parseqatom did was done on the parent subre.  But after
ea1268f63, in most cases we'd hack right on that same subre, thus
potentially modifying the portion of the NFA that would be copied
by a subsequent back-reference.

The particular thing that's asserting when you wrap {0} around such
a back-ref is just accidental road kill: it happens to notice that
the NFA is no longer consistent, because there's no path leading
from the start to the end of the copied sub-NFA, thanks to the copying
having been done between a pair of states that weren't actually
appropriate to reference.  What surprises me about this is not that
crash, but that we didn't see fundamental breakage of backref-using
patterns all over the place.  It evidently breaks only in corner
cases, but I'm not quite sure why the effects are so limited.

Anyway, the fix seems pretty straightforward.  We don't really need
anything about the subre as such except for its starting and ending
NFA states, so the attached modifies things to record only those
state pointers.  I'm not done testing this by any means, but it
does fix the two cases you showed, and I've been running that perl
script for some time with no further crashes.

I suspect the assertion you hit with the REG_NOSUB patch was just
further fallout from this same basic bug, but I've not yet rebased
that patch over this to check.

			regards, tom lane

  8. Re: Assert triggered during RE_compile_and_cache

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-08-08T01:03:26Z

    I wrote:
> ... What surprises me about this is not that
> crash, but that we didn't see fundamental breakage of backref-using
> patterns all over the place.  It evidently breaks only in corner
> cases, but I'm not quite sure why the effects are so limited.

Ah-hah, I've sussed it.  I'd supposed that the issue was that parseqatom
could replace the subre atom's endpoints in the bit where it starts
to "prepare a general-purpose state skeleton".  However, it seems that
that's not what makes it go off the rails.  Rather, in the specific
combination we've got in the test case, the next outer recursion level
of parseqatom() decides that it can free the subre that was returned
by the inner level, *which is the same subre that v->subs[n] is pointing
to*.  So this is really a use-after-free problem.  freesrnode() won't
actually free() the node, just stick it back onto the chain for possible
recycling --- and it doesn't clear the state pointer fields when it
does that.  So there's no use-after-free that ordinary tools could detect.
We only see a problem manifest if the subre node is reused later, which
explains why '(())(\2){0}' fails while '(())\2{0}' does not.

So the problem boils down to parseqatom deciding it can free child
subre nodes that it knows little about the provenance of.  It would
be safer to make that optimization by instead freeing the "top"
node passed in from parsebranch, which we know has got no other
interesting linkages.  That requires tweaking the API of parseqatom,
which why I'd not done it like that to begin with --- but that's not
a hard or complicated change, just a mite tedious.

Hence, the attached patch.

While this is sufficient to make the problem go away, I'm
inclined to apply both changesets.  Even if it accidentally
works right now to have later backrefs consult the outer s/s2
state pair rather than the original pair, that seems far too
convoluted and bug-prone.  The outer states should be strictly
the concern of the iteration setup logic in the outer invocation
of parseqatom.

(I'm sort of wondering now whether the outer s/s2 states are
even really necessary anymore ... maybe Spencer put those in
as a way of preventing some prehistoric version of this bug.
But I'm not excited about messing with that right now.)

			regards, tom lane

  9. Re: Assert triggered during RE_compile_and_cache

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-08-08T16:31:53Z

    I wrote:
> While this is sufficient to make the problem go away, I'm
> inclined to apply both changesets.  Even if it accidentally
> works right now to have later backrefs consult the outer s/s2
> state pair rather than the original pair, that seems far too
> convoluted and bug-prone.  The outer states should be strictly
> the concern of the iteration setup logic in the outer invocation
> of parseqatom.

> (I'm sort of wondering now whether the outer s/s2 states are
> even really necessary anymore ... maybe Spencer put those in
> as a way of preventing some prehistoric version of this bug.
> But I'm not excited about messing with that right now.)

I realized that the earlier patch is actually a bad idea, because
it breaks the possibility of updating the subre to mark it as
being referenced by a later backref, as the REG_NOSUB patch needs
to do.  However, on closer study, the outer s/s2 states being
added by the "prepare a general-purpose state skeleton" stanza
really are duplicative of the ones we already made for a
parenthesized atom, so we can just get rid of them.  Done that
way.

			regards, tom lane

  10. Re: Assert triggered during RE_compile_and_cache

    Mark Dilger <mark.dilger@enterprisedb.com> — 2021-08-08T17:00:10Z

    
> On Aug 8, 2021, at 9:31 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> 
> I realized that the earlier patch is actually a bad idea

Applying only your <fix-backref-corner-case-1.patch> to master, the following which did not crash begins to crash:

 select regexp_split_to_array('rjgykkkk', '(?:(.))((\1\1.))');

It also changes the results for another one:

 select regexp_split_to_array('jdpveoarcnsarcnsarcnszieqbqbqbqbiufdlywphbnrxtdoboouuzcqiqmenj', '()((.)){1}?\3?', 'itx');
-                                                                                     regexp_split_to_array                                                                                      
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
- {"","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""}
+                      regexp_split_to_array                       
+------------------------------------------------------------------
+ {jdpveoarcnsarcnsarcnszieqbqbqbqbiufdlywphbnrxtdoboouuzcqiqmenj}

I'm not sure what *should* be returned here, only that it is a behavioral change.

—
Mark Dilger
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

  11. Re: Assert triggered during RE_compile_and_cache

    Mark Dilger <mark.dilger@enterprisedb.com> — 2021-08-08T17:15:28Z

    
> On Aug 7, 2021, at 6:03 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> 
> That requires tweaking the API of parseqatom,
> which why I'd not done it like that to begin with --- but that's not
> a hard or complicated change, just a mite tedious.
> 
> Hence, the attached patch.

Applying your <alternate-backref-corner-case-fix-1.patch> to master changes the outcome of some regular expression queries, but I *think* it changes them for the better.

These three look to me exactly correct after the patch, and wrong before:

 select regexp_matches('vnrungnajjjgkaaeaper', '((.))(((\1)))((?:\5..))', 'mx');
- regexp_matches 
-----------------
-(0 rows)
+ regexp_matches  
+-----------------
+ {j,j,j,j,j,jgk}
+(1 row)

 select regexp_match('kgkgeganlifykxhfspjtgluwluwluwdfdfbbdjvrxjvrxedndrkaxxvbtqdj', '((.))\2');
  regexp_match
 --------------
- 
+ {b,b}
 (1 row)

 select regexp_split_to_array('uuuzkodphfbfbfb', '((.))(\1\2)', 'ntw');
  regexp_split_to_array
 -----------------------
- {uuuzkodphfbfbfb}
+ {"",zkodphfbfbfb}
 (1 row)

But these next two look to me correct before the patch and wrong after:

 select regexp_matches('ircecpbgyiggvtruqgxzigxzigxzisdbkuhbkuhrvl', '(((.)))(?:(\3))[^\f]');
  regexp_matches
 ----------------
-(0 rows)
+ {g,g,g,g}
+(1 row)

 select regexp_matches('fhgxnvbvjaej', '(((.)).)((\3)((.)))', 'csx');
- regexp_matches 
-----------------
-(0 rows)
+  regexp_matches   
+-------------------
+ {vb,v,v,vj,v,j,j}
+(1 row)

—
Mark Dilger
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

  12. Re: Assert triggered during RE_compile_and_cache

    Mark Dilger <mark.dilger@enterprisedb.com> — 2021-08-08T17:28:55Z

    
> On Aug 8, 2021, at 10:15 AM, Mark Dilger <mark.dilger@enterprisedb.com> wrote:
> 
> But these next two look to me correct before the patch and wrong after:
> 
> select regexp_matches('ircecpbgyiggvtruqgxzigxzigxzisdbkuhbkuhrvl', '(((.)))(?:(\3))[^\f]');
>  regexp_matches
> ----------------
> -(0 rows)
> + {g,g,g,g}
> +(1 row)
> 
> select regexp_matches('fhgxnvbvjaej', '(((.)).)((\3)((.)))', 'csx');
> - regexp_matches 
> -----------------
> -(0 rows)
> +  regexp_matches   
> +-------------------
> + {vb,v,v,vj,v,j,j}
> +(1 row)

Scratch that.  On further thought, these also look correct.  I wasn't doing the capturing in my head correctly.  So I think the patch is working!  I'll test a bit longer.

Is this patch (alternate-backref-corner-case-fix-1.patch) the current state of your patch set?  I'd like to be sure I'm testing your latest work.  Thanks.

—
Mark Dilger
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

  13. Re: Assert triggered during RE_compile_and_cache

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-08-08T17:29:36Z

    Mark Dilger <mark.dilger@enterprisedb.com> writes:
> Applying your <alternate-backref-corner-case-fix-1.patch> to master changes the outcome of some regular expression queries, but I *think* it changes them for the better.

[ squint... ] You sure you applied the patch properly?  All these examples
give me the same results in HEAD (with said patches as-committed) and v13.

			regards, tom lane

  14. Re: Assert triggered during RE_compile_and_cache

    Mark Dilger <mark.dilger@enterprisedb.com> — 2021-08-08T17:32:56Z

    
> On Aug 8, 2021, at 10:29 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> 
> Mark Dilger <mark.dilger@enterprisedb.com> writes:
>> Applying your <alternate-backref-corner-case-fix-1.patch> to master changes the outcome of some regular expression queries, but I *think* it changes them for the better.
> 
> [ squint... ] You sure you applied the patch properly?  All these examples
> give me the same results in HEAD (with said patches as-committed) and v13.
> 
> 			regards, tom lane

I'm not sure what you mean by "as-committed".  Did you commit one of these recently?

—
Mark Dilger
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

  15. Re: Assert triggered during RE_compile_and_cache

    Mark Dilger <mark.dilger@enterprisedb.com> — 2021-08-08T17:34:16Z

    
> On Aug 8, 2021, at 10:32 AM, Mark Dilger <mark.dilger@enterprisedb.com> wrote:
> 
> I'm not sure what you mean by "as-committed".  Did you commit one of these recently?

Nevermind, I see the commit now.

I'll rerun my tests with the new master.  I was still using the code that I pulled yesterday.

—
Mark Dilger
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

  16. Re: Assert triggered during RE_compile_and_cache

    Mark Dilger <mark.dilger@enterprisedb.com> — 2021-08-08T18:02:03Z

    
> On Aug 8, 2021, at 10:34 AM, Mark Dilger <mark.dilger@enterprisedb.com> wrote:
> 
> I'll rerun my tests with the new master.  I was still using the code that I pulled yesterday.

I am now testing REL_13_STABLE (ba9f665a4413f855bbf4b544481db326f7b9bd73) vs master (c1132aae336c41cf9d316222e525d8d593c2b5d2).  The regular expressions we discussed upthread show no differences.

There are a few changes which appear correct to me, but I don't know if you expected them:

 select regexp_match('hko', '((((?<!.))))(.(\3)(\1.))');
- regexp_match 
---------------
- 
+    regexp_match    
+--------------------
+ {"","","",hk,"",k}
 (1 row)

 select 'nigqvigqvee' !~ '(())((\2)\2)(?:([^\W]))';
-ERROR:  invalid regular expression: invalid escape \ sequence
+ ?column? 
+----------
+ f
+(1 row)
+

 select regexp_replace('tl', '.{0}?(((?<![^][^]{1}?)))(.)\2{6}?', 'jx', 'mt');
  regexp_replace
 ----------------
- tl
+ jxl
 (1 row)


—
Mark Dilger
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

  17. Re: Assert triggered during RE_compile_and_cache

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-08-08T18:44:02Z

    Mark Dilger <mark.dilger@enterprisedb.com> writes:
> There are a few changes which appear correct to me, but I don't know if you expected them:

>  select regexp_match('hko', '((((?<!.))))(.(\3)(\1.))');
> - regexp_match 
> ---------------
> - 
> +    regexp_match    
> +--------------------
> + {"","","",hk,"",k}
>  (1 row)

Yes, this one is a consequence of 4aea704a5 (Fix semantics of regular
expression back-references).  The lookbehind constraint should not be
applied within the back-ref.

>  select 'nigqvigqvee' !~ '(())((\2)\2)(?:([^\W]))';
> -ERROR:  invalid regular expression: invalid escape \ sequence
> + ?column? 
> +----------
> + f
> +(1 row)
> +

and this one of 2a0af7fe4 (Allow complemented character class escapes
within regex brackets).

>  select regexp_replace('tl', '.{0}?(((?<![^][^]{1}?)))(.)\2{6}?', 'jx', 'mt');
>   regexp_replace
>  ----------------
> - tl
> + jxl
>  (1 row)

This looks like also a consequence of 4aea704a5.

			regards, tom lane