Annotation of embedaddon/pcre/doc/pcrestack.3, revision 1.1.1.4

1.1.1.4 ! misho       1: .TH PCRESTACK 3 "24 June 2012" "PCRE 8.30"
1.1       misho       2: .SH NAME
                      3: PCRE - Perl-compatible regular expressions
                      4: .SH "PCRE DISCUSSION OF STACK USAGE"
                      5: .rs
                      6: .sp
1.1.1.4 ! misho       7: When you call \fBpcre[16|32]_exec()\fP, it makes use of an internal function
1.1.1.2   misho       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
1.1       misho      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
1.1.1.4 ! misho      22: The above comments apply when \fBpcre[16|32]_exec()\fP is run in its normal
1.1       misho      23: interpretive manner. If the pattern was studied with the
                     24: PCRE_STUDY_JIT_COMPILE option, and just-in-time compiling was successful, and
1.1.1.4 ! misho      25: the options passed to \fBpcre[16|32]_exec()\fP were not incompatible, the matching
1.1       misho      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
1.1.1.4 ! misho      33: The \fBpcre[16|32]_dfa_exec()\fP function operates in an entirely different way,
1.1.1.2   misho      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
1.1.1.4 ! misho      38: \fBpcre[16|32]_dfa_exec()\fP is controlled by the amount of workspace it is given.
1.1.1.2   misho      39: However, it is possible to write patterns with runaway infinite recursions;
1.1.1.4 ! misho      40: such patterns will cause \fBpcre[16|32]_dfa_exec()\fP to run out of stack. At
1.1.1.2   misho      41: present, there is no protection against this.
1.1       misho      42: .P
1.1.1.4 ! misho      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.
1.1       misho      45: .
                     46: .
1.1.1.4 ! misho      47: .SS "Reducing \fBpcre[16|32]_exec()\fP's stack usage"
1.1       misho      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: .
1.1.1.4 ! misho      82: .SS "Compiling PCRE to use heap instead of stack for \fBpcre[16|32]_exec()\fP"
1.1       misho      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
1.1.1.4 ! misho      87: \fBpcre[16|32]_exec()\fP is running. This makes it run a lot more slowly, however.
1.1       misho      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
1.1.1.4 ! misho      94: \fBpcre[16|32]_stack_malloc\fP and \fBpcre[16|32]_stack_free\fP variables. By
1.1.1.2   misho      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.
1.1       misho     100: .
                    101: .
1.1.1.4 ! misho     102: .SS "Limiting \fBpcre[16|32]_exec()\fP's stack usage"
1.1       misho     103: .rs
                    104: .sp
                    105: You can set limits on the number of times that \fBmatch()\fP is called, both in
1.1.1.4 ! misho     106: total and recursively. If a limit is exceeded, \fBpcre[16|32]_exec()\fP returns an
1.1       misho     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
1.1.1.4 ! misho     110: \fBpcre[16|32]_exec()\fP is called. For details of these interfaces, see the
1.1       misho     111: .\" HREF
                    112: \fBpcrebuild\fP
                    113: .\"
                    114: documentation and the
                    115: .\" HTML <a href="pcreapi.html#extradata">
                    116: .\" </a>
1.1.1.4 ! misho     117: section on extra data for \fBpcre[16|32]_exec()\fP
1.1       misho     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
1.1.1.2   misho     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.
1.1       misho     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
1.1.1.4 ! misho     134: string. This is done by calling \fBpcre[16|32]_exec()\fP repeatedly with different
1.1       misho     135: limits.
                    136: .
                    137: .
1.1.1.2   misho     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: .
1.1       misho     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
1.1.1.4 ! misho     184: do this before calling \fBpcre[16|32]_exec()\fP.
1.1       misho     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
1.1.1.4 ! misho     213: Last updated: 24 June 2012
1.1.1.2   misho     214: Copyright (c) 1997-2012 University of Cambridge.
1.1       misho     215: .fi

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