Numerous changes to move towards client-side v2 directories.

connection.c:
- Add some more connection accessor functions to make directory
  download redundancy checking work.

directory.c, or.h, router.c, routerlist.c:
- Start on logic to note when networkstatus downloads fail.

dirserv.c, routerlist.c, routerparse.c:
- Start maintaining an is_named field in routerstatus_t.  Don't
  actually look at it yet.

dirserv.c, routerlist.c:
- Remove expired networkstatus objects.

or.h:
- Make some booleans into bitfields
- Add prototypes

routerlist.c:
- Sort networkstatus list by publication time
- Function to remove old (older than 10 days) networkstatus objects.
- Function to set a list of routerinfo_ts' status info from the
  current set of networkstatus objects.
- Function to tell which routerinfos we need to download based no the
  current set of networkstatus objects.
- Do not launch a networkstatus download if a redundant one is in progress.

routerparse.c:
- Keep router entries in networkstatus sorted by digest.


svn:r5012

7 files changed, 361 insertions, 33 deletions

diff --git a/src/or/connection.c b/src/or/connection.c
index a5a4fb45b5..156bbc0b73 100644
--- a/src/or/connection.c
+++ b/src/or/connection.c
@@ -1479,6 +1479,29 @@ connection_or_exact_get_by_addr_port(uint32_t addr, uint16_t port)
   return best;
 }
 
+/** Return a connection with give type, address, port, and purpose or NULL if
+ * no such connection exists. */
+connection_t *
+connection_get_by_type_addr_port_purpose(int type, uint32_t addr, uint16_t port,
+                                         int purpose)
+{
+  int i, n;
+  connection_t *conn;
+  connection_t **carray;
+
+  get_connection_array(&carray,&n);
+  for (i=0;i<n;i++) {
+    conn = carray[i];
+    if (conn->type == type &&
+        conn->addr == addr &&
+        conn->port == port &&
+        conn->purpose == purpose &&
+        !conn->marked_for_close)
+      return conn;
+  }
+  return NULL;
+}
+
 connection_t *
 connection_get_by_identity_digest(const char *digest, int type)
 {
@@ -1603,6 +1626,26 @@ connection_get_by_type_state_rendquery(int type, int state, const char *rendquer
   return NULL;
 }
 
+/** Return an open, non-marked connection of a given type and purpose, or NULL
+ * if no such connection exists. */
+connection_t *
+connection_get_by_type_purpose(int type, int purpose)
+{
+  int i, n;
+  connection_t *conn;
+  connection_t **carray;
+
+  get_connection_array(&carray,&n);
+  for (i=0;i<n;i++) {
+    conn = carray[i];
+    if (conn->type == type &&
+        !conn->marked_for_close &&
+        (purpose == conn->purpose))
+      return conn;
+  }
+  return NULL;
+}
+
 /** Return 1 if <b>conn</b> is a listener conn, else return 0. */
 int
 connection_is_listener(connection_t *conn)
diff --git a/src/or/directory.c b/src/or/directory.c
index ec0295c8c3..7bcc6f2ed7 100644
--- a/src/or/directory.c
+++ b/src/or/directory.c
@@ -51,6 +51,8 @@ static int body_is_plausible(const char *body, size_t body_len, int purpose);
 static int purpose_is_private(uint8_t purpose);
 static char *http_get_header(const char *headers, const char *which);
 static char *http_get_origin(const char *headers, connection_t *conn);
+static void connection_dir_download_networkstatus_failed(connection_t *conn);
+static void dir_networkstatus_download_failed(smartlist_t *failed);
 
 /********* START VARIABLES **********/
 
@@ -274,9 +276,36 @@ connection_dir_connect_failed(connection_t *conn)
            conn->address);
     directory_get_from_dirserver(conn->purpose, NULL,
                                  0 /* don't retry_if_no_servers */);
+  } else if (conn->purpose == DIR_PURPOSE_FETCH_NETWORKSTATUS) {
+    log_fn(LOG_INFO, "Giving up on directory server at '%s'; retrying",
+           conn->address);
+    connection_dir_download_networkstatus_failed(conn);
   }
 }
 
