SafeBrowsing: Implement cache eviction for API full hash results.

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 4646d0ec4c7bba03f4c086db5bd57cf23ffc9ad3..2328617f4bffadb94f131bd48e8f6f4efbc1db09 100644
--- a/components/safe_browsing_db/database_manager.cc
+++ b/components/safe_browsing_db/database_manager.cc
@@ -166,20 +166,20 @@ void SafeBrowsingDatabaseManager::GetFullHashCachedResults(
   //   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.
-  //
-  // TODO(kcarattini): Implement cache eviction.
   for (const SBFullHash& full_hash : full_hashes) {
     auto entry = v4_full_hash_cache_.find(full_hash.prefix);
     if (entry != v4_full_hash_cache_.end()) {
       // Case 1.
-      const SBCachedFullHashResult& cache_result = entry->second;
+      SBCachedFullHashResult& cache_result = entry->second;
 
       const SBFullHashResult* found_full_hash = nullptr;
+      size_t i = 0;

[Nathan Parker, 2016/05/31 22:28:31]

how about something a bit more descriptive, like matched_idx

[kcarattini, 2016/06/01 10:58:36]

Done.

       for (const SBFullHashResult& hash_result : cache_result.full_hashes) {
         if (SBFullHashEqual(full_hash, hash_result.hash)) {
           found_full_hash = &hash_result;
           break;
         }
+        ++i;
       }
 
       if (found_full_hash) {
@@ -190,6 +190,16 @@ void SafeBrowsingDatabaseManager::GetFullHashCachedResults(
         } else {
           // Case ii.
           prefixes_needing_reqs->push_back(full_hash.prefix);
+          // If the negative cache expire time has passed, evict this full hash
+          // result from the cache.
+          if (cache_result.expire_after <= now) {

[Nathan Parker, 2016/05/31 23:32:04]

What if there are positive cache entries that haven't expired? Or is the
negative cache always longer?

Might it be necessary to have a periodic scan for expired entries, so they don't
sit around forever if they aren't revisited? I'm not familiar enough with the
pver3 caching to know if it does that.

[kcarattini, 2016/06/01 10:58:36]

Alex, correct me if I'm wrong, but I do not believe there is any guarantee that
the negative cache duration is longer. This code only removes the full hash in
question (that has expired), and only removes the entire cache entry if there
are no more full hashes in the entry (therefore no more positive cache entries
that haven't expired yes).
I do not believe the pver3 code does this, so I would guess it's probably not
necessary. But I don't know. We could add UMA for the number of entries in the
cache? Something else? 

[woz, 2016/06/02 15:38:26]

That's right -- there's no guarantee that neg. cache duration > pos. cache
duration.

+            cache_result.full_hashes.erase(
+                cache_result.full_hashes.begin() + i);
+            // If there are no more full hashes, we can evict the entire entry.
+            if (cache_result.full_hashes.empty()) {
+              v4_full_hash_cache_.erase(entry);
+            }
+          }
         }
       } else {
         // Case b.