src/main/gov/nasa/jpf/vm/PSIMHeap.java

   1 /*
   2  * Copyright (C) 2014, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   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
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  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.
  17  */
  18 package gov.nasa.jpf.vm;
  19
  20 import gov.nasa.jpf.Config;
  21 import gov.nasa.jpf.util.PSIntMap;
  22 import gov.nasa.jpf.util.Predicate;
  23
  24 import java.util.Iterator;
  25
  26 /**
  27  * heap implementation that uses a PersistentStagingMsbIntMap as the underlying container
  28  *
  29  * This is intended for large state spaces, to minimize store/restore costs. While those
  30  * are negligible for PersistentMaps, the per-change overhead is not since the container
  31  * has to duplicate the access path to the changed node on every modification. Efficiency
  32  * of PSIMHeap therefore relies on accessing objects in a consecutive pattern, i.e.
  33  * depends on clustered access.
  34  *
  35  * <2do> this should not be a GenericSGOIDHeap derived class since this includes
  36  * a number of non-persistent data structures (allocCounts, intern strings, pinDowns) that
  37  * are not persistent, i.e. still requires a memento that creates/restores snapshots of these
  38  * and hence looses a lot of the benefit we use a persistent map for
  39  *
  40  * NOTE - a reference value of 0 represents null and therefore is not a valid SGOID
  41  */
  42 public class PSIMHeap extends GenericSGOIDHeap {
  43
  44   /**
  45    * this sucks - we need a memento in order to store/restore allocCounts, internStrings and pinDownList
  46    */
  47   static class PSIMMemento extends GenericSGOIDHeapMemento {
  48     PSIntMap<ElementInfo> eiSnap;
  49
  50     PSIMMemento (PSIMHeap heap) {
  51       super(heap);
  52
  53       heap.elementInfos.process(ElementInfo.storer);
  54       eiSnap = heap.elementInfos; // no need to transform anything, it's persistent
  55     }
  56
  57     @Override
  58     public Heap restore(Heap inSitu) {
  59       super.restore( inSitu);
  60
  61       PSIMHeap heap = (PSIMHeap) inSitu;
  62       heap.elementInfos = eiSnap;
  63       heap.elementInfos.process(ElementInfo.restorer);
  64
  65       return heap;
  66     }
  67   }
  68
  69   class SweepPredicate implements Predicate<ElementInfo>{
  70     ThreadInfo ti;
  71     int tid;
  72     boolean isThreadTermination;
  73
  74     protected void setContext() {
  75       ti = vm.getCurrentThread();
  76       tid = ti.getId();
  77       isThreadTermination = ti.isTerminated();
  78     }
  79
  80     @Override
  81     public boolean isTrue (ElementInfo ei) {
  82
  83       if (ei.isMarked()){ // live object, prepare for next transition & gc cycle
  84         ei.setUnmarked();
  85         ei.setAlive( liveBitValue);
  86         ei.cleanUp( PSIMHeap.this, isThreadTermination, tid);
  87         return false;
  88
  89       } else { // object is no longer reachable
  90         // no finalizer support yet
  91         ei.processReleaseActions();
  92         // <2do> still have to process finalizers here, which might make the object live again
  93         vm.notifyObjectReleased( ti, ei);
  94         return true;
  95       }
  96     }
  97   }
  98
  99   SweepPredicate sweepPredicate;
 100   PSIntMap<ElementInfo> elementInfos;
 101
 102
 103   public PSIMHeap (Config config, KernelState ks) {
 104     super(config,ks);
 105
 106     elementInfos = new PSIntMap<ElementInfo>();
 107     sweepPredicate = new SweepPredicate();
 108   }
 109
 110   @Override
 111   public int size() {
 112     return elementInfos.size();
 113   }
 114
 115   @Override
 116   protected void set(int index, ElementInfo ei) {
 117     elementInfos = elementInfos.set(index, ei);
 118   }
 119
 120   @Override
 121   public ElementInfo get(int ref) {
 122     if (ref <= 0) {
 123       return null;
 124     } else {
 125       return elementInfos.get(ref);
 126     }
 127   }
 128
 129   @Override
 130   public ElementInfo getModifiable(int ref) {
 131     // <2do> this could probably use a specialized replaceValue() method
 132
 133     if (ref <= 0) {
 134       return null;
 135     } else {
 136       ElementInfo ei = elementInfos.get(ref);
 137
 138       if (ei != null && ei.isFrozen()) {
 139         ei = ei.deepClone();
 140         // freshly created ElementInfos are not frozen, so we don't have to defreeze
 141         elementInfos = elementInfos.set(ref, ei);
 142       }
 143
 144       return ei;
 145     }
 146   }
 147
 148   @Override
 149   protected void remove(int ref) {
 150     elementInfos = elementInfos.remove(ref);
 151   }
 152
 153   @Override
 154   protected void sweep () {
 155     sweepPredicate.setContext();
 156     elementInfos = elementInfos.removeAllSatisfying( sweepPredicate);
 157   }
 158
 159   @Override
 160   public Iterator<ElementInfo> iterator() {
 161     return elementInfos.iterator();
 162   }
 163
 164   @Override
 165   public Iterable<ElementInfo> liveObjects() {
 166     return elementInfos;
 167   }
 168
 169   @Override
 170   public void resetVolatiles() {
 171     // we don't have any
 172   }
 173
 174   @Override
 175   public void restoreVolatiles() {
 176     // we don't have any
 177   }
 178
 179   @Override
 180   public Memento<Heap> getMemento(MementoFactory factory) {
 181     return factory.getMemento(this);
 182   }
 183
 184   @Override
 185   public Memento<Heap> getMemento() {
 186     return new PSIMMemento(this);
 187   }
 188
 189 }