diff options
author | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | 2020-02-04 23:26:40 +0000 |
---|---|---|
committer | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | 2020-02-04 23:26:40 +0000 |
commit | a3c59ef6b67ec8617521508016b918ac982462ca (patch) | |
tree | 74708ada77bd4b417e655de520cb0bd0c14c04ca | |
parent | 1a436a58d878445e3bf12335e756fe097404b848 (diff) | |
parent | 85bcd37d24ef5eff629314bc5a2256f6ab17e92c (diff) | |
download | net-a3c59ef6b67ec8617521508016b918ac982462ca.tar.gz |
Merge "Add IpRange utility to convert IP ranges to IpPrefix" am: deb20c6b9c am: 33e2ff8084 am: 85bcd37d24
Change-Id: I81c06a1eb41c7d0cb92dd9b27865c611cf041847
-rw-r--r-- | common/src_frameworkcommon/android/net/util/IpRange.java | 221 | ||||
-rw-r--r-- | common/tests/unit/src/android/net/util/IpRangeTest.java | 270 |
2 files changed, 491 insertions, 0 deletions
diff --git a/common/src_frameworkcommon/android/net/util/IpRange.java b/common/src_frameworkcommon/android/net/util/IpRange.java new file mode 100644 index 00000000..04e92773 --- /dev/null +++ b/common/src_frameworkcommon/android/net/util/IpRange.java @@ -0,0 +1,221 @@ +/* + * Copyright (C) 2020 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package android.net.util; + +import static com.android.internal.annotations.VisibleForTesting.Visibility; + +import android.annotation.NonNull; +import android.net.IpPrefix; + +import com.android.internal.annotations.VisibleForTesting; + +import java.math.BigInteger; +import java.net.InetAddress; +import java.net.UnknownHostException; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.LinkedList; +import java.util.List; +import java.util.Objects; +import java.util.Queue; + +/** + * This class represents an IP range, i.e., a contiguous block of IP addresses defined by a starting + * and ending IP address. These addresses may not be power-of-two aligned. + * + * <p>Conversion to prefixes are deterministic, and will always return the same set of {@link + * IpPrefix}(es). Ordering of IpPrefix instances is not guaranteed. + */ +public final class IpRange { + private static final int SIGNUM_POSITIVE = 1; + + private final byte[] mStartAddr; + private final byte[] mEndAddr; + + public IpRange(@NonNull InetAddress startAddr, @NonNull InetAddress endAddr) { + Objects.requireNonNull(startAddr, "startAddr must not be null"); + Objects.requireNonNull(endAddr, "endAddr must not be null"); + + if (!startAddr.getClass().equals(endAddr.getClass())) { + throw new IllegalArgumentException("Invalid range: Address family mismatch"); + } + if (addrToBigInteger(startAddr.getAddress()).compareTo( + addrToBigInteger(endAddr.getAddress())) >= 0) { + throw new IllegalArgumentException( + "Invalid range; start address must be before end address"); + } + + mStartAddr = startAddr.getAddress(); + mEndAddr = endAddr.getAddress(); + } + + @VisibleForTesting(visibility = Visibility.PRIVATE) + public IpRange(@NonNull IpPrefix prefix) { + Objects.requireNonNull(prefix, "prefix must not be null"); + + // Use masked address from IpPrefix to zero out lower order bits. + mStartAddr = prefix.getRawAddress(); + + // Set all non-prefix bits to max. + mEndAddr = prefix.getRawAddress(); + for (int bitIndex = prefix.getPrefixLength(); bitIndex < 8 * mEndAddr.length; ++bitIndex) { + mEndAddr[bitIndex / 8] |= (byte) (0x80 >> (bitIndex % 8)); + } + } + + private static InetAddress getAsInetAddress(byte[] address) { + try { + return InetAddress.getByAddress(address); + } catch (UnknownHostException e) { + // Cannot happen. InetAddress.getByAddress can only throw an exception if the byte + // array is the wrong length, but are always generated from InetAddress(es). + throw new IllegalArgumentException("Address is invalid"); + } + } + + @VisibleForTesting(visibility = Visibility.PRIVATE) + public InetAddress getStartAddr() { + return getAsInetAddress(mStartAddr); + } + + @VisibleForTesting(visibility = Visibility.PRIVATE) + public InetAddress getEndAddr() { + return getAsInetAddress(mEndAddr); + } + + /** + * Converts this IP range to a list of IpPrefix instances. + * + * <p>This method outputs the IpPrefix instances for use in the routing architecture. + * + * <p>For example, the range 192.0.2.4 - 192.0.3.1 converts to the following prefixes: + * + * <ul> + * <li>192.0.2.128/25 + * <li>192.0.2.64/26 + * <li>192.0.2.32/27 + * <li>192.0.2.16/28 + * <li>192.0.2.8/29 + * <li>192.0.2.4/30 + * <li>192.0.3.0/31 + * </ul> + */ + public List<IpPrefix> asIpPrefixes() { + final boolean isIpv6 = (mStartAddr.length == 16); + final List<IpPrefix> result = new ArrayList<>(); + final Queue<IpPrefix> workingSet = new LinkedList<>(); + + // Start with the any-address. Inet4/6Address.ANY requires compiling against + // core-platform-api. + workingSet.add(new IpPrefix(isIpv6 ? getAsInetAddress(new byte[16]) /* IPv6_ANY */ + : getAsInetAddress(new byte[4]) /* IPv4_ANY */, 0)); + + // While items are still in the queue, test and narrow to subsets. + while (!workingSet.isEmpty()) { + final IpPrefix workingPrefix = workingSet.poll(); + final IpRange workingRange = new IpRange(workingPrefix); + + // If the other range is contained within, it's part of the output. Do not test subsets, + // or we will end up with duplicates. + if (containsRange(workingRange)) { + result.add(workingPrefix); + continue; + } + + // If there is any overlap, split the working range into it's two subsets, and + // reevaluate those. + if (overlapsRange(workingRange)) { + workingSet.addAll(getSubsetPrefixes(workingPrefix)); + } + } + + return result; + } + + /** + * Returns the two prefixes that comprise the given prefix. + * + * <p>For example, for the prefix 192.0.2.0/24, this will return the two prefixes that combined + * make up the current prefix: + * + * <ul> + * <li>192.0.2.0/25 + * <li>192.0.2.128/25 + * </ul> + */ + private static List<IpPrefix> getSubsetPrefixes(IpPrefix prefix) { + final List<IpPrefix> result = new ArrayList<>(); + + final int currentPrefixLen = prefix.getPrefixLength(); + result.add(new IpPrefix(prefix.getAddress(), currentPrefixLen + 1)); + + final byte[] other = prefix.getRawAddress(); + other[currentPrefixLen / 8] = + (byte) (other[currentPrefixLen / 8] ^ (0x80 >> (currentPrefixLen % 8))); + result.add(new IpPrefix(getAsInetAddress(other), currentPrefixLen + 1)); + + return result; + } + + /** + * Checks if the other IP range is contained within this one + * + * <p>Checks based on byte values. For other to be contained within this IP range, other's + * starting address must be greater or equal to the current IpRange's starting address, and the + * other's ending address must be less than or equal to the current IP range's ending address. + */ + @VisibleForTesting(visibility = Visibility.PRIVATE) + public boolean containsRange(IpRange other) { + return addrToBigInteger(mStartAddr).compareTo(addrToBigInteger(other.mStartAddr)) <= 0 + && addrToBigInteger(mEndAddr).compareTo(addrToBigInteger(other.mEndAddr)) >= 0; + } + + /** + * Checks if the other IP range overlaps with this one + * + * <p>Checks based on byte values. For there to be overlap, this IpRange's starting address must + * be less than the other's ending address, and vice versa. + */ + @VisibleForTesting(visibility = Visibility.PRIVATE) + public boolean overlapsRange(IpRange other) { + return addrToBigInteger(mStartAddr).compareTo(addrToBigInteger(other.mEndAddr)) <= 0 + && addrToBigInteger(other.mStartAddr).compareTo(addrToBigInteger(mEndAddr)) <= 0; + } + + @Override + public int hashCode() { + return Objects.hash(mStartAddr, mEndAddr); + } + + @Override + public boolean equals(Object obj) { + if (!(obj instanceof IpRange)) { + return false; + } + + final IpRange other = (IpRange) obj; + return Arrays.equals(mStartAddr, other.mStartAddr) + && Arrays.equals(mEndAddr, other.mEndAddr); + } + + /** Gets the InetAddress in BigInteger form */ + private static BigInteger addrToBigInteger(byte[] addr) { + // Since addr.getAddress() returns network byte order (big-endian), it is compatible with + // the BigInteger constructor (which assumes big-endian). + return new BigInteger(SIGNUM_POSITIVE, addr); + } +} diff --git a/common/tests/unit/src/android/net/util/IpRangeTest.java b/common/tests/unit/src/android/net/util/IpRangeTest.java new file mode 100644 index 00000000..f4d07e9b --- /dev/null +++ b/common/tests/unit/src/android/net/util/IpRangeTest.java @@ -0,0 +1,270 @@ +/* + * Copyright (C) 2020 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package android.net.util; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertNotEquals; +import static org.junit.Assert.assertTrue; +import static org.junit.Assert.fail; + +import android.net.InetAddresses; +import android.net.IpPrefix; + +import androidx.test.filters.SmallTest; +import androidx.test.runner.AndroidJUnit4; + +import org.junit.Test; +import org.junit.runner.RunWith; + +import java.net.Inet4Address; +import java.net.Inet6Address; +import java.net.InetAddress; +import java.util.ArrayList; +import java.util.List; + +@RunWith(AndroidJUnit4.class) +@SmallTest +public class IpRangeTest { + + private static InetAddress address(String addr) { + return InetAddresses.parseNumericAddress(addr); + } + + private static final Inet4Address IPV4_ADDR = (Inet4Address) address("192.0.2.4"); + private static final Inet4Address IPV4_RANGE_END = (Inet4Address) address("192.0.3.1"); + private static final Inet6Address IPV6_ADDR = (Inet6Address) address("2001:db8::"); + private static final Inet6Address IPV6_RANGE_END = (Inet6Address) address("2001:db9:010f::"); + + private static final byte[] IPV4_BYTES = IPV4_ADDR.getAddress(); + private static final byte[] IPV6_BYTES = IPV6_ADDR.getAddress(); + + @Test + public void testConstructorBadArguments() { + try { + new IpRange(null, IPV6_ADDR); + fail("Expected NullPointerException: null start address"); + } catch (NullPointerException expected) { + } + + try { + new IpRange(IPV6_ADDR, null); + fail("Expected NullPointerException: null end address"); + } catch (NullPointerException expected) { + } + + try { + new IpRange(null, null); + fail("Expected NullPointerException: null addresses"); + } catch (NullPointerException expected) { + } + + try { + new IpRange(null); + fail("Expected NullPointerException: null start address"); + } catch (NullPointerException expected) { + } + + try { + new IpRange(address("10.10.10.10"), address("1.2.3.4")); + fail("Expected IllegalArgumentException: start address after end address"); + } catch (IllegalArgumentException expected) { + } + + try { + new IpRange(address("ffff::"), address("abcd::")); + fail("Expected IllegalArgumentException: start address after end address"); + } catch (IllegalArgumentException expected) { + } + } + + @Test + public void testConstructor() { + IpRange r = new IpRange(new IpPrefix(IPV4_ADDR, 32)); + assertEquals(IPV4_ADDR, r.getStartAddr()); + assertEquals(IPV4_ADDR, r.getEndAddr()); + + r = new IpRange(new IpPrefix(IPV4_ADDR, 16)); + assertEquals(address("192.0.0.0"), r.getStartAddr()); + assertEquals(address("192.0.255.255"), r.getEndAddr()); + + r = new IpRange(IPV4_ADDR, IPV4_RANGE_END); + assertEquals(IPV4_ADDR, r.getStartAddr()); + assertEquals(IPV4_RANGE_END, r.getEndAddr()); + + r = new IpRange(new IpPrefix(IPV6_ADDR, 128)); + assertEquals(IPV6_ADDR, r.getStartAddr()); + assertEquals(IPV6_ADDR, r.getEndAddr()); + + r = new IpRange(new IpPrefix(IPV6_ADDR, 16)); + assertEquals(address("2001::"), r.getStartAddr()); + assertEquals(address("2001:ffff:ffff:ffff:ffff:ffff:ffff:ffff"), r.getEndAddr()); + + r = new IpRange(IPV6_ADDR, IPV6_RANGE_END); + assertEquals(IPV6_ADDR, r.getStartAddr()); + assertEquals(IPV6_RANGE_END, r.getEndAddr()); + } + + @Test + public void testContainsRangeEqualRanges() { + final IpRange r1 = new IpRange(new IpPrefix(IPV6_ADDR, 35)); + final IpRange r2 = new IpRange(new IpPrefix(IPV6_ADDR, 35)); + + assertTrue(r1.containsRange(r2)); + assertTrue(r2.containsRange(r1)); + assertEquals(r1, r2); + } + + @Test + public void testContainsRangeSubset() { + final IpRange r1 = new IpRange(new IpPrefix(IPV6_ADDR, 64)); + final IpRange r2 = new IpRange(new IpPrefix(address("2001:db8::0101"), 128)); + + assertTrue(r1.containsRange(r2)); + assertFalse(r2.containsRange(r1)); + assertNotEquals(r1, r2); + } + + @Test + public void testContainsRangeTruncatesLowerOrderBits() { + final IpRange r1 = new IpRange(new IpPrefix(IPV6_ADDR, 100)); + final IpRange r2 = new IpRange(new IpPrefix(address("2001:db8::0101"), 100)); + + assertTrue(r1.containsRange(r2)); + assertTrue(r2.containsRange(r1)); + assertEquals(r1, r2); + } + + @Test + public void testContainsRangeSubsetSameStartAddr() { + final IpRange r1 = new IpRange(new IpPrefix(IPV6_ADDR, 35)); + final IpRange r2 = new IpRange(new IpPrefix(IPV6_ADDR, 39)); + + assertTrue(r1.containsRange(r2)); + assertFalse(r2.containsRange(r1)); + assertNotEquals(r1, r2); + } + + @Test + public void testContainsRangeOverlapping() { + final IpRange r1 = new IpRange(new IpPrefix(address("2001:db9::"), 32)); + final IpRange r2 = new IpRange(address("2001:db8::"), address("2001:db9::1")); + + assertFalse(r1.containsRange(r2)); + assertFalse(r2.containsRange(r1)); + assertNotEquals(r1, r2); + } + + @Test + public void testOverlapsRangeEqualRanges() { + final IpRange r1 = new IpRange(new IpPrefix(IPV6_ADDR, 35)); + final IpRange r2 = new IpRange(new IpPrefix(IPV6_ADDR, 35)); + + assertTrue(r1.overlapsRange(r2)); + assertTrue(r2.overlapsRange(r1)); + assertEquals(r1, r2); + } + + @Test + public void testOverlapsRangeSubset() { + final IpRange r1 = new IpRange(new IpPrefix(IPV6_ADDR, 35)); + final IpRange r2 = new IpRange(new IpPrefix(IPV6_ADDR, 39)); + + assertTrue(r1.overlapsRange(r2)); + assertTrue(r2.overlapsRange(r1)); + assertNotEquals(r1, r2); + } + + @Test + public void testOverlapsRangeDisjoint() { + final IpRange r1 = new IpRange(new IpPrefix(IPV6_ADDR, 32)); + final IpRange r2 = new IpRange(new IpPrefix(address("2001:db9::"), 32)); + + assertFalse(r1.overlapsRange(r2)); + assertFalse(r2.overlapsRange(r1)); + assertNotEquals(r1, r2); + } + + @Test + public void testOverlapsRangePartialOverlapLow() { + final IpRange r1 = new IpRange(new IpPrefix(address("2001:db9::"), 32)); + final IpRange r2 = new IpRange(address("2001:db8::"), address("2001:db9::1")); + + assertTrue(r1.overlapsRange(r2)); + assertTrue(r2.overlapsRange(r1)); + assertNotEquals(r1, r2); + } + + @Test + public void testOverlapsRangePartialOverlapHigh() { + final IpRange r1 = new IpRange(new IpPrefix(address("2001:db7::"), 32)); + final IpRange r2 = new IpRange(address("2001:db7::ffff"), address("2001:db8::")); + + assertTrue(r1.overlapsRange(r2)); + assertTrue(r2.overlapsRange(r1)); + assertNotEquals(r1, r2); + } + + @Test + public void testIpRangeToPrefixesIpv4FullRange() throws Exception { + final IpRange range = new IpRange(address("0.0.0.0"), address("255.255.255.255")); + final List<IpPrefix> prefixes = new ArrayList<>(); + prefixes.add(new IpPrefix("0.0.0.0/0")); + + assertEquals(prefixes, range.asIpPrefixes()); + } + + @Test + public void testIpRangeToPrefixesIpv4() throws Exception { + final IpRange range = new IpRange(IPV4_ADDR, IPV4_RANGE_END); + final List<IpPrefix> prefixes = new ArrayList<>(); + prefixes.add(new IpPrefix("192.0.2.128/25")); + prefixes.add(new IpPrefix("192.0.2.64/26")); + prefixes.add(new IpPrefix("192.0.2.32/27")); + prefixes.add(new IpPrefix("192.0.2.16/28")); + prefixes.add(new IpPrefix("192.0.2.8/29")); + prefixes.add(new IpPrefix("192.0.2.4/30")); + prefixes.add(new IpPrefix("192.0.3.0/31")); + + assertEquals(prefixes, range.asIpPrefixes()); + } + + @Test + public void testIpRangeToPrefixesIpv6FullRange() throws Exception { + final IpRange range = + new IpRange(address("::"), address("ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff")); + final List<IpPrefix> prefixes = new ArrayList<>(); + prefixes.add(new IpPrefix("::/0")); + + assertEquals(prefixes, range.asIpPrefixes()); + } + + @Test + public void testIpRangeToPrefixesIpv6() throws Exception { + final IpRange range = new IpRange(IPV6_ADDR, IPV6_RANGE_END); + final List<IpPrefix> prefixes = new ArrayList<>(); + prefixes.add(new IpPrefix("2001:db8::/32")); + prefixes.add(new IpPrefix("2001:db9::/40")); + prefixes.add(new IpPrefix("2001:db9:100::/45")); + prefixes.add(new IpPrefix("2001:db9:108::/46")); + prefixes.add(new IpPrefix("2001:db9:10c::/47")); + prefixes.add(new IpPrefix("2001:db9:10e::/48")); + prefixes.add(new IpPrefix("2001:db9:10f::/128")); + + assertEquals(prefixes, range.asIpPrefixes()); + } +} |