|
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. |
|
24 </P> |
|
25 <P> |
|
26 Not all calls of <b>match()</b> increase the recursion depth; for an item such |
|
27 as a* it may be called several times at the same level, after matching |
|
28 different numbers of a's. Furthermore, in a number of cases where the result of |
|
29 the recursive call would immediately be passed back as the result of the |
|
30 current call (a "tail recursion"), the function is just restarted instead. |
|
31 </P> |
|
32 <P> |
|
33 The <b>pcre_dfa_exec()</b> function operates in an entirely different way, and |
|
34 hardly uses recursion at all. The limit on its complexity is the amount of |
|
35 workspace it is given. The comments that follow do NOT apply to |
|
36 <b>pcre_dfa_exec()</b>; they are relevant only for <b>pcre_exec()</b>. |
|
37 </P> |
|
38 <P> |
|
39 You can set limits on the number of times that <b>match()</b> is called, both in |
|
40 total and recursively. If the limit is exceeded, an error occurs. For details, |
|
41 see the |
|
42 <a href="pcreapi.html#extradata">section on extra data for <b>pcre_exec()</b></a> |
|
43 in the |
|
44 <a href="pcreapi.html"><b>pcreapi</b></a> |
|
45 documentation. |
|
46 </P> |
|
47 <P> |
|
48 Each time that <b>match()</b> is actually called recursively, it uses memory |
|
49 from the process stack. For certain kinds of pattern and data, very large |
|
50 amounts of stack may be needed, despite the recognition of "tail recursion". |
|
51 You can often reduce the amount of recursion, and therefore the amount of stack |
|
52 used, by modifying the pattern that is being matched. Consider, for example, |
|
53 this pattern: |
|
54 <pre> |
|
55 ([^<]|<(?!inet))+ |
|
56 </pre> |
|
57 It matches from wherever it starts until it encounters "<inet" or the end of |
|
58 the data, and is the kind of pattern that might be used when processing an XML |
|
59 file. Each iteration of the outer parentheses matches either one character that |
|
60 is not "<" or a "<" that is not followed by "inet". However, each time a |
|
61 parenthesis is processed, a recursion occurs, so this formulation uses a stack |
|
62 frame for each matched character. For a long string, a lot of stack is |
|
63 required. Consider now this rewritten pattern, which matches exactly the same |
|
64 strings: |
|
65 <pre> |
|
66 ([^<]++|<(?!inet))+ |
|
67 </pre> |
|
68 This uses very much less stack, because runs of characters that do not contain |
|
69 "<" are "swallowed" in one item inside the parentheses. Recursion happens only |
|
70 when a "<" character that is not followed by "inet" is encountered (and we |
|
71 assume this is relatively rare). A possessive quantifier is used to stop any |
|
72 backtracking into the runs of non-"<" characters, but that is not related to |
|
73 stack usage. |
|
74 </P> |
|
75 <P> |
|
76 This example shows that one way of avoiding stack problems when matching long |
|
77 subject strings is to write repeated parenthesized subpatterns to match more |
|
78 than one character whenever possible. |
|
79 </P> |
|
80 <br><b> |
|
81 Compiling PCRE to use heap instead of stack |
|
82 </b><br> |
|
83 <P> |
|
84 In environments where stack memory is constrained, you might want to compile |
|
85 PCRE to use heap memory instead of stack for remembering back-up points. This |
|
86 makes it run a lot more slowly, however. Details of how to do this are given in |
|
87 the |
|
88 <a href="pcrebuild.html"><b>pcrebuild</b></a> |
|
89 documentation. When built in this way, instead of using the stack, PCRE obtains |
|
90 and frees memory by calling the functions that are pointed to by the |
|
91 <b>pcre_stack_malloc</b> and <b>pcre_stack_free</b> variables. By default, these |
|
92 point to <b>malloc()</b> and <b>free()</b>, but you can replace the pointers to |
|
93 cause PCRE to use your own functions. Since the block sizes are always the |
|
94 same, and are always freed in reverse order, it may be possible to implement |
|
95 customized memory handlers that are more efficient than the standard functions. |
|
96 </P> |
|
97 <br><b> |
|
98 Limiting PCRE's stack usage |
|
99 </b><br> |
|
100 <P> |
|
101 PCRE has an internal counter that can be used to limit the depth of recursion, |
|
102 and thus cause <b>pcre_exec()</b> to give an error code before it runs out of |
|
103 stack. By default, the limit is very large, and unlikely ever to operate. It |
|
104 can be changed when PCRE is built, and it can also be set when |
|
105 <b>pcre_exec()</b> is called. For details of these interfaces, see the |
|
106 <a href="pcrebuild.html"><b>pcrebuild</b></a> |
|
107 and |
|
108 <a href="pcreapi.html"><b>pcreapi</b></a> |
|
109 documentation. |
|
110 </P> |
|
111 <P> |
|
112 As a very rough rule of thumb, you should reckon on about 500 bytes per |
|
113 recursion. Thus, if you want to limit your stack usage to 8Mb, you |
|
114 should set the limit at 16000 recursions. A 64Mb stack, on the other hand, can |
|
115 support around 128000 recursions. The <b>pcretest</b> test program has a command |
|
116 line option (<b>-S</b>) that can be used to increase the size of its stack. |
|
117 </P> |
|
118 <br><b> |
|
119 Changing stack size in Unix-like systems |
|
120 </b><br> |
|
121 <P> |
|
122 In Unix-like environments, there is not often a problem with the stack unless |
|
123 very long strings are involved, though the default limit on stack size varies |
|
124 from system to system. Values from 8Mb to 64Mb are common. You can find your |
|
125 default limit by running the command: |
|
126 <pre> |
|
127 ulimit -s |
|
128 </pre> |
|
129 Unfortunately, the effect of running out of stack is often SIGSEGV, though |
|
130 sometimes a more explicit error message is given. You can normally increase the |
|
131 limit on stack size by code such as this: |
|
132 <pre> |
|
133 struct rlimit rlim; |
|
134 getrlimit(RLIMIT_STACK, &rlim); |
|
135 rlim.rlim_cur = 100*1024*1024; |
|
136 setrlimit(RLIMIT_STACK, &rlim); |
|
137 </pre> |
|
138 This reads the current limits (soft and hard) using <b>getrlimit()</b>, then |
|
139 attempts to increase the soft limit to 100Mb using <b>setrlimit()</b>. You must |
|
140 do this before calling <b>pcre_exec()</b>. |
|
141 </P> |
|
142 <br><b> |
|
143 Changing stack size in Mac OS X |
|
144 </b><br> |
|
145 <P> |
|
146 Using <b>setrlimit()</b>, as described above, should also work on Mac OS X. It |
|
147 is also possible to set a stack size when linking a program. There is a |
|
148 discussion about stack sizes in Mac OS X at this web site: |
|
149 <a href="http://developer.apple.com/qa/qa2005/qa1419.html">http://developer.apple.com/qa/qa2005/qa1419.html.</a> |
|
150 </P> |
|
151 <br><b> |
|
152 AUTHOR |
|
153 </b><br> |
|
154 <P> |
|
155 Philip Hazel |
|
156 <br> |
|
157 University Computing Service |
|
158 <br> |
|
159 Cambridge CB2 3QH, England. |
|
160 <br> |
|
161 </P> |
|
162 <br><b> |
|
163 REVISION |
|
164 </b><br> |
|
165 <P> |
|
166 Last updated: 09 July 2008 |
|
167 <br> |
|
168 Copyright © 1997-2008 University of Cambridge. |
|
169 <br> |
|
170 <p> |
|
171 Return to the <a href="index.html">PCRE index page</a>. |
|
172 </p> |