Page MenuHomeFreeBSD

Add prng(9) API
ClosedPublic

Authored by cem on Aug 1 2020, 8:35 PM.
Tags
None
Referenced Files
Unknown Object (File)
Thu, Apr 11, 12:25 PM
Unknown Object (File)
Feb 24 2024, 9:46 PM
Unknown Object (File)
Feb 2 2024, 3:30 AM
Unknown Object (File)
Feb 2 2024, 3:30 AM
Unknown Object (File)
Dec 12 2023, 5:51 PM
Unknown Object (File)
Nov 20 2023, 8:45 PM
Unknown Object (File)
Nov 20 2023, 8:45 PM
Unknown Object (File)
Nov 20 2023, 8:45 PM
Subscribers

Details

Reviewers
markm
delphij
markj
kib
Group Reviewers
manpages
Commits
rS364219: Add prng(9) API
Summary

Add prng(9) as a replacement for random(9) in the kernel.

There are two major differences from random(9) and random(3):

  • General prng(9) APIs (prng32(9), etc) do not guarantee an implementation or particular sequence; they should not be used for repeatable simulations.
  • However, specific named API families are also exposed (for now: PCG), and those are expected to be repeatable (when so-guaranteed by the named algorithm).

One minor difference from random(3) and earlier random(9) is that PRNG
state for the general prng(9) APIs is per-CPU; this eliminates
contention in SMP workloads.

For now, random(9) becomes a thin shim around prng32(). Eventually I
would like to mechanically switch consumers over to the explicit API.

Diff Detail

Lint
Lint Passed
Unit
No Test Coverage
Build Status
Buildable 32735
Build 30177: arc lint + arc unit

Event Timeline

cem requested review of this revision.Aug 1 2020, 8:35 PM
cem created this revision.

So this KPI is not safe to use from interrupt handlers ? I think you need to mention it in the man page.

sys/sys/prng.h
8

Please use include guards instead of non-standard pragma.

In D25916#574168, @kib wrote:

So this KPI is not safe to use from interrupt handlers ? I think you need to mention it in the man page.

It is no worse from interrupt handlers as existing random(9) KPI, which does not document that deficiency. But we could use spinlock_enter() in place of critical_enter() if that would solve the problem better.

In D25916#574171, @cem wrote:
In D25916#574168, @kib wrote:

So this KPI is not safe to use from interrupt handlers ? I think you need to mention it in the man page.

It is no worse from interrupt handlers as existing random(9) KPI, which does not document that deficiency. But we could use spinlock_enter() in place of critical_enter() if that would solve the problem better.

It is fine for this KPI to not be interrupt-safe. Adding spinlock would make things (much) worse, either spinlock would be global causing scalability issues, or you have to add per-CPU spinlock, which means the overhead of interrupts flag manipulation, which is serializing on some CPUs.

I only asked to be explicit in the man page, so that the answer to this question did not require code spelunking.

In D25916#574172, @kib wrote:

It is fine for this KPI to not be interrupt-safe. Adding spinlock would make things (much) worse, either spinlock would be global causing scalability issues, or you have to add per-CPU spinlock, which means the overhead of interrupts flag manipulation, which is serializing on some CPUs.

I only asked to be explicit in the man page, so that the answer to this question did not require code spelunking.

Ok, sounds good. I will update the manual page.

From the manpages perspective, a tiny AUTHORS and HISTORY section would also be a good addition to the man page. Just saying... ;-)

Update manual page per review comments:

  • Be explicit about interrupt context unsafety
  • Add HISTORY section

Additionally, add a reference to arc4random(9) for CSPRNG generation needs.

No functional change; igor is happy.

Otherwise, the manual seems fine!

share/man/man9/prng.9
61
cem marked an inline comment as done.

man page: Use .Fx macro for FreeBSD

sys/sys/prng.h
13–16

These should probably be #ifdef _KERNEL to allow userspace inclusion of PCG via sys/prng.h. This might be useful for utilities in base that use random(3) or rand(3) today.

markm requested changes to this revision.Aug 3 2020, 6:31 PM

I like this general idea very much! I'm a bit leery of the critical regions, but I admit that I don't understand them properly. I presume that in a PCPU environment they are fine.

sys/sys/prng.h
8

We don't usually use these. Please use macro-based include guards instead.

This revision now requires changes to proceed.Aug 3 2020, 6:31 PM
rpokala added inline comments.
sys/kern/subr_prng.c
39

You're checking for 128bit support, but implementing 64-bit support...?

sys/libkern/random.c
43

Explicitly state that this is non-crypto, and refer to arc4random()?

I like this general idea very much! I'm a bit leery of the critical regions, but I admit that I don't understand them properly. I presume that in a PCPU environment they are fine.

Thanks! The critical regions are just used as a very cheap and short-term mutex on the per-CPU state. (The exception, as kib points out, is that CPUs may still be interrupted during a critical section, so this is not safe to use in interrupt handlers.) A handful of multiplications and additions are performed "under lock." (Maybe a few more multiplications and two divisions, if using the _bounded routines.) This is very very cheap and should not significantly impact scheduler fairness too badly.

sys/kern/subr_prng.c
39

The 64-bit generators use a 128-bit integer state.

sys/libkern/random.c
43

In this comment? The manual page does so already. Ideally this function gets removed before 13.0 anyway.

sys/sys/prng.h
8

Fine, if y'all insist :-).

cem marked 2 inline comments as done.
  • Use preprocessor include guard hack
  • ifdef _KERNEL the KPIs in sys/prng.h
kib added inline comments.
sys/sys/prng.h
13–16

I do not think userspace would work because we do not install /usr/include/contrib/... . But braces cannot hurt anyway.

markj added inline comments.
share/man/man9/prng.9
62

Can't this be folded into the previous sentence? "... and may produce different sequences on different hosts, CPUs, reboots, or versions of FreeBSD."

share/man/man9/prng.9
62

I think it would be less clear folded in, but probably that just means it's also unclear now. The two sentences are trying to cover different properties — the first is just "no ABI is promised, results may vary." The latter is promising a property of the implementation: the PCPU PRNGs all emit different sequences of numbers.

Imagine if each PCPU counter was seeded with zero and stepped by an identical function, e.g., libc's rand_r(). Each CPU generator would produce the exact same sequence of numbers. Here, I'm trying to document that each PCPU step function is unique.

share/man/man9/prng.9
62

I see, thanks. You use "may produce" in the previous sentence and "will produce" in this one, so I'd be fine leaving it as it is since I was just sloppy in how I read the text. "are guaranteed to produce" might be clearer though.

cem marked 2 inline comments as done.

Clarify manual page language around uniqueness property

This revision was not accepted when it landed; it landed in state Needs Review.Aug 13 2020, 8:48 PM
Closed by commit rS364219: Add prng(9) API (authored by cem). · Explain Why
This revision was automatically updated to reflect the committed changes.