Bug 1399879 - The Places hash SQL function is expensive on large urls. r=adw
authorMarco Bonardo <mbonardo@mozilla.com>
Mon, 18 Sep 2017 10:31:20 +0200
changeset 382763 e0005dc883eed2d5f6b0ccc80dff6cab9967e3e2
parent 382762 ab239d8e44cae3ce936fde2cd9e2d97bb3893345
child 382764 4c4b18031f8030a7ff433bb709ae049a619ea834
push id32574
push userkwierso@gmail.com
push dateMon, 25 Sep 2017 23:25:38 +0000
treeherdermozilla-central@641bfddb8711 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersadw
bugs1399879
milestone58.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 1399879 - The Places hash SQL function is expensive on large urls. r=adw This patch limits the amount of chars we hash and avoids some string copies. MozReview-Commit-ID: AAcLtTzrYlb
toolkit/components/places/Database.cpp
toolkit/components/places/Database.h
toolkit/components/places/SQLFunctions.cpp
toolkit/components/places/tests/head_common.js
toolkit/components/places/tests/migration/places_v40.sqlite
toolkit/components/places/tests/migration/xpcshell.ini
toolkit/components/places/tests/unit/test_hash.js
toolkit/components/places/tests/unit/xpcshell.ini
--- a/toolkit/components/places/Database.cpp
+++ b/toolkit/components/places/Database.cpp
@@ -1116,16 +1116,23 @@ Database::InitSchema(bool* aDatabaseMigr
 
       if (currentSchemaVersion < 39) {
         rv = MigrateV39Up();
         NS_ENSURE_SUCCESS(rv, rv);
       }
 
       // Firefox 57 uses schema version 39.
 
+      if (currentSchemaVersion < 40) {
+        rv = MigrateV40Up();
+        NS_ENSURE_SUCCESS(rv, rv);
+      }
+
+      // Firefox 58 uses schema version 40.
+
       // Schema Upgrades must add migration code here.
 
       rv = UpdateBookmarkRootTitles();
       // We don't want a broken localization to cause us to think
       // the database is corrupt and needs to be replaced.
       MOZ_ASSERT(NS_SUCCEEDED(rv));
     }
   }
