routerlist.c

/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. */
/* See LICENSE for licensing information */
/* $Id$ */
const char routerlist_c_id[] =
  "$Id$";

/**
 * \file routerlist.c
 * \brief Code to
 * maintain and access the global list of routerinfos for known
 * servers.
 **/

#include "or.h"

/****************************************************************************/

/* static function prototypes */
static routerstatus_t *router_pick_directory_server_impl(int requireother,
                                                         int fascistfirewall,
                                                         int for_v2_directory);
static routerstatus_t *router_pick_trusteddirserver_impl(
                 authority_type_t type, int requireother, int fascistfirewall);
static void mark_all_trusteddirservers_up(void);
static int router_nickname_matches(routerinfo_t *router, const char *nickname);
static void routerstatus_list_update_from_networkstatus(time_t now);
static void local_routerstatus_free(local_routerstatus_t *rs);
static void trusted_dir_server_free(trusted_dir_server_t *ds);
static void update_networkstatus_cache_downloads(time_t now);
static void update_networkstatus_client_downloads(time_t now);
static int signed_desc_digest_is_recognized(signed_descriptor_t *desc);
static void routerlist_assert_ok(routerlist_t *rl);
static int have_tried_downloading_all_statuses(int n_failures);
static routerstatus_t *networkstatus_find_entry(networkstatus_t *ns,
                                                const char *digest);
static local_routerstatus_t *router_get_combined_status_by_nickname(
                                                const char *nickname,
                                                int warn_if_unnamed);
static void update_router_have_minimum_dir_info(void);
static void router_dir_info_changed(void);

/****************************************************************************/

/** Global list of a trusted_dir_server_t object for each trusted directory
 * server. */
static smartlist_t *trusted_dir_servers = NULL;

/** Global list of all of the routers that we know about. */
static routerlist_t *routerlist = NULL;

/** Global list of all of the current network_status documents that we know
 * about.  This list is kept sorted by published_on. */
static smartlist_t *networkstatus_list = NULL;

/** Global list of local_routerstatus_t for each router, known or unknown.
 * Kept sorted by digest. */
static smartlist_t *routerstatus_list = NULL;

/** Map from lowercase nickname to digest of named server, if any. */
static strmap_t *named_server_map = NULL;

/** True iff any member of networkstatus_list has changed since the last time
 * we called routerstatus_list_update_from_networkstatus(). */
static int networkstatus_list_has_changed = 0;

/** True iff any element of routerstatus_list has changed since the last
 * time we called routers_update_all_from_networkstatus().*/
static int routerstatus_list_has_changed = 0;

/** List of strings for nicknames we've already warned about and that are
 * still unknown / unavailable. */
static smartlist_t *warned_nicknames = NULL;

/** List of strings for nicknames or fingerprints we've already warned about
 * and that are still conflicted. */
static smartlist_t *warned_conflicts = NULL;

/** The last time we tried to download any routerdesc, or 0 for "never".  We
 * use this to rate-limit download attempts when the number of routerdescs to
 * download is low. */
static time_t last_routerdesc_download_attempted = 0;

/** The last time we tried to download a networkstatus, or 0 for "never".  We
 * use this to rate-limit download attempts for directory caches (including
 * mirrors).  Clients don't use this now. */
static time_t last_networkstatus_download_attempted = 0;

/** True iff we have logged a warning about this OR not being valid or
 * not being named. */
static int have_warned_about_invalid_status = 0;
/** True iff we have logged a warning about this OR's version being older than
 * listed by the authorities  */
static int have_warned_about_old_version = 0;
/** True iff we have logged a warning about this OR's version being newer than
 * listed by the authorities  */
static int have_warned_about_new_version = 0;

/** Return the number of v2 directory authorities */
static INLINE int
get_n_v2_authorities(void)
{
  int n = 0;
  if (!trusted_dir_servers)
    return 0;
  SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
                    if (ds->is_v2_authority)
                      ++n);
  return n;
}

/** Repopulate our list of network_status_t objects from the list cached on
 * disk.  Return 0 on success, -1 on failure. */
