--- a/services/common/async.js
+++ b/services/common/async.js
@@ -202,9 +202,19 @@ this.Async = {
   querySpinningly: function querySpinningly(query, names) {
     // 'Synchronously' asyncExecute, fetching all results by name.
     let storageCallback = Object.create(Async._storageCallbackPrototype);
     storageCallback.names = names;
     storageCallback.syncCb = Async.makeSyncCallback();
     query.executeAsync(storageCallback);
     return Async.waitForSyncCallback(storageCallback.syncCb);
   },
+
+  promiseSpinningly(promise) {
+    let cb = Async.makeSpinningCallback();
+    promise.then(result =>  {
+      cb(null, result);
+    }, err => {
+      cb(err || new Error("Promise rejected without explicit error"));
+    });
+    return cb.wait();
+  },
 };

--- a/services/sync/modules/engines/bookmarks.js
+++ b/services/sync/modules/engines/bookmarks.js
@@ -267,79 +267,79 @@ BookmarksEngine.prototype = {
       }
     }
     return url;
   },
 
   _guidMapFailed: false,
   _buildGUIDMap: function _buildGUIDMap() {
     let guidMap = {};
-    for (let guid in this._store.getAllIDs()) {
-      // Figure out with which key to store the mapping.
-      let key;
-      let id = this._store.idForGUID(guid);
-      let itemType;
-      try {
-        itemType = PlacesUtils.bookmarks.getItemType(id);
-      } catch (ex) {
-        this._log.warn("Deleting invalid bookmark record with id", id);
-        try {
-          PlacesUtils.bookmarks.removeItem(id);
-        } catch (ex) {
-          this._log.warn("Failed to delete invalid bookmark", ex);
+    let tree = Async.promiseSpinningly(PlacesUtils.promiseBookmarksTree("", {
+      includeItemIds: true
+    }));
+    function* walkBookmarksTree(tree, parent=null) {
+      if (tree) {
+        // Skip root node
+        if (parent) {
+          yield [tree, parent];
         }
-        continue;
+        if (tree.children) {
+          for (let child of tree.children) {
+            yield* walkBookmarksTree(child, tree);
+          }
+        }
       }
-      switch (itemType) {
-        case PlacesUtils.bookmarks.TYPE_BOOKMARK:
+    }
 
-          // Smart bookmarks map to their annotation value.
-          let queryId;
-          try {
-            queryId = PlacesUtils.annotations.getItemAnnotation(
-              id, SMART_BOOKMARKS_ANNO);
-          } catch(ex) {}
+    function* walkBookmarksRoots(tree, rootGUIDs) {
+      for (let guid of rootGUIDs) {
+        let id = kSpecialIds.specialIdForGUID(guid, false);
+        let bookmarkRoot = id === null ? null :
+          tree.children.find(child => child.id === id);
+        if (bookmarkRoot === null) {
+          continue;
+        }
+        yield* walkBookmarksTree(bookmarkRoot, tree);
+      }
+    }
 
-          if (queryId) {
-            key = "q" + queryId;
+    let rootsToWalk = kSpecialIds.guids.filter(guid =>
+      guid !== 'places' && guid !== 'tags');
+
+    for (let [node, parent] of walkBookmarksRoots(tree, rootsToWalk)) {
+      let {guid, id, type: placeType} = node;
+      guid = kSpecialIds.specialGUIDForId(id) || guid;
+      let key;
+      switch (placeType) {
+        case PlacesUtils.TYPE_X_MOZ_PLACE:
+          // Bookmark
+          let query = null;
+          if (node.annos && node.uri.startsWith("place:")) {
+            query = node.annos.find(({name}) => name === SMART_BOOKMARKS_ANNO);
+          }
+          if (query && query.value) {
+            key = "q" + query.value;
           } else {
-            let uri;
-            try {
-              uri = PlacesUtils.bookmarks.getBookmarkURI(id);
-            } catch (ex) {
-              // Bug 1182366 - NS_ERROR_MALFORMED_URI here stops bookmarks sync.
-              // Try and get the string value of the URL for diagnostic purposes.
-              let url = this._getStringUrlForId(id);
-              this._log.warn(`Deleting bookmark with invalid URI. url="${url}", id=${id}`);
-              try {
-                PlacesUtils.bookmarks.removeItem(id);
-              } catch (ex) {
-                this._log.warn("Failed to delete invalid bookmark", ex);
-              }
-              continue;
-            }
-            key = "b" + uri.spec + ":" + PlacesUtils.bookmarks.getItemTitle(id);
+            key = "b" + node.uri + ":" + node.title;
           }
           break;
-        case PlacesUtils.bookmarks.TYPE_FOLDER:
-          key = "f" + PlacesUtils.bookmarks.getItemTitle(id);
+        case PlacesUtils.TYPE_X_MOZ_PLACE_CONTAINER:
+          // Folder
+          key = "f" + node.title;
           break;
-        case PlacesUtils.bookmarks.TYPE_SEPARATOR:
-          key = "s" + PlacesUtils.bookmarks.getItemIndex(id);
+        case PlacesUtils.TYPE_X_MOZ_PLACE_SEPARATOR:
+          // Separator
+          key = "s" + node.index;
           break;
         default:
+          this._log.error("Unknown place type: '"+placeType+"'");
           continue;
       }
 
-      // The mapping is on a per parent-folder-name basis.
-      let parent = PlacesUtils.bookmarks.getFolderIdForItem(id);
-      if (parent <= 0)
-        continue;
-
-      let parentName = PlacesUtils.bookmarks.getItemTitle(parent);
+      let parentName = parent.title;
       if (guidMap[parentName] == null)
         guidMap[parentName] = {};
 
       // If the entry already exists, remember that there are explicit dupes.
       let entry = new String(guid);
       entry.hasDupe = guidMap[parentName][key] != null;
 
       // Remember this item's GUID for its parent-name/key pair.

--- a/services/sync/tests/unit/test_bookmark_engine.js
+++ b/services/sync/tests/unit/test_bookmark_engine.js
@@ -391,17 +391,19 @@ add_test(function test_bookmark_guidMap_
     PlacesUtils.bookmarks.toolbarFolder, "Folder 1", 0);
   let itemGUID    = store.GUIDForId(itemID);
   let itemPayload = store.createRecord(itemGUID).cleartext;
   coll.insert(itemGUID, encryptPayload(itemPayload));
 
   engine.lastSync = 1;   // So we don't back up.
 
   // Make building the GUID map fail.
-  store.getAllIDs = function () { throw "Nooo"; };
+
+  let pbt = PlacesUtils.promiseBookmarksTree;
+  PlacesUtils.promiseBookmarksTree = function() { return Promise.reject("Nooo"); };
 
   // Ensure that we throw when accessing _guidMap.
   engine._syncStartup();
   _("No error.");
   do_check_false(engine._guidMapFailed);
 
   _("We get an error if building _guidMap fails in use.");
   let err;
@@ -417,16 +419,17 @@ add_test(function test_bookmark_guidMap_
   err = undefined;
   try {
     engine._processIncoming();
   } catch (ex) {
     err = ex;
   }
   do_check_eq(err, "Nooo");
 
+  PlacesUtils.promiseBookmarksTree = pbt;
   server.stop(run_next_test);
 });
 
 add_test(function test_bookmark_is_taggable() {
   let engine = new BookmarksEngine(Service);
   let store = engine._store;
 
   do_check_true(store.isTaggable("bookmark"));

--- a/services/sync/tests/unit/test_bookmark_invalid.js
+++ b/services/sync/tests/unit/test_bookmark_invalid.js
@@ -7,56 +7,16 @@ Cu.import("resource://services-sync/serv
 Cu.import("resource://services-sync/util.js");
 
 Service.engineManager.register(BookmarksEngine);
 
 var engine = Service.engineManager.get("bookmarks");
 var store = engine._store;
 var tracker = engine._tracker;
 
-// Return a promise resolved when the specified message is written to the
-// bookmarks engine log.
-function promiseLogMessage(messagePortion) {
-  return new Promise(resolve => {
-    let appender;
-    let log = Log.repository.getLogger("Sync.Engine.Bookmarks");
-
-    function TestAppender() {
-      Log.Appender.call(this);
-    }
-    TestAppender.prototype = Object.create(Log.Appender.prototype);
-    TestAppender.prototype.doAppend = function(message) {
-      if (message.indexOf(messagePortion) >= 0) {
-        log.removeAppender(appender);
-        resolve();
-      }
-    };
-    TestAppender.prototype.level = Log.Level.Debug;
-    appender = new TestAppender();
-    log.addAppender(appender);
-  });
-}
-
-// Returns a promise that resolves if the specified ID does *not* exist and
-// rejects if it does.
-function promiseNoItem(itemId) {
-  return new Promise((resolve, reject) => {
-    try {
-      PlacesUtils.bookmarks.getFolderIdForItem(itemId);
-      reject("fetching the item didn't fail");
-    } catch (ex) {
-      if (ex.result == Cr.NS_ERROR_ILLEGAL_VALUE) {
-        resolve("item doesn't exist");
-      } else {
-        reject("unexpected exception: " + ex);
-      }
-    }
-  });
-}
-
 add_task(function* test_ignore_invalid_uri() {
   _("Ensure that we don't die with invalid bookmarks.");
 
   // First create a valid bookmark.
   let bmid = PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                                   Services.io.newURI("http://example.com/", null, null),
                                                   PlacesUtils.bookmarks.DEFAULT_INDEX,
                                                   "the title");
@@ -65,23 +25,19 @@ add_task(function* test_ignore_invalid_u
   yield PlacesUtils.withConnectionWrapper("test_ignore_invalid_uri", Task.async(function* (db) {
     yield db.execute(
       `UPDATE moz_places SET url = :url
        WHERE id = (SELECT b.fk FROM moz_bookmarks b
        WHERE b.id = :id LIMIT 1)`,
       { id: bmid, url: "<invalid url>" });
   }));
 
-  // DB is now "corrupt" - setup a log appender to capture what we log.
-  let promiseMessage = promiseLogMessage('Deleting bookmark with invalid URI. url="<invalid url>"');
-  // This should work and log our invalid id.
+  // Ensure that this doesn't throw even though the DB is now in a bad state (a
+  // bookmark has an illegal url).
   engine._buildGUIDMap();
-  yield promiseMessage;
-  // And we should have deleted the item.
-  yield promiseNoItem(bmid);
 });
 
 add_task(function* test_ignore_missing_uri() {
   _("Ensure that we don't die with a bookmark referencing an invalid bookmark id.");
 
   // First create a valid bookmark.
   let bmid = PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
                                                   Services.io.newURI("http://example.com/", null, null),
@@ -91,21 +47,17 @@ add_task(function* test_ignore_missing_u
   // Now update moz_bookmarks to reference a non-existing places ID
   yield PlacesUtils.withConnectionWrapper("test_ignore_missing_uri", Task.async(function* (db) {
     yield db.execute(
       `UPDATE moz_bookmarks SET fk = 999999
        WHERE id = :id`
       , { id: bmid });
   }));
 
-  // DB is now "corrupt" - bookmarks will fail to locate a string url to log
-  // and use "<not found>" as a placeholder.
-  let promiseMessage = promiseLogMessage('Deleting bookmark with invalid URI. url="<not found>"');
+  // Ensure that this doesn't throw even though the DB is now in a bad state (a
+  // bookmark has an illegal url).
   engine._buildGUIDMap();
-  yield promiseMessage;
-  // And we should have deleted the item.
-  yield promiseNoItem(bmid);
 });
 
 function run_test() {
   initTestLogging('Trace');
   run_next_test();
 }