1096741 - Lazily instantiate two variables in mp_exptmod_safe_i()

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Nicholas Nethercote [inactive]]

In Firefox, mp_exptmod_safe_i() is really hot (see bug 1095272 comment 3).

mp_exptmod_safe_i has two variables, |tmp| and |powersArray| that are (a) large, and (b) rarely needed on the paths that Firefox executes. This bug will change things so they are instantiated lazily.

Comment 1

[Nicholas Nethercote [inactive]]

Attachment: (part 1) - In mp_exptmod_safe_i(), instantiate |powersArray| lazily

In my mem50 run, this saves over 100 MiB's worth of unnecessary heap
allocations.

Comment 2

[Nicholas Nethercote [inactive]]

Attachment: (part 2) - In mp_exptmod_safe_i(), instantiate |tmp| lazily

In my mem50 run, this also saves over 100 MiB's worth of unnecessary heap
allocations.

Comment 3

[Nicholas Nethercote [inactive]]

rrelyea: it looks like nelsonb has done most of the mpi/ reviews in the past but he appears to not be active any more. So I'm asking you. Please reassign the review request if there's somebody else more appropriate. Thanks.

Comment 4

[Yuriy M. Kaminskiy]

Comment on attachment 8520759 [details] [diff] [review]
(part 2) - In mp_exptmod_safe_i(), instantiate |tmp| lazily

Review of attachment 8520759 [details] [diff] [review]:
-----------------------------------------------------------------

::: lib/freebl/mpi/mpmontg.c
@@ +998,5 @@
>    pa2 = &accum2;
>  
> +  /* tmp is only used in the following for certain window_bits values */
>  
> +  if (window_bits == 4 || window_bits == 5) {

window_bits == 6 also uses tmp (switch case fall-through)

Comment 5

[Yuriy M. Kaminskiy]

Comment on attachment 8520757 [details] [diff] [review]
(part 1) - In mp_exptmod_safe_i(), instantiate |powersArray| lazily

Review of attachment 8520757 [details] [diff] [review]:
-----------------------------------------------------------------

::: lib/freebl/mpi/mpmontg.c
@@ +956,5 @@
>      if ( i & 1 ) {
>        /* we've filled the array do our 'per array' processing */
>        if (acc_index == (WEAVE_WORD_SIZE-1)) {
>      int acc_index = i & (WEAVE_WORD_SIZE-1); /* i % WEAVE_WORD_SIZE */
> +        ENSURE_POWERS;

Unneeded. This loop won't be executed when num_powers < WEAVE_WORD_SIZE, and powers is already assigned in if (num_powers > 2) above.

@@ +972,5 @@
>         * and target are the same so we need to copy.. After that, the
>         * weave array */
>        if (i > 2* WEAVE_WORD_SIZE) {
>        /* up to 8 we can find 2^i-1 in the accum array, but at 8 we our source
> +        ENSURE_POWERS;

Ditto. I would unmacro ENSURE_POWERS and just add condition (if(num_powers > 2)) around old code; YMMV.

Comment 6

[Nicholas Nethercote [inactive]]

Attachment: (part 1) - In mp_exptmod_safe_i(), instantiate |powersArray| lazily

Comment 7

[Nicholas Nethercote [inactive]]

Attachment: (part 2) - In mp_exptmod_safe_i(), instantiate |tmp| lazily

Comment 8

[Nicholas Nethercote [inactive]]

Yuriy: thank you for the suggestions. The new versions are much simpler.

Comment 9

[Nicholas Nethercote [inactive]]

rrelyea: 1 month review ping.

Comment 10

[Nicholas Nethercote [inactive]]

rrelyea: 2.25 month review ping.

Comment 11

[Kai Engert (:KaiE:)]

Comment on attachment 8522051 [details] [diff] [review]
(part 1) - In mp_exptmod_safe_i(), instantiate |powersArray| lazily

It isn't immediately obvious, why restricting allocation to scenario (num_powers > 2) is safe for the second loop.

It seems your decision depends on the constant WEAVE_WORD_SIZE, which means, the second loop will be executed, only, if (num_powers > 5).

Please add a comment that explains why delayed allocation is safe, you probably want to mention above assumptions, or anything else I might have missed in your thinking.

Comment 12

[Kai Engert (:KaiE:)]

Comment on attachment 8522051 [details] [diff] [review]
(part 1) - In mp_exptmod_safe_i(), instantiate |powersArray| lazily

Is this code used by anything that requires "constant time" execution, in order to make timing attacks difficult?

Comment 13

[Nicholas Nethercote [inactive]]

Attachment: (part 1) - In mp_exptmod_safe_i(), instantiate |powersArray| lazily

This version has an extra comment.

Comment 14

[Nicholas Nethercote [inactive]]

(In reply to Kai Engert (:kaie) from comment #11)
> Comment on attachment 8522051 [details] [diff] [review]
> (part 1) - In mp_exptmod_safe_i(), instantiate |powersArray| lazily
> 
> It isn't immediately obvious, why restricting allocation to scenario
> (num_powers > 2) is safe for the second loop.
> 
> It seems your decision depends on the constant WEAVE_WORD_SIZE, which means,
> the second loop will be executed, only, if (num_powers > 5).
>
> Please add a comment that explains why delayed allocation is safe, you
> probably want to mention above assumptions, or anything else I might have
> missed in your thinking.

There's an existing comment that says "if WEAVE_WORD_SIZE is not 4, this code will have to change" which is why I wrote the patch this way. But I can add an additional comment.

> Is this code used by anything that requires "constant time" execution, in
> order to make timing attacks difficult?

I don't know. I was hoping that NSS reviewers would know about that.

Comment 15

[Robert Relyea]

Comment on attachment 8522052 [details] [diff] [review]
(part 2) - In mp_exptmod_safe_i(), instantiate |tmp| lazily

r+ rrelyea and kaie 
with kaie's comments.

Comment 16

[Robert Relyea]

Comment on attachment 8555024 [details] [diff] [review]
(part 1) - In mp_exptmod_safe_i(), instantiate |powersArray| lazily

r+ rrelyea and kaie
with kaie's comments.

Comment 17

[Nicholas Nethercote [inactive]]

This got r+ 1.5 months ago. Can it land? Thanks.

Comment 18

[Kai Engert (:KaiE:)]

(In reply to Nicholas Nethercote [:njn] (on vacation until April 30th) from comment #17)
> This got r+ 1.5 months ago. Can it land? Thanks.

Thanks for the reminder!

https://hg.mozilla.org/projects/nss/rev/80b6963079d9
https://hg.mozilla.org/projects/nss/rev/62f085e7ecc6