Give VPNs the INTERNET capability when they route most of the IP space
Test: manual, plus wrote some new tests for this
Bug: 72765718
Change-Id: I9759da72b752fd8eeb1d0647db9ab341f04c0528
diff --git a/core/java/android/net/IpPrefix.java b/core/java/android/net/IpPrefix.java
index 6e2654e..4631c56 100644
--- a/core/java/android/net/IpPrefix.java
+++ b/core/java/android/net/IpPrefix.java
@@ -25,6 +25,7 @@
import java.net.InetAddress;
import java.net.UnknownHostException;
import java.util.Arrays;
+import java.util.Comparator;
/**
* This class represents an IP prefix, i.e., a contiguous block of IP addresses aligned on a
@@ -187,6 +188,20 @@
}
/**
+ * Returns whether the specified prefix is entirely contained in this prefix.
+ *
+ * Note this is mathematical inclusion, so a prefix is always contained within itself.
+ * @param otherPrefix the prefix to test
+ * @hide
+ */
+ public boolean containsPrefix(IpPrefix otherPrefix) {
+ if (otherPrefix.getPrefixLength() < prefixLength) return false;
+ final byte[] otherAddress = otherPrefix.getRawAddress();
+ NetworkUtils.maskRawAddress(otherAddress, prefixLength);
+ return Arrays.equals(otherAddress, address);
+ }
+
+ /**
* @hide
*/
public boolean isIPv6() {
@@ -230,6 +245,38 @@
}
/**
+ * Returns a comparator ordering IpPrefixes by length, shorter to longer.
+ * Contents of the address will break ties.
+ * @hide
+ */
+ public static Comparator<IpPrefix> lengthComparator() {
+ return new Comparator<IpPrefix>() {
+ @Override
+ public int compare(IpPrefix prefix1, IpPrefix prefix2) {
+ if (prefix1.isIPv4()) {
+ if (prefix2.isIPv6()) return -1;
+ } else {
+ if (prefix2.isIPv4()) return 1;
+ }
+ final int p1len = prefix1.getPrefixLength();
+ final int p2len = prefix2.getPrefixLength();
+ if (p1len < p2len) return -1;
+ if (p2len < p1len) return 1;
+ final byte[] a1 = prefix1.address;
+ final byte[] a2 = prefix2.address;
+ final int len = a1.length < a2.length ? a1.length : a2.length;
+ for (int i = 0; i < len; ++i) {
+ if (a1[i] < a2[i]) return -1;
+ if (a1[i] > a2[i]) return 1;
+ }
+ if (a2.length < len) return 1;
+ if (a1.length < len) return -1;
+ return 0;
+ }
+ };
+ }
+
+ /**
* Implement the Parcelable interface.
*/
public static final Creator<IpPrefix> CREATOR =
diff --git a/core/java/android/net/NetworkUtils.java b/core/java/android/net/NetworkUtils.java
index fe9563d..9a5d502 100644
--- a/core/java/android/net/NetworkUtils.java
+++ b/core/java/android/net/NetworkUtils.java
@@ -16,19 +16,20 @@
package android.net;
-import java.io.FileDescriptor;
-import java.net.InetAddress;
-import java.net.Inet4Address;
-import java.net.Inet6Address;
-import java.net.SocketException;
-import java.net.UnknownHostException;
-import java.util.Collection;
-import java.util.Locale;
-
import android.os.Parcel;
import android.util.Log;
import android.util.Pair;
+import java.io.FileDescriptor;
+import java.math.BigInteger;
+import java.net.Inet4Address;
+import java.net.Inet6Address;
+import java.net.InetAddress;
+import java.net.SocketException;
+import java.net.UnknownHostException;
+import java.util.Collection;
+import java.util.Locale;
+import java.util.TreeSet;
/**
* Native methods for managing network interfaces.
@@ -385,4 +386,72 @@
result = builder.toString();
return result;
}
+
+ /**
+ * Returns a prefix set without overlaps.
+ *
+ * This expects the src set to be sorted from shorter to longer. Results are undefined
+ * failing this condition. The returned prefix set is sorted in the same order as the
+ * passed set, with the same comparator.
+ */
+ private static TreeSet<IpPrefix> deduplicatePrefixSet(final TreeSet<IpPrefix> src) {
+ final TreeSet<IpPrefix> dst = new TreeSet<>(src.comparator());
+ // Prefixes match addresses that share their upper part up to their length, therefore
+ // the only kind of possible overlap in two prefixes is strict inclusion of the longer
+ // (more restrictive) in the shorter (including equivalence if they have the same
+ // length).
+ // Because prefixes in the src set are sorted from shorter to longer, deduplicating
+ // is done by simply iterating in order, and not adding any longer prefix that is
+ // already covered by a shorter one.
+ newPrefixes:
+ for (IpPrefix newPrefix : src) {
+ for (IpPrefix existingPrefix : dst) {
+ if (existingPrefix.containsPrefix(newPrefix)) {
+ continue newPrefixes;
+ }
+ }
+ dst.add(newPrefix);
+ }
+ return dst;
+ }
+
+ /**
+ * Returns how many IPv4 addresses match any of the prefixes in the passed ordered set.
+ *
+ * Obviously this returns an integral value between 0 and 2**32.
+ * The behavior is undefined if any of the prefixes is not an IPv4 prefix or if the
+ * set is not ordered smallest prefix to longer prefix.
+ *
+ * @param prefixes the set of prefixes, ordered by length
+ */
+ public static long routedIPv4AddressCount(final TreeSet<IpPrefix> prefixes) {
+ long routedIPCount = 0;
+ for (final IpPrefix prefix : deduplicatePrefixSet(prefixes)) {
+ if (!prefix.isIPv4()) {
+ Log.wtf(TAG, "Non-IPv4 prefix in routedIPv4AddressCount");
+ }
+ int rank = 32 - prefix.getPrefixLength();
+ routedIPCount += 1L << rank;
+ }
+ return routedIPCount;
+ }
+
+ /**
+ * Returns how many IPv6 addresses match any of the prefixes in the passed ordered set.
+ *
+ * This returns a BigInteger between 0 and 2**128.
+ * The behavior is undefined if any of the prefixes is not an IPv6 prefix or if the
+ * set is not ordered smallest prefix to longer prefix.
+ */
+ public static BigInteger routedIPv6AddressCount(final TreeSet<IpPrefix> prefixes) {
+ BigInteger routedIPCount = BigInteger.ZERO;
+ for (final IpPrefix prefix : deduplicatePrefixSet(prefixes)) {
+ if (!prefix.isIPv6()) {
+ Log.wtf(TAG, "Non-IPv6 prefix in routedIPv6AddressCount");
+ }
+ int rank = 128 - prefix.getPrefixLength();
+ routedIPCount = routedIPCount.add(BigInteger.ONE.shiftLeft(rank));
+ }
+ return routedIPCount;
+ }
}