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