| 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. | ||||
