Tethering: ensure downstream prefix do not conflict with upstream

- Add New class PrivateAddressCoordinator to coordinate the private
  address conflict problem.
- Downstream prefix would be random in 192.168.0.0/24 ~
  192.168.255.0/24.
- If new upstream prefix is conflict with existing downstream prefix,
  downstream would be kicked out and it would request a new one.
- The last conflict upstream prefixes would be blacklist. Avoid to
select downstream prefix which is conflict with prefixes in blacklist.

Bug: 130879722
Test: -build, flash, boot
      -atest TetheringTests

Merged-In: Ib45b87bcd9eeb5da03fb7ec90b1af9ca53998cf5
Change-Id: Ib45b87bcd9eeb5da03fb7ec90b1af9ca53998cf5
diff --git a/Tethering/src/android/net/ip/IpServer.java b/Tethering/src/android/net/ip/IpServer.java
index 659d344..f08429b 100644
--- a/Tethering/src/android/net/ip/IpServer.java
+++ b/Tethering/src/android/net/ip/IpServer.java
@@ -16,14 +16,13 @@
 
 package android.net.ip;
 
-import static android.net.InetAddresses.parseNumericAddress;
 import static android.net.RouteInfo.RTN_UNICAST;
 import static android.net.TetheringManager.TetheringRequest.checkStaticAddressConfiguration;
 import static android.net.dhcp.IDhcpServer.STATUS_SUCCESS;
 import static android.net.shared.Inet4AddressUtils.intToInet4AddressHTH;
-import static android.net.util.NetworkConstants.FF;
 import static android.net.util.NetworkConstants.RFC7421_PREFIX_LENGTH;
 import static android.net.util.NetworkConstants.asByte;
+import static android.net.util.PrefixUtils.asIpPrefix;
 import static android.net.util.TetheringMessageBase.BASE_IPSERVER;
 import static android.system.OsConstants.RT_SCOPE_UNIVERSE;
 
@@ -66,11 +65,11 @@
 import com.android.internal.util.MessageUtils;
 import com.android.internal.util.State;
 import com.android.internal.util.StateMachine;
+import com.android.networkstack.tethering.PrivateAddressCoordinator;
 
 import java.io.IOException;
 import java.net.Inet4Address;
 import java.net.Inet6Address;
-import java.net.InetAddress;
 import java.net.NetworkInterface;
 import java.net.UnknownHostException;
 import java.util.ArrayList;
@@ -108,27 +107,8 @@
 
     private static final byte DOUG_ADAMS = (byte) 42;
 
-    private static final String USB_NEAR_IFACE_ADDR = "192.168.42.129";
-    private static final int USB_PREFIX_LENGTH = 24;
-    private static final String WIFI_HOST_IFACE_ADDR = "192.168.43.1";
-    private static final int WIFI_HOST_IFACE_PREFIX_LENGTH = 24;
-    private static final String WIFI_P2P_IFACE_ADDR = "192.168.49.1";
-    private static final int WIFI_P2P_IFACE_PREFIX_LENGTH = 24;
-    private static final String ETHERNET_IFACE_ADDR = "192.168.50.1";
-    private static final int ETHERNET_IFACE_PREFIX_LENGTH = 24;
-
-    // TODO: remove this constant after introducing PrivateAddressCoordinator.
-    private static final List<IpPrefix> NCM_PREFIXES = Collections.unmodifiableList(
-            Arrays.asList(
-                    new IpPrefix("192.168.42.0/24"),
-                    new IpPrefix("192.168.51.0/24"),
-                    new IpPrefix("192.168.52.0/24"),
-                    new IpPrefix("192.168.53.0/24")
-    ));
-
     // TODO: have PanService use some visible version of this constant
-    private static final String BLUETOOTH_IFACE_ADDR = "192.168.44.1";
-    private static final int BLUETOOTH_DHCP_PREFIX_LENGTH = 24;
+    private static final String BLUETOOTH_IFACE_ADDR = "192.168.44.1/24";
 
     // TODO: have this configurable
     private static final int DHCP_LEASE_TIME_SECS = 3600;
@@ -167,6 +147,14 @@
          * Notify that the DHCP leases changed in one of the IpServers.
          */
         public void dhcpLeasesChanged() { }
+
+        /**
+         * Request Tethering change.
+         *
+         * @param tetheringType the downstream type of this IpServer.
+         * @param enabled enable or disable tethering.
+         */
+        public void requestEnableTethering(int tetheringType, boolean enabled) { }
     }
 
     /** Capture IpServer dependencies, for injection. */
@@ -196,6 +184,7 @@
                 return 0;
             }
         }
+
         /** Create a DhcpServer instance to be used by IpServer. */
         public abstract void makeDhcpServer(String ifName, DhcpServingParamsParcel params,
                 DhcpServerCallbacks cb);
@@ -225,16 +214,20 @@
     public static final int CMD_NEIGHBOR_EVENT              = BASE_IPSERVER + 11;
     // request from DHCP server that it wants to have a new prefix
     public static final int CMD_NEW_PREFIX_REQUEST          = BASE_IPSERVER + 12;
+    // request from PrivateAddressCoordinator to restart tethering.
+    public static final int CMD_NOTIFY_PREFIX_CONFLICT      = BASE_IPSERVER + 13;
 
     private final State mInitialState;
     private final State mLocalHotspotState;
     private final State mTetheredState;
     private final State mUnavailableState;
+    private final State mWaitingForRestartState;
 
     private final SharedLog mLog;
     private final INetd mNetd;
     private final Callback mCallback;
     private final InterfaceController mInterfaceCtrl;
+    private final PrivateAddressCoordinator mPrivateAddressCoordinator;
 
     private final String mIfaceName;
     private final int mInterfaceType;
@@ -261,7 +254,6 @@
     private int mDhcpServerStartIndex = 0;
     private IDhcpServer mDhcpServer;
     private RaParams mLastRaParams;
-    private LinkAddress mIpv4Address;
 
     private LinkAddress mStaticIpv4ServerAddr;
     private LinkAddress mStaticIpv4ClientAddr;
@@ -316,12 +308,14 @@
 
     private final IpNeighborMonitor mIpNeighborMonitor;
 
+    private LinkAddress mIpv4Address;
+
     // TODO: Add a dependency object to pass the data members or variables from the tethering
     // object. It helps to reduce the arguments of the constructor.
     public IpServer(
             String ifaceName, Looper looper, int interfaceType, SharedLog log,
             INetd netd, Callback callback, boolean usingLegacyDhcp, boolean usingBpfOffload,
-            Dependencies deps) {
+            PrivateAddressCoordinator addressCoordinator, Dependencies deps) {
         super(ifaceName, looper);
         mLog = log.forSubComponent(ifaceName);
         mNetd = netd;
@@ -332,6 +326,7 @@
         mLinkProperties = new LinkProperties();
         mUsingLegacyDhcp = usingLegacyDhcp;
         mUsingBpfOffload = usingBpfOffload;
+        mPrivateAddressCoordinator = addressCoordinator;
         mDeps = deps;
         resetLinkProperties();
         mLastError = TetheringManager.TETHER_ERROR_NO_ERROR;
@@ -352,9 +347,11 @@
         mLocalHotspotState = new LocalHotspotState();
         mTetheredState = new TetheredState();
         mUnavailableState = new UnavailableState();
+        mWaitingForRestartState = new WaitingForRestartState();
         addState(mInitialState);
         addState(mLocalHotspotState);
         addState(mTetheredState);
+        addState(mWaitingForRestartState, mTetheredState);
         addState(mUnavailableState);
 
         setInitialState(mInitialState);
@@ -387,6 +384,11 @@
         return new LinkProperties(mLinkProperties);
     }
 
