Fortuna: allow increased concurrency

[cem]

Summary

Add experimental feature to increase concurrency in Fortuna. As this
diverges slightly from canonical Fortuna, and due to the security
sensitivity of random(4), it is off by default. To enable it, set the
tunable kern.random.fortuna.concurrent_read="1". The rest of this commit
message describes the behavior when enabled.

Readers continue to update shared Fortuna state under global mutex, as they
do in the status quo implementation of the algorithm, but shift the actual
PRF generation out from under the global lock. This massively reduces the
CPU time readers spend holding the global lock, allowing for increased
concurrency on SMP systems and less bullying of the harvestq kthread.

It is somewhat of a deviation from FS&K. I think the primary difference is
that the specific sequence of AES keys will differ if READ_RANDOM_UIO is
accessed concurrently (as the 2nd thread to take the mutex will no longer
receive a key derived from rekeying the first thread). However, I believe
the goals of rekeying AES are maintained: trivially, we continue to rekey
every 1MB for the statistical property; and each consumer gets a
forward-secret, independent AES key for their PRF.

Since Chacha doesn't need to rekey for sequences of any length, this change
makes no difference to the sequence of Chacha keys and PRF generated when
Chacha is used in place of AES.

On a GENERIC 4-thread VM (so, INVARIANTS/WITNESS, numbers not necessarily
representative), 3x concurrent AES performance jumped from ~55 MiB/s per
thread to ~197 MB/s per thread. Concurrent Chacha20 at 3 threads went from
roughly ~113 MB/s per thread to ~430 MB/s per thread.

Prior to this change, the system was extremely unresponsive with 3-4
concurrent random readers; each thread had high variance in latency and
throughput, depending on who got lucky and won the lock. "rand_harvestq"
thread CPU use was high (double digits), seemingly due to spinning on the
global lock.

After the change, concurrent random readers and the system in general are
much more responsive, and rand_harvestq CPU use dropped to basically zero.

Tests are added to the devrandom suite to ensure the uint128_add primitive
utilized by unlocked read functions to specification.

Test Plan

$ make -C tests/sys/devrandom
$ $(make -V .OBJDIR -C tests/sys/devrandom)/uint128_test.full uint128_inc
passed
$ $(make -V .OBJDIR -C tests/sys/devrandom)/uint128_test.full uint128_add64
passed
$ $(make -V .OBJDIR -C tests/sys/devrandom)/uint128_test.full uint128_chacha_ctr
passed

[markm]

This is a step in a direction that I've been wanting to doo for quite some time; pin multiple output generators to processors. There is more, but I need to write it in detail first.

[cem]

Thanks Mark for taking a look at both of these differentials!

In D20313#437862, @markm wrote:

This is a step in a direction that I've been wanting to doo for quite some time; pin multiple output generators to processors. There is more, but I need to write it in detail first.

I remember you had proposed work in this direction! I know I said I didn't intend to work on it at the time, but I sort of fell into this idea accidentally. I was rereading FS&K for the parent differential and this idea occurred to me. I had to implement at least a proof of concept. :-) (And I still have one TODO in my scribbled notes on my printed copy of FS&K chapter 9…)

I think this differential is mostly a conservative step — we still have a canonical, single instance, global Fortuna (modulo slight AES rekeying differences) — it just shifts the CPU work of PRF generation out from under the global mutex. (This is especially beneficial because FreeBSD mutexes assume CPU work takes a relatively short amount of time and therefore waiters will spin indefinitely waiting for an on-CPU lock holder. That doesn't work as well for long CPU-intensive PRF generation under lock. Additionally, our mutexes are not fair, so concurrent readers (and rand_harvestq) get varying amounts of lock acquisitions arbitrarily.)

I have a nice screenshot demonstrating the result (in Chacha mode; with AES the readers see about 190 MB/s):

[cem]

I think to actually land this, it probably makes sense to hide this behavior behind a non-default tunable. I don't think that complicates things too much, but please discuss. It's certainly a "Relnotes: yes". Is that acceptable from a secteam perspective, @delphij ?

Another alternative would be to fork the fortuna module, but I don't like that solution much.

[cem]

Add default-off (for now) knob to enable/disable the feature

[cem]

Need secteam approval.

[cem]

• Rebase on newer version of D20312
• Refactor somewhat to improve clarity
• Continue to artificially limit lock hold duration to 4kB in "locked" == "!concurrent" mode
• Continue to rekey AES at 1MB intervals

I think this is more or less ready to commit (behavior while disabled is
satisfactory), barring any review concerns. Thanks!

[cem]

Rebase on D20312 changes

[delphij]

sys/dev/random/fortuna.c

493 ↗

(On Diff #58384)

The mutex would be held for too long for huge block (it seems that we all missed this in D20312), and it shouldn't because it would enable userland to effectively DoS the kernel because the mutexes would spin waiting for something else that is computational intensive. The synchronization model must be revisited here.

I think in order to make this work the code needs to be refactored to something more MP friendly, e.g. fortuna_state should be per-CPU, and the read be done in critical sections.

sys/dev/random/uint128.h

69 ↗

(On Diff #57570)

It seems that this is really uint128_add64?

[cem]

sys/dev/random/fortuna.c

493 ↗

(On Diff #58384)

I noticed and fixed this in D20312, actually. In this revision, please see line 477 above (if locked ⇒ chunk_size = PAGE_SIZE;) and corresponding comment.

The user can already DoS the kernel (although less severely) today, due to PAGE_SIZE generation under lock. There's no good way to fix this without the exact change in this revision ­— moving PRF generation out from under the mutex.

This change does make the code substantially more MP friendly, please see the proposed commit message.

sys/dev/random/uint128.h

69 ↗

(On Diff #57570)

Yes, I can change the name if you like.

[delphij]

sys/dev/random/uint128.h

69 ↗

(On Diff #57570)

Yes, please.

[cem]

Rename uint128_add to the more appropriate uint128_add64