DynamicArea


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