Reporting: Cap number of clients in cache.

net/reporting/reporting_cache.cc

 // Copyright 2017 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/reporting/reporting_cache.h"
 
 #include <map>
 #include <memory>
 #include <set>
 #include <string>
 #include <vector>
 
 #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"
 #include "net/reporting/reporting_report.h"
 #include "url/gurl.h"
 
 namespace net {
 
 namespace {
 
@@ skipping 159 matching lines @@
   }
 }
 
 void ReportingCache::SetClient(const url::Origin& origin,
                                const GURL& endpoint,
                                ReportingClient::Subdomains subdomains,
                                const std::string& group,
                                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();
+
+  const ReportingClient* old_client =
+      GetClientByOriginAndEndpoint(origin, endpoint);
+  if (old_client) {
+    last_used = client_last_used_[old_client];
+    RemoveClient(old_client);
   }

[shivanisha, 2017/05/03 19:00:00]

May be not have old_client here at all.
AddClient can then use [] operator to add the client which will make sure to
replace if it exists and insert if it doesn't.
You can also then remove the DCHECK(!old_client) in line 213. To me it seems
simpler to follow unless we are losing anything with this approach?

[Julia Tuttle, 2017/05/04 16:50:21]

There's more going on in RemoveClient than just removing the client; it also has
to remove it from the wildcard index and last used map. We don't *need* the
DCHECK on line 213, though -- it was just a sanity check.

[shivanisha, 2017/05/05 19:24:48]

Acknowledged.

 
-  clients_[origin][endpoint] = base::MakeUnique<ReportingClient>(
-      origin, endpoint, subdomains, group, expires);
+  AddClient(base::MakeUnique<ReportingClient>(origin, endpoint, subdomains,
+                                              group, expires),
+            last_used);
 
-  MaybeAddWildcardClient(clients_[origin][endpoint].get());
+  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(FindClientToEvict(tick_clock()->NowTicks()));

[shivanisha, 2017/05/03 19:00:00]

RemoveClient(to_evict)?

[Julia Tuttle, 2017/05/04 16:50:22]

...oops, done.

+  }
 
   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();
 }
 
 const ReportingReport* ReportingCache::FindReportToEvict() const {
   const ReportingReport* earliest_queued = nullptr;
 
   for (const auto& it : reports_) {
     const ReportingReport* report = it.first;
     if (base::ContainsKey(pending_reports_, report))
       continue;
     if (!earliest_queued || report->queued < earliest_queued->queued) {
       earliest_queued = report;
     }
   }
 
   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(
     const std::string& domain,
     const std::string& group,
     std::vector<const ReportingClient*>* clients_out) const {
   clients_out->clear();
 
   auto it = wildcard_clients_.find(domain);
   if (it == wildcard_clients_.end())
     return;
 
   for (const ReportingClient* client : it->second) {
     DCHECK_EQ(ReportingClient::Subdomains::INCLUDE, client->subdomains);
     if (client->group == group)
       clients_out->push_back(client);
   }
 }
 
+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_) {

[shivanisha, 2017/05/03 19:00:00]

How does this ensure that clients which have pending reports are not evicted?

[Julia Tuttle, 2017/05/04 16:50:21]

It doesn't! The cache has no understanding of the relationship between reports
and clients.

I'm not sure if I should be worried about this; for sites that regularly send
reports, LRU will keep them from being evicted, but for sites that don't,
there's no way to know which clients will be needed later when picking one to
evict.

[shivanisha, 2017/05/05 19:24:48]

Can we map the elements in pending_reports_ to the client they are going to be
sent to? If yes, then we can avoid evicting those clients.

[Julia Tuttle, 2017/05/08 14:15:55]

We could do that, but that would make evicting a client an
O(num_clients*num_pending_reports) operation. I'd rather just keep a set of
pending clients as well.

Really, though, I'm not sure what protecting pending clients gains us over just
updating the LRU timestamp when we start a delivery attempt -- if the cache is
that crowded, we're going to need to evict something, and we don't actually *do*
anything with the client when the delivery attempt finishes.

+    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