Regexp memory corruption with large tries

[pengvado]

The following script crashes with "regexp memory corruption at ./foo.pl line 4."

use re "Debug";
$x = join "|", "aaa".."mzz";
$y = join "|", "naa".."zzz";
"fnord" =~ m/(?:$x)|(?:$y)/;

The "use re 'Debug';" line is part of triggering the bug; the same regexp without debugging doesn't crash.

I have reproduced this with perl-5.38.2 and 5.40.2 and 5.42.RC1.
perl-5.36.0 is not affected.
Git bisect blames acababb.

---

Perl configuration

Summary of my perl5 (revision 5 version 40 subversion 2) configuration:
  Commit id: 2e0f6a60c12ff9b5fd18e5a18d350b4366ea12b7
  Platform:
    osname=linux
    osvers=6.6.21-gentoo-dist
    archname=x86_64-linux
    uname='linux pai 6.6.21-gentoo-dist #1 smp preempt_dynamic thu apr 11 23:32:55 -00 2024 x86_64 amd ryzen 9 7950x 16-core processor authenticamd gnulinux '
    config_args='-de -Dmksymlinks -Dprefix=/usr/local'
    hint=recommended
    useposix=true
    d_sigaction=define
    useithreads=undef
    usemultiplicity=undef
    use64bitint=define
    use64bitall=define
    uselongdouble=undef
    usemymalloc=n
    default_inc_excludes_dot=define
  Compiler:
    cc='cc'
    ccflags ='-fwrapv -fno-strict-aliasing -pipe -fstack-protector-strong -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64'
    optimize='-O2'
    cppflags='-fwrapv -fno-strict-aliasing -pipe -fstack-protector-strong'
    ccversion=''
    gccversion='13.2.1 20240113'
    gccosandvers=''
    intsize=4
    longsize=8
    ptrsize=8
    doublesize=8
    byteorder=12345678
    doublekind=3
    d_longlong=define
    longlongsize=8
    d_longdbl=define
    longdblsize=16
    longdblkind=3
    ivtype='long'
    ivsize=8
    nvtype='double'
    nvsize=8
    Off_t='off_t'
    lseeksize=8
    alignbytes=8
    prototype=define
  Linker and Libraries:
    ld='cc'
    ldflags =' -fstack-protector-strong -L/usr/local/lib'
    libpth=/usr/lib /usr/local/lib /lib64 /usr/lib64 /lib /usr/local/lib64
    libs=-lpthread -lgdbm -ldl -lm -lcrypt -lutil -lc -lgdbm_compat
    perllibs=-lpthread -ldl -lm -lcrypt -lutil -lc
    libc=/lib/../lib64/libc.so.6
    so=so
    useshrplib=false
    libperl=libperl.a
    gnulibc_version='2.38'
  Dynamic Linking:
    dlsrc=dl_dlopen.xs
    dlext=so
    d_dlsymun=undef
    ccdlflags='-Wl,-E'
    cccdlflags='-fPIC'
    lddlflags='-shared -O2 -L/usr/local/lib -fstack-protector-strong'


---
@INC for perl 5.40.2:
    /usr/local/lib/perl5/site_perl/5.40.2/x86_64-linux
    /usr/local/lib/perl5/site_perl/5.40.2
    /usr/local/lib/perl5/5.40.2/x86_64-linux
    /usr/local/lib/perl5/5.40.2
    /usr/local/lib/perl5/site_perl

---
Environment for perl 5.40.2:
    HOME=/home/pengvado
    LANG=en_US.utf8
    LANGUAGE (unset)
    LC_COLLATE=C
    LD_LIBRARY_PATH (unset)
    LOGDIR (unset)
    PATH=/usr/local/bin:/usr/local/sbin:/usr/sbin:/usr/bin:/sbin:/bin:/opt/bin
    PERL_BADLANG (unset)
    SHELL=/bin/zsh

[jkeenan]

Bisecting with the following invocation ...

