Tristan Matthews | 0461646 | 2013-11-14 16:09:34 -0500 | [diff] [blame] | 1 | <html> |
| 2 | <head> |
| 3 | <title>pcrestack specification</title> |
| 4 | </head> |
| 5 | <body bgcolor="#FFFFFF" text="#00005A" link="#0066FF" alink="#3399FF" vlink="#2222BB"> |
| 6 | <h1>pcrestack man page</h1> |
| 7 | <p> |
| 8 | Return to the <a href="index.html">PCRE index page</a>. |
| 9 | </p> |
| 10 | <p> |
| 11 | This page is part of the PCRE HTML documentation. It was generated automatically |
| 12 | from the original man page. If there is any nonsense in it, please consult the |
| 13 | man page, in case the conversion went wrong. |
| 14 | <br> |
| 15 | <br><b> |
| 16 | PCRE DISCUSSION OF STACK USAGE |
| 17 | </b><br> |
| 18 | <P> |
| 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. 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 | repetition. |
| 27 | </P> |
| 28 | <P> |
| 29 | Not all calls of <b>match()</b> increase the recursion depth; for an item such |
| 30 | as a* it may be called several times at the same level, after matching |
| 31 | different numbers of a's. Furthermore, in a number of cases where the result of |
| 32 | the recursive call would immediately be passed back as the result of the |
| 33 | current call (a "tail recursion"), the function is just restarted instead. |
| 34 | </P> |
| 35 | <P> |
| 36 | The above comments apply when <b>pcre_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_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. |
| 44 | </P> |
| 45 | <P> |
| 46 | The <b>pcre_dfa_exec()</b> function operates in an entirely different way, and |
| 47 | uses recursion only when there is a regular expression recursion or subroutine |
| 48 | call in the pattern. This includes the processing of assertion and "once-only" |
| 49 | subpatterns, which are handled like subroutine calls. Normally, these are never |
| 50 | very deep, and the limit on the complexity of <b>pcre_dfa_exec()</b> is |
| 51 | controlled by the amount of workspace it is given. However, it is possible to |
| 52 | write patterns with runaway infinite recursions; such patterns will cause |
| 53 | <b>pcre_dfa_exec()</b> to run out of stack. At present, there is no protection |
| 54 | against this. |
| 55 | </P> |
| 56 | <P> |
| 57 | The comments that follow do NOT apply to <b>pcre_dfa_exec()</b>; they are |
| 58 | relevant only for <b>pcre_exec()</b> without the JIT optimization. |
| 59 | </P> |
| 60 | <br><b> |
| 61 | Reducing <b>pcre_exec()</b>'s stack usage |
| 62 | </b><br> |
| 63 | <P> |
| 64 | Each time that <b>match()</b> is actually called recursively, it uses memory |
| 65 | from the process stack. For certain kinds of pattern and data, very large |
| 66 | amounts of stack may be needed, despite the recognition of "tail recursion". |
| 67 | You can often reduce the amount of recursion, and therefore the amount of stack |
| 68 | used, by modifying the pattern that is being matched. Consider, for example, |
| 69 | this pattern: |
| 70 | <pre> |
| 71 | ([^<]|<(?!inet))+ |
| 72 | </pre> |
| 73 | It matches from wherever it starts until it encounters "<inet" or the end of |
| 74 | the data, and is the kind of pattern that might be used when processing an XML |
| 75 | file. Each iteration of the outer parentheses matches either one character that |
| 76 | is not "<" or a "<" that is not followed by "inet". However, each time a |
| 77 | parenthesis is processed, a recursion occurs, so this formulation uses a stack |
| 78 | frame for each matched character. For a long string, a lot of stack is |
| 79 | required. Consider now this rewritten pattern, which matches exactly the same |
| 80 | strings: |
| 81 | <pre> |
| 82 | ([^<]++|<(?!inet))+ |
| 83 | </pre> |
| 84 | This uses very much less stack, because runs of characters that do not contain |
| 85 | "<" are "swallowed" in one item inside the parentheses. Recursion happens only |
| 86 | when a "<" character that is not followed by "inet" is encountered (and we |
| 87 | assume this is relatively rare). A possessive quantifier is used to stop any |
| 88 | backtracking into the runs of non-"<" characters, but that is not related to |
| 89 | stack usage. |
| 90 | </P> |
| 91 | <P> |
| 92 | This example shows that one way of avoiding stack problems when matching long |
| 93 | subject strings is to write repeated parenthesized subpatterns to match more |
| 94 | than one character whenever possible. |
| 95 | </P> |
| 96 | <br><b> |
| 97 | Compiling PCRE to use heap instead of stack for <b>pcre_exec()</b> |
| 98 | </b><br> |
| 99 | <P> |
| 100 | In environments where stack memory is constrained, you might want to compile |
| 101 | PCRE to use heap memory instead of stack for remembering back-up points when |
| 102 | <b>pcre_exec()</b> is running. This makes it run a lot more slowly, however. |
| 103 | Details of how to do this are given in the |
| 104 | <a href="pcrebuild.html"><b>pcrebuild</b></a> |
| 105 | documentation. When built in this way, instead of using the stack, PCRE obtains |
| 106 | and frees memory by calling the functions that are pointed to by the |
| 107 | <b>pcre_stack_malloc</b> and <b>pcre_stack_free</b> variables. By default, these |
| 108 | point to <b>malloc()</b> and <b>free()</b>, but you can replace the pointers to |
| 109 | cause PCRE to use your own functions. Since the block sizes are always the |
| 110 | same, and are always freed in reverse order, it may be possible to implement |
| 111 | customized memory handlers that are more efficient than the standard functions. |
| 112 | </P> |
| 113 | <br><b> |
| 114 | Limiting <b>pcre_exec()</b>'s stack usage |
| 115 | </b><br> |
| 116 | <P> |
| 117 | You can set limits on the number of times that <b>match()</b> is called, both in |
| 118 | total and recursively. If a limit is exceeded, <b>pcre_exec()</b> returns an |
| 119 | error code. Setting suitable limits should prevent it from running out of |
| 120 | stack. The default values of the limits are very large, and unlikely ever to |
| 121 | operate. They can be changed when PCRE is built, and they can also be set when |
| 122 | <b>pcre_exec()</b> is called. For details of these interfaces, see the |
| 123 | <a href="pcrebuild.html"><b>pcrebuild</b></a> |
| 124 | documentation and the |
| 125 | <a href="pcreapi.html#extradata">section on extra data for <b>pcre_exec()</b></a> |
| 126 | in the |
| 127 | <a href="pcreapi.html"><b>pcreapi</b></a> |
| 128 | documentation. |
| 129 | </P> |
| 130 | <P> |
| 131 | As a very rough rule of thumb, you should reckon on about 500 bytes per |
| 132 | recursion. Thus, if you want to limit your stack usage to 8Mb, you |
| 133 | should set the limit at 16000 recursions. A 64Mb stack, on the other hand, can |
| 134 | support around 128000 recursions. |
| 135 | </P> |
| 136 | <P> |
| 137 | In Unix-like environments, the <b>pcretest</b> test program has a command line |
| 138 | option (<b>-S</b>) that can be used to increase the size of its stack. As long |
| 139 | as the stack is large enough, another option (<b>-M</b>) can be used to find the |
| 140 | smallest limits that allow a particular pattern to match a given subject |
| 141 | string. This is done by calling <b>pcre_exec()</b> repeatedly with different |
| 142 | limits. |
| 143 | </P> |
| 144 | <br><b> |
| 145 | Changing stack size in Unix-like systems |
| 146 | </b><br> |
| 147 | <P> |
| 148 | In Unix-like environments, there is not often a problem with the stack unless |
| 149 | very long strings are involved, though the default limit on stack size varies |
| 150 | from system to system. Values from 8Mb to 64Mb are common. You can find your |
| 151 | default limit by running the command: |
| 152 | <pre> |
| 153 | ulimit -s |
| 154 | </pre> |
| 155 | Unfortunately, the effect of running out of stack is often SIGSEGV, though |
| 156 | sometimes a more explicit error message is given. You can normally increase the |
| 157 | limit on stack size by code such as this: |
| 158 | <pre> |
| 159 | struct rlimit rlim; |
| 160 | getrlimit(RLIMIT_STACK, &rlim); |
| 161 | rlim.rlim_cur = 100*1024*1024; |
| 162 | setrlimit(RLIMIT_STACK, &rlim); |
| 163 | </pre> |
| 164 | This reads the current limits (soft and hard) using <b>getrlimit()</b>, then |
| 165 | attempts to increase the soft limit to 100Mb using <b>setrlimit()</b>. You must |
| 166 | do this before calling <b>pcre_exec()</b>. |
| 167 | </P> |
| 168 | <br><b> |
| 169 | Changing stack size in Mac OS X |
| 170 | </b><br> |
| 171 | <P> |
| 172 | Using <b>setrlimit()</b>, as described above, should also work on Mac OS X. It |
| 173 | is also possible to set a stack size when linking a program. There is a |
| 174 | discussion about stack sizes in Mac OS X at this web site: |
| 175 | <a href="http://developer.apple.com/qa/qa2005/qa1419.html">http://developer.apple.com/qa/qa2005/qa1419.html.</a> |
| 176 | </P> |
| 177 | <br><b> |
| 178 | AUTHOR |
| 179 | </b><br> |
| 180 | <P> |
| 181 | Philip Hazel |
| 182 | <br> |
| 183 | University Computing Service |
| 184 | <br> |
| 185 | Cambridge CB2 3QH, England. |
| 186 | <br> |
| 187 | </P> |
| 188 | <br><b> |
| 189 | REVISION |
| 190 | </b><br> |
| 191 | <P> |
| 192 | Last updated: 26 August 2011 |
| 193 | <br> |
| 194 | Copyright © 1997-2011 University of Cambridge. |
| 195 | <br> |
| 196 | <p> |
| 197 | Return to the <a href="index.html">PCRE index page</a>. |
| 198 | </p> |