663508 - Add FixedMalloc::FindBeginning

Status: RESOLVED FIXED

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

Description

[Felix S. Klock II [:pnkfelix, :fklock]]

Given an address managed by a block allocated by (any!) FixedAlloc, we can find the block's beginning via FixedAlloc::FindBeginning (at least in debug builds).

Given an address within an object allocated by a GC, we can find the object's beginning via GC::FindBeginnningFast.  (And there's also GC::FindBeginningGuarded for when you don't know if the address points into managed memory.)

It makes sense for FixedMalloc to provide similar functionality, if there is a need for it.

Bug 663177 and Bug 663386 provide the necessary motivation to add the functionality to FixedMalloc.

Comment 1

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: patchA: extend GCHeap::AddrToBlock to handle far addresses

[Re]discovered that GCHeap::AddrToBlock does not handle addresses that are more than kBlockSize words away from the start of the block (I'm calling these "far addresses" in the context of this ticket, until someone else suggests a better or more standard terminology).

FixedMalloc::FindBeginning is layered on top of GCHeap::AddrToBlock, so it seems if we want FixedMalloc::FindBeginning to be robust, then we need GCHeap::AddrToBlock to work even for far addresses.

This patch is an attempt to add that to GCHeap::AddrToBlock, by walking back up to the first block of nonzero size.  I still need to thoroughly vet the GCHeap code to ensure that this is sufficient.

Comment 2

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: patchB: FixedMalloc::FindBeginning

1. Used a snippet from GC::findGCGraphBeginning as basis for FixedMalloc::FindBeginning.  But I also fixed Bug 663386 in this code, which made the logic more expensive (more searching).  Looking at it now, I might be just as well off lifting the traversal over m_allocs to the top of the function, before ever invoking GCHeap::AddrToBlock.

2. Since FixedMalloc::FindBeginning may be inefficient (it has to do a lot of ugly searches), I added FixedMalloc::FindBeginningKnownSize that leverages the size of the object containing the address to dispatch more efficiently to FixedAlloc or GCHeap accordingly.  (A reasonable person might ask when would you know the overall size but not know the start of the object; for an answer in the form of a use case, see Bug 663177.)

3. Revised #if's so that FixedAlloc::QueryOwnsObject is visible #ifdef MMGC_HEAP_GRAPH and so that FixedAlloc::FindBeginning is visible #ifdef DEBUG.

4. Drive-by fix to FixedAlloc::FindBeginning to return GetUserPointer(mem) instead of mem.  (I still need to check that this does not break the black-list functionality.)

Comment 3

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: selftestM: tests FindBeginning and FindBeginningKnownSize

Selftest.  It works sufficiently well that its failures motivated patchA (attachment 553898 [details] [diff] [review]).

Comment 4

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 538898 [details] [diff] [review]
patchA: extend GCHeap::AddrToBlock to handle far addresses

I figure Tommy might be able to enlighten me as to whether this is a non-starter or not.

(I'm only asking for feedback, not a review, because I won't push this until I do a survey of GCHeap to sanity check my logic here.  But maybe Tommy will be able to tell me quickly that its a bogus idea so that I won't waste time doing a survey.)

Comment 5

[Tommy Reilly]

Comment on attachment 538898 [details] [diff] [review]
patchA: extend GCHeap::AddrToBlock to handle far addresses

Why index > 0 tested in loop? Otherwise looks fine.

Comment 6

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: patchC: sanity-check blocks for far addresses have zero size (at allocation time)

This patch is meant to go hand-in-hand with patchA.  It checks the invariant that patchA is relying on (that the blocks after the first in a given allocation have size == 0 from the get-go).

The selftests all run without the assertion in this patch firing.  so that is a good sign.

Comment 7

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #5)
> Comment on attachment 538898 [details] [diff] [review] [review]
> patchA: extend GCHeap::AddrToBlock to handle far addresses
> 
> Why index > 0 tested in loop? Otherwise looks fine.

Because I did not want to go beyond the first block for the region in my search backwards.  Thinking on it now, the invariants should ensure that we always run into a non-zero size block before index ever goes negative; I'll revise the patch to convert the test into an assertion.

Comment 8

[Tommy Reilly]

> I'll revise the patch to convert the test into an assertion.

aren't size_t's unsigned?  Seems like AddrToRegion guarantees that item is greater than  region->baseAddr.

Comment 9

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #8)
> > I'll revise the patch to convert the test into an assertion.
> 
> aren't size_t's unsigned?  Seems like AddrToRegion guarantees that item is greater than region->baseAddr.

Yes, we're definitely going to start the search at some address greater than the region->baseAddr.

Your point about size_t's being unsigned is well-taken; an assertion that index is non-negative would be vacuous.  Of course it would still be bad if the loop ever decrements the index when the index == 0; the search should stay within the bounds of the single region identified by AddrToRegion.

(Elaboration: An assertion that (index == 0 implies block->size > 0) would encode a simple invariant that in an ideal world would be immediately apparent from the data structure: namely, that the header block for the allocation (which may fall at the start of the region, or may be somewhere further down in the region, but must be somewhere in the region) must have non-zero size, and if that invariant were ever broken, then things would be completely bonkers.  But the GCHeap code is hairy enough (Bug 563889) that I think its not a bad thing to make explicit in an assertion.  I can't assert the exact thing I want (because if I knew where the header block was, then I wouldn't be walking backwards to find it in the first place), but I can at least put in a coarse approximation.)

Comment 10

[Steven Johnson]

> an assertion that index is non-negative would be vacuous

...and would actually generate a warning-treated-as-error on some compile configs. Fix aggressively.

Comment 11

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #10)
> > an assertion that index is non-negative would be vacuous
> 
> ...and would actually generate a warning-treated-as-error on some compile
> configs. Fix aggressively.

In case its not clear: (1.) the assertion being discussed is still hypothetical, there's no code for it yet, and (2.) the test expression under discussion was never (index >= 0), it was (index > 0), which remains meaningful for unsigned type.  Still, thanks for the warning.  :)

Comment 12

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #2)
> 
> 2. Since FixedMalloc::FindBeginning may be inefficient (it has to do a lot
> of ugly searches), I added FixedMalloc::FindBeginningKnownSize that
> leverages the size of the object containing the address to dispatch more
> efficiently to FixedAlloc or GCHeap accordingly.  (A reasonable person might
> ask when would you know the overall size but not know the start of the
> object; for an answer in the form of a use case, see Bug 663177.)

This was nonsense reasoning; the GCRoot constructor doesn't know the size; it asks FixedMalloc to derive it from the 'this' pointer.  But the whole point of adding Bug 663177 is that we cannot trust the 'this' pointer!

So, I no longer think there are any use-cases for FixedMalloc::FindBeginningKnownSize.  I'll remove it from the patch.

Comment 13

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #7)
> (In reply to comment #5)
> > Comment on attachment 538898 [details] [diff] [review] [review] [review]
> > patchA: extend GCHeap::AddrToBlock to handle far addresses
> > 
> > Why index > 0 tested in loop? Otherwise looks fine.
> 
> Because I did not want to go beyond the first block for the region in my
> search backwards.  Thinking on it now, the invariants should ensure that we
> always run into a non-zero size block before index ever goes negative; I'll
> revise the patch to convert the test into an assertion.

D'oh, the loop was supposed to be decrementing index as it went!  No wonder Tommy was confused by the test.

Comment 14

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: patchA': extend GCHeap::AddrToBlock to handle far addresses

Comment 15

[Tommy Reilly]

I'm having second thoughts about this, almost all callers of AddrToBlock are passing a pointer to the beginning of a GCHeap allocation.   I wonder if we should have a new API ie GCHeap::FindBeginning that does this searching and then pass the base pointer to AddrToBlock and not change any of the existing callers.   Might make the code more robust in the face of impending refactorings.

Comment 16

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #15)
> I'm having second thoughts about this, almost all callers of AddrToBlock are
> passing a pointer to the beginning of a GCHeap allocation.   I wonder if we
> should have a new API ie GCHeap::FindBeginning that does this searching and
> then pass the base pointer to AddrToBlock and not change any of the existing
> callers.   Might make the code more robust in the face of impending
> refactorings.

I'm cool with that idea, I'll revise the patch.

Comment 17

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 539186 [details] [diff] [review]
patchA': extend GCHeap::AddrToBlock to handle far addresses

( cancelling review to address comment 15 )

Comment 18

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #16)
> (In reply to comment #15)
> > I'm having second thoughts about this, almost all callers of AddrToBlock are
> > passing a pointer to the beginning of a GCHeap allocation.   I wonder if we
> > should have a new API ie GCHeap::FindBeginning that does this searching and
> > then pass the base pointer to AddrToBlock and not change any of the existing
> > callers.   Might make the code more robust in the face of impending
> > refactorings.
> 
> I'm cool with that idea, I'll revise the patch.

Filed as Bug 664140.

Comment 19

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 539186 [details] [diff] [review]
patchA': extend GCHeap::AddrToBlock to handle far addresses

Patch A', i.e. attachment 539186 [details] [diff] [review] has been obsoleted by the patch attached to Bug 664140

Comment 20

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: patchB': FixedMalloc::FindBeginning

Revised patchB so that:

* FindBeginning and the functions it invokes are exposed in all compile-modes, since we are going to be using this functionality in Release mode (Bug 664137).

* Lifted traversal over m_allocs array to toplevel of FixedMalloc::FindBeginning, since I suspect that it was not saving much if any execution time in the common case to be doing the AddrToBlock lookup first.

Comment 21

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: selftestM': tests FindBeginning

Revised the selftest to test only FixedMalloc::FindBeginning (since I have removed FindBeginningKnownSize) and to do the selftest unconditionally since the function is now provided regardless of the MMGC_HEAP_GRAPH and DEBUG preprocessor symbol settings.

Comment 22

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: patchB'': FixedMalloc::FindBeginning[AndSize]

Revised patchB' to add a new FindBeginningAndSize variant, following a suggestion of Tom's from Bug 663491, comment 7.

This work actually uncovered an additional potential source of "running off the end" for Debugger builds: FixedAlloc::Size (which is what GCRoot's size inference usually boils down to, via FixedMalloc::Size) does not subtract off DebugSize().  I *think* that means that the constructed GCRoots will over-estimate their own size (even more than they already do since they must round-up their size to the corresponding block size for the FixedAlloc in question).  Really interesting.  I'm looking forward to getting rid of these roots (or making them exactly traced).

Anyway, for now this discovery is left as a note above a commented-out assertion in the newly added FixedMalloc::FindBeginningAndSize (and also the new function returns the size with DebugSize stripped off, since I think that's the right thing to do; but this definitely warrants review).

Comment 23

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: selftestM'': tests FindBeginning[AndSize]

Expanded the selftest again, this time to cover FindBeginningAndSize.

I'm concerned about the somewhat hacked-in rounding up of the provided sz to whatever the size class is supposed to be; I'm a little worried that I might be writing the test to fit the code, particularly with respect to the fact that I am manually adding DebugSize() to sz when determining the expected result from LargeSize().  But the existing documentation for FixedMalloc::LargeSize() are not sufficiently clear about whether they include DebugSize() or not.  :(

Comment 24

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: patchB''': FixedMalloc::FindBeginning[AndSize]

An attempt to get started on Bug 664137 unveiled a problem with this patch: I have to discount the DebugSize() from the invocation of LargeSize().  (See again my note at the end of comment 23.)

In other words, I need to make FindBeginningAndSize() compatible with what FixedMalloc::Size returns; otherwise my in-progress patch for Bug 663508 hits the assertion:
    GCAssert(!IsPointerToGCPage((char*)object + size - 1));
in GC::MarkRoots()

This change in turn requires updates to the selftest, to be posted shortly.

Comment 25

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: selftestM''': tests FindBeginning[AndSize]

Revised selftest's computation of what the expected roundup size will be in Debugger builds, namely:

  roundup_actual_size =
      roundUp(sz + DebugSize(), GCHeap::kBlockSize) - DebugSize();

I can actually kind of understand this one (versus my previous version which just seemed ad hoc): of course the GCHeap-allocated segment of memory is going to have to include the debug-information, and of course we will want to strip that debug information off in terms of what size we predict the user wanted.

Comment 26

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 539339 [details] [diff] [review]
patchB''': FixedMalloc::FindBeginning[AndSize]

I've put the patch through its paces (in particular by testing out my patch for Bug 664137).

There's still a remaining task to investigate whether FixedAlloc::Size should be discounting DebugSize, or more broadly, to sanitize the documentation with indications of whether the various size functions are returning RealSize or UserSize (analogous to meanings of GetRealPointer and GetUserPointer).  I would not push this without filing a bug for that.

Comment 27

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 539340 [details] [diff] [review]
selftestM''': tests FindBeginning[AndSize]

I'm happy with the thoroughness of the tests here.  They caught a lot of intermediate bugs as I was working on the code, especially at the edge-cases with/without DebugSize() addition under shell debugger builds.

I'm not as happy with its control structure (the returning of numeric codes is ugly; but it is also reasonably self-contained.  Its just meant to assist if one is stepping through the test in a debugger).

Comment 28

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 539339 [details] [diff] [review]
patchB''': FixedMalloc::FindBeginning[AndSize]

Sandbox builder uncovered Linux warning-as-error failure due to this declaration:

+        const bool FindBeginningAndSize(const void* addr,
+                                        const void* &begin_recv,
+                                        size_t &size_recv);

The 'const' is the problem; consider it removed from the patch in your review.

Comment 29

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: patchB'''': FixedMalloc::FindBeginning[AndSize]

(In reply to comment #28)
> The 'const' is the problem; consider it removed from the patch in your
> review.

Removed bogus 'const' qualifier.  (Why wait when no reviews have taken place?)

Comment 30

[Felix S. Klock II [:pnkfelix, :fklock]]

Comment on attachment 539340 [details] [diff] [review]
selftestM''': tests FindBeginning[AndSize]

Windows really dislikes the machinations I did in allocateVerifyAndFree helper function.  I might as well come up with something more straight-forward before I get this reviewed.  Retracting review request.

Comment 31

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: selftestM'''': tests FindBeginning[AndSize]

Okay, fourth time's the charm.  :)

This is a bit easier to read, too.  (Not as nice as it could be if one were to resolve Bug 663531, although I am now realizing that it may not be feasible to resolve that ticket without using some sort of exception mechanism, yuck.)

Comment 32

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #31)
> Created attachment 539647 [details] [diff] [review] [review]
> selftestM'''': tests FindBeginning[AndSize]
> 
> Okay, fourth time's the charm.  :)
 
The comment above checkLookups is out-of-date; that will be fixed before pushing.
+    // Returns 2 if the second test (of FindBeginningAndSize) fails.

Comment 33

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #31)
> This is a bit easier to read, too.  (Not as nice as it could be if one were
> to resolve Bug 663531, although I am now realizing that it may not be
> feasible to resolve that ticket without using some sort of exception
> mechanism, yuck.)

Never mind this throwaway comment; %%verify turns into a call to verifyPass which is *already* layered atop our exception mechanism.  So this is not an argument against that ticket.

Comment 34

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #26)
> There's still a remaining task to investigate whether FixedAlloc::Size
> should be discounting DebugSize, or more broadly, to sanitize the
> documentation with indications of whether the various size functions are
> returning RealSize or UserSize (analogous to meanings of GetRealPointer and
> GetUserPointer).  I would not push this without filing a bug for that.

Filed as Bug 664715.

Comment 35

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #29)
> Created attachment 539593 [details] [diff] [review] [review]
> patchB'''': FixedMalloc::FindBeginning[AndSize]

Pushed to Serrano.

  tamarin-redux-serrano
  changeset: 6321:3b6a480af8d7
  user:      Felix S Klock II <[e-mail]>
  summary:   Bug 663508: Add FixedMalloc::FindBeginning[AndSize] (r=treilly, sr pending lhansen).
  http://asteam.corp.adobe.com/hg/tamarin-redux-serrano/rev/3b6a480af8d7

Comment 36

[Lars T Hansen]

Comment on attachment 539593 [details] [diff] [review]
patchB'''': FixedMalloc::FindBeginning[AndSize]

My (strong?) inclination is SR- because FixedAlloc::QueryOwnsObject has to iterate across the block list to answer the question - this seems highly inappropriate, my gut feeling is that the block lists can be long in Flash applications.

Can I get some reasoning to back up that decision?

Comment 37

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #36)
> Comment on attachment 539593 [details] [diff] [review] [review]
> patchB'''': FixedMalloc::FindBeginning[AndSize]
> 
> My (strong?) inclination is SR- because FixedAlloc::QueryOwnsObject has to
> iterate across the block list to answer the question - this seems highly
> inappropriate, my gut feeling is that the block lists can be long in Flash
> applications.
> 
> Can I get some reasoning to back up that decision?

I do not understand, what alternative are you suggesting?

(The relatively weak reasoning I employed was that (1.) this was the only reliable mechanism I was able to come up with, and (2.) Tommy asserted that GCRoots are infrequently constructed so the performance impact is hopefully nil.)

Comment 38

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #37)
> (In reply to comment #36)
> > Comment on attachment 539593 [details] [diff] [review] [review] [review]
> > patchB'''': FixedMalloc::FindBeginning[AndSize]
> > 
> > My (strong?) inclination is SR- because FixedAlloc::QueryOwnsObject has to
> > iterate across the block list to answer the question - this seems highly
> > inappropriate, my gut feeling is that the block lists can be long in Flash
> > applications.
> > 
> > Can I get some reasoning to back up that decision?
> 
> I do not understand, what alternative are you suggesting?
> 
> (The relatively weak reasoning I employed was that (1.) this was the only
> reliable mechanism I was able to come up with, and (2.) Tommy asserted that
> GCRoots are infrequently constructed so the performance impact is hopefully
> nil.)

Thinking out loud: one alternative I did consider would be to change the definition of 'QueryOwnsObject(addr)' to look like this:

  FixedAlloc::FixedBlock *b = FixedAlloc::GetFixedBlock(addr);
  return (b->alloc == this);

The problem is that FixedAlloc::GetFixedBlock will return garbage for a non-FixedAlloc-allocated 'addr', and so the 'b->alloc' dereference would be invalid.

Is there some way I could reliably validate the returned address for 'b' before doing the dereference?

Comment 39

[Felix S. Klock II [:pnkfelix, :fklock]]

(Lars: it would be good to know relatively soon if you think I should back-out the changeset from Serrano and find a different approach.  At this point I've landed in TR-serrano, and have been preparing to land in P4 Serrano depot.  But I can hold off and investigate other options if you want me to.)

Comment 40

[Lars T Hansen]

(In reply to comment #37)
> (In reply to comment #36)
> > Comment on attachment 539593 [details] [diff] [review] [review] [review]
> > patchB'''': FixedMalloc::FindBeginning[AndSize]
> > 
> > My (strong?) inclination is SR- because FixedAlloc::QueryOwnsObject has to
> > iterate across the block list to answer the question - this seems highly
> > inappropriate, my gut feeling is that the block lists can be long in Flash
> > applications.
> > 
> > Can I get some reasoning to back up that decision?
> 
> I do not understand, what alternative are you suggesting?

A data structure where lookup is not O(total number of allocated blocks) for every query is the most natural approach I think.  Yes, a lot more work, but the reason QueryOwnsObject was DEBUG-only is that it was known to be inadequate as a general API.  My intent was always to make it better.

I suppose a simple cache might also work (most roots will be registered soon after being allocated) but I don't know that for sure.

> (The relatively weak reasoning I employed was that (1.) this was the only
> reliable mechanism I was able to come up with, and (2.) Tommy asserted that
> GCRoots are infrequently constructed so the performance impact is hopefully
> nil.)

That may be so, though actual data on the root construction frequency in existing FP code and/or the number of blocks probed for each of those constructions would make me sleep more easily.

Anyhow if we're going to keep these new APIs the way they are they will need to be flagged in documentation as potentially slow, so that we don't start calling them willy-nilly.  (Still dangerous.)

Comment 41

[Lars T Hansen]

(In reply to comment #39)
> (Lars: it would be good to know relatively soon if you think I should
> back-out the changeset from Serrano and find a different approach.  At this
> point I've landed in TR-serrano, and have been preparing to land in P4
> Serrano depot.  But I can hold off and investigate other options if you want
> me to.)

Since the API is likely fine we can land what you have, but if I end up rejecting the change as it stands then followup work will be required.

Comment 42

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #40)
> > (The relatively weak reasoning I employed was that (1.) this was the only
> > reliable mechanism I was able to come up with, and (2.) Tommy asserted that
> > GCRoots are infrequently constructed so the performance impact is hopefully
> > nil.)
> 
> That may be so, though actual data on the root construction frequency in
> existing FP code and/or the number of blocks probed for each of those
> constructions would make me sleep more easily.
> 
> Anyhow if we're going to keep these new APIs the way they are they will need
> to be flagged in documentation as potentially slow, so that we don't start
> calling them willy-nilly.  (Still dangerous.)

(In reply to comment #41)
> Since the API is likely fine we can land what you have, but if I end up
> rejecting the change as it stands then followup work will be required.

Okay, I'm cool with all of this.

I'll finish the process of landing it for Serrano, and then I'll start on tasks for the issues you describe: Gather data on how big a problem it might be, and investigate alternative data structures.

(I absolutely agree an O(1) time solution would be preferable.  Maybe I'll scope-creep it up to include Bug 610982.)

Comment 43

[Felix S. Klock II [:pnkfelix, :fklock]]

Attachment: patchD: add stats on root construction and block counts

With this patch, an ATS10 AS3 run of the full automated suite (made up of 26,509 tests) says:

             roots constructed: 10,745

    max block iteration length:  2,680
    min block iteration length:      9
   mean block iteration length:    639
std dev block iteration length:    375.5

In hindsight, maybe I should have tried to gather per-test statistics as well.  (Is it suspect that the average number of roots constructed per-test is less than 1?)

Comment 44

[Lars T Hansen]

My inclination is that the only tests that have really good validity here are actual Flash applications.  Brent has a list on the wiki; a few of those should provide some answers maybe.

Comment 45

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #44)
> My inclination is that the only tests that have really good validity here
> are actual Flash applications.  Brent has a list on the wiki; a few of those
> should provide some answers maybe.

I had already started working through one of the real world test suites before seeing that comment.  I finished that and then looked at Brent's list, which for the most part did not overlap.

From what I can see, Brent's list produces more interesting data than most of the entries on the Real World tests (at least in the suite I chose).  The ATS10 AS3 run seems to be a bit more stressful on average than Brent's test suite is on this particular issue (of GCRoots and the newly added block traversal to find the beginning of each root).

Below is a slice of the data from those runs; I've tried to provide context in the first line by listing the allocation-work, the gc-count, and the peak-occupancy for blocks-heap-allocated at the time of the last gcbehavior sample.

The main conclusion I draw from this is that roots are constructed rarely, as Tommy predicted (especially compared to the number of objects reported by allocation-work).  The average traversal is longer than I would like (I'd be much more comfortable if more of those Mean values were less than 100).

Interesting exceptional cases in the data:
* Cigna Tabbing has a long max block traversal.  (But only 12 roots constructed during the gcbehavior instrumentation, so that's not too worrisome.)
* Crush the Castle 2's Mean block traversal length is large and very close to its Max block traversal length.
* Big Pixel Zombie's block traversal length is a clear outlier.  Note that this is one of the largest benchmarks I ran (its the only one where the GCCount was > 9).
* Water Life has a large number of constructed roots and a large max block traversal.

My immediate plan is to: 
1. finish landing this in the main code base, so TR and TR-serrano match up.
2. switch to working on telemetry, so that we can gather performance data more effectively

(The slice of gathered data follows.)

== BRENTS LIST ==

Checkin App
ObjsAlloc:   320,094 ByteAlloc:  44,791,959 GCCount:  3 PeakHeapBlocks:  7,413
NewRoots:        228 BlocksIter_Max:    118  _Mean:  93

Cigna Tabbing
ObjsAlloc: 4,928,619 ByteAlloc: 331,369,057 GCCount:  5 PeakHeapBlocks: 20,064
NewRoots:         12 BlocksIter_Max:    997  _Mean: 247

Coverflow
ObjsAlloc:   165,134 ByteAlloc:  30,931,041 GCCount:  3 PeakHeapBlocks: 15,863
NewRoots:         17 BlocksIter_Max:     96  _Mean:  40

Flex Datagrid Scroll
ObjsAlloc:   480,184 ByteAlloc:  64,132,693 GCCount:  4 PeakHeapBlocks:  7,698
NewRoots:         12 BlocksIter_Max:    241  _Mean:  71

Crush the Castle 2
ObjsAlloc:   372,945 ByteAlloc:  76,543,977 GCCount:  3 PeakHeapBlocks: 18,183
NewRoots:        260 BlocksIter_Max:    763  _Mean: 664

Mechanism
ObjsAlloc:   647,227 ByteAlloc:  65,534,592 GCCount:  7 PeakHeapBlocks:  7,738
NewRoots:        156 BlocksIter_Max:    215  _Mean:  90

Big Pixel Zombies
ObjsAlloc: 8,457,552 ByteAlloc: 517,668,505 GCCount: 10 PeakHeapBlocks: 34,728
NewRoots:        389 BlocksIter_Max:  7,866  _Mean: 2,298

Top Ten - Moodstream
ObjsAlloc:   287,939 ByteAlloc:  31,212,387 GCCount:  3 PeakHeapBlocks: 13,608
NewRoots:        309 BlocksIter_Max:    691  _Mean: 201

Top Ten - Mono
ObjsAlloc:    90,432 ByteAlloc:  10,393,353 GCCount:  2 PeakHeapBlocks: 46,039
NewRoots:        490 BlocksIter_Max:    199  _Mean:  64

Top Ten - Water Life
ObjsAlloc: 1,551,550 ByteAlloc: 123,696,078 GCCount:  4 PeakHeapBlocks: 21,355
NewRoots:      1,439 BlocksIter_Max:  1,692  _Mean: 264

Top Ten - Get the Glass
ObjsAlloc: 9,855,788 ByteAlloc: 352,634,998 GCCount:  6 PeakHeapBlocks: 25,075
NewRoots:         92 BlocksIter_Max:    443  _Mean: 146

== REAL WORLD TEST SUITE ==

RealWorld/scrolling/mobileMenuScroll_AS2/mobileMenuScrollAS2.swf
ObjsAlloc:    39,800 ByteAlloc:   3,839,038 GCCount:  1 PeakHeapBlocks:  5,315
NewRoots:          4 BlocksIter_Max:     27  _Mean:  18

RealWorld/scrolling/largeTextScroll_Device_FP9_tf.swf
ObjsAlloc:    61,636 ByteAlloc:   9,021,003 GCCount:  2 PeakHeapBlocks:  1,729
NewRoots:          8 BlocksIter_Max:     40  _Mean:  18

RealWorld/scrolling/largeTextScroll_Embed_FP9_tf.swf
ObjsAlloc:    61,171 ByteAlloc:   8,984,830 GCCount:  2 PeakHeapBlocks:  1,825
NewRoots:          8 BlocksIter_Max:     40  _Mean:  18

RealWorld/scrolling/scroll_CJK/Scrolling_FTE_CJK.swf
ObjsAlloc:   170,368 ByteAlloc:  25,803,061 GCCount:  3 PeakHeapBlocks:  4,506
NewRoots:          8 BlocksIter_Max:     40  _Mean:  18

RealWorld/edit/largeTextEdit_Device_FP9_tf.swf
ObjsAlloc:    62,553 ByteAlloc:   9,138,974 GCCount:  2 PeakHeapBlocks:  1,505
NewRoots:          8 BlocksIter_Max:     39  _Mean:  17

RealWorld/xml/xmlParser/bin-release/XmlParser.swf
ObjsAlloc:   203,019 ByteAlloc:  35,089,227 GCCount:  3 PeakHeapBlocks:  4,386
NewRoots:         14 BlocksIter_Max:     40  _Mean:  20

RealWorld/games/AirLogoBalls.swf
ObjsAlloc:   242,472 ByteAlloc:  34,288,741 GCCount:  3 PeakHeapBlocks:  5,297
NewRoots:        302 BlocksIter_Max:     39  _Mean:  16

RealWorld/games/DTD/DesktopTDPro.swf
ObjsAlloc: 1,299,193 ByteAlloc:  89,765,911 GCCount:  3 PeakHeapBlocks:  6,619
NewRoots:          4 BlocksIter_Max:     27  _Mean:  18

RealWorld/games/PushButtonEngine-r189/Build/FlexBuilder/RollyBallGame/bin-release/RollyBallGame.swf
ObjsAlloc: 1,168,636 ByteAlloc: 120,955,018 GCCount:  4 PeakHeapBlocks:  8,105
NewRoots:         25 BlocksIter_Max:    201  _Mean:  73

RealWorld/games/GammaBros/gammaBros_AS2.swf
ObjsAlloc: 1,419,791 ByteAlloc:  85,300,466 GCCount:  2 PeakHeapBlocks:  8,470
NewRoots:         78 BlocksIter_Max:    649  _Mean: 567

RealWorld/highFidelitySites/adobeFlash10/3D/Coverflow.swf
ObjsAlloc:   168,628 ByteAlloc:  31,077,402 GCCount:  3 PeakHeapBlocks: 16,062
NewRoots:         14 BlocksIter_Max:     97  _Mean:  32

http://www.craftymind.com/factory/guimark2/FlashChartingTest.swf
ObjsAlloc:    76,515 ByteAlloc:  10,307,626 GCCount:  2 PeakHeapBlocks:  3,430
NewRoots:          8 BlocksIter_Max:     39  _Mean:  17

http://www.craftymind.com/factory/guimark2/FlashGamingTest.swf
ObjsAlloc:   123,892 ByteAlloc:  59,095,811 GCCount:  3 PeakHeapBlocks:  7,590
NewRoots:          8 BlocksIter_Max:     39  _Mean:  17

http://www.craftymind.com/factory/guimark2/FlashTextTest.swf
ObjsAlloc:    78,764 ByteAlloc:  11,547,169 GCCount:  2 PeakHeapBlocks:  4,657
NewRoots:          8 BlocksIter_Max:     39  _Mean:  17

http://www.craftymind.com/factory/guimark3/bitmap/FlashGame.swf
ObjsAlloc:   327,191 ByteAlloc:  26,407,402 GCCount:  2 PeakHeapBlocks:  2,172
NewRoots:          8 BlocksIter_Max:     39  _Mean:  17

http://www.craftymind.com/factory/guimark3/compute/FlashBoid.swf
ObjsAlloc: 1,385,649 ByteAlloc:  83,739,880 GCCount:  2 PeakHeapBlocks:  1,761
NewRoots:          8 BlocksIter_Max:     39  _Mean:  17

http://www.craftymind.com/factory/guimark3/vector/FlashRipple.swf
ObjsAlloc:   323,560 ByteAlloc:  22,085,097 GCCount:  2 PeakHeapBlocks:  1,871
NewRoots:          8 BlocksIter_Max:     39  _Mean:  17

RealWorld/rendering/countryside.swf
ObjsAlloc:    43,234 ByteAlloc:   4,595,679 GCCount:  1 PeakHeapBlocks:    929
NewRoots:          4 BlocksIter_Max:     27  _Mean:  18

RealWorld/rendering/countrysideBlur.swf
ObjsAlloc:    42,963 ByteAlloc:   4,664,186 GCCount:  1 PeakHeapBlocks:  4,758
NewRoots:          4 BlocksIter_Max:     27  _Mean:  18

Comment 46

[Lars T Hansen]

Hm, I have much larger GC counts for Get the Glass, but (a) I did not skip the intro and (b) I played it for quite some time - usually enough to get jailed twice - but of course that's time consuming.  It's hard to know what the "right" thing to do is for something like that.

Also note re your introductory data, most flash apps seem to have heaps that are 3x-5x larger than the GC heaps (loads of fixedmalloc memory I think) so peak heap blocks may not be the best indicator of how much work the GC should be doing.  Again, hard to know what the "right" datum is.

Comment 47

[Tommy Reilly]

Comment on attachment 539647 [details] [diff] [review]
selftestM'''': tests FindBeginning[AndSize]

I'm leery of the bug # as C++ namespace/class blowing up in our face.  Don't have a better solution though...

Comment 48

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #47)
> Comment on attachment 539647 [details] [diff] [review] [review]
> selftestM'''': tests FindBeginning[AndSize]
> 
> I'm leery of the bug # as C++ namespace/class blowing up in our face.  Don't
> have a better solution though...

Yeah, I'm just following the ad-hoc convention there.  (I think I asked Lars whether he had any better ideas for naming convention and he said that bug id was as good as anything else.)

Or, wait, are you talking about the issue that the namespace and the class both have the same identifier?  *That* is an artifact of how I resolved Bug 604347, but it should be trivial to modify that so that the generated id for the namespace is distinct from the generated id for the class.  Is that what you are concerned about blowing up?

Comment 49

[Tommy Reilly]

No just generally concerned with using bug id's in identifiers and code getting ugly/hard to read.   I mean wouldn't something like ST_FixedMalloc_FindBeginning be better?

Comment 50

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to comment #49)
> No just generally concerned with using bug id's in identifiers and code
> getting ugly/hard to read.   I mean wouldn't something like
> ST_FixedMalloc_FindBeginning be better?

I suppose the bug id is already encoded in the Selftest itself.

I'd balk a bit at a camel-cased filename just because none of the other selftest files do it.  But I have no problem with alpha-renaming the test to ST_fixedmalloc_findbeginning.st

Lars, any objections to that?

Comment 51

[Lars T Hansen]

(In reply to comment #50)
> (In reply to comment #49)
> > No just generally concerned with using bug id's in identifiers and code
> > getting ugly/hard to read.   I mean wouldn't something like
> > ST_FixedMalloc_FindBeginning be better?
> 
> I suppose the bug id is already encoded in the Selftest itself.
> 
> I'd balk a bit at a camel-cased filename just because none of the other
> selftest files do it.  But I have no problem with alpha-renaming the test to
> ST_fixedmalloc_findbeginning.st
> 
> Lars, any objections to that?

I'm fine either way.

Comment 52

[Tommy Reilly]

I'm case agnostic, I just think words are better than #'s in this case.

Comment 53

[Lars T Hansen]

Comment on attachment 539593 [details] [diff] [review]
patchB'''': FixedMalloc::FindBeginning[AndSize]

SR+ but really only for the purposes of making TR and TR-serrano match up on this code.  Given the data you posted I think you should file a bug immediately to follow up on this, because this is the kind of potential performance bottleneck that will be well hidden and which will bite us when we least want it.

Comment 54

[Felix S. Klock II [:pnkfelix, :fklock]]

(In reply to Lars T Hansen from comment #53)
> Comment on attachment 539593 [details] [diff] [review]
> patchB'''': FixedMalloc::FindBeginning[AndSize]
> 
> SR+ but really only for the purposes of making TR and TR-serrano match up on
> this code.  Given the data you posted I think you should file a bug
> immediately to follow up on this, because this is the kind of potential
> performance bottleneck that will be well hidden and which will bite us when
> we least want it.

Filed follow-up as Bug 681388.

Comment 55

[Tamarin Bot]

changeset: 6540:0bdd7ace90ff
user:      Felix S Klock II <[e-mail]>
summary:   Bug 663508: FixedMalloc::FindBeginning code; it is slow (r=treilly, sr=lhansen).

http://hg.mozilla.org/tamarin-redux/rev/0bdd7ace90ff

Comment 56

[Tamarin Bot]

changeset: 6541:27ff0ce12204
user:      Felix S Klock II <[e-mail]>
summary:   Bug 663508: selftest for FixedMalloc::FindBeginning[AndSize] (r=treilly, sr=lhansen).

http://hg.mozilla.org/tamarin-redux/rev/27ff0ce12204