+/** DOCDOC */
+static void
+connection_dir_download_networkstatus_failed(connection_t *conn)
+{
+    if (!strcmpstart(conn->requested_resource, "all")) {
+      directory_get_from_dirserver(conn->purpose, "all.z",
+                                   0 /* don't retry_if_no_servers */);
+    } else if (!strcmpstart(conn->requested_resource, "fp/")) {
+      smartlist_t *failed = smartlist_create();
+      smartlist_split_string(failed, conn->requested_resource+3, "+", 0, 0);
+      if (smartlist_len(failed)) {
+        char *last = smartlist_get(failed,smartlist_len(failed)-1);
+        size_t last_len = strlen(last);
+        if (!strcmp(last+last_len-2, ".z"))
+          last[last_len-2] = '\0';
+
+        dir_networkstatus_download_failed(failed);
+        SMARTLIST_FOREACH(failed, char *, cp, tor_free(cp));
+      }
+      smartlist_free(failed);
+    }
+}
+
 /** Helper for directory_initiate_command_(router|trusted_dir): send the
  * command to a server whose address is <b>address</b>, whose IP is
  * <b>addr</b>, whose directory port is <b>dir_port</b>, whose tor version is
@@ -896,6 +925,7 @@ connection_dir_client_reached_eof(connection_t *conn)
              status_code, reason, conn->address, conn->port,
              conn->requested_resource);
       tor_free(body); tor_free(headers); tor_free(reason);
+      connection_dir_download_networkstatus_failed(conn);
       return -1;
     }
     if (conn->requested_resource &&
@@ -922,6 +952,9 @@ connection_dir_client_reached_eof(connection_t *conn)
         break;
     }
     if (which) {
+      if (smartlist_len(which)) {
+        dir_networkstatus_download_failed(which);
+      }
       SMARTLIST_FOREACH(which, char *, cp, tor_free(cp));
       smartlist_free(which);
     }
@@ -1451,3 +1484,18 @@ connection_dir_finished_connecting(connection_t *conn)
   return 0;
 }
 
+/** DOCDOC */
+static void
+dir_networkstatus_download_failed(smartlist_t *failed)
+{
+  SMARTLIST_FOREACH(failed, const char *, fp,
+  {
+    char digest[DIGEST_LEN];
+    trusted_dir_server_t *dir;
+    base16_decode(digest, DIGEST_LEN, fp, strlen(fp));
+    dir = router_get_trusteddirserver_by_digest(digest);
+
+    ++dir->n_networkstatus_failures;
+  });
+}
+
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index 92faab7f67..d9bea6eb9a 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -388,11 +388,11 @@ directory_remove_invalid(void)
       changed = 1;
     } else if (r>0 && !ent->is_verified) {
       log(LOG_INFO, "Router '%s' is now approved.", ent->nickname);
-      ent->is_verified = 1;
+      ent->is_verified = ent->is_named = 1;
       changed = 1;
     } else if (r==0 && ent->is_verified) {
       log(LOG_INFO, "Router '%s' is no longer approved.", ent->nickname);
-      ent->is_verified = 0;
+      ent->is_verified = ent->is_named = 0;
       changed = 1;
     }
   }
