Skip to content
GitLab
Projects Groups Snippets
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Sign in
  • Tor Tor
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
  • Issues 330
    • Issues 330
    • List
    • Boards
    • Service Desk
    • Milestones
  • Merge requests 31
    • Merge requests 31
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
  • Deployments
    • Deployments
    • Environments
    • Releases
  • Monitor
    • Monitor
    • Incidents
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Repository
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • The Tor Project
  • Core
  • TorTor
  • Issues
  • #1203
Closed
Open
Issue created Jan 06, 2010 by Roger Dingledine@armaReporter

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]

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information
Assignee
Assign to
Time tracking