Bug 610914: performance improvements for WeaveCrypto.
☠☠ backed out by 84fe21efcb57 ☠ ☠
authorRichard Newman <rnewman@mozilla.com>
Mon, 06 Dec 2010 11:52:30 -0800
changeset 58757 faa6ce5a0a20cd74597e297220cff7654a65ebdb
parent 58756 3ee27049cd1abcf6f69ce350f8529614defbe091
child 58758 183be003b3126d6e355e4042178c0fb70e85d57d
push id1
push usershaver@mozilla.com
push dateTue, 04 Jan 2011 17:58:04 +0000
bugs610914
Bug 610914: performance improvements for WeaveCrypto.
services/crypto/modules/WeaveCrypto.js
services/crypto/tests/unit/test_crypto_crypt.js
services/sync/modules/base_records/crypto.js
services/sync/tests/unit/test_keys.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/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);
 }