Make arc4random() depend on less subsystems by decoupling extract_entropy()
from the enqueue_randomness() logic.

Add add_event_data() which just enqueues some data into the event buffer
which can be used by extract_entropy(). On top of this remove the
timeout_del() call in dequeue_randomness() it does serve any meaningful
reason.
OK kettenis@ deraadt@ mpi@

In dequeue_randomness() use an atomic instruction to increase the
rnd_event_cons. This way even concurrent calls to dequeue_randomness()
will use some different events.
OK deraadt@ djm@

Delete obsolete /* ARGSUSED */ lint comments.

ok miod@ millert@

Style: always use *retval and never retval[0] in syscalls,
to reflect that retval is just a single return value.

ok miod@

Make comment match the code.

Since rnd.c r1.127, there is only one stirring polynomial.

s/poll/pool

ansi

slight copyright update regarding recent work

introduce "cpu_rnd_messybits" for use instead of nanotime in dev/rnd.c.

rnd.c uses nanotime to get access to some bits that change quickly
between events that it can mix into the entropy pool. it doesn't
use nanotime to get a monotonically increasing set or ordered and
accurate timestamps, it just wants something with bits that change.

there's been discussions for years about letting rnd use a clock
that's super fast to read, but not necessarily accurate, but it
wasn't until recently that i figured out it wasn't interested in
time at all, so things like keeping a fast clock coherent between
cpu cores or correct according to ntp is unecessary. this means we
can just let rnd read the cycle counters on cpus and things will
be fine. cpus with cycle counters that vary in their speed and
arent kept consistent between cores may even be desirable in this
context.

so this is the first step in converting rnd.c to reading cycle
counter. it copies the nanotime backend to each arch, and they can
replace it with something MD as a second step later on.

djm@ suggested rnd_messybytes, but we landed on cpu_rnd_messybits.
thanks to visa for his eyes.
ok deraadt@ visa@
deraadt@ says he will help handle any MD fallout that occurs.

dev/rndvar.h no longer has statistical interfaces (removed during various
conversion steps). it only contains kernel prototypes for 4 interfaces,
all of which legitimately belong in sys/systm.h, which are already included
by all enqueue_randomness() users.

3 includes not needed

Update comment block at the top to describe (a) the ring damage logic,
and (b) the boot-time acceleration.

Rewrite the entropy enqueue ring to collect damage asyncronously, and adapt the
dequeue to mix a selection of "best" ring entries. Change the dequeue timeout
to exponentially backoff because excessive pool buffer generation is pointless
-- rekey's generally happen at 1.6MB and a long timeout, a lot of cpu cycles
were being wasted.

During boot-up (before timeouts work) aggressively consume enqueue damage
and rekey every time, to accelerate entropy injection into the chacha ring.

The goal is to compensate rapidly for weak seeding in unidentifiable
conditions, and ensure quality to arc4random() calls early in boot.
ok kettenis visa

For large reads from /dev/random, use the arc4random_ctx_*() functions
instead of hand-rolling the same code to set up a temporary ChaCha
instance.
tweak/ok semarie@, ok deraadt@

Pass bootblock indicator RB_GOODRANDOM to random_start(). Future work
will frantically compensate.
ok kettenis

During the rekey operation, we feedback 1 word to the lowest level.
But it was a constant, that is really silly. Pass back the first
word from the middle layer.
ok visa

entropy_add_ptr and entropy_input_rotate are only used inside
enqueue_randomness(), so make them local static instead of global.

be more consistant about with using sizeof(object) rather than the constant
defining the [size]

Describe the purpose of add_entropy_words() in simpler terms.

The description of the enqueue_randomness() input parameter was crazy untrue.

Explain enqueue_randomness() better. It is the supply-entropy function,
and change wording from 'entropy queue', what we have is a ring which
collects 'damage' from successive calls until drawn down

The long explanation for CRC stirring isn't helping. If anything
it suggests we should reconsider this mechanism and do something
simpler... delete the explanation for now.

The main comment block from 1996 has become highly inaccurate and
misleading, so rewrite it.

The interesting parts are bootblock-seeding from file + hwrng,
arc4random() being available incredibly early, and seperate timeouts
to pull entropy data forward into a stir of the chacha state (one for
entropy ring crc whitening into a buffer, the 2nd for buffer folding
into the chacha)

Now that it is better documented, I can try to improve each component.

remove unneccessary include files

Make sure 'ts' is initialized.

ok deraadt@

previous commit accidentally aliased two unique timeouts
hit by millert

rename functions and types unrelated to the higher-level arc4 API
ok djm markus

Replace field f_isfd with field f_flags in struct filterops to allow
adding more filter properties without cluttering the struct.

OK mpi@, anton@

Use C99 designated initializers with struct filterops. In addition,
make the structs const so that the data are put in .rodata.

OK mpi@, deraadt@, anton@, bluhm@

replace add_*_randomness with enqueue_randomness()

this gets rid of the source annotation which doesn't really add
anything other than adding complexitiy. randomess is generally
good enough that the few extra bits that the source type would
add are not worth it.

ok mikeb@ deraadt@

Situation occur where bootloader cannot supply kernel with early
random data. But a new source of entropy arrived a few months ago
-- KARL generates highly disturbed images for some kernels (well,
not for bsd.rd)
This assumes the tail of text (just before etext[]) is readable.
We are trying to use a portable symbol name, and also avoid reading
a locore0 which has been unmapped...
ok mortimer

Do not hardcode key length. Pointed out by jsing@

ok deraadt@

Use a temporary chacha instance to fill large randomdata sections. Avoids
grabbing the rnglock repeatedly.

ok deraadt@ djm@

Don't mention XOR as a mix-in function since addition is done since 1.180

Remove interlocks between producers and consumers of randomness data

A lot of randomness event producers are executed in the interrupt
context increasing the time spent in the interrupt handler resulting
in extra costs when adding randomness data to the pool. However, in
practice randomness event producers require interlocking between each
other, but not with with consumers due to the opportunistic nature of
event consumers.

To be able to take advantage of this idea, the ring buffer indexing
is now done with two free running producer and consumer counters modulo
power of 2 size of the ring buffer.

With input from and OK visa, tb, jasper

clang (and newer gcc at high -O) are unaware that objects placed in strange
sections, such as __attribute__((section(".openbsd.randomdata"))), may be
non-zero. In combination with "const" or "static" the compiler becomes even
more sure nothing can influence the object and assumes the value will be 0.
A few optimizations later, a security requirement has been removed.

Until a better annotation arrives in compilers, be warned: Do not mix
const or static with these random objects, you won't get what you want.
Spotted in a regression test by bluhm, long discussion with kettenis.

spelling and whitespace

fix spelling errors and typos, from Michael W. Bombardieri

when openbsd.randomdata was made readonly, the proto seed copy got done
too late, leading to poor rng in the kernel early on. a behavioural
artifact in vmm spotted the issue.
ok tedu guenther mlarkin

another unused variable bites the dust. spotted by deraadt

the old time delta code is no longer used. nothing reads these values.
remove it another relic of the superstitious past.
ok deraadt millert mikeb

kern.arandom no longer exists
from rob pierce