+    /** The address which IpServer is using. */
+    public LinkAddress getAddress() {
+        return mIpv4Address;
+    }
+
     /**
      * Get the latest list of DHCP leases that was reported. Must be called on the IpServer looper
      * thread.
@@ -617,6 +619,7 @@
         // NOTE: All of configureIPv4() will be refactored out of existence
         // into calls to InterfaceController, shared with startIPv4().
         mInterfaceCtrl.clearIPv4Address();
+        mPrivateAddressCoordinator.releaseDownstream(this);
         mIpv4Address = null;
         mStaticIpv4ServerAddr = null;
         mStaticIpv4ClientAddr = null;
@@ -625,43 +628,24 @@
     private boolean configureIPv4(boolean enabled) {
         if (VDBG) Log.d(TAG, "configureIPv4(" + enabled + ")");
 
-        // TODO: Replace this hard-coded information with dynamically selected
-        // config passed down to us by a higher layer IP-coordinating element.
-        final Inet4Address srvAddr;
-        int prefixLen = 0;
-        try {
-            if (mStaticIpv4ServerAddr != null) {
-                srvAddr = (Inet4Address) mStaticIpv4ServerAddr.getAddress();
-                prefixLen = mStaticIpv4ServerAddr.getPrefixLength();
-            } else if (mInterfaceType == TetheringManager.TETHERING_USB
-                    || mInterfaceType == TetheringManager.TETHERING_NCM) {
-                srvAddr = (Inet4Address) parseNumericAddress(USB_NEAR_IFACE_ADDR);
-                prefixLen = USB_PREFIX_LENGTH;
-            } else if (mInterfaceType == TetheringManager.TETHERING_WIFI) {
-                srvAddr = (Inet4Address) parseNumericAddress(getRandomWifiIPv4Address());
-                prefixLen = WIFI_HOST_IFACE_PREFIX_LENGTH;
-            } else if (mInterfaceType == TetheringManager.TETHERING_WIFI_P2P) {
-                srvAddr = (Inet4Address) parseNumericAddress(WIFI_P2P_IFACE_ADDR);
-                prefixLen = WIFI_P2P_IFACE_PREFIX_LENGTH;
-            } else if (mInterfaceType == TetheringManager.TETHERING_ETHERNET) {
-                // TODO: randomize address for tethering too, similarly to wifi
-                srvAddr = (Inet4Address) parseNumericAddress(ETHERNET_IFACE_ADDR);
-                prefixLen = ETHERNET_IFACE_PREFIX_LENGTH;
-            } else {
-                // BT configures the interface elsewhere: only start DHCP.
-                // TODO: make all tethering types behave the same way, and delete the bluetooth
-                // code that calls into NetworkManagementService directly.
-                srvAddr = (Inet4Address) parseNumericAddress(BLUETOOTH_IFACE_ADDR);
-                mIpv4Address = new LinkAddress(srvAddr, BLUETOOTH_DHCP_PREFIX_LENGTH);
-                return configureDhcp(enabled, mIpv4Address, null /* clientAddress */);
-            }
-            mIpv4Address = new LinkAddress(srvAddr, prefixLen);
-        } catch (IllegalArgumentException e) {
-            mLog.e("Error selecting ipv4 address", e);
-            if (!enabled) stopDhcp();
+        if (enabled) {
+            mIpv4Address = requestIpv4Address();
+        }
+
+        if (mIpv4Address == null) {
+            mLog.e("No available ipv4 address");
             return false;
         }
 
+        if (mInterfaceType == TetheringManager.TETHERING_BLUETOOTH) {
+            // BT configures the interface elsewhere: only start DHCP.
+            // TODO: make all tethering types behave the same way, and delete the bluetooth
+            // code that calls into NetworkManagementService directly.
+            return configureDhcp(enabled, mIpv4Address, null /* clientAddress */);
+        }
+
+        final IpPrefix ipv4Prefix = asIpPrefix(mIpv4Address);
+
         final Boolean setIfaceUp;
         if (mInterfaceType == TetheringManager.TETHERING_WIFI
                 || mInterfaceType == TetheringManager.TETHERING_WIFI_P2P) {
@@ -688,21 +672,14 @@
         return configureDhcp(enabled, mIpv4Address, mStaticIpv4ClientAddr);
     }
 
-    private Inet4Address getRandomIPv4Address(@NonNull final byte[] rawAddr) {
-        final byte[] ipv4Addr = rawAddr;
-        ipv4Addr[3] = getRandomSanitizedByte(DOUG_ADAMS, asByte(0), asByte(1), FF);
-        try {
-            return (Inet4Address) InetAddress.getByAddress(ipv4Addr);
-        } catch (UnknownHostException e) {
-            mLog.e("Failed to construct Inet4Address from raw IPv4 addr");
-            return null;
-        }
-    }
+    private LinkAddress requestIpv4Address() {
+        if (mStaticIpv4ServerAddr != null) return mStaticIpv4ServerAddr;
 
-    private String getRandomWifiIPv4Address() {
-        final Inet4Address ipv4Addr =
-                getRandomIPv4Address(parseNumericAddress(WIFI_HOST_IFACE_ADDR).getAddress());
-        return ipv4Addr != null ? ipv4Addr.getHostAddress() : WIFI_HOST_IFACE_ADDR;
+        if (mInterfaceType == TetheringManager.TETHERING_BLUETOOTH) {
+            return new LinkAddress(BLUETOOTH_IFACE_ADDR);
+        }
+
+        return mPrivateAddressCoordinator.requestDownstreamAddress(this);
     }
 
     private boolean startIPv6() {
@@ -978,19 +955,6 @@
         }
     }
 
-    // TODO: call PrivateAddressCoordinator.requestDownstreamAddress instead of this temporary
-    // logic.
-    private Inet4Address requestDownstreamAddress(@NonNull final IpPrefix currentPrefix) {
-        final int oldIndex = NCM_PREFIXES.indexOf(currentPrefix);
-        if (oldIndex == -1) {
-            mLog.e("current prefix isn't supported for NCM link: " + currentPrefix);
-            return null;
-        }
-
-        final IpPrefix newPrefix = NCM_PREFIXES.get((oldIndex + 1) % NCM_PREFIXES.size());
-        return getRandomIPv4Address(newPrefix.getRawAddress());
-    }
-
     private void handleNewPrefixRequest(@NonNull final IpPrefix currentPrefix) {
         if (!currentPrefix.contains(mIpv4Address.getAddress())
                 || currentPrefix.getPrefixLength() != mIpv4Address.getPrefixLength()) {
@@ -999,12 +963,12 @@
         }
 
         final LinkAddress deprecatedLinkAddress = mIpv4Address;
-        final Inet4Address srvAddr = requestDownstreamAddress(currentPrefix);
-        if (srvAddr == null) {
+        mIpv4Address = requestIpv4Address();
+        if (mIpv4Address == null) {
             mLog.e("Fail to request a new downstream prefix");
             return;
         }
-        mIpv4Address = new LinkAddress(srvAddr, currentPrefix.getPrefixLength());
+        final Inet4Address srvAddr = (Inet4Address) mIpv4Address.getAddress();
 
         // Add new IPv4 address on the interface.
         if (!mInterfaceCtrl.addAddress(srvAddr, currentPrefix.getPrefixLength())) {
@@ -1162,7 +1126,7 @@
             }
 
             try {
-                NetdUtils.tetherInterface(mNetd, mIfaceName, PrefixUtils.asIpPrefix(mIpv4Address));
+                NetdUtils.tetherInterface(mNetd, mIfaceName, asIpPrefix(mIpv4Address));
             } catch (RemoteException | ServiceSpecificException | IllegalStateException e) {
                 mLog.e("Error Tethering", e);
                 mLastError = TetheringManager.TETHER_ERROR_TETHER_IFACE_ERROR;
@@ -1222,6 +1186,11 @@
                 case CMD_NEW_PREFIX_REQUEST:
                     handleNewPrefixRequest((IpPrefix) message.obj);
                     break;
+                case CMD_NOTIFY_PREFIX_CONFLICT:
+                    mLog.i("restart tethering: " + mInterfaceType);
+                    mCallback.requestEnableTethering(mInterfaceType, false /* enabled */);
+                    transitionTo(mWaitingForRestartState);
+                    break;
                 default:
                     return false;
             }
@@ -1403,6 +1372,28 @@
         }
     }
 
+    class WaitingForRestartState extends State {
+        @Override
+        public boolean processMessage(Message message) {
+            logMessage(this, message.what);
+            switch (message.what) {
+                case CMD_TETHER_UNREQUESTED:
+                    transitionTo(mInitialState);
+                    mLog.i("Untethered (unrequested) and restarting " + mIfaceName);
+                    mCallback.requestEnableTethering(mInterfaceType, true /* enabled */);
+                    break;
+                case CMD_INTERFACE_DOWN:
+                    transitionTo(mUnavailableState);
+                    mLog.i("Untethered (interface down) and restarting" + mIfaceName);
+                    mCallback.requestEnableTethering(mInterfaceType, true /* enabled */);
+                    break;
+                default:
+                    return false;
+            }
+            return true;
+        }
+    }
+
     // Accumulate routes representing "prefixes to be assigned to the local
     // interface", for subsequent modification of local_network routing.
     private static ArrayList<RouteInfo> getLocalRoutesFor(
diff --git a/Tethering/src/com/android/networkstack/tethering/PrivateAddressCoordinator.java b/Tethering/src/com/android/networkstack/tethering/PrivateAddressCoordinator.java
new file mode 100644
index 0000000..160a166
--- /dev/null
+++ b/Tethering/src/com/android/networkstack/tethering/PrivateAddressCoordinator.java
@@ -0,0 +1,254 @@
+/*
+ * 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 com.android.networkstack.tethering;
+
+import android.content.Context;
+import android.net.ConnectivityManager;
+import android.net.IpPrefix;
+import android.net.LinkAddress;
+import android.net.LinkProperties;
+import android.net.Network;
+import android.net.ip.IpServer;
+import android.net.util.PrefixUtils;
+import android.util.ArrayMap;
+import android.util.ArraySet;
+
+import androidx.annotation.Nullable;
+
+import com.android.internal.annotations.VisibleForTesting;
+import com.android.internal.util.IndentingPrintWriter;
+
+import java.net.InetAddress;
+import java.net.UnknownHostException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.Random;
+
+/**
+ * This class coordinate IP addresses conflict problem.
+ *
+ * Tethering downstream IP addresses may conflict with network assigned addresses. This
+ * coordinator is responsible for recording all of network assigned addresses and dispatched
+ * free address to downstream interfaces.
+ *
+ * This class is not thread-safe and should be accessed on the same tethering internal thread.
+ * @hide
+ */
+public class PrivateAddressCoordinator {
+    public static final int PREFIX_LENGTH = 24;
+
+    private static final int MAX_UBYTE = 256;
+    private static final int BYTE_MASK = 0xff;
+    // reserved for bluetooth tethering.
+    private static final int BLUETOOTH_RESERVED = 44;
+    private static final byte DEFAULT_ID = (byte) 42;
+
+    // Upstream monitor would be stopped when tethering is down. When tethering restart, downstream
+    // address may be requested before coordinator get current upstream notification. To ensure
+    // coordinator do not select conflict downstream prefix, mUpstreamPrefixMap would not be cleared
+    // when tethering is down. Instead coordinator would remove all depcreted upstreams from
+    // mUpstreamPrefixMap when tethering is starting. See #maybeRemoveDeprectedUpstreams().
+    private final ArrayMap<Network, List<IpPrefix>> mUpstreamPrefixMap;
+    private final ArraySet<IpServer> mDownstreams;
+    // IANA has reserved the following three blocks of the IP address space for private intranets:
+    // 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16
+    // Tethering use 192.168.0.0/16 that has 256 contiguous class C network numbers.
+    private static final String DEFAULT_TETHERING_PREFIX = "192.168.0.0/16";
+    private final IpPrefix mTetheringPrefix;
+    private final ConnectivityManager mConnectivityMgr;
+
+    public PrivateAddressCoordinator(Context context) {
+        mDownstreams = new ArraySet<>();
+        mUpstreamPrefixMap = new ArrayMap<>();
+        mTetheringPrefix = new IpPrefix(DEFAULT_TETHERING_PREFIX);
+        mConnectivityMgr = (ConnectivityManager) context.getSystemService(
+                Context.CONNECTIVITY_SERVICE);
+    }
+
+    /**
+     * Record a new upstream IpPrefix which may conflict with tethering downstreams.
+     * The downstreams will be notified if a conflict is found.
+     */
+    public void updateUpstreamPrefix(final Network network, final LinkProperties lp) {
+        final ArrayList<IpPrefix> ipv4Prefixes = getIpv4Prefixes(lp.getAllLinkAddresses());
+        if (ipv4Prefixes.isEmpty()) {
+            removeUpstreamPrefix(network);
+            return;
+        }
+
+        mUpstreamPrefixMap.put(network, ipv4Prefixes);
+        handleMaybePrefixConflict(ipv4Prefixes);
+    }
+
+    private ArrayList<IpPrefix> getIpv4Prefixes(final List<LinkAddress> linkAddresses) {
+        final ArrayList<IpPrefix> list = new ArrayList<>();
+        for (LinkAddress address : linkAddresses) {
+            if (!address.isIpv4()) continue;
+
+            list.add(PrefixUtils.asIpPrefix(address));
+        }
+
+        return list;
+    }
+
+    private void handleMaybePrefixConflict(final List<IpPrefix> prefixes) {
+        for (IpServer downstream : mDownstreams) {
+            final IpPrefix target = getDownstreamPrefix(downstream);
+            if (target == null) continue;
+
+            for (IpPrefix source : prefixes) {
+                if (isConflictPrefix(source, target)) {
+                    downstream.sendMessage(IpServer.CMD_NOTIFY_PREFIX_CONFLICT);
+                    break;
+                }
+            }
+        }
+    }
+
+    /** Remove IpPrefix records corresponding to input network. */
+    public void removeUpstreamPrefix(final Network network) {
+        mUpstreamPrefixMap.remove(network);
+    }
+
+    private void maybeRemoveDeprectedUpstreams() {
+        if (!mDownstreams.isEmpty() || mUpstreamPrefixMap.isEmpty()) return;
+
+        final ArrayList<Network> toBeRemoved = new ArrayList<>();
+        List<Network> allNetworks = Arrays.asList(mConnectivityMgr.getAllNetworks());
+        for (int i = 0; i < mUpstreamPrefixMap.size(); i++) {
+            final Network network = mUpstreamPrefixMap.keyAt(i);
+            if (!allNetworks.contains(network)) toBeRemoved.add(network);
+        }
+
+        mUpstreamPrefixMap.removeAll(toBeRemoved);
+    }
+
+    /**
+     * Pick a random available address and mark its prefix as in use for the provided IpServer,
+     * returns null if there is no available address.
+     */
+    @Nullable
+    public LinkAddress requestDownstreamAddress(final IpServer ipServer) {
+        maybeRemoveDeprectedUpstreams();
+
+        // Address would be 192.168.[subAddress]/24.
+        final byte[] bytes = mTetheringPrefix.getRawAddress();
+        final int subAddress = getRandomSubAddr();
+        final int subNet = (subAddress >> 8) & BYTE_MASK;
+        bytes[3] = getSanitizedAddressSuffix(subAddress, (byte) 0, (byte) 1, (byte) 0xff);
+        for (int i = 0; i < MAX_UBYTE; i++) {
+            final int newSubNet = (subNet + i) & BYTE_MASK;
+            if (newSubNet == BLUETOOTH_RESERVED) continue;
+
+            bytes[2] = (byte) newSubNet;
+            final InetAddress addr;
+            try {
+                addr = InetAddress.getByAddress(bytes);
+            } catch (UnknownHostException e) {
+                throw new IllegalStateException("Invalid address, shouldn't happen.", e);
+            }
+
+            final IpPrefix prefix = new IpPrefix(addr, PREFIX_LENGTH);
+            // Check whether this prefix is in use.
+            if (isDownstreamPrefixInUse(prefix)) continue;
+            // Check whether this prefix is conflict with any current upstream network.
+            if (isConflictWithUpstream(prefix)) continue;
+
+            mDownstreams.add(ipServer);
+            return new LinkAddress(addr, PREFIX_LENGTH);
+        }
+
+        // No available address.
+        return null;
+    }
+
+    /** Get random sub address value. Return value is in 0 ~ 0xffff. */
+    @VisibleForTesting
+    public int getRandomSubAddr() {
+        return ((new Random()).nextInt()) & 0xffff; // subNet is in 0 ~ 0xffff.
+    }
+
+    private byte getSanitizedAddressSuffix(final int source, byte... excluded) {
+        final byte subId = (byte) (source & BYTE_MASK);
+        for (byte value : excluded) {
+            if (subId == value) return DEFAULT_ID;
+        }
+
+        return subId;
+    }
+
+    /** Release downstream record for IpServer. */
+    public void releaseDownstream(final IpServer ipServer) {
+        mDownstreams.remove(ipServer);
+    }
+
+    /** Clear current upstream prefixes records. */
+    public void clearUpstreamPrefixes() {
+        mUpstreamPrefixMap.clear();
+    }
+
+    private boolean isConflictWithUpstream(final IpPrefix source) {
+        for (int i = 0; i < mUpstreamPrefixMap.size(); i++) {
+            final List<IpPrefix> list = mUpstreamPrefixMap.valueAt(i);
+            for (IpPrefix target : list) {
+                if (isConflictPrefix(source, target)) return true;
+            }
+        }
+        return false;
+    }
+
+    private boolean isConflictPrefix(final IpPrefix prefix1, final IpPrefix prefix2) {
+        if (prefix2.getPrefixLength() < prefix1.getPrefixLength()) {
+            return prefix2.contains(prefix1.getAddress());
+        }
+
+        return prefix1.contains(prefix2.getAddress());
+    }
+
+    private boolean isDownstreamPrefixInUse(final IpPrefix source) {
+        // This class always generates downstream prefixes with the same prefix length, so
+        // prefixes cannot be contained in each other. They can only be equal to each other.
+        for (IpServer downstream : mDownstreams) {
+            final IpPrefix prefix = getDownstreamPrefix(downstream);
+            if (source.equals(prefix)) return true;
+        }
+        return false;
+    }
+
+    private IpPrefix getDownstreamPrefix(final IpServer downstream) {
+        final LinkAddress address = downstream.getAddress();
+        if (address == null) return null;
+
+        return PrefixUtils.asIpPrefix(address);
+    }
+
+    void dump(final IndentingPrintWriter pw) {
+        pw.decreaseIndent();
+        pw.println("mUpstreamPrefixMap:");
+        pw.increaseIndent();
+        for (int i = 0; i < mUpstreamPrefixMap.size(); i++) {
+            pw.println(mUpstreamPrefixMap.keyAt(i) + " - " + mUpstreamPrefixMap.valueAt(i));
+        }
+        pw.decreaseIndent();
+        pw.println("mDownstreams:");
+        pw.increaseIndent();
+        for (IpServer ipServer : mDownstreams) {
+            pw.println(ipServer.interfaceType() + " - " + ipServer.getAddress());
+        }
+        pw.decreaseIndent();
+    }
+}
diff --git a/Tethering/src/com/android/networkstack/tethering/Tethering.java b/Tethering/src/com/android/networkstack/tethering/Tethering.java
index 04ad43f..69eec8d 100644
--- a/Tethering/src/com/android/networkstack/tethering/Tethering.java
+++ b/Tethering/src/com/android/networkstack/tethering/Tethering.java
@@ -207,6 +207,7 @@
             new SparseArray<>();
 
     // used to synchronize public access to members
+    // TODO(b/153621704): remove mPublicSync to make Tethering lock free
     private final Object mPublicSync;
     private final Context mContext;
     private final ArrayMap<String, TetherState> mTetherStates;
@@ -231,6 +232,7 @@
     private final TetheringThreadExecutor mExecutor;
     private final TetheringNotificationUpdater mNotificationUpdater;
     private final UserManager mUserManager;
+    private final PrivateAddressCoordinator mPrivateAddressCoordinator;
     private int mActiveDataSubId = INVALID_SUBSCRIPTION_ID;
     // All the usage of mTetheringEventCallback should run in the same thread.
     private ITetheringEventCallback mTetheringEventCallback = null;
@@ -314,6 +316,7 @@
         mExecutor = new TetheringThreadExecutor(mHandler);
         mActiveDataSubIdListener = new ActiveDataSubIdListener(mExecutor);
         mNetdCallback = new NetdCallback();
+        mPrivateAddressCoordinator = new PrivateAddressCoordinator(mContext);
 
         // Load tethering configuration.
         updateConfiguration();
@@ -1616,6 +1619,14 @@
             }
         }
 
