embedaddon/pcre/doc/html/pcrestack.html - view

File: [ELWIX - Embedded LightWeight unIX -] / embedaddon / pcre / doc / html / pcrestack.html
Revision 1.1.1.3 (vendor branch): download - view: text, annotated - select for diffs - revision graph
Mon Jul 22 08:25:57 2013 UTC (11 years, 8 months ago) by misho
Branches: pcre, MAIN
CVS tags: v8_34, v8_33, HEAD

8.33

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:  8: Return to the <a href="index.html">PCRE index page</a>. 9:  10:  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:   15:   16: PCRE DISCUSSION OF STACK USAGE 17:   18:  19: When you call pcre[16|32]_exec(), it makes use of an internal function 20: called match(). 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 24: match() 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:  28:  29: Not all calls of match() 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:  35:  36: The above comments apply when pcre[16|32]_exec() 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 pcre[16|32]_exec() were not incompatible, the matching 40: process uses the JIT-compiled code instead of the match() function. In 41: this case, the memory requirements are handled entirely differently. See the 42: <a href="pcrejit.html">pcrejit</a> 43: documentation for details. 44:  45:  46: The pcre[16|32]_dfa_exec() function operates in an entirely different way, 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 51: pcre[16|32]_dfa_exec() is controlled by the amount of workspace it is given. 52: However, it is possible to write patterns with runaway infinite recursions; 53: such patterns will cause pcre[16|32]_dfa_exec() to run out of stack. At 54: present, there is no protection against this. 55:  56:  57: The comments that follow do NOT apply to pcre[16|32]_dfa_exec(); they are 58: relevant only for pcre[16|32]_exec() without the JIT optimization. 59:  60:   61: Reducing pcre[16|32]_exec()'s stack usage 62:   63:  64: Each time that match() 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:  91:  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:  96:   97: Compiling PCRE to use heap instead of stack for pcre[16|32]_exec() 98:   99:  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: pcre[16|32]_exec() 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">pcrebuild</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: pcre[16|32]_stack_malloc and pcre[16|32]_stack_free variables. By 108: default, these point to malloc() and free(), 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. 113:  114:   115: Limiting pcre[16|32]_exec()'s stack usage 116:   117:  118: You can set limits on the number of times that match() is called, both in 119: total and recursively. If a limit is exceeded, pcre[16|32]_exec() returns an 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 123: pcre[16|32]_exec() is called. For details of these interfaces, see the 124: <a href="pcrebuild.html">pcrebuild</a> 125: documentation and the 126: <a href="pcreapi.html#extradata">section on extra data for pcre[16|32]_exec()</a> 127: in the 128: <a href="pcreapi.html">pcreapi</a> 129: documentation. 130:  131:  132: As a very rough rule of thumb, you should reckon on about 500 bytes per 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. 136:  137:  138: In Unix-like environments, the pcretest test program has a command line 139: option (-S) that can be used to increase the size of its stack. As long 140: as the stack is large enough, another option (-M) can be used to find the 141: smallest limits that allow a particular pattern to match a given subject 142: string. This is done by calling pcre[16|32]_exec() repeatedly with different 143: limits. 144:  145:   146: Obtaining an estimate of stack usage 147:   148:  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 -C option causes pcretest to output information about the 158: options with which PCRE was compiled. When -m is also given (before 159: -C), 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:  166:  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:  171:   172: Changing stack size in Unix-like systems 173:   174:  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 getrlimit(), then 192: attempts to increase the soft limit to 100Mb using setrlimit(). You must 193: do this before calling pcre[16|32]_exec(). 194:  195:   196: Changing stack size in Mac OS X 197:   198:  199: Using setrlimit(), 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:  204:   205: AUTHOR 206:   207:  208: Philip Hazel 209:   210: University Computing Service 211:   212: Cambridge CB2 3QH, England. 213:   214:  215:   216: REVISION 217:   218:  219: Last updated: 24 June 2012 220:   221: Copyright © 1997-2012 University of Cambridge. 222:   223:  224: Return to the <a href="index.html">PCRE index page</a>. 225: 