Bug 713524 - Batch bookmark inserts. r=rnewman, a=android-only
authorNick Alexander <nalexander@mozilla.com>
Mon, 30 Apr 2012 13:40:30 -0700
changeset 92731 0d06d9f8e4f65ea1f1524b75943a296645e3c111
parent 92730 62a472b617de966a45c3cff3f86e33946421ff3e
child 92732 74108dd3201df330bb7f93d8064932c2b251503f
push id22557
push usermbrubeck@mozilla.com
push dateTue, 01 May 2012 18:41:22 +0000
treeherdermozilla-central@74108dd3201d [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersrnewman, android-only
bugs713524
milestone15.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 713524 - Batch bookmark inserts. r=rnewman, a=android-only
mobile/android/base/sync/Utils.java
mobile/android/base/sync/repositories/Server11RepositorySession.java
mobile/android/base/sync/repositories/android/AndroidBrowserBookmarksRepositorySession.java
mobile/android/base/sync/repositories/android/AndroidBrowserHistoryDataAccessor.java
mobile/android/base/sync/repositories/android/AndroidBrowserHistoryRepositorySession.java
mobile/android/base/sync/repositories/android/AndroidBrowserRepositoryDataAccessor.java
mobile/android/base/sync/repositories/android/AndroidBrowserRepositorySession.java
mobile/android/base/sync/repositories/android/BookmarksInsertionManager.java
mobile/android/sync/java-sources.mn
--- a/mobile/android/base/sync/Utils.java
+++ b/mobile/android/base/sync/Utils.java
@@ -1,56 +1,23 @@
-/* ***** BEGIN LICENSE BLOCK *****
- * Version: MPL 1.1/GPL 2.0/LGPL 2.1
- *
- * The contents of this file are subject to the Mozilla Public License Version
- * 1.1 (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- * http://www.mozilla.org/MPL/
- *
- * Software distributed under the License is distributed on an "AS IS" basis,
- * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
- * for the specific language governing rights and limitations under the
- * License.
- *
- * The Original Code is Android Sync Client.
- *
- * The Initial Developer of the Original Code is
- * the Mozilla Foundation.
- * Portions created by the Initial Developer are Copyright (C) 2011
- * the Initial Developer. All Rights Reserved.
- *
- * Contributor(s):
- * Jason Voll <jvoll@mozilla.com>
- * Richard Newman <rnewman@mozilla.com>
- *
- * Alternatively, the contents of this file may be used under the terms of
- * either the GNU General Public License Version 2 or later (the "GPL"), or
- * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
- * in which case the provisions of the GPL or the LGPL are applicable instead
- * of those above. If you wish to allow use of your version of this file only
- * under the terms of either the GPL or the LGPL, and not to allow others to
- * use your version of this file under the terms of the MPL, indicate your
- * decision by deleting the provisions above and replace them with the notice
- * and other provisions required by the GPL or the LGPL. If you do not delete
- * the provisions above, a recipient may use your version of this file under
- * the terms of any one of the MPL, the GPL or the LGPL.
- *
- * ***** END LICENSE BLOCK ***** */
+/* 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/. */
 
 package org.mozilla.gecko.sync;
 
 import java.io.UnsupportedEncodingException;
 import java.math.BigDecimal;
 import java.math.BigInteger;
 import java.net.URLDecoder;
 import java.security.MessageDigest;
 import java.security.NoSuchAlgorithmException;
 import java.security.SecureRandom;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.HashMap;
 import java.util.Locale;
 import java.util.Map;
 import java.util.TreeMap;
 
 import org.json.simple.JSONArray;
 import org.mozilla.apache.commons.codec.binary.Base32;
 import org.mozilla.apache.commons.codec.binary.Base64;
@@ -304,9 +271,31 @@ public class Utils {
         break;
       case 2:
         out.put(URLDecoder.decode(pair[0]), URLDecoder.decode(pair[1]));
         break;
       }
     }
     return out;
   }
+
+  // Because TextUtils.join is not stubbed.
+  public static String toDelimitedString(String delimiter, Collection<String> items) {
+    if (items == null || items.size() == 0) {
+      return "";
+    }
+
+    StringBuilder sb = new StringBuilder();
+    int i = 0;
+    int c = items.size();
+    for (String string : items) {
+      sb.append(string);
+      if (++i < c) {
+        sb.append(delimiter);
+      }
+    }
+    return sb.toString();
+  }
+
+  public static String toCommaSeparatedString(Collection<String> items) {
+    return toDelimitedString(", ", items);
+  }
 }
