r17188@tombo: nickm | 2008-07-18 14:35:18 -0400

 Add new ExcludeExitNodes option.  Also add a new routerset type to handle Exclude[Exit]Nodes.  It is optimized for O(1) membership tests, so as to make choosing a random router run in O(N_routers) time instead of in O(N_routers*N_Excluded_Routers).


svn:r16061

7 files changed, 317 insertions, 35 deletions

diff --git a/ChangeLog b/ChangeLog
index 34f25e8ce3..6f50e3c7e2 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -15,6 +15,14 @@ Changes in version 0.2.1.3-alpha - 2008-07-xx
       tend to have multiple test circuits going through a single entry
       guard, which makes our bandwidth test less accurate. Fixes part
       of bug 654; patch contributed by Josh Albrecht.
+    - Add an ExcludeExitNodes option so users can list a set of nodes
+      that should be be excluded from the exit node position, but
+      allowed elsewhere.  Implements proposal 151.
+    - Allow address patterns (e.g., 255.128.0.0/16) to appear in
+      ExcludeNodes and ExcludeExitNodes lists.
+    - Change the implementation of ExcludeNodes and ExcludeExitNodes
+      to be more efficient.  Formerly it was quadratic in the number
+      of servers; now it should be linear.  Fixes bug 509.
 
   o Minor bugfixes:
     - Change the contrib/tor.logrotate script so it makes the new
diff --git a/doc/tor.1.in b/doc/tor.1.in
index 0275c21dbd..381fe79414 100644
--- a/doc/tor.1.in
+++ b/doc/tor.1.in
@@ -422,8 +422,16 @@ you are reliable and high-bandwidth enough to be a useful server.)
 .LP
 .TP
 \fBExcludeNodes \fR\fInode\fR,\fInode\fR,\fI...\fP
