RFR: 8262316: Reducing locks in RSA Blinding

classic Classic list List threaded Threaded
18 messages Options
Reply | Threaded
Open this post in threaded view
|

RFR: 8262316: Reducing locks in RSA Blinding

Anthony Scarpino-2
Hi,

I need a review of the locking change to the RSA blinding code. The problem was reported that multithreaded performance suffered because there was one global lock on the many blindings operation.  The change reduces locking by using a ConcurrentLinkedQueue to store the different BlindingParameters that other threads maybe using.  The queue size is limited to prevent sudden surges in stored BlindingParameters and a WeakHashMap is still used so the objects can be freed when no longer used.  Performance doubles under high load.

thanks

Tony

-------------

Commit messages:
 - change putIfAbsent usage to minimize competing threads
 - add loop to check the queue on reset
 - add comment, cleanup
 - minor update
 - queue idea

Changes: https://git.openjdk.java.net/jdk/pull/3296/files
 Webrev: https://webrevs.openjdk.java.net/?repo=jdk&pr=3296&range=00
  Issue: https://bugs.openjdk.java.net/browse/JDK-8262316
  Stats: 82 lines in 1 file changed: 39 ins; 16 del; 27 mod
  Patch: https://git.openjdk.java.net/jdk/pull/3296.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/3296/head:pull/3296

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding

Jamil Nimeh-2
On Wed, 31 Mar 2021 21:47:24 GMT, Anthony Scarpino <[hidden email]> wrote:

> Hi,
>
> I need a review of the locking change to the RSA blinding code. The problem was reported that multithreaded performance suffered because there was one global lock on the many blindings operation.  The change reduces locking by using a ConcurrentLinkedQueue to store the different BlindingParameters that other threads maybe using.  The queue size is limited to prevent sudden surges in stored BlindingParameters and a WeakHashMap is still used so the objects can be freed when no longer used.  Performance doubles under high load.
>
> thanks
>
> Tony

src/java.base/share/classes/sun/security/rsa/RSACore.java line 414:

