3.0 performance degraded due to locking

Using some internal QUIC tests, we see this timing in 1.1:
$ USE_GQUIC_VERSIONS=1 perf record -F 999 -g ./quic_lib_tests  --gtest_repeat=100  --gtest_filter=*ZeroRttDisabled*
$ perf report

+   31.73%    31.55%  quic_lib_tests  quic_lib_tests       [.] bn_sqr8x_internal
+    9.28%     9.28%  quic_lib_tests  quic_lib_tests       [.] mul4x_internal
+    4.91%     4.91%  quic_lib_tests  quic_lib_tests       [.] sha256_block_data_order_avx

In 3.0 we see this:

$ USE_GQUIC_VERSIONS=1 perf record -F 999 -g ./quic_lib_tests  --gtest_repeat=100  --gtest_filter=*ZeroRttDisabled*
$ perf report

+   11.02%    10.99%  quic_lib_tests  quic_lib_tests       [.] bn_sqr8x_internal
+    8.38%     8.08%  quic_lib_tests  libpthread-2.31.so   [.] __pthread_rwlock_rdlock
+    7.65%     7.51%  quic_lib_tests  libpthread-2.31.so   [.] __pthread_rwlock_unlock
+    4.98%     4.78%  quic_lib_tests  quic_lib_tests       [.] getrn
+    4.14%     4.11%  quic_lib_tests  quic_lib_tests       [.] mul4x_internal
+    3.37%     2.57%  quic_lib_tests  quic_lib_tests       [.] ossl_tolower
     3.30%     3.30%  quic_lib_tests  quic_lib_tests       [.] ossl_lh_strcasehash
+    2.72%     2.13%  quic_lib_tests  quic_lib_tests       [.] OPENSSL_strcasecmp
+    2.29%     2.05%  quic_lib_tests  quic_lib_tests       [.] ossl_lib_ctx_get_data
+    1.93%     1.93%  quic_lib_tests  quic_lib_tests       [.] sha256_block_data_order_avx

This seems to be part of OSSL_DECODER_CTX_new_for_pkey  16% of the time is spent in locking, on a single threaded binary. And 10% is in a string hashtable lookup.
If anyone on the project is going to look at this, I will try to get a small reproducer. But our the time for our QUIC tests is doubling.

Yes, a small reproducer would be great. I'll try to look at it.

Here is a small reproducer in C++, written by an Akamai colleague.
The code is at https://gist.github.com/richsalz/31a98a3095fa36ab6a66082a0c028a6f
Here are the compile commands and timing. This small reproducer is 17 times slower. When used in our QUIC implementation, small transfers average twice as slowly. Microsoft's MSQUIC (their production-quality open source stack on Windows and Azure) avoids use of 3.0 for this exact reason; they use the 1.1 branch of @quictls/openssl
$ g++ -O2 -Wall -std=c++17 test_25519.cc -I openssl1/common/include/ openssl1/common/lib/libcrypto.a -lpthread -ldl -o bin.11
$ g++ -O2 -Wall -std=c++17 test_25519.cc -I openssl3/common/include/ openssl3/common/lib/libcrypto.a -lpthread -ldl -o bin.30

$ time ./bin.11

real	0m3.484s
user	0m3.481s
sys	0m0.002s

$ time ./bin.30

real	0m53.588s
user	0m53.566s
sys	0m0.020s

I have some good news. Current master (and 3.1, I presume) is 4 times faster than 3.0.
I will still look if there is smth obvious to fix in 3.1

ossl_namemap_name2num_n with descendants (including locks/unlocks) liiks like a hotspot to me - 45% according to callgrind in master. @paulidale @hlandau - could you please take a look?

e.g. could we avoid CRYPTO_strndup/OPENSSL_free calls here (~10% in this synthetic example)?

NOTE: @beldmit If you are looking at timing, do the calls twice, and measure starting from the second one..
The first will cache the fetches..

I am mostly looking at the amount of calls.

Commenting the CRYPTO_strndup/OPENSSL_free causes gazillion tests to fail and 3 times speedup. Weird.

Nevermind, looked into the code :)

This is on my to look at list but I'm pretty busy following last week's face to face and I've a huge pile of other stuff to look at.
@beldmit, I have difficulty believing that strndup/free is the culprit.  Locking is more likely as @richsalz reported.  3.1 should have improved things in this regard by avoiding the more egregious locking problems.  I'm hopeful but I cannot say if any others remain at this point.  Time will tell.
However, I'm not certain that locking fixes alone will be sufficient.  @richsalz's code directly encounters one of the known problems: decoders are slower in 3.0 due to the provider architecture.  We need to be able to support a provider loading a key in a format that libcrypto doesn't know about and this means multiple parsing attempts.  There simply isn't any other option.  That doesn't mean we can't streamline things further -- we intend to look more deeply into this but contractor time is a limited resource and there are many other priorities.  Rest assured that performance is definitely on the backlog and is important to the project.
As for MSQUIC, there is a quick (sic) win available by refactoring the QUIC code to not create a new SSL_CTX on every connection.  Doing this in 1.1.1 is a moderately heavy operation, doing it in 3.0 is quite a bit heavier.  I suspect that avoiding this will improve things significantly, both for 1.1.1 and 3.0/3.1.  Unfortunately, I do not see myself getting time to contribute such a patch to MSQUIC any time soon.
Volunteers who can contribute such changes are welcomed of course.

Yes, long-term run shows that strdup/free are not tge culprit. I'll attach the callgrind results later

callgrind.out.655458.txt
What looks strange to me is 153 millions of call to ossl_decoder_fast_is_a with 20% of overal time (with descendants).

We need to be able to support a provider loading a key in a format that libcrypto doesn't know about and this means multiple parsing attempts. T

The project went too far. In order to support things that aren't currently available, the project is hurting -- a lot -- current users.  That is the wrong trade-off.  (This kind of "make it flexible, we can't see future needs" has been an endemic problem in OpenSSL code since the beginning, going back to SSLeay.)
@nibanks you might want to take a look at Pauli's suggestions above.  My feeling, however, is that "quite a bit heavier" for flexibility that nobody can currently use is a mistake.

Dear @nibanks
I'd split things apart.

The redesign to provider causes significant slowdown in some specific areas. It's a problem to be solved on OpenSSL level for corner cases or in general.

The architectural difference between 1.1.1 and 3.0 series is significant itself. So the approaches worked well for 1.1.1 should be reconsidered for 3.0. @paulidale provided a totally relevant recommendation and ignoring it looks like a suboptimal decision to me.

Is there list of know deficiencies @beldmit? I look at the linked https://github.com/microsoft/msquic/pull/2588 and it make sense. We could look  for patterns like that if if is clear what the caveats are. Aside from Quic, I also work on SslStream that empowers all TLS operations in .NET. While we did the work to support OpenSSL 3 we did not run any benchmarks AFAIK as at that time no distro we support was using it. I'm going to put it in my TODO list as well.

@wfurt #17627 contains some of these issues. Loading keys/certificates is currently much slower than in 1.1.1, but IRL it's usually one-time operation.

On our side, we spent some time trying to use a simple HTTP client / load generator on Ubuntu 22 and were stumped to see it saturate at around 400 connections per second for 48 threads while on other machines it worked fine. We noticed that there was something completely odd regarding locking as it was impossible for the process to use much more than one CPU and that most of the time was spent in futex_wake() and friends. After trying many things we finally locally built 1.1.1 and linked against it and suddenly the performance reached 74000 cps, or almost 200 times more.
Additionally, on the server side we already noticed an extreme use of locking, with chains starting like this one and involving pthread_rwlocks:
  92.80%  [kernel]                  [k] native_queued_spin_lock_slowpath.part.0