-A list of identity fingerprints or nicknames of nodes to never use when
-building a circuit.
+A list of identity fingerprints, nicknames, and address patterns of
+nodes to never use when building a circuit.  (Example: ExcludeNodes
+SlowServer, $ABCDEFFFFFFFFFFFFFFF, 255.254.0.0/8)
+.LP
+.TP
+\fBExcludeExitNodes \fR\fInode\fR,\fInode\fR,\fI...\fP
+A list of identity fingerprints, nicknames, and address patterns of
+nodes to never use when picking an exit node.  Note that any node
+listed in ExcludeNodes is automatically considered to be part of this
+list.
 .LP
 .TP
 \fBEntryNodes \fR\fInode\fR,\fInode\fR,\fI...\fP
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 72dcc1c2e3..354a9767e1 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -1174,7 +1174,7 @@ choose_good_exit_server_general(routerlist_t *dir, int need_uptime,
   smartlist_t *connections;
   int best_support = -1;
   int n_best_support=0;
-  smartlist_t *sl, *preferredexits, *excludedexits;
+  smartlist_t *sl, *preferredexits;
   routerinfo_t *router;
   or_options_t *options = get_options();
 
@@ -1262,9 +1262,6 @@ choose_good_exit_server_general(routerlist_t *dir, int need_uptime,
   preferredexits = smartlist_create();
   add_nickname_list_to_smartlist(preferredexits,options->ExitNodes,1);
 
-  excludedexits = smartlist_create();
-  add_nickname_list_to_smartlist(excludedexits,options->ExcludeNodes,0);
-
   sl = smartlist_create();
 
   /* If any routers definitely support any pending connections, choose one
@@ -1274,7 +1271,7 @@ choose_good_exit_server_general(routerlist_t *dir, int need_uptime,
       if (n_supported[i] == best_support)
         smartlist_add(sl, smartlist_get(dir->routers, i));
 
-    smartlist_subtract(sl,excludedexits);
+    routerset_subtract_routers(sl,options->_ExcludeExitNodesUnion);
     if (options->StrictExitNodes || smartlist_overlap(sl,preferredexits))
       smartlist_intersect(sl,preferredexits);
     router = routerlist_sl_choose_by_bandwidth(sl, WEIGHT_FOR_EXIT);
@@ -1294,7 +1291,6 @@ choose_good_exit_server_general(routerlist_t *dir, int need_uptime,
                  need_capacity?", fast":"",
                  need_uptime?", stable":"");
         smartlist_free(preferredexits);
-        smartlist_free(excludedexits);
         smartlist_free(sl);
         tor_free(n_supported);
         return choose_good_exit_server_general(dir, 0, 0);
@@ -1316,7 +1312,7 @@ choose_good_exit_server_general(routerlist_t *dir, int need_uptime,
         }
       }
 
-      smartlist_subtract(sl,excludedexits);
+      routerset_subtract_routers(sl,options->_ExcludeExitNodesUnion);
       if (options->StrictExitNodes || smartlist_overlap(sl,preferredexits))
         smartlist_intersect(sl,preferredexits);
         /* XXX sometimes the above results in null, when the requested
@@ -1330,7 +1326,6 @@ choose_good_exit_server_general(routerlist_t *dir, int need_uptime,
   }
 
   smartlist_free(preferredexits);
-  smartlist_free(excludedexits);
   smartlist_free(sl);
   tor_free(n_supported);
   if (router) {
@@ -1363,15 +1358,15 @@ choose_good_exit_server(uint8_t purpose, routerlist_t *dir,
   switch (purpose) {
     case CIRCUIT_PURPOSE_C_GENERAL:
       if (is_internal) /* pick it like a middle hop */
-        return router_choose_random_node(NULL, get_options()->ExcludeNodes,
-               NULL, need_uptime, need_capacity, 0,
-               get_options()->_AllowInvalid & ALLOW_INVALID_MIDDLE, 0, 0);
+        return router_choose_random_node(NULL, NULL,
+              NULL, get_options()->ExcludeNodes, need_uptime, need_capacity, 0,
+              get_options()->_AllowInvalid & ALLOW_INVALID_MIDDLE, 0, 0);
       else
         return choose_good_exit_server_general(dir,need_uptime,need_capacity);
     case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
       return router_choose_random_node(
-               options->RendNodes, options->RendExcludeNodes,
-               NULL, need_uptime, need_capacity, 0,
+               options->RendNodes, options->RendExcludeNodes, NULL,
+               options->ExcludeNodes, need_uptime, need_capacity, 0,
                options->_AllowInvalid & ALLOW_INVALID_RENDEZVOUS, 0, 0);
   }
   log_warn(LD_BUG,"Unhandled purpose %d", purpose);
@@ -1592,7 +1587,7 @@ choose_good_middle_server(uint8_t purpose,
   if (purpose == CIRCUIT_PURPOSE_TESTING)
     preferred = compute_preferred_testing_list(options->TestVia);
   choice = router_choose_random_node(preferred,
-           options->ExcludeNodes, excluded,
+           NULL, excluded, options->ExcludeNodes,
            state->need_uptime, state->need_capacity, 0,
            options->_AllowInvalid & ALLOW_INVALID_MIDDLE, 0, 0);
   tor_free(preferred);
@@ -1627,6 +1622,7 @@ choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state)
     routerlist_add_family(excluded, r);
   }
   if (firewall_is_fascist_or()) {
+    /*XXXX021 This can slow things down a lot; use a smarter implementation */
     /* exclude all ORs that listen on the wrong port */
     routerlist_t *rl = router_get_routerlist();
     int i;
@@ -1647,8 +1643,10 @@ choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state)
   }
 
   choice = router_choose_random_node(
-           NULL, options->ExcludeNodes,
-           excluded, state ? state->need_uptime : 0,
+           NULL, NULL,
+           excluded,
+           options->ExcludeNodes,
+           state ? state->need_uptime : 0,
            state ? state->need_capacity : 0,
            state ? 0 : 1,
            options->_AllowInvalid & ALLOW_INVALID_ENTRY, 0, 0);
