Add intersection methods to Match 69/969/2
authorAlessandro Boch <aboch@cisco.com>
Thu, 22 Aug 2013 16:57:50 +0000 (09:57 -0700)
committerGerrit Code Review <gerrit@opendaylight.org>
Thu, 22 Aug 2013 21:59:24 +0000 (21:59 +0000)
- Add method to test and get intersection of two Match objects and correspondent Junit
- Fixed bug in NetUtils.inetAddressConflict()
- Made Match.toString() less verbose

Change-Id: I46cb93f7fc1a46aaaf3a3c341477166d8c1c8822
Signed-off-by: Alessandro Boch <aboch@cisco.com>
opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/match/Match.java
opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/match/MatchField.java
opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/utils/NetUtils.java
opendaylight/sal/api/src/test/java/org/opendaylight/controller/sal/match/MatchTest.java

index 9bab839..7a94d05 100644 (file)
@@ -246,93 +246,175 @@ public class Match implements Cloneable, Serializable {
     /**
      * Check whether the current match conflicts with the passed filter match
      * This match conflicts with the filter if for at least a MatchType defined
-     * in the filter match, the respective MatchFields differ or are not compatible
+     * in the filter match, the respective MatchFields differ or are not
+     * compatible
+     *
+     * In other words the function returns true if the set of packets described
+     * by one match and the set of packets described by the other match are
+     * disjoint. Equivalently, if the intersection of the two sets of packets
+     * described by the two matches is an empty.
      *
      * For example, Let's suppose the filter has the following MatchFields:
      * DL_TYPE = 0x800
-     * NW_DST =  172.20.30.110/24
+     * NW_DST = 172.20.30.110/24
      *
      * while this match has the following MatchFields:
+     * DL_TYPE = 0x800
      * NW_DST = 172.20.30.45/24
      * TP_DST = 80
      *
-     * Then the function would return false as the two Match are not conflicting
+     * Then the function would return false as the two Match are not
+     * conflicting.
      *
-     * Note: the mask value is taken into account only for MatchType.NW_SRC and MatchType.NW_DST
+     * Note: the mask value is taken into account only for MatchType.NW_SRC and
+     * MatchType.NW_DST
      *
-     * @param match the MAtch describing the filter
-     * @return true if the match is conflicting with the filter, false otherwise
+     * @param match
+     *            the Match describing the filter
+     * @return true if the set of packets described by one match and the set of
+     *         packets described by the other match are disjoint, false
+     *         otherwise
      */
     public boolean conflictWithFilter(Match filter) {
+        return !this.intersetcs(filter);
+    }
+
+    /**
+     * Merge the current Match fields with the fields of the filter Match. A
+     * check is first run to see if this Match is compatible with the filter
+     * Match. If it is not, the merge is not attempted.
+     *
+     * The result is the match object representing the intersection of the set
+     * of packets described by this match with the set of packets described by
+     * the filter match. If the intersection of the two sets is empty, the
+     * return match will be empty as well.
+     *
+     * @param filter
+     *            the match with which attempting the merge
+     * @return a new Match object describing the set of packets represented by
+     *         the intersection of this and the filter matches.
+     */
+    public Match mergeWithFilter(Match filter) {
+        return this.getIntersection(filter);
+    }
+
+    /**
+     * Return the match representing the intersection of the set of packets
+     * described by this match with the set of packets described by the other
+     * match. Such as m.intersect(m) == m and m.intersect(o) == o where o is an
+     * empty match.
+     *
+     * @param other
+     *            the match with which computing the intersection
+     * @return a new Match object representing the intersection of the set of
+     *         packets described by this match with the set of packets described
+     *         by the other match.
+     */
+    public Match getIntersection(Match other) {
+        Match intersection = new Match();
+        if (this.intersetcs(other)) {
+            for (MatchType type : MatchType.values()) {
+                if (this.isAny(type) && other.isAny(type)) {
+                    continue;
+                }
+                if (this.isAny(type)) {
+                    intersection.setField(other.getField(type).clone());
+                    continue;
+                } else if (other.isAny(type)) {
+                    intersection.setField(this.getField(type).clone());
+                    continue;
+                }
+                // Either they are equal or it is about IP address
+                switch (type) {
+                // When it is about IP address, take the wider prefix address between the twos
+                case NW_SRC:
+                case NW_DST:
+                    MatchField thisField = this.getField(type);
+                    MatchField otherField = other.getField(type);
+                    InetAddress thisAddress = (InetAddress) thisField.getValue();
+                    InetAddress otherAddress = (InetAddress) otherField.getValue();
+                    InetAddress thisMask = (InetAddress) thisField.getMask();
+                    InetAddress otherMask = (InetAddress) otherField.getMask();
+
+                    int thisMaskLen = (thisMask == null) ? ((thisAddress instanceof Inet4Address) ? 32 : 128)
+                            : NetUtils.getSubnetMaskLength(thisMask);
+                    int otherMaskLen = (otherMask == null) ? ((otherAddress instanceof Inet4Address) ? 32 : 128)
+                            : NetUtils.getSubnetMaskLength(otherMask);
+                    if (otherMaskLen < thisMaskLen) {
+                        intersection.setField(new MatchField(type, NetUtils.getSubnetPrefix(otherAddress, otherMaskLen), otherMask));
+                    } else {
+                        intersection.setField(new MatchField(type, NetUtils.getSubnetPrefix(thisAddress, thisMaskLen), thisMask));
+                    }
+                    break;
+                default:
+                    // this and other match field are equal for this type, pick this match field
+                    intersection.setField(this.getField(type).clone());
+                }
+            }
+        }
+        return intersection;
+    }
+
+    /**
+     * Checks whether the intersection of the set of packets described by this
+     * match with the set of packets described by the other match is non empty
+     *
+     * For example, if this match is: DL_SRC = 00:cc:bb:aa:11:22
+     *
+     * and the other match is: DL_TYPE = 0x800 NW_SRC = 1.2.3.4
+     *
+     * then their respective matching packets set intersection is non empty:
+     * DL_SRC = 00:cc:bb:aa:11:22 DL_TYPE = 0x800 NW_SRC = 1.2.3.4
+     *
+     * @param other
+     *            the other match with which testing the intersection
+     * @return true if the intersection of the respective matching packets sets
+     *         is non empty
+     */
+    public boolean intersetcs(Match other) {
+        if (this.getMatches() == 0 || other.getMatches() == 0) {
+            // No intersection with the empty set
+            return false;
+        }
         // Iterate through the MatchType defined in the filter
-        for (MatchType type : filter.getMatchesList()) {
-            if (this.isAny(type)) {
+        for (MatchType type : MatchType.values()) {
+            if (this.isAny(type) || other.isAny(type)) {
                 continue;
             }
 
             MatchField thisField = this.getField(type);
-            MatchField filterField = filter.getField(type);
+            MatchField otherField = other.getField(type);
 
             switch (type) {
             case DL_SRC:
             case DL_DST:
-                if (Arrays.equals((byte[]) thisField.getValue(),
-                        (byte[]) filterField.getValue())) {
+                if (!Arrays.equals((byte[]) thisField.getValue(), (byte[]) otherField.getValue())) {
                     return false;
                 }
                 break;
             case NW_SRC:
             case NW_DST:
                 InetAddress thisAddress = (InetAddress) thisField.getValue();
-                InetAddress filterAddress = (InetAddress) filterField
-                        .getValue();
+                InetAddress otherAddress = (InetAddress) otherField.getValue();
                 // Validity check
-                if (thisAddress instanceof Inet4Address
-                        && filterAddress instanceof Inet6Address
-                        || thisAddress instanceof Inet6Address
-                        && filterAddress instanceof Inet4Address) {
-                    return true;
+                if (thisAddress instanceof Inet4Address && otherAddress instanceof Inet6Address
+                        || thisAddress instanceof Inet6Address && otherAddress instanceof Inet4Address) {
+                    return false;
                 }
                 InetAddress thisMask = (InetAddress) thisField.getMask();
-                InetAddress filterMask = (InetAddress) filterField.getMask();
-                // thisAddress has to be in same subnet of filterAddress
-                if (NetUtils.inetAddressConflict(thisAddress, filterAddress,
-                        thisMask, filterMask)) {
-                    return true;
+                InetAddress otherMask = (InetAddress) otherField.getMask();
+                if (NetUtils.inetAddressConflict(thisAddress, otherAddress, thisMask, otherMask)
+                        && NetUtils.inetAddressConflict(otherAddress, thisAddress, otherMask, thisMask)) {
+                    return false;
                 }
                 break;
             default:
-                if (!thisField.getValue().equals(filterField.getValue())) {
-                    return true;
-                }
-            }
-            //TODO: check v4 v6 incompatibility
-        }
-        return false;
-    }
-
-    /**
-     * Merge the current Match fields with the fields of the filter Match
-     * A check is first run to see if this Match is compatible with the
-     * filter Match. If it is not, the merge is not attempted.
-     *
-     *
-     * @param filter
-     * @return
-     */
-    public Match mergeWithFilter(Match filter) {
-        if (!this.conflictWithFilter(filter)) {
-            /*
-             * No conflict with the filter
-             * We can copy over the fields which this match does not have
-             */
-            for (MatchType type : filter.getMatchesList()) {
-                if (this.isAny(type)) {
-                    this.setField(filter.getField(type).clone());
+                if (!thisField.getValue().equals(otherField.getValue())) {
+                    return false;
                 }
             }
         }
-        return this;
+        return true;
     }
 
     @Override
index 3b8a295..54be4c6 100644 (file)
@@ -184,7 +184,8 @@ public class MatchField implements Cloneable, Serializable {
 
     @Override
     public String toString() {
-        return type + "(" + getValueString() + "," + getMaskString() + ")";
+        return (mask == null) ? String.format("%s(%s)", getTypeString(), getValueString()) :
+            String.format("%s(%s,%s)", getTypeString(), getValueString(), getMaskString());
     }
 
     @Override
index 0fce4f4..e940211 100644 (file)
@@ -247,11 +247,18 @@ public abstract class NetUtils {
      * Checks if the test address and mask conflicts with the filter address and
      * mask
      *
-     * For example: testAddress: 172.28.2.23 testMask: 255.255.255.0
-     * filtAddress: 172.28.1.10 testMask: 255.255.255.0 conflict
+     * For example:
+     * testAddress: 172.28.2.23
+     * testMask: 255.255.255.0
+     * filterAddress: 172.28.1.10
+     * testMask: 255.255.255.0
+     * do conflict
      *
-     * testAddress: 172.28.2.23 testMask: 255.255.255.0 filtAddress: 172.28.1.10
-     * testMask: 255.255.0.0 do not conflict
+     * testAddress: 172.28.2.23
+     * testMask: 255.255.255.0
+     * filterAddress: 172.28.1.10
+     * testMask: 255.255.0.0
+     * do not conflict
      *
      * Null parameters are permitted
      *
@@ -275,7 +282,8 @@ public abstract class NetUtils {
 
         int testMaskLen = (testMask == null) ? ((testAddress instanceof Inet4Address) ? 32 : 128) : NetUtils
                 .getSubnetMaskLength(testMask);
-        int filterMaskLen = NetUtils.getSubnetMaskLength(filterMask);
+        int filterMaskLen = (filterMask == null) ? ((testAddress instanceof Inet4Address) ? 32 : 128) : NetUtils
+                .getSubnetMaskLength(filterMask);
 
         // Mask length check. Test mask has to be more specific than filter one
         if (testMaskLen < filterMaskLen) {
@@ -464,7 +472,7 @@ public abstract class NetUtils {
 
     /*
      * Following utilities are useful when you need to compare or bit shift java
-     * primitive type variable which are inerently signed
+     * primitive type variable which are inherently signed
      */
     /**
      * Returns the unsigned value of the passed byte variable
index ae78e1a..5dcb898 100644 (file)
@@ -523,4 +523,94 @@ public class MatchTest {
         Assert.assertTrue(field.getValue().equals(new Short(vlan)));
         Assert.assertTrue(field.isValid());
     }
+
+    @Test
+    public void testIntersection() throws UnknownHostException {
+        Short ethType = Short.valueOf((short)0x800);
+        InetAddress ip1 = InetAddress.getByName("1.1.1.1");
+        InetAddress ip2 = InetAddress.getByName("1.1.1.0");
+        InetAddress ipm2 = InetAddress.getByName("255.255.255.0");
+        InetAddress ip3 = InetAddress.getByName("1.3.0.0");
+        InetAddress ipm3 = InetAddress.getByName("255.255.0.0");
+
+        Match m1 = new Match();
+        m1.setField(MatchType.DL_TYPE, ethType);
+        m1.setField(MatchType.NW_SRC, ip1);
+
+        Match m2 = new Match();
+        m2.setField(MatchType.DL_TYPE, ethType);
+        m2.setField(MatchType.NW_SRC, ip2, ipm2);
+
+        Match m3 = new Match();
+        m3.setField(MatchType.DL_TYPE, ethType);
+        m3.setField(MatchType.NW_SRC, ip3, ipm3);
+        m3.setField(MatchType.NW_PROTO, IPProtocols.TCP.byteValue());
+
+        Match m3r = m3.reverse();
+        Assert.assertTrue(m3.intersetcs(m3r));
+
+        Assert.assertTrue(m1.intersetcs(m2));
+        Assert.assertTrue(m2.intersetcs(m1));
+        Assert.assertFalse(m1.intersetcs(m3));
+        Assert.assertTrue(m1.intersetcs(m3r));
+        Assert.assertFalse(m3.intersetcs(m1));
+        Assert.assertTrue(m3.intersetcs(m1.reverse()));
+        Assert.assertFalse(m2.intersetcs(m3));
+        Assert.assertFalse(m3.intersetcs(m2));
+        Assert.assertTrue(m2.intersetcs(m3r));
+
+
+        Match i = m1.getIntersection(m2);
+        Assert.assertTrue(((Short)i.getField(MatchType.DL_TYPE).getValue()).equals(ethType));
+        Assert.assertTrue(((InetAddress)i.getField(MatchType.NW_SRC).getValue()).equals(ip2));
+        Assert.assertTrue(((InetAddress)i.getField(MatchType.NW_SRC).getMask()).equals(ipm2));
+
+        i = m2.getIntersection(m3);
+        Assert.assertTrue(i.getMatches() == 0);
+
+        Match m4 = new Match();
+        m4.setField(MatchType.DL_TYPE, ethType);
+        m4.setField(MatchType.NW_PROTO, IPProtocols.TCP.byteValue());
+        Assert.assertTrue(m4.intersetcs(m3));
+
+        Match m5 = new Match();
+        m5.setField(MatchType.DL_TYPE, ethType);
+        m3.setField(MatchType.NW_SRC, ip3, ipm3);
+        m5.setField(MatchType.NW_PROTO, IPProtocols.UDP.byteValue());
+        Assert.assertFalse(m5.intersetcs(m3));
+        Assert.assertFalse(m5.intersetcs(m4));
+        Assert.assertTrue(m5.intersetcs(m5));
+        Assert.assertFalse(m3.intersetcs(m5));
+        Assert.assertFalse(m4.intersetcs(m5));
+
+
+        Match i2 = m4.getIntersection(m3);
+        Assert.assertFalse(i2.getMatches() == 0);
+        Assert.assertFalse(i2.getMatchesList().isEmpty());
+        Assert.assertTrue(((InetAddress)i2.getField(MatchType.NW_SRC).getValue()).equals(ip3));
+        Assert.assertTrue(((InetAddress)i2.getField(MatchType.NW_SRC).getMask()).equals(ipm3));
+        Assert.assertTrue(((Byte)i2.getField(MatchType.NW_PROTO).getValue()).equals(IPProtocols.TCP.byteValue()));
+
+        byte src[] = {(byte)0, (byte)0xab,(byte)0xbc,(byte)0xcd,(byte)0xde,(byte)0xef};
+        byte dst[] = {(byte)0x10, (byte)0x11,(byte)0x12,(byte)0x13,(byte)0x14,(byte)0x15};
+        Short srcPort = (short)1024;
+        Short dstPort = (short)80;
+
+        // Check identity
+        Match m6 = new Match();
+        m6.setField(MatchType.DL_SRC, src);
+        m6.setField(MatchType.DL_DST, dst);
+        m6.setField(MatchType.NW_SRC, ip2, ipm2);
+        m6.setField(MatchType.NW_DST, ip3, ipm3);
+        m6.setField(MatchType.NW_PROTO, IPProtocols.UDP.byteValue());
+        m6.setField(MatchType.TP_SRC, srcPort);
+        m6.setField(MatchType.TP_DST, dstPort);
+        Assert.assertTrue(m6.intersetcs(m6));
+        Assert.assertTrue(m6.getIntersection(m6).equals(m6));
+
+        // Empty match, represents the empty set
+        Match o = new Match();
+        Assert.assertTrue(m6.getIntersection(o).equals(o));
+        Assert.assertTrue(o.getIntersection(m6).equals(o));
+    }
 }