routerset.c (19279B)
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-2021, 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 confmgt.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 "core/or/or.h" 31 #include "core/or/policies.h" 32 #include "feature/client/bridges.h" 33 #include "feature/dirparse/policy_parse.h" 34 #include "feature/nodelist/nickname.h" 35 #include "feature/nodelist/nodelist.h" 36 #include "feature/nodelist/routerset.h" 37 #include "lib/conf/conftypes.h" 38 #include "lib/confmgt/typedvar.h" 39 #include "lib/encoding/confline.h" 40 #include "lib/geoip/geoip.h" 41 42 #include "core/or/addr_policy_st.h" 43 #include "core/or/extend_info_st.h" 44 #include "feature/nodelist/node_st.h" 45 #include "feature/nodelist/routerinfo_st.h" 46 #include "feature/nodelist/routerstatus_st.h" 47 #include "lib/confmgt/var_type_def_st.h" 48 49 /** Return a new empty routerset. */ 50 routerset_t * 51 routerset_new(void) 52 { 53 routerset_t *result = tor_malloc_zero(sizeof(routerset_t)); 54 result->list = smartlist_new(); 55 result->names = strmap_new(); 56 result->digests = digestmap_new(); 57 result->policies = smartlist_new(); 58 result->country_names = smartlist_new(); 59 result->fragile = 0; 60 return result; 61 } 62 63 /** If <b>c</b> is a country code in the form {cc}, return a newly allocated 64 * string holding the "cc" part. Else, return NULL. */ 65 STATIC char * 66 routerset_get_countryname(const char *c) 67 { 68 char *country; 69 70 if (strlen(c) < 4 || c[0] !='{' || c[3] !='}') 71 return NULL; 72 73 country = tor_strndup(c+1, 2); 74 tor_strlower(country); 75 return country; 76 } 77 78 /** Update the routerset's <b>countries</b> bitarray_t. Called whenever 79 * the GeoIP IPv4 database is reloaded. 80 */ 81 void 82 routerset_refresh_countries(routerset_t *target) 83 { 84 int cc; 85 bitarray_free(target->countries); 86 87 if (!geoip_is_loaded(AF_INET)) { 88 target->countries = NULL; 89 target->n_countries = 0; 90 return; 91 } 92 target->n_countries = geoip_get_n_countries(); 93 target->countries = bitarray_init_zero(target->n_countries); 94 SMARTLIST_FOREACH_BEGIN(target->country_names, const char *, country) { 95 cc = geoip_get_country(country); 96 if (cc >= 0) { 97 tor_assert(cc < target->n_countries); 98 bitarray_set(target->countries, cc); 99 } else { 100 log_warn(LD_CONFIG, "Country code '%s' is not recognized.", 101 country); 102 } 103 } SMARTLIST_FOREACH_END(country); 104 } 105 106 /** Parse the string <b>s</b> to create a set of routerset entries, and add 107 * them to <b>target</b>. In log messages, refer to the string as 108 * <b>description</b>. Return 0 on success, -1 on failure. 109 * 110 * Three kinds of elements are allowed in routersets: nicknames, IP address 111 * patterns, and fingerprints. They may be surrounded by optional space, and 112 * must be separated by commas. 113 */ 114 int 115 routerset_parse(routerset_t *target, const char *s, const char *description) 116 { 117 int r = 0; 118 int added_countries = 0; 119 char *countryname; 120 smartlist_t *list = smartlist_new(); 121 int malformed_list; 122 smartlist_split_string(list, s, ",", 123 SPLIT_SKIP_SPACE | SPLIT_IGNORE_BLANK, 0); 124 SMARTLIST_FOREACH_BEGIN(list, char *, nick) { 125 addr_policy_t *p; 126 /* if it doesn't pass our validation, assume it's malformed */ 127 malformed_list = 1; 128 if (is_legal_hexdigest(nick)) { 129 char d[DIGEST_LEN]; 130 if (*nick == '$') 131 ++nick; 132 log_debug(LD_CONFIG, "Adding identity %s to %s", nick, description); 133 base16_decode(d, sizeof(d), nick, HEX_DIGEST_LEN); 134 digestmap_set(target->digests, d, (void*)1); 135 } else if (is_legal_nickname(nick)) { 136 log_debug(LD_CONFIG, "Adding nickname %s to %s", nick, description); 137 strmap_set_lc(target->names, nick, (void*)1); 138 } else if ((countryname = routerset_get_countryname(nick)) != NULL) { 139 log_debug(LD_CONFIG, "Adding country %s to %s", nick, 140 description); 141 smartlist_add(target->country_names, countryname); 142 added_countries = 1; 143 } else if ((strchr(nick,'.') || strchr(nick, ':') || strchr(nick, '*')) 144 && (p = router_parse_addr_policy_item_from_string( 145 nick, ADDR_POLICY_REJECT, 146 &malformed_list))) { 147 /* IPv4 addresses contain '.', IPv6 addresses contain ':', 148 * and wildcard addresses contain '*'. */ 149 log_debug(LD_CONFIG, "Adding address %s to %s", nick, description); 150 smartlist_add(target->policies, p); 151 } else if (malformed_list) { 152 log_warn(LD_CONFIG, "Entry '%s' in %s is malformed. Discarding entire" 153 " list.", nick, description); 154 r = -1; 155 tor_free(nick); 156 SMARTLIST_DEL_CURRENT(list, nick); 157 } else { 158 log_notice(LD_CONFIG, "Entry '%s' in %s is ignored. Using the" 159 " remainder of the list.", nick, description); 160 tor_free(nick); 161 SMARTLIST_DEL_CURRENT(list, nick); 162 } 163 } SMARTLIST_FOREACH_END(nick); 164 policy_expand_unspec(&target->policies); 165 smartlist_add_all(target->list, list); 166 smartlist_free(list); 167 if (added_countries) 168 routerset_refresh_countries(target); 169 return r; 170 } 171 172 /** Add all members of the set <b>source</b> to <b>target</b>. */ 173 void 174 routerset_union(routerset_t *target, const routerset_t *source) 175 { 176 char *s; 177 tor_assert(target); 178 if (!source || !source->list) 179 return; 180 s = routerset_to_string(source); 181 routerset_parse(target, s, "other routerset"); 182 tor_free(s); 183 } 184 185 /** Return true iff <b>set</b> lists only nicknames and digests, and includes 186 * no IP ranges or countries. */ 187 int 188 routerset_is_list(const routerset_t *set) 189 { 190 return smartlist_len(set->country_names) == 0 && 191 smartlist_len(set->policies) == 0; 192 } 193 194 /** Return true iff we need a GeoIP IP-to-country database to make sense of 195 * <b>set</b>. */ 196 int 197 routerset_needs_geoip(const routerset_t *set) 198 { 199 return set && smartlist_len(set->country_names); 200 } 201 202 /** Return true iff there are no entries in <b>set</b>. */ 203 int 204 routerset_is_empty(const routerset_t *set) 205 { 206 return !set || smartlist_len(set->list) == 0; 207 } 208 209 /** Return the number of entries in <b>set</b>. This does NOT return a 210 * negative value. */ 211 int 212 routerset_len(const routerset_t *set) 213 { 214 if (!set) { 215 return 0; 216 } 217 return smartlist_len(set->list); 218 } 219 220 /** Helper. Return true iff <b>set</b> contains a router based on the other 221 * provided fields. Return higher values for more specific subentries: a 222 * single router is more specific than an address range of routers, which is 223 * more specific in turn than a country code. 224 * 225 * (If country is -1, then we take the country 226 * from addr.) */ 227 static int 228 routerset_contains2(const routerset_t *set, const tor_addr_t *addr, 229 uint16_t orport, const tor_addr_t *addr2, 230 uint16_t orport2, const char *nickname, 231 const char *id_digest, country_t country) 232 { 233 if (!set || !set->list) 234 return 0; 235 if (nickname && strmap_get_lc(set->names, nickname)) 236 return 4; 237 if (id_digest && digestmap_get(set->digests, id_digest)) 238 return 4; 239 if (addr && compare_tor_addr_to_addr_policy(addr, orport, set->policies) 240 == ADDR_POLICY_REJECTED) 241 return 3; 242 if (addr2 && compare_tor_addr_to_addr_policy(addr2, orport2, set->policies) 243 == ADDR_POLICY_REJECTED) 244 return 3; 245 if (set->countries) { 246 if (country < 0 && addr) 247 country = geoip_get_country_by_addr(addr); 248 249 if (country >= 0 && country < set->n_countries && 250 bitarray_is_set(set->countries, country)) 251 return 2; 252 } 253 return 0; 254 } 255 256 /** Helper. Like routerset_contains2() but for a single IP/port combo. 257 */ 258 STATIC int 259 routerset_contains(const routerset_t *set, const tor_addr_t *addr, 260 uint16_t orport, const char *nickname, 261 const char *id_digest, country_t country) 262 { 263 return routerset_contains2(set, addr, orport, NULL, 0, 264 nickname, id_digest, country); 265 } 266 267 /** If *<b>setp</b> includes at least one country code, or if 268 * <b>only_some_cc_set</b> is 0, add the ?? and A1 country codes to 269 * *<b>setp</b>, creating it as needed. Return true iff *<b>setp</b> changed. 270 */ 271 int 272 routerset_add_unknown_ccs(routerset_t **setp, int only_if_some_cc_set) 273 { 274 routerset_t *set; 275 int add_unknown, add_a1; 276 if (only_if_some_cc_set) { 277 if (!*setp || smartlist_len((*setp)->country_names) == 0) 278 return 0; 279 } 280 if (!*setp) 281 *setp = routerset_new(); 282 283 set = *setp; 284 285 add_unknown = ! smartlist_contains_string_case(set->country_names, "??") && 286 geoip_get_country("??") >= 0; 287 add_a1 = ! smartlist_contains_string_case(set->country_names, "a1") && 288 geoip_get_country("A1") >= 0; 289 290 if (add_unknown) { 291 smartlist_add_strdup(set->country_names, "??"); 292 smartlist_add_strdup(set->list, "{??}"); 293 } 294 if (add_a1) { 295 smartlist_add_strdup(set->country_names, "a1"); 296 smartlist_add_strdup(set->list, "{a1}"); 297 } 298 299 if (add_unknown || add_a1) { 300 routerset_refresh_countries(set); 301 return 1; 302 } 303 return 0; 304 } 305 306 /** Return true iff we can tell that <b>ei</b> is a member of <b>set</b>. */ 307 int 308 routerset_contains_extendinfo(const routerset_t *set, const extend_info_t *ei) 309 { 310 const tor_addr_port_t *ap1 = NULL, *ap2 = NULL; 311 if (! tor_addr_is_null(&ei->orports[0].addr)) 312 ap1 = &ei->orports[0]; 313 if (! tor_addr_is_null(&ei->orports[1].addr)) 314 ap2 = &ei->orports[1]; 315 return routerset_contains2(set, 316 ap1 ? &ap1->addr : NULL, 317 ap1 ? ap1->port : 0, 318 ap2 ? &ap2->addr : NULL, 319 ap2 ? ap2->port : 0, 320 ei->nickname, 321 ei->identity_digest, 322 -1 /*country*/); 323 } 324 325 /** Return true iff <b>ri</b> is in <b>set</b>. If country is <b>-1</b>, we 326 * look up the country. */ 327 int 328 routerset_contains_router(const routerset_t *set, const routerinfo_t *ri, 329 country_t country) 330 { 331 return routerset_contains2(set, &ri->ipv4_addr, ri->ipv4_orport, 332 &ri->ipv6_addr, ri->ipv6_orport, ri->nickname, 333 ri->cache_info.identity_digest, country); 334 } 335 336 /** Return true iff <b>rs</b> is in <b>set</b>. If country is <b>-1</b>, we 337 * look up the country. */ 338 int 339 routerset_contains_routerstatus(const routerset_t *set, 340 const routerstatus_t *rs, 341 country_t country) 342 { 343 return routerset_contains(set, 344 &rs->ipv4_addr, 345 rs->ipv4_orport, 346 rs->nickname, 347 rs->identity_digest, 348 country); 349 } 350 351 /** Return true iff <b>node</b> is in <b>set</b>. */ 352 int 353 routerset_contains_node(const routerset_t *set, const node_t *node) 354 { 355 if (node->rs) 356 return routerset_contains_routerstatus(set, node->rs, node->country); 357 else if (node->ri) 358 return routerset_contains_router(set, node->ri, node->country); 359 else 360 return 0; 361 } 362 363 /** Return true iff <b>routerset</b> contains the bridge <b>bridge</b>. */ 364 int 365 routerset_contains_bridge(const routerset_t *set, const bridge_info_t *bridge) 366 { 367 const char *id = (const char*)bridge_get_rsa_id_digest(bridge); 368 const tor_addr_port_t *addrport = bridge_get_addr_port(bridge); 369 370 tor_assert(addrport); 371 return routerset_contains(set, &addrport->addr, addrport->port, 372 NULL, id, -1); 373 } 374 375 /** Add every known node_t that is a member of <b>routerset</b> to 376 * <b>out</b>, but never add any that are part of <b>excludeset</b>. 377 * If <b>running_only</b>, only add the running ones. */ 378 void 379 routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset, 380 const routerset_t *excludeset, int running_only) 381 { 382 tor_assert(out); 383 if (!routerset || !routerset->list) 384 return; 385 386 if (routerset_is_list(routerset)) { 387 /* No routers are specified by type; all are given by name or digest. 388 * we can do a lookup in O(len(routerset)). */ 389 SMARTLIST_FOREACH(routerset->list, const char *, name, { 390 const node_t *node = node_get_by_nickname(name, 0); 391 if (node) { 392 if (!running_only || node->is_running) 393 if (!routerset_contains_node(excludeset, node)) 394 smartlist_add(out, (void*)node); 395 } 396 }); 397 } else { 398 /* We need to iterate over the routerlist to get all the ones of the 399 * right kind. */ 400 const smartlist_t *nodes = nodelist_get_list(); 401 SMARTLIST_FOREACH(nodes, const node_t *, node, { 402 if (running_only && !node->is_running) 403 continue; 404 if (routerset_contains_node(routerset, node) && 405 !routerset_contains_node(excludeset, node)) 406 smartlist_add(out, (void*)node); 407 }); 408 } 409 } 410 411 /** Remove every node_t from <b>lst</b> that is in <b>routerset</b>. */ 412 void 413 routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset) 414 { 415 tor_assert(lst); 416 if (!routerset) 417 return; 418 SMARTLIST_FOREACH(lst, const node_t *, node, { 419 if (routerset_contains_node(routerset, node)) { 420 //log_debug(LD_DIR, "Subtracting %s",r->nickname); 421 SMARTLIST_DEL_CURRENT(lst, node); 422 } 423 }); 424 } 425 426 /** Return a new string that when parsed by routerset_parse_string() will 427 * yield <b>set</b>. */ 428 char * 429 routerset_to_string(const routerset_t *set) 430 { 431 if (!set || !set->list) 432 return tor_strdup(""); 433 return smartlist_join_strings(set->list, ",", 0, NULL); 434 } 435 436 /** Helper: return true iff old and new are both NULL, or both non-NULL 437 * equal routersets. */ 438 int 439 routerset_equal(const routerset_t *old, const routerset_t *new) 440 { 441 if (routerset_is_empty(old) && routerset_is_empty(new)) { 442 /* Two empty sets are equal */ 443 return 1; 444 } else if (routerset_is_empty(old) || routerset_is_empty(new)) { 445 /* An empty set is equal to nothing else. */ 446 return 0; 447 } 448 tor_assert(old != NULL); 449 tor_assert(new != NULL); 450 451 if (smartlist_len(old->list) != smartlist_len(new->list)) 452 return 0; 453 454 SMARTLIST_FOREACH(old->list, const char *, cp1, { 455 const char *cp2 = smartlist_get(new->list, cp1_sl_idx); 456 if (strcmp(cp1, cp2)) 457 return 0; 458 }); 459 460 return 1; 461 } 462 463 /** Free all storage held in <b>routerset</b>. */ 464 void 465 routerset_free_(routerset_t *routerset) 466 { 467 if (!routerset) 468 return; 469 470 SMARTLIST_FOREACH(routerset->list, char *, cp, tor_free(cp)); 471 smartlist_free(routerset->list); 472 SMARTLIST_FOREACH(routerset->policies, addr_policy_t *, p, 473 addr_policy_free(p)); 474 smartlist_free(routerset->policies); 475 SMARTLIST_FOREACH(routerset->country_names, char *, cp, tor_free(cp)); 476 smartlist_free(routerset->country_names); 477 478 strmap_free(routerset->names, NULL); 479 digestmap_free(routerset->digests, NULL); 480 bitarray_free(routerset->countries); 481 tor_free(routerset); 482 } 483 484 /** 485 * config helper: parse a routerset-typed variable. 486 * 487 * Takes as input as a single line in <b>line</b>; writes its results into a 488 * routerset_t** passed as <b>target</b>. On success return 0; on failure 489 * return -1 and store an error message into *<b>errmsg</b>. 490 **/ 491 /* 492 * Warning: For this type, the default value (NULL) and "" are sometimes 493 * considered different values. That is generally risky, and best avoided for 494 * other types in the future. For cases where we want the default to be "all 495 * routers" (like EntryNodes) we should add a new routerset value indicating 496 * "all routers" (see #31908) 497 */ 498 static int 499 routerset_kv_parse(void *target, const config_line_t *line, char **errmsg, 500 const void *params) 501 { 502 (void)params; 503 routerset_t **lines = target; 504 505 if (*lines && (*lines)->fragile) { 506 if (line->command == CONFIG_LINE_APPEND) { 507 (*lines)->fragile = 0; 508 } else { 509 routerset_free(*lines); // Represent empty sets as NULL 510 } 511 } 512 513 int ret; 514 routerset_t *rs = routerset_new(); 515 if (routerset_parse(rs, line->value, line->key) < 0) { 516 *errmsg = tor_strdup("Invalid router list."); 517 ret = -1; 518 } else { 519 if (!routerset_is_empty(rs)) { 520 if (!*lines) { 521 *lines = routerset_new(); 522 } 523 routerset_union(*lines, rs); 524 } 525 ret = 0; 526 } 527 routerset_free(rs); 528 return ret; 529 } 530 531 /** 532 * config helper: encode a routerset-typed variable. 533 * 534 * Return a newly allocated string containing the value of the 535 * routerset_t** passed as <b>value</b>. 536 */ 537 static char * 538 routerset_encode(const void *value, const void *params) 539 { 540 (void)params; 541 const routerset_t **p = (const routerset_t**)value; 542 return routerset_to_string(*p); 543 } 544 545 /** 546 * config helper: free and clear a routerset-typed variable. 547 * 548 * Clear the routerset_t** passed as <b>value</b>. 549 */ 550 static void 551 routerset_clear(void *value, const void *params) 552 { 553 (void)params; 554 routerset_t **p = (routerset_t**)value; 555 routerset_free(*p); // sets *p to NULL. 556 } 557 558 /** 559 * config helper: copy a routerset-typed variable. 560 * 561 * Takes it input from a routerset_t** in <b>src</b>; writes its output to a 562 * routerset_t** in <b>dest</b>. Returns 0 on success, -1 on (impossible) 563 * failure. 564 **/ 565 static int 566 routerset_copy(void *dest, const void *src, const void *params) 567 { 568 (void)params; 569 routerset_t **output = (routerset_t**)dest; 570 const routerset_t *input = *(routerset_t**)src; 571 routerset_free(*output); // sets *output to NULL 572 if (! routerset_is_empty(input)) { 573 *output = routerset_new(); 574 routerset_union(*output, input); 575 } 576 return 0; 577 } 578 579 static void 580 routerset_mark_fragile(void *target, const void *params) 581 { 582 (void)params; 583 routerset_t **ptr = (routerset_t **)target; 584 if (*ptr) 585 (*ptr)->fragile = 1; 586 } 587 588 /** 589 * Function table to implement a routerset_t-based configuration type. 590 **/ 591 static const var_type_fns_t routerset_type_fns = { 592 .kv_parse = routerset_kv_parse, 593 .encode = routerset_encode, 594 .clear = routerset_clear, 595 .copy = routerset_copy, 596 .mark_fragile = routerset_mark_fragile, 597 }; 598 599 /** 600 * Definition of a routerset_t-based configuration type. 601 * 602 * Values are mapped to and from strings using the format defined in 603 * routerset_parse(): nicknames, IP address patterns, and fingerprints--with 604 * optional space, separated by commas. 605 * 606 * Empty sets are represented as NULL. 607 **/ 608 const var_type_def_t ROUTERSET_type_defn = { 609 .name = "RouterList", 610 .fns = &routerset_type_fns, 611 .flags = CFLG_NOREPLACE 612 };