--- a/browser/components/migration/AutoMigrate.jsm
+++ b/browser/components/migration/AutoMigrate.jsm
@@ -6,45 +6,44 @@
 
 this.EXPORTED_SYMBOLS = ["AutoMigrate"];
 
 const { classes: Cc, interfaces: Ci, results: Cr, utils: Cu } = Components;
 
 const kAutoMigrateEnabledPref = "browser.migrate.automigrate.enabled";
 const kUndoUIEnabledPref = "browser.migrate.automigrate.ui.enabled";
 
-const kAutoMigrateStartedPref = "browser.migrate.automigrate.started";
-const kAutoMigrateFinishedPref = "browser.migrate.automigrate.finished";
 const kAutoMigrateBrowserPref = "browser.migrate.automigrate.browser";
 
 const kAutoMigrateLastUndoPromptDateMsPref = "browser.migrate.automigrate.lastUndoPromptDateMs";
 const kAutoMigrateDaysToOfferUndoPref = "browser.migrate.automigrate.daysToOfferUndo";
 
-const kPasswordManagerTopic = "passwordmgr-storage-changed";
-const kPasswordManagerTopicTypes = new Set([
-  "addLogin",
-  "modifyLogin",
-]);
-
-const kSyncTopic = "fxaccounts:onlogin";
-
 const kNotificationId = "abouthome-automigration-undo";
 
 Cu.import("resource:///modules/MigrationUtils.jsm");
 Cu.import("resource://gre/modules/Preferences.jsm");
 Cu.import("resource://gre/modules/Services.jsm");
 Cu.import("resource://gre/modules/Task.jsm");
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "AsyncShutdown",
+                                  "resource://gre/modules/AsyncShutdown.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "LoginHelper",
                                   "resource://gre/modules/LoginHelper.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "OS",
+                                  "resource://gre/modules/osfile.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "PlacesUtils",
                                   "resource://gre/modules/PlacesUtils.jsm");
 
 Cu.importGlobalProperties(["URL"]);
 
