663159 - GCRoot doesn't work well with multiple inheritance

Status: RESOLVED FIXED

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

Description

[Steven Johnson]

If you declare a class that inherits from GCRoot as well as other classes:

    class A: public B, public GCRoot, public C

the standard GCRoot constructor will assume the root starts at 'this', which is incorrect, as the 'this' seen by GCRoot's ctor won't necessarily be the same as the 'this' allocated by the subclass. However, the size calculated by FixedMalloc::Size is still correct, so the conservative scanner will read off the end of the object, causing a crash if we happen to be the last block in a page.

Comment 1

[Steven Johnson]

Possible ways to address this:

-- require all GCRoots to be exactly traced. Arguably the best long term solution anyway. 
-- add FixedMalloc::FindBeginning (like GCAlloc::FindBeginning) and have GCRoot call this to recover the proper start point. A bit hacky but less work (short-term) than rewriting conservative roots to be exact. (Also, not clear whether existing FixedMalloc data structures allow efficient implementation of this.)

Ways that WON'T address this:

-- move GCRoot to the front of the inheritance tree. C++ doesn't require any memory layout for MI, so we're at the compiler's mercy here.

Comment 2

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

(I assigned myself thinking I could at least attach the patches related to a short-term solution, but Steven's right that we probably should be discussing the long term solution here.  So I'll just unassign myself but still attach patches if they are fruitful in short-term.)

Comment 3

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

