diff --git a/health/aidl/default/Health.cpp b/health/aidl/default/Health.cpp
index f401643..f485e54 100644
--- a/health/aidl/default/Health.cpp
+++ b/health/aidl/default/Health.cpp
@@ -36,6 +36,11 @@
     LinkedCallback* linked = reinterpret_cast<LinkedCallback*>(cookie);
     linked->OnCallbackDied();
 }
+// Delete the owned cookie.
+void onCallbackUnlinked(void* cookie) {
+    LinkedCallback* linked = reinterpret_cast<LinkedCallback*>(cookie);
+    delete linked;
+}
 }  // namespace
 
 /*
@@ -57,6 +62,7 @@
     : instance_name_(instance_name),
       healthd_config_(std::move(config)),
       death_recipient_(AIBinder_DeathRecipient_new(&OnCallbackDiedWrapped)) {
+    AIBinder_DeathRecipient_setOnUnlinked(death_recipient_.get(), onCallbackUnlinked);
     battery_monitor_.init(healthd_config_.get());
 }
 
@@ -272,7 +278,11 @@
 
     {
         std::lock_guard<decltype(callbacks_lock_)> lock(callbacks_lock_);
-        callbacks_.emplace_back(LinkedCallback::Make(ref<Health>(), callback));
+        LinkedCallback* linked_callback_result = LinkedCallback::Make(ref<Health>(), callback);
+        if (!linked_callback_result) {
+            return ndk::ScopedAStatus::fromStatus(STATUS_UNEXPECTED_NULL);
+        }
+        callbacks_[linked_callback_result] = callback;
         // unlock
     }
 
@@ -298,12 +308,24 @@
 
     std::lock_guard<decltype(callbacks_lock_)> lock(callbacks_lock_);
 
-    auto matches = [callback](const auto& linked) {
-        return linked->callback()->asBinder() == callback->asBinder();  // compares binder object
+    auto matches = [callback](const auto& cb) {
+        return cb->asBinder() == callback->asBinder();  // compares binder object
     };
-    auto it = std::remove_if(callbacks_.begin(), callbacks_.end(), matches);
-    bool removed = (it != callbacks_.end());
-    callbacks_.erase(it, callbacks_.end());  // calls unlinkToDeath on deleted callbacks.
+    bool removed = false;
+    for (auto it = callbacks_.begin(); it != callbacks_.end();) {
+        if (it->second->asBinder() == callback->asBinder()) {
+            auto status = AIBinder_unlinkToDeath(callback->asBinder().get(), death_recipient_.get(),
+                                                 reinterpret_cast<void*>(it->first));
+            if (status != STATUS_OK && status != STATUS_DEAD_OBJECT) {
+                LOG(WARNING) << __func__
+                             << "Cannot unlink to death: " << ::android::statusToString(status);
+            }
+            it = callbacks_.erase(it);
+            removed = true;
+        } else {
+            it++;
+        }
+    }
     return removed ? ndk::ScopedAStatus::ok()
                    : ndk::ScopedAStatus::fromExceptionCode(EX_ILLEGAL_ARGUMENT);
 }
@@ -331,13 +353,20 @@
 void Health::OnHealthInfoChanged(const HealthInfo& health_info) {
     // Notify all callbacks
     std::unique_lock<decltype(callbacks_lock_)> lock(callbacks_lock_);
-    // is_dead notifies a callback and return true if it is dead.
-    auto is_dead = [&](const auto& linked) {
-        auto res = linked->callback()->healthInfoChanged(health_info);
-        return IsDeadObjectLogged(res);
-    };
-    auto it = std::remove_if(callbacks_.begin(), callbacks_.end(), is_dead);
-    callbacks_.erase(it, callbacks_.end());  // calls unlinkToDeath on deleted callbacks.
+    for (auto it = callbacks_.begin(); it != callbacks_.end();) {
+        auto res = it->second->healthInfoChanged(health_info);
+        if (IsDeadObjectLogged(res)) {
+            // if it's dead, remove it
+            it = callbacks_.erase(it);
+        } else {
+            it++;
+            if (!res.isOk()) {
+                LOG(DEBUG)
+                        << "Cannot call healthInfoChanged:" << res.getDescription()
+                        << ". Do nothing here if callback is dead as it will be cleaned up later.";
+            }
+        }
+    }
     lock.unlock();
 
     // Let HalHealthLoop::OnHealthInfoChanged() adjusts uevent / wakealarm periods
diff --git a/health/aidl/default/LinkedCallback.cpp b/health/aidl/default/LinkedCallback.cpp
index 2985ffe..12a8df3 100644
--- a/health/aidl/default/LinkedCallback.cpp
+++ b/health/aidl/default/LinkedCallback.cpp
@@ -24,35 +24,24 @@
 
 namespace aidl::android::hardware::health {
 
-std::unique_ptr<LinkedCallback> LinkedCallback::Make(
-        std::shared_ptr<Health> service, std::shared_ptr<IHealthInfoCallback> callback) {
-    std::unique_ptr<LinkedCallback> ret(new LinkedCallback());
+LinkedCallback* LinkedCallback::Make(std::shared_ptr<Health> service,
+                                     std::shared_ptr<IHealthInfoCallback> callback) {
+    LinkedCallback* ret(new LinkedCallback());
+    // pass ownership of this object to the death recipient
     binder_status_t linkRet =
             AIBinder_linkToDeath(callback->asBinder().get(), service->death_recipient_.get(),
-                                 reinterpret_cast<void*>(ret.get()));
+                                 reinterpret_cast<void*>(ret));
     if (linkRet != ::STATUS_OK) {
         LOG(WARNING) << __func__ << "Cannot link to death: " << linkRet;
         return nullptr;
     }
     ret->service_ = service;
-    ret->callback_ = std::move(callback);
+    ret->callback_ = callback;
     return ret;
 }
 
 LinkedCallback::LinkedCallback() = default;
 
-LinkedCallback::~LinkedCallback() {
-    if (callback_ == nullptr) {
-        return;
-    }
-    auto status =
-            AIBinder_unlinkToDeath(callback_->asBinder().get(), service()->death_recipient_.get(),
-                                   reinterpret_cast<void*>(this));
-    if (status != STATUS_OK && status != STATUS_DEAD_OBJECT) {
-        LOG(WARNING) << __func__ << "Cannot unlink to death: " << ::android::statusToString(status);
-    }
-}
-
 std::shared_ptr<Health> LinkedCallback::service() {
     auto service_sp = service_.lock();
     CHECK_NE(nullptr, service_sp);
@@ -60,7 +49,10 @@
 }
 
 void LinkedCallback::OnCallbackDied() {
-    service()->unregisterCallback(callback_);
+    auto sCb = callback_.lock();
+    if (sCb) {
+        service()->unregisterCallback(sCb);
+    }
 }
 
 }  // namespace aidl::android::hardware::health
diff --git a/health/aidl/default/LinkedCallback.h b/health/aidl/default/LinkedCallback.h
index 82490a7..0494921 100644
--- a/health/aidl/default/LinkedCallback.h
+++ b/health/aidl/default/LinkedCallback.h
@@ -31,18 +31,10 @@
 class LinkedCallback {
   public:
     // Automatically linkToDeath upon construction with the returned object as the cookie.
-    // service->death_reciepient() should be from CreateDeathRecipient().
-    // Not using a strong reference to |service| to avoid circular reference. The lifetime
-    // of |service| must be longer than this LinkedCallback object.
-    static std::unique_ptr<LinkedCallback> Make(std::shared_ptr<Health> service,
-                                                std::shared_ptr<IHealthInfoCallback> callback);
-
-    // Automatically unlinkToDeath upon destruction. So, it is always safe to reinterpret_cast
-    // the cookie back to the LinkedCallback object.
-    ~LinkedCallback();
-
-    // The wrapped IHealthInfoCallback object.
-    const std::shared_ptr<IHealthInfoCallback>& callback() const { return callback_; }
+    // The deathRecipient owns the LinkedCallback object and will delete it with
+    // cookie when it's unlinked.
+    static LinkedCallback* Make(std::shared_ptr<Health> service,
+                                std::shared_ptr<IHealthInfoCallback> callback);
 
     // On callback died, unreigster it from the service.
     void OnCallbackDied();
@@ -54,7 +46,7 @@
     std::shared_ptr<Health> service();
 
     std::weak_ptr<Health> service_;
-    std::shared_ptr<IHealthInfoCallback> callback_;
+    std::weak_ptr<IHealthInfoCallback> callback_;
 };
 
 }  // namespace aidl::android::hardware::health
diff --git a/health/aidl/default/include/health-impl/Health.h b/health/aidl/default/include/health-impl/Health.h
index dc3a0ef..429ae2a 100644
--- a/health/aidl/default/include/health-impl/Health.h
+++ b/health/aidl/default/include/health-impl/Health.h
@@ -16,6 +16,7 @@
 
 #pragma once
 
+#include <map>
 #include <memory>
 #include <optional>
 
@@ -112,7 +113,7 @@
     ndk::ScopedAIBinder_DeathRecipient death_recipient_;
     int binder_fd_ = -1;
     std::mutex callbacks_lock_;
-    std::vector<std::unique_ptr<LinkedCallback>> callbacks_;
+    std::map<LinkedCallback*, std::shared_ptr<IHealthInfoCallback>> callbacks_;
 };
 
 }  // namespace aidl::android::hardware::health