Serious startup slowdown caused by unoptimized jitterentropy code

[wtarreau]

Problem:

I found that after upgrading my local aws-lc build on my development machine, regression tests started to randomly time out on haproxy. Looking closer with perf record, I found a lot of "jent*" functions clogging the CPU, the heaviest one being "rol64", making me think about what is normally a single x86 instruction.

I measured the time it takes to start haproxy 100 times when built with aws-lc 1.39 and got this, indicating roughly 400 microseconds of user CPU per startup:

$ time for i in {1..100}; do ./haproxy-awslc-1.39 -v >/dev/null ; done

real    0m0.425s
user    0m0.039s
sys     0m0.074s

With 1.71 it was almost multiplied by 100, at 36 milliseconds per process:

$ time for i in {1..100}; do ./haproxy-awslc-1.71 -v >/dev/null ; done

real    0m4.063s
user    0m3.586s
sys     0m0.154s

The difference is clearly visible in perf report:

Overhead  Command          Shared Object       Symbol                                                              
  23.07%  haproxy-awslc-1  haproxy-awslc-1.71  [.] rol64
  14.84%  haproxy-awslc-1  haproxy-awslc-1.71  [.] jent_keccakp_chi
  12.51%  haproxy-awslc-1  haproxy-awslc-1.71  [.] jent_keccakp_theta
   8.57%  haproxy-awslc-1  haproxy-awslc-1.71  [.] jent_keccakp_rho
   8.44%  haproxy-awslc-1  haproxy-awslc-1.71  [.] xoshiro128starstar
   6.35%  haproxy-awslc-1  haproxy-awslc-1.71  [.] jent_keccakp_pi
   5.69%  haproxy-awslc-1  haproxy-awslc-1.71  [.] jent_memaccess
   2.16%  haproxy-awslc-1  haproxy-awslc-1.71  [.] uint32rotl
   2.08%  haproxy-awslc-1  haproxy-awslc-1.71  [.] ptr_to_le32
   1.53%  haproxy-awslc-1  haproxy-awslc-1.71  [.] jent_sha3_update
   1.31%  haproxy-awslc-1  haproxy-awslc-1.71  [.] jent_keccakp_1600
   1.14%  haproxy-awslc-1  haproxy-awslc-1.71  [.] jent_sha3_init
   1.05%  haproxy-awslc-1  libc-2.33.so        [.] __memset_avx2_unaligned_erms
   0.79%  haproxy-awslc-1  haproxy-awslc-1.71  [.] jent_keccakp_iota
   0.67%  haproxy-awslc-1  haproxy-awslc-1.71  [.] jent_get_nstime
   0.60%  haproxy-awslc-1  haproxy-awslc-1.71  [.] jent_sha3_fill_state
   0.54%  haproxy-awslc-1  haproxy-awslc-1.71  [.] le32_to_ptr
   0.53%  haproxy-awslc-1  haproxy-awslc-1.71  [.] jent_hash_time
   0.47%  haproxy-awslc-1  haproxy-awslc-1.71  [.] ptr_to_le64

There's a massive problem here. Grepping for "rol64" drove me to the jitterentropy third party lib, in sha3 code. All of these are supposed to be single-instructions on a CPU, but being forced at -O0, they result in an immense amount of garbage (huge and slow functions) that take 100 to 1000 times the equivalent number of cycles to execute, to the point of slowing down operations by that much.

Solution:

I don't know at this stage. I'm still investigating. I've found that the lib contains a test for optimizations and asks to run without:

third_party/jitterentropy/jitterentropy-library/src/jitterentropy-base.c: #error "The CPU Jitter random number generator must not be compiled with optimizations. See documentation. Use the compiler switch -O0 for compiling jitterentropy.c."

