diff options
| -rw-r--r-- | src/or/circuitbuild.c | 1 | ||||
| -rw-r--r-- | src/or/circuitlist.c | 1 | ||||
| -rw-r--r-- | src/or/config.c | 2 | ||||
| -rw-r--r-- | src/or/confparse.c | 2 | ||||
| -rw-r--r-- | src/or/connection_edge.c | 1 | ||||
| -rw-r--r-- | src/or/control.c | 16 | ||||
| -rw-r--r-- | src/or/directory.c | 1 | ||||
| -rw-r--r-- | src/or/include.am | 2 | ||||
| -rw-r--r-- | src/or/networkstatus.c | 24 | ||||
| -rw-r--r-- | src/or/networkstatus.h | 2 | ||||
| -rw-r--r-- | src/or/nodelist.c | 500 | ||||
| -rw-r--r-- | src/or/nodelist.h | 13 | ||||
| -rw-r--r-- | src/or/rendclient.c | 1 | ||||
| -rw-r--r-- | src/or/rendservice.c | 1 | ||||
| -rw-r--r-- | src/or/router.c | 1 | ||||
| -rw-r--r-- | src/or/routerlist.c | 1057 | ||||
| -rw-r--r-- | src/or/routerlist.h | 49 | ||||
| -rw-r--r-- | src/or/routerset.c | 426 | ||||
| -rw-r--r-- | src/or/routerset.h | 48 |
19 files changed, 1040 insertions, 1108 deletions
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index e9d010ee30..d4969239cb 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -33,6 +33,7 @@ #include "router.h" #include "routerlist.h" #include "routerparse.h" +#include "routerset.h" #include "statefile.h" #include "crypto.h" #undef log diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c index 7ed942c8fe..d9b74bd4c2 100644 --- a/src/or/circuitlist.c +++ b/src/or/circuitlist.c @@ -26,6 +26,7 @@ #include "rendcommon.h" #include "rephist.h" #include "routerlist.h" +#include "routerset.h" #include "ht.h" /********* START VARIABLES **********/ diff --git a/src/or/config.c b/src/or/config.c index 3536db6d07..4557853cec 100644 --- a/src/or/config.c +++ b/src/or/config.c @@ -28,6 +28,7 @@ #include "hibernate.h" #include "main.h" #include "networkstatus.h" +#include "nodelist.h" #include "policies.h" #include "relay.h" #include "rendclient.h" @@ -36,6 +37,7 @@ #include "router.h" #include "util.h" #include "routerlist.h" +#include "routerset.h" #include "statefile.h" #include "transports.h" #ifdef _WIN32 diff --git a/src/or/confparse.c b/src/or/confparse.c index 203395d081..67cf43fe8c 100644 --- a/src/or/confparse.c +++ b/src/or/confparse.c @@ -6,7 +6,7 @@ #include "or.h" #include "confparse.h" -#include "routerlist.h" +#include "routerset.h" static uint64_t config_parse_memunit(const char *s, int *ok); static int config_parse_msec_interval(const char *s, int *ok); diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c index 1592033c54..ade3b48df2 100644 --- a/src/or/connection_edge.c +++ b/src/or/connection_edge.c @@ -33,6 +33,7 @@ #include "rephist.h" #include "router.h" #include "routerlist.h" +#include "routerset.h" #ifdef HAVE_LINUX_TYPES_H #include <linux/types.h> diff --git a/src/or/control.c b/src/or/control.c index bb893267df..74c6acc000 100644 --- a/src/or/control.c +++ b/src/or/control.c @@ -1639,10 +1639,13 @@ getinfo_helper_dir(control_connection_t *control_conn, const char *question, char **answer, const char **errmsg) { - const routerinfo_t *ri; + const node_t *node; + const routerinfo_t *ri = NULL; (void) control_conn; if (!strcmpstart(question, "desc/id/")) { - ri = router_get_by_hexdigest(question+strlen("desc/id/")); + node = node_get_by_hex_id(question+strlen("desc/id/")); + if (node) + ri = node->ri; if (ri) { const char *body = signed_descriptor_get_body(&ri->cache_info); if (body) @@ -1651,7 +1654,9 @@ getinfo_helper_dir(control_connection_t *control_conn, } else if (!strcmpstart(question, "desc/name/")) { /* XXX023 Setting 'warn_if_unnamed' here is a bit silly -- the * warning goes to the user, not to the controller. */ - ri = router_get_by_nickname(question+strlen("desc/name/"),1); + node = node_get_by_nickname(question+strlen("desc/name/"), 1); + if (node) + ri = node->ri; if (ri) { const char *body = signed_descriptor_get_body(&ri->cache_info); if (body) @@ -1713,8 +1718,9 @@ getinfo_helper_dir(control_connection_t *control_conn, *answer = tor_strndup(md->body, md->bodylen); } } else if (!strcmpstart(question, "desc-annotations/id/")) { - ri = router_get_by_hexdigest(question+ - strlen("desc-annotations/id/")); + node = node_get_by_hex_id(question+strlen("desc-annotations/id/")); + if (node) + ri = node->ri; if (ri) { const char *annotations = signed_descriptor_get_annotations(&ri->cache_info); diff --git a/src/or/directory.c b/src/or/directory.c index effccc5856..7df91fb57e 100644 --- a/src/or/directory.c +++ b/src/or/directory.c @@ -25,6 +25,7 @@ #include "router.h" #include "routerlist.h" #include "routerparse.h" +#include "routerset.h" #if defined(EXPORTMALLINFO) && defined(HAVE_MALLOC_H) && defined(HAVE_MALLINFO) #ifndef OPENBSD diff --git a/src/or/include.am b/src/or/include.am index 5c93e3e598..e9811ec962 100644 --- a/src/or/include.am +++ b/src/or/include.am @@ -53,6 +53,7 @@ src_or_libtor_a_SOURCES = \ src/or/router.c \ src/or/routerlist.c \ src/or/routerparse.c \ + src/or/routerset.c \ src/or/statefile.c \ src/or/status.c \ $(evdns_source) \ @@ -124,6 +125,7 @@ ORHEADERS = \ src/or/replaycache.h \ src/or/router.h \ src/or/routerlist.h \ + src/or/routerset.h \ src/or/routerparse.h \ src/or/statefile.h \ src/or/status.h diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c index ff31f82ff6..0cc6a21085 100644 --- a/src/or/networkstatus.c +++ b/src/or/networkstatus.c @@ -2304,6 +2304,30 @@ networkstatus_parse_flavor_name(const char *flavname) return -1; } +/** Return 0 if this routerstatus is obsolete, too new, isn't + * running, or otherwise not a descriptor that we would make any + * use of even if we had it. Else return 1. */ +int +client_would_use_router(const routerstatus_t *rs, time_t now, + const or_options_t *options) +{ + if (!rs->is_flagged_running && !options->FetchUselessDescriptors) { + /* If we had this router descriptor, we wouldn't even bother using it. + * But, if we want to have a complete list, fetch it anyway. */ + return 0; + } + if (rs->published_on + options->TestingEstimatedDescriptorPropagationTime + > now) { + /* Most caches probably don't have this descriptor yet. */ + return 0; + } + if (rs->published_on + OLD_ROUTER_DESC_MAX_AGE < now) { + /* We'd drop it immediately for being too old. */ + return 0; + } + return 1; +} + /** If <b>question</b> is a string beginning with "ns/" in a format the * control interface expects for a GETINFO question, set *<b>answer</b> to a * newly-allocated string containing networkstatus lines for the appropriate diff --git a/src/or/networkstatus.h b/src/or/networkstatus.h index 0af17512dd..dcd58f8898 100644 --- a/src/or/networkstatus.h +++ b/src/or/networkstatus.h @@ -71,6 +71,8 @@ int should_delay_dir_fetches(const or_options_t *options); void update_networkstatus_downloads(time_t now); void update_certificate_downloads(time_t now); int consensus_is_waiting_for_certs(void); +int client_would_use_router(const routerstatus_t *rs, time_t now, + const or_options_t *options); networkstatus_v2_t *networkstatus_v2_get_by_digest(const char *digest); networkstatus_t *networkstatus_get_latest_consensus(void); networkstatus_t *networkstatus_get_latest_consensus_by_flavor( diff --git a/src/or/nodelist.c b/src/or/nodelist.c index b96491f5f9..c357bc0474 100644 --- a/src/or/nodelist.c +++ b/src/or/nodelist.c @@ -5,19 +5,26 @@ /* See LICENSE for licensing information */ #include "or.h" +#include "address.h" #include "config.h" +#include "control.h" #include "dirserv.h" +#include "geoip.h" +#include "main.h" #include "microdesc.h" #include "networkstatus.h" #include "nodelist.h" #include "policies.h" +#include "rendservice.h" #include "router.h" #include "routerlist.h" +#include "routerset.h" #include <string.h> static void nodelist_drop_node(node_t *node, int remove_from_ht); static void node_free(node_t *node); +static void update_router_have_minimum_dir_info(void); /** A nodelist_t holds a node_t object for every router we're "willing to use * for something". Specifically, it should hold a node_t for every node that @@ -905,3 +912,496 @@ node_get_pref_ipv6_orport(const node_t *node, tor_addr_port_t *ap_out) } } +/** Refresh the country code of <b>ri</b>. This function MUST be called on + * each router when the GeoIP database is reloaded, and on all new routers. */ +void +node_set_country(node_t *node) +{ + if (node->rs) + node->country = geoip_get_country_by_ip(node->rs->addr); + else if (node->ri) + node->country = geoip_get_country_by_ip(node->ri->addr); + else + node->country = -1; +} + +/** Set the country code of all routers in the routerlist. */ +void +nodelist_refresh_countries(void) +{ + smartlist_t *nodes = nodelist_get_list(); + SMARTLIST_FOREACH(nodes, node_t *, node, + node_set_country(node)); +} + +/** Return true iff router1 and router2 have similar enough network addresses + * that we should treat them as being in the same family */ +static INLINE int +addrs_in_same_network_family(const tor_addr_t *a1, + const tor_addr_t *a2) +{ + return 0 == tor_addr_compare_masked(a1, a2, 16, CMP_SEMANTIC); +} + +/** Return true if <b>node</b>'s nickname matches <b>nickname</b> + * (case-insensitive), or if <b>node's</b> identity key digest + * matches a hexadecimal value stored in <b>nickname</b>. Return + * false otherwise. */ +static int +node_nickname_matches(const node_t *node, const char *nickname) +{ + const char *n = node_get_nickname(node); + if (n && nickname[0]!='$' && !strcasecmp(n, nickname)) + return 1; + return hex_digest_nickname_matches(nickname, + node->identity, + n, + node_is_named(node)); +} + +/** Return true iff <b>node</b> is named by some nickname in <b>lst</b>. */ +static INLINE int +node_in_nickname_smartlist(const smartlist_t *lst, const node_t *node) +{ + if (!lst) return 0; + SMARTLIST_FOREACH(lst, const char *, name, { + if (node_nickname_matches(node, name)) + return 1; + }); + return 0; +} + +/** Return true iff r1 and r2 are in the same family, but not the same + * router. */ +int +nodes_in_same_family(const node_t *node1, const node_t *node2) +{ + const or_options_t *options = get_options(); + + /* Are they in the same family because of their addresses? */ + if (options->EnforceDistinctSubnets) { + tor_addr_t a1, a2; + node_get_addr(node1, &a1); + node_get_addr(node2, &a2); + if (addrs_in_same_network_family(&a1, &a2)) + return 1; + } + + /* Are they in the same family because the agree they are? */ + { + const smartlist_t *f1, *f2; + f1 = node_get_declared_family(node1); + f2 = node_get_declared_family(node2); + if (f1 && f2 && + node_in_nickname_smartlist(f1, node2) && + node_in_nickname_smartlist(f2, node1)) + return 1; + } + + /* Are they in the same option because the user says they are? */ + if (options->NodeFamilySets) { + SMARTLIST_FOREACH(options->NodeFamilySets, const routerset_t *, rs, { + if (routerset_contains_node(rs, node1) && + routerset_contains_node(rs, node2)) + return 1; + }); + } + + return 0; +} + +/** + * Add all the family of <b>node</b>, including <b>node</b> itself, to + * the smartlist <b>sl</b>. + * + * This is used to make sure we don't pick siblings in a single path, or + * pick more than one relay from a family for our entry guard list. + * Note that a node may be added to <b>sl</b> more than once if it is + * part of <b>node</b>'s family for more than one reason. + */ +void +nodelist_add_node_and_family(smartlist_t *sl, const node_t *node) +{ + const smartlist_t *all_nodes = nodelist_get_list(); + const smartlist_t *declared_family; + const or_options_t *options = get_options(); + + tor_assert(node); + + declared_family = node_get_declared_family(node); + + /* Let's make sure that we have the node itself, if it's a real node. */ + { + const node_t *real_node = node_get_by_id(node->identity); + if (real_node) + smartlist_add(sl, (node_t*)real_node); + } + + /* First, add any nodes with similar network addresses. */ + if (options->EnforceDistinctSubnets) { + tor_addr_t node_addr; + node_get_addr(node, &node_addr); + + SMARTLIST_FOREACH_BEGIN(all_nodes, const node_t *, node2) { + tor_addr_t a; + node_get_addr(node2, &a); + if (addrs_in_same_network_family(&a, &node_addr)) + smartlist_add(sl, (void*)node2); + } SMARTLIST_FOREACH_END(node2); + } + + /* Now, add all nodes in the declared_family of this node, if they + * also declare this node to be in their family. */ + if (declared_family) { + /* Add every r such that router declares familyness with node, and node + * declares familyhood with router. */ + SMARTLIST_FOREACH_BEGIN(declared_family, const char *, name) { + const node_t *node2; + const smartlist_t *family2; + if (!(node2 = node_get_by_nickname(name, 0))) + continue; + if (!(family2 = node_get_declared_family(node2))) + continue; + SMARTLIST_FOREACH_BEGIN(family2, const char *, name2) { + if (node_nickname_matches(node, name2)) { + smartlist_add(sl, (void*)node2); + break; + } + } SMARTLIST_FOREACH_END(name2); + } SMARTLIST_FOREACH_END(name); + } + + /* If the user declared any families locally, honor those too. */ + if (options->NodeFamilySets) { + SMARTLIST_FOREACH(options->NodeFamilySets, const routerset_t *, rs, { + if (routerset_contains_node(rs, node)) { + routerset_get_all_nodes(sl, rs, NULL, 0); + } + }); + } +} + +/** Find a router that's up, that has this IP address, and + * that allows exit to this address:port, or return NULL if there + * isn't a good one. + * Don't exit enclave to excluded relays -- it wouldn't actually + * hurt anything, but this way there are fewer confused users. + */ +const node_t * +router_find_exact_exit_enclave(const char *address, uint16_t port) +{/*XXXX MOVE*/ + uint32_t addr; + struct in_addr in; + tor_addr_t a; + const or_options_t *options = get_options(); + + if (!tor_inet_aton(address, &in)) + return NULL; /* it's not an IP already */ + addr = ntohl(in.s_addr); + + tor_addr_from_ipv4h(&a, addr); + + SMARTLIST_FOREACH(nodelist_get_list(), const node_t *, node, { + if (node_get_addr_ipv4h(node) == addr && + node->is_running && + compare_tor_addr_to_node_policy(&a, port, node) == + ADDR_POLICY_ACCEPTED && + !routerset_contains_node(options->_ExcludeExitNodesUnion, node)) + return node; + }); + return NULL; +} + +/** Return 1 if <b>router</b> is not suitable for these parameters, else 0. + * If <b>need_uptime</b> is non-zero, we require a minimum uptime. + * If <b>need_capacity</b> is non-zero, we require a minimum advertised + * bandwidth. + * If <b>need_guard</b>, we require that the router is a possible entry guard. + */ +int +node_is_unreliable(const node_t *node, int need_uptime, + int need_capacity, int need_guard) +{ + if (need_uptime && !node->is_stable) + return 1; + if (need_capacity && !node->is_fast) + return 1; + if (need_guard && !node->is_possible_guard) + return 1; + return 0; +} + +/** Return 1 if all running sufficiently-stable routers we can use will reject + * addr:port, return 0 if any might accept it. */ +int +router_exit_policy_all_nodes_reject(const tor_addr_t *addr, uint16_t port, + int need_uptime) +{ + addr_policy_result_t r; + + SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t *, node) { + if (node->is_running && + !node_is_unreliable(node, need_uptime, 0, 0)) { + + r = compare_tor_addr_to_node_policy(addr, port, node); + + if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED) + return 0; /* this one could be ok. good enough. */ + } + } SMARTLIST_FOREACH_END(node); + return 1; /* all will reject. */ +} + +/** Mark the router with ID <b>digest</b> as running or non-running + * in our routerlist. */ +void +router_set_status(const char *digest, int up) +{ + node_t *node; + tor_assert(digest); + + SMARTLIST_FOREACH(router_get_trusted_dir_servers(), + trusted_dir_server_t *, d, + if (tor_memeq(d->digest, digest, DIGEST_LEN)) + d->is_running = up); + + node = node_get_mutable_by_id(digest); + if (node) { +#if 0 + log_debug(LD_DIR,"Marking router %s as %s.", + node_describe(node), up ? "up" : "down"); +#endif + if (!up && node_is_me(node) && !net_is_disabled()) + log_warn(LD_NET, "We just marked ourself as down. Are your external " + "addresses reachable?"); + node->is_running = up; + } + + router_dir_info_changed(); +} + +/** True iff, the last time we checked whether we had enough directory info + * to build circuits, the answer was "yes". */ +static int have_min_dir_info = 0; +/** True iff enough has changed since the last time we checked whether we had + * enough directory info to build circuits that our old answer can no longer + * be trusted. */ +static int need_to_update_have_min_dir_info = 1; +/** String describing what we're missing before we have enough directory + * info. */ +static char dir_info_status[128] = ""; + +/** Return true iff we have enough networkstatus and router information to + * start building circuits. Right now, this means "more than half the + * networkstatus documents, and at least 1/4 of expected routers." */ +//XXX should consider whether we have enough exiting nodes here. +int +router_have_minimum_dir_info(void) +{ + if (PREDICT_UNLIKELY(need_to_update_have_min_dir_info)) { + update_router_have_minimum_dir_info(); + need_to_update_have_min_dir_info = 0; + } + return have_min_dir_info; +} + +/** Called when our internal view of the directory has changed. This can be + * when the authorities change, networkstatuses change, the list of routerdescs + * changes, or number of running routers changes. + */ +void +router_dir_info_changed(void) +{ + need_to_update_have_min_dir_info = 1; + rend_hsdir_routers_changed(); +} + +/** Return a string describing what we're missing before we have enough + * directory info. */ +const char * +get_dir_info_status_string(void) +{ + return dir_info_status; +} + +/** Iterate over the servers listed in <b>consensus</b>, and count how many of + * them seem like ones we'd use, and how many of <em>those</em> we have + * descriptors for. Store the former in *<b>num_usable</b> and the latter in + * *<b>num_present</b>. If <b>in_set</b> is non-NULL, only consider those + * routers in <b>in_set</b>. If <b>exit_only</b> is true, only consider nodes + * with the Exit flag. + */ +static void +count_usable_descriptors(int *num_present, int *num_usable, + const networkstatus_t *consensus, + const or_options_t *options, time_t now, + routerset_t *in_set, int exit_only) +{ + const int md = (consensus->flavor == FLAV_MICRODESC); + *num_present = 0, *num_usable=0; + + SMARTLIST_FOREACH_BEGIN(consensus->routerstatus_list, routerstatus_t *, rs) + { + if (exit_only && ! rs->is_exit) + continue; + if (in_set && ! routerset_contains_routerstatus(in_set, rs, -1)) + continue; + if (client_would_use_router(rs, now, options)) { + const char * const digest = rs->descriptor_digest; + int present; + ++*num_usable; /* the consensus says we want it. */ + if (md) + present = NULL != microdesc_cache_lookup_by_digest256(NULL, digest); + else + present = NULL != router_get_by_descriptor_digest(digest); + if (present) { + /* we have the descriptor listed in the consensus. */ + ++*num_present; + } + } + } + SMARTLIST_FOREACH_END(rs); + + log_debug(LD_DIR, "%d usable, %d present (%s).", *num_usable, *num_present, + md ? "microdescs" : "descs"); +} + +/** We just fetched a new set of descriptors. Compute how far through + * the "loading descriptors" bootstrapping phase we are, so we can inform + * the controller of our progress. */ +int +count_loading_descriptors_progress(void) +{ + int num_present = 0, num_usable=0; + time_t now = time(NULL); + const networkstatus_t *consensus = + networkstatus_get_reasonably_live_consensus(now,usable_consensus_flavor()); + double fraction; + + if (!consensus) + return 0; /* can't count descriptors if we have no list of them */ + + count_usable_descriptors(&num_present, &num_usable, + consensus, get_options(), now, NULL, 0); + + if (num_usable == 0) + return 0; /* don't div by 0 */ + fraction = num_present / (num_usable/4.); + if (fraction > 1.0) + return 0; /* it's not the number of descriptors holding us back */ + return BOOTSTRAP_STATUS_LOADING_DESCRIPTORS + (int) + (fraction*(BOOTSTRAP_STATUS_CONN_OR-1 - + BOOTSTRAP_STATUS_LOADING_DESCRIPTORS)); +} + +/** Change the value of have_min_dir_info, setting it true iff we have enough + * network and router information to build circuits. Clear the value of + * need_to_update_have_min_dir_info. */ +static void +update_router_have_minimum_dir_info(void) +{ + int num_present = 0, num_usable=0; + int num_exit_present = 0, num_exit_usable = 0; + time_t now = time(NULL); + int res; + const or_options_t *options = get_options(); + const networkstatus_t *consensus = + networkstatus_get_reasonably_live_consensus(now,usable_consensus_flavor()); + int using_md; + + if (!consensus) { + if (!networkstatus_get_latest_consensus()) + strlcpy(dir_info_status, "We have no usable consensus.", + sizeof(dir_info_status)); + else + strlcpy(dir_info_status, "We have no recent usable consensus.", + sizeof(dir_info_status)); + res = 0; + goto done; + } + + if (should_delay_dir_fetches(get_options())) { + log_notice(LD_DIR, "no known bridge descriptors running yet; stalling"); + strlcpy(dir_info_status, "No live bridge descriptors.", + sizeof(dir_info_status)); + res = 0; + goto done; + } + + using_md = consensus->flavor == FLAV_MICRODESC; + + count_usable_descriptors(&num_present, &num_usable, consensus, options, now, + NULL, 0); + count_usable_descriptors(&num_exit_present, &num_exit_usable, + consensus, options, now, options->ExitNodes, 1); + +/* What fraction of desired server descriptors do we need before we will + * build circuits? */ +#define FRAC_USABLE_NEEDED .75 +/* What fraction of desired _exit_ server descriptors do we need before we + * will build circuits? */ +#define FRAC_EXIT_USABLE_NEEDED .5 + + if (num_present < num_usable * FRAC_USABLE_NEEDED) { + tor_snprintf(dir_info_status, sizeof(dir_info_status), + "We have only %d/%d usable %sdescriptors.", + num_present, num_usable, using_md ? "micro" : ""); + res = 0; + control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS, 0); + goto done; + } else if (num_present < 2) { + tor_snprintf(dir_info_status, sizeof(dir_info_status), + "Only %d %sdescriptor%s here and believed reachable!", + num_present, using_md ? "micro" : "", num_present ? "" : "s"); + res = 0; + goto done; + } else if (num_exit_present < num_exit_usable * FRAC_EXIT_USABLE_NEEDED) { + tor_snprintf(dir_info_status, sizeof(dir_info_status), + "We have only %d/%d usable exit node descriptors.", + num_exit_present, num_exit_usable); + res = 0; + control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS, 0); + goto done; + } + + /* Check for entry nodes. */ + if (options->EntryNodes) { + count_usable_descriptors(&num_present, &num_usable, consensus, options, + now, options->EntryNodes, 0); + + if (!num_usable || !num_present) { + tor_snprintf(dir_info_status, sizeof(dir_info_status), + "We have only %d/%d usable entry node %sdescriptors.", + num_present, num_usable, using_md?"micro":""); + res = 0; + goto done; + } + } + + res = 1; + + done: + if (res && !have_min_dir_info) { + log(LOG_NOTICE, LD_DIR, + "We now have enough directory information to build circuits."); + control_event_client_status(LOG_NOTICE, "ENOUGH_DIR_INFO"); + control_event_bootstrap(BOOTSTRAP_STATUS_CONN_OR, 0); + } + if (!res && have_min_dir_info) { + int quiet = directory_too_idle_to_fetch_descriptors(options, now); + log(quiet ? LOG_INFO : LOG_NOTICE, LD_DIR, + "Our directory information is no longer up-to-date " + "enough to build circuits: %s", dir_info_status); + + /* a) make us log when we next complete a circuit, so we know when Tor + * is back up and usable, and b) disable some activities that Tor + * should only do while circuits are working, like reachability tests + * and fetching bridge descriptors only over circuits. */ + can_complete_circuit = 0; + + control_event_client_status(LOG_NOTICE, "NOT_ENOUGH_DIR_INFO"); + } + have_min_dir_info = res; + need_to_update_have_min_dir_info = 0; +} + diff --git a/src/or/nodelist.h b/src/or/nodelist.h index fb65fa5483..2e978f1782 100644 --- a/src/or/nodelist.h +++ b/src/or/nodelist.h @@ -61,11 +61,22 @@ smartlist_t *nodelist_get_list(void); void node_get_addr(const node_t *node, tor_addr_t *addr_out); #define node_get_addr_ipv4h(n) node_get_prim_addr_ipv4h((n)) -/* XXXX These need to move out of routerlist.c */ void nodelist_refresh_countries(void); void node_set_country(node_t *node); void nodelist_add_node_and_family(smartlist_t *nodes, const node_t *node); int nodes_in_same_family(const node_t *node1, const node_t *node2); +const node_t *router_find_exact_exit_enclave(const char *address, + uint16_t port); +int node_is_unreliable(const node_t *router, int need_uptime, + int need_capacity, int need_guard); +int router_exit_policy_all_nodes_reject(const tor_addr_t *addr, uint16_t port, + int need_uptime); +void router_set_status(const char *digest, int up); +int router_have_minimum_dir_info(void); +void router_dir_info_changed(void); +const char *get_dir_info_status_string(void); +int count_loading_descriptors_progress(void); + #endif diff --git a/src/or/rendclient.c b/src/or/rendclient.c index 0b6d82bdf4..73e1c41d7b 100644 --- a/src/or/rendclient.c +++ b/src/or/rendclient.c @@ -23,6 +23,7 @@ #include "rephist.h" #include "router.h" #include "routerlist.h" +#include "routerset.h" static extend_info_t *rend_client_get_random_intro_impl( const rend_cache_entry_t *rend_query, diff --git a/src/or/rendservice.c b/src/or/rendservice.c index 394831f857..0bfa17d108 100644 --- a/src/or/rendservice.c +++ b/src/or/rendservice.c @@ -26,6 +26,7 @@ #include "replaycache.h" #include "routerlist.h" #include "routerparse.h" +#include "routerset.h" static origin_circuit_t *find_intro_circuit(rend_intro_point_t *intro, const char *pk_digest); diff --git a/src/or/router.c b/src/or/router.c index 91209eef04..052ed38074 100644 --- a/src/or/router.c +++ b/src/or/router.c @@ -29,6 +29,7 @@ #include "routerparse.h" #include "statefile.h" #include "transports.h" +#include "routerset.h" /** * \file router.c diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 214c086448..98357d6a38 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -34,6 +34,7 @@ #include "router.h" #include "routerlist.h" #include "routerparse.h" +#include "routerset.h" // #define DEBUG_ROUTERLIST @@ -47,11 +48,8 @@ static const routerstatus_t *router_pick_trusteddirserver_impl( static void mark_all_trusteddirservers_up(void); static int router_nickname_matches(const routerinfo_t *router, const char *nickname); -static int node_nickname_matches(const node_t *router, - const char *nickname); static void trusted_dir_server_free(trusted_dir_server_t *ds); static int signed_desc_digest_is_recognized(signed_descriptor_t *desc); -static void update_router_have_minimum_dir_info(void); static const char *signed_descriptor_get_body_impl( const signed_descriptor_t *desc, int with_annotations); @@ -1352,88 +1350,6 @@ router_reset_status_download_failures(void) mark_all_trusteddirservers_up(); } -/** Return true iff router1 and router2 have similar enough network addresses - * that we should treat them as being in the same family */ -static INLINE int -addrs_in_same_network_family(const tor_addr_t *a1, - const tor_addr_t *a2) -{ - /* XXXX MOVE ? */ - return 0 == tor_addr_compare_masked(a1, a2, 16, CMP_SEMANTIC); -} - -/** - * Add all the family of <b>node</b>, including <b>node</b> itself, to - * the smartlist <b>sl</b>. - * - * This is used to make sure we don't pick siblings in a single path, or - * pick more than one relay from a family for our entry guard list. - * Note that a node may be added to <b>sl</b> more than once if it is - * part of <b>node</b>'s family for more than one reason. - */ -void -nodelist_add_node_and_family(smartlist_t *sl, const node_t *node) -{ - /* XXXX MOVE */ - const smartlist_t *all_nodes = nodelist_get_list(); - const smartlist_t *declared_family; - const or_options_t *options = get_options(); - - tor_assert(node); - - declared_family = node_get_declared_family(node); - - /* Let's make sure that we have the node itself, if it's a real node. */ - { - const node_t *real_node = node_get_by_id(node->identity); - if (real_node) - smartlist_add(sl, (node_t*)real_node); - } - - /* First, add any nodes with similar network addresses. */ - if (options->EnforceDistinctSubnets) { - tor_addr_t node_addr; - node_get_addr(node, &node_addr); - - SMARTLIST_FOREACH_BEGIN(all_nodes, const node_t *, node2) { - tor_addr_t a; - node_get_addr(node2, &a); - if (addrs_in_same_network_family(&a, &node_addr)) - smartlist_add(sl, (void*)node2); - } SMARTLIST_FOREACH_END(node2); - } - - /* Now, add all nodes in the declared_family of this node, if they - * also declare this node to be in their family. */ - if (declared_family) { - /* Add every r such that router declares familyness with node, and node - * declares familyhood with router. */ - SMARTLIST_FOREACH_BEGIN(declared_family, const char *, name) { - const node_t *node2; - const smartlist_t *family2; - if (!(node2 = node_get_by_nickname(name, 0))) - continue; - if (!(family2 = node_get_declared_family(node2))) - continue; - SMARTLIST_FOREACH_BEGIN(family2, const char *, name2) { - if (node_nickname_matches(node, name2)) { - smartlist_add(sl, (void*)node2); - break; - } - } SMARTLIST_FOREACH_END(name2); - } SMARTLIST_FOREACH_END(name); - } - - /* If the user declared any families locally, honor those too. */ - if (options->NodeFamilySets) { - SMARTLIST_FOREACH(options->NodeFamilySets, const routerset_t *, rs, { - if (routerset_contains_node(rs, node)) { - routerset_get_all_nodes(sl, rs, NULL, 0); - } - }); - } -} - /** Given a <b>router</b>, add every node_t in its family (including the * node itself!) to <b>sl</b>. * @@ -1455,59 +1371,6 @@ routerlist_add_node_and_family(smartlist_t *sl, const routerinfo_t *router) nodelist_add_node_and_family(sl, node); } -/** Return true iff <b>node</b> is named by some nickname in <b>lst</b>. */ -static INLINE int -node_in_nickname_smartlist(const smartlist_t *lst, const node_t *node) -{ - /* XXXX MOVE */ - if (!lst) return 0; - SMARTLIST_FOREACH(lst, const char *, name, { - if (node_nickname_matches(node, name)) - return 1; - }); - return 0; -} - -/** Return true iff r1 and r2 are in the same family, but not the same - * router. */ -int -nodes_in_same_family(const node_t *node1, const node_t *node2) -{ - /* XXXX MOVE */ - const or_options_t *options = get_options(); - - /* Are they in the same family because of their addresses? */ - if (options->EnforceDistinctSubnets) { - tor_addr_t a1, a2; - node_get_addr(node1, &a1); - node_get_addr(node2, &a2); - if (addrs_in_same_network_family(&a1, &a2)) - return 1; - } - - /* Are they in the same family because the agree they are? */ - { - const smartlist_t *f1, *f2; - f1 = node_get_declared_family(node1); - f2 = node_get_declared_family(node2); - if (f1 && f2 && - node_in_nickname_smartlist(f1, node2) && - node_in_nickname_smartlist(f2, node1)) - return 1; - } - - /* Are they in the same option because the user says they are? */ - if (options->NodeFamilySets) { - SMARTLIST_FOREACH(options->NodeFamilySets, const routerset_t *, rs, { - if (routerset_contains_node(rs, node1) && - routerset_contains_node(rs, node2)) - return 1; - }); - } - - return 0; -} - /** Return 1 iff any member of the (possibly NULL) comma-separated list * <b>list</b> is an acceptable nickname or hexdigest for <b>router</b>. Else * return 0. @@ -1571,56 +1434,6 @@ routerlist_find_my_routerinfo(void) return NULL; } -/** Find a router that's up, that has this IP address, and - * that allows exit to this address:port, or return NULL if there - * isn't a good one. - * Don't exit enclave to excluded relays -- it wouldn't actually - * hurt anything, but this way there are fewer confused users. - */ -const node_t * -router_find_exact_exit_enclave(const char *address, uint16_t port) -{/*XXXX MOVE*/ - uint32_t addr; - struct in_addr in; - tor_addr_t a; - const or_options_t *options = get_options(); - - if (!tor_inet_aton(address, &in)) - return NULL; /* it's not an IP already */ - addr = ntohl(in.s_addr); - - tor_addr_from_ipv4h(&a, addr); - - SMARTLIST_FOREACH(nodelist_get_list(), const node_t *, node, { - if (node_get_addr_ipv4h(node) == addr && - node->is_running && - compare_tor_addr_to_node_policy(&a, port, node) == - ADDR_POLICY_ACCEPTED && - !routerset_contains_node(options->_ExcludeExitNodesUnion, node)) - return node; - }); - return NULL; -} - -/** Return 1 if <b>router</b> is not suitable for these parameters, else 0. - * If <b>need_uptime</b> is non-zero, we require a minimum uptime. - * If <b>need_capacity</b> is non-zero, we require a minimum advertised - * bandwidth. - * If <b>need_guard</b>, we require that the router is a possible entry guard. - */ -int -node_is_unreliable(const node_t *node, int need_uptime, - int need_capacity, int need_guard) -{ - if (need_uptime && !node->is_stable) - return 1; - if (need_capacity && !node->is_fast) - return 1; - if (need_guard && !node->is_possible_guard) - return 1; - return 0; -} - /** Return the smaller of the router's configured BandwidthRate * and its advertised capacity. */ uint32_t @@ -2301,7 +2114,7 @@ hex_digest_nickname_decode(const char *hexdigest, * combination of a router, encoded in hexadecimal, matches <b>hexdigest</b> * (which is optionally prefixed with a single dollar sign). Return false if * <b>hexdigest</b> is malformed, or it doesn't match. */ -static int +int hex_digest_nickname_matches(const char *hexdigest, const char *identity_digest, const char *nickname, int is_named) { @@ -2361,129 +2174,6 @@ router_nickname_matches(const routerinfo_t *router, const char *nickname) return router_hex_digest_matches(router, nickname); } -/** Return true if <b>node</b>'s nickname matches <b>nickname</b> - * (case-insensitive), or if <b>node's</b> identity key digest - * matches a hexadecimal value stored in <b>nickname</b>. Return - * false otherwise. */ -static int -node_nickname_matches(const node_t *node, const char *nickname) -{ - const char *n = node_get_nickname(node); - if (n && nickname[0]!='$' && !strcasecmp(n, nickname)) - return 1; - return hex_digest_nickname_matches(nickname, - node->identity, - n, - node_is_named(node)); -} - -/** Return the router in our routerlist whose (case-insensitive) - * nickname or (case-sensitive) hexadecimal key digest is - * <b>nickname</b>. Return NULL if no such router is known. - */ -const routerinfo_t * -router_get_by_nickname(const char *nickname, int warn_if_unnamed) -{ -#if 1 - const node_t *node = node_get_by_nickname(nickname, warn_if_unnamed); - if (node) - return node->ri; - else - return NULL; -#else - int maybedigest; - char digest[DIGEST_LEN]; - routerinfo_t *best_match=NULL; - int n_matches = 0; - const char *named_digest = NULL; - - tor_assert(nickname); - if (!routerlist) - return NULL; - if (nickname[0] == '$') - return router_get_by_hexdigest(nickname); - if (!strcasecmp(nickname, UNNAMED_ROUTER_NICKNAME)) - return NULL; - - maybedigest = (strlen(nickname) >= HEX_DIGEST_LEN) && - (base16_decode(digest,DIGEST_LEN,nickname,HEX_DIGEST_LEN) == 0); - - if ((named_digest = networkstatus_get_router_digest_by_nickname(nickname))) { - return rimap_get(routerlist->identity_map, named_digest); - } - if (networkstatus_nickname_is_unnamed(nickname)) - return NULL; - - /* If we reach this point, there's no canonical value for the nickname. */ - - SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router, - { - if (!strcasecmp(router->nickname, nickname)) { - ++n_matches; - if (n_matches <= 1 || router->is_running) - best_match = router; - } else if (maybedigest && - tor_memeq(digest, router->cache_info.identity_digest, - DIGEST_LEN)) { - if (router_hex_digest_matches(router, nickname)) - return router; - /* If we reach this point, we have a ID=name syntax that matches the - * identity but not the name. That isn't an acceptable match. */ - } - }); - - if (best_match) { - if (warn_if_unnamed && n_matches > 1) { - smartlist_t *fps = smartlist_new(); - int any_unwarned = 0; - SMARTLIST_FOREACH_BEGIN(routerlist->routers, routerinfo_t *, router) { - routerstatus_t *rs; - char fp[HEX_DIGEST_LEN+1]; - if (strcasecmp(router->nickname, nickname)) - continue; - rs = router_get_mutable_consensus_status_by_id( - router->cache_info.identity_digest); - if (rs && !rs->name_lookup_warned) { - rs->name_lookup_warned = 1; - any_unwarned = 1; - } - base16_encode(fp, sizeof(fp), - router->cache_info.identity_digest, DIGEST_LEN); - smartlist_add_asprintf(fps, "\"$%s\" for the one at %s:%d", - fp, router->address, router->or_port); - } SMARTLIST_FOREACH_END(router); - if (any_unwarned) { - char *alternatives = smartlist_join_strings(fps, "; ",0,NULL); - log_warn(LD_CONFIG, - "There are multiple matches for the nickname \"%s\"," - " but none is listed as named by the directory authorities. " - "Choosing one arbitrarily. If you meant one in particular, " - "you should say %s.", nickname, alternatives); - tor_free(alternatives); - } - SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp)); - smartlist_free(fps); - } else if (warn_if_unnamed) { - routerstatus_t *rs = router_get_mutable_consensus_status_by_id( - best_match->cache_info.identity_digest); - if (rs && !rs->name_lookup_warned) { - char fp[HEX_DIGEST_LEN+1]; - base16_encode(fp, sizeof(fp), - best_match->cache_info.identity_digest, DIGEST_LEN); - log_warn(LD_CONFIG, "You specified a server \"%s\" by name, but this " - "name is not registered, so it could be used by any server, " - "not just the one you meant. " - "To make sure you get the same server in the future, refer to " - "it by key, as \"$%s\".", nickname, fp); - rs->name_lookup_warned = 1; - } - } - return best_match; - } - return NULL; -#endif -} - /** Return true iff <b>digest</b> is the digest of the identity key of a * trusted directory matching at least one bit of <b>type</b>. If <b>type</b> * is zero, any authority is okay. */ @@ -2530,18 +2220,6 @@ hexdigest_to_digest(const char *hexdigest, char *digest) return 0; } -/** Return the router in our routerlist whose hexadecimal key digest - * is <b>hexdigest</b>. Return NULL if no such router is known. */ -const routerinfo_t * -router_get_by_hexdigest(const char *hexdigest) -{ - if (is_legal_nickname(hexdigest)) - return NULL; - - /* It's not a legal nickname, so it must be a hexdigest or nothing. */ - return router_get_by_nickname(hexdigest, 1); -} - /** As router_get_by_id_digest,but return a pointer that you're allowed to * modify */ routerinfo_t * @@ -3261,33 +2939,6 @@ routerlist_reset_warnings(void) networkstatus_reset_warnings(); } -/** Mark the router with ID <b>digest</b> as running or non-running - * in our routerlist. */ -void -router_set_status(const char *digest, int up) -{ - node_t *node; - tor_assert(digest); - - SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, d, - if (tor_memeq(d->digest, digest, DIGEST_LEN)) - d->is_running = up); - - node = node_get_mutable_by_id(digest); - if (node) { -#if 0 - log_debug(LD_DIR,"Marking router %s as %s.", - node_describe(node), up ? "up" : "down"); -#endif - if (!up && node_is_me(node) && !net_is_disabled()) - log_warn(LD_NET, "We just marked ourself as down. Are your external " - "addresses reachable?"); - node->is_running = up; - } - - router_dir_info_changed(); -} - /** Add <b>router</b> to the routerlist, if we don't already have it. Replace * older entries (if any) with the same key. Note: Callers should not hold * their pointers to <b>router</b> if this function fails; <b>router</b> @@ -4061,27 +3712,6 @@ routerlist_retry_directory_downloads(time_t now) update_all_descriptor_downloads(now); } -/** Return 1 if all running sufficiently-stable routers we can use will reject - * addr:port, return 0 if any might accept it. */ -int -router_exit_policy_all_nodes_reject(const tor_addr_t *addr, uint16_t port, - int need_uptime) -{ /* XXXX MOVE */ - addr_policy_result_t r; - - SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t *, node) { - if (node->is_running && - !node_is_unreliable(node, need_uptime, 0, 0)) { - - r = compare_tor_addr_to_node_policy(addr, port, node); - - if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED) - return 0; /* this one could be ok. good enough. */ - } - } SMARTLIST_FOREACH_END(node); - return 1; /* all will reject. */ -} - /** Return true iff <b>router</b> does not permit exit streams. */ int @@ -4335,30 +3965,6 @@ initiate_descriptor_downloads(const routerstatus_t *source, tor_free(resource); } -/** Return 0 if this routerstatus is obsolete, too new, isn't - * running, or otherwise not a descriptor that we would make any - * use of even if we had it. Else return 1. */ -static INLINE int -client_would_use_router(const routerstatus_t *rs, time_t now, - const or_options_t *options) -{ - if (!rs->is_flagged_running && !options->FetchUselessDescriptors) { - /* If we had this router descriptor, we wouldn't even bother using it. - * But, if we want to have a complete list, fetch it anyway. */ - return 0; - } - if (rs->published_on + options->TestingEstimatedDescriptorPropagationTime - > now) { - /* Most caches probably don't have this descriptor yet. */ - return 0; - } - if (rs->published_on + OLD_ROUTER_DESC_MAX_AGE < now) { - /* We'd drop it immediately for being too old. */ - return 0; - } - return 1; -} - /** Max amount of hashes to download per request. * Since squid does not like URLs >= 4096 bytes we limit it to 96. * 4096 - strlen(http://255.255.255.255/tor/server/d/.z) == 4058 @@ -4871,231 +4477,6 @@ update_extrainfo_downloads(time_t now) smartlist_free(wanted); } -/** True iff, the last time we checked whether we had enough directory info - * to build circuits, the answer was "yes". */ -static int have_min_dir_info = 0; -/** True iff enough has changed since the last time we checked whether we had - * enough directory info to build circuits that our old answer can no longer - * be trusted. */ -static int need_to_update_have_min_dir_info = 1; -/** String describing what we're missing before we have enough directory - * info. */ -static char dir_info_status[128] = ""; - -/** Return true iff we have enough networkstatus and router information to - * start building circuits. Right now, this means "more than half the - * networkstatus documents, and at least 1/4 of expected routers." */ -//XXX should consider whether we have enough exiting nodes here. -int -router_have_minimum_dir_info(void) -{ - if (PREDICT_UNLIKELY(need_to_update_have_min_dir_info)) { - update_router_have_minimum_dir_info(); - need_to_update_have_min_dir_info = 0; - } - return have_min_dir_info; -} - -/** Called when our internal view of the directory has changed. This can be - * when the authorities change, networkstatuses change, the list of routerdescs - * changes, or number of running routers changes. - */ -void -router_dir_info_changed(void) -{ - need_to_update_have_min_dir_info = 1; - rend_hsdir_routers_changed(); -} - -/** Return a string describing what we're missing before we have enough - * directory info. */ -const char * -get_dir_info_status_string(void) -{ - return dir_info_status; -} - -/** Iterate over the servers listed in <b>consensus</b>, and count how many of - * them seem like ones we'd use, and how many of <em>those</em> we have - * descriptors for. Store the former in *<b>num_usable</b> and the latter in - * *<b>num_present</b>. If <b>in_set</b> is non-NULL, only consider those - * routers in <b>in_set</b>. If <b>exit_only</b> is true, only consider nodes - * with the Exit flag. - */ -static void -count_usable_descriptors(int *num_present, int *num_usable, - const networkstatus_t *consensus, - const or_options_t *options, time_t now, - routerset_t *in_set, int exit_only) -{ - const int md = (consensus->flavor == FLAV_MICRODESC); - *num_present = 0, *num_usable=0; - - SMARTLIST_FOREACH_BEGIN(consensus->routerstatus_list, routerstatus_t *, rs) - { - if (exit_only && ! rs->is_exit) - continue; - if (in_set && ! routerset_contains_routerstatus(in_set, rs, -1)) - continue; - if (client_would_use_router(rs, now, options)) { - const char * const digest = rs->descriptor_digest; - int present; - ++*num_usable; /* the consensus says we want it. */ - if (md) - present = NULL != microdesc_cache_lookup_by_digest256(NULL, digest); - else - present = NULL != router_get_by_descriptor_digest(digest); - if (present) { - /* we have the descriptor listed in the consensus. */ - ++*num_present; - } - } - } - SMARTLIST_FOREACH_END(rs); - - log_debug(LD_DIR, "%d usable, %d present (%s).", *num_usable, *num_present, - md ? "microdescs" : "descs"); -} - -/** We just fetched a new set of descriptors. Compute how far through - * the "loading descriptors" bootstrapping phase we are, so we can inform - * the controller of our progress. */ -int -count_loading_descriptors_progress(void) -{ - int num_present = 0, num_usable=0; - time_t now = time(NULL); - const networkstatus_t *consensus = - networkstatus_get_reasonably_live_consensus(now,usable_consensus_flavor()); - double fraction; - - if (!consensus) - return 0; /* can't count descriptors if we have no list of them */ - - count_usable_descriptors(&num_present, &num_usable, - consensus, get_options(), now, NULL, 0); - - if (num_usable == 0) - return 0; /* don't div by 0 */ - fraction = num_present / (num_usable/4.); - if (fraction > 1.0) - return 0; /* it's not the number of descriptors holding us back */ - return BOOTSTRAP_STATUS_LOADING_DESCRIPTORS + (int) - (fraction*(BOOTSTRAP_STATUS_CONN_OR-1 - - BOOTSTRAP_STATUS_LOADING_DESCRIPTORS)); -} - -/** Change the value of have_min_dir_info, setting it true iff we have enough - * network and router information to build circuits. Clear the value of - * need_to_update_have_min_dir_info. */ -static void -update_router_have_minimum_dir_info(void) -{ - int num_present = 0, num_usable=0; - int num_exit_present = 0, num_exit_usable = 0; - time_t now = time(NULL); - int res; - const or_options_t *options = get_options(); - const networkstatus_t *consensus = - networkstatus_get_reasonably_live_consensus(now,usable_consensus_flavor()); - int using_md; - - if (!consensus) { - if (!networkstatus_get_latest_consensus()) - strlcpy(dir_info_status, "We have no usable consensus.", - sizeof(dir_info_status)); - else - strlcpy(dir_info_status, "We have no recent usable consensus.", - sizeof(dir_info_status)); - res = 0; - goto done; - } - - if (should_delay_dir_fetches(get_options())) { - log_notice(LD_DIR, "no known bridge descriptors running yet; stalling"); - strlcpy(dir_info_status, "No live bridge descriptors.", - sizeof(dir_info_status)); - res = 0; - goto done; - } - - using_md = consensus->flavor == FLAV_MICRODESC; - - count_usable_descriptors(&num_present, &num_usable, consensus, options, now, - NULL, 0); - count_usable_descriptors(&num_exit_present, &num_exit_usable, - consensus, options, now, options->ExitNodes, 1); - -/* What fraction of desired server descriptors do we need before we will - * build circuits? */ -#define FRAC_USABLE_NEEDED .75 -/* What fraction of desired _exit_ server descriptors do we need before we - * will build circuits? */ -#define FRAC_EXIT_USABLE_NEEDED .5 - - if (num_present < num_usable * FRAC_USABLE_NEEDED) { - tor_snprintf(dir_info_status, sizeof(dir_info_status), - "We have only %d/%d usable %sdescriptors.", - num_present, num_usable, using_md ? "micro" : ""); - res = 0; - control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS, 0); - goto done; - } else if (num_present < 2) { - tor_snprintf(dir_info_status, sizeof(dir_info_status), - "Only %d %sdescriptor%s here and believed reachable!", - num_present, using_md ? "micro" : "", num_present ? "" : "s"); - res = 0; - goto done; - } else if (num_exit_present < num_exit_usable * FRAC_EXIT_USABLE_NEEDED) { - tor_snprintf(dir_info_status, sizeof(dir_info_status), - "We have only %d/%d usable exit node descriptors.", - num_exit_present, num_exit_usable); - res = 0; - control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS, 0); - goto done; - } - - /* Check for entry nodes. */ - if (options->EntryNodes) { - count_usable_descriptors(&num_present, &num_usable, consensus, options, - now, options->EntryNodes, 0); - - if (!num_usable || !num_present) { - tor_snprintf(dir_info_status, sizeof(dir_info_status), - "We have only %d/%d usable entry node %sdescriptors.", - num_present, num_usable, using_md?"micro":""); - res = 0; - goto done; - } - } - - res = 1; - - done: - if (res && !have_min_dir_info) { - log(LOG_NOTICE, LD_DIR, - "We now have enough directory information to build circuits."); - control_event_client_status(LOG_NOTICE, "ENOUGH_DIR_INFO"); - control_event_bootstrap(BOOTSTRAP_STATUS_CONN_OR, 0); - } - if (!res && have_min_dir_info) { - int quiet = directory_too_idle_to_fetch_descriptors(options, now); - log(quiet ? LOG_INFO : LOG_NOTICE, LD_DIR, - "Our directory information is no longer up-to-date " - "enough to build circuits: %s", dir_info_status); - - /* a) make us log when we next complete a circuit, so we know when Tor - * is back up and usable, and b) disable some activities that Tor - * should only do while circuits are working, like reachability tests - * and fetching bridge descriptors only over circuits. */ - can_complete_circuit = 0; - - control_event_client_status(LOG_NOTICE, "NOT_ENOUGH_DIR_INFO"); - } - have_min_dir_info = res; - need_to_update_have_min_dir_info = 0; -} - /** Reset the descriptor download failure count on all routers, so that we * can retry any long-failed routers immediately. */ @@ -5409,149 +4790,6 @@ routers_sort_by_identity(smartlist_t *routers) smartlist_sort(routers, _compare_routerinfo_by_id_digest); } -/** A routerset specifies constraints on a set of possible routerinfos, based - * on their names, identities, or addresses. It is optimized for determining - * whether a router is a member or not, in O(1+P) time, where P is the number - * of address policy constraints. */ -struct routerset_t { - /** A list of strings for the elements of the policy. Each string is either - * a nickname, a hexadecimal identity fingerprint, or an address policy. A - * router belongs to the set if its nickname OR its identity OR its address - * matches an entry here. */ - smartlist_t *list; - /** A map from lowercase nicknames of routers in the set to (void*)1 */ - strmap_t *names; - /** A map from identity digests routers in the set to (void*)1 */ - digestmap_t *digests; - /** An address policy for routers in the set. For implementation reasons, - * a router belongs to the set if it is _rejected_ by this policy. */ - smartlist_t *policies; - - /** A human-readable description of what this routerset is for. Used in - * log messages. */ - char *description; - - /** A list of the country codes in this set. */ - smartlist_t *country_names; - /** Total number of countries we knew about when we built <b>countries</b>.*/ - int n_countries; - /** Bit array mapping the return value of geoip_get_country() to 1 iff the - * country is a member of this routerset. Note that we MUST call - * routerset_refresh_countries() whenever the geoip country list is - * reloaded. */ - bitarray_t *countries; -}; - -/** Return a new empty routerset. */ -routerset_t * -routerset_new(void) -{ - routerset_t *result = tor_malloc_zero(sizeof(routerset_t)); - result->list = smartlist_new(); - result->names = strmap_new(); - result->digests = digestmap_new(); - result->policies = smartlist_new(); - result->country_names = smartlist_new(); - return result; -} - -/** If <b>c</b> is a country code in the form {cc}, return a newly allocated - * string holding the "cc" part. Else, return NULL. */ -static char * -routerset_get_countryname(const char *c) -{ - char *country; - - if (strlen(c) < 4 || c[0] !='{' || c[3] !='}') - return NULL; - - country = tor_strndup(c+1, 2); - tor_strlower(country); - return country; -} - -/** Update the routerset's <b>countries</b> bitarray_t. Called whenever - * the GeoIP database is reloaded. - */ -void -routerset_refresh_countries(routerset_t *target) -{ - int cc; - bitarray_free(target->countries); - - if (!geoip_is_loaded()) { - target->countries = NULL; - target->n_countries = 0; - return; - } - target->n_countries = geoip_get_n_countries(); - target->countries = bitarray_init_zero(target->n_countries); - SMARTLIST_FOREACH_BEGIN(target->country_names, const char *, country) { - cc = geoip_get_country(country); - if (cc >= 0) { - tor_assert(cc < target->n_countries); - bitarray_set(target->countries, cc); - } else { - log(LOG_WARN, LD_CONFIG, "Country code '%s' is not recognized.", - country); - } - } SMARTLIST_FOREACH_END(country); -} - -/** Parse the string <b>s</b> to create a set of routerset entries, and add - * them to <b>target</b>. In log messages, refer to the string as - * <b>description</b>. Return 0 on success, -1 on failure. - * - * Three kinds of elements are allowed in routersets: nicknames, IP address - * patterns, and fingerprints. They may be surrounded by optional space, and - * must be separated by commas. - */ -int -routerset_parse(routerset_t *target, const char *s, const char *description) -{ - int r = 0; - int added_countries = 0; - char *countryname; - smartlist_t *list = smartlist_new(); - smartlist_split_string(list, s, ",", - SPLIT_SKIP_SPACE | SPLIT_IGNORE_BLANK, 0); - SMARTLIST_FOREACH_BEGIN(list, char *, nick) { - addr_policy_t *p; - if (is_legal_hexdigest(nick)) { - char d[DIGEST_LEN]; - if (*nick == '$') - ++nick; - log_debug(LD_CONFIG, "Adding identity %s to %s", nick, description); - base16_decode(d, sizeof(d), nick, HEX_DIGEST_LEN); - digestmap_set(target->digests, d, (void*)1); - } else if (is_legal_nickname(nick)) { - log_debug(LD_CONFIG, "Adding nickname %s to %s", nick, description); - strmap_set_lc(target->names, nick, (void*)1); - } else if ((countryname = routerset_get_countryname(nick)) != NULL) { - log_debug(LD_CONFIG, "Adding country %s to %s", nick, - description); - smartlist_add(target->country_names, countryname); - added_countries = 1; - } else if ((strchr(nick,'.') || strchr(nick, '*')) && - (p = router_parse_addr_policy_item_from_string( - nick, ADDR_POLICY_REJECT))) { - log_debug(LD_CONFIG, "Adding address %s to %s", nick, description); - smartlist_add(target->policies, p); - } else { - log_warn(LD_CONFIG, "Entry '%s' in %s is misformed.", nick, - description); - r = -1; - tor_free(nick); - SMARTLIST_DEL_CURRENT(list, nick); - } - } SMARTLIST_FOREACH_END(nick); - smartlist_add_all(target->list, list); - smartlist_free(list); - if (added_countries) - routerset_refresh_countries(target); - return r; -} - /** Called when we change a node set, or when we reload the geoip list: * recompute all country info in all configuration node sets and in the * routerlist. */ @@ -5574,297 +4812,6 @@ refresh_all_country_info(void) nodelist_refresh_countries(); } -/** Add all members of the set <b>source</b> to <b>target</b>. */ -void -routerset_union(routerset_t *target, const routerset_t *source) -{ - char *s; - tor_assert(target); - if (!source || !source->list) - return; - s = routerset_to_string(source); - routerset_parse(target, s, "other routerset"); - tor_free(s); -} - -/** Return true iff <b>set</b> lists only nicknames and digests, and includes - * no IP ranges or countries. */ -int -routerset_is_list(const routerset_t *set) -{ - return smartlist_len(set->country_names) == 0 && - smartlist_len(set->policies) == 0; -} - -/** Return true iff we need a GeoIP IP-to-country database to make sense of - * <b>set</b>. */ -int -routerset_needs_geoip(const routerset_t *set) -{ - return set && smartlist_len(set->country_names); -} - -/** Return true iff there are no entries in <b>set</b>. */ -int -routerset_is_empty(const routerset_t *set) -{ - return !set || smartlist_len(set->list) == 0; -} - -/** Helper. Return true iff <b>set</b> contains a router based on the other - * provided fields. Return higher values for more specific subentries: a - * single router is more specific than an address range of routers, which is - * more specific in turn than a country code. - * - * (If country is -1, then we take the country - * from addr.) */ -static int -routerset_contains(const routerset_t *set, const tor_addr_t *addr, - uint16_t orport, - const char *nickname, const char *id_digest, - country_t country) -{ - if (!set || !set->list) - return 0; - if (nickname && strmap_get_lc(set->names, nickname)) - return 4; - if (id_digest && digestmap_get(set->digests, id_digest)) - return 4; - if (addr && compare_tor_addr_to_addr_policy(addr, orport, set->policies) - == ADDR_POLICY_REJECTED) - return 3; - if (set->countries) { - if (country < 0 && addr) - country = geoip_get_country_by_ip(tor_addr_to_ipv4h(addr)); - - if (country >= 0 && country < set->n_countries && - bitarray_is_set(set->countries, country)) - return 2; - } - return 0; -} - -/** Return true iff we can tell that <b>ei</b> is a member of <b>set</b>. */ -int -routerset_contains_extendinfo(const routerset_t *set, const extend_info_t *ei) -{ - return routerset_contains(set, - &ei->addr, - ei->port, - ei->nickname, - ei->identity_digest, - -1 /*country*/); -} - -/** Return true iff <b>ri</b> is in <b>set</b>. If country is <b>-1</b>, we - * look up the country. */ -int -routerset_contains_router(const routerset_t *set, const routerinfo_t *ri, - country_t country) -{ - tor_addr_t addr; - tor_addr_from_ipv4h(&addr, ri->addr); - return routerset_contains(set, - &addr, - ri->or_port, - ri->nickname, - ri->cache_info.identity_digest, - country); -} - -/** Return true iff <b>rs</b> is in <b>set</b>. If country is <b>-1</b>, we - * look up the country. */ -int -routerset_contains_routerstatus(const routerset_t *set, - const routerstatus_t *rs, - country_t country) -{ - tor_addr_t addr; - tor_addr_from_ipv4h(&addr, rs->addr); - return routerset_contains(set, - &addr, - rs->or_port, - rs->nickname, - rs->identity_digest, - country); -} - -/** Return true iff <b>node</b> is in <b>set</b>. */ -int -routerset_contains_node(const routerset_t *set, const node_t *node) -{ - if (node->rs) - return routerset_contains_routerstatus(set, node->rs, node->country); - else if (node->ri) - return routerset_contains_router(set, node->ri, node->country); - else - return 0; -} - -/** Add every known node_t that is a member of <b>routerset</b> to - * <b>out</b>, but never add any that are part of <b>excludeset</b>. - * If <b>running_only</b>, only add the running ones. */ -void -routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset, - const routerset_t *excludeset, int running_only) -{ /* XXXX MOVE */ - tor_assert(out); - if (!routerset || !routerset->list) - return; - - if (routerset_is_list(routerset)) { - /* No routers are specified by type; all are given by name or digest. - * we can do a lookup in O(len(routerset)). */ - SMARTLIST_FOREACH(routerset->list, const char *, name, { - const node_t *node = node_get_by_nickname(name, 1); - if (node) { - if (!running_only || node->is_running) - if (!routerset_contains_node(excludeset, node)) - smartlist_add(out, (void*)node); - } - }); - } else { - /* We need to iterate over the routerlist to get all the ones of the - * right kind. */ - smartlist_t *nodes = nodelist_get_list(); - SMARTLIST_FOREACH(nodes, const node_t *, node, { - if (running_only && !node->is_running) - continue; - if (routerset_contains_node(routerset, node) && - !routerset_contains_node(excludeset, node)) - smartlist_add(out, (void*)node); - }); - } -} - -#if 0 -/** Add to <b>target</b> every node_t from <b>source</b> except: - * - * 1) Don't add it if <b>include</b> is non-empty and the relay isn't in - * <b>include</b>; and - * 2) Don't add it if <b>exclude</b> is non-empty and the relay is - * excluded in a more specific fashion by <b>exclude</b>. - * 3) If <b>running_only</b>, don't add non-running routers. - */ -void -routersets_get_node_disjunction(smartlist_t *target, - const smartlist_t *source, - const routerset_t *include, - const routerset_t *exclude, int running_only) -{ - SMARTLIST_FOREACH(source, const node_t *, node, { - int include_result; - if (running_only && !node->is_running) - continue; - if (!routerset_is_empty(include)) - include_result = routerset_contains_node(include, node); - else - include_result = 1; - - if (include_result) { - int exclude_result = routerset_contains_node(exclude, node); - if (include_result >= exclude_result) - smartlist_add(target, (void*)node); - } - }); -} -#endif - -/** Remove every node_t from <b>lst</b> that is in <b>routerset</b>. */ -void -routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset) -{ /*XXXX MOVE ? */ - tor_assert(lst); - if (!routerset) - return; - SMARTLIST_FOREACH(lst, const node_t *, node, { - if (routerset_contains_node(routerset, node)) { - //log_debug(LD_DIR, "Subtracting %s",r->nickname); - SMARTLIST_DEL_CURRENT(lst, node); - } - }); -} - -/** Return a new string that when parsed by routerset_parse_string() will - * yield <b>set</b>. */ -char * -routerset_to_string(const routerset_t *set) -{ - if (!set || !set->list) - return tor_strdup(""); - return smartlist_join_strings(set->list, ",", 0, NULL); -} - -/** Helper: return true iff old and new are both NULL, or both non-NULL - * equal routersets. */ -int -routerset_equal(const routerset_t *old, const routerset_t *new) -{ - if (routerset_is_empty(old) && routerset_is_empty(new)) { - /* Two empty sets are equal */ - return 1; - } else if (routerset_is_empty(old) || routerset_is_empty(new)) { - /* An empty set is equal to nothing else. */ - return 0; - } - tor_assert(old != NULL); - tor_assert(new != NULL); - - if (smartlist_len(old->list) != smartlist_len(new->list)) - return 0; - - SMARTLIST_FOREACH(old->list, const char *, cp1, { - const char *cp2 = smartlist_get(new->list, cp1_sl_idx); - if (strcmp(cp1, cp2)) - return 0; - }); - - return 1; -} - -/** Free all storage held in <b>routerset</b>. */ -void -routerset_free(routerset_t *routerset) -{ - if (!routerset) - return; - - SMARTLIST_FOREACH(routerset->list, char *, cp, tor_free(cp)); - smartlist_free(routerset->list); - SMARTLIST_FOREACH(routerset->policies, addr_policy_t *, p, - addr_policy_free(p)); - smartlist_free(routerset->policies); - SMARTLIST_FOREACH(routerset->country_names, char *, cp, tor_free(cp)); - smartlist_free(routerset->country_names); - - strmap_free(routerset->names, NULL); - digestmap_free(routerset->digests, NULL); - bitarray_free(routerset->countries); - tor_free(routerset); -} - -/** Refresh the country code of <b>ri</b>. This function MUST be called on - * each router when the GeoIP database is reloaded, and on all new routers. */ -void -node_set_country(node_t *node) -{ - if (node->rs) - node->country = geoip_get_country_by_ip(node->rs->addr); - else if (node->ri) - node->country = geoip_get_country_by_ip(node->ri->addr); - else - node->country = -1; -} - -/** Set the country code of all routers in the routerlist. */ -void -nodelist_refresh_countries(void) /* MOVE */ -{ - smartlist_t *nodes = nodelist_get_list(); - SMARTLIST_FOREACH(nodes, node_t *, node, - node_set_country(node)); -} - /** Determine the routers that are responsible for <b>id</b> (binary) and * add pointers to those routers' routerstatus_t to <b>responsible_dirs</b>. * Return -1 if we're returning an empty smartlist, else return 0. diff --git a/src/or/routerlist.h b/src/or/routerlist.h index ab58b9ee5a..58143010b3 100644 --- a/src/or/routerlist.h +++ b/src/or/routerlist.h @@ -39,10 +39,6 @@ void router_reset_status_download_failures(void); int routers_have_same_or_addrs(const routerinfo_t *r1, const routerinfo_t *r2); int router_nickname_is_in_list(const routerinfo_t *router, const char *list); const routerinfo_t *routerlist_find_my_routerinfo(void); -const node_t *router_find_exact_exit_enclave(const char *address, - uint16_t port); -int node_is_unreliable(const node_t *router, int need_uptime, - int need_capacity, int need_guard); uint32_t router_get_advertised_bandwidth(const routerinfo_t *router); uint32_t router_get_advertised_bandwidth_capped(const routerinfo_t *router); @@ -53,8 +49,6 @@ const node_t *router_choose_random_node(smartlist_t *excludedsmartlist, struct routerset_t *excludedset, router_crn_flags_t flags); -const routerinfo_t *router_get_by_nickname(const char *nickname, - int warn_if_unnamed); int router_is_named(const routerinfo_t *router); int router_digest_is_trusted_dir_type(const char *digest, dirinfo_type_t type); @@ -63,7 +57,6 @@ int router_digest_is_trusted_dir_type(const char *digest, int router_addr_is_trusted_dir(uint32_t addr); int hexdigest_to_digest(const char *hexdigest, char *digest); -const routerinfo_t *router_get_by_hexdigest(const char *hexdigest); const routerinfo_t *router_get_by_id_digest(const char *digest); routerinfo_t *router_get_mutable_by_digest(const char *digest); signed_descriptor_t *router_get_by_descriptor_digest(const char *digest); @@ -80,7 +73,6 @@ void routerlist_remove(routerlist_t *rl, routerinfo_t *ri, int make_old, time_t now); void routerlist_free_all(void); void routerlist_reset_warnings(void); -void router_set_status(const char *digest, int up); static int WRA_WAS_ADDED(was_router_added_t s); static int WRA_WAS_OUTDATED(was_router_added_t s); @@ -133,8 +125,6 @@ void router_load_extrainfo_from_string(const char *s, const char *eos, int descriptor_digests); void routerlist_retry_directory_downloads(time_t now); -int router_exit_policy_all_nodes_reject(const tor_addr_t *addr, uint16_t port, - int need_uptime); int router_exit_policy_rejects_all(const routerinfo_t *router); trusted_dir_server_t *add_trusted_dir_server(const char *nickname, @@ -150,10 +140,6 @@ void update_consensus_router_descriptor_downloads(time_t now, int is_vote, void update_router_descriptor_downloads(time_t now); void update_all_descriptor_downloads(time_t now); void update_extrainfo_downloads(time_t now); -int router_have_minimum_dir_info(void); -void router_dir_info_changed(void); -const char *get_dir_info_status_string(void); -int count_loading_descriptors_progress(void); void router_reset_descriptor_download_failures(void); int router_differences_are_cosmetic(const routerinfo_t *r1, const routerinfo_t *r2); @@ -166,38 +152,6 @@ void routerlist_assert_ok(const routerlist_t *rl); const char *esc_router_info(const routerinfo_t *router); void routers_sort_by_identity(smartlist_t *routers); -routerset_t *routerset_new(void); -void routerset_refresh_countries(routerset_t *rs); -int routerset_parse(routerset_t *target, const char *s, - const char *description); -void routerset_union(routerset_t *target, const routerset_t *source); -int routerset_is_list(const routerset_t *set); -int routerset_needs_geoip(const routerset_t *set); -int routerset_is_empty(const routerset_t *set); -int routerset_contains_router(const routerset_t *set, const routerinfo_t *ri, - country_t country); -int routerset_contains_routerstatus(const routerset_t *set, - const routerstatus_t *rs, - country_t country); -int routerset_contains_extendinfo(const routerset_t *set, - const extend_info_t *ei); - -int routerset_contains_node(const routerset_t *set, const node_t *node); -void routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset, - const routerset_t *excludeset, - int running_only); -#if 0 -void routersets_get_node_disjunction(smartlist_t *target, - const smartlist_t *source, - const routerset_t *include, - const routerset_t *exclude, int running_only); -#endif -void routerset_subtract_nodes(smartlist_t *out, - const routerset_t *routerset); - -char *routerset_to_string(const routerset_t *routerset); -int routerset_equal(const routerset_t *old, const routerset_t *new); -void routerset_free(routerset_t *routerset); void refresh_all_country_info(void); int hid_serv_get_responsible_directories(smartlist_t *responsible_dirs, @@ -215,6 +169,9 @@ int hex_digest_nickname_decode(const char *hexdigest, char *digest_out, char *nickname_qualifier_out, char *nickname_out); +int hex_digest_nickname_matches(const char *hexdigest, + const char *identity_digest, + const char *nickname, int is_named); #ifdef ROUTERLIST_PRIVATE /** Helper type for choosing routers by bandwidth: contains a union of diff --git a/src/or/routerset.c b/src/or/routerset.c new file mode 100644 index 0000000000..263cf79d70 --- /dev/null +++ b/src/or/routerset.c @@ -0,0 +1,426 @@ +/* Copyright (c) 2001 Matej Pfajfar. + * Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2012, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#include "or.h" +#include "geoip.h" +#include "nodelist.h" +#include "policies.h" +#include "router.h" +#include "routerparse.h" +#include "routerset.h" + +/** A routerset specifies constraints on a set of possible routerinfos, based + * on their names, identities, or addresses. It is optimized for determining + * whether a router is a member or not, in O(1+P) time, where P is the number + * of address policy constraints. */ +struct routerset_t { + /** A list of strings for the elements of the policy. Each string is either + * a nickname, a hexadecimal identity fingerprint, or an address policy. A + * router belongs to the set if its nickname OR its identity OR its address + * matches an entry here. */ + smartlist_t *list; + /** A map from lowercase nicknames of routers in the set to (void*)1 */ + strmap_t *names; + /** A map from identity digests routers in the set to (void*)1 */ + digestmap_t *digests; + /** An address policy for routers in the set. For implementation reasons, + * a router belongs to the set if it is _rejected_ by this policy. */ + smartlist_t *policies; + + /** A human-readable description of what this routerset is for. Used in + * log messages. */ + char *description; + + /** A list of the country codes in this set. */ + smartlist_t *country_names; + /** Total number of countries we knew about when we built <b>countries</b>.*/ + int n_countries; + /** Bit array mapping the return value of geoip_get_country() to 1 iff the + * country is a member of this routerset. Note that we MUST call + * routerset_refresh_countries() whenever the geoip country list is + * reloaded. */ + bitarray_t *countries; +}; + +/** Return a new empty routerset. */ +routerset_t * +routerset_new(void) +{ + routerset_t *result = tor_malloc_zero(sizeof(routerset_t)); + result->list = smartlist_new(); + result->names = strmap_new(); + result->digests = digestmap_new(); + result->policies = smartlist_new(); + result->country_names = smartlist_new(); + return result; +} + +/** If <b>c</b> is a country code in the form {cc}, return a newly allocated + * string holding the "cc" part. Else, return NULL. */ +static char * +routerset_get_countryname(const char *c) +{ + char *country; + + if (strlen(c) < 4 || c[0] !='{' || c[3] !='}') + return NULL; + + country = tor_strndup(c+1, 2); + tor_strlower(country); + return country; +} + +/** Update the routerset's <b>countries</b> bitarray_t. Called whenever + * the GeoIP database is reloaded. + */ +void +routerset_refresh_countries(routerset_t *target) +{ + int cc; + bitarray_free(target->countries); + + if (!geoip_is_loaded()) { + target->countries = NULL; + target->n_countries = 0; + return; + } + target->n_countries = geoip_get_n_countries(); + target->countries = bitarray_init_zero(target->n_countries); + SMARTLIST_FOREACH_BEGIN(target->country_names, const char *, country) { + cc = geoip_get_country(country); + if (cc >= 0) { + tor_assert(cc < target->n_countries); + bitarray_set(target->countries, cc); + } else { + log(LOG_WARN, LD_CONFIG, "Country code '%s' is not recognized.", + country); + } + } SMARTLIST_FOREACH_END(country); +} + +/** Parse the string <b>s</b> to create a set of routerset entries, and add + * them to <b>target</b>. In log messages, refer to the string as + * <b>description</b>. Return 0 on success, -1 on failure. + * + * Three kinds of elements are allowed in routersets: nicknames, IP address + * patterns, and fingerprints. They may be surrounded by optional space, and + * must be separated by commas. + */ +int +routerset_parse(routerset_t *target, const char *s, const char *description) +{ + int r = 0; + int added_countries = 0; + char *countryname; + smartlist_t *list = smartlist_new(); + smartlist_split_string(list, s, ",", + SPLIT_SKIP_SPACE | SPLIT_IGNORE_BLANK, 0); + SMARTLIST_FOREACH_BEGIN(list, char *, nick) { + addr_policy_t *p; + if (is_legal_hexdigest(nick)) { + char d[DIGEST_LEN]; + if (*nick == '$') + ++nick; + log_debug(LD_CONFIG, "Adding identity %s to %s", nick, description); + base16_decode(d, sizeof(d), nick, HEX_DIGEST_LEN); + digestmap_set(target->digests, d, (void*)1); + } else if (is_legal_nickname(nick)) { + log_debug(LD_CONFIG, "Adding nickname %s to %s", nick, description); + strmap_set_lc(target->names, nick, (void*)1); + } else if ((countryname = routerset_get_countryname(nick)) != NULL) { + log_debug(LD_CONFIG, "Adding country %s to %s", nick, + description); + smartlist_add(target->country_names, countryname); + added_countries = 1; + } else if ((strchr(nick,'.') || strchr(nick, '*')) && + (p = router_parse_addr_policy_item_from_string( + nick, ADDR_POLICY_REJECT))) { + log_debug(LD_CONFIG, "Adding address %s to %s", nick, description); + smartlist_add(target->policies, p); + } else { + log_warn(LD_CONFIG, "Entry '%s' in %s is misformed.", nick, + description); + r = -1; + tor_free(nick); + SMARTLIST_DEL_CURRENT(list, nick); + } + } SMARTLIST_FOREACH_END(nick); + smartlist_add_all(target->list, list); + smartlist_free(list); + if (added_countries) + routerset_refresh_countries(target); + return r; +} + +/** Add all members of the set <b>source</b> to <b>target</b>. */ +void +routerset_union(routerset_t *target, const routerset_t *source) +{ + char *s; + tor_assert(target); + if (!source || !source->list) + return; + s = routerset_to_string(source); + routerset_parse(target, s, "other routerset"); + tor_free(s); +} + +/** Return true iff <b>set</b> lists only nicknames and digests, and includes + * no IP ranges or countries. */ +int +routerset_is_list(const routerset_t *set) +{ + return smartlist_len(set->country_names) == 0 && + smartlist_len(set->policies) == 0; +} + +/** Return true iff we need a GeoIP IP-to-country database to make sense of + * <b>set</b>. */ +int +routerset_needs_geoip(const routerset_t *set) +{ + return set && smartlist_len(set->country_names); +} + +/** Return true iff there are no entries in <b>set</b>. */ +int +routerset_is_empty(const routerset_t *set) +{ + return !set || smartlist_len(set->list) == 0; +} + +/** Helper. Return true iff <b>set</b> contains a router based on the other + * provided fields. Return higher values for more specific subentries: a + * single router is more specific than an address range of routers, which is + * more specific in turn than a country code. + * + * (If country is -1, then we take the country + * from addr.) */ +static int +routerset_contains(const routerset_t *set, const tor_addr_t *addr, + uint16_t orport, + const char *nickname, const char *id_digest, + country_t country) +{ + if (!set || !set->list) + return 0; + if (nickname && strmap_get_lc(set->names, nickname)) + return 4; + if (id_digest && digestmap_get(set->digests, id_digest)) + return 4; + if (addr && compare_tor_addr_to_addr_policy(addr, orport, set->policies) + == ADDR_POLICY_REJECTED) + return 3; + if (set->countries) { + if (country < 0 && addr) + country = geoip_get_country_by_ip(tor_addr_to_ipv4h(addr)); + + if (country >= 0 && country < set->n_countries && + bitarray_is_set(set->countries, country)) + return 2; + } + return 0; +} + +/** Return true iff we can tell that <b>ei</b> is a member of <b>set</b>. */ +int +routerset_contains_extendinfo(const routerset_t *set, const extend_info_t *ei) +{ + return routerset_contains(set, + &ei->addr, + ei->port, + ei->nickname, + ei->identity_digest, + -1 /*country*/); +} + +/** Return true iff <b>ri</b> is in <b>set</b>. If country is <b>-1</b>, we + * look up the country. */ +int +routerset_contains_router(const routerset_t *set, const routerinfo_t *ri, + country_t country) +{ + tor_addr_t addr; + tor_addr_from_ipv4h(&addr, ri->addr); + return routerset_contains(set, + &addr, + ri->or_port, + ri->nickname, + ri->cache_info.identity_digest, + country); +} + +/** Return true iff <b>rs</b> is in <b>set</b>. If country is <b>-1</b>, we + * look up the country. */ +int +routerset_contains_routerstatus(const routerset_t *set, + const routerstatus_t *rs, + country_t country) +{ + tor_addr_t addr; + tor_addr_from_ipv4h(&addr, rs->addr); + return routerset_contains(set, + &addr, + rs->or_port, + rs->nickname, + rs->identity_digest, + country); +} + +/** Return true iff <b>node</b> is in <b>set</b>. */ +int +routerset_contains_node(const routerset_t *set, const node_t *node) +{ + if (node->rs) + return routerset_contains_routerstatus(set, node->rs, node->country); + else if (node->ri) + return routerset_contains_router(set, node->ri, node->country); + else + return 0; +} + +/** Add every known node_t that is a member of <b>routerset</b> to + * <b>out</b>, but never add any that are part of <b>excludeset</b>. + * If <b>running_only</b>, only add the running ones. */ +void +routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset, + const routerset_t *excludeset, int running_only) +{ + tor_assert(out); + if (!routerset || !routerset->list) + return; + + if (routerset_is_list(routerset)) { + /* No routers are specified by type; all are given by name or digest. + * we can do a lookup in O(len(routerset)). */ + SMARTLIST_FOREACH(routerset->list, const char *, name, { + const node_t *node = node_get_by_nickname(name, 1); + if (node) { + if (!running_only || node->is_running) + if (!routerset_contains_node(excludeset, node)) + smartlist_add(out, (void*)node); + } + }); + } else { + /* We need to iterate over the routerlist to get all the ones of the + * right kind. */ + smartlist_t *nodes = nodelist_get_list(); + SMARTLIST_FOREACH(nodes, const node_t *, node, { + if (running_only && !node->is_running) + continue; + if (routerset_contains_node(routerset, node) && + !routerset_contains_node(excludeset, node)) + smartlist_add(out, (void*)node); + }); + } +} + +#if 0 +/** Add to <b>target</b> every node_t from <b>source</b> except: + * + * 1) Don't add it if <b>include</b> is non-empty and the relay isn't in + * <b>include</b>; and + * 2) Don't add it if <b>exclude</b> is non-empty and the relay is + * excluded in a more specific fashion by <b>exclude</b>. + * 3) If <b>running_only</b>, don't add non-running routers. + */ +void +routersets_get_node_disjunction(smartlist_t *target, + const smartlist_t *source, + const routerset_t *include, + const routerset_t *exclude, int running_only) +{ + SMARTLIST_FOREACH(source, const node_t *, node, { + int include_result; + if (running_only && !node->is_running) + continue; + if (!routerset_is_empty(include)) + include_result = routerset_contains_node(include, node); + else + include_result = 1; + + if (include_result) { + int exclude_result = routerset_contains_node(exclude, node); + if (include_result >= exclude_result) + smartlist_add(target, (void*)node); + } + }); +} +#endif + +/** Remove every node_t from <b>lst</b> that is in <b>routerset</b>. */ +void +routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset) +{ + tor_assert(lst); + if (!routerset) + return; + SMARTLIST_FOREACH(lst, const node_t *, node, { + if (routerset_contains_node(routerset, node)) { + //log_debug(LD_DIR, "Subtracting %s",r->nickname); + SMARTLIST_DEL_CURRENT(lst, node); + } + }); +} + +/** Return a new string that when parsed by routerset_parse_string() will + * yield <b>set</b>. */ +char * +routerset_to_string(const routerset_t *set) +{ + if (!set || !set->list) + return tor_strdup(""); + return smartlist_join_strings(set->list, ",", 0, NULL); +} + +/** Helper: return true iff old and new are both NULL, or both non-NULL + * equal routersets. */ +int +routerset_equal(const routerset_t *old, const routerset_t *new) +{ + if (routerset_is_empty(old) && routerset_is_empty(new)) { + /* Two empty sets are equal */ + return 1; + } else if (routerset_is_empty(old) || routerset_is_empty(new)) { + /* An empty set is equal to nothing else. */ + return 0; + } + tor_assert(old != NULL); + tor_assert(new != NULL); + + if (smartlist_len(old->list) != smartlist_len(new->list)) + return 0; + + SMARTLIST_FOREACH(old->list, const char *, cp1, { + const char *cp2 = smartlist_get(new->list, cp1_sl_idx); + if (strcmp(cp1, cp2)) + return 0; + }); + + return 1; +} + +/** Free all storage held in <b>routerset</b>. */ +void +routerset_free(routerset_t *routerset) +{ + if (!routerset) + return; + + SMARTLIST_FOREACH(routerset->list, char *, cp, tor_free(cp)); + smartlist_free(routerset->list); + SMARTLIST_FOREACH(routerset->policies, addr_policy_t *, p, + addr_policy_free(p)); + smartlist_free(routerset->policies); + SMARTLIST_FOREACH(routerset->country_names, char *, cp, tor_free(cp)); + smartlist_free(routerset->country_names); + + strmap_free(routerset->names, NULL); + digestmap_free(routerset->digests, NULL); + bitarray_free(routerset->countries); + tor_free(routerset); +} + diff --git a/src/or/routerset.h b/src/or/routerset.h new file mode 100644 index 0000000000..ad0832e4df --- /dev/null +++ b/src/or/routerset.h @@ -0,0 +1,48 @@ +/* Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2012, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file routerlist.h + * \brief Header file for routerset.c + **/ + +#ifndef TOR_ROUTERSET_H +#define TOR_ROUTERSET_H + +routerset_t *routerset_new(void); +void routerset_refresh_countries(routerset_t *rs); +int routerset_parse(routerset_t *target, const char *s, + const char *description); +void routerset_union(routerset_t *target, const routerset_t *source); +int routerset_is_list(const routerset_t *set); +int routerset_needs_geoip(const routerset_t *set); +int routerset_is_empty(const routerset_t *set); +int routerset_contains_router(const routerset_t *set, const routerinfo_t *ri, + country_t country); +int routerset_contains_routerstatus(const routerset_t *set, + const routerstatus_t *rs, + country_t country); +int routerset_contains_extendinfo(const routerset_t *set, + const extend_info_t *ei); + +int routerset_contains_node(const routerset_t *set, const node_t *node); +void routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset, + const routerset_t *excludeset, + int running_only); +#if 0 +void routersets_get_node_disjunction(smartlist_t *target, + const smartlist_t *source, + const routerset_t *include, + const routerset_t *exclude, int running_only); +#endif +void routerset_subtract_nodes(smartlist_t *out, + const routerset_t *routerset); + +char *routerset_to_string(const routerset_t *routerset); +int routerset_equal(const routerset_t *old, const routerset_t *new); +void routerset_free(routerset_t *routerset); + +#endif + |