@@ -752,6 +752,8 @@ dirserv_set_cached_directory(const char *directory, time_t published,
 /** We've just received a v2 network-status for an authoritative directory
  * with fingerprint <b>fp</b> (hex digest, no spaces), published at
  * <b>published</b>.  Store it so we can serve it to others.
+ *
+ * DOCDOC directory==NULL, published==0
  */
 void
 dirserv_set_cached_networkstatus_v2(const char *directory, const char *fp,
@@ -764,12 +766,19 @@ dirserv_set_cached_networkstatus_v2(const char *directory, const char *fp,
   tor_assert(strlen(fp) == HEX_DIGEST_LEN);
 
   if (!(d = strmap_get(cached_v2_networkstatus, fp))) {
+    if (!directory)
+      return;
     d = tor_malloc_zero(sizeof(cached_dir_t));
     strmap_set(cached_v2_networkstatus, fp, d);
   }
 
   tor_assert(d);
-  set_cached_dir(d, tor_strdup(directory), published);
+  if (directory) {
+    set_cached_dir(d, tor_strdup(directory), published);
+  } else {
+    free_cached_dir(d);
+    strmap_remove(cached_v2_networkstatus, fp);
+  }
 }
 
 static cached_dir_t *
diff --git a/src/or/or.h b/src/or/or.h
index 05a0895adc..2669587ecf 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -755,17 +755,22 @@ typedef struct {
   addr_policy_t *exit_policy; /**< What streams will this OR permit
                                       * to exit? */
   long uptime; /**< How many seconds the router claims to have been up */
-  uint8_t is_hibernating; /**< Whether the router claims to be hibernating */
   smartlist_t *declared_family; /**< Nicknames of router which this router
                                  * claims are its family. */
   char *contact_info; /**< Declared contact info for this router. */
+  unsigned int is_hibernating:1; /**< Whether the router claims to be
+                                  * hibernating */
 
   /* local info */
-  int is_running; /**< As far as we know, is this OR currently running? */
+  unsigned int is_running:1; /**< As far as we know, is this OR currently
+                              * running? */
+  unsigned int is_verified:1; /**< Has a trusted dirserver validated this OR?
+                               *  (For Authdir: Have we validated this OR?)
+                               */
+  /*XXXX Make this get used once we think we do naming right. NM */
+  unsigned int is_named:1; /* Do we believe the nickname that this OR gives us? */
+
   time_t status_set_at; /**< When did we last update is_running? */
-  int is_verified; /**< Has a trusted dirserver validated this OR?
-                    * (For Authdir: Have we validated this OR?)
-                    */
 
   /* The below items are used only by authdirservers for
    * reachability testing. */
@@ -1504,6 +1509,9 @@ connection_t *connection_get_by_identity_digest(const char *digest, int type);
 connection_t *connection_get_by_global_id(uint32_t id);
 
 connection_t *connection_get_by_type(int type);
+connection_t *connection_get_by_type_purpose(int type, int purpose);
+connection_t *connection_get_by_type_addr_port_purpose(int type, uint32_t addr,
+                                                     uint16_t port, int purpose);
 connection_t *connection_get_by_type_state(int type, int state);
 connection_t *connection_get_by_type_state_lastwritten(int type, int state);
 connection_t *connection_get_by_type_state_rendquery(int type, int state, const char *rendquery);
@@ -2015,8 +2023,9 @@ typedef struct trusted_dir_server_t {
   uint32_t addr;
   uint16_t dir_port;
   char digest[DIGEST_LEN];
-  int is_running;
-  int supports_v1_protocol;
+  unsigned int is_running:1;
+  unsigned int supports_v1_protocol:1;
+  int n_networkstatus_failures;
 } trusted_dir_server_t;
 
 int router_reload_router_list(void);
@@ -2097,6 +2106,8 @@ void clear_trusted_dir_servers(void);
 networkstatus_t *networkstatus_get_by_digest(const char *digest);
 void update_networkstatus_cache_downloads(time_t now);
 void update_networkstatus_client_downloads(time_t now);
+void routers_update_status_from_networkstatus(smartlist_t *routers);
+smartlist_t *router_list_superseded(void);
 
 /********************************* routerparse.c ************************/
 
diff --git a/src/or/router.c b/src/or/router.c
index d75b6bbcc4..ffb7ffeabd 100644
--- a/src/or/router.c
+++ b/src/or/router.c
@@ -764,10 +764,13 @@ router_rebuild_descriptor(int force)
   config_parse_addr_policy(get_options()->ExitPolicy, &ri->exit_policy, -1);
   options_append_default_exit_policy(&ri->exit_policy);
 
-  if (desc_routerinfo) /* inherit values */
+  if (desc_routerinfo) { /* inherit values */
     ri->is_verified = desc_routerinfo->is_verified;
+    ri->is_running = desc_routerinfo->is_running;
+    ri->is_named = desc_routerinfo->is_named;
+  }
   if (authdir_mode(options))
-    ri->is_verified = 1; /* believe in yourself */
+    ri->is_verified = ri->is_named = 1; /* believe in yourself */
   if (options->MyFamily) {
     ri->declared_family = smartlist_create();
     smartlist_split_string(ri->declared_family, options->MyFamily, ",",
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 8afa9f853b..66e7b62f32 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -980,6 +980,7 @@ router_add_to_routerlist(routerinfo_t *router, const char **msg)
       return -2;
     }
     router->is_verified = authdir_verified;
+    router->is_named = router->is_verified; /*XXXX NM not right. */
     if (tor_version_as_new_as(router->platform,"0.1.0.2-rc"))
       router->is_verified = 1;
   }
@@ -996,6 +997,7 @@ router_add_to_routerlist(routerinfo_t *router, const char **msg)
         if (authdir) {
           /* Update the is_verified status based on our lookup. */
           old_router->is_verified = router->is_verified;
+          old_router->is_named = router->is_named;
         } else {
           /* Update the is_running status to whatever we were told. */
           old_router->is_running = router->is_running;
@@ -1198,10 +1200,37 @@ router_load_routerlist_from_directory(const char *s,
   return 0;
 }
 
+/**DOCDOC */
+static char *
+networkstatus_get_cache_filename(const networkstatus_t *ns)
+{
+  const char *datadir = get_options()->DataDirectory;
+  size_t len = strlen(datadir)+64;
+  char fp[HEX_DIGEST_LEN+1];
+  char *fn = tor_malloc(len+1);
+  base16_encode(fp, HEX_DIGEST_LEN+1, ns->identity_digest, DIGEST_LEN);
+  tor_snprintf(fn, len, "%s/cached-status/%s",datadir,fp);
+  return fn;
+
+}
+/** DOCDOC */
+static int
+_compare_networkstatus_published_on(const void **_a, const void **_b)
+{
+  const networkstatus_t *a = *_a, *b = *_b;
+  if (a->published_on < b->published_on)
+    return -1;
+  else if (a->published_on > b->published_on)
+    return 1;
+  else
+    return 0;
+}
+
 /** How far in the future do we allow a network-status to get? (seconds) */
 #define NETWORKSTATUS_ALLOW_SKEW (48*60*60)
 /** DOCDOC returns 0 on no problems, -1 on problems.
  * requested fingerprints must be upcased.
+ * removes and frees items from requested_fingerpritns
  */
 int
 router_set_networkstatus(const char *s, time_t arrived_at,
@@ -1210,15 +1239,16 @@ router_set_networkstatus(const char *s, time_t arrived_at,
   networkstatus_t *ns;
   int i, found;
   time_t now;
-  char fp[HEX_DIGEST_LEN+1];
   int skewed = 0;
+  trusted_dir_server_t *trusted_dir;
+  char fp[HEX_DIGEST_LEN+1];
 
   ns = networkstatus_parse_from_string(s);
   if (!ns) {
     log_fn(LOG_WARN, "Couldn't parse network status.");
     return -1;
   }
-  if (!router_digest_is_trusted_dir(ns->identity_digest)) {
+  if (!(trusted_dir=router_get_trusteddirserver_by_digest(ns->identity_digest))) {
     log_fn(LOG_INFO, "Network status was signed, but not by an authoritative directory we recognize.");
     networkstatus_free(ns);
     return -1;
@@ -1238,21 +1268,27 @@ router_set_networkstatus(const char *s, time_t arrived_at,
     networkstatus_list = smartlist_create();
 
   if (source == NS_FROM_DIR && router_digest_is_me(ns->identity_digest)) {
-    /* Drop our own networkstatus when we get it from somebody else. */
+    /* Don't replace our own networkstatus when we get it from somebody else. */
     networkstatus_free(ns);
     return 0;
   }
 
   base16_encode(fp, HEX_DIGEST_LEN+1, ns->identity_digest, DIGEST_LEN);
 
-  if (requested_fingerprints &&
-      !smartlist_string_isin(requested_fingerprints, fp)) {
-    char *requested = smartlist_join_strings(requested_fingerprints," ",0,NULL);
-    log_fn(LOG_WARN, "We received a network status with a fingerprint (%s) that we never requested. (%s) Dropping.", fp, requested);
-    tor_free(requested);
-    return 0;
+  if (requested_fingerprints) {
+    if (smartlist_string_isin(requested_fingerprints, fp)) {
+      smartlist_string_remove(requested_fingerprints, fp);
+    } else {
+      char *requested = smartlist_join_strings(requested_fingerprints," ",0,NULL);
+      log_fn(LOG_WARN, "We received a network status with a fingerprint (%s) that we never requested. (%s) Dropping.", fp, requested);
+      tor_free(requested);
+      return 0;
+    }
   }
 
+  if (source != NS_FROM_CACHE)
+    trusted_dir->n_networkstatus_failures = 0;
+
   found = 0;
   for (i=0; i < smartlist_len(networkstatus_list); ++i) {
     networkstatus_t *old_ns = smartlist_get(networkstatus_list, i);
@@ -1281,11 +1317,10 @@ router_set_networkstatus(const char *s, time_t arrived_at,
   if (!found)
     smartlist_add(networkstatus_list, ns);
 
+  smartlist_sort(networkstatus_list, _compare_networkstatus_published_on);
+
   if (source != NS_FROM_CACHE && !skewed) {
-    const char *datadir = get_options()->DataDirectory;
-    size_t len = strlen(datadir)+64;
-    char *fn = tor_malloc(len+1);
-    tor_snprintf(fn, len, "%s/cached-status/%s",datadir,fp);
+    char *fn = networkstatus_get_cache_filename(ns);
     if (write_str_to_file(fn, s, 0)<0) {
       log_fn(LOG_NOTICE, "Couldn't write cached network status to \"%s\"", fn);
     }
@@ -1298,6 +1333,56 @@ router_set_networkstatus(const char *s, time_t arrived_at,
   return 0;
 }
 
+#define MAX_NETWORKSTATUS_AGE (10*24*60*60)
+/** DOCDOC */
+void
+networkstatus_list_clean(time_t now)
+{
+  int i;
+  if (!networkstatus_list)
+    return;
+
+  for (i = 0; i < smartlist_len(networkstatus_list); ++i) {
+    networkstatus_t *ns = smartlist_get(networkstatus_list, i);
+    char *fname = NULL;;
+    if (ns->published_on + MAX_NETWORKSTATUS_AGE > now)
+      continue;
+    /* Okay, this one is too old.  Remove it from the list, and delete it
+     * from the cache. */
+    smartlist_del(networkstatus_list, i--);
+    fname = networkstatus_get_cache_filename(ns);
+    if (file_status(fname) == FN_FILE) {
+      log_fn(LOG_INFO, "Removing too-old networkstatus in %s", fname);
+      unlink(fname);
+    }
+    tor_free(fname);
+    if (get_options()->DirPort) {
+      char fp[HEX_DIGEST_LEN+1];
+      base16_encode(fp, sizeof(fp), ns->identity_digest, DIGEST_LEN);
+      dirserv_set_cached_networkstatus_v2(NULL, fp, 0);
+    }
+    networkstatus_free(ns);
+  }
+}
+
+/** Helper for bsearching a list of routerstatus_t pointers.*/
+static int
+_compare_digest_to_routerstatus_entry(const void *_key, const void **_member)
+{
+  const char *key = _key;
+  const routerstatus_t *rs = *_member;
+  return memcmp(key, rs->identity_digest, DIGEST_LEN);
+}
+
+/** Return the entry in <b>ns</b> for the identity digest <b>digest</b>, or
+ * NULL if none was found. */
+routerstatus_t *
+networkstatus_find_entry(networkstatus_t *ns, const char *digest)
+{
+  return smartlist_bsearch(ns->entries, digest,
+                           _compare_digest_to_routerstatus_entry);
+}
+
 /* XXXX These should be configurable, perhaps? NM */
 #define AUTHORITY_NS_CACHE_INTERVAL 10*60
 #define NONAUTHORITY_NS_CACHE_INTERVAL 15*60
@@ -1324,6 +1409,10 @@ update_networkstatus_cache_downloads(time_t now)
          char resource[HEX_DIGEST_LEN+6];
          if (router_digest_is_me(ds->digest))
            continue;
+         if (connection_get_by_type_addr_port_purpose(
+                CONN_TYPE_DIR, ds->addr, ds->dir_port,
+                DIR_PURPOSE_FETCH_NETWORKSTATUS))
+           continue;
          strlcpy(resource, "fp/", sizeof(resource));
          base16_encode(resource+3, sizeof(resource)-3, ds->digest, DIGEST_LEN);
          strlcat(resource, ".z", sizeof(resource));
@@ -1331,7 +1420,9 @@ update_networkstatus_cache_downloads(time_t now)
        });
   } else {
     /* A non-authority cache launches one connection to a random authority. */
-    directory_get_from_dirserver(DIR_PURPOSE_FETCH_NETWORKSTATUS,"all.z",1);
+    if (!connection_get_by_type_purpose(CONN_TYPE_DIR,
+                                        DIR_PURPOSE_FETCH_NETWORKSTATUS))
+      directory_get_from_dirserver(DIR_PURPOSE_FETCH_NETWORKSTATUS,"all.z",1);
   }
 }
 
@@ -1353,10 +1444,15 @@ update_networkstatus_client_downloads(time_t now)
   char *resource, *cp;
   size_t resource_len;
 
+  if (connection_get_by_type_purpose(CONN_TYPE_DIR,
+                                     DIR_PURPOSE_FETCH_NETWORKSTATUS))
+    return;
+
   /* This is a little tricky.  We want to download enough network-status
-   * objects so that we have at least half of them under NETWORKSTATUS_MAX_VALIDITY
-   * publication time.  We want to download a new *one* if the most recent
-   * one's publication time is under NETWORKSTATUS_CLIENT_DL_INTERVAL.
+   * objects so that we have at least half of them under
+   * NETWORKSTATUS_MAX_VALIDITY publication time.  We want to download a new
+   * *one* if the most recent one's publication time is under
+   * NETWORKSTATUS_CLIENT_DL_INTERVAL.
    */
   if (!trusted_dir_servers || !smartlist_len(trusted_dir_servers))
     return;
@@ -1707,7 +1803,7 @@ routers_update_status_from_entry(smartlist_t *routers,
 {
   int authdir = get_options()->AuthoritativeDir;
   int is_running = 1;
-  int is_verified = 0;
+  int is_verified = 0, is_named = 0;
   int hex_digest_set = 0;
   char nickname[MAX_NICKNAME_LEN+1];
   char hexdigest[HEX_DIGEST_LEN+1];
@@ -1726,6 +1822,7 @@ routers_update_status_from_entry(smartlist_t *routers,
      * entry will either extend to a NUL (old running-routers format) or to an
      * equals sign (new router-status format). */
     is_verified = 1;
+    is_named = 1;
     end = strchr(cp, '=');
     if (!end)
       end = strchr(cp,'\0');
@@ -1781,9 +1878,9 @@ routers_update_status_from_entry(smartlist_t *routers,
       /* If we're not an authoritative directory, update verified status.
        */
       if (nickname_matches && digest_matches)
-        r->is_verified = 1;
+        r->is_verified = r->is_named = 1;
       else if (digest_matches)
-        r->is_verified = 0;
+        r->is_verified = r->is_named = 0;
     }
     if (digest_matches)
       if (r->status_set_at < list_time) {
@@ -1878,3 +1975,111 @@ networkstatus_get_by_digest(const char *digest)
   return NULL;
 }
 
+#define DEFAULT_RUNNING_INTERVAL 60*60
+#define MIN_TO_INFLUENCE_RUNNING 3
+void
+routers_update_status_from_networkstatus(smartlist_t *routers)
+{
+  int n_trusted, n_statuses, n_valid, n_naming, n_named, n_running, n_listing,
+    n_recent;
+  int i;
+  time_t now = time(NULL);
+
+  if (authdir_mode(get_options())) {
+    /* An authoritative directory should never believer someone else about
+     * a server's status. */
+    return;
+  }
+
+  if (!networkstatus_list)
+    networkstatus_list = smartlist_create();
+  if (!trusted_dir_servers)
+    trusted_dir_servers = smartlist_create();
+
+  n_trusted = smartlist_len(trusted_dir_servers);
+  n_statuses = smartlist_len(networkstatus_list);
+
+  if (n_statuses < (n_trusted/2)+1) {
+    /* Not enough statuses to adjust status. */
+    return;
+  }
+
+  if (n_statuses < MIN_TO_INFLUENCE_RUNNING) {
+    n_recent = n_statuses;
+  } else {
+    n_recent = 0;
+    for (i=smartlist_len(networkstatus_list)-1; i >= 0; --i) {
+      networkstatus_t *ns = smartlist_get(networkstatus_list, i);
+      if (ns->published_on + DEFAULT_RUNNING_INTERVAL < now)
+        break;
+      ++n_recent;
+    }
+    if (n_recent < MIN_TO_INFLUENCE_RUNNING) {
+      n_recent = MIN_TO_INFLUENCE_RUNNING;
+    }
+  }
+
+  SMARTLIST_FOREACH(routers, routerinfo_t *, router,
+  {
+    n_listing = n_valid = n_naming = n_named = n_running = 0;
+
+    SMARTLIST_FOREACH(networkstatus_list, networkstatus_t *, ns,
+    {
+      routerstatus_t *rs = networkstatus_find_entry(ns, router->identity_digest);
+      if (ns->binds_names)
+        ++n_naming;
+      if (!rs)
+        continue;
+      ++n_listing;
+      if (rs->is_named && !strcasecmp(rs->nickname, router->nickname))
+        ++n_named;
+      if (rs->is_valid)
+        ++n_valid;
+      if (ns_sl_idx >= smartlist_len(networkstatus_list)-n_recent) {
+        if (rs->is_running)
+          ++n_running;
+      }
+    });
+
+    log_fn(LOG_DEBUG, "Router '%s' at %s:%d is listed by %d/%d directories, "
+           "named by %d/%d, validated by %d/%d, and %d/%d recent directories "
+           "think it's running.",
+           router->nickname, router->address, router->or_port,
+           n_listing, n_statuses, n_named, n_naming, n_valid, n_statuses,
+           n_running, n_recent);
+
+    router->is_named = (n_named > n_naming/2);
+    router->is_verified = (n_valid > n_statuses/2);
+    router->is_running = (n_running > n_recent/2);
+  });
+}
+
+/** Return new list of ID digests for superseded routers.
+ * A router is superseded if any network-status has a router with a different
+ * digest published more recently.
+ */
+smartlist_t *
+router_list_superseded(void)
+{
+  smartlist_t *superseded = smartlist_create();
+
+  if (!routerlist || !networkstatus_list)
+    return superseded;
+
+  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, ri,
+  {
+    SMARTLIST_FOREACH(networkstatus_list, networkstatus_t *, ns,
+    {
+      routerstatus_t *rs = networkstatus_find_entry(ns, ri->identity_digest);
+      if (memcmp(ri->signed_descriptor_digest,rs->descriptor_digest,DIGEST_LEN)
+          && rs->published_on > ri->published_on) {
+        char *d = tor_malloc(DIGEST_LEN);
+        memcpy(d, ri->identity_digest, DIGEST_LEN);
+        smartlist_add(superseded, d);
+        break;
+      }
+    });
+  });
+  return superseded;
+}
+
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index 5befbd96dc..e7c9ca3535 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -849,7 +849,7 @@ router_parse_list_from_string(const char **s, routerlist_t **dest,
 
     if (!good_nickname_list) {
       router->is_running = 1; /* start out assuming all dirservers are up */
-      router->is_verified = 1;
+      router->is_verified = router->is_named = 1;
       router->status_set_at = time(NULL);
     }
     smartlist_add(routers, router);
@@ -1245,6 +1245,14 @@ routerstatus_parse_entry_from_string(const char **s, smartlist_t *tokens)
   return rs;
 }
 
+/** Helper to sort a smartlist of pointers to routerstatus_t */
+static int
+_compare_routerstatus_entries(const void **_a, const void **_b)
+{
+  const routerstatus_t *a = *_a, *b = *_b;
+  return memcmp(a->identity_digest, b->identity_digest, DIGEST_LEN);
+}
+
 /** Given a versioned (v2 or later) network-status object in <b>s</b>, try to
  * parse it and return the result.  Return NULL on failure.  Check the
  * signature of the network status, but do not (yet) check the signing key for
@@ -1387,6 +1395,7 @@ networkstatus_parse_from_string(const char *s)
     if ((rs = routerstatus_parse_entry_from_string(&s, tokens)))
       smartlist_add(ns->entries, rs);
   }
+  smartlist_sort(ns->entries, _compare_routerstatus_entries);
 
   if (tokenize_string(s, NULL, tokens, NETSTATUS)) {
     log_fn(LOG_WARN, "Error tokenizing network-status footer.");