/* 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 countries.*/ 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 c 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 countries 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(AF_INET)) { 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 s to create a set of routerset entries, and add * them to target. In log messages, refer to the string as * description. 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 source to target. */ 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 set 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 * set. */ int routerset_needs_geoip(const routerset_t *set) { return set && smartlist_len(set->country_names); } /** Return true iff there are no entries in set. */ int routerset_is_empty(const routerset_t *set) { return !set || smartlist_len(set->list) == 0; } /** Helper. Return true iff set 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_addr(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 ei is a member of set. */ 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 ri is in set. If country is -1, 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 rs is in set. If country is -1, 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 node is in set. */ 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 routerset to * out, but never add any that are part of excludeset. * If running_only, 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 target every node_t from source except: * * 1) Don't add it if include is non-empty and the relay isn't in * include; and * 2) Don't add it if exclude is non-empty and the relay is * excluded in a more specific fashion by exclude. * 3) If running_only, 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 lst that is in routerset. */ 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 set. */ 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 routerset. */ 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); }