RE: FYI: Linker & Verifier fixes (really GC mark procedures)

RE: FYI: Linker & Verifier fixes (really GC mark procedures)

[Boehm, Hans]

I haven't been following the details here, but some of the suggested
directions scare me a bit.

The present issue aside, I think we're in general far better off
allocating collectable memory for anything that interacts with the
collector, and making the mark descriptors conservative, and eventually
correct.  (If we know that fields will contain either small integers or
pointers, just allocating it as potentially pointer-containing would
also currently work fine.)  Certainly I think we should be moving in
that direction.

The code in _Jv_MarkObj that directly traces objects referenced from
class objects (instead of pushing them on the mark stack) is on very
thin ice.  That's not how mark procedures are supposed to work.  In my
opinion, if we could make it go away, that would be great.

In particular, in thinking about this again, I'm not sure this is
correct with incremental GC, and it may be causing some of the problems
there.  With incremental GC we may end up tracing only the subobjects,
since the containing object may not have been dirtied.  I think the
subobjects currently look pointer-free, which would cause this to fail.

Aside from this issue, _Jv_MarkObj seems to already have been a major
source of very subtle bugs.  I am more and more convinced that this is
just not the right design.

Hans

RE: FYI: Linker & Verifier fixes (really GC mark procedures)

[Andrew Haley]

Boehm, Hans writes:
 > I haven't been following the details here, but some of the suggested
 > directions scare me a bit.
 > 
 > The present issue aside, I think we're in general far better off
 > allocating collectable memory for anything that interacts with the
 > collector, and making the mark descriptors conservative, and eventually
 > correct.  (If we know that fields will contain either small integers or
 > pointers, just allocating it as potentially pointer-containing would
 > also currently work fine.)  Certainly I think we should be moving in
 > that direction.
 > 
 > The code in _Jv_MarkObj that directly traces objects referenced from
 > class objects (instead of pushing them on the mark stack) is on very
 > thin ice.  That's not how mark procedures are supposed to work.  In my
 > opinion, if we could make it go away, that would be great.

Indeed.  I have a patch in the pipeline that causes all objects of
class Class to be properly allocated rather than statically allocated
by the linker.  In turn, this has the potential to make _Jv_MarkObj
eventually go away.

Andrew.

Re: FYI: Linker & Verifier fixes (really GC mark procedures)

[Bryce McKinlay]

Andrew Haley wrote:
>  > The code in _Jv_MarkObj that directly traces objects referenced from
>  > class objects (instead of pushing them on the mark stack) is on very
>  > thin ice.  That's not how mark procedures are supposed to work.  In my
>  > opinion, if we could make it go away, that would be great.
>
> Indeed.  I have a patch in the pipeline that causes all objects of
> class Class to be properly allocated rather than statically allocated
> by the linker.  In turn, this has the potential to make _Jv_MarkObj
> eventually go away.
>   

Yes, _Jv_MarkObj has long been a source of bugs - it would be a big 
improvement to get rid of it.

Once we have this new class metadata scheme, the layout of jclass will 
no longer dictated by the compiler/ABI. It should be trivial to arrange 
jclass so that (eg) all the pointers that need to be marked are at the 
beginning of the object, and give it a length-based mark descriptor so 
that we maintain precise scanning.

Since we'll be allocating variable-length storage for each class's 
static fields at runtime, this would be split into one block for 
pointers, and another block for non-pointer data.

Bryce

Re: FYI: Linker & Verifier fixes (really GC mark procedures)

[Tom Tromey]

>>>>> "Andrew" == Andrew Haley <aph@redhat.com> writes:

Andrew> Indeed.  I have a patch in the pipeline that causes all objects of
Andrew> class Class to be properly allocated rather than statically allocated
Andrew> by the linker.  In turn, this has the potential to make _Jv_MarkObj
Andrew> eventually go away.

I did a little work on the gcjx branch in this area.  But it has
never been tested.  Anyway the idea was that the compiler could emit
real mark descriptors for Class, by special-casing it a bit in
boehm.c.

With your work we could just defer this to runtime like we do for
interpreted classes.  The goal would be to remove all the
Class-specific code from _Jv_MarkObj.

Tom

Re: FYI: Linker & Verifier fixes (really GC mark procedures)

[Andrew Haley]

Tom Tromey writes:
 > >>>>> "Andrew" == Andrew Haley <aph@redhat.com> writes:
 > 
 > Andrew> Indeed.  I have a patch in the pipeline that causes all objects of
 > Andrew> class Class to be properly allocated rather than statically allocated
 > Andrew> by the linker.  In turn, this has the potential to make _Jv_MarkObj
 > Andrew> eventually go away.
 > 
 > I did a little work on the gcjx branch in this area.  But it has
 > never been tested.  Anyway the idea was that the compiler could emit
 > real mark descriptors for Class, by special-casing it a bit in
 > boehm.c.
 > 
 > With your work we could just defer this to runtime like we do for
 > interpreted classes.  The goal would be to remove all the
 > Class-specific code from _Jv_MarkObj.

