Bug 673470 - Don't resort if not needed. Fix comparator. Cleanups. r=dcamp
authorGian-Carlo Pascutto <gpascutto@mozilla.com>
Wed, 15 Aug 2012 09:08:37 +0200
changeset 108384 bad7e62cd7d23dc3425b2e3c88123b8b2f04a611
parent 108383 033c251cfddb96a3fbeb67b778b94bee5be50d62
child 108385 553ae070f33a456123c74b4620945d83f906df09
push id214
push userakeybl@mozilla.com
push dateWed, 14 Nov 2012 20:38:59 +0000
treeherdermozilla-release@c8b08ec8e1aa [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdcamp
bugs673470
milestone17.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 673470 - Don't resort if not needed. Fix comparator. Cleanups. r=dcamp
toolkit/components/url-classifier/Entries.h
toolkit/components/url-classifier/HashStore.cpp
toolkit/components/url-classifier/LookupCache.cpp
toolkit/components/url-classifier/ProtocolParser.cpp
--- a/toolkit/components/url-classifier/Entries.h
+++ b/toolkit/components/url-classifier/Entries.h
@@ -123,29 +123,35 @@ struct SafebrowsingHash
   void ToString(nsACString& aStr) const {
     uint32 len = ((sHashSize + 2) / 3) * 4;
     aStr.SetCapacity(len + 1);
     PL_Base64Encode((char*)buf, sHashSize, aStr.BeginWriting());
     aStr.BeginWriting()[len] = '\0';
   }
 #endif
   PRUint32 ToUint32() const {
-    PRUint32 res = 0;
-    memcpy(&res, buf, NS_MIN<size_t>(4, S));
-    return res;
+      return *((uint32*)buf);
   }
   void FromUint32(PRUint32 aHash) {
-    memcpy(buf, &aHash, NS_MIN<size_t>(4, S));
+      *((uint32*)buf) = aHash;
   }
 };
 
 class PrefixComparator {
 public:
   static int Compare(const PRUint8* a, const PRUint8* b) {
-    return *((uint32*)a) - *((uint32*)b);
+      uint32 first = *((uint32*)a);
+      uint32 second = *((uint32*)b);
+      if (first > second) {
+          return 1;
+      } else if (first == second) {
+          return 0;
+      } else {
+          return -1;
+      }
   }
 };
 typedef SafebrowsingHash<PREFIX_SIZE, PrefixComparator> Prefix;
 typedef nsTArray<Prefix> PrefixArray;
 
 class CompletionComparator {
 public:
   static int Compare(const PRUint8* a, const PRUint8* b) {
--- a/toolkit/components/url-classifier/HashStore.cpp
+++ b/toolkit/components/url-classifier/HashStore.cpp
@@ -76,18 +76,18 @@
 //    uint32 numSubChunks
 //    uint32 numAddPrefixes
 //    uint32 numSubPrefixes
 //    uint32 numAddCompletes
 //    uint32 numSubCompletes
 //    0...numAddChunks               uint32 addChunk
 //    0...numSubChunks               uint32 subChunk
 //    byte sliced (numAddPrefixes)   uint32 add chunk of AddPrefixes
+//    byte sliced (numSubPrefixes)   uint32 add chunk of SubPrefixes
 //    byte sliced (numSubPrefixes)   uint32 sub chunk of SubPrefixes
-//    byte sliced (numSubPrefixes)   uint32 add chunk of SubPrefixes
 //    byte sliced (numSubPrefixes)   uint32 SubPrefixes
 //    0...numAddCompletes            32-byte Completions + uint32 addChunk
 //    0...numSubCompletes            32-byte Completions + uint32 addChunk
 //                                                       + uint32 subChunk
 //    16-byte MD5 of all preceding data
 
 // NSPR_LOG_MODULES=UrlClassifierDbService:5
 extern PRLogModuleInfo *gUrlClassifierDbServiceLog;
@@ -991,39 +991,71 @@ RemoveMatchingPrefixes(const SubPrefixAr
       } while (hashIter != hashEnd &&
                !(removeIter->CompareAlt(*hashIter) < 0));
       ++removeIter;
     }
   }
   Erase(aFullHashes, out, hashIter);
 }
 
