dirserv.c

/* Copyright 2001-2004 Roger Dingledine.
 * Copyright 2004-2005 Roger Dingledine, Nick Mathewson. */
/* See LICENSE for licensing information */
/* $Id$ */
const char dirserv_c_id[] = "$Id$";

#include "or.h"

/**
 * \file dirserv.c
 * \brief Directory server core implementation. Manages directory
 * contents and generates directories.
 **/

/** How far in the future do we allow a router to get? (seconds) */
#define ROUTER_ALLOW_SKEW (60*60*12) /* 12 hours */
/** How many seconds do we wait before regenerating the directory? */
#define DIR_REGEN_SLACK_TIME 30

extern long stats_n_seconds_working;

typedef enum {
  FP_NAMED, /**< Listed in fingerprint file. */
  FP_VALID, /**< Unlisted but believed valid. */
  FP_INVALID, /**< Believed invalid. */
  FP_REJECT, /**< We will not publish this router. */
} router_status_t;

/** Do we need to regenerate the directory when someone asks for it? */
static int the_directory_is_dirty = 1;
static int runningrouters_is_dirty = 1;
static int the_v2_networkstatus_is_dirty = 1;

static void directory_remove_invalid(void);
static int dirserv_regenerate_directory(void);
static char *format_versions_list(config_line_t *ln);
/* Should be static; exposed for testing */
int add_fingerprint_to_dir(const char *nickname, const char *fp, smartlist_t *list);
static int router_is_general_exit(routerinfo_t *ri);
static router_status_t dirserv_router_get_status(const routerinfo_t *router,
                                                 const char **msg);
static int dirserv_thinks_router_is_reachable(routerinfo_t *router,
                                              time_t now);

/************** Fingerprint handling code ************/

static addr_policy_t *authdir_reject_policy = NULL;
static addr_policy_t *authdir_invalid_policy = NULL;

/** Parse authdir policy strings from the configuration.
 */
void
parse_authdir_policy(void)
{
  addr_policy_t *n;
  if (authdir_reject_policy) {
    addr_policy_free(authdir_reject_policy);
    authdir_reject_policy = NULL;
  }
  config_parse_addr_policy(get_options()->AuthDirReject,
                           &authdir_reject_policy, ADDR_POLICY_REJECT);
  /* ports aren't used. */
  for (n=authdir_reject_policy; n; n = n->next) {
    n->prt_min = 1;
    n->prt_max = 65535;
  }

  if (authdir_invalid_policy) {
    addr_policy_free(authdir_invalid_policy);
    authdir_invalid_policy = NULL;
  }
  config_parse_addr_policy(get_options()->AuthDirInvalid,
                           &authdir_invalid_policy, ADDR_POLICY_REJECT);
  /* ports aren't used. */
  for (n=authdir_invalid_policy; n; n = n->next) {
    n->prt_min = 1;
    n->prt_max = 65535;
  }
}

/** A member of fingerprint_list: maps a name to a fingerprint.
 **/
typedef struct fingerprint_entry_t {
  char *nickname; /**< The name of a router (if this fingerprint is bound to a
                   * name); the string "!reject" (if this fingerprint should
                   * always be rejected); or the string "!invalid" (if this
                   * fingerprint should be accepted but never marked as
                   * valid. */
  char *fingerprint; /**< Stored as HEX_DIGEST_LEN characters, followed by a NUL */
} fingerprint_entry_t;

/** List of nickname-\>identity fingerprint mappings for all the routers
 * that we name.  Used to prevent router impersonation. */
/* Should be static; exposed for testing */
smartlist_t *fingerprint_list = NULL;

/** Add the fingerprint <b>fp</b> for the nickname <b>nickname</b> to
 * the smartlist of fingerprint_entry_t's <b>list</b>. Return 0 if it's
 * new, or 1 if we replaced the old value.
 */