I instrumented the code in hope to find "the" culprit and found something like 80 calls to any flavor of pthread_rwlock_*() in a single accept/get/response/close cycle! 1.1.1 already had quite a bunch of them (I don't remember how many) but significantly less overhead, as if it was used on shorter chains. In the end we reimplemented our own locks (same principle as the lock callbacks that were unfortunately dropped from 1.1) and could more than double the server-side performance thanks to using much lighter locks.
So yes, there definitely is a big locking problem there. The rule of thumb for a call to any pthread_* function should normally be "am I really willing to give up the CPU and switch to another task, possibly thrashing all the L1 cache here?". Of course that's not exact but in terms of cost and impacts it's extremely close to reality. pthread_* functions should only be for high-level code (browsers etc) and rare cases. It's way too expensive for low-level or library code.
I failed to find any single occurrence of an atomic operation in the whole codebase, which makes me think that all of them are instead implemented by hand around a lock, so that's a dead end, when you consider that scalable code normally tries hard to avoid atomic ops because they slow things down, and that pthread_* functions do involve atomic ops and a syscall in the contented case that is at least 100 times slower than the atomic op itself...
For now we're condemned to stick to 1.1.1, as 3.0 is not just "degraded", it's simply not realistically usable at all for anything beyond the openssl command-line utility for us. This will pose security issues in field over time once 1.1.1 stops being supported, as power users are only starting to discover the big regression now by progressively switching to new distros. But for now we have no other choice.

@wtarreau, there was a bug in 3.0 where multiple threads ended up completely serialised which killed multiprocessor performance and, from your description, I think you hit this.  This was fixed in #18151 which was merged to later 3.0 releases.
OpenSSL does use atomic operations for reference counting (mostly).  It was quite a performance win when it was introduced.
@wfurt, the rule of thumb is pre-load what you're going to use.  Fetch is an additional cost over 1.1.1, so pre-fetch.  Certificate/key loading is slower, so pre-load where possible.  Avoid the convenience calls like EVP_sha256() because these do a (late) fetch internally.
@richsalz, the post quantum provider is using provider based decoders.  I am glad that the flexibility was included to enable such.

@paulidale, Yes, I know about OpenQuantumSafe.  It could have been done by them creating EVP_PKEY's, etc., by hand. That might not be as clean, admittedly, but you could have added EX_DATA to those objects, for example. Again, this is hurting everyone for what is still a niche offering.
Or you could do the "freeze" concept I offered in #15600.
Or you could have an internal hard-wired path that avoids lookup for default-enabled keys.
Is "avoid convenience calls like EVP_sha256" documented anywhere?
Lots of ways to approach this, and the project doesn't seem to be spending much effort on it, unless I am missing something.

@paulidale regarding 18151 I doubt given that it was fixed 9 months ago already and the problem was still present in November or so (I don't remember what exact version was the last one by then, probably 3.0.7). And even the last tests we'd run on 3.1-dev by then were less bad than 3.0 but still far from 1.1.1. OK interesting for atomic ops, I'm just surprised not to have been able to spot them though.

Is "avoid convenience calls like EVP_sha256" documented anywhere?

It appears not.. It should be so here it is..
https://github.com/openssl/openssl/pull/20354

I instrumented the code in hope to find "the" culprit and found something like 80 calls to any flavor of pthread_rwlock_*() in a single accept/get/response/close cycle!

@wtarreau - I wonder if you have any documentation or notes from that time which might help us identify which specific locks were causing the problem? I'm assuming the "80 calls" were not from 80 different call sites, but certain calls being repeated multiple times?

Hi Matt,
most of the notes I had were regarding 1.1.1 which we'll stick to, and for now I don't have access to this machine. But I think I will eventually again relatively soon, so as time permits I'll try to collect more info. The thing is that it's difficult to observe the call places because the time wasted calling locks is not evenly spread due to context-switches and sleeps in the kernel. In my case it's by redefining my own pthread_rwlock_*() functions that I had the idea of just adding a call counter and was amazed by the number of calls per connection. I do have some variants of these functions for debugging purposes which disable exponential back-off and which more easily permit to collect call graphs using perf, they're just a bit less easy to use and less precise.

But I think I will eventually again relatively soon, so as time permits I'll try to collect more info.

The other thing to bear in mind is that there are numerous performance improvements in 3.1. It's still not at 1.1.1 levels, but its better than 3.0. If you do re-run the exercise, doing it against 3.1 would be most helpful for us to figure out what we still have left to do.

Hi @mattcaswell
I could finally connect to the machine today and run the various tests for you. I compared openssl versions 1.1.1t, 3.0.8, 3.1.1-dev (commit 004bd8f97d), as well as wolfssl 5.5.4 (which uses very little locking). These were running on haproxy-2.8-dev8-c05d30, with regular pthread_rwlocks and with our own lighter rwlocks (plock). The machine is an intel Sapphire Rapids dual 8480+ (2 x 56 cores), hence 224 threads total. The tests only involved server mode (i.e. haproxy accepting connections) because the client mode in 3.0 is not even usable at all beyond just command-line tools.
The results are the following, in number of HTTPS connections per second, TLSv1.3, rsa2k cert:

openssl 1.1.1: pthread: 44k      plock:  53k
openssl 3.0.8: pthread: 10-15k   plock:  19k       # 3.0 is unstable with pthread
openssl 3.1.1: pthread: 26k      plock:  28k
wolfssl 5.5.4: pthread: 120-122k plock:  120-122k  # reached load generator's limits.

In single core, all of them show the same performance, so the only difference is locking. I re-enabled the lock counting in the plock version, since we redefine the pthread_rwlock functions, it's easy to do. These were measured over 1 million total connections. The results below are the number of calls to the lock functions per connection:

openssl 1.1.1: 120 rdlock, 276 wrlock, 396 unlock
openssl 3.0.8: 635 rdlock,  56 wrlock, 691 unlock
openssl 3.1.1: 164 rdlock,  57 wrlock, 220 unlock
wolfssl 5.5.4:   0 rdlock,   1 wrlock,   1 unlock

As you see it is not complicated, the performance is inversely proportional to the number of lock calls. It's very likely that the extra rdlocks in 3.1 compared to 1.1.1 are still far too much because performed on very thin operations. Also what is not seen here are the atomic ops, but maybe 3.1.1 still has a lot more shared data that are also accessed via atomic ops. And based on the performance numbers above, even though 3.1 recovers on some of the massive defects of 3.0, 3.1 still requires twice as many servers as 1.1.1 to process the same workload.
As promised I got a callgraph on 3.1. It's huge so I'm compressing it. I'm also attaching the flame graph but it's not really exploitable beyond seeing what are the main direct callers of the locks. pthread_rwlock_* here are our functions. pl_wait_unlock_long is the relaxation function that's waiting for someone else to release the lock, that's why it appears a lot. I'm well conscious that when you're dealing with 220 locks on a single connection, for sure these won't be removed in an eye blink, as I'm certain it already took time to add them :-(
I do really think that one of the biggest mistake in 1.1 was the removal of the locking callbacks, because in addition to adding an overdose of locks, newer versions don't even offer the possibility to switch to something lighter than pthread anymore, and that's extremely frustrating. I tend to think that if there is one low hanging fruit for the short term, it's definitely re-enabling a locking API. And please, not one using a generic unlock, but a separate read_unlock and write_unlock, which the user may both map to a the same generic unlock function if they want, but generally speaking, having to read a lock just to figure how to unlock it doubles the unlocking cost just for wrong API reasons, and that's exactly the type of thing that end up with a heavy mechanism like you have in pthread.
Hoping this helps.
ossl31-pthemu-perfreport.txt.gz

I have worked on embedded systems with multiple levels of threading, and removal of the locking API in favor of pthread would have definitely impacted that (I left before 1.1.1 was released).

Embedded/severely constrained systems are no longer a target for OpenSSL. That ship has sailed long time ago. That  of course does not imply we should not try to resolve performance problems caused by locking. But IMO no, adding back custom locking callbacks is not the way to go.

Perhaps "--thrads=external" is the way to support external locking systems.  Then you document what the various OSSL lock functions have to do.

The poor server might have to use its own private build of OpenSSL. Many apps will be fine with the performance hit.  (I’m not, it stinks). Maybe we can have a high-performance locking option.

Users absolutely hate having to rebuild OpenSSL in field. They always fear to miss an update and to be at risk, this is the reason why we're still having difficulties making some switch to QuicTLS. And nowadays given the pace at which wolfSSL is progressing, the huge bump in performance and the support for the QUIC API, for sure if one has to think about rebuilding in field, the opportunity to switch to another stack comes to mind.

The solution to the performance problems with locking must be to do less locking and/or avoiding locking contention (perhaps with application help, if it knows what it is doing) and not to replace some locking calls with some other calls.

Since the team seems to no longer be spending any effort on reducing locking, downstream users have little choice.
But I disagree with your comment, @t8m: lightweight locking is a completely reasonable option, especially if the heavy guarantees are not needed.

Embedded/severely constrained systems are no longer a target for OpenSSL. That ship has sailed long time ago. That of course does not imply we should not try to resolve performance problems caused by locking. But IMO no, adding back custom locking callbacks is not the way to go.

In this particular case (~10 years ago), it was a Xeon-based system with 32GB of RAM running Linux... not really constrained. The issue was the relationship between OpenSSL, pthread, and the other (lightweight) threading models running within pthreads, which were affinity-locked to a given core.

See also #20698.  I think that's probably a dup of this one.

See also #20715.

Worth noting that we now have an internal API ossl_crypto_mutex_lock which at least uses pthread_mutex_t rather than pthread_rwlock_t. We could switch to using this internally if it is better optimised for our use cases.

Uhhh it would be even worse! Even higher latency, forced scheduling on misses etc. Please no, enough damage already!

Can anyone assist here?
We are in no way against performance improvements in this area, we'd really appreciate anything that helps.  The OpenSSL contractors cannot make this a priority currently.  That is unfortunate but we've a lot of differing priorities to balance.
@richsalz, since you are, by far, the most vocal about the apparent lack of action in this area, you are welcome to submit pull requests to address the issues.

Well, the thing is, several of us are suggesting that offering the ability for the application to provide its own locks (as was the case before 1.1) would address the problem of locking compatibility, but t8m said that this known-working solution is not welcome, so it's hard to see how to assist in such conditions.

@wataash Would the application be providing its own locking routines at runtime or OpenSSL build time? The latter seems more of an option to me.
What locking routines would applications offer that offer higher performance? Spinlocks?

Would the application be providing its own locking routines at runtime or OpenSSL build time? The latter seems more of an option to me.

As explained above, providing them at build time implies that users will need to rebuild OpenSSL in field, something that most users do not want to do, to make sure they stay safe regarding updates by benefitting from those delivered by their operating system vendor. Thus, runtime as was done till 1.0.2 is the most suitable.

What locking routines would applications offer that offer higher performance? Spinlocks?

Any method that is deemed best for the application. For example applications using more threads than processors might want to perform blocking waits using mutexes to avoid spinning. Others that have no more threads than processors might want to use various types of spinlocks. Applications dealing with more than a few tens of threads will definitely want to implement exponential back-off and/or ticket-based locks, others might even want to implement NUMA-aware locks because they'll use multi-socket CPUs. And of course there are all other appliation-specific stuff such as counting locks, the time spent waiting, releasing internal resources while waiting to let other threads progress on something else, or perform a longjmp to switch to another task in a cooperative scheduler, etc. Practically anything that a thread-aware application wants to keep control on in order to manage resources.
In our case we had to switch to plocks because rwlocks are super expensive, unfair, do not implement exponential back-off and were causing crashes do to pauses in excess of two seconds due to extreme competition between threads, some of which would systematically fail. No single locking solution can be the solution to all use cases, and I think it's pretty visible in the number of issues opened on this specific topic.
The previous CRYPTO_set_locking_callback() API wasn't pretty but it did the job and it allowed to separately unlock reads from writes which is crucial for performance (something that pthread missed but it's almost 30 years
old and back then the focus was definitely not on low latency and multi-core CPUs since they did not exist).

@paulidale Alright, if you want to go there...
The project "we've a lot of differing priorities to balance" can be summed up in one four-letter word: QUIC. Nobody publicly wants that. The project should fix what it broke. The project, and its paid staff, should make fixing the performance problems a priority.  That's my opinion, and I'm sorry if you don't like it, but that's a thing with open source, you have to take complaints as well as the kudo's.
It's never too late to change direction.

@paulidale questions:

which of master or openssl-3.0 would this be fixed in first?
who would do a backport / forward port?
how active is 3.1.x development?
what happens if this doesn't get fixed in 3.0.x?  would the project extend the end of LTS for 3.1 past 3.0, or maybe go for a 3.2 and encourage people to move to 3.2?

@nicowilliams I generally agree that in an ideal world the cost of the lock wouldn't matter much since they should rarely be used. The problem here, as you can see, is their massive usage, which means it will not go away in an eyeblink. That's why I proposed as a low hanging fruit to restore the locking callbacks so that we can at least use some that suit the application's model in this context.
An RCU method like you described could of course be great, but I strongly doubt we'll see that in a reasonable time frame because, as you've noticed as well, they're used absolutely everywhere (when accepting a connection calls 691 locks there's definitely a problem with the data model). In fact while 1.1.1 was faster, when using massive threads it still spends most of its time in locks, as well, indicating that they've been there for a very long time and have deep roots. But let's see what is doable in a reasonable time frame. Anyway the problem we're having right now is that 1.1.1 is dead in 4 months and we won't have a working supported update by then :-/

@wtarreau

The problem here, as you can see, is their massive usage, which means it will not go away in an eyeblink.

No, there is a bug in 3.0 that's not there in 1.1 or 3.1, and I believe it has to do with disabling providers in code that should only be reading the providers list.  That makes that code acquire a write lock in what should be a read-only code path!

That's why I proposed as a low hanging fruit to restore the locking callbacks so that we can at least use some that suit the application's model in this context.

There is no alternative locking callbacks that an application could possibly provide that would make a threaded application perform well again with 3.0.  That should be absolutely clear by now.
(Or, if you really think that an application could provide a locking callback that yields better performance, please demonstrate that.)

An RCU method like you described could of course be great, but I strongly doubt we'll see that in a reasonable time frame because, [...]

Correct, we need to identify the breaking change and revert it.

Anyway the problem we're having right now is that 1.1.1 is dead in 4 months and we won't have a working supported update by then :-/

3.1 happens to be performant enough.  If you're using 3.0 and it doesn't work for you, switch to 3.1.
You can even safely LD_PRELOAD 3.1.

A hot stack trace that exemplifies the all-readers-are-now-writers-haha bug is in #20698 and looks like:
    CRYPTO_THREAD_write_lock (threads_pthread.c:112)
    algorithm_do_map (core_algorithm.c:48)
    algorithm_do_this (core_algorithm.c:122)
    ossl_provider_doall_activated (provider_core.c:1431)
    ossl_algorithm_do_all (core_algorithm.c:162)
    ossl_method_construct (core_fetch.c:162)
    inner_evp_generic_fetch (evp_fetch.c:344)
    evp_generic_do_all (evp_fetch.c:654)
    EVP_KEYMGMT_do_all_provided (keymgmt_meth.c:295)
    sk_EVP_KEYMGMT_num (decoder_pkey.c:54)
    ossl_decoder_ctx_setup_for_pkey (decoder_pkey.c:350)
    OSSL_DECODER_CTX_new_for_pkey (decoder_pkey.c:450)
    x509_pubkey_ex_d2i_ex (x_pubkey.c:208)
   ...

We're parsing a public key, so we need a provider for whatever algorithms are involved (PK and digest), so we search the provider list, and in the middle of doing that we grab a **** write lock.  This is what causes the performance disaster.  This is what needs fixing first.
RCU can help revamp all of this, but it's a separate topic, which is why I opened a separate issue for it (#20715).

* which of `master` or `openssl-3.0` would this be fixed in first?

Master usually.

* who would do a backport / forward port?

The person who does the pull required generally.

* how active is 3.1.x development?

Fairly, mostly bug fixes.

* what happens if this doesn't get fixed in 3.0.x?  would the project extend the end of LTS for 3.1 past 3.0, or maybe go for a 3.2 and encourage people to move to 3.2?

Extending support for 3.1 is something we've mentioned but not decided on.  3.1 will get a validated FIPS provider and the certificate sunsets after five years, so we'll need to do something I feel.

Extending support for 3.1 is something we've mentioned but not decided on. 3.1 will get a validated FIPS provider and the certificate sunsets after five years, so we'll need to do something I feel.

I'm looking to see if I can find a candidate commit to have introduced this.   This commit refactors the code in
    order to adhere to those guidelines and rules.

and
commit 03c137de971354b7c2e00f0198e85446ead6cfc3
Author: Matt Caswell<EMAIL_ADDRESS>Date:   Mon Aug 30 15:33:07 2021 +0100

    Add commentary about lock usage in provider_core.c

    Provide some guidelines, as well as some rules for using the locks in
    provider_core.c, in order to avoid the introduction of deadlocks.

and
commit 59a783d05ae379335f70261126d19859ae5a855d
Author: Matt Caswell<EMAIL_ADDRESS>Date:   Tue Jun 22 15:39:40 2021 +0100

    Fix a race in ossl_provider_add_to_store()

    If two threads both attempt to load the same provider at the same time,
    they will first both check to see if the provider already exists. If it
    doesn't then they will both then create new provider objects and call the
    init function. However only one of the threads will be successful in adding
    the provider to the store. For the "losing" thread we should still return
    "success", but we should deinitialise and free the no longer required
    provider object, and return the object that exists in the store.

that I really need to understand.
I should also write a test program for bisecting.  That will probably be more productive, but this one felt like code inspection should go faster.

@nicowilliams

3.1 happens to be performant enough. If you're using 3.0 and it doesn't work for you, switch to 3.1.

Have you seen my measures above ? 3.1 is still twice as slow as 1.1.1 (i.e. requires the double of servers) and 4 times slower than wolfssl. No, 3.1's performance is absolutely not acceptable. BTW the call graph above was on 3.1.
BTW I never claimed to be able to fix 3.0 from the application, as my measurements show, using alternative locks only helps get some performance back, but that's still hiding the dust under the carpet. For those of us on 1.1.1 at least it helps. For those on 3.0 it helps a lot more but for wrong reasons: if locks are abused, for sure using cheaper ones will reduce the contention, but making locks less abused in the first place would be better.

@wtarreau are your alternative locks spinlocks?  That's not a solution.  Application provided lock callbacks have library initialization issues where multiple objects/libraries (even in statically-linked apps) depend on OpenSSL, and then order of initialization matters, and if the first object/library to initialize OpenSSL fails to set spinlocks then you lose.  Just using libcurl and MIT Kerberos (say) makes this happen.  Do that and use gRPC in the same program and you've got serious problems with application-provided lock callbacks.  Moreover, spinlocks can work for some apps but not necessarily all apps.
Let's fix this.
The root cause is clear: taking write locks to read through the providers list.
The actual commits at fault I've not found yet.
There's several functions in this stack trace snippet that acquire write locks unnecessarily, in some cases via callback functions like reserve_evp_method_store().:
    CRYPTO_THREAD_write_lock (threads_pthread.c:112)
    algorithm_do_map (core_algorithm.c:48)
    algorithm_do_this (core_algorithm.c:122)
    ossl_provider_doall_activated (provider_core.c:1431)
    ossl_algorithm_do_all (core_algorithm.c:162)
    ossl_method_construct (core_fetch.c:162)
    inner_evp_generic_fetch (evp_fetch.c:344)

ossl_provider_doall_activated() definitely takes a write lock that it absolutely should not.  Perhaps the entire design of ossl_provider_doall_activated() is busted since its cb apparently is meant to be able to mutate.
Some help understanding this code would be nice.  Is there a guide to these internals?

@nicowilliams

are your alternative locks spinlocks?

Not exactly, but in part. They're spinning and upgradable RW locks with support for exponential back-off to reduce the contention on large thread counts. Here there is no library initialization issue because there's no initialization. The only need is for the storage area of the lock to be zero. Nothing magic nor any dependency with anything external, just very basic stuff. At the moment I'm implementing them by replacing pthread_rwlocks to save what CPU cycles can be saved this way, that's absolutely ugly.
One point though, regarding the code analysis you're currently running through. I don't know this code but the huge number of lock calls per connection suggests that some of them are called at very low levels. In this case even a read lock is disastrous because it will take exclusivity on the cache line for the time it takes to increment the lock, and it will take it again to release the lock. This is why even with cheaper locks on 1.1.1 it remains severely contended: at 53k cps and 396 locks per connection, that's 21M locks/s or 42M times a cache line changes hand per second, i.e. we're basically at 25ns per move and suspended to the cache's latency if that happens on the same cache line. This is also why the untyped unlock is so expensive, it forces a read before releasing the lock, which forces a remote owner to temporarily drop exclusivity on the line, so it's slow both for the one that wants to check the lock's state and for the one that was using it.
You'll also note that in 3.0 the performance was divided by 4 despite the number of write locks was also divided by 4, in part because the number of read locks was multiplied by 5, and very likely because someone holds the write look for much too long.
But definitely, the locks are taken and released way too often. It's generally good to think that an atomic op takes 100ns and that a lock needs at least two of them on a non-contended path. Of course this is not exact but it gives rules of thumb that help design storage models.
Good luck digging there, I personally gave up, finding it too convoluted (probably too dynamic).

@wtarreau the 3.0 performance problem is much worse than 4x.  The more contention, the worse it gets.
I agree that there's several low-level places (I see two at least) where write locks get taken that shouldn't be taken at all.
I also agree that read locks will still be slow, but they'll be much less slow than write locks if we can make it so writes are rare (as they should be).  It will be even better if we can make the provider list read-only, but with ENGINEs I think we can only make it append-only (which can be done lock-free with an atomic compare-and-swap, and the readers may need to do a memory barrier when reading that, so not great, but still better than atomic writes to hot cache lines).  I think the intent here was that with FIPS being toggle-able at run-time we have to allow run-time disabling of non-FIPS providers, but this is clearly a performance disaster and we should instead have readers skip over non-FIPS providers when FIPS is enabled.

Yes. BTW the memory barrier is free on modern architectures (the ones we care for) which adopt the TSO model.
BTW for 3.0 in client mode, in our tests the performance dropped from 74000 conn/s (1.1.1) to ~400/s (3.0). I didn't measure the amount of locks there but the machine was entirely wasting its cycles context-switching. So if you want to try to stress certain parts to make them appear, probably that using client mode with sufficient threads will exacerbate the issues. I don't understand the providers model, but your description makes me feel like two lists would be needed instead (fips and non-fips) and that only the correct one should be run over.

@wtarreau that's 185x slower!

I don't understand the providers model, but your description makes me feel like two lists would be needed instead (fips and non-fips) and that only the correct one should be run over.

Or just skip providers marked non-FIPS when in FIPS mode.
The real issue is ENGINE loading (e.g., ENGINE_add()).  That implies that the providers list has to be mutable, though append-only might be good enough.  Maintaining backwards compatibility means allowing ENGINE_add() to continue working.  Though, really, I don't understand the relationship between engines and providers yet.

@paulidale I wonder if the project might not have to extend 1.1.x support due to this.  If even 3.1 is not good enough...

The real issue is ENGINE loading (e.g., ENGINE_add()). That implies that the providers list has to be mutable, though append-only might be good enough. Maintaining backwards compatibility means allowing ENGINE_add() to continue working. Though, really, I don't understand the relationship between engines and providers yet.

In fact, even rebuilding a new list from scratch every time the list has to be updated, and that atomically replaces the previous one would very likely work because I don't think that the list is updated thousands of times a second.
I think that the data model tries to optimize for fast changes, while these do not match the requirements. For example in haproxy for exceptional events (e.g. a server gets added/removed), we prefer to use a rendez-vous point so that the operation is entirely single-threaded, which in turn allows to remove any locking mechanism around the rarely updated structure. This happens sufficiently rarely for anyone to even notice, if it takes 10 microseconds every second, who cares... That's better than taking 50ns every 100ns.

@wtarreau re: that 185x slowdown you see, is that constructing an SSL_CTX per-connection even though most/all are to the same target?  Not that the project should accidentally punish suboptimal uses of its APIs...

No, that was my first thought when I met this situation, based on the issue reports about this, but that's not the case, there's just one SSL_CTX per thread, created at boot time and that's all.

Some help understanding this code would be nice. Is there a guide to these internals?

#levitte you might need to step in here.
In other places

think the intent here was that with FIPS being toggle-able at run-time we have to allow run-time disabling of non-FIPS providers, but this is clearly a performance disaster and we should instead have readers skip over non-FIPS providers when FIPS is enabled.

Nope, FIPS and non-FIPS are easy to do via library contexts and properties.  The intent was to support PKCS #11 providers where what device they are using is pluggable -- thus providers need to be dynamic to some degree.  We (over?) engineered things to allow load/unload at any point.

if the project might not have to extend 1.1.x support

Post EOL support will be available to premium support customers.

We (over?) engineered things to allow load/unload at any point.

nice to hear, even if it's from an individual and not a statement from the OMC.

Post EOL support will be available to premium support customers.

This is disappointing to hear from an open source project.  It sounds like the kind of the thing a commercial software company would say.  Especially since it sure seems like the 3.0 design has a flaw.

Post EOL support will be available to premium support customers.

This is disappointing to hear from an open source project. It sounds like the kind of the thing a commercial software company would say. Especially since it sure seems like the 3.0 design has a flaw.

This is why we're encouraging our users to stay on older LTS distros which provide extended support for 1.1.1 (ubuntu 20.04, RHEL8, debian 11)  for the time it takes to find a solution, possibly through an alternative implementation. This is a real problem as at some point it will cause hardware compatibility issues, and it puts all the effort and responsibility on the distro vendors :-(

Nope, FIPS and non-FIPS are easy to do via library contexts and properties. The intent was to support PKCS #11 providers where what device they are using is pluggable -- thus providers need to be dynamic to some degree. We (over?) engineered things to allow load/unload at any point.

Just never remove any providers, only mark them disabled with a memory barrier.

We (over?) engineered things to allow load/unload at any point.

nice to hear, even if it's from an individual and not a statement from the OMC.

I don't need to hear this from the OMC.  I only need this fixed.  The project needs this fixed.  I'm going to leave the politics out.

Post EOL support will be available to premium support customers.

This is disappointing to hear from an open source project. It sounds like the kind of the thing a commercial software company would say. Especially since it sure seems like the 3.0 design has a flaw.

It's certainly not good that people can't move to 3.x due to the performance problems.

ossl_provider_doall_activated() definitely takes a write lock that it absolutely should not. Perhaps the entire design of ossl_provider_doall_activated() is busted since its cb apparently is meant to be able to mutate.

I believe I understand the reasoning as to why that write lock is there. If we can find a way to refactor things to get rid of it that would be great.
The purpose of ossl_provider_doall_activated is to call a callback (cb) on all providers that are currently activated. However we could have the situation where another thread attempts to deactivate a provider while ossl_provider_doall_activated is running - thus resulting in the cb actually being called on a deactivated provider in error. In order to avoid this we iterate through all the providers and take hold of the flag_lock to allow us to query whether prov->flag_activated is set. This much could be done with a read lock. However, if it is set then we next call provider_activate. This has the effect of writing to prov->activatecnt (in order to increment the number of "activation" counts) and prov->flag_activated (in order to set it - even though we know it is already set).  This is the reason that the write lock is obtained. Subsequently the write lock is then released.
The result is a list of providers which we know cannot be deactivated until activatecnt is decremented again and therefore we are free to call the callback not under lock without fear of another thread deactivating the provider.
The final step is then to call provider_deactivate on all those providers where we incremented the activatecnt to decrement it (and actually deactivate the provider if the activatecnt has fallen to a low enough value).
It occurs to me that we could optimise this. provider_activate() does a number of things but most of them are irrelevant in this situation. If we took a read lock on the flag_lock and determine that prov_flag_activated is set then all we actually need to do is increment prov->activatecnt. This could probably be done as an atomic.
There remains a problem in the final provider_deactivate step because deactivating the provider involves taking another write lock on prov->flag_lock and it is less clear to me how we could avoid that one.

There remains a problem in the final provider_deactivate step because deactivating the provider involves taking another write lock on prov->flag_lock and it is less clear to me how we could avoid that one.

Actually....probably we could just decrement activatecnt not under lock. Only if the result is then low enough to trigger an actual deactivation then we could take hold of the write lock and really deactivate it. We would have to be careful to handle the situation where activatecnt is incremented again between it dropping low enough for a deactivation and us taking the write lock.

Or, if deactivation would not actually ever unload the provider, just make it unavailable for further fetches, we could just atomically increment or decrement the activation count.  It actually does NOT matter what any other thread does in such case - an application cannot expect consistent behavior if multiple threads are randomly loading/unloading providers in the same library context.
We could truly unload the provider only when a libctx is being tear down.

I implemented my idea in #20927.

There remains a problem in the final provider_deactivate step because deactivating the provider involves taking another write lock on prov->flag_lock and it is less clear to me how we could avoid that one.

Actually....probably we could just decrement activatecnt not under lock. Only if the result is then low enough to trigger an actual deactivation then we could take hold of the write lock and really deactivate it. We would have to be careful to handle the situation where activatecnt is incremented again between it dropping low enough for a deactivation and us taking the write lock.

Yes, exactly.  You don't need a heavy duty lock where a simple atomic operation suffices.
Also, it's OK if one thread races to list providers while another races to deactivate some providers.  Unless the two threads can prove which one won, it doesn't matter if the reader thread sees those providers activated or deactivated.

Fixed another lock in #20932. It's unlikely this was the source of any contention since the justification for removing it is that we know its single threaded!! Still it should be cleaned up.

@mattcaswell absolutely, in the perf top it's very common to find RAND_bytes() in the stack from what I remember. I just had a look at the perf record above and it accounts for roughly 20% of the CPU alone, most of it in the locks.

Is there any reason not to have a per-thread RNG state?  Memory footprint?  If memory footprint is an issue then we could have a function that apps can call to say "this thread needs a thread-local RNG" and have the default be a global RNG.

Random state is per-thread, re-seeded from the global when needed.  See https://www.openssl.org/docs/man3.1/man7/EVP_RAND.html

Random state is per-thread, re-seeded from the global when needed. See https://www.openssl.org/docs/man3.1/man7/EVP_RAND.html

Ah, good to know.  It shouldn't be a hot stack though.  One possibility would be to use pthread_mutex_trylock() with the winner responsible for writing new seeds into all threads' RNGs where those new seeds will be picked up eventually.

The design of the DRBG stuff was explicitly intended to be lock-free except for re-seeding. Guess that didn't happen.

I've not looked at the RNG.

Another fix in #20943 related to ex_callback data which can impact everytime we create or free an object that can have ex_data associated with (regardless of whether it actually has any such data). E.g. this impacts BIO_new(), BIO_free() etc.

I found and fixed another DRBG related issue in #20944. It's unclear to what extent we can backport this one since the fix requires a new API function in the public DRBG fetchable interface.

@wtarreau could you please rerun your check with the Matt's patches mentioned in https://github.com/openssl/openssl/issues/20286#issuecomment-1542032326 and below?

I would love to, but I don't have access to that machine anymore. Maybe later in the future.

I think there are some more patches to come yet...

One more patch in #20953

The set of patches I've mentioned above have focused on identifying write locks which we should not be taking during a handshake. For each one identified I've looked at what we could do to eliminate it. Mostly this has meant converting write locks to read locks, although in some cases atomics have been used instead. To reduce the number of read locks in use we probably need a more radical approach such as the one proposed by @nicowilliams in #20715, although its possible that we might be able to identify some low-hanging fruit to remove some completely without that.
As far as the write locks are concerned I identified them by running s_server with a default configuration and using the default server.pem cert/key file:
$ ./openssl s_server -cert server.pem

I then connected to it using default configuration with s_client:
$ ./openssl s_client

I ignored the first few connection attempts to allow s_server to initialise caches etc and then examined what locks were taken by s_server during the handshake and the send of a simple message client -> server. I did all this on master. I expect all the patches identified to be equally applicable to 3.1/3.0, but its probably worth re-running the exercise in 3.1 to see if there are any additional locks being taken there that don't impact master.
In master, before my patches I saw 64 write locks being taken. After my patches there are 0. I am hoping that is sufficient to have a measurable impact on performance, but I don't have an easy way of measuring that right at the moment.

Doesn't the team have (almost) permanent access to scalable hardware for performance regression testing ? That's always a nice investment, and even vendors are easily willing to give away hardware for opensource projects.

We have some hardware that this can probably be done on and are trying to get a performance testing environment together. But we're not quite there yet.

We may receive a machine with sufficent cores to assess such gains in the next few weeks.

That would be great. One more point to note is that the patches are of course still going through review and decisions have yet to be taken about which branches they go to, i.e. they've not been merged yet. If you do get the opportunity to do some tests we'll need to make sure we are testing the right target with the right set of patches.

FYI, we (MsQuic) have dedicated hardware and existing tests that can be used to fairly easily measure perf improvements. The only problem (and possibly point of contention) is that we need a branch of quictls to point MsQuic to, to test. If someone can make that available, I can run the tests and have the data within an hour.

Same here, at the very least when running quick tests on shared lab machines, we must not spend 10 minutes figuring which patches to download and apply on top of what, so a branch, tag or commit ID is really essential.

Doesn't the team have (almost) permanent access to scalable hardware for performance regression testing ?

I'm not aware of any accessible hardware that goes beyond a small to, maybe at a stretch, moderate scale.
As a small OpenSource project, we have to rely on the community to do this.

As a small OpenSource project, we have to rely on the community to do this.

You have what, at least six paid staffers? And maybe US$1M or more in the bank after collecting premium support fees.  A moderate multi-CPU system is a few hundred USD. You're not a small project and dissembling doesn't help.

And in any case it's mostly a matter of asking. As a smaller opensource project, in haproxy we're very frequently offered to test hardware from CPU vendors, NIC & crypto accelerators vendors, or cloud providers, and in fact a few times a year we have to decline by lack of developers time. Given the criticality of the openssl code's scalability for many vendors, I see no reason why the project couldn't benefit from such offerings: it will dictate whether or not their hardware will be correctly used in the next few years. Simply making a public statement on the web site that you need frequent (daily? weekly?) access to large-scale hardware for performance regression testing should be sufficient to get you what you need and validate the effect of intuitive changes. At least we never commit performance-related changes that were not measured, and that's fortunate because more often than not the intuition is wrong.

The approach taken in #20944 turned out to be quite controversial so I have an alternative, hopefully less controversial version, in #20970. #20970 also has the advantage that we don't even use a read lock to get the reseed count.

Link: #20927, #20929, #20952

So I have the following:

#20927
#20943
#20950
#20952
#20953
#20970

Am I missing any?  I am working on merging this into a branch of quictls/openssl so that people can test.

Yes, @richsalz, we are in sync on this list.

There is also #20929, #20932

Thanks for the additions, @mattcaswell.

I have created a QuicTLS branch at https://github.com/quictls/openssl/tree/openssl-3.1.0%2Bquic%2Blocks that has all of the locking PR's.  @wtarreau, @nibanks please take a look.  And anyone else, of course.

Many thanks Rich! I'm particularly short of time these days (release in one week) but will do my best to give it a try in a reasonable time frame.

All that work, @mattcaswell, and it looks like MsQUIC has better handshakes but everything else is no-effect:
ThroughputUp_linux_x64_openssl3_Default Median (kbps)
Baseline 6217821 / Lock-fixes 6206295
% change from baseline: -0.18

ThroughputDown_linux_x64_openssl3_Default Median (kbps)
Baseline 6309755 / Lock-fixes 6173859
% change from baseline: -2.15

RPS_linux_x64_openssl3_ConnectionCount_1 Median (RPS)
Baseline 5814 / Lock-fixes 6537
% change from baseline: +12.43

RPS_linux_x64_openssl3_Default Median (RPS)
Baseline 627691 / Lock-fixes 625486
% change from baseline: -0.35

HPS_linux_x64_openssl3_Default Median (HPS)
Baseline 10252 / Lock-fixes 10490
% change from baseline: +2.32

Let's hope Willy has better news when he has time to test.

 I'm sorry, looks like the most degraded was connection count which is fixed now - but the rest were basically the same for 3.0 and 1.1.1. Do I miss anything? If not, looks like this benchmark is almost indifferent to the version change...

From 1.1 to 3.1 handshakes/sec dropped by 18%.  The other tests show negligible change.

Do I correctly understand that this problem is resolved by the patches?

Do I correctly understand that this problem is resolved by the patches?

No.  For MSQUIC the patches have almost no effect.  We need to see what other use-cases are effected, such as HAProxy.

I still suspect that not creating lots of SSL_CTXs will be a decent performance win.

I wonder how many threads were in use for the MSQUIC test?

It depends on the test being run, but for the RPS_default and HPS tests we have per-CPU threads. Full machines specs are here, but we have 40 logical processors on these machines. If you're interested, I can fairly easily collect flame graphs from our tests as well.

It depends on the test being run, but for the RPS_default and HPS tests we have per-CPU threads. Full machines specs are here, but we have 40 logical processors on these machines.

Ah - so 40 threads? My guess is that isn't high enough for lock contention to become a serious problem. This set of patches were targeted at removing lock contention problems (since the original issue raised here was specifically about locking performance).

If you're interested, I can fairly easily collect flame graphs from our tests as well.

Yes please!

Hi all,
I've run new tests on a smaller machine (AMD EPYC 74F3, 24 cores). The test consists in building haproxy with quictls/openssl-3.1.0+quic and quictls/openssl-3.1.0+quic+locks. As anticipated, the overhead of the locking on this machine is lower than on big ones (~15%), and Matt's changes did not provide a really significant performance gain there. The biggest one is +2.9% on the reuse case, which is not bad already, maybe we can expect more when using more threads. However, with the patches I'm not seeing pthread_rwlock_wrlock() anymore in the perf top, this is already a significant improvement. This load was transferred to rdlock and unlock though. For completeness I also ran the same tests with plock instead of pthread's locks and again, no change since there's basically no contention, only the cost of touching the locks.
The tests were run in rekeying and resume modes:
Test 1.1: quictls-3.1.0, pthread rwlocks, tls-reuse : 48.5k cps

   $ h1load -t 48 -c 960 -r 1 --tls-reuse https://<IP_ADDRESS>:8443/

   8.62%  libpthread-2.31.so  [.] __pthread_rwlock_unlock
   8.11%  libcrypto.so.81.3   [.] EVP_MD_free
   5.54%  libcrypto.so.81.3   [.] EVP_MD_up_ref
   5.08%  libpthread-2.31.so  [.] __pthread_rwlock_rdlock
   4.55%  libcrypto.so.81.3   [.] EVP_DigestInit_ex
   3.91%  libcrypto.so.81.3   [.] EVP_DigestUpdate
   3.67%  libcrypto.so.81.3   [.] EVP_MD_CTX_copy_ex
   3.35%  libcrypto.so.81.3   [.] sha512_block_data_order_avx2
   2.29%  libcrypto.so.81.3   [.] fe_mul
   2.26%  libcrypto.so.81.3   [.] ossl_namemap_empty
   2.02%  libcrypto.so.81.3   [.] x25519_fe64_sqr
   1.97%  [kernel]            [k] native_queued_spin_lock_slowpath
   1.74%  libpthread-2.31.so  [.] __pthread_rwlock_wrlock
   1.74%  libcrypto.so.81.3   [.] EVP_DigestFinal_ex
   1.67%  libc-2.31.so        [.] __nss_database_lookup
   1.23%  libc-2.31.so        [.] pthread_attr_setschedparam
   1.22%  libcrypto.so.81.3   [.] ossl_sa_get
   0.90%  libcrypto.so.81.3   [.] x25519_fe64_mul
   0.89%  libcrypto.so.81.3   [.] do_name
   0.80%  libcrypto.so.81.3   [.] fe_sq
   0.79%  libc-2.31.so        [.] malloc
   0.65%  libcrypto.so.81.3   [.] OPENSSL_cleanse
   0.64%  libcrypto.so.81.3   [.] OPENSSL_LH_doall_arg
   0.53%  libcrypto.so.81.3   [.] OPENSSL_LH_retrieve
   0.53%  libcrypto.so.81.3   [.] ossl_method_store_cache_get
   0.43%  libcrypto.so.81.3   [.] cmov

Test 1.2: quictls-3.1.0, pthread rwlocks, no-reuse : 27.5k cps

  $ h1load -t 48 -c 960 -r 1 https://<IP_ADDRESS>:8443/

  22.80%  libcrypto.so.81.3   [.] __bn_sqrx8x_reduction
  13.67%  libcrypto.so.81.3   [.] mulx4x_internal
  13.10%  libcrypto.so.81.3   [.] bn_sqrx8x_internal
   2.20%  libpthread-2.31.so  [.] __pthread_rwlock_unlock
   2.16%  libcrypto.so.81.3   [.] sha512_block_data_order_avx2
   1.86%  libcrypto.so.81.3   [.] EVP_MD_free
   1.63%  libpthread-2.31.so  [.] __pthread_rwlock_rdlock
   1.62%  libcrypto.so.81.3   [.] fe_mul
   1.47%  libcrypto.so.81.3   [.] __bn_postx4x_internal
   1.47%  libcrypto.so.81.3   [.] EVP_MD_up_ref
   1.42%  libcrypto.so.81.3   [.] x25519_fe64_sqr
   1.09%  libc-2.31.so        [.] __nss_database_lookup
   1.08%  libcrypto.so.81.3   [.] EVP_DigestInit_ex
   1.00%  libcrypto.so.81.3   [.] EVP_MD_CTX_copy_ex
   0.96%  libcrypto.so.81.3   [.] ossl_namemap_empty
   0.91%  libc-2.31.so        [.] pthread_attr_setschedparam
   0.76%  libcrypto.so.81.3   [.] EVP_DigestUpdate
   0.69%  libcrypto.so.81.3   [.] bn_mulx4x_mont
   0.66%  libcrypto.so.81.3   [.] x25519_fe64_mul
   0.61%  libpthread-2.31.so  [.] __pthread_rwlock_wrlock
   0.58%  libcrypto.so.81.3   [.] fe_sq
   0.52%  libc-2.31.so        [.] malloc

Test 3.1: quictls-3.1.0+locks, pthread rwlocks, tls-reuse : 49.9k cps

   $ h1load -t 48 -c 960 -r 1 --tls-reuse https://<IP_ADDRESS>:8443/

   9.28%  libcrypto.so.81.3   [.] EVP_MD_free
   8.91%  libpthread-2.31.so  [.] __pthread_rwlock_unlock
   6.60%  libcrypto.so.81.3   [.] EVP_MD_up_ref
   5.86%  libpthread-2.31.so  [.] __pthread_rwlock_rdlock
   5.14%  libcrypto.so.81.3   [.] EVP_DigestInit_ex
   4.35%  libcrypto.so.81.3   [.] EVP_DigestUpdate
   4.10%  libcrypto.so.81.3   [.] EVP_MD_CTX_copy_ex
   3.38%  libcrypto.so.81.3   [.] sha512_block_data_order_avx2
   2.54%  libcrypto.so.81.3   [.] ossl_namemap_empty
   2.31%  libcrypto.so.81.3   [.] fe_mul
   2.17%  libcrypto.so.81.3   [.] EVP_DigestFinal_ex
   2.04%  libcrypto.so.81.3   [.] x25519_fe64_sqr
   1.59%  libc-2.31.so        [.] __nss_database_lookup
   1.18%  libc-2.31.so        [.] pthread_attr_setschedparam
   0.90%  libcrypto.so.81.3   [.] x25519_fe64_mul
   0.81%  libcrypto.so.81.3   [.] fe_sq
   0.79%  libcrypto.so.81.3   [.] do_name
   0.78%  libc-2.31.so        [.] malloc
   0.67%  libcrypto.so.81.3   [.] OPENSSL_cleanse
   0.53%  haproxy-qtls31lk    [.] pl_wait_unlock_long
   0.53%  libcrypto.so.81.3   [.] OPENSSL_LH_doall_arg
   0.51%  libcrypto.so.81.3   [.] OPENSSL_LH_retrieve
   0.44%  libcrypto.so.81.3   [.] EVP_KDF_free

Test 3.2: quictls-3.1.0+locks, pthread rwlocks, no-reuse : 27.4k cps

  $ h1load -t 48 -c 960 -r 1 https://<IP_ADDRESS>:8443/

  23.12%  libcrypto.so.81.3   [.] __bn_sqrx8x_reduction
  13.87%  libcrypto.so.81.3   [.] mulx4x_internal
  13.30%  libcrypto.so.81.3   [.] bn_sqrx8x_internal
   2.18%  libcrypto.so.81.3   [.] sha512_block_data_order_avx2
   1.90%  libpthread-2.31.so  [.] __pthread_rwlock_unlock
   1.90%  libcrypto.so.81.3   [.] EVP_MD_free
   1.77%  libpthread-2.31.so  [.] __pthread_rwlock_rdlock
   1.63%  libcrypto.so.81.3   [.] fe_mul
   1.55%  libcrypto.so.81.3   [.] EVP_MD_up_ref
   1.51%  libcrypto.so.81.3   [.] __bn_postx4x_internal
   1.45%  libcrypto.so.81.3   [.] x25519_fe64_sqr
   1.11%  libcrypto.so.81.3   [.] EVP_DigestInit_ex
   1.03%  libcrypto.so.81.3   [.] EVP_MD_CTX_copy_ex
   1.01%  libc-2.31.so        [.] __nss_database_lookup
   0.97%  libcrypto.so.81.3   [.] ossl_namemap_empty
   0.88%  libc-2.31.so        [.] pthread_attr_setschedparam
   0.80%  libcrypto.so.81.3   [.] EVP_DigestUpdate
   0.71%  libcrypto.so.81.3   [.] bn_mulx4x_mont
   0.69%  libcrypto.so.81.3   [.] x25519_fe64_mul
   0.59%  libcrypto.so.81.3   [.] fe_sq
   0.52%  libc-2.31.so        [.] malloc
   0.49%  libcrypto.so.81.3   [.] OPENSSL_cleanse
   0.46%  libcrypto.so.81.3   [.] do_name

If we only grep on pthread.*lock:
$ grep pthread.*lock test-locks-ossl31.txt
Test 1.1: quictls-3.1.0, pthread rwlocks, tls-reuse : 48.5k cps
   8.62%  libpthread-2.31.so  [.] __pthread_rwlock_unlock
   5.08%  libpthread-2.31.so  [.] __pthread_rwlock_rdlock
   1.74%  libpthread-2.31.so  [.] __pthread_rwlock_wrlock
Test 1.2: quictls-3.1.0, pthread rwlocks, no-reuse : 27.5k cps
   2.20%  libpthread-2.31.so  [.] __pthread_rwlock_unlock
   1.63%  libpthread-2.31.so  [.] __pthread_rwlock_rdlock
   0.61%  libpthread-2.31.so  [.] __pthread_rwlock_wrlock
Test 3.1: quictls-3.1.0+locks, pthread rwlocks, tls-reuse : 49.9k cps
   8.91%  libpthread-2.31.so  [.] __pthread_rwlock_unlock
   5.86%  libpthread-2.31.so  [.] __pthread_rwlock_rdlock
Test 3.2: quictls-3.1.0+locks, pthread rwlocks, no-reuse : 27.4k cps
   1.90%  libpthread-2.31.so  [.] __pthread_rwlock_unlock
   1.77%  libpthread-2.31.so  [.] __pthread_rwlock_rdlock

FWIW as a comparison, wolfssl-5.6.0 delivers 35.0k in the no-reuse test and 79.2k in the reuse test, indicating that this machine is able to deliver more once the locks are gone (resp 27% and 59% more).

I finally ran the test on quictls-1.1.1 as well for a comparison. By the way, the limit above at 79k in the resume  test for wolfssl was client-limited. Adding two more clients it reached 124k.
With quictls-1.1.1 we get 30.5k CPS without resume and 106k CPS with resume:
Test 6.1: quictls 1.1.1, pthread rwlocks, no-reuse : 30.5k cps

  $ h1load -t 48 -c 960 -r 1 https://<IP_ADDRESS>:8443/

  28.49%  libcrypto.so.81.1.1  [.] __bn_sqrx8x_reduction
  16.83%  libcrypto.so.81.1.1  [.] mulx4x_internal
  16.33%  libcrypto.so.81.1.1  [.] bn_sqrx8x_internal
   2.50%  libcrypto.so.81.1.1  [.] sha512_block_data_order_avx2
   1.99%  libcrypto.so.81.1.1  [.] fe_mul
   1.86%  libcrypto.so.81.1.1  [.] __bn_postx4x_internal
   1.78%  libcrypto.so.81.1.1  [.] x25519_fe64_sqr
   1.02%  libc-2.31.so         [.] pthread_attr_setschedparam
   0.87%  libcrypto.so.81.1.1  [.] bn_mulx4x_mont
   0.84%  libcrypto.so.81.1.1  [.] x25519_fe64_mul
   0.71%  libcrypto.so.81.1.1  [.] fe_sq
   0.68%  libcrypto.so.81.1.1  [.] OPENSSL_cleanse
   0.55%  libc-2.31.so         [.] malloc
   0.55%  libc-2.31.so         [.] __nss_database_lookup
   0.36%  libcrypto.so.81.1.1  [.] ASN1_item_ex_i2d
   0.35%  libcrypto.so.81.1.1  [.] cmov
   0.28%  [kernel]             [k] acpi_processor_ffh_cstate_enter
   0.26%  libcrypto.so.81.1.1  [.] x25519_fe64_sub
   0.26%  libcrypto.so.81.1.1  [.] asn1_i2d_ex_primitive
   0.25%  libcrypto.so.81.1.1  [.] x25519_scalar_mult
   0.24%  libcrypto.so.81.1.1  [.] asn1_template_ex_i2d
   0.24%  libpthread-2.31.so   [.] __pthread_rwlock_wrlock
   0.24%  libcrypto.so.81.1.1  [.] bn_powerx5
   0.23%  libc-2.31.so         [.] free

Test 6.2: quictls 1.1.1, pthread rwlocks, reuse : 76.0k* cps (client limited) / 106k

  $ h1load -t 48 -c 960 -r 1 --tls-reuse https://<IP_ADDRESS>:8443/

   8.25%  libcrypto.so.81.1.1  [.] sha512_block_data_order_avx2
   6.10%  libcrypto.so.81.1.1  [.] fe_mul
   5.25%  libcrypto.so.81.1.1  [.] x25519_fe64_sqr
   3.93%  [kernel]             [k] native_queued_spin_lock_slowpath
   3.47%  libc-2.31.so         [.] pthread_attr_setschedparam
   2.48%  libcrypto.so.81.1.1  [.] x25519_fe64_mul
   2.17%  libcrypto.so.81.1.1  [.] fe_sq
   1.99%  libcrypto.so.81.1.1  [.] OPENSSL_cleanse
   1.87%  libpthread-2.31.so   [.] __pthread_rwlock_wrlock
   1.78%  libc-2.31.so         [.] malloc
   1.43%  libc-2.31.so         [.] __nss_database_lookup
   1.15%  libcrypto.so.81.1.1  [.] cmov
   0.85%  libcrypto.so.81.1.1  [.] x25519_scalar_mult
   0.85%  libcrypto.so.81.1.1  [.] x25519_fe64_sub
   0.76%  libc-2.31.so         [.] free
   0.64%  libcrypto.so.81.1.1  [.] x25519_fe64_add
   0.61%  libcrypto.so.81.1.1  [.] EVP_MD_CTX_reset
   0.56%  libcrypto.so.81.1.1  [.] ASN1_item_ex_i2d
   0.43%  [kernel]             [k] iommu_map_page
   0.42%  libcrypto.so.81.1.1  [.] asn1_i2d_ex_primitive
   0.42%  libcrypto.so.81.1.1  [.] asn1_template_ex_i2d
   0.41%  [kernel]             [k] _raw_spin_lock
   0.40%  haproxy-qtls111      [.] ebmb_insert
   0.39%  libcrypto.so.81.1.1  [.] pkey_hkdf_derive_init
   0.38%  [kernel]             [k] __fget_light
   0.37%  [kernel]             [k] memset
   0.37%  haproxy-qtls111      [.] pl_wait_unlock_long
   0.37%  [kernel]             [k] acpi_processor_ffh_cstate_enter
   0.35%  libssl.so.81.1.1     [.] do_ssl3_write
   0.33%  libcrypto.so.81.1.1  [.] SHA512_Update

Thus it tends to confirm the the simple fact of sharing too much between threads is the root cause of the problem.

I think most applications would be able to enter a steady configuration state pretty quickly.  I opened #15600 for this.
I will not have time to work on this but here is the idea:

Once an application calls that, a global flag is set.  Maybe it's per-library-context.
The relevant locking calls get preceeded by if (!frozen) ...lock-call... The tricky part is figuring out what the "relevant" calls are. But you can do that incrementally.
The various fetch routines can use a cache table (index by query string) and just return the old value. The tricky part is doing that in a lock-free way, but that's known technology.
Attempting to load a provider get an assertion failure (to make diagnosis easy)
Attempts to unload a provider, other than at process exist, also assert.

My intuition tells me that this will, for most applications, bring 3.0 performance much closer to 1.1 as it would avoid locking altogether.
Libraries that load providers would be strongly encouraged to include a function that applications can call to load the providers their library needs. Failure to do so would get a core dump that can be easily diagnosed.

Any updates on this?

Sadly, not that I'm aware of, except that as users upgrade, the situation is getting worse. We discovered that some can simply not perform SSL health checks anymore on large farms due to the 95% time spent in the locks that are slowing down the checks. It turned from 6600 connections/s at 8 CPUs avg to 2000 checks per second at 80 CPUs with a basically unusable service. The only solution we can give for now is "roll back to the previous distro which had 1.1.1, the last usable version", and when they ask what's the long term option we have no bright future to announce them :-(  It would become urgent to extend 1.1.1 support for as long as this problem is not fixed, or users are going to run outdated versions forever!

Quoting from https://www.openssl.org/blog/blog/2023/07/24/f2f-otc-committers-day3/:

The current performance of the master branch is slightly better than that of version 1.1.1 for our own handshakes per
second test at higher thread levels. However, it notably performs worse at 1 and 10 threads. Further investigation is
warranted to examine this performance issue, but it is unlikely to be related to lock-related problems.

Slides with some detail are at https://docs.google.com/presentation/d/1Ih_-jOXkrGZE1WviQw1ziXyiTFoLRhMVo8bcUj91dIY/edit#slide=id.p1

Thanks for the slides, Rich. At least it shows there's some tests now, it's already an improvement. The single-threaded test that degrades is a big concern because it cannot even come from locking and possibly implies some sleeping if more threads manage to hide this. In the worst case if there would be some sleeping with lock held, it could explain the extreme contention in multi-thread mode.

At least it shows there's some tests now, it's already an improvement.

There's even use of -fsanitize=thread in master now.
Looking at the state of the world it seems likely to me that 3.0 will just be replaced by 3.3 or some version that will indeed perform closer to 1.1.

I'm not keen on the infallible locks thing though.  POSIX mutexes are NOT infallible, but OpenSSL's "infallible" mutex lock is implemented with POSIX mutexes like so:
121 void ossl_crypto_mutex_lock(CRYPTO_MUTEX *mutex)
122 {
123     pthread_mutex_t *mutex_p;
124
125     mutex_p = (pthread_mutex_t *)mutex;
126     pthread_mutex_lock(mutex_p);
127 }

EOWNERDEAD and EDEADLK are always possible.  An infallible mutex that builds on pthread_mutex_lock() should check for these and... what? assert()?  Basically, I don't believe in infallible locks.

@mattcaswell my sense, looking at the current state of master, and the slides that @richsalz linked to, that the team is working hard on threaded performance in the master branch with an eye to a 3.2 or 3.3 release.  Is that right?  If so, what is the timeline for such a release?  Is there an ETA for when a release policy will be agreed to?

To be honest, nobody tests the returns from pthread_mutex_lock() because 1) these are already super slow, and slowing them even more with tests is generally not welcome where locks are used, and 2) in practice when you're told you can't lock because someone else has a trouble, basically you have no other option than killing the program.

