From: Alessandro Boch Date: Thu, 22 Aug 2013 16:57:50 +0000 (-0700) Subject: Add intersection methods to Match X-Git-Tag: releasepom-0.1.0~181^2 X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?p=controller.git;a=commitdiff_plain;h=28b610000f621ce31cca004165a963eafb6ae430 Add intersection methods to Match - 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 --- diff --git a/opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/match/Match.java b/opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/match/Match.java index 9bab839198..7a94d05bf1 100644 --- a/opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/match/Match.java +++ b/opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/match/Match.java @@ -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 diff --git a/opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/match/MatchField.java b/opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/match/MatchField.java index 3b8a295216..54be4c6718 100644 --- a/opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/match/MatchField.java +++ b/opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/match/MatchField.java @@ -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 diff --git a/opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/utils/NetUtils.java b/opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/utils/NetUtils.java index 0fce4f4b0a..e94021119d 100644 --- a/opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/utils/NetUtils.java +++ b/opendaylight/sal/api/src/main/java/org/opendaylight/controller/sal/utils/NetUtils.java @@ -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 diff --git a/opendaylight/sal/api/src/test/java/org/opendaylight/controller/sal/match/MatchTest.java b/opendaylight/sal/api/src/test/java/org/opendaylight/controller/sal/match/MatchTest.java index ae78e1acc8..5dcb898dfb 100644 --- a/opendaylight/sal/api/src/test/java/org/opendaylight/controller/sal/match/MatchTest.java +++ b/opendaylight/sal/api/src/test/java/org/opendaylight/controller/sal/match/MatchTest.java @@ -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)); + } }