circuitbuild.c
上传用户:awang829
上传日期:2019-07-14
资源大小:2356k
文件大小:110k
源码类别:

网络

开发平台:

Unix_Linux

  1. /* Copyright (c) 2001 Matej Pfajfar.
  2.  * Copyright (c) 2001-2004, Roger Dingledine.
  3.  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  4.  * Copyright (c) 2007-2009, The Tor Project, Inc. */
  5. /* See LICENSE for licensing information */
  6. /**
  7.  * file circuitbuild.c
  8.  * brief The actual details of building circuits.
  9.  **/
  10. #include "or.h"
  11. /********* START VARIABLES **********/
  12. /** A global list of all circuits at this hop. */
  13. extern circuit_t *global_circuitlist;
  14. /** An entry_guard_t represents our information about a chosen long-term
  15.  * first hop, known as a "helper" node in the literature. We can't just
  16.  * use a routerinfo_t, since we want to remember these even when we
  17.  * don't have a directory. */
  18. typedef struct {
  19.   char nickname[MAX_NICKNAME_LEN+1];
  20.   char identity[DIGEST_LEN];
  21.   time_t chosen_on_date; /**< Approximately when was this guard added?
  22.                           * "0" if we don't know. */
  23.   char *chosen_by_version; /**< What tor version added this guard? NULL
  24.                             * if we don't know. */
  25.   unsigned int made_contact : 1; /**< 0 if we have never connected to this
  26.                                   * router, 1 if we have. */
  27.   unsigned int can_retry : 1; /**< Should we retry connecting to this entry,
  28.                                * in spite of having it marked as unreachable?*/
  29.   time_t bad_since; /**< 0 if this guard is currently usable, or the time at
  30.                       * which it was observed to become (according to the
  31.                       * directory or the user configuration) unusable. */
  32.   time_t unreachable_since; /**< 0 if we can connect to this guard, or the
  33.                              * time at which we first noticed we couldn't
  34.                              * connect to it. */
  35.   time_t last_attempted; /**< 0 if we can connect to this guard, or the time
  36.                           * at which we last failed to connect to it. */
  37. } entry_guard_t;
  38. /** A list of our chosen entry guards. */
  39. static smartlist_t *entry_guards = NULL;
  40. /** A value of 1 means that the entry_guards list has changed
  41.  * and those changes need to be flushed to disk. */
  42. static int entry_guards_dirty = 0;
  43. /********* END VARIABLES ************/
  44. static int circuit_deliver_create_cell(circuit_t *circ,
  45.                                        uint8_t cell_type, const char *payload);
  46. static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit);
  47. static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
  48. static int onion_extend_cpath(origin_circuit_t *circ);
  49. static int count_acceptable_routers(smartlist_t *routers);
  50. static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
  51. static void entry_guards_changed(void);
  52. static time_t start_of_month(time_t when);
  53. /** Iterate over values of circ_id, starting from conn->next_circ_id,
  54.  * and with the high bit specified by conn->circ_id_type, until we get
  55.  * a circ_id that is not in use by any other circuit on that conn.
  56.  *
  57.  * Return it, or 0 if can't get a unique circ_id.
  58.  */
  59. static circid_t
  60. get_unique_circ_id_by_conn(or_connection_t *conn)
  61. {
  62.   circid_t test_circ_id;
  63.   circid_t attempts=0;
  64.   circid_t high_bit;
  65.   tor_assert(conn);
  66.   if (conn->circ_id_type == CIRC_ID_TYPE_NEITHER) {
  67.     log_warn(LD_BUG, "Trying to pick a circuit ID for a connection from "
  68.              "a client with no identity.");
  69.     return 0;
  70.   }
  71.   high_bit = (conn->circ_id_type == CIRC_ID_TYPE_HIGHER) ? 1<<15 : 0;
  72.   do {
  73.     /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
  74.      * circID such that (high_bit|test_circ_id) is not already used. */
  75.     test_circ_id = conn->next_circ_id++;
  76.     if (test_circ_id == 0 || test_circ_id >= 1<<15) {
  77.       test_circ_id = 1;
  78.       conn->next_circ_id = 2;
  79.     }
  80.     if (++attempts > 1<<15) {
  81.       /* Make sure we don't loop forever if all circ_id's are used. This
  82.        * matters because it's an external DoS opportunity.
  83.        */
  84.       log_warn(LD_CIRC,"No unused circ IDs. Failing.");
  85.       return 0;
  86.     }
  87.     test_circ_id |= high_bit;
  88.   } while (circuit_id_in_use_on_orconn(test_circ_id, conn));
  89.   return test_circ_id;
  90. }
  91. /** If <b>verbose</b> is false, allocate and return a comma-separated list of
  92.  * the currently built elements of circuit_t.  If <b>verbose</b> is true, also
  93.  * list information about link status in a more verbose format using spaces.
  94.  * If <b>verbose_names</b> is false, give nicknames for Named routers and hex
  95.  * digests for others; if <b>verbose_names</b> is true, use $DIGEST=Name style
  96.  * names.
  97.  */
  98. static char *
  99. circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
  100. {
  101.   crypt_path_t *hop;
  102.   smartlist_t *elements;
  103.   const char *states[] = {"closed", "waiting for keys", "open"};
  104.   char buf[128];
  105.   char *s;
  106.   elements = smartlist_create();
  107.   if (verbose) {
  108.     const char *nickname = build_state_get_exit_nickname(circ->build_state);
  109.     tor_snprintf(buf, sizeof(buf), "%s%s circ (length %d%s%s):",
  110.                  circ->build_state->is_internal ? "internal" : "exit",
  111.                  circ->build_state->need_uptime ? " (high-uptime)" : "",
  112.                  circ->build_state->desired_path_len,
  113.                  circ->_base.state == CIRCUIT_STATE_OPEN ? "" : ", exit ",
  114.                  circ->_base.state == CIRCUIT_STATE_OPEN ? "" :
  115.                  (nickname?nickname:"*unnamed*"));
  116.     smartlist_add(elements, tor_strdup(buf));
  117.   }
  118.   hop = circ->cpath;
  119.   do {
  120.     routerinfo_t *ri;
  121.     routerstatus_t *rs;
  122.     char *elt;
  123.     const char *id;
  124.     if (!hop)
  125.       break;
  126.     id = hop->extend_info->identity_digest;
  127.     if (!verbose && hop->state != CPATH_STATE_OPEN)
  128.       break;
  129.     if (!hop->extend_info)
  130.       break;
  131.     if (verbose_names) {
  132.       elt = tor_malloc(MAX_VERBOSE_NICKNAME_LEN+1);
  133.       if ((ri = router_get_by_digest(id))) {
  134.         router_get_verbose_nickname(elt, ri);
  135.       } else if ((rs = router_get_consensus_status_by_id(id))) {
  136.         routerstatus_get_verbose_nickname(elt, rs);
  137.       } else if (hop->extend_info->nickname &&
  138.                  is_legal_nickname(hop->extend_info->nickname)) {
  139.         elt[0] = '$';
  140.         base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  141.         elt[HEX_DIGEST_LEN+1]= '~';
  142.         strlcpy(elt+HEX_DIGEST_LEN+2,
  143.                 hop->extend_info->nickname, MAX_NICKNAME_LEN+1);
  144.       } else {
  145.         elt[0] = '$';
  146.         base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  147.       }
  148.     } else { /* ! verbose_names */
  149.       if ((ri = router_get_by_digest(id)) &&
  150.           ri->is_named) {
  151.         elt = tor_strdup(hop->extend_info->nickname);
  152.       } else {
  153.         elt = tor_malloc(HEX_DIGEST_LEN+2);
  154.         elt[0] = '$';
  155.         base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  156.       }
  157.     }
  158.     tor_assert(elt);
  159.     if (verbose) {
  160.       size_t len = strlen(elt)+2+strlen(states[hop->state])+1;
  161.       char *v = tor_malloc(len);
  162.       tor_assert(hop->state <= 2);
  163.       tor_snprintf(v,len,"%s(%s)",elt,states[hop->state]);
  164.       smartlist_add(elements, v);
  165.       tor_free(elt);
  166.     } else {
  167.       smartlist_add(elements, elt);
  168.     }
  169.     hop = hop->next;
  170.   } while (hop != circ->cpath);
  171.   s = smartlist_join_strings(elements, verbose?" ":",", 0, NULL);
  172.   SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
  173.   smartlist_free(elements);
  174.   return s;
  175. }
  176. /** If <b>verbose</b> is false, allocate and return a comma-separated
  177.  * list of the currently built elements of circuit_t.  If
  178.  * <b>verbose</b> is true, also list information about link status in
  179.  * a more verbose format using spaces.
  180.  */
  181. char *
  182. circuit_list_path(origin_circuit_t *circ, int verbose)
  183. {
  184.   return circuit_list_path_impl(circ, verbose, 0);
  185. }
  186. /** Allocate and return a comma-separated list of the currently built elements
  187.  * of circuit_t, giving each as a verbose nickname.
  188.  */
  189. char *
  190. circuit_list_path_for_controller(origin_circuit_t *circ)
  191. {
  192.   return circuit_list_path_impl(circ, 0, 1);
  193. }
  194. /** Log, at severity <b>severity</b>, the nicknames of each router in
  195.  * circ's cpath. Also log the length of the cpath, and the intended
  196.  * exit point.
  197.  */
  198. void
  199. circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ)
  200. {
  201.   char *s = circuit_list_path(circ,1);
  202.   log(severity,domain,"%s",s);
  203.   tor_free(s);
  204. }
  205. /** Tell the rep(utation)hist(ory) module about the status of the links
  206.  * in circ.  Hops that have become OPEN are marked as successfully
  207.  * extended; the _first_ hop that isn't open (if any) is marked as
  208.  * unable to extend.
  209.  */
  210. /* XXXX Someday we should learn from OR circuits too. */
  211. void
  212. circuit_rep_hist_note_result(origin_circuit_t *circ)
  213. {
  214.   crypt_path_t *hop;
  215.   char *prev_digest = NULL;
  216.   routerinfo_t *router;
  217.   hop = circ->cpath;
  218.   if (!hop) /* circuit hasn't started building yet. */
  219.     return;
  220.   if (server_mode(get_options())) {
  221.     routerinfo_t *me = router_get_my_routerinfo();
  222.     if (!me)
  223.       return;
  224.     prev_digest = me->cache_info.identity_digest;
  225.   }
  226.   do {
  227.     router = router_get_by_digest(hop->extend_info->identity_digest);
  228.     if (router) {
  229.       if (prev_digest) {
  230.         if (hop->state == CPATH_STATE_OPEN)
  231.           rep_hist_note_extend_succeeded(prev_digest,
  232.                                          router->cache_info.identity_digest);
  233.         else {
  234.           rep_hist_note_extend_failed(prev_digest,
  235.                                       router->cache_info.identity_digest);
  236.           break;
  237.         }
  238.       }
  239.       prev_digest = router->cache_info.identity_digest;
  240.     } else {
  241.       prev_digest = NULL;
  242.     }
  243.     hop=hop->next;
  244.   } while (hop!=circ->cpath);
  245. }
  246. /** Pick all the entries in our cpath. Stop and return 0 when we're
  247.  * happy, or return -1 if an error occurs. */
  248. static int
  249. onion_populate_cpath(origin_circuit_t *circ)
  250. {
  251.   int r;
  252. again:
  253.   r = onion_extend_cpath(circ);
  254.   if (r < 0) {
  255.     log_info(LD_CIRC,"Generating cpath hop failed.");
  256.     return -1;
  257.   }
  258.   if (r == 0)
  259.     goto again;
  260.   return 0; /* if r == 1 */
  261. }
  262. /** Create and return a new origin circuit. Initialize its purpose and
  263.  * build-state based on our arguments.  The <b>flags</b> argument is a
  264.  * bitfield of CIRCLAUNCH_* flags. */
  265. origin_circuit_t *
  266. origin_circuit_init(uint8_t purpose, int flags)
  267. {
  268.   /* sets circ->p_circ_id and circ->p_conn */
  269.   origin_circuit_t *circ = origin_circuit_new();
  270.   circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OR_WAIT);
  271.   circ->build_state = tor_malloc_zero(sizeof(cpath_build_state_t));
  272.   circ->build_state->onehop_tunnel =
  273.     ((flags & CIRCLAUNCH_ONEHOP_TUNNEL) ? 1 : 0);
  274.   circ->build_state->need_uptime =
  275.     ((flags & CIRCLAUNCH_NEED_UPTIME) ? 1 : 0);
  276.   circ->build_state->need_capacity =
  277.     ((flags & CIRCLAUNCH_NEED_CAPACITY) ? 1 : 0);
  278.   circ->build_state->is_internal =
  279.     ((flags & CIRCLAUNCH_IS_INTERNAL) ? 1 : 0);
  280.   circ->_base.purpose = purpose;
  281.   return circ;
  282. }
  283. /** Build a new circuit for <b>purpose</b>. If <b>exit</b>
  284.  * is defined, then use that as your exit router, else choose a suitable
  285.  * exit node.
  286.  *
  287.  * Also launch a connection to the first OR in the chosen path, if
  288.  * it's not open already.
  289.  */
  290. origin_circuit_t *
  291. circuit_establish_circuit(uint8_t purpose, extend_info_t *exit, int flags)
  292. {
  293.   origin_circuit_t *circ;
  294.   int err_reason = 0;
  295.   circ = origin_circuit_init(purpose, flags);
  296.   if (onion_pick_cpath_exit(circ, exit) < 0 ||
  297.       onion_populate_cpath(circ) < 0) {
  298.     circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_NOPATH);
  299.     return NULL;
  300.   }
  301.   control_event_circuit_status(circ, CIRC_EVENT_LAUNCHED, 0);
  302.   if ((err_reason = circuit_handle_first_hop(circ)) < 0) {
  303.     circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
  304.     return NULL;
  305.   }
  306.   return circ;
  307. }
  308. /** Start establishing the first hop of our circuit. Figure out what
  309.  * OR we should connect to, and if necessary start the connection to
  310.  * it. If we're already connected, then send the 'create' cell.
  311.  * Return 0 for ok, -reason if circ should be marked-for-close. */
  312. int
  313. circuit_handle_first_hop(origin_circuit_t *circ)
  314. {
  315.   crypt_path_t *firsthop;
  316.   or_connection_t *n_conn;
  317.   int err_reason = 0;
  318.   const char *msg = NULL;
  319.   int should_launch = 0;
  320.   firsthop = onion_next_hop_in_cpath(circ->cpath);
  321.   tor_assert(firsthop);
  322.   tor_assert(firsthop->extend_info);
  323.   /* now see if we're already connected to the first OR in 'route' */
  324.   log_debug(LD_CIRC,"Looking for firsthop '%s:%u'",
  325.             fmt_addr(&firsthop->extend_info->addr),
  326.             firsthop->extend_info->port);
  327.   n_conn = connection_or_get_for_extend(firsthop->extend_info->identity_digest,
  328.                                         &firsthop->extend_info->addr,
  329.                                         &msg,
  330.                                         &should_launch);
  331.   if (!n_conn) {
  332.     /* not currently connected in a useful way. */
  333.     const char *name = firsthop->extend_info->nickname ?
  334.       firsthop->extend_info->nickname : fmt_addr(&firsthop->extend_info->addr);
  335.     log_info(LD_CIRC, "Next router is %s: %s ", safe_str(name), msg?msg:"???");
  336.     circ->_base.n_hop = extend_info_dup(firsthop->extend_info);
  337.     if (should_launch) {
  338.       if (circ->build_state->onehop_tunnel)
  339.         control_event_bootstrap(BOOTSTRAP_STATUS_CONN_DIR, 0);
  340.       n_conn = connection_or_connect(&firsthop->extend_info->addr,
  341.                                      firsthop->extend_info->port,
  342.                                      firsthop->extend_info->identity_digest);
  343.       if (!n_conn) { /* connect failed, forget the whole thing */
  344.         log_info(LD_CIRC,"connect to firsthop failed. Closing.");
  345.         return -END_CIRC_REASON_CONNECTFAILED;
  346.       }
  347.     }
  348.     log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
  349.     /* return success. The onion/circuit/etc will be taken care of
  350.      * automatically (may already have been) whenever n_conn reaches
  351.      * OR_CONN_STATE_OPEN.
  352.      */
  353.     return 0;
  354.   } else { /* it's already open. use it. */
  355.     tor_assert(!circ->_base.n_hop);
  356.     circ->_base.n_conn = n_conn;
  357.     log_debug(LD_CIRC,"Conn open. Delivering first onion skin.");
  358.     if ((err_reason = circuit_send_next_onion_skin(circ)) < 0) {
  359.       log_info(LD_CIRC,"circuit_send_next_onion_skin failed.");
  360.       return err_reason;
  361.     }
  362.   }
  363.   return 0;
  364. }
  365. /** Find any circuits that are waiting on <b>or_conn</b> to become
  366.  * open and get them to send their create cells forward.
  367.  *
  368.  * Status is 1 if connect succeeded, or 0 if connect failed.
  369.  */
  370. void
  371. circuit_n_conn_done(or_connection_t *or_conn, int status)
  372. {
  373.   smartlist_t *pending_circs;
  374.   int err_reason = 0;
  375.   log_debug(LD_CIRC,"or_conn to %s/%s, status=%d",
  376.             or_conn->nickname ? or_conn->nickname : "NULL",
  377.             or_conn->_base.address, status);
  378.   pending_circs = smartlist_create();
  379.   circuit_get_all_pending_on_or_conn(pending_circs, or_conn);
  380.   SMARTLIST_FOREACH_BEGIN(pending_circs, circuit_t *, circ)
  381.     {
  382.       /* These checks are redundant wrt get_all_pending_on_or_conn, but I'm
  383.        * leaving them in in case it's possible for the status of a circuit to
  384.        * change as we're going down the list. */
  385.       if (circ->marked_for_close || circ->n_conn || !circ->n_hop ||
  386.           circ->state != CIRCUIT_STATE_OR_WAIT)
  387.         continue;
  388.       if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
  389.         /* Look at addr/port. This is an unkeyed connection. */
  390.         if (!tor_addr_eq(&circ->n_hop->addr, &or_conn->_base.addr) ||
  391.             circ->n_hop->port != or_conn->_base.port)
  392.           continue;
  393.       } else {
  394.         /* We expected a key. See if it's the right one. */
  395.         if (memcmp(or_conn->identity_digest,
  396.                    circ->n_hop->identity_digest, DIGEST_LEN))
  397.           continue;
  398.       }
  399.       if (!status) { /* or_conn failed; close circ */
  400.         log_info(LD_CIRC,"or_conn failed. Closing circ.");
  401.         circuit_mark_for_close(circ, END_CIRC_REASON_OR_CONN_CLOSED);
  402.         continue;
  403.       }
  404.       log_debug(LD_CIRC, "Found circ, sending create cell.");
  405.       /* circuit_deliver_create_cell will set n_circ_id and add us to
  406.        * orconn_circuid_circuit_map, so we don't need to call
  407.        * set_circid_orconn here. */
  408.       circ->n_conn = or_conn;
  409.       extend_info_free(circ->n_hop);
  410.       circ->n_hop = NULL;
  411.       if (CIRCUIT_IS_ORIGIN(circ)) {
  412.         if ((err_reason =
  413.              circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ))) < 0) {
  414.           log_info(LD_CIRC,
  415.                    "send_next_onion_skin failed; circuit marked for closing.");
  416.           circuit_mark_for_close(circ, -err_reason);
  417.           continue;
  418.           /* XXX could this be bad, eg if next_onion_skin failed because conn
  419.            *     died? */
  420.         }
  421.       } else {
  422.         /* pull the create cell out of circ->onionskin, and send it */
  423.         tor_assert(circ->n_conn_onionskin);
  424.         if (circuit_deliver_create_cell(circ,CELL_CREATE,
  425.                                         circ->n_conn_onionskin)<0) {
  426.           circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
  427.           continue;
  428.         }
  429.         tor_free(circ->n_conn_onionskin);
  430.         circuit_set_state(circ, CIRCUIT_STATE_OPEN);
  431.       }
  432.     }
  433.   SMARTLIST_FOREACH_END(circ);
  434.   smartlist_free(pending_circs);
  435. }
  436. /** Find a new circid that isn't currently in use on the circ->n_conn
  437.  * for the outgoing
  438.  * circuit <b>circ</b>, and deliver a cell of type <b>cell_type</b>
  439.  * (either CELL_CREATE or CELL_CREATE_FAST) with payload <b>payload</b>
  440.  * to this circuit.
  441.  * Return -1 if we failed to find a suitable circid, else return 0.
  442.  */
  443. static int
  444. circuit_deliver_create_cell(circuit_t *circ, uint8_t cell_type,
  445.                             const char *payload)
  446. {
  447.   cell_t cell;
  448.   circid_t id;
  449.   tor_assert(circ);
  450.   tor_assert(circ->n_conn);
  451.   tor_assert(payload);
  452.   tor_assert(cell_type == CELL_CREATE || cell_type == CELL_CREATE_FAST);
  453.   id = get_unique_circ_id_by_conn(circ->n_conn);
  454.   if (!id) {
  455.     log_warn(LD_CIRC,"failed to get unique circID.");
  456.     return -1;
  457.   }
  458.   log_debug(LD_CIRC,"Chosen circID %u.", id);
  459.   circuit_set_n_circid_orconn(circ, id, circ->n_conn);
  460.   memset(&cell, 0, sizeof(cell_t));
  461.   cell.command = cell_type;
  462.   cell.circ_id = circ->n_circ_id;
  463.   memcpy(cell.payload, payload, ONIONSKIN_CHALLENGE_LEN);
  464.   append_cell_to_circuit_queue(circ, circ->n_conn, &cell, CELL_DIRECTION_OUT);
  465.   if (CIRCUIT_IS_ORIGIN(circ)) {
  466.     /* mark it so it gets better rate limiting treatment. */
  467.     circ->n_conn->client_used = time(NULL);
  468.   }
  469.   return 0;
  470. }
  471. /** We've decided to start our reachability testing. If all
  472.  * is set, log this to the user. Return 1 if we did, or 0 if
  473.  * we chose not to log anything. */
  474. int
  475. inform_testing_reachability(void)
  476. {
  477.   char dirbuf[128];
  478.   routerinfo_t *me = router_get_my_routerinfo();
  479.   if (!me)
  480.     return 0;
  481.   control_event_server_status(LOG_NOTICE,
  482.                               "CHECKING_REACHABILITY ORADDRESS=%s:%d",
  483.                               me->address, me->or_port);
  484.   if (me->dir_port) {
  485.     tor_snprintf(dirbuf, sizeof(dirbuf), " and DirPort %s:%d",
  486.                  me->address, me->dir_port);
  487.     control_event_server_status(LOG_NOTICE,
  488.                                 "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
  489.                                 me->address, me->dir_port);
  490.   }
  491.   log(LOG_NOTICE, LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... "
  492.                          "(this may take up to %d minutes -- look for log "
  493.                          "messages indicating success)",
  494.       me->address, me->or_port,
  495.       me->dir_port ? dirbuf : "",
  496.       me->dir_port ? "are" : "is",
  497.       TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT/60);
  498.   return 1;
  499. }
  500. /** Return true iff we should send a create_fast cell to start building a given
  501.  * circuit */
  502. static INLINE int
  503. should_use_create_fast_for_circuit(origin_circuit_t *circ)
  504. {
  505.   or_options_t *options = get_options();
  506.   tor_assert(circ->cpath);
  507.   tor_assert(circ->cpath->extend_info);
  508.   if (!circ->cpath->extend_info->onion_key)
  509.     return 1; /* our hand is forced: only a create_fast will work. */
  510.   if (!options->FastFirstHopPK)
  511.     return 0; /* we prefer to avoid create_fast */
  512.   if (server_mode(options)) {
  513.     /* We're a server, and we know an onion key. We can choose.
  514.      * Prefer to blend in. */
  515.     return 0;
  516.   }
  517.   return 1;
  518. }
  519. /** This is the backbone function for building circuits.
  520.  *
  521.  * If circ's first hop is closed, then we need to build a create
  522.  * cell and send it forward.
  523.  *
  524.  * Otherwise, we need to build a relay extend cell and send it
  525.  * forward.
  526.  *
  527.  * Return -reason if we want to tear down circ, else return 0.
  528.  */
  529. int
  530. circuit_send_next_onion_skin(origin_circuit_t *circ)
  531. {
  532.   crypt_path_t *hop;
  533.   routerinfo_t *router;
  534.   char payload[2+4+DIGEST_LEN+ONIONSKIN_CHALLENGE_LEN];
  535.   char *onionskin;
  536.   size_t payload_len;
  537.   tor_assert(circ);
  538.   if (circ->cpath->state == CPATH_STATE_CLOSED) {
  539.     int fast;
  540.     uint8_t cell_type;
  541.     log_debug(LD_CIRC,"First skin; sending create cell.");
  542.     if (circ->build_state->onehop_tunnel)
  543.       control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE, 0);
  544.     else
  545.       control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE, 0);
  546.     router = router_get_by_digest(circ->_base.n_conn->identity_digest);
  547.     fast = should_use_create_fast_for_circuit(circ);
  548.     if (!fast) {
  549.       /* We are an OR and we know the right onion key: we should
  550.        * send an old slow create cell.
  551.        */
  552.       cell_type = CELL_CREATE;
  553.       if (onion_skin_create(circ->cpath->extend_info->onion_key,
  554.                             &(circ->cpath->dh_handshake_state),
  555.                             payload) < 0) {
  556.         log_warn(LD_CIRC,"onion_skin_create (first hop) failed.");
  557.         return - END_CIRC_REASON_INTERNAL;
  558.       }
  559.       note_request("cell: create", 1);
  560.     } else {
  561.       /* We are not an OR, and we're building the first hop of a circuit to a
  562.        * new OR: we can be speedy and use CREATE_FAST to save an RSA operation
  563.        * and a DH operation. */
  564.       cell_type = CELL_CREATE_FAST;
  565.       memset(payload, 0, sizeof(payload));
  566.       crypto_rand(circ->cpath->fast_handshake_state,
  567.                   sizeof(circ->cpath->fast_handshake_state));
  568.       memcpy(payload, circ->cpath->fast_handshake_state,
  569.              sizeof(circ->cpath->fast_handshake_state));
  570.       note_request("cell: create fast", 1);
  571.     }
  572.     if (circuit_deliver_create_cell(TO_CIRCUIT(circ), cell_type, payload) < 0)
  573.       return - END_CIRC_REASON_RESOURCELIMIT;
  574.     circ->cpath->state = CPATH_STATE_AWAITING_KEYS;
  575.     circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
  576.     log_info(LD_CIRC,"First hop: finished sending %s cell to '%s'",
  577.              fast ? "CREATE_FAST" : "CREATE",
  578.              router ? router->nickname : "<unnamed>");
  579.   } else {
  580.     tor_assert(circ->cpath->state == CPATH_STATE_OPEN);
  581.     tor_assert(circ->_base.state == CIRCUIT_STATE_BUILDING);
  582.     log_debug(LD_CIRC,"starting to send subsequent skin.");
  583.     hop = onion_next_hop_in_cpath(circ->cpath);
  584.     if (!hop) {
  585.       /* done building the circuit. whew. */
  586.       circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
  587.       log_info(LD_CIRC,"circuit built!");
  588.       circuit_reset_failure_count(0);
  589.       if (circ->build_state->onehop_tunnel)
  590.         control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS, 0);
  591.       if (!has_completed_circuit && !circ->build_state->onehop_tunnel) {
  592.         or_options_t *options = get_options();
  593.         has_completed_circuit=1;
  594.         /* FFFF Log a count of known routers here */
  595.         log(LOG_NOTICE, LD_GENERAL,
  596.             "Tor has successfully opened a circuit. "
  597.             "Looks like client functionality is working.");
  598.         control_event_bootstrap(BOOTSTRAP_STATUS_DONE, 0);
  599.         control_event_client_status(LOG_NOTICE, "CIRCUIT_ESTABLISHED");
  600.         if (server_mode(options) && !check_whether_orport_reachable()) {
  601.           inform_testing_reachability();
  602.           consider_testing_reachability(1, 1);
  603.         }
  604.       }
  605.       circuit_rep_hist_note_result(circ);
  606.       circuit_has_opened(circ); /* do other actions as necessary */
  607.       return 0;
  608.     }
  609.     if (tor_addr_family(&hop->extend_info->addr) != AF_INET) {
  610.       log_warn(LD_BUG, "Trying to extend to a non-IPv4 address.");
  611.       return - END_CIRC_REASON_INTERNAL;
  612.     }
  613.     set_uint32(payload, tor_addr_to_ipv4n(&hop->extend_info->addr));
  614.     set_uint16(payload+4, htons(hop->extend_info->port));
  615.     onionskin = payload+2+4;
  616.     memcpy(payload+2+4+ONIONSKIN_CHALLENGE_LEN,
  617.            hop->extend_info->identity_digest, DIGEST_LEN);
  618.     payload_len = 2+4+ONIONSKIN_CHALLENGE_LEN+DIGEST_LEN;
  619.     if (onion_skin_create(hop->extend_info->onion_key,
  620.                           &(hop->dh_handshake_state), onionskin) < 0) {
  621.       log_warn(LD_CIRC,"onion_skin_create failed.");
  622.       return - END_CIRC_REASON_INTERNAL;
  623.     }
  624.     log_info(LD_CIRC,"Sending extend relay cell.");
  625.     note_request("cell: extend", 1);
  626.     /* send it to hop->prev, because it will transfer
  627.      * it to a create cell and then send to hop */
  628.     if (relay_send_command_from_edge(0, TO_CIRCUIT(circ),
  629.                                      RELAY_COMMAND_EXTEND,
  630.                                      payload, payload_len, hop->prev) < 0)
  631.       return 0; /* circuit is closed */
  632.     hop->state = CPATH_STATE_AWAITING_KEYS;
  633.   }
  634.   return 0;
  635. }
  636. /** Our clock just jumped by <b>seconds_elapsed</b>. Assume
  637.  * something has also gone wrong with our network: notify the user,
  638.  * and abandon all not-yet-used circuits. */
  639. void
  640. circuit_note_clock_jumped(int seconds_elapsed)
  641. {
  642.   int severity = server_mode(get_options()) ? LOG_WARN : LOG_NOTICE;
  643.   log(severity, LD_GENERAL, "Your system clock just jumped %d seconds %s; "
  644.       "assuming established circuits no longer work.",
  645.       seconds_elapsed >=0 ? seconds_elapsed : -seconds_elapsed,
  646.       seconds_elapsed >=0 ? "forward" : "backward");
  647.   control_event_general_status(LOG_WARN, "CLOCK_JUMPED TIME=%d",
  648.                                seconds_elapsed);
  649.   has_completed_circuit=0; /* so it'll log when it works again */
  650.   control_event_client_status(severity, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
  651.                               "CLOCK_JUMPED");
  652.   circuit_mark_all_unused_circs();
  653.   circuit_expire_all_dirty_circs();
  654. }
  655. /** Take the 'extend' <b>cell</b>, pull out addr/port plus the onion
  656.  * skin and identity digest for the next hop. If we're already connected,
  657.  * pass the onion skin to the next hop using a create cell; otherwise
  658.  * launch a new OR connection, and <b>circ</b> will notice when the
  659.  * connection succeeds or fails.
  660.  *
  661.  * Return -1 if we want to warn and tear down the circuit, else return 0.
  662.  */
  663. int
  664. circuit_extend(cell_t *cell, circuit_t *circ)
  665. {
  666.   or_connection_t *n_conn;
  667.   relay_header_t rh;
  668.   char *onionskin;
  669.   char *id_digest=NULL;
  670.   uint32_t n_addr32;
  671.   uint16_t n_port;
  672.   tor_addr_t n_addr;
  673.   const char *msg = NULL;
  674.   int should_launch = 0;
  675.   if (circ->n_conn) {
  676.     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  677.            "n_conn already set. Bug/attack. Closing.");
  678.     return -1;
  679.   }
  680.   if (circ->n_hop) {
  681.     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  682.            "conn to next hop already launched. Bug/attack. Closing.");
  683.     return -1;
  684.   }
  685.   if (!server_mode(get_options())) {
  686.     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  687.            "Got an extend cell, but running as a client. Closing.");
  688.     return -1;
  689.   }
  690.   relay_header_unpack(&rh, cell->payload);
  691.   if (rh.length < 4+2+ONIONSKIN_CHALLENGE_LEN+DIGEST_LEN) {
  692.     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  693.            "Wrong length %d on extend cell. Closing circuit.",
  694.            rh.length);
  695.     return -1;
  696.   }
  697.   n_addr32 = ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE));
  698.   n_port = ntohs(get_uint16(cell->payload+RELAY_HEADER_SIZE+4));
  699.   onionskin = cell->payload+RELAY_HEADER_SIZE+4+2;
  700.   id_digest = cell->payload+RELAY_HEADER_SIZE+4+2+ONIONSKIN_CHALLENGE_LEN;
  701.   tor_addr_from_ipv4h(&n_addr, n_addr32);
  702.   if (!n_port || !n_addr32) {
  703.     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  704.            "Client asked me to extend to zero destination port or addr.");
  705.     return -1;
  706.   }
  707.   /* Check if they asked us for 0000..0000. We support using
  708.    * an empty fingerprint for the first hop (e.g. for a bridge relay),
  709.    * but we don't want to let people send us extend cells for empty
  710.    * fingerprints -- a) because it opens the user up to a mitm attack,
  711.    * and b) because it lets an attacker force the relay to hold open a
  712.    * new TLS connection for each extend request. */
  713.   if (tor_digest_is_zero(id_digest)) {
  714.     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  715.            "Client asked me to extend without specifying an id_digest.");
  716.     return -1;
  717.   }
  718.   /* Next, check if we're being asked to connect to the hop that the
  719.    * extend cell came from. There isn't any reason for that, and it can
  720.    * assist circular-path attacks. */
  721.   if (!memcmp(id_digest, TO_OR_CIRCUIT(circ)->p_conn->identity_digest,
  722.               DIGEST_LEN)) {
  723.     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  724.            "Client asked me to extend back to the previous hop.");
  725.     return -1;
  726.   }
  727.   n_conn = connection_or_get_for_extend(id_digest,
  728.                                         &n_addr,
  729.                                         &msg,
  730.                                         &should_launch);
  731.   if (!n_conn) {
  732.     log_debug(LD_CIRC|LD_OR,"Next router (%s:%d): %s",
  733.               fmt_addr(&n_addr), (int)n_port, msg?msg:"????");
  734.     circ->n_hop = extend_info_alloc(NULL /*nickname*/,
  735.                                     id_digest,
  736.                                     NULL /*onion_key*/,
  737.                                     &n_addr, n_port);
  738.     circ->n_conn_onionskin = tor_malloc(ONIONSKIN_CHALLENGE_LEN);
  739.     memcpy(circ->n_conn_onionskin, onionskin, ONIONSKIN_CHALLENGE_LEN);
  740.     circuit_set_state(circ, CIRCUIT_STATE_OR_WAIT);
  741.     if (should_launch) {
  742.       /* we should try to open a connection */
  743.       n_conn = connection_or_connect(&n_addr, n_port, id_digest);
  744.       if (!n_conn) {
  745.         log_info(LD_CIRC,"Launching n_conn failed. Closing circuit.");
  746.         circuit_mark_for_close(circ, END_CIRC_REASON_CONNECTFAILED);
  747.         return 0;
  748.       }
  749.       log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
  750.     }
  751.     /* return success. The onion/circuit/etc will be taken care of
  752.      * automatically (may already have been) whenever n_conn reaches
  753.      * OR_CONN_STATE_OPEN.
  754.      */
  755.     return 0;
  756.   }
  757.   tor_assert(!circ->n_hop); /* Connection is already established. */
  758.   circ->n_conn = n_conn;
  759.   log_debug(LD_CIRC,"n_conn is %s:%u",
  760.             n_conn->_base.address,n_conn->_base.port);
  761.   if (circuit_deliver_create_cell(circ, CELL_CREATE, onionskin) < 0)
  762.     return -1;
  763.   return 0;
  764. }
  765. /** Initialize cpath->{f|b}_{crypto|digest} from the key material in
  766.  * key_data.  key_data must contain CPATH_KEY_MATERIAL bytes, which are
  767.  * used as follows:
  768.  *   - 20 to initialize f_digest
  769.  *   - 20 to initialize b_digest
  770.  *   - 16 to key f_crypto
  771.  *   - 16 to key b_crypto
  772.  *
  773.  * (If 'reverse' is true, then f_XX and b_XX are swapped.)
  774.  */
  775. int
  776. circuit_init_cpath_crypto(crypt_path_t *cpath, const char *key_data,
  777.                           int reverse)
  778. {
  779.   crypto_digest_env_t *tmp_digest;
  780.   crypto_cipher_env_t *tmp_crypto;
  781.   tor_assert(cpath);
  782.   tor_assert(key_data);
  783.   tor_assert(!(cpath->f_crypto || cpath->b_crypto ||
  784.              cpath->f_digest || cpath->b_digest));
  785.   cpath->f_digest = crypto_new_digest_env();
  786.   crypto_digest_add_bytes(cpath->f_digest, key_data, DIGEST_LEN);
  787.   cpath->b_digest = crypto_new_digest_env();
  788.   crypto_digest_add_bytes(cpath->b_digest, key_data+DIGEST_LEN, DIGEST_LEN);
  789.   if (!(cpath->f_crypto =
  790.         crypto_create_init_cipher(key_data+(2*DIGEST_LEN),1))) {
  791.     log_warn(LD_BUG,"Forward cipher initialization failed.");
  792.     return -1;
  793.   }
  794.   if (!(cpath->b_crypto =
  795.         crypto_create_init_cipher(key_data+(2*DIGEST_LEN)+CIPHER_KEY_LEN,0))) {
  796.     log_warn(LD_BUG,"Backward cipher initialization failed.");
  797.     return -1;
  798.   }
  799.   if (reverse) {
  800.     tmp_digest = cpath->f_digest;
  801.     cpath->f_digest = cpath->b_digest;
  802.     cpath->b_digest = tmp_digest;
  803.     tmp_crypto = cpath->f_crypto;
  804.     cpath->f_crypto = cpath->b_crypto;
  805.     cpath->b_crypto = tmp_crypto;
  806.   }
  807.   return 0;
  808. }
  809. /** A created or extended cell came back to us on the circuit, and it included
  810.  * <b>reply</b> as its body.  (If <b>reply_type</b> is CELL_CREATED, the body
  811.  * contains (the second DH key, plus KH).  If <b>reply_type</b> is
  812.  * CELL_CREATED_FAST, the body contains a secret y and a hash H(x|y).)
  813.  *
  814.  * Calculate the appropriate keys and digests, make sure KH is
  815.  * correct, and initialize this hop of the cpath.
  816.  *
  817.  * Return - reason if we want to mark circ for close, else return 0.
  818.  */
  819. int
  820. circuit_finish_handshake(origin_circuit_t *circ, uint8_t reply_type,
  821.                          const char *reply)
  822. {
  823.   char keys[CPATH_KEY_MATERIAL_LEN];
  824.   crypt_path_t *hop;
  825.   if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS)
  826.     hop = circ->cpath;
  827.   else {
  828.     hop = onion_next_hop_in_cpath(circ->cpath);
  829.     if (!hop) { /* got an extended when we're all done? */
  830.       log_warn(LD_PROTOCOL,"got extended when circ already built? Closing.");
  831.       return - END_CIRC_REASON_TORPROTOCOL;
  832.     }
  833.   }
  834.   tor_assert(hop->state == CPATH_STATE_AWAITING_KEYS);
  835.   if (reply_type == CELL_CREATED && hop->dh_handshake_state) {
  836.     if (onion_skin_client_handshake(hop->dh_handshake_state, reply, keys,
  837.                                     DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) {
  838.       log_warn(LD_CIRC,"onion_skin_client_handshake failed.");
  839.       return -END_CIRC_REASON_TORPROTOCOL;
  840.     }
  841.     /* Remember hash of g^xy */
  842.     memcpy(hop->handshake_digest, reply+DH_KEY_LEN, DIGEST_LEN);
  843.   } else if (reply_type == CELL_CREATED_FAST && !hop->dh_handshake_state) {
  844.     if (fast_client_handshake(hop->fast_handshake_state, reply, keys,
  845.                               DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) {
  846.       log_warn(LD_CIRC,"fast_client_handshake failed.");
  847.       return -END_CIRC_REASON_TORPROTOCOL;
  848.     }
  849.     memcpy(hop->handshake_digest, reply+DIGEST_LEN, DIGEST_LEN);
  850.   } else {
  851.     log_warn(LD_PROTOCOL,"CREATED cell type did not match CREATE cell type.");
  852.     return -END_CIRC_REASON_TORPROTOCOL;
  853.   }
  854.   if (hop->dh_handshake_state) {
  855.     crypto_dh_free(hop->dh_handshake_state); /* don't need it anymore */
  856.     hop->dh_handshake_state = NULL;
  857.   }
  858.   memset(hop->fast_handshake_state, 0, sizeof(hop->fast_handshake_state));
  859.   if (circuit_init_cpath_crypto(hop, keys, 0)<0) {
  860.     return -END_CIRC_REASON_TORPROTOCOL;
  861.   }
  862.   hop->state = CPATH_STATE_OPEN;
  863.   log_info(LD_CIRC,"Finished building %scircuit hop:",
  864.            (reply_type == CELL_CREATED_FAST) ? "fast " : "");
  865.   circuit_log_path(LOG_INFO,LD_CIRC,circ);
  866.   control_event_circuit_status(circ, CIRC_EVENT_EXTENDED, 0);
  867.   return 0;
  868. }
  869. /** We received a relay truncated cell on circ.
  870.  *
  871.  * Since we don't ask for truncates currently, getting a truncated
  872.  * means that a connection broke or an extend failed. For now,
  873.  * just give up: for circ to close, and return 0.
  874.  */
  875. int
  876. circuit_truncated(origin_circuit_t *circ, crypt_path_t *layer)
  877. {
  878. //  crypt_path_t *victim;
  879. //  connection_t *stream;
  880.   tor_assert(circ);
  881.   tor_assert(layer);
  882.   /* XXX Since we don't ask for truncates currently, getting a truncated
  883.    *     means that a connection broke or an extend failed. For now,
  884.    *     just give up.
  885.    */
  886.   circuit_mark_for_close(TO_CIRCUIT(circ),
  887.           END_CIRC_REASON_FLAG_REMOTE|END_CIRC_REASON_OR_CONN_CLOSED);
  888.   return 0;
  889. #if 0
  890.   while (layer->next != circ->cpath) {
  891.     /* we need to clear out layer->next */
  892.     victim = layer->next;
  893.     log_debug(LD_CIRC, "Killing a layer of the cpath.");
  894.     for (stream = circ->p_streams; stream; stream=stream->next_stream) {
  895.       if (stream->cpath_layer == victim) {
  896.         log_info(LD_APP, "Marking stream %d for close because of truncate.",
  897.                  stream->stream_id);
  898.         /* no need to send 'end' relay cells,
  899.          * because the other side's already dead
  900.          */
  901.         connection_mark_unattached_ap(stream, END_STREAM_REASON_DESTROY);
  902.       }
  903.     }
  904.     layer->next = victim->next;
  905.     circuit_free_cpath_node(victim);
  906.   }
  907.   log_info(LD_CIRC, "finished");
  908.   return 0;
  909. #endif
  910. }
  911. /** Given a response payload and keys, initialize, then send a created
  912.  * cell back.
  913.  */
  914. int
  915. onionskin_answer(or_circuit_t *circ, uint8_t cell_type, const char *payload,
  916.                  const char *keys)
  917. {
  918.   cell_t cell;
  919.   crypt_path_t *tmp_cpath;
  920.   tmp_cpath = tor_malloc_zero(sizeof(crypt_path_t));
  921.   tmp_cpath->magic = CRYPT_PATH_MAGIC;
  922.   memset(&cell, 0, sizeof(cell_t));
  923.   cell.command = cell_type;
  924.   cell.circ_id = circ->p_circ_id;
  925.   circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
  926.   memcpy(cell.payload, payload,
  927.          cell_type == CELL_CREATED ? ONIONSKIN_REPLY_LEN : DIGEST_LEN*2);
  928.   log_debug(LD_CIRC,"init digest forward 0x%.8x, backward 0x%.8x.",
  929.             (unsigned int)*(uint32_t*)(keys),
  930.             (unsigned int)*(uint32_t*)(keys+20));
  931.   if (circuit_init_cpath_crypto(tmp_cpath, keys, 0)<0) {
  932.     log_warn(LD_BUG,"Circuit initialization failed");
  933.     tor_free(tmp_cpath);
  934.     return -1;
  935.   }
  936.   circ->n_digest = tmp_cpath->f_digest;
  937.   circ->n_crypto = tmp_cpath->f_crypto;
  938.   circ->p_digest = tmp_cpath->b_digest;
  939.   circ->p_crypto = tmp_cpath->b_crypto;
  940.   tmp_cpath->magic = 0;
  941.   tor_free(tmp_cpath);
  942.   if (cell_type == CELL_CREATED)
  943.     memcpy(circ->handshake_digest, cell.payload+DH_KEY_LEN, DIGEST_LEN);
  944.   else
  945.     memcpy(circ->handshake_digest, cell.payload+DIGEST_LEN, DIGEST_LEN);
  946.   circ->is_first_hop = (cell_type == CELL_CREATED_FAST);
  947.   append_cell_to_circuit_queue(TO_CIRCUIT(circ),
  948.                                circ->p_conn, &cell, CELL_DIRECTION_IN);
  949.   log_debug(LD_CIRC,"Finished sending 'created' cell.");
  950.   if (!is_local_addr(&circ->p_conn->_base.addr) &&
  951.       !connection_or_nonopen_was_started_here(circ->p_conn)) {
  952.     /* record that we could process create cells from a non-local conn
  953.      * that we didn't initiate; presumably this means that create cells
  954.      * can reach us too. */
  955.     router_orport_found_reachable();
  956.   }
  957.   return 0;
  958. }
  959. /** Choose a length for a circuit of purpose <b>purpose</b>.
  960.  * Default length is 3 + the number of endpoints that would give something
  961.  * away. If the routerlist <b>routers</b> doesn't have enough routers
  962.  * to handle the desired path length, return as large a path length as
  963.  * is feasible, except if it's less than 2, in which case return -1.
  964.  */
  965. static int
  966. new_route_len(uint8_t purpose, extend_info_t *exit,
  967.               smartlist_t *routers)
  968. {
  969.   int num_acceptable_routers;
  970.   int routelen;
  971.   tor_assert(routers);
  972.   routelen = 3;
  973.   if (exit &&
  974.       purpose != CIRCUIT_PURPOSE_TESTING &&
  975.       purpose != CIRCUIT_PURPOSE_S_ESTABLISH_INTRO)
  976.     routelen++;
  977.   num_acceptable_routers = count_acceptable_routers(routers);
  978.   log_debug(LD_CIRC,"Chosen route length %d (%d/%d routers suitable).",
  979.             routelen, num_acceptable_routers, smartlist_len(routers));
  980.   if (num_acceptable_routers < 2) {
  981.     log_info(LD_CIRC,
  982.              "Not enough acceptable routers (%d). Discarding this circuit.",
  983.              num_acceptable_routers);
  984.     return -1;
  985.   }
  986.   if (num_acceptable_routers < routelen) {
  987.     log_info(LD_CIRC,"Not enough routers: cutting routelen from %d to %d.",
  988.              routelen, num_acceptable_routers);
  989.     routelen = num_acceptable_routers;
  990.   }
  991.   return routelen;
  992. }
  993. /** Fetch the list of predicted ports, dup it into a smartlist of
  994.  * uint16_t's, remove the ones that are already handled by an
  995.  * existing circuit, and return it.
  996.  */
  997. static smartlist_t *
  998. circuit_get_unhandled_ports(time_t now)
  999. {
  1000.   smartlist_t *source = rep_hist_get_predicted_ports(now);
  1001.   smartlist_t *dest = smartlist_create();
  1002.   uint16_t *tmp;
  1003.   int i;
  1004.   for (i = 0; i < smartlist_len(source); ++i) {
  1005.     tmp = tor_malloc(sizeof(uint16_t));
  1006.     memcpy(tmp, smartlist_get(source, i), sizeof(uint16_t));
  1007.     smartlist_add(dest, tmp);
  1008.   }
  1009.   circuit_remove_handled_ports(dest);
  1010.   return dest;
  1011. }
  1012. /** Return 1 if we already have circuits present or on the way for
  1013.  * all anticipated ports. Return 0 if we should make more.
  1014.  *
  1015.  * If we're returning 0, set need_uptime and need_capacity to
  1016.  * indicate any requirements that the unhandled ports have.
  1017.  */
  1018. int
  1019. circuit_all_predicted_ports_handled(time_t now, int *need_uptime,
  1020.                                     int *need_capacity)
  1021. {
  1022.   int i, enough;
  1023.   uint16_t *port;
  1024.   smartlist_t *sl = circuit_get_unhandled_ports(now);
  1025.   smartlist_t *LongLivedServices = get_options()->LongLivedPorts;
  1026.   tor_assert(need_uptime);
  1027.   tor_assert(need_capacity);
  1028.   enough = (smartlist_len(sl) == 0);
  1029.   for (i = 0; i < smartlist_len(sl); ++i) {
  1030.     port = smartlist_get(sl, i);
  1031.     if (smartlist_string_num_isin(LongLivedServices, *port))
  1032.       *need_uptime = 1;
  1033.     tor_free(port);
  1034.   }
  1035.   smartlist_free(sl);
  1036.   return enough;
  1037. }
  1038. /** Return 1 if <b>router</b> can handle one or more of the ports in
  1039.  * <b>needed_ports</b>, else return 0.
  1040.  */
  1041. static int
  1042. router_handles_some_port(routerinfo_t *router, smartlist_t *needed_ports)
  1043. {
  1044.   int i;
  1045.   uint16_t port;
  1046.   for (i = 0; i < smartlist_len(needed_ports); ++i) {
  1047.     addr_policy_result_t r;
  1048.     port = *(uint16_t *)smartlist_get(needed_ports, i);
  1049.     tor_assert(port);
  1050.     r = compare_addr_to_addr_policy(0, port, router->exit_policy);
  1051.     if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED)
  1052.       return 1;
  1053.   }
  1054.   return 0;
  1055. }
  1056. /** Return true iff <b>conn</b> needs another general circuit to be
  1057.  * built. */
  1058. static int
  1059. ap_stream_wants_exit_attention(connection_t *conn)
  1060. {
  1061.   if (conn->type == CONN_TYPE_AP &&
  1062.       conn->state == AP_CONN_STATE_CIRCUIT_WAIT &&
  1063.       !conn->marked_for_close &&
  1064.       !(TO_EDGE_CONN(conn)->want_onehop) && /* ignore one-hop streams */
  1065.       !(TO_EDGE_CONN(conn)->use_begindir) && /* ignore targeted dir fetches */
  1066.       !(TO_EDGE_CONN(conn)->chosen_exit_name) && /* ignore defined streams */
  1067.       !connection_edge_is_rendezvous_stream(TO_EDGE_CONN(conn)) &&
  1068.       !circuit_stream_is_being_handled(TO_EDGE_CONN(conn), 0,
  1069.                                        MIN_CIRCUITS_HANDLING_STREAM))
  1070.     return 1;
  1071.   return 0;
  1072. }
  1073. /** Return a pointer to a suitable router to be the exit node for the
  1074.  * general-purpose circuit we're about to build.
  1075.  *
  1076.  * Look through the connection array, and choose a router that maximizes
  1077.  * the number of pending streams that can exit from this router.
  1078.  *
  1079.  * Return NULL if we can't find any suitable routers.
  1080.  */
  1081. static routerinfo_t *
  1082. choose_good_exit_server_general(routerlist_t *dir, int need_uptime,
  1083.                                 int need_capacity)
  1084. {
  1085.   int *n_supported;
  1086.   int i;
  1087.   int n_pending_connections = 0;
  1088.   smartlist_t *connections;
  1089.   int best_support = -1;
  1090.   int n_best_support=0;
  1091.   routerinfo_t *router;
  1092.   or_options_t *options = get_options();
  1093.   connections = get_connection_array();
  1094.   /* Count how many connections are waiting for a circuit to be built.
  1095.    * We use this for log messages now, but in the future we may depend on it.
  1096.    */
  1097.   SMARTLIST_FOREACH(connections, connection_t *, conn,
  1098.   {
  1099.     if (ap_stream_wants_exit_attention(conn))
  1100.       ++n_pending_connections;
  1101.   });
  1102. //  log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
  1103. //         n_pending_connections);
  1104.   /* Now we count, for each of the routers in the directory, how many
  1105.    * of the pending connections could possibly exit from that
  1106.    * router (n_supported[i]). (We can't be sure about cases where we
  1107.    * don't know the IP address of the pending connection.)
  1108.    *
  1109.    * -1 means "Don't use this router at all."
  1110.    */
  1111.   n_supported = tor_malloc(sizeof(int)*smartlist_len(dir->routers));
  1112.   for (i = 0; i < smartlist_len(dir->routers); ++i) {/* iterate over routers */
  1113.     router = smartlist_get(dir->routers, i);
  1114.     if (router_is_me(router)) {
  1115.       n_supported[i] = -1;
  1116. //      log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
  1117.       /* XXX there's probably a reverse predecessor attack here, but
  1118.        * it's slow. should we take this out? -RD
  1119.        */
  1120.       continue;
  1121.     }
  1122.     if (!router->is_running || router->is_bad_exit) {
  1123.       n_supported[i] = -1;
  1124.       continue; /* skip routers that are known to be down or bad exits */
  1125.     }
  1126.     if (router_is_unreliable(router, need_uptime, need_capacity, 0)) {
  1127.       n_supported[i] = -1;
  1128.       continue; /* skip routers that are not suitable */
  1129.     }
  1130.     if (!(router->is_valid || options->_AllowInvalid & ALLOW_INVALID_EXIT)) {
  1131.       /* if it's invalid and we don't want it */
  1132.       n_supported[i] = -1;
  1133. //      log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.",
  1134. //             router->nickname, i);
  1135.       continue; /* skip invalid routers */
  1136.     }
  1137.     if (options->ExcludeSingleHopRelays && router->allow_single_hop_exits) {
  1138.       n_supported[i] = -1;
  1139.       continue;
  1140.     }
  1141.     if (router_exit_policy_rejects_all(router)) {
  1142.       n_supported[i] = -1;
  1143. //      log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
  1144. //             router->nickname, i);
  1145.       continue; /* skip routers that reject all */
  1146.     }
  1147.     n_supported[i] = 0;
  1148.     /* iterate over connections */
  1149.     SMARTLIST_FOREACH(connections, connection_t *, conn,
  1150.     {
  1151.       if (!ap_stream_wants_exit_attention(conn))
  1152.         continue; /* Skip everything but APs in CIRCUIT_WAIT */
  1153.       if (connection_ap_can_use_exit(TO_EDGE_CONN(conn), router)) {
  1154.         ++n_supported[i];
  1155. //        log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
  1156. //               router->nickname, i, n_supported[i]);
  1157.       } else {
  1158. //        log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
  1159. //               router->nickname, i);
  1160.       }
  1161.     }); /* End looping over connections. */
  1162.     if (n_pending_connections > 0 && n_supported[i] == 0) {
  1163.       /* Leave best_support at -1 if that's where it is, so we can
  1164.        * distinguish it later. */
  1165.       continue;
  1166.     }
  1167.     if (n_supported[i] > best_support) {
  1168.       /* If this router is better than previous ones, remember its index
  1169.        * and goodness, and start counting how many routers are this good. */
  1170.       best_support = n_supported[i]; n_best_support=1;
  1171. //      log_fn(LOG_DEBUG,"%s is new best supported option so far.",
  1172. //             router->nickname);
  1173.     } else if (n_supported[i] == best_support) {
  1174.       /* If this router is _as good_ as the best one, just increment the
  1175.        * count of equally good routers.*/
  1176.       ++n_best_support;
  1177.     }
  1178.   }
  1179.   log_info(LD_CIRC,
  1180.            "Found %d servers that might support %d/%d pending connections.",
  1181.            n_best_support, best_support >= 0 ? best_support : 0,
  1182.            n_pending_connections);
  1183.   /* If any routers definitely support any pending connections, choose one
  1184.    * at random. */
  1185.   if (best_support > 0) {
  1186.     smartlist_t *supporting = smartlist_create(), *use = smartlist_create();
  1187.     for (i = 0; i < smartlist_len(dir->routers); i++)
  1188.       if (n_supported[i] == best_support)
  1189.         smartlist_add(supporting, smartlist_get(dir->routers, i));
  1190.     routersets_get_disjunction(use, supporting, options->ExitNodes,
  1191.                                options->_ExcludeExitNodesUnion, 1);
  1192.     if (smartlist_len(use) == 0 && !options->StrictExitNodes) {
  1193.       routersets_get_disjunction(use, supporting, NULL,
  1194.                                  options->_ExcludeExitNodesUnion, 1);
  1195.     }
  1196.     router = routerlist_sl_choose_by_bandwidth(use, WEIGHT_FOR_EXIT);
  1197.     smartlist_free(use);
  1198.     smartlist_free(supporting);
  1199.   } else {
  1200.     /* Either there are no pending connections, or no routers even seem to
  1201.      * possibly support any of them.  Choose a router at random that satisfies
  1202.      * at least one predicted exit port. */
  1203.     int try;
  1204.     smartlist_t *needed_ports, *supporting, *use;
  1205.     if (best_support == -1) {
  1206.       if (need_uptime || need_capacity) {
  1207.         log_info(LD_CIRC,
  1208.                  "We couldn't find any live%s%s routers; falling back "
  1209.                  "to list of all routers.",
  1210.                  need_capacity?", fast":"",
  1211.                  need_uptime?", stable":"");
  1212.         tor_free(n_supported);
  1213.         return choose_good_exit_server_general(dir, 0, 0);
  1214.       }
  1215.       log_notice(LD_CIRC, "All routers are down or won't exit -- choosing a "
  1216.                  "doomed exit at random.");
  1217.     }
  1218.     supporting = smartlist_create();
  1219.     use = smartlist_create();
  1220.     needed_ports = circuit_get_unhandled_ports(time(NULL));
  1221.     for (try = 0; try < 2; try++) {
  1222.       /* try once to pick only from routers that satisfy a needed port,
  1223.        * then if there are none, pick from any that support exiting. */
  1224.       for (i = 0; i < smartlist_len(dir->routers); i++) {
  1225.         router = smartlist_get(dir->routers, i);
  1226.         if (n_supported[i] != -1 &&
  1227.             (try || router_handles_some_port(router, needed_ports))) {
  1228. //          log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
  1229. //                 try, router->nickname);
  1230.           smartlist_add(supporting, router);
  1231.         }
  1232.       }
  1233.       routersets_get_disjunction(use, supporting, options->ExitNodes,
  1234.                                  options->_ExcludeExitNodesUnion, 1);
  1235.       if (smartlist_len(use) == 0 && !options->StrictExitNodes) {
  1236.         routersets_get_disjunction(use, supporting, NULL,
  1237.                                    options->_ExcludeExitNodesUnion, 1);
  1238.       }
  1239.       /* XXX sometimes the above results in null, when the requested
  1240.        * exit node is down. we should pick it anyway. */
  1241.       router = routerlist_sl_choose_by_bandwidth(use, WEIGHT_FOR_EXIT);
  1242.       if (router)
  1243.         break;
  1244.       smartlist_clear(supporting);
  1245.       smartlist_clear(use);
  1246.     }
  1247.     SMARTLIST_FOREACH(needed_ports, uint16_t *, cp, tor_free(cp));
  1248.     smartlist_free(needed_ports);
  1249.     smartlist_free(use);
  1250.     smartlist_free(supporting);
  1251.   }
  1252.   tor_free(n_supported);
  1253.   if (router) {
  1254.     log_info(LD_CIRC, "Chose exit server '%s'", router->nickname);
  1255.     return router;
  1256.   }
  1257.   if (options->StrictExitNodes) {
  1258.     log_warn(LD_CIRC,
  1259.              "No specified exit routers seem to be running, and "
  1260.              "StrictExitNodes is set: can't choose an exit.");
  1261.   }
  1262.   return NULL;
  1263. }
  1264. /** Return a pointer to a suitable router to be the exit node for the
  1265.  * circuit of purpose <b>purpose</b> that we're about to build (or NULL
  1266.  * if no router is suitable).
  1267.  *
  1268.  * For general-purpose circuits, pass it off to
  1269.  * choose_good_exit_server_general()
  1270.  *
  1271.  * For client-side rendezvous circuits, choose a random node, weighted
  1272.  * toward the preferences in 'options'.
  1273.  */
  1274. static routerinfo_t *
  1275. choose_good_exit_server(uint8_t purpose, routerlist_t *dir,
  1276.                         int need_uptime, int need_capacity, int is_internal)
  1277. {
  1278.   or_options_t *options = get_options();
  1279.   router_crn_flags_t flags = 0;
  1280.   if (need_uptime)
  1281.     flags |= CRN_NEED_UPTIME;
  1282.   if (need_capacity)
  1283.     flags |= CRN_NEED_CAPACITY;
  1284.   switch (purpose) {
  1285.     case CIRCUIT_PURPOSE_C_GENERAL:
  1286.       if (options->_AllowInvalid & ALLOW_INVALID_MIDDLE)
  1287.         flags |= CRN_ALLOW_INVALID;
  1288.       if (is_internal) /* pick it like a middle hop */
  1289.         return router_choose_random_node(NULL, NULL,
  1290.                                          options->ExcludeNodes, flags);
  1291.       else
  1292.         return choose_good_exit_server_general(dir,need_uptime,need_capacity);
  1293.     case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
  1294.       if (options->_AllowInvalid & ALLOW_INVALID_RENDEZVOUS)
  1295.         flags |= CRN_ALLOW_INVALID;
  1296.       return router_choose_random_node(NULL, NULL,
  1297.                                        options->ExcludeNodes, flags);
  1298.   }
  1299.   log_warn(LD_BUG,"Unhandled purpose %d", purpose);
  1300.   tor_fragile_assert();
  1301.   return NULL;
  1302. }
  1303. /** Log a warning if the user specified an exit for the circuit that
  1304.  * has been excluded from use by ExcludeNodes or ExcludeExitNodes. */
  1305. static void
  1306. warn_if_last_router_excluded(origin_circuit_t *circ, const extend_info_t *exit)
  1307. {
  1308.   or_options_t *options = get_options();
  1309.   routerset_t *rs = options->ExcludeNodes;
  1310.   const char *description;
  1311.   int domain = LD_CIRC;
  1312.   uint8_t purpose = circ->_base.purpose;
  1313.   if (circ->build_state->onehop_tunnel)
  1314.     return;
  1315.   switch (purpose)
  1316.     {
  1317.     default:
  1318.     case CIRCUIT_PURPOSE_OR:
  1319.     case CIRCUIT_PURPOSE_INTRO_POINT:
  1320.     case CIRCUIT_PURPOSE_REND_POINT_WAITING:
  1321.     case CIRCUIT_PURPOSE_REND_ESTABLISHED:
  1322.       log_warn(LD_BUG, "Called on non-origin circuit (purpose %d)",
  1323.                (int)purpose);
  1324.       return;
  1325.     case CIRCUIT_PURPOSE_C_GENERAL:
  1326.       if (circ->build_state->is_internal)
  1327.         return;
  1328.       description = "Requested exit node";
  1329.       rs = options->_ExcludeExitNodesUnion;
  1330.       break;
  1331.     case CIRCUIT_PURPOSE_C_INTRODUCING:
  1332.     case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
  1333.     case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
  1334.     case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
  1335.     case CIRCUIT_PURPOSE_S_CONNECT_REND:
  1336.     case CIRCUIT_PURPOSE_S_REND_JOINED:
  1337.     case CIRCUIT_PURPOSE_TESTING:
  1338.       return;
  1339.     case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
  1340.     case CIRCUIT_PURPOSE_C_REND_READY:
  1341.     case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
  1342.     case CIRCUIT_PURPOSE_C_REND_JOINED:
  1343.       description = "Chosen rendezvous point";
  1344.       domain = LD_BUG;
  1345.       break;
  1346.     case CIRCUIT_PURPOSE_CONTROLLER:
  1347.       rs = options->_ExcludeExitNodesUnion;
  1348.       description = "Controller-selected circuit target";
  1349.       break;
  1350.     }
  1351.   if (routerset_contains_extendinfo(rs, exit)) {
  1352.     log_fn(LOG_WARN, domain, "%s '%s' is in ExcludeNodes%s. Using anyway "
  1353.            "(circuit purpose %d).",
  1354.            description,exit->nickname,
  1355.            rs==options->ExcludeNodes?"":" or ExcludeExitNodes",
  1356.            (int)purpose);
  1357.     circuit_log_path(LOG_WARN, domain, circ);
  1358.   }
  1359.   return;
  1360. }
  1361. /** Decide a suitable length for circ's cpath, and pick an exit
  1362.  * router (or use <b>exit</b> if provided). Store these in the
  1363.  * cpath. Return 0 if ok, -1 if circuit should be closed. */
  1364. static int
  1365. onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit)
  1366. {
  1367.   cpath_build_state_t *state = circ->build_state;
  1368.   routerlist_t *rl = router_get_routerlist();
  1369.   if (state->onehop_tunnel) {
  1370.     log_debug(LD_CIRC, "Launching a one-hop circuit for dir tunnel.");
  1371.     state->desired_path_len = 1;
  1372.   } else {
  1373.     int r = new_route_len(circ->_base.purpose, exit, rl->routers);
  1374.     if (r < 1) /* must be at least 1 */
  1375.       return -1;
  1376.     state->desired_path_len = r;
  1377.   }
  1378.   if (exit) { /* the circuit-builder pre-requested one */
  1379.     warn_if_last_router_excluded(circ, exit);
  1380.     log_info(LD_CIRC,"Using requested exit node '%s'", exit->nickname);
  1381.     exit = extend_info_dup(exit);
  1382.   } else { /* we have to decide one */
  1383.     routerinfo_t *router =
  1384.       choose_good_exit_server(circ->_base.purpose, rl, state->need_uptime,
  1385.                               state->need_capacity, state->is_internal);
  1386.     if (!router) {
  1387.       log_warn(LD_CIRC,"failed to choose an exit server");
  1388.       return -1;
  1389.     }
  1390.     exit = extend_info_from_router(router);
  1391.   }
  1392.   state->chosen_exit = exit;
  1393.   return 0;
  1394. }
  1395. /** Give <b>circ</b> a new exit destination to <b>exit</b>, and add a
  1396.  * hop to the cpath reflecting this. Don't send the next extend cell --
  1397.  * the caller will do this if it wants to.
  1398.  */
  1399. int
  1400. circuit_append_new_exit(origin_circuit_t *circ, extend_info_t *exit)
  1401. {
  1402.   cpath_build_state_t *state;
  1403.   tor_assert(exit);
  1404.   tor_assert(circ);
  1405.   state = circ->build_state;
  1406.   tor_assert(state);
  1407.   if (state->chosen_exit)
  1408.     extend_info_free(state->chosen_exit);
  1409.   state->chosen_exit = extend_info_dup(exit);
  1410.   ++circ->build_state->desired_path_len;
  1411.   onion_append_hop(&circ->cpath, exit);
  1412.   return 0;
  1413. }
  1414. /** Take an open <b>circ</b>, and add a new hop at the end, based on
  1415.  * <b>info</b>. Set its state back to CIRCUIT_STATE_BUILDING, and then
  1416.  * send the next extend cell to begin connecting to that hop.
  1417.  */
  1418. int
  1419. circuit_extend_to_new_exit(origin_circuit_t *circ, extend_info_t *exit)
  1420. {
  1421.   int err_reason = 0;
  1422.   warn_if_last_router_excluded(circ, exit);
  1423.   circuit_append_new_exit(circ, exit);
  1424.   circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
  1425.   if ((err_reason = circuit_send_next_onion_skin(circ))<0) {
  1426.     log_warn(LD_CIRC, "Couldn't extend circuit to new point '%s'.",
  1427.              exit->nickname);
  1428.     circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
  1429.     return -1;
  1430.   }
  1431.   return 0;
  1432. }
  1433. /** Return the number of routers in <b>routers</b> that are currently up
  1434.  * and available for building circuits through.
  1435.  */
  1436. static int
  1437. count_acceptable_routers(smartlist_t *routers)
  1438. {
  1439.   int i, n;
  1440.   int num=0;
  1441.   routerinfo_t *r;
  1442.   n = smartlist_len(routers);
  1443.   for (i=0;i<n;i++) {
  1444.     r = smartlist_get(routers, i);
  1445. //    log_debug(LD_CIRC,
  1446. //              "Contemplating whether router %d (%s) is a new option.",
  1447. //              i, r->nickname);
  1448.     if (r->is_running == 0) {
  1449. //      log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
  1450.       goto next_i_loop;
  1451.     }
  1452.     if (r->is_valid == 0) {
  1453. //      log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
  1454.       goto next_i_loop;
  1455.       /* XXX This clause makes us count incorrectly: if AllowInvalidRouters
  1456.        * allows this node in some places, then we're getting an inaccurate
  1457.        * count. For now, be conservative and don't count it. But later we
  1458.        * should try to be smarter. */
  1459.     }
  1460.     num++;
  1461. //    log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
  1462.     next_i_loop:
  1463.       ; /* C requires an explicit statement after the label */
  1464.   }
  1465.   return num;
  1466. }
  1467. /** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>.
  1468.  * This function is used to extend cpath by another hop.
  1469.  */
  1470. void
  1471. onion_append_to_cpath(crypt_path_t **head_ptr, crypt_path_t *new_hop)
  1472. {
  1473.   if (*head_ptr) {
  1474.     new_hop->next = (*head_ptr);
  1475.     new_hop->prev = (*head_ptr)->prev;
  1476.     (*head_ptr)->prev->next = new_hop;
  1477.     (*head_ptr)->prev = new_hop;
  1478.   } else {
  1479.     *head_ptr = new_hop;
  1480.     new_hop->prev = new_hop->next = new_hop;
  1481.   }
  1482. }
  1483. /** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
  1484.  * and <b>state</b> and the cpath <b>head</b> (currently populated only
  1485.  * to length <b>cur_len</b> to decide a suitable middle hop for a
  1486.  * circuit. In particular, make sure we don't pick the exit node or its
  1487.  * family, and make sure we don't duplicate any previous nodes or their
  1488.  * families. */
  1489. static routerinfo_t *
  1490. choose_good_middle_server(uint8_t purpose,
  1491.                           cpath_build_state_t *state,
  1492.                           crypt_path_t *head,
  1493.                           int cur_len)
  1494. {
  1495.   int i;
  1496.   routerinfo_t *r, *choice;
  1497.   crypt_path_t *cpath;
  1498.   smartlist_t *excluded;
  1499.   or_options_t *options = get_options();
  1500.   router_crn_flags_t flags = 0;
  1501.   tor_assert(_CIRCUIT_PURPOSE_MIN <= purpose &&
  1502.              purpose <= _CIRCUIT_PURPOSE_MAX);
  1503.   log_debug(LD_CIRC, "Contemplating intermediate hop: random choice.");
  1504.   excluded = smartlist_create();
  1505.   if ((r = build_state_get_exit_router(state))) {
  1506.     smartlist_add(excluded, r);
  1507.     routerlist_add_family(excluded, r);
  1508.   }
  1509.   for (i = 0, cpath = head; i < cur_len; ++i, cpath=cpath->next) {
  1510.     if ((r = router_get_by_digest(cpath->extend_info->identity_digest))) {
  1511.       smartlist_add(excluded, r);
  1512.       routerlist_add_family(excluded, r);
  1513.     }
  1514.   }
  1515.   if (state->need_uptime)
  1516.     flags |= CRN_NEED_UPTIME;
  1517.   if (state->need_capacity)
  1518.     flags |= CRN_NEED_CAPACITY;
  1519.   if (options->_AllowInvalid & ALLOW_INVALID_MIDDLE)
  1520.     flags |= CRN_ALLOW_INVALID;
  1521.   choice = router_choose_random_node(NULL,
  1522.                                      excluded, options->ExcludeNodes, flags);
  1523.   smartlist_free(excluded);
  1524.   return choice;
  1525. }
  1526. /** Pick a good entry server for the circuit to be built according to
  1527.  * <b>state</b>.  Don't reuse a chosen exit (if any), don't use this
  1528.  * router (if we're an OR), and respect firewall settings; if we're
  1529.  * configured to use entry guards, return one.
  1530.  *
  1531.  * If <b>state</b> is NULL, we're choosing a router to serve as an entry
  1532.  * guard, not for any particular circuit.
  1533.  */
  1534. static routerinfo_t *
  1535. choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state)
  1536. {
  1537.   routerinfo_t *r, *choice;
  1538.   smartlist_t *excluded;
  1539.   or_options_t *options = get_options();
  1540.   router_crn_flags_t flags = 0;
  1541.   if (state && options->UseEntryGuards &&
  1542.       (purpose != CIRCUIT_PURPOSE_TESTING || options->BridgeRelay)) {
  1543.     return choose_random_entry(state);
  1544.   }
  1545.   excluded = smartlist_create();
  1546.   if (state && (r = build_state_get_exit_router(state))) {
  1547.     smartlist_add(excluded, r);
  1548.     routerlist_add_family(excluded, r);
  1549.   }
  1550.   if (firewall_is_fascist_or()) {
  1551.     /*XXXX This could slow things down a lot; use a smarter implementation */
  1552.     /* exclude all ORs that listen on the wrong port, if anybody notices. */
  1553.     routerlist_t *rl = router_get_routerlist();
  1554.     int i;
  1555.     for (i=0; i < smartlist_len(rl->routers); i++) {
  1556.       r = smartlist_get(rl->routers, i);
  1557.       if (!fascist_firewall_allows_or(r))
  1558.         smartlist_add(excluded, r);
  1559.     }
  1560.   }
  1561.   /* and exclude current entry guards, if applicable */
  1562.   if (options->UseEntryGuards && entry_guards) {
  1563.     SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
  1564.       {
  1565.         if ((r = router_get_by_digest(entry->identity))) {
  1566.           smartlist_add(excluded, r);
  1567.           routerlist_add_family(excluded, r);
  1568.         }
  1569.       });
  1570.   }
  1571.   if (state) {
  1572.     flags |= CRN_NEED_GUARD;
  1573.     if (state->need_uptime)
  1574.       flags |= CRN_NEED_UPTIME;
  1575.     if (state->need_capacity)
  1576.       flags |= CRN_NEED_CAPACITY;
  1577.   }
  1578.   if (options->_AllowInvalid & ALLOW_INVALID_ENTRY)
  1579.     flags |= CRN_ALLOW_INVALID;
  1580.   choice = router_choose_random_node(
  1581.            NULL,
  1582.            excluded,
  1583.            options->ExcludeNodes,
  1584.            flags);
  1585.   smartlist_free(excluded);
  1586.   return choice;
  1587. }
  1588. /** Return the first non-open hop in cpath, or return NULL if all
  1589.  * hops are open. */
  1590. static crypt_path_t *
  1591. onion_next_hop_in_cpath(crypt_path_t *cpath)
  1592. {
  1593.   crypt_path_t *hop = cpath;
  1594.   do {
  1595.     if (hop->state != CPATH_STATE_OPEN)
  1596.       return hop;
  1597.     hop = hop->next;
  1598.   } while (hop != cpath);
  1599.   return NULL;
  1600. }
  1601. /** Choose a suitable next hop in the cpath <b>head_ptr</b>,
  1602.  * based on <b>state</b>. Append the hop info to head_ptr.
  1603.  */
  1604. static int
  1605. onion_extend_cpath(origin_circuit_t *circ)
  1606. {
  1607.   uint8_t purpose = circ->_base.purpose;
  1608.   cpath_build_state_t *state = circ->build_state;
  1609.   int cur_len = circuit_get_cpath_len(circ);
  1610.   extend_info_t *info = NULL;
  1611.   if (cur_len >= state->desired_path_len) {
  1612.     log_debug(LD_CIRC, "Path is complete: %d steps long",
  1613.               state->desired_path_len);
  1614.     return 1;
  1615.   }
  1616.   log_debug(LD_CIRC, "Path is %d long; we want %d", cur_len,
  1617.             state->desired_path_len);
  1618.   if (cur_len == state->desired_path_len - 1) { /* Picking last node */
  1619.     info = extend_info_dup(state->chosen_exit);
  1620.   } else if (cur_len == 0) { /* picking first node */
  1621.     routerinfo_t *r = choose_good_entry_server(purpose, state);
  1622.     if (r)
  1623.       info = extend_info_from_router(r);
  1624.   } else {
  1625.     routerinfo_t *r =
  1626.       choose_good_middle_server(purpose, state, circ->cpath, cur_len);
  1627.     if (r)
  1628.       info = extend_info_from_router(r);
  1629.   }
  1630.   if (!info) {
  1631.     log_warn(LD_CIRC,"Failed to find node for hop %d of our path. Discarding "
  1632.              "this circuit.", cur_len);
  1633.     return -1;
  1634.   }
  1635.   log_debug(LD_CIRC,"Chose router %s for hop %d (exit is %s)",
  1636.             info->nickname, cur_len+1, build_state_get_exit_nickname(state));
  1637.   onion_append_hop(&circ->cpath, info);
  1638.   extend_info_free(info);
  1639.   return 0;
  1640. }
  1641. /** Create a new hop, annotate it with information about its
  1642.  * corresponding router <b>choice</b>, and append it to the
  1643.  * end of the cpath <b>head_ptr</b>. */
  1644. static int
  1645. onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice)
  1646. {
  1647.   crypt_path_t *hop = tor_malloc_zero(sizeof(crypt_path_t));
  1648.   /* link hop into the cpath, at the end. */
  1649.   onion_append_to_cpath(head_ptr, hop);
  1650.   hop->magic = CRYPT_PATH_MAGIC;
  1651.   hop->state = CPATH_STATE_CLOSED;
  1652.   hop->extend_info = extend_info_dup(choice);
  1653.   hop->package_window = circuit_initial_package_window();
  1654.   hop->deliver_window = CIRCWINDOW_START;
  1655.   return 0;
  1656. }
  1657. /** Allocate a new extend_info object based on the various arguments. */
  1658. extend_info_t *
  1659. extend_info_alloc(const char *nickname, const char *digest,
  1660.                   crypto_pk_env_t *onion_key,
  1661.                   const tor_addr_t *addr, uint16_t port)
  1662. {
  1663.   extend_info_t *info = tor_malloc_zero(sizeof(extend_info_t));
  1664.   memcpy(info->identity_digest, digest, DIGEST_LEN);
  1665.   if (nickname)
  1666.     strlcpy(info->nickname, nickname, sizeof(info->nickname));
  1667.   if (onion_key)
  1668.     info->onion_key = crypto_pk_dup_key(onion_key);
  1669.   tor_addr_copy(&info->addr, addr);
  1670.   info->port = port;
  1671.   return info;
  1672. }
  1673. /** Allocate and return a new extend_info_t that can be used to build a
  1674.  * circuit to or through the router <b>r</b>. */
  1675. extend_info_t *
  1676. extend_info_from_router(routerinfo_t *r)
  1677. {
  1678.   tor_addr_t addr;
  1679.   tor_assert(r);
  1680.   tor_addr_from_ipv4h(&addr, r->addr);
  1681.   return extend_info_alloc(r->nickname, r->cache_info.identity_digest,
  1682.                            r->onion_pkey, &addr, r->or_port);
  1683. }
  1684. /** Release storage held by an extend_info_t struct. */
  1685. void
  1686. extend_info_free(extend_info_t *info)
  1687. {
  1688.   tor_assert(info);
  1689.   if (info->onion_key)
  1690.     crypto_free_pk_env(info->onion_key);
  1691.   tor_free(info);
  1692. }
  1693. /** Allocate and return a new extend_info_t with the same contents as
  1694.  * <b>info</b>. */
  1695. extend_info_t *
  1696. extend_info_dup(extend_info_t *info)
  1697. {
  1698.   extend_info_t *newinfo;
  1699.   tor_assert(info);
  1700.   newinfo = tor_malloc(sizeof(extend_info_t));
  1701.   memcpy(newinfo, info, sizeof(extend_info_t));
  1702.   if (info->onion_key)
  1703.     newinfo->onion_key = crypto_pk_dup_key(info->onion_key);
  1704.   else
  1705.     newinfo->onion_key = NULL;
  1706.   return newinfo;
  1707. }
  1708. /** Return the routerinfo_t for the chosen exit router in <b>state</b>.
  1709.  * If there is no chosen exit, or if we don't know the routerinfo_t for
  1710.  * the chosen exit, return NULL.
  1711.  */
  1712. routerinfo_t *
  1713. build_state_get_exit_router(cpath_build_state_t *state)
  1714. {
  1715.   if (!state || !state->chosen_exit)
  1716.     return NULL;
  1717.   return router_get_by_digest(state->chosen_exit->identity_digest);
  1718. }
  1719. /** Return the nickname for the chosen exit router in <b>state</b>. If
  1720.  * there is no chosen exit, or if we don't know the routerinfo_t for the
  1721.  * chosen exit, return NULL.
  1722.  */
  1723. const char *
  1724. build_state_get_exit_nickname(cpath_build_state_t *state)
  1725. {
  1726.   if (!state || !state->chosen_exit)
  1727.     return NULL;
  1728.   return state->chosen_exit->nickname;
  1729. }
  1730. /** Check whether the entry guard <b>e</b> is usable, given the directory
  1731.  * authorities' opinion about the router (stored in <b>ri</b>) and the user's
  1732.  * configuration (in <b>options</b>). Set <b>e</b>-&gt;bad_since
  1733.  * accordingly. Return true iff the entry guard's status changes.
  1734.  *
  1735.  * If it's not usable, set *<b>reason</b> to a static string explaining why.
  1736.  */
  1737. /*XXXX take a routerstatus, not a routerinfo. */
  1738. static int
  1739. entry_guard_set_status(entry_guard_t *e, routerinfo_t *ri,
  1740.                        time_t now, or_options_t *options, const char **reason)
  1741. {
  1742.   char buf[HEX_DIGEST_LEN+1];
  1743.   int changed = 0;
  1744.   tor_assert(options);
  1745.   *reason = NULL;
  1746.   /* Do we want to mark this guard as bad? */
  1747.   if (!ri)
  1748.     *reason = "unlisted";
  1749.   else if (!ri->is_running)
  1750.     *reason = "down";
  1751.   else if (options->UseBridges && ri->purpose != ROUTER_PURPOSE_BRIDGE)
  1752.     *reason = "not a bridge";
  1753.   else if (!options->UseBridges && !ri->is_possible_guard &&
  1754.            !routerset_contains_router(options->EntryNodes,ri))
  1755.     *reason = "not recommended as a guard";
  1756.   else if (routerset_contains_router(options->ExcludeNodes, ri))
  1757.     *reason = "excluded";
  1758.   if (*reason && ! e->bad_since) {
  1759.     /* Router is newly bad. */
  1760.     base16_encode(buf, sizeof(buf), e->identity, DIGEST_LEN);
  1761.     log_info(LD_CIRC, "Entry guard %s (%s) is %s: marking as unusable.",
  1762.              e->nickname, buf, *reason);
  1763.     e->bad_since = now;
  1764.     control_event_guard(e->nickname, e->identity, "BAD");
  1765.     changed = 1;
  1766.   } else if (!*reason && e->bad_since) {
  1767.     /* There's nothing wrong with the router any more. */
  1768.     base16_encode(buf, sizeof(buf), e->identity, DIGEST_LEN);
  1769.     log_info(LD_CIRC, "Entry guard %s (%s) is no longer unusable: "
  1770.              "marking as ok.", e->nickname, buf);
  1771.     e->bad_since = 0;
  1772.     control_event_guard(e->nickname, e->identity, "GOOD");
  1773.     changed = 1;
  1774.   }
  1775.   return changed;
  1776. }
  1777. /** Return true iff enough time has passed since we last tried to connect
  1778.  * to the unreachable guard <b>e</b> that we're willing to try again. */
  1779. static int
  1780. entry_is_time_to_retry(entry_guard_t *e, time_t now)
  1781. {
  1782.   long diff;
  1783.   if (e->last_attempted < e->unreachable_since)
  1784.     return 1;
  1785.   diff = now - e->unreachable_since;
  1786.   if (diff < 6*60*60)
  1787.     return now > (e->last_attempted + 60*60);
  1788.   else if (diff < 3*24*60*60)
  1789.     return now > (e->last_attempted + 4*60*60);
  1790.   else if (diff < 7*24*60*60)
  1791.     return now > (e->last_attempted + 18*60*60);
  1792.   else
  1793.     return now > (e->last_attempted + 36*60*60);
  1794. }
  1795. /** Return the router corresponding to <b>e</b>, if <b>e</b> is
  1796.  * working well enough that we are willing to use it as an entry
  1797.  * right now. (Else return NULL.) In particular, it must be
  1798.  * - Listed as either up or never yet contacted;
  1799.  * - Present in the routerlist;
  1800.  * - Listed as 'stable' or 'fast' by the current dirserver consensus,
  1801.  *   if demanded by <b>need_uptime</b> or <b>need_capacity</b>;
  1802.  *   (This check is currently redundant with the Guard flag, but in
  1803.  *   the future that might change. Best to leave it in for now.)
  1804.  * - Allowed by our current ReachableORAddresses config option; and
  1805.  * - Currently thought to be reachable by us (unless assume_reachable
  1806.  *   is true).
  1807.  */
  1808. static INLINE routerinfo_t *
  1809. entry_is_live(entry_guard_t *e, int need_uptime, int need_capacity,
  1810.               int assume_reachable)
  1811. {
  1812.   routerinfo_t *r;
  1813.   if (e->bad_since)
  1814.     return NULL;
  1815.   /* no good if it's unreachable, unless assume_unreachable or can_retry. */
  1816.   if (!assume_reachable && !e->can_retry &&
  1817.       e->unreachable_since && !entry_is_time_to_retry(e, time(NULL)))
  1818.     return NULL;
  1819.   r = router_get_by_digest(e->identity);
  1820.   if (!r)
  1821.     return NULL;
  1822.   if (get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_BRIDGE)
  1823.     return NULL;
  1824.   if (!get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_GENERAL)
  1825.     return NULL;
  1826.   if (router_is_unreliable(r, need_uptime, need_capacity, 0))
  1827.     return NULL;
  1828.   if (!fascist_firewall_allows_or(r))
  1829.     return NULL;
  1830.   return r;
  1831. }
  1832. /** Return the number of entry guards that we think are usable. */
  1833. static int
  1834. num_live_entry_guards(void)
  1835. {
  1836.   int n = 0;
  1837.   if (! entry_guards)
  1838.     return 0;
  1839.   SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
  1840.     {
  1841.       if (entry_is_live(entry, 0, 1, 0))
  1842.         ++n;
  1843.     });
  1844.   return n;
  1845. }
  1846. /** If <b>digest</b> matches the identity of any node in the
  1847.  * entry_guards list, return that node. Else return NULL. */
  1848. static INLINE entry_guard_t *
  1849. is_an_entry_guard(const char *digest)
  1850. {
  1851.   SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
  1852.                     if (!memcmp(digest, entry->identity, DIGEST_LEN))
  1853.                       return entry;
  1854.                    );
  1855.   return NULL;
  1856. }
  1857. /** Dump a description of our list of entry guards to the log at level
  1858.  * <b>severity</b>. */
  1859. static void
  1860. log_entry_guards(int severity)
  1861. {
  1862.   smartlist_t *elements = smartlist_create();
  1863.   char buf[1024];
  1864.   char *s;
  1865.   SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  1866.     {
  1867.       tor_snprintf(buf, sizeof(buf), "%s (%s%s)",
  1868.                    e->nickname,
  1869.                    entry_is_live(e, 0, 1, 0) ? "up " : "down ",
  1870.                    e->made_contact ? "made-contact" : "never-contacted");
  1871.       smartlist_add(elements, tor_strdup(buf));
  1872.     });
  1873.   s = smartlist_join_strings(elements, ",", 0, NULL);
  1874.   SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
  1875.   smartlist_free(elements);
  1876.   log_fn(severity,LD_CIRC,"%s",s);
  1877.   tor_free(s);
  1878. }
  1879. /** Called when one or more guards that we would previously have used for some
  1880.  * purpose are no longer in use because a higher-priority guard has become
  1881.  * usable again. */
  1882. static void
  1883. control_event_guard_deferred(void)
  1884. {
  1885.   /* XXXX We don't actually have a good way to figure out _how many_ entries
  1886.    * are live for some purpose.  We need an entry_is_even_slightly_live()
  1887.    * function for this to work right.  NumEntryGuards isn't reliable: if we
  1888.    * need guards with weird properties, we can have more than that number
  1889.    * live.
  1890.    **/
  1891. #if 0
  1892.   int n = 0;
  1893.   or_options_t *options = get_options();
  1894.   if (!entry_guards)
  1895.     return;
  1896.   SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
  1897.     {
  1898.       if (entry_is_live(entry, 0, 1, 0)) {
  1899.         if (n++ == options->NumEntryGuards) {
  1900.           control_event_guard(entry->nickname, entry->identity, "DEFERRED");
  1901.           return;
  1902.         }
  1903.       }
  1904.     });
  1905. #endif
  1906. }
  1907. /** Add a new (preferably stable and fast) router to our
  1908.  * entry_guards list. Return a pointer to the router if we succeed,
  1909.  * or NULL if we can't find any more suitable entries.
  1910.  *
  1911.  * If <b>chosen</b> is defined, use that one, and if it's not
  1912.  * already in our entry_guards list, put it at the *beginning*.
  1913.  * Else, put the one we pick at the end of the list. */
  1914. static routerinfo_t *
  1915. add_an_entry_guard(routerinfo_t *chosen, int reset_status)
  1916. {
  1917.   routerinfo_t *router;
  1918.   entry_guard_t *entry;
  1919.   if (chosen) {
  1920.     router = chosen;
  1921.     entry = is_an_entry_guard(router->cache_info.identity_digest);
  1922.     if (entry) {
  1923.       if (reset_status) {
  1924.         entry->bad_since = 0;
  1925.         entry->can_retry = 1;
  1926.       }
  1927.       return NULL;
  1928.     }
  1929.   } else {
  1930.     router = choose_good_entry_server(CIRCUIT_PURPOSE_C_GENERAL, NULL);
  1931.     if (!router)
  1932.       return NULL;
  1933.   }
  1934.   entry = tor_malloc_zero(sizeof(entry_guard_t));
  1935.   log_info(LD_CIRC, "Chose '%s' as new entry guard.", router->nickname);
  1936.   strlcpy(entry->nickname, router->nickname, sizeof(entry->nickname));
  1937.   memcpy(entry->identity, router->cache_info.identity_digest, DIGEST_LEN);
  1938.   entry->chosen_on_date = start_of_month(time(NULL));
  1939.   entry->chosen_by_version = tor_strdup(VERSION);
  1940.   if (chosen) /* prepend */
  1941.     smartlist_insert(entry_guards, 0, entry);
  1942.   else /* append */
  1943.     smartlist_add(entry_guards, entry);
  1944.   control_event_guard(entry->nickname, entry->identity, "NEW");
  1945.   control_event_guard_deferred();
  1946.   log_entry_guards(LOG_INFO);
  1947.   return router;
  1948. }
  1949. /** If the use of entry guards is configured, choose more entry guards
  1950.  * until we have enough in the list. */
  1951. static void
  1952. pick_entry_guards(void)
  1953. {
  1954.   or_options_t *options = get_options();
  1955.   int changed = 0;
  1956.   tor_assert(entry_guards);
  1957.   while (num_live_entry_guards() < options->NumEntryGuards) {
  1958.     if (!add_an_entry_guard(NULL, 0))
  1959.       break;
  1960.     changed = 1;
  1961.   }
  1962.   if (changed)
  1963.     entry_guards_changed();
  1964. }
  1965. /** How long (in seconds) do we allow an entry guard to be nonfunctional,
  1966.  * unlisted, excluded, or otherwise nonusable before we give up on it? */
  1967. #define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60)
  1968. /** Release all storage held by <b>e</b>. */
  1969. static void
  1970. entry_guard_free(entry_guard_t *e)
  1971. {
  1972.   tor_assert(e);
  1973.   tor_free(e->chosen_by_version);
  1974.   tor_free(e);
  1975. }
  1976. /** Remove any entry guard which was selected by an unknown version of Tor,
  1977.  * or which was selected by a version of Tor that's known to select
  1978.  * entry guards badly. */
  1979. static int
  1980. remove_obsolete_entry_guards(void)
  1981. {
  1982.   int changed = 0, i;
  1983.   time_t this_month = start_of_month(time(NULL));
  1984.   for (i = 0; i < smartlist_len(entry_guards); ++i) {
  1985.     entry_guard_t *entry = smartlist_get(entry_guards, i);
  1986.     const char *ver = entry->chosen_by_version;
  1987.     const char *msg = NULL;
  1988.     tor_version_t v;
  1989.     int version_is_bad = 0, date_is_bad = 0;
  1990.     if (!ver) {
  1991.       msg = "does not say what version of Tor it was selected by";
  1992.       version_is_bad = 1;
  1993.     } else if (tor_version_parse(ver, &v)) {
  1994.       msg = "does not seem to be from any recognized version of Tor";
  1995.       version_is_bad = 1;
  1996.     } else if ((tor_version_as_new_as(ver, "0.1.0.10-alpha") &&
  1997.                 !tor_version_as_new_as(ver, "0.1.2.16-dev")) ||
  1998.                (tor_version_as_new_as(ver, "0.2.0.0-alpha") &&
  1999.                 !tor_version_as_new_as(ver, "0.2.0.6-alpha"))) {
  2000.       msg = "was selected without regard for guard bandwidth";
  2001.       version_is_bad = 1;
  2002.     } else if (entry->chosen_on_date + 3600*24*35 < this_month) {
  2003.       /* It's been more than a month, and probably more like two since
  2004.        * chosen_on_date is clipped to the beginning of its month. */
  2005.       msg = "was selected several months ago";
  2006.       date_is_bad = 1;
  2007.     }
  2008.     if (version_is_bad || date_is_bad) { /* we need to drop it */
  2009.       char dbuf[HEX_DIGEST_LEN+1];
  2010.       tor_assert(msg);
  2011.       base16_encode(dbuf, sizeof(dbuf), entry->identity, DIGEST_LEN);
  2012.       log_fn(version_is_bad ? LOG_NOTICE : LOG_INFO, LD_CIRC,
  2013.              "Entry guard '%s' (%s) %s. (Version=%s.) Replacing it.",
  2014.              entry->nickname, dbuf, msg, ver?escaped(ver):"none");
  2015.       control_event_guard(entry->nickname, entry->identity, "DROPPED");
  2016.       entry_guard_free(entry);
  2017.       smartlist_del_keeporder(entry_guards, i--);
  2018.       log_entry_guards(LOG_INFO);
  2019.       changed = 1;
  2020.     }
  2021.   }
  2022.   return changed ? 1 : 0;
  2023. }
  2024. /** Remove all entry guards that have been down or unlisted for so
  2025.  * long that we don't think they'll come up again. Return 1 if we
  2026.  * removed any, or 0 if we did nothing. */
  2027. static int
  2028. remove_dead_entry_guards(void)
  2029. {
  2030.   char dbuf[HEX_DIGEST_LEN+1];
  2031.   char tbuf[ISO_TIME_LEN+1];
  2032.   time_t now = time(NULL);
  2033.   int i;
  2034.   int changed = 0;
  2035.   for (i = 0; i < smartlist_len(entry_guards); ) {
  2036.     entry_guard_t *entry = smartlist_get(entry_guards, i);
  2037.     if (entry->bad_since &&
  2038.         entry->bad_since + ENTRY_GUARD_REMOVE_AFTER < now) {
  2039.       base16_encode(dbuf, sizeof(dbuf), entry->identity, DIGEST_LEN);
  2040.       format_local_iso_time(tbuf, entry->bad_since);
  2041.       log_info(LD_CIRC, "Entry guard '%s' (%s) has been down or unlisted "
  2042.                "since %s local time; removing.",
  2043.                entry->nickname, dbuf, tbuf);
  2044.       control_event_guard(entry->nickname, entry->identity, "DROPPED");
  2045.       entry_guard_free(entry);
  2046.       smartlist_del_keeporder(entry_guards, i);
  2047.       log_entry_guards(LOG_INFO);
  2048.       changed = 1;
  2049.     } else
  2050.       ++i;
  2051.   }
  2052.   return changed ? 1 : 0;
  2053. }
  2054. /** A new directory or router-status has arrived; update the down/listed
  2055.  * status of the entry guards.
  2056.  *
  2057.  * An entry is 'down' if the directory lists it as nonrunning.
  2058.  * An entry is 'unlisted' if the directory doesn't include it.
  2059.  *
  2060.  * Don't call this on startup; only on a fresh download. Otherwise we'll
  2061.  * think that things are unlisted.
  2062.  */
  2063. void
  2064. entry_guards_compute_status(void)
  2065. {
  2066.   time_t now;
  2067.   int changed = 0;
  2068.   int severity = LOG_DEBUG;
  2069.   or_options_t *options;
  2070.   digestmap_t *reasons;
  2071.   if (! entry_guards)
  2072.     return;
  2073.   options = get_options();
  2074.   now = time(NULL);
  2075.   reasons = digestmap_new();
  2076.   SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry)
  2077.     {
  2078.       routerinfo_t *r = router_get_by_digest(entry->identity);
  2079.       const char *reason = NULL;
  2080.       if (entry_guard_set_status(entry, r, now, options, &reason))
  2081.         changed = 1;
  2082.       if (entry->bad_since)
  2083.         tor_assert(reason);
  2084.       if (reason)
  2085.         digestmap_set(reasons, entry->identity, (char*)reason);
  2086.     }
  2087.   SMARTLIST_FOREACH_END(entry);
  2088.   if (remove_dead_entry_guards())
  2089.     changed = 1;
  2090.   severity = changed ? LOG_DEBUG : LOG_INFO;
  2091.   if (changed) {
  2092.     SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) {
  2093.       const char *reason = digestmap_get(reasons, entry->identity);
  2094.       log_info(LD_CIRC, "Summary: Entry '%s' is %s, %s%s%s, and %s.",
  2095.                entry->nickname,
  2096.                entry->unreachable_since ? "unreachable" : "reachable",
  2097.                entry->bad_since ? "unusable" : "usable",
  2098.                reason ? ", ": "",
  2099.                reason ? reason : "",
  2100.                entry_is_live(entry, 0, 1, 0) ? "live" : "not live");
  2101.     } SMARTLIST_FOREACH_END(entry);
  2102.     log_info(LD_CIRC, "    (%d/%d entry guards are usable/new)",
  2103.              num_live_entry_guards(), smartlist_len(entry_guards));
  2104.     log_entry_guards(LOG_INFO);
  2105.     entry_guards_changed();
  2106.   }
  2107.   digestmap_free(reasons, NULL);
  2108. }
  2109. /** Called when a connection to an OR with the identity digest <b>digest</b>
  2110.  * is established (<b>succeeded</b>==1) or has failed (<b>succeeded</b>==0).
  2111.  * If the OR is an entry, change that entry's up/down status.
  2112.  * Return 0 normally, or -1 if we want to tear down the new connection.
  2113.  *
  2114.  * If <b>mark_relay_status</b>, also call router_set_status() on this
  2115.  * relay.
  2116.  *
  2117.  * XXX022 change succeeded and mark_relay_status into 'int flags'.
  2118.  */
  2119. int
  2120. entry_guard_register_connect_status(const char *digest, int succeeded,
  2121.                                     int mark_relay_status, time_t now)
  2122. {
  2123.   int changed = 0;
  2124.   int refuse_conn = 0;
  2125.   int first_contact = 0;
  2126.   entry_guard_t *entry = NULL;
  2127.   int idx = -1;
  2128.   char buf[HEX_DIGEST_LEN+1];
  2129.   if (! entry_guards)
  2130.     return 0;
  2131.   SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  2132.     {
  2133.       if (!memcmp(e->identity, digest, DIGEST_LEN)) {
  2134.         entry = e;
  2135.         idx = e_sl_idx;
  2136.         break;
  2137.       }
  2138.     });
  2139.   if (!entry)
  2140.     return 0;
  2141.   base16_encode(buf, sizeof(buf), entry->identity, DIGEST_LEN);
  2142.   if (succeeded) {
  2143.     if (entry->unreachable_since) {
  2144.       log_info(LD_CIRC, "Entry guard '%s' (%s) is now reachable again. Good.",
  2145.                entry->nickname, buf);
  2146.       entry->can_retry = 0;
  2147.       entry->unreachable_since = 0;
  2148.       entry->last_attempted = now;
  2149.       control_event_guard(entry->nickname, entry->identity, "UP");
  2150.       changed = 1;
  2151.     }
  2152.     if (!entry->made_contact) {
  2153.       entry->made_contact = 1;
  2154.       first_contact = changed = 1;
  2155.     }
  2156.   } else { /* ! succeeded */
  2157.     if (!entry->made_contact) {
  2158.       /* We've never connected to this one. */
  2159.       log_info(LD_CIRC,
  2160.                "Connection to never-contacted entry guard '%s' (%s) failed. "
  2161.                "Removing from the list. %d/%d entry guards usable/new.",
  2162.                entry->nickname, buf,
  2163.                num_live_entry_guards()-1, smartlist_len(entry_guards)-1);
  2164.       entry_guard_free(entry);
  2165.       smartlist_del_keeporder(entry_guards, idx);
  2166.       log_entry_guards(LOG_INFO);
  2167.       changed = 1;
  2168.     } else if (!entry->unreachable_since) {
  2169.       log_info(LD_CIRC, "Unable to connect to entry guard '%s' (%s). "
  2170.                "Marking as unreachable.", entry->nickname, buf);
  2171.       entry->unreachable_since = entry->last_attempted = now;
  2172.       control_event_guard(entry->nickname, entry->identity, "DOWN");
  2173.       changed = 1;
  2174.       entry->can_retry = 0; /* We gave it an early chance; no good. */
  2175.     } else {
  2176.       char tbuf[ISO_TIME_LEN+1];
  2177.       format_iso_time(tbuf, entry->unreachable_since);
  2178.       log_debug(LD_CIRC, "Failed to connect to unreachable entry guard "
  2179.                 "'%s' (%s).  It has been unreachable since %s.",
  2180.                 entry->nickname, buf, tbuf);
  2181.       entry->last_attempted = now;
  2182.       entry->can_retry = 0; /* We gave it an early chance; no good. */
  2183.     }
  2184.   }
  2185.   /* if the caller asked us to, also update the is_running flags for this
  2186.    * relay */
  2187.   if (mark_relay_status)
  2188.     router_set_status(digest, succeeded);
  2189.   if (first_contact) {
  2190.     /* We've just added a new long-term entry guard. Perhaps the network just
  2191.      * came back? We should give our earlier entries another try too,
  2192.      * and close this connection so we don't use it before we've given
  2193.      * the others a shot. */
  2194.     SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, {
  2195.         if (e == entry)
  2196.           break;
  2197.         if (e->made_contact) {
  2198.           routerinfo_t *r = entry_is_live(e, 0, 1, 1);
  2199.           if (r && e->unreachable_since) {
  2200.             refuse_conn = 1;
  2201.             e->can_retry = 1;
  2202.           }
  2203.         }
  2204.       });
  2205.     if (refuse_conn) {
  2206.       log_info(LD_CIRC,
  2207.                "Connected to new entry guard '%s' (%s). Marking earlier "
  2208.                "entry guards up. %d/%d entry guards usable/new.",
  2209.                entry->nickname, buf,
  2210.                num_live_entry_guards(), smartlist_len(entry_guards));
  2211.       log_entry_guards(LOG_INFO);
  2212.       changed = 1;
  2213.     }
  2214.   }
  2215.   if (changed)
  2216.     entry_guards_changed();
  2217.   return refuse_conn ? -1 : 0;
  2218. }
  2219. /** When we try to choose an entry guard, should we parse and add
  2220.  * config's EntryNodes first? */
  2221. static int should_add_entry_nodes = 0;
  2222. /** Called when the value of EntryNodes changes in our configuration. */
  2223. void
  2224. entry_nodes_should_be_added(void)
  2225. {
  2226.   log_info(LD_CIRC, "New EntryNodes config option detected. Will use.");
  2227.   should_add_entry_nodes = 1;
  2228. }
  2229. /** Add all nodes in EntryNodes that aren't currently guard nodes to the list
  2230.  * of guard nodes, at the front. */
  2231. static void
  2232. entry_guards_prepend_from_config(void)
  2233. {
  2234.   or_options_t *options = get_options();
  2235.   smartlist_t *entry_routers, *entry_fps;
  2236.   smartlist_t *old_entry_guards_on_list, *old_entry_guards_not_on_list;
  2237.   tor_assert(entry_guards);
  2238.   should_add_entry_nodes = 0;
  2239.   if (!options->EntryNodes) {
  2240.     /* It's possible that a controller set EntryNodes, thus making
  2241.      * should_add_entry_nodes set, then cleared it again, all before the
  2242.      * call to choose_random_entry() that triggered us. If so, just return.
  2243.      */
  2244.     return;
  2245.   }
  2246.   if (options->EntryNodes) {
  2247.     char *string = routerset_to_string(options->EntryNodes);
  2248.     log_info(LD_CIRC,"Adding configured EntryNodes '%s'.", string);
  2249.     tor_free(string);
  2250.   }
  2251.   entry_routers = smartlist_create();
  2252.   entry_fps = smartlist_create();
  2253.   old_entry_guards_on_list = smartlist_create();
  2254.   old_entry_guards_not_on_list = smartlist_create();
  2255.   /* Split entry guards into those on the list and those not. */
  2256.   /* XXXX022 Now that we allow countries and IP ranges in EntryNodes, this is
  2257.    *  potentially an enormous list. For now, we disable such values for
  2258.    *  EntryNodes in options_validate(); really, this wants a better solution.
  2259.    *  Perhaps we should do this calculation once whenever the list of routers
  2260.    *  changes or the entrynodes setting changes.
  2261.    */
  2262.   routerset_get_all_routers(entry_routers, options->EntryNodes, 0);
  2263.   SMARTLIST_FOREACH(entry_routers, routerinfo_t *, ri,
  2264.                     smartlist_add(entry_fps,ri->cache_info.identity_digest));
  2265.   SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, {
  2266.     if (smartlist_digest_isin(entry_fps, e->identity))
  2267.       smartlist_add(old_entry_guards_on_list, e);
  2268.     else
  2269.       smartlist_add(old_entry_guards_not_on_list, e);
  2270.   });
  2271.   /* Remove all currently configured entry guards from entry_routers. */
  2272.   SMARTLIST_FOREACH(entry_routers, routerinfo_t *, ri, {
  2273.     if (is_an_entry_guard(ri->cache_info.identity_digest)) {
  2274.       SMARTLIST_DEL_CURRENT(entry_routers, ri);
  2275.     }
  2276.   });
  2277.   /* Now build the new entry_guards list. */
  2278.   smartlist_clear(entry_guards);
  2279.   /* First, the previously configured guards that are in EntryNodes. */
  2280.   smartlist_add_all(entry_guards, old_entry_guards_on_list);
  2281.   /* Next, the rest of EntryNodes */
  2282.   SMARTLIST_FOREACH(entry_routers, routerinfo_t *, ri, {
  2283.     add_an_entry_guard(ri, 0);
  2284.   });
  2285.   /* Finally, the remaining EntryNodes, unless we're strict */
  2286.   if (options->StrictEntryNodes) {
  2287.     SMARTLIST_FOREACH(old_entry_guards_not_on_list, entry_guard_t *, e,
  2288.                       entry_guard_free(e));
  2289.   } else {
  2290.     smartlist_add_all(entry_guards, old_entry_guards_not_on_list);
  2291.   }
  2292.   smartlist_free(entry_routers);
  2293.   smartlist_free(entry_fps);
  2294.   smartlist_free(old_entry_guards_on_list);
  2295.   smartlist_free(old_entry_guards_not_on_list);
  2296.   entry_guards_changed();
  2297. }
  2298. /** Return 1 if we're fine adding arbitrary routers out of the
  2299.  * directory to our entry guard list. Else return 0. */
  2300. int
  2301. entry_list_can_grow(or_options_t *options)
  2302. {
  2303.   if (options->StrictEntryNodes)
  2304.     return 0;
  2305.   if (options->UseBridges)
  2306.     return 0;
  2307.   return 1;
  2308. }
  2309. /** Pick a live (up and listed) entry guard from entry_guards. If
  2310.  * <b>state</b> is non-NULL, this is for a specific circuit --
  2311.  * make sure not to pick this circuit's exit or any node in the
  2312.  * exit's family. If <b>state</b> is NULL, we're looking for a random
  2313.  * guard (likely a bridge). */
  2314. routerinfo_t *
  2315. choose_random_entry(cpath_build_state_t *state)
  2316. {
  2317.   or_options_t *options = get_options();
  2318.   smartlist_t *live_entry_guards = smartlist_create();
  2319.   smartlist_t *exit_family = smartlist_create();
  2320.   routerinfo_t *chosen_exit = state?build_state_get_exit_router(state) : NULL;
  2321.   routerinfo_t *r = NULL;
  2322.   int need_uptime = state ? state->need_uptime : 0;
  2323.   int need_capacity = state ? state->need_capacity : 0;
  2324.   int consider_exit_family = 0;
  2325.   if (chosen_exit) {
  2326.     smartlist_add(exit_family, chosen_exit);
  2327.     routerlist_add_family(exit_family, chosen_exit);
  2328.     consider_exit_family = 1;
  2329.   }
  2330.   if (!entry_guards)
  2331.     entry_guards = smartlist_create();
  2332.   if (should_add_entry_nodes)
  2333.     entry_guards_prepend_from_config();
  2334.   if (entry_list_can_grow(options) &&
  2335.       (! entry_guards ||
  2336.        smartlist_len(entry_guards) < options->NumEntryGuards))
  2337.     pick_entry_guards();
  2338.  retry:
  2339.   smartlist_clear(live_entry_guards);
  2340.   SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
  2341.     {
  2342.       r = entry_is_live(entry, need_uptime, need_capacity, 0);
  2343.       if (r && (!consider_exit_family || !smartlist_isin(exit_family, r))) {
  2344.         smartlist_add(live_entry_guards, r);
  2345.         if (!entry->made_contact) {
  2346.           /* Always start with the first not-yet-contacted entry
  2347.            * guard. Otherwise we might add several new ones, pick
  2348.            * the second new one, and now we've expanded our entry
  2349.            * guard list without needing to. */
  2350.           goto choose_and_finish;
  2351.         }
  2352.         if (smartlist_len(live_entry_guards) >= options->NumEntryGuards)
  2353.           break; /* we have enough */
  2354.       }
  2355.     });
  2356.   /* Try to have at least 2 choices available. This way we don't
  2357.    * get stuck with a single live-but-crummy entry and just keep
  2358.    * using him.
  2359.    * (We might get 2 live-but-crummy entry guards, but so be it.) */
  2360.   if (smartlist_len(live_entry_guards) < 2) {
  2361.     if (entry_list_can_grow(options)) {
  2362.       /* still no? try adding a new entry then */
  2363.       /* XXX if guard doesn't imply fast and stable, then we need
  2364.        * to tell add_an_entry_guard below what we want, or it might
  2365.        * be a long time til we get it. -RD */
  2366.       r = add_an_entry_guard(NULL, 0);
  2367.       if (r) {
  2368.         entry_guards_changed();
  2369.         /* XXX we start over here in case the new node we added shares
  2370.          * a family with our exit node. There's a chance that we'll just
  2371.          * load up on entry guards here, if the network we're using is
  2372.          * one big family. Perhaps we should teach add_an_entry_guard()
  2373.          * to understand nodes-to-avoid-if-possible? -RD */
  2374.         goto retry;
  2375.       }
  2376.     }
  2377.     if (!r && need_uptime) {
  2378.       need_uptime = 0; /* try without that requirement */
  2379.       goto retry;
  2380.     }
  2381.     if (!r && need_capacity) {
  2382.       /* still no? last attempt, try without requiring capacity */
  2383.       need_capacity = 0;
  2384.       goto retry;
  2385.     }
  2386.     if (!r && !entry_list_can_grow(options) && consider_exit_family) {
  2387.       /* still no? if we're using bridges or have strictentrynodes
  2388.        * set, and our chosen exit is in the same family as all our
  2389.        * bridges/entry guards, then be flexible about families. */
  2390.       consider_exit_family = 0;
  2391.       goto retry;
  2392.     }
  2393.     /* live_entry_guards may be empty below. Oh well, we tried. */
  2394.   }
  2395.  choose_and_finish:
  2396.   if (entry_list_can_grow(options)) {
  2397.     /* We choose uniformly at random here, because choose_good_entry_server()
  2398.      * already weights its choices by bandwidth, so we don't want to
  2399.      * *double*-weight our guard selection. */
  2400.     r = smartlist_choose(live_entry_guards);
  2401.   } else {
  2402.     /* We need to weight by bandwidth, because our bridges or entryguards
  2403.      * were not already selected proportional to their bandwidth. */
  2404.     r = routerlist_sl_choose_by_bandwidth(live_entry_guards, WEIGHT_FOR_GUARD);
  2405.   }
  2406.   smartlist_free(live_entry_guards);
  2407.   smartlist_free(exit_family);
  2408.   return r;
  2409. }
  2410. /** Helper: Return the start of the month containing <b>time</b>. */
  2411. static time_t
  2412. start_of_month(time_t now)
  2413. {
  2414.   struct tm tm;
  2415.   tor_gmtime_r(&now, &tm);
  2416.   tm.tm_sec = 0;
  2417.   tm.tm_min = 0;
  2418.   tm.tm_hour = 0;
  2419.   tm.tm_mday = 1;
  2420.   return tor_timegm(&tm);
  2421. }
  2422. /** Parse <b>state</b> and learn about the entry guards it describes.
  2423.  * If <b>set</b> is true, and there are no errors, replace the global
  2424.  * entry_list with what we find.
  2425.  * On success, return 0. On failure, alloc into *<b>msg</b> a string
  2426.  * describing the error, and return -1.
  2427.  */
  2428. int
  2429. entry_guards_parse_state(or_state_t *state, int set, char **msg)
  2430. {
  2431.   entry_guard_t *node = NULL;
  2432.   smartlist_t *new_entry_guards = smartlist_create();
  2433.   config_line_t *line;
  2434.   time_t now = time(NULL);
  2435.   const char *state_version = state->TorVersion;
  2436.   digestmap_t *added_by = digestmap_new();
  2437.   *msg = NULL;
  2438.   for (line = state->EntryGuards; line; line = line->next) {
  2439.     if (!strcasecmp(line->key, "EntryGuard")) {
  2440.       smartlist_t *args = smartlist_create();
  2441.       node = tor_malloc_zero(sizeof(entry_guard_t));
  2442.       /* all entry guards on disk have been contacted */
  2443.       node->made_contact = 1;
  2444.       smartlist_add(new_entry_guards, node);
  2445.       smartlist_split_string(args, line->value, " ",
  2446.                              SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  2447.       if (smartlist_len(args)<2) {
  2448.         *msg = tor_strdup("Unable to parse entry nodes: "
  2449.                           "Too few arguments to EntryGuard");
  2450.       } else if (!is_legal_nickname(smartlist_get(args,0))) {
  2451.         *msg = tor_strdup("Unable to parse entry nodes: "
  2452.                           "Bad nickname for EntryGuard");
  2453.       } else {
  2454.         strlcpy(node->nickname, smartlist_get(args,0), MAX_NICKNAME_LEN+1);
  2455.         if (base16_decode(node->identity, DIGEST_LEN, smartlist_get(args,1),
  2456.                           strlen(smartlist_get(args,1)))<0) {
  2457.           *msg = tor_strdup("Unable to parse entry nodes: "
  2458.                             "Bad hex digest for EntryGuard");
  2459.         }
  2460.       }
  2461.       SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
  2462.       smartlist_free(args);
  2463.       if (*msg)
  2464.         break;
  2465.     } else if (!strcasecmp(line->key, "EntryGuardDownSince") ||
  2466.                !strcasecmp(line->key, "EntryGuardUnlistedSince")) {
  2467.       time_t when;
  2468.       time_t last_try = 0;
  2469.       if (!node) {
  2470.         *msg = tor_strdup("Unable to parse entry nodes: "
  2471.                "EntryGuardDownSince/UnlistedSince without EntryGuard");
  2472.         break;
  2473.       }
  2474.       if (parse_iso_time(line->value, &when)<0) {
  2475.         *msg = tor_strdup("Unable to parse entry nodes: "
  2476.                           "Bad time in EntryGuardDownSince/UnlistedSince");
  2477.         break;
  2478.       }
  2479.       if (when > now) {
  2480.         /* It's a bad idea to believe info in the future: you can wind
  2481.          * up with timeouts that aren't allowed to happen for years. */
  2482.         continue;
  2483.       }
  2484.       if (strlen(line->value) >= ISO_TIME_LEN+ISO_TIME_LEN+1) {
  2485.         /* ignore failure */
  2486.         (void) parse_iso_time(line->value+ISO_TIME_LEN+1, &last_try);
  2487.       }
  2488.       if (!strcasecmp(line->key, "EntryGuardDownSince")) {
  2489.         node->unreachable_since = when;
  2490.         node->last_attempted = last_try;
  2491.       } else {
  2492.         node->bad_since = when;
  2493.       }
  2494.     } else if (!strcasecmp(line->key, "EntryGuardAddedBy")) {
  2495.       char d[DIGEST_LEN];
  2496.       /* format is digest version date */
  2497.       if (strlen(line->value) < HEX_DIGEST_LEN+1+1+1+ISO_TIME_LEN) {
  2498.         log_warn(LD_BUG, "EntryGuardAddedBy line is not long enough.");
  2499.         continue;
  2500.       }
  2501.       if (base16_decode(d, sizeof(d), line->value, HEX_DIGEST_LEN)<0 ||
  2502.           line->value[HEX_DIGEST_LEN] != ' ') {
  2503.         log_warn(LD_BUG, "EntryGuardAddedBy line %s does not begin with "
  2504.                  "hex digest", escaped(line->value));
  2505.         continue;
  2506.       }
  2507.       digestmap_set(added_by, d, tor_strdup(line->value+HEX_DIGEST_LEN+1));
  2508.     } else {
  2509.       log_warn(LD_BUG, "Unexpected key %s", line->key);
  2510.     }
  2511.   }
  2512.   SMARTLIST_FOREACH(new_entry_guards, entry_guard_t *, e,
  2513.    {
  2514.      char *sp;
  2515.      char *val = digestmap_get(added_by, e->identity);
  2516.      if (val && (sp = strchr(val, ' '))) {
  2517.        time_t when;
  2518.        *sp++ = '';
  2519.        if (parse_iso_time(sp, &when)<0) {
  2520.          log_warn(LD_BUG, "Can't read time %s in EntryGuardAddedBy", sp);
  2521.        } else {
  2522.          e->chosen_by_version = tor_strdup(val);
  2523.          e->chosen_on_date = when;
  2524.        }
  2525.      } else {
  2526.        if (state_version) {
  2527.          e->chosen_by_version = tor_strdup(state_version);
  2528.          e->chosen_on_date = start_of_month(time(NULL));
  2529.        }
  2530.      }
  2531.    });
  2532.   if (*msg || !set) {
  2533.     SMARTLIST_FOREACH(new_entry_guards, entry_guard_t *, e,
  2534.                       entry_guard_free(e));
  2535.     smartlist_free(new_entry_guards);
  2536.   } else { /* !err && set */
  2537.     if (entry_guards) {
  2538.       SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  2539.                         entry_guard_free(e));
  2540.       smartlist_free(entry_guards);
  2541.     }
  2542.     entry_guards = new_entry_guards;
  2543.     entry_guards_dirty = 0;
  2544.     /* XXX022 hand new_entry_guards to this func, and move it up a
  2545.      * few lines, so we don't have to re-dirty it */
  2546.     if (remove_obsolete_entry_guards())
  2547.       entry_guards_dirty = 1;
  2548.   }
  2549.   digestmap_free(added_by, _tor_free);
  2550.   return *msg ? -1 : 0;
  2551. }
  2552. /** Our list of entry guards has changed, or some element of one
  2553.  * of our entry guards has changed. Write the changes to disk within
  2554.  * the next few minutes.
  2555.  */
  2556. static void
  2557. entry_guards_changed(void)
  2558. {
  2559.   time_t when;
  2560.   entry_guards_dirty = 1;
  2561.   /* or_state_save() will call entry_guards_update_state(). */
  2562.   when = get_options()->AvoidDiskWrites ? time(NULL) + 3600 : time(NULL)+600;
  2563.   or_state_mark_dirty(get_or_state(), when);
  2564. }
  2565. /** If the entry guard info has not changed, do nothing and return.
  2566.  * Otherwise, free the EntryGuards piece of <b>state</b> and create
  2567.  * a new one out of the global entry_guards list, and then mark
  2568.  * <b>state</b> dirty so it will get saved to disk.
  2569.  */
  2570. void
  2571. entry_guards_update_state(or_state_t *state)
  2572. {
  2573.   config_line_t **next, *line;
  2574.   if (! entry_guards_dirty)
  2575.     return;
  2576.   config_free_lines(state->EntryGuards);
  2577.   next = &state->EntryGuards;
  2578.   *next = NULL;
  2579.   if (!entry_guards)
  2580.     entry_guards = smartlist_create();
  2581.   SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  2582.     {
  2583.       char dbuf[HEX_DIGEST_LEN+1];
  2584.       if (!e->made_contact)
  2585.         continue; /* don't write this one to disk */
  2586.       *next = line = tor_malloc_zero(sizeof(config_line_t));
  2587.       line->key = tor_strdup("EntryGuard");
  2588.       line->value = tor_malloc(HEX_DIGEST_LEN+MAX_NICKNAME_LEN+2);
  2589.       base16_encode(dbuf, sizeof(dbuf), e->identity, DIGEST_LEN);
  2590.       tor_snprintf(line->value,HEX_DIGEST_LEN+MAX_NICKNAME_LEN+2,
  2591.                    "%s %s", e->nickname, dbuf);
  2592.       next = &(line->next);
  2593.       if (e->unreachable_since) {
  2594.         *next = line = tor_malloc_zero(sizeof(config_line_t));
  2595.         line->key = tor_strdup("EntryGuardDownSince");
  2596.         line->value = tor_malloc(ISO_TIME_LEN+1+ISO_TIME_LEN+1);
  2597.         format_iso_time(line->value, e->unreachable_since);
  2598.         if (e->last_attempted) {
  2599.           line->value[ISO_TIME_LEN] = ' ';
  2600.           format_iso_time(line->value+ISO_TIME_LEN+1, e->last_attempted);
  2601.         }
  2602.         next = &(line->next);
  2603.       }
  2604.       if (e->bad_since) {
  2605.         *next = line = tor_malloc_zero(sizeof(config_line_t));
  2606.         line->key = tor_strdup("EntryGuardUnlistedSince");
  2607.         line->value = tor_malloc(ISO_TIME_LEN+1);
  2608.         format_iso_time(line->value, e->bad_since);
  2609.         next = &(line->next);
  2610.       }
  2611.       if (e->chosen_on_date && e->chosen_by_version &&
  2612.           !strchr(e->chosen_by_version, ' ')) {
  2613.         char d[HEX_DIGEST_LEN+1];
  2614.         char t[ISO_TIME_LEN+1];
  2615.         size_t val_len;
  2616.         *next = line = tor_malloc_zero(sizeof(config_line_t));
  2617.         line->key = tor_strdup("EntryGuardAddedBy");
  2618.         val_len = (HEX_DIGEST_LEN+1+strlen(e->chosen_by_version)
  2619.                    +1+ISO_TIME_LEN+1);
  2620.         line->value = tor_malloc(val_len);
  2621.         base16_encode(d, sizeof(d), e->identity, DIGEST_LEN);
  2622.         format_iso_time(t, e->chosen_on_date);
  2623.         tor_snprintf(line->value, val_len, "%s %s %s",
  2624.                      d, e->chosen_by_version, t);
  2625.         next = &(line->next);
  2626.       }
  2627.     });
  2628.   if (!get_options()->AvoidDiskWrites)
  2629.     or_state_mark_dirty(get_or_state(), 0);
  2630.   entry_guards_dirty = 0;
  2631. }
  2632. /** If <b>question</b> is the string "entry-guards", then dump
  2633.  * to *<b>answer</b> a newly allocated string describing all of
  2634.  * the nodes in the global entry_guards list. See control-spec.txt
  2635.  * for details.
  2636.  * For backward compatibility, we also handle the string "helper-nodes".
  2637.  * */
  2638. int
  2639. getinfo_helper_entry_guards(control_connection_t *conn,
  2640.                             const char *question, char **answer)
  2641. {
  2642.   int use_long_names = conn->use_long_names;
  2643.   if (!strcmp(question,"entry-guards") ||
  2644.       !strcmp(question,"helper-nodes")) {
  2645.     smartlist_t *sl = smartlist_create();
  2646.     char tbuf[ISO_TIME_LEN+1];
  2647.     char nbuf[MAX_VERBOSE_NICKNAME_LEN+1];
  2648.     if (!entry_guards)
  2649.       entry_guards = smartlist_create();
  2650.     SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  2651.       {
  2652.         size_t len = MAX_VERBOSE_NICKNAME_LEN+ISO_TIME_LEN+32;
  2653.         char *c = tor_malloc(len);
  2654.         const char *status = NULL;
  2655.         time_t when = 0;
  2656.         if (!e->made_contact) {
  2657.           status = "never-connected";
  2658.         } else if (e->bad_since) {
  2659.           when = e->bad_since;
  2660.           status = "unusable";
  2661.         } else {
  2662.           status = "up";
  2663.         }
  2664.         if (use_long_names) {
  2665.           routerinfo_t *ri = router_get_by_digest(e->identity);
  2666.           if (ri) {
  2667.             router_get_verbose_nickname(nbuf, ri);
  2668.           } else {
  2669.             nbuf[0] = '$';
  2670.             base16_encode(nbuf+1, sizeof(nbuf)-1, e->identity, DIGEST_LEN);
  2671.             /* e->nickname field is not very reliable if we don't know about
  2672.              * this router any longer; don't include it. */
  2673.           }
  2674.         } else {
  2675.           base16_encode(nbuf, sizeof(nbuf), e->identity, DIGEST_LEN);
  2676.         }
  2677.         if (when) {
  2678.           format_iso_time(tbuf, when);
  2679.           tor_snprintf(c, len, "%s %s %sn", nbuf, status, tbuf);
  2680.         } else {
  2681.           tor_snprintf(c, len, "%s %sn", nbuf, status);
  2682.         }
  2683.         smartlist_add(sl, c);
  2684.       });
  2685.     *answer = smartlist_join_strings(sl, "", 0, NULL);
  2686.     SMARTLIST_FOREACH(sl, char *, c, tor_free(c));
  2687.     smartlist_free(sl);
  2688.   }
  2689.   return 0;
  2690. }
  2691. /** Information about a configured bridge. Currently this just matches the
  2692.  * ones in the torrc file, but one day we may be able to learn about new
  2693.  * bridges on our own, and remember them in the state file. */
  2694. typedef struct {
  2695.   /** Address of the bridge. */
  2696.   tor_addr_t addr;
  2697.   /** TLS port for the bridge. */
  2698.   uint16_t port;
  2699.   /** Expected identity digest, or all zero bytes if we don't know what the
  2700.    * digest should be. */
  2701.   char identity[DIGEST_LEN];
  2702.   /** When should we next try to fetch a descriptor for this bridge? */
  2703.   download_status_t fetch_status;
  2704. } bridge_info_t;
  2705. /** A list of configured bridges. Whenever we actually get a descriptor
  2706.  * for one, we add it as an entry guard. */
  2707. static smartlist_t *bridge_list = NULL;
  2708. /** Initialize the bridge list to empty, creating it if needed. */
  2709. void
  2710. clear_bridge_list(void)
  2711. {
  2712.   if (!bridge_list)
  2713.     bridge_list = smartlist_create();
  2714.   SMARTLIST_FOREACH(bridge_list, bridge_info_t *, b, tor_free(b));
  2715.   smartlist_clear(bridge_list);
  2716. }
  2717. /** Return a bridge pointer if <b>ri</b> is one of our known bridges
  2718.  * (either by comparing keys if possible, else by comparing addr/port).
  2719.  * Else return NULL. */
  2720. static bridge_info_t *
  2721. routerinfo_get_configured_bridge(routerinfo_t *ri)
  2722. {
  2723.   if (!bridge_list)
  2724.     return NULL;
  2725.   SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge)
  2726.     {
  2727.       if (tor_digest_is_zero(bridge->identity) &&
  2728.           tor_addr_eq_ipv4h(&bridge->addr, ri->addr) &&
  2729.           bridge->port == ri->or_port)
  2730.         return bridge;
  2731.       if (!memcmp(bridge->identity, ri->cache_info.identity_digest,
  2732.                   DIGEST_LEN))
  2733.         return bridge;
  2734.     }
  2735.   SMARTLIST_FOREACH_END(bridge);
  2736.   return NULL;
  2737. }
  2738. /** Return 1 if <b>ri</b> is one of our known bridges, else 0. */
  2739. int
  2740. routerinfo_is_a_configured_bridge(routerinfo_t *ri)
  2741. {
  2742.   return routerinfo_get_configured_bridge(ri) ? 1 : 0;
  2743. }
  2744. /** Remember a new bridge at <b>addr</b>:<b>port</b>. If <b>digest</b>
  2745.  * is set, it tells us the identity key too. */
  2746. void
  2747. bridge_add_from_config(const tor_addr_t *addr, uint16_t port, char *digest)
  2748. {
  2749.   bridge_info_t *b = tor_malloc_zero(sizeof(bridge_info_t));
  2750.   tor_addr_copy(&b->addr, addr);
  2751.   b->port = port;
  2752.   if (digest)
  2753.     memcpy(b->identity, digest, DIGEST_LEN);
  2754.   b->fetch_status.schedule = DL_SCHED_BRIDGE;
  2755.   if (!bridge_list)
  2756.     bridge_list = smartlist_create();
  2757.   smartlist_add(bridge_list, b);
  2758. }
  2759. /** If <b>digest</b> is one of our known bridges, return it. */
  2760. static bridge_info_t *
  2761. find_bridge_by_digest(const char *digest)
  2762. {
  2763.   SMARTLIST_FOREACH(bridge_list, bridge_info_t *, bridge,
  2764.     {
  2765.       if (!memcmp(bridge->identity, digest, DIGEST_LEN))
  2766.         return bridge;
  2767.     });
  2768.   return NULL;
  2769. }
  2770. /** We need to ask <b>bridge</b> for its server descriptor. <b>address</b>
  2771.  * is a helpful string describing this bridge. */
  2772. static void
  2773. launch_direct_bridge_descriptor_fetch(bridge_info_t *bridge)
  2774. {
  2775.   char *address;
  2776.   if (connection_get_by_type_addr_port_purpose(
  2777.       CONN_TYPE_DIR, &bridge->addr, bridge->port,
  2778.       DIR_PURPOSE_FETCH_SERVERDESC))
  2779.     return; /* it's already on the way */
  2780.   address = tor_dup_addr(&bridge->addr);
  2781.   directory_initiate_command(address, &bridge->addr,
  2782.                              bridge->port, 0,
  2783.                              0, /* does not matter */
  2784.                              1, bridge->identity,
  2785.                              DIR_PURPOSE_FETCH_SERVERDESC,
  2786.                              ROUTER_PURPOSE_BRIDGE,
  2787.                              0, "authority.z", NULL, 0, 0);
  2788.   tor_free(address);
  2789. }
  2790. /** Fetching the bridge descriptor from the bridge authority returned a
  2791.  * "not found". Fall back to trying a direct fetch. */
  2792. void
  2793. retry_bridge_descriptor_fetch_directly(const char *digest)
  2794. {
  2795.   bridge_info_t *bridge = find_bridge_by_digest(digest);
  2796.   if (!bridge)
  2797.     return; /* not found? oh well. */
  2798.   launch_direct_bridge_descriptor_fetch(bridge);
  2799. }
  2800. /** For each bridge in our list for which we don't currently have a
  2801.  * descriptor, fetch a new copy of its descriptor -- either directly
  2802.  * from the bridge or via a bridge authority. */
  2803. void
  2804. fetch_bridge_descriptors(time_t now)
  2805. {
  2806.   or_options_t *options = get_options();
  2807.   int num_bridge_auths = get_n_authorities(BRIDGE_AUTHORITY);
  2808.   int ask_bridge_directly;
  2809.   int can_use_bridge_authority;
  2810.   if (!bridge_list)
  2811.     return;
  2812.   SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge)
  2813.     {
  2814.       if (!download_status_is_ready(&bridge->fetch_status, now,
  2815.                                     IMPOSSIBLE_TO_DOWNLOAD))
  2816.         continue; /* don't bother, no need to retry yet */
  2817.       /* schedule another fetch as if this one will fail, in case it does */
  2818.       download_status_failed(&bridge->fetch_status, 0);
  2819.       can_use_bridge_authority = !tor_digest_is_zero(bridge->identity) &&
  2820.                                  num_bridge_auths;
  2821.       ask_bridge_directly = !can_use_bridge_authority ||
  2822.                             !options->UpdateBridgesFromAuthority;
  2823.       log_debug(LD_DIR, "ask_bridge_directly=%d (%d, %d, %d)",
  2824.                 ask_bridge_directly, tor_digest_is_zero(bridge->identity),
  2825.                 !options->UpdateBridgesFromAuthority, !num_bridge_auths);
  2826.       if (ask_bridge_directly &&
  2827.           !fascist_firewall_allows_address_or(&bridge->addr, bridge->port)) {
  2828.         log_notice(LD_DIR, "Bridge at '%s:%d' isn't reachable by our "
  2829.                    "firewall policy. %s.", fmt_addr(&bridge->addr),
  2830.                    bridge->port,
  2831.                    can_use_bridge_authority ?
  2832.                      "Asking bridge authority instead" : "Skipping");
  2833.         if (can_use_bridge_authority)
  2834.           ask_bridge_directly = 0;
  2835.         else
  2836.           continue;
  2837.       }
  2838.       if (ask_bridge_directly) {
  2839.         /* we need to ask the bridge itself for its descriptor. */
  2840.         launch_direct_bridge_descriptor_fetch(bridge);
  2841.       } else {
  2842.         /* We have a digest and we want to ask an authority. We could
  2843.          * combine all the requests into one, but that may give more
  2844.          * hints to the bridge authority than we want to give. */
  2845.         char resource[10 + HEX_DIGEST_LEN];
  2846.         memcpy(resource, "fp/", 3);
  2847.         base16_encode(resource+3, HEX_DIGEST_LEN+1,
  2848.                       bridge->identity, DIGEST_LEN);
  2849.         memcpy(resource+3+HEX_DIGEST_LEN, ".z", 3);
  2850.         log_info(LD_DIR, "Fetching bridge info '%s' from bridge authority.",
  2851.                  resource);
  2852.         directory_get_from_dirserver(DIR_PURPOSE_FETCH_SERVERDESC,
  2853.                 ROUTER_PURPOSE_BRIDGE, resource, 0);
  2854.       }
  2855.     }
  2856.   SMARTLIST_FOREACH_END(bridge);
  2857. }
  2858. /** We just learned a descriptor for a bridge. See if that
  2859.  * digest is in our entry guard list, and add it if not. */
  2860. void
  2861. learned_bridge_descriptor(routerinfo_t *ri, int from_cache)
  2862. {
  2863.   tor_assert(ri);
  2864.   tor_assert(ri->purpose == ROUTER_PURPOSE_BRIDGE);
  2865.   if (get_options()->UseBridges) {
  2866.     int first = !any_bridge_descriptors_known();
  2867.     bridge_info_t *bridge = routerinfo_get_configured_bridge(ri);
  2868.     time_t now = time(NULL);
  2869.     ri->is_running = 1;
  2870.     if (bridge) { /* if we actually want to use this one */
  2871.       /* it's here; schedule its re-fetch for a long time from now. */
  2872.       if (!from_cache)
  2873.         download_status_reset(&bridge->fetch_status);
  2874.       add_an_entry_guard(ri, 1);
  2875.       log_notice(LD_DIR, "new bridge descriptor '%s' (%s)", ri->nickname,
  2876.                  from_cache ? "cached" : "fresh");
  2877.       if (first)
  2878.         routerlist_retry_directory_downloads(now);
  2879.     }
  2880.   }
  2881. }
  2882. /** Return 1 if any of our entry guards have descriptors that
  2883.  * are marked with purpose 'bridge' and are running. Else return 0.
  2884.  *
  2885.  * We use this function to decide if we're ready to start building
  2886.  * circuits through our bridges, or if we need to wait until the
  2887.  * directory "server/authority" requests finish. */
  2888. int
  2889. any_bridge_descriptors_known(void)
  2890. {
  2891.   tor_assert(get_options()->UseBridges);
  2892.   return choose_random_entry(NULL)!=NULL ? 1 : 0;
  2893. }
  2894. /** Return 1 if there are any directory conns fetching bridge descriptors
  2895.  * that aren't marked for close. We use this to guess if we should tell
  2896.  * the controller that we have a problem. */
  2897. int
  2898. any_pending_bridge_descriptor_fetches(void)
  2899. {
  2900.   smartlist_t *conns = get_connection_array();
  2901.   SMARTLIST_FOREACH(conns, connection_t *, conn,
  2902.   {
  2903.     if (conn->type == CONN_TYPE_DIR &&
  2904.         conn->purpose == DIR_PURPOSE_FETCH_SERVERDESC &&
  2905.         TO_DIR_CONN(conn)->router_purpose == ROUTER_PURPOSE_BRIDGE &&
  2906.         !conn->marked_for_close &&
  2907.         conn->linked && !conn->linked_conn->marked_for_close) {
  2908.       log_debug(LD_DIR, "found one: %s", conn->address);
  2909.       return 1;
  2910.     }
  2911.   });
  2912.   return 0;
  2913. }
  2914. /** Return 1 if we have at least one descriptor for a bridge and
  2915.  * all descriptors we know are down. Else return 0. If <b>act</b> is
  2916.  * 1, then mark the down bridges up; else just observe and report. */
  2917. static int
  2918. bridges_retry_helper(int act)
  2919. {
  2920.   routerinfo_t *ri;
  2921.   int any_known = 0;
  2922.   int any_running = 0;
  2923.   if (!entry_guards)
  2924.     entry_guards = smartlist_create();
  2925.   SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  2926.     {
  2927.       ri = router_get_by_digest(e->identity);
  2928.       if (ri && ri->purpose == ROUTER_PURPOSE_BRIDGE) {
  2929.         any_known = 1;
  2930.         if (ri->is_running)
  2931.           any_running = 1; /* some bridge is both known and running */
  2932.         else if (act) { /* mark it for retry */
  2933.           ri->is_running = 1;
  2934.           e->can_retry = 1;
  2935.           e->bad_since = 0;
  2936.         }
  2937.       }
  2938.     });
  2939.   log_debug(LD_DIR, "any_known %d, any_running %d", any_known, any_running);
  2940.   return any_known && !any_running;
  2941. }
  2942. /** Do we know any descriptors for our bridges, and are they all
  2943.  * down? */
  2944. int
  2945. bridges_known_but_down(void)
  2946. {
  2947.   return bridges_retry_helper(0);
  2948. }
  2949. /** Mark all down known bridges up. */
  2950. void
  2951. bridges_retry_all(void)
  2952. {
  2953.   bridges_retry_helper(1);
  2954. }
  2955. /** Release all storage held by the list of entry guards and related
  2956.  * memory structs. */
  2957. void
  2958. entry_guards_free_all(void)
  2959. {
  2960.   if (entry_guards) {
  2961.     SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
  2962.                       entry_guard_free(e));
  2963.     smartlist_free(entry_guards);
  2964.     entry_guards = NULL;
  2965.   }
  2966.   clear_bridge_list();
  2967.   smartlist_free(bridge_list);
  2968.   bridge_list = NULL;
  2969. }