perl Porting/bisect.pl \
--start=v5.37.9 \
--end=v5.37.10 \
-- ./perl -Ilib $P5P_DIR/gh-23388-regexp-debug.pl

... confirmed acababb as the breaking commit:

commit acababb42be12ff2986b73c1bfa963b70bb5d54e
Author:     Yves Orton <demerphq@gmail.com>
AuthorDate: Mon Jan 9 16:34:13 2023
Commit:     Yves Orton <demerphq@gmail.com>
CommitDate: Mon Mar 13 09:26:08 2023

    regexec.c - teach BRANCH and BRANCHJ nodes to reset capture buffers

@demerphq, can you take a look? Thanks.

[richardleach]

Disclaimer: I understand next to nothing about the regex internals.

The DEBUG_r statement at https://github.com/Perl/perl5/blob/blead/regcomp_trie.c#L1550-L1559 seems to be doing the corruption:

        DEBUG_r(if (optimize) {
            /*
                Try to clean up some of the debris left after the
                optimisation.
             */
            while( optimize < jumper ) {
                OP( optimize ) = OPTIMIZED;
                optimize++;
            }
        });

At least, if this code is removed - or the code just above that sets optimize is removed - the OP's script doesn't warn about memory corruption.

Presumably something about the optimisation, or the clean-up after it, needs updating following acababb.

[richardleach]

The OP's script outputs like this:

TRIE: Chid:0x6  CP:0x66   'f' St:0x1    W:0x0  - good -> St: 0xDBD 
TRIE: Chid:0xE  CP:0x6E   'n' St:0xDBD  W:0x0  - good -> St: 0xF1D 
TRIE: Chid:0xF  CP:0x6F   'o' St:0xF1D  W:0x0  - good -> St: 0xF2C 
TRIE: Chid:0x0  CP:0x0        St:0xF2C  W:0xE95 - last -> St: 0x0   
7f98b1b37acc 109
regexp memory corruption at /tmp/23388 line 4.

109 is the node definition for OPTIMIZED: https://github.com/Perl/perl5/blob/blead/regnodes.h#L1226

[richardleach]

On a DDEBUGGING build with -Drv (runtime output only!):

Matching REx "(?:aaa|aab|aac|aad|aae|aaf|aag|aah|aai|aaj|aak|aal|aam|aan|a"... against "fnord"
                             |   0| Setting an EVAL scope, savestack = 3,
   0 <> <fnord>              |   0| regmatch start
   0 <> <fnord>              |   0| 1:BRANCH (buf:0/0)(35156)
                             |   0| Setting an EVAL scope, savestack = 5,
                             |   0| push #0   BRANCH_next 
   0 <> <fnord>              |   1|  3:TRIEC-EXACT(JUMP)<S:1/9140 W:8788 L:3/3 C:26364/26>[a-m](4775)
   1 <f> <nord>              |   1| TRIE: Chid:0x6  CP:0x66   'f' St:0x1    W:0x0  - good -> St: 0xDBD 
   2 <fn> <ord>              |   1| TRIE: Chid:0xE  CP:0x6E   'n' St:0xDBD  W:0x0  - good -> St: 0xF1D 
   3 <fno> <rd>              |   1| TRIE: Chid:0xF  CP:0x6F   'o' St:0xF1D  W:0x0  - good -> St: 0xF2C 
   3 <fno> <rd>              |   1| TRIE: Chid:0x0  CP:0x0        St:0xF2C  W:0xE95 - last -> St: 0x0   
                             |   1|  TRIE: got 1 possible matches
                             |   1|  Setting an EVAL scope, savestack = 5,
                             |   1|  TRIE: matched word #3733, continuing
                             |   1|  push #1   TRIE_next  
                             |   1|       #0   BRANCH_next 
   3 <fno> <rd>              |   2|   4775:OPTIMIZED(4779)
7f30a95acae4 109
regexp memory corruption at /tmp/23388 line 4.