On Sun, Oct 11, 2015 at 08:16:01PM -0400, George Spelvin wrote: > > I'm not thrilled with incrementing the pointer from i to len, but mixing > at positions i+k to i+k+len. The whole LFSR scheme relies on a regular > pass structure.
That part I'm not worried about. We still have a regular pass structure --- since for each CPU, we are still iterating over the pool in a regular fashion. > How about this instead: drop the hashed offset, and instead let each > writer do an atomic_add_return on the index, then iterate over the > "reserved" slots. Concurrent additions will at least do non-overlapping > writes until the numer equals the pool size. One atomic operation per byte that we're mixing in? That's quite expensive. > Personally, I hate the input_rotate. It's not that it's harmful, just > that it doesn't do much good compared to the cost; for the number of cycles > and context space required there are more efficient mixing operations. The input_rotate is useful for the input pool, for things like keyboard code so we can make sure they enter the pool at more points than just the low bits of each word. But for the output pools, it really doesn't make any sense. And we are getting to the point where we may end up having different mixing algorithms for the nonblocking pool, and in that case I have absolutely no trouble dropping the input_rotate part of the mixing algorithm for the non-blocking pool. > Or a small machine with a couple of concurrent /dev/urandom abusers. > Remember, it's globally readable, so it has to be resistance to malicious > abuse. One of the other ways we could solve this is by hanging a struct off the task structure, and if we detect that we have a /dev/urandom abuser, we give that process its own urandom pool, so any pissing that it does will be in its own pool. (So to speak.) Most processes don't actually use that much randomness, and I'm not that worried about in-kernel users of the nonblocking pool. Even with the most exec-heavy workload, setting up a new exec image is heavyweight enough that you're really not going to be contending on the lock. I also have trouble with someone spending $$$$ on a system with 1K cpu cores and wasting all of their CPU power with running shell scripts that fork and exec a lot. :-) The reality is that most processes don't use /dev/urandom or getrandom(2) at all, and those that do, many of them only use it sparingly. So maybe the right answer is to do something simple which takes care of the abusers. > You can add rather than XOR, and we have atomic add primitives. Atomic-add primitives aren't portable either. The representation isn't guaranteed to be 32-bits, and some platforms an atomic int is only 24-bits wide (the top 8 bits being used for locking purposes). > There are several possible solutions that don't need separate pools > (including separate add-back pools, with a shared seeded pool that > is never touched by add-back), so I don't think it's necessary to > give up yet. Hmm, maybe. I'm a bit worried about the amount of complexity that this entails, and the reality is that the urandom pool or pools don't provide anything other than cryptogaphic randomness. At this point, I wonder if it might not be simpler to restrict the current nonblocking pool to kernel users, and for userspace users, the first time a process reads from /dev/urandom or calls getrandom(2), we create for them a ChaCha20 CRNG, which hangs off of the task structure. This would require about 72 bytes of state per process, but normally very few processes are reading from /dev/urandom or calling getrandom(2) from userspace. The CRNG would be initialized from the non-blocking pool, and is reseeded after, say, 2**24 cranks or five minutes. It's essentially an OpenBSD-style arc4random in the kernel. (Arguably the right answer is to put arc4random in libc, where it can automatically handle forks/clones/pthread automatically, but it seems pretty clear *that* train has left a long time ago.) I have a feeling this may be less code and complexity, and it nicely handles the case where we have a /dev/urandom abuser who feels that they want to call /dev/urandom in a tight loop, even on a 4 socket Xeon system. :-) - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/