Author: Zoltán Herczeg Date: To: pcre-dev Subject: [pcre-dev] JIT stack FAQ
Hi,
I noticed that the JIT stack handling cause a lot of misunderstanding. It was my fault, I thought the "CONTROLLING THE JIT STACK" part of pcrejit.3 man page was enough. I realized the concept (reasons) of the JIT stack are missing.
Probably the best way to explain this is through questions:
1) Why do we need the JIT stack?
PCRE (and JIT) is a recursive, depth-first engine, so it needs a stack where the local data of the current node is pushed before checking its child nodes. Allocating real machine stack on some platforms are difficult. For example, the stack chain needs to be updated every time if we extend the stack on PowerPC. Although it is possible, its updating time overhead decreases performance. So we do the recursion in memory.
2) Why don't we simply allocate a block of memory with malloc?
Modern OS-es has a nice feature: they can reserve an address space instead of allocating memory. We can safely allocate memory pages inside this address sapce, so the stack could grow without moving memory data (this is important because of pointers). Thus we can allocate 1M address space, and use only a single memory page (usually 4K) if that is enough. However, we can still grow up to 1M anytime if needed.
3) Who "owns" the stack?
The owner of the stack is the user program, not the jit studied pattern or anything else. The user program must ensure:
- If a stack is used by pcre_exec (since it is assigned to the pattern currently runing), that stack must not be used by any other threads (to avoid overwriting the same memory area). The best practice for multithreaded programs to allocate a stack for each thread, and return this stack through the JIT callback function.
- You can free the stack anytime, as long as it will not be used by pcre_exec anymore. When you assign the stack to a pattern, only a pointer is set. There is no refcounting or any other magic. You can free the patterns and stacks in any order, anytime. Just DO NOT call a pcre_exec with a pattern pointing to an already freed stack, that will cause SEGFAULT. (And do not free a stack currently used by a pcre_exec in another thread). The solution for multithreaded programs are above. You can also replace the stack for the patterns as well anytime. You can even free the previous stack before replacing. The only rule is the rule for pcre_exec above.
4) Shall I allocate/free a stack every time before/after a pcre_exec?
No. Too costly. But you could implement some clever idea which release the stack if it is not used in lets say 2 minutes. Or anything else. The JIT callback can help to achive this without keepnig a list of the currently jit studied patterns.
5) Ok the stack is for long term memory allocation. But what happens if a pattern cause stack overflow with the stack of 1M? Is that 1M kept until the stack free? Especially on embedded sytems, it might be a good idea to release memory sometimes without freeing the stack.
There is no API for this at the moment. Probably a function call which returns with the currently allocated memory for any stack and another which allows releasing memory (shrinking the stack) would be a good idea if someone needs this.
6) This is too much of a headache. Isn't there any better solution for JIT stack handling?
No, thanks to Windows... If pthreads would be used everywhere, we could throw out this complicated API.
