libast: provide rand_r fallback

[McDutchie]

ksh depends on the operating system's rand_r function for reproducible seeded $RANDOM sequences. But rand_r has been removed from the 2024 version of the POSIX standard, so we cannot rely on systems continuing to provide it. We should add a fallback implementation to libast for use on systems that don't come with it.

[dnewhall]

I took a cursory look at this.

The most portable fix here is to replace rand_r(&rp->rand_seed) in init.c with just rand().

rand_r returns the same value range as rand and was supposed to be the thread-safe replacement for it, but it never really was (you have to do additional steps to ensure the seed value is thread-safe). There are some C linters that say to replace rand with rand_r, but that was never good advice and now it's deprecated. GNU provides nrand48_r, which is the closest thing that could be used as a modern replacement, but it isn't portable.

If thread safety is what's desired, then it needs to be completely implemented from scratch because there is no way to do thread-safe pseudo-random numbers in POSIX. If compatibility with the existing behavior is what's desired, then rand will do that because we are already calling srand to seed it in put_rand.

An additional oddity with the code is that nget_rand (and by extension get_rand) explicitly refuses to return the same number in a row. That, by definition, makes it non-random (well, less random, in this case).
(Fun fact: the Allies during WW2 were finally able to break the Enigma machine encryption in part by realizing it never returned the same value twice, thus giving the "random" values a pattern)

[dnewhall]

If we decide to do a more thorough reimplementation, this is worth reading:
https://www.evanjones.ca/random-thread-safe.html

[McDutchie]

Thanks for looking into this. A few points:

Thread-safety is irrelevant because this project does not use threads, and never will. Parallelism is implemented by forking or spawning processes.

$RANDOM should not be confused with randomness. It is designed to give the sort of pseudorandomness that is useful for simple games, but nothing more. In fact, it is deliberately reproducible. After seeding it by assigning a known value to it (e.g. RANDOM=123), it will give the same sequence of pseudorandom numbers each time.

rand_r is used instead of rand because this is necessary to keep reproducible seeded $RANDOM sequences working in the shell, particularly in combination with virtual subshells, which require us to save and restore the intermediate seed value. Only rand_r will give us access to the intermediate seed value so we can save it. This is why we are going to have to provide a complete fallback implementation of rand_r.

It's an ancient design decision that $RANDOM never returns the same value twice in a row. This is not going to change at this point. Given that it's not actually random, this is not a problem.

(For real randomness, the dev branch, i.e. future 93u+m/1.1, has added $SRANDOM; see 00b296c, 77ae650, 4c868d6.)

[dnewhall]

Oh, OK. That makes sense.

I've coded up a proof-of-concept replacing rand_r with nrand48 in init.c that appears to work. But should we provide a fallback in case the host implementation doesn't support nrand48? The title mentions adding it to libast; where would such a function go in that case?

[McDutchie]

Using nrand48 is an interesting idea. I looked it up in the POSIX standard. Turns out it's part of a family of functions that has been in POSIX since Issue 1, and is not deprecated, so that seems safe to just use, without providing a fallback. (If a fallback does turn out to be needed, there was one for UWIN in the file src/lib/libast/uwin/rand48.c that was removed in 0ea97b9, so we could re-use that.)

In the meantime I've been working on a rand_r fallback and some related tweaks. The rand_r implementation is so trivial (all of 15 lines) that I think it's not worth doing this in libast. I'll just incorporate it straight into ksh93/sh/init.c. I will apply that first to the dev branch and the 1.0 branch, closing this issue.

After that I would like to see a PR with your nrand48 proof of concept, if you like (which would also remove the rand_r fallback again as rand_r would be unused). We can test that on the dev branch and it can become part of the future 93u+m/1.1 release.