int
router_reload_networkstatus(void)
{
  char filename[512];
  struct stat st;
  smartlist_t *entries;
  char *s;
  tor_assert(get_options()->DataDirectory);
  if (!networkstatus_list)
    networkstatus_list = smartlist_create();

  tor_snprintf(filename,sizeof(filename),"%s/cached-status",
               get_options()->DataDirectory);
  entries = tor_listdir(filename);
  SMARTLIST_FOREACH(entries, const char *, fn, {
      char buf[DIGEST_LEN];
      if (strlen(fn) != HEX_DIGEST_LEN ||
          base16_decode(buf, sizeof(buf), fn, strlen(fn))) {
        log_info(LD_DIR,
                 "Skipping cached-status file with unexpected name \"%s\"",fn);
        continue;
      }
      tor_snprintf(filename,sizeof(filename),"%s/cached-status/%s",
                   get_options()->DataDirectory, fn);
      s = read_file_to_str(filename, 0);
      if (s) {
        stat(filename, &st);
        if (router_set_networkstatus(s, st.st_mtime, NS_FROM_CACHE, NULL)<0) {
          log_warn(LD_FS, "Couldn't load networkstatus from \"%s\"",filename);
        }
        tor_free(s);
      }
    });
  SMARTLIST_FOREACH(entries, char *, fn, tor_free(fn));
  smartlist_free(entries);
  networkstatus_list_clean(time(NULL));
  routers_update_all_from_networkstatus();
  return 0;
}

/* Router descriptor storage.
 *
 * Routerdescs are stored in a big file, named "cached-routers".  As new
 * routerdescs arrive, we append them to a journal file named
 * "cached-routers.new".
 *
 * From time to time, we replace "cached-routers" with a new file containing
 * only the live, non-superseded descriptors, and clear cached-routers.new.
 *
 * On startup, we read both files.
 */

/** The size of the router log, in bytes. */
static size_t router_journal_len = 0;
/** The size of the router store, in bytes. */
static size_t router_store_len = 0;
/** Total bytes dropped since last rebuild. */
static size_t router_bytes_dropped = 0;

/** Helper: return 1 iff the router log is so big we want to rebuild the
 * store. */
static int
router_should_rebuild_store(void)
{
  if (router_store_len > (1<<16))
    return (router_journal_len > router_store_len / 2 ||
            router_bytes_dropped > router_store_len / 2);
  else
    return router_journal_len > (1<<15);
}

/** Add the <b>len</b>-type router descriptor in <b>s</b> to the router
 * journal. */
static int
router_append_to_journal(signed_descriptor_t *desc)
{
  or_options_t *options = get_options();
  size_t fname_len = strlen(options->DataDirectory)+32;
  char *fname = tor_malloc(fname_len);
  const char *body = signed_descriptor_get_body(desc);
  size_t len = desc->signed_descriptor_len;

  tor_snprintf(fname, fname_len, "%s/cached-routers.new",
               options->DataDirectory);

  tor_assert(len == strlen(body));

  if (append_bytes_to_file(fname, body, len, 1)) {
    log_warn(LD_FS, "Unable to store router descriptor");
    tor_free(fname);
    return -1;
  }
  desc->saved_location = SAVED_IN_JOURNAL;
  desc->saved_offset = router_journal_len;

  tor_free(fname);
  router_journal_len += len;
  return 0;
}

static int
_compare_old_routers_by_age(const void **_a, const void **_b)
{
  const signed_descriptor_t *r1 = *_a, *r2 = *_b;
  return r1->published_on - r2->published_on;
}

static int
_compare_routers_by_age(const void **_a, const void **_b)
{
  const routerinfo_t *r1 = *_a, *r2 = *_b;
  return r1->cache_info.published_on - r2->cache_info.published_on;
}

/** If the journal is too long, or if <b>force</b> is true, then atomically
 * replace the router store with the routers currently in our routerlist, and
 * clear the journal.  Return 0 on success, -1 on failure.
 */
