638297 - Share buffers between encryption and decryption calls

Status: RESOLVED FIXED

(Firefox :: Sync, defect)

Description

[Richard Newman [:rnewman]]

Every hit on WeaveCrypto.decrypt and .encrypt allocates two new buffers and casts them a few times. That's a lot of allocations.

It would likely be a big memory allocation win to use a limited set of buffers and grow them as necessary, reusing them on each call.

Comment 1

[Philipp von Weitershausen [:philikon]]

Allocating two buffers (input and output) once and reusing them on all crypt calls would save us 4*3*N allocations, thus requesting blocking Fennec.

Comment 2

[Philipp von Weitershausen [:philikon]]

Apart from the four 3*N and 1*N object allocations for the buffers, these are the remaining allocations that are proportional to N:

1*N WeaveCrypto.js:433  ivParam = this.nss.PK11_ParamFromIV(...
1*N WeaveCrypto.js:438  ctx = this.nss.PK11_CreateContextBySymKey(...
1*N WeaveCrypto.js:443  tmpOutputSize
1*N WeaveCrypto.js:445  tmpOutputSize.address()?
1*N WeaveCrypto.js:455  tmpOutputSize2
1*N WeaveCrypto.js:456  tmpOutputSize2.address()?

I'm pretty sure we only have to allocate those integers and their pointers once. Depending on how PK11_ParamFromIV and PK11_CreateContextBySymKey work, we might even be able to only create those once (together with the IV and the sym key, respectively).

For completeness' sake, here are the buffer allocation hits:

3*N WeaveCrypto.js:404  let input = new ctypes.ArrayType(...
3*N WeaveCrypto.js:405  let ints  = ctypes.cast(input, ...
3*N WeaveCrypto.js:408  let outputBuffer = new ctypes.ArrayType(...
3*N WeaveCrypto.js:460  let newOutput = ctypes.cast(output, ...
1*N WeaveCrypto.js:449  output.adressOfElement(actualOutputSize)

Comment 3

[Richard Newman [:rnewman]]

The buffer management is getting pretty tangly, so I'm going to resume later tonight and in the morning.

Comment 4

[Richard Newman [:rnewman]]

Attachment: Part 0: reuse ints. v1

This saves two ctype int allocations per decrypt or encrypt call.

Comment 5

[Richard Newman [:rnewman]]

Attachment: Part 1: reuse buffers. v1

This patch:

* Initializes a pair of shared buffers, one for input and one for output.
* Maintains an int-array pointer where useful, to avoid a cast.
* Adds explicit buffer lengths to commonCrypt.

* Avoids one buffer allocation and one cast in encrypt.
* Avoids two buffer allocations and one cast in decrypt.

We don't replace the other buffer allocation in encrypt, because the current method works better with non-ASCII input, and a correct fix for this would be significant additional complexity.

We also don't replace the cast in the response of commonCrypt, because it is helpful in carrying the actual output size with the response.

Tests pass; running CrossWeave now.

Comment 6

[Philipp von Weitershausen [:philikon]]

Comment on attachment 516642 [details] [diff] [review]
Part 0: reuse ints. v1

>+    // Avoid allocating new temporary ints on every run of _commonCrypt.
>+    _commonCryptSignedOutputSize: new ctypes.int(),
>+    _commonCryptUnsignedOutputSize: new ctypes.unsigned_int(),

I don't think we want to allocate these on import time and share them between instances of WeaveCrypto. I suggest creating them as null here and initializing them in one the of the init* methods, or upon first use. We also want to store the pointer as that seems to be a separate ctypes object (see comment 2).

r=me with that

Comment 7

[Philipp von Weitershausen [:philikon]]

Comment on attachment 516645 [details] [diff] [review]
Part 1: reuse buffers. v1

>             this.initNSS();
>             this.initAlgorithmSettings();   // Depends on NSS.
>             this.initIVSECItem();
>+            this.initBuffers(1024);

Make the 1024 a const please.

r=me with that.

Comment 8

[Richard Newman [:rnewman]]

Thanks Philipp. Pushed:

http://hg.mozilla.org/services/fx-sync/rev/2f6df1b6f135
http://hg.mozilla.org/services/fx-sync/rev/c20309b83792

Let's see what CrossWeave has to say about this.

Comment 9

[Richard Newman [:rnewman]]

Attachment: Part 2: reuse buffer in generateRandomBytes. v1

Surprise part 2!

Comment 10

[Richard Newman [:rnewman]]

(In reply to comment #9)
> Surprise part 2!

This avoids the allocation of a 16-byte buffer, ctype reference, and address on every IV generation... which is once per uploaded encrypted item. Won't affect download/decrypt, but avoids some churn on upload syncs.

CrossWeave passes, btw.

Comment 11

[Richard Newman [:rnewman]]

Attachment: Part 2: reuse buffer in generateRandomBytes. v2

This reorders some tests to verify that changing buffer size downwards still works.

Comment 12

[Richard Newman [:rnewman]]

As if by magic:

http://hg.mozilla.org/services/fx-sync/rev/aa442a9f34a1

Comment 13

[Richard Newman [:rnewman]]

Sharing buffers and populating them by iteration is slow -- 20 times slower than allocating a new buffer. That's just JS.

We noticed that a fresh big sync allocated 700MB less on desktop... but extended sync time, and that reflects in Philipp's graphs.

Unless we're able to fill a buffer from a JS string using a ctypes call, we should back out most of Part 1.

Probably a straight back-out is infeasible, so I'll prepare an amendment patch.

Comment 14

[Richard Newman [:rnewman]]

Attachment: Don't zero-pad. v1

We no longer do anything that requires zero-padding; we use explicit buffer lengths everywhere. This small patch removes it, which will save some needless array traversals.

Tests pass; haven't run crossweave yet.

Comment 15

[Richard Newman [:rnewman]]

(In reply to comment #13)

> We noticed that a fresh big sync allocated 700MB less on desktop... but
> extended sync time, and that reflects in Philipp's graphs.
> 
> Unless we're able to fill a buffer from a JS string using a ctypes call, we
> should back out most of Part 1.
> 
> Probably a straight back-out is infeasible, so I'll prepare an amendment patch.

Subsequent re-measurements revealed that total time is not significantly impacted, but the memory reduction is real. As such a backout is unnecessary.

However, we should consider implementing some of the missing ctypes operations -- readBytes (readString with no UTF-8 decoding) and writeString -- and use these to push work down into C++.

Comment 16

[Philipp von Weitershausen [:philikon]]

Comment on attachment 517056 [details] [diff] [review]
Don't zero-pad. v1

>   // Fill it too short.
>   cryptoSvc.byteCompressInts("MMM", intData, 8);
>-  for (let i = 0; i < 8; ++i)
>+  for (let i = 0; i < 3; ++i)
>     do_check_eq(intData[i], [77, 77, 77, 0, 0, 0, 0, 0, 0][i]);

This test is now a bit misleading... I would suggest having either only a 3-element array here OR go through the whole buffer, demonstrating that only elements up to 'len' are rewritten.

r=me otherwise.

Comment 17

[Richard Newman [:rnewman]]

Attachment: Don't zero-pad. v2

This addresses the prior review comment and also adds logic to handle short IVs in a consistent way (by null-padding them up to blockSize). To my knowledge, Sync never uses an IV shorter than (for AES) 16 bytes, but at least the code is now deterministic in that case!

This should be the final patch for this bug, unless I'm able to enhance js-ctypes within the time available today -- if that works, I can get a 20-40x speedup on byteCompressInts, giving us better than the best of both worlds (less garbage and faster runtime).

It's best to operate under the assumption that it won't be ready and reviewed in time, given that we're blocking Fennec, so please behave accordingly.

Comment 18

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

(In reply to comment #17)
> This addresses the prior review comment and
> also adds logic to handle short IVs in a
> consistent way (by null-padding them up to
> blockSize). To my knowledge, Sync never uses
> an IV shorter than (for AES) 16 bytes, but
> at least the code is now deterministic in
> that case!

Do not pad the IV with zeros. Sync uses randomly generated IVs, and we are relying on the fact that we will generate all 16 byes randomly. The IV has to be 16 bytes. If it isn't, that is an extremely serious error. 

Example: let's say the IV is one byte; then there are only 255 possible (zero-padded) IVs which pretty much defeats the purposes of an IV in the first place.

Comment 19

[Philipp von Weitershausen [:philikon]]

(In reply to comment #18)
> Do not pad the IV with zeros. Sync uses randomly generated IVs, and we are
> relying on the fact that we will generate all 16 byes randomly. The IV has to
> be 16 bytes. If it isn't, that is an extremely serious error. 

Thanks for pre-empting my review comment :). I agree, we should fail hard if the IV isn't the blocksize.

Comment 20

[Richard Newman [:rnewman]]

(In reply to comment #18)
> Do not pad the IV with zeros.

OK.

I don't want to do nothing in the case of a short IV, which is what we were doing, so throw instead?

(Thanks for the drive-by review!)

Comment 21

[Philipp von Weitershausen [:philikon]]

(In reply to comment #20)
> I don't want to do nothing in the case of a short IV, which is what we were
> doing, so throw instead?

Yes please.

Comment 22

[Richard Newman [:rnewman]]

Attachment: Don't zero-pad. v3

Throw instead.

Comment 23

[Richard Newman [:rnewman]]

Thar she blows:

http://hg.mozilla.org/services/fx-sync/rev/90aa2db69b98

Philipp, please merge up to s-c when you get a chance.

Comment 24

[Richard Newman [:rnewman]]

Filed follow-up:

  Bug 639589

Comment 25

[Philipp von Weitershausen [:philikon]]

Merged part 3 to services-central:
http://hg.mozilla.org/services/services-central/rev/cf2463e452ba

Here are the services-central URLs for the previous parts:

Part 0: http://hg.mozilla.org/services/services-central/rev/2ef1943bd05b
Part 1: http://hg.mozilla.org/services/services-central/rev/66df10cc265c
Part 2: http://hg.mozilla.org/services/services-central/rev/a5360f16ee60

Comment 26

[Philipp von Weitershausen [:philikon]]

Landed:

Part 0: http://hg.mozilla.org/mozilla-central/rev/2ef1943bd05b
Part 1: http://hg.mozilla.org/mozilla-central/rev/66df10cc265c
Part 2: http://hg.mozilla.org/mozilla-central/rev/a5360f16ee60
Part 3: http://hg.mozilla.org/mozilla-central/rev/cf2463e452ba