Bug 702217 - Avoid double allocation in UrlClassifier. Handle OOM conditions. r=dcamp
authorGian-Carlo Pascutto <gpascutto@mozilla.com>
Tue, 10 Jan 2012 17:09:32 +0100
changeset 85350 a0fb6ed985c669b3d641186097ff735222e7464c
parent 85349 4796cf23c294a2d11b9dd302fbc3392c7d0248d7
child 85351 9bee22d394a9772e6fd7ef67f3ada5cd56eb22f7
push id805
push userakeybl@mozilla.com
push dateWed, 01 Feb 2012 18:17:35 +0000
treeherdermozilla-aurora@6fb3bf232436 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdcamp
bugs702217
milestone12.0a1
Bug 702217 - Avoid double allocation in UrlClassifier. Handle OOM conditions. r=dcamp
toolkit/components/build/nsToolkitCompsCID.h
toolkit/components/telemetry/TelemetryHistograms.h
toolkit/components/url-classifier/nsIUrlClassifierPrefixSet.idl
toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp
toolkit/components/url-classifier/nsUrlClassifierPrefixSet.h
toolkit/components/url-classifier/tests/unit/test_prefixset.js
--- a/toolkit/components/build/nsToolkitCompsCID.h
+++ b/toolkit/components/build/nsToolkitCompsCID.h
@@ -158,19 +158,19 @@
 // {59648a91-5a60-4122-8ff2-54b839c84aed}
 #define NS_PARENTALCONTROLSSERVICE_CID \
 { 0x580530e5, 0x118c, 0x4bc7, { 0xab, 0x88, 0xbc, 0x2c, 0xd2, 0xb9, 0x72, 0x23 } }
 
 // {e7f70966-9a37-48d7-8aeb-35998f31090e}
 #define NS_TYPEAHEADFIND_CID \
 { 0xe7f70966, 0x9a37, 0x48d7, { 0x8a, 0xeb, 0x35, 0x99, 0x8f, 0x31, 0x09, 0x0e} }
 
-// {7902e243-9b00-4673-9288-1b7fc246a8f8}
+// {15a892dd-cb0f-4a9f-a27f-8291d5e16653}
 #define NS_URLCLASSIFIERPREFIXSET_CID \
-{ 0x7902e243, 0x9b00, 0x4673, { 0x92, 0x88, 0x1b, 0x7f, 0xc2, 0x46, 0xa8, 0xf8} }
+{ 0x15a892dd, 0xcb0f, 0x4a9f, { 0xa2, 0x7f, 0x82, 0x91, 0xd5, 0xe1, 0x66, 0x53} }
 
 // {5eb7c3c1-ec1f-4007-87cc-eefb37d68ce6}
 #define NS_URLCLASSIFIERDBSERVICE_CID \
 { 0x5eb7c3c1, 0xec1f, 0x4007, { 0x87, 0xcc, 0xee, 0xfb, 0x37, 0xd6, 0x8c, 0xe6} }
 
 // {c2be6dc0-ef1e-4abd-86a2-4f864ddc57f6}
 #define NS_URLCLASSIFIERSTREAMUPDATER_CID \
 { 0xc2be6dc0, 0xef1e, 0x4abd, { 0x86, 0xa2, 0x4f, 0x86, 0x4d, 0xdc, 0x57, 0xf6} }
