[libcxx] Allow random_device to be built optionally

[efriedma]

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.

[• Quuxplusone]

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! ;))

[jroelofs]

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

[jroelofs]

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

[weimingz]

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

srand(0), rand()

[bcain]

In D41316#957598, @jroelofs wrote:

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.

[weimingz]

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

[• Quuxplusone]

@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.

[weimingz]

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/

[weimingz]

any suggestions?

[jroelofs]

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]

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.

[weimingz]

ping?

[EricWF]

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

2

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

[EricWF]

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]

test/std/experimental/filesystem/lit.local.cfg

5 ↗

(On Diff #132089)

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

[weimingz]

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

[weimingz]

ping?

[weimingz]

gentle ping?

[• Quuxplusone]

test/std/numerics/rand/rand.device/lit.local.cfg

2

@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.

[mclow.lists]

[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.

[efriedma]

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]

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).

[weimingz]

Thanks Eli!

[jroelofs]

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

[mclow.lists]

In D41316#1054968, @efriedma wrote:

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]

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.

[efriedma]

A very similar patch was merged in e0d01294bc124211a8ffb55e69162eb34a242680 .

CMakeLists.txt

 option(LIBCXX_ENABLE_EXPERIMENTAL_LIBRARY "Build libc++experimental.a" ON)
 set(ENABLE_FILESYSTEM_DEFAULT ${LIBCXX_ENABLE_EXPERIMENTAL_LIBRARY})
 if (WIN32)
   set(ENABLE_FILESYSTEM_DEFAULT OFF)
 endif()
 option(LIBCXX_ENABLE_FILESYSTEM "Build filesystem as part of libc++experimental.a"
     ${ENABLE_FILESYSTEM_DEFAULT})
 option(LIBCXX_INCLUDE_TESTS "Build the libc++ tests." ${LLVM_INCLUDE_TESTS})
+option(LIBCXX_ENABLE_RANDOM_DEVICE "Build random_device class" ON)
 
 # Benchmark options -----------------------------------------------------------
 option(LIBCXX_INCLUDE_BENCHMARKS "Build the libc++ benchmarks and their dependancies" ON)
 set(LIBCXX_BENCHMARK_NATIVE_STDLIB "" CACHE STRING
         "Build the benchmarks against the specified native STL.
          The value must be one of libc++/libstdc++")
 set(LIBCXX_BENCHMARK_NATIVE_GCC_TOOLCHAIN "" CACHE STRING
     "Use alternate GCC toolchain when building the native benchmarks")

 config_define_if(LIBCXX_ABI_FORCE_MICROSOFT _LIBCPP_ABI_FORCE_MICROSOFT)
 
 config_define_if_not(LIBCXX_ENABLE_GLOBAL_FILESYSTEM_NAMESPACE _LIBCPP_HAS_NO_GLOBAL_FILESYSTEM_NAMESPACE)
 config_define_if_not(LIBCXX_ENABLE_STDIN _LIBCPP_HAS_NO_STDIN)
 config_define_if_not(LIBCXX_ENABLE_STDOUT _LIBCPP_HAS_NO_STDOUT)
 config_define_if_not(LIBCXX_ENABLE_THREADS _LIBCPP_HAS_NO_THREADS)
 config_define_if_not(LIBCXX_ENABLE_MONOTONIC_CLOCK _LIBCPP_HAS_NO_MONOTONIC_CLOCK)
 config_define_if_not(LIBCXX_ENABLE_THREAD_UNSAFE_C_FUNCTIONS _LIBCPP_HAS_NO_THREAD_UNSAFE_C_FUNCTIONS)
+config_define_if_not(LIBCXX_ENABLE_RANDOM_DEVICE _LIBCPP_HAS_NO_RANDOM_DEVICE)
 
 config_define_if(LIBCXX_HAS_PTHREAD_API _LIBCPP_HAS_THREAD_API_PTHREAD)
 config_define_if(LIBCXX_HAS_EXTERNAL_THREAD_API _LIBCPP_HAS_THREAD_API_EXTERNAL)
 config_define_if(LIBCXX_HAS_WIN32_THREAD_API _LIBCPP_HAS_THREAD_API_WIN32)
 config_define_if(LIBCXX_BUILD_EXTERNAL_THREAD_LIBRARY _LIBCPP_HAS_THREAD_LIBRARY_EXTERNAL)
 config_define_if(LIBCXX_HAS_MUSL_LIBC _LIBCPP_HAS_MUSL_LIBC)
 config_define_if(LIBCXX_NO_VCRUNTIME _LIBCPP_NO_VCRUNTIME)
 

include/__config_site.in

 #cmakedefine _LIBCPP_ABI_FORCE_ITANIUM
 #cmakedefine _LIBCPP_ABI_FORCE_MICROSOFT
 #cmakedefine _LIBCPP_HAS_NO_GLOBAL_FILESYSTEM_NAMESPACE
 #cmakedefine _LIBCPP_HAS_NO_STDIN
 #cmakedefine _LIBCPP_HAS_NO_STDOUT
 #cmakedefine _LIBCPP_HAS_NO_THREADS
 #cmakedefine _LIBCPP_HAS_NO_MONOTONIC_CLOCK
 #cmakedefine _LIBCPP_HAS_NO_THREAD_UNSAFE_C_FUNCTIONS
+#cmakedefine _LIBCPP_HAS_NO_RANDOM_DEVICE
 #cmakedefine _LIBCPP_HAS_MUSL_LIBC
 #cmakedefine _LIBCPP_HAS_THREAD_API_PTHREAD
 #cmakedefine _LIBCPP_HAS_THREAD_API_EXTERNAL
 #cmakedefine _LIBCPP_HAS_THREAD_API_WIN32
 #cmakedefine _LIBCPP_HAS_THREAD_LIBRARY_EXTERNAL
 #cmakedefine _LIBCPP_DISABLE_VISIBILITY_ANNOTATIONS
 #cmakedefine _LIBCPP_NO_VCRUNTIME
 
 @_LIBCPP_ABI_DEFINES@
 
 #endif // _LIBCPP_CONFIG_SITE

include/random

if (!__is.fail())
             __x._V_[__i] = _Vp[__i];
         __x._Y_ = _Vp[_Kp];
     }
     return __is;
 }
 
 typedef shuffle_order_engine<minstd_rand0, 256>                         knuth_b;
 