@@ -2341,16 +2348,41 @@ Database::MigrateV39Up() {
   // Create an index on dateAdded.
   nsresult rv = mMainConn->ExecuteSimpleSQL(CREATE_IDX_MOZ_BOOKMARKS_DATEADDED);
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
+Database::MigrateV40Up() {
+  MOZ_ASSERT(NS_IsMainThread());
+  // We are changing the hashing function to crop the hashed text to a maximum
+  // length, thus we must recalculate the hashes.
+  // Due to this, on downgrade some of these may not match, it should be limited
+  // to unicode and very long urls though.
+  nsresult rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+    "UPDATE moz_places "
+    "SET url_hash = hash(url) "
+    "WHERE url_hash <> hash(url)"));
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+    "UPDATE moz_icons "
+    "SET fixed_icon_url_hash = hash(fixup_url(icon_url)) "
+    "WHERE fixed_icon_url_hash <> hash(fixup_url(icon_url))"));
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+    "UPDATE moz_pages_w_icons "
+    "SET page_url_hash = hash(page_url) "
+    "WHERE page_url_hash <> hash(page_url)"));
+  NS_ENSURE_SUCCESS(rv, rv);
+  return NS_OK;
+}
+
+nsresult
 Database::GetItemsWithAnno(const nsACString& aAnnoName, int32_t aItemType,
                            nsTArray<int64_t>& aItemIds)
 {
   nsCOMPtr<mozIStorageStatement> stmt;
   nsresult rv = mMainConn->CreateStatement(NS_LITERAL_CSTRING(
     "SELECT b.id FROM moz_items_annos a "
     "JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id "
     "JOIN moz_bookmarks b ON b.id = a.item_id "
--- a/toolkit/components/places/Database.h
+++ b/toolkit/components/places/Database.h
@@ -14,17 +14,17 @@
 #include "mozilla/storage/StatementCache.h"
 #include "mozilla/Attributes.h"
 #include "nsIEventTarget.h"
 #include "Shutdown.h"
 #include "nsCategoryCache.h"
 
 // This is the schema version. Update it at any schema change and add a
 // corresponding migrateVxx method below.
-#define DATABASE_SCHEMA_VERSION 39
+#define DATABASE_SCHEMA_VERSION 40
 
 // Fired after Places inited.
 #define TOPIC_PLACES_INIT_COMPLETE "places-init-complete"
 // This topic is received when the profile is about to be lost.  Places does
 // initial shutdown work and notifies TOPIC_PLACES_SHUTDOWN to all listeners.
 // Any shutdown work that requires the Places APIs should happen here.
 #define TOPIC_PROFILE_CHANGE_TEARDOWN "profile-change-teardown"
 // Fired when Places is shutting down.  Any code should stop accessing Places
@@ -299,16 +299,17 @@ protected:
   nsresult MigrateV32Up();
   nsresult MigrateV33Up();
   nsresult MigrateV34Up();
   nsresult MigrateV35Up();
   nsresult MigrateV36Up();
   nsresult MigrateV37Up();
   nsresult MigrateV38Up();
   nsresult MigrateV39Up();
+  nsresult MigrateV40Up();
 
   nsresult UpdateBookmarkRootTitles();
 
   friend class ConnectionShutdownBlocker;
 
   int64_t CreateMobileRoot();
   nsresult GetItemsWithAnno(const nsACString& aAnnoName, int32_t aItemType,
                             nsTArray<int64_t>& aItemIds);
--- a/toolkit/components/places/SQLFunctions.cpp
+++ b/toolkit/components/places/SQLFunctions.cpp
@@ -14,21 +14,28 @@
 #include "nsUnicodeProperties.h"
 #include "nsUTF8Utils.h"
 #include "nsINavHistoryService.h"
 #include "nsPrintfCString.h"
 #include "nsNavHistory.h"
 #include "mozilla/Likely.h"
 #include "nsVariant.h"
 #include "mozilla/HashFunctions.h"
+#include <algorithm>
 
 // Maximum number of chars to search through.
 // MatchAutoCompleteFunction won't look for matches over this threshold.
 #define MAX_CHARS_TO_SEARCH_THROUGH 255
 
+// Maximum number of chars to use for calculating hashes. This value has been
+// picked to ensure low hash collisions on a real world common places.sqlite.
+// While collisions are not a big deal for functionality, a low ratio allows
+// for slightly more efficient SELECTs.
+#define MAX_CHARS_TO_HASH 1500U
+
 using namespace mozilla::storage;
 
 ////////////////////////////////////////////////////////////////////////////////
 //// Anonymous Helpers
 
 namespace {
 
   typedef nsACString::const_char_iterator const_char_iterator;
@@ -233,17 +240,17 @@ namespace {
       sourceCur = sourceNext;
     }
 
     return false;
   }
 
   static
   MOZ_ALWAYS_INLINE nsDependentCString
-  getSharedString(mozIStorageValueArray* aValues, uint32_t aIndex) {
+  getSharedUTF8String(mozIStorageValueArray* aValues, uint32_t aIndex) {
     uint32_t len;
     const char* str = aValues->AsSharedUTF8String(aIndex, &len);
     if (!str) {
       return nsDependentCString("", (uint32_t)0);
     }
     return nsDependentCString(str, len);
   }
 
@@ -411,36 +418,36 @@ namespace places {
   {
     // Macro to make the code a bit cleaner and easier to read.  Operates on
     // searchBehavior.
     int32_t searchBehavior = aArguments->AsInt32(kArgIndexSearchBehavior);
     #define HAS_BEHAVIOR(aBitName) \
       (searchBehavior & mozIPlacesAutoComplete::BEHAVIOR_##aBitName)
 
     nsDependentCString searchString =
-      getSharedString(aArguments, kArgSearchString);
+      getSharedUTF8String(aArguments, kArgSearchString);
     nsDependentCString url =
-      getSharedString(aArguments, kArgIndexURL);
+      getSharedUTF8String(aArguments, kArgIndexURL);
 
     int32_t matchBehavior = aArguments->AsInt32(kArgIndexMatchBehavior);
 
     // We only want to filter javascript: URLs if we are not supposed to search
     // for them, and the search does not start with "javascript:".
     if (matchBehavior != mozIPlacesAutoComplete::MATCH_ANYWHERE_UNMODIFIED &&
         StringBeginsWith(url, NS_LITERAL_CSTRING("javascript:")) &&
         !HAS_BEHAVIOR(JAVASCRIPT) &&
         !StringBeginsWith(searchString, NS_LITERAL_CSTRING("javascript:"))) {
       NS_ADDREF(*_result = mCachedZero);
       return NS_OK;
     }
 
     int32_t visitCount = aArguments->AsInt32(kArgIndexVisitCount);
     bool typed = aArguments->AsInt32(kArgIndexTyped) ? true : false;
     bool bookmark = aArguments->AsInt32(kArgIndexBookmark) ? true : false;
-    nsDependentCString tags = getSharedString(aArguments, kArgIndexTags);
+    nsDependentCString tags = getSharedUTF8String(aArguments, kArgIndexTags);
     int32_t openPageCount = aArguments->AsInt32(kArgIndexOpenPageCount);
     bool matches = false;
     if (HAS_BEHAVIOR(RESTRICT)) {
       // Make sure we match all the filter requirements.  If a given restriction
       // is active, make sure the corresponding condition is not true.
       matches = (!HAS_BEHAVIOR(HISTORY) || visitCount > 0) &&
                 (!HAS_BEHAVIOR(TYPED) || typed) &&
                 (!HAS_BEHAVIOR(BOOKMARK) || bookmark) &&
@@ -467,17 +474,17 @@ namespace places {
     // Clean up our URI spec and prepare it for searching.
     nsCString fixedUrlBuf;
     nsDependentCSubstring fixedUrl =
       fixupURISpec(url, matchBehavior, fixedUrlBuf);
     // Limit the number of chars we search through.
     const nsDependentCSubstring& trimmedUrl =
       Substring(fixedUrl, 0, MAX_CHARS_TO_SEARCH_THROUGH);
 
-    nsDependentCString title = getSharedString(aArguments, kArgIndexTitle);
+    nsDependentCString title = getSharedUTF8String(aArguments, kArgIndexTitle);
     // Limit the number of chars we search through.
     const nsDependentCSubstring& trimmedTitle =
       Substring(title, 0, MAX_CHARS_TO_SEARCH_THROUGH);
 
     // Determine if every token matches either the bookmark title, tags, page
     // title, or page URL.
     nsCWhitespaceTokenizer tokenizer(searchString);
     while (matches && tokenizer.hasMoreTokens()) {
@@ -999,52 +1006,57 @@ namespace places {
     MOZ_ASSERT(aArguments);
 
     // Fetch arguments.  Use default values if they were omitted.
     uint32_t numEntries;
     nsresult rv = aArguments->GetNumEntries(&numEntries);
     NS_ENSURE_SUCCESS(rv, rv);
     NS_ENSURE_TRUE(numEntries >= 1  && numEntries <= 2, NS_ERROR_FAILURE);
 
-    nsString str;
-    aArguments->GetString(0, str);
+    nsDependentCString str = getSharedUTF8String(aArguments, 0);
     nsAutoCString mode;
     if (numEntries > 1) {
       aArguments->GetUTF8String(1, mode);
     }
 
+    // HashString doesn't stop at the string boundaries if a length is passed to
+    // it, so ensure to pass a proper value.
+    const uint32_t maxLenToHash = std::min(static_cast<uint32_t>(str.Length()),
+                                           MAX_CHARS_TO_HASH);
     RefPtr<nsVariant> result = new nsVariant();
     if (mode.IsEmpty()) {
       // URI-like strings (having a prefix before a colon), are handled specially,
       // as a 48 bit hash, where first 16 bits are the prefix hash, while the
       // other 32 are the string hash.
       // The 16 bits have been decided based on the fact hashing all of the IANA
       // known schemes, plus "places", does not generate collisions.
-      nsAString::const_iterator start, tip, end;
-      str.BeginReading(tip);
+      // Since we only care about schemes, we just search in the first 50 chars.
+      // The longest known IANA scheme, at this time, is 30 chars.
+      const nsDependentCSubstring& strHead = StringHead(str, 50);
+      nsACString::const_iterator start, tip, end;
+      strHead.BeginReading(tip);
       start = tip;
-      str.EndReading(end);
-      if (FindInReadable(NS_LITERAL_STRING(":"), tip, end)) {
-        const nsDependentSubstring& prefix = Substring(start, tip);
+      strHead.EndReading(end);
+      uint32_t strHash = HashString(str.get(), maxLenToHash);
+      if (FindCharInReadable(':', tip, end)) {
+        const nsDependentCSubstring& prefix = Substring(start, tip);
         uint64_t prefixHash = static_cast<uint64_t>(HashString(prefix) & 0x0000FFFF);
         // The second half of the url is more likely to be unique, so we add it.
-        uint32_t srcHash = HashString(str);
-        uint64_t hash = (prefixHash << 32) + srcHash;
+        uint64_t hash = (prefixHash << 32) + strHash;
         result->SetAsInt64(hash);
       } else {
-        uint32_t hash = HashString(str);
-        result->SetAsInt64(hash);
+        result->SetAsInt64(strHash);
       }
     } else if (mode.EqualsLiteral("prefix_lo")) {
       // Keep only 16 bits.
-      uint64_t hash = static_cast<uint64_t>(HashString(str) & 0x0000FFFF) << 32;
+      uint64_t hash = static_cast<uint64_t>(HashString(str.get(), maxLenToHash) & 0x0000FFFF) << 32;
       result->SetAsInt64(hash);
     } else if (mode.EqualsLiteral("prefix_hi")) {
       // Keep only 16 bits.
-      uint64_t hash = static_cast<uint64_t>(HashString(str) & 0x0000FFFF) << 32;
+      uint64_t hash = static_cast<uint64_t>(HashString(str.get(), maxLenToHash) & 0x0000FFFF) << 32;
       // Make this a prefix upper bound by filling the lowest 32 bits.
       hash +=  0xFFFFFFFF;
       result->SetAsInt64(hash);
     } else {
       return NS_ERROR_FAILURE;
     }
 
     result.forget(_result);
--- a/toolkit/components/places/tests/head_common.js
+++ b/toolkit/components/places/tests/head_common.js
@@ -1,17 +1,17 @@
 /* -*- indent-tabs-mode: nil; js-indent-level: 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/. */
 
 // It is expected that the test files importing this file define Cu etc.
 /* global Cu, Ci, Cc, Cr */
 
-const CURRENT_SCHEMA_VERSION = 39;
+const CURRENT_SCHEMA_VERSION = 40;
 const FIRST_UPGRADABLE_SCHEMA_VERSION = 11;
 
 const NS_APP_USER_PROFILE_50_DIR = "ProfD";
 const NS_APP_PROFILE_DIR_STARTUP = "ProfDS";
 
 // Shortcuts to transitions type.
 const TRANSITION_LINK = Ci.nsINavHistoryService.TRANSITION_LINK;
 const TRANSITION_TYPED = Ci.nsINavHistoryService.TRANSITION_TYPED;
new file mode 100644
index 0000000000000000000000000000000000000000..3eff303261b52cc7cc63660fa20822920ff5d6fa
GIT binary patch
literal 1146880
zc%1Fsdz4)FT^R5?kDZ-aYxTrlJF(+Y9K}{FtyZtdGB}Pbtsa*3uq-K3iqA5;b9Z;7
z*}3bPSxGBfx>le)lsc!-!#M=XBfz1QhNL-%(&li|&_mPGwB(RN0*8<jQov3Eh0tKf
zoRB|yXJ((;T?G!MCh_NUcJFU~-~0VN?(aV4O8@LrPd-s;hQ-mSK2d5GcLvV~>2&bU
zVlfDUZ1Q_wFz=q3*sN6Y`#^AO*`Po5?%r$7;LR658(cql?YZZ!UfcQX`<^>=wSRhW
z`j4($oL+V1uFH>J{;f;5H$U5aZ}Ux!|Ij#E|6KjMpZViw9-sX9<U6AO5j|1+NbTW?
zU!K@dy^(YR000000000000000000000000000000004h4ZoK8q-F;6!n7VPkQY(j7
zCZelDm1a267%J6jQKS92)NIx(!&A+0xs3bvpBmhEda!ur_>m{i3>J?ZKQMT%_|1DM
zo;ZGUR`G#WWvEi#Qf$?S<{BiS%{SI;?Cv{sZ|cV2+$1_(PgYAK;nEqlcfNV0xvkiA
zc3LwNYG<r8qkD_pedjl&ZXBB%^kO)DIjWaudY+6L&2p((8k(wAo|y`lWNln&cHg|4
z*=f#ZE}UsAf2h@9^NsYq-F-*yPu<u!H}-H8U7RS@FE)n8rYhx|XEwLDxYE>CZa+Jv
z`92<KrEGrgP2GKi$sF!lW)8_L!&12%mY43kcV-654ZXP8G6S~~_O%i=-&l7~ci&UV
z@Vl28zIC}(OO574RIZFxmYc<!ZZV5xTQ4)2(TiJ(t-ND1d7H1@-QD--3TI`qR1a&-
zr91Aq#Y7ggS!Vdo-u7itX;z}z=4am6-S?fz@VzUn$kOoL-((eTb>z+I$#C<H%p1D<
z_HSEw$m5kpGpbKtswA`OoYCcXy>ZFdE3}*)f6?yZ1MRY%mCWL<ThC&&9!)I2>kZ#z
z7IQ6Em_=*<P`k4EM&F&?eaDhnJi5Xx+IRBG3v$;tnabkkE6iv9X|Z5^F7+kLvoUq!
z_PK%EY0Ez<I=k*%={d1N%h~C4cF#N^uHTV7**7jcEi<iKcTIbKi&mqvvv0{Vtk~%0
zL0cI^3yyo@_U^t%lJN^Sk3U)uN5b03^iA<QRvLOy{>`J#?%aIgJG%S!EH_+xN+Z!!
ztvMgOeWkJHlW!iVb7bvZo5Ky=eY=yfQa6t^o_tB%6#I^qhMLR0d8B%Hsl9Xa#QGIh
zaH?J%8ZR}*Z;EeNX{bf{HxD<vbMw)4xxP)CQvaw~8m@+oXR66FXsFRFHMcMPynbek
z)B7HKVz9Vy&jZcj>Xu6R%9d7b^Lrjz+uirzgQ@SkzunzU?<6->*DdOF$@@#OSScq5
zb$am7;Hl!tQ%8>NJ9WNzbnyI^;>?@P+|J`CP8W}#dE$v>UMyyFwiHLAS~Gce7oRwB
z{LtBbr}iJ-mjp+vrLo3bKL-X6?mP3u>EghaVt8e;QZKb0@yqRPJ%^Wz&wW)cw{zjw
z*3$i(-*f+(?!J5PO?}@zb4xe3XzdScmn_#eU8vb7)3?`3-B{b(-M4dR>c*i(D>Z*K
zjb%csmtDOD3Ab9uT4^FI&Md_PJ9liJeMHYL=jOrHxxVu|Q$hPyo4GwoQ_ZMdA6jO#
zq3z2A*PL9HYu!EP7u}0t^1QE&++6Kl_Kuv{`9N#JTaw!58*l3AZr$ED;<>e&ea&6?
z`L-piGygKY(y|oyojHBt$nm7*vBBe~w-jeu6i*MHJ3X^NORvBMZ`AF?&3kUk^&Q=G
ztCgF3f#1Hcw(7<k^U0%sPwK{*xg%TfQX5voW>{V}SXgqbOHx_~-TF4|9Lu6hp>^S&
zN=CaBF1@Q3T%$({xxT0O-0HBF4B9!qCE=d;jCFVS-G6`TANMXj&_$K}$_I9<i+kZM
zn%w6Xm)vok2S(@BchPyQEWGQJjw;P+xcI3tbG8;;0Haa09M*^0!?xCUnTNshkAN-n
z=VVK<F<l#ZD*4KpYTV*9bkg>Zmuh3-{?>PRSYJ7N`{o;4y4sK6_soBLwZ4%Xb02a`
zR=6F$)#|nqI+xMhfV20;>`Tmo6-?ITR+m+>>h*B6a;0<YY|rKT2JgMqHP)V8=elZt
z?7s2#On2Ybt*Q6iJOBM$o1ALSywToV&o2FjUa+@y*thtGX{Ro{92V@GYJ{Das`+DI
z_+(k|O5N^d^X5mhxxS~i-s)Hv&a89D3nN`Y5aiqcLvtwI-M4L9>OGIlpW}tE^GgDm
zrRRL{>;KB<e*PaS3vQbw55)PG=bK}T@61NnXe_wjHh=G)RCnLTjj4aKckW0!FL(2w
z(o5z(`}$X0dDh9B;o_TknfrS7Wp#0M!OQY;U+d$Q<Q`w<En&fRvG@j9F5~8#W-e*#
z_61ot{i|dydC?<eG^&S{vD!)#UU<3Aye!`$De1Z#Hb&}|$@W9BGeUB=UaEwbhbj}L
zv9R?%-nnsmlk2eOxf?<JGx7fGe|r6gu7Ah1FI=l%D?Im!BnSWi000000000000000
z00000000000000000000{Qq^ZXHD>AuqI!~=Yvg!ToAPXEd0Z*zrOy++uz!V>di;C
z?|SP*>B_0FF;#6g9@#$7KRA4Ls&*_oFtB&990V`#I`jBvw!EXTCfK*MpLPci-PFFZ
zcl5~czFp&!R}R%$?ce_Uzwjet`8C1*%{vSELOQpp&=myZ&E{m|;ceTJerjQ}e<HeC
zsa8w<QGION$#$rCtP>imNByO0wQ@C@=x>I#QgyOF|Hh!}{N<NE_VoCk6DKboeyVi#
zVB@h153WCc?e@1+yVnLcx`X@j`FuK9G}1(6c(~H+ABiTmJ=zHCm%{oZmHNoSk>5Hp
zUaHl?>LZ(W?5tJB#+%jYiD;z1*=jh^AG{Dw?Pwlr>>fIE>cYMU*FSpx?zip8tqJZA
zf|<dRWho6uQ_Y7*>ZQhb*a%*@RDI_BV}qCKmq$h~1i?@J+y{%l_Tgu{k{R9}>|8p-
zQn?(}8jIE<tZhB>)V9$|Jsgd$bP~4BOl@m3Y&66A)@Bq{8`~BxQ==A@%cW$(dq)Q9
zj~(7K6}{`?*$3CZFmQPATy{-xB-q;-JGEf!a(F4MMw4NE(eMj<t%s9QHOVR`9gjEm
z9X)*b>dE5=PnXjVuK(E|9{<qU%$nd(uxDw{!&76O4p-{9U5-r+C;dKoVdChnsgcuL
zkCt{O{eJq-FFgHpdQEU5cy#G%4OgSF{+YE{vG3_>b9}5)>mQ4%t^QA*Jb0;c{OH~T
zdxj4@xc)=mxbZvRomvwN1zVSPfBEv|WzNJ%RBP5N!&A+0(J-y#;Dz$ZYPDJ)xbXP&
z)$<RoAN{TOKiiw!f~ok=g5(DP00000000000000000000000000000000000003Se
z)}^|Gd@7g9=Yy{EmtXqW)8pyhB%F%B79>9a000000000000000000000000000000
z00000008hhlTT$+8w&Y}=xR?=OU17S$qxVk000000000000000000000000000000
z000000KDGhv#AY*{6uuMH>q^T?+oHUjXx28Abug9jK4dn0ssI2000000000000000
z0000000000000000002M-^v@hbHVm>A(*U|YGJc~BDz|sR!jX+eJuaR^|@TIF`W-4
zD#OE-X8%Yu5xnq*u2z0ND3!}mt+6mac;TLGF4&XoD~FfDYBU+v7w^71lM8kyyN9R7
zI?+XYi|JhONNaC38tboB#>Sh~>BSivQn}#1)^rvIdy-@5j>|#(<@h(^Uy6S;{(<<}
zqzV84000000000000000000000000000000000000RPY3k=dS_td?qFvwtGGTB%k`
z{ZW0adv)f%!h-th%*ND2Wq7#K>>r6Ha(89+q{`u?uo_K<^@Z)ScV>2{hNs3lfdxA<
zcV`|+4OgSF{#s>hyjh)IxHH|FM5$bkYK?{AuHIyR>!1Bl5dU`kBk{TTt=GSF{oh=l
zyng?+Kfd-e*Un$N{khLP_s^eu^0_;n{alg+000000000000000000000000000000
z000000094>Y+1iLNCl}v@-dg&R48Q9LD%`qFLh-HX3Ha2rw{Los-@A!@YqA^RtJSt
zDt})mJJpju6^?|pX7O}stkG_e`stuuW<T-1!^g)@)_1@A%;`M`qx9ajotB$sS{5?L
zqDHfLw$i9H!*Z+1i?9CV^PMh!;?DB!$EWuXTxvdXWNaY)U2ED+Q=8jO^QnA3ce4Gr
z&x^-8e|Egx`jtD@cFKFcFu3n>^sXmIk3K#Wol75B-D$mdrge9|>p-P3GSz4lk9Yp4
zc`>RLkDS`yY29<KQ?7pJm8iV^METtGnd66cr{B@r>1FFoFS&enU$t7Cj;89xk$R~y
z9<~qv#h1VSkxu*c_lLXAO$<bPhofU-htiL&>a^cI)4nU8nH~Lf*l33J;^`==&h+t>
zpi_SBQ~R3(M<#Y`ePZZB>D}o=w{`k>bf%ANK0UJl#RIc{*1dQ<Y+jD)7dsvN!S{5^
zFAf|(vg6p`+xP7}bLr|}=AAw5jtV<xI?Ci{`+00?ta!R!8o3zOJ1u|xFFNJ#{@~92
z2aZh-o!xrk?7^LxeTB~1oIRX${$QmZjz(AJ*0l9k<2y}1`cS9*c>eI!gW-jN6XlWS
z)HCTr`Syi3cQomA`sO}Pg^gr=M`oAy!_Uv2=#$UXYL#6lw^yh49>_n`oy;Y<pf=4O
z&7tJVI8wV5RWHq4STFzhUv<h~eBZHMr$%=SJ+yuI#bYDs@5;5NP?$NXg+e-eEE=v<
z!{TF6baA3ozt|c0a~nP~TTZn154C+)SEu!ZGgovvbD}w(oPnDfulZDG><a@^wb7(;
zx!pKDknOa-eRk~h>@76cBq^IoY-q+KnRbi9w%PIK25MhB!=?J7*2&$}?1bB`yB<!r
zo98z#ZGJ4QO)YHOy6Y#B*zCw%52jje^ZDM{$=;k@kD}&mc5myk^89Q2R09A200000
z000000000000000000000000000000fY(}2YxDeTJP7~*00000000000000000000
z0000000000000000C<h{Cco+UPlNbt$p!!b000000000000000000000000000000
z000000KWYd(p|xZR4`GlW%H@7U|lL0zMAPtcBJF42JzRE4FCWD000000000000000
z00000000000000000000yl!-7Hl!xXwRBfzU19iYZxTtxe;y=1000000000000000
z000000000000000000000002+I<YpD*_4`yt`1!cr!PnKawFZFL^JURg7}N^$CCm8
z000000000000000000000000000000000000091>>&s+<-6yN1k+8Atsfkj(`B)TP
zOv;NJ)0yDN@J!`oJ(>*b%}SC~4jUu&%4D+=)%sFN+lgqnQVqAwW;RYmQL`uMI1~S3
z5PvcLcv1iW000000000000000000000000000000000000Kh+ZeVN^biD<Y|4Yv(P
z(Zz{U{bJ)(6gA(RIg*+UoUBKaVZB)i8{5iZW29c0Y*wOL`p(Sm)X8dTBndy2q%|L#
zNze4QI)45&J}>|P000000000000000000000000000000000000C<h{CcoMEfgt{J
zd@Vked;kCd00000000000000000000000000000000000fLnMV+Y_Wx8}q4DF1Ido
zDjW%G&C{i^Mm7_4oxl82_P>01w%nX)W!~4$T$?!-HJWEDjY=~t&!nb);?CLfLi)BO
z^+qQ*lipV@7l)(h;zX%_u~BSB#pZaWQ5=n`<*?qWHo`Cog%ibcr7>A8O^4-TRBJ_w
zkIl6@9YxjQQoS?Qi!Z<T+-!M!Dw$ScO+Hn~W^>!KFMh7?{jJ~L<k;3e_t_x+pYi+S
zW_&ch@A|9Pf9?8vuRnSH?rUGZ_Q7k<UOReib&>!80000000000000000000000000
z00000000000DKGEu{OKu=!S{t>d?h-`f^k+HyY1WE6s4IG}VkMwQ_i6XyMMG?K_Iw
zzjIA?)A_!I;YBHv)zU~f88w>aQnNHPRjWKR6}EdynijYBug>28op-ew%>5DfMU|ms
z@QHT%_J@i)iaQ2+v-dxGtNh7QJ*+inTkI-se|S~){-?g#2-Q-fIT4jBqm{6{V6^SG
zW$z!n{T6MLV+u><@`6S?d$RW*xmA;~sY-d_G9-<*KU~OeJJw#p@k*l^)u%628kJ^a
zNuaZstwB3YTPwITpWU{9!{4CoXg!*kZML)fZ`f$zSZ~W^H$KunwDvR_^Ph&M>eZp~
zQe(W6I#AsH)~@Wv-OJ~WC)dJk-j4gT*^PUa&uh<MB$}!<lf>O`%d9x~XgwSWYa`RM
zo$lI}&Tc%kd~WMRw>zFcu%z>?sqDu6%QskZx{`zIN$!-M_`N~=O8h7B7vj&v|2_WI
z_}|4pAOBbq1ONa40000000000000000000000000000000001h*TSkyE)@hX?>h7N
zXSVdrR^I;mzwjf4PUWY5?t{f&`*5x&)0KK~{ipx@!qb_~#}9qu#_yy%AAk0T$3K+q
ze0*Wx@L*RV(^YtI{pfGK|JhFP__f>LlJ9(c^!(j#>+VU0?THTu@n6TU#9xU&6aPy5
zGw~0^m*R6t5C8xG00000000000000000000000000000000000{+8Bc?n_NXBmK?F
z@Ni|Kzx$rdqp7ia)L*JrD_5h5{^@FSe5_LIAB(EP{pk&vt%ZeqFJHdg-<R3Bs6{iZ
zm8z5d`J3a7T2wBV`n%qc*}EuS4=1B)cquIRXYb1FS+uKNj!g~sXSy<LQvE&cZ6TWp
zQn{XF?mh8u2JtuISL3h7e-?i!{-gNw@$bc-PJ#dc0000000000000000000000000
z00000000000Pw9Tn<=F7*-Spw)7lhTo9@;o*V=ToHrduD)7qpnnS7xqY19+{Y7qZ*
z{I&Qm;xEU482^6!>G+fJe@%h_00000000000000000000000000000000000008i<
zA(u&~@^8$yir|IrPLb;rU7aG^DKecR-IYlfl3*sE>S=8XJxM1$@vjH*H{w_0uf~5C
ze<}W>`1A4a#h*@s000000000000000000000000000000000000002+tz}gvmkPSh
zUw-LhPmkxbnIP5E+7w!w?$##P+H|!x+14i0+N3j?pwN>v?up+O#9xU&AAd6bX#9cr
zU&cQWPsig)5C8xG00000000000000000000000000000000000{%+Q0Hl;3ApE>{7
z;HCQIk<kmeR-mzW^vLkOUE`Bi4%G^+z<6Wd(Zh$Yo;-f=bUE7!gi|}3#~Qnb&YZfi
zuX{~qQ=xpaTCLUxE<8Sc^?WPg$qN%lcTJ6)-g>mOGt&y3JbCa^<@nLP2lfmfNVfum
z!)K>z$D#uRdk4!st-#)qf%;>I_e@3ax_Gv$71(p)<i*2JmChb)Ja!@9lT0=he>F&c
z000000000000000000000000000000000000002sb)+|&$`$fK*ZIpYeeCJ+o+Ofr
zzY!!q000000000000000000000000000000000000002+x|GS}3q47hieC<r9{>OV
z00000000000000000000000000000000000cwM<IlPd&W=P$qXv8Ts-lKT4i`-1rE
z@n6ROJAN_#eEhrdr{Yh<|2h6>{LAr&;-8P-AOC3lFXDfeBmn>b000000000000000
z00000000000000000000z~7@>HdRRVtZNsAwe2Fmrd@QeZWp=UcG0z}U1V=-7nz=R
zkuG#)3rS`!8>CX1_3a{^?-aRC(bXxkog&jI(p^bWNcSY;uaBP(;=hhxiN6wmDgIya
zXXD?Fe<S{Q{2$|gAOG9<U&rr{-xvR2{QXH1000000000000000000000000000000
z000000002|J?YM-QmK4yO{eTy-6^xZoiekkQ>JgrWmAPzz9%X2seGYb%XGJEnYHbl
zbUNRTrq{Ql>2<kmA(hJJ+C`?TU8J*J*+SAV*(Mp;Y(8J;N#?Nr`Zt33tMMPlzZ3tr
z_*dc&#y=JRQ2f1dGY;dk@uB#kcys)Q__ibo000000000000000000000000000000
z00000004k*ORKY~T&gGNI)C}4>?hv0u3as(tEr#3b8WktZ&hD><(@CBX;-^D)z$A@
z-LB?3)%5rGwyRz3>dRmI)T(wh+o^tW;I?)()2aUM5B9XH=}z_I`9g2DkV|!HzxclH
z-fYmRz0{Q*Sih*2UX|1ev$eThFTVPd&u8XquiUXVKVN(K!a&!2?Q<JGl3P$)^Qml4
zvJUIxz94=%{$l*u_>=K}ihn8oSMiU=FT`<NkHh#}d^CPXyghzPk^}$%0000000000
z0000000000000000000000000!0XMbOfD64oxl82S9W0iTqX6>!MfSXi?9CV^K0iS
zuiUYA&3vWj-0Hc?%U}OU?|kJe!K(SnAAHYk^Oax!i=O$)M;|K8S3dlFe!lYKf7Lx#
z`P_z&<mM}DKGn6bl3iHIEUct&%j62Pm7e5a*I)n5ApT1H`S_FZN8=B~KNkPf_)0t$
zpN$9OUGaVKhB$rw|6Kn<k^}$%00000000000000000000000000000000000z_*IE
znN6uHQF;4`^110V#}DmZ-3m<AMl02@Jk-+F3N)jrI$Wx^1DST9G}aiJkzJG7RH#Q$
zb2iXQn23gxE;{vGI}p~UW)sq_K)CDN#6YxnI65|VsJ9g;?|yuG|G=f@6Gz4d*0usC
zpQ+U<yH0MePVYUCZv~DY*>P;}?fZ6~xpZ~#wpQTSu2Z8sh926!`{J>Y?pEN))#=0g
zqH1ZhF+8@u6*zqLV0dBRM0un+^-Q51I6i)|zWd#0PVYGwt!o7a_g#+O_2lT$$A_YG
zYg&Q*&4D8mJGMSCbfNU_Rjt6z{RfUs51rk5;_ShlJw3^yrQ^R0;;$zg0000000000
z00000000000000000000000000001Z{m5lgK`NW>N{T|JrxkhrHJ%Xw0000000000
z0000000000000000000000000006wkdXnF4{D(pOSMgWlKS@3S000000000000000
w00000000000000000000006+ZrS5Dhm0Fj{w#&7dOjkBlDCF9;OgjC40ogPS>i_@%
--- a/toolkit/components/places/tests/migration/xpcshell.ini
+++ b/toolkit/components/places/tests/migration/xpcshell.ini
@@ -20,16 +20,17 @@ support-files =
   places_v32.sqlite
   places_v33.sqlite
   places_v34.sqlite
   places_v35.sqlite
   places_v36.sqlite
   places_v37.sqlite
   places_v38.sqlite
   places_v39.sqlite
+  places_v40.sqlite
 
 [test_current_from_downgraded.js]
 [test_current_from_v6.js]
 [test_current_from_v11.js]
 [test_current_from_v19.js]
 [test_current_from_v24.js]
 [test_current_from_v25.js]
 [test_current_from_v26.js]
new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/unit/test_hash.js
@@ -0,0 +1,44 @@
+/* Any copyright is dedicated to the Public Domain.
+ * http://creativecommons.org/publicdomain/zero/1.0/ */
+
+add_task(async function() {
+  // Check particular unicode urls with insertion and selection APIs to ensure
+  // url hashes match properly.
+  const URLS = [
+    "http://президент.президент/президент/",
+    "https://www.аррӏе.com/аррӏе/",
+    "http://名がドメイン/",
+  ];
+
+  for (let url of URLS) {
+    await PlacesTestUtils.addVisits(url);
+    Assert.ok(await PlacesUtils.history.fetch(url),
+              "Found the added visit");
+    await PlacesUtils.bookmarks.insert({
+      url, parentGuid: PlacesUtils.bookmarks.unfiledGuid
+    });
+    Assert.ok(await PlacesUtils.bookmarks.fetch({ url }),
+              "Found the added bookmark");
+    let db = await PlacesUtils.promiseDBConnection();
+    let rows = await db.execute(
+      "SELECT id FROM moz_places WHERE url_hash = hash(:url) AND url = :url",
+      {url: new URL(url).href});
+    Assert.equal(rows.length, 1, "Matched the place from the database");
+    let id = rows[0].getResultByName("id");
+
+    // Now, suppose the urls has been inserted without proper parsing and retry.
+    // This should normally not happen through the API, but we have evidence
+    // it somehow happened.
+    await PlacesUtils.withConnectionWrapper("test_hash.js", async wdb => {
+      await wdb.execute(`
+        UPDATE moz_places SET url_hash = hash(:url), url = :url
+        WHERE id = :id
+      `, {url, id});
+      rows = await wdb.execute(
+        "SELECT id FROM moz_places WHERE url_hash = hash(:url) AND url = :url",
+        {url});
+      Assert.equal(rows.length, 1, "Matched the place from the database");
+    });
+
+  }
+});
--- a/toolkit/components/places/tests/unit/xpcshell.ini
+++ b/toolkit/components/places/tests/unit/xpcshell.ini
@@ -78,16 +78,17 @@ skip-if = (os == "win" && os_version == 
 [test_corrupt_telemetry.js]
 [test_crash_476292.js]
 [test_database_replaceOnStartup.js]
 [test_download_history.js]
 [test_frecency.js]
 [test_frecency_decay.js]
 [test_frecency_zero_updated.js]
 [test_getChildIndex.js]
+[test_hash.js]
 [test_history.js]
 [test_history_autocomplete_tags.js]
 [test_history_catobs.js]
 [test_history_clear.js]
 [test_history_notifications.js]
 [test_history_observer.js]
 [test_history_sidebar.js]
 [test_hosts_triggers.js]