Right.  I've been trying to get this done all year, but I keep getting
sidetracked to fix other things.  Sigh...

But yeah, my plan is to remove almost all knowledge of the shape of an
instance of Class from the compiler, and then the runtime can do
whatever is convenient.  I'm a bit worried that this might result in
long startup times, so I'm going to be cautious -- at least to begin
with.

Andrew.

Re: FYI: Linker & Verifier fixes (really GC mark procedures)

[Bryce McKinlay]

Andrew Haley wrote:
> Tom Tromey writes:
>  > >>>>> "Andrew" == Andrew Haley <aph@redhat.com> writes:
>  > 
>  > Andrew> Indeed.  I have a patch in the pipeline that causes all objects of
>  > Andrew> class Class to be properly allocated rather than statically allocated
>  > Andrew> by the linker.  In turn, this has the potential to make _Jv_MarkObj
>  > Andrew> eventually go away.
>  > 
>  > I did a little work on the gcjx branch in this area.  But it has
>  > never been tested.  Anyway the idea was that the compiler could emit
>  > real mark descriptors for Class, by special-casing it a bit in
>  > boehm.c.
>  > 
>  > With your work we could just defer this to runtime like we do for
>  > interpreted classes.  The goal would be to remove all the
>  > Class-specific code from _Jv_MarkObj.
>
> Right.  I've been trying to get this done all year, but I keep getting
> sidetracked to fix other things.  Sigh...
>
> But yeah, my plan is to remove almost all knowledge of the shape of an
> instance of Class from the compiler, and then the runtime can do
> whatever is convenient.  I'm a bit worried that this might result in
> long startup times, so I'm going to be cautious -- at least to begin
> with.

I suspect it is actually possible to _improve_ startup time once this is 
fully implemented.

If the bulk of the class metadata is pointer-free and read-only, then we 
eliminate a vast number of relocations - so much less time ought to be 
spent in the dynamic linker. It should be possible to only create Class 
objects for classes which are actually used/referenced at runtime, so 
the added allocation overhead ought to be pretty minimal.

Bryce

Re: FYI: Linker & Verifier fixes (really GC mark procedures)

[Andrew Haley]

Bryce McKinlay writes:
 > Andrew Haley wrote:
 > >
 > > But yeah, my plan is to remove almost all knowledge of the shape of an
 > > instance of Class from the compiler, and then the runtime can do
 > > whatever is convenient.  I'm a bit worried that this might result in
 > > long startup times, so I'm going to be cautious -- at least to begin
 > > with.
 > 
 > I suspect it is actually possible to _improve_ startup time once this is 
 > fully implemented.
 > 
 > If the bulk of the class metadata is pointer-free and read-only, then we 
 > eliminate a vast number of relocations - so much less time ought to be 
 > spent in the dynamic linker. It should be possible to only create Class 
 > objects for classes which are actually used/referenced at runtime, so 
 > the added allocation overhead ought to be pretty minimal.

That might well be true, but we've (well, at least I have) been caught
this way before: assuming that something would be a speedup when it
turned out to be a slowdown.  I hope you're right.

Andrew.

Re: FYI: Linker & Verifier fixes (really GC mark procedures)

[Tom Tromey]

>>>>> "Tom" == Tom Tromey <tromey@redhat.com> writes:

Tom> I did a little work on the gcjx branch in this area.  But it has
Tom> never been tested.  Anyway the idea was that the compiler could emit
Tom> real mark descriptors for Class, by special-casing it a bit in
Tom> boehm.c.

I looked at this today.  We can't scan Class using a bitmap descriptor
yet, because its layout is wrong for this.  The descriptor overflows
and we have to fall back to procedural scanning.

We could still do better than we do today, I think.  For instance we
could scan Class conservatively, and make sure to allocate
Class-related structures via the GC (using conservative scanning or
introducing new mark kinds as desired).

Not only would this clean up the ugly and potentially problematic code
in _Jv_MarkObj, but it would remove some leaks (that occur if a Class
is GCd) we currently have.  Also I suspect conservative scanning is
faster than what we're doing now (this might go for other classes as
well).

I've started a patch to do this, but it isn't complete.

Tom

Re: FYI: Linker & Verifier fixes (really GC mark procedures)

[Hans Boehm]

On Thu, 2 Feb 2006, Tom Tromey wrote:

