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 2018/08/22 14:55:25 UTC
[trafficserver] branch master updated (92b67e4 -> a34b7b8)
This is an automated email from the ASF dual-hosted git repository.
amc pushed a change to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git.
from 92b67e4 Completes documentation regarding redirects
new 1e2ef5c IntrusiveDList: Add user conversion from iterator to pointer to value_type.
new c157bdc IntrusiveDList: Update erase methods.
new f462170 IntrusiveHashMap: remove from "ts" namespace. The predecessor class, TSHashTable, wasn't in "ts" and having worked with IntrusiveHashMap for a while, I think it's best this isn't either.
new 8913fa3 IntrusiveHashMap: Change range to be std::pair based for better compatibility.
new 546a267 IntrusiveHashMap: Update erase methods. Add additional iterator_for methods for erase.
new 46de425 IntrusiveHashMap: Add overloads to apply method to support functor taking reference or pointer.
new 9b03c9c Outbound server session management - Replace TSHashTable with IntrusiveHashMap.
new a34b7b8 HttpConnectionCount: Replace TSHashTable with IntrusiveHashMap.
The 8 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
.../internal-libraries/intrusive-list.en.rst | 35 +++-
lib/ts/IntrusiveDList.h | 77 ++++++++-
lib/ts/IntrusiveHashMap.h | 181 ++++++++++++++-------
lib/ts/unit-tests/test_IntrusiveHashMap.cc | 8 +-
proxy/http/HttpConnectionCount.cc | 2 +-
proxy/http/HttpConnectionCount.h | 75 ++++++---
proxy/http/HttpServerSession.h | 111 ++++++++++++-
proxy/http/HttpSessionManager.cc | 74 +++++----
proxy/http/HttpSessionManager.h | 58 +------
9 files changed, 434 insertions(+), 187 deletions(-)
[trafficserver] 04/08: IntrusiveHashMap: Change range to be
std::pair based for better compatibility.
Posted by am...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
commit 8913fa332862fcc610265f671ef33604d7da94e2
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Sat Jul 21 19:49:35 2018 -0500
IntrusiveHashMap: Change range to be std::pair based for better compatibility.
---
lib/ts/IntrusiveHashMap.h | 37 +++++++++++-------------------
lib/ts/unit-tests/test_IntrusiveHashMap.cc | 4 ++--
2 files changed, 16 insertions(+), 25 deletions(-)
diff --git a/lib/ts/IntrusiveHashMap.h b/lib/ts/IntrusiveHashMap.h
index 84a64fa..c69a9a5 100644
--- a/lib/ts/IntrusiveHashMap.h
+++ b/lib/ts/IntrusiveHashMap.h
@@ -151,12 +151,9 @@ public:
/// A range of elements in the map.
/// It is a half open range, [first, last) in the usual STL style.
/// @internal I tried @c std::pair as a base for this but was unable to get STL container operations to work.
- struct range {
- iterator first; ///< First element.
- iterator last; ///< Past last element.
-
- /// Construct from two iterators.
- range(iterator const &lhs, iterator const &rhs);
+ struct range : public std::pair<iterator, iterator> {
+ using super_type = std::pair<iterator, iterator>; ///< Super type.
+ using super_type::super_type; ///< Use super type constructors.
// These methods enable treating the range as a view in to the hash map.
@@ -167,12 +164,13 @@ public:
};
/// A range of constant elements in the map.
- struct const_range {
- const_iterator first; ///< First element.
- const_iterator last; ///< Past last element.
+ struct const_range : public std::pair<const_iterator, const_iterator> {
+ using super_type = std::pair<const_iterator, const_iterator>; ///< Super type.
+
+ /// Allow implicit conversion of range to const_range.
+ const_range(range const &r);
- /// Construct from two iterators.
- const_range(const_iterator const &lhs, const_iterator const &rhs);
+ using super_type::super_type; ///< Use super type constructors.
// These methods enable treating the range as a view in to the hash map.
@@ -353,38 +351,31 @@ IntrusiveHashMap<H>::Bucket::contains(value_type *v) const
}
// ---------------------
-template <typename H> IntrusiveHashMap<H>::range::range(iterator const &lhs, iterator const &rhs) : first(lhs), last(rhs) {}
-
template <typename H>
auto
IntrusiveHashMap<H>::range::begin() const -> iterator const &
{
- return first;
+ return super_type::first;
}
template <typename H>
auto
IntrusiveHashMap<H>::range::end() const -> iterator const &
{
- return last;
-}
-
-template <typename H>
-IntrusiveHashMap<H>::const_range::const_range(const_iterator const &lhs, const_iterator const &rhs) : first(lhs), last(rhs)
-{
+ return super_type::second;
}
template <typename H>
auto
IntrusiveHashMap<H>::const_range::begin() const -> const_iterator const &
{
- return first;
+ return super_type::first;
}
template <typename H>
auto
IntrusiveHashMap<H>::const_range::end() const -> const_iterator const &
{
- return last;
+ return super_type::second;
}
// ---------------------
@@ -476,7 +467,7 @@ IntrusiveHashMap<H>::equal_range(key_type key) -> range
++last;
}
- return {first, last};
+ return range{first, last};
}
template <typename H>
diff --git a/lib/ts/unit-tests/test_IntrusiveHashMap.cc b/lib/ts/unit-tests/test_IntrusiveHashMap.cc
index 67a0377..6828e3a 100644
--- a/lib/ts/unit-tests/test_IntrusiveHashMap.cc
+++ b/lib/ts/unit-tests/test_IntrusiveHashMap.cc
@@ -120,7 +120,7 @@ TEST_CASE("IntrusiveHashMap", "[libts][IntrusiveHashMap]")
map.insert(new Thing("dup"sv, 81));
auto r = map.equal_range("dup"sv);
- REQUIRE(r.first != r.last);
+ REQUIRE(r.first != r.second);
REQUIRE(r.first->_payload == "dup"sv);
Map::iterator idx;
@@ -131,7 +131,7 @@ TEST_CASE("IntrusiveHashMap", "[libts][IntrusiveHashMap]")
map.erase(map.iterator_for(&thing));
});
r = map.equal_range("dup"sv);
- REQUIRE(r.first != r.last);
+ REQUIRE(r.first != r.second);
idx = r.first;
REQUIRE(idx->_payload == "dup"sv);
REQUIRE((++idx)->_payload == "dup"sv);
[trafficserver] 06/08: IntrusiveHashMap: Add overloads to apply
method to support functor taking reference or pointer.
Posted by am...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
commit 46de4252f38b7df32943a702dc93dce79c3eb08e
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Fri Jul 20 08:36:45 2018 -0500
IntrusiveHashMap: Add overloads to apply method to support functor taking reference or pointer.
---
lib/ts/IntrusiveHashMap.h | 37 +++++++++++++++++++++++++-----
lib/ts/unit-tests/test_IntrusiveHashMap.cc | 2 +-
2 files changed, 32 insertions(+), 7 deletions(-)
diff --git a/lib/ts/IntrusiveHashMap.h b/lib/ts/IntrusiveHashMap.h
index 003326b..3f1848a 100644
--- a/lib/ts/IntrusiveHashMap.h
+++ b/lib/ts/IntrusiveHashMap.h
@@ -617,17 +617,42 @@ IntrusiveHashMap<H>::erase(range const &r) -> iterator
return this->erase(r.first, r.second);
}
+namespace detail
+{
+// Make @c apply more convenient by allowing the function to take a reference type or pointer type to the container
+// elements. The pointer type is the base, plus a shim to convert from a reference type functor to a pointer pointer
+// type. The complex return type definition forces only one, but not both, to be valid for a particular functor. This
+// also must be done via free functions and not method overloads because the compiler forces a match up of method
+// definitions and declarations before any template instantiation.
+
+template <typename H, typename F>
+auto
+IntrusiveHashMapApply(IntrusiveHashMap<H> &map, F &&f)
+ -> decltype(f(*static_cast<typename IntrusiveHashMap<H>::value_type *>(nullptr)), map)
+{
+ return map.apply([&f](typename IntrusiveHashMap<H>::value_type *v) { return f(*v); });
+}
+
+template <typename H, typename F>
+auto
+IntrusiveHashMapApply(IntrusiveHashMap<H> &map, F &&f)
+ -> decltype(f(static_cast<typename IntrusiveHashMap<H>::value_type *>(nullptr)), map)
+{
+ auto spot{map.begin()};
+ auto limit{map.end()};
+ while (spot != limit) {
+ f(spot++); // post increment means @a spot is updated before @a f is applied.
+ }
+ return map;
+}
+} // namespace detail
+
template <typename H>
template <typename F>
auto
IntrusiveHashMap<H>::apply(F &&f) -> self_type &
{
- iterator spot{this->begin()};
- iterator limit{this->end()};
- while (spot != limit) {
- f(*spot++); // post increment means @a spot is updated before @a f is applied.
- }
- return *this;
+ return detail::IntrusiveHashMapApply(*this, f);
};
template <typename H>
diff --git a/lib/ts/unit-tests/test_IntrusiveHashMap.cc b/lib/ts/unit-tests/test_IntrusiveHashMap.cc
index 6828e3a..abcbd35 100644
--- a/lib/ts/unit-tests/test_IntrusiveHashMap.cc
+++ b/lib/ts/unit-tests/test_IntrusiveHashMap.cc
@@ -144,5 +144,5 @@ TEST_CASE("IntrusiveHashMap", "[libts][IntrusiveHashMap]")
REQUIRE(elt._payload == "dup"sv);
}
// clean up the last bits.
- map.apply([](Thing &thing) { delete &thing; });
+ map.apply([](Thing *thing) { delete thing; });
};
[trafficserver] 01/08: IntrusiveDList: Add user conversion from
iterator to pointer to value_type.
Posted by am...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
commit 1e2ef5c8281531a7797f735011e27748a98ec801
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Fri Jul 20 08:36:21 2018 -0500
IntrusiveDList: Add user conversion from iterator to pointer to value_type.
---
lib/ts/IntrusiveDList.h | 20 ++++++++++++++++++++
1 file changed, 20 insertions(+)
diff --git a/lib/ts/IntrusiveDList.h b/lib/ts/IntrusiveDList.h
index 320be15..98f92d4 100644
--- a/lib/ts/IntrusiveDList.h
+++ b/lib/ts/IntrusiveDList.h
@@ -142,6 +142,11 @@ public:
/// @return A pointer to the referent.
value_type *operator->() const;
+ /// Convenience conversion to pointer type
+ /// Because of how this list is normally used, being able to pass an iterator as a pointer is quite convienent.
+ /// If the iterator isn't valid, it converts to @c nullptr.
+ operator value_type *() const;
+
/// Equality
bool operator==(self_type const &that) const;
@@ -206,6 +211,11 @@ public:
/// @return A pointer to the referent.
value_type *operator->() const;
+ /// Convenience conversion to pointer type
+ /// Because of how this list is normally used, being able to pass an iterator as a pointer is quite convienent.
+ /// If the iterator isn't valid, it converts to @c nullptr.
+ operator value_type *() const;
+
protected:
/// Internal constructor for containers.
iterator(list_type *list, value_type *v);
@@ -395,6 +405,11 @@ template <typename L> auto IntrusiveDList<L>::iterator::operator-> () const -> v
return super_type::_v;
}
+template <typename L> IntrusiveDList<L>::const_iterator::operator value_type *() const
+{
+ return _v;
+}
+
template <typename L> auto IntrusiveDList<L>::const_iterator::operator*() const -> value_type &
{
return *_v;
@@ -405,6 +420,11 @@ template <typename L> auto IntrusiveDList<L>::iterator::operator*() const -> val
return *super_type::_v;
}
+template <typename L> IntrusiveDList<L>::iterator::operator value_type *() const
+{
+ return super_type::_v;
+}
+
template <typename L>
bool
IntrusiveDList<L>::empty() const
[trafficserver] 07/08: Outbound server session management - Replace
TSHashTable with IntrusiveHashMap.
Posted by am...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
commit 9b03c9c163dbd489d858169cd7386e00359a3c73
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Fri Jul 20 08:37:13 2018 -0500
Outbound server session management - Replace TSHashTable with IntrusiveHashMap.
---
proxy/http/HttpServerSession.h | 111 ++++++++++++++++++++++++++++++++++++---
proxy/http/HttpSessionManager.cc | 74 +++++++++++++++-----------
proxy/http/HttpSessionManager.h | 58 ++------------------
3 files changed, 152 insertions(+), 91 deletions(-)
diff --git a/proxy/http/HttpServerSession.h b/proxy/http/HttpServerSession.h
index 491e2ca..5e4224a 100644
--- a/proxy/http/HttpServerSession.h
+++ b/proxy/http/HttpServerSession.h
@@ -66,10 +66,13 @@ enum {
class HttpServerSession : public VConnection
{
+ using self_type = HttpServerSession;
using super_type = VConnection;
public:
HttpServerSession() : super_type(nullptr) {}
+ HttpServerSession(self_type const &) = delete;
+ self_type &operator=(self_type const &) = delete;
void destroy();
void new_connection(NetVConnection *new_vc);
@@ -152,12 +155,36 @@ public:
bool private_session = false;
// Copy of the owning SM's server session sharing settings
- TSServerSessionSharingMatchType sharing_match{TS_SERVER_SESSION_SHARING_MATCH_BOTH};
- TSServerSessionSharingPoolType sharing_pool{TS_SERVER_SESSION_SHARING_POOL_GLOBAL};
+ TSServerSessionSharingMatchType sharing_match = TS_SERVER_SESSION_SHARING_MATCH_BOTH;
+ TSServerSessionSharingPoolType sharing_pool = TS_SERVER_SESSION_SHARING_POOL_GLOBAL;
// int share_session;
- LINK(HttpServerSession, ip_hash_link);
- LINK(HttpServerSession, host_hash_link);
+ /// Hash map descriptor class for IP map.
+ struct IPLinkage {
+ self_type *_next = nullptr;
+ self_type *_prev = nullptr;
+
+ static self_type *&next_ptr(self_type *);
+ static self_type *&prev_ptr(self_type *);
+ static uint32_t hash_of(sockaddr const *key);
+ static sockaddr const *key_of(self_type const *ssn);
+ static bool equal(sockaddr const *lhs, sockaddr const *rhs);
+ // Add a couple overloads for internal convenience.
+ static bool equal(sockaddr const *lhs, HttpServerSession const *rhs);
+ static bool equal(HttpServerSession const *lhs, sockaddr const *rhs);
+ } _ip_link;
+
+ /// Hash map descriptor class for FQDN map.
+ struct FQDNLinkage {
+ self_type *_next = nullptr;
+ self_type *_prev = nullptr;
+
+ static self_type *&next_ptr(self_type *);
+ static self_type *&prev_ptr(self_type *);
+ static uint64_t hash_of(CryptoHash const &key);
+ static CryptoHash const &key_of(self_type *ssn);
+ static bool equal(CryptoHash const &lhs, CryptoHash const &rhs);
+ } _fqdn_link;
// Keep track of connection limiting and a pointer to the
// singleton that keeps track of the connection counts.
@@ -187,8 +214,6 @@ public:
}
private:
- HttpServerSession(HttpServerSession &);
-
NetVConnection *server_vc = nullptr;
int magic = HTTP_SS_MAGIC_DEAD;
@@ -197,6 +222,8 @@ private:
extern ClassAllocator<HttpServerSession> httpServerSessionAllocator;
+// --- Implementation ---
+
inline void
HttpServerSession::attach_hostname(const char *hostname)
{
@@ -204,3 +231,75 @@ HttpServerSession::attach_hostname(const char *hostname)
CryptoContext().hash_immediate(hostname_hash, (unsigned char *)hostname, strlen(hostname));
}
}
+
+inline HttpServerSession *&
+HttpServerSession::IPLinkage::next_ptr(self_type *ssn)
+{
+ return ssn->_ip_link._next;
+}
+
+inline HttpServerSession *&
+HttpServerSession::IPLinkage::prev_ptr(self_type *ssn)
+{
+ return ssn->_ip_link._prev;
+}
+
+inline uint32_t
+HttpServerSession::IPLinkage::hash_of(sockaddr const *key)
+{
+ return ats_ip_hash(key);
+}
+
+inline sockaddr const *
+HttpServerSession::IPLinkage::key_of(self_type const *ssn)
+{
+ return &ssn->get_server_ip().sa;
+}
+
+inline bool
+HttpServerSession::IPLinkage::equal(sockaddr const *lhs, sockaddr const *rhs)
+{
+ return ats_ip_addr_port_eq(lhs, rhs);
+}
+
+inline bool
+HttpServerSession::IPLinkage::equal(sockaddr const *lhs, HttpServerSession const *rhs)
+{
+ return ats_ip_addr_port_eq(lhs, key_of(rhs));
+}
+
+inline bool
+HttpServerSession::IPLinkage::equal(HttpServerSession const *lhs, sockaddr const *rhs)
+{
+ return ats_ip_addr_port_eq(key_of(lhs), rhs);
+}
+
+inline HttpServerSession *&
+HttpServerSession::FQDNLinkage::next_ptr(self_type *ssn)
+{
+ return ssn->_fqdn_link._next;
+}
+
+inline HttpServerSession *&
+HttpServerSession::FQDNLinkage::prev_ptr(self_type *ssn)
+{
+ return ssn->_fqdn_link._prev;
+}
+
+inline uint64_t
+HttpServerSession::FQDNLinkage::hash_of(CryptoHash const &key)
+{
+ return key.fold();
+}
+
+inline CryptoHash const &
+HttpServerSession::FQDNLinkage::key_of(self_type *ssn)
+{
+ return ssn->hostname_hash;
+}
+
+inline bool
+HttpServerSession::FQDNLinkage::equal(CryptoHash const &lhs, CryptoHash const &rhs)
+{
+ return lhs == rhs;
+}
diff --git a/proxy/http/HttpSessionManager.cc b/proxy/http/HttpSessionManager.cc
index 07f7c41..8831a45 100644
--- a/proxy/http/HttpSessionManager.cc
+++ b/proxy/http/HttpSessionManager.cc
@@ -45,11 +45,11 @@ initialize_thread_for_http_sessions(EThread *thread)
HttpSessionManager httpSessionManager;
-ServerSessionPool::ServerSessionPool() : Continuation(new_ProxyMutex()), m_ip_pool(1023), m_host_pool(1023)
+ServerSessionPool::ServerSessionPool() : Continuation(new_ProxyMutex()), m_ip_pool(1023), m_fqdn_pool(1023)
{
SET_HANDLER(&ServerSessionPool::eventHandler);
- m_ip_pool.setExpansionPolicy(IPHashTable::MANUAL);
- m_host_pool.setExpansionPolicy(HostHashTable::MANUAL);
+ m_ip_pool.set_expansion_policy(IPTable::MANUAL);
+ m_fqdn_pool.set_expansion_policy(FQDNTable::MANUAL);
}
void
@@ -57,10 +57,9 @@ ServerSessionPool::purge()
{
// @c do_io_close can free the instance which clears the intrusive links and breaks the iterator.
// Therefore @c do_io_close is called on a post-incremented iterator.
- for (IPHashTable::iterator last = m_ip_pool.end(), spot = m_ip_pool.begin(); spot != last; spot++->do_io_close()) {
- }
+ m_ip_pool.apply([](HttpServerSession *ssn) -> void { ssn->do_io_close(); });
m_ip_pool.clear();
- m_host_pool.clear();
+ m_fqdn_pool.clear();
}
bool
@@ -97,38 +96,48 @@ ServerSessionPool::acquireSession(sockaddr const *addr, CryptoHash const &hostna
TSServerSessionSharingMatchType match_style, HttpSM *sm, HttpServerSession *&to_return)
{
HSMresult_t zret = HSM_NOT_FOUND;
+ to_return = nullptr;
+
if (TS_SERVER_SESSION_SHARING_MATCH_HOST == match_style) {
- // This is broken out because only in this case do we check the host hash first.
- HostHashTable::Location loc = m_host_pool.find(hostname_hash);
- in_port_t port = ats_ip_port_cast(addr);
- while (loc) { // scan for matching port.
- if (port == ats_ip_port_cast(loc->get_server_ip()) && validate_sni(sm, loc->get_netvc())) {
+ // This is broken out because only in this case do we check the host hash first. The range must be checked
+ // to verify an upstream that matches port and SNI name is selected. Walk backwards to select oldest.
+ in_port_t port = ats_ip_port_cast(addr);
+ FQDNTable::iterator first, last;
+ // FreeBSD/clang++ bug workaround: explicit cast to super type to make overload work. Not needed on Fedora27 nor gcc.
+ // Not fixed on FreeBSD as of llvm 6.0.1.
+ std::tie(first, last) = static_cast<const decltype(m_fqdn_pool)::range::super_type &>(m_fqdn_pool.equal_range(hostname_hash));
+ while (last != first) {
+ --last;
+ if (port == ats_ip_port_cast(last->get_server_ip()) && validate_sni(sm, last->get_netvc())) {
+ zret = HSM_DONE;
break;
}
- ++loc;
}
- if (loc) {
- to_return = loc;
- m_host_pool.remove(loc);
- m_ip_pool.remove(m_ip_pool.find(loc));
+ if (zret == HSM_DONE) {
+ to_return = last;
+ m_fqdn_pool.erase(last);
+ m_ip_pool.erase(to_return);
}
} else if (TS_SERVER_SESSION_SHARING_MATCH_NONE != match_style) { // matching is not disabled.
- IPHashTable::Location loc = m_ip_pool.find(addr);
- // If we're matching on the IP address we're done, this one is good enough.
- // Otherwise we need to scan further matches to match the host name as well.
- // Note we don't have to check the port because it's checked as part of the IP address key.
+ IPTable::iterator first, last;
+ // FreeBSD/clang++ bug workaround: explicit cast to super type to make overload work. Not needed on Fedora27 nor gcc.
+ // Not fixed on FreeBSD as of llvm 6.0.1.
+ std::tie(first, last) = static_cast<const decltype(m_ip_pool)::range::super_type &>(m_ip_pool.equal_range(addr));
+ // The range is all that is needed in the match IP case, otherwise need to scan for matching fqdn.
+ // Note the port is matched as part of the address key so it doesn't need to be checked again.
if (TS_SERVER_SESSION_SHARING_MATCH_IP != match_style) {
- while (loc) {
- if (loc->hostname_hash == hostname_hash && validate_sni(sm, loc->get_netvc())) {
+ while (last != first) {
+ --last;
+ if (last->hostname_hash == hostname_hash && validate_sni(sm, last->get_netvc())) {
+ zret = HSM_DONE;
break;
}
- ++loc;
}
}
- if (loc) {
- to_return = loc;
- m_ip_pool.remove(loc);
- m_host_pool.remove(m_host_pool.find(loc));
+ if (zret == HSM_DONE) {
+ to_return = last;
+ m_ip_pool.erase(last);
+ m_fqdn_pool.erase(to_return);
}
}
return zret;
@@ -152,7 +161,7 @@ ServerSessionPool::releaseSession(HttpServerSession *ss)
ss->get_netvc()->set_active_timeout(ss->get_netvc()->get_active_timeout());
// put it in the pools.
m_ip_pool.insert(ss);
- m_host_pool.insert(ss);
+ m_fqdn_pool.insert(ss);
Debug("http_ss",
"[%" PRId64 "] [release session] "
@@ -189,9 +198,10 @@ ServerSessionPool::eventHandler(int event, void *data)
sockaddr const *addr = net_vc->get_remote_addr();
HttpConfigParams *http_config_params = HttpConfig::acquire();
bool found = false;
+ auto spot = m_ip_pool.find(addr);
- for (ServerSessionPool::IPHashTable::Location lh = m_ip_pool.find(addr); lh; ++lh) {
- if ((s = lh)->get_netvc() == net_vc) {
+ while (spot != m_ip_pool.end() && spot->_ip_link.equal(addr, spot)) {
+ if ((s = spot)->get_netvc() == net_vc) {
// if there was a timeout of some kind on a keep alive connection, and
// keeping the connection alive will not keep us above the # of max connections
// to the origin and we are below the min number of keep alive connections to this
@@ -218,8 +228,8 @@ ServerSessionPool::eventHandler(int event, void *data)
HttpDebugNames::get_event_name(event));
ink_assert(s->state == HSS_KA_SHARED);
// Out of the pool! Now!
- m_ip_pool.remove(lh);
- m_host_pool.remove(m_host_pool.find(s));
+ m_ip_pool.erase(spot);
+ m_fqdn_pool.erase(s);
// Drop connection on this end.
s->do_io_close();
found = true;
diff --git a/proxy/http/HttpSessionManager.h b/proxy/http/HttpSessionManager.h
index 66998a7..0c0f297 100644
--- a/proxy/http/HttpSessionManager.h
+++ b/proxy/http/HttpSessionManager.h
@@ -34,7 +34,7 @@
#include "P_EventSystem.h"
#include "HttpServerSession.h"
-#include <ts/Map.h>
+#include <ts/IntrusiveHashMap.h>
class ProxyClientTransaction;
class HttpSM;
@@ -67,56 +67,8 @@ public:
static bool validate_sni(HttpSM *sm, NetVConnection *netvc);
protected:
- /// Interface class for IP map.
- struct IPHashing {
- typedef uint32_t ID;
- typedef sockaddr const *Key;
- typedef HttpServerSession Value;
- typedef DList(HttpServerSession, ip_hash_link) ListHead;
-
- static ID
- hash(Key key)
- {
- return ats_ip_hash(key);
- }
- static Key
- key(Value const *value)
- {
- return &value->get_server_ip().sa;
- }
- static bool
- equal(Key lhs, Key rhs)
- {
- return ats_ip_addr_port_eq(lhs, rhs);
- }
- };
-
- /// Interface class for FQDN map.
- struct HostHashing {
- typedef uint64_t ID;
- typedef CryptoHash const &Key;
- typedef HttpServerSession Value;
- typedef DList(HttpServerSession, host_hash_link) ListHead;
-
- static ID
- hash(Key key)
- {
- return key.fold();
- }
- static Key
- key(Value const *value)
- {
- return value->hostname_hash;
- }
- static bool
- equal(Key lhs, Key rhs)
- {
- return lhs == rhs;
- }
- };
-
- typedef TSHashTable<IPHashing> IPHashTable; ///< Sessions by IP address.
- typedef TSHashTable<HostHashing> HostHashTable; ///< Sessions by host name.
+ using IPTable = IntrusiveHashMap<HttpServerSession::IPLinkage>;
+ using FQDNTable = IntrusiveHashMap<HttpServerSession::FQDNLinkage>;
public:
/** Check if a session matches address and host name.
@@ -142,8 +94,8 @@ public:
// Pools of server sessions.
// Note that each server session is stored in both pools.
- IPHashTable m_ip_pool;
- HostHashTable m_host_pool;
+ IPTable m_ip_pool;
+ FQDNTable m_fqdn_pool;
};
class HttpSessionManager
[trafficserver] 02/08: IntrusiveDList: Update erase methods.
Posted by am...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
commit c157bdcb38d719b3413f19ed1f6f8fc3246ccf34
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Sun Jul 22 21:24:02 2018 -0500
IntrusiveDList: Update erase methods.
---
.../internal-libraries/intrusive-list.en.rst | 35 ++++++++++++-
lib/ts/IntrusiveDList.h | 57 ++++++++++++++++++++--
2 files changed, 86 insertions(+), 6 deletions(-)
diff --git a/doc/developer-guide/internal-libraries/intrusive-list.en.rst b/doc/developer-guide/internal-libraries/intrusive-list.en.rst
index 7a9c3b6..32e78c7 100644
--- a/doc/developer-guide/internal-libraries/intrusive-list.en.rst
+++ b/doc/developer-guide/internal-libraries/intrusive-list.en.rst
@@ -23,7 +23,9 @@ IntrusiveDList
:class:`IntrusiveDList` is a class that provides a double linked list using pointers embeded in the
object. :class:`IntrusiveDList` also acts as a queue. No memory management is done - objects can be
added to and removed from the list but the allocation and deallocation of the objects must be
-handled outside the class. This class supports an STL compliant bidirectional iteration.
+handled outside the class. This class supports an STL compliant bidirectional iteration. The
+iterators automatically convert to pointer as in normal use of this class the contained elements
+will be referenced by pointers.
Definition
**********
@@ -52,6 +54,16 @@ Definition
Return a reference to the previous element pointer embedded in the element :arg:`elt`.
+ .. type:: iterator
+
+ An STL compliant bidirectional iterator on elements in the list. :type:`iterator` has a user
+ defined conversion to :code:`value_type *` for convenience in use.
+
+ .. type:: const_iterator
+
+ An STL compliant bidirectional constant iterator on elements in the list. :type:`const_iterator` has a user
+ defined conversion to :code:`const value_type *` for convenience in use.
+
.. function:: value_type * head()
Return a pointer to the head element in the list. This may be :code:`nullptr` if the list is empty.
@@ -84,6 +96,27 @@ Definition
Remove the tail element and return a pointer to it. May be :code:`nullptr` if the list is empty.
+ .. function:: iterator erase(const iterator & loc)
+
+ Remove the element at :arg:`loc`. Return the element after :arg:`loc`.
+
+ .. function:: iterator erase(const iterator & start, const iterator & limit)
+
+ Remove the elements in the half open range from and including :arg:`start`
+ to but not including :arg:`limit`.
+
+ .. function:: iterator iterator_for(value_type * value)
+
+ Return an :type:`iterator` that refers to :arg:`value`. :arg:`value` is checked for being in a
+ list but there is no guarantee it is in this list. If :arg:`value` is not in a list then the
+ end iterator is returned.
+
+ .. function:: const_iterator iterator_for(const value_type * value)
+
+ Return a :type:`const_iterator` that refers to :arg:`value`. :arg:`value` is checked for being
+ in a list but there is no guarantee it is in this list. If :arg:`value` is not in a list then
+ the end iterator is returned.
+
Usage
*****
diff --git a/lib/ts/IntrusiveDList.h b/lib/ts/IntrusiveDList.h
index 98f92d4..44fa8c5 100644
--- a/lib/ts/IntrusiveDList.h
+++ b/lib/ts/IntrusiveDList.h
@@ -265,9 +265,18 @@ public:
/// @return This list.
self_type &insert_before(iterator const &target, value_type *v);
- /// Take @a elt out of this list.
- /// @return This list.
- self_type &erase(value_type *v);
+ /// Take @a v out of this list.
+ /// @return The element after @a v.
+ value_type *erase(value_type *v);
+
+ /// Take the element at @a loc out of this list.
+ /// @return Iterator for the next element.
+ iterator erase(const iterator &loc);
+
+ /// Take elements out of the list.
+ /// Remove elements start with @a start up to but not including @a limit.
+ /// @return @a limit
+ iterator erase(const iterator &start, const iterator &limit);
/// Remove all elements.
/// @note @b No memory management is done!
@@ -577,12 +586,15 @@ IntrusiveDList<L>::insert_before(iterator const &target, value_type *v) -> self_
template <typename L>
auto
-IntrusiveDList<L>::erase(value_type *v) -> self_type &
+IntrusiveDList<L>::erase(value_type *v) -> value_type *
{
+ value_type *zret{nullptr};
+
if (L::prev_ptr(v)) {
L::next_ptr(L::prev_ptr(v)) = L::next_ptr(v);
}
if (L::next_ptr(v)) {
+ zret = L::next_ptr(v);
L::prev_ptr(L::next_ptr(v)) = L::prev_ptr(v);
}
if (v == _head) {
@@ -594,10 +606,45 @@ IntrusiveDList<L>::erase(value_type *v) -> self_type &
L::prev_ptr(v) = L::next_ptr(v) = nullptr;
--_count;
- return *this;
+ return zret;
}
template <typename L>
+auto
+IntrusiveDList<L>::erase(const iterator &loc) -> iterator
+{
+ return this->iterator_for(this->erase(loc._v));
+};
+
+template <typename L>
+auto
+IntrusiveDList<L>::erase(const iterator &first, const iterator &limit) -> iterator
+{
+ value_type *spot = first;
+ value_type *prev{L::prev_ptr(spot)};
+ if (prev) {
+ L::next_ptr(prev) = limit;
+ }
+ if (spot == _head) {
+ _head = limit;
+ }
+ // tail is only updated if @a limit is @a end (e.g., @c nullptr).
+ if (nullptr == limit) {
+ _tail = prev;
+ } else {
+ L::prev_ptr(limit) = prev;
+ }
+ // Clear links in removed elements.
+ while (spot != limit) {
+ value_type *target{spot};
+ spot = L::next_ptr(spot);
+ L::prev_ptr(target) = L::next_ptr(target) = nullptr;
+ };
+
+ return {limit._v, this};
+};
+
+template <typename L>
size_t
IntrusiveDList<L>::count() const
{
[trafficserver] 08/08: HttpConnectionCount: Replace TSHashTable
with IntrusiveHashMap.
Posted by am...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
commit a34b7b873319cd8638f1b21eaf19f9d6d36a09b4
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Sat Jul 28 18:32:02 2018 -0500
HttpConnectionCount: Replace TSHashTable with IntrusiveHashMap.
---
proxy/http/HttpConnectionCount.cc | 2 +-
proxy/http/HttpConnectionCount.h | 75 ++++++++++++++++++++++++++-------------
2 files changed, 51 insertions(+), 26 deletions(-)
diff --git a/proxy/http/HttpConnectionCount.cc b/proxy/http/HttpConnectionCount.cc
index ca2f495..5aabff8 100644
--- a/proxy/http/HttpConnectionCount.cc
+++ b/proxy/http/HttpConnectionCount.cc
@@ -181,7 +181,7 @@ OutboundConnTrack::obtain(TxnConfig const &txn_cnf, std::string_view fqdn, IpEnd
Group::Key key{addr, hash, txn_cnf.match};
std::lock_guard<std::mutex> lock(_imp._mutex); // Table lock
auto loc = _imp._table.find(key);
- if (loc.isValid()) {
+ if (loc != _imp._table.end()) {
zret._g = loc;
} else {
zret._g = new Group(key, fqdn);
diff --git a/proxy/http/HttpConnectionCount.h b/proxy/http/HttpConnectionCount.h
index 2cd7731..12a3178 100644
--- a/proxy/http/HttpConnectionCount.h
+++ b/proxy/http/HttpConnectionCount.h
@@ -33,7 +33,7 @@
#include <ts/ink_config.h>
#include <ts/ink_mutex.h>
#include <ts/ink_inet.h>
-#include <ts/Map.h>
+#include <ts/IntrusiveHashMap.h>
#include <ts/Diags.h>
#include <ts/CryptoHash.h>
#include <ts/BufferWriterForward.h>
@@ -123,7 +123,9 @@ public:
std::atomic<int> _in_queue{0}; ///< # of connections queued, waiting for a connection.
std::atomic<Ticker> _last_alert{0}; ///< Absolute time of the last alert.
- LINK(Group, _link); ///< Intrusive hash table support.
+ // Links for intrusive container.
+ Group *_next{nullptr};
+ Group *_prev{nullptr};
/** Constructor.
* Construct from @c Key because the use cases do a table lookup first so the @c Key is already constructed.
@@ -252,33 +254,24 @@ protected:
static GlobalConfig *_global_config; ///< Global configuration data.
/// Types and methods for the hash table.
- struct HashDescriptor {
- using ID = uint64_t;
- using Key = Group::Key const &;
- using Value = Group;
- using ListHead = DList(Value, _link);
-
- static ID
- hash(Key key)
- {
- return Group::hash(key);
- }
- static Key
- key(Value *v)
- {
- return v->_key;
- }
- static bool
- equal(Key lhs, Key rhs)
- {
- return Group::equal(lhs, rhs);
- }
+ struct Linkage {
+ using key_type = Group::Key const &;
+ using value_type = Group;
+
+ static value_type *&next_ptr(value_type *value);
+ static value_type *&prev_ptr(value_type *value);
+
+ static uint64_t hash_of(key_type key);
+
+ static key_type key_of(value_type *v);
+
+ static bool equal(key_type lhs, key_type rhs);
};
/// Internal implementation class instance.
struct Imp {
- TSHashTable<HashDescriptor> _table; ///< Hash table of upstream groups.
- std::mutex _mutex; ///< Lock for insert & find.
+ IntrusiveHashMap<Linkage> _table; ///< Hash table of upstream groups.
+ std::mutex _mutex; ///< Lock for insert & find.
};
static Imp _imp;
@@ -401,6 +394,38 @@ OutboundConnTrack::TxnState::rescheduled()
++_g->_rescheduled;
}
+/* === Linkage === */
+inline auto
+OutboundConnTrack::Linkage::next_ptr(value_type *value) -> value_type *&
+{
+ return value->_next;
+}
+
+inline auto
+OutboundConnTrack::Linkage::prev_ptr(value_type *value) -> value_type *&
+{
+ return value->_prev;
+}
+
+inline uint64_t
+OutboundConnTrack::Linkage::hash_of(key_type key)
+{
+ return Group::hash(key);
+}
+
+inline auto
+OutboundConnTrack::Linkage::key_of(value_type *value) -> key_type
+{
+ return value->_key;
+}
+
+inline bool
+OutboundConnTrack::Linkage::equal(key_type lhs, key_type rhs)
+{
+ return Group::equal(lhs, rhs);
+}
+/* === */
+
Action *register_ShowConnectionCount(Continuation *, HTTPHdr *);
namespace ts
[trafficserver] 05/08: IntrusiveHashMap: Update erase methods. Add
additional iterator_for methods for erase.
Posted by am...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
commit 546a267efd94805f8c7655b4784c15fb31d3dc8e
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Sun Jul 22 21:25:15 2018 -0500
IntrusiveHashMap: Update erase methods.
Add additional iterator_for methods for erase.
---
lib/ts/IntrusiveHashMap.h | 103 ++++++++++++++++++++++++++++++++++------------
1 file changed, 76 insertions(+), 27 deletions(-)
diff --git a/lib/ts/IntrusiveHashMap.h b/lib/ts/IntrusiveHashMap.h
index c69a9a5..003326b 100644
--- a/lib/ts/IntrusiveHashMap.h
+++ b/lib/ts/IntrusiveHashMap.h
@@ -225,23 +225,30 @@ public:
/** Get an @c iterator for the value @a v.
- This is a bit obscure but needed in certain cases. It should only be used on a @a value that
- is already known to be in the table.
+ This is a bit obscure but needed in certain cases. Because the interface assumes iterators are always valid
+ this avoid containment checks, which is useful if @a v is already known to be in the container.
*/
iterator iterator_for(value_type *v);
+ const_iterator iterator_for(const value_type *v) const;
/** Remove the value at @a loc from the table.
@note This does @b not clean up the removed elements. Use carefully to avoid leaks.
- @return @c true if the value was removed, @c false otherwise.
+ @return An iterator the next value past @a loc. [STL compatibility]
*/
- bool erase(iterator const &loc);
+ iterator erase(iterator const &loc);
/// Remove all elements in the @c range @a r.
- bool erase(range const &r);
- /// Remove all elements in the range (first, last]
- bool erase(iterator const &first, iterator const &last);
+ iterator erase(range const &r);
+
+ /// Remove all elements in the range (start, limit]
+ iterator erase(iterator const &start, iterator const &limit);
+
+ /// Remove a @a value from the container.
+ /// @a value is checked for being a member of the container.
+ /// @return @c true if @a value was in the container and removed, @c false if it was not in the container.
+ bool erase(value_type *value);
/** Apply @a F(value_type&) to every element in the hash map.
*
@@ -479,6 +486,13 @@ IntrusiveHashMap<H>::equal_range(key_type key) const -> const_range
template <typename H>
auto
+IntrusiveHashMap<H>::iterator_for(const value_type *v) const -> const_iterator
+{
+ return _list.iterator_for(v);
+}
+
+template <typename H>
+auto
IntrusiveHashMap<H>::iterator_for(value_type *v) -> iterator
{
return _list.iterator_for(v);
@@ -541,31 +555,66 @@ IntrusiveHashMap<H>::insert(value_type *v)
}
template <typename H>
-bool
-IntrusiveHashMap<H>::erase(iterator const &loc)
+auto
+IntrusiveHashMap<H>::erase(iterator const &loc) -> iterator
{
- bool zret = false;
+ value_type *v = loc;
+ iterator zret = ++(this->iterator_for(v)); // get around no const_iterator -> iterator.
+ Bucket *b = this->bucket_for(H::key_of(v));
+ value_type *nv = H::next_ptr(v);
+ value_type *limit = b->limit();
+ if (b->_v == v) { // removed first element in bucket, update bucket
+ if (limit == nv) { // that was also the only element, deactivate bucket
+ _active_buckets.erase(b);
+ b->clear();
+ } else {
+ b->_v = nv;
+ --b->_count;
+ }
+ }
+ _list.erase(loc);
+ return zret;
+}
+template <typename H>
+bool
+IntrusiveHashMap<H>::erase(value_type *value)
+{
+ auto loc = this->find(value);
if (loc != this->end()) {
- value_type *v = &*loc;
- Bucket *b = this->bucket_for(H::key_of(v));
- if (b->contains(v)) {
- value_type *nv = H::next_ptr(v);
- value_type *limit = b->limit();
- if (b->_v == v) { // removed first element in bucket, update bucket
- if (limit == nv) { // that was also the only element, deactivate bucket
- _active_buckets.erase(b);
- b->clear();
- } else {
- b->_v = nv;
- --b->_count;
- }
- }
- zret = true;
- _list.erase(v);
+ this->erase(loc);
+ return true;
+ }
+ return false;
+}
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::erase(iterator const &start, iterator const &limit) -> iterator
+{
+ auto spot{start};
+ Bucket *bucket{this->bucket_for(spot)};
+ while (spot != limit) {
+ auto target = bucket;
+ bucket = bucket->_link._next; // bump now to avoid forward iteration problems in case of bucket removal.
+ value_type *v_limit = bucket ? bucket->_v : nullptr;
+ while (spot != v_limit && spot != limit) {
+ --(target->_count);
+ ++spot;
+ }
+ if (target->_count == 0) {
+ _active_buckets.erase(target);
}
}
- return zret;
+ _list.erase(start, limit);
+ return _list.iterator_for(limit); // convert from const_iterator back to iterator
+};
+
+template <typename H>
+auto
+IntrusiveHashMap<H>::erase(range const &r) -> iterator
+{
+ return this->erase(r.first, r.second);
}
template <typename H>
[trafficserver] 03/08: IntrusiveHashMap: remove from "ts"
namespace. The predecessor class, TSHashTable,
wasn't in "ts" and having worked with IntrusiveHashMap for a while,
I think it's best this isn't either.
Posted by am...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
commit f462170c3801526250c169fe29d93639be75c9ee
Author: Alan M. Carroll <am...@apache.org>
AuthorDate: Fri Jul 27 23:26:32 2018 -0500
IntrusiveHashMap: remove from "ts" namespace.
The predecessor class, TSHashTable, wasn't in "ts" and having worked with IntrusiveHashMap for a while,
I think it's best this isn't either.
---
lib/ts/IntrusiveHashMap.h | 4 ----
lib/ts/unit-tests/test_IntrusiveHashMap.cc | 2 +-
2 files changed, 1 insertion(+), 5 deletions(-)
diff --git a/lib/ts/IntrusiveHashMap.h b/lib/ts/IntrusiveHashMap.h
index b39514c..84a64fa 100644
--- a/lib/ts/IntrusiveHashMap.h
+++ b/lib/ts/IntrusiveHashMap.h
@@ -28,8 +28,6 @@
#include <algorithm>
#include <ts/IntrusiveDList.h>
-namespace ts
-{
/** Intrusive Hash Table.
Values stored in this container are not destroyed when the container is destroyed or removed from the container.
@@ -658,5 +656,3 @@ IntrusiveHashMap<H>::get_expansion_limit() const
return _expansion_limit;
}
/* ---------------------------------------------------------------------------------------------- */
-
-} // namespace ts
diff --git a/lib/ts/unit-tests/test_IntrusiveHashMap.cc b/lib/ts/unit-tests/test_IntrusiveHashMap.cc
index ba30e97..67a0377 100644
--- a/lib/ts/unit-tests/test_IntrusiveHashMap.cc
+++ b/lib/ts/unit-tests/test_IntrusiveHashMap.cc
@@ -78,7 +78,7 @@ struct ThingMapDescriptor {
}
};
-using Map = ts::IntrusiveHashMap<ThingMapDescriptor>;
+using Map = IntrusiveHashMap<ThingMapDescriptor>;
} // namespace