src/or/routerset.c

   1 /* Copyright (c) 2001 Matej Pfajfar.
   2  * Copyright (c) 2001-2004, Roger Dingledine.
   3  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
   4  * Copyright (c) 2007-2013, The Tor Project, Inc. */
   5 /* See LICENSE for licensing information */
   6
   7 #include "or.h"
   8 #include "geoip.h"
   9 #include "nodelist.h"
  10 #include "policies.h"
  11 #include "router.h"
  12 #include "routerparse.h"
  13 #include "routerset.h"
  14
  15 /** A routerset specifies constraints on a set of possible routerinfos, based
  16  * on their names, identities, or addresses.  It is optimized for determining
  17  * whether a router is a member or not, in O(1+P) time, where P is the number
  18  * of address policy constraints. */
  19 struct routerset_t {
  20   /** A list of strings for the elements of the policy.  Each string is either
  21    * a nickname, a hexadecimal identity fingerprint, or an address policy.  A
  22    * router belongs to the set if its nickname OR its identity OR its address
  23    * matches an entry here. */
  24   smartlist_t *list;
  25   /** A map from lowercase nicknames of routers in the set to (void*)1 */
  26   strmap_t *names;
  27   /** A map from identity digests routers in the set to (void*)1 */
  28   digestmap_t *digests;
  29   /** An address policy for routers in the set.  For implementation reasons,
  30    * a router belongs to the set if it is _rejected_ by this policy. */
  31   smartlist_t *policies;
  32
  33   /** A human-readable description of what this routerset is for.  Used in
  34    * log messages. */
  35   char *description;
  36
  37   /** A list of the country codes in this set. */
  38   smartlist_t *country_names;
  39   /** Total number of countries we knew about when we built <b>countries</b>.*/
  40   int n_countries;
  41   /** Bit array mapping the return value of geoip_get_country() to 1 iff the
  42    * country is a member of this routerset.  Note that we MUST call
  43    * routerset_refresh_countries() whenever the geoip country list is
  44    * reloaded. */
  45   bitarray_t *countries;
  46 };
  47
  48 /** Return a new empty routerset. */
  49 routerset_t *
  50 routerset_new(void)
  51 {
  52   routerset_t *result = tor_malloc_zero(sizeof(routerset_t));
  53   result->list = smartlist_new();
  54   result->names = strmap_new();
  55   result->digests = digestmap_new();
  56   result->policies = smartlist_new();
  57   result->country_names = smartlist_new();
  58   return result;
  59 }
  60
  61 /** If <b>c</b> is a country code in the form {cc}, return a newly allocated
  62  * string holding the "cc" part.  Else, return NULL. */
  63 static char *
  64 routerset_get_countryname(const char *c)
  65 {
  66   char *country;
  67
  68   if (strlen(c) < 4 || c[0] !='{' || c[3] !='}')
  69     return NULL;
  70
  71   country = tor_strndup(c+1, 2);
  72   tor_strlower(country);
  73   return country;
  74 }
  75
  76 /** Update the routerset's <b>countries</b> bitarray_t. Called whenever
  77  * the GeoIP IPv4 database is reloaded.
  78  */
  79 void
  80 routerset_refresh_countries(routerset_t *target)
  81 {
  82   int cc;
  83   bitarray_free(target->countries);
  84
  85   if (!geoip_is_loaded(AF_INET)) {
  86     target->countries = NULL;
  87     target->n_countries = 0;
  88     return;
  89   }
  90   target->n_countries = geoip_get_n_countries();
  91   target->countries = bitarray_init_zero(target->n_countries);
  92   SMARTLIST_FOREACH_BEGIN(target->country_names, const char *, country) {
  93     cc = geoip_get_country(country);
  94     if (cc >= 0) {
  95       tor_assert(cc < target->n_countries);
  96       bitarray_set(target->countries, cc);
  97     } else {
  98       log_warn(LD_CONFIG, "Country code '%s' is not recognized.",
  99           country);
 100     }
 101   } SMARTLIST_FOREACH_END(country);
 102 }
 103
 104 /** Parse the string <b>s</b> to create a set of routerset entries, and add
 105  * them to <b>target</b>.  In log messages, refer to the string as
 106  * <b>description</b>.  Return 0 on success, -1 on failure.
 107  *
 108  * Three kinds of elements are allowed in routersets: nicknames, IP address
 109  * patterns, and fingerprints.  They may be surrounded by optional space, and
 110  * must be separated by commas.
 111  */
 112 int
 113 routerset_parse(routerset_t *target, const char *s, const char *description)
 114 {
 115   int r = 0;
 116   int added_countries = 0;
 117   char *countryname;
 118   smartlist_t *list = smartlist_new();
 119   smartlist_split_string(list, s, ",",
 120                          SPLIT_SKIP_SPACE | SPLIT_IGNORE_BLANK, 0);
 121   SMARTLIST_FOREACH_BEGIN(list, char *, nick) {
 122       addr_policy_t *p;
 123       if (is_legal_hexdigest(nick)) {
 124         char d[DIGEST_LEN];
 125         if (*nick == '$')
 126           ++nick;
 127         log_debug(LD_CONFIG, "Adding identity %s to %s", nick, description);
 128         base16_decode(d, sizeof(d), nick, HEX_DIGEST_LEN);
 129         digestmap_set(target->digests, d, (void*)1);
 130       } else if (is_legal_nickname(nick)) {
 131         log_debug(LD_CONFIG, "Adding nickname %s to %s", nick, description);
 132         strmap_set_lc(target->names, nick, (void*)1);
 133       } else if ((countryname = routerset_get_countryname(nick)) != NULL) {
 134         log_debug(LD_CONFIG, "Adding country %s to %s", nick,
 135                   description);
 136         smartlist_add(target->country_names, countryname);
 137         added_countries = 1;
 138       } else if ((strchr(nick,'.') || strchr(nick, '*')) &&
 139                  (p = router_parse_addr_policy_item_from_string(
 140                                      nick, ADDR_POLICY_REJECT))) {
 141         log_debug(LD_CONFIG, "Adding address %s to %s", nick, description);
 142         smartlist_add(target->policies, p);
 143       } else {
 144         log_warn(LD_CONFIG, "Entry '%s' in %s is malformed.", nick,
 145                  description);
 146         r = -1;
 147         tor_free(nick);
 148         SMARTLIST_DEL_CURRENT(list, nick);
 149       }
 150   } SMARTLIST_FOREACH_END(nick);
 151   policy_expand_unspec(&target->policies);
 152   smartlist_add_all(target->list, list);
 153   smartlist_free(list);
 154   if (added_countries)
 155     routerset_refresh_countries(target);
 156   return r;
 157 }
 158
 159 /** Add all members of the set <b>source</b> to <b>target</b>. */
 160 void
 161 routerset_union(routerset_t *target, const routerset_t *source)
 162 {
 163   char *s;
 164   tor_assert(target);
 165   if (!source || !source->list)
 166     return;
 167   s = routerset_to_string(source);
 168   routerset_parse(target, s, "other routerset");
 169   tor_free(s);
 170 }
 171
 172 /** Return true iff <b>set</b> lists only nicknames and digests, and includes
 173  * no IP ranges or countries. */
 174 int
 175 routerset_is_list(const routerset_t *set)
 176 {
 177   return smartlist_len(set->country_names) == 0 &&
 178     smartlist_len(set->policies) == 0;
 179 }
 180
 181 /** Return true iff we need a GeoIP IP-to-country database to make sense of
 182  * <b>set</b>. */
 183 int
 184 routerset_needs_geoip(const routerset_t *set)
 185 {
 186   return set && smartlist_len(set->country_names);
 187 }
 188
 189 /** Return true iff there are no entries in <b>set</b>. */
 190 int
 191 routerset_is_empty(const routerset_t *set)
 192 {
 193   return !set || smartlist_len(set->list) == 0;
 194 }
 195
 196 /** Helper.  Return true iff <b>set</b> contains a router based on the other
 197  * provided fields.  Return higher values for more specific subentries: a
 198  * single router is more specific than an address range of routers, which is
 199  * more specific in turn than a country code.
 200  *
 201  * (If country is -1, then we take the country
 202  * from addr.) */
 203 static int
 204 routerset_contains(const routerset_t *set, const tor_addr_t *addr,
 205                    uint16_t orport,
 206                    const char *nickname, const char *id_digest,
 207                    country_t country)
 208 {
 209   if (!set || !set->list)
 210     return 0;
 211   if (nickname && strmap_get_lc(set->names, nickname))
 212     return 4;
 213   if (id_digest && digestmap_get(set->digests, id_digest))
 214     return 4;
 215   if (addr && compare_tor_addr_to_addr_policy(addr, orport, set->policies)
 216       == ADDR_POLICY_REJECTED)
 217     return 3;
 218   if (set->countries) {
 219     if (country < 0 && addr)
 220       country = geoip_get_country_by_addr(addr);
 221
 222     if (country >= 0 && country < set->n_countries &&
 223         bitarray_is_set(set->countries, country))
 224       return 2;
 225   }
 226   return 0;
 227 }
 228
 229 /** If *<b>setp</b> includes at least one country code, or if
 230  * <b>only_some_cc_set</b> is 0, add the ?? and A1 country codes to
 231  * *<b>setp</b>, creating it as needed.  Return true iff *<b>setp</b> changed.
 232  */
 233 int
 234 routerset_add_unknown_ccs(routerset_t **setp, int only_if_some_cc_set)
 235 {
 236   routerset_t *set;
 237   int add_unknown, add_a1;
 238   if (only_if_some_cc_set) {
 239     if (!*setp || smartlist_len((*setp)->country_names) == 0)
 240       return 0;
 241   }
 242   if (!*setp)
 243     *setp = routerset_new();
 244
 245   set = *setp;
 246
 247   add_unknown = ! smartlist_contains_string_case(set->country_names, "??") &&
 248     geoip_get_country("??") >= 0;
 249   add_a1 = ! smartlist_contains_string_case(set->country_names, "a1") &&
 250     geoip_get_country("A1") >= 0;
 251
 252   if (add_unknown) {
 253     smartlist_add(set->country_names, tor_strdup("??"));
 254     smartlist_add(set->list, tor_strdup("{??}"));
 255   }
 256   if (add_a1) {
 257     smartlist_add(set->country_names, tor_strdup("a1"));
 258     smartlist_add(set->list, tor_strdup("{a1}"));
 259   }
 260
 261   if (add_unknown || add_a1) {
 262     routerset_refresh_countries(set);
 263     return 1;
 264   }
 265   return 0;
 266 }
 267
 268 /** Return true iff we can tell that <b>ei</b> is a member of <b>set</b>. */
 269 int
 270 routerset_contains_extendinfo(const routerset_t *set, const extend_info_t *ei)
 271 {
 272   return routerset_contains(set,
 273                             &ei->addr,
 274                             ei->port,
 275                             ei->nickname,
 276                             ei->identity_digest,
 277                             -1 /*country*/);
 278 }
 279
 280 /** Return true iff <b>ri</b> is in <b>set</b>.  If country is <b>-1</b>, we
 281  * look up the country. */
 282 int
 283 routerset_contains_router(const routerset_t *set, const routerinfo_t *ri,
 284                           country_t country)
 285 {
 286   tor_addr_t addr;
 287   tor_addr_from_ipv4h(&addr, ri->addr);
 288   return routerset_contains(set,
 289                             &addr,
 290                             ri->or_port,
 291                             ri->nickname,
 292                             ri->cache_info.identity_digest,
 293                             country);
 294 }
 295
 296 /** Return true iff <b>rs</b> is in <b>set</b>.  If country is <b>-1</b>, we
 297  * look up the country. */
 298 int
 299 routerset_contains_routerstatus(const routerset_t *set,
 300                                 const routerstatus_t *rs,
 301                                 country_t country)
 302 {
 303   tor_addr_t addr;
 304   tor_addr_from_ipv4h(&addr, rs->addr);
 305   return routerset_contains(set,
 306                             &addr,
 307                             rs->or_port,
 308                             rs->nickname,
 309                             rs->identity_digest,
 310                             country);
 311 }
 312
 313 /** Return true iff <b>node</b> is in <b>set</b>. */
 314 int
 315 routerset_contains_node(const routerset_t *set, const node_t *node)
 316 {
 317   if (node->rs)
 318     return routerset_contains_routerstatus(set, node->rs, node->country);
 319   else if (node->ri)
 320     return routerset_contains_router(set, node->ri, node->country);
 321   else
 322     return 0;
 323 }
 324
 325 /** Add every known node_t that is a member of <b>routerset</b> to
 326  * <b>out</b>, but never add any that are part of <b>excludeset</b>.
 327  * If <b>running_only</b>, only add the running ones. */
 328 void
 329 routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset,
 330                         const routerset_t *excludeset, int running_only)
 331 {
 332   tor_assert(out);
 333   if (!routerset || !routerset->list)
 334     return;
 335
 336   if (routerset_is_list(routerset)) {
 337     /* No routers are specified by type; all are given by name or digest.
 338      * we can do a lookup in O(len(routerset)). */
 339     SMARTLIST_FOREACH(routerset->list, const char *, name, {
 340         const node_t *node = node_get_by_nickname(name, 1);
 341         if (node) {
 342           if (!running_only || node->is_running)
 343             if (!routerset_contains_node(excludeset, node))
 344               smartlist_add(out, (void*)node);
 345         }
 346     });
 347   } else {
 348     /* We need to iterate over the routerlist to get all the ones of the
 349      * right kind. */
 350     smartlist_t *nodes = nodelist_get_list();
 351     SMARTLIST_FOREACH(nodes, const node_t *, node, {
 352         if (running_only && !node->is_running)
 353           continue;
 354         if (routerset_contains_node(routerset, node) &&
 355             !routerset_contains_node(excludeset, node))
 356           smartlist_add(out, (void*)node);
 357     });
 358   }
 359 }
 360
 361 /** Remove every node_t from <b>lst</b> that is in <b>routerset</b>. */
 362 void
 363 routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset)
 364 {
 365   tor_assert(lst);
 366   if (!routerset)
 367     return;
 368   SMARTLIST_FOREACH(lst, const node_t *, node, {
 369       if (routerset_contains_node(routerset, node)) {
 370         //log_debug(LD_DIR, "Subtracting %s",r->nickname);
 371         SMARTLIST_DEL_CURRENT(lst, node);
 372       }
 373     });
 374 }
 375
 376 /** Return a new string that when parsed by routerset_parse_string() will
 377  * yield <b>set</b>. */
 378 char *
 379 routerset_to_string(const routerset_t *set)
 380 {
 381   if (!set || !set->list)
 382     return tor_strdup("");
 383   return smartlist_join_strings(set->list, ",", 0, NULL);
 384 }
 385
 386 /** Helper: return true iff old and new are both NULL, or both non-NULL
 387  * equal routersets. */
 388 int
 389 routerset_equal(const routerset_t *old, const routerset_t *new)
 390 {
 391   if (routerset_is_empty(old) && routerset_is_empty(new)) {
 392     /* Two empty sets are equal */
 393     return 1;
 394   } else if (routerset_is_empty(old) || routerset_is_empty(new)) {
 395     /* An empty set is equal to nothing else. */
 396     return 0;
 397   }
 398   tor_assert(old != NULL);
 399   tor_assert(new != NULL);
 400
 401   if (smartlist_len(old->list) != smartlist_len(new->list))
 402     return 0;
 403
 404   SMARTLIST_FOREACH(old->list, const char *, cp1, {
 405     const char *cp2 = smartlist_get(new->list, cp1_sl_idx);
 406     if (strcmp(cp1, cp2))
 407       return 0;
 408   });
 409
 410   return 1;
 411 }
 412
 413 /** Free all storage held in <b>routerset</b>. */
 414 void
 415 routerset_free(routerset_t *routerset)
 416 {
 417   if (!routerset)
 418     return;
 419
 420   SMARTLIST_FOREACH(routerset->list, char *, cp, tor_free(cp));
 421   smartlist_free(routerset->list);
 422   SMARTLIST_FOREACH(routerset->policies, addr_policy_t *, p,
 423                     addr_policy_free(p));
 424   smartlist_free(routerset->policies);
 425   SMARTLIST_FOREACH(routerset->country_names, char *, cp, tor_free(cp));
 426   smartlist_free(routerset->country_names);
 427
 428   strmap_free(routerset->names, NULL);
 429   digestmap_free(routerset->digests, NULL);
 430   bitarray_free(routerset->countries);
 431   tor_free(routerset);
 432 }
 433