diff --git a/cmds/servicemanager/ServiceManager.cpp b/cmds/servicemanager/ServiceManager.cpp
index abe6436..ae74ac3 100644
--- a/cmds/servicemanager/ServiceManager.cpp
+++ b/cmds/servicemanager/ServiceManager.cpp
@@ -423,12 +423,11 @@
 
 void ServiceManager::handleClientCallbacks() {
     for (const auto& [name, service] : mNameToService) {
-        handleServiceClientCallback(name, true);
+        handleServiceClientCallback(name);
     }
 }
 
-ssize_t ServiceManager::handleServiceClientCallback(const std::string& serviceName,
-                                                    bool isCalledOnInterval) {
+ssize_t ServiceManager::handleServiceClientCallback(const std::string& serviceName) {
     auto serviceIt = mNameToService.find(serviceName);
     if (serviceIt == mNameToService.end() || mNameToClientCallback.count(serviceName) < 1) {
         return -1;
@@ -452,17 +451,14 @@
         service.guaranteeClient = false;
     }
 
-    // only send notifications if this was called via the interval checking workflow
-    if (isCalledOnInterval) {
-        if (hasClients && !service.hasClients) {
-            // client was retrieved in some other way
-            sendClientCallbackNotifications(serviceName, true);
-        }
+    if (hasClients && !service.hasClients) {
+        // client was retrieved in some other way
+        sendClientCallbackNotifications(serviceName, true);
+    }
 
-        // there are no more clients, but the callback has not been called yet
-        if (!hasClients && service.hasClients) {
-            sendClientCallbackNotifications(serviceName, false);
-        }
+    // there are no more clients, but the callback has not been called yet
+    if (!hasClients && service.hasClients) {
+        sendClientCallbackNotifications(serviceName, false);
     }
 
     return count;
@@ -522,7 +518,7 @@
         return Status::fromExceptionCode(Status::EX_ILLEGAL_STATE);
     }
 
-    int clients = handleServiceClientCallback(name, false);
+    int clients = handleServiceClientCallback(name);
 
     // clients < 0: feature not implemented or other error. Assume clients.
     // Otherwise:
@@ -531,7 +527,7 @@
     // So, if clients > 2, then at least one other service on the system must hold a refcount.
     if (clients < 0 || clients > 2) {
         // client callbacks are either disabled or there are other clients
-        LOG(INFO) << "Tried to unregister " << name << ", but there are clients: " << clients;
+        LOG(INFO) << "Tried to unregister " << name << " but there are clients: " << clients;
         return Status::fromExceptionCode(Status::EX_ILLEGAL_STATE);
     }
 
diff --git a/cmds/servicemanager/ServiceManager.h b/cmds/servicemanager/ServiceManager.h
index a2fc5a8..77f5250 100644
--- a/cmds/servicemanager/ServiceManager.h
+++ b/cmds/servicemanager/ServiceManager.h
@@ -75,7 +75,7 @@
     void removeRegistrationCallback(const wp<IBinder>& who,
                         ServiceCallbackMap::iterator* it,
                         bool* found);
-    ssize_t handleServiceClientCallback(const std::string& serviceName, bool isCalledOnInterval);
+    ssize_t handleServiceClientCallback(const std::string& serviceName);
      // Also updates mHasClients (of what the last callback was)
     void sendClientCallbackNotifications(const std::string& serviceName, bool hasClients);
     // removes a callback from mNameToClientCallback, deleting the entry if the vector is empty
diff --git a/libs/binder/LazyServiceRegistrar.cpp b/libs/binder/LazyServiceRegistrar.cpp
index f064bd7..dc9482c 100644
--- a/libs/binder/LazyServiceRegistrar.cpp
+++ b/libs/binder/LazyServiceRegistrar.cpp
@@ -53,13 +53,14 @@
 
     struct Service {
         sp<IBinder> service;
+        std::string name;
         bool allowIsolated;
         int dumpFlags;
     };
     /**
-     * Map of registered names and services
+     * Number of services that have been registered.
      */
-    std::map<std::string, Service> mRegisteredServices;
+    std::vector<Service> mRegisteredServices;
 };
 
 bool ClientCounterCallback::registerService(const sp<IBinder>& service, const std::string& name,
@@ -67,24 +68,20 @@
     auto manager = interface_cast<AidlServiceManager>(
                     ProcessState::self()->getContextObject(nullptr));
 
-    bool reRegister = mRegisteredServices.count(name) > 0;
-    std::string regStr = (reRegister) ? "Re-registering" : "Registering";
-    ALOGI("%s service %s", regStr.c_str(), name.c_str());
+    ALOGI("Registering service %s", name.c_str());
 
     if (!manager->addService(name.c_str(), service, allowIsolated, dumpFlags).isOk()) {
         ALOGE("Failed to register service %s", name.c_str());
         return false;
     }
 
-    if (!manager->registerClientCallback(name, service, this).isOk()) {
-        ALOGE("Failed to add client callback for service %s", name.c_str());
-        return false;
+    if (!manager->registerClientCallback(name, service, this).isOk())
+    {
+      ALOGE("Failed to add client callback for service %s", name.c_str());
+      return false;
     }
 
-    if (!reRegister) {
-        // Only add this when a service is added for the first time, as it is not removed
-        mRegisteredServices[name] = {service, allowIsolated, dumpFlags};
-    }
+    mRegisteredServices.push_back({service, name, allowIsolated, dumpFlags});
 
     return true;
 }
@@ -122,11 +119,10 @@
     for (; unRegisterIt != mRegisteredServices.end(); ++unRegisterIt) {
         auto& entry = (*unRegisterIt);
 
-        bool success = manager->tryUnregisterService(entry.first, entry.second.service).isOk();
-
+        bool success = manager->tryUnregisterService(entry.name, entry.service).isOk();
 
         if (!success) {
-            ALOGI("Failed to unregister service %s", entry.first.c_str());
+            ALOGI("Failed to unregister service %s", entry.name.c_str());
             break;
         }
     }
@@ -141,8 +137,7 @@
         auto& entry = (*reRegisterIt);
 
         // re-register entry
-        if (!registerService(entry.second.service, entry.first, entry.second.allowIsolated,
-                             entry.second.dumpFlags)) {
+        if (!registerService(entry.service, entry.name, entry.allowIsolated, entry.dumpFlags)) {
             // Must restart. Otherwise, clients will never be able to get a hold of this service.
             ALOGE("Bad state: could not re-register services");
         }