Tcl Source Code

View Ticket
Login
2026-11-18
18:32 • Closed ticket [7d47ba7d94]: Stack overruns in regexp code plus 4 other chang... artifact: adb199c0ef user: serhiy.storchaka
18:27 • Ticket [7d47ba7d94]: 3 changes artifact: 0be96ffbb5 user: serhiy.storchaka
18:21
Fix [7d47ba7d94]: the regexp engine could overflow the C stack on deeply nested REs check-in: e720024d74 user: serhiy.storchaka tags: core-8-6-branch
16:06 • Ticket [7d47ba7d94] Stack overruns in regexp code status still Pending with ... artifact: 4c3dea3ce2 user: jan.nijtmans
16:05 • Pending ticket [7d47ba7d94]. artifact: a3b05b5380 user: jan.nijtmans
16:01
Fix [7d47ba7d94]: the regexp engine could overflow the C stack on deeply nested REs check-in: 2f0f1fadba user: jan.nijtmans tags: core-9-0-branch
2026-11-15
14:30 • Ticket [7d47ba7d94] Stack overruns in regexp code status still Open with 3 o... artifact: dafe13f3fb user: serhiy.storchaka
01:26 • Ticket [7d47ba7d94]: 3 changes artifact: 7eb572b882 user: chrstphrchvz
2026-11-13
21:48
[7d47ba7d94] follow-up: stack check misfires under AddressSanitizer check-in: 942d86d156 user: jan.nijtmans tags: trunk, main
19:26 • Open ticket [7d47ba7d94]: Stack overruns in regexp code plus 5 other changes artifact: a5c3dd4c0f user: serhiy.storchaka
18:54
Fix the C stack check of the regexp engine [7d47ba7d94] under AddressSanitizer: with its fake stack ... closed check-in: 5abb653b5d user: serhiy.storchaka tags: regexp-stack-check-asan
2026-11-01
16:57 • Closed ticket [7d47ba7d94]: Stack overruns in regexp code plus 4 other chang... artifact: 55c20fc863 user: dkf
2026-10-28
13:53 • Ticket [7d47ba7d94]: 3 changes artifact: 21e00ce766 user: jan.nijtmans
13:51
[7d47ba7d94] follow-up: on musl: TclpGetCStackLimit() returned NULL check-in: e67bd0fb30 user: jan.nijtmans tags: trunk, main
11:04 • Ticket [7d47ba7d94] Stack overruns in regexp code status still Pending with ... artifact: dcd2721495 user: serhiy.storchaka
11:03
Fix [7d47ba7d94] on musl: TclpGetCStackLimit() returned NULL on Linux without glibc, so the regexp e... closed check-in: 0b7238035e user: serhiy.storchaka tags: musl-stack-limit
2026-10-19
21:08 • Pending ticket [7d47ba7d94]: Stack overruns in regexp code plus 5 other chan... artifact: 899feddc87 user: jan.nijtmans
21:00
Fix [7d47ba7d94]: the regexp engine could overflow the C stack on deeply nested REs check-in: 4a966b9df4 user: jan.nijtmans tags: trunk, main
2026-10-16
12:15
Fix [7d47ba7d94]: the regexp engine could overflow the C stack on deeply nested REs. Rebase to trunk closed check-in: 3de02ad5e8 user: jan.nijtmans tags: regexp-stack-depth
2026-10-11
10:09 • Ticket [1905562fff] test reg-33.14 gets pointer smash status still Open with... artifact: 22fe20aef0 user: serhiy.storchaka
10:09 • Ticket [7d47ba7d94] Stack overruns in regexp code status still Open with 3 o... artifact: 3ea17d5f13 user: serhiy.storchaka
2026-10-10
20:48 • Ticket [7d47ba7d94]: 4 changes artifact: a1745c694b user: serhiy.storchaka
20:46
Fix [7d47ba7d94]: the regexp engine could overflow the C stack on deeply nested REs. Implement STACK... check-in: ef6503421f user: serhiy.storchaka tags: regexp-stack-depth
2015-10-21
17:04 • Ticket [7d47ba7d94] Stack overruns in regexp code status still Open with 3 o... artifact: 3e8a7045f3 user: tgl
14:20 • Ticket [7d47ba7d94]: 3 changes artifact: 7b3e61535a user: dgp
2015-10-19
15:35 • Ticket [7d47ba7d94]: 3 changes artifact: 1756e75034 user: dgp
2015-10-17
04:18 • Ticket [7d47ba7d94]: 3 changes artifact: 041721364b user: tgl
03:38 • New ticket [7d47ba7d94]. artifact: 31993579eb user: tgl

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-18 18:32:47
Status: Closed Closed by: serhiy.storchaka
Resolution: Fixed Closed on: 2026-11-18 18:32:47
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.


jan.nijtmans added on 2026-11-18 16:05:12:

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

Well, I was right about this reluctancy: two follow-up commits were needed to make it fully right in various situations. But now the code has been on trunk some time, without further indications of any trouble, it's time to backport.

So, backported now to core-9-0-branch. Serhiy, if you want to backport further to 8.6, please go ahead! +1. This would be nice for Tcl 9.8.19.


jan.nijtmans added on 2026-11-18 16:06:02:

> This would be nice for Tcl 9.8.19

That should have been Tcl 8.6.19


serhiy.storchaka added on 2026-11-18 18:27:58:

Backported to core-8-6-branch: [e720024d74]. 8.6 has no TCL_NOINLINE in tcl.h, so regguts.h defines it locally.