author Marco Bonardo <mbonardo@mozilla.com>

Mon, 18 Sep 2017 10:31:20 +0200

changeset 669873 760c0899da9cd5bc5c640be030de20865a45ca98

parent 669017 82b2ae0b03ca1d99d1fe6a9944c450dba3b2bc97

child 733074 361a87981e75f124f548d69844c83b0f463600b0

push id 81452

push user mak77@bonardo.net

push date Mon, 25 Sep 2017 14:01:15 +0000

reviewers adw

bugs 1399879

milestone 58.0a1

toolkit/components/places/Database.cpp file | annotate | diff | comparison | revisions

toolkit/components/places/Database.h file | annotate | diff | comparison | revisions

toolkit/components/places/SQLFunctions.cpp file | annotate | diff | comparison | revisions

toolkit/components/places/tests/head_common.js file | annotate | diff | comparison | revisions

toolkit/components/places/tests/migration/places_v40.sqlite file | annotate | diff | comparison | revisions

toolkit/components/places/tests/migration/xpcshell.ini file | annotate | diff | comparison | revisions

toolkit/components/places/tests/unit/test_hash.js file | annotate | diff | comparison | revisions

toolkit/components/places/tests/unit/xpcshell.ini file | annotate | diff | comparison | revisions
--- 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.Equals(NS_LITERAL_CSTRING("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.Equals(NS_LITERAL_CSTRING("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;
--- 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]
author	Marco Bonardo <mbonardo@mozilla.com>
	Mon, 18 Sep 2017 10:31:20 +0200
changeset 669873	760c0899da9cd5bc5c640be030de20865a45ca98
parent 669017	82b2ae0b03ca1d99d1fe6a9944c450dba3b2bc97
child 733074	361a87981e75f124f548d69844c83b0f463600b0
push id	81452
push user	mak77@bonardo.net
push date	Mon, 25 Sep 2017 14:01:15 +0000
reviewers	adw
bugs	1399879
milestone	58.0a1
toolkit/components/places/Database.cpp		file \| annotate \| diff \| comparison \| revisions
toolkit/components/places/Database.h		file \| annotate \| diff \| comparison \| revisions
toolkit/components/places/SQLFunctions.cpp		file \| annotate \| diff \| comparison \| revisions
toolkit/components/places/tests/head_common.js		file \| annotate \| diff \| comparison \| revisions
toolkit/components/places/tests/migration/places_v40.sqlite		file \| annotate \| diff \| comparison \| revisions
toolkit/components/places/tests/migration/xpcshell.ini		file \| annotate \| diff \| comparison \| revisions
toolkit/components/places/tests/unit/test_hash.js		file \| annotate \| diff \| comparison \| revisions
toolkit/components/places/tests/unit/xpcshell.ini		file \| annotate \| diff \| comparison \| revisions