int /* Should be static; exposed for testing */
add_fingerprint_to_dir(const char *nickname, const char *fp, smartlist_t *list)
{
  int i;
  fingerprint_entry_t *ent;
  char *fingerprint;
  tor_assert(nickname);
  tor_assert(fp);
  tor_assert(list);

  fingerprint = tor_strdup(fp);
  tor_strstrip(fingerprint, " ");

  if (nickname[0] != '!') {
    for (i = 0; i < smartlist_len(list); ++i) {
      ent = smartlist_get(list, i);
      if (!strcasecmp(ent->nickname,nickname)) {
        tor_free(ent->fingerprint);
        ent->fingerprint = fingerprint;
        return 1;
      }
    }
  }
  ent = tor_malloc(sizeof(fingerprint_entry_t));
  ent->nickname = tor_strdup(nickname);
  ent->fingerprint = fingerprint;
  smartlist_add(list, ent);
  return 0;
}

/** Add the nickname and fingerprint for this OR to the
 * global list of recognized identity key fingerprints. */
int
dirserv_add_own_fingerprint(const char *nickname, crypto_pk_env_t *pk)
{
  char fp[FINGERPRINT_LEN+1];
  if (crypto_pk_get_fingerprint(pk, fp, 0)<0) {
    err(LD_BUG, "Error computing fingerprint");
    return -1;
  }
  if (!fingerprint_list)
    fingerprint_list = smartlist_create();
  add_fingerprint_to_dir(nickname, fp, fingerprint_list);
  return 0;
}

/** Parse the nickname-\>fingerprint mappings stored in the file named
 * <b>fname</b>.  The file format is line-based, with each non-blank
 * holding one nickname, some space, and a fingerprint for that
 * nickname.  On success, replace the current fingerprint list with
 * the contents of <b>fname</b> and return 0.  On failure, leave the
 * current fingerprint list untouched, and return -1. */
int
dirserv_parse_fingerprint_file(const char *fname)
{
  char *cf;
  char *nickname, *fingerprint;
  smartlist_t *fingerprint_list_new;
  int result;
  config_line_t *front=NULL, *list;

  cf = read_file_to_str(fname, 0);
  if (!cf) {
    warn(LD_FS, "Cannot open fingerprint file %s", fname);
    return -1;
  }
  result = config_get_lines(cf, &front);
  tor_free(cf);
  if (result < 0) {
    warn(LD_CONFIG, "Error reading from fingerprint file");
    return -1;
  }

  fingerprint_list_new = smartlist_create();

  for (list=front; list; list=list->next) {
    nickname = list->key; fingerprint = list->value;
    if (strlen(nickname) > MAX_NICKNAME_LEN) {
      notice(LD_CONFIG,
            "Nickname '%s' too long in fingerprint file. Skipping.", nickname);
      continue;
    }
    if (!is_legal_nickname(nickname) &&
        strcasecmp(nickname, "!reject") &&
        strcasecmp(nickname, "!invalid")) {
      notice(LD_CONFIG,
             "Invalid nickname '%s' in fingerprint file. Skipping.", nickname);
      continue;
    }
    if (strlen(fingerprint) != FINGERPRINT_LEN ||
        !crypto_pk_check_fingerprint_syntax(fingerprint)) {
      notice(LD_CONFIG,
             "Invalid fingerprint (nickname '%s', fingerprint %s). Skipping.",
             nickname, fingerprint);
      continue;
    }
    if (0==strcasecmp(nickname, DEFAULT_CLIENT_NICKNAME)) {
      /* If you approved an OR called "client", then clients who use
       * the default nickname could all be rejected.  That's no good. */
      notice(LD_CONFIG,
          "Authorizing a nickname '%s' would break many clients; skipping.",
          DEFAULT_CLIENT_NICKNAME);
      continue;
    }
    if (add_fingerprint_to_dir(nickname, fingerprint, fingerprint_list_new) != 0)
      notice(LD_CONFIG, "Duplicate nickname '%s'.", nickname);
  }

  config_free_lines(front);
  dirserv_free_fingerprint_list();
  fingerprint_list = fingerprint_list_new;
  /* Delete any routers whose fingerprints we no longer recognize */
  directory_remove_invalid();
  return 0;
}

/** Check whether <b>router</b> has a nickname/identity key combination that
 * we recognize from the fingerprint list, or an IP we automatically act on
 * according to our configuration.  Return the appropriate router status.
 *
 * If the status is 'FP_REJECT' and <b>msg</b> is provided, set
 * *<b>msg</b> to an explanation of why.
 */
