Reporting: Cap number of clients in cache.

net/reporting/reporting_cache.cc

Index: net/reporting/reporting_cache.cc
diff --git a/net/reporting/reporting_cache.cc b/net/reporting/reporting_cache.cc
index 7e147b38008a390266e047ab20ce457c2a012697..24eea0e87518e50f0ec5cda9b5a1e0f498b2dfa7 100644
--- a/net/reporting/reporting_cache.cc
+++ b/net/reporting/reporting_cache.cc
@@ -12,6 +12,7 @@
 
 #include "base/memory/ptr_util.h"
 #include "base/stl_util.h"
+#include "base/time/tick_clock.h"
 #include "base/time/time.h"
 #include "net/reporting/reporting_client.h"
 #include "net/reporting/reporting_context.h"
@@ -191,56 +192,77 @@ void ReportingCache::SetClient(const url::Origin& origin,
                                base::TimeTicks expires) {
   DCHECK(endpoint.SchemeIsCryptographic());
 
-  // Since |subdomains| may differ from a previous call to SetClient for this
-  // origin and endpoint, the cache needs to remove and re-add the client to the
-  // index of wildcard clients, if applicable.
-  if (base::ContainsKey(clients_, origin) &&
-      base::ContainsKey(clients_[origin], endpoint)) {
-    MaybeRemoveWildcardClient(clients_[origin][endpoint].get());
-  }
+  base::TimeTicks last_used = tick_clock()->NowTicks();
 
-  clients_[origin][endpoint] = base::MakeUnique<ReportingClient>(
-      origin, endpoint, subdomains, group, expires);
+  const ReportingClient* old_client =
+      GetClientByOriginAndEndpoint(origin, endpoint);
+  if (old_client) {
+    last_used = client_last_used_[old_client];
+    RemoveClient(old_client);
+  }
 
-  MaybeAddWildcardClient(clients_[origin][endpoint].get());
+  AddClient(base::MakeUnique<ReportingClient>(origin, endpoint, subdomains,
+                                              group, expires),
+            last_used);
+
+  if (client_last_used_.size() > context_->policy().max_client_count) {
+    // There should only ever be one extra client, added above.
+    DCHECK_EQ(context_->policy().max_client_count + 1,
+              client_last_used_.size());
+    // And that shouldn't happen if it was replaced, not added.
+    DCHECK(!old_client);
+    const ReportingClient* to_evict =
+        FindClientToEvict(tick_clock()->NowTicks());
+    DCHECK(to_evict);
+    RemoveClient(to_evict);
+  }
 
   context_->NotifyCacheUpdated();
 }
 
+void ReportingCache::MarkClientUsed(const url::Origin& origin,
+                                    const GURL& endpoint) {
+  const ReportingClient* client =
+      GetClientByOriginAndEndpoint(origin, endpoint);
+  DCHECK(client);
+  client_last_used_[client] = tick_clock()->NowTicks();
+}
+
 void ReportingCache::RemoveClients(
     const std::vector<const ReportingClient*>& clients_to_remove) {
-  for (const ReportingClient* client : clients_to_remove) {
-    MaybeRemoveWildcardClient(client);
-    size_t erased = clients_[client->origin].erase(client->endpoint);
-    DCHECK_EQ(1u, erased);
-  }
+  for (const ReportingClient* client : clients_to_remove)
+    RemoveClient(client);
 
   context_->NotifyCacheUpdated();
 }
 
 void ReportingCache::RemoveClientForOriginAndEndpoint(const url::Origin& origin,
                                                       const GURL& endpoint) {
-  MaybeRemoveWildcardClient(clients_[origin][endpoint].get());
-  size_t erased = clients_[origin].erase(endpoint);
-  DCHECK_EQ(1u, erased);
+  const ReportingClient* client =
+      GetClientByOriginAndEndpoint(origin, endpoint);
+  RemoveClient(client);
 
   context_->NotifyCacheUpdated();
 }
 
 void ReportingCache::RemoveClientsForEndpoint(const GURL& endpoint) {
-  for (auto& origin_and_endpoints : clients_) {
-    if (base::ContainsKey(origin_and_endpoints.second, endpoint)) {
-      MaybeRemoveWildcardClient(origin_and_endpoints.second[endpoint].get());
-      origin_and_endpoints.second.erase(endpoint);
-    }
-  }
+  std::vector<const ReportingClient*> clients_to_remove;
 
-  context_->NotifyCacheUpdated();
+  for (auto& origin_and_endpoints : clients_)
+    if (base::ContainsKey(origin_and_endpoints.second, endpoint))
+      clients_to_remove.push_back(origin_and_endpoints.second[endpoint].get());
+
+  for (const ReportingClient* client : clients_to_remove)
+    RemoveClient(client);
+
+  if (!clients_to_remove.empty())
+    context_->NotifyCacheUpdated();
 }
 
 void ReportingCache::RemoveAllClients() {
   clients_.clear();
   wildcard_clients_.clear();
+  client_last_used_.clear();
 
   context_->NotifyCacheUpdated();
 }