--- a/mobile/android/base/sync/repositories/Server11RepositorySession.java
+++ b/mobile/android/base/sync/repositories/Server11RepositorySession.java
@@ -218,16 +218,18 @@ public class Server11RepositorySession e
   }
 
   public Server11RepositorySession(Repository repository) {
     super(repository);
     serverRepository = (Server11Repository) repository;
   }
 
   private String flattenIDs(String[] guids) {
+    // Consider using Utils.toDelimitedString if and when the signature changes
+    // to Collection<String> guids.
     if (guids.length == 0) {
       return "";
     }
     if (guids.length == 1) {
       return guids[0];
     }
     StringBuilder b = new StringBuilder();
     for (String guid : guids) {
--- a/mobile/android/base/sync/repositories/android/AndroidBrowserBookmarksRepositorySession.java
+++ b/mobile/android/base/sync/repositories/android/AndroidBrowserBookmarksRepositorySession.java
@@ -1,15 +1,16 @@
 /* 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/. */
 
 package org.mozilla.gecko.sync.repositories.android;
 
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.TreeMap;
 
 import org.json.simple.JSONArray;
 import org.mozilla.gecko.R;
@@ -24,25 +25,30 @@ import org.mozilla.gecko.sync.repositori
 import org.mozilla.gecko.sync.repositories.Repository;
 import org.mozilla.gecko.sync.repositories.delegates.RepositorySessionBeginDelegate;
 import org.mozilla.gecko.sync.repositories.delegates.RepositorySessionFinishDelegate;
 import org.mozilla.gecko.sync.repositories.delegates.RepositorySessionStoreDelegate;
 import org.mozilla.gecko.sync.repositories.delegates.RepositorySessionWipeDelegate;
 import org.mozilla.gecko.sync.repositories.domain.BookmarkRecord;
 import org.mozilla.gecko.sync.repositories.domain.Record;
 
+import android.content.ContentUris;
 import android.content.Context;
 import android.database.Cursor;
+import android.net.Uri;
 
-public class AndroidBrowserBookmarksRepositorySession extends AndroidBrowserRepositorySession {
+public class AndroidBrowserBookmarksRepositorySession extends AndroidBrowserRepositorySession
+  implements BookmarksInsertionManager.BookmarkInserter {
 
   public static final int DEFAULT_DELETION_FLUSH_THRESHOLD = 50;
+  public static final int DEFAULT_INSERTION_FLUSH_THRESHOLD = 50;
+
   // TODO: synchronization for these.
-  private HashMap<String, Long> guidToID = new HashMap<String, Long>();
-  private HashMap<Long, String> idToGuid = new HashMap<Long, String>();
+  private HashMap<String, Long> parentGuidToIDMap = new HashMap<String, Long>();
+  private HashMap<Long, String> parentIDToGuidMap = new HashMap<Long, String>();
 
   /**
    * Some notes on reparenting/reordering.
    *
    * Fennec stores new items with a high-negative position, because it doesn't care.
    * On the other hand, it also doesn't give us any help managing positions.
    *
    * We can process records and folders in any order, though we'll usually see folders
@@ -96,16 +102,17 @@ public class AndroidBrowserBookmarksRepo
   // TODO: can we guarantee serial access to these?
   private HashMap<String, ArrayList<String>> missingParentToChildren = new HashMap<String, ArrayList<String>>();
   private HashMap<String, JSONArray>         parentToChildArray      = new HashMap<String, JSONArray>();
   private int needsReparenting = 0;
 
   private AndroidBrowserBookmarksDataAccessor dataAccessor;
 
   protected BookmarksDeletionManager deletionManager;
+  protected BookmarksInsertionManager insertionManager;
 
   /**
    * An array of known-special GUIDs.
    */
   public static String[] SPECIAL_GUIDS = new String[] {
     // Mobile and desktop places roots have to come first.
     "places",
     "mobile",
@@ -222,23 +229,23 @@ public class AndroidBrowserBookmarksRepo
     return RepoUtils.getIntFromCursor(cur, BrowserContract.Bookmarks.TYPE);
   }
 
   private static boolean rowIsFolder(Cursor cur) {
     return getTypeFromCursor(cur) == BrowserContract.Bookmarks.TYPE_FOLDER;
   }
 
   private String getGUIDForID(long androidID) {
-    String guid = idToGuid.get(androidID);
+    String guid = parentIDToGuidMap.get(androidID);
     trace("  " + androidID + " => " + guid);
     return guid;
   }
 
   private long getIDForGUID(String guid) {
-    Long id = guidToID.get(guid);
+    Long id = parentGuidToIDMap.get(guid);
     if (id == null) {
       Logger.warn(LOG_TAG, "Couldn't find local ID for GUID " + guid);
       return -1;
     }
     return id.longValue();
   }
 
   private String getGUID(Cursor cur) {
@@ -414,17 +421,17 @@ public class AndroidBrowserBookmarksRepo
       androidParentGUID = getGUIDForID(androidParentID);
     }
 
     boolean needsReparenting = false;
 
     if (androidParentGUID == null) {
       Logger.debug(LOG_TAG, "No parent GUID for record " + recordGUID + " with parent " + androidParentID);
       // If the parent has been stored and somehow has a null GUID, throw an error.
-      if (idToGuid.containsKey(androidParentID)) {
+      if (parentIDToGuidMap.containsKey(androidParentID)) {
         Logger.error(LOG_TAG, "Have the parent android ID for the record but the parent's GUID wasn't found.");
         throw new NoGuidForIdException(null);
       }
 
       // We have a parent ID but it's wrong. If the record is deleted,
       // we'll just say that it was in the Unsorted Bookmarks folder.
       // If not, we'll move it into Mobile Bookmarks.
       needsReparenting = true;
@@ -475,17 +482,17 @@ public class AndroidBrowserBookmarksRepo
   }
 
   protected JSONArray getChildrenArrayForRecordCursor(Cursor cur, String recordGUID, boolean persist) throws NullCursorException {
     boolean isFolder = rowIsFolder(cur);
     if (!isFolder) {
       return null;
     }
 
-    long androidID = guidToID.get(recordGUID);
+    long androidID = parentGuidToIDMap.get(recordGUID);
     JSONArray childArray = getChildrenArray(androidID, persist);
     if (childArray == null) {
       return null;
     }
 
     Logger.debug(LOG_TAG, "Fetched " + childArray.size() + " children for " + recordGUID);
     return childArray;
   }
@@ -507,17 +514,17 @@ public class AndroidBrowserBookmarksRepo
 
     if (BrowserContractHelpers.isSupportedType(bmk.type)) {
       return false;
     }
 
     Logger.debug(LOG_TAG, "Ignoring record with guid: " + bmk.guid + " and type: " + bmk.type);
     return true;
   }
-  
+
   @Override
   public void begin(RepositorySessionBeginDelegate delegate) throws InvalidSessionTransitionException {
     // Check for the existence of special folders
     // and insert them if they don't exist.
     Cursor cur;
     try {
       Logger.debug(LOG_TAG, "Check and build special GUIDs.");
       dataAccessor.checkAndBuildSpecialGuids();
@@ -529,48 +536,122 @@ public class AndroidBrowserBookmarksRepo
       return;
     } catch (NullCursorException e) {
       delegate.onBeginFailed(e);
       return;
     } catch (Exception e) {
       delegate.onBeginFailed(e);
       return;
     }
-    
+
     // To deal with parent mapping of bookmarks we have to do some
     // hairy stuff. Here's the setup for it.
 
     Logger.debug(LOG_TAG, "Preparing folder ID mappings.");
 
     // Fake our root.
     Logger.debug(LOG_TAG, "Tracking places root as ID 0.");
-    idToGuid.put(0L, "places");
-    guidToID.put("places", 0L);
+    parentIDToGuidMap.put(0L, "places");
+    parentGuidToIDMap.put("places", 0L);
     try {
       cur.moveToFirst();
       while (!cur.isAfterLast()) {
         String guid = getGUID(cur);
         long id = RepoUtils.getLongFromCursor(cur, BrowserContract.Bookmarks._ID);
-        guidToID.put(guid, id);
-        idToGuid.put(id, guid);
+        parentGuidToIDMap.put(guid, id);
+        parentIDToGuidMap.put(id, guid);
         Logger.debug(LOG_TAG, "GUID " + guid + " maps to " + id);
         cur.moveToNext();
       }
     } finally {
       cur.close();
     }
     deletionManager = new BookmarksDeletionManager(dataAccessor, DEFAULT_DELETION_FLUSH_THRESHOLD);
+
+    // We just crawled the database enumerating all folders; we'll start the
+    // insertion manager with exactly these folders as the known parents (the
+    // collection is copied) in the manager constructor.
+    insertionManager = new BookmarksInsertionManager(DEFAULT_INSERTION_FLUSH_THRESHOLD, parentGuidToIDMap.keySet(), this);
+
     Logger.debug(LOG_TAG, "Done with initial setup of bookmarks session.");
     super.begin(delegate);
   }
 
+  /**
+   * Implement method of BookmarksInsertionManager.BookmarkInserter.
+   */
+  @Override
+  public boolean insertFolder(BookmarkRecord record) {
+    // A folder that is *not* deleted needs its androidID updated, so that
+    // updateBookkeeping can re-parent, etc.
+    Record toStore = prepareRecord(record);
+    try {
+      Uri recordURI = dbHelper.insert(toStore);
+      if (recordURI == null) {
+        delegate.onRecordStoreFailed(new RuntimeException("Got null URI inserting folder with guid " + toStore.guid + "."));
+        return false;
+      }
+      toStore.androidID = ContentUris.parseId(recordURI);
+      Logger.debug(LOG_TAG, "Inserted folder with guid " + toStore.guid + " as androidID " + toStore.androidID);
+
+      updateBookkeeping(toStore);
+    } catch (Exception e) {
+      delegate.onRecordStoreFailed(e);
+      return false;
+    }
+    trackRecord(toStore);
+    delegate.onRecordStoreSucceeded(toStore);
+    return true;
+  }
+
+  /**
+   * Implement method of BookmarksInsertionManager.BookmarkInserter.
+   */
+  @Override
+  public void bulkInsertNonFolders(Collection<BookmarkRecord> records) {
+    // All of these records are *not* deleted and *not* folders, so we don't
+    // need to update androidID at all!
+    // TODO: persist records that fail to insert for later retry.
+    ArrayList<Record> toStores = new ArrayList<Record>(records.size());
+    for (Record record : records) {
+      toStores.add(prepareRecord(record));
+    }
+
+    try {
+      int stored = dataAccessor.bulkInsert(toStores);
+      if (stored != toStores.size()) {
+        // Something failed; most pessimistic action is to declare that all insertions failed.
+        // TODO: perform the bulkInsert in a transaction and rollback unless all insertions succeed?
+        for (Record failed : toStores) {
+          delegate.onRecordStoreFailed(new RuntimeException("Possibly failed to bulkInsert non-folder with guid " + failed.guid + "."));
+        }
+        return;
+      }
+    } catch (NullCursorException e) {
+      delegate.onRecordStoreFailed(e); // TODO: include which records failed.
+      return;
+    }
+
+    // Success For All!
+    for (Record succeeded : toStores) {
+      try {
+        updateBookkeeping(succeeded);
+      } catch (Exception e) {
+        Logger.warn(LOG_TAG, "Got exception updating bookkeeping of non-folder with guid " + succeeded.guid + ".", e);
+      }
+      trackRecord(succeeded);
+      delegate.onRecordStoreSucceeded(succeeded);
+    }
+  }
+
   @Override
   public void finish(RepositorySessionFinishDelegate delegate) throws InactiveSessionException {
-    // Allow this to be GCed.
+    // Allow these to be GCed.
     deletionManager = null;
+    insertionManager = null;
 
     // Override finish to do this check; make sure all records
     // needing re-parenting have been re-parented.
     if (needsReparenting != 0) {
       Logger.error(LOG_TAG, "Finish called but " + needsReparenting +
                             " bookmark(s) have been placed in unsorted bookmarks and not been reparented.");
 
       // TODO: handling of failed reparenting.
@@ -666,30 +747,30 @@ public class AndroidBrowserBookmarksRepo
 
   /**
    * If the provided record doesn't have correct parent information,
    * update appropriate bookkeeping to improve the situation.
    *
    * @param bmk
    */
   private void handleParenting(BookmarkRecord bmk) {
-    if (guidToID.containsKey(bmk.parentID)) {
-      bmk.androidParentID = guidToID.get(bmk.parentID);
+    if (parentGuidToIDMap.containsKey(bmk.parentID)) {
+      bmk.androidParentID = parentGuidToIDMap.get(bmk.parentID);
 
       // Might as well set a basic position from the downloaded children array.
       JSONArray children = parentToChildArray.get(bmk.parentID);
       if (children != null) {
         int index = children.indexOf(bmk.guid);
         if (index >= 0) {
           bmk.androidPosition = index;
         }
       }
     }
     else {
-      bmk.androidParentID = guidToID.get("unfiled");
+      bmk.androidParentID = parentGuidToIDMap.get("unfiled");
       ArrayList<String> children;
       if (missingParentToChildren.containsKey(bmk.parentID)) {
         children = missingParentToChildren.get(bmk.parentID);
       } else {
         children = new ArrayList<String>();
       }
       children.add(bmk.guid);
       needsReparenting++;
@@ -714,18 +795,18 @@ public class AndroidBrowserBookmarksRepo
       return;
     }
 
     Logger.debug(LOG_TAG, "Updating bookkeeping for folder " + record.guid);
 
     // Mappings between ID and GUID.
     // TODO: update our persisted children arrays!
     // TODO: if our Android ID just changed, replace parents for all of our children.
-    guidToID.put(bmk.guid,      bmk.androidID);
-    idToGuid.put(bmk.androidID, bmk.guid);
+    parentGuidToIDMap.put(bmk.guid,      bmk.androidID);
+    parentIDToGuidMap.put(bmk.androidID, bmk.guid);
 
     JSONArray childArray = bmk.children;
 
     if (Logger.logVerbose(LOG_TAG)) {
       Logger.trace(LOG_TAG, bmk.guid + " has children " + childArray.toJSONString());
     }
     parentToChildArray.put(bmk.guid, childArray);
 
@@ -738,43 +819,60 @@ public class AndroidBrowserBookmarksRepo
         dataAccessor.updateParentAndPosition(child, bmk.androidID, position);
         needsReparenting--;
       }
       missingParentToChildren.remove(bmk.guid);
     }
   }
 
   @Override
+  protected void insert(Record record) throws NoGuidForIdException, NullCursorException, ParentNotFoundException {
+    try {
+      insertionManager.enqueueRecord((BookmarkRecord) record);
+    } catch (Exception e) {
+      throw new NullCursorException(e);
+    }
+  }
+
+  @Override
   protected void storeRecordDeletion(final Record record, final Record existingRecord) {
     if (SPECIAL_GUIDS_MAP.containsKey(record.guid)) {
       Logger.debug(LOG_TAG, "Told to delete record " + record.guid + ". Ignoring.");
       return;
     }
     final BookmarkRecord bookmarkRecord = (BookmarkRecord) record;
     final BookmarkRecord existingBookmark = (BookmarkRecord) existingRecord;
     final boolean isFolder = existingBookmark.isFolder();
     final String parentGUID = existingBookmark.parentID;
     deletionManager.deleteRecord(bookmarkRecord.guid, isFolder, parentGUID);
   }
 
-  protected void flushDeletions() {
+  protected void flushQueues() {
+    long now = now();
+    Logger.debug(LOG_TAG, "Applying remaining insertions.");
+    try {
+      insertionManager.finishUp();
+      Logger.debug(LOG_TAG, "Done applying remaining insertions.");
+    } catch (Exception e) {
+      Logger.warn(LOG_TAG, "Unable to apply remaining insertions.", e);
+    }
+
     Logger.debug(LOG_TAG, "Applying deletions.");
     try {
-      long now = now();
       untrackGUIDs(deletionManager.flushAll(getIDForGUID("unfiled"), now));
       Logger.debug(LOG_TAG, "Done applying deletions.");
     } catch (Exception e) {
       Logger.error(LOG_TAG, "Unable to apply deletions.", e);
     }
   }
 
   @SuppressWarnings("unchecked")
   private void finishUp() {
     try {
-      flushDeletions();
+      flushQueues();
       Logger.debug(LOG_TAG, "Have " + parentToChildArray.size() + " folders whose children might need repositioning.");
       for (Entry<String, JSONArray> entry : parentToChildArray.entrySet()) {
         String guid = entry.getKey();
         JSONArray onServer = entry.getValue();
         try {
           final long folderID = getIDForGUID(guid);
           JSONArray inDB = getChildrenArray(folderID, false);
 
@@ -819,16 +917,17 @@ public class AndroidBrowserBookmarksRepo
       super(delegate);
     }
 
     @Override
     public void run() {
       try {
         // Clear our queued deletions.
         deletionManager.clear();
+        insertionManager.clear();
         super.run();
       } catch (Exception ex) {
         delegate.onWipeFailed(ex);
         return;
       }
     }
   }
 
--- a/mobile/android/base/sync/repositories/android/AndroidBrowserHistoryDataAccessor.java
+++ b/mobile/android/base/sync/repositories/android/AndroidBrowserHistoryDataAccessor.java
@@ -13,17 +13,16 @@ import org.json.simple.JSONObject;
 import org.mozilla.gecko.db.BrowserContract;
 import org.mozilla.gecko.sync.Logger;
 import org.mozilla.gecko.sync.repositories.NullCursorException;
 import org.mozilla.gecko.sync.repositories.domain.HistoryRecord;
 import org.mozilla.gecko.sync.repositories.domain.Record;
 
 import android.content.ContentValues;
 import android.content.Context;
-import android.database.Cursor;
 import android.net.Uri;
 
 public class AndroidBrowserHistoryDataAccessor extends
     AndroidBrowserRepositoryDataAccessor {
 
   private AndroidBrowserHistoryDataExtender dataExtender;
 
   public AndroidBrowserHistoryDataAccessor(Context context) {
@@ -103,27 +102,25 @@ public class AndroidBrowserHistoryDataAc
   public static String[] GUID_AND_ID = new String[] { BrowserContract.History.GUID, BrowserContract.History._ID };
 
   /**
    * Insert records.
    * <p>
    * This inserts all the records (using <code>ContentProvider.bulkInsert</code>),
    * then inserts all the visit information (using the data extender's
    * <code>bulkInsert</code>, which internally uses a single database
-   * transaction), and then optionally updates the <code>androidID</code> of
-   * each record.
+   * transaction).
    *
    * @param records
-   *          The records to insert.
-   * @param fetchFreshAndroidIDs
-   *          <code>true</code> to update the <code>androidID</code> of each
-   *          record; <code>false</code> to invalidate them all.
+   *          the records to insert.
+   * @return
+   *          the number of records actually inserted.
    * @throws NullCursorException
    */
-  public void bulkInsert(ArrayList<HistoryRecord> records, boolean fetchFreshAndroidIDs) throws NullCursorException {
+  public int bulkInsert(ArrayList<HistoryRecord> records) throws NullCursorException {
     if (records.isEmpty()) {
       Logger.debug(LOG_TAG, "No records to insert, returning.");
     }
 
     int size = records.size();
     ContentValues[] cvs = new ContentValues[size];
     String[] guids = new String[size];
     Map<String, Record> guidToRecord = new HashMap<String, Record>();
@@ -144,42 +141,11 @@ public class AndroidBrowserHistoryDataAc
       Logger.debug(LOG_TAG, "Inserted " + inserted + " records, as expected.");
     } else {
       Logger.debug(LOG_TAG, "Inserted " +
                    inserted + " records but expected " +
                    size     + " records; continuing to update visits.");
     }
     // Then update the history visits.
     dataExtender.bulkInsert(records);
-
-    // And finally patch up the androidIDs.
-    if (!fetchFreshAndroidIDs) {
-      return;
-    }
-
-    // We do this here to save a few loops.
-    String guidIn = RepoUtils.computeSQLInClause(guids.length, BrowserContract.History.GUID);
-    Cursor cursor = queryHelper.safeQuery("", GUID_AND_ID, guidIn, guids, null);
-    int guidIndex = cursor.getColumnIndexOrThrow(BrowserContract.History.GUID);
-    int androidIDIndex = cursor.getColumnIndexOrThrow(BrowserContract.History._ID);
-
-    try {
-      cursor.moveToFirst();
-      while (!cursor.isAfterLast()) {
-        String guid = cursor.getString(guidIndex);
-        int androidID = cursor.getInt(androidIDIndex);
-        cursor.moveToNext();
-
-        Record record = guidToRecord.get(guid);
-        if (record == null) {
-          // Should never happen!
-          Logger.warn(LOG_TAG, "Failed to update androidID for record with guid " + guid + ".");
-          continue;
-        }
-        record.androidID = androidID;
-      }
-    } finally {
-      if (cursor != null) {
-        cursor.close();
-      }
-    }
+    return inserted;
   }
 }
--- a/mobile/android/base/sync/repositories/android/AndroidBrowserHistoryRepositorySession.java
+++ b/mobile/android/base/sync/repositories/android/AndroidBrowserHistoryRepositorySession.java
@@ -122,48 +122,47 @@ public class AndroidBrowserHistoryReposi
 
   @Override
   protected Record prepareRecord(Record record) {
     return record;
   }
 
   @Override
   public void abort() {
-    ((AndroidBrowserHistoryDataAccessor) dbHelper).closeExtender();
+    if (dbHelper != null) {
+      ((AndroidBrowserHistoryDataAccessor) dbHelper).closeExtender();
+      dbHelper = null;
+    }
     super.abort();
   }
 
   @Override
   public void finish(final RepositorySessionFinishDelegate delegate) throws InactiveSessionException {
-    ((AndroidBrowserHistoryDataAccessor) dbHelper).closeExtender();
+    if (dbHelper != null) {
+      ((AndroidBrowserHistoryDataAccessor) dbHelper).closeExtender();
+      dbHelper = null;
+    }
     super.finish(delegate);
   }
 
   protected Object recordsBufferMonitor = new Object();
   protected ArrayList<HistoryRecord> recordsBuffer = new ArrayList<HistoryRecord>();
 
   /**
    * Queue record for insertion, possibly flushing the queue.
    * <p>
    * Must be called on <code>storeWorkQueue</code> thread! But this is only
    * called from <code>store</code>, which is called on the queue thread.
    *
    * @param record
    *          A <code>Record</code> with a GUID that is not present locally.
-   * @return The <code>Record</code> to be inserted. <b>Warning:</b> the
-   *         <code>androidID</code> is not valid! It will be set after the
-   *         records are flushed to the database.
    */
   @Override
-  protected Record insert(Record record) throws NoGuidForIdException, NullCursorException, ParentNotFoundException {
-    HistoryRecord toStore = (HistoryRecord) prepareRecord(record);
-    toStore.androidID = -111; // Hopefully this special value will make it easy to catch future errors.
-    updateBookkeeping(toStore); // Does not use androidID -- just GUID -> String map.
-    enqueueNewRecord(toStore);
-    return toStore;
+  protected void insert(Record record) throws NoGuidForIdException, NullCursorException, ParentNotFoundException {
+    enqueueNewRecord((HistoryRecord) prepareRecord(record));
   }
 
   /**
    * Batch incoming records until some reasonable threshold is hit or storeDone
    * is received.
    * <p>
    * Must be called on <code>storeWorkQueue</code> thread!
    *
@@ -193,28 +192,54 @@ public class AndroidBrowserHistoryReposi
       Logger.debug(LOG_TAG, "No records to flush, returning.");
       return;
     }
 
     final ArrayList<HistoryRecord> outgoing = recordsBuffer;
     recordsBuffer = new ArrayList<HistoryRecord>();
     Logger.debug(LOG_TAG, "Flushing " + outgoing.size() + " records to database.");
     // TODO: move bulkInsert to AndroidBrowserDataAccessor?
-    ((AndroidBrowserHistoryDataAccessor) dbHelper).bulkInsert(outgoing, false); // Don't need to update any androidIDs.
+    int inserted = ((AndroidBrowserHistoryDataAccessor) dbHelper).bulkInsert(outgoing);
+    if (inserted != outgoing.size()) {
+      // Something failed; most pessimistic action is to declare that all insertions failed.
+      // TODO: perform the bulkInsert in a transaction and rollback unless all insertions succeed?
+      for (HistoryRecord failed : outgoing) {
+        delegate.onRecordStoreFailed(new RuntimeException("Failed to insert history item with guid " + failed.guid + "."));
+      }
+      return;
+    }
+
+    // All good, everybody succeeded.
+    for (HistoryRecord succeeded : outgoing) {
+      try {
+        // Does not use androidID -- just GUID -> String map.
+        updateBookkeeping(succeeded);
+      } catch (NoGuidForIdException e) {
+        // Should not happen.
+        throw new NullCursorException(e);
+      } catch (ParentNotFoundException e) {
+        // Should not happen.
+        throw new NullCursorException(e);
+      } catch (NullCursorException e) {
+        throw e;
+      }
+      trackRecord(succeeded);
+      delegate.onRecordStoreSucceeded(succeeded); // At this point, we are really inserted.
+    }
   }
 
   @Override
   public void storeDone() {
     storeWorkQueue.execute(new Runnable() {
       @Override
       public void run() {
         synchronized (recordsBufferMonitor) {
           try {
             flushNewRecords();
-          } catch (NullCursorException e) {
+          } catch (Exception e) {
             Logger.warn(LOG_TAG, "Error flushing records to database.", e);
           }
         }
         storeDone(System.currentTimeMillis());
       }
     });
   }
 }
\ No newline at end of file
--- a/mobile/android/base/sync/repositories/android/AndroidBrowserRepositoryDataAccessor.java
+++ b/mobile/android/base/sync/repositories/android/AndroidBrowserRepositoryDataAccessor.java
@@ -1,14 +1,16 @@
 /* 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/. */
 
 package org.mozilla.gecko.sync.repositories.android;
 
+import java.util.List;
+
 import org.mozilla.gecko.db.BrowserContract;
 import org.mozilla.gecko.sync.Logger;
 import org.mozilla.gecko.sync.repositories.NullCursorException;
 import org.mozilla.gecko.sync.repositories.domain.Record;
 
 import android.content.ContentValues;
 import android.content.Context;
 import android.database.Cursor;
@@ -172,9 +174,60 @@ public abstract class AndroidBrowserRepo
     String[] args = new String[] { guid };
 
     int updated = context.getContentResolver().update(getUri(), cv, where, args);
     if (updated == 1) {
       return;
     }
     Logger.warn(LOG_TAG, "Unexpectedly updated " + updated + " rows for guid " + guid);
   }
+
+  /**
+   * Insert records.
+   * <p>
+   * This inserts all the records (using <code>ContentProvider.bulkInsert</code>),
+   * but does <b>not</b> update the <code>androidID</code> of each record.
+   *
+   * @param records
+   *          the records to insert.
+   * @return
+   *          the number of records actually inserted.
+   * @throws NullCursorException
+   */
+  public int bulkInsert(List<Record> records) throws NullCursorException {
+    if (records.isEmpty()) {
+      Logger.debug(LOG_TAG, "No records to insert, returning.");
+    }
+
+    int size = records.size();
+    ContentValues[] cvs = new ContentValues[size];
+    int index = 0;
+    for (Record record : records) {
+      try {
+        cvs[index] = getContentValues(record);
+        index += 1;
+      } catch (Exception e) {
+        Logger.warn(LOG_TAG, "Got exception in getContentValues for record with guid " + record.guid, e);
+      }
+    }
+
+    if (index != size) {
+      // bulkInsert treats null ContentValues as blank rows, which we don't want
+      // to insert into the database.
+      // We expect exceptions in getContentValues to be exceedingly rare, so we
+      // re-allocate in the (rare) error case and maintain a fast path for the
+      // success case.
+      size = index;
+      ContentValues[] temp = new ContentValues[size];
+      System.arraycopy(cvs, 0, temp, 0, size); // No java.util.Arrays.copyOf in older Android SDKs.
+    }
+
+    int inserted = context.getContentResolver().bulkInsert(getUri(), cvs);
+    if (inserted == size) {
+      Logger.debug(LOG_TAG, "Inserted " + inserted + " records, as expected.");
+    } else {
+      Logger.debug(LOG_TAG, "Inserted " +
+                   inserted + " records but expected " +
+                   size     + " records.");
+    }
+    return inserted;
+  }
 }
--- a/mobile/android/base/sync/repositories/android/AndroidBrowserRepositorySession.java
+++ b/mobile/android/base/sync/repositories/android/AndroidBrowserRepositorySession.java
@@ -17,16 +17,17 @@ import org.mozilla.gecko.sync.repositori
 import org.mozilla.gecko.sync.repositories.NullCursorException;
 import org.mozilla.gecko.sync.repositories.ParentNotFoundException;
 import org.mozilla.gecko.sync.repositories.ProfileDatabaseException;
 import org.mozilla.gecko.sync.repositories.RecordFilter;
 import org.mozilla.gecko.sync.repositories.Repository;
 import org.mozilla.gecko.sync.repositories.StoreTrackingRepositorySession;
 import org.mozilla.gecko.sync.repositories.delegates.RepositorySessionBeginDelegate;
 import org.mozilla.gecko.sync.repositories.delegates.RepositorySessionFetchRecordsDelegate;
+import org.mozilla.gecko.sync.repositories.delegates.RepositorySessionFinishDelegate;
 import org.mozilla.gecko.sync.repositories.delegates.RepositorySessionGuidsSinceDelegate;
 import org.mozilla.gecko.sync.repositories.delegates.RepositorySessionWipeDelegate;
 import org.mozilla.gecko.sync.repositories.domain.Record;
 
 import android.content.ContentUris;
 import android.database.Cursor;
 import android.net.Uri;
 
@@ -48,19 +49,19 @@ import android.net.Uri;
  *
  * Similarly, all store calls go through the appropriate store queue. This
  * ensures that store() and storeDone() consequences occur before-after.
  *
  * @author rnewman
  *
  */
 public abstract class AndroidBrowserRepositorySession extends StoreTrackingRepositorySession {
+  public static final String LOG_TAG = "BrowserRepoSession";
 
   protected AndroidBrowserRepositoryDataAccessor dbHelper;
-  public static final String LOG_TAG = "BrowserRepoSession";
   private HashMap<String, String> recordToGuid;
 
   public AndroidBrowserRepositorySession(Repository repository) {
     super(repository);
   }
 
   /**
    * Retrieve a record from a cursor. Act as if we don't know the final contents of
@@ -143,16 +144,23 @@ public abstract class AndroidBrowserRepo
     } catch (Exception e) {
       deferredDelegate.onBeginFailed(e);
       return;
     }
     storeTracker = createStoreTracker();
     deferredDelegate.onBeginSucceeded(this);
   }
 
+  @Override
+  public void finish(RepositorySessionFinishDelegate delegate) throws InactiveSessionException {
+    dbHelper = null;
+    recordToGuid = null;
+    super.finish(delegate);
+  }
+
   protected abstract String buildRecordString(Record record);
 
   protected void checkDatabase() throws ProfileDatabaseException, NullCursorException {
     Logger.info(LOG_TAG, "BEGIN: checking database.");
     try {
       dbHelper.fetch(new String[] { "none" }).close();
       Logger.info(LOG_TAG, "END: checking database.");
     } catch (NullPointerException e) {
@@ -348,26 +356,31 @@ public abstract class AndroidBrowserRepo
     }
   }
 
   @Override
   public void fetchAll(RepositorySessionFetchRecordsDelegate delegate) {
     this.fetchSince(0, delegate);
   }
 
+  protected int storeCount = 0;
+
   @Override
   public void store(final Record record) throws NoStoreDelegateException {
     if (delegate == null) {
       throw new NoStoreDelegateException();
     }
     if (record == null) {
       Logger.error(LOG_TAG, "Record sent to store was null");
       throw new IllegalArgumentException("Null record passed to AndroidBrowserRepositorySession.store().");
     }
 
+    storeCount += 1;
+    Logger.debug(LOG_TAG, "Storing record with GUID " + record.guid + " (stored " + storeCount + " records this session).");
+
     // Store Runnables *must* complete synchronously. It's OK, they
     // run on a background thread.
     Runnable command = new Runnable() {
 
       @Override
       public void run() {
         if (!isActive()) {
           Logger.warn(LOG_TAG, "AndroidBrowserRepositorySession is inactive. Store failing.");
@@ -452,19 +465,17 @@ public abstract class AndroidBrowserRepo
           if (existingRecord == null) {
             trace("Looking up match for record " + record.guid);
             existingRecord = findExistingRecord(record);
           }
 
           if (existingRecord == null) {
             // The record is new.
             trace("No match. Inserting.");
-            Record inserted = insert(record);
-            trackRecord(inserted);
-            delegate.onRecordStoreSucceeded(inserted);
+            insert(record);
             return;
           }
 
           // We found a local dupe.
           trace("Incoming record " + record.guid + " dupes to local record " + existingRecord.guid);
 
           // Populate more expensive fields prior to reconciling.
           existingRecord = transformRecord(existingRecord);
@@ -526,26 +537,29 @@ public abstract class AndroidBrowserRepo
    */
   protected void storeRecordDeletion(final Record record, final Record existingRecord) {
     // TODO: we ought to mark the record as deleted rather than purging it,
     // in order to support syncing to multiple destinations. Bug 722607.
     dbHelper.purgeGuid(record.guid);
     delegate.onRecordStoreSucceeded(record);
   }
 
-  protected Record insert(Record record) throws NoGuidForIdException, NullCursorException, ParentNotFoundException {
+  protected void insert(Record record) throws NoGuidForIdException, NullCursorException, ParentNotFoundException {
     Record toStore = prepareRecord(record);
     Uri recordURI = dbHelper.insert(toStore);
-    long id = ContentUris.parseId(recordURI);
-    Logger.debug(LOG_TAG, "Inserted as " + id);
+    if (recordURI == null) {
+      throw new NullCursorException(new RuntimeException("Got null URI inserting record with guid " + record.guid));
+    }
+    toStore.androidID = ContentUris.parseId(recordURI);
 
-    toStore.androidID = id;
     updateBookkeeping(toStore);
-    Logger.debug(LOG_TAG, "insert() returning record " + toStore.guid);
-    return toStore;
+    trackRecord(toStore);
+    delegate.onRecordStoreSucceeded(toStore);
+
+    Logger.debug(LOG_TAG, "Inserted record with guid " + toStore.guid + " as androidID " + toStore.androidID);
   }
 
   protected Record replace(Record newRecord, Record existingRecord) throws NoGuidForIdException, NullCursorException, ParentNotFoundException {
     Record toStore = prepareRecord(newRecord);
 
     // newRecord should already have suitable androidID and guid.
     dbHelper.update(existingRecord.guid, toStore);
     updateBookkeeping(toStore);
new file mode 100644
--- /dev/null
+++ b/mobile/android/base/sync/repositories/android/BookmarksInsertionManager.java
@@ -0,0 +1,298 @@
+/* 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/. */
+
+package org.mozilla.gecko.sync.repositories.android;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedHashSet;
+import java.util.Map;
+import java.util.Set;
+
+import org.mozilla.gecko.sync.Logger;
+import org.mozilla.gecko.sync.Utils;
+import org.mozilla.gecko.sync.repositories.domain.BookmarkRecord;
+
+/**
+ * Queue up insertions:
+ * <ul>
+ * <li>Folder inserts where the parent is known. Do these immediately, because
+ * they allow other records to be inserted. Requires bookkeeping updates. On
+ * insert, flush the next set.</li>
+ * <li>Regular inserts where the parent is known. These can happen whenever.
+ * Batch for speed.</li>
+ * <li>Records where the parent is not known. These can be flushed out when the
+ * parent is known, or entered as orphans. This can be a queue earlier in the
+ * process, so they don't get assigned to Unsorted. Feed into the main batch
+ * when the parent arrives.</li>
+ * </ul>
+ * <p>
+ * Deletions are always done at the end so that orphaning is minimized, and
+ * that's why we are batching folders and non-folders separately.
+ * <p>
+ * Updates are always applied as they arrive.
+ * <p>
+ * Note that this class is not thread safe. This should be fine: call it only
+ * from within a store runnable.
+ */
+public class BookmarksInsertionManager {
+  public static final String LOG_TAG = "BookmarkInsert";
+  public static boolean DEBUG = false;
+
+  protected final int flushThreshold;
+  protected final BookmarkInserter inserter;
+
+  /**
+   * Folders that have been successfully inserted.
+   */
+  private final Set<String> insertedFolders = new HashSet<String>();
+
+  /**
+   * Non-folders waiting for bulk insertion.
+   * <p>
+   * We write in insertion order to keep things easy to debug.
+   */
+  private final Set<BookmarkRecord> nonFoldersToWrite = new LinkedHashSet<BookmarkRecord>();
+
+  /**
+   * Map from parent folder GUID to child records (folders and non-folders)
+   * waiting to be enqueued after parent folder is inserted.
+   */
+  private final Map<String, Set<BookmarkRecord>> recordsWaitingForParent = new HashMap<String, Set<BookmarkRecord>>();
+
+  /**
+   * Create an instance to be used for tracking insertions in a bookmarks
+   * repository session.
+   *
+   * @param flushThreshold
+   *        When this many non-folder records have been stored for insertion,
+   *        an incremental flush occurs.
+   * @param insertedFolders
+   *        The GUIDs of all the folders already inserted into the database.
+   * @param inserter
+   *        The <code>BookmarkInsert</code> to use.
+   */
+  public BookmarksInsertionManager(int flushThreshold, Collection<String> insertedFolders, BookmarkInserter inserter) {
+    this.flushThreshold = flushThreshold;
+    this.insertedFolders.addAll(insertedFolders);
+    this.inserter = inserter;
+  }
+
+  protected void addRecordWithUnwrittenParent(BookmarkRecord record) {
+    Set<BookmarkRecord> destination = recordsWaitingForParent.get(record.parentID);
+    if (destination == null) {
+      destination = new LinkedHashSet<BookmarkRecord>();
+      recordsWaitingForParent.put(record.parentID, destination);
+    }
+    destination.add(record);
+  }
+
+  /**
+   * If <code>record</code> is a folder, insert it immediately; if it is a
+   * non-folder, enqueue it. Then do the same for any records waiting for this record.
+   *
+   * @param record
+   *          the <code>BookmarkRecord</code> to enqueue.
+   */
+  protected void recursivelyEnqueueRecordAndChildren(BookmarkRecord record) {
+    if (record.isFolder()) {
+      if (!inserter.insertFolder(record)) {
+        Logger.warn(LOG_TAG, "Folder with known parent with guid " + record.parentID + " failed to insert!");
+        return;
+      }
+      Logger.debug(LOG_TAG, "Folder with known parent with guid " + record.parentID + " inserted; adding to inserted folders.");
+      insertedFolders.add(record.guid);
+    } else {
+      Logger.debug(LOG_TAG, "Non-folder has known parent with guid " + record.parentID + "; adding to insertion queue.");
+      nonFoldersToWrite.add(record);
+    }
+
+    // Now process record's children.
+    Set<BookmarkRecord> waiting = recordsWaitingForParent.remove(record.guid);
+    if (waiting == null) {
+      return;
+    }
+    for (BookmarkRecord waiter : waiting) {
+      recursivelyEnqueueRecordAndChildren(waiter);
+    }
+  }
+
+  /**
+   * Enqueue a folder.
+   *
+   * @param record
+   *          the folder to enqueue.
+   */
+  protected void enqueueFolder(BookmarkRecord record) {
+    Logger.debug(LOG_TAG, "Inserting folder with guid " + record.guid);
+
+    if (!insertedFolders.contains(record.parentID)) {
+      Logger.debug(LOG_TAG, "Folder has unknown parent with guid " + record.parentID + "; keeping until we see the parent.");
+      addRecordWithUnwrittenParent(record);
+      return;
+    }
+
+    // Parent is known; add as much of the tree as this roots.
+    recursivelyEnqueueRecordAndChildren(record);
+    flushNonFoldersIfNecessary();
+  }
+
+  /**
+   * Enqueue a non-folder.
+   *
+   * @param record
+   *          the non-folder to enqueue.
+   */
+  protected void enqueueNonFolder(BookmarkRecord record) {
+    Logger.debug(LOG_TAG, "Inserting non-folder with guid " + record.guid);
+
+    if (!insertedFolders.contains(record.parentID)) {
+      Logger.debug(LOG_TAG, "Non-folder has unknown parent with guid " + record.parentID + "; keeping until we see the parent.");
+      addRecordWithUnwrittenParent(record);
+      return;
+    }
+
+    // Parent is known; add to insertion queue and maybe write.
+    Logger.debug(LOG_TAG, "Non-folder has known parent with guid " + record.parentID + "; adding to insertion queue.");
+    nonFoldersToWrite.add(record);
+    flushNonFoldersIfNecessary();
+  }
+
+  /**
+   * Enqueue a bookmark record for eventual insertion.
+   *
+   * @param record
+   *          the <code>BookmarkRecord</code> to enqueue.
+   */
+  public void enqueueRecord(BookmarkRecord record) {
+    if (record.isFolder()) {
+      enqueueFolder(record);
+    } else {
+      enqueueNonFolder(record);
+    }
+    if (DEBUG) {
+      dumpState();
+    }
+  }
+
+  /**
+   * Flush non-folders; empties the insertion queue entirely.
+   */
+  protected void flushNonFolders() {
+    inserter.bulkInsertNonFolders(nonFoldersToWrite); // All errors are handled in bulkInsertNonFolders.
+    nonFoldersToWrite.clear();
+  }
+
+  /**
+   * Flush non-folder insertions if there are many of them; empties the
+   * insertion queue entirely.
+   */
+  protected void flushNonFoldersIfNecessary() {
+    int num = nonFoldersToWrite.size();
+    if (num < flushThreshold) {
+      Logger.debug(LOG_TAG, "Incremental flush called with " + num + " < " + flushThreshold + " non-folders; not flushing.");
+      return;
+    }
+    Logger.debug(LOG_TAG, "Incremental flush called with " + num + " non-folders; flushing.");
+    flushNonFolders();
+  }
+
+  /**
+   * Insert all remaining folders followed by all remaining non-folders,
+   * regardless of whether parent records have been successfully inserted.
+   */
+  public void finishUp() {
+    // Iterate through all waiting records, writing the folders and collecting
+    // the non-folders for bulk insertion.
+    int numFolders = 0;
+    int numNonFolders = 0;
+    for (Set<BookmarkRecord> records : recordsWaitingForParent.values()) {
+      for (BookmarkRecord record : records) {
+        if (!record.isFolder()) {
+          numNonFolders += 1;
+          nonFoldersToWrite.add(record);
+          continue;
+        }
+
+        numFolders += 1;
+        if (!inserter.insertFolder(record)) {
+          Logger.warn(LOG_TAG, "Folder with known parent with guid " + record.parentID + " failed to insert!");
+          continue;
+        }
+
+        Logger.debug(LOG_TAG, "Folder with known parent with guid " + record.parentID + " inserted; adding to inserted folders.");
+        insertedFolders.add(record.guid);
+      }
+    }
+    recordsWaitingForParent.clear();
+    flushNonFolders();
+
+    Logger.debug(LOG_TAG, "finishUp inserted " +
+        numFolders + " folders without known parents and " +
+        numNonFolders + " non-folders without known parents.");
+    if (DEBUG) {
+      dumpState();
+    }
+  }
+
+  public void clear() {
+    this.insertedFolders.clear();
+    this.nonFoldersToWrite.clear();
+    this.recordsWaitingForParent.clear();
+  }
+
+  // For debugging.
+  public boolean isClear() {
+    return nonFoldersToWrite.isEmpty() && recordsWaitingForParent.isEmpty();
+  }
+
+  // For debugging.
+  public void dumpState() {
+    ArrayList<String> readies = new ArrayList<String>();
+    for (BookmarkRecord record : nonFoldersToWrite) {
+      readies.add(record.guid);
+    }
+    String ready = Utils.toCommaSeparatedString(new ArrayList<String>(readies));
+
+    ArrayList<String> waits = new ArrayList<String>();
+    for (Set<BookmarkRecord> recs : recordsWaitingForParent.values()) {
+      for (BookmarkRecord rec : recs) {
+        waits.add(rec.guid);
+      }
+    }
+    String waiting = Utils.toCommaSeparatedString(waits);
+    String known = Utils.toCommaSeparatedString(insertedFolders);
+
+    Logger.debug(LOG_TAG, "Q=(" + ready + "), W = (" + waiting + "), P=(" + known + ")");
+  }
+
+  public interface BookmarkInserter {
+    /**
+     * Insert a single folder.
+     * <p>
+     * All exceptions should be caught and all delegate callbacks invoked here.
+     *
+     * @param record
+     *          the record to insert.
+     * @return
+     *          <code>true</code> if the folder was inserted; <code>false</code> otherwise.
+     */
+    public boolean insertFolder(BookmarkRecord record);
+
+    /**
+     * Insert many non-folders. Each non-folder's parent was already present in
+     * the database before this <code>BookmarkInsertionsManager</code> was
+     * created, or had <code>insertFolder</code> called with it as argument (and
+     * possibly was not inserted).
+     * <p>
+     * All exceptions should be caught and all delegate callbacks invoked here.
+     *
+     * @param record
+     *          the record to insert.
+     */
+    public void bulkInsertNonFolders(Collection<BookmarkRecord> records);
+  }
+}
--- a/mobile/android/sync/java-sources.mn
+++ b/mobile/android/sync/java-sources.mn
@@ -1,1 +1,1 @@
-sync/AlreadySyncingException.java sync/CollectionKeys.java sync/CommandProcessor.java sync/CommandRunner.java sync/CredentialsSource.java sync/crypto/CryptoException.java sync/crypto/CryptoInfo.java sync/crypto/HKDF.java sync/crypto/HMACVerificationException.java sync/crypto/KeyBundle.java sync/crypto/MissingCryptoInputException.java sync/crypto/NoKeyBundleException.java sync/crypto/PersistedCrypto5Keys.java sync/CryptoRecord.java sync/DelayedWorkTracker.java sync/delegates/ClientsDataDelegate.java sync/delegates/FreshStartDelegate.java sync/delegates/GlobalSessionCallback.java sync/delegates/InfoCollectionsDelegate.java sync/delegates/KeyUploadDelegate.java sync/delegates/MetaGlobalDelegate.java sync/delegates/WipeServerDelegate.java sync/EngineSettings.java sync/ExtendedJSONObject.java sync/GlobalSession.java sync/HTTPFailureException.java sync/InfoCollections.java sync/jpake/BigIntegerHelper.java sync/jpake/Gx3OrGx4IsZeroOrOneException.java sync/jpake/IncorrectZkpException.java sync/jpake/JPakeClient.java sync/jpake/JPakeCrypto.java sync/jpake/JPakeJson.java sync/jpake/JPakeNoActivePairingException.java sync/jpake/JPakeNumGenerator.java sync/jpake/JPakeNumGeneratorRandom.java sync/jpake/JPakeParty.java sync/jpake/JPakeRequest.java sync/jpake/JPakeRequestDelegate.java sync/jpake/JPakeResponse.java sync/jpake/stage/CompleteStage.java sync/jpake/stage/ComputeFinalStage.java sync/jpake/stage/ComputeKeyVerificationStage.java sync/jpake/stage/ComputeStepOneStage.java sync/jpake/stage/ComputeStepTwoStage.java sync/jpake/stage/DecryptDataStage.java sync/jpake/stage/DeleteChannel.java sync/jpake/stage/GetChannelStage.java sync/jpake/stage/GetRequestStage.java sync/jpake/stage/JPakeStage.java sync/jpake/stage/PutRequestStage.java sync/jpake/stage/VerifyPairingStage.java sync/jpake/Zkp.java sync/KeyBundleProvider.java sync/Logger.java sync/MetaGlobal.java sync/MetaGlobalException.java sync/MetaGlobalMissingEnginesException.java sync/MetaGlobalNotSetException.java sync/middleware/Crypto5MiddlewareRepository.java sync/middleware/Crypto5MiddlewareRepositorySession.java sync/middleware/MiddlewareRepository.java sync/middleware/MiddlewareRepositorySession.java sync/net/BaseResource.java sync/net/CompletedEntity.java sync/net/ConnectionMonitorThread.java sync/net/HandleProgressException.java sync/net/HttpResponseObserver.java sync/net/Resource.java sync/net/ResourceDelegate.java sync/net/SyncResourceDelegate.java sync/net/SyncResponse.java sync/net/SyncStorageCollectionRequest.java sync/net/SyncStorageCollectionRequestDelegate.java sync/net/SyncStorageRecordRequest.java sync/net/SyncStorageRequest.java sync/net/SyncStorageRequestDelegate.java sync/net/SyncStorageRequestIncrementalDelegate.java sync/net/SyncStorageResponse.java sync/net/TLSSocketFactory.java sync/net/WBOCollectionRequestDelegate.java sync/net/WBORequestDelegate.java sync/NoCollectionKeysSetException.java sync/NodeAuthenticationException.java sync/NonArrayJSONException.java sync/NonObjectJSONException.java sync/NullClusterURLException.java sync/PersistedMetaGlobal.java sync/PrefsSource.java sync/repositories/android/AndroidBrowserBookmarksDataAccessor.java sync/repositories/android/AndroidBrowserBookmarksRepository.java sync/repositories/android/AndroidBrowserBookmarksRepositorySession.java sync/repositories/android/AndroidBrowserHistoryDataAccessor.java sync/repositories/android/AndroidBrowserHistoryDataExtender.java sync/repositories/android/AndroidBrowserHistoryRepository.java sync/repositories/android/AndroidBrowserHistoryRepositorySession.java sync/repositories/android/AndroidBrowserRepository.java sync/repositories/android/AndroidBrowserRepositoryDataAccessor.java sync/repositories/android/AndroidBrowserRepositorySession.java sync/repositories/android/BookmarksDeletionManager.java sync/repositories/android/BrowserContractHelpers.java sync/repositories/android/CachedSQLiteOpenHelper.java sync/repositories/android/ClientsDatabase.java sync/repositories/android/ClientsDatabaseAccessor.java sync/repositories/android/FennecControlHelper.java sync/repositories/android/FennecTabsRepository.java sync/repositories/android/FormHistoryRepositorySession.java sync/repositories/android/PasswordsRepositorySession.java sync/repositories/android/RepoUtils.java sync/repositories/BookmarkNeedsReparentingException.java sync/repositories/BookmarksRepository.java sync/repositories/ConstrainedServer11Repository.java sync/repositories/delegates/DeferrableRepositorySessionCreationDelegate.java sync/repositories/delegates/DeferredRepositorySessionBeginDelegate.java sync/repositories/delegates/DeferredRepositorySessionFetchRecordsDelegate.java sync/repositories/delegates/DeferredRepositorySessionFinishDelegate.java sync/repositories/delegates/DeferredRepositorySessionStoreDelegate.java sync/repositories/delegates/RepositorySessionBeginDelegate.java sync/repositories/delegates/RepositorySessionCleanDelegate.java sync/repositories/delegates/RepositorySessionCreationDelegate.java sync/repositories/delegates/RepositorySessionFetchRecordsDelegate.java sync/repositories/delegates/RepositorySessionFinishDelegate.java sync/repositories/delegates/RepositorySessionGuidsSinceDelegate.java sync/repositories/delegates/RepositorySessionStoreDelegate.java sync/repositories/delegates/RepositorySessionWipeDelegate.java sync/repositories/domain/BookmarkRecord.java sync/repositories/domain/BookmarkRecordFactory.java sync/repositories/domain/ClientRecord.java sync/repositories/domain/ClientRecordFactory.java sync/repositories/domain/FormHistoryRecord.java sync/repositories/domain/HistoryRecord.java sync/repositories/domain/HistoryRecordFactory.java sync/repositories/domain/PasswordRecord.java sync/repositories/domain/Record.java sync/repositories/domain/TabsRecord.java sync/repositories/HashSetStoreTracker.java sync/repositories/HistoryRepository.java sync/repositories/IdentityRecordFactory.java sync/repositories/InactiveSessionException.java sync/repositories/InvalidBookmarkTypeException.java sync/repositories/InvalidRequestException.java sync/repositories/InvalidSessionTransitionException.java sync/repositories/MultipleRecordsForGuidException.java sync/repositories/NoContentProviderException.java sync/repositories/NoGuidForIdException.java sync/repositories/NoStoreDelegateException.java sync/repositories/NullCursorException.java sync/repositories/ParentNotFoundException.java sync/repositories/ProfileDatabaseException.java sync/repositories/RecordFactory.java sync/repositories/RecordFilter.java sync/repositories/Repository.java sync/repositories/RepositorySession.java sync/repositories/RepositorySessionBundle.java sync/repositories/Server11Repository.java sync/repositories/Server11RepositorySession.java sync/repositories/StoreTracker.java sync/repositories/StoreTrackingRepositorySession.java sync/setup/activities/AccountActivity.java sync/setup/activities/ActivityUtils.java sync/setup/activities/SetupFailureActivity.java sync/setup/activities/SetupSuccessActivity.java sync/setup/activities/SetupSyncActivity.java sync/setup/Constants.java sync/setup/InvalidSyncKeyException.java sync/setup/SyncAccounts.java sync/setup/SyncAuthenticatorService.java sync/stage/AbstractNonRepositorySyncStage.java sync/stage/AndroidBrowserBookmarksServerSyncStage.java sync/stage/AndroidBrowserHistoryServerSyncStage.java sync/stage/CheckPreconditionsStage.java sync/stage/CompletedStage.java sync/stage/EnsureClusterURLStage.java sync/stage/EnsureCrypto5KeysStage.java sync/stage/FennecTabsServerSyncStage.java sync/stage/FetchInfoCollectionsStage.java sync/stage/FetchMetaGlobalStage.java sync/stage/FormHistoryServerSyncStage.java sync/stage/GlobalSyncStage.java sync/stage/NoSuchStageException.java sync/stage/NoSyncIDException.java sync/stage/PasswordsServerSyncStage.java sync/stage/ServerSyncStage.java sync/stage/SyncClientsEngineStage.java sync/StubActivity.java sync/syncadapter/SyncAdapter.java sync/syncadapter/SyncService.java sync/SyncConfiguration.java sync/SyncConfigurationException.java sync/SyncException.java sync/synchronizer/ConcurrentRecordConsumer.java sync/synchronizer/RecordConsumer.java sync/synchronizer/RecordsChannel.java sync/synchronizer/RecordsChannelDelegate.java sync/synchronizer/RecordsConsumerDelegate.java sync/synchronizer/SerialRecordConsumer.java sync/synchronizer/SessionNotBegunException.java sync/synchronizer/Synchronizer.java sync/synchronizer/SynchronizerDelegate.java sync/synchronizer/SynchronizerSession.java sync/synchronizer/SynchronizerSessionDelegate.java sync/synchronizer/UnbundleError.java sync/synchronizer/UnexpectedSessionException.java sync/SynchronizerConfiguration.java sync/SynchronizerConfigurations.java sync/ThreadPool.java sync/UnexpectedJSONException.java sync/UnknownSynchronizerConfigurationVersionException.java sync/Utils.java
+sync/AlreadySyncingException.java sync/CollectionKeys.java sync/CommandProcessor.java sync/CommandRunner.java sync/CredentialsSource.java sync/crypto/CryptoException.java sync/crypto/CryptoInfo.java sync/crypto/HKDF.java sync/crypto/HMACVerificationException.java sync/crypto/KeyBundle.java sync/crypto/MissingCryptoInputException.java sync/crypto/NoKeyBundleException.java sync/crypto/PersistedCrypto5Keys.java sync/CryptoRecord.java sync/DelayedWorkTracker.java sync/delegates/ClientsDataDelegate.java sync/delegates/FreshStartDelegate.java sync/delegates/GlobalSessionCallback.java sync/delegates/InfoCollectionsDelegate.java sync/delegates/KeyUploadDelegate.java sync/delegates/MetaGlobalDelegate.java sync/delegates/WipeServerDelegate.java sync/EngineSettings.java sync/ExtendedJSONObject.java sync/GlobalSession.java sync/HTTPFailureException.java sync/InfoCollections.java sync/jpake/BigIntegerHelper.java sync/jpake/Gx3OrGx4IsZeroOrOneException.java sync/jpake/IncorrectZkpException.java sync/jpake/JPakeClient.java sync/jpake/JPakeCrypto.java sync/jpake/JPakeJson.java sync/jpake/JPakeNoActivePairingException.java sync/jpake/JPakeNumGenerator.java sync/jpake/JPakeNumGeneratorRandom.java sync/jpake/JPakeParty.java sync/jpake/JPakeRequest.java sync/jpake/JPakeRequestDelegate.java sync/jpake/JPakeResponse.java sync/jpake/stage/CompleteStage.java sync/jpake/stage/ComputeFinalStage.java sync/jpake/stage/ComputeKeyVerificationStage.java sync/jpake/stage/ComputeStepOneStage.java sync/jpake/stage/ComputeStepTwoStage.java sync/jpake/stage/DecryptDataStage.java sync/jpake/stage/DeleteChannel.java sync/jpake/stage/GetChannelStage.java sync/jpake/stage/GetRequestStage.java sync/jpake/stage/JPakeStage.java sync/jpake/stage/PutRequestStage.java sync/jpake/stage/VerifyPairingStage.java sync/jpake/Zkp.java sync/KeyBundleProvider.java sync/Logger.java sync/MetaGlobal.java sync/MetaGlobalException.java sync/MetaGlobalMissingEnginesException.java sync/MetaGlobalNotSetException.java sync/middleware/Crypto5MiddlewareRepository.java sync/middleware/Crypto5MiddlewareRepositorySession.java sync/middleware/MiddlewareRepository.java sync/middleware/MiddlewareRepositorySession.java sync/net/BaseResource.java sync/net/CompletedEntity.java sync/net/ConnectionMonitorThread.java sync/net/HandleProgressException.java sync/net/HttpResponseObserver.java sync/net/Resource.java sync/net/ResourceDelegate.java sync/net/SyncResourceDelegate.java sync/net/SyncResponse.java sync/net/SyncStorageCollectionRequest.java sync/net/SyncStorageCollectionRequestDelegate.java sync/net/SyncStorageRecordRequest.java sync/net/SyncStorageRequest.java sync/net/SyncStorageRequestDelegate.java sync/net/SyncStorageRequestIncrementalDelegate.java sync/net/SyncStorageResponse.java sync/net/TLSSocketFactory.java sync/net/WBOCollectionRequestDelegate.java sync/net/WBORequestDelegate.java sync/NoCollectionKeysSetException.java sync/NodeAuthenticationException.java sync/NonArrayJSONException.java sync/NonObjectJSONException.java sync/NullClusterURLException.java sync/PersistedMetaGlobal.java sync/PrefsSource.java sync/repositories/android/AndroidBrowserBookmarksDataAccessor.java sync/repositories/android/AndroidBrowserBookmarksRepository.java sync/repositories/android/AndroidBrowserBookmarksRepositorySession.java sync/repositories/android/AndroidBrowserHistoryDataAccessor.java sync/repositories/android/AndroidBrowserHistoryDataExtender.java sync/repositories/android/AndroidBrowserHistoryRepository.java sync/repositories/android/AndroidBrowserHistoryRepositorySession.java sync/repositories/android/AndroidBrowserRepository.java sync/repositories/android/AndroidBrowserRepositoryDataAccessor.java sync/repositories/android/AndroidBrowserRepositorySession.java sync/repositories/android/BookmarksDeletionManager.java sync/repositories/android/BookmarksInsertionManager.java sync/repositories/android/BrowserContractHelpers.java sync/repositories/android/CachedSQLiteOpenHelper.java sync/repositories/android/ClientsDatabase.java sync/repositories/android/ClientsDatabaseAccessor.java sync/repositories/android/FennecControlHelper.java sync/repositories/android/FennecTabsRepository.java sync/repositories/android/FormHistoryRepositorySession.java sync/repositories/android/PasswordsRepositorySession.java sync/repositories/android/RepoUtils.java sync/repositories/BookmarkNeedsReparentingException.java sync/repositories/BookmarksRepository.java sync/repositories/ConstrainedServer11Repository.java sync/repositories/delegates/DeferrableRepositorySessionCreationDelegate.java sync/repositories/delegates/DeferredRepositorySessionBeginDelegate.java sync/repositories/delegates/DeferredRepositorySessionFetchRecordsDelegate.java sync/repositories/delegates/DeferredRepositorySessionFinishDelegate.java sync/repositories/delegates/DeferredRepositorySessionStoreDelegate.java sync/repositories/delegates/RepositorySessionBeginDelegate.java sync/repositories/delegates/RepositorySessionCleanDelegate.java sync/repositories/delegates/RepositorySessionCreationDelegate.java sync/repositories/delegates/RepositorySessionFetchRecordsDelegate.java sync/repositories/delegates/RepositorySessionFinishDelegate.java sync/repositories/delegates/RepositorySessionGuidsSinceDelegate.java sync/repositories/delegates/RepositorySessionStoreDelegate.java sync/repositories/delegates/RepositorySessionWipeDelegate.java sync/repositories/domain/BookmarkRecord.java sync/repositories/domain/BookmarkRecordFactory.java sync/repositories/domain/ClientRecord.java sync/repositories/domain/ClientRecordFactory.java sync/repositories/domain/FormHistoryRecord.java sync/repositories/domain/HistoryRecord.java sync/repositories/domain/HistoryRecordFactory.java sync/repositories/domain/PasswordRecord.java sync/repositories/domain/Record.java sync/repositories/domain/TabsRecord.java sync/repositories/HashSetStoreTracker.java sync/repositories/HistoryRepository.java sync/repositories/IdentityRecordFactory.java sync/repositories/InactiveSessionException.java sync/repositories/InvalidBookmarkTypeException.java sync/repositories/InvalidRequestException.java sync/repositories/InvalidSessionTransitionException.java sync/repositories/MultipleRecordsForGuidException.java sync/repositories/NoContentProviderException.java sync/repositories/NoGuidForIdException.java sync/repositories/NoStoreDelegateException.java sync/repositories/NullCursorException.java sync/repositories/ParentNotFoundException.java sync/repositories/ProfileDatabaseException.java sync/repositories/RecordFactory.java sync/repositories/RecordFilter.java sync/repositories/Repository.java sync/repositories/RepositorySession.java sync/repositories/RepositorySessionBundle.java sync/repositories/Server11Repository.java sync/repositories/Server11RepositorySession.java sync/repositories/StoreTracker.java sync/repositories/StoreTrackingRepositorySession.java sync/setup/activities/AccountActivity.java sync/setup/activities/ActivityUtils.java sync/setup/activities/SetupFailureActivity.java sync/setup/activities/SetupSuccessActivity.java sync/setup/activities/SetupSyncActivity.java sync/setup/Constants.java sync/setup/InvalidSyncKeyException.java sync/setup/SyncAccounts.java sync/setup/SyncAuthenticatorService.java sync/stage/AbstractNonRepositorySyncStage.java sync/stage/AndroidBrowserBookmarksServerSyncStage.java sync/stage/AndroidBrowserHistoryServerSyncStage.java sync/stage/CheckPreconditionsStage.java sync/stage/CompletedStage.java sync/stage/EnsureClusterURLStage.java sync/stage/EnsureCrypto5KeysStage.java sync/stage/FennecTabsServerSyncStage.java sync/stage/FetchInfoCollectionsStage.java sync/stage/FetchMetaGlobalStage.java sync/stage/FormHistoryServerSyncStage.java sync/stage/GlobalSyncStage.java sync/stage/NoSuchStageException.java sync/stage/NoSyncIDException.java sync/stage/PasswordsServerSyncStage.java sync/stage/ServerSyncStage.java sync/stage/SyncClientsEngineStage.java sync/StubActivity.java sync/syncadapter/SyncAdapter.java sync/syncadapter/SyncService.java sync/SyncConfiguration.java sync/SyncConfigurationException.java sync/SyncException.java sync/synchronizer/ConcurrentRecordConsumer.java sync/synchronizer/RecordConsumer.java sync/synchronizer/RecordsChannel.java sync/synchronizer/RecordsChannelDelegate.java sync/synchronizer/RecordsConsumerDelegate.java sync/synchronizer/SerialRecordConsumer.java sync/synchronizer/SessionNotBegunException.java sync/synchronizer/Synchronizer.java sync/synchronizer/SynchronizerDelegate.java sync/synchronizer/SynchronizerSession.java sync/synchronizer/SynchronizerSessionDelegate.java sync/synchronizer/UnbundleError.java sync/synchronizer/UnexpectedSessionException.java sync/SynchronizerConfiguration.java sync/SynchronizerConfigurations.java sync/ThreadPool.java sync/UnexpectedJSONException.java sync/UnknownSynchronizerConfigurationVersionException.java sync/Utils.java