Split the routerset code out of routerlist.c

1 files changed, 426 insertions, 0 deletions

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);
+}
+