static int
router_rebuild_store(int force)
{
  size_t len = 0;
  or_options_t *options;
  size_t fname_len;
  smartlist_t *chunk_list = NULL;
  char *fname = NULL;
  int r = -1, i;
  off_t offset = 0;
  smartlist_t *old_routers, *routers;

  if (!force && !router_should_rebuild_store())
    return 0;
  if (!routerlist)
    return 0;

  /* Don't save deadweight. */
  routerlist_remove_old_routers();

  log_info(LD_DIR, "Rebuilding router descriptor cache");

  options = get_options();
  fname_len = strlen(options->DataDirectory)+32;
  fname = tor_malloc(fname_len);
  tor_snprintf(fname, fname_len, "%s/cached-routers", options->DataDirectory);
  chunk_list = smartlist_create();

  old_routers = smartlist_create();
  smartlist_add_all(old_routers, routerlist->old_routers);
  smartlist_sort(old_routers, _compare_old_routers_by_age);
  routers = smartlist_create();
  smartlist_add_all(routers, routerlist->routers);
  smartlist_sort(routers, _compare_routers_by_age);
  for (i = 0; i < 2; ++i) {
    smartlist_t *lst = smartlist_create();
    /* We sort the routers by age to enhance locality on disk. */
    if (i==0)
      lst = old_routers;
    else
      lst = routers;
    /* Now, add the appropriate members to chunk_list */
    SMARTLIST_FOREACH(lst, void *, ptr,
    {
      signed_descriptor_t *sd = (i==0) ?
        ((signed_descriptor_t*)ptr): &((routerinfo_t*)ptr)->cache_info;
      sized_chunk_t *c;
      const char *body = signed_descriptor_get_body(sd);
      if (!body) {
        log_warn(LD_BUG, "Bug! No descriptor available for router.");
        smartlist_free(lst);
        goto done;
      }
      c = tor_malloc(sizeof(sized_chunk_t));
      c->bytes = body;
      c->len = sd->signed_descriptor_len;
      smartlist_add(chunk_list, c);
    });
  }
  if (write_chunks_to_file(fname, chunk_list, 1)<0) {
    log_warn(LD_FS, "Error writing router store to disk.");
    goto done;
  }
  /* Our mmap is now invalid. */
  if (routerlist->mmap_descriptors) {
    tor_munmap_file(routerlist->mmap_descriptors);
    routerlist->mmap_descriptors = tor_mmap_file(fname);
    if (! routerlist->mmap_descriptors)
      log_warn(LD_FS, "Unable to mmap new descriptor file at '%s'.",fname);
  }

  offset = 0;
  for (i = 0; i < 2; ++i) {
    smartlist_t *lst = (i == 0) ? old_routers : routers;
    SMARTLIST_FOREACH(lst, void *, ptr,
    {
      signed_descriptor_t *sd = (i==0) ?
        ((signed_descriptor_t*)ptr): &((routerinfo_t*)ptr)->cache_info;

      sd->saved_location = SAVED_IN_CACHE;
      if (routerlist->mmap_descriptors) {
        tor_free(sd->signed_descriptor_body); // sets it to null
        sd->saved_offset = offset;
      }
      offset += sd->signed_descriptor_len;
      signed_descriptor_get_body(sd);
    });
  }
  smartlist_free(old_routers);
  smartlist_free(routers);

  tor_snprintf(fname, fname_len, "%s/cached-routers.new",
               options->DataDirectory);

  write_str_to_file(fname, "", 1);

  r = 0;
  router_store_len = len;
  router_journal_len = 0;
  router_bytes_dropped = 0;
 done:
  tor_free(fname);
  if (chunk_list) {
    SMARTLIST_FOREACH(chunk_list, sized_chunk_t *, c, tor_free(c));
    smartlist_free(chunk_list);
  }
  return r;
}

/* Load all cached router descriptors from the store. Return 0 on success and
 * -1 on failure.
 */
