Limit the harvest rate of "fast" entropy for random(4) so as not to overload the system.

[markm]

Summary

Limit the amount of "fast" entropy. We don't need nearly as much
for security, and the excess just slows things down badly.

PR: 230808
Submitted by: [e-mail], but tweeked by me
Reported by: Danilo Egea Gondolfo <[e-mail]>

Test Plan

Make the PRNG work hard while doing something intensive like "make
world". To make the PRNG work hard, do e.g.
$ dd if=/dev/random of=/dev/null bs=$((1024*1024))

[markm]

This improves things drastically from what they were. More detailed work will follow.

sys/dev/random/random_harvestq.c

220

I am aware of more improvements that can be made here, but I don't want "perfect to be the enemy of good enough".

[delphij]

sys/dev/random/random_harvestq.c

219–223

Can you add a comment to explain what was the purpose for "+ 1" here? (My guess is that it's to make sure that the code below would at least perform a read once, but it's not exactly clear to me why we would do it when read_rate is a non-zero value).

If the goal is to have a non-zero local_read_rate, it's probably a good idea to use a construction like:

local_read_rate = atomic_readandclear_32(&read_rate);
/* Perform at least one read per round */
local_read_rate = MAX(local_read_rate, 1);
/* But not exceeding RANDOM_KEYSIZE_WORDS */

instead?

[markm]

sys/dev/random/random_harvestq.c

220

The most obvious "safe" optimisation is to to remove local_read_rate altogether and always read some constant size of junk, such as RANDOM_KEYSIZE_WORDS, or possibly even 1 or 2 32-bit words.

[markm]

Address review commnts from delphij.

[cem]

I think the improvement is conservatively correct re: my reading of Fortuna, and no need to let perfect be the enemy of good for now.

sys/dev/random/random_harvestq.c

219–223

It's just a straightforward refactor of the previous +1 which was lower in the for-loop condition. This way the MIN() below can be spelled RANDOM_KEYSIZE_WORDS rather than RANDOM_KEYSIZE_WORDS - 1.

I agree it may not have purpose, but it is not really a regression in this patch ­— and this patch gives us the bulk of the improvement.

220

That optimization may not be safe for Yarrow, right? That is part of my motivation for encouraging removal of Yarrow for 12.0.

[markm]

sys/dev/random/random_harvestq.c

220

There is a better reason to deprecate Yarrow (apologies for not bringing it up before); Yarrow's authors no longer recommend its use.

[delphij]

Looks good to me. @jmg do you have any concerns if this is landed as-is?

[cem]

sys/dev/random/random_harvestq.c

220

Right. Emphasis on "part of." :-)

(I'm aware Yarrow and Fortuna share most of the same authors, and Fortuna builds on lessons learned from Yarrow. It is fresh in my mind — just read the chapter twice yesterday :-).)

[markm]

Thanks folks! Tinderbox build going, then I'll commit.

[jmg]

@delphij this is my comment copied over from https://reviews.freebsd.org/D16866?id=47165 that was unaddressed.

head/sys/dev/random/random_harvestq.c

223 ↗

(On Diff #47235)

this still results in excessive seeding. It caps the read rate to pools*8*8, or putting 64 bytes per pool in for every 4 bytes read. As most things will read a minimum of 16 bytes (128 bits), the smallest expected value for read_rate is 5 (the increment isn't a proper ceil function), or 40 bytes per pool for every read. With the number of pools, that's a lot of extra work still.

[gordon]

@markm Can you please specifically address the comment @jmg posted on this review (and it's ancestor)?

Thanks,
Gordon

[markm]

In D16873#359829, @jmg wrote:

@delphij this is my comment copied over from https://reviews.freebsd.org/D16866?id=47165 that was unaddressed.

I needed to get something that was a drastic improvement over the stats quo, and pretty quickly too. I acknowledged that it was not perfect, and could stand some tweeking. I believe I achieved that goal.

This is a "good" fix, not a "perfect" one. I will work on something closer to "perfect" when I don't need to do it in quite such a rush.

[cem]

head/sys/dev/random/random_harvestq.c

223 ↗

(On Diff #47235)

This revision is aiming for "drastic improvement," not perfection. I 100% agree that there is a lot that can still be done to improve devrandom's performance, and that should be pursued, but with this change it is less of an existential crisis.
More aggressive reductions in feeding also carry slightly higher risk than this very conservative fix.

I'd like to point to the 100 ms sleep in the random_harvestq kthread — we accumulate read rate over 100ms (or longer) intervals. Now that we're capping read rate at RANDOM_KEYSIZE_WORDS (8), we bound entropy collection at 2kB per 100 ms or 20 kB/s. This may still be excessive, but it is de minimis for something like RDRAND which can do ~500 MB/s. We're looking at savings of less than 40 microseconds per second or ~0.004% on modern amd64 hardware.

As you touched on in the other review, we would get more return from our efforts by focusing on things like better education around initial seeding.

Just my 2¢.

[jmg]

simple fix, limit local_read_rate to be 0 or 1. Even more simple that the fix that was committed.