+Return to the PCRE index page. +
+
+This page is part of the PCRE HTML documentation. It was generated automatically
+from the original man page. If there is any nonsense in it, please consult the
+man page, in case the conversion went wrong.
+
+
+PCRE DISCUSSION OF STACK USAGE
+
+
+When you call pcre_exec(), it makes use of an internal function called +match(). This calls itself recursively at branch points in the pattern, +in order to remember the state of the match so that it can back up and try a +different alternative if the first one fails. As matching proceeds deeper and +deeper into the tree of possibilities, the recursion depth increases. +
++Not all calls of match() increase the recursion depth; for an item such +as a* it may be called several times at the same level, after matching +different numbers of a's. Furthermore, in a number of cases where the result of +the recursive call would immediately be passed back as the result of the +current call (a "tail recursion"), the function is just restarted instead. +
++The pcre_dfa_exec() function operates in an entirely different way, and +hardly uses recursion at all. The limit on its complexity is the amount of +workspace it is given. The comments that follow do NOT apply to +pcre_dfa_exec(); they are relevant only for pcre_exec(). +
++You can set limits on the number of times that match() is called, both in +total and recursively. If the limit is exceeded, an error occurs. For details, +see the +section on extra data for pcre_exec() +in the +pcreapi +documentation. +
++Each time that match() is actually called recursively, it uses memory +from the process stack. For certain kinds of pattern and data, very large +amounts of stack may be needed, despite the recognition of "tail recursion". +You can often reduce the amount of recursion, and therefore the amount of stack +used, by modifying the pattern that is being matched. Consider, for example, +this pattern: +
+ ([^<]|<(?!inet))+ ++It matches from wherever it starts until it encounters "<inet" or the end of +the data, and is the kind of pattern that might be used when processing an XML +file. Each iteration of the outer parentheses matches either one character that +is not "<" or a "<" that is not followed by "inet". However, each time a +parenthesis is processed, a recursion occurs, so this formulation uses a stack +frame for each matched character. For a long string, a lot of stack is +required. Consider now this rewritten pattern, which matches exactly the same +strings: +
+ ([^<]++|<(?!inet))+ ++This uses very much less stack, because runs of characters that do not contain +"<" are "swallowed" in one item inside the parentheses. Recursion happens only +when a "<" character that is not followed by "inet" is encountered (and we +assume this is relatively rare). A possessive quantifier is used to stop any +backtracking into the runs of non-"<" characters, but that is not related to +stack usage. + +
+This example shows that one way of avoiding stack problems when matching long +subject strings is to write repeated parenthesized subpatterns to match more +than one character whenever possible. +
++In environments where stack memory is constrained, you might want to compile +PCRE to use heap memory instead of stack for remembering back-up points. This +makes it run a lot more slowly, however. Details of how to do this are given in +the +pcrebuild +documentation. When built in this way, instead of using the stack, PCRE obtains +and frees memory by calling the functions that are pointed to by the +pcre_stack_malloc and pcre_stack_free variables. By default, these +point to malloc() and free(), but you can replace the pointers to +cause PCRE to use your own functions. Since the block sizes are always the +same, and are always freed in reverse order, it may be possible to implement +customized memory handlers that are more efficient than the standard functions. +
++PCRE has an internal counter that can be used to limit the depth of recursion, +and thus cause pcre_exec() to give an error code before it runs out of +stack. By default, the limit is very large, and unlikely ever to operate. It +can be changed when PCRE is built, and it can also be set when +pcre_exec() is called. For details of these interfaces, see the +pcrebuild +and +pcreapi +documentation. +
++As a very rough rule of thumb, you should reckon on about 500 bytes per +recursion. Thus, if you want to limit your stack usage to 8Mb, you +should set the limit at 16000 recursions. A 64Mb stack, on the other hand, can +support around 128000 recursions. The pcretest test program has a command +line option (-S) that can be used to increase the size of its stack. +
++In Unix-like environments, there is not often a problem with the stack unless +very long strings are involved, though the default limit on stack size varies +from system to system. Values from 8Mb to 64Mb are common. You can find your +default limit by running the command: +
+ ulimit -s ++Unfortunately, the effect of running out of stack is often SIGSEGV, though +sometimes a more explicit error message is given. You can normally increase the +limit on stack size by code such as this: +
+ struct rlimit rlim; + getrlimit(RLIMIT_STACK, &rlim); + rlim.rlim_cur = 100*1024*1024; + setrlimit(RLIMIT_STACK, &rlim); ++This reads the current limits (soft and hard) using getrlimit(), then +attempts to increase the soft limit to 100Mb using setrlimit(). You must +do this before calling pcre_exec(). + +
+Using setrlimit(), as described above, should also work on Mac OS X. It +is also possible to set a stack size when linking a program. There is a +discussion about stack sizes in Mac OS X at this web site: +http://developer.apple.com/qa/qa2005/qa1419.html. +
+
+Philip Hazel
+
+University Computing Service
+
+Cambridge CB2 3QH, England.
+
+
+Last updated: 09 July 2008
+
+Copyright © 1997-2008 University of Cambridge.
+
+
+Return to the PCRE index page. +