SafeBrowsing: Implement cache eviction for API full hash results.

components/safe_browsing_db/database_manager.cc

 // Copyright 2015 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/database_manager.h"
 
 #include "components/safe_browsing_db/v4_get_hash_protocol_manager.h"
 #include "content/public/browser/browser_thread.h"
 #include "net/url_request/url_request_context_getter.h"
 #include "url/gurl.h"
@@ skipping 148 matching lines @@
   //     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.
-  //
-  // 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) {
         // Case a.
         if (found_full_hash->cache_expire_after > now) {
           // Case i.
           cached_results->push_back(*found_full_hash);
         } 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.
         if (cache_result.expire_after > now) {
           // Case i.
         } else {
           // Case ii.
           prefixes_needing_reqs->push_back(full_hash.prefix);
         }
       }
     } else {
       // Case 2.
       prefixes_needing_reqs->push_back(full_hash.prefix);
     }
   }
 
   // Multiple full hashes could share a prefix, remove duplicates.
   std::sort(prefixes_needing_reqs->begin(), prefixes_needing_reqs->end());

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

an idea: prefixes_needing_req's could be a set (like your fix to api metatdata)

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

I added a TODO. Since this change will require piping through the protocol
manager as well, I don't want to bloat this cl.

   prefixes_needing_reqs->erase(std::unique(prefixes_needing_reqs->begin(),
       prefixes_needing_reqs->end()), prefixes_needing_reqs->end());
 }
 
 void SafeBrowsingDatabaseManager::HandleGetHashesWithApisResults(
     SafeBrowsingApiCheck* check,
     const std::vector<SBFullHashResult>& full_hash_results,
     const base::Time& negative_cache_expire) {
   DCHECK_CURRENTLY_ON(BrowserThread::IO);
   DCHECK(check);
@@ skipping 59 matching lines @@
     const std::vector<SBFullHashResult>& cached_results,
     Client* client)
     : url_(url), prefixes_(prefixes), full_hashes_(full_hashes),
       cached_results_(cached_results), client_(client) {
 }
 
 SafeBrowsingDatabaseManager::SafeBrowsingApiCheck::~SafeBrowsingApiCheck() {
 }
 
 }  // namespace safe_browsing