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/NetworkCapabilities.java b/core/java/android/net/NetworkCapabilities.java
index 07e4ef3..4be01d0 100644
--- a/core/java/android/net/NetworkCapabilities.java
+++ b/core/java/android/net/NetworkCapabilities.java
@@ -958,7 +958,16 @@
     /**
      * List of UIDs this network applies to. No restriction if null.
      * <p>
-     * This is typically (and at this time, only) used by VPN. This network is only available to
+     * For networks, mUids represent the list of network this applies to, and null means this
+     * network applies to all UIDs.
+     * For requests, mUids is the list of UIDs this network MUST apply to to match ; ALL UIDs
+     * must be included in a network so that they match. As an exception to the general rule,
+     * a null mUids field for requests mean "no requirements" rather than what the general rule
+     * would suggest ("must apply to all UIDs") : this is because this has shown to be what users
+     * of this API expect in practice. A network that must match all UIDs can still be
+     * expressed with a set ranging the entire set of possible UIDs.
+     * <p>
+     * mUids is typically (and at this time, only) used by VPN. This network is only available to
      * the UIDs in this list, and it is their default network. Apps in this list that wish to
      * bypass the VPN can do so iff the VPN app allows them to or if they are privileged. If this
      * member is null, then the network is not restricted by app UID. If it's an empty list, then
@@ -1080,8 +1089,7 @@
      * @hide
      */
     public boolean satisfiedByUids(NetworkCapabilities nc) {
-        if (null == nc.mUids) return true; // The network satisfies everything.
-        if (null == mUids) return false; // Not everything allowed but requires everything
+        if (null == nc.mUids || null == mUids) return true; // The network satisfies everything.
         for (UidRange requiredRange : mUids) {
             if (requiredRange.contains(nc.mEstablishingVpnAppUid)) return true;
             if (!nc.appliesToUidRange(requiredRange)) {
diff --git a/core/java/android/net/NetworkRequest.java b/core/java/android/net/NetworkRequest.java
index a3bf682..96826f8 100644
--- a/core/java/android/net/NetworkRequest.java
+++ b/core/java/android/net/NetworkRequest.java
@@ -19,6 +19,7 @@
 import android.annotation.NonNull;
 import android.os.Parcel;
 import android.os.Parcelable;
+import android.os.Process;
 import android.text.TextUtils;
 
 import java.util.Objects;
@@ -131,12 +132,18 @@
      * needed in terms of {@link NetworkCapabilities} features
      */
     public static class Builder {
-        private final NetworkCapabilities mNetworkCapabilities = new NetworkCapabilities();
+        private final NetworkCapabilities mNetworkCapabilities;
 
         /**
          * Default constructor for Builder.
          */
-        public Builder() {}
+        public Builder() {
+            // By default, restrict this request to networks available to this app.
+            // Apps can rescind this restriction, but ConnectivityService will enforce
+            // it for apps that do not have the NETWORK_SETTINGS permission.
+            mNetworkCapabilities = new NetworkCapabilities();
+            mNetworkCapabilities.setSingleUid(Process.myUid());
+        }
 
         /**
          * Build {@link NetworkRequest} give the current set of capabilities.
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;
+    }
 }
diff --git a/services/core/java/com/android/server/ConnectivityService.java b/services/core/java/com/android/server/ConnectivityService.java
index fd2ef18..3021e6a 100644
--- a/services/core/java/com/android/server/ConnectivityService.java
+++ b/services/core/java/com/android/server/ConnectivityService.java
@@ -17,6 +17,7 @@
 package com.android.server;
 
 import static android.Manifest.permission.RECEIVE_DATA_ACTIVITY_CHANGE;
+import static android.content.pm.PackageManager.PERMISSION_GRANTED;
 import static android.net.ConnectivityManager.CONNECTIVITY_ACTION;
 import static android.net.ConnectivityManager.NETID_UNSET;
 import static android.net.ConnectivityManager.TYPE_ETHERNET;
@@ -1329,9 +1330,8 @@
         if (nai != null) {
             synchronized (nai) {
                 if (nai.networkCapabilities != null) {
-                    // TODO : don't remove the UIDs when communicating with processes
-                    // that have the NETWORK_SETTINGS permission.
-                    return networkCapabilitiesWithoutUids(nai.networkCapabilities);
+                    return networkCapabilitiesWithoutUidsUnlessAllowed(nai.networkCapabilities,
+                            Binder.getCallingPid(), Binder.getCallingUid());
                 }
             }
         }
@@ -1344,10 +1344,18 @@
         return getNetworkCapabilitiesInternal(getNetworkAgentInfoForNetwork(network));
     }
 
-    private NetworkCapabilities networkCapabilitiesWithoutUids(NetworkCapabilities nc) {
+    private NetworkCapabilities networkCapabilitiesWithoutUidsUnlessAllowed(
+            NetworkCapabilities nc, int callerPid, int callerUid) {
+        if (checkSettingsPermission(callerPid, callerUid)) return new NetworkCapabilities(nc);
         return new NetworkCapabilities(nc).setUids(null);
     }
 
+    private void restrictRequestUidsForCaller(NetworkCapabilities nc) {
+        if (!checkSettingsPermission()) {
+            nc.setSingleUid(Binder.getCallingUid());
+        }
+    }
+
     @Override
     public NetworkState[] getAllNetworkState() {
         // Require internal since we're handing out IMSI details
@@ -1546,6 +1554,16 @@
                 "ConnectivityService");
     }
 
+    private boolean checkSettingsPermission() {
+        return PERMISSION_GRANTED == mContext.checkCallingOrSelfPermission(
+                android.Manifest.permission.NETWORK_SETTINGS);
+    }
+
+    private boolean checkSettingsPermission(int pid, int uid) {
+        return PERMISSION_GRANTED == mContext.checkPermission(
+                android.Manifest.permission.NETWORK_SETTINGS, pid, uid);
+    }
+
     private void enforceTetherAccessPermission() {
         mContext.enforceCallingOrSelfPermission(
                 android.Manifest.permission.ACCESS_NETWORK_STATE,
@@ -4213,13 +4231,12 @@
             enforceMeteredApnPolicy(networkCapabilities);
         }
         ensureRequestableCapabilities(networkCapabilities);
-        // Set the UID range for this request to the single UID of the requester.
+        // Set the UID range for this request to the single UID of the requester, or to an empty
+        // set of UIDs if the caller has the appropriate permission and UIDs have not been set.
         // This will overwrite any allowed UIDs in the requested capabilities. Though there
         // are no visible methods to set the UIDs, an app could use reflection to try and get
         // networks for other apps so it's essential that the UIDs are overwritten.
-        // TODO : don't forcefully set the UID when communicating with processes
-        // that have the NETWORK_SETTINGS permission.
-        networkCapabilities.setSingleUid(Binder.getCallingUid());
+        restrictRequestUidsForCaller(networkCapabilities);
 
         if (timeoutMs < 0) {
             throw new IllegalArgumentException("Bad timeout specified");
@@ -4293,9 +4310,7 @@
         enforceMeteredApnPolicy(networkCapabilities);
         ensureRequestableCapabilities(networkCapabilities);
         ensureValidNetworkSpecifier(networkCapabilities);
-        // TODO : don't forcefully set the UID when communicating with processes
-        // that have the NETWORK_SETTINGS permission.
-        networkCapabilities.setSingleUid(Binder.getCallingUid());
+        restrictRequestUidsForCaller(networkCapabilities);
 
         NetworkRequest networkRequest = new NetworkRequest(networkCapabilities, TYPE_NONE,
                 nextNetworkRequestId(), NetworkRequest.Type.REQUEST);
@@ -4349,9 +4364,7 @@
         }
 
         NetworkCapabilities nc = new NetworkCapabilities(networkCapabilities);
-        // TODO : don't forcefully set the UIDs when communicating with processes
-        // that have the NETWORK_SETTINGS permission.
-        nc.setSingleUid(Binder.getCallingUid());
+        restrictRequestUidsForCaller(nc);
         if (!ConnectivityManager.checkChangePermission(mContext)) {
             // Apps without the CHANGE_NETWORK_STATE permission can't use background networks, so
             // make all their listens include NET_CAPABILITY_FOREGROUND. That way, they will get
@@ -4381,9 +4394,7 @@
         ensureValidNetworkSpecifier(networkCapabilities);
 
         final NetworkCapabilities nc = new NetworkCapabilities(networkCapabilities);
-        // TODO : don't forcefully set the UIDs when communicating with processes
-        // that have the NETWORK_SETTINGS permission.
-        nc.setSingleUid(Binder.getCallingUid());
+        restrictRequestUidsForCaller(nc);
 
         NetworkRequest networkRequest = new NetworkRequest(nc, TYPE_NONE, nextNetworkRequestId(),
                 NetworkRequest.Type.LISTEN);
@@ -4947,8 +4958,8 @@
             }
             case ConnectivityManager.CALLBACK_CAP_CHANGED: {
                 // networkAgent can't be null as it has been accessed a few lines above.
-                final NetworkCapabilities nc =
-                        networkCapabilitiesWithoutUids(networkAgent.networkCapabilities);
+                final NetworkCapabilities nc = networkCapabilitiesWithoutUidsUnlessAllowed(
+                        networkAgent.networkCapabilities, nri.mPid, nri.mUid);
                 putParcelable(bundle, nc);
                 break;
             }
diff --git a/tests/net/java/android/net/IpPrefixTest.java b/tests/net/java/android/net/IpPrefixTest.java
index b5b2c07..1f1ba2e 100644
--- a/tests/net/java/android/net/IpPrefixTest.java
+++ b/tests/net/java/android/net/IpPrefixTest.java
@@ -223,14 +223,14 @@
     }
 
     @Test
-    public void testContains() {
+    public void testContainsInetAddress() {
         IpPrefix p = new IpPrefix("2001:db8:f00::ace:d00d/127");
         assertTrue(p.contains(Address("2001:db8:f00::ace:d00c")));
         assertTrue(p.contains(Address("2001:db8:f00::ace:d00d")));
         assertFalse(p.contains(Address("2001:db8:f00::ace:d00e")));
         assertFalse(p.contains(Address("2001:db8:f00::bad:d00d")));
         assertFalse(p.contains(Address("2001:4868:4860::8888")));
-        assertFalse(p.contains(null));
+        assertFalse(p.contains((InetAddress)null));
         assertFalse(p.contains(Address("8.8.8.8")));
 
         p = new IpPrefix("192.0.2.0/23");
@@ -251,6 +251,53 @@
     }
 
     @Test
+    public void testContainsIpPrefix() {
+        assertTrue(new IpPrefix("0.0.0.0/0").containsPrefix(new IpPrefix("0.0.0.0/0")));
+        assertTrue(new IpPrefix("0.0.0.0/0").containsPrefix(new IpPrefix("1.2.3.4/0")));
+        assertTrue(new IpPrefix("0.0.0.0/0").containsPrefix(new IpPrefix("1.2.3.4/8")));
+        assertTrue(new IpPrefix("0.0.0.0/0").containsPrefix(new IpPrefix("1.2.3.4/24")));
+        assertTrue(new IpPrefix("0.0.0.0/0").containsPrefix(new IpPrefix("1.2.3.4/23")));
+
+        assertTrue(new IpPrefix("1.2.3.4/8").containsPrefix(new IpPrefix("1.2.3.4/8")));
+        assertTrue(new IpPrefix("1.2.3.4/8").containsPrefix(new IpPrefix("1.254.12.9/8")));
+        assertTrue(new IpPrefix("1.2.3.4/21").containsPrefix(new IpPrefix("1.2.3.4/21")));
+        assertTrue(new IpPrefix("1.2.3.4/32").containsPrefix(new IpPrefix("1.2.3.4/32")));
+
+        assertTrue(new IpPrefix("1.2.3.4/20").containsPrefix(new IpPrefix("1.2.3.0/24")));
+
+        assertFalse(new IpPrefix("1.2.3.4/32").containsPrefix(new IpPrefix("1.2.3.5/32")));
+        assertFalse(new IpPrefix("1.2.3.4/8").containsPrefix(new IpPrefix("2.2.3.4/8")));
+        assertFalse(new IpPrefix("0.0.0.0/16").containsPrefix(new IpPrefix("0.0.0.0/15")));
+        assertFalse(new IpPrefix("100.0.0.0/8").containsPrefix(new IpPrefix("99.0.0.0/8")));
+
+        assertTrue(new IpPrefix("::/0").containsPrefix(new IpPrefix("::/0")));
+        assertTrue(new IpPrefix("::/0").containsPrefix(new IpPrefix("2001:db8::f00/1")));
+        assertTrue(new IpPrefix("::/0").containsPrefix(new IpPrefix("3d8a:661:a0::770/8")));
+        assertTrue(new IpPrefix("::/0").containsPrefix(new IpPrefix("2001:db8::f00/8")));
+        assertTrue(new IpPrefix("::/0").containsPrefix(new IpPrefix("2001:db8::f00/64")));
+        assertTrue(new IpPrefix("::/0").containsPrefix(new IpPrefix("2001:db8::f00/113")));
+        assertTrue(new IpPrefix("::/0").containsPrefix(new IpPrefix("2001:db8::f00/128")));
+
+        assertTrue(new IpPrefix("2001:db8:f00::ace:d00d/64").containsPrefix(
+                new IpPrefix("2001:db8:f00::ace:d00d/64")));
+        assertTrue(new IpPrefix("2001:db8:f00::ace:d00d/64").containsPrefix(
+                new IpPrefix("2001:db8:f00::ace:d00d/120")));
+        assertFalse(new IpPrefix("2001:db8:f00::ace:d00d/64").containsPrefix(
+                new IpPrefix("2001:db8:f00::ace:d00d/32")));
+        assertFalse(new IpPrefix("2001:db8:f00::ace:d00d/64").containsPrefix(
+                new IpPrefix("2006:db8:f00::ace:d00d/96")));
+
+        assertTrue(new IpPrefix("2001:db8:f00::ace:d00d/128").containsPrefix(
+                new IpPrefix("2001:db8:f00::ace:d00d/128")));
+        assertTrue(new IpPrefix("2001:db8:f00::ace:d00d/100").containsPrefix(
+                new IpPrefix("2001:db8:f00::ace:ccaf/110")));
+
+        assertFalse(new IpPrefix("2001:db8:f00::ace:d00d/128").containsPrefix(
+                new IpPrefix("2001:db8:f00::ace:d00e/128")));
+        assertFalse(new IpPrefix("::/30").containsPrefix(new IpPrefix("::/29")));
+    }
+
+    @Test
     public void testHashCode() {
         IpPrefix p = new IpPrefix(new byte[4], 0);
         Random random = new Random();
diff --git a/tests/net/java/android/net/NetworkCapabilitiesTest.java b/tests/net/java/android/net/NetworkCapabilitiesTest.java
index 37b580c..caaa610 100644
--- a/tests/net/java/android/net/NetworkCapabilitiesTest.java
+++ b/tests/net/java/android/net/NetworkCapabilitiesTest.java
@@ -229,7 +229,9 @@
         assertFalse(netCap.appliesToUidRange(new UidRange(60, 3400)));
 
         NetworkCapabilities netCap2 = new NetworkCapabilities();
-        assertFalse(netCap2.satisfiedByUids(netCap));
+        // A new netcap object has null UIDs, so anything will satisfy it.
+        assertTrue(netCap2.satisfiedByUids(netCap));
+        // Still not equal though.
         assertFalse(netCap2.equalsUids(netCap));
         netCap2.setUids(uids);
         assertTrue(netCap2.satisfiedByUids(netCap));
@@ -246,7 +248,7 @@
         assertTrue(netCap.appliesToUid(650));
         assertFalse(netCap.appliesToUid(500));
 
-        assertFalse(new NetworkCapabilities().satisfiedByUids(netCap));
+        assertTrue(new NetworkCapabilities().satisfiedByUids(netCap));
         netCap.combineCapabilities(new NetworkCapabilities());
         assertTrue(netCap.appliesToUid(500));
         assertTrue(netCap.appliesToUidRange(new UidRange(1, 100000)));
diff --git a/tests/net/java/android/net/NetworkUtilsTest.java b/tests/net/java/android/net/NetworkUtilsTest.java
index 8d51c3b..a5ee8e3 100644
--- a/tests/net/java/android/net/NetworkUtilsTest.java
+++ b/tests/net/java/android/net/NetworkUtilsTest.java
@@ -19,8 +19,10 @@
 import android.net.NetworkUtils;
 import android.test.suitebuilder.annotation.SmallTest;
 
+import java.math.BigInteger;
 import java.net.Inet4Address;
 import java.net.InetAddress;
+import java.util.TreeSet;
 
 import junit.framework.TestCase;
 
@@ -67,4 +69,101 @@
         assertInvalidNetworkMask(IPv4Address("255.255.255.253"));
         assertInvalidNetworkMask(IPv4Address("255.255.0.255"));
     }
+
+    @SmallTest
+    public void testRoutedIPv4AddressCount() {
+        final TreeSet<IpPrefix> set = new TreeSet<>(IpPrefix.lengthComparator());
+        // No routes routes to no addresses.
+        assertEquals(0, NetworkUtils.routedIPv4AddressCount(set));
+
+        set.add(new IpPrefix("0.0.0.0/0"));
+        assertEquals(1l << 32, NetworkUtils.routedIPv4AddressCount(set));
+
+        set.add(new IpPrefix("20.18.0.0/16"));
+        set.add(new IpPrefix("20.18.0.0/24"));
+        set.add(new IpPrefix("20.18.0.0/8"));
+        // There is a default route, still covers everything
+        assertEquals(1l << 32, NetworkUtils.routedIPv4AddressCount(set));
+
+        set.clear();
+        set.add(new IpPrefix("20.18.0.0/24"));
+        set.add(new IpPrefix("20.18.0.0/8"));
+        // The 8-length includes the 24-length prefix
+        assertEquals(1l << 24, NetworkUtils.routedIPv4AddressCount(set));
+
+        set.add(new IpPrefix("10.10.10.126/25"));
+        // The 8-length does not include this 25-length prefix
+        assertEquals((1l << 24) + (1 << 7), NetworkUtils.routedIPv4AddressCount(set));
+
+        set.clear();
+        set.add(new IpPrefix("1.2.3.4/32"));
+        set.add(new IpPrefix("1.2.3.4/32"));
+        set.add(new IpPrefix("1.2.3.4/32"));
+        set.add(new IpPrefix("1.2.3.4/32"));
+        assertEquals(1l, NetworkUtils.routedIPv4AddressCount(set));
+
+        set.add(new IpPrefix("1.2.3.5/32"));
+        set.add(new IpPrefix("1.2.3.6/32"));
+
+        set.add(new IpPrefix("1.2.3.7/32"));
+        set.add(new IpPrefix("1.2.3.8/32"));
+        set.add(new IpPrefix("1.2.3.9/32"));
+        set.add(new IpPrefix("1.2.3.0/32"));
+        assertEquals(7l, NetworkUtils.routedIPv4AddressCount(set));
+
+        // 1.2.3.4/30 eats 1.2.3.{4-7}/32
+        set.add(new IpPrefix("1.2.3.4/30"));
+        set.add(new IpPrefix("6.2.3.4/28"));
+        set.add(new IpPrefix("120.2.3.4/16"));
+        assertEquals(7l - 4 + 4 + 16 + 65536, NetworkUtils.routedIPv4AddressCount(set));
+    }
+
+    @SmallTest
+    public void testRoutedIPv6AddressCount() {
+        final TreeSet<IpPrefix> set = new TreeSet<>(IpPrefix.lengthComparator());
+        // No routes routes to no addresses.
+        assertEquals(BigInteger.ZERO, NetworkUtils.routedIPv6AddressCount(set));
+
+        set.add(new IpPrefix("::/0"));
+        assertEquals(BigInteger.ONE.shiftLeft(128), NetworkUtils.routedIPv6AddressCount(set));
+
+        set.add(new IpPrefix("1234:622a::18/64"));
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6adb/96"));
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6adb/8"));
+        // There is a default route, still covers everything
+        assertEquals(BigInteger.ONE.shiftLeft(128), NetworkUtils.routedIPv6AddressCount(set));
+
+        set.clear();
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6adb/96"));
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6adb/8"));
+        // The 8-length includes the 96-length prefix
+        assertEquals(BigInteger.ONE.shiftLeft(120), NetworkUtils.routedIPv6AddressCount(set));
+
+        set.add(new IpPrefix("10::26/64"));
+        // The 8-length does not include this 64-length prefix
+        assertEquals(BigInteger.ONE.shiftLeft(120).add(BigInteger.ONE.shiftLeft(64)),
+                NetworkUtils.routedIPv6AddressCount(set));
+
+        set.clear();
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6ad4/128"));
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6ad4/128"));
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6ad4/128"));
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6ad4/128"));
+        assertEquals(BigInteger.ONE, NetworkUtils.routedIPv6AddressCount(set));
+
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6ad5/128"));
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6ad6/128"));
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6ad7/128"));
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6ad8/128"));
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6ad9/128"));
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6ad0/128"));
+        assertEquals(BigInteger.valueOf(7), NetworkUtils.routedIPv6AddressCount(set));
+
+        // add4:f00:80:f7:1111::6ad4/126 eats add4:f00:8[:f7:1111::6ad{4-7}/128
+        set.add(new IpPrefix("add4:f00:80:f7:1111::6ad4/126"));
+        set.add(new IpPrefix("d00d:f00:80:f7:1111::6ade/124"));
+        set.add(new IpPrefix("f00b:a33::/112"));
+        assertEquals(BigInteger.valueOf(7l - 4 + 4 + 16 + 65536),
+                NetworkUtils.routedIPv6AddressCount(set));
+    }
 }
diff --git a/tests/net/java/com/android/server/ConnectivityServiceTest.java b/tests/net/java/com/android/server/ConnectivityServiceTest.java
index 28f8122..5ea21ea 100644
--- a/tests/net/java/com/android/server/ConnectivityServiceTest.java
+++ b/tests/net/java/com/android/server/ConnectivityServiceTest.java
@@ -387,6 +387,7 @@
                     mScore = 20;
                     break;
                 case TRANSPORT_VPN:
+                    mNetworkCapabilities.removeCapability(NET_CAPABILITY_NOT_VPN);
                     mScore = ConnectivityConstants.VPN_DEFAULT_SCORE;
                     break;
                 default:
@@ -3744,14 +3745,19 @@
         final int uid = Process.myUid();
 
         final TestNetworkCallback genericNetworkCallback = new TestNetworkCallback();
+        final TestNetworkCallback genericNotVpnNetworkCallback = new TestNetworkCallback();
         final TestNetworkCallback wifiNetworkCallback = new TestNetworkCallback();
         final TestNetworkCallback vpnNetworkCallback = new TestNetworkCallback();
-        final NetworkRequest genericRequest = new NetworkRequest.Builder().build();
+        final NetworkRequest genericNotVpnRequest = new NetworkRequest.Builder().build();
+        final NetworkRequest genericRequest = new NetworkRequest.Builder()
+                .removeCapability(NET_CAPABILITY_NOT_VPN).build();
         final NetworkRequest wifiRequest = new NetworkRequest.Builder()
                 .addTransportType(TRANSPORT_WIFI).build();
         final NetworkRequest vpnNetworkRequest = new NetworkRequest.Builder()
+                .removeCapability(NET_CAPABILITY_NOT_VPN)
                 .addTransportType(TRANSPORT_VPN).build();
         mCm.registerNetworkCallback(genericRequest, genericNetworkCallback);
+        mCm.registerNetworkCallback(genericNotVpnRequest, genericNotVpnNetworkCallback);
         mCm.registerNetworkCallback(wifiRequest, wifiNetworkCallback);
         mCm.registerNetworkCallback(vpnNetworkRequest, vpnNetworkCallback);
 
@@ -3759,6 +3765,7 @@
         mWiFiNetworkAgent.connect(false);
 
         genericNetworkCallback.expectAvailableCallbacksUnvalidated(mWiFiNetworkAgent);
+        genericNotVpnNetworkCallback.expectAvailableCallbacksUnvalidated(mWiFiNetworkAgent);
         wifiNetworkCallback.expectAvailableCallbacksUnvalidated(mWiFiNetworkAgent);
         vpnNetworkCallback.assertNoCallback();
 
@@ -3773,16 +3780,19 @@
         vpnNetworkAgent.connect(false);
 
         genericNetworkCallback.expectAvailableCallbacksUnvalidated(vpnNetworkAgent);
+        genericNotVpnNetworkCallback.assertNoCallback();
         wifiNetworkCallback.assertNoCallback();
         vpnNetworkCallback.expectAvailableCallbacksUnvalidated(vpnNetworkAgent);
 
         genericNetworkCallback.expectCallback(CallbackState.NETWORK_CAPABILITIES, vpnNetworkAgent);
+        genericNotVpnNetworkCallback.assertNoCallback();
         vpnNetworkCallback.expectCapabilitiesLike(nc -> null == nc.getUids(), vpnNetworkAgent);
 
         ranges.clear();
         vpnNetworkAgent.setUids(ranges);
 
         genericNetworkCallback.expectCallback(CallbackState.LOST, vpnNetworkAgent);
+        genericNotVpnNetworkCallback.assertNoCallback();
         wifiNetworkCallback.assertNoCallback();
         vpnNetworkCallback.expectCallback(CallbackState.LOST, vpnNetworkAgent);
 
@@ -3790,18 +3800,21 @@
         vpnNetworkAgent.setUids(ranges);
 
         genericNetworkCallback.expectAvailableCallbacksValidated(vpnNetworkAgent);
+        genericNotVpnNetworkCallback.assertNoCallback();
         wifiNetworkCallback.assertNoCallback();
         vpnNetworkCallback.expectAvailableCallbacksValidated(vpnNetworkAgent);
 
         mWiFiNetworkAgent.disconnect();
 
         genericNetworkCallback.expectCallback(CallbackState.LOST, mWiFiNetworkAgent);
+        genericNotVpnNetworkCallback.expectCallback(CallbackState.LOST, mWiFiNetworkAgent);
         wifiNetworkCallback.expectCallback(CallbackState.LOST, mWiFiNetworkAgent);
         vpnNetworkCallback.assertNoCallback();
 
         vpnNetworkAgent.disconnect();
 
         genericNetworkCallback.expectCallback(CallbackState.LOST, vpnNetworkAgent);
+        genericNotVpnNetworkCallback.assertNoCallback();
         wifiNetworkCallback.assertNoCallback();
         vpnNetworkCallback.expectCallback(CallbackState.LOST, vpnNetworkAgent);
 
diff --git a/tests/net/java/com/android/server/connectivity/VpnTest.java b/tests/net/java/com/android/server/connectivity/VpnTest.java
index 1dbf9b2..f59850d 100644
--- a/tests/net/java/com/android/server/connectivity/VpnTest.java
+++ b/tests/net/java/com/android/server/connectivity/VpnTest.java
@@ -57,9 +57,13 @@
 import android.content.pm.UserInfo;
 import android.content.res.Resources;
 import android.net.ConnectivityManager;
+import android.net.IConnectivityManager;
+import android.net.IpPrefix;
+import android.net.LinkProperties;
 import android.net.Network;
 import android.net.NetworkCapabilities;
 import android.net.NetworkInfo.DetailedState;
+import android.net.RouteInfo;
 import android.net.UidRange;
 import android.net.VpnService;
 import android.os.Build.VERSION_CODES;
@@ -90,7 +94,8 @@
 import java.util.HashMap;
 import java.util.Map;
 import java.util.Set;
-
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
 
 /**
  * Tests for {@link Vpn}.
@@ -563,4 +568,75 @@
             return networks.get(network);
         }).when(mConnectivityManager).getNetworkCapabilities(any());
     }
+
+    // Need multiple copies of this, but Java's Stream objects can't be reused or
+    // duplicated.
+    private Stream<String> publicIpV4Routes() {
+        return Stream.of(
+                "0.0.0.0/5", "8.0.0.0/7", "11.0.0.0/8", "12.0.0.0/6", "16.0.0.0/4",
+                "32.0.0.0/3", "64.0.0.0/2", "128.0.0.0/3", "160.0.0.0/5", "168.0.0.0/6",
+                "172.0.0.0/12", "172.32.0.0/11", "172.64.0.0/10", "172.128.0.0/9",
+                "173.0.0.0/8", "174.0.0.0/7", "176.0.0.0/4", "192.0.0.0/9", "192.128.0.0/11",
+                "192.160.0.0/13", "192.169.0.0/16", "192.170.0.0/15", "192.172.0.0/14",
+                "192.176.0.0/12", "192.192.0.0/10", "193.0.0.0/8", "194.0.0.0/7",
+                "196.0.0.0/6", "200.0.0.0/5", "208.0.0.0/4");
+    }
+
+    private Stream<String> publicIpV6Routes() {
+        return Stream.of(
+                "::/1", "8000::/2", "c000::/3", "e000::/4", "f000::/5", "f800::/6",
+                "fe00::/8", "2605:ef80:e:af1d::/64");
+    }
+
+    @Test
+    public void testProvidesRoutesToMostDestinations() {
+        final LinkProperties lp = new LinkProperties();
+
+        // Default route provides routes to all IPv4 destinations.
+        lp.addRoute(new RouteInfo(new IpPrefix("0.0.0.0/0")));
+        assertTrue(Vpn.providesRoutesToMostDestinations(lp));
+
+        // Empty LP provides routes to no destination
+        lp.clear();
+        assertFalse(Vpn.providesRoutesToMostDestinations(lp));
+
+        // All IPv4 routes except for local networks. This is the case most relevant
+        // to this function. It provides routes to almost the entire space.
+        // (clone the stream so that we can reuse it later)
+        publicIpV4Routes().forEach(s -> lp.addRoute(new RouteInfo(new IpPrefix(s))));
+        assertTrue(Vpn.providesRoutesToMostDestinations(lp));
+
+        // Removing a 16-bit prefix, which is 65536 addresses. This is still enough to
+        // provide routes to "most" destinations.
+        lp.removeRoute(new RouteInfo(new IpPrefix("192.169.0.0/16")));
+        assertTrue(Vpn.providesRoutesToMostDestinations(lp));
+
+        // Remove the /2 route, which represent a quarter of the available routing space.
+        // This LP does not provides routes to "most" destinations any more.
+        lp.removeRoute(new RouteInfo(new IpPrefix("64.0.0.0/2")));
+        assertFalse(Vpn.providesRoutesToMostDestinations(lp));
+
+        lp.clear();
+        publicIpV6Routes().forEach(s -> lp.addRoute(new RouteInfo(new IpPrefix(s))));
+        assertTrue(Vpn.providesRoutesToMostDestinations(lp));
+
+        lp.removeRoute(new RouteInfo(new IpPrefix("::/1")));
+        assertFalse(Vpn.providesRoutesToMostDestinations(lp));
+
+        // V6 does not provide sufficient coverage but v4 does
+        publicIpV4Routes().forEach(s -> lp.addRoute(new RouteInfo(new IpPrefix(s))));
+        assertTrue(Vpn.providesRoutesToMostDestinations(lp));
+
+        // V4 still does
+        lp.removeRoute(new RouteInfo(new IpPrefix("192.169.0.0/16")));
+        assertTrue(Vpn.providesRoutesToMostDestinations(lp));
+
+        // V4 does not any more
+        lp.removeRoute(new RouteInfo(new IpPrefix("64.0.0.0/2")));
+        assertFalse(Vpn.providesRoutesToMostDestinations(lp));
+
+        // V4 does not, but V6 has sufficient coverage again
+        lp.addRoute(new RouteInfo(new IpPrefix("::/1")));
+        assertTrue(Vpn.providesRoutesToMostDestinations(lp));
+    }
 }