Implement libstd HashMap seeding on OS X

[Aaron1011]

PR #683 implemented support for random number generation on Windows and (relatively recent) Linux. This was accomplished by implementing RtlGenRandom and getrandom for Windows and Linux respectively.

For OS X (and other Unix systems without getrandom), implementing random number generation is significantly more complicated. We need to implement the following:

• Calling open/openat with /dev/random and /dev/urandom
• Calling read and close on the 'file descriptor' created above.

On Linux, file descriptors appear to be assigned sequentially. However, I don't believe that anything actually guarantees this - in other words, this could potentially be considered a source of non-determinism.

[RalfJung]

Uh, yes, this will be awful.

Alternatively we could "just" grant the interpreter FS access. But of course that would break cross-execution.

[oli-obk]

In order to keep file descriptors deterministic, we can use "symbolic file descriptors" (generate a new AllocId on every open call)

[RalfJung]

What is the point, if we allow programs to open and read files they are not deterministic any more anyway?

For a given seed, we'll always assign the same file descriptors. Small changes elsewhere in the program might affect that, but the same is true for the non-determinism that we return.

[Aaron1011]

This is actually going to be really simple once rust-lang/rust#59879 is merged, since SecRandomCopyBytes is essentially the same as all of the other random-generating functions.

[etaoins]

@Aaron1011

Assuming there are no other open file descriptors the sequential allocation is guaranteed by POSIX:

The open() function shall return a file descriptor for the named file that is the lowest file descriptor not currently open for that process.

[uberjay]

This is actually going to be really simple once rust-lang/rust#59879 is merged, since SecRandomCopyBytes is essentially the same as all of the other random-generating functions.

Unfortunately it turns out that SecRandomCopyBytes was not such a great solution after all: rust-lang/rust#59879 (comment). :(

[RalfJung]

Dang. :/

There is no precedent for this, but in principle we could also patch libstd to use the miri config flag as an indication to follow the iOS code path. Then we could still rely on SecRandomCopyBytes.

[oli-obk]

I think for a bunch of these APIs we should not reproduce the platform APIs, but add some attributes to a high level function that all platforms go through and hook miri into that.

[RalfJung]

Actually, for the rand crate, SecRandomCopyBytes is being used (through https://github.com/rust-random/getrandom/blob/master/src/macos.rs). So implementing that would still help.

[RalfJung]

See #709 and rust-lang/rust#60156

[RalfJung]

Status update: libstd is moving to using the getrandom crate for seeding HashMap. That would unify that code path with what the rand crate uses. Currently getrandom works on macOS in Miri because they use SecRandomCopyBytes, but that has been causing problems and they are still discussing what to do on macOS.

[RalfJung]

The current plan for getrandom seems to be to use the getentropy syscall, loaded via dlsym. So if we could revive and build on @oli-obk's hack for getting dlsym function pointers to work in Miri, that should actually work. :)

[RalfJung]

Current status: should be fixed by rust-lang/rust#62082, but it may be a while until that lands.