Annotation of embedaddon/pcre/doc/pcrestack.3, revision 1.1.1.2
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
1.1.1.2 ! misho 7: When you call \fBpcre[16]_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
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.2 ! misho 22: The above comments apply when \fBpcre[16]_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.2 ! misho 25: the options passed to \fBpcre[16]_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.2 ! misho 33: The \fBpcre[16]_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]_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]_dfa_exec()\fP to run out of stack. At
! 41: present, there is no protection against this.
1.1 misho 42: .P
1.1.1.2 ! misho 43: The comments that follow do NOT apply to \fBpcre[16]_dfa_exec()\fP; they are
! 44: relevant only for \fBpcre[16]_exec()\fP without the JIT optimization.
1.1 misho 45: .
46: .
1.1.1.2 ! misho 47: .SS "Reducing \fBpcre[16]_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.2 ! misho 82: .SS "Compiling PCRE to use heap instead of stack for \fBpcre[16]_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.2 ! misho 87: \fBpcre[16]_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.2 ! misho 94: \fBpcre[16]_stack_malloc\fP and \fBpcre[16]_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.
1.1 misho 100: .
101: .
1.1.1.2 ! misho 102: .SS "Limiting \fBpcre[16]_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.2 ! misho 106: total and recursively. If a limit is exceeded, \fBpcre[16]_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.2 ! misho 110: \fBpcre[16]_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.2 ! misho 117: section on extra data for \fBpcre[16]_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.2 ! misho 134: string. This is done by calling \fBpcre[16]_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.2 ! misho 184: do this before calling \fBpcre[16]_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.2 ! misho 213: Last updated: 21 January 2012
! 214: Copyright (c) 1997-2012 University of Cambridge.
1.1 misho 215: .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