+        private void addUpstreamPrefixes(final UpstreamNetworkState ns) {
+            mPrivateAddressCoordinator.updateUpstreamPrefix(ns.network, ns.linkProperties);
+        }
+
+        private void removeUpstreamPrefixes(final UpstreamNetworkState ns) {
+            mPrivateAddressCoordinator.removeUpstreamPrefix(ns.network);
+        }
+
         @VisibleForTesting
         void handleUpstreamNetworkMonitorCallback(int arg1, Object o) {
             if (arg1 == UpstreamNetworkMonitor.NOTIFY_LOCAL_PREFIXES) {
@@ -1624,6 +1635,14 @@
             }
 
             final UpstreamNetworkState ns = (UpstreamNetworkState) o;
+            switch (arg1) {
+                case UpstreamNetworkMonitor.EVENT_ON_LINKPROPERTIES:
+                    addUpstreamPrefixes(ns);
+                    break;
+                case UpstreamNetworkMonitor.EVENT_ON_LOST:
+                    removeUpstreamPrefixes(ns);
+                    break;
+            }
 
             if (ns == null || !pertainsToCurrentUpstream(ns)) {
                 // TODO: In future, this is where upstream evaluation and selection
@@ -2190,6 +2209,11 @@
         mOffloadController.dump(pw);
         pw.decreaseIndent();
 
+        pw.println("Private address coordinator:");
+        pw.increaseIndent();
+        mPrivateAddressCoordinator.dump(pw);
+        pw.decreaseIndent();
+
         pw.println("Log:");
         pw.increaseIndent();
         if (argsContain(args, "--short")) {
@@ -2231,6 +2255,11 @@
             public void dhcpLeasesChanged() {
                 updateConnectedClients(null /* wifiClients */);
             }
+
+            @Override
+            public void requestEnableTethering(int tetheringType, boolean enabled) {
+                enableTetheringInternal(tetheringType, enabled, null);
+            }
         };
     }
 
@@ -2314,7 +2343,8 @@
         final TetherState tetherState = new TetherState(
                 new IpServer(iface, mLooper, interfaceType, mLog, mNetd,
                              makeControlCallback(), mConfig.enableLegacyDhcpServer,
-                             mConfig.enableBpfOffload, mDeps.getIpServerDependencies()));
+                             mConfig.enableBpfOffload, mPrivateAddressCoordinator,
+                             mDeps.getIpServerDependencies()));
         mTetherStates.put(iface, tetherState);
         tetherState.ipServer.start();
     }
