diff --git a/health/aidl/default/Health.cpp b/health/aidl/default/Health.cpp
index 8174bc8..37662ea 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());
 }
 
@@ -286,7 +292,7 @@
         if (!linked_callback_result.ok()) {
             return ndk::ScopedAStatus::fromStatus(-linked_callback_result.error().code());
         }
-        callbacks_.emplace_back(std::move(*linked_callback_result));
+        callbacks_[*linked_callback_result] = callback;
         // unlock
     }
 
@@ -314,12 +320,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);
 }
@@ -347,8 +365,8 @@
 void Health::OnHealthInfoChanged(const HealthInfo& health_info) {
     // Notify all callbacks
     std::unique_lock<decltype(callbacks_lock_)> lock(callbacks_lock_);
-    for (const auto& linked : callbacks_) {
-        auto res = linked->callback()->healthInfoChanged(health_info);
+    for (const auto& [_, callback] : callbacks_) {
+        auto res = callback->healthInfoChanged(health_info);
         if (!res.isOk()) {
             LOG(DEBUG) << "Cannot call healthInfoChanged:" << res.getDescription()
                        << ". Do nothing here if callback is dead as it will be cleaned up later.";
diff --git a/health/aidl/default/LinkedCallback.cpp b/health/aidl/default/LinkedCallback.cpp
index 26e99f9..df471a3 100644
--- a/health/aidl/default/LinkedCallback.cpp
+++ b/health/aidl/default/LinkedCallback.cpp
@@ -24,35 +24,24 @@
 
 namespace aidl::android::hardware::health {
 
-::android::base::Result<std::unique_ptr<LinkedCallback>> LinkedCallback::Make(
+::android::base::Result<LinkedCallback*> LinkedCallback::Make(
         std::shared_ptr<Health> service, std::shared_ptr<IHealthInfoCallback> callback) {
-    std::unique_ptr<LinkedCallback> ret(new LinkedCallback());
+    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 ::android::base::Error(-linkRet);
     }
     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 da494c9..8c9c997 100644
--- a/health/aidl/default/LinkedCallback.h
+++ b/health/aidl/default/LinkedCallback.h
@@ -32,19 +32,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 ::android::base::Result<std::unique_ptr<LinkedCallback>> Make(
+    // The deathRecipient owns the LinkedCallback object and will delete it with
+    // cookie when it's unlinked.
+    static ::android::base::Result<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_; }
-
     // On callback died, unreigster it from the service.
     void OnCallbackDied();
 
@@ -55,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