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.
18 package gov.nasa.jpf.vm.serialize;
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;
48 import java.util.HashMap;
49 import java.util.List;
53 * serializer that can ignore marked fields and stackframes for state matching
55 * <2do> rework filter policies
57 public class FilteringSerializer extends AbstractSerializer implements ReferenceProcessor, Processor<ElementInfo> {
59 // indexed by method globalId
60 final ObjVector<FramePolicy> methodCache = new ObjVector<FramePolicy>();
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>();
66 final HashMap<ClassInfo,FinalBitSet> instanceFilterMasks = new HashMap<ClassInfo,FinalBitSet>();
67 final HashMap<ClassInfo,FinalBitSet> staticFilterMasks = new HashMap<ClassInfo,FinalBitSet>();
69 protected FilterConfiguration filter;
71 protected transient IntVector buf = new IntVector(4096);
73 // the reference queue for heap traversal
74 protected ObjectQueue<ElementInfo> refQueue;
80 public void attach(VM vm) {
83 filter = vm.getConfig().getInstance("filter.class", FilterConfiguration.class);
85 filter = new DefaultFilterConfiguration();
87 filter.init(vm.getConfig());
90 protected FramePolicy getFramePolicy(MethodInfo mi) {
93 int mid = mi.getGlobalId();
95 p = methodCache.get(mid);
97 p = filter.getFramePolicy(mi);
98 methodCache.set(mid, p);
101 p = filter.getFramePolicy(mi);
107 protected FinalBitSet getInstanceRefMask(ClassInfo ci) {
108 FinalBitSet v = instanceRefMasks.get(ci);
110 BitArray b = new BitArray(ci.getInstanceDataSize());
111 for (FieldInfo fi : filter.getMatchedInstanceFields(ci)) {
112 if (fi.isReference()) {
113 b.set(fi.getStorageOffset());
116 v = FinalBitSet.create(b);
117 if (v == null) throw new IllegalStateException("Null BitArray returned.");
118 instanceRefMasks.put(ci, v);
123 protected FinalBitSet getStaticRefMask(ClassInfo ci) {
124 FinalBitSet v = staticRefMasks.get(ci);
126 BitArray b = new BitArray(ci.getStaticDataSize());
127 for (FieldInfo fi : filter.getMatchedStaticFields(ci)) {
128 if (fi.isReference()) {
129 b.set(fi.getStorageOffset());
132 v = FinalBitSet.create(b);
133 if (v == null) throw new IllegalStateException("Null BitArray returned.");
134 staticRefMasks.put(ci, v);
139 protected FinalBitSet getInstanceFilterMask(ClassInfo ci) {
140 FinalBitSet v = instanceFilterMasks.get(ci);
142 BitArray b = new BitArray(ci.getInstanceDataSize());
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++) {
151 v = FinalBitSet.create(b);
152 if (v == null) throw new IllegalStateException("Null BitArray returned.");
153 instanceFilterMasks.put(ci, v);
158 protected FinalBitSet getStaticFilterMask(ClassInfo ci) {
159 FinalBitSet v = staticFilterMasks.get(ci);
161 BitArray b = new BitArray(ci.getStaticDataSize());
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++) {
170 v = FinalBitSet.create(b);
171 if (v == null) throw new IllegalStateException("Null BitArray returned.");
172 staticFilterMasks.put(ci, v);
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
181 if (refQueue == null){
182 refQueue = new ArrayObjectQueue<ElementInfo>();
189 //--- those are the methods that can be overridden by subclasses to implement abstractions
191 // needs to be public because of ReferenceProcessor interface
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
206 protected void processArrayFields (ArrayFields afields){
207 buf.add(afields.arrayLength());
209 if (afields.isReferenceArray()) {
210 int[] values = afields.asReferenceArray();
211 for (int i = 0; i < values.length; i++) {
212 processReference(values[i]);
215 afields.appendTo(buf);
219 protected void processNamedFields (ClassInfo ci, Fields fields){
220 FinalBitSet filtered = getInstanceFilterMask(ci);
221 FinalBitSet refs = getInstanceRefMask(ci);
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
227 int[] values = fields.asFieldSlots();
228 for (int i = 0; i < values.length; i++) {
229 if (!filtered.get(i)) {
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
247 public void process (ElementInfo ei) {
248 Fields fields = ei.getFields();
249 ClassInfo ci = ei.getClassInfo();
250 buf.add(ci.getUniqueId());
252 if (fields instanceof ArrayFields) { // not filtered
253 processArrayFields((ArrayFields)fields);
255 } else { // named fields, filtered
256 processNamedFields(ci, fields);
260 protected void processReferenceQueue () {
261 refQueue.process(this);
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.
269 protected void serializeStackFrames() {
270 ThreadList tl = ks.getThreadList();
272 for (ThreadInfo ti : tl) {
274 serializeStackFrames(ti);
279 protected void serializeStackFrames(ThreadInfo ti){
280 // we need to add the thread object itself as a root
281 processReference( ti.getThreadObjectRef());
283 for (StackFrame frame = ti.getTopFrame(); frame != null; frame = frame.getPrevious()){
284 serializeFrame(frame);
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());
293 int len = frame.getTopPos()+1;
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]);
308 protected void serializeFrame(StackFrame frame){
309 buf.add(frame.getMethodInfo().getGlobalId());
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();
315 buf.add(pc.getInstructionIndex());
320 int len = frame.getTopPos()+1;
323 int[] slots = frame.getSlots();
324 buf.append(slots,0,len);
326 frame.visitReferenceSlots(this);
329 // this is called after the heap got serialized, i.e. we should not use
330 // processReference() anymore.
331 protected void serializeThreadState (ThreadInfo ti){
333 buf.add( ti.getId());
334 buf.add( ti.getState().ordinal());
335 buf.add( ti.getStackDepth());
338 // NOTE: both lockRef and lockedObjects can only refer to live objects
339 // which are already heap-processed at this point (i.e. have a valid 'sid'
340 // in case we don't want to directly serialize the reference values)
342 // the object we are waiting for
343 ElementInfo eiLock = ti.getLockObject();
345 buf.add(getSerializedReferenceValue( eiLock));
348 // the objects we hold locks for
349 // NOTE: this should be independent of lockedObjects order, hence we
350 // have to factor this out
351 serializeLockedObjects( ti.getLockedObjects());
354 // NOTE: this should not be called before all live references have been processed
355 protected int getSerializedReferenceValue (ElementInfo ei){
356 return ei.getObjectRef();
359 protected void serializeLockedObjects(List<ElementInfo> lockedObjects){
360 // lockedObjects are already a set since we don't have multiple entries
361 // (that would just increase the lock count), but our serialization should
362 // NOT produce different values depending on order of entry. We could achieve this by using
363 // a canonical order (based on reference or sid values), but this would require
364 // System.arraycopys and object allocation, which is too much overhead
365 // given that the number of lockedObjects is small for all but the most
366 // pathological systems under test.
367 // We could spend all day to compute the perfect order-independent hash function,
368 // but since our StateSet isn't guaranteed to be collision free anyway, we
369 // rather shoot for something that can be nicely JITed
370 int n = lockedObjects.size();
374 if (n == 1){ // no order involved
375 buf.add( getSerializedReferenceValue( lockedObjects.get(0)));
378 // don't burn an iterator on this, 'n' is supposed to be small
379 int h = (n << 16) + (n % 3);
380 for (int i=0; i<n; i++){
381 int rot = (getSerializedReferenceValue( lockedObjects.get(i))) % 31;
382 h ^= (h << rot) | (h >>> (32 - rot)); // rotate left
389 protected void serializeThreadStates (){
390 ThreadList tl = ks.getThreadList();
392 for (ThreadInfo ti : tl) {
394 serializeThreadState(ti);
399 protected void serializeClassLoaders(){
400 buf.add(ks.classLoaders.size());
402 for (ClassLoaderInfo cl : ks.classLoaders) {
404 serializeStatics(cl.getStatics());
409 protected void serializeStatics(Statics statics){
410 buf.add(statics.size());
412 for (StaticElementInfo sei : statics.liveStatics()) {
417 protected void serializeClass (StaticElementInfo sei){
418 buf.add(sei.getStatus());
420 Fields fields = sei.getFields();
421 ClassInfo ci = sei.getClassInfo();
422 FinalBitSet filtered = getStaticFilterMask(ci);
423 FinalBitSet refs = getStaticRefMask(ci);
424 int max = ci.getStaticDataSize();
425 for (int i = 0; i < max; i++) {
426 if (!filtered.get(i)) {
427 int v = fields.getIntValue(i);
437 protected void serializeNativeStateHolders(){
438 for (NativeStateHolder nsh : nativeStateHolders){
439 serializeNativeStateHolder(nsh);
443 protected void serializeNativeStateHolder (NativeStateHolder nsh){
444 buf.add(nsh.getHash());
447 //--- our main purpose in life
450 protected int[] computeStoringData() {
454 initReferenceQueue();
456 //--- serialize all live objects and loaded classes
457 serializeStackFrames();
458 serializeClassLoaders();
459 processReferenceQueue();
461 //--- now serialize the thread states (which might refer to live objects)
462 // we do this last because threads contain some internal references
463 // (locked objects etc) that should NOT set the canonical reference serialization
464 // values (if they are encountered before their first explicit heap reference)
465 serializeThreadStates();
467 //--- last is serialization of native state holders
468 serializeNativeStateHolders();
470 return buf.toArray();
473 protected void dumpData() {
475 System.out.print("serialized data: [");
476 for (int i=0; i<n; i++) {
478 System.out.print(',');
480 System.out.print(buf.get(i));
482 System.out.println(']');