predictors: Add origin learning.

chrome/browser/predictors/resource_prefetch_predictor.cc

 // Copyright 2014 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/predictors/resource_prefetch_predictor.h"
 
 #include <map>
 #include <set>
 #include <utility>
 
@@ skipping 17 matching lines @@
 #include "content/public/browser/web_contents.h"
 #include "net/http/http_response_headers.h"
 #include "net/url_request/url_request.h"
 
 using content::BrowserThread;
 
 namespace predictors {
 
 namespace {
 
+using OriginStat = OriginData_OriginStat;
+
 // Sorted by decreasing likelihood according to HTTP archive.
 const char* kFontMimeTypes[] = {"font/woff2",
                                 "application/x-font-woff",
                                 "application/font-woff",
                                 "application/font-woff2",
                                 "font/x-woff",
                                 "application/x-font-ttf",
                                 "font/woff",
                                 "font/ttf",
                                 "application/x-font-otf",
@@ skipping 12 matching lines @@
   REPORTING_EVENT_ALL_HISTORY_CLEARED = 0,
   REPORTING_EVENT_PARTIAL_HISTORY_CLEARED = 1,
   REPORTING_EVENT_COUNT = 2
 };
 
 float ComputeRedirectConfidence(const predictors::RedirectStat& redirect) {
   return (redirect.number_of_hits() + 0.0) /
          (redirect.number_of_hits() + redirect.number_of_misses());
 }
 
+void UpdateOrAddToSummaries(

[alexilin, 2017/04/10 14:58:27]

nit:
We have a lot of different summaries. I'd propose
s/UpdateOrAddToSummaries/UpdateOrAddToOriginSummaries
or
s/UpdateOrAddToSummaries/UpdateOrAddToOrigins

[Benoit L, 2017/04/11 09:04:05]

Done.

+    std::map<GURL, ResourcePrefetchPredictor::OriginRequestSummary>* summaries,
+    const ResourcePrefetchPredictor::URLRequestSummary& request_summary) {
+  GURL origin = request_summary.resource_url.GetOrigin();

[alexilin, 2017/04/10 14:58:28]

Do we need a check for incorrect url here?
From the description of GetOrigin(): "If this URL is not a standard URL, then
the result will be an empty, invalid GURL".

[Benoit L, 2017/04/11 09:04:05]

Given the way this code is called, this should not happen.
Added a DCHECK() and an early return nonetheless, thanks for noticing!
Done.

+  auto it = summaries->find(origin);
+  if (it == summaries->end()) {
+    ResourcePrefetchPredictor::OriginRequestSummary summary;
+    summary.origin = origin;
+    summary.first_occurrence = summaries->size();
+    it = summaries->insert({origin, summary}).first;
+  }
+
+  it->second.always_access_network |=
+      request_summary.always_revalidate || request_summary.is_no_store;
+  it->second.accessed_network |= request_summary.network_accessed;
+}
+
+void InitializeOriginStatFromOriginRequestSummary(
+    OriginStat* origin,
+    const ResourcePrefetchPredictor::OriginRequestSummary& summary) {
+  origin->set_origin(summary.origin.spec());
+  origin->set_number_of_hits(1);
+  origin->set_average_position(summary.first_occurrence + 1);
+  origin->set_always_access_network(summary.always_access_network);
+  origin->set_accessed_network(summary.accessed_network);
+}
+
 // Used to fetch the visit count for a URL from the History database.
 class GetUrlVisitCountTask : public history::HistoryDBTask {
  public:
   using URLRequestSummary = ResourcePrefetchPredictor::URLRequestSummary;
   using PageRequestSummary = ResourcePrefetchPredictor::PageRequestSummary;
   typedef base::Callback<void(size_t,  // URL visit count.
                               const PageRequestSummary&)>
       VisitInfoCallback;
 
   GetUrlVisitCountTask(std::unique_ptr<PageRequestSummary> summary,
@@ skipping 173 matching lines @@
   if (!request_info->IsMainFrame())
     return false;
 
   content::ResourceType resource_type = request_info->GetResourceType();
   return resource_type == content::RESOURCE_TYPE_MAIN_FRAME
              ? IsHandledMainPage(response)
              : IsHandledSubresource(response, resource_type);
 }
 
 // static
 bool ResourcePrefetchPredictor::ShouldRecordRedirect(

[alexilin, 2017/04/10 14:58:28]

ShouldRecordRedirect and ShouldRecordResponse are the same now. Could we merge
them? At least, call the one from other.

[Benoit L, 2017/04/11 09:04:05]

Thanks!
Done.

     net::URLRequest* response) {
   const content::ResourceRequestInfo* request_info =
       content::ResourceRequestInfo::ForRequest(response);
   if (!request_info)
     return false;
 
   if (!request_info->IsMainFrame())
     return false;
 
-  return request_info->GetResourceType() == content::RESOURCE_TYPE_MAIN_FRAME &&
-      IsHandledMainPage(response);
+  content::ResourceType resource_type = request_info->GetResourceType();
+  return resource_type == content::RESOURCE_TYPE_MAIN_FRAME
+             ? IsHandledMainPage(response)
+             : IsHandledSubresource(response, resource_type);
 }
 
 // static
 bool ResourcePrefetchPredictor::IsHandledMainPage(net::URLRequest* request) {
   const GURL& url = request->url();
   bool bad_port = !g_allow_port_in_urls && url.has_port();
   return url.SchemeIsHTTPOrHTTPS() && !bad_port;
 }
 
 // static
@@ skipping 13 matching lines @@
     return false;
 
   if (response->method() != "GET")
     return false;
 
   if (response->original_url().spec().length() >
       ResourcePrefetchPredictorTables::kMaxStringLength) {
     return false;
   }
 
-  if (!response->response_info().headers.get() || IsNoStore(response))
+  if (!response->response_info().headers.get())
     return false;
 
   return true;
 }
 
 // static
 bool ResourcePrefetchPredictor::IsHandledResourceType(
     content::ResourceType resource_type,
     const std::string& mime_type) {
   content::ResourceType actual_resource_type =
@@ skipping 14 matching lines @@
   if (resource_type == content::RESOURCE_TYPE_PREFETCH ||
       resource_type == content::RESOURCE_TYPE_SUB_RESOURCE ||
       resource_type == content::RESOURCE_TYPE_XHR) {
     return GetResourceTypeFromMimeType(mime_type,
                                        content::RESOURCE_TYPE_LAST_TYPE);
   }
   return resource_type;
 }
 
 // static
-bool ResourcePrefetchPredictor::IsNoStore(const net::URLRequest* response) {
-  if (response->was_cached())
+bool ResourcePrefetchPredictor::IsNoStore(const net::URLRequest& response) {
+  if (response.was_cached())
     return false;
 
-  const net::HttpResponseInfo& response_info = response->response_info();
+  const net::HttpResponseInfo& response_info = response.response_info();
   if (!response_info.headers.get())
     return false;
   return response_info.headers->HasHeaderValue("cache-control", "no-store");
 }
 
 // static
 content::ResourceType ResourcePrefetchPredictor::GetResourceTypeFromMimeType(
     const std::string& mime_type,
     content::ResourceType fallback) {
   if (mime_type.empty()) {
@@ skipping 49 matching lines @@
 }
 
 // static
 void ResourcePrefetchPredictor::SetAllowPortInUrlsForTesting(bool state) {
   g_allow_port_in_urls = state;
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 // ResourcePrefetchPredictor nested types.
 
+ResourcePrefetchPredictor::OriginRequestSummary::OriginRequestSummary()
+    : origin(), always_access_network(false), accessed_network(false) {}

[alexilin, 2017/04/10 14:58:28]

Initializer for |first_occurrence|?

[Benoit L, 2017/04/11 09:04:05]

Ooops... Thanks. Too bad that neither I nor the compiler catched this.
Done.

+
+ResourcePrefetchPredictor::OriginRequestSummary::OriginRequestSummary(
+    const ResourcePrefetchPredictor::OriginRequestSummary& other) = default;

[alexilin, 2017/04/10 14:58:28]

nit:
No need to fully specialize the parameter name, I guess?

[Benoit L, 2017/04/11 09:04:05]

Done.

+
+ResourcePrefetchPredictor::OriginRequestSummary::~OriginRequestSummary() {}
+
 ResourcePrefetchPredictor::URLRequestSummary::URLRequestSummary()
     : resource_type(content::RESOURCE_TYPE_LAST_TYPE),
       priority(net::IDLE),
       was_cached(false),
       has_validators(false),
-      always_revalidate(false) {}
+      always_revalidate(false),
+      is_no_store(false) {}

[alexilin, 2017/04/10 14:58:27]

Initializer for |network_accessed|?

[Benoit L, 2017/04/11 09:04:05]

Done.

 
 ResourcePrefetchPredictor::URLRequestSummary::URLRequestSummary(
-    const URLRequestSummary& other)
-    : navigation_id(other.navigation_id),
-      resource_url(other.resource_url),
-      resource_type(other.resource_type),
-      priority(other.priority),
-      mime_type(other.mime_type),
-      was_cached(other.was_cached),
-      redirect_url(other.redirect_url),
-      has_validators(other.has_validators),
-      always_revalidate(other.always_revalidate) {}
+    const URLRequestSummary& other) = default;

[alexilin, 2017/04/10 14:58:28]

Nice catch!

 
 ResourcePrefetchPredictor::URLRequestSummary::~URLRequestSummary() {
 }
 
 // static
 bool ResourcePrefetchPredictor::URLRequestSummary::SummarizeResponse(
     const net::URLRequest& request,
     URLRequestSummary* summary) {
   const content::ResourceRequestInfo* request_info =
       content::ResourceRequestInfo::ForRequest(&request);
@@ skipping 11 matching lines @@
 
   scoped_refptr<net::HttpResponseHeaders> headers =
       request.response_info().headers;
   if (headers.get()) {
     summary->has_validators = headers->HasValidators();
     // RFC 2616, section 14.9.
     summary->always_revalidate =
         headers->HasHeaderValue("cache-control", "no-cache") ||
         headers->HasHeaderValue("pragma", "no-cache") ||
         headers->HasHeaderValue("vary", "*");
+    summary->is_no_store = IsNoStore(request);
   }
+  summary->network_accessed = request.response_info().network_accessed;
   return true;
 }
 
 ResourcePrefetchPredictor::PageRequestSummary::PageRequestSummary(
     const GURL& i_main_frame_url)
     : main_frame_url(i_main_frame_url), initial_url(i_main_frame_url) {}
 
 ResourcePrefetchPredictor::PageRequestSummary::PageRequestSummary(
     const PageRequestSummary& other) = default;
 
@@ skipping 34 matching lines @@
   if (initialization_state_ != NOT_INITIALIZED)
     return;
   initialization_state_ = INITIALIZING;
 
   // Create local caches using the database as loaded.
   auto url_data_map = base::MakeUnique<PrefetchDataMap>();
   auto host_data_map = base::MakeUnique<PrefetchDataMap>();
   auto url_redirect_data_map = base::MakeUnique<RedirectDataMap>();
   auto host_redirect_data_map = base::MakeUnique<RedirectDataMap>();
   auto manifest_data_map = base::MakeUnique<ManifestDataMap>();
+  auto origin_data_map = base::MakeUnique<OriginDataMap>();
 
   // Get raw pointers to pass to the first task. Ownership of the unique_ptrs
   // will be passed to the reply task.
   auto* url_data_map_ptr = url_data_map.get();
   auto* host_data_map_ptr = host_data_map.get();
   auto* url_redirect_data_map_ptr = url_redirect_data_map.get();
   auto* host_redirect_data_map_ptr = host_redirect_data_map.get();
   auto* manifest_data_map_ptr = manifest_data_map.get();
+  auto* origin_data_map_ptr = origin_data_map.get();
 
   BrowserThread::PostTaskAndReply(
       BrowserThread::DB, FROM_HERE,
       base::Bind(&ResourcePrefetchPredictorTables::GetAllData, tables_,
                  url_data_map_ptr, host_data_map_ptr, url_redirect_data_map_ptr,
-                 host_redirect_data_map_ptr, manifest_data_map_ptr),
+                 host_redirect_data_map_ptr, manifest_data_map_ptr,
+                 origin_data_map_ptr),
       base::Bind(&ResourcePrefetchPredictor::CreateCaches, AsWeakPtr(),
                  base::Passed(&url_data_map), base::Passed(&host_data_map),
                  base::Passed(&url_redirect_data_map),
                  base::Passed(&host_redirect_data_map),
-                 base::Passed(&manifest_data_map)));
+                 base::Passed(&manifest_data_map),
+                 base::Passed(&origin_data_map)));
 }
 
 void ResourcePrefetchPredictor::RecordURLRequest(
     const URLRequestSummary& request) {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
   if (initialization_state_ != INITIALIZED)
     return;
 
   CHECK_EQ(request.resource_type, content::RESOURCE_TYPE_MAIN_FRAME);
   OnMainFrameRequest(request);
@@ skipping 10 matching lines @@
   else
     OnSubresourceResponse(response);
 }
 
 void ResourcePrefetchPredictor::RecordURLRedirect(
     const URLRequestSummary& response) {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
   if (initialization_state_ != INITIALIZED)
     return;
 
-  CHECK_EQ(response.resource_type, content::RESOURCE_TYPE_MAIN_FRAME);
-  OnMainFrameRedirect(response);
+  if (response.resource_type == content::RESOURCE_TYPE_MAIN_FRAME)
+    OnMainFrameRedirect(response);
+  else
+    OnSubresourceRedirect(response);
 }
 
 void ResourcePrefetchPredictor::RecordMainFrameLoadComplete(
     const NavigationID& navigation_id) {
   switch (initialization_state_) {
     case NOT_INITIALIZED:
       StartInitialization();
       break;
     case INITIALIZING:
       break;
@@ skipping 159 matching lines @@
   inflight_navigations_.insert(
       std::make_pair(navigation_id, std::move(summary)));
 }
 
 void ResourcePrefetchPredictor::OnSubresourceResponse(
     const URLRequestSummary& response) {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
   DCHECK_EQ(INITIALIZED, initialization_state_);
 
   NavigationMap::const_iterator nav_it =
-        inflight_navigations_.find(response.navigation_id);
-  if (nav_it == inflight_navigations_.end()) {
+      inflight_navigations_.find(response.navigation_id);
+  if (nav_it == inflight_navigations_.end())
     return;
-  }
+  auto& page_request_summary = *nav_it->second;
 
-  nav_it->second->subresource_requests.push_back(response);
+  if (!response.is_no_store)
+    page_request_summary.subresource_requests.push_back(response);
+
+  if (config_.is_origin_prediction_enabled)
+    UpdateOrAddToSummaries(&page_request_summary.origins, response);
+}
+
+void ResourcePrefetchPredictor::OnSubresourceRedirect(
+    const URLRequestSummary& response) {
+  if (!config_.is_origin_prediction_enabled)

[alexilin, 2017/04/10 14:58:28]

nit:
Please, add DCHECK for the UI thread and the correct iniaitlization state.

[Benoit L, 2017/04/11 09:04:05]

Done.

+    return;
+
+  NavigationMap::const_iterator nav_it =
+      inflight_navigations_.find(response.navigation_id);
+  if (nav_it == inflight_navigations_.end())
+    return;
+  auto& page_request_summary = *nav_it->second;
+  UpdateOrAddToSummaries(&page_request_summary.origins, response);

[alexilin, 2017/04/10 14:58:28]

Just to make it clear: do you need original url or redirected url here?
Is it acceptable to use the same logic for redirect responses? I suppose yes,
because Chrome follows cache-control directives for redirects as well.

By the way, this triggered the idea that we could consider different redirect
response codes differently for the redirect table. For example, we could be
really confident that 301 redirect is permanent. 

[Benoit L, 2017/04/11 09:04:05]

As discussed offline, we want to keep the redirected origins with the page load
data.

 }
 
 void ResourcePrefetchPredictor::OnNavigationComplete(
     const NavigationID& nav_id_without_timing_info) {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
   DCHECK_EQ(INITIALIZED, initialization_state_);
 
   NavigationMap::iterator nav_it =
       inflight_navigations_.find(nav_id_without_timing_info);
   if (nav_it == inflight_navigations_.end())
@@ skipping 113 matching lines @@
   }
 
   return has_prefetchable_resource;
 }
 
 void ResourcePrefetchPredictor::CreateCaches(
     std::unique_ptr<PrefetchDataMap> url_data_map,
     std::unique_ptr<PrefetchDataMap> host_data_map,
     std::unique_ptr<RedirectDataMap> url_redirect_data_map,
     std::unique_ptr<RedirectDataMap> host_redirect_data_map,
-    std::unique_ptr<ManifestDataMap> manifest_data_map) {
+    std::unique_ptr<ManifestDataMap> manifest_data_map,
+    std::unique_ptr<OriginDataMap> origin_data_map) {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 
   DCHECK_EQ(INITIALIZING, initialization_state_);
   DCHECK(!url_table_cache_);
   DCHECK(!host_table_cache_);
   DCHECK(!url_redirect_table_cache_);
   DCHECK(!host_redirect_table_cache_);
   DCHECK(!manifest_table_cache_);
+  DCHECK(!origin_table_cache_);
+
   DCHECK(inflight_navigations_.empty());
 
   url_table_cache_ = std::move(url_data_map);
   host_table_cache_ = std::move(host_data_map);
   url_redirect_table_cache_ = std::move(url_redirect_data_map);
   host_redirect_table_cache_ = std::move(host_redirect_data_map);
   manifest_table_cache_ = std::move(manifest_data_map);
+  origin_table_cache_ = std::move(origin_data_map);
 
   ConnectToHistoryService();
 }
 
 void ResourcePrefetchPredictor::OnHistoryAndCacheLoaded() {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
   DCHECK_EQ(INITIALIZING, initialization_state_);
 
   // Initialize the prefetch manager only if prefetching is enabled.
   if (config_.IsPrefetchingEnabledForSomeOrigin(profile_)) {
@@ skipping 50 matching lines @@
   }
 }
 
 void ResourcePrefetchPredictor::DeleteAllUrls() {
   inflight_navigations_.clear();
   url_table_cache_->clear();
   host_table_cache_->clear();
   url_redirect_table_cache_->clear();
   host_redirect_table_cache_->clear();
   manifest_table_cache_->clear();
+  origin_table_cache_->clear();
 
   BrowserThread::PostTask(BrowserThread::DB, FROM_HERE,
       base::Bind(&ResourcePrefetchPredictorTables::DeleteAllData, tables_));
 }
 
 void ResourcePrefetchPredictor::DeleteUrls(const history::URLRows& urls) {
   // Check all the urls in the database and pick out the ones that are present
   // in the cache.
   std::vector<std::string> urls_to_delete, hosts_to_delete;
   std::vector<std::string> url_redirects_to_delete, host_redirects_to_delete;
   std::vector<std::string> manifest_hosts_to_delete;
+  std::vector<std::string> origin_hosts_to_delete;
 
   for (const auto& it : urls) {
     const std::string& url_spec = it.url().spec();
     if (url_table_cache_->find(url_spec) != url_table_cache_->end()) {

[alexilin, 2017/04/10 14:58:28]

TODO for future CLs:
Use erase with iterator to avoid a second lookup in a map.

       urls_to_delete.push_back(url_spec);
       url_table_cache_->erase(url_spec);
     }
 
     if (url_redirect_table_cache_->find(url_spec) !=
         url_redirect_table_cache_->end()) {
       url_redirects_to_delete.push_back(url_spec);
       url_redirect_table_cache_->erase(url_spec);
     }
 
     const std::string& host = it.url().host();
     if (host_table_cache_->find(host) != host_table_cache_->end()) {
       hosts_to_delete.push_back(host);
       host_table_cache_->erase(host);
     }
 
     if (host_redirect_table_cache_->find(host) !=
         host_redirect_table_cache_->end()) {
       host_redirects_to_delete.push_back(host);
       host_redirect_table_cache_->erase(host);
     }
 
     std::string manifest_host = history::HostForTopHosts(it.url());
     if (manifest_table_cache_->find(manifest_host) !=
         manifest_table_cache_->end()) {
       manifest_hosts_to_delete.push_back(manifest_host);
       manifest_table_cache_->erase(manifest_host);
     }
+
+    if (origin_table_cache_->find(host) != origin_table_cache_->end()) {
+      origin_hosts_to_delete.push_back(host);
+      origin_table_cache_->erase(host);
+    }
   }
 
   if (!urls_to_delete.empty() || !hosts_to_delete.empty()) {
     BrowserThread::PostTask(
         BrowserThread::DB, FROM_HERE,
         base::Bind(&ResourcePrefetchPredictorTables::DeleteResourceData,
                    tables_, urls_to_delete, hosts_to_delete));
   }
 
   if (!url_redirects_to_delete.empty() || !host_redirects_to_delete.empty()) {
     BrowserThread::PostTask(
         BrowserThread::DB, FROM_HERE,
         base::Bind(&ResourcePrefetchPredictorTables::DeleteRedirectData,
                    tables_, url_redirects_to_delete, host_redirects_to_delete));
   }
 
   if (!manifest_hosts_to_delete.empty()) {
     BrowserThread::PostTask(
         BrowserThread::DB, FROM_HERE,
         base::Bind(&ResourcePrefetchPredictorTables::DeleteManifestData,
                    tables_, manifest_hosts_to_delete));
   }
+
+  if (!origin_hosts_to_delete.empty()) {
+    BrowserThread::PostTask(
+        BrowserThread::DB, FROM_HERE,
+        base::Bind(&ResourcePrefetchPredictorTables::DeleteOriginData, tables_,
+                   origin_hosts_to_delete));
+  }
 }
 
 void ResourcePrefetchPredictor::RemoveOldestEntryInPrefetchDataMap(
     PrefetchKeyType key_type,
     PrefetchDataMap* data_map) {
   if (data_map->empty())
     return;
 
   uint64_t oldest_time = UINT64_MAX;
   std::string key_to_delete;
@@ skipping 83 matching lines @@
                       url_redirect_table_cache_.get());
     }
   }
 
   // Host level data - no cutoff, always learn the navigation if enabled.
   const std::string host = summary.main_frame_url.host();
   LearnNavigation(host, PREFETCH_KEY_TYPE_HOST, summary.subresource_requests,
                   config_.max_hosts_to_track, host_table_cache_.get(),
                   summary.initial_url.host(), host_redirect_table_cache_.get());
 
