zeromq/libzmq — pull request #417 by vmg (2012-08-31 17:14:48+00:00)
Title: Always treat randomness with love

Hey!

I've been doing some internal reviews of the ZMQ source code for GitHub. I'm a tad concerned about the way you treat randomness in the library (`random.cpp`, mostly).

The original `generate_random()` has a few critical flaws:

```cpp
uint32_t zmq::generate_random ()
{
// Compensate for the fact that rand() returns signed integer.
uint32_t low = (uint32_t) rand ();
uint32_t high = (uint32_t) rand ();
high <<= (sizeof (int) * 8 - 1);
return high | low;
}
```

- `rand()` does not return a "signed integer", it returns *integers in the range `[0, {RAND_MAX}]`*, which to be fair, is not saying much. `RAND_MAX` can be as low as 32767, and it's not being checked anywhere. Assuming that it has the default value of 2147483647 (2^31) like it does on GlibC is risky business:

- Any value lower than that is going to leave a hole on the bit stream when you shift up the sign bit from the second generation.
- Any value higher than that (e.g. 2^32, which could very well be casted into an `int`), would leave the MSB with a 75% bias towards 1 (assuming a 50% original bias OR'ed with the LSB of the second generation, which also has a 50% bias).

In general, `rand` is so ill-specified that using it on production code is suicidal, and any work-arounds for it are more easily implemented by writing a PRNG from scratch, the features of which we can control and analyze.

- On top of that, `rand()` is not reentrant. At all. And although GLibC's `rand()` is as mind-numbingly simple (stupid?) as this:

```c
int rand_r(unsigned int *seed)
{
*seed = *seed * 1103515245 + 12345;
return (*seed % ((unsigned int)RAND_MAX + 1));
}

int rand(void)
{
return (rand_r(&next));
}
```

...there's still a pretty big chance of getting races on the internal state, and most significantly, duplicate values, when being called from a highly concurrent library such as ZMQ.

- Last, but not least, `seed_random` is not called anywhere, so `rand` is running with a default seed. I may be missing something (I grep'ed to the extent of my available skills), and I couldn't find it anywhere. This was during my plane flight yesterday, so after finding out that the PRNG was not being seeded, I couldn't fall asleep for the rest of the flight. Awful.

### What I propose

For this PR, I went ahead and dropped `rand()` altogether, replacing it with a threadsafe implementation of a Mersenne Twister. MT is a fan favorite since always, and I very much dig the balance between the amount of code and the quality of the generated randomness.

My initial approach was to add a Mersenne instance with its own internal state for each `zmq::io_thread_t` on the system, but the thread references don't get passed *everywhere*, so that was getting the code base slightly too cluttered.

Instead, I decided to add minimal synchronization on the PRNG and kept a single instance of it available globally, as `zmq::random`. This PRNG is seeded on construction. This may not be the most elegant option, but it does prevent races and minimizes the amount of changes on the PR.

Anyway, I'm pretty happy with this. As stated, it's minimal and non-intrusive, and fixes the issue(s) at hand. I'd love some feedback (specially regarding formatting) from somebody who has read the ZMQ code for more than 3 hours.

Love and randomness,
Vicent