001: //
002: // Copyright (C) 2005 United States Government as represented by the
003: // Administrator of the National Aeronautics and Space Administration
004: // (NASA). All Rights Reserved.
005: //
006: // This software is distributed under the NASA Open Source Agreement
007: // (NOSA), version 1.3. The NOSA has been approved by the Open Source
008: // Initiative. See the file NOSA-1.3-JPF at the top of the distribution
009: // directory tree for the complete NOSA document.
010: //
011: // THE SUBJECT SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY OF ANY
012: // KIND, EITHER EXPRESSED, IMPLIED, OR STATUTORY, INCLUDING, BUT NOT
013: // LIMITED TO, ANY WARRANTY THAT THE SUBJECT SOFTWARE WILL CONFORM TO
014: // SPECIFICATIONS, ANY IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
015: // A PARTICULAR PURPOSE, OR FREEDOM FROM INFRINGEMENT, ANY WARRANTY THAT
016: // THE SUBJECT SOFTWARE WILL BE ERROR FREE, OR ANY WARRANTY THAT
017: // DOCUMENTATION, IF PROVIDED, WILL CONFORM TO THE SUBJECT SOFTWARE.
018: //
019: package gov.nasa.jpf.jvm;
020:
021: import gov.nasa.jpf.Config;
022: import gov.nasa.jpf.jvm.bytecode.Instruction;
023: import gov.nasa.jpf.util.Debug;
024:
025: import java.util.ArrayList;
026: import java.util.BitSet;
027: import java.util.Vector;
028:
029: // Mapping for constant strings
030: import java.util.HashMap;
031: import gov.nasa.jpf.util.DynamicIntArray;
032:
033: /**
034: * DynamicArea is the heap, i.e. the area were all objects created by NEW
035: * insn live. Hence the garbage collection mechanism resides here
036: */
037: public class DynamicArea extends Area {
038:
039: static DynamicArea heap;
040:
041: /**
042: * Used to store various mark phase infos
043: */
044: BitSet isUsed;
045: BitSet isRoot;
046: DynamicIntArray refThread;
047: DynamicIntArray lastAttrs;
048:
049: boolean runFinalizer;
050:
051: // just an internal helper
052: int markLevel;
053:
054: boolean outOfMemory; // can be used by listeners to simulate outOfMemory conditions
055:
056: /** Used for mapping constant strings to object references */
057: private HashMap String2Object = new HashMap();
058:
059: /** used to keep track of marked WeakRefs that might have to be updated */
060: private ArrayList weakRefs;
061:
062: public static void init(Config config) {
063: DynamicMap.init();
064: }
065:
066: /**
067: * Creates a new empty dynamic area.
068: */
069: public DynamicArea(Config config, KernelState ks) {
070: super (ks, DynamicElementInfo.storingDataLength);
071:
072: runFinalizer = config.getBoolean("vm.finalize", true);
073:
074: // beware - we store 'this' in a static field, which (a) makes it
075: // effectively a singleton, (b) means the assignment should be the very last
076: // insn to avoid handing out a ref to a partially initialized object (no
077: // subclassing!)
078: heap = this ;
079: }
080:
081: public boolean isStatic() {
082: return false;
083: }
084:
085: public static DynamicArea getHeap() {
086: return heap;
087: }
088:
089: public boolean getOutOfMemory() {
090: return outOfMemory;
091: }
092:
093: public void setOutOfMemory(boolean isOutOfMemory) {
094: outOfMemory = isOutOfMemory;
095: }
096:
097: public void gc() {
098: analyzeHeap(true);
099: }
100:
101: /**
102: * Our precise mark & sweep garbage collector. Be aware of two things
103: *
104: * (1) it's called every transition (forward) we detect has changed a reference,
105: * to ensure heap symmetry (save states), but at the cost of huge
106: * gc loads, where we cannot perform all the nasty performance tricks of
107: * 'normal' GCs
108: * (2) we do even more - we keep track of reachability, i.e. if an object is
109: * reachable from a thread root object, to check if it is thread local
110: * (in which case we can ignore corresponding field accesses as potential
111: * scheduling relevant insns in our on-the-fly partial order reduction).
112: * Note that reachability does not mean accessibility, which is much harder
113: *
114: * @aspects: gc
115: */
116:
117: public void analyzeHeap(boolean sweep) {
118: // <2do> pcm - we should refactor so that POR reachability (which is checked
119: // on each ref PUTFIELD, PUTSTATIC) is more effective !!
120:
121: int i;
122: int length = elements.length;
123: ElementInfo ei;
124: weakRefs = null;
125:
126: JVM.getVM().notifyGCBegin();
127:
128: initGc();
129:
130: // phase 0 - not awefully nice - we have to chache the attribute values
131: // so that we can determine at the end of the gc if any life object has
132: // changed only in its attributes. 'lastAttrs' could be a local.
133: // Since we have this loop, we also use it to reset all the propagated
134: // (i.e. re-computed) object attributes of live objects
135: for (i = 0; i < length; i++) {
136: ei = elements[i];
137: if (ei != null) {
138: lastAttrs.set(i, ei.attributes);
139: ei.attributes &= ~ElementInfo.ATTR_PROP_MASK;
140:
141: if ((ei.attributes & ElementInfo.ATTR_PINDOWN) != 0) {
142: markPinnedDown(i);
143: }
144: }
145: }
146:
147: // phase 1 - mark our root sets.
148: // After this phase, all directly root reachable objects have a 'lastGC'
149: // value of '-1', but are NOT recursively processed yet (i.e. all other
150: // ElementInfos still have the old 'lastGc'). However, all root marked objects
151: // do have their proper reachability attribute set
152: ks.tl.markRoots(); // mark thread stacks
153: ks.sa.markRoots(); // mark objects referenced from StaticArea ElementInfos
154:
155: // phase 2 - walk through all the marked ones recursively
156: // Now we traverse, and propagate the reachability attribute. After this
157: // phase, all live objects should be marked with the 'curGc' value
158: for (i = 0; i < length; i++) {
159: if (isRoot.get(i)) {
160: markRecursive(i);
161: }
162: }
163:
164: // phase 3 - run finalization (slightly approximated, since it should be
165: // done in a dedicated thread)
166: // we need to do this in two passes, or otherwise we might end up
167: // removing objects that are still referenced from within finalizers
168: if (sweep && runFinalizer) {
169: for (i = 0; i < length; i++) {
170: ei = elements[i];
171: if ((ei != null) && !isUsed.get(i)) {
172: // if finalization for some reason fails, re-mark the object
173: // For now, this is only mis-used for objects to finalize after a
174: // thread dies. Ultimately, this will be required since finalization
175: // can turn objects live again
176: if (!JVM.getVM().finalizeObject(ei)) {
177: markRecursive(i);
178: }
179: }
180: }
181: }
182:
183: // phase 4 - all finalizations are done, reclaim all unmarked objects, i.e.
184: // all objects with 'lastGc' != 'curGc', and check for attribute-only changes
185: int count = 0;
186: boolean heapModified = anyChanged;
187:
188: for (i = 0; i < length; i++) {
189: ei = elements[i];
190: if (ei != null) {
191: if (isUsed.get(i)) {
192: // Ok, it's live, BUT..
193: // beware of the case where the only change we had was a attribute
194: // change - the downside of our marvelous object attribute system is
195: // that we have to store the attributes so that we can later-on backtrack
196:
197: // NOTE: even if the critical case is only the one where 'anyChanged'
198: // is false (i.e. there was no other heap change), a high number of
199: // attribute-only object changes (reachability) is bad because it means
200: // the whole object has to be stored (we don't keep the attrs separate
201: // from the other ElementInfo storage). On the other hand, we use
202: // state collapsing, and hence the overhead should be bounded (<= 2x)
203: if (lastAttrs.get(i) != ei.attributes) {
204: /*
205: if (!heapModified) {
206: // that's BAD - an attribute-only change
207: System.out.println("attr-only change of " + ei + " "
208: + Integer.toHexString(lastAttrs.get(i)) + " -> "
209: + Integer.toHexString(ei.attributes));
210: }
211: */
212:
213: anyChanged = true;
214: hasChanged.set(i);
215: }
216: } else if (sweep) {
217: // this object is garbage, toast it
218: count++;
219: JVM.getVM().notifyObjectReleased(ei);
220: remove(i);
221: }
222: }
223: }
224:
225: if (sweep) {
226: checkWeakRefs(); // for potential nullification
227: }
228:
229: JVM.getVM().notifyGCEnd();
230: }
231:
232: void initGc() {
233: int len = elements.length;
234:
235: if ((isRoot == null) || (isRoot.size() < len)) {
236: isRoot = new BitSet(len);
237: } else {
238: isRoot.clear();
239: }
240:
241: if ((isUsed == null) || (isUsed.size() < len)) {
242: isUsed = new BitSet(len);
243: } else {
244: isUsed.clear();
245: }
246:
247: // those don't need to be reset, we only need them to temporarily
248: // store data on live objects
249: if (refThread == null) {
250: refThread = new DynamicIntArray();
251: }
252:
253: if (lastAttrs == null) {
254: lastAttrs = new DynamicIntArray();
255: }
256: }
257:
258: void logMark(FieldInfo fi, ElementInfo ei, int tid, int attrMask) {
259: /**/
260: for (int i = 0; i <= markLevel; i++)
261: System.out.print(" ");
262:
263: if (fi != null) {
264: System.out.print('\'');
265: System.out.print(fi.getName());
266: System.out.print("': ");
267: }
268:
269: System.out.print(ei);
270:
271: System.out.print(" ,attr:");
272: System.out.print(Integer.toHexString(ei.attributes));
273:
274: System.out.print(" ,mask:");
275: System.out.print(Integer.toHexString(attrMask));
276:
277: System.out.print(" ,thread:");
278: System.out.print(tid);
279: System.out.print("/");
280: System.out.print(refThread.get(ei.index));
281: System.out.print(" ");
282:
283: if (isRoot.get(ei.index))
284: System.out.print("R");
285: if (isUsed.get(ei.index))
286: System.out.print("V");
287:
288: System.out.println();
289: /**/
290: }
291:
292: /**
293: * recursive attribute propagating marker, used to traverse the object graph
294: * (it's here so that we can pass in gc-local data into the ElementInfo
295: * methods). This method is called on all root objects, and starts the
296: * traversal:
297: * DynamicArea.markRecursive(objref) <-- tid, default attrMask
298: * ElementInfo.markRecursive(tid,attrMask) <-- object attributes
299: * Fields.markRecursive(tid,attributes,attrMask) <-- field info
300: * DynamicArea.markRecursive(objref,tid,refAttrs, attrMask, fieldInfo)
301: * @aspects: gc
302: */
303: void markRecursive(int objref) {
304: int tid = refThread.get(objref);
305: ElementInfo ei = elements[objref];
306: int attrMask = ElementInfo.ATTR_PROP_MASK;
307:
308: markLevel = 0;
309:
310: isUsed.set(objref);
311: //logMark( null, ei, tid, attrMask);
312: ei.markRecursive(tid, attrMask);
313: }
314:
315: void markRecursive(int objref, int refTid, int refAttr,
316: int attrMask, FieldInfo fi) {
317: if (objref == -1) {
318: return;
319: }
320: ElementInfo ei = elements[objref];
321:
322: if (fi != null) {
323: attrMask &= fi.getAttributes();
324: }
325:
326: markLevel++;
327:
328: if (isRoot.get(objref)) {
329: if (!ei.isShared() && (refThread.get(objref) != refTid)) {
330: ei.setShared(attrMask);
331: //logMark( fi, ei, refTid, attrMask);
332: }
333: } else {
334: if (!isUsed.get(objref)
335: || !ei.hasEqualPropagatedAttributes(refAttr,
336: attrMask)) {
337: isUsed.set(objref);
338: refThread.set(objref, refTid);
339: ei.propagateAttributes(refAttr, attrMask);
340:
341: //logMark( fi, ei, refTid, attrMask);
342: ei.markRecursive(refTid, attrMask);
343: }
344: }
345:
346: markLevel--;
347: }
348:
349: /**
350: * called during non-recursive phase1 marking of all objects reachable
351: * from Thread roots
352: * @aspects: gc
353: */
354: void markThreadRoot(int objref, int tid) {
355: if (objref == -1) {
356: return;
357: }
358:
359: if (isRoot.get(objref)) {
360: int rt = refThread.get(objref);
361: if ((rt != tid) && (rt != -1)) {
362: elements[objref].setShared();
363: }
364: } else {
365: isRoot.set(objref);
366: refThread.set(objref, tid);
367: }
368: }
369:
370: /**
371: * called during non-recursive phase1 marking of all objects reachable
372: * from static fields
373: * @aspects: gc
374: */
375: void markStaticRoot(int objref) {
376: if (objref == -1) {
377: return;
378: }
379:
380: isRoot.set(objref);
381: refThread.set(objref, -1);
382: elements[objref].setShared();
383: }
384:
385: void markPinnedDown(int objref) {
386: isRoot.set(objref);
387: refThread.set(objref, -1);
388: // don't set shared yet
389: }
390:
391: public boolean isSchedulingRelevantObject(int objRef) {
392: if (objRef == -1)
393: return false;
394:
395: return elements[objRef].isSchedulingRelevant();
396: }
397:
398: public ElementInfo get(int index) {
399: if ((index < 0) || (index >= elements.length)) {
400: return null;
401: }
402:
403: return super .get(index);
404: }
405:
406: public void log() {
407: Debug.println(Debug.MESSAGE, "DA");
408:
409: for (int i = 0; i < elements.length; i++) {
410: if (elements[i] != null) {
411: elements[i].log();
412: }
413: }
414: }
415:
416: /**
417: * Creates a new array of the given type.
418: */
419: public int newArray(String type, int size, ThreadInfo th) {
420: // normalize dot notation into 'L..;'
421: if (!Types.isTypeCode(type)) {
422: type = Types.getTypeCode(type);
423: }
424:
425: int idx = newArray(indexFor(th), type, size);
426:
427: if (th != null) { // maybe we should report them all, and put the burden on the listener
428: JVM.getVM().notifyObjectCreated(th, elements[idx]);
429: }
430:
431: // see newObject for 'outOfMemory' handling
432:
433: return idx;
434: }
435:
436: /**
437: * Creates a new constant string.
438: * only called from LDC and LDC_W
439: */
440: public int newConstantString(String str) {
441: Integer objValue = (Integer) String2Object.get(str);
442:
443: if (objValue == null) {
444: // the mapping is empty
445: int newObjRef = newString(str, null);
446: String2Object.put(str, new Integer(newObjRef));
447:
448: return newObjRef;
449: } else {
450: int objRef = objValue.intValue();
451:
452: // check to see if object is really there - could have been GC-ed
453: ElementInfo ei = get(objRef);
454:
455: if (ei == null) {
456: // object is no longer available
457: int newObjRef = newString(str, null);
458: String2Object.remove(str);
459: String2Object.put(str, new Integer(newObjRef));
460:
461: return newObjRef;
462: } else {
463: if (!(ei.getClassInfo().getName().equals(
464: "java.lang.String") && ei.asString()
465: .equals(str))) {
466: // either it is no longer a string or the contents is different
467: int newObjRef = newString(str, null);
468: String2Object.remove(str);
469: String2Object.put(str, new Integer(newObjRef));
470:
471: return newObjRef;
472: }
473: }
474:
475: return objRef;
476: }
477: }
478:
479: /**
480: * Creates a new object of the given class.
481: */
482: public int newObject(ClassInfo ci, ThreadInfo th) {
483: int index;
484:
485: // first, we make sure the class and all its supers are initialized
486: // <?> this isn't done in the context of NEW? The ks.sa ref is BAD
487: // It's important we do this *before* we call indexFor, since it might get
488: // recursive here
489: if (!ks.sa.containsClass(ci.getName())) {
490: ks.sa.newClass(ci);
491: }
492:
493: // create the thing itself
494: Fields f = ci.createInstanceFields();
495: Monitor m = new Monitor();
496:
497: DynamicElementInfo dei = new DynamicElementInfo(f, m);
498:
499: // now get the index where to store this sucker, but be aware of that the
500: // returned index might be outside the current elements array (super.add
501: // takes care of this <Hrmm>)
502: index = indexFor(th);
503:
504: // and finally store it
505: add(index, dei);
506:
507: if (th != null) { // maybe we should report them all, and put the burden on the listener
508: JVM.getVM().notifyObjectCreated(th, dei);
509: }
510:
511: // note that we don't return -1 if 'outOfMemory' (which is handled in
512: // the NEWxx bytecode) because our allocs are used from within the
513: // exception handling of the resulting OutOfMemoryError (and we would
514: // have to override it, since the VM should guarantee proper exceptions)
515:
516: return index;
517: }
518:
519: /**
520: * Creates a new string.
521: */
522: public int newString(String str, ThreadInfo th) {
523: int length = str.length();
524: int index = newObject(ClassInfo
525: .getClassInfo("java.lang.String"), th);
526: int value = newArray("C", length, th);
527:
528: ElementInfo e = get(index);
529: // <2do> pcm - this is BAD, we shouldn't depend on private impl of
530: // external classes - replace with our own java.lang.String !
531: e.setReferenceField("value", value);
532: e.setIntField("offset", 0);
533: e.setIntField("count", length);
534:
535: e = get(value);
536: for (int i = 0; i < length; i++) {
537: e.setElement(i, str.charAt(i));
538: }
539:
540: return index;
541: }
542:
543: /**
544: * reset all weak references that now point to collected objects to 'null'
545: * NOTE: this implementation requires our own Reference/WeakReference implementation, to
546: * make sure the 'ref' field is the first one
547: */
548: void checkWeakRefs() {
549: if (weakRefs != null) {
550: int len = weakRefs.size();
551:
552: for (int i = 0; i < len; i++) {
553: Fields f = (Fields) weakRefs.get(i);
554: int ref = f.getIntValue(0); // watch out, the 0 only works with our own WeakReference impl
555: if (ref != -1) {
556: if ((elements[ref] == null)
557: || (elements[ref].isNull())) {
558: f.setReferenceValue(0, -1);
559: }
560: }
561: }
562:
563: weakRefs = null;
564: }
565: }
566:
567: ElementInfo createElementInfo() {
568: return new DynamicElementInfo();
569: }
570:
571: void registerWeakReference(Fields f) {
572: if (weakRefs == null) {
573: weakRefs = new ArrayList();
574: }
575:
576: weakRefs.add(f);
577: }
578:
579: private int indexFor(ThreadInfo th) {
580: Instruction pc = (th != null) ? th.getPC() : null;
581: synchronized (DynamicMap.class) {
582: int index;
583: int length;
584:
585: DynamicMapIndex i = new DynamicMapIndex(pc,
586: (th == null) ? 0 : th.index, 0);
587:
588: if (!DynamicMap.hasEntry(i)) {
589: index = DynamicMap.addEntry(i);
590: } else {
591: index = DynamicMap.getEntry(i);
592: length = elements.length;
593:
594: while ((index < length) && (elements[index] != null)) {
595: i.next();
596:
597: if (!DynamicMap.hasEntry(i)) {
598: index = DynamicMap.addEntry(i);
599:
600: break;
601: }
602:
603: index = DynamicMap.getEntry(i);
604: }
605: }
606:
607: return index;
608: }
609: }
610:
611: /**
612: * Creates a new array object at a given address.
613: */
614: private int newArray(int index, String type, int size) {
615: int ts = Types.getTypeSize(type);
616: boolean ir = Types.isReference(type);
617: String clsName = "[" + type;
618:
619: Fields f = new ArrayFields(clsName, ClassInfo
620: .getClassInfo(clsName), size * ts, size, ir);
621: Monitor m = new Monitor();
622:
623: ElementInfo e = new DynamicElementInfo(f, m);
624: add(index, e);
625:
626: return index;
627: }
628:
629: /**
630: * Creates a new object at the given address.
631: */
632: private int newObject(int index, ClassInfo ci) {
633: // this is just here to initialize the corresponding class
634: // (pcm - nicely hidden side effect)
635: ks.sa.get(ci.getName());
636:
637: Fields f = ci.createInstanceFields();
638: Monitor m = new Monitor();
639:
640: add(index, new DynamicElementInfo(f, m));
641:
642: return index;
643: }
644:
645: /*
646: * The following code is used to linearize a rooted structure in the heap
647: * A PredicateMap is used to map states onto predicates as an additional key
648: * used during the linearization
649: */
650:
651: private HashMap Object2Value;
652:
653: private int lincount;
654:
655: private PredicateMap pMap = null;
656:
657: public Vector linearizeRoot(int objref) {
658: Object2Value = new HashMap();
659: lincount = 0;
660: Vector result = new Vector();
661: return linearize(objref, result);
662: }
663:
664: public Vector linearizeRoot(int objref, PredicateMap obj) {
665: Object2Value = new HashMap();
666: lincount = 0;
667: Vector result = new Vector();
668: pMap = obj;
669: return linearize(objref, result);
670: }
671:
672: /*
673: * A structureMap is a special PredicateMap that is just an identity
674: * function, i.e. only the structure is important no additional predicaes
675: * are used
676: */
677: class structureMap extends PredicateMap {
678: public void evaluate() {
679: }
680:
681: public String getRep() {
682: return "";
683: }
684: }
685:
686: public Vector linearize(int objref, Vector result) {
687:
688: PredicateMap mapObj = pMap;
689:
690: if (objref == -1) {
691: result.addElement("-1");
692: return result;
693: }
694:
695: if (mapObj == null)
696: mapObj = new structureMap();
697:
698: mapObj.setRef(objref);
699: String refRep = "" + mapObj.getRef();
700:
701: String objRep;
702:
703: if (Object2Value.containsKey(refRep)) {
704: objRep = Object2Value.get(refRep).toString();
705: result.addElement(objRep);
706: return result;
707: } else {
708: Object2Value.put(refRep, new Integer(lincount));
709: mapObj.evaluate();
710: objRep = "" + lincount + mapObj.getRep();
711: lincount++;
712: }
713:
714: result.addElement(objRep);
715:
716: ElementInfo ei = elements[objref];
717: return ei.linearize(result);
718: }
719: }
|