--- a/toolkit/components/url-classifier/Classifier.cpp
+++ b/toolkit/components/url-classifier/Classifier.cpp
@@ -491,35 +491,28 @@ Classifier::Check(const nsACString& aSpe
       nsAutoCString checking;
       lookupHash.ToHexString(checking);
       LOG(("Checking fragment %s, hash %s (%X)", fragments[i].get(),
            checking.get(), lookupHash.ToUint32()));
     }
 
     for (uint32_t i = 0; i < cacheArray.Length(); i++) {
       LookupCache *cache = cacheArray[i];
-      bool has, fromCache;
+      bool has, fromCache, confirmed;
       uint32_t matchLength;
 
-      rv = cache->Has(lookupHash, &has, &matchLength, &fromCache);
+      rv = cache->Has(lookupHash, mTableFreshness, aFreshnessGuarantee,
+                      &has, &matchLength, &confirmed, &fromCache);
       NS_ENSURE_SUCCESS(rv, rv);
+
       if (has) {
         LookupResult *result = aResults.AppendElement();
         if (!result)
           return NS_ERROR_OUT_OF_MEMORY;
 
-        // For V2, there is no TTL for caching, so we use table freshness to
-        // decide if matching a completion should trigger a gethash request or not.
-        // For V4, this is done by Positive Caching & Negative Caching mechanism.
-        bool confirmed = false;
-        if (fromCache) {
-          cache->IsHashEntryConfirmed(lookupHash, mTableFreshness,
-                                      aFreshnessGuarantee, &confirmed);
-        }
-
         LOG(("Found a result in %s: %s",
              cache->TableName().get(),
              confirmed ? "confirmed." : "Not confirmed."));
 
         result->hash.complete = lookupHash;
         result->mConfirmed = confirmed;
         result->mTableName.Assign(cache->TableName());
         result->mPartialHashLength = confirmed ? COMPLETE_SIZE : matchLength;
@@ -1328,16 +1321,21 @@ Classifier::UpdateTableV4(nsTArray<Table
   }
 
   LookupCacheV4* lookupCache =
     LookupCache::Cast<LookupCacheV4>(GetLookupCacheForUpdate(aTable));
   if (!lookupCache) {
     return NS_ERROR_UC_UPDATE_TABLE_NOT_FOUND;
   }
 
+  // Remove cache entries whose negative cache time is expired when update.
+  // We don't check if positive cache time is expired here because we want to
+  // keep the eviction rule simple when doing an update.
+  lookupCache->InvalidateExpiredCacheEntry();
+
   nsresult rv = NS_OK;
 
   // If there are multiple updates for the same table, prefixes1 & prefixes2
   // will act as input and output in turn to reduce memory copy overhead.
   PrefixStringMap prefixes1, prefixes2;
   PrefixStringMap* input = &prefixes1;
   PrefixStringMap* output = &prefixes2;
 
@@ -1418,18 +1416,29 @@ Classifier::UpdateCache(TableUpdate* aUp
   nsAutoCString table(aUpdate->TableName());
   LOG(("Classifier::UpdateCache(%s)", table.get()));
 
   LookupCache *lookupCache = GetLookupCache(table);
   if (!lookupCache) {
     return NS_ERROR_FAILURE;
   }
 
-  auto updateV2 = TableUpdate::Cast<TableUpdateV2>(aUpdate);
-  lookupCache->AddCompletionsToCache(updateV2->AddCompletes());
+  auto lookupV2 = LookupCache::Cast<LookupCacheV2>(lookupCache);
+  if (lookupV2) {
+    auto updateV2 = TableUpdate::Cast<TableUpdateV2>(aUpdate);
+    lookupV2->AddCompletionsToCache(updateV2->AddCompletes());
+  } else {
+    auto lookupV4 = LookupCache::Cast<LookupCacheV4>(lookupCache);
+    if (!lookupV4) {
+      return NS_ERROR_FAILURE;
+    }
+
+    auto updateV4 = TableUpdate::Cast<TableUpdateV4>(aUpdate);
+    lookupV4->AddFullHashResponseToCache(updateV4->FullHashResponse());
+  }
 
 #if defined(DEBUG)
   lookupCache->DumpCache();
 #endif
 
   return NS_OK;
 }
 

--- a/toolkit/components/url-classifier/LookupCache.cpp
+++ b/toolkit/components/url-classifier/LookupCache.cpp
@@ -92,44 +92,16 @@ LookupCache::UpdateRootDirHandle(nsIFile
     LOG(("Private store directory for %s is %s", mTableName.get(),
                                                  NS_ConvertUTF16toUTF8(path).get()));
   }
 
   return rv;
 }
 
 nsresult
-LookupCache::AddCompletionsToCache(AddCompleteArray& aAddCompletes)
-{
-  for (uint32_t i = 0; i < aAddCompletes.Length(); i++) {
-    if (mGetHashCache.BinaryIndexOf(aAddCompletes[i].CompleteHash()) == mGetHashCache.NoIndex) {
-      mGetHashCache.AppendElement(aAddCompletes[i].CompleteHash());
-    }
-  }
-  mGetHashCache.Sort();
-
-  return NS_OK;
-}
-
-#if defined(DEBUG)
-void
-LookupCache::DumpCache()
-{
-  if (!LOG_ENABLED())
-    return;
-
-  for (uint32_t i = 0; i < mGetHashCache.Length(); i++) {
-    nsAutoCString str;
-    mGetHashCache[i].ToHexString(str);
-    LOG(("Caches: %s", str.get()));
-  }
-}
-#endif
-
-nsresult
 LookupCache::WriteFile()
 {
   if (nsUrlClassifierDBService::ShutdownHasStarted()) {
     return NS_ERROR_ABORT;
   }
 
   nsCOMPtr<nsIFile> psFile;
   nsresult rv = mStoreDirectory->Clone(getter_AddRefs(psFile));
@@ -147,22 +119,16 @@ LookupCache::WriteFile()
 void
 LookupCache::ClearAll()
 {
   ClearCache();
   ClearPrefixes();
   mPrimed = false;
 }
 
-void
-LookupCache::ClearCache()
-{
-  mGetHashCache.Clear();
-}
-
 /* static */ bool
 LookupCache::IsCanonicalizedIP(const nsACString& aHost)
 {
   // The canonicalization process will have left IP addresses in dotted
   // decimal with no surprises.
   uint32_t i1, i2, i3, i4;
   char c;
   if (PR_sscanf(PromiseFlatCString(aHost).get(), "%u.%u.%u.%u%c",
@@ -396,20 +362,22 @@ void
 LookupCacheV2::ClearAll()
 {
   LookupCache::ClearAll();
   mUpdateCompletions.Clear();
 }
 
 nsresult
 LookupCacheV2::Has(const Completion& aCompletion,
+                   const TableFreshnessMap& aTableFreshness,
+                   uint32_t aFreshnessGuarantee,
                    bool* aHas, uint32_t* aMatchLength,
-                   bool* aFromCache)
+                   bool* aConfirmed, bool* aFromCache)
 {
-  *aHas = *aFromCache = false;
+  *aHas = *aConfirmed = *aFromCache = false;
   *aMatchLength = 0;
 
   uint32_t prefix = aCompletion.ToUint32();
 
   bool found;
   nsresult rv = mPrefixSet->Contains(prefix, &found);
   NS_ENSURE_SUCCESS(rv, rv);
 
@@ -421,40 +389,30 @@ LookupCacheV2::Has(const Completion& aCo
   }
 
   if ((mGetHashCache.BinaryIndexOf(aCompletion) != nsTArray<Completion>::NoIndex) ||
       (mUpdateCompletions.BinaryIndexOf(aCompletion) != nsTArray<Completion>::NoIndex)) {
     LOG(("Complete in %s", mTableName.get()));
     *aFromCache = true;
     *aHas = true;
     *aMatchLength = COMPLETE_SIZE;
+
+    int64_t ageSec; // in seconds
+    if (aTableFreshness.Get(mTableName, &ageSec)) {
+      int64_t nowSec = (PR_Now() / PR_USEC_PER_SEC);
+      MOZ_ASSERT(ageSec <= nowSec);
+
+      // Considered completion as unsafe if its table is up-to-date.
+      *aConfirmed = (nowSec - ageSec) < aFreshnessGuarantee;
+    }
   }
 
   return NS_OK;
 }
 
-void
-LookupCacheV2::IsHashEntryConfirmed(const Completion& aEntry,
-                                    const TableFreshnessMap& aTableFreshness,
-                                    uint32_t aFreshnessGuarantee,
-                                    bool* aConfirmed)
-{
-  int64_t age; // in seconds
-  bool found = aTableFreshness.Get(mTableName, &age);
-  if (!found) {
-    *aConfirmed = false;
-  } else {
-    int64_t now = (PR_Now() / PR_USEC_PER_SEC);
-    MOZ_ASSERT(age <= now);
-
-    // Considered completion as unsafe if its table is up-to-date.
-    *aConfirmed = (now - age) < aFreshnessGuarantee;
-  }
-}
-
 bool
 LookupCacheV2::IsEmpty()
 {
   bool isEmpty;
   mPrefixSet->IsEmpty(&isEmpty);
   return isEmpty;
 }
 
@@ -490,16 +448,29 @@ LookupCacheV2::GetPrefixes(FallibleTArra
     // This can happen if its a new table, so no error.
     LOG(("GetPrefixes from empty LookupCache"));
     return NS_OK;
   }
   return mPrefixSet->GetPrefixesNative(aAddPrefixes);
 }
 
 nsresult
+LookupCacheV2::AddCompletionsToCache(AddCompleteArray& aAddCompletes)
+{
+  for (uint32_t i = 0; i < aAddCompletes.Length(); i++) {
+    if (mGetHashCache.BinaryIndexOf(aAddCompletes[i].CompleteHash()) == mGetHashCache.NoIndex) {
+      mGetHashCache.AppendElement(aAddCompletes[i].CompleteHash());
+    }
+  }
+  mGetHashCache.Sort();
+
+  return NS_OK;
+}
+
+nsresult
 LookupCacheV2::ReadCompletions()
 {
   HashStore store(mTableName, mProvider, mRootStoreDirectory);
 
   nsresult rv = store.Open();
   NS_ENSURE_SUCCESS(rv, rv);
 
   mUpdateCompletions.Clear();
@@ -507,16 +478,22 @@ LookupCacheV2::ReadCompletions()
   const AddCompleteArray& addComplete = store.AddCompletes();
   for (uint32_t i = 0; i < addComplete.Length(); i++) {
     mUpdateCompletions.AppendElement(addComplete[i].complete);
   }
 
   return NS_OK;
 }
 
+void
+LookupCacheV2::ClearCache()
+{
+  mGetHashCache.Clear();
+}
+
 nsresult
 LookupCacheV2::ClearPrefixes()
 {
   return mPrefixSet->SetPrefixes(nullptr, 0);
 }
 
 nsresult
 LookupCacheV2::StoreToFile(nsIFile* aFile)
@@ -587,16 +564,31 @@ LookupCacheV2::ConstructPrefixSet(AddPre
 #endif
 
   mPrimed = true;
 
   return NS_OK;
 }
 
 #if defined(DEBUG)
+
+void
+LookupCacheV2::DumpCache()
+{
+  if (!LOG_ENABLED()) {
+    return;
+  }
+
+  for (uint32_t i = 0; i < mGetHashCache.Length(); i++) {
+    nsAutoCString str;
+    mGetHashCache[i].ToHexString(str);
+    LOG(("Caches: %s", str.get()));
+  }
+}
+
 void
 LookupCacheV2::DumpCompletions()
 {
   if (!LOG_ENABLED())
     return;
 
   for (uint32_t i = 0; i < mUpdateCompletions.Length(); i++) {
     nsAutoCString str;

--- a/toolkit/components/url-classifier/LookupCache.h
+++ b/toolkit/components/url-classifier/LookupCache.h
@@ -190,47 +190,41 @@ public:
   virtual ~LookupCache() {}
 
   const nsCString &TableName() const { return mTableName; }
 
   // The directory handle where we operate will
   // be moved away when a backup is made.
   nsresult UpdateRootDirHandle(nsIFile* aRootStoreDirectory);
 
-  // This will Clear() the passed arrays when done.
-  nsresult AddCompletionsToCache(AddCompleteArray& aAddCompletes);
-
   // Write data stored in lookup cache to disk.
   nsresult WriteFile();
 
-  // Clear completions retrieved from gethash request.
-  void ClearCache();
-
   bool IsPrimed() const { return mPrimed; };
 
-#if DEBUG
-  void DumpCache();
-#endif
-
   virtual nsresult Open();
   virtual nsresult Init() = 0;
   virtual nsresult ClearPrefixes() = 0;
   virtual nsresult Has(const Completion& aCompletion,
+                       const TableFreshnessMap& aTableFreshness,
+                       uint32_t aFreshnessGuarantee,
                        bool* aHas, uint32_t* aMatchLength,
-                       bool* aFromCache) = 0;
+                       bool* aConfirmed, bool* aFromCache) = 0;
 
-  virtual void IsHashEntryConfirmed(const Completion& aEntry,
-                                    const TableFreshnessMap& aTableFreshness,
-                                    uint32_t aFreshnessGuarantee,
-                                    bool* aConfirmed) = 0;
+  // Clear completions retrieved from gethash request.
+  virtual void ClearCache() = 0;
 
   virtual bool IsEmpty() = 0;
 
   virtual void ClearAll();
 
+#if DEBUG
+  virtual void DumpCache() = 0;
+#endif
+
   template<typename T>
   static T* Cast(LookupCache* aThat) {
     return ((aThat && T::VER == aThat->Ver()) ? reinterpret_cast<T*>(aThat) : nullptr);
   }
 
 private:
   nsresult LoadPrefixSet();
 
@@ -242,52 +236,52 @@ private:
 
 protected:
   bool mPrimed;
   nsCString mTableName;
   nsCString mProvider;
   nsCOMPtr<nsIFile> mRootStoreDirectory;
   nsCOMPtr<nsIFile> mStoreDirectory;
 
-  // Full length hashes obtained in gethash request
-  CompletionArray mGetHashCache;
-
   // For gtest to inspect private members.
   friend class PerProviderDirectoryTestUtils;
 };
 
 class LookupCacheV2 final : public LookupCache
 {
 public:
   explicit LookupCacheV2(const nsACString& aTableName,
                          const nsACString& aProvider,
                          nsIFile* aStoreFile)
     : LookupCache(aTableName, aProvider, aStoreFile) {}
   ~LookupCacheV2() {}
 
   virtual nsresult Init() override;
   virtual nsresult Open() override;
+  virtual void ClearCache() override;
   virtual void ClearAll() override;
   virtual nsresult Has(const Completion& aCompletion,
+                       const TableFreshnessMap& aTableFreshness,
+                       uint32_t aFreshnessGuarantee,
                        bool* aHas, uint32_t* aMatchLength,
-                       bool* aFromCache) override;
-
-  virtual void IsHashEntryConfirmed(const Completion& aEntry,
-                                    const TableFreshnessMap& aTableFreshness,
-                                    uint32_t aFreshnessGuarantee,
-                                    bool* aConfirmed) override;
+                       bool* aConfirmed, bool* aFromCache) override;
 
   virtual bool IsEmpty() override;
 
   nsresult Build(AddPrefixArray& aAddPrefixes,
                  AddCompleteArray& aAddCompletes);
 
   nsresult GetPrefixes(FallibleTArray<uint32_t>& aAddPrefixes);
 
+  // This will Clear() the passed arrays when done.
+  nsresult AddCompletionsToCache(AddCompleteArray& aAddCompletes);
+
 #if DEBUG
+  virtual void DumpCache() override;
+
   void DumpCompletions();
 #endif
 
   static const int VER;
 
 protected:
   nsresult ReadCompletions();
 
@@ -303,14 +297,17 @@ private:
   // This will Clear() aAddPrefixes when done.
   nsresult ConstructPrefixSet(AddPrefixArray& aAddPrefixes);
 
   // Full length hashes obtained in update request
   CompletionArray mUpdateCompletions;
 
   // Set of prefixes known to be in the database
   RefPtr<nsUrlClassifierPrefixSet> mPrefixSet;
+
+  // Full length hashes obtained in gethash request
+  CompletionArray mGetHashCache;
 };
 
 } // namespace safebrowsing
 } // namespace mozilla
 
 #endif

