diff --git a/cmds/servicemanager/ServiceManager.cpp b/cmds/servicemanager/ServiceManager.cpp
index ae74ac3..abe6436 100644
--- a/cmds/servicemanager/ServiceManager.cpp
+++ b/cmds/servicemanager/ServiceManager.cpp
@@ -423,11 +423,12 @@
 
 void ServiceManager::handleClientCallbacks() {
     for (const auto& [name, service] : mNameToService) {
-        handleServiceClientCallback(name);
+        handleServiceClientCallback(name, true);
     }
 }
 
-ssize_t ServiceManager::handleServiceClientCallback(const std::string& serviceName) {
+ssize_t ServiceManager::handleServiceClientCallback(const std::string& serviceName,
+                                                    bool isCalledOnInterval) {
     auto serviceIt = mNameToService.find(serviceName);
     if (serviceIt == mNameToService.end() || mNameToClientCallback.count(serviceName) < 1) {
         return -1;
@@ -451,14 +452,17 @@
         service.guaranteeClient = false;
     }
 
-    if (hasClients && !service.hasClients) {
-        // client was retrieved in some other way
-        sendClientCallbackNotifications(serviceName, true);
-    }
+    // 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);
+        }
 
-    // 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;
@@ -518,7 +522,7 @@
         return Status::fromExceptionCode(Status::EX_ILLEGAL_STATE);
     }
 
-    int clients = handleServiceClientCallback(name);
+    int clients = handleServiceClientCallback(name, false);
 
     // clients < 0: feature not implemented or other error. Assume clients.
     // Otherwise:
@@ -527,7 +531,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 77f5250..a2fc5a8 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);
+    ssize_t handleServiceClientCallback(const std::string& serviceName, bool isCalledOnInterval);
      // 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 dc9482c..f064bd7 100644
--- a/libs/binder/LazyServiceRegistrar.cpp
+++ b/libs/binder/LazyServiceRegistrar.cpp
@@ -53,14 +53,13 @@
 
     struct Service {
         sp<IBinder> service;
-        std::string name;
         bool allowIsolated;
         int dumpFlags;
     };
     /**
-     * Number of services that have been registered.
+     * Map of registered names and services
      */
-    std::vector<Service> mRegisteredServices;
+    std::map<std::string, Service> mRegisteredServices;
 };
 
 bool ClientCounterCallback::registerService(const sp<IBinder>& service, const std::string& name,
@@ -68,20 +67,24 @@
     auto manager = interface_cast<AidlServiceManager>(
                     ProcessState::self()->getContextObject(nullptr));
 
-    ALOGI("Registering service %s", name.c_str());
+    bool reRegister = mRegisteredServices.count(name) > 0;
+    std::string regStr = (reRegister) ? "Re-registering" : "Registering";
+    ALOGI("%s service %s", regStr.c_str(), 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;
     }
 
-    mRegisteredServices.push_back({service, name, allowIsolated, dumpFlags});
+    if (!reRegister) {
+        // Only add this when a service is added for the first time, as it is not removed
+        mRegisteredServices[name] = {service, allowIsolated, dumpFlags};
+    }
 
     return true;
 }
@@ -119,10 +122,11 @@
     for (; unRegisterIt != mRegisteredServices.end(); ++unRegisterIt) {
         auto& entry = (*unRegisterIt);
 
-        bool success = manager->tryUnregisterService(entry.name, entry.service).isOk();
+        bool success = manager->tryUnregisterService(entry.first, entry.second.service).isOk();
+
 
         if (!success) {
-            ALOGI("Failed to unregister service %s", entry.name.c_str());
+            ALOGI("Failed to unregister service %s", entry.first.c_str());
             break;
         }
     }
@@ -137,7 +141,8 @@
         auto& entry = (*reRegisterIt);
 
         // re-register entry
-        if (!registerService(entry.service, entry.name, entry.allowIsolated, entry.dumpFlags)) {
+        if (!registerService(entry.second.service, entry.first, entry.second.allowIsolated,
+                             entry.second.dumpFlags)) {
             // Must restart. Otherwise, clients will never be able to get a hold of this service.
             ALOGE("Bad state: could not re-register services");
         }