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