--- a/toolkit/components/url-classifier/Classifier.cpp
+++ b/toolkit/components/url-classifier/Classifier.cpp
@@ -16,16 +16,17 @@
 #include "nsPrintfCString.h"
 #include "nsThreadUtils.h"
 #include "mozilla/Telemetry.h"
 #include "mozilla/Logging.h"
 #include "mozilla/SyncRunnable.h"
 #include "mozilla/Base64.h"
 #include "mozilla/Unused.h"
 #include "mozilla/TypedEnumBits.h"
+#include "nsIUrlClassifierUtils.h"
 
 // MOZ_LOG=UrlClassifierDbService:5
 extern mozilla::LazyLogModule gUrlClassifierDbServiceLog;
 #define LOG(args) MOZ_LOG(gUrlClassifierDbServiceLog, mozilla::LogLevel::Debug, args)
 #define LOG_ENABLED() MOZ_LOG_TEST(gUrlClassifierDbServiceLog, mozilla::LogLevel::Debug)
 
 #define STORE_DIRECTORY      NS_LITERAL_CSTRING("safebrowsing")
 #define TO_DELETE_DIR_SUFFIX NS_LITERAL_CSTRING("-to_delete")
@@ -80,132 +81,45 @@ Classifier::SplitTables(const nsACString
     }
     begin = iter;
     if (begin != end) {
       begin++;
     }
   }
 }
 
