Add a SiteEngagementEvictionPolicy.

chrome/browser/engagement/site_engagement_eviction_policy.cc

Index: chrome/browser/engagement/site_engagement_eviction_policy.cc
diff --git a/chrome/browser/engagement/site_engagement_eviction_policy.cc b/chrome/browser/engagement/site_engagement_eviction_policy.cc
new file mode 100644
index 0000000000000000000000000000000000000000..36ff260cbffe83c47328af819cc79d034f3be589
--- /dev/null
+++ b/chrome/browser/engagement/site_engagement_eviction_policy.cc
@@ -0,0 +1,74 @@
+// Copyright 2015 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 "chrome/browser/engagement/site_engagement_eviction_policy.h"
+#include "chrome/browser/engagement/site_engagement_service.h"
+#include "content/public/browser/browser_thread.h"
+
+namespace {
+const int kExpectedEngagementSites = 200;
+}  // namespace
+
+SiteEngagementEvictionPolicy::SiteEngagementEvictionPolicy(
+    SiteEngagementService* service)
+    : engagement_service_(service) {
+}
+SiteEngagementEvictionPolicy::~SiteEngagementEvictionPolicy() {
+}
+
+GURL SiteEngagementEvictionPolicy::GetEvictionOriginOnUIThread(
+    const std::map<GURL, int64>& usage_map,
+    int64 global_quota) {
+  GURL origin_to_evict;
+  int total_engagement_points = GetTotalEngagementPoints();
+  int64 max_overuse = std::numeric_limits<int64>::min();
+  for (auto usage : usage_map) {

[raymes, 2015/07/08 04:43:29]

const auto& usage

[calamity, 2015/07/10 05:05:05]

Done.

+    int64 overuse =

[raymes, 2015/07/21 03:16:00]

hmm overuse sort of implies that this will always be positive, but that's not
the case. It's sort of the usage relative to the quota. But I can't think of
better terminology here so overuse is probably fine :) Perhaps note this in a
comment

[calamity, 2015/07/21 04:57:09]

Done.

+        usage.second - GetSoftQuotaForOrigin(usage.first, global_quota,
+                                             total_engagement_points);
+    if (overuse > max_overuse) {
+      max_overuse = overuse;
+      origin_to_evict = usage.first;
+    }
+  }
+  return origin_to_evict;

[raymes, 2015/07/08 04:43:29]

As discussed offline, this is a heuristic but I think it should make it clear
what we're trying to optimise for (either by code or in comment) because then if
someone wanted to write a better heuristic they could. I think there are 2
things we want to optimise:
-evicting the sites that the user cares about least, first
-evicting the smallest number of sites to get under the quota limit

I think the current heuristic gives some combination of these 2 goals.

[calamity, 2015/07/10 05:05:05]

Done.

+}
+
+void SiteEngagementEvictionPolicy::GetEvictionOrigin(
+    const std::map<GURL, int64>& usage_map,
+    int64 global_quota,
+    const storage::GetEvictionOriginCallback& callback) {
+  content::BrowserThread::PostTaskAndReplyWithResult(
+      content::BrowserThread::UI, FROM_HERE,
+      base::Bind(&SiteEngagementEvictionPolicy::GetEvictionOriginOnUIThread,
+                 base::Unretained(this), usage_map, global_quota),

[raymes, 2015/07/08 04:43:29]

Are we sure this object will be alive for the life of the call?

[calamity, 2015/07/10 05:05:05]

As discussed this should be solved with a big refactor of this patch.

+      base::Bind(&SiteEngagementEvictionPolicy::ReplyWithEvictionOrigin,
+                 base::Unretained(this), callback));
+}
+
+int SiteEngagementEvictionPolicy::GetScore(const GURL& origin) {
+  return engagement_service_->GetScore(origin);
+}
+
+int SiteEngagementEvictionPolicy::GetTotalEngagementPoints() {
+  return engagement_service_->GetTotalEngagementPoints();

[raymes, 2015/07/08 04:43:29]

Did you consider making these functions virtual in SiteEngagementService (or
pulling them into an API which SiteEngagementService implements)

[calamity, 2015/07/10 05:05:05]

I did. I'm not sure how much the site engagement service will change so I don't
think it's worth pulling out a TestEngagementService quite yet. When there are
more clients and the API is more stable, it's definitely something I'll do.

Added a TODO to the header.

[raymes, 2015/07/21 03:16:00]

Ok, sounds good. I didn't notice a TODO but maybe I'm missing it :)