@@ -260,22 +282,68 @@ const ReportingReport* ReportingCache::FindReportToEvict() const {
   return earliest_queued;
 }
 
-void ReportingCache::MaybeAddWildcardClient(const ReportingClient* client) {
-  if (client->subdomains != ReportingClient::Subdomains::INCLUDE)
-    return;
+void ReportingCache::AddClient(std::unique_ptr<ReportingClient> client,
+                               base::TimeTicks last_used) {
+  DCHECK(client);
 
-  const std::string& domain = client->origin.host();
-  auto inserted = wildcard_clients_[domain].insert(client);
-  DCHECK(inserted.second);
+  url::Origin origin = client->origin;
+  GURL endpoint = client->endpoint;
+
+  auto inserted_last_used =
+      client_last_used_.insert(std::make_pair(client.get(), last_used));
+  DCHECK(inserted_last_used.second);
+
+  if (client->subdomains == ReportingClient::Subdomains::INCLUDE) {
+    const std::string& domain = origin.host();
+    auto inserted_wildcard_client =
+        wildcard_clients_[domain].insert(client.get());
+    DCHECK(inserted_wildcard_client.second);
+  }
+
+  auto inserted_client =
+      clients_[origin].insert(std::make_pair(endpoint, std::move(client)));
+  DCHECK(inserted_client.second);
 }
 
-void ReportingCache::MaybeRemoveWildcardClient(const ReportingClient* client) {
-  if (client->subdomains != ReportingClient::Subdomains::INCLUDE)
-    return;
+void ReportingCache::RemoveClient(const ReportingClient* client) {
+  DCHECK(client);
 
-  const std::string& domain = client->origin.host();
-  size_t erased = wildcard_clients_[domain].erase(client);
-  DCHECK_EQ(1u, erased);
+  url::Origin origin = client->origin;
+  GURL endpoint = client->endpoint;
+
+  if (client->subdomains == ReportingClient::Subdomains::INCLUDE) {
+    const std::string& domain = origin.host();
+    size_t erased_wildcard_client = wildcard_clients_[domain].erase(client);
+    DCHECK_EQ(1u, erased_wildcard_client);
+    if (wildcard_clients_[domain].empty()) {
+      size_t erased_wildcard_domain = wildcard_clients_.erase(domain);
+      DCHECK_EQ(1u, erased_wildcard_domain);
+    }
+  }
+
+  size_t erased_last_used = client_last_used_.erase(client);
+  DCHECK_EQ(1u, erased_last_used);
+
+  size_t erased_endpoint = clients_[origin].erase(endpoint);
+  DCHECK_EQ(1u, erased_endpoint);
+  if (clients_[origin].empty()) {
+    size_t erased_origin = clients_.erase(origin);
+    DCHECK_EQ(1u, erased_origin);
+  }
+}
+
+const ReportingClient* ReportingCache::GetClientByOriginAndEndpoint(
+    const url::Origin& origin,
+    const GURL& endpoint) const {
+  const auto& origin_it = clients_.find(origin);
+  if (origin_it == clients_.end())
+    return nullptr;
+
+  const auto& endpoint_it = origin_it->second.find(endpoint);
+  if (endpoint_it == origin_it->second.end())
+    return nullptr;
+
+  return endpoint_it->second.get();
 }
 
 void ReportingCache::GetWildcardClientsForDomainAndGroup(
@@ -295,4 +363,37 @@ void ReportingCache::GetWildcardClientsForDomainAndGroup(
   }
 }
 
+const ReportingClient* ReportingCache::FindClientToEvict(
+    base::TimeTicks now) const {
+  DCHECK(!client_last_used_.empty());
+
+  const ReportingClient* earliest_used = nullptr;
+  base::TimeTicks earliest_used_last_used;
+  const ReportingClient* earliest_expired = nullptr;
+
+  for (const auto& it : client_last_used_) {
+    const ReportingClient* client = it.first;
+    base::TimeTicks client_last_used = it.second;
+    if (earliest_used == nullptr ||
+        client_last_used < earliest_used_last_used) {
+      earliest_used = client;
+      earliest_used_last_used = client_last_used;
+    }
+    if (earliest_expired == nullptr ||
+        client->expires < earliest_expired->expires) {
+      earliest_expired = client;
+    }
+  }
+
+  // If there are expired clients, return the earliest-expired.
+  if (earliest_expired->expires < now)
+    return earliest_expired;
+  else
+    return earliest_used;
+}
+
+base::TickClock* ReportingCache::tick_clock() {
+  return context_->tick_clock();
+}
+
 }  // namespace net