--- a/toolkit/components/url-classifier/LookupCacheV4.cpp
+++ b/toolkit/components/url-classifier/LookupCacheV4.cpp
@@ -75,53 +75,107 @@ LookupCacheV4::Init()
   nsresult rv = mVLPrefixSet->Init(mTableName);
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
 LookupCacheV4::Has(const Completion& aCompletion,
+                   const TableFreshnessMap& aTableFreshness,
+                   uint32_t aFreshnessGuarantee,
                    bool* aHas, uint32_t* aMatchLength,
-                   bool* aFromCache)
+                   bool* aConfirmed, bool* aFromCache)
 {
-  *aHas = *aFromCache = false;
+  *aHas = *aConfirmed = *aFromCache = false;
   *aMatchLength = 0;
 
   uint32_t length = 0;
   nsDependentCSubstring fullhash;
   fullhash.Rebind((const char *)aCompletion.buf, COMPLETE_SIZE);
 
   nsresult rv = mVLPrefixSet->Matches(fullhash, &length);
   NS_ENSURE_SUCCESS(rv, rv);
 
+  MOZ_ASSERT(length == 0 || (length >= PREFIX_SIZE && length <= COMPLETE_SIZE));
+
   *aHas = length >= PREFIX_SIZE;
   *aMatchLength = length;
 
   if (LOG_ENABLED()) {
     uint32_t prefix = aCompletion.ToUint32();
     LOG(("Probe in V4 %s: %X, found %d, complete %d", mTableName.get(),
           prefix, *aHas, length == COMPLETE_SIZE));
   }
 
-  // TODO : Bug 1311935 - Implement v4 caching
+  // Check if fullhash match any prefix in the local database
+  if (!(*aHas)) {
+    return NS_OK;
+  }
+
+  // We always send 4-bytes for completion(Bug 1323953) so the prefix used to
+  // lookup for cache should be 4-bytes too.
+  nsDependentCSubstring prefix(reinterpret_cast<const char*>(aCompletion.buf),
+                               PREFIX_SIZE);
+
+  // Check if prefix can be found in cache.
+  CachedFullHashResponse* fullHashResponse = mCache.Get(prefix);
+  if (!fullHashResponse) {
+    return NS_OK;
+  }
+
+  *aFromCache = true;
+
+  int64_t nowSec = PR_Now() / PR_USEC_PER_SEC;
+  int64_t expiryTime;
+
+  FullHashExpiryCache& fullHashes = fullHashResponse->fullHashes;
+  nsDependentCSubstring completion(
+    reinterpret_cast<const char*>(aCompletion.buf), COMPLETE_SIZE);
+
+  // Check if we can find the fullhash in positive cache
+  if (fullHashes.Get(completion, &expiryTime)) {
+    if (nowSec <= expiryTime) {
+      // Url is NOT safe.
+      *aConfirmed = true;
+      LOG(("Found a valid fullhash in the positive cache"));
+    } else {
+      // Trigger a gethash request in this case(aConfirmed is false).
+      LOG(("Found an expired fullhash in the positive cache"));
+
+      // Remove fullhash entry from the cache when the negative cache
+      // is also expired because whether or not the fullhash is cached
+      // locally, we will need to consult the server next time we
+      // lookup this hash. We may as well remove it from our cache.
+      if (fullHashResponse->negativeCacheExpirySec < expiryTime) {
+        fullHashes.Remove(completion);
+        if (fullHashes.Count() == 0 &&
+            fullHashResponse->negativeCacheExpirySec < nowSec) {
+          mCache.Remove(prefix);
+        }
+      }
+    }
+    return NS_OK;
+  }
+
+  // Check negative cache.
+  if (fullHashResponse->negativeCacheExpirySec >= nowSec) {
+    // Url is safe.
+    LOG(("Found a valid prefix in the negative cache"));
+    *aHas = false;
+  } else {
+    LOG(("Found an expired prefix in the negative cache"));
+    if (fullHashes.Count() == 0) {
+      mCache.Remove(prefix);
+    }
+  }
 
   return NS_OK;
 }
 
