It is perhaps needlessly complex. Let's try to see if we can get it working using an external stack for only the backtracking information (the thing that can grow unbounded), and keep the system stack for small temporary data. It'll cost us another register, to keep an extra stack pointer, push and pop are no longer atomic operations, and we need to check a second "stack guard" limit, but the overhead should still be limited.
We can start the extra stack fairly small, but we'll still need to grow it for some regexps. /L On Wed, Jan 7, 2009 at 10:56 AM, Erik Corry <[email protected]> wrote: > > > On Wed, Jan 7, 2009 at 1:46 AM, <[email protected]> wrote: >> >> I am reverting Erik's LGTM. I am sorry but I honestly think this change >> is on a road to big train wreck. We should discuss in person as I think >> there are multiple issues not just with this change but with some >> assumptions that lead to this. >> >> Here are some of my concerns: >> - The excessive use of memory by doubling the space (and not giving back >> the previously allocated area). At least there is a maximum cutoff. > > As you note below we give the allocated area back at the earliest > opportunity. We could change the code to be less agressive in increasing > the stack size but we definitely want to keep a geometric algorithm of some > sort in order to keep time and space complexity linear. We don't have and > don't want a stack in several sections linked together. > >> - Why does the backtracking stack need to use esp? > > We did this to save a register, to use the fast stack-based instructions in > the instruction set and because PCRE showed dramatically better performance > when using the machine stack. Our experience from other VMs was that moving > esp to an allocated stack area worked fine, but as far as I recall we didn't > use purify, valgrind and similar tools on that project, so there may be > pitfalls we don't know about. > >> - Why does only PushBacktrack check the stack limit and not other >> pushes? > > The amount of data that can be pushed without a PushBacktrack can be > limited. For non-pathological regexps it's very limited. I think we can > add handling for pathological regexps to make sure we don't hit the guard > page. > >> - The design should be based on equally sized stack segments to avoid >> exponential-sized problems. > > See above. > >> >> - How will GC deal with the fact that you have disjoint stack segments? > > Nothing on the regexp stack is interesting for the GC so the GC ignores it > like it does C stack frames. It's all just integers. And we don't really > have disjoint stack segments. There's the normal stack and at some points > there's one active regexp stack which the GC can ignore. > >> >> Has this part been tested at all? > > There's no way to trigger a GC during regexp execution unless you switch > threads. Switching threads during GC isn't tested at the moment but should > work. The interesting issue there will be that the regexp code buffer > moves, and this aspect of it is independent of whether we use the esp stack > for regexps. > >> >> -Ivan >> >> >> Also, I spent an unnecessary amount of time because of a lack of >> comments in the change itself and the surrounding code. >> >> >> http://codereview.chromium.org/16538/diff/206/209 >> File src/regexp-macro-assembler-ia32.cc (right): >> >> http://codereview.chromium.org/16538/diff/206/209#newcode69 >> Line 69: * - register n ebp[-4*(n+1)] >> On 2009/01/06 14:47:05, Erik Corry wrote: >>> >>> I would prefer n - 1 here which would correspond to num_registers. >> >> I agree with Erik to change it to either >> - register (num_saved_registers_ - 1) ebp[-4*num_saved_registers_] >> or >> - register 1 ebp[-4] >> - register 2 ebp[-8] >> - register num_saved_registers_ ebp[-4*num_saved_registers_] >> >> http://codereview.chromium.org/16538/diff/206/209#newcode91 >> Line 91: * the existing stack to the new area. >> I really dislike unbounded exponential algorithms. We have run into >> issues with this just recently causing us to run out of address space. >> Also it is left unclear what happens with the embedded esp pointers in >> the copied stack. Are they adjusted or is the old stack kept around? > > There are no embedded esp pointers in the copied stack. > >> >> http://codereview.chromium.org/16538/diff/206/209#newcode104 >> Line 104: * | stack-limit = stack-bottom + 1KB >> On 2009/01/06 14:47:05, Erik Corry wrote: >>> >>> not always 1kbyte >>> >>> I prefer not to abbreviate byte. For 1024 I prefer either Ki which is >> >> correct >>> >>> or k which is correct for 1000. K seems neither fish nor fowl. >> >> Nitpicks! >> >> But I would like to know how you determined the 1KB value for the slack? >> >> There are bigger problems here. For example: Which way are low and high >> addresses? >> >> http://codereview.chromium.org/16538/diff/206/209#newcode115 >> Line 115: * are moved. >> This approach is very confusing. Basically ebp relative data stays in >> the old stack, whereas esp relative data is in the new page. This not > > True. > >> >> only leads to redundancies and potential update problems where one area >> of the stack is not kept up to date with the other copies, but it also > > Not sure what you mean here. All data is referenced by esp or by ebp, never > by both. > >> >> uses a lot more memory (first extension double, second extension 5x, >> third extension 7x, ...). > > I don't see how you are getting these figures. Even if we didn't free old > segments we would never use more than 4x. With freeing old segments we > never use more than 3x. (For almost all regexps we will never have to > allocate any new space since the machine stack will be easily big enough.) > > >> >> http://codereview.chromium.org/16538/diff/206/209#newcode699 >> Line 699: __ mov(ecx, stack_page_location()); >> Please explain in some detail what this piece of code is doing. Comments >> are absolutely necessary when reading assembly. Here is what I can >> gather from the context: >> >> // Tear down the stack frame. >> // If this stack frame is the last frame on the irregexp >> // extension stack then tear down the frame and then call >> // into C code to exit the extension stack. >> >> http://codereview.chromium.org/16538/diff/206/209#newcode700 >> Line 700: __ leave(); // Switches to original stack before freeing new >> stack area. >> Before potentially freeing the new stack area. >> >> http://codereview.chromium.org/16538/diff/206/209#newcode706 >> Line 706: // ExitStack(stack_page); >> Please provide a real comment describing what you are about to do. You >> are saving the result of this function across the call to C code, then >> you are aligning the stack (why?), then you call >> "ExitStack(stack_page);", last you are restoring the result to proceed >> with exiting from this function. >> >> http://codereview.chromium.org/16538/diff/206/209#newcode754 >> Line 754: __ pop(esp); // This might switch to another stack area! >> What if FrameAlign did introduce holes due to alignment? Does this pop >> really pop what you expect it to? My guess is no. >> >> http://codereview.chromium.org/16538/diff/206/209#newcode767 >> Line 767: __ mov(eax, -1); >> Please do not use a magic constant here. This should be some >> kRegExpStackOverflow value. >> >> http://codereview.chromium.org/16538/diff/206/209#newcode942 >> Line 942: int32_t* esp) { >> Please use stack_pointer or something similar to distinguish from the >> esp Register. Makes for very confused reading otherwise. >> >> Also this function confuses stack_top (which generally is what the stack >> pointer points to) with stack_end and so on. Generally I have seen this >> naming: >> >> ADDR 0 >> ... >> stack_begin (beginning of allocated stack area) >> ... (unused stack area) >> stack_top (location pointed to by the stack pointer) >> ... values on the stack ... >> stack_bottom (stack values end here) >> ... data structure describing the stack ... in this has StackPageHeader >> stack_end (end of allocated stack area) >> ... >> ADDR Infinity >> >> By also documenting it this way the offsets become natural when drawing >> the stack as structs will have the correct offsets. >> >> http://codereview.chromium.org/16538/diff/206/209#newcode966 >> Line 966: new_size += page_size * 2; // make room for guard page. >> This looks like you are adding two guard pages. If not please explain. >> >> http://codereview.chromium.org/16538/diff/206/209#newcode977 >> Line 977: &(reinterpret_cast<StackPageHeader*>(new_stack + >> allocated_size)[-1]); >> I find this a confusing construct. Negative array indices are alway hard >> to grok. How about: >> // The stack page header is at the bottom (high address) of the newly >> allocated stack. >> StackPageHeader* new_header = >> reinterpret_cast<StackPageHeader*>(new_stack + allocated_size - >> sizeof(StackPageHeader)); >> >> http://codereview.chromium.org/16538/diff/206/209#newcode1003 >> Line 1003: *esp += new_stack_top - stack_top; >> Why so complicated? Shouldn't this just be: >> *esp = new_stack_top - stack_size? >> >> http://codereview.chromium.org/16538/diff/206/209#newcode1016 >> Line 1016: FreeStack(stack_page->previous_stack_page); >> Why is it safe to free the stack pages at this point? Aren't some value >> still pointing into it? >> >> I now understand (wasted 20+ minutes trying to figure it out): You >> cannot deallocate the previous stack when allocating the new one because >> the C code will want to return to it. Then you use the fact that the >> saved esp is "restored" by the calling code by patching it to the new >> value. At this point here you know you switched to the new stack so you >> can drop the old ones. >> >> Comments are NOT optional. >> >> http://codereview.chromium.org/16538/diff/206/209#newcode1024 >> Line 1024: return 1; >> What is this magic number? >> >> http://codereview.chromium.org/16538 > > > > -- > Erik Corry, Software Engineer > Google Denmark ApS. CVR nr. 28 86 69 84 > c/o Philip & Partners, 7 Vognmagergade, P.O. Box 2227, DK-1018 Copenhagen K, > Denmark. > -- Lasse R.H. Nielsen [email protected] 'Faith without judgement merely degrades the spirit divine' --~--~---------~--~----~------------~-------~--~----~ v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev -~----------~----~----~----~------~----~------~--~---
