X-Git-Url: http://plrg.eecs.uci.edu/git/?p=jpf-core.git;a=blobdiff_plain;f=src%2Fmain%2Fgov%2Fnasa%2Fjpf%2Flistener%2FConflictTracker.java;h=3ec1eea1b9b9d466a0d9db55e5d001e97dbb3de4;hp=134346775940c10aaf5acd5db90d67c8b16159b9;hb=4dc7b430e4ec5e2cdba1c837b1c4960a5875cd6a;hpb=7208239ff942a7eb60c652342970ae6afb1976ba

diff --git a/src/main/gov/nasa/jpf/listener/ConflictTracker.java b/src/main/gov/nasa/jpf/listener/ConflictTracker.java
index 1343467..3ec1eea 100644
--- a/src/main/gov/nasa/jpf/listener/ConflictTracker.java
+++ b/src/main/gov/nasa/jpf/listener/ConflictTracker.java
@@ -37,28 +37,25 @@ import java.util.*;
  **/
 
 public class ConflictTracker extends ListenerAdapter {
-
   private final PrintWriter out;
   private final HashSet<String> conflictSet = new HashSet<String>(); // Variables we want to track
   private final HashSet<String> appSet = new HashSet<String>(); // Apps we want to find their conflicts
   private final HashSet<String> manualSet = new HashSet<String>(); // Writer classes with manual inputs to detect direct-direct(No Conflict) interactions
   private final HashMap<Integer, Node> nodes = new HashMap<Integer, Node>(); // Nodes of a graph
-  private HashSet<NameValuePair> tempSetSet = new HashSet<NameValuePair>();
+  private HashSet<Transition> transitions = new HashSet<Transition>();
+  private ArrayList<Update> currUpdates = new ArrayList<Update>();
   private long timeout;
   private long startTime;
   private Node parentNode = new Node(-2);
   private String operation;
   private String detail;
-  private String errorMessage;
   private int depth;
   private int id;
-  private boolean conflictFound = false;
-  private boolean isSet = false;
   private boolean manual = false;
 
   private final String SET_LOCATION_METHOD = "setLocationMode";
   private final String LOCATION_VAR = "locationMode";
-  
+
   public ConflictTracker(Config config, JPF jpf) {
     out = new PrintWriter(System.out, true);
 
@@ -89,215 +86,243 @@ public class ConflictTracker extends ListenerAdapter {
     startTime = System.currentTimeMillis();
   }
 
-  boolean propagateTheChange(Node currentNode) {
-	HashSet<Node> changed = new HashSet<Node>(currentNode.getSuccessors());
+  void propagateChange(Edge newEdge) {
+    HashSet<Edge> changed = new HashSet<Edge>();
 
-	while(!changed.isEmpty()) {
-      // Get the first element of HashSet and remove it from the changed set
-      Node nodeToProcess = changed.iterator().next();
-      changed.remove(nodeToProcess);
+    // Add the current node to the changed set
+    changed.add(newEdge);
 
-      // Update the sets, store the outSet to temp before its changes
-      boolean isChanged = updateSets(nodeToProcess);
+    while(!changed.isEmpty()) {
+      // Get the first element of the changed set and remove it
+      Edge edgeToProcess = changed.iterator().next();
+      changed.remove(edgeToProcess);
 
-      // Check for a conflict
-      if (checkForConflict(nodeToProcess))
-        return true;
-
-      // Checking if the out set has changed or not(Add its successors to the change list!)
-      if (isChanged) {
-        for (Node i : nodeToProcess.getSuccessors()) {
-          if (!changed.contains(i))
-            changed.add(i);
+      //If propagating change on edge causes change, enqueue all the target node's out edges
+      if (propagateEdge(edgeToProcess)) {
+        Node dst = edgeToProcess.getDst();
+        for (Edge e : dst.getOutEdges()) {
+          changed.add(e);
         }
       }
-	}
+    }
+  }
+
+  boolean propagateEdge(Edge e) {
+    HashMap<IndexObject, HashSet<Update>> srcUpdates = e.getSrc().getLastUpdates();
+    HashMap<IndexObject, HashSet<Update>> dstUpdates = e.getDst().getLastUpdates();
+    ArrayList<Update> edgeUpdates = e.getUpdates();
+    HashMap<IndexObject, Update> lastupdate = new HashMap<IndexObject, Update>();
+    boolean changed = false;
+    
+    //Go through each update on the current transition
+    for(int i=0; i<edgeUpdates.size(); i++) {
+      Update u = edgeUpdates.get(i);
+      IndexObject io = u.getIndex();
+      HashSet<Update> confupdates = null;
+
+      //See if we have already updated this device attribute
+      if (lastupdate.containsKey(io)) {
+        confupdates = new HashSet<Update>();
+        confupdates.add(lastupdate.get(io));
+      } else if (srcUpdates.containsKey(io)){
+        confupdates = srcUpdates.get(io);
+      }
 
-	return false;
+      //Check for conflict with the appropriate update set if we are not a manual transition
+      if (confupdates != null && !u.isManual()) {
+        for(Update u2: confupdates) {
+          if (conflicts(u, u2)) {
+            throw new RuntimeException(createErrorMessage(u, u2));
+          }
+        }
+      }
+      lastupdate.put(io, u);
+    }
+    for(IndexObject io: srcUpdates.keySet()) {
+      //Only propagate src changes if the transition doesn't update the device attribute
+      if (!lastupdate.containsKey(io)) {
+        //Make sure destination has hashset in map
+        if (!dstUpdates.containsKey(io))
+          dstUpdates.put(io, new HashSet<Update>());
+
+        changed |= dstUpdates.get(io).addAll(srcUpdates.get(io));
+      }
+    }
+    for(IndexObject io: lastupdate.keySet()) {
+      //Make sure destination has hashset in map
+      if (!dstUpdates.containsKey(io))
+        dstUpdates.put(io, new HashSet<Update>());
+      
+      changed |= dstUpdates.get(io).add(lastupdate.get(io));
+    }
+    return changed;
   }
 
-  boolean setOutSet(Node currentNode) {
-	Integer prevSize = currentNode.getOutSet().size();
+  //Method to check for conflicts between two updates
+  //Have conflict if same device, same attribute, different app, different vaalue
+  boolean conflicts(Update u, Update u2) {
+    return (!u.getApp().equals(u2.getApp())) &&
+      u.getDeviceId().equals(u2.getDeviceId()) &&
+      u.getAttribute().equals(u2.getAttribute()) &&
+      (!u.getValue().equals(u2.getValue()));
+  }
+  
+  String createErrorMessage(Update u, Update u2) {
+    String message = "Conflict found between the two apps. App"+u.getApp()+
+		     " has written the value: "+u.getValue()+
+      " to the attribute: "+u.getAttribute()+" while App"
+      +u2.getApp()+" is writing the value: "
+      +u2.getValue()+" to the same variable!";
+    System.out.println(message);	
+    return message;
+  }
 
-	// Update based on setSet
-	for (NameValuePair i : currentNode.getSetSet()) {
-      if (currentNode.getOutSet().contains(i))
-        currentNode.getOutSet().remove(i);
-      currentNode.getOutSet().add(i);
-	}
+  Edge createEdge(Node parent, Node current, Transition transition) {
+    //Check if this transition is explored.  If so, just skip everything
+    if (transitions.contains(transition))
+      return null;
 
-	// Add all the inSet
-	currentNode.getOutSet().addAll(currentNode.getInSet());
+    //Create edge
+    Edge e = new Edge(parent, current, transition, currUpdates);
+    parent.addOutEdge(e);
 
-	// Check if the outSet is changed
-	if (!prevSize.equals(currentNode.getOutSet().size()))
-      return true;
-	
-	return false;
+    //Mark transition as explored
+    transitions.add(transition);
+    return e;
   }
 
-  void setInSet(Node currentNode) {
-	for (Node i : currentNode.getPredecessors()) {
-      currentNode.getInSet().addAll(i.getOutSet());
+  static class Node {
+    Integer id;
+    Vector<Edge> outEdges = new Vector<Edge>();
+    HashMap<IndexObject, HashSet<Update>> lastUpdates = new HashMap<IndexObject,  HashSet<Update>>();
+    
+    Node(Integer id) {
+      this.id = id;
     }
-  }
 
-  boolean checkForConflict(Node currentNode) {
-	HashMap<String, String> valueMap = new HashMap<String, String>(); // HashMap from varName to value
-	HashMap<String, Integer> writerMap = new HashMap<String, Integer>(); // HashMap from varName to appNum
-
-	for (NameValuePair i : currentNode.getSetSet()) {
-      if (i.getIsManual()) // Manual input: we have no conflict
-        continue;
-
-      valueMap.put(i.getVarName(), i.getValue());
-      if (writerMap.containsKey(i.getVarName()))
-        writerMap.put(i.getVarName(), i.getAppNum()+writerMap.get(i.getVarName())); // We have two writers?
-      else
-        writerMap.put(i.getVarName(), i.getAppNum());
-	}
-
-	// Comparing the inSet and setSet to find the conflict
-	for (NameValuePair i : currentNode.getInSet()) {
-      if (valueMap.containsKey(i.getVarName())) {
-        String value = valueMap.get(i.getVarName());
-        Integer writer = writerMap.get(i.getVarName());
-        if ((value != null)&&(writer != null)) {
-          if (!value.equals(i.getValue())&&!writer.equals(i.getAppNum())) { // We have different values
-            errorMessage = "Conflict found between the two apps. App"+i.getAppNum()+" has written the value: "+i.getValue()+
-                    " to the variable: "+i.getVarName()+" while App"+writerMap.get(i.getVarName())+" is overwriting the value: "
-                    +valueMap.get(i.getVarName())+" to the same variable!";
-            return true;
-          }
-        }
-      }
-	}
+    Integer getId() {
+      return id;
+    }
+
+    Vector<Edge> getOutEdges() {
+      return outEdges;
+    }
 
-	return false;
+    void addOutEdge(Edge e) {
+      outEdges.add(e);
+    }
+    
+    HashMap<IndexObject, HashSet<Update>> getLastUpdates() {
+      return lastUpdates;
+    }
   }
 
-  boolean updateSets(Node currentNode) {
-	// Set input set according to output set of pred states of current state
-    setInSet(currentNode);
+  //Each Edge corresponds to a transition
+  static class Edge {
+    Node source, destination;
+    Transition transition;
+    ArrayList<Update> updates = new ArrayList<Update>();
+    
+    Edge(Node src, Node dst, Transition t, ArrayList<Update> _updates) {
+      this.source = src;
+      this.destination = dst;
+      this.transition = t;
+      this.updates.addAll(_updates);
+    }
 
-	// Set outSet according to inSet, and setSet of current node, check if there is a change
-    return setOutSet(currentNode);
-  }
+    Node getSrc() {
+      return source;
+    }
 
-  static class Node {
-	Integer id;
-	HashSet<Node> predecessors = new HashSet<Node>();
-	HashSet<Node> successors = new HashSet<Node>();
-	HashSet<NameValuePair> inSet = new HashSet<NameValuePair>();
-	HashSet<NameValuePair> setSet = new HashSet<NameValuePair>();
-	HashSet<NameValuePair> outSet = new HashSet<NameValuePair>();
-
-	Node(Integer id) {
-		this.id = id;
-	}
-
-	void addPredecessor(Node node) {
-		predecessors.add(node);
-	}
-
-	void addSuccessor(Node node) {
-		successors.add(node);
-	}
-
-	void setSetSet(HashSet<NameValuePair> setSet, boolean isManual) {
-      if (isManual)
-        this.setSet = new HashSet<NameValuePair>();
-      for (NameValuePair i : setSet) {
-        this.setSet.add(new NameValuePair(i.getAppNum(), i.getValue(), i.getVarName(), i.getIsManual()));
-      }
-	}
+    Node getDst() {
+      return destination;
+    }
 
-	Integer getId() {
-		return id;
-	}
+    Transition getTransition() {
+      return transition;
+    }
 
-	HashSet<Node> getPredecessors() {
-		return predecessors;
-	}
+    ArrayList<Update> getUpdates() {
+      return updates;
+    }
+  }
 
-	HashSet<Node> getSuccessors() {
-		return successors;
-	}
+  static class Update {
+    String appName;
+    String deviceId;
+    String attribute;
+    String value;
+    boolean ismanual;
+    
+    Update(String _appName, String _deviceId, String _attribute, String _value, boolean _ismanual) {
+      this.appName = _appName;
+      this.deviceId = _deviceId;
+      this.attribute = _attribute;
+      this.value = _value;
+      this.ismanual = _ismanual;
+    }
 
-	HashSet<NameValuePair> getInSet() {
-		return inSet;
-	}
+    boolean isManual() {
+      return ismanual;
+    }
+    
+    String getApp() {
+      return appName;
+    }
 
-	HashSet<NameValuePair> getSetSet() {
-		return setSet;
-	}
+    String getDeviceId() {
+      return deviceId;
+    }
 
-	HashSet<NameValuePair> getOutSet() {
-		return outSet;
-	}
-  }
+    String getAttribute() {
+      return attribute;
+    }
+    
+    String getValue() {
+      return value;
+    }
 
-  static class NameValuePair {
-	Integer appNum;
-	String value;
-	String varName;
-	boolean isManual;
-
-	NameValuePair(Integer appNum, String value, String varName, boolean isManual) {
-      this.appNum = appNum;
-      this.value = value;
-      this.varName = varName;
-      this.isManual = isManual;
-	}
-
-	void setAppNum(Integer appNum) {
-		this.appNum = appNum;
-	}
-
-	void setValue(String value) {
-		this.value = value;
-	}
-
-	void setVarName(String varName) {
-		this.varName = varName;
-	}
-
-    void setIsManual(String varName) {
-		this.isManual = isManual;
-	}
-
-	Integer getAppNum() {
-		return appNum;
-	}
-
-	String getValue() {
-		return value;
-	}
-
-	String getVarName() {
-		return varName;
-	}
-
-	boolean getIsManual() {
-		return isManual;
-	}
-
-	@Override
-	public boolean equals(Object o) {
-      if (o instanceof NameValuePair) {
-        NameValuePair other = (NameValuePair) o;
-        if (varName.equals(other.getVarName()))
-          return appNum.equals(other.getAppNum());
-      }
-      return false;
-	}
+    //Gets an index object for indexing updates by just device and attribute
+    IndexObject getIndex() {
+      return new IndexObject(this);
+    }
 
-	@Override
-	public int hashCode() {
-		return appNum.hashCode() * 31 + varName.hashCode();
-	}
+    public boolean equals(Object o) {
+      if (!(o instanceof Update))
+        return false;
+      Update u=(Update)o;
+      return (getDeviceId().equals(u.getDeviceId()) &&
+              getAttribute().equals(u.getAttribute()) &&
+              getApp().equals(u.getApp()) &&
+              getValue().equals(u.getValue()));
+    }
+
+    public int hashCode() {
+      return (getDeviceId().hashCode() << 3) ^
+        (getAttribute().hashCode() << 2) ^
+        (getApp().hashCode() << 1) ^
+        getValue().hashCode();
+    }
   }
 
+  static class IndexObject {
+    Update u;
+    IndexObject(Update _u) {
+      this.u = _u;
+    }
+    
+    public boolean equals(Object o) {
+      if (!(o instanceof IndexObject))
+        return false;
+      IndexObject io=(IndexObject)o;
+      return (u.getDeviceId().equals(io.u.getDeviceId()) &&
+              u.getAttribute().equals(io.u.getAttribute()));
+    }
+    public int hashCode() {
+      return (u.getDeviceId().hashCode() << 1) ^ u.getAttribute().hashCode();
+    }
+  }
+  
   @Override
   public void stateRestored(Search search) {
     id = search.getStateId();
@@ -308,37 +333,41 @@ public class ConflictTracker extends ListenerAdapter {
     out.println("The state is restored to state with id: "+id+", depth: "+depth);
   
     // Update the parent node
-    if (nodes.containsKey(id)) {
-	  parentNode = nodes.get(id);
-    } else {
-	  parentNode = new Node(id);
-    }
+    parentNode = getNode(id);
   }
 
   @Override
   public void searchStarted(Search search) {
     out.println("----------------------------------- search started");
   }
- 
+
+  private Node getNode(Integer id) {
+    if (!nodes.containsKey(id))
+      nodes.put(id, new Node(id));
+    return nodes.get(id);
+  }
 
   @Override
   public void stateAdvanced(Search search) {
     String theEnd = null;
+    Transition transition = search.getTransition();
     id = search.getStateId();
     depth = search.getDepth();
     operation = "forward";
 
-    // Add the node to the list of nodes	
-    nodes.put(id, new Node(id));
-    Node currentNode = nodes.get(id);
+    // Add the node to the list of nodes
+    Node currentNode = getNode(id);
 
-    // Update the setSet for this new node
-    if (isSet) {
-      currentNode.setSetSet(tempSetSet, manual);
-      tempSetSet = new HashSet<NameValuePair>(); 
-      isSet = false;
-      manual = false;
-    }
+    // Create an edge based on the current transition
+    Edge newEdge = createEdge(parentNode, currentNode, transition);
+
+    // Reset the temporary variables and flags
+    currUpdates.clear();
+    manual = false;
+
+    // If we have a new Edge, check for conflicts
+    if (newEdge != null)
+      propagateChange(newEdge);
 
     if (search.isNewState()) {
       detail = "new";
@@ -353,32 +382,8 @@ public class ConflictTracker extends ListenerAdapter {
 
     out.println("The state is forwarded to state with id: "+id+", depth: "+depth+" which is "+detail+" state: "+"% "+theEnd);
     
-    // Updating the predecessors for this node
-    // Check if parent node is already in successors of the current node or not
-    if (!(currentNode.getPredecessors().contains(parentNode)))
-	currentNode.addPredecessor(parentNode);
-
-    // Update the successors for this node
-    // Check if current node is already in successors of the parent node or not
-    if (!(parentNode.getSuccessors().contains(currentNode)))
-        parentNode.addSuccessor(currentNode);
-
-    // Update the sets, check if the outSet is changed or not
-    boolean isChanged = updateSets(currentNode);
-   
-    // Check for a conflict
-    conflictFound = checkForConflict(currentNode);
-
-    // Check if the outSet of this state has changed, update all of its successors' sets if any
-    if (isChanged)
-	conflictFound = conflictFound || propagateTheChange(currentNode);
-
     // Update the parent node
-    if (nodes.containsKey(id)) {
-	  parentNode = nodes.get(id);
-    } else {
-	  parentNode = new Node(id);
-    }
+    parentNode = currentNode;
   }
 
   @Override
@@ -391,11 +396,7 @@ public class ConflictTracker extends ListenerAdapter {
     out.println("The state is backtracked to state with id: "+id+", depth: "+depth);
 
     // Update the parent node
-    if (nodes.containsKey(id)) {
-	  parentNode = nodes.get(id);
-    } else {
-	  parentNode = new Node(id);
-    }
+    parentNode = getNode(id);
   }
 
   @Override
@@ -537,22 +538,13 @@ public class ConflictTracker extends ListenerAdapter {
     return null;
   }
 
-  private void writeWriterAndValue(String writer, String value, String var) {
-    // Update the temporary Set set.
-    NameValuePair temp = new NameValuePair(1, value, var, manual);
-    if (writer.equals("App2"))
-    	temp = new NameValuePair(2, value, var, manual);
-    
-    if (tempSetSet.contains(temp))
-	tempSetSet.remove(temp);
-    tempSetSet.add(temp);
-    // Set isSet to true
-    isSet = true;
+  private void writeWriterAndValue(String writer, String attribute, String value) {
+    Update u = new Update(writer, "DEVICE", attribute, value, manual);
+    currUpdates.add(u);
   }
 
   @Override
   public void instructionExecuted(VM vm, ThreadInfo ti, Instruction nextInsn, Instruction executedInsn) {
-    // Instantiate timeoutTimer
     if (timeout > 0) {
       if (System.currentTimeMillis() - startTime > timeout) {
         StringBuilder sbTimeOut = new StringBuilder();
@@ -562,46 +554,40 @@ public class ConflictTracker extends ListenerAdapter {
       }
     }
 
-    if (conflictFound) {
-      StringBuilder sb = new StringBuilder();
-      sb.append(errorMessage);
-      Instruction nextIns = ti.createAndThrowException("java.lang.RuntimeException", sb.toString());
-      ti.setNextPC(nextIns);
+    if (conflictSet.contains(LOCATION_VAR)) {
+      MethodInfo mi = executedInsn.getMethodInfo();
+      // Find the last load before return and get the value here
+      if (mi.getName().equals(SET_LOCATION_METHOD) &&
+          executedInsn instanceof ALOAD && nextInsn instanceof ARETURN) {
+        byte type  = getType(ti, executedInsn);
+        String value = getValue(ti, executedInsn, type);
+        
+        // Extract the writer app name
+        ClassInfo ci = mi.getClassInfo();
+        String writer = ci.getName();
+        
+        // Update the temporary Set set.
+        writeWriterAndValue(writer, LOCATION_VAR, value);
+      }
     } else {
-      if (conflictSet.contains(LOCATION_VAR)) {
-        MethodInfo mi = executedInsn.getMethodInfo();
-        // Find the last load before return and get the value here
-        if (mi.getName().equals(SET_LOCATION_METHOD) &&
-                executedInsn instanceof ALOAD && nextInsn instanceof ARETURN) {
-          byte type  = getType(ti, executedInsn);
-          String value = getValue(ti, executedInsn, type);
-
-          // Extract the writer app name
-          ClassInfo ci = mi.getClassInfo();
-          String writer = ci.getName();
-
-          // Update the temporary Set set.
-          writeWriterAndValue(writer, value, LOCATION_VAR);
-        }
-      } else {
-        if (executedInsn instanceof WriteInstruction) {
-          String varId = ((WriteInstruction) executedInsn).getFieldInfo().getFullName();
-          for (String var : conflictSet) {
-            if (varId.contains(var)) {
-              // Get variable info
-              byte type = getType(ti, executedInsn);
-              String value = getValue(ti, executedInsn, type);
-              String writer = getWriter(ti.getStack(), appSet);
-              // Just return if the writer is not one of the listed apps in the .jpf file
-              if (writer == null)
-                return;
-
-              if (getWriter(ti.getStack(), manualSet) != null)
-                manual = true;
-
-              // Update the temporary Set set.
-              writeWriterAndValue(writer, value, var);
-            }
+      if (executedInsn instanceof WriteInstruction) {
+        String varId = ((WriteInstruction) executedInsn).getFieldInfo().getFullName();
+        
+        for (String var : conflictSet) {
+          if (varId.contains(var)) {
+            // Get variable info
+            byte type = getType(ti, executedInsn);
+            String value = getValue(ti, executedInsn, type);
+            String writer = getWriter(ti.getStack(), appSet);
+            // Just return if the writer is not one of the listed apps in the .jpf file
+            if (writer == null)
+              return;
+            
+            if (getWriter(ti.getStack(), manualSet) != null)
+              manual = true;
+            
+            // Update the current updates
+            writeWriterAndValue(writer, var, value);
           }
         }
       }