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.

1 files changed, 327 insertions, 0 deletions

diff --git a/src/feature/dirauth/dircollate.c b/src/feature/dirauth/dircollate.c
new file mode 100644
index 0000000000..246977dcc8
--- /dev/null
+++ b/src/feature/dirauth/dircollate.c
@@ -0,0 +1,327 @@
+/* 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 */
+
+/**
+ * \file dircollate.c
+ *
+ * \brief Collation code for figuring out which identities to vote for in
+ *   the directory voting process.
+ *
+ * During the consensus calculation, when an authority is looking at the vote
+ * documents from all the authorities, it needs to compute the consensus for
+ * each relay listed by at least one authority.  But the notion of "each
+ * relay" can be tricky: some relays have Ed25519 keys, and others don't.
+ *
+ * Moreover, older consensus methods did RSA-based ID collation alone, and
+ * ignored Ed25519 keys.  We need to support those too until we're completely
+ * sure that authorities will never downgrade.
+ *
+ * This module is invoked exclusively from dirvote.c.
+ */
+
+#define DIRCOLLATE_PRIVATE
+#include "or/dirauth/dircollate.h"
+#include "or/dirauth/dirvote.h"
+
+#include "or/networkstatus_st.h"
+#include "or/vote_routerstatus_st.h"
+
+static void dircollator_collate_by_ed25519(dircollator_t *dc);
+
+/** Hashtable entry mapping a pair of digests (actually an ed25519 key and an
+ * RSA SHA1 digest) to an array of vote_routerstatus_t. */
+typedef struct ddmap_entry_s {
+  HT_ENTRY(ddmap_entry_s) node;
+  /** A SHA1-RSA1024 identity digest and Ed25519 identity key,
+   * concatenated.  (If there is no ed25519 identity key, there is no
+   * entry in this table.) */
+  uint8_t d[DIGEST_LEN + DIGEST256_LEN];
+  /* The nth member of this array corresponds to the vote_routerstatus_t (if
+   * any) received for this digest pair from the nth voter. */
+  vote_routerstatus_t *vrs_lst[FLEXIBLE_ARRAY_MEMBER];
+} ddmap_entry_t;
+
+#define ddmap_entry_free(e) \
+  FREE_AND_NULL(ddmap_entry_t, ddmap_entry_free_, (e))
+
+/** Release all storage held by e. */
+static void
+ddmap_entry_free_(ddmap_entry_t *e)
+{
+  tor_free(e);
+}
+
+/** Return a new empty ddmap_entry, with <b>n_votes</b> elements in
+ * vrs_list. */
+static ddmap_entry_t *
+ddmap_entry_new(int n_votes)
+{
+  return tor_malloc_zero(offsetof(ddmap_entry_t, vrs_lst) +
+                         sizeof(vote_routerstatus_t *) * n_votes);
+}
+
+/** Helper: compute a hash of a single ddmap_entry_t's identity (or
+ * identities) */
+static unsigned
+ddmap_entry_hash(const ddmap_entry_t *ent)
+{
+  return (unsigned) siphash24g(ent->d, sizeof(ent->d));
+}
+
+/** Helper: return true if <b>a</b> and <b>b</b> have the same
+ * identity/identities. */
+static unsigned
+ddmap_entry_eq(const ddmap_entry_t *a, const ddmap_entry_t *b)
+{
+  return fast_memeq(a->d, b->d, sizeof(a->d));
+}
+
+/** Record the RSA identity of <b>ent</b> as <b>rsa_sha1</b>, and the
+ * ed25519 identity as <b>ed25519</b>.  Both must be provided. */
+static void
+ddmap_entry_set_digests(ddmap_entry_t *ent,
+                        const uint8_t *rsa_sha1,
+                        const uint8_t *ed25519)
+{
+  memcpy(ent->d, rsa_sha1, DIGEST_LEN);
+  memcpy(ent->d + DIGEST_LEN, ed25519, DIGEST256_LEN);
+}
+
+HT_PROTOTYPE(double_digest_map, ddmap_entry_s, node, ddmap_entry_hash,
+             ddmap_entry_eq)
+HT_GENERATE2(double_digest_map, ddmap_entry_s, node, ddmap_entry_hash,
+             ddmap_entry_eq, 0.6, tor_reallocarray, tor_free_)
+
+/** Helper: add a single vote_routerstatus_t <b>vrs</b> to the collator
+ * <b>dc</b>, indexing it by its RSA key digest, and by the 2-tuple of its RSA
+ * key digest and Ed25519 key.   It must come from the <b>vote_num</b>th
+ * vote.
+ *
+ * Requires that the vote is well-formed -- that is, that it has no duplicate
+ * routerstatus entries.  We already checked for that when parsing the vote. */
+static void
+dircollator_add_routerstatus(dircollator_t *dc,
+                             int vote_num,
+                             networkstatus_t *vote,
+                             vote_routerstatus_t *vrs)
+{
+  const char *id = vrs->status.identity_digest;
+
+  /* Clear this flag; we might set it later during the voting process */
+  vrs->ed25519_reflects_consensus = 0;
+
+  (void) vote; // We don't currently need this.
+
+  /* First, add this item to the appropriate RSA-SHA-Id array. */
+  vote_routerstatus_t **vrs_lst = digestmap_get(dc->by_rsa_sha1, id);
+  if (NULL == vrs_lst) {
+    vrs_lst = tor_calloc(dc->n_votes, sizeof(vote_routerstatus_t *));
+    digestmap_set(dc->by_rsa_sha1, id, vrs_lst);
+  }
+  tor_assert(vrs_lst[vote_num] == NULL);
+  vrs_lst[vote_num] = vrs;
+
+  const uint8_t *ed = vrs->ed25519_id;
+
+  if (! vrs->has_ed25519_listing)
+    return;
+
+  /* Now add it to the appropriate <Ed,RSA-SHA-Id> array. */
+  ddmap_entry_t search, *found;
+  memset(&search, 0, sizeof(search));
+  ddmap_entry_set_digests(&search, (const uint8_t *)id, ed);
+  found = HT_FIND(double_digest_map, &dc->by_both_ids, &search);
+  if (NULL == found) {
+    found = ddmap_entry_new(dc->n_votes);
+    ddmap_entry_set_digests(found, (const uint8_t *)id, ed);
+    HT_INSERT(double_digest_map, &dc->by_both_ids, found);
+  }
+  vrs_lst = found->vrs_lst;
+  tor_assert(vrs_lst[vote_num] == NULL);
+  vrs_lst[vote_num] = vrs;
+}
+
+/** Create and return a new dircollator object to use when collating
+ * <b>n_votes</b> out of a total of <b>n_authorities</b>. */
+dircollator_t *
+dircollator_new(int n_votes, int n_authorities)
+{
+  dircollator_t *dc = tor_malloc_zero(sizeof(dircollator_t));
+
+  tor_assert(n_votes <= n_authorities);
+
+  dc->n_votes = n_votes;
+  dc->n_authorities = n_authorities;
+
+  dc->by_rsa_sha1 = digestmap_new();
+  HT_INIT(double_digest_map, &dc->by_both_ids);
+
+  return dc;
+}
+
+/** Release all storage held by <b>dc</b>. */
+void
+dircollator_free_(dircollator_t *dc)
+{
+  if (!dc)
+    return;
+
+  if (dc->by_collated_rsa_sha1 != dc->by_rsa_sha1)
+    digestmap_free(dc->by_collated_rsa_sha1, NULL);
+
+  digestmap_free(dc->by_rsa_sha1, tor_free_);
+  smartlist_free(dc->all_rsa_sha1_lst);
+
+  ddmap_entry_t **e, **next, *this;
+  for (e = HT_START(double_digest_map, &dc->by_both_ids);
+       e != NULL; e = next) {
+    this = *e;
+    next = HT_NEXT_RMV(double_digest_map, &dc->by_both_ids, e);
+    ddmap_entry_free(this);
+  }
+  HT_CLEAR(double_digest_map, &dc->by_both_ids);
+
+  tor_free(dc);
+}
+
+/** Add a single vote <b>v</b> to a dircollator <b>dc</b>.  This function must
+ * be called exactly once for each vote to be used in the consensus. It may
+ * only be called before dircollator_collate().
+ */
+void
+dircollator_add_vote(dircollator_t *dc, networkstatus_t *v)
+{
+  tor_assert(v->type == NS_TYPE_VOTE);
+  tor_assert(dc->next_vote_num < dc->n_votes);
+  tor_assert(!dc->is_collated);
+
+  const int votenum = dc->next_vote_num++;
+
+  SMARTLIST_FOREACH_BEGIN(v->routerstatus_list, vote_routerstatus_t *, vrs) {
+    dircollator_add_routerstatus(dc, votenum, v, vrs);
+  } SMARTLIST_FOREACH_END(vrs);
+}
+
+/** Sort the entries in <b>dc</b> according to <b>consensus_method</b>, so
+ * that the consensus process can iterate over them with
+ * dircollator_n_routers() and dircollator_get_votes_for_router(). */
+void
+dircollator_collate(dircollator_t *dc, int consensus_method)
+{
+  (void) consensus_method;
+
+  tor_assert(!dc->is_collated);
+  dc->all_rsa_sha1_lst = smartlist_new();
+
+  dircollator_collate_by_ed25519(dc);
+
+  smartlist_sort_digests(dc->all_rsa_sha1_lst);
+  dc->is_collated = 1;
+}
+
+/**
+ * Collation function for ed25519 consensuses: collate the votes for each
+ * entry in <b>dc</b> by ed25519 key and by RSA key.
+ *
+ * The rule is, approximately:
+ *    If a (ed,rsa) identity is listed by more than half of authorities,
+ *    include it.  And include all (rsa)-only votes about that node as
+ *    matching.
+ *
+ *    Otherwise, if an (*,rsa) or (rsa) identity is listed by more than
+ *    half of the authorities, and no (ed,rsa) pair for the same RSA key
+ *    has been already been included based on the rule above, include
+ *    that RSA identity.
+ */
+static void
+dircollator_collate_by_ed25519(dircollator_t *dc)
+{
+  const int total_authorities = dc->n_authorities;
+  digestmap_t *rsa_digests = digestmap_new();
+
+  ddmap_entry_t **iter;
+
+  /* Go over all <ed,rsa> pairs */
+  HT_FOREACH(iter, double_digest_map, &dc->by_both_ids) {
+    ddmap_entry_t *ent = *iter;
+    int n = 0, i;
+    for (i = 0; i < dc->n_votes; ++i) {
+      if (ent->vrs_lst[i] != NULL)
+        ++n;
+    }
+
+    /* If not enough authorties listed this exact <ed,rsa> pair,
+     * don't include it. */
+    if (n <= total_authorities / 2)
+      continue;
+
+    /* Now consider whether there are any other entries with the same
+     * RSA key (but with possibly different or missing ed value). */
+    vote_routerstatus_t **vrs_lst2 = digestmap_get(dc->by_rsa_sha1,
+                                                   (char*)ent->d);
+    tor_assert(vrs_lst2);
+
+    for (i = 0; i < dc->n_votes; ++i) {
+      if (ent->vrs_lst[i] != NULL) {
+        ent->vrs_lst[i]->ed25519_reflects_consensus = 1;
+      } else if (vrs_lst2[i] && ! vrs_lst2[i]->has_ed25519_listing) {
+        ent->vrs_lst[i] = vrs_lst2[i];
+      }
+    }
+
+    /* Record that we have seen this RSA digest. */
+    digestmap_set(rsa_digests, (char*)ent->d, ent->vrs_lst);
+    smartlist_add(dc->all_rsa_sha1_lst, ent->d);
+  }
+
+  /* Now look over all entries with an RSA digest, looking for RSA digests
+   * we didn't put in yet.
+   */
+  DIGESTMAP_FOREACH(dc->by_rsa_sha1, k, vote_routerstatus_t **, vrs_lst) {
+    if (digestmap_get(rsa_digests, k) != NULL)
+      continue; /* We already included this RSA digest */
+
+    int n = 0, i;
+    for (i = 0; i < dc->n_votes; ++i) {
+      if (vrs_lst[i] != NULL)
+        ++n;
+    }
+
+    if (n <= total_authorities / 2)
+      continue; /* Not enough votes */
+
+    digestmap_set(rsa_digests, k, vrs_lst);
+    smartlist_add(dc->all_rsa_sha1_lst, (char *)k);
+  } DIGESTMAP_FOREACH_END;
+
+  dc->by_collated_rsa_sha1 = rsa_digests;
+}
+
+/** Return the total number of collated router entries.  This function may
+ * only be called after dircollator_collate. */
+int
+dircollator_n_routers(dircollator_t *dc)
+{
+  tor_assert(dc->is_collated);
+  return smartlist_len(dc->all_rsa_sha1_lst);
+}
+
+/** Return an array of vote_routerstatus_t entries for the <b>idx</b>th router
+ * in the collation order.  Each array contains n_votes elements, where the
+ * nth element of the array is the vote_routerstatus_t from the nth voter for
+ * this identity (or NULL if there is no such entry).
+ *
+ * The maximum value for <b>idx</b> is dircollator_n_routers().
+ *
+ * This function may only be called after dircollator_collate. */
+vote_routerstatus_t **
+dircollator_get_votes_for_router(dircollator_t *dc, int idx)
+{
+  tor_assert(dc->is_collated);
+  tor_assert(idx < smartlist_len(dc->all_rsa_sha1_lst));
+  return digestmap_get(dc->by_collated_rsa_sha1,
+                       smartlist_get(dc->all_rsa_sha1_lst, idx));
+}
+