int
router_reload_router_list(void)
{
  or_options_t *options = get_options();
  size_t fname_len = strlen(options->DataDirectory)+32;
  char *fname = tor_malloc(fname_len), *contents;
  struct stat st;

  if (!routerlist)
    router_get_routerlist(); /* mallocs and inits it in place */

  router_journal_len = router_store_len = 0;

  tor_snprintf(fname, fname_len, "%s/cached-routers", options->DataDirectory);

  if (routerlist->mmap_descriptors) /* get rid of it first */
    tor_munmap_file(routerlist->mmap_descriptors);

  routerlist->mmap_descriptors = tor_mmap_file(fname);
  if (routerlist->mmap_descriptors) {
    router_store_len = routerlist->mmap_descriptors->size;
    router_load_routers_from_string(routerlist->mmap_descriptors->data,
                                    SAVED_IN_CACHE, NULL);
  }

  tor_snprintf(fname, fname_len, "%s/cached-routers.new",
               options->DataDirectory);
  contents = read_file_to_str(fname, 1);
  if (contents) {
    stat(fname, &st);
    router_load_routers_from_string(contents,
                                    SAVED_IN_JOURNAL, NULL);
    tor_free(contents);
  }

  tor_free(fname);

  if (router_journal_len) {
    /* Always clear the journal on startup.*/
    router_rebuild_store(1);
  } else {
    /* Don't cache expired routers. (This is in an else because
     * router_rebuild_store() also calls remove_old_routers().) */
    routerlist_remove_old_routers();
  }

  return 0;
}

/** Return a smartlist containing a list of trusted_dir_server_t * for all
 * known trusted dirservers.  Callers must not modify the list or its
 * contents.
 */
smartlist_t *
router_get_trusted_dir_servers(void)
{
  if (!trusted_dir_servers)
    trusted_dir_servers = smartlist_create();

  return trusted_dir_servers;
}

/** Try to find a running dirserver. If there are no running dirservers
 * in our routerlist and <b>retry_if_no_servers</b> is non-zero,
 * set all the authoritative ones as running again, and pick one;
 * if there are then no dirservers at all in our routerlist,
 * reload the routerlist and try one last time. If for_runningrouters is
 * true, then only pick a dirserver that can answer runningrouters queries
 * (that is, a trusted dirserver, or one running 0.0.9rc5-cvs or later).
 * Don't pick an authority if any non-authority is viable.
 * Other args are as in router_pick_directory_server_impl().
 */
routerstatus_t *
router_pick_directory_server(int requireother,
                             int fascistfirewall,
                             int for_v2_directory,
                             int retry_if_no_servers)
{
  routerstatus_t *choice;

  if (!routerlist)
    return NULL;

  choice = router_pick_directory_server_impl(requireother, fascistfirewall,
                                             for_v2_directory);
  if (choice || !retry_if_no_servers)
    return choice;

  log_info(LD_DIR,
           "No reachable router entries for dirservers. "
           "Trying them all again.");
  /* mark all authdirservers as up again */
  mark_all_trusteddirservers_up();
  /* try again */
  choice = router_pick_directory_server_impl(requireother, fascistfirewall,
                                             for_v2_directory);
  if (choice)
    return choice;

  log_info(LD_DIR,"Still no %s router entries. Reloading and trying again.",
           fascistfirewall ? "reachable" : "known");
  if (router_reload_router_list()) {
    return NULL;
  }
  /* give it one last try */
  choice = router_pick_directory_server_impl(requireother, fascistfirewall,
                                             for_v2_directory);
  return choice;
}

/** Return the trusted_dir_server_t for the directory authority whose identity
 * key hashes to <b>digest</b>, or NULL if no such authority is known.
 */
trusted_dir_server_t *
router_get_trusteddirserver_by_digest(const char *digest)
{
  if (!trusted_dir_servers)
    return NULL;

  SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
     {
       if (!memcmp(ds->digest, digest, DIGEST_LEN))
         return ds;
     });

  return NULL;
}

/** Try to find a running trusted dirserver. If there are no running
 * trusted dirservers and <b>retry_if_no_servers</b> is non-zero,
 * set them all as running again, and try again.
 * If <b>need_v1_authority</b> is set, return only trusted servers
 * that are authorities for the V1 directory protocol.
 * Other args are as in router_pick_trusteddirserver_impl().
 */
routerstatus_t *
router_pick_trusteddirserver(authority_type_t type,
                             int requireother,
                             int fascistfirewall,
                             int retry_if_no_servers)
{
  routerstatus_t *choice;

  choice = router_pick_trusteddirserver_impl(type,
                                             requireother, fascistfirewall);
  if (choice || !retry_if_no_servers)
    return choice;

  log_info(LD_DIR,
           "No trusted dirservers are reachable. Trying them all again.");
  mark_all_trusteddirservers_up();
  return router_pick_trusteddirserver_impl(type,
                                           requireother, fascistfirewall);
}

