diff --git a/services/core/java/com/android/server/ConnectivityService.java b/services/core/java/com/android/server/ConnectivityService.java
index 1035efb..446d186 100644
--- a/services/core/java/com/android/server/ConnectivityService.java
+++ b/services/core/java/com/android/server/ConnectivityService.java
@@ -71,6 +71,8 @@
 import android.net.INetworkPolicyListener;
 import android.net.INetworkPolicyManager;
 import android.net.INetworkStatsService;
+import android.net.InetAddresses;
+import android.net.IpPrefix;
 import android.net.LinkProperties;
 import android.net.LinkProperties.CompareResult;
 import android.net.MatchAllNetworkSpecifier;
@@ -1740,6 +1742,12 @@
                 }
             }
         }
+
+        @Override
+        public void onNat64PrefixEvent(int netId, boolean added,
+                                       String prefixString, int prefixLength) {
+            mHandler.post(() -> handleNat64PrefixEvent(netId, added, prefixString, prefixLength));
+        }
     };
 
     @VisibleForTesting
@@ -2767,6 +2775,29 @@
         handleUpdateLinkProperties(nai, new LinkProperties(nai.linkProperties));
     }
 
+    private void handleNat64PrefixEvent(int netId, boolean added, String prefixString,
+            int prefixLength) {
+        NetworkAgentInfo nai = mNetworkForNetId.get(netId);
+        if (nai == null) return;
+
+        log(String.format("NAT64 prefix %s on netId %d: %s/%d",
+                          (added ? "added" : "removed"), netId, prefixString, prefixLength));
+
+        IpPrefix prefix = null;
+        if (added) {
+            try {
+                prefix = new IpPrefix(InetAddresses.parseNumericAddress(prefixString),
+                        prefixLength);
+            } catch (IllegalArgumentException e) {
+                loge("Invalid NAT64 prefix " + prefixString + "/" + prefixLength);
+                return;
+            }
+        }
+
+        nai.clatd.setNat64Prefix(prefix);
+        handleUpdateLinkProperties(nai, new LinkProperties(nai.linkProperties));
+    }
+
     private void updateLingerState(NetworkAgentInfo nai, long now) {
         // 1. Update the linger timer. If it's changed, reschedule or cancel the alarm.
         // 2. If the network was lingering and there are now requests, unlinger it.
@@ -2882,7 +2913,7 @@
             e.rethrowFromSystemServer();
         }
         mNetworkAgentInfos.remove(nai.messenger);
