routerset.c 14 KB

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