+  if (config_.is_origin_prediction_enabled) {
+    LearnOrigins(host, summary.origins, config_.max_hosts_to_track,
+                 origin_table_cache_.get());
+  }
+
   if (observer_)
     observer_->OnNavigationLearned(url_visit_count, summary);
 }
 
 void ResourcePrefetchPredictor::LearnNavigation(
     const std::string& key,
     PrefetchKeyType key_type,
     const std::vector<URLRequestSummary>& new_resources,
     size_t max_data_map_size,
     PrefetchDataMap* data_map,
@@ skipping 224 matching lines @@
     const RedirectData& url_redirect_data =
         is_host ? empty_redirect_data : data;
     BrowserThread::PostTask(
         BrowserThread::DB, FROM_HERE,
         base::Bind(&ResourcePrefetchPredictorTables::UpdateData, tables_,
                    empty_data, empty_data, url_redirect_data,
                    host_redirect_data));
   }
 }
 
+void ResourcePrefetchPredictor::LearnOrigins(
+    const std::string& host,
+    const std::map<GURL, OriginRequestSummary>& summaries,
+    size_t max_data_map_size,
+    OriginDataMap* data_map) {
+  if (host.size() > ResourcePrefetchPredictorTables::kMaxStringLength)
+    return;
+
+  auto cache_entry = data_map->find(host);
+  bool new_entry = cache_entry == data_map->end();
+  if (new_entry) {
+    if (data_map->size() >= max_data_map_size)
+      RemoveOldestEntryInOriginDataMap(data_map);
+
+    cache_entry = data_map->insert({host, OriginData()}).first;
+    OriginData& data = cache_entry->second;
+    data.set_host(host);
+    data.set_last_visit_time(base::Time::Now().ToInternalValue());
+    size_t origins_size = summaries.size();
+    auto ordered_origins =
+        std::vector<const OriginRequestSummary*>(origins_size);
+    for (auto& kv : summaries) {

[alexilin, 2017/04/10 14:58:28]

const auto& ?

[Benoit L, 2017/04/11 09:04:05]

Done.

+      size_t index = kv.second.first_occurrence;
+      DCHECK_LT(index, origins_size);
+      ordered_origins[index] = &kv.second;
+    }
+
+    for (const OriginRequestSummary* summary : ordered_origins) {
+      auto* origin_to_add = data.add_origins();
+      InitializeOriginStatFromOriginRequestSummary(origin_to_add, *summary);
+    }
+  } else {
+    auto& data = cache_entry->second;
+    data.set_last_visit_time(base::Time::Now().ToInternalValue());
+
+    std::map<GURL, int> old_index;
+    int old_size = static_cast<int>(data.origins_size());
+    for (int i = 0; i < old_size; ++i) {
+      bool is_new =
+          old_index.insert({GURL(data.origins(i).origin()), i}).second;
+      DCHECK(is_new);
+    }
+
+    // Update the old origins.
+    for (int i = 0; i < old_size; ++i) {
+      auto* old_origin = data.mutable_origins(i);
+      GURL origin(old_origin->origin());
+      auto it = summaries.find(origin);
+      if (it == summaries.end()) {
+        // miss
+        old_origin->set_number_of_misses(old_origin->number_of_misses() + 1);
+        old_origin->set_consecutive_misses(old_origin->consecutive_misses() +
+                                           1);
+      } else {
+        // hit: update.
+        const auto& new_origin = it->second;
+        old_origin->set_always_access_network(new_origin.always_access_network);
+        old_origin->set_accessed_network(true);

[alexilin, 2017/04/10 14:58:27]

Why not `new_origin.accessed_network`?

[Benoit L, 2017/04/11 09:04:05]

Oops.
Done.

+
+        int position = new_origin.first_occurrence + 1;
+        int total =
+            old_origin->number_of_hits() + old_origin->number_of_misses();
+        old_origin->set_average_position(
+            ((old_origin->average_position() * total) + position) /
+            (total + 1));
+        old_origin->set_number_of_hits(old_origin->number_of_hits() + 1);
+        old_origin->set_consecutive_misses(0);
+      }
+    }
+
+    // Add new origins.
+    for (const auto& kv : summaries) {
+      if (old_index.find(kv.first) != old_index.end())
+        continue;
+
+      auto* origin_to_add = data.add_origins();
+      InitializeOriginStatFromOriginRequestSummary(origin_to_add, kv.second);
+    }
+  }
+
+  // Trim and Sort.
+  auto& data = cache_entry->second;
+  ResourcePrefetchPredictorTables::TrimOrigins(&data,
+                                               config_.max_consecutive_misses);
+  ResourcePrefetchPredictorTables::SortOrigins(&data);
+  if (data.origins_size() > static_cast<int>(config_.max_resources_per_entry)) {
+    data.mutable_origins()->DeleteSubrange(
+        config_.max_origins_per_entry,
+        data.origins_size() - config_.max_origins_per_entry);
+  }
+
+  // Update the database.
+  if (data.origins_size() == 0) {
+    data_map->erase(cache_entry);
+    if (!new_entry) {
+      BrowserThread::PostTask(
+          BrowserThread::DB, FROM_HERE,
+          base::Bind(&ResourcePrefetchPredictorTables::DeleteOriginData,
+                     tables_, std::vector<std::string>({host})));
+    }
+  } else {
+    BrowserThread::PostTask(
+        BrowserThread::DB, FROM_HERE,
+        base::Bind(&ResourcePrefetchPredictorTables::UpdateOriginData, tables_,
+                   host, data));
+  }
+}
+
+void ResourcePrefetchPredictor::RemoveOldestEntryInOriginDataMap(

[alexilin, 2017/04/10 14:58:27]

nit:
Could you put this function before LearnNavigation() definition to correspond
declaration order in .h file? I know, it's broken for this file but at least we
could preserve the order for new functions.
https://chromium.googlesource.com/chromium/src/+/master/styleguide/c++/c++.md...

[Benoit L, 2017/04/11 09:04:05]

Done.

+    OriginDataMap* data_map) {
+  if (data_map->empty())
+    return;
+
+  uint64_t oldest_time = UINT64_MAX;
+  std::string key_to_delete;
+  for (const auto& kv : *data_map) {
+    const OriginData& data = kv.second;
+    if (key_to_delete.empty() || data.last_visit_time() < oldest_time) {
+      key_to_delete = kv.first;
+      oldest_time = data.last_visit_time();
+    }
+  }
+
+  data_map->erase(key_to_delete);
+  BrowserThread::PostTask(
+      BrowserThread::DB, FROM_HERE,
+      base::Bind(&ResourcePrefetchPredictorTables::DeleteOriginData, tables_,
+                 std::vector<std::string>({key_to_delete})));
+}
+
 void ResourcePrefetchPredictor::ReportDatabaseReadiness(
     const history::TopHostsList& top_hosts) const {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
   if (top_hosts.size() == 0)
     return;
 
   size_t count_in_cache = 0;
   size_t total_visits = 0;
   for (const std::pair<std::string, int>& top_host : top_hosts) {
     const std::string& host = top_host.first;
@@ skipping 95 matching lines @@
 TestObserver::~TestObserver() {
   predictor_->SetObserverForTesting(nullptr);
 }
 
 TestObserver::TestObserver(ResourcePrefetchPredictor* predictor)
     : predictor_(predictor) {
   predictor_->SetObserverForTesting(this);
 }
 
 }  // namespace predictors