diff --git a/services/incremental/IncrementalService.cpp b/services/incremental/IncrementalService.cpp
index c1f237f..68b7ac0 100644
--- a/services/incremental/IncrementalService.cpp
+++ b/services/incremental/IncrementalService.cpp
@@ -160,7 +160,8 @@
 
 IncrementalService::IncFsMount::~IncFsMount() {
     if (dataLoaderStub) {
-        dataLoaderStub->destroy();
+        dataLoaderStub->requestDestroy();
+        dataLoaderStub->waitForDestroy();
     }
     LOG(INFO) << "Unmounting and cleaning up mount " << mountId << " with root '" << root << '\'';
     for (auto&& [target, _] : bindPoints) {
@@ -298,16 +299,7 @@
         dprintf(fd, "\t\troot: %s\n", mnt.root.c_str());
         dprintf(fd, "\t\tnextStorageDirNo: %d\n", mnt.nextStorageDirNo.load());
         if (mnt.dataLoaderStub) {
-            const auto& dataLoaderStub = *mnt.dataLoaderStub;
-            dprintf(fd, "\t\tdataLoaderStatus: %d\n", dataLoaderStub.status());
-            dprintf(fd, "\t\tdataLoaderStartRequested: %s\n",
-                    dataLoaderStub.startRequested() ? "true" : "false");
-            const auto& params = dataLoaderStub.params();
-            dprintf(fd, "\t\tdataLoaderParams:\n");
-            dprintf(fd, "\t\t\ttype: %s\n", toString(params.type).c_str());
-            dprintf(fd, "\t\t\tpackageName: %s\n", params.packageName.c_str());
-            dprintf(fd, "\t\t\tclassName: %s\n", params.className.c_str());
-            dprintf(fd, "\t\t\targuments: %s\n", params.arguments.c_str());
+            mnt.dataLoaderStub->onDump(fd);
         }
         dprintf(fd, "\t\tstorages (%d):\n", int(mnt.storages.size()));
         for (auto&& [storageId, storage] : mnt.storages) {
@@ -356,12 +348,7 @@
     std::thread([this, mounts = std::move(mounts)]() {
         mJni->initializeForCurrentThread();
         for (auto&& ifs : mounts) {
-            if (ifs->dataLoaderStub->create()) {
-                LOG(INFO) << "Successfully started data loader for mount " << ifs->mountId;
-            } else {
-                // TODO(b/133435829): handle data loader start failures
-                LOG(WARNING) << "Failed to start data loader for mount " << ifs->mountId;
-            }
+            ifs->dataLoaderStub->requestStart();
         }
     }).detach();
 }
@@ -521,7 +508,7 @@
     mountIt->second = std::move(ifs);
     l.unlock();
 
-    if (mSystemReady.load(std::memory_order_relaxed) && !dataLoaderStub->create()) {
+    if (mSystemReady.load(std::memory_order_relaxed) && !dataLoaderStub->requestCreate()) {
         // failed to create data loader
         LOG(ERROR) << "initializeDataLoader() failed";
         deleteStorage(dataLoaderStub->id());
@@ -1470,16 +1457,55 @@
     }
 }
 
+IncrementalService::DataLoaderStub::DataLoaderStub(IncrementalService& service, MountId id,
+                                                   DataLoaderParamsParcel&& params,
+                                                   FileSystemControlParcel&& control,
+                                                   const DataLoaderStatusListener* externalListener)
+      : mService(service),
+        mId(id),
+        mParams(std::move(params)),
+        mControl(std::move(control)),
+        mListener(externalListener ? *externalListener : DataLoaderStatusListener()) {
+    //
+}
+
 IncrementalService::DataLoaderStub::~DataLoaderStub() {
     waitForDestroy();
 }
 
-bool IncrementalService::DataLoaderStub::create() {
+bool IncrementalService::DataLoaderStub::requestCreate() {
+    return setTargetStatus(IDataLoaderStatusListener::DATA_LOADER_CREATED);
+}
+
+bool IncrementalService::DataLoaderStub::requestStart() {
+    return setTargetStatus(IDataLoaderStatusListener::DATA_LOADER_STARTED);
+}
+
+bool IncrementalService::DataLoaderStub::requestDestroy() {
+    return setTargetStatus(IDataLoaderStatusListener::DATA_LOADER_DESTROYED);
+}
+
+bool IncrementalService::DataLoaderStub::waitForDestroy(Clock::duration duration) {
+    return waitForStatus(IDataLoaderStatusListener::DATA_LOADER_DESTROYED, duration);
+}
+
+bool IncrementalService::DataLoaderStub::setTargetStatus(int status) {
     {
         std::unique_lock lock(mStatusMutex);
-        mStartRequested = false;
-        mDestroyRequested = false;
+        mTargetStatus = status;
+        mTargetStatusTs = Clock::now();
     }
+    return fsmStep();
+}
+
+bool IncrementalService::DataLoaderStub::waitForStatus(int status, Clock::duration duration) {
+    auto now = Clock::now();
+    std::unique_lock lock(mStatusMutex);
+    return mStatusCondition.wait_until(lock, now + duration,
+                                       [this, status] { return mCurrentStatus == status; });
+}
+
+bool IncrementalService::DataLoaderStub::create() {
     bool created = false;
     auto status = mService.mDataLoaderManager->initializeDataLoader(mId, mParams, mControl, this,
                                                                     &created);
@@ -1490,115 +1516,101 @@
     return true;
 }
 
-bool IncrementalService::DataLoaderStub::requestStart() {
-    {
-        std::unique_lock lock(mStatusMutex);
-        mStartRequested = true;
-        if (mStatus != IDataLoaderStatusListener::DATA_LOADER_CREATED) {
-            return true;
-        }
-    }
-    return start();
-}
-
 bool IncrementalService::DataLoaderStub::start() {
     sp<IDataLoader> dataloader;
     auto status = mService.mDataLoaderManager->getDataLoader(mId, &dataloader);
     if (!status.isOk()) {
+        LOG(ERROR) << "Failed to get dataloader: " << status.toString8();
         return false;
     }
     if (!dataloader) {
+        LOG(ERROR) << "DataLoader is null: " << status.toString8();
         return false;
     }
     status = dataloader->start(mId);
     if (!status.isOk()) {
+        LOG(ERROR) << "Failed to start DataLoader: " << status.toString8();
         return false;
     }
     return true;
 }
 
-void IncrementalService::DataLoaderStub::destroy() {
-    {
-        std::unique_lock lock(mStatusMutex);
-        mDestroyRequested = true;
-    }
+bool IncrementalService::DataLoaderStub::destroy() {
     mService.mDataLoaderManager->destroyDataLoader(mId);
-
-    waitForDestroy();
+    return true;
 }
 
-bool IncrementalService::DataLoaderStub::waitForDestroy() {
-    auto now = std::chrono::steady_clock::now();
-    std::unique_lock lock(mStatusMutex);
-    return mStatusCondition.wait_until(lock, now + 60s, [this] {
-        return mStatus == IDataLoaderStatusListener::DATA_LOADER_DESTROYED;
-    });
+bool IncrementalService::DataLoaderStub::fsmStep() {
+    int currentStatus;
+    int targetStatus;
+    {
+        std::unique_lock lock(mStatusMutex);
+        currentStatus = mCurrentStatus;
+        targetStatus = mTargetStatus;
+    }
+
+    if (currentStatus == targetStatus) {
+        return true;
+    }
+
+    switch (targetStatus) {
+        case IDataLoaderStatusListener::DATA_LOADER_DESTROYED: {
+            return destroy();
+        }
+        case IDataLoaderStatusListener::DATA_LOADER_STARTED: {
+            switch (currentStatus) {
+                case IDataLoaderStatusListener::DATA_LOADER_CREATED:
+                case IDataLoaderStatusListener::DATA_LOADER_STOPPED:
+                    return start();
+            }
+            // fallthrough
+        }
+        case IDataLoaderStatusListener::DATA_LOADER_CREATED:
+            switch (currentStatus) {
+                case IDataLoaderStatusListener::DATA_LOADER_DESTROYED:
+                    return create();
+            }
+            break;
+        default:
+            LOG(ERROR) << "Invalid target status: " << targetStatus
+                       << ", current status: " << currentStatus;
+            break;
+    }
+    return false;
 }
 
 binder::Status IncrementalService::DataLoaderStub::onStatusChanged(MountId mountId, int newStatus) {
-    if (mStatus == newStatus) {
-        return binder::Status::ok();
+    {
+        std::unique_lock lock(mStatusMutex);
+        if (mCurrentStatus == newStatus) {
+            return binder::Status::ok();
+        }
+        mCurrentStatus = newStatus;
     }
 
     if (mListener) {
         mListener->onStatusChanged(mountId, newStatus);
     }
 
-    bool startRequested;
-    bool destroyRequested;
-    {
-        std::unique_lock lock(mStatusMutex);
-        if (mStatus == newStatus) {
-            return binder::Status::ok();
-        }
-
-        startRequested = mStartRequested;
-        destroyRequested = mDestroyRequested;
-
-        mStatus = newStatus;
-    }
-
-    switch (newStatus) {
-        case IDataLoaderStatusListener::DATA_LOADER_CREATED: {
-            if (startRequested) {
-                LOG(WARNING) << "Start was requested, triggering, for mount: " << mountId;
-                start();
-            }
-            break;
-        }
-        case IDataLoaderStatusListener::DATA_LOADER_DESTROYED: {
-            if (!destroyRequested) {
-                LOG(WARNING) << "DataLoader destroyed, reconnecting, for mount: " << mountId;
-                create();
-            }
-            break;
-        }
-        case IDataLoaderStatusListener::DATA_LOADER_STARTED: {
-            break;
-        }
-        case IDataLoaderStatusListener::DATA_LOADER_STOPPED: {
-            break;
-        }
-        case IDataLoaderStatusListener::DATA_LOADER_IMAGE_READY: {
-            break;
-        }
-        case IDataLoaderStatusListener::DATA_LOADER_IMAGE_NOT_READY: {
-            break;
-        }
-        case IDataLoaderStatusListener::DATA_LOADER_UNRECOVERABLE: {
-            // Nothing for now. Rely on externalListener to handle this.
-            break;
-        }
-        default: {
-            LOG(WARNING) << "Unknown data loader status: " << newStatus
-                         << " for mount: " << mountId;
-            break;
-        }
-    }
+    fsmStep();
 
     return binder::Status::ok();
 }
 
+void IncrementalService::DataLoaderStub::onDump(int fd) {
+    dprintf(fd, "\t\tdataLoader:");
+    dprintf(fd, "\t\t\tcurrentStatus: %d\n", mCurrentStatus);
+    dprintf(fd, "\t\t\ttargetStatus: %d\n", mTargetStatus);
+    dprintf(fd, "\t\t\ttargetStatusTs: %lldmcs\n",
+            (long long)(elapsedMcs(mTargetStatusTs, Clock::now())));
+    const auto& params = mParams;
+    dprintf(fd, "\t\t\tdataLoaderParams:\n");
+    dprintf(fd, "\t\t\t\ttype: %s\n", toString(params.type).c_str());
+    dprintf(fd, "\t\t\t\tpackageName: %s\n", params.packageName.c_str());
+    dprintf(fd, "\t\t\t\tclassName: %s\n", params.className.c_str());
+    dprintf(fd, "\t\t\t\targuments: %s\n", params.arguments.c_str());
+}
+
 void IncrementalService::AppOpsListener::opChanged(int32_t, const String16&) {
     incrementalService.onAppOpChanged(packageName);
 }
diff --git a/services/incremental/IncrementalService.h b/services/incremental/IncrementalService.h
index 8c79d77..8b28bac 100644
--- a/services/incremental/IncrementalService.h
+++ b/services/incremental/IncrementalService.h
@@ -171,29 +171,31 @@
     public:
         DataLoaderStub(IncrementalService& service, MountId id, DataLoaderParamsParcel&& params,
                        FileSystemControlParcel&& control,
-                       const DataLoaderStatusListener* externalListener)
-              : mService(service),
-                mId(id),
-                mParams(std::move(params)),
-                mControl(std::move(control)),
-                mListener(externalListener ? *externalListener : DataLoaderStatusListener()) {}
+                       const DataLoaderStatusListener* externalListener);
         ~DataLoaderStub();
 
-        bool create();
+        bool requestCreate();
         bool requestStart();
-        void destroy();
+        bool requestDestroy();
 
-        // accessors
+        bool waitForDestroy(Clock::duration duration = std::chrono::seconds(60));
+
+        void onDump(int fd);
+
         MountId id() const { return mId; }
         const DataLoaderParamsParcel& params() const { return mParams; }
-        int status() const { return mStatus; }
-        bool startRequested() const { return mStartRequested; }
 
     private:
         binder::Status onStatusChanged(MountId mount, int newStatus) final;
 
+        bool create();
         bool start();
-        bool waitForDestroy();
+        bool destroy();
+
+        bool setTargetStatus(int status);
+        bool waitForStatus(int status, Clock::duration duration);
+
+        bool fsmStep();
 
         IncrementalService& mService;
         MountId const mId;
@@ -203,9 +205,9 @@
 
         std::mutex mStatusMutex;
         std::condition_variable mStatusCondition;
-        int mStatus = IDataLoaderStatusListener::DATA_LOADER_DESTROYED;
-        bool mStartRequested = false;
-        bool mDestroyRequested = true;
+        int mCurrentStatus = IDataLoaderStatusListener::DATA_LOADER_DESTROYED;
+        int mTargetStatus = IDataLoaderStatusListener::DATA_LOADER_DESTROYED;
+        TimePoint mTargetStatusTs = {};
     };
     using DataLoaderStubPtr = sp<DataLoaderStub>;
 
diff --git a/services/incremental/test/IncrementalServiceTest.cpp b/services/incremental/test/IncrementalServiceTest.cpp
index f9737fe..bfe92f4 100644
--- a/services/incremental/test/IncrementalServiceTest.cpp
+++ b/services/incremental/test/IncrementalServiceTest.cpp
@@ -106,11 +106,12 @@
 class MockDataLoader : public IDataLoader {
 public:
     MockDataLoader() {
-        ON_CALL(*this, create(_, _, _, _)).WillByDefault(Return((binder::Status::ok())));
-        ON_CALL(*this, start(_)).WillByDefault(Return((binder::Status::ok())));
-        ON_CALL(*this, stop(_)).WillByDefault(Return((binder::Status::ok())));
-        ON_CALL(*this, destroy(_)).WillByDefault(Return((binder::Status::ok())));
-        ON_CALL(*this, prepareImage(_, _, _)).WillByDefault(Return((binder::Status::ok())));
+        ON_CALL(*this, create(_, _, _, _)).WillByDefault(Invoke(this, &MockDataLoader::createOk));
+        ON_CALL(*this, start(_)).WillByDefault(Invoke(this, &MockDataLoader::startOk));
+        ON_CALL(*this, stop(_)).WillByDefault(Invoke(this, &MockDataLoader::stopOk));
+        ON_CALL(*this, destroy(_)).WillByDefault(Invoke(this, &MockDataLoader::destroyOk));
+        ON_CALL(*this, prepareImage(_, _, _))
+                .WillByDefault(Invoke(this, &MockDataLoader::prepareImageOk));
     }
     IBinder* onAsBinder() override { return nullptr; }
     MOCK_METHOD4(create,
@@ -123,6 +124,57 @@
     MOCK_METHOD3(prepareImage,
                  binder::Status(int32_t id, const std::vector<InstallationFileParcel>& addedFiles,
                                 const std::vector<std::string>& removedFiles));
+
+    void initializeCreateOkNoStatus() {
+        ON_CALL(*this, create(_, _, _, _))
+                .WillByDefault(Invoke(this, &MockDataLoader::createOkNoStatus));
+    }
+
+    binder::Status createOk(int32_t id, const content::pm::DataLoaderParamsParcel&,
+                            const content::pm::FileSystemControlParcel&,
+                            const sp<content::pm::IDataLoaderStatusListener>& listener) {
+        mListener = listener;
+        if (mListener) {
+            mListener->onStatusChanged(id, IDataLoaderStatusListener::DATA_LOADER_CREATED);
+        }
+        return binder::Status::ok();
+    }
+    binder::Status createOkNoStatus(int32_t id, const content::pm::DataLoaderParamsParcel&,
+                                    const content::pm::FileSystemControlParcel&,
+                                    const sp<content::pm::IDataLoaderStatusListener>& listener) {
+        mListener = listener;
+        return binder::Status::ok();
+    }
+    binder::Status startOk(int32_t id) {
+        if (mListener) {
+            mListener->onStatusChanged(id, IDataLoaderStatusListener::DATA_LOADER_STARTED);
+        }
+        return binder::Status::ok();
+    }
+    binder::Status stopOk(int32_t id) {
+        if (mListener) {
+            mListener->onStatusChanged(id, IDataLoaderStatusListener::DATA_LOADER_STOPPED);
+        }
+        return binder::Status::ok();
+    }
+    binder::Status destroyOk(int32_t id) {
+        if (mListener) {
+            mListener->onStatusChanged(id, IDataLoaderStatusListener::DATA_LOADER_DESTROYED);
+        }
+        mListener = nullptr;
+        return binder::Status::ok();
+    }
+    binder::Status prepareImageOk(int32_t id,
+                                  const ::std::vector<content::pm::InstallationFileParcel>&,
+                                  const ::std::vector<::std::string>&) {
+        if (mListener) {
+            mListener->onStatusChanged(id, IDataLoaderStatusListener::DATA_LOADER_IMAGE_READY);
+        }
+        return binder::Status::ok();
+    }
+
+private:
+    sp<IDataLoaderStatusListener> mListener;
 };
 
 class MockDataLoaderManager : public DataLoaderManagerWrapper {
@@ -434,7 +486,7 @@
     mVold->bindMountSuccess();
     mDataLoaderManager->initializeDataLoaderFails();
     EXPECT_CALL(*mDataLoaderManager, initializeDataLoader(_, _, _, _, _)).Times(1);
-    EXPECT_CALL(*mDataLoaderManager, destroyDataLoader(_)).Times(1);
+    EXPECT_CALL(*mDataLoaderManager, destroyDataLoader(_)).Times(0);
     EXPECT_CALL(*mDataLoader, create(_, _, _, _)).Times(0);
     EXPECT_CALL(*mDataLoader, start(_)).Times(0);
     EXPECT_CALL(*mDataLoader, destroy(_)).Times(0);
@@ -462,7 +514,6 @@
             mIncrementalService->createStorage(tempDir.path, std::move(mDataLoaderParcel), {},
                                                IncrementalService::CreateOptions::CreateNew);
     ASSERT_GE(storageId, 0);
-    mDataLoaderManager->setDataLoaderStatusCreated();
     mIncrementalService->deleteStorage(storageId);
 }
 
@@ -483,7 +534,6 @@
             mIncrementalService->createStorage(tempDir.path, std::move(mDataLoaderParcel), {},
                                                IncrementalService::CreateOptions::CreateNew);
     ASSERT_GE(storageId, 0);
-    mDataLoaderManager->setDataLoaderStatusCreated();
     // Simulated crash/other connection breakage.
     mDataLoaderManager->setDataLoaderStatusDestroyed();
 }
@@ -492,6 +542,7 @@
     mVold->mountIncFsSuccess();
     mIncFs->makeFileSuccess();
     mVold->bindMountSuccess();
+    mDataLoader->initializeCreateOkNoStatus();
     mDataLoaderManager->initializeDataLoaderSuccess();
     mDataLoaderManager->getDataLoaderSuccess();
     EXPECT_CALL(*mDataLoaderManager, initializeDataLoader(_, _, _, _, _)).Times(1);
@@ -514,11 +565,12 @@
     mVold->mountIncFsSuccess();
     mIncFs->makeFileSuccess();
     mVold->bindMountSuccess();
+    mDataLoader->initializeCreateOkNoStatus();
     mDataLoaderManager->initializeDataLoaderSuccess();
     mDataLoaderManager->getDataLoaderSuccess();
-    EXPECT_CALL(*mDataLoaderManager, initializeDataLoader(_, _, _, _, _)).Times(1);
+    EXPECT_CALL(*mDataLoaderManager, initializeDataLoader(_, _, _, _, _)).Times(2);
     EXPECT_CALL(*mDataLoaderManager, destroyDataLoader(_)).Times(1);
-    EXPECT_CALL(*mDataLoader, create(_, _, _, _)).Times(1);
+    EXPECT_CALL(*mDataLoader, create(_, _, _, _)).Times(2);
     EXPECT_CALL(*mDataLoader, start(_)).Times(1);
     EXPECT_CALL(*mDataLoader, destroy(_)).Times(1);
     EXPECT_CALL(*mVold, unmountIncFs(_)).Times(2);