Robust/src/IR/Flat/RuntimeConflictResolver.java

   1 package IR.Flat;
   2
   3 import java.io.File;
   4 import java.io.FileNotFoundException;
   5 import java.io.PrintWriter;
   6 import java.util.ArrayList;
   7 import java.util.HashSet;
   8 import java.util.Hashtable;
   9 import java.util.Iterator;
  10 import java.util.Set;
  11 import Analysis.Disjoint.*;
  12 import IR.TypeDescriptor;
  13
  14 //TODO fix inaccuracy problem and take advantage of the refEdges
  15 //TODO make it so that methods with no conflicts get no output.
  16 //TODO Make more efficient by only using ONE hashtable.
  17
  18 /* An instance of this class manages all OoOJava coarse-grained runtime conflicts
  19  * by generating C-code to either rule out the conflict at runtime or resolve one.
  20  *
  21  * How to Use:
  22  * 1) Instantiate singleton object
  23  * 2) Call void traverse(FlatSESEEnterNode rblock, Hashtable<Taint, Set<Effect>> effects, Hashtable<Taint, Set<Effect>> conflicts, ReachGraph rg)
  24  *    as many times as needed
  25  * 3) Call void close()
  26  */
  27 public class RuntimeConflictResolver {
  28   public static String outputFile;
  29   private PrintWriter cFile;
  30   private PrintWriter headerFile;
  31   private static final String hashAndQueueCFileDir = "oooJava/";
  32
  33   // initializing variables can be found in printHeader()
  34   private static final String getAllocSiteInC = "->allocsite";
  35   private static final String queryAndAddHashTableInC = "hashRCRInsert(";
  36   private static final String addToQueueInC = "enqueueRCRQueue(";
  37   private static final String dequeueFromQueueInC = "dequeueRCRQueue()";
  38
  39   private static final String clearQueue = "resetRCRQueue()";
  40   // Make hashtable; hashRCRCreate(unsigned int size, double loadfactor)
  41   private static final String mallocHashTable = "hashRCRCreate(1024, 0.25)";
  42   private static final String deallocHashTable = "hashRCRDelete()";
  43   private static final String resetHashTable = "hashRCRreset()";
  44
  45   public RuntimeConflictResolver(String buildir) throws FileNotFoundException {
  46     outputFile = buildir + "RuntimeConflictResolver";
  47
  48     cFile = new PrintWriter(new File(outputFile + ".c"));
  49     headerFile = new PrintWriter(new File(outputFile + ".h"));
  50
  51     cFile.append("#include \"" + hashAndQueueCFileDir + "hashRCR.h\"\n#include \""
  52         + hashAndQueueCFileDir + "Queue_RCR.h\"\n#include <stdlib.h>\n");
  53     cFile.append("#include \"classdefs.h\"\n");
  54     cFile.append("#include \"RuntimeConflictResolver.h\"\n");
  55
  56     headerFile.append("#ifndef __3_RCR_H_\n");
  57     headerFile.append("#define __3_RCR_H_\n");
  58     //TODO more closely integrate this by asking generic type from other components?
  59     //generic cast struct
  60     cFile.append("struct genericObjectStruct {int type; int oid; int allocsite; int ___cachedCode___; int ___cachedHash___;};\n");
  61   }
  62
  63   /*
  64    * Basic steps:
  65    * 1) Create pruned data structures from givens
  66    *     1a) Use effects sets to verify if we can access something (reads)
  67    *     1b) Mark conflicts with 2 flags (one for self, one for references down the line)
  68    * 2) build code output structure
  69    * 3) printout
  70    */
  71   public void traverse(FlatSESEEnterNode rblock,
  72       Hashtable<Taint, Set<Effect>> effects,
  73       Hashtable<Taint, Set<Effect>> conflicts,
  74       ReachGraph rg) {
  75
  76     Set<TempDescriptor> inVars = rblock.getInVarSet();
  77
  78     if (inVars.size() == 0)
  79       return;
  80
  81     // For every non-primative variable, generate unique method
  82     // Special Note: The Criteria for executing printCMethod in this loop should match
  83     // exactly the criteria in buildcode.java to invoke the generated C method(s).
  84     for (TempDescriptor invar : inVars) {
  85       TypeDescriptor type = invar.getType();
  86       if(type == null || type.isPrimitive()) {
  87         continue;
  88       }
  89
  90       Hashtable<AllocSite, ConcreteRuntimeObjNode> created = new Hashtable<AllocSite, ConcreteRuntimeObjNode>();
  91
  92       createTree(rblock, invar, effects, conflicts, rg, created);
  93       if (!created.isEmpty()) {
  94         rblock.addInVarForDynamicCoarseConflictResolution(invar);
  95         printCMethod(created, invar.getSafeSymbol(), rblock.getPrettyIdentifier());
  96       }
  97     }
  98   }
  99
 100   public void close() {
 101     // Adds Extra supporting methods
 102     cFile.append("void initializeStructsRCR() { " + mallocHashTable + "; " + clearQueue + "; }");
 103     cFile.append("void destroyRCR() { " + deallocHashTable + "; }\n");
 104
 105     headerFile.append("void initializeStructsRCR(); \nvoid destroyRCR(); \n");
 106     headerFile.append("#endif\n");
 107
 108     cFile.close();
 109     headerFile.close();
 110   }
 111
 112   private void createTree(FlatSESEEnterNode rblock,
 113       TempDescriptor invar,
 114       Hashtable<Taint, Set<Effect>> effects,
 115       Hashtable<Taint, Set<Effect>> conflicts,
 116       ReachGraph rg,
 117       Hashtable<AllocSite, ConcreteRuntimeObjNode> created) {
 118
 119     VariableNode varNode = rg.getVariableNodeNoMutation(invar);
 120     Hashtable<AllocSite, EffectsGroup> table =
 121         generateEffectsLookupTable(rblock, varNode, effects, conflicts);
 122
 123     // if table is null that means there's no conflicts, therefore we need not
 124     // create a traversal
 125     if (table == null)
 126       return;
 127
 128     Iterator<RefEdge> possibleEdges = varNode.iteratorToReferencees();
 129
 130     while (possibleEdges.hasNext()) {
 131       RefEdge edge = possibleEdges.next();
 132       assert edge != null;
 133
 134       ConcreteRuntimeObjNode singleRoot = new ConcreteRuntimeObjNode(edge.getDst(), false, true);
 135       AllocSite rootKey = singleRoot.allocSite;
 136
 137       if (!created.containsKey(rootKey)) {
 138         created.put(rootKey, singleRoot);
 139         createHelper(singleRoot, edge.getDst().iteratorToReferencees(), created, table);
 140       }
 141     }
 142   }
 143
 144   private Hashtable<AllocSite, EffectsGroup> generateEffectsLookupTable(FlatSESEEnterNode rblock,
 145         VariableNode var, Hashtable<Taint, Set<Effect>> effects,
 146         Hashtable<Taint, Set<Effect>> conflicts) {
 147       // we search effects since conflicts is only a subset of effects
 148       Taint taint = getProperTaint(rblock, var, effects);
 149       assert taint != null;
 150
 151       Set<Effect> localEffects = effects.get(taint);
 152       Set<Effect> localConflicts = conflicts.get(taint);
 153
 154       if (localEffects == null || localEffects.isEmpty() || localConflicts == null || localConflicts.isEmpty())
 155         return null;
 156
 157   //    Debug Code for manually checking effects
 158   //    System.out.println("For Taint " + taint);
 159   //    System.out.println("Effects");
 160   //    for(Effect e: localEffects)
 161   //    {
 162   //     System.out.println(e);
 163   //    }
 164   //
 165   //    System.out.println("Conflicts");
 166   //    for(Effect e: localConflicts)
 167   //    {
 168   //      System.out.println(e);
 169   //    }
 170
 171       Hashtable<AllocSite, EffectsGroup> lookupTable = new Hashtable<AllocSite, EffectsGroup>();
 172
 173       for (Effect e : localEffects) {
 174         boolean conflict = localConflicts.contains(e);
 175         AllocSite key = e.getAffectedAllocSite();
 176         EffectsGroup myEffects = lookupTable.get(key);
 177
 178         if(myEffects == null) {
 179           myEffects = new EffectsGroup();
 180           lookupTable.put(key, myEffects);
 181         }
 182
 183         if(e.getField().getType().isPrimitive()) {
 184           if(conflict) {
 185             myEffects.addPrimative(e);
 186           }
 187         }
 188         else {
 189           myEffects.addObj(e, conflict);
 190         }
 191       }
 192
 193       return lookupTable;
 194     }
 195
 196   // Plan is to add stuff to the tree depth-first sort of way. That way, we can
 197   // propagate up conflicts
 198   private void createHelper(ConcreteRuntimeObjNode curr, Iterator<RefEdge> edges, Hashtable<AllocSite, ConcreteRuntimeObjNode> created,
 199       Hashtable<AllocSite, EffectsGroup> table) {
 200     assert table != null;
 201
 202     AllocSite parentKey = curr.allocSite;
 203     EffectsGroup currEffects = table.get(parentKey);
 204
 205     if (currEffects == null || currEffects.isEmpty())
 206       return;
 207
 208     //Handle Objects
 209     if(currEffects.hasObjectConflicts()) {
 210       while(edges.hasNext()) {
 211         RefEdge edge = edges.next();
 212         String field = edge.getField();
 213         EffectPair effect = currEffects.getObjEffect(field); // TODO are you certain there is only one effect to get here?
 214         //If there is no effect, then there's not point in traversing this edge
 215         if(effect != null)
 216         {
 217           HeapRegionNode childHRN = edge.getDst();
 218           AllocSite childKey = childHRN.getAllocSite();
 219           boolean isNewChild = !created.containsKey(childKey);
 220           ConcreteRuntimeObjNode child;
 221
 222           if(isNewChild) {
 223             child = new ConcreteRuntimeObjNode(childHRN, effect.conflict, false);
 224             created.put(childKey, child);
 225           }
 226           else {
 227             child = created.get(childKey);
 228           }
 229
 230           curr.addObjChild(field, child, effect.conflict);
 231
 232           if (effect.conflict) {
 233             propogateObjConflictFlag(child);
 234           }
 235
 236           if (effect.type == Effect.read && isNewChild) {
 237             createHelper(child, childHRN.iteratorToReferencees(), created, table);
 238           }
 239         }
 240       }
 241     }
 242
 243     //Handle primitives
 244     if(currEffects.hasPrimativeConflicts()) {
 245       curr.primativeFields = currEffects.primativeConflictingFields;
 246       propogatePrimConflictFlag(curr);
 247     }
 248   }
 249
 250   // This will propagate the conflict up the data structure.
 251   private void propogateObjConflictFlag(ConcreteRuntimeObjNode in) {
 252     ConcreteRuntimeObjNode node = in;
 253
 254     while(node.lastReferencer != null) {
 255       node.lastReferencer.decendantsObjConflict = true;
 256       if(!node.conflictingParents.add(node.lastReferencer))
 257         break;
 258       node = node.lastReferencer;
 259     }
 260   }
 261
 262   private void propogatePrimConflictFlag(ConcreteRuntimeObjNode in) {
 263     ConcreteRuntimeObjNode node = in;
 264
 265     while(node.lastReferencer != null) {
 266       node.lastReferencer.decendantsPrimConflict = true;
 267       if(!node.conflictingParents.add(node.lastReferencer))
 268         break;
 269       node = node.lastReferencer;
 270     }
 271   }
 272
 273   /*
 274    * This method generates a C method for every inset variable and rblock.
 275    *
 276    * The C method works by generating a large switch statement that will run the appropriate
 277    * checking code for each object based on its allocation site. The switch statement is
 278    * surrounded by a while statement which dequeues objects to be checked from a queue. An
 279    * object is added to a queue only if it contains a conflict (in itself or in its referencees)
 280    *  and we came across it while checking through it's referencer. Because of this property,
 281    *  conflicts will be signaled by the referencer; the only exception is the inset variable which can
 282    *  signal a conflict within itself.
 283    */
 284   //TODO make empty switch statments just have a return.
 285   //TODO make check for only 1 case statement (String Builder?)
 286   //TODO where are all these "temp" variables coming from?
 287   private void printCMethod(Hashtable<AllocSite, ConcreteRuntimeObjNode> created, String inVar, String rBlock) {
 288     HashSet<AllocSite> done = new HashSet<AllocSite>();
 289     // note that primitive in-set variables do not generate effects, so we can assume
 290     // that inVar is an object
 291
 292     //Note: remember to change getTraverserInvocation if you change the line below
 293     String methodName = "void traverse___" + inVar.replaceAll(" ", "") + rBlock.replaceAll(" ", "") +
 294     "___(void * InVar)";
 295
 296     cFile.append(methodName + " {\n");
 297     headerFile.append(methodName + ";\n");
 298
 299     cFile.append("printf(\"The traverser ran for " + methodName + "\\n\");\n");
 300
 301     //Casts the ptr to a genericObjectSTruct so we can get to the ptr->allocsite field.
 302     cFile.append("struct genericObjectStruct * ptr = (struct genericObjectStruct *) InVar;  if(InVar != NULL) { " + queryAndAddHashTableInC
 303         + "ptr); do { ");
 304
 305     //This part of the code generates the switch statement from all objects in hash.
 306     cFile.append("switch(ptr->allocsite) { ");
 307     for (ConcreteRuntimeObjNode node : created.values()) {
 308       // If we haven't seen it and it's a node with more than 1 parent
 309       // Note: a node with 0 parents is a root node (i.e. inset variable)
 310       if (!done.contains(node.allocSite) && (node.getNumOfReachableParents() != 1 || node.isInsetVar)
 311           && node.decendantsConflict()) {
 312         addChecker(node, done, "ptr", 0);
 313       }
 314     }
 315     cFile.append(" default : break; ");
 316     cFile.append("}} while( (ptr = " + dequeueFromQueueInC + ") != NULL); ");
 317
 318     //Closes the method by clearing the Queue and reseting the hashTable to prevent
 319     //overhead from freeing and mallocing the structures.
 320     cFile.append(clearQueue + "; " + resetHashTable + "; }}\n");
 321
 322     cFile.flush();
 323   }
 324
 325   public String getTraverserInvocation(TempDescriptor invar, String varString, FlatSESEEnterNode sese) {
 326     return "traverse___" + invar.getSafeSymbol().replaceAll(" ", "") +
 327     sese.getPrettyIdentifier().replaceAll(" ", "") + "___("+varString+");";
 328   }
 329
 330   /*
 331    * addChecker creates a case statement for every object that is either an inset variable
 332    * or has multiple referencers (incoming edges). Else it just prints the checker for that object
 333    * so that its processing can be pushed up to the referencer node.
 334    */
 335   private void addChecker(ConcreteRuntimeObjNode node, HashSet<AllocSite> done, String prefix, int depth) {
 336     // We don't need a case statement for things with either 1 incoming or 0 out
 337     // going edges, because they can be processed when checking the parent.
 338     if ((node.getNumOfReachableParents() != 1 || node.isInsetVar)  && node.decendantsConflict()) {
 339       assert prefix.equals("ptr");
 340       cFile.append("case " + node.getAllocationSite() + ":\n { ");
 341     }
 342
 343     //Specific Primitives test for invars
 344     if(node.isInsetVar && node.hasPrimativeConflicts())
 345       handlePrimitiveConflict(prefix, node.primativeFields, node.allocSite);
 346
 347     // TODO orientation
 348     //Casts C pointer; depth is used to create unique "myPtr" name
 349     String currPtr = "myPtr" + depth;
 350     String structType = node.original.getType().getSafeSymbol();
 351     cFile.append("struct " + structType + " * "+currPtr+"= (struct "+ structType + " * ) " + prefix + "; ");
 352
 353     //Handles Objects
 354     for (ObjRef ref : node.objectRefs) {
 355       // Will only process edge if there is some sort of conflict with the Child
 356       if (ref.child.decendantsConflict()|| ref.child.hasConflicts()) {
 357         String childPtr = currPtr +"->___" + ref.field + "___";
 358
 359         // Checks if the child exists and has allocsite matching the conflict
 360         cFile.append("if(" + childPtr + " != NULL && " + childPtr + getAllocSiteInC + "=="
 361             + ref.allocSite + ") { ");
 362
 363         // Prints out conflicts of child
 364         if (ref.conflict)
 365           handleObjConflict(childPtr, node.allocSite);
 366
 367         if(ref.child.hasPrimativeConflicts())
 368           handlePrimitiveConflict(childPtr, ref.child.primativeFields, ref.child.allocSite);
 369
 370         if (ref.child.decendantsConflict()) {
 371           // Checks if we have visited the child before
 372           cFile.append("if(!" + queryAndAddHashTableInC + childPtr + ")) { ");
 373           if (ref.child.getNumOfReachableParents() == 1 && !ref.child.isInsetVar) {
 374             addChecker(ref.child, done, childPtr, depth + 1);
 375           }
 376           else {
 377             cFile.append(addToQueueInC + childPtr + ");");
 378           }
 379
 380           cFile.append(" } ");
 381         }
 382         cFile.append(" } ");
 383       }
 384     }
 385
 386     if ((node.getNumOfReachableParents() != 1 || node.isInsetVar) && node.decendantsConflict())
 387       cFile.println(" } break; ");
 388
 389     done.add(node.allocSite);
 390   }
 391
 392   private void handleObjConflict(String childPtr, AllocSite allocSite) {
 393     cFile.append("printf(\"Conflict detected with %p from parent with allocation site %u\\n\"," + childPtr + "," + allocSite.hashCodeSpecific() + ");");
 394   }
 395
 396   private void handlePrimitiveConflict(String ptr, ArrayList<String> conflicts, AllocSite allocSite) {
 397     cFile.append("printf(\"Primitive Conflict detected with %p with alloc site %u\\n\", "+ptr+", "+allocSite.hashCodeSpecific()+"); ");
 398   }
 399
 400   private Taint getProperTaint(FlatSESEEnterNode rblock, VariableNode var,
 401       Hashtable<Taint, Set<Effect>> effects) {
 402     Set<Taint> taints = effects.keySet();
 403
 404     for (Taint t : taints) {
 405       FlatSESEEnterNode sese = t.getSESE();
 406       //Jim says that this case should never happen, but it may
 407       if( sese == null ) {
 408           System.out.println( "What should I do with a stall site taint? --Jim");
 409       }
 410       if(sese != null && sese.equals(rblock) && t.getVar().equals(var.getTempDescriptor())) {
 411         return t;
 412       }
 413     }
 414     return null;
 415   }
 416
 417   private class EffectsGroup
 418   {
 419     Hashtable<String, EffectPair> myEffects;
 420     ArrayList<String> primativeConflictingFields;
 421
 422     public EffectsGroup() {
 423       myEffects = new Hashtable<String, EffectPair>();
 424       primativeConflictingFields = new ArrayList<String>();
 425     }
 426
 427     public void addPrimative(Effect e) {
 428       primativeConflictingFields.add(e.getField().toPrettyStringBrief());
 429     }
 430
 431     public void addObj(Effect e, boolean conflict) {
 432       EffectPair effect = new EffectPair(e, conflict);
 433       myEffects.put(e.getField().getSymbol(), effect);
 434     }
 435
 436     public boolean isEmpty() {
 437       return myEffects.isEmpty() && primativeConflictingFields.isEmpty();
 438     }
 439
 440     public boolean hasPrimativeConflicts(){
 441       return !primativeConflictingFields.isEmpty();
 442     }
 443
 444     public boolean hasObjectConflicts() {
 445       return !myEffects.isEmpty();
 446     }
 447
 448     public EffectPair getObjEffect(String field) {
 449       return myEffects.get(field);
 450     }
 451   }
 452
 453   private class EffectPair {
 454     Effect originalEffect;
 455     int type;
 456     boolean conflict;
 457
 458     public EffectPair(Effect e, boolean conflict) {
 459       originalEffect = e;
 460       type = e.getType();
 461       this.conflict = conflict;
 462     }
 463
 464     public int hashCode() {
 465       return originalEffect.hashCode();
 466     }
 467
 468     public boolean equals(Object o) {
 469       if (o == null)
 470         return false;
 471
 472       if (!(o instanceof EffectPair))
 473         return false;
 474
 475       EffectPair other = (EffectPair) o;
 476
 477       return (other.originalEffect.getAffectedAllocSite().equals(
 478           originalEffect.getAffectedAllocSite()) && other.originalEffect.getField().equals(
 479           originalEffect.getField()));
 480     }
 481
 482     public String toString()
 483     {
 484       return originalEffect.toString();
 485     }
 486   }
 487
 488   private class ObjRef {
 489     String field;
 490     int allocSite;
 491     boolean conflict;
 492     ConcreteRuntimeObjNode child;
 493
 494     public ObjRef(String fieldname, ConcreteRuntimeObjNode ref, boolean con) {
 495       field = fieldname;
 496       allocSite = ref.getAllocationSite();
 497       child = ref;
 498       conflict = con;
 499     }
 500   }
 501
 502   private class ConcreteRuntimeObjNode {
 503     ArrayList<ObjRef> objectRefs;
 504     ArrayList<String> primativeFields;
 505     ArrayList<ConcreteRuntimeObjNode> parents;
 506     HashSet<ConcreteRuntimeObjNode> conflictingParents;
 507     ConcreteRuntimeObjNode lastReferencer;
 508     boolean decendantsPrimConflict;
 509     boolean decendantsObjConflict;
 510     boolean isInsetVar;
 511     AllocSite allocSite;
 512     HeapRegionNode original;
 513
 514     public ConcreteRuntimeObjNode(HeapRegionNode me, boolean conflict, boolean isInVar) {
 515       objectRefs = new ArrayList<ObjRef>();
 516       parents = new ArrayList<ConcreteRuntimeObjNode>();
 517       conflictingParents = new HashSet<ConcreteRuntimeObjNode>();
 518       lastReferencer = null;
 519       allocSite = me.getAllocSite();
 520       original = me;
 521       isInsetVar = isInVar;
 522       decendantsPrimConflict = false;
 523       decendantsObjConflict = false;
 524       primativeFields = null;
 525     }
 526
 527     @Override
 528     public int hashCode() {
 529       // This gets allocsite number
 530       return allocSite.hashCodeSpecific();
 531     }
 532
 533     @Override
 534     public boolean equals(Object obj) {
 535       return original.equals(obj);
 536     }
 537
 538     public int getAllocationSite() {
 539       return allocSite.hashCodeSpecific();
 540     }
 541
 542     public int getNumOfReachableParents() {
 543       return conflictingParents.size();
 544     }
 545
 546     public boolean hasPrimativeConflicts() {
 547       return primativeFields != null;
 548     }
 549
 550     public boolean hasConflicts() {
 551       return (primativeFields != null) || !conflictingParents.isEmpty();
 552     }
 553
 554     public boolean decendantsConflict() {
 555       return decendantsPrimConflict || decendantsObjConflict;
 556     }
 557
 558     public void addObjChild(String field, ConcreteRuntimeObjNode child, boolean conflict) {
 559       child.lastReferencer = this;
 560       ObjRef ref = new ObjRef(field, child, conflict);
 561       objectRefs.add(ref);
 562       child.parents.add(this);
 563     }
 564
 565     public String toString()
 566     {
 567       return "AllocSite=" + getAllocationSite() + " myConflict=" + !conflictingParents.isEmpty() +
 568               " decCon="+decendantsObjConflict+ " NumOfParents=" + parents.size()+
 569               " NumOfConParents=" + getNumOfReachableParents() + " ObjectChildren=" + objectRefs.size();
 570     }
 571   }
 572 }