+/* globals kUndoStateFullPath */
+XPCOMUtils.defineLazyGetter(this, "kUndoStateFullPath", function() {
+  return OS.Path.join(OS.Constants.Path.profileDir, "initialMigrationMetadata.jsonlz4");
+});
+
 const AutoMigrate = {
   get resourceTypesToUse() {
     let {BOOKMARKS, HISTORY, PASSWORDS} = Ci.nsIBrowserProfileMigrator;
     return BOOKMARKS | HISTORY | PASSWORDS;
   },
 
   _checkIfEnabled() {
     let pref = Preferences.get(kAutoMigrateEnabledPref, false);
@@ -63,49 +62,16 @@ const AutoMigrate = {
       return JSON.parse(parser.getString("Preferences", kAutoMigrateEnabledPref));
     } catch (ex) { /* ignore exceptions (file doesn't exist, invalid value, etc.) */ }
 
     return pref;
   },
 
   init() {
     this.enabled = this._checkIfEnabled();
-    if (this.enabled) {
-      this.maybeInitUndoObserver();
-    }
-  },
-
-  maybeInitUndoObserver() {
-    if (!this.canUndo()) {
-      return;
-    }
-    // Now register places, password and sync observers:
-    this.onItemAdded = this.onItemMoved = this.onItemChanged =
-      this.removeUndoOption.bind(this, this.UNDO_REMOVED_REASON_BOOKMARK_CHANGE);
-    PlacesUtils.addLazyBookmarkObserver(this, true);
-    for (let topic of [kSyncTopic, kPasswordManagerTopic]) {
-      Services.obs.addObserver(this, topic, true);
-    }
-  },
-
-  observe(subject, topic, data) {
-    if (topic == kPasswordManagerTopic) {
-      // As soon as any login gets added or modified, disable undo:
-      // (Note that this ignores logins being removed as that doesn't
-      //  impair the 'undo' functionality of the import.)
-      if (kPasswordManagerTopicTypes.has(data)) {
-        // Ignore chrome:// things like sync credentials:
-        let loginInfo = subject.QueryInterface(Ci.nsILoginInfo);
-        if (!loginInfo.hostname || !loginInfo.hostname.startsWith("chrome://")) {
-          this.removeUndoOption(this.UNDO_REMOVED_REASON_PASSWORD_CHANGE);
-        }
-      }
-    } else if (topic == kSyncTopic) {
-      this.removeUndoOption(this.UNDO_REMOVED_REASON_SYNC_SIGNIN);
-    }
   },
 
   /**
    * Automatically pick a migrator and resources to migrate,
    * then migrate those and start up.
    *
    * @throws if automatically deciding on migrators/data
    *         failed for some reason.
@@ -132,31 +98,28 @@ const AutoMigrate = {
         sawErrors = true;
       } else if (topic == "Migration:Ended") {
         histogram.add(25);
         if (sawErrors) {
           histogram.add(26);
         }
         Services.obs.removeObserver(migrationObserver, "Migration:Ended");
         Services.obs.removeObserver(migrationObserver, "Migration:ItemError");
-        Services.prefs.setCharPref(kAutoMigrateStartedPref, startTime.toString());
-        Services.prefs.setCharPref(kAutoMigrateFinishedPref, Date.now().toString());
         Services.prefs.setCharPref(kAutoMigrateBrowserPref, pickedKey);
-        // Need to manually start listening to new bookmarks/logins being created,
-        // because, when we were initialized, there wasn't the possibility to
-        // 'undo' anything.
-        this.maybeInitUndoObserver();
+        // Save the undo history and block shutdown on that save completing.
+        AsyncShutdown.profileBeforeChange.addBlocker(
+          "AutoMigrate Undo saving", this.saveUndoState(), () => {
+            return {state: this._saveUndoStateTrackerForShutdown};
+          });
       }
     };
 
+    MigrationUtils.initializeUndoData();
     Services.obs.addObserver(migrationObserver, "Migration:Ended", false);
     Services.obs.addObserver(migrationObserver, "Migration:ItemError", false);
-    // We'll save this when the migration has finished, at which point the pref
-    // service will be available.
-    let startTime = Date.now();
     migrator.migrate(this.resourceTypesToUse, profileStartup, profileToMigrate);
     histogram.add(20);
   },
 
   /**
    * Pick and return a migrator to use for automatically migrating.
    *
    * @param {String} migratorKey   optional, a migrator key to prefer/pick.
@@ -206,91 +169,63 @@ const AutoMigrate = {
       return suggestedProfile;
     }
     if (profiles && profiles.length > 1) {
       throw new Error("Don't know how to pick a profile when more than 1 profile is present.");
     }
     return profiles ? profiles[0] : null;
   },
 
-  getUndoRange() {
-    let start, finish;
+  canUndo: Task.async(function* () {
+    if (this._savingPromise) {
+      yield this._savingPromise;
+    }
+    let fileExists = false;
     try {
-      start = parseInt(Preferences.get(kAutoMigrateStartedPref, "0"), 10);
-      finish = parseInt(Preferences.get(kAutoMigrateFinishedPref, "0"), 10);
+      fileExists = yield OS.File.exists(kUndoStateFullPath);
     } catch (ex) {
       Cu.reportError(ex);
     }
-    if (!finish || !start) {
-      return null;
-    }
-    return [new Date(start), new Date(finish)];
-  },
-
-  canUndo() {
-    return !!this.getUndoRange();
-  },
+    return fileExists;
+  }),
 
   undo: Task.async(function* () {
     let histogram = Services.telemetry.getHistogramById("FX_STARTUP_MIGRATION_AUTOMATED_IMPORT_UNDO");
     histogram.add(0);
-    if (!this.canUndo()) {
+    if (!(yield this.canUndo())) {
       histogram.add(5);
       throw new Error("Can't undo!");
     }
 
     histogram.add(10);
 
-    yield PlacesUtils.bookmarks.eraseEverything();
+    let readPromise = OS.File.read(kUndoStateFullPath, {
+      encoding: "utf-8",
+      compression: "lz4",
+    });
+    let stateData = this._dejsonifyUndoState(yield readPromise);
+    yield this._removeUnchangedBookmarks(stateData.get("bookmarks"));
     histogram.add(15);
 
-    // NB: we drop the start time of the migration for now. This is because
-    // imported history will always end up being 'backdated' to the actual
-    // visit time recorded by the browser from which we imported. As a result,
-    // a lower bound on this item doesn't really make sense.
-    // Note that for form data this could be different, but we currently don't
-    // support form data import from any non-Firefox browser, so it isn't
-    // imported from other browsers by the automigration code, nor do we
-    // remove it here.
-    let range = this.getUndoRange();
-    yield PlacesUtils.history.removeVisitsByFilter({
-      beginDate: new Date(0),
-      endDate: range[1]
-    });
+    yield this._removeSomeVisits(stateData.get("visits"));
     histogram.add(20);
 
-    try {
-      Services.logins.removeAllLogins();
-    } catch (ex) {
-      // ignore failure.
-    }
+    yield this._removeUnchangedLogins(stateData.get("logins"));
     histogram.add(25);
+
     this.removeUndoOption(this.UNDO_REMOVED_REASON_UNDO_USED);
     histogram.add(30);
   }),
 
   removeUndoOption(reason) {
-    // Remove observers, and ensure that exceptions doing so don't break
-    // removing the pref.
-    for (let topic of [kSyncTopic, kPasswordManagerTopic]) {
-      try {
-        Services.obs.removeObserver(this, topic);
-      } catch (ex) {
-        Cu.reportError("Error removing observer for " + topic + ": " + ex);
-      }
-    }
-    try {
-      PlacesUtils.removeLazyBookmarkObserver(this);
-    } catch (ex) {
-      Cu.reportError("Error removing lazy bookmark observer: " + ex);
-    }
+    // We don't wait for the off-main-thread removal to complete. OS.File will
+    // ensure it happens before shutdown.
+    OS.File.remove(kUndoStateFullPath, {ignoreAbsent: true});
 
     let migrationBrowser = Preferences.get(kAutoMigrateBrowserPref, "unknown");
-    Services.prefs.clearUserPref(kAutoMigrateStartedPref);
-    Services.prefs.clearUserPref(kAutoMigrateFinishedPref);
     Services.prefs.clearUserPref(kAutoMigrateBrowserPref);
 
     let browserWindows = Services.wm.getEnumerator("navigator:browser");
     while (browserWindows.hasMoreElements()) {
       let win = browserWindows.getNext();
       if (!win.closed) {
         for (let browser of win.gBrowser.browsers) {
           let nb = win.gBrowser.getNotificationBox(browser);
@@ -309,19 +244,23 @@ const AutoMigrate = {
   getBrowserUsedForMigration() {
     let browserId = Services.prefs.getCharPref(kAutoMigrateBrowserPref);
     if (browserId) {
       return MigrationUtils.getBrowserName(browserId);
     }
     return null;
   },
 
-  maybeShowUndoNotification(target) {
+  maybeShowUndoNotification: Task.async(function* (target) {
+    if (!(yield this.canUndo())) {
+      return;
+    }
+
     // The tab might have navigated since we requested the undo state:
-    if (!this.canUndo() || target.currentURI.spec != "about:home" ||
+    if (target.currentURI.spec != "about:home" ||
         !Preferences.get(kUndoUIEnabledPref, false)) {
       return;
     }
 
     let win = target.ownerGlobal;
     let notificationBox = win.gBrowser.getNotificationBox(target);
     if (!notificationBox || notificationBox.getNotificationWithValue("abouthome-automigration-undo")) {
       return;
@@ -360,17 +299,17 @@ const AutoMigrate = {
         },
       },
     ];
     notificationBox.appendNotification(
       message, kNotificationId, null, notificationBox.PRIORITY_INFO_HIGH, buttons
     );
     let remainingDays = Preferences.get(kAutoMigrateDaysToOfferUndoPref, 0);
     Services.telemetry.getHistogramById("FX_STARTUP_MIGRATION_UNDO_OFFERED").add(4 - remainingDays);
-  },
+  }),
 
   shouldStillShowUndoPrompt() {
     let today = new Date();
     // Round down to midnight:
     today = new Date(today.getFullYear(), today.getMonth(), today.getDate());
     // We store the unix timestamp corresponding to midnight on the last day
     // on which we prompted. Fetch that and compare it to today's date.
     // (NB: stored as a string because int prefs are too small for unix
@@ -390,16 +329,70 @@ const AutoMigrate = {
 
   UNDO_REMOVED_REASON_UNDO_USED: 0,
   UNDO_REMOVED_REASON_SYNC_SIGNIN: 1,
   UNDO_REMOVED_REASON_PASSWORD_CHANGE: 2,
   UNDO_REMOVED_REASON_BOOKMARK_CHANGE: 3,
   UNDO_REMOVED_REASON_OFFER_EXPIRED: 4,
   UNDO_REMOVED_REASON_OFFER_REJECTED: 5,
 
+  _jsonifyUndoState(state) {
+    if (!state) {
+      return "null";
+    }
+    // Deal with date serialization.
+    let bookmarks = state.get("bookmarks");
+    for (let bm of bookmarks) {
+      bm.lastModified = bm.lastModified.getTime();
+    }
+    let serializableState = {
+      bookmarks,
+      logins: state.get("logins"),
+      visits: state.get("visits"),
+    };
+    return JSON.stringify(serializableState);
+  },
+
+  _dejsonifyUndoState(state) {
+    state = JSON.parse(state);
+    for (let bm of state.bookmarks) {
+      bm.lastModified = new Date(bm.lastModified);
+    }
+    return new Map([
+      ["bookmarks", state.bookmarks],
+      ["logins", state.logins],
+      ["visits", state.visits],
+    ]);
+  },
+
+  _saveUndoStateTrackerForShutdown: "not running",
+  saveUndoState: Task.async(function* () {
+    let resolveSavingPromise;
+    this._saveUndoStateTrackerForShutdown = "processing undo history";
+    this._savingPromise = new Promise(resolve => { resolveSavingPromise = resolve });
+    let state = yield MigrationUtils.stopAndRetrieveUndoData();
+    this._saveUndoStateTrackerForShutdown = "writing undo history";
+    this._undoSavePromise = OS.File.writeAtomic(
+      kUndoStateFullPath, this._jsonifyUndoState(state), {
+        encoding: "utf-8",
+        compression: "lz4",
+        tmpPath: kUndoStateFullPath + ".tmp",
+      });
+    this._undoSavePromise.then(
+      rv => {
+        resolveSavingPromise(rv);
+        delete this._savingPromise;
+      },
+      e => {
+        Cu.reportError("Could not write undo state for automatic migration.");
+        throw e;
+      });
+    return this._undoSavePromise;
+  }),
+
   _removeUnchangedBookmarks: Task.async(function* (bookmarks) {
     if (!bookmarks.length) {
       return;
     }
 
     let guidToLMMap = new Map(bookmarks.map(b => [b.guid, b.lastModified]));
     let bookmarksFromDB = [];
     let bmPromises = Array.from(guidToLMMap.keys()).map(guid => {

--- a/browser/components/migration/tests/unit/test_automigration.js
+++ b/browser/components/migration/tests/unit/test_automigration.js
@@ -169,79 +169,93 @@ add_task(function* checkUndoPrecondition
                      "getMigrateData called with 'null' as a profile");
 
   let {BOOKMARKS, HISTORY, PASSWORDS} = Ci.nsIBrowserProfileMigrator;
   let expectedTypes = BOOKMARKS | HISTORY | PASSWORDS;
   Assert.deepEqual(gShimmedMigrator._migrateArgs, [expectedTypes, "startup", null],
                    "migrate called with 'null' as a profile");
 
   yield migrationFinishedPromise;
-  Assert.ok(Preferences.has("browser.migrate.automigrate.started"),
-            "Should have set start time pref");
-  Assert.ok(Preferences.has("browser.migrate.automigrate.finished"),
-            "Should have set finish time pref");
-  Assert.ok(AutoMigrate.canUndo(), "Should be able to undo migration");
-
-  let [beginRange, endRange] = AutoMigrate.getUndoRange();
-  let stringRange = `beginRange: ${beginRange}; endRange: ${endRange}`;
-  Assert.ok(beginRange <= endRange,
-            "Migration should have started before or when it ended " + stringRange);
+  Assert.ok(Preferences.has("browser.migrate.automigrate.browser"),
+            "Should have set browser pref");
+  Assert.ok((yield AutoMigrate.canUndo()), "Should be able to undo migration");
 
   yield AutoMigrate.undo();
   Assert.ok(true, "Should be able to finish an undo cycle.");
 });
 
 /**
  * Fake a migration and then try to undo it to verify all data gets removed.
  */
 add_task(function* checkUndoRemoval() {
-  let startTime = "" + Date.now();
-
+  MigrationUtils.initializeUndoData();
   // Insert a login and check that that worked.
-  let login = Cc["@mozilla.org/login-manager/loginInfo;1"].createInstance(Ci.nsILoginInfo);
-  login.init("www.mozilla.org", "http://www.mozilla.org", null, "user", "pass", "userEl", "passEl");
-  Services.logins.addLogin(login);
+  MigrationUtils.insertLoginWrapper({
+    hostname: "www.mozilla.org",
+    formSubmitURL: "http://www.mozilla.org",
+    username: "user",
+    password: "pass",
+  });
   let storedLogins = Services.logins.findLogins({}, "www.mozilla.org",
                                                 "http://www.mozilla.org", null);
   Assert.equal(storedLogins.length, 1, "Should have 1 login");
 
   // Insert a bookmark and check that we have exactly 1 bookmark for that URI.
-  yield PlacesUtils.bookmarks.insert({
+  yield MigrationUtils.insertBookmarkWrapper({
     parentGuid: PlacesUtils.bookmarks.toolbarGuid,
     url: "http://www.example.org/",
     title: "Some example bookmark",
   });
 
   let bookmark = yield PlacesUtils.bookmarks.fetch({url: "http://www.example.org/"});
   Assert.ok(bookmark, "Should have a bookmark before undo");
   Assert.equal(bookmark.title, "Some example bookmark", "Should have correct bookmark before undo.");
 
-  // Insert 2 history visits - one in the current migration time, one from before.
+  // Insert 2 history visits
   let now_uSec = Date.now() * 1000;
   let visitedURI = Services.io.newURI("http://www.example.com/", null, null);
-  yield PlacesTestUtils.addVisits([
-    {uri: visitedURI, visitDate: now_uSec},
-    {uri: visitedURI, visitDate: now_uSec - 100 * kUsecPerMin},
-  ]);
+  let frecencyUpdatePromise = new Promise(resolve => {
+    let expectedChanges = 2;
+    let observer = {
+      onFrecencyChanged: function() {
+        if (!--expectedChanges) {
+          PlacesUtils.history.removeObserver(observer);
+          resolve();
+        }
+      },
+    };
+    PlacesUtils.history.addObserver(observer, false);
+  });
+  yield MigrationUtils.insertVisitsWrapper([{
+    uri: visitedURI,
+    visits: [
+      {
+        transitionType: PlacesUtils.history.TRANSITION_LINK,
+        visitDate: now_uSec,
+      },
+      {
+        transitionType: PlacesUtils.history.TRANSITION_LINK,
+        visitDate: now_uSec - 100 * kUsecPerMin,
+      },
+    ]
+  }]);
+  yield frecencyUpdatePromise;
 
   // Verify that both visits get reported.
   let opts = PlacesUtils.history.getNewQueryOptions();
   opts.resultType = opts.RESULTS_AS_VISIT;
   let query = PlacesUtils.history.getNewQuery();
   query.uri = visitedURI;
   let visits = PlacesUtils.history.executeQuery(query, opts);
   visits.root.containerOpen = true;
   Assert.equal(visits.root.childCount, 2, "Should have 2 visits");
   // Clean up:
   visits.root.containerOpen = false;
 
-  // Now set finished pref:
-  let endTime = "" + Date.now();
-  Preferences.set("browser.migrate.automigrate.started", startTime);
-  Preferences.set("browser.migrate.automigrate.finished", endTime);
+  yield AutoMigrate.saveUndoState();
 
   // Verify that we can undo, then undo:
   Assert.ok(AutoMigrate.canUndo(), "Should be possible to undo migration");
   yield AutoMigrate.undo();
 
   // Check that the undo removed the history visits:
   visits = PlacesUtils.history.executeQuery(query, opts);
   visits.root.containerOpen = true;
@@ -251,57 +265,16 @@ add_task(function* checkUndoRemoval() {
   // Check that the undo removed the bookmarks:
   bookmark = yield PlacesUtils.bookmarks.fetch({url: "http://www.example.org/"});
   Assert.ok(!bookmark, "Should have no bookmarks after undo");
 
   // Check that the undo removed the passwords:
   storedLogins = Services.logins.findLogins({}, "www.mozilla.org",
                                             "http://www.mozilla.org", null);
   Assert.equal(storedLogins.length, 0, "Should have no logins");
-
-  // Finally check prefs got cleared:
-  Assert.ok(!Preferences.has("browser.migrate.automigrate.started"),
-            "Should no longer have pref for migration start time.");
-  Assert.ok(!Preferences.has("browser.migrate.automigrate.finished"),
-            "Should no longer have pref for migration finish time.");
-});
-
-add_task(function* checkUndoDisablingByBookmarksAndPasswords() {
-  let startTime = "" + Date.now();
-  Services.prefs.setCharPref("browser.migrate.automigrate.started", startTime);
-  // Now set finished pref:
-  let endTime = "" + (Date.now() + 1000);
-  Services.prefs.setCharPref("browser.migrate.automigrate.finished", endTime);
-  AutoMigrate.maybeInitUndoObserver();
-
-  Assert.ok(AutoMigrate.canUndo(), "Should be able to undo.");
-
-  // Insert a login and check that that disabled undo.
-  let login = Cc["@mozilla.org/login-manager/loginInfo;1"].createInstance(Ci.nsILoginInfo);
-  login.init("www.mozilla.org", "http://www.mozilla.org", null, "user", "pass", "userEl", "passEl");
-  Services.logins.addLogin(login);
-
-  Assert.ok(!AutoMigrate.canUndo(), "Should no longer be able to undo.");
-  Services.prefs.setCharPref("browser.migrate.automigrate.started", startTime);
-  Services.prefs.setCharPref("browser.migrate.automigrate.finished", endTime);
-  Assert.ok(AutoMigrate.canUndo(), "Should be able to undo.");
-  AutoMigrate.maybeInitUndoObserver();
-
-  // Insert a bookmark and check that that disabled undo.
-  yield PlacesUtils.bookmarks.insert({
-    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
-    url: "http://www.example.org/",
-    title: "Some example bookmark",
-  });
-  Assert.ok(!AutoMigrate.canUndo(), "Should no longer be able to undo.");
-
-  try {
-    Services.logins.removeAllLogins();
-  } catch (ex) {}
-  yield PlacesUtils.bookmarks.eraseEverything();
 });
 
 add_task(function* checkUndoBookmarksState() {
   MigrationUtils.initializeUndoData();
   const {TYPE_FOLDER, TYPE_BOOKMARK} = PlacesUtils.bookmarks;
   let title = "Some example bookmark";
   let url = "http://www.example.com";
   let parentGuid = PlacesUtils.bookmarks.toolbarGuid;