488733 - Make mark stack resilient to out-of-memory conditions

Status: VERIFIED FIXED

(Tamarin Graveyard :: Garbage Collection (mmGC), defect, P2)

Description

[Tommy Reilly]

1) don't require full realloc, should work with 1 page units
2) free mark stack when not in use
3) do some real world testing to profile real world mark stack growth patterns
4) do reseach on methods of marking w/ growing the mark stack (can we have a fixed mark stack? or change mark algorithms if we can't get more mark stack memory?)

Comment 1

[Lars T Hansen]

At a minimum the GC must be able to complete even if it can't allocate more space for the mark stack.

Segmented mark stack is good (though probably not necessary).

The recursive marker currently leads to excessive pause times and relatively deep call stacks in the worst case and should either be bounded, bounded on small systems, or made non-recursive.  This may require very low per-mark-item overhead to be affordable.

Comment 2

[Tommy Reilly]

> The recursive marker currently leads to excessive pause times 

How?

> relatively deep call stacks in the worst case and should either be bounded, bounded on small systems, or made non-recursive.  This may require very low per-mark-item overhead to be affordable.

Sure this could happen in a pathological edge case, I'd prefer to handle it separately from the real world problem of the GCStack doing heap allocations when memory is out.

Comment 3

[Lars T Hansen]

(In reply to comment #2)
> > The recursive marker currently leads to excessive pause times 
> 
> How?

I wrote this up - at least in part - in my mmgc audit, but the trick is that the work in a recursive mark is not accounted for in the timeout check for mark stack work.  So if you pack 100 pages with small objects all pointing to one another - and this is doable from actionscript, all it takes is a list or tree - then the marker can go away for a good long while on a slowish device.  I meant to post a demonstration of this when I was doing the policy benchmarking but it got pushed down on the to-do list.  I did observe it in practice, at least I found no other explanation for it at the time.

> > relatively deep call stacks in the worst case and should either be
> > bounded, bounded on small systems, or made non-recursive.  This may
> > require very low per-mark-item overhead to be affordable.
> 
> Sure this could happen in a pathological edge case, I'd prefer to handle it
> separately from the real world problem of the GCStack doing heap allocations
> when memory is out.

"Pathologicial edge case" == crash if you are limited to a 50KB stack and the marker uses 90KB, as it may in the worst case (the stack frame for MarkItem is not small, unfortunately).  It's a bug, it needs to be fixed; the stack budget for the GC is much smaller than its current worst-case behavior.  But I can further split this bug into two if you like, the two problems are related but not really dependent.

Comment 4

[Lars T Hansen]

Attachment: Segmented mark stack (no other changes), v1

A pretty straightforward reengineering to use one-page chunks for the mark stack rather than a single array-based stack.

The only places where this could be slower than the old code are in Pop(), which needs to check for underflow in the current chunk, and in Count(), which has to perform a simple computation of the size (three loads and two adds).  Measurements show no slowdown in practice on heap_stress.as.

Apart from the code review I'd like to know two other things:

One is whether it's OK for me to remove the initialization clauses in the nullary constructor for GCWorkItem, see the comment that's introduced by this patch.

The other is whether the code for DRC history needs to be supported.  Right now it's #if'd out in the code, but I've preserved the necessary functionality in this rewrite.  However, it would be my preference to get rid of the templating of GCStack and specialize it for GCWorkItem, and I would do so if the DRC history functionality can be removed completely.

Comment 5

[Tommy Reilly]

Comment on attachment 377672 [details] [diff] [review]
Segmented mark stack (no other changes), v1

I assume manifest and vcproj updates will accompany push, otherwise looks good.  As it see it this addresses:

1) mark stack never shrinking
2) realloc/copy overhead
3) potential multiple contiguous page frag issues

This data structure might work well for the ZCT too.

Comment 6

[Lars T Hansen]

Tommy, ping re: the two other questions I asked in the submission.

Comment 7

[Tommy Reilly]

Re: init clauses.   So you are asserting that its okay for these values to take on undefined values because we always initialize them before use?   I'll buy that, in DEBUG builds these will be poisoned in the heap case and also in the stack case which will help catch broken usage.  

Re: DRC history.   Rishit actually has a patch to fix the DRC history (it was bit rotting due to profiler work).  Can we leave it #if 0'd until that patch lands?

Which begs the question, why the desire to de-template GCStack?  Performance?  Template allergies?

Comment 8

[Lars T Hansen]