static router_status_t
dirserv_router_get_status(const routerinfo_t *router, const char **msg)
{
  fingerprint_entry_t *nn_ent = NULL, *fp_ent = NULL;
  char fp[FINGERPRINT_LEN+1];

  if (!fingerprint_list)
    fingerprint_list = smartlist_create();

  if (crypto_pk_get_fingerprint(router->identity_pkey, fp, 0)) {
    warn(LD_BUG,"Error computing fingerprint");
    return -1;
  }

  debug(LD_DIRSERV, "%d fingerprints known.", smartlist_len(fingerprint_list));
  SMARTLIST_FOREACH(fingerprint_list, fingerprint_entry_t *, ent,
  {
    if (!strcasecmp(fp,ent->fingerprint))
      fp_ent = ent;
    if (!strcasecmp(router->nickname,ent->nickname))
      nn_ent = ent;
  });

  if (fp_ent) {
    if (!strcasecmp(fp_ent->nickname, "!reject")) {
      if (msg)
        *msg = "Fingerprint is marked rejected";
      return FP_REJECT;
    } else if (!strcasecmp(fp_ent->nickname, "!invalid")) {
      if (msg)
        *msg = "Fingerprint is marged invalid";
      return FP_INVALID;
    }
  }

  if (!nn_ent) { /* No such server known with that nickname */
    addr_policy_result_t rej = router_compare_addr_to_addr_policy(
                       router->addr, router->or_port, authdir_reject_policy);
    addr_policy_result_t inv = router_compare_addr_to_addr_policy(
                       router->addr, router->or_port, authdir_invalid_policy);

    if (rej == ADDR_POLICY_PROBABLY_REJECTED || rej == ADDR_POLICY_REJECTED) {
      info(LD_DIRSERV, "Rejecting '%s' because of address %s",
           router->nickname, router->address);
      if (msg)
        *msg = "Authdir is rejecting routers in this range.";
      return FP_REJECT;
    }
    if (inv == ADDR_POLICY_PROBABLY_REJECTED || inv == ADDR_POLICY_REJECTED) {
      info(LD_DIRSERV, "Not marking '%s' valid because of address %s",
           router->nickname, router->address);
      return FP_INVALID;
    }
    if (tor_version_as_new_as(router->platform,"0.1.0.2-rc"))
      return FP_VALID;
    else
      return FP_INVALID;
    info(LD_DIRSERV,"No fingerprint found for '%s'",router->nickname);
    return 0;
  }
  if (0==strcasecmp(nn_ent->fingerprint, fp)) {
    debug(LD_DIRSERV,"Good fingerprint for '%s'",router->nickname);
    return FP_NAMED; /* Right fingerprint. */
  } else {
    warn(LD_DIRSERV,"Mismatched fingerprint for '%s': expected '%s' got '%s'. ContactInfo '%s', platform '%s'.)",
         router->nickname, nn_ent->fingerprint, fp,
         router->contact_info ? router->contact_info : "",
         router->platform ? router->platform : "");
    if (msg)
      *msg = "Rejected: There is already a verified server with this nickname and a different fingerprint.";
    return FP_REJECT; /* Wrong fingerprint. */
  }
}

/** If we are an authoritative dirserver, and the list of approved
 * servers contains one whose identity key digest is <b>digest</b>,
 * return that router's nickname.  Otherwise return NULL. */
const char *
dirserv_get_nickname_by_digest(const char *digest)
{
  char hexdigest[HEX_DIGEST_LEN+1];
  if (!fingerprint_list)
    return NULL;
  tor_assert(digest);

  base16_encode(hexdigest, HEX_DIGEST_LEN+1, digest, DIGEST_LEN);
  SMARTLIST_FOREACH(fingerprint_list, fingerprint_entry_t*, ent,
                    { if (!strcasecmp(hexdigest, ent->fingerprint))
                         return ent->nickname; } );
  return NULL;
}

