Annotation of embedaddon/pcre/doc/html/pcrestack.html, revision 1.1.1.3

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>
1.1.1.3 ! misho      19: When you call <b>pcre[16|32]_exec()</b>, it makes use of an internal function
1.1.1.2   misho      20: called <b>match()</b>. This calls itself recursively at branch points in the
                     21: pattern, in order to remember the state of the match so that it can back up and
                     22: try a different alternative if the first one fails. As matching proceeds deeper
                     23: and deeper into the tree of possibilities, the recursion depth increases. The
1.1       misho      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>
1.1.1.3 ! misho      36: The above comments apply when <b>pcre[16|32]_exec()</b> is run in its normal
1.1       misho      37: interpretive manner. If the pattern was studied with the
                     38: PCRE_STUDY_JIT_COMPILE option, and just-in-time compiling was successful, and
1.1.1.3 ! misho      39: the options passed to <b>pcre[16|32]_exec()</b> were not incompatible, the matching
1.1       misho      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>
1.1.1.3 ! misho      46: The <b>pcre[16|32]_dfa_exec()</b> function operates in an entirely different way,
1.1.1.2   misho      47: and uses recursion only when there is a regular expression recursion or
                     48: subroutine call in the pattern. This includes the processing of assertion and
                     49: "once-only" subpatterns, which are handled like subroutine calls. Normally,
                     50: these are never very deep, and the limit on the complexity of
1.1.1.3 ! misho      51: <b>pcre[16|32]_dfa_exec()</b> is controlled by the amount of workspace it is given.
1.1.1.2   misho      52: However, it is possible to write patterns with runaway infinite recursions;
1.1.1.3 ! misho      53: such patterns will cause <b>pcre[16|32]_dfa_exec()</b> to run out of stack. At
1.1.1.2   misho      54: present, there is no protection against this.
1.1       misho      55: </P>
                     56: <P>
1.1.1.3 ! misho      57: The comments that follow do NOT apply to <b>pcre[16|32]_dfa_exec()</b>; they are
        !            58: relevant only for <b>pcre[16|32]_exec()</b> without the JIT optimization.
1.1       misho      59: </P>
                     60: <br><b>