/** Pick a random running valid directory server/mirror from our
 * routerlist.  Don't pick an authority if any non-authorities are viable.
 * If <b>fascistfirewall</b>,
 * make sure the router we pick is allowed by our firewall options.
 * If <b>requireother</b>, it cannot be us.  If <b>for_v2_directory</b>,
 * choose a directory server new enough to support the v2 directory
 * functionality.
 */
static routerstatus_t *
router_pick_directory_server_impl(int requireother, int fascistfirewall,
                                  int for_v2_directory)
{
  routerstatus_t *result;
  smartlist_t *sl;
  smartlist_t *trusted;

  if (!routerstatus_list)
    return NULL;

  /* Find all the running dirservers we know about. */
  sl = smartlist_create();
  trusted = smartlist_create();
  SMARTLIST_FOREACH(routerstatus_list, local_routerstatus_t *, _local_status,
  {
    routerstatus_t *status = &(_local_status->status);
    int is_trusted;
    if (!status->is_running || !status->dir_port || !status->is_valid)
      continue;
    if (requireother && router_digest_is_me(status->identity_digest))
      continue;
    if (fascistfirewall) {
      if (!fascist_firewall_allows_address_dir(status->addr, status->dir_port))
        continue;
    }
    is_trusted = router_digest_is_trusted_dir(status->identity_digest);
    if (for_v2_directory && !(status->is_v2_dir || is_trusted))
      continue;
    smartlist_add(is_trusted ? trusted : sl, status);
  });

  if (smartlist_len(sl))
    result = smartlist_choose(sl);
  else
    result = smartlist_choose(trusted);
  smartlist_free(sl);
  smartlist_free(trusted);
  return result;
}

/** Choose randomly from among the trusted dirservers that are up.  If
 * <b>fascistfirewall</b>, make sure the port we pick is allowed by our
 * firewall options.  If <b>requireother</b>, it cannot be us.  If
 * <b>need_v1_authority</b>, choose a trusted authority for the v1 directory
 * system.
 */
static routerstatus_t *
router_pick_trusteddirserver_impl(authority_type_t type,
                                  int requireother, int fascistfirewall)
{
  smartlist_t *sl;
  routerinfo_t *me;
  routerstatus_t *rs;
  sl = smartlist_create();
  me = router_get_my_routerinfo();

  if (!trusted_dir_servers)
    return NULL;

  SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, d,
    {
      if (!d->is_running) continue;
      if (type == V1_AUTHORITY && !d->is_v1_authority)
        continue;
      if (type == V2_AUTHORITY && !d->is_v2_authority)
        continue;
      if (type == HIDSERV_AUTHORITY && !d->is_hidserv_authority)
        continue;
      if (requireother && me && router_digest_is_me(d->digest))
          continue;
      if (fascistfirewall) {
        if (!fascist_firewall_allows_address_dir(d->addr, d->dir_port))
          continue;
      }
      smartlist_add(sl, &d->fake_status);
    });

  rs = smartlist_choose(sl);
  smartlist_free(sl);
  return rs;
}

/** Go through and mark the authoritative dirservers as up. */
static void
mark_all_trusteddirservers_up(void)
{
  if (routerlist) {
    SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
       if (router_digest_is_trusted_dir(router->cache_info.identity_digest) &&
         router->dir_port > 0) {
         router->is_running = 1;
       });
  }
  if (trusted_dir_servers) {
    SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, dir,
    {
      local_routerstatus_t *rs;
      dir->is_running = 1;
      dir->n_networkstatus_failures = 0;
      rs = router_get_combined_status_by_digest(dir->digest);
      if (rs)
        rs->status.is_running = 1;
    });
  }
  last_networkstatus_download_attempted = 0;
  router_dir_info_changed();
}

/** Reset all internal variables used to count failed downloads of network
 * status objects. */
void
router_reset_status_download_failures(void)
{
  mark_all_trusteddirservers_up();
}