+#ifdef DEBUG
+template <class T>
+static void EnsureSorted(nsTArray<T>* aArray)
+{
+  T* start = aArray->Elements();
+  T* end = aArray->Elements() + aArray->Length();
+  T* iter = start;
+  T* previous = start;
+
+  while (iter != end) {
+    previous = iter;
+    ++iter;
+    if (iter != end) {
+      MOZ_ASSERT(iter->Compare(*previous) >= 0);
+    }
+  }
+
+  return;
+}
+#endif
+
 nsresult
 HashStore::ProcessSubs()
 {
-  EntrySort(mAddPrefixes);
-  EntrySort(mSubPrefixes);
-  EntrySort(mAddCompletes);
-  EntrySort(mSubCompletes);
+#ifdef DEBUG
+  EnsureSorted(&mAddPrefixes);
+  EnsureSorted(&mSubPrefixes);
+  EnsureSorted(&mAddCompletes);
+  EnsureSorted(&mSubCompletes);
+  LOG(("All databases seem to have a consistent sort order."));
+#endif
 
   RemoveMatchingPrefixes(mSubPrefixes, &mAddCompletes);
   RemoveMatchingPrefixes(mSubPrefixes, &mSubCompletes);
 
   // Clean up temporary subs (without per-client randomization),
   // that we temporarily stored so we could knock out completes.
   ChunkSet dummyChunks;
   dummyChunks.Set(0);
   ExpireEntries(&mSubPrefixes, dummyChunks);
   mSubChunks.Remove(dummyChunks);
 
   // Remove any remaining subbed prefixes from both addprefixes
   // and subprefixes.
   KnockoutSubs(&mSubPrefixes, &mAddPrefixes);
   KnockoutSubs(&mSubCompletes, &mAddCompletes);
 
+#ifdef DEBUG
+  EnsureSorted(&mAddPrefixes);
+  EnsureSorted(&mSubPrefixes);
+  EnsureSorted(&mAddCompletes);
+  EnsureSorted(&mSubCompletes);
+  LOG(("All databases seem to have a consistent sort order."));
+#endif
+
   return NS_OK;
 }
 
 nsresult
 HashStore::AugmentAdds(const nsTArray<PRUint32>& aPrefixes)
 {
   uint32 cnt = aPrefixes.Length();
   if (cnt != mAddPrefixes.Length()) {
--- a/toolkit/components/url-classifier/LookupCache.cpp
+++ b/toolkit/components/url-classifier/LookupCache.cpp
@@ -683,16 +683,36 @@ LookupCache::GetHostKeys(const nsACStrin
   return NS_OK;
 }
 
 bool LookupCache::IsPrimed()
 {
   return mPrimed;
 }
 
+#ifdef DEBUG
+template <class T>
+static void EnsureSorted(T* aArray)
+{
+  typename T::elem_type* start = aArray->Elements();
+  typename T::elem_type* end = aArray->Elements() + aArray->Length();
+  typename T::elem_type* iter = start;
+  typename T::elem_type* previous = start;
+
+  while (iter != end) {
+    previous = iter;
+    ++iter;
+    if (iter != end) {
+      MOZ_ASSERT(*previous <= *iter);
+    }
+  }
+  return;
+}
+#endif
+
 nsresult
 LookupCache::ConstructPrefixSet(AddPrefixArray& aAddPrefixes)
 {
   Telemetry::AutoTimer<Telemetry::URLCLASSIFIER_PS_CONSTRUCT_TIME> timer;
 
   FallibleTArray<PRUint32> array;
   nsresult rv;
   if (!array.SetCapacity(aAddPrefixes.Length())) {
@@ -704,18 +724,20 @@ LookupCache::ConstructPrefixSet(AddPrefi
     array.AppendElement(aAddPrefixes[i].PrefixHash().ToUint32());
   }
   aAddPrefixes.Clear();
 
   if (array.IsEmpty()) {
     // DB is empty, but put a sentinel to show that we looked
     array.AppendElement(0);
   }
+#ifdef DEBUG
   // PrefixSet requires sorted order
-  array.Sort();
+  EnsureSorted(&array);
+#endif
 
   // construct new one, replace old entries
   rv = mPrefixSet->SetPrefixes(array.Elements(), array.Length());
   if (NS_FAILED(rv)) {
     goto error_bailout;
   }
 
 #ifdef DEBUG
--- a/toolkit/components/url-classifier/ProtocolParser.cpp
+++ b/toolkit/components/url-classifier/ProtocolParser.cpp
@@ -505,24 +505,24 @@ ProtocolParser::ProcessPlaintextChunk(co
       if (mChunkState.hashSize == COMPLETE_SIZE) {
         Completion hash;
         hash.FromPlaintext(Substring(iter, end), mCryptoHash);
         mTableUpdate->NewSubComplete(addChunk, hash, mChunkState.num);
       } else {
         NS_ASSERTION(mChunkState.hashSize == 4, "Only 32- or 4-byte hashes can be used for add chunks.");
         Prefix hash;
         Completion domHash;
-        Prefix newHash;
         rv = LookupCache::GetKey(Substring(iter, end), &domHash, mCryptoHash);
         NS_ENSURE_SUCCESS(rv, rv);
         hash.FromPlaintext(Substring(iter, end), mCryptoHash);
         PRUint32 codedHash;
         rv = LookupCache::KeyedHash(hash.ToUint32(), domHash.ToUint32(), mHashKey,
                                     &codedHash, !mPerClientRandomize);
         NS_ENSURE_SUCCESS(rv, rv);
+        Prefix newHash;
         newHash.FromUint32(codedHash);
         mTableUpdate->NewSubPrefix(addChunk, newHash, mChunkState.num);
         // Needed to knock out completes
         // Fake chunk nr, will cause it to be removed next update
         mTableUpdate->NewSubPrefix(addChunk, hash, 0);
         mTableUpdate->NewSubChunk(0);
       }
     }