3 import Analysis.Disjoint.HeapAnalysis;
4 import Analysis.Disjoint.Alloc;
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!
17 public class BCXPointsToCheckVRuntime implements BuildCodeExtension {
19 protected State state;
20 protected BuildCode buildCode;
21 protected TypeUtil typeUtil;
22 protected HeapAnalysis heapAnalysis;
24 protected ClassDescriptor cdObject;
26 protected TypeDescriptor stringType;
28 private boolean DEBUG = false;
32 public BCXPointsToCheckVRuntime( State state,
35 HeapAnalysis heapAnalysis ) {
37 this.buildCode = buildCode;
38 this.typeUtil = typeUtil;
39 this.heapAnalysis = heapAnalysis;
41 ClassDescriptor cdString = typeUtil.getClass( typeUtil.StringClass );
42 assert cdString != null;
43 stringType = new TypeDescriptor( cdString );
47 public void additionalIncludesMethodsHeader(PrintWriter outmethodheader) {
48 outmethodheader.println( "#include<stdio.h>" );
49 outmethodheader.println( "#include<execinfo.h>" );
53 public void additionalCodeAtTopFlatMethodBody(PrintWriter output, FlatMethod fm) {
55 for( int i = 0; i < fm.numParameters(); ++i ) {
56 TempDescriptor td = fm.getParameter( i );
57 TypeDescriptor type = td.getType();
59 output.println( "// Generating points-to checks for method params" );
61 genAssertRuntimePtrVsHeapResults( output,
64 heapAnalysis.canPointToAfter( td, fm )
67 output.println( "// end method params" );
70 System.out.println( "\nGenerating code for "+fm );
71 System.out.println( " arg "+td+" can point to "+heapAnalysis.canPointToAfter( td, fm ) );
78 public void additionalCodePreNode(FlatMethod fm, FlatNode fn, PrintWriter output) {
89 // for PRE-NODE checks, only look at pointers we are reading from because
90 // pointers about to be set may be undefined and don't pass runtime checks nicely
96 case FKind.FlatLiteralNode: {
97 FlatLiteralNode fln = (FlatLiteralNode) fn;
99 if( fln.getType().equals( stringType ) ) {
102 output.println( "// Generating points-to checks for pre-node string literal" );
104 genAssertRuntimePtrVsHeapResults( output,
107 heapAnalysis.canPointToAt( lhs, fn )
110 output.println( "// end pre-node string literal" );
114 System.out.println( " before "+fn );
115 System.out.println( " "+lhs+" can point to "+heapAnalysis.canPointToAt( lhs, fn ) );
121 case FKind.FlatOpNode: {
122 FlatOpNode fon = (FlatOpNode) fn;
123 if( fon.getOp().getOp() == Operation.ASSIGN ) {
127 type = lhs.getType();
130 output.println( "// Generating points-to checks for pre-node op assign" );
133 //genAssertRuntimePtrVsHeapResults( output,
136 // heapAnalysis.canPointToAt( lhs, fn )
139 genAssertRuntimePtrVsHeapResults( output,
142 heapAnalysis.canPointToAt( rhs, fn )
145 output.println( "// end pre-node op assign" );
149 System.out.println( " before "+fn );
150 //System.out.println( " "+lhs+" can point to "+heapAnalysis.canPointToAt( lhs, fn ) );
151 System.out.println( " "+rhs+" can point to "+heapAnalysis.canPointToAt( rhs, fn ) );
158 case FKind.FlatCastNode: {
159 FlatCastNode fcn = (FlatCastNode) fn;
163 type = fcn.getType();
166 output.println( "// Generating points-to checks for pre-node cast" );
168 //genAssertRuntimePtrVsHeapResults( output,
171 // heapAnalysis.canPointToAt( lhs, fn )
174 genAssertRuntimePtrVsHeapResults( output,
177 heapAnalysis.canPointToAt( rhs, fn )
180 output.println( "// end pre-node cast" );
184 System.out.println( " before "+fn );
185 //System.out.println( " "+lhs+" can point to "+heapAnalysis.canPointToAt( lhs, fn ) );
186 System.out.println( " "+rhs+" can point to "+heapAnalysis.canPointToAt( rhs, fn ) );
192 case FKind.FlatFieldNode: {
193 FlatFieldNode ffn = (FlatFieldNode) fn;
196 fld = ffn.getField();
198 type = lhs.getType();
201 output.println( "// Generating points-to checks for pre-node field" );
203 //genAssertRuntimePtrVsHeapResults( output,
206 // heapAnalysis.canPointToAt( lhs, fn )
209 genAssertRuntimePtrVsHeapResults( output,
212 heapAnalysis.canPointToAt( rhs, fn )
215 genAssertRuntimePtrVsHeapResults( output,
220 heapAnalysis.canPointToAt( rhs, fld, fn )
223 output.println( "// end pre-node field" );
227 System.out.println( " before "+fn );
228 //System.out.println( " "+lhs+" can point to "+heapAnalysis.canPointToAt( lhs, fn ) );
229 System.out.println( " "+rhs+" can point to "+heapAnalysis.canPointToAt( rhs, fn ) );
230 System.out.println( " "+rhs+"."+fld+" can point to "+heapAnalysis.canPointToAt( rhs, fld, fn ) );
236 case FKind.FlatElementNode: {
237 FlatElementNode fen = (FlatElementNode) fn;
240 idx = fen.getIndex();
242 type = lhs.getType();
245 output.println( "// Generating points-to checks for pre-node element" );
247 //genAssertRuntimePtrVsHeapResults( output,
250 // heapAnalysis.canPointToAt( lhs, fn )
253 genAssertRuntimePtrVsHeapResults( output,
256 heapAnalysis.canPointToAt( rhs, fn )
259 genAssertRuntimePtrVsHeapResults( output,
264 heapAnalysis.canPointToAtElement( rhs, fn )
267 output.println( "// end pre-node element" );
271 System.out.println( " before "+fn );
272 //System.out.println( " "+lhs+" can point to "+heapAnalysis.canPointToAt( lhs, fn ) );
273 System.out.println( " "+rhs+" can point to "+heapAnalysis.canPointToAt( rhs, fn ) );
274 System.out.println( " "+rhs+"["+idx+"] can point to "+heapAnalysis.canPointToAtElement( rhs, fn ) );
280 case FKind.FlatCall: {
281 FlatCall fc = (FlatCall) fn;
282 //ret = fc.getReturnTemp();
284 FlatMethod fmCallee = state.getMethodFlat( fc.getMethod() );
286 boolean somethingChecked = false;
288 output.println( "// Generating points-to checks for pre-node call" );
290 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
291 arg = fc.getArgMatchingParamIndex( fmCallee, i );
292 type = arg.getType();
294 genAssertRuntimePtrVsHeapResults( output,
297 heapAnalysis.canPointToAt( arg, fn )
299 somethingChecked = true;
303 //if( ret != null ) {
304 // type = ret.getType();
305 // if( type.isPtr() ) {
306 // genAssertRuntimePtrVsHeapResults( output,
309 // heapAnalysis.canPointToAt( ret, fn )
311 // somethingChecked = true;
315 output.println( "// end pre-node call" );
317 if( DEBUG && somethingChecked ) {
319 System.out.println( " before "+fn+":" );
321 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
322 arg = fc.getArgMatchingParamIndex( fmCallee, i );
323 type = arg.getType();
325 System.out.println( " arg "+arg+" can point to "+heapAnalysis.canPointToAt( arg, fn ) );
329 //if( ret != null ) {
330 // type = ret.getType();
331 // if( type.isPtr() ) {
332 // System.out.println( " return temp "+ret+" can point to "+heapAnalysis.canPointToAt( ret, fn ) );
343 public void additionalCodePostNode(FlatMethod fm,
345 PrintWriter output) {
357 switch( fn.kind() ) {
360 case FKind.FlatLiteralNode: {
361 FlatLiteralNode fln = (FlatLiteralNode) fn;
363 if( fln.getType().equals( stringType ) ) {
366 output.println( "// Generating points-to checks for post-node string literal" );
368 genAssertRuntimePtrVsHeapResults( output,
371 heapAnalysis.canPointToAfter( lhs, fn )
374 output.println( "// end post-node string literal" );
378 System.out.println( " after "+fn );
379 System.out.println( " "+lhs+" can point to "+heapAnalysis.canPointToAfter( lhs, fn ) );
385 case FKind.FlatOpNode: {
386 FlatOpNode fon = (FlatOpNode) fn;
387 if( fon.getOp().getOp() == Operation.ASSIGN ) {
390 type = lhs.getType();
393 output.println( "// Generating points-to checks for post-node op assign" );
395 genAssertRuntimePtrVsHeapResults( output,
398 heapAnalysis.canPointToAfter( lhs, fn )
401 output.println( "// end post-node op assign" );
405 System.out.println( " after "+fn );
406 System.out.println( " "+lhs+" can point to "+heapAnalysis.canPointToAfter( lhs, fn ) );
413 case FKind.FlatCastNode: {
414 FlatCastNode fcn = (FlatCastNode) fn;
417 type = fcn.getType();
420 output.println( "// Generating points-to checks for post-node cast" );
422 genAssertRuntimePtrVsHeapResults( output,
425 heapAnalysis.canPointToAfter( lhs, fn )
428 output.println( "// end post-node cast" );
432 System.out.println( " after "+fn );
433 System.out.println( " "+lhs+" can point to "+heapAnalysis.canPointToAfter( lhs, fn ) );
439 case FKind.FlatFieldNode: {
440 FlatFieldNode ffn = (FlatFieldNode) fn;
443 type = lhs.getType();
446 output.println( "// Generating points-to checks for post-node field" );
448 genAssertRuntimePtrVsHeapResults( output,
451 heapAnalysis.canPointToAfter( lhs, fn )
454 output.println( "// end post-node field" );
458 System.out.println( " after "+fn );
459 System.out.println( " "+lhs+" can point to "+heapAnalysis.canPointToAfter( lhs, fn ) );
465 case FKind.FlatElementNode: {
466 FlatElementNode fen = (FlatElementNode) fn;
469 type = lhs.getType();
472 output.println( "// Generating points-to checks for post-node element" );
474 genAssertRuntimePtrVsHeapResults( output,
477 heapAnalysis.canPointToAfter( lhs, fn )
480 output.println( "// end post-node element" );
484 System.out.println( " after "+fn );
485 System.out.println( " "+lhs+" can point to "+heapAnalysis.canPointToAfter( lhs, fn ) );
491 case FKind.FlatCall: {
492 FlatCall fc = (FlatCall) fn;
493 ret = fc.getReturnTemp();
495 FlatMethod fmCallee = state.getMethodFlat( fc.getMethod() );
497 boolean somethingChecked = false;
499 output.println( "// Generating points-to checks for post-node call" );
501 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
502 arg = fc.getArgMatchingParamIndex( fmCallee, i );
503 type = arg.getType();
505 genAssertRuntimePtrVsHeapResults( output,
508 heapAnalysis.canPointToAfter( arg, fn )
510 somethingChecked = true;
515 type = ret.getType();
517 genAssertRuntimePtrVsHeapResults( output,
520 heapAnalysis.canPointToAfter( ret, fn )
522 somethingChecked = true;
526 output.println( "// end post-node call" );
528 if( DEBUG && somethingChecked ) {
530 System.out.println( " after "+fn+":" );
532 for( int i = 0; i < fmCallee.numParameters(); ++i ) {
533 arg = fc.getArgMatchingParamIndex( fmCallee, i );
534 type = arg.getType();
536 System.out.println( " arg "+arg+" can point to "+heapAnalysis.canPointToAfter( arg, fn ) );
541 type = ret.getType();
543 System.out.println( " return temp "+ret+" can point to "+heapAnalysis.canPointToAfter( ret, fn ) );
555 printConditionFailed( PrintWriter output,
559 // don't do this in the constructor of this extension object because
560 // build code hasn't created any types or classes yet!
561 if( cdObject == null ) {
562 cdObject = typeUtil.getClass( typeUtil.ObjectClass );
563 assert cdObject != null;
566 output.println( "printf(\"[[[ CHECK VS HEAP RESULTS FAILED ]]] Condition for failure( "+
567 condition+" ) allocsite=%d at %s:%d\\n\", ((struct "+
568 cdObject.getSafeSymbol()+"*)"+
569 pointer+")->allocsite, __FILE__, __LINE__ );" );
571 // spit out the stack trace (so fancy!)
572 output.println( "{" );
573 output.println( "void* buffer[100];" );
574 output.println( "char** strings;" );
575 output.println( "int nptrs,j;" );
576 output.println( "nptrs = backtrace(buffer, 100);" );
577 output.println( "strings = backtrace_symbols(buffer, nptrs);" );
578 output.println( "if (strings == NULL) {" );
579 output.println( " perror(\"backtrace_symbols\");" );
580 output.println( "}" );
581 output.println( "for (j = 0; j < nptrs; j++) {" );
582 output.println( " printf(\"%s\\n\", strings[j]);" );
583 output.println( "}" );
584 output.println( "}" );
591 genAssertRuntimePtrVsHeapResults( PrintWriter output,
594 Set<Alloc> targetsByAnalysis ) {
596 assert targetsByAnalysis != null;
598 output.println( "" );
599 output.println( "// checks vs. heap results (DEBUG) for "+x );
602 if( targetsByAnalysis == HeapAnalysis.DONTCARE_PTR ) {
603 output.println( "// ANALYSIS DIDN'T CARE WHAT "+x+" POINTS-TO" );
607 String ptr = buildCode.generateTemp( context, x );
611 if( targetsByAnalysis.isEmpty() ) {
612 condition = ptr+" != NULL";
615 condition = ptr+" != NULL &&";
617 Iterator<Alloc> aItr = targetsByAnalysis.iterator();
618 while( aItr.hasNext() ) {
619 Alloc a = aItr.next();
620 condition += ptr+"->allocsite != "+a.getUniqueAllocSiteID();
622 if( aItr.hasNext() ) {
628 output.println( "if( "+condition+" ) {" );
629 printConditionFailed( output, condition, ptr );
630 output.println( "}\n" );
636 genAssertRuntimePtrVsHeapResults( PrintWriter output,
639 FieldDescriptor f, // this null OR
640 TempDescriptor i, // this null
641 Hashtable< Alloc, Set<Alloc> > targetsByAnalysis ) {
642 // I assume when you invoke this method you already
643 // invoked a check on just what x points to, don't duplicate
644 // AND assume the check to x passed
646 assert targetsByAnalysis != null;
648 assert f == null || i == null;
651 output.println( "// checks vs. heap results (DEBUG) for "+x+"."+f );
653 output.println( "// checks vs. heap results (DEBUG) for "+x+"["+i+"]" );
657 if( targetsByAnalysis == HeapAnalysis.DONTCARE_DREF ) {
658 output.println( "// ANALYSIS DIDN'T CARE WHAT "+x+" POINTS-TO" );
663 if( targetsByAnalysis.isEmpty() ) {
664 output.println( "// Should have already checked "+x+" is NULL" );
667 output.println( "{" );
669 // if the ptr is null, that's ok, if not check allocsite
670 output.println( "if( "+
671 buildCode.generateTemp( context, x )+
674 // precompute the allocsite, if any, of the object we will
675 // get from hopping through the first ptr
676 output.println( "int allocsiteOneHop = -1;" );
677 output.println( buildCode.strObjType+"* objOneHop;" );
682 // jjenista - DON'T DEAL WITH THIS RIGHT NOW
683 //ClassDescriptor cdX = ;
684 //output.println( "objOneHop = ("+buildCode.strObjType+"*) "+
686 // "->"+f.getSafeSymbol()+";");
687 output.println( "}" );
688 output.println( "}" );
692 output.println( "objOneHop = ("+buildCode.strObjType+"*) "+
693 buildCode.generateTemp( context, x )+
694 "->"+f.getSafeSymbol()+";");
698 output.println( "objOneHop = ("+buildCode.strObjType+"*) "+
699 "((struct "+x.getType().dereference().getSafeSymbol()+"**)"+
700 "(((void*) &("+buildCode.generateTemp( context, x )+"->___length___))+sizeof(int)))"+
701 "["+buildCode.generateTemp( context, i )+"];" );
704 output.println( "if( objOneHop != NULL ) { allocsiteOneHop = objOneHop->allocsite; }" );
706 output.println( "switch( "+
707 buildCode.generateTemp( context, x )+
710 Iterator<Alloc> kItr = targetsByAnalysis.keySet().iterator();
711 while( kItr.hasNext() ) {
712 Alloc k = kItr.next();
714 output.print( "case "+
715 k.getUniqueAllocSiteID()+
718 Set<Alloc> hopTargets = targetsByAnalysis.get( k );
719 if( hopTargets == HeapAnalysis.DONTCARE_PTR ) {
720 output.print( "/* ANALYSIS DOESN'T CARE */" );
723 String condition = "allocsiteOneHop != -1";
725 if( !hopTargets.isEmpty() ) {
729 Iterator<Alloc> aItr = hopTargets.iterator();
730 while( aItr.hasNext() ) {
731 Alloc a = aItr.next();
734 "allocsiteOneHop != "+
735 a.getUniqueAllocSiteID();
737 if( aItr.hasNext() ) {
742 output.println( "if( "+condition+" ) {" );
743 printConditionFailed( output, condition, "objOneHop" );
744 output.println( "}" );
747 output.println( "break;" );
750 output.println( "default:" );
751 output.println( "// the previous condition for "+x+
752 " should already report this failure point" );
753 output.println( "break;" );
754 output.println( "}" );
755 output.println( "}" );
756 output.println( "}\n" );
763 public void printExtraArrayFields(PrintWriter outclassdefs) {}
764 public void outputTransCode(PrintWriter output) {}
765 public void buildCodeSetup() {}
766 public void generateSizeArrayExtensions(PrintWriter outclassdefs) {}
767 public void preCodeGenInitialization() {}
768 public void postCodeGenCleanUp() {}
769 public void additionalClassObjectFields(PrintWriter outclassdefs) {}
770 public void additionalCodeGen(PrintWriter outmethodheader,
771 PrintWriter outstructs,
772 PrintWriter outmethod) {}
773 public void additionalCodeAtTopOfMain(PrintWriter outmethod) {}
774 public void additionalCodeForCommandLineArgs(PrintWriter outmethod, String argsVar) {}
775 public void additionalCodeAtBottomOfMain(PrintWriter outmethod) {}
776 public void additionalIncludesMethodsImplementation(PrintWriter outmethod) {}
777 public void additionalIncludesStructsHeader(PrintWriter outstructs) {}
778 public void additionalCodeAtTopMethodsImplementation(PrintWriter outmethod) {}
779 public void additionalCodeNewObject(PrintWriter outmethod, String dstVar, FlatNew flatNew) {}
780 public void additionalCodeNewStringLiteral(PrintWriter output, String dstVar) {}