routerset.c 14 KB

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