Stop pushing version & cfdata into as entropy, since the contents are
known and we rely on the bootpath to prime us anyways.
This also solves the issue raised by kettenis, of version potentially
being non-word aligned
ok kettenis djm

Rototil the _rs_clearseed() function once more such that we don't map pages
beyond the end of .text/.rodata.

ok deraadt@

Since the initial entropy pool is 8192 bytes, we need three pages to create
the alias mapping when clearing it, since there is no guarantee the pool is
page aligned.

ok deraadt@

openbsd.randomdata became RO in userland due to the RELRO work. We should
also do so in the kernel, which gains us RO ssp cookie, which will prevent
spraying attacks.

The random layer was openbsd.randomdata annotating working entropy/chacha
buffers which in turn required them to be RW. To make that work again,
so we need to copy RO seeds to RW working buffers, and later clear the
RO seed buffers afterwards using a temporary RW mapping.

help & ok kettenis, ok guenther

Remove unused re_nbits from dev/rnd.c

"another leftover of the bean counter"

od tedu@ deraadt@

remove the sysctl kern.random counters, since none of the remaining
ones are capable of giving valuable works vs does-not-work evidence.
ok tedu

Change the random event buffer from a queue to an endless ring. This way
we don't drop any events when the queue is full. They are instead mixed
into previous events.
The mixing function selected is addition instead of xor to reduce the
possibility that new values effectively erase existing ones.
Convert some types to u_int to ensure defined overflow.
ok deraadt djm

Right shift by an amount larger than width of type is undefined behavior.
Pointed out by Martin Natano, slightly tweaked by me.

ok deraadt@

Use uiomove() instead of uiomovei().
Diff from Martin Natano, thanks!

ok kettenis@, deraadt@

use ulmin when looking at uio_resid to prevent wrapping around.
from Martin Natano (and also reported by Stefan Kempf)

Sync chacha_ivsetup to the version in ssh so that we could
specify custom counter value when setting up Chacha context.

ok reyk djm

missing word in comment; Kyle Milz

use the size of the buffer not the pointer in resume_randomness()
ok djm@ miod@ deraadt@

Remove some includes include-what-you-use claims don't
have any direct symbols used. Tested for indirect use by compiling
amd64/i386/sparc64 kernels.

ok tedu@ deraadt@

the rnd event ringbuf calculations aren't correct, which may result in
failure to fire the collection timeout. discovered by markus.
the order of events here doesn't actually matter, so switch to a simple
stack, which is easier to understand. ok markus

First step towards making uiomove() take a size_t size argument:
- rename uiomove() to uiomovei() and update all its users.
- introduce uiomove(), which is similar to uiomovei() but with a size_t.
- rewrite uiomovei() as an uiomove() wrapper.
ok kettenis@

New framework that allows hibernate to pass in entropy from it's fresh
boot.
ok mlarkin

remove the second void * argument on tasks.

when workqs were introduced, we provided a second argument so you
could pass a thing and some context to work on it in. there were
very few things that took advantage of the second argument, so when
i introduced pools i suggested removing it. since tasks were meant
to replace workqs, it was requested that we keep the second argument
to make porting from workqs to tasks easier.