-void
-LookupCacheV4::IsHashEntryConfirmed(const Completion& aEntry,
-                                    const TableFreshnessMap& aTableFreshness,
-                                    uint32_t aFreshnessGuarantee,
-                                    bool* aConfirmed)
-{
-  // TODO : Bug 1311935 - Implement v4 caching
-  *aConfirmed = true;
-}
-
 bool
 LookupCacheV4::IsEmpty()
 {
   bool isEmpty;
   mVLPrefixSet->IsEmpty(&isEmpty);
   return isEmpty;
 }
 
@@ -325,16 +379,27 @@ LookupCacheV4::ApplyUpdate(TableUpdateV4
     LOG(("Checksum mismatch after applying partial update"));
     return NS_ERROR_UC_UPDATE_CHECKSUM_MISMATCH;
   }
 
   return NS_OK;
 }
 
 nsresult
+LookupCacheV4::AddFullHashResponseToCache(const FullHashResponseMap& aResponseMap)
+{
+  for (auto iter = aResponseMap.ConstIter(); !iter.Done(); iter.Next()) {
+    CachedFullHashResponse* response = mCache.LookupOrAdd(iter.Key());
+    *response = *(iter.Data());
+  }
+
+  return NS_OK;
+}
+
+nsresult
 LookupCacheV4::InitCrypto(nsCOMPtr<nsICryptoHash>& aCrypto)
 {
   nsresult rv;
   aCrypto = do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID, &rv);
   if (NS_WARN_IF(NS_FAILED(rv))) {
     return rv;
   }
 
