3 import java.io.FileNotFoundException;
4 import java.io.PrintWriter;
5 import java.util.ArrayList;
6 import java.util.Collection;
7 import java.util.HashSet;
8 import java.util.Hashtable;
9 import java.util.Iterator;
11 import java.util.Vector;
13 import Analysis.Disjoint.*;
14 import Analysis.MLP.CodePlan;
16 import IR.TypeDescriptor;
17 import Analysis.OoOJava.OoOJavaAnalysis;
19 /* An instance of this class manages all OoOJava coarse-grained runtime conflicts
20 * by generating C-code to either rule out the conflict at runtime or resolve one.
23 * 1) Instantiate singleton object (String input is to specify output dir)
24 * 2) Call setGlobalEffects setGlobalEffects(Hashtable<Taint, Set<Effect>> ) ONCE
25 * 3) Input SESE blocks, for each block:
26 * 3a) call addToTraverseToDoList(FlatSESEEnterNode , ReachGraph , Hashtable<Taint, Set<Effect>>) for the seseBlock
27 * 3b) call String getTraverserInvocation(TempDescriptor, String, FlatSESEEnterNode) to get the name of the traverse method in C
28 * 4) Call void close()
29 * Note: All computation is done upon closing the object. Steps 1-3 only input data
31 public class RuntimeConflictResolver {
32 public static final boolean javaDebug = true;
33 public static final boolean cSideDebug = false;
35 private PrintWriter cFile;
36 private PrintWriter headerFile;
37 private static final String hashAndQueueCFileDir = "oooJava/";
38 //This keeps track of taints we've traversed to prevent printing duplicate traverse functions
39 //The Integer keeps track of the weakly connected group it's in (used in enumerateHeapRoots)
40 private Hashtable<Taint, Integer> doneTaints;
41 private Hashtable<Tuple, Integer> idMap=new Hashtable<Tuple,Integer>();
42 private Hashtable<Taint, Set<Effect>> globalEffects;
43 private Hashtable<Taint, Set<Effect>> globalConflicts;
44 private ArrayList<TraversalInfo> toTraverse;
46 public int currentID=1;
48 // initializing variables can be found in printHeader()
49 private static final String getAllocSiteInC = "->allocsite";
50 private static final String queryVistedHashtable = "hashRCRInsert";
51 private static final String addToQueueInC = "enqueueRCRQueue(";
52 private static final String dequeueFromQueueInC = "dequeueRCRQueue()";
53 private static final String clearQueue = "resetRCRQueue()";
54 // Make hashtable; hashRCRCreate(unsigned int size, double loadfactor)
55 private static final String mallocVisitedHashtable = "hashRCRCreate(128, 0.75)";
56 private static final String deallocVisitedHashTable = "hashRCRDelete()";
57 private static final String resetVisitedHashTable = "hashRCRreset()";
59 //TODO find correct strings for these
60 private static final String addCheckFromHashStructure = "checkFromHashStructure(";
61 private static final String putWaitingQueueBlock = "putWaitingQueueBlock("; //lifting of blocks will be done by hashtable.
62 private static final String putIntoAllocQueue = "putIntoWaitingQ(";
63 private static final int noConflict = 0;
64 private static final int conflictButTraverserCanContinue = 1;
65 private static final int conflictButTraverserCannotContinue = 2;
66 private static final int allocQueueIsNotEmpty = 0;
68 // Hashtable provides fast access to heaproot # lookups
69 private Hashtable<Taint, WeaklyConectedHRGroup> connectedHRHash;
70 private ArrayList<WeaklyConectedHRGroup> num2WeaklyConnectedHRGroup;
71 private int traverserIDCounter;
72 private int weaklyConnectedHRCounter;
73 private ArrayList<TaintAndInternalHeapStructure> pendingPrintout;
74 private EffectsTable effectsLookupTable;
75 private OoOJavaAnalysis oooa;
77 public RuntimeConflictResolver(String buildir, OoOJavaAnalysis oooa) throws FileNotFoundException {
78 String outputFile = buildir + "RuntimeConflictResolver";
81 cFile = new PrintWriter(new File(outputFile + ".c"));
82 headerFile = new PrintWriter(new File(outputFile + ".h"));
84 cFile.println("#include \"" + hashAndQueueCFileDir + "hashRCR.h\"\n#include \""
85 + hashAndQueueCFileDir + "Queue_RCR.h\"\n#include <stdlib.h>");
86 cFile.println("#include \"classdefs.h\"");
87 cFile.println("#include \"structdefs.h\"");
88 cFile.println("#include \"mlp_runtime.h\"");
89 cFile.println("#include \"RuntimeConflictResolver.h\"");
90 cFile.println("#include \"hashStructure.h\"");
92 headerFile.println("#ifndef __3_RCR_H_");
93 headerFile.println("#define __3_RCR_H_");
95 doneTaints = new Hashtable<Taint, Integer>();
96 connectedHRHash = new Hashtable<Taint, WeaklyConectedHRGroup>();
98 traverserIDCounter = 1;
99 weaklyConnectedHRCounter = 0;
100 pendingPrintout = new ArrayList<TaintAndInternalHeapStructure>();
101 toTraverse = new ArrayList<TraversalInfo>();
102 globalConflicts = new Hashtable<Taint, Set<Effect>>();
103 //Note: globalEffects is not instantiated since it'll be passed in whole while conflicts comes in chunks
106 public void setGlobalEffects(Hashtable<Taint, Set<Effect>> effects) {
107 globalEffects = effects;
110 System.out.println("============EFFECTS LIST AS PASSED IN============");
111 for(Taint t: globalEffects.keySet()) {
112 System.out.println("For Taint " + t);
113 for(Effect e: globalEffects.get(t)) {
114 System.out.println("\t" + e);
117 System.out.println("====================END LIST====================");
122 //Go through the SESE's
123 for(Iterator<FlatSESEEnterNode> seseit=oooa.getAllSESEs().iterator();seseit.hasNext();) {
124 FlatSESEEnterNode fsen=seseit.next();
125 Analysis.OoOJava.ConflictGraph conflictGraph;
126 Hashtable<Taint, Set<Effect>> conflicts;
127 System.out.println("-------");
128 System.out.println(fsen);
129 System.out.println(fsen.getIsCallerSESEplaceholder());
130 System.out.println(fsen.getParent());
132 if (fsen.getParent()!=null) {
133 conflictGraph = oooa.getConflictGraph(fsen.getParent());
134 System.out.println("CG="+conflictGraph);
135 if (conflictGraph!=null)
136 System.out.println("Conflicts="+conflictGraph.getConflictEffectSet(fsen));
139 if(!fsen.getIsCallerSESEplaceholder() && fsen.getParent()!=null &&
140 (conflictGraph = oooa.getConflictGraph(fsen.getParent())) != null &&
141 (conflicts = conflictGraph.getConflictEffectSet(fsen)) != null) {
142 FlatMethod fm=fsen.getfmEnclosing();
143 ReachGraph rg=oooa.getDisjointAnalysis().getReachGraph(fm.getMethod());
145 rg.writeGraph("RCR_RG_SESE_DEBUG");
147 addToTraverseToDoList(fsen, rg, conflicts);
150 //Go through the stall sites
151 for(Iterator<FlatNode> codeit=oooa.getNodesWithPlans().iterator();codeit.hasNext();) {
152 FlatNode fn=codeit.next();
153 CodePlan cp=oooa.getCodePlan(fn);
154 FlatSESEEnterNode currentSESE=cp.getCurrentSESE();
155 Analysis.OoOJava.ConflictGraph graph = oooa.getConflictGraph(currentSESE);
158 Set<Analysis.OoOJava.SESELock> seseLockSet = oooa.getLockMappings(graph);
159 Set<Analysis.OoOJava.WaitingElement> waitingElementSet =
160 graph.getStallSiteWaitingElementSet(fn, seseLockSet);
162 if(waitingElementSet.size()>0){
163 for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext();) {
164 Analysis.OoOJava.WaitingElement waitingElement = (Analysis.OoOJava.WaitingElement) iterator.next();
166 Analysis.OoOJava.ConflictGraph conflictGraph = graph;
167 Hashtable<Taint, Set<Effect>> conflicts;
168 ReachGraph rg = oooa.getDisjointAnalysis().getReachGraph(currentSESE.getmdEnclosing());
170 rg.writeGraph("RCR_RG_STALLSITE_DEBUG");
172 if((conflictGraph != null) &&
173 (conflicts = graph.getConflictEffectSet(fn)) != null &&
175 addToTraverseToDoList(fn, waitingElement.getTempDesc(), rg, conflicts);
182 buildEffectsLookupStructure();
188 * 1) Get global effects and conflicts
189 * 2) Create a hash structure (EffectsTable) to manage effects (hashed by affected Allocsite, then taint, then field)
190 * 2a) Use Effects to verify we can access something (reads)
191 * 2b) Use conflicts to mark conflicts (read/write/strongupdate)
192 * 2c) At second level of hash, store Heaproots that can cause conflicts at the field
193 * 3) Walk hash structure to identify and enumerate weakly connected groups and generate waiting queue slots.
194 * 4) Build internal representation of the rgs (pruned)
195 * 5) Print c methods by walking internal representation
198 public void addToTraverseToDoList(FlatSESEEnterNode rblock, ReachGraph rg, Hashtable<Taint, Set<Effect>> conflicts) {
200 toTraverse.add(new TraversalInfo(rblock, rg));
202 //Add to Global conflicts
203 for(Taint t: conflicts.keySet()) {
204 if(globalConflicts.containsKey(t)) {
205 globalConflicts.get(t).addAll(conflicts.get(t));
207 globalConflicts.put(t, conflicts.get(t));
213 public void addToTraverseToDoList(FlatNode fn, TempDescriptor tempDesc,
214 ReachGraph rg, Hashtable<Taint, Set<Effect>> conflicts) {
215 toTraverse.add(new TraversalInfo(fn, rg, tempDesc));
217 for(Taint t: conflicts.keySet()) {
218 if(globalConflicts.containsKey(t)) {
219 globalConflicts.get(t).addAll(conflicts.get(t));
221 globalConflicts.put(t, conflicts.get(t));
226 private void traverseSESEBlock(FlatSESEEnterNode rblock, ReachGraph rg) {
227 Collection<TempDescriptor> inVars = rblock.getInVarSet();
229 if (inVars.size() == 0)
231 System.out.println("RBLOCK:"+rblock);
232 System.out.println("["+inVars+"]");
233 // For every non-primitive variable, generate unique method
234 // Special Note: The Criteria for executing printCMethod in this loop should match
235 // exactly the criteria in buildcode.java to invoke the generated C method(s).
236 for (TempDescriptor invar : inVars) {
237 TypeDescriptor type = invar.getType();
238 if(type.isPrimitive()) {
241 System.out.println(invar);
242 //created stores nodes with specific alloc sites that have been traversed while building
243 //internal data structure. It is later traversed sequentially to find inset variables and
245 //NOTE: Integer stores Allocation Site ID
246 Hashtable<Integer, ConcreteRuntimeObjNode> created = new Hashtable<Integer, ConcreteRuntimeObjNode>();
247 VariableNode varNode = rg.getVariableNodeNoMutation(invar);
248 Taint taint = getProperTaintForFlatSESEEnterNode(rblock, varNode, globalEffects);
250 printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + rblock.toPrettyString());
254 //This is to prevent duplicate traversals from being generated
255 if(doneTaints.containsKey(taint))
258 doneTaints.put(taint, traverserIDCounter++);
259 createConcreteGraph(effectsLookupTable, created, varNode, taint);
262 //This will add the taint to the printout, there will be NO duplicates (checked above)
263 if(!created.isEmpty()) {
264 for(Iterator<ConcreteRuntimeObjNode> it=created.values().iterator();it.hasNext();) {
265 ConcreteRuntimeObjNode obj=it.next();
266 if (obj.hasPrimitiveConflicts()||obj.decendantsConflict()) {
267 rblock.addInVarForDynamicCoarseConflictResolution(invar);
271 pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created));
276 private void traverseStallSite(FlatNode enterNode, TempDescriptor invar, ReachGraph rg) {
277 TypeDescriptor type = invar.getType();
278 if(type == null || type.isPrimitive()) {
281 Hashtable<Integer, ConcreteRuntimeObjNode> created = new Hashtable<Integer, ConcreteRuntimeObjNode>();
282 VariableNode varNode = rg.getVariableNodeNoMutation(invar);
283 Taint taint = getProperTaintForEnterNode(enterNode, varNode, globalEffects);
286 printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + enterNode.toString());
290 if(doneTaints.containsKey(taint))
293 doneTaints.put(taint, traverserIDCounter++);
294 createConcreteGraph(effectsLookupTable, created, varNode, taint);
296 if (!created.isEmpty()) {
297 pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created));
301 public String getTraverserInvocation(TempDescriptor invar, String varString, FlatNode fn) {
303 if(fn instanceof FlatSESEEnterNode) {
304 flatname = ((FlatSESEEnterNode) fn).getPrettyIdentifier();
306 flatname = fn.toString();
309 return "traverse___" + invar.getSafeSymbol() +
310 removeInvalidChars(flatname) + "___("+varString+");";
313 public int getTraverserID(TempDescriptor invar, FlatNode fn) {
314 Tuple t=new Tuple(invar, fn);
315 if (idMap.containsKey(t))
316 return idMap.get(t).intValue();
317 int value=currentID++;
318 idMap.put(t, new Integer(value));
322 public String removeInvalidChars(String in) {
323 StringBuilder s = new StringBuilder(in);
324 for(int i = 0; i < s.length(); i++) {
325 if(s.charAt(i) == ' ' || s.charAt(i) == '.' || s.charAt(i) == '='||s.charAt(i)=='['||s.charAt(i)==']') {
333 public void close() {
334 //prints out all generated code
335 for(TaintAndInternalHeapStructure ths: pendingPrintout) {
336 printCMethod(ths.nodesInHeap, ths.t);
339 //Prints out the master traverser Invocation that'll call all other traverser
340 //based on traverserID
341 printMasterTraverserInvocation();
342 printResumeTraverserInvocation();
344 //TODO this is only temporary, remove when thread local vars implemented.
345 createMasterHashTableArray();
347 // Adds Extra supporting methods
348 cFile.println("void initializeStructsRCR() {\n " + mallocVisitedHashtable + ";\n " + clearQueue + ";\n}");
349 cFile.println("void destroyRCR() {\n " + deallocVisitedHashTable + ";\n}");
351 headerFile.println("void initializeStructsRCR();\nvoid destroyRCR();");
352 headerFile.println("#endif\n");
358 //Builds Effects Table and runs the analysis on them to get weakly connected HRs
359 //SPECIAL NOTE: Only runs after we've taken all the conflicts
360 private void buildEffectsLookupStructure(){
361 effectsLookupTable = new EffectsTable(globalEffects, globalConflicts);
362 effectsLookupTable.runAnalysis();
363 enumerateHeaproots();
366 private void runAllTraversals() {
367 for(TraversalInfo t: toTraverse) {
368 printDebug(javaDebug, "Running Traversal a traversal on " + t.f);
370 if(t.f instanceof FlatSESEEnterNode) {
371 traverseSESEBlock((FlatSESEEnterNode)t.f, t.rg);
373 if(t.invar == null) {
374 System.out.println("RCR ERROR: Attempted to run a stall site traversal with NO INVAR");
376 traverseStallSite(t.f, t.invar, t.rg);
383 //TODO: This is only temporary, remove when thread local variables are functional.
384 private void createMasterHashTableArray() {
385 headerFile.println("void createAndFillMasterHashStructureArray();");
386 cFile.println("void createAndFillMasterHashStructureArray() {\n" +
387 " rcr_createMasterHashTableArray("+weaklyConnectedHRCounter + ");");
389 for(int i = 0; i < weaklyConnectedHRCounter; i++) {
390 cFile.println(" allHashStructures["+i+"] = (HashStructure *) rcr_createHashtable("+num2WeaklyConnectedHRGroup.get(i).connectedHRs.size()+");");
395 private void printMasterTraverserInvocation() {
396 headerFile.println("\nint tasktraverse(SESEcommon * record);");
397 cFile.println("\nint tasktraverse(SESEcommon * record) {");
398 cFile.println(" switch(record->classID) {");
400 for(Iterator<FlatSESEEnterNode> seseit=oooa.getAllSESEs().iterator();seseit.hasNext();) {
401 FlatSESEEnterNode fsen=seseit.next();
402 cFile.println( " /* "+fsen.getPrettyIdentifier()+" */");
403 cFile.println( " case "+fsen.getIdentifier()+": {");
404 cFile.println( " "+fsen.getSESErecordName()+" * rec=("+fsen.getSESErecordName()+" *) record;");
405 Vector<TempDescriptor> invars=fsen.getInVarsForDynamicCoarseConflictResolution();
406 for(int i=0;i<invars.size();i++) {
407 TempDescriptor tmp=invars.get(i);
408 cFile.println(" " + this.getTraverserInvocation(tmp, "rec->"+tmp+", rec", fsen));
410 cFile.println( " }");
411 cFile.println( " break;");
414 for(Taint t: doneTaints.keySet()) {
415 if (t.isStallSiteTaint()){
416 cFile.println( " case -" + getTraverserID(t.getVar(), t.getStallSite())+ ": {");
417 cFile.println( " SESEstall * rec=(SESEstall*) record;");
418 cFile.println( " " + this.getTraverserInvocation(t.getVar(), "rec->___obj___, rec", t.getStallSite())+";");
419 cFile.println( " }");
420 cFile.println(" break;");
424 cFile.println(" default:\n printf(\"Invalid SESE ID was passed in.\\n\");\n break;");
431 //This will print the traverser invocation that takes in a traverserID and
433 private void printResumeTraverserInvocation() {
434 headerFile.println("\nint traverse(void * startingPtr, SESEcommon * record, int traverserID);");
435 cFile.println("\nint traverse(void * startingPtr, SESEcommon *record, int traverserID) {");
436 cFile.println(" switch(traverserID) {");
438 for(Taint t: doneTaints.keySet()) {
439 cFile.println(" case " + doneTaints.get(t)+ ":");
440 if(t.isRBlockTaint()) {
441 cFile.println(" " + this.getTraverserInvocation(t.getVar(), "startingPtr, ("+t.getSESE().getSESErecordName()+" *)record", t.getSESE()));
442 } else if (t.isStallSiteTaint()){
443 cFile.println("/* " + this.getTraverserInvocation(t.getVar(), "startingPtr, record", t.getStallSite())+"*/");
445 System.out.println("RuntimeConflictResolver encountered a taint that is neither SESE nor stallsite: " + t);
447 cFile.println(" break;");
450 if(RuntimeConflictResolver.cSideDebug) {
451 cFile.println(" default:\n printf(\"Invalid traverser ID %u was passed in.\\n\", traverserID);\n break;");
453 cFile.println(" default:\n break;");
460 private void createConcreteGraph(
462 Hashtable<Integer, ConcreteRuntimeObjNode> created,
463 VariableNode varNode,
466 // if table is null that means there's no conflicts, therefore we need not
467 // create a traversal
471 Iterator<RefEdge> possibleEdges = varNode.iteratorToReferencees();
472 while (possibleEdges.hasNext()) {
473 RefEdge edge = possibleEdges.next();
476 ConcreteRuntimeObjNode singleRoot = new ConcreteRuntimeObjNode(edge.getDst(), true, false);
477 int rootKey = singleRoot.allocSite.getUniqueAllocSiteID();
479 if (!created.containsKey(rootKey)) {
480 created.put(rootKey, singleRoot);
481 createHelper(singleRoot, edge.getDst().iteratorToReferencees(), created, table, t);
486 //This code is the old way of generating an effects lookup table.
487 //The new way is to instantiate an EffectsGroup
489 private Hashtable<AllocSite, EffectsGroup> generateEffectsLookupTable(
490 Taint taint, Hashtable<Taint,
491 Set<Effect>> effects,
492 Hashtable<Taint, Set<Effect>> conflicts) {
496 Set<Effect> localEffects = effects.get(taint);
497 Set<Effect> localConflicts = conflicts.get(taint);
499 //Debug Code for manually checking effects
501 printEffectsAndConflictsSets(taint, localEffects, localConflicts);
504 if (localEffects == null || localEffects.isEmpty() || localConflicts == null || localConflicts.isEmpty())
507 Hashtable<AllocSite, EffectsGroup> lookupTable = new Hashtable<AllocSite, EffectsGroup>();
509 for (Effect e : localEffects) {
510 boolean conflict = localConflicts.contains(e);
511 AllocSite key = e.getAffectedAllocSite();
512 EffectsGroup myEffects = lookupTable.get(key);
514 if(myEffects == null) {
515 myEffects = new EffectsGroup();
516 lookupTable.put(key, myEffects);
519 if(e.getField().getType().isPrimitive()) {
521 myEffects.addPrimitive(e, true);
525 myEffects.addObjEffect(e, conflict);
532 // Plan is to add stuff to the tree depth-first sort of way. That way, we can
533 // propagate up conflicts
534 private void createHelper(ConcreteRuntimeObjNode curr,
535 Iterator<RefEdge> edges,
536 Hashtable<Integer, ConcreteRuntimeObjNode> created,
539 assert table != null;
540 AllocSite parentKey = curr.allocSite;
541 EffectsGroup currEffects = table.getEffects(parentKey, taint);
543 if (currEffects == null || currEffects.isEmpty())
546 //Handle Objects (and primitives if child is new)
547 if(currEffects.hasObjectEffects()) {
548 while(edges.hasNext()) {
549 RefEdge edge = edges.next();
550 String field = edge.getField();
551 CombinedObjEffects effectsForGivenField = currEffects.getObjEffect(field);
552 //If there are no effects, then there's no point in traversing this edge
553 if(effectsForGivenField != null) {
554 HeapRegionNode childHRN = edge.getDst();
555 int childKey = childHRN.getAllocSite().getUniqueAllocSiteID();
556 boolean isNewChild = !created.containsKey(childKey);
557 ConcreteRuntimeObjNode child;
560 child = new ConcreteRuntimeObjNode(childHRN, false, curr.isObjectArray());
561 created.put(childKey, child);
563 child = created.get(childKey);
566 curr.addObjChild(field, child, effectsForGivenField);
568 if (effectsForGivenField.hasConflict()) {
569 child.hasPotentialToBeIncorrectDueToConflict = true;
570 propagateObjConflict(curr, child);
573 if(effectsForGivenField.hasReadEffect) {
574 child.addReachableParent(curr);
576 //If isNewChild, flag propagation will be handled at recursive call
578 createHelper(child, childHRN.iteratorToReferencees(), created, table, taint);
580 //This makes sure that all conflicts below the child is propagated up the referencers.
581 if(child.decendantsPrimConflict || child.hasPrimitiveConflicts()) {
582 propagatePrimConflict(child, child.enqueueToWaitingQueueUponConflict);
585 if(child.decendantsObjConflict) {
586 propagateObjConflict(child, child.enqueueToWaitingQueueUponConflict);
595 curr.primitiveConflictingFields = currEffects.primitiveConflictingFields;
596 if(currEffects.hasPrimitiveConflicts()) {
597 //Reminder: primitive conflicts are abstracted to object.
598 propagatePrimConflict(curr, curr);
602 // This will propagate the conflict up the data structure.
603 private void propagateObjConflict(ConcreteRuntimeObjNode curr, HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
604 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
605 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer
606 (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess))) // case where referencer has never seen possible unresolved referencee below
608 referencer.decendantsObjConflict = true;
609 propagateObjConflict(referencer, pointsOfAccess);
614 private void propagateObjConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) {
615 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
616 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer
617 (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess))) // case where referencer has never seen possible unresolved referencee below
619 referencer.decendantsObjConflict = true;
620 propagateObjConflict(referencer, pointOfAccess);
625 private void propagatePrimConflict(ConcreteRuntimeObjNode curr, HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
626 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
627 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above
628 (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess)))
630 referencer.decendantsPrimConflict = true;
631 propagatePrimConflict(referencer, pointsOfAccess);
636 private void propagatePrimConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) {
637 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
638 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above
639 (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess)))
641 referencer.decendantsPrimConflict = true;
642 propagatePrimConflict(referencer, pointOfAccess);
650 * This method generates a C method for every inset variable and rblock.
652 * The C method works by generating a large switch statement that will run the appropriate
653 * checking code for each object based on its allocation site. The switch statement is
654 * surrounded by a while statement which dequeues objects to be checked from a queue. An
655 * object is added to a queue only if it contains a conflict (in itself or in its referencees)
656 * and we came across it while checking through it's referencer. Because of this property,
657 * conflicts will be signaled by the referencer; the only exception is the inset variable which can
658 * signal a conflict within itself.
661 private void printCMethod(Hashtable<Integer, ConcreteRuntimeObjNode> created, Taint taint) {
662 //This hash table keeps track of all the case statements generated. Although it may seem a bit much
663 //for its purpose, I think it may come in handy later down the road to do it this way.
664 //(i.e. what if we want to eliminate some cases? Or build filter for 1 case)
665 String inVar = taint.getVar().getSafeSymbol();
668 if(taint.isStallSiteTaint()) {
669 rBlock = taint.getStallSite().toString();
670 } else if(taint.isRBlockTaint()) {
671 rBlock = taint.getSESE().getPrettyIdentifier();
673 System.out.println("RCR CRITICAL ERROR: TAINT IS NEITHER A STALLSITE NOR SESE! " + taint.toString());
677 Hashtable<AllocSite, StringBuilder> cases = new Hashtable<AllocSite, StringBuilder>();
680 for (ConcreteRuntimeObjNode node : created.values()) {
681 printDebug(javaDebug, "Considering " + node.allocSite + " for traversal");
682 if (!cases.containsKey(node.allocSite) && qualifiesForCaseStatement(node)) {
683 printDebug(javaDebug, "+\t" + node.allocSite + " qualified for case statement");
684 addChecker(taint, node, cases, null, "ptr", 0);
687 //IMPORTANT: remember to change getTraverserInvocation if you change the line below
691 if (taint.isStallSiteTaint()) {
692 methodName= "void traverse___" + inVar + removeInvalidChars(rBlock) + "___(void * InVar, SESEstall *record)";
694 methodName= "void traverse___" + inVar + removeInvalidChars(rBlock) + "___(void * InVar, "+taint.getSESE().getSESErecordName() +" *record)";
695 FlatSESEEnterNode fsese=taint.getSESE();
696 TempDescriptor tmp=taint.getVar();
697 index=fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp);
700 cFile.println(methodName + " {");
701 headerFile.println(methodName + ";");
704 cFile.println("printf(\"The traverser ran for " + methodName + "\\n\");");
707 if(cases.size() == 0) {
708 cFile.println(" return;");
710 cFile.println(" int totalcount=RUNBIAS;\n");
712 if (taint.isStallSiteTaint()) {
713 cFile.println(" record->rcrRecords[0].count=RUNBIAS;\n");
715 cFile.println(" record->rcrRecords["+index+"].count=RUNBIAS;\n");
716 cFile.println(" record->rcrRecords["+index+"].index=0;\n");
719 //clears queue and hashtable that keeps track of where we've been.
720 cFile.println(clearQueue + ";\n" + resetVisitedHashTable + ";");
722 //Casts the ptr to a generic object struct so we can get to the ptr->allocsite field.
723 cFile.println("struct ___Object___ * ptr = (struct ___Object___ *) InVar;\nif (InVar != NULL) {\n " + queryVistedHashtable + "(ptr);\n do {");
725 cFile.println(" switch(ptr->allocsite) {");
727 for(AllocSite singleCase: cases.keySet())
728 cFile.append(cases.get(singleCase));
730 cFile.println(" default:\n break; ");
731 cFile.println(" }\n } while((ptr = " + dequeueFromQueueInC + ") != NULL);\n}");
733 if (taint.isStallSiteTaint()) {
735 cFile.println(" if(atomic_sub_and_test(RUNBIAS-totalcount,&(record->rcrRecords[0].count))) {");
736 cFile.println(" psem_give_tag(record->common.parentsStallSem, record->tag);");
737 cFile.println(" BARRIER();");
738 cFile.println(" record->common.rcrstatus=0;");
741 cFile.println(" if(atomic_sub_and_test(RUNBIAS-totalcount,&(record->rcrRecords["+index+"].count))) {");
742 cFile.println(" int flag=LOCKXCHG32(&(record->rcrRecords["+index+"].flag),0);");
743 cFile.println(" if(flag) {");
744 //we have resolved a heap root...see if this was the last dependence
745 cFile.println(" if(atomic_sub_and_test(1, &(record->common.unresolvedDependencies))) workScheduleSubmit((void *)record);");
755 * addChecker creates a case statement for every object that is either an inset variable
756 * or has multiple referencers (incoming edges). Else it just prints the checker for that object
757 * so that its processing can be pushed up to the referencer node.
759 private void addChecker(Taint taint,
760 ConcreteRuntimeObjNode node,
761 Hashtable<AllocSite,StringBuilder> cases,
762 StringBuilder possibleContinuingCase,
765 StringBuilder currCase = possibleContinuingCase;
766 // We don't need a case statement for things with either 1 incoming or 0 out
767 // going edges, because they can be processed when checking the parent.
768 if(qualifiesForCaseStatement(node)) {
769 assert prefix.equals("ptr") && !cases.containsKey(node.allocSite);
770 currCase = new StringBuilder();
771 cases.put(node.allocSite, currCase);
772 currCase.append(" case " + node.getAllocationSite() + ": {\n");
774 //either currCase is continuing off a parent case or is its own.
775 assert currCase !=null;
776 boolean primConfRead=false;
777 boolean primConfWrite=false;
778 boolean objConfRead=false;
779 boolean objConfWrite=false;
782 for(String field: node.primitiveConflictingFields.keySet()) {
783 CombinedObjEffects effect=node.primitiveConflictingFields.get(field);
784 primConfRead|=effect.hasReadConflict;
785 primConfWrite|=effect.hasWriteConflict;
788 //Object Reference Test
789 for(ObjRef ref: node.objectRefs) {
790 CombinedObjEffects effect=ref.myEffects;
791 objConfRead|=effect.hasReadConflict;
792 objConfWrite|=effect.hasWriteConflict;
796 if (taint.isRBlockTaint()) {
797 FlatSESEEnterNode fsese=taint.getSESE();
798 TempDescriptor tmp=taint.getVar();
799 index=fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp);
802 //Do call if we need it.
803 if(primConfWrite||objConfWrite) {
804 int heaprootNum = connectedHRHash.get(taint).id;
805 assert heaprootNum != -1;
806 int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
807 int traverserID = doneTaints.get(taint);
808 currCase.append(" int tmpkey"+depth+"=rcr_generateKey("+prefix+");\n");
810 currCase.append(" int tmpvar"+depth+"=rcr_WTWRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+index+");\n");
812 currCase.append(" int tmpvar"+depth+"=rcr_WRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+index+");\n");
813 } else if (primConfRead||objConfRead) {
814 int heaprootNum = connectedHRHash.get(taint).id;
815 assert heaprootNum != -1;
816 int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
817 int traverserID = doneTaints.get(taint);
818 currCase.append(" int tmpkey"+depth+"=rcr_generateKey("+prefix+");\n");
820 currCase.append(" int tmpvar"+depth+"=rcr_WTREADBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+index+");\n");
822 currCase.append(" int tmpvar"+depth+"=rcr_READBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+index+");\n");
825 if(primConfWrite||objConfWrite||primConfRead||objConfRead) {
826 currCase.append("if (!(tmpvar"+depth+"&READYMASK)) totalcount--;\n");
827 currCase.append("if (!(tmpvar"+depth+"&SPEC)) {\n");
828 if (taint.isStallSiteTaint()) {
829 currCase.append(" struct rcrRecord * rcrrec=&record->rcrRecords["+index+"];\n");
830 currCase.append(" struct rcrRecord * tmprec;\n");
831 currCase.append(" if(likely(rcrrec->index<RCRSIZE)) {\n");
832 currCase.append(" rcrrec->array[rcrrec->index++]=tmpkey"+depth+";\n");
833 currCase.append("} else if(likely((tmprec=rcrrec->next)!=NULL)&&likely(tmprec->index<RCRSIZE)) {\n");
834 currCase.append(" tmprec->array[tmprec->index++]=tmpkey"+depth+";\n");
835 currCase.append("} else {\n");
836 currCase.append(" struct rcrRecord *trec=RUNMALLOC(sizeof(struct rcrRecord));");
837 currCase.append(" trec->array[0]=tmpkey"+depth+";\n");
838 currCase.append(" trec->index=1;\n");
839 currCase.append(" trec->next=tmprec;\n");
840 currCase.append(" rcrrec->next=trec;\n");
841 currCase.append("}\n");
843 currCase.append("}\n");
847 if(node.isObjectArray() && node.decendantsConflict()) {
848 //since each array element will get its own case statement, we just need to enqueue each item into the queue
849 //note that the ref would be the actual object and node would be of struct ArrayObject
851 ArrayList<Integer> allocSitesWithProblems = node.getReferencedAllocSites();
852 if(!allocSitesWithProblems.isEmpty()) {
853 //This is done with the assumption that an array of object stores pointers.
854 currCase.append("{\n int i;\n");
855 currCase.append(" for(i = 0; i<((struct ArrayObject *) " + prefix + " )->___length___; i++ ) {\n");
856 currCase.append(" struct ___Object___ * arrayElement =((struct ___Object___ **)(((char *) &(((struct ArrayObject *)"+ prefix+")->___length___))+sizeof(int)))[i];\n");
857 currCase.append(" if( arrayElement != NULL && (");
859 for(Integer i: allocSitesWithProblems) {
860 currCase.append("( arrayElement->allocsite == " + i.toString() +") ||");
862 //gets rid of the last ||
863 currCase.delete(currCase.length()-3, currCase.length());
865 currCase.append(") && "+queryVistedHashtable +"(arrayElement)) {\n");
866 currCase.append(" " + addToQueueInC + "arrayElement); }}}\n");
870 for(ObjRef ref: node.objectRefs) {
871 currCase.append("{ \n");
872 // Will only process edge if there is some sort of conflict with the Child
873 if (ref.hasConflictsDownThisPath()) {
874 String childPtr = "((struct "+node.original.getType().getSafeSymbol()+" *)"+prefix +")->___" + ref.field + "___";
876 String currPtr = "myPtr" + pdepth;
877 String structType = ref.child.original.getType().getSafeSymbol();
878 currCase.append(" struct " + structType + " * "+currPtr+"= (struct "+ structType + " * ) " + childPtr + ";\n");
880 // Checks if the child exists and has allocsite matching the conflict
881 currCase.append(" if (" + currPtr + " != NULL && " + currPtr + getAllocSiteInC + "==" + ref.allocSite + ") {\n");
883 if (ref.child.decendantsConflict() || ref.child.hasPrimitiveConflicts()) {
884 // Checks if we have visited the child before
886 currCase.append(" if (" + queryVistedHashtable +"("+ currPtr + ")) {\n");
887 if (ref.child.getNumOfReachableParents() == 1 && !ref.child.isInsetVar) {
888 addChecker(taint, ref.child, cases, currCase, currPtr, depth + 1);
891 currCase.append(" " + addToQueueInC + childPtr + ");\n ");
893 currCase.append(" }\n");
895 //one more brace for the opening if
896 if(ref.hasDirectObjConflict()) {
897 currCase.append(" }\n");
899 currCase.append(" }\n ");
901 currCase.append("} ");
905 if(qualifiesForCaseStatement(node)) {
906 currCase.append(" }\n break;\n");
910 private boolean qualifiesForCaseStatement(ConcreteRuntimeObjNode node) {
913 (node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
914 //non-inline-able code cases
915 (node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
916 //Cases where resumes are possible
917 (node.hasPotentialToBeIncorrectDueToConflict) && node.decendantsObjConflict) ||
918 //Array elements since we have to enqueue them all, we can't in line their checks
919 (node.canBeArrayElement() && (node.decendantsConflict() || node.hasPrimitiveConflicts()));
922 //This method will touch the waiting queues if necessary.
923 //IMPORTANT NOTE: This needs a closing } from the caller and the if is cannot continue
924 private void addCheckHashtableAndWaitingQ(StringBuilder currCase, Taint t, ConcreteRuntimeObjNode node, String ptr, int depth) {
925 Iterator<ConcreteRuntimeObjNode> it = node.enqueueToWaitingQueueUponConflict.iterator();
927 currCase.append(" int retval"+depth+" = "+ addCheckFromHashStructure + ptr + ");\n");
928 currCase.append(" if (retval"+depth+" == " + conflictButTraverserCannotContinue + " || ");
929 checkWaitingQueue(currCase, t, node);
930 currCase.append(") {\n");
931 //If cannot continue, then add all the undetermined references that lead from this child, including self.
932 //TODO need waitingQueue Side to automatically check the thing infront of it to prevent double adds.
933 putIntoWaitingQueue(currCase, t, node, ptr);
935 ConcreteRuntimeObjNode related;
936 while(it.hasNext()) {
938 //TODO maybe ptr won't even be needed since upon resume, the hashtable will remove obj.
939 putIntoWaitingQueue(currCase, t, related, ptr);
944 private void handleObjConflict(StringBuilder currCase, String childPtr, AllocSite allocSite, ObjRef ref) {
945 currCase.append("printf(\"Conflict detected with %p from parent with allocation site %u\\n\"," + childPtr + "," + allocSite.getUniqueAllocSiteID() + ");");
948 private void handlePrimitiveConflict(StringBuilder currCase, String ptr, ArrayList<String> conflicts, AllocSite allocSite) {
949 currCase.append("printf(\"Primitive Conflict detected with %p with alloc site %u\\n\", "+ptr+", "+allocSite.getUniqueAllocSiteID()+"); ");
953 private Taint getProperTaintForFlatSESEEnterNode(FlatSESEEnterNode rblock, VariableNode var,
954 Hashtable<Taint, Set<Effect>> effects) {
955 Set<Taint> taints = effects.keySet();
956 for (Taint t : taints) {
957 FlatSESEEnterNode sese = t.getSESE();
958 if(sese != null && sese.equals(rblock) && t.getVar().equals(var.getTempDescriptor())) {
966 private Taint getProperTaintForEnterNode(FlatNode stallSite, VariableNode var,
967 Hashtable<Taint, Set<Effect>> effects) {
968 Set<Taint> taints = effects.keySet();
969 for (Taint t : taints) {
970 FlatNode flatnode = t.getStallSite();
971 if(flatnode != null && flatnode.equals(stallSite) && t.getVar().equals(var.getTempDescriptor())) {
978 private void printEffectsAndConflictsSets(Taint taint, Set<Effect> localEffects,
979 Set<Effect> localConflicts) {
980 System.out.println("#### List of Effects/Conflicts ####");
981 System.out.println("For Taint " + taint);
982 System.out.println("Effects");
983 if(localEffects != null) {
984 for(Effect e: localEffects) {
985 System.out.println(e);
988 System.out.println("Conflicts");
989 if(localConflicts != null) {
990 for(Effect e: localConflicts) {
991 System.out.println(e);
996 private void printDebug(boolean guard, String debugStatements) {
998 System.out.println(debugStatements);
1001 //TODO finish this once waitingQueue side is figured out
1002 private void putIntoWaitingQueue(StringBuilder sb, Taint taint, ConcreteRuntimeObjNode node, String resumePtr ) {
1003 //Method looks like this: void put(int allocSiteID, x
1004 //struct WaitingQueue * queue, //get this from hashtable
1005 //int effectType, //not so sure we would actually need this one.
1007 //int traverserID); }
1008 int heaprootNum = connectedHRHash.get(taint).id;
1009 assert heaprootNum != -1;
1010 int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
1011 int traverserID = doneTaints.get(taint);
1013 //NOTE if the C-side is changed, this will have to be changed accordingly
1014 //TODO make sure this matches c-side
1015 sb.append(" putIntoWaitingQueue("+allocSiteID+", " +
1016 "allHashStructures["+ heaprootNum +"]->waitingQueue, " +
1018 traverserID+");\n");
1021 //TODO finish waitingQueue side
1023 * Inserts check to see if waitingQueue is occupied.
1025 * On C-side, =0 means empty queue, else occupied.
1027 private void checkWaitingQueue(StringBuilder sb, Taint taint, ConcreteRuntimeObjNode node) {
1028 //Method looks like int check(struct WaitingQueue * queue, int allocSiteID)
1029 assert sb != null && taint !=null;
1030 int heaprootNum = connectedHRHash.get(taint).id;
1031 assert heaprootNum != -1;
1032 int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
1034 sb.append(" (isEmptyForWaitingQ(allHashStructures["+ heaprootNum +"]->waitingQueue, " + allocSiteID + ") == "+ allocQueueIsNotEmpty+")");
1037 private void enumerateHeaproots() {
1038 //reset numbers jsut in case
1039 weaklyConnectedHRCounter = 0;
1040 num2WeaklyConnectedHRGroup = new ArrayList<WeaklyConectedHRGroup>();
1042 for(Taint t: connectedHRHash.keySet()) {
1043 if(connectedHRHash.get(t).id == -1) {
1044 WeaklyConectedHRGroup hg = connectedHRHash.get(t);
1045 hg.id = weaklyConnectedHRCounter;
1046 num2WeaklyConnectedHRGroup.add(weaklyConnectedHRCounter, hg);
1047 weaklyConnectedHRCounter++;
1052 private void printoutTable(EffectsTable table) {
1054 System.out.println("==============EFFECTS TABLE PRINTOUT==============");
1055 for(AllocSite as: table.table.keySet()) {
1056 System.out.println("\tFor AllocSite " + as.getUniqueAllocSiteID());
1058 BucketOfEffects boe = table.table.get(as);
1060 if(boe.potentiallyConflictingRoots != null && !boe.potentiallyConflictingRoots.isEmpty()) {
1061 System.out.println("\t\tPotentially conflicting roots: ");
1062 for(String key: boe.potentiallyConflictingRoots.keySet()) {
1063 System.out.println("\t\t-Field: " + key);
1064 System.out.println("\t\t\t" + boe.potentiallyConflictingRoots.get(key));
1067 for(Taint t: boe.taint2EffectsGroup.keySet()) {
1068 System.out.println("\t\t For Taint " + t);
1069 EffectsGroup eg = boe.taint2EffectsGroup.get(t);
1071 if(eg.hasPrimitiveConflicts()) {
1072 System.out.print("\t\t\tPrimitive Conflicts at alloc " + as.getUniqueAllocSiteID() +" : ");
1073 for(String field: eg.primitiveConflictingFields.keySet()) {
1074 System.out.print(field + " ");
1076 System.out.println();
1078 for(String fieldKey: eg.myEffects.keySet()) {
1079 CombinedObjEffects ce = eg.myEffects.get(fieldKey);
1080 System.out.println("\n\t\t\tFor allocSite " + as.getUniqueAllocSiteID() + " && field " + fieldKey);
1081 System.out.println("\t\t\t\tread " + ce.hasReadEffect + "/"+ce.hasReadConflict +
1082 " write " + ce.hasWriteEffect + "/" + ce.hasWriteConflict +
1083 " SU " + ce.hasStrongUpdateEffect + "/" + ce.hasStrongUpdateConflict);
1084 for(Effect ef: ce.originalEffects) {
1085 System.out.println("\t" + ef);
1094 private class EffectsGroup {
1095 Hashtable<String, CombinedObjEffects> myEffects;
1096 Hashtable<String, CombinedObjEffects> primitiveConflictingFields;
1098 public EffectsGroup() {
1099 myEffects = new Hashtable<String, CombinedObjEffects>();
1100 primitiveConflictingFields = new Hashtable<String, CombinedObjEffects>();
1103 public void addPrimitive(Effect e, boolean conflict) {
1104 CombinedObjEffects effects;
1105 if((effects = primitiveConflictingFields.get(e.getField().getSymbol())) == null) {
1106 effects = new CombinedObjEffects();
1107 primitiveConflictingFields.put(e.getField().getSymbol(), effects);
1109 effects.add(e, conflict);
1112 public void addObjEffect(Effect e, boolean conflict) {
1113 CombinedObjEffects effects;
1114 if((effects = myEffects.get(e.getField().getSymbol())) == null) {
1115 effects = new CombinedObjEffects();
1116 myEffects.put(e.getField().getSymbol(), effects);
1118 effects.add(e, conflict);
1121 public boolean isEmpty() {
1122 return myEffects.isEmpty() && primitiveConflictingFields.isEmpty();
1125 public boolean hasPrimitiveConflicts(){
1126 return !primitiveConflictingFields.isEmpty();
1129 public CombinedObjEffects getPrimEffect(String field) {
1130 return primitiveConflictingFields.get(field);
1133 public boolean hasObjectEffects() {
1134 return !myEffects.isEmpty();
1137 public CombinedObjEffects getObjEffect(String field) {
1138 return myEffects.get(field);
1142 //Is the combined effects for all effects with the same affectedAllocSite and field
1143 private class CombinedObjEffects {
1144 ArrayList<Effect> originalEffects;
1146 public boolean hasReadEffect;
1147 public boolean hasWriteEffect;
1148 public boolean hasStrongUpdateEffect;
1150 public boolean hasReadConflict;
1151 public boolean hasWriteConflict;
1152 public boolean hasStrongUpdateConflict;
1155 public CombinedObjEffects() {
1156 originalEffects = new ArrayList<Effect>();
1158 hasReadEffect = false;
1159 hasWriteEffect = false;
1160 hasStrongUpdateEffect = false;
1162 hasReadConflict = false;
1163 hasWriteConflict = false;
1164 hasStrongUpdateConflict = false;
1167 public boolean add(Effect e, boolean conflict) {
1168 if(!originalEffects.add(e))
1171 switch(e.getType()) {
1173 hasReadEffect = true;
1174 hasReadConflict = conflict;
1177 hasWriteEffect = true;
1178 hasWriteConflict = conflict;
1180 case Effect.strongupdate:
1181 hasStrongUpdateEffect = true;
1182 hasStrongUpdateConflict = conflict;
1185 System.out.println("RCR ERROR: An Effect Type never seen before has been encountered");
1192 public boolean hasConflict() {
1193 return hasReadConflict || hasWriteConflict || hasStrongUpdateConflict;
1196 public void mergeWith(CombinedObjEffects other) {
1197 for(Effect e: other.originalEffects) {
1198 if(!originalEffects.contains(e)){
1199 originalEffects.add(e);
1203 hasReadEffect |= other.hasReadEffect;
1204 hasWriteEffect |= other.hasWriteEffect;
1205 hasStrongUpdateEffect |= other.hasStrongUpdateEffect;
1207 hasReadConflict |= other.hasReadConflict;
1208 hasWriteConflict |= other.hasWriteConflict;
1209 hasStrongUpdateConflict |= other.hasStrongUpdateConflict;
1213 //This will keep track of a reference
1214 private class ObjRef {
1217 CombinedObjEffects myEffects;
1219 //This keeps track of the parent that we need to pass by inorder to get
1220 //to the conflicting child (if there is one).
1221 ConcreteRuntimeObjNode child;
1223 public ObjRef(String fieldname,
1224 ConcreteRuntimeObjNode ref,
1225 CombinedObjEffects myEffects) {
1227 allocSite = ref.getAllocationSite();
1230 this.myEffects = myEffects;
1233 public boolean hasConflictsDownThisPath() {
1234 return child.decendantsObjConflict || child.decendantsPrimConflict || child.hasPrimitiveConflicts() || myEffects.hasConflict();
1237 public boolean hasDirectObjConflict() {
1238 return myEffects.hasConflict();
1241 public boolean equals(Object other) {
1242 if(other == null || !(other instanceof ObjRef))
1245 ObjRef o = (ObjRef) other;
1247 if(o.field == this.field && o.allocSite == this.allocSite && this.child.equals(o.child))
1253 public int hashCode() {
1254 return child.allocSite.hashCode() ^ field.hashCode();
1257 public void mergeWith(ObjRef ref) {
1258 myEffects.mergeWith(ref.myEffects);
1262 private class ConcreteRuntimeObjNode {
1263 ArrayList<ObjRef> objectRefs;
1264 Hashtable<String, CombinedObjEffects> primitiveConflictingFields;
1265 HashSet<ConcreteRuntimeObjNode> parentsWithReadToNode;
1266 HashSet<ConcreteRuntimeObjNode> parentsThatWillLeadToConflicts;
1267 //this set keeps track of references down the line that need to be enqueued if traverser is "paused"
1268 HashSet<ConcreteRuntimeObjNode> enqueueToWaitingQueueUponConflict;
1269 boolean decendantsPrimConflict;
1270 boolean decendantsObjConflict;
1271 boolean hasPotentialToBeIncorrectDueToConflict;
1273 boolean isArrayElement;
1274 AllocSite allocSite;
1275 HeapRegionNode original;
1277 public ConcreteRuntimeObjNode(HeapRegionNode me, boolean isInVar, boolean isArrayElement) {
1278 objectRefs = new ArrayList<ObjRef>();
1279 primitiveConflictingFields = null;
1280 parentsThatWillLeadToConflicts = new HashSet<ConcreteRuntimeObjNode>();
1281 parentsWithReadToNode = new HashSet<ConcreteRuntimeObjNode>();
1282 enqueueToWaitingQueueUponConflict = new HashSet<ConcreteRuntimeObjNode>();
1283 allocSite = me.getAllocSite();
1285 isInsetVar = isInVar;
1286 decendantsPrimConflict = false;
1287 decendantsObjConflict = false;
1288 hasPotentialToBeIncorrectDueToConflict = false;
1289 this.isArrayElement = isArrayElement;
1292 public void addReachableParent(ConcreteRuntimeObjNode curr) {
1293 parentsWithReadToNode.add(curr);
1297 public boolean equals(Object obj) {
1298 return original.equals(obj);
1301 public int getAllocationSite() {
1302 return allocSite.getUniqueAllocSiteID();
1305 public int getNumOfReachableParents() {
1306 return parentsThatWillLeadToConflicts.size();
1309 public boolean hasPrimitiveConflicts() {
1310 return primitiveConflictingFields != null && !primitiveConflictingFields.isEmpty();
1313 public boolean decendantsConflict() {
1314 return decendantsPrimConflict || decendantsObjConflict;
1318 //returns true if at least one of the objects in points of access has been added
1319 public boolean addPossibleWaitingQueueEnqueue(HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
1320 boolean addedNew = false;
1321 for(ConcreteRuntimeObjNode dec: pointsOfAccess) {
1322 if(dec != null && dec != this){
1323 addedNew = addedNew || enqueueToWaitingQueueUponConflict.add(dec);
1330 public boolean addPossibleWaitingQueueEnqueue(ConcreteRuntimeObjNode pointOfAccess) {
1331 if(pointOfAccess != null && pointOfAccess != this){
1332 return enqueueToWaitingQueueUponConflict.add(pointOfAccess);
1338 public void addObjChild(String field, ConcreteRuntimeObjNode child, CombinedObjEffects ce) {
1339 ObjRef ref = new ObjRef(field, child, ce);
1341 if(objectRefs.contains(ref)) {
1342 ObjRef other = objectRefs.get(objectRefs.indexOf(ref));
1343 other.mergeWith(ref);
1346 objectRefs.add(ref);
1349 public boolean isObjectArray() {
1350 return original.getType().isArray() && !original.getType().isPrimitive() && !original.getType().isImmutable();
1353 public boolean canBeArrayElement() {
1354 return isArrayElement;
1357 public ArrayList<Integer> getReferencedAllocSites() {
1358 ArrayList<Integer> list = new ArrayList<Integer>();
1360 for(ObjRef r: objectRefs) {
1361 if(r.hasDirectObjConflict() || (r.child.parentsWithReadToNode.contains(this) && r.hasConflictsDownThisPath())) {
1362 list.add(r.allocSite);
1369 public String toString() {
1370 return "AllocSite=" + getAllocationSite() + " myConflict=" + !parentsThatWillLeadToConflicts.isEmpty() +
1371 " decCon="+decendantsObjConflict+
1372 " NumOfConParents=" + getNumOfReachableParents() + " ObjectChildren=" + objectRefs.size();
1376 private class EffectsTable {
1377 private Hashtable<AllocSite, BucketOfEffects> table;
1379 public EffectsTable(Hashtable<Taint, Set<Effect>> effects,
1380 Hashtable<Taint, Set<Effect>> conflicts) {
1381 table = new Hashtable<AllocSite, BucketOfEffects>();
1383 // rehash all effects (as a 5-tuple) by their affected allocation site
1384 for (Taint t : effects.keySet()) {
1385 Set<Effect> localConflicts = conflicts.get(t);
1386 for (Effect e : effects.get(t)) {
1387 BucketOfEffects bucket;
1388 if ((bucket = table.get(e.getAffectedAllocSite())) == null) {
1389 bucket = new BucketOfEffects();
1390 table.put(e.getAffectedAllocSite(), bucket);
1392 printDebug(javaDebug, "Added Taint" + t + " Effect " + e + "Conflict Status = " + (localConflicts!=null?localConflicts.contains(e):false)+" localConflicts = "+localConflicts);
1393 bucket.add(t, e, localConflicts!=null?localConflicts.contains(e):false);
1398 public EffectsGroup getEffects(AllocSite parentKey, Taint taint) {
1399 //This would get the proper bucket of effects and then get all the effects
1400 //for a parent for a specific taint
1402 return table.get(parentKey).taint2EffectsGroup.get(taint);
1404 catch (NullPointerException e) {
1409 // Run Analysis will walk the data structure and figure out the weakly
1410 // connected heap roots.
1411 public void runAnalysis() {
1413 printoutTable(this);
1416 //TODO is there a higher performance way to do this?
1417 for(AllocSite key: table.keySet()) {
1418 BucketOfEffects effects = table.get(key);
1419 //make sure there are actually conflicts in the bucket
1420 if(effects.potentiallyConflictingRoots != null && !effects.potentiallyConflictingRoots.isEmpty()){
1421 for(String field: effects.potentiallyConflictingRoots.keySet()){
1422 ArrayList<Taint> taints = effects.potentiallyConflictingRoots.get(field);
1423 //For simplicity, we just create a new group and add everything to it instead of
1424 //searching through all of them for the largest group and adding everyone in.
1425 WeaklyConectedHRGroup group = new WeaklyConectedHRGroup();
1426 group.add(taints); //This will automatically add the taint to the connectedHRhash
1433 private class WeaklyConectedHRGroup {
1434 HashSet<Taint> connectedHRs;
1435 //This is to keep track of unique waitingQueue positions for each allocsite.
1436 Hashtable<AllocSite, Integer> allocSiteToWaitingQueueMap;
1437 int waitingQueueCounter;
1440 public WeaklyConectedHRGroup() {
1441 connectedHRs = new HashSet<Taint>();
1442 id = -1; //this will be later modified
1443 waitingQueueCounter = 0;
1444 allocSiteToWaitingQueueMap = new Hashtable<AllocSite, Integer>();
1447 public void add(ArrayList<Taint> list) {
1448 for(Taint t: list) {
1453 public int getWaitingQueueBucketNum(ConcreteRuntimeObjNode node) {
1454 if(allocSiteToWaitingQueueMap.containsKey(node.allocSite)) {
1455 return allocSiteToWaitingQueueMap.get(node.allocSite);
1457 allocSiteToWaitingQueueMap.put(node.allocSite, waitingQueueCounter);
1458 return waitingQueueCounter++;
1462 public void add(Taint t) {
1463 connectedHRs.add(t);
1464 WeaklyConectedHRGroup oldGroup = connectedHRHash.get(t);
1465 connectedHRHash.put(t, this); //put new group into hash
1466 //If the taint was already in another group, move all its buddies over.
1467 if(oldGroup != this && oldGroup != null) {
1468 Iterator<Taint> it = oldGroup.connectedHRs.iterator();
1471 while((relatedTaint = it.next()) != null && !connectedHRs.contains(relatedTaint)) {
1472 this.add(relatedTaint);
1478 //This is a class that stores all the effects for an affected allocation site
1479 //across ALL taints. The structure is a hashtable of EffectGroups (see above) hashed
1480 //by a Taint. This way, I can keep EffectsGroups so I can reuse most to all of my old code
1481 //and allows for easier tracking of effects. In addition, a hashtable (keyed by the string
1482 //of the field access) keeps track of an ArrayList of taints of SESEblocks that conflict on that
1484 private class BucketOfEffects {
1485 // This table is used for lookup while creating the traversal.
1486 Hashtable<Taint, EffectsGroup> taint2EffectsGroup;
1488 //This table is used to help identify weakly connected groups: Contains ONLY
1489 //conflicting effects AND is only initialized when needed
1490 //String stores the field
1491 Hashtable<String, ArrayList<Taint>> potentiallyConflictingRoots;
1493 public BucketOfEffects() {
1494 taint2EffectsGroup = new Hashtable<Taint, EffectsGroup>();
1497 public void add(Taint t, Effect e, boolean conflict) {
1498 EffectsGroup effectsForGivenTaint;
1500 if ((effectsForGivenTaint = taint2EffectsGroup.get(t)) == null) {
1501 effectsForGivenTaint = new EffectsGroup();
1502 taint2EffectsGroup.put(t, effectsForGivenTaint);
1505 if (e.getField().getType().isPrimitive()) {
1507 effectsForGivenTaint.addPrimitive(e, true);
1510 effectsForGivenTaint.addObjEffect(e, conflict);
1514 if(potentiallyConflictingRoots == null) {
1515 potentiallyConflictingRoots = new Hashtable<String, ArrayList<Taint>>();
1518 ArrayList<Taint> taintsForField = potentiallyConflictingRoots.get(e.getField().getSafeSymbol());
1519 if(taintsForField == null) {
1520 taintsForField = new ArrayList<Taint>();
1521 potentiallyConflictingRoots.put(e.getField().getSafeSymbol(), taintsForField);
1524 if(!taintsForField.contains(t)) {
1525 taintsForField.add(t);
1531 private class TaintAndInternalHeapStructure {
1533 public Hashtable<Integer, ConcreteRuntimeObjNode> nodesInHeap;
1535 public TaintAndInternalHeapStructure(Taint taint, Hashtable<Integer, ConcreteRuntimeObjNode> nodesInHeap) {
1537 this.nodesInHeap = nodesInHeap;
1541 private class TraversalInfo {
1543 public ReachGraph rg;
1544 public TempDescriptor invar;
1546 public TraversalInfo(FlatNode fn, ReachGraph g) {
1552 public TraversalInfo(FlatNode fn, ReachGraph rg2, TempDescriptor tempDesc) {