src/main/gov/nasa/jpf/listener/HeapTracker.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.PropertyListenerAdapter;
  23 import gov.nasa.jpf.report.ConsolePublisher;
  24 import gov.nasa.jpf.report.Publisher;
  25 import gov.nasa.jpf.search.Search;
  26 import gov.nasa.jpf.util.DynamicObjectArray;
  27 import gov.nasa.jpf.util.Misc;
  28 import gov.nasa.jpf.util.SourceRef;
  29 import gov.nasa.jpf.util.StringSetMatcher;
  30 import gov.nasa.jpf.vm.ClassInfo;
  31 import gov.nasa.jpf.vm.ElementInfo;
  32 import gov.nasa.jpf.vm.Heap;
  33 import gov.nasa.jpf.vm.VM;
  34 import gov.nasa.jpf.vm.MethodInfo;
  35 import gov.nasa.jpf.vm.ThreadInfo;
  36
  37 import java.io.PrintWriter;
  38 import java.util.ArrayList;
  39 import java.util.Comparator;
  40 import java.util.HashMap;
  41 import java.util.Map;
  42 import java.util.Stack;
  43
  44 /**
  45  * HeapTracker - property-listener class to check heap utilization along all
  46  * execution paths (e.g. to verify heap bounds)
  47  */
  48 public class HeapTracker extends PropertyListenerAdapter {
  49
  50   static class PathStat implements Cloneable {
  51     int nNew = 0;
  52     int nReleased = 0;
  53     int heapSize = 0;  // in bytes
  54
  55     @Override
  56         public Object clone() {
  57       try {
  58         return super.clone();
  59       } catch (CloneNotSupportedException e) {
  60         return null;
  61       }
  62     }
  63   }
  64
  65   static class TypeStat {
  66     String typeName;
  67     int nAlloc;
  68     int nReleased;
  69
  70     TypeStat (String typeName){
  71       this.typeName = typeName;
  72     }
  73   }
  74
  75   PathStat stat = new PathStat();
  76   Stack<PathStat> pathStats = new Stack<PathStat>();
  77
  78   DynamicObjectArray<SourceRef> loc = new DynamicObjectArray<SourceRef>();
  79
  80   HashMap<String,TypeStat> typeStat = new HashMap<String,TypeStat>();
  81
  82   int maxState;
  83   int nForward;
  84   int nBacktrack;
  85
  86   int nElemTotal;
  87   int nGcTotal;
  88   int nSharedTotal;
  89   int nImmutableTotal;
  90
  91   int nElemMax = Integer.MIN_VALUE;
  92   int nElemMin = Integer.MAX_VALUE;
  93   int nElemAv;
  94
  95   int pElemSharedMax = Integer.MIN_VALUE;
  96   int pElemSharedMin = Integer.MAX_VALUE;
  97   int pElemSharedAv;
  98
  99   int pElemImmutableMax = Integer.MIN_VALUE;
 100   int pElemImmutableMin = Integer.MAX_VALUE;
 101   int pElemImmutableAv;
 102
 103   int nReleased;
 104   int nReleasedTotal;
 105   int nReleasedAv;
 106   int nReleasedMax = Integer.MIN_VALUE;
 107   int nReleasedMin = Integer.MAX_VALUE;
 108
 109   int maxPathHeap = Integer.MIN_VALUE;
 110   int maxPathNew = Integer.MIN_VALUE;
 111   int maxPathReleased = Integer.MIN_VALUE;
 112   int maxPathAlive = Integer.MIN_VALUE;
 113
 114   int initHeap = 0;
 115   int initNew = 0;
 116   int initReleased = 0;
 117   int initAlive = 0;
 118
 119
 120   boolean showTypeStats;
 121   int maxTypesShown;
 122
 123   // used as a property check
 124   int maxHeapSizeLimit;
 125   int maxLiveLimit;
 126   boolean throwOutOfMemory = false;
 127
 128   StringSetMatcher includes, excludes;
 129
 130   void updateMaxPathValues() {
 131       if (stat.heapSize > maxPathHeap) {
 132         maxPathHeap = stat.heapSize;
 133       }
 134
 135       if (stat.nNew > maxPathNew) {
 136         maxPathNew = stat.nNew;
 137       }
 138
 139       if (stat.nReleased > maxPathReleased) {
 140         maxPathReleased = stat.nReleased;
 141       }
 142
 143       int nAlive = stat.nNew - stat.nReleased;
 144       if (nAlive > maxPathAlive) {
 145         maxPathAlive = nAlive;
 146       }
 147   }
 148
 149   void allocTypeStats (ElementInfo ei) {
 150     String typeName = ei.getClassInfo().getName();
 151     TypeStat ts = typeStat.get(typeName);
 152     if (ts == null) {
 153       ts = new TypeStat(typeName);
 154       typeStat.put(typeName, ts);
 155     }
 156     ts.nAlloc++;
 157   }
 158
 159   void releaseTypeStats (ElementInfo ei) {
 160     String typeName = ei.getClassInfo().getName();
 161     TypeStat ts = typeStat.get(typeName);
 162     if (ts != null) {
 163       ts.nReleased++;
 164     }
 165   }
 166
 167
 168   public HeapTracker (Config config, JPF jpf) {
 169     maxHeapSizeLimit = config.getInt("heap.size_limit", -1);
 170     maxLiveLimit = config.getInt("heap.live_limit", -1);
 171     throwOutOfMemory = config.getBoolean("heap.throw_exception");
 172     showTypeStats = config.getBoolean("heap.show_types");
 173     maxTypesShown = config.getInt("heap.max_types", 20);
 174
 175     includes = StringSetMatcher.getNonEmpty(config.getStringArray("heap.include"));
 176     excludes = StringSetMatcher.getNonEmpty(config.getStringArray("heap.exclude"));
 177
 178     jpf.addPublisherExtension(ConsolePublisher.class, this);
 179   }
 180
 181   /******************************************* abstract Property *****/
 182
 183   /**
 184    * return 'false' if property is violated
 185    */
 186   @Override
 187   public boolean check (Search search, VM vm) {
 188     if (throwOutOfMemory) {
 189       // in this case we don't want to stop the program, but see if it
 190       // behaves gracefully - don't report a property violation
 191       return true;
 192     } else {
 193       if ((maxHeapSizeLimit >= 0) && (stat.heapSize > maxHeapSizeLimit)) {
 194         return false;
 195       }
 196       if ((maxLiveLimit >=0) && ((stat.nNew - stat.nReleased) > maxLiveLimit)) {
 197         return false;
 198       }
 199
 200       return true;
 201     }
 202   }
 203
 204   @Override
 205   public String getErrorMessage () {
 206     return "heap limit exceeded: " + stat.heapSize + " > " + maxHeapSizeLimit;
 207   }
 208
 209   /******************************************* SearchListener interface *****/
 210   @Override
 211   public void searchStarted(Search search) {
 212     super.searchStarted(search);
 213
 214     updateMaxPathValues();
 215     pathStats.push(stat);
 216
 217     initHeap = stat.heapSize;
 218     initNew = stat.nNew;
 219     initReleased = stat.nReleased;
 220     initAlive = initNew - initReleased;
 221
 222     stat = (PathStat)stat.clone();
 223   }
 224
 225   @Override
 226   public void stateAdvanced(Search search) {
 227
 228     if (search.isNewState()) {
 229       int id = search.getStateId();
 230
 231       if (id > maxState) maxState = id;
 232
 233       updateMaxPathValues();
 234       pathStats.push(stat);
 235       stat = (PathStat)stat.clone();
 236
 237       nForward++;
 238     }
 239   }
 240
 241   @Override
 242   public void stateBacktracked(Search search) {
 243     nBacktrack++;
 244
 245     if (!pathStats.isEmpty()){
 246       stat = pathStats.pop();
 247     }
 248   }
 249
 250   /******************************************* PublisherExtension interface ****/
 251   @Override
 252   public void publishFinished (Publisher publisher) {
 253     PrintWriter pw = publisher.getOut();
 254     publisher.publishTopicStart("heap statistics");
 255
 256     pw.println("heap statistics:");
 257     pw.println("  states:         " + maxState);
 258     pw.println("  forwards:       " + nForward);
 259     pw.println("  backtrack:      " + nBacktrack);
 260     pw.println();
 261     pw.println("  gc cycles:      " + nGcTotal);
 262     pw.println();
 263     pw.println("  max Objects:    " + nElemMax);
 264     pw.println("  min Objects:    " + nElemMin);
 265     pw.println("  avg Objects:    " + nElemAv);
 266     pw.println();
 267     pw.println("  max% shared:    " + pElemSharedMax);
 268     pw.println("  min% shared:    " + pElemSharedMin);
 269     pw.println("  avg% shared:    " + pElemSharedAv);
 270     pw.println();
 271     pw.println("  max% immutable: " + pElemImmutableMax);
 272     pw.println("  min% immutable: " + pElemImmutableMin);
 273     pw.println("  avg% immutable: " + pElemImmutableAv);
 274     pw.println();
 275     pw.println("  max released:   " + nReleasedMax);
 276     pw.println("  min released:   " + nReleasedMin);
 277     pw.println("  avg released:   " + nReleasedAv);
 278
 279     pw.println();
 280     pw.print(  "  max path heap (B):   " + maxPathHeap);
 281     pw.println(" / " + (maxPathHeap - initHeap));
 282     pw.print(  "  max path alive:      " + maxPathAlive);
 283     pw.println(" / " + (maxPathAlive - initAlive));
 284     pw.print(  "  max path new:        " + maxPathNew);
 285     pw.println(" / " + (maxPathNew - initNew));
 286     pw.print(  "  max path released:   " + maxPathReleased);
 287     pw.println(" / " + (maxPathReleased - initReleased));
 288
 289     if (showTypeStats) {
 290       pw.println();
 291       pw.println("  type allocation statistics:");
 292
 293       ArrayList<Map.Entry<String,TypeStat>> list =
 294         Misc.createSortedEntryList(typeStat, new Comparator<Map.Entry<String,TypeStat>>() {
 295           @Override
 296                 public int compare (Map.Entry<String,TypeStat> e1,
 297                               Map.Entry<String,TypeStat> e2) {
 298           return Integer.signum(e1.getValue().nAlloc - e2.getValue().nAlloc);
 299         }});
 300
 301       int i=0;
 302       for (Map.Entry<String,TypeStat> e : list) {
 303         TypeStat ts = e.getValue();
 304         pw.print("  ");
 305         pw.print(String.format("%1$9d : ", ts.nAlloc));
 306         pw.println(ts.typeName);
 307
 308         if (i++ > maxTypesShown) {
 309           pw.println("  ...");
 310           break;
 311         }
 312       }
 313     }
 314   }
 315
 316
 317   /******************************************* VMListener interface *********/
 318   @Override
 319   public void gcBegin(VM vm) {
 320     /**
 321      System.out.println();
 322      System.out.println( "----- gc cycle: " + vm.getDynamicArea().getGcNumber()
 323      + ", state: " + vm.getStateId());
 324      **/
 325   }
 326
 327   @Override
 328   public void gcEnd(VM vm) {
 329     Heap heap = vm.getHeap();
 330
 331     int n = 0;
 332     int nShared = 0;
 333     int nImmutable = 0;
 334
 335     for (ElementInfo ei : heap.liveObjects()) {
 336       n++;
 337
 338       if (ei.isShared()) nShared++;
 339       if (ei.isImmutable()) nImmutable++;
 340
 341       //printElementInfo(ei);
 342     }
 343
 344     nElemTotal += n;
 345     nGcTotal++;
 346
 347     if (n > nElemMax) nElemMax = n;
 348     if (n < nElemMin) nElemMin = n;
 349
 350     int pShared = (nShared * 100) / n;
 351     int pImmutable = (nImmutable * 100) / n;
 352
 353     if (pShared > pElemSharedMax) pElemSharedMax = pShared;
 354     if (pShared < pElemSharedMin) pElemSharedMin = pShared;
 355
 356     nSharedTotal += nShared;
 357     nImmutableTotal += nImmutable;
 358
 359     pElemSharedAv = (nSharedTotal * 100) / nElemTotal;
 360     pElemImmutableAv = (nImmutableTotal * 100) / nElemTotal;
 361
 362     if (pImmutable > pElemImmutableMax) pElemImmutableMax = pImmutable;
 363     if (pImmutable < pElemImmutableMin) pElemImmutableMin = pImmutable;
 364
 365     nElemAv = nElemTotal / nGcTotal;
 366     nReleasedAv = nReleasedTotal / nGcTotal;
 367
 368     if (nReleased > nReleasedMax) nReleasedMax = nReleased;
 369     if (nReleased < nReleasedMin) nReleasedMin = nReleased;
 370
 371     nReleased = 0;
 372   }
 373
 374   boolean isRelevantType (ElementInfo ei) {
 375     String clsName = ei.getClassInfo().getName();
 376     return StringSetMatcher.isMatch(clsName, includes, excludes);
 377   }
 378
 379   @Override
 380   public void objectCreated(VM vm, ThreadInfo ti, ElementInfo ei) {
 381     int idx = ei.getObjectRef();
 382     int line = ti.getLine();
 383     MethodInfo mi = ti.getTopFrameMethodInfo();
 384     SourceRef sr = null;
 385
 386     if (!isRelevantType(ei)) {
 387       return;
 388     }
 389
 390     if (mi != null) {
 391       ClassInfo mci = mi.getClassInfo();
 392       if (mci != null) {
 393         String file = mci.getSourceFileName();
 394         if (file != null) {
 395           sr = new SourceRef(file, line);
 396         } else {
 397           sr = new SourceRef(mci.getName(), line);
 398         }
 399       }
 400     }
 401
 402     // means references with null loc are from synthetic methods
 403     loc.set(idx, sr);
 404
 405     stat.nNew++;
 406     stat.heapSize += ei.getHeapSize();
 407
 408     // update the type statistics
 409     if (showTypeStats) {
 410       allocTypeStats(ei);
 411     }
 412
 413
 414     // check if we should simulate an OutOfMemoryError
 415     if (throwOutOfMemory) {
 416       if (((maxHeapSizeLimit >=0) && (stat.heapSize > maxHeapSizeLimit)) ||
 417           ((maxLiveLimit >=0) && ((stat.nNew - stat.nReleased) > maxLiveLimit))){
 418         vm.getHeap().setOutOfMemory(true);
 419       }
 420     }
 421   }
 422
 423   @Override
 424   public void objectReleased(VM vm, ThreadInfo ti, ElementInfo ei) {
 425
 426     if (!isRelevantType(ei)) {
 427       return;
 428     }
 429
 430     nReleasedTotal++;
 431     nReleased++;
 432
 433     if (showTypeStats) {
 434       releaseTypeStats(ei);
 435     }
 436
 437     stat.nReleased++;
 438     stat.heapSize -= ei.getHeapSize();
 439   }
 440
 441   /****************************************** private stuff ******/
 442   protected void printElementInfo(ElementInfo ei) {
 443     boolean first = false;
 444
 445     System.out.print( ei.getObjectRef());
 446     System.out.print( ": ");
 447     System.out.print( ei.getClassInfo().getName());
 448     System.out.print( "  [");
 449
 450     if (ei.isShared()) {
 451       System.out.print( "shared");
 452       first = false;
 453     }
 454     if (ei.isImmutable()) {
 455       if (!first) System.out.print(' ');
 456       System.out.print( "immutable");
 457     }
 458     System.out.print( "] ");
 459
 460     SourceRef sr = loc.get(ei.getObjectRef());
 461     if (sr != null) {
 462       System.out.println(sr);
 463     } else {
 464       System.out.println("?");
 465     }
 466   }
 467
 468
 469   static void printUsage () {
 470     System.out.println("HeapTracker - a JPF listener tool to report and check heap utilization");
 471     System.out.println("usage: java gov.nasa.jpf.tools.HeapTracker <jpf-options> <heapTracker-options> <class>");
 472     System.out.println("       +heap.size_limit=<num> : report property violation if heap exceeds <num> bytes");
 473     System.out.println("       +heap.live_limit=<num> : report property violation if more than <num> live objects");
 474     System.out.println("       +heap.classes=<regEx> : only report instances of classes matching <regEx>");
 475     System.out.println("       +heap.throw_exception=<bool>: throw a OutOfMemoryError instead of reporting property violation");
 476   }
 477 }
 478