Annotation of embedaddon/pcre/doc/html/pcrestack.html, revision 1.1
1.1 ! misho 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>
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to pcrestack.html CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / pcre / doc / html