Move full hash caching logic to v4_get_hash_protocol_manager

components/safe_browsing_db/v4_get_hash_protocol_manager.cc

 // Copyright 2016 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 "components/safe_browsing_db/v4_get_hash_protocol_manager.h"
 
 #include <utility>
 
 #include "base/base64url.h"
 #include "base/macros.h"
@@ skipping 34 matching lines @@
   INCONSISTENT_THREAT_TYPE_ERROR = 5,
 
   // A match in the response contained a metadata, but the metadata is invalid.
   UNEXPECTED_METADATA_VALUE_ERROR = 6,
 
   // Memory space for histograms is determined by the max.  ALWAYS
   // ADD NEW VALUES BEFORE THIS ONE.
   PARSE_RESULT_TYPE_MAX = 7,
 };
 
+// Enumerate full hash cache hits/misses for histogramming purposes.
+// DO NOT CHANGE THE ORDERING OF THESE VALUES.
+enum V4FullHashCacheResultType {
+  // Full hashes for which there is no cache hit.
+  FULL_HASH_CACHE_MISS = 0,
+
+  // Full hashes with a cache hit.
+  FULL_HASH_CACHE_HIT = 1,
+
+  // Full hashes with a negative cache hit.
+  FULL_HASH_NEGATIVE_CACHE_HIT = 2,
+
+  // Memory space for histograms is determined by the max. ALWAYS
+  // ADD NEW VALUES BEFORE THIS ONE.
+  FULL_HASH_CACHE_RESULT_MAX
+};
+
 // Record parsing errors of a GetHash result.
 void RecordParseGetHashResult(ParseResultType result_type) {
   UMA_HISTOGRAM_ENUMERATION("SafeBrowsing.ParseV4HashResult", result_type,
                             PARSE_RESULT_TYPE_MAX);
 }
 
 // Record a GetHash result.
 void RecordGetHashResult(safe_browsing::V4OperationResult result) {
   UMA_HISTOGRAM_ENUMERATION(
       "SafeBrowsing.GetV4HashResult", result,
       safe_browsing::V4OperationResult::OPERATION_RESULT_MAX);
 }
 
