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 49 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 UpdateOrAddToOrigins(
+    std::map<GURL, ResourcePrefetchPredictor::OriginRequestSummary>* summaries,
+    const ResourcePrefetchPredictor::URLRequestSummary& request_summary,
+    bool is_redirect) {
+  const GURL& resource_url = request_summary.resource_url;
+  const GURL& request_url = request_summary.request_url;

[alexilin, 2017/04/12 13:44:05]

No need in picking between resource_url and request_url. You can always use
request_url now and it'll be correct both for redirect and response.

request_url is an URL we've requested and redirect_url we're going to request
next if present.

+  bool valid_urls = resource_url.is_valid() && request_url.is_valid();
+
+  DCHECK(valid_urls);
+  if (!valid_urls)
+    return;
+
+  // If the response is a redirect, then add the original origin, otherwise

[alexilin, 2017/04/12 13:44:05]

request_url is exact URL that was requested so we won't update the starting
point of the redirect chain multiple times in the case of long redirect chain.

+  // the redirected one. Note that this makes the predictor imprecise when
+  // a request goes through multiple redirects, as this will update the
+  // summary of the starting point of the redirect chain only.
+  GURL origin =
+      is_redirect ? resource_url.GetOrigin() : request_url.GetOrigin();
+  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 191 matching lines @@
 
   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(
     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);
+  return ShouldRecordResponse(response);
 }
 
 // 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),
+      first_occurrence(0) {}
+
+ResourcePrefetchPredictor::OriginRequestSummary::OriginRequestSummary(
+    const OriginRequestSummary& other) = default;
+
+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),
+      network_accessed(false) {}
 
 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;
 
 ResourcePrefetchPredictor::URLRequestSummary::~URLRequestSummary() {
 }
 
 // static
 bool ResourcePrefetchPredictor::URLRequestSummary::SummarizeResponse(
     const net::URLRequest& request,
     URLRequestSummary* summary) {
   const content::ResourceRequestInfo* request_info =
       content::ResourceRequestInfo::ForRequest(&request);
   if (!request_info)
     return false;
 
   summary->resource_url = request.original_url();
+  summary->request_url = request.url();
   content::ResourceType resource_type_from_request =
       request_info->GetResourceType();
   summary->priority = request.priority();
   request.GetMimeType(&summary->mime_type);
   summary->was_cached = request.was_cached();
   summary->resource_type =
       GetResourceType(resource_type_from_request, summary->mime_type);
 
   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)
+    UpdateOrAddToOrigins(&page_request_summary.origins, response, false);
+}
+
+void ResourcePrefetchPredictor::OnSubresourceRedirect(
+    const URLRequestSummary& response) {
+  DCHECK_CURRENTLY_ON(BrowserThread::UI);
+  DCHECK_EQ(INITIALIZED, initialization_state_);
+
+  if (!config_.is_origin_prediction_enabled)
+    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;
+  UpdateOrAddToOrigins(&page_request_summary.origins, response, true);
 }
 
 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()) {
       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()) {
@@ skipping 12 matching lines @@
       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 50 matching lines @@
       });
 
   std::string key_to_delete = oldest_entry->first;
   data_map->erase(oldest_entry);
   BrowserThread::PostTask(
       BrowserThread::DB, FROM_HERE,
       base::Bind(&ResourcePrefetchPredictorTables::DeleteManifestData, tables_,
                  std::vector<std::string>({key_to_delete})));
 }
 
+void ResourcePrefetchPredictor::RemoveOldestEntryInOriginDataMap(
+    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::OnVisitCountLookup(
     size_t url_visit_count,
     const PageRequestSummary& summary) {
   DCHECK_CURRENTLY_ON(BrowserThread::UI);
 
   UMA_HISTOGRAM_COUNTS("ResourcePrefetchPredictor.HistoryVisitCountForUrl",
                        url_visit_count);
 
   // TODO(alexilin): make only one request to DB thread.
 
@@ skipping 13 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 (const auto& kv : summaries) {
+      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(new_origin.accessed_network);
+
+        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_,
+                   data));
+  }
+}
+
 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 98 matching lines @@
 TestObserver::~TestObserver() {
   predictor_->SetObserverForTesting(nullptr);
 }
 
 TestObserver::TestObserver(ResourcePrefetchPredictor* predictor)
     : predictor_(predictor) {
   predictor_->SetObserverForTesting(this);
 }
 
 }  // namespace predictors