From e106812a778f53760c819ab20a214ac3222b3b15 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Thu, 9 Aug 2012 12:21:37 -0400 Subject: Change smartlist_choose_node_by_bandwidth to avoid double This should make our preferred solution to #6538 easier to implement, avoid a bunch of potential nastiness with excessive int-vs-double math, and generally make the code there a little less scary. "But wait!" you say. "Is it really safe to do this? Won't the results come out differently?" Yes, but not much. We now round every weighted bandwidth to the nearest byte before computing on it. This will make every node that had a fractional part of its weighted bandwidth before either slighty more likely or slightly less likely. Further, the rand_bw value was only ever set with integer precision, so it can't accurately sample routers with tiny fractional bandwidth values anyway. Finally, doing repeated double-vs-uint64 comparisons is just plain sad; it will involve an implicit cast to double, which is never a fun thing. --- changes/bug6538 | 4 ++++ 1 file changed, 4 insertions(+) create mode 100644 changes/bug6538 (limited to 'changes') diff --git a/changes/bug6538 b/changes/bug6538 new file mode 100644 index 000000000..1e882eb1c --- /dev/null +++ b/changes/bug6538 @@ -0,0 +1,4 @@ + o Minor bugfixes: + - Switch weighted node selection rule from using a list of doubles + to using a list of int64_t. This should make the process slightly + easier to debug and maintain. Needed for fix for bug 6538. -- cgit v1.2.3 From 640a51684ce5a6cdae5c5f92cd2f932922380c00 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Thu, 9 Aug 2012 12:37:40 -0400 Subject: Remove remaining timing-dependency in choosing nodes by bandwidth The old approach, because of its "tmp >= rand_bw && !i_has_been_chosen" check, would run through the second part of the loop slightly slower than the first part. Now, we remove i_has_been_chosen, and instead set rand_bw = UINT64_MAX, so that every instance of the loop will do exactly the same amount of work regardless of the initial value of rand_bw. Fix for bug 6538. --- changes/bug6538 | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'changes') diff --git a/changes/bug6538 b/changes/bug6538 index 1e882eb1c..fc9e583d5 100644 --- a/changes/bug6538 +++ b/changes/bug6538 @@ -2,3 +2,11 @@ - Switch weighted node selection rule from using a list of doubles to using a list of int64_t. This should make the process slightly easier to debug and maintain. Needed for fix for bug 6538. + + o Security features: + - Switch to a completely time-invariant approach for picking nodes + weighted by bandwidth. Our old approach would run through the + part of the loop after it had made its choice slightly slower + than it ran through the part of the loop before it had made its + choice. Fix for bug 6538. + -- cgit v1.2.3 From 07df4dd52d3ab2eea2e8a8fc3222a5d297d077de Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Thu, 9 Aug 2012 13:47:42 -0400 Subject: Refactor the core of choosing by weights into a function This eliminates duplicated code, and lets us test a hairy piece of functionality. --- changes/bug6538 | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'changes') diff --git a/changes/bug6538 b/changes/bug6538 index fc9e583d5..03c168b60 100644 --- a/changes/bug6538 +++ b/changes/bug6538 @@ -10,3 +10,7 @@ than it ran through the part of the loop before it had made its choice. Fix for bug 6538. + o Code simplifications and refactoring: + - Move the core of our "choose a weighted element at random" logic + into its own function, and give it unit tests. Now the logic is + testable, and a little less fragile too. -- cgit v1.2.3