262 lines
10 KiB
HTML
262 lines
10 KiB
HTML
|
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
|
|
<HTML><HEAD><TITLE>Man page of PCRESTACK</TITLE>
|
|
</HEAD><BODY>
|
|
<H1>PCRESTACK</H1>
|
|
Section: C Library Functions (3)<BR>Updated: 24 June 2012<BR><A HREF="#index">Index</A>
|
|
<A HREF="/cgi-bin/man/man2html">Return to Main Contents</A><HR>
|
|
|
|
<A NAME="lbAB"> </A>
|
|
<H2>NAME</H2>
|
|
|
|
PCRE - Perl-compatible regular expressions
|
|
<A NAME="lbAC"> </A>
|
|
<H2>PCRE DISCUSSION OF STACK USAGE</H2>
|
|
|
|
|
|
<P>
|
|
When you call <B>pcre[16|32]_exec()</B>, it makes use of an internal function
|
|
called <B>match()</B>. 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. The
|
|
<B>match()</B> function is also called in other circumstances, for example,
|
|
whenever a parenthesized sub-pattern is entered, and in certain cases of
|
|
repetition.
|
|
<P>
|
|
|
|
Not all calls of <B>match()</B> 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.
|
|
<P>
|
|
|
|
The above comments apply when <B>pcre[16|32]_exec()</B> is run in its normal
|
|
interpretive manner. If the pattern was studied with the
|
|
PCRE_STUDY_JIT_COMPILE option, and just-in-time compiling was successful, and
|
|
the options passed to <B>pcre[16|32]_exec()</B> were not incompatible, the matching
|
|
process uses the JIT-compiled code instead of the <B>match()</B> function. In
|
|
this case, the memory requirements are handled entirely differently. See the
|
|
|
|
<B>pcrejit</B>
|
|
|
|
documentation for details.
|
|
<P>
|
|
|
|
The <B>pcre[16|32]_dfa_exec()</B> function operates in an entirely different way,
|
|
and uses recursion only when there is a regular expression recursion or
|
|
subroutine call in the pattern. This includes the processing of assertion and
|
|
"once-only" subpatterns, which are handled like subroutine calls. Normally,
|
|
these are never very deep, and the limit on the complexity of
|
|
<B>pcre[16|32]_dfa_exec()</B> is controlled by the amount of workspace it is given.
|
|
However, it is possible to write patterns with runaway infinite recursions;
|
|
such patterns will cause <B>pcre[16|32]_dfa_exec()</B> to run out of stack. At
|
|
present, there is no protection against this.
|
|
<P>
|
|
|
|
The comments that follow do NOT apply to <B>pcre[16|32]_dfa_exec()</B>; they are
|
|
relevant only for <B>pcre[16|32]_exec()</B> without the JIT optimization.
|
|
<A NAME="lbAD"> </A>
|
|
<H3>Reducing <B>pcre[16|32]_exec()</B>'s stack usage</H3>
|
|
|
|
|
|
<P>
|
|
Each time that <B>match()</B> 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:
|
|
<P>
|
|
<BR> ([^<]|<(?!inet))+
|
|
<P>
|
|
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:
|
|
<P>
|
|
<BR> ([^<]++|<(?!inet))+
|
|
<P>
|
|
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.
|
|
<P>
|
|
|
|
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.
|
|
<A NAME="lbAE"> </A>
|
|
<H3>Compiling PCRE to use heap instead of stack for <B>pcre[16|32]_exec()</B></H3>
|
|
|
|
|
|
<P>
|
|
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 when
|
|
<B>pcre[16|32]_exec()</B> is running. This makes it run a lot more slowly, however.
|
|
Details of how to do this are given in the
|
|
|
|
<B>pcrebuild</B>
|
|
|
|
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
|
|
<B>pcre[16|32]_stack_malloc</B> and <B>pcre[16|32]_stack_free</B> variables. By
|
|
default, these point to <B>malloc()</B> and <B>free()</B>, 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.
|
|
<A NAME="lbAF"> </A>
|
|
<H3>Limiting <B>pcre[16|32]_exec()</B>'s stack usage</H3>
|
|
|
|
|
|
<P>
|
|
You can set limits on the number of times that <B>match()</B> is called, both in
|
|
total and recursively. If a limit is exceeded, <B>pcre[16|32]_exec()</B> returns an
|
|
error code. Setting suitable limits should prevent it from running out of
|
|
stack. The default values of the limits are very large, and unlikely ever to
|
|
operate. They can be changed when PCRE is built, and they can also be set when
|
|
<B>pcre[16|32]_exec()</B> is called. For details of these interfaces, see the
|
|
|
|
<B>pcrebuild</B>
|
|
|
|
documentation and the
|
|
|
|
|
|
section on extra data for <B>pcre[16|32]_exec()</B>
|
|
|
|
in the
|
|
|
|
<B>pcreapi</B>
|
|
|
|
documentation.
|
|
<P>
|
|
|
|
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.
|
|
<P>
|
|
|
|
In Unix-like environments, the <B>pcretest</B> test program has a command line
|
|
option (<B>-S</B>) that can be used to increase the size of its stack. As long
|
|
as the stack is large enough, another option (<B>-M</B>) can be used to find the
|
|
smallest limits that allow a particular pattern to match a given subject
|
|
string. This is done by calling <B>pcre[16|32]_exec()</B> repeatedly with different
|
|
limits.
|
|
<A NAME="lbAG"> </A>
|
|
<H3>Obtaining an estimate of stack usage</H3>
|
|
|
|
|
|
<P>
|
|
The actual amount of stack used per recursion can vary quite a lot, depending
|
|
on the compiler that was used to build PCRE and the optimization or debugging
|
|
options that were set for it. The rule of thumb value of 500 bytes mentioned
|
|
above may be larger or smaller than what is actually needed. A better
|
|
approximation can be obtained by running this command:
|
|
<P>
|
|
<BR> pcretest -m -C
|
|
<P>
|
|
The <B>-C</B> option causes <B>pcretest</B> to output information about the
|
|
options with which PCRE was compiled. When <B>-m</B> is also given (before
|
|
<B>-C</B>), information about stack use is given in a line like this:
|
|
<P>
|
|
<BR> Match recursion uses stack: approximate frame size = 640 bytes
|
|
<P>
|
|
The value is approximate because some recursions need a bit more (up to perhaps
|
|
16 more bytes).
|
|
<P>
|
|
|
|
If the above command is given when PCRE is compiled to use the heap instead of
|
|
the stack for recursion, the value that is output is the size of each block
|
|
that is obtained from the heap.
|
|
<A NAME="lbAH"> </A>
|
|
<H3>Changing stack size in Unix-like systems</H3>
|
|
|
|
|
|
<P>
|
|
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:
|
|
<P>
|
|
<BR> ulimit -s
|
|
<P>
|
|
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:
|
|
<P>
|
|
<BR> struct rlimit rlim;
|
|
<BR> getrlimit(RLIMIT_STACK, &rlim);
|
|
<BR> rlim.rlim_cur = 100*1024*1024;
|
|
<BR> setrlimit(RLIMIT_STACK, &rlim);
|
|
<P>
|
|
This reads the current limits (soft and hard) using <B>getrlimit()</B>, then
|
|
attempts to increase the soft limit to 100Mb using <B>setrlimit()</B>. You must
|
|
do this before calling <B>pcre[16|32]_exec()</B>.
|
|
<A NAME="lbAI"> </A>
|
|
<H3>Changing stack size in Mac OS X</H3>
|
|
|
|
|
|
<P>
|
|
Using <B>setrlimit()</B>, 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:
|
|
|
|
|
|
<A HREF="http://developer.apple.com/qa/qa2005/qa1419.html.">http://developer.apple.com/qa/qa2005/qa1419.html.</A>
|
|
|
|
<A NAME="lbAJ"> </A>
|
|
<H2>AUTHOR</H2>
|
|
|
|
|
|
<P>
|
|
<PRE>
|
|
Philip Hazel
|
|
University Computing Service
|
|
Cambridge CB2 3QH, England.
|
|
</PRE>
|
|
|
|
<A NAME="lbAK"> </A>
|
|
<H2>REVISION</H2>
|
|
|
|
|
|
<P>
|
|
<PRE>
|
|
Last updated: 24 June 2012
|
|
Copyright (c) 1997-2012 University of Cambridge.
|
|
</PRE>
|
|
|
|
<P>
|
|
|
|
<HR>
|
|
<A NAME="index"> </A><H2>Index</H2>
|
|
<DL>
|
|
<DT id="1"><A HREF="#lbAB">NAME</A><DD>
|
|
<DT id="2"><A HREF="#lbAC">PCRE DISCUSSION OF STACK USAGE</A><DD>
|
|
<DL>
|
|
<DT id="3"><A HREF="#lbAD">Reducing <B>pcre[16|32]_exec()</B>'s stack usage</A><DD>
|
|
<DT id="4"><A HREF="#lbAE">Compiling PCRE to use heap instead of stack for <B>pcre[16|32]_exec()</B></A><DD>
|
|
<DT id="5"><A HREF="#lbAF">Limiting <B>pcre[16|32]_exec()</B>'s stack usage</A><DD>
|
|
<DT id="6"><A HREF="#lbAG">Obtaining an estimate of stack usage</A><DD>
|
|
<DT id="7"><A HREF="#lbAH">Changing stack size in Unix-like systems</A><DD>
|
|
<DT id="8"><A HREF="#lbAI">Changing stack size in Mac OS X</A><DD>
|
|
</DL>
|
|
<DT id="9"><A HREF="#lbAJ">AUTHOR</A><DD>
|
|
<DT id="10"><A HREF="#lbAK">REVISION</A><DD>
|
|
</DL>
|
|
<HR>
|
|
This document was created by
|
|
<A HREF="/cgi-bin/man/man2html">man2html</A>,
|
|
using the manual pages.<BR>
|
|
Time: 00:05:52 GMT, March 31, 2021
|
|
</BODY>
|
|
</HTML>
|