Re: [rvm-research] [GC]About MarkCompact and ComplexPhase

On 12/08/13 02:54, Eliot Moss wrote:
> On 8/11/2013 7:12 AM, ChenHao wrote:
>
>> 1.MarkCompactCollector.ToCursor
>>     void copy(ObjectReference from, ObjectReference to) {
>> cursor = VM.objectModel.copyTo(from, to, cursor);
>>        MarkCompactSpace.setForwardingPointer(to, ObjectReference.nullReference());
>>      }
>> the "cursor" is:
>> @param region The start of the region that was reserved for this object
>> @param region The start (or an address less than) the region that was reserved for this object.
>> but "cursor" may change during a collection, not always the start of the region.
I'm assuming your question is "what role does the cursor have in this
method call" ?  The javadoc for this method says it all, I think.

  /**
   * Copy an object to be pointer to by the to address. This is required
   * for delayed-copy collectors such as compacting collectors. During the
   * collection, MMTk reserves a region in the heap for an object as per
   * requirements found from ObjectModel and then asks ObjectModel to
   * determine what the object's reference will be post-copy.
   *
   * @param from the address of the object to be copied
   * @param to The target location.
   * @param region The start of the region that was reserved for this object
   * @return Address The address past the end of the copied object
   */

This version of 'copy' fills the space between 'region' and 'to' with
alignment fill.
>>
>> 2.MarkCompactCollector
>> public void calculateForwardingPointers() {
>>    /* Loop through the objects in the current 'from' region */
>>        while (fromCursor.hasMoreObjects()) {
>>         ......
>>
>>          if (MarkCompactSpace.toBeCompacted(current)) {
>>      .......
>> toCursor.incTo(Allocator.alignAllocationNoFill(toCursor.get(), align, offset));//【1】
>> .......
>>            if (!toCursor.sameRegion(fromCursor) && !toCursor.isAvailable(size)) {
>>              toCursor.advanceToNextRegion();
>>    toCursor.incTo(Allocator.alignAllocationNoFill(toCursor.get(), align, offset));//【2】
>>            }
>>
>>            ObjectReference target = VM.objectModel.getReferenceWhenCopiedTo(current, toCursor.get());
>>            if (toCursor.sameRegion(fromCursor) && target.toAddress().GE(current.toAddress())) {
>>              // Don't move the object.//【3】
>>              MarkCompactSpace.setForwardingPointer(current, current);
>>              toCursor.incTo(VM.objectModel.getObjectEndAddress(current));
>>            } else {
>>              MarkCompactSpace.setForwardingPointer(current, target);
>>              toCursor.inc(size);
>>            }
>>          }
>>        }
>> }
>> Why do "toCursor.incTo(Allocator.alignAllocationNoFill(toCursor.get(), align, offset));"  twice? See
>> 【1】【2】
> The first is normal aligning the copied object in to-space according to its
> required alignment.  The second is done if there was not room for the object
> in the region and the curosr therefore advanced to another region -- you need
> to take alignment into account again in this next region.
Eliot is right.  What you may be missing is that alignAllocationNoFill
simply calculates the address of the object after aligning it, it
doesn't have any side effects.  Given that this method is calculating
the eventual position of all the objects after compaction, it must call
this method every time it calculates an object's final position.
>
>> What does "if (toCursor.sameRegion(fromCursor) && target.toAddress().GE(current.toAddress())) "mean?
>> See【3】
>> In which condition the collector will not move the object?
> If the to- and from- regions are the same and the object would move ahead of
> the scanning cursor (rather than behind it).  This prevents trying to move the
> object more than once.  I have not dug deep enouigh into the algorithm's
> specifics to understand why things are coded this particular way.
Not quite.  It's actually ensuring that we handle objects that would
change if they were moved.  When we use Address-based hashing, an object
that has been hashed needs to record the hash code, so we allocate an
extra word of memory in the newly copied object.  We currently allocate
this at the end of the object, but other designs may do it differently,
and so it's possible that the object's start address may have to move.

Therefore, if the object either doesn't move, or moves in the "wrong"
direction, we know that moving the object has a side-effect, so we
special-case this and leave the object undisturbed rather than do a copy
to the same spot.

