Page MenuHomeFreeBSD

Add prng(9) API
Needs ReviewPublic

Authored by cem on Sat, Aug 1, 8:35 PM.

Details

Reviewers
markm
delphij
markj
kib
Group Reviewers
manpages
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 OK
Unit
No Unit Test Coverage
Build Status
Buildable 32768
Build 30203: arc lint + arc unit

Event Timeline

cem requested review of this revision.Sat, Aug 1, 8:35 PM
cem created this revision.
gbe added a subscriber: gbe.Sat, Aug 1, 8:55 PM
kib added a comment.Sat, Aug 1, 9:05 PM

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.

cem added a comment.Sat, Aug 1, 9:11 PM
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.

kib added a comment.Sat, Aug 1, 9:15 PM
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.

cem added a comment.Sat, Aug 1, 9:34 PM
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.

gbe added a comment.Sat, Aug 1, 10:29 PM

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

cem updated this revision to Diff 75276.Sun, Aug 2, 5:46 PM

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.

cem edited reviewers, added: manpages; removed: docs.Sun, Aug 2, 5:47 PM
0mp added a subscriber: 0mp.Sun, Aug 2, 6:05 PM

Otherwise, the manual seems fine!

share/man/man9/prng.9
61
cem updated this revision to Diff 75284.Sun, Aug 2, 8:47 PM
cem marked an inline comment as done.

man page: Use .Fx macro for FreeBSD

cem added inline comments.Mon, Aug 3, 6:09 PM
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.Mon, Aug 3, 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.Mon, Aug 3, 6:31 PM
rpokala added a subscriber: rpokala.Mon, Aug 3, 8:09 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()?

cem added a comment.Mon, Aug 3, 9:04 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.

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 updated this revision to Diff 75334.Mon, Aug 3, 10:18 PM
cem marked 2 inline comments as done.
  • Use preprocessor include guard hack
  • ifdef _KERNEL the KPIs in sys/prng.h
kib accepted this revision.Mon, Aug 3, 10:25 PM
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 accepted this revision.Tue, Aug 4, 4:03 PM
markj added inline comments.
share/man/man9/prng.9
63

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

cem added inline comments.Tue, Aug 4, 10:04 PM
share/man/man9/prng.9
63

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.

markj added inline comments.Wed, Aug 5, 2:40 AM
share/man/man9/prng.9
63

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 updated this revision to Diff 75425.Wed, Aug 5, 1:50 PM
cem marked 2 inline comments as done.

Clarify manual page language around uniqueness property