-static nsresult
-DeriveProviderFromPref(const nsACString& aTableName, nsCString& aProviderName)
-{
-  // Check all preferences "browser.safebrowsing.provider.[provider].list"
-  // to see which one contains |aTableName|.
-
-  nsCOMPtr<nsIPrefService> prefs = do_GetService(NS_PREFSERVICE_CONTRACTID);
-  NS_ENSURE_TRUE(prefs, NS_ERROR_FAILURE);
-  nsCOMPtr<nsIPrefBranch> prefBranch;
-  nsresult rv = prefs->GetBranch("browser.safebrowsing.provider.",
-                                  getter_AddRefs(prefBranch));
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  // We've got a pref branch for "browser.safebrowsing.provider.".
-  // Enumerate all children prefs and parse providers.
-  uint32_t childCount;
-  char** childArray;
-  rv = prefBranch->GetChildList("", &childCount, &childArray);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  // Collect providers from childArray.
-  nsTHashtable<nsCStringHashKey> providers;
-  for (uint32_t i = 0; i < childCount; i++) {
-    nsCString child(childArray[i]);
-    auto dotPos = child.FindChar('.');
-    if (dotPos < 0) {
-      continue;
-    }
-
-    nsDependentCSubstring provider = Substring(child, 0, dotPos);
-
-    providers.PutEntry(provider);
-  }
-  NS_FREE_XPCOM_ALLOCATED_POINTER_ARRAY(childCount, childArray);
-
-  // Now we have all providers. Check which one owns |aTableName|.
-  // e.g. The owning lists of provider "google" is defined in
-  // "browser.safebrowsing.provider.google.lists".
-  for (auto itr = providers.Iter(); !itr.Done(); itr.Next()) {
-    auto entry = itr.Get();
-    nsCString provider(entry->GetKey());
-    nsPrintfCString owninListsPref("%s.lists", provider.get());
-
-    nsXPIDLCString owningLists;
-    nsresult rv = prefBranch->GetCharPref(owninListsPref.get(),
-                                          getter_Copies(owningLists));
-    if (NS_FAILED(rv)) {
-      continue;
-    }
-
-    // We've got the owning lists (represented as string) of |provider|.
-    // Parse the string and see if |aTableName| is included.
-    nsTArray<nsCString> tables;
-    Classifier::SplitTables(owningLists, tables);
-    if (tables.Contains(aTableName)) {
-      aProviderName = provider;
-      return NS_OK;
-    }
-  }
-
-  return NS_ERROR_FAILURE;
-}
-
-// Lookup the provider name by table name on non-main thread.
-// On main thread, just call DeriveProviderFromPref() instead
-// but DeriveProviderFromPref is supposed to used internally.
-static nsCString
-GetProviderByTableName(const nsACString& aTableName)
-{
-  MOZ_ASSERT(!NS_IsMainThread(), "GetProviderByTableName MUST be called "
-                                 "on non-main thread.");
-  nsCString providerName;
-
-  nsCOMPtr<nsIRunnable> r = NS_NewRunnableFunction([&aTableName,
-                                                    &providerName] () -> void {
-    nsresult rv = DeriveProviderFromPref(aTableName, providerName);
-    if (NS_FAILED(rv)) {
-      LOG(("No provider found for %s", nsCString(aTableName).get()));
-    }
-  });
-
-  nsCOMPtr<nsIThread> mainThread = do_GetMainThread();
-  SyncRunnable::DispatchToThread(mainThread, r);
-
-  return providerName;
-}
-
 nsresult
 Classifier::GetPrivateStoreDirectory(nsIFile* aRootStoreDirectory,
                                      const nsACString& aTableName,
+                                     const nsACString& aProvider,
                                      nsIFile** aPrivateStoreDirectory)
 {
   NS_ENSURE_ARG_POINTER(aPrivateStoreDirectory);
 
   if (!StringEndsWith(aTableName, NS_LITERAL_CSTRING("-proto"))) {
     // Only V4 table names (ends with '-proto') would be stored
     // to per-provider sub-directory.
     nsCOMPtr<nsIFile>(aRootStoreDirectory).forget(aPrivateStoreDirectory);
     return NS_OK;
   }
 
-  nsCString providerName = GetProviderByTableName(aTableName);
-  if (providerName.IsEmpty()) {
+  if (aProvider.IsEmpty()) {
     // When failing to get provider, just store in the root folder.
     nsCOMPtr<nsIFile>(aRootStoreDirectory).forget(aPrivateStoreDirectory);
     return NS_OK;
   }
 
   nsCOMPtr<nsIFile> providerDirectory;
 
   // Clone first since we are gonna create a new directory.
   nsresult rv = aRootStoreDirectory->Clone(getter_AddRefs(providerDirectory));
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Append the provider name to the root store directory.
-  rv = providerDirectory->AppendNative(providerName);
+  rv = providerDirectory->AppendNative(aProvider);
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Ensure existence of the provider directory.
   bool dirExists;
   rv = providerDirectory->Exists(&dirExists);
   NS_ENSURE_SUCCESS(rv, rv);
 
   if (!dirExists) {
@@ -433,17 +347,17 @@ Classifier::AbortUpdateAndReset(const ns
 
 void
 Classifier::TableRequest(nsACString& aResult)
 {
   // Generating v2 table info.
   nsTArray<nsCString> tables;
   ActiveTables(tables);
   for (uint32_t i = 0; i < tables.Length(); i++) {
-    HashStore store(tables[i], mRootStoreDirectory);
+    HashStore store(tables[i], GetProvider(tables[i]), mRootStoreDirectory);
 
     nsresult rv = store.Open();
     if (NS_FAILED(rv))
       continue;
 
     aResult.Append(store.TableName());
     aResult.Append(';');
 
@@ -708,17 +622,17 @@ Classifier::RegenActiveTables()
 {
   mActiveTablesCache.Clear();
 
   nsTArray<nsCString> foundTables;
   ScanStoreDir(foundTables);
 
   for (uint32_t i = 0; i < foundTables.Length(); i++) {
     nsCString table(foundTables[i]);
-    HashStore store(table, mRootStoreDirectory);
+    HashStore store(table, GetProvider(table), mRootStoreDirectory);
 
     nsresult rv = store.Open();
     if (NS_FAILED(rv))
       continue;
 
     LookupCache *lookupCache = GetLookupCache(store.TableName());
     if (!lookupCache) {
       continue;
@@ -975,26 +889,38 @@ Classifier::CheckValidUpdate(nsTArray<Ta
   if (!validupdates) {
     // This can happen if the update was only valid for one table.
     return false;
   }
 
   return true;
 }
 
+nsCString
+Classifier::GetProvider(const nsACString& aTableName)
+{
+  nsCOMPtr<nsIUrlClassifierUtils> urlUtil =
+    do_GetService(NS_URLCLASSIFIERUTILS_CONTRACTID);
+
+  nsCString provider;
+  nsresult rv = urlUtil->GetProvider(aTableName, provider);
+
+  return NS_SUCCEEDED(rv) ? provider : EmptyCString();
+}
+
 /*
  * This will consume+delete updates from the passed nsTArray.
 */
 nsresult
 Classifier::UpdateHashStore(nsTArray<TableUpdate*>* aUpdates,
                             const nsACString& aTable)
 {
   LOG(("Classifier::UpdateHashStore(%s)", PromiseFlatCString(aTable).get()));
 
-  HashStore store(aTable, mRootStoreDirectory);
+  HashStore store(aTable, GetProvider(aTable), mRootStoreDirectory);
 
   if (!CheckValidUpdate(aUpdates, store.TableName())) {
     return NS_OK;
   }
 
   nsresult rv = store.Open();
   NS_ENSURE_SUCCESS(rv, rv);
   rv = store.BeginUpdate();
@@ -1203,20 +1129,21 @@ Classifier::GetLookupCache(const nsACStr
       return mLookupCaches[i];
     }
   }
 
   // TODO : Bug 1302600, It would be better if we have a more general non-main
   //        thread method to convert table name to protocol version. Currently
   //        we can only know this by checking if the table name ends with '-proto'.
   UniquePtr<LookupCache> cache;
+  nsCString provider = GetProvider(aTable);
   if (StringEndsWith(aTable, NS_LITERAL_CSTRING("-proto"))) {
-    cache = MakeUnique<LookupCacheV4>(aTable, mRootStoreDirectory);
+    cache = MakeUnique<LookupCacheV4>(aTable, provider, mRootStoreDirectory);
   } else {
-    cache = MakeUnique<LookupCacheV2>(aTable, mRootStoreDirectory);
+    cache = MakeUnique<LookupCacheV2>(aTable, provider, mRootStoreDirectory);
   }
 
   nsresult rv = cache->Init();
   if (NS_FAILED(rv)) {
     return nullptr;
   }
   rv = cache->Open();
   if (NS_FAILED(rv)) {

--- a/toolkit/components/url-classifier/Classifier.h
+++ b/toolkit/components/url-classifier/Classifier.h
@@ -19,16 +19,19 @@
 namespace mozilla {
 namespace safebrowsing {
 
 /**
  * Maintains the stores and LookupCaches for the url classifier.
  */
 class Classifier {
 public:
+  typedef nsClassHashtable<nsCStringHashKey, nsCString> ProviderDictType;
+
+public:
   Classifier();
   ~Classifier();
 
   nsresult Open(nsIFile& aCacheDirectory);
   void Close();
   void Reset();
 
   /**
@@ -98,16 +101,17 @@ public:
   // For V4 tables (suffixed by '-proto'), the private directory would
   // be [root directory path]/[provider]. The provider of V4 tables is
   // 'google4'.
   //
   // Note that if the table name is not owned by any provider, just use
   // the root directory.
   static nsresult GetPrivateStoreDirectory(nsIFile* aRootStoreDirectory,
                                            const nsACString& aTableName,
+                                           const nsACString& aProvider,
                                            nsIFile** aPrivateStoreDirectory);
 
 private:
   void DropStores();
   void DeleteTables(nsIFile* aDirectory, const nsTArray<nsCString>& aTables);
   void AbortUpdateAndReset(const nsCString& aTable);
 
   nsresult CreateStoreDirectory();
@@ -135,16 +139,18 @@ private:
 
   LookupCache *GetLookupCache(const nsACString& aTable);
 
   bool CheckValidUpdate(nsTArray<TableUpdate*>* aUpdates,
                         const nsACString& aTable);
 
   nsresult LoadMetadata(nsIFile* aDirectory, nsACString& aResult);
 
+  nsCString GetProvider(const nsACString& aTableName);
+
   // Root dir of the Local profile.
   nsCOMPtr<nsIFile> mCacheDirectory;
   // Main directory where to store the databases.
   nsCOMPtr<nsIFile> mRootStoreDirectory;
   // Used for atomically updating the other dirs.
   nsCOMPtr<nsIFile> mBackupDirectory;
   nsCOMPtr<nsIFile> mToDeleteDirectory;
   nsCOMPtr<nsICryptoHash> mCryptoHash;

--- a/toolkit/components/url-classifier/HashStore.cpp
+++ b/toolkit/components/url-classifier/HashStore.cpp
@@ -201,23 +201,26 @@ TableUpdateV4::NewRemovalIndices(const u
 }
 
 void
 TableUpdateV4::NewChecksum(const std::string& aChecksum)
 {
   mChecksum.Assign(aChecksum.data(), aChecksum.size());
 }
 
-HashStore::HashStore(const nsACString& aTableName, nsIFile* aRootStoreDir)
+HashStore::HashStore(const nsACString& aTableName,
+                     const nsACString& aProvider,
+                     nsIFile* aRootStoreDir)
   : mTableName(aTableName)
   , mInUpdate(false)
   , mFileSize(0)
 {
   nsresult rv = Classifier::GetPrivateStoreDirectory(aRootStoreDir,
                                                      aTableName,
+                                                     aProvider,
                                                      getter_AddRefs(mStoreDirectory));
   if (NS_FAILED(rv)) {
     LOG(("Failed to get private store directory for %s", mTableName.get()));
     mStoreDirectory = aRootStoreDir;
   }
 }
 
 HashStore::~HashStore()

--- a/toolkit/components/url-classifier/HashStore.h
+++ b/toolkit/components/url-classifier/HashStore.h
@@ -185,17 +185,19 @@ private:
   RemovalIndiceArray mRemovalIndiceArray;
   nsCString mClientState;
   nsCString mChecksum;
 };
 
 // There is one hash store per table.
 class HashStore {
 public:
-  HashStore(const nsACString& aTableName, nsIFile* aRootStoreFile);
+  HashStore(const nsACString& aTableName,
+            const nsACString& aProvider,
+            nsIFile* aRootStoreFile);
   ~HashStore();
 
   const nsCString& TableName() const { return mTableName; }
 
   nsresult Open();
   // Add Prefixes are stored partly in the PrefixSet (contains the
   // Prefix data organized for fast lookup/low RAM usage) and partly in the
   // HashStore (Add Chunk numbers - only used for updates, slow retrieval).

--- a/toolkit/components/url-classifier/LookupCache.cpp
+++ b/toolkit/components/url-classifier/LookupCache.cpp
@@ -37,19 +37,22 @@ extern mozilla::LazyLogModule gUrlClassi
 #define LOG(args) MOZ_LOG(gUrlClassifierDbServiceLog, mozilla::LogLevel::Debug, args)
 #define LOG_ENABLED() MOZ_LOG_TEST(gUrlClassifierDbServiceLog, mozilla::LogLevel::Debug)
 
 namespace mozilla {
 namespace safebrowsing {
 
 const int LookupCacheV2::VER = 2;
 
-LookupCache::LookupCache(const nsACString& aTableName, nsIFile* aRootStoreDir)
+LookupCache::LookupCache(const nsACString& aTableName,
+                         const nsACString& aProvider,
+                         nsIFile* aRootStoreDir)
   : mPrimed(false)
   , mTableName(aTableName)
+  , mProvider(aProvider)
   , mRootStoreDirectory(aRootStoreDir)
 {
   UpdateRootDirHandle(mRootStoreDirectory);
 }
 
 nsresult
 LookupCache::Open()
 {
@@ -67,16 +70,17 @@ LookupCache::UpdateRootDirHandle(nsIFile
 
   if (aNewRootStoreDirectory != mRootStoreDirectory) {
     rv = aNewRootStoreDirectory->Clone(getter_AddRefs(mRootStoreDirectory));
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   rv = Classifier::GetPrivateStoreDirectory(mRootStoreDirectory,
                                             mTableName,
+                                            mProvider,
                                             getter_AddRefs(mStoreDirectory));
 
   if (NS_FAILED(rv)) {
     LOG(("Failed to get private store directory for %s", mTableName.get()));
     mStoreDirectory = mRootStoreDirectory;
   }
 
   if (LOG_ENABLED()) {
@@ -473,17 +477,17 @@ LookupCacheV2::GetPrefixes(FallibleTArra
     return NS_OK;
   }
   return mPrefixSet->GetPrefixesNative(aAddPrefixes);
 }
 
 nsresult
 LookupCacheV2::ReadCompletions()
 {
-  HashStore store(mTableName, mRootStoreDirectory);
+  HashStore store(mTableName, mProvider, mRootStoreDirectory);
 
   nsresult rv = store.Open();
   NS_ENSURE_SUCCESS(rv, rv);
 
   mUpdateCompletions.Clear();
 
   const AddCompleteArray& addComplete = store.AddCompletes();
   for (uint32_t i = 0; i < addComplete.Length(); i++) {

--- a/toolkit/components/url-classifier/LookupCache.h
+++ b/toolkit/components/url-classifier/LookupCache.h
@@ -91,17 +91,19 @@ public:
   // Similar to GetKey(), but if the domain contains three or more components,
   // two keys will be returned:
   //  hostname.com/foo/bar -> [hostname.com]
   //  mail.hostname.com/foo/bar -> [hostname.com, mail.hostname.com]
   //  www.mail.hostname.com/foo/bar -> [hostname.com, mail.hostname.com]
   static nsresult GetHostKeys(const nsACString& aSpec,
                               nsTArray<nsCString>* aHostKeys);
 
-  LookupCache(const nsACString& aTableName, nsIFile* aStoreFile);
+  LookupCache(const nsACString& aTableName,
+              const nsACString& aProvider,
+              nsIFile* aStoreFile);
   virtual ~LookupCache() {}
 
   const nsCString &TableName() const { return mTableName; }
 
   // The directory handle where we operate will
   // be moved away when a backup is made.
   nsresult UpdateRootDirHandle(nsIFile* aRootStoreDirectory);
 
@@ -141,31 +143,34 @@ private:
   virtual nsresult LoadFromFile(nsIFile* aFile) = 0;
   virtual size_t SizeOfPrefixSet() = 0;
 
   virtual int Ver() const = 0;
 
 protected:
   bool mPrimed;
   nsCString mTableName;
+  nsCString mProvider;
   nsCOMPtr<nsIFile> mRootStoreDirectory;
   nsCOMPtr<nsIFile> mStoreDirectory;
 
   // Full length hashes obtained in gethash request
   CompletionArray mGetHashCache;
 
   // For gtest to inspect private members.
   friend class PerProviderDirectoryTestUtils;
 };
 
 class LookupCacheV2 final : public LookupCache
 {
 public:
-  explicit LookupCacheV2(const nsACString& aTableName, nsIFile* aStoreFile)
-    : LookupCache(aTableName, aStoreFile) {}
+  explicit LookupCacheV2(const nsACString& aTableName,
+                         const nsACString& aProvider,
+                         nsIFile* aStoreFile)
+    : LookupCache(aTableName, aProvider, aStoreFile) {}
   ~LookupCacheV2() {}
 
   virtual nsresult Init() override;
   virtual nsresult Open() override;
   virtual void ClearAll() override;
   virtual nsresult Has(const Completion& aCompletion,
                        bool* aHas, bool* aComplete) override;
 

--- a/toolkit/components/url-classifier/LookupCacheV4.h
+++ b/toolkit/components/url-classifier/LookupCacheV4.h
@@ -12,18 +12,20 @@ namespace mozilla {
 namespace safebrowsing {
 
 // Forward declaration.
 class TableUpdateV4;
 
 class LookupCacheV4 final : public LookupCache
 {
 public:
-  explicit LookupCacheV4(const nsACString& aTableName, nsIFile* aStoreFile)
-    : LookupCache(aTableName, aStoreFile) {}
+  explicit LookupCacheV4(const nsACString& aTableName,
+                         const nsACString& aProvider,
+                         nsIFile* aStoreFile)
+    : LookupCache(aTableName, aProvider, aStoreFile) {}
   ~LookupCacheV4() {}
 
   virtual nsresult Init() override;
   virtual nsresult Has(const Completion& aCompletion,
                        bool* aHas, bool* aComplete) override;
 
   nsresult Build(PrefixStringMap& aPrefixMap);
 

--- a/toolkit/components/url-classifier/nsIUrlClassifierUtils.idl
+++ b/toolkit/components/url-classifier/nsIUrlClassifierUtils.idl
@@ -18,16 +18,25 @@ interface nsIUrlClassifierUtils : nsISup
    *
    * @param uri URI to get the lookup key for.
    *
    * @returns String containing the canonicalized URI.
    */
   ACString getKeyForURI(in nsIURI uri);
 
   /**
+   * Get the provider by table name.
+   *
+   * @param tableName The table name that we want to lookup
+   *
+   * @returns the provider name that the given table belongs.
+   */
+  ACString getProvider(in ACString tableName);
+
+  /**
    * Get the protocol version for the given provider.
    *
    * @param provider String the provider name. e.g. "google"
    *
    * @returns String to indicate the protocol version. e.g. "2.2"
    */
   ACString getProtocolVersion(in ACString provider);
 

--- a/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
+++ b/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
@@ -1263,20 +1263,30 @@ nsUrlClassifierDBService::Init()
   mCheckBlockedURIs = Preferences::GetBool(CHECK_BLOCKED_PREF,
     CHECK_BLOCKED_DEFAULT);
   uint32_t gethashNoise = Preferences::GetUint(GETHASH_NOISE_PREF,
     GETHASH_NOISE_DEFAULT);
   gFreshnessGuarantee = Preferences::GetInt(CONFIRM_AGE_PREF,
     CONFIRM_AGE_DEFAULT_SEC);
   ReadTablesFromPrefs();
 
-  // Force PSM loading on main thread
   nsresult rv;
-  nsCOMPtr<nsICryptoHash> dummy = do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID, &rv);
-  NS_ENSURE_SUCCESS(rv, rv);
+
+  {
+    // Force PSM loading on main thread
+    nsCOMPtr<nsICryptoHash> dummy = do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID, &rv);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  {
+    // Force nsIUrlClassifierUtils loading on main thread.
+    nsCOMPtr<nsIUrlClassifierUtils> dummy =
+      do_GetService(NS_URLCLASSIFIERUTILS_CONTRACTID, &rv);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
 
   // Directory providers must also be accessed on the main thread.
   nsCOMPtr<nsIFile> cacheDir;
   rv = NS_GetSpecialDirectory(NS_APP_USER_PROFILE_LOCAL_50_DIR,
                               getter_AddRefs(cacheDir));
   if (NS_FAILED(rv)) {
     rv = NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR,
                                 getter_AddRefs(cacheDir));

--- a/toolkit/components/url-classifier/nsUrlClassifierUtils.cpp
+++ b/toolkit/components/url-classifier/nsUrlClassifierUtils.cpp
@@ -7,16 +7,17 @@
 #include "nsIURI.h"
 #include "nsUrlClassifierUtils.h"
 #include "nsTArray.h"
 #include "nsReadableUtils.h"
 #include "plbase64.h"
 #include "nsPrintfCString.h"
 #include "safebrowsing.pb.h"
 #include "mozilla/Sprintf.h"
+#include "mozilla/Mutex.h"
 
 #define DEFAULT_PROTOCOL_VERSION "2.2"
 
 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')));
 }
@@ -140,32 +141,55 @@ CreateClientInfo()
   c->set_client_id(clientId.get());
 
   return c;
 }
 
 } // end of namespace safebrowsing.
 } // end of namespace mozilla.
 
-nsUrlClassifierUtils::nsUrlClassifierUtils() : mEscapeCharmap(nullptr)
+nsUrlClassifierUtils::nsUrlClassifierUtils()
+  : mEscapeCharmap(nullptr)
+  , mProviderDictLock("nsUrlClassifierUtils.mProviderDictLock")
 {
 }
 
 nsresult
 nsUrlClassifierUtils::Init()
 {
   // Everything but alpha numerics, - and .
   mEscapeCharmap = new Charmap(0xffffffff, 0xfc009fff, 0xf8000001, 0xf8000001,
                                0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff);
   if (!mEscapeCharmap)
     return NS_ERROR_OUT_OF_MEMORY;
+
+  // nsIUrlClassifierUtils is a thread-safe service so it's
+  // allowed to use on non-main threads. However, building
+  // the provider dictionary must be on the main thread.
+  // We forcefully load nsUrlClassifierUtils in
+  // nsUrlClassifierDBService::Init() to ensure we must
+  // now be on the main thread.
+  nsresult rv = ReadProvidersFromPrefs(mProviderDict);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  // Add an observer for shutdown
+  nsCOMPtr<nsIObserverService> observerService =
+      mozilla::services::GetObserverService();
+  if (!observerService)
+    return NS_ERROR_FAILURE;
+
+  observerService->AddObserver(this, "xpcom-shutdown-threads", false);
+  Preferences::AddStrongObserver(this, "browser.safebrowsing");
+
   return NS_OK;
 }
 
-NS_IMPL_ISUPPORTS(nsUrlClassifierUtils, nsIUrlClassifierUtils)
+NS_IMPL_ISUPPORTS(nsUrlClassifierUtils,
+                  nsIUrlClassifierUtils,
+                  nsIObserver)
 
 /////////////////////////////////////////////////////////////////////////////
 // nsIUrlClassifierUtils
 
 NS_IMETHODIMP
 nsUrlClassifierUtils::GetKeyForURI(nsIURI * uri, nsACString & _retval)
 {
   nsCOMPtr<nsIURI> innerURI = NS_GetInnermostURI(uri);
@@ -245,16 +269,30 @@ nsUrlClassifierUtils::ConvertListNameToT
       return NS_OK;
     }
   }
 
   return NS_ERROR_FAILURE;
 }
 
 NS_IMETHODIMP
+nsUrlClassifierUtils::GetProvider(const nsACString& aTableName,
+                                  nsACString& aProvider)
+{
+  MutexAutoLock lock(mProviderDictLock);
+  nsCString* provider = nullptr;
+  if (mProviderDict.Get(aTableName, &provider)) {
+    aProvider = provider ? *provider : EmptyCString();
+  } else {
+    aProvider = EmptyCString();
+  }
+  return NS_OK;
+}
+
+NS_IMETHODIMP
 nsUrlClassifierUtils::GetProtocolVersion(const nsACString& aProvider,
                                          nsACString& aVersion)
 {
   nsCOMPtr<nsIPrefBranch> prefBranch = do_GetService(NS_PREFSERVICE_CONTRACTID);
   if (prefBranch) {
       nsPrintfCString prefName("browser.safebrowsing.provider.%s.pver",
                                nsCString(aProvider).get());
       nsXPIDLCString version;
@@ -301,20 +339,102 @@ nsUrlClassifierUtils::MakeUpdateRequestV
                                 out);
   NS_ENSURE_SUCCESS(rv, rv);
 
   aRequest = out;
 
   return NS_OK;
 }
 
+//////////////////////////////////////////////////////////
+// nsIObserver
+
+NS_IMETHODIMP
+nsUrlClassifierUtils::Observe(nsISupports *aSubject, const char *aTopic,
+                              const char16_t *aData)
+{
+  if (0 == strcmp(aTopic, NS_PREFBRANCH_PREFCHANGE_TOPIC_ID)) {
+    MutexAutoLock lock(mProviderDictLock);
+    return ReadProvidersFromPrefs(mProviderDict);
+  }
+
+  if (0 == strcmp(aTopic, "xpcom-shutdown-threads")) {
+    nsCOMPtr<nsIPrefBranch> prefs = do_GetService(NS_PREFSERVICE_CONTRACTID);
+    NS_ENSURE_TRUE(prefs, NS_ERROR_FAILURE);
+    return prefs->RemoveObserver("browser.safebrowsing", this);
+  }
+
+  return NS_ERROR_UNEXPECTED;
+}
+
 /////////////////////////////////////////////////////////////////////////////
 // non-interface methods
 
 nsresult
+nsUrlClassifierUtils::ReadProvidersFromPrefs(ProviderDictType& aDict)
+{
+  MOZ_ASSERT(NS_IsMainThread(), "ReadProvidersFromPrefs must be on main thread");
+
+  nsCOMPtr<nsIPrefService> prefs = do_GetService(NS_PREFSERVICE_CONTRACTID);
+  NS_ENSURE_TRUE(prefs, NS_ERROR_FAILURE);
+  nsCOMPtr<nsIPrefBranch> prefBranch;
+  nsresult rv = prefs->GetBranch("browser.safebrowsing.provider.",
+                                  getter_AddRefs(prefBranch));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  // We've got a pref branch for "browser.safebrowsing.provider.".
+  // Enumerate all children prefs and parse providers.
+  uint32_t childCount;
+  char** childArray;
+  rv = prefBranch->GetChildList("", &childCount, &childArray);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  // Collect providers from childArray.
+  nsTHashtable<nsCStringHashKey> providers;
+  for (uint32_t i = 0; i < childCount; i++) {
+    nsCString child(childArray[i]);
+    auto dotPos = child.FindChar('.');
+    if (dotPos < 0) {
+      continue;
+    }
+
+    nsDependentCSubstring provider = Substring(child, 0, dotPos);
+
+    providers.PutEntry(provider);
+  }
+  NS_FREE_XPCOM_ALLOCATED_POINTER_ARRAY(childCount, childArray);
+
+  // Now we have all providers. Check which one owns |aTableName|.
+  // e.g. The owning lists of provider "google" is defined in
+  // "browser.safebrowsing.provider.google.lists".
+  for (auto itr = providers.Iter(); !itr.Done(); itr.Next()) {
+    auto entry = itr.Get();
+    nsCString provider(entry->GetKey());
+    nsPrintfCString owninListsPref("%s.lists", provider.get());
+
+    nsXPIDLCString owningLists;
+    nsresult rv = prefBranch->GetCharPref(owninListsPref.get(),
+                                          getter_Copies(owningLists));
+    if (NS_FAILED(rv)) {
+      continue;
+    }
+
+    // We've got the owning lists (represented as string) of |provider|.
+    // Build the dictionary for the owning list and the current provider.
+    nsTArray<nsCString> tables;
+    Classifier::SplitTables(owningLists, tables);
+    for (auto tableName : tables) {
+      aDict.Put(tableName, new nsCString(provider));
+    }
+  }
+
+  return NS_OK;
+}
+
+nsresult
 nsUrlClassifierUtils::CanonicalizeHostname(const nsACString & hostname,
                                            nsACString & _retval)
 {
   nsAutoCString unescaped;
   if (!NS_UnescapeURL(PromiseFlatCString(hostname).get(),
                       PromiseFlatCString(hostname).Length(),
                       0, unescaped)) {
     unescaped.Assign(hostname);

--- a/toolkit/components/url-classifier/nsUrlClassifierUtils.h
+++ b/toolkit/components/url-classifier/nsUrlClassifierUtils.h
@@ -2,19 +2,25 @@
  * 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 nsUrlClassifierUtils_h_
 #define nsUrlClassifierUtils_h_
 
 #include "nsAutoPtr.h"
 #include "nsIUrlClassifierUtils.h"
+#include "nsClassHashtable.h"
+#include "nsIObserver.h"
 
-class nsUrlClassifierUtils final : public nsIUrlClassifierUtils
+class nsUrlClassifierUtils final : public nsIUrlClassifierUtils,
+                                   public nsIObserver
 {
+public:
+  typedef nsClassHashtable<nsCStringHashKey, nsCString> ProviderDictType;
+
 private:
   /**
    * A fast, bit-vector map for ascii characters.
    *
    * Internally stores 256 bits in an array of 8 ints.
    * Does quick bit-flicking to lookup needed characters.
    */
   class Charmap
@@ -41,16 +47,17 @@ private:
   };
 
 
 public:
   nsUrlClassifierUtils();
 
   NS_DECL_THREADSAFE_ISUPPORTS
   NS_DECL_NSIURLCLASSIFIERUTILS
+  NS_DECL_NSIOBSERVER
 
   nsresult Init();
 
   nsresult CanonicalizeHostname(const nsACString & hostname,
                                 nsACString & _retval);
   nsresult CanonicalizePath(const nsACString & url, nsACString & _retval);
 
   // This function will encode all "special" characters in typical url encoding,
@@ -75,12 +82,18 @@ private:
   // Disallow copy constructor
   nsUrlClassifierUtils(const nsUrlClassifierUtils&);
 
   // Function to tell if we should encode a character.
   bool ShouldURLEscape(const unsigned char c) const;
 
   void CleanupHostname(const nsACString & host, nsACString & _retval);
 
+  nsresult ReadProvidersFromPrefs(ProviderDictType& aDict);
+
   nsAutoPtr<Charmap> mEscapeCharmap;
+
+  // The provider lookup table and its mutex.
+  ProviderDictType mProviderDict;
+  mozilla::Mutex mProviderDictLock;
 };
 
 #endif // nsUrlClassifierUtils_h_

--- a/toolkit/components/url-classifier/tests/gtest/Common.cpp
+++ b/toolkit/components/url-classifier/tests/gtest/Common.cpp
@@ -1,15 +1,16 @@
 #include "Common.h"
 #include "HashStore.h"
 #include "Classifier.h"
 #include "nsAppDirectoryServiceDefs.h"
 #include "nsTArray.h"
 #include "nsIThread.h"
 #include "nsThreadUtils.h"
+#include "nsUrlClassifierUtils.h"
 
 using namespace mozilla;
 using namespace mozilla::safebrowsing;
 
 template<typename Function>
 void RunTestInNewThread(Function&& aFunction) {
   nsCOMPtr<nsIRunnable> r = NS_NewRunnableFunction(mozilla::Forward<Function>(aFunction));
   nsCOMPtr<nsIThread> testingThread;
@@ -36,16 +37,26 @@ GetFile(const nsTArray<nsString>& path)
 void ApplyUpdate(nsTArray<TableUpdate*>& updates)
 {
   nsCOMPtr<nsIFile> file;
   NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
 
   UniquePtr<Classifier> classifier(new Classifier());
   classifier->Open(*file);
 
+  {
+    // Force nsIUrlClassifierUtils loading on main thread
+    // because nsIUrlClassifierDBService will not run in advance
+    // in gtest.
+    nsresult rv;
+    nsCOMPtr<nsIUrlClassifierUtils> dummy =
+      do_GetService(NS_URLCLASSIFIERUTILS_CONTRACTID, &rv);
+      ASSERT_TRUE(NS_SUCCEEDED(rv));
+  }
+
   RunTestInNewThread([&] () -> void {
     classifier->ApplyUpdates(&updates);
   });
 }
 
 void ApplyUpdate(TableUpdate* update)
 {
   nsTArray<TableUpdate*> updates = { update };

--- a/toolkit/components/url-classifier/tests/gtest/TestLookupCacheV4.cpp
+++ b/toolkit/components/url-classifier/tests/gtest/TestLookupCacheV4.cpp
@@ -27,17 +27,17 @@ GeneratePrefix(const _Fragment& aFragmen
 static UniquePtr<LookupCacheV4>
 SetupLookupCacheV4(const _PrefixArray& prefixArray)
 {
   nsCOMPtr<nsIFile> file;
   NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
 
   file->AppendNative(GTEST_SAFEBROWSING_DIR);
 
-  UniquePtr<LookupCacheV4> cache = MakeUnique<LookupCacheV4>(GTEST_TABLE, file);
+  UniquePtr<LookupCacheV4> cache = MakeUnique<LookupCacheV4>(GTEST_TABLE, EmptyCString(), file);
   nsresult rv = cache->Init();
   EXPECT_EQ(rv, NS_OK);
 
   PrefixStringMap map;
   PrefixArrayToPrefixStringMap(prefixArray, map);
   rv = cache->Build(map);
   EXPECT_EQ(rv, NS_OK);
 

--- a/toolkit/components/url-classifier/tests/gtest/TestPerProviderDirectory.cpp
+++ b/toolkit/components/url-classifier/tests/gtest/TestPerProviderDirectory.cpp
@@ -27,17 +27,17 @@ void VerifyPrivateStorePath(const char* 
                             const char* aProvider,
                             nsIFile* aRootDir,
                             bool aUsePerProviderStore)
 {
   nsString rootStorePath;
   nsresult rv = aRootDir->GetPath(rootStorePath);
   EXPECT_EQ(rv, NS_OK);
 
-  T target(nsCString(aTableName), aRootDir);
+  T target(nsCString(aTableName), nsCString(aProvider), aRootDir);
 
   nsIFile* privateStoreDirectory =
     PerProviderDirectoryTestUtils::InspectStoreDirectory(target);
 
   nsString privateStorePath;
   rv = privateStoreDirectory->GetPath(privateStorePath);
   ASSERT_EQ(rv, NS_OK);
 

--- a/toolkit/components/url-classifier/tests/gtest/TestUrlClassifierTableUpdateV4.cpp
+++ b/toolkit/components/url-classifier/tests/gtest/TestUrlClassifierTableUpdateV4.cpp
@@ -247,17 +247,17 @@ testPartialUpdate(PrefixStringMap& add,
 static void
 testOpenLookupCache()
 {
   nsCOMPtr<nsIFile> file;
   NS_GetSpecialDirectory(NS_APP_USER_PROFILE_50_DIR, getter_AddRefs(file));
   file->AppendNative(GTEST_SAFEBROWSING_DIR);
 
   RunTestInNewThread([&] () -> void {
-    LookupCacheV4 cache(nsCString(GTEST_TABLE), file);
+    LookupCacheV4 cache(nsCString(GTEST_TABLE), EmptyCString(), file);
     nsresult rv = cache.Init();
     ASSERT_EQ(rv, NS_OK);
 
     rv = cache.Open();
     ASSERT_EQ(rv, NS_OK);
   });
 }