routerset.c 14 KB

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