Though, to that end, calling abort seems a much better choice than silently ignoring the error as ossl_crypto_mutex_lock currently does. Particularly for something like locking. So many memory safety (i.e. security-critical) invariants depend on lock functions actually locking.

Libraries calling abort is never a good idea. Checking and returning an error certainly should be done.

I wouldn't entirely agree with that (even libc free will abort in some cases of memory corruption), but, sure, there are multiple schools of thoughts as to how to handle programmer errors. My comment is that, given the existing type signature void ossl_crypto_mutex_lock(CRYPTO_MUTEX *mutex), you should abort.
If you want a fallible int ossl_crypto_mutex_lock(CRYPTO_MUTEX *mutex), with the caller being required to check, then you can pass the error up the caller. But, if you pick that option, do make sure the caller actually checks, or we're back to the same risk of security problems. (IIRC, OpenSSL went down this road because many of the fallible locking APIs were not checked in practice?)

To be honest, nobody tests the returns from pthread_mutex_lock() because 1) these are already super slow, and slowing them even more with tests is generally not welcome where locks are used, and 2) in practice when you're told you can't lock because someone else has a trouble, basically you have no other option than killing the program.

I agree that the lock/unlock functions should return void.  It's just that something needs to happen on error -- I'm not sure what exactly, but something.  At the very least there should be debug builds where lock errors trip assertions and cause aborts.

