KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gov > nasa > jpf > tools > IdleFilter


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.tools;
20
21 import gov.nasa.jpf.Config;
22 import gov.nasa.jpf.JPF;
23 import gov.nasa.jpf.Search;
24 import gov.nasa.jpf.ListenerAdapter;
25 import gov.nasa.jpf.VM;
26 import gov.nasa.jpf.jvm.ClassInfo;
27 import gov.nasa.jpf.jvm.JVM;
28 import gov.nasa.jpf.jvm.MethodInfo;
29 import gov.nasa.jpf.jvm.ThreadInfo;
30 import gov.nasa.jpf.jvm.bytecode.ArrayStoreInstruction;
31 import gov.nasa.jpf.jvm.bytecode.Instruction;
32 import gov.nasa.jpf.jvm.bytecode.InvokeInstruction;
33 import gov.nasa.jpf.util.DynamicObjectArray;
34
35 import java.util.HashMap JavaDoc;
36 import java.util.logging.Logger JavaDoc;
37
38 /**
39  * simple combined listener that checks if a thread seems to do idle loops that
40  * might starve other threads. The most classical case is a "busy wait" loop
41  * like
42  *
43  * for (long l=0; l<1000000; l++);
44  *
45  * which would give us a pretty long path. Even worse, things like
46  *
47  * while (true);
48  *
49  * would never return if we don't break the partial order execution loop. Once
50  * IdleFilter determines a thread is not doing anything useful (no field access,
51  * no array element access, no method calls, huge number of back jumps), it
52  * breaks the POR loop and increases a counter. If it encounters the same thread
53  * doing this again consecutively, it marks the state as seen, which prunes the
54  * whole search tree underneath it
55  */
56 public class IdleFilter extends ListenerAdapter {
57
58   static Logger JavaDoc log = JPF.getLogger("gov.nasa.jpf.tools.IdleFilter");
59
60   static class ThreadStat {
61     String JavaDoc tname;
62
63     int backJumps;
64
65     boolean isCleared = false;
66
67     int loopStartPc;
68
69     int loopEndPc;
70
71     int loopStackDepth;
72
73     ThreadStat(String JavaDoc tname) {
74       this.tname = tname;
75     }
76   }
77
78   DynamicObjectArray threadStats = new DynamicObjectArray(16);
79
80   ThreadStat ts;
81
82   int maxBackJumps;
83
84   boolean jumpPast;
85
86   // ----------------------------------------------------- SearchListener
87 // interface
88
89   public IdleFilter(Config config) {
90     maxBackJumps = config.getInt("idle.max_backjumps", 500);
91     jumpPast = config.getBoolean("idle.jump", false);
92   }
93
94   public void stateAdvanced(Search search) {
95     ts.backJumps = 0;
96     ts.isCleared = false;
97     ts.loopStackDepth = 0;
98     ts.loopStartPc = ts.loopEndPc = 0;
99   }
100
101   public void stateBacktracked(Search search) {
102     ts.backJumps = 0;
103     ts.isCleared = false;
104     ts.loopStackDepth = 0;
105     ts.loopStartPc = ts.loopEndPc = 0;
106   }
107
108   // ----------------------------------------------------- VMListener interface
109 public void instructionExecuted(VM vm) {
110     JVM jvm = (JVM) vm;
111     Instruction insn = jvm.getLastInstruction();
112     ThreadInfo ti = jvm.getLastThreadInfo();
113
114     int tid = ti.getIndex();
115     ts = (ThreadStat) threadStats.get(tid);
116     if (ts == null) {
117       ts = new ThreadStat(ti.getName());
118       threadStats.set(tid, ts);
119     }
120
121     if (insn.isBackJump()) {
122       ts.backJumps++;
123
124       int loopStackDepth = ti.countStackFrames();
125       int loopPc = jvm.getNextInstruction().getPosition();
126
127       if ((loopStackDepth != ts.loopStackDepth) || (loopPc != ts.loopStartPc)) {
128         // new loop, reset
129 ts.isCleared = false;
130         ts.loopStackDepth = loopStackDepth;
131         ts.loopStartPc = loopPc;
132         ts.loopEndPc = insn.getPosition();
133         ts.backJumps = 0;
134       } else {
135         if (!ts.isCleared) {
136           if (ts.backJumps > maxBackJumps) {
137
138             ti.yield(); // this breaks the executePorStep loop
139 MethodInfo mi = insn.getMethod();
140             ClassInfo ci = mi.getClassInfo();
141             int line = mi.getLineNumber(insn);
142             String JavaDoc file = ci.getSourceFileName();
143
144             if (jumpPast) {
145               // pretty bold, we jump past the loop end and go on from there
146
147               Instruction next = insn.getNext();
148               ti.setPC(next);
149
150               log.warning("WARNING: IdleFilter jumped past loop in: "
151                   + ti.getName() + "\n\tat " + ci.getName() + "."
152                   + mi.getName() + "(" + file + ":" + line + ")");
153             } else {
154               // cut this sucker off - we declare this a visited state
155 jvm.setIgnoreState(true);
156               
157               log.warning("WARNING: IdleFilter pruned thread: " + ti.getName()
158                   + "\n\tat " + ci.getName() + "." + mi.getName() + "(" + file
159                   + ":" + line + ")");
160             }
161           }
162         }
163       }
164
165     } else if (!ts.isCleared) {
166       // if we call methods or set array elements inside the loop in question,
167 // we assume this is not an idle loop and terminate the checks
168 if ((insn instanceof InvokeInstruction)
169           || (insn instanceof ArrayStoreInstruction)) {
170         int stackDepth = ti.countStackFrames();
171         int pc = insn.getPosition();
172
173         if (stackDepth == ts.loopStackDepth) {
174           if ((pc >= ts.loopStartPc) && (pc < ts.loopEndPc)) {
175             ts.isCleared = true;
176           }
177         }
178       }
179     }
180   }
181
182 }
183
Popular Tags