[CORD-2774] Support Dual-homing

Change-Id: I54d26e6dd0a76ba726afdf3b7160c46dcf6b79c5
diff --git a/apps/t3/src/main/java/org/onosproject/t3/api/GroupsInDevice.java b/apps/t3/src/main/java/org/onosproject/t3/api/GroupsInDevice.java
index e63bdca..74203af 100644
--- a/apps/t3/src/main/java/org/onosproject/t3/api/GroupsInDevice.java
+++ b/apps/t3/src/main/java/org/onosproject/t3/api/GroupsInDevice.java
@@ -21,6 +21,7 @@
 import org.onosproject.net.group.Group;
 
 import java.util.List;
+import java.util.Objects;
 
 /**
  * Class to represent the groups in a device for a given output and packet.
@@ -83,8 +84,31 @@
     }
 
     @Override
+    public boolean equals(Object o) {
+        if (this == o) {
+            return true;
+        }
+
+        if (o == null || getClass() != o.getClass()) {
+            return false;
+        }
+
+        GroupsInDevice that = (GroupsInDevice) o;
+
+        return Objects.equals(output, that.output) &&
+                Objects.equals(groups, that.groups) &&
+                Objects.equals(selector, that.selector);
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(output, groups, selector);
+    }
+
+    @Override
     public String toString() {
         return "GroupsInDevice{" +
+
                 "output=" + output +
                 ", groups=" + groups +
                 ", selector=" + selector +
diff --git a/apps/t3/src/main/java/org/onosproject/t3/api/TroubleshootService.java b/apps/t3/src/main/java/org/onosproject/t3/api/TroubleshootService.java
index 028df64..28ff728 100644
--- a/apps/t3/src/main/java/org/onosproject/t3/api/TroubleshootService.java
+++ b/apps/t3/src/main/java/org/onosproject/t3/api/TroubleshootService.java
@@ -22,6 +22,7 @@
 import org.onosproject.net.flow.TrafficSelector;
 
 import java.util.List;
+import java.util.Set;
 
 /**
  * API for troubleshooting services, providing static analysis of installed
@@ -45,7 +46,7 @@
      * @param type            the etherType of the traffic we want to trace.
      * @return a trace result
      */