>
>> 3.MarkCompactSpace
>> Some comments are confusing，just Crtl C+Crtl V?
>> traceObject()/traceMarkObject()/traceForwardObject()
>> testAndMark()/testAndClearMark()/clearMark()
>>
>> traceObject() is just a stub(Maybe I can reuse to perform Copying)
>> In traceMarkObject() method, why return "object" not "getForwardingPointer(object)"? See 【4】
>> public ObjectReference traceMarkObject(TraceLocal trace, ObjectReference object) {
>>      if (testAndMark(object)) {
>>        trace.processNode(object);
>>      } else if (!getForwardingPointer(object).isNull()) {
>>        return getForwardingPointer(object);
>>      }
>>      }
>>      return object;【4】
>>    }
> Apparently because getForwardingPointer(object) can be null here.  Again, I am
> not sure of the exact meaning of that, though it may mean that forwarding
> addresses have not yet been determined.  In a copying collector, we can
> generally determine the new address right away, but with mark-compact, we
> can't. When this routine is used in the first pass, it simply returns the
> address of the (now-marked) object.  When run after assigning forwarding
> addresses, it will return the forwarding address.
I'm not 100% certain about this, either, and I can't think of a case
where you would want to mark objects after installing forwarding
pointers.  Of course there are multiple mark phases in order to
implement reference types and finalizers, but their mark phases are done
before the forwarding pointers are calculated.  You might like to try
adding a log message to the

if (!getForwardingPointer(object).isNull()) 

branch and testing this assumption.

And yes, the traceObject() is just a stub and can be re-used for your
own purposes.

>
>> 4.MC & ComplexPhase
>> In org.mmtk.plan.markcompact.MC.java, ComplexPhase"mcColletion" is created and it replaces
>> "colletion" in Simple.
>> When a GC is triggered, perform Phase.beginNewPhaseStack(Phase.scheduleComplex(global().collection))
>> => pushScheduledPhase() & processPhaseStack()
>> There is no switch casestatement//for "SCHEDULE_COMPLEX" in processPhaseStack(), how to process
>> ComplexPhase in Phase?
>> Simple defines lots of Phases, which is necessary for a Plan? And when should I define my own phase?
>> I'm still not so clear about how to write collctionPhase().
> Someone else will have to answer that one, but typical GC algorithms have a
> number of phases and a plan needs to indicate which ones a given overall
> algorithm has, and the order in which they occur.  Ignoring any prepartory and
> "cleanup" sorts of phases, most GCs so some kind of tracing through objects,
> finding the reachable ones.  Copying GCs may do copying and forward address
> determination at this time as well.  Compacting GCs may have phases to
> determine forwarding addresses, move the objects, and update addresses to
> point to new locations.  Some of these phases can, with care, be folded
> together. Mark-sweep does not use forwarding addresses, but does need to
> sweep.  Sweeping may be done lazily, as allocation demands new blocks into
> which to allocate.
>
> Combined algorithms will generally need at least the phases of each algorithm
> being combined.  Parallel and concurrent collection can be even trickier, of
> course. And I've not mentioned reference counting techniques, stack tracing,
> generational collection, special spaces (e.g., for code, large objects,
> etc.).  But I hope this gives the general idea of phases.
See getNextPhase().  A Complex phase is simply a sequence of phases, so
it's interpreted at the point where we choose the next (simple) phase to
execute.  All you really need to know is that the phases in a complex
phase are executed sequentially.

> Simple defines lots of Phases, which is necessary for a Plan? 

All of them are required by one or more collectors.  Most top-level plan
classes leave most phases unchanged (this is why we have the class
hierarchy we do), and just implement the ones they need.  In general if
you define a space in your plan, your code needs to perform all the
steps required to collect that space.  If you read a collectionPhase
method from MarkSweep or SemiSpace (for example) you'll see how this
principal shapes the code.

> And when should I define my own phase?

When you need to do something that can't be achieved by the existing
phases.  Most plans don't define new phases.  Plans like MC do because
they have an inherently different structure.

cheers
>
> Regards -- Eliot Moss
>
> ------------------------------------------------------------------------------
> Get 100% visibility into Java/.NET code with AppDynamics Lite!
> It's a free troubleshooting tool designed for production.
> Get down to code-level detail for bottlenecks, with <2% overhead. 
> Download for free and get started troubleshooting in minutes. 
> http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
> _______________________________________________
> Jikesrvm-researchers mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers


------------------------------------------------------------------------------
Get 100% visibility into Java/.NET code with AppDynamics Lite!
It's a free troubleshooting tool designed for production.
Get down to code-level detail for bottlenecks, with <2% overhead. 
Download for free and get started troubleshooting in minutes. 
http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
_______________________________________________
Jikesrvm-researchers mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers