Line data Source code
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 269 : routerset_new(void)
52 : {
53 269 : routerset_t *result = tor_malloc_zero(sizeof(routerset_t));
54 269 : result->list = smartlist_new();
55 269 : result->names = strmap_new();
56 269 : result->digests = digestmap_new();
57 269 : result->policies = smartlist_new();
58 269 : result->country_names = smartlist_new();
59 269 : result->fragile = 0;
60 269 : 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 159 : routerset_get_countryname(const char *c)
67 : {
68 159 : char *country;
69 :
70 159 : if (strlen(c) < 4 || c[0] !='{' || c[3] !='}')
71 : return NULL;
72 :
73 28 : country = tor_strndup(c+1, 2);
74 28 : tor_strlower(country);
75 28 : 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 32 : routerset_refresh_countries(routerset_t *target)
83 : {
84 32 : int cc;
85 32 : bitarray_free(target->countries);
86 :
87 32 : if (!geoip_is_loaded(AF_INET)) {
88 29 : target->countries = NULL;
89 29 : target->n_countries = 0;
90 29 : return;
91 : }
92 3 : target->n_countries = geoip_get_n_countries();
93 3 : target->countries = bitarray_init_zero(target->n_countries);
94 5 : SMARTLIST_FOREACH_BEGIN(target->country_names, const char *, country) {
95 2 : cc = geoip_get_country(country);
96 2 : if (cc >= 0) {
97 1 : tor_assert(cc < target->n_countries);
98 1 : bitarray_set(target->countries, cc);
99 : } else {
100 1 : log_warn(LD_CONFIG, "Country code '%s' is not recognized.",
101 : country);
102 : }
103 2 : } 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 252 : routerset_parse(routerset_t *target, const char *s, const char *description)
116 : {
117 252 : int r = 0;
118 252 : int added_countries = 0;
119 252 : char *countryname;
120 252 : smartlist_t *list = smartlist_new();
121 252 : int malformed_list;
122 252 : smartlist_split_string(list, s, ",",
123 : SPLIT_SKIP_SPACE | SPLIT_IGNORE_BLANK, 0);
124 591 : SMARTLIST_FOREACH_BEGIN(list, char *, nick) {
125 339 : addr_policy_t *p;
126 : /* if it doesn't pass our validation, assume it's malformed */
127 339 : malformed_list = 1;
128 339 : if (is_legal_hexdigest(nick)) {
129 77 : char d[DIGEST_LEN];
130 77 : if (*nick == '$')
131 75 : ++nick;
132 77 : log_debug(LD_CONFIG, "Adding identity %s to %s", nick, description);
133 77 : base16_decode(d, sizeof(d), nick, HEX_DIGEST_LEN);
134 77 : digestmap_set(target->digests, d, (void*)1);
135 262 : } else if (is_legal_nickname(nick)) {
136 108 : log_debug(LD_CONFIG, "Adding nickname %s to %s", nick, description);
137 108 : strmap_set_lc(target->names, nick, (void*)1);
138 154 : } else if ((countryname = routerset_get_countryname(nick)) != NULL) {
139 26 : log_debug(LD_CONFIG, "Adding country %s to %s", nick,
140 : description);
141 26 : smartlist_add(target->country_names, countryname);
142 26 : added_countries = 1;
143 128 : } else if ((strchr(nick,'.') || strchr(nick, ':') || strchr(nick, '*'))
144 123 : && (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 121 : log_debug(LD_CONFIG, "Adding address %s to %s", nick, description);
150 121 : smartlist_add(target->policies, p);
151 7 : } else if (malformed_list) {
152 7 : log_warn(LD_CONFIG, "Entry '%s' in %s is malformed. Discarding entire"
153 : " list.", nick, description);
154 7 : r = -1;
155 7 : tor_free(nick);
156 7 : SMARTLIST_DEL_CURRENT(list, nick);
157 : } else {
158 0 : log_notice(LD_CONFIG, "Entry '%s' in %s is ignored. Using the"
159 : " remainder of the list.", nick, description);
160 0 : tor_free(nick);
161 0 : SMARTLIST_DEL_CURRENT(list, nick);
162 : }
163 339 : } SMARTLIST_FOREACH_END(nick);
164 252 : policy_expand_unspec(&target->policies);
165 252 : smartlist_add_all(target->list, list);
166 252 : smartlist_free(list);
167 252 : if (added_countries)
168 26 : routerset_refresh_countries(target);
169 252 : return r;
170 : }
171 :
172 : /** Add all members of the set <b>source</b> to <b>target</b>. */
173 : void
174 102 : routerset_union(routerset_t *target, const routerset_t *source)
175 : {
176 102 : char *s;
177 102 : tor_assert(target);
178 102 : if (!source || !source->list)
179 102 : return;
180 96 : s = routerset_to_string(source);
181 96 : routerset_parse(target, s, "other routerset");
182 96 : 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 35 : routerset_is_list(const routerset_t *set)
189 : {
190 35 : return smartlist_len(set->country_names) == 0 &&
191 29 : 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 59 : routerset_needs_geoip(const routerset_t *set)
198 : {
199 59 : return set && smartlist_len(set->country_names);
200 : }
201 :
202 : /** Return true iff there are no entries in <b>set</b>. */
203 : int
204 2446 : routerset_is_empty(const routerset_t *set)
205 : {
206 2446 : 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 3 : routerset_len(const routerset_t *set)
213 : {
214 3 : if (!set) {
215 : return 0;
216 : }
217 3 : 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 8221 : 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 8221 : if (!set || !set->list)
234 : return 0;
235 2204 : if (nickname && strmap_get_lc(set->names, nickname))
236 : return 4;
237 2161 : if (id_digest && digestmap_get(set->digests, id_digest))
238 : return 4;
239 2153 : if (addr && compare_tor_addr_to_addr_policy(addr, orport, set->policies)
240 : == ADDR_POLICY_REJECTED)
241 : return 3;
242 2057 : if (addr2 && compare_tor_addr_to_addr_policy(addr2, orport2, set->policies)
243 : == ADDR_POLICY_REJECTED)
244 : return 3;
245 2057 : if (set->countries) {
246 2 : if (country < 0 && addr)
247 2 : country = geoip_get_country_by_addr(addr);
248 :
249 2 : if (country >= 0 && country < set->n_countries &&
250 1 : bitarray_is_set(set->countries, country))
251 1 : 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 8135 : 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 8135 : 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 4 : routerset_add_unknown_ccs(routerset_t **setp, int only_if_some_cc_set)
273 : {
274 4 : routerset_t *set;
275 4 : int add_unknown, add_a1;
276 4 : if (only_if_some_cc_set) {
277 1 : if (!*setp || smartlist_len((*setp)->country_names) == 0)
278 : return 0;
279 : }
280 3 : if (!*setp)
281 1 : *setp = routerset_new();
282 :
283 3 : set = *setp;
284 :
285 6 : add_unknown = ! smartlist_contains_string_case(set->country_names, "??") &&
286 3 : geoip_get_country("??") >= 0;
287 6 : add_a1 = ! smartlist_contains_string_case(set->country_names, "a1") &&
288 3 : geoip_get_country("A1") >= 0;
289 :
290 3 : if (add_unknown) {
291 1 : smartlist_add_strdup(set->country_names, "??");
292 1 : smartlist_add_strdup(set->list, "{??}");
293 : }
294 3 : if (add_a1) {
295 1 : smartlist_add_strdup(set->country_names, "a1");
296 1 : smartlist_add_strdup(set->list, "{a1}");
297 : }
298 :
299 3 : if (add_unknown || add_a1) {
300 2 : routerset_refresh_countries(set);
301 2 : 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 81 : routerset_contains_extendinfo(const routerset_t *set, const extend_info_t *ei)
309 : {
310 81 : const tor_addr_port_t *ap1 = NULL, *ap2 = NULL;
311 81 : if (! tor_addr_is_null(&ei->orports[0].addr))
312 80 : ap1 = &ei->orports[0];
313 81 : if (! tor_addr_is_null(&ei->orports[1].addr))
314 0 : ap2 = &ei->orports[1];
315 161 : return routerset_contains2(set,
316 : ap1 ? &ap1->addr : NULL,
317 80 : ap1 ? ap1->port : 0,
318 : ap2 ? &ap2->addr : NULL,
319 0 : ap2 ? ap2->port : 0,
320 81 : ei->nickname,
321 81 : 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 5 : routerset_contains_router(const routerset_t *set, const routerinfo_t *ri,
329 : country_t country)
330 : {
331 10 : return routerset_contains2(set, &ri->ipv4_addr, ri->ipv4_orport,
332 5 : &ri->ipv6_addr, ri->ipv6_orport, ri->nickname,
333 5 : 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 8122 : routerset_contains_routerstatus(const routerset_t *set,
340 : const routerstatus_t *rs,
341 : country_t country)
342 : {
343 16244 : return routerset_contains(set,
344 : &rs->ipv4_addr,
345 8122 : rs->ipv4_orport,
346 8122 : rs->nickname,
347 8122 : rs->identity_digest,
348 : country);
349 : }
350 :
351 : /** Return true iff <b>node</b> is in <b>set</b>. */
352 : int
353 8062 : routerset_contains_node(const routerset_t *set, const node_t *node)
354 : {
355 8062 : if (node->rs)
356 8058 : return routerset_contains_routerstatus(set, node->rs, node->country);
357 4 : else if (node->ri)
358 2 : 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 0 : routerset_contains_bridge(const routerset_t *set, const bridge_info_t *bridge)
366 : {
367 0 : const char *id = (const char*)bridge_get_rsa_id_digest(bridge);
368 0 : const tor_addr_port_t *addrport = bridge_get_addr_port(bridge);
369 :
370 0 : tor_assert(addrport);
371 0 : 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 7 : routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset,
380 : const routerset_t *excludeset, int running_only)
381 : {
382 7 : tor_assert(out);
383 7 : if (!routerset || !routerset->list)
384 : return;
385 :
386 5 : 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 6 : 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 2 : const smartlist_t *nodes = nodelist_get_list();
401 3 : 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 2 : routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset)
414 : {
415 2 : tor_assert(lst);
416 2 : if (!routerset)
417 : return;
418 2 : 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 2426 : routerset_to_string(const routerset_t *set)
430 : {
431 2426 : if (!set || !set->list)
432 2289 : return tor_strdup("");
433 137 : 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 5 : routerset_equal(const routerset_t *old, const routerset_t *new)
440 : {
441 5 : if (routerset_is_empty(old) && routerset_is_empty(new)) {
442 : /* Two empty sets are equal */
443 : return 1;
444 4 : } else if (routerset_is_empty(old) || routerset_is_empty(new)) {
445 : /* An empty set is equal to nothing else. */
446 : return 0;
447 : }
448 3 : tor_assert(old != NULL);
449 3 : tor_assert(new != NULL);
450 :
451 3 : if (smartlist_len(old->list) != smartlist_len(new->list))
452 : return 0;
453 :
454 3 : 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 75079 : routerset_free_(routerset_t *routerset)
466 : {
467 75079 : if (!routerset)
468 : return;
469 :
470 558 : SMARTLIST_FOREACH(routerset->list, char *, cp, tor_free(cp));
471 252 : smartlist_free(routerset->list);
472 366 : SMARTLIST_FOREACH(routerset->policies, addr_policy_t *, p,
473 : addr_policy_free(p));
474 252 : smartlist_free(routerset->policies);
475 287 : SMARTLIST_FOREACH(routerset->country_names, char *, cp, tor_free(cp));
476 252 : smartlist_free(routerset->country_names);
477 :
478 252 : strmap_free(routerset->names, NULL);
479 252 : digestmap_free(routerset->digests, NULL);
480 252 : bitarray_free(routerset->countries);
481 252 : 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 84 : routerset_kv_parse(void *target, const config_line_t *line, char **errmsg,
500 : const void *params)
501 : {
502 84 : (void)params;
503 84 : routerset_t **lines = target;
504 :
505 84 : if (*lines && (*lines)->fragile) {
506 6 : if (line->command == CONFIG_LINE_APPEND) {
507 2 : (*lines)->fragile = 0;
508 : } else {
509 4 : routerset_free(*lines); // Represent empty sets as NULL
510 : }
511 : }
512 :
513 84 : int ret;
514 84 : routerset_t *rs = routerset_new();
515 84 : if (routerset_parse(rs, line->value, line->key) < 0) {
516 1 : *errmsg = tor_strdup("Invalid router list.");
517 1 : ret = -1;
518 : } else {
519 83 : if (!routerset_is_empty(rs)) {
520 83 : if (!*lines) {
521 73 : *lines = routerset_new();
522 : }
523 83 : routerset_union(*lines, rs);
524 : }
525 : ret = 0;
526 : }
527 84 : routerset_free(rs);
528 84 : 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 2325 : routerset_encode(const void *value, const void *params)
539 : {
540 2325 : (void)params;
541 2325 : const routerset_t **p = (const routerset_t**)value;
542 2325 : 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 65954 : routerset_clear(void *value, const void *params)
552 : {
553 65954 : (void)params;
554 65954 : routerset_t **p = (routerset_t**)value;
555 65954 : routerset_free(*p); // sets *p to NULL.
556 65954 : }
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 2350 : routerset_copy(void *dest, const void *src, const void *params)
567 : {
568 2350 : (void)params;
569 2350 : routerset_t **output = (routerset_t**)dest;
570 2350 : const routerset_t *input = *(routerset_t**)src;
571 2350 : routerset_free(*output); // sets *output to NULL
572 2350 : if (! routerset_is_empty(input)) {
573 0 : *output = routerset_new();
574 0 : routerset_union(*output, input);
575 : }
576 2350 : return 0;
577 : }
578 :
579 : static void
580 20302 : routerset_mark_fragile(void *target, const void *params)
581 : {
582 20302 : (void)params;
583 20302 : routerset_t **ptr = (routerset_t **)target;
584 20302 : if (*ptr)
585 104 : (*ptr)->fragile = 1;
586 20302 : }
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 : };
|
