Annotation of embedaddon/pcre/doc/html/pcrestack.html, revision 1.1.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