now that workqs are gone, i had a look at the use of the second
argument again and found only one good use of it (vdsp(4) on sparc64
if you're interested) and a tiny handful of questionable uses. the
vast majority of tasks only used a single argument. i have since
modified all tasks that used two args to only use one, so now we
can remove the second argument.

so this is a mechanical change. all tasks only passed NULL as their
second argument, so we can just remove it.

ok krw@

not necessary to zero hash context; the hash final functions all do that.

tmp is a bad name for a shactx

rename buffer to digest, more clear. ok deraadt

sha512 produces enough output, we can simplify extraction by not looping.
ok deraadt djm

Create a suspend/resume infrastructure for the RNG. At suspend time,
process all queued entropy and create a brand new pool to prevent
backtracking upon resume. At resume time, process the entropy queue
(since other resume code paths which run earlier can enqueue entropy)
and force all higher to reseed.
ok reyk djm

obvious sizes for free

typo; deraadt

use SHA512 to hash entropy instead of MD5

update comments to reflect chacha20. from Max Fillinger

zero entropy buf

add a size argument to free. will be used soon, but for now default to 0.
after discussions with beck deraadt kettenis.

Change return value of getentropy() to int 0 for success. Maximum
buffersize is enforced strictly, this supplies sufficient entropy
payload to act as seed material. Discourage general use of this
API, but lock down this function name as the go-to for userland
PRNG seeding. Improve documentation.
ok miod matthew

Add new getentropy() system call. Code and pressure from matthew.
I accepted that he's right (again) to seperate this out from heavy
sysctl API and this will simply a variety of things. Functionname
is not used by anyone in the ports tree, so we guess we can use it.
Shocking that no application has a function called this.
ok matthew & others who pushed him to start this early on

tiny style adjustments

Emit a warning if no entropy was supplied by the boot loader.

ok deraadt@

Refactor rnd startup so arc4random/arc4random_buf can create a chacha state
on first call, very early on, from boot-supplied entropy, then feed from
that. Later when we have more subsystems ready, the main() can properly
initialize the entropy-driven model. Lots of discussion with mikeb.
ok kettenis markus mikeb

With the earlier initialization of the random subsystem, random_hostseed()
is no longer providing significant value. The random subsystem is in
pretty good state, and moments later userland will feed the dmesg.
ok jsing

In random_start() we can assume the msg buffer is mapped, all systems do
it at startup, or in cpu_startup(). Improve comments to explain what is
happening here.
ok kettenis jsing

Put the entropy_pool[] into the ELF .openbsd.randomdata segment.
Also allow random_init() to be called later, by moving a few
entropy control initializions into the lower-level _rs_seed() layer.
tested by jsing, phessler and a few others

spacing; Loganaden Velvindron

Revert change to sha256: ramdisks don't build with this and the obvious
conf/files change isn't enough due to size limits

update a few RC4 references to ChaCha. thanks sthen

md5 smells bad. switch to sha256. ok deraadt matthew mikeb

replace rc4 with ChaCha20 here, too; ok djm, tedu, deraadt

replace workq_add_task with the task api.

this guarantees the reliability of the arc4_reinit task being run by not
relying on a pool to give us memory in an interrupt context.

ok mpi@

Fix a pair of aesthetic nits in dev/rnd.c:

fix language (feed -> fed) in a comment
16 -> MD5_DIGEST_LENGTH for legibility

No change to resulting object file.

ok djm@

reseed the random pool with 'dmesg' when more devices are attached
from hshoexer@; ok tedu@, "looks good" deraadt@

Change arc4random_uniform() to calculate ``2**32 % upper_bound'' as
``-upper_bound % upper_bound''. Simplifies the code and makes it the
same on both ILP32 and LP64 architectures, and also slightly faster on
LP64 architectures by using a 32-bit remainder instead of a 64-bit
remainder.

Pointed out by Jorden Verwer on tech@
ok deraadt; no objections from djm or otto

Add a new kqfilter for random which returns ARC4_MAIN_MAX_BYTES for read
and POOLBYTES for write.

looks right to deraadt

bring back carrying over state from the previous RC4 instance when
rekeying; ok deraadt@

all the bzeros in rnd are important, use explicit_bzero

update the documentation regarding the *4 vs *6 decision for early RC4
stream discard. this continues to be under discussion... at least this
moves the large-buffer transactions to using a *6 discard
discussed at length with djm and kjell

move comment block regarding ARC4_MAIN_MAX_BYTES

randomread does its own rekeying now, so we don't need the large buf function.
ok deraadt

OK, this is getting silly, but we might as well zero the entropy buffer
supplied by root (it can be large enough to overwhelm the entropy buffer,
and we are doing a re-key almost immediately)

zero another intermediate key storage area

be more careful with nanotime() calls in early entropy storage, since
at least sparc may not have the clock mapped (found by miod).
while here, protect some more timeout_*() calls with timeout_initialized()

split randomattach into random_init() and random_start(), so that we
can make attempts to load 'entropy' into the RC4.
ok miod ariane

spaces

switch back from PAGE_SIZE for the sake of sparc

destatic. ok deraadt

some minor improvements to rnd.
1. only support pool words == 2048.
2. define the amount of key we use.
3. define the amount of rc4 we skip.
4. use arc4random_buf instead of reimplementing inline.
5. bzero some more "secrets".
ok deraadt djm

substantial rewrite. put a very thin mutex at the entropy-collection
side so that entropy events can come in from any kernel context. place
a 2nd very thin mutex at the call-down path as well, so that any context can
request random data. in the middle, meet with a bcopy that has no mutex,
but copying unlocked data is actually a benefit.
move the pool->MD5->RC4init sequence into a workq driven from a timeout,
so that we can do all the heavy work without any mutex held or IPL; only
grab the 2nd mutex to swap to a new RC4 state. (this workq design from tedu)
ok dlg tedu

since randomwrite() also has no blocking operations at all, we need to
do a yield, otherwise an accidental cat by root into /dev/random kind
of makes your machine hurt a lot.

For very large operations in randomread(), use a local rc4 instance
much like arc4random_buf_large does, but without re-initializing it
every 8K.
ok tedu

make all /dev/*random nodes respond; in fact, don't even worry about
the minor number at all. The chances of an application ignoring the
error on /dev/random are *greater* than the risk of an application
getting bad data from it.
ok dlg tedu kjell

in arc4_stir() only grab 64 bytes from the MD5 output. Grabbing more
does not substantially increase the quality of the RC4 state. These
days we may have lots more userland libc's initializing themselves,
or lots of largebuf kernel calls which re-initialize their own RC4,
and thus deplete the MD5 more than originally intended.
discussed at length with tedu, djm, kjell and kettenis
ok kettenis

Do not fold the MD5 in half. This might have made sense to someone when
we were feeding the MD5 output direct to consumers, but now we only feed
the RC4, so the effect is to throw away half of the stretched data.
ok tedu djm, initial discussion started by kjell

comment cleanup

make randomattach do the parts of it's job in the right order, then move
it to where it belongs

cleanup the ioctl function

delete includes we do not need

further improvements describing what we are doing

all random nodes have been arc4-based for a while, so none of them ever
block. the kq and poll code should have been replaced with "selltrue"
type code a while ago.
with and ok nicm

be more cynical about boot-time entropy, and fold time and entropy data in.
ok djm

knf

Since there is only one random_state, we can access it directly without
the rs-> song and dance. Exactly the same diff was written by djm.

arc4random_count is not used; other things inside rndstats do the accounting

the rnd_debug stuff was not useful

kill RND_ARND_OLD, and decrease RND_NODEV to account for it; ok djm

Remove the get_random_bytes() API.
ok kjell djm

the random ioctl stuff is not very useful. I want to see all the
non-essential parts of rnd.c removed so that we can keep our eye on
what the code should be doing.
ok tedu who had a similar diff in the past

try to update the monster comment at the top of this file to explain
what it is we are doing
ok djm

rewrite randomwrite() for clarity after discussion with mikeb
ok djm

adding timer randomness in ioctl doesn't really help and looks suspicious.
ok deraadt

remove support for srandom and urandom. direct everyone to arandom instead.
we do this to prevent people from opening a device that sounds good, but
doesn't have the properties they really need.
ok deraadt

remove proc.h include from uvm_map.h. This has far reaching effects, as
sysctl.h was reliant on this particular include, and many drivers included
sysctl.h unnecessarily. remove sysctl.h or add proc.h as needed.
ok deraadt

Every selwakeup() should have a matching KNOTE() (even if kqueue isn't
supported it doesn't do any harm), so put the KNOTE() in selwakeup() itself and
remove it from any occurences where both are used, except one for kqueue itself
and one in sys_pipe.c (where the selwakeup is under a PIPE_SEL flag).

Based on a diff from tedu.

ok deraadt

Sanity check: we overrun the rnd_ed[] array if nbits is 32, but that
should be impossible given the multi-order delta logic

ok deraadt@

remove i386-only inline assembler roll() function; gcc optimises the
equivalent C code into a rol instruction anyway (confirmed with
objdump -d); "nuke it" weingart@

extra decl not needed; spotted by djm

allow entropy to be queued before randomattach() is called
worked on with djm

Seed the random pool with the dmesg buffer at randomattach().
This lets early arc4random() calls to return at least non-uniqe values
on different machines. The dmesg will have different MAC addresses,
etc. Also ignore the entropy count in arc4_stir, and just take what's
there. sizeof(struct timeval) should be sizof(struct timespec)
This was forgotten when we switched to nanotime.
With help from mickey.
OK djm@, deraadt@

kernel/5592: yield() between copying out large chunks of random data to
userspace - mitigates an effective DoS since generating these can hog
the CPU at splhigh()

feedback & ok tedu@ deraadt@

minor 3 was /dev/prandom, which used random(). make that use the
arandom code, just like minor 4. in fact, make them act exactly
the same.

Convert timeout_add() calls using multiples of hz to timeout_add_sec()

Really just the low-hanging fruit of (hopefully) forthcoming timeout
conversions.

ok art@, krw@

correct long since bitrotted comments

POOL_TAP5 is always 1 so unifdef it

no binary change

reorder functions and variables in rnd.c so they are more logically
arranged. They are now layed out in four sections:

1. Master entropy pool maintenance (add_entropy_words & extract entropy)
2. Entropy crediting (add_*_randomness backend)
3. Exported kernel API: arc4random() and friends
4. /dev/*random char devices

simplify math for arc4random_uniform() suggested by
Jinmei_Tatuya AT isc.org via jakob@

empirically verified for entire domain of upper_bound

rename arc4random_bytes => arc4random_buf to match libc's nicer name;
ok deraadt@

fix math screwup that reintroduced a bias for upper_bounds in range
(2^30,2^31). Nothing in the tree yet requests random numbers bounded
by this range.

report jakob!deraadt; ok deraadt@

Add a arc4random_uniform() that returns a uniformly distributed number
in the range 0 <= x < upper_bound

Please use this new API instead of "arc4random() % upper_bound", as it
avoids the "modulo bias" that favours small results when upper_bound is
not a power of two.

feedback deraadt@ mcbride@; ok deraadt@

switch from spls to mutexes for protecting the random state.

ok tedu@ djm@

zero the right object, not some hunk of stack; ok henric@

Switch arc4random to using routines from crypto/arc4.[ch], and rework
spl swizzling so we go to splhigh and back once per request instead of
once per byte.
Service large requests for arc4random_bytes using an independently keyed
generator rather than hogging the main one (at splhigh).
feedback from henric@; ok deraadt@

MALLOC -> malloc

ok krw@

ansify/de-register

ok miod@

``it's'' -> ``its'' when the grammar gods require this change.

make this use nanotime, not microtime; ok mickey@

use monotonic time for repeat event detections; feedback and ok deraadt@

fix accounting bug on extraction - we were incorrectly subtracting many times
the amount requested from the pool's entropy estimate; ok mickey@ deraadt@

De-inline a couple of long functions, which also makes them debugger-visible. 'makes sense' mickey@

Fix a variable name in a comment; from Clint <cruoho@gmail.com>; ok tdeval@

poll can ever deny reads for srandom only; millert@ ok

In randompoll() the write check was overriding the results of the read check.
OK mickey@

branches: 1.73.2;
remove a few inlines from funcs that are used more than once and make code bigger; asked by art@

use MALLOC/FREE for fixed size buffer allocations

Allocate buffers in randomread and randomwrite via malloc instead
of from the stack. Keeps us from running out of kernel stack during
stack-heavy networking load. The bug manifests as a panic during
bootup with an fpu-related assertion failure on i386.
Fix from Christopher Pascoe; commit requested by deraadt@

Replace RSA-derived md5 code with code derived from Colin Plumb's PD version.
This moves md5.c out of libkern and into sys/crypto where it belongs (as
requested by markus@). Note that md5.c is still mandatory (dev/rnd.c uses it).
Verified with IPsec + hmac-md5 and tcp md5sig. OK henning@ and hshoexer@

repair linuxisms tested on hppa, sparc, vax and i386; from Sven Dehmlow <sven_dehmlow@gmx.de>

kill _8 api completely

branches: 1.67.2;
per popular demand panic on premature arc4 initializations (would have paniced anyway elsewhere)

add arc4random_bytes. input ok mickey@

typos from Tom Cosgrove;

Replace select backends with poll backends. selscan() and pollscan()
now call the poll backend. With this change we implement greater
poll(2) functionality instead of emulating it via the select backend.
Adapted from NetBSD and including some changes from FreeBSD.
Tested by many, deraadt@ OK

branches: 1.63.2;
change arguments to suser. suser now takes the process, and a flags
argument. old cred only calls user suser_ucred. this will allow future
work to more flexibly implement the idea of a root process. looks like
something i saw in freebsd, but a little different.
use of suser_ucred vs suser in file system code should be looked at again,
for the moment semantics remain unchanged.
review and input from art@ testing and further review miod@

protect the arc4_getbyte() w/ an splhigh since
there by multiple pathways, where it worked
until read from userland in big buffers and some luck.
does not cause a memory trashing, but rather may
mess up the arc4 state such that it will not generate
one particular value until a stir. sigh.
was reported by multiple people over some time.

grammar fixens from Andrey Smagin

add kqfilter for random, regress is coming

from freebsd:
Throw away the first N words of output, as suggested in the
paper "Weaknesses in the Key Scheduling Algorithm of RC4"
by Fluher, Mantin, and Shamir. (N = 256 in our case.)

kill unused arc4random_8() API

a few typos from pechkin

on extract: better spl granularity, make sure pool is updated between runs; later pt out by camield@

First round of __P removal in sys

drop the low drop bits number to 10 drop

return ENOTTY not EINVAL in default: in *ioctl()

Restore entropy_count calculation. mickey@ ok

finer spl granularity, allowing ints to happen; pointed out and tested on vax by hugh@

branches: 1.50.4;
there was a possible overrun in prev folding length fix.
however i was lucky enough so it worked.
anyway, this fixes the problem and seems to run very
much alright on sparc at least.

oops, fix the after folding sizes

only run timeout if stirring happened, save cycles for mass energy conservation

reapply 1.39 once again, it seems i've fixed two bugs in it and it
works ok on sparc and i386 now.

advance through buffer, leftovers from singular version; from Henric Jungheim <henric@aimnet.com>

branches: 1.45.2;
oops; deraadt@ ok

fix ioctls; pointed out by Pawel Krawczyk <http://ceti.pl/~kravietz/>

fix indentation from 1.41 addition

do not call arc4_stir() on pool overflow.
calling it would hit perfomance in two evil ways,
by delaying queue processing and hitting on arc4
quality. basic idea was expressed by dm@ some time ago
when we were investigating poor arc4 quality.
then, numbers showed how badly it hits on us.

Support FIONBIO and FIOASYNC. FIOASYNC is more or less a no-op>

undo latest problem. breaks the sparc. diff is too large, we are not debugging it for you

replace linked lists for event queue with circular buffer,
which gives two advantages -- faster and smaller.
do not arc4_stir on pool overflow, it takes too much time, instead
just hash data in and keep entropy count trim.
some minor cleanups here and there.
fixes overdropping of entropy on non-idle system load.
provos@ ok

branches: 1.38.2;
Double usage of random() in the pseudo device to avoid setting
every 32nd bit to zero in the output. Checked by mickey.

this should fix the alpha; closes PR kernel/1189

better has when adding entropy to the pool.
bigger pool (4k).

add support for more random sources.
make it easy to add more in the future.
make extract_entropy() faster.
more accurate stats.

faster log2, more stats, lazy random stirring, more stats, less debug, help and ok from provos@

branches: 1.33.4;
Set j = i after arc4random key schedule to be more like arc4 stream cipher;
from conversations between various people

nbits should probably actually be initialized.

fix the types

more accounting!

now where did that patch go?

wasn't a race after all. properly initialize event_q pointers so the
last one doesn't point off the end.

revert, there's a nasty race condition here.

count properly (;

s/u_char/u_int8_t/g, where reasonable
s/\(static.*arc4_[^(]+(\)[^,)]+\([^)]*)\)/\1\2/g
less cpu load, just in case

count slow queue low entropy drops
bigger queue
use queue overflows for arc4_stir()

split the treatment of the random events
event_q by flipk@
spl fix by deraadt@
gother statistics about whole processing
use 'sysctl kern.random' to view what had happened
also fix wrong vm.psstrings description

little faster, smaller, safer

back out recent changes....

oops, clean debug flags

do the job out of the calling function's spl

no more 2(two) md5 libs in kernel!
tested for rnd(4).... should work for ip too, since it's
the copy of ip_md*.
use sys/md5k.h for protos.... std iface forever!
hurray!

Make sure arc4random gets initialized eventually.

moved init of ret in randomioctl() to better location

prevent this warning:
rnd.c:823: warning: `ret' might be used uninitialized in this function
when compiling with -Wall

Remove lots of timer_state structs as they just ate memory and only a few was
ever used. Now a single state is kept for net, tty and disk events resp.
Also, call the randomness from disk_unbusy instead of biodone, as biodone
gets a lot of virtual events (from virtual filesystems etc), and as a bonus:
feed xfer time and size into the entropy pool too.

don't count on MFS in add_blkdev_randomness

Fix prerequisite test, still need to check why NODEV bufs comes here.

random device is permanent now.

-Wall happieness

Short comment describing the origin of arc4.

cleanup and sync w/ latest Linux source.
remove keyboard randomness entry point.
make Free ppl happy, remove suspicious piece.
missed: SHA neede in libkern, why not to put aRC4 there too?

rnd -> random

Increased entropy through decreased typos.

Added arc4random and /dev/arnd.

indent nicely

Supply randomness source for the rnd device.

Update w/ the fact of MD5 presence in the libkern.a

The random data source driver itself.
Initial commit.

In dequeue_randomness() use an atomic instruction to increase the
rnd_event_cons. This way even concurrent calls to dequeue_randomness()
will use some different events.
OK deraadt@ djm@

Delete obsolete /* ARGSUSED */ lint comments.

ok miod@ millert@

Style: always use *retval and never retval[0] in syscalls,
to reflect that retval is just a single return value.

ok miod@

Make comment match the code.

Since rnd.c r1.127, there is only one stirring polynomial.

s/poll/pool

ansi

slight copyright update regarding recent work

introduce "cpu_rnd_messybits" for use instead of nanotime in dev/rnd.c.

rnd.c uses nanotime to get access to some bits that change quickly
between events that it can mix into the entropy pool. it doesn't
use nanotime to get a monotonically increasing set or ordered and
accurate timestamps, it just wants something with bits that change.

there's been discussions for years about letting rnd use a clock
that's super fast to read, but not necessarily accurate, but it
wasn't until recently that i figured out it wasn't interested in
time at all, so things like keeping a fast clock coherent between
cpu cores or correct according to ntp is unecessary. this means we
can just let rnd read the cycle counters on cpus and things will
be fine. cpus with cycle counters that vary in their speed and
arent kept consistent between cores may even be desirable in this
context.

so this is the first step in converting rnd.c to reading cycle
counter. it copies the nanotime backend to each arch, and they can
replace it with something MD as a second step later on.

djm@ suggested rnd_messybytes, but we landed on cpu_rnd_messybits.
thanks to visa for his eyes.
ok deraadt@ visa@
deraadt@ says he will help handle any MD fallout that occurs.

dev/rndvar.h no longer has statistical interfaces (removed during various
conversion steps). it only contains kernel prototypes for 4 interfaces,
all of which legitimately belong in sys/systm.h, which are already included
by all enqueue_randomness() users.

3 includes not needed

Update comment block at the top to describe (a) the ring damage logic,
and (b) the boot-time acceleration.

Rewrite the entropy enqueue ring to collect damage asyncronously, and adapt the
dequeue to mix a selection of "best" ring entries. Change the dequeue timeout
to exponentially backoff because excessive pool buffer generation is pointless
-- rekey's generally happen at 1.6MB and a long timeout, a lot of cpu cycles
were being wasted.

During boot-up (before timeouts work) aggressively consume enqueue damage
and rekey every time, to accelerate entropy injection into the chacha ring.

The goal is to compensate rapidly for weak seeding in unidentifiable
conditions, and ensure quality to arc4random() calls early in boot.
ok kettenis visa

For large reads from /dev/random, use the arc4random_ctx_*() functions
instead of hand-rolling the same code to set up a temporary ChaCha
instance.
tweak/ok semarie@, ok deraadt@

Pass bootblock indicator RB_GOODRANDOM to random_start(). Future work
will frantically compensate.
ok kettenis

During the rekey operation, we feedback 1 word to the lowest level.
But it was a constant, that is really silly. Pass back the first
word from the middle layer.
ok visa

entropy_add_ptr and entropy_input_rotate are only used inside
enqueue_randomness(), so make them local static instead of global.

be more consistant about with using sizeof(object) rather than the constant
defining the [size]

Describe the purpose of add_entropy_words() in simpler terms.

The description of the enqueue_randomness() input parameter was crazy untrue.

Explain enqueue_randomness() better. It is the supply-entropy function,
and change wording from 'entropy queue', what we have is a ring which
collects 'damage' from successive calls until drawn down

The long explanation for CRC stirring isn't helping. If anything
it suggests we should reconsider this mechanism and do something
simpler... delete the explanation for now.

The main comment block from 1996 has become highly inaccurate and
misleading, so rewrite it.

The interesting parts are bootblock-seeding from file + hwrng,
arc4random() being available incredibly early, and seperate timeouts
to pull entropy data forward into a stir of the chacha state (one for
entropy ring crc whitening into a buffer, the 2nd for buffer folding
into the chacha)

Now that it is better documented, I can try to improve each component.

remove unneccessary include files

Make sure 'ts' is initialized.

ok deraadt@

previous commit accidentally aliased two unique timeouts
hit by millert

rename functions and types unrelated to the higher-level arc4 API
ok djm markus

Replace field f_isfd with field f_flags in struct filterops to allow
adding more filter properties without cluttering the struct.

OK mpi@, anton@

Use C99 designated initializers with struct filterops. In addition,
make the structs const so that the data are put in .rodata.

OK mpi@, deraadt@, anton@, bluhm@

replace add_*_randomness with enqueue_randomness()

this gets rid of the source annotation which doesn't really add
anything other than adding complexitiy. randomess is generally
good enough that the few extra bits that the source type would
add are not worth it.

ok mikeb@ deraadt@

Situation occur where bootloader cannot supply kernel with early
random data. But a new source of entropy arrived a few months ago
-- KARL generates highly disturbed images for some kernels (well,
not for bsd.rd)
This assumes the tail of text (just before etext[]) is readable.
We are trying to use a portable symbol name, and also avoid reading
a locore0 which has been unmapped...
ok mortimer

Do not hardcode key length. Pointed out by jsing@

ok deraadt@

Use a temporary chacha instance to fill large randomdata sections. Avoids
grabbing the rnglock repeatedly.

ok deraadt@ djm@

Don't mention XOR as a mix-in function since addition is done since 1.180

Remove interlocks between producers and consumers of randomness data

A lot of randomness event producers are executed in the interrupt
context increasing the time spent in the interrupt handler resulting
in extra costs when adding randomness data to the pool. However, in
practice randomness event producers require interlocking between each
other, but not with with consumers due to the opportunistic nature of
event consumers.

To be able to take advantage of this idea, the ring buffer indexing
is now done with two free running producer and consumer counters modulo
power of 2 size of the ring buffer.

With input from and OK visa, tb, jasper

clang (and newer gcc at high -O) are unaware that objects placed in strange
sections, such as __attribute__((section(".openbsd.randomdata"))), may be
non-zero. In combination with "const" or "static" the compiler becomes even
more sure nothing can influence the object and assumes the value will be 0.
A few optimizations later, a security requirement has been removed.

Until a better annotation arrives in compilers, be warned: Do not mix
const or static with these random objects, you won't get what you want.
Spotted in a regression test by bluhm, long discussion with kettenis.

spelling and whitespace

fix spelling errors and typos, from Michael W. Bombardieri

when openbsd.randomdata was made readonly, the proto seed copy got done
too late, leading to poor rng in the kernel early on. a behavioural
artifact in vmm spotted the issue.
ok tedu guenther mlarkin

another unused variable bites the dust. spotted by deraadt

the old time delta code is no longer used. nothing reads these values.
remove it another relic of the superstitious past.
ok deraadt millert mikeb

kern.arandom no longer exists
from rob pierce

Stop pushing version & cfdata into as entropy, since the contents are
known and we rely on the bootpath to prime us anyways.
This also solves the issue raised by kettenis, of version potentially
being non-word aligned
ok kettenis djm

Rototil the _rs_clearseed() function once more such that we don't map pages
beyond the end of .text/.rodata.

ok deraadt@

Since the initial entropy pool is 8192 bytes, we need three pages to create
the alias mapping when clearing it, since there is no guarantee the pool is
page aligned.

ok deraadt@

openbsd.randomdata became RO in userland due to the RELRO work. We should
also do so in the kernel, which gains us RO ssp cookie, which will prevent
spraying attacks.

The random layer was openbsd.randomdata annotating working entropy/chacha
buffers which in turn required them to be RW. To make that work again,
so we need to copy RO seeds to RW working buffers, and later clear the
RO seed buffers afterwards using a temporary RW mapping.

help & ok kettenis, ok guenther

Remove unused re_nbits from dev/rnd.c

"another leftover of the bean counter"

od tedu@ deraadt@

remove the sysctl kern.random counters, since none of the remaining
ones are capable of giving valuable works vs does-not-work evidence.
ok tedu

Change the random event buffer from a queue to an endless ring. This way
we don't drop any events when the queue is full. They are instead mixed
into previous events.
The mixing function selected is addition instead of xor to reduce the
possibility that new values effectively erase existing ones.
Convert some types to u_int to ensure defined overflow.
ok deraadt djm

Right shift by an amount larger than width of type is undefined behavior.
Pointed out by Martin Natano, slightly tweaked by me.

ok deraadt@

Use uiomove() instead of uiomovei().
Diff from Martin Natano, thanks!

ok kettenis@, deraadt@

use ulmin when looking at uio_resid to prevent wrapping around.
from Martin Natano (and also reported by Stefan Kempf)

Sync chacha_ivsetup to the version in ssh so that we could
specify custom counter value when setting up Chacha context.

ok reyk djm

missing word in comment; Kyle Milz

use the size of the buffer not the pointer in resume_randomness()
ok djm@ miod@ deraadt@

Remove some includes include-what-you-use claims don't
have any direct symbols used. Tested for indirect use by compiling
amd64/i386/sparc64 kernels.

ok tedu@ deraadt@

the rnd event ringbuf calculations aren't correct, which may result in
failure to fire the collection timeout. discovered by markus.
the order of events here doesn't actually matter, so switch to a simple
stack, which is easier to understand. ok markus

First step towards making uiomove() take a size_t size argument:
- rename uiomove() to uiomovei() and update all its users.
- introduce uiomove(), which is similar to uiomovei() but with a size_t.
- rewrite uiomovei() as an uiomove() wrapper.
ok kettenis@

New framework that allows hibernate to pass in entropy from it's fresh
boot.
ok mlarkin

remove the second void * argument on tasks.

when workqs were introduced, we provided a second argument so you
could pass a thing and some context to work on it in. there were
very few things that took advantage of the second argument, so when
i introduced pools i suggested removing it. since tasks were meant
to replace workqs, it was requested that we keep the second argument
to make porting from workqs to tasks easier.

now that workqs are gone, i had a look at the use of the second
argument again and found only one good use of it (vdsp(4) on sparc64
if you're interested) and a tiny handful of questionable uses. the
vast majority of tasks only used a single argument. i have since
modified all tasks that used two args to only use one, so now we
can remove the second argument.

so this is a mechanical change. all tasks only passed NULL as their
second argument, so we can just remove it.

ok krw@

not necessary to zero hash context; the hash final functions all do that.

tmp is a bad name for a shactx

rename buffer to digest, more clear. ok deraadt

sha512 produces enough output, we can simplify extraction by not looping.
ok deraadt djm

Create a suspend/resume infrastructure for the RNG. At suspend time,
process all queued entropy and create a brand new pool to prevent
backtracking upon resume. At resume time, process the entropy queue
(since other resume code paths which run earlier can enqueue entropy)
and force all higher to reseed.
ok reyk djm

obvious sizes for free

typo; deraadt

use SHA512 to hash entropy instead of MD5

update comments to reflect chacha20. from Max Fillinger

zero entropy buf

add a size argument to free. will be used soon, but for now default to 0.
after discussions with beck deraadt kettenis.

Change return value of getentropy() to int 0 for success. Maximum
buffersize is enforced strictly, this supplies sufficient entropy
payload to act as seed material. Discourage general use of this
API, but lock down this function name as the go-to for userland
PRNG seeding. Improve documentation.
ok miod matthew

Add new getentropy() system call. Code and pressure from matthew.
I accepted that he's right (again) to seperate this out from heavy
sysctl API and this will simply a variety of things. Functionname
is not used by anyone in the ports tree, so we guess we can use it.
Shocking that no application has a function called this.
ok matthew & others who pushed him to start this early on

tiny style adjustments

Emit a warning if no entropy was supplied by the boot loader.

ok deraadt@

Refactor rnd startup so arc4random/arc4random_buf can create a chacha state
on first call, very early on, from boot-supplied entropy, then feed from
that. Later when we have more subsystems ready, the main() can properly
initialize the entropy-driven model. Lots of discussion with mikeb.
ok kettenis markus mikeb

With the earlier initialization of the random subsystem, random_hostseed()
is no longer providing significant value. The random subsystem is in
pretty good state, and moments later userland will feed the dmesg.
ok jsing

In random_start() we can assume the msg buffer is mapped, all systems do
it at startup, or in cpu_startup(). Improve comments to explain what is
happening here.
ok kettenis jsing

Put the entropy_pool[] into the ELF .openbsd.randomdata segment.
Also allow random_init() to be called later, by moving a few
entropy control initializions into the lower-level _rs_seed() layer.
tested by jsing, phessler and a few others

spacing; Loganaden Velvindron

Revert change to sha256: ramdisks don't build with this and the obvious
conf/files change isn't enough due to size limits

update a few RC4 references to ChaCha. thanks sthen

md5 smells bad. switch to sha256. ok deraadt matthew mikeb

replace rc4 with ChaCha20 here, too; ok djm, tedu, deraadt

replace workq_add_task with the task api.

this guarantees the reliability of the arc4_reinit task being run by not
relying on a pool to give us memory in an interrupt context.

ok mpi@

Fix a pair of aesthetic nits in dev/rnd.c:

fix language (feed -> fed) in a comment
16 -> MD5_DIGEST_LENGTH for legibility

No change to resulting object file.

ok djm@

reseed the random pool with 'dmesg' when more devices are attached
from hshoexer@; ok tedu@, "looks good" deraadt@

Change arc4random_uniform() to calculate ``2**32 % upper_bound'' as
``-upper_bound % upper_bound''. Simplifies the code and makes it the
same on both ILP32 and LP64 architectures, and also slightly faster on
LP64 architectures by using a 32-bit remainder instead of a 64-bit
remainder.

Pointed out by Jorden Verwer on tech@
ok deraadt; no objections from djm or otto

Add a new kqfilter for random which returns ARC4_MAIN_MAX_BYTES for read
and POOLBYTES for write.

looks right to deraadt

bring back carrying over state from the previous RC4 instance when
rekeying; ok deraadt@

all the bzeros in rnd are important, use explicit_bzero

update the documentation regarding the *4 vs *6 decision for early RC4
stream discard. this continues to be under discussion... at least this
moves the large-buffer transactions to using a *6 discard
discussed at length with djm and kjell

move comment block regarding ARC4_MAIN_MAX_BYTES

randomread does its own rekeying now, so we don't need the large buf function.
ok deraadt

OK, this is getting silly, but we might as well zero the entropy buffer
supplied by root (it can be large enough to overwhelm the entropy buffer,
and we are doing a re-key almost immediately)

zero another intermediate key storage area

be more careful with nanotime() calls in early entropy storage, since
at least sparc may not have the clock mapped (found by miod).
while here, protect some more timeout_*() calls with timeout_initialized()

split randomattach into random_init() and random_start(), so that we
can make attempts to load 'entropy' into the RC4.
ok miod ariane

spaces

switch back from PAGE_SIZE for the sake of sparc

destatic. ok deraadt

some minor improvements to rnd.
1. only support pool words == 2048.
2. define the amount of key we use.
3. define the amount of rc4 we skip.
4. use arc4random_buf instead of reimplementing inline.
5. bzero some more "secrets".
ok deraadt djm

substantial rewrite. put a very thin mutex at the entropy-collection
side so that entropy events can come in from any kernel context. place
a 2nd very thin mutex at the call-down path as well, so that any context can
request random data. in the middle, meet with a bcopy that has no mutex,
but copying unlocked data is actually a benefit.
move the pool->MD5->RC4init sequence into a workq driven from a timeout,
so that we can do all the heavy work without any mutex held or IPL; only
grab the 2nd mutex to swap to a new RC4 state. (this workq design from tedu)
ok dlg tedu

since randomwrite() also has no blocking operations at all, we need to
do a yield, otherwise an accidental cat by root into /dev/random kind
of makes your machine hurt a lot.

For very large operations in randomread(), use a local rc4 instance
much like arc4random_buf_large does, but without re-initializing it
every 8K.
ok tedu

make all /dev/*random nodes respond; in fact, don't even worry about
the minor number at all. The chances of an application ignoring the
error on /dev/random are *greater* than the risk of an application
getting bad data from it.
ok dlg tedu kjell

in arc4_stir() only grab 64 bytes from the MD5 output. Grabbing more
does not substantially increase the quality of the RC4 state. These
days we may have lots more userland libc's initializing themselves,
or lots of largebuf kernel calls which re-initialize their own RC4,
and thus deplete the MD5 more than originally intended.
discussed at length with tedu, djm, kjell and kettenis
ok kettenis

Do not fold the MD5 in half. This might have made sense to someone when
we were feeding the MD5 output direct to consumers, but now we only feed
the RC4, so the effect is to throw away half of the stretched data.
ok tedu djm, initial discussion started by kjell

comment cleanup

make randomattach do the parts of it's job in the right order, then move
it to where it belongs

cleanup the ioctl function

delete includes we do not need

further improvements describing what we are doing

all random nodes have been arc4-based for a while, so none of them ever
block. the kq and poll code should have been replaced with "selltrue"
type code a while ago.
with and ok nicm

be more cynical about boot-time entropy, and fold time and entropy data in.
ok djm

knf

Since there is only one random_state, we can access it directly without
the rs-> song and dance. Exactly the same diff was written by djm.

arc4random_count is not used; other things inside rndstats do the accounting

the rnd_debug stuff was not useful

kill RND_ARND_OLD, and decrease RND_NODEV to account for it; ok djm

Remove the get_random_bytes() API.
ok kjell djm

the random ioctl stuff is not very useful. I want to see all the
non-essential parts of rnd.c removed so that we can keep our eye on
what the code should be doing.
ok tedu who had a similar diff in the past

try to update the monster comment at the top of this file to explain
what it is we are doing
ok djm

rewrite randomwrite() for clarity after discussion with mikeb
ok djm

adding timer randomness in ioctl doesn't really help and looks suspicious.
ok deraadt

remove support for srandom and urandom. direct everyone to arandom instead.
we do this to prevent people from opening a device that sounds good, but
doesn't have the properties they really need.
ok deraadt

remove proc.h include from uvm_map.h. This has far reaching effects, as
sysctl.h was reliant on this particular include, and many drivers included
sysctl.h unnecessarily. remove sysctl.h or add proc.h as needed.
ok deraadt

Every selwakeup() should have a matching KNOTE() (even if kqueue isn't
supported it doesn't do any harm), so put the KNOTE() in selwakeup() itself and
remove it from any occurences where both are used, except one for kqueue itself
and one in sys_pipe.c (where the selwakeup is under a PIPE_SEL flag).

Based on a diff from tedu.

ok deraadt

Sanity check: we overrun the rnd_ed[] array if nbits is 32, but that
should be impossible given the multi-order delta logic

ok deraadt@

remove i386-only inline assembler roll() function; gcc optimises the
equivalent C code into a rol instruction anyway (confirmed with
objdump -d); "nuke it" weingart@

extra decl not needed; spotted by djm

allow entropy to be queued before randomattach() is called
worked on with djm

Seed the random pool with the dmesg buffer at randomattach().
This lets early arc4random() calls to return at least non-uniqe values
on different machines. The dmesg will have different MAC addresses,
etc. Also ignore the entropy count in arc4_stir, and just take what's
there. sizeof(struct timeval) should be sizof(struct timespec)
This was forgotten when we switched to nanotime.
With help from mickey.
OK djm@, deraadt@

kernel/5592: yield() between copying out large chunks of random data to
userspace - mitigates an effective DoS since generating these can hog
the CPU at splhigh()

feedback & ok tedu@ deraadt@

minor 3 was /dev/prandom, which used random(). make that use the
arandom code, just like minor 4. in fact, make them act exactly
the same.

Convert timeout_add() calls using multiples of hz to timeout_add_sec()

Really just the low-hanging fruit of (hopefully) forthcoming timeout
conversions.

ok art@, krw@

correct long since bitrotted comments

POOL_TAP5 is always 1 so unifdef it

no binary change

reorder functions and variables in rnd.c so they are more logically
arranged. They are now layed out in four sections:

1. Master entropy pool maintenance (add_entropy_words & extract entropy)
2. Entropy crediting (add_*_randomness backend)
3. Exported kernel API: arc4random() and friends
4. /dev/*random char devices

simplify math for arc4random_uniform() suggested by
Jinmei_Tatuya AT isc.org via jakob@

empirically verified for entire domain of upper_bound

rename arc4random_bytes => arc4random_buf to match libc's nicer name;
ok deraadt@

fix math screwup that reintroduced a bias for upper_bounds in range
(2^30,2^31). Nothing in the tree yet requests random numbers bounded
by this range.

report jakob!deraadt; ok deraadt@

Add a arc4random_uniform() that returns a uniformly distributed number
in the range 0 <= x < upper_bound

Please use this new API instead of "arc4random() % upper_bound", as it
avoids the "modulo bias" that favours small results when upper_bound is
not a power of two.

feedback deraadt@ mcbride@; ok deraadt@

switch from spls to mutexes for protecting the random state.

ok tedu@ djm@

zero the right object, not some hunk of stack; ok henric@

Switch arc4random to using routines from crypto/arc4.[ch], and rework
spl swizzling so we go to splhigh and back once per request instead of
once per byte.
Service large requests for arc4random_bytes using an independently keyed
generator rather than hogging the main one (at splhigh).
feedback from henric@; ok deraadt@

MALLOC -> malloc

ok krw@

ansify/de-register

ok miod@

``it's'' -> ``its'' when the grammar gods require this change.

make this use nanotime, not microtime; ok mickey@

use monotonic time for repeat event detections; feedback and ok deraadt@

fix accounting bug on extraction - we were incorrectly subtracting many times
the amount requested from the pool's entropy estimate; ok mickey@ deraadt@

De-inline a couple of long functions, which also makes them debugger-visible. 'makes sense' mickey@

Fix a variable name in a comment; from Clint <cruoho@gmail.com>; ok tdeval@

poll can ever deny reads for srandom only; millert@ ok

In randompoll() the write check was overriding the results of the read check.
OK mickey@

branches: 1.73.2;
remove a few inlines from funcs that are used more than once and make code bigger; asked by art@

use MALLOC/FREE for fixed size buffer allocations

Allocate buffers in randomread and randomwrite via malloc instead
of from the stack. Keeps us from running out of kernel stack during
stack-heavy networking load. The bug manifests as a panic during
bootup with an fpu-related assertion failure on i386.
Fix from Christopher Pascoe; commit requested by deraadt@

Replace RSA-derived md5 code with code derived from Colin Plumb's PD version.
This moves md5.c out of libkern and into sys/crypto where it belongs (as
requested by markus@). Note that md5.c is still mandatory (dev/rnd.c uses it).
Verified with IPsec + hmac-md5 and tcp md5sig. OK henning@ and hshoexer@

repair linuxisms tested on hppa, sparc, vax and i386; from Sven Dehmlow <sven_dehmlow@gmx.de>

kill _8 api completely

branches: 1.67.2;
per popular demand panic on premature arc4 initializations (would have paniced anyway elsewhere)

add arc4random_bytes. input ok mickey@

typos from Tom Cosgrove;

Replace select backends with poll backends. selscan() and pollscan()
now call the poll backend. With this change we implement greater
poll(2) functionality instead of emulating it via the select backend.
Adapted from NetBSD and including some changes from FreeBSD.
Tested by many, deraadt@ OK

branches: 1.63.2;
change arguments to suser. suser now takes the process, and a flags
argument. old cred only calls user suser_ucred. this will allow future
work to more flexibly implement the idea of a root process. looks like
something i saw in freebsd, but a little different.
use of suser_ucred vs suser in file system code should be looked at again,
for the moment semantics remain unchanged.
review and input from art@ testing and further review miod@

protect the arc4_getbyte() w/ an splhigh since
there by multiple pathways, where it worked
until read from userland in big buffers and some luck.
does not cause a memory trashing, but rather may
mess up the arc4 state such that it will not generate
one particular value until a stir. sigh.
was reported by multiple people over some time.

grammar fixens from Andrey Smagin

add kqfilter for random, regress is coming

from freebsd:
Throw away the first N words of output, as suggested in the
paper "Weaknesses in the Key Scheduling Algorithm of RC4"
by Fluher, Mantin, and Shamir. (N = 256 in our case.)

kill unused arc4random_8() API

a few typos from pechkin

on extract: better spl granularity, make sure pool is updated between runs; later pt out by camield@

First round of __P removal in sys

drop the low drop bits number to 10 drop

return ENOTTY not EINVAL in default: in *ioctl()

Restore entropy_count calculation. mickey@ ok

finer spl granularity, allowing ints to happen; pointed out and tested on vax by hugh@

branches: 1.50.4;
there was a possible overrun in prev folding length fix.
however i was lucky enough so it worked.
anyway, this fixes the problem and seems to run very
much alright on sparc at least.

oops, fix the after folding sizes

only run timeout if stirring happened, save cycles for mass energy conservation

reapply 1.39 once again, it seems i've fixed two bugs in it and it
works ok on sparc and i386 now.

advance through buffer, leftovers from singular version; from Henric Jungheim <henric@aimnet.com>

branches: 1.45.2;
oops; deraadt@ ok

fix ioctls; pointed out by Pawel Krawczyk <http://ceti.pl/~kravietz/>

fix indentation from 1.41 addition

do not call arc4_stir() on pool overflow.
calling it would hit perfomance in two evil ways,
by delaying queue processing and hitting on arc4
quality. basic idea was expressed by dm@ some time ago
when we were investigating poor arc4 quality.
then, numbers showed how badly it hits on us.

Support FIONBIO and FIOASYNC. FIOASYNC is more or less a no-op>

undo latest problem. breaks the sparc. diff is too large, we are not debugging it for you

replace linked lists for event queue with circular buffer,
which gives two advantages -- faster and smaller.
do not arc4_stir on pool overflow, it takes too much time, instead
just hash data in and keep entropy count trim.
some minor cleanups here and there.
fixes overdropping of entropy on non-idle system load.
provos@ ok

branches: 1.38.2;
Double usage of random() in the pseudo device to avoid setting
every 32nd bit to zero in the output. Checked by mickey.

this should fix the alpha; closes PR kernel/1189

better has when adding entropy to the pool.
bigger pool (4k).

add support for more random sources.
make it easy to add more in the future.
make extract_entropy() faster.
more accurate stats.

faster log2, more stats, lazy random stirring, more stats, less debug, help and ok from provos@

branches: 1.33.4;
Set j = i after arc4random key schedule to be more like arc4 stream cipher;
from conversations between various people

nbits should probably actually be initialized.

fix the types

more accounting!

now where did that patch go?

wasn't a race after all. properly initialize event_q pointers so the
last one doesn't point off the end.

revert, there's a nasty race condition here.

count properly (;

s/u_char/u_int8_t/g, where reasonable
s/\(static.*arc4_[^(]+(\)[^,)]+\([^)]*)\)/\1\2/g
less cpu load, just in case

count slow queue low entropy drops
bigger queue
use queue overflows for arc4_stir()

split the treatment of the random events
event_q by flipk@
spl fix by deraadt@
gother statistics about whole processing
use 'sysctl kern.random' to view what had happened
also fix wrong vm.psstrings description

little faster, smaller, safer

back out recent changes....

oops, clean debug flags

do the job out of the calling function's spl

no more 2(two) md5 libs in kernel!
tested for rnd(4).... should work for ip too, since it's
the copy of ip_md*.
use sys/md5k.h for protos.... std iface forever!
hurray!

Make sure arc4random gets initialized eventually.

moved init of ret in randomioctl() to better location

prevent this warning:
rnd.c:823: warning: `ret' might be used uninitialized in this function
when compiling with -Wall

Remove lots of timer_state structs as they just ate memory and only a few was
ever used. Now a single state is kept for net, tty and disk events resp.
Also, call the randomness from disk_unbusy instead of biodone, as biodone
gets a lot of virtual events (from virtual filesystems etc), and as a bonus:
feed xfer time and size into the entropy pool too.

don't count on MFS in add_blkdev_randomness