> >>>>> "Tom" == Tom Tromey <tromey@redhat.com> writes:
>
> Tom> I did a little work on the gcjx branch in this area.  But it has
> Tom> never been tested.  Anyway the idea was that the compiler could emit
> Tom> real mark descriptors for Class, by special-casing it a bit in
> Tom> boehm.c.
>
> I looked at this today.  We can't scan Class using a bitmap descriptor
> yet, because its layout is wrong for this.  The descriptor overflows
> and we have to fall back to procedural scanning.
>
Just to be clear, since I'm not quite sure I understand what you're saying
here:  I don't think it's the mark procedure per se
that's the problem.  The issue is having a mark procedure that
walks complicated data structures and traces those instead of just
pushing directly referenced objects.

In particular, I don't think there's a problem with using a mark
procedure to deal with bitmap overflow issues, as we do for a few
ordinary objects.  It does normally add some overhead.  But if the
object is large enough to overflow (especially a 64-bit) bitmap, that's
probably not dominant.

Hans

Re: FYI: Linker & Verifier fixes (really GC mark procedures)

[Tom Tromey]

>>>>> "Hans" == Hans Boehm <Hans.Boehm@hp.com> writes:

>> I looked at this today.  We can't scan Class using a bitmap descriptor
>> yet, because its layout is wrong for this.  The descriptor overflows
>> and we have to fall back to procedural scanning.

Hans> Just to be clear, since I'm not quite sure I understand what
Hans> you're saying here: I don't think it's the mark procedure per se
Hans> that's the problem.  The issue is having a mark procedure that
Hans> walks complicated data structures and traces those instead of
Hans> just pushing directly referenced objects.

I was interested in removing the mark procedure for Class objects, but
that isn't possible on 32 bit systems -- our choices are continue to
mark them procedurally, or mark them conservatively.

But, yeah, part of my patch is to allocate things that are pointed to
by Class such that they are scanned themselves and don't require
special treatment in the procedural scanner.  This will remove the
ugly/fragile/problematic code.

Tom

Re: FYI: Linker & Verifier fixes (really GC mark procedures)

[David Daney]

Tom Tromey wrote:
>>>>>>"Hans" == Hans Boehm <Hans.Boehm@hp.com> writes:
> 
> 
>>>I looked at this today.  We can't scan Class using a bitmap descriptor
>>>yet, because its layout is wrong for this.  The descriptor overflows
>>>and we have to fall back to procedural scanning.
> 
> 
> Hans> Just to be clear, since I'm not quite sure I understand what
> Hans> you're saying here: I don't think it's the mark procedure per se
> Hans> that's the problem.  The issue is having a mark procedure that
> Hans> walks complicated data structures and traces those instead of
> Hans> just pushing directly referenced objects.
> 
> I was interested in removing the mark procedure for Class objects, but
> that isn't possible on 32 bit systems -- our choices are continue to
> mark them procedurally, or mark them conservatively.
> 
> But, yeah, part of my patch is to allocate things that are pointed to
> by Class such that they are scanned themselves and don't require
> special treatment in the procedural scanner.  This will remove the
> ugly/fragile/problematic code.

This is slightly off topic, but could you put the bitmap descriptor as 
the last field in the Class object?  Then make a variable length bit 
string with the high (or perhaps low) order bit indicating if there was 
another segment of bit string following?

One word of bit string would mark the first 31 (or 63) fields, then if 
the high bit were set there would be another word for the next 31 (or 
63) fields...


David Daney.

Re: FYI: Linker & Verifier fixes (really GC mark procedures)

[Bryce McKinlay]

Tom Tromey wrote:
> Tom> I did a little work on the gcjx branch in this area.  But it has
> Tom> never been tested.  Anyway the idea was that the compiler could emit
> Tom> real mark descriptors for Class, by special-casing it a bit in
> Tom> boehm.c.
>
> I looked at this today.  We can't scan Class using a bitmap descriptor
> yet, because its layout is wrong for this.  The descriptor overflows
> and we have to fall back to procedural scanning.
>
> We could still do better than we do today, I think.  For instance we
> could scan Class conservatively, and make sure to allocate
> Class-related structures via the GC (using conservative scanning or
> introducing new mark kinds as desired).
>   

My idea was to rearrange the layout of Class such that all pointers go 
at the start of the Object, and non-pointers (plus pointers that we 
never want marked?) go at the end. Then, we should be able to use a 
length-based descriptor to get precise scanning.

Of course, Class needs to be allocated at runtime before we can make 
this happen. And, it will break the ABI - perhaps we could come up with 
some kind of compatibility mode to create a new-Class from the old, 
however.

Bryce

Re: FYI: Linker & Verifier fixes (really GC mark procedures)

[David Daney]

