Back to index

tor  0.2.3.19-rc
circuitbuild.c
Go to the documentation of this file.
00001 /* Copyright (c) 2001 Matej Pfajfar.
00002  * Copyright (c) 2001-2004, Roger Dingledine.
00003  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
00004  * Copyright (c) 2007-2012, The Tor Project, Inc. */
00005 /* See LICENSE for licensing information */
00006 
00012 #define CIRCUIT_PRIVATE
00013 
00014 #include "or.h"
00015 #include "circuitbuild.h"
00016 #include "circuitlist.h"
00017 #include "circuituse.h"
00018 #include "config.h"
00019 #include "connection.h"
00020 #include "connection_edge.h"
00021 #include "connection_or.h"
00022 #include "control.h"
00023 #include "directory.h"
00024 #include "main.h"
00025 #include "networkstatus.h"
00026 #include "nodelist.h"
00027 #include "onion.h"
00028 #include "policies.h"
00029 #include "transports.h"
00030 #include "relay.h"
00031 #include "rephist.h"
00032 #include "router.h"
00033 #include "routerlist.h"
00034 #include "routerparse.h"
00035 #include "crypto.h"
00036 #undef log
00037 #include <math.h>
00038 
00039 #ifndef MIN
00040 #define MIN(a,b) ((a)<(b)?(a):(b))
00041 #endif
00042 
00043 #define CBT_BIN_TO_MS(bin) ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2))
00044 
00045 /********* START VARIABLES **********/
00047 // XXXX: Add this as a member for entry_guard_t instead of global?
00048 // Then we could do per-guard statistics, as guards are likely to
00049 // vary in their own latency. The downside of this is that guards
00050 // can change frequently, so we'd be building a lot more circuits
00051 // most likely.
00052 /* XXXX024 Make this static; add accessor functions. */
00053 circuit_build_times_t circ_times;
00054 
00056 extern circuit_t *global_circuitlist;
00057 
00062 typedef struct {
00063   char nickname[MAX_NICKNAME_LEN+1];
00064   char identity[DIGEST_LEN];
00065   time_t chosen_on_date; 
00067   char *chosen_by_version; 
00069   unsigned int made_contact : 1; 
00071   unsigned int can_retry : 1; 
00073   unsigned int path_bias_notice : 1; 
00075   unsigned int path_bias_disabled : 1; 
00077   time_t bad_since; 
00080   time_t unreachable_since; 
00083   time_t last_attempted; 
00086   unsigned first_hops; 
00087   unsigned circuit_successes; 
00089 } entry_guard_t;
00090 
00094 typedef struct {
00096   tor_addr_t addr;
00098   uint16_t port;
00101   unsigned marked_for_removal : 1;
00104   char identity[DIGEST_LEN];
00105 
00107   char *transport_name;
00108 
00110   download_status_t fetch_status;
00111 } bridge_info_t;
00112 
00114 static smartlist_t *entry_guards = NULL;
00117 static int entry_guards_dirty = 0;
00118 
00121 static int unit_tests = 0;
00122 
00123 /********* END VARIABLES ************/
00124 
00125 static int circuit_deliver_create_cell(circuit_t *circ,
00126                                        uint8_t cell_type, const char *payload);
00127 static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit);
00128 static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
00129 static int onion_extend_cpath(origin_circuit_t *circ);
00130 static int count_acceptable_nodes(smartlist_t *routers);
00131 static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
00132 
00133 static void entry_guards_changed(void);
00134 static entry_guard_t *entry_guard_get_by_id_digest(const char *digest);
00135 
00136 static void bridge_free(bridge_info_t *bridge);
00137 
00147 static int
00148 circuit_build_times_disabled(void)
00149 {
00150   if (unit_tests) {
00151     return 0;
00152   } else {
00153     int consensus_disabled = networkstatus_get_param(NULL, "cbtdisabled",
00154                                                      0, 0, 1);
00155     int config_disabled = !get_options()->LearnCircuitBuildTimeout;
00156     int dirauth_disabled = get_options()->AuthoritativeDir;
00157     int state_disabled = did_last_state_file_write_fail() ? 1 : 0;
00158 
00159     if (consensus_disabled || config_disabled || dirauth_disabled ||
00160            state_disabled) {
00161       log_debug(LD_CIRC,
00162                "CircuitBuildTime learning is disabled. "
00163                "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
00164                consensus_disabled, config_disabled, dirauth_disabled,
00165                state_disabled);
00166       return 1;
00167     } else {
00168       log_debug(LD_CIRC,
00169                 "CircuitBuildTime learning is not disabled. "
00170                 "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
00171                 consensus_disabled, config_disabled, dirauth_disabled,
00172                 state_disabled);
00173       return 0;
00174     }
00175   }
00176 }
00177 
00185 static int32_t
00186 circuit_build_times_max_timeouts(void)
00187 {
00188   int32_t cbt_maxtimeouts;
00189 
00190   cbt_maxtimeouts = networkstatus_get_param(NULL, "cbtmaxtimeouts",
00191                                  CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT,
00192                                  CBT_MIN_MAX_RECENT_TIMEOUT_COUNT,
00193                                  CBT_MAX_MAX_RECENT_TIMEOUT_COUNT);
00194 
00195   if (!(get_options()->LearnCircuitBuildTimeout)) {
00196     log_debug(LD_BUG,
00197               "circuit_build_times_max_timeouts() called, cbtmaxtimeouts is"
00198               " %d",
00199               cbt_maxtimeouts);
00200   }
00201 
00202   return cbt_maxtimeouts;
00203 }
00204 
00214 static int32_t
00215 circuit_build_times_default_num_xm_modes(void)
00216 {
00217   int32_t num = networkstatus_get_param(NULL, "cbtnummodes",
00218                                         CBT_DEFAULT_NUM_XM_MODES,
00219                                         CBT_MIN_NUM_XM_MODES,
00220                                         CBT_MAX_NUM_XM_MODES);
00221 
00222   if (!(get_options()->LearnCircuitBuildTimeout)) {
00223     log_debug(LD_BUG,
00224               "circuit_build_times_default_num_xm_modes() called, cbtnummodes"
00225               " is %d",
00226               num);
00227   }
00228 
00229   return num;
00230 }
00231 
00238 static int32_t
00239 circuit_build_times_min_circs_to_observe(void)
00240 {
00241   int32_t num = networkstatus_get_param(NULL, "cbtmincircs",
00242                                         CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE,
00243                                         CBT_MIN_MIN_CIRCUITS_TO_OBSERVE,
00244                                         CBT_MAX_MIN_CIRCUITS_TO_OBSERVE);
00245 
00246   if (!(get_options()->LearnCircuitBuildTimeout)) {
00247     log_debug(LD_BUG,
00248               "circuit_build_times_min_circs_to_observe() called, cbtmincircs"
00249               " is %d",
00250               num);
00251   }
00252 
00253   return num;
00254 }
00255 
00258 int
00259 circuit_build_times_enough_to_compute(circuit_build_times_t *cbt)
00260 {
00261   return cbt->total_build_times >= circuit_build_times_min_circs_to_observe();
00262 }
00263 
00270 double
00271 circuit_build_times_quantile_cutoff(void)
00272 {
00273   int32_t num = networkstatus_get_param(NULL, "cbtquantile",
00274                                         CBT_DEFAULT_QUANTILE_CUTOFF,
00275                                         CBT_MIN_QUANTILE_CUTOFF,
00276                                         CBT_MAX_QUANTILE_CUTOFF);
00277 
00278   if (!(get_options()->LearnCircuitBuildTimeout)) {
00279     log_debug(LD_BUG,
00280               "circuit_build_times_quantile_cutoff() called, cbtquantile"
00281               " is %d",
00282               num);
00283   }
00284 
00285   return num/100.0;
00286 }
00287 
00288 /* DOCDOC circuit_build_times_get_bw_scale */
00289 int
00290 circuit_build_times_get_bw_scale(networkstatus_t *ns)
00291 {
00292   return networkstatus_get_param(ns, "bwweightscale",
00293                                  BW_WEIGHT_SCALE,
00294                                  BW_MIN_WEIGHT_SCALE,
00295                                  BW_MAX_WEIGHT_SCALE);
00296 }
00297 
00305 static double
00306 circuit_build_times_close_quantile(void)
00307 {
00308   int32_t param;
00309   /* Cast is safe - circuit_build_times_quantile_cutoff() is capped */
00310   int32_t min = (int)tor_lround(100*circuit_build_times_quantile_cutoff());
00311   param = networkstatus_get_param(NULL, "cbtclosequantile",
00312              CBT_DEFAULT_CLOSE_QUANTILE,
00313              CBT_MIN_CLOSE_QUANTILE,
00314              CBT_MAX_CLOSE_QUANTILE);
00315 
00316   if (!(get_options()->LearnCircuitBuildTimeout)) {
00317     log_debug(LD_BUG,
00318               "circuit_build_times_close_quantile() called, cbtclosequantile"
00319               " is %d", param);
00320   }
00321 
00322   if (param < min) {
00323     log_warn(LD_DIR, "Consensus parameter cbtclosequantile is "
00324              "too small, raising to %d", min);
00325     param = min;
00326   }
00327   return param / 100.0;
00328 }
00329 
00337 static int32_t
00338 circuit_build_times_test_frequency(void)
00339 {
00340   int32_t num = networkstatus_get_param(NULL, "cbttestfreq",
00341                                         CBT_DEFAULT_TEST_FREQUENCY,
00342                                         CBT_MIN_TEST_FREQUENCY,
00343                                         CBT_MAX_TEST_FREQUENCY);
00344 
00345   if (!(get_options()->LearnCircuitBuildTimeout)) {
00346     log_debug(LD_BUG,
00347               "circuit_build_times_test_frequency() called, cbttestfreq is %d",
00348               num);
00349   }
00350 
00351   return num;
00352 }
00353 
00361 static int32_t
00362 circuit_build_times_min_timeout(void)
00363 {
00364   int32_t num = networkstatus_get_param(NULL, "cbtmintimeout",
00365                                         CBT_DEFAULT_TIMEOUT_MIN_VALUE,
00366                                         CBT_MIN_TIMEOUT_MIN_VALUE,
00367                                         CBT_MAX_TIMEOUT_MIN_VALUE);
00368 
00369   if (!(get_options()->LearnCircuitBuildTimeout)) {
00370     log_debug(LD_BUG,
00371               "circuit_build_times_min_timeout() called, cbtmintimeout is %d",
00372               num);
00373   }
00374 
00375   return num;
00376 }
00377 
00384 int32_t
00385 circuit_build_times_initial_timeout(void)
00386 {
00387   int32_t min = circuit_build_times_min_timeout();
00388   int32_t param = networkstatus_get_param(NULL, "cbtinitialtimeout",
00389                                           CBT_DEFAULT_TIMEOUT_INITIAL_VALUE,
00390                                           CBT_MIN_TIMEOUT_INITIAL_VALUE,
00391                                           CBT_MAX_TIMEOUT_INITIAL_VALUE);
00392 
00393   if (!(get_options()->LearnCircuitBuildTimeout)) {
00394     log_debug(LD_BUG,
00395               "circuit_build_times_initial_timeout() called, "
00396               "cbtinitialtimeout is %d",
00397               param);
00398   }
00399 
00400   if (param < min) {
00401     log_warn(LD_DIR, "Consensus parameter cbtinitialtimeout is too small, "
00402              "raising to %d", min);
00403     param = min;
00404   }
00405   return param;
00406 }
00407 
00415 static int32_t
00416 circuit_build_times_recent_circuit_count(networkstatus_t *ns)
00417 {
00418   int32_t num;
00419   num = networkstatus_get_param(ns, "cbtrecentcount",
00420                                 CBT_DEFAULT_RECENT_CIRCUITS,
00421                                 CBT_MIN_RECENT_CIRCUITS,
00422                                 CBT_MAX_RECENT_CIRCUITS);
00423 
00424   if (!(get_options()->LearnCircuitBuildTimeout)) {
00425     log_debug(LD_BUG,
00426               "circuit_build_times_recent_circuit_count() called, "
00427               "cbtrecentcount is %d",
00428               num);
00429   }
00430 
00431   return num;
00432 }
00433 
00440 void
00441 circuit_build_times_new_consensus_params(circuit_build_times_t *cbt,
00442                                          networkstatus_t *ns)
00443 {
00444   int32_t num;
00445 
00446   /*
00447    * First check if we're doing adaptive timeouts at all; nothing to
00448    * update if we aren't.
00449    */
00450 
00451   if (!circuit_build_times_disabled()) {
00452     num = circuit_build_times_recent_circuit_count(ns);
00453 
00454     if (num > 0) {
00455       if (num != cbt->liveness.num_recent_circs) {
00456         int8_t *recent_circs;
00457         log_notice(LD_CIRC, "The Tor Directory Consensus has changed how many "
00458                    "circuits we must track to detect network failures from %d "
00459                    "to %d.", cbt->liveness.num_recent_circs, num);
00460 
00461         tor_assert(cbt->liveness.timeouts_after_firsthop ||
00462                    cbt->liveness.num_recent_circs == 0);
00463 
00464         /*
00465          * Technically this is a circular array that we are reallocating
00466          * and memcopying. However, since it only consists of either 1s
00467          * or 0s, and is only used in a statistical test to determine when
00468          * we should discard our history after a sufficient number of 1's
00469          * have been reached, it is fine if order is not preserved or
00470          * elements are lost.
00471          *
00472          * cbtrecentcount should only be changing in cases of severe network
00473          * distress anyway, so memory correctness here is paramount over
00474          * doing acrobatics to preserve the array.
00475          */
00476         recent_circs = tor_malloc_zero(sizeof(int8_t)*num);
00477         if (cbt->liveness.timeouts_after_firsthop &&
00478             cbt->liveness.num_recent_circs > 0) {
00479           memcpy(recent_circs, cbt->liveness.timeouts_after_firsthop,
00480                  sizeof(int8_t)*MIN(num, cbt->liveness.num_recent_circs));
00481         }
00482 
00483         // Adjust the index if it needs it.
00484         if (num < cbt->liveness.num_recent_circs) {
00485           cbt->liveness.after_firsthop_idx = MIN(num-1,
00486                   cbt->liveness.after_firsthop_idx);
00487         }
00488 
00489         tor_free(cbt->liveness.timeouts_after_firsthop);
00490         cbt->liveness.timeouts_after_firsthop = recent_circs;
00491         cbt->liveness.num_recent_circs = num;
00492       }
00493       /* else no change, nothing to do */
00494     } else { /* num == 0 */
00495       /*
00496        * Weird.  This probably shouldn't happen, so log a warning, but try
00497        * to do something sensible anyway.
00498        */
00499 
00500       log_warn(LD_CIRC,
00501                "The cbtrecentcircs consensus parameter came back zero!  "
00502                "This disables adaptive timeouts since we can't keep track of "
00503                "any recent circuits.");
00504 
00505       circuit_build_times_free_timeouts(cbt);
00506     }
00507   } else {
00508     /*
00509      * Adaptive timeouts are disabled; this might be because of the
00510      * LearnCircuitBuildTimes config parameter, and hence permanent, or
00511      * the cbtdisabled consensus parameter, so it may be a new condition.
00512      * Treat it like getting num == 0 above and free the circuit history
00513      * if we have any.
00514      */
00515 
00516     circuit_build_times_free_timeouts(cbt);
00517   }
00518 }
00519 
00522 void
00523 circuitbuild_running_unit_tests(void)
00524 {
00525   unit_tests = 1;
00526 }
00527 
00531 static double
00532 circuit_build_times_get_initial_timeout(void)
00533 {
00534   double timeout;
00535 
00536   /*
00537    * Check if we have LearnCircuitBuildTimeout, and if we don't,
00538    * always use CircuitBuildTimeout, no questions asked.
00539    */
00540   if (get_options()->LearnCircuitBuildTimeout) {
00541     if (!unit_tests && get_options()->CircuitBuildTimeout) {
00542       timeout = get_options()->CircuitBuildTimeout*1000;
00543       if (timeout < circuit_build_times_min_timeout()) {
00544         log_warn(LD_CIRC, "Config CircuitBuildTimeout too low. Setting to %ds",
00545                  circuit_build_times_min_timeout()/1000);
00546         timeout = circuit_build_times_min_timeout();
00547       }
00548     } else {
00549       timeout = circuit_build_times_initial_timeout();
00550     }
00551   } else {
00552     timeout = get_options()->CircuitBuildTimeout*1000;
00553   }
00554 
00555   return timeout;
00556 }
00557 
00564 void
00565 circuit_build_times_reset(circuit_build_times_t *cbt)
00566 {
00567   memset(cbt->circuit_build_times, 0, sizeof(cbt->circuit_build_times));
00568   cbt->total_build_times = 0;
00569   cbt->build_times_idx = 0;
00570   cbt->have_computed_timeout = 0;
00571 }
00572 
00579 void
00580 circuit_build_times_init(circuit_build_times_t *cbt)
00581 {
00582   memset(cbt, 0, sizeof(*cbt));
00583   /*
00584    * Check if we really are using adaptive timeouts, and don't keep
00585    * track of this stuff if not.
00586    */
00587   if (!circuit_build_times_disabled()) {
00588     cbt->liveness.num_recent_circs =
00589       circuit_build_times_recent_circuit_count(NULL);
00590     cbt->liveness.timeouts_after_firsthop =
00591       tor_malloc_zero(sizeof(int8_t)*cbt->liveness.num_recent_circs);
00592   } else {
00593     cbt->liveness.num_recent_circs = 0;
00594     cbt->liveness.timeouts_after_firsthop = NULL;
00595   }
00596   cbt->close_ms = cbt->timeout_ms = circuit_build_times_get_initial_timeout();
00597   control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
00598 }
00599 
00605 void
00606 circuit_build_times_free_timeouts(circuit_build_times_t *cbt)
00607 {
00608   if (!cbt) return;
00609 
00610   if (cbt->liveness.timeouts_after_firsthop) {
00611     tor_free(cbt->liveness.timeouts_after_firsthop);
00612   }
00613 
00614   cbt->liveness.num_recent_circs = 0;
00615 }
00616 
00617 #if 0
00618 
00621 static void
00622 circuit_build_times_rewind_history(circuit_build_times_t *cbt, int n)
00623 {
00624   int i = 0;
00625 
00626   cbt->build_times_idx -= n;
00627   cbt->build_times_idx %= CBT_NCIRCUITS_TO_OBSERVE;
00628 
00629   for (i = 0; i < n; i++) {
00630     cbt->circuit_build_times[(i+cbt->build_times_idx)
00631                              %CBT_NCIRCUITS_TO_OBSERVE]=0;
00632   }
00633 
00634   if (cbt->total_build_times > n) {
00635     cbt->total_build_times -= n;
00636   } else {
00637     cbt->total_build_times = 0;
00638   }
00639 
00640   log_info(LD_CIRC,
00641           "Rewound history by %d places. Current index: %d. "
00642           "Total: %d", n, cbt->build_times_idx, cbt->total_build_times);
00643 }
00644 #endif
00645 
00653 int
00654 circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t time)
00655 {
00656   if (time <= 0 || time > CBT_BUILD_TIME_MAX) {
00657     log_warn(LD_BUG, "Circuit build time is too large (%u)."
00658                       "This is probably a bug.", time);
00659     tor_fragile_assert();
00660     return -1;
00661   }
00662 
00663   log_debug(LD_CIRC, "Adding circuit build time %u", time);
00664 
00665   cbt->circuit_build_times[cbt->build_times_idx] = time;
00666   cbt->build_times_idx = (cbt->build_times_idx + 1) % CBT_NCIRCUITS_TO_OBSERVE;
00667   if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
00668     cbt->total_build_times++;
00669 
00670   if ((cbt->total_build_times % CBT_SAVE_STATE_EVERY) == 0) {
00671     /* Save state every n circuit builds */
00672     if (!unit_tests && !get_options()->AvoidDiskWrites)
00673       or_state_mark_dirty(get_or_state(), 0);
00674   }
00675 
00676   return 0;
00677 }
00678 
00682 static build_time_t
00683 circuit_build_times_max(circuit_build_times_t *cbt)
00684 {
00685   int i = 0;
00686   build_time_t max_build_time = 0;
00687   for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
00688     if (cbt->circuit_build_times[i] > max_build_time
00689             && cbt->circuit_build_times[i] != CBT_BUILD_ABANDONED)
00690       max_build_time = cbt->circuit_build_times[i];
00691   }
00692   return max_build_time;
00693 }
00694 
00695 #if 0
00696 
00697 build_time_t
00698 circuit_build_times_min(circuit_build_times_t *cbt)
00699 {
00700   int i = 0;
00701   build_time_t min_build_time = CBT_BUILD_TIME_MAX;
00702   for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
00703     if (cbt->circuit_build_times[i] && /* 0 <-> uninitialized */
00704         cbt->circuit_build_times[i] < min_build_time)
00705       min_build_time = cbt->circuit_build_times[i];
00706   }
00707   if (min_build_time == CBT_BUILD_TIME_MAX) {
00708     log_warn(LD_CIRC, "No build times less than CBT_BUILD_TIME_MAX!");
00709   }
00710   return min_build_time;
00711 }
00712 #endif
00713 
00723 static uint32_t *
00724 circuit_build_times_create_histogram(circuit_build_times_t *cbt,
00725                                      build_time_t *nbins)
00726 {
00727   uint32_t *histogram;
00728   build_time_t max_build_time = circuit_build_times_max(cbt);
00729   int i, c;
00730 
00731   *nbins = 1 + (max_build_time / CBT_BIN_WIDTH);
00732   histogram = tor_malloc_zero(*nbins * sizeof(build_time_t));
00733 
00734   // calculate histogram
00735   for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
00736     if (cbt->circuit_build_times[i] == 0
00737             || cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
00738       continue; /* 0 <-> uninitialized */
00739 
00740     c = (cbt->circuit_build_times[i] / CBT_BIN_WIDTH);
00741     histogram[c]++;
00742   }
00743 
00744   return histogram;
00745 }
00746 
00755 static build_time_t
00756 circuit_build_times_get_xm(circuit_build_times_t *cbt)
00757 {
00758   build_time_t i, nbins;
00759   build_time_t *nth_max_bin;
00760   int32_t bin_counts=0;
00761   build_time_t ret = 0;
00762   uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins);
00763   int n=0;
00764   int num_modes = circuit_build_times_default_num_xm_modes();
00765 
00766   tor_assert(nbins > 0);
00767   tor_assert(num_modes > 0);
00768 
00769   // Only use one mode if < 1000 buildtimes. Not enough data
00770   // for multiple.
00771   if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
00772     num_modes = 1;
00773 
00774   nth_max_bin = (build_time_t*)tor_malloc_zero(num_modes*sizeof(build_time_t));
00775 
00776   /* Determine the N most common build times */
00777   for (i = 0; i < nbins; i++) {
00778     if (histogram[i] >= histogram[nth_max_bin[0]]) {
00779       nth_max_bin[0] = i;
00780     }
00781 
00782     for (n = 1; n < num_modes; n++) {
00783       if (histogram[i] >= histogram[nth_max_bin[n]] &&
00784            (!histogram[nth_max_bin[n-1]]
00785                || histogram[i] < histogram[nth_max_bin[n-1]])) {
00786         nth_max_bin[n] = i;
00787       }
00788     }
00789   }
00790 
00791   for (n = 0; n < num_modes; n++) {
00792     bin_counts += histogram[nth_max_bin[n]];
00793     ret += CBT_BIN_TO_MS(nth_max_bin[n])*histogram[nth_max_bin[n]];
00794     log_info(LD_CIRC, "Xm mode #%d: %u %u", n, CBT_BIN_TO_MS(nth_max_bin[n]),
00795              histogram[nth_max_bin[n]]);
00796   }
00797 
00798   /* The following assert is safe, because we don't get called when we
00799    * haven't observed at least CBT_MIN_MIN_CIRCUITS_TO_OBSERVE circuits. */
00800   tor_assert(bin_counts > 0);
00801 
00802   ret /= bin_counts;
00803   tor_free(histogram);
00804   tor_free(nth_max_bin);
00805 
00806   return ret;
00807 }
00808 
00813 void
00814 circuit_build_times_update_state(circuit_build_times_t *cbt,
00815                                  or_state_t *state)
00816 {
00817   uint32_t *histogram;
00818   build_time_t i = 0;
00819   build_time_t nbins = 0;
00820   config_line_t **next, *line;
00821 
00822   histogram = circuit_build_times_create_histogram(cbt, &nbins);
00823   // write to state
00824   config_free_lines(state->BuildtimeHistogram);
00825   next = &state->BuildtimeHistogram;
00826   *next = NULL;
00827 
00828   state->TotalBuildTimes = cbt->total_build_times;
00829   state->CircuitBuildAbandonedCount = 0;
00830 
00831   for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
00832     if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
00833       state->CircuitBuildAbandonedCount++;
00834   }
00835 
00836   for (i = 0; i < nbins; i++) {
00837     // compress the histogram by skipping the blanks
00838     if (histogram[i] == 0) continue;
00839     *next = line = tor_malloc_zero(sizeof(config_line_t));
00840     line->key = tor_strdup("CircuitBuildTimeBin");
00841     tor_asprintf(&line->value, "%d %d",
00842             CBT_BIN_TO_MS(i), histogram[i]);
00843     next = &(line->next);
00844   }
00845 
00846   if (!unit_tests) {
00847     if (!get_options()->AvoidDiskWrites)
00848       or_state_mark_dirty(get_or_state(), 0);
00849   }
00850 
00851   tor_free(histogram);
00852 }
00853 
00859 static void
00860 circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt,
00861                                             build_time_t *raw_times,
00862                                             uint32_t num_times)
00863 {
00864   uint32_t n = num_times;
00865   if (num_times > CBT_NCIRCUITS_TO_OBSERVE) {
00866     log_notice(LD_CIRC, "The number of circuit times that this Tor version "
00867                "uses to calculate build times is less than the number stored "
00868                "in your state file. Decreasing the circuit time history from "
00869                "%lu to %d.", (unsigned long)num_times,
00870                CBT_NCIRCUITS_TO_OBSERVE);
00871   }
00872 
00873   if (n > INT_MAX-1) {
00874     log_warn(LD_CIRC, "For some insane reasons, you had %lu circuit build "
00875              "observations in your state file. That's far too many; probably "
00876              "there's a bug here.", (unsigned long)n);
00877     n = INT_MAX-1;
00878   }
00879 
00880   /* This code can only be run on a compact array */
00881   while (n-- > 1) {
00882     int k = crypto_rand_int(n + 1); /* 0 <= k <= n. */
00883     build_time_t tmp = raw_times[k];
00884     raw_times[k] = raw_times[n];
00885     raw_times[n] = tmp;
00886   }
00887 
00888   /* Since the times are now shuffled, take a random CBT_NCIRCUITS_TO_OBSERVE
00889    * subset (ie the first CBT_NCIRCUITS_TO_OBSERVE values) */
00890   for (n = 0; n < MIN(num_times, CBT_NCIRCUITS_TO_OBSERVE); n++) {
00891     circuit_build_times_add_time(cbt, raw_times[n]);
00892   }
00893 }
00894 
00902 static int
00903 circuit_build_times_filter_timeouts(circuit_build_times_t *cbt)
00904 {
00905   int num_filtered=0, i=0;
00906   double timeout_rate = 0;
00907   build_time_t max_timeout = 0;
00908 
00909   timeout_rate = circuit_build_times_timeout_rate(cbt);
00910   max_timeout = (build_time_t)cbt->close_ms;
00911 
00912   for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
00913     if (cbt->circuit_build_times[i] > max_timeout) {
00914       build_time_t replaced = cbt->circuit_build_times[i];
00915       num_filtered++;
00916       cbt->circuit_build_times[i] = CBT_BUILD_ABANDONED;
00917 
00918       log_debug(LD_CIRC, "Replaced timeout %d with %d", replaced,
00919                cbt->circuit_build_times[i]);
00920     }
00921   }
00922 
00923   log_info(LD_CIRC,
00924            "We had %d timeouts out of %d build times, "
00925            "and filtered %d above the max of %u",
00926           (int)(cbt->total_build_times*timeout_rate),
00927           cbt->total_build_times, num_filtered, max_timeout);
00928 
00929   return num_filtered;
00930 }
00931 
00939 int
00940 circuit_build_times_parse_state(circuit_build_times_t *cbt,
00941                                 or_state_t *state)
00942 {
00943   int tot_values = 0;
00944   uint32_t loaded_cnt = 0, N = 0;
00945   config_line_t *line;
00946   unsigned int i;
00947   build_time_t *loaded_times;
00948   int err = 0;
00949   circuit_build_times_init(cbt);
00950 
00951   if (circuit_build_times_disabled()) {
00952     return 0;
00953   }
00954 
00955   /* build_time_t 0 means uninitialized */
00956   loaded_times = tor_malloc_zero(sizeof(build_time_t)*state->TotalBuildTimes);
00957 
00958   for (line = state->BuildtimeHistogram; line; line = line->next) {
00959     smartlist_t *args = smartlist_new();
00960     smartlist_split_string(args, line->value, " ",
00961                            SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
00962     if (smartlist_len(args) < 2) {
00963       log_warn(LD_GENERAL, "Unable to parse circuit build times: "
00964                            "Too few arguments to CircuitBuildTime");
00965       err = 1;
00966       SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
00967       smartlist_free(args);
00968       break;
00969     } else {
00970       const char *ms_str = smartlist_get(args,0);
00971       const char *count_str = smartlist_get(args,1);
00972       uint32_t count, k;
00973       build_time_t ms;
00974       int ok;
00975       ms = (build_time_t)tor_parse_ulong(ms_str, 0, 0,
00976                                          CBT_BUILD_TIME_MAX, &ok, NULL);
00977       if (!ok) {
00978         log_warn(LD_GENERAL, "Unable to parse circuit build times: "
00979                              "Unparsable bin number");
00980         err = 1;
00981         SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
00982         smartlist_free(args);
00983         break;
00984       }
00985       count = (uint32_t)tor_parse_ulong(count_str, 0, 0,
00986                                         UINT32_MAX, &ok, NULL);
00987       if (!ok) {
00988         log_warn(LD_GENERAL, "Unable to parse circuit build times: "
00989                              "Unparsable bin count");
00990         err = 1;
00991         SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
00992         smartlist_free(args);
00993         break;
00994       }
00995 
00996       if (loaded_cnt+count+state->CircuitBuildAbandonedCount
00997             > state->TotalBuildTimes) {
00998         log_warn(LD_CIRC,
00999                  "Too many build times in state file. "
01000                  "Stopping short before %d",
01001                  loaded_cnt+count);
01002         SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
01003         smartlist_free(args);
01004         break;
01005       }
01006 
01007       for (k = 0; k < count; k++) {
01008         loaded_times[loaded_cnt++] = ms;
01009       }
01010       N++;
01011       SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
01012       smartlist_free(args);
01013     }
01014   }
01015 
01016   log_info(LD_CIRC,
01017            "Adding %d timeouts.", state->CircuitBuildAbandonedCount);
01018   for (i=0; i < state->CircuitBuildAbandonedCount; i++) {
01019     loaded_times[loaded_cnt++] = CBT_BUILD_ABANDONED;
01020   }
01021 
01022   if (loaded_cnt != state->TotalBuildTimes) {
01023     log_warn(LD_CIRC,
01024             "Corrupt state file? Build times count mismatch. "
01025             "Read %d times, but file says %d", loaded_cnt,
01026             state->TotalBuildTimes);
01027     err = 1;
01028     circuit_build_times_reset(cbt);
01029     goto done;
01030   }
01031 
01032   circuit_build_times_shuffle_and_store_array(cbt, loaded_times, loaded_cnt);
01033 
01034   /* Verify that we didn't overwrite any indexes */
01035   for (i=0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
01036     if (!cbt->circuit_build_times[i])
01037       break;
01038     tot_values++;
01039   }
01040   log_info(LD_CIRC,
01041            "Loaded %d/%d values from %d lines in circuit time histogram",
01042            tot_values, cbt->total_build_times, N);
01043 
01044   if (cbt->total_build_times != tot_values
01045         || cbt->total_build_times > CBT_NCIRCUITS_TO_OBSERVE) {
01046     log_warn(LD_CIRC,
01047             "Corrupt state file? Shuffled build times mismatch. "
01048             "Read %d times, but file says %d", tot_values,
01049             state->TotalBuildTimes);
01050     err = 1;
01051     circuit_build_times_reset(cbt);
01052     goto done;
01053   }
01054 
01055   circuit_build_times_set_timeout(cbt);
01056 
01057   if (!state->CircuitBuildAbandonedCount && cbt->total_build_times) {
01058     circuit_build_times_filter_timeouts(cbt);
01059   }
01060 
01061  done:
01062   tor_free(loaded_times);
01063   return err ? -1 : 0;
01064 }
01065 
01075 int
01076 circuit_build_times_update_alpha(circuit_build_times_t *cbt)
01077 {
01078   build_time_t *x=cbt->circuit_build_times;
01079   double a = 0;
01080   int n=0,i=0,abandoned_count=0;
01081   build_time_t max_time=0;
01082 
01083   /* http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation */
01084   /* We sort of cheat here and make our samples slightly more pareto-like
01085    * and less frechet-like. */
01086   cbt->Xm = circuit_build_times_get_xm(cbt);
01087 
01088   tor_assert(cbt->Xm > 0);
01089 
01090   for (i=0; i< CBT_NCIRCUITS_TO_OBSERVE; i++) {
01091     if (!x[i]) {
01092       continue;
01093     }
01094 
01095     if (x[i] < cbt->Xm) {
01096       a += tor_mathlog(cbt->Xm);
01097     } else if (x[i] == CBT_BUILD_ABANDONED) {
01098       abandoned_count++;
01099     } else {
01100       a += tor_mathlog(x[i]);
01101       if (x[i] > max_time)
01102         max_time = x[i];
01103     }
01104     n++;
01105   }
01106 
01107   /*
01108    * We are erring and asserting here because this can only happen
01109    * in codepaths other than startup. The startup state parsing code
01110    * performs this same check, and resets state if it hits it. If we
01111    * hit it at runtime, something serious has gone wrong.
01112    */
01113   if (n!=cbt->total_build_times) {
01114     log_err(LD_CIRC, "Discrepancy in build times count: %d vs %d", n,
01115             cbt->total_build_times);
01116   }
01117   tor_assert(n==cbt->total_build_times);
01118 
01119   if (max_time <= 0) {
01120     /* This can happen if Xm is actually the *maximum* value in the set.
01121      * It can also happen if we've abandoned every single circuit somehow.
01122      * In either case, tell the caller not to compute a new build timeout. */
01123     log_warn(LD_BUG,
01124              "Could not determine largest build time (%d). "
01125              "Xm is %dms and we've abandoned %d out of %d circuits.", max_time,
01126              cbt->Xm, abandoned_count, n);
01127     return 0;
01128   }
01129 
01130   a += abandoned_count*tor_mathlog(max_time);
01131 
01132   a -= n*tor_mathlog(cbt->Xm);
01133   // Estimator comes from Eq #4 in:
01134   // "Bayesian estimation based on trimmed samples from Pareto populations"
01135   // by Arturo J. Fernández. We are right-censored only.
01136   a = (n-abandoned_count)/a;
01137 
01138   cbt->alpha = a;
01139 
01140   return 1;
01141 }
01142 
01159 double
01160 circuit_build_times_calculate_timeout(circuit_build_times_t *cbt,
01161                                       double quantile)
01162 {
01163   double ret;
01164   tor_assert(quantile >= 0);
01165   tor_assert(1.0-quantile > 0);
01166   tor_assert(cbt->Xm > 0);
01167 
01168   ret = cbt->Xm/pow(1.0-quantile,1.0/cbt->alpha);
01169   if (ret > INT32_MAX) {
01170     ret = INT32_MAX;
01171   }
01172   tor_assert(ret > 0);
01173   return ret;
01174 }
01175 
01177 double
01178 circuit_build_times_cdf(circuit_build_times_t *cbt, double x)
01179 {
01180   double ret;
01181   tor_assert(cbt->Xm > 0);
01182   ret = 1.0-pow(cbt->Xm/x,cbt->alpha);
01183   tor_assert(0 <= ret && ret <= 1.0);
01184   return ret;
01185 }
01186 
01193 build_time_t
01194 circuit_build_times_generate_sample(circuit_build_times_t *cbt,
01195                                     double q_lo, double q_hi)
01196 {
01197   double randval = crypto_rand_double();
01198   build_time_t ret;
01199   double u;
01200 
01201   /* Generate between [q_lo, q_hi) */
01202   /*XXXX This is what nextafter is supposed to be for; we should use it on the
01203    * platforms that support it. */
01204   q_hi -= 1.0/(INT32_MAX);
01205 
01206   tor_assert(q_lo >= 0);
01207   tor_assert(q_hi < 1);
01208   tor_assert(q_lo < q_hi);
01209 
01210   u = q_lo + (q_hi-q_lo)*randval;
01211 
01212   tor_assert(0 <= u && u < 1.0);
01213   /* circuit_build_times_calculate_timeout returns <= INT32_MAX */
01214   ret = (build_time_t)
01215     tor_lround(circuit_build_times_calculate_timeout(cbt, u));
01216   tor_assert(ret > 0);
01217   return ret;
01218 }
01219 
01224 void
01225 circuit_build_times_initial_alpha(circuit_build_times_t *cbt,
01226                                   double quantile, double timeout_ms)
01227 {
01228   // Q(u) = Xm/((1-u)^(1/a))
01229   // Q(0.8) = Xm/((1-0.8))^(1/a)) = CircBuildTimeout
01230   // CircBuildTimeout = Xm/((1-0.8))^(1/a))
01231   // CircBuildTimeout = Xm*((1-0.8))^(-1/a))
01232   // ln(CircBuildTimeout) = ln(Xm)+ln(((1-0.8)))*(-1/a)
01233   // -ln(1-0.8)/(ln(CircBuildTimeout)-ln(Xm))=a
01234   tor_assert(quantile >= 0);
01235   tor_assert(cbt->Xm > 0);
01236   cbt->alpha = tor_mathlog(1.0-quantile)/
01237     (tor_mathlog(cbt->Xm)-tor_mathlog(timeout_ms));
01238   tor_assert(cbt->alpha > 0);
01239 }
01240 
01244 int
01245 circuit_build_times_needs_circuits(circuit_build_times_t *cbt)
01246 {
01247   /* Return true if < MIN_CIRCUITS_TO_OBSERVE */
01248   return !circuit_build_times_enough_to_compute(cbt);
01249 }
01250 
01255 int
01256 circuit_build_times_needs_circuits_now(circuit_build_times_t *cbt)
01257 {
01258   return circuit_build_times_needs_circuits(cbt) &&
01259     approx_time()-cbt->last_circ_at > circuit_build_times_test_frequency();
01260 }
01261 
01272 void
01273 circuit_build_times_network_is_live(circuit_build_times_t *cbt)
01274 {
01275   time_t now = approx_time();
01276   if (cbt->liveness.nonlive_timeouts > 0) {
01277     log_notice(LD_CIRC,
01278                "Tor now sees network activity. Restoring circuit build "
01279                "timeout recording. Network was down for %d seconds "
01280                "during %d circuit attempts.",
01281                (int)(now - cbt->liveness.network_last_live),
01282                cbt->liveness.nonlive_timeouts);
01283   }
01284   cbt->liveness.network_last_live = now;
01285   cbt->liveness.nonlive_timeouts = 0;
01286 }
01287 
01296 void
01297 circuit_build_times_network_circ_success(circuit_build_times_t *cbt)
01298 {
01299   /* Check for NULLness because we might not be using adaptive timeouts */
01300   if (cbt->liveness.timeouts_after_firsthop &&
01301       cbt->liveness.num_recent_circs > 0) {
01302     cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
01303       = 0;
01304     cbt->liveness.after_firsthop_idx++;
01305     cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
01306   }
01307 }
01308 
01317 static void
01318 circuit_build_times_network_timeout(circuit_build_times_t *cbt,
01319                                     int did_onehop)
01320 {
01321   /* Check for NULLness because we might not be using adaptive timeouts */
01322   if (cbt->liveness.timeouts_after_firsthop &&
01323       cbt->liveness.num_recent_circs > 0) {
01324     if (did_onehop) {
01325       cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
01326         = 1;
01327       cbt->liveness.after_firsthop_idx++;
01328       cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
01329     }
01330   }
01331 }
01332 
01341 static void
01342 circuit_build_times_network_close(circuit_build_times_t *cbt,
01343                                     int did_onehop, time_t start_time)
01344 {
01345   time_t now = time(NULL);
01346   /*
01347    * Check if this is a timeout that was for a circuit that spent its
01348    * entire existence during a time where we have had no network activity.
01349    */
01350   if (cbt->liveness.network_last_live < start_time) {
01351     if (did_onehop) {
01352       char last_live_buf[ISO_TIME_LEN+1];
01353       char start_time_buf[ISO_TIME_LEN+1];
01354       char now_buf[ISO_TIME_LEN+1];
01355       format_local_iso_time(last_live_buf, cbt->liveness.network_last_live);
01356       format_local_iso_time(start_time_buf, start_time);
01357       format_local_iso_time(now_buf, now);
01358       log_warn(LD_BUG,
01359                "Circuit somehow completed a hop while the network was "
01360                "not live. Network was last live at %s, but circuit launched "
01361                "at %s. It's now %s.", last_live_buf, start_time_buf,
01362                now_buf);
01363     }
01364     cbt->liveness.nonlive_timeouts++;
01365     if (cbt->liveness.nonlive_timeouts == 1) {
01366       log_notice(LD_CIRC,
01367                  "Tor has not observed any network activity for the past %d "
01368                  "seconds. Disabling circuit build timeout recording.",
01369                  (int)(now - cbt->liveness.network_last_live));
01370     } else {
01371       log_info(LD_CIRC,
01372              "Got non-live timeout. Current count is: %d",
01373              cbt->liveness.nonlive_timeouts);
01374     }
01375   }
01376 }
01377 
01388 int
01389 circuit_build_times_network_check_live(circuit_build_times_t *cbt)
01390 {
01391   if (cbt->liveness.nonlive_timeouts > 0) {
01392     return 0;
01393   }
01394 
01395   return 1;
01396 }
01397 
01408 int
01409 circuit_build_times_network_check_changed(circuit_build_times_t *cbt)
01410 {
01411   int total_build_times = cbt->total_build_times;
01412   int timeout_count=0;
01413   int i;
01414 
01415   if (cbt->liveness.timeouts_after_firsthop &&
01416       cbt->liveness.num_recent_circs > 0) {
01417     /* how many of our recent circuits made it to the first hop but then
01418      * timed out? */
01419     for (i = 0; i < cbt->liveness.num_recent_circs; i++) {
01420       timeout_count += cbt->liveness.timeouts_after_firsthop[i];
01421     }
01422   }
01423 
01424   /* If 80% of our recent circuits are timing out after the first hop,
01425    * we need to re-estimate a new initial alpha and timeout. */
01426   if (timeout_count < circuit_build_times_max_timeouts()) {
01427     return 0;
01428   }
01429 
01430   circuit_build_times_reset(cbt);
01431   if (cbt->liveness.timeouts_after_firsthop &&
01432       cbt->liveness.num_recent_circs > 0) {
01433     memset(cbt->liveness.timeouts_after_firsthop, 0,
01434             sizeof(*cbt->liveness.timeouts_after_firsthop)*
01435             cbt->liveness.num_recent_circs);
01436   }
01437   cbt->liveness.after_firsthop_idx = 0;
01438 
01439   /* Check to see if this has happened before. If so, double the timeout
01440    * to give people on abysmally bad network connections a shot at access */
01441   if (cbt->timeout_ms >= circuit_build_times_get_initial_timeout()) {
01442     if (cbt->timeout_ms > INT32_MAX/2 || cbt->close_ms > INT32_MAX/2) {
01443       log_warn(LD_CIRC, "Insanely large circuit build timeout value. "
01444               "(timeout = %fmsec, close = %fmsec)",
01445                cbt->timeout_ms, cbt->close_ms);
01446     } else {
01447       cbt->timeout_ms *= 2;
01448       cbt->close_ms *= 2;
01449     }
01450   } else {
01451     cbt->close_ms = cbt->timeout_ms
01452                   = circuit_build_times_get_initial_timeout();
01453   }
01454 
01455   control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
01456 
01457   log_notice(LD_CIRC,
01458             "Your network connection speed appears to have changed. Resetting "
01459             "timeout to %lds after %d timeouts and %d buildtimes.",
01460             tor_lround(cbt->timeout_ms/1000), timeout_count,
01461             total_build_times);
01462 
01463   return 1;
01464 }
01465 
01469 double
01470 circuit_build_times_timeout_rate(const circuit_build_times_t *cbt)
01471 {
01472   int i=0,timeouts=0;
01473   for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
01474     if (cbt->circuit_build_times[i] >= cbt->timeout_ms) {
01475        timeouts++;
01476     }
01477   }
01478 
01479   if (!cbt->total_build_times)
01480     return 0;
01481 
01482   return ((double)timeouts)/cbt->total_build_times;
01483 }
01484 
01488 double
01489 circuit_build_times_close_rate(const circuit_build_times_t *cbt)
01490 {
01491   int i=0,closed=0;
01492   for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
01493     if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) {
01494        closed++;
01495     }
01496   }
01497 
01498   if (!cbt->total_build_times)
01499     return 0;
01500 
01501   return ((double)closed)/cbt->total_build_times;
01502 }
01503 
01510 int
01511 circuit_build_times_count_close(circuit_build_times_t *cbt,
01512                                 int did_onehop,
01513                                 time_t start_time)
01514 {
01515   if (circuit_build_times_disabled()) {
01516     cbt->close_ms = cbt->timeout_ms
01517                   = circuit_build_times_get_initial_timeout();
01518     return 0;
01519   }
01520 
01521   /* Record this force-close to help determine if the network is dead */
01522   circuit_build_times_network_close(cbt, did_onehop, start_time);
01523 
01524   /* Only count timeouts if network is live.. */
01525   if (!circuit_build_times_network_check_live(cbt)) {
01526     return 0;
01527   }
01528 
01529   circuit_build_times_add_time(cbt, CBT_BUILD_ABANDONED);
01530   return 1;
01531 }
01532 
01542 void
01543 circuit_build_times_count_timeout(circuit_build_times_t *cbt,
01544                                   int did_onehop)
01545 {
01546   if (circuit_build_times_disabled()) {
01547     cbt->close_ms = cbt->timeout_ms
01548                   = circuit_build_times_get_initial_timeout();
01549     return;
01550   }
01551 
01552   /* Register the fact that a timeout just occurred. */
01553   circuit_build_times_network_timeout(cbt, did_onehop);
01554 
01555   /* If there are a ton of timeouts, we should reset
01556    * the circuit build timeout. */
01557   circuit_build_times_network_check_changed(cbt);
01558 }
01559 
01564 static int
01565 circuit_build_times_set_timeout_worker(circuit_build_times_t *cbt)
01566 {
01567   build_time_t max_time;
01568   if (!circuit_build_times_enough_to_compute(cbt))
01569     return 0;
01570 
01571   if (!circuit_build_times_update_alpha(cbt))
01572     return 0;
01573 
01574   cbt->timeout_ms = circuit_build_times_calculate_timeout(cbt,
01575                                 circuit_build_times_quantile_cutoff());
01576 
01577   cbt->close_ms = circuit_build_times_calculate_timeout(cbt,
01578                                 circuit_build_times_close_quantile());
01579 
01580   max_time = circuit_build_times_max(cbt);
01581 
01582   /* Sometimes really fast guard nodes give us such a steep curve
01583    * that this ends up being not that much greater than timeout_ms.
01584    * Make it be at least 1 min to handle this case. */
01585   cbt->close_ms = MAX(cbt->close_ms, circuit_build_times_initial_timeout());
01586 
01587   if (cbt->timeout_ms > max_time) {
01588     log_info(LD_CIRC,
01589                "Circuit build timeout of %dms is beyond the maximum build "
01590                "time we have ever observed. Capping it to %dms.",
01591                (int)cbt->timeout_ms, max_time);
01592     cbt->timeout_ms = max_time;
01593   }
01594 
01595   if (max_time < INT32_MAX/2 && cbt->close_ms > 2*max_time) {
01596     log_info(LD_CIRC,
01597                "Circuit build measurement period of %dms is more than twice "
01598                "the maximum build time we have ever observed. Capping it to "
01599                "%dms.", (int)cbt->close_ms, 2*max_time);
01600     cbt->close_ms = 2*max_time;
01601   }
01602 
01603   cbt->have_computed_timeout = 1;
01604   return 1;
01605 }
01606 
01611 void
01612 circuit_build_times_set_timeout(circuit_build_times_t *cbt)
01613 {
01614   long prev_timeout = tor_lround(cbt->timeout_ms/1000);
01615   double timeout_rate;
01616 
01617   /*
01618    * Just return if we aren't using adaptive timeouts
01619    */
01620   if (circuit_build_times_disabled())
01621     return;
01622 
01623   if (!circuit_build_times_set_timeout_worker(cbt))
01624     return;
01625 
01626   if (cbt->timeout_ms < circuit_build_times_min_timeout()) {
01627     log_warn(LD_CIRC, "Set buildtimeout to low value %fms. Setting to %dms",
01628              cbt->timeout_ms, circuit_build_times_min_timeout());
01629     cbt->timeout_ms = circuit_build_times_min_timeout();
01630     if (cbt->close_ms < cbt->timeout_ms) {
01631       /* This shouldn't happen because of MAX() in timeout_worker above,
01632        * but doing it just in case */
01633       cbt->close_ms = circuit_build_times_initial_timeout();
01634     }
01635   }
01636 
01637   control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_COMPUTED);
01638 
01639   timeout_rate = circuit_build_times_timeout_rate(cbt);
01640 
01641   if (prev_timeout > tor_lround(cbt->timeout_ms/1000)) {
01642     log_info(LD_CIRC,
01643                "Based on %d circuit times, it looks like we don't need to "
01644                "wait so long for circuits to finish. We will now assume a "
01645                "circuit is too slow to use after waiting %ld seconds.",
01646                cbt->total_build_times,
01647                tor_lround(cbt->timeout_ms/1000));
01648     log_info(LD_CIRC,
01649              "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
01650              cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
01651              timeout_rate);
01652   } else if (prev_timeout < tor_lround(cbt->timeout_ms/1000)) {
01653     log_info(LD_CIRC,
01654                "Based on %d circuit times, it looks like we need to wait "
01655                "longer for circuits to finish. We will now assume a "
01656                "circuit is too slow to use after waiting %ld seconds.",
01657                cbt->total_build_times,
01658                tor_lround(cbt->timeout_ms/1000));
01659     log_info(LD_CIRC,
01660              "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
01661              cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
01662              timeout_rate);
01663   } else {
01664     log_info(LD_CIRC,
01665              "Set circuit build timeout to %lds (%fms, %fms, Xm: %d, a: %f,"
01666              " r: %f) based on %d circuit times",
01667              tor_lround(cbt->timeout_ms/1000),
01668              cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, timeout_rate,
01669              cbt->total_build_times);
01670   }
01671 }
01672 
01679 static circid_t
01680 get_unique_circ_id_by_conn(or_connection_t *conn)
01681 {
01682   circid_t test_circ_id;
01683   circid_t attempts=0;
01684   circid_t high_bit;
01685 
01686   tor_assert(conn);
01687   if (conn->circ_id_type == CIRC_ID_TYPE_NEITHER) {
01688     log_warn(LD_BUG, "Trying to pick a circuit ID for a connection from "
01689              "a client with no identity.");
01690     return 0;
01691   }
01692   high_bit = (conn->circ_id_type == CIRC_ID_TYPE_HIGHER) ? 1<<15 : 0;
01693   do {
01694     /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
01695      * circID such that (high_bit|test_circ_id) is not already used. */
01696     test_circ_id = conn->next_circ_id++;
01697     if (test_circ_id == 0 || test_circ_id >= 1<<15) {
01698       test_circ_id = 1;
01699       conn->next_circ_id = 2;
01700     }
01701     if (++attempts > 1<<15) {
01702       /* Make sure we don't loop forever if all circ_id's are used. This
01703        * matters because it's an external DoS opportunity.
01704        */
01705       log_warn(LD_CIRC,"No unused circ IDs. Failing.");
01706       return 0;
01707     }
01708     test_circ_id |= high_bit;
01709   } while (circuit_id_in_use_on_orconn(test_circ_id, conn));
01710   return test_circ_id;
01711 }
01712 
01720 static char *
01721 circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
01722 {
01723   crypt_path_t *hop;
01724   smartlist_t *elements;
01725   const char *states[] = {"closed", "waiting for keys", "open"};
01726   char *s;
01727 
01728   elements = smartlist_new();
01729 
01730   if (verbose) {
01731     const char *nickname = build_state_get_exit_nickname(circ->build_state);
01732     smartlist_add_asprintf(elements, "%s%s circ (length %d%s%s):",
01733                  circ->build_state->is_internal ? "internal" : "exit",
01734                  circ->build_state->need_uptime ? " (high-uptime)" : "",
01735                  circ->build_state->desired_path_len,
01736                  circ->_base.state == CIRCUIT_STATE_OPEN ? "" : ", last hop ",
01737                  circ->_base.state == CIRCUIT_STATE_OPEN ? "" :
01738                  (nickname?nickname:"*unnamed*"));
01739   }
01740 
01741   hop = circ->cpath;
01742   do {
01743     char *elt;
01744     const char *id;
01745     const node_t *node;
01746     if (!hop)
01747       break;
01748     if (!verbose && hop->state != CPATH_STATE_OPEN)
01749       break;
01750     if (!hop->extend_info)
01751       break;
01752     id = hop->extend_info->identity_digest;
01753     if (verbose_names) {
01754       elt = tor_malloc(MAX_VERBOSE_NICKNAME_LEN+1);
01755       if ((node = node_get_by_id(id))) {
01756         node_get_verbose_nickname(node, elt);
01757       } else if (is_legal_nickname(hop->extend_info->nickname)) {
01758         elt[0] = '$';
01759         base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
01760         elt[HEX_DIGEST_LEN+1]= '~';
01761         strlcpy(elt+HEX_DIGEST_LEN+2,
01762                 hop->extend_info->nickname, MAX_NICKNAME_LEN+1);
01763       } else {
01764         elt[0] = '$';
01765         base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
01766       }
01767     } else { /* ! verbose_names */
01768       node = node_get_by_id(id);
01769       if (node && node_is_named(node)) {
01770         elt = tor_strdup(node_get_nickname(node));
01771       } else {
01772         elt = tor_malloc(HEX_DIGEST_LEN+2);
01773         elt[0] = '$';
01774         base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
01775       }
01776     }
01777     tor_assert(elt);
01778     if (verbose) {
01779       tor_assert(hop->state <= 2);
01780       smartlist_add_asprintf(elements,"%s(%s)",elt,states[hop->state]);
01781       tor_free(elt);
01782     } else {
01783       smartlist_add(elements, elt);
01784     }
01785     hop = hop->next;
01786   } while (hop != circ->cpath);
01787 
01788   s = smartlist_join_strings(elements, verbose?" ":",", 0, NULL);
01789   SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
01790   smartlist_free(elements);
01791   return s;
01792 }
01793 
01799 char *
01800 circuit_list_path(origin_circuit_t *circ, int verbose)
01801 {
01802   return circuit_list_path_impl(circ, verbose, 0);
01803 }
01804 
01808 char *
01809 circuit_list_path_for_controller(origin_circuit_t *circ)
01810 {
01811   return circuit_list_path_impl(circ, 0, 1);
01812 }
01813 
01818 void
01819 circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ)
01820 {
01821   char *s = circuit_list_path(circ,1);
01822   tor_log(severity,domain,"%s",s);
01823   tor_free(s);
01824 }
01825 
01831 /* XXXX Someday we should learn from OR circuits too. */
01832 void
01833 circuit_rep_hist_note_result(origin_circuit_t *circ)
01834 {
01835   crypt_path_t *hop;
01836   const char *prev_digest = NULL;
01837   hop = circ->cpath;
01838   if (!hop) /* circuit hasn't started building yet. */
01839     return;
01840   if (server_mode(get_options())) {
01841     const routerinfo_t *me = router_get_my_routerinfo();
01842     if (!me)
01843       return;
01844     prev_digest = me->cache_info.identity_digest;
01845   }
01846   do {
01847     const node_t *node = node_get_by_id(hop->extend_info->identity_digest);
01848     if (node) { /* Why do we check this?  We know the identity. -NM XXXX */
01849       if (prev_digest) {
01850         if (hop->state == CPATH_STATE_OPEN)
01851           rep_hist_note_extend_succeeded(prev_digest, node->identity);
01852         else {
01853           rep_hist_note_extend_failed(prev_digest, node->identity);
01854           break;
01855         }
01856       }
01857       prev_digest = node->identity;
01858     } else {
01859       prev_digest = NULL;
01860     }
01861     hop=hop->next;
01862   } while (hop!=circ->cpath);
01863 }
01864 
01867 static int
01868 onion_populate_cpath(origin_circuit_t *circ)
01869 {
01870   int r;
01871  again:
01872   r = onion_extend_cpath(circ);
01873   if (r < 0) {
01874     log_info(LD_CIRC,"Generating cpath hop failed.");
01875     return -1;
01876   }
01877   if (r == 0)
01878     goto again;
01879   return 0; /* if r == 1 */
01880 }
01881 
01885 origin_circuit_t *
01886 origin_circuit_init(uint8_t purpose, int flags)
01887 {
01888   /* sets circ->p_circ_id and circ->p_conn */
01889   origin_circuit_t *circ = origin_circuit_new();
01890   circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OR_WAIT);
01891   circ->build_state = tor_malloc_zero(sizeof(cpath_build_state_t));
01892   circ->build_state->onehop_tunnel =
01893     ((flags & CIRCLAUNCH_ONEHOP_TUNNEL) ? 1 : 0);
01894   circ->build_state->need_uptime =
01895     ((flags & CIRCLAUNCH_NEED_UPTIME) ? 1 : 0);
01896   circ->build_state->need_capacity =
01897     ((flags & CIRCLAUNCH_NEED_CAPACITY) ? 1 : 0);
01898   circ->build_state->is_internal =
01899     ((flags & CIRCLAUNCH_IS_INTERNAL) ? 1 : 0);
01900   circ->_base.purpose = purpose;
01901   return circ;
01902 }
01903 
01911 origin_circuit_t *
01912 circuit_establish_circuit(uint8_t purpose, extend_info_t *exit, int flags)
01913 {
01914   origin_circuit_t *circ;
01915   int err_reason = 0;
01916 
01917   circ = origin_circuit_init(purpose, flags);
01918 
01919   if (onion_pick_cpath_exit(circ, exit) < 0 ||
01920       onion_populate_cpath(circ) < 0) {
01921     circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_NOPATH);
01922     return NULL;
01923   }
01924 
01925   control_event_circuit_status(circ, CIRC_EVENT_LAUNCHED, 0);
01926 
01927   if ((err_reason = circuit_handle_first_hop(circ)) < 0) {
01928     circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
01929     return NULL;
01930   }
01931   return circ;
01932 }
01933 
01938 int
01939 circuit_handle_first_hop(origin_circuit_t *circ)
01940 {
01941   crypt_path_t *firsthop;
01942   or_connection_t *n_conn;
01943   int err_reason = 0;
01944   const char *msg = NULL;
01945   int should_launch = 0;
01946 
01947   firsthop = onion_next_hop_in_cpath(circ->cpath);
01948   tor_assert(firsthop);
01949   tor_assert(firsthop->extend_info);
01950 
01951   /* now see if we're already connected to the first OR in 'route' */
01952   log_debug(LD_CIRC,"Looking for firsthop '%s:%u'",
01953             fmt_addr(&firsthop->extend_info->addr),
01954             firsthop->extend_info->port);
01955 
01956   n_conn = connection_or_get_for_extend(firsthop->extend_info->identity_digest,
01957                                         &firsthop->extend_info->addr,
01958                                         &msg,
01959                                         &should_launch);
01960 
01961   if (!n_conn) {
01962     /* not currently connected in a useful way. */
01963     log_info(LD_CIRC, "Next router is %s: %s",
01964              safe_str_client(extend_info_describe(firsthop->extend_info)),
01965              msg?msg:"???");
01966     circ->_base.n_hop = extend_info_dup(firsthop->extend_info);
01967 
01968     if (should_launch) {
01969       if (circ->build_state->onehop_tunnel)
01970         control_event_bootstrap(BOOTSTRAP_STATUS_CONN_DIR, 0);
01971       n_conn = connection_or_connect(&firsthop->extend_info->addr,
01972                                      firsthop->extend_info->port,
01973                                      firsthop->extend_info->identity_digest);
01974       if (!n_conn) { /* connect failed, forget the whole thing */
01975         log_info(LD_CIRC,"connect to firsthop failed. Closing.");
01976         return -END_CIRC_REASON_CONNECTFAILED;
01977       }
01978     }
01979 
01980     log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
01981     /* return success. The onion/circuit/etc will be taken care of
01982      * automatically (may already have been) whenever n_conn reaches
01983      * OR_CONN_STATE_OPEN.
01984      */
01985     return 0;
01986   } else { /* it's already open. use it. */
01987     tor_assert(!circ->_base.n_hop);
01988     circ->_base.n_conn = n_conn;
01989     log_debug(LD_CIRC,"Conn open. Delivering first onion skin.");
01990     if ((err_reason = circuit_send_next_onion_skin(circ)) < 0) {
01991       log_info(LD_CIRC,"circuit_send_next_onion_skin failed.");
01992       return err_reason;
01993     }
01994   }
01995   return 0;
01996 }
01997 
02003 void
02004 circuit_n_conn_done(or_connection_t *or_conn, int status)
02005 {
02006   smartlist_t *pending_circs;
02007   int err_reason = 0;
02008 
02009   log_debug(LD_CIRC,"or_conn to %s/%s, status=%d",
02010             or_conn->nickname ? or_conn->nickname : "NULL",
02011             or_conn->_base.address, status);
02012 
02013   pending_circs = smartlist_new();
02014   circuit_get_all_pending_on_or_conn(pending_circs, or_conn);
02015 
02016   SMARTLIST_FOREACH_BEGIN(pending_circs, circuit_t *, circ)
02017     {
02018       /* These checks are redundant wrt get_all_pending_on_or_conn, but I'm
02019        * leaving them in in case it's possible for the status of a circuit to
02020        * change as we're going down the list. */
02021       if (circ->marked_for_close || circ->n_conn || !circ->n_hop ||
02022           circ->state != CIRCUIT_STATE_OR_WAIT)
02023         continue;
02024 
02025       if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
02026         /* Look at addr/port. This is an unkeyed connection. */
02027         if (!tor_addr_eq(&circ->n_hop->addr, &or_conn->_base.addr) ||
02028             circ->n_hop->port != or_conn->_base.port)
02029           continue;
02030       } else {
02031         /* We expected a key. See if it's the right one. */
02032         if (tor_memneq(or_conn->identity_digest,
02033                    circ->n_hop->identity_digest, DIGEST_LEN))
02034           continue;
02035       }
02036       if (!status) { /* or_conn failed; close circ */
02037         log_info(LD_CIRC,"or_conn failed. Closing circ.");
02038         circuit_mark_for_close(circ, END_CIRC_REASON_OR_CONN_CLOSED);
02039         continue;
02040       }
02041       log_debug(LD_CIRC, "Found circ, sending create cell.");
02042       /* circuit_deliver_create_cell will set n_circ_id and add us to
02043        * orconn_circuid_circuit_map, so we don't need to call
02044        * set_circid_orconn here. */
02045       circ->n_conn = or_conn;
02046       extend_info_free(circ->n_hop);
02047       circ->n_hop = NULL;
02048 
02049       if (CIRCUIT_IS_ORIGIN(circ)) {
02050         if ((err_reason =
02051              circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ))) < 0) {
02052           log_info(LD_CIRC,
02053                    "send_next_onion_skin failed; circuit marked for closing.");
02054           circuit_mark_for_close(circ, -err_reason);
02055           continue;
02056           /* XXX could this be bad, eg if next_onion_skin failed because conn
02057            *     died? */
02058         }
02059       } else {
02060         /* pull the create cell out of circ->onionskin, and send it */
02061         tor_assert(circ->n_conn_onionskin);
02062         if (circuit_deliver_create_cell(circ,CELL_CREATE,
02063                                         circ->n_conn_onionskin)<0) {
02064           circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
02065           continue;
02066         }
02067         tor_free(circ->n_conn_onionskin);
02068         circuit_set_state(circ, CIRCUIT_STATE_OPEN);
02069       }
02070     }
02071   SMARTLIST_FOREACH_END(circ);
02072 
02073   smartlist_free(pending_circs);
02074 }
02075 
02083 static int
02084 circuit_deliver_create_cell(circuit_t *circ, uint8_t cell_type,
02085                             const char *payload)
02086 {
02087   cell_t cell;
02088   circid_t id;
02089 
02090   tor_assert(circ);
02091   tor_assert(circ->n_conn);
02092   tor_assert(payload);
02093   tor_assert(cell_type == CELL_CREATE || cell_type == CELL_CREATE_FAST);
02094 
02095   id = get_unique_circ_id_by_conn(circ->n_conn);
02096   if (!id) {
02097     log_warn(LD_CIRC,"failed to get unique circID.");
02098     return -1;
02099   }
02100   log_debug(LD_CIRC,"Chosen circID %u.", id);
02101   circuit_set_n_circid_orconn(circ, id, circ->n_conn);
02102 
02103   memset(&cell, 0, sizeof(cell_t));
02104   cell.command = cell_type;
02105   cell.circ_id = circ->n_circ_id;
02106 
02107   memcpy(cell.payload, payload, ONIONSKIN_CHALLENGE_LEN);
02108   append_cell_to_circuit_queue(circ, circ->n_conn, &cell,
02109                                CELL_DIRECTION_OUT, 0);
02110 
02111   if (CIRCUIT_IS_ORIGIN(circ)) {
02112     /* mark it so it gets better rate limiting treatment. */
02113     circ->n_conn->client_used = time(NULL);
02114   }
02115 
02116   return 0;
02117 }
02118 
02122 int
02123 inform_testing_reachability(void)
02124 {
02125   char dirbuf[128];
02126   const routerinfo_t *me = router_get_my_routerinfo();
02127   if (!me)
02128     return 0;
02129   control_event_server_status(LOG_NOTICE,
02130                               "CHECKING_REACHABILITY ORADDRESS=%s:%d",
02131                               me->address, me->or_port);
02132   if (me->dir_port) {
02133     tor_snprintf(dirbuf, sizeof(dirbuf), " and DirPort %s:%d",
02134                  me->address, me->dir_port);
02135     control_event_server_status(LOG_NOTICE,
02136                                 "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
02137                                 me->address, me->dir_port);
02138   }
02139   log_notice(LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... "
02140                          "(this may take up to %d minutes -- look for log "
02141                          "messages indicating success)",
02142       me->address, me->or_port,
02143       me->dir_port ? dirbuf : "",
02144       me->dir_port ? "are" : "is",
02145       TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT/60);
02146 
02147   return 1;
02148 }
02149 
02152 static INLINE int
02153 should_use_create_fast_for_circuit(origin_circuit_t *circ)
02154 {
02155   const or_options_t *options = get_options();
02156   tor_assert(circ->cpath);
02157   tor_assert(circ->cpath->extend_info);
02158 
02159   if (!circ->cpath->extend_info->onion_key)
02160     return 1; /* our hand is forced: only a create_fast will work. */
02161   if (!options->FastFirstHopPK)
02162     return 0; /* we prefer to avoid create_fast */
02163   if (public_server_mode(options)) {
02164     /* We're a server, and we know an onion key. We can choose.
02165      * Prefer to blend our circuit into the other circuits we are
02166      * creating on behalf of others. */
02167     return 0;
02168   }
02169 
02170   return 1;
02171 }
02172 
02178 int
02179 circuit_timeout_want_to_count_circ(origin_circuit_t *circ)
02180 {
02181   return !circ->has_opened
02182           && circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN;
02183 }
02184 
02195 int
02196 circuit_send_next_onion_skin(origin_circuit_t *circ)
02197 {
02198   crypt_path_t *hop;
02199   const node_t *node;
02200   char payload[2+4+DIGEST_LEN+ONIONSKIN_CHALLENGE_LEN];
02201   char *onionskin;
02202   size_t payload_len;
02203 
02204   tor_assert(circ);
02205 
02206   if (circ->cpath->state == CPATH_STATE_CLOSED) {
02207     int fast;
02208     uint8_t cell_type;
02209     log_debug(LD_CIRC,"First skin; sending create cell.");
02210     if (circ->build_state->onehop_tunnel)
02211       control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE, 0);
02212     else
02213       control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE, 0);
02214 
02215     node = node_get_by_id(circ->_base.n_conn->identity_digest);
02216     fast = should_use_create_fast_for_circuit(circ);
02217     if (!fast) {
02218       /* We are an OR and we know the right onion key: we should
02219        * send an old slow create cell.
02220        */
02221       cell_type = CELL_CREATE;
02222       if (onion_skin_create(circ->cpath->extend_info->onion_key,
02223                             &(circ->cpath->dh_handshake_state),
02224                             payload) < 0) {
02225         log_warn(LD_CIRC,"onion_skin_create (first hop) failed.");
02226         return - END_CIRC_REASON_INTERNAL;
02227       }
02228       note_request("cell: create", 1);
02229     } else {
02230       /* We are not an OR, and we're building the first hop of a circuit to a
02231        * new OR: we can be speedy and use CREATE_FAST to save an RSA operation
02232        * and a DH operation. */
02233       cell_type = CELL_CREATE_FAST;
02234       memset(payload, 0, sizeof(payload));
02235       crypto_rand((char*) circ->cpath->fast_handshake_state,
02236                   sizeof(circ->cpath->fast_handshake_state));
02237       memcpy(payload, circ->cpath->fast_handshake_state,
02238              sizeof(circ->cpath->fast_handshake_state));
02239       note_request("cell: create fast", 1);
02240     }
02241 
02242     if (circuit_deliver_create_cell(TO_CIRCUIT(circ), cell_type, payload) < 0)
02243       return - END_CIRC_REASON_RESOURCELIMIT;
02244 
02245     circ->cpath->state = CPATH_STATE_AWAITING_KEYS;
02246     circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
02247     log_info(LD_CIRC,"First hop: finished sending %s cell to '%s'",
02248              fast ? "CREATE_FAST" : "CREATE",
02249              node ? node_describe(node) : "<unnamed>");
02250   } else {
02251     tor_assert(circ->cpath->state == CPATH_STATE_OPEN);
02252     tor_assert(circ->_base.state == CIRCUIT_STATE_BUILDING);
02253     log_debug(LD_CIRC,"starting to send subsequent skin.");
02254     hop = onion_next_hop_in_cpath(circ->cpath);
02255     if (!hop) {
02256       /* done building the circuit. whew. */
02257       circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
02258       if (circuit_timeout_want_to_count_circ(circ)) {
02259         struct timeval end;
02260         long timediff;
02261         tor_gettimeofday(&end);
02262         timediff = tv_mdiff(&circ->_base.timestamp_created, &end);
02263 
02264         /*
02265          * If the circuit build time is much greater than we would have cut
02266          * it off at, we probably had a suspend event along this codepath,
02267          * and we should discard the value.
02268          */
02269         if (timediff < 0 || timediff > 2*circ_times.close_ms+1000) {
02270           log_notice(LD_CIRC, "Strange value for circuit build time: %ldmsec. "
02271                               "Assuming clock jump. Purpose %d (%s)", timediff,
02272                      circ->_base.purpose,
02273                      circuit_purpose_to_string(circ->_base.purpose));
02274         } else if (!circuit_build_times_disabled()) {
02275           /* Only count circuit times if the network is live */
02276           if (circuit_build_times_network_check_live(&circ_times)) {
02277             circuit_build_times_add_time(&circ_times, (build_time_t)timediff);
02278             circuit_build_times_set_timeout(&circ_times);
02279           }
02280 
02281           if (circ->_base.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
02282             circuit_build_times_network_circ_success(&circ_times);
02283           }
02284         }
02285       }
02286       log_info(LD_CIRC,"circuit built!");
02287       circuit_reset_failure_count(0);
02288       /* Don't count cannibalized or onehop circs for path bias */
02289       if (circ->build_state->onehop_tunnel || circ->has_opened) {
02290         control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS, 0);
02291       } else {
02292         entry_guard_t *guard =
02293           entry_guard_get_by_id_digest(circ->_base.n_conn->identity_digest);
02294 
02295         if (guard) {
02296           guard->circuit_successes++;
02297 
02298           log_info(LD_PROTOCOL, "Got success count %u/%u for guard %s=%s",
02299                    guard->circuit_successes, guard->first_hops,
02300                    guard->nickname, hex_str(guard->identity, DIGEST_LEN));
02301 
02302           if (guard->first_hops < guard->circuit_successes) {
02303             log_warn(LD_BUG, "Unexpectedly high circuit_successes (%u/%u) "
02304                      "for guard %s",
02305                      guard->circuit_successes, guard->first_hops,
02306                      guard->nickname);
02307           }
02308         }
02309       }
02310       if (!can_complete_circuit && !circ->build_state->onehop_tunnel) {
02311         const or_options_t *options = get_options();
02312         can_complete_circuit=1;
02313         /* FFFF Log a count of known routers here */
02314         log_notice(LD_GENERAL,
02315             "Tor has successfully opened a circuit. "
02316             "Looks like client functionality is working.");
02317         control_event_bootstrap(BOOTSTRAP_STATUS_DONE, 0);
02318         control_event_client_status(LOG_NOTICE, "CIRCUIT_ESTABLISHED");
02319         clear_broken_connection_map(1);
02320         if (server_mode(options) && !check_whether_orport_reachable()) {
02321           inform_testing_reachability();
02322           consider_testing_reachability(1, 1);
02323         }
02324       }
02325       circuit_rep_hist_note_result(circ);
02326       circuit_has_opened(circ); /* do other actions as necessary */
02327 
02328       /* We're done with measurement circuits here. Just close them */
02329       if (circ->_base.purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT)
02330         circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED);
02331       return 0;
02332     }
02333 
02334     if (tor_addr_family(&hop->extend_info->addr) != AF_INET) {
02335       log_warn(LD_BUG, "Trying to extend to a non-IPv4 address.");
02336       return - END_CIRC_REASON_INTERNAL;
02337     }
02338 
02339     set_uint32(payload, tor_addr_to_ipv4n(&hop->extend_info->addr));
02340     set_uint16(payload+4, htons(hop->extend_info->port));
02341 
02342     onionskin = payload+2+4;
02343     memcpy(payload+2+4+ONIONSKIN_CHALLENGE_LEN,
02344            hop->extend_info->identity_digest, DIGEST_LEN);
02345     payload_len = 2+4+ONIONSKIN_CHALLENGE_LEN+DIGEST_LEN;
02346 
02347     if (onion_skin_create(hop->extend_info->onion_key,
02348                           &(hop->dh_handshake_state), onionskin) < 0) {
02349       log_warn(LD_CIRC,"onion_skin_create failed.");
02350       return - END_CIRC_REASON_INTERNAL;
02351     }
02352 
02353     log_info(LD_CIRC,"Sending extend relay cell.");
02354     note_request("cell: extend", 1);
02355     /* send it to hop->prev, because it will transfer
02356      * it to a create cell and then send to hop */
02357     if (relay_send_command_from_edge(0, TO_CIRCUIT(circ),
02358                                      RELAY_COMMAND_EXTEND,
02359                                      payload, payload_len, hop->prev) < 0)
02360       return 0; /* circuit is closed */
02361 
02362     hop->state = CPATH_STATE_AWAITING_KEYS;
02363   }
02364   return 0;
02365 }
02366 
02370 void
02371 circuit_note_clock_jumped(int seconds_elapsed)
02372 {
02373   int severity = server_mode(get_options()) ? LOG_WARN : LOG_NOTICE;
02374   tor_log(severity, LD_GENERAL, "Your system clock just jumped %d seconds %s; "
02375       "assuming established circuits no longer work.",
02376       seconds_elapsed >=0 ? seconds_elapsed : -seconds_elapsed,
02377       seconds_elapsed >=0 ? "forward" : "backward");
02378   control_event_general_status(LOG_WARN, "CLOCK_JUMPED TIME=%d",
02379                                seconds_elapsed);
02380   can_complete_circuit=0; /* so it'll log when it works again */
02381   control_event_client_status(severity, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
02382                               "CLOCK_JUMPED");
02383   circuit_mark_all_unused_circs();
02384   circuit_expire_all_dirty_circs();
02385 }
02386 
02395 int
02396 circuit_extend(cell_t *cell, circuit_t *circ)
02397 {
02398   or_connection_t *n_conn;
02399   relay_header_t rh;
02400   char *onionskin;
02401   char *id_digest=NULL;
02402   uint32_t n_addr32;
02403   uint16_t n_port;
02404   tor_addr_t n_addr;
02405   const char *msg = NULL;
02406   int should_launch = 0;
02407 
02408   if (circ->n_conn) {
02409     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
02410            "n_conn already set. Bug/attack. Closing.");
02411     return -1;
02412   }
02413   if (circ->n_hop) {
02414     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
02415            "conn to next hop already launched. Bug/attack. Closing.");
02416     return -1;
02417   }
02418 
02419   if (!server_mode(get_options())) {
02420     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
02421            "Got an extend cell, but running as a client. Closing.");
02422     return -1;
02423   }
02424 
02425   relay_header_unpack(&rh, cell->payload);
02426 
02427   if (rh.length < 4+2+ONIONSKIN_CHALLENGE_LEN+DIGEST_LEN) {
02428     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
02429            "Wrong length %d on extend cell. Closing circuit.",
02430            rh.length);
02431     return -1;
02432   }
02433 
02434   n_addr32 = ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE));
02435   n_port = ntohs(get_uint16(cell->payload+RELAY_HEADER_SIZE+4));
02436   onionskin = (char*) cell->payload+RELAY_HEADER_SIZE+4+2;
02437   id_digest = (char*) cell->payload+RELAY_HEADER_SIZE+4+2+
02438     ONIONSKIN_CHALLENGE_LEN;
02439   tor_addr_from_ipv4h(&n_addr, n_addr32);
02440 
02441   if (!n_port || !n_addr32) {
02442     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
02443            "Client asked me to extend to zero destination port or addr.");
02444     return -1;
02445   }
02446 
02447   /* Check if they asked us for 0000..0000. We support using
02448    * an empty fingerprint for the first hop (e.g. for a bridge relay),
02449    * but we don't want to let people send us extend cells for empty
02450    * fingerprints -- a) because it opens the user up to a mitm attack,
02451    * and b) because it lets an attacker force the relay to hold open a
02452    * new TLS connection for each extend request. */
02453   if (tor_digest_is_zero(id_digest)) {
02454     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
02455            "Client asked me to extend without specifying an id_digest.");
02456     return -1;
02457   }
02458 
02459   /* Next, check if we're being asked to connect to the hop that the
02460    * extend cell came from. There isn't any reason for that, and it can
02461    * assist circular-path attacks. */
02462   if (tor_memeq(id_digest, TO_OR_CIRCUIT(circ)->p_conn->identity_digest,
02463               DIGEST_LEN)) {
02464     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
02465            "Client asked me to extend back to the previous hop.");
02466     return -1;
02467   }
02468 
02469   n_conn = connection_or_get_for_extend(id_digest,
02470                                         &n_addr,
02471                                         &msg,
02472                                         &should_launch);
02473 
02474   if (!n_conn) {
02475     log_debug(LD_CIRC|LD_OR,"Next router (%s:%d): %s",
02476               fmt_addr(&n_addr), (int)n_port, msg?msg:"????");
02477 
02478     circ->n_hop = extend_info_alloc(NULL /*nickname*/,
02479                                     id_digest,
02480                                     NULL /*onion_key*/,
02481                                     &n_addr, n_port);
02482 
02483     circ->n_conn_onionskin = tor_malloc(ONIONSKIN_CHALLENGE_LEN);
02484     memcpy(circ->n_conn_onionskin, onionskin, ONIONSKIN_CHALLENGE_LEN);
02485     circuit_set_state(circ, CIRCUIT_STATE_OR_WAIT);
02486 
02487     if (should_launch) {
02488       /* we should try to open a connection */
02489       n_conn = connection_or_connect(&n_addr, n_port, id_digest);
02490       if (!n_conn) {
02491         log_info(LD_CIRC,"Launching n_conn failed. Closing circuit.");
02492         circuit_mark_for_close(circ, END_CIRC_REASON_CONNECTFAILED);
02493         return 0;
02494       }
02495       log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
02496     }
02497     /* return success. The onion/circuit/etc will be taken care of
02498      * automatically (may already have been) whenever n_conn reaches
02499      * OR_CONN_STATE_OPEN.
02500      */
02501     return 0;
02502   }
02503 
02504   tor_assert(!circ->n_hop); /* Connection is already established. */
02505   circ->n_conn = n_conn;
02506   log_debug(LD_CIRC,"n_conn is %s:%u",
02507             n_conn->_base.address,n_conn->_base.port);
02508 
02509   if (circuit_deliver_create_cell(circ, CELL_CREATE, onionskin) < 0)
02510     return -1;
02511   return 0;
02512 }
02513 
02524 int
02525 circuit_init_cpath_crypto(crypt_path_t *cpath, const char *key_data,
02526                           int reverse)
02527 {
02528   crypto_digest_t *tmp_digest;
02529   crypto_cipher_t *tmp_crypto;
02530 
02531   tor_assert(cpath);
02532   tor_assert(key_data);
02533   tor_assert(!(cpath->f_crypto || cpath->b_crypto ||
02534              cpath->f_digest || cpath->b_digest));
02535 
02536   cpath->f_digest = crypto_digest_new();
02537   crypto_digest_add_bytes(cpath->f_digest, key_data, DIGEST_LEN);
02538   cpath->b_digest = crypto_digest_new();
02539   crypto_digest_add_bytes(cpath->b_digest, key_data+DIGEST_LEN, DIGEST_LEN);
02540 
02541   if (!(cpath->f_crypto =
02542         crypto_cipher_new(key_data+(2*DIGEST_LEN)))) {
02543     log_warn(LD_BUG,"Forward cipher initialization failed.");
02544     return -1;
02545   }
02546   if (!(cpath->b_crypto =
02547         crypto_cipher_new(key_data+(2*DIGEST_LEN)+CIPHER_KEY_LEN))) {
02548     log_warn(LD_BUG,"Backward cipher initialization failed.");
02549     return -1;
02550   }
02551 
02552   if (reverse) {
02553     tmp_digest = cpath->f_digest;
02554     cpath->f_digest = cpath->b_digest;
02555     cpath->b_digest = tmp_digest;
02556     tmp_crypto = cpath->f_crypto;
02557     cpath->f_crypto = cpath->b_crypto;
02558     cpath->b_crypto = tmp_crypto;
02559   }
02560 
02561   return 0;
02562 }
02563 
02566 static int
02567 pathbias_get_min_circs(const or_options_t *options)
02568 {
02569 #define DFLT_PATH_BIAS_MIN_CIRC 20
02570   if (options->PathBiasCircThreshold >= 5)
02571     return options->PathBiasCircThreshold;
02572   else
02573     return networkstatus_get_param(NULL, "pb_mincircs",
02574                                    DFLT_PATH_BIAS_MIN_CIRC,
02575                                    5, INT32_MAX);
02576 }
02577 
02578 static double
02579 pathbias_get_notice_rate(const or_options_t *options)
02580 {
02581 #define DFLT_PATH_BIAS_NOTICE_PCT 40
02582   if (options->PathBiasNoticeRate >= 0.0)
02583     return options->PathBiasNoticeRate;
02584   else
02585     return networkstatus_get_param(NULL, "pb_noticepct",
02586                                    DFLT_PATH_BIAS_NOTICE_PCT, 0, 100)/100.0;
02587 }
02588 
02589 static double
02590 pathbias_get_disable_rate(const or_options_t *options)
02591 {
02592 // XXX: This needs tuning based on use + experimentation before we set it
02593 #define DFLT_PATH_BIAS_DISABLE_PCT 0
02594   if (options->PathBiasDisableRate >= 0.0)
02595     return options->PathBiasDisableRate;
02596   else
02597     return networkstatus_get_param(NULL, "pb_disablepct",
02598                                    DFLT_PATH_BIAS_DISABLE_PCT, 0, 100)/100.0;
02599 }
02600 
02601 static int
02602 pathbias_get_scale_threshold(const or_options_t *options)
02603 {
02604 #define DFLT_PATH_BIAS_SCALE_THRESHOLD 200
02605   if (options->PathBiasScaleThreshold >= 2)
02606     return options->PathBiasScaleThreshold;
02607   else
02608     return networkstatus_get_param(NULL, "pb_scalecircs",
02609                                    DFLT_PATH_BIAS_SCALE_THRESHOLD, 10,
02610                                    INT32_MAX);
02611 }
02612 
02613 static int
02614 pathbias_get_scale_factor(const or_options_t *options)
02615 {
02616 #define DFLT_PATH_BIAS_SCALE_FACTOR 4
02617   if (options->PathBiasScaleFactor >= 1)
02618     return options->PathBiasScaleFactor;
02619   else
02620     return networkstatus_get_param(NULL, "pb_scalefactor",
02621                                 DFLT_PATH_BIAS_SCALE_THRESHOLD, 1, INT32_MAX);
02622 }
02623 
02628 static int
02629 entry_guard_inc_first_hop_count(entry_guard_t *guard)
02630 {
02631   const or_options_t *options = get_options();
02632 
02633   entry_guards_changed();
02634 
02635   if (guard->first_hops > (unsigned)pathbias_get_min_circs(options)) {
02636     /* Note: We rely on the < comparison here to allow us to set a 0
02637      * rate and disable the feature entirely. If refactoring, don't
02638      * change to <= */
02639     if (guard->circuit_successes/((double)guard->first_hops)
02640         < pathbias_get_disable_rate(options)) {
02641 
02642       log_warn(LD_PROTOCOL,
02643                "Extremely low circuit success rate %u/%u for guard %s=%s. "
02644                "This might indicate an attack, or a bug.",
02645                guard->circuit_successes, guard->first_hops, guard->nickname,
02646                hex_str(guard->identity, DIGEST_LEN));
02647 
02648       guard->path_bias_disabled = 1;
02649       guard->bad_since = approx_time();
02650       return -1;
02651     } else if (guard->circuit_successes/((double)guard->first_hops)
02652                < pathbias_get_notice_rate(options)
02653                && !guard->path_bias_notice) {
02654       guard->path_bias_notice = 1;
02655       log_notice(LD_PROTOCOL,
02656                  "Low circuit success rate %u/%u for guard %s=%s.",
02657                  guard->circuit_successes, guard->first_hops, guard->nickname,
02658                  hex_str(guard->identity, DIGEST_LEN));
02659     }
02660   }
02661 
02662   /* If we get a ton of circuits, just scale everything down */
02663   if (guard->first_hops > (unsigned)pathbias_get_scale_threshold(options)) {
02664     const int scale_factor = pathbias_get_scale_factor(options);
02665     guard->first_hops /= scale_factor;
02666     guard->circuit_successes /= scale_factor;
02667   }
02668   guard->first_hops++;
02669   log_info(LD_PROTOCOL, "Got success count %u/%u for guard %s",
02670            guard->circuit_successes, guard->first_hops, guard->nickname);
02671   return 0;
02672 }
02673 
02684 int
02685 circuit_finish_handshake(origin_circuit_t *circ, uint8_t reply_type,
02686                          const uint8_t *reply)
02687 {
02688   char keys[CPATH_KEY_MATERIAL_LEN];
02689   crypt_path_t *hop;
02690 
02691   if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS) {
02692     hop = circ->cpath;
02693     /* Don't count cannibalized or onehop circs for path bias */
02694     if (!circ->has_opened && !circ->build_state->onehop_tunnel) {
02695       entry_guard_t *guard;
02696 
02697       guard = entry_guard_get_by_id_digest(
02698               circ->_base.n_conn->identity_digest);
02699       if (guard) {
02700         if (entry_guard_inc_first_hop_count(guard) < 0) {
02701           /* Bogus guard; we already warned. */
02702           return -END_CIRC_REASON_TORPROTOCOL;
02703         }
02704       }
02705     }
02706   } else {
02707     hop = onion_next_hop_in_cpath(circ->cpath);
02708     if (!hop) { /* got an extended when we're all done? */
02709       log_warn(LD_PROTOCOL,"got extended when circ already built? Closing.");
02710       return - END_CIRC_REASON_TORPROTOCOL;
02711     }
02712   }
02713   tor_assert(hop->state == CPATH_STATE_AWAITING_KEYS);
02714 
02715   if (reply_type == CELL_CREATED && hop->dh_handshake_state) {
02716     if (onion_skin_client_handshake(hop->dh_handshake_state, (char*)reply,keys,
02717                                     DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) {
02718       log_warn(LD_CIRC,"onion_skin_client_handshake failed.");
02719       return -END_CIRC_REASON_TORPROTOCOL;
02720     }
02721     /* Remember hash of g^xy */
02722     memcpy(hop->handshake_digest, reply+DH_KEY_LEN, DIGEST_LEN);
02723   } else if (reply_type == CELL_CREATED_FAST && !hop->dh_handshake_state) {
02724     if (fast_client_handshake(hop->fast_handshake_state, reply,
02725                               (uint8_t*)keys,
02726                               DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) {
02727       log_warn(LD_CIRC,"fast_client_handshake failed.");
02728       return -END_CIRC_REASON_TORPROTOCOL;
02729     }
02730     memcpy(hop->handshake_digest, reply+DIGEST_LEN, DIGEST_LEN);
02731   } else {
02732     log_warn(LD_PROTOCOL,"CREATED cell type did not match CREATE cell type.");
02733     return -END_CIRC_REASON_TORPROTOCOL;
02734   }
02735 
02736   crypto_dh_free(hop->dh_handshake_state); /* don't need it anymore */
02737   hop->dh_handshake_state = NULL;
02738 
02739   memset(hop->fast_handshake_state, 0, sizeof(hop->fast_handshake_state));
02740 
02741   if (circuit_init_cpath_crypto(hop, keys, 0)<0) {
02742     return -END_CIRC_REASON_TORPROTOCOL;
02743   }
02744 
02745   hop->state = CPATH_STATE_OPEN;
02746   log_info(LD_CIRC,"Finished building %scircuit hop:",
02747            (reply_type == CELL_CREATED_FAST) ? "fast " : "");
02748   circuit_log_path(LOG_INFO,LD_CIRC,circ);
02749   control_event_circuit_status(circ, CIRC_EVENT_EXTENDED, 0);
02750 
02751   return 0;
02752 }
02753 
02760 int
02761 circuit_truncated(origin_circuit_t *circ, crypt_path_t *layer)
02762 {
02763 //  crypt_path_t *victim;
02764 //  connection_t *stream;
02765 
02766   tor_assert(circ);
02767   tor_assert(layer);
02768 
02769   /* XXX Since we don't ask for truncates currently, getting a truncated
02770    *     means that a connection broke or an extend failed. For now,
02771    *     just give up.
02772    */
02773   circuit_mark_for_close(TO_CIRCUIT(circ),
02774           END_CIRC_REASON_FLAG_REMOTE|END_CIRC_REASON_OR_CONN_CLOSED);
02775   return 0;
02776 
02777 #if 0
02778   while (layer->next != circ->cpath) {
02779     /* we need to clear out layer->next */
02780     victim = layer->next;
02781     log_debug(LD_CIRC, "Killing a layer of the cpath.");
02782 
02783     for (stream = circ->p_streams; stream; stream=stream->next_stream) {
02784       if (stream->cpath_layer == victim) {
02785         log_info(LD_APP, "Marking stream %d for close because of truncate.",
02786                  stream->stream_id);
02787         /* no need to send 'end' relay cells,
02788          * because the other side's already dead
02789          */
02790         connection_mark_unattached_ap(stream, END_STREAM_REASON_DESTROY);
02791       }
02792     }
02793 
02794     layer->next = victim->next;
02795     circuit_free_cpath_node(victim);
02796   }
02797 
02798   log_info(LD_CIRC, "finished");
02799   return 0;
02800 #endif
02801 }
02802 
02806 int
02807 onionskin_answer(or_circuit_t *circ, uint8_t cell_type, const char *payload,
02808                  const char *keys)
02809 {
02810   cell_t cell;
02811   crypt_path_t *tmp_cpath;
02812 
02813   tmp_cpath = tor_malloc_zero(sizeof(crypt_path_t));
02814   tmp_cpath->magic = CRYPT_PATH_MAGIC;
02815 
02816   memset(&cell, 0, sizeof(cell_t));
02817   cell.command = cell_type;
02818   cell.circ_id = circ->p_circ_id;
02819 
02820   circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
02821 
02822   memcpy(cell.payload, payload,
02823          cell_type == CELL_CREATED ? ONIONSKIN_REPLY_LEN : DIGEST_LEN*2);
02824 
02825   log_debug(LD_CIRC,"init digest forward 0x%.8x, backward 0x%.8x.",
02826             (unsigned int)get_uint32(keys),
02827             (unsigned int)get_uint32(keys+20));
02828   if (circuit_init_cpath_crypto(tmp_cpath, keys, 0)<0) {
02829     log_warn(LD_BUG,"Circuit initialization failed");
02830     tor_free(tmp_cpath);
02831     return -1;
02832   }
02833   circ->n_digest = tmp_cpath->f_digest;
02834   circ->n_crypto = tmp_cpath->f_crypto;
02835   circ->p_digest = tmp_cpath->b_digest;
02836   circ->p_crypto = tmp_cpath->b_crypto;
02837   tmp_cpath->magic = 0;
02838   tor_free(tmp_cpath);
02839 
02840   if (cell_type == CELL_CREATED)
02841     memcpy(circ->handshake_digest, cell.payload+DH_KEY_LEN, DIGEST_LEN);
02842   else
02843     memcpy(circ->handshake_digest, cell.payload+DIGEST_LEN, DIGEST_LEN);
02844 
02845   circ->is_first_hop = (cell_type == CELL_CREATED_FAST);
02846 
02847   append_cell_to_circuit_queue(TO_CIRCUIT(circ),
02848                                circ->p_conn, &cell, CELL_DIRECTION_IN, 0);
02849   log_debug(LD_CIRC,"Finished sending '%s' cell.",
02850             circ->is_first_hop ? "created_fast" : "created");
02851 
02852   if (!is_local_addr(&circ->p_conn->_base.addr) &&
02853       !connection_or_nonopen_was_started_here(circ->p_conn)) {
02854     /* record that we could process create cells from a non-local conn
02855      * that we didn't initiate; presumably this means that create cells
02856      * can reach us too. */
02857     router_orport_found_reachable();
02858   }
02859 
02860   return 0;
02861 }
02862 
02869 static int
02870 new_route_len(uint8_t purpose, extend_info_t *exit,
02871               smartlist_t *nodes)
02872 {
02873   int num_acceptable_routers;
02874   int routelen;
02875 
02876   tor_assert(nodes);
02877 
02878   routelen = DEFAULT_ROUTE_LEN;
02879   if (exit &&
02880       purpose != CIRCUIT_PURPOSE_TESTING &&
02881       purpose != CIRCUIT_PURPOSE_S_ESTABLISH_INTRO)
02882     routelen++;
02883 
02884   num_acceptable_routers = count_acceptable_nodes(nodes);
02885 
02886   log_debug(LD_CIRC,"Chosen route length %d (%d/%d routers suitable).",
02887             routelen, num_acceptable_routers, smartlist_len(nodes));
02888 
02889   if (num_acceptable_routers < 2) {
02890     log_info(LD_CIRC,
02891              "Not enough acceptable routers (%d). Discarding this circuit.",
02892              num_acceptable_routers);
02893     return -1;
02894   }
02895 
02896   if (num_acceptable_routers < routelen) {
02897     log_info(LD_CIRC,"Not enough routers: cutting routelen from %d to %d.",
02898              routelen, num_acceptable_routers);
02899     routelen = num_acceptable_routers;
02900   }
02901 
02902   return routelen;
02903 }
02904 
02907 static smartlist_t *
02908 circuit_get_unhandled_ports(time_t now)
02909 {
02910   smartlist_t *dest = rep_hist_get_predicted_ports(now);
02911   circuit_remove_handled_ports(dest);
02912   return dest;
02913 }
02914 
02921 int
02922 circuit_all_predicted_ports_handled(time_t now, int *need_uptime,
02923                                     int *need_capacity)
02924 {
02925   int i, enough;
02926   uint16_t *port;
02927   smartlist_t *sl = circuit_get_unhandled_ports(now);
02928   smartlist_t *LongLivedServices = get_options()->LongLivedPorts;
02929   tor_assert(need_uptime);
02930   tor_assert(need_capacity);
02931   // Always predict need_capacity
02932   *need_capacity = 1;
02933   enough = (smartlist_len(sl) == 0);
02934   for (i = 0; i < smartlist_len(sl); ++i) {
02935     port = smartlist_get(sl, i);
02936     if (smartlist_string_num_isin(LongLivedServices, *port))
02937       *need_uptime = 1;
02938     tor_free(port);
02939   }
02940   smartlist_free(sl);
02941   return enough;
02942 }
02943 
02947 static int
02948 node_handles_some_port(const node_t *node, smartlist_t *needed_ports)
02949 { /* XXXX MOVE */
02950   int i;
02951   uint16_t port;
02952 
02953   for (i = 0; i < smartlist_len(needed_ports); ++i) {
02954     addr_policy_result_t r;
02955     /* alignment issues aren't a worry for this dereference, since
02956        needed_ports is explicitly a smartlist of uint16_t's */
02957     port = *(uint16_t *)smartlist_get(needed_ports, i);
02958     tor_assert(port);
02959     if (node)
02960       r = compare_tor_addr_to_node_policy(NULL, port, node);
02961     else
02962       continue;
02963     if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED)
02964       return 1;
02965   }
02966   return 0;
02967 }
02968 
02971 static int
02972 ap_stream_wants_exit_attention(connection_t *conn)
02973 {
02974   entry_connection_t *entry;
02975   if (conn->type != CONN_TYPE_AP)
02976     return 0;
02977   entry = TO_ENTRY_CONN(conn);
02978 
02979   if (conn->state == AP_CONN_STATE_CIRCUIT_WAIT &&
02980       !conn->marked_for_close &&
02981       !(entry->want_onehop) && /* ignore one-hop streams */
02982       !(entry->use_begindir) && /* ignore targeted dir fetches */
02983       !(entry->chosen_exit_name) && /* ignore defined streams */
02984       !connection_edge_is_rendezvous_stream(TO_EDGE_CONN(conn)) &&
02985       !circuit_stream_is_being_handled(TO_ENTRY_CONN(conn), 0,
02986                                        MIN_CIRCUITS_HANDLING_STREAM))
02987     return 1;
02988   return 0;
02989 }
02990 
02999 static const node_t *
03000 choose_good_exit_server_general(int need_uptime, int need_capacity)
03001 {
03002   int *n_supported;
03003   int n_pending_connections = 0;
03004   smartlist_t *connections;
03005   int best_support = -1;
03006   int n_best_support=0;
03007   const or_options_t *options = get_options();
03008   const smartlist_t *the_nodes;
03009   const node_t *node=NULL;
03010 
03011   connections = get_connection_array();
03012 
03013   /* Count how many connections are waiting for a circuit to be built.
03014    * We use this for log messages now, but in the future we may depend on it.
03015    */
03016   SMARTLIST_FOREACH(connections, connection_t *, conn,
03017   {
03018     if (ap_stream_wants_exit_attention(conn))
03019       ++n_pending_connections;
03020   });
03021 //  log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
03022 //         n_pending_connections);
03023   /* Now we count, for each of the routers in the directory, how many
03024    * of the pending connections could possibly exit from that
03025    * router (n_supported[i]). (We can't be sure about cases where we
03026    * don't know the IP address of the pending connection.)
03027    *
03028    * -1 means "Don't use this router at all."
03029    */
03030   the_nodes = nodelist_get_list();
03031   n_supported = tor_malloc(sizeof(int)*smartlist_len(the_nodes));
03032   SMARTLIST_FOREACH_BEGIN(the_nodes, const node_t *, node) {
03033     const int i = node_sl_idx;
03034     if (router_digest_is_me(node->identity)) {
03035       n_supported[i] = -1;
03036 //      log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
03037       /* XXX there's probably a reverse predecessor attack here, but
03038        * it's slow. should we take this out? -RD
03039        */
03040       continue;
03041     }
03042     if (!node_has_descriptor(node)) {
03043       n_supported[i] = -1;
03044       continue;
03045     }
03046     if (!node->is_running || node->is_bad_exit) {
03047       n_supported[i] = -1;
03048       continue; /* skip routers that are known to be down or bad exits */
03049     }
03050     if (node_get_purpose(node) != ROUTER_PURPOSE_GENERAL) {
03051       /* never pick a non-general node as a random exit. */
03052       n_supported[i] = -1;
03053       continue;
03054     }
03055     if (routerset_contains_node(options->_ExcludeExitNodesUnion, node)) {
03056       n_supported[i] = -1;
03057       continue; /* user asked us not to use it, no matter what */
03058     }
03059     if (options->ExitNodes &&
03060         !routerset_contains_node(options->ExitNodes, node)) {
03061       n_supported[i] = -1;
03062       continue; /* not one of our chosen exit nodes */
03063     }
03064 
03065     if (node_is_unreliable(node, need_uptime, need_capacity, 0)) {
03066       n_supported[i] = -1;
03067       continue; /* skip routers that are not suitable.  Don't worry if
03068                  * this makes us reject all the possible routers: if so,
03069                  * we'll retry later in this function with need_update and
03070                  * need_capacity set to 0. */
03071     }
03072     if (!(node->is_valid || options->_AllowInvalid & ALLOW_INVALID_EXIT)) {
03073       /* if it's invalid and we don't want it */
03074       n_supported[i] = -1;
03075 //      log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.",
03076 //             router->nickname, i);
03077       continue; /* skip invalid routers */
03078     }
03079     if (options->ExcludeSingleHopRelays &&
03080         node_allows_single_hop_exits(node)) {
03081       n_supported[i] = -1;
03082       continue;
03083     }
03084     if (node_exit_policy_rejects_all(node)) {
03085       n_supported[i] = -1;
03086 //      log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
03087 //             router->nickname, i);
03088       continue; /* skip routers that reject all */
03089     }
03090     n_supported[i] = 0;
03091     /* iterate over connections */
03092     SMARTLIST_FOREACH_BEGIN(connections, connection_t *, conn) {
03093       if (!ap_stream_wants_exit_attention(conn))
03094         continue; /* Skip everything but APs in CIRCUIT_WAIT */
03095       if (connection_ap_can_use_exit(TO_ENTRY_CONN(conn), node)) {
03096         ++n_supported[i];
03097 //        log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
03098 //               router->nickname, i, n_supported[i]);
03099       } else {
03100 //        log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
03101 //               router->nickname, i);
03102       }
03103     } SMARTLIST_FOREACH_END(conn);
03104     if (n_pending_connections > 0 && n_supported[i] == 0) {
03105       /* Leave best_support at -1 if that's where it is, so we can
03106        * distinguish it later. */
03107       continue;
03108     }
03109     if (n_supported[i] > best_support) {
03110       /* If this router is better than previous ones, remember its index
03111        * and goodness, and start counting how many routers are this good. */
03112       best_support = n_supported[i]; n_best_support=1;
03113 //      log_fn(LOG_DEBUG,"%s is new best supported option so far.",
03114 //             router->nickname);
03115     } else if (n_supported[i] == best_support) {
03116       /* If this router is _as good_ as the best one, just increment the
03117        * count of equally good routers.*/
03118       ++n_best_support;
03119     }
03120   } SMARTLIST_FOREACH_END(node);
03121   log_info(LD_CIRC,
03122            "Found %d servers that might support %d/%d pending connections.",
03123            n_best_support, best_support >= 0 ? best_support : 0,
03124            n_pending_connections);
03125 
03126   /* If any routers definitely support any pending connections, choose one
03127    * at random. */
03128   if (best_support > 0) {
03129     smartlist_t *supporting = smartlist_new();
03130 
03131     SMARTLIST_FOREACH(the_nodes, const node_t *, node, {
03132       if (n_supported[node_sl_idx] == best_support)
03133         smartlist_add(supporting, (void*)node);
03134     });
03135 
03136     node = node_sl_choose_by_bandwidth(supporting, WEIGHT_FOR_EXIT);
03137     smartlist_free(supporting);
03138   } else {
03139     /* Either there are no pending connections, or no routers even seem to
03140      * possibly support any of them.  Choose a router at random that satisfies
03141      * at least one predicted exit port. */
03142 
03143     int attempt;
03144     smartlist_t *needed_ports, *supporting;
03145 
03146     if (best_support == -1) {
03147       if (need_uptime || need_capacity) {
03148         log_info(LD_CIRC,
03149                  "We couldn't find any live%s%s routers; falling back "
03150                  "to list of all routers.",
03151                  need_capacity?", fast":"",
03152                  need_uptime?", stable":"");
03153         tor_free(n_supported);
03154         return choose_good_exit_server_general(0, 0);
03155       }
03156       log_notice(LD_CIRC, "All routers are down or won't exit%s -- "
03157                  "choosing a doomed exit at random.",
03158                  options->_ExcludeExitNodesUnion ? " or are Excluded" : "");
03159     }
03160     supporting = smartlist_new();
03161     needed_ports = circuit_get_unhandled_ports(time(NULL));
03162     for (attempt = 0; attempt < 2; attempt++) {
03163       /* try once to pick only from routers that satisfy a needed port,
03164        * then if there are none, pick from any that support exiting. */
03165       SMARTLIST_FOREACH_BEGIN(the_nodes, const node_t *, node) {
03166         if (n_supported[node_sl_idx] != -1 &&
03167             (attempt || node_handles_some_port(node, needed_ports))) {
03168 //          log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
03169 //                 try, router->nickname);
03170           smartlist_add(supporting, (void*)node);
03171         }
03172       } SMARTLIST_FOREACH_END(node);
03173 
03174       node = node_sl_choose_by_bandwidth(supporting, WEIGHT_FOR_EXIT);
03175       if (node)
03176         break;
03177       smartlist_clear(supporting);
03178       /* If we reach this point, we can't actually support any unhandled
03179        * predicted ports, so clear all the remaining ones. */
03180       if (smartlist_len(needed_ports))
03181         rep_hist_remove_predicted_ports(needed_ports);
03182     }
03183     SMARTLIST_FOREACH(needed_ports, uint16_t *, cp, tor_free(cp));
03184     smartlist_free(needed_ports);
03185     smartlist_free(supporting);
03186   }
03187 
03188   tor_free(n_supported);
03189   if (node) {
03190     log_info(LD_CIRC, "Chose exit server '%s'", node_describe(node));
03191     return node;
03192   }
03193   if (options->ExitNodes) {
03194     log_warn(LD_CIRC,
03195              "No specified %sexit routers seem to be running: "
03196              "can't choose an exit.",
03197              options->_ExcludeExitNodesUnion ? "non-excluded " : "");
03198   }
03199   return NULL;
03200 }
03201 
03212 static const node_t *
03213 choose_good_exit_server(uint8_t purpose,
03214                         int need_uptime, int need_capacity, int is_internal)
03215 {
03216   const or_options_t *options = get_options();
03217   router_crn_flags_t flags = CRN_NEED_DESC;
03218   if (need_uptime)
03219     flags |= CRN_NEED_UPTIME;
03220   if (need_capacity)
03221     flags |= CRN_NEED_CAPACITY;
03222 
03223   switch (purpose) {
03224     case CIRCUIT_PURPOSE_C_GENERAL:
03225       if (options->_AllowInvalid & ALLOW_INVALID_MIDDLE)
03226         flags |= CRN_ALLOW_INVALID;
03227       if (is_internal) /* pick it like a middle hop */
03228         return router_choose_random_node(NULL, options->ExcludeNodes, flags);
03229       else
03230         return choose_good_exit_server_general(need_uptime,need_capacity);
03231     case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
03232       if (options->_AllowInvalid & ALLOW_INVALID_RENDEZVOUS)
03233         flags |= CRN_ALLOW_INVALID;
03234       return router_choose_random_node(NULL, options->ExcludeNodes, flags);
03235   }
03236   log_warn(LD_BUG,"Unhandled purpose %d", purpose);
03237   tor_fragile_assert();
03238   return NULL;
03239 }
03240 
03243 static void
03244 warn_if_last_router_excluded(origin_circuit_t *circ, const extend_info_t *exit)
03245 {
03246   const or_options_t *options = get_options();
03247   routerset_t *rs = options->ExcludeNodes;
03248   const char *description;
03249   uint8_t purpose = circ->_base.purpose;
03250 
03251   if (circ->build_state->onehop_tunnel)
03252     return;
03253 
03254   switch (purpose)
03255     {
03256     default:
03257     case CIRCUIT_PURPOSE_OR:
03258     case CIRCUIT_PURPOSE_INTRO_POINT:
03259     case CIRCUIT_PURPOSE_REND_POINT_WAITING:
03260     case CIRCUIT_PURPOSE_REND_ESTABLISHED:
03261       log_warn(LD_BUG, "Called on non-origin circuit (purpose %d, %s)",
03262                (int)purpose,
03263                circuit_purpose_to_string(purpose));
03264       return;
03265     case CIRCUIT_PURPOSE_C_GENERAL:
03266       if (circ->build_state->is_internal)
03267         return;
03268       description = "requested exit node";
03269       rs = options->_ExcludeExitNodesUnion;
03270       break;
03271     case CIRCUIT_PURPOSE_C_INTRODUCING:
03272     case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
03273     case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
03274     case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
03275     case CIRCUIT_PURPOSE_S_CONNECT_REND:
03276     case CIRCUIT_PURPOSE_S_REND_JOINED:
03277     case CIRCUIT_PURPOSE_TESTING:
03278       return;
03279     case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
03280     case CIRCUIT_PURPOSE_C_REND_READY:
03281     case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
03282     case CIRCUIT_PURPOSE_C_REND_JOINED:
03283       description = "chosen rendezvous point";
03284       break;
03285     case CIRCUIT_PURPOSE_CONTROLLER:
03286       rs = options->_ExcludeExitNodesUnion;
03287       description = "controller-selected circuit target";
03288       break;
03289     }
03290 
03291   if (routerset_contains_extendinfo(rs, exit)) {
03292     /* We should never get here if StrictNodes is set to 1. */
03293     if (options->StrictNodes) {
03294       log_warn(LD_BUG, "Using %s '%s' which is listed in ExcludeNodes%s, "
03295                "even though StrictNodes is set. Please report. "
03296                "(Circuit purpose: %s)",
03297                description, extend_info_describe(exit),
03298                rs==options->ExcludeNodes?"":" or ExcludeExitNodes",
03299                circuit_purpose_to_string(purpose));
03300     } else {
03301       log_warn(LD_CIRC, "Using %s '%s' which is listed in "
03302                "ExcludeNodes%s, because no better options were available. To "
03303                "prevent this (and possibly break your Tor functionality), "
03304                "set the StrictNodes configuration option. "
03305                "(Circuit purpose: %s)",
03306                description, extend_info_describe(exit),
03307                rs==options->ExcludeNodes?"":" or ExcludeExitNodes",
03308                circuit_purpose_to_string(purpose));
03309     }
03310     circuit_log_path(LOG_WARN, LD_CIRC, circ);
03311   }
03312 
03313   return;
03314 }
03315 
03319 static int
03320 onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit)
03321 {
03322   cpath_build_state_t *state = circ->build_state;
03323 
03324   if (state->onehop_tunnel) {
03325     log_debug(LD_CIRC, "Launching a one-hop circuit for dir tunnel.");
03326     state->desired_path_len = 1;
03327   } else {
03328     int r = new_route_len(circ->_base.purpose, exit, nodelist_get_list());
03329     if (r < 1) /* must be at least 1 */
03330       return -1;
03331     state->desired_path_len = r;
03332   }
03333 
03334   if (exit) { /* the circuit-builder pre-requested one */
03335     warn_if_last_router_excluded(circ, exit);
03336     log_info(LD_CIRC,"Using requested exit node '%s'",
03337              extend_info_describe(exit));
03338     exit = extend_info_dup(exit);
03339   } else { /* we have to decide one */
03340     const node_t *node =
03341       choose_good_exit_server(circ->_base.purpose, state->need_uptime,
03342                               state->need_capacity, state->is_internal);
03343     if (!node) {
03344       log_warn(LD_CIRC,"failed to choose an exit server");
03345       return -1;
03346     }
03347     exit = extend_info_from_node(node, 0);
03348     tor_assert(exit);
03349   }
03350   state->chosen_exit = exit;
03351   return 0;
03352 }
03353 
03358 int
03359 circuit_append_new_exit(origin_circuit_t *circ, extend_info_t *exit)
03360 {
03361   cpath_build_state_t *state;
03362   tor_assert(exit);
03363   tor_assert(circ);
03364 
03365   state = circ->build_state;
03366   tor_assert(state);
03367   extend_info_free(state->chosen_exit);
03368   state->chosen_exit = extend_info_dup(exit);
03369 
03370   ++circ->build_state->desired_path_len;
03371   onion_append_hop(&circ->cpath, exit);
03372   return 0;
03373 }
03374 
03379 int
03380 circuit_extend_to_new_exit(origin_circuit_t *circ, extend_info_t *exit)
03381 {
03382   int err_reason = 0;
03383   warn_if_last_router_excluded(circ, exit);
03384   circuit_append_new_exit(circ, exit);
03385   circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
03386   if ((err_reason = circuit_send_next_onion_skin(circ))<0) {
03387     log_warn(LD_CIRC, "Couldn't extend circuit to new point %s.",
03388              extend_info_describe(exit));
03389     circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
03390     return -1;
03391   }
03392   return 0;
03393 }
03394 
03398 static int
03399 count_acceptable_nodes(smartlist_t *nodes)
03400 {
03401   int num=0;
03402 
03403   SMARTLIST_FOREACH_BEGIN(nodes, const node_t *, node) {
03404     //    log_debug(LD_CIRC,
03405 //              "Contemplating whether router %d (%s) is a new option.",
03406 //              i, r->nickname);
03407     if (! node->is_running)
03408 //      log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
03409       continue;
03410     if (! node->is_valid)
03411 //      log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
03412       continue;
03413     if (! node_has_descriptor(node))
03414       continue;
03415       /* XXX This clause makes us count incorrectly: if AllowInvalidRouters
03416        * allows this node in some places, then we're getting an inaccurate
03417        * count. For now, be conservative and don't count it. But later we
03418        * should try to be smarter. */
03419     ++num;
03420   } SMARTLIST_FOREACH_END(node);
03421 
03422 //    log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
03423 
03424   return num;
03425 }
03426 
03430 void
03431 onion_append_to_cpath(crypt_path_t **head_ptr, crypt_path_t *new_hop)
03432 {
03433   if (*head_ptr) {
03434     new_hop->next = (*head_ptr);
03435     new_hop->prev = (*head_ptr)->prev;
03436     (*head_ptr)->prev->next = new_hop;
03437     (*head_ptr)->prev = new_hop;
03438   } else {
03439     *head_ptr = new_hop;
03440     new_hop->prev = new_hop->next = new_hop;
03441   }
03442 }
03443 
03450 static const node_t *
03451 choose_good_middle_server(uint8_t purpose,
03452                           cpath_build_state_t *state,
03453                           crypt_path_t *head,
03454                           int cur_len)
03455 {
03456   int i;
03457   const node_t *r, *choice;
03458   crypt_path_t *cpath;
03459   smartlist_t *excluded;
03460   const or_options_t *options = get_options();
03461   router_crn_flags_t flags = CRN_NEED_DESC;
03462   tor_assert(_CIRCUIT_PURPOSE_MIN <= purpose &&
03463              purpose <= _CIRCUIT_PURPOSE_MAX);
03464 
03465   log_debug(LD_CIRC, "Contemplating intermediate hop: random choice.");
03466   excluded = smartlist_new();
03467   if ((r = build_state_get_exit_node(state))) {
03468     nodelist_add_node_and_family(excluded, r);
03469   }
03470   for (i = 0, cpath = head; i < cur_len; ++i, cpath=cpath->next) {
03471     if ((r = node_get_by_id(cpath->extend_info->identity_digest))) {
03472       nodelist_add_node_and_family(excluded, r);
03473     }
03474   }
03475 
03476   if (state->need_uptime)
03477     flags |= CRN_NEED_UPTIME;
03478   if (state->need_capacity)
03479     flags |= CRN_NEED_CAPACITY;
03480   if (options->_AllowInvalid & ALLOW_INVALID_MIDDLE)
03481     flags |= CRN_ALLOW_INVALID;
03482   choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
03483   smartlist_free(excluded);
03484   return choice;
03485 }
03486 
03495 static const node_t *
03496 choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state)
03497 {
03498   const node_t *choice;
03499   smartlist_t *excluded;
03500   const or_options_t *options = get_options();
03501   router_crn_flags_t flags = CRN_NEED_GUARD|CRN_NEED_DESC;
03502   const node_t *node;
03503 
03504   if (state && options->UseEntryGuards &&
03505       (purpose != CIRCUIT_PURPOSE_TESTING || options->BridgeRelay)) {
03506     /* This request is for an entry server to use for a regular circuit,
03507      * and we use entry guard nodes.  Just return one of the guard nodes.  */
03508     return choose_random_entry(state);
03509   }
03510 
03511   excluded = smartlist_new();
03512 
03513   if (state && (node = build_state_get_exit_node(state))) {
03514     /* Exclude the exit node from the state, if we have one.  Also exclude its
03515      * family. */
03516     nodelist_add_node_and_family(excluded, node);
03517   }
03518   if (firewall_is_fascist_or()) {
03519     /* Exclude all ORs that we can't reach through our firewall */
03520     smartlist_t *nodes = nodelist_get_list();
03521     SMARTLIST_FOREACH(nodes, const node_t *, node, {
03522       if (!fascist_firewall_allows_node(node))
03523         smartlist_add(excluded, (void*)node);
03524     });
03525   }
03526   /* and exclude current entry guards and their families, if applicable */
03527   if (options->UseEntryGuards && entry_guards) {
03528     SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
03529       {
03530         if ((node = node_get_by_id(entry->identity))) {
03531           nodelist_add_node_and_family(excluded, node);
03532         }
03533       });
03534   }
03535 
03536   if (state) {
03537     if (state->need_uptime)
03538       flags |= CRN_NEED_UPTIME;
03539     if (state->need_capacity)
03540       flags |= CRN_NEED_CAPACITY;
03541   }
03542   if (options->_AllowInvalid & ALLOW_INVALID_ENTRY)
03543     flags |= CRN_ALLOW_INVALID;
03544 
03545   choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
03546   smartlist_free(excluded);
03547   return choice;
03548 }
03549 
03552 static crypt_path_t *
03553 onion_next_hop_in_cpath(crypt_path_t *cpath)
03554 {
03555   crypt_path_t *hop = cpath;
03556   do {
03557     if (hop->state != CPATH_STATE_OPEN)
03558       return hop;
03559     hop = hop->next;
03560   } while (hop != cpath);
03561   return NULL;
03562 }
03563 
03567 static int
03568 onion_extend_cpath(origin_circuit_t *circ)
03569 {
03570   uint8_t purpose = circ->_base.purpose;
03571   cpath_build_state_t *state = circ->build_state;
03572   int cur_len = circuit_get_cpath_len(circ);
03573   extend_info_t *info = NULL;
03574 
03575   if (cur_len >= state->desired_path_len) {
03576     log_debug(LD_CIRC, "Path is complete: %d steps long",
03577               state->desired_path_len);
03578     return 1;
03579   }
03580 
03581   log_debug(LD_CIRC, "Path is %d long; we want %d", cur_len,
03582             state->desired_path_len);
03583 
03584   if (cur_len == state->desired_path_len - 1) { /* Picking last node */
03585     info = extend_info_dup(state->chosen_exit);
03586   } else if (cur_len == 0) { /* picking first node */
03587     const node_t *r = choose_good_entry_server(purpose, state);
03588     if (r) {
03589       /* If we're extending to a bridge, use the preferred address
03590          rather than the primary, for potentially extending to an IPv6
03591          bridge.  */
03592       int use_pref_addr = (r->ri != NULL &&
03593                            r->ri->purpose == ROUTER_PURPOSE_BRIDGE);
03594       info = extend_info_from_node(r, use_pref_addr);
03595       tor_assert(info);
03596     }
03597   } else {
03598     const node_t *r =
03599       choose_good_middle_server(purpose, state, circ->cpath, cur_len);
03600     if (r) {
03601       info = extend_info_from_node(r, 0);
03602       tor_assert(info);
03603     }
03604   }
03605 
03606   if (!info) {
03607     log_warn(LD_CIRC,"Failed to find node for hop %d of our path. Discarding "
03608              "this circuit.", cur_len);
03609     return -1;
03610   }
03611 
03612   log_debug(LD_CIRC,"Chose router %s for hop %d (exit is %s)",
03613             extend_info_describe(info),
03614             cur_len+1, build_state_get_exit_nickname(state));
03615 
03616   onion_append_hop(&circ->cpath, info);
03617   extend_info_free(info);
03618   return 0;
03619 }
03620 
03624 static int
03625 onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice)
03626 {
03627   crypt_path_t *hop = tor_malloc_zero(sizeof(crypt_path_t));
03628 
03629   /* link hop into the cpath, at the end. */
03630   onion_append_to_cpath(head_ptr, hop);
03631 
03632   hop->magic = CRYPT_PATH_MAGIC;
03633   hop->state = CPATH_STATE_CLOSED;
03634 
03635   hop->extend_info = extend_info_dup(choice);
03636 
03637   hop->package_window = circuit_initial_package_window();
03638   hop->deliver_window = CIRCWINDOW_START;
03639 
03640   return 0;
03641 }
03642 
03644 extend_info_t *
03645 extend_info_alloc(const char *nickname, const char *digest,
03646                   crypto_pk_t *onion_key,
03647                   const tor_addr_t *addr, uint16_t port)
03648 {
03649   extend_info_t *info = tor_malloc_zero(sizeof(extend_info_t));
03650   memcpy(info->identity_digest, digest, DIGEST_LEN);
03651   if (nickname)
03652     strlcpy(info->nickname, nickname, sizeof(info->nickname));
03653   if (onion_key)
03654     info->onion_key = crypto_pk_dup_key(onion_key);
03655   tor_addr_copy(&info->addr, addr);
03656   info->port = port;
03657   return info;
03658 }
03659 
03664 extend_info_t *
03665 extend_info_from_router(const routerinfo_t *r, int for_direct_connect)
03666 {
03667   tor_addr_port_t ap;
03668   tor_assert(r);
03669 
03670   if (for_direct_connect)
03671     router_get_pref_orport(r, &ap);
03672   else
03673     router_get_prim_orport(r, &ap);
03674   return extend_info_alloc(r->nickname, r->cache_info.identity_digest,
03675                            r->onion_pkey, &ap.addr, ap.port);
03676 }
03677 
03685 extend_info_t *
03686 extend_info_from_node(const node_t *node, int for_direct_connect)
03687 {
03688   if (node->ri) {
03689     return extend_info_from_router(node->ri, for_direct_connect);
03690   } else if (node->rs && node->md) {
03691     tor_addr_t addr;
03692     tor_addr_from_ipv4h(&addr, node->rs->addr);
03693     return extend_info_alloc(node->rs->nickname,
03694                              node->identity,
03695                              node->md->onion_pkey,
03696                              &addr,
03697                              node->rs->or_port);
03698   } else {
03699     return NULL;
03700   }
03701 }
03702 
03704 void
03705 extend_info_free(extend_info_t *info)
03706 {
03707   if (!info)
03708     return;
03709   crypto_pk_free(info->onion_key);
03710   tor_free(info);
03711 }
03712 
03715 extend_info_t *
03716 extend_info_dup(extend_info_t *info)
03717 {
03718   extend_info_t *newinfo;
03719   tor_assert(info);
03720   newinfo = tor_malloc(sizeof(extend_info_t));
03721   memcpy(newinfo, info, sizeof(extend_info_t));
03722   if (info->onion_key)
03723     newinfo->onion_key = crypto_pk_dup_key(info->onion_key);
03724   else
03725     newinfo->onion_key = NULL;
03726   return newinfo;
03727 }
03728 
03733 const node_t *
03734 build_state_get_exit_node(cpath_build_state_t *state)
03735 {
03736   if (!state || !state->chosen_exit)
03737     return NULL;
03738   return node_get_by_id(state->chosen_exit->identity_digest);
03739 }
03740 
03745 const char *
03746 build_state_get_exit_nickname(cpath_build_state_t *state)
03747 {
03748   if (!state || !state->chosen_exit)
03749     return NULL;
03750   return state->chosen_exit->nickname;
03751 }
03752 
03760 static int
03761 entry_guard_set_status(entry_guard_t *e, const node_t *node,
03762                        time_t now, const or_options_t *options,
03763                        const char **reason)
03764 {
03765   char buf[HEX_DIGEST_LEN+1];
03766   int changed = 0;
03767 
03768   *reason = NULL;
03769 
03770   /* Do we want to mark this guard as bad? */
03771   if (!node)
03772     *reason = "unlisted";
03773   else if (!node->is_running)
03774     *reason = "down";
03775   else if (options->UseBridges && (!node->ri ||
03776                                    node->ri->purpose != ROUTER_PURPOSE_BRIDGE))
03777     *reason = "not a bridge";
03778   else if (options->UseBridges && !node_is_a_configured_bridge(node))
03779     *reason = "not a configured bridge";
03780   else if (!options->UseBridges && !node->is_possible_guard &&
03781            !routerset_contains_node(options->EntryNodes,node))
03782     *reason = "not recommended as a guard";
03783   else if (routerset_contains_node(options->ExcludeNodes, node))
03784     *reason = "excluded";
03785   else if (e->path_bias_disabled)
03786     *reason = "path-biased";
03787 
03788   if (*reason && ! e->bad_since) {
03789     /* Router is newly bad. */
03790     base16_encode(buf, sizeof(buf), e->identity, DIGEST_LEN);
03791     log_info(LD_CIRC, "Entry guard %s (%s) is %s: marking as unusable.",
03792              e->nickname, buf, *reason);
03793 
03794     e->bad_since = now;
03795     control_event_guard(e->nickname, e->identity, "BAD");
03796     changed = 1;
03797   } else if (!*reason && e->bad_since) {
03798     /* There's nothing wrong with the router any more. */
03799     base16_encode(buf, sizeof(buf), e->identity, DIGEST_LEN);
03800     log_info(LD_CIRC, "Entry guard %s (%s) is no longer unusable: "
03801              "marking as ok.", e->nickname, buf);
03802 
03803     e->bad_since = 0;
03804     control_event_guard(e->nickname, e->identity, "GOOD");
03805     changed = 1;
03806   }
03807   return changed;
03808 }
03809 
03812 static int
03813 entry_is_time_to_retry(entry_guard_t *e, time_t now)
03814 {
03815   long diff;
03816   if (e->last_attempted < e->unreachable_since)
03817     return 1;
03818   diff = now - e->unreachable_since;
03819   if (diff < 6*60*60)
03820     return now > (e->last_attempted + 60*60);
03821   else if (diff < 3*24*60*60)
03822     return now > (e->last_attempted + 4*60*60);
03823   else if (diff < 7*24*60*60)
03824     return now > (e->last_attempted + 18*60*60);
03825   else
03826     return now > (e->last_attempted + 36*60*60);
03827 }
03828 
03843 static INLINE const node_t *
03844 entry_is_live(entry_guard_t *e, int need_uptime, int need_capacity,
03845               int assume_reachable, const char **msg)
03846 {
03847   const node_t *node;
03848   const or_options_t *options = get_options();
03849   tor_assert(msg);
03850 
03851   if (e->path_bias_disabled) {
03852     *msg = "path-biased";
03853     return NULL;
03854   }
03855   if (e->bad_since) {
03856     *msg = "bad";
03857     return NULL;
03858   }
03859   /* no good if it's unreachable, unless assume_unreachable or can_retry. */
03860   if (!assume_reachable && !e->can_retry &&
03861       e->unreachable_since && !entry_is_time_to_retry(e, time(NULL))) {
03862     *msg = "unreachable";
03863     return NULL;
03864   }
03865   node = node_get_by_id(e->identity);
03866   if (!node || !node_has_descriptor(node)) {
03867     *msg = "no descriptor";
03868     return NULL;
03869   }
03870   if (get_options()->UseBridges) {
03871     if (node_get_purpose(node) != ROUTER_PURPOSE_BRIDGE) {
03872       *msg = "not a bridge";
03873       return NULL;
03874     }
03875     if (!node_is_a_configured_bridge(node)) {
03876       *msg = "not a configured bridge";
03877       return NULL;
03878     }
03879   } else { /* !get_options()->UseBridges */
03880     if (node_get_purpose(node) != ROUTER_PURPOSE_GENERAL) {
03881       *msg = "not general-purpose";
03882       return NULL;
03883     }
03884   }
03885   if (routerset_contains_node(options->EntryNodes, node)) {
03886     /* they asked for it, they get it */
03887     need_uptime = need_capacity = 0;
03888   }
03889   if (node_is_unreliable(node, need_uptime, need_capacity, 0)) {
03890     *msg = "not fast/stable";
03891     return NULL;
03892   }
03893   if (!fascist_firewall_allows_node(node)) {
03894     *msg = "unreachable by config";
03895     return NULL;
03896   }
03897   return node;
03898 }
03899 
03901 static int
03902 num_live_entry_guards(void)
03903 {
03904   int n = 0;
03905   const char *msg;
03906   if (! entry_guards)
03907     return 0;
03908   SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
03909     {
03910       if (entry_is_live(entry, 0, 1, 0, &msg))
03911         ++n;
03912     });
03913   return n;
03914 }
03915 
03918 static entry_guard_t *
03919 entry_guard_get_by_id_digest(const char *digest)
03920 {
03921   SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
03922                     if (tor_memeq(digest, entry->identity, DIGEST_LEN))
03923                       return entry;
03924                    );
03925   return NULL;
03926 }
03927 
03930 static void
03931 log_entry_guards(int severity)
03932 {
03933   smartlist_t *elements = smartlist_new();
03934   char *s;
03935 
03936   SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e)
03937     {
03938       const char *msg = NULL;
03939       if (entry_is_live(e, 0, 1, 0, &msg))
03940         smartlist_add_asprintf(elements, "%s [%s] (up %s)",
03941                      e->nickname,
03942                      hex_str(e->identity, DIGEST_LEN),
03943                      e->made_contact ? "made-contact" : "never-contacted");
03944       else
03945         smartlist_add_asprintf(elements, "%s [%s] (%s, %s)",
03946                      e->nickname,
03947                      hex_str(e->identity, DIGEST_LEN),
03948                      msg,
03949                      e->made_contact ? "made-contact" : "never-contacted");
03950     }
03951   SMARTLIST_FOREACH_END(e);
03952 
03953   s = smartlist_join_strings(elements, ",", 0, NULL);
03954   SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
03955   smartlist_free(elements);
03956   log_fn(severity,LD_CIRC,"%s",s);
03957   tor_free(s);
03958 }
03959 
03963 static void
03964 control_event_guard_deferred(void)
03965 {
03966   /* XXXX We don't actually have a good way to figure out _how many_ entries
03967    * are live for some purpose.  We need an entry_is_even_slightly_live()
03968    * function for this to work right.  NumEntryGuards isn't reliable: if we
03969    * need guards with weird properties, we can have more than that number
03970    * live.
03971    **/
03972 #if 0
03973   int n = 0;
03974   const char *msg;
03975   const or_options_t *options = get_options();
03976   if (!entry_guards)
03977     return;
03978   SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
03979     {
03980       if (entry_is_live(entry, 0, 1, 0, &msg)) {
03981         if (n++ == options->NumEntryGuards) {
03982           control_event_guard(entry->nickname, entry->identity, "DEFERRED");
03983           return;
03984         }
03985       }
03986     });
03987 #endif
03988 }
03989 
03997 static const node_t *
03998 add_an_entry_guard(const node_t *chosen, int reset_status, int prepend)
03999 {
04000   const node_t *node;
04001   entry_guard_t *entry;
04002 
04003   if (chosen) {
04004     node = chosen;
04005     entry = entry_guard_get_by_id_digest(node->identity);
04006     if (entry) {
04007       if (reset_status) {
04008         entry->bad_since = 0;
04009         entry->can_retry = 1;
04010       }
04011       return NULL;
04012     }
04013   } else {
04014     node = choose_good_entry_server(CIRCUIT_PURPOSE_C_GENERAL, NULL);
04015     if (!node)
04016       return NULL;
04017   }
04018   entry = tor_malloc_zero(sizeof(entry_guard_t));
04019   log_info(LD_CIRC, "Chose %s as new entry guard.",
04020            node_describe(node));
04021   strlcpy(entry->nickname, node_get_nickname(node), sizeof(entry->nickname));
04022   memcpy(entry->identity, node->identity, DIGEST_LEN);
04023   /* Choose expiry time smudged over the past month. The goal here
04024    * is to a) spread out when Tor clients rotate their guards, so they
04025    * don't all select them on the same day, and b) avoid leaving a
04026    * precise timestamp in the state file about when we first picked
04027    * this guard. For details, see the Jan 2010 or-dev thread. */
04028   entry->chosen_on_date = time(NULL) - crypto_rand_int(3600*24*30);
04029   entry->chosen_by_version = tor_strdup(VERSION);
04030   if (prepend)
04031     smartlist_insert(entry_guards, 0, entry);
04032   else
04033     smartlist_add(entry_guards, entry);
04034   control_event_guard(entry->nickname, entry->identity, "NEW");
04035   control_event_guard_deferred();
04036   log_entry_guards(LOG_INFO);
04037   return node;
04038 }
04039 
04042 static void
04043 pick_entry_guards(const or_options_t *options)
04044 {
04045   int changed = 0;
04046 
04047   tor_assert(entry_guards);
04048 
04049   while (num_live_entry_guards() < options->NumEntryGuards) {
04050     if (!add_an_entry_guard(NULL, 0, 0))
04051       break;
04052     changed = 1;
04053   }
04054   if (changed)
04055     entry_guards_changed();
04056 }
04057 
04060 #define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60)
04061 
04063 static void
04064 entry_guard_free(entry_guard_t *e)
04065 {
04066   if (!e)
04067     return;
04068   tor_free(e->chosen_by_version);
04069   tor_free(e);
04070 }
04071 
04075 /* XXXX The "obsolete guards" and "chosen long ago guards" things should
04076  * probably be different functions. */
04077 static int
04078 remove_obsolete_entry_guards(time_t now)
04079 {
04080   int changed = 0, i;
04081 
04082   for (i = 0; i < smartlist_len(entry_guards); ++i) {
04083     entry_guard_t *entry = smartlist_get(entry_guards, i);
04084     const char *ver = entry->chosen_by_version;
04085     const char *msg = NULL;
04086     tor_version_t v;
04087     int version_is_bad = 0, date_is_bad = 0;
04088     if (!ver) {
04089       msg = "does not say what version of Tor it was selected by";
04090       version_is_bad = 1;
04091     } else if (tor_version_parse(ver, &v)) {
04092       msg = "does not seem to be from any recognized version of Tor";
04093       version_is_bad = 1;
04094     } else {
04095       char *tor_ver = NULL;
04096       tor_asprintf(&tor_ver, "Tor %s", ver);
04097       if ((tor_version_as_new_as(tor_ver, "0.1.0.10-alpha") &&
04098            !tor_version_as_new_as(tor_ver, "0.1.2.16-dev")) ||
04099           (tor_version_as_new_as(tor_ver, "0.2.0.0-alpha") &&
04100            !tor_version_as_new_as(tor_ver, "0.2.0.6-alpha")) ||
04101           /* above are bug 440; below are bug 1217 */
04102           (tor_version_as_new_as(tor_ver, "0.2.1.3-alpha") &&
04103            !tor_version_as_new_as(tor_ver, "0.2.1.23")) ||
04104           (tor_version_as_new_as(tor_ver, "0.2.2.0-alpha") &&
04105            !tor_version_as_new_as(tor_ver, "0.2.2.7-alpha"))) {
04106         msg = "was selected without regard for guard bandwidth";
04107         version_is_bad = 1;
04108       }
04109       tor_free(tor_ver);
04110     }
04111     if (!version_is_bad && entry->chosen_on_date + 3600*24*60 < now) {
04112       /* It's been 2 months since the date listed in our state file. */
04113       msg = "was selected several months ago";
04114       date_is_bad = 1;
04115     }
04116 
04117     if (version_is_bad || date_is_bad) { /* we need to drop it */
04118       char dbuf[HEX_DIGEST_LEN+1];
04119       tor_assert(msg);
04120       base16_encode(dbuf, sizeof(dbuf), entry->identity, DIGEST_LEN);
04121       log_fn(version_is_bad ? LOG_NOTICE : LOG_INFO, LD_CIRC,
04122              "Entry guard '%s' (%s) %s. (Version=%s.) Replacing it.",
04123              entry->nickname, dbuf, msg, ver?escaped(ver):"none");
04124       control_event_guard(entry->nickname, entry->identity, "DROPPED");
04125       entry_guard_free(entry);
04126       smartlist_del_keeporder(entry_guards, i--);
04127       log_entry_guards(LOG_INFO);
04128       changed = 1;
04129     }
04130   }
04131 
04132   return changed ? 1 : 0;
04133 }
04134 
04138 static int
04139 remove_dead_entry_guards(time_t now)
04140 {
04141   char dbuf[HEX_DIGEST_LEN+1];
04142   char tbuf[ISO_TIME_LEN+1];
04143   int i;
04144   int changed = 0;
04145 
04146   for (i = 0; i < smartlist_len(entry_guards); ) {
04147     entry_guard_t *entry = smartlist_get(entry_guards, i);
04148     if (entry->bad_since &&
04149         ! entry->path_bias_disabled &&
04150         entry->bad_since + ENTRY_GUARD_REMOVE_AFTER < now) {
04151 
04152       base16_encode(dbuf, sizeof(dbuf), entry->identity, DIGEST_LEN);
04153       format_local_iso_time(tbuf, entry->bad_since);
04154       log_info(LD_CIRC, "Entry guard '%s' (%s) has been down or unlisted "
04155                "since %s local time; removing.",
04156                entry->nickname, dbuf, tbuf);
04157       control_event_guard(entry->nickname, entry->identity, "DROPPED");
04158       entry_guard_free(entry);
04159       smartlist_del_keeporder(entry_guards, i);
04160       log_entry_guards(LOG_INFO);
04161       changed = 1;
04162     } else
04163       ++i;
04164   }
04165   return changed ? 1 : 0;
04166 }
04167 
04177 void
04178 entry_guards_compute_status(const or_options_t *options, time_t now)
04179 {
04180   int changed = 0;
04181   digestmap_t *reasons;
04182 
04183   if (! entry_guards)
04184     return;
04185 
04186   if (options->EntryNodes) /* reshuffle the entry guard list if needed */
04187     entry_nodes_should_be_added();
04188 
04189   reasons = digestmap_new();
04190   SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry)
04191     {
04192       const node_t *r = node_get_by_id(entry->identity);
04193       const char *reason = NULL;
04194       if (entry_guard_set_status(entry, r, now, options, &reason))
04195         changed = 1;
04196 
04197       if (entry->bad_since)
04198         tor_assert(reason);
04199       if (reason)
04200         digestmap_set(reasons, entry->identity, (char*)reason);
04201     }
04202   SMARTLIST_FOREACH_END(entry);
04203 
04204   if (remove_dead_entry_guards(now))
04205     changed = 1;
04206   if (remove_obsolete_entry_guards(now))
04207     changed = 1;
04208 
04209   if (changed) {
04210     SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) {
04211       const char *reason = digestmap_get(reasons, entry->identity);
04212       const char *live_msg = "";
04213       const node_t *r = entry_is_live(entry, 0, 1, 0, &live_msg);
04214       log_info(LD_CIRC, "Summary: Entry %s [%s] is %s, %s%s%s, and %s%s.",
04215                entry->nickname,
04216                hex_str(entry->identity, DIGEST_LEN),
04217                entry->unreachable_since ? "unreachable" : "reachable",
04218                entry->bad_since ? "unusable" : "usable",
04219                reason ? ", ": "",
04220                reason ? reason : "",
04221                r ? "live" : "not live / ",
04222                r ? "" : live_msg);
04223     } SMARTLIST_FOREACH_END(entry);
04224     log_info(LD_CIRC, "    (%d/%d entry guards are usable/new)",
04225              num_live_entry_guards(), smartlist_len(entry_guards));
04226     log_entry_guards(LOG_INFO);
04227     entry_guards_changed();
04228   }
04229 
04230   digestmap_free(reasons, NULL);
04231 }
04232 
04243 int
04244 entry_guard_register_connect_status(const char *digest, int succeeded,
04245                                     int mark_relay_status, time_t now)
04246 {
04247   int changed = 0;
04248   int refuse_conn = 0;
04249   int first_contact = 0;
04250   entry_guard_t *entry = NULL;
04251   int idx = -1;
04252   char buf[HEX_DIGEST_LEN+1];
04253 
04254   if (! entry_guards)
04255     return 0;
04256 
04257   SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
04258     tor_assert(e);
04259     if (tor_memeq(e->identity, digest, DIGEST_LEN)) {
04260       entry = e;
04261       idx = e_sl_idx;
04262       break;
04263     }
04264   } SMARTLIST_FOREACH_END(e);
04265 
04266   if (!entry)
04267     return 0;
04268 
04269   base16_encode(buf, sizeof(buf), entry->identity, DIGEST_LEN);
04270 
04271   if (succeeded) {
04272     if (entry->unreachable_since) {
04273       log_info(LD_CIRC, "Entry guard '%s' (%s) is now reachable again. Good.",
04274                entry->nickname, buf);
04275       entry->can_retry = 0;
04276       entry->unreachable_since = 0;
04277       entry->last_attempted = now;
04278       control_event_guard(entry->nickname, entry->identity, "UP");
04279       changed = 1;
04280     }
04281     if (!entry->made_contact) {
04282       entry->made_contact = 1;
04283       first_contact = changed = 1;
04284     }
04285   } else { /* ! succeeded */
04286     if (!entry->made_contact) {
04287       /* We've never connected to this one. */
04288       log_info(LD_CIRC,
04289                "Connection to never-contacted entry guard '%s' (%s) failed. "
04290                "Removing from the list. %d/%d entry guards usable/new.",
04291                entry->nickname, buf,
04292                num_live_entry_guards()-1, smartlist_len(entry_guards)-1);
04293       control_event_guard(entry->nickname, entry->identity, "DROPPED");
04294       entry_guard_free(entry);
04295       smartlist_del_keeporder(entry_guards, idx);
04296       log_entry_guards(LOG_INFO);
04297       changed = 1;
04298     } else if (!entry->unreachable_since) {
04299       log_info(LD_CIRC, "Unable to connect to entry guard '%s' (%s). "
04300                "Marking as unreachable.", entry->nickname, buf);
04301       entry->unreachable_since = entry->last_attempted = now;
04302       control_event_guard(entry->nickname, entry->identity, "DOWN");
04303       changed = 1;
04304       entry->can_retry = 0; /* We gave it an early chance; no good. */
04305     } else {
04306       char tbuf[ISO_TIME_LEN+1];
04307       format_iso_time(tbuf, entry->unreachable_since);
04308       log_debug(LD_CIRC, "Failed to connect to unreachable entry guard "
04309                 "'%s' (%s).  It has been unreachable since %s.",
04310                 entry->nickname, buf, tbuf);
04311       entry->last_attempted = now;
04312       entry->can_retry = 0; /* We gave it an early chance; no good. */
04313     }
04314   }
04315 
04316   /* if the caller asked us to, also update the is_running flags for this
04317    * relay */
04318   if (mark_relay_status)
04319     router_set_status(digest, succeeded);
04320 
04321   if (first_contact) {
04322     /* We've just added a new long-term entry guard. Perhaps the network just
04323      * came back? We should give our earlier entries another try too,
04324      * and close this connection so we don't use it before we've given
04325      * the others a shot. */
04326     SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, {
04327         if (e == entry)
04328           break;
04329         if (e->made_contact) {
04330           const char *msg;
04331           const node_t *r = entry_is_live(e, 0, 1, 1, &msg);
04332           if (r && e->unreachable_since) {
04333             refuse_conn = 1;
04334             e->can_retry = 1;
04335           }
04336         }
04337       });
04338     if (refuse_conn) {
04339       log_info(LD_CIRC,
04340                "Connected to new entry guard '%s' (%s). Marking earlier "
04341                "entry guards up. %d/%d entry guards usable/new.",
04342                entry->nickname, buf,
04343                num_live_entry_guards(), smartlist_len(entry_guards));
04344       log_entry_guards(LOG_INFO);
04345       changed = 1;
04346     }
04347   }
04348 
04349   if (changed)
04350     entry_guards_changed();
04351   return refuse_conn ? -1 : 0;
04352 }
04353 
04356 static int should_add_entry_nodes = 0;
04357 
04359 void
04360 entry_nodes_should_be_added(void)
04361 {
04362   log_info(LD_CIRC, "EntryNodes config option set. Putting configured "
04363            "relays at the front of the entry guard list.");
04364   should_add_entry_nodes = 1;
04365 }
04366 
04369 static void
04370 entry_guards_set_from_config(const or_options_t *options)
04371 {
04372   smartlist_t *entry_nodes, *worse_entry_nodes, *entry_fps;
04373   smartlist_t *old_entry_guards_on_list, *old_entry_guards_not_on_list;
04374   tor_assert(entry_guards);
04375 
04376   should_add_entry_nodes = 0;
04377 
04378   if (!options->EntryNodes) {
04379     /* It's possible that a controller set EntryNodes, thus making
04380      * should_add_entry_nodes set, then cleared it again, all before the
04381      * call to choose_random_entry() that triggered us. If so, just return.
04382      */
04383     return;
04384   }
04385 
04386   {
04387     char *string = routerset_to_string(options->EntryNodes);
04388     log_info(LD_CIRC,"Adding configured EntryNodes '%s'.", string);
04389     tor_free(string);
04390   }
04391 
04392   entry_nodes = smartlist_new();
04393   worse_entry_nodes = smartlist_new();
04394   entry_fps = smartlist_new();
04395   old_entry_guards_on_list = smartlist_new();
04396   old_entry_guards_not_on_list = smartlist_new();
04397 
04398   /* Split entry guards into those on the list and those not. */
04399 
04400   routerset_get_all_nodes(entry_nodes, options->EntryNodes,
04401                           options->ExcludeNodes, 0);
04402   SMARTLIST_FOREACH(entry_nodes, const node_t *,node,
04403                     smartlist_add(entry_fps, (void*)node->identity));
04404 
04405   SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, {
04406     if (smartlist_digest_isin(entry_fps, e->identity))
04407       smartlist_add(old_entry_guards_on_list, e);
04408     else
04409       smartlist_add(old_entry_guards_not_on_list, e);
04410   });
04411 
04412   /* Remove all currently configured guard nodes, excluded nodes, unreachable
04413    * nodes, or non-Guard nodes from entry_nodes. */
04414   SMARTLIST_FOREACH_BEGIN(entry_nodes, const node_t *, node) {
04415     if (entry_guard_get_by_id_digest(node->identity)) {
04416       SMARTLIST_DEL_CURRENT(entry_nodes, node);
04417       continue;
04418     } else if (routerset_contains_node(options->ExcludeNodes, node)) {
04419       SMARTLIST_DEL_CURRENT(entry_nodes, node);
04420       continue;
04421     } else if (!fascist_firewall_allows_node(node)) {
04422       SMARTLIST_DEL_CURRENT(entry_nodes, node);
04423       continue;
04424     } else if (! node->is_possible_guard) {
04425       smartlist_add(worse_entry_nodes, (node_t*)node);
04426       SMARTLIST_DEL_CURRENT(entry_nodes, node);
04427     }
04428   } SMARTLIST_FOREACH_END(node);
04429 
04430   /* Now build the new entry_guards list. */
04431   smartlist_clear(entry_guards);
04432   /* First, the previously configured guards that are in EntryNodes. */
04433   smartlist_add_all(entry_guards, old_entry_guards_on_list);
04434   /* Next, scramble the rest of EntryNodes, putting the guards first. */
04435   smartlist_shuffle(entry_nodes);
04436   smartlist_shuffle(worse_entry_nodes);
04437   smartlist_add_all(entry_nodes, worse_entry_nodes);
04438 
04439   /* Next, the rest of EntryNodes */
04440   SMARTLIST_FOREACH_BEGIN(entry_nodes, const node_t *, node) {
04441     add_an_entry_guard(node, 0, 0);
04442     if (smartlist_len(entry_guards) > options->NumEntryGuards * 10)
04443       break;
04444   } SMARTLIST_FOREACH_END(node);
04445   log_notice(LD_GENERAL, "%d entries in guards", smartlist_len(entry_guards));
04446   /* Finally, free the remaining previously configured guards that are not in
04447    * EntryNodes. */
04448   SMARTLIST_FOREACH(old_entry_guards_not_on_list, entry_guard_t *, e,
04449                     entry_guard_free(e));
04450 
04451   smartlist_free(entry_nodes);
04452   smartlist_free(worse_entry_nodes);
04453   smartlist_free(entry_fps);
04454   smartlist_free(old_entry_guards_on_list);
04455   smartlist_free(old_entry_guards_not_on_list);
04456   entry_guards_changed();
04457 }
04458 
04463 int
04464 entry_list_is_constrained(const or_options_t *options)
04465 {
04466   if (options->EntryNodes)
04467     return 1;
04468   if (options->UseBridges)
04469     return 1;
04470   return 0;
04471 }
04472 
04478 const node_t *
04479 choose_random_entry(cpath_build_state_t *state)
04480 {
04481   const or_options_t *options = get_options();
04482   smartlist_t *live_entry_guards = smartlist_new();
04483   smartlist_t *exit_family = smartlist_new();
04484   const node_t *chosen_exit =
04485     state?build_state_get_exit_node(state) : NULL;
04486   const node_t *node = NULL;
04487   int need_uptime = state ? state->need_uptime : 0;
04488   int need_capacity = state ? state->need_capacity : 0;
04489   int preferred_min, consider_exit_family = 0;
04490 
04491   if (chosen_exit) {
04492     nodelist_add_node_and_family(exit_family, chosen_exit);
04493     consider_exit_family = 1;
04494   }
04495 
04496   if (!entry_guards)
04497     entry_guards = smartlist_new();
04498 
04499   if (should_add_entry_nodes)
04500     entry_guards_set_from_config(options);
04501 
04502   if (!entry_list_is_constrained(options) &&
04503       smartlist_len(entry_guards) < options->NumEntryGuards)
04504     pick_entry_guards(options);
04505 
04506  retry:
04507   smartlist_clear(live_entry_guards);
04508   SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) {
04509       const char *msg;
04510       node = entry_is_live(entry, need_uptime, need_capacity, 0, &msg);
04511       if (!node)
04512         continue; /* down, no point */
04513       if (node == chosen_exit)
04514         continue; /* don't pick the same node for entry and exit */
04515       if (consider_exit_family && smartlist_isin(exit_family, node))
04516         continue; /* avoid relays that are family members of our exit */
04517 #if 0 /* since EntryNodes is always strict now, this clause is moot */
04518       if (options->EntryNodes &&
04519           !routerset_contains_node(options->EntryNodes, node)) {
04520         /* We've come to the end of our preferred entry nodes. */
04521         if (smartlist_len(live_entry_guards))
04522           goto choose_and_finish; /* only choose from the ones we like */
04523         if (options->StrictNodes) {
04524           /* in theory this case should never happen, since
04525            * entry_guards_set_from_config() drops unwanted relays */
04526           tor_fragile_assert();
04527         } else {
04528           log_info(LD_CIRC,
04529                    "No relays from EntryNodes available. Using others.");
04530         }
04531       }
04532 #endif
04533       smartlist_add(live_entry_guards, (void*)node);
04534       if (!entry->made_contact) {
04535         /* Always start with the first not-yet-contacted entry
04536          * guard. Otherwise we might add several new ones, pick
04537          * the second new one, and now we've expanded our entry
04538          * guard list without needing to. */
04539         goto choose_and_finish;
04540       }
04541       if (smartlist_len(live_entry_guards) >= options->NumEntryGuards)
04542         goto choose_and_finish; /* we have enough */
04543   } SMARTLIST_FOREACH_END(entry);
04544 
04545   if (entry_list_is_constrained(options)) {
04546     /* If we prefer the entry nodes we've got, and we have at least
04547      * one choice, that's great. Use it. */
04548     preferred_min = 1;
04549   } else {
04550     /* Try to have at least 2 choices available. This way we don't
04551      * get stuck with a single live-but-crummy entry and just keep
04552      * using him.
04553      * (We might get 2 live-but-crummy entry guards, but so be it.) */
04554     preferred_min = 2;
04555   }
04556 
04557   if (smartlist_len(live_entry_guards) < preferred_min) {
04558     if (!entry_list_is_constrained(options)) {
04559       /* still no? try adding a new entry then */
04560       /* XXX if guard doesn't imply fast and stable, then we need
04561        * to tell add_an_entry_guard below what we want, or it might
04562        * be a long time til we get it. -RD */
04563       node = add_an_entry_guard(NULL, 0, 0);
04564       if (node) {
04565         entry_guards_changed();
04566         /* XXX we start over here in case the new node we added shares
04567          * a family with our exit node. There's a chance that we'll just
04568          * load up on entry guards here, if the network we're using is
04569          * one big family. Perhaps we should teach add_an_entry_guard()
04570          * to understand nodes-to-avoid-if-possible? -RD */
04571         goto retry;
04572       }
04573     }
04574     if (!node && need_uptime) {
04575       need_uptime = 0; /* try without that requirement */
04576       goto retry;
04577     }
04578     if (!node && need_capacity) {
04579       /* still no? last attempt, try without requiring capacity */
04580       need_capacity = 0;
04581       goto retry;
04582     }
04583 #if 0
04584     /* Removing this retry logic: if we only allow one exit, and it is in the
04585        same family as all our entries, then we are just plain not going to win
04586        here. */
04587     if (!node && entry_list_is_constrained(options) && consider_exit_family) {
04588       /* still no? if we're using bridges or have strictentrynodes
04589        * set, and our chosen exit is in the same family as all our
04590        * bridges/entry guards, then be flexible about families. */
04591       consider_exit_family = 0;
04592       goto retry;
04593     }
04594 #endif
04595     /* live_entry_guards may be empty below. Oh well, we tried. */
04596   }
04597 
04598  choose_and_finish:
04599   if (entry_list_is_constrained(options)) {
04600     /* We need to weight by bandwidth, because our bridges or entryguards
04601      * were not already selected proportional to their bandwidth. */
04602     node = node_sl_choose_by_bandwidth(live_entry_guards, WEIGHT_FOR_GUARD);
04603   } else {
04604     /* We choose uniformly at random here, because choose_good_entry_server()
04605      * already weights its choices by bandwidth, so we don't want to
04606      * *double*-weight our guard selection. */
04607     node = smartlist_choose(live_entry_guards);
04608   }
04609   smartlist_free(live_entry_guards);
04610   smartlist_free(exit_family);
04611   return node;
04612 }
04613 
04620 int
04621 entry_guards_parse_state(or_state_t *state, int set, char **msg)
04622 {
04623   entry_guard_t *node = NULL;
04624   smartlist_t *new_entry_guards = smartlist_new();
04625   config_line_t *line;
04626   time_t now = time(NULL);
04627   const char *state_version = state->TorVersion;
04628   digestmap_t *added_by = digestmap_new();
04629 
04630   *msg = NULL;
04631   for (line = state->EntryGuards; line; line = line->next) {
04632     if (!strcasecmp(line->key, "EntryGuard")) {
04633       smartlist_t *args = smartlist_new();
04634       node = tor_malloc_zero(sizeof(entry_guard_t));
04635       /* all entry guards on disk have been contacted */
04636       node->made_contact = 1;
04637       smartlist_add(new_entry_guards, node);
04638       smartlist_split_string(args, line->value, " ",
04639                              SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
04640       if (smartlist_len(args)<2) {
04641         *msg = tor_strdup("Unable to parse entry nodes: "
04642                           "Too few arguments to EntryGuard");
04643       } else if (!is_legal_nickname(smartlist_get(args,0))) {
04644         *msg = tor_strdup("Unable to parse entry nodes: "
04645                           "Bad nickname for EntryGuard");
04646       } else {
04647         strlcpy(node->nickname, smartlist_get(args,0), MAX_NICKNAME_LEN+1);
04648         if (base16_decode(node->identity, DIGEST_LEN, smartlist_get(args,1),
04649                           strlen(smartlist_get(args,1)))<0) {
04650           *msg = tor_strdup("Unable to parse entry nodes: "
04651                             "Bad hex digest for EntryGuard");
04652         }
04653       }
04654       SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
04655       smartlist_free(args);
04656       if (*msg)
04657         break;
04658     } else if (!strcasecmp(line->key, "EntryGuardDownSince") ||
04659                !strcasecmp(line->key, "EntryGuardUnlistedSince")) {
04660       time_t when;
04661       time_t last_try = 0;
04662       if (!node) {
04663         *msg = tor_strdup("Unable to parse entry nodes: "
04664                "EntryGuardDownSince/UnlistedSince without EntryGuard");
04665         break;
04666       }
04667       if (parse_iso_time(line->value, &when)<0) {
04668         *msg = tor_strdup("Unable to parse entry nodes: "
04669                           "Bad time in EntryGuardDownSince/UnlistedSince");
04670         break;
04671       }
04672       if (when > now) {
04673         /* It's a bad idea to believe info in the future: you can wind
04674          * up with timeouts that aren't allowed to happen for years. */
04675         continue;
04676       }
04677       if (strlen(line->value) >= ISO_TIME_LEN+ISO_TIME_LEN+1) {
04678         /* ignore failure */
04679         (void) parse_iso_time(line->value+ISO_TIME_LEN+1, &last_try);
04680       }
04681       if (!strcasecmp(line->key, "EntryGuardDownSince")) {
04682         node->unreachable_since = when;
04683         node->last_attempted = last_try;
04684       } else {
04685         node->bad_since = when;
04686       }
04687     } else if (!strcasecmp(line->key, "EntryGuardAddedBy")) {
04688       char d[DIGEST_LEN];
04689       /* format is digest version date */
04690       if (strlen(line->value) < HEX_DIGEST_LEN+1+1+1+ISO_TIME_LEN) {
04691         log_warn(LD_BUG, "EntryGuardAddedBy line is not long enough.");
04692         continue;
04693       }
04694       if (base16_decode(d, sizeof(d), line->value, HEX_DIGEST_LEN)<0 ||
04695           line->value[HEX_DIGEST_LEN] != ' ') {
04696         log_warn(LD_BUG, "EntryGuardAddedBy line %s does not begin with "
04697                  "hex digest", escaped(line->value));
04698         continue;
04699       }
04700       digestmap_set(added_by, d, tor_strdup(line->value+HEX_DIGEST_LEN+1));
04701     } else if (!strcasecmp(line->key, "EntryGuardPathBias")) {
04702       const or_options_t *options = get_options();
04703       unsigned hop_cnt, success_cnt;
04704 
04705       if (tor_sscanf(line->value, "%u %u", &success_cnt, &hop_cnt) != 2) {
04706         log_warn(LD_GENERAL, "Unable to parse guard path bias info: "
04707                  "Misformated EntryGuardPathBias %s", escaped(line->value));
04708         continue;
04709       }
04710 
04711       node->first_hops = hop_cnt;
04712       node->circuit_successes = success_cnt;
04713       log_info(LD_GENERAL, "Read %u/%u path bias for node %s",
04714                node->circuit_successes, node->first_hops, node->nickname);
04715       /* Note: We rely on the < comparison here to allow us to set a 0
04716        * rate and disable the feature entirely. If refactoring, don't
04717        * change to <= */
04718       if (node->circuit_successes/((double)node->first_hops)
04719           < pathbias_get_disable_rate(options)) {
04720         node->path_bias_disabled = 1;
04721         log_info(LD_GENERAL,
04722                  "Path bias is too high (%u/%u); disabling node %s",
04723                  node->circuit_successes, node->first_hops, node->nickname);
04724       }
04725 
04726     } else {
04727       log_warn(LD_BUG, "Unexpected key %s", line->key);
04728     }
04729   }
04730 
04731   SMARTLIST_FOREACH(new_entry_guards, entry_guard_t *, e,
04732    {
04733      char *sp;
04734      char *val = digestmap_get(added_by, e->identity);
04735      if (val && (sp = strchr(val, ' '))) {
04736        time_t when;
04737        *sp++ = '\0';
04738        if (parse_iso_time(sp, &when)<0) {
04739          log_warn(LD_BUG, "Can't read time %s in EntryGuardAddedBy", sp);
04740        } else {
04741          e->chosen_by_version = tor_strdup(val);
04742          e->chosen_on_date = when;
04743        }
04744      } else {
04745        if (state_version) {
04746          e->chosen_by_version = tor_strdup(state_version);
04747          e->chosen_on_date = time(NULL) - crypto_rand_int(3600*24*30);
04748        }
04749      }
04750      if (node->path_bias_disabled && !node->bad_since)
04751        node->bad_since = time(NULL);
04752    });
04753 
04754   if (*msg || !set) {
04755     SMARTLIST_FOREACH(new_entry_guards, entry_guard_t *, e,
04756                       entry_guard_free(e));
04757     smartlist_free(new_entry_guards);
04758   } else { /* !err && set */
04759     if (entry_guards) {
04760       SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
04761                         entry_guard_free(e));
04762       smartlist_free(entry_guards);
04763     }
04764     entry_guards = new_entry_guards;
04765     entry_guards_dirty = 0;
04766     /* XXX024 hand new_entry_guards to this func, and move it up a
04767      * few lines, so we don't have to re-dirty it */
04768     if (remove_obsolete_entry_guards(now))
04769       entry_guards_dirty = 1;
04770   }
04771   digestmap_free(added_by, _tor_free);
04772   return *msg ? -1 : 0;
04773 }
04774 
04779 static void
04780 entry_guards_changed(void)
04781 {
04782   time_t when;
04783   entry_guards_dirty = 1;
04784 
04785   /* or_state_save() will call entry_guards_update_state(). */
04786   when = get_options()->AvoidDiskWrites ? time(NULL) + 3600 : time(NULL)+600;
04787   or_state_mark_dirty(get_or_state(), when);
04788 }
04789 
04795 void
04796 entry_guards_update_state(or_state_t *state)
04797 {
04798   config_line_t **next, *line;
04799   if (! entry_guards_dirty)
04800     return;
04801 
04802   config_free_lines(state->EntryGuards);
04803   next = &state->EntryGuards;
04804   *next = NULL;
04805   if (!entry_guards)
04806     entry_guards = smartlist_new();
04807   SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
04808     {
04809       char dbuf[HEX_DIGEST_LEN+1];
04810       if (!e->made_contact)
04811         continue; /* don't write this one to disk */
04812       *next = line = tor_malloc_zero(sizeof(config_line_t));
04813       line->key = tor_strdup("EntryGuard");
04814       base16_encode(dbuf, sizeof(dbuf), e->identity, DIGEST_LEN);
04815       tor_asprintf(&line->value, "%s %s", e->nickname, dbuf);
04816       next = &(line->next);
04817       if (e->unreachable_since) {
04818         *next = line = tor_malloc_zero(sizeof(config_line_t));
04819         line->key = tor_strdup("EntryGuardDownSince");
04820         line->value = tor_malloc(ISO_TIME_LEN+1+ISO_TIME_LEN+1);
04821         format_iso_time(line->value, e->unreachable_since);
04822         if (e->last_attempted) {
04823           line->value[ISO_TIME_LEN] = ' ';
04824           format_iso_time(line->value+ISO_TIME_LEN+1, e->last_attempted);
04825         }
04826         next = &(line->next);
04827       }
04828       if (e->bad_since) {
04829         *next = line = tor_malloc_zero(sizeof(config_line_t));
04830         line->key = tor_strdup("EntryGuardUnlistedSince");
04831         line->value = tor_malloc(ISO_TIME_LEN+1);
04832         format_iso_time(line->value, e->bad_since);
04833         next = &(line->next);
04834       }
04835       if (e->chosen_on_date && e->chosen_by_version &&
04836           !strchr(e->chosen_by_version, ' ')) {
04837         char d[HEX_DIGEST_LEN+1];
04838         char t[ISO_TIME_LEN+1];
04839         *next = line = tor_malloc_zero(sizeof(config_line_t));
04840         line->key = tor_strdup("EntryGuardAddedBy");
04841         base16_encode(d, sizeof(d), e->identity, DIGEST_LEN);
04842         format_iso_time(t, e->chosen_on_date);
04843         tor_asprintf(&line->value, "%s %s %s",
04844                      d, e->chosen_by_version, t);
04845         next = &(line->next);
04846       }
04847       if (e->first_hops) {
04848         *next = line = tor_malloc_zero(sizeof(config_line_t));
04849         line->key = tor_strdup("EntryGuardPathBias");
04850         tor_asprintf(&line->value, "%u %u",
04851                      e->circuit_successes, e->first_hops);
04852         next = &(line->next);
04853       }
04854 
04855     });
04856   if (!get_options()->AvoidDiskWrites)
04857     or_state_mark_dirty(get_or_state(), 0);
04858   entry_guards_dirty = 0;
04859 }
04860 
04867 int
04868 getinfo_helper_entry_guards(control_connection_t *conn,
04869                             const char *question, char **answer,
04870                             const char **errmsg)
04871 {
04872   (void) conn;
04873   (void) errmsg;
04874 
04875   if (!strcmp(question,"entry-guards") ||
04876       !strcmp(question,"helper-nodes")) {
04877     smartlist_t *sl = smartlist_new();
04878     char tbuf[ISO_TIME_LEN+1];
04879     char nbuf[MAX_VERBOSE_NICKNAME_LEN+1];
04880     if (!entry_guards)
04881       entry_guards = smartlist_new();
04882     SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
04883         const char *status = NULL;
04884         time_t when = 0;
04885         const node_t *node;
04886 
04887         if (!e->made_contact) {
04888           status = "never-connected";
04889         } else if (e->bad_since) {
04890           when = e->bad_since;
04891           status = "unusable";
04892         } else {
04893           status = "up";
04894         }
04895 
04896         node = node_get_by_id(e->identity);
04897         if (node) {
04898           node_get_verbose_nickname(node, nbuf);
04899         } else {
04900           nbuf[0] = '$';
04901           base16_encode(nbuf+1, sizeof(nbuf)-1, e->identity, DIGEST_LEN);
04902           /* e->nickname field is not very reliable if we don't know about
04903            * this router any longer; don't include it. */
04904         }
04905 
04906         if (when) {
04907           format_iso_time(tbuf, when);
04908           smartlist_add_asprintf(sl, "%s %s %s\n", nbuf, status, tbuf);
04909         } else {
04910           smartlist_add_asprintf(sl, "%s %s\n", nbuf, status);
04911         }
04912     } SMARTLIST_FOREACH_END(e);
04913     *answer = smartlist_join_strings(sl, "", 0, NULL);
04914     SMARTLIST_FOREACH(sl, char *, c, tor_free(c));
04915     smartlist_free(sl);
04916   }
04917   return 0;
04918 }
04919 
04924 static smartlist_t *bridge_list = NULL;
04925 
04928 void
04929 mark_bridge_list(void)
04930 {
04931   if (!bridge_list)
04932     bridge_list = smartlist_new();
04933   SMARTLIST_FOREACH(bridge_list, bridge_info_t *, b,
04934                     b->marked_for_removal = 1);
04935 }
04936 
04939 void
04940 sweep_bridge_list(void)
04941 {
04942   if (!bridge_list)
04943     bridge_list = smartlist_new();
04944   SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, b) {
04945     if (b->marked_for_removal) {
04946       SMARTLIST_DEL_CURRENT(bridge_list, b);
04947       bridge_free(b);
04948     }
04949   } SMARTLIST_FOREACH_END(b);
04950 }
04951 
04953 static void
04954 clear_bridge_list(void)
04955 {
04956   if (!bridge_list)
04957     bridge_list = smartlist_new();
04958   SMARTLIST_FOREACH(bridge_list, bridge_info_t *, b, bridge_free(b));
04959   smartlist_clear(bridge_list);
04960 }
04961 
04963 static void
04964 bridge_free(bridge_info_t *bridge)
04965 {
04966   if (!bridge)
04967     return;
04968 
04969   tor_free(bridge->transport_name);
04970   tor_free(bridge);
04971 }
04972 
04974 static smartlist_t *transport_list = NULL;
04975 
04978 void
04979 mark_transport_list(void)
04980 {
04981   if (!transport_list)
04982     transport_list = smartlist_new();
04983   SMARTLIST_FOREACH(transport_list, transport_t *, t,
04984                     t->marked_for_removal = 1);
04985 }
04986 
04989 void
04990 sweep_transport_list(void)
04991 {
04992   if (!transport_list)
04993     transport_list = smartlist_new();
04994   SMARTLIST_FOREACH_BEGIN(transport_list, transport_t *, t) {
04995     if (t->marked_for_removal) {
04996       SMARTLIST_DEL_CURRENT(transport_list, t);
04997       transport_free(t);
04998     }
04999   } SMARTLIST_FOREACH_END(t);
05000 }
05001 
05004 void
05005 clear_transport_list(void)
05006 {
05007   if (!transport_list)
05008     transport_list = smartlist_new();
05009   SMARTLIST_FOREACH(transport_list, transport_t *, t, transport_free(t));
05010   smartlist_clear(transport_list);
05011 }
05012 
05014 void
05015 transport_free(transport_t *transport)
05016 {
05017   if (!transport)
05018     return;
05019 
05020   tor_free(transport->name);
05021   tor_free(transport);
05022 }
05023 
05026 transport_t *
05027 transport_get_by_name(const char *name)
05028 {
05029   tor_assert(name);
05030 
05031   if (!transport_list)
05032     return NULL;
05033 
05034   SMARTLIST_FOREACH_BEGIN(transport_list, transport_t *, transport) {
05035     if (!strcmp(transport->name, name))
05036       return transport;
05037   } SMARTLIST_FOREACH_END(transport);
05038 
05039   return NULL;
05040 }
05041 
05045 transport_t *
05046 transport_new(const tor_addr_t *addr, uint16_t port,
05047                  const char *name, int socks_ver)
05048 {
05049   transport_t *t = tor_malloc_zero(sizeof(transport_t));
05050 
05051   tor_addr_copy(&t->addr, addr);
05052   t->port = port;
05053   t->name = tor_strdup(name);
05054   t->socks_version = socks_ver;
05055 
05056   return t;
05057 }
05058 
05064 static int
05065 transport_resolve_conflicts(transport_t *t)
05066 {
05067   /* This is how we resolve transport conflicts:
05068 
05069      If there is already a transport with the same name and addrport,
05070      we either have duplicate torrc lines OR we are here post-HUP and
05071      this transport was here pre-HUP as well. In any case, mark the
05072      old transport so that it doesn't get removed and ignore the new
05073      one. Our caller has to free the new transport so we return '1' to
05074      signify this.
05075 
05076      If there is already a transport with the same name but different
05077      addrport:
05078      * if it's marked for removal, it means that it either has a lower
05079      priority than 't' in torrc (otherwise the mark would have been
05080      cleared by the paragraph above), or it doesn't exist at all in
05081      the post-HUP torrc. We destroy the old transport and register 't'.
05082      * if it's *not* marked for removal, it means that it was newly
05083      added in the post-HUP torrc or that it's of higher priority, in
05084      this case we ignore 't'. */
05085   transport_t *t_tmp = transport_get_by_name(t->name);
05086   if (t_tmp) { /* same name */
05087     if (tor_addr_eq(&t->addr, &t_tmp->addr) && (t->port == t_tmp->port)) {
05088       /* same name *and* addrport */
05089       t_tmp->marked_for_removal = 0;
05090       return 1;
05091     } else { /* same name but different addrport */
05092       if (t_tmp->marked_for_removal) { /* marked for removal */
05093         log_notice(LD_GENERAL, "You tried to add transport '%s' at '%s:%u' "
05094                    "but there was already a transport marked for deletion at "
05095                    "'%s:%u'. We deleted the old transport and registered the "
05096                    "new one.", t->name, fmt_addr(&t->addr), t->port,
05097                    fmt_addr(&t_tmp->addr), t_tmp->port);
05098         smartlist_remove(transport_list, t_tmp);
05099         transport_free(t_tmp);
05100       } else { /* *not* marked for removal */
05101         log_notice(LD_GENERAL, "You tried to add transport '%s' at '%s:%u' "
05102                    "but the same transport already exists at '%s:%u'. "
05103                    "Skipping.", t->name, fmt_addr(&t->addr), t->port,
05104                    fmt_addr(&t_tmp->addr), t_tmp->port);
05105         return -1;
05106       }
05107     }
05108   }
05109 
05110   return 0;
05111 }
05112 
05118 int
05119 transport_add(transport_t *t)
05120 {
05121   int r;
05122   tor_assert(t);
05123 
05124   r = transport_resolve_conflicts(t);
05125 
05126   switch (r) {
05127   case 0: /* should register transport */
05128     if (!transport_list)
05129       transport_list = smartlist_new();
05130     smartlist_add(transport_list, t);
05131     return 0;
05132   default: /* let our caller know the return code */
05133     return r;
05134   }
05135 }
05136 
05140 int
05141 transport_add_from_config(const tor_addr_t *addr, uint16_t port,
05142                           const char *name, int socks_ver)
05143 {
05144   transport_t *t = transport_new(addr, port, name, socks_ver);
05145 
05146   int r = transport_add(t);
05147 
05148   switch (r) {
05149   case -1:
05150   default:
05151     log_notice(LD_GENERAL, "Could not add transport %s at %s:%u. Skipping.",
05152                t->name, fmt_addr(&t->addr), t->port);
05153     transport_free(t);
05154     return -1;
05155   case 1:
05156     log_info(LD_GENERAL, "Succesfully registered transport %s at %s:%u.",
05157              t->name, fmt_addr(&t->addr), t->port);
05158      transport_free(t); /* falling */
05159      return 0;
05160   case 0:
05161     log_info(LD_GENERAL, "Succesfully registered transport %s at %s:%u.",
05162              t->name, fmt_addr(&t->addr), t->port);
05163     return 0;
05164   }
05165 }
05166 
05170 static bridge_info_t *
05171 get_configured_bridge_by_addr_port_digest(const tor_addr_t *addr,
05172                                           uint16_t port,
05173                                           const char *digest)
05174 {
05175   if (!bridge_list)
05176     return NULL;
05177   SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge)
05178     {
05179       if (tor_digest_is_zero(bridge->identity) &&
05180           !tor_addr_compare(&bridge->addr, addr, CMP_EXACT) &&
05181           bridge->port == port)
05182         return bridge;
05183       if (digest && tor_memeq(bridge->identity, digest, DIGEST_LEN))
05184         return bridge;
05185     }
05186   SMARTLIST_FOREACH_END(bridge);
05187   return NULL;
05188 }
05189 
05192 static bridge_info_t *
05193 get_configured_bridge_by_routerinfo(const routerinfo_t *ri)
05194 {
05195   tor_addr_port_t ap;
05196 
05197   router_get_pref_orport(ri, &ap);
05198   return get_configured_bridge_by_addr_port_digest(&ap.addr, ap.port,
05199                                                ri->cache_info.identity_digest);
05200 }
05201 
05203 int
05204 routerinfo_is_a_configured_bridge(const routerinfo_t *ri)
05205 {
05206   return get_configured_bridge_by_routerinfo(ri) ? 1 : 0;
05207 }
05208 
05210 int
05211 node_is_a_configured_bridge(const node_t *node)
05212 {
05213   int retval = 0;               /* Negative.  */
05214   smartlist_t *orports = NULL;
05215 
05216   if (!node)
05217     goto out;
05218 
05219   orports = node_get_all_orports(node);
05220   if (orports == NULL)
05221     goto out;
05222 
05223   SMARTLIST_FOREACH_BEGIN(orports, tor_addr_port_t *, orport) {
05224     if (get_configured_bridge_by_addr_port_digest(&orport->addr, orport->port,
05225                                                   node->identity) != NULL) {
05226       retval = 1;
05227       goto out;
05228     }
05229   } SMARTLIST_FOREACH_END(orport);
05230 
05231  out:
05232   if (orports != NULL) {
05233     SMARTLIST_FOREACH(orports, tor_addr_port_t *, p, tor_free(p));
05234     smartlist_free(orports);
05235     orports = NULL;
05236   }
05237   return retval;
05238 }
05239 
05244 void
05245 learned_router_identity(const tor_addr_t *addr, uint16_t port,
05246                         const char *digest)
05247 {
05248   bridge_info_t *bridge =
05249     get_configured_bridge_by_addr_port_digest(addr, port, digest);
05250   if (bridge && tor_digest_is_zero(bridge->identity)) {
05251     memcpy(bridge->identity, digest, DIGEST_LEN);
05252     log_notice(LD_DIR, "Learned fingerprint %s for bridge %s:%d",
05253                hex_str(digest, DIGEST_LEN), fmt_addr(addr), port);
05254   }
05255 }
05256 
05260 static int
05261 bridge_has_digest(const bridge_info_t *bridge, const char *digest)
05262 {
05263   if (digest)
05264     return tor_memeq(digest, bridge->identity, DIGEST_LEN);
05265   else
05266     return tor_digest_is_zero(bridge->identity);
05267 }
05268 
05274 static void
05275 bridge_resolve_conflicts(const tor_addr_t *addr, uint16_t port,
05276                          const char *digest, const char *transport_name)
05277 {
05278   /* Iterate the already-registered bridge list:
05279 
05280      If you find a bridge with the same adress and port, mark it for
05281      removal. It doesn't make sense to have two active bridges with
05282      the same IP:PORT. If the bridge in question has a different
05283      digest or transport than <b>digest</b>/<b>transport_name</b>,
05284      it's probably a misconfiguration and we should warn the user.
05285   */
05286   SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge) {
05287     if (bridge->marked_for_removal)
05288       continue;
05289 
05290     if (tor_addr_eq(&bridge->addr, addr) && (bridge->port == port)) {
05291 
05292       bridge->marked_for_removal = 1;
05293 
05294       if (!bridge_has_digest(bridge, digest) ||
05295           strcmp_opt(bridge->transport_name, transport_name)) {
05296         /* warn the user */
05297         char *bridge_description_new, *bridge_description_old;
05298         tor_asprintf(&bridge_description_new, "%s:%u:%s:%s",
05299                      fmt_addr(addr), port,
05300                      digest ? hex_str(digest, DIGEST_LEN) : "",
05301                      transport_name ? transport_name : "");
05302         tor_asprintf(&bridge_description_old, "%s:%u:%s:%s",
05303                      fmt_addr(&bridge->addr), bridge->port,
05304                      tor_digest_is_zero(bridge->identity) ?
05305                      "" : hex_str(bridge->identity,DIGEST_LEN),
05306                      bridge->transport_name ? bridge->transport_name : "");
05307 
05308         log_warn(LD_GENERAL,"Tried to add bridge '%s', but we found a conflict"
05309                  " with the already registered bridge '%s'. We will discard"
05310                  " the old bridge and keep '%s'. If this is not what you"
05311                  " wanted, please change your configuration file accordingly.",
05312                  bridge_description_new, bridge_description_old,
05313                  bridge_description_new);
05314 
05315         tor_free(bridge_description_new);
05316         tor_free(bridge_description_old);
05317       }
05318     }
05319   } SMARTLIST_FOREACH_END(bridge);
05320 }
05321 
05327 void
05328 bridge_add_from_config(const tor_addr_t *addr, uint16_t port,
05329                        const char *digest, const char *transport_name)
05330 {
05331   bridge_info_t *b;
05332 
05333   bridge_resolve_conflicts(addr, port, digest, transport_name);
05334 
05335   b = tor_malloc_zero(sizeof(bridge_info_t));
05336   tor_addr_copy(&b->addr, addr);
05337   b->port = port;
05338   if (digest)
05339     memcpy(b->identity, digest, DIGEST_LEN);
05340   if (transport_name)
05341     b->transport_name = tor_strdup(transport_name);
05342   b->fetch_status.schedule = DL_SCHED_BRIDGE;
05343   if (!bridge_list)
05344     bridge_list = smartlist_new();
05345 
05346   smartlist_add(bridge_list, b);
05347 }
05348 
05350 static int
05351 routerset_contains_bridge(const routerset_t *routerset,
05352                           const bridge_info_t *bridge)
05353 {
05354   int result;
05355   extend_info_t *extinfo;
05356   tor_assert(bridge);
05357   if (!routerset)
05358     return 0;
05359 
05360   extinfo = extend_info_alloc(
05361          NULL, bridge->identity, NULL, &bridge->addr, bridge->port);
05362   result = routerset_contains_extendinfo(routerset, extinfo);
05363   extend_info_free(extinfo);
05364   return result;
05365 }
05366 
05368 static bridge_info_t *
05369 find_bridge_by_digest(const char *digest)
05370 {
05371   SMARTLIST_FOREACH(bridge_list, bridge_info_t *, bridge,
05372     {
05373       if (tor_memeq(bridge->identity, digest, DIGEST_LEN))
05374         return bridge;
05375     });
05376   return NULL;
05377 }
05378 
05379 /* DOCDOC find_transport_name_by_bridge_addrport */
05380 const char *
05381 find_transport_name_by_bridge_addrport(const tor_addr_t *addr, uint16_t port)
05382 {
05383   if (!bridge_list)
05384     return NULL;
05385 
05386   SMARTLIST_FOREACH_BEGIN(bridge_list, const bridge_info_t *, bridge) {
05387     if (tor_addr_eq(&bridge->addr, addr) &&
05388         (bridge->port == port))
05389       return bridge->transport_name;
05390   } SMARTLIST_FOREACH_END(bridge);
05391 
05392   return NULL;
05393 }
05394 
05403 int
05404 find_transport_by_bridge_addrport(const tor_addr_t *addr, uint16_t port,
05405                                   const transport_t **transport)
05406 {
05407   *transport = NULL;
05408   if (!bridge_list)
05409     return 0;
05410 
05411   SMARTLIST_FOREACH_BEGIN(bridge_list, const bridge_info_t *, bridge) {
05412     if (tor_addr_eq(&bridge->addr, addr) &&
05413         (bridge->port == port)) { /* bridge matched */
05414       if (bridge->transport_name) { /* it also uses pluggable transports */
05415         *transport = transport_get_by_name(bridge->transport_name);
05416         if (*transport == NULL) { /* it uses pluggable transports, but
05417                                      the transport could not be found! */
05418           return -1;
05419         }
05420         return 0;
05421       } else { /* bridge matched, but it doesn't use transports. */
05422         break;
05423       }
05424     }
05425   } SMARTLIST_FOREACH_END(bridge);
05426 
05427   *transport = NULL;
05428   return 0;
05429 }
05430 
05432 static void
05433 launch_direct_bridge_descriptor_fetch(bridge_info_t *bridge)
05434 {
05435   char *address;
05436   const or_options_t *options = get_options();
05437 
05438   if (connection_get_by_type_addr_port_purpose(
05439       CONN_TYPE_DIR, &bridge->addr, bridge->port,
05440       DIR_PURPOSE_FETCH_SERVERDESC))
05441     return; /* it's already on the way */
05442 
05443   if (routerset_contains_bridge(options->ExcludeNodes, bridge)) {
05444     download_status_mark_impossible(&bridge->fetch_status);
05445     log_warn(LD_APP, "Not using bridge at %s: it is in ExcludeNodes.",
05446              safe_str_client(fmt_addr(&bridge->addr)));
05447     return;
05448   }
05449 
05450   address = tor_dup_addr(&bridge->addr);
05451 
05452   directory_initiate_command(address, &bridge->addr,
05453                              bridge->port, 0,
05454                              0, /* does not matter */
05455                              1, bridge->identity,
05456                              DIR_PURPOSE_FETCH_SERVERDESC,
05457                              ROUTER_PURPOSE_BRIDGE,
05458                              0, "authority.z", NULL, 0, 0);
05459   tor_free(address);
05460 }
05461 
05464 void
05465 retry_bridge_descriptor_fetch_directly(const char *digest)
05466 {
05467   bridge_info_t *bridge = find_bridge_by_digest(digest);
05468   if (!bridge)
05469     return; /* not found? oh well. */
05470 
05471   launch_direct_bridge_descriptor_fetch(bridge);
05472 }
05473 
05477 void
05478 fetch_bridge_descriptors(const or_options_t *options, time_t now)
05479 {
05480   int num_bridge_auths = get_n_authorities(BRIDGE_DIRINFO);
05481   int ask_bridge_directly;
05482   int can_use_bridge_authority;
05483 
05484   if (!bridge_list)
05485     return;
05486 
05487   /* If we still have unconfigured managed proxies, don't go and
05488      connect to a bridge. */
05489   if (pt_proxies_configuration_pending())
05490     return;
05491 
05492   SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge)
05493     {
05494       if (!download_status_is_ready(&bridge->fetch_status, now,
05495                                     IMPOSSIBLE_TO_DOWNLOAD))
05496         continue; /* don't bother, no need to retry yet */
05497       if (routerset_contains_bridge(options->ExcludeNodes, bridge)) {
05498         download_status_mark_impossible(&bridge->fetch_status);
05499         log_warn(LD_APP, "Not using bridge at %s: it is in ExcludeNodes.",
05500                  safe_str_client(fmt_addr(&bridge->addr)));
05501         continue;
05502       }
05503 
05504       /* schedule another fetch as if this one will fail, in case it does */
05505       download_status_failed(&bridge->fetch_status, 0);
05506 
05507       can_use_bridge_authority = !tor_digest_is_zero(bridge->identity) &&
05508                                  num_bridge_auths;
05509       ask_bridge_directly = !can_use_bridge_authority ||
05510                             !options->UpdateBridgesFromAuthority;
05511       log_debug(LD_DIR, "ask_bridge_directly=%d (%d, %d, %d)",
05512                 ask_bridge_directly, tor_digest_is_zero(bridge->identity),
05513                 !options->UpdateBridgesFromAuthority, !num_bridge_auths);
05514 
05515       if (ask_bridge_directly &&
05516           !fascist_firewall_allows_address_or(&bridge->addr, bridge->port)) {
05517         log_notice(LD_DIR, "Bridge at '%s:%d' isn't reachable by our "
05518                    "firewall policy. %s.", fmt_addr(&bridge->addr),
05519                    bridge->port,
05520                    can_use_bridge_authority ?
05521                      "Asking bridge authority instead" : "Skipping");
05522         if (can_use_bridge_authority)
05523           ask_bridge_directly = 0;
05524         else
05525           continue;
05526       }
05527 
05528       if (ask_bridge_directly) {
05529         /* we need to ask the bridge itself for its descriptor. */
05530         launch_direct_bridge_descriptor_fetch(bridge);
05531       } else {
05532         /* We have a digest and we want to ask an authority. We could
05533          * combine all the requests into one, but that may give more
05534          * hints to the bridge authority than we want to give. */
05535         char resource[10 + HEX_DIGEST_LEN];
05536         memcpy(resource, "fp/", 3);
05537         base16_encode(resource+3, HEX_DIGEST_LEN+1,
05538                       bridge->identity, DIGEST_LEN);
05539         memcpy(resource+3+HEX_DIGEST_LEN, ".z", 3);
05540         log_info(LD_DIR, "Fetching bridge info '%s' from bridge authority.",
05541                  resource);
05542         directory_get_from_dirserver(DIR_PURPOSE_FETCH_SERVERDESC,
05543                 ROUTER_PURPOSE_BRIDGE, resource, 0);
05544       }
05545     }
05546   SMARTLIST_FOREACH_END(bridge);
05547 }
05548 
05554 static void
05555 rewrite_node_address_for_bridge(const bridge_info_t *bridge, node_t *node)
05556 {
05557   /* XXXX move this function. */
05558   /* XXXX overridden addresses should really live in the node_t, so that the
05559    *   routerinfo_t and the microdesc_t can be immutable.  But we can only
05560    *   do that safely if we know that no function that connects to an OR
05561    *   does so through an address from any source other than node_get_addr().
05562    */
05563   tor_addr_t addr;
05564 
05565   if (node->ri) {
05566     routerinfo_t *ri = node->ri;
05567     tor_addr_from_ipv4h(&addr, ri->addr);
05568 
05569     if ((!tor_addr_compare(&bridge->addr, &addr, CMP_EXACT) &&
05570          bridge->port == ri->or_port) ||
05571         (!tor_addr_compare(&bridge->addr, &ri->ipv6_addr, CMP_EXACT) &&
05572          bridge->port == ri->ipv6_orport)) {
05573       /* they match, so no need to do anything */
05574     } else {
05575       if (tor_addr_family(&bridge->addr) == AF_INET) {
05576         ri->addr = tor_addr_to_ipv4h(&bridge->addr);
05577         tor_free(ri->address);
05578         ri->address = tor_dup_ip(ri->addr);
05579         ri->or_port = bridge->port;
05580         log_info(LD_DIR,
05581                  "Adjusted bridge routerinfo for '%s' to match configured "
05582                  "address %s:%d.",
05583                  ri->nickname, ri->address, ri->or_port);
05584       } else if (tor_addr_family(&bridge->addr) == AF_INET6) {
05585         tor_addr_copy(&ri->ipv6_addr, &bridge->addr);
05586         ri->ipv6_orport = bridge->port;
05587         log_info(LD_DIR,
05588                  "Adjusted bridge routerinfo for '%s' to match configured "
05589                  "address %s:%d.",
05590                  ri->nickname, fmt_addr(&ri->ipv6_addr), ri->ipv6_orport);
05591       } else {
05592         log_err(LD_BUG, "Address family not supported: %d.",
05593                 tor_addr_family(&bridge->addr));
05594         return;
05595       }
05596     }
05597 
05598     /* Indicate that we prefer connecting to this bridge over the
05599        protocol that the bridge address indicates.  Last bridge
05600        descriptor handled wins.  */
05601     ri->ipv6_preferred = tor_addr_family(&bridge->addr) == AF_INET6;
05602 
05603     /* XXXipv6 we lack support for falling back to another address for
05604        the same relay, warn the user */
05605     if (!tor_addr_is_null(&ri->ipv6_addr)) {
05606       tor_addr_port_t ap;
05607       router_get_pref_orport(ri, &ap);
05608       log_notice(LD_CONFIG,
05609                  "Bridge '%s' has both an IPv4 and an IPv6 address.  "
05610                  "Will prefer using its %s address (%s:%d).",
05611                  ri->nickname,
05612                  ri->ipv6_preferred ? "IPv6" : "IPv4",
05613                  fmt_addr(&ap.addr), ap.port);
05614     }
05615   }
05616   if (node->rs) {
05617     routerstatus_t *rs = node->rs;
05618     tor_addr_from_ipv4h(&addr, rs->addr);
05619 
05620     if (!tor_addr_compare(&bridge->addr, &addr, CMP_EXACT) &&
05621         bridge->port == rs->or_port) {
05622       /* they match, so no need to do anything */
05623     } else {
05624       rs->addr = tor_addr_to_ipv4h(&bridge->addr);
05625       rs->or_port = bridge->port;
05626       log_info(LD_DIR,
05627                "Adjusted bridge routerstatus for '%s' to match "
05628                "configured address %s:%d.",
05629                rs->nickname, fmt_addr(&bridge->addr), rs->or_port);
05630     }
05631   }
05632 }
05633 
05636 void
05637 learned_bridge_descriptor(routerinfo_t *ri, int from_cache)
05638 {
05639   tor_assert(ri);
05640   tor_assert(ri->purpose == ROUTER_PURPOSE_BRIDGE);
05641   if (get_options()->UseBridges) {
05642     int first = !any_bridge_descriptors_known();
05643     bridge_info_t *bridge = get_configured_bridge_by_routerinfo(ri);
05644     time_t now = time(NULL);
05645     router_set_status(ri->cache_info.identity_digest, 1);
05646 
05647     if (bridge) { /* if we actually want to use this one */
05648       node_t *node;
05649       /* it's here; schedule its re-fetch for a long time from now. */
05650       if (!from_cache)
05651         download_status_reset(&bridge->fetch_status);
05652 
05653       node = node_get_mutable_by_id(ri->cache_info.identity_digest);
05654       tor_assert(node);
05655       rewrite_node_address_for_bridge(bridge, node);
05656       add_an_entry_guard(node, 1, 1);
05657 
05658       log_notice(LD_DIR, "new bridge descriptor '%s' (%s): %s", ri->nickname,
05659                  from_cache ? "cached" : "fresh", router_describe(ri));
05660       /* set entry->made_contact so if it goes down we don't drop it from
05661        * our entry node list */
05662       entry_guard_register_connect_status(ri->cache_info.identity_digest,
05663                                           1, 0, now);
05664       if (first)
05665         routerlist_retry_directory_downloads(now);
05666     }
05667   }
05668 }
05669 
05676 int
05677 any_bridge_descriptors_known(void)
05678 {
05679   tor_assert(get_options()->UseBridges);
05680   return choose_random_entry(NULL)!=NULL ? 1 : 0;
05681 }
05682 
05686 int
05687 any_pending_bridge_descriptor_fetches(void)
05688 {
05689   smartlist_t *conns = get_connection_array();
05690   SMARTLIST_FOREACH(conns, connection_t *, conn,
05691   {
05692     if (conn->type == CONN_TYPE_DIR &&
05693         conn->purpose == DIR_PURPOSE_FETCH_SERVERDESC &&
05694         TO_DIR_CONN(conn)->router_purpose == ROUTER_PURPOSE_BRIDGE &&
05695         !conn->marked_for_close &&
05696         conn->linked &&
05697         conn->linked_conn && !conn->linked_conn->marked_for_close) {
05698       log_debug(LD_DIR, "found one: %s", conn->address);
05699       return 1;
05700     }
05701   });
05702   return 0;
05703 }
05704 
05709 static int
05710 entries_retry_helper(const or_options_t *options, int act)
05711 {
05712   const node_t *node;
05713   int any_known = 0;
05714   int any_running = 0;
05715   int need_bridges = options->UseBridges != 0;
05716   if (!entry_guards)
05717     entry_guards = smartlist_new();
05718   SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
05719       node = node_get_by_id(e->identity);
05720       if (node && node_has_descriptor(node) &&
05721           node_is_bridge(node) == need_bridges) {
05722         any_known = 1;
05723         if (node->is_running)
05724           any_running = 1; /* some entry is both known and running */
05725         else if (act) {
05726           /* Mark all current connections to this OR as unhealthy, since
05727            * otherwise there could be one that started 30 seconds
05728            * ago, and in 30 seconds it will time out, causing us to mark
05729            * the node down and undermine the retry attempt. We mark even
05730            * the established conns, since if the network just came back
05731            * we'll want to attach circuits to fresh conns. */
05732           connection_or_set_bad_connections(node->identity, 1);
05733 
05734           /* mark this entry node for retry */
05735           router_set_status(node->identity, 1);
05736           e->can_retry = 1;
05737           e->bad_since = 0;
05738         }
05739       }
05740   } SMARTLIST_FOREACH_END(e);
05741   log_debug(LD_DIR, "%d: any_known %d, any_running %d",
05742             act, any_known, any_running);
05743   return any_known && !any_running;
05744 }
05745 
05748 int
05749 entries_known_but_down(const or_options_t *options)
05750 {
05751   tor_assert(entry_list_is_constrained(options));
05752   return entries_retry_helper(options, 0);
05753 }
05754 
05756 void
05757 entries_retry_all(const or_options_t *options)
05758 {
05759   tor_assert(entry_list_is_constrained(options));
05760   entries_retry_helper(options, 1);
05761 }
05762 
05767 int
05768 any_bridges_dont_support_microdescriptors(void)
05769 {
05770   const node_t *node;
05771   static int ever_answered_yes = 0;
05772   if (!get_options()->UseBridges || !entry_guards)
05773     return 0;
05774   if (ever_answered_yes)
05775     return 1; /* if we ever answer 'yes', always answer 'yes' */
05776   SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
05777     node = node_get_by_id(e->identity);
05778     if (node && node->ri &&
05779         node_is_bridge(node) && node_is_a_configured_bridge(node) &&
05780         !tor_version_supports_microdescriptors(node->ri->platform)) {
05781       /* This is one of our current bridges, and we know enough about
05782        * it to know that it won't be able to answer our microdescriptor
05783        * questions. */
05784       ever_answered_yes = 1;
05785       return 1;
05786     }
05787   } SMARTLIST_FOREACH_END(e);
05788   return 0;
05789 }
05790 
05793 void
05794 entry_guards_free_all(void)
05795 {
05796   if (entry_guards) {
05797     SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
05798                       entry_guard_free(e));
05799     smartlist_free(entry_guards);
05800     entry_guards = NULL;
05801   }
05802   clear_bridge_list();
05803   clear_transport_list();
05804   smartlist_free(bridge_list);
05805   smartlist_free(transport_list);
05806   bridge_list = NULL;
05807   transport_list = NULL;
05808 }
05809