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: ([^<]|<(?!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>
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 © 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>
![[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