Bug 617173 - Merge fx-sync to mozilla-central. a=blocking
☠☠ backed out by 84fe21efcb57 ☠ ☠
authorPhilipp von Weitershausen <philipp@weitershausen.de>
Mon, 06 Dec 2010 23:04:51 -0800
changeset 58766 4d16d58becaf3ae909de7ab2bd1b67d58e49806d
parent 58754 885c41905de1115800518fd5fae1bad374fd8aeb (current diff)
parent 58765 680d3557cafee52e1db57829238e61c8ee3ee42f (diff)
child 58767 84fe21efcb57b212f07d8a14d801712dd773b7f0
push id17416
push userpweitershausen@mozilla.com
push dateTue, 07 Dec 2010 07:05:47 +0000
treeherdermozilla-central@4d16d58becaf [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersblocking
bugs617173
milestone2.0b8pre
first release with
nightly linux32
4d16d58becaf / 4.0b8pre / 20101207030325 / files
nightly linux64
4d16d58becaf / 4.0b8pre / 20101207030325 / files
nightly mac
4d16d58becaf / 4.0b8pre / 20101207030325 / files
nightly win32
4d16d58becaf / 4.0b8pre / 20101207030325 / files
nightly win64
4d16d58becaf / 4.0b8pre / 20101207044840 / files
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
releases
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 617173 - Merge fx-sync to mozilla-central. a=blocking
services/crypto/modules/WeaveCrypto.js
services/sync/modules/engines/bookmarks.js
services/sync/modules/engines/history.js
services/sync/modules/engines/prefs.js
services/sync/modules/service.js
services/sync/tests/unit/head_helpers.js
services/sync/tests/unit/test_bookmark_predecessor.js
services/sync/tests/unit/test_bookmark_tracker.js
services/sync/tests/unit/test_history_tracker.js
services/sync/tests/unit/test_syncengine_sync.js
--- a/services/crypto/modules/WeaveCrypto.js
+++ b/services/crypto/modules/WeaveCrypto.js
@@ -494,21 +494,32 @@ WeaveCrypto.prototype = {
         outputBuffer = this._commonCrypt(input, outputBuffer, symmetricKey, iv, this.nss.CKA_DECRYPT);
 
         // outputBuffer contains UTF-8 data, let js-ctypes autoconvert that to a JS string.
         // XXX Bug 573842: wrap the string from ctypes to get a new string, so
         // we don't hit bug 573841.
         return "" + outputBuffer.readString() + "";
     },
 
+    _importSymKey: function _importSymKey(slot, mechanism, origin, op, keyItem) {
+        let symKey = this.nss.PK11_ImportSymKey(slot, mechanism, origin, op, keyItem.address(), null);
+        if (symKey.isNull())
+            throw Components.Exception("symkey import failed", Cr.NS_ERROR_FAILURE);
+        return symKey;
+    },
+    
+    _freeSymKey: function _freeSymKey(symKey) {
+        if (symKey && !symKey.isNull())
+            this.nss.PK11_FreeSymKey(symKey);
+    },
 
     _commonCrypt : function (input, output, symmetricKey, iv, operation) {
         this.log("_commonCrypt() called");
         // Get rid of the base64 encoding and convert to SECItems.
-        let keyItem = this.makeSECItem(symmetricKey, true);
+        let keyItem = this.makeSECItem(symmetricKey, true, true);
         let ivItem  = this.makeSECItem(iv, true);
 
         // Determine which (padded) PKCS#11 mechanism to use.
         // EG: AES_128_CBC --> CKM_AES_CBC --> CKM_AES_CBC_PAD
         let mechanism = this.nss.PK11_AlgtagToMechanism(this.algorithm);
         mechanism = this.nss.PK11_GetPadMechanism(mechanism);
         if (mechanism == this.nss.CKM_INVALID_MECHANISM)
             throw Components.Exception("invalid algorithm (can't pad)", Cr.NS_ERROR_FAILURE);
@@ -518,20 +529,17 @@ WeaveCrypto.prototype = {
             ivParam = this.nss.PK11_ParamFromIV(mechanism, ivItem.address());
             if (ivParam.isNull())
                 throw Components.Exception("can't convert IV to param", Cr.NS_ERROR_FAILURE);
 
             slot = this.nss.PK11_GetInternalKeySlot();
             if (slot.isNull())
                 throw Components.Exception("can't get internal key slot", Cr.NS_ERROR_FAILURE);
 
-            symKey = this.nss.PK11_ImportSymKey(slot, mechanism, this.nss.PK11_OriginUnwrap, operation, keyItem.address(), null);
-            if (symKey.isNull())
-                throw Components.Exception("symkey import failed", Cr.NS_ERROR_FAILURE);
-
+            symKey = this._importSymKey(slot, mechanism, this.nss.PK11_OriginUnwrap, operation, keyItem);
             ctx = this.nss.PK11_CreateContextBySymKey(mechanism, operation, symKey, ivParam);
             if (ctx.isNull())
                 throw Components.Exception("couldn't create context for symkey", Cr.NS_ERROR_FAILURE);
 
             let maxOutputSize = output.length;
             let tmpOutputSize = new ctypes.int(); // Note 1: NSS uses a signed int here...
 
             if (this.nss.PK11_CipherOp(ctx, output, tmpOutputSize.address(), maxOutputSize, input, input.length))
@@ -552,18 +560,17 @@ WeaveCrypto.prototype = {
             let newOutput = ctypes.cast(output, ctypes.unsigned_char.array(actualOutputSize));
             return newOutput;
         } catch (e) {
             this.log("_commonCrypt: failed: " + e);
             throw e;
         } finally {
             if (ctx && !ctx.isNull())
                 this.nss.PK11_DestroyContext(ctx, true);
-            if (symKey && !symKey.isNull())
-                this.nss.PK11_FreeSymKey(symKey);
+            this._freeSymKey(symKey);
             if (slot && !slot.isNull())
                 this.nss.PK11_FreeSlot(slot);
             if (ivParam && !ivParam.isNull())
                 this.nss.SECITEM_FreeItem(ivParam, true);
         }
     },
 
 
@@ -688,17 +695,16 @@ WeaveCrypto.prototype = {
         if (isEncoded)
             input = atob(input);
         let outputData = new ctypes.ArrayType(ctypes.unsigned_char, input.length)();
         this.byteCompress(input, outputData);
 
         return new this.nss_t.SECItem(this.nss.SIBUFFER, outputData, outputData.length);
     },
 
-
     /**
      * Returns the expanded data string for the derived key.
      */
     deriveKeyFromPassphrase : function deriveKeyFromPassphrase(passphrase, salt, keyLength) {
         this.log("deriveKeyFromPassphrase() called.");
         let passItem = this.makeSECItem(passphrase, false);
         let saltItem = this.makeSECItem(salt, true);
 
@@ -746,8 +752,50 @@ WeaveCrypto.prototype = {
                 this.nss.SECOID_DestroyAlgorithmID(algid, true);
             if (slot && !slot.isNull())
                 this.nss.PK11_FreeSlot(slot);
             if (symKey && !symKey.isNull())
                 this.nss.PK11_FreeSymKey(symKey);
     }
     },
 };
+
+// Memoize makeSECItem for symmetric keys.
+WeaveCrypto.prototype.makeSECItem =
+(function (orig) {
+  let memo = {};
+
+  return function(input, isEncoded, memoize) {
+    if (memoize) {
+      let memoKey = "" + input + !!isEncoded;
+      let val = memo[memoKey];
+      if (!val) {
+        val = orig.apply(this, arguments);
+        memo[memoKey] = val;
+      }
+      return val;
+    }
+    return orig.apply(this, arguments);
+  };
+}(WeaveCrypto.prototype.makeSECItem));
+
+WeaveCrypto.prototype._importSymKey =
+(function (orig) {
+  let memo = {}
+  
+  return function(slot, mechanism, origin, op, keyItem) {
+    // keyItem lookup is already memoized, so we can directly use the address.
+    // Slot changes each time. Don't use it as memo key input.
+    let memoKey = "" + "-" + mechanism +
+                  origin + op + "-" + keyItem.address();
+    let val = memo[memoKey];
+    if (!val) {
+      val = orig.apply(this, arguments);
+      memo[memoKey] = val;
+    }
+    return val;
+  };
+}(WeaveCrypto.prototype._importSymKey));
+
+// Yes, this leaks. However, _importSymKey is now memoized, so the average user
+// will have only a single key, which we persist for the lifetime of the
+// session...
+WeaveCrypto.prototype._freeSymKey = function(symKey) {};
--- a/services/crypto/tests/unit/test_crypto_crypt.js
+++ b/services/crypto/tests/unit/test_crypto_crypt.js
@@ -3,17 +3,79 @@ try {
   Components.utils.import("resource://services-crypto/WeaveCrypto.js");
   cryptoSvc = new WeaveCrypto();
 } catch (ex) {
   // Fallback to binary WeaveCrypto
   cryptoSvc = Cc["@labs.mozilla.com/Weave/Crypto;1"]
                 .getService(Ci.IWeaveCrypto);
 }
 
-function run_test() {
+function weavecrypto_memo() {
+  if (!cryptoSvc._importSymKey)
+    return
+      
+  let w = new WeaveCrypto();
+  let key = w.generateRandomKey();
+  let keyItem1 = w.makeSECItem(key, true, true);
+  let keyItem2 = w.makeSECItem(key, true, true);
+  do_check_eq(keyItem1, keyItem2);
+  
+  do_check_eq("" + w.nss.PK11_AlgtagToMechanism(w.algorithm),
+              "" + w.nss.PK11_AlgtagToMechanism(w.algorithm));
+  
+  let symKey1 =
+    w._importSymKey(w.nss.PK11_GetInternalKeySlot(),
+                    w.nss.PK11_AlgtagToMechanism(w.algorithm),
+                    w.nss.PK11_OriginUnwrap,
+                    w.nss.CKA_DECRYPT, 
+                    keyItem1);
+  let symKey2 =
+    w._importSymKey(w.nss.PK11_GetInternalKeySlot(),
+                    w.nss.PK11_AlgtagToMechanism(w.algorithm),
+                    w.nss.PK11_OriginUnwrap,
+                    w.nss.CKA_DECRYPT, 
+                    keyItem1);
+  do_check_eq(symKey1, symKey2);
+}
+
+/*
+With memoization:
+make check-one  10.39s user 0.75s system 100% cpu 11.041 total
+nsStringStats
+ => mAllocCount:           1923
+ => mReallocCount:          306
+ => mFreeCount:            1923
+ => mShareCount:           6764
+ => mAdoptCount:            101
+ => mAdoptFreeCount:        101
+<<<<<<<
+
+Without memoization, it crashes after a few thousand iterations... and 5610 take
+make check-one  7.57s user 0.67s system 101% cpu 8.105 total
+nsStringStats
+ => mAllocCount:           1923
+ => mReallocCount:          306
+ => mFreeCount:            1923
+ => mShareCount:           6764
+ => mAdoptCount:            101
+ => mAdoptFreeCount:        101
+<<<<<<<
+*/ 
+function multiple_decrypts(iterations) {
+  let iv = cryptoSvc.generateRandomIV();
+  let key = cryptoSvc.generateRandomKey();
+  let cipherText = cryptoSvc.encrypt("Hello, world.", key, iv);
+  
+  for (let i = 0; i < iterations; ++i) {
+    let clearText = cryptoSvc.decrypt(cipherText, key, iv);
+    do_check_eq(clearText + " " + i, "Hello, world. " + i);
+  }
+}
+  
+function test_encryption() {
   // First, do a normal run with expected usage... Generate a random key and
   // iv, encrypt and decrypt a string.
   var iv = cryptoSvc.generateRandomIV();
   do_check_eq(iv.length, 24);
 
   var key = cryptoSvc.generateRandomKey();
   do_check_eq(key.length, 44);
 
@@ -157,8 +219,14 @@ function run_test() {
     failure = false;
     clearText = cryptoSvc.decrypt(badcipher, key, iv);
   } catch (e) {
     failure = true;
   }
   do_check_true(failure);
 
 }
+
+function run_test() {
+  weavecrypto_memo();
+  multiple_decrypts(6000);
+  test_encryption();
+}
--- a/services/sync/modules/base_records/crypto.js
+++ b/services/sync/modules/base_records/crypto.js
@@ -318,16 +318,19 @@ function KeyBundle(realm, collectionName
   
   if (keyStr && !keyStr.charAt)
     // Ensure it's valid.
     throw "KeyBundle given non-string key.";
   
   Identity.call(this, realm, collectionName, keyStr);
   this._hmac    = null;
   this._encrypt = null;
+  
+  // Cache the key object.
+  this._hmacObj = null;
 }
 
 KeyBundle.prototype = {
   __proto__: Identity.prototype,
   
   /*
    * Accessors for the two keys.
    */
@@ -340,21 +343,21 @@ KeyBundle.prototype = {
   },
 
   get hmacKey() {
     return this._hmac;
   },
   
   set hmacKey(value) {
     this._hmac = value;
+    this._hmacObj = value ? Utils.makeHMACKey(value) : null;
   },
   
   get hmacKeyObject() {
-    if (this.hmacKey)
-      return Utils.makeHMACKey(this.hmacKey);
+    return this._hmacObj;
   },
 }
 
 function BulkKeyBundle(realm, collectionName) {
   let log = Log4Moz.repository.getLogger("BulkKeyBundle");
   log.info("BulkKeyBundle being created for " + collectionName);
   KeyBundle.call(this, realm, collectionName);
 }
@@ -378,17 +381,17 @@ BulkKeyBundle.prototype = {
    */
   set keyPair(value) {
     if (value.length && (value.length == 2)) {
       let json = JSON.stringify(value);
       let en = value[0];
       let hm = value[1];
       
       this.password = json;
-      this._hmac    = Utils.safeAtoB(hm);
+      this.hmacKey  = Utils.safeAtoB(hm);
       this._encrypt = en;          // Store in base64.
     }
     else {
       throw "Invalid keypair";
   }
   },
 };
 
@@ -408,17 +411,18 @@ SyncKeyBundle.prototype = {
    * hashed into individual keys.
    */
   get keyStr() {
     return this.password;
   },
 
   set keyStr(value) {
     this.password = value;
-    this._hmac = null;
+    this._hmac    = null;
+    this._hmacObj = null;
     this._encrypt = null;
     this.generateEntry();
   },
   
   /*
    * Can't rely on password being set through any of our setters:
    * Identity does work under the hood.
    * 
@@ -432,16 +436,22 @@ SyncKeyBundle.prototype = {
   },
   
   get hmacKey() {
     if (!this._hmac)
       this.generateEntry();
     return this._hmac;
   },
   
+  get hmacKeyObject() {
+    if (!this._hmacObj)
+      this.generateEntry();
+    return this._hmacObj;
+  },
+  
   /*
    * If we've got a string, hash it into keys and store them.
    */
   generateEntry: function generateEntry() {
     let m = this.keyStr;
     if (m) {
       // Decode into a 16-byte string before we go any further.
       m = Utils.decodeKeyBase32(m);
@@ -455,12 +465,15 @@ SyncKeyBundle.prototype = {
       let enc = Utils.sha256HMACBytes(m, k1, h);
       
       // Second key: depends on the output of the first run.
       let k2 = Utils.makeHMACKey(enc + HMAC_INPUT + u + "\x02");
       let hmac = Utils.sha256HMACBytes(m, k2, h);
       
       // Save them.
       this._encrypt = btoa(enc);
-      this._hmac    = hmac;
+      
+      // Individual sets: cheaper than calling parent setter.
+      this._hmac = hmac;
+      this._hmacObj = Utils.makeHMACKey(hmac);
     }
   }
 };
--- a/services/sync/modules/constants.js
+++ b/services/sync/modules/constants.js
@@ -96,16 +96,18 @@ MODE_TRUNCATE:                         0
 PERMS_FILE:                            0644,
 PERMS_PASSFILE:                        0600,
 PERMS_DIRECTORY:                       0755,
 
 // Number of records to upload in a single POST (multiple POSTS if exceeded)
 // FIXME: Record size limit is 256k (new cluster), so this can be quite large!
 // (Bug 569295)
 MAX_UPLOAD_RECORDS:                    100,
+MAX_HISTORY_UPLOAD:                    5000,
+MAX_HISTORY_DOWNLOAD:                  5000,
 
 // Top-level statuses:
 STATUS_OK:                             "success.status_ok",
 SYNC_FAILED:                           "error.sync.failed",
 LOGIN_FAILED:                          "error.login.failed",
 SYNC_FAILED_PARTIAL:                   "error.sync.failed_partial",
 CLIENT_NOT_CONFIGURED:                 "service.client_not_configured",
 STATUS_DISABLED:                       "service.disabled",
--- a/services/sync/modules/engines.js
+++ b/services/sync/modules/engines.js
@@ -134,16 +134,17 @@ EngineManagerSvc.prototype = {
       name = val.name;
     delete this._engines[name];
   }
 };
 
 function Engine(name) {
   this.Name = name || "Unnamed";
   this.name = name.toLowerCase();
+  this.downloadLimit = null;
 
   this._notify = Utils.notify("weave:engine:");
   this._log = Log4Moz.repository.getLogger("Engine." + this.Name);
   let level = Svc.Prefs.get("log.logger.engine." + this.name, "Debug");
   this._log.level = Log4Moz.Level[level];
 
   this._tracker; // initialize tracker to load previously changed IDs
   this._log.debug("Engine initialized");
@@ -490,17 +491,23 @@ SyncEngine.prototype = {
         throw resp;
       }
     }
 
     // Mobile: check if we got the maximum that we requested; get the rest if so.
     let toFetch = [];
     if (handled.length == newitems.limit) {
       let guidColl = new Collection(this.engineURL);
+      
+      // Sort and limit so that on mobile we only get the last X records.
+      guidColl.limit = this.downloadLimit;
       guidColl.newer = this.lastSync;
+      
+      // index: Orders by the sortindex descending (highest weight first).
+      guidColl.sort  = "index";
 
       let guids = guidColl.get();
       if (!guids.success)
         throw guids;
 
       // Figure out which guids weren't just fetched then remove any guids that
       // were already waiting and prepend the new ones
       let extra = Utils.arraySub(guids.obj, handled);
--- a/services/sync/modules/engines/bookmarks.js
+++ b/services/sync/modules/engines/bookmarks.js
@@ -16,16 +16,17 @@
  * The Initial Developer of the Original Code is Mozilla.
  * Portions created by the Initial Developer are Copyright (C) 2007
  * the Initial Developer. All Rights Reserved.
  *
  * Contributor(s):
  *  Dan Mills <thunder@mozilla.com>
  *  Jono DiCarlo <jdicarlo@mozilla.org>
  *  Anant Narayanan <anant@kix.in>
+ *  Philipp von Weitershausen <philipp@weitershausen.de>
  *
  * 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
@@ -37,18 +38,19 @@
  * ***** END LICENSE BLOCK ***** */
 
 const EXPORTED_SYMBOLS = ['BookmarksEngine', 'BookmarksSharingManager'];
 
 const Cc = Components.classes;
 const Ci = Components.interfaces;
 const Cu = Components.utils;
 
-const PARENT_ANNO = "weave/parent";
-const PREDECESSOR_ANNO = "weave/predecessor";
+const GUID_ANNO = "sync/guid";
+const PARENT_ANNO = "sync/parent";
+const CHILDREN_ANNO = "sync/children";
 const SERVICE_NOT_SUPPORTED = "Service not supported on this platform";
 const FOLDER_SORTINDEX = 1000000;
 
 try {
   Cu.import("resource://gre/modules/PlacesUtils.jsm");
 }
 catch(ex) {
   Cu.import("resource://gre/modules/utils.js");
@@ -86,38 +88,26 @@ Utils.lazy2(kSpecialIds, "mobile", funct
     return root[0];
 
   // Create the special mobile folder to store mobile bookmarks
   let mobile = Svc.Bookmark.createFolder(Svc.Bookmark.placesRoot, "mobile", -1);
   Utils.anno(mobile, anno, 1);
   return mobile;
 });
 
-// Create some helper functions to convert GUID/ids
-function idForGUID(guid) {
-  if (guid in kSpecialIds)
-    return kSpecialIds[guid];
-  return Svc.Bookmark.getItemIdForGUID(guid);
-}
-function GUIDForId(placeId) {
-  for (let [guid, id] in Iterator(kSpecialIds))
-    if (placeId == id)
-      return guid;
-  return Svc.Bookmark.getItemGUID(placeId);
-}
-
 function BookmarksEngine() {
   SyncEngine.call(this, "Bookmarks");
   this._handleImport();
 }
 BookmarksEngine.prototype = {
   __proto__: SyncEngine.prototype,
   _recordObj: PlacesItem,
   _storeObj: BookmarksStore,
   _trackerObj: BookmarksTracker,
+  version: 2,
 
   _handleImport: function _handleImport() {
     Svc.Obs.add("bookmarks-restore-begin", function() {
       this._log.debug("Ignoring changes from importing bookmarks");
       this._tracker.ignoreAll = true;
     }, this);
 
     Svc.Obs.add("bookmarks-restore-success", function() {
@@ -146,17 +136,17 @@ BookmarksEngine.prototype = {
     // Lazily create a mapping of folder titles and separator positions to GUID
     this.__defineGetter__("_lazyMap", function() {
       delete this._lazyMap;
 
       let lazyMap = {};
       for (let guid in this._store.getAllIDs()) {
         // Figure out what key to store the mapping
         let key;
-        let id = idForGUID(guid);
+        let id = this._store.idForGUID(guid);
         switch (Svc.Bookmark.getItemType(id)) {
           case Svc.Bookmark.TYPE_BOOKMARK:
             key = "b" + Svc.Bookmark.getBookmarkURI(id).spec + ":" +
               Svc.Bookmark.getItemTitle(id);
             break;
           case Svc.Bookmark.TYPE_FOLDER:
             key = "f" + Svc.Bookmark.getItemTitle(id);
             break;
@@ -164,16 +154,19 @@ BookmarksEngine.prototype = {
             key = "s" + Svc.Bookmark.getItemIndex(id);
             break;
           default:
             continue;
         }
 
         // The mapping is on a per parent-folder-name basis
         let parent = Svc.Bookmark.getFolderIdForItem(id);
+        if (parent <= 0)
+          continue;
+
         let parentName = Svc.Bookmark.getItemTitle(parent);
         if (lazyMap[parentName] == null)
           lazyMap[parentName] = {};
 
         // If the entry already exists, remember that there are explicit dupes
         let entry = new String(guid);
         entry.hasDupe = lazyMap[parentName][key] != null;
 
@@ -206,16 +199,27 @@ BookmarksEngine.prototype = {
         // Give the guid if we have the matching pair
         this._log.trace("Finding mapping: " + item.parentName + ", " + key);
         let parent = lazyMap[item.parentName];
         let dupe = parent && parent[key];
         this._log.trace("Mapped dupe: " + dupe);
         return dupe;
       };
     });
+
+    this._store._childrenToOrder = {};
+  },
+
+  _processIncoming: function _processIncoming() {
+    SyncEngine.prototype._processIncoming.call(this);
+    // Reorder children.
+    this._tracker.ignoreAll = true;
+    this._store._orderChildren();
+    this._tracker.ignoreAll = false;
+    delete this._store._childrenToOrder;
   },
 
   _syncFinish: function _syncFinish() {
     SyncEngine.prototype._syncFinish.call(this);
     delete this._lazyMap;
     this._tracker._ensureMobileQuery();
   },
 
@@ -252,18 +256,18 @@ function BookmarksStore(name) {
 
   // Explicitly nullify our references to our cached services so we don't leak
   Svc.Obs.add("places-shutdown", function() {
     this.__bms = null;
     this.__hsvc = null;
     this.__ls = null;
     this.__ms = null;
     this.__ts = null;
-    if (this.__frecencyStm)
-      this.__frecencyStm.finalize();
+    for each ([query, stmt] in Iterator(this._stmts))
+      stmt.finalize();
   }, this);
 }
 BookmarksStore.prototype = {
   __proto__: Store.prototype,
 
   __bms: null,
   get _bms() {
     if (!this.__bms)
@@ -271,17 +275,18 @@ BookmarksStore.prototype = {
                    getService(Ci.nsINavBookmarksService);
     return this.__bms;
   },
 
   __hsvc: null,
   get _hsvc() {
     if (!this.__hsvc)
       this.__hsvc = Cc["@mozilla.org/browser/nav-history-service;1"].
-                    getService(Ci.nsINavHistoryService);
+                    getService(Ci.nsINavHistoryService).
+                    QueryInterface(Ci.nsPIPlacesDatabase);
     return this.__hsvc;
   },
 
   __ls: null,
   get _ls() {
     if (!this.__ls)
       this.__ls = Cc["@mozilla.org/browser/livemark-service;2"].
                   getService(Ci.nsILivemarkService);
@@ -309,31 +314,33 @@ BookmarksStore.prototype = {
     if (!this.__ts)
       this.__ts = Cc["@mozilla.org/browser/tagging-service;1"].
                   getService(Ci.nsITaggingService);
     return this.__ts;
   },
 
 
   itemExists: function BStore_itemExists(id) {
-    return idForGUID(id) > 0;
+    return this.idForGUID(id) > 0;
   },
 
   // Hash of old GUIDs to the new renamed GUIDs
   aliases: {},
 
   applyIncoming: function BStore_applyIncoming(record) {
-    // Ignore (accidental?) root changes
-    if (record.id in kSpecialIds) {
-      this._log.debug("Skipping change to root node: " + record.id);
+    // For special folders we're only interested in child ordering.
+    if ((record.id in kSpecialIds) && record.children) {
+      this._log.debug("Processing special node: " + record.id);
+      // Reorder children later
+      this._childrenToOrder[record.id] = record.children;
       return;
     }
 
     // Convert GUID fields to the aliased GUID if necessary
-    ["id", "parentid", "predecessorid"].forEach(function(field) {
+    ["id", "parentid"].forEach(function(field) {
       let alias = this.aliases[record[field]];
       if (alias != null)
         record[field] = alias;
     }, this);
 
     // Preprocess the record before doing the normal apply
     switch (record.type) {
       case "query": {
@@ -365,176 +372,84 @@ BookmarksStore.prototype = {
         break;
       }
     }
 
     // Figure out the local id of the parent GUID if available
     let parentGUID = record.parentid;
     record._orphan = false;
     if (parentGUID != null) {
-      let parentId = idForGUID(parentGUID);
+      let parentId = this.idForGUID(parentGUID);
 
       // Default to unfiled if we don't have the parent yet
       if (parentId <= 0) {
         this._log.trace("Reparenting to unfiled until parent is synced");
         record._orphan = true;
         parentId = kSpecialIds.unfiled;
       }
 
       // Save the parent id for modifying the bookmark later
       record._parent = parentId;
     }
 
-    // Default to append unless we're not an orphan with the predecessor
-    let predGUID = record.predecessorid;
-    record._insertPos = Svc.Bookmark.DEFAULT_INDEX;
-    if (!record._orphan) {
-      // No predecessor means it's the first item
-      if (predGUID == null)
-        record._insertPos = 0;
-      else {
-        // The insert position is one after the predecessor of the same parent
-        let predId = idForGUID(predGUID);
-        if (predId != -1 && this._getParentGUIDForId(predId) == parentGUID) {
-          record._insertPos = Svc.Bookmark.getItemIndex(predId) + 1;
-          record._predId = predId;
-        }
-        else
-          this._log.trace("Appending to end until predecessor is synced");
-      }
-    }
-
     // Do the normal processing of incoming records
     Store.prototype.applyIncoming.apply(this, arguments);
 
     // Do some post-processing if we have an item
-    let itemId = idForGUID(record.id);
+    let itemId = this.idForGUID(record.id);
     if (itemId > 0) {
       // Move any children that are looking for this folder as a parent
-      if (record.type == "folder")
+      if (record.type == "folder") {
         this._reparentOrphans(itemId);
+        // Reorder children later
+        if (record.children)
+          this._childrenToOrder[record.id] = record.children;
+      }
 
       // Create an annotation to remember that it needs a parent
-      // XXX Work around Bug 510628 by prepending parenT
       if (record._orphan)
-        Utils.anno(itemId, PARENT_ANNO, "T" + parentGUID);
-      // It's now in the right folder, so move annotated items behind this
-      else
-        this._attachFollowers(itemId);
-
-      // Create an annotation if we have a predecessor but no position
-      // XXX Work around Bug 510628 by prepending predecessoR
-      if (predGUID != null && record._insertPos == Svc.Bookmark.DEFAULT_INDEX)
-        Utils.anno(itemId, PREDECESSOR_ANNO, "R" + predGUID);
+        Utils.anno(itemId, PARENT_ANNO, parentGUID);
     }
   },
 
   /**
    * Find all ids of items that have a given value for an annotation
    */
   _findAnnoItems: function BStore__findAnnoItems(anno, val) {
-    // XXX Work around Bug 510628 by prepending parenT
-    if (anno == PARENT_ANNO)
-      val = "T" + val;
-    // XXX Work around Bug 510628 by prepending predecessoR
-    else if (anno == PREDECESSOR_ANNO)
-      val = "R" + val;
-
     return Svc.Annos.getItemsWithAnnotation(anno, {}).filter(function(id)
       Utils.anno(id, anno) == val);
   },
 
   /**
    * For the provided parent item, attach its children to it
    */
   _reparentOrphans: function _reparentOrphans(parentId) {
     // Find orphans and reunite with this folder parent
-    let parentGUID = GUIDForId(parentId);
+    let parentGUID = this.GUIDForId(parentId);
     let orphans = this._findAnnoItems(PARENT_ANNO, parentGUID);
 
     this._log.debug("Reparenting orphans " + orphans + " to " + parentId);
     orphans.forEach(function(orphan) {
-      // Append the orphan under the parent unless it's supposed to be first
-      let insertPos = Svc.Bookmark.DEFAULT_INDEX;
-      if (!Svc.Annos.itemHasAnnotation(orphan, PREDECESSOR_ANNO))
-        insertPos = 0;
-
       // Move the orphan to the parent and drop the missing parent annotation
-      Svc.Bookmark.moveItem(orphan, parentId, insertPos);
+      Svc.Bookmark.moveItem(orphan, parentId, Svc.Bookmark.DEFAULT_INDEX);
       Svc.Annos.removeItemAnnotation(orphan, PARENT_ANNO);
-    });
-
-    // Fix up the ordering of the now-parented items
-    orphans.forEach(this._attachFollowers, this);
-  },
-
-  /**
-   * Move an item and all of its followers to a new position until reaching an
-   * item that shouldn't be moved
-   */
-  _moveItemChain: function BStore__moveItemChain(itemId, insertPos, stopId) {
-    let parentId = Svc.Bookmark.getFolderIdForItem(itemId);
-
-    // Keep processing the item chain until it loops to the stop item
-    do {
-      // Figure out what's next in the chain
-      let itemPos = Svc.Bookmark.getItemIndex(itemId);
-      let nextId = Svc.Bookmark.getIdForItemAt(parentId, itemPos + 1);
-
-      Svc.Bookmark.moveItem(itemId, parentId, insertPos);
-      this._log.trace("Moved " + itemId + " to " + insertPos);
-
-      // Prepare for the next item in the chain
-      insertPos = Svc.Bookmark.getItemIndex(itemId) + 1;
-      itemId = nextId;
-
-      // Stop if we ran off the end or the item is looking for its pred.
-      if (itemId == -1 || Svc.Annos.itemHasAnnotation(itemId, PREDECESSOR_ANNO))
-        break;
-    } while (itemId != stopId);
-  },
-
-  /**
-   * For the provided predecessor item, attach its followers to it
-   */
-  _attachFollowers: function BStore__attachFollowers(predId) {
-    let predGUID = GUIDForId(predId);
-    let followers = this._findAnnoItems(PREDECESSOR_ANNO, predGUID);
-    if (followers.length > 1)
-      this._log.warn(predId + " has more than one followers: " + followers);
-
-    // Start at the first follower and move the chain of followers
-    let parent = Svc.Bookmark.getFolderIdForItem(predId);
-    followers.forEach(function(follow) {
-      this._log.trace("Repositioning " + follow + " behind " + predId);
-      if (Svc.Bookmark.getFolderIdForItem(follow) != parent) {
-        this._log.warn("Follower doesn't have the same parent: " + parent);
-        return;
-      }
-
-      // Move the chain of followers to after the predecessor
-      let insertPos = Svc.Bookmark.getItemIndex(predId) + 1;
-      this._moveItemChain(follow, insertPos, predId);
-
-      // Remove the annotation now that we're putting it in the right spot
-      Svc.Annos.removeItemAnnotation(follow, PREDECESSOR_ANNO);
     }, this);
   },
 
   create: function BStore_create(record) {
     let newId;
     switch (record.type) {
     case "bookmark":
     case "query":
     case "microsummary": {
       let uri = Utils.makeURI(record.bmkUri);
-      newId = this._bms.insertBookmark(record._parent, uri, record._insertPos,
-        record.title);
-      this._log.debug(["created bookmark", newId, "under", record._parent, "at",
-        record._insertPos, "as", record.title, record.bmkUri].join(" "));
+      newId = this._bms.insertBookmark(record._parent, uri,
+                                       Svc.Bookmark.DEFAULT_INDEX, record.title);
+      this._log.debug(["created bookmark", newId, "under", record._parent,
+                       "as", record.title, record.bmkUri].join(" "));
 
       this._tagURI(uri, record.tags);
       this._bms.setKeywordForBookmark(newId, record.keyword);
       if (record.description)
         Utils.anno(newId, "bookmarkProperties/description", record.description);
 
       if (record.loadInSidebar)
         Utils.anno(newId, "bookmarkProperties/loadInSidebar", true);
@@ -551,53 +466,56 @@ BookmarksStore.prototype = {
           catch(ex) { /* ignore "missing local generator" exceptions */ }
         }
         else
           this._log.warn("Can't create microsummary -- not supported.");
       }
     } break;
     case "folder":
       newId = this._bms.createFolder(record._parent, record.title,
-        record._insertPos);
-      this._log.debug(["created folder", newId, "under", record._parent, "at",
-        record._insertPos, "as", record.title].join(" "));
+                                     Svc.Bookmark.DEFAULT_INDEX);
+      this._log.debug(["created folder", newId, "under", record._parent,
+                       "as", record.title].join(" "));
 
       if (record.description)
         Utils.anno(newId, "bookmarkProperties/description", record.description);
+
+      // record.children will be dealt with in _orderChildren.
       break;
     case "livemark":
       let siteURI = null;
       if (record.siteUri != null)
         siteURI = Utils.makeURI(record.siteUri);
 
       newId = this._ls.createLivemark(record._parent, record.title, siteURI,
-        Utils.makeURI(record.feedUri), record._insertPos);
-      this._log.debug(["created livemark", newId, "under", record._parent, "at",
-        record._insertPos, "as", record.title, record.siteUri, record.feedUri].
-        join(" "));
+                                      Utils.makeURI(record.feedUri),
+                                      Svc.Bookmark.DEFAULT_INDEX);
+      this._log.debug(["created livemark", newId, "under", record._parent, "as",
+                       record.title, record.siteUri, record.feedUri].join(" "));
       break;
     case "separator":
-      newId = this._bms.insertSeparator(record._parent, record._insertPos);
-      this._log.debug(["created separator", newId, "under", record._parent,
-        "at", record._insertPos].join(" "));
+      newId = this._bms.insertSeparator(record._parent,
+                                        Svc.Bookmark.DEFAULT_INDEX);
+      this._log.debug(["created separator", newId, "under", record._parent]
+                      .join(" "));
       break;
     case "item":
       this._log.debug(" -> got a generic places item.. do nothing?");
       return;
     default:
       this._log.error("_create: Unknown item type: " + record.type);
       return;
     }
 
     this._log.trace("Setting GUID of new item " + newId + " to " + record.id);
     this._setGUID(newId, record.id);
   },
 
   remove: function BStore_remove(record) {
-    let itemId = idForGUID(record.id);
+    let itemId = this.idForGUID(record.id);
     if (itemId <= 0) {
       this._log.debug("Item " + record.id + " already removed");
       return;
     }
     var type = this._bms.getItemType(itemId);
 
     switch (type) {
     case this._bms.TYPE_BOOKMARK:
@@ -615,37 +533,29 @@ BookmarksStore.prototype = {
       break;
     default:
       this._log.error("remove: Unknown item type: " + type);
       break;
     }
   },
 
   update: function BStore_update(record) {
-    let itemId = idForGUID(record.id);
+    let itemId = this.idForGUID(record.id);
 
     if (itemId <= 0) {
       this._log.debug("Skipping update for unknown item: " + record.id);
       return;
     }
 
     this._log.trace("Updating " + record.id + " (" + itemId + ")");
 
-    // Move the bookmark to a new parent if necessary
+    // Move the bookmark to a new parent or new position if necessary
     if (Svc.Bookmark.getFolderIdForItem(itemId) != record._parent) {
-      this._log.trace("Moving item to a new parent");
-      Svc.Bookmark.moveItem(itemId, record._parent, record._insertPos);
-    }
-    // Move the chain of bookmarks to a new position
-    else if (Svc.Bookmark.getItemIndex(itemId) != record._insertPos &&
-             !record._orphan) {
-      this._log.trace("Moving item and followers to a new position");
-
-      // Stop moving at the predecessor unless we don't have one
-      this._moveItemChain(itemId, record._insertPos, record._predId || itemId);
+      this._log.trace("Moving item to a new parent.");
+      Svc.Bookmark.moveItem(itemId, record._parent, Svc.Bookmark.DEFAULT_INDEX);
     }
 
     for (let [key, val] in Iterator(record.cleartext)) {
       switch (key) {
       case "title":
         this._bms.setItemTitle(itemId, val);
         break;
       case "bmkUri":
@@ -681,48 +591,108 @@ BookmarksStore.prototype = {
         }
       } break;
       case "siteUri":
         this._ls.setSiteURI(itemId, Utils.makeURI(val));
         break;
       case "feedUri":
         this._ls.setFeedURI(itemId, Utils.makeURI(val));
         break;
+      case "children":
+        Utils.anno(itemId, CHILDREN_ANNO, val.join(","));
+        break;
       }
     }
   },
 
+  _orderChildren: function _orderChildren() {
+    for (let [guid, children] in Iterator(this._childrenToOrder)) {
+      // Convert children GUIDs to aliases if they exist.
+      children = children.map(function(guid) {
+        return this.aliases[guid] || guid;
+      }, this);
+
+      // Reorder children according to the GUID list. Gracefully deal
+      // with missing items, e.g. locally deleted.
+      let delta = 0;
+      for (let idx = 0; idx < children.length; idx++) {
+        let itemid = this.idForGUID(children[idx]);
+        if (itemid == -1) {
+          delta += 1;
+          this._log.trace("Could not locate record " + children[idx]);
+          continue;
+        }
+        try {
+          Svc.Bookmark.setItemIndex(itemid, idx - delta);
+        } catch (ex) {
+          this._log.debug("Could not move item " + children[idx] + ": " + ex);
+        }
+      }
+
+      // Update the children annotation. If there were mismatches due to local
+      // changes, we'll have to regenerate it from scratch, otherwise we can
+      // just use the incoming value.
+      let folderid = this.idForGUID(guid);
+      if (delta) {
+        this._updateChildrenAnno(folderid);
+      } else {
+        Utils.anno(folderid, CHILDREN_ANNO, children.join(","));
+      }
+    }
+  },
+
+  _updateChildrenAnno: function _updateChildrenAnno(itemid) {
+    let node = node = this._getNode(itemid);
+    let childids = [];
+
+    if (node.type == node.RESULT_TYPE_FOLDER &&
+        !this._ls.isLivemark(node.itemId)) {
+      node.QueryInterface(Ci.nsINavHistoryQueryResultNode);
+      node.containerOpen = true;
+      for (var i = 0; i < node.childCount; i++)
+        childids.push(node.getChild(i).itemId);
+    }
+    let childGUIDs = childids.map(this.GUIDForId, this);
+    Utils.anno(itemid, CHILDREN_ANNO, childGUIDs.join(","));
+    return childGUIDs;
+  },
+
+  get _removeAllChildrenAnnosStm() {
+    let stmt = this._getStmt(
+      "DELETE FROM moz_items_annos " +
+      "WHERE anno_attribute_id = " +
+        "(SELECT id FROM moz_anno_attributes WHERE name = :anno_name)");
+    stmt.params.anno_name = CHILDREN_ANNO;
+    return stmt;
+  },
+
+  _removeAllChildrenAnnos: function _removeAllChildrenAnnos() {
+    Utils.queryAsync(this._removeAllChildrenAnnosStm);
+  },
+
   changeItemID: function BStore_changeItemID(oldID, newID) {
     // Remember the GUID change for incoming records
     this.aliases[oldID] = newID;
 
     // Update any existing annotation references
     this._findAnnoItems(PARENT_ANNO, oldID).forEach(function(itemId) {
-      Utils.anno(itemId, PARENT_ANNO, "T" + newID);
-    }, this);
-    this._findAnnoItems(PREDECESSOR_ANNO, oldID).forEach(function(itemId) {
-      Utils.anno(itemId, PREDECESSOR_ANNO, "R" + newID);
+      Utils.anno(itemId, PARENT_ANNO, newID);
     }, this);
 
     // Make sure there's an item to change GUIDs
-    let itemId = idForGUID(oldID);
+    let itemId = this.idForGUID(oldID);
     if (itemId <= 0)
       return;
 
     this._log.debug("Changing GUID " + oldID + " to " + newID);
     this._setGUID(itemId, newID);
-  },
 
-  _setGUID: function BStore__setGUID(itemId, guid) {
-    let collision = idForGUID(guid);
-    if (collision != -1) {
-      this._log.warn("Freeing up GUID " + guid  + " used by " + collision);
-      Svc.Annos.removeItemAnnotation(collision, "placesInternal/GUID");
-    }
-    Svc.Bookmark.setItemGUID(itemId, guid);
+    // Update parent
+    let parentid = this._bms.getFolderIdForItem(itemId);
+    this._updateChildrenAnno(parentid);
   },
 
   _getNode: function BStore__getNode(folder) {
     let query = this._hsvc.getNewQuery();
     query.setFolders([folder], 1);
     return this._hsvc.executeQuery(query, this._hsvc.getNewQueryOptions()).root;
   },
 
@@ -751,19 +721,32 @@ BookmarksStore.prototype = {
   _getStaticTitle: function BStore__getStaticTitle(id) {
     try {
       return Utils.anno(id, "bookmarks/staticTitle");
     } catch (e) {
       return "";
     }
   },
 
+  _getChildGUIDsForId: function _getChildGUIDsForId(itemid) {
+    let anno;
+    try {
+      anno = Utils.anno(itemid, CHILDREN_ANNO);
+    } catch(ex) {
+      // Ignore
+    }
+    if (anno)
+      return anno.split(",");
+
+    return this._updateChildrenAnno(itemid);
+  },
+
   // Create a record starting from the weave id (places guid)
   createRecord: function createRecord(id, collection) {
-    let placeId = idForGUID(id);
+    let placeId = this.idForGUID(id);
     let record;
     if (placeId <= 0) { // deleted item
       record = new PlacesItem(collection, id);
       record.deleted = true;
       return record;
     }
 
     let parent = Svc.Bookmark.getFolderIdForItem(placeId);
@@ -813,58 +796,183 @@ BookmarksStore.prototype = {
         if (siteURI != null)
           record.siteUri = siteURI.spec;
         record.feedUri = this._ls.getFeedURI(placeId).spec;
 
       } else {
         record = new BookmarkFolder(collection, id);
       }
 
-      record.parentName = Svc.Bookmark.getItemTitle(parent);
+      if (parent > 0)
+        record.parentName = Svc.Bookmark.getItemTitle(parent);
       record.title = this._bms.getItemTitle(placeId);
       record.description = this._getDescription(placeId);
+      record.children = this._getChildGUIDsForId(placeId);
       break;
 
     case this._bms.TYPE_SEPARATOR:
       record = new BookmarkSeparator(collection, id);
-      // Create a positioning identifier for the separator
-      record.parentName = Svc.Bookmark.getItemTitle(parent);
+      if (parent > 0)
+        record.parentName = Svc.Bookmark.getItemTitle(parent);
+      // Create a positioning identifier for the separator, used by _lazyMap
       record.pos = Svc.Bookmark.getItemIndex(placeId);
       break;
 
     case this._bms.TYPE_DYNAMIC_CONTAINER:
       record = new PlacesItem(collection, id);
       this._log.warn("Don't know how to serialize dynamic containers yet");
       break;
 
     default:
       record = new PlacesItem(collection, id);
       this._log.warn("Unknown item type, cannot serialize: " +
                      this._bms.getItemType(placeId));
     }
 
-    record.parentid = this._getParentGUIDForId(placeId);
-    record.predecessorid = this._getPredecessorGUIDForId(placeId);
+    record.parentid = this.GUIDForId(parent);
     record.sortindex = this._calculateIndex(record);
 
     return record;
   },
 
-  __frecencyStm: null,
+  _stmts: {},
+  _getStmt: function(query) {
+    if (query in this._stmts)
+      return this._stmts[query];
+
+    this._log.trace("Creating SQL statement: " + query);
+    return this._stmts[query] = Utils.createStatement(this._hsvc.DBConnection,
+                                                      query);
+  },
+
   get _frecencyStm() {
-    if (!this.__frecencyStm) {
-      this._log.trace("Creating SQL statement: _frecencyStm");
-      this.__frecencyStm = Utils.createStatement(
-        Svc.History.DBConnection,
+    return this._getStmt(
         "SELECT frecency " +
         "FROM moz_places " +
         "WHERE url = :url " +
         "LIMIT 1");
+  },
+
+  get _addGUIDAnnotationNameStm() {
+    let stmt = this._getStmt(
+      "INSERT OR IGNORE INTO moz_anno_attributes (name) VALUES (:anno_name)");
+    stmt.params.anno_name = GUID_ANNO;
+    return stmt;
+  },
+
+  get _checkGUIDItemAnnotationStm() {
+    let stmt = this._getStmt(
+      "SELECT b.id AS item_id, " +
+        "(SELECT id FROM moz_anno_attributes WHERE name = :anno_name) AS name_id, " +
+        "a.id AS anno_id, a.dateAdded AS anno_date " +
+      "FROM moz_bookmarks b " +
+      "LEFT JOIN moz_items_annos a ON a.item_id = b.id " +
+                                 "AND a.anno_attribute_id = name_id " +
+      "WHERE b.id = :item_id");
+    stmt.params.anno_name = GUID_ANNO;
+    return stmt;
+  },
+
+  get _addItemAnnotationStm() {
+    return this._getStmt(
+    "INSERT OR REPLACE INTO moz_items_annos " +
+      "(id, item_id, anno_attribute_id, mime_type, content, flags, " +
+       "expiration, type, dateAdded, lastModified) " +
+    "VALUES (:id, :item_id, :name_id, :mime_type, :content, :flags, " +
+            ":expiration, :type, :date_added, :last_modified)");
+  },
+
+  // Some helper functions to handle GUIDs
+  _setGUID: function _setGUID(id, guid) {
+    if (arguments.length == 1)
+      guid = Utils.makeGUID();
+
+    // Ensure annotation name exists
+    Utils.queryAsync(this._addGUIDAnnotationNameStm);
+
+    let stmt = this._checkGUIDItemAnnotationStm;
+    stmt.params.item_id = id;
+    let result = Utils.queryAsync(stmt, ["item_id", "name_id", "anno_id",
+                                         "anno_date"])[0];
+    if (!result) {
+      let log = Log4Moz.repository.getLogger("Engine.Bookmarks");
+      log.warn("Couldn't annotate bookmark id " + id);
+      return guid;
     }
-    return this.__frecencyStm;
+
+    stmt = this._addItemAnnotationStm;
+    if (result.anno_id) {
+      stmt.params.id = result.anno_id;
+      stmt.params.date_added = result.anno_date;
+    } else {
+      stmt.params.id = null;
+      stmt.params.date_added = Date.now() * 1000;
+    }
+    stmt.params.item_id = result.item_id;
+    stmt.params.name_id = result.name_id;
+    stmt.params.content = guid;
+    stmt.params.flags = 0;
+    stmt.params.expiration = Ci.nsIAnnotationService.EXPIRE_NEVER;
+    stmt.params.type = Ci.nsIAnnotationService.TYPE_STRING;
+    stmt.params.last_modified = Date.now() * 1000;
+    Utils.queryAsync(stmt);
+
+    return guid;
+  },
+
+  get _guidForIdStm() {
+    let stmt = this._getStmt(
+      "SELECT a.content AS guid " +
+      "FROM moz_items_annos a " +
+      "JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id " +
+      "JOIN moz_bookmarks b ON b.id = a.item_id " +
+      "WHERE n.name = :anno_name AND b.id = :item_id");
+    stmt.params.anno_name = GUID_ANNO;
+    return stmt;
+  },
+
+  GUIDForId: function GUIDForId(id) {
+    for (let [guid, specialId] in Iterator(kSpecialIds))
+      if (id == specialId)
+         return guid;
+
+    let stmt = this._guidForIdStm;
+    stmt.params.item_id = id;
+
+    // Use the existing GUID if it exists
+    let result = Utils.queryAsync(stmt, ["guid"])[0];
+    if (result)
+      return result.guid;
+
+    // Give the uri a GUID if it doesn't have one
+    return this._setGUID(id);
+  },
+
+  get _idForGUIDStm() {
+    let stmt = this._getStmt(
+      "SELECT a.item_id AS item_id " +
+      "FROM moz_items_annos a " +
+      "JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id " +
+      "WHERE n.name = :anno_name AND a.content = :guid");
+    stmt.params.anno_name = GUID_ANNO;
+    return stmt;
+  },
+
+  idForGUID: function idForGUID(guid) {
+    if (guid in kSpecialIds)
+      return kSpecialIds[guid];
+
+    let stmt = this._idForGUIDStm;
+    // guid might be a String object rather than a string.
+    stmt.params.guid = guid.toString();
+
+    let result = Utils.queryAsync(stmt, ["item_id"])[0];
+    if (result)
+      return result.item_id;
+    return -1;
   },
 
   _calculateIndex: function _calculateIndex(record) {
     // Ensure folders have a very high sort index so they're not synced last.
     if (record.type == "folder")
       return FOLDER_SORTINDEX;
 
     // For anything directly under the toolbar, give it a boost of more than an
@@ -879,91 +987,30 @@ BookmarksStore.prototype = {
       let result = Utils.queryAsync(this._frecencyStm, ["frecency"]);
       if (result.length)
         index += result[0].frecency;
     }
 
     return index;
   },
 
-  _getParentGUIDForId: function BStore__getParentGUIDForId(itemId) {
-    // Give the parent annotation if it exists
-    try {
-      // XXX Work around Bug 510628 by removing prepended parenT
-      return Utils.anno(itemId, PARENT_ANNO).slice(1);
-    }
-    catch(ex) {}
-
-    let parentid = this._bms.getFolderIdForItem(itemId);
-    if (parentid == -1) {
-      this._log.debug("Found orphan bookmark, reparenting to unfiled");
-      parentid = this._bms.unfiledBookmarksFolder;
-      this._bms.moveItem(itemId, parentid, -1);
-    }
-    return GUIDForId(parentid);
-  },
-
-  _getPredecessorGUIDForId: function BStore__getPredecessorGUIDForId(itemId) {
-    // Give the predecessor annotation if it exists
-    try {
-      // XXX Work around Bug 510628 by removing prepended predecessoR
-      return Utils.anno(itemId, PREDECESSOR_ANNO).slice(1);
-    }
-    catch(ex) {}
-
-    // Figure out the predecessor, unless it's the first item
-    let itemPos = Svc.Bookmark.getItemIndex(itemId);
-    if (itemPos == 0)
-      return;
-
-    // For items directly under unfiled/unsorted, give no predecessor
-    let parentId = Svc.Bookmark.getFolderIdForItem(itemId);
-    if (parentId == Svc.Bookmark.unfiledBookmarksFolder)
-      return;
-
-    let predecessorId = Svc.Bookmark.getIdForItemAt(parentId, itemPos - 1);
-    if (predecessorId == -1) {
-      this._log.debug("No predecessor directly before " + itemId + " under " +
-        parentId + " at " + itemPos);
-
-      // Find the predecessor before the item
-      do {
-        // No more items to check, it must be the first one
-        if (--itemPos < 0)
-          break;
-        predecessorId = Svc.Bookmark.getIdForItemAt(parentId, itemPos);
-      } while (predecessorId == -1);
-
-      // Fix up the item to be at the right position for next time
-      itemPos++;
-      this._log.debug("Fixing " + itemId + " to be at position " + itemPos);
-      Svc.Bookmark.moveItem(itemId, parentId, itemPos);
-
-      // There must be no predecessor for this item!
-      if (itemPos == 0)
-        return;
-    }
-
-    return GUIDForId(predecessorId);
-  },
-
   _getChildren: function BStore_getChildren(guid, items) {
     let node = guid; // the recursion case
     if (typeof(node) == "string") // callers will give us the guid as the first arg
-      node = this._getNode(idForGUID(guid));
+      node = this._getNode(this.idForGUID(guid));
 
     if (node.type == node.RESULT_TYPE_FOLDER &&
         !this._ls.isLivemark(node.itemId)) {
       node.QueryInterface(Ci.nsINavHistoryQueryResultNode);
       node.containerOpen = true;
 
       // Remember all the children GUIDs and recursively get more
       for (var i = 0; i < node.childCount; i++) {
         let child = node.getChild(i);
-        items[GUIDForId(child.itemId)] = true;
+        items[this.GUIDForId(child.itemId)] = true;
         this._getChildren(child, items);
       }
     }
 
     return items;
   },
 
   _tagURI: function BStore_tagURI(bmkURI, tags) {
@@ -974,17 +1021,18 @@ BookmarksStore.prototype = {
     let dummyURI = Utils.makeURI("about:weave#BStore_tagURI");
     this._ts.tagURI(dummyURI, tags);
     this._ts.untagURI(bmkURI, null);
     this._ts.tagURI(bmkURI, tags);
     this._ts.untagURI(dummyURI, null);
   },
 
   getAllIDs: function BStore_getAllIDs() {
-    let items = {};
+    let items = {"menu": true,
+                 "toolbar": true};
     for (let [guid, id] in Iterator(kSpecialIds))
       if (guid != "places" && guid != "tags")
         this._getChildren(guid, items);
     return items;
   },
 
   wipe: function BStore_wipe() {
     // Save a backup before clearing out all bookmarks
@@ -994,20 +1042,16 @@ BookmarksStore.prototype = {
       if (guid != "places")
         this._bms.removeFolderChildren(id);
   }
 };
 
 function BookmarksTracker(name) {
   Tracker.call(this, name);
 
-  // Ignore changes to the special roots
-  for (let guid in kSpecialIds)
-    this.ignoreID(guid);
-
   Svc.Obs.add("places-shutdown", this);
   Svc.Obs.add("weave:engine:start-tracking", this);
   Svc.Obs.add("weave:engine:stop-tracking", this);
 }
 BookmarksTracker.prototype = {
   __proto__: Tracker.prototype,
 
   _enabled: false,
@@ -1026,16 +1070,22 @@ BookmarksTracker.prototype = {
         }
         // Fall through to clean up.
       case "places-shutdown":
         // Explicitly nullify our references to our cached services so
         // we don't leak
         this.__ls = null;
         this.__bms = null;
         break;
+      case "weave:service:start-over":
+        // User has decided to stop syncing, we're going to stop tracking soon.
+        // This means we have to clean up the children annotations so that they
+        // won't be out of sync with reality if/when we start tracking again.
+        Engines.get("bookmarks")._store._removeAllChildrenAnnos();
+        break;
     }
   },
 
   __bms: null,
   get _bms() {
     if (!this.__bms)
       this.__bms = Cc["@mozilla.org/browser/nav-bookmarks-service;1"].
                    getService(Ci.nsINavBookmarksService);
@@ -1051,38 +1101,36 @@ BookmarksTracker.prototype = {
   },
 
   QueryInterface: XPCOMUtils.generateQI([
     Ci.nsINavBookmarkObserver,
     Ci.nsINavBookmarkObserver_MOZILLA_1_9_1_ADDITIONS,
     Ci.nsISupportsWeakReference
   ]),
 
+  _GUIDForId: function _GUIDForId(item_id) {
+    // Isn't indirection fun...
+    return Engines.get("bookmarks")._store.GUIDForId(item_id);
+  },
+
+  _updateChildrenAnno: function _updateChildrenAnno(itemid) {
+    return Engines.get("bookmarks")._store._updateChildrenAnno(itemid);
+  },
+
   /**
    * Add a bookmark (places) id to be uploaded and bump up the sync score
    *
    * @param itemId
    *        Places internal id of the bookmark to upload
    */
   _addId: function BMT__addId(itemId) {
-    if (this.addChangedID(GUIDForId(itemId)))
+    if (this.addChangedID(this._GUIDForId(itemId, true)))
       this._upScore();
   },
 
-  /**
-   * Add the successor id for the item that follows the given item
-   */
-  _addSuccessor: function BMT__addSuccessor(itemId) {
-    let parentId = Svc.Bookmark.getFolderIdForItem(itemId);
-    let itemPos = Svc.Bookmark.getItemIndex(itemId);
-    let succId = Svc.Bookmark.getIdForItemAt(parentId, itemPos + 1);
-    if (succId != -1)
-      this._addId(succId);
-  },
-
   /* Every add/remove/change is worth 10 points */
   _upScore: function BMT__upScore() {
     this.score += 10;
   },
 
   /**
    * Determine if a change should be ignored: we're ignoring everything or the
    * folder is for livemarks
@@ -1097,17 +1145,17 @@ BookmarksTracker.prototype = {
     if (this.ignoreAll)
       return true;
 
     // Ensure that the mobile bookmarks query is correct in the UI
     this._ensureMobileQuery();
 
     // Make sure to remove items that have the exclude annotation
     if (Svc.Annos.itemHasAnnotation(itemId, "places/excludeFromBackup")) {
-      this.removeChangedID(GUIDForId(itemId));
+      this.removeChangedID(this._GUIDForId(itemId, true));
       return true;
     }
 
     // Get the folder id if we weren't given one
     if (folder == null)
       folder = this._bms.getFolderIdForItem(itemId);
 
     let tags = kSpecialIds.tags;
@@ -1124,26 +1172,29 @@ BookmarksTracker.prototype = {
   },
 
   onItemAdded: function BMT_onEndUpdateBatch(itemId, folder, index) {
     if (this._ignore(itemId, folder))
       return;
 
     this._log.trace("onItemAdded: " + itemId);
     this._addId(itemId);
-    this._addSuccessor(itemId);
+    this._updateChildrenAnno(folder);
+    this._addId(folder);
   },
 
   onBeforeItemRemoved: function BMT_onBeforeItemRemoved(itemId) {
     if (this._ignore(itemId))
       return;
 
     this._log.trace("onBeforeItemRemoved: " + itemId);
     this._addId(itemId);
-    this._addSuccessor(itemId);
+    let folder = Svc.Bookmark.getFolderIdForItem(itemId);
+    this._updateChildrenAnno(folder);
+    this._addId(folder);
   },
 
   _ensureMobileQuery: function _ensureMobileQuery() {
     let anno = "PlacesOrganizer/OrganizerQuery";
     let find = function(val) Svc.Annos.getItemsWithAnnotation(anno, {}).filter(
       function(id) Utils.anno(id, anno) == val);
 
     // Don't continue if the Library isn't ready
@@ -1197,26 +1248,25 @@ BookmarksTracker.prototype = {
     this._addId(itemId);
   },
 
   onItemMoved: function BMT_onItemMoved(itemId, oldParent, oldIndex, newParent, newIndex) {
     if (this._ignore(itemId))
       return;
 
     this._log.trace("onItemMoved: " + itemId);
-    this._addId(itemId);
-    this._addSuccessor(itemId);
-
-    // Get the thing that's now at the old place
-    let oldSucc = Svc.Bookmark.getIdForItemAt(oldParent, oldIndex);
-    if (oldSucc != -1)
-      this._addId(oldSucc);
+    this._updateChildrenAnno(oldParent);
+    this._addId(oldParent);
+    if (oldParent != newParent) {
+      this._addId(itemId);
+      this._updateChildrenAnno(newParent);
+      this._addId(newParent);
+    }
 
     // Remove any position annotations now that the user moved the item
     Svc.Annos.removeItemAnnotation(itemId, PARENT_ANNO);
-    Svc.Annos.removeItemAnnotation(itemId, PREDECESSOR_ANNO);
   },
 
   onBeginUpdateBatch: function BMT_onBeginUpdateBatch() {},
   onEndUpdateBatch: function BMT_onEndUpdateBatch() {},
   onItemRemoved: function BMT_onItemRemoved(itemId, folder, index) {},
   onItemVisited: function BMT_onItemVisited(itemId, aVisitID, time) {}
 };
--- a/services/sync/modules/engines/history.js
+++ b/services/sync/modules/engines/history.js
@@ -14,16 +14,17 @@
  * The Original Code is Weave
  *
  * The Initial Developer of the Original Code is Mozilla.
  * Portions created by the Initial Developer are Copyright (C) 2008
  * the Initial Developer. All Rights Reserved.
  *
  * Contributor(s):
  *  Dan Mills <thunder@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
@@ -38,25 +39,27 @@ const EXPORTED_SYMBOLS = ['HistoryEngine
 
 const Cc = Components.classes;
 const Ci = Components.interfaces;
 const Cu = Components.utils;
 
 const GUID_ANNO = "sync/guid";
 
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
+Cu.import("resource://services-sync/constants.js");
 Cu.import("resource://services-sync/engines.js");
 Cu.import("resource://services-sync/stores.js");
 Cu.import("resource://services-sync/trackers.js");
 Cu.import("resource://services-sync/type_records/history.js");
 Cu.import("resource://services-sync/util.js");
 Cu.import("resource://services-sync/log4moz.js");
 
 function HistoryEngine() {
   SyncEngine.call(this, "History");
+  this.downloadLimit = MAX_HISTORY_DOWNLOAD;
 }
 HistoryEngine.prototype = {
   __proto__: SyncEngine.prototype,
   _recordObj: HistoryRec,
   _storeObj: HistoryStore,
   _trackerObj: HistoryTracker,
 
   _sync: Utils.batchSync("History", SyncEngine),
@@ -317,17 +320,17 @@ HistoryStore.prototype = {
   changeItemID: function HStore_changeItemID(oldID, newID) {
     this.setGUID(this._findURLByGUID(oldID).url, newID);
   },
 
 
   getAllIDs: function HistStore_getAllIDs() {
     // Only get places visited within the last 30 days (30*24*60*60*1000ms)
     this._allUrlStm.params.cutoff_date = (Date.now() - 2592000000) * 1000;
-    this._allUrlStm.params.max_results = 5000;
+    this._allUrlStm.params.max_results = MAX_HISTORY_UPLOAD;
 
     let urls = Utils.queryAsync(this._allUrlStm, "url");
     let self = this;
     return urls.reduce(function(ids, item) {
       ids[self.GUIDForUri(item.url, true)] = item.url;
       return ids;
     }, {});
   },
--- a/services/sync/modules/engines/prefs.js
+++ b/services/sync/modules/engines/prefs.js
@@ -128,26 +128,23 @@ PrefStore.prototype = {
     return values;
   },
 
   _setAllPrefs: function PrefStore__setAllPrefs(values) {
     // cache 
     let ltmExists = true;
     let ltm = {};
     let enabledBefore = false;
+    let enabledPref = "lightweightThemes.isThemeSelected";
     let prevTheme = "";
     try {
       Cu.import("resource://gre/modules/LightweightThemeManager.jsm", ltm);
       ltm = ltm.LightweightThemeManager;
-
-      let enabledPref = "lightweightThemes.isThemeSelected";
-      if (this._prefs.getPrefType(enabledPref) == this._prefs.PREF_BOOL) {
-        enabledBefore = this._prefs.getBoolPref(enabledPref);
-        prevTheme = ltm.currentTheme;
-      }
+      enabledBefore = this._prefs.get(enabledPref, false);
+      prevTheme = ltm.currentTheme;
     } catch(ex) {
       ltmExists = false;
     } // LightweightThemeManager only exists in Firefox 3.6+
 
     for (let [pref, value] in Iterator(values)) {
       if (!this._isSynced(pref))
         continue;
 
@@ -161,17 +158,17 @@ PrefStore.prototype = {
         this._prefs.set(pref, value);
       } catch(ex) {
         this._log.trace("Failed to set pref: " + pref + ": " + ex);
       } 
     }
 
     // Notify the lightweight theme manager of all the new values
     if (ltmExists) {
-      let enabledNow = this._prefs.getBoolPref("lightweightThemes.isThemeSelected");    
+      let enabledNow = this._prefs.get(enabledPref, false);
       if (enabledBefore && !enabledNow)
         ltm.currentTheme = null;
       else if (enabledNow && ltm.usedThemes[0] != prevTheme) {
         ltm.currentTheme = null;
         ltm.currentTheme = ltm.usedThemes[0];
       }
     }
   },
--- a/services/sync/modules/service.js
+++ b/services/sync/modules/service.js
@@ -1057,27 +1057,50 @@ WeaveSvc.prototype = {
 
   // Stuff we need to do after login, before we can really do
   // anything (e.g. key setup).
   _remoteSetup: function WeaveSvc__remoteSetup(infoResponse) {
     let reset = false;
 
     this._log.debug("Fetching global metadata record");
     let meta = Records.get(this.metaURL);
+    
+    // Checking modified time of the meta record.
+    if (infoResponse &&
+        (infoResponse.obj.meta != this.metaModified) &&
+        !meta.isNew) {
+      
+      // Delete the cached meta record...
+      this._log.debug("Clearing cached meta record. metaModified is " +
+          JSON.stringify(this.metaModified) + ", setting to " +
+          JSON.stringify(infoResponse.obj.meta));
+      Records.del(this.metaURL);
+      
+      // ... fetch the current record from the server, and COPY THE FLAGS.
+      let newMeta       = Records.get(this.metaURL);
+      newMeta.isNew     = meta.isNew;
+      newMeta.changed   = meta.changed;
+      
+      // Switch in the new meta object and record the new time.
+      meta              = newMeta;
+      this.metaModified = infoResponse.obj.meta;
+    }
 
     let remoteVersion = (meta && meta.payload.storageVersion)?
       meta.payload.storageVersion : "";
 
     this._log.debug(["Weave Version:", WEAVE_VERSION, "Local Storage:",
       STORAGE_VERSION, "Remote Storage:", remoteVersion].join(" "));
 
     // Check for cases that require a fresh start. When comparing remoteVersion,
     // we need to convert it to a number as older clients used it as a string.
     if (!meta || !meta.payload.storageVersion || !meta.payload.syncID ||
         STORAGE_VERSION > parseFloat(remoteVersion)) {
+      
+      this._log.info("One of: no meta, no meta storageVersion, or no meta syncID. Fresh start needed.");
 
       // abort the server wipe if the GET status was anything other than 404 or 200
       let status = Records.response.status;
       if (status != 200 && status != 404) {
         this._checkServerError(Records.response);
         Status.sync = METARECORD_DOWNLOAD_FAIL;
         this._log.warn("Unknown error while downloading metadata record. " +
                        "Aborting sync.");
@@ -1103,16 +1126,18 @@ WeaveSvc.prototype = {
       return true;
     }
     else if (remoteVersion > STORAGE_VERSION) {
       Status.sync = VERSION_OUT_OF_DATE;
       this._log.warn("Upgrade required to access newer storage version.");
       return false;
     }
     else if (meta.payload.syncID != this.syncID) {
+      
+      this._log.info("Sync IDs differ. Local is " + this.syncID + ", remote is " + meta.payload.syncID);
       this.resetClient();
       this.syncID = meta.payload.syncID;
       this._log.debug("Clear cached values and take syncId: " + this.syncID);
 
       if (!this.upgradeSyncKey(meta.payload.syncID)) {
         this._log.warn("Failed to upgrade sync key. Failing remote setup.");
         return false;
       }
@@ -1124,30 +1149,30 @@ WeaveSvc.prototype = {
 
       // bug 545725 - re-verify creds and fail sanely
       if (!this.verifyLogin()) {
         Status.sync = CREDENTIALS_CHANGED;
         this._log.info("Credentials have changed, aborting sync and forcing re-login.");
         return false;
       }
 
-        return true;
+      return true;
     }
     else {
       if (!this.upgradeSyncKey(meta.payload.syncID)) {
         this._log.warn("Failed to upgrade sync key. Failing remote setup.");
         return false;
       }
 
       if (!this.verifyAndFetchSymmetricKeys(infoResponse)) {
         this._log.warn("Failed to fetch symmetric keys. Failing remote setup.");
         return false;
       }
 
-          return true;
+      return true;
     }
   },
 
   /**
    * Determine if a sync should run.
    * 
    * @param ignore [optional]
    *        array of reasons to ignore when checking
@@ -1403,26 +1428,16 @@ WeaveSvc.prototype = {
     // Figure out what the last modified time is for each collection
     let info = this._fetchInfo(infoURL, true);
     this.globalScore = 0;
 
     // Convert the response to an object and read out the modified times
     for each (let engine in [Clients].concat(Engines.getAll()))
       engine.lastModified = info.obj[engine.name] || 0;
 
-    // If the modified time of the meta record ever changes, clear the cache.
-    // ... unless meta is marked as new.
-    if ((info.obj.meta != this.metaModified) && !Records.get(this.metaURL).isNew) {
-      this._log.debug("Clearing cached meta record. metaModified is " +
-          JSON.stringify(this.metaModified) + ", setting to " +
-          JSON.stringify(info.obj.meta));
-      Records.del(this.metaURL);
-      this.metaModified = info.obj.meta;
-    }
-
     if (!(this._remoteSetup(info)))
       throw "aborting sync, remote setup failed";
 
     // Make sure we have an up-to-date list of clients before sending commands
     this._log.trace("Refreshing client list");
     this._syncEngine(Clients);
 
     // Wipe data in the desired direction if necessary
@@ -1512,16 +1527,25 @@ WeaveSvc.prototype = {
       this.syncThreshold = hasMobile ? MULTI_MOBILE_THRESHOLD : MULTI_DESKTOP_THRESHOLD;
     }
   },
 
   _updateEnabledEngines: function _updateEnabledEngines() {
     let meta = Records.get(this.metaURL);
     if (meta.isNew || !meta.payload.engines)
       return;
+    
+    // If we're the only client, and no engines are marked as enabled,
+    // thumb our noses at the server data: it can't be right.
+    // Belt-and-suspenders approach to Bug 615926.
+    if ((this.numClients <= 1) &&
+        ([e for (e in meta.payload.engines) if (e != "clients")].length == 0)) {
+      this._log.info("One client and no enabled engines: not touching local engine status.");
+      return;
+    }
 
     this._ignorePrefObserver = true;
 
     let enabled = [eng.name for each (eng in Engines.getEnabled())];
     for (let engineName in meta.payload.engines) {
       let index = enabled.indexOf(engineName);
       if (index != -1) {
         // The engine is enabled locally. Nothing to do.
--- a/services/sync/modules/type_records/bookmark.js
+++ b/services/sync/modules/type_records/bookmark.js
@@ -81,17 +81,17 @@ PlacesItem.prototype = {
     throw "Unknown places item object type: " + type;
   },
 
   __proto__: CryptoWrapper.prototype,
   _logName: "Record.PlacesItem",
 };
 
 Utils.deferGetSet(PlacesItem, "cleartext", ["hasDupe", "parentid", "parentName",
-  "predecessorid", "type"]);
+                                            "type"]);
 
 function Bookmark(collection, id, type) {
   PlacesItem.call(this, collection, id, type || "bookmark");
 }
 Bookmark.prototype = {
   __proto__: PlacesItem.prototype,
   _logName: "Record.Bookmark",
 };
@@ -122,17 +122,18 @@ Utils.deferGetSet(BookmarkQuery, "cleart
 function BookmarkFolder(collection, id, type) {
   PlacesItem.call(this, collection, id, type || "folder");
 }
 BookmarkFolder.prototype = {
   __proto__: PlacesItem.prototype,
   _logName: "Record.Folder",
 };
 
-Utils.deferGetSet(BookmarkFolder, "cleartext", ["description", "title"]);
+Utils.deferGetSet(BookmarkFolder, "cleartext", ["description", "title",
+                                                "children"]);
 
 function Livemark(collection, id) {
   BookmarkFolder.call(this, collection, id, "livemark");
 }
 Livemark.prototype = {
   __proto__: BookmarkFolder.prototype,
   _logName: "Record.Livemark",
 };
--- a/services/sync/tests/unit/head_helpers.js
+++ b/services/sync/tests/unit/head_helpers.js
@@ -387,8 +387,24 @@ function SyncTestingInfrastructure(engin
  * @usage _("Hello World") -> prints "Hello World"
  * @usage _(1, 2, 3) -> prints "1 2 3"
  */
 let _ = function(some, debug, text, to) print(Array.slice(arguments).join(" "));
 
 _("Setting the identity for passphrase");
 Cu.import("resource://services-sync/identity.js");
 
+
+/*
+ * Test setup helpers.
+ */
+
+// Turn WBO cleartext into "encrypted" payload as it goes over the wire
+function encryptPayload(cleartext) {
+  if (typeof cleartext == "object") {
+    cleartext = JSON.stringify(cleartext);
+  }
+
+  return {ciphertext: cleartext, // ciphertext == cleartext with fake crypto
+          IV: "irrelevant",
+          hmac: Utils.sha256HMAC(cleartext, Utils.makeHMACKey(""))};
+}
+
--- a/services/sync/tests/unit/head_http_server.js
+++ b/services/sync/tests/unit/head_http_server.js
@@ -254,8 +254,17 @@ ServerCollection.prototype = {
       }
       response.setHeader('X-Weave-Timestamp', ''+Date.now()/1000, false);
       response.setStatusLine(request.httpVersion, statusCode, status);
       response.bodyOutputStream.write(body, body.length);
     };
   }
 
 };
+
+/*
+ * Test setup helpers.
+ */
+function sync_httpd_setup(handlers) {
+  handlers["/1.0/foo/storage/meta/global"]
+      = (new ServerWBO('global', {})).handler();
+  return httpd_setup(handlers);
+}
--- a/services/sync/tests/unit/test_bookmark_order.js
+++ b/services/sync/tests/unit/test_bookmark_order.js
@@ -34,138 +34,101 @@ function check(expected) {
   let bookmarks = getBookmarks(Svc.Bookmark.unfiledBookmarksFolder);
 
   _("Checking if the bookmark structure is", JSON.stringify(expected));
   _("Got bookmarks:", JSON.stringify(bookmarks));
   do_check_true(Utils.deepEquals(bookmarks, expected));
 }
 
 function run_test() {
+  let store = new BookmarksEngine()._store;
+  initTestLogging("Trace");
+
   _("Starting with a clean slate of no bookmarks");
-  let store = new (new BookmarksEngine())._storeObj();
   store.wipe();
   check([]);
 
-  function $B(name, parent, pred) {
+  function bookmark(name, parent) {
     let bookmark = new Bookmark("http://weave.server/my-bookmark");
     bookmark.id = name;
     bookmark.title = name;
     bookmark.bmkUri = "http://uri/";
     bookmark.parentid = parent || "unfiled";
-    bookmark.predecessorid = pred;
     bookmark.tags = [];
-    store.applyIncoming(bookmark);
+    return bookmark;
   }
 
-  function $F(name, parent, pred) {
+  function folder(name, parent, children) {
     let folder = new BookmarkFolder("http://weave.server/my-bookmark-folder");
     folder.id = name;
     folder.title = name;
     folder.parentid = parent || "unfiled";
-    folder.predecessorid = pred;
-    store.applyIncoming(folder);
+    folder.children = children;
+    return folder;
+  }
+
+  function apply(record) {
+    store._childrenToOrder = {};
+    store.applyIncoming(record);
+    store._orderChildren();
+    delete store._childrenToOrder;
   }
 
   _("basic add first bookmark");
-  $B("10", "");
+  apply(bookmark("10", ""));
   check(["10"]);
 
   _("basic append behind 10");
-  $B("20", "", "10");
+  apply(bookmark("20", ""));
   check(["10", "20"]);
 
   _("basic create in folder");
-  $F("f30", "", "20");
-  $B("31", "f30");
+  apply(bookmark("31", "f30"));
+  let f30 = folder("f30", "", ["31"]);
+  apply(f30);
   check(["10", "20", ["31"]]);
 
-  _("insert missing predecessor -> append");
-  $B("50", "", "f40");
-  check(["10", "20", ["31"], "50"]);
-
-  _("insert missing parent -> append");
-  $B("41", "f40");
-  check(["10", "20", ["31"], "50", "41"]);
+  _("insert missing parent -> append to unfiled");
+  apply(bookmark("41", "f40"));
+  check(["10", "20", ["31"], "41"]);
 
   _("insert another missing parent -> append");
-  $B("42", "f40", "41");
-  check(["10", "20", ["31"], "50", "41", "42"]);
+  apply(bookmark("42", "f40"));
+  check(["10", "20", ["31"], "41", "42"]);
 
   _("insert folder -> move children and followers");
-  $F("f40", "", "f30");
-  check(["10", "20", ["31"], ["41", "42"], "50"]);
+  let f40 = folder("f40", "", ["41", "42"]);
+  apply(f40);
+  check(["10", "20", ["31"], ["41", "42"]]);
 
-  _("Moving 10 behind 50 -> update 10, 20");
-  $B("10", "", "50");
-  $B("20", "");
-  check(["20", ["31"], ["41", "42"], "50", "10"]);
+  _("Moving 41 behind 42 -> update f40");
+  f40.children = ["42", "41"];
+  apply(f40);
+  check(["10", "20", ["31"], ["42", "41"]]);
 
   _("Moving 10 back to front -> update 10, 20");
-  $B("10", "");
-  $B("20", "", "10");
-  check(["10", "20", ["31"], ["41", "42"], "50"]);
-
-  _("Moving 10 behind 50 in different order -> update 20, 10");
-  $B("20", "");
-  $B("10", "", "50");
-  check(["20", ["31"], ["41", "42"], "50", "10"]);
-
-  _("Moving 10 back to front in different order -> update 20, 10");
-  $B("20", "", "10");
-  $B("10", "");
-  check(["10", "20", ["31"], ["41", "42"], "50"]);
+  f40.children = ["41", "42"];
+  apply(f40);
+  check(["10", "20", ["31"], ["41", "42"]]);
 
-  _("Moving 50 behind 42 in f40 -> update 50");
-  $B("50", "f40", "42");
-  check(["10", "20", ["31"], ["41", "42", "50"]]);
+  _("Moving 20 behind 42 in f40 -> update 50");
+  apply(bookmark("20", "f40"));
+  check(["10", ["31"], ["41", "42", "20"]]);
 
-  _("Moving 10 in front of 31 in f30 -> update 10, 20, 31");
-  $B("10", "f30");
-  $B("20", "");
-  $B("31", "f30", "10");
-  check(["20", ["10", "31"], ["41", "42", "50"]]);
-
-  _("Moving 20 between 10 and 31 -> update 20, f30, 31");
-  $B("20", "f30", "10");
-  $F("f30", "");
-  $B("31", "f30", "20");
-  check([["10", "20", "31"], ["41", "42", "50"]]);
+  _("Moving 10 in front of 31 in f30 -> update 10, f30");
+  apply(bookmark("10", "f30"));
+  f30.children = ["10", "31"];
+  apply(f30);
+  check([["10", "31"], ["41", "42", "20"]]);
 
-  _("Move 20 back to front -> update 20, f30, 31");
-  $B("20", "");
-  $F("f30", "", "20");
-  $B("31", "f30", "10");
-  check(["20", ["10", "31"], ["41", "42", "50"]]);
-
-  _("Moving 20 between 10 and 31 different order -> update f30, 20, 31");
-  $F("f30", "");
-  $B("20", "f30", "10");
-  $B("31", "f30", "20");
-  check([["10", "20", "31"], ["41", "42", "50"]]);
-
-  _("Move 20 back to front different order -> update f30, 31, 20");
-  $F("f30", "", "20");
-  $B("31", "f30", "10");
-  $B("20", "");
-  check(["20", ["10", "31"], ["41", "42", "50"]]);
+  _("Moving 20 from f40 to f30 -> update 20, f30");
+  apply(bookmark("20", "f30"));
+  f30.children = ["10", "20", "31"];
+  apply(f30);
+  check([["10", "20", "31"], ["41", "42"]]);
 
-  _("Moving 20 between 10 and 31 different order 2 -> update 31, f30, 20");
-  $B("31", "f30", "20");
-  $F("f30", "");
-  $B("20", "f30", "10");
-  check([["10", "20", "31"], ["41", "42", "50"]]);
+  _("Move 20 back to front -> update 20, f30");
+  apply(bookmark("20", ""));
+  f30.children = ["10", "31"];
+  apply(f30);
+  check([["10", "31"], ["41", "42"], "20"]);
 
-  _("Move 20 back to front different order 2 -> update 31, f30, 20");
-  $B("31", "f30", "10");
-  $F("f30", "", "20");
-  $B("20", "");
-  check(["20", ["10", "31"], ["41", "42", "50"]]);
-
-  _("Move 10, 31 to f40 but update in reverse -> update 41, 31, 10");
-  $B("41", "f40", "31");
-  $B("31", "f40", "10");
-  $B("10", "f40");
-  check(["20", [], ["10", "31", "41", "42", "50"]]);
-
-  _("Reparent f40 into f30");
-  $F("f40", "f30");
-  check(["20", [["10", "31", "41", "42", "50"]]]);
 }
deleted file mode 100644
--- a/services/sync/tests/unit/test_bookmark_predecessor.js
+++ /dev/null
@@ -1,44 +0,0 @@
-_("Make sure bad bookmarks can still get their predecessors");
-Cu.import("resource://services-sync/engines/bookmarks.js");
-Cu.import("resource://services-sync/util.js");
-
-function run_test() {
-  let baseuri = "http://fake/uri/";
-
-  _("Starting with a clean slate of no bookmarks");
-  let store = new (new BookmarksEngine())._storeObj();
-  store.wipe();
-
-  let uri = Utils.makeURI("http://uri/");
-  function insert(pos, folder) {
-    folder = folder || Svc.Bookmark.toolbarFolder;
-    let name = "pos" + pos;
-    let bmk = Svc.Bookmark.insertBookmark(folder, uri, pos, name);
-    Svc.Bookmark.setItemGUID(bmk, name);
-    return bmk;
-  }
-
-  _("Creating a couple bookmarks that create holes");
-  let first = insert(5);
-  let second = insert(10);
-
-  _("Making sure the record created for the first has no predecessor");
-  let pos5 = store.createRecord("pos5");
-  do_check_eq(pos5.predecessorid, undefined);
-
-  _("Making sure the second record has the first as its predecessor");
-  let pos10 = store.createRecord("pos10");
-  do_check_eq(pos10.predecessorid, "pos5");
-
-  _("Make sure the index of item gets fixed");
-  do_check_eq(Svc.Bookmark.getItemIndex(first), 0);
-  do_check_eq(Svc.Bookmark.getItemIndex(second), 1);
-
-  _("Make sure things that are in unsorted don't set the predecessor");
-  insert(0, Svc.Bookmark.unfiledBookmarksFolder);
-  insert(1, Svc.Bookmark.unfiledBookmarksFolder);
-  do_check_eq(store.createRecord("pos0").predecessorid,
-              undefined);
-  do_check_eq(store.createRecord("pos1").predecessorid,
-              undefined);
-}
--- a/services/sync/tests/unit/test_bookmark_store.js
+++ b/services/sync/tests/unit/test_bookmark_store.js
@@ -1,56 +1,164 @@
+Cu.import("resource://services-sync/engines.js");
 Cu.import("resource://services-sync/engines/bookmarks.js");
+Cu.import("resource://services-sync/type_records/bookmark.js");
 Cu.import("resource://services-sync/util.js");
 
-function run_test() {
-  let store = new BookmarksEngine()._store;
-  store.wipe();
+Engines.register(BookmarksEngine);
+let engine = Engines.get("bookmarks");
+let store = engine._store;
+let fxuri = Utils.makeURI("http://getfirefox.com/");
+let tburi = Utils.makeURI("http://getthunderbird.com/");
 
+function test_bookmark_create() {
   try {
     _("Ensure the record isn't present yet.");
-    let fxuri = Utils.makeURI("http://getfirefox.com/");
     let ids = Svc.Bookmark.getBookmarkIdsForURI(fxuri, {});
     do_check_eq(ids.length, 0);
 
     _("Let's create a new record.");
-    let fxrecord = {id: "{5d81b87c-d5fc-42d9-a114-d69b7342f10e}0",
-                    type: "bookmark",
-                    bmkUri: fxuri.spec,
-                    title: "Get Firefox!",
-                    tags: [],
-                    keyword: "awesome",
-                    loadInSidebar: false,
-                    parentName: "Bookmarks Toolbar",
-                    parentid: "toolbar"};
+    let fxrecord = new Bookmark("bookmarks", "get-firefox1");
+    fxrecord.bmkUri        = fxuri.spec;
+    fxrecord.description   = "Firefox is awesome.";
+    fxrecord.title         = "Get Firefox!";
+    fxrecord.tags          = ["firefox", "awesome", "browser"];
+    fxrecord.keyword       = "awesome";
+    fxrecord.loadInSidebar = false;
+    fxrecord.parentName    = "Bookmarks Toolbar";
+    fxrecord.parentid      = "toolbar";
     store.applyIncoming(fxrecord);
 
     _("Verify it has been created correctly.");
-    ids = Svc.Bookmark.getBookmarkIdsForURI(fxuri, {});
-    do_check_eq(ids.length, 1);
-    let id = ids[0];
-    do_check_eq(Svc.Bookmark.getItemGUID(id), fxrecord.id);
+    let id = store.idForGUID(fxrecord.id);
+    do_check_eq(store.GUIDForId(id), fxrecord.id);
     do_check_eq(Svc.Bookmark.getItemType(id), Svc.Bookmark.TYPE_BOOKMARK);
     do_check_eq(Svc.Bookmark.getItemTitle(id), fxrecord.title);
     do_check_eq(Svc.Bookmark.getFolderIdForItem(id),
                 Svc.Bookmark.toolbarFolder);
     do_check_eq(Svc.Bookmark.getKeywordForBookmark(id), fxrecord.keyword);
 
     _("Have the store create a new record object. Verify that it has the same data.");
     let newrecord = store.createRecord(fxrecord.id);
-    for each (let property in ["type", "bmkUri", "title", "keyword",
-                               "parentName", "parentid"])
-      do_check_eq(newrecord[property], fxrecord[property]);      
+    do_check_true(newrecord instanceof Bookmark);
+    for each (let property in ["type", "bmkUri", "description", "title",
+                               "keyword", "parentName", "parentid"])
+      do_check_eq(newrecord[property], fxrecord[property]);
+    do_check_true(Utils.deepEquals(newrecord.tags.sort(),
+                                   fxrecord.tags.sort()));
 
     _("The calculated sort index is based on frecency data.");
     do_check_true(newrecord.sortindex >= 150);
+  } finally {
+    _("Clean up.");
+    store.wipe();
+  }
+}
+
+function test_folder_create() {
+  try {
+    _("Create a folder.");
+    let folder = new BookmarkFolder("bookmarks", "testfolder-1");
+    folder.parentName = "Bookmarks Toolbar";
+    folder.parentid   = "toolbar";
+    folder.title      = "Test Folder";
+    store.applyIncoming(folder);
+
+    _("Verify it has been created correctly.");
+    let id = store.idForGUID(folder.id);
+    do_check_eq(Svc.Bookmark.getItemType(id), Svc.Bookmark.TYPE_FOLDER);
+    do_check_eq(Svc.Bookmark.getItemTitle(id), folder.title);
+    do_check_eq(Svc.Bookmark.getFolderIdForItem(id),
+                Svc.Bookmark.toolbarFolder);
+
+    _("Have the store create a new record object. Verify that it has the same data.");
+    let newrecord = store.createRecord(folder.id);
+    do_check_true(newrecord instanceof BookmarkFolder);
+    for each (let property in ["title","title", "parentName", "parentid"])
+      do_check_eq(newrecord[property], folder[property]);      
 
     _("Folders have high sort index to ensure they're synced first.");
-    let folder_id = Svc.Bookmark.createFolder(Svc.Bookmark.toolbarFolder,
-                                              "Test Folder", 0);
-    let folder_guid = Svc.Bookmark.getItemGUID(folder_id);
-    let folder_record = store.createRecord(folder_guid);
-    do_check_eq(folder_record.sortindex, 1000000);
+    do_check_eq(newrecord.sortindex, 1000000);
   } finally {
     _("Clean up.");
     store.wipe();
   }
 }
+
+function test_move_folder() {
+  try {
+    _("Create two folders and a bookmark in one of them.");
+    let folder1_id = Svc.Bookmark.createFolder(
+      Svc.Bookmark.toolbarFolder, "Folder1", 0);
+    let folder1_guid = store.GUIDForId(folder1_id);
+    let folder2_id = Svc.Bookmark.createFolder(
+      Svc.Bookmark.toolbarFolder, "Folder2", 0);
+    let folder2_guid = store.GUIDForId(folder2_id);
+    let bmk_id = Svc.Bookmark.insertBookmark(
+      folder1_id, fxuri, Svc.Bookmark.DEFAULT_INDEX, "Get Firefox!");
+    let bmk_guid = store.GUIDForId(bmk_id);
+
+    _("Get a record, reparent it and apply it to the store.");
+    let record = store.createRecord(bmk_guid);
+    do_check_eq(record.parentid, folder1_guid);
+    record.parentid = folder2_guid;
+    record.description = ""; //TODO for some reason we need this
+    store.applyIncoming(record);
+
+    _("Verify the new parent.");
+    let new_folder_id = Svc.Bookmark.getFolderIdForItem(bmk_id);
+    do_check_eq(store.GUIDForId(new_folder_id), folder2_guid);
+  } finally {
+    _("Clean up.");
+    store.wipe();
+  }
+}
+
+function test_move_order() {
+  // Make sure the tracker is turned on.
+  Svc.Obs.notify("weave:engine:start-tracking");
+  try {
+    _("Create two bookmarks");
+    let bmk1_id = Svc.Bookmark.insertBookmark(
+      Svc.Bookmark.toolbarFolder, fxuri, Svc.Bookmark.DEFAULT_INDEX,
+      "Get Firefox!");
+    let bmk1_guid = store.GUIDForId(bmk1_id);
+    let bmk2_id = Svc.Bookmark.insertBookmark(
+      Svc.Bookmark.toolbarFolder, tburi, Svc.Bookmark.DEFAULT_INDEX,
+      "Get Thunderbird!");
+    let bmk2_guid = store.GUIDForId(bmk2_id);
+
+    _("Verify order.");
+    do_check_eq(Svc.Bookmark.getItemIndex(bmk1_id), 0);
+    do_check_eq(Svc.Bookmark.getItemIndex(bmk2_id), 1);
+    let toolbar = store.createRecord("toolbar");
+    dump(JSON.stringify(toolbar.cleartext));
+    do_check_eq(toolbar.children.length, 2);
+    do_check_eq(toolbar.children[0], bmk1_guid);
+    do_check_eq(toolbar.children[1], bmk2_guid);
+
+    _("Move bookmarks around.");
+    store._childrenToOrder = {};
+    toolbar.children = [bmk2_guid, bmk1_guid];
+    store.applyIncoming(toolbar);
+    // Bookmarks engine does this at the end of _processIncoming
+    engine._tracker.ignoreAll = true;
+    store._orderChildren();
+    engine._tracker.ignoreAll = false;
+    delete store._childrenToOrder;
+
+    _("Verify new order.");
+    do_check_eq(Svc.Bookmark.getItemIndex(bmk2_id), 0);
+    do_check_eq(Svc.Bookmark.getItemIndex(bmk1_id), 1);
+
+  } finally {
+    Svc.Obs.notify("weave:engine:stop-tracking");
+    _("Clean up.");
+    store.wipe();
+  }
+}
+
+function run_test() {
+  test_bookmark_create();
+  test_folder_create();
+  test_move_folder();
+  test_move_order();
+}
--- a/services/sync/tests/unit/test_bookmark_tracker.js
+++ b/services/sync/tests/unit/test_bookmark_tracker.js
@@ -1,13 +1,15 @@
+Cu.import("resource://services-sync/engines.js");
 Cu.import("resource://services-sync/engines/bookmarks.js");
 Cu.import("resource://services-sync/util.js");
 
 function run_test() {
-  let engine = new BookmarksEngine();
+  Engines.register(BookmarksEngine);
+  let engine = Engines.get("bookmarks");
   engine._store.wipe();
 
   _("Verify we've got an empty tracker to work with.");
   let tracker = engine._tracker;
   do_check_eq([id for (id in tracker.changedIDs)].length, 0);
 
   let folder = Svc.Bookmark.createFolder(Svc.Bookmark.bookmarksMenuFolder,
                                          "Test Folder",
@@ -22,22 +24,24 @@ function run_test() {
   try {
     _("Create bookmark. Won't show because we haven't started tracking yet");
     createBmk();
     do_check_eq([id for (id in tracker.changedIDs)].length, 0);
 
     _("Tell the tracker to start tracking changes.");
     Svc.Obs.notify("weave:engine:start-tracking");
     createBmk();
-    do_check_eq([id for (id in tracker.changedIDs)].length, 1);
+    // We expect two changed items because the containing folder
+    // changed as well (new child).
+    do_check_eq([id for (id in tracker.changedIDs)].length, 2);
 
     _("Notifying twice won't do any harm.");
     Svc.Obs.notify("weave:engine:start-tracking");
     createBmk();
-    do_check_eq([id for (id in tracker.changedIDs)].length, 2);
+    do_check_eq([id for (id in tracker.changedIDs)].length, 3);
 
     _("Let's stop tracking again.");
     tracker.clearChangedIDs();
     Svc.Obs.notify("weave:engine:stop-tracking");
     createBmk();
     do_check_eq([id for (id in tracker.changedIDs)].length, 0);
 
     _("Notifying twice won't do any harm.");
new file mode 100644
--- /dev/null
+++ b/services/sync/tests/unit/test_history_engine.js
@@ -0,0 +1,143 @@
+Cu.import("resource://services-sync/base_records/wbo.js");
+Cu.import("resource://services-sync/base_records/crypto.js");
+Cu.import("resource://services-sync/engines/history.js");
+Cu.import("resource://services-sync/type_records/history.js");
+Cu.import("resource://services-sync/constants.js");
+Cu.import("resource://services-sync/engines.js");
+Cu.import("resource://services-sync/identity.js");
+Cu.import("resource://services-sync/util.js");
+
+function makeSteamEngine() {
+  return new SteamEngine();
+}
+
+var syncTesting = new SyncTestingInfrastructure(makeSteamEngine);
+
+function test_processIncoming_mobile_history_batched() {
+  _("SyncEngine._processIncoming works on history engine.");
+
+  let FAKE_DOWNLOAD_LIMIT = 100;
+  
+  Svc.Prefs.set("clusterURL", "http://localhost:8080/");
+  Svc.Prefs.set("username", "foo");
+  Svc.Prefs.set("client.type", "mobile");
+  Svc.History.removeAllPages();
+  Engines.register(HistoryEngine);
+
+  // A collection that logs each GET
+  let collection = new ServerCollection();
+  collection.get_log = [];
+  collection._get = collection.get;
+  collection.get = function (options) {
+    this.get_log.push(options);
+    return this._get(options);
+  };
+
+  // Let's create some 234 server side history records. They're all at least
+  // 10 minutes old.
+  let visitType = Ci.nsINavHistoryService.TRANSITION_LINK;
+  for (var i = 0; i < 234; i++) {
+    let id = 'record-no-' + i;
+    let modified = Date.now()/1000 - 60*(i+10);
+    let payload = encryptPayload({
+      id: id,
+      histUri: "http://foo/bar?" + id,
+        title: id,
+        sortindex: i,
+        visits: [{date: (modified - 5), type: visitType}],
+        deleted: false});
+    
+    let wbo = new ServerWBO(id, payload);
+    wbo.modified = modified;
+    collection.wbos[id] = wbo;
+  }
+  
+  let server = sync_httpd_setup({
+      "/1.0/foo/storage/history": collection.handler()
+  });
+  do_test_pending();
+
+  let engine = new HistoryEngine("history");
+  let meta_global = Records.set(engine.metaURL, new WBORecord(engine.metaURL));
+  meta_global.payload.engines = {history: {version: engine.version,
+                                           syncID: engine.syncID}};
+
+  try {
+
+    _("On a mobile client, we get new records from the server in batches of 50.");
+    engine._syncStartup();
+    
+    // Fake a lower limit.
+    engine.downloadLimit = FAKE_DOWNLOAD_LIMIT;
+    _("Last modified: " + engine.lastModified);
+    _("Processing...");
+    engine._processIncoming();
+    
+    _("Last modified: " + engine.lastModified);
+    engine._syncFinish();
+    
+    // Back to the normal limit.
+    _("Running again. Should fetch none, because of lastModified");
+    engine.downloadLimit = MAX_HISTORY_DOWNLOAD;
+    _("Processing...");
+    engine._processIncoming();
+    
+    _("Last modified: " + engine.lastModified);
+    _("Running again. Expecting to pull everything");
+    
+    engine.lastModified = undefined;
+    engine.lastSync     = 0;
+    _("Processing...");
+    engine._processIncoming();
+    
+    _("Last modified: " + engine.lastModified);
+
+    // Verify that the right number of GET requests with the right
+    // kind of parameters were made.
+    do_check_eq(collection.get_log.length,
+        // First try:
+        1 +    // First 50...
+        1 +    // 1 GUID fetch...
+               // 1 fetch...
+        Math.ceil((FAKE_DOWNLOAD_LIMIT - 50) / MOBILE_BATCH_SIZE) +
+        // Second try: none
+        // Third try:
+        1 +    // First 50...
+        1 +    // 1 GUID fetch...
+               // 4 fetch...
+        Math.ceil((234 - 50) / MOBILE_BATCH_SIZE));
+    
+    // Check the structure of each HTTP request.
+    do_check_eq(collection.get_log[0].full, 1);
+    do_check_eq(collection.get_log[0].limit, MOBILE_BATCH_SIZE);
+    do_check_eq(collection.get_log[1].full, undefined);
+    do_check_eq(collection.get_log[1].sort, "index");
+    do_check_eq(collection.get_log[1].limit, FAKE_DOWNLOAD_LIMIT);
+    do_check_eq(collection.get_log[2].full, 1);
+    do_check_eq(collection.get_log[3].full, 1);
+    do_check_eq(collection.get_log[3].limit, MOBILE_BATCH_SIZE);
+    do_check_eq(collection.get_log[4].full, undefined);
+    do_check_eq(collection.get_log[4].sort, "index");
+    do_check_eq(collection.get_log[4].limit, MAX_HISTORY_DOWNLOAD);
+    for (let i = 0; i <= Math.floor((234 - 50) / MOBILE_BATCH_SIZE); i++) {
+      let j = i + 5;
+      do_check_eq(collection.get_log[j].full, 1);
+      do_check_eq(collection.get_log[j].limit, undefined);
+      if (i < Math.floor((234 - 50) / MOBILE_BATCH_SIZE))
+        do_check_eq(collection.get_log[j].ids.length, MOBILE_BATCH_SIZE);
+      else
+        do_check_eq(collection.get_log[j].ids.length, 234 % MOBILE_BATCH_SIZE);
+    }
+
+  } finally {
+    server.stop(do_test_finished);
+    Svc.Prefs.resetBranch("");
+    Records.clearCache();
+  }
+}
+
+function run_test() {
+  CollectionKeys.generateNewKeys();
+
+  test_processIncoming_mobile_history_batched();
+}
--- a/services/sync/tests/unit/test_history_tracker.js
+++ b/services/sync/tests/unit/test_history_tracker.js
@@ -13,17 +13,17 @@ function run_test() {
   let _counter = 0;
   function addVisit() {
     Svc.History.addVisit(Utils.makeURI("http://getfirefox.com/" + _counter),
                          Date.now() * 1000, null, 1, false, 0);
     _counter += 1;
   }
 
   try {
-    _("Create bookmark. Won't show because we haven't started tracking yet");
+    _("Create history item. Won't show because we haven't started tracking yet");
     addVisit();
     do_check_eq([id for (id in tracker.changedIDs)].length, 0);
 
     _("Tell the tracker to start tracking changes.");
     Svc.Obs.notify("weave:engine:start-tracking");
     addVisit();
     do_check_eq([id for (id in tracker.changedIDs)].length, 1);
 
--- a/services/sync/tests/unit/test_keys.js
+++ b/services/sync/tests/unit/test_keys.js
@@ -1,14 +1,38 @@
 var btoa;
 
 Cu.import("resource://services-sync/base_records/crypto.js");
 Cu.import("resource://services-sync/constants.js");
 btoa = Cu.import("resource://services-sync/util.js").btoa;
 
+function test_time_keyFromString(iterations) {
+  let k;
+  let o;
+  let b = new BulkKeyBundle();
+  let d = Utils.decodeKeyBase32("ababcdefabcdefabcdefabcdef");
+  b.generateRandom();
+  
+  _("Running " + iterations + " iterations of hmacKeyObject + sha256HMACBytes.");
+  for (let i = 0; i < iterations; ++i) {
+    let k = b.hmacKeyObject;
+    o = Utils.sha256HMACBytes(d, k);
+  }
+  do_check_true(!!o);
+  _("Done.");
+}
+
+function test_repeated_hmac() {
+  let testKey = "ababcdefabcdefabcdefabcdef";
+  let k = Utils.makeHMACKey("foo");
+  let one = Utils.sha256HMACBytes(Utils.decodeKeyBase32(testKey), k);
+  let two = Utils.sha256HMACBytes(Utils.decodeKeyBase32(testKey), k);
+  do_check_eq(one, two);
+}
+
 function test_keymanager() {
   let testKey = "ababcdefabcdefabcdefabcdef";
   
   let username = "john@example.com";
   
   // Decode the key here to mirror what generateEntry will do,
   // but pass it encoded into the KeyBundle call below.
   
@@ -151,9 +175,13 @@ function test_key_persistence() {
   do_check_true(!!id.hmacKey);
   do_check_true(!!id.encryptionKey);
 }
 
 function run_test() {
   test_keymanager();
   test_collections_manager();
   test_key_persistence();
+  test_repeated_hmac();
+  
+  // Only do 1,000 to avoid a 5-second pause in test runs.
+  test_time_keyFromString(1000);
 }
--- a/services/sync/tests/unit/test_syncengine_sync.js
+++ b/services/sync/tests/unit/test_syncengine_sync.js
@@ -97,40 +97,16 @@ SteamEngine.prototype = {
 
 
 function makeSteamEngine() {
   return new SteamEngine();
 }
 
 var syncTesting = new SyncTestingInfrastructure(makeSteamEngine);
 
-
-/*
- * Test setup helpers
- */
-
-function sync_httpd_setup(handlers) {
-  handlers["/1.0/foo/storage/meta/global"]
-      = (new ServerWBO('global', {})).handler();
-  return httpd_setup(handlers);
-}
-
-// Turn WBO cleartext into "encrypted" payload as it goes over the wire
-function encryptPayload(cleartext) {
-  if (typeof cleartext == "object") {
-    cleartext = JSON.stringify(cleartext);
-  }
-
-  return {encryption: "../crypto/steam",
-          ciphertext: cleartext, // ciphertext == cleartext with fake crypto
-          IV: "irrelevant",
-          hmac: Utils.sha256HMAC(cleartext, null)};
-}
-
-
 /*
  * Tests
  * 
  * SyncEngine._sync() is divided into four rather independent steps:
  *
  * - _syncStartup()
  * - _processIncoming()
  * - _uploadOutgoing()
@@ -517,17 +493,17 @@ function test_processIncoming_mobile_bat
 
   let engine = makeSteamEngine();
   let meta_global = Records.set(engine.metaURL, new WBORecord(engine.metaURL));
   meta_global.payload.engines = {steam: {version: engine.version,
                                          syncID: engine.syncID}};
 
   try {
 
-    // On a mobile client, we get new records from the server in batches of 50.
+    _("On a mobile client, we get new records from the server in batches of 50.");
     engine._syncStartup();
     engine._processIncoming();
     do_check_eq([id for (id in engine._store.items)].length, 234);
     do_check_true('record-no-0' in engine._store.items);
     do_check_true('record-no-49' in engine._store.items);
     do_check_true('record-no-50' in engine._store.items);
     do_check_true('record-no-233' in engine._store.items);
 
@@ -551,17 +527,16 @@ function test_processIncoming_mobile_bat
   } finally {
     server.stop(do_test_finished);
     Svc.Prefs.resetBranch("");
     Records.clearCache();
     syncTesting = new SyncTestingInfrastructure(makeSteamEngine);
   }
 }
 
-
 function test_uploadOutgoing_toEmptyServer() {
   _("SyncEngine._uploadOutgoing uploads new records to server");
 
   Svc.Prefs.set("clusterURL", "http://localhost:8080/");
   Svc.Prefs.set("username", "foo");
   let collection = new ServerCollection();
   collection.wbos.flying = new ServerWBO('flying');
   collection.wbos.scotsman = new ServerWBO('scotsman');
@@ -1012,16 +987,18 @@ function test_canDecrypt_true() {
   }
 }
 
 
 function run_test() {
   if (DISABLE_TESTS_BUG_604565)
     return;
 
+  CollectionKeys.generateNewKeys();
+
   test_syncStartup_emptyOrOutdatedGlobalsResetsSync();
   test_syncStartup_serverHasNewerVersion();
   test_syncStartup_syncIDMismatchResetsClient();
   test_processIncoming_emptyServer();
   test_processIncoming_createFromServer();
   test_processIncoming_reconcile();
   test_processIncoming_mobile_batchSize();
   test_uploadOutgoing_toEmptyServer();