@@ -534,16 +599,94 @@ LookupCacheV4::LoadMetadata(nsACString& 
   if (NS_FAILED(rv)) {
     LOG(("Failed to read checksum."));
     return rv;
   }
 
   return rv;
 }
 
+void
+LookupCacheV4::ClearCache()
+{
+  mCache.Clear();
+}
+
+// This function remove cache entries whose negative cache time is expired.
+// It is possible that a cache entry whose positive cache time is not yet
+// expired but still being removed after calling this API. Right now we call
+// this on every update.
+void
+LookupCacheV4::InvalidateExpiredCacheEntry()
+{
+  int64_t nowSec = PR_Now() / PR_USEC_PER_SEC;
+
+  for (auto iter = mCache.Iter(); !iter.Done(); iter.Next()) {
+    CachedFullHashResponse* response = iter.Data();
+    if (response->negativeCacheExpirySec < nowSec) {
+      iter.Remove();
+    }
+  }
+}
+
+#if defined(DEBUG)
+static
+void CStringToHexString(const nsACString& aIn, nsACString& aOut)
+{
+  static const char* const lut = "0123456789ABCDEF";
+  // 32 bytes is the longest hash
+  size_t len = COMPLETE_SIZE;
+
+  aOut.SetCapacity(2 * len);
+  for (size_t i = 0; i < aIn.Length(); ++i) {
+    const char c = static_cast<const char>(aIn[i]);
+    aOut.Append(lut[(c >> 4) & 0x0F]);
+    aOut.Append(lut[c & 15]);
+  }
+}
+
+static
+nsCString GetFormattedTimeString(int64_t aCurTimeSec)
+{
+  PRExplodedTime pret;
+  PR_ExplodeTime(aCurTimeSec * PR_USEC_PER_SEC, PR_GMTParameters, &pret);
+
+  return nsPrintfCString(
+         "%04d-%02d-%02d %02d:%02d:%02d UTC",
+         pret.tm_year, pret.tm_month + 1, pret.tm_mday,
+         pret.tm_hour, pret.tm_min, pret.tm_sec);
+}
+
+void
+LookupCacheV4::DumpCache()
+{
+  if (!LOG_ENABLED()) {
+    return;
+  }
+
+  for (auto iter = mCache.ConstIter(); !iter.Done(); iter.Next()) {
+    nsAutoCString strPrefix;
+    CStringToHexString(iter.Key(), strPrefix);
+
+    CachedFullHashResponse* response = iter.Data();
+    LOG(("Caches prefix: %s, Expire time: %s",
+         strPrefix.get(),
+         GetFormattedTimeString(response->negativeCacheExpirySec).get()));
+
+    FullHashExpiryCache& fullHashes = response->fullHashes;
+    for (auto iter2 = fullHashes.ConstIter(); !iter2.Done(); iter2.Next()) {
+      nsAutoCString strFullhash;
+      CStringToHexString(iter2.Key(), strFullhash);
+      LOG(("  - %s, Expire time: %s", strFullhash.get(),
+           GetFormattedTimeString(iter2.Data()).get()));
+    }
+  }
+}
+#endif
+
 VLPrefixSet::VLPrefixSet(const PrefixStringMap& aMap)
   : mCount(0)
 {
   for (auto iter = aMap.ConstIter(); !iter.Done(); iter.Next()) {
     uint32_t size = iter.Key();
     mMap.Put(size, new PrefixString(*iter.Data(), size));
     mCount += iter.Data()->Length() / size;
   }

--- a/toolkit/components/url-classifier/LookupCacheV4.h
+++ b/toolkit/components/url-classifier/LookupCacheV4.h
@@ -20,52 +20,61 @@ public:
   explicit LookupCacheV4(const nsACString& aTableName,
                          const nsACString& aProvider,
                          nsIFile* aStoreFile)
     : LookupCache(aTableName, aProvider, aStoreFile) {}
   ~LookupCacheV4() {}
 
   virtual nsresult Init() override;
   virtual nsresult Has(const Completion& aCompletion,
+                       const TableFreshnessMap& aTableFreshness,
+                       uint32_t aFreshnessGuarantee,
                        bool* aHas, uint32_t* aMatchLength,
-                       bool* aFromCache) override;
+                       bool* aConfirmed, bool* aFromCache) override;
 