Libraries calling abort is never a good idea. Checking and returning an error certainly should be done.

I agree.  What we're hearing is "checking for locking errors is ETOOHARD" -- that's probably the real problem here, and it falls under my "I don't believe in infallible locks" comment :)
If we're going to have pretend-infallible locks then at the very least there should be a build option for what to do on lock failure -- ignore, log... somewhere, block indefinitely, assert/abort, call some callback, ...
I would really like OpenSSL to evolve to a shared-nothing-mutable threading design where the only cases where there are locks are when writers want to publish to readers new immutable versions of shared mutable state.  That would reduce the number of lock-taking error cases to check to a number that would not elicit an error-checking-is-ETOOHARD response.

That's another good reason for re-allowing user-provided locks, because clearly such semantics are not acceptable to some programs. We currently have to redefine our own pthread_rwlock_* functions to spoof the ones openssl is using in order to limit the degradation caused by locking, it's a real pain and may interfere with other libs which want to use the original one.

@mattcaswell my sense, looking at the current state of master, and the slides that @richsalz linked to, that the team is working hard on threaded performance in the master branch with an eye to a 3.2 or 3.3 release. Is that right? If so, what is the timeline for such a release? Is there an ETA for when a release policy will be agreed to?

We have implemented numerous lock related improvements in the master branch (which will become 3.2 when it is released). Mostly this is removal of unnecessary write locks (sometimes converting them to read locks, or sometimes removing them completely/avoiding them). We are currently targeting October for the 3.2 release. Beyond 3.2 we are shifting to a "time-based" release policy, so the next release after 3.2 (presumably 3.3) will be April 2024, and the one after that October 2024.
For the 3.2 release we are currently forming the release steering committee mentioned in the policy.

