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;
15 import IR.TypeDescriptor;
16 import Analysis.OoOJava.OoOJavaAnalysis;
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.
22 * 1) Instantiate singleton object (String input is to specify output dir)
23 * 2) Call setGlobalEffects setGlobalEffects(Hashtable<Taint, Set<Effect>> ) ONCE
24 * 3) Input SESE blocks, for each block:
25 * 3a) call addToTraverseToDoList(FlatSESEEnterNode , ReachGraph , Hashtable<Taint, Set<Effect>>) for the seseBlock
26 * 3b) call String getTraverserInvocation(TempDescriptor, String, FlatSESEEnterNode) to get the name of the traverse method in C
27 * 4) Call void close()
28 * Note: All computation is done upon closing the object. Steps 1-3 only input data
30 public class RuntimeConflictResolver {
31 public static final boolean javaDebug = true;
32 public static final boolean cSideDebug = true;
34 private PrintWriter cFile;
35 private PrintWriter headerFile;
36 private static final String hashAndQueueCFileDir = "oooJava/";
37 //This keeps track of taints we've traversed to prevent printing duplicate traverse functions
38 //The Integer keeps track of the weakly connected group it's in (used in enumerateHeapRoots)
39 private Hashtable<Taint, Integer> doneTaints;
40 private Hashtable<Tuple, Integer> idMap=new Hashtable<Tuple,Integer>();
41 private Hashtable<Taint, Set<Effect>> globalEffects;
42 private Hashtable<Taint, Set<Effect>> globalConflicts;
43 private ArrayList<TraversalInfo> toTraverse;
45 public int currentID=1;
47 // initializing variables can be found in printHeader()
48 private static final String getAllocSiteInC = "->allocsite";
49 private static final String queryVistedHashtable = "hashRCRInsert";
50 private static final String addToQueueInC = "enqueueRCRQueue(";
51 private static final String dequeueFromQueueInC = "dequeueRCRQueue()";
52 private static final String clearQueue = "resetRCRQueue()";
53 // Make hashtable; hashRCRCreate(unsigned int size, double loadfactor)
54 private static final String mallocVisitedHashtable = "hashRCRCreate(128, 0.75)";
55 private static final String deallocVisitedHashTable = "hashRCRDelete()";
56 private static final String resetVisitedHashTable = "hashRCRreset()";
58 // Hashtable provides fast access to heaproot # lookups
59 private Hashtable<Taint, WeaklyConectedHRGroup> connectedHRHash;
60 private ArrayList<WeaklyConectedHRGroup> num2WeaklyConnectedHRGroup;
61 private int traverserIDCounter;
62 private int weaklyConnectedHRCounter;
63 private ArrayList<TaintAndInternalHeapStructure> pendingPrintout;
64 private EffectsTable effectsLookupTable;
65 private OoOJavaAnalysis oooa;
67 public RuntimeConflictResolver(String buildir, OoOJavaAnalysis oooa) throws FileNotFoundException {
68 String outputFile = buildir + "RuntimeConflictResolver";
71 cFile = new PrintWriter(new File(outputFile + ".c"));
72 headerFile = new PrintWriter(new File(outputFile + ".h"));
74 cFile.println("#include \"" + hashAndQueueCFileDir + "hashRCR.h\"\n#include \""
75 + hashAndQueueCFileDir + "Queue_RCR.h\"\n#include <stdlib.h>");
76 cFile.println("#include \"classdefs.h\"");
77 cFile.println("#include \"structdefs.h\"");
78 cFile.println("#include \"mlp_runtime.h\"");
79 cFile.println("#include \"RuntimeConflictResolver.h\"");
80 cFile.println("#include \"hashStructure.h\"");
82 headerFile.println("#ifndef __3_RCR_H_");
83 headerFile.println("#define __3_RCR_H_");
85 doneTaints = new Hashtable<Taint, Integer>();
86 connectedHRHash = new Hashtable<Taint, WeaklyConectedHRGroup>();
88 traverserIDCounter = 1;
89 weaklyConnectedHRCounter = 0;
90 pendingPrintout = new ArrayList<TaintAndInternalHeapStructure>();
91 toTraverse = new ArrayList<TraversalInfo>();
92 globalConflicts = new Hashtable<Taint, Set<Effect>>();
93 //Note: globalEffects is not instantiated since it'll be passed in whole while conflicts comes in chunks
96 public void setGlobalEffects(Hashtable<Taint, Set<Effect>> effects) {
97 globalEffects = effects;
100 System.out.println("============EFFECTS LIST AS PASSED IN============");
101 for(Taint t: globalEffects.keySet()) {
102 System.out.println("For Taint " + t);
103 for(Effect e: globalEffects.get(t)) {
104 System.out.println("\t" + e);
107 System.out.println("====================END LIST====================");
112 // Go through the SESE's
113 for (Iterator<FlatSESEEnterNode> seseit = oooa.getAllSESEs().iterator(); seseit.hasNext();) {
114 FlatSESEEnterNode fsen = seseit.next();
115 Analysis.OoOJava.ConflictGraph conflictGraph;
116 Hashtable<Taint, Set<Effect>> conflicts;
117 System.out.println("-------");
118 System.out.println(fsen);
119 System.out.println(fsen.getIsCallerSESEplaceholder());
120 System.out.println(fsen.getParent());
122 if (fsen.getParent() != null) {
123 conflictGraph = oooa.getConflictGraph(fsen.getParent());
124 System.out.println("CG=" + conflictGraph);
125 if (conflictGraph != null)
126 System.out.println("Conflicts=" + conflictGraph.getConflictEffectSet(fsen));
129 if (!fsen.getIsCallerSESEplaceholder() && fsen.getParent() != null
130 && (conflictGraph = oooa.getConflictGraph(fsen.getParent())) != null
131 && (conflicts = conflictGraph.getConflictEffectSet(fsen)) != null) {
132 FlatMethod fm = fsen.getfmEnclosing();
133 ReachGraph rg = oooa.getDisjointAnalysis().getReachGraph(fm.getMethod());
135 rg.writeGraph("RCR_RG_SESE_DEBUG");
137 addToTraverseToDoList(fsen, rg, conflicts);
140 // Go through the stall sites
141 for (Iterator<FlatNode> codeit = oooa.getNodesWithPlans().iterator(); codeit.hasNext();) {
142 FlatNode fn = codeit.next();
143 CodePlan cp = oooa.getCodePlan(fn);
144 FlatSESEEnterNode currentSESE = cp.getCurrentSESE();
145 Analysis.OoOJava.ConflictGraph graph = oooa.getConflictGraph(currentSESE);
148 Set<Analysis.OoOJava.SESELock> seseLockSet = oooa.getLockMappings(graph);
149 Set<Analysis.OoOJava.WaitingElement> waitingElementSet =
150 graph.getStallSiteWaitingElementSet(fn, seseLockSet);
152 if (waitingElementSet.size() > 0) {
153 for (Iterator<Analysis.OoOJava.WaitingElement> iterator = waitingElementSet.iterator(); iterator.hasNext();) {
154 Analysis.OoOJava.WaitingElement waitingElement =
155 (Analysis.OoOJava.WaitingElement) iterator.next();
157 Analysis.OoOJava.ConflictGraph conflictGraph = graph;
158 Hashtable<Taint, Set<Effect>> conflicts;
159 ReachGraph rg = oooa.getDisjointAnalysis().getReachGraph(currentSESE.getmdEnclosing());
161 rg.writeGraph("RCR_RG_STALLSITE_DEBUG");
163 if ((conflictGraph != null) && (conflicts = graph.getConflictEffectSet(fn)) != null
165 addToTraverseToDoList(fn, waitingElement.getTempDesc(), rg, conflicts);
172 buildEffectsLookupStructure();
178 * 1) Get global effects and conflicts
179 * 2) Create a hash structure (EffectsTable) to manage effects (hashed by affected Allocsite, then taint, then field)
180 * 2a) Use Effects to verify we can access something (reads)
181 * 2b) Use conflicts to mark conflicts (read/write/strongupdate)
182 * 2c) At second level of hash, store Heaproots that can cause conflicts at the field
183 * 3) Walk hash structure to identify and enumerate weakly connected groups and generate waiting queue slots.
184 * 4) Build internal representation of the rgs (pruned)
185 * 5) Print c methods by walking internal representation
188 public void addToTraverseToDoList(FlatSESEEnterNode rblock, ReachGraph rg, Hashtable<Taint, Set<Effect>> conflicts) {
190 toTraverse.add(new TraversalInfo(rblock, rg));
192 //Add to Global conflicts
193 for(Taint t: conflicts.keySet()) {
194 if(globalConflicts.containsKey(t)) {
195 globalConflicts.get(t).addAll(conflicts.get(t));
197 globalConflicts.put(t, conflicts.get(t));
203 public void addToTraverseToDoList(FlatNode fn, TempDescriptor tempDesc,
204 ReachGraph rg, Hashtable<Taint, Set<Effect>> conflicts) {
205 toTraverse.add(new TraversalInfo(fn, rg, tempDesc));
207 for(Taint t: conflicts.keySet()) {
208 if(globalConflicts.containsKey(t)) {
209 globalConflicts.get(t).addAll(conflicts.get(t));
211 globalConflicts.put(t, conflicts.get(t));
216 private void traverseSESEBlock(FlatSESEEnterNode rblock, ReachGraph rg) {
217 Collection<TempDescriptor> inVars = rblock.getInVarSet();
219 if (inVars.size() == 0)
221 System.out.println("RBLOCK:"+rblock);
222 System.out.println("["+inVars+"]");
224 // For every non-primitive variable, generate unique method
225 for (TempDescriptor invar : inVars) {
226 TypeDescriptor type = invar.getType();
227 if(type.isPrimitive()) {
230 System.out.println(invar);
231 //created stores nodes with specific alloc sites that have been traversed while building
232 //internal data structure. It is later traversed sequentially to find inset variables and
234 //NOTE: Integer stores Allocation Site ID in hashtable
235 Hashtable<Integer, ConcreteRuntimeObjNode> created = new Hashtable<Integer, ConcreteRuntimeObjNode>();
236 VariableNode varNode = rg.getVariableNodeNoMutation(invar);
237 Taint taint = getProperTaintForFlatSESEEnterNode(rblock, varNode, globalEffects);
239 printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + rblock.toPrettyString());
243 //This is to prevent duplicate traversals from being generated
244 if(doneTaints.containsKey(taint))
247 doneTaints.put(taint, traverserIDCounter++);
248 createConcreteGraph(effectsLookupTable, created, varNode, taint);
251 //This will add the taint to the printout, there will be NO duplicates (checked above)
252 if(!created.isEmpty()) {
253 for(Iterator<ConcreteRuntimeObjNode> it=created.values().iterator();it.hasNext();) {
254 ConcreteRuntimeObjNode obj=it.next();
255 if (obj.hasPrimitiveConflicts()||obj.decendantsConflict()) {
256 rblock.addInVarForDynamicCoarseConflictResolution(invar);
261 pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created));
266 private void traverseStallSite(FlatNode enterNode, TempDescriptor invar, ReachGraph rg) {
267 TypeDescriptor type = invar.getType();
268 if(type == null || type.isPrimitive()) {
272 Hashtable<Integer, ConcreteRuntimeObjNode> created = new Hashtable<Integer, ConcreteRuntimeObjNode>();
273 VariableNode varNode = rg.getVariableNodeNoMutation(invar);
274 Taint taint = getProperTaintForEnterNode(enterNode, varNode, globalEffects);
277 printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + enterNode.toString());
281 if(doneTaints.containsKey(taint))
284 doneTaints.put(taint, traverserIDCounter++);
285 createConcreteGraph(effectsLookupTable, created, varNode, taint);
287 if (!created.isEmpty()) {
288 pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created));
292 public String getTraverserInvocation(TempDescriptor invar, String varString, FlatNode fn) {
294 if(fn instanceof FlatSESEEnterNode) {
295 flatname = ((FlatSESEEnterNode) fn).getPrettyIdentifier();
297 flatname = fn.toString();
300 return "traverse___" + invar.getSafeSymbol() +
301 removeInvalidChars(flatname) + "___("+varString+");";
304 public int getTraverserID(TempDescriptor invar, FlatNode fn) {
305 Tuple t=new Tuple(invar, fn);
306 if (idMap.containsKey(t))
307 return idMap.get(t).intValue();
308 int value=currentID++;
309 idMap.put(t, new Integer(value));
313 public String removeInvalidChars(String in) {
314 StringBuilder s = new StringBuilder(in);
315 for(int i = 0; i < s.length(); i++) {
316 if(s.charAt(i) == ' ' || s.charAt(i) == '.' || s.charAt(i) == '='||s.charAt(i)=='['||s.charAt(i)==']') {
324 public void close() {
325 //prints out all generated code
326 for(TaintAndInternalHeapStructure ths: pendingPrintout) {
327 printCMethod(ths.nodesInHeap, ths.t);
330 //Prints out the master traverser Invocation that'll call all other traversers
331 //based on traverserID
332 printMasterTraverserInvocation();
333 printResumeTraverserInvocation();
335 //TODO this is only temporary, remove when thread local vars implemented.
336 createMasterHashTableArray();
338 // Adds Extra supporting methods
339 cFile.println("void initializeStructsRCR() {\n " + mallocVisitedHashtable + ";\n " + clearQueue + ";\n}");
340 cFile.println("void destroyRCR() {\n " + deallocVisitedHashTable + ";\n}");
342 headerFile.println("void initializeStructsRCR();\nvoid destroyRCR();");
343 headerFile.println("#endif\n");
349 //Builds Effects Table and runs the analysis on them to get weakly connected HRs
350 //SPECIAL NOTE: Only runs after we've taken all the conflicts and effects
351 private void buildEffectsLookupStructure(){
352 effectsLookupTable = new EffectsTable(globalEffects, globalConflicts);
353 effectsLookupTable.runAnalysis();
354 enumerateHeaproots();
357 private void runAllTraversals() {
358 for(TraversalInfo t: toTraverse) {
359 printDebug(javaDebug, "Running Traversal a traversal on " + t.f);
361 if(t.f instanceof FlatSESEEnterNode) {
362 traverseSESEBlock((FlatSESEEnterNode)t.f, t.rg);
364 if(t.invar == null) {
365 System.out.println("RCR ERROR: Attempted to run a stall site traversal with NO INVAR");
367 traverseStallSite(t.f, t.invar, t.rg);
374 //TODO: This is only temporary, remove when thread local variables are functional.
375 private void createMasterHashTableArray() {
376 headerFile.println("void createAndFillMasterHashStructureArray();");
377 cFile.println("void createAndFillMasterHashStructureArray() {\n" +
378 " rcr_createMasterHashTableArray("+weaklyConnectedHRCounter + ");");
380 for(int i = 0; i < weaklyConnectedHRCounter; i++) {
381 cFile.println(" allHashStructures["+i+"] = (HashStructure *) rcr_createHashtable("+num2WeaklyConnectedHRGroup.get(i).connectedHRs.size()+");");
386 private void printMasterTraverserInvocation() {
387 headerFile.println("\nint tasktraverse(SESEcommon * record);");
388 cFile.println("\nint tasktraverse(SESEcommon * record) {");
389 cFile.println(" if(!CAS(&record->rcrstatus,1,2)) return;");
390 cFile.println(" switch(record->classID) {");
392 for(Iterator<FlatSESEEnterNode> seseit=oooa.getAllSESEs().iterator();seseit.hasNext();) {
393 FlatSESEEnterNode fsen=seseit.next();
394 cFile.println( " /* "+fsen.getPrettyIdentifier()+" */");
395 cFile.println( " case "+fsen.getIdentifier()+": {");
396 cFile.println( " "+fsen.getSESErecordName()+" * rec=("+fsen.getSESErecordName()+" *) record;");
397 Vector<TempDescriptor> invars=fsen.getInVarsForDynamicCoarseConflictResolution();
398 for(int i=0;i<invars.size();i++) {
399 TempDescriptor tmp=invars.get(i);
400 cFile.println(" " + this.getTraverserInvocation(tmp, "rec->"+tmp+", rec", fsen));
402 cFile.println( " }");
403 cFile.println( " break;");
406 for(Taint t: doneTaints.keySet()) {
407 if (t.isStallSiteTaint()){
408 cFile.println( " case -" + getTraverserID(t.getVar(), t.getStallSite())+ ": {");
409 cFile.println( " SESEstall * rec=(SESEstall*) record;");
410 cFile.println( " " + this.getTraverserInvocation(t.getVar(), "rec->___obj___, rec", t.getStallSite())+";");
411 cFile.println( " }");
412 cFile.println(" break;");
416 cFile.println(" default:\n printf(\"Invalid SESE ID was passed in.\\n\");\n break;");
423 //This will print the traverser invocation that takes in a traverserID and starting ptr
424 private void printResumeTraverserInvocation() {
425 headerFile.println("\nint traverse(void * startingPtr, SESEcommon * record, int traverserID);");
426 cFile.println("\nint traverse(void * startingPtr, SESEcommon *record, int traverserID) {");
427 cFile.println(" switch(traverserID) {");
429 for(Taint t: doneTaints.keySet()) {
430 cFile.println(" case " + doneTaints.get(t)+ ":");
431 if(t.isRBlockTaint()) {
432 cFile.println(" " + this.getTraverserInvocation(t.getVar(), "startingPtr, ("+t.getSESE().getSESErecordName()+" *)record", t.getSESE()));
433 } else if (t.isStallSiteTaint()){
434 cFile.println("/* " + this.getTraverserInvocation(t.getVar(), "startingPtr, record", t.getStallSite())+"*/");
436 System.out.println("RuntimeConflictResolver encountered a taint that is neither SESE nor stallsite: " + t);
438 cFile.println(" break;");
441 if(RuntimeConflictResolver.cSideDebug) {
442 cFile.println(" default:\n printf(\"Invalid traverser ID %u was passed in.\\n\", traverserID);\n break;");
444 cFile.println(" default:\n break;");
451 private void createConcreteGraph(
453 Hashtable<Integer, ConcreteRuntimeObjNode> created,
454 VariableNode varNode,
457 // if table is null that means there's no conflicts, therefore we need not
458 // create a traversal
462 Iterator<RefEdge> possibleEdges = varNode.iteratorToReferencees();
463 while (possibleEdges.hasNext()) {
464 RefEdge edge = possibleEdges.next();
467 ConcreteRuntimeObjNode singleRoot = new ConcreteRuntimeObjNode(edge.getDst(), true, false);
468 int rootKey = singleRoot.allocSite.getUniqueAllocSiteID();
470 if (!created.containsKey(rootKey)) {
471 created.put(rootKey, singleRoot);
472 createHelper(singleRoot, edge.getDst().iteratorToReferencees(), created, table, t);
477 // Plan is to add stuff to the tree depth-first sort of way. That way, we can
478 // propagate up conflicts
479 private void createHelper(ConcreteRuntimeObjNode curr,
480 Iterator<RefEdge> edges,
481 Hashtable<Integer, ConcreteRuntimeObjNode> created,
484 assert table != null;
485 AllocSite parentKey = curr.allocSite;
486 EffectsGroup currEffects = table.getEffects(parentKey, taint);
488 if (currEffects == null || currEffects.isEmpty())
491 //Handle Objects (and primitives if child is new)
492 if(currEffects.hasObjectEffects()) {
493 while(edges.hasNext()) {
494 RefEdge edge = edges.next();
495 String field = edge.getField();
496 CombinedObjEffects effectsForGivenField = currEffects.getObjEffect(field);
497 //If there are no effects, then there's no point in traversing this edge
498 if(effectsForGivenField != null) {
499 HeapRegionNode childHRN = edge.getDst();
500 int childKey = childHRN.getAllocSite().getUniqueAllocSiteID();
501 boolean isNewChild = !created.containsKey(childKey);
502 ConcreteRuntimeObjNode child;
505 child = new ConcreteRuntimeObjNode(childHRN, false, curr.isObjectArray());
506 created.put(childKey, child);
508 child = created.get(childKey);
511 curr.addObjChild(field, child, effectsForGivenField);
513 if (effectsForGivenField.hasConflict()) {
514 child.hasPotentialToBeIncorrectDueToConflict = true;
515 propagateObjConflict(curr, child);
518 if(effectsForGivenField.hasReadEffect) {
519 child.addReachableParent(curr);
521 //If isNewChild, flag propagation will be handled at recursive call
523 createHelper(child, childHRN.iteratorToReferencees(), created, table, taint);
525 //This makes sure that all conflicts below the child is propagated up the referencers.
526 if(child.decendantsPrimConflict || child.hasPrimitiveConflicts()) {
527 propagatePrimConflict(child, child.enqueueToWaitingQueueUponConflict);
530 if(child.decendantsObjConflict) {
531 propagateObjConflict(child, child.enqueueToWaitingQueueUponConflict);
540 curr.primitiveConflictingFields = currEffects.primitiveConflictingFields;
541 if(currEffects.hasPrimitiveConflicts()) {
542 //Reminder: primitive conflicts are abstracted to object.
543 propagatePrimConflict(curr, curr);
547 // This will propagate the conflict up the data structure.
548 private void propagateObjConflict(ConcreteRuntimeObjNode curr, HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
549 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
550 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer
551 (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess))) // case where referencer has never seen possible unresolved referencee below
553 referencer.decendantsObjConflict = true;
554 propagateObjConflict(referencer, pointsOfAccess);
559 private void propagateObjConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) {
560 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
561 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer
562 (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess))) // case where referencer has never seen possible unresolved referencee below
564 referencer.decendantsObjConflict = true;
565 propagateObjConflict(referencer, pointOfAccess);
570 private void propagatePrimConflict(ConcreteRuntimeObjNode curr, HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
571 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
572 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above
573 (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess)))
575 referencer.decendantsPrimConflict = true;
576 propagatePrimConflict(referencer, pointsOfAccess);
581 private void propagatePrimConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) {
582 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
583 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above
584 (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess)))
586 referencer.decendantsPrimConflict = true;
587 propagatePrimConflict(referencer, pointOfAccess);
593 * This method generates a C method for every inset variable and rblock.
595 * The C method works by generating a large switch statement that will run the appropriate
596 * checking code for each object based on its allocation site. The switch statement is
597 * surrounded by a while statement which dequeues objects to be checked from a queue. An
598 * object is added to a queue only if it contains a conflict (in itself or in its referencees)
599 * and we came across it while checking through it's referencer. Because of this property,
600 * conflicts will be signaled by the referencer; the only exception is the inset variable which can
601 * signal a conflict within itself.
604 private void printCMethod(Hashtable<Integer, ConcreteRuntimeObjNode> created, Taint taint) {
605 String inVar = taint.getVar().getSafeSymbol();
608 if(taint.isStallSiteTaint()) {
609 rBlock = taint.getStallSite().toString();
610 } else if(taint.isRBlockTaint()) {
611 rBlock = taint.getSESE().getPrettyIdentifier();
613 System.out.println("RCR CRITICAL ERROR: TAINT IS NEITHER A STALLSITE NOR SESE! " + taint.toString());
617 //This hash table keeps track of all the case statements generated.
618 Hashtable<AllocSite, StringBuilder> cases = new Hashtable<AllocSite, StringBuilder>();
621 for (ConcreteRuntimeObjNode node : created.values()) {
622 printDebug(javaDebug, "Considering " + node.allocSite + " for traversal");
623 if (!cases.containsKey(node.allocSite) && qualifiesForCaseStatement(node)) {
624 printDebug(javaDebug, "+\t" + node.allocSite + " qualified for case statement");
625 addChecker(taint, node, cases, null, "ptr", 0);
632 if (taint.isStallSiteTaint()) {
633 methodName= "void traverse___" + inVar + removeInvalidChars(rBlock) + "___(void * InVar, SESEstall *record)";
635 methodName= "void traverse___" + inVar + removeInvalidChars(rBlock) + "___(void * InVar, "+taint.getSESE().getSESErecordName() +" *record)";
636 FlatSESEEnterNode fsese=taint.getSESE();
637 TempDescriptor tmp=taint.getVar();
638 index=fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp);
641 cFile.println(methodName + " {");
642 headerFile.println(methodName + ";");
645 cFile.println("printf(\"The traverser ran for " + methodName + "\\n\");");
648 if(cases.size() == 0) {
649 cFile.println(" return;");
651 cFile.println(" int totalcount=RUNBIAS;\n");
653 if (taint.isStallSiteTaint()) {
654 cFile.println(" record->rcrRecords[0].count=RUNBIAS;\n");
656 cFile.println(" record->rcrRecords["+index+"].count=RUNBIAS;\n");
657 cFile.println(" record->rcrRecords["+index+"].index=0;\n");
660 //clears queue and hashtable that keeps track of where we've been.
661 cFile.println(clearQueue + ";\n" + resetVisitedHashTable + ";");
662 //generic cast to ___Object___ to access ptr->allocsite field.
663 cFile.println("struct ___Object___ * ptr = (struct ___Object___ *) InVar;\nif (InVar != NULL) {\n " + queryVistedHashtable + "(ptr);\n do {");
664 if (taint.isRBlockTaint()) {
665 cFile.println(" if(unlikely(record->common.doneExecuting)) {");
666 cFile.println(" record->common.rcrstatus=0;");
667 cFile.println(" return;");
670 cFile.println(" switch(ptr->allocsite) {");
672 for(AllocSite singleCase: cases.keySet()) {
673 cFile.append(cases.get(singleCase));
676 cFile.println(" default:\n break; ");
677 cFile.println(" }\n } while((ptr = " + dequeueFromQueueInC + ") != NULL);\n}");
679 if (taint.isStallSiteTaint()) {
681 cFile.println(" if(atomic_sub_and_test(RUNBIAS-totalcount,&(record->rcrRecords[0].count))) {");
682 cFile.println(" psem_give_tag(record->common.parentsStallSem, record->tag);");
683 cFile.println(" BARRIER();");
684 cFile.println(" record->common.rcrstatus=0;");
687 cFile.println(" if(atomic_sub_and_test(RUNBIAS-totalcount,&(record->rcrRecords["+index+"].count))) {");
688 cFile.println(" int flag=LOCKXCHG32(&(record->rcrRecords["+index+"].flag),0);");
689 cFile.println(" if(flag) {");
690 //we have resolved a heap root...see if this was the last dependence
691 cFile.println(" if(atomic_sub_and_test(1, &(record->common.unresolvedDependencies))) workScheduleSubmit((void *)record);");
694 cFile.println(" record->common.rcrstatus=0;");
702 * addChecker creates a case statement for every object that is an inset variable, has more
703 * than 1 parent && has conflicts, or where resumes are possible (from waiting queue).
704 * See .qualifiesForCaseStatement
706 private void addChecker(Taint taint,
707 ConcreteRuntimeObjNode node,
708 Hashtable<AllocSite,StringBuilder> cases,
709 StringBuilder possibleContinuingCase,
712 StringBuilder currCase = possibleContinuingCase;
713 if(qualifiesForCaseStatement(node)) {
714 assert prefix.equals("ptr") && !cases.containsKey(node.allocSite);
715 currCase = new StringBuilder();
716 cases.put(node.allocSite, currCase);
717 currCase.append(" case " + node.getAllocationSite() + ": {\n");
719 //either currCase is continuing off a parent case or is its own.
720 assert currCase !=null;
722 boolean primConfRead=false;
723 boolean primConfWrite=false;
724 boolean objConfRead=false;
725 boolean objConfWrite=false;
728 for(String field: node.primitiveConflictingFields.keySet()) {
729 CombinedObjEffects effect=node.primitiveConflictingFields.get(field);
730 primConfRead|=effect.hasReadConflict;
731 primConfWrite|=effect.hasWriteConflict;
734 //Object Reference Test
735 for(String field: node.objectRefs.keySet()) {
736 for(ObjRef ref: node.objectRefs.get(field)) {
737 CombinedObjEffects effect=ref.myEffects;
738 objConfRead|=effect.hasReadConflict;
739 objConfWrite|=effect.hasWriteConflict;
744 if (taint.isRBlockTaint()) {
745 FlatSESEEnterNode fsese=taint.getSESE();
746 TempDescriptor tmp=taint.getVar();
747 index=fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp);
750 String strrcr=taint.isRBlockTaint()?"&record->rcrRecords["+index+"], ":"NULL, ";
752 //Do call if we need it.
753 if(primConfWrite||objConfWrite) {
754 int heaprootNum = connectedHRHash.get(taint).id;
755 assert heaprootNum != -1;
756 int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
757 int traverserID = doneTaints.get(taint);
758 currCase.append(" int tmpkey"+depth+"=rcr_generateKey("+prefix+");\n");
760 currCase.append(" int tmpvar"+depth+"=rcr_WTWRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+strrcr+index+");\n");
762 currCase.append(" int tmpvar"+depth+"=rcr_WRITEBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+strrcr+index+");\n");
763 } else if (primConfRead||objConfRead) {
764 int heaprootNum = connectedHRHash.get(taint).id;
765 assert heaprootNum != -1;
766 int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
767 int traverserID = doneTaints.get(taint);
768 currCase.append(" int tmpkey"+depth+"=rcr_generateKey("+prefix+");\n");
770 currCase.append(" int tmpvar"+depth+"=rcr_WTREADBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+strrcr+index+");\n");
772 currCase.append(" int tmpvar"+depth+"=rcr_READBINCASE(allHashStructures["+heaprootNum+"], tmpkey"+depth+", (SESEcommon *) record, "+strrcr+index+");\n");
775 if(primConfWrite||objConfWrite||primConfRead||objConfRead) {
776 currCase.append("if (!(tmpvar"+depth+"&READYMASK)) totalcount--;\n");
780 currCase.append("{\n");
782 if(node.isObjectArray() && node.decendantsConflict()) {
783 //since each array element will get its own case statement, we just need to enqueue each item into the queue
784 //note that the ref would be the actual object and node would be of struct ArrayObject
786 ArrayList<Integer> allocSitesWithProblems = node.getReferencedAllocSites();
787 if(!allocSitesWithProblems.isEmpty()) {
788 String childPtr = "((struct ___Object___ **)(((char *) &(((struct ArrayObject *)"+ prefix+")->___length___))+sizeof(int)))[i]";
789 String currPtr = "arrayElement" + pdepth;
791 //This is done with the assumption that an array of object stores pointers.
792 currCase.append("{\n int i;\n");
793 currCase.append(" for(i = 0; i<((struct ArrayObject *) " + prefix + " )->___length___; i++ ) {\n");
794 currCase.append(" struct ___Object___ *"+currPtr+" = "+childPtr+";\n");
795 currCase.append(" if( arrayElement"+pdepth+" != NULL) {\n");
797 //There should be only one field, hence we only take the first field in the keyset.
798 assert node.objectRefs.keySet().size() <= 1;
799 ArrayList<ObjRef> refsAtParticularField = node.objectRefs.get(node.objectRefs.keySet().iterator().next());
800 printObjRefSwitchStatement(taint,cases,pdepth,currCase,refsAtParticularField,childPtr,currPtr);
801 currCase.append(" }}}\n");
805 for(String field: node.objectRefs.keySet()) {
806 ArrayList<ObjRef> refsAtParticularField = node.objectRefs.get(field);
807 String childPtr = "((struct "+node.original.getType().getSafeSymbol()+" *)"+prefix +")->___" + field + "___";
808 String currPtr = "myPtr" + pdepth;
809 currCase.append(" struct ___Object___ * "+currPtr+"= (struct ___Object___ * ) " + childPtr + ";\n");
810 currCase.append(" if (" + currPtr + " != NULL) { ");
812 printObjRefSwitchStatement(taint, cases, depth, currCase, refsAtParticularField, childPtr, currPtr);
813 currCase.append("}");
817 currCase.append("}\n"); //For particular top level case statement.
819 if(qualifiesForCaseStatement(node)) {
820 currCase.append(" }\n break;\n");
824 private void printObjRefSwitchStatement(Taint taint, Hashtable<AllocSite, StringBuilder> cases,
825 int pDepth, StringBuilder currCase, ArrayList<ObjRef> refsAtParticularField, String childPtr,
827 currCase.append(" switch(" + currPtr + getAllocSiteInC + ") {\n");
829 for(ObjRef ref: refsAtParticularField) {
830 if(ref.child.decendantsConflict() || ref.child.hasPrimitiveConflicts()) {
831 currCase.append(" case "+ref.allocSite+":\n {\n");
832 //The hash insert is here because we don't want to enqueue things unless we know it conflicts.
833 currCase.append(" if (" + queryVistedHashtable +"("+ currPtr + ")) {\n");
835 if (ref.child.getNumOfReachableParents() == 1 && !ref.child.isInsetVar) {
836 addChecker(taint, ref.child, cases, currCase, currPtr, pDepth + 1);
839 currCase.append(" " + addToQueueInC + childPtr + ");\n ");
841 currCase.append(" }\n"); //close for queryVistedHashtable
843 currCase.append("}\n"); //close for internal case statement
847 currCase.append(" default:\n" +
849 " }\n"); //internal switch.
852 private boolean qualifiesForCaseStatement(ConcreteRuntimeObjNode node) {
855 (node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
856 //non-inline-able code cases
857 (node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
858 //Cases where resumes are possible
859 (node.hasPotentialToBeIncorrectDueToConflict) && node.decendantsObjConflict);
862 private Taint getProperTaintForFlatSESEEnterNode(FlatSESEEnterNode rblock, VariableNode var,
863 Hashtable<Taint, Set<Effect>> effects) {
864 Set<Taint> taints = effects.keySet();
865 for (Taint t : taints) {
866 FlatSESEEnterNode sese = t.getSESE();
867 if(sese != null && sese.equals(rblock) && t.getVar().equals(var.getTempDescriptor())) {
875 private Taint getProperTaintForEnterNode(FlatNode stallSite, VariableNode var,
876 Hashtable<Taint, Set<Effect>> effects) {
877 Set<Taint> taints = effects.keySet();
878 for (Taint t : taints) {
879 FlatNode flatnode = t.getStallSite();
880 if(flatnode != null && flatnode.equals(stallSite) && t.getVar().equals(var.getTempDescriptor())) {
887 private void printDebug(boolean guard, String debugStatements) {
889 System.out.println(debugStatements);
892 private void enumerateHeaproots() {
893 weaklyConnectedHRCounter = 0;
894 num2WeaklyConnectedHRGroup = new ArrayList<WeaklyConectedHRGroup>();
896 for(Taint t: connectedHRHash.keySet()) {
897 if(connectedHRHash.get(t).id == -1) {
898 WeaklyConectedHRGroup hg = connectedHRHash.get(t);
899 hg.id = weaklyConnectedHRCounter;
900 num2WeaklyConnectedHRGroup.add(weaklyConnectedHRCounter, hg);
901 weaklyConnectedHRCounter++;
906 private void printoutTable(EffectsTable table) {
908 System.out.println("==============EFFECTS TABLE PRINTOUT==============");
909 for(AllocSite as: table.table.keySet()) {
910 System.out.println("\tFor AllocSite " + as.getUniqueAllocSiteID());
912 BucketOfEffects boe = table.table.get(as);
914 if(boe.potentiallyConflictingRoots != null && !boe.potentiallyConflictingRoots.isEmpty()) {
915 System.out.println("\t\tPotentially conflicting roots: ");
916 for(String key: boe.potentiallyConflictingRoots.keySet()) {
917 System.out.println("\t\t-Field: " + key);
918 System.out.println("\t\t\t" + boe.potentiallyConflictingRoots.get(key));
921 for(Taint t: boe.taint2EffectsGroup.keySet()) {
922 System.out.println("\t\t For Taint " + t);
923 EffectsGroup eg = boe.taint2EffectsGroup.get(t);
925 if(eg.hasPrimitiveConflicts()) {
926 System.out.print("\t\t\tPrimitive Conflicts at alloc " + as.getUniqueAllocSiteID() +" : ");
927 for(String field: eg.primitiveConflictingFields.keySet()) {
928 System.out.print(field + " ");
930 System.out.println();
932 for(String fieldKey: eg.myEffects.keySet()) {
933 CombinedObjEffects ce = eg.myEffects.get(fieldKey);
934 System.out.println("\n\t\t\tFor allocSite " + as.getUniqueAllocSiteID() + " && field " + fieldKey);
935 System.out.println("\t\t\t\tread " + ce.hasReadEffect + "/"+ce.hasReadConflict +
936 " write " + ce.hasWriteEffect + "/" + ce.hasWriteConflict +
937 " SU " + ce.hasStrongUpdateEffect + "/" + ce.hasStrongUpdateConflict);
938 for(Effect ef: ce.originalEffects) {
939 System.out.println("\t" + ef);
948 private class EffectsGroup {
949 Hashtable<String, CombinedObjEffects> myEffects;
950 Hashtable<String, CombinedObjEffects> primitiveConflictingFields;
952 public EffectsGroup() {
953 myEffects = new Hashtable<String, CombinedObjEffects>();
954 primitiveConflictingFields = new Hashtable<String, CombinedObjEffects>();
957 public void addPrimitive(Effect e, boolean conflict) {
958 CombinedObjEffects effects;
959 if((effects = primitiveConflictingFields.get(e.getField().getSymbol())) == null) {
960 effects = new CombinedObjEffects();
961 primitiveConflictingFields.put(e.getField().getSymbol(), effects);
963 effects.add(e, conflict);
966 public void addObjEffect(Effect e, boolean conflict) {
967 CombinedObjEffects effects;
968 if((effects = myEffects.get(e.getField().getSymbol())) == null) {
969 effects = new CombinedObjEffects();
970 myEffects.put(e.getField().getSymbol(), effects);
972 effects.add(e, conflict);
975 public boolean isEmpty() {
976 return myEffects.isEmpty() && primitiveConflictingFields.isEmpty();
979 public boolean hasPrimitiveConflicts(){
980 return !primitiveConflictingFields.isEmpty();
983 public CombinedObjEffects getPrimEffect(String field) {
984 return primitiveConflictingFields.get(field);
987 public boolean hasObjectEffects() {
988 return !myEffects.isEmpty();
991 public CombinedObjEffects getObjEffect(String field) {
992 return myEffects.get(field);
996 //Is the combined effects for all effects with the same affectedAllocSite and field
997 private class CombinedObjEffects {
998 ArrayList<Effect> originalEffects;
1000 public boolean hasReadEffect;
1001 public boolean hasWriteEffect;
1002 public boolean hasStrongUpdateEffect;
1004 public boolean hasReadConflict;
1005 public boolean hasWriteConflict;
1006 public boolean hasStrongUpdateConflict;
1009 public CombinedObjEffects() {
1010 originalEffects = new ArrayList<Effect>();
1012 hasReadEffect = false;
1013 hasWriteEffect = false;
1014 hasStrongUpdateEffect = false;
1016 hasReadConflict = false;
1017 hasWriteConflict = false;
1018 hasStrongUpdateConflict = false;
1021 public boolean add(Effect e, boolean conflict) {
1022 if(!originalEffects.add(e))
1025 switch(e.getType()) {
1027 hasReadEffect = true;
1028 hasReadConflict = conflict;
1031 hasWriteEffect = true;
1032 hasWriteConflict = conflict;
1034 case Effect.strongupdate:
1035 hasStrongUpdateEffect = true;
1036 hasStrongUpdateConflict = conflict;
1039 System.out.println("RCR ERROR: An Effect Type never seen before has been encountered");
1046 public boolean hasConflict() {
1047 return hasReadConflict || hasWriteConflict || hasStrongUpdateConflict;
1050 public void mergeWith(CombinedObjEffects other) {
1051 for(Effect e: other.originalEffects) {
1052 if(!originalEffects.contains(e)){
1053 originalEffects.add(e);
1057 hasReadEffect |= other.hasReadEffect;
1058 hasWriteEffect |= other.hasWriteEffect;
1059 hasStrongUpdateEffect |= other.hasStrongUpdateEffect;
1061 hasReadConflict |= other.hasReadConflict;
1062 hasWriteConflict |= other.hasWriteConflict;
1063 hasStrongUpdateConflict |= other.hasStrongUpdateConflict;
1067 //This will keep track of a reference
1068 private class ObjRef {
1071 CombinedObjEffects myEffects;
1073 //This keeps track of the parent that we need to pass by inorder to get
1074 //to the conflicting child (if there is one).
1075 ConcreteRuntimeObjNode child;
1077 public ObjRef(String fieldname,
1078 ConcreteRuntimeObjNode ref,
1079 CombinedObjEffects myEffects) {
1081 allocSite = ref.getAllocationSite();
1084 this.myEffects = myEffects;
1087 public boolean hasConflictsDownThisPath() {
1088 return child.decendantsObjConflict || child.decendantsPrimConflict || child.hasPrimitiveConflicts() || myEffects.hasConflict();
1091 public boolean hasDirectObjConflict() {
1092 return myEffects.hasConflict();
1095 public boolean equals(Object other) {
1096 if(other == null || !(other instanceof ObjRef))
1099 ObjRef o = (ObjRef) other;
1101 if(o.field == this.field && o.allocSite == this.allocSite && this.child.equals(o.child))
1107 public int hashCode() {
1108 return child.allocSite.hashCode() ^ field.hashCode();
1111 public void mergeWith(ObjRef ref) {
1112 myEffects.mergeWith(ref.myEffects);
1116 private class ConcreteRuntimeObjNode {
1117 Hashtable<String, ArrayList<ObjRef>> objectRefs;
1118 Hashtable<String, CombinedObjEffects> primitiveConflictingFields;
1119 HashSet<ConcreteRuntimeObjNode> parentsWithReadToNode;
1120 HashSet<ConcreteRuntimeObjNode> parentsThatWillLeadToConflicts;
1121 //this set keeps track of references down the line that need to be enqueued if traverser is "paused"
1122 HashSet<ConcreteRuntimeObjNode> enqueueToWaitingQueueUponConflict;
1123 boolean decendantsPrimConflict;
1124 boolean decendantsObjConflict;
1125 boolean hasPotentialToBeIncorrectDueToConflict;
1127 boolean isArrayElement;
1128 AllocSite allocSite;
1129 HeapRegionNode original;
1131 public ConcreteRuntimeObjNode(HeapRegionNode me, boolean isInVar, boolean isArrayElement) {
1132 objectRefs = new Hashtable<String, ArrayList<ObjRef>>(5);
1133 primitiveConflictingFields = null;
1134 parentsThatWillLeadToConflicts = new HashSet<ConcreteRuntimeObjNode>();
1135 parentsWithReadToNode = new HashSet<ConcreteRuntimeObjNode>();
1136 enqueueToWaitingQueueUponConflict = new HashSet<ConcreteRuntimeObjNode>();
1137 allocSite = me.getAllocSite();
1139 isInsetVar = isInVar;
1140 decendantsPrimConflict = false;
1141 decendantsObjConflict = false;
1142 hasPotentialToBeIncorrectDueToConflict = false;
1143 this.isArrayElement = isArrayElement;
1146 public void addReachableParent(ConcreteRuntimeObjNode curr) {
1147 parentsWithReadToNode.add(curr);
1151 public boolean equals(Object other) {
1152 if(other == null || !(other instanceof ConcreteRuntimeObjNode))
1155 return original.equals(((ConcreteRuntimeObjNode)other).original);
1158 public int getAllocationSite() {
1159 return allocSite.getUniqueAllocSiteID();
1162 public int getNumOfReachableParents() {
1163 return parentsThatWillLeadToConflicts.size();
1166 public boolean hasPrimitiveConflicts() {
1167 return primitiveConflictingFields != null && !primitiveConflictingFields.isEmpty();
1170 public boolean decendantsConflict() {
1171 return decendantsPrimConflict || decendantsObjConflict;
1175 //returns true if at least one of the objects in points of access has been added
1176 public boolean addPossibleWaitingQueueEnqueue(HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
1177 boolean addedNew = false;
1178 for(ConcreteRuntimeObjNode dec: pointsOfAccess) {
1179 if(dec != null && dec != this){
1180 addedNew = addedNew || enqueueToWaitingQueueUponConflict.add(dec);
1187 public boolean addPossibleWaitingQueueEnqueue(ConcreteRuntimeObjNode pointOfAccess) {
1188 if(pointOfAccess != null && pointOfAccess != this){
1189 return enqueueToWaitingQueueUponConflict.add(pointOfAccess);
1195 public void addObjChild(String field, ConcreteRuntimeObjNode child, CombinedObjEffects ce) {
1196 printDebug(javaDebug,this.allocSite.getUniqueAllocSiteID() + " added child at " + child.getAllocationSite());
1197 ObjRef ref = new ObjRef(field, child, ce);
1199 if(objectRefs.containsKey(field)){
1200 ArrayList<ObjRef> array = objectRefs.get(field);
1202 if(array.contains(ref)) {
1203 ObjRef other = array.get(array.indexOf(ref));
1204 other.mergeWith(ref);
1205 printDebug(javaDebug," Merged with old");
1206 printDebug(javaDebug," Old="+ other.child.original + "\n new="+ref.child.original);
1210 printDebug(javaDebug," Just added new;\n Field: " + field);
1211 printDebug(javaDebug," AllocSite: " + child.getAllocationSite());
1212 printDebug(javaDebug," Child: "+child.original);
1216 ArrayList<ObjRef> array = new ArrayList<ObjRef>(3);
1219 objectRefs.put(field, array);
1223 public boolean isObjectArray() {
1224 return original.getType().isArray() && !original.getType().isPrimitive() && !original.getType().isImmutable();
1227 public boolean canBeArrayElement() {
1228 return isArrayElement;
1231 public ArrayList<Integer> getReferencedAllocSites() {
1232 ArrayList<Integer> list = new ArrayList<Integer>();
1234 for(String key: objectRefs.keySet()) {
1235 for(ObjRef r: objectRefs.get(key)) {
1236 if(r.hasDirectObjConflict() || (r.child.parentsWithReadToNode.contains(this) && r.hasConflictsDownThisPath())) {
1237 list.add(r.allocSite);
1245 public String toString() {
1246 return "AllocSite=" + getAllocationSite() + " myConflict=" + !parentsThatWillLeadToConflicts.isEmpty() +
1247 " decCon="+decendantsObjConflict+
1248 " NumOfConParents=" + getNumOfReachableParents() + " ObjectChildren=" + objectRefs.size();
1252 private class EffectsTable {
1253 private Hashtable<AllocSite, BucketOfEffects> table;
1255 public EffectsTable(Hashtable<Taint, Set<Effect>> effects,
1256 Hashtable<Taint, Set<Effect>> conflicts) {
1257 table = new Hashtable<AllocSite, BucketOfEffects>();
1259 // rehash all effects (as a 5-tuple) by their affected allocation site
1260 for (Taint t : effects.keySet()) {
1261 Set<Effect> localConflicts = conflicts.get(t);
1262 for (Effect e : effects.get(t)) {
1263 BucketOfEffects bucket;
1264 if ((bucket = table.get(e.getAffectedAllocSite())) == null) {
1265 bucket = new BucketOfEffects();
1266 table.put(e.getAffectedAllocSite(), bucket);
1268 printDebug(javaDebug, "Added Taint" + t + " Effect " + e + "Conflict Status = " + (localConflicts!=null?localConflicts.contains(e):false)+" localConflicts = "+localConflicts);
1269 bucket.add(t, e, localConflicts!=null?localConflicts.contains(e):false);
1274 public EffectsGroup getEffects(AllocSite parentKey, Taint taint) {
1275 //This would get the proper bucket of effects and then get all the effects
1276 //for a parent for a specific taint
1278 return table.get(parentKey).taint2EffectsGroup.get(taint);
1280 catch (NullPointerException e) {
1285 // Run Analysis will walk the data structure and figure out the weakly
1286 // connected heap roots.
1287 public void runAnalysis() {
1289 printoutTable(this);
1292 for(AllocSite key: table.keySet()) {
1293 BucketOfEffects effects = table.get(key);
1294 //make sure there are actually conflicts in the bucket
1295 if(effects.potentiallyConflictingRoots != null && !effects.potentiallyConflictingRoots.isEmpty()){
1296 for(String field: effects.potentiallyConflictingRoots.keySet()){
1297 ArrayList<Taint> taints = effects.potentiallyConflictingRoots.get(field);
1298 //For simplicity, we just create a new group and add everything to it instead of
1299 //searching through all of them for the largest group and adding everyone in.
1300 WeaklyConectedHRGroup group = new WeaklyConectedHRGroup();
1301 group.add(taints); //This will automatically add the taint to the connectedHRhash
1308 private class WeaklyConectedHRGroup {
1309 HashSet<Taint> connectedHRs;
1310 //This is to keep track of unique waitingQueue positions for each allocsite.
1311 Hashtable<AllocSite, Integer> allocSiteToWaitingQueueMap;
1312 int waitingQueueCounter;
1315 public WeaklyConectedHRGroup() {
1316 connectedHRs = new HashSet<Taint>();
1317 id = -1; //this will be later modified
1318 waitingQueueCounter = 0;
1319 allocSiteToWaitingQueueMap = new Hashtable<AllocSite, Integer>();
1322 public void add(ArrayList<Taint> list) {
1323 for(Taint t: list) {
1328 public int getWaitingQueueBucketNum(ConcreteRuntimeObjNode node) {
1329 if(allocSiteToWaitingQueueMap.containsKey(node.allocSite)) {
1330 return allocSiteToWaitingQueueMap.get(node.allocSite);
1332 allocSiteToWaitingQueueMap.put(node.allocSite, waitingQueueCounter);
1333 return waitingQueueCounter++;
1337 public void add(Taint t) {
1338 connectedHRs.add(t);
1339 WeaklyConectedHRGroup oldGroup = connectedHRHash.get(t);
1340 connectedHRHash.put(t, this); //put new group into hash
1341 //If the taint was already in another group, move all its buddies over.
1342 if(oldGroup != this && oldGroup != null) {
1343 Iterator<Taint> it = oldGroup.connectedHRs.iterator();
1346 while((relatedTaint = it.next()) != null && !connectedHRs.contains(relatedTaint)) {
1347 this.add(relatedTaint);
1353 //This is a class that stores all the effects for an affected allocation site
1354 //across ALL taints. The structure is a hashtable of EffectGroups (see above) hashed
1355 //by a Taint. This way, I can keep EffectsGroups so I can reuse most to all of my old code
1356 //and allows for easier tracking of effects. In addition, a hashtable (keyed by the string
1357 //of the field access) keeps track of an ArrayList of taints of SESEblocks that conflict on that
1359 private class BucketOfEffects {
1360 // This table is used for lookup while creating the traversal.
1361 Hashtable<Taint, EffectsGroup> taint2EffectsGroup;
1363 //This table is used to help identify weakly connected groups: Contains ONLY
1364 //conflicting effects AND is only initialized when needed
1365 //String stores the field
1366 Hashtable<String, ArrayList<Taint>> potentiallyConflictingRoots;
1368 public BucketOfEffects() {
1369 taint2EffectsGroup = new Hashtable<Taint, EffectsGroup>();
1372 public void add(Taint t, Effect e, boolean conflict) {
1373 EffectsGroup effectsForGivenTaint;
1375 if ((effectsForGivenTaint = taint2EffectsGroup.get(t)) == null) {
1376 effectsForGivenTaint = new EffectsGroup();
1377 taint2EffectsGroup.put(t, effectsForGivenTaint);
1380 if (e.getField().getType().isPrimitive()) {
1382 effectsForGivenTaint.addPrimitive(e, true);
1385 effectsForGivenTaint.addObjEffect(e, conflict);
1389 if(potentiallyConflictingRoots == null) {
1390 potentiallyConflictingRoots = new Hashtable<String, ArrayList<Taint>>();
1393 ArrayList<Taint> taintsForField = potentiallyConflictingRoots.get(e.getField().getSafeSymbol());
1394 if(taintsForField == null) {
1395 taintsForField = new ArrayList<Taint>();
1396 potentiallyConflictingRoots.put(e.getField().getSafeSymbol(), taintsForField);
1399 if(!taintsForField.contains(t)) {
1400 taintsForField.add(t);
1406 private class TaintAndInternalHeapStructure {
1408 public Hashtable<Integer, ConcreteRuntimeObjNode> nodesInHeap;
1410 public TaintAndInternalHeapStructure(Taint taint, Hashtable<Integer, ConcreteRuntimeObjNode> nodesInHeap) {
1412 this.nodesInHeap = nodesInHeap;
1416 private class TraversalInfo {
1418 public ReachGraph rg;
1419 public TempDescriptor invar;
1421 public TraversalInfo(FlatNode fn, ReachGraph g) {
1427 public TraversalInfo(FlatNode fn, ReachGraph rg2, TempDescriptor tempDesc) {