On 24 May 2011 02:47, Alexandre Bergel alexandre.bergel@me.com wrote:
What is Ephemerons?
http://portal.acm.org/citation.cfm?id=263733&coll=portal&dl=ACM
Here the paper, if Eliot's explanation is not enough.
Alexandre
Le 23 mai 2011 à 20:43, Igor Stasenko siguctua@gmail.com a écrit :
I felt a bit hacky today and decided to implement Ephemerons.
I tried to run it on both StackVM and Cog VMs, it seems to work fine (at least all 4 tests, which my brain were capable to produce, are green. ;)
You can find the VM code on SqS/VMMaker in package: VMMaker-oscog-IgorStasenko.67
Also, i created a separate issue on Cog issue tracker to track it. http://code.google.com/p/cog/issues/detail?id=44
The implementation may contain a bugs. So, it needs review and testing. Now i would like all interested parties to give a feedback and help integrating it into our production images.
-- Best regards, Igor Stasenko AKA sig.
Eliot, i need your help to synthesize tests which test that if stack pages are reachable only from ephemeron(s), then it handled correctly.
I did a following change in #markPhase: (after marking all roots)
... blah blah ...
"Only safe to free stack pages after all roots have been traced." self markAndTraceAndMaybeFreeStackPages: fullGCFlag.
"the above was in original code, and i also added following: "
"Process ephemerons" [ self processEphemeronsQueue ] whileTrue: [ "some stack pages may be reachable only through ephemerons" self markAndTraceAndMaybeFreeStackPages: fullGCFlag. ].
There could be a potential problem, if some stack page are reachable from ephemeron only, because i'm not sure how #markAndTraceAndMaybeFreeStackPages: works.
The situation could be following:
(roots) ->..-> ephemeron 2 (roots) ->..-> ephemeron 1 ephemeron 1 (value) ->..-> ephemeron 2 key ephemeron2 -> (value) ->..-> stack page
so, here is step-by-step explanation, which could lead to problem(s):
1. GC found ephemeron 2. But its key not yet marked, since the only reference to it is visible from ephemeron 1. Therefore ephemeron 2 are put into queue.
2. GC found ephemeron 1, and lets assume that its key already marked, so we don't put it into a queue but continue with tracing its value (strongly). As result of tracing, now ephemeron's 2 key will be marked as reachable.
3. we done with initial mark stage. Now going to call initial #markAndTraceAndMaybeFreeStackPages:
4. we start analyzing the queue. And since at this stage ephemeron's 2 key is already marked, so we proceed with tracing its value, which makes some more stack page marked as reachable.
5. we tracing the left stack pages which possibly discovered once ephemeron's 2 value is traced.
So, my doubts are at step 3. If #markAndTraceAndMaybeFreeStackPages doesn't works as i expecting, it could presume that some stack pages are not accessible and prematurely free them, before processing ephemeron's queue which discovering some extra live stack pages.
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.
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@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.
On 24 May 2011 16:58, Javier Burroni javier.burroni@gmail.com wrote:
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
The mail you posted is hard to follow for me, because i don't really understand what 'rescued ephemeron' means. Is it the one who initially seen without its key being marked, but then after full graph traversal has it key marked?
The ephemerons extension to GC are quite simple (it explains why it took me 1 day to get initial implementation working).
The only implication of ephemerons, that you need to fulfill is that you mark all reachable objects before analyzing ephemerons queue. And during analysis you have to make sure that again, you are marking all reachable objects discovered through ephemerons, whose keys are marked. If you obey the above rules, then there's not much to fear about. It will just work :)
On Tue, May 24, 2011 at 9:09 AM, Igor Stasenko siguctua@gmail.com wrote:
On 24 May 2011 16:58, Javier Burroni javier.burroni@gmail.com wrote:
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
The mail you posted is hard to follow for me, because i don't really understand what 'rescued ephemeron' means. Is it the one who initially seen without its key being marked, but then after full graph traversal has it key marked?
The ephemerons extension to GC are quite simple (it explains why it took me 1 day to get initial implementation working).
The only implication of ephemerons, that you need to fulfill is that you mark all reachable objects before analyzing ephemerons queue. And during analysis you have to make sure that again, you are marking all reachable objects discovered through ephemerons, whose keys are marked. If you obey the above rules, then there's not much to fear about. It will just work :)
I think there are two implications, and the second one is non-obvious because the original implementor of ephemerons in VW, who was a GC expert, got this wrong. The first implication is indeed that you mark all reachable objects before analysing ephemerons with unmarked/unreachable keys (ephemerons with marked/reachable keys can and should be processed just like ordinary objects). The second implication is that the tracing of ephemerons with unreachable keys continues until a fixed-point is reached where no new ephemerons have been added to the ephemeron queue. i.e. when tracing ephemerons with unreachable keys one may reach new ephemerons which themselves may have either marked/reachable or unmarked/unreachable keys. This is really important and a tad tricky.
cheers, Eliot
-- Best regards, Igor Stasenko AKA sig.
On 24 May 2011 18:38, Eliot Miranda eliot.miranda@gmail.com wrote:
On Tue, May 24, 2011 at 9:09 AM, Igor Stasenko siguctua@gmail.com wrote:
On 24 May 2011 16:58, Javier Burroni javier.burroni@gmail.com wrote:
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
The mail you posted is hard to follow for me, because i don't really understand what 'rescued ephemeron' means. Is it the one who initially seen without its key being marked, but then after full graph traversal has it key marked?
The ephemerons extension to GC are quite simple (it explains why it took me 1 day to get initial implementation working).
The only implication of ephemerons, that you need to fulfill is that you mark all reachable objects before analyzing ephemerons queue. And during analysis you have to make sure that again, you are marking all reachable objects discovered through ephemerons, whose keys are marked. If you obey the above rules, then there's not much to fear about. It will just work :)
I think there are two implications, and the second one is non-obvious because the original implementor of ephemerons in VW, who was a GC expert, got this wrong. The first implication is indeed that you mark all reachable objects before analysing ephemerons with unmarked/unreachable keys (ephemerons with marked/reachable keys can and should be processed just like ordinary objects). The second implication is that the tracing of ephemerons with unreachable keys continues until a fixed-point is reached where no new ephemerons have been added to the ephemeron queue. i.e. when tracing ephemerons with unreachable keys one may reach new ephemerons which themselves may have either marked/reachable or unmarked/unreachable keys.
I got it from another perspective: we are keep analyzing queue, as long as there are some marking activity happen during previous analysis.
This is what this loop for:
"Process ephemerons" [ self processEphemeronsQueue ] whileTrue: [ "some stack pages may be reachable only through ephemerons" fullGCFlag ifTrue: [ self markAndTraceRestStackPages ]. ].
#processEphemeronsQueue aswers true if during processing the queue, some ephemerons are marked their values (because it is found that their keys are marked).
This is really important and a tad tricky.
And it is there. Don't worry i got it right. :)
My only concern now is about #markAndTraceOrFreeMachineCode: i found that it sends #markAndTrace: , and so, potentially it could mark some previously unmarked ephemeron's keys. Then we are in trouble, since after that we should again mark values for those ephemerons. So, i need your comment about that.
On Tue, May 24, 2011 at 9:56 AM, Igor Stasenko siguctua@gmail.com wrote:
On 24 May 2011 18:38, Eliot Miranda eliot.miranda@gmail.com wrote:
On Tue, May 24, 2011 at 9:09 AM, Igor Stasenko siguctua@gmail.com
wrote:
On 24 May 2011 16:58, Javier Burroni javier.burroni@gmail.com wrote:
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
The mail you posted is hard to follow for me, because i don't really understand what 'rescued ephemeron' means. Is it the one who initially seen without its key being marked, but then after full graph traversal has it key marked?
The ephemerons extension to GC are quite simple (it explains why it took me 1 day to get initial implementation working).
The only implication of ephemerons, that you need to fulfill is that you mark all reachable objects before analyzing ephemerons queue. And during analysis you have to make sure that again, you are marking all reachable objects discovered through ephemerons, whose keys are marked. If you obey the above rules, then there's not much to fear about. It will just work :)
I think there are two implications, and the second one is non-obvious
because the original implementor of ephemerons in VW, who was a GC expert, got this wrong. The first implication is indeed that you mark all reachable objects before analysing ephemerons with unmarked/unreachable keys (ephemerons with marked/reachable keys can and should be processed just like ordinary objects). The second implication is that the tracing of ephemerons with unreachable keys continues until a fixed-point is reached where no new ephemerons have been added to the ephemeron queue. i.e. when tracing ephemerons with unreachable keys one may reach new ephemerons which themselves may have either marked/reachable or unmarked/unreachable keys.
I got it from another perspective: we are keep analyzing queue, as long as there are some marking activity happen during previous analysis.
This is what this loop for:
"Process ephemerons" [ self processEphemeronsQueue ] whileTrue: [ "some stack pages may be reachable only through ephemerons" fullGCFlag ifTrue: [ self markAndTraceRestStackPages ]. ].#processEphemeronsQueue aswers true if during processing the queue, some ephemerons are marked their values (because it is found that their keys are marked).
This is really important and a tad tricky.
And it is there. Don't worry i got it right. :)
My only concern now is about #markAndTraceOrFreeMachineCode: i found that it sends #markAndTrace: , and so, potentially it could mark some previously unmarked ephemeron's keys. Then we are in trouble, since after that we should again mark values for those ephemerons. So, i need your comment about that.
Tracing object references in machine code methods is conceptually the same as finding them in objects. A machine code method contains references to other objects and so these must be traced and the references updated when the referents move. This happens via markAndTrace: just as it does for references from stack pages or ordinary objects. There's no magic here. There is an optimization, avoiding the tracing for incremental GCs unless the method contains references to young objects, since tracing machine code is much more expensive than tracing objects. And of course the machine code method isn't a real object, but a proxy for its compiled method, so it gets discarded when its compiled method is collected. But apart from the cost, the young optimization, and the being a proxy it is really the same process as tracing ordinary objects.
HTH, Eliot
-- Best regards, Igor Stasenko AKA sig.
On 24 May 2011 19:31, Eliot Miranda eliot.miranda@gmail.com wrote:
On Tue, May 24, 2011 at 9:56 AM, Igor Stasenko siguctua@gmail.com wrote:
On 24 May 2011 18:38, Eliot Miranda eliot.miranda@gmail.com wrote:
On Tue, May 24, 2011 at 9:09 AM, Igor Stasenko siguctua@gmail.com wrote:
On 24 May 2011 16:58, Javier Burroni javier.burroni@gmail.com wrote:
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
The mail you posted is hard to follow for me, because i don't really understand what 'rescued ephemeron' means. Is it the one who initially seen without its key being marked, but then after full graph traversal has it key marked?
The ephemerons extension to GC are quite simple (it explains why it took me 1 day to get initial implementation working).
The only implication of ephemerons, that you need to fulfill is that you mark all reachable objects before analyzing ephemerons queue. And during analysis you have to make sure that again, you are marking all reachable objects discovered through ephemerons, whose keys are marked. If you obey the above rules, then there's not much to fear about. It will just work :)
I think there are two implications, and the second one is non-obvious because the original implementor of ephemerons in VW, who was a GC expert, got this wrong. The first implication is indeed that you mark all reachable objects before analysing ephemerons with unmarked/unreachable keys (ephemerons with marked/reachable keys can and should be processed just like ordinary objects). The second implication is that the tracing of ephemerons with unreachable keys continues until a fixed-point is reached where no new ephemerons have been added to the ephemeron queue. i.e. when tracing ephemerons with unreachable keys one may reach new ephemerons which themselves may have either marked/reachable or unmarked/unreachable keys.
I got it from another perspective: we are keep analyzing queue, as long as there are some marking activity happen during previous analysis.
This is what this loop for:
"Process ephemerons" [ self processEphemeronsQueue ] whileTrue: [ "some stack pages may be reachable only through ephemerons" fullGCFlag ifTrue: [ self markAndTraceRestStackPages ]. ].
#processEphemeronsQueue aswers true if during processing the queue, some ephemerons are marked their values (because it is found that their keys are marked).
This is really important and a tad tricky.
And it is there. Don't worry i got it right. :)
My only concern now is about #markAndTraceOrFreeMachineCode: i found that it sends #markAndTrace: , and so, potentially it could mark some previously unmarked ephemeron's keys. Then we are in trouble, since after that we should again mark values for those ephemerons. So, i need your comment about that.
Tracing object references in machine code methods is conceptually the same as finding them in objects. A machine code method contains references to other objects and so these must be traced and the references updated when the referents move. This happens via markAndTrace: just as it does for references from stack pages or ordinary objects. There's no magic here. There is an optimization, avoiding the tracing for incremental GCs unless the method contains references to young objects, since tracing machine code is much more expensive than tracing objects. And of course the machine code method isn't a real object, but a proxy for its compiled method, so it gets discarded when its compiled method is collected. But apart from the cost, the young optimization, and the being a proxy it is really the same process as tracing ordinary objects.
So, from your explanation my first conclusion is that existing implementation is wrong. (not saying about ephemerons). Since before tracing machine code, you tracing stack pages and freeing them. Then what happens if by occasion, a machine code (indirectly) will point to page which already freed?
Also, i am a bit wonder, what other objects a machine code could reference to, in addition to what it's compiled method (from which it was generated)? Isn't it would be simpler to treat machine code to be 'alive' as long as its corresponding compiled method are alive as well? And objects , reachable directly from compiled method are the same as reachable from machine code. No?
Ah, ok.. i think i know the answer: inline caches could reference other methods and so on..
So, then i need to deal with that.. Would it be ok to do it like that:
fullGCFlag ifTrue: [ self markAndTraceRestStackPages ]. self markAndTraceOrFreeMachineCode: fullGCFlag.
"Process ephemerons" [ self processEphemeronsQueue ] whileTrue: [ "some stack pages may be reachable only through ephemerons" fullGCFlag ifTrue: [ self markAndTraceRestStackPages ]. self markAndTraceOrFreeMachineCode: fullGCFlag. ].
self unlinkEphemeronsStillInQueue. "Free unused stack pages. Only safe to free stack pages after all have been traced. "
fullGCFlag ifTrue: [ self freeUnusedStackPages ].
or it will require some more serious hacking?
On 24 May 2011 19:57, Igor Stasenko siguctua@gmail.com wrote:
On 24 May 2011 19:31, Eliot Miranda eliot.miranda@gmail.com wrote:
On Tue, May 24, 2011 at 9:56 AM, Igor Stasenko siguctua@gmail.com wrote:
On 24 May 2011 18:38, Eliot Miranda eliot.miranda@gmail.com wrote:
On Tue, May 24, 2011 at 9:09 AM, Igor Stasenko siguctua@gmail.com wrote:
On 24 May 2011 16:58, Javier Burroni javier.burroni@gmail.com wrote:
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
The mail you posted is hard to follow for me, because i don't really understand what 'rescued ephemeron' means. Is it the one who initially seen without its key being marked, but then after full graph traversal has it key marked?
The ephemerons extension to GC are quite simple (it explains why it took me 1 day to get initial implementation working).
The only implication of ephemerons, that you need to fulfill is that you mark all reachable objects before analyzing ephemerons queue. And during analysis you have to make sure that again, you are marking all reachable objects discovered through ephemerons, whose keys are marked. If you obey the above rules, then there's not much to fear about. It will just work :)
I think there are two implications, and the second one is non-obvious because the original implementor of ephemerons in VW, who was a GC expert, got this wrong. The first implication is indeed that you mark all reachable objects before analysing ephemerons with unmarked/unreachable keys (ephemerons with marked/reachable keys can and should be processed just like ordinary objects). The second implication is that the tracing of ephemerons with unreachable keys continues until a fixed-point is reached where no new ephemerons have been added to the ephemeron queue. i.e. when tracing ephemerons with unreachable keys one may reach new ephemerons which themselves may have either marked/reachable or unmarked/unreachable keys.
I got it from another perspective: we are keep analyzing queue, as long as there are some marking activity happen during previous analysis.
This is what this loop for:
"Process ephemerons" [ self processEphemeronsQueue ] whileTrue: [ "some stack pages may be reachable only through ephemerons" fullGCFlag ifTrue: [ self markAndTraceRestStackPages ]. ].
#processEphemeronsQueue aswers true if during processing the queue, some ephemerons are marked their values (because it is found that their keys are marked).
This is really important and a tad tricky.
And it is there. Don't worry i got it right. :)
My only concern now is about #markAndTraceOrFreeMachineCode: i found that it sends #markAndTrace: , and so, potentially it could mark some previously unmarked ephemeron's keys. Then we are in trouble, since after that we should again mark values for those ephemerons. So, i need your comment about that.
Tracing object references in machine code methods is conceptually the same as finding them in objects. A machine code method contains references to other objects and so these must be traced and the references updated when the referents move. This happens via markAndTrace: just as it does for references from stack pages or ordinary objects. There's no magic here. There is an optimization, avoiding the tracing for incremental GCs unless the method contains references to young objects, since tracing machine code is much more expensive than tracing objects. And of course the machine code method isn't a real object, but a proxy for its compiled method, so it gets discarded when its compiled method is collected. But apart from the cost, the young optimization, and the being a proxy it is really the same process as tracing ordinary objects.
So, from your explanation my first conclusion is that existing implementation is wrong. (not saying about ephemerons). Since before tracing machine code, you tracing stack pages and freeing them. Then what happens if by occasion, a machine code (indirectly) will point to page which already freed?
Also, i am a bit wonder, what other objects a machine code could reference to, in addition to what it's compiled method (from which it was generated)? Isn't it would be simpler to treat machine code to be 'alive' as long as its corresponding compiled method are alive as well? And objects , reachable directly from compiled method are the same as reachable from machine code. No?
it would be good to prove that machine code cannot reference objects not reachable by other means (from roots or stack). Like that, you won't need to mark objects reachable from machine code, and hence can simplify the logic. But i don't know all implications yet.. so it is just a guess.
Isn't it would be simpler to treat machine code to be 'alive' as long
as its corresponding compiled method are alive as well? And objects , reachable directly from compiled method are the same as reachable from machine code. No?
Tracing objects have two ends, keeping reachable alive, and fixing references if the referred object moves.
Even if we could assume that tracing and marking could be done without paying attention to the native code, fixing the references will still need some knowledge of native code.
Two observations about this:
. While a CompiledMethod is being executed in its native form, and if this same CompiledMethod changes itself, for example, the two versions of the CompiledMethod should be kept alive, and the only references to the literals in the old CompiledMethod could be the native code itself. Unless you somehow keep a reference to the old CompiledMethod (for example, in the stack).
. An alternative option to fix the references from native methods, is to have arrays of pairs, Object-Offset. Where the object is what's pointed to by the native array, and the offset is where in the code cache the reference is. Regular GC will fix this auxiliary arrays, and a final step in GC should fix the native references.
I'm not sure about Cog, but I'm sure that at least one other VM implements this later technique.
It has three different references from native code to Objects, and one is special: literals referred from CompiledMethods are inlined references from native code. The CompiledMethod itself is referenced from native code, as it's pushed into the stack on the prologue. And finally, the "class pointer" of the receiver is checked in the prologue to see if the receiver is of the right "class".
This last references, lets call them classCheckReferences, are modified when there's polymorphism and the same native code is activated for a different class. For this case we would need to also change the class in the auxiliary array, but to do that we'd need to know where to change it, etc. It could have been an indirect reference through the auxiliary array, however, the auxiliary array may also move, so we enter a circle.
The solution is to just have offsets in the auxiliary array for classCheckReferences. The GC walks this array in a special way: dereferencing the "offsets", and treating that word in the code cache as a regular object slot. This is one way of knowing how to trace into the native code for object references.
You could also have some special format with metainformation on every native code, to tell where the references are. Or you could make all references indirect through the PC (on platforms where it's supported), and have all references togehter in memory, etc.
oh well... I hope you skipped part of this :) or otherwise, I hope it was helpful
gera
On 24 May 2011 23:51, Gerardo Richarte gera@corest.com wrote:
Isn't it would be simpler to treat machine code to be 'alive' as long
as its corresponding compiled method are alive as well? And objects , reachable directly from compiled method are the same as reachable from machine code. No?
Tracing objects have two ends, keeping reachable alive, and fixing references if the referred object moves.
Even if we could assume that tracing and marking could be done without paying attention to the native code, fixing the references will still need some knowledge of native code.
Yes. But currently the border of my interest are not extends beyond mark phase. Ephemerons don't need special handling during other GC phases, only during mark phase. While fixing refs are done usually at compaction phase.
Two observations about this:
. While a CompiledMethod is being executed in its native form, and if this same CompiledMethod changes itself, for example, the two versions of the CompiledMethod should be kept alive, and the only references to the literals in the old CompiledMethod could be the native code itself. Unless you somehow keep a reference to the old CompiledMethod (for example, in the stack).
A CompiledMethod could "change" itself only via #become: If you just replacing old compiled method in class with a new one, nothing bad happens, since method activation record (aka context) keeps a reference to activated method and it is not changes if you simply manipulating with classe's method dictionary. You can even remove method from class, but it doesn't means that all contexts with such method should magically disappear from stack, right? :)
So, the only special case is when compiled method are turned into another object via #become: . And you can deal with it pretty easily: simply deoptimize all stack frames with machine code for that method and make sure that it will run interpreted code when those contexts will be activated. In any way, just make sure that you never invoking a machine code which is now invalidated because of #become:
Btw.. what happen with contexts whose compiled methods are turned not to compiled methods? For instance:
thisContext sender method becomeForward: (XYZ new)
?
To my expectation, VM could behave gracefully in such cases by simply sending #cannotInterpret: (or variant of it) once context with such thing (which has to be a method but its not) at attempt to activate the context with it. (Currently such expression just violently crashing the VM )
. An alternative option to fix the references from native methods, is to have arrays of pairs, Object-Offset. Where the object is what's pointed to by the native array, and the offset is where in the code cache the reference is. Regular GC will fix this auxiliary arrays, and a final step in GC should fix the native references.
Again, fixing refs may be needed during compaction phase. It depends on implementation, of course (you can generate native code which have no inlined literals, but refers to them via CompiledMethod as interpreter does).
But not during mark phase. Frankly i don't see good reason for a need to scan native code during mark phase (apart from detecting unused code.. but then i think a better place for this stuff closer to code which responsible for compaction phase).
I'm not sure about Cog, but I'm sure that at least one other VM implements this later technique.
It has three different references from native code to Objects, and one is special: literals referred from CompiledMethods are inlined references from native code. The CompiledMethod itself is referenced from native code, as it's pushed into the stack on the prologue. And finally, the "class pointer" of the receiver is checked in the prologue to see if the receiver is of the right "class".
This last references, lets call them classCheckReferences, are modified when there's polymorphism and the same native code is activated for a different class. For this case we would need to also change the class in the auxiliary array, but to do that we'd need to know where to change it, etc. It could have been an indirect reference through the auxiliary array, however, the auxiliary array may also move, so we enter a circle.
The solution is to just have offsets in the auxiliary array for classCheckReferences. The GC walks this array in a special way: dereferencing the "offsets", and treating that word in the code cache as a regular object slot. This is one way of knowing how to trace into the native code for object references.
You could also have some special format with metainformation on every native code, to tell where the references are. Or you could make all references indirect through the PC (on platforms where it's supported), and have all references togehter in memory, etc.
oh well... I hope you skipped part of this :)
No. It was infromative.
Still it doesn't answers my question: why you need to trace the native code during mark phase. Why CompiledMethods, which represent the native code are not enough?
Auxuliary array.. okay. Lets assume that if CompiledMethod has a machine code, it requires 1 extra object on heap (auxuliary array), which of course could have some arbitrary references. But tracing this aux array can be done automatically during usual tracing phase, if it detects that: a) an oop is compiled method b) a method has native code then c) we also tracing auxiliary array
So then, when you tracing stuff, you deal with it in-place, per each discovered compiled method.
But what i see in Cog's #markPhase: is different:
[ trace roots ] [ trace & free stack pages ]. [ trace & free machine code ] << why it here?
I cannot say if it good or bad, robust or not, because largely i don't know the logic behind it.. But what i clearly see that such composition are not so nice for introducing ephemerons.
So, Eliot, please shed some more light on the purpose of #markAndTraceOrFreeMachineCode:
On 05/24/2011 08:44 PM, Igor Stasenko wrote
Even if we could assume that tracing and marking could be done without paying attention to the native code, fixing the references will still need some knowledge of native code.
Yes. But currently the border of my interest are not extends beyond mark phase.
well, it depends on how you are going to later fix the addresses. If you are, for example, using proxy/forwarders or threading the referrers, then you usually do this during the mark phase, and take advantage of that during the compact phase (if there's such a phase). I don't know nothing about Squeak's GC, how does it assign new addresses and do the compaction? does it have two GCs? (a faster, generational, and a slower for full compaction for example? does it have an incremental GC?)
Two observations about this:
. While a CompiledMethod is being executed in its native form, and if this same CompiledMethod changes itself, for example, the two versions of the CompiledMethod should be kept alive, and the only references to the literals in the old CompiledMethod could be the native code itself. Unless you somehow keep a reference to the old CompiledMethod (for example, in the stack).
A CompiledMethod could "change" itself only via #become:
uhm, not sure what you mean, what about something like:
thisContext sender method literalAt: 1 put: 'sarasa'
(I'm taking your syntax, and inventing what I don't know, use your imagination to understand :)
This will "kill" the reference to the literal from the CM, while the native code should still have it.
could be funnier, like changing the bytecodes, but that's somehow strange (thought NOT never seen).
If you just replacing old compiled method in class with a new one, nothing bad happens, since method activation record (aka context) keeps a reference to activated method and it
true if prologue pushes the address of the CM (we are talking about a JIT VM, right?), for what the prologue must have a pointer to the CM, which must be fixed if the CM changes. Same for:
Again, fixing refs may be needed during compaction phase. It depends on implementation, of course (you can generate native code which have no inlined literals, but refers to them via CompiledMethod as interpreter does).
You'll need a reference to the CM from native code to do this, unless of course you are doing all activations via some sort of interpreter/dispatcher, in which case you loose some speed you could gain by direct native-to-native direct method call. (I'm sure Eliot knows the name for this :)
Still it doesn't answers my question: why you need to trace the native code during mark phase. Why CompiledMethods, which represent the native code are not enough?
Again, not sure about Squeak, but if you use threading or forwarding you do that during the Mark phase, and take advantage of it latter (if there's any latter at all... I mean, some copying GCs with semi-spaces don't have anything else than a trace phase, in which they trace and copy)
Auxuliary array.. okay. Lets assume that if CompiledMethod has a machine code, it requires 1 extra object on heap (auxuliary array), which of course could have some arbitrary references. But tracing this aux array can be done automatically during usual tracing phase, if it detects that: a) an oop is compiled method b) a method has native code then c) we also tracing auxiliary array
right, you could do that, an implementation I know from very close has some of this auxiliary arrays, only three for all CMs.
But what i see in Cog's #markPhase: is different:
[ trace roots ] [ trace & free stack pages ]. [ trace & free machine code ] << why it here?
uhm, that's interesting. I think Eliot said that machine code has structure, it is interesting indeed, and lets the GC collect code too. Why there? I think anywhere during the tracing phase is the same, isn't it? It does look robust (aside from possible bugs, of course).
But what i clearly see that such composition are not so nice for introducing ephemerons.
That shouldn't be a problem, but of course it all depends on your implementation of ephemerons and how the rest of the code reuses tracing algorithms, so I can't say.
gera
On 25 May 2011 03:56, Gerardo Richarte gera@corest.com wrote:
On 05/24/2011 08:44 PM, Igor Stasenko wrote
Even if we could assume that tracing and marking could be done without paying attention to the native code, fixing the references will still need some knowledge of native code.
Yes. But currently the border of my interest are not extends beyond mark phase.
well, it depends on how you are going to later fix the addresses. If you are, for example, using proxy/forwarders or threading the referrers, then you usually do this during the mark phase, and take advantage of that during the compact phase (if there's such a phase). I don't know nothing about Squeak's GC, how does it assign new addresses and do the compaction? does it have two GCs? (a faster, generational, and a slower for full compaction for example? does it have an incremental GC?)
Two observations about this:
. While a CompiledMethod is being executed in its native form, and if this same CompiledMethod changes itself, for example, the two versions of the CompiledMethod should be kept alive, and the only references to the literals in the old CompiledMethod could be the native code itself. Unless you somehow keep a reference to the old CompiledMethod (for example, in the stack).
A CompiledMethod could "change" itself only via #become:
uhm, not sure what you mean, what about something like:
thisContext sender method literalAt: 1 put: 'sarasa'
(I'm taking your syntax, and inventing what I don't know, use your imagination to understand :)
This will "kill" the reference to the literal from the CM, while the native code should still have it.
could be funnier, like changing the bytecodes, but that's somehow strange (thought NOT never seen).
If you just replacing old compiled method in class with a new one, nothing bad happens, since method activation record (aka context) keeps a reference to activated method and it
true if prologue pushes the address of the CM (we are talking about a JIT VM, right?), for what the prologue must have a pointer to the CM, which must be fixed if the CM changes. Same for:
Again, fixing refs may be needed during compaction phase. It depends on implementation, of course (you can generate native code which have no inlined literals, but refers to them via CompiledMethod as interpreter does).
You'll need a reference to the CM from native code to do this, unless of course you are doing all activations via some sort of interpreter/dispatcher, in which case you loose some speed you could gain by direct native-to-native direct method call. (I'm sure Eliot knows the name for this :)
Still it doesn't answers my question: why you need to trace the native code during mark phase. Why CompiledMethods, which represent the native code are not enough?
Again, not sure about Squeak, but if you use threading or forwarding you do that during the Mark phase, and take advantage of it latter (if there's any latter at all... I mean, some copying GCs with semi-spaces don't have anything else than a trace phase, in which they trace and copy)
Auxuliary array.. okay. Lets assume that if CompiledMethod has a machine code, it requires 1 extra object on heap (auxuliary array), which of course could have some arbitrary references. But tracing this aux array can be done automatically during usual tracing phase, if it detects that: a) an oop is compiled method b) a method has native code then c) we also tracing auxiliary array
right, you could do that, an implementation I know from very close has some of this auxiliary arrays, only three for all CMs.
But what i see in Cog's #markPhase: is different:
[ trace roots ] [ trace & free stack pages ]. [ trace & free machine code ] << why it here?
uhm, that's interesting. I think Eliot said that machine code has structure, it is interesting indeed, and lets the GC collect code too. Why there? I think anywhere during the tracing phase is the same, isn't it? It does look robust (aside from possible bugs, of course).
But what i clearly see that such composition are not so nice for introducing ephemerons.
That shouldn't be a problem, but of course it all depends on your implementation of ephemerons and how the rest of the code reuses tracing algorithms, so I can't say.
For ephemerons there is a queue which should be considered after whole heap is already marked. Then each item in that queue should be considered and could trigger additional marking (because ephemeron's value should be traced only if it's key are reachable from other objects than ephemeron itself).
Because of that, no object should be considered as "free" until ephemeron queue is fully processed and no additional values found to trace.
So, if you put it like that:
[ mark usual stuff ] [ mark and free machine code ] [ process ephemerons queue ]
then it is wrong , because you can mistakenly free the machine code which reachable only via one of ephemerons. Or if you do it like that:
[ mark usual stuff ] [ process ephemerons queue ] [ mark and free machine code ]
then it is also wrong, since queue should be considered last. The only way how it can work is when you have unified trace procedure, which makes no difference between machine code and heap, and you postpone freeing any memory after ephemerons processing are done:
[ mark usual stuff ] << machine code, stack pages etc etc should be traced here [ process ephemerons queue ] << during processing queue, again it should also trace newly discovered reachable machine code, stack pages etc [ free machine code, stack pages etc ]
gera
On Tue, May 24, 2011 at 9:09 AM, Igor Stasenko siguctua@gmail.com wrote:
On 24 May 2011 16:58, Javier Burroni javier.burroni@gmail.com wrote:
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
The mail you posted is hard to follow for me, because i don't really understand what 'rescued ephemeron' means. Is it the one who initially seen without its key being marked, but then after full graph traversal has it key marked?
In the above a rescued ephemeron is an ephemeron with an unreachable key, an ephemeron which should be finalized. I don't think it is good terminology. I prefer bereaved ephemeron, since a bereaved ephemeron is one referring to an object that would die were it not for the reference from ephemerons. Other less poetic terms would be triggered, or active.
The ephemerons extension to GC are quite simple (it explains why it took me 1 day to get initial implementation working).
The only implication of ephemerons, that you need to fulfill is that you mark all reachable objects before analyzing ephemerons queue. And during analysis you have to make sure that again, you are marking all reachable objects discovered through ephemerons, whose keys are marked. If you obey the above rules, then there's not much to fear about. It will just work :)
-- Best regards, Igor Stasenko AKA sig.
On 24 May 2011 18:42, Eliot Miranda eliot.miranda@gmail.com wrote:
On Tue, May 24, 2011 at 9:09 AM, Igor Stasenko siguctua@gmail.com wrote:
On 24 May 2011 16:58, Javier Burroni javier.burroni@gmail.com wrote:
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
The mail you posted is hard to follow for me, because i don't really understand what 'rescued ephemeron' means. Is it the one who initially seen without its key being marked, but then after full graph traversal has it key marked?
In the above a rescued ephemeron is an ephemeron with an unreachable key, an ephemeron which should be finalized. I don't think it is good terminology. I prefer bereaved ephemeron, since a bereaved ephemeron is one referring to an object that would die were it not for the reference from ephemerons. Other less poetic terms would be triggered, or active.
oh.. so it is straightly opposite to what i was assuming. As to me there are no need for special terminology: it just an ephemeron who lost its key (because it turns to be the garbage). As a consequence of that, it no longer referencing its value strongly.
Btw, since i was reusing my previous finalization scheme for ephemerons, when ephemeron's key dies, you will be automatically notified, and could do anything you want for finalizing them. Except that i didn't yet thought deeply, what better scheme we could use there. But this is at image side anyways.
But it is more than that. You can get multiple notifications at different stages of ephemeron: - as i said, you got notification, once its key dies - but later, if you keep ephemeron and don't throw it away, you could also get a notification once its value dies. - of course if both key and value dying at the same moment (within single GC cycle), then you got only single notification.
(btw, by writing this, i found a bug, which are already fixed).
There was a caveat with finalization which calls #weakFinalizerCheck: for each weak reference replaced by nil for a single object. It is incorrect, because if analyzed object contains more than 1 weak reference, then it will call this method twice in a row, and will create a loop in a list
list head == oop oop next == oop
and the list tail will be lost.
The existing images are not affected by this bug, just because in WeakFinalizerItem there is only 1 weak reference which could die, so it is impossible by construction.
But not with Ephemerons: since for Ephemerons both key and value could die at once, and it will trigger this bug. So, i had to fix the #weakFinalizerCheck: to put finalizable oop into the list only when it's 'next' field are nil.
vm-dev@lists.squeakfoundation.org
-
Eliot Miranda -
Gerardo Richarte -
Igor Stasenko -
Javier Burroni