This will be a nice improvement, time-based releases are essential to keep a good health and kick away stuff that cannot be completed in time and going to cause trouble.

For the 3.2 release we are currently forming the release steering committee mentioned in the policy.

For the 3.3 release actually. 3.2 is almost done in practice.

That's another good reason for re-allowing user-provided locks, because clearly such semantics are not acceptable to some programs.

Absolutely not, at least not run-time configured lock callbacks.  User-provided lock callbacks conflict with OpenSSL being used by multiple different libraries in the same process, something that happens plenty.  Libraries like OpenSSL (if not all libraries) just must self-initialize automatically, which leaves no easy way to specify global options like alternative lock callbacks.
Build configuration time alternative lock callbacks are fine though.

We currently have to redefine our own pthread_rwlock_* functions to spoof the ones openssl is using in order to limit the degradation caused by locking, it's a real pain and may interfere with other libs which want to use the original one.

That's like a build configuration time alternative lock callback -- nothing wrong with that.  Mind you, all read-write locks are inherently bad for performance.

User-provided lock callbacks conflict with OpenSSL being used by multiple different libraries in the same process

This is simply not true. Under no circumstances should any lock be held during the program's initialization. If that were the case, even in its current state it would simply deadlock. Build-time doesn't work with distros, the locking mechanism depends on the program and not on the operating system, even less on the distro, so there's no way a build-time config will be suitable (just like the current choice is not suitable for servers and might work fine for browsers).
The reason is simple:

