Return to pcrestack.3 CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / pcre / doc

8.33

    1: .TH PCRESTACK 3 "24 June 2012" "PCRE 8.30"
    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[16|32]_exec()\fP, it makes use of an internal function
    8: called \fBmatch()\fP. This calls itself recursively at branch points in the
    9: pattern, in order to remember the state of the match so that it can back up and
   10: try a different alternative if the first one fails. As matching proceeds deeper
   11: and 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[16|32]_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[16|32]_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[16|32]_dfa_exec()\fP function operates in an entirely different way,
   34: and uses recursion only when there is a regular expression recursion or
   35: subroutine call in the pattern. This includes the processing of assertion and
   36: "once-only" subpatterns, which are handled like subroutine calls. Normally,
   37: these are never very deep, and the limit on the complexity of
   38: \fBpcre[16|32]_dfa_exec()\fP is controlled by the amount of workspace it is given.
   39: However, it is possible to write patterns with runaway infinite recursions;
   40: such patterns will cause \fBpcre[16|32]_dfa_exec()\fP to run out of stack. At
   41: present, there is no protection against this.
   42: .P
   43: The comments that follow do NOT apply to \fBpcre[16|32]_dfa_exec()\fP; they are
   44: relevant only for \fBpcre[16|32]_exec()\fP without the JIT optimization.
   45: .
   46: .
   47: .SS "Reducing \fBpcre[16|32]_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[16|32]_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[16|32]_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[16|32]_stack_malloc\fP and \fBpcre[16|32]_stack_free\fP variables. By
   95: default, these point to \fBmalloc()\fP and \fBfree()\fP, but you can replace
   96: the pointers to cause PCRE to use your own functions. Since the block sizes are
   97: always the same, and are always freed in reverse order, it may be possible to
   98: implement customized memory handlers that are more efficient than the standard
   99: functions.
  100: .
  101: .
  102: .SS "Limiting \fBpcre[16|32]_exec()\fP's stack usage"
  103: .rs
  104: .sp
  105: You can set limits on the number of times that \fBmatch()\fP is called, both in
  106: total and recursively. If a limit is exceeded, \fBpcre[16|32]_exec()\fP returns an
  107: error code. Setting suitable limits should prevent it from running out of
  108: stack. The default values of the limits are very large, and unlikely ever to
  109: operate. They can be changed when PCRE is built, and they can also be set when
  110: \fBpcre[16|32]_exec()\fP is called. For details of these interfaces, see the
  111: .\" HREF
  112: \fBpcrebuild\fP
  113: .\"
  114: documentation and the
  115: .\" HTML <a href="pcreapi.html#extradata">
  116: .\" </a>
  117: section on extra data for \fBpcre[16|32]_exec()\fP
  118: .\"
  119: in the
  120: .\" HREF
  121: \fBpcreapi\fP
  122: .\"
  123: documentation.
  124: .P
  125: As a very rough rule of thumb, you should reckon on about 500 bytes per
  126: recursion. Thus, if you want to limit your stack usage to 8Mb, you should set
  127: the limit at 16000 recursions. A 64Mb stack, on the other hand, can support
  128: around 128000 recursions.
  129: .P
  130: In Unix-like environments, the \fBpcretest\fP test program has a command line
  131: option (\fB-S\fP) that can be used to increase the size of its stack. As long
  132: as the stack is large enough, another option (\fB-M\fP) can be used to find the
  133: smallest limits that allow a particular pattern to match a given subject
  134: string. This is done by calling \fBpcre[16|32]_exec()\fP repeatedly with different
  135: limits.
  136: .
  137: .
  138: .SS "Obtaining an estimate of stack usage"
  139: .rs
  140: .sp
  141: The actual amount of stack used per recursion can vary quite a lot, depending
  142: on the compiler that was used to build PCRE and the optimization or debugging
  143: options that were set for it. The rule of thumb value of 500 bytes mentioned
  144: above may be larger or smaller than what is actually needed. A better
  145: approximation can be obtained by running this command:
  146: .sp
  147:   pcretest -m -C
  148: .sp
  149: The \fB-C\fP option causes \fBpcretest\fP to output information about the
  150: options with which PCRE was compiled. When \fB-m\fP is also given (before
  151: \fB-C\fP), information about stack use is given in a line like this:
  152: .sp
  153:   Match recursion uses stack: approximate frame size = 640 bytes
  154: .sp
  155: The value is approximate because some recursions need a bit more (up to perhaps
  156: 16 more bytes).
  157: .P
  158: If the above command is given when PCRE is compiled to use the heap instead of
  159: the stack for recursion, the value that is output is the size of each block
  160: that is obtained from the heap.
  161: .
  162: .
  163: .SS "Changing stack size in Unix-like systems"
  164: .rs
  165: .sp
  166: In Unix-like environments, there is not often a problem with the stack unless
  167: very long strings are involved, though the default limit on stack size varies
  168: from system to system. Values from 8Mb to 64Mb are common. You can find your
  169: default limit by running the command:
  170: .sp
  171:   ulimit -s
  172: .sp
  173: Unfortunately, the effect of running out of stack is often SIGSEGV, though
  174: sometimes a more explicit error message is given. You can normally increase the
  175: limit on stack size by code such as this:
  176: .sp
  177:   struct rlimit rlim;
  178:   getrlimit(RLIMIT_STACK, &rlim);
  179:   rlim.rlim_cur = 100*1024*1024;
  180:   setrlimit(RLIMIT_STACK, &rlim);
  181: .sp
  182: This reads the current limits (soft and hard) using \fBgetrlimit()\fP, then
  183: attempts to increase the soft limit to 100Mb using \fBsetrlimit()\fP. You must
  184: do this before calling \fBpcre[16|32]_exec()\fP.
  185: .
  186: .
  187: .SS "Changing stack size in Mac OS X"
  188: .rs
  189: .sp
  190: Using \fBsetrlimit()\fP, as described above, should also work on Mac OS X. It
  191: is also possible to set a stack size when linking a program. There is a
  192: discussion about stack sizes in Mac OS X at this web site:
  193: .\" HTML <a href="http://developer.apple.com/qa/qa2005/qa1419.html">
  194: .\" </a>
  195: http://developer.apple.com/qa/qa2005/qa1419.html.
  196: .\"
  197: .
  198: .
  199: .SH AUTHOR
  200: .rs
  201: .sp
  202: .nf
  203: Philip Hazel
  204: University Computing Service
  205: Cambridge CB2 3QH, England.
  206: .fi
  207: .
  208: .
  209: .SH REVISION
  210: .rs
  211: .sp
  212: .nf
  213: Last updated: 24 June 2012
  214: Copyright (c) 1997-2012 University of Cambridge.
  215: .fi