2 * Copyright (C) 2014, United States Government, as represented by the
3 * Administrator of the National Aeronautics and Space Administration.
6 * The Java Pathfinder core (jpf-core) platform is licensed under the
7 * Apache License, Version 2.0 (the "License"); you may not use this file except
8 * in compliance with the License. You may obtain a copy of the License at
10 * http://www.apache.org/licenses/LICENSE-2.0.
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
19 package gov.nasa.jpf.vm;
21 import java.util.ArrayList;
22 import java.util.HashMap;
23 import java.util.Iterator;
26 import gov.nasa.jpf.Config;
27 import gov.nasa.jpf.JPFException;
28 import gov.nasa.jpf.util.ArrayObjectQueue;
29 import gov.nasa.jpf.util.IntTable;
30 import gov.nasa.jpf.util.IntVector;
31 import gov.nasa.jpf.util.ObjectQueue;
32 import gov.nasa.jpf.util.Processor;
35 * this is an abstract root for Heap implementations, providing a standard
36 * mark&sweep collector, change attribute management, and generic pinDownList,
37 * weakReference and internString handling
39 * The concrete Heap implementors have to provide the ElementInfo collection
40 * and associated getters, allocators and iterators
42 public abstract class GenericHeap implements Heap, Iterable<ElementInfo> {
44 static abstract class GenericHeapMemento implements Memento<Heap> {
45 // those can be simply copied
47 IntVector pinDownList;
48 Map<Integer,IntTable<String>> internStringsMap;
50 protected GenericHeapMemento (GenericHeap heap){
51 // these are copy-on-first-write, so we don't have to clone
52 pinDownList = heap.pinDownList;
53 internStringsMap = heap.internStringsMap;
54 attributes = heap.attributes & ATTR_STORE_MASK;
60 public Heap restore (Heap inSitu) {
61 GenericHeap heap = (GenericHeap) inSitu;
62 heap.pinDownList = pinDownList;
63 heap.internStringsMap = internStringsMap;
64 heap.attributes = attributes;
65 heap.liveBitValue = false; // always start with false after a restore
71 protected class ElementInfoMarker implements Processor<ElementInfo>{
73 public void process (ElementInfo ei) {
74 ei.markRecursive( GenericHeap.this); // this might in turn call queueMark
80 // list of pinned down references (this is only efficient for a small number of objects)
81 // this is copy-on-first-write
82 protected IntVector pinDownList;
85 // this is copy-on-first-write, it is created on demand upon adding the first interned string,
86 // and it includes IntTable per process.
87 protected Map<Integer,IntTable<String>> internStringsMap;
89 // the usual drill - the lower 2 bytes are sticky, the upper two ones
90 // hold change status and transient (transition local) flags
91 protected int attributes;
93 static final int ATTR_GC = 0x0001;
94 static final int ATTR_OUT_OF_MEMORY = 0x0002;
95 static final int ATTR_RUN_FINALIZER = 0x0004;
97 static final int ATTR_ELEMENTS_CHANGED = 0x10000;
98 static final int ATTR_PINDOWN_CHANGED = 0x20000;
99 static final int ATTR_INTERN_CHANGED = 0x40000;
100 static final int ATTR_ATTRIBUTE_CHANGED = 0x80000;
103 static final int ATTR_STORE_MASK = 0x0000ffff;
104 static final int ATTR_ANY_CHANGED = (ATTR_ELEMENTS_CHANGED | ATTR_PINDOWN_CHANGED | ATTR_INTERN_CHANGED | ATTR_ATTRIBUTE_CHANGED);
107 //--- these objects are only used during gc
109 // used to keep track of marked WeakRefs that might have to be updated (no need to restore, only transient use during gc)
110 protected ArrayList<ElementInfo> weakRefs;
112 protected ObjectQueue<ElementInfo> markQueue = new ArrayObjectQueue<ElementInfo>();
114 // this is set to false upon backtrack/restore
115 protected boolean liveBitValue;
117 protected ElementInfoMarker elementInfoMarker = new ElementInfoMarker();
119 // the number of live objects
120 // <2do> currently only defined after gc
121 protected int nLiveObjects;
125 public GenericHeap (Config config, KernelState ks){
128 pinDownList = new IntVector(256);
129 attributes |= ATTR_PINDOWN_CHANGED; // no need to clone on next add
131 if (config.getBoolean("vm.finalize", true)){
132 attributes |= ATTR_RUN_FINALIZER;
135 if (config.getBoolean("vm.sweep",true)){
136 attributes |= ATTR_GC;
141 protected DynamicElementInfo createElementInfo (int objref, ClassInfo ci, Fields f, Monitor m, ThreadInfo ti){
142 return new DynamicElementInfo( objref,ci,f,m,ti);
145 //--- pinDown handling
146 protected void addToPinDownList (int objref){
147 if ((attributes & ATTR_PINDOWN_CHANGED) == 0) {
148 pinDownList = pinDownList.clone();
149 attributes |= ATTR_PINDOWN_CHANGED;
151 pinDownList.add(objref);
154 protected void removeFromPinDownList (int objref){
155 if ((attributes & ATTR_PINDOWN_CHANGED) == 0) {
156 pinDownList = pinDownList.clone();
157 attributes |= ATTR_PINDOWN_CHANGED;
159 pinDownList.removeFirst(objref);
163 public void registerPinDown(int objref){
164 ElementInfo ei = getModifiable(objref);
166 if (ei.incPinDown()){
167 addToPinDownList(objref);
170 throw new JPFException("pinDown reference not a live object: " + objref);
175 public void releasePinDown(int objref){
176 ElementInfo ei = getModifiable(objref);
178 if (ei.decPinDown()){
179 removeFromPinDownList(objref);
182 throw new JPFException("pinDown reference not a live object: " + objref);
185 void markPinDownList (){
186 if (pinDownList != null){
187 int len = pinDownList.size();
188 for (int i=0; i<len; i++){
189 int objref = pinDownList.get(i);
195 //--- weak reference handling
198 public void registerWeakReference (ElementInfo ei) {
199 if (weakRefs == null) {
200 weakRefs = new ArrayList<ElementInfo>();
207 * reset all weak references that now point to collected objects to 'null'
208 * NOTE: this implementation requires our own Reference/WeakReference implementation, to
209 * make sure the 'ref' field is the first one
211 protected void cleanupWeakRefs () {
212 if (weakRefs != null) {
213 for (ElementInfo ei : weakRefs) {
214 Fields f = ei.getFields();
215 int ref = f.getIntValue(0); // watch out, the 0 only works with our own WeakReference impl
216 if (ref != MJIEnv.NULL) {
217 ElementInfo refEi = get(ref);
218 if ((refEi == null) || (refEi.isNull())) {
219 ei = ei.getModifiableInstance();
220 // we need to make sure the Fields are properly state managed
221 ei.setReferenceField(ei.getFieldInfo(0), MJIEnv.NULL);
230 // NOTE - this is where to assert if this index isn't occupied yet, since only concrete classes know
231 // if there can be collisions, and how elements are stored
233 protected abstract AllocationContext getSUTAllocationContext (ClassInfo ci, ThreadInfo ti);
234 protected abstract AllocationContext getSystemAllocationContext (ClassInfo ci, ThreadInfo ti, int anchor);
237 * this is called for newXX(..) allocations that are SUT thread specific, i.e. in response to
238 * a explicit NEW or xNEWARRAY instruction that should take the allocating thread into account
240 protected abstract int getNewElementInfoIndex (AllocationContext ctx);
244 protected ElementInfo createObject (ClassInfo ci, ThreadInfo ti, int objref) {
245 // create the thing itself
246 Fields f = ci.createInstanceFields();
247 Monitor m = new Monitor();
248 ElementInfo ei = createElementInfo( objref, ci, f, m, ti);
252 attributes |= ATTR_ELEMENTS_CHANGED;
254 // and do the default (const) field initialization
255 ci.initializeInstanceData(ei, ti);
257 vm.notifyObjectCreated(ti, ei);
259 // note that we don't return -1 if 'outOfMemory' (which is handled in
260 // the NEWxx bytecode) because our allocs are used from within the
261 // exception handling of the resulting OutOfMemoryError (and we would
262 // have to override it, since the VM should guarantee proper exceptions)
268 public ElementInfo newObject(ClassInfo ci, ThreadInfo ti) {
269 AllocationContext ctx = getSUTAllocationContext( ci, ti);
270 int index = getNewElementInfoIndex( ctx);
271 ElementInfo ei = createObject( ci, ti, index);
277 public ElementInfo newSystemObject (ClassInfo ci, ThreadInfo ti, int anchor) {
278 AllocationContext ctx = getSystemAllocationContext( ci, ti, anchor);
279 int index = getNewElementInfoIndex( ctx);
280 ElementInfo ei = createObject( ci, ti, index);
284 protected ElementInfo createArray (String elementType, int nElements, ClassInfo ci, ThreadInfo ti, int objref) {
286 Fields f = ci.createArrayFields(ci.getName(), nElements, Types.getTypeSize(elementType), Types.isReference(elementType));
287 Monitor m = new Monitor();
288 DynamicElementInfo ei = createElementInfo( objref, ci, f, m, ti);
292 attributes |= ATTR_ELEMENTS_CHANGED;
294 vm.notifyObjectCreated(ti, ei);
299 protected ClassInfo getArrayClassInfo (ThreadInfo ti, String elementType) {
300 String type = "[" + elementType;
301 SystemClassLoaderInfo sysCl = ti.getSystemClassLoaderInfo();
302 ClassInfo ciArray = sysCl.getResolvedClassInfo(type);
304 if (!ciArray.isInitialized()) {
305 // we do this explicitly here since there are no clinits for array classes
306 ciArray.registerClass(ti);
307 ciArray.setInitialized();
314 public ElementInfo newArray(String elementType, int nElements, ThreadInfo ti) {
315 // see newObject for OOM simulation
316 ClassInfo ci = getArrayClassInfo(ti, elementType);
317 AllocationContext ctx = getSUTAllocationContext( ci, ti);
319 int index = getNewElementInfoIndex( ctx);
320 ElementInfo ei = createArray( elementType, nElements, ci, ti, index);
326 public ElementInfo newSystemArray(String elementType, int nElements, ThreadInfo ti, int anchor) {
327 // see newObject for OOM simulation
328 ClassInfo ci = getArrayClassInfo(ti, elementType);
329 AllocationContext ctx = getSystemAllocationContext( ci, ti, anchor);
331 int index = getNewElementInfoIndex( ctx);
332 ElementInfo ei = createArray( elementType, nElements, ci, ti, index);
339 protected ElementInfo initializeStringObject( String str, int index, int vref) {
340 ElementInfo ei = getModifiable(index);
341 ei.setReferenceField("value", vref);
343 ElementInfo eVal = getModifiable(vref);
344 CharArrayFields cf = (CharArrayFields)eVal.getFields();
345 cf.setCharValues(str.toCharArray());
350 protected ElementInfo newString (ClassInfo ciString, ClassInfo ciChars, String str, ThreadInfo ti, AllocationContext ctx) {
352 //--- the string object itself
353 int sRef = getNewElementInfoIndex( ctx);
354 createObject( ciString, ti, sRef);
356 //--- its char[] array
357 ctx = ctx.extend(ciChars, sRef);
358 int vRef = getNewElementInfoIndex( ctx);
359 createArray( "C", str.length(), ciChars, ti, vRef);
361 ElementInfo ei = initializeStringObject(str, sRef, vRef);
366 public ElementInfo newString(String str, ThreadInfo ti){
368 SystemClassLoaderInfo sysCl = ti.getSystemClassLoaderInfo();
369 ClassInfo ciString = sysCl.getStringClassInfo();
370 ClassInfo ciChars = sysCl.getCharArrayClassInfo();
372 AllocationContext ctx = getSUTAllocationContext( ciString, ti);
373 return newString( ciString, ciChars, str, ti, ctx);
381 public ElementInfo newSystemString (String str, ThreadInfo ti, int anchor) {
383 SystemClassLoaderInfo sysCl = ti.getSystemClassLoaderInfo();
384 ClassInfo ciString = sysCl.getStringClassInfo();
385 ClassInfo ciChars = sysCl.getCharArrayClassInfo();
387 AllocationContext ctx = getSystemAllocationContext( ciString, ti, anchor);
388 return newString( ciString, ciChars, str, ti, ctx);
396 public ElementInfo newInternString (String str, ThreadInfo ti) {
397 if(internStringsMap==null) {
398 internStringsMap = vm.getInitialInternStringsMap();
401 int prcId = ti.getApplicationContext().getId();
402 IntTable.Entry<String> e = internStringsMap.get(prcId).get(str);
406 ElementInfo ei = newString( str, ti);
407 int index = ei.getObjectRef();
409 // new interned Strings are always pinned down
411 addToPinDownList(index);
412 addToInternStrings(str, index, prcId);
425 protected void addToInternStrings (String str, int objref, int prcId) {
426 if ((attributes & ATTR_INTERN_CHANGED) == 0){
427 // shallow copy all interned strings tables
428 internStringsMap = new HashMap<Integer,IntTable<String>>(internStringsMap);
430 // only clone the interned strings table of the current process
431 internStringsMap.put(prcId, internStringsMap.get(prcId).clone());
433 // just cloned, no need to clone on the next add
434 attributes |= ATTR_INTERN_CHANGED;
436 internStringsMap.get(prcId).add(str, objref);
441 public ElementInfo newSystemThrowable (ClassInfo ciThrowable, String details, int[] stackSnapshot, int causeRef,
442 ThreadInfo ti, int anchor) {
443 SystemClassLoaderInfo sysCl = ti.getSystemClassLoaderInfo();
444 ClassInfo ciString = sysCl.getStringClassInfo();
445 ClassInfo ciChars = sysCl.getCharArrayClassInfo();
447 //--- the Throwable object itself
448 AllocationContext ctx = getSystemAllocationContext( ciThrowable, ti, anchor);
449 int xRef = getNewElementInfoIndex( ctx);
450 ElementInfo eiThrowable = createObject( ciThrowable, ti, xRef);
452 //--- the detailMsg field
453 if (details != null) {
454 AllocationContext ctxString = ctx.extend( ciString, xRef);
455 ElementInfo eiMsg = newString( ciString, ciChars, details, ti, ctxString);
456 eiThrowable.setReferenceField("detailMessage", eiMsg.getObjectRef());
459 //--- the stack snapshot field
460 ClassInfo ciSnap = getArrayClassInfo(ti, "I");
461 AllocationContext ctxSnap = ctx.extend(ciSnap, xRef);
462 int snapRef = getNewElementInfoIndex( ctxSnap);
463 ElementInfo eiSnap = createArray( "I", stackSnapshot.length, ciSnap, ti, snapRef);
464 int[] snap = eiSnap.asIntArray();
465 System.arraycopy( stackSnapshot, 0, snap, 0, stackSnapshot.length);
466 eiThrowable.setReferenceField("snapshot", snapRef);
468 //--- the cause field
469 eiThrowable.setReferenceField("cause", (causeRef != MJIEnv.NULL)? causeRef : xRef);
475 //--- abstract accessors
478 * these methods abstract away the container type used in GenericHeap subclasses
482 * internal setter used during allocation
486 protected abstract void set (int index, ElementInfo ei);
489 * public getter to access but not change ElementInfos
492 public abstract ElementInfo get (int ref);
496 * public getter to access modifiable ElementInfos;
499 public abstract ElementInfo getModifiable (int ref);
503 * internal remover used by generic sweep
505 protected abstract void remove (int ref);
511 * return Iterator for all non-null ElementInfo entries
514 public abstract Iterator<ElementInfo> iterator();
517 public abstract Iterable<ElementInfo> liveObjects();
520 //--- garbage collection
522 public boolean isGcEnabled (){
523 return (attributes & ATTR_GC) != 0;
526 public void setGcEnabled (boolean doGC) {
527 if (doGC != isGcEnabled()) {
529 attributes |= ATTR_GC;
531 attributes &= ~ATTR_GC;
533 attributes |= ATTR_ATTRIBUTE_CHANGED;
538 public void unmarkAll(){
539 for (ElementInfo ei : liveObjects()){
545 * add a non-null, not yet marked reference to the markQueue
547 * called from ElementInfo.markRecursive(). We don't want to expose the
548 * markQueue since a copying collector might not have it
551 public void queueMark (int objref){
552 if (objref == MJIEnv.NULL) {
556 ElementInfo ei = get(objref);
557 if (!ei.isMarked()){ // only add objects once
564 * called during non-recursive phase1 marking of all objects reachable
569 public void markStaticRoot (int objref) {
570 if (objref != MJIEnv.NULL) {
576 * called during non-recursive phase1 marking of all objects reachable
581 public void markThreadRoot (int objref, int tid) {
582 if (objref != MJIEnv.NULL) {
588 * this implementation uses a generic ElementInfo iterator, it can be replaced
589 * with a more efficient container specific version
591 protected void sweep () {
592 ThreadInfo ti = vm.getCurrentThread();
593 int tid = ti.getId();
594 boolean isThreadTermination = ti.isTerminated();
597 if(vm.finalizersEnabled()) {
598 markFinalizableObjects();
601 // now go over all objects, purge the ones that are not live and reset attrs for rest
602 for (ElementInfo ei : this){
604 if (ei.isMarked()){ // live object, prepare for next transition & gc cycle
606 ei.setAlive(liveBitValue);
608 ei.cleanUp(this, isThreadTermination, tid);
612 ei.processReleaseActions();
614 vm.notifyObjectReleased(ti, ei);
615 remove(ei.getObjectRef());
622 protected void markFinalizableObjects () {
623 FinalizerThreadInfo tiFinalizer = vm.getFinalizerThread();
625 if (tiFinalizer != null){
626 for (ElementInfo ei : this) {
627 if (!ei.isMarked() && ei.hasFinalizer() && !ei.isFinalized()) {
628 ei = tiFinalizer.getFinalizerQueuedInstance(ei);
629 ei.setMarked(); // make sure it's not collected before the finalizerQueue has been processed
630 ei.markRecursive(this);
636 protected void mark () {
639 //--- mark everything in our root set
641 vm.getThreadList().markRoots(this); // mark thread stacks
642 vm.getClassLoaderList().markRoots(this); // mark all static references
644 //--- trace all entries - this gets recursive
645 markQueue.process(elementInfoMarker);
653 liveBitValue = !liveBitValue;
657 // at this point all live objects are marked
660 cleanupWeakRefs(); // for potential nullification
662 vm.processPostGcActions();
667 * clean up reference values that are stored outside of reference fields
668 * called from KernelState to process live ElementInfos after GC has finished
669 * and only live objects remain in the heap.
671 * <2do> full heap enumeration is BAD - check if this can be moved into the sweep loop
674 public void cleanUpDanglingReferences() {
675 ThreadInfo ti = ThreadInfo.getCurrentThread();
676 int tid = ti.getId();
677 boolean isThreadTermination = ti.isTerminated();
679 for (ElementInfo e : this) {
681 e.cleanUp(this, isThreadTermination, tid);
687 * check if object is alive. This is here and not in ElementInfo
688 * because we might own the liveness bit. In fact, the generic
689 * implementation uses bit-toggle to avoid iteration over all live
690 * objects at the end of GC
693 public boolean isAlive (ElementInfo ei){
694 return (ei == null || ei.isMarkedOrAlive(liveBitValue));
697 //--- state management
699 // since we can't provide generic implementations, we force concrete subclasses to
700 // handle volatile information
703 public abstract void resetVolatiles();
706 public abstract void restoreVolatiles();
709 public boolean hasChanged() {
710 return (attributes & ATTR_ANY_CHANGED) != 0;
714 public void markChanged(int objref) {
715 attributes |= ATTR_ELEMENTS_CHANGED;
718 public void setStored() {
719 attributes &= ~ATTR_ANY_CHANGED;
723 public abstract Memento<Heap> getMemento(MementoFactory factory);
726 public abstract Memento<Heap> getMemento();
729 //--- out of memory simulation
732 public boolean isOutOfMemory() {
733 return (attributes & ATTR_OUT_OF_MEMORY) != 0;
737 public void setOutOfMemory(boolean isOutOfMemory) {
738 if (isOutOfMemory != isOutOfMemory()) {
740 attributes |= ATTR_OUT_OF_MEMORY;
742 attributes &= ~ATTR_OUT_OF_MEMORY;
744 attributes |= ATTR_ATTRIBUTE_CHANGED;
753 public void checkConsistency(boolean isStateStore) {
754 for (ElementInfo ei : this){
755 ei.checkConsistency();