/** Look through the routerlist and identify routers that
 * advertise the same /16 network address as <b>router</b>.
 * Add each of them to <b>sl</b>.
 */
static void
routerlist_add_network_family(smartlist_t *sl, routerinfo_t *router)
{
  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, r,
  {
    if (router != r &&
        (router->addr & 0xffff0000) == (r->addr & 0xffff0000))
      smartlist_add(sl, r);
  });
}

/** Add all the family of <b>router</b> to the smartlist <b>sl</b>.
 * This is used to make sure we don't pick siblings in a single path.
 */
void
routerlist_add_family(smartlist_t *sl, routerinfo_t *router)
{
  routerinfo_t *r;
  config_line_t *cl;
  or_options_t *options = get_options();

  /* First, add any routers with similar network addresses.
   * XXX It's possible this will be really expensive; we'll see. */
  if (options->EnforceDistinctSubnets)
    routerlist_add_network_family(sl, router);

  if (!router->declared_family)
    return;

  /* Add every r such that router declares familyness with r, and r
   * declares familyhood with router. */
  SMARTLIST_FOREACH(router->declared_family, const char *, n,
    {
      if (!(r = router_get_by_nickname(n, 0)))
        continue;
      if (!r->declared_family)
        continue;
      SMARTLIST_FOREACH(r->declared_family, const char *, n2,
        {
          if (router_nickname_matches(router, n2))
            smartlist_add(sl, r);
        });
    });

  /* If the user declared any families locally, honor those too. */
  for (cl = get_options()->NodeFamilies; cl; cl = cl->next) {
    if (router_nickname_is_in_list(router, cl->value)) {
      add_nickname_list_to_smartlist(sl, cl->value, 0, 1, 1);
    }
  }
}

/** Given a (possibly NULL) comma-and-whitespace separated list of nicknames,
 * see which nicknames in <b>list</b> name routers in our routerlist, and add
 * the routerinfos for those routers to <b>sl</b>.  If <b>must_be_running</b>,
 * only include routers that we think are running.  If <b>warn_if_down</b>,
 * warn if some included routers aren't running.  If <b>warn_if_unnamed</b>,
 * warn if any non-Named routers are specified by nickname.
 */
void
add_nickname_list_to_smartlist(smartlist_t *sl, const char *list,
                               int must_be_running,
                               int warn_if_down, int warn_if_unnamed)
{
  routerinfo_t *router;
  smartlist_t *nickname_list;
  int have_dir_info = router_have_minimum_dir_info();

  if (!list)
    return; /* nothing to do */
  tor_assert(sl);

  nickname_list = smartlist_create();
  if (!warned_nicknames)
    warned_nicknames = smartlist_create();

  smartlist_split_string(nickname_list, list, ",",
                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);

  SMARTLIST_FOREACH(nickname_list, const char *, nick, {
    int warned;
    if (!is_legal_nickname_or_hexdigest(nick)) {
      log_warn(LD_CONFIG, "Nickname '%s' is misformed; skipping", nick);
      continue;
    }
    router = router_get_by_nickname(nick, warn_if_unnamed);
    warned = smartlist_string_isin(warned_nicknames, nick);
    if (router) {
      if (!must_be_running || router->is_running) {
        smartlist_add(sl,router);
        if (warned)
          smartlist_string_remove(warned_nicknames, nick);
      } else {
        if (!warned) {
          log_fn(warn_if_down ? LOG_WARN : LOG_DEBUG, LD_CONFIG,
                 "Nickname list includes '%s' which is known but down.",nick);
          smartlist_add(warned_nicknames, tor_strdup(nick));
        }
      }
    } else if (!router_get_combined_status_by_nickname(nick,warn_if_unnamed)) {
      if (!warned) {
        log_fn(have_dir_info ? LOG_WARN : LOG_INFO, LD_CONFIG,
               "Nickname list includes '%s' which isn't a known router.",nick);
        smartlist_add(warned_nicknames, tor_strdup(nick));
      }
    }
  });
  SMARTLIST_FOREACH(nickname_list, char *, nick, tor_free(nick));
  smartlist_free(nickname_list);
}

/** Return 1 iff any member of the (possibly NULL) comma-separated list
 * <b>list</b> is an acceptable nickname or hexdigest for <b>router</b>.  Else
 * return 0.
 */
