Adding upstream version 124.0.1.upstream/124.0.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

20 files changed, 3788 insertions, 0 deletions

diff --git a/toolkit/components/url-classifier/tests/gtest/Common.cpp b/toolkit/components/url-classifier/tests/gtest/Common.cpp
new file mode 100644
index 0000000000..172ded051f
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/Common.cpp
@@ -0,0 +1,219 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "Common.h"
+
+#include "Classifier.h"
+#include "HashStore.h"
+#include "mozilla/Components.h"
+#include "mozilla/SpinEventLoopUntil.h"
+#include "mozilla/Unused.h"
+#include "nsAppDirectoryServiceDefs.h"
+#include "nsIThread.h"
+#include "nsTArray.h"
+#include "nsThreadUtils.h"
+#include "nsUrlClassifierUtils.h"
+
+using namespace mozilla;
+using namespace mozilla::safebrowsing;
+
+nsresult SyncApplyUpdates(TableUpdateArray& aUpdates) {
+  // We need to spin a new thread specifically because the callback
+  // will be on the caller thread. If we call Classifier::AsyncApplyUpdates
+  // and wait on the same thread, this function will never return.
+
+  nsresult ret = NS_ERROR_FAILURE;
+  bool done = false;
+  auto onUpdateComplete = [&done, &ret](nsresult rv) {
+    // We are on the "ApplyUpdate" thread. Post an event to main thread
+    // so that we can avoid busy waiting on the main thread.
+    nsCOMPtr<nsIRunnable> r =
+        NS_NewRunnableFunction("SyncApplyUpdates", [&done, &ret, rv] {
+          ret = rv;
+          done = true;
+        });
+    NS_DispatchToMainThread(r);
+  };
+
+  nsCOMPtr<nsIFile> file;
+  NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
+
+  nsCOMPtr<nsIRunnable> r = NS_NewRunnableFunction("SyncApplyUpdates", [&]() {
+    RefPtr<Classifier> classifier = new Classifier();
+    classifier->Open(*file);
+
+    nsresult rv = classifier->AsyncApplyUpdates(aUpdates, onUpdateComplete);
+    if (NS_FAILED(rv)) {
+      onUpdateComplete(rv);
+    }
+  });
+
+  nsCOMPtr<nsIThread> testingThread;
+  NS_NewNamedThread("ApplyUpdates", getter_AddRefs(testingThread));
+  if (!testingThread) {
+    return NS_ERROR_FAILURE;
+  }
+
+  testingThread->Dispatch(r, NS_DISPATCH_NORMAL);
+
+  // NS_NewCheckSummedOutputStream in HashStore::WriteFile
+  // will synchronously init NS_CRYPTO_HASH_CONTRACTID on
+  // the main thread. As a result we have to keep processing
+  // pending event until |done| becomes true. If there's no
+  // more pending event, what we only can do is wait.
+  MOZ_ALWAYS_TRUE(SpinEventLoopUntil("url-classifier:SyncApplyUpdates"_ns,
+                                     [&]() { return done; }));
+
+  return ret;
+}
+
+already_AddRefed<nsIFile> GetFile(const nsTArray<nsString>& path) {
+  nsCOMPtr<nsIFile> file;
+  nsresult rv =
+      NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
+  if (NS_WARN_IF(NS_FAILED(rv))) {
+    return nullptr;
+  }
+
+  for (uint32_t i = 0; i < path.Length(); i++) {
+    file->Append(path[i]);
+  }
+  return file.forget();
+}
+
+void ApplyUpdate(TableUpdateArray& updates) {
+  // Force nsUrlClassifierUtils loading on main thread
+  // because nsIUrlClassifierDBService will not run in advance
+  // in gtest.
+  nsUrlClassifierUtils::GetInstance();
+
+  SyncApplyUpdates(updates);
+}
+
+void ApplyUpdate(TableUpdate* update) {
+  TableUpdateArray updates = {update};
+  ApplyUpdate(updates);
+}
+
+nsresult PrefixArrayToPrefixStringMap(const _PrefixArray& aPrefixArray,
+                                      PrefixStringMap& aOut) {
+  aOut.Clear();
+
+  // Buckets are keyed by prefix length and contain an array of
+  // all prefixes of that length.
+  nsClassHashtable<nsUint32HashKey, _PrefixArray> table;
+  for (const auto& prefix : aPrefixArray) {
+    _PrefixArray* array = table.GetOrInsertNew(prefix.Length());
+    array->AppendElement(prefix);
+  }
+
+  // The resulting map entries will be a concatenation of all
+  // prefix data for the prefixes of a given size.
+  for (const auto& entry : table) {
+    uint32_t size = entry.GetKey();
+    uint32_t count = entry.GetData()->Length();
+
+    auto str = MakeUnique<_Prefix>();
+    str->SetLength(size * count);
+
+    char* dst = str->BeginWriting();
+
+    entry.GetData()->Sort();
+    for (uint32_t i = 0; i < count; i++) {
+      memcpy(dst, entry.GetData()->ElementAt(i).get(), size);
+      dst += size;
+    }
+
+    aOut.InsertOrUpdate(size, std::move(str));
+  }
+
+  return NS_OK;
+}
+
+nsresult PrefixArrayToAddPrefixArray(const _PrefixArray& aPrefixArray,
+                                     AddPrefixArray& aOut) {
+  aOut.Clear();
+
+  for (const auto& prefix : aPrefixArray) {
+    // Create prefix hash from string
+    AddPrefix* add = aOut.AppendElement(fallible);
+    if (!add) {
+      return NS_ERROR_OUT_OF_MEMORY;
+    }
+
+    add->addChunk = 1;
+    add->prefix.Assign(prefix);
+  }
+
+  EntrySort(aOut);
+
+  return NS_OK;
+}
+
+_Prefix CreatePrefixFromURL(const char* aURL, uint8_t aPrefixSize) {
+  return CreatePrefixFromURL(nsCString(aURL), aPrefixSize);
+}
+
+_Prefix CreatePrefixFromURL(const nsCString& aURL, uint8_t aPrefixSize) {
+  Completion complete;
+  complete.FromPlaintext(aURL);
+
+  _Prefix prefix;
+  prefix.Assign((const char*)complete.buf, aPrefixSize);
+  return prefix;
+}
+
+void CheckContent(LookupCacheV4* aCache, const _PrefixArray& aPrefixArray) {
+  PrefixStringMap vlPSetMap;
+  aCache->GetPrefixes(vlPSetMap);
+
+  PrefixStringMap expected;
+  PrefixArrayToPrefixStringMap(aPrefixArray, expected);
+
+  for (const auto& entry : vlPSetMap) {
+    nsCString* expectedPrefix = expected.Get(entry.GetKey());
+    nsCString* resultPrefix = entry.GetWeak();
+
+    ASSERT_TRUE(resultPrefix->Equals(*expectedPrefix));
+  }
+}
+
+nsresult BuildLookupCache(const RefPtr<Classifier>& classifier,
+                          const nsACString& aTable,
+                          _PrefixArray& aPrefixArray) {
+  RefPtr<LookupCache> cache = classifier->GetLookupCache(aTable, false);
+  if (!cache) {
+    return NS_ERROR_FAILURE;
+  }
+
+  if (LookupCache::Cast<LookupCacheV4>(cache)) {
+    // V4
+    RefPtr<LookupCacheV4> cacheV4 = LookupCache::Cast<LookupCacheV4>(cache);
+
+    PrefixStringMap map;
+    PrefixArrayToPrefixStringMap(aPrefixArray, map);
+    return cacheV4->Build(map);
+  } else {
+    // V2
+    RefPtr<LookupCacheV2> cacheV2 = LookupCache::Cast<LookupCacheV2>(cache);
+
+    AddPrefixArray addPrefixes;
+    AddCompleteArray addComples;
+
+    PrefixArrayToAddPrefixArray(aPrefixArray, addPrefixes);
+    return cacheV2->Build(addPrefixes, addComples);
+  }
+}
+
+RefPtr<Classifier> GetClassifier() {
+  nsCOMPtr<nsIFile> file;
+  NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
+
+  RefPtr<Classifier> classifier = new Classifier();
+  nsresult rv = classifier->Open(*file);
+  EXPECT_TRUE(rv == NS_OK);
+
+  return classifier;
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/Common.h b/toolkit/components/url-classifier/tests/gtest/Common.h
new file mode 100644
index 0000000000..9c196abafa
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/Common.h
@@ -0,0 +1,147 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef nsUrlClassifierGTestCommon_h__
+#define nsUrlClassifierGTestCommon_h__
+
+#include "Entries.h"
+#include "nsAppDirectoryServiceDefs.h"
+#include "nsIFile.h"
+#include "nsTArray.h"
+#include "nsIThread.h"
+#include "nsThreadUtils.h"
+#include "HashStore.h"
+
+#include "gtest/gtest.h"
+#include "mozilla/gtest/MozAssertions.h"
+#include "LookupCacheV4.h"
+
+using namespace mozilla::safebrowsing;
+
+namespace mozilla {
+namespace safebrowsing {
+class Classifier;
+class LookupCacheV4;
+class TableUpdate;
+}  // namespace safebrowsing
+}  // namespace mozilla
+
+#define GTEST_SAFEBROWSING_DIR "safebrowsing"_ns
+#define GTEST_TABLE_V4 "gtest-malware-proto"_ns
+#define GTEST_TABLE_V2 "gtest-malware-simple"_ns
+
+template <typename Function>
+void RunTestInNewThread(Function&& aFunction) {
+  nsCOMPtr<nsIRunnable> r = NS_NewRunnableFunction(
+      "RunTestInNewThread", std::forward<Function>(aFunction));
+  nsCOMPtr<nsIThread> testingThread;
+  nsresult rv =
+      NS_NewNamedThread("Testing Thread", getter_AddRefs(testingThread), r);
+  ASSERT_EQ(rv, NS_OK);
+  testingThread->Shutdown();
+}
+
+// Synchronously apply updates by calling Classifier::AsyncApplyUpdates.
+nsresult SyncApplyUpdates(Classifier* aClassifier,
+                          nsTArray<TableUpdate*>* aUpdates);
+nsresult SyncApplyUpdates(TableUpdateArray& aUpdates);
+
+// Return nsIFile with root directory - NS_APP_USER_PROFILE_50_DIR
+// Sub-directories are passed in path argument.
+already_AddRefed<nsIFile> GetFile(const nsTArray<nsString>& aPath);
+
+// ApplyUpdate will call |ApplyUpdates| of Classifier within a new thread
+void ApplyUpdate(nsTArray<TableUpdate*>& aUpdates);
+
+void ApplyUpdate(TableUpdate* aUpdate);
+
+/**
+ * Prefix processing utility functions
+ */
+
+typedef nsCString _Prefix;
+typedef nsTArray<nsCString> _PrefixArray;
+
+// This function converts a lexigraphic-sorted prefixes array
+// to a hash table keyed by prefix size(PrefixStringMap is defined in Entries.h)
+nsresult PrefixArrayToPrefixStringMap(const _PrefixArray& aPrefixArray,
+                                      PrefixStringMap& aOut);
+
+// This function converts a lexigraphic-sorted prefixes array
+// to an array containing AddPrefix(AddPrefix is defined in Entries.h)
+nsresult PrefixArrayToAddPrefixArray(const _PrefixArray& aPrefixArray,
+                                     AddPrefixArray& aOut);
+
+_Prefix CreatePrefixFromURL(const char* aURL, uint8_t aPrefixSize);
+
+_Prefix CreatePrefixFromURL(const nsCString& aURL, uint8_t aPrefixSize);
+
+// To test if the content is equal
+void CheckContent(LookupCacheV4* cache, const _PrefixArray& aPrefixArray);
+
+/**
+ * Utility function to generate safebrowsing internal structure
+ */
+
+static inline nsresult BuildCache(LookupCacheV2* cache,
+                                  const _PrefixArray& aPrefixArray) {
+  AddPrefixArray prefixes;
+  AddCompleteArray completions;
+  nsresult rv = PrefixArrayToAddPrefixArray(aPrefixArray, prefixes);
+  if (NS_FAILED(rv)) {
+    return rv;
+  }
+
+  return cache->Build(prefixes, completions);
+}
+
+static inline nsresult BuildCache(LookupCacheV4* cache,
+                                  const _PrefixArray& aPrefixArray) {
+  PrefixStringMap map;
+  PrefixArrayToPrefixStringMap(aPrefixArray, map);
+  return cache->Build(map);
+}
+
+// Create a LookupCacheV4 object with sepecified prefix array.
+template <typename T>
+RefPtr<T> SetupLookupCache(const _PrefixArray& aPrefixArray,
+                           nsCOMPtr<nsIFile>& aFile) {
+  RefPtr<T> cache = new T(GTEST_TABLE_V4, ""_ns, aFile);
+
+  nsresult rv = cache->Init();
+  EXPECT_EQ(rv, NS_OK);
+
+  rv = BuildCache(cache, aPrefixArray);
+  EXPECT_EQ(rv, NS_OK);
+
+  return cache;
+}
+
+template <typename T>
+RefPtr<T> SetupLookupCache(const _PrefixArray& aPrefixArray) {
+  nsCOMPtr<nsIFile> file;
+  NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
+
+  file->AppendNative(GTEST_SAFEBROWSING_DIR);
+
+  RefPtr<T> cache = new T(GTEST_TABLE_V4, ""_ns, file);
+  nsresult rv = cache->Init();
+  EXPECT_EQ(rv, NS_OK);
+
+  rv = BuildCache(cache, aPrefixArray);
+  EXPECT_EQ(rv, NS_OK);
+
+  return cache;
+}
+
+/**
+ * Retrieve Classifer class
+ */
+RefPtr<Classifier> GetClassifier();
+
+nsresult BuildLookupCache(const RefPtr<Classifier>& aClassifier,
+                          const nsACString& aTable, _PrefixArray& aPrefixArray);
+
+#endif  // nsUrlClassifierGTestCommon_h__
diff --git a/toolkit/components/url-classifier/tests/gtest/TestCaching.cpp b/toolkit/components/url-classifier/tests/gtest/TestCaching.cpp
new file mode 100644
index 0000000000..520eb35dcb
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestCaching.cpp
@@ -0,0 +1,271 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "Common.h"
+#include "LookupCacheV4.h"
+
+#define EXPIRED_TIME_SEC (PR_Now() / PR_USEC_PER_SEC - 3600)
+#define NOTEXPIRED_TIME_SEC (PR_Now() / PR_USEC_PER_SEC + 3600)
+
+#define CACHED_URL "cache.com/"_ns
+#define NEG_CACHE_EXPIRED_URL "cache.negExpired.com/"_ns
+#define POS_CACHE_EXPIRED_URL "cache.posExpired.com/"_ns
+#define BOTH_CACHE_EXPIRED_URL "cache.negAndposExpired.com/"_ns
+
+static void SetupCacheEntry(LookupCacheV2* aLookupCache,
+                            const nsCString& aCompletion,
+                            bool aNegExpired = false,
+                            bool aPosExpired = false) {
+  AddCompleteArray completes;
+  AddCompleteArray emptyCompletes;
+  MissPrefixArray misses;
+  MissPrefixArray emptyMisses;
+
+  AddComplete* add = completes.AppendElement(mozilla::fallible);
+  add->complete.FromPlaintext(aCompletion);
+
+  Prefix* prefix = misses.AppendElement(mozilla::fallible);
+  prefix->FromPlaintext(aCompletion);
+
+  // Setup positive cache first otherwise negative cache expiry will be
+  // overwritten.
+  int64_t posExpirySec = aPosExpired ? EXPIRED_TIME_SEC : NOTEXPIRED_TIME_SEC;
+  aLookupCache->AddGethashResultToCache(completes, emptyMisses, posExpirySec);
+
+  int64_t negExpirySec = aNegExpired ? EXPIRED_TIME_SEC : NOTEXPIRED_TIME_SEC;
+  aLookupCache->AddGethashResultToCache(emptyCompletes, misses, negExpirySec);
+}
+
+static void SetupCacheEntry(LookupCacheV4* aLookupCache,
+                            const nsCString& aCompletion,
+                            bool aNegExpired = false,
+                            bool aPosExpired = false) {
+  FullHashResponseMap map;
+
+  Prefix prefix;
+  prefix.FromPlaintext(aCompletion);
+
+  CachedFullHashResponse* response = map.GetOrInsertNew(prefix.ToUint32());
+
+  response->negativeCacheExpirySec =
+      aNegExpired ? EXPIRED_TIME_SEC : NOTEXPIRED_TIME_SEC;
+  response->fullHashes.InsertOrUpdate(
+      CreatePrefixFromURL(aCompletion, COMPLETE_SIZE),
+      aPosExpired ? EXPIRED_TIME_SEC : NOTEXPIRED_TIME_SEC);
+
+  aLookupCache->AddFullHashResponseToCache(map);
+}
+
+template <typename T>
+static void TestCache(const Completion aCompletion, bool aExpectedHas,
+                      bool aExpectedConfirmed, bool aExpectedInCache,
+                      T* aCache = nullptr) {
+  bool has, inCache, confirmed;
+  uint32_t matchLength;
+
+  if (aCache) {
+    aCache->Has(aCompletion, &has, &matchLength, &confirmed);
+    inCache = aCache->IsInCache(aCompletion.ToUint32());
+  } else {
+    _PrefixArray array = {CreatePrefixFromURL("cache.notexpired.com/", 10),
+                          CreatePrefixFromURL("cache.expired.com/", 8),
+                          CreatePrefixFromURL("gound.com/", 5),
+                          CreatePrefixFromURL("small.com/", 4)};
+
+    RefPtr<T> cache = SetupLookupCache<T>(array);
+
+    // Create an expired entry and a non-expired entry
+    SetupCacheEntry(cache, "cache.notexpired.com/"_ns);
+    SetupCacheEntry(cache, "cache.expired.com/"_ns, true, true);
+
+    cache->Has(aCompletion, &has, &matchLength, &confirmed);
+    inCache = cache->IsInCache(aCompletion.ToUint32());
+  }
+
+  EXPECT_EQ(has, aExpectedHas);
+  EXPECT_EQ(confirmed, aExpectedConfirmed);
+  EXPECT_EQ(inCache, aExpectedInCache);
+}
+
+template <typename T>
+static void TestCache(const nsCString& aURL, bool aExpectedHas,
+                      bool aExpectedConfirmed, bool aExpectedInCache,
+                      T* aCache = nullptr) {
+  Completion lookupHash;
+  lookupHash.FromPlaintext(aURL);
+
+  TestCache<T>(lookupHash, aExpectedHas, aExpectedConfirmed, aExpectedInCache,
+               aCache);
+}
+
+// This testcase check the returned result of |Has| API if fullhash cannot match
+// any prefix in the local database.
+TEST(UrlClassifierCaching, NotFound)
+{
+  TestCache<LookupCacheV2>("nomatch.com/"_ns, false, false, false);
+  TestCache<LookupCacheV4>("nomatch.com/"_ns, false, false, false);
+}
+
+// This testcase check the returned result of |Has| API if fullhash find a match
+// in the local database but not in the cache.
+TEST(UrlClassifierCaching, NotInCache)
+{
+  TestCache<LookupCacheV2>("gound.com/"_ns, true, false, false);
+  TestCache<LookupCacheV4>("gound.com/"_ns, true, false, false);
+}
+
+// This testcase check the returned result of |Has| API if fullhash matches
+// a cache entry in positive cache.
+TEST(UrlClassifierCaching, InPositiveCacheNotExpired)
+{
+  TestCache<LookupCacheV2>("cache.notexpired.com/"_ns, true, true, true);
+  TestCache<LookupCacheV4>("cache.notexpired.com/"_ns, true, true, true);
+}
+
+// This testcase check the returned result of |Has| API if fullhash matches
+// a cache entry in positive cache but that it is expired.
+TEST(UrlClassifierCaching, InPositiveCacheExpired)
+{
+  TestCache<LookupCacheV2>("cache.expired.com/"_ns, true, false, true);
+  TestCache<LookupCacheV4>("cache.expired.com/"_ns, true, false, true);
+}
+
+// This testcase check the returned result of |Has| API if fullhash matches
+// a cache entry in negative cache.
+TEST(UrlClassifierCaching, InNegativeCacheNotExpired)
+{
+  // Create a fullhash whose prefix matches the prefix in negative cache
+  // but completion doesn't match any fullhash in positive cache.
+
+  Completion prefix;
+  prefix.FromPlaintext("cache.notexpired.com/"_ns);
+
+  Completion fullhash;
+  fullhash.FromPlaintext("firefox.com/"_ns);
+
+  // Overwrite the 4-byte prefix of `fullhash` so that it conflicts with
+  // `prefix`. Since "cache.notexpired.com" is added to database in TestCache as
+  // a 10-byte prefix, we should copy more than 10 bytes to fullhash to ensure
+  // it can match the prefix in database.
+  memcpy(fullhash.buf, prefix.buf, 10);
+
+  TestCache<LookupCacheV2>(fullhash, false, false, true);
+  TestCache<LookupCacheV4>(fullhash, false, false, true);
+}
+
+// This testcase check the returned result of |Has| API if fullhash matches
+// a cache entry in negative cache but that entry is expired.
+TEST(UrlClassifierCaching, InNegativeCacheExpired)
+{
+  // Create a fullhash whose prefix is in the cache.
+
+  Completion prefix;
+  prefix.FromPlaintext("cache.expired.com/"_ns);
+
+  Completion fullhash;
+  fullhash.FromPlaintext("firefox.com/"_ns);
+
+  memcpy(fullhash.buf, prefix.buf, 10);
+
+  TestCache<LookupCacheV2>(fullhash, true, false, true);
+  TestCache<LookupCacheV4>(fullhash, true, false, true);
+}
+
+// This testcase create 4 cache entries.
+// 1. unexpired entry.
+// 2. an entry whose negative cache time is expired but whose positive cache
+//    is not expired.
+// 3. an entry whose positive cache time is expired
+// 4. an entry whose negative cache time and positive cache time are expired
+// After calling |InvalidateExpiredCacheEntry| API, entries with expired
+// negative time should be removed from cache(2 & 4)
+template <typename T>
+void TestInvalidateExpiredCacheEntry() {
+  _PrefixArray array = {CreatePrefixFromURL(CACHED_URL, 10),
+                        CreatePrefixFromURL(NEG_CACHE_EXPIRED_URL, 8),
+                        CreatePrefixFromURL(POS_CACHE_EXPIRED_URL, 5),
+                        CreatePrefixFromURL(BOTH_CACHE_EXPIRED_URL, 4)};
+  RefPtr<T> cache = SetupLookupCache<T>(array);
+
+  SetupCacheEntry(cache, CACHED_URL, false, false);
+  SetupCacheEntry(cache, NEG_CACHE_EXPIRED_URL, true, false);
+  SetupCacheEntry(cache, POS_CACHE_EXPIRED_URL, false, true);
+  SetupCacheEntry(cache, BOTH_CACHE_EXPIRED_URL, true, true);
+
+  // Before invalidate
+  TestCache<T>(CACHED_URL, true, true, true, cache.get());
+  TestCache<T>(NEG_CACHE_EXPIRED_URL, true, true, true, cache.get());
+  TestCache<T>(POS_CACHE_EXPIRED_URL, true, false, true, cache.get());
+  TestCache<T>(BOTH_CACHE_EXPIRED_URL, true, false, true, cache.get());
+
+  // Call InvalidateExpiredCacheEntry to remove cache entries whose negative
+  // cache time is expired
+  cache->InvalidateExpiredCacheEntries();
+
+  // After invalidate, NEG_CACHE_EXPIRED_URL & BOTH_CACHE_EXPIRED_URL should
+  // not be found in cache.
+  TestCache<T>(NEG_CACHE_EXPIRED_URL, true, false, false, cache.get());
+  TestCache<T>(BOTH_CACHE_EXPIRED_URL, true, false, false, cache.get());
+
+  // Other entries should remain the same result.
+  TestCache<T>(CACHED_URL, true, true, true, cache.get());
+  TestCache<T>(POS_CACHE_EXPIRED_URL, true, false, true, cache.get());
+}
+
+TEST(UrlClassifierCaching, InvalidateExpiredCacheEntryV2)
+{ TestInvalidateExpiredCacheEntry<LookupCacheV2>(); }
+
+TEST(UrlClassifierCaching, InvalidateExpiredCacheEntryV4)
+{ TestInvalidateExpiredCacheEntry<LookupCacheV4>(); }
+
+// This testcase check if an cache entry whose negative cache time is expired
+// and it doesn't have any postive cache entries in it, it should be removed
+// from cache after calling |Has|.
+TEST(UrlClassifierCaching, NegativeCacheExpireV2)
+{
+  _PrefixArray array = {CreatePrefixFromURL(NEG_CACHE_EXPIRED_URL, 8)};
+  RefPtr<LookupCacheV2> cache = SetupLookupCache<LookupCacheV2>(array);
+
+  nsCOMPtr<nsICryptoHash> cryptoHash =
+      do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID);
+
+  MissPrefixArray misses;
+  Prefix* prefix = misses.AppendElement(mozilla::fallible);
+  prefix->FromPlaintext(NEG_CACHE_EXPIRED_URL);
+
+  AddCompleteArray dummy;
+  cache->AddGethashResultToCache(dummy, misses, EXPIRED_TIME_SEC);
+
+  // Ensure it is in cache in the first place.
+  EXPECT_EQ(cache->IsInCache(prefix->ToUint32()), true);
+
+  // It should be removed after calling Has API.
+  TestCache<LookupCacheV2>(NEG_CACHE_EXPIRED_URL, true, false, false,
+                           cache.get());
+}
+
+TEST(UrlClassifierCaching, NegativeCacheExpireV4)
+{
+  _PrefixArray array = {CreatePrefixFromURL(NEG_CACHE_EXPIRED_URL, 8)};
+  RefPtr<LookupCacheV4> cache = SetupLookupCache<LookupCacheV4>(array);
+
+  FullHashResponseMap map;
+  Prefix prefix;
+  nsCOMPtr<nsICryptoHash> cryptoHash =
+      do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID);
+  prefix.FromPlaintext(NEG_CACHE_EXPIRED_URL);
+  CachedFullHashResponse* response = map.GetOrInsertNew(prefix.ToUint32());
+
+  response->negativeCacheExpirySec = EXPIRED_TIME_SEC;
+
+  cache->AddFullHashResponseToCache(map);
+
+  // Ensure it is in cache in the first place.
+  EXPECT_EQ(cache->IsInCache(prefix.ToUint32()), true);
+
+  // It should be removed after calling Has API.
+  TestCache<LookupCacheV4>(NEG_CACHE_EXPIRED_URL, true, false, false,
+                           cache.get());
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestChunkSet.cpp b/toolkit/components/url-classifier/tests/gtest/TestChunkSet.cpp
new file mode 100644
index 0000000000..6835103b30
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestChunkSet.cpp
@@ -0,0 +1,281 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <set>
+
+#include "ChunkSet.h"
+#include "mozilla/ArrayUtils.h"
+
+#include "Common.h"
+
+TEST(UrlClassifierChunkSet, Empty)
+{
+  mozilla::safebrowsing::ChunkSet chunkSet;
+  mozilla::safebrowsing::ChunkSet removeSet;
+
+  removeSet.Set(0);
+
+  ASSERT_FALSE(chunkSet.Has(0));
+  ASSERT_FALSE(chunkSet.Has(1));
+  ASSERT_TRUE(chunkSet.Remove(removeSet) == NS_OK);
+  ASSERT_TRUE(chunkSet.Length() == 0);
+
+  chunkSet.Set(0);
+
+  ASSERT_TRUE(chunkSet.Has(0));
+  ASSERT_TRUE(chunkSet.Length() == 1);
+  ASSERT_TRUE(chunkSet.Remove(removeSet) == NS_OK);
+  ASSERT_FALSE(chunkSet.Has(0));
+  ASSERT_TRUE(chunkSet.Length() == 0);
+}
+
+TEST(UrlClassifierChunkSet, Main)
+{
+  static int testVals[] = {2, 1, 5, 6, 8, 7, 14, 10, 12, 13};
+
+  mozilla::safebrowsing::ChunkSet chunkSet;
+
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
+    chunkSet.Set(testVals[i]);
+  }
+
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
+    ASSERT_TRUE(chunkSet.Has(testVals[i]));
+  }
+
+  ASSERT_FALSE(chunkSet.Has(3));
+  ASSERT_FALSE(chunkSet.Has(4));
+  ASSERT_FALSE(chunkSet.Has(9));
+  ASSERT_FALSE(chunkSet.Has(11));
+
+  ASSERT_TRUE(chunkSet.Length() == MOZ_ARRAY_LENGTH(testVals));
+}
+
+TEST(UrlClassifierChunkSet, Merge)
+{
+  static int testVals[] = {2, 1, 5, 6, 8, 7, 14, 10, 12, 13};
+  static int mergeVals[] = {9, 3, 4, 20, 14, 16};
+
+  mozilla::safebrowsing::ChunkSet chunkSet;
+  mozilla::safebrowsing::ChunkSet mergeSet;
+
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
+    chunkSet.Set(testVals[i]);
+  }
+
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
+    mergeSet.Set(mergeVals[i]);
+  }
+
+  chunkSet.Merge(mergeSet);
+
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
+    ASSERT_TRUE(chunkSet.Has(testVals[i]));
+  }
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
+    ASSERT_TRUE(chunkSet.Has(mergeVals[i]));
+  }
+
+  // -1 because 14 is duplicated in both sets
+  ASSERT_TRUE(chunkSet.Length() ==
+              MOZ_ARRAY_LENGTH(testVals) + MOZ_ARRAY_LENGTH(mergeVals) - 1);
+
+  ASSERT_FALSE(chunkSet.Has(11));
+  ASSERT_FALSE(chunkSet.Has(15));
+  ASSERT_FALSE(chunkSet.Has(17));
+  ASSERT_FALSE(chunkSet.Has(18));
+  ASSERT_FALSE(chunkSet.Has(19));
+}
+
+TEST(UrlClassifierChunkSet, Merge2)
+{
+  static int testVals[] = {2, 1, 5, 6, 8, 7, 14, 10, 12, 13};
+  static int mergeVals[] = {9, 3, 4, 20, 14, 16};
+  static int mergeVals2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
+
+  mozilla::safebrowsing::ChunkSet chunkSet;
+  mozilla::safebrowsing::ChunkSet mergeSet;
+  mozilla::safebrowsing::ChunkSet mergeSet2;
+
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
+    chunkSet.Set(testVals[i]);
+  }
+
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
+    mergeSet.Set(mergeVals[i]);
+  }
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals2); i++) {
+    mergeSet2.Set(mergeVals2[i]);
+  }
+
+  chunkSet.Merge(mergeSet);
+  chunkSet.Merge(mergeSet2);
+
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
+    ASSERT_TRUE(chunkSet.Has(testVals[i]));
+  }
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
+    ASSERT_TRUE(chunkSet.Has(mergeVals[i]));
+  }
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals2); i++) {
+    ASSERT_TRUE(chunkSet.Has(mergeVals2[i]));
+  }
+
+  ASSERT_FALSE(chunkSet.Has(15));
+  ASSERT_FALSE(chunkSet.Has(17));
+  ASSERT_FALSE(chunkSet.Has(18));
+  ASSERT_FALSE(chunkSet.Has(19));
+}
+
+TEST(UrlClassifierChunkSet, Stress)
+{
+  mozilla::safebrowsing::ChunkSet chunkSet;
+  mozilla::safebrowsing::ChunkSet mergeSet;
+  std::set<int> refSet;
+  std::set<int> refMergeSet;
+  static const int TEST_ITERS = 7000;
+  static const int REMOVE_ITERS = 3000;
+  static const int TEST_RANGE = 10000;
+
+  // Construction by Set
+  for (int i = 0; i < TEST_ITERS; i++) {
+    int chunk = rand() % TEST_RANGE;
+    chunkSet.Set(chunk);
+    refSet.insert(chunk);
+  }
+
+  // Same elements as reference set
+  for (auto it = refSet.begin(); it != refSet.end(); ++it) {
+    ASSERT_TRUE(chunkSet.Has(*it));
+  }
+
+  // Hole punching via Remove
+  for (int i = 0; i < REMOVE_ITERS; i++) {
+    int chunk = rand() % TEST_RANGE;
+    mozilla::safebrowsing::ChunkSet helpChunk;
+    helpChunk.Set(chunk);
+
+    chunkSet.Remove(helpChunk);
+    refSet.erase(chunk);
+
+    ASSERT_FALSE(chunkSet.Has(chunk));
+  }
+
+  // Should have chunks present in reference set
+  // Should not have chunks absent in reference set
+  for (int it = 0; it < TEST_RANGE; ++it) {
+    auto found = refSet.find(it);
+    if (chunkSet.Has(it)) {
+      ASSERT_FALSE(found == refSet.end());
+    } else {
+      ASSERT_TRUE(found == refSet.end());
+    }
+  }
+
+  // Construct set to merge with
+  for (int i = 0; i < TEST_ITERS; i++) {
+    int chunk = rand() % TEST_RANGE;
+    mergeSet.Set(chunk);
+    refMergeSet.insert(chunk);
+  }
+
+  // Merge set constructed correctly
+  for (auto it = refMergeSet.begin(); it != refMergeSet.end(); ++it) {
+    ASSERT_TRUE(mergeSet.Has(*it));
+  }
+
+  mozilla::safebrowsing::ChunkSet origSet;
+  origSet = chunkSet.InfallibleClone();
+
+  chunkSet.Merge(mergeSet);
+  refSet.insert(refMergeSet.begin(), refMergeSet.end());
+
+  // Check for presence of elements from both source
+  // Should not have chunks absent in reference set
+  for (int it = 0; it < TEST_RANGE; ++it) {
+    auto found = refSet.find(it);
+    if (chunkSet.Has(it)) {
+      ASSERT_FALSE(found == refSet.end());
+    } else {
+      ASSERT_TRUE(found == refSet.end());
+    }
+  }
+
+  // Unmerge
+  chunkSet.Remove(origSet);
+  for (int it = 0; it < TEST_RANGE; ++it) {
+    if (origSet.Has(it)) {
+      ASSERT_FALSE(chunkSet.Has(it));
+    } else if (mergeSet.Has(it)) {
+      ASSERT_TRUE(chunkSet.Has(it));
+    }
+  }
+}
+
+TEST(UrlClassifierChunkSet, RemoveClear)
+{
+  static int testVals[] = {2, 1, 5, 6, 8, 7, 14, 10, 12, 13};
+  static int mergeVals[] = {3, 4, 9, 16, 20};
+
+  mozilla::safebrowsing::ChunkSet chunkSet;
+  mozilla::safebrowsing::ChunkSet mergeSet;
+  mozilla::safebrowsing::ChunkSet removeSet;
+
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
+    chunkSet.Set(testVals[i]);
+    removeSet.Set(testVals[i]);
+  }
+
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
+    mergeSet.Set(mergeVals[i]);
+  }
+
+  ASSERT_TRUE(chunkSet.Merge(mergeSet) == NS_OK);
+  ASSERT_TRUE(chunkSet.Remove(removeSet) == NS_OK);
+
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
+    ASSERT_TRUE(chunkSet.Has(mergeVals[i]));
+  }
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
+    ASSERT_FALSE(chunkSet.Has(testVals[i]));
+  }
+
+  chunkSet.Clear();
+
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
+    ASSERT_FALSE(chunkSet.Has(mergeVals[i]));
+  }
+}
+
+TEST(UrlClassifierChunkSet, Serialize)
+{
+  static int testVals[] = {2, 1, 5, 6, 8, 7, 14, 10, 12, 13};
+  static int mergeVals[] = {3, 4, 9, 16, 20};
+
+  mozilla::safebrowsing::ChunkSet chunkSet;
+  mozilla::safebrowsing::ChunkSet mergeSet;
+
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(testVals); i++) {
+    chunkSet.Set(testVals[i]);
+  }
+
+  for (size_t i = 0; i < MOZ_ARRAY_LENGTH(mergeVals); i++) {
+    mergeSet.Set(mergeVals[i]);
+  }
+
+  chunkSet.Merge(mergeSet);
+
+  nsAutoCString mergeResult;
+  chunkSet.Serialize(mergeResult);
+
+  printf("mergeResult: %s\n", mergeResult.get());
+
+  nsAutoCString expected("1-10,12-14,16,20"_ns);
+
+  ASSERT_TRUE(mergeResult.Equals(expected));
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestClassifier.cpp b/toolkit/components/url-classifier/tests/gtest/TestClassifier.cpp
new file mode 100644
index 0000000000..4000d6b32e
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestClassifier.cpp
@@ -0,0 +1,83 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "Classifier.h"
+#include "LookupCacheV4.h"
+
+#include "Common.h"
+
+static void TestReadNoiseEntries(RefPtr<Classifier> classifier,
+                                 const nsCString& aTable, const nsCString& aURL,
+                                 const _PrefixArray& aPrefixArray) {
+  Completion lookupHash;
+  lookupHash.FromPlaintext(aURL);
+  RefPtr<LookupResult> result = new LookupResult;
+  result->hash.complete = lookupHash;
+
+  PrefixArray noiseEntries;
+  uint32_t noiseCount = 3;
+  nsresult rv;
+  rv = classifier->ReadNoiseEntries(result->hash.fixedLengthPrefix, aTable,
+                                    noiseCount, noiseEntries);
+  ASSERT_TRUE(rv == NS_OK)
+  << "ReadNoiseEntries returns an error";
+  EXPECT_TRUE(noiseEntries.Length() > 0)
+      << "Number of noise entries is less than 0";
+
+  for (uint32_t i = 0; i < noiseEntries.Length(); i++) {
+    // Test the noise entry should not equal the "real" hash request
+    EXPECT_NE(noiseEntries[i], result->hash.fixedLengthPrefix)
+        << "Noise entry is the same as real hash request";
+    // Test the noise entry should exist in the cached prefix array
+    nsAutoCString partialHash;
+    partialHash.Assign(reinterpret_cast<char*>(&noiseEntries[i]), PREFIX_SIZE);
+    EXPECT_TRUE(aPrefixArray.Contains(partialHash))
+        << "Noise entry is not in the cached prefix array";
+  }
+}
+
+TEST(UrlClassifierClassifier, ReadNoiseEntriesV4)
+{
+  RefPtr<Classifier> classifier = GetClassifier();
+  _PrefixArray array = {
+      CreatePrefixFromURL("bravo.com/", 5),
+      CreatePrefixFromURL("browsing.com/", 9),
+      CreatePrefixFromURL("gound.com/", 4),
+      CreatePrefixFromURL("small.com/", 4),
+      CreatePrefixFromURL("gdfad.com/", 4),
+      CreatePrefixFromURL("afdfound.com/", 4),
+      CreatePrefixFromURL("dffa.com/", 4),
+  };
+
+  nsresult rv;
+  rv = BuildLookupCache(classifier, GTEST_TABLE_V4, array);
+  ASSERT_TRUE(rv == NS_OK)
+  << "Fail to build LookupCache";
+
+  TestReadNoiseEntries(classifier, GTEST_TABLE_V4, "gound.com/"_ns, array);
+}
+
+TEST(UrlClassifierClassifier, ReadNoiseEntriesV2)
+{
+  RefPtr<Classifier> classifier = GetClassifier();
+  _PrefixArray array = {
+      CreatePrefixFromURL("helloworld.com/", 4),
+      CreatePrefixFromURL("firefox.com/", 4),
+      CreatePrefixFromURL("chrome.com/", 4),
+      CreatePrefixFromURL("safebrowsing.com/", 4),
+      CreatePrefixFromURL("opera.com/", 4),
+      CreatePrefixFromURL("torbrowser.com/", 4),
+      CreatePrefixFromURL("gfaads.com/", 4),
+      CreatePrefixFromURL("qggdsas.com/", 4),
+      CreatePrefixFromURL("nqtewq.com/", 4),
+  };
+
+  nsresult rv;
+  rv = BuildLookupCache(classifier, GTEST_TABLE_V2, array);
+  ASSERT_TRUE(rv == NS_OK)
+  << "Fail to build LookupCache";
+
+  TestReadNoiseEntries(classifier, GTEST_TABLE_V2, "helloworld.com/"_ns, array);
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestFailUpdate.cpp b/toolkit/components/url-classifier/tests/gtest/TestFailUpdate.cpp
new file mode 100644
index 0000000000..f94852a821
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestFailUpdate.cpp
@@ -0,0 +1,109 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "HashStore.h"
+#include "mozilla/Unused.h"
+#include "nsPrintfCString.h"
+#include "string.h"
+
+#include "Common.h"
+
+static const char* kFilesInV2[] = {".vlpset", ".sbstore"};
+static const char* kFilesInV4[] = {".vlpset", ".metadata"};
+
+#define GTEST_MALWARE_TABLE_V4 "goog-malware-proto"_ns
+#define GTEST_PHISH_TABLE_V4 "goog-phish-proto"_ns
+
+#define ROOT_DIR u"safebrowsing"_ns
+#define SB_FILE(x, y) NS_ConvertUTF8toUTF16(nsPrintfCString("%s%s", x, y))
+
+template <typename T, size_t N>
+static void CheckFileExist(const nsCString& aTable, const T (&aFiles)[N],
+                           bool aExpectExists, const char* aMsg = nullptr) {
+  for (uint32_t i = 0; i < N; i++) {
+    // This is just a quick way to know if this is v4 table
+    NS_ConvertUTF8toUTF16 SUB_DIR(strstr(aTable.get(), "-proto") ? "google4"
+                                                                 : "");
+    nsCOMPtr<nsIFile> file = GetFile(nsTArray<nsString>{
+        ROOT_DIR, SUB_DIR, SB_FILE(aTable.get(), aFiles[i])});
+
+    bool exists;
+    file->Exists(&exists);
+
+    if (aMsg) {
+      ASSERT_EQ(aExpectExists, exists)
+          << file->HumanReadablePath().get() << " " << aMsg;
+    } else {
+      ASSERT_EQ(aExpectExists, exists) << file->HumanReadablePath().get();
+    }
+  }
+}
+
+TEST(UrlClassifierFailUpdate, CheckTableReset)
+{
+  const bool FULL_UPDATE = true;
+  const bool PARTIAL_UPDATE = false;
+
+  // Apply V2 update
+  {
+    RefPtr<TableUpdateV2> update = new TableUpdateV2(GTEST_TABLE_V2);
+    mozilla::Unused << update->NewAddChunk(1);
+
+    ApplyUpdate(update);
+
+    // A successful V2 update should create .vlpset & .sbstore files
+    CheckFileExist(GTEST_TABLE_V2, kFilesInV2, true,
+                   "V2 update doesn't create vlpset or sbstore");
+  }
+
+  // Helper function to generate table update data
+  auto func = [](RefPtr<TableUpdateV4> update, bool full, const char* str) {
+    update->SetFullUpdate(full);
+    nsCString prefix(str);
+    update->NewPrefixes(prefix.Length(), prefix);
+  };
+
+  // Apply V4 update for table1
+  {
+    RefPtr<TableUpdateV4> update = new TableUpdateV4(GTEST_MALWARE_TABLE_V4);
+    func(update, FULL_UPDATE, "test_prefix");
+
+    ApplyUpdate(update);
+
+    // A successful V4 update should create .vlpset & .metadata files
+    CheckFileExist(GTEST_MALWARE_TABLE_V4, kFilesInV4, true,
+                   "v4 update doesn't create vlpset or metadata");
+  }
+
+  // Apply V4 update for table2
+  {
+    RefPtr<TableUpdateV4> update = new TableUpdateV4(GTEST_PHISH_TABLE_V4);
+    func(update, FULL_UPDATE, "test_prefix");
+
+    ApplyUpdate(update);
+
+    CheckFileExist(GTEST_PHISH_TABLE_V4, kFilesInV4, true,
+                   "v4 update doesn't create vlpset or metadata");
+  }
+
+  // Apply V4 update with the same prefix in previous full udpate
+  // This should cause an update error.
+  {
+    RefPtr<TableUpdateV4> update = new TableUpdateV4(GTEST_MALWARE_TABLE_V4);
+    func(update, PARTIAL_UPDATE, "test_prefix");
+
+    ApplyUpdate(update);
+
+    // A fail update should remove files for that table
+    CheckFileExist(GTEST_MALWARE_TABLE_V4, kFilesInV4, false,
+                   "a fail v4 update doesn't remove the tables");
+
+    // A fail update should NOT remove files for the other tables
+    CheckFileExist(GTEST_TABLE_V2, kFilesInV2, true,
+                   "a fail v4 update removes a v2 table");
+    CheckFileExist(GTEST_PHISH_TABLE_V4, kFilesInV4, true,
+                   "a fail v4 update removes the other v4 table");
+  }
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestFindFullHash.cpp b/toolkit/components/url-classifier/tests/gtest/TestFindFullHash.cpp
new file mode 100644
index 0000000000..f0f5785017
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestFindFullHash.cpp
@@ -0,0 +1,216 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/Base64.h"
+#include "nsUrlClassifierUtils.h"
+#include "safebrowsing.pb.h"
+
+#include "Common.h"
+
+using namespace mozilla;
+
+template <size_t N>
+static void ToBase64EncodedStringArray(nsCString (&aInput)[N],
+                                       nsTArray<nsCString>& aEncodedArray) {
+  for (size_t i = 0; i < N; i++) {
+    nsCString encoded;
+    nsresult rv = mozilla::Base64Encode(aInput[i], encoded);
+    NS_ENSURE_SUCCESS_VOID(rv);
+    aEncodedArray.AppendElement(std::move(encoded));
+  }
+}
+
+TEST(UrlClassifierFindFullHash, Request)
+{
+  nsUrlClassifierUtils* urlUtil = nsUrlClassifierUtils::GetInstance();
+
+  nsTArray<nsCString> listNames;
+  listNames.AppendElement("moztest-phish-proto");
+  listNames.AppendElement("moztest-unwanted-proto");
+
+  nsCString listStates[] = {nsCString("sta\x00te1", 7),
+                            nsCString("sta\x00te2", 7)};
+  nsTArray<nsCString> listStateArray;
+  ToBase64EncodedStringArray(listStates, listStateArray);
+
+  nsCString prefixes[] = {nsCString("\x00\x00\x00\x01", 4),
+                          nsCString("\x00\x00\x00\x00\x01", 5),
+                          nsCString("\x00\xFF\x00\x01", 4),
+                          nsCString("\x00\xFF\x00\x01\x11\x23\xAA\xBC", 8),
+                          nsCString("\x00\x00\x00\x01\x00\x01\x98", 7)};
+  nsTArray<nsCString> prefixArray;
+  ToBase64EncodedStringArray(prefixes, prefixArray);
+
+  nsCString requestBase64;
+  nsresult rv;
+  rv = urlUtil->MakeFindFullHashRequestV4(listNames, listStateArray,
+                                          prefixArray, requestBase64);
+  ASSERT_NS_SUCCEEDED(rv);
+
+  // Base64 URL decode first.
+  FallibleTArray<uint8_t> requestBinary;
+  rv = Base64URLDecode(requestBase64, Base64URLDecodePaddingPolicy::Require,
+                       requestBinary);
+  ASSERT_NS_SUCCEEDED(rv);
+
+  // Parse the FindFullHash binary and compare with the expected values.
+  FindFullHashesRequest r;
+  ASSERT_TRUE(r.ParseFromArray(&requestBinary[0], requestBinary.Length()));
+
+  // Compare client states.
+  ASSERT_EQ(r.client_states_size(), (int)ArrayLength(listStates));
+  for (int i = 0; i < r.client_states_size(); i++) {
+    auto s = r.client_states(i);
+    ASSERT_TRUE(listStates[i].Equals(nsCString(s.c_str(), s.size())));
+  }
+
+  auto threatInfo = r.threat_info();
+
+  // Compare threat types.
+  ASSERT_EQ(threatInfo.threat_types_size(), (int)ArrayLength(listStates));
+  for (int i = 0; i < threatInfo.threat_types_size(); i++) {
+    uint32_t expectedThreatType;
+    rv =
+        urlUtil->ConvertListNameToThreatType(listNames[i], &expectedThreatType);
+    ASSERT_NS_SUCCEEDED(rv);
+    ASSERT_EQ(threatInfo.threat_types(i), (int)expectedThreatType);
+  }
+
+  // Compare prefixes.
+  ASSERT_EQ(threatInfo.threat_entries_size(), (int)ArrayLength(prefixes));
+  for (int i = 0; i < threatInfo.threat_entries_size(); i++) {
+    auto p = threatInfo.threat_entries(i).hash();
+    ASSERT_TRUE(prefixes[i].Equals(nsCString(p.c_str(), p.size())));
+  }
+}
+
+/////////////////////////////////////////////////////////////
+// Following is to test parsing the gethash response.
+
+namespace {
+
+// safebrowsing::Duration manipulation.
+struct MyDuration {
+  uint32_t mSecs;
+  uint32_t mNanos;
+};
+void PopulateDuration(Duration& aDest, const MyDuration& aSrc) {
+  aDest.set_seconds(aSrc.mSecs);
+  aDest.set_nanos(aSrc.mNanos);
+}
+
+// The expected match data.
+static MyDuration EXPECTED_MIN_WAIT_DURATION = {12, 10};
+static MyDuration EXPECTED_NEG_CACHE_DURATION = {120, 9};
+static const struct ExpectedMatch {
+  nsCString mCompleteHash;
+  ThreatType mThreatType;
+  MyDuration mPerHashCacheDuration;
+} EXPECTED_MATCH[] = {
+    {nsCString("01234567890123456789012345678901"),
+     SOCIAL_ENGINEERING_PUBLIC,
+     {8, 500}},
+    {nsCString("12345678901234567890123456789012"),
+     SOCIAL_ENGINEERING_PUBLIC,
+     {7, 100}},
+    {nsCString("23456789012345678901234567890123"),
+     SOCIAL_ENGINEERING_PUBLIC,
+     {1, 20}},
+};
+
+class MyParseCallback final : public nsIUrlClassifierParseFindFullHashCallback {
+ public:
+  NS_DECL_ISUPPORTS
+
+  explicit MyParseCallback(uint32_t& aCallbackCount)
+      : mCallbackCount(aCallbackCount) {}
+
+  NS_IMETHOD
+  OnCompleteHashFound(const nsACString& aCompleteHash,
+                      const nsACString& aTableNames,
+                      uint32_t aPerHashCacheDuration) override {
+    Verify(aCompleteHash, aTableNames, aPerHashCacheDuration);
+
+    return NS_OK;
+  }
+
+  NS_IMETHOD
+  OnResponseParsed(uint32_t aMinWaitDuration,
+                   uint32_t aNegCacheDuration) override {
+    VerifyDuration(aMinWaitDuration / 1000, EXPECTED_MIN_WAIT_DURATION);
+    VerifyDuration(aNegCacheDuration, EXPECTED_NEG_CACHE_DURATION);
+
+    return NS_OK;
+  }
+
+ private:
+  void Verify(const nsACString& aCompleteHash, const nsACString& aTableNames,
+              uint32_t aPerHashCacheDuration) {
+    auto expected = EXPECTED_MATCH[mCallbackCount];
+
+    ASSERT_TRUE(aCompleteHash.Equals(expected.mCompleteHash));
+
+    // Verify aTableNames
+    nsUrlClassifierUtils* urlUtil = nsUrlClassifierUtils::GetInstance();
+
+    nsCString tableNames;
+    nsresult rv =
+        urlUtil->ConvertThreatTypeToListNames(expected.mThreatType, tableNames);
+    ASSERT_NS_SUCCEEDED(rv);
+    ASSERT_TRUE(aTableNames.Equals(tableNames));
+
+    VerifyDuration(aPerHashCacheDuration, expected.mPerHashCacheDuration);
+
+    mCallbackCount++;
+  }
+
+  void VerifyDuration(uint32_t aToVerify, const MyDuration& aExpected) {
+    ASSERT_TRUE(aToVerify == aExpected.mSecs);
+  }
+
+  ~MyParseCallback() = default;
+
+  uint32_t& mCallbackCount;
+};
+
+NS_IMPL_ISUPPORTS(MyParseCallback, nsIUrlClassifierParseFindFullHashCallback)
+
+}  // end of unnamed namespace.
+
+TEST(UrlClassifierFindFullHash, ParseRequest)
+{
+  // Build response.
+  FindFullHashesResponse r;
+
+  // Init response-wise durations.
+  auto minWaitDuration = r.mutable_minimum_wait_duration();
+  PopulateDuration(*minWaitDuration, EXPECTED_MIN_WAIT_DURATION);
+  auto negCacheDuration = r.mutable_negative_cache_duration();
+  PopulateDuration(*negCacheDuration, EXPECTED_NEG_CACHE_DURATION);
+
+  // Init matches.
+  for (uint32_t i = 0; i < ArrayLength(EXPECTED_MATCH); i++) {
+    auto expected = EXPECTED_MATCH[i];
+    auto match = r.mutable_matches()->Add();
+    match->set_threat_type(expected.mThreatType);
+    match->mutable_threat()->set_hash(expected.mCompleteHash.BeginReading(),
+                                      expected.mCompleteHash.Length());
+    auto perHashCacheDuration = match->mutable_cache_duration();
+    PopulateDuration(*perHashCacheDuration, expected.mPerHashCacheDuration);
+  }
+  std::string s;
+  r.SerializeToString(&s);
+
+  uint32_t callbackCount = 0;
+  nsCOMPtr<nsIUrlClassifierParseFindFullHashCallback> callback =
+      new MyParseCallback(callbackCount);
+
+  nsUrlClassifierUtils* urlUtil = nsUrlClassifierUtils::GetInstance();
+  nsresult rv = urlUtil->ParseFindFullHashResponseV4(
+      nsCString(s.c_str(), s.size()), callback);
+  NS_ENSURE_SUCCESS_VOID(rv);
+
+  ASSERT_EQ(callbackCount, ArrayLength(EXPECTED_MATCH));
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestLookupCacheV4.cpp b/toolkit/components/url-classifier/tests/gtest/TestLookupCacheV4.cpp
new file mode 100644
index 0000000000..e1482c1416
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestLookupCacheV4.cpp
@@ -0,0 +1,152 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "Classifier.h"
+#include "LookupCacheV4.h"
+#include "nsAppDirectoryServiceDefs.h"
+
+#include "Common.h"
+
+#define GTEST_SAFEBROWSING_DIR "safebrowsing"_ns
+
+static void TestHasPrefix(const nsCString& aURL, bool aExpectedHas,
+                          bool aExpectedComplete) {
+  _PrefixArray array = {CreatePrefixFromURL("bravo.com/", 32),
+                        CreatePrefixFromURL("browsing.com/", 8),
+                        CreatePrefixFromURL("gound.com/", 5),
+                        CreatePrefixFromURL("small.com/", 4)};
+
+  nsCOMPtr<nsIFile> file;
+  NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
+  file->AppendNative(GTEST_SAFEBROWSING_DIR);
+
+  RunTestInNewThread([&]() -> void {
+    RefPtr<LookupCache> cache = SetupLookupCache<LookupCacheV4>(array, file);
+
+    Completion lookupHash;
+    lookupHash.FromPlaintext(aURL);
+
+    bool has, confirmed;
+    uint32_t matchLength;
+    // Freshness is not used in V4 so we just put dummy values here.
+    TableFreshnessMap dummy;
+    nsresult rv = cache->Has(lookupHash, &has, &matchLength, &confirmed);
+
+    EXPECT_EQ(rv, NS_OK);
+    EXPECT_EQ(has, aExpectedHas);
+    EXPECT_EQ(matchLength == COMPLETE_SIZE, aExpectedComplete);
+    EXPECT_EQ(confirmed, false);
+
+    cache->ClearAll();
+  });
+}
+
+TEST(UrlClassifierLookupCacheV4, HasComplete)
+{ TestHasPrefix("bravo.com/"_ns, true, true); }
+
+TEST(UrlClassifierLookupCacheV4, HasPrefix)
+{ TestHasPrefix("browsing.com/"_ns, true, false); }
+
+TEST(UrlClassifierLookupCacheV4, Nomatch)
+{ TestHasPrefix("nomatch.com/"_ns, false, false); }
+
+// Test an existing .pset should be removed after .vlpset is written
+TEST(UrlClassifierLookupCacheV4, RemoveOldPset)
+{
+  nsCOMPtr<nsIFile> oldPsetFile;
+  NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR,
+                         getter_AddRefs(oldPsetFile));
+  oldPsetFile->AppendNative("safebrowsing"_ns);
+  oldPsetFile->AppendNative(GTEST_TABLE_V4 + ".pset"_ns);
+
+  nsCOMPtr<nsIFile> newPsetFile;
+  NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR,
+                         getter_AddRefs(newPsetFile));
+  newPsetFile->AppendNative("safebrowsing"_ns);
+  newPsetFile->AppendNative(GTEST_TABLE_V4 + ".vlpset"_ns);
+
+  // Create the legacy .pset file
+  nsresult rv = oldPsetFile->Create(nsIFile::NORMAL_FILE_TYPE, 0666);
+  EXPECT_EQ(rv, NS_OK);
+
+  bool exists;
+  rv = oldPsetFile->Exists(&exists);
+  EXPECT_EQ(rv, NS_OK);
+  EXPECT_EQ(exists, true);
+
+  // Setup the data in lookup cache and write its data to disk
+  RefPtr<Classifier> classifier = GetClassifier();
+  _PrefixArray array = {CreatePrefixFromURL("entry.com/", 4)};
+  rv = BuildLookupCache(classifier, GTEST_TABLE_V4, array);
+  EXPECT_EQ(rv, NS_OK);
+
+  RefPtr<LookupCache> cache = classifier->GetLookupCache(GTEST_TABLE_V4, false);
+  rv = cache->WriteFile();
+  EXPECT_EQ(rv, NS_OK);
+
+  // .vlpset should exist while .pset should be removed
+  rv = newPsetFile->Exists(&exists);
+  EXPECT_EQ(rv, NS_OK);
+  EXPECT_EQ(exists, true);
+
+  rv = oldPsetFile->Exists(&exists);
+  EXPECT_EQ(rv, NS_OK);
+  EXPECT_EQ(exists, false);
+
+  newPsetFile->Remove(false);
+}
+
+// Test the legacy load
+TEST(UrlClassifierLookupCacheV4, LoadOldPset)
+{
+  nsCOMPtr<nsIFile> oldPsetFile;
+
+  _PrefixArray array = {CreatePrefixFromURL("entry.com/", 4)};
+  PrefixStringMap map;
+  PrefixArrayToPrefixStringMap(array, map);
+
+  // Prepare .pset file on disk
+  {
+    NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR,
+                           getter_AddRefs(oldPsetFile));
+    oldPsetFile->AppendNative("safebrowsing"_ns);
+    oldPsetFile->AppendNative(GTEST_TABLE_V4 + ".pset"_ns);
+
+    RefPtr<VariableLengthPrefixSet> pset = new VariableLengthPrefixSet;
+    pset->SetPrefixes(map);
+
+    nsCOMPtr<nsIOutputStream> stream;
+    nsresult rv =
+        NS_NewLocalFileOutputStream(getter_AddRefs(stream), oldPsetFile);
+    EXPECT_EQ(rv, NS_OK);
+
+    rv = pset->WritePrefixes(stream);
+    EXPECT_EQ(rv, NS_OK);
+  }
+
+  // Load data from disk
+  RefPtr<Classifier> classifier = GetClassifier();
+  RefPtr<LookupCache> cache = classifier->GetLookupCache(GTEST_TABLE_V4, false);
+
+  RefPtr<LookupCacheV4> cacheV4 = LookupCache::Cast<LookupCacheV4>(cache);
+  CheckContent(cacheV4, array);
+
+  oldPsetFile->Remove(false);
+}
+
+TEST(UrlClassifierLookupCacheV4, BuildAPI)
+{
+  _PrefixArray init = {_Prefix("alph")};
+  RefPtr<LookupCacheV4> cache = SetupLookupCache<LookupCacheV4>(init);
+
+  _PrefixArray update = {_Prefix("beta")};
+  PrefixStringMap map;
+  PrefixArrayToPrefixStringMap(update, map);
+
+  cache->Build(map);
+  EXPECT_TRUE(map.IsEmpty());
+
+  CheckContent(cache, update);
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestPerProviderDirectory.cpp b/toolkit/components/url-classifier/tests/gtest/TestPerProviderDirectory.cpp
new file mode 100644
index 0000000000..a79ab643f4
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestPerProviderDirectory.cpp
@@ -0,0 +1,127 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "HashStore.h"
+#include "LookupCache.h"
+#include "LookupCacheV4.h"
+#include "nsAppDirectoryServiceDefs.h"
+
+#include "Common.h"
+
+namespace mozilla {
+namespace safebrowsing {
+
+class PerProviderDirectoryTestUtils {
+ public:
+  template <typename T>
+  static nsIFile* InspectStoreDirectory(const T& aT) {
+    return aT.mStoreDirectory;
+  }
+};
+
+}  // end of namespace safebrowsing
+}  // end of namespace mozilla
+
+template <typename T>
+static void VerifyPrivateStorePath(T* target, const nsCString& aTableName,
+                                   const nsCString& aProvider,
+                                   const nsCOMPtr<nsIFile>& aRootDir,
+                                   bool aUsePerProviderStore) {
+  nsString rootStorePath;
+  nsresult rv = aRootDir->GetPath(rootStorePath);
+  EXPECT_EQ(rv, NS_OK);
+
+  nsIFile* privateStoreDirectory =
+      PerProviderDirectoryTestUtils::InspectStoreDirectory(*target);
+
+  nsString privateStorePath;
+  rv = privateStoreDirectory->GetPath(privateStorePath);
+  ASSERT_EQ(rv, NS_OK);
+
+  nsString expectedPrivateStorePath = rootStorePath;
+
+  if (aUsePerProviderStore) {
+    // Use API to append "provider" to the root directoy path
+    nsCOMPtr<nsIFile> expectedPrivateStoreDir;
+    rv = aRootDir->Clone(getter_AddRefs(expectedPrivateStoreDir));
+    ASSERT_EQ(rv, NS_OK);
+
+    expectedPrivateStoreDir->AppendNative(aProvider);
+    rv = expectedPrivateStoreDir->GetPath(expectedPrivateStorePath);
+    ASSERT_EQ(rv, NS_OK);
+  }
+
+  printf("table: %s\nprovider: %s\nroot path: %s\nprivate path: %s\n\n",
+         aTableName.get(), aProvider.get(),
+         NS_ConvertUTF16toUTF8(rootStorePath).get(),
+         NS_ConvertUTF16toUTF8(privateStorePath).get());
+
+  ASSERT_TRUE(privateStorePath == expectedPrivateStorePath);
+}
+
+TEST(UrlClassifierPerProviderDirectory, LookupCache)
+{
+  nsCOMPtr<nsIFile> rootDir;
+  NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(rootDir));
+
+  RunTestInNewThread([&]() -> void {
+    // For V2 tables (NOT ending with '-proto'), root directory should be
+    // used as the private store.
+    {
+      nsAutoCString table("goog-phish-shavar");
+      nsAutoCString provider("google");
+      RefPtr<LookupCacheV2> lc = new LookupCacheV2(table, provider, rootDir);
+      VerifyPrivateStorePath<LookupCacheV2>(lc, table, provider, rootDir,
+                                            false);
+    }
+
+    // For V4 tables, if provider is found, use per-provider subdirectory;
+    // If not found, use root directory.
+    {
+      nsAutoCString table("goog-noprovider-proto");
+      nsAutoCString provider("");
+      RefPtr<LookupCacheV4> lc = new LookupCacheV4(table, provider, rootDir);
+      VerifyPrivateStorePath<LookupCacheV4>(lc, table, provider, rootDir,
+                                            false);
+    }
+    {
+      nsAutoCString table("goog-phish-proto");
+      nsAutoCString provider("google4");
+      RefPtr<LookupCacheV4> lc = new LookupCacheV4(table, provider, rootDir);
+      VerifyPrivateStorePath<LookupCacheV4>(lc, table, provider, rootDir, true);
+    }
+  });
+}
+
+TEST(UrlClassifierPerProviderDirectory, HashStore)
+{
+  nsCOMPtr<nsIFile> rootDir;
+  NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(rootDir));
+
+  RunTestInNewThread([&]() -> void {
+    // For V2 tables (NOT ending with '-proto'), root directory should be
+    // used as the private store.
+    {
+      nsAutoCString table("goog-phish-shavar");
+      nsAutoCString provider("google");
+      HashStore hs(table, provider, rootDir);
+      VerifyPrivateStorePath(&hs, table, provider, rootDir, false);
+    }
+    // For V4 tables, if provider is found, use per-provider subdirectory;
+    // If not found, use root directory.
+    {
+      nsAutoCString table("goog-noprovider-proto");
+      nsAutoCString provider("");
+      HashStore hs(table, provider, rootDir);
+      VerifyPrivateStorePath(&hs, table, provider, rootDir, false);
+    }
+    {
+      nsAutoCString table("goog-phish-proto");
+      nsAutoCString provider("google4");
+      HashStore hs(table, provider, rootDir);
+      VerifyPrivateStorePath(&hs, table, provider, rootDir, true);
+    }
+  });
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestPrefixSet.cpp b/toolkit/components/url-classifier/tests/gtest/TestPrefixSet.cpp
new file mode 100644
index 0000000000..6d83cd02f6
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestPrefixSet.cpp
@@ -0,0 +1,87 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/Preferences.h"
+#include "nsString.h"
+#include "nsUrlClassifierPrefixSet.h"
+
+#include "Common.h"
+
+// This function generate N 4 byte prefixes.
+static void RandomPrefixes(uint32_t N, nsTArray<uint32_t>& array) {
+  array.Clear();
+  array.SetCapacity(N);
+
+  for (uint32_t i = 0; i < N; i++) {
+    bool added = false;
+
+    while (!added) {
+      nsAutoCString prefix;
+      char* dst = prefix.BeginWriting();
+      for (uint32_t j = 0; j < 4; j++) {
+        dst[j] = static_cast<char>(rand() % 256);
+      }
+
+      const char* src = prefix.BeginReading();
+      uint32_t data = 0;
+      memcpy(&data, src, sizeof(data));
+
+      if (!array.Contains(data)) {
+        array.AppendElement(data);
+        added = true;
+      }
+    }
+  }
+
+  struct Comparator {
+    bool LessThan(const uint32_t& aA, const uint32_t& aB) const {
+      return aA < aB;
+    }
+
+    bool Equals(const uint32_t& aA, const uint32_t& aB) const {
+      return aA == aB;
+    }
+  };
+
+  array.Sort(Comparator());
+}
+
+void RunTest(uint32_t aTestSize) {
+  RefPtr<nsUrlClassifierPrefixSet> prefixSet = new nsUrlClassifierPrefixSet();
+  nsTArray<uint32_t> array;
+
+  RandomPrefixes(aTestSize, array);
+
+  nsresult rv = prefixSet->SetPrefixes(array.Elements(), array.Length());
+  ASSERT_NS_SUCCEEDED(rv);
+
+  for (uint32_t i = 0; i < array.Length(); i++) {
+    uint32_t value = 0;
+    rv = prefixSet->GetPrefixByIndex(i, &value);
+    ASSERT_NS_SUCCEEDED(rv);
+
+    ASSERT_TRUE(value == array[i]);
+  }
+}
+
+TEST(URLClassifierPrefixSet, GetTargetPrefixWithLargeSet)
+{
+  // Make sure the delta algorithm will be used.
+  static const char prefKey[] = "browser.safebrowsing.prefixset_max_array_size";
+  mozilla::Preferences::SetUint(prefKey, 10000);
+
+  // Ideally, we should test more than 512 * 1024 entries. But, it will make the
+  // test too long. So, we test 100k entries instead.
+  RunTest(100000);
+}
+
+TEST(URLClassifierPrefixSet, GetTargetPrefixWithSmallSet)
+{
+  // Make sure the delta algorithm won't be used.
+  static const char prefKey[] = "browser.safebrowsing.prefixset_max_array_size";
+  mozilla::Preferences::SetUint(prefKey, 10000);
+
+  RunTest(1000);
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestProtocolParser.cpp b/toolkit/components/url-classifier/tests/gtest/TestProtocolParser.cpp
new file mode 100644
index 0000000000..2155140b4d
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestProtocolParser.cpp
@@ -0,0 +1,140 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/EndianUtils.h"
+#include "ProtocolParser.h"
+
+#include "Common.h"
+
+typedef FetchThreatListUpdatesResponse_ListUpdateResponse ListUpdateResponse;
+
+static bool InitUpdateResponse(ListUpdateResponse* aUpdateResponse,
+                               ThreatType aThreatType, const nsACString& aState,
+                               const nsACString& aChecksum, bool isFullUpdate,
+                               const nsTArray<uint32_t>& aFixedLengthPrefixes,
+                               bool aDoPrefixEncoding) {
+  aUpdateResponse->set_threat_type(aThreatType);
+  aUpdateResponse->set_new_client_state(aState.BeginReading(), aState.Length());
+  aUpdateResponse->mutable_checksum()->set_sha256(aChecksum.BeginReading(),
+                                                  aChecksum.Length());
+  aUpdateResponse->set_response_type(isFullUpdate
+                                         ? ListUpdateResponse::FULL_UPDATE
+                                         : ListUpdateResponse::PARTIAL_UPDATE);
+
+  auto additions = aUpdateResponse->mutable_additions()->Add();
+
+  if (!aDoPrefixEncoding) {
+    additions->set_compression_type(RAW);
+    auto rawHashes = additions->mutable_raw_hashes();
+    rawHashes->set_prefix_size(4);
+    auto prefixes = rawHashes->mutable_raw_hashes();
+    for (auto p : aFixedLengthPrefixes) {
+      char buffer[4];
+      mozilla::NativeEndian::copyAndSwapToBigEndian(buffer, &p, 1);
+      prefixes->append(buffer, 4);
+    }
+    return true;
+  }
+
+  if (1 != aFixedLengthPrefixes.Length()) {
+    printf("This function only supports single value encoding.\n");
+    return false;
+  }
+
+  uint32_t firstValue = aFixedLengthPrefixes[0];
+  additions->set_compression_type(RICE);
+  auto riceHashes = additions->mutable_rice_hashes();
+  riceHashes->set_first_value(firstValue);
+  riceHashes->set_num_entries(0);
+
+  return true;
+}
+
+static void DumpBinary(const nsACString& aBinary) {
+  nsCString s;
+  for (size_t i = 0; i < aBinary.Length(); i++) {
+    s.AppendPrintf("\\x%.2X", (uint8_t)aBinary[i]);
+  }
+  printf("%s\n", s.get());
+}
+
+TEST(UrlClassifierProtocolParser, UpdateWait)
+{
+  // Top level response which contains a list of update response
+  // for different lists.
+  FetchThreatListUpdatesResponse response;
+
+  auto r = response.mutable_list_update_responses()->Add();
+  InitUpdateResponse(r, SOCIAL_ENGINEERING_PUBLIC, nsCString("sta\x00te", 6),
+                     nsCString("check\x0sum", 9), true, {0, 1, 2, 3},
+                     false /* aDoPrefixEncoding */);
+
+  // Set min wait duration.
+  auto minWaitDuration = response.mutable_minimum_wait_duration();
+  minWaitDuration->set_seconds(8);
+  minWaitDuration->set_nanos(1 * 1000000000);
+
+  std::string s;
+  response.SerializeToString(&s);
+
+  DumpBinary(nsCString(s.c_str(), s.length()));
+
+  ProtocolParser* p = new ProtocolParserProtobuf();
+  p->AppendStream(nsCString(s.c_str(), s.length()));
+  p->End();
+  ASSERT_EQ(p->UpdateWaitSec(), 9u);
+  delete p;
+}
+
+TEST(UrlClassifierProtocolParser, SingleValueEncoding)
+{
+  // Top level response which contains a list of update response
+  // for different lists.
+  FetchThreatListUpdatesResponse response;
+
+  auto r = response.mutable_list_update_responses()->Add();
+
+  const char* expectedPrefix = "\x00\x01\x02\x00";
+  if (!InitUpdateResponse(r, SOCIAL_ENGINEERING_PUBLIC,
+                          nsCString("sta\x00te", 6),
+                          nsCString("check\x0sum", 9), true,
+                          // As per spec, we should interpret the prefix as
+                          // uint32 in little endian before encoding.
+                          {mozilla::LittleEndian::readUint32(expectedPrefix)},
+                          true /* aDoPrefixEncoding */)) {
+    printf("Failed to initialize update response.");
+    ASSERT_TRUE(false);
+    return;
+  }
+
+  // Set min wait duration.
+  auto minWaitDuration = response.mutable_minimum_wait_duration();
+  minWaitDuration->set_seconds(8);
+  minWaitDuration->set_nanos(1 * 1000000000);
+
+  std::string s;
+  response.SerializeToString(&s);
+
+  // Feed data to the protocol parser.
+  ProtocolParser* p = new ProtocolParserProtobuf();
+  p->SetRequestedTables({nsCString("googpub-phish-proto")});
+  p->AppendStream(nsCString(s.c_str(), s.length()));
+  p->End();
+
+  const TableUpdateArray& tus = p->GetTableUpdates();
+  RefPtr<const TableUpdateV4> tuv4 = TableUpdate::Cast<TableUpdateV4>(tus[0]);
+  auto& prefixMap = tuv4->Prefixes();
+  for (const auto& entry : prefixMap) {
+    // This prefix map should contain only a single 4-byte prefixe.
+    ASSERT_EQ(entry.GetKey(), 4u);
+
+    // The fixed-length prefix string from ProtocolParser should
+    // exactly match the expected prefix string.
+    nsCString* prefix = entry.GetWeak();
+    ASSERT_TRUE(prefix->Equals(nsCString(expectedPrefix, 4)));
+  }
+
+  delete p;
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestRiceDeltaDecoder.cpp b/toolkit/components/url-classifier/tests/gtest/TestRiceDeltaDecoder.cpp
new file mode 100644
index 0000000000..9130cfe385
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestRiceDeltaDecoder.cpp
@@ -0,0 +1,173 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/ArrayUtils.h"
+#include "RiceDeltaDecoder.h"
+
+#include "Common.h"
+
+namespace {
+
+struct TestingData {
+  std::vector<uint32_t> mExpectedDecoded;
+  std::vector<uint8_t> mEncoded;
+  uint32_t mRiceParameter;
+};
+
+}  // namespace
+
+static bool runOneTest(TestingData& aData) {
+  RiceDeltaDecoder decoder(&aData.mEncoded[0], aData.mEncoded.size());
+
+  std::vector<uint32_t> decoded(aData.mExpectedDecoded.size());
+
+  uint32_t firstValue = aData.mExpectedDecoded[0];
+  bool rv = decoder.Decode(
+      aData.mRiceParameter, firstValue,
+      decoded.size() - 1,  // # of entries (first value not included).
+      &decoded[0]);
+
+  return rv && decoded == aData.mExpectedDecoded;
+}
+
+TEST(UrlClassifierRiceDeltaDecoder, SingleEncodedValue)
+{
+  TestingData td = {{99}, {99}, 0};
+
+  ASSERT_TRUE(runOneTest(td));
+}
+
+// In this batch of tests, the encoded data would be like
+// what we originally receive from the network. See comment
+// in |runOneTest| for more detail.
+TEST(UrlClassifierRiceDeltaDecoder, Empty)
+{
+  // The following structure and testing data is copied from Chromium source
+  // code:
+  //
+  // https://chromium.googlesource.com/chromium/src.git/+/950f9975599768b6a08c7146cb4befa161be87aa/components/safe_browsing_db/v4_rice_unittest.cc#75
+  //
+  // and will be translated to our own testing format.
+
+  struct RiceDecodingTestInfo {
+    uint32_t mRiceParameter;
+    std::vector<uint32_t> mDeltas;
+    std::string mEncoded;
+
+    RiceDecodingTestInfo(uint32_t aRiceParameter,
+                         const std::vector<uint32_t>& aDeltas,
+                         const std::string& aEncoded)
+        : mRiceParameter(aRiceParameter),
+          mDeltas(aDeltas),
+          mEncoded(aEncoded) {}
+  };
+
+  // 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 media/webrtc/trunk/webrtc/LICENSE.
+
+  // ----- Start of Chromium test code ----
+  const std::vector<RiceDecodingTestInfo> TESTING_DATA_CHROMIUM = {
+      RiceDecodingTestInfo(2, {15, 9}, "\xf7\x2"),
+      RiceDecodingTestInfo(
+          28, {1777762129, 2093280223, 924369848},
+          "\xbf\xa8\x3f\xfb\xfc\xfb\x5e\x27\xe6\xc3\x1d\xc6\x38"),
+      RiceDecodingTestInfo(
+          28, {62763050, 1046523781, 192522171, 1800511020, 4442775, 582142548},
+          "\x54\x60\x7b\xe7\x0a\x5f\xc1\xdc\xee\x69\xde"
+          "\xfe\x58\x3c\xa3\xd6\xa5\xf2\x10\x8c\x4a\x59"
+          "\x56\x00"),
+      RiceDecodingTestInfo(
+          28,
+          {26067715, 344823336, 8420095, 399843890, 95029378, 731622412,
+           35811335, 1047558127, 1117722715, 78698892},
+          "\x06\x86\x1b\x23\x14\xcb\x46\xf2\xaf\x07\x08\xc9\x88\x54\x1f\x41\x04"
+          "\xd5\x1a\x03\xeb\xe6\x3a\x80\x13\x91\x7b\xbf\x83\xf3\xb7\x85\xf1\x29"
+          "\x18\xb3\x61\x09"),
+      RiceDecodingTestInfo(
+          27,
+          {225846818, 328287420, 166748623, 29117720, 552397365, 350353215,
+           558267528, 4738273, 567093445, 28563065, 55077698, 73091685,
+           339246010, 98242620, 38060941, 63917830, 206319759, 137700744},
+          "\x89\x98\xd8\x75\xbc\x44\x91\xeb\x39\x0c\x3e\x30\x9a\x78\xf3\x6a\xd4"
+          "\xd9\xb1\x9f\xfb\x70\x3e\x44\x3e\xa3\x08\x67\x42\xc2\x2b\x46\x69\x8e"
+          "\x3c\xeb\xd9\x10\x5a\x43\x9a\x32\xa5\x2d\x4e\x77\x0f\x87\x78\x20\xb6"
+          "\xab\x71\x98\x48\x0c\x9e\x9e\xd7\x23\x0c\x13\x43\x2c\xa9\x01"),
+      RiceDecodingTestInfo(
+          28,
+          {339784008, 263128563, 63871877, 69723256, 826001074, 797300228,
+           671166008, 207712688},
+          std::string("\x21\xc5\x02\x91\xf9\x82\xd7\x57\xb8\xe9\x3c\xf0\xc8\x4f"
+                      "\xe8\x64\x8d\x77\x62\x04\xd6\x85\x3f\x1c\x97\x00\x04\x1b"
+                      "\x17\xc6",
+                      30)),
+      RiceDecodingTestInfo(
+          28,
+          {471820069, 196333855, 855579133, 122737976, 203433838, 85354544,
+           1307949392, 165938578, 195134475, 553930435, 49231136},
+          "\x95\x9c\x7d\xb0\x8f\xe8\xd9\xbd\xfe\x8c\x7f\x81\x53\x0d\x75\xdc\x4e"
+          "\x40\x18\x0c\x9a\x45\x3d\xa8\xdc\xfa\x26\x59\x40\x9e\x16\x08\x43\x77"
+          "\xc3\x4e\x04\x01\xa4\xe6\x5d\x00"),
+      RiceDecodingTestInfo(
+          27,
+          {87336845, 129291033, 30906211, 433549264, 30899891, 53207875,
+           11959529, 354827862, 82919275, 489637251, 53561020, 336722992,
+           408117728, 204506246, 188216092, 9047110, 479817359, 230317256},
+          "\x1a\x4f\x69\x2a\x63\x9a\xf6\xc6\x2e\xaf\x73\xd0\x6f\xd7\x31\xeb\x77"
+          "\x1d\x43\xe3\x2b\x93\xce\x67\x8b\x59\xf9\x98\xd4\xda\x4f\x3c\x6f\xb0"
+          "\xe8\xa5\x78\x8d\x62\x36\x18\xfe\x08\x1e\x78\xd8\x14\x32\x24\x84\x61"
+          "\x1c\xf3\x37\x63\xc4\xa0\x88\x7b\x74\xcb\x64\xc8\x5c\xba\x05"),
+      RiceDecodingTestInfo(
+          28,
+          {297968956, 19709657, 259702329, 76998112, 1023176123, 29296013,
+           1602741145, 393745181, 177326295, 55225536, 75194472},
+          "\xf1\x94\x0a\x87\x6c\x5f\x96\x90\xe3\xab\xf7\xc0\xcb\x2d\xe9\x76\xdb"
+          "\xf8\x59\x63\xc1\x6f\x7c\x99\xe3\x87\x5f\xc7\x04\xde\xb9\x46\x8e\x54"
+          "\xc0\xac\x4a\x03\x0d\x6c\x8f\x00"),
+      RiceDecodingTestInfo(
+          28,
+          {532220688, 780594691, 436816483, 163436269, 573044456, 1069604,
+           39629436, 211410997, 227714491, 381562898, 75610008, 196754597,
+           40310339, 15204118, 99010842},
+          "\x41\x2c\xe4\xfe\x06\xdc\x0d\xbd\x31\xa5\x04\xd5\x6e\xdd\x9b\x43\xb7"
+          "\x3f\x11\x24\x52\x10\x80\x4f\x96\x4b\xd4\x80\x67\xb2\xdd\x52\xc9\x4e"
+          "\x02\xc6\xd7\x60\xde\x06\x92\x52\x1e\xdd\x35\x64\x71\x26\x2c\xfe\xcf"
+          "\x81\x46\xb2\x79\x01"),
+      RiceDecodingTestInfo(
+          28,
+          {219354713, 389598618, 750263679, 554684211, 87381124, 4523497,
+           287633354, 801308671, 424169435, 372520475, 277287849},
+          "\xb2\x2c\x26\x3a\xcd\x66\x9c\xdb\x5f\x07\x2e\x6f\xe6\xf9\x21\x10\x52"
+          "\xd5\x94\xf4\x82\x22\x48\xf9\x9d\x24\xf6\xff\x2f\xfc\x6d\x3f\x21\x65"
+          "\x1b\x36\x34\x56\xea\xc4\x21\x00"),
+  };
+
+  // ----- End of Chromium test code ----
+
+  for (auto tdc : TESTING_DATA_CHROMIUM) {
+    // Populate chromium testing data to our native testing data struct.
+    TestingData d;
+
+    d.mRiceParameter = tdc.mRiceParameter;  // Populate rice parameter.
+
+    // Populate encoded data from std::string to vector<uint8>.
+    d.mEncoded.resize(tdc.mEncoded.size());
+    memcpy(&d.mEncoded[0], tdc.mEncoded.c_str(), tdc.mEncoded.size());
+
+    // Populate deltas to expected decoded data. The first value would be just
+    // set to an arbitrary value, say 7, to avoid any assumption to the
+    // first value in the implementation.
+    d.mExpectedDecoded.resize(tdc.mDeltas.size() + 1);
+    for (size_t i = 0; i < d.mExpectedDecoded.size(); i++) {
+      if (0 == i) {
+        d.mExpectedDecoded[i] = 7;  // "7" is an arbitrary starting value
+      } else {
+        d.mExpectedDecoded[i] = d.mExpectedDecoded[i - 1] + tdc.mDeltas[i - 1];
+      }
+    }
+
+    ASSERT_TRUE(runOneTest(d));
+  }
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestSafeBrowsingProtobuf.cpp b/toolkit/components/url-classifier/tests/gtest/TestSafeBrowsingProtobuf.cpp
new file mode 100644
index 0000000000..aa15344324
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestSafeBrowsingProtobuf.cpp
@@ -0,0 +1,30 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "safebrowsing.pb.h"
+
+#include "Common.h"
+
+TEST(UrlClassifierProtobuf, Empty)
+{
+  using namespace mozilla::safebrowsing;
+
+  const std::string CLIENT_ID = "firefox";
+
+  // Construct a simple update request.
+  FetchThreatListUpdatesRequest r;
+  r.set_allocated_client(new ClientInfo());
+  r.mutable_client()->set_client_id(CLIENT_ID);
+
+  // Then serialize.
+  std::string s;
+  r.SerializeToString(&s);
+
+  // De-serialize.
+  FetchThreatListUpdatesRequest r2;
+  r2.ParseFromString(s);
+
+  ASSERT_EQ(r2.client().client_id(), CLIENT_ID);
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestSafebrowsingHash.cpp b/toolkit/components/url-classifier/tests/gtest/TestSafebrowsingHash.cpp
new file mode 100644
index 0000000000..2fc4c793f7
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestSafebrowsingHash.cpp
@@ -0,0 +1,58 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/EndianUtils.h"
+
+#include "Common.h"
+
+TEST(UrlClassifierHash, ToFromUint32)
+{
+  using namespace mozilla::safebrowsing;
+
+  // typedef SafebrowsingHash<PREFIX_SIZE, PrefixComparator> Prefix;
+  // typedef nsTArray<Prefix> PrefixArray;
+
+  const char PREFIX_RAW[4] = {0x1, 0x2, 0x3, 0x4};
+  uint32_t PREFIX_UINT32;
+  memcpy(&PREFIX_UINT32, PREFIX_RAW, 4);
+
+  Prefix p;
+  p.Assign(nsCString(PREFIX_RAW, 4));
+  ASSERT_EQ(p.ToUint32(), PREFIX_UINT32);
+
+  p.FromUint32(PREFIX_UINT32);
+  ASSERT_EQ(memcmp(PREFIX_RAW, p.buf, 4), 0);
+}
+
+TEST(UrlClassifierHash, Compare)
+{
+  using namespace mozilla;
+  using namespace mozilla::safebrowsing;
+
+  Prefix p1, p2, p3;
+
+  // The order of p1,p2,p3 is "p1 == p3 < p2"
+#if MOZ_LITTLE_ENDIAN()
+  p1.Assign(nsCString("\x01\x00\x00\x00", 4));
+  p2.Assign(nsCString("\x00\x00\x00\x01", 4));
+  p3.Assign(nsCString("\x01\x00\x00\x00", 4));
+#else
+  p1.Assign(nsCString("\x00\x00\x00\x01", 4));
+  p2.Assign(nsCString("\x01\x00\x00\x00", 4));
+  p3.Assign(nsCString("\x00\x00\x00\x01", 4));
+#endif
+
+  // Make sure "p1 == p3 < p2" is true
+  // on both little and big endian machine.
+
+  ASSERT_EQ(p1.Compare(p2), -1);
+  ASSERT_EQ(p1.Compare(p1), 0);
+  ASSERT_EQ(p2.Compare(p1), 1);
+  ASSERT_EQ(p1.Compare(p3), 0);
+
+  ASSERT_TRUE(p1 < p2);
+  ASSERT_TRUE(p1 == p1);
+  ASSERT_TRUE(p1 == p3);
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestTable.cpp b/toolkit/components/url-classifier/tests/gtest/TestTable.cpp
new file mode 100644
index 0000000000..796f40b265
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestTable.cpp
@@ -0,0 +1,59 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "nsUrlClassifierDBService.h"
+
+#include "Common.h"
+
+static void TestResponseCode(const char* table, nsresult result) {
+  nsCString tableName(table);
+  ASSERT_EQ(TablesToResponse(tableName), result);
+}
+
+TEST(UrlClassifierTable, ResponseCode)
+{
+  // malware URIs.
+  TestResponseCode("goog-malware-shavar", NS_ERROR_MALWARE_URI);
+  TestResponseCode("test-malware-simple", NS_ERROR_MALWARE_URI);
+  TestResponseCode("goog-phish-shavar,test-malware-simple",
+                   NS_ERROR_MALWARE_URI);
+  TestResponseCode(
+      "test-malware-simple,mozstd-track-digest256,mozplugin-block-digest256",
+      NS_ERROR_MALWARE_URI);
+
+  // phish URIs.
+  TestResponseCode("goog-phish-shavar", NS_ERROR_PHISHING_URI);
+  TestResponseCode("test-phish-simple", NS_ERROR_PHISHING_URI);
+  TestResponseCode("test-phish-simple,mozplugin-block-digest256",
+                   NS_ERROR_PHISHING_URI);
+  TestResponseCode(
+      "mozstd-track-digest256,test-phish-simple,goog-unwanted-shavar",
+      NS_ERROR_PHISHING_URI);
+
+  // unwanted URIs.
+  TestResponseCode("goog-unwanted-shavar", NS_ERROR_UNWANTED_URI);
+  TestResponseCode("test-unwanted-simple", NS_ERROR_UNWANTED_URI);
+  TestResponseCode("mozplugin-unwanted-digest256,mozfull-track-digest256",
+                   NS_ERROR_UNWANTED_URI);
+  TestResponseCode(
+      "test-block-simple,mozfull-track-digest256,test-unwanted-simple",
+      NS_ERROR_UNWANTED_URI);
+
+  // track URIs.
+  TestResponseCode("test-track-simple", NS_ERROR_TRACKING_URI);
+  TestResponseCode("mozstd-track-digest256", NS_ERROR_TRACKING_URI);
+  TestResponseCode("test-block-simple,mozstd-track-digest256",
+                   NS_ERROR_TRACKING_URI);
+
+  // block URIs
+  TestResponseCode("test-block-simple", NS_ERROR_BLOCKED_URI);
+  TestResponseCode("mozplugin-block-digest256", NS_ERROR_BLOCKED_URI);
+  TestResponseCode("mozplugin2-block-digest256", NS_ERROR_BLOCKED_URI);
+
+  TestResponseCode("test-trackwhite-simple", NS_OK);
+  TestResponseCode("mozstd-trackwhite-digest256", NS_OK);
+  TestResponseCode("goog-badbinurl-shavar", NS_OK);
+  TestResponseCode("goog-downloadwhite-digest256", NS_OK);
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestURLsAndHashing.cpp b/toolkit/components/url-classifier/tests/gtest/TestURLsAndHashing.cpp
new file mode 100644
index 0000000000..0563c6a776
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestURLsAndHashing.cpp
@@ -0,0 +1,71 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "LookupCache.h"
+
+#include "Common.h"
+
+static void VerifyFragments(const nsACString& aURL,
+                            const nsTArray<nsCString>& aExpected) {
+  nsTArray<nsCString> fragments;
+  nsresult rv = LookupCache::GetLookupFragments(aURL, &fragments);
+  ASSERT_EQ(rv, NS_OK) << "GetLookupFragments should not fail";
+
+  ASSERT_EQ(aExpected.Length(), fragments.Length())
+      << "Fragments generated from " << aURL.BeginReading()
+      << " are not the same as expected";
+
+  for (const auto& fragment : fragments) {
+    ASSERT_TRUE(aExpected.Contains(fragment))
+    << "Fragments generated from " << aURL.BeginReading()
+    << " are not the same as expected";
+  }
+}
+
+// This testcase references SafeBrowsing spec:
+// https://developers.google.com/safe-browsing/v4/urls-hashing#suffixprefix-expressions
+TEST(URLsAndHashing, FragmentURLWithQuery)
+{
+  const nsLiteralCString url("a.b.c/1/2.html?param=1");
+  nsTArray<nsCString> expect = {
+      "a.b.c/1/2.html?param=1"_ns,
+      "a.b.c/1/2.html"_ns,
+      "a.b.c/"_ns,
+      "a.b.c/1/"_ns,
+      "b.c/1/2.html?param=1"_ns,
+      "b.c/1/2.html"_ns,
+      "b.c/"_ns,
+      "b.c/1/"_ns,
+  };
+
+  VerifyFragments(url, expect);
+}
+
+// This testcase references SafeBrowsing spec:
+// https://developers.google.com/safe-browsing/v4/urls-hashing#suffixprefix-expressions
+TEST(URLsAndHashing, FragmentURLWithoutQuery)
+{
+  const nsLiteralCString url("a.b.c.d.e.f.g/1.html");
+  nsTArray<nsCString> expect = {
+      "a.b.c.d.e.f.g/1.html"_ns, "a.b.c.d.e.f.g/"_ns,
+      "c.d.e.f.g/1.html"_ns,     "c.d.e.f.g/"_ns,
+      "d.e.f.g/1.html"_ns,       "d.e.f.g/"_ns,
+      "e.f.g/1.html"_ns,         "e.f.g/"_ns,
+      "f.g/1.html"_ns,           "f.g/"_ns,
+  };
+
+  VerifyFragments(url, expect);
+}
+
+TEST(URLsAndHashing, FragmentURLEndWithoutPath)
+{
+  const nsLiteralCString url("1.2.3.4/?query=string");
+  nsTArray<nsCString> expect = {
+      "1.2.3.4/?query=string"_ns,
+      "1.2.3.4/"_ns,
+  };
+
+  VerifyFragments(url, expect);
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestUrlClassifierTableUpdateV4.cpp b/toolkit/components/url-classifier/tests/gtest/TestUrlClassifierTableUpdateV4.cpp
new file mode 100644
index 0000000000..d4dec867bd
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestUrlClassifierTableUpdateV4.cpp
@@ -0,0 +1,785 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "Classifier.h"
+#include "HashStore.h"
+#include "mozilla/Components.h"
+#include "mozilla/Unused.h"
+#include "nsAppDirectoryServiceDefs.h"
+#include "nsIFile.h"
+#include "nsThreadUtils.h"
+#include "string.h"
+#include "LookupCacheV4.h"
+#include "nsUrlClassifierUtils.h"
+
+#include "Common.h"
+
+#define GTEST_SAFEBROWSING_DIR "safebrowsing"_ns
+#define GTEST_TABLE "gtest-malware-proto"_ns
+#define GTEST_PREFIXFILE "gtest-malware-proto.vlpset"_ns
+
+// This function removes common elements of inArray and outArray from
+// outArray. This is used by partial update testcase to ensure partial update
+// data won't contain prefixes we already have.
+static void RemoveIntersection(const _PrefixArray& inArray,
+                               _PrefixArray& outArray) {
+  for (uint32_t i = 0; i < inArray.Length(); i++) {
+    int32_t idx = outArray.BinaryIndexOf(inArray[i]);
+    if (idx >= 0) {
+      outArray.RemoveElementAt(idx);
+    }
+  }
+}
+
+// This fucntion removes elements from outArray by index specified in
+// removal array.
+static void RemoveElements(const nsTArray<uint32_t>& removal,
+                           _PrefixArray& outArray) {
+  for (int32_t i = removal.Length() - 1; i >= 0; i--) {
+    outArray.RemoveElementAt(removal[i]);
+  }
+}
+
+static void MergeAndSortArray(const _PrefixArray& array1,
+                              const _PrefixArray& array2,
+                              _PrefixArray& output) {
+  output.Clear();
+  output.AppendElements(array1);
+  output.AppendElements(array2);
+  output.Sort();
+}
+
+static void CalculateSHA256(_PrefixArray& prefixArray, nsCString& sha256) {
+  prefixArray.Sort();
+
+  nsresult rv;
+  nsCOMPtr<nsICryptoHash> cryptoHash =
+      do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID, &rv);
+
+  cryptoHash->Init(nsICryptoHash::SHA256);
+  for (uint32_t i = 0; i < prefixArray.Length(); i++) {
+    const _Prefix& prefix = prefixArray[i];
+    cryptoHash->Update(
+        reinterpret_cast<uint8_t*>(const_cast<char*>(prefix.get())),
+        prefix.Length());
+  }
+  cryptoHash->Finish(false, sha256);
+}
+
+// N: Number of prefixes, MIN/MAX: minimum/maximum prefix size
+// This function will append generated prefixes to outArray.
+static void CreateRandomSortedPrefixArray(uint32_t N, uint32_t MIN,
+                                          uint32_t MAX,
+                                          _PrefixArray& outArray) {
+  outArray.SetCapacity(outArray.Length() + N);
+
+  const uint32_t range = (MAX - MIN + 1);
+
+  for (uint32_t i = 0; i < N; i++) {
+    uint32_t prefixSize = (rand() % range) + MIN;
+    _Prefix prefix;
+    prefix.SetLength(prefixSize);
+
+    while (true) {
+      char* dst = prefix.BeginWriting();
+      for (uint32_t j = 0; j < prefixSize; j++) {
+        dst[j] = rand() % 256;
+      }
+
+      if (!outArray.Contains(prefix)) {
+        outArray.AppendElement(prefix);
+        break;
+      }
+    }
+  }
+
+  outArray.Sort();
+}
+
+// N: Number of removal indices, MAX: maximum index
+static void CreateRandomRemovalIndices(uint32_t N, uint32_t MAX,
+                                       nsTArray<uint32_t>& outArray) {
+  for (uint32_t i = 0; i < N; i++) {
+    uint32_t idx = rand() % MAX;
+    if (!outArray.Contains(idx)) {
+      outArray.InsertElementSorted(idx);
+    }
+  }
+}
+
+// Function to generate TableUpdateV4.
+static void GenerateUpdateData(bool fullUpdate, PrefixStringMap& add,
+                               nsTArray<uint32_t>* removal, nsCString* sha256,
+                               TableUpdateArray& tableUpdates) {
+  RefPtr<TableUpdateV4> tableUpdate = new TableUpdateV4(GTEST_TABLE);
+  tableUpdate->SetFullUpdate(fullUpdate);
+
+  for (const auto& entry : add) {
+    nsCString* pstring = entry.GetWeak();
+    tableUpdate->NewPrefixes(entry.GetKey(), *pstring);
+  }
+
+  if (removal) {
+    tableUpdate->NewRemovalIndices(removal->Elements(), removal->Length());
+  }
+
+  if (sha256) {
+    std::string stdSHA256;
+    stdSHA256.assign(const_cast<char*>(sha256->BeginReading()),
+                     sha256->Length());
+
+    tableUpdate->SetSHA256(stdSHA256);
+  }
+
+  tableUpdates.AppendElement(tableUpdate);
+}
+
+static void VerifyPrefixSet(PrefixStringMap& expected) {
+  // Verify the prefix set is written to disk.
+  nsCOMPtr<nsIFile> file;
+  NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
+  file->AppendNative(GTEST_SAFEBROWSING_DIR);
+
+  RefPtr<LookupCacheV4> lookup =
+      new LookupCacheV4(GTEST_TABLE, "test"_ns, file);
+  lookup->Init();
+
+  file->AppendNative(GTEST_PREFIXFILE);
+  lookup->LoadFromFile(file);
+
+  PrefixStringMap prefixesInFile;
+  lookup->GetPrefixes(prefixesInFile);
+
+  for (const auto& entry : expected) {
+    nsCString* expectedPrefix = entry.GetWeak();
+    nsCString* resultPrefix = prefixesInFile.Get(entry.GetKey());
+
+    ASSERT_TRUE(*resultPrefix == *expectedPrefix);
+  }
+}
+
+static void Clear() {
+  nsCOMPtr<nsIFile> file;
+  NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
+
+  RefPtr<Classifier> classifier = new Classifier();
+  classifier->Open(*file);
+  classifier->Reset();
+}
+
+static void testUpdateFail(TableUpdateArray& tableUpdates) {
+  nsresult rv = SyncApplyUpdates(tableUpdates);
+  ASSERT_NS_FAILED(rv);
+}
+
+static void testUpdate(TableUpdateArray& tableUpdates,
+                       PrefixStringMap& expected) {
+  // Force nsUrlClassifierUtils loading on main thread
+  // because nsIUrlClassifierDBService will not run in advance
+  // in gtest.
+  nsUrlClassifierUtils::GetInstance();
+
+  nsresult rv = SyncApplyUpdates(tableUpdates);
+  ASSERT_TRUE(rv == NS_OK);
+  VerifyPrefixSet(expected);
+}
+
+static void testFullUpdate(PrefixStringMap& add, nsCString* sha256) {
+  TableUpdateArray tableUpdates;
+
+  GenerateUpdateData(true, add, nullptr, sha256, tableUpdates);
+
+  testUpdate(tableUpdates, add);
+}
+
+static void testPartialUpdate(PrefixStringMap& add, nsTArray<uint32_t>* removal,
+                              nsCString* sha256, PrefixStringMap& expected) {
+  TableUpdateArray tableUpdates;
+  GenerateUpdateData(false, add, removal, sha256, tableUpdates);
+
+  testUpdate(tableUpdates, expected);
+}
+
+static void testOpenLookupCache() {
+  nsCOMPtr<nsIFile> file;
+  NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
+  file->AppendNative(GTEST_SAFEBROWSING_DIR);
+
+  RunTestInNewThread([&]() -> void {
+    RefPtr<LookupCacheV4> cache =
+        new LookupCacheV4(nsCString(GTEST_TABLE), ""_ns, file);
+    nsresult rv = cache->Init();
+    ASSERT_EQ(rv, NS_OK);
+
+    rv = cache->Open();
+    ASSERT_EQ(rv, NS_OK);
+  });
+}
+
+// Tests start from here.
+TEST(UrlClassifierTableUpdateV4, FixLengthPSetFullUpdate)
+{
+  srand(time(NULL));
+
+  _PrefixArray array;
+  PrefixStringMap map;
+  nsCString sha256;
+
+  CreateRandomSortedPrefixArray(5000, 4, 4, array);
+  PrefixArrayToPrefixStringMap(array, map);
+  CalculateSHA256(array, sha256);
+
+  testFullUpdate(map, &sha256);
+
+  Clear();
+}
+
+TEST(UrlClassifierTableUpdateV4, VariableLengthPSetFullUpdate)
+{
+  _PrefixArray array;
+  PrefixStringMap map;
+  nsCString sha256;
+
+  CreateRandomSortedPrefixArray(5000, 5, 32, array);
+  PrefixArrayToPrefixStringMap(array, map);
+  CalculateSHA256(array, sha256);
+
+  testFullUpdate(map, &sha256);
+
+  Clear();
+}
+
+// This test contain both variable length prefix set and fixed-length prefix set
+TEST(UrlClassifierTableUpdateV4, MixedPSetFullUpdate)
+{
+  _PrefixArray array;
+  PrefixStringMap map;
+  nsCString sha256;
+
+  CreateRandomSortedPrefixArray(5000, 4, 4, array);
+  CreateRandomSortedPrefixArray(1000, 5, 32, array);
+  PrefixArrayToPrefixStringMap(array, map);
+  CalculateSHA256(array, sha256);
+
+  testFullUpdate(map, &sha256);
+
+  Clear();
+}
+
+TEST(UrlClassifierTableUpdateV4, PartialUpdateWithRemoval)
+{
+  _PrefixArray fArray;
+
+  // Apply a full update first.
+  {
+    PrefixStringMap fMap;
+    nsCString sha256;
+
+    CreateRandomSortedPrefixArray(10000, 4, 4, fArray);
+    CreateRandomSortedPrefixArray(2000, 5, 32, fArray);
+    PrefixArrayToPrefixStringMap(fArray, fMap);
+    CalculateSHA256(fArray, sha256);
+
+    testFullUpdate(fMap, &sha256);
+  }
+
+  // Apply a partial update with removal.
+  {
+    _PrefixArray pArray, mergedArray;
+    PrefixStringMap pMap, mergedMap;
+    nsCString sha256;
+
+    CreateRandomSortedPrefixArray(5000, 4, 4, pArray);
+    CreateRandomSortedPrefixArray(1000, 5, 32, pArray);
+    RemoveIntersection(fArray, pArray);
+    PrefixArrayToPrefixStringMap(pArray, pMap);
+
+    // Remove 1/5 of elements of original prefix set.
+    nsTArray<uint32_t> removal;
+    CreateRandomRemovalIndices(fArray.Length() / 5, fArray.Length(), removal);
+    RemoveElements(removal, fArray);
+
+    // Calculate the expected prefix map.
+    MergeAndSortArray(fArray, pArray, mergedArray);
+    PrefixArrayToPrefixStringMap(mergedArray, mergedMap);
+    CalculateSHA256(mergedArray, sha256);
+
+    testPartialUpdate(pMap, &removal, &sha256, mergedMap);
+  }
+
+  Clear();
+}
+
+TEST(UrlClassifierTableUpdateV4, PartialUpdateWithoutRemoval)
+{
+  _PrefixArray fArray;
+
+  // Apply a full update first.
+  {
+    PrefixStringMap fMap;
+    nsCString sha256;
+
+    CreateRandomSortedPrefixArray(10000, 4, 4, fArray);
+    CreateRandomSortedPrefixArray(2000, 5, 32, fArray);
+    PrefixArrayToPrefixStringMap(fArray, fMap);
+    CalculateSHA256(fArray, sha256);
+
+    testFullUpdate(fMap, &sha256);
+  }
+
+  // Apply a partial update without removal
+  {
+    _PrefixArray pArray, mergedArray;
+    PrefixStringMap pMap, mergedMap;
+    nsCString sha256;
+
+    CreateRandomSortedPrefixArray(5000, 4, 4, pArray);
+    CreateRandomSortedPrefixArray(1000, 5, 32, pArray);
+    RemoveIntersection(fArray, pArray);
+    PrefixArrayToPrefixStringMap(pArray, pMap);
+
+    // Calculate the expected prefix map.
+    MergeAndSortArray(fArray, pArray, mergedArray);
+    PrefixArrayToPrefixStringMap(mergedArray, mergedMap);
+    CalculateSHA256(mergedArray, sha256);
+
+    testPartialUpdate(pMap, nullptr, &sha256, mergedMap);
+  }
+
+  Clear();
+}
+
+// Expect failure because partial update contains prefix already
+// in old prefix set.
+TEST(UrlClassifierTableUpdateV4, PartialUpdatePrefixAlreadyExist)
+{
+  _PrefixArray fArray;
+
+  // Apply a full update fist.
+  {
+    PrefixStringMap fMap;
+    nsCString sha256;
+
+    CreateRandomSortedPrefixArray(1000, 4, 32, fArray);
+    PrefixArrayToPrefixStringMap(fArray, fMap);
+    CalculateSHA256(fArray, sha256);
+
+    testFullUpdate(fMap, &sha256);
+  }
+
+  // Apply a partial update which contains a prefix in previous full update.
+  // This should cause an update error.
+  {
+    _PrefixArray pArray;
+    PrefixStringMap pMap;
+    TableUpdateArray tableUpdates;
+
+    // Pick one prefix from full update prefix and add it to partial update.
+    // This should result a failure when call ApplyUpdates.
+    pArray.AppendElement(fArray[rand() % fArray.Length()]);
+    CreateRandomSortedPrefixArray(200, 4, 32, pArray);
+    PrefixArrayToPrefixStringMap(pArray, pMap);
+
+    GenerateUpdateData(false, pMap, nullptr, nullptr, tableUpdates);
+    testUpdateFail(tableUpdates);
+  }
+
+  Clear();
+}
+
+// Test apply partial update directly without applying an full update first.
+TEST(UrlClassifierTableUpdateV4, OnlyPartialUpdate)
+{
+  _PrefixArray pArray;
+  PrefixStringMap pMap;
+  nsCString sha256;
+
+  CreateRandomSortedPrefixArray(5000, 4, 4, pArray);
+  CreateRandomSortedPrefixArray(1000, 5, 32, pArray);
+  PrefixArrayToPrefixStringMap(pArray, pMap);
+  CalculateSHA256(pArray, sha256);
+
+  testPartialUpdate(pMap, nullptr, &sha256, pMap);
+
+  Clear();
+}
+
+// Test partial update without any ADD prefixes, only removalIndices.
+TEST(UrlClassifierTableUpdateV4, PartialUpdateOnlyRemoval)
+{
+  _PrefixArray fArray;
+
+  // Apply a full update first.
+  {
+    PrefixStringMap fMap;
+    nsCString sha256;
+
+    CreateRandomSortedPrefixArray(5000, 4, 4, fArray);
+    CreateRandomSortedPrefixArray(1000, 5, 32, fArray);
+    PrefixArrayToPrefixStringMap(fArray, fMap);
+    CalculateSHA256(fArray, sha256);
+
+    testFullUpdate(fMap, &sha256);
+  }
+
+  // Apply a partial update without add prefix, only contain removal indices.
+  {
+    _PrefixArray pArray;
+    PrefixStringMap pMap, mergedMap;
+    nsCString sha256;
+
+    // Remove 1/5 of elements of original prefix set.
+    nsTArray<uint32_t> removal;
+    CreateRandomRemovalIndices(fArray.Length() / 5, fArray.Length(), removal);
+    RemoveElements(removal, fArray);
+
+    PrefixArrayToPrefixStringMap(fArray, mergedMap);
+    CalculateSHA256(fArray, sha256);
+
+    testPartialUpdate(pMap, &removal, &sha256, mergedMap);
+  }
+
+  Clear();
+}
+
+// Test one tableupdate array contains full update and multiple partial updates.
+TEST(UrlClassifierTableUpdateV4, MultipleTableUpdates)
+{
+  _PrefixArray fArray, pArray, mergedArray;
+  PrefixStringMap fMap, pMap, mergedMap;
+  nsCString sha256;
+
+  TableUpdateArray tableUpdates;
+
+  // Generate first full udpate
+  CreateRandomSortedPrefixArray(10000, 4, 4, fArray);
+  CreateRandomSortedPrefixArray(2000, 5, 32, fArray);
+  PrefixArrayToPrefixStringMap(fArray, fMap);
+  CalculateSHA256(fArray, sha256);
+
+  GenerateUpdateData(true, fMap, nullptr, &sha256, tableUpdates);
+
+  // Generate second partial update
+  CreateRandomSortedPrefixArray(3000, 4, 4, pArray);
+  CreateRandomSortedPrefixArray(1000, 5, 32, pArray);
+  RemoveIntersection(fArray, pArray);
+  PrefixArrayToPrefixStringMap(pArray, pMap);
+
+  MergeAndSortArray(fArray, pArray, mergedArray);
+  CalculateSHA256(mergedArray, sha256);
+
+  GenerateUpdateData(false, pMap, nullptr, &sha256, tableUpdates);
+
+  // Generate thrid partial update
+  fArray.AppendElements(pArray);
+  fArray.Sort();
+  pArray.Clear();
+  CreateRandomSortedPrefixArray(3000, 4, 4, pArray);
+  CreateRandomSortedPrefixArray(1000, 5, 32, pArray);
+  RemoveIntersection(fArray, pArray);
+  PrefixArrayToPrefixStringMap(pArray, pMap);
+
+  // Remove 1/5 of elements of original prefix set.
+  nsTArray<uint32_t> removal;
+  CreateRandomRemovalIndices(fArray.Length() / 5, fArray.Length(), removal);
+  RemoveElements(removal, fArray);
+
+  MergeAndSortArray(fArray, pArray, mergedArray);
+  PrefixArrayToPrefixStringMap(mergedArray, mergedMap);
+  CalculateSHA256(mergedArray, sha256);
+
+  GenerateUpdateData(false, pMap, &removal, &sha256, tableUpdates);
+
+  testUpdate(tableUpdates, mergedMap);
+
+  Clear();
+}
+
+// Test apply full update first, and then apply multiple partial updates
+// in one tableupdate array.
+TEST(UrlClassifierTableUpdateV4, MultiplePartialUpdateTableUpdates)
+{
+  _PrefixArray fArray;
+
+  // Apply a full update first
+  {
+    PrefixStringMap fMap;
+    nsCString sha256;
+
+    // Generate first full udpate
+    CreateRandomSortedPrefixArray(10000, 4, 4, fArray);
+    CreateRandomSortedPrefixArray(3000, 5, 32, fArray);
+    PrefixArrayToPrefixStringMap(fArray, fMap);
+    CalculateSHA256(fArray, sha256);
+
+    testFullUpdate(fMap, &sha256);
+  }
+
+  // Apply multiple partial updates in one table update
+  {
+    _PrefixArray pArray, mergedArray;
+    PrefixStringMap pMap, mergedMap;
+    nsCString sha256;
+    nsTArray<uint32_t> removal;
+    TableUpdateArray tableUpdates;
+
+    // Generate first partial update
+    CreateRandomSortedPrefixArray(3000, 4, 4, pArray);
+    CreateRandomSortedPrefixArray(1000, 5, 32, pArray);
+    RemoveIntersection(fArray, pArray);
+    PrefixArrayToPrefixStringMap(pArray, pMap);
+
+    // Remove 1/5 of elements of original prefix set.
+    CreateRandomRemovalIndices(fArray.Length() / 5, fArray.Length(), removal);
+    RemoveElements(removal, fArray);
+
+    MergeAndSortArray(fArray, pArray, mergedArray);
+    CalculateSHA256(mergedArray, sha256);
+
+    GenerateUpdateData(false, pMap, &removal, &sha256, tableUpdates);
+
+    fArray.AppendElements(pArray);
+    fArray.Sort();
+    pArray.Clear();
+    removal.Clear();
+
+    // Generate second partial update.
+    CreateRandomSortedPrefixArray(2000, 4, 4, pArray);
+    CreateRandomSortedPrefixArray(1000, 5, 32, pArray);
+    RemoveIntersection(fArray, pArray);
+    PrefixArrayToPrefixStringMap(pArray, pMap);
+
+    // Remove 1/5 of elements of original prefix set.
+    CreateRandomRemovalIndices(fArray.Length() / 5, fArray.Length(), removal);
+    RemoveElements(removal, fArray);
+
+    MergeAndSortArray(fArray, pArray, mergedArray);
+    PrefixArrayToPrefixStringMap(mergedArray, mergedMap);
+    CalculateSHA256(mergedArray, sha256);
+
+    GenerateUpdateData(false, pMap, &removal, &sha256, tableUpdates);
+
+    testUpdate(tableUpdates, mergedMap);
+  }
+
+  Clear();
+}
+
+// Test removal indices are larger than the original prefix set.
+TEST(UrlClassifierTableUpdateV4, RemovalIndexTooLarge)
+{
+  _PrefixArray fArray;
+
+  // Apply a full update first
+  {
+    PrefixStringMap fMap;
+    nsCString sha256;
+
+    CreateRandomSortedPrefixArray(1000, 4, 32, fArray);
+    PrefixArrayToPrefixStringMap(fArray, fMap);
+    CalculateSHA256(fArray, sha256);
+
+    testFullUpdate(fMap, &sha256);
+  }
+
+  // Apply a partial update with removal indice array larger than
+  // old prefix set(fArray). This should cause an error.
+  {
+    _PrefixArray pArray;
+    PrefixStringMap pMap;
+    nsTArray<uint32_t> removal;
+    TableUpdateArray tableUpdates;
+
+    CreateRandomSortedPrefixArray(200, 4, 32, pArray);
+    RemoveIntersection(fArray, pArray);
+    PrefixArrayToPrefixStringMap(pArray, pMap);
+
+    for (uint32_t i = 0; i < fArray.Length() + 1; i++) {
+      removal.AppendElement(i);
+    }
+
+    GenerateUpdateData(false, pMap, &removal, nullptr, tableUpdates);
+    testUpdateFail(tableUpdates);
+  }
+
+  Clear();
+}
+
+TEST(UrlClassifierTableUpdateV4, ChecksumMismatch)
+{
+  // Apply a full update first
+  {
+    _PrefixArray fArray;
+    PrefixStringMap fMap;
+    nsCString sha256;
+
+    CreateRandomSortedPrefixArray(1000, 4, 32, fArray);
+    PrefixArrayToPrefixStringMap(fArray, fMap);
+    CalculateSHA256(fArray, sha256);
+
+    testFullUpdate(fMap, &sha256);
+  }
+
+  // Apply a partial update with incorrect sha256
+  {
+    _PrefixArray pArray;
+    PrefixStringMap pMap;
+    nsCString sha256;
+    TableUpdateArray tableUpdates;
+
+    CreateRandomSortedPrefixArray(200, 4, 32, pArray);
+    PrefixArrayToPrefixStringMap(pArray, pMap);
+
+    // sha256 should be calculated with both old prefix set and add prefix
+    // set, here we only calculate sha256 with add prefix set to check if
+    // applyUpdate will return failure.
+    CalculateSHA256(pArray, sha256);
+
+    GenerateUpdateData(false, pMap, nullptr, &sha256, tableUpdates);
+    testUpdateFail(tableUpdates);
+  }
+
+  Clear();
+}
+
+TEST(UrlClassifierTableUpdateV4, ApplyUpdateThenLoad)
+{
+  // Apply update with sha256
+  {
+    _PrefixArray fArray;
+    PrefixStringMap fMap;
+    nsCString sha256;
+
+    CreateRandomSortedPrefixArray(1000, 4, 32, fArray);
+    PrefixArrayToPrefixStringMap(fArray, fMap);
+    CalculateSHA256(fArray, sha256);
+
+    testFullUpdate(fMap, &sha256);
+
+    // Open lookup cache will load prefix set and verify the sha256
+    testOpenLookupCache();
+  }
+
+  Clear();
+
+  // Apply update without sha256
+  {
+    _PrefixArray fArray;
+    PrefixStringMap fMap;
+
+    CreateRandomSortedPrefixArray(1000, 4, 32, fArray);
+    PrefixArrayToPrefixStringMap(fArray, fMap);
+
+    testFullUpdate(fMap, nullptr);
+
+    testOpenLookupCache();
+  }
+
+  Clear();
+}
+
+// This test is used to avoid an eror from nsICryptoHash
+TEST(UrlClassifierTableUpdateV4, ApplyUpdateWithFixedChecksum)
+{
+  _PrefixArray fArray = {_Prefix("enus"),
+                         _Prefix("apollo"),
+                         _Prefix("mars"),
+                         _Prefix("Hecatonchires cyclopes"),
+                         _Prefix("vesta"),
+                         _Prefix("neptunus"),
+                         _Prefix("jupiter"),
+                         _Prefix("diana"),
+                         _Prefix("minerva"),
+                         _Prefix("ceres"),
+                         _Prefix("Aidos,Adephagia,Adikia,Aletheia"),
+                         _Prefix("hecatonchires"),
+                         _Prefix("alcyoneus"),
+                         _Prefix("hades"),
+                         _Prefix("vulcanus"),
+                         _Prefix("juno"),
+                         _Prefix("mercury"),
+                         _Prefix("Stheno, Euryale and Medusa")};
+  fArray.Sort();
+
+  PrefixStringMap fMap;
+  PrefixArrayToPrefixStringMap(fArray, fMap);
+
+  nsCString sha256(
+      "\xae\x18\x94\xd7\xd0\x83\x5f\xc1"
+      "\x58\x59\x5c\x2c\x72\xb9\x6e\x5e"
+      "\xf4\xe8\x0a\x6b\xff\x5e\x6b\x81"
+      "\x65\x34\x06\x16\x06\x59\xa0\x67");
+
+  testFullUpdate(fMap, &sha256);
+
+  // Open lookup cache will load prefix set and verify the sha256
+  testOpenLookupCache();
+
+  Clear();
+}
+
+// This test ensure that an empty update works correctly. Empty update
+// should be skipped by CheckValidUpdate in Classifier::UpdateTableV4.
+TEST(UrlClassifierTableUpdateV4, EmptyUpdate)
+{
+  PrefixStringMap emptyAddition;
+  nsTArray<uint32_t> emptyRemoval;
+
+  _PrefixArray array;
+  PrefixStringMap map;
+  nsCString sha256;
+
+  CalculateSHA256(array, sha256);
+
+  // Test apply empty full/partial update before we already
+  // have data in DB.
+  testFullUpdate(emptyAddition, &sha256);
+  testPartialUpdate(emptyAddition, &emptyRemoval, &sha256, map);
+
+  // Apply an full update.
+  CreateRandomSortedPrefixArray(100, 4, 4, array);
+  CreateRandomSortedPrefixArray(10, 5, 32, array);
+  PrefixArrayToPrefixStringMap(array, map);
+  CalculateSHA256(array, sha256);
+
+  testFullUpdate(map, &sha256);
+
+  // Test apply empty full/partial update when we already
+  // have data in DB
+  testPartialUpdate(emptyAddition, &emptyRemoval, &sha256, map);
+  testFullUpdate(emptyAddition, &sha256);
+
+  Clear();
+}
+
+// This test ensure applying an empty update directly through update algorithm
+// should be correct.
+TEST(UrlClassifierTableUpdateV4, EmptyUpdate2)
+{
+  // Setup LookupCache with initial data
+  _PrefixArray array;
+  CreateRandomSortedPrefixArray(100, 4, 4, array);
+  CreateRandomSortedPrefixArray(10, 5, 32, array);
+  RefPtr<LookupCacheV4> cache = SetupLookupCache<LookupCacheV4>(array);
+
+  // Setup TableUpdate object with only sha256 from previous update(initial
+  // data).
+  nsCString sha256;
+  CalculateSHA256(array, sha256);
+  std::string stdSHA256;
+  stdSHA256.assign(const_cast<char*>(sha256.BeginReading()), sha256.Length());
+
+  RefPtr<TableUpdateV4> tableUpdate = new TableUpdateV4(GTEST_TABLE);
+  tableUpdate->SetSHA256(stdSHA256);
+
+  // Apply update directly through LookupCache interface
+  PrefixStringMap input, output;
+  PrefixArrayToPrefixStringMap(array, input);
+  nsresult rv = cache->ApplyUpdate(tableUpdate.get(), input, output);
+
+  ASSERT_TRUE(rv == NS_OK);
+
+  Clear();
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestUrlClassifierUtils.cpp b/toolkit/components/url-classifier/tests/gtest/TestUrlClassifierUtils.cpp
new file mode 100644
index 0000000000..354a47f07d
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestUrlClassifierUtils.cpp
@@ -0,0 +1,254 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include <ctype.h>
+#include <stdio.h>
+
+#include <mozilla/RefPtr.h>
+#include "nsEscape.h"
+#include "nsString.h"
+#include "nsUrlClassifierUtils.h"
+#include "stdlib.h"
+
+#include "Common.h"
+
+static char int_to_hex_digit(int32_t i) {
+  NS_ASSERTION((i >= 0) && (i <= 15), "int too big in int_to_hex_digit");
+  return static_cast<char>(((i < 10) ? (i + '0') : ((i - 10) + 'A')));
+}
+
+static void CheckEquals(nsCString& expected, nsCString& actual) {
+  ASSERT_TRUE((expected).Equals((actual)))
+  << "Expected:" << expected.get() << ", Actual:" << actual.get();
+}
+
+static void TestUnescapeHelper(const char* in, const char* expected) {
+  nsCString out, strIn(in), strExp(expected);
+
+  NS_UnescapeURL(strIn.get(), strIn.Length(), esc_AlwaysCopy, out);
+  CheckEquals(strExp, out);
+}
+
+static void TestEncodeHelper(const char* in, const char* expected) {
+  nsCString out, strIn(in), strExp(expected);
+  nsUrlClassifierUtils::GetInstance()->SpecialEncode(strIn, true, out);
+  CheckEquals(strExp, out);
+}
+
+static void TestCanonicalizeHelper(const char* in, const char* expected) {
+  nsCString out, strIn(in), strExp(expected);
+  nsUrlClassifierUtils::GetInstance()->CanonicalizePath(strIn, out);
+  CheckEquals(strExp, out);
+}
+
+static void TestCanonicalNumHelper(const char* in, uint32_t bytes,
+                                   bool allowOctal, const char* expected) {
+  nsCString out, strIn(in), strExp(expected);
+  nsUrlClassifierUtils::GetInstance()->CanonicalNum(strIn, bytes, allowOctal,
+                                                    out);
+  CheckEquals(strExp, out);
+}
+
+void TestHostnameHelper(const char* in, const char* expected) {
+  nsCString out, strIn(in), strExp(expected);
+  nsUrlClassifierUtils::GetInstance()->CanonicalizeHostname(strIn, out);
+  CheckEquals(strExp, out);
+}
+
+// Make sure Unescape from nsEncode.h's unescape does what the server does.
+TEST(UrlClassifierUtils, Unescape)
+{
+  // test empty string
+  TestUnescapeHelper("\0", "\0");
+
+  // Test docoding of all characters.
+  nsCString allCharsEncoded, allCharsEncodedLowercase, allCharsAsString;
+  for (int32_t i = 1; i < 256; ++i) {
+    allCharsEncoded.Append('%');
+    allCharsEncoded.Append(int_to_hex_digit(i / 16));
+    allCharsEncoded.Append((int_to_hex_digit(i % 16)));
+
+    allCharsEncodedLowercase.Append('%');
+    allCharsEncodedLowercase.Append(tolower(int_to_hex_digit(i / 16)));
+    allCharsEncodedLowercase.Append(tolower(int_to_hex_digit(i % 16)));
+
+    allCharsAsString.Append(static_cast<char>(i));
+  }
+
+  nsCString out;
+  NS_UnescapeURL(allCharsEncoded.get(), allCharsEncoded.Length(),
+                 esc_AlwaysCopy, out);
+
+  CheckEquals(allCharsAsString, out);
+
+  out.Truncate();
+  NS_UnescapeURL(allCharsEncodedLowercase.get(),
+                 allCharsEncodedLowercase.Length(), esc_AlwaysCopy, out);
+  CheckEquals(allCharsAsString, out);
+
+  // Test %-related edge cases
+  TestUnescapeHelper("%", "%");
+  TestUnescapeHelper("%xx", "%xx");
+  TestUnescapeHelper("%%", "%%");
+  TestUnescapeHelper("%%%", "%%%");
+  TestUnescapeHelper("%%%%", "%%%%");
+  TestUnescapeHelper("%1", "%1");
+  TestUnescapeHelper("%1z", "%1z");
+  TestUnescapeHelper("a%1z", "a%1z");
+  TestUnescapeHelper("abc%d%e%fg%hij%klmno%", "abc%d%e%fg%hij%klmno%");
+
+  // A few more tests
+  TestUnescapeHelper("%25", "%");
+  TestUnescapeHelper("%25%32%35", "%25");
+}
+
+TEST(UrlClassifierUtils, Enc)
+{
+  // Test empty string
+  TestEncodeHelper("", "");
+
+  // Test that all characters we shouldn't encode ([33-34],36,[38,126]) are not.
+  nsCString noenc;
+  for (int32_t i = 33; i < 127; i++) {
+    if (i != 35 && i != 37) {  // skip %
+      noenc.Append(static_cast<char>(i));
+    }
+  }
+  nsCString out;
+  nsUrlClassifierUtils::GetInstance()->SpecialEncode(noenc, false, out);
+  CheckEquals(noenc, out);
+
+  // Test that all the chars that we should encode [0,32],35, 37,[127,255] are
+  nsCString yesAsString, yesExpectedString;
+  for (int32_t i = 1; i < 256; i++) {
+    if (i < 33 || i == 35 || i == 37 || i > 126) {
+      yesAsString.Append(static_cast<char>(i));
+      yesExpectedString.Append('%');
+      yesExpectedString.Append(int_to_hex_digit(i / 16));
+      yesExpectedString.Append(int_to_hex_digit(i % 16));
+    }
+  }
+
+  out.Truncate();
+  nsUrlClassifierUtils::GetInstance()->SpecialEncode(yesAsString, false, out);
+  CheckEquals(yesExpectedString, out);
+
+  TestEncodeHelper("blah//blah", "blah/blah");
+}
+
+TEST(UrlClassifierUtils, Canonicalize)
+{
+  // Test repeated %-decoding. Note: %25 --> %, %32 --> 2, %35 --> 5
+  TestCanonicalizeHelper("%25", "%25");
+  TestCanonicalizeHelper("%25%32%35", "%25");
+  TestCanonicalizeHelper("asdf%25%32%35asd", "asdf%25asd");
+  TestCanonicalizeHelper("%%%25%32%35asd%%", "%25%25%25asd%25%25");
+  TestCanonicalizeHelper("%25%32%35%25%32%35%25%32%35", "%25%25%25");
+  TestCanonicalizeHelper("%25", "%25");
+  TestCanonicalizeHelper(
+      "%257Ea%2521b%2540c%2523d%2524e%25f%255E00%252611%252A22%252833%252944_"
+      "55%252B",
+      "~a!b@c%23d$e%25f^00&11*22(33)44_55+");
+
+  TestCanonicalizeHelper("", "");
+  TestCanonicalizeHelper(
+      "%31%36%38%2e%31%38%38%2e%39%39%2e%32%36/%2E%73%65%63%75%72%65/"
+      "%77%77%77%2E%65%62%61%79%2E%63%6F%6D/",
+      "168.188.99.26/.secure/www.ebay.com/");
+  TestCanonicalizeHelper(
+      "195.127.0.11/uploads/%20%20%20%20/.verify/"
+      ".eBaysecure=updateuserdataxplimnbqmn-xplmvalidateinfoswqpcmlx=hgplmcx/",
+      "195.127.0.11/uploads/%20%20%20%20/.verify/"
+      ".eBaysecure=updateuserdataxplimnbqmn-xplmvalidateinfoswqpcmlx=hgplmcx/");
+  // Added in bug 489455.  %00 should no longer be changed to %01.
+  TestCanonicalizeHelper("%00", "%00");
+}
+
+void TestParseIPAddressHelper(const char* in, const char* expected) {
+  nsCString out, strIn(in), strExp(expected);
+  nsUrlClassifierUtils::GetInstance()->ParseIPAddress(strIn, out);
+  CheckEquals(strExp, out);
+}
+
+TEST(UrlClassifierUtils, ParseIPAddress)
+{
+  TestParseIPAddressHelper("123.123.0.0.1", "");
+  TestParseIPAddressHelper("255.0.0.1", "255.0.0.1");
+  TestParseIPAddressHelper("12.0x12.01234", "12.18.2.156");
+  TestParseIPAddressHelper("276.2.3", "20.2.0.3");
+  TestParseIPAddressHelper("012.034.01.055", "10.28.1.45");
+  TestParseIPAddressHelper("0x12.0x43.0x44.0x01", "18.67.68.1");
+  TestParseIPAddressHelper("167838211", "10.1.2.3");
+  TestParseIPAddressHelper("3279880203", "195.127.0.11");
+  TestParseIPAddressHelper("0x12434401", "18.67.68.1");
+  TestParseIPAddressHelper("413960661", "24.172.137.213");
+  TestParseIPAddressHelper("03053104725", "24.172.137.213");
+  TestParseIPAddressHelper("030.0254.0x89d5", "24.172.137.213");
+  TestParseIPAddressHelper("1.234.4.0377", "1.234.4.255");
+  TestParseIPAddressHelper("1.2.3.00x0", "");
+  TestParseIPAddressHelper("10.192.95.89 xy", "10.192.95.89");
+  TestParseIPAddressHelper("10.192.95.89 xyz", "");
+  TestParseIPAddressHelper("1.2.3.0x0", "1.2.3.0");
+  TestParseIPAddressHelper("1.2.3.4", "1.2.3.4");
+}
+
+TEST(UrlClassifierUtils, CanonicalNum)
+{
+  TestCanonicalNumHelper("", 1, true, "");
+  TestCanonicalNumHelper("10", 0, true, "");
+  TestCanonicalNumHelper("45", 1, true, "45");
+  TestCanonicalNumHelper("0x10", 1, true, "16");
+  TestCanonicalNumHelper("367", 2, true, "1.111");
+  TestCanonicalNumHelper("012345", 3, true, "0.20.229");
+  TestCanonicalNumHelper("0173", 1, true, "123");
+  TestCanonicalNumHelper("09", 1, false, "9");
+  TestCanonicalNumHelper("0x120x34", 2, true, "");
+  TestCanonicalNumHelper("0x12fc", 2, true, "18.252");
+  TestCanonicalNumHelper("3279880203", 4, true, "195.127.0.11");
+  TestCanonicalNumHelper("0x0000059", 1, true, "89");
+  TestCanonicalNumHelper("0x00000059", 1, true, "89");
+  TestCanonicalNumHelper("0x0000067", 1, true, "103");
+}
+
+TEST(UrlClassifierUtils, Hostname)
+{
+  TestHostnameHelper("abcd123;[]", "abcd123;[]");
+  TestHostnameHelper("abc.123", "abc.123");
+  TestHostnameHelper("abc..123", "abc.123");
+  TestHostnameHelper("trailing.", "trailing");
+  TestHostnameHelper("i love trailing dots....", "i%20love%20trailing%20dots");
+  TestHostnameHelper(".leading", "leading");
+  TestHostnameHelper("..leading", "leading");
+  TestHostnameHelper(".dots.", "dots");
+  TestHostnameHelper(".both.", "both");
+  TestHostnameHelper(".both..", "both");
+  TestHostnameHelper("..both.", "both");
+  TestHostnameHelper("..both..", "both");
+  TestHostnameHelper("..a.b.c.d..", "a.b.c.d");
+  TestHostnameHelper("..127.0.0.1..", "127.0.0.1");
+  TestHostnameHelper("AB CD 12354", "ab%20cd%2012354");
+  TestHostnameHelper("\1\2\3\4\112\177", "%01%02%03%04j%7F");
+  TestHostnameHelper("<>.AS/-+", "<>.as/-+");
+  // Added in bug 489455.  %00 should no longer be changed to %01.
+  TestHostnameHelper("%00", "%00");
+}
+
+TEST(UrlClassifierUtils, LongHostname)
+{
+  static const int kTestSize = 1024 * 150;
+  char* str = static_cast<char*>(malloc(kTestSize + 1));
+  memset(str, 'x', kTestSize);
+  str[kTestSize] = '\0';
+
+  nsAutoCString out;
+  nsDependentCString in(str);
+  PRIntervalTime clockStart = PR_IntervalNow();
+  nsUrlClassifierUtils::GetInstance()->CanonicalizeHostname(in, out);
+  PRIntervalTime clockEnd = PR_IntervalNow();
+
+  CheckEquals(in, out);
+
+  printf("CanonicalizeHostname on long string (%dms)\n",
+         PR_IntervalToMilliseconds(clockEnd - clockStart));
+}
diff --git a/toolkit/components/url-classifier/tests/gtest/TestVariableLengthPrefixSet.cpp b/toolkit/components/url-classifier/tests/gtest/TestVariableLengthPrefixSet.cpp
new file mode 100644
index 0000000000..6eb36a12d2
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/TestVariableLengthPrefixSet.cpp
@@ -0,0 +1,486 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "LookupCacheV4.h"
+#include "mozilla/Preferences.h"
+#include <mozilla/RefPtr.h>
+#include "nsAppDirectoryServiceDefs.h"
+#include "nsClassHashtable.h"
+#include "nsString.h"
+#include "VariableLengthPrefixSet.h"
+
+#include "Common.h"
+
+// Create fullhash by appending random characters.
+static nsCString CreateFullHash(const nsACString& in) {
+  nsCString out(in);
+  out.SetLength(32);
+  for (size_t i = in.Length(); i < 32; i++) {
+    out.SetCharAt(char(rand() % 256), i);
+  }
+
+  return out;
+}
+
+// This function generate N prefixes with size between MIN and MAX.
+// The output array will not be cleared, random result will append to it
+static void RandomPrefixes(uint32_t N, uint32_t MIN, uint32_t MAX,
+                           _PrefixArray& array) {
+  array.SetCapacity(array.Length() + N);
+
+  uint32_t range = (MAX - MIN + 1);
+
+  for (uint32_t i = 0; i < N; i++) {
+    uint32_t prefixSize = (rand() % range) + MIN;
+    _Prefix prefix;
+    prefix.SetLength(prefixSize);
+
+    bool added = false;
+    while (!added) {
+      char* dst = prefix.BeginWriting();
+      for (uint32_t j = 0; j < prefixSize; j++) {
+        dst[j] = rand() % 256;
+      }
+
+      if (!array.Contains(prefix)) {
+        array.AppendElement(prefix);
+        added = true;
+      }
+    }
+  }
+}
+
+// This test loops through all the prefixes and converts each prefix to
+// fullhash by appending random characters, each converted fullhash
+// should at least match its original length in the prefixSet.
+static void DoExpectedLookup(LookupCacheV4* cache, _PrefixArray& array) {
+  uint32_t matchLength = 0;
+  for (uint32_t i = 0; i < array.Length(); i++) {
+    const nsCString& prefix = array[i];
+    Completion complete;
+    complete.Assign(CreateFullHash(prefix));
+
+    // Find match for prefix-generated full hash
+    bool has, confirmed;
+    cache->Has(complete, &has, &matchLength, &confirmed);
+    MOZ_ASSERT(matchLength != 0);
+
+    if (matchLength != prefix.Length()) {
+      // Return match size is not the same as prefix size.
+      // In this case it could be because the generated fullhash match other
+      // prefixes, check if this prefix exist.
+      bool found = false;
+
+      for (uint32_t j = 0; j < array.Length(); j++) {
+        if (array[j].Length() != matchLength) {
+          continue;
+        }
+
+        if (0 == memcmp(complete.buf, array[j].BeginReading(), matchLength)) {
+          found = true;
+          break;
+        }
+      }
+      ASSERT_TRUE(found);
+    }
+  }
+}
+
+static void DoRandomLookup(LookupCacheV4* cache, uint32_t N,
+                           _PrefixArray& array) {
+  for (uint32_t i = 0; i < N; i++) {
+    // Random 32-bytes test fullhash
+    char buf[32];
+    for (uint32_t j = 0; j < 32; j++) {
+      buf[j] = (char)(rand() % 256);
+    }
+
+    // Get the expected result.
+    nsTArray<uint32_t> expected;
+    for (uint32_t j = 0; j < array.Length(); j++) {
+      const nsACString& str = array[j];
+      if (0 == memcmp(buf, str.BeginReading(), str.Length())) {
+        expected.AppendElement(str.Length());
+      }
+    }
+
+    Completion complete;
+    complete.Assign(nsDependentCSubstring(buf, 32));
+    bool has, confirmed;
+    uint32_t matchLength = 0;
+    cache->Has(complete, &has, &matchLength, &confirmed);
+
+    ASSERT_TRUE(expected.IsEmpty() ? !matchLength
+                                   : expected.Contains(matchLength));
+  }
+}
+
+static already_AddRefed<LookupCacheV4> SetupLookupCache(
+    const nsACString& aName) {
+  nsCOMPtr<nsIFile> rootDir;
+  NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(rootDir));
+
+  nsAutoCString provider("test");
+  RefPtr<LookupCacheV4> lookup = new LookupCacheV4(aName, provider, rootDir);
+  lookup->Init();
+
+  return lookup.forget();
+}
+
+class UrlClassifierPrefixSetTest : public ::testing::TestWithParam<uint32_t> {
+ protected:
+  void SetUp() override {
+    // max_array_size to 0 means we are testing delta algorithm here.
+    static const char prefKey[] =
+        "browser.safebrowsing.prefixset.max_array_size";
+    mozilla::Preferences::SetUint(prefKey, GetParam());
+
+    mCache = SetupLookupCache("test"_ns);
+  }
+
+  void TearDown() override {
+    mCache = nullptr;
+    mArray.Clear();
+    mMap.Clear();
+  }
+
+  nsresult SetupPrefixes(_PrefixArray&& aArray) {
+    mArray = std::move(aArray);
+    PrefixArrayToPrefixStringMap(mArray, mMap);
+    return mCache->Build(mMap);
+  }
+
+  void SetupPrefixesAndVerify(_PrefixArray& aArray) {
+    mArray = aArray.Clone();
+    PrefixArrayToPrefixStringMap(mArray, mMap);
+
+    ASSERT_NS_SUCCEEDED(mCache->Build(mMap));
+    Verify();
+  }
+
+  void SetupPrefixesAndVerify(_PrefixArray&& aArray) {
+    nsresult rv = SetupPrefixes(std::move(aArray));
+    ASSERT_NS_SUCCEEDED(rv);
+    Verify();
+  }
+
+  void SetupRandomPrefixesAndVerify(uint32_t N, uint32_t MIN, uint32_t MAX) {
+    srand(time(nullptr));
+    RandomPrefixes(N, MIN, MAX, mArray);
+    PrefixArrayToPrefixStringMap(mArray, mMap);
+
+    ASSERT_NS_SUCCEEDED(mCache->Build(mMap));
+    Verify();
+  }
+
+  void Verify() {
+    DoExpectedLookup(mCache, mArray);
+    DoRandomLookup(mCache, 1000, mArray);
+    CheckContent(mCache, mArray);
+  }
+
+  RefPtr<LookupCacheV4> mCache;
+  _PrefixArray mArray;
+  PrefixStringMap mMap;
+};
+
+// Test setting prefix set with only 4-bytes prefixes
+TEST_P(UrlClassifierPrefixSetTest, FixedLengthSet) {
+  SetupPrefixesAndVerify({
+      _Prefix("alph"),
+      _Prefix("brav"),
+      _Prefix("char"),
+      _Prefix("delt"),
+      _Prefix("echo"),
+      _Prefix("foxt"),
+  });
+}
+
+TEST_P(UrlClassifierPrefixSetTest, FixedLengthRandomSet) {
+  SetupRandomPrefixesAndVerify(1500, 4, 4);
+}
+
+TEST_P(UrlClassifierPrefixSetTest, FixedLengthRandomLargeSet) {
+  SetupRandomPrefixesAndVerify(15000, 4, 4);
+}
+
+TEST_P(UrlClassifierPrefixSetTest, FixedLengthTinySet) {
+  SetupPrefixesAndVerify({
+      _Prefix("tiny"),
+  });
+}
+
+// Test setting prefix set with only 5~32 bytes prefixes
+TEST_P(UrlClassifierPrefixSetTest, VariableLengthSet) {
+  SetupPrefixesAndVerify(
+      {_Prefix("bravo"), _Prefix("charlie"), _Prefix("delta"),
+       _Prefix("EchoEchoEchoEchoEcho"), _Prefix("foxtrot"),
+       _Prefix("GolfGolfGolfGolfGolfGolfGolfGolf"), _Prefix("hotel"),
+       _Prefix("november"), _Prefix("oscar"), _Prefix("quebec"),
+       _Prefix("romeo"), _Prefix("sierrasierrasierrasierrasierra"),
+       _Prefix("Tango"), _Prefix("whiskey"), _Prefix("yankee"),
+       _Prefix("ZuluZuluZuluZulu")});
+}
+
+TEST_P(UrlClassifierPrefixSetTest, VariableLengthRandomSet) {
+  SetupRandomPrefixesAndVerify(1500, 5, 32);
+}
+
+// Test setting prefix set with both 4-bytes prefixes and 5~32 bytes prefixes
+TEST_P(UrlClassifierPrefixSetTest, MixedPrefixSet) {
+  SetupPrefixesAndVerify(
+      {_Prefix("enus"), _Prefix("apollo"), _Prefix("mars"),
+       _Prefix("Hecatonchires cyclopes"), _Prefix("vesta"), _Prefix("neptunus"),
+       _Prefix("jupiter"), _Prefix("diana"), _Prefix("minerva"),
+       _Prefix("ceres"), _Prefix("Aidos,Adephagia,Adikia,Aletheia"),
+       _Prefix("hecatonchires"), _Prefix("alcyoneus"), _Prefix("hades"),
+       _Prefix("vulcanus"), _Prefix("juno"), _Prefix("mercury"),
+       _Prefix("Stheno, Euryale and Medusa")});
+}
+
+TEST_P(UrlClassifierPrefixSetTest, MixedRandomPrefixSet) {
+  SetupRandomPrefixesAndVerify(1500, 4, 32);
+}
+
+// Test resetting prefix set
+TEST_P(UrlClassifierPrefixSetTest, ResetPrefix) {
+  // Base prefix set
+  _PrefixArray oldArray = {
+      _Prefix("Iceland"),   _Prefix("Peru"),    _Prefix("Mexico"),
+      _Prefix("Australia"), _Prefix("Japan"),   _Prefix("Egypt"),
+      _Prefix("America"),   _Prefix("Finland"), _Prefix("Germany"),
+      _Prefix("Italy"),     _Prefix("France"),  _Prefix("Taiwan"),
+  };
+  SetupPrefixesAndVerify(oldArray);
+
+  // New prefix set
+  _PrefixArray newArray = {
+      _Prefix("Pikachu"),    _Prefix("Bulbasaur"), _Prefix("Charmander"),
+      _Prefix("Blastoise"),  _Prefix("Pidgey"),    _Prefix("Mewtwo"),
+      _Prefix("Jigglypuff"), _Prefix("Persian"),   _Prefix("Tentacool"),
+      _Prefix("Onix"),       _Prefix("Eevee"),     _Prefix("Jynx"),
+  };
+  SetupPrefixesAndVerify(newArray);
+
+  // Should not match any of the first prefix set
+  uint32_t matchLength = 0;
+  for (uint32_t i = 0; i < oldArray.Length(); i++) {
+    Completion complete;
+    complete.Assign(CreateFullHash(oldArray[i]));
+
+    // Find match for prefix-generated full hash
+    bool has, confirmed;
+    mCache->Has(complete, &has, &matchLength, &confirmed);
+
+    ASSERT_TRUE(matchLength == 0);
+  }
+}
+
+// Test only set one 4-bytes prefix and one full-length prefix
+TEST_P(UrlClassifierPrefixSetTest, TinyPrefixSet) {
+  SetupPrefixesAndVerify({
+      _Prefix("AAAA"),
+      _Prefix("11112222333344445555666677778888"),
+  });
+}
+
+// Test empty prefix set and IsEmpty function
+TEST_P(UrlClassifierPrefixSetTest, EmptyFixedPrefixSet) {
+  ASSERT_TRUE(mCache->IsEmpty());
+
+  SetupPrefixesAndVerify({});
+
+  // Insert an 4-bytes prefix, then IsEmpty should return false
+  SetupPrefixesAndVerify({_Prefix("test")});
+
+  ASSERT_TRUE(!mCache->IsEmpty());
+}
+
+TEST_P(UrlClassifierPrefixSetTest, EmptyVariableLengthPrefixSet) {
+  ASSERT_TRUE(mCache->IsEmpty());
+
+  SetupPrefixesAndVerify({});
+
+  // Insert an 5~32 bytes prefix, then IsEmpty should return false
+  SetupPrefixesAndVerify({_Prefix("test variable length")});
+
+  ASSERT_TRUE(!mCache->IsEmpty());
+}
+
+// Test prefix size should only between 4~32 bytes
+TEST_P(UrlClassifierPrefixSetTest, MinMaxPrefixSet) {
+  // Test prefix set between 4-32 bytes, should success
+  SetupPrefixesAndVerify({_Prefix("1234"), _Prefix("ABCDEFGHIJKKMNOP"),
+                          _Prefix("1aaa2bbb3ccc4ddd5eee6fff7ggg8hhh")});
+
+  // Prefix size less than 4-bytes should fail
+  nsresult rv = SetupPrefixes({_Prefix("123")});
+  ASSERT_NS_FAILED(rv);
+
+  // Prefix size greater than 32-bytes should fail
+  rv = SetupPrefixes({_Prefix("1aaa2bbb3ccc4ddd5eee6fff7ggg8hhh9")});
+  ASSERT_NS_FAILED(rv);
+}
+
+// Test save then load prefix set with only 4-bytes prefixes
+TEST_P(UrlClassifierPrefixSetTest, LoadSaveFixedLengthPrefixSet) {
+  nsCOMPtr<nsIFile> file;
+  _PrefixArray array;
+  PrefixStringMap map;
+
+  // Save
+  {
+    RefPtr<LookupCacheV4> save = SetupLookupCache("test-save"_ns);
+
+    RandomPrefixes(10000, 4, 4, array);
+
+    PrefixArrayToPrefixStringMap(array, map);
+    save->Build(map);
+
+    DoExpectedLookup(save, array);
+    DoRandomLookup(save, 1000, array);
+    CheckContent(save, array);
+
+    NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
+    file->Append(u"test.vlpset"_ns);
+    save->StoreToFile(file);
+  }
+
+  // Load
+  {
+    RefPtr<LookupCacheV4> load = SetupLookupCache("test-load"_ns);
+    load->LoadFromFile(file);
+
+    DoExpectedLookup(load, array);
+    DoRandomLookup(load, 1000, array);
+    CheckContent(load, array);
+  }
+
+  file->Remove(false);
+}
+
+// Test save then load prefix set with only 5~32 bytes prefixes
+TEST_P(UrlClassifierPrefixSetTest, LoadSaveVariableLengthPrefixSet) {
+  nsCOMPtr<nsIFile> file;
+  _PrefixArray array;
+  PrefixStringMap map;
+
+  // Save
+  {
+    RefPtr<LookupCacheV4> save = SetupLookupCache("test-save"_ns);
+
+    RandomPrefixes(10000, 5, 32, array);
+
+    PrefixArrayToPrefixStringMap(array, map);
+    save->Build(map);
+
+    DoExpectedLookup(save, array);
+    DoRandomLookup(save, 1000, array);
+    CheckContent(save, array);
+
+    NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
+    file->Append(u"test.vlpset"_ns);
+    save->StoreToFile(file);
+  }
+
+  // Load
+  {
+    RefPtr<LookupCacheV4> load = SetupLookupCache("test-load"_ns);
+    load->LoadFromFile(file);
+
+    DoExpectedLookup(load, array);
+    DoRandomLookup(load, 1000, array);
+    CheckContent(load, array);
+  }
+
+  file->Remove(false);
+}
+
+// Test save then load prefix with both 4 bytes prefixes and 5~32 bytes prefixes
+TEST_P(UrlClassifierPrefixSetTest, LoadSavePrefixSet) {
+  nsCOMPtr<nsIFile> file;
+  _PrefixArray array;
+  PrefixStringMap map;
+
+  // Save
+  {
+    RefPtr<LookupCacheV4> save = SetupLookupCache("test-save"_ns);
+
+    // Try to simulate the real case that most prefixes are 4bytes
+    RandomPrefixes(20000, 4, 4, array);
+    RandomPrefixes(1000, 5, 32, array);
+
+    PrefixArrayToPrefixStringMap(array, map);
+    save->Build(map);
+
+    DoExpectedLookup(save, array);
+    DoRandomLookup(save, 1000, array);
+    CheckContent(save, array);
+
+    NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
+    file->Append(u"test.vlpset"_ns);
+    save->StoreToFile(file);
+  }
+
+  // Load
+  {
+    RefPtr<LookupCacheV4> load = SetupLookupCache("test-load"_ns);
+    load->LoadFromFile(file);
+
+    DoExpectedLookup(load, array);
+    DoRandomLookup(load, 1000, array);
+    CheckContent(load, array);
+  }
+
+  file->Remove(false);
+}
+
+// This is for fixed-length prefixset
+TEST_P(UrlClassifierPrefixSetTest, LoadSaveNoDelta) {
+  nsCOMPtr<nsIFile> file;
+  _PrefixArray array;
+  PrefixStringMap map;
+
+  for (uint32_t i = 0; i < 100; i++) {
+    // construct a tree without deltas by making the distance
+    // between entries larger than 16 bits
+    uint32_t v = ((1 << 16) + 1) * i;
+    nsCString* ele = array.AppendElement();
+    ele->AppendASCII(reinterpret_cast<const char*>(&v), 4);
+  }
+
+  // Save
+  {
+    RefPtr<LookupCacheV4> save = SetupLookupCache("test-save"_ns);
+
+    PrefixArrayToPrefixStringMap(array, map);
+    save->Build(map);
+
+    DoExpectedLookup(save, array);
+    DoRandomLookup(save, 1000, array);
+    CheckContent(save, array);
+
+    NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
+    file->Append(u"test.vlpset"_ns);
+    save->StoreToFile(file);
+  }
+
+  // Load
+  {
+    RefPtr<LookupCacheV4> load = SetupLookupCache("test-load"_ns);
+    load->LoadFromFile(file);
+
+    DoExpectedLookup(load, array);
+    DoRandomLookup(load, 1000, array);
+    CheckContent(load, array);
+  }
+
+  file->Remove(false);
+}
+
+// To run the same test for different configurations of
+// "browser_safebrowsing_prefixset_max_array_size"
+INSTANTIATE_TEST_SUITE_P(UrlClassifierPrefixSetTest, UrlClassifierPrefixSetTest,
+                         ::testing::Values(0, UINT32_MAX));
diff --git a/toolkit/components/url-classifier/tests/gtest/moz.build b/toolkit/components/url-classifier/tests/gtest/moz.build
new file mode 100644
index 0000000000..070012de77
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/gtest/moz.build
@@ -0,0 +1,40 @@
+# -*- Mode: python; indent-tabs-mode: nil; tab-width: 40 -*-
+# vim: set filetype=python:
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+LOCAL_INCLUDES += [
+    "../..",
+]
+
+DEFINES["GOOGLE_PROTOBUF_NO_RTTI"] = True
+DEFINES["GOOGLE_PROTOBUF_NO_STATIC_INITIALIZER"] = True
+
+UNIFIED_SOURCES += [
+    "Common.cpp",
+    "TestCaching.cpp",
+    "TestChunkSet.cpp",
+    "TestClassifier.cpp",
+    "TestFailUpdate.cpp",
+    "TestFindFullHash.cpp",
+    "TestLookupCacheV4.cpp",
+    "TestPerProviderDirectory.cpp",
+    "TestPrefixSet.cpp",
+    "TestProtocolParser.cpp",
+    "TestRiceDeltaDecoder.cpp",
+    "TestSafebrowsingHash.cpp",
+    "TestSafeBrowsingProtobuf.cpp",
+    "TestTable.cpp",
+    "TestUrlClassifierTableUpdateV4.cpp",
+    "TestUrlClassifierUtils.cpp",
+    "TestURLsAndHashing.cpp",
+    "TestVariableLengthPrefixSet.cpp",
+]
+
+# Required to have the same MOZ_SAFEBROWSING_DUMP_FAILED_UPDATES
+# as non-testing code.
+if CONFIG["NIGHTLY_BUILD"] or CONFIG["MOZ_DEBUG"]:
+    DEFINES["MOZ_SAFEBROWSING_DUMP_FAILED_UPDATES"] = True
+
+FINAL_LIBRARY = "xul-gtest"