Add Fenestras X random(4) implementation

[cem]

Summary

Big picture:

• Scalable entropy generation with per-CPU, buffered local generators.
• "Push" system for reseeding child generators when root PRNG is reseeded. (Design can be extended to arc4random(9) and userspace generators.)
• Similar entropy pooling system to Fortuna, but starts with a single pool to quickly bootstrap as much entropy as possible early on.
• Reseeding from pooled entropy based on time schedule. The time interval starts small and grows exponentially until reaching a cap. Again, the goal is to have the RNG state depend on as much entropy as possible quickly, but still periodically incorporate new entropy for the same reasons as Fortuna.

Notable design choices in this implementation that differ from those
specified in the whitepaper:

• Blake2B instead of SHA-2 512 for entropy pooling
• Chacha20 instead of AES-CTR DRBG
• Initial seeding. We support more platforms and not all of them use loader(8). So we have to grab the initial entropy sources in kernel mode instead, as much as possible. Fortuna didn't have any mechanism for this aside from the special case of loader-provided previous-boot entropy, so most of these sources remain TODO after this commit.

Test Plan

Branch is up on Github including two revisions not posted on phabricator: one to enable the option by default in amd64 GENERIC, and one to add some printf XXX style logging which would not be included in a "real" version of this algorithm but is useful to verify it is working as designed. (It could be left in as CTR or dtrace or something hooks, just not raw printf.)

https://github.com/cemeyer/freebsd/tree/201912_random4_fxrng

Design whitepaper: https://aka.ms/win10rng

See also more discussion of design in fx_main.c.

Some logging (with the entire patch stack, although I tested each piece individually while working on the stack):

Dec 16 11:14:41 testvm kernel: ---<<BOOT>>---
Dec 16 11:14:41 testvm kernel: Copyright (c) 1992-2019 The FreeBSD Project.
...
Dec 16 11:14:41 testvm kernel: subsystem ffffff
Dec 16 11:14:41 testvm kernel:    parse_acpi_tables(0)... done.
...
Dec 16 11:14:41 testvm kernel: subsystem 2160000
Dec 16 11:14:41 testvm kernel:    random_init(0)... done.
Dec 16 11:14:41 testvm kernel:    random_harvestq_init(0)... done.
Dec 16 11:14:41 testvm kernel:    random_alg_context_ra_init_alg(0)... done.
Dec 16 11:14:41 testvm kernel:    module_register_init(&rdrand_mod)... random: registering fast source Intel Secure Key RNG
Dec 16 11:14:41 testvm kernel: random: fast provider: "Intel Secure Key RNG"
Dec 16 11:14:41 testvm kernel: done.
Dec 16 11:14:41 testvm kernel:    module_register_init(&nehemiah_mod)... done.
Dec 16 11:14:41 testvm kernel:    random_harvestq_prime(0)... XXXfxrng_event_processor: source 0 'first' time
Dec 16 11:14:41 testvm kernel: done.
Dec 16 11:14:41 testvm kernel:    __stack_chk_init(0)... XXXfxrng_alg_seeded: seeded with 4096 bytes of high-quality entropy.
Dec 16 11:14:41 testvm kernel: random: unblocking device.
Dec 16 11:14:41 testvm kernel: done.
...
Dec 16 11:14:41 testvm kernel: subsystem 3100000
...
Dec 16 11:14:41 testvm kernel:    module_register_init(&randomdev_mod)... random: entropy device external interface
Dec 16 11:14:41 testvm kernel: done.
...
Dec 16 11:14:41 testvm kernel: XXXfxrng_event_processor: source 1 'first' time
Dec 16 11:14:41 testvm kernel: cryptosoft0: <software crypto>
...
Dec 16 11:14:41 testvm kernel: subsystem a000000
...
Dec 16 11:14:41 testvm kernel:    kproc_start(&random_proc_kp)... done.
Dec 16 11:14:41 testvm kernel: XXXfxrng_event_processor: source 7 'first' time
Dec 16 11:14:41 testvm kernel:    mca_startup(0)... XXXfxrng_event_processor: source 8 'first' time
Dec 16 11:14:41 testvm kernel: done.
Dec 16 11:14:41 testvm kernel:    acpi_taskq_init(0)... XXXfxrng_event_processor: source 16 'first' time
Dec 16 11:14:41 testvm kernel: done.
...
Dec 16 11:14:41 testvm kernel: subsystem fffffff
...
Dec 16 11:14:41 testvm kernel:    oktousecallout(0)... done.
Dec 16 11:14:41 testvm kernel: XXXfxrng_event_processor: source 9 'first' time
Dec 16 11:14:41 testvm kernel: XXXfxent_timer_reseed_npools: Bumping generation due to timer reseed
Dec 16 11:14:41 testvm kernel: XXXfxent_timer_reseed: Did 1 sec reseed, queued the next in 3 sec.
...
Dec 16 11:14:41 testvm kernel: vtrnd0: <VirtIO Entropy Adapter> on virtio_pci0
Dec 16 11:14:41 testvm kernel: random: registering fast source VirtIO Entropy Adapter
Dec 16 11:14:41 testvm kernel: XXXfxrng_event_processor: source 19 'first' time
...
Dec 16 11:14:41 testvm kernel: XXXfxent_timer_reseed_npools: Bumping generation due to timer reseed
Dec 16 11:14:41 testvm kernel: XXXfxent_timer_reseed: Did 3 sec reseed, queued the next in 9 sec.
Dec 16 11:14:50 testvm kernel: XXXfxent_timer_reseed_npools: Bumping generation due to timer reseed
Dec 16 11:14:50 testvm kernel: XXXfxent_timer_reseed: Did 9 sec reseed, queued the next in 27 sec.
Dec 16 11:15:10 testvm arc4random_test_long[558]: XXX_rs_forkdetect: reseeding due to seed version 8 != 10
Dec 16 11:15:17 testvm kernel: XXXfxent_timer_reseed_npools: Bumping generation due to timer reseed
Dec 16 11:15:17 testvm kernel: XXXfxent_timer_reseed: Did 27 sec reseed, queued the next in 81 sec.
Dec 16 11:15:40 testvm arc4random_test_long[558]: XXX_rs_forkdetect: reseeding due to seed version 10 != 11
Dec 16 11:16:38 testvm kernel: XXXfxent_timer_reseed_npools: Bumping generation due to timer reseed
Dec 16 11:16:38 testvm kernel: XXXfxent_timer_reseed: Did 81 sec reseed, queued the next in 243 sec.
Dec 16 11:16:41 testvm arc4random_test_long[558]: XXX_rs_forkdetect: reseeding due to seed version 11 != 12
Dec 16 11:20:41 testvm kernel: XXXfxent_timer_reseed_npools: Bumping generation due to timer reseed
Dec 16 11:20:41 testvm kernel: XXXfxent_timer_reseed: Did 243 sec reseed, queued the next in 729 sec.
Dec 16 11:20:41 testvm arc4random_test_long[558]: XXX_rs_forkdetect: reseeding due to seed version 12 != 13
Dec 16 11:32:50 testvm kernel: XXXfxent_timer_reseed_npools: Bumping generation due to timer reseed
Dec 16 11:32:50 testvm kernel: XXXfxent_timer_reseed: Did 729 sec reseed, queued the next in 2187 sec.
Dec 16 11:33:13 testvm arc4random_test_long[558]: XXX_rs_forkdetect: reseeding due to seed version 13 != 14

