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;
12 import Analysis.Disjoint.*;
13 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 = false;
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<Taint, Set<Effect>> globalEffects;
41 private Hashtable<Taint, Set<Effect>> globalConflicts;
42 private ArrayList<TraversalInfo> toTraverse;
44 // initializing variables can be found in printHeader()
45 private static final String getAllocSiteInC = "->allocsite";
46 private static final String queryVistedHashtable = "hashRCRInsert";
47 private static final String addToQueueInC = "enqueueRCRQueue(";
48 private static final String dequeueFromQueueInC = "dequeueRCRQueue()";
49 private static final String clearQueue = "resetRCRQueue()";
50 // Make hashtable; hashRCRCreate(unsigned int size, double loadfactor)
51 private static final String mallocVisitedHashtable = "hashRCRCreate(128, 0.75)";
52 private static final String deallocVisitedHashTable = "hashRCRDelete()";
53 private static final String resetVisitedHashTable = "hashRCRreset()";
55 //TODO find correct strings for these
56 private static final String addCheckFromHashStructure = "checkFromHashStructure(";
57 private static final String putWaitingQueueBlock = "putWaitingQueueBlock("; //lifting of blocks will be done by hashtable.
58 private static final String putIntoAllocQueue = "putIntoWaitingQ(";
59 private static final int noConflict = 0;
60 private static final int conflictButTraverserCanContinue = 1;
61 private static final int conflictButTraverserCannotContinue = 2;
62 private static final int allocQueueIsNotEmpty = 0;
64 // Hashtable provides fast access to heaproot # lookups
65 private Hashtable<Taint, WeaklyConectedHRGroup> connectedHRHash;
66 private ArrayList<WeaklyConectedHRGroup> num2WeaklyConnectedHRGroup;
67 private int traverserIDCounter;
68 private int weaklyConnectedHRCounter;
69 private ArrayList<TaintAndInternalHeapStructure> pendingPrintout;
70 private EffectsTable effectsLookupTable;
71 private OoOJavaAnalysis oooa;
73 public RuntimeConflictResolver(String buildir, OoOJavaAnalysis oooa) throws FileNotFoundException {
74 String outputFile = buildir + "RuntimeConflictResolver";
77 cFile = new PrintWriter(new File(outputFile + ".c"));
78 headerFile = new PrintWriter(new File(outputFile + ".h"));
80 cFile.println("#include \"" + hashAndQueueCFileDir + "hashRCR.h\"\n#include \""
81 + hashAndQueueCFileDir + "Queue_RCR.h\"\n#include <stdlib.h>");
82 cFile.println("#include \"classdefs.h\"");
83 cFile.println("#include \"structdefs.h\"");
84 cFile.println("#include \"mlp_runtime.h\"");
85 cFile.println("#include \"RuntimeConflictResolver.h\"");
86 cFile.println("#include \"hashStructure.h\"");
88 headerFile.println("#ifndef __3_RCR_H_");
89 headerFile.println("#define __3_RCR_H_");
91 doneTaints = new Hashtable<Taint, Integer>();
92 connectedHRHash = new Hashtable<Taint, WeaklyConectedHRGroup>();
94 traverserIDCounter = 1;
95 weaklyConnectedHRCounter = 0;
96 pendingPrintout = new ArrayList<TaintAndInternalHeapStructure>();
97 toTraverse = new ArrayList<TraversalInfo>();
98 globalConflicts = new Hashtable<Taint, Set<Effect>>();
99 //Note: globalEffects is not instantiated since it'll be passed in whole while conflicts comes in chunks
102 public void setGlobalEffects(Hashtable<Taint, Set<Effect>> effects) {
103 globalEffects = effects;
106 System.out.println("============EFFECTS LIST AS PASSED IN============");
107 for(Taint t: globalEffects.keySet()) {
108 System.out.println("For Taint " + t);
109 for(Effect e: globalEffects.get(t)) {
110 System.out.println("\t" + e);
113 System.out.println("====================END LIST====================");
118 //Go through the SESE's
119 for(Iterator<FlatSESEEnterNode> seseit=oooa.getAllSESEs().iterator();seseit.hasNext();) {
120 FlatSESEEnterNode fsen=seseit.next();
121 Analysis.OoOJava.ConflictGraph conflictGraph;
122 Hashtable<Taint, Set<Effect>> conflicts;
123 System.out.println("-------");
124 System.out.println(fsen);
125 System.out.println(fsen.getIsCallerSESEplaceholder());
126 System.out.println(fsen.getParent());
128 if (fsen.getParent()!=null) {
129 conflictGraph = oooa.getConflictGraph(fsen.getParent());
130 System.out.println("CG="+conflictGraph);
131 if (conflictGraph!=null)
132 System.out.println("Conflicts="+conflictGraph.getConflictEffectSet(fsen));
135 if(!fsen.getIsCallerSESEplaceholder() && fsen.getParent()!=null &&
136 (conflictGraph = oooa.getConflictGraph(fsen.getParent())) != null &&
137 (conflicts = conflictGraph.getConflictEffectSet(fsen)) != null) {
138 FlatMethod fm=fsen.getfmEnclosing();
139 ReachGraph rg=oooa.getDisjointAnalysis().getReachGraph(fm.getMethod());
141 rg.writeGraph("RCR_RG_SESE_DEBUG");
143 addToTraverseToDoList(fsen, rg, conflicts);
146 //Go through the stall sites
147 for(Iterator<FlatNode> codeit=oooa.getNodesWithPlans().iterator();codeit.hasNext();) {
148 FlatNode fn=codeit.next();
149 CodePlan cp=oooa.getCodePlan(fn);
150 FlatSESEEnterNode currentSESE=cp.getCurrentSESE();
151 Analysis.OoOJava.ConflictGraph graph = oooa.getConflictGraph(currentSESE);
154 Set<Analysis.OoOJava.SESELock> seseLockSet = oooa.getLockMappings(graph);
155 Set<Analysis.OoOJava.WaitingElement> waitingElementSet =
156 graph.getStallSiteWaitingElementSet(fn, seseLockSet);
158 if(waitingElementSet.size()>0){
159 for (Iterator iterator = waitingElementSet.iterator(); iterator.hasNext();) {
160 Analysis.OoOJava.WaitingElement waitingElement = (Analysis.OoOJava.WaitingElement) iterator.next();
162 Analysis.OoOJava.ConflictGraph conflictGraph = graph;
163 Hashtable<Taint, Set<Effect>> conflicts;
164 ReachGraph rg = oooa.getDisjointAnalysis().getReachGraph(currentSESE.getmdEnclosing());
166 rg.writeGraph("RCR_RG_STALLSITE_DEBUG");
168 if((conflictGraph != null) &&
169 (conflicts = graph.getConflictEffectSet(fn)) != null &&
171 addToTraverseToDoList(fn, waitingElement.getTempDesc(), rg, conflicts);
178 buildEffectsLookupStructure();
184 * 1) Get global effects and conflicts
185 * 2) Create a hash structure (EffectsTable) to manage effects (hashed by affected Allocsite, then taint, then field)
186 * 2a) Use Effects to verify we can access something (reads)
187 * 2b) Use conflicts to mark conflicts (read/write/strongupdate)
188 * 2c) At second level of hash, store Heaproots that can cause conflicts at the field
189 * 3) Walk hash structure to identify and enumerate weakly connected groups and generate waiting queue slots.
190 * 4) Build internal representation of the rgs (pruned)
191 * 5) Print c methods by walking internal representation
194 public void addToTraverseToDoList(FlatSESEEnterNode rblock, ReachGraph rg, Hashtable<Taint, Set<Effect>> conflicts) {
196 toTraverse.add(new TraversalInfo(rblock, rg));
198 //Add to Global conflicts
199 for(Taint t: conflicts.keySet()) {
200 if(globalConflicts.containsKey(t)) {
201 globalConflicts.get(t).addAll(conflicts.get(t));
203 globalConflicts.put(t, conflicts.get(t));
209 public void addToTraverseToDoList(FlatNode fn, TempDescriptor tempDesc,
210 ReachGraph rg, Hashtable<Taint, Set<Effect>> conflicts) {
211 toTraverse.add(new TraversalInfo(fn, rg, tempDesc));
213 for(Taint t: conflicts.keySet()) {
214 if(globalConflicts.containsKey(t)) {
215 globalConflicts.get(t).addAll(conflicts.get(t));
217 globalConflicts.put(t, conflicts.get(t));
222 private void traverseSESEBlock(FlatSESEEnterNode rblock, ReachGraph rg) {
223 Collection<TempDescriptor> inVars = rblock.getInVarSet();
225 if (inVars.size() == 0)
228 // For every non-primitive variable, generate unique method
229 // Special Note: The Criteria for executing printCMethod in this loop should match
230 // exactly the criteria in buildcode.java to invoke the generated C method(s).
231 for (TempDescriptor invar : inVars) {
232 TypeDescriptor type = invar.getType();
233 if(type == null || type.isPrimitive()) {
237 //created stores nodes with specific alloc sites that have been traversed while building
238 //internal data structure. It is later traversed sequentially to find inset variables and
240 Hashtable<AllocSite, ConcreteRuntimeObjNode> created = new Hashtable<AllocSite, ConcreteRuntimeObjNode>();
241 VariableNode varNode = rg.getVariableNodeNoMutation(invar);
242 Taint taint = getProperTaintForFlatSESEEnterNode(rblock, varNode, globalEffects);
244 printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + rblock.toPrettyString());
248 //This is to prevent duplicate traversals from being generated
249 if(doneTaints.containsKey(taint))
252 doneTaints.put(taint, traverserIDCounter++);
253 createConcreteGraph(effectsLookupTable, created, varNode, taint);
256 //This will add the taint to the printout, there will be NO duplicates (checked above)
257 if(!created.isEmpty()) {
258 rblock.addInVarForDynamicCoarseConflictResolution(invar);
259 pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created));
264 private void traverseStallSite(FlatNode enterNode, TempDescriptor invar, ReachGraph rg) {
265 TypeDescriptor type = invar.getType();
266 if(type == null || type.isPrimitive()) {
269 Hashtable<AllocSite, ConcreteRuntimeObjNode> created = new Hashtable<AllocSite, ConcreteRuntimeObjNode>();
270 VariableNode varNode = rg.getVariableNodeNoMutation(invar);
271 Taint taint = getProperTaintForEnterNode(enterNode, varNode, globalEffects);
274 printDebug(javaDebug, "Null FOR " +varNode.getTempDescriptor().getSafeSymbol() + enterNode.toString());
278 if(doneTaints.containsKey(taint))
281 doneTaints.put(taint, traverserIDCounter++);
282 createConcreteGraph(effectsLookupTable, created, varNode, taint);
284 if (!created.isEmpty()) {
285 pendingPrintout.add(new TaintAndInternalHeapStructure(taint, created));
289 public String getTraverserInvocation(TempDescriptor invar, String varString, FlatNode fn) {
291 if(fn instanceof FlatSESEEnterNode) {
292 flatname = ((FlatSESEEnterNode) fn).getPrettyIdentifier();
294 flatname = fn.toString();
297 return "traverse___" + removeInvalidChars(invar.getSafeSymbol()) +
298 removeInvalidChars(flatname) + "___("+varString+");";
301 public String removeInvalidChars(String in) {
302 StringBuilder s = new StringBuilder(in);
303 for(int i = 0; i < s.length(); i++) {
304 if(s.charAt(i) == ' ' || s.charAt(i) == '.' || s.charAt(i) == '=') {
312 public void close() {
313 //prints out all generated code
314 for(TaintAndInternalHeapStructure ths: pendingPrintout) {
315 printCMethod(ths.nodesInHeap, ths.t);
318 //Prints out the master traverser Invocation that'll call all other traverser
319 //based on traverserID
320 printMasterTraverserInvocation();
321 printResumeTraverserInvocation();
323 //TODO this is only temporary, remove when thread local vars implemented.
324 createMasterHashTableArray();
326 // Adds Extra supporting methods
327 cFile.println("void initializeStructsRCR() {\n " + mallocVisitedHashtable + ";\n " + clearQueue + ";\n}");
328 cFile.println("void destroyRCR() {\n " + deallocVisitedHashTable + ";\n}");
330 headerFile.println("void initializeStructsRCR();\nvoid destroyRCR();");
331 headerFile.println("#endif\n");
337 //Builds Effects Table and runs the analysis on them to get weakly connected HRs
338 //SPECIAL NOTE: Only runs after we've taken all the conflicts
339 private void buildEffectsLookupStructure(){
340 effectsLookupTable = new EffectsTable(globalEffects, globalConflicts);
341 effectsLookupTable.runAnaylsis();
342 enumerateHeaproots();
345 private void runAllTraversals() {
346 for(TraversalInfo t: toTraverse) {
347 printDebug(javaDebug, "Running Traversal a traversal on " + t.f);
349 if(t.f instanceof FlatSESEEnterNode) {
350 traverseSESEBlock((FlatSESEEnterNode)t.f, t.rg);
352 if(t.invar == null) {
353 System.out.println("RCR ERROR: Attempted to run a stall site traversal with NO INVAR");
355 traverseStallSite(t.f, t.invar, t.rg);
362 //TODO: This is only temporary, remove when thread local variables are functional.
363 private void createMasterHashTableArray() {
364 headerFile.println("void createAndFillMasterHashStructureArray();");
365 cFile.println("void createAndFillMasterHashStructureArray() {\n" +
366 " rcr_createMasterHashTableArray("+weaklyConnectedHRCounter + ");");
368 for(int i = 0; i < weaklyConnectedHRCounter; i++) {
369 cFile.println(" allHashStructures["+i+"] = (HashStructure *) rcr_createHashtable("+num2WeaklyConnectedHRGroup.get(i).connectedHRs.size()+");");
374 private void printMasterTraverserInvocation() {
375 headerFile.println("\nint tasktraverse(SESEcommon * record);");
376 cFile.println("\nint tasktraverse(SESEcommon * record) {");
377 cFile.println(" switch(record->classID) {");
379 for(Iterator<FlatSESEEnterNode> seseit=oooa.getAllSESEs().iterator();seseit.hasNext();) {
380 FlatSESEEnterNode fsen=seseit.next();
381 cFile.println( " /* "+fsen.getPrettyIdentifier()+" */");
382 cFile.println( " case "+fsen.getIdentifier()+": {");
383 cFile.println( " "+fsen.getSESErecordName()+" * rec=("+fsen.getSESErecordName()+" *) record;");
384 Vector<TempDescriptor> invars=fsen.getInVarsForDynamicCoarseConflictResolution();
385 for(int i=0;i<invars.size();i++) {
386 TempDescriptor tmp=invars.get(i);
387 cFile.println(" " + this.getTraverserInvocation(tmp, "rec->"+tmp+", rec", fsen));
389 cFile.println( " }");
390 cFile.println( " break;");
393 cFile.println(" default:\n printf(\"Invalid SESE ID was passed in.\\n\");\n break;");
400 //This will print the traverser invocation that takes in a traverserID and
402 private void printResumeTraverserInvocation() {
403 headerFile.println("\nint traverse(void * startingPtr, SESEcommon * record, int traverserID);");
404 cFile.println("\nint traverse(void * startingPtr, SESEcommon *record, int traverserID) {");
405 cFile.println(" switch(traverserID) {");
407 for(Taint t: doneTaints.keySet()) {
408 cFile.println(" case " + doneTaints.get(t)+ ":");
409 if(t.isRBlockTaint()) {
410 cFile.println(" " + this.getTraverserInvocation(t.getVar(), "startingPtr, ("+t.getSESE().getSESErecordName()+" *)record", t.getSESE()));
411 } else if (t.isStallSiteTaint()){
412 cFile.println(" " + this.getTraverserInvocation(t.getVar(), "startingPtr, record", t.getStallSite()));
414 System.out.println("RuntimeConflictResolver encountered a taint that is neither SESE nor stallsite: " + t);
418 if(RuntimeConflictResolver.cSideDebug) {
419 cFile.println(" default:\n printf(\"Invalid traverser ID %u was passed in.\\n\", traverserID);\n break;");
421 cFile.println(" default:\n break;");
428 private void createConcreteGraph(
430 Hashtable<AllocSite, ConcreteRuntimeObjNode> created,
431 VariableNode varNode,
434 // if table is null that means there's no conflicts, therefore we need not
435 // create a traversal
439 Iterator<RefEdge> possibleEdges = varNode.iteratorToReferencees();
440 while (possibleEdges.hasNext()) {
441 RefEdge edge = possibleEdges.next();
444 ConcreteRuntimeObjNode singleRoot = new ConcreteRuntimeObjNode(edge.getDst(), true, false);
445 AllocSite rootKey = singleRoot.allocSite;
447 if (!created.containsKey(rootKey)) {
448 created.put(rootKey, singleRoot);
449 createHelper(singleRoot, edge.getDst().iteratorToReferencees(), created, table, t);
454 //This code is the old way of generating an effects lookup table.
455 //The new way is to instantiate an EffectsGroup
457 private Hashtable<AllocSite, EffectsGroup> generateEffectsLookupTable(
458 Taint taint, Hashtable<Taint,
459 Set<Effect>> effects,
460 Hashtable<Taint, Set<Effect>> conflicts) {
464 Set<Effect> localEffects = effects.get(taint);
465 Set<Effect> localConflicts = conflicts.get(taint);
467 //Debug Code for manually checking effects
469 printEffectsAndConflictsSets(taint, localEffects, localConflicts);
472 if (localEffects == null || localEffects.isEmpty() || localConflicts == null || localConflicts.isEmpty())
475 Hashtable<AllocSite, EffectsGroup> lookupTable = new Hashtable<AllocSite, EffectsGroup>();
477 for (Effect e : localEffects) {
478 boolean conflict = localConflicts.contains(e);
479 AllocSite key = e.getAffectedAllocSite();
480 EffectsGroup myEffects = lookupTable.get(key);
482 if(myEffects == null) {
483 myEffects = new EffectsGroup();
484 lookupTable.put(key, myEffects);
487 if(e.getField().getType().isPrimitive()) {
489 myEffects.addPrimitive(e, true);
493 myEffects.addObjEffect(e, conflict);
500 // Plan is to add stuff to the tree depth-first sort of way. That way, we can
501 // propagate up conflicts
502 private void createHelper(ConcreteRuntimeObjNode curr,
503 Iterator<RefEdge> edges,
504 Hashtable<AllocSite, ConcreteRuntimeObjNode> created,
507 assert table != null;
508 AllocSite parentKey = curr.allocSite;
509 EffectsGroup currEffects = table.getEffects(parentKey, taint);
511 if (currEffects == null || currEffects.isEmpty())
514 //Handle Objects (and primitives if child is new)
515 if(currEffects.hasObjectEffects()) {
516 while(edges.hasNext()) {
517 RefEdge edge = edges.next();
518 String field = edge.getField();
519 CombinedObjEffects effectsForGivenField = currEffects.getObjEffect(field);
520 //If there are no effects, then there's no point in traversing this edge
521 if(effectsForGivenField != null) {
522 HeapRegionNode childHRN = edge.getDst();
523 AllocSite childKey = childHRN.getAllocSite();
524 boolean isNewChild = !created.containsKey(childKey);
525 ConcreteRuntimeObjNode child;
528 child = new ConcreteRuntimeObjNode(childHRN, false, curr.isObjectArray());
529 created.put(childKey, child);
531 child = created.get(childKey);
534 curr.addObjChild(field, child, effectsForGivenField);
536 if (effectsForGivenField.hasConflict()) {
537 child.hasPotentialToBeIncorrectDueToConflict = true;
538 propogateObjConflict(curr, child);
541 if(effectsForGivenField.hasReadEffect) {
542 child.addReachableParent(curr);
544 //If isNewChild, flag propagation will be handled at recursive call
546 createHelper(child, childHRN.iteratorToReferencees(), created, table, taint);
548 //This makes sure that all conflicts below the child is propagated up the referencers.
549 if(child.decendantsPrimConflict || child.hasPrimitiveConflicts()) {
550 propogatePrimConflict(child, child.enqueueToWaitingQueueUponConflict);
553 if(child.decendantsObjConflict) {
554 propogateObjConflict(child, child.enqueueToWaitingQueueUponConflict);
563 curr.primitiveConflictingFields = currEffects.primitiveConflictingFields;
564 if(currEffects.hasPrimitiveConflicts()) {
565 //Reminder: primitive conflicts are abstracted to object.
566 propogatePrimConflict(curr, curr);
570 // This will propagate the conflict up the data structure.
571 private void propogateObjConflict(ConcreteRuntimeObjNode curr, HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
572 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
573 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer
574 (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess))) // case where referencer has never seen possible unresolved referencee below
576 referencer.decendantsObjConflict = true;
577 propogateObjConflict(referencer, pointsOfAccess);
582 private void propogateObjConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) {
583 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
584 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //case where referencee has never seen referncer
585 (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess))) // case where referencer has never seen possible unresolved referencee below
587 referencer.decendantsObjConflict = true;
588 propogateObjConflict(referencer, pointOfAccess);
593 private void propogatePrimConflict(ConcreteRuntimeObjNode curr, HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
594 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
595 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above
596 (pointsOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointsOfAccess)))
598 referencer.decendantsPrimConflict = true;
599 propogatePrimConflict(referencer, pointsOfAccess);
604 private void propogatePrimConflict(ConcreteRuntimeObjNode curr, ConcreteRuntimeObjNode pointOfAccess) {
605 for(ConcreteRuntimeObjNode referencer: curr.parentsWithReadToNode) {
606 if(curr.parentsThatWillLeadToConflicts.add(referencer) || //same cases as above
607 (pointOfAccess != null && referencer.addPossibleWaitingQueueEnqueue(pointOfAccess)))
609 referencer.decendantsPrimConflict = true;
610 propogatePrimConflict(referencer, pointOfAccess);
618 * This method generates a C method for every inset variable and rblock.
620 * The C method works by generating a large switch statement that will run the appropriate
621 * checking code for each object based on its allocation site. The switch statement is
622 * surrounded by a while statement which dequeues objects to be checked from a queue. An
623 * object is added to a queue only if it contains a conflict (in itself or in its referencees)
624 * and we came across it while checking through it's referencer. Because of this property,
625 * conflicts will be signaled by the referencer; the only exception is the inset variable which can
626 * signal a conflict within itself.
629 private void printCMethod(Hashtable<AllocSite, ConcreteRuntimeObjNode> created, Taint taint) {
630 //This hash table keeps track of all the case statements generated. Although it may seem a bit much
631 //for its purpose, I think it may come in handy later down the road to do it this way.
632 //(i.e. what if we want to eliminate some cases? Or build filter for 1 case)
633 String inVar = taint.getVar().getSafeSymbol();
636 if(taint.isStallSiteTaint()) {
637 rBlock = taint.getStallSite().toString();
638 } else if(taint.isRBlockTaint()) {
639 rBlock = taint.getSESE().getPrettyIdentifier();
641 System.out.println("RCR CRITICAL ERROR: TAINT IS NEITHER A STALLSITE NOR SESE! " + taint.toString());
645 Hashtable<AllocSite, StringBuilder> cases = new Hashtable<AllocSite, StringBuilder>();
648 for (ConcreteRuntimeObjNode node : created.values()) {
649 printDebug(javaDebug, "Considering " + node.allocSite + " for traversal");
650 if (!cases.containsKey(node.allocSite) && qualifiesForCaseStatement(node)) {
651 printDebug(javaDebug, "+\t" + node.allocSite + " qualified for case statement");
652 addChecker(taint, node, cases, null, "ptr", 0);
655 //IMPORTANT: remember to change getTraverserInvocation if you change the line below
657 if (taint.isStallSiteTaint()) {
658 methodName= "void traverse___" + removeInvalidChars(inVar) +
659 removeInvalidChars(rBlock) + "___(void * InVar, SESEcommon *record)";
661 methodName= "void traverse___" + removeInvalidChars(inVar) +
662 removeInvalidChars(rBlock) + "___(void * InVar, "+taint.getSESE().getSESErecordName() +" *record)";
665 cFile.println(methodName + " {");
666 headerFile.println(methodName + ";");
669 cFile.println("printf(\"The traverser ran for " + methodName + "\\n\");");
672 if(cases.size() == 0) {
673 cFile.println(" return; }");
675 //clears queue and hashtable that keeps track of where we've been.
676 cFile.println(clearQueue + ";\n" + resetVisitedHashTable + ";");
678 //Casts the ptr to a genericObjectStruct so we can get to the ptr->allocsite field.
679 cFile.println("struct ___Object___ * ptr = (struct ___Object___ *) InVar;\nif (InVar != NULL) {\n " + queryVistedHashtable + "(ptr);\n do {");
681 cFile.println(" switch(ptr->allocsite) {");
683 for(AllocSite singleCase: cases.keySet())
684 cFile.append(cases.get(singleCase));
686 cFile.println(" default:\n break; ");
687 cFile.println(" }\n } while((ptr = " + dequeueFromQueueInC + ") != NULL);\n}\n}\n");
693 * addChecker creates a case statement for every object that is either an inset variable
694 * or has multiple referencers (incoming edges). Else it just prints the checker for that object
695 * so that its processing can be pushed up to the referencer node.
697 private void addChecker(Taint taint,
698 ConcreteRuntimeObjNode node,
699 Hashtable<AllocSite,StringBuilder> cases,
700 StringBuilder possibleContinuingCase,
703 StringBuilder currCase = possibleContinuingCase;
704 // We don't need a case statement for things with either 1 incoming or 0 out
705 // going edges, because they can be processed when checking the parent.
706 if(qualifiesForCaseStatement(node)) {
707 assert prefix.equals("ptr") && !cases.containsKey(node.allocSite);
708 currCase = new StringBuilder();
709 cases.put(node.allocSite, currCase);
710 currCase.append(" case " + node.getAllocationSite() + ": {\n");
712 //either currCase is continuing off a parent case or is its own.
713 assert currCase !=null;
714 boolean primConfRead=false;
715 boolean primConfWrite=false;
716 boolean objConfRead=false;
717 boolean objConfWrite=false;
720 for(String field: node.primitiveConflictingFields.keySet()) {
721 CombinedObjEffects effect=node.primitiveConflictingFields.get(field);
722 primConfRead|=effect.hasReadConflict;
723 primConfWrite|=effect.hasWriteConflict;
726 //Object Reference Test
727 for(ObjRef ref: node.objectRefs) {
728 CombinedObjEffects effect=ref.myEffects;
729 objConfRead|=effect.hasReadConflict;
730 objConfWrite|=effect.hasWriteConflict;
734 currCase.append(" if(");
735 checkWaitingQueue(currCase, taint, node);
736 currCase.append("||");
740 if (taint.isRBlockTaint()) {
741 FlatSESEEnterNode fsese=taint.getSESE();
742 TempDescriptor tmp=taint.getVar();
743 index=fsese.getInVarsForDynamicCoarseConflictResolution().indexOf(tmp);
746 //Do call if we need it.
747 if(primConfWrite||objConfWrite) {
748 int heaprootNum = connectedHRHash.get(taint).id;
749 assert heaprootNum != -1;
750 int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
751 int traverserID = doneTaints.get(taint);
752 currCase.append(" rcr_WRITEBINCASE(allHashStructures["+heaprootNum+"],"+prefix+", (SESEcommon *) record, "+index+")");
753 } else if (primConfRead||objConfRead) {
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(" rcr_READBINCASE(allHashStructures["+heaprootNum+"],"+prefix+", (SESEcommon *) record, "+index+")");
762 currCase.append(") {\n");
763 putIntoWaitingQueue(currCase, taint, node, prefix);
764 currCase.append(" break;\n");
765 currCase.append(" }\n");
766 } else if(primConfRead||primConfWrite||objConfWrite) {
767 currCase.append(";\n");
774 if(node.isObjectArray() && node.decendantsConflict()) {
775 //since each array element will get its own case statement, we just need to enqueue each item into the queue
776 //note that the ref would be the actual object and node would be of struct ArrayObject
778 //This is done with the assumption that an array of object stores pointers.
779 currCase.append("{\n int i;\n");
780 currCase.append(" for(i = 0; i<((struct ArrayObject *) " + prefix + " )->___length___; i++ ) {\n");
781 currCase.append(" void * arrayElement = ((INTPTR *)(&(((struct ArrayObject *) " + prefix + " )->___length___) + sizeof(int)))[i];\n");
782 currCase.append(" if( arrayElement != NULL && "+ queryVistedHashtable +"(arrayElement)) {\n");
783 currCase.append(" " + addToQueueInC + "arrayElement); }}}\n");
787 for(ObjRef ref: node.objectRefs) {
788 // Will only process edge if there is some sort of conflict with the Child
789 if (ref.hasConflictsDownThisPath()) {
790 String childPtr = "((struct "+node.original.getType().getSafeSymbol()+" *)"+prefix +")->___" + ref.field + "___";
792 String currPtr = "myPtr" + pdepth;
793 String structType = ref.child.original.getType().getSafeSymbol();
794 currCase.append(" struct " + structType + " * "+currPtr+"= (struct "+ structType + " * ) " + childPtr + ";\n");
797 // Checks if the child exists and has allocsite matching the conflict
798 currCase.append(" if (" + currPtr + " != NULL && " + currPtr + getAllocSiteInC + "==" + ref.allocSite + ") {\n");
800 if (ref.child.decendantsConflict() || ref.child.hasPrimitiveConflicts()) {
801 // Checks if we have visited the child before
803 currCase.append(" if (" + queryVistedHashtable +"("+ currPtr + ")) {\n");
804 if (ref.child.getNumOfReachableParents() == 1 && !ref.child.isInsetVar) {
805 addChecker(taint, ref.child, cases, currCase, currPtr, depth + 1);
808 currCase.append(" " + addToQueueInC + childPtr + ");\n ");
811 currCase.append(" }\n");
813 //one more brace for the opening if
814 if(ref.hasDirectObjConflict()) {
815 currCase.append(" }\n");
818 currCase.append(" }\n ");
823 if(qualifiesForCaseStatement(node)) {
824 currCase.append(" }\n break;\n");
828 private boolean qualifiesForCaseStatement(ConcreteRuntimeObjNode node) {
831 (node.isInsetVar && (node.decendantsConflict() || node.hasPrimitiveConflicts())) ||
832 //non-inline-able code cases
833 (node.getNumOfReachableParents() != 1 && node.decendantsConflict()) ||
834 //Cases where resumes are possible
835 (node.hasPotentialToBeIncorrectDueToConflict) && node.decendantsObjConflict) ||
836 //Array elements since we have to enqueue them all, we can't in line their checks
837 (node.canBeArrayElement() && (node.decendantsConflict() || node.hasPrimitiveConflicts()));
840 //This method will touch the waiting queues if necessary.
841 //IMPORTANT NOTE: This needs a closing } from the caller and the if is cannot continue
842 private void addCheckHashtableAndWaitingQ(StringBuilder currCase, Taint t, ConcreteRuntimeObjNode node, String ptr, int depth) {
843 Iterator<ConcreteRuntimeObjNode> it = node.enqueueToWaitingQueueUponConflict.iterator();
845 currCase.append(" int retval"+depth+" = "+ addCheckFromHashStructure + ptr + ");\n");
846 currCase.append(" if (retval"+depth+" == " + conflictButTraverserCannotContinue + " || ");
847 checkWaitingQueue(currCase, t, node);
848 currCase.append(") {\n");
849 //If cannot continue, then add all the undetermined references that lead from this child, including self.
850 //TODO need waitingQueue Side to automatically check the thing infront of it to prevent double adds.
851 putIntoWaitingQueue(currCase, t, node, ptr);
853 ConcreteRuntimeObjNode related;
854 while(it.hasNext()) {
856 //TODO maybe ptr won't even be needed since upon resume, the hashtable will remove obj.
857 putIntoWaitingQueue(currCase, t, related, ptr);
862 private void handleObjConflict(StringBuilder currCase, String childPtr, AllocSite allocSite, ObjRef ref) {
863 currCase.append("printf(\"Conflict detected with %p from parent with allocation site %u\\n\"," + childPtr + "," + allocSite.getUniqueAllocSiteID() + ");");
866 private void handlePrimitiveConflict(StringBuilder currCase, String ptr, ArrayList<String> conflicts, AllocSite allocSite) {
867 currCase.append("printf(\"Primitive Conflict detected with %p with alloc site %u\\n\", "+ptr+", "+allocSite.getUniqueAllocSiteID()+"); ");
871 private Taint getProperTaintForFlatSESEEnterNode(FlatSESEEnterNode rblock, VariableNode var,
872 Hashtable<Taint, Set<Effect>> effects) {
873 Set<Taint> taints = effects.keySet();
874 for (Taint t : taints) {
875 FlatSESEEnterNode sese = t.getSESE();
876 if(sese != null && sese.equals(rblock) && t.getVar().equals(var.getTempDescriptor())) {
884 private Taint getProperTaintForEnterNode(FlatNode stallSite, VariableNode var,
885 Hashtable<Taint, Set<Effect>> effects) {
886 Set<Taint> taints = effects.keySet();
887 for (Taint t : taints) {
888 FlatNode flatnode = t.getStallSite();
889 if(flatnode != null && flatnode.equals(stallSite) && t.getVar().equals(var.getTempDescriptor())) {
896 private void printEffectsAndConflictsSets(Taint taint, Set<Effect> localEffects,
897 Set<Effect> localConflicts) {
898 System.out.println("#### List of Effects/Conflicts ####");
899 System.out.println("For Taint " + taint);
900 System.out.println("Effects");
901 if(localEffects != null) {
902 for(Effect e: localEffects) {
903 System.out.println(e);
906 System.out.println("Conflicts");
907 if(localConflicts != null) {
908 for(Effect e: localConflicts) {
909 System.out.println(e);
914 private void printDebug(boolean guard, String debugStatements) {
916 System.out.println(debugStatements);
919 //TODO finish this once waitingQueue side is figured out
920 private void putIntoWaitingQueue(StringBuilder sb, Taint taint, ConcreteRuntimeObjNode node, String resumePtr ) {
921 //Method looks like this: void put(int allocSiteID, x
922 //struct WaitingQueue * queue, //get this from hashtable
923 //int effectType, //not so sure we would actually need this one.
925 //int traverserID); }
926 int heaprootNum = connectedHRHash.get(taint).id;
927 assert heaprootNum != -1;
928 int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
929 int traverserID = doneTaints.get(taint);
931 //NOTE if the C-side is changed, this will have to be changed accordingly
932 //TODO make sure this matches c-side
933 sb.append(" putIntoWaitingQueue("+allocSiteID+", " +
934 "allHashStructures["+ heaprootNum +"]->waitingQueue, " +
939 //TODO finish waitingQueue side
941 * Inserts check to see if waitingQueue is occupied.
943 * On C-side, =0 means empty queue, else occupied.
945 private void checkWaitingQueue(StringBuilder sb, Taint taint, ConcreteRuntimeObjNode node) {
946 //Method looks like int check(struct WaitingQueue * queue, int allocSiteID)
947 assert sb != null && taint !=null;
948 int heaprootNum = connectedHRHash.get(taint).id;
949 assert heaprootNum != -1;
950 int allocSiteID = connectedHRHash.get(taint).getWaitingQueueBucketNum(node);
952 sb.append(" (isEmptyForWaitingQ(allHashStructures["+ heaprootNum +"]->waitingQueue, " + allocSiteID + ") == "+ allocQueueIsNotEmpty+")");
955 private void enumerateHeaproots() {
956 //reset numbers jsut in case
957 weaklyConnectedHRCounter = 0;
958 num2WeaklyConnectedHRGroup = new ArrayList<WeaklyConectedHRGroup>();
960 for(Taint t: connectedHRHash.keySet()) {
961 if(connectedHRHash.get(t).id == -1) {
962 WeaklyConectedHRGroup hg = connectedHRHash.get(t);
963 hg.id = weaklyConnectedHRCounter;
964 num2WeaklyConnectedHRGroup.add(weaklyConnectedHRCounter, hg);
965 weaklyConnectedHRCounter++;
970 private void printoutTable(EffectsTable table) {
972 System.out.println("==============EFFECTS TABLE PRINTOUT==============");
973 for(AllocSite as: table.table.keySet()) {
974 System.out.println("\tFor AllocSite " + as.getUniqueAllocSiteID());
976 BucketOfEffects boe = table.table.get(as);
978 if(boe.potentiallyConflictingRoots != null && !boe.potentiallyConflictingRoots.isEmpty()) {
979 System.out.println("\t\tPotentially conflicting roots: ");
980 for(String key: boe.potentiallyConflictingRoots.keySet()) {
981 System.out.println("\t\t-Field: " + key);
982 System.out.println("\t\t\t" + boe.potentiallyConflictingRoots.get(key));
985 for(Taint t: boe.taint2EffectsGroup.keySet()) {
986 System.out.println("\t\t For Taint " + t);
987 EffectsGroup eg = boe.taint2EffectsGroup.get(t);
989 if(eg.hasPrimitiveConflicts()) {
990 System.out.print("\t\t\tPrimitive Conflicts at alloc " + as.getUniqueAllocSiteID() +" : ");
991 for(String field: eg.primitiveConflictingFields.keySet()) {
992 System.out.print(field + " ");
994 System.out.println();
996 for(String fieldKey: eg.myEffects.keySet()) {
997 CombinedObjEffects ce = eg.myEffects.get(fieldKey);
998 System.out.println("\n\t\t\tFor allocSite " + as.getUniqueAllocSiteID() + " && field " + fieldKey);
999 System.out.println("\t\t\t\tread " + ce.hasReadEffect + "/"+ce.hasReadConflict +
1000 " write " + ce.hasWriteEffect + "/" + ce.hasWriteConflict +
1001 " SU " + ce.hasStrongUpdateEffect + "/" + ce.hasStrongUpdateConflict);
1002 for(Effect ef: ce.originalEffects) {
1003 System.out.println("\t" + ef);
1012 private class EffectsGroup {
1013 Hashtable<String, CombinedObjEffects> myEffects;
1014 Hashtable<String, CombinedObjEffects> primitiveConflictingFields;
1016 public EffectsGroup() {
1017 myEffects = new Hashtable<String, CombinedObjEffects>();
1018 primitiveConflictingFields = new Hashtable<String, CombinedObjEffects>();
1021 public void addPrimitive(Effect e, boolean conflict) {
1022 CombinedObjEffects effects;
1023 if((effects = primitiveConflictingFields.get(e.getField().getSymbol())) == null) {
1024 effects = new CombinedObjEffects();
1025 primitiveConflictingFields.put(e.getField().getSymbol(), effects);
1027 effects.add(e, conflict);
1030 public void addObjEffect(Effect e, boolean conflict) {
1031 CombinedObjEffects effects;
1032 if((effects = myEffects.get(e.getField().getSymbol())) == null) {
1033 effects = new CombinedObjEffects();
1034 myEffects.put(e.getField().getSymbol(), effects);
1036 effects.add(e, conflict);
1039 public boolean isEmpty() {
1040 return myEffects.isEmpty() && primitiveConflictingFields.isEmpty();
1043 public boolean hasPrimitiveConflicts(){
1044 return !primitiveConflictingFields.isEmpty();
1047 public CombinedObjEffects getPrimEffect(String field) {
1048 return primitiveConflictingFields.get(field);
1051 public boolean hasObjectEffects() {
1052 return !myEffects.isEmpty();
1055 public CombinedObjEffects getObjEffect(String field) {
1056 return myEffects.get(field);
1060 //Is the combined effects for all effects with the same affectedAllocSite and field
1061 private class CombinedObjEffects {
1062 ArrayList<Effect> originalEffects;
1064 public boolean hasReadEffect;
1065 public boolean hasWriteEffect;
1066 public boolean hasStrongUpdateEffect;
1068 public boolean hasReadConflict;
1069 public boolean hasWriteConflict;
1070 public boolean hasStrongUpdateConflict;
1073 public CombinedObjEffects() {
1074 originalEffects = new ArrayList<Effect>();
1076 hasReadEffect = false;
1077 hasWriteEffect = false;
1078 hasStrongUpdateEffect = false;
1080 hasReadConflict = false;
1081 hasWriteConflict = false;
1082 hasStrongUpdateConflict = false;
1085 public boolean add(Effect e, boolean conflict) {
1086 if(!originalEffects.add(e))
1089 switch(e.getType()) {
1091 hasReadEffect = true;
1092 hasReadConflict = conflict;
1095 hasWriteEffect = true;
1096 hasWriteConflict = conflict;
1098 case Effect.strongupdate:
1099 hasStrongUpdateEffect = true;
1100 hasStrongUpdateConflict = conflict;
1103 System.out.println("RCR ERROR: An Effect Type never seen before has been encountered");
1110 public boolean hasConflict() {
1111 return hasReadConflict || hasWriteConflict || hasStrongUpdateConflict;
1115 //This will keep track of a reference
1116 private class ObjRef {
1119 CombinedObjEffects myEffects;
1121 //This keeps track of the parent that we need to pass by inorder to get
1122 //to the conflicting child (if there is one).
1123 ConcreteRuntimeObjNode child;
1125 public ObjRef(String fieldname,
1126 ConcreteRuntimeObjNode ref,
1127 CombinedObjEffects myEffects) {
1129 allocSite = ref.getAllocationSite();
1132 this.myEffects = myEffects;
1135 public boolean hasConflictsDownThisPath() {
1136 return child.decendantsObjConflict || child.decendantsPrimConflict || child.hasPrimitiveConflicts() || myEffects.hasConflict();
1139 public boolean hasDirectObjConflict() {
1140 return myEffects.hasConflict();
1144 private class ConcreteRuntimeObjNode {
1145 ArrayList<ObjRef> objectRefs;
1146 Hashtable<String, CombinedObjEffects> primitiveConflictingFields;
1147 HashSet<ConcreteRuntimeObjNode> parentsWithReadToNode;
1148 HashSet<ConcreteRuntimeObjNode> parentsThatWillLeadToConflicts;
1149 //this set keeps track of references down the line that need to be enqueued if traverser is "paused"
1150 HashSet<ConcreteRuntimeObjNode> enqueueToWaitingQueueUponConflict;
1151 boolean decendantsPrimConflict;
1152 boolean decendantsObjConflict;
1153 boolean hasPotentialToBeIncorrectDueToConflict;
1155 boolean isArrayElement;
1156 AllocSite allocSite;
1157 HeapRegionNode original;
1159 public ConcreteRuntimeObjNode(HeapRegionNode me, boolean isInVar, boolean isArrayElement) {
1160 objectRefs = new ArrayList<ObjRef>();
1161 primitiveConflictingFields = null;
1162 parentsThatWillLeadToConflicts = new HashSet<ConcreteRuntimeObjNode>();
1163 parentsWithReadToNode = new HashSet<ConcreteRuntimeObjNode>();
1164 enqueueToWaitingQueueUponConflict = new HashSet<ConcreteRuntimeObjNode>();
1165 allocSite = me.getAllocSite();
1167 isInsetVar = isInVar;
1168 decendantsPrimConflict = false;
1169 decendantsObjConflict = false;
1170 hasPotentialToBeIncorrectDueToConflict = false;
1171 this.isArrayElement = isArrayElement;
1174 public void addReachableParent(ConcreteRuntimeObjNode curr) {
1175 parentsWithReadToNode.add(curr);
1179 public boolean equals(Object obj) {
1180 return original.equals(obj);
1183 public int getAllocationSite() {
1184 return allocSite.getUniqueAllocSiteID();
1187 public int getNumOfReachableParents() {
1188 return parentsThatWillLeadToConflicts.size();
1191 public boolean hasPrimitiveConflicts() {
1192 return primitiveConflictingFields != null && !primitiveConflictingFields.isEmpty();
1195 public boolean decendantsConflict() {
1196 return decendantsPrimConflict || decendantsObjConflict;
1200 //returns true if at least one of the objects in points of access has been added
1201 public boolean addPossibleWaitingQueueEnqueue(HashSet<ConcreteRuntimeObjNode> pointsOfAccess) {
1202 boolean addedNew = false;
1203 for(ConcreteRuntimeObjNode dec: pointsOfAccess) {
1204 if(dec != null && dec != this){
1205 addedNew = addedNew || enqueueToWaitingQueueUponConflict.add(dec);
1212 public boolean addPossibleWaitingQueueEnqueue(ConcreteRuntimeObjNode pointOfAccess) {
1213 if(pointOfAccess != null && pointOfAccess != this){
1214 return enqueueToWaitingQueueUponConflict.add(pointOfAccess);
1220 public void addObjChild(String field, ConcreteRuntimeObjNode child, CombinedObjEffects ce) {
1221 ObjRef ref = new ObjRef(field, child, ce);
1222 objectRefs.add(ref);
1225 public boolean isObjectArray() {
1226 return original.getType().isArray() && !original.getType().isPrimitive() && !original.getType().isImmutable();
1229 public boolean canBeArrayElement() {
1230 return isArrayElement;
1233 public String toString() {
1234 return "AllocSite=" + getAllocationSite() + " myConflict=" + !parentsThatWillLeadToConflicts.isEmpty() +
1235 " decCon="+decendantsObjConflict+
1236 " NumOfConParents=" + getNumOfReachableParents() + " ObjectChildren=" + objectRefs.size();
1240 private class EffectsTable {
1241 private Hashtable<AllocSite, BucketOfEffects> table;
1243 public EffectsTable(Hashtable<Taint, Set<Effect>> effects,
1244 Hashtable<Taint, Set<Effect>> conflicts) {
1245 table = new Hashtable<AllocSite, BucketOfEffects>();
1247 // rehash all effects (as a 5-tuple) by their affected allocation site
1248 for (Taint t : effects.keySet()) {
1249 Set<Effect> localConflicts = conflicts.get(t);
1250 for (Effect e : effects.get(t)) {
1251 BucketOfEffects bucket;
1252 if ((bucket = table.get(e.getAffectedAllocSite())) == null) {
1253 bucket = new BucketOfEffects();
1254 table.put(e.getAffectedAllocSite(), bucket);
1256 printDebug(javaDebug, "Added Taint" + t + " Effect " + e + "Conflict Status = " + (localConflicts!=null?localConflicts.contains(e):false)+" localConflicts = "+localConflicts);
1257 bucket.add(t, e, localConflicts!=null?localConflicts.contains(e):false);
1262 public EffectsGroup getEffects(AllocSite parentKey, Taint taint) {
1263 //This would get the proper bucket of effects and then get all the effects
1264 //for a parent for a specific taint
1266 return table.get(parentKey).taint2EffectsGroup.get(taint);
1268 catch (NullPointerException e) {
1273 // Run Analysis will walk the data structure and figure out the weakly
1274 // connected heap roots.
1275 public void runAnaylsis() {
1277 printoutTable(this);
1280 //TODO is there a higher performance way to do this?
1281 for(AllocSite key: table.keySet()) {
1282 BucketOfEffects effects = table.get(key);
1283 //make sure there are actually conflicts in the bucket
1284 if(effects.potentiallyConflictingRoots != null && !effects.potentiallyConflictingRoots.isEmpty()){
1285 for(String field: effects.potentiallyConflictingRoots.keySet()){
1286 ArrayList<Taint> taints = effects.potentiallyConflictingRoots.get(field);
1287 //For simplicity, we just create a new group and add everything to it instead of
1288 //searching through all of them for the largest group and adding everyone in.
1289 WeaklyConectedHRGroup group = new WeaklyConectedHRGroup();
1290 group.add(taints); //This will automatically add the taint to the connectedHRhash
1297 private class WeaklyConectedHRGroup {
1298 HashSet<Taint> connectedHRs;
1299 //This is to keep track of unique waitingQueue positions for each allocsite.
1300 Hashtable<AllocSite, Integer> allocSiteToWaitingQueueMap;
1301 int waitingQueueCounter;
1304 public WeaklyConectedHRGroup() {
1305 connectedHRs = new HashSet<Taint>();
1306 id = -1; //this will be later modified
1307 waitingQueueCounter = 0;
1308 allocSiteToWaitingQueueMap = new Hashtable<AllocSite, Integer>();
1311 public void add(ArrayList<Taint> list) {
1312 for(Taint t: list) {
1317 public int getWaitingQueueBucketNum(ConcreteRuntimeObjNode node) {
1318 if(allocSiteToWaitingQueueMap.containsKey(node.allocSite)) {
1319 return allocSiteToWaitingQueueMap.get(node.allocSite);
1322 allocSiteToWaitingQueueMap.put(node.allocSite, waitingQueueCounter);
1323 return waitingQueueCounter++;
1327 public void add(Taint t) {
1328 connectedHRs.add(t);
1329 WeaklyConectedHRGroup oldGroup = connectedHRHash.get(t);
1330 connectedHRHash.put(t, this); //put new group into hash
1331 //If the taint was already in another group, move all its buddies over.
1332 if(oldGroup != this && oldGroup != null) {
1333 Iterator<Taint> it = oldGroup.connectedHRs.iterator();
1336 while((relatedTaint = it.next()) != null && !connectedHRs.contains(relatedTaint)) {
1337 this.add(relatedTaint);
1343 //This is a class that stores all the effects for an affected allocation site
1344 //across ALL taints. The structure is a hashtable of EffectGroups (see above) hashed
1345 //by a Taint. This way, I can keep EffectsGroups so I can reuse most to all of my old code
1346 //and allows for easier tracking of effects. In addition, a hashtable (keyed by the string
1347 //of the field access) keeps track of an ArrayList of taints of SESEblocks that conflict on that
1349 private class BucketOfEffects {
1350 // This table is used for lookup while creating the traversal.
1351 Hashtable<Taint, EffectsGroup> taint2EffectsGroup;
1353 //This table is used to help identify weakly connected groups: Contains ONLY
1354 //conflicting effects AND is only initialized when needed
1355 //String stores the field
1356 Hashtable<String, ArrayList<Taint>> potentiallyConflictingRoots;
1358 public BucketOfEffects() {
1359 taint2EffectsGroup = new Hashtable<Taint, EffectsGroup>();
1362 public void add(Taint t, Effect e, boolean conflict) {
1363 EffectsGroup effectsForGivenTaint;
1365 if ((effectsForGivenTaint = taint2EffectsGroup.get(t)) == null) {
1366 effectsForGivenTaint = new EffectsGroup();
1367 taint2EffectsGroup.put(t, effectsForGivenTaint);
1370 if (e.getField().getType().isPrimitive()) {
1372 effectsForGivenTaint.addPrimitive(e, true);
1375 effectsForGivenTaint.addObjEffect(e, conflict);
1379 if(potentiallyConflictingRoots == null) {
1380 potentiallyConflictingRoots = new Hashtable<String, ArrayList<Taint>>();
1383 ArrayList<Taint> taintsForField = potentiallyConflictingRoots.get(e.getField().getSafeSymbol());
1384 if(taintsForField == null) {
1385 taintsForField = new ArrayList<Taint>();
1386 potentiallyConflictingRoots.put(e.getField().getSafeSymbol(), taintsForField);
1389 if(!taintsForField.contains(t)) {
1390 taintsForField.add(t);
1396 private class TaintAndInternalHeapStructure {
1398 public Hashtable<AllocSite, ConcreteRuntimeObjNode> nodesInHeap;
1400 public TaintAndInternalHeapStructure(Taint taint, Hashtable<AllocSite, ConcreteRuntimeObjNode> nodesInHeap) {
1402 this.nodesInHeap = nodesInHeap;
1406 private class TraversalInfo {
1408 public ReachGraph rg;
1409 public TempDescriptor invar;
1411 public TraversalInfo(FlatNode fn, ReachGraph g) {
1417 public TraversalInfo(FlatNode fn, ReachGraph rg2, TempDescriptor tempDesc) {