Move literally everything out of src/or

This commit won't build yet -- it just puts everything in a slightly
more logical place.

The reasoning here is that "src/core" will hold the stuff that every (or
nearly every) tor instance will need in order to do onion routing.
Other features (including some necessary ones) will live in
"src/feature".  The "src/app" directory will hold the stuff needed
to have Tor be an application you can actually run.

This commit DOES NOT refactor the former contents of src/or into a
logical set of acyclic libraries, or change any code at all.  That
will have to come in the future.

We will continue to move things around and split them in the future,
but I hope this lays a reasonable groundwork for doing so.

13 files changed, 2188 insertions, 0 deletions

diff --git a/src/core/proto/proto_cell.c b/src/core/proto/proto_cell.c
new file mode 100644
index 0000000000..41554bd1b0
--- /dev/null
+++ b/src/core/proto/proto_cell.c
@@ -0,0 +1,86 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "or/or.h"
+#include "lib/container/buffers.h"
+#include "or/proto_cell.h"
+
+#include "or/connection_or.h"
+
+#include "or/var_cell_st.h"
+
+/** True iff the cell command <b>command</b> is one that implies a
+ * variable-length cell in Tor link protocol <b>linkproto</b>. */
+static inline int
+cell_command_is_var_length(uint8_t command, int linkproto)
+{
+  /* If linkproto is v2 (2), CELL_VERSIONS is the only variable-length cells
+   * work as implemented here. If it's 1, there are no variable-length cells.
+   * Tor does not support other versions right now, and so can't negotiate
+   * them.
+   */
+  switch (linkproto) {
+  case 1:
+    /* Link protocol version 1 has no variable-length cells. */
+    return 0;
+  case 2:
+    /* In link protocol version 2, VERSIONS is the only variable-length cell */
+    return command == CELL_VERSIONS;
+  case 0:
+  case 3:
+  default:
+    /* In link protocol version 3 and later, and in version "unknown",
+     * commands 128 and higher indicate variable-length. VERSIONS is
+     * grandfathered in. */
+    return command == CELL_VERSIONS || command >= 128;
+  }
+}
+
+/** Check <b>buf</b> for a variable-length cell according to the rules of link
+ * protocol version <b>linkproto</b>.  If one is found, pull it off the buffer
+ * and assign a newly allocated var_cell_t to *<b>out</b>, and return 1.
+ * Return 0 if whatever is on the start of buf_t is not a variable-length
+ * cell.  Return 1 and set *<b>out</b> to NULL if there seems to be the start
+ * of a variable-length cell on <b>buf</b>, but the whole thing isn't there
+ * yet. */
+int
+fetch_var_cell_from_buf(buf_t *buf, var_cell_t **out, int linkproto)
+{
+  char hdr[VAR_CELL_MAX_HEADER_SIZE];
+  var_cell_t *result;
+  uint8_t command;
+  uint16_t length;
+  const int wide_circ_ids = linkproto >= MIN_LINK_PROTO_FOR_WIDE_CIRC_IDS;
+  const int circ_id_len = get_circ_id_size(wide_circ_ids);
+  const unsigned header_len = get_var_cell_header_size(wide_circ_ids);
+  *out = NULL;
+  if (buf_datalen(buf) < header_len)
+    return 0;
+  buf_peek(buf, hdr, header_len);
+
+  command = get_uint8(hdr + circ_id_len);
+  if (!(cell_command_is_var_length(command, linkproto)))
+    return 0;
+
+  length = ntohs(get_uint16(hdr + circ_id_len + 1));
+  if (buf_datalen(buf) < (size_t)(header_len+length))
+    return 1;
+
+  result = var_cell_new(length);
+  result->command = command;
+  if (wide_circ_ids)
+    result->circ_id = ntohl(get_uint32(hdr));
+  else
+    result->circ_id = ntohs(get_uint16(hdr));
+
+  buf_drain(buf, header_len);
+  buf_peek(buf, (char*) result->payload, length);
+  buf_drain(buf, length);
+
+  *out = result;
+  return 1;
+}
+
diff --git a/src/core/proto/proto_cell.h b/src/core/proto/proto_cell.h
new file mode 100644
index 0000000000..b29645e41d
--- /dev/null
+++ b/src/core/proto/proto_cell.h
@@ -0,0 +1,17 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_PROTO_CELL_H
+#define TOR_PROTO_CELL_H
+
+struct buf_t;
+struct var_cell_t;
+
+int fetch_var_cell_from_buf(struct buf_t *buf, struct var_cell_t **out,
+                            int linkproto);
+
+#endif /* !defined(TOR_PROTO_CELL_H) */
+
diff --git a/src/core/proto/proto_control0.c b/src/core/proto/proto_control0.c
new file mode 100644
index 0000000000..34e7ddb8d9
--- /dev/null
+++ b/src/core/proto/proto_control0.c
@@ -0,0 +1,26 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "or/or.h"
+#include "lib/container/buffers.h"
+#include "or/proto_control0.h"
+
+/** Return 1 iff buf looks more like it has an (obsolete) v0 controller
+ * command on it than any valid v1 controller command. */
+int
+peek_buf_has_control0_command(buf_t *buf)
+{
+  if (buf_datalen(buf) >= 4) {
+    char header[4];
+    uint16_t cmd;
+    buf_peek(buf, header, sizeof(header));
+    cmd = ntohs(get_uint16(header+2));
+    if (cmd <= 0x14)
+      return 1; /* This is definitely not a v1 control command. */
+  }
+  return 0;
+}
+
diff --git a/src/core/proto/proto_control0.h b/src/core/proto/proto_control0.h
new file mode 100644
index 0000000000..b80dc6c8f8
--- /dev/null
+++ b/src/core/proto/proto_control0.h
@@ -0,0 +1,14 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_PROTO_CONTROL0_H
+#define TOR_PROTO_CONTROL0_H
+
+struct buf_t;
+int peek_buf_has_control0_command(struct buf_t *buf);
+
+#endif /* !defined(TOR_PROTO_CONTROL0_H) */
+
diff --git a/src/core/proto/proto_ext_or.c b/src/core/proto/proto_ext_or.c
new file mode 100644
index 0000000000..f30d876231
--- /dev/null
+++ b/src/core/proto/proto_ext_or.c
@@ -0,0 +1,40 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "or/or.h"
+#include "lib/container/buffers.h"
+#include "or/ext_orport.h"
+#include "or/proto_ext_or.h"
+
+/** The size of the header of an Extended ORPort message: 2 bytes for
+ *  COMMAND, 2 bytes for BODYLEN */
+#define EXT_OR_CMD_HEADER_SIZE 4
+
+/** Read <b>buf</b>, which should contain an Extended ORPort message
+ *  from a transport proxy. If well-formed, create and populate
+ *  <b>out</b> with the Extended ORport message. Return 0 if the
+ *  buffer was incomplete, 1 if it was well-formed and -1 if we
+ *  encountered an error while parsing it.  */
+int
+fetch_ext_or_command_from_buf(buf_t *buf, ext_or_cmd_t **out)
+{
+  char hdr[EXT_OR_CMD_HEADER_SIZE];
+  uint16_t len;
+
+  if (buf_datalen(buf) < EXT_OR_CMD_HEADER_SIZE)
+    return 0;
+  buf_peek(buf, hdr, sizeof(hdr));
+  len = ntohs(get_uint16(hdr+2));
+  if (buf_datalen(buf) < (unsigned)len + EXT_OR_CMD_HEADER_SIZE)
+    return 0;
+  *out = ext_or_cmd_new(len);
+  (*out)->cmd = ntohs(get_uint16(hdr));
+  (*out)->len = len;
+  buf_drain(buf, EXT_OR_CMD_HEADER_SIZE);
+  buf_get_bytes(buf, (*out)->body, len);
+  return 1;
+}
+
diff --git a/src/core/proto/proto_ext_or.h b/src/core/proto/proto_ext_or.h
new file mode 100644
index 0000000000..708a45974b
--- /dev/null
+++ b/src/core/proto/proto_ext_or.h
@@ -0,0 +1,22 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_PROTO_EXT_OR_H
+#define TOR_PROTO_EXT_OR_H
+
+struct buf_t;
+
+/** A parsed Extended ORPort message. */
+typedef struct ext_or_cmd_t {
+  uint16_t cmd; /** Command type */
+  uint16_t len; /** Body length */
+  char body[FLEXIBLE_ARRAY_MEMBER]; /** Message body */
+} ext_or_cmd_t;
+
+int fetch_ext_or_command_from_buf(struct buf_t *buf,
+                                  struct ext_or_cmd_t **out);
+
+#endif /* !defined(TOR_PROTO_EXT_OR_H) */
diff --git a/src/core/proto/proto_http.c b/src/core/proto/proto_http.c
new file mode 100644
index 0000000000..ecc669e3a4
--- /dev/null
+++ b/src/core/proto/proto_http.c
@@ -0,0 +1,171 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#define PROTO_HTTP_PRIVATE
+#include "or/or.h"
+#include "lib/container/buffers.h"
+#include "or/proto_http.h"
+
+/** Return true if <b>cmd</b> looks like a HTTP (proxy) request. */
+int
+peek_buf_has_http_command(const buf_t *buf)
+{
+  if (buf_peek_startswith(buf, "CONNECT ") ||
+      buf_peek_startswith(buf, "DELETE ") ||
+      buf_peek_startswith(buf, "GET ") ||
+      buf_peek_startswith(buf, "POST ") ||
+      buf_peek_startswith(buf, "PUT " ))
+    return 1;
+  return 0;
+}
+
+/** There is a (possibly incomplete) http statement on <b>buf</b>, of the
+ * form "\%s\\r\\n\\r\\n\%s", headers, body. (body may contain NULs.)
+ * If a) the headers include a Content-Length field and all bytes in
+ * the body are present, or b) there's no Content-Length field and
+ * all headers are present, then:
+ *
+ *  - strdup headers into <b>*headers_out</b>, and NUL-terminate it.
+ *  - memdup body into <b>*body_out</b>, and NUL-terminate it.
+ *  - Then remove them from <b>buf</b>, and return 1.
+ *
+ *  - If headers or body is NULL, discard that part of the buf.
+ *  - If a headers or body doesn't fit in the arg, return -1.
+ *  (We ensure that the headers or body don't exceed max len,
+ *   _even if_ we're planning to discard them.)
+ *  - If force_complete is true, then succeed even if not all of the
+ *    content has arrived.
+ *
+ * Else, change nothing and return 0.
+ */
+int
+fetch_from_buf_http(buf_t *buf,
+                    char **headers_out, size_t max_headerlen,
+                    char **body_out, size_t *body_used, size_t max_bodylen,
+                    int force_complete)
+{
+  const char *headers;
+  size_t headerlen, bodylen, contentlen=0;
+  int crlf_offset;
+  int r;
+
+  if (buf_datalen(buf) == 0)
+    return 0;
+
+  crlf_offset = buf_find_string_offset(buf, "\r\n\r\n", 4);
+  if (crlf_offset > (int)max_headerlen ||
+      (crlf_offset < 0 && buf_datalen(buf) > max_headerlen)) {
+    log_debug(LD_HTTP,"headers too long.");
+    return -1;
+  } else if (crlf_offset < 0) {
+    log_debug(LD_HTTP,"headers not all here yet.");
+    return 0;
+  }
+  /* Okay, we have a full header.  Make sure it all appears in the first
+   * chunk. */
+  headerlen = crlf_offset + 4;
+  size_t headers_in_chunk = 0;
+  buf_pullup(buf, headerlen, &headers, &headers_in_chunk);
+
+  bodylen = buf_datalen(buf) - headerlen;
+  log_debug(LD_HTTP,"headerlen %d, bodylen %d.", (int)headerlen, (int)bodylen);
+
+  if (max_headerlen <= headerlen) {
+    log_warn(LD_HTTP,"headerlen %d larger than %d. Failing.",
+             (int)headerlen, (int)max_headerlen-1);
+    return -1;
+  }
+  if (max_bodylen <= bodylen) {
+    log_warn(LD_HTTP,"bodylen %d larger than %d. Failing.",
+             (int)bodylen, (int)max_bodylen-1);
+    return -1;
+  }
+
+  r = buf_http_find_content_length(headers, headerlen, &contentlen);
+  if (r == -1) {
+    log_warn(LD_PROTOCOL, "Content-Length is bogus; maybe "
+             "someone is trying to crash us.");
+    return -1;
+  } else if (r == 1) {
+    /* if content-length is malformed, then our body length is 0. fine. */
+    log_debug(LD_HTTP,"Got a contentlen of %d.",(int)contentlen);
+    if (bodylen < contentlen) {
+      if (!force_complete) {
+        log_debug(LD_HTTP,"body not all here yet.");
+        return 0; /* not all there yet */
+      }
+    }
+    if (bodylen > contentlen) {
+      bodylen = contentlen;
+      log_debug(LD_HTTP,"bodylen reduced to %d.",(int)bodylen);
+    }
+  } else {
+    tor_assert(r == 0);
+    /* Leave bodylen alone */
+  }
+
+  /* all happy. copy into the appropriate places, and return 1 */
+  if (headers_out) {
+    *headers_out = tor_malloc(headerlen+1);
+    buf_get_bytes(buf, *headers_out, headerlen);
+    (*headers_out)[headerlen] = 0; /* NUL terminate it */
+  }
+  if (body_out) {
+    tor_assert(body_used);
+    *body_used = bodylen;
+    *body_out = tor_malloc(bodylen+1);
+    buf_get_bytes(buf, *body_out, bodylen);
+    (*body_out)[bodylen] = 0; /* NUL terminate it */
+  }
+  return 1;
+}
+
+/**
+ * Scan the HTTP headers in the <b>headerlen</b>-byte memory range at
+ * <b>headers</b>, looking for a "Content-Length" header.  Try to set
+ * *<b>result_out</b> to the numeric value of that header if possible.
+ * Return -1 if the header was malformed, 0 if it was missing, and 1 if
+ * it was present and well-formed.
+ */
+STATIC int
+buf_http_find_content_length(const char *headers, size_t headerlen,
+                             size_t *result_out)
+{
+  const char *p, *newline;
+  char *len_str, *eos=NULL;
+  size_t remaining, result;
+  int ok;
+  *result_out = 0; /* The caller shouldn't look at this unless the
+                    * return value is 1, but let's prevent confusion */
+
+#define CONTENT_LENGTH "\r\nContent-Length: "
+  p = (char*) tor_memstr(headers, headerlen, CONTENT_LENGTH);
+  if (p == NULL)
+    return 0;
+
+  tor_assert(p >= headers && p < headers+headerlen);
+  remaining = (headers+headerlen)-p;
+  p += strlen(CONTENT_LENGTH);
+  remaining -= strlen(CONTENT_LENGTH);
+
+  newline = memchr(p, '\n', remaining);
+  if (newline == NULL)
+    return -1;
+
+  len_str = tor_memdup_nulterm(p, newline-p);
+  /* We limit the size to INT_MAX because other parts of the buffer.c
+   * code don't like buffers to be any bigger than that. */
+  result = (size_t) tor_parse_uint64(len_str, 10, 0, INT_MAX, &ok, &eos);
+  if (eos && !tor_strisspace(eos)) {
+    ok = 0;
+  } else {
+    *result_out = result;
+  }
+  tor_free(len_str);
+
+  return ok ? 1 : -1;
+}
+
diff --git a/src/core/proto/proto_http.h b/src/core/proto/proto_http.h
new file mode 100644
index 0000000000..587e435ede
--- /dev/null
+++ b/src/core/proto/proto_http.h
@@ -0,0 +1,24 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_PROTO_HTTP_H
+#define TOR_PROTO_HTTP_H
+
+struct buf_t;
+
+int fetch_from_buf_http(struct buf_t *buf,
+                        char **headers_out, size_t max_headerlen,
+                        char **body_out, size_t *body_used, size_t max_bodylen,
+                        int force_complete);
+int peek_buf_has_http_command(const struct buf_t *buf);
+
+#ifdef PROTO_HTTP_PRIVATE
+STATIC int buf_http_find_content_length(const char *headers, size_t headerlen,
+                                        size_t *result_out);
+#endif
+
+#endif /* !defined(TOR_PROTO_HTTP_H) */
+
diff --git a/src/core/proto/proto_socks.c b/src/core/proto/proto_socks.c
new file mode 100644
index 0000000000..f5e6ce581b
--- /dev/null
+++ b/src/core/proto/proto_socks.c
@@ -0,0 +1,713 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "or/or.h"
+#include "or/addressmap.h"
+#include "lib/container/buffers.h"
+#include "or/connection.h"
+#include "or/control.h"
+#include "or/config.h"
+#include "lib/crypt_ops/crypto_util.h"
+#include "or/ext_orport.h"
+#include "or/proto_socks.h"
+#include "or/reasons.h"
+
+#include "or/socks_request_st.h"
+
+static void socks_request_set_socks5_error(socks_request_t *req,
+                              socks5_reply_status_t reason);
+
+static int parse_socks(const char *data, size_t datalen, socks_request_t *req,
+                       int log_sockstype, int safe_socks, ssize_t *drain_out,
+                       size_t *want_length_out);
+static int parse_socks_client(const uint8_t *data, size_t datalen,
+                              int state, char **reason,
+                              ssize_t *drain_out);
+/**
+ * Wait this many seconds before warning the user about using SOCKS unsafely
+ * again. */
+#define SOCKS_WARN_INTERVAL 5
+
+/** Warn that the user application has made an unsafe socks request using
+ * protocol <b>socks_protocol</b> on port <b>port</b>.  Don't warn more than
+ * once per SOCKS_WARN_INTERVAL, unless <b>safe_socks</b> is set. */
+static void
+log_unsafe_socks_warning(int socks_protocol, const char *address,
+                         uint16_t port, int safe_socks)
+{
+  static ratelim_t socks_ratelim = RATELIM_INIT(SOCKS_WARN_INTERVAL);
+
+  if (safe_socks) {
+    log_fn_ratelim(&socks_ratelim, LOG_WARN, LD_APP,
+             "Your application (using socks%d to port %d) is giving "
+             "Tor only an IP address. Applications that do DNS resolves "
+             "themselves may leak information. Consider using Socks4A "
+             "(e.g. via privoxy or socat) instead. For more information, "
+             "please see https://wiki.torproject.org/TheOnionRouter/"
+             "TorFAQ#SOCKSAndDNS.%s",
+             socks_protocol,
+             (int)port,
+             safe_socks ? " Rejecting." : "");
+  }
+  control_event_client_status(LOG_WARN,
+                              "DANGEROUS_SOCKS PROTOCOL=SOCKS%d ADDRESS=%s:%d",
+                              socks_protocol, address, (int)port);
+}
+
+/** Do not attempt to parse socks messages longer than this.  This value is
+ * actually significantly higher than the longest possible socks message. */
+#define MAX_SOCKS_MESSAGE_LEN 512
+
+/** Return a new socks_request_t. */
+socks_request_t *
+socks_request_new(void)
+{
+  return tor_malloc_zero(sizeof(socks_request_t));
+}
+
+/** Free all storage held in the socks_request_t <b>req</b>. */
+void
+socks_request_free_(socks_request_t *req)
+{
+  if (!req)
+    return;
+  if (req->username) {
+    memwipe(req->username, 0x10, req->usernamelen);
+    tor_free(req->username);
+  }
+  if (req->password) {
+    memwipe(req->password, 0x04, req->passwordlen);
+    tor_free(req->password);
+  }
+  memwipe(req, 0xCC, sizeof(socks_request_t));
+  tor_free(req);
+}
+
+/** There is a (possibly incomplete) socks handshake on <b>buf</b>, of one
+ * of the forms
+ *  - socks4: "socksheader username\\0"
+ *  - socks4a: "socksheader username\\0 destaddr\\0"
+ *  - socks5 phase one: "version #methods methods"
+ *  - socks5 phase two: "version command 0 addresstype..."
+ * If it's a complete and valid handshake, and destaddr fits in
+ *   MAX_SOCKS_ADDR_LEN bytes, then pull the handshake off the buf,
+ *   assign to <b>req</b>, and return 1.
+ *
+ * If it's invalid or too big, return -1.
+ *
+ * Else it's not all there yet, leave buf alone and return 0.
+ *
+ * If you want to specify the socks reply, write it into <b>req->reply</b>
+ *   and set <b>req->replylen</b>, else leave <b>req->replylen</b> alone.
+ *
+ * If <b>log_sockstype</b> is non-zero, then do a notice-level log of whether
+ * the connection is possibly leaking DNS requests locally or not.
+ *
+ * If <b>safe_socks</b> is true, then reject unsafe socks protocols.
+ *
+ * If returning 0 or -1, <b>req->address</b> and <b>req->port</b> are
+ * undefined.
+ */
+int
+fetch_from_buf_socks(buf_t *buf, socks_request_t *req,
+                     int log_sockstype, int safe_socks)
+{
+  int res;
+  ssize_t n_drain;
+  size_t want_length = 128;
+  const char *head = NULL;
+  size_t datalen = 0;
+
+  if (buf_datalen(buf) < 2) /* version and another byte */
+    return 0;
+
+  do {
+    n_drain = 0;
+    buf_pullup(buf, want_length, &head, &datalen);
+    tor_assert(head && datalen >= 2);
+    want_length = 0;
+
+    res = parse_socks(head, datalen, req, log_sockstype,
+                      safe_socks, &n_drain, &want_length);
+
+    if (n_drain < 0)
+      buf_clear(buf);
+    else if (n_drain > 0)
+      buf_drain(buf, n_drain);
+
+  } while (res == 0 && head && want_length < buf_datalen(buf) &&
+           buf_datalen(buf) >= 2);
+
+  return res;
+}
+
+/** Create a SOCKS5 reply message with <b>reason</b> in its REP field and
+ * have Tor send it as error response to <b>req</b>.
+ */
+static void
+socks_request_set_socks5_error(socks_request_t *req,
+                  socks5_reply_status_t reason)
+{
+   req->replylen = 10;
+   memset(req->reply,0,10);
+
+   req->reply[0] = 0x05;   // VER field.
+   req->reply[1] = reason; // REP field.
+   req->reply[3] = 0x01;   // ATYP field.
+}
+
+static const char SOCKS_PROXY_IS_NOT_AN_HTTP_PROXY_MSG[] =
+  "HTTP/1.0 501 Tor is not an HTTP Proxy\r\n"
+  "Content-Type: text/html; charset=iso-8859-1\r\n\r\n"
+  "<html>\n"
+  "<head>\n"
+  "<title>This is a SOCKS Proxy, Not An HTTP Proxy</title>\n"
+  "</head>\n"
+  "<body>\n"
+  "<h1>This is a SOCKs proxy, not an HTTP proxy.</h1>\n"
+  "<p>\n"
+  "It appears you have configured your web browser to use this Tor port as\n"
+  "an HTTP proxy.\n"
+  "</p><p>\n"
+  "This is not correct: This port is configured as a SOCKS proxy, not\n"
+  "an HTTP proxy. If you need an HTTP proxy tunnel, use the HTTPTunnelPort\n"
+  "configuration option in place of, or in addition to, SOCKSPort.\n"
+  "Please configure your client accordingly.\n"
+  "</p>\n"
+  "<p>\n"
+  "See <a href=\"https://www.torproject.org/documentation.html\">"
+  "https://www.torproject.org/documentation.html</a> for more "
+  "information.\n"
+  "</p>\n"
+  "</body>\n"
+  "</html>\n";
+
+/** Implementation helper to implement fetch_from_*_socks.  Instead of looking
+ * at a buffer's contents, we look at the <b>datalen</b> bytes of data in
+ * <b>data</b>. Instead of removing data from the buffer, we set
+ * <b>drain_out</b> to the amount of data that should be removed (or -1 if the
+ * buffer should be cleared).  Instead of pulling more data into the first
+ * chunk of the buffer, we set *<b>want_length_out</b> to the number of bytes
+ * we'd like to see in the input buffer, if they're available. */
+static int
+parse_socks(const char *data, size_t datalen, socks_request_t *req,
+            int log_sockstype, int safe_socks, ssize_t *drain_out,
+            size_t *want_length_out)
+{
+  unsigned int len;
+  char tmpbuf[TOR_ADDR_BUF_LEN+1];
+  tor_addr_t destaddr;
+  uint32_t destip;
+  uint8_t socksver;
+  char *next, *startaddr;
+  unsigned char usernamelen, passlen;
+  struct in_addr in;
+
+  if (datalen < 2) {
+    /* We always need at least 2 bytes. */
+    *want_length_out = 2;
+    return 0;
+  }
+
+  if (req->socks_version == 5 && !req->got_auth) {
+    /* See if we have received authentication.  Strictly speaking, we should
+       also check whether we actually negotiated username/password
+       authentication.  But some broken clients will send us authentication
+       even if we negotiated SOCKS_NO_AUTH. */
+    if (*data == 1) { /* username/pass version 1 */
+      /* Format is: authversion [1 byte] == 1
+                    usernamelen [1 byte]
+                    username    [usernamelen bytes]
+                    passlen     [1 byte]
+                    password    [passlen bytes] */
+      usernamelen = (unsigned char)*(data + 1);
+      if (datalen < 2u + usernamelen + 1u) {
+        *want_length_out = 2u + usernamelen + 1u;
+        return 0;
+      }
+      passlen = (unsigned char)*(data + 2u + usernamelen);
+      if (datalen < 2u + usernamelen + 1u + passlen) {
+        *want_length_out = 2u + usernamelen + 1u + passlen;
+        return 0;
+      }
+      req->replylen = 2; /* 2 bytes of response */
+      req->reply[0] = 1; /* authversion == 1 */
+      req->reply[1] = 0; /* authentication successful */
+      log_debug(LD_APP,
+               "socks5: Accepted username/password without checking.");
+      if (usernamelen) {
+        req->username = tor_memdup(data+2u, usernamelen);
+        req->usernamelen = usernamelen;
+      }
+      if (passlen) {
+        req->password = tor_memdup(data+3u+usernamelen, passlen);
+        req->passwordlen = passlen;
+      }
+      *drain_out = 2u + usernamelen + 1u + passlen;
+      req->got_auth = 1;
+      *want_length_out = 7; /* Minimal socks5 command. */
+      return 0;
+    } else if (req->auth_type == SOCKS_USER_PASS) {
+      /* unknown version byte */
+      log_warn(LD_APP, "Socks5 username/password version %d not recognized; "
+               "rejecting.", (int)*data);
+      return -1;
+    }
+  }
+
+  socksver = *data;
+
+  switch (socksver) { /* which version of socks? */
+    case 5: /* socks5 */
+
+      if (req->socks_version != 5) { /* we need to negotiate a method */
+        unsigned char nummethods = (unsigned char)*(data+1);
+        int have_user_pass, have_no_auth;
+        int r=0;
+        tor_assert(!req->socks_version);
+        if (datalen < 2u+nummethods) {
+          *want_length_out = 2u+nummethods;
+          return 0;
+        }
+        if (!nummethods)
+          return -1;
+        req->replylen = 2; /* 2 bytes of response */
+        req->reply[0] = 5; /* socks5 reply */
+        have_user_pass = (memchr(data+2, SOCKS_USER_PASS, nummethods) !=NULL);
+        have_no_auth   = (memchr(data+2, SOCKS_NO_AUTH,   nummethods) !=NULL);
+        if (have_user_pass && !(have_no_auth && req->socks_prefer_no_auth)) {
+          req->auth_type = SOCKS_USER_PASS;
+          req->reply[1] = SOCKS_USER_PASS; /* tell client to use "user/pass"
+                                              auth method */
+          req->socks_version = 5; /* remember we've already negotiated auth */
+          log_debug(LD_APP,"socks5: accepted method 2 (username/password)");
+          r=0;
+        } else if (have_no_auth) {
+          req->reply[1] = SOCKS_NO_AUTH; /* tell client to use "none" auth
+                                            method */
+          req->socks_version = 5; /* remember we've already negotiated auth */
+          log_debug(LD_APP,"socks5: accepted method 0 (no authentication)");
+          r=0;
+        } else {
+          log_warn(LD_APP,
+                    "socks5: offered methods don't include 'no auth' or "
+                    "username/password. Rejecting.");
+          req->reply[1] = '\xFF'; /* reject all methods */
+          r=-1;
+        }
+        /* Remove packet from buf. Some SOCKS clients will have sent extra
+         * junk at this point; let's hope it's an authentication message. */
+        *drain_out = 2u + nummethods;
+
+        return r;
+      }
+      if (req->auth_type != SOCKS_NO_AUTH && !req->got_auth) {
+        log_warn(LD_APP,
+                 "socks5: negotiated authentication, but none provided");
+        return -1;
+      }
+      /* we know the method; read in the request */
+      log_debug(LD_APP,"socks5: checking request");
+      if (datalen < 7) {/* basic info plus >=1 for addr plus 2 for port */
+        *want_length_out = 7;
+        return 0; /* not yet */
+      }
+      req->command = (unsigned char) *(data+1);
+      if (req->command != SOCKS_COMMAND_CONNECT &&
+          req->command != SOCKS_COMMAND_RESOLVE &&
+          req->command != SOCKS_COMMAND_RESOLVE_PTR) {
+        /* not a connect or resolve or a resolve_ptr? we don't support it. */
+        socks_request_set_socks5_error(req,SOCKS5_COMMAND_NOT_SUPPORTED);
+
+        log_warn(LD_APP,"socks5: command %d not recognized. Rejecting.",
+                 req->command);
+        return -1;
+      }
+      switch (*(data+3)) { /* address type */
+        case 1: /* IPv4 address */
+        case 4: /* IPv6 address */ {
+          const int is_v6 = *(data+3) == 4;
+          const unsigned addrlen = is_v6 ? 16 : 4;
+          log_debug(LD_APP,"socks5: ipv4 address type");
+          if (datalen < 6+addrlen) {/* ip/port there? */
+            *want_length_out = 6+addrlen;
+            return 0; /* not yet */
+          }
+
+          if (is_v6)
+            tor_addr_from_ipv6_bytes(&destaddr, data+4);
+          else
+            tor_addr_from_ipv4n(&destaddr, get_uint32(data+4));
+
+          tor_addr_to_str(tmpbuf, &destaddr, sizeof(tmpbuf), 1);
+
+          if (BUG(strlen(tmpbuf)+1 > MAX_SOCKS_ADDR_LEN)) {
+            /* LCOV_EXCL_START -- This branch is unreachable, given the
+             * size of tmpbuf and the actual value of MAX_SOCKS_ADDR_LEN */
+            socks_request_set_socks5_error(req, SOCKS5_GENERAL_ERROR);
+            log_warn(LD_APP,
+                     "socks5 IP takes %d bytes, which doesn't fit in %d. "
+                     "Rejecting.",
+                     (int)strlen(tmpbuf)+1,(int)MAX_SOCKS_ADDR_LEN);
+            return -1;
+            /* LCOV_EXCL_STOP */
+          }
+          strlcpy(req->address,tmpbuf,sizeof(req->address));
+          req->port = ntohs(get_uint16(data+4+addrlen));
+          *drain_out = 6+addrlen;
+          if (req->command != SOCKS_COMMAND_RESOLVE_PTR &&
+              !addressmap_have_mapping(req->address,0)) {
+            log_unsafe_socks_warning(5, req->address, req->port, safe_socks);
+            if (safe_socks) {
+              socks_request_set_socks5_error(req, SOCKS5_NOT_ALLOWED);
+              return -1;
+            }
+          }
+          return 1;
+        }
+        case 3: /* fqdn */
+          log_debug(LD_APP,"socks5: fqdn address type");
+          if (req->command == SOCKS_COMMAND_RESOLVE_PTR) {
+            socks_request_set_socks5_error(req,
+                                           SOCKS5_ADDRESS_TYPE_NOT_SUPPORTED);
+            log_warn(LD_APP, "socks5 received RESOLVE_PTR command with "
+                     "hostname type. Rejecting.");
+            return -1;
+          }
+          len = (unsigned char)*(data+4);
+          if (datalen < 7+len) { /* addr/port there? */
+            *want_length_out = 7+len;
+            return 0; /* not yet */
+          }
+          if (BUG(len+1 > MAX_SOCKS_ADDR_LEN)) {
+            /* LCOV_EXCL_START -- unreachable, since len is at most 255,
+             * and MAX_SOCKS_ADDR_LEN is 256. */
+            socks_request_set_socks5_error(req, SOCKS5_GENERAL_ERROR);
+            log_warn(LD_APP,
+                     "socks5 hostname is %d bytes, which doesn't fit in "
+                     "%d. Rejecting.", len+1,MAX_SOCKS_ADDR_LEN);
+            return -1;
+            /* LCOV_EXCL_STOP */
+          }
+          memcpy(req->address,data+5,len);
+          req->address[len] = 0;
+          req->port = ntohs(get_uint16(data+5+len));
+          *drain_out = 5+len+2;
+
+          if (!string_is_valid_dest(req->address)) {
+            socks_request_set_socks5_error(req, SOCKS5_GENERAL_ERROR);
+
+            log_warn(LD_PROTOCOL,
+                     "Your application (using socks5 to port %d) gave Tor "
+                     "a malformed hostname: %s. Rejecting the connection.",
+                     req->port, escaped_safe_str_client(req->address));
+            return -1;
+          }
+          if (log_sockstype)
+            log_notice(LD_APP,
+                  "Your application (using socks5 to port %d) instructed "
+                  "Tor to take care of the DNS resolution itself if "
+                  "necessary. This is good.", req->port);
+          return 1;
+        default: /* unsupported */
+          socks_request_set_socks5_error(req,
+                                         SOCKS5_ADDRESS_TYPE_NOT_SUPPORTED);
+          log_warn(LD_APP,"socks5: unsupported address type %d. Rejecting.",
+                   (int) *(data+3));
+          return -1;
+      }
+      tor_assert(0);
+      break;
+    case 4: { /* socks4 */
+      enum {socks4, socks4a} socks4_prot = socks4a;
+      const char *authstart, *authend;
+      /* http://ss5.sourceforge.net/socks4.protocol.txt */
+      /* http://ss5.sourceforge.net/socks4A.protocol.txt */
+
+      req->socks_version = 4;
+      if (datalen < SOCKS4_NETWORK_LEN) {/* basic info available? */
+        *want_length_out = SOCKS4_NETWORK_LEN;
+        return 0; /* not yet */
+      }
+      // buf_pullup(buf, 1280);
+      req->command = (unsigned char) *(data+1);
+      if (req->command != SOCKS_COMMAND_CONNECT &&
+          req->command != SOCKS_COMMAND_RESOLVE) {
+        /* not a connect or resolve? we don't support it. (No resolve_ptr with
+         * socks4.) */
+        log_warn(LD_APP,"socks4: command %d not recognized. Rejecting.",
+                 req->command);
+        return -1;
+      }
+
+      req->port = ntohs(get_uint16(data+2));
+      destip = ntohl(get_uint32(data+4));
+      if ((!req->port && req->command!=SOCKS_COMMAND_RESOLVE) || !destip) {
+        log_warn(LD_APP,"socks4: Port or DestIP is zero. Rejecting.");
+        return -1;
+      }
+      if (destip >> 8) {
+        log_debug(LD_APP,"socks4: destip not in form 0.0.0.x.");
+        in.s_addr = htonl(destip);
+        tor_inet_ntoa(&in,tmpbuf,sizeof(tmpbuf));
+        if (BUG(strlen(tmpbuf)+1 > MAX_SOCKS_ADDR_LEN)) {
+          /* LCOV_EXCL_START -- This branch is unreachable, given the
+           * size of tmpbuf and the actual value of MAX_SOCKS_ADDR_LEN */
+          log_debug(LD_APP,"socks4 addr (%d bytes) too long. Rejecting.",
+                    (int)strlen(tmpbuf));
+          return -1;
+          /* LCOV_EXCL_STOP */
+        }
+        log_debug(LD_APP,
+                  "socks4: successfully read destip (%s)",
+                  safe_str_client(tmpbuf));
+        socks4_prot = socks4;
+      }
+
+      authstart = data + SOCKS4_NETWORK_LEN;
+      next = memchr(authstart, 0,
+                    datalen-SOCKS4_NETWORK_LEN);
+      if (!next) {
+        if (datalen >= 1024) {
+          log_debug(LD_APP, "Socks4 user name too long; rejecting.");
+          return -1;
+        }
+        log_debug(LD_APP,"socks4: Username not here yet.");
+        *want_length_out = datalen+1024; /* More than we need, but safe */
+        return 0;
+      }
+      authend = next;
+      tor_assert(next < data+datalen);
+
+      startaddr = NULL;
+      if (socks4_prot != socks4a &&
+          !addressmap_have_mapping(tmpbuf,0)) {
+        log_unsafe_socks_warning(4, tmpbuf, req->port, safe_socks);
+
+        if (safe_socks)
+          return -1;
+      }
+      if (socks4_prot == socks4a) {
+        if (next+1 == data+datalen) {
+          log_debug(LD_APP,"socks4: No part of destaddr here yet.");
+          *want_length_out = datalen + 1024; /* More than we need, but safe */
+          return 0;
+        }
+        startaddr = next+1;
+        next = memchr(startaddr, 0, data + datalen - startaddr);
+        if (!next) {
+          if (datalen >= 1024) {
+            log_debug(LD_APP,"socks4: Destaddr too long.");
+            return -1;
+          }
+          log_debug(LD_APP,"socks4: Destaddr not all here yet.");
+          *want_length_out = datalen + 1024; /* More than we need, but safe */
+          return 0;
+        }
+        if (MAX_SOCKS_ADDR_LEN <= next-startaddr) {
+          log_warn(LD_APP,"socks4: Destaddr too long. Rejecting.");
+          return -1;
+        }
+        // tor_assert(next < buf->cur+buf_datalen(buf));
+
+        if (log_sockstype)
+          log_notice(LD_APP,
+                     "Your application (using socks4a to port %d) instructed "
+                     "Tor to take care of the DNS resolution itself if "
+                     "necessary. This is good.", req->port);
+      }
+      log_debug(LD_APP,"socks4: Everything is here. Success.");
+      strlcpy(req->address, startaddr ? startaddr : tmpbuf,
+              sizeof(req->address));
+      if (!string_is_valid_dest(req->address)) {
+        log_warn(LD_PROTOCOL,
+                 "Your application (using socks4 to port %d) gave Tor "
+                 "a malformed hostname: %s. Rejecting the connection.",
+                 req->port, escaped_safe_str_client(req->address));
+        return -1;
+      }
+      if (authend != authstart) {
+        req->got_auth = 1;
+        req->usernamelen = authend - authstart;
+        req->username = tor_memdup(authstart, authend - authstart);
+      }
+      /* next points to the final \0 on inbuf */
+      *drain_out = next - data + 1;
+      return 1;
+    }
+    case 'G': /* get */
+    case 'H': /* head */
+    case 'P': /* put/post */
+    case 'C': /* connect */
+      strlcpy((char*)req->reply, SOCKS_PROXY_IS_NOT_AN_HTTP_PROXY_MSG,
+              MAX_SOCKS_REPLY_LEN);
+      req->replylen = strlen((char*)req->reply)+1;
+      /* fall through */
+    default: /* version is not socks4 or socks5 */
+      log_warn(LD_APP,
+               "Socks version %d not recognized. (This port is not an "
+               "HTTP proxy; did you want to use HTTPTunnelPort?)",
+               *(data));
+      {
+        /* Tell the controller the first 8 bytes. */
+        char *tmp = tor_strndup(data, datalen < 8 ? datalen : 8);
+        control_event_client_status(LOG_WARN,
+                                    "SOCKS_UNKNOWN_PROTOCOL DATA=\"%s\"",
+                                    escaped(tmp));
+        tor_free(tmp);
+      }
+      return -1;
+  }
+}
+
+/** Inspect a reply from SOCKS server stored in <b>buf</b> according
+ * to <b>state</b>, removing the protocol data upon success. Return 0 on
+ * incomplete response, 1 on success and -1 on error, in which case
+ * <b>reason</b> is set to a descriptive message (free() when finished
+ * with it).
+ *
+ * As a special case, 2 is returned when user/pass is required
+ * during SOCKS5 handshake and user/pass is configured.
+ */
+int
+fetch_from_buf_socks_client(buf_t *buf, int state, char **reason)
+{
+  ssize_t drain = 0;
+  int r;
+  const char *head = NULL;
+  size_t datalen = 0;
+
+  if (buf_datalen(buf) < 2)
+    return 0;
+
+  buf_pullup(buf, MAX_SOCKS_MESSAGE_LEN, &head, &datalen);
+  tor_assert(head && datalen >= 2);
+
+  r = parse_socks_client((uint8_t*)head, datalen,
+                         state, reason, &drain);
+  if (drain > 0)
+    buf_drain(buf, drain);
+  else if (drain < 0)
+    buf_clear(buf);
+
+  return r;
+}
+
+/** Implementation logic for fetch_from_*_socks_client. */
+static int
+parse_socks_client(const uint8_t *data, size_t datalen,
+                   int state, char **reason,
+                   ssize_t *drain_out)
+{
+  unsigned int addrlen;
+  *drain_out = 0;
+  if (datalen < 2)
+    return 0;
+
+  switch (state) {
+    case PROXY_SOCKS4_WANT_CONNECT_OK:
+      /* Wait for the complete response */
+      if (datalen < 8)
+        return 0;
+
+      if (data[1] != 0x5a) {
+        *reason = tor_strdup(socks4_response_code_to_string(data[1]));
+        return -1;
+      }
+
+      /* Success */
+      *drain_out = 8;
+      return 1;
+
+    case PROXY_SOCKS5_WANT_AUTH_METHOD_NONE:
+      /* we don't have any credentials */
+      if (data[1] != 0x00) {
+        *reason = tor_strdup("server doesn't support any of our "
+                             "available authentication methods");
+        return -1;
+      }
+
+      log_info(LD_NET, "SOCKS 5 client: continuing without authentication");
+      *drain_out = -1;
+      return 1;
+
+    case PROXY_SOCKS5_WANT_AUTH_METHOD_RFC1929:
+      /* we have a username and password. return 1 if we can proceed without
+       * providing authentication, or 2 otherwise. */
+      switch (data[1]) {
+        case 0x00:
+          log_info(LD_NET, "SOCKS 5 client: we have auth details but server "
+                            "doesn't require authentication.");
+          *drain_out = -1;
+          return 1;
+        case 0x02:
+          log_info(LD_NET, "SOCKS 5 client: need authentication.");
+          *drain_out = -1;
+          return 2;
+        /* fall through */
+      }
+
+      *reason = tor_strdup("server doesn't support any of our available "
+                           "authentication methods");
+      return -1;
+
+    case PROXY_SOCKS5_WANT_AUTH_RFC1929_OK:
+      /* handle server reply to rfc1929 authentication */
+      if (data[1] != 0x00) {
+        *reason = tor_strdup("authentication failed");
+        return -1;
+      }
+
+      log_info(LD_NET, "SOCKS 5 client: authentication successful.");
+      *drain_out = -1;
+      return 1;
+
+    case PROXY_SOCKS5_WANT_CONNECT_OK:
+      /* response is variable length. BND.ADDR, etc, isn't needed
+       * (don't bother with buf_pullup()), but make sure to eat all
+       * the data used */
+
+      /* wait for address type field to arrive */
+      if (datalen < 4)
+        return 0;
+
+      switch (data[3]) {
+        case 0x01: /* ip4 */
+          addrlen = 4;
+          break;
+        case 0x04: /* ip6 */
+          addrlen = 16;
+          break;
+        case 0x03: /* fqdn (can this happen here?) */
+          if (datalen < 5)
+            return 0;
+          addrlen = 1 + data[4];
+          break;
+        default:
+          *reason = tor_strdup("invalid response to connect request");
+          return -1;
+      }
+
+      /* wait for address and port */
+      if (datalen < 6 + addrlen)
+        return 0;
+
+      if (data[1] != 0x00) {
+        *reason = tor_strdup(socks5_response_code_to_string(data[1]));
+        return -1;
+      }
+
+      *drain_out = 6 + addrlen;
+      return 1;
+  }
+
+  /* LCOV_EXCL_START */
+  /* shouldn't get here if the input state is one we know about... */
+  tor_assert(0);
+
+  return -1;
+  /* LCOV_EXCL_STOP */
+}
diff --git a/src/core/proto/proto_socks.h b/src/core/proto/proto_socks.h
new file mode 100644
index 0000000000..53de288f65
--- /dev/null
+++ b/src/core/proto/proto_socks.h
@@ -0,0 +1,21 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_PROTO_SOCKS_H
+#define TOR_PROTO_SOCKS_H
+
+struct socks_request_t;
+struct buf_t;
+
+struct socks_request_t *socks_request_new(void);
+void socks_request_free_(struct socks_request_t *req);
+#define socks_request_free(req) \
+  FREE_AND_NULL(socks_request_t, socks_request_free_, (req))
+int fetch_from_buf_socks(struct buf_t *buf, socks_request_t *req,
+                         int log_sockstype, int safe_socks);
+int fetch_from_buf_socks_client(buf_t *buf, int state, char **reason);
+
+#endif /* !defined(TOR_PROTO_SOCKS_H) */
diff --git a/src/core/proto/protover.c b/src/core/proto/protover.c
new file mode 100644
index 0000000000..f63c134565
--- /dev/null
+++ b/src/core/proto/protover.c
@@ -0,0 +1,923 @@
+/* Copyright (c) 2016-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file protover.c
+ * \brief Versioning information for different pieces of the Tor protocol.
+ *
+ * Starting in version 0.2.9.3-alpha, Tor places separate version numbers on
+ * each of the different components of its protocol. Relays use these numbers
+ * to advertise what versions of the protocols they can support, and clients
+ * use them to find what they can ask a given relay to do.  Authorities vote
+ * on the supported protocol versions for each relay, and also vote on the
+ * which protocols you should have to support in order to be on the Tor
+ * network. All Tor instances use these required/recommended protocol versions
+ * to tell what level of support for recent protocols each relay has, and
+ * to decide whether they should be running given their current protocols.
+ *
+ * The main advantage of these protocol versions numbers over using Tor
+ * version numbers is that they allow different implementations of the Tor
+ * protocols to develop independently, without having to claim compatibility
+ * with specific versions of Tor.
+ **/
+
+#define PROTOVER_PRIVATE
+
+#include "or/or.h"
+#include "or/protover.h"
+#include "or/routerparse.h"
+
+#ifndef HAVE_RUST
+
+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. */
+/// C_RUST_COUPLED: src/rust/protover/protover.rs `PROTOCOL_NAMES`
+static const struct {
+  protocol_type_t protover_type;
+  const char *name;
+} PROTOCOL_NAMES[] = {
+  { PRT_LINK, "Link" },
+  { PRT_LINKAUTH, "LinkAuth" },
+  { PRT_RELAY, "Relay" },
+  { PRT_DIRCACHE, "DirCache" },
+  { PRT_HSDIR, "HSDir" },
+  { PRT_HSINTRO, "HSIntro" },
+  { PRT_HSREND, "HSRend" },
+  { PRT_DESC, "Desc" },
+  { PRT_MICRODESC, "Microdesc"},
+  { PRT_CONS, "Cons" }
+};
+
+#define N_PROTOCOL_NAMES ARRAY_LENGTH(PROTOCOL_NAMES)
+
+/* Maximum allowed length of any single subprotocol name. */
+// C_RUST_COUPLED: src/rust/protover/protover.rs
+//                 `MAX_PROTOCOL_NAME_LENGTH`
+static const unsigned MAX_PROTOCOL_NAME_LENGTH = 100;
+
+/**
+ * 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;
+  }
+  /* LCOV_EXCL_START */
+  tor_assert_nonfatal_unreached_once();
+  return "UNKNOWN";
+  /* LCOV_EXCL_STOP */
+}
+
+/**
+ * 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);
+}
+
+/** The largest possible protocol version. */
+#define MAX_PROTOCOL_VERSION (UINT32_MAX-1)
+
+/**
+ * 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
+
+  /* A range must start with a digit. */
+  if (!TOR_ISDIGIT(*s)) {
+    goto error;
+  }
+
+  /* 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, MAX_PROTOCOL_VERSION, &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 */
+  if (!TOR_ISDIGIT(*s)) {
+    goto error;
+  }
+  high = (uint32_t) tor_parse_ulong(s, 10, 0,
+                                    MAX_PROTOCOL_VERSION, &ok, &next);
+  if (!ok)
+    goto error;
+  if (next != end_of_range)
+    goto error;
+
+  if (low > high)
+    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;
+
+  /* The name must be nonempty */
+  if (equals == s)
+    goto error;
+
+  /* The name must not be longer than MAX_PROTOCOL_NAME_LENGTH. */
+  if (equals - s > (int)MAX_PROTOCOL_NAME_LENGTH) {
+    log_warn(LD_NET, "When parsing a protocol entry, I got a very large "
+             "protocol name. This is possibly an attack or a bug, unless "
+             "the Tor network truly supports protocol names larger than "
+             "%ud characters. The offending string was: %s",
+             MAX_PROTOCOL_NAME_LENGTH, escaped(out->name));
+    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;
+    }
+
+    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;
+}
+
+/**
+ * Return true if the unparsed protover in <b>s</b> would contain a protocol
+ * name longer than MAX_PROTOCOL_NAME_LENGTH, and false otherwise.
+ */
+bool
+protover_contains_long_protocol_names(const char *s)
+{
+  smartlist_t *list = parse_protocol_list(s);
+  if (!list)
+    return true; /* yes, has a dangerous name */
+  SMARTLIST_FOREACH(list, proto_entry_t *, ent, proto_entry_free(ent));
+  smartlist_free(list);
+  return false; /* no, looks fine */
+}
+
+/**
+ * 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 true iff "list" encodes a protocol list that includes support for
+ * the indicated protocol and version.
+ */
+int
+protocol_list_supports_protocol(const char *list, protocol_type_t tp,
+                                uint32_t version)
+{
+  /* NOTE: This is a pretty inefficient implementation. If it ever shows
+   * up in profiles, we should memoize it.
+   */
+  smartlist_t *protocols = parse_protocol_list(list);
+  if (!protocols) {
+    return 0;
+  }
+  int contains = protocol_list_contains(protocols, tp, version);
+
+  SMARTLIST_FOREACH(protocols, proto_entry_t *, ent, proto_entry_free(ent));
+  smartlist_free(protocols);
+  return contains;
+}
+
+/**
+ * Return true iff "list" encodes a protocol list that includes support for
+ * the indicated protocol and version, or some later version.
+ */
+int
+protocol_list_supports_protocol_or_later(const char *list,
+                                         protocol_type_t tp,
+                                         uint32_t version)
+{
+  /* NOTE: This is a pretty inefficient implementation. If it ever shows
+   * up in profiles, we should memoize it.
+   */
+  smartlist_t *protocols = parse_protocol_list(list);
+  if (!protocols) {
+    return 0;
+  }
+  const char *pr_name = protocol_type_to_str(tp);
+
+  int contains = 0;
+  SMARTLIST_FOREACH_BEGIN(protocols, proto_entry_t *, proto) {
+    if (strcasecmp(proto->name, pr_name))
+      continue;
+    SMARTLIST_FOREACH_BEGIN(proto->ranges, const proto_range_t *, range) {
+      if (range->high >= version) {
+        contains = 1;
+        goto found;
+      }
+    } SMARTLIST_FOREACH_END(range);
+  } SMARTLIST_FOREACH_END(proto);
+
+ found:
+  SMARTLIST_FOREACH(protocols, proto_entry_t *, ent, proto_entry_free(ent));
+  smartlist_free(protocols);
+  return contains;
+}
+
+/** Return the canonical string containing the list of protocols
+ * that we support. */
+/// C_RUST_COUPLED: src/rust/protover/protover.rs `SUPPORTED_PROTOCOLS`
+const char *
+protover_get_supported_protocols(void)
+{
+  return
+    "Cons=1-2 "
+    "Desc=1-2 "
+    "DirCache=1-2 "
+    "HSDir=1-2 "
+    "HSIntro=3-4 "
+    "HSRend=1-2 "
+    "Link=1-5 "
+    "LinkAuth=1,3 "
+    "Microdesc=1-2 "
+    "Relay=1-2";
+}
+
+/** The protocols from protover_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(protover_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_strdup(chunks, 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;
+}
+
+/* We treat any protocol list with more than this many subprotocols in it
+ * as a DoS attempt. */
+/// C_RUST_COUPLED: src/rust/protover/protover.rs
+///                 `MAX_PROTOCOLS_TO_EXPAND`
+static const int MAX_PROTOCOLS_TO_EXPAND = (1<<16);
+
+/** Voting helper: Given a list of proto_entry_t, return a newly allocated
+ * smartlist of newly allocated strings, one for each included protocol
+ * version. (So 'Foo=3,5-7' expands to a list of 'Foo=3', 'Foo=5', 'Foo=6',
+ * 'Foo=7'.)
+ *
+ * Do not list any protocol version more than once.
+ *
+ * Return NULL if the list would be too big.
+ */
+static smartlist_t *
+expand_protocol_list(const smartlist_t *protos)
+{
+  smartlist_t *expanded = smartlist_new();
+  if (!protos)
+    return expanded;
+
+  SMARTLIST_FOREACH_BEGIN(protos, const proto_entry_t *, ent) {
+    const char *name = ent->name;
+    if (strlen(name) > MAX_PROTOCOL_NAME_LENGTH) {
+      log_warn(LD_NET, "When expanding a protocol entry, I got a very large "
+               "protocol name. This is possibly an attack or a bug, unless "
+               "the Tor network truly supports protocol names larger than "
+               "%ud characters. The offending string was: %s",
+               MAX_PROTOCOL_NAME_LENGTH, escaped(name));
+      continue;
+    }
+    SMARTLIST_FOREACH_BEGIN(ent->ranges, const proto_range_t *, range) {
+      uint32_t u;
+      for (u = range->low; u <= range->high; ++u) {
+        smartlist_add_asprintf(expanded, "%s=%lu", name, (unsigned long)u);
+        if (smartlist_len(expanded) > MAX_PROTOCOLS_TO_EXPAND)
+          goto too_many;
+      }
+    } SMARTLIST_FOREACH_END(range);
+  } SMARTLIST_FOREACH_END(ent);
+
+  smartlist_sort_strings(expanded);
+  smartlist_uniq_strings(expanded); // This makes voting work. do not remove
+  return expanded;
+
+ too_many:
+  SMARTLIST_FOREACH(expanded, char *, cp, tor_free(cp));
+  smartlist_free(expanded);
+  return NULL;
+}
+
+/** Voting helper: compare two singleton proto_entry_t items by version
+ * alone. (A singleton item is one with a single range entry where
+ * low==high.) */
+static int
+cmp_single_ent_by_version(const void **a_, const void **b_)
+{
+  const proto_entry_t *ent_a = *a_;
+  const proto_entry_t *ent_b = *b_;
+
+  tor_assert(smartlist_len(ent_a->ranges) == 1);
+  tor_assert(smartlist_len(ent_b->ranges) == 1);
+
+  const proto_range_t *a = smartlist_get(ent_a->ranges, 0);
+  const proto_range_t *b = smartlist_get(ent_b->ranges, 0);
+
+  tor_assert(a->low == a->high);
+  tor_assert(b->low == b->high);
+
+  if (a->low < b->low) {
+    return -1;
+  } else if (a->low == b->low) {
+    return 0;
+  } else {
+    return 1;
+  }
+}
+
+/** Voting helper: Given a list of singleton protocol strings (of the form
+ * Foo=7), return a canonical listing of all the protocol versions listed,
+ * with as few ranges as possible, with protocol versions sorted lexically and
+ * versions sorted in numerically increasing order, using as few range entries
+ * as possible.
+ **/
+static char *
+contract_protocol_list(const smartlist_t *proto_strings)
+{
+  if (smartlist_len(proto_strings) == 0) {
+    return tor_strdup("");
+  }
+
+  // map from name to list of single-version entries
+  strmap_t *entry_lists_by_name = strmap_new();
+  // list of protocol names
+  smartlist_t *all_names = smartlist_new();
+  // list of strings for the output we're building
+  smartlist_t *chunks = smartlist_new();
+
+  // Parse each item and stick it entry_lists_by_name. Build
+  // 'all_names' at the same time.
+  SMARTLIST_FOREACH_BEGIN(proto_strings, const char *, s) {
+    if (BUG(!s))
+      continue;// LCOV_EXCL_LINE
+    proto_entry_t *ent = parse_single_entry(s, s+strlen(s));
+    if (BUG(!ent))
+      continue; // LCOV_EXCL_LINE
+    smartlist_t *lst = strmap_get(entry_lists_by_name, ent->name);
+    if (!lst) {
+      smartlist_add(all_names, ent->name);
+      lst = smartlist_new();
+      strmap_set(entry_lists_by_name, ent->name, lst);
+    }
+    smartlist_add(lst, ent);
+  } SMARTLIST_FOREACH_END(s);
+
+  // We want to output the protocols sorted by their name.
+  smartlist_sort_strings(all_names);
+
+  SMARTLIST_FOREACH_BEGIN(all_names, const char *, name) {
+    const int first_entry = (name_sl_idx == 0);
+    smartlist_t *lst = strmap_get(entry_lists_by_name, name);
+    tor_assert(lst);
+    // Sort every entry with this name by version. They are
+    // singletons, so there can't be overlap.
+    smartlist_sort(lst, cmp_single_ent_by_version);
+
+    if (! first_entry)
+      smartlist_add_strdup(chunks, " ");
+
+    /* We're going to construct this entry from the ranges. */
+    proto_entry_t *entry = tor_malloc_zero(sizeof(proto_entry_t));
+    entry->ranges = smartlist_new();
+    entry->name = tor_strdup(name);
+
+    // Now, find all the ranges of versions start..end where
+    // all of start, start+1, start+2, ..end are included.
+    int start_of_cur_series = 0;
+    while (start_of_cur_series < smartlist_len(lst)) {
+      const proto_entry_t *ent = smartlist_get(lst, start_of_cur_series);
+      const proto_range_t *range = smartlist_get(ent->ranges, 0);
+      const uint32_t ver_low = range->low;
+      uint32_t ver_high = ver_low;
+
+      int idx;
+      for (idx = start_of_cur_series+1; idx < smartlist_len(lst); ++idx) {
+        ent = smartlist_get(lst, idx);
+        range = smartlist_get(ent->ranges, 0);
+        if (range->low != ver_high + 1)
+          break;
+        ver_high += 1;
+      }
+
+      // Now idx is either off the end of the list, or the first sequence
+      // break in the list.
+      start_of_cur_series = idx;
+
+      proto_range_t *new_range = tor_malloc_zero(sizeof(proto_range_t));
+      new_range->low = ver_low;
+      new_range->high = ver_high;
+      smartlist_add(entry->ranges, new_range);
+    }
+    proto_entry_encode_into(chunks, entry);
+    proto_entry_free(entry);
+
+  } SMARTLIST_FOREACH_END(name);
+
+  // Build the result...
+  char *result = smartlist_join_strings(chunks, "", 0, NULL);
+
+  // And free all the stuff we allocated.
+  SMARTLIST_FOREACH_BEGIN(all_names, const char *, name) {
+    smartlist_t *lst = strmap_get(entry_lists_by_name, name);
+    tor_assert(lst);
+    SMARTLIST_FOREACH(lst, proto_entry_t *, e, proto_entry_free(e));
+    smartlist_free(lst);
+  } SMARTLIST_FOREACH_END(name);
+
+  strmap_free(entry_lists_by_name, NULL);
+  smartlist_free(all_names);
+  SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
+  smartlist_free(chunks);
+
+  return result;
+}
+
+/**
+ * Protocol voting implementation.
+ *
+ * Given a list of strings describing protocol versions, return a newly
+ * allocated string encoding all of the protocols that are listed by at
+ * least <b>threshold</b> of the inputs.
+ *
+ * The string is minimal and sorted according to the rules of
+ * contract_protocol_list above.
+ */
+char *
+protover_compute_vote(const smartlist_t *list_of_proto_strings,
+                      int threshold)
+{
+  if (smartlist_len(list_of_proto_strings) == 0) {
+    return tor_strdup("");
+  }
+
+  smartlist_t *all_entries = smartlist_new();
+
+  // First, parse the inputs and break them into singleton entries.
+  SMARTLIST_FOREACH_BEGIN(list_of_proto_strings, const char *, vote) {
+    smartlist_t *unexpanded = parse_protocol_list(vote);
+    if (! unexpanded) {
+      log_warn(LD_NET, "I failed with parsing a protocol list from "
+               "an authority. The offending string was: %s",
+               escaped(vote));
+      continue;
+    }
+    smartlist_t *this_vote = expand_protocol_list(unexpanded);
+    if (this_vote == NULL) {
+      log_warn(LD_NET, "When expanding a protocol list from an authority, I "
+               "got too many protocols. This is possibly an attack or a bug, "
+               "unless the Tor network truly has expanded to support over %d "
+               "different subprotocol versions. The offending string was: %s",
+               MAX_PROTOCOLS_TO_EXPAND, escaped(vote));
+    } else {
+      smartlist_add_all(all_entries, this_vote);
+      smartlist_free(this_vote);
+    }
+    SMARTLIST_FOREACH(unexpanded, proto_entry_t *, e, proto_entry_free(e));
+    smartlist_free(unexpanded);
+  } SMARTLIST_FOREACH_END(vote);
+
+  if (smartlist_len(all_entries) == 0) {
+    smartlist_free(all_entries);
+    return tor_strdup("");
+  }
+
+  // Now sort the singleton entries
+  smartlist_sort_strings(all_entries);
+
+  // Now find all the strings that appear at least 'threshold' times.
+  smartlist_t *include_entries = smartlist_new();
+  const char *cur_entry = smartlist_get(all_entries, 0);
+  int n_times = 0;
+  SMARTLIST_FOREACH_BEGIN(all_entries, const char *, ent) {
+    if (!strcmp(ent, cur_entry)) {
+      n_times++;
+    } else {
+      if (n_times >= threshold && cur_entry)
+        smartlist_add(include_entries, (void*)cur_entry);
+      cur_entry = ent;
+      n_times = 1 ;
+    }
+  } SMARTLIST_FOREACH_END(ent);
+
+  if (n_times >= threshold && cur_entry)
+    smartlist_add(include_entries, (void*)cur_entry);
+
+  // Finally, compress that list.
+  char *result = contract_protocol_list(include_entries);
+  smartlist_free(include_entries);
+  SMARTLIST_FOREACH(all_entries, char *, cp, tor_free(cp));
+  smartlist_free(all_entries);
+
+  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_some;
+  smartlist_t *missing_completely;
+  smartlist_t *missing_all;
+
+  if (!s) {
+    return 1;
+  }
+
+  smartlist_t *entries = parse_protocol_list(s);
+  if (BUG(entries == NULL)) {
+    log_warn(LD_NET, "Received an unparseable protocol list %s"
+             " from the consensus", escaped(s));
+    return 1;
+  }
+
+  missing_some = smartlist_new();
+  missing_completely = 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) {
+      proto_entry_t *unsupported = tor_malloc_zero(sizeof(proto_entry_t));
+      proto_range_t *versions = tor_malloc_zero(sizeof(proto_range_t));
+      uint32_t i;
+
+      unsupported->name = tor_strdup(ent->name);
+      unsupported->ranges = smartlist_new();
+
+      for (i = range->low; i <= range->high; ++i) {
+        if (!protover_is_supported_here(tp, i)) {
+          if (versions->low == 0 && versions->high == 0) {
+            versions->low = i;
+            /* Pre-emptively add the high now, just in case we're in a single
+             * version range (e.g. "Link=999"). */
+            versions->high = i;
+          }
+          /* If the last one to be unsupported is one less than the current
+           * one, we're in a continuous range, so set the high field. */
+          if ((versions->high && versions->high == i - 1) ||
+              /* Similarly, if the last high wasn't set and we're currently
+               * one higher than the low, add current index as the highest
+               * known high. */
+              (!versions->high && versions->low == i - 1)) {
+            versions->high = i;
+            continue;
+          }
+        } else {
+          /* If we hit a supported version, and we previously had a range,
+           * we've hit a non-continuity. Copy the previous range and add it to
+           * the unsupported->ranges list and zero-out the previous range for
+           * the next iteration. */
+          if (versions->low != 0 && versions->high != 0) {
+            proto_range_t *versions_to_add = tor_malloc(sizeof(proto_range_t));
+
+            versions_to_add->low = versions->low;
+            versions_to_add->high = versions->high;
+            smartlist_add(unsupported->ranges, versions_to_add);
+
+            versions->low = 0;
+            versions->high = 0;
+          }
+        }
+      }
+      /* Once we've run out of versions to check, see if we had any unsupported
+       * ones and, if so, add them to unsupported->ranges. */
+      if (versions->low != 0 && versions->high != 0) {
+        smartlist_add(unsupported->ranges, versions);
+      }
+      /* Finally, if we had something unsupported, add it to the list of
+       * missing_some things and mark that there was something missing. */
+      if (smartlist_len(unsupported->ranges) != 0) {
+        smartlist_add(missing_some, (void*) unsupported);
+        all_supported = 0;
+      } else {
+        proto_entry_free(unsupported);
+        tor_free(versions);
+      }
+    } SMARTLIST_FOREACH_END(range);
+
+    continue;
+
+  unsupported:
+    all_supported = 0;
+    smartlist_add(missing_completely, (void*) ent);
+  } SMARTLIST_FOREACH_END(ent);
+
+  /* We keep the two smartlists separate so that we can free the proto_entry_t
+   * we created and put in missing_some, so here we add them together to build
+   * the string. */
+  missing_all = smartlist_new();
+  smartlist_add_all(missing_all, missing_some);
+  smartlist_add_all(missing_all, missing_completely);
+
+  if (missing_out && !all_supported) {
+    tor_assert(smartlist_len(missing_all) != 0);
+    *missing_out = encode_protocol_list(missing_all);
+  }
+  SMARTLIST_FOREACH(missing_some, proto_entry_t *, ent, proto_entry_free(ent));
+  smartlist_free(missing_some);
+  smartlist_free(missing_completely);
+  smartlist_free(missing_all);
+
+  SMARTLIST_FOREACH(entries, proto_entry_t *, ent, proto_entry_free(ent));
+  smartlist_free(entries);
+
+  return all_supported;
+}
+
+/** Helper: Given a list of proto_entry_t, return true iff
+ * <b>pr</b>=<b>ver</b> is included in that list. */
+static int
+protocol_list_contains(const smartlist_t *protos,
+                       protocol_type_t pr, uint32_t ver)
+{
+  if (BUG(protos == NULL)) {
+    return 0; // LCOV_EXCL_LINE
+  }
+  const char *pr_name = protocol_type_to_str(pr);
+  if (BUG(pr_name == NULL)) {
+    return 0; // LCOV_EXCL_LINE
+  }
+
+  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;
+}
+
+/** Return a string describing the protocols supported by tor version
+ * <b>version</b>, or an empty string if we cannot tell.
+ *
+ * Note that this is only used to infer protocols for Tor versions that
+ * can't declare their own.
+ **/
+/// C_RUST_COUPLED: src/rust/protover/protover.rs `compute_for_old_tor`
+const char *
+protover_compute_for_old_tor(const char *version)
+{
+  if (version == NULL) {
+    /* No known version; guess the oldest series that is still supported. */
+    version = "0.2.5.15";
+  }
+
+  if (tor_version_as_new_as(version,
+                            FIRST_TOR_VERSION_TO_ADVERTISE_PROTOCOLS)) {
+    return "";
+  } else if (tor_version_as_new_as(version, "0.2.9.1-alpha")) {
+    /* 0.2.9.1-alpha HSRend=2 */
+    return "Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1-2 "
+      "Link=1-4 LinkAuth=1 "
+      "Microdesc=1-2 Relay=1-2";
+  } else if (tor_version_as_new_as(version, "0.2.7.5")) {
+    /* 0.2.7-stable added Desc=2, Microdesc=2, Cons=2, which indicate
+     * ed25519 support.  We'll call them present only in "stable" 027,
+     * though. */
+    return "Cons=1-2 Desc=1-2 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
+      "Link=1-4 LinkAuth=1 "
+      "Microdesc=1-2 Relay=1-2";
+  } else if (tor_version_as_new_as(version, "0.2.4.19")) {
+    /* No currently supported Tor server versions are older than this, or
+     * lack these protocols. */
+    return "Cons=1 Desc=1 DirCache=1 HSDir=1 HSIntro=3 HSRend=1 "
+      "Link=1-4 LinkAuth=1 "
+      "Microdesc=1 Relay=1-2";
+  } else {
+    /* Cannot infer protocols. */
+    return "";
+  }
+}
+
+/**
+ * Release all storage held by static fields in protover.c
+ */
+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;
+  }
+}
+
+#endif /* !defined(HAVE_RUST) */
+
diff --git a/src/core/proto/protover.h b/src/core/proto/protover.h
new file mode 100644
index 0000000000..7319d2f8c4
--- /dev/null
+++ b/src/core/proto/protover.h
@@ -0,0 +1,97 @@
+/* Copyright (c) 2016-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file protover.h
+ * \brief Headers and type declarations for protover.c
+ **/
+
+#ifndef TOR_PROTOVER_H
+#define TOR_PROTOVER_H
+
+#include <stdbool.h>
+#include "lib/cc/torint.h"
+#include "lib/testsupport/testsupport.h"
+struct smartlist_t;
+
+/** The first version of Tor that included "proto" entries in its
+ * descriptors.  Authorities should use this to decide whether to
+ * guess proto lines. */
+/* This is a guess. */
+/// C_RUST_COUPLED: src/rust/protover/protover.rs
+///                 `FIRST_TOR_VERSION_TO_ADVERTISE_PROTOCOLS`
+#define FIRST_TOR_VERSION_TO_ADVERTISE_PROTOCOLS "0.2.9.3-alpha"
+
+/** The protover version number that signifies HSDir support for HSv3 */
+#define PROTOVER_HSDIR_V3 2
+/** The protover version number that signifies HSv3 intro point support */
+#define PROTOVER_HS_INTRO_V3 4
+/** The protover version number that signifies HSv3 rendezvous point support */
+#define PROTOVER_HS_RENDEZVOUS_POINT_V3 2
+
+/** List of recognized subprotocols. */
+/// C_RUST_COUPLED: src/rust/protover/ffi.rs `translate_to_rust`
+/// C_RUST_COUPLED: src/rust/protover/protover.rs `Proto`
+typedef enum protocol_type_t {
+  PRT_LINK,
+  PRT_LINKAUTH,
+  PRT_RELAY,
+  PRT_DIRCACHE,
+  PRT_HSDIR,
+  PRT_HSINTRO,
+  PRT_HSREND,
+  PRT_DESC,
+  PRT_MICRODESC,
+  PRT_CONS,
+} protocol_type_t;
+
+bool protover_contains_long_protocol_names(const char *s);
+int protover_all_supported(const char *s, char **missing);
+int protover_is_supported_here(protocol_type_t pr, uint32_t ver);
+const char *protover_get_supported_protocols(void);
+
+char *protover_compute_vote(const struct smartlist_t *list_of_proto_strings,
+                            int threshold);
+const char *protover_compute_for_old_tor(const char *version);
+int protocol_list_supports_protocol(const char *list, protocol_type_t tp,
+                                    uint32_t version);
+int protocol_list_supports_protocol_or_later(const char *list,
+                                             protocol_type_t tp,
+                                             uint32_t version);
+
+void protover_free_all(void);
+
+#ifdef PROTOVER_PRIVATE
+/** Represents a range of subprotocols of a given type. All subprotocols
+ * between <b>low</b> and <b>high</b> inclusive are included. */
+typedef struct proto_range_t {
+  uint32_t low;
+  uint32_t high;
+} proto_range_t;
+
+/** Represents a set of ranges of subprotocols of a given type. */
+typedef struct proto_entry_t {
+  /** The name of the protocol.
+   *
+   * (This needs to handle voting on protocols which
+   * we don't recognize yet, so it's a char* rather than a protocol_type_t.)
+   */
+  char *name;
+  /** Smartlist of proto_range_t */
+  struct smartlist_t *ranges;
+} proto_entry_t;
+
+#if !defined(HAVE_RUST) && defined(TOR_UNIT_TESTS)
+STATIC struct smartlist_t *parse_protocol_list(const char *s);
+STATIC char *encode_protocol_list(const struct 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);
+STATIC void proto_entry_free_(proto_entry_t *entry);
+#endif /* !defined(HAVE_RUST) && defined(TOR_UNIT_TESTS) */
+
+#define proto_entry_free(entry) \
+  FREE_AND_NULL(proto_entry_t, proto_entry_free_, (entry))
+
+#endif /* defined(PROTOVER_PRIVATE) */
+
+#endif /* !defined(TOR_PROTOVER_H) */
diff --git a/src/core/proto/protover_rust.c b/src/core/proto/protover_rust.c
new file mode 100644
index 0000000000..bd2f88b98e
--- /dev/null
+++ b/src/core/proto/protover_rust.c
@@ -0,0 +1,34 @@
+/* Copyright (c) 2016-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/*
+ * \file protover_rust.c
+ * \brief Provide a C wrapper for functions exposed in /src/rust/protover,
+ * and safe translation/handling between the Rust/C boundary.
+ */
+
+#include "or/or.h"
+#include "or/protover.h"
+
+#ifdef HAVE_RUST
+
+/* Define for compatibility, used in main.c */
+void
+protover_free_all(void)
+{
+}
+
+int protover_contains_long_protocol_names_(const char *s);
+
+/**
+ * Return true if the unparsed protover in <b>s</b> would contain a protocol
+ * name longer than MAX_PROTOCOL_NAME_LENGTH, and false otherwise.
+ */
+bool
+protover_contains_long_protocol_names(const char *s)
+{
+  return protover_contains_long_protocol_names_(s) != 0;
+}
+
+#endif /* defined(HAVE_RUST) */
+