r8826@totoro: nickm | 2006-10-01 17:58:45 -0400

 Disprefer exit nodes for entry, middle positions (fixes bug 200).  Also, switch to using a uint64_t to hold "total bandwidth for all nodes" under consideration; crypt_rand_int would have died at 2GB/s network capacity.


svn:r8571

4 files changed, 62 insertions, 32 deletions

diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 586a6704a..11b417818 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -1199,7 +1199,7 @@ choose_good_exit_server_general(routerlist_t *dir, int need_uptime,
     smartlist_subtract(sl,excludedexits);
     if (options->StrictExitNodes || smartlist_overlap(sl,preferredexits))
       smartlist_intersect(sl,preferredexits);
-    router = routerlist_sl_choose_by_bandwidth(sl);
+    router = routerlist_sl_choose_by_bandwidth(sl, 1);
   } else {
     /* Either there are no pending connections, or no routers even seem to
      * possibly support any of them.  Choose a router at random that satisfies
@@ -1238,7 +1238,7 @@ choose_good_exit_server_general(routerlist_t *dir, int need_uptime,
         smartlist_intersect(sl,preferredexits);
         /* XXX sometimes the above results in null, when the requested
          * exit node is down. we should pick it anyway. */
-      router = routerlist_sl_choose_by_bandwidth(sl);
+      router = routerlist_sl_choose_by_bandwidth(sl, 1);
       if (router)
         break;
     }
@@ -1282,14 +1282,14 @@ choose_good_exit_server(uint8_t purpose, routerlist_t *dir,
       if (is_internal) /* pick it like a middle hop */
         return router_choose_random_node(NULL, get_options()->ExcludeNodes,
                NULL, need_uptime, need_capacity, 0,
-               get_options()->_AllowInvalid & ALLOW_INVALID_MIDDLE, 0);
+               get_options()->_AllowInvalid & ALLOW_INVALID_MIDDLE, 0, 0);
       else
         return choose_good_exit_server_general(dir,need_uptime,need_capacity);
     case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
       return router_choose_random_node(
                options->RendNodes, options->RendExcludeNodes,
                NULL, need_uptime, need_capacity, 0,
-               options->_AllowInvalid & ALLOW_INVALID_RENDEZVOUS, 0);
+               options->_AllowInvalid & ALLOW_INVALID_RENDEZVOUS, 0, 0);
   }
   log_warn(LD_BUG,"Bug: unhandled purpose %d", purpose);
   tor_fragile_assert();
@@ -1508,7 +1508,7 @@ choose_good_middle_server(uint8_t purpose,
   choice = router_choose_random_node(preferred,
            options->ExcludeNodes, excluded,
            state->need_uptime, state->need_capacity, 0,
-           options->_AllowInvalid & ALLOW_INVALID_MIDDLE, 0);
+           options->_AllowInvalid & ALLOW_INVALID_MIDDLE, 0, 0);
   if (preferred)
     tor_free(preferred);
   smartlist_free(excluded);
@@ -1571,7 +1571,7 @@ choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state)
            excluded, state ? state->need_uptime : 0,
            state ? state->need_capacity : 0,
            state ? 0 : 1,
-           options->_AllowInvalid & ALLOW_INVALID_ENTRY, 0);
+           options->_AllowInvalid & ALLOW_INVALID_ENTRY, 0, 0);
   smartlist_free(excluded);
   return choice;
 }
