protover.c 23 KB

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