Add IpRange utility to convert IP ranges to IpPrefix
IKE Traffic Selectors are defined to be an IP range, with a start and an
end IP address. However, the Android system works in IP Prefixes. This
commit adds a utility to convert between the two.
Bug: 144246767
Test: New tests added, passing
Change-Id: I428fee682dea21346f92c5c628642dee3c785ba9
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 0000000..04e9277
--- /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 0000000..f4d07e9
--- /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());
+ }
+}