diff --git a/src/or/or.h b/src/or/or.h
index f434f5309..4fe16012e 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -918,6 +918,7 @@ typedef struct {
   unsigned int is_fast:1; /** Do we think this is a fast OR? */
   unsigned int is_stable:1; /** Do we think this is a stable OR? */
   unsigned int is_possible_guard:1; /**< Do we think this is an OK guard? */
+  unsigned int is_exit:1; /**< Do we think this is an OK exit? */
 
 /** Tor can use this desc for circuit-building. */
 #define ROUTER_PURPOSE_GENERAL 0
@@ -2562,13 +2563,15 @@ routerinfo_t *router_find_exact_exit_enclave(const char *address,
 int router_is_unreliable(routerinfo_t *router, int need_uptime,
                          int need_capacity, int need_guard);
 uint32_t router_get_advertised_bandwidth(routerinfo_t *router);
-routerinfo_t *routerlist_sl_choose_by_bandwidth(smartlist_t *sl);
+routerinfo_t *routerlist_sl_choose_by_bandwidth(smartlist_t *sl, int for_exit);
+
 routerinfo_t *router_choose_random_node(const char *preferred,
                                         const char *excluded,
                                         smartlist_t *excludedsmartlist,
                                         int need_uptime, int need_bandwidth,
                                         int need_guard,
-                                        int allow_invalid, int strict);
+                                        int allow_invalid, int strict,
+                                        int weight_for_exit);
 routerinfo_t *router_get_by_nickname(const char *nickname,
                                      int warn_if_unnamed);
 routerinfo_t *router_get_by_hexdigest(const char *hexdigest);
diff --git a/src/or/rendservice.c b/src/or/rendservice.c
index a3e5134a6..1af99df90 100644
--- a/src/or/rendservice.c
+++ b/src/or/rendservice.c
@@ -1005,7 +1005,7 @@ rend_services_introduce(void)
       router = router_choose_random_node(service->intro_prefer_nodes,
                service->intro_exclude_nodes, exclude_routers, 1, 0, 0,
                get_options()->_AllowInvalid & ALLOW_INVALID_INTRODUCTION,
-               0);
+               0, 0);
       if (!router) {
         log_warn(LD_REND,
                  "Could only establish %d introduction points for %s.",
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 92cab57a0..b36fa82d5 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -884,46 +884,70 @@ router_get_advertised_bandwidth(routerinfo_t *router)
  * the advertised bandwidth of each router.
  */
 routerinfo_t *
-routerlist_sl_choose_by_bandwidth(smartlist_t *sl)
+routerlist_sl_choose_by_bandwidth(smartlist_t *sl, int for_exit)
 {
   int i;
   routerinfo_t *router;
-  smartlist_t *bandwidths;
-  uint32_t this_bw, tmp, total_bw=0, rand_bw;
-  uint32_t *p;
+  uint32_t *bandwidths;
+  uint32_t this_bw;
+  uint64_t total_nonexit_bw = 0, total_exit_bw = 0, total_bw = 0;
+  uint64_t rand_bw, tmp;
+  double exit_weight;
 
   /* First count the total bandwidth weight, and make a smartlist
    * of each value. */
-  bandwidths = smartlist_create();
+  bandwidths = tor_malloc(sizeof(uint32_t)*smartlist_len(sl));
   for (i = 0; i < smartlist_len(sl); ++i) {
     router = smartlist_get(sl, i);
     this_bw = router_get_advertised_bandwidth(router);
     /* if they claim something huge, don't believe it */
     if (this_bw > MAX_BELIEVABLE_BANDWIDTH)
       this_bw = MAX_BELIEVABLE_BANDWIDTH;
-    p = tor_malloc(sizeof(uint32_t));
-    *p = this_bw;
-    smartlist_add(bandwidths, p);
-    total_bw += this_bw;
+    bandwidths[i] = this_bw;
+    if (router->is_exit)
+      total_exit_bw += this_bw;
+    else
+      total_nonexit_bw += this_bw;
   }
-  if (!total_bw) {
-    SMARTLIST_FOREACH(bandwidths, uint32_t*, p, tor_free(p));
-    smartlist_free(bandwidths);
+  if (!(total_exit_bw+total_nonexit_bw)) {
+    tor_free(bandwidths);
     return smartlist_choose(sl);
   }
+  if (for_exit) {
+    exit_weight = 1.0;
+    total_bw = total_exit_bw + total_nonexit_bw;
+  } else if (total_exit_bw < total_nonexit_bw / 2) {
+    exit_weight = 0.0;
+    total_bw = total_nonexit_bw;
+  } else {
+    uint64_t leftover = (total_exit_bw - total_nonexit_bw / 2);
+    exit_weight = U64_TO_DBL(leftover) /
+      U64_TO_DBL(leftover + total_nonexit_bw);
+    total_bw =  total_nonexit_bw +
+      DBL_TO_U64(exit_weight * U64_TO_DBL(total_exit_bw));
+  }
+  /*
+  log_debug(LD_CIRC, "Total bw = "U64_FORMAT", total exit bw = "U64_FORMAT
+            ", total nonexit bw = "U64_FORMAT", exit weight = %lf "
+            "(for exit == %d)",
+            U64_PRINTF_ARG(total_bw), U64_PRINTF_ARG(total_exit_bw),
+            U64_PRINTF_ARG(total_nonexit_bw), exit_weight, for_exit);
+  */
+
   /* Second, choose a random value from the bandwidth weights. */
-  rand_bw = crypto_rand_int(total_bw);
+  rand_bw = crypto_rand_uint64(total_bw);
   /* Last, count through sl until we get to the element we picked */
   tmp = 0;
-  for (i=0; ; i++) {
-    tor_assert(i < smartlist_len(sl));
-    p = smartlist_get(bandwidths, i);
-    tmp += *p;
+  for (i=0; i < smartlist_len(sl); i++) {
+    router = smartlist_get(sl, i);
+    if (router->is_exit)
+      tmp += ((uint64_t)(bandwidths[i] * exit_weight));
+    else
+      tmp += bandwidths[i];
     if (tmp >= rand_bw)
       break;
   }
-  SMARTLIST_FOREACH(bandwidths, uint32_t*, p, tor_free(p));
-  smartlist_free(bandwidths);
+  tor_free(bandwidths);
   return (routerinfo_t *)smartlist_get(sl, i);
 }
 
@@ -944,7 +968,8 @@ router_choose_random_node(const char *preferred,
                           smartlist_t *excludedsmartlist,
                           int need_uptime, int need_capacity,
                           int need_guard,
-                          int allow_invalid, int strict)
+                          int allow_invalid, int strict,
+                          int weight_for_exit)
 {
   smartlist_t *sl, *excludednodes;
   routerinfo_t *choice = NULL;
@@ -975,8 +1000,8 @@ router_choose_random_node(const char *preferred,
       smartlist_subtract(sl,excludedsmartlist);
     routerlist_sl_remove_unreliable_routers(sl, need_uptime,
                                             need_capacity, need_guard);
-    if (need_capacity)
-      choice = routerlist_sl_choose_by_bandwidth(sl);
+    if (need_capacity) /* XXXX Is this documented in path spec. -NM */
+      choice = routerlist_sl_choose_by_bandwidth(sl, weight_for_exit);
     else
       choice = smartlist_choose(sl);
     smartlist_free(sl);
@@ -989,7 +1014,8 @@ router_choose_random_node(const char *preferred,
                need_uptime?", stable":"",
                need_guard?", guard":"");
       choice = router_choose_random_node(
-        NULL, excluded, excludedsmartlist, 0, 0, 0, allow_invalid, 0);
+        NULL, excluded, excludedsmartlist,
+        0, 0, 0, allow_invalid, 0, weight_for_exit);
     }
   }
   smartlist_free(excludednodes);
@@ -3422,6 +3448,7 @@ routers_update_status_from_networkstatus(smartlist_t *routers,
       router->is_fast = rs->status.is_fast;
       router->is_stable = rs->status.is_stable;
       router->is_possible_guard = rs->status.is_possible_guard;
+      router->is_exit =  rs->status.is_exit;
     }
     if (router->is_running && ds) {
       ds->n_networkstatus_failures = 0;