You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by am...@apache.org on 2011/07/08 17:08:13 UTC
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...
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 \