> 412:                 if (!u.equals(BigInteger.ZERO) &&
> 413:                     !v.equals(BigInteger.ZERO)) {
> 414:

Is it ever possible that u could be equal to BigInteger.ZERO?  The only place I see a new BlindingRandomPair created is within the scope of the BlindingParameters object, and it has a guard in its constructor that resets u to BigInteger.ONE if u is zero.  Or is this check to guard against the reset of u/v down around line 416-419 (recalculated when reusable)?

-------------

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding

djelinski
In reply to this post by Anthony Scarpino-2
On Wed, 31 Mar 2021 21:47:24 GMT, Anthony Scarpino <[hidden email]> wrote:

> Hi,
>
> I need a review of the locking change to the RSA blinding code. The problem was reported that multithreaded performance suffered because there was one global lock on the many blindings operation.  The change reduces locking by using a ConcurrentLinkedQueue to store the different BlindingParameters that other threads maybe using.  The queue size is limited to prevent sudden surges in stored BlindingParameters and a WeakHashMap is still used so the objects can be freed when no longer used.  Performance doubles under high load.
>
> thanks
>
> Tony

src/java.base/share/classes/sun/security/rsa/RSACore.java line 66:

> 64:     // like performance testing.
> 65:     private static final Map<BigInteger, ConcurrentLinkedQueue<BlindingParameters>>
> 66:                 blindingCache = new WeakHashMap<>();

I'd use a synchronizedMap here now

-------------

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding

Anthony Scarpino-2
In reply to this post by Jamil Nimeh-2
On Thu, 1 Apr 2021 15:51:55 GMT, Jamil Nimeh <[hidden email]> wrote:

>> Hi,
>>
>> I need a review of the locking change to the RSA blinding code. The problem was reported that multithreaded performance suffered because there was one global lock on the many blindings operation.  The change reduces locking by using a ConcurrentLinkedQueue to store the different BlindingParameters that other threads maybe using.  The queue size is limited to prevent sudden surges in stored BlindingParameters and a WeakHashMap is still used so the objects can be freed when no longer used.  Performance doubles under high load.
>>
>> thanks
>>
>> Tony
>
> src/java.base/share/classes/sun/security/rsa/RSACore.java line 414:
>
>> 412:                 if (!u.equals(BigInteger.ZERO) &&
>> 413:                     !v.equals(BigInteger.ZERO)) {
>> 414:
>
> Is it ever possible that u could be equal to BigInteger.ZERO?  The only place I see a new BlindingRandomPair created is within the scope of the BlindingParameters object, and it has a guard in its constructor that resets u to BigInteger.ONE if u is zero.  Or is this check to guard against the reset of u/v down around line 416-419 (recalculated when reusable)?

The both values are never zero now as the old code used zero to define the parameters needed to be reset.  I don't think this zero check is necessary.. let me try something else that fits with the isReusable() here and the one below when putting it into the queue

-------------

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding

Anthony Scarpino-2
In reply to this post by djelinski
On Fri, 2 Apr 2021 06:36:57 GMT, djelinski <[hidden email]> wrote:

>> Hi,
>>
>> I need a review of the locking change to the RSA blinding code. The problem was reported that multithreaded performance suffered because there was one global lock on the many blindings operation.  The change reduces locking by using a ConcurrentLinkedQueue to store the different BlindingParameters that other threads maybe using.  The queue size is limited to prevent sudden surges in stored BlindingParameters and a WeakHashMap is still used so the objects can be freed when no longer used.  Performance doubles under high load.
>>
>> thanks
>>
>> Tony
>
> src/java.base/share/classes/sun/security/rsa/RSACore.java line 66:
>
>> 64:     // like performance testing.
>> 65:     private static final Map<BigInteger, ConcurrentLinkedQueue<BlindingParameters>>
>> 66:                 blindingCache = new WeakHashMap<>();
>
> I'd use a synchronizedMap here now

Using a synchronizedMap would only let one thread access the hashmap at a time, which is what I'm trying to reduce.  Get ops do not need to be locked and put ops don't either because the values are objects of random data, losing one is not significant to the operation.

-------------

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding [v2]

Anthony Scarpino-2
In reply to this post by Anthony Scarpino-2
> Hi,
>
> I need a review of the locking change to the RSA blinding code. The problem was reported that multithreaded performance suffered because there was one global lock on the many blindings operation.  The change reduces locking by using a ConcurrentLinkedQueue to store the different BlindingParameters that other threads maybe using.  The queue size is limited to prevent sudden surges in stored BlindingParameters and a WeakHashMap is still used so the objects can be freed when no longer used.  Performance doubles under high load.
>
> thanks
>
> Tony

Anthony Scarpino has updated the pull request incrementally with one additional commit since the last revision:

  Better handle the comparing of ONE and ZERO

-------------

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/3296/files
  - new: https://git.openjdk.java.net/jdk/pull/3296/files/3b054789..e948ecac

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=3296&range=01
 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=3296&range=00-01

  Stats: 13 lines in 1 file changed: 1 ins; 1 del; 11 mod
  Patch: https://git.openjdk.java.net/jdk/pull/3296.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/3296/head:pull/3296

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding [v2]

djelinski
In reply to this post by Anthony Scarpino-2
On Fri, 2 Apr 2021 17:45:45 GMT, Anthony Scarpino <[hidden email]> wrote:

>> src/java.base/share/classes/sun/security/rsa/RSACore.java line 66:
>>
>>> 64:     // like performance testing.
>>> 65:     private static final Map<BigInteger, ConcurrentLinkedQueue<BlindingParameters>>
>>> 66:                 blindingCache = new WeakHashMap<>();
>>
>> I'd use a synchronizedMap here now
>
> Using a synchronizedMap would only let one thread access the hashmap at a time, which is what I'm trying to reduce.  Get ops do not need to be locked and put ops don't either because the values are objects of random data, losing one is not significant to the operation.

According to SO, unsynchronized writes to a map can lead to lock up, see here:
https://stackoverflow.com/a/1003237
Or here:
https://mailinator.blogspot.com/2009/06/beautiful-race-condition.html?m=1
What's the performance impact of adding synchronization on the hash map only?

-------------

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding [v2]

Anthony Scarpino-2
On Fri, 2 Apr 2021 20:52:42 GMT, djelinski <[hidden email]> wrote:

>> Using a synchronizedMap would only let one thread access the hashmap at a time, which is what I'm trying to reduce.  Get ops do not need to be locked and put ops don't either because the values are objects of random data, losing one is not significant to the operation.
>
> According to SO, unsynchronized writes to a map can lead to lock up, see here:
> https://stackoverflow.com/a/1003237
> Or here:
> https://mailinator.blogspot.com/2009/06/beautiful-race-condition.html?m=1
> What's the performance impact of adding synchronization on the hash map only?

Ok, thanks for pointing that out, I didn't realize that limitation.  However using synchronizedMap is overkill as it locks every operation.  As I read it, only structural changes like adding and removing keys from the map causes problems.  Getting a value from the map does not.  Therefore I would only need to synchronize the putIfAbsent() at 449, which is pretty minor.  The expunging of the map is already synchronized in WeakHashMap.

The original code was half the performance of this one.

-------------

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding [v2]

Florent Guillaume-2
On Fri, 2 Apr 2021 23:12:21 GMT, Anthony Scarpino <[hidden email]> wrote:

>> According to SO, unsynchronized writes to a map can lead to lock up, see here:
>> https://stackoverflow.com/a/1003237
>> Or here:
>> https://mailinator.blogspot.com/2009/06/beautiful-race-condition.html?m=1
>> What's the performance impact of adding synchronization on the hash map only?
>
> Ok, thanks for pointing that out, I didn't realize that limitation.  However using synchronizedMap is overkill as it locks every operation.  As I read it, only structural changes like adding and removing keys from the map causes problems.  Getting a value from the map does not.  Therefore I would only need to synchronize the putIfAbsent() at 449, which is pretty minor.  The expunging of the map is already synchronized in WeakHashMap.
>
> The original code was half the performance of this one.

If you synchronize `putIfAbsent` but not `get` you'll still get the possible infinite loop described in the SO post.

-------------

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding [v2]

djelinski
On Sat, 3 Apr 2021 01:06:50 GMT, Florent Guillaume <[hidden email]> wrote:

>> Ok, thanks for pointing that out, I didn't realize that limitation.  However using synchronizedMap is overkill as it locks every operation.  As I read it, only structural changes like adding and removing keys from the map causes problems.  Getting a value from the map does not.  Therefore I would only need to synchronize the putIfAbsent() at 449, which is pretty minor.  The expunging of the map is already synchronized in WeakHashMap.
>>
>> The original code was half the performance of this one.
>
> If you synchronize `putIfAbsent` but not `get` you'll still get the possible infinite loop described in the SO post.

Expunging entries is synchronized over an internal data structure, so if you synchronize puts only, nothing prevents expunge (called from get) from running in parallel with put.
The original code performed big integer exponentiation inside a synchronized block, your code doesn't. I expect substantial performance gains even with synchronization around hash map access, this is why I asked about performance.

-------------

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding [v2]

Anthony Scarpino-2
On Sat, 3 Apr 2021 05:40:11 GMT, djelinski <[hidden email]> wrote:

>> If you synchronize `putIfAbsent` but not `get` you'll still get the possible infinite loop described in the SO post.
>
> Expunging entries is synchronized over an internal data structure, so if you synchronize puts only, nothing prevents expunge (called from get) from running in parallel with put.
> The original code performed big integer exponentiation inside a synchronized block, your code doesn't. I expect substantial performance gains even with synchronization around hash map access, this is why I asked about performance.

I finally see that get() is affected by the locking.  Expunge seems to not lock the able which could cause multiple threads get ops to corrupt the map.  I'll put a ReentrantLock around the put & get.  I prefer to not use synchronized() blocks as ReentrantLock maybe better after Project Loom

Sure, the performance was largely affected by the math ops in the old code.  I wanted to eliminate as much of the performance decelerators as possible

-------------

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding [v3]

Anthony Scarpino-2
In reply to this post by Anthony Scarpino-2
> Hi,
>
> I need a review of the locking change to the RSA blinding code. The problem was reported that multithreaded performance suffered because there was one global lock on the many blindings operation.  The change reduces locking by using a ConcurrentLinkedQueue to store the different BlindingParameters that other threads maybe using.  The queue size is limited to prevent sudden surges in stored BlindingParameters and a WeakHashMap is still used so the objects can be freed when no longer used.  Performance doubles under high load.
>
> thanks
>
> Tony

Anthony Scarpino has updated the pull request incrementally with one additional commit since the last revision:

  Use ReentrantLock for put and get

-------------

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/3296/files
  - new: https://git.openjdk.java.net/jdk/pull/3296/files/e948ecac..dda3ed69

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=3296&range=02
 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=3296&range=01-02

  Stats: 21 lines in 1 file changed: 9 ins; 0 del; 12 mod
  Patch: https://git.openjdk.java.net/jdk/pull/3296.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/3296/head:pull/3296

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding [v3]

djelinski
On Tue, 6 Apr 2021 04:26:58 GMT, Anthony Scarpino <[hidden email]> wrote:

>> Hi,
>>
>> I need a review of the locking change to the RSA blinding code. The problem was reported that multithreaded performance suffered because there was one global lock on the many blindings operation.  The change reduces locking by using a ConcurrentLinkedQueue to store the different BlindingParameters that other threads maybe using.  The queue size is limited to prevent sudden surges in stored BlindingParameters and a WeakHashMap is still used so the objects can be freed when no longer used.  Performance doubles under high load.
>>
>> thanks
>>
>> Tony
>
> Anthony Scarpino has updated the pull request incrementally with one additional commit since the last revision:
>
>   Use ReentrantLock for put and get

src/java.base/share/classes/sun/security/rsa/RSACore.java line 443:

> 441:         lock.lock();
> 442:         try {
> 443:             queue = blindingCache.get(n);

Suggestion:

            queue = blindingCache.computeIfAbsent(n, ignored -> new ConcurrentLinkedQueue<>());

-------------

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding [v4]

Anthony Scarpino-2
In reply to this post by Anthony Scarpino-2
> Hi,
>
> I need a review of the locking change to the RSA blinding code. The problem was reported that multithreaded performance suffered because there was one global lock on the many blindings operation.  The change reduces locking by using a ConcurrentLinkedQueue to store the different BlindingParameters that other threads maybe using.  The queue size is limited to prevent sudden surges in stored BlindingParameters and a WeakHashMap is still used so the objects can be freed when no longer used.  Performance doubles under high load.
>
> thanks
>
> Tony

Anthony Scarpino has updated the pull request incrementally with one additional commit since the last revision:

  use computeIfAbsent instead

-------------

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/3296/files
  - new: https://git.openjdk.java.net/jdk/pull/3296/files/dda3ed69..f8c7baf7

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=3296&range=03
 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=3296&range=02-03

  Stats: 19 lines in 1 file changed: 3 ins; 15 del; 1 mod
  Patch: https://git.openjdk.java.net/jdk/pull/3296.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/3296/head:pull/3296

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding [v3]

Anthony Scarpino-2
In reply to this post by djelinski
On Tue, 6 Apr 2021 07:29:00 GMT, djelinski <[hidden email]> wrote:

>> Anthony Scarpino has updated the pull request incrementally with one additional commit since the last revision:
>>
>>   Use ReentrantLock for put and get
>
> src/java.base/share/classes/sun/security/rsa/RSACore.java line 443:
>
>> 441:         lock.lock();
>> 442:         try {
>> 443:             queue = blindingCache.get(n);
>
> Suggestion:
>
>             queue = blindingCache.computeIfAbsent(n, ignored -> new ConcurrentLinkedQueue<>());

Yeah, that makes sense after all the changes

-------------

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding [v4]

djelinski
In reply to this post by Anthony Scarpino-2
On Tue, 6 Apr 2021 19:43:50 GMT, Anthony Scarpino <[hidden email]> wrote:

>> Hi,
>>
>> I need a review of the locking change to the RSA blinding code. The problem was reported that multithreaded performance suffered because there was one global lock on the many blindings operation.  The change reduces locking by using a ConcurrentLinkedQueue to store the different BlindingParameters that other threads maybe using.  The queue size is limited to prevent sudden surges in stored BlindingParameters and a WeakHashMap is still used so the objects can be freed when no longer used.  Performance doubles under high load.
>>
>> thanks
>>
>> Tony
>
> Anthony Scarpino has updated the pull request incrementally with one additional commit since the last revision:
>
>   use computeIfAbsent instead

+1 (non-binding)

-------------

Marked as reviewed by [hidden email] (no known OpenJDK username).

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Re: RFR: 8262316: Reducing locks in RSA Blinding [v4]

Jamil Nimeh-2
In reply to this post by Anthony Scarpino-2
On Tue, 6 Apr 2021 19:43:50 GMT, Anthony Scarpino <[hidden email]> wrote:

>> Hi,
>>
>> I need a review of the locking change to the RSA blinding code. The problem was reported that multithreaded performance suffered because there was one global lock on the many blindings operation.  The change reduces locking by using a ConcurrentLinkedQueue to store the different BlindingParameters that other threads maybe using.  The queue size is limited to prevent sudden surges in stored BlindingParameters and a WeakHashMap is still used so the objects can be freed when no longer used.  Performance doubles under high load.
>>
>> thanks
>>
>> Tony
>
> Anthony Scarpino has updated the pull request incrementally with one additional commit since the last revision:
>
>   use computeIfAbsent instead

Looks good to me as well.

-------------

Marked as reviewed by jnimeh (Reviewer).

PR: https://git.openjdk.java.net/jdk/pull/3296
Reply | Threaded
Open this post in threaded view
|

Integrated: 8262316: Reducing locks in RSA Blinding

Anthony Scarpino-2
In reply to this post by Anthony Scarpino-2
On Wed, 31 Mar 2021 21:47:24 GMT, Anthony Scarpino <[hidden email]> wrote:

> Hi,
>
> I need a review of the locking change to the RSA blinding code. The problem was reported that multithreaded performance suffered because there was one global lock on the many blindings operation.  The change reduces locking by using a ConcurrentLinkedQueue to store the different BlindingParameters that other threads maybe using.  The queue size is limited to prevent sudden surges in stored BlindingParameters and a WeakHashMap is still used so the objects can be freed when no longer used.  Performance doubles under high load.
>
> thanks
>
> Tony

This pull request has now been integrated.

Changeset: 7a99a987
Author:    Anthony Scarpino <[hidden email]>
URL:       https://git.openjdk.java.net/jdk/commit/7a99a987
Stats:     80 lines in 1 file changed: 37 ins; 17 del; 26 mod

8262316: Reducing locks in RSA Blinding

Reviewed-by: jnimeh

-------------

PR: https://git.openjdk.java.net/jdk/pull/3296