Page MenuHomePhabricator

[libcxx] Allow random_device to be built optionally
Needs ReviewPublic

Authored by efriedma on Dec 15 2017, 4:56 PM.

Details

Summary

The default implementation of random_device uses /dev/urandom, which may not be available to systems like bare-metals.

This patch adds a CMake option "LIBCXX_ENABLE_RANDOM_DEVICE" to control the build. Default is On.

Diff Detail

Repository
rCXX libc++

Event Timeline

weimingz created this revision.Dec 15 2017, 4:56 PM

I keep seeing patches go by for other targets where they're just implementing random_device for their target. It doesn't *have* to be based on an actual /dev/urandom. You can see all the other options under #ifdefs in this file: getentropy, /dev/random, nacl_secure_random, arc4random, rand_s,... If you're on a target that doesn't have any of these, then IMO the appropriate patch would be one of

  • #ifdef _LIBCPP_USING_YOURPLATFORM_RANDOM
  • #ifdef _LIBCPP_USING_ALWAYSZERO_RANDOM

where the latter provides a "random_device" that yields nothing but zeroes. That would still be very slightly better than providing a non-conforming implementation. (And notice that the useless double random_device::entropy() method will for the first time return a *mathematically correct* value for the always-zero random_device! ;))

I'd much rather provide no implementation than one that lies. Broken builds are much safer than problems at runtime.

I say that because there are contexts where it is absolutely critical that https://xkcd.com/221/ not be the implementation of an RNG.

Does it make sense to provide an implementation based on C99 rand?
like
#ifdef _LIBCPP_USING_C99_RANDOM

srand(0), rand()
bcain added a comment.Dec 16 2017, 2:37 PM

I'd much rather provide no implementation than one that lies. Broken builds are much safer than problems at runtime.

Agreed! Especially the problems caused by a predictable random seed.

Should we go with current patch? or provide a srand/rand based implementation as an option?

@weimingz: Since your platform supports srand(0), is it possible to look at how your platform implements srand(0) and "inline" that implementation into random_device? That seems like it would be more in keeping with the other ifdefs in this file.

I'm confident that constructing an instance of random_device MUST NOT actually call srand. (I'd like to say that it shouldn't even call rand.) Either of those calls would be observable by the programmer. But there is a precedent for e.g. random_shuffle making calls to rand.

We can wrap the random_device as a minstd_rand, a linear congruential enginer that a lot of C lib uses for rand().
However based on documentation, we should just provides dummy implementation which throws an exception in the constructor of random_device [1,2]
But compared with run-time exception, a link time error is better if we simply skip the implementation. Any thoughts?

[1]

explicit random_device(const string& token = implementation-defined );
...
Throws: A value of an implementation-defined type derived from exception if the random_device could not be initialized.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf section 29.6.6 Class random_device (page 1082)

[2]

Notice that random devices may not always be available to produce random numbers (and in some systems, they may even never be available). This is signaled by throwing an exception derived from the standard exception or when a number is requested with operator()

http://www.cplusplus.com/reference/random/random_device/

any suggestions?

Should we go with current patch?

You'll need a bunch of UNSUPPORTED: has-no-random-device or something like it, but other than that, I'm happy with the patch as-is.

weimingz updated this revision to Diff 132089.Jan 30 2018, 6:13 PM

Disable tests that depend on random_device.
filesystem tests rely on random_device as seed to create random path. Although it's possible to avoid the random_device but if the build target has no random_device, it's very possible that neither filesystem nor other seeding device like clock is available.

EricWF added a comment.Feb 9 2018, 6:10 PM

I think the direction here is OK. Although I really hate allowing bits of libc++ to be "optional". In this case it should be OK, but often it makes the library trickier to maintain -- and these configurations often go untested between releases.

CMakeLists.txt
74

nit: ON

test/std/experimental/filesystem/lit.local.cfg
5 ↗(On Diff #132089)

I would rather keep these tests running using a different source for the random seed if possible.

test/std/numerics/rand/rand.device/lit.local.cfg
1 ↗(On Diff #132089)

There are only 3 tests under this directory. I would rather mark each one explicitly with // UNSUPPORTED: libcpp-has-no-random-device

EricWF added inline comments.Feb 9 2018, 6:15 PM
test/std/experimental/filesystem/lit.local.cfg
5 ↗(On Diff #132089)

Perhaps the random generator could be initialized using std::chrono::system_clock::now().time_since_epoch().count(), which should produce more distinct values that the typical time(NULL) method used to initialize srand.

EricWF added inline comments.Feb 9 2018, 6:17 PM
test/std/experimental/filesystem/lit.local.cfg
5 ↗(On Diff #132089)

Actually std::chrono::high_resolution_clock would be better.

weimingz updated this revision to Diff 133977.Feb 12 2018, 6:53 PM

Modified the random generator in filesystem_test_helper to use high_resolution_clock as seed.

gentle ping?

Quuxplusone added inline comments.Mar 5 2018, 11:04 AM
test/std/numerics/rand/rand.device/lit.local.cfg
1 ↗(On Diff #132089)

@weimingz: looks like this request from Eric is unresolved.

FWIW: I'm still ambivalent about the whole direction of this patch; but I'm happy if everyone else is happy. I don't anticipate any new comments from me.

efriedma commandeered this revision.Apr 2 2018, 1:30 PM
efriedma added a reviewer: weimingz.
hintonda removed a subscriber: hintonda.Apr 2 2018, 1:43 PM

[rand.device]/2 seems to be the authoritative word here:

If implementation limitations prevent generating nondeterministic random numbers, the implementation may employ a random number engine.

Yes, the standard says you're allowed to throw an exception from the random_device constructor, or use a PRNG with an arbitrary seed, or even just return zeros from operator(). But none of those behaviors are actually useful; the code will compile, but you won't get the expected randomness. So I prefer this solution, even if it isn't strictly standard-compliant.

(I'll post an updated version with the tests fixed soon.)

efriedma updated this revision to Diff 141255.Apr 5 2018, 6:54 PM

Get rid of the test changes.

They were broken in multiple ways, and weren't really useful anyway because the targets where you would want to use this can't run the libcxx testsuite anyway (because they don't have an operating system to run the test programs under).

Thanks Eli!

the targets where you would want to use this can't run the libcxx

testsuite anyway (because they don't have an operating system to run the
test programs under).

I used to run libcxx tests for an arm baremetal toolchain I was building
via semihosted QEMU. It was awkward and slow (especially for some of the
std::*_distribution tests), but it worked.

Jon

Yes, the standard says you're allowed to throw an exception from the random_device constructor, or use a PRNG with an arbitrary seed, or even just return zeros from operator(). But none of those behaviors are actually useful; the code will compile, but you won't get the expected randomness. So I prefer this solution, even if it isn't strictly standard-compliant.

I'd very much prefer something standards-compliant.

bcraig added a subscriber: bcraig.Apr 24 2018, 11:54 AM

For those that would prefer random device to not exist if it isn't cryptographically secure, please write a wg21 paper. I will gladly review such a paper, and if you need a presenter, then I will present it if I am attending. I won't be at Rapperswil, but I will be at San Diego.

Stated differently, I agree with both Marshall and the other commenters on this page. I don't want busted random_devices to build, AND I want a standards compliant implementation.

To some degree, this overlaps with http://wg21.link/P0829 . That (my) paper does not require random_device to exist in a freestanding environment.