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