/** Clear the current fingerprint list. */
void
dirserv_free_fingerprint_list(void)
{
  int i;
  fingerprint_entry_t *ent;
  if (!fingerprint_list)
    return;

  for (i = 0; i < smartlist_len(fingerprint_list); ++i) {
    ent = smartlist_get(fingerprint_list, i);
    tor_free(ent->nickname);
    tor_free(ent->fingerprint);
    tor_free(ent);
  }
  smartlist_free(fingerprint_list);
  fingerprint_list = NULL;
}

/*
 *    Descriptor list
 */

/** Return -1 if <b>ri</b> has a private or otherwise bad address,
 * unless we're configured to not care. Return 0 if all ok. */
static int
dirserv_router_has_valid_address(routerinfo_t *ri)
{
  struct in_addr iaddr;
  if (get_options()->DirAllowPrivateAddresses)
    return 0; /* whatever it is, we're fine with it */
  if (!tor_inet_aton(ri->address, &iaddr)) {
    info(LD_DIRSERV,"Router '%s' published non-IP address '%s'. Refusing.",
         ri->nickname, ri->address);
    return -1;
  }
  if (is_internal_IP(ntohl(iaddr.s_addr))) {
    info(LD_DIRSERV,
         "Router '%s' published internal IP address '%s'. Refusing.",
         ri->nickname, ri->address);
    return -1; /* it's a private IP, we should reject it */
  }
  return 0;
}

/** Check whether we, as a directory server, want to accept <b>ri</b>.  If so,
 * return 0, and set its is_valid,named,running fields.  Otherwise, return -1.
 *
 * If the router is rejected, set *<b>msg</b> to an explanation of why.
 */
int
authdir_wants_to_reject_router(routerinfo_t *ri,
                               const char **msg)
{
  /* Okay.  Now check whether the fingerprint is recognized. */
  router_status_t status = dirserv_router_get_status(ri, msg);
  time_t now;
  tor_assert(msg);
  if (status == FP_REJECT)
    return -1; /* msg is already set. */

  /* Is there too much clock skew? */
  now = time(NULL);
  if (ri->cache_info.published_on > now+ROUTER_ALLOW_SKEW) {
    notice(LD_DIRSERV, "Publication time for nickname '%s' is too far (%d minutes) in the future; possible clock skew. Not adding (ContactInfo '%s', platform '%s').",
           ri->nickname, (int)((ri->cache_info.published_on-now)/60),
           ri->contact_info ? ri->contact_info : "",
           ri->platform ? ri->platform : "");
    *msg = "Rejected: Your clock is set too far in the future, or your timezone is not correct.";
    return -1;
  }
  if (ri->cache_info.published_on < now-ROUTER_MAX_AGE) {
    notice(LD_DIRSERV, "Publication time for router with nickname '%s' is too far (%d minutes) in the past. Not adding (ContactInfo '%s', platform '%s').",
           ri->nickname, (int)((now-ri->cache_info.published_on)/60),
           ri->contact_info ? ri->contact_info : "",
           ri->platform ? ri->platform : "");
    *msg = "Rejected: Server is expired, or your clock is too far in the past, or your timezone is not correct.";
    return -1;
  }
  if (dirserv_router_has_valid_address(ri) < 0) {
    notice(LD_DIRSERV, "Router with nickname '%s' has invalid address '%s'. Not adding (ContactInfo '%s', platform '%s').",
           ri->nickname, ri->address,
           ri->contact_info ? ri->contact_info : "",
           ri->platform ? ri->platform : "");
    *msg = "Rejected: Address is not an IP, or IP is a private address.";
    return -1;
  }
  /* Okay, looks like we're willing to accept this one. */
  switch (status) {
    case FP_NAMED:
      ri->is_named = ri->is_verified = 1;
      break;
    case FP_VALID:
      ri->is_named = 0;
      ri->is_verified = 1;
      break;
    case FP_INVALID:
      ri->is_named = ri->is_verified = 0;
      break;
    default:
      tor_assert(0);
  }

  return 0;
}

