commit b2b2e1c7f24d9b65059e3d089768d6c49ba4f58f
Author: Nick Mathewson <nickm(a)torproject.org>
Date: Tue Aug 9 19:11:47 2016 -0400
checkpoint basic protover backend
---
src/or/include.am | 2 +
src/or/main.c | 2 +
src/or/protover.c | 406 +++++++++++++++++++++++++++++++++++++++++++++++
src/or/protover.h | 50 ++++++
src/test/include.am | 1 +
src/test/test.c | 1 +
src/test/test.h | 1 +
src/test/test_protover.c | 91 +++++++++++
8 files changed, 554 insertions(+)
diff --git a/src/or/include.am b/src/or/include.am
index 3988eef..b4554aa 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -60,6 +60,7 @@ LIBTOR_A_SOURCES = \
src/or/shared_random_state.c \
src/or/transports.c \
src/or/periodic.c \
+ src/or/protover.c \
src/or/policies.c \
src/or/reasons.c \
src/or/relay.c \
@@ -172,6 +173,7 @@ ORHEADERS = \
src/or/transports.h \
src/or/periodic.h \
src/or/policies.h \
+ src/or/protover.h \
src/or/reasons.h \
src/or/relay.h \
src/or/rendcache.h \
diff --git a/src/or/main.c b/src/or/main.c
index 03c2b7e..c70fa82 100644
--- a/src/or/main.c
+++ b/src/or/main.c
@@ -46,6 +46,7 @@
#include "onion.h"
#include "periodic.h"
#include "policies.h"
+#include "protover.h"
#include "transports.h"
#include "relay.h"
#include "rendclient.h"
@@ -2974,6 +2975,7 @@ tor_free_all(int postfork)
ext_orport_free_all();
control_free_all();
sandbox_free_getaddrinfo_cache();
+ protover_free_all();
if (!postfork) {
config_free_all();
or_state_free_all();
diff --git a/src/or/protover.c b/src/or/protover.c
new file mode 100644
index 0000000..b78978e
--- /dev/null
+++ b/src/or/protover.c
@@ -0,0 +1,406 @@
+
+#define PROTOVER_PRIVATE
+
+#include "protover.h"
+#include "compat.h"
+#include "torlog.h"
+
+static const smartlist_t *get_supported_protocol_list(void);
+static int protocol_list_contains(const smartlist_t *protos,
+ protocol_type_t pr, uint32_t ver);
+
+/** Mapping between protocol type string and protocol type. */
+static const struct {
+ protocol_type_t protover_type;
+ const char *name;
+} PROTOCOL_NAMES[] = {
+ { PRT_LINK, "Link" },
+ { PRT_LINKAUTH, "LinkAuth" },
+ { PRT_RELAY, "Relay" },
+ { PRT_HSMID, "HSMid" },
+ { PRT_DIRCACHE, "DirCache" },
+ { PRT_HSDIR, "HSDir" },
+ { PRT_DESC, "Desc" },
+ { PRT_MICRODESC, "Microdesc"},
+ { PRT_CONS, "Cons" }
+};
+
+#define N_PROTOCOL_NAMES ARRAY_LENGTH(PROTOCOL_NAMES)
+
+/**
+ * Given a protocol_type_t, return the corresponding string used in
+ * descriptors.
+ */
+STATIC const char *
+protocol_type_to_str(protocol_type_t pr)
+{
+ unsigned i;
+ for (i=0; i < N_PROTOCOL_NAMES; ++i) {
+ if (PROTOCOL_NAMES[i].protover_type == pr)
+ return PROTOCOL_NAMES[i].name;
+ }
+ tor_assert_nonfatal_unreached_once();
+ return "UNKNOWN";
+}
+
+/**
+ * Given a string, find the corresponding protocol type and store it in
+ * <b>pr_out</b>. Return 0 on success, -1 on failure.
+ */
+STATIC int
+str_to_protocol_type(const char *s, protocol_type_t *pr_out)
+{
+ if (BUG(!pr_out))
+ return -1;
+
+ unsigned i;
+ for (i=0; i < N_PROTOCOL_NAMES; ++i) {
+ if (0 == strcmp(s, PROTOCOL_NAMES[i].name)) {
+ *pr_out = PROTOCOL_NAMES[i].protover_type;
+ return 0;
+ }
+ }
+
+ return -1;
+}
+
+/**
+ * Release all space held by a single proto_entry_t structure
+ */
+STATIC void
+proto_entry_free(proto_entry_t *entry)
+{
+ if (!entry)
+ return;
+ tor_free(entry->name);
+ SMARTLIST_FOREACH(entry->ranges, proto_range_t *, r, tor_free(r));
+ smartlist_free(entry->ranges);
+ tor_free(entry);
+}
+
+/**
+ * Given a string <b>s</b> and optional end-of-string pointer
+ * <b>end_of_range</b>, parse the protocol range and store it in
+ * <b>low_out</b> and <b>high_out</b>. A protocol range has the format U, or
+ * U-U, where U is an unsigned 32-bit integer.
+ */
+static int
+parse_version_range(const char *s, const char *end_of_range,
+ uint32_t *low_out, uint32_t *high_out)
+{
+ uint32_t low, high;
+ char *next = NULL;
+ int ok;
+
+ tor_assert(high_out);
+ tor_assert(low_out);
+
+ if (BUG(!end_of_range))
+ end_of_range = s + strlen(s); // LCOV_EXCL_LINE
+
+ /* Note that this wouldn't be safe if we didn't know that eventually,
+ * we'd hit a NUL */
+ low = (uint32_t) tor_parse_ulong(s, 10, 0, UINT32_MAX, &ok, &next);
+ if (!ok)
+ goto error;
+ if (next > end_of_range)
+ goto error;
+ if (next == end_of_range) {
+ high = low;
+ goto done;
+ }
+
+ if (*next != '-')
+ goto error;
+ s = next+1;
+ /* ibid */
+ high = (uint32_t) tor_parse_ulong(s, 10, 0, UINT32_MAX, &ok, &next);
+ if (!ok)
+ goto error;
+ if (next != end_of_range)
+ goto error;
+
+ done:
+ *high_out = high;
+ *low_out = low;
+ return 0;
+
+ error:
+ return -1;
+}
+
+/** Parse a single protocol entry from <b>s</b> up to an optional
+ * <b>end_of_entry</b> pointer, and return that protocol entry. Return NULL
+ * on error.
+ *
+ * A protocol entry has a keyword, an = sign, and zero or more ranges. */
+static proto_entry_t *
+parse_single_entry(const char *s, const char *end_of_entry)
+{
+ proto_entry_t *out = tor_malloc_zero(sizeof(proto_entry_t));
+ const char *equals;
+
+ out->ranges = smartlist_new();
+
+ if (BUG (!end_of_entry))
+ end_of_entry = s + strlen(s); // LCOV_EXCL_LINE
+
+ /* There must be an =. */
+ equals = memchr(s, '=', end_of_entry - s);
+ if (!equals)
+ goto error;
+
+ out->name = tor_strndup(s, equals-s);
+
+ tor_assert(equals < end_of_entry);
+
+ s = equals + 1;
+ while (s < end_of_entry) {
+ const char *comma = memchr(s, ',', end_of_entry-s);
+ proto_range_t *range = tor_malloc_zero(sizeof(proto_range_t));
+ if (! comma)
+ comma = end_of_entry;
+
+ smartlist_add(out->ranges, range);
+ if (parse_version_range(s, comma, &range->low, &range->high) < 0) {
+ goto error;
+ }
+
+ if (range->low > range->high) {
+ goto error;
+ }
+
+ s = comma;
+ while (*s == ',' && s < end_of_entry)
+ ++s;
+ }
+
+ return out;
+
+ error:
+ proto_entry_free(out);
+ return NULL;
+}
+
+/**
+ * Parse the protocol list from <b>s</b> and return it as a smartlist of
+ * proto_entry_t
+ */
+STATIC smartlist_t *
+parse_protocol_list(const char *s)
+{
+ smartlist_t *entries = smartlist_new();
+
+ while (*s) {
+ /* Find the next space or the NUL. */
+ const char *end_of_entry = strchr(s, ' ');
+ proto_entry_t *entry;
+ if (!end_of_entry)
+ end_of_entry = s + strlen(s);
+
+ entry = parse_single_entry(s, end_of_entry);
+
+ if (! entry)
+ goto error;
+
+ smartlist_add(entries, entry);
+
+ s = end_of_entry;
+ while (*s == ' ')
+ ++s;
+ }
+
+ return entries;
+
+ error:
+ SMARTLIST_FOREACH(entries, proto_entry_t *, ent, proto_entry_free(ent));
+ smartlist_free(entries);
+ return NULL;
+}
+
+/**
+ * Given a protocol type and version number, return true iff we know
+ * how to speak that protocol.
+ */
+int
+protover_is_supported_here(protocol_type_t pr, uint32_t ver)
+{
+ const smartlist_t *ours = get_supported_protocol_list();
+ return protocol_list_contains(ours, pr, ver);
+}
+
+/** Return the canonical string containing the list of protocols
+ * that we support. */
+const char *
+get_supported_protocols(void)
+{
+ return
+ "Cons=1-2 "
+ "Desc=1-2 "
+ "DirCache=1 "
+ "HSDir=1 "
+ "HSMid=1 "
+ "Link=1-4 "
+ "LinkAuth=1 "
+ "Microdesc=1-2 "
+ "Relay=1-2";
+}
+
+/** The protocols from get_supported_protocols(), as parsed into a list of
+ * proto_entry_t values. Access this via get_supported_protocol_list. */
+static smartlist_t *supported_protocol_list = NULL;
+
+/** Return a pointer to a smartlist of proto_entry_t for the protocols
+ * we support. */
+static const smartlist_t *
+get_supported_protocol_list(void)
+{
+ if (PREDICT_UNLIKELY(supported_protocol_list == NULL)) {
+ supported_protocol_list = parse_protocol_list(get_supported_protocols());
+ }
+ return supported_protocol_list;
+}
+
+/**
+ * Given a protocol entry, encode it at the end of the smartlist <b>chunks</b>
+ * as one or more newly allocated strings.
+ */
+static void
+proto_entry_encode_into(smartlist_t *chunks, const proto_entry_t *entry)
+{
+ smartlist_add_asprintf(chunks, "%s=", entry->name);
+
+ SMARTLIST_FOREACH_BEGIN(entry->ranges, proto_range_t *, range) {
+ const char *comma = "";
+ if (range_sl_idx != 0)
+ comma = ",";
+
+ if (range->low == range->high) {
+ smartlist_add_asprintf(chunks, "%s%lu",
+ comma, (unsigned long)range->low);
+ } else {
+ smartlist_add_asprintf(chunks, "%s%lu-%lu",
+ comma, (unsigned long)range->low,
+ (unsigned long)range->high);
+ }
+ } SMARTLIST_FOREACH_END(range);
+}
+
+/** Given a list of space-separated proto_entry_t items,
+ * encode it into a newly allocated space-separated string. */
+STATIC char *
+encode_protocol_list(const smartlist_t *sl)
+{
+ const char *separator = "";
+ smartlist_t *chunks = smartlist_new();
+ SMARTLIST_FOREACH_BEGIN(sl, const proto_entry_t *, ent) {
+ smartlist_add(chunks, tor_strdup(separator));
+
+ proto_entry_encode_into(chunks, ent);
+
+ separator = " ";
+ } SMARTLIST_FOREACH_END(ent);
+
+ char *result = smartlist_join_strings(chunks, "", 0, NULL);
+
+ SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
+ smartlist_free(chunks);
+
+ return result;
+}
+
+/** Return true if every protocol version described in the string <b>s</b> is
+ * one that we support, and false otherwise. If <b>missing_out</b> is
+ * provided, set it to the list of protocols we do not support.
+ *
+ * NOTE: This is quadratic, but we don't do it much: only a few times per
+ * consensus. Checking signatures should be way more expensive than this
+ * ever would be.
+ **/
+int
+protover_all_supported(const char *s, char **missing_out)
+{
+ int all_supported = 1;
+ smartlist_t *missing;
+
+ if (!s) {
+ return 1;
+ }
+
+ smartlist_t *entries = parse_protocol_list(s);
+
+ missing = smartlist_new();
+
+ SMARTLIST_FOREACH_BEGIN(entries, const proto_entry_t *, ent) {
+ protocol_type_t tp;
+ if (str_to_protocol_type(ent->name, &tp) < 0) {
+ if (smartlist_len(ent->ranges)) {
+ goto unsupported;
+ }
+ continue;
+ }
+
+ SMARTLIST_FOREACH_BEGIN(ent->ranges, const proto_range_t *, range) {
+ uint32_t i;
+ for (i = range->low; i <= range->high; ++i) {
+ if (!protover_is_supported_here(tp, i)) {
+ goto unsupported;
+ }
+ }
+ } SMARTLIST_FOREACH_END(range);
+
+ continue;
+
+ unsupported:
+ all_supported = 0;
+ smartlist_add(missing, (void*) ent);
+ } SMARTLIST_FOREACH_END(ent);
+
+
+ if (missing_out && !all_supported) {
+ tor_assert(0 != smartlist_len(missing));
+ *missing_out = encode_protocol_list(missing);
+ }
+ smartlist_free(missing);
+
+ SMARTLIST_FOREACH(entries, proto_entry_t *, ent, proto_entry_free(ent));
+ smartlist_free(entries);
+
+ return all_supported;
+}
+
+static int
+protocol_list_contains(const smartlist_t *protos,
+ protocol_type_t pr, uint32_t ver)
+{
+ if (BUG(protos == NULL)) {
+ return 0;
+ }
+ const char *pr_name = protocol_type_to_str(pr);
+ if (BUG(pr_name == NULL)) {
+ return 0;
+ }
+
+ SMARTLIST_FOREACH_BEGIN(protos, const proto_entry_t *, ent) {
+ if (strcasecmp(ent->name, pr_name))
+ continue;
+ /* name matches; check the ranges */
+ SMARTLIST_FOREACH_BEGIN(ent->ranges, const proto_range_t *, range) {
+ if (ver >= range->low && ver <= range->high)
+ return 1;
+ } SMARTLIST_FOREACH_END(range);
+ } SMARTLIST_FOREACH_END(ent);
+
+ return 0;
+}
+
+void
+protover_free_all(void)
+{
+ if (supported_protocol_list) {
+ smartlist_t *entries = supported_protocol_list;
+ SMARTLIST_FOREACH(entries, proto_entry_t *, ent, proto_entry_free(ent));
+ smartlist_free(entries);
+ supported_protocol_list = NULL;
+ }
+}
diff --git a/src/or/protover.h b/src/or/protover.h
new file mode 100644
index 0000000..d12a067
--- /dev/null
+++ b/src/or/protover.h
@@ -0,0 +1,50 @@
+
+#ifndef TOR_PROTOVER_H
+#define TOR_PROTOVER_H
+
+#include "container.h"
+
+typedef enum protocol_type_t {
+ PRT_LINK,
+ PRT_LINKAUTH,
+ PRT_RELAY,
+ PRT_HSMID,
+ PRT_DIRCACHE,
+ PRT_HSDIR,
+ PRT_DESC,
+ PRT_MICRODESC,
+ PRT_CONS,
+} protocol_type_t;
+
+/*
+const protover_set_t *protover_get_supported(void);
+protover_set_t *protover_set_parse(const char *s);
+int protover_is_supported_here_str(const char *name, uint32_t ver);
+int protover_is_supported_by(protocol_type_t pr, uint32_t ver);
+*/
+
+int protover_all_supported(const char *s, char **missing);
+int protover_is_supported_here(protocol_type_t pr, uint32_t ver);
+const char *get_supported_protocols(void);
+
+void protover_free_all(void);
+
+#ifdef PROTOVER_PRIVATE
+typedef struct proto_range_t {
+ uint32_t low;
+ uint32_t high;
+} proto_range_t;
+
+typedef struct proto_entry_t {
+ char *name;
+ smartlist_t *ranges;
+} proto_entry_t;
+
+STATIC smartlist_t *parse_protocol_list(const char *s);
+STATIC void proto_entry_free(proto_entry_t *entry);
+STATIC char *encode_protocol_list(const smartlist_t *sl);
+STATIC const char *protocol_type_to_str(protocol_type_t pr);
+STATIC int str_to_protocol_type(const char *s, protocol_type_t *pr_out);
+#endif
+
+#endif
diff --git a/src/test/include.am b/src/test/include.am
index 2e91f7c..a64310d 100644
--- a/src/test/include.am
+++ b/src/test/include.am
@@ -107,6 +107,7 @@ src_test_test_SOURCES = \
src/test/test_options.c \
src/test/test_policy.c \
src/test/test_procmon.c \
+ src/test/test_protover.c \
src/test/test_pt.c \
src/test/test_pubsub.c \
src/test/test_relay.c \
diff --git a/src/test/test.c b/src/test/test.c
index 2f10c7e..9a41b97 100644
--- a/src/test/test.c
+++ b/src/test/test.c
@@ -1214,6 +1214,7 @@ struct testgroup_t testgroups[] = {
{ "options/", options_tests },
{ "policy/" , policy_tests },
{ "procmon/", procmon_tests },
+ { "protover/", protover_tests },
{ "pt/", pt_tests },
{ "relay/" , relay_tests },
{ "relaycell/", relaycell_tests },
diff --git a/src/test/test.h b/src/test/test.h
index c0643e1..d9ea57d 100644
--- a/src/test/test.h
+++ b/src/test/test.h
@@ -206,6 +206,7 @@ extern struct testcase_t oos_tests[];
extern struct testcase_t options_tests[];
extern struct testcase_t policy_tests[];
extern struct testcase_t procmon_tests[];
+extern struct testcase_t protover_tests[];
extern struct testcase_t pubsub_tests[];
extern struct testcase_t pt_tests[];
extern struct testcase_t relay_tests[];
diff --git a/src/test/test_protover.c b/src/test/test_protover.c
new file mode 100644
index 0000000..606ca57
--- /dev/null
+++ b/src/test/test_protover.c
@@ -0,0 +1,91 @@
+/* Copyright (c) 2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#define PROTOVER_PRIVATE
+
+#include "orconfig.h"
+#include "test.h"
+
+#include "protover.h"
+
+static void
+test_protover_parse(void *arg)
+{
+ (void) arg;
+ char *re_encoded = NULL;
+
+ const char *orig = "Foo=1,3 Bar=3 Baz= Quux=9-12,14,15-16,900";
+ smartlist_t *elts = parse_protocol_list(orig);
+
+ tt_assert(elts);
+ tt_int_op(smartlist_len(elts), OP_EQ, 4);
+
+ const proto_entry_t *e;
+ const proto_range_t *r;
+ e = smartlist_get(elts, 0);
+ tt_str_op(e->name, OP_EQ, "Foo");
+ tt_int_op(smartlist_len(e->ranges), OP_EQ, 2);
+ {
+ r = smartlist_get(e->ranges, 0);
+ tt_int_op(r->low, OP_EQ, 1);
+ tt_int_op(r->high, OP_EQ, 1);
+
+ r = smartlist_get(e->ranges, 1);
+ tt_int_op(r->low, OP_EQ, 3);
+ tt_int_op(r->high, OP_EQ, 3);
+ }
+
+ e = smartlist_get(elts, 1);
+ tt_str_op(e->name, OP_EQ, "Bar");
+ tt_int_op(smartlist_len(e->ranges), OP_EQ, 1);
+ {
+ r = smartlist_get(e->ranges, 0);
+ tt_int_op(r->low, OP_EQ, 3);
+ tt_int_op(r->high, OP_EQ, 3);
+ }
+
+ e = smartlist_get(elts, 2);
+ tt_str_op(e->name, OP_EQ, "Baz");
+ tt_int_op(smartlist_len(e->ranges), OP_EQ, 0);
+
+ e = smartlist_get(elts, 3);
+ tt_str_op(e->name, OP_EQ, "Quux");
+ tt_int_op(smartlist_len(e->ranges), OP_EQ, 4);
+ {
+ r = smartlist_get(e->ranges, 0);
+ tt_int_op(r->low, OP_EQ, 9);
+ tt_int_op(r->high, OP_EQ, 12);
+
+ r = smartlist_get(e->ranges, 1);
+ tt_int_op(r->low, OP_EQ, 14);
+ tt_int_op(r->high, OP_EQ, 14);
+
+ r = smartlist_get(e->ranges, 2);
+ tt_int_op(r->low, OP_EQ, 15);
+ tt_int_op(r->high, OP_EQ, 16);
+
+ r = smartlist_get(e->ranges, 3);
+ tt_int_op(r->low, OP_EQ, 900);
+ tt_int_op(r->high, OP_EQ, 900);
+ }
+
+ re_encoded = encode_protocol_list(elts);
+ tt_assert(re_encoded);
+ tt_str_op(re_encoded, OP_EQ, orig);
+
+ done:
+ if (elts)
+ SMARTLIST_FOREACH(elts, proto_entry_t *, ent, proto_entry_free(ent));
+ smartlist_free(elts);
+ tor_free(re_encoded);
+}
+
+
+#define PV_TEST(name, flags) \
+ { #name, test_protover_ ##name, (flags), NULL, NULL }
+
+struct testcase_t protover_tests[] = {
+ PV_TEST(parse, 0),
+ END_OF_TESTCASES
+};
+
