From: Perry C. <per...@us...> - 2003-05-06 20:26:43
|
One missing feature of Jikes's current and past GC system is Java's Reference class which includes soft, weak, phantom references and various reference queues. I am considering implementing this in the near future. Before doing so, I would like to solicit contributions from anyone who would like to share ideas or code. If you are interested, please erply on the mailing list or directly to me. Perry |
From: Eliot M. <mo...@cs...> - 2003-05-06 20:43:49
|
We implemented it here in 2.0.3 GCTk, Perry; you can contact Chris Hoffmann (hof...@cs...) about its status in 2.2 (it may already be done). -- Eliot |
From: Sergiy K. <se...@cs...> - 2003-06-24 04:43:41
|
Today I changed Jikes RVM stack from int[] to VM_WordArray throughout the system. Now I have this error during BootImageWriter.java execution: Exception in thread "main" java.lang.Error: BootImageWriter: com.ibm.JikesRVM.VM_WordArray@1e43847 is not in bootimage at BootImageWriterMessages.fail(BootImageWriterMessages.java:98) at BootImageMap.getImageOffset(BootImageMap.java:154) at BootImageWriter.main(BootImageWriter.java:536) with the following code at BootImageWriter.java: //-#if RVM_FOR_32_ADDR 536: bootRecord.spRegister = VM_Address.fromInt(bootImageAddress + BootImageMap.getImageOffset(startupStack) + (startupStack.length() << LOG_BYTES_IN_ADDRESS)); bootRecord.ipRegister = VM_Address.fromInt(bootImageAddress + BootImageMap.getImageOffset(startupCode)); //-#endif //-#if RVM_FOR_64_ADDR bootRecord.spRegister = VM_Address.fromLong(bootImageAddress + BootImageMap.getImageOffset(startupStack) + (startupStack.length() << LOG_BYTES_IN_ADDRESS)); bootRecord.ipRegister = VM_Address.fromLong(bootImageAddress + BootImageMap.getImageOffset(startupCode)); //-#endif I modified jconfigure to be sure that VM_WordArray is included in the boot image, but I still get this error. Sergiy |
From: David P G. <gr...@us...> - 2003-06-24 13:22:02
|
We left it as an int[] intentionally. It should be an int[]. It is NOT a VM_WordArray. For the same reason the jtoc remains an int[]. --dave |
From: Sergiy K. <se...@cs...> - 2003-06-24 20:15:25
|
Doesn't it violate JVM spec, which says that references should occupy one stack slot? I suspect it will not work if you reserve two stack slots for references, because java-to-bytecode compiler will assume only one slot. We ran into this problem before when we tried to reserve only one 8-byte wide stack slot for doubles and longs to save space. Anyway, what is you motivation behind this decision? Sergiy ----- Original Message ----- From: "David P Grove" <gr...@us...> To: <jik...@os...> Sent: Tuesday, June 24, 2003 4:21 AM Subject: Re: [Jikesrvm-core] 64-bit port stack > We left it as an int[] intentionally. It should be an int[]. It is NOT a > VM_WordArray. For the same reason the jtoc remains an int[]. > > --dave > > _______________________________________________ > Jikesrvm-core mailing list > Jik...@ww... > http://www-124.ibm.com/developerworks/oss/mailman/listinfo/jikesrvm-core |
From: Eliot M. <mo...@cs...> - 2003-06-26 23:54:24
|
>>>>> "David" == David P Grove <gr...@us...> writes: David> We left it as an int[] intentionally. It should be an int[]. David> It is NOT a VM_WordArray. For the same reason the jtoc remains David> an int[]. I guess I (for one) need more explanation. I agree that the jtoc can/should be an int[], since many of its elements require only word alignment, and we can simply leave gaps (or, more cleverly, fill them in with 32-bit items, if we like) when we force alignment on 64-bit items. But I don't see that logic for the stacks. -- Eliot |
From: David P G. <gr...@us...> - 2003-06-27 00:02:57
|
Sorry, Sergiy and I had some more off-list discussion. Basically, my argument is that probably the most accurate description of a stack is byte[]. It's just a hunk of raw memory that is pretty much never accessed via normal Java (I think growing a stack is the only case, and this goes out to memcopy anyways). The Java type has very little to do with the "data structure" of stack frames that the compilers/runtime system superimpose on top of this hunk of bytes. --dave |
From: Eliot M. <mo...@cs...> - 2003-06-27 00:11:08
|
>>>>> "David" == David P Grove <gr...@us...> writes: David> Sorry, Sergiy and I had some more off-list discussion. Basically, my David> argument is that probably the most accurate description of a stack is David> byte[]. It's just a hunk of raw memory that is pretty much never accessed David> via normal Java (I think growing a stack is the only case, and this goes David> out to memcopy anyways). The Java type has very little to do with the David> "data structure" of stack frames that the compilers/runtime system David> superimpose on top of this hunk of bytes. Thanks; I buy that -- E |
From: Eliot M. <mo...@cs...> - 2003-06-26 23:51:53
|
Not sure if VM_WordArray is the right choice. Certainly we used WORD[], which resolved to int[] in 32-bit and long[] on 64-bit. In the basline compiler, the slots are definitely 64 bits wide, and pretty much everything is 64-bit aligned in the stack. This seems right to me, and it works. Note that certain things need to be 64-bit aligned, since I think they have prepare/atrtempt applied to them, as 64-bit quantities .... -- E |
From: Chris H. <hof...@cs...> - 2003-05-08 20:27:54
|
Perry Cheng wrote: > > One missing feature of Jikes's current and past GC system is Java's > Reference class which includes soft, weak, phantom references and > various reference queues. I am considering implementing this in the > near future. Before doing so, I would like to solicit contributions > from anyone who would like to share ideas or code. If you are > interested, please erply on the mailing list or directly to me. > > Perry The implementations of the reference classes in GCTk are fairly different from what needs to be done for JMTk, although looking at what you did to handle finalization in general I think the final result will be easier to write and cleaner to read in JMTk (score one for JMTk!). I've made a stab at moving the key classes into JMTk, but there a few questions I have: 1) The Finalizer class resurrects objects simply by adding them to the Object[] named 'live'. I just want to confirm that that there is no "magic" that I'm missing and that the second call to StopTheWorldGC.processAllWork() made during collection is what ensures that these objects become live again. 2) If the objects were dead and then made live as above, I can assume it is guaranteed that after that second call Plan.isLive() will now return true and Plan.traceObject() will return the new address of the object (if it has been moved)? 3) I'm unsure of the best place to actually call Reference.clear() and Reference.enqueue(). The simplest thing is probably to do this in the FinalizationThread after calling Object.finalize(), but perhaps there is a better place. Chris -- Chris Hoffmann -- Dept. of Computer Science/UMass at Amherst http://www-ali.cs.umass.edu/~hoffmann |
From: Perry C. <per...@us...> - 2003-05-08 20:35:24
|
Chris, (1) You are right, the processAllWork basically retraces the objects in the resurrected objects so that finalization can proceed. (2) Yep. (3) What you suggest sounsd reasonable. But I can't really say without seeing the code. By the way, I am curious how you handle the soft references, in regards to the requirement that no OutOfMemory exception can be thrown until they are all cleared. Also, as a first cut, the implementation does not have to be perfect as long as finalizers still work correctly. Thanks for your help in this. Perry Chris Hoffmann <hof...@cs...> Sent by: jik...@ww... 05/08/2003 01:27 PM Please respond to jikesrvm-core To: jik...@ww... cc: Subject: Re: [Jikesrvm-core] Soft, Weak, and Phantom References Perry Cheng wrote: > > One missing feature of Jikes's current and past GC system is Java's > Reference class which includes soft, weak, phantom references and > various reference queues. I am considering implementing this in the > near future. Before doing so, I would like to solicit contributions > from anyone who would like to share ideas or code. If you are > interested, please erply on the mailing list or directly to me. > > Perry The implementations of the reference classes in GCTk are fairly different from what needs to be done for JMTk, although looking at what you did to handle finalization in general I think the final result will be easier to write and cleaner to read in JMTk (score one for JMTk!). I've made a stab at moving the key classes into JMTk, but there a few questions I have: 1) The Finalizer class resurrects objects simply by adding them to the Object[] named 'live'. I just want to confirm that that there is no "magic" that I'm missing and that the second call to StopTheWorldGC.processAllWork() made during collection is what ensures that these objects become live again. 2) If the objects were dead and then made live as above, I can assume it is guaranteed that after that second call Plan.isLive() will now return true and Plan.traceObject() will return the new address of the object (if it has been moved)? 3) I'm unsure of the best place to actually call Reference.clear() and Reference.enqueue(). The simplest thing is probably to do this in the FinalizationThread after calling Object.finalize(), but perhaps there is a better place. Chris -- Chris Hoffmann -- Dept. of Computer Science/UMass at Amherst http://www-ali.cs.umass.edu/~hoffmann _______________________________________________ Jikesrvm-core mailing list Jik...@ww... http://www-124.ibm.com/developerworks/oss/mailman/listinfo/jikesrvm-core |
From: Chris H. <hof...@cs...> - 2003-05-08 22:43:13
|
Perry Cheng wrote: > By the way, I am curious how you handle the soft references, in regards to the > requirement that no OutOfMemory exception can be thrown > until they are all cleared. Well.... As implemented in GCTk soft references were treated as weak references, hence objects that were only softly reachable were immediately killed and never kept "artificially" alive, so the issue didn't come up. In my sketched-out code for JMTk I have a little stub that would allow truly softly reachable objects and a comment about clearing the cache of softly reachable objects before running out of memory, but I haven't thought much about how you'd do that! Do you have some ideas? By the way, I should mention that most of the GCTk reference and finalization work was not done by me but by a grad student, Xiaotao Liu, last summer. Even if not a lot of his actual code makes it into JMTk, we have him to thank for finally beating into my head why the heck you'd want phantom references to have such weird semantics! Chris -- Chris Hoffmann -- Dept. of Computer Science/UMass at Amherst http://www-ali.cs.umass.edu/~hoffmann |
From: Eliot M. <mo...@cs...> - 2003-05-08 23:09:24
|
... and if it's any help to you to know, I helped Xiaotao design this and ehcked his implementation code. -- Eliot |
From: Chris H. <hof...@cs...> - 2003-05-09 21:16:50
|
Something I just noticed: Finalizer.addLive() resizes the live object array by calling 'new Object[]' if it isn't big enough. But this would be called during StopTheWorldGC.collect(). Is it really legal now to allocate memory in the middle of a GC?! If not, since the live array never needs to be bigger than the candidate array, it can be resized at the same time that the candidate array is resized, which only happens at places where it is definitely safe to allocate new memory. Chris -- Chris Hoffmann -- Dept. of Computer Science/UMass at Amherst http://www-ali.cs.umass.edu/~hoffmann |
From: Perry C. <per...@us...> - 2003-05-09 21:45:27
|
Hi Chris, You are right in that it is generally unsafe to call new during a StopTheWorld GC. Re-sizing it along with addCandidate might not work though since the processing of finalizers is asynchronous so that the size of the live array can outstrip the candidate array. I will have to do something a bit different like make sure the amount of space left in live can always accomodate the total amount in the live array during the resizing operation. By the way, do not feel constrained by the way the finalization is currently done in JMTk since the right design decision may well be for the Java references implementation to subsume the current treatment of finalizers. Perry Chris Hoffmann <hof...@cs...> Sent by: jik...@ww... 05/09/2003 02:16 PM Please respond to jikesrvm-core To: jik...@ww... cc: Subject: Re: [Jikesrvm-core] Soft, Weak, and Phantom References Something I just noticed: Finalizer.addLive() resizes the live object array by calling 'new Object[]' if it isn't big enough. But this would be called during StopTheWorldGC.collect(). Is it really legal now to allocate memory in the middle of a GC?! If not, since the live array never needs to be bigger than the candidate array, it can be resized at the same time that the candidate array is resized, which only happens at places where it is definitely safe to allocate new memory. Chris -- Chris Hoffmann -- Dept. of Computer Science/UMass at Amherst http://www-ali.cs.umass.edu/~hoffmann _______________________________________________ Jikesrvm-core mailing list Jik...@ww... http://www-124.ibm.com/developerworks/oss/mailman/listinfo/jikesrvm-core |
From: Chris H. <hof...@cs...> - 2003-05-09 22:35:41
|
Perry Cheng wrote: > > Hi Chris, > > You are right in that it is generally unsafe to call new during a > StopTheWorld GC. Re-sizing it along with addCandidate might not work > though since the processing of finalizers is asynchronous so that the > size of the live array can outstrip the candidate array. I will have > to do something a bit different like make sure the amount of space > left in live can always accomodate the total amount in the live array > during the resizing operation. Ah, true. Instead of "total amount in the live array" do you mean "candidate" array? That is, on each addCandidate call, ensure size of the unused part of live >= size of used part of candidate > > By the way, do not feel constrained by the way the finalization is > currently done in JMTk since the right design decision may well be for > the Java references implementation to subsume the current treatment of > finalizers. Well I like the implementation of the finalization! And the general idea seems to work pretty well for references. It just seems this approach doesn't fit in so well with traditional reference counting (i.e. immediate release of an object's memory). But I'm not convinced that a good scheme for traditional reference counting would work well for mark/sweep or copying collectors. I'm leaning toward the idea that there should be two different policies implemented, the one actually used being the appropriate one for the type of collector. Chris -- Chris Hoffmann -- Dept. of Computer Science/UMass at Amherst http://www-ali.cs.umass.edu/~hoffmann |
From: Steve B. <Ste...@an...> - 2003-05-12 02:53:59
|
I still have not had time to get my head around all the issues, so take this with a grain of salt... . The ref count collector extends StopTheWorldGC because it *is* stop the world :-) Yes, the current implementation is *not* concurrent, it only reclaims objects during periodic stop-the-world GCs. Incs and decs accumulate in buffers which are processed during GCs. Soon we will have concurrent cycle detection, but the core collection will remain stop the world. . I have not yet got to examining how the mechanisms work, but I imagine it may not be necessary to have multiple flavors of ref count, but instead to essentially use tracing for these falavors of reference... What are the timing issues here? I think it might help for Chris and I (and anyone else) to chat on the phone (the bandwidth here is too low). I am going away Tuesday (late Monday EST) until the start of next week. Perhaps we can talk next week if it is not too late. Otherwise I could talk on Monday evening. I would not be available before about 7 or 8 pm EST on Monday. --Steve |
From: Chris H. <hof...@cs...> - 2003-05-12 17:13:16
|
Steve, It only occurred to me later that even a pure pay-as-you-go reference count collector will still have a distinct collection phase to clean up objects involved in cycles. At least I don't remember any workable algorithms that don't. So I think the same implementation of References will work for RC as the other detectors. I think the only addition needs to be to an extra bit in the object header that says this object has soft, weak, and/or phantom pointers to it. If that bit is set then "your" standard RC will not collect the object when the ref count is zero but will leave it to "my" special processing to determine when it is time to get rid of it. I can be available to talk Monday evening if we think it's necessary. Chris Steve Blackburn wrote: > > I still have not had time to get my head around all the issues, so > take this with a grain of salt... > > . The ref count collector extends StopTheWorldGC because it *is* stop > the world :-) Yes, the current implementation is *not* concurrent, > it only reclaims objects during periodic stop-the-world GCs. Incs > and decs accumulate in buffers which are processed during GCs. Soon > we will have concurrent cycle detection, but the core collection > will remain stop the world. > > . I have not yet got to examining how the mechanisms work, but I > imagine it may not be necessary to have multiple flavors of ref > count, but instead to essentially use tracing for these falavors > of reference... > > What are the timing issues here? I think it might help for Chris and I > (and anyone else) to chat on the phone (the bandwidth here is too low). > I am going away Tuesday (late Monday EST) until the start of next week. > Perhaps we can talk next week if it is not too late. Otherwise I could > talk on Monday evening. I would not be available before about 7 or 8 pm > EST on Monday. -- Chris Hoffmann -- Dept. of Computer Science/UMass at Amherst http://www-ali.cs.umass.edu/~hoffmann |
From: Steve B. <Ste...@an...> - 2003-05-13 05:24:58
|
These plans sound good, but I've run out of time, so I won't be able to engage further until I return on Monday. I'm off to the Northern Territory to feed some crocodiles ;-) Cheers, --Steve |
From: Eliot M. <mo...@cs...> - 2003-05-12 04:49:53
|
Let me further observe that there is a somewhat hard-to-decode rule about one of the categories of weak references (the soft ones, if I recall correctly), that they must be detected and cleared atomically as a group. Specifically, if object Z is soft-reachable from soft references X and Y, then X and Y need to be cleared at the same time, guaranteeing that if Z is soft-reachable from _any_ soft reference that is cleared, then _all_ those soft references are cleared. It is simplest to clear all the soft references whose referents are not more strongly reachable. The other categories do not have this "group atomicity" requirement. Since the ref counting collection is stop-the-world / batch, the process will be easier than in a concurrent RC collector (I would really need to think on that one!). The key is not to reclaim immediately an object that is more weakly reachable but not strongly reachable. Here is an approach that I believe will work: - Include the weaker kinds of references in the ref count - Each kind of weaker reference is kept on a list of refs of that category - After processing normal incs/decs, which may allow some objects to be reclaimed, go through the weak references (by category, strongest to weakest), and decrement their referents. After processing a category, go back through that category's list of references and increment the count back, BUT ONLY IF the count is not zero. For references whose referent's count is zero, do the clearing / queueing work implied. - Note: It is important to do the processing in a second pass over the list since a referent may be the target of multiple references. Processing only at the moment the count goes to zero might miss processing other references to the same referent. - The same approach presumably works for finalization as well. Hope this helps .... -- Eliot |
From: David P G. <gr...@us...> - 2003-05-12 15:03:43
|
> It is simplest to clear all the > soft references whose referents are not more strongly reachable. True, but if I understand what you are saying, the performance of this solution is pretty unappealing. The primary use of soft references is to cache things. If the cache is completely wiped every GC, then it isn't very useful to the application. --dave |
From: Eliot M. <mo...@cs...> - 2003-05-12 15:43:41
|
>>>>> "David" == David P Grove <gr...@us...> writes: >> It is simplest to clear all the >> soft references whose referents are not more strongly reachable. David> True, but if I understand what you are saying, the performance of this David> solution is pretty unappealing. The primary use of soft references is to David> cache things. If the cache is completely wiped every GC, then it isn't David> very useful to the application. Oh, I agree; what we actually do is clear them only if "regular" collection did not find enough garbage. So, we make a decision after the first round of GC whether to keep or clear, and then apply that decision uniformly to all the soft res. -- Eliot |
From: Chris H. <hof...@cs...> - 2003-05-12 17:05:29
|
Here's the design as I see it this morning. (Subject to change once I've had my morning coffee and bagel....) As I mentioned in my separate reply to Steve, I don't think we need to include the non-strong references in the reference count. In fact, I don't think we want to as I, at least, would like Plan.isLive() to return false only if the object is not strongly reachable, which would be hard to do if the other references affect that count. It suffices to have a single bit in the object that indicates that there are non-strong references to the object. And in fact this bit is only needed for RC collection, and perhaps not even in Steve's implementation since it doesn't free objects as soon as it detects the strong RC has gone to zero. As Eliot says, each soft/weak/phantom reference object is kept on its own queue. A simplification from finalization is that we don't need the complexity of maintaining separate candidate and live arrays and worrying about resizing them safely, etc.: the java.lang.ref.Reference object itself can contain fields that enable their instances to be chained together into linked lists. It also contains fields that have the VM_Address of the referent and the referent as a java.lang.Object. In most cases the latter is usually null since the whole idea is to allow the objects to die if necessary! In soft references, though it *is* filled in, as we want them to stay alive unless we get an OutOfMemory exception. Weak references are fairly easy, and I need to think about phantoms a bit more, but soft reference processing could look something like the following: In StopTheWorldGC.collect() * (optional) heuristic preprocessing: an application-specific(?) algorithm could decide that certain soft references should be cleared before we hit the panic stage, or be cleared only if they are not strongly reachable any more. * initial trace * process lists of objects needing finalization and only weakly or phantomly reachable. By processing these lists in order of strength we can make sure we process referents in the proper order. * potential second trace if any objects were resurrected by the above. Somewhere (perhaps VM_Runtime.resolvedNewScalar and family?) we trap OutOfMemory exceptions. If we get one, we call a new VM_Interface method that is supposed to scavenge for all possible extra memory. This would in turn clear all the SoftReference objects. We then call VM_Interface.gc() again, and try to allocate again. If we still get OutOfMemory, then we have no choice but to propagate that back to the application. [Optionally, the reclamation of SoftReferences could be an iterative algorithm, releasing objects in an application-specific way based on how likely they are to be used again. But this is probably overkill.] Note that there is no explicit soft/weak/phantom reference count maintained anywhere. This information is implicit in the number of times an object is refered to by Reference objects in the various lists. Chris Eliot Moss wrote: > > Let me further observe that there is a somewhat hard-to-decode rule about > one of the categories of weak references (the soft ones, if I recall > correctly), that they must be detected and cleared atomically as a > group. Specifically, if object Z is soft-reachable from soft references X > and Y, then X and Y need to be cleared at the same time, guaranteeing that > if Z is soft-reachable from _any_ soft reference that is cleared, then > _all_ those soft references are cleared. It is simplest to clear all the > soft references whose referents are not more strongly reachable. > > The other categories do not have this "group atomicity" requirement. > > Since the ref counting collection is stop-the-world / batch, the process > will be easier than in a concurrent RC collector (I would really need to > think on that one!). The key is not to reclaim immediately an object that > is more weakly reachable but not strongly reachable. > > Here is an approach that I believe will work: > > - Include the weaker kinds of references in the ref count > - Each kind of weaker reference is kept on a list of refs of that category > - After processing normal incs/decs, which may allow some objects to be > reclaimed, go through the weak references (by category, strongest to > weakest), and decrement their referents. After processing a category, go > back through that category's list of references and increment the count > back, BUT ONLY IF the count is not zero. For references whose referent's > count is zero, do the clearing / queueing work implied. > - Note: It is important to do the processing in a second pass over the list > since a referent may be the target of multiple references. Processing > only at the moment the count goes to zero might miss processing other > references to the same referent. > - The same approach presumably works for finalization as well. > > Hope this helps .... > > -- Eliot > _______________________________________________ > Jikesrvm-core mailing list > Jik...@ww... > http://www-124.ibm.com/developerworks/oss/mailman/listinfo/jikesrvm-core -- Chris Hoffmann -- Dept. of Computer Science/UMass at Amherst http://www-ali.cs.umass.edu/~hoffmann |
From: Chris H. <hof...@cs...> - 2003-05-15 21:45:45
|
I've sent to the contrib list a set of patches that will enable the various Reference classes to work in Jikes RVM, built and successfully tested against the latest CVS head. One thing that I know needs some thought is the synchronization/locking to ensure multithread safety. I based things loosely on the way Finalizer.java was doing the handoff from the gc to the finalizer thread, so possibly everything really is safe already. On the other hand, there are actually two locks: a VM_Synchronizer that Julian Dolby had already added to the java/lang/ref/Reference class and a JMKT Lock object such as was used by Perry in Finalizer.java. I tried to unify these and got an apparent deadlock.... I guess I need to learn more about all the flavors of locks in Jikes! Eliot and I talked about the differences between sweeping/copying collectors and reference counting ones and I think we agree that there are fundamental differences in the way Reference objects are handled in the two cases -- e.g. in the first you need an interface to make seemingly dead objects alive, in the latter you need to kill seemingly live objects. Once I have a concrete RC collector to work with it will be a little clearer to me whether References can be handled with minor variations in the ReferenceProcessor class I just submitted or if I need two radically different ReferenceProcessor implementations. Chris -- Chris Hoffmann -- Dept. of Computer Science/UMass at Amherst http://www-ali.cs.umass.edu/~hoffmann |
From: Steve B. <Ste...@an...> - 2003-05-19 10:47:25
|
Hi, Back after a brief break... > Once I have a concrete RC collector to work with it... What do you need in particular? There is a working RC collector there now (RefCount). Let me know if you need something more. Cheers, --Steve |