Bug 1258127 - Add migration logic for old synced bookmarks. r=rnewman,markh draft
authorKit Cambridge <kit@yakshaving.ninja>
Fri, 18 Nov 2016 14:00:56 -0800
changeset 441685 dec55de0673c191db0dbe8e3205d0c9cc639aa56
parent 441684 97fdac6ccb0d0326a3da7e42259dc6a961994ac3
child 537609 7c45044d1eea88275094a28bbdc9f5d1f1260408
push id36491
push userbmo:kcambridge@mozilla.com
push dateSun, 20 Nov 2016 18:09:12 +0000
reviewersrnewman, markh
bugs1258127
milestone53.0a1
Bug 1258127 - Add migration logic for old synced bookmarks. r=rnewman,markh MozReview-Commit-ID: Gye30bYZejy
browser/base/content/test/general/browser_aboutAccounts.js
services/sync/modules-testing/fakeservices.js
services/sync/modules/engines/bookmarks.js
services/sync/modules/util.js
services/sync/tests/unit/test_bookmark_tracker.js
toolkit/components/places/PlacesSyncUtils.jsm
toolkit/components/places/tests/unit/test_sync_utils.js
--- a/browser/base/content/test/general/browser_aboutAccounts.js
+++ b/browser/base/content/test/general/browser_aboutAccounts.js
@@ -324,19 +324,20 @@ var gTests = [
   teardown: function() {
     gBrowser.removeCurrentTab();
   },
   run: function* () {
     setPref("identity.fxaccounts.remote.signup.uri", "https://example.com/");
     yield setSignedInUser();
     let tab = yield promiseNewTabLoadEvent("about:accounts");
     // sign the user out - the tab should have action=signin
+    let loadPromise = promiseOneMessage(tab, "test:document:load");
     yield signOut();
     // wait for the new load.
-    yield promiseOneMessage(tab, "test:document:load");
+    yield loadPromise;
     is(tab.linkedBrowser.contentDocument.location.href, "about:accounts?action=signin");
   }
 },
 {
   desc: "Test entrypoint query string, no action, no user logged in",
   teardown: () => gBrowser.removeCurrentTab(),
   run: function* () {
     // When this loads with no user logged-in, we expect the "normal" URL
@@ -430,39 +431,38 @@ function promiseOneMessage(tab, messageN
 }
 
 function promiseNewTabLoadEvent(aUrl)
 {
   let tab = gBrowser.selectedTab = gBrowser.addTab(aUrl);
   let browser = tab.linkedBrowser;
   let mm = browser.messageManager;
 
-  // give it an e10s-friendly content script to help with our tests.
-  mm.loadFrameScript(CHROME_BASE + "content_aboutAccounts.js", true);
+  // give it an e10s-friendly content script to help with our tests,
   // and wait for it to tell us about the load.
-  return promiseOneMessage(tab, "test:document:load").then(
-    () => tab
-  );
+  let promise = promiseOneMessage(tab, "test:document:load");
+  mm.loadFrameScript(CHROME_BASE + "content_aboutAccounts.js", true);
+  return promise.then(() => tab);
 }
 
 // Returns a promise which is resolved with the iframe's URL after a new
 // tab is created and the iframe in that tab loads.
 function promiseNewTabWithIframeLoadEvent(aUrl) {
   let deferred = Promise.defer();
   let tab = gBrowser.selectedTab = gBrowser.addTab(aUrl);
   let browser = tab.linkedBrowser;
   let mm = browser.messageManager;
 
-  // give it an e10s-friendly content script to help with our tests.
-  mm.loadFrameScript(CHROME_BASE + "content_aboutAccounts.js", true);
+  // give it an e10s-friendly content script to help with our tests,
   // and wait for it to tell us about the iframe load.
   mm.addMessageListener("test:iframe:load", function onFrameLoad(message) {
     mm.removeMessageListener("test:iframe:load", onFrameLoad);
     deferred.resolve([tab, message.data.url]);
   });
+  mm.loadFrameScript(CHROME_BASE + "content_aboutAccounts.js", true);
   return deferred.promise;
 }
 
 function checkVisibilities(tab, data) {
   let ids = Object.keys(data);
   let mm = tab.linkedBrowser.messageManager;
   let deferred = Promise.defer();
   mm.addMessageListener("test:check-visibilities-response", function onResponse(message) {
--- a/services/sync/modules-testing/fakeservices.js
+++ b/services/sync/modules-testing/fakeservices.js
@@ -34,26 +34,32 @@ this.FakeFilesystemService = function Fa
     if (!Utils[origName]) {
       Utils[origName] = Utils[name];
     }
   }
 
   Utils.jsonSave = function jsonSave(filePath, that, obj, callback) {
     let json = typeof obj == "function" ? obj.call(that) : obj;
     self.fakeContents["weave/" + filePath + ".json"] = JSON.stringify(json);
-    callback.call(that);
+    if (callback) {
+      callback.call(that);
+    }
+    return Promise.resolve();
   };
 
   Utils.jsonLoad = function jsonLoad(filePath, that, cb) {
     let obj;
     let json = self.fakeContents["weave/" + filePath + ".json"];
     if (json) {
       obj = JSON.parse(json);
     }
-    cb.call(that, obj);
+    if (cb) {
+      cb.call(that, obj);
+    }
+    return Promise.resolve(obj);
   };
 
   Utils.jsonMove = function jsonMove(aFrom, aTo, that) {
     const fromPath = "weave/" + aFrom + ".json";
     self.fakeContents["weave/" + aTo + ".json"] = self.fakeContents[fromPath];
     delete self.fakeContents[fromPath];
     return Promise.resolve();
   };
--- a/services/sync/modules/engines/bookmarks.js
+++ b/services/sync/modules/engines/bookmarks.js
@@ -851,16 +851,17 @@ BookmarksStore.prototype = {
 // The bookmarks tracker is a special flower. Instead of listening for changes
 // via observer notifications, it queries Places for the set of items that have
 // changed since the last sync. Because it's a "pull-based" tracker, it ignores
 // all concepts of "add a changed ID." However, it still registers an observer
 // to bump the score, so that changed bookmarks are synced immediately.
 function BookmarksTracker(name, engine) {
   this._batchDepth = 0;
   this._batchSawScoreIncrement = false;
+  this._migratedOldEntries = false;
   Tracker.call(this, name, engine);
 
   delete this.changedIDs; // so our getter/setter takes effect.
 
   Svc.Obs.add("places-shutdown", this);
 }
 BookmarksTracker.prototype = {
   __proto__: Tracker.prototype,
@@ -928,20 +929,71 @@ BookmarksTracker.prototype = {
 
   set changedIDs(obj) {
     // let engine init set it to nothing.
     if (Object.keys(obj).length != 0) {
       throw new Error("Don't set initial changed bookmark IDs");
     }
   },
 
+  // Migrates tracker entries from the old JSON-based tracker to Places. This
+  // is called the first time we start tracking changes.
+  _migrateOldEntries: Task.async(function* () {
+    let existingIDs = yield Utils.jsonLoad("changes/" + this.file, this);
+    if (existingIDs === null) {
+      // If the tracker file doesn't exist, we don't need to migrate, even if
+      // the engine is enabled. It's possible we're upgrading before the first
+      // sync. In the worst case, getting this wrong has the same effect as a
+      // restore: we'll reupload everything to the server.
+      this._log.debug("migrateOldEntries: Missing bookmarks tracker file; " +
+                      "skipping migration");
+      return null;
+    }
+
+    if (!this._needsMigration()) {
+      // We have a tracker file, but bookmark syncing is disabled, or this is
+      // the first sync. It's likely the tracker file is stale. Remove it and
+      // skip migration.
+      this._log.debug("migrateOldEntries: Bookmarks engine disabled or " +
+                      "first sync; skipping migration");
+      return Utils.jsonRemove("changes/" + this.file, this);
+    }
+
+    // At this point, we know the engine is enabled, we have a tracker file
+    // (though it may be empty), and we've synced before.
+    this._log.debug("migrateOldEntries: Migrating old tracker entries");
+    let entries = [];
+    for (let syncID in existingIDs) {
+      let change = existingIDs[syncID];
+      // Allow raw timestamps for backward-compatibility with changed IDs
+      // persisted before bug 1274496.
+      let timestamp = typeof change == "number" ? change : change.modified;
+      entries.push({
+        syncId: syncID,
+        modified: timestamp * 1000,
+      });
+    }
+    yield PlacesSyncUtils.bookmarks.migrateOldTrackerEntries(entries);
+    return Utils.jsonRemove("changes/" + this.file, this);
+  }),
+
+  _needsMigration() {
+    return this.engine && this.engineIsEnabled() && this.engine.lastSync > 0;
+  },
+
   observe: function observe(subject, topic, data) {
     Tracker.prototype.observe.call(this, subject, topic, data);
 
     switch (topic) {
+      case "weave:engine:start-tracking":
+        if (!this._migratedOldEntries) {
+          this._migratedOldEntries = true;
+          Async.promiseSpinningly(this._migrateOldEntries());
+        }
+        break;
       case "bookmarks-restore-begin":
         this._log.debug("Ignoring changes from importing bookmarks.");
         break;
       case "bookmarks-restore-success":
         this._log.debug("Tracking all items on successful import.");
 
         this._log.debug("Restore succeeded: wiping server and other clients.");
         this.engine.service.resetClient([this.name]);
--- a/services/sync/modules/util.js
+++ b/services/sync/modules/util.js
@@ -362,17 +362,20 @@ this.Utils = {
         json = null;
       } else {
         if (that._log) {
           that._log.debug("Failed to load json", e);
         }
       }
     }
 
-    callback.call(that, json);
+    if (callback) {
+      callback.call(that, json);
+    }
+    return json;
   }),
 
   /**
    * Save a json-able object to disk in the profile directory.
    *
    * @param filePath
    *        JSON file path save to <filePath>.json
    * @param that
--- a/services/sync/tests/unit/test_bookmark_tracker.js
+++ b/services/sync/tests/unit/test_bookmark_tracker.js
@@ -8,16 +8,17 @@ const {
   fetchGuidsWithAnno,
 } = Cu.import("resource://gre/modules/PlacesSyncUtils.jsm");
 Cu.import("resource://gre/modules/Task.jsm");
 Cu.import("resource://services-sync/constants.js");
 Cu.import("resource://services-sync/engines/bookmarks.js");
 Cu.import("resource://services-sync/engines.js");
 Cu.import("resource://services-sync/service.js");
 Cu.import("resource://services-sync/util.js");
+Cu.import("resource://gre/modules/osfile.jsm");
 Cu.import("resource://gre/modules/Task.jsm");
 Cu.import("resource://testing-common/PlacesTestUtils.jsm");
 Cu.import("resource:///modules/PlacesUIUtils.jsm");
 
 Service.engineManager.register(BookmarksEngine);
 var engine = Service.engineManager.get("bookmarks");
 var store  = engine._store;
 var tracker = engine._tracker;
@@ -35,16 +36,17 @@ function* verifyTrackerEmpty() {
 }
 
 function* resetTracker() {
   yield PlacesTestUtils.markBookmarksAsSynced();
   tracker.resetScore();
 }
 
 function* cleanup() {
+  engine.lastSync = 0;
   store.wipe();
   yield resetTracker();
   yield stopTracking();
 }
 
 // startTracking is a signal that the test wants to notice things that happen
 // after this is called (ie, things already tracked should be discarded.)
 function* startTracking() {
@@ -121,16 +123,56 @@ var populateTree = Task.async(function* 
         itemId, BookmarkAnnos.EXCLUDEBACKUP_ANNO, "Don't back this up", 0,
         PlacesUtils.annotations.EXPIRE_NEVER);
     }
     guids[item.title] = yield PlacesUtils.promiseItemGuid(itemId);
   }
   return guids;
 });
 
+function* insertBookmarksToMigrate() {
+  let mozBmk = yield PlacesUtils.bookmarks.insert({
+    guid: "0gtWTOgYcoJD",
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    url: "https://mozilla.org",
+  });
+  let fxBmk = yield PlacesUtils.bookmarks.insert({
+    guid: "0dbpnMdxKxfg",
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    url: "http://getfirefox.com",
+  });
+  let tbBmk = yield PlacesUtils.bookmarks.insert({
+    guid: "r5ouWdPB3l28",
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    url: "http://getthunderbird.com",
+  });
+  let bzBmk = yield PlacesUtils.bookmarks.insert({
+    guid: "YK5Bdq5MIqL6",
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    url: "https://bugzilla.mozilla.org",
+  });
+  let exampleBmk = yield PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    url: "https://example.com",
+  });
+
+  yield PlacesTestUtils.setBookmarkSyncFields({
+    guid: fxBmk.guid,
+    syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+  }, {
+    guid: tbBmk.guid,
+    syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.UNKNOWN,
+  }, {
+    guid: exampleBmk.guid,
+    syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+  });
+
+  yield PlacesUtils.bookmarks.remove(exampleBmk.guid);
+}
+
 add_task(function* test_tracking() {
   _("Test starting and stopping the tracker");
 
   // Remove existing tracking information for roots.
   yield startTracking();
 
   let folder = PlacesUtils.bookmarks.createFolder(
     PlacesUtils.bookmarks.bookmarksMenuFolder,
@@ -1586,16 +1628,183 @@ add_task(function* test_mobile_query() {
     yield verifyTrackedItems([mozBmk.guid, "mobile"]);
     do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 5);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
+add_task(function* test_skip_migration() {
+  yield* insertBookmarksToMigrate();
+
+  let originalTombstones = yield PlacesTestUtils.fetchSyncTombstones();
+  let originalFields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+    "0gtWTOgYcoJD", "0dbpnMdxKxfg", "r5ouWdPB3l28", "YK5Bdq5MIqL6");
+
+  let filePath = OS.Path.join(OS.Constants.Path.profileDir, "weave", "changes",
+    "bookmarks.json");
+
+  _("No tracker file");
+  {
+    yield Utils.jsonRemove("changes/bookmarks", tracker);
+    ok(!(yield OS.File.exists(filePath)), "Tracker file should not exist");
+
+    yield tracker._migrateOldEntries();
+
+    let fields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+      "0gtWTOgYcoJD", "0dbpnMdxKxfg", "r5ouWdPB3l28", "YK5Bdq5MIqL6");
+    deepEqual(fields, originalFields,
+      "Sync fields should not change if tracker file is missing");
+    let tombstones = yield PlacesTestUtils.fetchSyncTombstones();
+    deepEqual(tombstones, originalTombstones,
+      "Tombstones should not change if tracker file is missing");
+  }
+
+  _("Existing tracker file; engine disabled");
+  {
+    yield Utils.jsonSave("changes/bookmarks", tracker, {});
+    ok(yield OS.File.exists(filePath),
+      "Tracker file should exist before disabled engine migration");
+
+    engine.disabled = true;
+    yield tracker._migrateOldEntries();
+    engine.disabled = false;
+
+    let fields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+      "0gtWTOgYcoJD", "0dbpnMdxKxfg", "r5ouWdPB3l28", "YK5Bdq5MIqL6");
+    deepEqual(fields, originalFields,
+      "Sync fields should not change on disabled engine migration");
+    let tombstones = yield PlacesTestUtils.fetchSyncTombstones();
+    deepEqual(tombstones, originalTombstones,
+      "Tombstones should not change if tracker file is missing");
+
+    ok(!(yield OS.File.exists(filePath)),
+      "Tracker file should be deleted after disabled engine migration");
+  }
+
+  _("Existing tracker file; first sync");
+  {
+    yield Utils.jsonSave("changes/bookmarks", tracker, {});
+    ok(yield OS.File.exists(filePath),
+      "Tracker file should exist before first sync migration");
+
+    engine.lastSync = 0;
+    yield tracker._migrateOldEntries();
+
+    let fields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+      "0gtWTOgYcoJD", "0dbpnMdxKxfg", "r5ouWdPB3l28", "YK5Bdq5MIqL6");
+    deepEqual(fields, originalFields,
+      "Sync fields should not change on first sync migration");
+    let tombstones = yield PlacesTestUtils.fetchSyncTombstones();
+    deepEqual(tombstones, originalTombstones,
+      "Tombstones should not change if tracker file is missing");
+
+    ok(!(yield OS.File.exists(filePath)),
+      "Tracker file should be deleted after first sync migration");
+  }
+
+  yield* cleanup();
+});
+
+add_task(function* test_migrate_empty_tracker() {
+  _("Migration with empty tracker file");
+  yield* insertBookmarksToMigrate();
+
+  yield Utils.jsonSave("changes/bookmarks", tracker, {});
+
+  engine.lastSync = Date.now() / 1000;
+  yield tracker._migrateOldEntries();
+
+  let fields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+    "0gtWTOgYcoJD", "0dbpnMdxKxfg", "r5ouWdPB3l28", "YK5Bdq5MIqL6");
+  for (let field of fields) {
+    equal(field.syncStatus, PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+      `Sync status of migrated bookmark ${field.guid} should be NORMAL`);
+    strictEqual(field.syncChangeCounter, 0,
+      `Change counter of migrated bookmark ${field.guid} should be 0`);
+  }
+
+  let tombstones = yield PlacesTestUtils.fetchSyncTombstones();
+  deepEqual(tombstones, [], "Migration should delete old tombstones");
+
+  let filePath = OS.Path.join(OS.Constants.Path.profileDir, "weave", "changes",
+    "bookmarks.json");
+  ok(!(yield OS.File.exists(filePath)),
+    "Tracker file should be deleted after empty tracker migration");
+
+  yield* cleanup();
+});
+
+add_task(function* test_migrate_existing_tracker() {
+  _("Migration with existing tracker entries");
+  yield* insertBookmarksToMigrate();
+
+  let mozBmk = yield PlacesUtils.bookmarks.fetch("0gtWTOgYcoJD");
+  let fxBmk = yield PlacesUtils.bookmarks.fetch("0dbpnMdxKxfg");
+  let mozChangeTime = Math.floor(mozBmk.lastModified / 1000) - 60;
+  let fxChangeTime = Math.floor(fxBmk.lastModified / 1000) + 60;
+  yield Utils.jsonSave("changes/bookmarks", tracker, {
+    "0gtWTOgYcoJD": mozChangeTime,
+    "0dbpnMdxKxfg": {
+      modified: fxChangeTime,
+      deleted: false,
+    },
+    "3kdIPWHs9hHC": {
+      modified: 1479494951,
+      deleted: true,
+    },
+    "l7DlMy2lL1jL": 1479496460,
+  });
+
+  engine.lastSync = Date.now() / 1000;
+  yield tracker._migrateOldEntries();
+
+  let changedFields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+    "0gtWTOgYcoJD", "0dbpnMdxKxfg");
+  for (let field of changedFields) {
+    if (field.guid == "0gtWTOgYcoJD") {
+      ok(field.lastModified.getTime(), mozBmk.lastModified.getTime(),
+        `Modified time for ${field.guid} should not be reset to older change time`);
+    } else if (field.guid == "0dbpnMdxKxfg") {
+      equal(field.lastModified.getTime(), fxChangeTime * 1000,
+        `Modified time for ${field.guid} should be updated to newer change time`);
+    }
+    equal(field.syncStatus, PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+      `Sync status of migrated bookmark ${field.guid} should be NORMAL`);
+    ok(field.syncChangeCounter > 0,
+      `Change counter of migrated bookmark ${field.guid} should be > 0`);
+  }
+
+  let unchangedFields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+    "r5ouWdPB3l28", "YK5Bdq5MIqL6");
+  for (let field of unchangedFields) {
+    equal(field.syncStatus, PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+      `Sync status of unchanged bookmark ${field.guid} should be NORMAL`);
+    strictEqual(field.syncChangeCounter, 0,
+      `Change counter of unchanged bookmark ${field.guid} should be 0`);
+  }
+
+  let tombstones = yield PlacesTestUtils.fetchSyncTombstones();
+  yield deepEqual(tombstones, [{
+    guid: "3kdIPWHs9hHC",
+    dateRemoved: new Date(1479494951 * 1000),
+  }, {
+    guid: "l7DlMy2lL1jL",
+    dateRemoved: new Date(1479496460 * 1000),
+  }], "Should write tombstones for deleted tracked items");
+
+  let filePath = OS.Path.join(OS.Constants.Path.profileDir, "weave", "changes",
+    "bookmarks.json");
+  ok(!(yield OS.File.exists(filePath)),
+    "Tracker file should be deleted after existing tracker migration");
+
+  yield* cleanup();
+});
+
 function run_test() {
   initTestLogging("Trace");
 
   Log.repository.getLogger("Sync.Engine.Bookmarks").level = Log.Level.Trace;
   Log.repository.getLogger("Sync.Store.Bookmarks").level = Log.Level.Trace;
   Log.repository.getLogger("Sync.Tracker.Bookmarks").level = Log.Level.Trace;
 
   run_next_test();
--- a/toolkit/components/places/PlacesSyncUtils.jsm
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -106,16 +106,108 @@ const BookmarkSyncUtils = PlacesSyncUtil
     let db = yield PlacesUtils.promiseDBConnection();
     let childGuids = yield fetchChildGuids(db, parentGuid);
     return childGuids.map(guid =>
       BookmarkSyncUtils.guidToSyncId(guid)
     );
   }),
 
   /**
+   * Migrates an array of `{ syncId, modified }` tuples from the old JSON-based
+   * tracker to the new sync change counter. `modified` is when the change was
+   * added to the old tracker, in milliseconds.
+   *
+   * Sync calls this method before the first bookmark sync after the Places
+   * schema migration.
+   */
+  migrateOldTrackerEntries(entries) {
+    return PlacesUtils.withConnectionWrapper(
+      "BookmarkSyncUtils: migrateOldTrackerEntries", function(db) {
+        return db.executeTransaction(function* () {
+          // Mark all existing bookmarks as synced, and clear their change
+          // counters to avoid a full upload on the next sync. Note that
+          // this means we'll miss changes made between startup and the first
+          // post-migration sync, as well as changes made on a new release
+          // channel that weren't synced before the user downgraded. This is
+          // unfortunate, but no worse than the behavior of the old tracker.
+          //
+          // We also likely have bookmarks that don't exist on the server,
+          // because the old tracker missed them. We'll eventually fix the
+          // server once we decide on a repair strategy.
+          yield db.executeCached(`
+            WITH RECURSIVE
+            syncedItems(id) AS (
+              SELECT b.id FROM moz_bookmarks b
+              WHERE b.guid IN ('menu________', 'toolbar_____', 'unfiled_____',
+                               'mobile______')
+              UNION ALL
+              SELECT b.id FROM moz_bookmarks b
+              JOIN syncedItems s ON b.parent = s.id
+            )
+            UPDATE moz_bookmarks SET
+              syncStatus = :syncStatus,
+              syncChangeCounter = 0
+            WHERE id IN syncedItems`,
+            { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL });
+
+          yield db.executeCached(`DELETE FROM moz_bookmarks_deleted`);
+
+          yield db.executeCached(`CREATE TEMP TABLE moz_bookmarks_tracked (
+            guid TEXT PRIMARY KEY,
+            time INTEGER
+          )`);
+
+          try {
+            for (let { syncId, modified } of entries) {
+              let guid = BookmarkSyncUtils.syncIdToGuid(syncId);
+              if (!PlacesUtils.isValidGuid(guid)) {
+                BookmarkSyncLog.warn(`migrateOldTrackerEntries: Ignoring ` +
+                                     `change for invalid item ${guid}`);
+                continue;
+              }
+              let time = PlacesUtils.toPRTime(Number.isFinite(modified) ?
+                                              modified : Date.now());
+              yield db.executeCached(`
+                INSERT OR IGNORE INTO moz_bookmarks_tracked (guid, time)
+                VALUES (:guid, :time)`,
+                { guid, time });
+            }
+
+            // Bump the change counter for existing tracked items.
+            yield db.executeCached(`
+              INSERT OR REPLACE INTO moz_bookmarks (id, fk, type, parent,
+                                                    position, title,
+                                                    dateAdded, lastModified,
+                                                    guid, syncChangeCounter,
+                                                    syncStatus)
+              SELECT b.id, b.fk, b.type, b.parent, b.position, b.title,
+                     b.dateAdded, MAX(b.lastModified, t.time), b.guid,
+                     b.syncChangeCounter + 1, b.syncStatus
+              FROM moz_bookmarks b
+              JOIN moz_bookmarks_tracked t ON b.guid = t.guid`);
+
+            // Insert tombstones for nonexistent tracked items, using the most
+            // recent deletion date for more accurate reconciliation. We assume
+            // the tracked item belongs to a synced root.
+            yield db.executeCached(`
+              INSERT OR REPLACE INTO moz_bookmarks_deleted (guid, dateRemoved)
+              SELECT t.guid, MAX(IFNULL((SELECT dateRemoved FROM moz_bookmarks_deleted
+                                         WHERE guid = t.guid), 0), t.time)
+              FROM moz_bookmarks_tracked t
+              LEFT JOIN moz_bookmarks b ON t.guid = b.guid
+              WHERE b.guid IS NULL`);
+          } finally {
+            yield db.executeCached(`DROP TABLE moz_bookmarks_tracked`);
+          }
+        });
+      }
+    );
+  },
+
+  /**
    * Reorders a folder's children, based on their order in the array of sync
    * IDs.
    *
    * Sync uses this method to reorder all synced children after applying all
    * incoming records.
    *
    */
   order: Task.async(function* (parentSyncId, childSyncIds) {
--- a/toolkit/components/places/tests/unit/test_sync_utils.js
+++ b/toolkit/components/places/tests/unit/test_sync_utils.js
@@ -2311,8 +2311,74 @@ add_task(function* test_remove_partial()
     // greatGrandChildNextSiblingBmk]`.
     greatGrandChildPrevSiblingBmk.syncId,
     greatGrandChildNextSiblingBmk.syncId,
   ], "Should move descendants to closest living ancestor");
 
   yield PlacesUtils.bookmarks.eraseEverything();
   yield PlacesSyncUtils.bookmarks.reset();
 });
+
+add_task(function* test_migrateOldTrackerEntries() {
+  let unknownBmk = yield PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    url: "http://getfirefox.com",
+    title: "Get Firefox!",
+  });
+  let newBmk = yield PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    url: "http://getthunderbird.com",
+    title: "Get Thunderbird!",
+  });
+  let normalBmk = yield PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    url: "https://mozilla.org",
+    title: "Mozilla",
+  });
+
+  yield PlacesTestUtils.setBookmarkSyncFields({
+    guid: unknownBmk.guid,
+    syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.UNKNOWN,
+    syncChangeCounter: 0,
+  }, {
+    guid: normalBmk.guid,
+    syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+  });
+  PlacesUtils.tagging.tagURI(uri("http://getfirefox.com"), ["taggy"]);
+
+  let tombstoneSyncId = makeGuid();
+  yield PlacesSyncUtils.bookmarks.migrateOldTrackerEntries([{
+    syncId: normalBmk.guid,
+    modified: Date.now(),
+  }, {
+    syncId: tombstoneSyncId,
+    modified: 1479162463976,
+  }]);
+
+  let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+  deepEqual(Object.keys(changes).sort(), [normalBmk.guid, tombstoneSyncId].sort(),
+    "Should return change records for migrated bookmark and tombstone");
+
+  let fields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+    unknownBmk.guid, newBmk.guid, normalBmk.guid);
+  for (let field of fields) {
+    if (field.guid == normalBmk.guid) {
+      ok(field.lastModified > normalBmk.lastModified,
+        `Should bump last modified date for migrated bookmark ${field.guid}`);
+      equal(field.syncChangeCounter, 1,
+        `Should bump change counter for migrated bookmark ${field.guid}`);
+    } else {
+      strictEqual(field.syncChangeCounter, 0,
+        `Should not bump change counter for ${field.guid}`);
+    }
+    equal(field.syncStatus, PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+      `Should set sync status for ${field.guid} to NORMAL`);
+  }
+
+  let tombstones = yield PlacesTestUtils.fetchSyncTombstones();
+  deepEqual(tombstones, [{
+    guid: tombstoneSyncId,
+    dateRemoved: new Date(1479162463976),
+  }], "Should write tombstone for nonexistent migrated item");
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
+});