diff --git a/Tethering/tests/unit/src/android/net/ip/IpServerTest.java b/Tethering/tests/unit/src/android/net/ip/IpServerTest.java
index 307ebf1..0cda29a 100644
--- a/Tethering/tests/unit/src/android/net/ip/IpServerTest.java
+++ b/Tethering/tests/unit/src/android/net/ip/IpServerTest.java
@@ -78,6 +78,7 @@
 import android.net.ip.RouterAdvertisementDaemon.RaParams;
 import android.net.util.InterfaceParams;
 import android.net.util.InterfaceSet;
+import android.net.util.PrefixUtils;
 import android.net.util.SharedLog;
 import android.os.RemoteException;
 import android.os.test.TestLooper;
@@ -86,6 +87,8 @@
 import androidx.test.filters.SmallTest;
 import androidx.test.runner.AndroidJUnit4;
 
+import com.android.networkstack.tethering.PrivateAddressCoordinator;
+
 import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -109,7 +112,7 @@
     private static final String UPSTREAM_IFACE2 = "upstream1";
     private static final int UPSTREAM_IFINDEX = 101;
     private static final int UPSTREAM_IFINDEX2 = 102;
-    private static final String BLUETOOTH_IFACE_ADDR = "192.168.42.1";
+    private static final String BLUETOOTH_IFACE_ADDR = "192.168.44.1";
     private static final int BLUETOOTH_DHCP_PREFIX_LENGTH = 24;
     private static final int DHCP_LEASE_TIME_SECS = 3600;
     private static final boolean DEFAULT_USING_BPF_OFFLOAD = true;
@@ -119,6 +122,9 @@
 
     private static final int MAKE_DHCPSERVER_TIMEOUT_MS = 1000;
 
+    private final LinkAddress mTestAddress = new LinkAddress("192.168.42.5/24");
+    private final IpPrefix mBluetoothPrefix = new IpPrefix("192.168.44.0/24");
+
     @Mock private INetd mNetd;
     @Mock private IpServer.Callback mCallback;
     @Mock private SharedLog mSharedLog;
@@ -126,6 +132,7 @@
     @Mock private RouterAdvertisementDaemon mRaDaemon;
     @Mock private IpNeighborMonitor mIpNeighborMonitor;
     @Mock private IpServer.Dependencies mDependencies;
+    @Mock private PrivateAddressCoordinator mAddressCoordinator;
 
     @Captor private ArgumentCaptor<DhcpServingParamsParcel> mDhcpParamsCaptor;
 
@@ -173,7 +180,7 @@
 
         mIpServer = new IpServer(
                 IFACE_NAME, mLooper.getLooper(), interfaceType, mSharedLog, mNetd,
-                mCallback, usingLegacyDhcp, usingBpfOffload, mDependencies);
+                mCallback, usingLegacyDhcp, usingBpfOffload, mAddressCoordinator, mDependencies);
         mIpServer.start();
         mNeighborEventConsumer = neighborCaptor.getValue();
 