I just do not understand why it is done this way, the doc say "see documentation" but nothing explains this in the doc (and there's even a link that returns a 404). Something that relies on -O0 is seriously broken given that it will solely depend on how dumb the compiler itself tries to be and we have no guarantees on this.

I have not found yet what the call path for these functions is, nor if we can avoid it under certain conditions. What if I pass -Dinline="__inline __attribute__((always_inline))" to at least save the basic asm-level operations from being turned into functions ?

And even if this thing was really needed for obscure reasons, can't we make it run for way less than 40 ms on modern systems ? 40ms is an eternity at a computer scale, some operating systems boot in less than that. Not even thinking about smaller machines like armv7 where it may take ages.

Requirements / Acceptance Criteria:

At least get back to the normal CPU usage of previous versions (not yet bisected, and I don't think it will be useful as someone probably had a good reason at some point to think it would be nice to rely on this) or have a way to easily opt out for this CPU-hungry mechanism which already impacts stability (I haven't found how for now).

Thanks!

[wtarreau]

The inline definition just makes it go down from 36ms to 32ms (i.e. 80 times slower instead of 90). Not worth it.

[wtarreau]

And changing -O0 to -O2 -U__OPTIMIZE__ only divides that time by 4 (9.5ms of overhead). The entirety of the whole program startup time is spent in these functions:

Overhead  Command  Shared Object      Symbol                                                                       
  56.35%  haproxy  haproxy            [.] jent_keccakp_1600                                                       
  25.05%  haproxy  haproxy            [.] jent_measure_jitter                                                     
   4.10%  haproxy  [kernel.kallsyms]  [k] insn_get_opcode                                                         
   4.10%  haproxy  ld-2.33.so         [.] check_match                                                             
   3.50%  haproxy  haproxy            [.] jent_sha3_update                                                        
   1.98%  haproxy  [kernel.kallsyms]  [k] xas_load                                                                

[wtarreau]

OK I finally found by trial and error that passing:

 -DDISABLE_CPU_JITTER_ENTROPY=ON

on the cmake command line fixes it. That will do it for me now but I think that a better solution should be found, and if this is the only one, at least it should be prominently documented so that users don't fall into the same trap by accident.

[torben-hansen]

Hi, thanks for the report. Your observations look correct and we are also aware of the initial startup cost.

The implementation of AWS-LC's randomness generation (RNG) has changed slightly. The backend RNG now prioritise a policy of "rule of two" for entropy sources: Two entropy sources must fail before AWS-LC can return predictable randomness. Its our new defense-in-depth mechanism.

What this means in practice, is that AWS-LC will prioritise to use two "independent" entropy sources. Namely, "CPU Jitter Entropy" and an Operating System source (e.g. getrandom, getentropy, etc). You cannot as a user configure entropy sources at runtime. That's a deliberate choice to reduce mutation surface. The reason we use "CPU Jitter Entropy" is because of its portability; e.g. CPU entropy sources such as rndr aren't always available.

CPU Jitter Entropy is quite slow, as you discovered. That fact cannot be changed. But AWS-LC contains a number of "caches" that mitigates it for a steady-state application; the downside is that you cannot avoid it at startup, because we have to get fresh entropy to initialise the library.

If you are experiencing problems running AWS-LC in production using the default setup, happy to hear about.

[wtarreau]

Hi, many thanks for your explanation.

Regarding the impacts, they are significant. I initially noticed regression tests randomly failing on my machine because they run in parallel (typically 2*nproc), but now they're taking insane amounts of CPU and are hindering each other and triggering timeouts. And any API that used to dynamically check for versions and enabled features using "haproxy -v" and "haproxy -cc", or to validate a keyword by issuing "haproxy -c -f /tmp/keyword.cfg" now runs 90 times slower. It's a problem because we've always been particularly careful about extremely fast startups to encourage dynamic validation for APIs, and suddenly it means this practice has to be seriously reconsidered by users.

What I don't understand however is why the jitterentropy library needs to be initialized when getrandom() works. If, as you explained, two entropy sources must fail before AWS-LC can return predictable randomness, and getrandom() is tested first and works, there's no need to switch to jitterentropy, right ? Or is it just related to initialization order, making its initialization mandatory despite not being used ? If so, maybe we could adjust the initialization calls to only initialize it once getrandom() has failed ?

At the moment the only solution I'm seeing is for us to update our build docs to explain to users how to disable jitterentropy at build time :-( It's a bit of a shame because we've consistently promoted aws-lc a lot for its great performance, so I'm feeling a bit uneasy starting to add some forms of "except for xxx" in the doc.

[justsmth]

For your immediate use case, -DDISABLE_CPU_JITTER_ENTROPY=ON is a supported build-time option. On x86_64 (or AArch64 with RNDR), this still maintains two independent entropy sources: the OS RNG (getrandom) as the seed source and RDRAND/RNDR providing the extra entropy -- so rule-of-two is preserved. We agree the documentation around this flag needs improvement.

If getrandom() is tested first and works, there's no need to switch to jitterentropy, right?

[...] maybe we could adjust the initialization calls to only initialize it once getrandom() has failed?

One clarification on the design: the two sources aren't arranged as a fallback chain (try A, fall back to B on failure); BOTH contribute to every seed/reseed concurrently. So deferring Jitter init until the OS source fails wouldn't match the threat model. We still mix in a second independent source in case the first is weak or compromised in a way we can't detect (say, a backdoored OS RNG or the initial boot of an IoT device). Jitter Entropy was chosen as that second source for its portability across platforms that lack hardware RNG instructions.

That said, it's worth exploring the possibility of making Jitter Entropy a fallback second source rather than the unconditional one. On platforms where two faster independent sources are already available (e.g., getrandom + RDRAND on x86_64, or getrandom + RNDR on modern AArch64), we might satisfy rule-of-two without paying the Jitter initialization cost at all, and only bring Jitter into the picture on targets that genuinely need it, i.e., those with no HW RNG. (FIPS builds would still require CPU Jitter Entropy.) That could preserve the defense-in-depth guarantee everywhere while eliminating the startup penalty on the most popular platforms.

[wtarreau]

-DDISABLE_CPU_JITTER_ENTROPY=ON is a supported build-time option.

Perfect, thank you for confirming!

it's worth exploring the possibility of making Jitter Entropy a fallback second source rather than the unconditional one.

Absolutely, that matches the principles of "fallback" I was speaking about, and to initialize it last if you didn't find the two sources you need. And the two platforms that give you HW entropy are also the ones we all care about for performance (i.e. people will rarely complain about 40-50ms of CPU time when starting a process on an old MIPS for example).