Tristan Matthews | 0461646 | 2013-11-14 16:09:34 -0500 | [diff] [blame] | 1 | .TH PCRESTACK 3 |
| 2 | .SH NAME |
| 3 | PCRE - Perl-compatible regular expressions |
| 4 | .SH "PCRE DISCUSSION OF STACK USAGE" |
| 5 | .rs |
| 6 | .sp |
| 7 | When you call \fBpcre_exec()\fP, it makes use of an internal function called |
| 8 | \fBmatch()\fP. This calls itself recursively at branch points in the pattern, |
| 9 | in order to remember the state of the match so that it can back up and try a |
| 10 | different alternative if the first one fails. As matching proceeds deeper and |
| 11 | deeper into the tree of possibilities, the recursion depth increases. The |
| 12 | \fBmatch()\fP function is also called in other circumstances, for example, |
| 13 | whenever a parenthesized sub-pattern is entered, and in certain cases of |
| 14 | repetition. |
| 15 | .P |
| 16 | Not all calls of \fBmatch()\fP increase the recursion depth; for an item such |
| 17 | as a* it may be called several times at the same level, after matching |
| 18 | different numbers of a's. Furthermore, in a number of cases where the result of |
| 19 | the recursive call would immediately be passed back as the result of the |
| 20 | current call (a "tail recursion"), the function is just restarted instead. |
| 21 | .P |
| 22 | The above comments apply when \fBpcre_exec()\fP is run in its normal |
| 23 | interpretive manner. If the pattern was studied with the |
| 24 | PCRE_STUDY_JIT_COMPILE option, and just-in-time compiling was successful, and |
| 25 | the options passed to \fBpcre_exec()\fP were not incompatible, the matching |
| 26 | process uses the JIT-compiled code instead of the \fBmatch()\fP function. In |
| 27 | this case, the memory requirements are handled entirely differently. See the |
| 28 | .\" HREF |
| 29 | \fBpcrejit\fP |
| 30 | .\" |
| 31 | documentation for details. |
| 32 | .P |
| 33 | The \fBpcre_dfa_exec()\fP 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 \fBpcre_dfa_exec()\fP 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 | \fBpcre_dfa_exec()\fP to run out of stack. At present, there is no protection |
| 41 | against this. |
| 42 | .P |
| 43 | The comments that follow do NOT apply to \fBpcre_dfa_exec()\fP; they are |
| 44 | relevant only for \fBpcre_exec()\fP without the JIT optimization. |
| 45 | . |
| 46 | . |
| 47 | .SS "Reducing \fBpcre_exec()\fP's stack usage" |
| 48 | .rs |
| 49 | .sp |
| 50 | Each time that \fBmatch()\fP is actually called recursively, it uses memory |
| 51 | from the process stack. For certain kinds of pattern and data, very large |
| 52 | amounts of stack may be needed, despite the recognition of "tail recursion". |
| 53 | You can often reduce the amount of recursion, and therefore the amount of stack |
| 54 | used, by modifying the pattern that is being matched. Consider, for example, |
| 55 | this pattern: |
| 56 | .sp |
| 57 | ([^<]|<(?!inet))+ |
| 58 | .sp |
| 59 | It matches from wherever it starts until it encounters "<inet" or the end of |
| 60 | the data, and is the kind of pattern that might be used when processing an XML |
| 61 | file. Each iteration of the outer parentheses matches either one character that |
| 62 | is not "<" or a "<" that is not followed by "inet". However, each time a |
| 63 | parenthesis is processed, a recursion occurs, so this formulation uses a stack |
| 64 | frame for each matched character. For a long string, a lot of stack is |
| 65 | required. Consider now this rewritten pattern, which matches exactly the same |
| 66 | strings: |
| 67 | .sp |
| 68 | ([^<]++|<(?!inet))+ |
| 69 | .sp |
| 70 | This uses very much less stack, because runs of characters that do not contain |
| 71 | "<" are "swallowed" in one item inside the parentheses. Recursion happens only |
| 72 | when a "<" character that is not followed by "inet" is encountered (and we |
| 73 | assume this is relatively rare). A possessive quantifier is used to stop any |
| 74 | backtracking into the runs of non-"<" characters, but that is not related to |
| 75 | stack usage. |
| 76 | .P |
| 77 | This example shows that one way of avoiding stack problems when matching long |
| 78 | subject strings is to write repeated parenthesized subpatterns to match more |
| 79 | than one character whenever possible. |
| 80 | . |
| 81 | . |
| 82 | .SS "Compiling PCRE to use heap instead of stack for \fBpcre_exec()\fP" |
| 83 | .rs |
| 84 | .sp |
| 85 | In environments where stack memory is constrained, you might want to compile |
| 86 | PCRE to use heap memory instead of stack for remembering back-up points when |
| 87 | \fBpcre_exec()\fP is running. This makes it run a lot more slowly, however. |
| 88 | Details of how to do this are given in the |
| 89 | .\" HREF |
| 90 | \fBpcrebuild\fP |
| 91 | .\" |
| 92 | documentation. When built in this way, instead of using the stack, PCRE obtains |
| 93 | and frees memory by calling the functions that are pointed to by the |
| 94 | \fBpcre_stack_malloc\fP and \fBpcre_stack_free\fP variables. By default, these |
| 95 | point to \fBmalloc()\fP and \fBfree()\fP, 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. |
| 99 | . |
| 100 | . |
| 101 | .SS "Limiting \fBpcre_exec()\fP's stack usage" |
| 102 | .rs |
| 103 | .sp |
| 104 | You can set limits on the number of times that \fBmatch()\fP is called, both in |
| 105 | total and recursively. If a limit is exceeded, \fBpcre_exec()\fP returns an |
| 106 | error code. Setting suitable limits should prevent it from running out of |
| 107 | stack. The default values of the limits are very large, and unlikely ever to |
| 108 | operate. They can be changed when PCRE is built, and they can also be set when |
| 109 | \fBpcre_exec()\fP is called. For details of these interfaces, see the |
| 110 | .\" HREF |
| 111 | \fBpcrebuild\fP |
| 112 | .\" |
| 113 | documentation and the |
| 114 | .\" HTML <a href="pcreapi.html#extradata"> |
| 115 | .\" </a> |
| 116 | section on extra data for \fBpcre_exec()\fP |
| 117 | .\" |
| 118 | in the |
| 119 | .\" HREF |
| 120 | \fBpcreapi\fP |
| 121 | .\" |
| 122 | documentation. |
| 123 | .P |
| 124 | As a very rough rule of thumb, you should reckon on about 500 bytes per |
| 125 | recursion. Thus, if you want to limit your stack usage to 8Mb, you |
| 126 | should set the limit at 16000 recursions. A 64Mb stack, on the other hand, can |
| 127 | support around 128000 recursions. |
| 128 | .P |
| 129 | In Unix-like environments, the \fBpcretest\fP test program has a command line |
| 130 | option (\fB-S\fP) that can be used to increase the size of its stack. As long |
| 131 | as the stack is large enough, another option (\fB-M\fP) can be used to find the |
| 132 | smallest limits that allow a particular pattern to match a given subject |
| 133 | string. This is done by calling \fBpcre_exec()\fP repeatedly with different |
| 134 | limits. |
| 135 | . |
| 136 | . |
| 137 | .SS "Changing stack size in Unix-like systems" |
| 138 | .rs |
| 139 | .sp |
| 140 | In Unix-like environments, there is not often a problem with the stack unless |
| 141 | very long strings are involved, though the default limit on stack size varies |
| 142 | from system to system. Values from 8Mb to 64Mb are common. You can find your |
| 143 | default limit by running the command: |
| 144 | .sp |
| 145 | ulimit -s |
| 146 | .sp |
| 147 | Unfortunately, the effect of running out of stack is often SIGSEGV, though |
| 148 | sometimes a more explicit error message is given. You can normally increase the |
| 149 | limit on stack size by code such as this: |
| 150 | .sp |
| 151 | struct rlimit rlim; |
| 152 | getrlimit(RLIMIT_STACK, &rlim); |
| 153 | rlim.rlim_cur = 100*1024*1024; |
| 154 | setrlimit(RLIMIT_STACK, &rlim); |
| 155 | .sp |
| 156 | This reads the current limits (soft and hard) using \fBgetrlimit()\fP, then |
| 157 | attempts to increase the soft limit to 100Mb using \fBsetrlimit()\fP. You must |
| 158 | do this before calling \fBpcre_exec()\fP. |
| 159 | . |
| 160 | . |
| 161 | .SS "Changing stack size in Mac OS X" |
| 162 | .rs |
| 163 | .sp |
| 164 | Using \fBsetrlimit()\fP, as described above, should also work on Mac OS X. It |
| 165 | is also possible to set a stack size when linking a program. There is a |
| 166 | discussion about stack sizes in Mac OS X at this web site: |
| 167 | .\" HTML <a href="http://developer.apple.com/qa/qa2005/qa1419.html"> |
| 168 | .\" </a> |
| 169 | http://developer.apple.com/qa/qa2005/qa1419.html. |
| 170 | .\" |
| 171 | . |
| 172 | . |
| 173 | .SH AUTHOR |
| 174 | .rs |
| 175 | .sp |
| 176 | .nf |
| 177 | Philip Hazel |
| 178 | University Computing Service |
| 179 | Cambridge CB2 3QH, England. |
| 180 | .fi |
| 181 | . |
| 182 | . |
| 183 | .SH REVISION |
| 184 | .rs |
| 185 | .sp |
| 186 | .nf |
| 187 | Last updated: 26 August 2011 |
| 188 | Copyright (c) 1997-2011 University of Cambridge. |
| 189 | .fi |