16
16
PCRE DISCUSSION OF STACK USAGE
19
When you call <b>pcre_exec()</b>, it makes use of an internal function called
20
<b>match()</b>. This calls itself recursively at branch points in the pattern,
21
in order to remember the state of the match so that it can back up and try a
22
different alternative if the first one fails. As matching proceeds deeper and
23
deeper into the tree of possibilities, the recursion depth increases.
19
When you call <b>pcre[16]_exec()</b>, it makes use of an internal function
20
called <b>match()</b>. This calls itself recursively at branch points in the
21
pattern, in order to remember the state of the match so that it can back up and
22
try a different alternative if the first one fails. As matching proceeds deeper
23
and deeper into the tree of possibilities, the recursion depth increases. The
24
<b>match()</b> function is also called in other circumstances, for example,
25
whenever a parenthesized sub-pattern is entered, and in certain cases of
26
29
Not all calls of <b>match()</b> increase the recursion depth; for an item such
30
33
current call (a "tail recursion"), the function is just restarted instead.
33
The <b>pcre_dfa_exec()</b> function operates in an entirely different way, and
34
uses recursion only when there is a regular expression recursion or subroutine
35
call in the pattern. This includes the processing of assertion and "once-only"
36
subpatterns, which are handled like subroutine calls. Normally, these are never
37
very deep, and the limit on the complexity of <b>pcre_dfa_exec()</b> is
38
controlled by the amount of workspace it is given. However, it is possible to
39
write patterns with runaway infinite recursions; such patterns will cause
40
<b>pcre_dfa_exec()</b> to run out of stack. At present, there is no protection
44
The comments that follow do NOT apply to <b>pcre_dfa_exec()</b>; they are
45
relevant only for <b>pcre_exec()</b>.
36
The above comments apply when <b>pcre[16]_exec()</b> is run in its normal
37
interpretive manner. If the pattern was studied with the
38
PCRE_STUDY_JIT_COMPILE option, and just-in-time compiling was successful, and
39
the options passed to <b>pcre[16]_exec()</b> were not incompatible, the matching
40
process uses the JIT-compiled code instead of the <b>match()</b> function. In
41
this case, the memory requirements are handled entirely differently. See the
42
<a href="pcrejit.html"><b>pcrejit</b></a>
43
documentation for details.
46
The <b>pcre[16]_dfa_exec()</b> function operates in an entirely different way,
47
and uses recursion only when there is a regular expression recursion or
48
subroutine call in the pattern. This includes the processing of assertion and
49
"once-only" subpatterns, which are handled like subroutine calls. Normally,
50
these are never very deep, and the limit on the complexity of
51
<b>pcre[16]_dfa_exec()</b> is controlled by the amount of workspace it is given.
52
However, it is possible to write patterns with runaway infinite recursions;
53
such patterns will cause <b>pcre[16]_dfa_exec()</b> to run out of stack. At
54
present, there is no protection against this.
57
The comments that follow do NOT apply to <b>pcre[16]_dfa_exec()</b>; they are
58
relevant only for <b>pcre[16]_exec()</b> without the JIT optimization.
48
Reducing <b>pcre_exec()</b>'s stack usage
61
Reducing <b>pcre[16]_exec()</b>'s stack usage
51
64
Each time that <b>match()</b> is actually called recursively, it uses memory
81
94
than one character whenever possible.
84
Compiling PCRE to use heap instead of stack for <b>pcre_exec()</b>
97
Compiling PCRE to use heap instead of stack for <b>pcre[16]_exec()</b>
87
100
In environments where stack memory is constrained, you might want to compile
88
101
PCRE to use heap memory instead of stack for remembering back-up points when
89
<b>pcre_exec()</b> is running. This makes it run a lot more slowly, however.
102
<b>pcre[16]_exec()</b> is running. This makes it run a lot more slowly, however.
90
103
Details of how to do this are given in the
91
104
<a href="pcrebuild.html"><b>pcrebuild</b></a>
92
105
documentation. When built in this way, instead of using the stack, PCRE obtains
93
106
and frees memory by calling the functions that are pointed to by the
94
<b>pcre_stack_malloc</b> and <b>pcre_stack_free</b> variables. By default, these
95
point to <b>malloc()</b> and <b>free()</b>, but you can replace the pointers to
96
cause PCRE to use your own functions. Since the block sizes are always the
97
same, and are always freed in reverse order, it may be possible to implement
98
customized memory handlers that are more efficient than the standard functions.
107
<b>pcre[16]_stack_malloc</b> and <b>pcre[16]_stack_free</b> variables. By
108
default, these point to <b>malloc()</b> and <b>free()</b>, but you can replace
109
the pointers to cause PCRE to use your own functions. Since the block sizes are
110
always the same, and are always freed in reverse order, it may be possible to
111
implement customized memory handlers that are more efficient than the standard
101
Limiting <b>pcre_exec()</b>'s stack usage
115
Limiting <b>pcre[16]_exec()</b>'s stack usage
104
118
You can set limits on the number of times that <b>match()</b> is called, both in
105
total and recursively. If a limit is exceeded, <b>pcre_exec()</b> returns an
119
total and recursively. If a limit is exceeded, <b>pcre[16]_exec()</b> returns an
106
120
error code. Setting suitable limits should prevent it from running out of
107
121
stack. The default values of the limits are very large, and unlikely ever to
108
122
operate. They can be changed when PCRE is built, and they can also be set when
109
<b>pcre_exec()</b> is called. For details of these interfaces, see the
123
<b>pcre[16]_exec()</b> is called. For details of these interfaces, see the
110
124
<a href="pcrebuild.html"><b>pcrebuild</b></a>
111
125
documentation and the
112
<a href="pcreapi.html#extradata">section on extra data for <b>pcre_exec()</b></a>
126
<a href="pcreapi.html#extradata">section on extra data for <b>pcre[16]_exec()</b></a>
114
128
<a href="pcreapi.html"><b>pcreapi</b></a>
118
132
As a very rough rule of thumb, you should reckon on about 500 bytes per
119
recursion. Thus, if you want to limit your stack usage to 8Mb, you
120
should set the limit at 16000 recursions. A 64Mb stack, on the other hand, can
121
support around 128000 recursions.
133
recursion. Thus, if you want to limit your stack usage to 8Mb, you should set
134
the limit at 16000 recursions. A 64Mb stack, on the other hand, can support
135
around 128000 recursions.
124
138
In Unix-like environments, the <b>pcretest</b> test program has a command line
125
139
option (<b>-S</b>) that can be used to increase the size of its stack. As long
126
140
as the stack is large enough, another option (<b>-M</b>) can be used to find the
127
141
smallest limits that allow a particular pattern to match a given subject
128
string. This is done by calling <b>pcre_exec()</b> repeatedly with different
142
string. This is done by calling <b>pcre[16]_exec()</b> repeatedly with different
146
Obtaining an estimate of stack usage
149
The actual amount of stack used per recursion can vary quite a lot, depending
150
on the compiler that was used to build PCRE and the optimization or debugging
151
options that were set for it. The rule of thumb value of 500 bytes mentioned
152
above may be larger or smaller than what is actually needed. A better
153
approximation can be obtained by running this command:
157
The <b>-C</b> option causes <b>pcretest</b> to output information about the
158
options with which PCRE was compiled. When <b>-m</b> is also given (before
159
<b>-C</b>), information about stack use is given in a line like this:
161
Match recursion uses stack: approximate frame size = 640 bytes
163
The value is approximate because some recursions need a bit more (up to perhaps
167
If the above command is given when PCRE is compiled to use the heap instead of
168
the stack for recursion, the value that is output is the size of each block
169
that is obtained from the heap.
132
172
Changing stack size in Unix-like systems
added
removed
doc/html/pcrestack.html