@@ -200,12 +207,14 @@
             lp.setInterfaceName(upstreamIface);
             dispatchTetherConnectionChanged(upstreamIface, lp, 0);
         }
-        reset(mNetd, mCallback);
+        reset(mNetd, mCallback, mAddressCoordinator);
+        when(mAddressCoordinator.requestDownstreamAddress(any())).thenReturn(mTestAddress);
     }
 
     @Before public void setUp() throws Exception {
         MockitoAnnotations.initMocks(this);
         when(mSharedLog.forSubComponent(anyString())).thenReturn(mSharedLog);
+        when(mAddressCoordinator.requestDownstreamAddress(any())).thenReturn(mTestAddress);
     }
 
     @Test
@@ -214,7 +223,7 @@
                 .thenReturn(mIpNeighborMonitor);
         mIpServer = new IpServer(IFACE_NAME, mLooper.getLooper(), TETHERING_BLUETOOTH, mSharedLog,
                 mNetd, mCallback, false /* usingLegacyDhcp */, DEFAULT_USING_BPF_OFFLOAD,
-                mDependencies);
+                mAddressCoordinator, mDependencies);
         mIpServer.start();
         mLooper.dispatchAll();
         verify(mCallback).updateInterfaceState(
@@ -277,16 +286,17 @@
         initTetheredStateMachine(TETHERING_BLUETOOTH, null);
 
         dispatchCommand(IpServer.CMD_TETHER_UNREQUESTED);
-        InOrder inOrder = inOrder(mNetd, mCallback);
+        InOrder inOrder = inOrder(mCallback, mNetd, mAddressCoordinator);
         inOrder.verify(mNetd).tetherApplyDnsInterfaces();
         inOrder.verify(mNetd).tetherInterfaceRemove(IFACE_NAME);
         inOrder.verify(mNetd).networkRemoveInterface(INetd.LOCAL_NET_ID, IFACE_NAME);
         inOrder.verify(mNetd).interfaceSetCfg(argThat(cfg -> IFACE_NAME.equals(cfg.ifName)));
+        inOrder.verify(mAddressCoordinator).releaseDownstream(any());
         inOrder.verify(mCallback).updateInterfaceState(
                 mIpServer, STATE_AVAILABLE, TETHER_ERROR_NO_ERROR);
         inOrder.verify(mCallback).updateLinkProperties(
                 eq(mIpServer), any(LinkProperties.class));
-        verifyNoMoreInteractions(mNetd, mCallback);
+        verifyNoMoreInteractions(mNetd, mCallback, mAddressCoordinator);
     }
 
     @Test
@@ -294,7 +304,8 @@
         initStateMachine(TETHERING_USB);
 
         dispatchCommand(IpServer.CMD_TETHER_REQUESTED, STATE_TETHERED);
-        InOrder inOrder = inOrder(mCallback, mNetd);
+        InOrder inOrder = inOrder(mCallback, mNetd, mAddressCoordinator);
+        inOrder.verify(mAddressCoordinator).requestDownstreamAddress(any());
         inOrder.verify(mNetd).interfaceSetCfg(argThat(cfg ->
                   IFACE_NAME.equals(cfg.ifName) && assertContainsFlag(cfg.flags, IF_STATE_UP)));
         inOrder.verify(mNetd).tetherInterfaceAdd(IFACE_NAME);
@@ -306,7 +317,7 @@
         inOrder.verify(mCallback).updateLinkProperties(
                 eq(mIpServer), mLinkPropertiesCaptor.capture());
         assertIPv4AddressAndDirectlyConnectedRoute(mLinkPropertiesCaptor.getValue());
-        verifyNoMoreInteractions(mNetd, mCallback);
+        verifyNoMoreInteractions(mNetd, mCallback, mAddressCoordinator);
     }
 
     @Test
@@ -314,7 +325,8 @@
         initStateMachine(TETHERING_WIFI_P2P);
 
         dispatchCommand(IpServer.CMD_TETHER_REQUESTED, STATE_LOCAL_ONLY);
-        InOrder inOrder = inOrder(mCallback, mNetd);
+        InOrder inOrder = inOrder(mCallback, mNetd, mAddressCoordinator);
+        inOrder.verify(mAddressCoordinator).requestDownstreamAddress(any());
         inOrder.verify(mNetd).interfaceSetCfg(argThat(cfg ->
                   IFACE_NAME.equals(cfg.ifName) && assertNotContainsFlag(cfg.flags, IF_STATE_UP)));
         inOrder.verify(mNetd).tetherInterfaceAdd(IFACE_NAME);
@@ -326,7 +338,7 @@
         inOrder.verify(mCallback).updateLinkProperties(
                 eq(mIpServer), mLinkPropertiesCaptor.capture());
         assertIPv4AddressAndDirectlyConnectedRoute(mLinkPropertiesCaptor.getValue());
-        verifyNoMoreInteractions(mNetd, mCallback);
+        verifyNoMoreInteractions(mNetd, mCallback, mAddressCoordinator);
     }
 
     @Test
@@ -392,18 +404,19 @@
         initTetheredStateMachine(TETHERING_BLUETOOTH, UPSTREAM_IFACE);
 
         dispatchCommand(IpServer.CMD_TETHER_UNREQUESTED);
-        InOrder inOrder = inOrder(mNetd, mCallback);
+        InOrder inOrder = inOrder(mNetd, mCallback, mAddressCoordinator);
         inOrder.verify(mNetd).ipfwdRemoveInterfaceForward(IFACE_NAME, UPSTREAM_IFACE);
         inOrder.verify(mNetd).tetherRemoveForward(IFACE_NAME, UPSTREAM_IFACE);
         inOrder.verify(mNetd).tetherApplyDnsInterfaces();
         inOrder.verify(mNetd).tetherInterfaceRemove(IFACE_NAME);
         inOrder.verify(mNetd).networkRemoveInterface(INetd.LOCAL_NET_ID, IFACE_NAME);
         inOrder.verify(mNetd).interfaceSetCfg(argThat(cfg -> IFACE_NAME.equals(cfg.ifName)));
+        inOrder.verify(mAddressCoordinator).releaseDownstream(any());
         inOrder.verify(mCallback).updateInterfaceState(
                 mIpServer, STATE_AVAILABLE, TETHER_ERROR_NO_ERROR);
         inOrder.verify(mCallback).updateLinkProperties(
                 eq(mIpServer), any(LinkProperties.class));
-        verifyNoMoreInteractions(mNetd, mCallback);
+        verifyNoMoreInteractions(mNetd, mCallback, mAddressCoordinator);
     }
 
     @Test
@@ -483,7 +496,7 @@
         initTetheredStateMachine(TETHERING_WIFI, UPSTREAM_IFACE);
         dispatchTetherConnectionChanged(UPSTREAM_IFACE);
 
-        assertDhcpStarted(new IpPrefix("192.168.43.0/24"));
+        assertDhcpStarted(PrefixUtils.asIpPrefix(mTestAddress));
     }
 
     @Test
@@ -491,7 +504,7 @@
         initTetheredStateMachine(TETHERING_BLUETOOTH, UPSTREAM_IFACE);
         dispatchTetherConnectionChanged(UPSTREAM_IFACE);
 
-        assertDhcpStarted(new IpPrefix("192.168.44.0/24"));
+        assertDhcpStarted(mBluetoothPrefix);
     }
 
     @Test
@@ -499,7 +512,7 @@
         initTetheredStateMachine(TETHERING_WIFI_P2P, UPSTREAM_IFACE);
         dispatchTetherConnectionChanged(UPSTREAM_IFACE);
 
-        assertDhcpStarted(new IpPrefix("192.168.49.0/24"));
+        assertDhcpStarted(PrefixUtils.asIpPrefix(mTestAddress));
     }
 
     @Test
@@ -524,21 +537,27 @@
         eventCallbacks = dhcpEventCbsCaptor.getValue();
         assertDhcpStarted(new IpPrefix("192.168.42.0/24"));
 
-        // Simulate the DHCP server receives DHCPDECLINE on MirrorLink and then signals
-        // onNewPrefixRequest callback.
-        eventCallbacks.onNewPrefixRequest(new IpPrefix("192.168.42.0/24"));
-        mLooper.dispatchAll();
-
         final ArgumentCaptor<LinkProperties> lpCaptor =
                 ArgumentCaptor.forClass(LinkProperties.class);
