trafficserver-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From a..@apache.org
Subject svn commit: r1144353 [1/2] - in /trafficserver/traffic/trunk: cop/ iocore/aio/ iocore/cache/ iocore/cluster/ iocore/dns/ iocore/eventsystem/ iocore/hostdb/ iocore/net/ iocore/utils/ lib/ts/ mgmt/api/remote/ mgmt/cli/ mgmt/preparse/ mgmt/tools/ proxy/ p...
Date Fri, 08 Jul 2011 15:08:13 GMT
Author: amc
Date: Fri Jul  8 15:08:11 2011
New Revision: 1144353

URL: http://svn.apache.org/viewvc?rev=1144353&view=rev
Log:
Unfortunately a dog's breakfast of fixes I needed to get ATS working and prepare for IPv6.

1) Internal APIs were changed to use sockaddr* consistently.
2) Use of sockaddr_storage internally was minimized, in most cases an IPv6 structure suffices and is much smaller.
3) Forward transparency now works when traffic_server is directly invoked, and not just when started through the trafficserver script.
4) Added the lib directory as an include directory to a number of Makefiles as part of the transition to using lib as the base library directory.
5) Added InstrusiveDList and IpMap to TS library in preparation for IPv6.

Added:
    trafficserver/traffic/trunk/lib/ts/IntrusiveDList.h
    trafficserver/traffic/trunk/lib/ts/IpMap.cc
    trafficserver/traffic/trunk/lib/ts/IpMap.h
Modified:
    trafficserver/traffic/trunk/cop/Makefile.am
    trafficserver/traffic/trunk/iocore/aio/Makefile.am
    trafficserver/traffic/trunk/iocore/cache/Makefile.am
    trafficserver/traffic/trunk/iocore/cluster/Makefile.am
    trafficserver/traffic/trunk/iocore/dns/Makefile.am
    trafficserver/traffic/trunk/iocore/eventsystem/Makefile.am
    trafficserver/traffic/trunk/iocore/hostdb/Makefile.am
    trafficserver/traffic/trunk/iocore/net/Connection.cc
    trafficserver/traffic/trunk/iocore/net/I_NetVConnection.h
    trafficserver/traffic/trunk/iocore/net/Makefile.am
    trafficserver/traffic/trunk/iocore/net/P_Connection.h
    trafficserver/traffic/trunk/iocore/net/P_NetAccept.h
    trafficserver/traffic/trunk/iocore/net/P_NetVConnection.h
    trafficserver/traffic/trunk/iocore/net/P_UnixNetVConnection.h
    trafficserver/traffic/trunk/iocore/net/UnixConnection.cc
    trafficserver/traffic/trunk/iocore/net/UnixNetAccept.cc
    trafficserver/traffic/trunk/iocore/net/UnixNetProcessor.cc
    trafficserver/traffic/trunk/iocore/utils/Makefile.am
    trafficserver/traffic/trunk/lib/ts/Makefile.am
    trafficserver/traffic/trunk/lib/ts/ink_inet.h
    trafficserver/traffic/trunk/mgmt/api/remote/Makefile.am
    trafficserver/traffic/trunk/mgmt/cli/Makefile.am
    trafficserver/traffic/trunk/mgmt/preparse/Makefile.am
    trafficserver/traffic/trunk/mgmt/tools/Makefile.am
    trafficserver/traffic/trunk/proxy/FetchSM.cc
    trafficserver/traffic/trunk/proxy/InkAPI.cc
    trafficserver/traffic/trunk/proxy/InkAPITest.cc
    trafficserver/traffic/trunk/proxy/InkAPITestTool.cc
    trafficserver/traffic/trunk/proxy/PluginVC.cc
    trafficserver/traffic/trunk/proxy/congest/Makefile.am
    trafficserver/traffic/trunk/proxy/hdrs/Makefile.am
    trafficserver/traffic/trunk/proxy/http/HttpClientSession.cc
    trafficserver/traffic/trunk/proxy/http/HttpSM.cc
    trafficserver/traffic/trunk/proxy/http/HttpTransact.h
    trafficserver/traffic/trunk/proxy/http/Makefile.am
    trafficserver/traffic/trunk/proxy/http/remap/Makefile.am
    trafficserver/traffic/trunk/proxy/logging/Makefile.am
    trafficserver/traffic/trunk/proxy/stats/Makefile.am

Modified: trafficserver/traffic/trunk/cop/Makefile.am
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/cop/Makefile.am?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/cop/Makefile.am (original)
+++ trafficserver/traffic/trunk/cop/Makefile.am Fri Jul  8 15:08:11 2011
@@ -18,6 +18,7 @@
 #  limitations under the License.
 
 AM_CPPFLAGS = $(iocore_include_dirs) \
+  -I$(top_srcdir)/lib \
   -I$(top_srcdir)/lib/records \
   -I$(top_srcdir)/mgmt \
   -I$(top_srcdir)/mgmt/cluster \

Modified: trafficserver/traffic/trunk/iocore/aio/Makefile.am
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/aio/Makefile.am?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/aio/Makefile.am (original)
+++ trafficserver/traffic/trunk/iocore/aio/Makefile.am Fri Jul  8 15:08:11 2011
@@ -18,6 +18,7 @@
 
 AM_CPPFLAGS = \
   -I$(top_srcdir)/iocore/eventsystem \
+  -I$(top_srcdir)/lib \
   -I$(top_srcdir)/lib/records
 
 DEFS += @IOCORE_MODULARIZED_DEFS@

Modified: trafficserver/traffic/trunk/iocore/cache/Makefile.am
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/cache/Makefile.am?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/cache/Makefile.am (original)
+++ trafficserver/traffic/trunk/iocore/cache/Makefile.am Fri Jul  8 15:08:11 2011
@@ -25,6 +25,7 @@ ADD_SRC =
 else
 AM_CPPFLAGS = \
   $(iocore_include_dirs) \
+  -I$(top_srcdir)/lib \
   -I$(top_srcdir)/lib/records \
   -I$(top_srcdir)/proxy \
   -I$(top_srcdir)/proxy/hdrs \

Modified: trafficserver/traffic/trunk/iocore/cluster/Makefile.am
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/cluster/Makefile.am?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/cluster/Makefile.am (original)
+++ trafficserver/traffic/trunk/iocore/cluster/Makefile.am Fri Jul  8 15:08:11 2011
@@ -18,6 +18,7 @@
 
 AM_CPPFLAGS = \
   $(iocore_include_dirs) \
+  -I$(top_srcdir)/lib \
   -I$(top_srcdir)/lib/records \
   -I$(top_srcdir)/proxy/http \
   -I$(top_srcdir)/proxy/hdrs \

Modified: trafficserver/traffic/trunk/iocore/dns/Makefile.am
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/dns/Makefile.am?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/dns/Makefile.am (original)
+++ trafficserver/traffic/trunk/iocore/dns/Makefile.am Fri Jul  8 15:08:11 2011
@@ -23,6 +23,7 @@ AM_CPPFLAGS = \
 else
 AM_CPPFLAGS = \
   $(iocore_include_dirs) \
+  -I$(top_srcdir)/lib \
   -I$(top_srcdir)/lib/records \
   -I$(top_srcdir)/proxy \
   -I$(top_srcdir)/proxy/http \

Modified: trafficserver/traffic/trunk/iocore/eventsystem/Makefile.am
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/eventsystem/Makefile.am?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/eventsystem/Makefile.am (original)
+++ trafficserver/traffic/trunk/iocore/eventsystem/Makefile.am Fri Jul  8 15:08:11 2011
@@ -17,6 +17,7 @@
 #  limitations under the License.
 
 AM_CPPFLAGS = \
+  -I$(top_srcdir)/lib \
   -I$(top_srcdir)/lib/records
 
 DEFS += @IOCORE_MODULARIZED_DEFS@

Modified: trafficserver/traffic/trunk/iocore/hostdb/Makefile.am
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/hostdb/Makefile.am?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/hostdb/Makefile.am (original)
+++ trafficserver/traffic/trunk/iocore/hostdb/Makefile.am Fri Jul  8 15:08:11 2011
@@ -23,6 +23,7 @@ AM_CPPFLAGS = \
 else
 AM_CPPFLAGS = \
   $(iocore_include_dirs) \
+  -I$(top_srcdir)/lib \
   -I$(top_srcdir)/lib/records \
   -I$(top_srcdir)/proxy \
   -I$(top_srcdir)/proxy/hdrs \

Modified: trafficserver/traffic/trunk/iocore/net/Connection.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/net/Connection.cc?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/net/Connection.cc (original)
+++ trafficserver/traffic/trunk/iocore/net/Connection.cc Fri Jul  8 15:08:11 2011
@@ -129,8 +129,12 @@ Connection::close()
 }
 
 int