for the few threaded systems that start more threads than CPUs, latency is not a problem at all and it's better to sleep in locks, hence the current choice
for those with one thread per CPU, suffering a sleep and wake is terrible and totally ruins openssl's performance.
but it's the same lib in both cases. It used to be well addressed in the past by letting the application provide its locks. it has worked well for a decade. I'm perfectly fine (and would even encourage) to say that pthread_rwlocks are used unless the application changes them. But the regression from 1.0.2 and 1.1.0 on this point is so huge it's not even fun.

Mind you, all read-write locks are inherently bad for performance.

True to a certain extent but locking in general is bad for performance and it's not used to improve performance but to guarantee consistency between competing threads. rwlocks are always worse than just atomic ops or rcu etc but these do not suit every model and when a lock is needed, if the shared-to-exclusive ratio is reasonably relevant then rwlocks are better than exclusive locks. Also do not forget that atomic ops imply memory barriers and serialize writes in CPU caches. Sometimes it's much faster to perform a lock, a few changes and unlock than to perform many atomic changes. The typical case is stats counters, where you'd rather lock, update a full cache line at once and unlock rather than bouncing the cache line between threads for each counter (e.g. 8 times per line for 64-bit counters). And that's exactly a case where an RCU approach doesn't work since you want to collect cumulative updates.