+// Record a full hash cache hit result.
+void RecordV4FullHashCacheResult(
+    V4FullHashCacheResultType result_type) {
+  UMA_HISTOGRAM_ENUMERATION("SafeBrowsing.V4FullHashCacheResult", result_type,
+                            FULL_HASH_CACHE_RESULT_MAX);
+}
+
 }  // namespace
 
 namespace safe_browsing {
 
 const char kUmaV4HashResponseMetricName[] =
     "SafeBrowsing.GetV4HashHttpResponseOrErrorCode";
 
 // The default V4GetHashProtocolManagerFactory.
 class V4GetHashProtocolManagerFactoryImpl
     : public V4GetHashProtocolManagerFactory {
@@ skipping 35 matching lines @@
     : gethash_error_count_(0),
       gethash_back_off_mult_(1),
       next_gethash_time_(Time::FromDoubleT(0)),
       config_(config),
       request_context_getter_(request_context_getter),
       url_fetcher_id_(0),
       clock_(new base::DefaultClock()) {}
 
 V4GetHashProtocolManager::~V4GetHashProtocolManager() {
   // Delete in-progress SafeBrowsing requests.
-  STLDeleteContainerPairFirstPointers(hash_requests_.begin(),
-                                      hash_requests_.end());
-  hash_requests_.clear();
+  STLDeleteContainerPairFirstPointers(pending_hash_requests_.begin(),
+                                      pending_hash_requests_.end());
+  pending_hash_requests_.clear();
 }
 
 // static
 void V4GetHashProtocolManager::RegisterFactory(
     std::unique_ptr<V4GetHashProtocolManagerFactory> factory) {
   if (factory_)
     delete factory_;
   factory_ = factory.release();
 }
 
@@ skipping 69 matching lines @@
     if (expected_threat_type == THREAT_TYPE_UNSPECIFIED) {
       expected_threat_type = match.threat_type();
     } else if (match.threat_type() != expected_threat_type) {
       RecordParseGetHashResult(INCONSISTENT_THREAT_TYPE_ERROR);
       return false;
     }
 
     // Fill in the full hash.
     SBFullHashResult result;
     result.hash = StringToSBFullHash(match.threat().hash());
-
     if (match.has_cache_duration()) {
       // Seconds resolution is good enough so we ignore the nanos field.
       result.cache_expire_after =
           clock_->Now() +
           base::TimeDelta::FromSeconds(match.cache_duration().seconds());
     } else {
       result.cache_expire_after = clock_->Now();
     }
 
     // Different threat types will handle the metadata differently.
@@ skipping 95 matching lines @@
   std::string req_base64 = GetHashRequest(prefixes, platforms, threat_type);
   GURL gethash_url;
   net::HttpRequestHeaders headers;
   GetHashUrlAndHeaders(req_base64, &gethash_url, &headers);
 
   net::URLFetcher* fetcher =
       net::URLFetcher::Create(url_fetcher_id_++, gethash_url,
                               net::URLFetcher::GET, this)
           .release();
   fetcher->SetExtraRequestHeaders(headers.ToString());
-  hash_requests_[fetcher] = callback;
+  pending_hash_requests_[fetcher] = std::make_pair(prefixes, callback);
 
   fetcher->SetLoadFlags(net::LOAD_DISABLE_CACHE);
   fetcher->SetRequestContext(request_context_getter_.get());
   fetcher->Start();
 }
 
 void V4GetHashProtocolManager::GetFullHashesWithApis(
     const std::vector<SBPrefix>& prefixes,
     FullHashCallback callback) {
   std::vector<PlatformType> platform = {CHROME_PLATFORM};
   GetFullHashes(prefixes, platform, API_ABUSE, callback);
 }
 
 void V4GetHashProtocolManager::SetClockForTests(
     std::unique_ptr<base::Clock> clock) {
   clock_ = std::move(clock);
 }
 
 // net::URLFetcherDelegate implementation ----------------------------------
 
 // SafeBrowsing request responses are handled here.
 void V4GetHashProtocolManager::OnURLFetchComplete(
     const net::URLFetcher* source) {
   DCHECK(CalledOnValidThread());
 
-  HashRequests::iterator it = hash_requests_.find(source);
-  DCHECK(it != hash_requests_.end()) << "Request not found";
+  PendingHashRequests::iterator it = pending_hash_requests_.find(source);
+  DCHECK(it != pending_hash_requests_.end()) << "Request not found";
 
   // FindFullHashes response.
   // Reset the scoped pointer so the fetcher gets destroyed properly.
   std::unique_ptr<const net::URLFetcher> fetcher(it->first);
 
   int response_code = source->GetResponseCode();
   net::URLRequestStatus status = source->GetStatus();
   V4ProtocolManagerUtil::RecordHttpResponseOrErrorCode(
       kUmaV4HashResponseMetricName, status, response_code);
 
-  const FullHashCallback& callback = it->second;
+  const FullHashCallback& callback = it->second.second;

[Nathan Parker, 2016/08/15 19:54:47]

nit: I might vote for a simple struct rather than a pair, since second.second is
pretty opaque.

   std::vector<SBFullHashResult> full_hashes;
   base::Time negative_cache_expire;
   if (status.is_success() && response_code == net::HTTP_OK) {
     RecordGetHashResult(V4OperationResult::STATUS_200);
     ResetGetHashErrors();
     std::string data;
     source->GetResponseAsString(&data);
     if (!ParseHashResponse(data, &full_hashes, &negative_cache_expire)) {
       full_hashes.clear();
       RecordGetHashResult(V4OperationResult::PARSE_ERROR);
     }
   } else {
     HandleGetHashError(clock_->Now());
 
     DVLOG(1) << "SafeBrowsing GetEncodedFullHashes request for: "
              << source->GetURL() << " failed with error: " << status.error()
              << " and response code: " << response_code;
 
     if (status.status() == net::URLRequestStatus::FAILED) {
       RecordGetHashResult(V4OperationResult::NETWORK_ERROR);
     } else {
       RecordGetHashResult(V4OperationResult::HTTP_ERROR);
     }
   }
 
+  const std::vector<SBPrefix>& prefixes = it->second.first;
+  // If the time is uninitialized, don't cache the results.
+  if (!negative_cache_expire.is_null()) {
+    // Cache the results.
+    // Create or reset all cached results for this prefix.
+    for (const SBPrefix& prefix : prefixes) {
+      v4_full_hash_cache_[SB_THREAT_TYPE_API_ABUSE][prefix] =

[Nathan Parker, 2016/08/15 19:54:47]

The threat type shouldn't be hardcoded here... it probably should be pulled from
the request.

+          SBCachedFullHashResult(negative_cache_expire);
+    }
+    // Insert any full hash hits. Note that there may be one, multiple, or no
+    // full hashes for any given prefix.
+    for (const SBFullHashResult& result : full_hashes) {
+      v4_full_hash_cache_[SB_THREAT_TYPE_API_ABUSE][result.hash.prefix].
+          full_hashes.push_back(result);
+    }
+  }
+
   // Invoke the callback with full_hashes, even if there was a parse error or
   // an error response code (in which case full_hashes will be empty). The
   // caller can't be blocked indefinitely.
   callback.Run(full_hashes, negative_cache_expire);
 
-  hash_requests_.erase(it);
+  pending_hash_requests_.erase(it);
 }
 
 void V4GetHashProtocolManager::HandleGetHashError(const Time& now) {
   DCHECK(CalledOnValidThread());
   base::TimeDelta next = V4ProtocolManagerUtil::GetNextBackOffInterval(
       &gethash_error_count_, &gethash_back_off_mult_);
   next_gethash_time_ = now + next;
 }
 
 void V4GetHashProtocolManager::GetHashUrlAndHeaders(
     const std::string& req_base64,
     GURL* gurl,
     net::HttpRequestHeaders* headers) const {
   V4ProtocolManagerUtil::GetRequestUrlAndHeaders(req_base64, "fullHashes:find",
                                                  config_, gurl, headers);
 }
 
+void V4GetHashProtocolManager::GetFullHashCachedResults(
+    const SBThreatType& threat_type,
+    const std::vector<SBFullHash>& full_hashes,
+    base::Time now,
+    std::vector<SBPrefix>* prefixes_needing_reqs,
+    std::vector<SBFullHashResult>* cached_results) {
+  DCHECK(prefixes_needing_reqs);
+  prefixes_needing_reqs->clear();
+  DCHECK(cached_results);
+  cached_results->clear();
+
+  // Caching behavior is documented here:
+  // https://developers.google.com/safe-browsing/v4/caching#about-caching
+  //
+  // The cache operates as follows:
+  // 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's
+  //   cache entry if they expire AND their expire time is after the negative
+  //   cache expire time.
+  for (const SBFullHash& full_hash : full_hashes) {
+    auto entry = v4_full_hash_cache_[threat_type].find(full_hash.prefix);
+    if (entry != v4_full_hash_cache_[threat_type].end()) {
+      // Case 1.
+      SBCachedFullHashResult& cache_result = entry->second;
+
+      const SBFullHashResult* found_full_hash = nullptr;
+      size_t matched_idx = 0;
+      for (const SBFullHashResult& hash_result : cache_result.full_hashes) {
+        if (SBFullHashEqual(full_hash, hash_result.hash)) {
+          found_full_hash = &hash_result;
+          break;
+        }
+        ++matched_idx;
+      }
+
+      if (found_full_hash) {
+        // Case a.
+        if (found_full_hash->cache_expire_after > now) {
+          // Case i.
+          cached_results->push_back(*found_full_hash);
+          RecordV4FullHashCacheResult(FULL_HASH_CACHE_HIT);
+        } else {
+          // Case ii.
+          prefixes_needing_reqs->push_back(full_hash.prefix);
+          RecordV4FullHashCacheResult(FULL_HASH_CACHE_MISS);
+          // If the negative cache expire time has passed, evict this full hash
+          // result from the cache.
+          if (cache_result.expire_after <= now) {
+            cache_result.full_hashes.erase(
+                cache_result.full_hashes.begin() + matched_idx);
+            // If there are no more full hashes, we can evict the entire entry.
+            if (cache_result.full_hashes.empty()) {
+              v4_full_hash_cache_[threat_type].erase(entry);
+            }
+          }
+        }
+      } else {
+        // Case b.
+        if (cache_result.expire_after > now) {
+          // Case i.
+          RecordV4FullHashCacheResult(FULL_HASH_NEGATIVE_CACHE_HIT);
+        } else {
+          // Case ii.
+          prefixes_needing_reqs->push_back(full_hash.prefix);
+          RecordV4FullHashCacheResult(FULL_HASH_CACHE_MISS);
+        }
+      }
+    } else {
+      // Case 2.
+      prefixes_needing_reqs->push_back(full_hash.prefix);
+      RecordV4FullHashCacheResult(FULL_HASH_CACHE_MISS);
+    }
+  }
+
+  // Multiple full hashes could share a prefix, remove duplicates.
+  // TODO(kcarattini): Make |prefixes_needing_reqs| a set.
+  std::sort(prefixes_needing_reqs->begin(), prefixes_needing_reqs->end());
+  prefixes_needing_reqs->erase(std::unique(prefixes_needing_reqs->begin(),
+      prefixes_needing_reqs->end()), prefixes_needing_reqs->end());
+}
+
 }  // namespace safe_browsing