--- a/toolkit/components/url-classifier/Classifier.cpp
+++ b/toolkit/components/url-classifier/Classifier.cpp
@@ -1419,17 +1419,22 @@ Classifier::UpdateCache(TableUpdate* aUp
   LookupCache *lookupCache = GetLookupCache(table);
   if (!lookupCache) {
     return NS_ERROR_FAILURE;
   }
 
   auto lookupV2 = LookupCache::Cast<LookupCacheV2>(lookupCache);
   if (lookupV2) {
     auto updateV2 = TableUpdate::Cast<TableUpdateV2>(aUpdate);
-    lookupV2->AddCompletionsToCache(updateV2->AddCompletes());
+
+    if (updateV2->AddCompletes().Length() > 0) {
+      lookupV2->AddPositiveCache(updateV2->AddCompletes());
+    } else {
+      lookupV2->AddNegativeCache(updateV2->MissPrefixes());
+    }
   } else {
     auto lookupV4 = LookupCache::Cast<LookupCacheV4>(lookupCache);
     if (!lookupV4) {
       return NS_ERROR_FAILURE;
     }
 
     auto updateV4 = TableUpdate::Cast<TableUpdateV4>(aUpdate);
     lookupV4->AddFullHashResponseToCache(updateV4->FullHashResponse());

--- a/toolkit/components/url-classifier/Entries.h
+++ b/toolkit/components/url-classifier/Entries.h
@@ -257,16 +257,17 @@ struct SubComplete {
     return subChunk - aOther.subChunk;
   }
 };
 
 typedef FallibleTArray<AddPrefix>   AddPrefixArray;
 typedef FallibleTArray<AddComplete> AddCompleteArray;
 typedef FallibleTArray<SubPrefix>   SubPrefixArray;
 typedef FallibleTArray<SubComplete> SubCompleteArray;
+typedef FallibleTArray<Prefix>      MissPrefixArray;
 
 /**
  * Compares chunks by their add chunk, then their prefix.
  */
 template<class T>
 class EntryCompare {
 public:
   typedef T elem_type;

--- a/toolkit/components/url-classifier/HashStore.cpp
+++ b/toolkit/components/url-classifier/HashStore.cpp
@@ -144,16 +144,25 @@ TableUpdateV2::NewSubComplete(uint32_t a
   SubComplete *sub = mSubCompletes.AppendElement(fallible);
   if (!sub) return NS_ERROR_OUT_OF_MEMORY;
   sub->addChunk = aAddChunk;
   sub->complete = aHash;
   sub->subChunk = aSubChunk;
   return NS_OK;
 }
 
+nsresult
+TableUpdateV2::NewMissPrefix(const Prefix& aPrefix)
+{
+  Prefix* prefix = mMissPrefixes.AppendElement(fallible);
+  if (!prefix) return NS_ERROR_OUT_OF_MEMORY;
+  *prefix = aPrefix;
+  return NS_OK;
+}
+
 void
 TableUpdateV4::NewPrefixes(int32_t aSize, std::string& aPrefixes)
 {
   NS_ENSURE_TRUE_VOID(aPrefixes.size() % aSize == 0);
   NS_ENSURE_TRUE_VOID(!mPrefixesMap.Get(aSize));
 
   if (LOG_ENABLED() && 4 == aSize) {
     int numOfPrefixes = aPrefixes.size() / 4;

--- a/toolkit/components/url-classifier/HashStore.h
+++ b/toolkit/components/url-classifier/HashStore.h
@@ -60,17 +60,18 @@ public:
   bool Empty() const override {
     return mAddChunks.Length() == 0 &&
       mSubChunks.Length() == 0 &&
       mAddExpirations.Length() == 0 &&
       mSubExpirations.Length() == 0 &&
       mAddPrefixes.Length() == 0 &&
       mSubPrefixes.Length() == 0 &&
       mAddCompletes.Length() == 0 &&
-      mSubCompletes.Length() == 0;
+      mSubCompletes.Length() == 0 &&
+      mMissPrefixes.Length() == 0;
   }
 
   // Throughout, uint32_t aChunk refers only to the chunk number. Chunk data is
   // stored in the Prefix structures.
   MOZ_MUST_USE nsresult NewAddChunk(uint32_t aChunk) {
     return mAddChunks.Set(aChunk);
   };
   MOZ_MUST_USE nsresult NewSubChunk(uint32_t aChunk) {
@@ -87,29 +88,33 @@ public:
                                      const Prefix& aPrefix,
                                      uint32_t aSubChunk);
   MOZ_MUST_USE nsresult NewAddComplete(uint32_t aChunk,
                                        const Completion& aCompletion);
   MOZ_MUST_USE nsresult NewSubComplete(uint32_t aAddChunk,
                                        const Completion& aCompletion,
                                        uint32_t aSubChunk);
 
+  MOZ_MUST_USE nsresult NewMissPrefix(const Prefix& aPrefix);
+
   ChunkSet& AddChunks() { return mAddChunks; }
   ChunkSet& SubChunks() { return mSubChunks; }
 
   // Expirations for chunks.
   ChunkSet& AddExpirations() { return mAddExpirations; }
   ChunkSet& SubExpirations() { return mSubExpirations; }
 
   // Hashes associated with this chunk.
   AddPrefixArray& AddPrefixes() { return mAddPrefixes; }
   SubPrefixArray& SubPrefixes() { return mSubPrefixes; }
   AddCompleteArray& AddCompletes() { return mAddCompletes; }
   SubCompleteArray& SubCompletes() { return mSubCompletes; }
 
+  MissPrefixArray& MissPrefixes() { return mMissPrefixes; }
+
   // For downcasting.
   static const int TAG = 2;
 
 private:
 
   // The list of chunk numbers that we have for each of the type of chunks.
   ChunkSet mAddChunks;
   ChunkSet mSubChunks;
@@ -119,16 +124,18 @@ private:
   // 4-byte sha256 prefixes.
   AddPrefixArray mAddPrefixes;
   SubPrefixArray mSubPrefixes;
 
   // 32-byte hashes.
   AddCompleteArray mAddCompletes;
   SubCompleteArray mSubCompletes;
 
+  MissPrefixArray mMissPrefixes;
+
   virtual int Tag() const override { return TAG; }
 };
 
 // Structure for DBService/HashStore/Classifiers to update.
 // It would contain the prefixes (both fixed and variable length)
 // for addition and indices to removal. See Bug 1283009.
 class TableUpdateV4 : public TableUpdate {
 public:

--- a/toolkit/components/url-classifier/LookupCache.cpp
+++ b/toolkit/components/url-classifier/LookupCache.cpp
@@ -376,23 +376,29 @@ LookupCacheV2::Has(const Completion& aCo
   *aMatchLength = 0;
 
   uint32_t prefix = aCompletion.ToUint32();
 
   bool found;
   nsresult rv = mPrefixSet->Contains(prefix, &found);
   NS_ENSURE_SUCCESS(rv, rv);
 
-  LOG(("Probe in %s: %X, found %d", mTableName.get(), prefix, found));
 
   if (found) {
+    if (mNegativeCache.BinaryIndexOf(prefix) != mNegativeCache.NoIndex) {
+      LOG(("Probe in %s: %X, hit negative cache", mTableName.get(), prefix));
+      return NS_OK;
+    }
+
     *aHas = true;
     *aMatchLength = PREFIX_SIZE;
   }
 
+  LOG(("Probe in %s: %X, found %d", mTableName.get(), prefix, found));
+
   if ((mGetHashCache.BinaryIndexOf(aCompletion) != nsTArray<Completion>::NoIndex) ||
       (mUpdateCompletions.BinaryIndexOf(aCompletion) != nsTArray<Completion>::NoIndex)) {
     LOG(("Complete in %s", mTableName.get()));
     *aFromCache = true;
     *aHas = true;
 
     int64_t ageSec; // in seconds
     if (aTableFreshness.Get(mTableName, &ageSec)) {
@@ -447,29 +453,44 @@ LookupCacheV2::GetPrefixes(FallibleTArra
     // This can happen if its a new table, so no error.
     LOG(("GetPrefixes from empty LookupCache"));
     return NS_OK;
   }
   return mPrefixSet->GetPrefixesNative(aAddPrefixes);
 }
 
 nsresult
-LookupCacheV2::AddCompletionsToCache(AddCompleteArray& aAddCompletes)
+LookupCacheV2::AddPositiveCache(AddCompleteArray& aAddCompletes)
 {
   for (uint32_t i = 0; i < aAddCompletes.Length(); i++) {
-    if (mGetHashCache.BinaryIndexOf(aAddCompletes[i].CompleteHash()) == mGetHashCache.NoIndex) {
+    if (mGetHashCache.BinaryIndexOf(aAddCompletes[i].CompleteHash()) ==
+        mGetHashCache.NoIndex) {
       mGetHashCache.AppendElement(aAddCompletes[i].CompleteHash());
     }
   }
   mGetHashCache.Sort();
 
   return NS_OK;
 }
 
 nsresult
+LookupCacheV2::AddNegativeCache(MissPrefixArray& aMissPrefixes)
+{
+  for (uint32_t i = 0; i < aMissPrefixes.Length(); i++) {
+    if (mNegativeCache.BinaryIndexOf(aMissPrefixes[i].ToUint32()) ==
+        mNegativeCache.NoIndex) {
+      mNegativeCache.AppendElement(aMissPrefixes[i].ToUint32());
+    }
+  }
+  mNegativeCache.Sort();
+
+  return NS_OK;
+}
+
+nsresult
 LookupCacheV2::ReadCompletions()
 {
   HashStore store(mTableName, mProvider, mRootStoreDirectory);
 
   nsresult rv = store.Open();
   NS_ENSURE_SUCCESS(rv, rv);
 
   mUpdateCompletions.Clear();
@@ -480,16 +501,17 @@ LookupCacheV2::ReadCompletions()
   }
 
   return NS_OK;
 }
 
 void
 LookupCacheV2::ClearCache()
 {
+  mNegativeCache.Clear();
   mGetHashCache.Clear();
 }
 
 nsresult
 LookupCacheV2::ClearPrefixes()
 {
   return mPrefixSet->SetPrefixes(nullptr, 0);
 }

--- a/toolkit/components/url-classifier/LookupCache.h
+++ b/toolkit/components/url-classifier/LookupCache.h
@@ -121,27 +121,36 @@ public:
   nsCString table;
 };
 
 class CacheResultV2 final : public CacheResult
 {
 public:
   static const int VER;
 
-  Completion completion;
+  // When this is true, hash.prefix is used to record a cache miss.
+  bool miss = false;
+  union {
+    Completion completion;
+    Prefix prefix;
+  } hash;
+
   uint32_t addChunk;
 
   bool operator==(const CacheResultV2& aOther) const {
-    return table == aOther.table &&
-           completion == aOther.completion &&
-           addChunk == aOther.addChunk;
+    if (table != aOther.table || miss != aOther.miss) {
+      return false;
+    }
+    return miss ? (hash.prefix == aOther.hash.prefix) :
+                  (hash.completion == aOther.hash.completion &&
+                   addChunk == aOther.addChunk);
   }
 
   bool findCompletion(const Completion& aCompletion) const override {
-    return completion == aCompletion;
+    return hash.completion == aCompletion;
   }
 
   virtual int Ver() const override { return VER; }
 };
 
 class CacheResultV4 final : public CacheResult
 {
 public:
@@ -267,17 +276,19 @@ public:
   virtual bool IsEmpty() override;
 
   nsresult Build(AddPrefixArray& aAddPrefixes,
                  AddCompleteArray& aAddCompletes);
 
   nsresult GetPrefixes(FallibleTArray<uint32_t>& aAddPrefixes);
 
   // This will Clear() the passed arrays when done.
-  nsresult AddCompletionsToCache(AddCompleteArray& aAddCompletes);
+  nsresult AddPositiveCache(AddCompleteArray& aAddCompletes);
+
+  nsresult AddNegativeCache(MissPrefixArray& aMissPrefixes);
 
 #if DEBUG
   virtual void DumpCache() override;
 
   void DumpCompletions();
 #endif
 
   static const int VER;
@@ -300,14 +311,18 @@ private:
   // Full length hashes obtained in update request
   CompletionArray mUpdateCompletions;
 
   // Set of prefixes known to be in the database
   RefPtr<nsUrlClassifierPrefixSet> mPrefixSet;
 
   // Full length hashes obtained in gethash request
   CompletionArray mGetHashCache;
+
+  // Entries that cannot be completed. We expect them to die at
+  // the next update
+  nsTArray<uint32_t> mNegativeCache;
 };
 
 } // namespace safebrowsing
 } // namespace mozilla
 
 #endif

--- a/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
+++ b/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
@@ -277,42 +277,30 @@ nsUrlClassifierDBServiceWorker::DoLookup
 
 
   if (LOG_ENABLED()) {
     PRIntervalTime clockEnd = PR_IntervalNow();
     LOG(("query took %dms\n",
          PR_IntervalToMilliseconds(clockEnd - clockStart)));
   }
 
-  nsAutoPtr<LookupResultArray> completes(new LookupResultArray());
-
   for (uint32_t i = 0; i < results->Length(); i++) {
-    const LookupResult& lookupResult = results->ElementAt(i);
-
-    // mMissCache should only be used in V2.
-    if (!lookupResult.mProtocolV2 ||
-        !mMissCache.Contains(lookupResult.hash.fixedLengthPrefix)) {
-      completes->AppendElement(lookupResult);
-    }
-  }
-
-  for (uint32_t i = 0; i < completes->Length(); i++) {
-    if (!completes->ElementAt(i).Confirmed()) {
+    if (!results->ElementAt(i).Confirmed()) {
       // We're going to be doing a gethash request, add some extra entries.
       // Note that we cannot pass the first two by reference, because we
-      // add to completes, whicah can cause completes to reallocate and move.
-      AddNoise(completes->ElementAt(i).hash.fixedLengthPrefix,
-               completes->ElementAt(i).mTableName,
-               mGethashNoise, *completes);
+      // add to results, whicah can cause completes to reallocate and move.
+      AddNoise(results->ElementAt(i).hash.fixedLengthPrefix,
+               results->ElementAt(i).mTableName,
+               mGethashNoise, *results);
       break;
     }
   }
 
   // At this point ownership of 'results' is handed to the callback.
-  c->LookupComplete(completes.forget());
+  c->LookupComplete(results.forget());
 
   return NS_OK;
 }
 
 nsresult
 nsUrlClassifierDBServiceWorker::HandlePendingLookups()
 {
   if (gShuttingDownThread) {
@@ -693,18 +681,16 @@ nsUrlClassifierDBServiceWorker::NotifyUp
   }
 
   // Do not record telemetry for testing tables.
   if (!provider.Equals(TESTING_TABLE_PROVIDER_NAME)) {
     Telemetry::Accumulate(Telemetry::URLCLASSIFIER_UPDATE_ERROR, provider,
                           NS_ERROR_GET_CODE(updateStatus));
   }
 
-  mMissCache.Clear();
-
   // Null out mUpdateObserver before notifying so that BeginUpdate()
   // becomes available prior to callback.
   nsCOMPtr<nsIUrlClassifierUpdateObserver> updateObserver = nullptr;
   updateObserver.swap(mUpdateObserver);
 
   if (NS_SUCCEEDED(mUpdateStatus)) {
     LOG(("Notifying success: %d", mUpdateWaitSec));
     updateObserver->UpdateSuccess(mUpdateWaitSec);
@@ -907,25 +893,28 @@ nsresult
 nsUrlClassifierDBServiceWorker::CacheResultToTableUpdate(CacheResult* aCacheResult,
                                                          TableUpdate* aUpdate)
 {
   auto tuV2 = TableUpdate::Cast<TableUpdateV2>(aUpdate);
   if (tuV2) {
     auto result = CacheResult::Cast<CacheResultV2>(aCacheResult);
     MOZ_ASSERT(result);
 
-    LOG(("CacheCompletion hash %X, Addchunk %d", result->completion.ToUint32(),
-         result->addChunk));
+    if (!result->miss) {
+      LOG(("CacheCompletion hash %X, Addchunk %d", result->hash.completion.ToUint32(),
+           result->addChunk));
 
-    nsresult rv = tuV2->NewAddComplete(result->addChunk, result->completion);
-    if (NS_FAILED(rv)) {
-      return rv;
+      nsresult rv = tuV2->NewAddComplete(result->addChunk, result->hash.completion);
+      if (NS_FAILED(rv)) {
+        return rv;
+      }
+      return tuV2->NewAddChunk(result->addChunk);
+    } else {
+      return tuV2->NewMissPrefix(result->hash.prefix);
     }
-    rv = tuV2->NewAddChunk(result->addChunk);
-    return rv;
   }
 
   auto tuV4 = TableUpdate::Cast<TableUpdateV4>(aUpdate);
   if (tuV4) {
     auto result = CacheResult::Cast<CacheResultV4>(aCacheResult);
     MOZ_ASSERT(result);
 
     if (LOG_ENABLED()) {
@@ -942,31 +931,16 @@ nsUrlClassifierDBServiceWorker::CacheRes
     return NS_OK;
   }
 
   // tableUpdate object should be either v2 or v4.
   return NS_ERROR_FAILURE;
 }
 
 nsresult
-nsUrlClassifierDBServiceWorker::CacheMisses(PrefixArray *results)
-{
-  LOG(("nsUrlClassifierDBServiceWorker::CacheMisses [%p] %" PRIuSIZE,
-       this, results->Length()));
-
-  // Ownership is transferred in to us
-  nsAutoPtr<PrefixArray> resultsPtr(results);
-
-  for (uint32_t i = 0; i < resultsPtr->Length(); i++) {
-    mMissCache.AppendElement(resultsPtr->ElementAt(i));
-  }
-  return NS_OK;
-}
-
-nsresult
 nsUrlClassifierDBServiceWorker::OpenDb()
 {
   if (gShuttingDownThread) {
     return NS_ERROR_ABORT;
   }
 
   MOZ_ASSERT(!NS_IsMainThread(), "Must initialize DB on background thread");
   // Connection already open, don't do anything.
@@ -1065,16 +1039,17 @@ public:
     , mPendingCompletions(0)
     , mCallback(c)
     {}
 
 private:
   ~nsUrlClassifierLookupCallback();
 
   nsresult HandleResults();
+  nsresult HandleMissResults();
   nsresult ProcessComplete(CacheResult* aCacheResult);
 
   RefPtr<nsUrlClassifierDBService> mDBService;
   nsAutoPtr<LookupResultArray> mResults;
 
   // Completed results to send back to the worker for caching.
   nsAutoPtr<CacheResultArray> mCacheResults;
 
@@ -1193,17 +1168,17 @@ nsUrlClassifierLookupCallback::Completio
   LOG(("nsUrlClassifierLookupCallback::Completion [%p, %s, %d]",
        this, PromiseFlatCString(aTableName).get(), aChunkId));
 
   MOZ_ASSERT(!StringEndsWith(aTableName, NS_LITERAL_CSTRING("-proto")));
 
   auto result = new CacheResultV2;
 
   result->table = aTableName;
-  result->completion.Assign(aCompleteHash);
+  result->hash.completion.Assign(aCompleteHash);
   result->addChunk = aChunkId;
 
   return ProcessComplete(result);
 }
 
 NS_IMETHODIMP
 nsUrlClassifierLookupCallback::CompletionV4(const nsACString& aPartialHash,
                                             const nsACString& aTableName,
@@ -1380,31 +1355,23 @@ nsUrlClassifierLookupCallback::HandleRes
     }
   }
 
   if (matchResult != MatchResult::eTelemetryDisabled) {
     Telemetry::Accumulate(Telemetry::URLCLASSIFIER_MATCH_RESULT,
                           ConvertMatchResultToUint(matchResult));
   }
 
-  // TODO: Bug 1333328, Refactor cache miss mechanism for v2.
   // Some parts of this gethash request generated no hits at all.
   // Prefixes must have been removed from the database since our last update.
   // Save the prefixes we checked to prevent repeated requests
   // until the next update.
-  nsAutoPtr<PrefixArray> cacheMisses(new PrefixArray());
-  if (cacheMisses) {
-    for (uint32_t i = 0; i < mResults->Length(); i++) {
-      LookupResult &result = mResults->ElementAt(i);
-      if (result.mProtocolV2 && !result.Confirmed() && !result.mNoise) {
-        cacheMisses->AppendElement(result.hash.fixedLengthPrefix);
-      }
-    }
-    // Hands ownership of the miss array back to the worker thread.
-    mDBService->CacheMisses(cacheMisses.forget());
+  nsresult rv = HandleMissResults();
+  if (NS_FAILED(rv)) {
+    return rv;
   }
 
   if (mCacheResults) {
     // This hands ownership of the cache results array back to the worker
     // thread.
     mDBService->CacheCompletions(mCacheResults.forget());
   }
 
@@ -1413,16 +1380,41 @@ nsUrlClassifierLookupCallback::HandleRes
     if (i != 0)
       tableStr.Append(',');
     tableStr.Append(tables[i]);
   }
 
   return mCallback->HandleEvent(tableStr);
 }
 
+nsresult
+nsUrlClassifierLookupCallback::HandleMissResults()
+{
+  for (uint32_t i = 0; i < mResults->Length(); i++) {
+    LookupResult &result = mResults->ElementAt(i);
+    if (!result.mProtocolV2 || result.Confirmed() || result.mNoise) {
+      continue;
+    }
+
+    if (!mCacheResults) {
+      mCacheResults = new CacheResultArray();
+      if (!mCacheResults) {
+        return NS_ERROR_OUT_OF_MEMORY;
+      }
+    }
+
+    auto cacheResult = new CacheResultV2;
+    cacheResult->table = result.mTableName;
+    cacheResult->miss = true;
+    cacheResult->hash.prefix = result.hash.fixedLengthPrefix;
+    mCacheResults->AppendElement(cacheResult);
+  }
+  return NS_OK;
+}
+
 struct Provider {
   nsCString name;
   uint8_t priority;
 };
 
 // Order matters
 // Provider which is not included in this table has the lowest priority 0
 static const Provider kBuiltInProviders[] = {
@@ -2259,24 +2251,16 @@ nsUrlClassifierDBService::ReloadDatabase
 nsresult
 nsUrlClassifierDBService::CacheCompletions(CacheResultArray *results)
 {
   NS_ENSURE_TRUE(gDbBackgroundThread, NS_ERROR_NOT_INITIALIZED);
 
   return mWorkerProxy->CacheCompletions(results);
 }
 
-nsresult
-nsUrlClassifierDBService::CacheMisses(PrefixArray *results)
-{
-  NS_ENSURE_TRUE(gDbBackgroundThread, NS_ERROR_NOT_INITIALIZED);
-
-  return mWorkerProxy->CacheMisses(results);
-}
-
 bool
 nsUrlClassifierDBService::GetCompleter(const nsACString &tableName,
                                        nsIUrlClassifierHashCompleter **completer)
 {
   // If we have specified a completer, go ahead and query it. This is only
   // used by tests.
   if (mCompleters.Get(tableName, completer)) {
     return true;

--- a/toolkit/components/url-classifier/nsUrlClassifierDBService.h
+++ b/toolkit/components/url-classifier/nsUrlClassifierDBService.h
@@ -78,17 +78,16 @@ public:
   NS_DECL_THREADSAFE_ISUPPORTS
   NS_DECL_NSIURLCLASSIFIERDBSERVICE
   NS_DECL_NSIURICLASSIFIER
   NS_DECL_NSIOBSERVER
 
   bool GetCompleter(const nsACString& tableName,
                       nsIUrlClassifierHashCompleter** completer);
   nsresult CacheCompletions(mozilla::safebrowsing::CacheResultArray *results);
-  nsresult CacheMisses(mozilla::safebrowsing::PrefixArray *results);
 
   static nsIThread* BackgroundThread();
 
   static bool ShutdownHasStarted();
 
 private:
   // No subclassing
   ~nsUrlClassifierDBService();
@@ -175,17 +174,16 @@ public:
 
   // Open the DB connection
   nsresult GCC_MANGLING_WORKAROUND OpenDb();
 
   // Provide a way to forcibly close the db connection.
   nsresult GCC_MANGLING_WORKAROUND CloseDb();
 
   nsresult CacheCompletions(CacheResultArray * aEntries);
-  nsresult CacheMisses(PrefixArray * aEntries);
 
   // Used to probe the state of the worker thread. When the update begins,
   // mUpdateObserver will be set. When the update finished, mUpdateObserver
   // will be nulled out in NotifyUpdateObserver.
   bool IsBusyUpdating() const { return !!mUpdateObserver; }
 
   // Delegate Classifier to disable async update. If there is an
   // ongoing update on the update thread, we will be blocked until
@@ -234,20 +232,16 @@ private:
   nsCOMPtr<nsIFile> mCacheDir;
 
   // XXX: maybe an array of autoptrs.  Or maybe a class specifically
   // storing a series of updates.
   nsTArray<mozilla::safebrowsing::TableUpdate*> mTableUpdates;
 
   uint32_t mUpdateWaitSec;
 
-  // Entries that cannot be completed. We expect them to die at
-  // the next update
-  PrefixArray mMissCache;
-
   // Stores the last results that triggered a table update.
   nsAutoPtr<CacheResultArray> mLastResults;
 
   nsresult mUpdateStatus;
   nsTArray<nsCString> mUpdateTables;
 
   nsCOMPtr<nsIUrlClassifierUpdateObserver> mUpdateObserver;
   bool mInStream;

--- a/toolkit/components/url-classifier/nsUrlClassifierProxies.cpp
+++ b/toolkit/components/url-classifier/nsUrlClassifierProxies.cpp
@@ -206,30 +206,16 @@ UrlClassifierDBServiceWorkerProxy::Cache
 
 NS_IMETHODIMP
 UrlClassifierDBServiceWorkerProxy::CacheCompletionsRunnable::Run()
 {
   mTarget->CacheCompletions(mEntries);
   return NS_OK;
 }
 
-nsresult
-UrlClassifierDBServiceWorkerProxy::CacheMisses(PrefixArray * aEntries)
-{
-  nsCOMPtr<nsIRunnable> r = new CacheMissesRunnable(mTarget, aEntries);
-  return DispatchToWorkerThread(r);
-}
-
-NS_IMETHODIMP
-UrlClassifierDBServiceWorkerProxy::CacheMissesRunnable::Run()
-{
-  mTarget->CacheMisses(mEntries);
-  return NS_OK;
-}
-
 NS_IMETHODIMP
 UrlClassifierDBServiceWorkerProxy::SetLastUpdateTime(const nsACString& table,
                                                      uint64_t lastUpdateTime)
 {
   nsCOMPtr<nsIRunnable> r =
     new SetLastUpdateTimeRunnable(mTarget, table, lastUpdateTime);
   return DispatchToWorkerThread(r);
 }

--- a/toolkit/components/url-classifier/nsUrlClassifierProxies.h
+++ b/toolkit/components/url-classifier/nsUrlClassifierProxies.h
@@ -128,32 +128,16 @@ public:
 
     NS_DECL_NSIRUNNABLE
 
   private:
     RefPtr<nsUrlClassifierDBServiceWorker> mTarget;
      mozilla::safebrowsing::CacheResultArray *mEntries;
   };
 
-  class CacheMissesRunnable : public mozilla::Runnable
-  {
-  public:
-    CacheMissesRunnable(nsUrlClassifierDBServiceWorker* aTarget,
-                        mozilla::safebrowsing::PrefixArray *aEntries)
-      : mTarget(aTarget)
-      , mEntries(aEntries)
-    { }
-
-    NS_DECL_NSIRUNNABLE
-
-  private:
-    RefPtr<nsUrlClassifierDBServiceWorker> mTarget;
-    mozilla::safebrowsing::PrefixArray *mEntries;
-  };
-
   class DoLocalLookupRunnable : public mozilla::Runnable
   {
   public:
     DoLocalLookupRunnable(nsUrlClassifierDBServiceWorker* aTarget,
                           const nsACString& spec,
                           const nsACString& tables,
                           mozilla::safebrowsing::LookupResultArray* results)
       : mTarget(aTarget)
@@ -205,17 +189,16 @@ public:
   nsresult DoLocalLookup(const nsACString& spec,
                          const nsACString& tables,
                          mozilla::safebrowsing::LookupResultArray* results);
 
   nsresult OpenDb();
   nsresult CloseDb();
 
   nsresult CacheCompletions(mozilla::safebrowsing::CacheResultArray * aEntries);
-  nsresult CacheMisses(mozilla::safebrowsing::PrefixArray * aEntries);
 
 private:
   ~UrlClassifierDBServiceWorkerProxy() {}
 
   RefPtr<nsUrlClassifierDBServiceWorker> mTarget;
 };
 
 // The remaining classes here are all proxies to the main thread