-        InOrder inOrder = inOrder(mNetd, mCallback);
-        inOrder.verify(mCallback).updateInterfaceState(
-                mIpServer, STATE_LOCAL_ONLY, TETHER_ERROR_NO_ERROR);
-        inOrder.verify(mCallback).updateLinkProperties(eq(mIpServer), lpCaptor.capture());
+        InOrder inOrder = inOrder(mNetd, mCallback, mAddressCoordinator);
+        inOrder.verify(mAddressCoordinator).requestDownstreamAddress(any());
         inOrder.verify(mNetd).networkAddInterface(INetd.LOCAL_NET_ID, IFACE_NAME);
         // One for ipv4 route, one for ipv6 link local route.
         inOrder.verify(mNetd, times(2)).networkAddRoute(eq(INetd.LOCAL_NET_ID), eq(IFACE_NAME),
                 any(), any());
+        inOrder.verify(mCallback).updateInterfaceState(
+                mIpServer, STATE_LOCAL_ONLY, TETHER_ERROR_NO_ERROR);
+        inOrder.verify(mCallback).updateLinkProperties(eq(mIpServer), lpCaptor.capture());
+        verifyNoMoreInteractions(mCallback, mAddressCoordinator);
+
+        // Simulate the DHCP server receives DHCPDECLINE on MirrorLink and then signals
+        // onNewPrefixRequest callback.
+        final LinkAddress newAddress = new LinkAddress("192.168.100.125/24");
+        when(mAddressCoordinator.requestDownstreamAddress(any())).thenReturn(newAddress);
+        eventCallbacks.onNewPrefixRequest(new IpPrefix("192.168.42.0/24"));
+        mLooper.dispatchAll();
+
+        inOrder.verify(mAddressCoordinator).requestDownstreamAddress(any());
         inOrder.verify(mNetd).tetherApplyDnsInterfaces();
         inOrder.verify(mCallback).updateLinkProperties(eq(mIpServer), lpCaptor.capture());
         verifyNoMoreInteractions(mCallback);
