Code to make clients fetch and use microdescriptors for circuit building

To turn this on, set UseMicrodescriptors to "1" (or "auto" if you
want it on-if-you're-a-client).  It should go auto-by-default once
0.2.3.1-alpha is released.

Because of our node logic, directory caches will never use
microdescriptors when they have the right routerinfo available.

12 files changed, 127 insertions, 47 deletions

diff --git a/changes/microdesc_use b/changes/microdesc_use
new file mode 100644
index 0000000000..89faf7c5fb
--- /dev/null
+++ b/changes/microdesc_use
@@ -0,0 +1,10 @@
+  o Major features
+    - Clients can now use microdescriptors instead of regular descriptors
+      to build circuits.  Microdescriptors are authority-generated and
+      -authenticated summaries of regular descriptors' contents, designed
+      to change very rarely.  This feature is designed to save bandwidth,
+      especially for clients on slow internet connections.  It's off
+      by default for now, since nearly no caches support it, but it will
+      be on-by-default for clients in a future version.  You can use the
+      UseMicrodescriptors option to turn it on.
+
diff --git a/src/or/config.c b/src/or/config.c
index c93699134c..09ad51f00c 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -381,6 +381,7 @@ static config_var_t _option_vars[] = {
   V(UpdateBridgesFromAuthority,  BOOL,     "0"),
   V(UseBridges,                  BOOL,     "0"),
   V(UseEntryGuards,              BOOL,     "1"),
+  V(UseMicrodescriptors,         AUTOBOOL, "0"),
   V(User,                        STRING,   NULL),
   VAR("V1AuthoritativeDirectory",BOOL, V1AuthoritativeDir,   "0"),
   VAR("V2AuthoritativeDirectory",BOOL, V2AuthoritativeDir,   "0"),
@@ -919,7 +920,8 @@ consider_adding_dir_authorities(or_options_t *options,
     if (!options->AlternateBridgeAuthority)
       type |= BRIDGE_DIRINFO;
     if (!options->AlternateDirAuthority)
-      type |= V1_DIRINFO | V2_DIRINFO | V3_DIRINFO;
+      type |= V1_DIRINFO | V2_DIRINFO | V3_DIRINFO | EXTRAINFO_DIRINFO |
+        MICRODESC_DIRINFO;
     if (!options->AlternateHSAuthority)
       type |= HIDSERV_DIRINFO;
     add_default_trusted_dir_authorities(type);
@@ -4605,7 +4607,7 @@ parse_dir_server_line(const char *line, dirinfo_type_t required_type,
         log_warn(LD_CONFIG, "Bad v3 identity digest '%s' on DirServer line",
                  flag);
       } else {
-        type |= V3_DIRINFO;
+        type |= V3_DIRINFO|EXTRAINFO_DIRINFO|MICRODESC_DIRINFO;
       }
     } else {
       log_warn(LD_CONFIG, "Unrecognized flag '%s' on DirServer line",
diff --git a/src/or/directory.c b/src/or/directory.c
index f21dc85c05..184a6b4a90 100644
--- a/src/or/directory.c
+++ b/src/or/directory.c
@@ -147,9 +147,10 @@ purpose_needs_anonymity(uint8_t dir_purpose, uint8_t router_purpose)
   return 1;
 }
 
-/** Return a newly allocated string describing <b>auth</b>. */
-char *
-dirinfo_type_to_string(dirinfo_type_t auth)
+/** Return a newly allocated string describing <b>auth</b>. Only describes
+ * authority features. */
+static char *
+authdir_type_to_string(dirinfo_type_t auth)
 {
   char *result;
   smartlist_t *lst = smartlist_create();
@@ -328,7 +329,7 @@ directory_post_to_dirservers(uint8_t dir_purpose, uint8_t router_purpose,
                                               NULL, payload, upload_len, 0);
   } SMARTLIST_FOREACH_END(ds);
   if (!found) {
-    char *s = dirinfo_type_to_string(type);
+    char *s = authdir_type_to_string(type);
     log_warn(LD_DIR, "Publishing server descriptor to directory authorities "
              "of type '%s', but no authorities of that type listed!", s);
     tor_free(s);
@@ -379,7 +380,7 @@ directory_get_from_dirserver(uint8_t dir_purpose, uint8_t router_purpose,
       type = V3_DIRINFO;
       break;
     case DIR_PURPOSE_FETCH_MICRODESC:
-      type = V3_DIRINFO;
+      type = MICRODESC_DIRINFO;
       break;
     default:
       log_warn(LD_BUG, "Unexpected purpose %d", (int)dir_purpose);
diff --git a/src/or/directory.h b/src/or/directory.h
index 9f4c31d9f7..caff938e5c 100644
--- a/src/or/directory.h
+++ b/src/or/directory.h
@@ -13,7 +13,6 @@
 #define _TOR_DIRECTORY_H
 
 int directories_have_accepted_server_descriptor(void);
-char *dirinfo_type_to_string(dirinfo_type_t auth);
 void directory_post_to_dirservers(uint8_t dir_purpose, uint8_t router_purpose,
                                   dirinfo_type_t type, const char *payload,
                                   size_t payload_len, size_t extrainfo_len);
diff --git a/src/or/microdesc.c b/src/or/microdesc.c
index 6209bbf33e..0e8aa836f1 100644
--- a/src/or/microdesc.c
+++ b/src/or/microdesc.c
@@ -9,6 +9,7 @@
 #include "networkstatus.h"
 #include "nodelist.h"
 #include "policies.h"
+#include "router.h"
 #include "routerlist.h"
 #include "routerparse.h"
 
@@ -251,6 +252,9 @@ microdescs_add_list_to_cache(microdesc_cache_t *cache,
       SMARTLIST_FOREACH(added, microdesc_t *, md, nodelist_add_microdesc(md));
   }
 
+  if (smartlist_len(added))
+    router_dir_info_changed();
+
   return added;
 }
 
@@ -570,6 +574,8 @@ microdesc_list_missing_digest256(networkstatus_t *ns, microdesc_cache_t *cache,
       continue;
     if (skip && digestmap_get(skip, rs->descriptor_digest))
       continue;
+    if (tor_mem_is_zero(rs->descriptor_digest, DIGEST256_LEN))
+      continue; /* This indicates a bug somewhere XXXX023*/
     /* XXXX Also skip if we're a noncache and wouldn't use this router.
      * XXXX NM Microdesc
      */
@@ -602,11 +608,8 @@ update_microdesc_downloads(time_t now)
   if (!consensus)
     return;
 
-  if (!directory_caches_dir_info(options)) {
-    /* Right now, only caches fetch microdescriptors.
-     * XXXX NM Microdescs */
+  if (!we_fetch_microdescriptors(options))
     return;
-  }
 
   pending = digestmap_new();
   list_pending_microdesc_downloads(pending);
@@ -647,3 +650,45 @@ update_microdescs_from_networkstatus(time_t now)
   } SMARTLIST_FOREACH_END(rs);
 }
 
+/** Return true iff we should prefer to use microdescriptors rather than
+ * routerdescs for building circuits. */
+int
+we_use_microdescriptors_for_circuits(or_options_t *options)
+{
+  int ret = options->UseMicrodescriptors;
+  if (ret == -1) {
+    /* UseMicrodescriptors is "auto"; we need to decide: */
+    /* So we decide that we'll use microdescriptors iff we are not a server */
+    ret = ! server_mode(options);
+  }
+  return ret;
+}
+
+/** Return true iff we should try to download microdescriptors at all. */
+int
+we_fetch_microdescriptors(or_options_t *options)
+{
+  if (directory_caches_dir_info(options))
+    return 1;
+  return we_use_microdescriptors_for_circuits(options);
+}
+
+/** Return true iff we should try to download router descriptors at all. */
+int
+we_fetch_router_descriptors(or_options_t *options)
+{
+  if (directory_caches_dir_info(options))
+    return 1;
+  return ! we_use_microdescriptors_for_circuits(options);
+}
+
+/** Return the consensus flavor we actually want to use to build circuits. */
+int
+usable_consensus_flavor(void)
+{
+  if (we_use_microdescriptors_for_circuits(get_options())) {
+    return FLAV_MICRODESC;
+  } else {
+    return FLAV_NS;
+  }
+}
diff --git a/src/or/microdesc.h b/src/or/microdesc.h
index c967742aa3..94b1ff6f85 100644
--- a/src/or/microdesc.h
+++ b/src/or/microdesc.h
@@ -43,5 +43,10 @@ void microdesc_free_all(void);
 void update_microdesc_downloads(time_t now);
 void update_microdescs_from_networkstatus(time_t now);
 
+int usable_consensus_flavor(void);
+int we_fetch_microdescriptors(or_options_t *options);
+int we_fetch_router_descriptors(or_options_t *options);
+int we_use_microdescriptors_for_circuits(or_options_t *options);
+
 #endif
 
diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c
index b191f57c84..663d1ad919 100644
--- a/src/or/networkstatus.c
+++ b/src/or/networkstatus.c
@@ -50,7 +50,9 @@ static strmap_t *unnamed_server_map = NULL;
  * of whichever type we are using for our own circuits.  This will be the same
  * as one of current_ns_consensus or current_md_consensus.
  */
-#define current_consensus current_ns_consensus
+#define current_consensus                                       \
+  (we_use_microdescriptors_for_circuits(get_options()) ?        \
+   current_md_consensus : current_ns_consensus)
 
 /** Most recently received and validated v3 "ns"-flavored consensus network
  * status. */
@@ -1187,7 +1189,7 @@ we_want_to_fetch_flavor(or_options_t *options, int flavor)
   }
   /* Otherwise, we want the flavor only if we want to use it to build
    * circuits. */
-  return (flavor == USABLE_CONSENSUS_FLAVOR);
+  return flavor == usable_consensus_flavor();
 }
 
 /** How many times will we try to fetch a consensus before we give up? */
@@ -1392,7 +1394,7 @@ update_certificate_downloads(time_t now)
 int
 consensus_is_waiting_for_certs(void)
 {
-  return consensus_waiting_for_certs[USABLE_CONSENSUS_FLAVOR].consensus
+  return consensus_waiting_for_certs[usable_consensus_flavor()].consensus
     ? 1 : 0;
 }
 
@@ -1621,7 +1623,7 @@ networkstatus_set_current_consensus(const char *consensus,
     flavor = networkstatus_get_flavor_name(flav);
   }
 
-  if (flav != USABLE_CONSENSUS_FLAVOR &&
+  if (flav != usable_consensus_flavor() &&
       !directory_caches_dir_info(options)) {
     /* This consensus is totally boring to us: we won't use it, and we won't
      * serve it.  Drop it. */
@@ -1726,14 +1728,14 @@ networkstatus_set_current_consensus(const char *consensus,
     }
   }
 
-  if (!from_cache && flav == USABLE_CONSENSUS_FLAVOR)
+  if (!from_cache && flav == usable_consensus_flavor())
     control_event_client_status(LOG_NOTICE, "CONSENSUS_ARRIVED");
 
   /* Are we missing any certificates at all? */
   if (r != 1 && dl_certs)
     authority_certs_fetch_missing(c, now);
 
-  if (flav == USABLE_CONSENSUS_FLAVOR) {
+  if (flav == usable_consensus_flavor()) {
     notify_control_networkstatus_changed(current_consensus, c);
   }
   if (flav == FLAV_NS) {
@@ -1780,8 +1782,8 @@ networkstatus_set_current_consensus(const char *consensus,
       download_status_failed(&consensus_dl_status[flav], 0);
   }
 
-  if (flav == USABLE_CONSENSUS_FLAVOR) {
-    /* XXXXNM Microdescs: needs a non-ns variant. */
+  if (flav == usable_consensus_flavor()) {
+    /* XXXXNM Microdescs: needs a non-ns variant. ???? NM*/
     update_consensus_networkstatus_fetch_time(now);
 
     nodelist_set_consensus(current_consensus);
diff --git a/src/or/or.h b/src/or/or.h
index a976916baf..f45ccb7bcd 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1641,6 +1641,9 @@ typedef struct routerstatus_t {
   /** True iff this router is a version that, if it caches directory info,
    * we can get v3 downloads from. */
   unsigned int version_supports_v3_dir:1;
+  /** True iff this router is a version that, if it caches directory info,
+   * we can get microdescriptors from. */
+  unsigned int version_supports_microdesc_cache:1;
 
   unsigned int has_bandwidth:1; /**< The vote/consensus had bw info */
   unsigned int has_exitsummary:1; /**< The vote/consensus had exit summaries */
@@ -1918,9 +1921,6 @@ typedef enum {
   FLAV_MICRODESC = 1,
 } consensus_flavor_t;
 
-/** Which consensus flavor do we actually want to use to build circuits? */
-#define USABLE_CONSENSUS_FLAVOR FLAV_NS
-
 /** How many different consensus flavors are there? */
 #define N_CONSENSUS_FLAVORS ((int)(FLAV_MICRODESC)+1)
 
@@ -2092,6 +2092,12 @@ typedef struct authority_cert_t {
 
 /** Bitfield enum type listing types of information that directory authorities
  * can be authoritative about, and that directory caches may or may not cache.
+ *
+ * Note that the granularity here is based on authority granularity and on
+ * cache capabilities.  Thus, one particular bit may correspond in practice to
+ * a few types of directory info, so long as every authority that pronounces
+ * officially about one of the types prounounces officially about all of them,
+ * and so long as every cache that caches one of them caches all of them.
  */
 typedef enum {
   NO_DIRINFO      = 0,
@@ -2107,7 +2113,9 @@ typedef enum {
   /** Serves bridge descriptors. */
   BRIDGE_DIRINFO  = 1 << 4,
   /** Serves extrainfo documents. */
-  EXTRAINFO_DIRINFO   = 1 << 5,
+  EXTRAINFO_DIRINFO=1 << 5,
+  /** Serves microdescriptors. */
+  MICRODESC_DIRINFO=1 << 6,
 } dirinfo_type_t;
 
 #define CRYPT_PATH_MAGIC 0x70127012u
@@ -2642,7 +2650,7 @@ typedef struct {
   /** To what authority types do we publish our descriptor? Choices are
    * "v1", "v2", "v3", "bridge", or "". */
   smartlist_t *PublishServerDescriptor;
-  /** An authority type, derived from PublishServerDescriptor. */
+  /** A bitfield of authority types, derived from PublishServerDescriptor. */
   dirinfo_type_t _PublishServerDescriptor;
   /** Boolean: do we publish hidden service descriptors to the HS auths? */
   int PublishHidServDescriptors;
@@ -3043,6 +3051,10 @@ typedef struct {
    * the defaults have changed. */
   int _UsingTestNetworkDefaults;
 
+  /** If 1, we try to use microdescriptors to build circuits.  If 0, we don't.
+   * If -1, Tor decides. */
+  int UseMicrodescriptors;
+
 } or_options_t;
 
 /** Persistent state for an onion router, as saved to disk. */
diff --git a/src/or/router.c b/src/or/router.c
index e4dab0ead9..6de069f03f 100644
--- a/src/or/router.c
+++ b/src/or/router.c
@@ -699,7 +699,8 @@ init_keys(void)
   crypto_pk_get_digest(get_server_identity_key(), digest);
   type = ((options->V1AuthoritativeDir ? V1_DIRINFO : NO_DIRINFO) |
           (options->V2AuthoritativeDir ? V2_DIRINFO : NO_DIRINFO) |
-          (options->V3AuthoritativeDir ? V3_DIRINFO : NO_DIRINFO) |
+          (options->V3AuthoritativeDir ?
+               (V3_DIRINFO|MICRODESC_DIRINFO|EXTRAINFO_DIRINFO) : NO_DIRINFO) |
           (options->BridgeAuthoritativeDir ? BRIDGE_DIRINFO : NO_DIRINFO) |
           (options->HSAuthoritativeDir ? HIDSERV_DIRINFO : NO_DIRINFO));
 
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 8bcfa05880..6f90a8baf3 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -1127,6 +1127,9 @@ router_pick_directory_server_impl(dirinfo_type_t type, int flags)
     if ((type & EXTRAINFO_DIRINFO) &&
         !router_supports_extrainfo(node->identity, 0))
       continue;
+    if ((type & MICRODESC_DIRINFO) && !is_trusted &&
+        !node->rs->version_supports_microdesc_cache)
+      continue;
     if (try_excluding && options->ExcludeNodes &&
         routerset_contains_routerstatus(options->ExcludeNodes, status,
                                         country)) {
@@ -2443,18 +2446,6 @@ router_get_by_nickname(const char *nickname, int warn_if_unnamed)
 #endif
 }
 
-/** Try to find a routerinfo for <b>digest</b>. If we don't have one,
- * return 1. If we do, ask tor_version_as_new_as() for the answer.
- */
-int
-router_digest_version_as_new_as(const char *digest, const char *cutoff)
-{
-  const routerinfo_t *router = router_get_by_id_digest(digest);
-  if (!router)
-    return 1;
-  return tor_version_as_new_as(router->platform, cutoff);
-}
-
 /** Return true iff <b>digest</b> is the digest of the identity key of a
  * trusted directory matching at least one bit of <b>type</b>.  If <b>type</b>
  * is zero, any authority is okay. */
@@ -4726,6 +4717,8 @@ update_router_descriptor_downloads(time_t now)
   static time_t last_dummy_download = 0;
   if (should_delay_dir_fetches(options))
     return;
+  if (!we_fetch_router_descriptors(options))
+    return;
   if (directory_fetches_dir_info_early(options)) {
     update_router_descriptor_cache_downloads_v2(now);
   }
@@ -4879,20 +4872,28 @@ count_usable_descriptors(int *num_present, int *num_usable,
                          or_options_t *options, time_t now,
                          routerset_t *in_set)
 {
+  const int md = (consensus->flavor == FLAV_MICRODESC);
   *num_present = 0, *num_usable=0;
 
-  SMARTLIST_FOREACH(consensus->routerstatus_list, routerstatus_t *, rs,
-     {
+  SMARTLIST_FOREACH_BEGIN(consensus->routerstatus_list, routerstatus_t *, rs)
+    {
        if (in_set && ! routerset_contains_routerstatus(in_set, rs, -1))
          continue;
        if (client_would_use_router(rs, now, options)) {
+         const char * const digest = rs->descriptor_digest;
+         int present;
          ++*num_usable; /* the consensus says we want it. */
-         if (router_get_by_descriptor_digest(rs->descriptor_digest)) {
+         if (md)
+           present = NULL != (microdesc_cache_lookup_by_digest256(NULL, digest));
+         else
+           present = NULL != router_get_by_descriptor_digest(digest);
+         if (present) {
            /* we have the descriptor listed in the consensus. */
            ++*num_present;
          }
        }
-     });
+     }
+  SMARTLIST_FOREACH_END(rs);
 
   log_debug(LD_DIR, "%d usable, %d present.", *num_usable, *num_present);
 }
@@ -4906,7 +4907,7 @@ count_loading_descriptors_progress(void)
   int num_present = 0, num_usable=0;
   time_t now = time(NULL);
   const networkstatus_t *consensus =
-    networkstatus_get_reasonably_live_consensus(now, FLAV_NS);
+    networkstatus_get_reasonably_live_consensus(now, usable_consensus_flavor());
   double fraction;
 
   if (!consensus)
@@ -4936,14 +4937,14 @@ update_router_have_minimum_dir_info(void)
   int res;
   or_options_t *options = get_options();
   const networkstatus_t *consensus =
-    networkstatus_get_reasonably_live_consensus(now, FLAV_NS);
+    networkstatus_get_reasonably_live_consensus(now, usable_consensus_flavor());
 
   if (!consensus) {
     if (!networkstatus_get_latest_consensus())
-      strlcpy(dir_info_status, "We have no network-status consensus.",
+      strlcpy(dir_info_status, "We have no usable consensus.",
               sizeof(dir_info_status));
     else
-      strlcpy(dir_info_status, "We have no recent network-status consensus.",
+      strlcpy(dir_info_status, "We have no recent usable consensus.",
               sizeof(dir_info_status));
     res = 0;
     goto done;
diff --git a/src/or/routerlist.h b/src/or/routerlist.h
index 41a4c907ef..940e206365 100644
--- a/src/or/routerlist.h
+++ b/src/or/routerlist.h
@@ -56,7 +56,6 @@ const node_t *router_choose_random_node(smartlist_t *excludedsmartlist,
 
 const routerinfo_t *router_get_by_nickname(const char *nickname,
                                      int warn_if_unnamed);
-int router_digest_version_as_new_as(const char *digest, const char *cutoff);
 int router_digest_is_trusted_dir_type(const char *digest,
                                       dirinfo_type_t type);
 #define router_digest_is_trusted_dir(d) \
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index 80214b3cfb..163cc37240 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -2085,6 +2085,7 @@ routerstatus_parse_entry_from_string(memarea_t *area,
       rs->version_supports_begindir = 1;
       rs->version_supports_extrainfo_upload = 1;
       rs->version_supports_conditional_consensus = 1;
+      rs->version_supports_microdesc_cache = 1;
     } else {
       rs->version_supports_begindir =
         tor_version_as_new_as(tok->args[0], "0.2.0.1-alpha");
@@ -2094,6 +2095,8 @@ routerstatus_parse_entry_from_string(memarea_t *area,
         tor_version_as_new_as(tok->args[0], "0.2.0.8-alpha");
       rs->version_supports_conditional_consensus =
         tor_version_as_new_as(tok->args[0], "0.2.1.1-alpha");
+      rs->version_supports_microdesc_cache =
+        tor_version_as_new_as(tok->args[0], "0.2.3.0-alpha");
     }
     if (vote_rs) {
       vote_rs->version = tor_strdup(tok->args[0]);