-Server::setup_fd_for_listen(bool non_blocking, int recv_bufsize, int send_bufsize)
-{
+Server::setup_fd_for_listen(
+  bool non_blocking,
+  int recv_bufsize,
+  int send_bufsize,
+  bool transparent
+) {
   int res = 0;
 #ifdef SEND_BUF_SIZE
   {
@@ -212,6 +216,20 @@ Server::setup_fd_for_listen(bool non_blo
     if ((res = safe_getsockname(fd, (struct sockaddr *) &sa, &namelen)))
       goto Lerror;
   }
+
+  if (transparent) {
+#if TS_USE_TPROXY
+    int transparent_value = 1;
+    Debug("http_tproxy", "Listen port inbound transparency enabled.\n");
+    if (setsockopt(fd, SOL_IP, TS_IP_TRANSPARENT, &transparent_value, sizeof(transparent_value)) == -1) {
+      Error("[Server::setup_fd_for_listen] Unable to set transparent socket option [%d] %s\n", errno, strerror(errno));
+      _exit(1);
+    }
+#else
+    Error("[Server::setup_fd_for_listen] Transparency requested but TPROXY not configured\n");
+#endif
+  }
+
   return 0;
 Lerror:
   res = -errno;
@@ -223,7 +241,7 @@ Lerror:
 
 
 int
-Server::listen(int port_number, int domain, bool non_blocking, int recv_bufsize, int send_bufsize)
+Server::listen(int port_number, int domain, bool non_blocking, int recv_bufsize, int send_bufsize, bool transparent)
 {
   ink_assert(fd == NO_FD);
   int res = 0;
@@ -335,6 +353,19 @@ Server::listen(int port_number, int doma
     goto Lerror;
 #endif
 
+  if (transparent) {
+#if TS_USE_TPROXY
+    int transparent_value = 1;
+    Debug("http_tproxy", "Listen port inbound transparency enabled.\n");
+    if (setsockopt(fd, SOL_IP, TS_IP_TRANSPARENT, &transparent_value, sizeof(transparent_value)) == -1) {
+      Error("[Server::listen] Unable to set transparent socket option [%d] %s\n", errno, strerror(errno));
+      _exit(1);
+    }
+#else
+    Error("[Server::listen] Transparency requested but TPROXY not configured\n");
+#endif
+  }
+
 #if defined(linux)
   if (NetProcessor::accept_mss > 0)
     if ((res = safe_setsockopt(fd, IPPROTO_TCP, TCP_MAXSEG, (char *) &NetProcessor::accept_mss, sizeof(int))) < 0)

Modified: trafficserver/traffic/trunk/iocore/net/I_NetVConnection.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/net/I_NetVConnection.h?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/net/I_NetVConnection.h (original)
+++ trafficserver/traffic/trunk/iocore/net/I_NetVConnection.h Fri Jul  8 15:08:11 2011
@@ -369,7 +369,7 @@ public:
   virtual ink_hrtime get_inactivity_timeout() = 0;
 
   /** Returns local sockaddr storage. */
-  sockaddr_storage const* get_local_addr();
+  sockaddr const* get_local_addr();
 
   /** Returns local ip. */
   unsigned int get_local_ip();
@@ -378,7 +378,7 @@ public:
   int get_local_port();
 
   /** Returns remote sockaddr storage. */
-  sockaddr_storage const* get_remote_addr();
+  sockaddr const* get_remote_addr();
 
   /** Returns remote ip. */
   unsigned int get_remote_ip();
@@ -458,8 +458,9 @@ private:
   NetVConnection & operator =(const NetVConnection &);
 
 protected:
-  struct sockaddr_storage local_addr;
-  struct sockaddr_storage remote_addr;
+  // An IPv6 struct suffices for IP addresses.
+  struct sockaddr_in6 local_addr;
+  struct sockaddr_in6 remote_addr;
 
   int got_local_addr;
   int got_remote_addr;

Modified: trafficserver/traffic/trunk/iocore/net/Makefile.am
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/net/Makefile.am?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/net/Makefile.am (original)
+++ trafficserver/traffic/trunk/iocore/net/Makefile.am Fri Jul  8 15:08:11 2011
@@ -23,6 +23,7 @@ AM_CPPFLAGS = \
 else
 AM_CPPFLAGS = \
   $(iocore_include_dirs) \
+  -I$(top_srcdir)/lib \
   -I$(top_srcdir)/lib/records \
   -I$(top_srcdir)/proxy \
   -I$(top_srcdir)/proxy/hdrs \

Modified: trafficserver/traffic/trunk/iocore/net/P_Connection.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/net/P_Connection.h?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/net/P_Connection.h (original)
+++ trafficserver/traffic/trunk/iocore/net/P_Connection.h Fri Jul  8 15:08:11 2011
@@ -81,7 +81,7 @@ struct NetVCOptions;
 struct Connection
 {
   SOCKET fd; ///< Socket for connection.
-  struct sockaddr_storage sa; ///< Remote address.
+  sockaddr_in6 sa; ///< Remote address.
   bool is_bound; ///< Flag for already bound to a local address.
   bool is_connected; ///< Flag for already connected.
 
@@ -123,11 +123,7 @@ struct Connection
 		 uint32_t addr, ///< Remote IP address.
 		 uint16_t port ///< Remote port.
 	     ) {
-    sockaddr_in* sa_in = reinterpret_cast<sockaddr_in*>(&sa);
-    sa.ss_family = AF_INET;
-    sa_in->sin_port = htons(port);
-    sa_in->sin_addr.s_addr = addr;
-    memset(&(sa_in->sin_zero), 0, 8);
+    ink_inet_ip4_set(&sa, addr, htons(port));
   }
     
   int setup_mc_send(unsigned int mc_ip, int mc_port,
@@ -181,8 +177,13 @@ struct Server: public Connection
   // converted into network byte order
   //
 
-  int listen(int port, int domain = AF_INET, bool non_blocking = false, int recv_bufsize = 0, int send_bufsize = 0);
-  int setup_fd_for_listen(bool non_blocking = false, int recv_bufsize = 0, int send_bufsize = 0);
+  int listen(int port, int domain = AF_INET, bool non_blocking = false, int recv_bufsize = 0, int send_bufsize = 0, bool transparent = false);
+  int setup_fd_for_listen(
+    bool non_blocking = false,
+    int recv_bufsize = 0,
+    int send_bufsize = 0,
+    bool transparent = false ///< Inbound transparent.
+  );
 
   Server()
     : Connection()

Modified: trafficserver/traffic/trunk/iocore/net/P_NetAccept.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/net/P_NetAccept.h?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/net/P_NetAccept.h (original)
+++ trafficserver/traffic/trunk/iocore/net/P_NetAccept.h Fri Jul  8 15:08:11 2011
@@ -112,7 +112,7 @@ struct NetAccept:public Continuation
   virtual void init_accept(EThread * t = NULL);
   virtual void init_accept_per_thread();
   // 0 == success
-  int do_listen(bool non_blocking);
+  int do_listen(bool non_blocking, bool transparent = false);
 
   int do_blocking_accept(NetAccept * master_na, EThread * t);
   virtual int acceptEvent(int event, void *e);

Modified: trafficserver/traffic/trunk/iocore/net/P_NetVConnection.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/net/P_NetVConnection.h?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/net/P_NetVConnection.h (original)
+++ trafficserver/traffic/trunk/iocore/net/P_NetVConnection.h Fri Jul  8 15:08:11 2011
@@ -23,81 +23,62 @@
 
 #include "I_NetVConnection.h"
 
-TS_INLINE sockaddr_storage const*
+TS_INLINE sockaddr const*
 NetVConnection::get_remote_addr()
 {
   if (!got_remote_addr) {
     set_remote_addr();
     got_remote_addr = 1;
   }
-  return &remote_addr;
+  return ink_inet_sa_cast(&remote_addr);
 }
 
 TS_INLINE unsigned int
 NetVConnection::get_remote_ip()
 {
-  switch (get_remote_addr()->ss_family) {
-  case AF_INET:
-    return (unsigned int)((struct sockaddr_in *)(get_remote_addr()))->sin_addr.s_addr;
-  default:
-    return 0;
-  }
+  sockaddr const* addr = this->get_remote_addr();
+  return ink_inet_is_ip4(addr)
+    ? ink_inet_ip4_addr_cast(addr)
+    : 0;
 }
 
 
+/// @return The remote port in host order.
 TS_INLINE int
 NetVConnection::get_remote_port()
 {
-  switch (get_remote_addr()->ss_family) {
-  case AF_INET:
-    return ntohs(((struct sockaddr_in *)(get_remote_addr()))->sin_port);
-  case AF_INET6:
-    return ntohs(((struct sockaddr_in6 *)(get_remote_addr()))->sin6_port);
-  default:
-    return 0;
-  }
+  return ink_inet_get_port(this->get_remote_addr());
 }
 
-TS_INLINE sockaddr_storage const*
+TS_INLINE sockaddr const*
 NetVConnection::get_local_addr()
 {
   if (!got_local_addr) {
     set_local_addr();
-    switch (local_addr.ss_family) {
-    case AF_INET:
-      if (((struct sockaddr_in *)(&local_addr))->sin_addr.s_addr || ((struct sockaddr_in *)&(local_addr))->sin_port) {
-        got_local_addr = 1;
-      }
-      break;
-    case AF_INET6:
-      if (((struct sockaddr_in6 *)(&local_addr))->sin6_addr.s6_addr || ((struct sockaddr_in6 *)(&local_addr))->sin6_port) {
-        got_local_addr = 1;
-      }
+    sockaddr* a = ink_inet_sa_cast(&local_addr); // cache required type.
+    if (
+      (ink_inet_is_ip(a) && ink_inet_port_cast(a)) // IP and has a port.
+      || (ink_inet_is_ip4(a) && ink_inet_ip4_addr_cast(a)) // IPv4
+      || (ink_inet_is_ip6(a) && !IN6_IS_ADDR_UNSPECIFIED(&ink_inet_ip6_addr_cast(a)))
+    ) {
+      got_local_addr = 1;
     }
   }
-  return &local_addr;
+  return ink_inet_sa_cast(&local_addr);
 }
 
 TS_INLINE unsigned int
 NetVConnection::get_local_ip()
 {
-  switch (get_local_addr()->ss_family) {
-  case AF_INET:
-    return (unsigned int)((struct sockaddr_in *)(get_local_addr()))->sin_addr.s_addr;
-  default:
-    return 0;
-  }
+  sockaddr const* addr = this->get_local_addr();
+  return ink_inet_is_ip4(addr)
+    ? ink_inet_ip4_addr_cast(addr)
+    : 0;
 }
 
+/// @return The local port in host order.
 TS_INLINE int
 NetVConnection::get_local_port()
 {
-  switch (get_local_addr()->ss_family) {
-  case AF_INET:
-    return ntohs(((struct sockaddr_in *)(get_local_addr()))->sin_port);
-  case AF_INET6:
-    return ntohs(((struct sockaddr_in6 *)(get_local_addr()))->sin6_port);
-  default:
-    return 0;
-  }
+  return ink_inet_get_port(this->get_local_addr());
 }

Modified: trafficserver/traffic/trunk/iocore/net/P_UnixNetVConnection.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/net/P_UnixNetVConnection.h?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/net/P_UnixNetVConnection.h (original)
+++ trafficserver/traffic/trunk/iocore/net/P_UnixNetVConnection.h Fri Jul  8 15:08:11 2011
@@ -257,7 +257,7 @@ TS_INLINE void
 UnixNetVConnection::set_local_addr()
 {
   int local_sa_size = sizeof(local_addr);
-  safe_getsockname(con.fd, (sockaddr *) & local_addr, &local_sa_size);
+  safe_getsockname(con.fd, ink_inet_sa_cast(&local_addr), &local_sa_size);
 }
 
 TS_INLINE ink_hrtime

Modified: trafficserver/traffic/trunk/iocore/net/UnixConnection.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/net/UnixConnection.cc?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/net/UnixConnection.cc (original)
+++ trafficserver/traffic/trunk/iocore/net/UnixConnection.cc Fri Jul  8 15:08:11 2011
@@ -53,6 +53,8 @@ Connection::setup_mc_send(unsigned int m
   ink_assert(fd == NO_FD);
   int res = 0;
   int enable_reuseaddr = 1;
+  sockaddr_in* sa_in = ink_inet_ip4_cast(&sa);
+  sockaddr_in bind_sa;
 
   if ((res = socketManager.mc_socket(AF_INET, SOCK_DGRAM, 0, non_blocking)) < 0)
     goto Lerror;
@@ -63,19 +65,12 @@ Connection::setup_mc_send(unsigned int m
     goto Lerror;
   }
 
-  struct sockaddr_in bind_sa;
-  memset(&bind_sa, 0, sizeof(bind_sa));
-  bind_sa.sin_family = AF_INET;
-  bind_sa.sin_port = htons(my_port);
-  bind_sa.sin_addr.s_addr = my_ip;
+  ink_inet_ip4_set(&bind_sa, my_ip, htons(my_port));
   if ((res = socketManager.ink_bind(fd, (struct sockaddr *) &bind_sa, sizeof(bind_sa), IPPROTO_UDP)) < 0) {
     goto Lerror;
   }
 
-  sa.ss_family = AF_INET;
-  ((struct sockaddr_in *)(&sa))->sin_port = htons(mc_port);
-  ((struct sockaddr_in *)(&sa))->sin_addr.s_addr = mc_ip;
-  memset(&(((struct sockaddr_in *)(&sa))->sin_zero), 0, 8);
+  ink_inet_ip4_set(sa_in, mc_ip, htons(mc_port));
 
 #ifdef SET_CLOSE_ON_EXEC
   if ((res = safe_fcntl(fd, F_SETFD, 1)) < 0)
@@ -116,6 +111,7 @@ Connection::setup_mc_receive(unsigned in
   (void) c;
   int res = 0;
   int enable_reuseaddr = 1;
+  sockaddr_in* sa_in = ink_inet_ip4_cast(&sa);
 
   if ((res = socketManager.socket(AF_INET, SOCK_DGRAM, 0)) < 0)
     goto Lerror;
@@ -130,10 +126,7 @@ Connection::setup_mc_receive(unsigned in
   if ((res = safe_setsockopt(fd, SOL_SOCKET, SO_REUSEADDR, (char *) &enable_reuseaddr, sizeof(enable_reuseaddr)) < 0))
     goto Lerror;
 
-  memset(&sa, 0, sizeof(sa));
-  sa.ss_family = AF_INET;
-  ((struct sockaddr_in *)(&sa))->sin_addr.s_addr = mc_ip;
-  ((struct sockaddr_in *)(&sa))->sin_port = htons(mc_port);
+  ink_inet_ip4_set(sa_in, mc_ip, htons(mc_port));
 
   if ((res = socketManager.ink_bind(fd, (struct sockaddr *) &sa, sizeof(sa), IPPROTO_TCP)) < 0)
     goto Lerror;
@@ -298,13 +291,8 @@ Connection::open(NetVCOptions const& opt
 
   // Local address/port.
   struct sockaddr_in bind_sa;
-  memset(&bind_sa, 0, sizeof(bind_sa));
-  bind_sa.sin_family = AF_INET;
-  bind_sa.sin_port = htons(local_port);
-  bind_sa.sin_addr.s_addr = local_addr;
-  if (-1 == socketManager.ink_bind(fd,
-				   reinterpret_cast<struct sockaddr *>(&bind_sa),
-				   sizeof(bind_sa)))
+  ink_inet_ip4_set(&bind_sa, local_addr, htons(local_port));
+  if (-1==socketManager.ink_bind(fd,ink_inet_sa_cast(&bind_sa),sizeof bind_sa))
     return -errno;
 
   cleanup.reset();

Modified: trafficserver/traffic/trunk/iocore/net/UnixNetAccept.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/net/UnixNetAccept.cc?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/net/UnixNetAccept.cc (original)
+++ trafficserver/traffic/trunk/iocore/net/UnixNetAccept.cc Fri Jul  8 15:08:11 2011
@@ -125,10 +125,12 @@ net_accept(NetAccept * na, void *ep, boo
     vc->action_ = *na->action_;
     vc->set_is_transparent(na->server.f_inbound_transparent);
     vc->set_is_other_side_transparent(na->server.f_outbound_transparent);
-    Debug("http_tproxy", "Marking accepted %sconnection on %x as%s outbound transparent.\n",
-	  na->server.f_inbound_transparent ? "transparent " : "",
-	  na, na->server.f_outbound_transparent ? "" : " not"
-	  );
+    Debug(
+      "http_tproxy",
+      "Marking accepted %sconnection on %x as%s outbound transparent.\n",
+      na->server.f_inbound_transparent ? "inbound transparent " : "",
+      na, na->server.f_outbound_transparent ? "" : " not"
+    );
     vc->closed  = 0;
     SET_CONTINUATION_HANDLER(vc, (NetVConnHandler) & UnixNetVConnection::acceptEvent);
 
@@ -265,18 +267,18 @@ NetAccept::init_accept_per_thread()
 
 
 int
-NetAccept::do_listen(bool non_blocking)
+NetAccept::do_listen(bool non_blocking, bool transparent)
 {
   int res = 0;
 
   if (server.fd != NO_FD) {
-    if ((res = server.setup_fd_for_listen(non_blocking, recv_bufsize, send_bufsize))) {
+    if ((res = server.setup_fd_for_listen(non_blocking, recv_bufsize, send_bufsize, transparent))) {
       Warning("unable to listen on main accept port %d: errno = %d, %s", port, errno, strerror(errno));
       goto Lretry;
     }
   } else {
   Lretry:
-    if ((res = server.listen(port, domain, non_blocking, recv_bufsize, send_bufsize)))
+    if ((res = server.listen(port, domain, non_blocking, recv_bufsize, send_bufsize, transparent)))
       Warning("unable to listen on port %d: %d %d, %s", port, res, errno, strerror(errno));
   }
   if (callback_on_open && !action_->cancelled) {
@@ -347,8 +349,8 @@ NetAccept::do_blocking_accept(NetAccept 
     vc->accept_port = ntohs(((struct sockaddr_in *)(&(server.sa)))->sin_port);
     vc->set_is_transparent(master_na->server.f_inbound_transparent);
     vc->set_is_other_side_transparent(master_na->server.f_outbound_transparent);
-    Debug("http_tproxy", "Marking accepted %sconnect on %x as%s outbound transparent.\n",
-	  master_na->server.f_inbound_transparent ? "transparent " : "",
+    Debug("http_tproxy", "Marking accepted %sconnection on %x as%s outbound transparent.\n",
+	  master_na->server.f_inbound_transparent ? "inbound transparent " : "",
 	  master_na, master_na->server.f_outbound_transparent ? "" : " not"
 	  );
     vc->mutex = new_ProxyMutex();

Modified: trafficserver/traffic/trunk/iocore/net/UnixNetProcessor.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/net/UnixNetProcessor.cc?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/net/UnixNetProcessor.cc (original)
+++ trafficserver/traffic/trunk/iocore/net/UnixNetProcessor.cc Fri Jul  8 15:08:11 2011
@@ -170,7 +170,17 @@ UnixNetProcessor::accept_internal(Contin
   na->server.accept_ip_str = accept_ip_str;
   na->server.f_outbound_transparent = opt.f_outbound_transparent;
   na->server.f_inbound_transparent = opt.f_inbound_transparent;
-  if (opt.f_outbound_transparent) Debug("http_tproxy", "Marking accept server %x on port %d as outbound transparent.\n", na, opt.port);
+  if (opt.f_outbound_transparent || opt.f_inbound_transparent) {
+    Debug(
+      "http_tproxy",
+      "Marking accept server %x on port %d as %s%s%s transparent.\n",
+      na, opt.port,
+      (opt.f_outbound_transparent ? "outbound" : ""),
+      (opt.f_outbound_transparent && opt.f_inbound_transparent ? ", " : ""),
+      (opt.f_inbound_transparent ? "inbound" : "")
+    );
+  }
+
   na->action_ = NEW(new NetAcceptAction());
   *na->action_ = cont;
   na->action_->server = &na->server;
@@ -183,7 +193,7 @@ UnixNetProcessor::accept_internal(Contin
     na->mutex = cont->mutex;
   if (frequent_accept) { // true
     if (accept_threads > 0)  {
-      if (0 == na->do_listen(BLOCKING)) {
+      if (0 == na->do_listen(BLOCKING, opt.f_inbound_transparent)) {
         NetAccept *a;
 
         for (int i=1; i < accept_threads; ++i) {

Modified: trafficserver/traffic/trunk/iocore/utils/Makefile.am
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/iocore/utils/Makefile.am?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/iocore/utils/Makefile.am (original)
+++ trafficserver/traffic/trunk/iocore/utils/Makefile.am Fri Jul  8 15:08:11 2011
@@ -17,6 +17,7 @@
 #  limitations under the License.
 
 AM_CPPFLAGS = \
+  -I$(top_srcdir)/lib \
   -I$(top_srcdir)/lib/records \
   -I$(top_srcdir)/iocore/eventsystem
 

Added: trafficserver/traffic/trunk/lib/ts/IntrusiveDList.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/lib/ts/IntrusiveDList.h?rev=1144353&view=auto
==============================================================================
--- trafficserver/traffic/trunk/lib/ts/IntrusiveDList.h (added)
+++ trafficserver/traffic/trunk/lib/ts/IntrusiveDList.h Fri Jul  8 15:08:11 2011
@@ -0,0 +1,279 @@
+# if ! defined(TS_INTRUSIVE_DOUBLE_LIST_HEADER)
+# define TS_INTRUSIVE_DOUBLE_LIST_HEADER
+
+# if USE_STL
+#   include <iterator>
+# else
+namespace std {
+  struct bidirectional_iterator_tag;
+}
+# endif
+
+/** @file
+
+    Intrusive double linked list container.
+
+    This holds items in a doubly linked list using members of the
+    items.  Elements are copied in to the list. No memory management
+    is done by the list implementation.
+
+    To use this class a client should create the structure for
+    elements of the list and ensure that it has two self pointers to
+    be used by the list. For example,
+
+    @code
+      struct Elt {
+        int _payload;
+        Elt* _next;
+        Elt* _prev;
+      };
+    @endcode
+  
+    The list is declared as
+    @code
+      typedef IntrusiveDList<Elt, &Elt::_next, &Elt::_prev> EltList;
+    @endcode
+  
+    An element can be in multiple types of lists simultaneously as
+    long as each list type uses distinct members. It is not possible
+    for an element to be in more than one list of the same type
+    simultaneously.  This is intrinsic to intrusive list support.
+
+    Element access is done by using either STL style iteration, or
+    direct access to the member pointers. A client can have its own
+    mechanism for getting an element to start, or use the @c getHead
+    and/or @c getTail methods to get the first and last elements in
+    the list respectively.
+
+    @note This is a header only library.
+
+    @note Due to bugs in either the C++ standard or gcc (or both), the
+    link members @b must be declared in the class used for the
+    list. If they are declared in a super class you will get "could
+    not convert template argument" errors, even though it should
+    work. This is because @c &T::m is of type @c S::* if @c S is a
+    super class of @c T and @c m is declared in @c S. My view is that
+    if I write "&T::m" I want a "T::*" and the compiler shouldn't go
+    rummaging through the class hierarchy for some other type. For
+    MSVC you can @c static_cast the template arguments as a
+    workaround, but not in gcc.
+
+    @section license License
+
+    Licensed to the Apache Software Foundation (ASF) under one
+    or more contributor license agreements.  See the NOTICE file
+    distributed with this work for additional information
+    regarding copyright ownership.  The ASF licenses this file
+    to you under the Apache License, Version 2.0 (the
+    "License"); you may not use this file except in compliance
+    with the License.  You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+    Unless required by applicable law or agreed to in writing, software
+    distributed under the License is distributed on an "AS IS" BASIS,
+    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+    See the License for the specific language governing permissions and
+    limitations under the License.
+
+ */
+template <
+  typename T, ///< Type of list element.
+  T* (T::*N), ///< Member to use for pointer to next element.
+  T* (T::*P)  ///< Member to use for pointer to previous element.
+> class IntrusiveDList {
+  friend class iterator;
+public:
+  typedef IntrusiveDList self; ///< Self reference type.
+  typedef T element_type; ///< Type of list element.
+  /** STL style iterator for access to elements.
+   */
+  class iterator {
+    friend class IntrusiveDList;
+  public:
+    typedef iterator self; ///< Self reference type.
+    typedef T value_type; ///< Referenced type for iterator.
+    typedef int difference_type; ///< Distance type.
+    typedef T* pointer; ///< Pointer to referent.
+    typedef T& reference; ///< Reference to referent.
+    typedef std::bidirectional_iterator_tag iterator_category;
+
+    /// Default constructor.
+    iterator() : _list(0), _elt(0) {}
+    /// Equality test.
+    /// @return @c true if @c this and @a that refer to the same object.
+    bool operator==(self const& that) const {
+      return _list == that._list && _elt == that._elt;
+    }
+    /// Pre-increment.
+    /// Move to the next element in the list.
+    /// @return The iterator.
+    self& operator++() {
+      if (_elt) _elt = _elt->*N;
+      return *this;
+    }
+    /// Pre-decrement.
+    /// Move to the previous element in the list.
+    /// @return The iterator.
+    self& operator--() {
+      if (_elt) _elt = _elt->*P;
+      else if (_list) _elt = _list->_tail;
+      return *this;
+    }
+    /// Post-increment.
+    /// Move to the next element in the list.
+    /// @return The iterator value before the increment.
+    self operator++(int) {
+      self tmp(*this);
+      ++*this;
+      return tmp;
+    }
+    /// Post-decrement.
+    /// Move to the previous element in the list.
+    /// @return The iterator value before the decrement.
+    self operator--(int) {
+      self tmp(*this);
+      ++*this;
+      return tmp;
+    }
+    /// Inequality test.
+    /// @return @c true if @c this and @a do not refer to the same object.
+    bool operator!=(self const& that) const { return !(*this == that); }
+    /// Dereference.
+    /// @return A reference to the referent.
+    reference operator*() { return *_elt; }
+    /// Dereference.
+    /// @return A pointer to the referent.
+    pointer operator->() { return _elt; }
+  protected:
+    IntrusiveDList* _list; ///< List for this iterator.
+    T* _elt; ///< Referenced element.
+    /// Internal constructor for containers.
+    iterator(
+      IntrusiveDList* container, ///< Container for iteration.
+      T* elt ///< Initial referent
+    ) : _list(container), _elt(elt) {
+    }
+  };
+
+  /// Default constructor (empty list).
+  IntrusiveDList() : _head(0), _tail(0) { }
+  /// Empty check.
+  /// @return @c true if the list is empty.
+  bool isEmpty() const { return 0 == _head; }
+  /// Add @a elt as the first element in the list.
+  /// @return This container.
+  self& prepend(
+    T* elt ///< Element to add.
+  ) {
+    elt->*N = _head;
+    elt->*P = 0;
+    if (_head) _head->*P = elt;
+    _head = elt;
+    if (! _tail) _tail = _head; // empty to non-empty transition
+    return *this;
+  }
+  /// Add @elt as the last element in the list.
+  /// @return This container.
+  self& append(
+    T* elt ///< Element to add.
+  ) {
+    elt->*N = 0;
+    elt->*P = _tail;
+    if (_tail) _tail->*N = elt;
+    _tail = elt;
+    if (! _head) _head = _tail; // empty to non-empty transition
+    return *this;
+  }
+  /// Remove the first element of the list.
+  /// @return A poiner to the removed item, or @c NULL if the list was empty.
+  T* takeHead() {
+    T* zret = 0;
+    if (_head) {
+      zret = _head;
+      _head = _head->*N;
+      if (_head) _head->*P = 0;
+      else _tail = 0; // non-empty to empty transition.
+      zret->*N = 0; // erase traces of list.
+      zret->*P = 0;
+    }
+    return zret;
+  }
+  /// Remove the last element of the list.
+  /// @return A poiner to the removed item, or @c NULL if the list was empty.
+  T* takeTail() {
+    T* zret = 0;
+    if (_tail) {
+      zret = _tail;
+      _tail = _tail->*P = 0;
+      if (_tail) _tail->*N = 0;
+      else _head = 0; // non-empty to empty transition.
+      zret->*N = 0; // erase traces of list.
+      zret->*P = 0;
+    }
+    return zret;
+  }
+  /// Insert a new element @a elt after @a target.
+  /// The caller is responsible for ensuring @a target is in this list
+  /// and @a elt is not in a list.
+  /// @return This list.
+  self& insertAfter(
+    T* target, ///< Target element in list.
+    T* elt ///< Element to insert.
+  ) {
+    // Should assert that !(elt->*N || elt->*P)
+    elt->*N = target->*N;
+    elt->*P = target;
+    target->*N = elt;
+    if (elt->*N) elt->*N->*P = elt;
+    if (target == _tail) _tail = elt;
+    return *this;
+  }
+  /// Insert a new element @a elt before @a target.
+  /// The caller is responsible for ensuring @a target is in this list
+  /// and @a elt is not in a list.
+  /// @return This list.
+  self& insertBefore(
+    T* target, ///< Target element in list.
+    T* elt ///< Element to insert.
+  ) {
+    // Should assert that !(elt->*N || elt->*P)
+    elt->*P = target->*P;
+    elt->*N = target;
+    target->*P = elt;
+    if (elt->*P) elt->*P->*N = elt;
+    if (target == _head) _head = elt;
+    return *this;
+  }
+  /// Take @a elt out of this list.
+  /// @return This list.
+  self& take(
+    T* elt ///< Element to remove.
+  ) {
+    if (elt->*P) elt->*P->*N = elt->*N;
+    if (elt->*N) elt->*N->*P = elt->*P;
+    if (elt == _head) _head = elt->*N;
+    if (elt == _tail) _tail = elt->*P;
+    elt->*P = elt->*N = 0;
+    return *this;
+  }
+  /// Remove all elements.
+  /// @note @b No memory management is done!
+  /// @return This container.
+  self& clear() { _head = _tail = 0; return *this; }
+
+  /// Get an iterator to the first element.
+  iterator begin() { return iterator(this, _head); }
+  /// Get an iterator to past the last element.
+  iterator end() { return iterator(this, 0); }
+  /// Get the first element.
+  T* getHead() { return _head; }
+  /// Get the last element.
+  T* getTail() { return _tail; }
+protected:
+  T* _head; ///< First element in list.
+  T* _tail; ///< Last element in list.
+};
+
+# endif // TS_INTRUSIVE_DOUBLE_LIST_HEADER
+

Added: trafficserver/traffic/trunk/lib/ts/IpMap.cc
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/lib/ts/IpMap.cc?rev=1144353&view=auto
==============================================================================
--- trafficserver/traffic/trunk/lib/ts/IpMap.cc (added)
+++ trafficserver/traffic/trunk/lib/ts/IpMap.cc Fri Jul  8 15:08:11 2011
@@ -0,0 +1,1114 @@
+# include "IpMap.h"
+// # include <iostream>
+
+/*  Don't bother to look at this code if you don't know how a
+    red/black tree works. There are so many good references on the
+    subject it's a waste to have some inferior version here. The
+    methods on @c Node follow the standard implementation except for
+    being parameterized by direction (so that, for instance, right
+    rotate and left rotate are both done by the @c rotate method with
+    a direction argument).
+*/
+
+// Validation / printing disabled until I figure out how to generalize so
+// as to not tie reporting into a particular project environment.
+
+namespace ts { namespace detail {
+
+/// Equality.
+/// @note If @a n is @c NULL it is treated as having the color @c BLACK.
+/// @return @c true if @a c and the color of @a n are the same.
+inline bool operator == ( RBNode* n, RBNode::Color c ) {
+  return c == ( n ? n->getColor() : RBNode::BLACK);
+}
+/// Equality.
+/// @note If @a n is @c NULL it is treated as having the color @c BLACK.
+/// @return @c true if @a c and the color of @a n are the same.
+inline bool operator == ( RBNode::Color c, RBNode* n ) {
+  return n == c;
+}
+
+inline RBNode*
+RBNode::getChild(Direction d) const {
+  return d == RIGHT ? _right
+    : d == LEFT ? _left
+    : 0
+    ;
+}
+
+RBNode*
+RBNode::rotate(Direction d) {
+  self* parent = _parent; // Cache because it can change before we use it.
+  Direction child_dir = _parent ? _parent->getChildDirection(this) : NONE;
+  Direction other_dir = this->flip(d);
+  self* child = this;
+
+  if (d != NONE && this->getChild(other_dir)) {
+    child = this->getChild(other_dir);
+    this->clearChild(other_dir);
+    this->setChild(child->getChild(d), other_dir);
+    child->clearChild(d);
+    child->setChild(this, d);
+    child->structureFixup();
+    this->structureFixup();
+    if (parent) {
+      parent->clearChild(child_dir);
+      parent->setChild(child, child_dir);
+    } else {
+      child->_parent = 0;
+    }
+  }
+  return child;
+}
+
+RBNode*
+RBNode::setChild(self* n, Direction d) {
+  if (n) n->_parent = this;
+  if (d == RIGHT) _right = n;
+  else if (d == LEFT) _left = n;
+  return n;
+}
+
+// Returns the root node
+RBNode*
+RBNode::rippleStructureFixup() {
+  self* root = this; // last node seen, root node at the end
+  self* p = this;
+  while (p) {
+    p->structureFixup();
+    root = p;
+    p = root->_parent;
+  }
+  return root;
+}
+
+void
+RBNode::replaceWith(self* n) {
+  n->_color = _color;
+  if (_parent) {
+    Direction d = _parent->getChildDirection(this);
+    _parent->setChild(0, d);
+    if (_parent != n) _parent->setChild(n, d);
+  } else {
+    n->_parent = 0;
+  }
+  n->_left = n->_right = 0;
+  if (_left && _left != n) n->setChild(_left, LEFT);
+  if (_right && _right != n) n->setChild(_right, RIGHT);
+  _left = _right = 0;
+}
+
+/* Rebalance the tree. This node is the unbalanced node. */
+RBNode*
+RBNode::rebalanceAfterInsert() {
+  self* x(this); // the node with the imbalance
+
+  while (x && x->_parent == RED) {
+    Direction child_dir = NONE;
+        
+    if (x->_parent->_parent)
+      child_dir = x->_parent->_parent->getChildDirection(x->_parent);
+    else
+      break;
+    Direction other_dir(flip(child_dir));
+        
+    self* y = x->_parent->_parent->getChild(other_dir);
+    if (y == RED) {
+      x->_parent->_color = BLACK;
+      y->_color = BLACK;
+      x = x->_parent->_parent;
+      x->_color = RED;
+    } else {
+      if (x->_parent->getChild(other_dir) == x) {
+        x = x->_parent;
+        x->rotate(child_dir);
+      }
+      // Note setting the parent color to BLACK causes the loop to exit.
+      x->_parent->_color = BLACK;
+      x->_parent->_parent->_color = RED;
+      x->_parent->_parent->rotate(other_dir);
+    }
+  }
+    
+  // every node above this one has a subtree structure change,
+  // so notify it. serendipitously, this makes it easy to return
+  // the new root node.
+  self* root = this->rippleStructureFixup();
+  root->_color = BLACK;
+
+  return root;
+}
+
+
+// Returns new root node
+RBNode*
+RBNode::remove() {
+  self* root = 0; // new root node, returned to caller
+
+  /*  Handle two special cases first.
+      - This is the only node in the tree, return a new root of NIL
+      - This is the root node with only one child, return that child as new root
+  */
+  if (!_parent && !(_left && _right)) {
+    if (_left) {
+      _left->_parent = 0;
+      root = _left;
+      root->_color = BLACK;
+    } else if (_right) {
+      _right->_parent = 0;
+      root = _right;
+      root->_color = BLACK;
+    } // else that was the only node, so leave @a root @c NULL.
+    return root;
+  }
+
+  /*  The node to be removed from the tree.
+      If @c this (the target node) has both children, we remove
+      its successor, which cannot have a left child and
+      put that node in place of the target node. Otherwise this
+      node has at most one child, so we can remove it.
+      Note that the successor of a node with a right child is always
+      a right descendant of the node. Therefore, remove_node
+      is an element of the tree rooted at this node.
+      Because of the initial special case checks, we know
+      that remove_node is @b not the root node.
+  */
+  self* remove_node(_left && _right ? _next : this);
+
+  // This is the color of the node physically removed from the tree.
+  // Normally this is the color of @a remove_node
+  Color remove_color = remove_node->_color;
+  // Need to remember the direction from @a remove_node to @a splice_node
+  Direction d(NONE);
+
+  // The child node that will be promoted to replace the removed node.
+  // The choice of left or right is irrelevant, as remove_node has at
+  // most one child (and splice_node may be NIL if remove_node has no
+  // children).
+  self* splice_node(remove_node->_left
+    ? remove_node->_left
+    : remove_node->_right
+  );
+
+  if (splice_node) {
+    // @c replace_with copies color so in this case the actual color
+    // lost is that of the splice_node.
+    remove_color = splice_node->_color;
+    remove_node->replaceWith(splice_node);
+  } else {
+    // No children on remove node so we can just clip it off the tree
+    // We update splice_node to maintain the invariant that it is
+    // the node where the physical removal occurred.
+    splice_node = remove_node->_parent;
+    // Keep @a d up to date.
+    d = splice_node->getChildDirection(remove_node);
+    splice_node->setChild(0, d);
+  }
+
+  // If the node to pull out of the tree isn't this one, 
+  // then replace this node in the tree with that removed
+  // node in liu of copying the data over.
+  if (remove_node != this) {
+    // Don't leave @a splice_node referring to a removed node
+    if (splice_node == this) splice_node = remove_node;
+    this->replaceWith(remove_node);
+  }
+
+  root = splice_node->rebalanceAfterRemove(remove_color, d);
+  root->_color = BLACK;
+  return root;
+}
+
+/**
+ * Rebalance tree after a deletion
+ * Called on the spliced in node or its parent, whichever is not NIL.
+ * This modifies the tree structure only if @a c is @c BLACK.
+ */
+RBNode*
+RBNode::rebalanceAfterRemove(
+  Color c, //!< The color of the removed node
+  Direction d //!< Direction of removed node from its parent
+) {
+  self* root;
+
+  if (BLACK == c) { // only rebalance if too much black
+    self* n = this;
+    self* parent = n->_parent;
+
+    // If @a direction is set, then we need to start at a leaf psuedo-node.
+    // This is why we need @a parent, otherwise we could just use @a n.
+    if (NONE != d) {
+      parent = n;
+      n = 0;
+    }
+
+    while (parent) { // @a n is not the root
+      // If the current node is RED, we can just recolor and be done
+      if (n == RED) {
+        n->_color = BLACK;
+        break;
+      } else {
+        // Parameterizing the rebalance logic on the directions. We
+        // write for the left child case and flip directions for the
+        // right child case
+        Direction near(LEFT), far(RIGHT);
+        if (
+          (NONE == d && parent->getChildDirection(n) == RIGHT)
+          || RIGHT == d
+        ) {
+          near = RIGHT;
+          far = LEFT;
+        }
+
+        self* w = parent->getChild(far); // sibling(n)
+
+        if (w->_color == RED) {
+          w->_color = BLACK;
+          parent->_color = RED;
+          parent->rotate(near);
+          w = parent->getChild(far);
+        }
+
+        self* wfc = w->getChild(far);
+        if (w->getChild(near) == BLACK && wfc == BLACK) {
+          w->_color = RED;
+          n = parent;
+          parent = n->_parent;
+          d = NONE; // Cancel any leaf node logic
+        } else {
+          if (wfc->_color == BLACK) {
+            w->getChild(near)->_color = BLACK;
+            w->_color = RED;
+            w->rotate(far);
+            w = parent->getChild(far);
+            wfc = w->getChild(far); // w changed, update far child cache.
+          }
+          w->_color = parent->_color;
+          parent->_color = BLACK;
+          wfc->_color = BLACK;
+          parent->rotate(near);
+          break;
+        }
+      }
+    }
+  }
+  root = this->rippleStructureFixup();
+  return root;
+}
+
+/** Ensure that the local information associated with each node is
+    correct globally This should only be called on debug builds as it
+    breaks any efficiencies we have gained from our tree structure.
+    */
+int
+RBNode::validate() {
+# if 0
+  int black_ht = 0;
+  int black_ht1, black_ht2;
+
+  if (_left) {
+    black_ht1 = _left->validate();
+  }
+  else
+    black_ht1 = 1;
+
+  if (black_ht1 > 0 && _right)
+    black_ht2 = _right->validate();
+  else
+    black_ht2 = 1;
+
+  if (black_ht1 == black_ht2) {
+    black_ht = black_ht1;
+    if (this->_color == BLACK)
+      ++black_ht;
+    else {	// No red-red
+      if (_left == RED)
+        black_ht = 0;
+      else if (_right == RED)
+        black_ht = 0;
+      if (black_ht == 0)
+        std::cout << "Red-red child\n";
+    }
+  } else {
+    std::cout << "Height mismatch " << black_ht1 << " " << black_ht2 << "\n";
+  }
+  if (black_ht > 0 && !this->structureValidate())
+    black_ht = 0;
+
+  return black_ht;
+# else
+  return 0;
+# endif
+}
+
+/** Base template class for IP maps.
+    This class is templated by the @a N type which must be a subclass
+    of @c RBNode. This class carries information about the addresses stored
+    in the map. This includes the type, the common argument type, and
+    some utility methods to operate on the address.
+*/
+template <
+  typename N ///< Node type.
+> struct IpMapBase {
+  friend class ::IpMap;
+  
+  typedef IpMapBase self; ///< Self reference type.
+  typedef typename N::ArgType ArgType; ///< Import type.
+  typedef typename N::Metric Metric;   ///< Import type.g482
+
+  IpMapBase() : _root(0) {}
+  ~IpMapBase() { this->erase(); }
+
+  /** Mark a range.
+      All addresses in the range [ @a min , @a max ] are marked with @a data.
+      @return This object.
+  */
+  self& mark(
+    ArgType min, ///< Minimum value in range.
+    ArgType max, ///< Maximum value in range.
+    void* data = 0     ///< Client data payload.
+  );
+  /** Unmark addresses.
+
+      All addresses in the range [ @a min , @a max ] are cleared
+      (removed from the map), no longer marked.
+
+      @return This object.
+  */
+  self& unmark(
+    ArgType min,
+    ArgType max
+  );
+
+  /** Test for membership.
+
+      @return @c true if the address is in the map, @c false if not.
+      If the address is in the map and @a ptr is not @c NULL, @c *ptr
+      is set to the client data for the address.
+  */
+  bool contains(
+    ArgType target, ///< Search target value.
+    void **ptr = 0 ///< Client data return.
+  );
+
+  /** Erase entire map.
+
+      All addresses are discarded.
+
+      @note This is much faster than using @c unmark with a range of
+      all addresses.
+
+      @return This map.
+  */
+  self& erase();
+
+  /** Lower bound for @a target.  @return The node whose minimum value
+      is the largest that is not greater than @a target, or @c NULL if
+      all minimum values are larger than @a target.
+  */
+  N* lowerBound(ArgType target);
+
+  /** Insert @a n after @a spot.
+      Caller is responsible for ensuring that @a spot is in this container
+      and the proper location for @a n.
+  */
+  void insertAfter(
+    N* spot, ///< Node in list.
+    N* n ///< Node to insert.
+  );
+  /** Insert @a n before @a spot.
+      Caller is responsible for ensuring that @a spot is in this container
+      and the proper location for @a n.
+  */
+  void insertBefore(
+    N* spot, ///< Node in list.
+    N* n ///< Node to insert.
+  );
+  /// Add node @a n as the first node.
+  void prepend(
+    N* n
+  );
+  /// Add node @a n as the last node.
+  void append(
+    N* n
+  );
+  /// Remove a node.
+  void remove(
+    N* n ///< Node to remove.
+  );
+
+  /** Validate internal data structures.
+      @note Intended for debugging, not general client use.
+  */
+  void validate();
+
+  /// Print all spans.
+  /// @return This map.
+  self& print();
+  
+  // Helper methods.
+  N* prev(RBNode* n) { return static_cast<N*>(n->_prev); }
+  N* next(RBNode* n) { return static_cast<N*>(n->_next); }
+  N* parent(RBNode* n) { return static_cast<N*>(n->_parent); }
+  N* left(RBNode* n) { return static_cast<N*>(n->_left); }
+  N* right(RBNode* n) { return static_cast<N*>(n->_right); }
+  N* getHead() { return static_cast<N*>(_list.getHead()); }
+  N* getTail() { return static_cast<N*>(_list.getTail()); }
+
+  N* _root; ///< Root node.
+  /// In order list of nodes.
+  /// For ugly compiler reasons, this is a list of base class pointers
+  /// even though we really store @a N instances on it.
+  typedef IntrusiveDList<RBNode, &RBNode::_next, &RBNode::_prev> NodeList;
+  /// This keeps track of all allocated nodes in order.
+  /// Iteration depends on this list being maintained.
+  NodeList _list;
+};
+
+template < typename N > N*
+IpMapBase<N>::lowerBound(ArgType target) {
+  N* n = _root; // current node to test.
+  N* zret = 0; // best node so far.
+  while (n) {
+    if (target < n->_min) n = left(n);
+    else {
+      zret = n; // this is a better candidate.
+      if (n->_max < target) n = right(n);
+      else break;
+    }
+  }
+  return zret;
+}
+
+template < typename N > IpMapBase<N>&
+IpMapBase<N>::erase() {
+  // Delete everything.
+  N* n = static_cast<N*>(_list.getHead());
+  while (n) {
+    N* x = n;
+    n = next(n);
+    delete x;
+  }
+  _list.clear();
+  _root = 0;
+  return *this;
+}
+
+template < typename N > IpMapBase<N>&
+IpMapBase<N>::mark(ArgType min, ArgType max, void* payload) {
+  N* n = this->lowerBound(min); // current node.
+  N* x = 0; // New node, gets set if we re-use an existing one.
+
+  /*  We have lots of special cases here primarily to minimize memory allocation
+      by re-using an existing node as often as possible.
+  */
+  if (n) {
+    Metric min_1 = N::deref(min);
+    N::dec(min_1);
+    if (n->_min == min) {
+      // Could be another span further left which is adjacent.
+      // Coalesce if the data is the same.
+      if (n->_prev && prev(n)->_data == payload && prev(n)->_max == min_1) {
+        x = prev(n);
+        n = x; // need to back up n because we've moved our frame of reference back.
+        x->setMax(max);
+      } else if (n->_max <= max) {
+        // Span will be subsumed by request span so it's available for use.
+        x = n;
+        x->setMax(max).setData(payload);
+      } else if (n->_data == payload) {
+        return *this; // request is covered by existing span with the same data
+      } else {
+        Metric max_plus = N::deref(max);
+        N::inc(max_plus);
+        // request span is covered by existing span.
+        x = new N(min, max, payload); //
+        n->setMin(max_plus); // clip existing.
+        this->insertBefore(n, x);
+        return *this;
+      }
+    } else if (n->_data == payload && n->_max >= min_1) {
+      x = n;
+      // If the existing span covers the requested span, we're done.
+      if (x->_max >= max) return *this;
+      x->setMax(max);
+    } else if (n->_max <= max) {
+      // Can only have left skew overlap, otherwise disjoint.
+      // Clip if overlap.
+      if (n->_max >= min) n->setMax(min_1);
+      else if (next(n) && n->_max <= max) {
+        // request region covers next span so we can re-use that node.
+        x = next(n);
+        x->setMin(min).setMax(max).setData(payload);
+        n = x; // this gets bumped again, which is correct.
+      }
+    } else {
+      // Existing span covers new span but with a different payload.
+      // We split it, put the new span in between and we're done.
+      N* r;
+      Metric max_plus = N::deref(max);
+      N::inc(max_plus);
+      x = new N(min, max, payload);
+      r = new N(max_plus, n->_max, n->_data);
+      n->setMax(min_1);
+      this->insertAfter(n, x);
+      this->insertAfter(x, r);
+      return *this; // done.
+    }
+    n = next(n); // lower bound span handled, move on.
+    if (!x) {
+      x = new N(min, max, payload);
+      if (n) this->insertBefore(n, x);
+      else this->append(x); // note that since n == 0 we'll just return.
+    }
+  } else {
+    x = new N(min, max, payload);
+    this->prepend(x);
+    n = next(x);
+  }
+
+  // At this point, @a x has the node for this span and all existing spans of
+  // interest start at or past this span.
+  while (n) {
+    if (n->_max <= max) {
+      x = n;
+      n = next(n);
+      this->remove(x);
+    } else if (n->_min > max) {
+      // no overlap so we're done.
+      break;
+    } else {
+      Metric max_plus = N::deref(max);
+      // just right overlap, clip and we're done.
+      N::inc(max_plus);
+      n->setMin(max_plus);
+      break;
+    }
+  }
+
+  return *this;
+}
+
+template <typename N> IpMapBase<N>&
+IpMapBase<N>::unmark(ArgType min, ArgType max) {
+  N* n = this->lowerBound(min);
+  N* x; // temp for deletes.
+
+  // Need to handle special case where first span starts to the left.
+  if (n && n->_min < min) {
+    if (n->_max >= min) { // some overlap
+      Metric min_1 = N::deref(min);
+      N::dec(min_1);
+      if (n->_max > max) {
+        // request span is covered by existing span - split existing span.
+        Metric max_plus = N::deref(max);
+        N::inc(max_plus);
+        x = new N(max_plus, n->_max, n->_data);
+        n->setMax(min_1);
+        this->insertAfter(n, x);
+        return *this; // done.
+      } else {
+        n->setMax(min_1); // just clip overloap.
+      }
+    } // else disjoint so just skip it.
+    n = next(n);
+  }
+  // n and all subsequent spans start at >= min.
+  while (n) {
+    x = n;
+    n = next(n);
+    if (x->_max <= max) {
+      this->remove(x);
+    } else {
+      if (x->_min <= max) { // clip overlap
+        Metric max_plus = N::deref(max);
+        N::inc(max_plus);
+        x->setMin(max_plus);
+      }
+      break;
+    }
+  }
+  return *this;
+}
+
+template <typename N> void
+IpMapBase<N>::insertAfter(N* spot, N* n) {
+  N* c = right(spot);
+  if (!c) spot->setChild(n, N::RIGHT);
+  else spot->_next->setChild(n, N::LEFT);
+
+  _list.insertAfter(spot, n);
+  _root = static_cast<N*>(n->rebalanceAfterInsert());
+}
+
+template <typename N> void
+IpMapBase<N>::insertBefore(N* spot, N* n) {
+  N* c = left(spot);
+  if (!c) spot->setChild(n, N::LEFT);
+  else spot->_prev->setChild(n, N::RIGHT);
+
+  _list.insertBefore(spot, n);
+  _root = static_cast<N*>(n->rebalanceAfterInsert());
+}
+
+template <typename N> void
+IpMapBase<N>::prepend(N* n) {
+  if (!_root) _root = n;
+  else _root = static_cast<N*>(_list.getHead()->setChild(n, N::LEFT)->rebalanceAfterInsert());
+  _list.prepend(n);
+}
+
+template <typename N> void
+IpMapBase<N>::append(N* n) {
+  if (!_root) _root = n;
+  else _root = static_cast<N*>(_list.getTail()->setChild(n, N::RIGHT)->rebalanceAfterInsert());
+  _list.append(n);
+}
+
+template <typename N> void
+IpMapBase<N>::remove(N* n) {
+  _root = static_cast<N*>(n->remove());
+  _list.take(n);
+  delete n;
+}
+
+template <typename N> bool
+IpMapBase<N>::contains(ArgType x, void** ptr) {
+  bool zret = false;
+  N* n = _root; // current node to test.
+  while (n) {
+    if (x < n->_min) n = left(n);
+    else if (n->_max < x) n = right(n);
+    else {
+      if (ptr) *ptr = n->_data;
+      zret = true;
+      break;
+    }
+  }
+  return zret;
+}
+//----------------------------------------------------------------------------
+template <typename N> void
+IpMapBase<N>::validate() {
+# if 0
+  if (_root) _root->validate();
+  for ( Node* n = _list.getHead() ; n ; n = n->_next ) {
+    Node* x;
+    if (0 != (x = n->_next)) {
+      if (x->_prev != n)
+        std::cout << "Broken list" << std::endl;
+      if (n->_max >= x->_min)
+        std::cout << "Out of order - " << n->_max << " > " << x->_min << std::endl;
+      if (n->_parent == n || n->_left == n || n->_right == n)
+        std::cout << "Looped node" << std::endl;
+    }
+  }
+# endif
+}
+
+template <typename N> IpMapBase<N>&
+IpMapBase<N>::print() {
+# if 0
+  for ( Node* n = _list.getHead() ; n ; n = n->_next ) {
+    std::cout
+      << n << ": " << n->_min << '-' << n->_max << " [" << n->_data << "] "
+      << (n->_color == Node::BLACK ? "Black " : "Red   ") << "P=" << n->_parent << " L=" << n->_left << " R=" << n->_right
+      << std::endl;
+  }
+# endif
+  return *this;
+}
+
+//----------------------------------------------------------------------------
+typedef Interval<uint32_t, uint32_t> Ip4Span;
+
+/** Node for IPv4 map.
+    We store the address in host order in the @a _min and @a _max
+    members for performance. We store copies in the @a _sa member
+    for API compliance (which requires @c sockaddr* access).
+*/
+class Ip4Node : public IpMap::Node, protected Ip4Span {
+  friend class IpMapBase<Ip4Node>;
+public:
+  typedef Ip4Node self; ///< Self reference type.
+
+  /// Construct with values.
+  Ip4Node(
+    ArgType min, ///< Minimum address (network order).
+    ArgType max, ///< Maximum address (network order).
+    void* data ///< Client data.
+  ) : Node(data), Ip4Span(ntohl(min), ntohl(max)) {
+    ink_inet_ip4_set(ink_inet_sa_cast(&_sa._min), min);
+    ink_inet_ip4_set(ink_inet_sa_cast(&_sa._max), max);
+  }
+  /// @return The minimum value of the interval.
+  virtual sockaddr const* min() {
+    return ink_inet_sa_cast(&_sa._min);
+  }
+  /// @return The maximum value of the interval.
+  virtual sockaddr const* max() {
+    return ink_inet_sa_cast(&_sa._max);
+  }
+  /// Set the client data.
+  self& setData(
+    void* data ///< Client data.
+  ) {
+    _data = data;
+    return *this;
+  }
+protected:
+  
+  /// Set the minimum value of the interval.
+  /// @return This interval.
+  self& setMin(
+    ArgType min ///< Minimum value (host order).
+  ) {
+    _min = min;
+    _sa._min.sin_addr.s_addr = htonl(min);
+    return *this;
+  }
+  
+  /// Set the maximum value of the interval.
+  /// @return This interval.
+  self& setMax(
+    ArgType max ///< Maximum value (host order).
+  ) {
+    _max = max;
+    _sa._max.sin_addr.s_addr = htonl(max);
+    return *this;
+  }
+  
+  // Static helper methods for Metric.
+  
+  /** Compare two metrics.
+      @return
+        - -1 if @a lhs < @a rhs
+        -  0 if @a lhs == @a rhs
+        -  1 if @a lhs > @a rhs
+  */
+  static int cmp(
+    ArgType lhs,
+    ArgType rhs
+  ) {
+    return lhs < rhs ? -1
+      : lhs > rhs ? 1
+      : 0
+      ;
+  }
+  
+  /// Increment a metric.
+  static void inc(
+    Metric& m ///< Incremented in place.
+  ) {
+    ++m;
+  }
+  
+  /// Decrement a metric.
+  static void dec(
+    Metric& m ///< Decremented in place.
+  ) {
+    --m;
+  }
+  
+  /// @return Dereferenced @a addr.
+  static Metric deref(
+    ArgType addr ///< Argument to dereference.
+  ) {
+    return addr;
+  }
+  
+  struct {
+    sockaddr_in _min;
+    sockaddr_in _max;
+  } _sa; ///< Addresses in API compliant form.
+
+};
+
+class Ip4Map : public IpMapBase<Ip4Node> {
+  friend class ::IpMap;
+};
+
+//----------------------------------------------------------------------------
+typedef Interval<sockaddr_in6> Ip6Span;
+
+/** Node for IPv6 map.
+*/
+class Ip6Node : public IpMap::Node, protected Ip6Span {
+  friend class IpMapBase<Ip6Node>;
+public:
+  typedef Ip6Node self; ///< Self reference type.
+  /// Override @c ArgType from @c Interval because the convention
+  /// is to use a pointer, not a reference.
+  typedef Metric const* ArgType;
+
+  /// Construct from pointers.
+  Ip6Node(
+    ArgType min, ///< Minimum address (network order).
+    ArgType max, ///< Maximum address (network order).
+    void* data ///< Client data.
+  ) : Node(data), Ip6Span(*min, *max) {
+  }
+  /// Construct with values.
+  Ip6Node(
+    Metric const& min, ///< Minimum address (network order).
+    Metric const& max, ///< Maximum address (network order).
+    void* data ///< Client data.
+  ) : Node(data), Ip6Span(min, max) {
+  }
+  /// @return The minimum value of the interval.
+  virtual sockaddr const* min() {
+    return ink_inet_sa_cast(&_min);
+  }
+  /// @return The maximum value of the interval.
+  virtual sockaddr const* max() {
+    return ink_inet_sa_cast(&_max);
+  }
+  /// Set the client data.
+  self& setData(
+    void* data ///< Client data.
+  ) {
+    _data = data;
+    return *this;
+  }
+protected:
+  
+  /// Set the minimum value of the interval.
+  /// @return This interval.
+  self& setMin(
+    ArgType min ///< Minimum value (host order).
+  ) {
+    ink_inet_copy(ink_inet_sa_cast(&_min), ink_inet_sa_cast(min));
+    return *this;
+  }
+  
+  /// Set the minimum value of the interval.
+  /// @note Convenience overload.
+  /// @return This interval.
+  self& setMin(
+    Metric const& min ///< Minimum value (host order).
+  ) {
+    return this->setMin(&min);
+  }
+  
+  /// Set the maximum value of the interval.
+  /// @return This interval.
+  self& setMax(
+    ArgType max ///< Maximum value (host order).
+  ) {
+    ink_inet_copy(ink_inet_sa_cast(&_max), ink_inet_sa_cast(max));
+    return *this;
+  }
+  /// Set the maximum value of the interval.
+  /// @note Convenience overload.
+  /// @return This interval.
+  self& setMax(
+    Metric const& max ///< Maximum value (host order).
+  ) {
+    return this->setMax(&max);
+  }
+  
+  // Static helper methods for Metric.
+  
+  /** Compare two metrics.
+      @return
+        - -1 if @a lhs < @a rhs
+        -  0 if @a lhs == @a rhs
+        -  1 if @a lhs > @a rhs
+  */
+  static int cmp(
+    ArgType lhs,
+    ArgType rhs
+  ) {
+    return ink_inet_cmp(ink_inet_sa_cast(lhs), ink_inet_sa_cast(rhs));
+  }
+  
+  /// Increment a metric.
+  static void inc(
+    Metric& m ///< Incremented in place.
+  ) {
+    uint8_t* addr = m.sin6_addr.__in6_u.__u6_addr8;
+    uint8_t* b = addr + INK_IP6_SIZE;
+    do {
+      ++*--b;
+    } while (b > addr && 0 == *b);
+  }
+  
+  /// Decrement a metric.
+  static void dec(
+    Metric& m ///< Decremented in place.
+  ) {
+    uint8_t* addr = m.sin6_addr.__in6_u.__u6_addr8;
+    uint8_t* b = addr + INK_IP6_SIZE;
+    do {
+      --*--b;
+    } while (b > addr && static_cast<uint8_t>(0xFF) == *b);
+  }
+  /// @return Dereferenced @a addr.
+  static Metric const& deref(
+    ArgType addr ///< Argument to dereference.
+  ) {
+    return *addr;
+  }
+  
+};
+
+inline int cmp(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) {
+  return memcmp(lhs.sin6_addr.__in6_u.__u6_addr8, rhs.sin6_addr.__in6_u.__u6_addr8, INK_IP6_SIZE);
+}
+
+// Helper functions
+
+/// Less than.
+inline bool operator<(sockaddr_in6 const* lhs, sockaddr_in6 const& rhs) {
+  return -1 == ts::detail::cmp(*lhs, rhs);
+}
+/// Less than.
+inline bool operator<(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
+  return -1 == ts::detail::cmp(lhs, *rhs);
+}
+/// Equality.
+inline bool operator==(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
+  return 0 == ts::detail::cmp(lhs, *rhs);
+}
+/// Equality.
+inline bool operator==(sockaddr_in6 const* lhs, sockaddr_in6 const& rhs) {
+  return 0 == ts::detail::cmp(*lhs, rhs);
+}
+/// Equality.
+inline bool operator==(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) {
+  return 0 == ts::detail::cmp(lhs, rhs);
+}
+/// Less than or equal.
+inline bool operator<=(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
+  return 1 != ts::detail::cmp(lhs, *rhs);
+}
+/// Greater than or equal.
+inline bool operator>=(sockaddr_in6 const& lhs, sockaddr_in6 const& rhs) {
+  return -1 != ts::detail::cmp(lhs, rhs);
+}
+/// Greater than or equal.
+inline bool operator>=(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
+  return -1 != ts::detail::cmp(lhs, *rhs);
+}
+/// Greater than.
+inline bool operator>(sockaddr_in6 const& lhs, sockaddr_in6 const* rhs) {
+  return 1 == ts::detail::cmp(lhs, *rhs);
+}
+
+class Ip6Map : public IpMapBase<Ip6Node> {
+  friend class ::IpMap;
+};
+
+}} // end namespaces
+
+//----------------------------------------------------------------------------
+namespace {
+  ///< @return The network order IPv4 address in @a target.
+  inline uint32_t const& ip4_addr(sockaddr const* target) {
+    return ink_inet_ip4_cast(target)->sin_addr.s_addr;
+  }
+}
+IpMap::~IpMap() {
+  delete _m4;
+  delete _m6;
+}
+
+inline ts::detail::Ip4Map*
+IpMap::force4() {
+  if (!_m4) _m4 = new ts::detail::Ip4Map;
+  return _m4;
+}
+
+bool
+IpMap::contains(sockaddr const* target, void** ptr) {
+  bool zret = false;
+  if (AF_INET == target->sa_family) {
+    if (_m4) {
+      zret = _m4->contains(ntohl(ip4_addr(target)));
+    }
+  } else if (AF_INET6 == target->sa_family) {
+    if (_m6) {
+      zret = _m6->contains(ink_inet_ip6_cast(target));
+    }
+  }
+  return zret;
+}
+
+IpMap&
+IpMap::mark(
+  sockaddr const* min,
+  sockaddr const* max,
+  void* data
+) {
+  ink_assert(min->sa_family == max->sa_family);
+  if (AF_INET == min->sa_family) {
+    this->force4()->mark(ip4_addr(min), ip4_addr(max), data);
+  } else if (AF_INET6 == min->sa_family) {
+    if (!_m6) _m6 = new ts::detail::Ip6Map;
+    _m6->mark(ink_inet_ip6_cast(min), ink_inet_ip6_cast(max));
+  }
+  return *this;
+}
+
+IpMap&
+IpMap::mark(uint32_t min, uint32_t max, void* data) {
+  this->force4()->mark(min, max, data);
+  return *this;
+}
+
+IpMap&
+IpMap::unmark(
+  sockaddr const* min,
+  sockaddr const* max
+) {
+  ink_assert(min->sa_family == max->sa_family);
+  if (AF_INET == min->sa_family) {
+    if (_m4) _m4->unmark(ip4_addr(min), ip4_addr(max));
+  } else if (AF_INET6 == min->sa_family) {
+    if (_m6) _m6->unmark(ink_inet_ip6_cast(min), ink_inet_ip6_cast(max));
+  }
+  return *this;
+}
+
+IpMap::iterator
+IpMap::begin() {
+  Node* x;
+  if (_m4) x = _m4->getHead();
+  if (!x && _m6) x = _m6->getHead();
+  return iterator(this, x);
+}
+
+IpMap::iterator&
+IpMap::iterator::operator ++ () {
+  if (_node) {
+    // If we go past the end of the list see if it was the v4 list
+    // and if so, move to the v6 list (if it's there).
+    Node* x = static_cast<Node*>(_node->_next);
+    if (!x && _tree->_m4 && _tree->_m6 && _node == _tree->_m4->getTail())
+      x = _tree->_m6->getTail();
+    _node = x;
+  }
+  return *this;
+}
+
+inline IpMap::iterator&
+IpMap::iterator::operator--() {
+  if (_node) {
+    // At a node, try to back up. Handle the case where we back over the
+    // start of the v6 addresses and switch to the v4, if there are any.
+    Node* x = static_cast<Node*>(_node->_prev);
+    if (!x && _tree->_m4 && _tree->_m6 && _node == _tree->_m6->getHead())
+      x = _tree->_m4->getTail();
+    _node = x;
+  } else if (_tree) {
+    // We were at the end. Back up to v6 if possible, v4 if not.
+    if (_tree->_m6) _node = _tree->_m6->getTail();
+    if (!_node && _tree->_m4) _node = _tree->_m4->getTail();
+  }
+  return *this;
+}
+
+
+//----------------------------------------------------------------------------
+//----------------------------------------------------------------------------
+

Added: trafficserver/traffic/trunk/lib/ts/IpMap.h
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/lib/ts/IpMap.h?rev=1144353&view=auto
==============================================================================
--- trafficserver/traffic/trunk/lib/ts/IpMap.h (added)
+++ trafficserver/traffic/trunk/lib/ts/IpMap.h Fri Jul  8 15:08:11 2011
@@ -0,0 +1,433 @@
+# if ! defined(TS_IP_MAP_HEADER)
+# define TS_IP_MAP_HEADER
+
+# include <ts/ink_assert.h>
+# include <ts/ink_inet.h>
+# include <ts/IntrusiveDList.h>
+
+/** @file
+
+    Map of IP addresses to client data.
+
+    @section license License
+
+    Licensed to the Apache Software Foundation (ASF) under one
+    or more contributor license agreements.  See the NOTICE file
+    distributed with this work for additional information
+    regarding copyright ownership.  The ASF licenses this file
+    to you under the Apache License, Version 2.0 (the
+    "License"); you may not use this file except in compliance
+    with the License.  You may obtain a copy of the License at
+
+      http://www.apache.org/licenses/LICENSE-2.0
+
+    Unless required by applicable law or agreed to in writing, software
+    distributed under the License is distributed on an "AS IS" BASIS,
+    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+    See the License for the specific language governing permissions and
+    limitations under the License.
+*/
+
+namespace ts { namespace detail {
+
+  /** Interval class.
+      This holds an interval based on a metric @a T along with
+      client data.
+  */
+  template <
+    typename T, ///< Metric for span.
+    typename A  = T const& ///< Argument type.
+  > struct Interval {
+    typedef T Metric; ///< Metric (storage) type.
+    typedef A ArgType; ///< Type used to pass instances of @c Metric.
+
+    Interval() {} ///< Default constructor.
+    /// Construct with values.
+    Interval(
+      ArgType min, ///< Minimum value in span.
+      ArgType max ///< Maximum value in span.
+    ) : _min(min), _max(max) {}
+    Metric _min; ///< Minimum value in span.
+    Metric _max; ///< Maximum value in span.
+  };
+
+  class Ip4Map; // Forward declare.
+  class Ip6Map; // Forward declare.
+
+  /** A node in a red/black tree.
+      This class provides only the basic tree operations. The client
+      must provide the search and decision logic. This enables this class
+      to be a base class for templated nodes with much less code duplication.
+  */
+  struct RBNode {
+    typedef RBNode self; //!< self reference type
+
+    //! Node colors
+    typedef enum { RED, BLACK } Color;
+
+    //! Directional constants
+    typedef enum { NONE, LEFT, RIGHT } Direction;
+
+    /// Get a child by direction.
+    /// @return The child in the direction @a d if it exists,
+    /// @c NULL if not.
+    self* getChild(
+      Direction d //!< The direction of the desired child
+    ) const;
+
+    /** Determine which child a node is
+        @return @c LEFT if @a n is the left child,
+        @c RIGHT if @a n is the right child,
+        @c NONE if @a n is not a child
+    */
+    Direction getChildDirection(
+      self* const& n //!< The presumed child node
+    ) const {
+      return (n == _left) ? LEFT : (n == _right) ? RIGHT : NONE;
+    }
+
+    /** Get the parent node.
+        @return A Node* to the parent node or a @c nil Node* if no parent.
+    */
+    self* getParent() const { return const_cast<self*>(_parent); }
+
+    /// @return The color of the node.
+    Color getColor() const { return _color; }
+
+    //! Reverse a direction
+    /** @return @c LEFT if @a d is @c RIGHT, @c RIGHT if @a d is @c LEFT,
+        @c NONE otherwise.
+    */
+    Direction flip(Direction d) {
+      return LEFT == d ? RIGHT : RIGHT == d ? LEFT : NONE;
+    }
+
+    /** Perform internal validation checks.
+        @return 0 on failure, black height of the tree on success.
+    */
+    int validate();
+
+    /// Default constructor.
+    RBNode()
+      : _color(RED)
+      , _parent(0)
+      , _left(0)
+      , _right(0)
+      , _next(0)
+      , _prev(0) {
+    }
+
+    /// Destructor (force virtual).
+    virtual ~RBNode() { }
+
+    /** Rotate the subtree rooted at this node.
+        The node is rotated in to the position of one of its children.
+        Which child is determined by the direction parameter @a d. The
+        child in the other direction becomes the new root of the subtree.
+
+        If the parent pointer is set, then the child pointer of the original
+        parent is updated so that the tree is left in a consistent state.
+
+        @note If there is no child in the other direction, the rotation
+        fails and the original node is returned. It is @b not required
+        that a child exist in the direction specified by @a d.
+
+        @return The new root node for the subtree.
+    */
+    self* rotate(
+      Direction d //!< The direction to rotate
+    );
+
+    /** Set the child node in direction @a d to @a n.
+        The @a d child is set to the node @a n. The pointers in this
+        node and @a n are set correctly. This can only be called if
+        there is no child node already present.
+
+        @return @a n.
+    */
+    self* setChild(
+      self* n, //!< The node to set as the child
+      Direction d //!< The direction of the child
+    );
+
+    /** Remove this node from the tree.
+        The tree is rebalanced after removal.
+        @return The new root node.
+    */
+    self* remove();
+
+    void clearChild(Direction dir) {
+      if (LEFT == dir) _left = 0;
+      else if (RIGHT == dir) _right = 0;
+    }
+
+    /** @name Subclass hook methods */
+    //@{
+    /** Structural change notification.
+        This method is called if the structure of the subtree rooted at
+        this node was changed.
+			
+        This is intended a hook. The base method is empty so that subclasses
+        are not required to override.
+    */
+    virtual void structureFixup() {}
+
+    /** Called from @c validate to perform any additional validation checks.
+        Clients should chain this if they wish to perform additional checks.
+        @return @c true if the validation is successful, @c false otherwise.
+        @note The base method simply returns @c true.
+    */
+    virtual bool structureValidate() { return true; }
+    //@}
+
+    /** Replace this node with another node.
+        This is presumed to be non-order modifying so the next reference
+        is @b not updated.
+    */
+    void replaceWith(
+      self* n //!< Node to put in place of this node.
+    );
+
+    //! Rebalance the tree starting at this node
+    /** The tree is rebalanced so that all of the invariants are
+        true. The (potentially new) root of the tree is returned.
+
+        @return The root node of the tree after the rebalance.
+    */
+    self* rebalanceAfterInsert();
+		
+    /** Rebalance the tree after a deletion.
+        Called on the lowest modified node.
+        @return The new root of the tree.
+    */
+    self* rebalanceAfterRemove(
+      Color c, //!< The color of the removed node.
+      Direction d //!< Direction of removed node from parent
+    );
+
+    //! Invoke @c structure_fixup() on this node and all of its ancestors.
+    self* rippleStructureFixup();
+
+    Color _color;  ///< node color
+    self* _parent; ///< parent node (needed for rotations)
+    self* _left;   ///< left child
+    self* _right;  ///< right child
+    self* _next; ///< Next node.
+    self* _prev; ///< Previous node.
+  };
+
+}} // namespace ts::detail
+
+/** Map from IP addresses to client data.
+
+    Conceptually this class maps the entire space of IP addresses to
+    client data. Client data is stored as a @c (void*). Memory
+    management of the data is left to the client. The interface
+    supports marking ranges of addresses with a specific client
+    data. Marking takes a painter's algorithm approach -- any marking
+    overwrites any previous marking on an address. Details of marking
+    calls are discarded and only the final results are kept. That is,
+    a client cannot unmark expliticly any previous marking. Only a
+    specific range of addresses can be unmarked.
+
+    Both IPv4 and IPv6 are supported in the same map. Mixed ranges are
+    not supported (any particular range of addresses must be a single
+    protocol but ranges of both types can be in the map).
+
+    Use @c mark to mark / set/ add addresses to the map.
+    Use @c unmark to unset addresses (setting the client data to 0 does
+    @b not remove the address -- this is for the convenience of clients
+    that do not need data, only membership). @c contains tests for
+    membership and retrieves the client data.
+
+    Ranges can be marked and unmarked arbitrarily. The internal
+    representation keeps a minimal set of ranges to describe the
+    current addresses. Search time is O(log n) where n is the number
+    of disjoint ranges. Marking and unmarking can take O(log n) and
+    may require memory allocation / deallocation although this is
+    minimized.
+
+*/
+
+class IpMap {
+public:
+  typedef IpMap self; ///< Self reference type.
+
+  class iterator; // forward declare.
+  
+  /** Public API for intervals in the map.
+  */
+  class Node : protected ts::detail::RBNode {
+    friend class iterator;
+    friend class IpMap;
+  public:
+    typedef Node self; ///< Self reference type.
+    /// Default constructor.
+    Node() : _data(0) {}
+    /// Construct with @a data.
+    Node(void* data) : _data(data) {}
+    /// @return Client data for the node.
+    virtual void* data() { return _data; }
+    /// Set client data.
+    virtual self& setData(
+      void* data ///< Client data pointer to store.
+    ) {
+      _data = data;
+      return *this;
+    }
+    /// @return Minimum value of the interval.
+    virtual sockaddr const* min() = 0;
+    /// @return Maximum value of the interval.
+    virtual sockaddr const* max() = 0;
+  protected:
+    void* _data; ///< Client data.
+  };
+
+  /** Iterator over nodes / intervals.
+
+      The iteration is over all nodes, regardless of which node is
+      used to create the iterator. The node passed to the constructor
+      just sets the current location.
+  */
+  class iterator {
+    friend class IpMap;
+  public:
+    typedef iterator self; ///< Self reference type.
+    typedef Node value_type; ///< Referenced type for iterator.
+    typedef int difference_type; ///< Distance type.
+    typedef Node* pointer; ///< Pointer to referent.
+    typedef Node& reference; ///< Reference to referent.
+    typedef std::bidirectional_iterator_tag iterator_category;
+    /// Default constructor.
+    iterator() : _tree(0), _node(0) {}
+
+    reference operator* (); //!< value operator
+    pointer operator -> (); //!< dereference operator
+    self& operator++(); //!< next node (prefix)
+    self operator++(int); //!< next node (postfix)
+    self& operator--(); ///< previous node (prefix)
+    self operator--(int); ///< next node (postfix)
+
+    /** Equality.
+        @return @c true if the iterators refer to the same node.
+    */
+    bool operator==(self const& that) const;
+    /** Inequality.
+        @return @c true if the iterators refer to different nodes.
+    */
+    bool operator!=(self const& that) const { return ! (*this == that); }
+  private:
+    /// Construct a valid iterator.
+    iterator(IpMap* tree, Node* node) : _tree(tree), _node(node) {}
+      IpMap* _tree; ///< Container.
+      Node* _node; //!< Current node.
+    };
+
+  IpMap(); ///< Default constructor.
+  ~IpMap(); ///< Destructor.
+
+  /** Mark a range.
+      All addresses in the range [ @a min , @a max ] are marked with @a data.
+      @return This object.
+  */
+  self& mark(
+    sockaddr const* min, ///< Minimum value in range.
+    sockaddr const* max, ///< Maximum value in range.
+    void* data = 0     ///< Client data payload.
+  );
+
+  /** Mark a range.
+      All addresses in the range [ @a min , @a max ] are marked with @a data.
+      @note Convenience overload for IPv4 addresses.
+      @return This object.
+  */
+  self& mark(
+    uint32_t min, ///< Minimum address (network order).
+    uint32_t max, ///< Maximum address (network order).
+    void* data = 0 ///< Client data.
+  );
+
+  /** Unmark addresses.
+
+      All addresses in the range [ @a min , @a max ] are cleared
+      (removed from the map), no longer marked.
+
+      @return This object.
+  */
+  self& unmark(
+    sockaddr const* min, ///< Minimum value.
+    sockaddr const* max  ///< Maximum value.
+  );
+
+  /** Test for membership.
+
+      @return @c true if the address is in the map, @c false if not.
+      If the address is in the map and @a ptr is not @c NULL, @c *ptr
+      is set to the client data for the address.
+  */
+  bool contains(
+    sockaddr const* target, ///< Search target value.
+    void **ptr = 0 ///< Client data return.
+  );
+
+  /// Iterator for first element.
+  iterator begin();
+  /// Iterator past last element.
+  iterator end();
+
+  /** Validate internal data structures.
+      @note Intended for debugging, not general client use.
+  */
+  void validate();
+
+  /// Print all spans.
+  /// @return This map.
+  self& print();
+
+protected:
+  /// Force the IPv4 map to exist.
+  /// @return The IPv4 map.
+  ts::detail::Ip4Map* force4();
+  
+  ts::detail::Ip4Map* _m4; ///< Map of IPv4 addresses.
+  ts::detail::Ip6Map* _m6; ///< Map of IPv6 addresses.
+  
+};
+
+inline IpMap::iterator
+IpMap::end() {
+  return iterator(this, 0);
+}
+
+inline IpMap::iterator
+IpMap::iterator::operator ++ (int) {
+  iterator old(*this);
+  ++*this;
+  return old;
+}
+
+inline IpMap::iterator
+IpMap::iterator::operator--(int) {
+  self tmp(*this);
+  --*this;
+  return tmp;
+}
+
+inline bool
+IpMap::iterator::operator == (iterator const& that) const {
+  return _tree == that._tree && _node == that._node;
+}
+
+inline IpMap::iterator::reference
+IpMap::iterator::operator * () {
+  return *_node;
+}
+
+inline IpMap::iterator::pointer
+IpMap::iterator::operator -> () {
+  return _node;
+}
+
+inline IpMap::IpMap() : _m4(0), _m6(0) {}
+
+# endif // TS_IP_MAP_HEADER

Modified: trafficserver/traffic/trunk/lib/ts/Makefile.am
URL: http://svn.apache.org/viewvc/trafficserver/traffic/trunk/lib/ts/Makefile.am?rev=1144353&r1=1144352&r2=1144353&view=diff
==============================================================================
--- trafficserver/traffic/trunk/lib/ts/Makefile.am (original)
+++ trafficserver/traffic/trunk/lib/ts/Makefile.am Fri Jul  8 15:08:11 2011
@@ -20,6 +20,8 @@ noinst_PROGRAMS = mkdfa CompileParseRule
 check_PROGRAMS = test_atomic test_freelist test_arena test_List test_Map test_Vec
 TESTS = $(check_PROGRAMS)
 
+AM_CPPFLAGS = -I$(top_srcdir)/lib
+
 lib_LTLIBRARIES = libtsutil.la
 
 libtsutil_la_LDFLAGS = -no-undefined -version-info @TS_LIBTOOL_VERSION@
@@ -122,6 +124,8 @@ libtsutil_la_SOURCES = \
   llqueue.cc \
   lockfile.cc \
   I_Layout.h \
+  IntrusiveDList.h \
+  IpMap.h IpMap.cc \
   Layout.cc \
   MatcherUtils.cc \
   MatcherUtils.h \



Mime
View raw message