diff --git a/transport/HidlTransportSupport.cpp b/transport/HidlTransportSupport.cpp
index d0871f6..9c2bf25 100644
--- a/transport/HidlTransportSupport.cpp
+++ b/transport/HidlTransportSupport.cpp
@@ -58,7 +58,23 @@
         return false;
     }
 
-    details::gServicePrioMap.set(service, { policy, priority });
+    // Due to ABI considerations, IBase cannot have a destructor to clean this up.
+    // So, because this API is so infrequently used, (expected to be usually only
+    // one time for a process, but it can be more), we are cleaning it up here.
+    // TODO(b/37794345): if ever we update the HIDL ABI for launches in an Android
+    // release in the meta-version sense, we should remove this.
+    std::unique_lock<std::mutex> lock = details::gServicePrioMap.lock();
+
+    std::vector<wp<::android::hidl::base::V1_0::IBase>> toDelete;
+    for (const auto& kv : details::gServicePrioMap) {
+        if (kv.first.promote() == nullptr) {
+            toDelete.push_back(kv.first);
+        }
+    }
+    for (const auto& k : toDelete) {
+        details::gServicePrioMap.eraseLocked(k);
+    }
+    details::gServicePrioMap.setLocked(service, {policy, priority});
 
     return true;
 }
diff --git a/transport/include/hidl/ConcurrentMap.h b/transport/include/hidl/ConcurrentMap.h
index 4066869..54c1a32 100644
--- a/transport/include/hidl/ConcurrentMap.h
+++ b/transport/include/hidl/ConcurrentMap.h
@@ -76,6 +76,14 @@
         return iter->second;
     }
 
+    size_type eraseLocked(const K& k) { return mMap.erase(k); }
+
+    // the concurrent map must be locked in order to iterate over it
+    iterator begin() { return mMap.begin(); }
+    iterator end() { return mMap.end(); }
+    const_iterator begin() const { return mMap.begin(); }
+    const_iterator end() const { return mMap.end(); }
+
    private:
     mutable std::mutex mMutex;
     std::map<K, V> mMap;