/** Parse the server descriptor at <b>desc</b> and maybe insert it into
 * the list of server descriptors. Set *<b>msg</b> to a message that
 * should be passed back to the origin of this descriptor.
 *
 * Return 2 if descriptor is well-formed and accepted;
 *  1 if well-formed and accepted but origin should hear *msg;
 *  0 if well-formed but redundant with one we already have;
 * -1 if it looks vaguely like a router descriptor but rejected;
 * -2 if we can't find a router descriptor in <b>desc</b>.
 */
int
dirserv_add_descriptor(const char *desc, const char **msg)
{
  int r;
  routerinfo_t *ri = NULL, *ri_old = NULL;
  tor_assert(msg);
  *msg = NULL;

  /* Check: is the descriptor syntactically valid? */
  ri = router_parse_entry_from_string(desc, NULL);
  if (!ri) {
    warn(LD_DIRSERV, "Couldn't parse uploaded server descriptor");
    *msg = "Rejected: Couldn't parse server descriptor.";
    return -2;
  }
  /* Check whether this descriptor is semantically identical to the last one
   * from this server.  (We do this here and not in router_add_to_routerlist
   * because we want to be able to accept the newest router descriptor that
   * another authority has, so we all converge on the same one.) */
  ri_old = router_get_by_digest(ri->cache_info.identity_digest);
  if (ri_old && ri_old->cache_info.published_on < ri->cache_info.published_on
      && router_differences_are_cosmetic(ri_old, ri)) {
    info(LD_DIRSERV,
         "Not replacing descriptor from '%s'; differences are cosmetic.",
         ri->nickname);
    *msg = "Not replacing router descriptor; no information has changed since the last one with this identity.";
    routerinfo_free(ri);
    control_event_or_authdir_new_descriptor("DROPPED", desc, *msg);
    return 0;
  }
  if ((r = router_add_to_routerlist(ri, msg, 0))<0) {
    if (r < -1) /* unless the routerinfo was fine, just out-of-date */
      control_event_or_authdir_new_descriptor("REJECTED", desc, *msg);
    return r == -1 ? 0 : -1;
  } else {
    smartlist_t *changed;
    control_event_or_authdir_new_descriptor("ACCEPTED", desc, *msg);

    changed = smartlist_create();
    smartlist_add(changed, ri);
    control_event_descriptors_changed(changed);
    smartlist_free(changed);
    if (!*msg) {
      *msg =  ri->is_verified ? "Verified server descriptor accepted" :
        "Unverified server descriptor accepted";
    }
    return r == 0 ? 2 : 1;
  }
}

/** Remove all descriptors whose nicknames or fingerprints no longer
 * are allowed by our fingerprint list. (Descriptors that used to be
 * good can become bad when we reload the fingerprint list.)
 */
static void
directory_remove_invalid(void)
{
  int i;
  int changed = 0;
  routerlist_t *rl = router_get_routerlist();

  for (i = 0; i < smartlist_len(rl->routers); ++i) {
    const char *msg;
    routerinfo_t *ent = smartlist_get(rl->routers, i);
    router_status_t r = dirserv_router_get_status(ent, &msg);
    switch (r) {
      case FP_REJECT:
        info(LD_DIRSERV, "Router '%s' is now rejected: %s",
            ent->nickname, msg?msg:"");
        routerlist_remove(rl, ent, i--, 0);
        changed = 1;
        break;
      case FP_NAMED:
        if (!ent->is_verified || !ent->is_named) {
          info(LD_DIRSERV,
               "Router '%s' is now verified and named.", ent->nickname);
          ent->is_verified = ent->is_named = 1;
          changed = 1;
        }
        break;
      case FP_VALID:
        if (!ent->is_verified || ent->is_named) {
          info(LD_DIRSERV, "Router '%s' is now verified.", ent->nickname);
          ent->is_verified = 1;
          ent->is_named = 0;
          changed = 1;
        }
        break;
      case FP_INVALID:
        if (ent->is_verified || ent->is_named) {
          info(LD_DIRSERV,
               "Router '%s' is no longer verified.", ent->nickname);
          ent->is_verified = ent->is_named = 0;
          changed = 1;
        }
        break;
    }
  }
  if (changed)
    directory_set_dirty();
}

/** Write a list of unregistered descriptors into a newly allocated
 * string and return it. Used by dirserv operators to keep track of
 * fast nodes that haven't registered.
 */