@@ -1845,7 +1843,7 @@ entry_guard_set_status(entry_guard_t *e, routerinfo_t *ri,
   else if (!options->UseBridges && !ri->is_possible_guard &&
            !router_nickname_is_in_list(ri, options->EntryNodes))
     *reason = "not recommended as a guard";
-  else if (router_nickname_is_in_list(ri, options->ExcludeNodes))
+  else if (routerset_contains_router(options->ExcludeNodes, ri))
     *reason = "excluded";
 
   if (*reason && ! e->bad_since) {
diff --git a/src/or/config.c b/src/or/config.c
index 7f483a745e..a7ec8bf931 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -37,6 +37,8 @@ typedef enum config_type_t {
   CONFIG_TYPE_LINELIST_V,   /**< Catch-all "virtual" option to summarize
                              * context-sensitive config lines when fetching.
                              */
+  CONFIG_TYPE_ROUTERSET,    /**< A list of router names, addrs, and fps,
+                             * parsed into a routerset_t. */
   CONFIG_TYPE_OBSOLETE,     /**< Obsolete (ignored) option. */
 } config_type_t;
 
@@ -194,8 +196,9 @@ static config_var_t _option_vars[] = {
   V(EnforceDistinctSubnets,      BOOL,     "1"),
   V(EntryNodes,                  STRING,   NULL),
   V(TestingEstimatedDescriptorPropagationTime, INTERVAL, "10 minutes"),
-  V(ExcludeNodes,                STRING,   NULL),
-  V(ExitNodes,                   STRING,   NULL),
+  V(ExcludeNodes,                ROUTERSET, NULL),
+  V(ExcludeExitNodes,            ROUTERSET, NULL),
+  V(ExitNodes,                   STRING, NULL),
   V(ExitPolicy,                  LINELIST, NULL),
   V(ExitPolicyRejectPrivate,     BOOL,     "1"),
   V(FallbackNetworkstatusFile,   FILENAME,
@@ -1647,6 +1650,19 @@ config_assign_value(config_format_t *fmt, or_options_t *options,
     }
     break;
 
+  case CONFIG_TYPE_ROUTERSET:
+    if (*(routerset_t**)lvalue) {
+      routerset_free(*(routerset_t**)lvalue);
+    }
+    *(routerset_t**)lvalue = routerset_new();
+    if (routerset_parse(*(routerset_t**)lvalue, c->value, c->key)<0) {
+      tor_snprintf(buf, sizeof(buf), "Invalid exit list '%s' for option '%s'",
+                   c->value, c->key);
+      *msg = tor_strdup(buf);
+      return -1;
+    }
+    break;
+
   case CONFIG_TYPE_CSV:
     if (*(smartlist_t**)lvalue) {
       SMARTLIST_FOREACH(*(smartlist_t**)lvalue, char *, cp, tor_free(cp));
@@ -1896,6 +1912,9 @@ get_assigned_option(config_format_t *fmt, or_options_t *options,
       result->value = tor_strdup(*(int*)value ? "1" : "0");
       escape_val = 0; /* Can't need escape. */
       break;
+    case CONFIG_TYPE_ROUTERSET:
+      result->value = routerset_to_string(*(routerset_t**)value);
+      break;
     case CONFIG_TYPE_CSV:
       if (*(smartlist_t**)value)
         result->value =
@@ -2101,6 +2120,11 @@ option_clear(config_format_t *fmt, or_options_t *options, config_var_t *var)
     case CONFIG_TYPE_MEMUNIT:
       *(uint64_t*)lvalue = 0;
       break;
+    case CONFIG_TYPE_ROUTERSET:
+      if (*(routerset_t**)lvalue) {
+        routerset_free(*(routerset_t**)lvalue);
+        *(routerset_t**)lvalue = NULL;
+      }
     case CONFIG_TYPE_CSV:
       if (*(smartlist_t**)lvalue) {
         SMARTLIST_FOREACH(*(smartlist_t **)lvalue, char *, cp, tor_free(cp));
@@ -2906,6 +2930,12 @@ options_validate(or_options_t *old_options, or_options_t *options,
     REJECT("TransPort and TransListenAddress are disabled in this build.");
 #endif
 
+  if (options->ExcludeExitNodes || options->ExcludeNodes) {
+    options->_ExcludeExitNodesUnion = routerset_new();
+    routerset_union(options->_ExcludeExitNodesUnion,options->ExcludeExitNodes);
+    routerset_union(options->_ExcludeExitNodesUnion,options->ExcludeNodes);
+  }
+
   if (options->StrictExitNodes &&
       (!options->ExitNodes || !strlen(options->ExitNodes)) &&
       (!old_options ||
@@ -3284,8 +3314,6 @@ options_validate(or_options_t *old_options, or_options_t *options,
     return -1;
   if (check_nickname_list(options->EntryNodes, "EntryNodes", msg))
     return -1;
-  if (check_nickname_list(options->ExcludeNodes, "ExcludeNodes", msg))
-    return -1;
   if (check_nickname_list(options->RendNodes, "RendNodes", msg))
     return -1;
   if (check_nickname_list(options->RendNodes, "RendExcludeNodes", msg))
@@ -5121,6 +5149,7 @@ getinfo_helper_config(control_connection_t *conn,
         case CONFIG_TYPE_DOUBLE: type = "Float"; break;
         case CONFIG_TYPE_BOOL: type = "Boolean"; break;
         case CONFIG_TYPE_ISOTIME: type = "Time"; break;
+        case CONFIG_TYPE_ROUTERSET: type = "RouterList"; break;
         case CONFIG_TYPE_CSV: type = "CommaList"; break;
         case CONFIG_TYPE_LINELIST: type = "LineList"; break;
         case CONFIG_TYPE_LINELIST_S: type = "Dependant"; break;
diff --git a/src/or/or.h b/src/or/or.h
index e53923d97b..b81db6f7af 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -2028,8 +2028,12 @@ typedef struct {
                         * stop building circuits? */
   int StrictEntryNodes; /**< Boolean: When none of our EntryNodes are up, do we
                          * stop building circuits? */
-  char *ExcludeNodes; /**< Comma-separated list of nicknames of ORs not to
-                       * use in circuits. */
+  struct routerset_t *ExcludeNodes; /**< Comma-separated list of nicknames of
+                       * ORs not to use in circuits. */
+  struct routerset_t *ExcludeExitNodes; /**<DODOC */
+
+  /** Union of ExcludeNodes and ExcludeExitNodes */
+  struct routerset_t *_ExcludeExitNodesUnion;
 
   char *RendNodes; /**< Comma-separated list of nicknames used as introduction
                     * points. */
@@ -4032,9 +4036,11 @@ typedef enum {
 routerinfo_t *routerlist_sl_choose_by_bandwidth(smartlist_t *sl,
                                                 bandwidth_weight_rule_t rule);
 routerstatus_t *routerstatus_sl_choose_by_bandwidth(smartlist_t *sl);
+/* XXXX021. This is a truly hideous interface. */
 routerinfo_t *router_choose_random_node(const char *preferred,
                                         const char *excluded,
                                         smartlist_t *excludedsmartlist,
+                                        struct routerset_t *excludedset,
                                         int need_uptime, int need_capacity,
                                         int need_guard,
                                         int allow_invalid, int strict,
@@ -4108,6 +4114,22 @@ void routerlist_assert_ok(routerlist_t *rl);
 const char *esc_router_info(routerinfo_t *router);
 void routers_sort_by_identity(smartlist_t *routers);
 
+typedef struct routerset_t routerset_t;
+
+routerset_t *routerset_new(void);
+int routerset_parse(routerset_t *target, const char *s,
+                    const char *description);
+void routerset_union(routerset_t *target, const routerset_t *source);
+int routerset_contains_router(const routerset_t *set, routerinfo_t *ri);
+int routerset_contains_routerstatus(const routerset_t *set,
+                                    routerstatus_t *rs);
+void routerset_get_all_routers(smartlist_t *out, const routerset_t *routerset,
+                               int running_only);
+void routerset_subtract_routers(smartlist_t *out,
+                                const routerset_t *routerset);
+char *routerset_to_string(const routerset_t *routerset);
+void routerset_free(routerset_t *routerset);
+
 int hid_serv_get_responsible_directories(smartlist_t *responsible_dirs,
                                          const char *id);
 int hid_serv_acting_as_directory(void);
diff --git a/src/or/rendservice.c b/src/or/rendservice.c
index 1965b12859..5e739c5285 100644
--- a/src/or/rendservice.c
+++ b/src/or/rendservice.c
@@ -1229,6 +1229,7 @@ rend_services_introduce(void)
   int changed, prev_intro_nodes;
   smartlist_t *intro_routers, *exclude_routers;
   time_t now;
+  or_options_t *options = get_options();
 
   intro_routers = smartlist_create();
   exclude_routers = smartlist_create();
@@ -1303,7 +1304,8 @@ rend_services_introduce(void)
     /* The directory is now here. Pick three ORs as intro points. */
     for (j=prev_intro_nodes; j < NUM_INTRO_POINTS; ++j) {
       router = router_choose_random_node(service->intro_prefer_nodes,
-               service->intro_exclude_nodes, exclude_routers, 1, 0, 0,
+               service->intro_exclude_nodes, exclude_routers,
+               options->ExcludeNodes, 1, 0, 0,
                get_options()->_AllowInvalid & ALLOW_INVALID_INTRODUCTION,
                0, 0);
       if (!router) {
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 3d61fa5d11..0d6f9b56f8 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -1706,7 +1706,8 @@ routerstatus_sl_choose_by_bandwidth(smartlist_t *sl)
 /** Return a random running router from the routerlist.  If any node
  * named in <b>preferred</b> is available, pick one of those.  Never
  * pick a node named in <b>excluded</b>, or whose routerinfo is in
- * <b>excludedsmartlist</b>, even if they are the only nodes
+ * <b>excludedsmartlist</b>, or whose routerinfo matches <b>excludedset</b>,
+ * even if they are the only nodes
  * available.  If <b>strict</b> is true, never pick any node besides
  * those in <b>preferred</b>.
  * If <b>need_uptime</b> is non-zero and any router has more than
@@ -1723,6 +1724,7 @@ routerinfo_t *
 router_choose_random_node(const char *preferred,
                           const char *excluded,
                           smartlist_t *excludedsmartlist,
+                          routerset_t *excludedset,
                           int need_uptime, int need_capacity,
                           int need_guard,
                           int allow_invalid, int strict,
@@ -1752,6 +1754,8 @@ router_choose_random_node(const char *preferred,
     smartlist_subtract(sl,excludednodes);
     if (excludedsmartlist)
       smartlist_subtract(sl,excludedsmartlist);
+    if (excludedset)
+      routerset_subtract_routers(sl,excludedset);
     choice = smartlist_choose(sl);
     smartlist_free(sl);
   }
@@ -1765,6 +1769,8 @@ router_choose_random_node(const char *preferred,
     smartlist_subtract(sl,excludednodes);
     if (excludedsmartlist)
       smartlist_subtract(sl,excludedsmartlist);
+    if (excludedset)
+      routerset_subtract_routers(sl,excludedset);
 
     if (need_capacity || need_guard)
       choice = routerlist_sl_choose_by_bandwidth(sl, rule);
@@ -1781,7 +1787,7 @@ router_choose_random_node(const char *preferred,
                need_uptime?", stable":"",
                need_guard?", guard":"");
       choice = router_choose_random_node(
-        NULL, excluded, excludedsmartlist,
+        NULL, excluded, excludedsmartlist, excludedset,
         0, 0, 0, allow_invalid, 0, weight_for_exit);
     }
   }
@@ -1798,12 +1804,13 @@ router_choose_random_node(const char *preferred,
   return choice;
 }
 
-/** Return true iff the digest of <b>router</b>'s identity key,
- * encoded in hexadecimal, matches <b>hexdigest</b> (which is
- * optionally prefixed with a single dollar sign).  Return false if
+/** Helper: Return true iff the <b>identity_digest</b> and <b>nickname</b>
+ * combination of a router, encoded in hexadecimal, matches <b>hexdigest</b>
+ * (which is optionally prefixed with a single dollar sign).  Return false if
  * <b>hexdigest</b> is malformed, or it doesn't match.  */
 static INLINE int
-router_hex_digest_matches(routerinfo_t *router, const char *hexdigest)
+hex_digest_matches(const char *hexdigest, const char *identity_digest,
+                   const char *nickname, int is_named)
 {
   char digest[DIGEST_LEN];
   size_t len;
@@ -1817,15 +1824,26 @@ router_hex_digest_matches(routerinfo_t *router, const char *hexdigest)
   else if (len > HEX_DIGEST_LEN &&
            (hexdigest[HEX_DIGEST_LEN] == '=' ||
             hexdigest[HEX_DIGEST_LEN] == '~')) {
-    if (strcasecmp(hexdigest+HEX_DIGEST_LEN+1, router->nickname))
+    if (strcasecmp(hexdigest+HEX_DIGEST_LEN+1, nickname))
       return 0;
-    if (hexdigest[HEX_DIGEST_LEN] == '=' && !router->is_named)
+    if (hexdigest[HEX_DIGEST_LEN] == '=' && !is_named)
       return 0;
   }
 
   if (base16_decode(digest, DIGEST_LEN, hexdigest, HEX_DIGEST_LEN)<0)
     return 0;
-  return (!memcmp(digest, router->cache_info.identity_digest, DIGEST_LEN));
+  return (!memcmp(digest, identity_digest, DIGEST_LEN));
+}
+
+/** Return true iff the digest of <b>router</b>'s identity key,
+ * encoded in hexadecimal, matches <b>hexdigest</b> (which is
+ * optionally prefixed with a single dollar sign).  Return false if
+ * <b>hexdigest</b> is malformed, or it doesn't match.  */
+static INLINE int
+router_hex_digest_matches(routerinfo_t *router, const char *hexdigest)
+{
+  return hex_digest_matches(hexdigest, router->cache_info.identity_digest,
+                            router->nickname, router->is_named);
 }
 
 /** Return true if <b>router</b>'s nickname matches <b>nickname</b>
@@ -4645,6 +4663,203 @@ routers_sort_by_identity(smartlist_t *routers)
   smartlist_sort(routers, _compare_routerinfo_by_id_digest);
 }
 
+/** A routerset specifies constraints on a set of possible routerinfos, based
+ * on their names, identities, or addresses.  It is optimized for determining
+ * whether a router is a member or not, in O(1+P) time, where P is the number
+ * of address policy constraints. */
+struct routerset_t {
+  /** A list of strings for the elements of the policy.  Each string is either
+   * a nickname, a hexadecimal identity fingerprint, or an address policy.  A
+   * router belongs to the set if its nickname OR its identity OR its address
+   * matches an entry here. */
+  smartlist_t *list;
+  /** A map from lowercase nicknames of routers in the set to (void*)1 */
+  strmap_t *names;
+  /** A map from identity digests routers in the set to (void*)1 */
+  digestmap_t *digests;
+  /** An address policy for routers in the set.  For implementation reasons,
+   * a router belongs to the set if it is _rejected_ by this policy. */
+  smartlist_t *policies;
+};
+
+/** Return a new empty routerset. */
+routerset_t *
+routerset_new(void)
+{
+  routerset_t *result = tor_malloc_zero(sizeof(routerset_t));
+  result->list = smartlist_create();
+  result->names = strmap_new();
+  result->digests = digestmap_new();
+  result->policies = smartlist_create();
+  return result;
+}
+
+/** Parse the string <b>s</b> to create a set of routerset entries, and add
+ * them to <b>target</b>.  In log messages, refer to the string as
+ * <b>description</b>.  Return 0 on success, -1 on failure.
+ *
+ * Three kinds of elements are allowed in routersets: nicknames, IP address
+ * patterns, and fingerprints.  They may be surrounded by optional space, and
+ * mst be separated by commas.
+ */
+int
+routerset_parse(routerset_t *target, const char *s, const char *description)
+{
+  int r = 0;
+  smartlist_t *list = smartlist_create();
+  smartlist_split_string(list, s, ",",
+                         SPLIT_SKIP_SPACE | SPLIT_IGNORE_BLANK, 0);
+  SMARTLIST_FOREACH(list, char *, nick, {
+      addr_policy_t *p;
+      if (is_legal_hexdigest(nick)) {
+        char d[DIGEST_LEN];
+        if (*nick == '$')
+          ++nick;
+        base16_decode(d, sizeof(d), nick, HEX_DIGEST_LEN);
+        digestmap_set(target->digests, d, (void*)1);
+      } else if (is_legal_nickname(nick)) {
+        strmap_set_lc(target->names, nick, (void*)1);
+      } else if ((strchr(nick,'.') || strchr(nick, '*')) &&
+                 (p = router_parse_addr_policy_item_from_string(
+                                             nick, ADDR_POLICY_REJECT))) {
+        smartlist_add(target->policies, p);
+      } else {
+        log_warn(LD_CONFIG, "Nickname '%s' in %s is misformed.", nick,
+                 description);
+        r = -1;
+        tor_free(nick);
+        SMARTLIST_DEL_CURRENT(list, nick);
+      }
+    });
+  smartlist_add_all(target->list, list);
+  smartlist_free(list);
+  return r;
+}
+
+/** Add all members of the set <b>source</b> to <b>target</b>. */
+void
+routerset_union(routerset_t *target, const routerset_t *source)
+{
+  char *s;
+  tor_assert(target);
+  if (!source || !source->list)
+    return;
+  s = routerset_to_string(source);
+  routerset_parse(target, s, "other routerset");
+  tor_free(s);
+}
+
+/** Helper.  Return true iff <b>set</b> contains a router based on the other
+ * provided fields. */
+static int
+routerset_contains(const routerset_t *set, uint32_t addr, uint16_t orport,
+                   const char *nickname, const char *id_digest, int is_named)
+{
+  if (!set || !set->list) return 0;
+  (void) is_named; /* not supported */
+  if (strmap_get_lc(set->names, nickname))
+    return 1;
+  if (digestmap_get(set->digests, id_digest))
+    return 1;
+  if (compare_addr_to_addr_policy(addr, orport, set->policies)
+      == ADDR_POLICY_REJECT)
+    return 1;
+  return 0;
+}
+
+/** Return true iff <b>ri</b> is in <b>set</b>. */
+int
+routerset_contains_router(const routerset_t *set, routerinfo_t *ri)
+{
+  return routerset_contains(set,
+                            ri->addr,
+                            ri->or_port,
+                            ri->nickname,
+                            ri->cache_info.identity_digest,
+                            ri->is_named);
+}
+
+/** Return true iff <b>rs</b> is in <b>set</b>. */
+int
+routerset_contains_routerstatus(const routerset_t *set, routerstatus_t *rs)
+{
+  return routerset_contains(set,
+                            rs->addr,
+                            rs->or_port,
+                            rs->nickname,
+                            rs->identity_digest,
+                            rs->is_named);
+}
+
+/** Add every known routerinfo_t that is a member of <b>routerset</b> to
+ * <b>out</b>.  If <b>running_only</b>, only add the running ones. */
+void
+routerset_get_all_routers(smartlist_t *out, const routerset_t *routerset,
+                          int running_only)
+{
+  tor_assert(out);
+  if (!routerset || !routerset->list)
+    return;
+  if (!warned_nicknames)
+    warned_nicknames = smartlist_create();
+  SMARTLIST_FOREACH(routerset->list, const char *, name, {
+    routerinfo_t *router = router_get_by_nickname(name, 1);
+    if (router) {
+      if (!running_only || router->is_running)
+        smartlist_add(out, router);
+    }
+  });
+  if (smartlist_len(routerset->policies)) {
+    routerlist_t *rl = router_get_routerlist();
+    SMARTLIST_FOREACH(rl->routers, routerinfo_t *, router,
+      if (compare_addr_to_addr_policy(router->addr, router->or_port,
+               routerset->policies) == ADDR_POLICY_REJECT) {
+        if (!running_only || router->is_running)
+          smartlist_add(out, router);
+      });
+  }
+}
+
+/** Remove every routerinfo_t from <b>lst</b> that is in <b>routerset</b>. */
+void
+routerset_subtract_routers(smartlist_t *lst, const routerset_t *routerset)
+{
+  tor_assert(lst);
+  if (!routerset)
+    return;
+  SMARTLIST_FOREACH(lst, routerinfo_t *, r, {
+      if (routerset_contains_router(routerset, r)) {
+        SMARTLIST_DEL_CURRENT(lst, r);
+      }
+    });
+}
+
+/** Return a new string that when parsed by routerset_parse_string() will
+ * yield <b>set</b>. */
+char *
+routerset_to_string(const routerset_t *set)
+{
+  if (!set || !set->list)
+    return tor_strdup("");
+  return smartlist_join_strings(set->list, ",", 0, NULL);
+}
+
+/** Free all storage held in <b>routerset</b>. */
+void
+routerset_free(routerset_t *routerset)
+{
+  SMARTLIST_FOREACH(routerset->list, char *, cp, tor_free(cp));
+  smartlist_free(routerset->list);
+  SMARTLIST_FOREACH(routerset->policies, addr_policy_t *, p,
+                    addr_policy_free(p));
+  smartlist_free(routerset->policies);
+
+  strmap_free(routerset->names, NULL);
+  digestmap_free(routerset->digests, NULL);
+
+  tor_free(routerset);
+}
+
 /** Determine the routers that are responsible for <b>id</b> (binary) and
  * add pointers to those routers' routerstatus_t to <b>responsible_dirs</b>.
  * Return -1 if we're returning an empty smartlist, else return 0.