Page MenuHomeFreeBSD

Make random() behaves as documented: "result is uniform in [0, 2^31 - 1]"
ClosedPublic

Authored by lprylli_netflix.com on Mar 23 2021, 4:34 AM.
Tags
None
Referenced Files
Unknown Object (File)
Wed, Nov 20, 7:58 AM
Unknown Object (File)
Thu, Nov 14, 12:39 PM
Unknown Object (File)
Thu, Nov 14, 11:52 AM
Unknown Object (File)
Thu, Nov 14, 8:38 AM
Unknown Object (File)
Thu, Nov 14, 7:07 AM
Unknown Object (File)
Thu, Nov 14, 1:06 AM
Unknown Object (File)
Tue, Nov 12, 8:16 AM
Unknown Object (File)
Mar 28 2024, 10:23 AM

Details

Summary
random() was switched in https://reviews.freebsd.org/rS364219     to return result of new prng32().

Since then, random() no longer behaves as documented returning
number with 32 bit range instead of 31 bit range, and
is inconsistent with previous/current doc and usage.

That breaks the computation of things like the "prob xx" match field
in ipfw rules in tests like the one at:
 https://cgit.freebsd.org/src/tree/sys/netpfil/ipfw/ip_fw2.c#n2475
(designed to assume the documented 31 bit range for random()).

Other non-exhaustive examples of places that break because of that changes are:
   sys/dev/bce/if_bcereg.h
   sys/kern/subr_stats.c
   sys/netinet/cc/cc_cdg.c

Over the more than 30 years that random() has been documented as
having a 31 bit range, there seems to be a few places that have
hardcoded assumptions that max value is 0x7fffffff, so the only
safe choice is trying to purge random() use or restore it to
is previous bounds rather than trying to adjust all existing
code to a new bound.

Diff Detail

Repository
rS FreeBSD src repository - subversion
Lint
Lint Passed
Unit
No Test Coverage
Build Status
Buildable 38001
Build 34890: arc lint + arc unit

Event Timeline

This revision is now accepted and ready to land.Mar 23 2021, 5:05 AM

Loic doesn't have a commit bit, so I've offered to commit on his behalf.

cem accepted this revision.EditedMar 23 2021, 5:52 AM

Nice find. I'd encourage using prng32_bounded instead, but I don't think this is mechanically wrong.

Please update the manual page (which refers to 2^32 now, despite the previously-wrong file comment mentioning 2^31) along with this change.

Updates random.9 man page

This reinstates the 31bit return range for random, while maintaining deprecated status,
and pointing at prng(9).

This revision now requires review to proceed.Mar 23 2021, 7:16 AM
In D29385#658103, @cem wrote:

Please update the manual page (which refers to 2^32 now, despite the previously-wrong file comment mentioning 2^31) along with this change.

Done. random(9) was no longer documenting any interval for random() since an older deprecation commit in 2019: https://reviews.freebsd.org/rS356097 , so man-page change is now reinstating documentation for return interval while maintaining deprecation status (and added ref to prng(9)).

This revision is now accepted and ready to land.Mar 23 2021, 7:25 AM
share/man/man9/random.9
138

I'd go ahead and say .Fx 14.0 here instead of a vague future version.

lprylli_netflix.com marked an inline comment as done.

Document plan for removal as 14.0

This revision now requires review to proceed.Mar 23 2021, 5:48 PM

document scheduled removal as 14.0 as suggested.

Great Work! Looks good to go to me.

This revision is now accepted and ready to land.Mar 23 2021, 5:52 PM