int
router_nickname_is_in_list(routerinfo_t *router, const char *list)
{
  smartlist_t *nickname_list;
  int v = 0;

  if (!list)
    return 0; /* definitely not */
  tor_assert(router);

  nickname_list = smartlist_create();
  smartlist_split_string(nickname_list, list, ",",
                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  SMARTLIST_FOREACH(nickname_list, const char *, cp,
                    if (router_nickname_matches(router, cp)) {v=1;break;});
  SMARTLIST_FOREACH(nickname_list, char *, cp, tor_free(cp));
  smartlist_free(nickname_list);
  return v;
}

/** Add every router from our routerlist that is currently running to
 * <b>sl</b>, so that we can pick a node for a circuit.
 */
static void
router_add_running_routers_to_smartlist(smartlist_t *sl, int allow_invalid,
                                        int need_uptime, int need_capacity,
                                        int need_guard)
{
  if (!routerlist)
    return;

  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  {
    if (router->is_running &&
        router->purpose == ROUTER_PURPOSE_GENERAL &&
        (router->is_valid ||
/* XXX this next part is wrong and should be fixed one day -RD */
        (allow_invalid &&
         !router_is_unreliable(router, need_uptime,
                               need_capacity, need_guard)))) {
      /* If it's running, and either it's valid or we're ok picking
       * invalid routers and this one is suitable.
       */
      smartlist_add(sl, router);
    }
  });
}

/** Look through the routerlist until we find a router that has my key.
 Return it. */
routerinfo_t *
routerlist_find_my_routerinfo(void)
{
  if (!routerlist)
    return NULL;

  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  {
    if (router_is_me(router))
      return router;
  });
  return NULL;
}

/** Find a router that's up, that has this IP address, and
 * that allows exit to this address:port, or return NULL if there
 * isn't a good one.
 */
routerinfo_t *
router_find_exact_exit_enclave(const char *address, uint16_t port)
{
  uint32_t addr;
  struct in_addr in;

  if (!tor_inet_aton(address, &in))
    return NULL; /* it's not an IP already */
  addr = ntohl(in.s_addr);

  SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
  {
    if (router->is_running &&
        router->addr == addr &&
        compare_addr_to_addr_policy(addr, port, router->exit_policy) ==
          ADDR_POLICY_ACCEPTED)
      return router;
  });
  return NULL;
}

/** Return 1 if <b>router</b> is not suitable for these parameters, else 0.
 * If <b>need_uptime</b> is non-zero, we require a minimum uptime.
 * If <b>need_capacity</b> is non-zero, we require a minimum advertised
 * bandwidth.
 */
int
router_is_unreliable(routerinfo_t *router, int need_uptime,
                     int need_capacity, int need_guard)
{
  if (need_uptime && !router->is_stable)
    return 1;
  if (need_capacity && !router->is_fast)
    return 1;
  if (need_guard && !router->is_possible_guard)
    return 1;
  return 0;
}

/** Remove from routerlist <b>sl</b> all routers that are not
 * sufficiently stable. */
static void
routerlist_sl_remove_unreliable_routers(smartlist_t *sl, int need_uptime,
                                        int need_capacity, int need_guard)
{
  int i;
  routerinfo_t *router;

  for (i = 0; i < smartlist_len(sl); ++i) {
    router = smartlist_get(sl, i);
    if (router_is_unreliable(router, need_uptime,
                             need_capacity, need_guard)) {
//      log(LOG_DEBUG, "Router '%s' has insufficient uptime; deleting.",
 //         router->nickname);
      smartlist_del(sl, i--);
    }
  }
}

/** Return the smaller of the router's configured BandwidthRate
 * and its advertised capacity. */
uint32_t
router_get_advertised_bandwidth(routerinfo_t *router)
{
  if (router->bandwidthcapacity < router->bandwidthrate)
    return router->bandwidthcapacity;
  return router->bandwidthrate;
}

#define MAX_BELIEVABLE_BANDWIDTH 1500000 /* 1.5 MB/sec */

/** Choose a random element of router list <b>sl</b>, weighted by
 * the advertised bandwidth of each router.
 */