Bryce McKinlay wrote:
> Tom Tromey wrote:
> 
>> Tom> I did a little work on the gcjx branch in this area.  But it has
>> Tom> never been tested.  Anyway the idea was that the compiler could emit
>> Tom> real mark descriptors for Class, by special-casing it a bit in
>> Tom> boehm.c.
>>
>> I looked at this today.  We can't scan Class using a bitmap descriptor
>> yet, because its layout is wrong for this.  The descriptor overflows
>> and we have to fall back to procedural scanning.
>>
>> We could still do better than we do today, I think.  For instance we
>> could scan Class conservatively, and make sure to allocate
>> Class-related structures via the GC (using conservative scanning or
>> introducing new mark kinds as desired).
>>   
> 
> 
> My idea was to rearrange the layout of Class such that all pointers go 
> at the start of the Object, and non-pointers (plus pointers that we 
> never want marked?) go at the end. Then, we should be able to use a 
> length-based descriptor to get precise scanning.
> 
> Of course, Class needs to be allocated at runtime before we can make 
> this happen. And, it will break the ABI - perhaps we could come up with 
> some kind of compatibility mode to create a new-Class from the old, 
> however.

Does it really change the ABI in a bad way?  Couldn't we just hack up 
javah to layout the classes the new way.  There is no guarantee of C++ 
ABI stability across versions is there?

And for the BC ABI isn't the class layed out at runtime?

David Daney.

Re: FYI: Linker & Verifier fixes (really GC mark procedures)

[Andrew Haley]

David Daney writes:
 > 
 > Does it really change the ABI in a bad way?  Couldn't we just hack up 
 > javah to layout the classes the new way.  There is no guarantee of C++ 
 > ABI stability across versions is there?

That's right, there isn't.

 > And for the BC ABI isn't the class layed out at runtime?

Not for class Class, no: that's still fixed.  That is the point of
what I'll be doing as soon as if fix this damn bug I'm working on...

Andrew.

Re: FYI: Linker & Verifier fixes (really GC mark procedures)

[Bryce McKinlay]

David Daney wrote:
>> Of course, Class needs to be allocated at runtime before we can make 
>> this happen. And, it will break the ABI - perhaps we could come up 
>> with some kind of compatibility mode to create a new-Class from the 
>> old, however.
>
> Does it really change the ABI in a bad way? 

Yes, changing the layout of java.lang.Class will break the BC ABI 
because the class Objects are
> And for the BC ABI isn't the class layed out at runtime? 

Not yet - this is the change that Andrew is working on. Thinking about 
it more, compatibility will be difficult to implement because code 
currently refers to the static Class objects directly, by symbol - we'd 
need to somehow overwrite these pointers.

We need to consider whether the advantages of changing the layout would 
justify breaking the ABI. If the layout remains the same, can we retain 
compatibility with existing code that uses static java.lang.Class while 
switching to dynamic allocation for new code?

Bryce

Re: FYI: Linker & Verifier fixes (really GC mark procedures)

[Tom Tromey]

>>>>> "Hans" == Boehm, Hans <hans.boehm@hp.com> writes:

Hans> The present issue aside, I think we're in general far better off
Hans> allocating collectable memory for anything that interacts with the
Hans> collector, and making the mark descriptors conservative, and eventually
Hans> correct.

I agree.  I don't think it would be extremely hard to expose a bit
more GC API here, and set up proper descriptors for various
libgcj-internal non-java-class objects that we want to mark properly.

Tom

RE: FYI: Linker & Verifier fixes (really GC mark procedures)

[Boehm, Hans]

> This is slightly off topic, but could you put the bitmap 
> descriptor as 
> the last field in the Class object?  Then make a variable length bit 
> string with the high (or perhaps low) order bit indicating if 
> there was 
> another segment of bit string following?
> 
> One word of bit string would mark the first 31 (or 63) 
> fields, then if 
> the high bit were set there would be another word for the next 31 (or 
> 63) fields...
> 
Theoretically it could.  But it doesn't match well with the way the GC
does things.  And I also don't think it would be a measurable win.

The GC understands descriptor words associated with an entire page of
objects.  That word may be a descriptor that tells the GC to look in the
object itself for the real descriptor, or to indirect twice through a
"vtable pointer" to find it.  This is all reasonably clean so long as
all descriptors fit in a word.  (Actually it's unclean in one very
subtle respect, which might get even more complicated with
variable-length descriptors.  The issue has to do with false pointers to
objects with garbage descriptors.)

The reason for doing all of this, instead of just calling mark
procedures from the collector, is largely to avoid a procedure call (and
associated startup costs dealing with got-tables, etc.) for every marked
object.  The only place it fails is for objects that are longer than 30
or 62 words long and don't qualify for a length descriptor.  But those
generally require enough work to trace that the procedure call is likely
to be in the noise anyway.

So long as we get the mark procedure(s) to behave correctly, I think
we're fine.  Class objects aren't likely to make up a large fraction of
the heap anyway, I hope.

Hans