r15779@tombo: nickm | 2008-01-01 23:43:24 -0500

 Use reference-counting to avoid allocating a zillion little addr_policy_t objects. (This is an old patch that had been sitting on my hard drive for a while.)


svn:r13017

8 files changed, 346 insertions, 207 deletions

diff --git a/src/common/util.c b/src/common/util.c
index 92fb7d63b0..24037c10b2 100644
--- a/src/common/util.c
+++ b/src/common/util.c
@@ -2382,7 +2382,7 @@ parse_port_range(const char *port, uint16_t *port_min_out,
 }
 
 /** Parse a string <b>s</b> in the format of
- * (IP(/mask|/mask-bits)?|*)(:*|port(-maxport)?)?, setting the various
+ * (IP(/mask|/mask-bits)?|*)(:(*|port(-maxport))?)?, setting the various
  * *out pointers as appropriate.  Return 0 on success, -1 on failure.
  */
 int
diff --git a/src/or/or.h b/src/or/or.h
index fa4a4d0538..5058ce5629 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1137,17 +1137,20 @@ typedef enum {
 
 /** A linked list of policy rules */
 typedef struct addr_policy_t {
-  addr_policy_action_t policy_type; /**< What to do when the policy matches.*/
-
-  /* XXXX020 make this ipv6-capable */
-  uint32_t addr; /**< Base address to accept or reject. */
+  int refcnt; /**< Reference count */
+  addr_policy_action_t policy_type:2;/**< What to do when the policy matches.*/
+  unsigned int is_private:1; /**< True iff this is the pseudo-address,
+                              * "private". */
+  unsigned int is_canonical:1; /**< True iff this policy is the canonical
+                                * copy (stored in a hash table to avoid
+                                * duplication of common policies) */
   maskbits_t maskbits; /**< Accept/reject all addresses <b>a</b> such that the
                  * first <b>maskbits</b> bits of <b>a</b> match
                  * <b>addr</b>. */
+  /* XXXX020 make this ipv6-capable */
+  uint32_t addr; /**< Base address to accept or reject. */
   uint16_t prt_min; /**< Lowest port number to accept/reject. */
   uint16_t prt_max; /**< Highest port number to accept/reject. */
-
-  struct addr_policy_t *next; /**< Next rule in list. */
 } addr_policy_t;
 
 /** A cached_dir_t represents a cacheable directory object, along with its
@@ -1265,8 +1268,8 @@ typedef struct {
   uint32_t bandwidthburst; /**< How large is this OR's token bucket? */
   /** How many bytes/s is this router known to handle? */
   uint32_t bandwidthcapacity;
-  addr_policy_t *exit_policy; /**< What streams will this OR permit
-                                      * to exit? */
+  smartlist_t *exit_policy; /**< What streams will this OR permit
+                             * to exit?  NULL for 'reject *:*'. */
   long uptime; /**< How many seconds the router claims to have been up */
   smartlist_t *declared_family; /**< Nicknames of router which this router
                                  * claims are its family. */
@@ -2280,7 +2283,7 @@ typedef struct {
    * means directly from the authorities) no matter our other config? */
   int FetchDirInfoEarly;
 
-  addr_policy_t *reachable_addr_policy; /**< Parsed from ReachableAddresses */
+  smartlist_t *reachable_addr_policy; /**< Parsed from ReachableAddresses */
 
   char *VirtualAddrNetwork; /**< Address and mask to hand out for virtual
                              * MAPADDRESS requests. */
@@ -3452,19 +3455,23 @@ int authdir_policy_baddir_address(uint32_t addr, uint16_t port);
 int authdir_policy_badexit_address(uint32_t addr, uint16_t port);
 
 int validate_addr_policies(or_options_t *options, char **msg);
+void policy_expand_private(smartlist_t **policy);
 void policies_parse_from_options(or_options_t *options);
 
-int cmp_addr_policies(addr_policy_t *a, addr_policy_t *b);
+addr_policy_t *addr_policy_get_canonical_entry(addr_policy_t *ent);
+int cmp_addr_policies(smartlist_t *a, smartlist_t *b);
 addr_policy_result_t compare_addr_to_addr_policy(uint32_t addr,
-                              uint16_t port, addr_policy_t *policy);
-int policies_parse_exit_policy(config_line_t *cfg, addr_policy_t **dest,
+                              uint16_t port, smartlist_t *policy);
+int policies_parse_exit_policy(config_line_t *cfg, smartlist_t **dest,
                                int rejectprivate, const char *local_address);
-int exit_policy_is_general_exit(addr_policy_t *policy);
-int policy_is_reject_star(addr_policy_t *policy);
+void policies_set_router_exitpolicy_to_reject_all(routerinfo_t *exitrouter);
+int exit_policy_is_general_exit(smartlist_t *policy);
+int policy_is_reject_star(smartlist_t *policy);
 int getinfo_helper_policies(control_connection_t *conn,
                             const char *question, char **answer);
-int policy_write_item(char *buf, size_t buflen, addr_policy_t *policy);
+int policy_write_item(char *buf, size_t buflen, addr_policy_t *item);
 
+void addr_policy_list_free(smartlist_t *p);
 void addr_policy_free(addr_policy_t *p);
 void policies_free_all(void);
 
@@ -3999,15 +4006,15 @@ routerinfo_t *router_parse_entry_from_string(const char *s, const char *end,
                                              const char *prepend_annotations);
 extrainfo_t *extrainfo_parse_entry_from_string(const char *s, const char *end,
                          int cache_copy, struct digest_ri_map_t *routermap);
-addr_policy_t *router_parse_addr_policy_from_string(const char *s,
-                                                    int assume_action);
+addr_policy_t *router_parse_addr_policy_item_from_string(const char *s,
+                                                  int assume_action);
 version_status_t tor_version_is_obsolete(const char *myversion,
                                          const char *versionlist);
 int tor_version_parse(const char *s, tor_version_t *out);
 int tor_version_as_new_as(const char *platform, const char *cutoff);
 int tor_version_compare(tor_version_t *a, tor_version_t *b);
 void sort_version_list(smartlist_t *lst, int remove_duplicates);
-void assert_addr_policy_ok(addr_policy_t *t);
+void assert_addr_policy_ok(smartlist_t *t);
 void dump_distinct_digest_count(int severity);
 
 networkstatus_v2_t *networkstatus_v2_parse_from_string(const char *s);
diff --git a/src/or/policies.c b/src/or/policies.c
index 0e3d49b498..51ace8e260 100644
--- a/src/or/policies.c
+++ b/src/or/policies.c
@@ -12,30 +12,74 @@ const char policies_c_id[] = \
  **/
 
 #include "or.h"
+#include "ht.h"
 
 /** Policy that addresses for incoming SOCKS connections must match. */
-static addr_policy_t *socks_policy = NULL;
+static smartlist_t *socks_policy = NULL;
 /** Policy that addresses for incoming directory connections must match. */
-static addr_policy_t *dir_policy = NULL;
+static smartlist_t *dir_policy = NULL;
 /** Policy that addresses for incoming router descriptors must match in order
  * to be published by us. */
-static addr_policy_t *authdir_reject_policy = NULL;
+static smartlist_t *authdir_reject_policy = NULL;
 /** Policy that addresses for incoming router descriptors must match in order
  * to be marked as valid in our networkstatus. */
-static addr_policy_t *authdir_invalid_policy = NULL;
+static smartlist_t *authdir_invalid_policy = NULL;
 /** Policy that addresses for incoming router descriptors must <b>not</b>
  * match in order to not be marked as BadDirectory. */
-static addr_policy_t *authdir_baddir_policy = NULL;
+static smartlist_t *authdir_baddir_policy = NULL;
 /** Policy that addresses for incoming router descriptors must <b>not</b>
  * match in order to not be marked as BadExit. */
-static addr_policy_t *authdir_badexit_policy = NULL;
+static smartlist_t *authdir_badexit_policy = NULL;
 
 /** Parsed addr_policy_t describing which addresses we believe we can start
  * circuits at. */
-static addr_policy_t *reachable_or_addr_policy = NULL;
+static smartlist_t *reachable_or_addr_policy = NULL;
 /** Parsed addr_policy_t describing which addresses we believe we can connect
  * to directories at. */
-static addr_policy_t *reachable_dir_addr_policy = NULL;
+static smartlist_t *reachable_dir_addr_policy = NULL;
+
+/** Replace all "private" entries in *<b>policy</b> with their expanded
+ * equivalents. */
+void
+policy_expand_private(smartlist_t **policy)
+{
+  static const char *private_nets[] = {
+    "0.0.0.0/8", "169.254.0.0/16",
+    "127.0.0.0/8", "192.168.0.0/16", "10.0.0.0/8", "172.16.0.0/12", NULL };
+  uint16_t port_min, port_max;
+
+  int i;
+  smartlist_t *tmp;
+
+  if (!*policy)
+    return;
+
+  tmp = smartlist_create();
+
+  SMARTLIST_FOREACH(*policy, addr_policy_t *, p,
+  {
+     if (! p->is_private) {
+       smartlist_add(tmp, p);
+       continue;
+     }
+     for (i = 0; private_nets[i]; ++i) {
+       addr_policy_t policy;
+       memcpy(&policy, p, sizeof(addr_policy_t));
+       policy.is_private = 0;
+       policy.is_canonical = 0;
+       if (parse_addr_and_port_range(private_nets[i],
+                                     &policy.addr,
+                                     &policy.maskbits, &port_min, &port_max)) {
+         tor_assert(0);
+       }
+       smartlist_add(tmp, addr_policy_get_canonical_entry(&policy));
+     }
+     addr_policy_free(p);
+  });
+
+  smartlist_free(*policy);
+  *policy = tmp;
+}
 
 /**
  * Given a linked list of config lines containing "allow" and "deny"
@@ -43,21 +87,18 @@ static addr_policy_t *reachable_dir_addr_policy = NULL;
  * if any tokens are malformed, else return 0.
  */
 static int
-parse_addr_policy(config_line_t *cfg, addr_policy_t **dest,
+parse_addr_policy(config_line_t *cfg, smartlist_t **dest,
                   int assume_action)
 {
-  addr_policy_t **nextp;
+  smartlist_t *result;
   smartlist_t *entries;
+  addr_policy_t *item;
   int r = 0;
 
   if (!cfg)
     return 0;
 
-  nextp = dest;
-
-  while (*nextp)
-    nextp = &((*nextp)->next);
-
+  result = smartlist_create();
   entries = smartlist_create();
   for (; cfg; cfg = cfg->next) {
     smartlist_split_string(entries, cfg->value, ",",
@@ -65,11 +106,9 @@ parse_addr_policy(config_line_t *cfg, addr_policy_t **dest,
     SMARTLIST_FOREACH(entries, const char *, ent,
     {
       log_debug(LD_CONFIG,"Adding new entry '%s'",ent);
-      *nextp = router_parse_addr_policy_from_string(ent, assume_action);
-      if (*nextp) {
-        /* Advance nextp to the end of the policy. */
-        while (*nextp)
-          nextp = &((*nextp)->next);
+      item = router_parse_addr_policy_item_from_string(ent, assume_action);
+      if (item) {
+        smartlist_add(result, item);
       } else {
         log_warn(LD_CONFIG,"Malformed policy '%s'.", ent);
         r = -1;
@@ -79,6 +118,19 @@ parse_addr_policy(config_line_t *cfg, addr_policy_t **dest,
     smartlist_clear(entries);
   }
   smartlist_free(entries);
+  if (r == -1) {
+    addr_policy_list_free(result);
+  } else {
+    policy_expand_private(&result);
+
+    if (*dest) {
+      smartlist_add_all(*dest, result);
+      smartlist_free(result);
+    } else {
+      *dest = result;
+    }
+  }
+
   return r;
 }
 
@@ -96,7 +148,7 @@ parse_reachable_addresses(void)
              "Both ReachableDirAddresses and ReachableORAddresses are set. "
              "ReachableAddresses setting will be ignored.");
   }
-  addr_policy_free(reachable_or_addr_policy);
+  addr_policy_list_free(reachable_or_addr_policy);
   reachable_or_addr_policy = NULL;
   if (!options->ReachableORAddresses && options->ReachableAddresses)
     log_info(LD_CONFIG,
@@ -110,7 +162,7 @@ parse_reachable_addresses(void)
              options->ReachableORAddresses ? "OR" : "");
   }
 
-  addr_policy_free(reachable_dir_addr_policy);
+  addr_policy_list_free(reachable_dir_addr_policy);
   reachable_dir_addr_policy = NULL;
   if (!options->ReachableDirAddresses && options->ReachableAddresses)
     log_info(LD_CONFIG,
@@ -139,7 +191,7 @@ firewall_is_fascist_or(void)
  */
 static int
 addr_policy_permits_address(uint32_t addr, uint16_t port,
-                            addr_policy_t *policy)
+                            smartlist_t *policy)
 {
   addr_policy_result_t p;
   p = compare_addr_to_addr_policy(addr, port, policy);
@@ -237,7 +289,7 @@ authdir_policy_badexit_address(uint32_t addr, uint16_t port)
 int
 validate_addr_policies(or_options_t *options, char **msg)
 {
-  addr_policy_t *addr_policy=NULL;
+  smartlist_t *addr_policy=NULL;
   *msg = NULL;
 
   if (policies_parse_exit_policy(options->ExitPolicy, &addr_policy,
@@ -267,7 +319,7 @@ validate_addr_policies(or_options_t *options, char **msg)
     REJECT("Error in AuthDirInvalid entry.");
 
 err:
-  addr_policy_free(addr_policy);
+  addr_policy_list_free(addr_policy);
   return *msg ? -1 : 0;
 #undef REJECT
 }
@@ -277,18 +329,19 @@ err:
  * Ignore port specifiers.
  */
 static void
-load_policy_from_option(config_line_t *config, addr_policy_t **policy,
+load_policy_from_option(config_line_t *config, smartlist_t **policy,
                         int assume_action)
 {
-  addr_policy_t *n;
-  addr_policy_free(*policy);
+  addr_policy_list_free(*policy);
   *policy = NULL;
   parse_addr_policy(config, policy, assume_action);
-  /* ports aren't used. */
-  for (n=*policy; n; n = n->next) {
-    n->prt_min = 1;
-    n->prt_max = 65535;
-  }
+  if (!*policy)
+    return;
+  SMARTLIST_FOREACH(*policy, addr_policy_t *, n, {
+      /* ports aren't used. */
+      n->prt_min = 1;
+      n->prt_max = 65535;
+    });
 }
 
 /** Set all policies based on <b>options</b>, which should have been validated
@@ -317,6 +370,8 @@ cmp_single_addr_policy(addr_policy_t *a, addr_policy_t *b)
   int r;
   if ((r=((int)a->policy_type - (int)b->policy_type)))
     return r;
+  if ((r=((int)a->is_private - (int)b->is_private)))
+    return r;
   if ((r=((int)a->addr - (int)b->addr)))
     return r;
   if ((r=((int)a->maskbits - (int)b->maskbits)))
@@ -331,23 +386,88 @@ cmp_single_addr_policy(addr_policy_t *a, addr_policy_t *b)
 /** Like cmp_single_addr_policy() above, but looks at the
  * whole set of policies in each case. */
 int
-cmp_addr_policies(addr_policy_t *a, addr_policy_t *b)
+cmp_addr_policies(smartlist_t *a, smartlist_t *b)
 {
-  int r;
-  while (a && b) {
-    if ((r=cmp_single_addr_policy(a,b)))
+  int r, i;
+  int len_a = a ? smartlist_len(a) : 0;
+  int len_b = b ? smartlist_len(b) : 0;
+
+  for (i = 0; i < len_a && i < len_b; ++i) {
+    if ((r = cmp_single_addr_policy(smartlist_get(a, i), smartlist_get(b, i))))
       return r;
-    a = a->next;
-    b = b->next;
   }
-  if (!a && !b)
+  if (i == len_a && i == len_b)
     return 0;
-  if (a)
+  if (i < len_a)
     return -1;
   else
     return 1;
 }
 
+/** Node in hashtable used to store address policy entries. */
+typedef struct policy_map_ent_t {
+  HT_ENTRY(policy_map_ent_t) node;
+  addr_policy_t *policy;
+} policy_map_ent_t;
+
+static HT_HEAD(policy_map, policy_map_ent_t) policy_root;
+
+/** Return true iff a and b are equal. */
+static INLINE int
+policy_eq(policy_map_ent_t *a, policy_map_ent_t *b)
+{
+  return cmp_single_addr_policy(a->policy, b->policy) == 0;
+}
+
+/** Return a hashcode for <b>ent</b> */
+static unsigned int
+policy_hash(policy_map_ent_t *ent)
+{
+  addr_policy_t *a = ent->policy;
+  unsigned int r;
+  if (a->is_private)
+    r = 0x1234abcd;
+  else
+    r = (unsigned int)a->addr;
+  r += a->prt_min << 8;
+  r += a->prt_max << 16;
+  r += a->maskbits;
+  if (a->policy_type == ADDR_POLICY_REJECT)
+    r ^= 0xffffffff;
+
+  return r;
+}
+
+HT_PROTOTYPE(policy_map, policy_map_ent_t, node, policy_hash,
+             policy_eq)
+HT_GENERATE(policy_map, policy_map_ent_t, node, policy_hash,
+            policy_eq, 0.6, malloc, realloc, free)
+
+/** Given a pointer to an addr_policy_t, return a copy of the pointer to the
+ * "canonical" copy of that addr_policy_t; the canonical copy is a single
+ * reference-counted object. */
+addr_policy_t *
+addr_policy_get_canonical_entry(addr_policy_t *e)
+{
+  policy_map_ent_t search, *found;
+  if (e->is_canonical)
+    return e;
+
+  search.policy = e;
+  found = HT_FIND(policy_map, &policy_root, &search);
+  if (!found) {
+    found = tor_malloc_zero(sizeof(policy_map_ent_t));
+    found->policy = tor_memdup(e, sizeof(addr_policy_t));
+    found->policy->is_canonical = 1;
+    found->policy->refcnt = 1;
+    HT_INSERT(policy_map, &policy_root, found);
+  }
+
+  tor_assert(!cmp_single_addr_policy(found->policy, e));
+  ++found->policy->refcnt;
+  return found->policy;
+}
+
 /** Decide whether a given addr:port is definitely accepted,
  * definitely rejected, probably accepted, or probably rejected by a
  * given policy.  If <b>addr</b> is 0, we don't know the IP of the
@@ -367,15 +487,17 @@ cmp_addr_policies(addr_policy_t *a, addr_policy_t *b)
  */
 addr_policy_result_t
 compare_addr_to_addr_policy(uint32_t addr, uint16_t port,
-                            addr_policy_t *policy)
+                            smartlist_t *policy)
 {
   int maybe_reject = 0;
   int maybe_accept = 0;
   int match = 0;
   int maybe = 0;
-  addr_policy_t *tmpe;
+  int i, len;
+  len = policy ? smartlist_len(policy) : 0;
 
-  for (tmpe=policy; tmpe; tmpe=tmpe->next) {
+  for (i = 0; i < len; ++i) {
+    addr_policy_t *tmpe = smartlist_get(policy, i);
     maybe = 0;
     if (!addr) {
       /* Address is unknown. */
@@ -420,6 +542,7 @@ compare_addr_to_addr_policy(uint32_t addr, uint16_t port,
       }
     }
   }
+
   /* accept all by default. */
   return maybe_reject ? ADDR_POLICY_PROBABLY_ACCEPTED : ADDR_POLICY_ACCEPTED;
 }
@@ -468,7 +591,7 @@ addr_policy_intersects(addr_policy_t *a, addr_policy_t *b)
 /** Add the exit policy described by <b>more</b> to <b>policy</b>.
  */
 static void
-append_exit_policy_string(addr_policy_t **policy, const char *more)
+append_exit_policy_string(smartlist_t **policy, const char *more)
 {
   config_line_t tmp;
 
@@ -480,38 +603,40 @@ append_exit_policy_string(addr_policy_t **policy, const char *more)
 
 /** Detect and excise "dead code" from the policy *<b>dest</b>. */
 static void
-exit_policy_remove_redundancies(addr_policy_t **dest)
+exit_policy_remove_redundancies(smartlist_t *dest)
 {
-  addr_policy_t *ap, *tmp, *victim, *previous;
+  addr_policy_t *ap, *tmp, *victim;
+  int i, j;
 
   /* Step one: find a *:* entry and cut off everything after it. */
-  for (ap=*dest; ap; ap=ap->next) {
+  for (i = 0; i < smartlist_len(dest); ++i) {
+    ap = smartlist_get(dest, i);
     if (ap->maskbits == 0 && ap->prt_min <= 1 && ap->prt_max >= 65535) {
       /* This is a catch-all line -- later lines are unreachable. */
-      if (ap->next) {
-        addr_policy_free(ap->next);
-        ap->next = NULL;
+      while (i+1 < smartlist_len(dest)) {
+        victim = smartlist_get(dest, i+1);
+        smartlist_del(dest, i+1);
+        addr_policy_free(victim);
       }
+      break;
     }
   }
 
   /* Step two: for every entry, see if there's a redundant entry
    * later on, and remove it. */
-  for (ap=*dest; ap; ap=ap->next) {
-    tmp=ap;
-    while (tmp) {
-      if (tmp->next && addr_policy_covers(ap, tmp->next)) {
+  for (i = 0; i < smartlist_len(dest)-1; ++i) {
+    ap = smartlist_get(dest, i);
+    for (j = i+1; j < smartlist_len(dest); ++j) {
+      tmp = smartlist_get(dest, j);
+      tor_assert(j > i);
+      if (addr_policy_covers(ap, tmp)) {
         char p1[POLICY_BUF_LEN], p2[POLICY_BUF_LEN];
-        policy_write_item(p1, sizeof(p1), tmp->next);
+        policy_write_item(p1, sizeof(p1), tmp);
         policy_write_item(p2, sizeof(p2), ap);
-        log(LOG_DEBUG, LD_CONFIG, "Removing exit policy %s.  It is made "
-            "redundant by %s.", p1, p2);
-        victim = tmp->next;
-        tmp->next = victim->next;
-        victim->next = NULL;
-        addr_policy_free(victim);
-      } else {
-        tmp=tmp->next;
+        log(LOG_DEBUG, LD_CONFIG, "Removing exit policy %s (%d).  It is made "
+            "redundant by %s (%d).", p1, j, p2, i);
+        smartlist_del_keeporder(dest, j--);
+        addr_policy_free(tmp);
       }
     }
   }
@@ -523,15 +648,14 @@ exit_policy_remove_redundancies(addr_policy_t **dest)
    *
    * Anybody want to doublecheck the logic here? XXX
    */
-  ap = *dest;
-  previous = NULL;
-  while (ap) {
-    for (tmp=ap->next; tmp; tmp=tmp->next) {
+  for (i = 0; i < smartlist_len(dest)-1; ++i) {
+    ap = smartlist_get(dest, i);
+    for (j = i+1; j < smartlist_len(dest); ++j) {
+      tor_assert(j > i);
+      tmp = smartlist_get(dest, j);
       if (ap->policy_type != tmp->policy_type) {
-        if (addr_policy_intersects(ap, tmp)) {
-          tmp = NULL; /* so that we advance previous and ap */
+        if (addr_policy_intersects(ap, tmp))
           break;
-        }
       } else { /* policy_types are equal. */
         if (addr_policy_covers(tmp, ap)) {
           char p1[POLICY_BUF_LEN], p2[POLICY_BUF_LEN];
@@ -539,27 +663,12 @@ exit_policy_remove_redundancies(addr_policy_t **dest)
           policy_write_item(p2, sizeof(p2), tmp);
           log(LOG_DEBUG, LD_CONFIG, "Removing exit policy %s.  It is already "
               "covered by %s.", p1, p2);
-          victim = ap;
-          ap = ap->next;
-
-          if (previous) {
-            assert(previous->next == victim);
-            previous->next = victim->next;
-          } else {
-            assert(*dest == victim);
-            *dest = victim->next;
-          }
-
-          victim->next = NULL;
-          addr_policy_free(victim);
+          smartlist_del_keeporder(dest, i--);
+          addr_policy_free(ap);
           break;
         }
       }
     }
-    if (!tmp) {
-      previous = ap;
-      ap = ap->next;
-    }
   }
 }
 
@@ -576,7 +685,7 @@ exit_policy_remove_redundancies(addr_policy_t **dest)
  * else return 0.
  */
 int
-policies_parse_exit_policy(config_line_t *cfg, addr_policy_t **dest,
+policies_parse_exit_policy(config_line_t *cfg, smartlist_t **dest,
                            int rejectprivate, const char *local_address)
 {
   if (rejectprivate) {
@@ -591,22 +700,33 @@ policies_parse_exit_policy(config_line_t *cfg, addr_policy_t **dest,
     return -1;
   append_exit_policy_string(dest, DEFAULT_EXIT_POLICY);
 
-  exit_policy_remove_redundancies(dest);
+  exit_policy_remove_redundancies(*dest);
+
   return 0;
 }
 
+/** DOCDOC */
+void
+policies_set_router_exitpolicy_to_reject_all(routerinfo_t *r)
+{
+  addr_policy_t *item;
+  addr_policy_list_free(r->exit_policy);
+  r->exit_policy = smartlist_create();
+  item = router_parse_addr_policy_item_from_string("reject *:*", -1);
+  smartlist_add(r->exit_policy, item);
+}
+
 /** Return true iff <b>ri</b> is "useful as an exit node", meaning
  * it allows exit to at least one /8 address space for at least
  * two of ports 80, 443, and 6667. */
 int
-exit_policy_is_general_exit(addr_policy_t *policy)
+exit_policy_is_general_exit(smartlist_t *policy)
 {
   static const int ports[] = { 80, 443, 6667 };
   int n_allowed = 0;
   int i;
   for (i = 0; i < 3; ++i) {
-    struct addr_policy_t *p = policy;
-    for ( ; p; p = p->next) {
+    SMARTLIST_FOREACH(policy, addr_policy_t *, p, {
       if (p->prt_min > ports[i] || p->prt_max < ports[i])
         continue; /* Doesn't cover our port. */
       if (p->maskbits > 8)
@@ -618,7 +738,7 @@ exit_policy_is_general_exit(addr_policy_t *policy)
         ++n_allowed;
         break; /* stop considering this port */
       }
-    }
+    });
   }
   return n_allowed >= 2;
 }
@@ -626,16 +746,16 @@ exit_policy_is_general_exit(addr_policy_t *policy)
 /** Return false if <b>policy</b> might permit access to some addr:port;
  * otherwise if we are certain it rejects everything, return true. */
 int
-policy_is_reject_star(addr_policy_t *p)
+policy_is_reject_star(smartlist_t *policy)
 {
-  for ( ; p; p = p->next) {
+  SMARTLIST_FOREACH(policy, addr_policy_t *, p, {
     if (p->policy_type == ADDR_POLICY_ACCEPT)
       return 0;
     else if (p->policy_type == ADDR_POLICY_REJECT &&
              p->prt_min <= 1 && p->prt_max == 65535 &&
              p->maskbits == 0)
       return 1;
-  }
+  });
   return 1;
 }
 
@@ -647,14 +767,21 @@ policy_write_item(char *buf, size_t buflen, addr_policy_t *policy)
   struct in_addr in;
   size_t written = 0;
   char addrbuf[INET_NTOA_BUF_LEN];
+  const char *addrpart;
   int result;
 
   in.s_addr = htonl(policy->addr);
   tor_inet_ntoa(&in, addrbuf, sizeof(addrbuf));
   /* write accept/reject 1.2.3.4 */
+  if (policy->is_private)
+    addrpart = "private";
+  else if (policy->maskbits == 0)
+    addrpart = "*";
+  else
+    addrpart = addrbuf;
   result = tor_snprintf(buf, buflen, "%s %s",
             policy->policy_type == ADDR_POLICY_ACCEPT ? "accept" : "reject",
-            policy->maskbits == 0 ? "*" : addrbuf);
+                        addrpart);
   if (result < 0)
     return -1;
   written += strlen(buf);
@@ -708,14 +835,30 @@ getinfo_helper_policies(control_connection_t *conn,
 
 /** Release all storage held by <b>p</b>. */
 void
-addr_policy_free(addr_policy_t *p)
+addr_policy_list_free(smartlist_t *lst)
 {
-  addr_policy_t *e;
+  if (!lst) return;
+  SMARTLIST_FOREACH(lst, addr_policy_t *, policy, addr_policy_free(policy));
+  smartlist_free(lst);
+}
 
-  while (p) {
-    e = p;
-    p = p->next;
-    tor_free(e);
+/** Release all storage held by <b>p</b>. */
+void
+addr_policy_free(addr_policy_t *p)
+{
+  if (p) {
+    if (--p->refcnt <= 0) {
+      if (p->is_canonical) {
+        policy_map_ent_t search, *found;
+        search.policy = p;
+        found = HT_REMOVE(policy_map, &policy_root, &search);
+        if (found) {
+          tor_assert(p == found->policy);
+          tor_free(found);
+        }
+      }
+      tor_free(p);
+    }
   }
 }
 
@@ -723,17 +866,17 @@ addr_policy_free(addr_policy_t *p)
 void
 policies_free_all(void)
 {
-  addr_policy_free(reachable_or_addr_policy);
+  addr_policy_list_free(reachable_or_addr_policy);
   reachable_or_addr_policy = NULL;
-  addr_policy_free(reachable_dir_addr_policy);
+  addr_policy_list_free(reachable_dir_addr_policy);
   reachable_dir_addr_policy = NULL;
-  addr_policy_free(socks_policy);
+  addr_policy_list_free(socks_policy);
   socks_policy = NULL;
-  addr_policy_free(dir_policy);
+  addr_policy_list_free(dir_policy);
   dir_policy = NULL;
-  addr_policy_free(authdir_reject_policy);
+  addr_policy_list_free(authdir_reject_policy);
   authdir_reject_policy = NULL;
-  addr_policy_free(authdir_invalid_policy);
+  addr_policy_list_free(authdir_invalid_policy);
   authdir_invalid_policy = NULL;
 }
 
diff --git a/src/or/relay.c b/src/or/relay.c
index 650a3d567a..d5e81c1b72 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -764,9 +764,7 @@ connection_edge_process_end_not_open(
                  "Exitrouter '%s' seems to be more restrictive than its exit "
                  "policy. Not using this router as exit for now.",
                  exitrouter->nickname);
-          addr_policy_free(exitrouter->exit_policy);
-          exitrouter->exit_policy =
-            router_parse_addr_policy_from_string("reject *:*", -1);
+          policies_set_router_exitpolicy_to_reject_all(exitrouter);
         }
         /* rewrite it to an IP if we learned one. */
         if (addressmap_rewrite(conn->socks_request->address,
@@ -819,9 +817,7 @@ connection_edge_process_end_not_open(
       case END_STREAM_REASON_HIBERNATING:
       case END_STREAM_REASON_RESOURCELIMIT:
         if (exitrouter) {
-          addr_policy_free(exitrouter->exit_policy);
-          exitrouter->exit_policy =
-            router_parse_addr_policy_from_string("reject *:*", -1);
+          policies_set_router_exitpolicy_to_reject_all(exitrouter);
         }
         if (conn->_base.chosen_exit_optional) {
           /* stop wanting a specific exit */
diff --git a/src/or/router.c b/src/or/router.c
index cdceac44ad..c9482275c6 100644
--- a/src/or/router.c
+++ b/src/or/router.c
@@ -1631,26 +1631,28 @@ router_dump_router_to_string(char *s, size_t maxlen, routerinfo_t *router,
   }
 
   /* Write the exit policy to the end of 's'. */
-  tmpe = router->exit_policy;
   if (dns_seems_to_be_broken()) {
     /* DNS is screwed up; don't claim to be an exit. */
     strlcat(s+written, "reject *:*\n", maxlen-written);
     written += strlen("reject *:*\n");
     tmpe = NULL;
-  }
-  for ( ; tmpe; tmpe=tmpe->next) {
-    result = policy_write_item(s+written, maxlen-written, tmpe);
-    if (result < 0) {
-      log_warn(LD_BUG,"descriptor policy_write_item ran out of room!");
-      return -1;
-    }
-    tor_assert(result == (int)strlen(s+written));
-    written += result;
-    if (written+2 > maxlen) {
-      log_warn(LD_BUG,"descriptor policy_write_item ran out of room (2)!");
-      return -1;
+  } else if (router->exit_policy) {
+    int i;
+    for (i = 0; i < smartlist_len(router->exit_policy); ++i) {
+      tmpe = smartlist_get(router->exit_policy, i);
+      result = policy_write_item(s+written, maxlen-written, tmpe);
+      if (result < 0) {
+        log_warn(LD_BUG,"descriptor policy_write_item ran out of room!");
+        return -1;
+      }
+      tor_assert(result == (int)strlen(s+written));
+      written += result;
+      if (written+2 > maxlen) {
+        log_warn(LD_BUG,"descriptor policy_write_item ran out of room (2)!");
+        return -1;
+      }
+      s[written++] = '\n';
     }
-    s[written++] = '\n';
   }
 
   if (written+256 > maxlen) { /* Not enough room for signature. */
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 32b0dbaf45..3ead01fd8a 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -2079,7 +2079,7 @@ routerinfo_free(routerinfo_t *router)
     SMARTLIST_FOREACH(router->declared_family, char *, s, tor_free(s));
     smartlist_free(router->declared_family);
   }
-  addr_policy_free(router->exit_policy);
+  addr_policy_list_free(router->exit_policy);
 
   /* XXXX020 Remove once 414/417 is fixed. But I have a hunch... */
   memset(router, 77, sizeof(routerinfo_t));
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index 6ec4e4bcce..eb7949000b 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -1242,6 +1242,7 @@ router_parse_entry_from_string(const char *s, const char *end,
                       log_warn(LD_DIR,"Error in exit policy");
                       goto err;
                     });
+  policy_expand_private(&router->exit_policy);
 
   if ((tok = find_first_by_keyword(tokens, K_FAMILY)) && tok->n_args) {
     int i;
@@ -2426,7 +2427,7 @@ networkstatus_parse_detached_signatures(const char *s, const char *eos)
  * ADDR_POLICY_REJECT) for items that specify no action.
  */
 addr_policy_t *
-router_parse_addr_policy_from_string(const char *s, int assume_action)
+router_parse_addr_policy_item_from_string(const char *s, int assume_action)
 {
   directory_token_t *tok = NULL;
   const char *cp, *eos;
@@ -2475,13 +2476,14 @@ router_parse_addr_policy_from_string(const char *s, int assume_action)
 static int
 router_add_exit_policy(routerinfo_t *router, directory_token_t *tok)
 {
-  addr_policy_t *newe, **tmpe;
+  addr_policy_t *newe;
   newe = router_parse_addr_policy(tok);
   if (!newe)
     return -1;
-  for (tmpe = &router->exit_policy; *tmpe; tmpe=&((*tmpe)->next))
-    ;
-  *tmpe = newe;
+  if (! router->exit_policy)
+    router->exit_policy = smartlist_create();
+
+  smartlist_add(router->exit_policy, newe);
 
   return 0;
 }
@@ -2491,7 +2493,7 @@ router_add_exit_policy(routerinfo_t *router, directory_token_t *tok)
 static addr_policy_t *
 router_parse_addr_policy(directory_token_t *tok)
 {
-  addr_policy_t *newe;
+  addr_policy_t newe;
   char *arg;
 
   tor_assert(tok->tp == K_REJECT || tok->tp == K_ACCEPT);
@@ -2503,20 +2505,19 @@ router_parse_addr_policy(directory_token_t *tok)
   if (!strcmpstart(arg,"private"))
     return router_parse_addr_policy_private(tok);
 
-  newe = tor_malloc_zero(sizeof(addr_policy_t));
+  memset(&newe, 0, sizeof(newe));
 
-  newe->policy_type = (tok->tp == K_REJECT) ? ADDR_POLICY_REJECT
+  newe.policy_type = (tok->tp == K_REJECT) ? ADDR_POLICY_REJECT
     : ADDR_POLICY_ACCEPT;
 
-  if (parse_addr_and_port_range(arg, &newe->addr, &newe->maskbits,
-                                &newe->prt_min, &newe->prt_max))
+  if (parse_addr_and_port_range(arg, &newe.addr, &newe.maskbits,
+                                &newe.prt_min, &newe.prt_max))
     goto policy_read_failed;
 
-  return newe;
+  return addr_policy_get_canonical_entry(&newe);
 
 policy_read_failed:
   log_warn(LD_DIR,"Couldn't parse line %s. Dropping", escaped(arg));
-  tor_free(newe);
   return NULL;
 }
 
@@ -2527,17 +2528,14 @@ policy_read_failed:
 static addr_policy_t *
 router_parse_addr_policy_private(directory_token_t *tok)
 {
-  static const char *private_nets[] = {
-    "0.0.0.0/8", "169.254.0.0/16",
-    "127.0.0.0/8", "192.168.0.0/16", "10.0.0.0/8", "172.16.0.0/12",NULL };
-  char *arg;
-  addr_policy_t *result, **nextp;
-  int net;
+  const char *arg;
   uint16_t port_min, port_max;
+  addr_policy_t result;
 
   arg = tok->args[0];
   if (strcmpstart(arg, "private"))
     return NULL;
+
   arg += strlen("private");
   arg = (char*) eat_whitespace(arg);
   if (!arg || *arg != ':')
@@ -2546,37 +2544,26 @@ router_parse_addr_policy_private(directory_token_t *tok)
   if (parse_port_range(arg+1, &port_min, &port_max)<0)
     return NULL;
 
-  nextp = &result;
-  for (net = 0; private_nets[net]; ++net) {
-    char buf[POLICY_BUF_LEN];
-    *nextp = tor_malloc_zero(sizeof(addr_policy_t));
-    (*nextp)->policy_type = (tok->tp == K_REJECT) ? ADDR_POLICY_REJECT
-      : ADDR_POLICY_ACCEPT;
-    tor_snprintf(buf, sizeof(buf), "%s%s",
-                 private_nets[net], arg);
-    if (parse_addr_and_port_range(buf,
-                                  &(*nextp)->addr, &(*nextp)->maskbits,
-                                  &(*nextp)->prt_min, &(*nextp)->prt_max)) {
-      log_warn(LD_BUG, "Couldn't parse an address range we generated!");
-      return NULL;
-    }
-    nextp = &(*nextp)->next;
-  }
+  memset(&result, 0, sizeof(result));
+  result.policy_type = (tok->tp == K_REJECT) ? ADDR_POLICY_REJECT
+    : ADDR_POLICY_ACCEPT;
+  result.is_private = 1;
+  result.prt_min = port_min;
+  result.prt_max = port_max;
 
-  return result;
+  return addr_policy_get_canonical_entry(&result);
 }
 
 /** Log and exit if <b>t</b> is malformed */
 void
-assert_addr_policy_ok(addr_policy_t *t)
+assert_addr_policy_ok(smartlist_t *lst)
 {
-  while (t) {
+  if (!lst) return;
+  SMARTLIST_FOREACH(lst, addr_policy_t *, t, {
     tor_assert(t->policy_type == ADDR_POLICY_REJECT ||
                t->policy_type == ADDR_POLICY_ACCEPT);
     tor_assert(t->prt_min <= t->prt_max);
-    t = t->next;
-  }
-
+  });
 }
 
 /*
diff --git a/src/or/test.c b/src/or/test.c
index 8a54916143..fed4128167 100644
--- a/src/or/test.c
+++ b/src/or/test.c
@@ -2193,18 +2193,16 @@ test_dir_format(void)
   r1->nickname = tor_strdup("Magri");
   r1->platform = tor_strdup(platform);
 
-  ex1 = tor_malloc_zero(sizeof(addr_policy_t));;
-  ex2 = tor_malloc_zero(sizeof(addr_policy_t));;
+  ex1 = tor_malloc_zero(sizeof(addr_policy_t));
+  ex2 = tor_malloc_zero(sizeof(addr_policy_t));
   ex1->policy_type = ADDR_POLICY_ACCEPT;
   ex1->addr = 0;
   ex1->maskbits = 0;
   ex1->prt_min = ex1->prt_max = 80;
-  ex1->next = ex2;
   ex2->policy_type = ADDR_POLICY_REJECT;
   ex2->addr = 18 << 24;
   ex2->maskbits = 8;
   ex2->prt_min = ex2->prt_max = 24;
-  ex2->next = NULL;
   r2 = tor_malloc_zero(sizeof(routerinfo_t));
   r2->address = tor_strdup("1.1.1.1");
   r2->addr = 0x0a030201u; /* 10.3.2.1 */
@@ -2215,7 +2213,9 @@ test_dir_format(void)
   r2->onion_pkey = crypto_pk_dup_key(pk2);
   r2->identity_pkey = crypto_pk_dup_key(pk1);
   r2->bandwidthrate = r2->bandwidthburst = r2->bandwidthcapacity = 3000;
-  r2->exit_policy = ex1;
+  r2->exit_policy = smartlist_create();
+  smartlist_add(r2->exit_policy, &ex2);
+  smartlist_add(r2->exit_policy, &ex1);
   r2->nickname = tor_strdup("Fred");
 
   test_assert(!crypto_pk_write_public_key_to_string(pk1, &pk1_str,
@@ -2922,18 +2922,22 @@ test_v3_networkstatus(void)
 static void
 test_policies(void)
 {
-  addr_policy_t *policy, *policy2;
+  smartlist_t *policy, *policy2;
+  addr_policy_t *p;
   tor_addr_t tar;
   config_line_t line;
 
-  policy = router_parse_addr_policy_from_string("reject 192.168.0.0/16:*",-1);
-  test_eq(NULL, policy->next);
-  test_eq(ADDR_POLICY_REJECT, policy->policy_type);
+  policy = smartlist_create();
+
+  p = router_parse_addr_policy_item_from_string("reject 192.168.0.0/16:*",-1);
+  test_eq(ADDR_POLICY_REJECT, p->policy_type);
   tor_addr_from_ipv4(&tar, 0xc0a80000u);
-  test_assert(policy->addr == 0xc0a80000u);
-  test_eq(16, policy->maskbits);
-  test_eq(1, policy->prt_min);
-  test_eq(65535, policy->prt_max);
+  test_assert(p->addr == 0xc0a80000u);
+  test_eq(16, p->maskbits);
+  test_eq(1, p->prt_min);
+  test_eq(65535, p->prt_max);
+
+  smartlist_add(policy, p);
 
   test_assert(ADDR_POLICY_ACCEPTED ==
           compare_addr_to_addr_policy(0x01020304u, 2, policy));
@@ -2955,8 +2959,8 @@ test_policies(void)
   test_assert(!policy_is_reject_star(policy2));
   test_assert(policy_is_reject_star(policy));
 
-  addr_policy_free(policy);
-  addr_policy_free(policy2);
+  addr_policy_list_free(policy);
+  addr_policy_list_free(policy2);
 
   /* make sure compacting logic works. */
   policy = NULL;
@@ -2967,9 +2971,9 @@ test_policies(void)
   test_assert(policy);
   //test_streq(policy->string, "accept *:80");
   //test_streq(policy->next->string, "reject *:*");
-  test_eq_ptr(policy->next->next, NULL);
+  test_eq(smartlist_len(policy), 2);
 
-  addr_policy_free(policy);
+  addr_policy_list_free(policy);
 }
 
 static void