1.1.1.3 ! misho      61: Reducing <b>pcre[16|32]_exec()</b>'s stack usage
1.1       misho      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:   ([^&#60;]|&#60;(?!inet))+
                     72: </pre>
                     73: It matches from wherever it starts until it encounters "&#60;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 "&#60;" or a "&#60;" 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:   ([^&#60;]++|&#60;(?!inet))+
                     83: </pre>
                     84: This uses very much less stack, because runs of characters that do not contain
                     85: "&#60;" are "swallowed" in one item inside the parentheses. Recursion happens only
                     86: when a "&#60;" 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-"&#60;" 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>
1.1.1.3 ! misho      97: Compiling PCRE to use heap instead of stack for <b>pcre[16|32]_exec()</b>
1.1       misho      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
1.1.1.3 ! misho     102: <b>pcre[16|32]_exec()</b> is running. This makes it run a lot more slowly, however.
1.1       misho     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
1.1.1.3 ! misho     107: <b>pcre[16|32]_stack_malloc</b> and <b>pcre[16|32]_stack_free</b> variables. By
1.1.1.2   misho     108: default, these point to <b>malloc()</b> and <b>free()</b>, but you can replace
                    109: the pointers to cause PCRE to use your own functions. Since the block sizes are
                    110: always the same, and are always freed in reverse order, it may be possible to
                    111: implement customized memory handlers that are more efficient than the standard
                    112: functions.
1.1       misho     113: </P>
                    114: <br><b>
1.1.1.3 ! misho     115: Limiting <b>pcre[16|32]_exec()</b>'s stack usage
1.1       misho     116: </b><br>
                    117: <P>
                    118: You can set limits on the number of times that <b>match()</b> is called, both in
1.1.1.3 ! misho     119: total and recursively. If a limit is exceeded, <b>pcre[16|32]_exec()</b> returns an
1.1       misho     120: error code. Setting suitable limits should prevent it from running out of
                    121: stack. The default values of the limits are very large, and unlikely ever to
                    122: operate. They can be changed when PCRE is built, and they can also be set when
1.1.1.3 ! misho     123: <b>pcre[16|32]_exec()</b> is called. For details of these interfaces, see the
1.1       misho     124: <a href="pcrebuild.html"><b>pcrebuild</b></a>
                    125: documentation and the
1.1.1.3 ! misho     126: <a href="pcreapi.html#extradata">section on extra data for <b>pcre[16|32]_exec()</b></a>
1.1       misho     127: in the
                    128: <a href="pcreapi.html"><b>pcreapi</b></a>
                    129: documentation.
                    130: </P>
                    131: <P>
                    132: As a very rough rule of thumb, you should reckon on about 500 bytes per
1.1.1.2   misho     133: recursion. Thus, if you want to limit your stack usage to 8Mb, you should set
                    134: the limit at 16000 recursions. A 64Mb stack, on the other hand, can support
                    135: around 128000 recursions.
1.1       misho     136: </P>
                    137: <P>
                    138: In Unix-like environments, the <b>pcretest</b> test program has a command line
                    139: option (<b>-S</b>) that can be used to increase the size of its stack. As long
                    140: as the stack is large enough, another option (<b>-M</b>) can be used to find the
                    141: smallest limits that allow a particular pattern to match a given subject
1.1.1.3 ! misho     142: string. This is done by calling <b>pcre[16|32]_exec()</b> repeatedly with different
1.1       misho     143: limits.
                    144: </P>
                    145: <br><b>
1.1.1.2   misho     146: Obtaining an estimate of stack usage
                    147: </b><br>
                    148: <P>
                    149: The actual amount of stack used per recursion can vary quite a lot, depending
                    150: on the compiler that was used to build PCRE and the optimization or debugging
                    151: options that were set for it. The rule of thumb value of 500 bytes mentioned
                    152: above may be larger or smaller than what is actually needed. A better
                    153: approximation can be obtained by running this command:
                    154: <pre>
                    155:   pcretest -m -C
                    156: </pre>
                    157: The <b>-C</b> option causes <b>pcretest</b> to output information about the
                    158: options with which PCRE was compiled. When <b>-m</b> is also given (before
                    159: <b>-C</b>), information about stack use is given in a line like this:
                    160: <pre>
                    161:   Match recursion uses stack: approximate frame size = 640 bytes
                    162: </pre>
                    163: The value is approximate because some recursions need a bit more (up to perhaps
                    164: 16 more bytes).
                    165: </P>
                    166: <P>
                    167: If the above command is given when PCRE is compiled to use the heap instead of
                    168: the stack for recursion, the value that is output is the size of each block
                    169: that is obtained from the heap.
                    170: </P>
                    171: <br><b>
1.1       misho     172: Changing stack size in Unix-like systems
                    173: </b><br>
                    174: <P>
                    175: In Unix-like environments, there is not often a problem with the stack unless
                    176: very long strings are involved, though the default limit on stack size varies
                    177: from system to system. Values from 8Mb to 64Mb are common. You can find your
                    178: default limit by running the command:
                    179: <pre>
                    180:   ulimit -s
                    181: </pre>
                    182: Unfortunately, the effect of running out of stack is often SIGSEGV, though
                    183: sometimes a more explicit error message is given. You can normally increase the
                    184: limit on stack size by code such as this:
                    185: <pre>
                    186:   struct rlimit rlim;
                    187:   getrlimit(RLIMIT_STACK, &rlim);
                    188:   rlim.rlim_cur = 100*1024*1024;
                    189:   setrlimit(RLIMIT_STACK, &rlim);
                    190: </pre>
                    191: This reads the current limits (soft and hard) using <b>getrlimit()</b>, then
                    192: attempts to increase the soft limit to 100Mb using <b>setrlimit()</b>. You must
1.1.1.3 ! misho     193: do this before calling <b>pcre[16|32]_exec()</b>.
1.1       misho     194: </P>
                    195: <br><b>
                    196: Changing stack size in Mac OS X
                    197: </b><br>
                    198: <P>
                    199: Using <b>setrlimit()</b>, as described above, should also work on Mac OS X. It
                    200: is also possible to set a stack size when linking a program. There is a
                    201: discussion about stack sizes in Mac OS X at this web site:
                    202: <a href="http://developer.apple.com/qa/qa2005/qa1419.html">http://developer.apple.com/qa/qa2005/qa1419.html.</a>
                    203: </P>
                    204: <br><b>
                    205: AUTHOR
                    206: </b><br>
                    207: <P>
                    208: Philip Hazel
                    209: <br>
                    210: University Computing Service
                    211: <br>
                    212: Cambridge CB2 3QH, England.
                    213: <br>
                    214: </P>
                    215: <br><b>
                    216: REVISION
                    217: </b><br>
                    218: <P>
1.1.1.3 ! misho     219: Last updated: 24 June 2012
1.1       misho     220: <br>
1.1.1.2   misho     221: Copyright &copy; 1997-2012 University of Cambridge.
1.1       misho     222: <br>
                    223: <p>
                    224: Return to the <a href="index.html">PCRE index page</a>.
                    225: </p>

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>