char *
dirserver_getinfo_unregistered(const char *question)
{
  router_status_t r;
  smartlist_t *answerlist;
  char buf[1024];
  char *answer;
  int min_bw = atoi(question);
  routerlist_t *rl = router_get_routerlist();

  answerlist = smartlist_create();
  SMARTLIST_FOREACH(rl->routers, routerinfo_t *, ent, {
    r = dirserv_router_get_status(ent, NULL);
    if (ent->bandwidthcapacity >= (size_t)min_bw &&
        ent->bandwidthrate >= (size_t)min_bw &&
        r != FP_NAMED) {
      /* then log this one */
      tor_snprintf(buf, sizeof(buf),
                   "%s: BW %d on '%s'.",
                   ent->nickname, ent->bandwidthcapacity,
                   ent->platform ? ent->platform : "");
      smartlist_add(answerlist, tor_strdup(buf));
    }
  });
  answer = smartlist_join_strings(answerlist, "\r\n", 0, NULL);
  SMARTLIST_FOREACH(answerlist, char *, cp, tor_free(cp));
  smartlist_free(answerlist);
  return answer;
}

/** Mark the directory as <b>dirty</b> -- when we're next asked for a
 * directory, we will rebuild it instead of reusing the most recently
 * generated one.
 */
void
directory_set_dirty(void)
{
  time_t now = time(NULL);

  if (!the_directory_is_dirty)
    the_directory_is_dirty = now;
  if (!runningrouters_is_dirty)
    runningrouters_is_dirty = now;
  if (!the_v2_networkstatus_is_dirty)
    the_v2_networkstatus_is_dirty = now;
}

/**
 * Allocate and return a description of the status of the server <b>desc</b>,
 * for use in a router-status line.  The server is listed
 * as running iff <b>is_live</b> is true.
 */
static char *
list_single_server_status(routerinfo_t *desc, int is_live)
{
  char buf[MAX_NICKNAME_LEN+HEX_DIGEST_LEN+4]; /* !nickname=$hexdigest\0 */
  char *cp;

  tor_assert(desc);

  cp = buf;
  if (!is_live) {
    *cp++ = '!';
  }
  if (desc->is_verified) {
    strlcpy(cp, desc->nickname, sizeof(buf)-(cp-buf));
    cp += strlen(cp);
    *cp++ = '=';
  }
  *cp++ = '$';
  base16_encode(cp, HEX_DIGEST_LEN+1, desc->cache_info.identity_digest,
                DIGEST_LEN);
  return tor_strdup(buf);
}

#define REACHABLE_TIMEOUT (60*60) /* an hour */
/* Make sure this is 3 times the value of get_dir_fetch_period() */

/** Treat a router as alive if
 *    - It's me, and I'm not hibernating.
 * or - we're connected to it and we've found it reachable recently. */
static int
dirserv_thinks_router_is_reachable(routerinfo_t *router, time_t now)
{
  connection_t *conn;
  if (router_is_me(router) && !we_are_hibernating())
    return 1;
  conn = connection_get_by_identity_digest(router->cache_info.identity_digest);
  if (conn && conn->state == OR_CONN_STATE_OPEN)
    return get_options()->AssumeReachable ||
           now < router->last_reachable + REACHABLE_TIMEOUT;
  return 0;
}

/** Return 1 if we're confident that there's a problem with
 * <b>router</b>'s reachability and its operator should be notified.
 */
int
dirserv_thinks_router_is_blatantly_unreachable(routerinfo_t *router, time_t now)
{
  connection_t *conn;
  if (router->is_hibernating)
    return 0;
  conn = connection_get_by_identity_digest(router->cache_info.identity_digest);
  if (conn && conn->state == OR_CONN_STATE_OPEN &&
      now >= router->last_reachable + 2*REACHABLE_TIMEOUT &&
      router->testing_since &&
      now >= router->testing_since + 2*REACHABLE_TIMEOUT)
    return 1;
  return 0;
}

/** Based on the routerinfo_ts in <b>routers</b>, allocate the
 * contents of a router-status line, and store it in
 * *<b>router_status_out</b>.  Return 0 on success, -1 on failure.
 */