-    StaticPacketTrace trace(HostId sourceHost, HostId destinationHost, EthType.EtherType type);
+    Set<StaticPacketTrace> trace(HostId sourceHost, HostId destinationHost, EthType.EtherType type);
 
     /**
      * Requests a static trace be performed for the given traffic selector
diff --git a/apps/t3/src/main/java/org/onosproject/t3/cli/TroubleshootSimpleTraceCommand.java b/apps/t3/src/main/java/org/onosproject/t3/cli/TroubleshootSimpleTraceCommand.java
index 971163b..75356dc 100644
--- a/apps/t3/src/main/java/org/onosproject/t3/cli/TroubleshootSimpleTraceCommand.java
+++ b/apps/t3/src/main/java/org/onosproject/t3/cli/TroubleshootSimpleTraceCommand.java
@@ -25,6 +25,8 @@
 import org.onosproject.t3.api.StaticPacketTrace;
 import org.onosproject.t3.api.TroubleshootService;
 
+import java.util.Set;
+
 import static org.onlab.packet.EthType.EtherType;
 
 /**
@@ -62,15 +64,17 @@
         //Printing the traced hosts
         print("Tracing between: %s and %s", srcHost, dstHost);
 
-        //Build the trace
-        StaticPacketTrace trace = service.trace(HostId.hostId(srcHost), HostId.hostId(dstHost), type);
-        if (trace.getInitialPacket() != null) {
-            print("Tracing Packet: %s", trace.getInitialPacket());
-            print("%s", T3CliUtils.printTrace(trace, verbosity1, verbosity2));
-        } else {
-            print("Cannot obtain trace between %s and %s", srcHost, dstHost);
-            print("Reason: %s", trace.resultMessage());
-        }
+        //Build the traces
+        Set<StaticPacketTrace> traces = service.trace(HostId.hostId(srcHost), HostId.hostId(dstHost), type);
+        traces.forEach(trace -> {
+            if (trace.getInitialPacket() != null) {
+                print("Tracing Packet: %s", trace.getInitialPacket());
+                print("%s", T3CliUtils.printTrace(trace, verbosity1, verbosity2));
+            } else {
+                print("Cannot obtain trace between %s and %s", srcHost, dstHost);
+                print("Reason: %s", trace.resultMessage());
+            }
+        });
 
 
     }
diff --git a/apps/t3/src/main/java/org/onosproject/t3/impl/TroubleshootManager.java b/apps/t3/src/main/java/org/onosproject/t3/impl/TroubleshootManager.java
index 00c2335..0f21f06 100644
--- a/apps/t3/src/main/java/org/onosproject/t3/impl/TroubleshootManager.java
+++ b/apps/t3/src/main/java/org/onosproject/t3/impl/TroubleshootManager.java
@@ -18,6 +18,7 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
 import org.apache.commons.lang3.tuple.Pair;
@@ -150,7 +151,7 @@
                     if (((sameLocation && onlyLocalDst && onlyLocalSrc) ||
                             (!onlyLocalSrc && !onlyLocalDst && ipAddressesToPing.size() > 0))
                             && !host.equals(hostToPing)) {
-                        tracesBuilder.add(trace(host.id(), hostToPing.id(), type));
+                        tracesBuilder.addAll(trace(host.id(), hostToPing.id(), type));
                     }
                 });
             }
@@ -159,7 +160,7 @@
     }
 
     @Override
-    public StaticPacketTrace trace(HostId sourceHost, HostId destinationHost, EtherType etherType) {
+    public Set<StaticPacketTrace> trace(HostId sourceHost, HostId destinationHost, EtherType etherType) {
         Host source = hostService.getHost(sourceHost);
         Host destination = hostService.getHost(destinationHost);
 
@@ -168,12 +169,12 @@
 
         if (source == null) {
             failTrace.addResultMessage("Source Host " + sourceHost + " does not exist");
-            return failTrace;
+            return ImmutableSet.of(failTrace);
         }
 
         if (destination == null) {
             failTrace.addResultMessage("Destination Host " + destinationHost + " does not exist");
-            return failTrace;
+            return ImmutableSet.of(failTrace);
         }
 
         TrafficSelector.Builder selectorBuilder = DefaultTrafficSelector.builder()
@@ -188,9 +189,13 @@
             // we are under same leaf so it's L2 Unicast.
             if (areBridged(source, destination)) {
                 selectorBuilder.matchEthDst(destination.mac());
-                StaticPacketTrace trace = trace(selectorBuilder.build(), source.location());
-                trace.addEndpointHosts(Pair.of(source, destination));
-                return trace;
+                ImmutableSet.Builder<StaticPacketTrace> traces = ImmutableSet.builder();
+                source.locations().forEach(hostLocation -> {
+                    StaticPacketTrace trace = trace(selectorBuilder.build(), hostLocation);
+                    trace.addEndpointHosts(Pair.of(source, destination));
+                    traces.add(trace);
+                });
+                return traces.build();
             }
 
             //handle the IPs for src and dst in case of L3
@@ -198,18 +203,18 @@
 
                 //Match on the source IP
                 if (!matchIP(source, failTrace, selectorBuilder, etherType, true)) {
-                    return failTrace;
+                    return ImmutableSet.of(failTrace);
                 }
 
                 //Match on destination IP
                 if (!matchIP(destination, failTrace, selectorBuilder, etherType, false)) {
-                    return failTrace;
+                    return ImmutableSet.of(failTrace);
                 }
 
             } else {
                 failTrace.addResultMessage("Host based trace supports only IPv4 or IPv6 as EtherType, " +
                         "please use packet based");
-                return failTrace;
+                return ImmutableSet.of(failTrace);
             }
 
             //l3 unicast, we get the dst mac of the leaf the source is connected to from netcfg
@@ -221,13 +226,17 @@
                 failTrace.addResultMessage("Can't get " + source.location().deviceId() +
                         " router MAC from segment routing config can't perform L3 tracing.");
             }
-            StaticPacketTrace trace = trace(selectorBuilder.build(), source.location());
-            trace.addEndpointHosts(Pair.of(source, destination));
-            return trace;
+            ImmutableSet.Builder<StaticPacketTrace> traces = ImmutableSet.builder();
+            source.locations().forEach(hostLocation -> {
+                StaticPacketTrace trace = trace(selectorBuilder.build(), hostLocation);
+                trace.addEndpointHosts(Pair.of(source, destination));
+                traces.add(trace);
+            });
+            return traces.build();
 
         } catch (ConfigException e) {
             failTrace.addResultMessage("Can't get config " + e.getMessage());
-            return failTrace;
+            return ImmutableSet.of(failTrace);
         }
     }
 
@@ -333,11 +342,12 @@
                 "Device " + in.deviceId() + " must exist in ONOS");
 
         StaticPacketTrace trace = new StaticPacketTrace(packet, in);
+        boolean isDualHomed = getHosts(trace).stream().anyMatch(host -> host.locations().size() > 1);
         //FIXME this can be done recursively
-        trace = traceInDevice(trace, packet, in);
+        trace = traceInDevice(trace, packet, in, isDualHomed);
         //Building output connect Points
         List<ConnectPoint> path = new ArrayList<>();
-        trace = getTrace(path, in, trace);
+        trace = getTrace(path, in, trace, isDualHomed);
         return trace;
     }
 
@@ -347,9 +357,11 @@
      * @param completePath the path traversed by the packet
      * @param in           the input connect point
      * @param trace        the trace to build
+     * @param isDualHomed  true if the trace we are doing starts or ends in a dual homed host
      * @return the build trace for that packet.
      */
