Re: [pcre-dev] Calculated match recursion stack size

Top Page
Delete this message
Author: Graycode
Date:  
To: pcre-dev
Subject: Re: [pcre-dev] Calculated match recursion stack size
On Wed, 18 Jan 2012, Philip Hazel wrote:

> On Tue, 6 Dec 2011, Graycode wrote:
>
> > This is a feature request to enable PCRE to calculate and tell the net
> > impact on the stack for each recursive call in the internal match()
> > function used by pcre_exec().
> >
> > Below is a modified version of what I've been using for some time.
> > I tried to make this similar to other PCRE code style, hopefully it
> > got close enough to seem familiar. There is still one "//" commented
> > line that should have been removed.
>
> I think I understand your patch, and I understand why you want the
> information, but I'm afraid I don't like the way the patch works.


Thank you for any consideration. There is no pressing need for it,
this is something I can just keep doing on my own.


> 1. It uses static variables. These are a no-no because they are not
> thread safe.


There is 2 static variables, one is thread safe and the other is not.
The content of the static variable 'X_Calc_StakSize' is neither
referenced nor altered. The patch uses the value of its address as a
flag to indicate whether the call to match() is a special request for
the stack size or whether it's a normal processing call. It could
have used the address of the match() function itself, or any other
unique thing. Testing for an address of something seemed like a fast
way to make a distinct determination.

The other static 'ptr_StakPrev' is not thread safe. It holds the
address of a stack variable between the two calls of match(). The
effect on the stack between the two match() is what is being measured.
Honestly at the time I couldn't determine an easy way to accomplish
that without using a static. Perhaps you can think of something
better.

My program makes the call to get the PCRE stack size when starting up
and readying things for RegEx. By only calculating the PCRE stack
effect at start-up it's bypassing any thread safety issue. That
method probably won't be satisfactory for other people though.


> 2. I don't understand the use of #ifdef PCRE_CONFIG_MATCH_RECURSION_STACK
> because you have defined that macro, so the #ifdef will always be true.


Sorry, that's a carry-over from the code I've been using to do this.
When there's a new release of PCRE I manually re-apply the changes to
my copy. The #ifdefs help to locate where changes are needed and to
help identify what's part of this functionality. If I sense a possible
screw-up on my part then I could comment out the #define and rebuild
without the patch getting compiled.


> 3. I am not at all sure this should be a PCRE_CONFIG_xxx thing because
> you can't change it by a config option.


No it can't be changed. I used PCRE_CONFIG_xxx because the request for
stack calculation didn't seem to belong in pcre_fullinfo() and it didn't
seem worth adding a mew API. So I piggy-backed it on pcre_config().
In retrospect a new dedicated API might have been a good choice.


> 4. If somebody links statically with pcre_config(), it will always drag
> in pcre_exec(), even it they don't use that function in their
> application, making their binary a lot larger than it should be.


You're right. I hadn't thought anyone would use pcre_config() without
having pcre_exec().


> 5. There are places in pcre_exec() that have code like this:
>
>       for (fi = min;; fi++)
>         {
>         int slength;
>         RMATCH(eptr, ecode, offset_top, md, eptrb, RM14);
>         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
>         if (fi >= max) RRETURN(MATCH_NOMATCH);
>         if ((slength = match_ref(offset, eptr, length, md, caseless)) < 0)
>           {
>           CHECK_PARTIAL();
>           RRETURN(MATCH_NOMATCH);
>           }
>         eptr += slength;
>         }
>       /* Control never gets here */

>
> I cannot claim to know very much about the way stacks work in modern
> compilers, but it seems to me that extra stack is needed for the slength
> variable, and so the stack used before the call to RMATCH at that point
> will be larger than at other points where there is no such declaration.
> If I am right, it means that there is no single size that applies to all
> calls. I won't be surprised to learn I am wrong, however.


You're not wrong at all.

> 6. I am not sure why your code allows for two additional ints. Where do
> they come from?


The answer is in your question #5. There was another place where I saw
two ints on the stack above RMATCH() where #5 shows just one int.


> After all those negatives, here is something positive: I *think* that
> perhaps the way to approach this is to arrange for the "special" way of
> calling pcre_exec() to be indicated differently, so that it can be
> called directly from pcretest (or any other program) without going via
> pcre_config. Unfortunately, there are very few option bits left, so I
> would not want to use one of them on this rather rare and specialist
> feature. However, something magic like "all option bits set" might be a
> possibility. Then, in addition, the caller would have to pass over a
> pointer to memory that fulfils the function of your static variable.
> This could be cast via the regex argument, I suppose, though that's a
> bit messy. The function would yield the answer.
>
> Safety check: if all option bits are set, check that the regex pointer
> does NOT point to a plausible regex, and that extra, subject, and offset
> pointers are all NULL, and length, start_offset, and offset count are
> all zero.


In the patch I was using the address of a static variable as being the
equivalent of an option bit. That made it a unique vector for getting
the stack size without a chance of interfering with the "real" work of
matching expressions.

Hopefully there is much better ways than what I did in that patch. It
would be terrific if you can someday come up with something that is
supportable.


> I am not particularly happy about this, but I will do some experiments.


This may be low priority for many other PCRE users, otherwise someone
would have asked for it long ago. I happen to want a safe (at least
a very close accuracy) measurement of each recursion's stack in order
to then throttle PCRE's recursion_limit and avoid the possibility of a
stack fault.

Building 64-bit applications is becoming more common.  Yet in Windows
the default stack is 1 Meg for both 32 and 64 bit programs.
       (insert popular anti-Windows humor here)*
Perhaps some will only be able to recurse about half the depth of
32-bit builds unless they address the stack in some fashion.  It may
take more than just upping a linker option when PCRE is being invoked
from threads (whose default stack is 1 Meg too).


Maybe I'm too "old-school" in feeling the need to do stuff like this.


Regards,
Graycode