0001: package soot.jimple.toolkits.thread.transaction;
0002:
0003: import java.util.*;
0004:
0005: import soot.*;
0006: import soot.util.Chain;
0007: import soot.jimple.*;
0008: import soot.jimple.toolkits.pointer.*;
0009: import soot.jimple.toolkits.thread.ThreadLocalObjectsAnalysis;
0010: import soot.jimple.toolkits.thread.mhp.UnsynchronizedMhpAnalysis;
0011: import soot.jimple.toolkits.callgraph.*;
0012: import soot.jimple.toolkits.infoflow.*;
0013: import soot.jimple.spark.pag.*;
0014: import soot.jimple.spark.sets.*;
0015: import soot.toolkits.scalar.*;
0016: import soot.toolkits.graph.*;
0017:
0018: public class TransactionTransformer extends SceneTransformer {
0019: public TransactionTransformer(Singletons.Global g) {
0020: }
0021:
0022: public static TransactionTransformer v() {
0023: return G
0024: .v()
0025: .soot_jimple_toolkits_thread_transaction_TransactionTransformer();
0026: }
0027:
0028: // Lock options
0029: boolean optionOneGlobalLock = false;
0030: boolean optionStaticLocks = false;
0031: boolean optionUseLocksets = false;
0032: boolean optionLeaveOriginalLocks = false;
0033: boolean optionIncludeEmptyPossibleEdges = false;
0034:
0035: // Semantic options
0036: boolean optionAvoidDeadlock = true;
0037: boolean optionOpenNesting = true;
0038:
0039: // Analysis options
0040: boolean optionDoMHP = false;
0041: boolean optionDoTLO = false;
0042: boolean optionOnFlyTLO = false; // not a CLI option yet // on-fly is more efficient, but harder to measure in time
0043:
0044: // Output options
0045: boolean optionPrintMhpSummary = true; // not a CLI option yet
0046: boolean optionPrintGraph = false;
0047: boolean optionPrintTable = false;
0048: boolean optionPrintDebug = false;
0049:
0050: UnsynchronizedMhpAnalysis mhp;
0051:
0052: protected void internalTransform(String phaseName, Map options) {
0053: // Get phase options
0054:
0055: String lockingScheme = PhaseOptions.getString(options,
0056: "locking-scheme");
0057: if (lockingScheme.equals("fine-grained")) {
0058: optionOneGlobalLock = false;
0059: optionStaticLocks = false;
0060: optionUseLocksets = true;
0061: optionLeaveOriginalLocks = false;
0062: }
0063: // if(lockingScheme.equals("fine-static"))
0064: // {
0065: // optionOneGlobalLock = false;
0066: // optionStaticLocks = true;
0067: // optionUseLocksets = true;
0068: // optionLeaveOriginalLocks = false;
0069: // }
0070: if (lockingScheme.equals("medium-grained")) // rename to coarse-grained
0071: {
0072: optionOneGlobalLock = false;
0073: optionStaticLocks = false;
0074: optionUseLocksets = false;
0075: optionLeaveOriginalLocks = false;
0076: }
0077: if (lockingScheme.equals("coarse-grained")) // rename to coarse-static
0078: {
0079: optionOneGlobalLock = false;
0080: optionStaticLocks = true;
0081: optionUseLocksets = false;
0082: optionLeaveOriginalLocks = false;
0083: }
0084: if (lockingScheme.equals("single-static")) {
0085: optionOneGlobalLock = true;
0086: optionStaticLocks = true;
0087: optionUseLocksets = false;
0088: optionLeaveOriginalLocks = false;
0089: }
0090: if (lockingScheme.equals("leave-original")) {
0091: optionOneGlobalLock = false;
0092: optionStaticLocks = false;
0093: optionUseLocksets = false;
0094: optionLeaveOriginalLocks = true;
0095: }
0096:
0097: optionAvoidDeadlock = PhaseOptions.getBoolean(options,
0098: "avoid-deadlock");
0099: optionOpenNesting = PhaseOptions.getBoolean(options,
0100: "open-nesting");
0101:
0102: optionDoMHP = PhaseOptions.getBoolean(options, "do-mhp");
0103: optionDoTLO = PhaseOptions.getBoolean(options, "do-tlo");
0104: // optionOnFlyTLO = PhaseOptions.getBoolean( options, "on-fly-tlo" ); // not a real option yet
0105:
0106: // optionPrintMhpSummary = PhaseOptions.getBoolean( options, "print-mhp" ); // not a real option yet
0107: optionPrintGraph = PhaseOptions.getBoolean(options,
0108: "print-graph");
0109: optionPrintTable = PhaseOptions.getBoolean(options,
0110: "print-table");
0111: optionPrintDebug = PhaseOptions.getBoolean(options,
0112: "print-debug");
0113:
0114: // optionIncludeEmptyPossibleEdges = PhaseOptions.getBoolean( options, "include-empty-edges" ); // not a real option yet
0115:
0116: // *** Build May Happen In Parallel Info ***
0117: if (optionDoMHP
0118: && Scene.v().getPointsToAnalysis() instanceof PAG) {
0119: G.v().out
0120: .println("[wjtp.tn] *** Build May-Happen-in-Parallel Info *** "
0121: + (new Date()));
0122: mhp = new UnsynchronizedMhpAnalysis();
0123: if (optionPrintMhpSummary) {
0124: mhp.printMhpSummary();
0125: }
0126: } else {
0127: mhp = null;
0128: }
0129:
0130: // *** Find Thread-Local Objects ***
0131: ThreadLocalObjectsAnalysis tlo = null;
0132: if (optionDoTLO) {
0133: G.v().out
0134: .println("[wjtp.tn] *** Find Thread-Local Objects *** "
0135: + (new Date()));
0136: if (mhp != null)
0137: tlo = new ThreadLocalObjectsAnalysis(mhp); // can tell only that a field/local is local to the object it's being accessed in
0138: else
0139: tlo = new ThreadLocalObjectsAnalysis(
0140: new UnsynchronizedMhpAnalysis()); // can tell only that a field/local is local to the object it's being accessed in
0141: if (!optionOnFlyTLO) {
0142: tlo.precompute();
0143: G.v().out
0144: .println("[wjtp.tn] TLO totals (#analyzed/#encountered): "
0145: + SmartMethodInfoFlowAnalysis.counter
0146: + "/"
0147: + ClassInfoFlowAnalysis.methodCount);
0148: }
0149: }
0150:
0151: // *** Find and Name Transactions ***
0152: // The transaction finder finds the start, end, and preparatory statements
0153: // for each transaction. It also calculates the non-transitive read/write
0154: // sets for each transaction.
0155: // For all methods, run the intraprocedural analysis (TransactionAnalysis)
0156: Date start = new Date();
0157: G.v().out
0158: .println("[wjtp.tn] *** Find and Name Transactions *** "
0159: + start);
0160: Map<SootMethod, FlowSet> methodToFlowSet = new HashMap<SootMethod, FlowSet>();
0161: Map<SootMethod, ExceptionalUnitGraph> methodToExcUnitGraph = new HashMap<SootMethod, ExceptionalUnitGraph>();
0162: Iterator runAnalysisClassesIt = Scene.v()
0163: .getApplicationClasses().iterator();
0164: while (runAnalysisClassesIt.hasNext()) {
0165: SootClass appClass = (SootClass) runAnalysisClassesIt
0166: .next();
0167: Iterator methodsIt = appClass.getMethods().iterator();
0168: while (methodsIt.hasNext()) {
0169: SootMethod method = (SootMethod) methodsIt.next();
0170: if (method.isConcrete()) {
0171: Body b = method.retrieveActiveBody();
0172: ExceptionalUnitGraph eug = new ExceptionalUnitGraph(
0173: b);
0174: methodToExcUnitGraph.put(method, eug);
0175:
0176: // run the intraprocedural analysis
0177: TransactionAnalysis ta = new TransactionAnalysis(
0178: eug, b, optionPrintDebug, tlo);
0179: Chain units = b.getUnits();
0180: Unit lastUnit = (Unit) units.getLast();
0181: FlowSet fs = (FlowSet) ta.getFlowBefore(lastUnit);
0182:
0183: // add the results to the list of results
0184: methodToFlowSet.put(method, fs);
0185: }
0186: }
0187: }
0188:
0189: // Create a composite list of all transactions
0190: List<Transaction> AllTransactions = new Vector<Transaction>();
0191: Collection<FlowSet> AllFlowSets = methodToFlowSet.values();
0192: Iterator<FlowSet> fsIt = AllFlowSets.iterator();
0193: while (fsIt.hasNext()) {
0194: FlowSet fs = fsIt.next();
0195: List fList = fs.toList();
0196: for (int i = 0; i < fList.size(); i++)
0197: AllTransactions
0198: .add(((TransactionFlowPair) fList.get(i)).tn);
0199: }
0200:
0201: // Assign Names To Transactions
0202: assignNamesToTransactions(AllTransactions);
0203:
0204: if (optionOnFlyTLO) {
0205: G.v().out
0206: .println("[wjtp.tn] TLO totals (#analyzed/#encountered): "
0207: + SmartMethodInfoFlowAnalysis.counter
0208: + "/"
0209: + ClassInfoFlowAnalysis.methodCount);
0210: }
0211:
0212: // *** Find Transitive Read/Write Sets ***
0213: // Finds the transitive read/write set for each transaction using a given
0214: // nesting model.
0215: G.v().out
0216: .println("[wjtp.tn] *** Find Transitive Read/Write Sets *** "
0217: + (new Date()));
0218: PointsToAnalysis pta = Scene.v().getPointsToAnalysis();
0219: TransactionAwareSideEffectAnalysis tasea = null;
0220: if (optionOpenNesting) // TODO: NOT COMPLETE. Must have open/closed switch in TransactionAnalysis as well.
0221: {
0222: tasea = new TransactionAwareSideEffectAnalysis(pta, Scene
0223: .v().getCallGraph(), AllTransactions, tlo);
0224: } else {
0225: tasea = new TransactionAwareSideEffectAnalysis(pta, Scene
0226: .v().getCallGraph(), null, tlo);
0227: }
0228: Iterator<Transaction> tnIt = AllTransactions.iterator();
0229: while (tnIt.hasNext()) {
0230: Transaction tn = tnIt.next();
0231: Iterator<Object> invokeIt = tn.invokes.iterator();
0232: while (invokeIt.hasNext()) {
0233: Stmt stmt = (Stmt) invokeIt.next();
0234:
0235: HashSet uses = new HashSet();
0236: RWSet stmtRead = tasea.readSet(tn.method, stmt, tn,
0237: uses);
0238: if (stmtRead != null)
0239: tn.read.union(stmtRead);
0240:
0241: RWSet stmtWrite = tasea.writeSet(tn.method, stmt, tn,
0242: uses);
0243: if (stmtWrite != null)
0244: tn.write.union(stmtWrite);
0245:
0246: // memory hog???
0247: /* CodeBlockRWSet bothRW = new CodeBlockRWSet();
0248: bothRW.union(stmtRead);
0249: bothRW.union(stmtWrite);
0250: tn.unitToRWSet.put(stmt, bothRW);
0251:
0252: List<Object> usesList;
0253: if(tn.unitToUses.containsKey(stmt))
0254: usesList = tn.unitToUses.get(stmt);
0255: else
0256: {
0257: usesList = new ArrayList<Object>();
0258: tn.unitToUses.put(stmt, usesList);
0259: }
0260:
0261: for(Iterator usesIt = uses.iterator(); usesIt.hasNext(); )
0262: {
0263: Object use = usesIt.next();
0264: if(!usesList.contains(use))
0265: usesList.add(use);
0266: }
0267: */
0268: }
0269: }
0270: long longTime = ((new Date()).getTime() - start.getTime()) / 100;
0271: float time = ((float) longTime) / 10.0f;
0272: if (optionOnFlyTLO) {
0273: G.v().out
0274: .println("[wjtp.tn] TLO totals (#analyzed/#encountered): "
0275: + SmartMethodInfoFlowAnalysis.counter
0276: + "/"
0277: + ClassInfoFlowAnalysis.methodCount);
0278: G.v().out
0279: .println("[wjtp.tn] Time for stages utilizing on-fly TLO: "
0280: + time + "s");
0281: }
0282:
0283: // *** Find Stray Reads/Writes *** (DISABLED)
0284: // add external data races as one-line transactions
0285: // note that finding them isn't that hard (though it is time consuming)
0286: // For all methods, run the intraprocedural analysis (transaction finder)
0287: // Note that these will only be transformed if they are either added to
0288: // methodToFlowSet or if a loop and new body transformer are used for methodToStrayRWSet
0289: /* Map methodToStrayRWSet = new HashMap();
0290: Iterator runRWFinderClassesIt = Scene.v().getApplicationClasses().iterator();
0291: while (runRWFinderClassesIt.hasNext())
0292: {
0293: SootClass appClass = (SootClass) runRWFinderClassesIt.next();
0294: Iterator methodsIt = appClass.getMethods().iterator();
0295: while (methodsIt.hasNext())
0296: {
0297: SootMethod method = (SootMethod) methodsIt.next();
0298: Body b = method.retrieveActiveBody();
0299: UnitGraph g = (UnitGraph) methodToExcUnitGraph.get(method);
0300:
0301: // run the interprocedural analysis
0302: // PTFindStrayRW ptfrw = new PTFindStrayRW(new ExceptionalUnitGraph(b), b, AllTransactions);
0303: PTFindStrayRW ptfrw = new PTFindStrayRW(g, b, AllTransactions);
0304: Chain units = b.getUnits();
0305: Unit firstUnit = (Unit) units.iterator().next();
0306: FlowSet fs = (FlowSet) ptfrw.getFlowBefore(firstUnit);
0307:
0308: // add the results to the list of results
0309: methodToStrayRWSet.put(method, fs);
0310: }
0311: }
0312: //*/
0313:
0314: // *** Calculate Locking Groups ***
0315: // Search for data dependencies between transactions, and split them into disjoint sets
0316: G.v().out.println("[wjtp.tn] *** Calculate Locking Groups *** "
0317: + (new Date()));
0318: int nextGroup = 1;
0319: List<TransactionGroup> groups = new ArrayList<TransactionGroup>();
0320: groups.add(new TransactionGroup(0)); // dummy group
0321: if (optionOneGlobalLock) // use one group for all transactions
0322: {
0323: TransactionGroup onlyGroup = new TransactionGroup(nextGroup);
0324: Iterator<Transaction> tnIt1 = AllTransactions.iterator();
0325: while (tnIt1.hasNext()) {
0326: Transaction tn1 = tnIt1.next();
0327: onlyGroup.add(tn1);
0328: }
0329: nextGroup++;
0330: groups.add(onlyGroup);
0331: } else // calculate separate groups for transactions
0332: {
0333: Iterator<Transaction> tnIt1 = AllTransactions.iterator();
0334: while (tnIt1.hasNext()) {
0335: Transaction tn1 = tnIt1.next();
0336:
0337: // if this transaction has somehow already been marked for deletion
0338: if (tn1.setNumber == -1)
0339: continue;
0340:
0341: // if this transaction is empty
0342: if (tn1.read.size() == 0 && tn1.write.size() == 0
0343: && !optionLeaveOriginalLocks) {
0344: // this transaction has no effect except on locals... we don't need it!
0345: tn1.setNumber = -1; // AKA delete the transactional region (but don't really so long as we are using
0346: // the synchronized keyword in our language... because java guarantees memory
0347: // barriers at certain points in synchronized blocks)
0348: } else {
0349: Iterator<Transaction> tnIt2 = AllTransactions
0350: .iterator();
0351: while (tnIt2.hasNext()) {
0352: Transaction tn2 = tnIt2.next();
0353:
0354: // check if this transactional region is going to be deleted
0355: if (tn2.setNumber == -1)
0356: continue;
0357:
0358: // check if they're already marked as having an interference
0359: // NOTE: this results in a sound grouping, but a badly
0360: // incomplete dependency graph. If the dependency
0361: // graph is to be analyzed, we cannot do this
0362: // if(tn1.setNumber > 0 && tn1.setNumber == tn2.setNumber)
0363: // continue;
0364:
0365: // check if these two transactions can't ever be in parallel
0366: if (!mayHappenInParallel(tn1, tn2))
0367: continue;
0368:
0369: // check for RW or WW data dependencies.
0370: // or, for optionLeaveOriginalLocks, check type compatibility
0371: SootClass classOne = null;
0372: SootClass classTwo = null;
0373: boolean typeCompatible = false;
0374: boolean emptyEdge = false;
0375: if (tn1.origLock != null
0376: && tn2.origLock != null) {
0377: // Check if edge is empty
0378: if (tn1.origLock == null
0379: || tn2.origLock == null)
0380: emptyEdge = true;
0381: else if (!(tn1.origLock instanceof Local)
0382: || !(tn2.origLock instanceof Local))
0383: emptyEdge = !tn1.origLock
0384: .equals(tn2.origLock);
0385: else
0386: emptyEdge = !pta
0387: .reachingObjects(
0388: (Local) tn1.origLock)
0389: .hasNonEmptyIntersection(
0390: pta
0391: .reachingObjects((Local) tn2.origLock));
0392:
0393: // Check if types are compatible
0394: RefLikeType typeOne = (RefLikeType) tn1.origLock
0395: .getType();
0396: RefLikeType typeTwo = (RefLikeType) tn2.origLock
0397: .getType();
0398: classOne = (typeOne instanceof RefType) ? ((RefType) typeOne)
0399: .getSootClass()
0400: : null;
0401: classTwo = (typeTwo instanceof RefType) ? ((RefType) typeTwo)
0402: .getSootClass()
0403: : null;
0404: if (classOne != null && classTwo != null) {
0405: Hierarchy h = Scene.v()
0406: .getActiveHierarchy();
0407: if (classOne.isInterface()) {
0408: if (classTwo.isInterface()) {
0409: typeCompatible = h
0410: .getSubinterfacesOfIncluding(
0411: classOne)
0412: .contains(classTwo)
0413: || h
0414: .getSubinterfacesOfIncluding(
0415: classTwo)
0416: .contains(
0417: classOne);
0418: } else {
0419: typeCompatible = h
0420: .getImplementersOf(
0421: classOne)
0422: .contains(classTwo);
0423: }
0424: } else {
0425: if (classTwo.isInterface()) {
0426: typeCompatible = h
0427: .getImplementersOf(
0428: classTwo)
0429: .contains(classOne);
0430: } else {
0431: typeCompatible = (classOne != null
0432: && Scene
0433: .v()
0434: .getActiveHierarchy()
0435: .getSubclassesOfIncluding(
0436: classOne)
0437: .contains(
0438: classTwo) || classTwo != null
0439: && Scene
0440: .v()
0441: .getActiveHierarchy()
0442: .getSubclassesOfIncluding(
0443: classTwo)
0444: .contains(
0445: classOne));
0446: }
0447: }
0448: }
0449: }
0450: if ((!optionLeaveOriginalLocks && (tn1.write
0451: .hasNonEmptyIntersection(tn2.write)
0452: || tn1.write
0453: .hasNonEmptyIntersection(tn2.read) || tn1.read
0454: .hasNonEmptyIntersection(tn2.write)))
0455: || (optionLeaveOriginalLocks
0456: && typeCompatible && (optionIncludeEmptyPossibleEdges || !emptyEdge))) {
0457: // Determine the size of the intersection for GraphViz output
0458: CodeBlockRWSet rw = null;
0459: int size;
0460: if (optionLeaveOriginalLocks) {
0461: rw = new CodeBlockRWSet();
0462: size = emptyEdge ? 0 : 1;
0463: } else {
0464: rw = tn1.write.intersection(tn2.write);
0465: rw.union(tn1.write
0466: .intersection(tn2.read));
0467: rw.union(tn1.read
0468: .intersection(tn2.write));
0469: size = rw.size();
0470: }
0471:
0472: // Record this
0473: tn1.edges
0474: .add(new TransactionDataDependency(
0475: tn2, size, rw));
0476: // Don't add opposite... all n^2 pairs will be visited separately
0477:
0478: if (size > 0) {
0479: // if tn1 already is in a group
0480: if (tn1.setNumber > 0) {
0481: // if tn2 is NOT already in a group
0482: if (tn2.setNumber == 0) {
0483: tn1.group.add(tn2);
0484: }
0485: // if tn2 is already in a group
0486: else if (tn2.setNumber > 0) {
0487: if (tn1.setNumber != tn2.setNumber) // if they are equal, then they are already in the same group!
0488: {
0489: tn1.group
0490: .mergeGroups(tn2.group);
0491: }
0492: }
0493: }
0494: // if tn1 is NOT already in a group
0495: else if (tn1.setNumber == 0) {
0496: // if tn2 is NOT already in a group
0497: if (tn2.setNumber == 0) {
0498: TransactionGroup newGroup = new TransactionGroup(
0499: nextGroup);
0500: newGroup.add(tn1);
0501: newGroup.add(tn2);
0502: groups.add(newGroup);
0503: nextGroup++;
0504: }
0505: // if tn2 is already in a group
0506: else if (tn2.setNumber > 0) {
0507: tn2.group.add(tn1);
0508: }
0509: }
0510: }
0511: }
0512: }
0513: // If, after comparing to all other transactions, we have no group:
0514: if (tn1.setNumber == 0) {
0515: tn1.setNumber = -1; // delete transactional region
0516: }
0517: }
0518: }
0519: }
0520:
0521: // *** Detect the Possibility of Deadlock ***
0522: TransitiveTargets tt = new TransitiveTargets(Scene.v()
0523: .getCallGraph(), new Filter(
0524: new TransactionVisibleEdgesPred(null)));
0525: if (!optionUseLocksets) // deadlock detection for all single-lock-per-region allocations
0526: {
0527: MutableDirectedGraph lockOrder;
0528: boolean foundDeadlock;
0529: do {
0530: G.v().out
0531: .println("[wjtp.tn] *** Detect the Possibility of Deadlock *** "
0532: + (new Date()));
0533: foundDeadlock = false;
0534: lockOrder = new HashMutableDirectedGraph(); // start each iteration with a fresh graph
0535:
0536: // Assemble the partial ordering of locks
0537: Iterator<Transaction> deadlockIt1 = AllTransactions
0538: .iterator();
0539: while (deadlockIt1.hasNext() && !foundDeadlock) {
0540: Transaction tn1 = deadlockIt1.next();
0541:
0542: // skip if unlocked
0543: if (tn1.setNumber <= 0)
0544: continue;
0545:
0546: // add a node for this set
0547: if (!lockOrder.containsNode(tn1.group)) {
0548: lockOrder.addNode(tn1.group);
0549: }
0550:
0551: // Get list of tn1's target methods
0552: if (tn1.transitiveTargets == null) {
0553: tn1.transitiveTargets = new HashSet<MethodOrMethodContext>();
0554: Iterator<Object> tn1InvokeIt = tn1.invokes
0555: .iterator();
0556: while (tn1InvokeIt.hasNext()) {
0557: Unit tn1Invoke = (Unit) tn1InvokeIt.next();
0558: Iterator<MethodOrMethodContext> targetIt = tt
0559: .iterator(tn1Invoke);
0560: while (targetIt.hasNext())
0561: tn1.transitiveTargets.add(targetIt
0562: .next());
0563: }
0564: }
0565:
0566: // compare to each other tn
0567: Iterator<Transaction> deadlockIt2 = AllTransactions
0568: .iterator();
0569: while (deadlockIt2.hasNext() && !foundDeadlock) {
0570: Transaction tn2 = deadlockIt2.next();
0571:
0572: // skip if unlocked or in same set as tn1
0573: if (tn2.setNumber <= 0
0574: || tn2.setNumber == tn1.setNumber) // this is wrong... dynamic locks in same group can be diff locks
0575: continue;
0576:
0577: // add a node for this set
0578: if (!lockOrder.containsNode(tn2.group)) {
0579: lockOrder.addNode(tn2.group);
0580: }
0581:
0582: if (tn1.transitiveTargets.contains(tn2.method)
0583: && !foundDeadlock) {
0584: // This implies the partial ordering tn1lock before tn2lock
0585: if (optionPrintDebug) {
0586: G.v().out.println("group"
0587: + (tn1.setNumber)
0588: + " before group"
0589: + (tn2.setNumber) + ": "
0590: + "outer: " + tn1.name
0591: + " inner: " + tn2.name);
0592: }
0593:
0594: // Check if tn2lock before tn1lock is in our lock order
0595: List afterTn2 = new ArrayList();
0596: afterTn2.addAll(lockOrder
0597: .getSuccsOf(tn2.group));
0598: for (int i = 0; i < afterTn2.size(); i++) {
0599: List succs = lockOrder
0600: .getSuccsOf(afterTn2.get(i));
0601: for (Object o : succs) {
0602: if (!afterTn2.contains(o))
0603: afterTn2.add(o);
0604: }
0605: }
0606:
0607: if (afterTn2.contains(tn1.group)) {
0608: if (!optionAvoidDeadlock) {
0609: G.v().out
0610: .println("[wjtp.tn] DEADLOCK HAS BEEN DETECTED: not correcting");
0611: foundDeadlock = true;
0612: } else {
0613: G.v().out
0614: .println("[wjtp.tn] DEADLOCK HAS BEEN DETECTED: merging group"
0615: + (tn1.setNumber)
0616: + " and group"
0617: + (tn2.setNumber)
0618: + " and restarting deadlock detection");
0619:
0620: if (optionPrintDebug) {
0621: G.v().out
0622: .println("tn1.setNumber was "
0623: + tn1.setNumber
0624: + " and tn2.setNumber was "
0625: + tn2.setNumber);
0626: G.v().out
0627: .println("tn1.group.size was "
0628: + tn1.group.transactions
0629: .size()
0630: + " and tn2.group.size was "
0631: + tn2.group.transactions
0632: .size());
0633: G.v().out
0634: .println("tn1.group.num was "
0635: + tn1.group
0636: .num()
0637: + " and tn2.group.num was "
0638: + tn2.group
0639: .num());
0640: }
0641: tn1.group.mergeGroups(tn2.group);
0642: if (optionPrintDebug) {
0643: G.v().out
0644: .println("tn1.setNumber is "
0645: + tn1.setNumber
0646: + " and tn2.setNumber is "
0647: + tn2.setNumber);
0648: G.v().out
0649: .println("tn1.group.size is "
0650: + tn1.group.transactions
0651: .size()
0652: + " and tn2.group.size is "
0653: + tn2.group.transactions
0654: .size());
0655: }
0656:
0657: foundDeadlock = true;
0658: }
0659: }
0660:
0661: lockOrder.addEdge(tn1.group, tn2.group);
0662: }
0663: }
0664: }
0665: } while (foundDeadlock && optionAvoidDeadlock);
0666: }
0667:
0668: // *** Calculate Locking Objects ***
0669: // Get a list of all dependencies for each group
0670: G.v().out
0671: .println("[wjtp.tn] *** Calculate Locking Objects *** "
0672: + (new Date()));
0673: RWSet rws[] = new CodeBlockRWSet[nextGroup - 1];
0674: for (int group = 0; group < nextGroup - 1; group++)
0675: rws[group] = new CodeBlockRWSet();
0676: if (!optionStaticLocks) {
0677: // THIS SHOULD BE REMOVED AND REPLACED WITH A PER-TRANSACTION CONTRIBUTING RWSET
0678: Iterator<Transaction> tnIt8 = AllTransactions.iterator();
0679: while (tnIt8.hasNext()) {
0680: Transaction tn = tnIt8.next();
0681: if (tn.setNumber <= 0)
0682: continue;
0683: Iterator<TransactionDataDependency> EdgeIt = tn.edges
0684: .iterator();
0685: while (EdgeIt.hasNext()) {
0686: TransactionDataDependency tdd = EdgeIt.next();
0687: rws[tn.setNumber - 1].union(tdd.rw);
0688: }
0689: }
0690: }
0691:
0692: // Inspect each group's RW dependencies to determine if there's a possibility
0693: // of a shared lock object (if all dependencies are fields/localobjs of the same object)
0694: if (optionStaticLocks) {
0695: // Allocate one new static lock for each group.
0696: for (int group = 0; group < nextGroup - 1; group++) {
0697: TransactionGroup tnGroup = groups.get(group + 1);
0698: tnGroup.isDynamicLock = false;
0699: tnGroup.useDynamicLock = false;
0700: tnGroup.lockObject = null;
0701: }
0702: } else if (optionLeaveOriginalLocks) {
0703: // This mode is treated similarly to dynamic allocation: one lock per group, could be static or dynamic.
0704: // However, instead of finding the lock, we already have it, and need to figure out if it's static or not.
0705: for (int group = 0; group < nextGroup - 1; group++) {
0706: TransactionGroup tnGroup = groups.get(group + 1);
0707: tnGroup.isDynamicLock = false; // assume it's a static lock... then try to prove otherwise
0708: tnGroup.useDynamicLock = false;
0709: tnGroup.lockObject = null;
0710: }
0711:
0712: // if for any lock there is any def to anything other than a static field, then it's a local lock.
0713: // for each transaction, check every def of the lock
0714: Iterator<Transaction> tnAIt = AllTransactions.iterator();
0715: while (tnAIt.hasNext()) {
0716: Transaction tn = tnAIt.next();
0717: if (tn.setNumber <= 0)
0718: continue;
0719: ExceptionalUnitGraph egraph = new ExceptionalUnitGraph(
0720: tn.method.retrieveActiveBody());
0721: SmartLocalDefs sld = new SmartLocalDefs(egraph,
0722: new SimpleLiveLocals(egraph));
0723: if (tn.origLock == null
0724: || !(tn.origLock instanceof Local)) // || tn.begin == null)
0725: continue;
0726: List<Unit> rDefs = sld.getDefsOfAt((Local) tn.origLock,
0727: tn.entermonitor);
0728: if (rDefs == null)
0729: continue;
0730: Iterator<Unit> rDefsIt = rDefs.iterator();
0731: while (rDefsIt.hasNext()) {
0732: Stmt next = (Stmt) rDefsIt.next();
0733: if (next instanceof DefinitionStmt) {
0734: Value rightOp = ((DefinitionStmt) next)
0735: .getRightOp();
0736: if (rightOp instanceof FieldRef) {
0737: if (((FieldRef) rightOp).getField()
0738: .isStatic()) {
0739: // lock may be static
0740: tn.group.lockObject = rightOp;
0741: } else {
0742: // this lock must be dynamic
0743: tn.group.isDynamicLock = true;
0744: tn.group.useDynamicLock = true;
0745: tn.group.lockObject = tn.origLock;
0746: }
0747: } else {
0748: // this lock is probably dynamic (but it's hard to tell for sure)
0749: tn.group.isDynamicLock = true;
0750: tn.group.useDynamicLock = true;
0751: tn.group.lockObject = tn.origLock;
0752: }
0753: } else {
0754: // this lock is probably dynamic (but it's hard to tell for sure)
0755: tn.group.isDynamicLock = true;
0756: tn.group.useDynamicLock = true;
0757: tn.group.lockObject = tn.origLock;
0758: }
0759: }
0760: }
0761: } else // for locksets and dynamic locks
0762: {
0763: for (int group = 0; group < nextGroup - 1; group++) {
0764: TransactionGroup tnGroup = groups.get(group + 1);
0765:
0766: if (optionUseLocksets) {
0767: tnGroup.useLocksets = true; // initially, guess that this is true
0768: } else {
0769: tnGroup.isDynamicLock = (rws[group].getGlobals()
0770: .size() == 0);
0771: tnGroup.useDynamicLock = true;
0772: tnGroup.lockObject = null;
0773: }
0774:
0775: // empty groups don't get locks
0776: if (rws[group].size() <= 0) // There are no transactions in this group
0777: {
0778: if (optionUseLocksets) {
0779: tnGroup.useLocksets = false;
0780: } else {
0781: tnGroup.isDynamicLock = false;
0782: tnGroup.useDynamicLock = false;
0783: }
0784: continue;
0785: }
0786: }
0787: }
0788:
0789: // Find runtime lock objects (if using dynamic locks or locksets)
0790: Map<Value, Integer> lockToLockNum = null;
0791: List<PointsToSetInternal> lockPTSets = null;
0792: if (!optionOneGlobalLock && !optionStaticLocks
0793: && !optionLeaveOriginalLocks) {
0794: // Data structures for determining lock numbers
0795: lockPTSets = new ArrayList<PointsToSetInternal>();
0796: lockToLockNum = new HashMap<Value, Integer>();
0797:
0798: // For each transaction, if the group's R/Ws may be fields of the same object,
0799: // then check for the transaction if they must be fields of the same RUNTIME OBJECT
0800: Iterator<Transaction> tnIt9 = AllTransactions.iterator();
0801: while (tnIt9.hasNext()) {
0802: Transaction tn = tnIt9.next();
0803:
0804: int group = tn.setNumber - 1;
0805: if (group < 0)
0806: continue;
0807:
0808: if (tn.group.useDynamicLock || tn.group.useLocksets) // if attempting to use a dynamic lock or locksets
0809: {
0810:
0811: // Get list of objects (FieldRef or Local) to be locked (lockset analysis)
0812: G.v().out.println("[wjtp.tn] * " + tn.name + " *");
0813: LocksetAnalysis la = new LocksetAnalysis(
0814: new BriefUnitGraph(tn.method
0815: .retrieveActiveBody()));
0816: tn.lockset = la.getLocksetOf(tasea, rws[group], tn);
0817:
0818: // Determine if list is suitable for the selected locking scheme
0819: // TODO check for nullness
0820: if (optionUseLocksets) {
0821: // Post-process the locksets
0822: if (tn.lockset == null
0823: || tn.lockset.size() <= 0) {
0824: // If the lockset is invalid, revert the entire group to static locks:
0825: tn.group.useLocksets = false;
0826:
0827: // Create a lockset containing a single placeholder static lock for each tn in the group
0828: Value newStaticLock = new NewStaticLock(
0829: tn.method.getDeclaringClass());
0830: EquivalentValue newStaticLockEqVal = new EquivalentValue(
0831: newStaticLock);
0832: for (Transaction groupTn : tn.group) {
0833: groupTn.lockset = new ArrayList<EquivalentValue>();
0834: groupTn.lockset.add(newStaticLockEqVal);
0835: }
0836:
0837: // Assign a lock number to the placeholder
0838: Integer lockNum = new Integer(-lockPTSets
0839: .size()); // negative indicates a static lock
0840: G.v().out.println("[wjtp.tn] Lock: num "
0841: + lockNum + " type "
0842: + newStaticLock.getType() + " obj "
0843: + newStaticLock);
0844: lockToLockNum.put(newStaticLockEqVal,
0845: lockNum);
0846: lockToLockNum.put(newStaticLock, lockNum);
0847: PointsToSetInternal dummyLockPT = new HashPointsToSet(
0848: newStaticLock.getType(), (PAG) pta); // KILLS CHA-BASED ANALYSIS (pointer exception)
0849: lockPTSets.add(dummyLockPT);
0850: } else {
0851: // If the lockset is valid
0852: // Assign a lock number for each lock in the lockset
0853: for (EquivalentValue lockEqVal : tn.lockset) {
0854: Value lock = lockEqVal.getValue();
0855:
0856: // Get reaching objects for this lock
0857: PointsToSetInternal lockPT;
0858: if (lock instanceof Local)
0859: lockPT = (PointsToSetInternal) pta
0860: .reachingObjects((Local) lock);
0861: else if (lock instanceof StaticFieldRef) // needs special treatment: could be primitive
0862: lockPT = null;
0863: else if (lock instanceof InstanceFieldRef) {
0864: Local base = (Local) ((InstanceFieldRef) lock)
0865: .getBase();
0866: if (base instanceof FakeJimpleLocal)
0867: lockPT = (PointsToSetInternal) pta
0868: .reachingObjects(
0869: ((FakeJimpleLocal) base)
0870: .getRealLocal(),
0871: ((FieldRef) lock)
0872: .getField());
0873: else
0874: lockPT = (PointsToSetInternal) pta
0875: .reachingObjects(
0876: base,
0877: ((FieldRef) lock)
0878: .getField());
0879: } else if (lock instanceof NewStaticLock) // placeholder for anything that needs a static lock
0880: lockPT = null;
0881: else
0882: lockPT = null;
0883:
0884: if (lockPT != null) {
0885: // Assign an existing lock number if possible
0886: boolean foundLock = false;
0887: for (int i = 0; i < lockPTSets
0888: .size(); i++) {
0889: PointsToSetInternal otherLockPT = lockPTSets
0890: .get(i);
0891: if (lockPT
0892: .hasNonEmptyIntersection(otherLockPT)) // will never happen for empty, negative numbered sets
0893: {
0894: G.v().out
0895: .println("[wjtp.tn] Lock: num "
0896: + i
0897: + " type "
0898: + lock
0899: .getType()
0900: + " obj "
0901: + lock);
0902: lockToLockNum.put(lock,
0903: new Integer(i));
0904: otherLockPT.addAll(lockPT,
0905: null);
0906: foundLock = true;
0907: break;
0908: }
0909: }
0910:
0911: // Assign a brand new lock number otherwise
0912: if (!foundLock) {
0913: G.v().out
0914: .println("[wjtp.tn] Lock: num "
0915: + lockPTSets
0916: .size()
0917: + " type "
0918: + lock
0919: .getType()
0920: + " obj "
0921: + lock);
0922: lockToLockNum.put(lock,
0923: new Integer(lockPTSets
0924: .size()));
0925: PointsToSetInternal otherLockPT = new HashPointsToSet(
0926: lockPT.getType(),
0927: (PAG) pta);
0928: lockPTSets.add(otherLockPT);
0929: otherLockPT
0930: .addAll(lockPT, null);
0931: }
0932: } else // static field locks and pathological cases...
0933: {
0934: // Assign an existing lock number if possible
0935: if (lockToLockNum.get(lockEqVal) != null) {
0936: Integer lockNum = lockToLockNum
0937: .get(lockEqVal);
0938: G.v().out
0939: .println("[wjtp.tn] Lock: num "
0940: + lockNum
0941: + " type "
0942: + lock
0943: .getType()
0944: + " obj "
0945: + lock);
0946: lockToLockNum
0947: .put(lock, lockNum);
0948: } else {
0949: Integer lockNum = new Integer(
0950: -lockPTSets.size()); // negative indicates a static lock
0951: G.v().out
0952: .println("[wjtp.tn] Lock: num "
0953: + lockNum
0954: + " type "
0955: + lock
0956: .getType()
0957: + " obj "
0958: + lock);
0959: lockToLockNum.put(lockEqVal,
0960: lockNum);
0961: lockToLockNum
0962: .put(lock, lockNum);
0963: PointsToSetInternal dummyLockPT = new HashPointsToSet(
0964: lock.getType(),
0965: (PAG) pta);
0966: lockPTSets.add(dummyLockPT);
0967: }
0968: }
0969: }
0970:
0971: }
0972: } else {
0973: if (tn.lockset == null
0974: || tn.lockset.size() != 1) {// Found too few or too many locks
0975: // So use a static lock instead
0976: tn.lockObject = null;
0977: tn.group.useDynamicLock = false;
0978: tn.group.lockObject = null;
0979: } else {// Found exactly one lock
0980: // Use it!
0981: tn.lockObject = (Value) tn.lockset.get(0);
0982:
0983: // If it's the best lock we've found in the group yet, use it for display
0984: if (tn.group.lockObject == null
0985: || tn.lockObject instanceof Ref)
0986: tn.group.lockObject = tn.lockObject;
0987: }
0988: }
0989: }
0990: }
0991: if (optionUseLocksets) {
0992: // If any lock has only a singleton reaching object, treat it like a static lock
0993: for (int i = 0; i < lockPTSets.size(); i++) {
0994: PointsToSetInternal pts = lockPTSets.get(i);
0995: if (pts.size() == 1 && false) // isSingleton(pts)) // It's NOT easy to find a singleton: single alloc node must be run just once
0996: {
0997: for (Object e : lockToLockNum.entrySet()) {
0998: Map.Entry entry = (Map.Entry) e;
0999: Integer value = (Integer) entry.getValue();
1000: if (value == i) {
1001: entry.setValue(new Integer(-i));
1002: }
1003: }
1004: }
1005: }
1006: }
1007: }
1008:
1009: // print out locksets
1010: if (optionUseLocksets) {
1011: for (Transaction tn : AllTransactions) {
1012: if (tn.group != null) {
1013: G.v().out.println("[wjtp.tn] "
1014: + tn.name
1015: + " lockset: "
1016: + locksetToLockNumString(tn.lockset,
1017: lockToLockNum)
1018: + (tn.group.useLocksets ? ""
1019: : " (placeholder)"));
1020: }
1021: }
1022: }
1023:
1024: // *** Detect the Possibility of Deadlock for Locksets ***
1025: MutableEdgeLabelledDirectedGraph permanentOrder = new HashMutableEdgeLabelledDirectedGraph();
1026: MutableEdgeLabelledDirectedGraph lockOrder = null;
1027: if (optionUseLocksets) // deadlock detection and lock ordering for lockset allocations
1028: {
1029: boolean foundDeadlock;
1030: do {
1031: G.v().out
1032: .println("[wjtp.tn] *** Detect "
1033: + (optionAvoidDeadlock ? "and Correct "
1034: : "")
1035: + "the Possibility of Deadlock for Locksets *** "
1036: + (new Date()));
1037: foundDeadlock = false;
1038: lockOrder = (HashMutableEdgeLabelledDirectedGraph) ((HashMutableEdgeLabelledDirectedGraph) permanentOrder)
1039: .clone(); // start each iteration with a fresh copy of the permanent orders
1040:
1041: // Assemble the partial ordering of locks
1042: Iterator<Transaction> deadlockIt1 = AllTransactions
1043: .iterator();
1044: while (deadlockIt1.hasNext() && !foundDeadlock) {
1045: Transaction tn1 = deadlockIt1.next();
1046:
1047: // skip if unlocked
1048: if (tn1.group == null)
1049: continue;
1050:
1051: // add a node for each lock in this lockset
1052: for (EquivalentValue lockEqVal : tn1.lockset) {
1053: Value lock = lockEqVal.getValue();
1054:
1055: if (!lockOrder.containsNode(lockToLockNum
1056: .get(lock)))
1057: lockOrder.addNode(lockToLockNum.get(lock));
1058: }
1059:
1060: // Get list of tn1's target methods
1061: if (tn1.transitiveTargets == null) {
1062: tn1.transitiveTargets = new HashSet<MethodOrMethodContext>();
1063: Iterator<Object> tn1InvokeIt = tn1.invokes
1064: .iterator();
1065: while (tn1InvokeIt.hasNext()) {
1066: Unit tn1Invoke = (Unit) tn1InvokeIt.next();
1067: Iterator<MethodOrMethodContext> targetIt = tt
1068: .iterator(tn1Invoke);
1069: while (targetIt.hasNext())
1070: tn1.transitiveTargets.add(targetIt
1071: .next());
1072: }
1073: }
1074:
1075: // compare to each other tn
1076: Iterator<Transaction> deadlockIt2 = AllTransactions
1077: .iterator();
1078: while (deadlockIt2.hasNext() && !foundDeadlock) {
1079: Transaction tn2 = deadlockIt2.next();
1080:
1081: // skip if unlocked
1082: if (tn2.group == null)
1083: continue;
1084:
1085: // add a node for each lock in this lockset
1086: for (EquivalentValue lockEqVal : tn2.lockset) {
1087: Value lock = lockEqVal.getValue();
1088:
1089: if (!lockOrder.containsNode(lockToLockNum
1090: .get(lock)))
1091: lockOrder.addNode(lockToLockNum
1092: .get(lock));
1093: }
1094:
1095: if (tn1.transitiveTargets.contains(tn2.method)
1096: && !foundDeadlock) {
1097: // This implies the partial ordering (locks in tn1) before (locks in tn2)
1098: if (true) //optionPrintDebug)
1099: {
1100: G.v().out.println("locks in "
1101: + (tn1.name)
1102: + " before locks in "
1103: + (tn2.name) + ": " + "outer: "
1104: + tn1.name + " inner: "
1105: + tn2.name);
1106: }
1107:
1108: // Check if tn2locks before tn1locks is in our lock order
1109: for (EquivalentValue lock2EqVal : tn2.lockset) {
1110: Value lock2 = lock2EqVal.getValue();
1111: Integer lock2Num = lockToLockNum
1112: .get(lock2);
1113:
1114: List afterTn2 = new ArrayList();
1115: afterTn2.addAll(lockOrder
1116: .getSuccsOf(lock2Num)); // filter here!
1117: ListIterator lit = afterTn2
1118: .listIterator();
1119: while (lit.hasNext()) {
1120: Integer to = (Integer) lit.next(); // node the edges go to
1121: List labels = lockOrder
1122: .getLabelsForEdges(
1123: lock2Num, to);
1124: boolean keep = false;
1125: if (labels != null) // this shouldn't really happen... is something wrong with the edge-labelled graph?
1126: {
1127: for (Object l : labels) {
1128: Transaction labelTn = (Transaction) l;
1129:
1130: // Check if labelTn and tn1 share a static lock
1131: boolean tnsShareAStaticLock = false;
1132: for (EquivalentValue tn1LockEqVal : tn1.lockset) {
1133: Integer tn1LockNum = lockToLockNum
1134: .get(tn1LockEqVal
1135: .getValue());
1136: if (tn1LockNum < 0) {
1137: // this is a static lock... see if some lock in labelTn has the same #
1138: for (EquivalentValue labelTnLockEqVal : labelTn.lockset) {
1139: if (lockToLockNum
1140: .get(labelTnLockEqVal
1141: .getValue()) == tn1LockNum) {
1142: tnsShareAStaticLock = true;
1143: }
1144: }
1145: }
1146: }
1147:
1148: if (!tnsShareAStaticLock) // !hasStaticLockInCommon(tn1, labelTn))
1149: {
1150: keep = true;
1151: break;
1152: }
1153: }
1154: }
1155: if (!keep)
1156: lit.remove();
1157: }
1158:
1159: /* for( int i = 0; i < afterTn2.size(); i++ )
1160: {
1161: List succs = lockOrder.getSuccsOf(afterTn2.get(i)); // but not here
1162: for( Object o : succs )
1163: {
1164: if(!afterTn2.contains(o))
1165: afterTn2.add(o);
1166: }
1167: }
1168: */
1169:
1170: for (EquivalentValue lock1EqVal : tn1.lockset) {
1171: Value lock1 = lock1EqVal.getValue();
1172: Integer lock1Num = lockToLockNum
1173: .get(lock1);
1174:
1175: if ((lock1Num != lock2Num || lock1Num > 0)
1176: && afterTn2
1177: .contains(lock1Num)) {
1178: if (!optionAvoidDeadlock) {
1179: G.v().out
1180: .println("[wjtp.tn] DEADLOCK HAS BEEN DETECTED: not correcting");
1181: foundDeadlock = true;
1182: } else {
1183: G.v().out
1184: .println("[wjtp.tn] DEADLOCK HAS BEEN DETECTED while inspecting "
1185: + lock1Num
1186: + " ("
1187: + lock1
1188: + ") and "
1189: + lock2Num
1190: + " ("
1191: + lock2
1192: + ") ");
1193:
1194: // Create a deadlock avoidance edge
1195: DeadlockAvoidanceEdge dae = new DeadlockAvoidanceEdge(
1196: tn1.method
1197: .getDeclaringClass());
1198: EquivalentValue daeEqVal = new EquivalentValue(
1199: dae);
1200:
1201: // Register it as a static lock
1202: Integer daeNum = new Integer(
1203: -lockPTSets.size()); // negative indicates a static lock
1204: permanentOrder
1205: .addNode(daeNum);
1206: lockToLockNum.put(dae,
1207: daeNum);
1208: PointsToSetInternal dummyLockPT = new HashPointsToSet(
1209: lock1.getType(),
1210: (PAG) pta);
1211: lockPTSets.add(dummyLockPT);
1212:
1213: // Add it to the locksets of tn1 and whoever says l2 before l1
1214: for (EquivalentValue lockEqVal : tn1.lockset) {
1215: Integer lockNum = lockToLockNum
1216: .get(lockEqVal
1217: .getValue());
1218: if (!permanentOrder
1219: .containsNode(lockNum))
1220: permanentOrder
1221: .addNode(lockNum);
1222: permanentOrder.addEdge(
1223: daeNum,
1224: lockNum, tn1);
1225: }
1226: tn1.lockset.add(daeEqVal);
1227:
1228: List forwardLabels = lockOrder
1229: .getLabelsForEdges(
1230: lock1Num,
1231: lock2Num);
1232: if (forwardLabels != null) {
1233: for (Object t : forwardLabels) {
1234: Transaction tn = (Transaction) t;
1235: if (!tn.lockset
1236: .contains(daeEqVal)) {
1237: for (EquivalentValue lockEqVal : tn.lockset) {
1238: Integer lockNum = lockToLockNum
1239: .get(lockEqVal
1240: .getValue());
1241: if (!permanentOrder
1242: .containsNode(lockNum))
1243: permanentOrder
1244: .addNode(lockNum);
1245: permanentOrder
1246: .addEdge(
1247: daeNum,
1248: lockNum,
1249: tn);
1250: }
1251: tn.lockset
1252: .add(daeEqVal);
1253: }
1254: }
1255: }
1256:
1257: List backwardLabels = lockOrder
1258: .getLabelsForEdges(
1259: lock2Num,
1260: lock1Num);
1261: if (backwardLabels != null) {
1262: for (Object t : backwardLabels) {
1263: Transaction tn = (Transaction) t;
1264: if (!tn.lockset
1265: .contains(daeEqVal)) {
1266: for (EquivalentValue lockEqVal : tn.lockset) {
1267: Integer lockNum = lockToLockNum
1268: .get(lockEqVal
1269: .getValue());
1270: if (!permanentOrder
1271: .containsNode(lockNum))
1272: permanentOrder
1273: .addNode(lockNum);
1274: permanentOrder
1275: .addEdge(
1276: daeNum,
1277: lockNum,
1278: tn);
1279: }
1280: tn.lockset
1281: .add(daeEqVal);
1282: G.v().out
1283: .println("[wjtp.tn] Adding deadlock avoidance edge between "
1284: + (tn1.name)
1285: + " and "
1286: + (tn.name));
1287: }
1288: }
1289: G.v().out
1290: .println("[wjtp.tn] Restarting deadlock detection");
1291: }
1292:
1293: foundDeadlock = true;
1294: break;
1295: }
1296: }
1297:
1298: if (lock1Num != lock2Num)
1299: lockOrder.addEdge(lock1Num,
1300: lock2Num, tn1);
1301: }
1302: if (foundDeadlock)
1303: break;
1304: }
1305: }
1306: }
1307: }
1308: } while (foundDeadlock && optionAvoidDeadlock);
1309: ((HashMutableEdgeLabelledDirectedGraph) lockOrder)
1310: .printGraph();
1311:
1312: G.v().out
1313: .println("[wjtp.tn] *** Reorder Locksets to Avoid Deadlock *** "
1314: + (new Date()));
1315: for (Transaction tn : AllTransactions) {
1316: // Get the portion of the lock order that is visible to tn
1317: HashMutableDirectedGraph visibleOrder = new HashMutableDirectedGraph();
1318: if (tn.group != null) {
1319: for (Transaction otherTn : AllTransactions) {
1320: // Check if otherTn and tn share a static lock
1321: boolean tnsShareAStaticLock = false;
1322: for (EquivalentValue tnLockEqVal : tn.lockset) {
1323: Integer tnLockNum = lockToLockNum
1324: .get(tnLockEqVal.getValue());
1325: if (tnLockNum < 0) {
1326: // this is a static lock... see if some lock in labelTn has the same #
1327: if (otherTn.group != null) {
1328: for (EquivalentValue otherTnLockEqVal : otherTn.lockset) {
1329: if (lockToLockNum
1330: .get(otherTnLockEqVal
1331: .getValue()) == tnLockNum) {
1332: tnsShareAStaticLock = true;
1333: }
1334: }
1335: } else
1336: tnsShareAStaticLock = true; // not really... but we want to skip this one
1337: }
1338: }
1339:
1340: if (!tnsShareAStaticLock || tn == otherTn) // if tns don't share any static lock, or if tns are the same one
1341: {
1342: // add these orderings to tn's visible order
1343: MutableDirectedGraph orderings = lockOrder
1344: .getEdgesForLabel(otherTn);
1345: for (Object node1 : orderings.getNodes()) {
1346: if (!visibleOrder.containsNode(node1))
1347: visibleOrder.addNode(node1);
1348: for (Object node2 : orderings
1349: .getSuccsOf(node1)) {
1350: if (!visibleOrder
1351: .containsNode(node2))
1352: visibleOrder.addNode(node2);
1353: visibleOrder.addEdge(node1, node2);
1354: }
1355: }
1356: }
1357: }
1358:
1359: G.v().out.println("VISIBLE ORDER FOR " + tn.name);
1360: visibleOrder.printGraph();
1361:
1362: // Order locks in tn's lockset according to the visible order (insertion sort)
1363: List<EquivalentValue> newLockset = new ArrayList();
1364: for (EquivalentValue lockEqVal : tn.lockset) {
1365: Value lockToInsert = lockEqVal.getValue();
1366: Integer lockNumToInsert = lockToLockNum
1367: .get(lockToInsert);
1368: int i = 0;
1369: while (i < newLockset.size()) {
1370: EquivalentValue existingLockEqVal = newLockset
1371: .get(i);
1372: Value existingLock = existingLockEqVal
1373: .getValue();
1374: Integer existingLockNum = lockToLockNum
1375: .get(existingLock);
1376: if (visibleOrder.containsEdge(
1377: lockNumToInsert, existingLockNum)
1378: || lockNumToInsert < existingLockNum)
1379: // !visibleOrder.containsEdge(existingLockNum, lockNumToInsert) ) // if(! existing before toinsert )
1380: break;
1381: i++;
1382: }
1383: newLockset.add(i, lockEqVal);
1384: }
1385: G.v().out.println("reordered from "
1386: + locksetToLockNumString(tn.lockset,
1387: lockToLockNum)
1388: + " to "
1389: + locksetToLockNumString(newLockset,
1390: lockToLockNum));
1391:
1392: tn.lockset = newLockset;
1393: }
1394: }
1395: }
1396:
1397: // *** Print Output and Transform Program ***
1398: G.v().out
1399: .println("[wjtp.tn] *** Print Output and Transform Program *** "
1400: + (new Date()));
1401:
1402: // Print topological graph in graphviz format
1403: if (optionPrintGraph) {
1404: printGraph(AllTransactions, groups, lockToLockNum);
1405: }
1406:
1407: // Print table of transaction information
1408: if (optionPrintTable) {
1409: printTable(AllTransactions);
1410: printGroups(AllTransactions, nextGroup, groups, rws);
1411: }
1412:
1413: // For all methods, run the transformer (Pessimistic Transaction Tranformation)
1414: if (!optionLeaveOriginalLocks) {
1415: // BEGIN UGLINESS
1416: TransactionBodyTransformer.addedGlobalLockObj = new boolean[nextGroup];
1417: TransactionBodyTransformer.addedGlobalLockObj[0] = false;
1418: boolean useGlobalLock[] = new boolean[nextGroup - 1];
1419: for (int i = 1; i < nextGroup; i++) {
1420: TransactionGroup tnGroup = groups.get(i);
1421: TransactionBodyTransformer.addedGlobalLockObj[i] = (!optionOneGlobalLock)
1422: && (tnGroup.useDynamicLock || tnGroup.useLocksets);
1423: useGlobalLock[i - 1] = !tnGroup.useDynamicLock
1424: && !tnGroup.useLocksets;
1425: }
1426: // END UGLINESS
1427:
1428: Iterator doTransformClassesIt = Scene.v()
1429: .getApplicationClasses().iterator();
1430: while (doTransformClassesIt.hasNext()) {
1431: SootClass appClass = (SootClass) doTransformClassesIt
1432: .next();
1433: Iterator methodsIt = appClass.getMethods().iterator();
1434: while (methodsIt.hasNext()) {
1435: SootMethod method = (SootMethod) methodsIt.next();
1436: if (method.isConcrete()) {
1437: Body b = method.getActiveBody();
1438:
1439: FlowSet fs = methodToFlowSet.get(method);
1440:
1441: if (fs == null) // newly added methods have no flowset
1442: continue;
1443:
1444: TransactionBodyTransformer.v()
1445: .internalTransform(b, fs, groups);
1446: }
1447: }
1448: }
1449: }
1450: }
1451:
1452: public String locksetToLockNumString(List<EquivalentValue> lockset,
1453: Map<Value, Integer> lockToLockNum) {
1454: if (lockset == null)
1455: return "null";
1456: String ret = "[";
1457: boolean first = true;
1458: for (EquivalentValue lockEqVal : lockset) {
1459: if (!first)
1460: ret = ret + " ";
1461: first = false;
1462: ret = ret + lockToLockNum.get(lockEqVal.getValue());
1463: }
1464: return ret + "]";
1465: }
1466:
1467: public boolean mayHappenInParallel(Transaction tn1, Transaction tn2) {
1468: if (mhp == null) {
1469: if (optionLeaveOriginalLocks)
1470: return true;
1471: ReachableMethods rm = Scene.v().getReachableMethods();
1472: if (!rm.contains(tn1.method) || !rm.contains(tn2.method))
1473: return false;
1474: return true;
1475: }
1476: return mhp.mayHappenInParallel(tn1.method, tn2.method);
1477: }
1478:
1479: public void assignNamesToTransactions(
1480: List<Transaction> AllTransactions) {
1481: // Give each method a unique, deterministic identifier
1482: // Sort transactions into bins... one for each method name
1483:
1484: // Get list of method names
1485: List<String> methodNamesTemp = new ArrayList<String>();
1486: Iterator<Transaction> tnIt5 = AllTransactions.iterator();
1487: while (tnIt5.hasNext()) {
1488: Transaction tn1 = tnIt5.next();
1489: String mname = tn1.method.getSignature(); //tn1.method.getSignature() + "." + tn1.method.getName();
1490: if (!methodNamesTemp.contains(mname))
1491: methodNamesTemp.add(mname);
1492: }
1493: String methodNames[] = new String[1];
1494: methodNames = methodNamesTemp.toArray(methodNames);
1495: Arrays.sort(methodNames);
1496:
1497: // Initialize method-named bins
1498: // this matrix is <# method names> wide and <max txns possible in one method> + 1 tall
1499: int identMatrix[][] = new int[methodNames.length][Transaction.nextIDNum
1500: - methodNames.length + 2];
1501: for (int i = 0; i < methodNames.length; i++) {
1502: identMatrix[i][0] = 0;
1503: for (int j = 1; j < Transaction.nextIDNum
1504: - methodNames.length + 1; j++) {
1505: identMatrix[i][j] = 50000;
1506: }
1507: }
1508:
1509: // Put transactions into bins
1510: Iterator<Transaction> tnIt0 = AllTransactions.iterator();
1511: while (tnIt0.hasNext()) {
1512: Transaction tn1 = tnIt0.next();
1513: int methodNum = Arrays.binarySearch(methodNames, tn1.method
1514: .getSignature());
1515: identMatrix[methodNum][0]++;
1516: identMatrix[methodNum][identMatrix[methodNum][0]] = tn1.IDNum;
1517: }
1518:
1519: // Sort bins by transaction IDNum
1520: // IDNums vary, but always increase in code-order within a method
1521: for (int j = 0; j < methodNames.length; j++) {
1522: identMatrix[j][0] = 0; // set the counter to 0 so it sorts out (into slot 0).
1523: Arrays.sort(identMatrix[j]); // sort this subarray
1524: }
1525:
1526: // Generate a name based on the bin number and location within the bin
1527: Iterator<Transaction> tnIt4 = AllTransactions.iterator();
1528: while (tnIt4.hasNext()) {
1529: Transaction tn1 = tnIt4.next();
1530: int methodNum = Arrays.binarySearch(methodNames, tn1.method
1531: .getSignature());
1532: int tnNum = Arrays.binarySearch(identMatrix[methodNum],
1533: tn1.IDNum) - 1;
1534: tn1.name = "m"
1535: + (methodNum < 10 ? "00" : (methodNum < 100 ? "0"
1536: : "")) + methodNum + "n"
1537: + (tnNum < 10 ? "0" : "") + tnNum;
1538: }
1539: }
1540:
1541: public void printGraph(Collection<Transaction> AllTransactions,
1542: List<TransactionGroup> groups,
1543: Map<Value, Integer> lockToLockNum) {
1544: final String[] colors = { "black", "blue", "blueviolet",
1545: "chartreuse", "crimson", "darkgoldenrod1",
1546: "darkseagreen", "darkslategray", "deeppink",
1547: "deepskyblue1", "firebrick1", "forestgreen", "gold",
1548: "gray80", "navy", "pink", "red", "sienna",
1549: "turquoise1", "yellow" };
1550: Map<Integer, String> lockColors = new HashMap<Integer, String>();
1551: int colorNum = 0;
1552: HashSet<Transaction> visited = new HashSet<Transaction>();
1553:
1554: G.v().out.println("[transaction-graph]"
1555: + (optionUseLocksets ? "" : " strict")
1556: + " graph transactions {"); // "\n[transaction-graph] start=1;");
1557:
1558: for (int group = 0; group < groups.size(); group++) {
1559: boolean printedHeading = false;
1560: Iterator<Transaction> tnIt = AllTransactions.iterator();
1561: while (tnIt.hasNext()) {
1562: Transaction tn = tnIt.next();
1563: if (tn.setNumber == group + 1) {
1564: if (!printedHeading) {
1565: // if(localLock[group] && lockObject[group] != null)
1566: if (tn.group.useDynamicLock
1567: && tn.group.lockObject != null) {
1568: String typeString = "";
1569: // if(lockObject[group].getType() instanceof RefType)
1570: // typeString = ((RefType) lockObject[group].getType()).getSootClass().getShortName();
1571: // else
1572: // typeString = lockObject[group].getType().toString();
1573: if (tn.group.lockObject.getType() instanceof RefType)
1574: typeString = ((RefType) tn.group.lockObject
1575: .getType()).getSootClass()
1576: .getShortName();
1577: else
1578: typeString = tn.group.lockObject
1579: .getType().toString();
1580: G.v().out
1581: .println("[transaction-graph] subgraph cluster_"
1582: + (group + 1)
1583: + " {\n[transaction-graph] color=blue;\n[transaction-graph] label=\"Lock: a \\n"
1584: + typeString + " object\";");
1585: } else if (tn.group.useLocksets) {
1586: G.v().out
1587: .println("[transaction-graph] subgraph cluster_"
1588: + (group + 1)
1589: + " {\n[transaction-graph] color=blue;\n[transaction-graph] label=\"Locksets\";");
1590: } else {
1591: String objString = "";
1592: // if(lockObject[group] == null)
1593: if (tn.group.lockObject == null) {
1594: objString = "lockObj" + (group + 1);
1595: }
1596: // else if(lockObject[group] instanceof FieldRef)
1597: else if (tn.group.lockObject instanceof FieldRef) {
1598: // SootField field = ((FieldRef) lockObject[group]).getField();
1599: SootField field = ((FieldRef) tn.group.lockObject)
1600: .getField();
1601: objString = field.getDeclaringClass()
1602: .getShortName()
1603: + "." + field.getName();
1604: } else
1605: objString = tn.group.lockObject
1606: .toString();
1607: // objString = lockObject[group].toString();
1608: G.v().out
1609: .println("[transaction-graph] subgraph cluster_"
1610: + (group + 1)
1611: + " {\n[transaction-graph] color=blue;\n[transaction-graph] label=\"Lock: \\n"
1612: + objString + "\";");
1613: }
1614: printedHeading = true;
1615: }
1616: if (Scene.v().getReachableMethods().contains(
1617: tn.method))
1618: G.v().out.println("[transaction-graph] "
1619: + tn.name + " [name=\""
1620: + tn.method.toString()
1621: + "\" style=\"setlinewidth(3)\"];");
1622: else
1623: G.v().out
1624: .println("[transaction-graph] "
1625: + tn.name
1626: + " [name=\""
1627: + tn.method.toString()
1628: + "\" color=cadetblue1 style=\"setlinewidth(1)\"];");
1629:
1630: if (tn.group.useLocksets) // print locks instead of dependence edges
1631: {
1632: for (EquivalentValue lockEqVal : tn.lockset) {
1633: Integer lockNum = lockToLockNum
1634: .get(lockEqVal.getValue());
1635: for (Transaction tn2 : tn.group) {
1636: if (!visited.contains(tn2)
1637: && mayHappenInParallel(tn, tn2)) {
1638: for (EquivalentValue lock2EqVal : tn2.lockset) {
1639: Integer lock2Num = lockToLockNum
1640: .get(lock2EqVal
1641: .getValue());
1642: if (lockNum.intValue() == lock2Num
1643: .intValue()) {
1644: // Get the color for this lock
1645: if (!lockColors
1646: .containsKey(lockNum)) {
1647: lockColors
1648: .put(
1649: lockNum,
1650: colors[colorNum
1651: % colors.length]);
1652: colorNum++;
1653: }
1654: String color = lockColors
1655: .get(lockNum);
1656:
1657: // Draw an edge for this lock
1658: G.v().out
1659: .println("[transaction-graph] "
1660: + tn.name
1661: + " -- "
1662: + tn2.name
1663: + " [color="
1664: + color
1665: + " style="
1666: + (lockNum >= 0 ? "dashed"
1667: : "solid")
1668: + " exactsize=1 style=\"setlinewidth(3)\"];");
1669: }
1670: }
1671: }
1672: }
1673: visited.add(tn);
1674: }
1675: } else {
1676: Iterator<TransactionDataDependency> tnedgeit = tn.edges
1677: .iterator();
1678: while (tnedgeit.hasNext()) {
1679: TransactionDataDependency edge = tnedgeit
1680: .next();
1681: Transaction tnedge = edge.other;
1682: if (tnedge.setNumber == group + 1)
1683: G.v().out
1684: .println("[transaction-graph] "
1685: + tn.name
1686: + " -- "
1687: + tnedge.name
1688: + " [color="
1689: + (edge.size > 0 ? "black"
1690: : "cadetblue1")
1691: + " style="
1692: + (tn.setNumber > 0
1693: && tn.group.useDynamicLock ? "dashed"
1694: : "solid")
1695: + " exactsize="
1696: + edge.size
1697: + " style=\"setlinewidth(3)\"];");
1698: }
1699: }
1700: }
1701:
1702: }
1703: if (printedHeading)
1704: G.v().out.println("[transaction-graph] }");
1705: }
1706:
1707: // Print nodes with no group
1708: {
1709: boolean printedHeading = false;
1710: Iterator<Transaction> tnIt = AllTransactions.iterator();
1711: while (tnIt.hasNext()) {
1712: Transaction tn = tnIt.next();
1713: if (tn.setNumber == -1) {
1714: if (!printedHeading) {
1715: // putting these nodes in a "source" ranked subgraph makes them appear above all the clusters
1716: G.v().out
1717: .println("[transaction-graph] subgraph lone {\n[transaction-graph] rank=source;");
1718: printedHeading = true;
1719: }
1720: if (Scene.v().getReachableMethods().contains(
1721: tn.method))
1722: G.v().out.println("[transaction-graph] "
1723: + tn.name + " [name=\""
1724: + tn.method.toString()
1725: + "\" style=\"setlinewidth(3)\"];");
1726: else
1727: G.v().out
1728: .println("[transaction-graph] "
1729: + tn.name
1730: + " [name=\""
1731: + tn.method.toString()
1732: + "\" color=cadetblue1 style=\"setlinewidth(1)\"];");
1733:
1734: Iterator<TransactionDataDependency> tnedgeit = tn.edges
1735: .iterator();
1736: while (tnedgeit.hasNext()) {
1737: TransactionDataDependency edge = tnedgeit
1738: .next();
1739: Transaction tnedge = edge.other;
1740: if (tnedge.setNumber != tn.setNumber
1741: || tnedge.setNumber == -1)
1742: G.v().out
1743: .println("[transaction-graph] "
1744: + tn.name
1745: + " -- "
1746: + tnedge.name
1747: + " [color="
1748: + (edge.size > 0 ? "black"
1749: : "cadetblue1")
1750: + " style="
1751: + (tn.setNumber > 0
1752: && tn.group.useDynamicLock ? "dashed"
1753: : "solid")
1754: + " exactsize="
1755: + edge.size
1756: + " style=\"setlinewidth(1)\"];");
1757: }
1758: }
1759: }
1760: if (printedHeading)
1761: G.v().out.println("[transaction-graph] }");
1762: }
1763:
1764: G.v().out.println("[transaction-graph] }");
1765: }
1766:
1767: public void printTable(Collection<Transaction> AllTransactions) {
1768: G.v().out.println("[transaction-table] ");
1769: Iterator<Transaction> tnIt7 = AllTransactions.iterator();
1770: while (tnIt7.hasNext()) {
1771: Transaction tn = tnIt7.next();
1772:
1773: // Figure out if it's reachable, and if it MHP itself
1774: boolean reachable = false;
1775: boolean mhpself = false;
1776: {
1777: ReachableMethods rm = Scene.v().getReachableMethods();
1778: reachable = rm.contains(tn.method);
1779: if (mhp != null)
1780: mhpself = mhp.mayHappenInParallel(tn.method,
1781: tn.method);
1782: }
1783: G.v().out.println("[transaction-table] Transaction "
1784: + tn.name
1785: + (reachable ? " reachable" : " dead")
1786: + (mhpself ? " [called from >= 2 threads]"
1787: : " [called from <= 1 thread]"));
1788: G.v().out.println("[transaction-table] Where: "
1789: + tn.method.getDeclaringClass().toString() + ":"
1790: + tn.method.toString() + ": ");
1791: G.v().out.println("[transaction-table] Orig : "
1792: + tn.origLock);
1793: G.v().out.println("[transaction-table] Prep : "
1794: + tn.prepStmt);
1795: G.v().out.println("[transaction-table] Begin: "
1796: + tn.entermonitor);
1797: G.v().out.print("[transaction-table] End : early:"
1798: + tn.earlyEnds.toString() + " exc:"
1799: + tn.exceptionalEnd + " through:" + tn.end + " \n");
1800: G.v().out.println("[transaction-table] Size : "
1801: + tn.units.size());
1802: if (tn.read.size() < 100)
1803: G.v().out.print("[transaction-table] Read : "
1804: + tn.read.size()
1805: + "\n[transaction-table] "
1806: + tn.read.toString().replaceAll("\\[",
1807: " : [").replaceAll("\n",
1808: "\n[transaction-table] "));
1809: else
1810: G.v().out.print("[transaction-table] Read : "
1811: + tn.read.size() + " \n[transaction-table] ");
1812: if (tn.write.size() < 100)
1813: G.v().out.print("Write: "
1814: + tn.write.size()
1815: + "\n[transaction-table] "
1816: + tn.write.toString().replaceAll("\\[",
1817: " : [").replaceAll("\n",
1818: "\n[transaction-table] ")); // label provided by previous print statement
1819: else
1820: G.v().out.print("Write: " + tn.write.size()
1821: + "\n[transaction-table] "); // label provided by previous print statement
1822: G.v().out.print("Edges: (" + tn.edges.size() + ") "); // label provided by previous print statement
1823: Iterator<TransactionDataDependency> tnedgeit = tn.edges
1824: .iterator();
1825: while (tnedgeit.hasNext())
1826: G.v().out.print(tnedgeit.next().other.name + " ");
1827: if (tn.group != null && tn.group.useLocksets) {
1828: G.v().out.println("\n[transaction-table] Locks: "
1829: + tn.lockset);
1830:
1831: } else
1832: G.v().out
1833: .println("\n[transaction-table] Lock : "
1834: + (tn.setNumber == -1 ? "-"
1835: : (tn.lockObject == null ? "Global"
1836: : (tn.lockObject
1837: .toString() + (tn.lockObjectArrayIndex == null ? ""
1838: : "["
1839: + tn.lockObjectArrayIndex
1840: + "]")))));
1841: G.v().out.println("[transaction-table] Group: "
1842: + tn.setNumber + "\n[transaction-table] ");
1843: }
1844: }
1845:
1846: public void printGroups(Collection<Transaction> AllTransactions,
1847: int nextGroup, List<TransactionGroup> groups, RWSet rws[]) {
1848: G.v().out
1849: .print("[transaction-groups] Group Summaries\n[transaction-groups] ");
1850: for (int group = 0; group < nextGroup - 1; group++) {
1851: TransactionGroup tnGroup = groups.get(group + 1);
1852: if (tnGroup.size() > 0) {
1853: G.v().out.print("Group " + (group + 1) + " ");
1854: G.v().out
1855: .print("Locking: "
1856: + (tnGroup.useLocksets ? "using "
1857: : (tnGroup.isDynamicLock
1858: && tnGroup.useDynamicLock ? "Dynamic on "
1859: : "Static on "))
1860: + (tnGroup.useLocksets ? "locksets"
1861: : (tnGroup.lockObject == null ? "null"
1862: : tnGroup.lockObject
1863: .toString())));
1864: G.v().out.print("\n[transaction-groups] : ");
1865: Iterator<Transaction> tnIt = AllTransactions.iterator();
1866: while (tnIt.hasNext()) {
1867: Transaction tn = tnIt.next();
1868: if (tn.setNumber == group + 1)
1869: G.v().out.print(tn.name + " ");
1870: }
1871: G.v().out.print("\n[transaction-groups] "
1872: + rws[group].toString().replaceAll("\\[",
1873: " : [").replaceAll("\n",
1874: "\n[transaction-groups] "));
1875: }
1876: }
1877: G.v().out.print("Erasing \n[transaction-groups] : ");
1878: Iterator<Transaction> tnIt = AllTransactions.iterator();
1879: while (tnIt.hasNext()) {
1880: Transaction tn = tnIt.next();
1881: if (tn.setNumber == -1)
1882: G.v().out.print(tn.name + " ");
1883: }
1884: G.v().out.println("\n[transaction-groups] ");
1885: }
1886: }
|