-  virtual void IsHashEntryConfirmed(const Completion& aEntry,
-                                    const TableFreshnessMap& aTableFreshness,
-                                    uint32_t aFreshnessGuarantee,
-                                    bool* aConfirmed) override;
+  virtual void ClearCache() override;
+
+#if DEBUG
+  virtual void DumpCache() override;
+#endif
 
   virtual bool IsEmpty() override;
 
   nsresult Build(PrefixStringMap& aPrefixMap);
 
   nsresult GetPrefixes(PrefixStringMap& aPrefixMap);
   nsresult GetFixedLengthPrefixes(FallibleTArray<uint32_t>& aPrefixes);
 
   // ApplyUpdate will merge data stored in aTableUpdate with prefixes in aInputMap.
   nsresult ApplyUpdate(TableUpdateV4* aTableUpdate,
                        PrefixStringMap& aInputMap,
                        PrefixStringMap& aOutputMap);
 
+  nsresult AddFullHashResponseToCache(const FullHashResponseMap& aResponseMap);
+
   nsresult WriteMetadata(TableUpdateV4* aTableUpdate);
   nsresult LoadMetadata(nsACString& aState, nsACString& aChecksum);
 
+  void InvalidateExpiredCacheEntry();
+
   static const int VER;
 
 protected:
   virtual nsresult ClearPrefixes() override;
   virtual nsresult StoreToFile(nsIFile* aFile) override;
   virtual nsresult LoadFromFile(nsIFile* aFile) override;
   virtual size_t SizeOfPrefixSet() override;
 
 private:
   virtual int Ver() const override { return VER; }
 
   nsresult InitCrypto(nsCOMPtr<nsICryptoHash>& aCrypto);
   nsresult VerifyChecksum(const nsACString& aChecksum);
 
   RefPtr<VariableLengthPrefixSet> mVLPrefixSet;