If the interface ends up staying the same then we should consider  it later. It
will just require adding a SiteEngementScoreMap (or something) which has those 2
functions (GetScore and GetTotal) and is implemented by the
SiteEngagementService.

[calamity, 2015/07/21 04:57:09]

This changed and there's a TestSiteEngagementService in the unit test now.

[raymes, 2015/07/21 09:22:19]

I still think we should eventually remove the virtual functions in favour of an
interface that gets implemented. Let's discuss tomorrow but this can be done in
a followup CL.

+}
+
+int64 SiteEngagementEvictionPolicy::GetSoftQuotaForOrigin(
+    const GURL& origin,
+    int64 global_quota,
+    int total_engagement_points) {
+  double quota_per_point =

[raymes, 2015/07/08 04:43:29]

Out of curiosity, what units is quota? I would guess something like bytes or kb
which should be fine. I was just worried that quota_per_point might be very
small, in which case we could re-arrange the multiplications/divisions to get
better accuracy, but I don't think that should be the case.

[calamity, 2015/07/10 05:05:05]

Bytes. Do you think that it's worth doing this anyway?

+      global_quota /
+      std::max(kExpectedEngagementSites * SiteEngagementScore::kMaxPoints,

[raymes, 2015/07/08 04:43:29]

Hmm, what is kExpectedEngagementSites exactly? Is this the max number of sites
that we expect to have quota?

[calamity, 2015/07/10 05:05:05]

It's a reasonable minimum. This is there so that the overuse value is still
meaningful if the user has only visited a few sites. Otherwise the soft quota
would be very large and engagement wouldn't affect the overuse metric as much.

We may just want a maximum and minimum for quota_per_point to achieve the same
goal...

[raymes, 2015/07/21 03:16:00]

Hmm say the number of points was 3 and site A had 2 points and site B had 1.
Global quota = 100GB. That would mean that A would have a soft quota of 66GB and
B of 33GB. Their usage wouldn't affect their overuse very much because it's
presumably small. Is this what we're trying to protect against? The problem in
my mind right now is that if there is sufficiently large disk space relative to
the total number of points then we will always have this problem. So perhaps the
minimum number of points should be relative to the global quota? (though I
haven't done my maths on this so I don't know if it would fix all the problems
:)

What if we (for some reason) end up with a very large number of points relative
to the global quota. I think this would mean that usage would have a relatively
large affect on overuse (the reverse case) is that true? Is that something we
want to protect against too? Hmm.. 

Were these cases considered in the design doc? It could be something worth
documenting because it seems tricky! :)

[calamity, 2015/07/21 04:57:09]

Yeah, this was definitely something I was thinking about a bit. I think we can
just forge ahead with this basic algorithm for now and do a small amount of math
later and account for these cases. I don't want to jam this largely structural
CL chock full of heuristics and tests for those sorts of corner cases.

+               static_cast<double>(total_engagement_points));
+
+  return GetScore(origin) * quota_per_point;
+}
+
+void SiteEngagementEvictionPolicy::ReplyWithEvictionOrigin(
+    const storage::GetEvictionOriginCallback& callback,
+    const GURL& origin_to_evict) {
+  callback.Run(origin_to_evict);

[raymes, 2015/07/08 04:43:29]

We should be able to pull this out into a function in the anonymous namespace
above :)

[calamity, 2015/07/10 05:05:05]

Done.

+}