Lazily instantiate two variables in mp_exptmod_safe_i()

RESOLVED FIXED in 3.19

Status

NSS
Libraries
P1
normal
RESOLVED FIXED
4 years ago
3 years ago

People

(Reporter: njn, Assigned: njn)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments, 3 obsolete attachments)

(Assignee)

Description

4 years ago
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.
(Assignee)

Updated

4 years ago
Summary: Reduce NSS's heap allocation rate → Lazily instantiate two variables in mp_exptmod_safe_i()
(Assignee)

Comment 1

4 years ago
Created attachment 8520757 [details] [diff] [review]
(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.
Attachment #8520757 - Flags: review?(rrelyea)
(Assignee)

Comment 2

4 years ago
Created attachment 8520759 [details] [diff] [review]
(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.
Attachment #8520759 - Flags: review?(rrelyea)
(Assignee)

Comment 3

4 years ago
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

4 years ago
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

4 years ago
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.
(Assignee)

Comment 6

4 years ago
Created attachment 8522051 [details] [diff] [review]
(part 1) - In mp_exptmod_safe_i(), instantiate |powersArray| lazily
Attachment #8522051 - Flags: review?(rrelyea)
(Assignee)

Updated

4 years ago
Attachment #8520757 - Attachment is obsolete: true
Attachment #8520757 - Flags: review?(rrelyea)
(Assignee)

Comment 7

4 years ago
Created attachment 8522052 [details] [diff] [review]
(part 2) - In mp_exptmod_safe_i(), instantiate |tmp| lazily
Attachment #8522052 - Flags: review?(rrelyea)
(Assignee)

Updated

4 years ago
Attachment #8520759 - Attachment is obsolete: true
Attachment #8520759 - Flags: review?(rrelyea)
(Assignee)

Comment 8

4 years ago
Yuriy: thank you for the suggestions. The new versions are much simpler.
(Assignee)

Comment 9

4 years ago
rrelyea: 1 month review ping.
(Assignee)

Comment 10

3 years ago
rrelyea: 2.25 month review ping.

Comment 11

3 years ago
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

3 years ago
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?
(Assignee)

Comment 13

3 years ago
Created attachment 8555024 [details] [diff] [review]
(part 1) - In mp_exptmod_safe_i(), instantiate |powersArray| lazily

This version has an extra comment.
Attachment #8555024 - Flags: review?(kaie)
(Assignee)

Updated

3 years ago
Attachment #8522051 - Attachment is obsolete: true
Attachment #8522051 - Flags: review?(rrelyea)
(Assignee)

Comment 14

3 years ago
(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

3 years ago
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.
Attachment #8522052 - Flags: review?(rrelyea) → review+

Comment 16

3 years ago
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.
Attachment #8555024 - Flags: review?(kaie) → review+
(Assignee)

Comment 17

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

Comment 18

3 years ago
(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
Status: ASSIGNED → RESOLVED
Last Resolved: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → 3.18.1

Updated

3 years ago
Target Milestone: 3.18.1 → 3.19

Updated

3 years ago
Priority: -- → P1
You need to log in before you can comment on or make changes to this bug.