diff --git a/Tethering/tests/unit/src/com/android/networkstack/tethering/PrivateAddressCoordinatorTest.java b/Tethering/tests/unit/src/com/android/networkstack/tethering/PrivateAddressCoordinatorTest.java
new file mode 100644
index 0000000..93efd49
--- /dev/null
+++ b/Tethering/tests/unit/src/com/android/networkstack/tethering/PrivateAddressCoordinatorTest.java
@@ -0,0 +1,254 @@
+/*
+ * 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 com.android.networkstack.tethering;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
+import static org.mockito.Mockito.never;
+import static org.mockito.Mockito.reset;
+import static org.mockito.Mockito.spy;
+import static org.mockito.Mockito.verify;
+import static org.mockito.Mockito.when;
+
+import android.content.Context;
+import android.net.ConnectivityManager;
+import android.net.InetAddresses;
+import android.net.IpPrefix;
+import android.net.LinkAddress;
+import android.net.LinkProperties;
+import android.net.Network;
+import android.net.ip.IpServer;
+import android.net.util.NetworkConstants;
+import android.net.util.PrefixUtils;
+
+import androidx.test.filters.SmallTest;
+import androidx.test.runner.AndroidJUnit4;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.Mock;
+import org.mockito.MockitoAnnotations;
+
+import java.util.List;
+
+@RunWith(AndroidJUnit4.class)
+@SmallTest
+public final class PrivateAddressCoordinatorTest {
+    private static final String TEST_MOBILE_IFNAME = "test_rmnet_data0";
+    private static final String TEST_WIFI_IFNAME = "test_wlan0";
+
+    @Mock private IpServer mHotspotIpServer;
+    @Mock private IpServer mUsbIpServer;
+    @Mock private IpServer mEthernetIpServer;
+    @Mock private Context mContext;
+    @Mock private ConnectivityManager mConnectivityMgr;
+
+    private PrivateAddressCoordinator mPrivateAddressCoordinator;
+    private final IpPrefix mBluetoothPrefix = new IpPrefix("192.168.44.0/24");
+    private final Network mWifiNetwork = new Network(1);
+    private final Network mMobileNetwork = new Network(2);
+    private final Network[] mAllNetworks = {mMobileNetwork, mWifiNetwork};
+
+    @Before
+    public void setUp() throws Exception {
+        MockitoAnnotations.initMocks(this);
+
+        when(mContext.getSystemService(Context.CONNECTIVITY_SERVICE)).thenReturn(mConnectivityMgr);
+        when(mConnectivityMgr.getAllNetworks()).thenReturn(mAllNetworks);
+        mPrivateAddressCoordinator = spy(new PrivateAddressCoordinator(mContext));
+    }
+
+    @Test
+    public void testDownstreamPrefixRequest() throws Exception {
+        LinkAddress address = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mHotspotIpServer);
+        final IpPrefix hotspotPrefix = PrefixUtils.asIpPrefix(address);
+        assertNotEquals(hotspotPrefix, mBluetoothPrefix);
+
+        address = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mHotspotIpServer);
+        final IpPrefix testDupRequest = PrefixUtils.asIpPrefix(address);
+        assertNotEquals(hotspotPrefix, testDupRequest);
+        assertNotEquals(mBluetoothPrefix, testDupRequest);
+        mPrivateAddressCoordinator.releaseDownstream(mHotspotIpServer);
+
+        address = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mUsbIpServer);
+        final IpPrefix usbPrefix = PrefixUtils.asIpPrefix(address);
+        assertNotEquals(usbPrefix, mBluetoothPrefix);
+        assertNotEquals(usbPrefix, hotspotPrefix);
+        mPrivateAddressCoordinator.releaseDownstream(mUsbIpServer);
+    }
+
+    @Test
+    public void testRequestDownstreamAddress() throws Exception {
+        LinkAddress expectedAddress = new LinkAddress("192.168.43.42/24");
+        int fakeSubAddr = 0x2b00;
+        when(mPrivateAddressCoordinator.getRandomSubAddr()).thenReturn(fakeSubAddr);
+        LinkAddress actualAddress = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mHotspotIpServer);
+        assertEquals(actualAddress, expectedAddress);
+        mPrivateAddressCoordinator.releaseDownstream(mHotspotIpServer);
+
+        fakeSubAddr = 0x2b01;
+        when(mPrivateAddressCoordinator.getRandomSubAddr()).thenReturn(fakeSubAddr);
+        actualAddress = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mHotspotIpServer);
+        assertEquals(actualAddress, expectedAddress);
+        mPrivateAddressCoordinator.releaseDownstream(mHotspotIpServer);
+
+        fakeSubAddr = 0x2bff;
+        when(mPrivateAddressCoordinator.getRandomSubAddr()).thenReturn(fakeSubAddr);
+        actualAddress = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mHotspotIpServer);
+        assertEquals(actualAddress, expectedAddress);
+        mPrivateAddressCoordinator.releaseDownstream(mHotspotIpServer);
+
+        expectedAddress = new LinkAddress("192.168.43.5/24");
+        fakeSubAddr = 0x2b05;
+        when(mPrivateAddressCoordinator.getRandomSubAddr()).thenReturn(fakeSubAddr);
+        actualAddress = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mHotspotIpServer);
+        assertEquals(actualAddress, expectedAddress);
+        mPrivateAddressCoordinator.releaseDownstream(mHotspotIpServer);
+    }
+
+    @Test
+    public void testReserveBluetoothPrefix() throws Exception {
+        final int fakeSubAddr = 0x2c05;
+        when(mPrivateAddressCoordinator.getRandomSubAddr()).thenReturn(fakeSubAddr);
+        LinkAddress address = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mHotspotIpServer);
+        final IpPrefix hotspotPrefix = PrefixUtils.asIpPrefix(address);
+        assertNotEquals("Should not get reserved prefix: ", mBluetoothPrefix, hotspotPrefix);
+        mPrivateAddressCoordinator.releaseDownstream(mHotspotIpServer);
+    }
+
+    @Test
+    public void testNoConflictDownstreamPrefix() throws Exception {
+        final int fakeHotspotSubAddr = 0x2b05;
+        final IpPrefix predefinedPrefix = new IpPrefix("192.168.43.0/24");
+        when(mPrivateAddressCoordinator.getRandomSubAddr()).thenReturn(fakeHotspotSubAddr);
+        LinkAddress address = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mHotspotIpServer);
+        final IpPrefix hotspotPrefix = PrefixUtils.asIpPrefix(address);
+        assertEquals("Wrong wifi perfix: ", predefinedPrefix, hotspotPrefix);
+        when(mHotspotIpServer.getAddress()).thenReturn(address);
+
+        address = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mUsbIpServer);
+        final IpPrefix usbPrefix = PrefixUtils.asIpPrefix(address);
+        assertNotEquals(predefinedPrefix, usbPrefix);
+
+        mPrivateAddressCoordinator.releaseDownstream(mHotspotIpServer);
+        mPrivateAddressCoordinator.releaseDownstream(mUsbIpServer);
+        address = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mUsbIpServer);
+        final IpPrefix allowUseFreePrefix = PrefixUtils.asIpPrefix(address);
+        assertEquals("Fail to reselect available perfix: ", predefinedPrefix, allowUseFreePrefix);
+    }
+
+    private LinkProperties buildUpstreamLinkProperties(boolean withIPv4, boolean withIPv6,
+            boolean isMobile) {
+        final String testIface;
+        final String testIpv4Address;
+        if (isMobile) {
+            testIface = TEST_MOBILE_IFNAME;
+            testIpv4Address = "10.0.0.1";
+        } else {
+            testIface = TEST_WIFI_IFNAME;
+            testIpv4Address = "192.168.43.5";
+        }
+
+        final LinkProperties prop = new LinkProperties();
+        prop.setInterfaceName(testIface);
+
+        if (withIPv4) {
+            prop.addLinkAddress(
+                    new LinkAddress(InetAddresses.parseNumericAddress(testIpv4Address),
+                            NetworkConstants.IPV4_ADDR_BITS));
+        }
+
+        if (withIPv6) {
+            prop.addLinkAddress(
+                    new LinkAddress(InetAddresses.parseNumericAddress("2001:db8::"),
+                            NetworkConstants.RFC7421_PREFIX_LENGTH));
+        }
+        return prop;
+    }
+
+    @Test
+    public void testNoConflictUpstreamPrefix() throws Exception {
+        final int fakeHotspotSubId = 43;
+        final int fakeHotspotSubAddr = 0x2b05;
+        final IpPrefix predefinedPrefix = new IpPrefix("192.168.43.0/24");
+        // Force always get subAddress "43.5" for conflict testing.
+        when(mPrivateAddressCoordinator.getRandomSubAddr()).thenReturn(fakeHotspotSubAddr);
+        // 1. Enable hotspot with prefix 192.168.43.0/24
+        final LinkAddress hotspotAddr = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mHotspotIpServer);
+        final IpPrefix hotspotPrefix = PrefixUtils.asIpPrefix(hotspotAddr);
+        assertEquals("Wrong wifi perfix: ", predefinedPrefix, hotspotPrefix);
+        when(mHotspotIpServer.getAddress()).thenReturn(hotspotAddr);
+        // 2. Update v6 only mobile network, hotspot prefix should not be removed.
+        List<String> testConflicts;
+        final LinkProperties v6OnlyMobileProp = buildUpstreamLinkProperties(false, true, true);
+        mPrivateAddressCoordinator.updateUpstreamPrefix(mMobileNetwork, v6OnlyMobileProp);
+        verify(mHotspotIpServer, never()).sendMessage(IpServer.CMD_NOTIFY_PREFIX_CONFLICT);
+        mPrivateAddressCoordinator.removeUpstreamPrefix(mMobileNetwork);
+        // 3. Update v4 only mobile network, hotspot prefix should not be removed.
+        final LinkProperties v4OnlyMobileProp = buildUpstreamLinkProperties(true, false, true);
+        mPrivateAddressCoordinator.updateUpstreamPrefix(mMobileNetwork, v4OnlyMobileProp);
+        verify(mHotspotIpServer, never()).sendMessage(IpServer.CMD_NOTIFY_PREFIX_CONFLICT);
+        // 4. Update v4v6 mobile network, hotspot prefix should not be removed.
+        final LinkProperties v4v6MobileProp = buildUpstreamLinkProperties(true, true, true);
+        mPrivateAddressCoordinator.updateUpstreamPrefix(mMobileNetwork, v4v6MobileProp);
+        verify(mHotspotIpServer, never()).sendMessage(IpServer.CMD_NOTIFY_PREFIX_CONFLICT);
+        // 5. Update v6 only wifi network, hotspot prefix should not be removed.
+        final LinkProperties v6OnlyWifiProp = buildUpstreamLinkProperties(false, true, false);
+        mPrivateAddressCoordinator.updateUpstreamPrefix(mWifiNetwork, v6OnlyWifiProp);
+        verify(mHotspotIpServer, never()).sendMessage(IpServer.CMD_NOTIFY_PREFIX_CONFLICT);
+        mPrivateAddressCoordinator.removeUpstreamPrefix(mWifiNetwork);
+        // 6. Update v4 only wifi network, it conflict with hotspot prefix.
+        final LinkProperties v4OnlyWifiProp = buildUpstreamLinkProperties(true, false, false);
+        mPrivateAddressCoordinator.updateUpstreamPrefix(mWifiNetwork, v4OnlyWifiProp);
+        verify(mHotspotIpServer).sendMessage(IpServer.CMD_NOTIFY_PREFIX_CONFLICT);
+        reset(mHotspotIpServer);
+        // 7. Restart hotspot again and its prefix is different previous.
+        mPrivateAddressCoordinator.releaseDownstream(mHotspotIpServer);
+        final LinkAddress hotspotAddr2 = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mHotspotIpServer);
+        final IpPrefix hotspotPrefix2 = PrefixUtils.asIpPrefix(hotspotAddr2);
+        assertNotEquals(hotspotPrefix, hotspotPrefix2);
+        when(mHotspotIpServer.getAddress()).thenReturn(hotspotAddr2);
+        mPrivateAddressCoordinator.updateUpstreamPrefix(mWifiNetwork, v4OnlyWifiProp);
+        verify(mHotspotIpServer, never()).sendMessage(IpServer.CMD_NOTIFY_PREFIX_CONFLICT);
+        // 7. Usb tethering can be enabled and its prefix is different with conflict one.
+        final LinkAddress usbAddr = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mUsbIpServer);
+        final IpPrefix usbPrefix = PrefixUtils.asIpPrefix(usbAddr);
+        assertNotEquals(predefinedPrefix, usbPrefix);
+        assertNotEquals(hotspotPrefix2, usbPrefix);
+        when(mUsbIpServer.getAddress()).thenReturn(usbAddr);
+        // 8. Disable wifi upstream, then wifi's prefix can be selected again.
+        mPrivateAddressCoordinator.removeUpstreamPrefix(mWifiNetwork);
+        final LinkAddress ethAddr = mPrivateAddressCoordinator.requestDownstreamAddress(
+                mEthernetIpServer);
+        final IpPrefix ethPrefix = PrefixUtils.asIpPrefix(ethAddr);
+        assertEquals(predefinedPrefix, ethPrefix);
+    }
+}
diff --git a/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java b/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java
index 0132aba..bb65b18 100644
--- a/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java
+++ b/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java
@@ -32,6 +32,7 @@
 import static android.net.TetheringManager.TETHERING_NCM;
 import static android.net.TetheringManager.TETHERING_USB;
 import static android.net.TetheringManager.TETHERING_WIFI;
+import static android.net.TetheringManager.TETHER_ERROR_IFACE_CFG_ERROR;
 import static android.net.TetheringManager.TETHER_ERROR_NO_ERROR;
 import static android.net.TetheringManager.TETHER_ERROR_UNKNOWN_IFACE;
 import static android.net.TetheringManager.TETHER_HARDWARE_OFFLOAD_FAILED;
@@ -84,6 +85,7 @@
 import android.hardware.usb.UsbManager;
 import android.net.ConnectivityManager;
 import android.net.EthernetManager;
+import android.net.EthernetManager.TetheredInterfaceCallback;
 import android.net.EthernetManager.TetheredInterfaceRequest;
 import android.net.IIntResultListener;
 import android.net.INetd;
@@ -169,9 +171,11 @@
     private static final String TEST_MOBILE_IFNAME = "test_rmnet_data0";
     private static final String TEST_XLAT_MOBILE_IFNAME = "v4-test_rmnet_data0";
     private static final String TEST_USB_IFNAME = "test_rndis0";
-    private static final String TEST_WLAN_IFNAME = "test_wlan0";
+    private static final String TEST_WIFI_IFNAME = "test_wlan0";
+    private static final String TEST_WLAN_IFNAME = "test_wlan1";
     private static final String TEST_P2P_IFNAME = "test_p2p-p2p0-0";
     private static final String TEST_NCM_IFNAME = "test_ncm0";
+    private static final String TEST_ETH_IFNAME = "test_eth0";
     private static final String TETHERING_NAME = "Tethering";
     private static final String[] PROVISIONING_APP_NAME = {"some", "app"};
     private static final String PROVISIONING_NO_UI_APP_NAME = "no_ui_app";
@@ -279,10 +283,11 @@
                             || ifName.equals(TEST_WLAN_IFNAME)
                             || ifName.equals(TEST_MOBILE_IFNAME)
                             || ifName.equals(TEST_P2P_IFNAME)
-                            || ifName.equals(TEST_NCM_IFNAME));
+                            || ifName.equals(TEST_NCM_IFNAME)
+                            || ifName.equals(TEST_ETH_IFNAME));
             final String[] ifaces = new String[] {
                     TEST_USB_IFNAME, TEST_WLAN_IFNAME, TEST_MOBILE_IFNAME, TEST_P2P_IFNAME,
-                    TEST_NCM_IFNAME};
+                    TEST_NCM_IFNAME, TEST_ETH_IFNAME};
             return new InterfaceParams(ifName, ArrayUtils.indexOf(ifaces, ifName) + IFINDEX_OFFSET,
                     MacAddress.ALL_ZEROS_ADDRESS);
         }
@@ -490,7 +495,7 @@
         when(mNetd.interfaceGetList())
                 .thenReturn(new String[] {
                         TEST_MOBILE_IFNAME, TEST_WLAN_IFNAME, TEST_USB_IFNAME, TEST_P2P_IFNAME,
-                        TEST_NCM_IFNAME});
+                        TEST_NCM_IFNAME, TEST_ETH_IFNAME});
         when(mResources.getString(R.string.config_wifi_tether_enable)).thenReturn("");
         mInterfaceConfiguration = new InterfaceConfigurationParcel();
         mInterfaceConfiguration.flags = new String[0];
@@ -1836,6 +1841,109 @@
         mCarrierConfig.putBoolean(CarrierConfigManager.KEY_CARRIER_CONFIG_APPLIED_BOOL, true);
         sendConfigurationChanged();
     }
+
+    private static UpstreamNetworkState buildV4WifiUpstreamState(final String ipv4Address,
+            final int prefixLength, final Network network) {
+        final LinkProperties prop = new LinkProperties();
+        prop.setInterfaceName(TEST_WIFI_IFNAME);
+
+        prop.addLinkAddress(
+                new LinkAddress(InetAddresses.parseNumericAddress(ipv4Address),
+                        prefixLength));
+
+        final NetworkCapabilities capabilities = new NetworkCapabilities()
+                .addTransportType(NetworkCapabilities.TRANSPORT_WIFI);
+        return new UpstreamNetworkState(prop, capabilities, network);
+    }
+
+    @Test
+    public void testHandleIpConflict() throws Exception {
+        final Network wifiNetwork = new Network(200);
+        final Network[] allNetworks = { wifiNetwork };
+        when(mCm.getAllNetworks()).thenReturn(allNetworks);
+        UpstreamNetworkState upstreamNetwork = null;
+        runUsbTethering(upstreamNetwork);
+        final ArgumentCaptor<InterfaceConfigurationParcel> ifaceConfigCaptor =
+                ArgumentCaptor.forClass(InterfaceConfigurationParcel.class);
+        verify(mNetd).interfaceSetCfg(ifaceConfigCaptor.capture());
+        final String ipv4Address = ifaceConfigCaptor.getValue().ipv4Addr;
+        verify(mDhcpServer, timeout(DHCPSERVER_START_TIMEOUT_MS).times(1)).startWithCallbacks(
+                any(), any());
+        reset(mNetd, mUsbManager);
+        upstreamNetwork = buildV4WifiUpstreamState(ipv4Address, 30, wifiNetwork);
+        mTetheringDependencies.mUpstreamNetworkMonitorMasterSM.sendMessage(
+                Tethering.TetherMasterSM.EVENT_UPSTREAM_CALLBACK,
+                UpstreamNetworkMonitor.EVENT_ON_LINKPROPERTIES,
+                0,
+                upstreamNetwork);
+        mLooper.dispatchAll();
+        // verify trun off usb tethering
+        verify(mUsbManager).setCurrentFunctions(UsbManager.FUNCTION_NONE);
+        mTethering.interfaceRemoved(TEST_USB_IFNAME);
+        mLooper.dispatchAll();
+        // verify restart usb tethering
+        verify(mUsbManager).setCurrentFunctions(UsbManager.FUNCTION_RNDIS);
+    }
+
+    @Test
+    public void testNoAddressAvailable() throws Exception {
+        final Network wifiNetwork = new Network(200);
+        final Network[] allNetworks = { wifiNetwork };
+        when(mCm.getAllNetworks()).thenReturn(allNetworks);
+        final String upstreamAddress = "192.168.0.100";
+        runUsbTethering(null);
+        verify(mDhcpServer, timeout(DHCPSERVER_START_TIMEOUT_MS).times(1)).startWithCallbacks(
+                any(), any());
+        reset(mUsbManager);
+        final TetheredInterfaceRequest mockRequest = mock(TetheredInterfaceRequest.class);
+        when(mEm.requestTetheredInterface(any(), any())).thenReturn(mockRequest);
+        final ArgumentCaptor<TetheredInterfaceCallback> callbackCaptor =
+                ArgumentCaptor.forClass(TetheredInterfaceCallback.class);
+        mTethering.startTethering(createTetheringRequestParcel(TETHERING_ETHERNET), null);
+        mLooper.dispatchAll();
+        verify(mEm).requestTetheredInterface(any(), callbackCaptor.capture());
+        TetheredInterfaceCallback ethCallback = callbackCaptor.getValue();
+        ethCallback.onAvailable(TEST_ETH_IFNAME);
+        mLooper.dispatchAll();
+        reset(mUsbManager, mEm);
+
+        final UpstreamNetworkState upstreamNetwork = buildV4WifiUpstreamState(
+                upstreamAddress, 16, wifiNetwork);
+        mTetheringDependencies.mUpstreamNetworkMonitorMasterSM.sendMessage(
+                Tethering.TetherMasterSM.EVENT_UPSTREAM_CALLBACK,
+                UpstreamNetworkMonitor.EVENT_ON_LINKPROPERTIES,
+                0,
+                upstreamNetwork);
+        mLooper.dispatchAll();
+        // verify trun off usb tethering
+        verify(mUsbManager).setCurrentFunctions(UsbManager.FUNCTION_NONE);
+        // verify trun off ethernet tethering
+        verify(mockRequest).release();
+        mTethering.interfaceRemoved(TEST_USB_IFNAME);
+        ethCallback.onUnavailable();
+        mLooper.dispatchAll();
+        // verify restart usb tethering
+        verify(mUsbManager).setCurrentFunctions(UsbManager.FUNCTION_RNDIS);
+        // verify restart ethernet tethering
+        verify(mEm).requestTetheredInterface(any(), callbackCaptor.capture());
+        ethCallback = callbackCaptor.getValue();
+        ethCallback.onAvailable(TEST_ETH_IFNAME);
+
+        reset(mUsbManager, mEm);
+        when(mNetd.interfaceGetList())
+                .thenReturn(new String[] {
+                        TEST_MOBILE_IFNAME, TEST_WLAN_IFNAME, TEST_USB_IFNAME, TEST_P2P_IFNAME,
+                        TEST_NCM_IFNAME, TEST_ETH_IFNAME});
+
+        mTethering.interfaceStatusChanged(TEST_USB_IFNAME, true);
+        sendUsbBroadcast(true, true, true, TETHERING_USB);
+        mLooper.dispatchAll();
+        assertContains(Arrays.asList(mTethering.getTetherableIfaces()), TEST_USB_IFNAME);
+        assertContains(Arrays.asList(mTethering.getTetherableIfaces()), TEST_ETH_IFNAME);
+        assertEquals(TETHER_ERROR_IFACE_CFG_ERROR, mTethering.getLastTetherError(TEST_USB_IFNAME));
+        assertEquals(TETHER_ERROR_IFACE_CFG_ERROR, mTethering.getLastTetherError(TEST_ETH_IFNAME));
+    }
+
     // TODO: Test that a request for hotspot mode doesn't interfere with an
     // already operating tethering mode interface.
 }