routerset.c 12 KB

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