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