Libraries calling abort is never a good idea. Checking and returning an error certainly should be done.

In general 100% yes. It is for an application not a library how to handle errors, and calling abort would preempt this. The only exception as I see it is assertion failures — and that is the sole circumstance where OpenSSL (correctly) uses abort today.
(Allowing an application to provide a custom assertion failure handler callback would also be reasonable, but after that point any attempt to reenter the library should rightly be considered UB.)

I agree. What we're hearing is "checking for locking errors is ETOOHARD" -- that's probably the real problem here, and it falls under my "I don't believe in infallible locks" comment :)
If we're going to have pretend-infallible locks then at the very least there should be a build option for what to do on lock failure -- ignore, log... somewhere, block indefinitely, assert/abort, call some callback, ...
I would really like OpenSSL to evolve to a shared-nothing-mutable threading design where the only cases where there are locks are when writers want to publish to readers new immutable versions of shared mutable state. That would reduce the number of lock-taking error cases to check to a number that would not elicit an error-checking-is-ETOOHARD response.

The only cases where acquiring a standard POSIX mutex can fail are cases which correspond to caller error which reflect a bug in our code in which an expected invariant is not being met. These situations are correctly addressed with an assertion (where they are even detectible) as there is no guarantee that anything about our internal state is valid in this case.
It should also be noted that the usage errors which can be made with a POSIX mutex (relock, unlock when not owner) also constitute undefined behaviour. There is no guarantee that these operations will fail 'nicely' when they are misused and if they are misused something has gone seriously wrong and we don't have any kind of guarantee of sane behaviour.

User-provided lock callbacks conflict with OpenSSL being used by multiple different libraries in the same process

This is simply not true. Under no circumstances should any lock be held during the program's initialization. If that were the case, even in its current state it would simply deadlock.

If, and only if only applications ever set lock callbacks, and never ever ever libraries that use OpenSSL, and still, if OpenSSL self-initializes for everything on first-need, then that would be almost OK.
The program (the application, main()) may not even know that it has to initialize OpenSSL because libraries that the program uses use OpenSSL.  For example, just using the name service switch w/o an nscd can cause this to happen via name service switch plugins that run in the application processes without the application authors even knowing.
Not only that, but OpenSSL uses versioned symbols now and multiple versions can now co-exist in the same process.  Yes, I've got apps that indirectly have OpenSSL 1.1 and 3.0 loaded in the same process, and never the twain meet.  But each object gets to link with only one version of OpenSSL, so the only way the application could set lock callbacks for all versions would be for it to dlopen() them and use dlfsym().  (Sure, if I needed to set different lock primitives, I'd probably only have to do it for one version of OpenSSL, so that might work.)
Going back to global lock callbacks would be a disaster if ever any OpenSSL-using libraries install their own lock callbacks.  And I guarantee that some developer somewhere will misunderstand and try to initialize OpenSSL lock callbacks in their library.

Build-time doesn't work with distros, the locking mechanism depends on the program and not on the operating system, even less on the distro, so there's no way a build-time config will be suitable (just like the current choice is not suitable for servers and might work fine for browsers).

You also have ELF symbol interposition to help you in this case.  Symbol interposition is actually a very nice solution because you don't even have to change the application if you don't want to or can't -- just use LD_PRELOAD.
OpenSSL just has to get their design for threaded scalability right.  There should be no need to switch to lock primitives that use spinlocks or anything of the sort.
Read-write locks are a performance disaster.  So are mutexes for that matter.  The correct answer is for OpenSSL to switch to a shared-nothing-mutable model, but that's clearly not happening before 3.4 now :cry:.

(Allowing an application to provide a custom assertion failure handler callback would also be reasonable, but after that point any attempt to reenter the library should rightly be considered UB.)

By that token, ignoring errors from pthread lock primitives is also UB.  If we're going to have the OpenSSL lock primitives return void then lock failures must abort().  The obvious answer is to not have OpenSSL lock primitives pretend to be infallible.  I guess that means I should open an issue about that.

(Allowing an application to provide a custom assertion failure handler callback would also be reasonable, but after that point any attempt to reenter the library should rightly be considered UB.)

By that token, ignoring errors from pthread lock primitives is also UB. If we're going to have the OpenSSL lock primitives return void then lock failures must abort(). The obvious answer is to not have OpenSSL lock primitives pretend to be infallible. I guess that means I should open an issue about that.

It is not about "pretending to be infallible". All cases of failure correspond to violation of an invariant where the only safe handling strategy is an assertion failure.
Can you explain which error codes from pthread_mutex_lock or pthread_mutex_unlock you are concerned about?

Can you explain which error codes from pthread_mutex_lock or pthread_mutex_unlock you are concerned about?

EOWNERDEAD and EDEADLK.

It is not about "pretending to be infallible". All cases of failure correspond to violation of an invariant where the only safe handling strategy is an assertion failure.

No assertions here:
121 void ossl_crypto_mutex_lock(CRYPTO_MUTEX *mutex)
122 {
123     pthread_mutex_t *mutex_p;
124
125     mutex_p = (pthread_mutex_t *)mutex;
126     pthread_mutex_lock(mutex_p);
127 }

What am I missing?  I don't see how this is OK.

(... lock callbacks ...)
I continue to disagree, I'm sorry. Even if you inherit from openssl that is loaded by another library, you're not going to change its lock callbacks nor suffer form them. And if you purposely use it, in the worst case two parts of the code will replace the locks (e.g. the first lib then the application). And so what ? it's always done with everything unlocked so you're running entirely on one version at a time. We can even imagine to make the registration fail if one was already performed so that there's no surprises. But basically this boils down to using 3 cases:

pthread_rwlocks
fast non-sleeping locks
other callbacks for debugging (e.g. counting).

And no, LD_PRELOAD is not a solution in field. We're already doing that and it's an horror, especially since right now the only thing we can intercept are pthread functions that maybe we don't want to intercept for other components. If at the very least we were certain to know which openssl functions we can forcefully redefine that would mostly be OK, I'd rather redefine them than pthread_rwlock. Plus the pthread_rwlock interface is ugly, it uses the same unlock function for read and write locks, forcing you to perform an extra memory access, while openssl internally differentiates them.

(... lock callbacks ...)
I continue to disagree, I'm sorry. Even if you inherit from openssl that is loaded by another library, you're not going to change its lock callbacks nor suffer form them. And if you purposely use it, in the worst case two parts of the code will replace the locks (e.g. the first lib then the application). And so what ?

But in that case if the lock callbacks are different then you'll be mismatching lock functions and locks!  That's UB, of course, and I expect a crash.
No, the only way in which global lock callbacks are OK is if they are set extremely early in main().  It's never OK if global lock callbacks are set by libraries that use OpenSSL.

it's always done with everything unlocked so you're running entirely on one version at a time.

If two or more users in the same process use OpenSSL, and both set the global lock callbacks, then there is no way to guarantee that "it's always done with everything unlocked".
Besides, the guarantee you want is not "it's always done with everything unlocked" but "it's always done before any locks are created".  I don't see how to do that other than either have the lock callbacks be in a lib_ctx like @mattcaswell suggested (so, not global) or only the app initializes them and only very early in main().
I'd be OK w/ per-lib_ctx lock callbacks.

But basically this boils down to using 3 cases:
* pthread_rwlocks

* fast non-sleeping locks

Spinlocks may not sleep, but they don't and can't fully resolve the performance problems with read-write locks.

* other callbacks for debugging (e.g. counting).

Arguably this should be done by OpenSSL itself.

But in that case if the lock callbacks are different then you'll be mismatching lock functions and locks!

No, because you're passing the whole set of callbacks at once for the same lib. The first or last one that passes sets the whole callbacks to be used by the openssl internal code. There's never any mixing of some functions and others here.

Besides, the guarantee you want is not "it's always done with everything unlocked" but "it's always done before any locks are created".

This is exactly what SSL_library_init() used to be made for: only one calls it and it's the one responsible for initializing the lib, locks etc. There's always a boot phase in any program, this has never been an issue.

And no, LD_PRELOAD is not a solution in field. We're already doing that and it's an horror, especially since right now the only thing we can intercept are pthread functions that maybe we don't want to intercept for other components. If at the very least we were certain to know which openssl functions we can forcefully redefine that would mostly be OK, I'd rather redefine them than pthread_rwlock.

Sure, I could see not wanting to interpose on locks from anything other than OpenSSL.  If OpenSSL made its lock funcitons interposable (hmm, they should be interposable as it is, I think) then you could just interpose on CRYPTO_THREAD_*lock() only.  Did you try that?

Plus the pthread_rwlock interface is ugly, it uses the same unlock function for read and write locks, forcing you to perform an extra memory access, while openssl internally differentiates them.

It does?  Where?  There's only CRYPTO_THREAD_unlock() for unlocking in readers and writers both.

No, no and no. I'm sorry. Libs do not use SSL callbacks to synchronize between themselves, they provide openssl with locks to use internally. That's completely different.

No, no and no. I'm sorry. Libs do not use SSL callbacks to synchronize between themselves, they provide openssl with locks to use internally. That's completely different.

I don't know what you're talking about.  Can you show me code to show me what you mean by "they provide openssl with locks to use internally"?

In https://github.com/openssl/openssl/issues/20286#issuecomment-1701379768, @wtarreau talks about two libraries using openssl with different locking schemes and colliding.  Inhttps://github.com/openssl/openssl/issues/20286#issuecomment-1701069849 @mattcaswell suggests a solution: openssl has a libctx variable each time openssl is linked into a library.  (Think different libraries use different crypto providers).  That could work.
I am going to copy @nicowilliams comment at https://github.com/openssl/openssl/issues/20286#issuecomment-1701318469 into a new issue.