(In reply to comment #2)
> (I assigned myself thinking I could at least attach the patches related to a
> short-term solution, but Steven's right that we probably should be
> discussing the long term solution here.  So I'll just unassign myself but
> still attach patches if they are fruitful in short-term.)

Tommy suggested opening a parallel bug for the short-term responses to the fundamental problem: see Bug 663177.  (So I'll be putting my patches there instead.)

Comment 4

[Dan Smith]

Initially targeting for Anza, but this could be changed after review by Lars.

Comment 5

[Steven Johnson]

Longterm fix can be targeted for Anza, but a short-term fix is required for Serrano.

Comment 6

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

(In reply to comment #5)
> Longterm fix can be targeted for Anza, but a short-term fix is required for
> Serrano.

The short-term fix I'm proposing for Serrano is Bug 663177.  (Such an assertion should serve as a safety net for cases where the compiler is foiling us, at least for debug builds.  There is still the spectre of a compiler that chooses one layout in release-mode and a different layout in debug-mode.)

Comment 7

[Steven Johnson]

(In reply to comment #6)
> The short-term fix I'm proposing for Serrano is Bug 663177.  

It might work, but be wary there -- 663177 is presumably a debug assertion that will check that GCRoot's this matches the allocation start, but we have no way of being certain that the layout in non-debug (optimizer-enabled) builds will match that of debug builds!

Comment 8

[Dan Smith]

We can add a self-test that checks that our assumptions about layout are valid on various builds and platforms, yes?

Comment 9

[Steven Johnson]

(In reply to comment #8)
> We can add a self-test that checks that our assumptions about layout are
> valid on various builds and platforms, yes?

Yes, but the selftest will only be valid if we know we are building with the same compiler + compilation settings -- which is definitely not the case for all permutations of Flash/AIR.

Yes, I realize I'm being paranoid here, but I think a robust, verifiable fix is both desirable and doable.

Comment 10

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

(In reply to comment #7)
> (In reply to comment #6)
> > The short-term fix I'm proposing for Serrano is Bug 663177.  
> 
> It might work, but be wary there -- 663177 is presumably a debug assertion
> that will check that GCRoot's this matches the allocation start, but we have
> no way of being certain that the layout in non-debug (optimizer-enabled)
> builds will match that of debug builds!

True, Dan and I discussed this on the phone a little while ago.  He mused about whether we should enable the hypothetical check temporarily in release builds, in order to catch exactly the scenario you described.


(In reply to comment #9)
> (In reply to comment #8)
> > We can add a self-test that checks that our assumptions about layout are
> > valid on various builds and platforms, yes?
> 
> Yes, but the selftest will only be valid if we know we are building with the
> same compiler + compilation settings -- which is definitely not the case for
> all permutations of Flash/AIR.
> 
> Yes, I realize I'm being paranoid here, but I think a robust, verifiable fix
> is both desirable and doable.

My main worry about doing FindBeginning in the GCRoot constructor is that I don't know what computational cost that will incur on our runtime performance.  Although, as its been said above, exactly-traced GCRoots won't use the conservative tracer and therefore could similarly avoid the FindBeginning cost.  So maybe a hybrid solution of doing FindBeginning just for conservatively-traced GCRoots would be reasonable.

Comment 11

[Steven Johnson]

FWIW, it looks like virtually no existing GCRoots are exactly traced -- LivePoolNode is the only one I could find from a quick scan.

Comment 12

[Steven Johnson]

I wonder if this could be made acceptable as a quickfix for Serrano, *IF* we combine it with some compiletime assertions.

i.e.,

	// make sure HWVideoPlane is first since it is a GCRoot
	class BaseOpenGL3DContext : public HWVideoPlane, public IOpenGLContext, public IGPUBlendTexture {

and then something like...

	BaseOpenGL3DContext:: BaseOpenGL3DContext(...)
	{
		// verify that our "GCRoot" parent starts at the beginning...
		MMGC_STATIC_ASSERT((char*)this == (char*)&this->firstDataMemberInGCRoot);
	}

Although... crap, this still may not work, because GCRoot has virtual methods, so firstDataMemberInGCRoot still won't match 'this'.

Comment 13

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

(In reply to comment #12)
> I wonder if this could be made acceptable as a quickfix for Serrano, *IF* we
> combine it with some compiletime assertions.
> 
> i.e.,
> 
> 	// make sure HWVideoPlane is first since it is a GCRoot
> 	class BaseOpenGL3DContext : public HWVideoPlane, public IOpenGLContext,
> public IGPUBlendTexture {
> 
> and then something like...
> 
> 	BaseOpenGL3DContext:: BaseOpenGL3DContext(...)
> 	{
> 		// verify that our "GCRoot" parent starts at the beginning...
> 		MMGC_STATIC_ASSERT((char*)this == (char*)&this->firstDataMemberInGCRoot);
> 	}
> 
> Although... crap, this still may not work, because GCRoot has virtual
> methods, so firstDataMemberInGCRoot still won't match 'this'.

A STATIC_ASSERT sounds like a great idea.  I can see the problem with the example above, but maybe something like this would work:

STATIC_ASSERT(offsetof(LeafType, firstgcrootmember) == offsetof(GCRoot, firstgcrootmember))

Steven agreed that it has potential; I will investigate whether this would also catch the problem.

Comment 14

[Lars T Hansen]

MI is not / should not be supported for GC classes at all, whether GCRoot or others, and we probably need to verify that it is not being used not just for GCRoot but generally.  (Well, for GCObject we don't care right now because its size is zero, but that may change.)  The GC wants control of layout; even though the C++ spec does not provide the necessary control for SI in all cases we can work with it (this is why GCObject/GCFinalizedObject are split).  For MI it's much worse.

There is a script, utils/gcClasses.as, which probabilistically computes class hierarchies.  (Something Clang/Dehydra based would be better.)  It could be used to check this statically.

Another point is that I dearly want to disentangle FixedMalloc from the rest of MMgc and not require its use for GCRoots.  So that's worth keeping in mind.  One possibility may be to only allow the use of the three-argument constructor, which effectively does the same as outlawing GCRoot and requiring the use of the locking API everywhere.

Comment 15

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

An interesting fact I was not previously aware of, learned from Bug 388070, comment 6:

> if you have a polymorphic object (with a vtable), dynamic_cast<void*> will
> return a pointer to the most-derived object, without knowing the type and
> without requiring RTTI.

GCRoot has a vtable.  The problem is that it needs to be a completely constructed object for this trick to work; i.e. if we invoked a fixup method on GCRoot after it has been completely constructed, then that could be used to support MI.

(I'm not actually interested in making MI work; I was interested in using dynamic_cast<void*>(this) in the GCRoot constructor, but a small C++ experiment illustrated that you cannot use the trick while in the midst of going up the constructor chain.)

Comment 16

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

Attachment: c++ experiment illustrating dynamic_cast<void*>(this)

Illustrates note from comment 15; when I run this, I get:

A::A() this: 0x7fff5fbff610 dyncast: 0x7fff5fbff610
C::C() this: 0x7fff5fbff610 dyncast: 0x7fff5fbff610
A::A() this: 0x7fff5fbff618 dyncast: 0x7fff5fbff618
B::B() this: 0x7fff5fbff618 dyncast: 0x7fff5fbff618
D::D() this: 0x7fff5fbff610 dyncast: 0x7fff5fbff610
A::done() this: 0x7fff5fbff610 dyncast: 0x7fff5fbff610
C::done() this: 0x7fff5fbff610 dyncast: 0x7fff5fbff610
A::done() this: 0x7fff5fbff618 dyncast: 0x7fff5fbff610
B::done() this: 0x7fff5fbff618 dyncast: 0x7fff5fbff610
D::done() this: 0x7fff5fbff610 dyncast: 0x7fff5fbff610

(note the change in how dynamic_cast<void*>(this) is handled between B::B() and B::done().)

Comment 17

[Steven Johnson]

(In reply to comment #14)
> MI is not / should not be supported for GC classes at all, whether GCRoot or
> others, and we probably need to verify that it is not being used not just
> for GCRoot but generally.  (Well, for GCObject we don't care right now
> because its size is zero, but that may change.)  The GC wants control of
> layout; even though the C++ spec does not provide the necessary control for
> SI in all cases we can work with it (this is why GCObject/GCFinalizedObject
> are split).  For MI it's much worse.

Agree 100%. Unfortunately this is historically not existing practice in the Player, and (even worse) new code is being written this way. Apparently we've been mostly getting lucky up to now.

Comment 18

[Steven Johnson]

(In reply to comment #15)
> (I'm not actually interested in making MI work; I was interested in using
> dynamic_cast<void*>(this) in the GCRoot constructor, but a small C++
> experiment illustrated that you cannot use the trick while in the midst of
> going up the constructor chain.)

dynamic_cast<> requires RTTI to be enabled in order to work; as a matter of policy the Player codebase explicitly *disables* RTTI on all compilers where it's possible to do so. So this is not an option.

Comment 19

[Steven Johnson]

(In reply to comment #15)
> An interesting fact I was not previously aware of, learned from Bug 388070,
> comment 6:
> 
> > if you have a polymorphic object (with a vtable), dynamic_cast<void*> will
> > return a pointer to the most-derived object, without knowing the type and
> > without requiring RTTI.

Hmm... let me research this assertion; it's contrary to my understanding, but it wouldn't be the first time I've been wrong.

Comment 20

[Steven Johnson]

So, with all due respect to Mr. Smedberg, I can't find any precedent that suggests that dynamic_cast<> is legal without RTTI enabled.

However, an alternate sneaky trick occurred to me: the old use-a-virtual-method-as-faux-RTTI approach. To wit:

    class GCRoot {
        virtual void* getBasePointer() const { return (void*)this; }
        GCRoot(GC* gc) { gc->AddRoot(getBasePointer(), ...); }
    };

    ...

    class SomeLeafClassThatMultiplyInheritsFromGCRoot : public A, public B, public C {
        virtual void* getBasePointer() const { return (void*)this; }
    }
        
This allows us to recover the "proper" start in O(1) time, without hacking up a FindBeginning(). On the downside, it still requires manual invention to ensure the proper overload to getBasePointer() are added.

Actually.... wait, crud, this still won't work at all: since the vtable inside the GCRoot ctor will know only about GCRoot, not the subclasses. Foo.

(I wonder if the right answer isn't do simply disallow *ALL* inheritance of GCRoot, multiple or single, and require explicit AddRoot() calls...)

Comment 21

[Steven Johnson]

(In reply to comment #20)
> So, with all due respect to Mr. Smedberg, I can't find any precedent that
> suggests that dynamic_cast<> is legal without RTTI enabled.

Correcting myself, I found this in the RVCT documentation: "You are permitted to use dynamic_cast without --rtti in cases where RTTI is not required, such as dynamic cast to an unambiguous base, and dynamic cast to (void *). If you try to use dynamic_cast without --rtti in cases where RTTI is required, the compiler generates an error." (Not sure if this is language mandate or compiler-specific behavior... tread carefully.)

Comment 22

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

(In reply to comment #21)
> (In reply to comment #20)
> > So, with all due respect to Mr. Smedberg, I can't find any precedent that
> > suggests that dynamic_cast<> is legal without RTTI enabled.
> 
> Correcting myself, I found this in the RVCT documentation: "You are
> permitted to use dynamic_cast without --rtti in cases where RTTI is not
> required, such as dynamic cast to an unambiguous base, and dynamic cast to
> (void *). If you try to use dynamic_cast without --rtti in cases where RTTI
> is required, the compiler generates an error." (Not sure if this is language
> mandate or compiler-specific behavior... tread carefully.)

There is also an interesting back-and-forth here:

  http://gcc.gnu.org/bugzilla/show_bug.cgi?id=28687

(Perhaps unsurprising, Benjamin Smedberg is involved in the argument there as well. :)

Comment 23

[Steven Johnson]

Hmm... based on that, it was broken in (at least some) versions of GCC prior to 4.2 when RTTI is disabled; IIUC we are still using GCC4.0 for OSX 32-bit. So this may be a nonstarter for us.

(On a side note, I tend to agree with the 'dynamic-cast-requires-RTTI' camp just on principle, even if some cases can get by without it, purely on the principle that casting in C++ is already a too-complex set of rules, and further special-casing dynamic_cast makes my head hurt. But then, I'm not maintaining a giant existing source base that relies on the legacy behavior...)

Comment 24

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

Attachment: c++ experiment w/ dynamic_cast and offsetof

(In reply to comment #13)
> A STATIC_ASSERT sounds like a great idea.  I can see the problem with the
> example above, but maybe something like this would work:
> 
> STATIC_ASSERT(offsetof(LeafType, firstgcrootmember) == offsetof(GCRoot,
> firstgcrootmember))

I expanded my experiment from comment 16 to explore how offsetof can be used to introspect this case.  It looks like it can solve our problem, *except* that I don't think its any more portable than anything else we are doing.

In particular, while I am seeing the static asserts firing appropriately, there are warnings; in particular, GCC emits a warning that I may be misusing offsetof.  But I've seen this same warning about offsetof emitted elsewhere when compiling, so I do not think this is a warning that would crater the player or shell builds.)

References:
http://stackoverflow.com/questions/1129894/why-cant-you-use-offsetof-on-non-pod-strucutures-in-c

http://gcc.gnu.org/onlinedocs/gcc-4.4.0/gcc/Warning-Options.html#index-Winvalid_002doffsetof-441

http://en.wikipedia.org/wiki/C%2B%2B0x#Modification_to_the_definition_of_plain_old_data

The static assert may still be worth exploring.  It *did* successfully catch (at compile time) the failure to layout GCRoot at the front of the player class from WE 2873296.  But then again, the fact that I have to put it at each leaf class of interest basically means that I have to detect the failure cases anyway, and the real question is whether passing the static assert is actually meaningful, or if compilers could silently select a different layout for non-POD after passing the offsetof MMGC_STATIC_ASSERT.

Comment 25

[Steven Johnson]

(In reply to comment #23)
> Hmm... based on that, it was broken in (at least some) versions of GCC prior
> to 4.2 when RTTI is disabled; IIUC we are still using GCC4.0 for OSX 32-bit.
> So this may be a nonstarter for us.

Also, anecdotal reports from googling seem to indicate that MSVC may not have the same optimization (ie, any dynamic_cast without RTTI is dangerous).

Comment 26

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

(In reply to comment #24)
> The static assert may still be worth exploring.  It *did* successfully catch
> (at compile time) the failure to layout GCRoot at the front of the player
> class from WE 2873296.  But then again, the fact that I have to put it at
> each leaf class of interest basically means that I have to detect the
> failure cases anyway, and the real question is whether passing the static
> assert is actually meaningful, or if compilers could silently select a
> different layout for non-POD after passing the offsetof MMGC_STATIC_ASSERT.

Another really ugly wart is that all of GCRoot's data members are currently private.  Thus, to even express the STATIC_ASSERT, we need to expose at least one of them.

I filed that task (with patch) as Bug 663491.

Next task: extending gcClasses.as as suggested by Lars in comment 14 so that I can actually find all of the leaf classes that we need to put the STATIC_ASSERT into.

Comment 27

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

(In reply to comment #26) 
> Next task: extending gcClasses.as as suggested by Lars in comment 14 so that
> I can actually find all of the leaf classes that we need to put the
> STATIC_ASSERT into.

Filed as Bug 663917.

Comment 28

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

(In reply to comment #10)
> My main worry about doing FindBeginning in the GCRoot constructor is that I
> don't know what computational cost that will incur on our runtime
> performance.  Although, as its been said above, exactly-traced GCRoots won't
> use the conservative tracer and therefore could similarly avoid the
> FindBeginning cost.  So maybe a hybrid solution of doing FindBeginning just
> for conservatively-traced GCRoots would be reasonable.

In Bug 663491, comment 7 (in reply to Bug 663491, comment 5), Tommy argues for doing FixedMalloc::FindBeginning in the GCRoot constructor.

In comment 14, Lars points out:
> Another point is that I dearly want to disentangle FixedMalloc from the rest
> of MMgc and not require its use for GCRoots.  So that's worth keeping in
> mind.

So he will still want a different long-term solution (Lars proposed one, there may be others; we will have to attack this post-Serrano).

Comment 29

[Tommy Reilly]

In a world where there aren't a ton of GCRoots and they are all exactly traced decoupling from FixedMalloc should be doable.  Although I don't think I'll ever agree to decoupling from FixedMalloc until we can guarantee fields are properly zero'd.   We've had may crazy reference leak bugs from dirty GCRoots.

Comment 30

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

Added dependence on Bug 681388, which has a patch that speeds up FixedMalloc::FindBeginning for the GCRoot case and thus makes that fix for the multiple inheritance problem acceptable with respect to performance if not aesthetics.

Comment 31

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

Now that FixedMalloc::FindBeginning should be constant-time in almost all GCRoot construction cases, closing this off.  (If it turns out to still be problematic, e.g. if the locking introduced by Bug 681388 is a problem, then I say we bite the bullet and go through and make all instances of GCRoot singly-inherited.  That, or get rid of GCRoot entirely.)