-        nai.maybeStopClat();
+        nai.clatd.update();
         synchronized (mNetworkForNetId) {
             // Remove the NetworkAgent, but don't mark the netId as
             // available until we've told netd to delete it below.
@@ -5190,11 +5221,10 @@
             LinkProperties oldLp) {
         int netId = networkAgent.network.netId;
 
-        // The NetworkAgentInfo does not know whether clatd is running on its network or not. Before
-        // we do anything else, make sure its LinkProperties are accurate.
-        if (networkAgent.clatd != null) {
-            networkAgent.clatd.fixupLinkProperties(oldLp, newLp);
-        }
+        // The NetworkAgentInfo does not know whether clatd is running on its network or not, or
+        // whether there is a NAT64 prefix. Before we do anything else, make sure its LinkProperties
+        // are accurate.
+        networkAgent.clatd.fixupLinkProperties(oldLp, newLp);
 
         updateInterfaces(newLp, oldLp, netId, networkAgent.networkCapabilities);
         updateMtu(newLp, oldLp);
@@ -5224,8 +5254,8 @@
             synchronized (networkAgent) {
                 networkAgent.linkProperties = newLp;
             }
-            // Start or stop clat accordingly to network state.
-            networkAgent.updateClat(mNMS);
+            // Start or stop DNS64 detection and 464xlat according to network state.
+            networkAgent.clatd.update();
             notifyIfacesChangedForNetworkStats();
             if (networkAgent.everConnected) {
                 try {
diff --git a/services/core/java/com/android/server/connectivity/Nat464Xlat.java b/services/core/java/com/android/server/connectivity/Nat464Xlat.java
index 9d9b1cf..2646d76 100644
--- a/services/core/java/com/android/server/connectivity/Nat464Xlat.java
+++ b/services/core/java/com/android/server/connectivity/Nat464Xlat.java
@@ -18,19 +18,24 @@
 
 import android.net.ConnectivityManager;
 import android.net.INetd;
+import android.net.InetAddresses;
 import android.net.InterfaceConfiguration;
+import android.net.IpPrefix;
 import android.net.LinkAddress;
 import android.net.LinkProperties;
 import android.net.NetworkInfo;
 import android.net.RouteInfo;
 import android.os.INetworkManagementService;
 import android.os.RemoteException;
+import android.os.ServiceSpecificException;
 import android.util.Slog;
 
+import com.android.internal.annotations.VisibleForTesting;
 import com.android.internal.util.ArrayUtils;
 import com.android.server.net.BaseNetworkObserver;
 
 import java.net.Inet4Address;
+import java.net.Inet6Address;
 import java.util.Objects;
 
 /**
@@ -67,15 +72,16 @@
     private final NetworkAgentInfo mNetwork;
 
     private enum State {
-        IDLE,       // start() not called. Base iface and stacked iface names are null.
-        STARTING,   // start() called. Base iface and stacked iface names are known.
-        RUNNING,    // start() called, and the stacked iface is known to be up.
-        STOPPING;   // stop() called, this Nat464Xlat is still registered as a network observer for
-                    // the stacked interface.
+        IDLE,         // start() not called. Base iface and stacked iface names are null.
+        DISCOVERING,  // same as IDLE, except prefix discovery in progress.
+        STARTING,     // start() called. Base iface and stacked iface names are known.
+        RUNNING,      // start() called, and the stacked iface is known to be up.
     }
 
+    private IpPrefix mNat64Prefix;
     private String mBaseIface;
     private String mIface;
+    private Inet6Address mIPv6Address;
     private State mState = State.IDLE;
 
     public Nat464Xlat(NetworkAgentInfo nai, INetd netd, INetworkManagementService nmService) {
@@ -85,20 +91,51 @@
     }
 
     /**
-     * Determines whether a network requires clat.
+     * Whether to attempt 464xlat on this network. This is true for an IPv6-only network that is
+     * currently connected and where the NetworkAgent has not disabled 464xlat. It is the signal to
+     * enable NAT64 prefix discovery.
+     *
      * @param network the NetworkAgentInfo corresponding to the network.
      * @return true if the network requires clat, false otherwise.
      */
-    public static boolean requiresClat(NetworkAgentInfo nai) {
+    @VisibleForTesting
+    protected static boolean requiresClat(NetworkAgentInfo nai) {
         // TODO: migrate to NetworkCapabilities.TRANSPORT_*.
         final boolean supported = ArrayUtils.contains(NETWORK_TYPES, nai.networkInfo.getType());
         final boolean connected = ArrayUtils.contains(NETWORK_STATES, nai.networkInfo.getState());
-        // We only run clat on networks that don't have a native IPv4 address.
-        final boolean hasIPv4Address =
-                (nai.linkProperties != null) && nai.linkProperties.hasIPv4Address();
-        final boolean skip464xlat =
-                (nai.netMisc() != null) && nai.netMisc().skip464xlat;
-        return supported && connected && !hasIPv4Address && !skip464xlat;
+
+        // Only run clat on networks that have a global IPv6 address and don't have a native IPv4
+        // address.
+        LinkProperties lp = nai.linkProperties;
+        final boolean isIpv6OnlyNetwork = (lp != null) && lp.hasGlobalIPv6Address()
+                && !lp.hasIPv4Address();
+
+        // If the network tells us it doesn't use clat, respect that.
+        final boolean skip464xlat = (nai.netMisc() != null) && nai.netMisc().skip464xlat;
+
+        return supported && connected && isIpv6OnlyNetwork && !skip464xlat;
+    }
+
+    /**
+     * Whether the clat demon should be started on this network now. This is true if requiresClat is
+     * true and a NAT64 prefix has been discovered.
+     *
+     * @param nai the NetworkAgentInfo corresponding to the network.
+     * @return true if the network should start clat, false otherwise.
+     */
+    @VisibleForTesting
+    protected static boolean shouldStartClat(NetworkAgentInfo nai) {
+        LinkProperties lp = nai.linkProperties;
+        return requiresClat(nai) && lp != null && lp.getNat64Prefix() != null;
+    }
+
+    /**
+     * @return true if we have started prefix discovery and not yet stopped it (regardless of
+     * whether it is still running or has succeeded).
+     * A true result corresponds to internal states DISCOVERING, STARTING and RUNNING.
+     */
+    public boolean isPrefixDiscoveryStarted() {
+        return mState == State.DISCOVERING || isStarted();
     }
 
     /**
@@ -106,7 +143,7 @@
      * A true result corresponds to internal states STARTING and RUNNING.
      */
     public boolean isStarted() {
-        return mState != State.IDLE;
+        return (mState == State.STARTING || mState == State.RUNNING);
     }
 
     /**
@@ -124,32 +161,31 @@
     }
 
     /**
-     * @return true if clatd has been stopped.
-     */
-    public boolean isStopping() {
-        return mState == State.STOPPING;
-    }
-
-    /**
      * Start clatd, register this Nat464Xlat as a network observer for the stacked interface,
      * and set internal state.
      */
     private void enterStartingState(String baseIface) {
         try {
             mNMService.registerObserver(this);
-        } catch(RemoteException e) {
-            Slog.e(TAG,
-                    "startClat: Can't register interface observer for clat on " + mNetwork.name());
+        } catch (RemoteException e) {
+            Slog.e(TAG, "Can't register interface observer for clat on " + mNetwork.name());
             return;
         }
+
+        String addrStr = null;
         try {
-            mNetd.clatdStart(baseIface);
-        } catch(RemoteException|IllegalStateException e) {
-            Slog.e(TAG, "Error starting clatd on " + baseIface, e);
+            addrStr = mNetd.clatdStart(baseIface, mNat64Prefix.toString());
+        } catch (RemoteException | ServiceSpecificException e) {
+            Slog.e(TAG, "Error starting clatd on " + baseIface + ": " + e);
         }
         mIface = CLAT_PREFIX + baseIface;
         mBaseIface = baseIface;
         mState = State.STARTING;
+        try {
+            mIPv6Address = (Inet6Address) InetAddresses.parseNumericAddress(addrStr);
+        } catch (ClassCastException | IllegalArgumentException | NullPointerException e) {
+            Slog.e(TAG, "Invalid IPv6 address " + addrStr);
+        }
     }
 
     /**
@@ -161,37 +197,27 @@
     }
 
     /**
-     * Stop clatd, and turn ND offload on if it had been turned off.
-     */
-    private void enterStoppingState() {
-        try {
-            mNetd.clatdStop(mBaseIface);
-        } catch(RemoteException|IllegalStateException e) {
-            Slog.e(TAG, "Error stopping clatd on " + mBaseIface, e);
-        }
-
-        mState = State.STOPPING;
-    }
-
-    /**
      * Unregister as a base observer for the stacked interface, and clear internal state.
      */
-    private void enterIdleState() {
+    private void leaveStartedState() {
         try {
             mNMService.unregisterObserver(this);
-        } catch(RemoteException|IllegalStateException e) {
-            Slog.e(TAG, "Error unregistering clatd observer on " + mBaseIface, e);
+        } catch (RemoteException | IllegalStateException e) {
+            Slog.e(TAG, "Error unregistering clatd observer on " + mBaseIface + ": " + e);
         }
-
         mIface = null;
         mBaseIface = null;
         mState = State.IDLE;
+        if (requiresClat(mNetwork)) {
+            mState = State.DISCOVERING;
+        } else {
+            stopPrefixDiscovery();
+            mState = State.IDLE;
+        }
     }
 
-    /**
-     * Starts the clat daemon.
-     */
-    public void start() {
+    @VisibleForTesting
+    protected void start() {
         if (isStarted()) {
             Slog.e(TAG, "startClat: already started");
             return;
@@ -212,20 +238,82 @@
         enterStartingState(baseIface);
     }
 
-    /**
-     * Stops the clat daemon.
-     */
-    public void stop() {
+    @VisibleForTesting
+    protected void stop() {
         if (!isStarted()) {
+            Slog.e(TAG, "stopClat: already stopped");
             return;
         }
-        Slog.i(TAG, "Stopping clatd on " + mBaseIface);
 
-        boolean wasStarting = isStarting();
-        enterStoppingState();
-        if (wasStarting) {
-            enterIdleState();
+        Slog.i(TAG, "Stopping clatd on " + mBaseIface);
+        try {
+            mNetd.clatdStop(mBaseIface);
+        } catch (RemoteException | ServiceSpecificException e) {
+            Slog.e(TAG, "Error stopping clatd on " + mBaseIface + ": " + e);
         }
+
+        String iface = mIface;
+        boolean wasRunning = isRunning();
+
+        // Change state before updating LinkProperties. handleUpdateLinkProperties ends up calling
+        // fixupLinkProperties, and if at that time the state is still RUNNING, fixupLinkProperties
+        // would wrongly inform ConnectivityService that there is still a stacked interface.
+        leaveStartedState();
+
+        if (wasRunning) {
+            LinkProperties lp = new LinkProperties(mNetwork.linkProperties);
+            lp.removeStackedLink(iface);
+            mNetwork.connService().handleUpdateLinkProperties(mNetwork, lp);
+        }
+    }
+
+    private void startPrefixDiscovery() {
+        try {
+            mNetd.resolverStartPrefix64Discovery(getNetId());
+            mState = State.DISCOVERING;
+        } catch (RemoteException | ServiceSpecificException e) {
+            Slog.e(TAG, "Error starting prefix discovery on netId " + getNetId() + ": " + e);
+        }
+    }
+
+    private void stopPrefixDiscovery() {
+        try {
+            mNetd.resolverStopPrefix64Discovery(getNetId());
+        } catch (RemoteException | ServiceSpecificException e) {
+            Slog.e(TAG, "Error stopping prefix discovery on netId " + getNetId() + ": " + e);
+        }
+    }
+
+    /**
+     * Starts/stops NAT64 prefix discovery and clatd as necessary.
+     */
+    public void update() {
+        // TODO: turn this class into a proper StateMachine. // http://b/126113090
+        if (requiresClat(mNetwork)) {
+            if (!isPrefixDiscoveryStarted()) {
+                startPrefixDiscovery();
+            } else if (shouldStartClat(mNetwork)) {
+                // NAT64 prefix detected. Start clatd.
+                // TODO: support the NAT64 prefix changing after it's been discovered. There is no
+                // need to support this at the moment because it cannot happen without changes to
+                // the Dns64Configuration code in netd.
+                start();
+            } else {
+                // NAT64 prefix removed. Stop clatd and go back into DISCOVERING state.
+                stop();
+            }
+        } else {
+            // Network no longer requires clat. Stop clat and prefix discovery.
+            if (isStarted()) {
+                stop();
+            } else if (isPrefixDiscoveryStarted()) {
+                leaveStartedState();
+            }
+        }
+    }
+
+    public void setNat64Prefix(IpPrefix nat64Prefix) {
+        mNat64Prefix = nat64Prefix;
     }
 
     /**
@@ -234,6 +322,8 @@
      * has no idea that 464xlat is running on top of it.
      */
     public void fixupLinkProperties(LinkProperties oldLp, LinkProperties lp) {
+        lp.setNat64Prefix(mNat64Prefix);
+
         if (!isRunning()) {
             return;
         }
@@ -272,7 +362,7 @@
         try {
             InterfaceConfiguration config = mNMService.getInterfaceConfig(iface);
             return config.getLinkAddress();
-        } catch(RemoteException|IllegalStateException e) {
+        } catch (RemoteException | IllegalStateException e) {
             Slog.e(TAG, "Error getting link properties: " + e);
             return null;
         }
@@ -282,6 +372,20 @@
      * Adds stacked link on base link and transitions to RUNNING state.
      */
     private void handleInterfaceLinkStateChanged(String iface, boolean up) {
+        // TODO: if we call start(), then stop(), then start() again, and the
+        // interfaceLinkStateChanged notification for the first start is delayed past the first
+        // stop, then the code becomes out of sync with system state and will behave incorrectly.
+        //
+        // This is not trivial to fix because:
+        // 1. It is not guaranteed that start() will eventually result in the interface coming up,
+        //    because there could be an error starting clat (e.g., if the interface goes down before
+        //    the packet socket can be bound).
+        // 2. If start is called multiple times, there is nothing in the interfaceLinkStateChanged
+        //    notification that says which start() call the interface was created by.
+        //
+        // Once this code is converted to StateMachine, it will be possible to use deferMessage to
+        // ensure it stays in STARTING state until the interfaceLinkStateChanged notification fires,
+        // and possibly use a timeout (or provide some guarantees at the lower layer) to address #1.
         if (!isStarting() || !up || !Objects.equals(mIface, iface)) {
             return;
         }
@@ -307,20 +411,16 @@
         if (!Objects.equals(mIface, iface)) {
             return;
         }
-        if (!isRunning() && !isStopping()) {
+        if (!isRunning()) {
             return;
         }
 
         Slog.i(TAG, "interface " + iface + " removed");
-        if (!isStopping()) {
-            // Ensure clatd is stopped if stop() has not been called: this likely means that clatd
-            // has crashed.
-            enterStoppingState();
-        }
-        enterIdleState();
-        LinkProperties lp = new LinkProperties(mNetwork.linkProperties);
-        lp.removeStackedLink(iface);
-        mNetwork.connService().handleUpdateLinkProperties(mNetwork, lp);
+        // If we're running, and the interface was removed, then we didn't call stop(), and it's
+        // likely that clatd crashed. Ensure we call stop() so we can start clatd again. Calling
+        // stop() will also update LinkProperties, and if clatd crashed, the LinkProperties update
+        // will cause ConnectivityService to call start() again.
+        stop();
     }
 
     @Override
@@ -337,4 +437,9 @@
     public String toString() {
         return "mBaseIface: " + mBaseIface + ", mIface: " + mIface + ", mState: " + mState;
     }
+
+    @VisibleForTesting
+    protected int getNetId() {
+        return mNetwork.network.netId;
+    }
 }
diff --git a/services/core/java/com/android/server/connectivity/NetworkAgentInfo.java b/services/core/java/com/android/server/connectivity/NetworkAgentInfo.java
index d0cff25..f11a0de 100644
--- a/services/core/java/com/android/server/connectivity/NetworkAgentInfo.java
+++ b/services/core/java/com/android/server/connectivity/NetworkAgentInfo.java
@@ -236,7 +236,7 @@
     public final AsyncChannel asyncChannel;
 
     // Used by ConnectivityService to keep track of 464xlat.
-    public Nat464Xlat clatd;
+    public final Nat464Xlat clatd;
 
     // Set after asynchronous creation of the NetworkMonitor.
     private volatile INetworkMonitor mNetworkMonitor;
@@ -244,8 +244,6 @@
     private static final String TAG = ConnectivityService.class.getSimpleName();
     private static final boolean VDBG = false;
     private final ConnectivityService mConnService;
-    private final INetd mNetd;
-    private final INetworkManagementService mNMS;
     private final Context mContext;
     private final Handler mHandler;
 
@@ -260,9 +258,8 @@
         linkProperties = lp;
         networkCapabilities = nc;
         currentScore = score;
+        clatd = new Nat464Xlat(this, netd, nms);
         mConnService = connService;
-        mNetd = netd;
-        mNMS = nms;
         mContext = context;
         mHandler = handler;
         networkMisc = misc;
@@ -595,32 +592,6 @@
         for (LingerTimer timer : mLingerTimers) { pw.println(timer); }
     }
 
-    public void updateClat(INetworkManagementService netd) {
-        if (Nat464Xlat.requiresClat(this)) {
-            maybeStartClat();
-        } else {
-            maybeStopClat();
-        }
-    }
-
-    /** Ensure clat has started for this network. */
-    public void maybeStartClat() {
-        if (clatd != null && clatd.isStarted()) {
-            return;
-        }
-        clatd = new Nat464Xlat(this, mNetd, mNMS);
-        clatd.start();
-    }
-
-    /** Ensure clat has stopped for this network. */
-    public void maybeStopClat() {
-        if (clatd == null) {
-            return;
-        }
-        clatd.stop();
-        clatd = null;
-    }
-
     public String toString() {
         return "NetworkAgentInfo{ ni{" + networkInfo + "}  "
                 + "network{" + network + "}  nethandle{" + network.getNetworkHandle() + "}  "
diff --git a/tests/net/java/com/android/server/ConnectivityServiceTest.java b/tests/net/java/com/android/server/ConnectivityServiceTest.java
index d1a0692..c126026 100644
--- a/tests/net/java/com/android/server/ConnectivityServiceTest.java
+++ b/tests/net/java/com/android/server/ConnectivityServiceTest.java
@@ -17,10 +17,10 @@
 package com.android.server;
 
 import static android.net.ConnectivityManager.CONNECTIVITY_ACTION;
+import static android.net.ConnectivityManager.NETID_UNSET;
 import static android.net.ConnectivityManager.PRIVATE_DNS_MODE_OFF;
 import static android.net.ConnectivityManager.PRIVATE_DNS_MODE_OPPORTUNISTIC;
 import static android.net.ConnectivityManager.PRIVATE_DNS_MODE_PROVIDER_HOSTNAME;
-import static android.net.ConnectivityManager.NETID_UNSET;
 import static android.net.ConnectivityManager.TYPE_ETHERNET;
 import static android.net.ConnectivityManager.TYPE_MOBILE;
 import static android.net.ConnectivityManager.TYPE_MOBILE_FOTA;
@@ -1798,6 +1798,12 @@
                     fn.test((NetworkCapabilities) cbi.arg));
         }
 
+        void expectLinkPropertiesLike(Predicate<LinkProperties> fn, MockNetworkAgent agent) {
+            CallbackInfo cbi = expectCallback(CallbackState.LINK_PROPERTIES, agent);
+            assertTrue("Received LinkProperties don't match expectations : " + cbi.arg,
+                    fn.test((LinkProperties) cbi.arg));
+        }
+
         void expectBlockedStatusCallback(boolean expectBlocked, MockNetworkAgent agent) {
             CallbackInfo cbi = expectCallback(CallbackState.BLOCKED_STATUS, agent);
             boolean actualBlocked = (boolean) cbi.arg;
@@ -5087,6 +5093,9 @@
     public void testStackedLinkProperties() throws UnknownHostException, RemoteException {
         final LinkAddress myIpv4 = new LinkAddress("1.2.3.4/24");
         final LinkAddress myIpv6 = new LinkAddress("2001:db8:1::1/64");
+        final String kNat64PrefixString = "2001:db8:64:64:64:64::";
+        final IpPrefix kNat64Prefix = new IpPrefix(InetAddress.getByName(kNat64PrefixString), 96);
+
         final NetworkRequest networkRequest = new NetworkRequest.Builder()
                 .addTransportType(TRANSPORT_CELLULAR)
                 .addCapability(NET_CAPABILITY_INTERNET)
@@ -5094,8 +5103,9 @@
         final TestNetworkCallback networkCallback = new TestNetworkCallback();
         mCm.registerNetworkCallback(networkRequest, networkCallback);
 
-        // Prepare ipv6 only link properties and connect.
+        // Prepare ipv6 only link properties.
         mCellNetworkAgent = new MockNetworkAgent(TRANSPORT_CELLULAR);
+        final int cellNetId = mCellNetworkAgent.getNetwork().netId;
         final LinkProperties cellLp = new LinkProperties();
         cellLp.setInterfaceName(MOBILE_IFNAME);
         cellLp.addLinkAddress(myIpv6);
@@ -5105,15 +5115,44 @@
         when(mNetworkManagementService.getInterfaceConfig(CLAT_PREFIX + MOBILE_IFNAME))
                 .thenReturn(getClatInterfaceConfig(myIpv4));
 
-        // Connect with ipv6 link properties, then expect clat setup ipv4 and update link
-        // properties properly.
+        // Connect with ipv6 link properties. Expect prefix discovery to be started.
         mCellNetworkAgent.sendLinkProperties(cellLp);
         mCellNetworkAgent.connect(true);
         networkCallback.expectAvailableThenValidatedCallbacks(mCellNetworkAgent);
-        verify(mMockNetd, times(1)).clatdStart(MOBILE_IFNAME);
-        Nat464Xlat clat = mService.getNat464Xlat(mCellNetworkAgent);
+        verify(mMockNetd, times(1)).resolverStartPrefix64Discovery(cellNetId);
 
-        // Clat iface up, expect stack link updated.
+        // Switching default network updates TCP buffer sizes.
+        verifyTcpBufferSizeChange(ConnectivityService.DEFAULT_TCP_BUFFER_SIZES);
+
+        // Add an IPv4 address. Expect prefix discovery to be stopped. Netd doesn't tell us that
+        // the NAT64 prefix was removed because one was never discovered.
+        cellLp.addLinkAddress(myIpv4);
+        mCellNetworkAgent.sendLinkProperties(cellLp);
+        networkCallback.expectCallback(CallbackState.LINK_PROPERTIES, mCellNetworkAgent);
+        verify(mMockNetd, times(1)).resolverStopPrefix64Discovery(cellNetId);
+
+        verifyNoMoreInteractions(mMockNetd);
+        reset(mMockNetd);
+
+        // Remove IPv4 address. Expect prefix discovery to be started again.
+        cellLp.removeLinkAddress(myIpv4);
+        cellLp.removeRoute(new RouteInfo(myIpv4, null, MOBILE_IFNAME));
+        mCellNetworkAgent.sendLinkProperties(cellLp);
+        networkCallback.expectCallback(CallbackState.LINK_PROPERTIES, mCellNetworkAgent);
+        verify(mMockNetd, times(1)).resolverStartPrefix64Discovery(cellNetId);
+
+        // When NAT64 prefix discovery succeeds, LinkProperties are updated and clatd is started.
+        Nat464Xlat clat = mService.getNat464Xlat(mCellNetworkAgent);
+        assertNull(mCm.getLinkProperties(mCellNetworkAgent.getNetwork()).getNat64Prefix());
+        mService.mNetdEventCallback.onNat64PrefixEvent(cellNetId, true /* added */,
+                kNat64PrefixString, 96);
+        LinkProperties lpBeforeClat = (LinkProperties) networkCallback.expectCallback(
+                CallbackState.LINK_PROPERTIES, mCellNetworkAgent).arg;
+        assertEquals(0, lpBeforeClat.getStackedLinks().size());
+        assertEquals(kNat64Prefix, lpBeforeClat.getNat64Prefix());
+        verify(mMockNetd, times(1)).clatdStart(MOBILE_IFNAME, kNat64Prefix.toString());
+
+        // Clat iface comes up. Expect stacked link to be added.
         clat.interfaceLinkStateChanged(CLAT_PREFIX + MOBILE_IFNAME, true);
         networkCallback.expectCallback(CallbackState.LINK_PROPERTIES, mCellNetworkAgent);
         List<LinkProperties> stackedLps = mCm.getLinkProperties(mCellNetworkAgent.getNetwork())
@@ -5130,20 +5169,66 @@
         assertNotEquals(stackedLpsAfterChange, Collections.EMPTY_LIST);
         assertEquals(makeClatLinkProperties(myIpv4), stackedLpsAfterChange.get(0));
 
-        // Add ipv4 address, expect stacked linkproperties be cleaned up
+        // Add ipv4 address, expect that clatd and prefix discovery are stopped and stacked
+        // linkproperties are cleaned up.
         cellLp.addLinkAddress(myIpv4);
         cellLp.addRoute(new RouteInfo(myIpv4, null, MOBILE_IFNAME));
         mCellNetworkAgent.sendLinkProperties(cellLp);
         networkCallback.expectCallback(CallbackState.LINK_PROPERTIES, mCellNetworkAgent);
         verify(mMockNetd, times(1)).clatdStop(MOBILE_IFNAME);
+        verify(mMockNetd, times(1)).resolverStopPrefix64Discovery(cellNetId);
 
-        // Clat iface removed, expect linkproperties revert to original one
-        clat.interfaceRemoved(CLAT_PREFIX + MOBILE_IFNAME);
+        // As soon as stop is called, the linkproperties lose the stacked interface.
         networkCallback.expectCallback(CallbackState.LINK_PROPERTIES, mCellNetworkAgent);
         LinkProperties actualLpAfterIpv4 = mCm.getLinkProperties(mCellNetworkAgent.getNetwork());
-        assertEquals(cellLp, actualLpAfterIpv4);
+        LinkProperties expected = new LinkProperties(cellLp);
+        expected.setNat64Prefix(kNat64Prefix);
+        assertEquals(expected, actualLpAfterIpv4);
+        assertEquals(0, actualLpAfterIpv4.getStackedLinks().size());
 
-        // Clean up
+        // The interface removed callback happens but has no effect after stop is called.
+        clat.interfaceRemoved(CLAT_PREFIX + MOBILE_IFNAME);
+        networkCallback.assertNoCallback();
+
+        verifyNoMoreInteractions(mMockNetd);
+        reset(mMockNetd);
+
+        // Stopping prefix discovery causes netd to tell us that the NAT64 prefix is gone.
+        mService.mNetdEventCallback.onNat64PrefixEvent(cellNetId, false /* added */,
+                kNat64PrefixString, 96);
+        networkCallback.expectLinkPropertiesLike((lp) -> lp.getNat64Prefix() == null,
+                mCellNetworkAgent);
+
+        // Remove IPv4 address and expect prefix discovery and clatd to be started again.
+        cellLp.removeLinkAddress(myIpv4);
+        cellLp.removeRoute(new RouteInfo(myIpv4, null, MOBILE_IFNAME));
+        cellLp.removeDnsServer(InetAddress.getByName("8.8.8.8"));
+        mCellNetworkAgent.sendLinkProperties(cellLp);
+        networkCallback.expectCallback(CallbackState.LINK_PROPERTIES, mCellNetworkAgent);
+        verify(mMockNetd, times(1)).resolverStartPrefix64Discovery(cellNetId);
+        mService.mNetdEventCallback.onNat64PrefixEvent(cellNetId, true /* added */,
+                kNat64PrefixString, 96);
+        networkCallback.expectCallback(CallbackState.LINK_PROPERTIES, mCellNetworkAgent);
+        verify(mMockNetd, times(1)).clatdStart(MOBILE_IFNAME, kNat64Prefix.toString());
+
+
+        // Clat iface comes up. Expect stacked link to be added.
+        clat.interfaceLinkStateChanged(CLAT_PREFIX + MOBILE_IFNAME, true);
+        networkCallback.expectLinkPropertiesLike(
+                (lp) -> lp.getStackedLinks().size() == 1 && lp.getNat64Prefix() != null,
+                mCellNetworkAgent);
+
+        // NAT64 prefix is removed. Expect that clat is stopped.
+        mService.mNetdEventCallback.onNat64PrefixEvent(cellNetId, false /* added */,
+                kNat64PrefixString, 96);
+        networkCallback.expectLinkPropertiesLike(
+                (lp) -> lp.getStackedLinks().size() == 0 && lp.getNat64Prefix() == null,
+                mCellNetworkAgent);
+        verify(mMockNetd, times(1)).clatdStop(MOBILE_IFNAME);
+        networkCallback.expectLinkPropertiesLike((lp) -> lp.getStackedLinks().size() == 0,
+                mCellNetworkAgent);
+
+        // Clean up.
         mCellNetworkAgent.disconnect();
         networkCallback.expectCallback(CallbackState.LOST, mCellNetworkAgent);
         networkCallback.assertNoCallback();
@@ -5224,30 +5309,34 @@
         mCm.unregisterNetworkCallback(networkCallback);
     }
 
-    private static final String TEST_TCP_BUFFER_SIZES = "1,2,3,4,5,6";
-
-    private void verifyTcpBufferSizeChange(String tcpBufferSizes) throws Exception {
+    private void verifyTcpBufferSizeChange(String tcpBufferSizes) {
         String[] values = tcpBufferSizes.split(",");
         String rmemValues = String.join(" ", values[0], values[1], values[2]);
         String wmemValues = String.join(" ", values[3], values[4], values[5]);
         waitForIdle();
-        verify(mMockNetd, atLeastOnce()).setTcpRWmemorySize(rmemValues, wmemValues);
+        try {
+            verify(mMockNetd, atLeastOnce()).setTcpRWmemorySize(rmemValues, wmemValues);
+        } catch (RemoteException e) {
+            fail("mMockNetd should never throw RemoteException");
+        }
         reset(mMockNetd);
     }
 
     @Test
-    public void testTcpBufferReset() throws Exception {
+    public void testTcpBufferReset() {
+        final String testTcpBufferSizes = "1,2,3,4,5,6";
+
         mCellNetworkAgent = new MockNetworkAgent(TRANSPORT_CELLULAR);
         reset(mMockNetd);
-        // Simple connection should have updated tcp buffer size.
+        // Switching default network updates TCP buffer sizes.
         mCellNetworkAgent.connect(false);
         verifyTcpBufferSizeChange(ConnectivityService.DEFAULT_TCP_BUFFER_SIZES);
 
         // Change link Properties should have updated tcp buffer size.
         LinkProperties lp = new LinkProperties();
-        lp.setTcpBufferSizes(TEST_TCP_BUFFER_SIZES);
+        lp.setTcpBufferSizes(testTcpBufferSizes);
         mCellNetworkAgent.sendLinkProperties(lp);
-        verifyTcpBufferSizeChange(TEST_TCP_BUFFER_SIZES);
+        verifyTcpBufferSizeChange(testTcpBufferSizes);
     }
 
     @Test
diff --git a/tests/net/java/com/android/server/connectivity/Nat464XlatTest.java b/tests/net/java/com/android/server/connectivity/Nat464XlatTest.java
index 07b1d05..37c0df8 100644
--- a/tests/net/java/com/android/server/connectivity/Nat464XlatTest.java
+++ b/tests/net/java/com/android/server/connectivity/Nat464XlatTest.java
@@ -16,9 +16,11 @@
 
 package com.android.server.connectivity;
 
+import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
 import static org.mockito.Mockito.eq;
+import static org.mockito.Mockito.inOrder;
 import static org.mockito.Mockito.times;
 import static org.mockito.Mockito.verify;
 import static org.mockito.Mockito.verifyNoMoreInteractions;
@@ -27,6 +29,7 @@
 import android.net.ConnectivityManager;
 import android.net.INetd;
 import android.net.InterfaceConfiguration;
+import android.net.IpPrefix;
 import android.net.LinkAddress;
 import android.net.LinkProperties;
 import android.net.NetworkInfo;
@@ -43,6 +46,7 @@
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.mockito.ArgumentCaptor;
+import org.mockito.InOrder;
 import org.mockito.Mock;
 import org.mockito.MockitoAnnotations;
 
@@ -53,6 +57,8 @@
     static final String BASE_IFACE = "test0";
     static final String STACKED_IFACE = "v4-test0";
     static final LinkAddress ADDR = new LinkAddress("192.0.2.5/29");
+    static final String NAT64_PREFIX = "64:ff9b::/96";
+    static final int NETID = 42;
 
     @Mock ConnectivityService mConnectivity;
     @Mock NetworkMisc mMisc;
@@ -65,7 +71,11 @@
     Handler mHandler;
 
     Nat464Xlat makeNat464Xlat() {
-        return new Nat464Xlat(mNai, mNetd, mNms);
+        return new Nat464Xlat(mNai, mNetd, mNms) {
+            @Override protected int getNetId() {
+                return NETID;
+            }
+        };
     }
 
     @Before
@@ -87,6 +97,24 @@
         when(mConfig.getLinkAddress()).thenReturn(ADDR);
     }
 
+    private void assertRequiresClat(boolean expected, NetworkAgentInfo nai) {
+        String msg = String.format("requiresClat expected %b for type=%d state=%s skip=%b "
+                + "nat64Prefix=%s addresses=%s", expected, nai.networkInfo.getType(),
+                nai.networkInfo.getDetailedState(),
+                mMisc.skip464xlat, nai.linkProperties.getNat64Prefix(),
+                nai.linkProperties.getLinkAddresses());
+        assertEquals(msg, expected, Nat464Xlat.requiresClat(nai));
+    }
+
+    private void assertShouldStartClat(boolean expected, NetworkAgentInfo nai) {
+        String msg = String.format("shouldStartClat expected %b for type=%d state=%s skip=%b "
+                + "nat64Prefix=%s addresses=%s", expected, nai.networkInfo.getType(),
+                nai.networkInfo.getDetailedState(),
+                mMisc.skip464xlat, nai.linkProperties.getNat64Prefix(),
+                nai.linkProperties.getLinkAddresses());
+        assertEquals(msg, expected, Nat464Xlat.shouldStartClat(nai));
+    }
+
     @Test
     public void testRequiresClat() throws Exception {
         final int[] supportedTypes = {
@@ -102,20 +130,45 @@
             NetworkInfo.DetailedState.SUSPENDED,
         };
 
+        LinkProperties oldLp = new LinkProperties(mNai.linkProperties);
         for (int type : supportedTypes) {
             mNai.networkInfo.setType(type);
             for (NetworkInfo.DetailedState state : supportedDetailedStates) {
                 mNai.networkInfo.setDetailedState(state, "reason", "extraInfo");
-                String msg = String.format("requiresClat expected for type=%d state=%s",
-                        type, state);
+
+                mNai.linkProperties.setNat64Prefix(new IpPrefix("2001:db8:0:64::/96"));
+                assertRequiresClat(false, mNai);
+                assertShouldStartClat(false, mNai);
+
+                mNai.linkProperties.addLinkAddress(new LinkAddress("fc00::1/64"));
+                assertRequiresClat(false, mNai);
+                assertShouldStartClat(false, mNai);
+
+                mNai.linkProperties.addLinkAddress(new LinkAddress("2001:db8::1/64"));
+                assertRequiresClat(true, mNai);
+                assertShouldStartClat(true, mNai);
 
                 mMisc.skip464xlat = true;
-                String errorMsg = msg + String.format(" skip464xlat=%b", mMisc.skip464xlat);
-                assertFalse(errorMsg, Nat464Xlat.requiresClat(mNai));
+                assertRequiresClat(false, mNai);
+                assertShouldStartClat(false, mNai);
 
                 mMisc.skip464xlat = false;
-                errorMsg = msg + String.format(" skip464xlat=%b", mMisc.skip464xlat);
-                assertTrue(errorMsg, Nat464Xlat.requiresClat(mNai));
+                assertRequiresClat(true, mNai);
+                assertShouldStartClat(true, mNai);
+
+                mNai.linkProperties.addLinkAddress(new LinkAddress("192.0.2.2/24"));
+                assertRequiresClat(false, mNai);
+                assertShouldStartClat(false, mNai);
+
+                mNai.linkProperties.removeLinkAddress(new LinkAddress("192.0.2.2/24"));
+                assertRequiresClat(true, mNai);
+                assertShouldStartClat(true, mNai);
+
+                mNai.linkProperties.setNat64Prefix(null);
+                assertRequiresClat(true, mNai);
+                assertShouldStartClat(false, mNai);
+
+                mNai.linkProperties = new LinkProperties(oldLp);
             }
         }
     }
@@ -125,11 +178,13 @@
         Nat464Xlat nat = makeNat464Xlat();
         ArgumentCaptor<LinkProperties> c = ArgumentCaptor.forClass(LinkProperties.class);
 
-        // ConnectivityService starts clat.
+        nat.setNat64Prefix(new IpPrefix(NAT64_PREFIX));
+
+        // Start clat.
         nat.start();
 
         verify(mNms).registerObserver(eq(nat));
-        verify(mNetd).clatdStart(eq(BASE_IFACE));
+        verify(mNetd).clatdStart(eq(BASE_IFACE), eq(NAT64_PREFIX));
 
         // Stacked interface up notification arrives.
         nat.interfaceLinkStateChanged(STACKED_IFACE, true);
@@ -141,22 +196,109 @@
         assertTrue(c.getValue().getAllInterfaceNames().contains(STACKED_IFACE));
         assertRunning(nat);
 
-        // ConnectivityService stops clat (Network disconnects, IPv4 addr appears, ...).
+        // Stop clat (Network disconnects, IPv4 addr appears, ...).
         nat.stop();
 
         verify(mNetd).clatdStop(eq(BASE_IFACE));
+        verify(mConnectivity, times(2)).handleUpdateLinkProperties(eq(mNai), c.capture());
+        verify(mNms).unregisterObserver(eq(nat));
+        assertTrue(c.getValue().getStackedLinks().isEmpty());
+        assertFalse(c.getValue().getAllInterfaceNames().contains(STACKED_IFACE));
+        verify(mNetd).resolverStopPrefix64Discovery(eq(NETID));
+        assertIdle(nat);
 
-        // Stacked interface removed notification arrives.
+        // Stacked interface removed notification arrives and is ignored.
         nat.interfaceRemoved(STACKED_IFACE);
         mLooper.dispatchNext();
 
-        verify(mNms).unregisterObserver(eq(nat));
-        verify(mConnectivity, times(2)).handleUpdateLinkProperties(eq(mNai), c.capture());
+        verifyNoMoreInteractions(mNetd, mNms, mConnectivity);
+    }
+
+    private void checkStartStopStart(boolean interfaceRemovedFirst) throws Exception {
+        Nat464Xlat nat = makeNat464Xlat();
+        ArgumentCaptor<LinkProperties> c = ArgumentCaptor.forClass(LinkProperties.class);
+        InOrder inOrder = inOrder(mNetd, mConnectivity);
+
+        nat.setNat64Prefix(new IpPrefix(NAT64_PREFIX));
+
+        nat.start();
+
+        inOrder.verify(mNetd).clatdStart(eq(BASE_IFACE), eq(NAT64_PREFIX));
+
+        // Stacked interface up notification arrives.
+        nat.interfaceLinkStateChanged(STACKED_IFACE, true);
+        mLooper.dispatchNext();
+
+        inOrder.verify(mConnectivity).handleUpdateLinkProperties(eq(mNai), c.capture());
+        assertFalse(c.getValue().getStackedLinks().isEmpty());
+        assertTrue(c.getValue().getAllInterfaceNames().contains(STACKED_IFACE));
+        assertRunning(nat);
+
+        // ConnectivityService stops clat (Network disconnects, IPv4 addr appears, ...).
+        nat.stop();
+
+        inOrder.verify(mNetd).clatdStop(eq(BASE_IFACE));
+
+        inOrder.verify(mConnectivity, times(1)).handleUpdateLinkProperties(eq(mNai), c.capture());
         assertTrue(c.getValue().getStackedLinks().isEmpty());
         assertFalse(c.getValue().getAllInterfaceNames().contains(STACKED_IFACE));
         assertIdle(nat);
 
-        verifyNoMoreInteractions(mNetd, mNms, mConnectivity);
+        if (interfaceRemovedFirst) {
+            // Stacked interface removed notification arrives and is ignored.
+            nat.interfaceRemoved(STACKED_IFACE);
+            mLooper.dispatchNext();
+            nat.interfaceLinkStateChanged(STACKED_IFACE, false);
+            mLooper.dispatchNext();
+        }
+
+        assertTrue(c.getValue().getStackedLinks().isEmpty());
+        assertFalse(c.getValue().getAllInterfaceNames().contains(STACKED_IFACE));
+        assertIdle(nat);
+        inOrder.verifyNoMoreInteractions();
+
+        nat.start();
+
+        inOrder.verify(mNetd).clatdStart(eq(BASE_IFACE), eq(NAT64_PREFIX));
+
+        if (!interfaceRemovedFirst) {
+            // Stacked interface removed notification arrives and is ignored.
+            nat.interfaceRemoved(STACKED_IFACE);
+            mLooper.dispatchNext();
+            nat.interfaceLinkStateChanged(STACKED_IFACE, false);
+            mLooper.dispatchNext();
+        }
+
+        // Stacked interface up notification arrives.
+        nat.interfaceLinkStateChanged(STACKED_IFACE, true);
+        mLooper.dispatchNext();
+
+        inOrder.verify(mConnectivity).handleUpdateLinkProperties(eq(mNai), c.capture());
+        assertFalse(c.getValue().getStackedLinks().isEmpty());
+        assertTrue(c.getValue().getAllInterfaceNames().contains(STACKED_IFACE));
+        assertRunning(nat);
+
+        // ConnectivityService stops clat again.
+        nat.stop();
+
+        inOrder.verify(mNetd).clatdStop(eq(BASE_IFACE));
+
+        inOrder.verify(mConnectivity, times(1)).handleUpdateLinkProperties(eq(mNai), c.capture());
+        assertTrue(c.getValue().getStackedLinks().isEmpty());
+        assertFalse(c.getValue().getAllInterfaceNames().contains(STACKED_IFACE));
+        assertIdle(nat);
+
+        inOrder.verifyNoMoreInteractions();
+    }
+
+    @Test
+    public void testStartStopStart() throws Exception {
+        checkStartStopStart(true);
+    }
+
+    @Test
+    public void testStartStopStartBeforeInterfaceRemoved() throws Exception {
+        checkStartStopStart(false);
     }
 
     @Test
@@ -164,11 +306,12 @@
         Nat464Xlat nat = makeNat464Xlat();
         ArgumentCaptor<LinkProperties> c = ArgumentCaptor.forClass(LinkProperties.class);
 
-        // ConnectivityService starts clat.
+        nat.setNat64Prefix(new IpPrefix(NAT64_PREFIX));
+
         nat.start();
 
         verify(mNms).registerObserver(eq(nat));
-        verify(mNetd).clatdStart(eq(BASE_IFACE));
+        verify(mNetd).clatdStart(eq(BASE_IFACE), eq(NAT64_PREFIX));
 
         // Stacked interface up notification arrives.
         nat.interfaceLinkStateChanged(STACKED_IFACE, true);
@@ -184,9 +327,10 @@
         nat.interfaceRemoved(STACKED_IFACE);
         mLooper.dispatchNext();
 
-        verify(mNms).unregisterObserver(eq(nat));
         verify(mNetd).clatdStop(eq(BASE_IFACE));
         verify(mConnectivity, times(2)).handleUpdateLinkProperties(eq(mNai), c.capture());
+        verify(mNms).unregisterObserver(eq(nat));
+        verify(mNetd).resolverStopPrefix64Discovery(eq(NETID));
         assertTrue(c.getValue().getStackedLinks().isEmpty());
         assertFalse(c.getValue().getAllInterfaceNames().contains(STACKED_IFACE));
         assertIdle(nat);
@@ -201,24 +345,25 @@
     public void testStopBeforeClatdStarts() throws Exception {
         Nat464Xlat nat = makeNat464Xlat();
 
-        // ConnectivityService starts clat.
+        nat.setNat64Prefix(new IpPrefix(NAT64_PREFIX));
+
         nat.start();
 
         verify(mNms).registerObserver(eq(nat));
-        verify(mNetd).clatdStart(eq(BASE_IFACE));
+        verify(mNetd).clatdStart(eq(BASE_IFACE), eq(NAT64_PREFIX));
 
         // ConnectivityService immediately stops clat (Network disconnects, IPv4 addr appears, ...)
         nat.stop();
 
-        verify(mNms).unregisterObserver(eq(nat));
         verify(mNetd).clatdStop(eq(BASE_IFACE));
+        verify(mNms).unregisterObserver(eq(nat));
+        verify(mNetd).resolverStopPrefix64Discovery(eq(NETID));
         assertIdle(nat);
 
         // In-flight interface up notification arrives: no-op
         nat.interfaceLinkStateChanged(STACKED_IFACE, true);
         mLooper.dispatchNext();
 
-
         // Interface removed notification arrives after stopClatd() takes effect: no-op.
         nat.interfaceRemoved(STACKED_IFACE);
         mLooper.dispatchNext();
@@ -232,17 +377,19 @@
     public void testStopAndClatdNeverStarts() throws Exception {
         Nat464Xlat nat = makeNat464Xlat();
 
-        // ConnectivityService starts clat.
+        nat.setNat64Prefix(new IpPrefix(NAT64_PREFIX));
+
         nat.start();
 
         verify(mNms).registerObserver(eq(nat));
-        verify(mNetd).clatdStart(eq(BASE_IFACE));
+        verify(mNetd).clatdStart(eq(BASE_IFACE), eq(NAT64_PREFIX));
 
         // ConnectivityService immediately stops clat (Network disconnects, IPv4 addr appears, ...)
         nat.stop();
 
-        verify(mNms).unregisterObserver(eq(nat));
         verify(mNetd).clatdStop(eq(BASE_IFACE));
+        verify(mNms).unregisterObserver(eq(nat));
+        verify(mNetd).resolverStopPrefix64Discovery(eq(NETID));
         assertIdle(nat);
 
         verifyNoMoreInteractions(mNetd, mNms, mConnectivity);