--- a/toolkit/components/telemetry/TelemetryHistograms.h
+++ b/toolkit/components/telemetry/TelemetryHistograms.h
@@ -261,16 +261,17 @@ HISTOGRAM(NETWORK_DISK_CACHE_OUTPUT_STRE
 /**
  * Url-Classifier telemetry
  */
 #ifdef MOZ_URL_CLASSIFIER
 HISTOGRAM(URLCLASSIFIER_PS_FILELOAD_TIME, 1, 1000, 10, EXPONENTIAL, "Time spent loading PrefixSet from file (ms)")
 HISTOGRAM(URLCLASSIFIER_PS_FALLOCATE_TIME, 1, 1000, 10, EXPONENTIAL, "Time spent fallocating PrefixSet (ms)")
 HISTOGRAM(URLCLASSIFIER_PS_CONSTRUCT_TIME, 1, 5000, 15, EXPONENTIAL, "Time spent constructing PrefixSet from DB (ms)")
 HISTOGRAM(URLCLASSIFIER_PS_LOOKUP_TIME, 1, 500, 10, EXPONENTIAL, "Time spent per PrefixSet lookup (ms)")
+HISTOGRAM_BOOLEAN(URLCLASSIFIER_PS_OOM, "Did UrlClassifier run out of memory during PrefixSet construction?")
 #endif
 
 /**
  * Places telemetry.
  */
 HISTOGRAM(PLACES_PAGES_COUNT, 1000, 150000, 20, EXPONENTIAL, "PLACES: Number of unique pages")
 HISTOGRAM(PLACES_BOOKMARKS_COUNT, 100, 8000, 15, EXPONENTIAL, "PLACES: Number of bookmarks")
 HISTOGRAM(PLACES_TAGS_COUNT, 1, 200, 10, EXPONENTIAL, "PLACES: Number of tags")
--- a/toolkit/components/url-classifier/nsIUrlClassifierPrefixSet.idl
+++ b/toolkit/components/url-classifier/nsIUrlClassifierPrefixSet.idl
@@ -7,17 +7,17 @@
  * the License. You may obtain a copy of the License at
  * http://www.mozilla.org/MPL/
  *
  * Software distributed under the License is distributed on an "AS IS" basis,
  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  * for the specific language governing rights and limitations under the
  * License.
  *
- * The Original Code is Url Classifier code
+ * The Original Code is Url Classifier code.
  *
  * The Initial Developer of the Original Code is
  * the Mozilla Foundation.
  * Portions created by the Initial Developer are Copyright (C) 2011
  * the Initial Developer. All Rights Reserved.
  *
  * Contributor(s):
  *   Gian-Carlo Pascutto <gpascutto@mozilla.com>
@@ -36,23 +36,32 @@
  *
  * ***** END LICENSE BLOCK ***** */
 
 #include "nsISupports.idl"
 #include "nsIFile.idl"
 
 interface nsIArray;
 
-[scriptable, uuid(7902e243-9b00-4673-9288-1b7fc246a8f8)]
+// Note that the PrefixSet name is historical and we do properly support
+// duplicated values, so it's really a Prefix Trie.
+// All methods are thread-safe.
+
+[scriptable, uuid(519c8519-0f30-426b-bb7b-c400ba0318e2)]
 interface nsIUrlClassifierPrefixSet : nsISupports
 {
+  // Fills the PrefixSet with the given array of prefixes.
+  // Can send an empty Array to clear the tree. A truly "empty tree"
+  // cannot be represented, so put a sentinel value if that is required
+  // Requires array to be sorted.
   void setPrefixes([const, array, size_is(aLength)] in unsigned long aPrefixes,
                    in unsigned long aLength);
-  void addPrefixes([const, array, size_is(aLength)] in unsigned long aPrefixes,
-                   in unsigned long aLength);
-  boolean contains(in unsigned long aPrefix);
+  // Do a lookup in the PrefixSet, return whether the value is present.
+  // If aReady is set, we will block until there are any entries.
+  // If not set, we will return in aReady whether we were ready or not.
   boolean probe(in unsigned long aPrefix, in unsigned long aKey,
                 inout boolean aReady);
+  // Return the key that is used to randomize the collisions in the prefixes.
   PRUint32 getKey();
   boolean isEmpty();
   void loadFromFile(in nsIFile aFile);
   void storeToFile(in nsIFile aFile);
 };
--- a/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
+++ b/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
@@ -486,17 +486,17 @@ public:
                             PRUint32 numRequested,
                             bool before,
                             nsTArray<nsUrlClassifierEntry> &entries);
 
   // Ask the db for a random number.  This is temporary, and should be
   // replaced with nsIRandomGenerator when 419739 is fixed.
   nsresult RandomNumber(PRInt64 *randomNum);
   // Return an array with all Prefixes known
-  nsresult ReadPrefixes(nsTArray<PRUint32>& array, PRUint32 aKey);
+  nsresult ReadPrefixes(FallibleTArray<PRUint32>& array, PRUint32 aKey);
 
 
 protected:
   nsresult ReadEntries(mozIStorageStatement *statement,
                        nsTArray<nsUrlClassifierEntry>& entries);
   nsUrlClassifierDBServiceWorker *mWorker;
   nsCOMPtr<mozIStorageConnection> mConnection;
 
