src/main/gov/nasa/jpf/listener/MethodAnalyzer.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.listener;
  19
  20 import gov.nasa.jpf.Config;
  21 import gov.nasa.jpf.JPF;
  22 import gov.nasa.jpf.ListenerAdapter;
  23 import gov.nasa.jpf.jvm.bytecode.InstanceInvocation;
  24 import gov.nasa.jpf.jvm.bytecode.JVMInvokeInstruction;
  25 import gov.nasa.jpf.jvm.bytecode.JVMReturnInstruction;
  26 import gov.nasa.jpf.report.ConsolePublisher;
  27 import gov.nasa.jpf.report.Publisher;
  28 import gov.nasa.jpf.search.Search;
  29 import gov.nasa.jpf.util.StringSetMatcher;
  30 import gov.nasa.jpf.vm.ElementInfo;
  31 import gov.nasa.jpf.vm.Instruction;
  32 import gov.nasa.jpf.vm.MJIEnv;
  33 import gov.nasa.jpf.vm.VM;
  34 import gov.nasa.jpf.vm.MethodInfo;
  35 import gov.nasa.jpf.vm.StackFrame;
  36 import gov.nasa.jpf.vm.ThreadInfo;
  37 import gov.nasa.jpf.vm.Types;
  38
  39 import java.io.PrintWriter;
  40 import java.util.HashMap;
  41
  42
  43 /**
  44  * analyzes call/execute sequences of methods
  45  * closely modeled after the DeadlockAnalyzer, i.e. keeps it's own
  46  * log and doesn't require full instruction trace
  47  *
  48  * <2do> this needs to be refactored with DeadlockAnalyzer - the whole
  49  * trace mgnt (except of the printing) can be made generic
  50  */
  51 public class MethodAnalyzer extends ListenerAdapter {
  52
  53   enum OpType { CALL (">  "),                 // invokeX breaks transition (e.g. blocked sync)
  54                 EXECUTE (" - "),              // method entered method after transition break
  55                 CALL_EXECUTE (">- "),         // call & enter within same transition
  56                 RETURN ("  <"),               // method returned
  57                 EXEC_RETURN (" -<"),          // enter & return in consecutive ops
  58                 CALL_EXEC_RETURN (">-<");     // call & enter & return in consecutive ops
  59     String code;
  60     OpType (String code){ this.code = code; }
  61   };
  62
  63   static class MethodOp {
  64     OpType type;
  65
  66     ThreadInfo ti;
  67     ElementInfo ei;
  68     Instruction insn; // the caller
  69     MethodInfo mi;    // the callee
  70     int stackDepth;
  71
  72     // this is used to keep our own trace
  73     int stateId = 0;
  74     MethodOp prevTransition;
  75     MethodOp p;   // prev during execution
  76
  77     MethodOp (OpType type, MethodInfo mi, ThreadInfo ti, ElementInfo ei, int stackDepth){
  78       this.type = type;
  79       this.ti = ti;
  80       this.mi = mi;
  81       this.ei = ei;
  82       this.stackDepth = stackDepth;
  83     }
  84
  85     MethodOp clone (OpType newType){
  86       MethodOp op = new MethodOp(newType, mi, ti, ei, stackDepth);
  87       op.p = p;
  88       return op;
  89     }
  90
  91     boolean isMethodEnter() {
  92       return (type == OpType.CALL_EXECUTE) || (type == OpType.EXECUTE);
  93     }
  94
  95     boolean isSameMethod(MethodOp op) {
  96       return (mi == op.mi) && (ti == op.ti) && (ei == op.ei) && (stackDepth == op.stackDepth);
  97     }
  98
  99     void printOn(PrintWriter pw, MethodAnalyzer analyzer) {
 100       pw.print(ti.getId());
 101       pw.print(": ");
 102
 103       pw.print(type.code);
 104       pw.print(' ');
 105
 106       if (analyzer.showDepth){
 107         for (int i = 0; i < stackDepth; i++) {
 108           pw.print('.');
 109         }
 110         pw.print(' ');
 111       }
 112
 113       if (!mi.isStatic()){
 114         if (ei.getClassInfo() != mi.getClassInfo()){ // method is in superclass
 115           pw.print(mi.getClassName());
 116           pw.print('<');
 117           pw.print(ei);
 118           pw.print('>');
 119         } else { // method is in concrete object class
 120           pw.print(ei);
 121         }
 122       } else {
 123         pw.print(mi.getClassName());
 124       }
 125
 126       pw.print('.');
 127
 128       pw.print(Types.getDequalifiedMethodSignature(mi.getUniqueName()));
 129     }
 130
 131     @Override
 132         public String toString() {
 133       return "Op {" + ti.getName() + ',' + type.code +
 134                    ',' + mi.getFullName() + ',' + ei + '}';
 135     }
 136   }
 137
 138   // report options
 139
 140   StringSetMatcher includes = null; //  means all
 141   StringSetMatcher excludes = null; //  means none
 142
 143   int maxHistory;
 144   String format;
 145   boolean skipInit;
 146   boolean showDepth;
 147   boolean showTransition;
 148   boolean showCompleted;
 149
 150   // execution environment
 151
 152   VM vm;
 153   Search search;
 154
 155   OpType opType;
 156
 157   // this is used to keep our own trace
 158   MethodOp lastOp;
 159   MethodOp lastTransition;
 160   boolean isFirstTransition = true;
 161
 162   // this is set after we call revertAndFlatten during reporting
 163   // (we can't call revertAndFlatten twice since it is destructive, but
 164   // we might have to report several times in case we have several publishers)
 165   MethodOp firstOp = null;
 166
 167   // for HeuristicSearches. Ok, that's braindead but at least no need for cloning
 168   HashMap<Integer,MethodOp> storedTransition = new HashMap<Integer,MethodOp>();
 169
 170
 171   public MethodAnalyzer (Config config, JPF jpf){
 172     jpf.addPublisherExtension(ConsolePublisher.class, this);
 173
 174     maxHistory = config.getInt("method.max_history", Integer.MAX_VALUE);
 175     format = config.getString("method.format", "raw");
 176     skipInit = config.getBoolean("method.skip_init", true);
 177     showDepth = config.getBoolean("method.show_depth", false);
 178     showTransition = config.getBoolean("method.show_transition", false);
 179
 180     includes = StringSetMatcher.getNonEmpty(config.getStringArray("method.include"));
 181     excludes = StringSetMatcher.getNonEmpty(config.getStringArray("method.exclude"));
 182
 183     vm = jpf.getVM();
 184     search = jpf.getSearch();
 185   }
 186
 187
 188   void addOp (VM vm, OpType opType, MethodInfo mi, ThreadInfo ti, ElementInfo ei, int stackDepth){
 189     if (!(skipInit && isFirstTransition)) {
 190       MethodOp op = new MethodOp(opType, mi, ti, ei, stackDepth);
 191       if (lastOp == null){
 192         lastOp = op;
 193       } else {
 194         op.p = lastOp;
 195         lastOp = op;
 196       }
 197     }
 198   }
 199
 200   boolean isAnalyzedMethod (MethodInfo mi){
 201     if (mi != null){
 202       String mthName = mi.getFullName();
 203       return StringSetMatcher.isMatch(mthName, includes, excludes);
 204     } else {
 205       return false;
 206     }
 207   }
 208
 209   void printOn (PrintWriter pw) {
 210     MethodOp start = firstOp;
 211     int lastStateId  = Integer.MIN_VALUE;
 212     int transition = skipInit ? 1 : 0;
 213     int lastTid = start.ti.getId();
 214
 215     for (MethodOp op = start; op != null; op = op.p) {
 216
 217       if (showTransition) {
 218         if (op.stateId != lastStateId) {
 219           lastStateId = op.stateId;
 220           pw.print("------------------------------------------ #");
 221           pw.println(transition++);
 222         }
 223       } else {
 224         int tid = op.ti.getId();
 225         if (tid != lastTid) {
 226           lastTid = tid;
 227           pw.println("------------------------------------------");
 228         }
 229       }
 230
 231       op.printOn(pw, this);
 232       pw.println();
 233     }
 234   }
 235
 236   // warning - this rotates pointers in situ, i.e. destroys the original structure
 237   MethodOp revertAndFlatten (MethodOp start) {
 238
 239     MethodOp last = null;
 240     MethodOp prevTransition = start.prevTransition;
 241
 242     for (MethodOp op = start; op != null;) {
 243       MethodOp opp = op.p;
 244       op.p = last;
 245
 246       if (opp == null) {
 247         if (prevTransition == null) {
 248           return op;
 249         } else {
 250           last = op;
 251           op = prevTransition;
 252           prevTransition = op.prevTransition;
 253         }
 254       } else {
 255         last = op;
 256         op = opp;
 257       }
 258     }
 259
 260     return null;
 261   }
 262
 263   //--- SearchListener interface
 264   // <2do> this is the same as DeadlockAnalyzer, except of xxOp type -> refactor
 265   @Override
 266   public void stateAdvanced (Search search){
 267
 268     if (search.isNewState() && (lastOp != null)) {
 269       int stateId = search.getStateId();
 270
 271       for (MethodOp op=lastOp; op != null; op=op.p) {
 272         op.stateId = stateId;
 273       }
 274
 275       lastOp.prevTransition = lastTransition;
 276       lastTransition = lastOp;
 277     }
 278
 279     lastOp = null;
 280     isFirstTransition = false;
 281   }
 282
 283   @Override
 284   public void stateBacktracked (Search search){
 285     int stateId = search.getStateId();
 286     while ((lastTransition != null) && (lastTransition.stateId > stateId)){
 287       lastTransition = lastTransition.prevTransition;
 288     }
 289     lastOp = null;
 290   }
 291
 292   @Override
 293   public void stateStored (Search search) {
 294     // always called after stateAdvanced
 295     storedTransition.put(search.getStateId(), lastTransition);
 296   }
 297
 298   @Override
 299   public void stateRestored (Search search) {
 300     int stateId = search.getStateId();
 301     MethodOp op = storedTransition.get(stateId);
 302     if (op != null) {
 303       lastTransition = op;
 304       storedTransition.remove(stateId);  // not strictly required, but we don't come back
 305     }
 306   }
 307
 308
 309   //--- VMlistener interface
 310   @Override
 311   public void instructionExecuted (VM vm, ThreadInfo thread, Instruction nextInsn, Instruction executedInsn) {
 312     ThreadInfo ti;
 313     MethodInfo mi;
 314     ElementInfo ei = null;
 315
 316     if (executedInsn instanceof JVMInvokeInstruction) {
 317       JVMInvokeInstruction call = (JVMInvokeInstruction)executedInsn;
 318       ti = thread;
 319       mi = call.getInvokedMethod(ti);
 320
 321       if (isAnalyzedMethod(mi)) {
 322         OpType type;
 323
 324         // check if this was actually executed, or is a blocked sync call
 325         if (ti.getNextPC() == call) { // re-executed -> blocked or overlayed
 326           type = OpType.CALL;
 327
 328         } else { // executed
 329           if (ti.isFirstStepInsn()) {
 330             type = OpType.EXECUTE;
 331           } else {
 332             type = OpType.CALL_EXECUTE;
 333           }
 334         }
 335
 336         if (call instanceof InstanceInvocation) {
 337           ei = ((InstanceInvocation)call).getThisElementInfo(ti);
 338         }
 339
 340         addOp(vm,type,mi,ti,ei, ti.getStackDepth());
 341       }
 342
 343     } else if (executedInsn instanceof JVMReturnInstruction) {
 344       JVMReturnInstruction ret = (JVMReturnInstruction)executedInsn;
 345       ti = thread;
 346       StackFrame frame = ret.getReturnFrame();
 347       mi = frame.getMethodInfo();
 348
 349       if (isAnalyzedMethod(mi)) {
 350         if (!mi.isStatic()) {
 351           int ref = frame.getThis();
 352           if (ref != MJIEnv.NULL) {
 353             ei = ti.getElementInfo(ref);
 354           }
 355         }
 356
 357         addOp(vm,OpType.RETURN,mi,ti,ei, ti.getStackDepth()+1); // postExec-> frame already popped
 358       }
 359     }
 360   }
 361
 362   //--- the PubisherExtension part
 363   @Override
 364   public void publishPropertyViolation (Publisher publisher) {
 365
 366     if (firstOp == null && lastTransition != null){ // do this just once
 367       firstOp = revertAndFlatten(lastTransition);
 368     }
 369
 370     if (firstOp == null){
 371       return;
 372     }
 373
 374     PrintWriter pw = publisher.getOut();
 375     publisher.publishTopicStart("method ops " + publisher.getLastErrorId());
 376
 377
 378     printOn(pw);
 379   }
 380 }