commit b2b2e1c7f24d9b65059e3d089768d6c49ba4f58f Author: Nick Mathewson nickm@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 +}; +