+#ifndef _LIBCPP_HAS_NO_RANDOM_DEVICE
 // random_device
 
 class _LIBCPP_TYPE_VIS random_device
 {
 #ifdef _LIBCPP_USING_DEV_RANDOM
     int __f_;
 #endif // defined(_LIBCPP_USING_DEV_RANDOM)
 public:
public:
     // property functions
     double entropy() const _NOEXCEPT;
 
 private:
     // no copy functions
     random_device(const random_device&); // = delete;
     random_device& operator=(const random_device&); // = delete;
 };
+#endif // _LIBCPP_HAS_NO_RANDOM_DEVICE
 
 // seed_seq
 
 class _LIBCPP_TEMPLATE_VIS seed_seq
 {
 public:
     // types
     typedef uint32_t result_type;

src/random.cpp

 //===-------------------------- random.cpp --------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is dual licensed under the MIT and the University of Illinois Open
 // Source Licenses. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include <__config>
+#ifndef _LIBCPP_HAS_NO_RANDOM_DEVICE
 
 #if defined(_LIBCPP_USING_WIN32_RANDOM)
 // Must be defined before including stdlib.h to enable rand_s().
 #define _CRT_RAND_S
 #endif // defined(_LIBCPP_USING_WIN32_RANDOM)
 
 #include "random"
 #include "system_error"

 
 double
 random_device::entropy() const _NOEXCEPT
 {
     return 0;
 }
 
 _LIBCPP_END_NAMESPACE_STD
+#endif // _LIBCPP_HAS_NO_RANDOM_DEVICE

test/std/numerics/rand/rand.device/lit.local.cfg

+# Disable all of the random device tests if the correct feature is not available.
+if 'libcpp-has-no-random-device' in config.available_features:
+  config.unsupported = True

test/support/filesystem_test_helper.hpp

 
 #ifndef LIBCXX_FILESYSTEM_DYNAMIC_TEST_HELPER
 #error LIBCXX_FILESYSTEM_DYNAMIC_TEST_HELPER must be defined
 #endif
 
 struct scoped_test_env
 {
     scoped_test_env() : test_root(random_env_path())
-        { fs_helper_run(fs_make_cmd("init_test_directory", test_root)); }
+        { fs_helper_run(fs_make_cmd("init_test_directory", test_root));
+          auto now = std::chrono::high_resolution_clock::now();
+          srand(now.time_since_epoch().count());
+        }
 
     ~scoped_test_env()
         { fs_helper_run(fs_make_cmd("destroy_test_directory", test_root)); }
 
     scoped_test_env(scoped_test_env const &) = delete;
     scoped_test_env & operator=(scoped_test_env const &) = delete;
 
     fs::path make_env_path(std::string p) { return sanitize_path(p); }

 
 private:
     static char to_hex(int ch) {
         return ch < 10 ? static_cast<char>('0' + ch)
                        : static_cast<char>('a' + (ch - 10));
     }
 
     static char random_hex_char() {
-        static std::mt19937 rd { std::random_device{}() };
-        static std::uniform_int_distribution<int> mrand{0, 15};
-        return to_hex( mrand(rd) );
+        return to_hex(rand() & 0xF);
     }
 
     static std::string unique_path_suffix() {
         std::string model = "test.%%%%%%";
         for (auto & ch :  model) {
             if (ch == '%') ch = random_hex_char();
         }
         return model;