src/main/gov/nasa/jpf/vm/serialize/FilteringSerializer.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.serialize;
  19
  20
  21 import gov.nasa.jpf.util.ArrayObjectQueue;
  22 import gov.nasa.jpf.util.BitArray;
  23 import gov.nasa.jpf.util.FinalBitSet;
  24 import gov.nasa.jpf.util.IntVector;
  25 import gov.nasa.jpf.util.ObjVector;
  26 import gov.nasa.jpf.util.ObjectQueue;
  27 import gov.nasa.jpf.util.Processor;
  28 import gov.nasa.jpf.vm.AbstractSerializer;
  29 import gov.nasa.jpf.vm.ArrayFields;
  30 import gov.nasa.jpf.vm.ClassInfo;
  31 import gov.nasa.jpf.vm.ClassLoaderInfo;
  32 import gov.nasa.jpf.vm.ElementInfo;
  33 import gov.nasa.jpf.vm.FieldInfo;
  34 import gov.nasa.jpf.vm.Fields;
  35 import gov.nasa.jpf.vm.Heap;
  36 import gov.nasa.jpf.vm.Instruction;
  37 import gov.nasa.jpf.vm.MJIEnv;
  38 import gov.nasa.jpf.vm.VM;
  39 import gov.nasa.jpf.vm.MethodInfo;
  40 import gov.nasa.jpf.vm.NativeStateHolder;
  41 import gov.nasa.jpf.vm.ReferenceProcessor;
  42 import gov.nasa.jpf.vm.StackFrame;
  43 import gov.nasa.jpf.vm.StaticElementInfo;
  44 import gov.nasa.jpf.vm.Statics;
  45 import gov.nasa.jpf.vm.ThreadInfo;
  46 import gov.nasa.jpf.vm.ThreadList;
  47
  48 import java.util.HashMap;
  49 import java.util.List;
  50
  51
  52 /**
  53  * serializer that can ignore marked fields and stackframes for state matching
  54  *
  55  * <2do> rework filter policies
  56  */
  57 public class FilteringSerializer extends AbstractSerializer implements ReferenceProcessor, Processor<ElementInfo> {
  58
  59   // indexed by method globalId
  60   final ObjVector<FramePolicy> methodCache = new ObjVector<FramePolicy>();
  61
  62   //--- search global bitmask caches
  63   final HashMap<ClassInfo,FinalBitSet> instanceRefMasks = new HashMap<ClassInfo,FinalBitSet>();
  64   final HashMap<ClassInfo,FinalBitSet> staticRefMasks   = new HashMap<ClassInfo,FinalBitSet>();
  65
  66   final HashMap<ClassInfo,FinalBitSet> instanceFilterMasks = new HashMap<ClassInfo,FinalBitSet>();
  67   final HashMap<ClassInfo,FinalBitSet> staticFilterMasks   = new HashMap<ClassInfo,FinalBitSet>();
  68
  69   protected FilterConfiguration filter;
  70
  71   protected transient IntVector buf = new IntVector(4096);
  72
  73   // the reference queue for heap traversal
  74   protected ObjectQueue<ElementInfo> refQueue;
  75
  76   Heap heap;
  77
  78
  79   @Override
  80   public void attach(VM vm) {
  81     super.attach(vm);
  82
  83     filter = vm.getConfig().getInstance("filter.class", FilterConfiguration.class);
  84     if (filter == null) {
  85       filter = new DefaultFilterConfiguration();
  86     }
  87     filter.init(vm.getConfig());
  88   }
  89
  90   protected FramePolicy getFramePolicy(MethodInfo mi) {
  91     FramePolicy p = null;
  92
  93     int mid = mi.getGlobalId();
  94     if (mid >= 0){
  95       p = methodCache.get(mid);
  96     if (p == null) {
  97       p = filter.getFramePolicy(mi);
  98       methodCache.set(mid, p);
  99     }
 100     } else {
 101       p = filter.getFramePolicy(mi);
 102     }
 103
 104     return p;
 105   }
 106
 107   protected FinalBitSet getInstanceRefMask(ClassInfo ci) {
 108     FinalBitSet v = instanceRefMasks.get(ci);
 109     if (v == null) {
 110       BitArray b = new BitArray(ci.getInstanceDataSize());
 111       for (FieldInfo fi : filter.getMatchedInstanceFields(ci)) {
 112         if (fi.isReference()) {
 113           b.set(fi.getStorageOffset());
 114         }
 115       }
 116       v = FinalBitSet.create(b);
 117       if (v == null) throw new IllegalStateException("Null BitArray returned.");
 118       instanceRefMasks.put(ci, v);
 119     }
 120     return v;
 121   }
 122
 123   protected FinalBitSet getStaticRefMask(ClassInfo ci) {
 124     FinalBitSet v = staticRefMasks.get(ci);
 125     if (v == null) {
 126       BitArray b = new BitArray(ci.getStaticDataSize());
 127       for (FieldInfo fi : filter.getMatchedStaticFields(ci)) {
 128         if (fi.isReference()) {
 129           b.set(fi.getStorageOffset());
 130         }
 131       }
 132       v = FinalBitSet.create(b);
 133       if (v == null) throw new IllegalStateException("Null BitArray returned.");
 134       staticRefMasks.put(ci, v);
 135     }
 136     return v;
 137   }
 138
 139   protected FinalBitSet getInstanceFilterMask(ClassInfo ci) {
 140     FinalBitSet v = instanceFilterMasks.get(ci);
 141     if (v == null) {
 142       BitArray b = new BitArray(ci.getInstanceDataSize());
 143       b.setAll();
 144       for (FieldInfo fi : filter.getMatchedInstanceFields(ci)) {
 145         int start = fi.getStorageOffset();
 146         int end = start + fi.getStorageSize();
 147         for (int i = start; i < end; i++) {
 148           b.clear(i);
 149         }
 150       }
 151       v = FinalBitSet.create(b);
 152       if (v == null) throw new IllegalStateException("Null BitArray returned.");
 153       instanceFilterMasks.put(ci, v);
 154     }
 155     return v;
 156   }
 157
 158   protected FinalBitSet getStaticFilterMask(ClassInfo ci) {
 159     FinalBitSet v = staticFilterMasks.get(ci);
 160     if (v == null) {
 161       BitArray b = new BitArray(ci.getStaticDataSize());
 162       b.setAll();
 163       for (FieldInfo fi : filter.getMatchedStaticFields(ci)) {
 164         int start = fi.getStorageOffset();
 165         int end = start + fi.getStorageSize();
 166         for (int i = start; i < end; i++) {
 167           b.clear(i);
 168         }
 169       }
 170       v = FinalBitSet.create(b);
 171       if (v == null) throw new IllegalStateException("Null BitArray returned.");
 172       staticFilterMasks.put(ci, v);
 173     }
 174     return v;
 175   }
 176
 177   protected void initReferenceQueue() {
 178     // note - this assumes all heap objects are in an unmarked state, but this
 179     // is true if we enter outside the gc
 180
 181     if (refQueue == null){
 182       refQueue = new ArrayObjectQueue<ElementInfo>();
 183     } else {
 184       refQueue.clear();
 185     }
 186   }
 187
 188
 189   //--- those are the methods that can be overridden by subclasses to implement abstractions
 190
 191   // needs to be public because of ReferenceProcessor interface
 192   @Override
 193   public void processReference(int objref) {
 194     if (objref != MJIEnv.NULL) {
 195       ElementInfo ei = heap.get(objref);
 196       if (!ei.isMarked()) { // only add objects once
 197         ei.setMarked();
 198         refQueue.add(ei);
 199       }
 200     }
 201
 202     buf.add(objref);
 203   }
 204
 205
 206   protected void processArrayFields (ArrayFields afields){
 207     buf.add(afields.arrayLength());
 208
 209     if (afields.isReferenceArray()) {
 210       int[] values = afields.asReferenceArray();
 211       for (int i = 0; i < values.length; i++) {
 212         processReference(values[i]);
 213       }
 214     } else {
 215       afields.appendTo(buf);
 216     }
 217   }
 218
 219   protected void processNamedFields (ClassInfo ci, Fields fields){
 220     FinalBitSet filtered = getInstanceFilterMask(ci);
 221     FinalBitSet refs = getInstanceRefMask(ci);
 222
 223     // using a block operation probably doesn't buy us much here since
 224     // we would have to blank the filtered slots and then visit the
 225     // non-filtered reference slots, i.e. do two iterations over
 226     // the mask bit sets
 227     int[] values = fields.asFieldSlots();
 228     for (int i = 0; i < values.length; i++) {
 229       if (!filtered.get(i)) {
 230         int v = values[i];
 231         if (refs.get(i)) {
 232           processReference(v);
 233         } else {
 234           buf.add(v);
 235         }
 236       }
 237     }
 238   }
 239
 240   // needs to be public because of ElementInfoProcessor interface
 241   // NOTE: we don't serialize the monitor state here since this is
 242   // redundant to the thread locking state (which we will do after the heap).
 243   // <2do> we don't strictly need the lockCount since this has to show in the
 244   // stack frames. However, we should probably add monitor serialization to
 245   // better support specialized subclasses
 246   @Override
 247   public void process (ElementInfo ei) {
 248     Fields fields = ei.getFields();
 249     ClassInfo ci = ei.getClassInfo();
 250     buf.add(ci.getUniqueId());
 251
 252     if (fields instanceof ArrayFields) { // not filtered
 253       processArrayFields((ArrayFields)fields);
 254
 255     } else { // named fields, filtered
 256       processNamedFields(ci, fields);
 257     }
 258   }
 259
 260   protected void processReferenceQueue () {
 261     refQueue.process(this);
 262
 263     // this sucks, but we can't do the 'isMarkedOrLive' trick used in gc here
 264     // because gc depends on live bit integrity, and we only mark non-filtered live
 265     // objects here, i.e. we can't just set the Heap liveBitValue subsequently.
 266     heap.unmarkAll();
 267   }
 268
 269   protected void serializeStackFrames() {
 270     ThreadList tl = ks.getThreadList();
 271
 272     for (ThreadInfo ti : tl) {
 273       if (ti.isAlive()) {
 274         serializeStackFrames(ti);
 275       }
 276     }
 277   }
 278
 279   protected void serializeStackFrames(ThreadInfo ti){
 280     // we need to add the thread object itself as a root
 281     processReference( ti.getThreadObjectRef());
 282
 283     for (StackFrame frame = ti.getTopFrame(); frame != null; frame = frame.getPrevious()){
 284       serializeFrame(frame);
 285     }
 286   }
 287
 288   /** more generic, but less efficient because it can't use block operations
 289   protected void _serializeFrame(StackFrame frame){
 290     buf.add(frame.getMethodInfo().getGlobalId());
 291     buf.add(frame.getPC().getInstructionIndex());
 292
 293     int len = frame.getTopPos()+1;
 294     buf.add(len);
 295
 296     // this looks like something we can push into the frame
 297     int[] slots = frame.getSlots();
 298     for (int i = 0; i < len; i++) {
 299       if (frame.isReferenceSlot(i)) {
 300         processReference(slots[i]);
 301       } else {
 302         buf.add(slots[i]);
 303       }
 304     }
 305   }
 306   **/
 307
 308   protected void serializeFrame(StackFrame frame){
 309     buf.add(frame.getMethodInfo().getGlobalId());
 310
 311     // there can be (rare) cases where a listener sets a null nextPc in
 312     // a frame that is still on the stack
 313     Instruction pc = frame.getPC();
 314     if (pc != null){
 315       buf.add(pc.getInstructionIndex());
 316     } else {
 317       buf.add(-1);
 318     }
 319
 320     int len = frame.getTopPos()+1;
 321     buf.add(len);
 322
 323     int[] slots = frame.getSlots();
 324     buf.append(slots,0,len);
 325
 326     frame.visitReferenceSlots(this);
 327   }
 328
 329   // this is called after the heap got serialized, i.e. we should not use
 330   // processReference() anymore.
 331   protected void serializeThreadState (ThreadInfo ti){
 332
 333     buf.add( ti.getId());
 334     buf.add( ti.getState().ordinal());
 335     // SmartThings...ignore this
 336     //    buf.add( ti.getStackDepth());
 337
 338     //--- the lock state
 339     // NOTE: both lockRef and lockedObjects can only refer to live objects
 340     // which are already heap-processed at this point (i.e. have a valid 'sid'
 341     // in case we don't want to directly serialize the reference values)
 342
 343     // the object we are waiting for
 344     ElementInfo eiLock = ti.getLockObject();
 345     if (eiLock != null){
 346       buf.add(getSerializedReferenceValue( eiLock));
 347     }
 348
 349     // the objects we hold locks for
 350     // NOTE: this should be independent of lockedObjects order, hence we
 351     // have to factor this out
 352     serializeLockedObjects( ti.getLockedObjects());
 353   }
 354
 355   // NOTE: this should not be called before all live references have been processed
 356   protected int getSerializedReferenceValue (ElementInfo ei){
 357     return ei.getObjectRef();
 358   }
 359
 360   protected void serializeLockedObjects(List<ElementInfo> lockedObjects){
 361     // lockedObjects are already a set since we don't have multiple entries
 362     // (that would just increase the lock count), but our serialization should
 363     // NOT produce different values depending on order of entry. We could achieve this by using
 364     // a canonical order (based on reference or sid values), but this would require
 365     // System.arraycopys and object allocation, which is too much overhead
 366     // given that the number of lockedObjects is small for all but the most
 367     // pathological systems under test.
 368     // We could spend all day to compute the perfect order-independent hash function,
 369     // but since our StateSet isn't guaranteed to be collision free anyway, we
 370     // rather shoot for something that can be nicely JITed
 371     int n = lockedObjects.size();
 372     buf.add(n);
 373
 374     if (n > 0){
 375       if (n == 1){ // no order involved
 376         buf.add( getSerializedReferenceValue( lockedObjects.get(0)));
 377
 378       } else {
 379         // don't burn an iterator on this, 'n' is supposed to be small
 380         int h = (n << 16) + (n % 3);
 381         for (int i=0; i<n; i++){
 382           int rot = (getSerializedReferenceValue( lockedObjects.get(i))) % 31;
 383           h ^= (h << rot) | (h >>> (32 - rot)); // rotate left
 384         }
 385         buf.add( h);
 386       }
 387     }
 388   }
 389
 390   protected void serializeThreadStates (){
 391     ThreadList tl = ks.getThreadList();
 392
 393     for (ThreadInfo ti : tl) {
 394       if (ti.isAlive()) {
 395         serializeThreadState(ti);
 396       }
 397     }
 398   }
 399
 400   protected void serializeClassLoaders(){
 401     buf.add(ks.classLoaders.size());
 402
 403     for (ClassLoaderInfo cl : ks.classLoaders) {
 404       if(cl.isAlive()) {
 405         serializeStatics(cl.getStatics());
 406       }
 407     }
 408   }
 409
 410   protected void serializeStatics(Statics statics){
 411     buf.add(statics.size());
 412
 413     for (StaticElementInfo sei : statics.liveStatics()) {
 414       serializeClass(sei);
 415     }
 416   }
 417
 418   protected void serializeClass (StaticElementInfo sei){
 419     buf.add(sei.getStatus());
 420
 421     Fields fields = sei.getFields();
 422     ClassInfo ci = sei.getClassInfo();
 423     FinalBitSet filtered = getStaticFilterMask(ci);
 424     FinalBitSet refs = getStaticRefMask(ci);
 425     int max = ci.getStaticDataSize();
 426     for (int i = 0; i < max; i++) {
 427       if (!filtered.get(i)) {
 428         int v = fields.getIntValue(i);
 429         if (refs.get(i)) {
 430           processReference(v);
 431         } else {
 432           buf.add(v);
 433         }
 434       }
 435     }
 436   }
 437
 438   protected void serializeNativeStateHolders(){
 439     for (NativeStateHolder nsh : nativeStateHolders){
 440       serializeNativeStateHolder(nsh);
 441     }
 442   }
 443
 444   protected void serializeNativeStateHolder (NativeStateHolder nsh){
 445     buf.add(nsh.getHash());
 446   }
 447
 448   //--- our main purpose in life
 449
 450   @Override
 451   protected int[] computeStoringData() {
 452
 453     buf.clear();
 454     heap = ks.getHeap();
 455     initReferenceQueue();
 456
 457     //--- serialize all live objects and loaded classes
 458     serializeStackFrames();
 459     serializeClassLoaders();
 460     processReferenceQueue();
 461
 462     //--- now serialize the thread states (which might refer to live objects)
 463     // we do this last because threads contain some internal references
 464     // (locked objects etc) that should NOT set the canonical reference serialization
 465     // values (if they are encountered before their first explicit heap reference)
 466     serializeThreadStates();
 467
 468     //--- last is serialization of native state holders
 469     serializeNativeStateHolders();
 470
 471     return buf.toArray();
 472   }
 473
 474   protected void dumpData() {
 475     int n = buf.size();
 476     System.out.print("serialized data: [");
 477     for (int i=0; i<n; i++) {
 478       if (i>0) {
 479         System.out.print(',');
 480       }
 481       System.out.print(buf.get(i));
 482     }
 483     System.out.println(']');
 484   }
 485 }