| <html> |
| <head> |
| <title>pcre2stack specification</title> |
| </head> |
| <body bgcolor="#FFFFFF" text="#00005A" link="#0066FF" alink="#3399FF" vlink="#2222BB"> |
| <h1>pcre2stack man page</h1> |
| <p> |
| Return to the <a href="index.html">PCRE2 index page</a>. |
| </p> |
| <p> |
| This page is part of the PCRE2 HTML documentation. It was generated |
| automatically from the original man page. If there is any nonsense in it, |
| please consult the man page, in case the conversion went wrong. |
| <br> |
| <br><b> |
| PCRE2 DISCUSSION OF STACK USAGE |
| </b><br> |
| <P> |
| When you call <b>pcre2_match()</b>, it makes use of an internal function called |
| <b>match()</b>. This calls itself recursively at branch points in the pattern, |
| in order to remember the state of the match so that it can back up and try a |
| different alternative after a failure. As matching proceeds deeper and deeper |
| into the tree of possibilities, the recursion depth increases. The |
| <b>match()</b> function is also called in other circumstances, for example, |
| whenever a parenthesized sub-pattern is entered, and in certain cases of |
| repetition. |
| </P> |
| <P> |
| Not all calls of <b>match()</b> increase the recursion depth; for an item such |
| as a* it may be called several times at the same level, after matching |
| different numbers of a's. Furthermore, in a number of cases where the result of |
| the recursive call would immediately be passed back as the result of the |
| current call (a "tail recursion"), the function is just restarted instead. |
| </P> |
| <P> |
| Each time the internal <b>match()</b> function is called recursively, it uses |
| memory from the process stack. For certain kinds of pattern and data, very |
| large amounts of stack may be needed, despite the recognition of "tail |
| recursion". Note that if PCRE2 is compiled with the -fsanitize=address option |
| of the GCC compiler, the stack requirements are greatly increased. |
| </P> |
| <P> |
| The above comments apply when <b>pcre2_match()</b> is run in its normal |
| interpretive manner. If the compiled pattern was processed by |
| <b>pcre2_jit_compile()</b>, and just-in-time compiling was successful, and the |
| options passed to <b>pcre2_match()</b> were not incompatible, the matching |
| process uses the JIT-compiled code instead of the <b>match()</b> function. In |
| this case, the memory requirements are handled entirely differently. See the |
| <a href="pcre2jit.html"><b>pcre2jit</b></a> |
| documentation for details. |
| </P> |
| <P> |
| The <b>pcre2_dfa_match()</b> function operates in a different way to |
| <b>pcre2_match()</b>, and uses recursion only when there is a regular expression |
| recursion or subroutine call in the pattern. This includes the processing of |
| assertion and "once-only" subpatterns, which are handled like subroutine calls. |
| Normally, these are never very deep, and the limit on the complexity of |
| <b>pcre2_dfa_match()</b> is controlled by the amount of workspace it is given. |
| However, it is possible to write patterns with runaway infinite recursions; |
| such patterns will cause <b>pcre2_dfa_match()</b> to run out of stack. At |
| present, there is no protection against this. |
| </P> |
| <P> |
| The comments that follow do NOT apply to <b>pcre2_dfa_match()</b>; they are |
| relevant only for <b>pcre2_match()</b> without the JIT optimization. |
| </P> |
| <br><b> |
| Reducing <b>pcre2_match()</b>'s stack usage |
| </b><br> |
| <P> |
| You can often reduce the amount of recursion, and therefore the |
| amount of stack used, by modifying the pattern that is being matched. Consider, |
| for example, this pattern: |
| <pre> |
| ([^<]|<(?!inet))+ |
| </pre> |
| It matches from wherever it starts until it encounters "<inet" or the end of |
| the data, and is the kind of pattern that might be used when processing an XML |
| file. Each iteration of the outer parentheses matches either one character that |
| is not "<" or a "<" that is not followed by "inet". However, each time a |
| parenthesis is processed, a recursion occurs, so this formulation uses a stack |
| frame for each matched character. For a long string, a lot of stack is |
| required. Consider now this rewritten pattern, which matches exactly the same |
| strings: |
| <pre> |
| ([^<]++|<(?!inet))+ |
| </pre> |
| This uses very much less stack, because runs of characters that do not contain |
| "<" are "swallowed" in one item inside the parentheses. Recursion happens only |
| when a "<" character that is not followed by "inet" is encountered (and we |
| assume this is relatively rare). A possessive quantifier is used to stop any |
| backtracking into the runs of non-"<" characters, but that is not related to |
| stack usage. |
| </P> |
| <P> |
| This example shows that one way of avoiding stack problems when matching long |
| subject strings is to write repeated parenthesized subpatterns to match more |
| than one character whenever possible. |
| </P> |
| <br><b> |
| Compiling PCRE2 to use heap instead of stack for <b>pcre2_match()</b> |
| </b><br> |
| <P> |
| In environments where stack memory is constrained, you might want to compile |
| PCRE2 to use heap memory instead of stack for remembering back-up points when |
| <b>pcre2_match()</b> is running. This makes it run more slowly, however. Details |
| of how to do this are given in the |
| <a href="pcre2build.html"><b>pcre2build</b></a> |
| documentation. When built in this way, instead of using the stack, PCRE2 |
| gets memory for remembering backup points from the heap. By default, the memory |
| is obtained by calling the system <b>malloc()</b> function, but you can arrange |
| to supply your own memory management function. For details, see the section |
| entitled |
| <a href="pcre2api.html#matchcontext">"The match context"</a> |
| in the |
| <a href="pcre2api.html"><b>pcre2api</b></a> |
| documentation. Since the block sizes are always the same, it may be possible to |
| implement customized a memory handler that is more efficient than the standard |
| function. The memory blocks obtained for this purpose are retained and re-used |
| if possible while <b>pcre2_match()</b> is running. They are all freed just |
| before it exits. |
| </P> |
| <br><b> |
| Limiting <b>pcre2_match()</b>'s stack usage |
| </b><br> |
| <P> |
| You can set limits on the number of times the internal <b>match()</b> function |
| is called, both in total and recursively. If a limit is exceeded, |
| <b>pcre2_match()</b> returns an error code. Setting suitable limits should |
| prevent it from running out of stack. The default values of the limits are very |
| large, and unlikely ever to operate. They can be changed when PCRE2 is built, |
| and they can also be set when <b>pcre2_match()</b> is called. For details of |
| these interfaces, see the |
| <a href="pcre2build.html"><b>pcre2build</b></a> |
| documentation and the section entitled |
| <a href="pcre2api.html#matchcontext">"The match context"</a> |
| in the |
| <a href="pcre2api.html"><b>pcre2api</b></a> |
| documentation. |
| </P> |
| <P> |
| As a very rough rule of thumb, you should reckon on about 500 bytes per |
| recursion. Thus, if you want to limit your stack usage to 8Mb, you should set |
| the limit at 16000 recursions. A 64Mb stack, on the other hand, can support |
| around 128000 recursions. |
| </P> |
| <P> |
| The <b>pcre2test</b> test program has a modifier called "find_limits" which, if |
| applied to a subject line, causes it to find the smallest limits that allow a a |
| pattern to match. This is done by calling <b>pcre2_match()</b> repeatedly with |
| different limits. |
| </P> |
| <br><b> |
| Changing stack size in Unix-like systems |
| </b><br> |
| <P> |
| In Unix-like environments, there is not often a problem with the stack unless |
| very long strings are involved, though the default limit on stack size varies |
| from system to system. Values from 8Mb to 64Mb are common. You can find your |
| default limit by running the command: |
| <pre> |
| ulimit -s |
| </pre> |
| Unfortunately, the effect of running out of stack is often SIGSEGV, though |
| sometimes a more explicit error message is given. You can normally increase the |
| limit on stack size by code such as this: |
| <pre> |
| struct rlimit rlim; |
| getrlimit(RLIMIT_STACK, &rlim); |
| rlim.rlim_cur = 100*1024*1024; |
| setrlimit(RLIMIT_STACK, &rlim); |
| </pre> |
| This reads the current limits (soft and hard) using <b>getrlimit()</b>, then |
| attempts to increase the soft limit to 100Mb using <b>setrlimit()</b>. You must |
| do this before calling <b>pcre2_match()</b>. |
| </P> |
| <br><b> |
| Changing stack size in Mac OS X |
| </b><br> |
| <P> |
| Using <b>setrlimit()</b>, as described above, should also work on Mac OS X. It |
| is also possible to set a stack size when linking a program. There is a |
| discussion about stack sizes in Mac OS X at this web site: |
| <a href="http://developer.apple.com/qa/qa2005/qa1419.html">http://developer.apple.com/qa/qa2005/qa1419.html.</a> |
| </P> |
| <br><b> |
| AUTHOR |
| </b><br> |
| <P> |
| Philip Hazel |
| <br> |
| University Computing Service |
| <br> |
| Cambridge, England. |
| <br> |
| </P> |
| <br><b> |
| REVISION |
| </b><br> |
| <P> |
| Last updated: 21 November 2014 |
| <br> |
| Copyright © 1997-2014 University of Cambridge. |
| <br> |
| <p> |
| Return to the <a href="index.html">PCRE2 index page</a>. |
| </p> |