SafeBrowsing: Implement cache lookup for full hash checks

components/safe_browsing_db/database_manager.cc

Index: components/safe_browsing_db/database_manager.cc
diff --git a/components/safe_browsing_db/database_manager.cc b/components/safe_browsing_db/database_manager.cc
index 6baf4da4acb07d8a43307fbd5d49e9b9587525b0..1f82ec19673c65bdf837aa8c49055055cfa2d36c 100644
--- a/components/safe_browsing_db/database_manager.cc
+++ b/components/safe_browsing_db/database_manager.cc
@@ -94,21 +94,30 @@ bool SafeBrowsingDatabaseManager::CheckApiBlacklistUrl(const GURL& url,
   if (full_hashes.empty())
     return true;
 
-  // Copy to prefixes.
+  // First check the cache.
+
+  // Used to determine cache expiration.
+  base::Time now = base::Time::Now();
+
+  std::vector<SBFullHashResult> cached_results;
   std::vector<SBPrefix> prefixes;

[Nathan Parker, 2016/05/26 22:30:55]

maybe "prefixes_needing_reqs"?  Otherwise it looks like the prefixes of all the
full hashes.

[awoz, 2016/05/27 16:54:36]

+1

[kcarattini, 2016/05/30 05:22:51]

Done.

-  for (const SBFullHash& full_hash : full_hashes) {
-    prefixes.push_back(full_hash.prefix);
-  }
-  // Multiple full hashes could share a prefix, remove duplicates.
-  std::sort(prefixes.begin(), prefixes.end());
-  prefixes.erase(std::unique(prefixes.begin(), prefixes.end()), prefixes.end());
-  DCHECK(!prefixes.empty());
+  GetCachedResults(full_hashes, now, &prefixes, &cached_results);
+
+  if (prefixes.empty() && cached_results.empty())
+    return true;
 
   SafeBrowsingApiCheck* check =
-      new SafeBrowsingApiCheck(url, prefixes, full_hashes, client);
+      new SafeBrowsingApiCheck(url, prefixes, full_hashes, cached_results,
+                               client);
   api_checks_.insert(check);
 
-  // TODO(kcarattini): Implement cache compliance.
+  if (prefixes.empty()) {
+    // We can call the callback immediately if no prefixes require a request.
+    std::vector<SBFullHashResult> full_hash_results;
+    HandleGetHashesWithApisResults(check, full_hash_results, base::Time());

[Nathan Parker, 2016/05/26 22:30:55]

Shouldn't this be cached_results?

[kcarattini, 2016/05/30 05:22:50]

The cached_results are stored in the check (passed as the first argument).
full_hash_results represents the results from the SB server (which are empty
because there was no request). Can I make this more clear somehow? I've updated
the comment.

+    return false;
+  }
+
   v4_get_hash_protocol_manager_->GetFullHashesWithApis(prefixes,
       base::Bind(&SafeBrowsingDatabaseManager::HandleGetHashesWithApisResults,
                  base::Unretained(this), check));
@@ -116,6 +125,96 @@ bool SafeBrowsingDatabaseManager::CheckApiBlacklistUrl(const GURL& url,
   return false;
 }
 
+void SafeBrowsingDatabaseManager::GetCachedResults(
+    const std::vector<SBFullHash>& full_hashes,
+    base::Time now,
+    std::vector<SBPrefix>* prefixes,
+    std::vector<SBFullHashResult>* cached_results) {
+  DCHECK(prefixes);
+  prefixes->clear();
+  DCHECK(cached_results);
+  cached_results->clear();
+
+  if (full_hashes.empty())

[Nathan Parker, 2016/05/26 22:30:55]

nit: This is duplicate of that up on line 94

[kcarattini, 2016/05/30 05:22:50]

Removed.

+    return;
+
+  // Caching behavior is documented here:
+  // https://devsite.googleplex.com/safe-browsing/v4/caching#about-caching

[awoz, 2016/05/27 16:54:36]

Can you update this to the public URL?
https://developers.google.com/safe-browsing/v4/caching#about-caching

[kcarattini, 2016/05/30 05:22:50]

Done.

+  //
+  // The cache operates as follows:

[Nathan Parker, 2016/05/26 22:30:55]

Nice documentation!

[awoz, 2016/05/27 16:54:36]

+1!

[kcarattini, 2016/05/30 05:22:50]

Thanks!

+  // Lookup:
+  //     Case 1: The prefix is in the cache.
+  //         Case a: The full hash is in the cache.
+  //             Case i : The positive full hash result has not expired.
+  //                      The result is unsafe and we do not need to send a new
+  //                      request.
+  //             Case ii: The positive full hash result has expired.
+  //                      We need to send a request for full hashes.
+  //         Case b: The full hash is not in the cache.
+  //             Case i : The negative cache entry has not expired.
+  //                      The result is still safe and we do not need to send a
+  //                      new request.
+  //             Case ii: The negative cache entry has expired.
+  //                      We need to send a request for full hashes.
+  //     Case 2: The prefix is not in the cache.
+  //             We need to send a request for full hashes.
+  //
+  // Eviction:
+  //   SBCachedFullHashResult entries can be removed from the cache only when
+  //   the negative cache expire time and the cache expire time of all full
+  //   hash results for that prefix have expired.
+  //   Individual full hash results can be removed from the prefix'

[awoz, 2016/05/27 16:54:36]

s/prefix'/prefix's

[kcarattini, 2016/05/30 05:22:51]

Done.

+  //   cache entry if they expire AND their expire time is after the negative
+  //   cache expire time.
+  //
+  // TODO(kcarattini): Implement cache eviction.
+  for (const SBFullHash& full_hash : full_hashes) {
+    auto entry = api_cache_.find(full_hash.prefix);
+    if (entry != api_cache_.end()) {
+      // Case 1.
+      const SBCachedFullHashResult& cache_result = entry->second;
+      bool full_hash_in_cache = false;
+      size_t i = 0;
+
+      for (; i < cache_result.full_hashes.size(); ++i) {

[Nathan Parker, 2016/05/26 22:30:55]

Not sure if this is better, you decide.  It's one less variable:


const SBFullHashResult* found_full_hash = nullptr;
for (const SBFullHashResult& hash_result : cache_result.full_hashes)  {
  if...() {
   found_full_hash = &hash_result;
   break;
}

if (found_full_hash) {
 ..
}

[kcarattini, 2016/05/30 05:22:50]

Done.

+        const SBFullHashResult& hash_result = cache_result.full_hashes[i];
+        if (SBFullHashEqual(full_hash, hash_result.hash)) {
+          full_hash_in_cache = true;
+          break;
+        }
+      }
+
+      if (full_hash_in_cache) {
+        // Case a.
+        const SBFullHashResult& hash_result = cache_result.full_hashes[i];
+        if (hash_result.cache_expire_after > now) {
+          // Case i.
+          cached_results->push_back(hash_result);
+        } else {
+          // Case ii.
+          prefixes->push_back(full_hash.prefix);
+        }
+      } else {
+        // Case b.
+        if (cache_result.expire_after > now) {
+          // Case i.

[Nathan Parker, 2016/05/26 22:30:55]

This is a little weird, but I see the point of the symmetry.

[kcarattini, 2016/05/30 05:22:50]

Acknowledged.

+        } else {
+          // Case ii.
+          prefixes->push_back(full_hash.prefix);
+        }
+      }
+    } else {
+      // Case 2.
+      prefixes->push_back(full_hash.prefix);
+    }
+  }
+
+  // Multiple full hashes could share a prefix, remove duplicates.
+  std::sort(prefixes->begin(), prefixes->end());
+  prefixes->erase(std::unique(
+      prefixes->begin(), prefixes->end()), prefixes->end());
+}
+
 void SafeBrowsingDatabaseManager::HandleGetHashesWithApisResults(
     SafeBrowsingApiCheck* check,
     const std::vector<SBFullHashResult>& full_hash_results,
@@ -145,29 +244,45 @@ void SafeBrowsingDatabaseManager::HandleGetHashesWithApisResults(
 
   ThreatMetadata md;
   // Merge the metadata from all matching results.
-  // TODO(kcarattini): This is O(N^2). Look at improving performance by
-  // using a map, sorting or doing binary search etc..
-  for (const SBFullHashResult& result : full_hash_results) {
-    for (const SBFullHash& full_hash : check->full_hashes()) {
+  // Note: A full hash may have a result in both the cached results (from
+  // its own cache lookup) and in the server results (if another full hash
+  // with the same prefix needed to request results from the server). In this
+  // unlikely case, the two results' metadata will be merged.
+  PopulateMetadataResult(full_hash_results, check->full_hashes(), &md);
+  PopulateMetadataResult(check->cached_results(), check->full_hashes(), &md);
+
+  check->client()->OnCheckApiBlacklistUrlResult(check->url(), md);
+  api_checks_.erase(it);
+  delete check;
+}
+
+// TODO(kcarattini): This is O(N^2). Look at improving performance by
+// using a map, sorting or doing binary search etc..
+void SafeBrowsingDatabaseManager::PopulateMetadataResult(
+    const std::vector<SBFullHashResult>& results,
+    const std::vector<SBFullHash>& full_hashes,
+    ThreatMetadata* md) {
+  DCHECK(md);
+  for (const SBFullHashResult& result : results) {
+    for (const SBFullHash& full_hash : full_hashes) {
       if (SBFullHashEqual(full_hash, result.hash)) {
-        md.api_permissions.insert(md.api_permissions.end(),
-                                  result.metadata.api_permissions.begin(),
-                                  result.metadata.api_permissions.end());
+        md->api_permissions.insert(md->api_permissions.end(),
+            result.metadata.api_permissions.begin(),
+            result.metadata.api_permissions.end());
         break;
       }
     }
   }
-
-  check->client()->OnCheckApiBlacklistUrlResult(check->url(), md);
-  api_checks_.erase(it);
-  delete check;
 }
 
 SafeBrowsingDatabaseManager::SafeBrowsingApiCheck::SafeBrowsingApiCheck(
-    const GURL& url, const std::vector<SBPrefix>& prefixes,
-    const std::vector<SBFullHash>& full_hashes, Client* client)
+    const GURL& url,
+    const std::vector<SBPrefix>& prefixes,
+    const std::vector<SBFullHash>& full_hashes,
+    const std::vector<SBFullHashResult>& cached_results,
+    Client* client)
     : url_(url), prefixes_(prefixes), full_hashes_(full_hashes),
-      client_(client) {
+      cached_results_(cached_results), client_(client) {
 }
 
 SafeBrowsingDatabaseManager::SafeBrowsingApiCheck::~SafeBrowsingApiCheck() {