Robust/src/IR/Flat/BCXPointsToCheckVRuntime.java

   1 package IR.Flat;
   2
   3 import Analysis.Disjoint.HeapAnalysis;
   4 import Analysis.Disjoint.Alloc;
   5 import IR.*;
   6
   7 import java.io.*;
   8 import java.util.*;
   9
  10
  11 // This BuildCode Extension (BCX) takes a heap analysis
  12 // with points-to information and generates checks at runtime
  13 // verifies the allocation site of objects pointed-to.  It
  14 // doesn't fully verify an analysis but it can reveal bugs!
  15
  16
  17 public class BCXPointsToCheckVRuntime implements BuildCodeExtension {
  18
  19   protected BuildCode    buildCode;
  20   protected TypeUtil     typeUtil;
  21   protected HeapAnalysis heapAnalysis;
  22
  23   protected ClassDescriptor cdObject;
  24
  25
  26   public BCXPointsToCheckVRuntime( BuildCode    buildCode,
  27                                    TypeUtil     typeUtil,
  28                                    HeapAnalysis heapAnalysis ) {
  29     this.buildCode    = buildCode;
  30     this.typeUtil     = typeUtil;
  31     this.heapAnalysis = heapAnalysis;
  32   }
  33
  34
  35   public void additionalIncludesMethodsHeader(PrintWriter outmethodheader) {
  36     outmethodheader.println( "#include<stdio.h>" );
  37     outmethodheader.println( "#include<execinfo.h>" );
  38   }
  39
  40
  41   public void additionalCodeAtTopFlatMethodBody(PrintWriter output, FlatMethod fm) {
  42
  43     for( int i = 0; i < fm.numParameters(); ++i ) {
  44       TempDescriptor td   = fm.getParameter( i );
  45       TypeDescriptor type = td.getType();
  46       if( type.isPtr() ) {
  47         genAssertRuntimePtrVsHeapResults( output,
  48                                           fm,
  49                                           td,
  50                                           heapAnalysis.canPointToAfter( td, fm )
  51                                           );
  52       }
  53     }
  54   }
  55
  56
  57   public void additionalCodePreNode(FlatMethod fm, FlatNode fn, PrintWriter output) {
  58
  59     TempDescriptor  lhs;
  60     TempDescriptor  rhs;
  61     FieldDescriptor fld;
  62     TempDescriptor  idx;
  63     TypeDescriptor  type;
  64
  65
  66     switch( fn.kind() ) {
  67
  68       case FKind.FlatOpNode: {
  69         FlatOpNode fon = (FlatOpNode) fn;
  70         if( fon.getOp().getOp() == Operation.ASSIGN ) {
  71           lhs = fon.getDest();
  72           rhs = fon.getLeft();
  73
  74           type = lhs.getType();
  75           if( type.isPtr() ) {
  76             genAssertRuntimePtrVsHeapResults( output,
  77                                               fm,
  78                                               lhs,
  79                                               heapAnalysis.canPointToAt( lhs, fn )
  80                                               );
  81
  82             genAssertRuntimePtrVsHeapResults( output,
  83                                               fm,
  84                                               rhs,
  85                                               heapAnalysis.canPointToAt( rhs, fn )
  86                                               );
  87           }
  88         }
  89       } break;
  90
  91
  92       case FKind.FlatCastNode: {
  93         FlatCastNode fcn = (FlatCastNode) fn;
  94         lhs = fcn.getDst();
  95         rhs = fcn.getSrc();
  96
  97         type = fcn.getType();
  98         if( type.isPtr() ) {
  99           genAssertRuntimePtrVsHeapResults( output,
 100                                             fm,
 101                                             lhs,
 102                                             heapAnalysis.canPointToAt( lhs, fn )
 103                                             );
 104
 105           genAssertRuntimePtrVsHeapResults( output,
 106                                             fm,
 107                                             rhs,
 108                                             heapAnalysis.canPointToAt( rhs, fn )
 109                                             );
 110         }
 111       } break;
 112
 113
 114       case FKind.FlatFieldNode: {
 115         FlatFieldNode ffn = (FlatFieldNode) fn;
 116         lhs = ffn.getDst();
 117         rhs = ffn.getSrc();
 118         fld = ffn.getField();
 119
 120         type = lhs.getType();
 121         if( type.isPtr() ) {
 122           genAssertRuntimePtrVsHeapResults( output,
 123                                             fm,
 124                                             lhs,
 125                                             heapAnalysis.canPointToAt( lhs, fn )
 126                                             );
 127
 128           genAssertRuntimePtrVsHeapResults( output,
 129                                             fm,
 130                                             rhs,
 131                                             heapAnalysis.canPointToAt( rhs, fn )
 132                                             );
 133
 134           genAssertRuntimePtrVsHeapResults( output,
 135                                             fm,
 136                                             rhs,
 137                                             fld,
 138                                             null,
 139                                             heapAnalysis.canPointToAt( rhs, fld, fn )
 140                                             );
 141         }
 142       } break;
 143
 144
 145       case FKind.FlatElementNode: {
 146         FlatElementNode fen = (FlatElementNode) fn;
 147         lhs = fen.getDst();
 148         rhs = fen.getSrc();
 149         idx = fen.getIndex();
 150
 151         type = lhs.getType();
 152         if( type.isPtr() ) {
 153           genAssertRuntimePtrVsHeapResults( output,
 154                                             fm,
 155                                             lhs,
 156                                             heapAnalysis.canPointToAt( lhs, fn )
 157                                             );
 158
 159           genAssertRuntimePtrVsHeapResults( output,
 160                                             fm,
 161                                             rhs,
 162                                             heapAnalysis.canPointToAt( rhs, fn )
 163                                             );
 164
 165           genAssertRuntimePtrVsHeapResults( output,
 166                                             fm,
 167                                             rhs,
 168                                             null,
 169                                             idx,
 170                                             heapAnalysis.canPointToAtElement( rhs, fn )
 171                                             );
 172         }
 173       } break;
 174
 175     }
 176
 177   }
 178
 179
 180   public void additionalCodePostNode(FlatMethod fm,
 181                                      FlatNode fn,
 182                                      PrintWriter output) {
 183     switch( fn.kind() ) {
 184       case FKind.FlatCall: {
 185         FlatCall       fc = (FlatCall) fn;
 186         TempDescriptor td = fc.getReturnTemp();
 187
 188         if( td != null ) {
 189           TypeDescriptor type = td.getType();
 190           if( type.isPtr() ) {
 191             genAssertRuntimePtrVsHeapResults( output,
 192                                               fm,
 193                                               td,
 194                                               heapAnalysis.canPointToAfter( td, fn )
 195                                               );
 196           }
 197         }
 198       } break;
 199     }
 200   }
 201
 202
 203
 204   protected void
 205     printConditionFailed( PrintWriter output,
 206                           String      condition,
 207                           String      pointer ) {
 208
 209     // don't do this in the constructor of this extension object because
 210     // build code hasn't created any types or classes yet!
 211     if( cdObject == null ) {
 212       cdObject = typeUtil.getClass( typeUtil.ObjectClass );
 213       assert cdObject != null;
 214     }
 215
 216     output.println( "printf(\"[[[ CHECK VS HEAP RESULTS FAILED ]]] Condition for failure( "+
 217                     condition+" ) allocsite=%d at %s:%d\\n\", ((struct "+
 218                     cdObject.getSafeSymbol()+"*)"+
 219                     pointer+")->allocsite, __FILE__, __LINE__ );" );
 220
 221     // spit out the stack trace (so fancy!)
 222     output.println( "{" );
 223     output.println( "void* buffer[100];" );
 224     output.println( "char** strings;" );
 225     output.println( "int nptrs,j;" );
 226     output.println( "nptrs = backtrace(buffer, 100);" );
 227     output.println( "strings = backtrace_symbols(buffer, nptrs);" );
 228     output.println( "if (strings == NULL) {" );
 229     output.println( "  perror(\"backtrace_symbols\");" );
 230     output.println( "}" );
 231     output.println( "for (j = 0; j < nptrs; j++) {" );
 232     output.println( "  printf(\"%s\\n\", strings[j]);" );
 233     output.println( "}" );
 234     output.println( "}" );
 235   }
 236
 237
 238
 239
 240   protected void
 241     genAssertRuntimePtrVsHeapResults( PrintWriter    output,
 242                                       FlatMethod     context,
 243                                       TempDescriptor x,
 244                                       Set<Alloc>     targetsByAnalysis ) {
 245
 246     assert targetsByAnalysis != null;
 247
 248     output.println( "" );
 249     output.println( "// checks vs. heap results (DEBUG) for "+x );
 250
 251
 252     if( targetsByAnalysis == HeapAnalysis.DONTCARE_PTR ) {
 253       output.println( "// ANALYSIS DIDN'T CARE WHAT "+x+" POINTS-TO" );
 254       return;
 255     }
 256
 257     String ptr = buildCode.generateTemp( context, x );
 258
 259     String condition;
 260
 261     if( targetsByAnalysis.isEmpty() ) {
 262       condition = ptr+" != NULL";
 263
 264     } else {
 265       condition = ptr+" != NULL &&";
 266
 267       Iterator<Alloc> aItr = targetsByAnalysis.iterator();
 268       while( aItr.hasNext() ) {
 269         Alloc a = aItr.next();
 270         condition += ptr+"->allocsite != "+a.getUniqueAllocSiteID();
 271
 272         if( aItr.hasNext() ) {
 273           condition += " &&";
 274         }
 275       }
 276     }
 277
 278     output.println( "if( "+condition+" ) {" );
 279     printConditionFailed( output, condition, ptr );
 280     output.println( "}\n" );
 281   }
 282
 283
 284
 285   protected void
 286     genAssertRuntimePtrVsHeapResults( PrintWriter                    output,
 287                                       FlatMethod                     context,
 288                                       TempDescriptor                 x,
 289                                       FieldDescriptor                f, // this null OR
 290                                       TempDescriptor                 i, // this null
 291                                       Hashtable< Alloc, Set<Alloc> > targetsByAnalysis ) {
 292     // I assume when you invoke this method you already
 293     // invoked a check on just what x points to, don't duplicate
 294     // AND assume the check to x passed
 295
 296     assert targetsByAnalysis != null;
 297
 298     assert f == null || i == null;
 299
 300     if( f != null ) {
 301       output.println( "// checks vs. heap results (DEBUG) for "+x+"."+f );
 302     } else {
 303       output.println( "// checks vs. heap results (DEBUG) for "+x+"["+i+"]" );
 304     }
 305
 306
 307     if( targetsByAnalysis == HeapAnalysis.DONTCARE_DREF ) {
 308       output.println( "// ANALYSIS DIDN'T CARE WHAT "+x+" POINTS-TO" );
 309       return;
 310     }
 311
 312
 313     if( targetsByAnalysis.isEmpty() ) {
 314       output.println( "// Should have already checked "+x+" is NULL" );
 315
 316     } else {
 317       output.println( "{" );
 318
 319       // if the ptr is null, that's ok, if not check allocsite
 320       output.println( "if( "+
 321                       buildCode.generateTemp( context, x )+
 322                       " != NULL ) {" );
 323
 324       // precompute the allocsite, if any, of the object we will
 325       // get from hopping through the first ptr
 326       output.println( "int allocsiteOneHop = -1;" );
 327       output.println( buildCode.strObjType+"* objOneHop;" );
 328
 329       if( f != null ) {
 330         output.println( "objOneHop = ("+buildCode.strObjType+"*) "+
 331                         buildCode.generateTemp( context, x )+
 332                         "->"+f.getSafeSymbol()+";");
 333       } else {
 334         output.println( "objOneHop = ("+buildCode.strObjType+"*) "+
 335                         "((struct "+x.getType().dereference().getSafeSymbol()+"**)"+
 336                         "(((void*) &("+buildCode.generateTemp( context, x )+"->___length___))+sizeof(int)))"+
 337                         "["+buildCode.generateTemp( context, i )+"];" );
 338       }
 339
 340       output.println( "if( objOneHop != NULL ) { allocsiteOneHop = objOneHop->allocsite; }" );
 341
 342       output.println( "switch( "+
 343                       buildCode.generateTemp( context, x )+
 344                       "->allocsite ) {" );
 345
 346       Iterator<Alloc> kItr = targetsByAnalysis.keySet().iterator();
 347       while( kItr.hasNext() ) {
 348         Alloc k = kItr.next();
 349
 350         output.print( "case "+
 351                       k.getUniqueAllocSiteID()+
 352                       ":" );
 353
 354         Set<Alloc> hopTargets = targetsByAnalysis.get( k );
 355         if( hopTargets == HeapAnalysis.DONTCARE_PTR ) {
 356           output.print( "/* ANALYSIS DOESN'T CARE */" );
 357
 358         } else {
 359           String condition = "allocsiteOneHop != -1";
 360
 361           if( !hopTargets.isEmpty() ) {
 362             condition += " && ";
 363           }
 364
 365           Iterator<Alloc> aItr = hopTargets.iterator();
 366           while( aItr.hasNext() ) {
 367             Alloc a = aItr.next();
 368
 369             condition +=
 370               "allocsiteOneHop != "+
 371               a.getUniqueAllocSiteID();
 372
 373             if( aItr.hasNext() ) {
 374               condition += " && ";
 375             }
 376           }
 377
 378           output.println( "if( "+condition+" ) {" );
 379           printConditionFailed( output, condition, "objOneHop" );
 380           output.println( "}" );
 381         }
 382
 383         output.println( "break;" );
 384       }
 385
 386       output.println( "default:" );
 387       output.println( "// the previous condition for "+x+
 388                       " should already report this failure point" );
 389       output.println( "break;" );
 390       output.println( "}" );
 391       output.println( "}" );
 392       output.println( "}\n" );
 393     }
 394   }
 395
 396
 397
 398
 399   public void printExtraArrayFields(PrintWriter outclassdefs) {}
 400   public void outputTransCode(PrintWriter output) {}
 401   public void buildCodeSetup() {}
 402   public void generateSizeArrayExtensions(PrintWriter outclassdefs) {}
 403   public void preCodeGenInitialization() {}
 404   public void postCodeGenCleanUp() {}
 405   public void additionalClassObjectFields(PrintWriter outclassdefs) {}
 406   public void additionalCodeGen(PrintWriter outmethodheader,
 407                                    PrintWriter outstructs,
 408                                    PrintWriter outmethod) {}
 409   public void additionalCodeAtTopOfMain(PrintWriter outmethod) {}
 410   public void additionalCodeForCommandLineArgs(PrintWriter outmethod, String argsVar) {}
 411   public void additionalCodeAtBottomOfMain(PrintWriter outmethod) {}
 412   public void additionalIncludesMethodsImplementation(PrintWriter outmethod) {}
 413   public void additionalIncludesStructsHeader(PrintWriter outstructs) {}
 414   public void additionalCodeAtTopMethodsImplementation(PrintWriter outmethod) {}
 415   public void additionalCodeNewObject(PrintWriter outmethod, String dstVar, FlatNew flatNew) {}
 416   public void additionalCodeNewStringLiteral(PrintWriter output, String dstVar) {}
 417 }