int
list_server_status(smartlist_t *routers, char **router_status_out)
{
  /* List of entries in a router-status style: An optional !, then an optional
   * equals-suffixed nickname, then a dollar-prefixed hexdigest. */
  smartlist_t *rs_entries;
  time_t now = time(NULL);
  int authdir_mode = get_options()->AuthoritativeDir;
  tor_assert(router_status_out);

  rs_entries = smartlist_create();

  SMARTLIST_FOREACH(routers, routerinfo_t *, ri,
  {
    if (authdir_mode) {
      /* Update router status in routerinfo_t. */
      ri->is_running = dirserv_thinks_router_is_reachable(ri, now);
    }
    smartlist_add(rs_entries, list_single_server_status(ri, ri->is_running));
  });

  *router_status_out = smartlist_join_strings(rs_entries, " ", 0, NULL);

  SMARTLIST_FOREACH(rs_entries, char *, cp, tor_free(cp));
  smartlist_free(rs_entries);

  return 0;
}

/** Helper: Given pointers to two strings describing tor versions, return -1
 * if _a precedes _b, 1 if _b preceeds _a, and 0 if they are equivalent.
 * Used to sort a list of versions. */
static int
_compare_tor_version_str_ptr(const void **_a, const void **_b)
{
  const char *a = *_a, *b = *_b;
  int ca, cb;
  tor_version_t va, vb;
  ca = tor_version_parse(a, &va);
  cb = tor_version_parse(b, &vb);
  /* If they both parse, compare them. */
  if (!ca && !cb)
    return tor_version_compare(&va,&vb);
  /* If one parses, it comes first. */
  if (!ca && cb)
    return -1;
  if (ca && !cb)
    return 1;
  /* If neither parses, compare strings.  Also, the directory server admin needs
  ** to be smacked upside the head.  But Tor is tolerant and gentle. */
  return strcmp(a,b);
}

/* Given a (possibly empty) list of config_line_t, each line of which contains
 * a list of comma-separated version numbers surrounded by optional space,
 * allocate and return a new string containing the version numbers, in order,
 * separated by commas.  Used to generate Recommended(Client|Server)?Versions
 */
