smartlist_choose_by_bandwidth() uses crypto_rand_uint64() wrong
In smartlist_choose_by_bandwidth(), we sum up all the bandwidths available and then use crypto_rand_uint64() to pick which relay we'll use. But we have an off-by-one error.
Imagine there are three relays, each with bandwidth 1. So total_bw is 3. So crypto_rand_uint64() can return {0, 1, 2} with equal probability.
Suppose it returns 1.
Then we go through the first round of the for() loop, at the end of which tmp = 1.
So 1 >= 1, and we break. We return the first relay when we should have returned the second.
Ok, so this is a really crazy case that will never happen in practice, right? Not quite.
First, it could have been triggered in the pathological case described by kenobi here (if we hadn't accidentally made it much less likely by moving to KB in the consensus): https://bugs.torproject.org/flyspray/index.php?do=details&id=1194&area=comments#3664 Second, imagine if the first relay has 0 bandwidth, and the other relays have some bandwidth. If crypto_rand_uint64() returns 0, we'll pick the first relay even though it has no weight.
The fix (well, hack) is to set rand_bw++ once we've chosen it. Then we count our fenceposts correctly.
In theory, we shouldn't run into the round-off error warn at the end of the for() clause. Heck if I know how it'll go in practice though.
Thanks to kenobi for diagnosing and coming up with the fix.
[Automatically added by flyspray2trac: Operating System: All]