+
+  FullHashResponseMap mCache;
 };
 
 } // namespace safebrowsing
 } // namespace mozilla
 
 #endif

--- a/toolkit/components/url-classifier/VariableLengthPrefixSet.cpp
+++ b/toolkit/components/url-classifier/VariableLengthPrefixSet.cpp
@@ -183,16 +183,17 @@ VariableLengthPrefixSet::Matches(const n
   if (found) {
     *aLength = PREFIX_SIZE_FIXED;
     return NS_OK;
   }
 
   for (auto iter = mVLPrefixSet.ConstIter(); !iter.Done(); iter.Next()) {
     if (BinarySearch(aFullHash, *iter.Data(), iter.Key())) {
       *aLength = iter.Key();
+      MOZ_ASSERT(*aLength > 4);
       return NS_OK;
     }
   }
 
   return NS_OK;
 }
 
 nsresult

--- a/toolkit/components/url-classifier/tests/gtest/TestLookupCacheV4.cpp
+++ b/toolkit/components/url-classifier/tests/gtest/TestLookupCacheV4.cpp
@@ -42,23 +42,28 @@ TestHasPrefix(const _Fragment& aFragment
 
   RunTestInNewThread([&] () -> void {
     UniquePtr<LookupCache> cache = SetupLookupCacheV4(array);
 
     Completion lookupHash;
     nsCOMPtr<nsICryptoHash> cryptoHash = do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID);
     lookupHash.FromPlaintext(aFragment, cryptoHash);
 
-    bool has, fromCache;
+    bool has, confirmed, fromCache;
     uint32_t matchLength;
-    nsresult rv = cache->Has(lookupHash, &has, &matchLength, &fromCache);
+    // Freshness is not used in V4 so we just put dummy values here.
+    TableFreshnessMap dummy;
+    nsresult rv = cache->Has(lookupHash, dummy, 0,
+                             &has, &matchLength, &confirmed, &fromCache);
 
     EXPECT_EQ(rv, NS_OK);
     EXPECT_EQ(has, aExpectedHas);
     EXPECT_EQ(matchLength == COMPLETE_SIZE, aExpectedComplete);
+    EXPECT_EQ(confirmed, false);
+    EXPECT_EQ(fromCache, false);
 
     cache->ClearAll();
   });
 
 }
 
 TEST(LookupCacheV4, HasComplete)
 {