protover.c 28 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938
  1. /* Copyright (c) 2016-2017, The Tor Project, Inc. */
  2. /* See LICENSE for licensing information */
  3. /**
  4. * \file protover.c
  5. * \brief Versioning information for different pieces of the Tor protocol.
  6. *
  7. * Starting in version 0.2.9.3-alpha, Tor places separate version numbers on
  8. * each of the different components of its protocol. Relays use these numbers
  9. * to advertise what versions of the protocols they can support, and clients
  10. * use them to find what they can ask a given relay to do. Authorities vote
  11. * on the supported protocol versions for each relay, and also vote on the
  12. * which protocols you should have to support in order to be on the Tor
  13. * network. All Tor instances use these required/recommended protocol versions
  14. * to tell what level of support for recent protocols each relay has, and
  15. * to decide whether they should be running given their current protocols.
  16. *
  17. * The main advantage of these protocol versions numbers over using Tor
  18. * version numbers is that they allow different implementations of the Tor
  19. * protocols to develop independently, without having to claim compatibility
  20. * with specific versions of Tor.
  21. **/
  22. #define PROTOVER_PRIVATE
  23. #include "compat.h"
  24. #include "or.h"
  25. #include "protover.h"
  26. #include "routerparse.h"
  27. #ifndef HAVE_RUST
  28. static const smartlist_t *get_supported_protocol_list(void);
  29. static int protocol_list_contains(const smartlist_t *protos,
  30. protocol_type_t pr, uint32_t ver);
  31. /** Mapping between protocol type string and protocol type. */
  32. /// C_RUST_COUPLED: src/rust/protover/protover.rs `PROTOCOL_NAMES`
  33. static const struct {
  34. protocol_type_t protover_type;
  35. const char *name;
  36. } PROTOCOL_NAMES[] = {
  37. { PRT_LINK, "Link" },
  38. { PRT_LINKAUTH, "LinkAuth" },
  39. { PRT_RELAY, "Relay" },
  40. { PRT_DIRCACHE, "DirCache" },
  41. { PRT_HSDIR, "HSDir" },
  42. { PRT_HSINTRO, "HSIntro" },
  43. { PRT_HSREND, "HSRend" },
  44. { PRT_DESC, "Desc" },
  45. { PRT_MICRODESC, "Microdesc"},
  46. { PRT_CONS, "Cons" }
  47. };
  48. #define N_PROTOCOL_NAMES ARRAY_LENGTH(PROTOCOL_NAMES)
  49. /* Maximum allowed length of any single subprotocol name. */
  50. // C_RUST_COUPLED: src/rust/protover/protover.rs
  51. // `MAX_PROTOCOL_NAME_LENGTH`
  52. static const unsigned MAX_PROTOCOL_NAME_LENGTH = 100;
  53. /**
  54. * Given a protocol_type_t, return the corresponding string used in
  55. * descriptors.
  56. */
  57. STATIC const char *
  58. protocol_type_to_str(protocol_type_t pr)
  59. {
  60. unsigned i;
  61. for (i=0; i < N_PROTOCOL_NAMES; ++i) {
  62. if (PROTOCOL_NAMES[i].protover_type == pr)
  63. return PROTOCOL_NAMES[i].name;
  64. }
  65. /* LCOV_EXCL_START */
  66. tor_assert_nonfatal_unreached_once();
  67. return "UNKNOWN";
  68. /* LCOV_EXCL_STOP */
  69. }
  70. /**
  71. * Given a string, find the corresponding protocol type and store it in
  72. * <b>pr_out</b>. Return 0 on success, -1 on failure.
  73. */
  74. STATIC int
  75. str_to_protocol_type(const char *s, protocol_type_t *pr_out)
  76. {
  77. if (BUG(!pr_out))
  78. return -1;
  79. unsigned i;
  80. for (i=0; i < N_PROTOCOL_NAMES; ++i) {
  81. if (0 == strcmp(s, PROTOCOL_NAMES[i].name)) {
  82. *pr_out = PROTOCOL_NAMES[i].protover_type;
  83. return 0;
  84. }
  85. }
  86. return -1;
  87. }
  88. /**
  89. * Release all space held by a single proto_entry_t structure
  90. */
  91. STATIC void
  92. proto_entry_free_(proto_entry_t *entry)
  93. {
  94. if (!entry)
  95. return;
  96. tor_free(entry->name);
  97. SMARTLIST_FOREACH(entry->ranges, proto_range_t *, r, tor_free(r));
  98. smartlist_free(entry->ranges);
  99. tor_free(entry);
  100. }
  101. /** The largest possible protocol version. */
  102. #define MAX_PROTOCOL_VERSION (UINT32_MAX-1)
  103. /**
  104. * Given a string <b>s</b> and optional end-of-string pointer
  105. * <b>end_of_range</b>, parse the protocol range and store it in
  106. * <b>low_out</b> and <b>high_out</b>. A protocol range has the format U, or
  107. * U-U, where U is an unsigned 32-bit integer.
  108. */
  109. static int
  110. parse_version_range(const char *s, const char *end_of_range,
  111. uint32_t *low_out, uint32_t *high_out)
  112. {
  113. uint32_t low, high;
  114. char *next = NULL;
  115. int ok;
  116. tor_assert(high_out);
  117. tor_assert(low_out);
  118. if (BUG(!end_of_range))
  119. end_of_range = s + strlen(s); // LCOV_EXCL_LINE
  120. /* A range must start with a digit. */
  121. if (!TOR_ISDIGIT(*s)) {
  122. goto error;
  123. }
  124. /* Note that this wouldn't be safe if we didn't know that eventually,
  125. * we'd hit a NUL */
  126. low = (uint32_t) tor_parse_ulong(s, 10, 0, MAX_PROTOCOL_VERSION, &ok, &next);
  127. if (!ok)
  128. goto error;
  129. if (next > end_of_range)
  130. goto error;
  131. if (next == end_of_range) {
  132. high = low;
  133. goto done;
  134. }
  135. if (*next != '-')
  136. goto error;
  137. s = next+1;
  138. /* ibid */
  139. if (!TOR_ISDIGIT(*s)) {
  140. goto error;
  141. }
  142. high = (uint32_t) tor_parse_ulong(s, 10, 0,
  143. MAX_PROTOCOL_VERSION, &ok, &next);
  144. if (!ok)
  145. goto error;
  146. if (next != end_of_range)
  147. goto error;
  148. if (low > high)
  149. goto error;
  150. done:
  151. *high_out = high;
  152. *low_out = low;
  153. return 0;
  154. error:
  155. return -1;
  156. }
  157. static int
  158. is_valid_keyword(const char *s, size_t n)
  159. {
  160. for (size_t i = 0; i < n; i++) {
  161. if (!TOR_ISALNUM(s[i]) && s[i] != '-')
  162. return 0;
  163. }
  164. return 1;
  165. }
  166. /** Parse a single protocol entry from <b>s</b> up to an optional
  167. * <b>end_of_entry</b> pointer, and return that protocol entry. Return NULL
  168. * on error.
  169. *
  170. * A protocol entry has a keyword, an = sign, and zero or more ranges. */
  171. static proto_entry_t *
  172. parse_single_entry(const char *s, const char *end_of_entry)
  173. {
  174. proto_entry_t *out = tor_malloc_zero(sizeof(proto_entry_t));
  175. const char *equals;
  176. out->ranges = smartlist_new();
  177. if (BUG (!end_of_entry))
  178. end_of_entry = s + strlen(s); // LCOV_EXCL_LINE
  179. /* There must be an =. */
  180. equals = memchr(s, '=', end_of_entry - s);
  181. if (!equals)
  182. goto error;
  183. /* The name must be nonempty */
  184. if (equals == s)
  185. goto error;
  186. /* The name must not be longer than MAX_PROTOCOL_NAME_LENGTH. */
  187. if (equals - s > (int)MAX_PROTOCOL_NAME_LENGTH) {
  188. log_warn(LD_NET, "When parsing a protocol entry, I got a very large "
  189. "protocol name. This is possibly an attack or a bug, unless "
  190. "the Tor network truly supports protocol names larger than "
  191. "%ud characters. The offending string was: %s",
  192. MAX_PROTOCOL_NAME_LENGTH, escaped(out->name));
  193. goto error;
  194. }
  195. /* The name must contain only alphanumeric characters and hyphens. */
  196. if (!is_valid_keyword(s, equals-s))
  197. goto error;
  198. out->name = tor_strndup(s, equals-s);
  199. tor_assert(equals < end_of_entry);
  200. s = equals + 1;
  201. while (s < end_of_entry) {
  202. const char *comma = memchr(s, ',', end_of_entry-s);
  203. proto_range_t *range = tor_malloc_zero(sizeof(proto_range_t));
  204. if (! comma)
  205. comma = end_of_entry;
  206. smartlist_add(out->ranges, range);
  207. if (parse_version_range(s, comma, &range->low, &range->high) < 0) {
  208. goto error;
  209. }
  210. s = comma;
  211. while (*s == ',' && s < end_of_entry)
  212. ++s;
  213. }
  214. return out;
  215. error:
  216. proto_entry_free(out);
  217. return NULL;
  218. }
  219. /**
  220. * Parse the protocol list from <b>s</b> and return it as a smartlist of
  221. * proto_entry_t
  222. */
  223. STATIC smartlist_t *
  224. parse_protocol_list(const char *s)
  225. {
  226. smartlist_t *entries = smartlist_new();
  227. while (*s) {
  228. /* Find the next space or the NUL. */
  229. const char *end_of_entry = strchr(s, ' ');
  230. proto_entry_t *entry;
  231. if (!end_of_entry)
  232. end_of_entry = s + strlen(s);
  233. entry = parse_single_entry(s, end_of_entry);
  234. if (! entry)
  235. goto error;
  236. smartlist_add(entries, entry);
  237. s = end_of_entry;
  238. while (*s == ' ')
  239. ++s;
  240. }
  241. return entries;
  242. error:
  243. SMARTLIST_FOREACH(entries, proto_entry_t *, ent, proto_entry_free(ent));
  244. smartlist_free(entries);
  245. return NULL;
  246. }
  247. /**
  248. * Return true if the unparsed protover in <b>s</b> would contain a protocol
  249. * name longer than MAX_PROTOCOL_NAME_LENGTH, and false otherwise.
  250. */
  251. bool
  252. protover_contains_long_protocol_names(const char *s)
  253. {
  254. smartlist_t *list = parse_protocol_list(s);
  255. if (!list)
  256. return true; /* yes, has a dangerous name */
  257. SMARTLIST_FOREACH(list, proto_entry_t *, ent, proto_entry_free(ent));
  258. smartlist_free(list);
  259. return false; /* no, looks fine */
  260. }
  261. /**
  262. * Given a protocol type and version number, return true iff we know
  263. * how to speak that protocol.
  264. */
  265. int
  266. protover_is_supported_here(protocol_type_t pr, uint32_t ver)
  267. {
  268. const smartlist_t *ours = get_supported_protocol_list();
  269. return protocol_list_contains(ours, pr, ver);
  270. }
  271. /**
  272. * Return true iff "list" encodes a protocol list that includes support for
  273. * the indicated protocol and version.
  274. */
  275. int
  276. protocol_list_supports_protocol(const char *list, protocol_type_t tp,
  277. uint32_t version)
  278. {
  279. /* NOTE: This is a pretty inefficient implementation. If it ever shows
  280. * up in profiles, we should memoize it.
  281. */
  282. smartlist_t *protocols = parse_protocol_list(list);
  283. if (!protocols) {
  284. return 0;
  285. }
  286. int contains = protocol_list_contains(protocols, tp, version);
  287. SMARTLIST_FOREACH(protocols, proto_entry_t *, ent, proto_entry_free(ent));
  288. smartlist_free(protocols);
  289. return contains;
  290. }
  291. /**
  292. * Return true iff "list" encodes a protocol list that includes support for
  293. * the indicated protocol and version, or some later version.
  294. */
  295. int
  296. protocol_list_supports_protocol_or_later(const char *list,
  297. protocol_type_t tp,
  298. uint32_t version)
  299. {
  300. /* NOTE: This is a pretty inefficient implementation. If it ever shows
  301. * up in profiles, we should memoize it.
  302. */
  303. smartlist_t *protocols = parse_protocol_list(list);
  304. if (!protocols) {
  305. return 0;
  306. }
  307. const char *pr_name = protocol_type_to_str(tp);
  308. int contains = 0;
  309. SMARTLIST_FOREACH_BEGIN(protocols, proto_entry_t *, proto) {
  310. if (strcasecmp(proto->name, pr_name))
  311. continue;
  312. SMARTLIST_FOREACH_BEGIN(proto->ranges, const proto_range_t *, range) {
  313. if (range->high >= version) {
  314. contains = 1;
  315. goto found;
  316. }
  317. } SMARTLIST_FOREACH_END(range);
  318. } SMARTLIST_FOREACH_END(proto);
  319. found:
  320. SMARTLIST_FOREACH(protocols, proto_entry_t *, ent, proto_entry_free(ent));
  321. smartlist_free(protocols);
  322. return contains;
  323. }
  324. /** Return the canonical string containing the list of protocols
  325. * that we support. */
  326. /// C_RUST_COUPLED: src/rust/protover/protover.rs `SUPPORTED_PROTOCOLS`
  327. const char *
  328. protover_get_supported_protocols(void)
  329. {
  330. return
  331. "Cons=1-2 "
  332. "Desc=1-2 "
  333. "DirCache=1-2 "
  334. "HSDir=1-2 "
  335. "HSIntro=3-4 "
  336. "HSRend=1-2 "
  337. "Link=1-5 "
  338. "LinkAuth=1,3 "
  339. "Microdesc=1-2 "
  340. "Relay=1-2";
  341. }
  342. /** The protocols from protover_get_supported_protocols(), as parsed into a
  343. * list of proto_entry_t values. Access this via
  344. * get_supported_protocol_list. */
  345. static smartlist_t *supported_protocol_list = NULL;
  346. /** Return a pointer to a smartlist of proto_entry_t for the protocols
  347. * we support. */
  348. static const smartlist_t *
  349. get_supported_protocol_list(void)
  350. {
  351. if (PREDICT_UNLIKELY(supported_protocol_list == NULL)) {
  352. supported_protocol_list =
  353. parse_protocol_list(protover_get_supported_protocols());
  354. }
  355. return supported_protocol_list;
  356. }
  357. /**
  358. * Given a protocol entry, encode it at the end of the smartlist <b>chunks</b>
  359. * as one or more newly allocated strings.
  360. */
  361. static void
  362. proto_entry_encode_into(smartlist_t *chunks, const proto_entry_t *entry)
  363. {
  364. smartlist_add_asprintf(chunks, "%s=", entry->name);
  365. SMARTLIST_FOREACH_BEGIN(entry->ranges, proto_range_t *, range) {
  366. const char *comma = "";
  367. if (range_sl_idx != 0)
  368. comma = ",";
  369. if (range->low == range->high) {
  370. smartlist_add_asprintf(chunks, "%s%lu",
  371. comma, (unsigned long)range->low);
  372. } else {
  373. smartlist_add_asprintf(chunks, "%s%lu-%lu",
  374. comma, (unsigned long)range->low,
  375. (unsigned long)range->high);
  376. }
  377. } SMARTLIST_FOREACH_END(range);
  378. }
  379. /** Given a list of space-separated proto_entry_t items,
  380. * encode it into a newly allocated space-separated string. */
  381. STATIC char *
  382. encode_protocol_list(const smartlist_t *sl)
  383. {
  384. const char *separator = "";
  385. smartlist_t *chunks = smartlist_new();
  386. SMARTLIST_FOREACH_BEGIN(sl, const proto_entry_t *, ent) {
  387. smartlist_add_strdup(chunks, separator);
  388. proto_entry_encode_into(chunks, ent);
  389. separator = " ";
  390. } SMARTLIST_FOREACH_END(ent);
  391. char *result = smartlist_join_strings(chunks, "", 0, NULL);
  392. SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
  393. smartlist_free(chunks);
  394. return result;
  395. }
  396. /* We treat any protocol list with more than this many subprotocols in it
  397. * as a DoS attempt. */
  398. /// C_RUST_COUPLED: src/rust/protover/protover.rs
  399. /// `MAX_PROTOCOLS_TO_EXPAND`
  400. static const int MAX_PROTOCOLS_TO_EXPAND = (1<<16);
  401. /** Voting helper: Given a list of proto_entry_t, return a newly allocated
  402. * smartlist of newly allocated strings, one for each included protocol
  403. * version. (So 'Foo=3,5-7' expands to a list of 'Foo=3', 'Foo=5', 'Foo=6',
  404. * 'Foo=7'.)
  405. *
  406. * Do not list any protocol version more than once.
  407. *
  408. * Return NULL if the list would be too big.
  409. */
  410. static smartlist_t *
  411. expand_protocol_list(const smartlist_t *protos)
  412. {
  413. smartlist_t *expanded = smartlist_new();
  414. if (!protos)
  415. return expanded;
  416. SMARTLIST_FOREACH_BEGIN(protos, const proto_entry_t *, ent) {
  417. const char *name = ent->name;
  418. if (strlen(name) > MAX_PROTOCOL_NAME_LENGTH) {
  419. log_warn(LD_NET, "When expanding a protocol entry, I got a very large "
  420. "protocol name. This is possibly an attack or a bug, unless "
  421. "the Tor network truly supports protocol names larger than "
  422. "%ud characters. The offending string was: %s",
  423. MAX_PROTOCOL_NAME_LENGTH, escaped(name));
  424. continue;
  425. }
  426. SMARTLIST_FOREACH_BEGIN(ent->ranges, const proto_range_t *, range) {
  427. uint32_t u;
  428. for (u = range->low; u <= range->high; ++u) {
  429. smartlist_add_asprintf(expanded, "%s=%lu", name, (unsigned long)u);
  430. if (smartlist_len(expanded) > MAX_PROTOCOLS_TO_EXPAND)
  431. goto too_many;
  432. }
  433. } SMARTLIST_FOREACH_END(range);
  434. } SMARTLIST_FOREACH_END(ent);
  435. smartlist_sort_strings(expanded);
  436. smartlist_uniq_strings(expanded); // This makes voting work. do not remove
  437. return expanded;
  438. too_many:
  439. SMARTLIST_FOREACH(expanded, char *, cp, tor_free(cp));
  440. smartlist_free(expanded);
  441. return NULL;
  442. }
  443. /** Voting helper: compare two singleton proto_entry_t items by version
  444. * alone. (A singleton item is one with a single range entry where
  445. * low==high.) */
  446. static int
  447. cmp_single_ent_by_version(const void **a_, const void **b_)
  448. {
  449. const proto_entry_t *ent_a = *a_;
  450. const proto_entry_t *ent_b = *b_;
  451. tor_assert(smartlist_len(ent_a->ranges) == 1);
  452. tor_assert(smartlist_len(ent_b->ranges) == 1);
  453. const proto_range_t *a = smartlist_get(ent_a->ranges, 0);
  454. const proto_range_t *b = smartlist_get(ent_b->ranges, 0);
  455. tor_assert(a->low == a->high);
  456. tor_assert(b->low == b->high);
  457. if (a->low < b->low) {
  458. return -1;
  459. } else if (a->low == b->low) {
  460. return 0;
  461. } else {
  462. return 1;
  463. }
  464. }
  465. /** Voting helper: Given a list of singleton protocol strings (of the form
  466. * Foo=7), return a canonical listing of all the protocol versions listed,
  467. * with as few ranges as possible, with protocol versions sorted lexically and
  468. * versions sorted in numerically increasing order, using as few range entries
  469. * as possible.
  470. **/
  471. static char *
  472. contract_protocol_list(const smartlist_t *proto_strings)
  473. {
  474. if (smartlist_len(proto_strings) == 0) {
  475. return tor_strdup("");
  476. }
  477. // map from name to list of single-version entries
  478. strmap_t *entry_lists_by_name = strmap_new();
  479. // list of protocol names
  480. smartlist_t *all_names = smartlist_new();
  481. // list of strings for the output we're building
  482. smartlist_t *chunks = smartlist_new();
  483. // Parse each item and stick it entry_lists_by_name. Build
  484. // 'all_names' at the same time.
  485. SMARTLIST_FOREACH_BEGIN(proto_strings, const char *, s) {
  486. if (BUG(!s))
  487. continue;// LCOV_EXCL_LINE
  488. proto_entry_t *ent = parse_single_entry(s, s+strlen(s));
  489. if (BUG(!ent))
  490. continue; // LCOV_EXCL_LINE
  491. smartlist_t *lst = strmap_get(entry_lists_by_name, ent->name);
  492. if (!lst) {
  493. smartlist_add(all_names, ent->name);
  494. lst = smartlist_new();
  495. strmap_set(entry_lists_by_name, ent->name, lst);
  496. }
  497. smartlist_add(lst, ent);
  498. } SMARTLIST_FOREACH_END(s);
  499. // We want to output the protocols sorted by their name.
  500. smartlist_sort_strings(all_names);
  501. SMARTLIST_FOREACH_BEGIN(all_names, const char *, name) {
  502. const int first_entry = (name_sl_idx == 0);
  503. smartlist_t *lst = strmap_get(entry_lists_by_name, name);
  504. tor_assert(lst);
  505. // Sort every entry with this name by version. They are
  506. // singletons, so there can't be overlap.
  507. smartlist_sort(lst, cmp_single_ent_by_version);
  508. if (! first_entry)
  509. smartlist_add_strdup(chunks, " ");
  510. /* We're going to construct this entry from the ranges. */
  511. proto_entry_t *entry = tor_malloc_zero(sizeof(proto_entry_t));
  512. entry->ranges = smartlist_new();
  513. entry->name = tor_strdup(name);
  514. // Now, find all the ranges of versions start..end where
  515. // all of start, start+1, start+2, ..end are included.
  516. int start_of_cur_series = 0;
  517. while (start_of_cur_series < smartlist_len(lst)) {
  518. const proto_entry_t *ent = smartlist_get(lst, start_of_cur_series);
  519. const proto_range_t *range = smartlist_get(ent->ranges, 0);
  520. const uint32_t ver_low = range->low;
  521. uint32_t ver_high = ver_low;
  522. int idx;
  523. for (idx = start_of_cur_series+1; idx < smartlist_len(lst); ++idx) {
  524. ent = smartlist_get(lst, idx);
  525. range = smartlist_get(ent->ranges, 0);
  526. if (range->low != ver_high + 1)
  527. break;
  528. ver_high += 1;
  529. }
  530. // Now idx is either off the end of the list, or the first sequence
  531. // break in the list.
  532. start_of_cur_series = idx;
  533. proto_range_t *new_range = tor_malloc_zero(sizeof(proto_range_t));
  534. new_range->low = ver_low;
  535. new_range->high = ver_high;
  536. smartlist_add(entry->ranges, new_range);
  537. }
  538. proto_entry_encode_into(chunks, entry);
  539. proto_entry_free(entry);
  540. } SMARTLIST_FOREACH_END(name);
  541. // Build the result...
  542. char *result = smartlist_join_strings(chunks, "", 0, NULL);
  543. // And free all the stuff we allocated.
  544. SMARTLIST_FOREACH_BEGIN(all_names, const char *, name) {
  545. smartlist_t *lst = strmap_get(entry_lists_by_name, name);
  546. tor_assert(lst);
  547. SMARTLIST_FOREACH(lst, proto_entry_t *, e, proto_entry_free(e));
  548. smartlist_free(lst);
  549. } SMARTLIST_FOREACH_END(name);
  550. strmap_free(entry_lists_by_name, NULL);
  551. smartlist_free(all_names);
  552. SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
  553. smartlist_free(chunks);
  554. return result;
  555. }
  556. /**
  557. * Protocol voting implementation.
  558. *
  559. * Given a list of strings describing protocol versions, return a newly
  560. * allocated string encoding all of the protocols that are listed by at
  561. * least <b>threshold</b> of the inputs.
  562. *
  563. * The string is minimal and sorted according to the rules of
  564. * contract_protocol_list above.
  565. */
  566. char *
  567. protover_compute_vote(const smartlist_t *list_of_proto_strings,
  568. int threshold)
  569. {
  570. if (smartlist_len(list_of_proto_strings) == 0) {
  571. return tor_strdup("");
  572. }
  573. smartlist_t *all_entries = smartlist_new();
  574. // First, parse the inputs and break them into singleton entries.
  575. SMARTLIST_FOREACH_BEGIN(list_of_proto_strings, const char *, vote) {
  576. smartlist_t *unexpanded = parse_protocol_list(vote);
  577. if (! unexpanded) {
  578. log_warn(LD_NET, "I failed with parsing a protocol list from "
  579. "an authority. The offending string was: %s",
  580. escaped(vote));
  581. continue;
  582. }
  583. smartlist_t *this_vote = expand_protocol_list(unexpanded);
  584. if (this_vote == NULL) {
  585. log_warn(LD_NET, "When expanding a protocol list from an authority, I "
  586. "got too many protocols. This is possibly an attack or a bug, "
  587. "unless the Tor network truly has expanded to support over %d "
  588. "different subprotocol versions. The offending string was: %s",
  589. MAX_PROTOCOLS_TO_EXPAND, escaped(vote));
  590. } else {
  591. smartlist_add_all(all_entries, this_vote);
  592. smartlist_free(this_vote);
  593. }
  594. SMARTLIST_FOREACH(unexpanded, proto_entry_t *, e, proto_entry_free(e));
  595. smartlist_free(unexpanded);
  596. } SMARTLIST_FOREACH_END(vote);
  597. if (smartlist_len(all_entries) == 0) {
  598. smartlist_free(all_entries);
  599. return tor_strdup("");
  600. }
  601. // Now sort the singleton entries
  602. smartlist_sort_strings(all_entries);
  603. // Now find all the strings that appear at least 'threshold' times.
  604. smartlist_t *include_entries = smartlist_new();
  605. const char *cur_entry = smartlist_get(all_entries, 0);
  606. int n_times = 0;
  607. SMARTLIST_FOREACH_BEGIN(all_entries, const char *, ent) {
  608. if (!strcmp(ent, cur_entry)) {
  609. n_times++;
  610. } else {
  611. if (n_times >= threshold && cur_entry)
  612. smartlist_add(include_entries, (void*)cur_entry);
  613. cur_entry = ent;
  614. n_times = 1 ;
  615. }
  616. } SMARTLIST_FOREACH_END(ent);
  617. if (n_times >= threshold && cur_entry)
  618. smartlist_add(include_entries, (void*)cur_entry);
  619. // Finally, compress that list.
  620. char *result = contract_protocol_list(include_entries);
  621. smartlist_free(include_entries);
  622. SMARTLIST_FOREACH(all_entries, char *, cp, tor_free(cp));
  623. smartlist_free(all_entries);
  624. return result;
  625. }
  626. /** Return true if every protocol version described in the string <b>s</b> is
  627. * one that we support, and false otherwise. If <b>missing_out</b> is
  628. * provided, set it to the list of protocols we do not support.
  629. *
  630. * NOTE: This is quadratic, but we don't do it much: only a few times per
  631. * consensus. Checking signatures should be way more expensive than this
  632. * ever would be.
  633. **/
  634. int
  635. protover_all_supported(const char *s, char **missing_out)
  636. {
  637. int all_supported = 1;
  638. smartlist_t *missing_some;
  639. smartlist_t *missing_completely;
  640. smartlist_t *missing_all;
  641. if (!s) {
  642. return 1;
  643. }
  644. smartlist_t *entries = parse_protocol_list(s);
  645. if (BUG(entries == NULL)) {
  646. log_warn(LD_NET, "Received an unparseable protocol list %s"
  647. " from the consensus", escaped(s));
  648. return 1;
  649. }
  650. missing_some = smartlist_new();
  651. missing_completely = smartlist_new();
  652. SMARTLIST_FOREACH_BEGIN(entries, const proto_entry_t *, ent) {
  653. protocol_type_t tp;
  654. if (str_to_protocol_type(ent->name, &tp) < 0) {
  655. if (smartlist_len(ent->ranges)) {
  656. goto unsupported;
  657. }
  658. continue;
  659. }
  660. SMARTLIST_FOREACH_BEGIN(ent->ranges, const proto_range_t *, range) {
  661. proto_entry_t *unsupported = tor_malloc_zero(sizeof(proto_entry_t));
  662. proto_range_t *versions = tor_malloc_zero(sizeof(proto_range_t));
  663. uint32_t i;
  664. unsupported->name = tor_strdup(ent->name);
  665. unsupported->ranges = smartlist_new();
  666. for (i = range->low; i <= range->high; ++i) {
  667. if (!protover_is_supported_here(tp, i)) {
  668. if (versions->low == 0 && versions->high == 0) {
  669. versions->low = i;
  670. /* Pre-emptively add the high now, just in case we're in a single
  671. * version range (e.g. "Link=999"). */
  672. versions->high = i;
  673. }
  674. /* If the last one to be unsupported is one less than the current
  675. * one, we're in a continous range, so set the high field. */
  676. if ((versions->high && versions->high == i - 1) ||
  677. /* Similarly, if the last high wasn't set and we're currently
  678. * one higher than the low, add current index as the highest
  679. * known high. */
  680. (!versions->high && versions->low == i - 1)) {
  681. versions->high = i;
  682. continue;
  683. }
  684. } else {
  685. /* If we hit a supported version, and we previously had a range,
  686. * we've hit a non-continuity. Copy the previous range and add it to
  687. * the unsupported->ranges list and zero-out the previous range for
  688. * the next iteration. */
  689. if (versions->low != 0 && versions->high != 0) {
  690. proto_range_t *versions_to_add = tor_malloc(sizeof(proto_range_t));
  691. versions_to_add->low = versions->low;
  692. versions_to_add->high = versions->high;
  693. smartlist_add(unsupported->ranges, versions_to_add);
  694. versions->low = 0;
  695. versions->high = 0;
  696. }
  697. }
  698. }
  699. /* Once we've run out of versions to check, see if we had any unsupported
  700. * ones and, if so, add them to unsupported->ranges. */
  701. if (versions->low != 0 && versions->high != 0) {
  702. smartlist_add(unsupported->ranges, versions);
  703. }
  704. /* Finally, if we had something unsupported, add it to the list of
  705. * missing_some things and mark that there was something missing. */
  706. if (smartlist_len(unsupported->ranges) != 0) {
  707. smartlist_add(missing_some, (void*) unsupported);
  708. all_supported = 0;
  709. } else {
  710. proto_entry_free(unsupported);
  711. tor_free(versions);
  712. }
  713. } SMARTLIST_FOREACH_END(range);
  714. continue;
  715. unsupported:
  716. all_supported = 0;
  717. smartlist_add(missing_completely, (void*) ent);
  718. } SMARTLIST_FOREACH_END(ent);
  719. /* We keep the two smartlists separate so that we can free the proto_entry_t
  720. * we created and put in missing_some, so here we add them together to build
  721. * the string. */
  722. missing_all = smartlist_new();
  723. smartlist_add_all(missing_all, missing_some);
  724. smartlist_add_all(missing_all, missing_completely);
  725. if (missing_out && !all_supported) {
  726. tor_assert(smartlist_len(missing_all) != 0);
  727. *missing_out = encode_protocol_list(missing_all);
  728. }
  729. SMARTLIST_FOREACH(missing_some, proto_entry_t *, ent, proto_entry_free(ent));
  730. smartlist_free(missing_some);
  731. smartlist_free(missing_completely);
  732. smartlist_free(missing_all);
  733. SMARTLIST_FOREACH(entries, proto_entry_t *, ent, proto_entry_free(ent));
  734. smartlist_free(entries);
  735. return all_supported;
  736. }
  737. /** Helper: Given a list of proto_entry_t, return true iff
  738. * <b>pr</b>=<b>ver</b> is included in that list. */
  739. static int
  740. protocol_list_contains(const smartlist_t *protos,
  741. protocol_type_t pr, uint32_t ver)
  742. {
  743. if (BUG(protos == NULL)) {
  744. return 0; // LCOV_EXCL_LINE
  745. }
  746. const char *pr_name = protocol_type_to_str(pr);
  747. if (BUG(pr_name == NULL)) {
  748. return 0; // LCOV_EXCL_LINE
  749. }
  750. SMARTLIST_FOREACH_BEGIN(protos, const proto_entry_t *, ent) {
  751. if (strcasecmp(ent->name, pr_name))
  752. continue;
  753. /* name matches; check the ranges */
  754. SMARTLIST_FOREACH_BEGIN(ent->ranges, const proto_range_t *, range) {
  755. if (ver >= range->low && ver <= range->high)
  756. return 1;
  757. } SMARTLIST_FOREACH_END(range);
  758. } SMARTLIST_FOREACH_END(ent);
  759. return 0;
  760. }
  761. /** Return a string describing the protocols supported by tor version
  762. * <b>version</b>, or an empty string if we cannot tell.
  763. *
  764. * Note that this is only used to infer protocols for Tor versions that
  765. * can't declare their own.
  766. **/
  767. /// C_RUST_COUPLED: src/rust/protover/protover.rs `compute_for_old_tor`
  768. const char *
  769. protover_compute_for_old_tor(const char *version)
  770. {
  771. if (version == NULL) {
  772. /* No known version; guess the oldest series that is still supported. */
  773. version = "0.2.5.15";
  774. }
  775. if (tor_version_as_new_as(version,
  776. FIRST_TOR_VERSION_TO_ADVERTISE_PROTOCOLS)) {
  777. return "";
  778. } else if (tor_version_as_new_as(version, "0.2.9.1-alpha")) {
  779. /* 0.2.9.1-alpha HSRend=2 */
  780. return "Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1-2 "
  781. "Link=1-4 LinkAuth=1 "
  782. "Microdesc=1-2 Relay=1-2";
  783. } else if (tor_version_as_new_as(version, "0.2.7.5")) {
  784. /* 0.2.7-stable added Desc=2, Microdesc=2, Cons=2, which indicate
  785. * ed25519 support. We'll call them present only in "stable" 027,
  786. * though. */
  787. return "Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
  788. "Link=1-4 LinkAuth=1 "
  789. "Microdesc=1-2 Relay=1-2";
  790. } else if (tor_version_as_new_as(version, "0.2.4.19")) {
  791. /* No currently supported Tor server versions are older than this, or
  792. * lack these protocols. */
  793. return "Cons=1 Desc=1 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
  794. "Link=1-4 LinkAuth=1 "
  795. "Microdesc=1 Relay=1-2";
  796. } else {
  797. /* Cannot infer protocols. */
  798. return "";
  799. }
  800. }
  801. /**
  802. * Release all storage held by static fields in protover.c
  803. */
  804. void
  805. protover_free_all(void)
  806. {
  807. if (supported_protocol_list) {
  808. smartlist_t *entries = supported_protocol_list;
  809. SMARTLIST_FOREACH(entries, proto_entry_t *, ent, proto_entry_free(ent));
  810. smartlist_free(entries);
  811. supported_protocol_list = NULL;
  812. }
  813. }
  814. #endif /* !defined(HAVE_RUST) */