@@ -508,17 +508,18 @@ protected:
   nsCOMPtr<mozIStorageStatement> mExpireStatement;
 
   nsCOMPtr<mozIStorageStatement> mPartialEntriesStatement;
   nsCOMPtr<mozIStorageStatement> mPartialEntriesAfterStatement;
   nsCOMPtr<mozIStorageStatement> mLastPartialEntriesStatement;
   nsCOMPtr<mozIStorageStatement> mPartialEntriesBeforeStatement;
 
   nsCOMPtr<mozIStorageStatement> mRandomStatement;
-  nsCOMPtr<mozIStorageStatement> mAllPrefixStatement;
+  nsCOMPtr<mozIStorageStatement> mAllPrefixGetStatement;
+  nsCOMPtr<mozIStorageStatement> mAllPrefixCountStatement;
 };
 
 nsresult
 nsUrlClassifierStore::Init(nsUrlClassifierDBServiceWorker *worker,
                            mozIStorageConnection *connection,
                            const nsACString& entriesName)
 {
   mWorker = worker;
@@ -571,18 +572,23 @@ nsUrlClassifierStore::Init(nsUrlClassifi
   NS_ENSURE_SUCCESS(rv, rv);
 
   rv = mConnection->CreateStatement
     (NS_LITERAL_CSTRING("SELECT abs(random())"),
      getter_AddRefs(mRandomStatement));
   NS_ENSURE_SUCCESS(rv, rv);
 
   rv = mConnection->CreateStatement(NS_LITERAL_CSTRING("SELECT domain, partial_data, complete_data FROM ")
-     + entriesName,
-     getter_AddRefs(mAllPrefixStatement));
+    + entriesName,
+    getter_AddRefs(mAllPrefixGetStatement));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  rv = mConnection->CreateStatement(NS_LITERAL_CSTRING("SELECT COUNT(1) FROM ")
+    + entriesName,
+    getter_AddRefs(mAllPrefixCountStatement));
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 void
 nsUrlClassifierStore::Close()
 {
@@ -594,17 +600,18 @@ nsUrlClassifierStore::Close()
   mExpireStatement = nsnull;
 
   mPartialEntriesStatement = nsnull;
   mPartialEntriesAfterStatement = nsnull;
   mPartialEntriesBeforeStatement = nsnull;
   mLastPartialEntriesStatement = nsnull;
   mRandomStatement = nsnull;
 
-  mAllPrefixStatement = nsnull;
+  mAllPrefixGetStatement = nsnull;
+  mAllPrefixCountStatement = nsnull;
 
   mConnection = nsnull;
 }
 
 
 bool
 nsUrlClassifierStore::ReadStatement(mozIStorageStatement* statement,
                                     nsUrlClassifierEntry& entry)
@@ -3545,60 +3552,73 @@ static nsresult KeyedHash(PRUint32 aPref
   h1 *= c5;
   h1 ^= h1 >> 16;
 
   *aOut = h1;
 
   return NS_OK;
 }
 
-nsresult nsUrlClassifierStore::ReadPrefixes(nsTArray<PRUint32>& array,
+nsresult nsUrlClassifierStore::ReadPrefixes(FallibleTArray<PRUint32>& array,
                                             PRUint32 aKey)
 {
-  mozStorageStatementScoper scoper(mAllPrefixStatement);
+  mozStorageStatementScoper scoper(mAllPrefixGetStatement);
+  mozStorageStatementScoper scoperToo(mAllPrefixCountStatement);
   bool hasMoreData;
   PRUint32 pcnt = 0;
   PRUint32 fcnt = 0;
 
 #if defined(PR_LOGGING)
   PRIntervalTime clockStart = 0;
   if (LOG_ENABLED()) {
     clockStart = PR_IntervalNow();
   }
 #endif
 
-  while (NS_SUCCEEDED(mAllPrefixStatement->ExecuteStep(&hasMoreData)) && hasMoreData) {
+  // Make sure we allocate no more than we really need, so first
+  // check how much entries there are
+  if (NS_SUCCEEDED(mAllPrefixCountStatement->ExecuteStep(&hasMoreData)) && hasMoreData) {
+    PRUint32 count = mAllPrefixCountStatement->AsInt32(0);
+    if (!array.SetCapacity(count)) {
+      return NS_ERROR_OUT_OF_MEMORY;
+    }
+  } else {
+    return NS_ERROR_FILE_CORRUPTED;
+  }
+
+  while (NS_SUCCEEDED(mAllPrefixGetStatement->ExecuteStep(&hasMoreData)) && hasMoreData) {
     PRUint32 prefixval;
     PRUint32 domainval;
     PRUint32 size;
 
-    const PRUint8 *blobdomain = mAllPrefixStatement->AsSharedBlob(0, &size);
+    const PRUint8 *blobdomain = mAllPrefixGetStatement->AsSharedBlob(0, &size);
     if (!blobdomain || (size != DOMAIN_LENGTH))
       return false;
 
     domainval = *(reinterpret_cast<const PRUint32*>(blobdomain));
 
-    const PRUint8 *blobprefix = mAllPrefixStatement->AsSharedBlob(1, &size);
+    const PRUint8 *blobprefix = mAllPrefixGetStatement->AsSharedBlob(1, &size);
     if (!blobprefix || (size != PARTIAL_LENGTH)) {
-      const PRUint8 *blobfull = mAllPrefixStatement->AsSharedBlob(2, &size);
+      const PRUint8 *blobfull = mAllPrefixGetStatement->AsSharedBlob(2, &size);
       if (!blobfull || (size != COMPLETE_LENGTH)) {
         prefixval = domainval;
         fcnt++;
       } else {
         prefixval = *(reinterpret_cast<const PRUint32*>(blobfull));
       }
     } else {
       prefixval = *(reinterpret_cast<const PRUint32*>(blobprefix));
     }
 
     PRUint32 keyedVal;
     nsresult rv = KeyedHash(prefixval, domainval, aKey, &keyedVal);
     NS_ENSURE_SUCCESS(rv, rv);
 
-    array.AppendElement(keyedVal);
+    PRUint32 *res = array.AppendElement(keyedVal);
+    MOZ_ASSERT(res != nsnull);
     pcnt++;
     // Normal DB size is about 500k entries. If we are getting 10x
     // as much, the database must be corrupted.
     if (pcnt > 5000000) {
       return NS_ERROR_FILE_CORRUPTED;
     }
   }
 
@@ -3619,47 +3639,64 @@ nsresult
 nsUrlClassifierDBServiceWorker::ConstructPrefixSet()
 {
   Telemetry::AutoTimer<Telemetry::URLCLASSIFIER_PS_CONSTRUCT_TIME> timer;
 
   PRUint32 key;
   nsresult rv = mPrefixSet->GetKey(&key);
   NS_ENSURE_SUCCESS(rv, rv);
 
-  nsTArray<PRUint32> array;
+  FallibleTArray<PRUint32> array;
   rv = mMainStore.ReadPrefixes(array, key);
-  NS_ENSURE_SUCCESS(rv, rv);
+  if (NS_FAILED(rv)) {
+    goto error_bailout;
+  }
 
 #ifdef HASHFUNCTION_COLLISION_TEST
   array.Sort();
   PRUint32 collisions = 0;
   for (int i = 1; i < array.Length(); i++) {
     if (array[i - 1] == array[i]) {
       collisions++;
     }
   }
   LOG(("%d collisions in the set", collisions));
 #endif
 
-  // clear old tree
-  rv = mPrefixSet->SetPrefixes(nsnull, 0);
-  NS_ENSURE_SUCCESS(rv, rv);
   if (array.IsEmpty()) {
-    // DB is empty, but put a sentinel to show that we looked
-    array.AppendElement(0);
+    // DB is empty, put a sentinel to show that we loaded it
+    if (!array.AppendElement(0)) {
+      goto error_bailout;
+    }
   }
-  // construct new one
+  // SetPrefixes requires sorted arrays
+  array.Sort();
+
+  // construct new prefixset
   rv = mPrefixSet->SetPrefixes(array.Elements(), array.Length());
-  NS_ENSURE_SUCCESS(rv, rv);
+  if (NS_FAILED(rv)) {
+    goto error_bailout;
+  }
 
   // store the new tree to disk
   rv = mPrefixSet->StoreToFile(mPSFile);
   NS_WARN_IF_FALSE(NS_SUCCEEDED(rv), "failed to store the prefixset");
 
   return NS_OK;
+
+ error_bailout:
+  // load an empty prefixset so the browser can work
+  nsAutoTArray<PRUint32, 1> sentinel;
+  sentinel.Clear();
+  sentinel.AppendElement(0);
+  mPrefixSet->SetPrefixes(sentinel.Elements(), sentinel.Length());
+  if (rv == NS_ERROR_OUT_OF_MEMORY) {
+    Telemetry::Accumulate(Telemetry::URLCLASSIFIER_PS_OOM, 1);
+  }
+  return rv;
 }
 
 nsresult
 nsUrlClassifierDBServiceWorker::LoadPrefixSet(nsCOMPtr<nsIFile> & aFile)
 {
   bool empty;
   nsresult rv = mPrefixSet->IsEmpty(&empty);
   NS_ENSURE_SUCCESS(rv, rv);
--- a/toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp
+++ b/toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp
@@ -184,80 +184,91 @@ nsUrlClassifierPrefixSet::InitKey()
   LOG(("Initialized PrefixSet, key = %X", mRandomKey));
 
   return NS_OK;
 }
 
 NS_IMETHODIMP
 nsUrlClassifierPrefixSet::SetPrefixes(const PRUint32 * aArray, PRUint32 aLength)
 {
-  {
+  if (aLength <= 0) {
     MutexAutoLock lock(mPrefixSetLock);
     if (mHasPrefixes) {
       LOG(("Clearing PrefixSet"));
       mDeltas.Clear();
       mIndexPrefixes.Clear();
       mIndexStarts.Clear();
       mHasPrefixes = false;
     }
-  }
-  if (aLength > 0) {
-    // Ensure they are sorted before adding
-    nsTArray<PRUint32> prefixes;
-    prefixes.AppendElements(aArray, aLength);
-    prefixes.Sort();
-    AddPrefixes(prefixes.Elements(), prefixes.Length());
+  } else {
+    return MakePrefixSet(aArray, aLength);
   }
 
   return NS_OK;
 }
 
-NS_IMETHODIMP
-nsUrlClassifierPrefixSet::AddPrefixes(const PRUint32 * prefixes, PRUint32 aLength)
+nsresult
+nsUrlClassifierPrefixSet::MakePrefixSet(const PRUint32 * prefixes, PRUint32 aLength)
 {
   if (aLength == 0) {
     return NS_OK;
   }
 
-  nsTArray<PRUint32> mNewIndexPrefixes(mIndexPrefixes);
-  nsTArray<PRUint32> mNewIndexStarts(mIndexStarts);
-  nsTArray<PRUint16> mNewDeltas(mDeltas);
+#ifdef DEBUG
+  for (PRUint32 i = 1; i < aLength; i++) {
+    MOZ_ASSERT(prefixes[i] >= prefixes[i-1]);
+  }
+#endif
 
-  mNewIndexPrefixes.AppendElement(prefixes[0]);
-  mNewIndexStarts.AppendElement(mNewDeltas.Length());
+  FallibleTArray<PRUint32> newIndexPrefixes;
+  FallibleTArray<PRUint32> newIndexStarts;
+  FallibleTArray<PRUint16> newDeltas;
+
+  if (!newIndexPrefixes.AppendElement(prefixes[0])) {
+    return NS_ERROR_OUT_OF_MEMORY;
+  }
+  if (!newIndexStarts.AppendElement(newDeltas.Length())) {
+    return NS_ERROR_OUT_OF_MEMORY;
+  }
 
   PRUint32 numOfDeltas = 0;
   PRUint32 currentItem = prefixes[0];
   for (PRUint32 i = 1; i < aLength; i++) {
     if ((numOfDeltas >= DELTAS_LIMIT) ||
           (prefixes[i] - currentItem >= MAX_INDEX_DIFF)) {
-      mNewIndexStarts.AppendElement(mNewDeltas.Length());
-      mNewIndexPrefixes.AppendElement(prefixes[i]);
+      if (!newIndexStarts.AppendElement(newDeltas.Length())) {
+        return NS_ERROR_OUT_OF_MEMORY;
+      }
+      if (!newIndexPrefixes.AppendElement(prefixes[i])) {
+        return NS_ERROR_OUT_OF_MEMORY;
+      }
       numOfDeltas = 0;
     } else {
       PRUint16 delta = prefixes[i] - currentItem;
-      mNewDeltas.AppendElement(delta);
+      if (!newDeltas.AppendElement(delta)) {
+        return NS_ERROR_OUT_OF_MEMORY;
+      }
       numOfDeltas++;
     }
     currentItem = prefixes[i];
   }
 
-  mNewIndexPrefixes.Compact();
-  mNewIndexStarts.Compact();
-  mNewDeltas.Compact();
+  newIndexPrefixes.Compact();
+  newIndexStarts.Compact();
+  newDeltas.Compact();
 
-  LOG(("Total number of indices: %d", mNewIndexPrefixes.Length()));
-  LOG(("Total number of deltas: %d", mNewDeltas.Length()));
+  LOG(("Total number of indices: %d", newIndexPrefixes.Length()));
+  LOG(("Total number of deltas: %d", newDeltas.Length()));
 
   MutexAutoLock lock(mPrefixSetLock);
 
   // This just swaps some pointers
-  mIndexPrefixes.SwapElements(mNewIndexPrefixes);
-  mIndexStarts.SwapElements(mNewIndexStarts);
-  mDeltas.SwapElements(mNewDeltas);
+  mIndexPrefixes.SwapElements(newIndexPrefixes);
+  mIndexStarts.SwapElements(newIndexStarts);
+  mDeltas.SwapElements(newDeltas);
 
   mHasPrefixes = true;
   mSetIsReady.NotifyAll();
 
   return NS_OK;
 }
 
 PRUint32 nsUrlClassifierPrefixSet::BinSearch(PRUint32 start,
@@ -273,17 +284,17 @@ PRUint32 nsUrlClassifierPrefixSet::BinSe
       end = i - 1;
     } else {
       return i;
     }
   }
   return end;
 }
 
-NS_IMETHODIMP
+nsresult
 nsUrlClassifierPrefixSet::Contains(PRUint32 aPrefix, bool * aFound)
 {
   mPrefixSetLock.AssertCurrentThreadOwns();
 
   *aFound = false;
 
   if (!mHasPrefixes) {
     return NS_OK;
--- a/toolkit/components/url-classifier/nsUrlClassifierPrefixSet.h
+++ b/toolkit/components/url-classifier/nsUrlClassifierPrefixSet.h
@@ -54,31 +54,21 @@
 class nsPrefixSetReporter;
 
 class nsUrlClassifierPrefixSet : public nsIUrlClassifierPrefixSet
 {
 public:
   nsUrlClassifierPrefixSet();
   virtual ~nsUrlClassifierPrefixSet();
 
-  // Can send an empty Array to clean the tree
   NS_IMETHOD SetPrefixes(const PRUint32* aArray, PRUint32 aLength);
-  // Given prefixes must be in sorted order and bigger than
-  // anything currently in the Prefix Set
-  NS_IMETHOD AddPrefixes(const PRUint32* aArray, PRUint32 aLength);
-  // Does the PrefixSet contain this prefix? not thread-safe
-  NS_IMETHOD Contains(PRUint32 aPrefix, bool* aFound);
-  // Do a lookup in the PrefixSet
-  // if aReady is set, we will block until there are any entries
-  // if not set, we will return in aReady whether we were ready or not
   NS_IMETHOD Probe(PRUint32 aPrefix, PRUint32 aKey, bool* aReady, bool* aFound);
   NS_IMETHOD IsEmpty(bool * aEmpty);
   NS_IMETHOD LoadFromFile(nsIFile* aFile);
   NS_IMETHOD StoreToFile(nsIFile* aFile);
-  // Return a key that is used to randomize the collisions in the prefixes
   NS_IMETHOD GetKey(PRUint32* aKey);
 
   NS_DECL_ISUPPORTS
 
   // Return the estimated size of the set on disk and in memory,
   // in bytes
   size_t SizeOfIncludingThis(nsMallocSizeOfFun mallocSizeOf);
 
@@ -86,29 +76,31 @@ protected:
   static const PRUint32 DELTAS_LIMIT = 100;
   static const PRUint32 MAX_INDEX_DIFF = (1 << 16);
   static const PRUint32 PREFIXSET_VERSION_MAGIC = 1;
 
   mozilla::Mutex mPrefixSetLock;
   mozilla::CondVar mSetIsReady;
   nsRefPtr<nsPrefixSetReporter> mReporter;
 
+  nsresult Contains(PRUint32 aPrefix, bool* aFound);
+  nsresult MakePrefixSet(const PRUint32* aArray, PRUint32 aLength);
   PRUint32 BinSearch(PRUint32 start, PRUint32 end, PRUint32 target);
   nsresult LoadFromFd(mozilla::AutoFDClose & fileFd);
   nsresult StoreToFd(mozilla::AutoFDClose & fileFd);
   nsresult InitKey();
 
   // boolean indicating whether |setPrefixes| has been
   // called with a non-empty array.
   bool mHasPrefixes;
   // key used to randomize hash collisions
   PRUint32 mRandomKey;
   // the prefix for each index.
-  nsTArray<PRUint32> mIndexPrefixes;
+  FallibleTArray<PRUint32> mIndexPrefixes;
   // the value corresponds to the beginning of the run
   // (an index in |_deltas|) for the index
-  nsTArray<PRUint32> mIndexStarts;
+  FallibleTArray<PRUint32> mIndexStarts;
   // array containing deltas from indices.
-  nsTArray<PRUint16> mDeltas;
+  FallibleTArray<PRUint16> mDeltas;
 
 };
 
 #endif
--- a/toolkit/components/url-classifier/tests/unit/test_prefixset.js
+++ b/toolkit/components/url-classifier/tests/unit/test_prefixset.js
@@ -61,17 +61,17 @@ function doExpectedLookups(pset, prefixe
   }
 }
 
 // testBasicPset: A very basic test of the prefix set to make sure that it
 // exists and to give a basic example of its use.
 function testBasicPset() {
   let pset = Cc["@mozilla.org/url-classifier/prefixset;1"]
                .createInstance(Ci.nsIUrlClassifierPrefixSet);
-  let prefixes = [2,100,50,2000,78000,1593203];
+  let prefixes = [2,50,100,2000,78000,1593203];
   pset.setPrefixes(prefixes, prefixes.length);
 
   do_check_true(wrappedProbe(pset, 100));
   do_check_false(wrappedProbe(pset, 100000));
   do_check_true(wrappedProbe(pset, 1593203));
   do_check_false(wrappedProbe(pset, 999));
   do_check_false(wrappedProbe(pset, 0));
 }
@@ -94,25 +94,16 @@ function testSimplePset() {
   let pset = newPset();
   let prefixes = [1,2,100,400,123456789];
   pset.setPrefixes(prefixes, prefixes.length);
 
   doRandomLookups(pset, prefixes, 100);
   doExpectedLookups(pset, prefixes, 1);
 }
 
-function testUnsortedPset() {
-  let pset = newPset();
-  let prefixes = [5,1,20,100,200000,100000];
-  pset.setPrefixes(prefixes, prefixes.length);
-
-  doRandomLookups(pset, prefixes, 100);
-  doExpectedLookups(pset, prefixes, 1);
-}
-
 function testReSetPrefixes() {
   let pset = newPset();
   let prefixes = [1, 5, 100, 1000, 150000];
   pset.setPrefixes(prefixes, prefixes.length);
 
   doExpectedLookups(pset, prefixes, 1);
 
   let secondPrefixes = [12, 50, 300, 2000, 5000, 200000];
@@ -153,17 +144,16 @@ function testTinySet() {
 
   prefixes = [];
   pset.setPrefixes(prefixes, prefixes.length);
   do_check_false(wrappedProbe(pset, 1));
 }
 
 let tests = [testBasicPset,
              testSimplePset,
-             testUnsortedPset,
              testReSetPrefixes,
              testLargeSet,
              testDuplicates,
              testTinySet];
 
 function run_test() {
   // None of the tests use |executeSoon| or any sort of callbacks, so we can
   // just run them in succession.