Merge branch 'ticket7570_7571'

Conflicts:
	src/or/routerlist.c

13 files changed, 559 insertions, 147 deletions

diff --git a/changes/ipv6_automap b/changes/ipv6_automap
new file mode 100644
index 0000000000..1b44585277
--- /dev/null
+++ b/changes/ipv6_automap
@@ -0,0 +1,19 @@
+  o Minor features:
+
+    - AutomapHostsOnResolve now support IPv6 addresses. By default, we
+      prefer to hand out virtual IPv6 addresses, since there are more of
+      them and we can't run out. To override this behavior and make
+      IPv4 addresses preferred, set NoPreferIPv6Automap on whatever
+      SOCKSPort or DNSPort you're using for resolving. Implements
+      ticket #7571.
+
+    - AutomapHostsOnResolve responses are now randomized, to avoid
+      annoying situations where Tor is restarted and applications
+      connect to the wrong addresses.
+
+    - We never try more than 1000 times to pick a virtual address
+      when AutomapHostsOnResolve is set. That's good enough so long
+      as we aren't close to handing out our entire virtual address
+      space; if you're getting there, it's best to switch to IPv6
+      virtual addresses anyway.
+
diff --git a/changes/prop205-simplified b/changes/prop205-simplified
new file mode 100644
index 0000000000..25d204d598
--- /dev/null
+++ b/changes/prop205-simplified
@@ -0,0 +1,25 @@
+  o Major features (client-side DNS):
+
+    - The updating and usage of DNS cache is now configurable on a
+      per- client-port level. SOCKSPort, DNSPort, etc lines may now
+      contain {No,}Cache{IPv4,IPv6,}DNS lines to indicate that we
+      shouldn't cache these types of DNS answers when we receive them
+      from an exit node in response to a request from this port, and
+      {No,}UseCached{IPv4,IPv6,DNS} lines to indicate that if we have
+      cached DNS answers of these types, we shouldn't use them. It's
+      potentially risky to use cached DNS answers at the client,
+      since doing so can indicate to one exit
+      what answers we've gotten for DNS lookups in the past. With
+      IPv6, this becomes especially problematic. Using cached DNS
+      answers for requests on the same circuit would present less
+      linkability risk, since all traffic on a circuits is already
+      linkable, but it would also provide little performance benefit:
+      the exit node caches DNS replies too. Implements a simplified
+      version of Proposal 205. Implements ticket #7570.
+
+  o Disabled features:
+
+    - Client-side use of the DNS cache is now off by default.  See "Major
+      features (client-side DNS)" for more information. Implements a
+      simplified version of Proposal 205. Implements ticket #7570.
+
diff --git a/doc/tor.1.txt b/doc/tor.1.txt
index 29d99b85af..85b7f4c35a 100644
--- a/doc/tor.1.txt
+++ b/doc/tor.1.txt
@@ -929,11 +929,37 @@ The following options are useful only for clients (that is, if
         Tells exits that, if a host has both an IPv4 and an IPv6 address,
         we would prefer to connect to it via IPv6. (IPv4 is the default.) +
 +
-    NOTE: Although this option allows you to specify an IP address other than
-    localhost, you should do so only with extreme caution.  The SOCKS
-    protocol is unencrypted and (as we use it) unauthenticated, so exposing
-    it in this way could leak your information to anybody watching your
-    network, and allow anybody to use your computer as an open proxy.
+       NOTE: Although this option allows you to specify an IP address
+       other than localhost, you should do so only with extreme caution.
+       The SOCKS protocol is unencrypted and (as we use it)
+       unauthenticated, so exposing it in this way could leak your
+       information to anybody watching your network, and allow anybody
+       to use your computer as an open proxy.
+    **CacheIPv4DNS**;;
+        Tells the client to remember IPv4 DNS answers we receive from exit
+        nodes via this connection. (On by default.)
+    **CacheIPv6DNS**;;
+        Tells the client to remember IPv6 DNS answers we receive from exit
+        nodes via this connection.
+    **CacheDNS**;;
+        Tells the client to remember all DNS answers we receive from exit
+        nodes via this connection.
+    **UseIPv4Cache**;;
+        Tells the client to use any cached IPv4 DNS answers we have when making
+        requests via this connection. (NOTE: This option, along UseIPv6Cache
+        and UseDNSCache, can harm your anonymity, and probably
+        won't help performance as much as you might expect. Use with care!)
+    **UseIPv6Cache**;;
+        Tells the client to use any cached IPv6 DNS answers we have when making
+        requests via this connection.
+    **UseDNSCache**;;
+        Tells the client to use any cached DNS answers we have when making
+        requests via this connection.
+    **PreferIPv6Automap**;;
+        When serving a hostname lookup request on this port that
+        should get automapped (according to AutomapHostsOnResove),
+        if we could return either an IPv4 or an IPv6 answer, prefer
+        an IPv6 answer. (On by default.)
 
 **SOCKSListenAddress** __IP__[:__PORT__]::
     Bind to this address to listen for connections from Socks-speaking
@@ -1019,16 +1045,20 @@ The following options are useful only for clients (that is, if
     applications to do DNS resolves themselves is usually a bad idea and
     can leak your location to attackers. (Default: 1)
 
-**VirtualAddrNetwork** __Address__/__bits__::
+**VirtualAddrNetworkIPv4** __Address__/__bits__ +
+
+**VirtualAddrNetworkIPv6** [__Address__]/__bits__::
     When Tor needs to assign a virtual (unused) address because of a MAPADDRESS
     command from the controller or the AutomapHostsOnResolve feature, Tor
-    picks an unassigned address from this range. (Default:
-    127.192.0.0/10) +
+    picks an unassigned address from this range. (Defaults:
+    127.192.0.0/10 and [FE80::]/10 respectively.) +
  +
     When providing proxy server service to a network of computers using a tool
-    like dns-proxy-tor, change this address to "10.192.0.0/10" or
-    "172.16.0.0/12". The default **VirtualAddrNetwork** address range on a
-    properly configured machine will route to the loopback interface. For
+    like dns-proxy-tor, change the IPv4 network to "10.192.0.0/10" or
+    "172.16.0.0/12" and change the IPv6 network to "[FC00]/7".
+    The default **VirtualAddrNetwork** address ranges on a
+    properly configured machine will route to the loopback or link-local
+    interface. For
     local use, no change to the default VirtualAddrNetwork setting is needed.
 
 **AllowNonRFC953Hostnames** **0**|**1**::
diff --git a/src/or/addressmap.c b/src/or/addressmap.c
index 98448ebddf..f4c31295a8 100644
--- a/src/or/addressmap.c
+++ b/src/or/addressmap.c
@@ -4,6 +4,8 @@
  * Copyright (c) 2007-2012, The Tor Project, Inc. */
 /* See LICENSE for licensing information */
 
+#define ADDRESSMAP_PRIVATE
+
 #include "or.h"
 #include "addressmap.h"
 #include "circuituse.h"
@@ -52,11 +54,13 @@ typedef struct {
 /** Entry for mapping addresses to which virtual address we mapped them to. */
 typedef struct {
   char *ipv4_address;
+  char *ipv6_address;
   char *hostname_address;
 } virtaddress_entry_t;
 
 /** A hash table to store client-side address rewrite instructions. */
 static strmap_t *addressmap=NULL;
+
 /**
  * Table mapping addresses to which virtual address, if any, we
  * assigned them to.
@@ -210,6 +214,24 @@ addressmap_clear_excluded_trackexithosts(const or_options_t *options)
   } STRMAP_FOREACH_END;
 }
 
+/** Return true iff <b>address</b> is one that we are configured to
+ * automap on resolve according to <b>options</b>. */
+int
+addressmap_address_should_automap(const char *address,
+                                  const or_options_t *options)
+{
+  const smartlist_t *suffix_list = options->AutomapHostsSuffixes;
+
+  if (!suffix_list)
+    return 0;
+
+  SMARTLIST_FOREACH_BEGIN(suffix_list, const char *, suffix) {
+    if (!strcasecmpend(address, suffix))
+      return 1;
+  } SMARTLIST_FOREACH_END(suffix);
+  return 0;
+}
+
 /** Remove all AUTOMAP mappings from the addressmap for which the
  * source address no longer matches AutomapHostsSuffixes, which is
  * no longer allowed by AutomapHostsOnResolve, or for which the
@@ -232,15 +254,7 @@ addressmap_clear_invalid_automaps(const or_options_t *options)
       continue; /* not an automap mapping. */
 
     if (!remove) {
-      int suffix_found = 0;
-      SMARTLIST_FOREACH(suffixes, const char *, suffix, {
-          if (!strcasecmpend(src_address, suffix)) {
-            suffix_found = 1;
-            break;
-          }
-      });
-      if (!suffix_found)
-        remove = 1;
+      remove = ! addressmap_address_should_automap(src_address, options);
     }
 
     if (!remove && ! address_is_in_virtual_range(ent->new_address))
@@ -335,7 +349,9 @@ addressmap_match_superdomains(char *address)
  * was a .exit.
  */
 int
-addressmap_rewrite(char *address, size_t maxlen, time_t *expires_out,
+addressmap_rewrite(char *address, size_t maxlen,
+                   unsigned flags,
+                   time_t *expires_out,
                    addressmap_entry_source_t *exit_source_out)
 {
   addressmap_entry_t *ent;
@@ -368,6 +384,16 @@ addressmap_rewrite(char *address, size_t maxlen, time_t *expires_out,
       goto done;
     }
 
+    if (ent && ent->source == ADDRMAPSRC_DNS) {
+      sa_family_t f;
+      tor_addr_t tmp;
+      f = tor_addr_parse(&tmp, ent->new_address);
+      if (f == AF_INET && !(flags & AMR_FLAG_USE_IPV4_DNS))
+        goto done;
+      else if (f == AF_INET6 && !(flags & AMR_FLAG_USE_IPV6_DNS))
+        goto done;
+    }
+
     if (ent->dst_wildcard && !exact_match) {
       strlcat(address, ".", maxlen);
       strlcat(address, ent->new_address, maxlen);
@@ -409,11 +435,22 @@ addressmap_rewrite(char *address, size_t maxlen, time_t *expires_out,
  * *<b>expires_out</b> to the expiry time of the result, or to <b>time_max</b>
  * if the result does not expire. */
 int
-addressmap_rewrite_reverse(char *address, size_t maxlen, time_t *expires_out)
+addressmap_rewrite_reverse(char *address, size_t maxlen, unsigned flags,
+                           time_t *expires_out)
 {
   char *s, *cp;
   addressmap_entry_t *ent;
   int r = 0;
+  {
+    sa_family_t f;
+    tor_addr_t tmp;
+    f = tor_addr_parse(&tmp, address);
+    if (f == AF_INET && !(flags & AMR_FLAG_USE_IPV4_DNS))
+      return 0;
+    else if (f == AF_INET6 && !(flags & AMR_FLAG_USE_IPV6_DNS))
+      return 0;
+  }
+
   tor_asprintf(&s, "REVERSE[%s]", address);
   ent = strmap_get(addressmap, s);
   if (ent) {
@@ -571,13 +608,13 @@ client_dns_clear_failures(const char *address)
  * <b>ttl</b>seconds; otherwise, we use the default.
  */
 static void
-client_dns_set_addressmap_impl(origin_circuit_t *on_circ,
+client_dns_set_addressmap_impl(entry_connection_t *for_conn,
                                const char *address, const char *name,
                                const char *exitname,
                                int ttl)
 {
   char *extendedaddress=NULL, *extendedval=NULL;
-  (void)on_circ;
+  (void)for_conn;
 
   tor_assert(address);
   tor_assert(name);
@@ -617,7 +654,7 @@ client_dns_set_addressmap_impl(origin_circuit_t *on_circ,
  * <b>ttl</b>seconds; otherwise, we use the default.
  */
 void
-client_dns_set_addressmap(origin_circuit_t *on_circ,
+client_dns_set_addressmap(entry_connection_t *for_conn,
                           const char *address,
                           const tor_addr_t *val,
                           const char *exitname,
@@ -629,17 +666,21 @@ client_dns_set_addressmap(origin_circuit_t *on_circ,
   tor_assert(address);
   tor_assert(val);
 
-  if (tor_addr_parse(&addr_tmp, address) == 0)
+  if (tor_addr_parse(&addr_tmp, address) >= 0)
     return; /* If address was an IP address already, don't add a mapping. */
 
-  /* XXXXX For now, don't cache IPv6 addresses. */
-  if (tor_addr_family(val) != AF_INET)
-    return;
+  if (tor_addr_family(val) == AF_INET) {
+    if (! for_conn->cache_ipv4_answers)
+      return;
+  } else if (tor_addr_family(val) == AF_INET6) {
+    if (! for_conn->cache_ipv6_answers)
+      return;
+  }
 
   if (! tor_addr_to_str(valbuf, val, sizeof(valbuf), 1))
     return;
 
-  client_dns_set_addressmap_impl(on_circ, address, valbuf, exitname, ttl);
+  client_dns_set_addressmap_impl(for_conn, address, valbuf, exitname, ttl);
 }
 
 /** Add a cache entry noting that <b>address</b> (ordinarily a dotted quad)
@@ -652,14 +693,21 @@ client_dns_set_addressmap(origin_circuit_t *on_circ,
  * <b>ttl</b>seconds; otherwise, we use the default.
  */
 void
-client_dns_set_reverse_addressmap(origin_circuit_t *on_circ,
+client_dns_set_reverse_addressmap(entry_connection_t *for_conn,
                                   const char *address, const char *v,
                                   const char *exitname,
                                   int ttl)
 {
   char *s = NULL;
+  {
+    tor_addr_t tmp_addr;
+    sa_family_t f = tor_addr_parse(&tmp_addr, address);
+    if ((f == AF_INET && ! for_conn->cache_ipv4_answers) ||
+        (f == AF_INET6 && ! for_conn->cache_ipv6_answers))
+      return;
+  }
   tor_asprintf(&s, "REVERSE[%s]", address);
-  client_dns_set_addressmap_impl(on_circ, s, v, exitname, ttl);
+  client_dns_set_addressmap_impl(for_conn, s, v, exitname, ttl);
   tor_free(s);
 }
 
@@ -670,13 +718,9 @@ client_dns_set_reverse_addressmap(origin_circuit_t *on_circ,
  *
  * These options are configured by parse_virtual_addr_network().
  */
-/** Which network should we use for virtual IPv4 addresses?  Only the first
- * bits of this value are fixed. */
-static uint32_t virtual_addr_network = 0x7fc00000u;
-/** How many bits of <b>virtual_addr_network</b> are fixed? */
-static maskbits_t virtual_addr_netmask_bits = 10;
-/** What's the next virtual address we will hand out? */
-static uint32_t next_virtual_addr    = 0x7fc00000u;
+
+static virtual_addr_conf_t virtaddr_conf_ipv4;
+static virtual_addr_conf_t virtaddr_conf_ipv6;
 
 /** Read a netmask of the form 127.192.0.0/10 from "val", and check whether
  * it's a valid set of virtual addresses to hand out in response to MAPADDRESS
@@ -684,37 +728,49 @@ static uint32_t next_virtual_addr    = 0x7fc00000u;
  * string and return -1 on failure.  If validate_only is false, sets the
  * actual virtual address range to the parsed value. */
 int
-parse_virtual_addr_network(const char *val, int validate_only,
+parse_virtual_addr_network(const char *val, sa_family_t family,
+                           int validate_only,
                            char **msg)
 {
-  uint32_t addr;
-  uint16_t port_min, port_max;
+  const int ipv6 = (family == AF_INET6);
+  tor_addr_t addr;
   maskbits_t bits;
+  const int max_bits = ipv6 ? 40 : 16;
+  virtual_addr_conf_t *conf = ipv6 ? &virtaddr_conf_ipv6 : &virtaddr_conf_ipv4;
 
-  if (parse_addr_and_port_range(val, &addr, &bits, &port_min, &port_max)) {
-    if (msg) *msg = tor_strdup("Error parsing VirtualAddressNetwork");
+  if (tor_addr_parse_mask_ports(val, 0, &addr, &bits, NULL, NULL) < 0) {
+    if (msg)
+      tor_asprintf(msg, "Error parsing VirtualAddressNetwork%s %s",
+                   ipv6?"IPv6":"", val);
     return -1;
   }
-
+  if (tor_addr_family(&addr) != family) {
+    if (msg)
+      tor_asprintf(msg, "Incorrect address type for VirtualAddressNetwork%s",
+                   ipv6?"IPv6":"");
+    return -1;
+  }
+#if 0
   if (port_min != 1 || port_max != 65535) {
-    if (msg) *msg = tor_strdup("Can't specify ports on VirtualAddressNetwork");
+    if (msg)
+      tor_asprintf(msg, "Can't specify ports on VirtualAddressNetwork%s",
+                   ipv6?"IPv6":"");
     return -1;
   }
+#endif
 
-  if (bits > 16) {
-    if (msg) *msg = tor_strdup("VirtualAddressNetwork expects a /16 "
-                               "network or larger");
+  if (bits > max_bits) {
+    if (msg)
+      tor_asprintf(msg, "VirtualAddressNetwork%s expects a /%d "
+                   "network or larger",ipv6?"IPv6":"", max_bits);
     return -1;
   }
 
   if (validate_only)
     return 0;
 
-  virtual_addr_network = (uint32_t)( addr & (0xfffffffful << (32-bits)) );
-  virtual_addr_netmask_bits = bits;
-
-  if (addr_mask_cmp_bits(next_virtual_addr, addr, bits))
-    next_virtual_addr = addr;
+  tor_addr_copy(&conf->addr, &addr);
+  conf->bits = bits;
 
   return 0;
 }
@@ -726,29 +782,60 @@ parse_virtual_addr_network(const char *val, int validate_only,
 int
 address_is_in_virtual_range(const char *address)
 {
-  struct in_addr in;
+  tor_addr_t addr;
   tor_assert(address);
   if (!strcasecmpend(address, ".virtual")) {
     return 1;
-  } else if (tor_inet_aton(address, &in)) {
-    uint32_t addr = ntohl(in.s_addr);
-    if (!addr_mask_cmp_bits(addr, virtual_addr_network,
-                            virtual_addr_netmask_bits))
+  } else if (tor_addr_parse(&addr, address) >= 0) {
+    const virtual_addr_conf_t *conf = (tor_addr_family(&addr) == AF_INET6) ?
+      &virtaddr_conf_ipv6 : &virtaddr_conf_ipv4;
+    if (tor_addr_compare_masked(&addr, &conf->addr, conf->bits, CMP_EXACT)==0)
       return 1;
   }
   return 0;
 }
 
-/** Increment the value of next_virtual_addr; reset it to the start of the
- * virtual address range if it wraps around.
+/** Return a random address conforming to the virtual address configuration
+ * in <b>conf</b>.
  */
-static INLINE void
-increment_virtual_addr(void)
+/* private */ void
+get_random_virtual_addr(const virtual_addr_conf_t *conf, tor_addr_t *addr_out)
 {
-  ++next_virtual_addr;
-  if (addr_mask_cmp_bits(next_virtual_addr, virtual_addr_network,
-                         virtual_addr_netmask_bits))
-    next_virtual_addr = virtual_addr_network;
+  uint8_t tmp[4];
+  const uint8_t *addr_bytes;
+  uint8_t bytes[16];
+  const int ipv6 = tor_addr_family(&conf->addr) == AF_INET6;
+  const int total_bytes = ipv6 ? 16 : 4;
+
+  tor_assert(conf->bits <= total_bytes * 8);
+
+  /* Set addr_bytes to the bytes of the virtual network, in host order */
+  if (ipv6) {
+    addr_bytes = tor_addr_to_in6_addr8(&conf->addr);
+  } else {
+    set_uint32(tmp, tor_addr_to_ipv4n(&conf->addr));
+    addr_bytes = tmp;
+  }
+
+  /* Get an appropriate number of random bytes. */
+  crypto_rand((char*)bytes, total_bytes);
+
+  /* Now replace the first "conf->bits" bits of 'bytes' with addr_bytes*/
+  if (conf->bits >= 8)
+    memcpy(bytes, addr_bytes, conf->bits / 8);
+  if (conf->bits & 7) {
+    uint8_t mask = 0xff >> (conf->bits & 7);
+    bytes[conf->bits/8] &= mask;
+    bytes[conf->bits/8] |= addr_bytes[conf->bits/8] & ~mask;
+  }
+
+  if (ipv6)
+    tor_addr_from_ipv6_bytes(addr_out, (char*) bytes);
+  else
+    tor_addr_from_ipv4n(addr_out, get_uint32(bytes));
+
+  tor_assert(tor_addr_compare_masked(addr_out, &conf->addr,
+                                     conf->bits, CMP_EXACT)==0);
 }
 
 /** Return a newly allocated string holding an address of <b>type</b>
@@ -771,37 +858,48 @@ addressmap_get_virtual_address(int type)
       strlcat(buf, ".virtual", sizeof(buf));
     } while (strmap_get(addressmap, buf));
     return tor_strdup(buf);
-  } else if (type == RESOLVED_TYPE_IPV4) {
-    // This is an imperfect estimate of how many addresses are available, but
-    // that's ok.
-    struct in_addr in;
-    uint32_t available = 1u << (32-virtual_addr_netmask_bits);
-    while (available) {
-      /* Don't hand out any .0 or .255 address. */
-      while ((next_virtual_addr & 0xff) == 0 ||
-             (next_virtual_addr & 0xff) == 0xff) {
-        increment_virtual_addr();
-        if (! --available) {
-          log_warn(LD_CONFIG, "Ran out of virtual addresses!");
-          return NULL;
-        }
+  } else if (type == RESOLVED_TYPE_IPV4 || type == RESOLVED_TYPE_IPV6) {
+    const int ipv6 = (type == RESOLVED_TYPE_IPV6);
+    const virtual_addr_conf_t *conf = ipv6 ?
+      &virtaddr_conf_ipv6 : &virtaddr_conf_ipv4;
+
+    /* Don't try more than 1000 times.  This gives us P < 1e-9 for
+     * failing to get a good address so long as the address space is
+     * less than ~97.95% full.  That's always going to be true under
+     * sensible circumstances for an IPv6 /10, and it's going to be
+     * true for an IPv4 /10 as long as we've handed out less than
+     * 4.08 million addresses. */
+    uint32_t attempts = 1000;
+
+    tor_addr_t addr;
+
+    while (attempts--) {
+      get_random_virtual_addr(conf, &addr);
+
+      if (!ipv6) {
+        /* Don't hand out any .0 or .255 address. */
+        const uint32_t a = tor_addr_to_ipv4h(&addr);
+        if ((a & 0xff) == 0 || (a & 0xff) == 0xff)
+          continue;
       }
-      in.s_addr = htonl(next_virtual_addr);
-      tor_inet_ntoa(&in, buf, sizeof(buf));
+
+      tor_addr_to_str(buf, &addr, sizeof(buf), 1);
       if (!strmap_get(addressmap, buf)) {
-        increment_virtual_addr();
-        break;
-      }
+        /* XXXX This code is to make sure I didn't add an undecorated version
+         * by mistake. I hope it's needless. */
+        char tmp[TOR_ADDR_BUF_LEN];
+        tor_addr_to_str(buf, &addr, sizeof(tmp), 0);
+        if (strmap_get(addressmap, tmp)) {
+          log_warn(LD_BUG, "%s wasn't in the addressmap, but %s was.",
+                   buf, tmp);
+          continue;
+        }
 
-      increment_virtual_addr();
-      --available;
-      // log_info(LD_CONFIG, "%d addrs available", (int)available);
-      if (! available) {
-        log_warn(LD_CONFIG, "Ran out of virtual addresses!");
-        return NULL;
+        return tor_strdup(buf);
       }
     }
-    return tor_strdup(buf);
+    log_warn(LD_CONFIG, "Ran out of virtual addresses!");
+    return NULL;
   } else {
     log_warn(LD_BUG, "Called with unsupported address type (%d)", type);
     return NULL;
@@ -834,8 +932,13 @@ addressmap_register_virtual_address(int type, char *new_address)
     vent_needs_to_be_added = 1;
   }
 
-  addrp = (type == RESOLVED_TYPE_IPV4) ?
-    &vent->ipv4_address : &vent->hostname_address;
+  if (type == RESOLVED_TYPE_IPV4)
+    addrp = &vent->ipv4_address;
+  else if (type == RESOLVED_TYPE_IPV6)
+    addrp = &vent->ipv6_address;
+  else
+    addrp = &vent->hostname_address;
+
   if (*addrp) {
     addressmap_entry_t *ent = strmap_get(addressmap, *addrp);
     if (ent && ent->new_address &&
@@ -843,7 +946,7 @@ addressmap_register_virtual_address(int type, char *new_address)
       tor_free(new_address);
       tor_assert(!vent_needs_to_be_added);
       return tor_strdup(*addrp);
-    } else
+    } else {
       log_warn(LD_BUG,
                "Internal confusion: I thought that '%s' was mapped to by "
                "'%s', but '%s' really maps to '%s'. This is a harmless bug.",
@@ -851,6 +954,7 @@ addressmap_register_virtual_address(int type, char *new_address)
                safe_str_client(*addrp),
                safe_str_client(*addrp),
                ent?safe_str_client(ent->new_address):"(nothing)");
+    }
   }
 
   tor_free(*addrp);
diff --git a/src/or/addressmap.h b/src/or/addressmap.h
index 9b07341479..3f1c44571f 100644
--- a/src/or/addressmap.h
+++ b/src/or/addressmap.h
@@ -14,9 +14,12 @@ void addressmap_clean(time_t now);
 void addressmap_clear_configured(void);
 void addressmap_clear_transient(void);
 void addressmap_free_all(void);
-int addressmap_rewrite(char *address, size_t maxlen, time_t *expires_out,
+#define AMR_FLAG_USE_IPV4_DNS (1u<<0)
+#define AMR_FLAG_USE_IPV6_DNS (1u<<1)
+int addressmap_rewrite(char *address, size_t maxlen, unsigned flags,
+                       time_t *expires_out,
                        addressmap_entry_source_t *exit_source_out);
-int addressmap_rewrite_reverse(char *address, size_t maxlen,
+int addressmap_rewrite_reverse(char *address, size_t maxlen, unsigned flags,
                                time_t *expires_out);
 int addressmap_have_mapping(const char *address, int update_timeout);
 
@@ -24,11 +27,12 @@ void addressmap_register(const char *address, char *new_address,
                          time_t expires, addressmap_entry_source_t source,
                          const int address_wildcard,
                          const int new_address_wildcard);
-int parse_virtual_addr_network(const char *val, int validate_only,
+int parse_virtual_addr_network(const char *val,
+                               sa_family_t family, int validate_only,
                                char **msg);
 int client_dns_incr_failures(const char *address);
 void client_dns_clear_failures(const char *address);
-void client_dns_set_addressmap(origin_circuit_t *on_circ,
+void client_dns_set_addressmap(entry_connection_t *for_conn,
                                const char *address, const tor_addr_t *val,
                                const char *exitname, int ttl);
 const char *addressmap_register_virtual_address(int type, char *new_address);
@@ -36,9 +40,21 @@ void addressmap_get_mappings(smartlist_t *sl, time_t min_expires,
                              time_t max_expires, int want_expiry);
 int address_is_in_virtual_range(const char *addr);
 void clear_trackexithost_mappings(const char *exitname);
-void client_dns_set_reverse_addressmap(origin_circuit_t *on_circ,
+void client_dns_set_reverse_addressmap(entry_connection_t *for_conn,
                                        const char *address, const char *v,
                                        const char *exitname, int ttl);
+int addressmap_address_should_automap(const char *address,
+                                      const or_options_t *options);
+
+#ifdef ADDRESSMAP_PRIVATE
+typedef struct virtual_addr_conf_t {
+  tor_addr_t addr;
+  maskbits_t bits;
+} virtual_addr_conf_t;
+
+void get_random_virtual_addr(const virtual_addr_conf_t *conf,
+                             tor_addr_t *addr_out);
+#endif
 
 #endif
 
diff --git a/src/or/config.c b/src/or/config.c
index acfe2c4f83..1df10e110e 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -98,6 +98,7 @@ static config_abbrev_t option_abbrevs_[] = {
   { "HashedControlPassword", "__HashedControlSessionPassword", 1, 0},
   { "StrictEntryNodes", "StrictNodes", 0, 1},
   { "StrictExitNodes", "StrictNodes", 0, 1},
+  { "VirtualAddrNetwork", "VirtualAddrNetworkIPv4", 0, 0},
   { "_UseFilteringSSLBufferevents", "UseFilteringSSLBufferevents", 0, 1},
   { NULL, NULL, 0, 0},
 };
@@ -396,7 +397,8 @@ static config_var_t option_vars_[] = {
   V(V3AuthUseLegacyKey,          BOOL,     "0"),
   V(V3BandwidthsFile,            FILENAME, NULL),
   VAR("VersioningAuthoritativeDirectory",BOOL,VersioningAuthoritativeDir, "0"),
-  V(VirtualAddrNetwork,          STRING,   "127.192.0.0/10"),
+  V(VirtualAddrNetworkIPv4,      STRING,   "127.192.0.0/10"),
+  V(VirtualAddrNetworkIPv6,      STRING,   "[FE80::]/10"),
   V(WarnPlaintextPorts,          CSV,      "23,109,110,143"),
   V(UseFilteringSSLBufferevents, BOOL,    "0"),
   VAR("__ReloadTorrcOnSIGHUP",   BOOL,  ReloadTorrcOnSIGHUP,      "1"),
@@ -678,7 +680,7 @@ config_free_all(void)
 
   if (configured_ports) {
     SMARTLIST_FOREACH(configured_ports,
-                      port_cfg_t *, p, tor_free(p));
+                      port_cfg_t *, p, port_cfg_free(p));
     smartlist_free(configured_ports);
     configured_ports = NULL;
   }
@@ -1379,7 +1381,8 @@ options_act(const or_options_t *old_options)
 
   /* Register addressmap directives */
   config_register_addressmaps(options);
-  parse_virtual_addr_network(options->VirtualAddrNetwork, 0, NULL);
+  parse_virtual_addr_network(options->VirtualAddrNetworkIPv4, AF_INET,0,NULL);
+  parse_virtual_addr_network(options->VirtualAddrNetworkIPv6, AF_INET6,0,NULL);
 
   /* Update address policies. */
   if (policies_parse_from_options(options) < 0) {
@@ -1492,8 +1495,10 @@ options_act(const or_options_t *old_options)
       if (!smartlist_strings_eq(old_options->AutomapHostsSuffixes,
                                 options->AutomapHostsSuffixes))
         revise_automap_entries = 1;
-      else if (!opt_streq(old_options->VirtualAddrNetwork,
-                          options->VirtualAddrNetwork))
+      else if (!opt_streq(old_options->VirtualAddrNetworkIPv4,
+                          options->VirtualAddrNetworkIPv4) ||
+               !opt_streq(old_options->VirtualAddrNetworkIPv6,
+                          options->VirtualAddrNetworkIPv6))
         revise_automap_entries = 1;
     }
 
@@ -2968,7 +2973,11 @@ options_validate(or_options_t *old_options, or_options_t *options,
     REJECT("Failed to configure client authorization for hidden services. "
            "See logs for details.");
 
-  if (parse_virtual_addr_network(options->VirtualAddrNetwork, 1, NULL)<0)
+  if (parse_virtual_addr_network(options->VirtualAddrNetworkIPv4,
+                                 AF_INET, 1, msg)<0)
+    return -1;
+  if (parse_virtual_addr_network(options->VirtualAddrNetworkIPv6,
+                                 AF_INET6, 1, msg)<0)
     return -1;
 
   if (options->PreferTunneledDirConns && !options->TunnelDirConns)
@@ -4589,6 +4598,17 @@ parse_dir_fallback_line(const char *line,
   return r;
 }
 
+/** Allocate and return a new port_cfg_t with reasonable defaults. */
+static port_cfg_t *
+port_cfg_new(void)
+{
+  port_cfg_t *cfg = tor_malloc_zero(sizeof(port_cfg_t));
+  cfg->ipv4_traffic = 1;
+  cfg->cache_ipv4_answers = 1;
+  cfg->prefer_ipv6_virtaddr = 1;
+  return cfg;
+}
+
 /** Free all storage held in <b>port</b> */
 static void
 port_cfg_free(port_cfg_t *port)
@@ -4763,13 +4783,14 @@ parse_port_config(smartlist_t *out,
 
     if (use_server_options && out) {
       /* Add a no_listen port. */
-      port_cfg_t *cfg = tor_malloc_zero(sizeof(port_cfg_t));
+      port_cfg_t *cfg = port_cfg_new();
       cfg->type = listener_type;
       cfg->port = mainport;
       tor_addr_make_unspec(&cfg->addr); /* Server ports default to 0.0.0.0 */
       cfg->no_listen = 1;
       cfg->bind_ipv4_only = 1;
       cfg->ipv4_traffic = 1;
+      cfg->prefer_ipv6_virtaddr = 1;
       smartlist_add(out, cfg);
     }
 
@@ -4782,14 +4803,13 @@ parse_port_config(smartlist_t *out,
         return -1;
       }
       if (out) {
-        port_cfg_t *cfg = tor_malloc_zero(sizeof(port_cfg_t));
+        port_cfg_t *cfg = port_cfg_new();
         cfg->type = listener_type;
         cfg->port = port ? port : mainport;
         tor_addr_copy(&cfg->addr, &addr);
         cfg->session_group = SESSION_GROUP_UNSET;
         cfg->isolation_flags = ISO_DEFAULT;
         cfg->no_advertise = 1;
-        cfg->ipv4_traffic = 1;
         smartlist_add(out, cfg);
       }
     }
@@ -4807,13 +4827,12 @@ parse_port_config(smartlist_t *out,
    * one. */
   if (! ports) {
     if (defaultport && out) {
-       port_cfg_t *cfg = tor_malloc_zero(sizeof(port_cfg_t));
+       port_cfg_t *cfg = port_cfg_new();
        cfg->type = listener_type;
        cfg->port = defaultport;
        tor_addr_parse(&cfg->addr, defaultaddr);
        cfg->session_group = SESSION_GROUP_UNSET;
        cfg->isolation_flags = ISO_DEFAULT;
-       cfg->ipv4_traffic = 1;
        smartlist_add(out, cfg);
     }
     return 0;
@@ -4834,7 +4853,10 @@ parse_port_config(smartlist_t *out,
     int ok;
     int no_listen = 0, no_advertise = 0, all_addrs = 0,
       bind_ipv4_only = 0, bind_ipv6_only = 0,
-      ipv4_traffic = 1, ipv6_traffic = 0, prefer_ipv6 = 0;
+      ipv4_traffic = 1, ipv6_traffic = 0, prefer_ipv6 = 0,
+      cache_ipv4 = 1, use_cached_ipv4 = 0,
+      cache_ipv6 = 0, use_cached_ipv6 = 0,
+      prefer_ipv6_automap = 1;
 
     smartlist_split_string(elts, ports->value, NULL,
                            SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
@@ -4971,6 +4993,28 @@ parse_port_config(smartlist_t *out,
             continue;
           }
         }
+        if (!strcasecmp(elt, "CacheIPv4DNS")) {
+          cache_ipv4 = ! no;
+          continue;
+        } else if (!strcasecmp(elt, "CacheIPv6DNS")) {
+          cache_ipv6 = ! no;
+          continue;
+        } else if (!strcasecmp(elt, "CacheDNS")) {
+          cache_ipv4 = cache_ipv6 = ! no;
+          continue;
+        } else if (!strcasecmp(elt, "UseIPv4Cache")) {
+          use_cached_ipv4 = ! no;
+          continue;
+        } else if (!strcasecmp(elt, "UseIPv6Cache")) {
+          use_cached_ipv6 = ! no;
+          continue;
+        } else if (!strcasecmp(elt, "UseDNSCache")) {
+          use_cached_ipv4 = use_cached_ipv6 = ! no;
+          continue;
+        } else if (!strcasecmp(elt, "PreferIPv6Automap")) {
+          prefer_ipv6_automap = ! no;
+          continue;
+        }
 
         if (!strcasecmpend(elt, "s"))
           elt[strlen(elt)-1] = '\0'; /* kill plurals. */
@@ -5010,7 +5054,7 @@ parse_port_config(smartlist_t *out,
     }
 
     if (out && port) {
-      port_cfg_t *cfg = tor_malloc_zero(sizeof(port_cfg_t));
+      port_cfg_t *cfg = port_cfg_new();
       tor_addr_copy(&cfg->addr, &addr);
       cfg->port = port;
       cfg->type = listener_type;
@@ -5024,6 +5068,11 @@ parse_port_config(smartlist_t *out,
       cfg->ipv4_traffic = ipv4_traffic;
       cfg->ipv6_traffic = ipv6_traffic;
       cfg->prefer_ipv6 = prefer_ipv6;
+      cfg->cache_ipv4_answers = cache_ipv4;
+      cfg->cache_ipv6_answers = cache_ipv6;
+      cfg->use_cached_ipv4_answers = use_cached_ipv4;
+      cfg->use_cached_ipv6_answers = use_cached_ipv6;
+      cfg->prefer_ipv6_virtaddr = prefer_ipv6_automap;
 
       smartlist_add(out, cfg);
     }
@@ -5125,7 +5174,7 @@ parse_ports(or_options_t *options, int validate_only,
                         options->DNSPort_lines, options->DNSListenAddress,
                         "DNS", CONN_TYPE_AP_DNS_LISTENER,
                         "127.0.0.1", 0,
-                        CL_PORT_WARN_NONLOCAL) < 0) {
+                        CL_PORT_WARN_NONLOCAL|CL_PORT_TAKES_HOSTNAMES) < 0) {
     *msg = tor_strdup("Invalid DNSPort/DNSListenAddress configuration");
     goto err;
   }
diff --git a/src/or/connection.c b/src/or/connection.c
index 223bbd938f..740462e7c6 100644
--- a/src/or/connection.c
+++ b/src/or/connection.c
@@ -1130,6 +1130,11 @@ connection_listener_new(const struct sockaddr *listensockaddr,
     lis_conn->socks_ipv4_traffic = 1;
     lis_conn->socks_ipv6_traffic = 1;
   }
+  lis_conn->cache_ipv4_answers = port_cfg->cache_ipv4_answers;
+  lis_conn->cache_ipv6_answers = port_cfg->cache_ipv6_answers;
+  lis_conn->use_cached_ipv4_answers = port_cfg->use_cached_ipv4_answers;
+  lis_conn->use_cached_ipv6_answers = port_cfg->use_cached_ipv6_answers;
+  lis_conn->prefer_ipv6_virtaddr = port_cfg->prefer_ipv6_virtaddr;
 
   if (connection_add(conn) < 0) { /* no space, forget it */
     log_warn(LD_NET,"connection_add for listener failed. Giving up.");
@@ -1366,6 +1371,15 @@ connection_init_accepted_conn(connection_t *conn,
       TO_ENTRY_CONN(conn)->ipv4_traffic_ok = listener->socks_ipv4_traffic;
       TO_ENTRY_CONN(conn)->ipv6_traffic_ok = listener->socks_ipv6_traffic;
       TO_ENTRY_CONN(conn)->prefer_ipv6_traffic = listener->socks_prefer_ipv6;
+      TO_ENTRY_CONN(conn)->cache_ipv4_answers = listener->cache_ipv4_answers;
+      TO_ENTRY_CONN(conn)->cache_ipv6_answers = listener->cache_ipv6_answers;
+      TO_ENTRY_CONN(conn)->use_cached_ipv4_answers =
+        listener->use_cached_ipv4_answers;
+      TO_ENTRY_CONN(conn)->use_cached_ipv6_answers =
+        listener->use_cached_ipv6_answers;
+      TO_ENTRY_CONN(conn)->prefer_ipv6_virtaddr =
+        listener->prefer_ipv6_virtaddr;
+
       switch (TO_CONN(listener)->type) {
         case CONN_TYPE_AP_LISTENER:
           conn->state = AP_CONN_STATE_SOCKS_WAIT;
diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c
index 95088c7c17..28c9e09ee5 100644
--- a/src/or/connection_edge.c
+++ b/src/or/connection_edge.c
@@ -897,7 +897,7 @@ connection_ap_handshake_rewrite_and_attach(entry_connection_t *conn,
   socks_request_t *socks = conn->socks_request;
   hostname_type_t addresstype;
   const or_options_t *options = get_options();
-  struct in_addr addr_tmp;
+  tor_addr_t addr_tmp;
   /* We set this to true if this is an address we should automatically
    * remap to a local address in VirtualAddrNetwork */
   int automap = 0;
@@ -927,17 +927,20 @@ connection_ap_handshake_rewrite_and_attach(entry_connection_t *conn,
     conn->original_dest_address = tor_strdup(conn->socks_request->address);
 
   if (socks->command == SOCKS_COMMAND_RESOLVE &&
-      !tor_inet_aton(socks->address, &addr_tmp) &&
-      options->AutomapHostsOnResolve && options->AutomapHostsSuffixes) {
-    SMARTLIST_FOREACH(options->AutomapHostsSuffixes, const char *, cp,
-                      if (!strcasecmpend(socks->address, cp)) {
-                        automap = 1;
-                        break;
-                      });
+      tor_addr_parse(&addr_tmp, socks->address)<0 &&
+      options->AutomapHostsOnResolve) {
+    automap = addressmap_address_should_automap(socks->address, options);
     if (automap) {
       const char *new_addr;
+      int addr_type = RESOLVED_TYPE_IPV4;
+      if (conn->socks_request->socks_version != 4) {
+        if (!conn->ipv4_traffic_ok ||
+            (conn->ipv6_traffic_ok && conn->prefer_ipv6_traffic) ||
+            conn->prefer_ipv6_virtaddr)
+          addr_type = RESOLVED_TYPE_IPV6;
+      }
       new_addr = addressmap_register_virtual_address(
-                              RESOLVED_TYPE_IPV4, tor_strdup(socks->address));
+                                    addr_type, tor_strdup(socks->address));
       if (! new_addr) {
         log_warn(LD_APP, "Unable to automap address %s",
                  escaped_safe_str(socks->address));
@@ -952,8 +955,14 @@ connection_ap_handshake_rewrite_and_attach(entry_connection_t *conn,
   }
 
   if (socks->command == SOCKS_COMMAND_RESOLVE_PTR) {
+    unsigned rewrite_flags = 0;
+    if (conn->use_cached_ipv4_answers)
+      rewrite_flags |= AMR_FLAG_USE_IPV4_DNS;
+    if (conn->use_cached_ipv6_answers)
+      rewrite_flags |= AMR_FLAG_USE_IPV6_DNS;
+
     if (addressmap_rewrite_reverse(socks->address, sizeof(socks->address),
-                                   &map_expires)) {
+                                   rewrite_flags, &map_expires)) {
       char *result = tor_strdup(socks->address);
       /* remember _what_ is supposed to have been resolved. */
       tor_snprintf(socks->address, sizeof(socks->address), "REVERSE[%s]",
@@ -984,8 +993,13 @@ connection_ap_handshake_rewrite_and_attach(entry_connection_t *conn,
     }
   } else if (!automap) {
     /* For address map controls, remap the address. */
+    unsigned rewrite_flags = 0;
+    if (conn->use_cached_ipv4_answers)
+      rewrite_flags |= AMR_FLAG_USE_IPV4_DNS;
+    if (conn->use_cached_ipv6_answers)
+      rewrite_flags |= AMR_FLAG_USE_IPV6_DNS;
     if (addressmap_rewrite(socks->address, sizeof(socks->address),
-                           &map_expires, &exit_source)) {
+                           rewrite_flags, &map_expires, &exit_source)) {
       control_event_stream_status(conn, STREAM_EVENT_REMAP,
                                   REMAP_STREAM_SOURCE_CACHE);
     }
@@ -2053,15 +2067,11 @@ connection_ap_handshake_socks_resolved(entry_connection_t *conn,
   size_t replylen;
 
   if (ttl >= 0) {
-    origin_circuit_t *origin_circ = NULL;
-    circuit_t *circ = ENTRY_TO_EDGE_CONN(conn)->on_circuit;
-    if (CIRCUIT_IS_ORIGIN(circ)) /* should always be true */
-      origin_circ = TO_ORIGIN_CIRCUIT(circ);
     if (answer_type == RESOLVED_TYPE_IPV4 && answer_len == 4) {
       tor_addr_t a;
       tor_addr_from_ipv4n(&a, get_uint32(answer));
       if (! tor_addr_is_null(&a)) {
-        client_dns_set_addressmap(origin_circ,
+        client_dns_set_addressmap(conn,
                                   conn->socks_request->address, &a,
                                   conn->chosen_exit_name, ttl);
       }
@@ -2069,13 +2079,13 @@ connection_ap_handshake_socks_resolved(entry_connection_t *conn,
       tor_addr_t a;
       tor_addr_from_ipv6_bytes(&a, (char*)answer);
       if (! tor_addr_is_null(&a)) {
-        client_dns_set_addressmap(origin_circ,
+        client_dns_set_addressmap(conn,
                                   conn->socks_request->address, &a,
                                   conn->chosen_exit_name, ttl);
       }
     } else if (answer_type == RESOLVED_TYPE_HOSTNAME && answer_len < 256) {
       char *cp = tor_strndup((char*)answer, answer_len);
-      client_dns_set_reverse_addressmap(origin_circ,
+      client_dns_set_reverse_addressmap(conn,
                                         conn->socks_request->address,
                                         cp,
                                         conn->chosen_exit_name, ttl);
diff --git a/src/or/control.c b/src/or/control.c
index 75c9af6f7b..65689c46dd 100644
--- a/src/or/control.c
+++ b/src/or/control.c
@@ -1373,10 +1373,13 @@ handle_control_mapaddress(control_connection_t *conn, uint32_t len,
                      "512-syntax error: invalid address '%s'", to);
         log_warn(LD_CONTROL,
                  "Skipping invalid argument '%s' in MapAddress msg", to);
-      } else if (!strcmp(from, ".") || !strcmp(from, "0.0.0.0")) {
+      } else if (!strcmp(from, ".") || !strcmp(from, "0.0.0.0") ||
+                 !strcmp(from, "::")) {
+        const char type =
+          !strcmp(from,".") ? RESOLVED_TYPE_HOSTNAME :
+          (!strcmp(from, "0.0.0.0") ? RESOLVED_TYPE_IPV4 : RESOLVED_TYPE_IPV6);
         const char *address = addressmap_register_virtual_address(
-              !strcmp(from,".") ? RESOLVED_TYPE_HOSTNAME : RESOLVED_TYPE_IPV4,
-               tor_strdup(to));
+                                                     type, tor_strdup(to));
         if (!address) {
           smartlist_add_asprintf(reply,
                        "451-resource exhausted: skipping '%s'", line);
diff --git a/src/or/or.h b/src/or/or.h
index 06a74f6370..3a8e50c801 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1225,7 +1225,7 @@ typedef struct listener_connection_t {
   uint8_t isolation_flags;
   /**@}*/
 
-  /** For a SOCKS listener, these fields describe whether we should
+  /** For a SOCKS listeners, these fields describe whether we should
    * allow IPv4 and IPv6 addresses from our exit nodes, respectively.
    *
    * @{
@@ -1237,6 +1237,24 @@ typedef struct listener_connection_t {
    * addresses? */
   unsigned int socks_prefer_ipv6 : 1;
 
+  /** For a socks listener: should we cache IPv4/IPv6 DNS information that
+   * exit nodes tell us?
+   *
+   * @{ */
+  unsigned int cache_ipv4_answers : 1;
+  unsigned int cache_ipv6_answers : 1;
+  /** @} */
+  /** For a socks listeners: if we find an answer in our client-side DNS cache,
+   * should we use it?
+   *
+   * @{ */
+  unsigned int use_cached_ipv4_answers : 1;
+  unsigned int use_cached_ipv6_answers : 1;
+  /** @} */
+  /** For socks listeners: When we can automap an address to IPv4 or IPv6,
+   * do we prefer IPv6? */
+  unsigned int prefer_ipv6_virtaddr : 1;
+
 } listener_connection_t;
 
 /** Minimum length of the random part of an AUTH_CHALLENGE cell. */
@@ -1545,6 +1563,24 @@ typedef struct entry_connection_t {
   /** Should we say we prefer IPv6 traffic? */
   unsigned int prefer_ipv6_traffic : 1;
 
+  /** For a socks listener: should we cache IPv4/IPv6 DNS information that
+   * exit nodes tell us?
+   *
+   * @{ */
+  unsigned int cache_ipv4_answers : 1;
+  unsigned int cache_ipv6_answers : 1;
+  /** @} */
+  /** For a socks listeners: if we find an answer in our client-side DNS cache,
+   * should we use it?
+   *
+   * @{ */
+  unsigned int use_cached_ipv4_answers : 1;
+  unsigned int use_cached_ipv6_answers : 1;
+  /** @} */
+  /** For socks listeners: When we can automap an address to IPv4 or IPv6,
+   * do we prefer IPv6? */
+  unsigned int prefer_ipv6_virtaddr : 1;
+
 } entry_connection_t;
 
 /** Subtype of connection_t for an "directory connection" -- that is, an HTTP
@@ -3084,10 +3120,30 @@ typedef struct port_cfg_t {
   unsigned int all_addrs : 1;
   unsigned int bind_ipv4_only : 1;
   unsigned int bind_ipv6_only : 1;
+
+  /* Client port types only: */
   unsigned int ipv4_traffic : 1;
   unsigned int ipv6_traffic : 1;
   unsigned int prefer_ipv6 : 1;
 
+  /** For a socks listener: should we cache IPv4/IPv6 DNS information that
+   * exit nodes tell us?
+   *
+   * @{ */
+  unsigned int cache_ipv4_answers : 1;
+  unsigned int cache_ipv6_answers : 1;
+  /** @} */
+  /** For a socks listeners: if we find an answer in our client-side DNS cache,
+   * should we use it?
+   *
+   * @{ */
+  unsigned int use_cached_ipv4_answers : 1;
+  unsigned int use_cached_ipv6_answers : 1;
+  /** @} */
+  /** For socks listeners: When we can automap an address to IPv4 or IPv6,
+   * do we prefer IPv6? */
+  unsigned int prefer_ipv6_virtaddr : 1;
+
   /* Unix sockets only: */
   /** Path for an AF_UNIX address */
   char unix_addr[FLEXIBLE_ARRAY_MEMBER];
@@ -3568,8 +3624,10 @@ typedef struct {
   /** Should we fetch our dir info at the start of the consensus period? */
   int FetchDirInfoExtraEarly;
 
-  char *VirtualAddrNetwork; /**< Address and mask to hand out for virtual
-                             * MAPADDRESS requests. */
+  char *VirtualAddrNetworkIPv4; /**< Address and mask to hand out for virtual
+                                 * MAPADDRESS requests for IPv4 addresses */
+  char *VirtualAddrNetworkIPv6; /**< Address and mask to hand out for virtual
+                                 * MAPADDRESS requests for IPv6 addresses */
   int ServerDNSSearchDomains; /**< Boolean: If set, we don't force exit
                       * addresses to be FQDNs, but rather search for them in
                       * the local domains. */
diff --git a/src/or/relay.c b/src/or/relay.c
index 7f49299e2b..2103087ee4 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -706,6 +706,7 @@ connection_ap_process_end_not_open(
       case END_STREAM_REASON_EXITPOLICY:
         if (rh->length >= 5) {
           tor_addr_t addr;
+
           int ttl = -1;
           tor_addr_make_unspec(&addr);
           if (rh->length == 5 || rh->length == 9) {
@@ -742,9 +743,19 @@ connection_ap_process_end_not_open(
             return 0;
           }
 
-          client_dns_set_addressmap(circ,
+          client_dns_set_addressmap(conn,
                                     conn->socks_request->address, &addr,
                                     conn->chosen_exit_name, ttl);
+
+          {
+            char new_addr[TOR_ADDR_BUF_LEN];
+            tor_addr_to_str(new_addr, &addr, sizeof(new_addr), 1);
+            if (strcmp(conn->socks_request->address, new_addr)) {
+              strlcpy(conn->socks_request->address, new_addr,
+                      sizeof(conn->socks_request->address));
+              control_event_stream_status(conn, STREAM_EVENT_REMAP, 0);
+            }
+          }
         }
         /* check if he *ought* to have allowed it */
         if (exitrouter &&
@@ -757,12 +768,7 @@ connection_ap_process_end_not_open(
                  node_describe(exitrouter));
           policies_set_node_exitpolicy_to_reject_all(exitrouter);
         }
-        /* rewrite it to an IP if we learned one. */
-        if (addressmap_rewrite(conn->socks_request->address,
-                               sizeof(conn->socks_request->address),
-                               NULL, NULL)) {
-          control_event_stream_status(conn, STREAM_EVENT_REMAP, 0);
-        }
+
         if (conn->chosen_exit_optional ||
             conn->chosen_exit_retries) {
           /* stop wanting a specific exit */
@@ -972,7 +978,7 @@ connection_edge_process_relay_cell_not_open(
         return 0;
       }
 
-      client_dns_set_addressmap(TO_ORIGIN_CIRCUIT(circ),
+      client_dns_set_addressmap(entry_conn,
                                 entry_conn->socks_request->address, &addr,
                                 entry_conn->chosen_exit_name, ttl);
 
diff --git a/src/test/test_addr.c b/src/test/test_addr.c
index d2b25e5e6c..eea0fcde89 100644
--- a/src/test/test_addr.c
+++ b/src/test/test_addr.c
@@ -3,9 +3,11 @@
  * Copyright (c) 2007-2012, The Tor Project, Inc. */
 /* See LICENSE for licensing information */
 
+#define ADDRESSMAP_PRIVATE
 #include "orconfig.h"
 #include "or.h"
 #include "test.h"
+#include "addressmap.h"
 
 static void
 test_addr_basic(void)
@@ -773,6 +775,74 @@ test_addr_parse(void)
   ;
 }
 
+static void
+update_difference(int ipv6, uint8_t *d,
+                  const tor_addr_t *a, const tor_addr_t *b)
+{
+  const int n_bytes = ipv6 ? 16 : 4;
+  uint8_t a_tmp[4], b_tmp[4];
+  const uint8_t *ba, *bb;
+  int i;
+
+  if (ipv6) {
+    ba = tor_addr_to_in6_addr8(a);
+    bb = tor_addr_to_in6_addr8(b);
+  } else {
+    set_uint32(a_tmp, tor_addr_to_ipv4n(a));
+    set_uint32(b_tmp, tor_addr_to_ipv4n(b));
+    ba = a_tmp; bb = b_tmp;
+  }
+
+  for (i = 0; i < n_bytes; ++i) {
+    d[i] |= ba[i] ^ bb[i];
+  }
+}
+
+static void
+test_virtaddrmap(void *data)
+{
+  /* Let's start with a bunch of random addresses. */
+  int ipv6, bits, iter, b;
+  virtual_addr_conf_t cfg[2];
+  uint8_t bytes[16];
+
+  (void)data;
+
+  tor_addr_parse(&cfg[0].addr, "64.65.0.0");
+  tor_addr_parse(&cfg[1].addr, "3491:c0c0::");
+
+  for (ipv6 = 0; ipv6 <= 1; ++ipv6) {
+    for (bits = 0; bits < 18; ++bits) {
+      tor_addr_t last_a;
+      cfg[ipv6].bits = bits;
+      memset(bytes, 0, sizeof(bytes));
+      tor_addr_copy(&last_a, &cfg[ipv6].addr);
+      /* Generate 128 addresses with each addr/bits combination. */
+      for (iter = 0; iter < 128; ++iter) {
+        tor_addr_t a;
+
+        get_random_virtual_addr(&cfg[ipv6], &a);
+        //printf("%s\n", fmt_addr(&a));
+        /* Make sure that the first b bits match the configured network */
+        tt_int_op(0, ==, tor_addr_compare_masked(&a, &cfg[ipv6].addr,
+                                                 bits, CMP_EXACT));
+
+        /* And track which bits have been different between pairs of
+         * addresses */
+        update_difference(ipv6, bytes, &last_a, &a);
+      }
+
+      /* Now make sure all but the first 'bits' bits of bytes are true */
+      for (b = bits+1; b < (ipv6?128:32); ++b) {
+        tt_assert(1 & (bytes[b/8] >> (7-(b&7))));
+      }
+    }
+  }
+
+ done:
+  ;
+}
+
 #define ADDR_LEGACY(name)                                               \
   { #name, legacy_test_helper, 0, &legacy_setup, test_addr_ ## name }
 
@@ -780,6 +850,7 @@ struct testcase_t addr_tests[] = {
   ADDR_LEGACY(basic),
   ADDR_LEGACY(ip6_helpers),
   ADDR_LEGACY(parse),
+  { "virtaddr", test_virtaddrmap, 0, NULL, NULL },
   END_OF_TESTCASES
 };
 
diff --git a/src/test/test_config.c b/src/test/test_config.c
index e04b9dfc2e..9f6b260fea 100644
--- a/src/test/test_config.c
+++ b/src/test/test_config.c
@@ -42,6 +42,11 @@ test_config_addressmap(void *arg)
   config_get_lines(buf, &(get_options_mutable()->AddressMap), 0);
   config_register_addressmaps(get_options());
 
+/* Use old interface for now, so we don't need to rewrite the unit tests */
+#define addressmap_rewrite(a,s,eo,ao)                                   \
+  addressmap_rewrite((a),(s),AMR_FLAG_USE_IPV4_DNS|AMR_FLAG_USE_IPV6_DNS, \
+                     (eo),(ao))
+
   /* MapAddress .invalidwildcard.com .torserver.exit  - no match */
   strlcpy(address, "www.invalidwildcard.com", sizeof(address));
   test_assert(!addressmap_rewrite(address, sizeof(address), &expires, NULL));
@@ -158,6 +163,8 @@ test_config_addressmap(void *arg)
   strlcpy(address, "www.torproject.org", sizeof(address));
   test_assert(!addressmap_rewrite(address, sizeof(address), &expires, NULL));
 
+#undef addressmap_rewrite
+
  done:
   ;
 }