[Vm-dev] Re: [Pharo-project] [Ann] Ephemerons for Cog

[Javier Burroni]

Hi Igor,
It's great you have implemented Ephemerons. I'll take a look to the code asap.

I've sent the following mail to the VSWE-L list like a month ago. It
may (or may not) be useful for you
saludos
jb

-----------
Consider the following code:

testNestedEphemeronsWEphemeronKey
  | toBeRescued |
  toBeRescued := EphemeronWRescueMemory
      key: Object new
      value: (EphemeronWRescueMemory key: Object new).
  Smalltalk unusedMemory.
  Ephemeron processRescuedEphemerons.
  Smalltalk unusedMemory.
  self
      assert: toBeRescued hasBeenRescued;
      deny: toBeRescued value key methodDictionaryArray isNil;
      assert: toBeRescued value hasBeenRescued

Where EphemeronWRescueMemory is an Ephemeron's subclass which can
answer if it has been already rescued.
This code will break smalltalk.
The reason for this test to fail, is the existence of an ephemeron (B)
as other ephemeron's value (A).
Following Hayes, whenever ephemeron A rescued, it should be traced as
any other object -loosing the idea of ephemerons, neither in a direct
or indirect way-.
However, the apparent behavior when following object A and finding
ephemerons, is to mark and queue the just found ephemeron -B in this
case-; but never trace the ephemeron -B-. This makes B's reference to
be out of date, and (potentially) point to non valid objects.
In Hayes code:

Heap::markPhase3
  EphemeronQueue enumerate:[:ephemeron|
          ephemeron deref signal: almostCollectable.
          ephemeron deref keyField tracePointerQueueingEphemerons.
          ephemeron deref valueField tracePointerQueueingEphemerons].

When the correct code should be:
Heap::markPhase3
  EphemeronQueue enumerate:[:ephemeron|
          ephemeron deref signal: almostCollectable.
          ephemeron deref keyField tracePointer.
          ephemeron deref valueField tracePointer].

There are an interesting point regarding Hayes work: the first time a
GC is run, the ephemeron B will be handle as a non-ephemeron ("Mark
all of the objects reachable from this pointer, paying no attention to
ephemerons" p. 183 [1]).
With a small modification, the algorithm may be able to handle object
B as an ephemeron in the first run. To do so, we have to focus on the
fundamental idea of ephemerons: the topological relation between
objects and the ephemeron's key/value. The relation between objects
and the ephemeron itself shall be of no importance.

So, suppose we have this:
VMGarbageCollector>>#rescueEphemerons
  | unknowns rescan rescued |
  rescued := rescan := false.
  unknowns := ephemeronsStack.
  [ephemerons isEmpty] whileFalse: [
      rescan := self followEphemeronsCollectingIn: unknowns.
      rescan ifTrue: [ephemerons addAll: unknowns] ifFalse: [
          unknowns do: [:ephemeron |
              self rescueEphemeron: ephemeron.
              rescued := true]].
      unknowns reset].
  rescued ifTrue: [self someEphemeronsRescued]


VMGarbageCollector>>#followEphemeronsCollectingIn: unknowns
  | rescan |
  rescan := false.
  [ephemerons isEmpty] whileFalse: [| ephemeron |
      ephemeron := ephemerons pop.
      ephemeron == nil ifFalse: [
          (self checkReachablePropertyOf: ephemeron)
              ifTrue: [
                  self follow: ephemeron count: ephemeron
_extendedSize startingAt: 1.
                  rescan := true]
              ifFalse: [unknowns add: ephemeron]]].
  ^rescan

VMGarbageCollector>>#rescueEphemeron: ephemeron
  ephemeron _haveNoWeaks
  self follow: ephemeron count: ephemeron _extendedSize startingAt: 1.
  rescuedEphemerons add: ephemeron

This implementation may fail to detect object as 'almost collectable',
whenever a rescued ephemeron refers to an object, when this object is
the key of a non yet seen ephemeron. But the set of correctly rescued
ephemerons is big than the Hayes set (which is a subset)

/jb

[1]: Hayes, B. 1997. Ephemerons: a new finalization mechanism.
Proceedings of the 12th ACM SIGPLAN conference on Object-oriented
programming, systems, languages, and applications.
http://portal.acm.org/citation.cfm?id=263733


On Tue, May 24, 2011 at 10:52 AM, Igor Stasenko <siguctua at gmail.com> wrote:
>
> Okay, i fixed this without delving deep into code.
> I just split #markAndTraceAndMaybeFreeStackPages: on three separate methods:
>
> #invalidateStackPagesTraceState
> #markAndTraceRestStackPages
> #freeUnusedStackPages
>
> so a code now looks like following:
>
>        "Now deal with stack pages"
>        fullGCFlag
>                ifFalse: [ self invalidateStackPagesTraceState ]
>                ifTrue: [ self markAndTraceRestStackPages ].
>
>        "Process ephemerons"
>        [ self processEphemeronsQueue ] whileTrue: [
>                "some stack pages may be reachable only through ephemerons"
>                fullGCFlag
>                        ifTrue: [ self markAndTraceRestStackPages ].
>        ].
>        self unlinkEphemeronsStillInQueue.
>
>        "Free unused stack pages. Only safe to free stack pages after all
> have been traced. "
>
>        fullGCFlag ifTrue: [ self freeUnusedStackPages  ].
>
>        "Only safe to free any machine code methods after all
>         stack pages have been traced."
>        self markAndTraceOrFreeMachineCode: fullGCFlag.
>
>
> Now the last question:
> should i take care of #markAndTraceOrFreeMachineCode: as well?
> Can machine code point to an object(s) which are not reachable from
> roots & ephemerons,
> but only from machine code?
>
> I guess not, because if machine code could point to a subgraph which
> holding arbitrary set of objects,
> then it will be also dangerous to free stack pages before tracing machine code.
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>



-- 
" To be is to do " ( Socrates )
" To be or not to be " ( Shakespeare )
" To do is to be " ( Sartre )
" Do be do be do " ( Sinatra )