(In reply to comment #7)
> Re: init clauses.   So you are asserting that its okay for these values to take
> on undefined values because we always initialize them before use?   I'll buy
> that, in DEBUG builds these will be poisoned in the heap case and also in the
> stack case which will help catch broken usage.  

OK.  As you saw from my mail elsewhere the point may be somewhat moot with GCC (since it can't get rid of the array init loop that I was trying to get rid of, even if the constructor is nullary) but I may still change this, then.

> Re: DRC history.   Rishit actually has a patch to fix the DRC history (it was
> bit rotting due to profiler work).  Can we leave it #if 0'd until that patch
> lands?

No problem.

> Which begs the question, why the desire to de-template GCStack?  Performance? 
> Template allergies?

Both, as it turns out.

Performance: If I knew that GCStack was only used with values for T that required no initialization then allocation of a segment could be optimized further.  (Allocate one block and use the uninitialized tail for the array memory).  That benefit is possibly not measurable, though.

Cleanup: I don't mind the template per se, but if the type were not templated then I don't have to worry about how it may be used, and some syntactic cruft disappears.

Keeping the current code is no big deal at all, I was just looking for opportunities to throw out code.

Comment 9

[Tommy Reilly]

A DRC history mechanism is poor justification for any loss of performance in the mark stack.  When BasicList lands maybe history could use that (it wants a small list, not a big stack) and free up this specialization.

Comment 10

[Lars T Hansen]

(In reply to comment #9)

Sounds like a plan.  In that case I probably won't change the constructor for GCWorkItem as the entire problem with a non-empty constructor for it will not be relevant for the mark stack.

Comment 11

[Lars T Hansen]

Comment on attachment 377672 [details] [diff] [review]
Segmented mark stack (no other changes), v1

redux changeset 1e107d040149 (with vcproj and manifest additions and one workaround for vc++ template issues)

Comment 12

[Lars T Hansen]

Attachment: Mark stack overflow handling, v1

This appears to work.  Mostly I'd like a preliminary review so that I can address issues or answer questions about the approach, while I keep testing & thinking.

Performance is better than I expected: on my Mac, heap_stress.as slows down by only 5% when given a single 4KB mark stack segment, normally it needs three to run without mark stack overflow.  (This is hardly conclusive, but as expected the overflow handler seems to converge rapidly.)

Comment 13

[Lars T Hansen]

Attachment: Stress test for mark stack overflow

Shows the overflow handling in the worst possible light: chained list of large arrays pointing to unique objects; as each array element is pushed onto the mark stack before any is scanned, the resulting behavior with a short mark stack is approximately quadratic in the heap size.

(The correct fix for that problem is to avoid pushing all array elements or indeed all the constituents of large objects, but to keep the object plus an index into the object on the mark stack.  If we care.)

Comment 14

[Lars T Hansen]

Attachment: Another stress test

Iterative instead of recursive (stresses different code); checks that the data structure is not corrupted, too.

Comment 15

[Lars T Hansen]

Attachment: Mark stack overflow handling

Cleaned up and tested some more; I consider this ready for review / integration.

Later, when the PleaseAlloc API becomes available, we need to make a small change to hook into that, see comment in GCStack.cpp.

Comment 16

[Tommy Reilly]

Comment on attachment 378872 [details] [diff] [review]
Mark stack overflow handling

A quick review was done, very nice!   We should brain storm on how to test this in the player.  I'd like a way to pound it affectively.  

So far all I got is a floating HeapLimit that sets the heap limit to some small % larger than the minimum size required for the app not to hit the abort state, I think edwin could use that too.  How's that sound?

Comment 17

[Lars T Hansen]

(In reply to comment #16)
> (From update of attachment 378872 [details] [diff] [review])
> We should brain storm on how to test this
> in the player.  I'd like a way to pound it affectively.

Agree, ideally we would test it with heap_stress and my test cases in the shell, but also somehow in the player.

> So far all I got is a floating HeapLimit that sets the heap limit to some
> small % larger than the minimum size required for the app not to hit the
> abort state, I think edwin could use that too.  How's that sound?

It would at least be somewhat likely to tickle the overflow handling, but I'm worried about whether we're guaranteeing anything.  As you saw, I had some debug code in GCStack.cpp that limits the number of mark stack segments.  We could expose this code at very low cost in debug builds for sure, but maybe even in release-debugger builds.  (The cost in release builds would be close to zero but I don't know if it's a good idea to expose it there - opinions?)  Then some configuration var (in mmgc.cfg or whatever) could be used to set the number of segments low, 1 being a good value.  That way, we're guaranteed some testing, which makes me feel a little safer.

Comment 18

[Lars T Hansen]

Comment on attachment 378872 [details] [diff] [review]
Mark stack overflow handling

redux changeset:   1923:790e14872904

Comment 19

[Lars T Hansen]

Attachment: Last piece of the puzzle: use PleaseAlloc to allocate mark stack segments

Trivial patch.

Comment 20

[Lars T Hansen]

redux changeset 1965:47e44de0df74

Comment 21

[Chris Peyer]

Resolved fixed engineering / work item that has been pushed.  Setting status to verified.