Just this right after SSL_library_init():
	CRYPTO_set_locking_callback(ssl_locking_function);

The application provides its own ssl_locking_function which looks something like this that we used to use before 1.1.0:
void ssl_locking_function(int mode, int n, const char * file, int line)
{
	if (mode & CRYPTO_LOCK) {
		if (mode & CRYPTO_READ)
			HA_RWLOCK_RDLOCK(SSL_LOCK, &ssl_rwlocks[n]);
		else
			HA_RWLOCK_WRLOCK(SSL_LOCK, &ssl_rwlocks[n]);
	}
	else {
		if (mode & CRYPTO_READ)
			HA_RWLOCK_RDUNLOCK(SSL_LOCK, &ssl_rwlocks[n]);
		else
			HA_RWLOCK_WRUNLOCK(SSL_LOCK, &ssl_rwlocks[n]);
	}
}

In short, the application says to openssl "I'm having suitable locks for you to use, please use these ones" and that's all. These locks are used by openssl functions, not by the application. If you look, openssl even passes an index for these. It could as well pass a pointer to the lock but this method allows the locks to be of different sizes and it's up to the application to initialize them. If I had a choice of API I'd rather take
pointers and say "they're initializd using pthread_rwlock_init() and they're of size pthread_rwlock_t but the application may repurpose them if it wants and if it knows how to use a pthread_rwlock_t".

Just this right after SSL_library_init():
	CRYPTO_set_locking_callback(ssl_locking_function);

There can be only one user doing this in a process, and it must do this before all uses of OpenSSL.  If two users try this, then the first must win and the second must lose, and the first user's lock callbacks must be the only ones that get used.  If any user causes OpenSSL [self-]initialization to happen then all subsequent attempts to initialize OpenSSL must be no-ops.
And I strenuously object to libraries not having self-initialization.  Optional initialization when you're the first, that's OK but lame, but really, no, OpenSSL's threading performance should not depend on you providing better lock callbacks.

OpenSSL's threading performance should not depend on you providing better lock callbacks.
That's an ideal world but as I explained, as long as it shares lots of things it's this situation. And it's gotten much worse over time, see my measures above, from something like 120 to around 600 locks per accepted connection, versus just one for wolfssl.

do more shared-nothing-mutable, as that would greatly reduce the amount of lock contention.
Nobody denied that, it's just that at one moment such a statement has to face reality, and certain things which have to be atomically updated as a group need to be locked. We can also decide to change lots of things in the model and remove features, but there is a set of features and some of them require atomicity in certain operations. Atomic ops and RCU cannot do everything, the model must match.

If a new lib was developed from scratch it would probably adapt its API to follow such rules as much as possible. Here we're dealing with almost 30 years of backward compatiliity which is also why applications adopt it.

If a new lib was developed from scratch it would probably adapt its API to follow such rules as much as possible. Here we're dealing with almost 30 years of backward compatiliity which is also why applications adopt it.

I believe that the OpenSSL implementation can be adapted to be mostly shared-mutable-nothing.  I've described elsewhere how one might do that, and I'll repeat it here briefly:

make current shared-mutable structures like SSL_CTX internally have an immutable version pointed to as the current immutable version
use RCU or similar to

every time a shared-mutable structure -> publish a new immutable version inside
(writing will generally require an exclusive lock)
every time an immutable version is needed -> safely read it without locks

for global items like the providers list also use RCU or similar so that reading those does not require any locking

The only cases where acquiring a standard POSIX mutex can fail are cases which correspond to caller error which reflect a bug in our code in which an expected invariant is not being met.

There's two ways that POSIX mutexes can fail the way you're using them:
1. you have a lock-taking order bug that leads to deadlocks that get detected

2. a thread was canceled by the application or whatever (OpenSSL does not use `pthread_cleanup_{push,pop}()`

Regarding (1), ignoring deadlock errors and continuing is arguably worse than having a deadlock to begin with.
Yes. We should assert.

Regarding (2)... perhaps OpenSSL should use pthread_cleanup_{push,pop}().
When has OpenSSL ever been safe for use with pthread_cancel? We cannot support
a use case where a thread executing OpenSSL library code might be terminated at
some arbitrary time while mutating internal OpenSSL data structures.

It also does not seem to me to be remotely worth augmenting the OpenSSL codebase
with these calls given the rather obscure and rare usage of pthread_cancel.
Of course, you're welcome to raise a PR if you think this is a valuable feature
for a use case you are interested in. But it seems like this is going to require
radical rearchitecture of basically all code in the OpenSSL codebase, whether or
not it uses locks.

Can you explain which error codes from pthread_mutex_lock or pthread_mutex_unlock you are concerned about?
EOWNERDEAD and EDEADLK.

EOWNERDEAD is not applicable because it applies only to robust mutexes used in
an interprocess fashion, neither of which are the case in OpenSSL.
EDEADLK is documented as follows:
   The pthread_mutex_lock() function may fail if:

   EDEADLK
          A deadlock condition was detected.

"may fail" — meaning this is UB and you have no guarantee about this error code
being returned, so it is not sound as a fault handling strategy. If it does
occur it indicates a bug and the only safe thing to do is to assert.

What am I missing? I don't see how this is OK.

Yes. This is bad. We should assert here.
Regarding OpenSSL's excessive use of shared mutable state: wholly agree. This was an architectural mistake and we need to back out of it and find a way to do it that doesn't break API. So I'm basically in support of the architectural destination you're elaborating on here.

@nicowilliams : "every time a shared-mutable structure XXXX -> publish a new immutable version inside"
I assume XXXX means "changes" and that you left a word out. Also, what does "publish" mean?

@nicowilliams : "every time a shared-mutable structure XXXX -> publish a new immutable version inside" I assume XXXX means "changes" and that you left a word out. Also, what does "publish" mean?

Imagine that struct ssl_ctx_st has a field of type struct ssl_ctx_st * that points to an immutable version of itself, and that you use RCU or similar to a) replace that pointer with a pointer to the next new immutable version, b) to read it.

@nicowilliams : "every time a shared-mutable structure XXXX -> publish a new immutable version inside" I assume XXXX means "changes" and that you left a word out. Also, what does "publish" mean?

Oops, yes, I missed the word "changes" there.

@richsalz
FWIW, I've got a new rcu locked hash table implementation here:
https://github.com/nhorman/openssl/tree/new-lhash
Currently its roughly at parity with 3.0
master + new hash table:
real	0m4.095s
user 0m4.075s
sys	0m0.003s
but there are several more tables that need to be converted to leverage lockless operation.  If anyone would like to try it out

"roughly at parity"  Can you post side-by-side comparisons?  Also looking forward to seeing lock contention drop dramatically once you convert the various crypto-loookup table stuff.  Nice work.

@nhorman do you really mean at parity with 3.0, not an earlier version?

Sorry, I meant to say that the new hash implementation is roughly at parity with the master branch (sometimes a percent or two faster), but effectively parity.  But standby, I've noticed something regarding our L1 cache miss rate that I'm chasing down

Are you sure the L1 cache miss isn't caused by the excess use of atomics at various places that cause cache lines to bounce back and forth between cores ?

@wtarreau thats some of it, yes. In particular EVP_MD_up_ref seems to be causing a good deal of contention, but there are several data structures for the tests I've been running (the handshake test in the tools repository).  I'm observing them with perf record  -a -g -e cache-misses if you want to look as well

OK. I'm not surprised, I noticed the number of locks per connection reduced between some version ranges from 3.0 to 3.1-dev, the time spent in locks as well, while performance dropped at the same time! The only way for perf to drop despite less time spent in locks was clearly a sign of an increase of atomics usage (probably placed inside certain small loops instead of taking a lock once around it for a short time), and that further aggravates performance and makes it much harder to locate at the same time :-/  I can't try at the moment but I'll probably give it a try some time in the future.

The new hash table implementation here:
https://github.com/nhorman/openssl/tree/new-lhash
definately has the potential to add atomic calls, but all use cases are currently operating in a lockless mode
It definately seems to be becomming clear that when we accelerate hash table lookups in lockless mode we wind up, in the higher multithreaded cases, creating more cache line contention on other reads (atomics and otherwise)

@richsalz I don't have final data for your test case  (just ran it today quickly based on @beldmit request).  Mostly I've been working with the handshake test in our tools repo.  You can see those numbers here:
https://github.com/openssl/project/issues/440#issuecomment-1929357718

Okay thanks.  But still, good work!

I've tried the test_25519 reproducer with all the current 3.x branches and 1.1.1. Here are the results:

Branch
Real Time avg
Performance penalty from 1.1.1

1.1.1
2.40 s
0%

3.0
27.9 s
1146 %

3.1
4.56 s
90 %

3.2
3.17 s
32 %

I think we are pretty near the 1.1.1 performance on this particular benchmark that's basically testing a repeated decoding of  25519 key with 3.2.

callgrind.out.986463.txt
FTR, 3.2 callgrind results.

Rather than going to RCU with lhash, I suggest that lhash is replaced by something more recent.  While lhash was a great idea at the time, it has serious flaws now:

OpenSSL's use of hash tables are mostly add only.  There are only a couple of instances where item removal is required.  Lhash was designed for regular addition and removal.  It is really clever and efficiently resizing (both larger and smaller) when required, but our use generally doesn't require size reduction (which comes at a cost).
Lhash runs with a deliberately high load factor.  Often above unity.  This pretty much guarantees collisions which need to be resolved.
Lhash's collision resolution is to search a linked list of clashing items.  Linear time worst case.
Lhash resizing is purely power of two based which is far from the optimal ϕ based resizing.

Things have moved forward a lot in the last 40+ years since the lhash algorithm was invented.  Hash tables these days should run with a lower load factor (memory being cheap), they should have efficient collision resolution and they should be cache efficient.  There has been a lot of recent work on cache friendly hash tables.  There has also been work on lockless hash tables.  My suggestion is a cache friendly hash table in preference to a lockless one, but both should be considered.
There has also been some very recent developments in hash tables that are provably optimal in a space vs time respect.  We must consider these too.  E.g. https://www.quantamagazine.org/scientists-find-optimal-balance-of-data-storage-and-time-20240208/

Replacing LHASH, both API and implementation, would get a thumbs up from me. The existing LHASH code can be left as a near-deprecated public API for applications which still use it. Unfortunately LHASH is used as part of our public API in places so we can't realistically formally deprecate it.
I certainly have some ideas on the design of a replacement (internal) API.
I'd like to see any replacement minimise allocations as much as possible and maybe even support moves for objects which can support it (partially intrusive design). I also want it to generate code which allows hash and equality function pointer calls to be devirtualised and inlined.
Some food for thought:

(newer, includes detailed design diagrams and discussion) https://www.boost.org/doc/libs/1_84_0/libs/unordered/doc/html/unordered.html#intro

early design discussion: https://pdimov.github.io/articles/unordered_dev_plan.html
blogpost: https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html
blogpost: http://bannalia.blogspot.com/2013/10/implementation-of-c-unordered.html
blogpost: https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html

(older) https://www.boost.org/doc/libs/1_84_0/doc/html/intrusive/unordered_set_unordered_multiset.html
the above research cited by @paulidale

Let's move the LHASH replacement discussion here: https://github.com/openssl/openssl/issues/23599

Are there any updated benchmarks with the new OpenSSL 3.4 compared to 1.1.1?

https://openssl-library.org/performance.html