static char *
format_versions_list(config_line_t *ln)
{
  smartlist_t *versions;
  char *result;
  versions = smartlist_create();
  for ( ; ln; ln = ln->next) {
    smartlist_split_string(versions, ln->value, ",",
                           SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
  }
  smartlist_sort(versions, _compare_tor_version_str_ptr);
  result = smartlist_join_strings(versions,",",0,NULL);
  SMARTLIST_FOREACH(versions,char *,s,tor_free(s));
  smartlist_free(versions);
  return result;
}

/** Generate a new directory and write it into a newly allocated string.
 * Point *<b>dir_out</b> to the allocated string.  Sign the
 * directory with <b>private_key</b>.  Return 0 on success, -1 on
 * failure.
 */
int
dirserv_dump_directory_to_string(char **dir_out,
                                 crypto_pk_env_t *private_key)
{
  char *cp;
  char *router_status;
  char *identity_pkey; /* Identity key, DER64-encoded. */
  char *recommended_versions;
  char digest[DIGEST_LEN];
  char published[ISO_TIME_LEN+1];
  time_t published_on;
  char *buf = NULL;
  size_t buf_len;
  size_t identity_pkey_len;
  routerlist_t *rl = router_get_routerlist();

  tor_assert(dir_out);
  *dir_out = NULL;

  if (list_server_status(rl->routers, &router_status))
    return -1;

  if (crypto_pk_write_public_key_to_string(private_key,&identity_pkey,
                                           &identity_pkey_len)<0) {
    warn(LD_BUG,"write identity_pkey to string failed!");
    return -1;
  }

  recommended_versions = format_versions_list(get_options()->RecommendedVersions);

  published_on = time(NULL);
  format_iso_time(published, published_on);

  buf_len = 2048+strlen(recommended_versions)+
    strlen(router_status);
  SMARTLIST_FOREACH(rl->routers, routerinfo_t *, ri,
                    buf_len += ri->cache_info.signed_descriptor_len+1);
  buf = tor_malloc(buf_len);
  /* We'll be comparing against buf_len throughout the rest of the
     function, though strictly speaking we shouldn't be able to exceed
     it.  This is C, after all, so we may as well check for buffer
     overruns.*/

  tor_snprintf(buf, buf_len,
           "signed-directory\n"
           "published %s\n"
           "recommended-software %s\n"
           "router-status %s\n"
           "dir-signing-key\n%s\n",
           published, recommended_versions, router_status,
           identity_pkey);

  tor_free(recommended_versions);
  tor_free(router_status);
  tor_free(identity_pkey);

  cp = buf + strlen(buf);
  SMARTLIST_FOREACH(rl->routers, routerinfo_t *, ri,
    {
      size_t len = ri->cache_info.signed_descriptor_len;
      if (cp+len+1 >= buf+buf_len)
        goto truncated;
      memcpy(cp, ri->cache_info.signed_descriptor, len);
      cp += len;
      *cp++ = '\n'; /* add an extra newline in case somebody was depending on
                     * it. */
    });
  *cp = '\0';

  /* These multiple strlcat calls are inefficient, but dwarfed by the RSA
     signature.
  */
  if (strlcat(buf, "directory-signature ", buf_len) >= buf_len)
    goto truncated;
  if (strlcat(buf, get_options()->Nickname, buf_len) >= buf_len)
    goto truncated;
  if (strlcat(buf, "\n", buf_len) >= buf_len)
    goto truncated;

  if (router_get_dir_hash(buf,digest)) {
    warn(LD_BUG,"couldn't compute digest");
    tor_free(buf);
    return -1;
  }
  if (router_append_dirobj_signature(buf,buf_len,digest,private_key)<0) {
    tor_free(buf);
    return -1;
  }

  *dir_out = buf;
  return 0;
 truncated:
  warn(LD_BUG,"tried to exceed string length.");
  tor_free(buf);
  return -1;
}

/** Most recently generated encoded signed directory. (auth dirservers only.)*/
static cached_dir_t the_directory = { NULL, NULL, 0, 0, 0 };

/* Used only by non-auth dirservers: The directory and runningrouters we'll
 * serve when requested. */
static cached_dir_t cached_directory = { NULL, NULL, 0, 0, 0 };
static cached_dir_t cached_runningrouters = { NULL, NULL, 0, 0, 0 };

/* Used for other dirservers' v2 network statuses.  Map from hexdigest to
 * cached_dir_t. */
static digestmap_t *cached_v2_networkstatus = NULL;

/** Possibly replace the contents of <b>d</b> with the value of
 * <b>directory</b> published on <b>when</b>, unless <b>when</b> is older than
 * the last value, or too far in the future.
 *
 * Does not copy <b>directory</b>; free it if it isn't used.
 */
static void
set_cached_dir(cached_dir_t *d, char *directory, time_t when)
{
  time_t now = time(NULL);
  if (when<=d->published) {
    info(LD_DIRSERV, "Ignoring old directory; not caching.");
    tor_free(directory);
  } else if (when>=now+ROUTER_MAX_AGE) {
    info(LD_DIRSERV, "Ignoring future directory; not caching.");
    tor_free(directory);
  } else {
    /* if (when>d->published && when<now+ROUTER_MAX_AGE) */
    debug(LD_DIRSERV, "Caching directory.");
    tor_free(d->dir);
    d->dir = directory;
    d->dir_len = strlen(directory);
    tor_free(d->dir_z);
    if (tor_gzip_compress(&(d->dir_z), &(d->dir_z_len), d->dir, d->dir_len,
                          ZLIB_METHOD)) {
      warn(LD_BUG,"Error compressing cached directory");
    }
    d->published = when;
  }
}

/** Remove all storage held in <b>d</b>, but do not free <b>d</b> itself. */
static void
clear_cached_dir(cached_dir_t *d)
{
  tor_free(d->dir);
  tor_free(d->dir_z);
  memset(d, 0, sizeof(cached_dir_t));
}

/** Free all storage held by the cached_dir_t in <b>d</b>. */