Merge "Give VPNs the INTERNET capability when they route most of the IP space" am: 20013384dc

am: 18e51821b1

Change-Id: I33c6fcc72753e00af601cf915aa78416174a3871

2 files changed, 122 insertions, 6 deletions

diff --git a/core/java/android/net/IpPrefix.java b/core/java/android/net/IpPrefix.java
index 6e2654e3ce7c..4631c565962f 100644
--- a/core/java/android/net/IpPrefix.java
+++ b/core/java/android/net/IpPrefix.java
@@ -25,6 +25,7 @@ import java.net.Inet6Address;
 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 @@ public final class IpPrefix implements Parcelable {
     }
 
     /**
+     * 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 @@ public final class IpPrefix implements Parcelable {
     }
 
     /**
+     * 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 fe9563d6d325..9a5d502673f3 100644
--- a/core/java/android/net/NetworkUtils.java
+++ b/core/java/android/net/NetworkUtils.java
@@ -16,19 +16,20 @@
 
 package android.net;
 
+import android.os.Parcel;
+import android.util.Log;
+import android.util.Pair;
+
 import java.io.FileDescriptor;
-import java.net.InetAddress;
+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 android.os.Parcel;
-import android.util.Log;
-import android.util.Pair;
-
+import java.util.TreeSet;
 
 /**
  * Native methods for managing network interfaces.
@@ -385,4 +386,72 @@ public class NetworkUtils {
         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;
+    }
 }