Parallelism (INVARIANTS kernel and bhyve hypervisor running on an idle CPU with single core boost > multi-core boost, so take the actual numbers with a grain of salt):

testvm# ./bench_getrandom 1m
^C
1143 MiB read 432 MiB/s
testvm# for i in $(jot $(sysctl -n hw.ncpu)) ; do ./bench_getrandom 1m & ; done
[2] 774
[3] 775
[4] 776
[5] 777
testvm# killall -INFO bench_getrandom
5519 MiB read 404 MiB/s
5611 MiB read 411 MiB/s
5515 MiB read 404 MiB/s
5513 MiB read 404 MiB/s

testvm# ps auxwwww | grep rand
USER PID  %CPU %MEM    VSZ  RSS TT  STAT STARTED      TIME COMMAND
root 774 100.0  0.7  11920 3276 u0  RN   11:46     1:13.16 ./bench_getrandom 1m
root 775 100.0  0.7  11920 3276 u0  RN   11:46     1:13.17 ./bench_getrandom 1m
root 776 100.0  0.7  11920 3276 u0  RN   11:46     1:13.18 ./bench_getrandom 1m
root 777 100.0  0.7  11920 3276 u0  RN   11:46     1:13.10 ./bench_getrandom 1m
root  18   0.0  0.0      0   16  -  DL   11:14     0:01.49 [rand_harvestq]
# Note minimal CPU time in rand_harvestq; system is still responsive

[cem]

Rebase over recent random(4) API changes; no functional change intended.

[cem]

I would like to land this soon, default off, for slightly wider consumption. Does anyone have any objection to the change going in disabled? There should be no functional change.

[markm]

I'm happy to see this landed in disabled form.