Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Make thread_rng() available without std #313

Closed
pitdicker opened this issue Mar 18, 2018 · 12 comments
Closed

Make thread_rng() available without std #313

pitdicker opened this issue Mar 18, 2018 · 12 comments
Labels
E-help-wanted Participation: help wanted P-low Priority: Low

Comments

@pitdicker
Copy link
Contributor

pitdicker commented Mar 18, 2018

Currently we don't have thread_rng() available without the std feature.

The primary reason is that we do not have thread-local storage available to keep the state of ThreadRng in. And a second problem is that we don't have OsRng or JitterRng available, so we have no way to seed it.

The reason to make ThreadRng available, even when the performance is sub-par, is that it makes it easier to port libraries to the no_std environment. API's do not always allow for the state of an RNG to be passed around.

A few possible solutions:

  • In some cases we may not have thread-local storage available to keep the ThreadRng in.
  • Using a hardware RNG, like RDRAND on x86, or other on-chip devices may be a solution.
  • With WebAssembly we have a fast cryptograpic 'system' RNG, that may be a good alternative to use directly instead of our own PRNG (exposed via OsRng).
  • On tiny hardware using some RNG based on differences between timers may be a good and fast.

Two problems to keep in mind:

  • We now guarantee the RNG is of cryptographic quality, i.e. unpredictable. When we use some other RNG (pluggable?), can we keep similar promises?
  • Wo don't want some arbitrary dependency to silently override the ThreadRng to something else.

One solution could be to let ThreadRng fall back to EntropyRng when we have no thread-local storage, meaning no std feature. Or maybe even put the fallback behind a feature flag itself.

Next EntropyRng could be changed to not only use OsRng, and JitterRng as a fallback, but to have a secondary fallback if both are not available. The secondary fallback should then somehow be pluggable, so some external generator like RDRAND can be used.

@dhardy
Copy link
Member

dhardy commented Mar 18, 2018

Good goal.

Even without thread-local memory we have static memory, and any platform with threading support must support at least mutexes, so we could try using them; I don't know how to write portable code doing that however.

@pitdicker already suggested two options for user-selected fallbacks:

  • unbound extern(C) functions for which the user must provide an implementation (which I didn't like since these functions could be defined from any lib in an application)
  • putting OsRng (or EntropyRng) in its own crate, and letting users replace the crate

It would be good to have help from people experienced in no-std work on this one.

@dhardy dhardy added X-enhancement E-help-wanted Participation: help wanted labels Mar 18, 2018
@jethrogb
Copy link

jethrogb commented Mar 18, 2018

This seems like it might be a good candidate for the "global resource" treatment being discussed as part of the portability WG rust-lang-nursery/portability-wg#3

@pitdicker
Copy link
Contributor Author

Thank you for linking that issue, that seems like just the thing to keep an eye on!

@vks
Copy link
Collaborator

vks commented Jul 16, 2018

lazy_static has some nightly-only tricks to work on no_std using spin, maybe this could be used for thread-local storage as well?

@dhardy
Copy link
Member

dhardy commented Jul 16, 2018

That's half the problem. The other half is getting entropy to seed a PRNG.

EntropyRng is supposed to allow a user-defined source of randomness, but we haven't implemented that yet.

@vks
Copy link
Collaborator

vks commented Jul 16, 2018

I thought JitterRng works on no_std?

@dhardy
Copy link
Member

dhardy commented Jul 16, 2018

Given a suitable high-resolution timer, yes. But not by default, because the default timer comes from the std lib.

@dhardy
Copy link
Member

dhardy commented Aug 1, 2018

There seem to be three issues here:

  1. What does thread_rng do when thread_local [storage] is not available? If the application is single-threaded, then a single, global instance can be used. If multi-threaded, then a global instance can still be used but needs some kind of locking mechanism (hence suggestion of spin above).

    This is resolvable — but in no_std mode should we always use spin-locks? Should we make this an optional feature and assume no threading by default? Is there some way we can test this?

  2. There is no entropy source to seed from. The EntropyRng type already supports a Custom source in theory, except there is no way for users to implement this. We can support this (see below).

  3. JitterRng is in a similar position: it can be used in theory, but requires a user-supplied timer. So we could support overriding the default timer, though this isn't actually required.


Custom static code injection can be done via a feature flag which enables (and uses) extern(C) function declarations, which the user must implement. I don't believe there's a way to only declare functions without extern(C)?

Alternatively we could add a dummy crate with an empty implementation, and expect users to patch their dependency tree with a real implementation.

Or we could use run-time code injection, which should allow more Rustic options, perhaps passing a pointer to some type implementing RngCore (or another trait). This is how the log crate works, and is perhaps the best option. (We need to avoid requiring an allocator, but log manages this — it shouldn't be a problem.) The main drawback of this approach is that users must call something like rand::set_custom_rng at the beginning of their executables and potentially also test suites.

@dhardy
Copy link
Member

dhardy commented Aug 2, 2018

There is one other advantage to using a dummy crate: local storage.

The current design of EntropyRng involves instantiation of all internals whenever EntropyRng::new is called, which is probably whenever it is used. Because of this, OsRng has an internal cache to avoid opening multiple file handles and JitterRng has a cache to avoid needing to test the timer multiple times. The OsRng object (often zero-size) or JitterRng object (small) then gets created within the EntropyRng instance, temporarily.

If CustomRng were defined in an external, replaceable crate, this would let users store any data they like within the type, instantiated each time EntropyRng is called, but also gives incentive to include caching of initialisation and re-usable resources for CustomRng, at least if EntropyRng might be instantiated many times.

But I'm not sure this is the right solution. Run-time injection as in the log crate seems like a nicer API, which doesn't allow this (though we could still include a fixed-size storage space). Logging error messages correctly (rather than repeating errors for each instance) is more difficult than it could be with the current EntropyRng design, as would "learning" which source to use (though the current design re-tries all more-preferable sources each time anyway).

So we could make EntropyRng a handle to a global resource which uses locking on each access instead, though overall the pros and cons seem fairly even.

@dhardy dhardy added this to the 0.6 release milestone Aug 23, 2018
@dhardy dhardy modified the milestones: 0.6 release, 0.7 release Mar 1, 2019
@vks vks removed this from the 0.7 release milestone Jun 27, 2019
@cbeck88
Copy link

cbeck88 commented Aug 14, 2019

@dhardy I think it's worth pointing out that getrandom is currently a no_std crate

https://github.com/rust-random/getrandom/blob/master/src/lib.rs#L127

so the "second half" of the problem seems solved?

@dhardy
Copy link
Member

dhardy commented Aug 14, 2019

The second half of this problem is rust-random/getrandom#4 .

As for the "first" half of this problem, I'm not sure how much genuine interest there is, and for what type of solution (thread-local, shared-with-mutex, single-thread reentrant-safe, simple single-thread).

I think it may not be useful to pursue a general solution in this crate, however I guess this issue can stay open for discussion.

@dhardy dhardy added P-low Priority: Low and removed P-medium labels Oct 29, 2019
@dhardy
Copy link
Member

dhardy commented Oct 29, 2019

In fact, lets close this until there is demand; otherwise this appears to be a solution in search of a problem.

@dhardy dhardy closed this as completed Oct 29, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
E-help-wanted Participation: help wanted P-low Priority: Low
Projects
None yet
Development

No branches or pull requests

5 participants