Tcl Source Code

View Ticket
Login
Ticket UUID: 1905562
Title: test reg-33.14 gets pointer smash
Type: Bug Created on: 2008-03-02 03:57:14
Submitter: kennykb Assigned to: dgp
Subsystem: 43. Regexp Severity: Minor
Priority: 5 Medium Last modified: 2026-10-11 10:09:04
Status: Open Closed by: nobody
Resolution: None Closed on: 2008-07-16 02:20:19
Version: 8.6.18, 9.0.5, 9.1.0
Description:
Running a self-built TCL from today's HEAD, I get a segmentation violation at reg-33.14.  The build was with
msys and MSVC 2k5 with

CC=cl path/to/win/configure --enable-symbols --enable-threads

More details when I've got 'em.
User Comments:
kennykb added on 2008-03-02 11:23:07:
Logged In: YES 
user_id=99768
Originator: YES

The crash appears to be related to a stack overflow, heap corruption, or memory exhaustion in the duptraverse() function in regc_nfa.c.  Running without the MSVC debugger, there is a simple pointer smash.  Launching the executable under the debugger, and running from there, yields instead a call to Tcl_Panic with "unable to allocate 368 bytes" at line 1032.  The recursive nest of calls to duptraverse is beyond MSVC's ability to traverse.

dgp added on 2008-03-12 02:09:00:
Logged In: YES 
user_id=80530
Originator: NO


any progress on this?

cleverly added on 2008-03-15 02:26:14:
Logged In: YES 
user_id=22080
Originator: NO

As a point of reference, with 8.5.2rc1 reg-33.14 also segfaults on OpenBSD 4.2 (sparc64) in a non-thread enabled build (gcc 3.3.5).

dgp added on 2008-03-19 00:27:18:
Logged In: YES 
user_id=80530
Originator: NO


Reproduced on sparc Solaris 9 with a
--enable-symbols --enable-64bit configuration.

dgp added on 2008-03-19 04:07:24:
Logged In: YES 
user_id=80530
Originator: NO


Going back a few releases...

$ make runtest
...
% info patch
8.4.15
% regexp {(x{200}){200}$y} x
Segmentation Fault


The test that triggers the crash
is new.  The bugginess that permits
the crash is apparently not.

dgp added on 2008-03-19 04:36:50:
Logged In: YES 
user_id=80530
Originator: NO


This is looking like C stack overflow.

dgp added on 2008-03-19 04:57:29:
Logged In: YES 
user_id=80530
Originator: NO


On a platform where test reg-33.14
does not crash, I see:

% regexp {(x{222}){222}$y} x
couldn't compile regular expression pattern: nfa has too many states

So if things continue to get bigger,
this error message appears to protect against
the possibility of stack overflow everywhere.
It's assumed there's enough stack to cover traversal
of all nfa's with states below the limit.

Points to a possible fix of imposing a smaller
limit on these stack-limited platforms?

Alternative would be a significant rewrite of
the RE engine guts to not do so much recursive
stuff.

Shorter term, we can either drop the demands
of test reg-33.14 to avoid confronting the issue
in the test suite, or simply mark it as a
nonportable test.

kennykb added on 2008-03-19 19:51:53:
Logged In: YES 
user_id=99768
Originator: YES

Reassigning to someone who appears to have a clue what's going on.

dkf added on 2008-03-19 20:41:10:
Logged In: YES 
user_id=79902
Originator: NO

Suggested workaround: use a bigger stack. Meanwhile, I've marked the test nonPortable.

Maybe the correct fix is to use stack protection voodoo like Tcl does/did. Assigning to Miguel for comment.

dgp added on 2008-03-19 21:07:40:
Logged In: YES 
user_id=80530
Originator: NO


Miguel's efforts at stack protection are
appreciated, but they don't exactly have
a flawless track record.

A more certain "real fix" for this issue
would be to follow the expr parser rewrite
example and replace all these recursive
routines with non-recursive versions.

dkf added on 2008-03-19 21:46:03:
Logged In: YES 
user_id=79902
Originator: NO

Hmm, it's doing tree-traversal and it needs to actions both before and after the recursive step. That's the case that's hard to convert.

msofer added on 2008-06-28 20:38:02:
Logged In: YES 
user_id=148712
Originator: NO

C-stack protection against too-deep Tcl recursion? I'd rather get rid of it. And I will, during 8.6a? as part of NRE. 

I imagine we could keep parts of it for regexps, but I agree with dgp (and jenglish, and many others): C-stack checking magic is a nasty hack, non-portable and half-working at best.

dkf added on 2008-07-01 21:31:11:
Logged In: YES 
user_id=79902
Originator: NO

Added a focussed limit. duptraverse() can now only go 500 deep, and that seems to be enough for everything in the test suite that's normally run. Let me know if that's not enough (or too much).

sf-robot added on 2008-07-16 09:20:19:
Logged In: YES 
user_id=1312539
Originator: NO

This Tracker item was closed automatically by the system. It was
previously set to a Pending status, and the original submitter
did not respond within 14 days (the time period specified by
the administrator of this Tracker).

dgp added on 2013-02-07 00:52:58:
See 3603557 for report from someone for whom
that was not enough. :)

dgp added on 2013-04-01 23:20:48:
Another person needing broader limits has reported
to TCLCORE.  Re-opening so that a different solution
can be considered.

dgp added on 2013-08-01 17:19:51:
Ticket [8d2c0da36d] is a third report on this.
Time to fix it.

dgp added on 2013-08-01 17:38:48:
The current trunk already has the limit
raise from 500 (in 8.6.0 release) to 700.

As luck would have it, the new stress test
derived from DejaGnu requires a value of 701,
at least on my system.

dgp added on 2013-08-01 17:48:05:
Another less simplified test:

https://git.lysator.liu.se/lyskom-server/lyskom-server/blobs/raw/master/src/server/testsuite/dejagnu.0/01-long-regexp.exp

dgp added on 2013-08-01 17:50:58:
Empirically, on my system, that one needs a limit of 817.

dgp added on 2013-08-01 19:10:51:
At the other end, on a Solaris 10 system where 
I can produce the stack overflow crashes, I need
a DUPTRAVERSE_MAX_DEPTH value of no more than 32639
to provide protection.

Pending further input from other platforms, I'd
suggest a better compromise limit value to permit
ridiculous regexps but still provide the stack
overflow protection would be a value of 15000.

dgp added on 2013-08-01 19:25:08:
Committed that value to trunk, along
with a test to keep the latest in-the-wild
regexp working.

Subject to further revision if we get even
longer regexps reported, or if we find platforms
where the new limit fails to protect against
stack smashes.

dgp added on 2013-08-30 17:04:51:
See Ticket 267b7e2334 for another complaint
on this subject (possibly out of date) but
with a tangible suggestion how to implement
a real solution rather than on ongoing tuning
chase.

dkf added on 2013-09-09 09:52:24:

Assigning to someone who's more likely to work on this than me.


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

The crash is gone since the DUPTRAVERSE_MAX_DEPTH limit, but the error is still the misleading "out of memory" (see also [267b7e2334]), and reg-33.14 is still marked nonPortable.

Proposed fix in branch regexp-stack-depth (for [7d47ba7d94]): the recursive functions now check the real stack depth, so such REs fail with "regular expression is too complex" on any stack size, and reg-33.14 is a normal test again.