routerset.c 15 KB

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