-    private StaticPacketTrace getTrace(List<ConnectPoint> completePath, ConnectPoint in, StaticPacketTrace trace) {
+    private StaticPacketTrace getTrace(List<ConnectPoint> completePath, ConnectPoint in, StaticPacketTrace trace,
+                                       boolean isDualHomed) {
 
         log.debug("------------------------------------------------------------");
 
@@ -384,8 +396,9 @@
             //If the two host collections contain the same item it means we reached the proper output
             if (!Collections.disjoint(hostsList, hosts)) {
                 log.debug("Stopping here because host is expected destination {}, reached through", completePath);
-                trace.addResultMessage("Reached required destination Host " + cp);
-                computePath(completePath, trace, outputPath.getOutput());
+                if (computePath(completePath, trace, outputPath.getOutput())) {
+                    trace.addResultMessage("Reached required destination Host " + cp);
+                }
                 break;
             } else if (cp.port().equals(PortNumber.CONTROLLER)) {
 
@@ -434,9 +447,9 @@
                     updatedPacket.add(Criteria.matchInPort(dst.port()));
                     log.debug("DST Connect Point {}", dst);
                     //build the elements for that device
-                    traceInDevice(trace, updatedPacket.build(), dst);
+                    traceInDevice(trace, updatedPacket.build(), dst, isDualHomed);
                     //continue the trace along the path
-                    getTrace(completePath, dst, trace);
+                    getTrace(completePath, dst, trace, isDualHomed);
                 }
             } else if (edgePortService.isEdgePoint(outputPath.getOutput()) &&
                     trace.getInitialPacket().getCriterion(Criterion.Type.ETH_DST) != null &&
@@ -569,7 +582,7 @@
      * @param trace        the trace we are building
      * @param output       the final output connect point
      */
-    private void computePath(List<ConnectPoint> completePath, StaticPacketTrace trace, ConnectPoint output) {
+    private boolean computePath(List<ConnectPoint> completePath, StaticPacketTrace trace, ConnectPoint output) {
         List<ConnectPoint> traverseList = new ArrayList<>();
         if (!completePath.contains(trace.getInitialConnectPoint())) {
             traverseList.add(trace.getInitialConnectPoint());
@@ -578,21 +591,26 @@
         if (output != null && !completePath.contains(output)) {
             traverseList.add(output);
         }
-        trace.addCompletePath(traverseList);
+        if (!trace.getCompletePaths().contains(traverseList)) {
+            trace.addCompletePath(traverseList);
+            return true;
+        }
+        return false;
     }
 
     /**
      * Traces the packet inside a device starting from an input connect point.
      *
-     * @param trace  the trace we are building
-     * @param packet the packet we are tracing
-     * @param in     the input connect point.
+     * @param trace       the trace we are building
+     * @param packet      the packet we are tracing
+     * @param in          the input connect point.
+     * @param isDualHomed true if the trace we are doing starts or ends in a dual homed host
      * @return updated trace
      */
-    private StaticPacketTrace traceInDevice(StaticPacketTrace trace, TrafficSelector packet, ConnectPoint in) {
+    private StaticPacketTrace traceInDevice(StaticPacketTrace trace, TrafficSelector packet, ConnectPoint in,
+                                            boolean isDualHomed) {
 
-        //we already traversed this device.
-        if (trace.getGroupOuputs(in.deviceId()) != null) {
+        if (trace.getGroupOuputs(in.deviceId()) != null && !isDualHomed) {
             log.debug("Trace already contains device and given outputs");
             return trace;
         }
@@ -1018,6 +1036,11 @@
             trace.addResultMessage("Connect point out " + output + " is same as initial input " +
                     trace.getInitialConnectPoint());
         } else {
+            GroupsInDevice device = new GroupsInDevice(output, groupsForDevice, builder.build());
+            if (trace.getGroupOuputs(output.deviceId()) != null
+                    && trace.getGroupOuputs(output.deviceId()).contains(device)) {
+                return;
+            }
             trace.addGroupOutputPath(in.deviceId(),
                     new GroupsInDevice(output, groupsForDevice, builder.build()));
             outputPorts.add(outputInstruction.port());