[or-cvs] r10939: Fix router_choose_by_bandwidth to no longer be biases by flo (in tor/trunk: . src/or)

[nickm@xxxxxxxx]

Author: nickm
Date: 2007-07-26 17:26:57 -0400 (Thu, 26 Jul 2007)
New Revision: 10939

Modified:
   tor/trunk/
   tor/trunk/ChangeLog
   tor/trunk/src/or/routerlist.c
Log:
 r13927@catbus:  nickm | 2007-07-26 17:26:49 -0400
 Fix router_choose_by_bandwidth to no longer be biases by floating-point roundoff issues.  This runs through the list of routers yet another time, and uses an additional bitfield, but this should be okay: the function did not appear in profiles before, and shouldnt start appearing now.



Property changes on: tor/trunk
___________________________________________________________________
 svk:merge ticket from /tor/trunk [r13927] on 8246c3cf-6607-4228-993b-4d95d33730f1

Modified: tor/trunk/ChangeLog
===================================================================
--- tor/trunk/ChangeLog	2007-07-26 21:26:53 UTC (rev 10938)
+++ tor/trunk/ChangeLog	2007-07-26 21:26:57 UTC (rev 10939)
@@ -85,7 +85,13 @@
       field.  "GETINFO address-mappings" always does the right thing.
     - Use CRLF line endings properly in NS events.
 
+  o Minor bugfixes (misc):
+    - Choose perfectly fairly among routers when choosing by bandwidth and
+      weighting by fraction of bandwidth provided by exits.  Previously,
+      we would choose with only approximate fairness, and correct ourselves
+      if we ran off the end of the list. [Bugfix on 0.1.2.x]
 
+
 Changes in version 0.1.2.15 - 2007-07-17
   o Major bugfixes (compilation):
     - Fix compile on FreeBSD/NetBSD/OpenBSD. Oops.

Modified: tor/trunk/src/or/routerlist.c
===================================================================
--- tor/trunk/src/or/routerlist.c	2007-07-26 21:26:53 UTC (rev 10938)
+++ tor/trunk/src/or/routerlist.c	2007-07-26 21:26:57 UTC (rev 10939)
@@ -1200,12 +1200,14 @@
   uint64_t rand_bw, tmp;
   double exit_weight;
   int n_unknown = 0;
+  bitarray_t *exit_bits;
 
   /* First count the total bandwidth weight, and make a list
    * of each value.  <0 means "unknown; no routerinfo."  We use the
    * bits of negative values to remember whether the router was fast (-x)&1
    * and whether it was an exit (-x)&2.  Yes, it's a hack. */
   bandwidths = tor_malloc(sizeof(int32_t)*smartlist_len(sl));
+  exit_bits = bitarray_init_zero(smartlist_len(sl));
 
   /* Iterate over all the routerinfo_t or routerstatus_t, and */
   for (i = 0; i < (unsigned)smartlist_len(sl); ++i) {
@@ -1230,6 +1232,8 @@
       is_exit = router->is_exit;
       this_bw = router_get_advertised_bandwidth(router);
     }
+    if (is_exit)
+      bitarray_set(exit_bits, i);
     /* if they claim something huge, don't believe it */
     if (this_bw > MAX_BELIEVABLE_BANDWIDTH)
       this_bw = MAX_BELIEVABLE_BANDWIDTH;
@@ -1293,8 +1297,18 @@
     uint64_t leftover = (total_exit_bw - total_nonexit_bw / 2);
     exit_weight = U64_TO_DBL(leftover) /
       U64_TO_DBL(leftover + total_nonexit_bw);
+#if 0
     total_bw =  total_nonexit_bw +
       DBL_TO_U64(exit_weight * U64_TO_DBL(total_exit_bw));
+#endif
+    total_bw = 0;
+    for (i=0; i < (unsigned)smartlist_len(sl); i++) {
+      is_exit = bitarray_is_set(exit_bits, i);
+      if (is_exit)
+        total_bw += ((uint64_t)(bandwidths[i] * exit_weight));
+      else
+        total_bw += bandwidths[i];
+    }
   }
   /*
   log_debug(LD_CIRC, "Total bw = "U64_FORMAT", total exit bw = "U64_FORMAT
@@ -1310,13 +1324,7 @@
   /* Last, count through sl until we get to the element we picked */
   tmp = 0;
   for (i=0; i < (unsigned)smartlist_len(sl); i++) {
-    if (statuses) {
-      status = smartlist_get(sl, i);
-      is_exit = status->is_exit;
-    } else {
-      router = smartlist_get(sl, i);
-      is_exit = router->is_exit;
-    }
+    is_exit = bitarray_is_set(exit_bits, i);
     if (is_exit)
       tmp += ((uint64_t)(bandwidths[i] * exit_weight));
     else
@@ -1325,12 +1333,15 @@
       break;
   }
   if (i == (unsigned)smartlist_len(sl)) {
-    /* This is possible due to round-off error. */
+    /* This was once possible due to round-off error, but shouldn't be able
+     * to occur any longer. */
+    tor_fragile_assert();
     --i;
     log_warn(LD_BUG, "Round-off error in computing bandwidth had an effect on "
              " which router we chose.  Please tell the developers.");
   }
   tor_free(bandwidths);
+  tor_free(exit_bits);
   return smartlist_get(sl, i);
 }