Tcl Source Code

View Ticket
Login
Ticket UUID: 7d47ba7d9497fda88c064b6152d3a2126c3cd9d2
Title: Stack overruns in regexp code
Type: Bug Created on: 2015-10-17 03:38:02
Submitter: tgl Assigned to: jan.nijtmans
Subsystem: 43. Regexp Severity: Important
Priority: 5 Medium Last modified: 2026-11-15 14:30:08
Status: Open Closed by: nobody
Resolution: None Closed on: 2026-11-01 16:57:43
Version: 8.6.18, 9.0.5, 9.1.0
Description:
There are various ways to drive the regexp code into stack overflow.  An example is that

regexp {(^$)+} {z}

will cause a stack overrun in markreachable() in 8.6.4.  (On my x86_64 machine, if I set "ulimit -s 1024" it takes about 4 minutes to get to this point, but it will get there.)  I believe this is driven by the problem discussed in http://core.tcl.tk/tcl/tktview?name=8f245009b0 which I plan to submit a fix for, but the point that concerns me right now is that there are multiple places that recurse to a depth limited only by the size of the regexp NFA, and if you don't have lots of stack space you are going to get a SIGSEGV on stack overflow.

The Postgres project has decided to deal with this hazard by uniformly installing stack overflow checks in all recursive functions in the regex code; see
http://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=b63fc28776c5d2efdb4de326ad0f0b5b88f82220

I would like to submit a Tcl-adapted version of that patch, but I do not know what implementation technology would be considered acceptable, so the point of this bug report is to ask.

I see that you guys previously noted the possibility of stack overrun in duptraverse() and fixed it with a hard-wired recursion depth count limit.  That answer doesn't seem too appealing to me: it complicates the function's API and it's very unclear what number to use for the limit.  So propagating the same methodology into a dozen other places is not attractive.

The technology Postgres is using depends on measuring the distance from a function's local variables to a stack base pointer established at execution startup.  I do not see how we can use that exact approach in Tcl, since Tcl is fundamentally a library not an application and can't run at execution start; but I wonder if it would be okay to decree that we'll allow a maximum stack depth of so-and-so-many kilobytes measured from the entry to regcomp() or regexec() respectively.  That could be mechanized by taking the address of the "struct vars" struct as being the measurement reference.

Comments or better ideas appreciated.
User Comments:
tgl added on 2015-10-17 04:18:43:
Note: open tickets 1905562 and 267b7e2334 both appear related to this.

dgp added on 2015-10-19 15:35:29:
I don't have much to add.  Just want to confirm your instinct
that the hard limit we stuck into Tcl 8.6 was a mistake that
you do not want to repeat.

dgp added on 2015-10-21 14:20:53:
I brought over some of this, but since the stack depth
test doesn't port, I just punted and created a
STACK_TOO_DEEP() that always returns false, so
stack checking is a no-op.  Room for improvement.

tgl added on 2015-10-21 17:04:26:
OK, I'll submit a patch in this ticket to make it do something real, but probably not for a week or two.

Is this code checked into mainline yet?

serhiy.storchaka added on 2026-10-10 20:48:01:

The (^$)+ example is long fixed, but stack overflow was still easy to trigger in 8.6, 9.0 and 9.1: parentheses nested 40000 deep crashed in parse(), and lookahead constraints nested only 600 deep crashed in the checkLAConstraint() recursion, because each level kept a 16 KB small DFA on the stack. STACK_TOO_DEEP() was still defined as 0.

Proposed fix in branch regexp-stack-depth, following your proposal: STACK_TOO_DEEP() limits the stack used by one compile or execution to REG_MAX_STACK_DEPTH (1 MB by default), measured from a local variable of compile() or exec(), and it is checked in the same places as in PostgreSQL. Lookahead DFAs are cached per execution, as in PostgreSQL's getladfa(), instead of being built on the stack. Too deep nesting now fails with "regular expression is too complex". Tests reg-33.32 to 33.35.


serhiy.storchaka added on 2026-10-11 10:09:04:

A fixed limit cannot protect threads with smaller stacks: with a 1 MB stack, the branch crashed in duptraverse(). Now STACK_TOO_DEEP() also uses the real stack limit of the current thread where the system reports it (new internal TclpGetCStackLimit(): pthread_getattr_np, pthread_attr_get_np, pthread_get_stackaddr_np, pthread_stackseg_np, thr_stksegment, VirtualQuery), with REG_MAX_STACK_DEPTH as a cap. New test stack-4.1 runs deep REs with a 256 KB stack. Tested on Linux, Windows, FreeBSD, DragonFly, NetBSD, OpenBSD and OpenIndiana.


jan.nijtmans added on 2026-10-19 21:08:23:

Now merged to [4a966b9df4|trunk]

In addition, tested on MacOS. CI build is clean.

I'm reluctant to merge further to core-9-0-branch for now, since Tcl 9.0.5 is coming soon.


serhiy.storchaka added on 2026-10-28 11:04:20:

On Alpine Linux (musl), stack-4.1 segfaults: TclpGetCStackLimit() returns NULL there, so the 1 MB default is used. Fixed on branch musl-stack-limit.


jan.nijtmans added on 2026-10-28 13:53:40:

> On Alpine Linux (musl), stack-4.1 segfaults

Thanks! This part now merged to trunk too.


serhiy.storchaka added on 2026-11-13 19:26:13:

The stack check misfires under AddressSanitizer with its fake stack (the default in GCC 15): addresses of local variables are then on the heap, so the computed depth is meaningless, and even loading a package fails with "regular expression is too complex". Proposed fix in branch regexp-stack-check-asan: use the frame address with GCC and Clang.


chrstphrchvz added on 2026-11-15 01:26:03:

Can the fix for this ticket instead make use of TclGetCStackPtr() (the existing fix for [7371b6270b])? I believe REG_STACK_ADDR() might be duplicating it.


serhiy.storchaka added on 2026-11-15 14:30:08:

It is the same technique (__builtin_frame_address(0)), but calling TclGetCStackPtr() in the check makes regexp compilation about 5% slower, since the check runs at every recursion level. I'd rather keep the macro inline, and add _AddressOfReturnAddress() for MSVC as TclGetCStackPtr() does.