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
The following commit(s) were added to refs/heads/master by this push: new 9082b9219 libswoc: Final elimination of obsolete IpMap. (#9548) 9082b9219 is described below commit 9082b92190ef37862b56ef8c549e1e32f104dc75 Author: Alan M. Carroll <a...@apache.org> AuthorDate: Wed Mar 22 10:01:42 2023 -0500 libswoc: Final elimination of obsolete IpMap. (#9548) --- include/tscore/IpMap.h | 504 ------------- src/tscore/CMakeLists.txt | 1 - src/tscore/IpMap.cc | 1342 ----------------------------------- src/tscore/Makefile.am | 2 - src/tscore/unit_tests/test_IpMap.cc | 633 ----------------- 5 files changed, 2482 deletions(-) diff --git a/include/tscore/IpMap.h b/include/tscore/IpMap.h deleted file mode 100644 index 72c54482e..000000000 --- a/include/tscore/IpMap.h +++ /dev/null @@ -1,504 +0,0 @@ -/** @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. -*/ - -#pragma once - -#include <algorithm> -#include <utility> - -#include "tscore/ink_platform.h" -#include "tscore/ink_defs.h" -#include "tscore/RbTree.h" -#include "tscore/ink_inet.h" -#include "tscpp/util/IntrusiveDList.h" -#include "tscore/ink_assert.h" -#include "tscore/BufferWriterForward.h" - -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 { - using Metric = T; ///< Metric (storage) type. - using ArgType = A; ///< 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. -} // namespace detail -} // namespace ts - -/** 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 explicitly 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: - using self_type = IpMap; ///< Self reference type. - - class iterator; // forward declare. - - static constexpr in_addr_t RAW_IP4_MIN_ADDR = 0; - static constexpr IpAddr IP4_MIN_ADDR{RAW_IP4_MIN_ADDR}; - static constexpr in_addr_t RAW_IP4_MAX_ADDR = ~0; - static constexpr IpAddr IP4_MAX_ADDR{RAW_IP4_MAX_ADDR}; - - static constexpr in6_addr RAW_IP6_MIN_ADDR = {{{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}}}; - static constexpr IpAddr IP6_MIN_ADDR{RAW_IP6_MIN_ADDR}; - static constexpr in6_addr RAW_IP6_MAX_ADDR = {{{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}}}; - static constexpr IpAddr IP6_MAX_ADDR{RAW_IP6_MAX_ADDR}; - - /** Public API for intervals in the map. - */ - class Node : protected ts::detail::RBNode - { - friend class iterator; - friend class IpMap; - - public: - using self_type = Node; ///< Self reference type. - /// Default constructor. - Node() {} - /// 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_type & - setData(void *data ///< Client data pointer to store. - ) - { - _data = data; - return *this; - } - /// @return Minimum value of the interval. - virtual sockaddr const *min() const = 0; - /// @return Maximum value of the interval. - virtual sockaddr const *max() const = 0; - - protected: - void *_data = nullptr; ///< 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: - using self_type = iterator; ///< Self reference type. - using value_type = Node; ///< Referenced type for iterator. - using difference_type = int; ///< Distance type. - using pointer = Node *; ///< Pointer to referent. - using reference = Node &; ///< Reference to referent. - using iterator_category = std::bidirectional_iterator_tag; - /// Default constructor. - iterator() = default; - reference operator*() const; //!< value operator - pointer operator->() const; //!< dereference operator - self_type &operator++(); //!< next node (prefix) - self_type operator++(int); //!< next node (postfix) - self_type &operator--(); ///< previous node (prefix) - self_type operator--(int); ///< next node (postfix) - - /** Equality. - @return @c true if the iterators refer to the same node. - */ - bool operator==(self_type const &that) const; - /** Inequality. - @return @c true if the iterators refer to different nodes. - */ - bool - operator!=(self_type const &that) const - { - return !(*this == that); - } - - private: - /// Construct a valid iterator. - iterator(IpMap const *tree, Node *node) : _tree(tree), _node(node) {} - IpMap const *_tree = nullptr; ///< Container. - Node *_node = nullptr; //!< Current node. - }; - - IpMap() = default; ///< Default constructor. - IpMap(self_type const &that) = delete; - IpMap(self_type &&that) noexcept; - ~IpMap(); ///< Destructor. - - self_type &operator=(self_type const &that) = delete; - self_type &operator=(self_type &&that); - - /** Mark a range. - All addresses in the range [ @a min , @a max ] are marked with @a data. - @return This object. - */ - self_type &mark(sockaddr const *min, ///< Minimum value in range. - sockaddr const *max, ///< Maximum value in range. - void *data = nullptr ///< 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_type &mark(in_addr_t min, ///< Minimum address (network order). - in_addr_t max, ///< Maximum address (network order). - void *data = nullptr ///< Client data. - ); - - /** 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_type &mark(IpAddr const &min, ///< Minimum address (network order). - IpAddr const &max, ///< Maximum address (network order). - void *data = nullptr ///< Client data. - ); - - /** Mark an IPv4 address @a addr with @a data. - This is equivalent to calling @c mark(addr, addr, data). - @note Convenience overload for IPv4 addresses. - @return This object. - */ - self_type &mark(in_addr_t addr, ///< Address (network order). - void *data = nullptr ///< Client data. - ); - - /** Mark a range. - All addresses in the range [ @a min , @a max ] are marked with @a data. - @note Convenience overload. - @return This object. - */ - self_type &mark(IpEndpoint const *min, ///< Minimum address (network order). - IpEndpoint const *max, ///< Maximum address (network order). - void *data = nullptr ///< Client data. - ); - - /** Mark an address @a addr with @a data. - This is equivalent to calling @c mark(addr, addr, data). - @note Convenience overload. - @return This object. - */ - self_type &mark(IpEndpoint const *addr, ///< Address (network order). - void *data = nullptr ///< 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_type &unmark(sockaddr const *min, ///< Minimum value. - sockaddr const *max ///< Maximum value. - ); - /// Unmark addresses (overload). - self_type &unmark(IpAddr const &min, IpAddr const &max); - /// Unmark addresses (overload). - self_type &unmark(IpEndpoint const *min, IpEndpoint const *max); - /// Unmark overload. - self_type &unmark(in_addr_t min, ///< Minimum of range to unmark. - in_addr_t max ///< Maximum of range to unmark. - ); - - /** Fill addresses. - - This background fills using the range. All addresses in the - range that are @b not present in the map are added. No - previously present address is changed. - - @note This is useful for filling in first match tables because @a data for already present - addresses is not changed. - - @return This object. - */ - self_type &fill(sockaddr const *min, sockaddr const *max, void *data = nullptr); - /// Fill addresses (overload). - self_type &fill(IpEndpoint const *min, IpEndpoint const *max, void *data = nullptr); - /// Fill addresses (overload). - self_type &fill(IpAddr const &min, IpAddr const &max, void *data = nullptr); - /// Fill addresses (overload). - self_type &fill(in_addr_t min, in_addr_t max, void *data = nullptr); - - /** 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 nullptr, @c *ptr - is set to the client data for the address. - */ - bool contains(sockaddr const *target, ///< Search target (network order). - void **ptr = nullptr ///< Client data return. - ) const; - - /** Test for membership. - - @note Convenience overload for IPv4. - - @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 nullptr, @c *ptr - is set to the client data for the address. - */ - bool contains(in_addr_t target, ///< Search target (network order). - void **ptr = nullptr ///< Client data return. - ) const; - - /** Test for membership. - - @note Convenience overload for @c IpEndpoint. - - @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 nullptr, @c *ptr - is set to the client data for the address. - */ - bool contains(IpEndpoint const *target, ///< Search target (network order). - void **ptr = nullptr ///< Client data return. - ) const; - - /** Test for membership. - - @note Convenience overload for @c IpAddr. - - @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 nullptr, @c *ptr - is set to the client data for the address. - */ - bool contains(IpAddr const &target, ///< Search target (network order). - void **ptr = nullptr ///< Client data return. - ) const; - - /** Remove all addresses from the map. - - @note This is much faster than @c unmark. - @return This object. - */ - self_type &clear(); - - /// Iterator for first element. - iterator begin() const; - /// Iterator past last element. - iterator end() const; - /// @return Number of distinct ranges in the map. - size_t count() const; - - /** Validate internal data structures. - @note Intended for debugging, not general client use. - */ - void validate(); - - /** Generate formatted output. - * - * @param w Destination of formatted output. - * @param spec Formatting specification. - * @return @a w - */ - ts::BufferWriter &describe(ts::BufferWriter &w, ts::BWFSpec const &spec) const; - -protected: - /// Force the IPv4 map to exist. - /// @return The IPv4 map. - ts::detail::Ip4Map *force4(); - /// Force the IPv6 map to exist. - /// @return The IPv6 map. - ts::detail::Ip6Map *force6(); - - ts::detail::Ip4Map *_m4 = nullptr; ///< Map of IPv4 addresses. - ts::detail::Ip6Map *_m6 = nullptr; ///< Map of IPv6 addresses. -}; - -inline IpMap & -IpMap::mark(in_addr_t addr, void *data) -{ - return this->mark(addr, addr, data); -} - -inline IpMap & -IpMap::mark(IpAddr const &min, IpAddr const &max, void *data) -{ - IpEndpoint x, y; - x.assign(min); - y.assign(max); - return this->mark(&x.sa, &y.sa, data); -} - -inline IpMap & -IpMap::mark(IpEndpoint const *addr, void *data) -{ - return this->mark(&addr->sa, &addr->sa, data); -} - -inline IpMap & -IpMap::mark(IpEndpoint const *min, IpEndpoint const *max, void *data) -{ - return this->mark(&min->sa, &max->sa, data); -} - -inline IpMap & -IpMap::unmark(IpEndpoint const *min, IpEndpoint const *max) -{ - return this->unmark(&min->sa, &max->sa); -} - -inline IpMap & -IpMap::unmark(IpAddr const &min, IpAddr const &max) -{ - IpEndpoint x, y; - x.assign(min); - y.assign(max); - return this->unmark(&x.sa, &y.sa); -} - -inline IpMap & -IpMap::fill(IpEndpoint const *min, IpEndpoint const *max, void *data) -{ - return this->fill(&min->sa, &max->sa, data); -} - -inline IpMap & -IpMap::fill(IpAddr const &min, IpAddr const &max, void *data) -{ - IpEndpoint x, y; - x.assign(min); - y.assign(max); - return this->fill(&x.sa, &y.sa, data); -} - -inline bool -IpMap::contains(IpEndpoint const *target, void **ptr) const -{ - return this->contains(&target->sa, ptr); -} - -inline bool -IpMap::contains(IpAddr const &addr, void **ptr) const -{ - IpEndpoint ip; - ip.assign(addr); - return this->contains(&ip.sa, ptr); -} - -inline IpMap::iterator -IpMap::end() const -{ - return iterator(this, nullptr); -} - -inline IpMap::iterator -IpMap::iterator::operator++(int) -{ - iterator old(*this); - ++*this; - return old; -} - -inline IpMap::iterator -IpMap::iterator::operator--(int) -{ - self_type 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*() const -{ - return *_node; -} - -inline IpMap::iterator::pointer -IpMap::iterator::operator->() const -{ - return _node; -} - -namespace ts -{ -inline BufferWriter & -bwformat(BufferWriter &w, BWFSpec const &spec, IpMap const &map) -{ - return map.describe(w, spec); -} -} // namespace ts diff --git a/src/tscore/CMakeLists.txt b/src/tscore/CMakeLists.txt index ff7acdfbe..e16a8c237 100644 --- a/src/tscore/CMakeLists.txt +++ b/src/tscore/CMakeLists.txt @@ -123,7 +123,6 @@ add_executable(test_tscore unit_tests/test_History.cc unit_tests/test_IntrusiveHashMap.cc unit_tests/test_IntrusivePtr.cc - unit_tests/test_IpMap.cc unit_tests/test_List.cc unit_tests/test_MMH.cc unit_tests/test_MT_hashtable.cc diff --git a/src/tscore/IpMap.cc b/src/tscore/IpMap.cc deleted file mode 100644 index 5200e1c19..000000000 --- a/src/tscore/IpMap.cc +++ /dev/null @@ -1,1342 +0,0 @@ -/** @file - IP address map support. - - Provide the ability to create a range based mapping for the IP - address space. Addresses can be added and removed and each address - is associated with arbitrary client data. - - @internal 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). - - @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. - */ - -// Validation / printing disabled until I figure out how to generalize so -// as to not tie reporting into a particular project environment. - -/* @internal It is a bit ugly to store a @c sockaddr equivalent in the table - as all that is actually needed is the raw address. Unfortunately some clients - require a @c sockaddr* return via the iterator and that's expensive to - compute all the time. I should, at some point, re-examine this and see if we - can do better and have a more compact internal format. I suspect I did this - before we had IpAddr as a type. -*/ - -#include "tscore/IpMap.h" -#include "tscore/ink_inet.h" -#include "tscore/BufferWriter.h" - -namespace ts -{ -namespace detail -{ - // Helper functions - - inline int - cmp(sockaddr_in6 const &lhs, sockaddr_in6 const &rhs) - { - return memcmp(lhs.sin6_addr.s6_addr, rhs.sin6_addr.s6_addr, TS_IP6_SIZE); - } - - /// Less than. - inline bool - operator<(sockaddr_in6 const &lhs, sockaddr_in6 const &rhs) - { - return ts::detail::cmp(lhs, rhs) < 0; - } - inline bool - operator<(sockaddr_in6 const *lhs, sockaddr_in6 const &rhs) - { - return ts::detail::cmp(*lhs, rhs) < 0; - } - /// Less than. - inline bool - operator<(sockaddr_in6 const &lhs, sockaddr_in6 const *rhs) - { - return ts::detail::cmp(lhs, *rhs) < 0; - } - /// Equality. - inline bool - operator==(sockaddr_in6 const &lhs, sockaddr_in6 const *rhs) - { - return ts::detail::cmp(lhs, *rhs) == 0; - } - /// Equality. - inline bool - operator==(sockaddr_in6 const *lhs, sockaddr_in6 const &rhs) - { - return ts::detail::cmp(*lhs, rhs) == 0; - } - /// Equality. - inline bool - operator==(sockaddr_in6 const &lhs, sockaddr_in6 const &rhs) - { - return ts::detail::cmp(lhs, rhs) == 0; - } - /// Less than or equal. - inline bool - operator<=(sockaddr_in6 const &lhs, sockaddr_in6 const *rhs) - { - return ts::detail::cmp(lhs, *rhs) <= 0; - } - /// Less than or equal. - inline bool - operator<=(sockaddr_in6 const &lhs, sockaddr_in6 const &rhs) - { - return ts::detail::cmp(lhs, rhs) <= 0; - } - /// Greater than or equal. - inline bool - operator>=(sockaddr_in6 const &lhs, sockaddr_in6 const &rhs) - { - return ts::detail::cmp(lhs, rhs) >= 0; - } - /// Greater than or equal. - inline bool - operator>=(sockaddr_in6 const &lhs, sockaddr_in6 const *rhs) - { - return ts::detail::cmp(lhs, *rhs) >= 0; - } - /// Greater than. - inline bool - operator>(sockaddr_in6 const &lhs, sockaddr_in6 const *rhs) - { - return ts::detail::cmp(lhs, *rhs) > 0; - } - - /** 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; - - using self_type = IpMapBase<N>; ///< Self reference type. - using ArgType = typename N::ArgType; ///< Import type. - using Metric = typename N::Metric; ///< Import type.g482 - - IpMapBase() = default; - IpMapBase(self_type &&that) : _root(that._root), _list(std::move(that._list)) { that._root = nullptr; } - ~IpMapBase(); - /** Mark a range. - All addresses in the range [ @a min , @a max ] are marked with @a data. - @return This object. - */ - self_type &mark(ArgType min, ///< Minimum value in range. - ArgType max, ///< Maximum value in range. - void *data = nullptr ///< 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_type &unmark(ArgType min, ArgType max); - - /** Fill addresses. - - This background fills using the range. All addresses in the - range that are @b not present in the map are added. No - previously present address is changed. - - @note This is useful for filling in first match tables. - - @return This object. - */ - self_type &fill(ArgType min, ArgType max, void *data = nullptr); - - /** 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 nullptr, @c *ptr - is set to the client data for the address. - */ - bool contains(ArgType target, ///< Search target value. - void **ptr = nullptr ///< Client data return. - ) const; - - /** Remove all addresses in the map. - - @note This is much faster than using @c unmark with a range of - all addresses. - - @return This object. - */ - self_type &clear(); - - /** Lower bound for @a target. @return The node whose minimum value - is the largest that is not greater than @a target, or @c nullptr 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 insert_after(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 insert_before(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(); - - /// @return The number of distinct ranges. - size_t count() const; - - /** Generate formatted output. - * - * @param w Destination of the output. - * @param spec Format specification. - * @return @a w. - */ - ts::BufferWriter &describe(ts::BufferWriter &w, ts::BWFSpec const &spec) const; - - // Helper methods. - N * - prev(RBNode *n) const - { - return static_cast<N *>(n->_prev); - } - N * - next(RBNode *n) const - { - return static_cast<N *>(n->_next); - } - N * - parent(RBNode *n) const - { - return static_cast<N *>(n->_parent); - } - N * - left(RBNode *n) const - { - return static_cast<N *>(n->_left); - } - N * - right(RBNode *n) const - { - return static_cast<N *>(n->_right); - } - N * - head() - { - return static_cast<N *>(_list.head()); - } - N * - tail() - { - return static_cast<N *>(_list.tail()); - } - - N *_root = nullptr; ///< 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. - struct NodeLinkage { - static RBNode *& - next_ptr(RBNode *n) - { - return n->_next; - } - static RBNode *& - prev_ptr(RBNode *n) - { - return n->_prev; - } - }; - using NodeList = ts::IntrusiveDList<NodeLinkage>; - /// 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 = nullptr; // 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>::clear() - { - // Delete everything. - N *n = static_cast<N *>(_list.head()); - while (n) { - N *x = n; - n = next(n); - delete x; - } - _list.clear(); - _root = nullptr; - return *this; - } - - template <typename N> - IpMapBase<N> & - IpMapBase<N>::fill(ArgType rmin, ArgType rmax, void *payload) - { - // Rightmost node of interest with n->_min <= min. - N *n = this->lowerBound(rmin); - N *x = nullptr; // New node (if any). - // Need copies because we will modify these. - Metric localmin = N::deref(rmin); - Metric localmax = N::deref(rmax); - - // Handle cases involving a node of interest to the left of the - // range. - if (n) { - if (n->_min < localmin) { - Metric min_1 = localmin; - N::dec(min_1); // dec is OK because min isn't zero. - if (n->_max < min_1) { // no overlap or adj. - n = next(n); - } else if (n->_max >= localmax) { // incoming range is covered, just discard. - return *this; - } else if (n->_data != payload) { // different payload, clip range on left. - localmin = n->_max; - N::inc(localmin); - n = next(n); - } else { // skew overlap with same payload, use node and continue. - x = n; - n = next(n); - } - } - } else { - n = this->head(); - } - - // Work through the rest of the nodes of interest. - // Invariant: n->_min >= min - - // Careful here -- because max_plus1 might wrap we need to use it only if we can be certain it - // didn't. This is done by ordering the range tests so that when max_plus1 is used when we know - // there exists a larger value than max. - Metric max_plus1 = localmax; - N::inc(max_plus1); - - /* Notes: - - max (and thence also max_plus1) never change during the loop. - - we must have either x != 0 or adjust min but not both for each loop iteration. - */ - while (n) { - if (n->_data == payload) { - if (x) { - if (n->_max <= localmax) { // next range is covered, so we can remove and continue. -#if defined(__clang_analyzer__) - x->_next = n->_next; // done in @c remove, but CA doesn't realize that. - // It's insufficient to assert(x->_next != n) after the remove. -#endif - this->remove(n); - n = next(x); - } else if (n->_min <= max_plus1) { - // Overlap or adjacent with larger max - absorb and finish. - x->setMax(n->_max); - this->remove(n); - return *this; - } else { - // have the space to finish off the range. - x->setMax(localmax); - return *this; - } - } else { // not carrying a span. - if (n->_max <= localmax) { // next range is covered - use it. - x = n; - x->setMin(localmin); - n = next(n); - } else if (n->_min <= max_plus1) { - n->setMin(localmin); - return *this; - } else { // no overlap, space to complete range. - this->insert_before(n, new N(localmin, localmax, payload)); - return *this; - } - } - } else { // different payload - if (x) { - if (localmax < n->_min) { // range ends before n starts, done. - x->setMax(localmax); - return *this; - } else if (localmax <= n->_max) { // range ends before n, done. - x->setMaxMinusOne(n->_min); - return *this; - } else { // n is contained in range, skip over it. - x->setMaxMinusOne(n->_min); - x = nullptr; - localmin = n->_max; - N::inc(localmin); // OK because n->_max maximal => next is null. - n = next(n); - } - } else { // no carry node. - if (localmax < n->_min) { // entirely before next span. - this->insert_before(n, new N(localmin, localmax, payload)); - return *this; - } else { - if (localmin < n->_min) { // leading section, need node. - N *y = new N(localmin, n->_min, payload); - y->decrementMax(); - this->insert_before(n, y); - } - if (localmax <= n->_max) { // nothing past node - return *this; - } - localmin = n->_max; - N::inc(localmin); - n = next(n); - } - } - } - } - // Invariant: min is larger than any existing range maximum. - if (x) { - x->setMax(localmax); - } else { - this->append(new N(localmin, localmax, payload)); - } - 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 = nullptr; // New node, gets set if we re-use an existing one. - N *y = nullptr; // Temporary for removing and advancing. - - // Several places it is handy to have max+1. Must be careful - // about wrapping. - Metric max_plus = N::deref(max); - N::inc(max_plus); - - /* Some subtlety - for IPv6 we overload the compare operators to do the right thing, but we - * can't overload pointer comparisons. Therefore we carefully never compare pointers in this - * logic. Only @a min and @a max can be pointers, everything else is an instance or a reference. - * Since there's no good reason to compare @a min and @a max this isn't particularly tricky, but - * it's good to keep in mind. If we were somewhat more clever, we would provide static less than - * and equal operators in the template class @a N and convert all the comparisons to use only - * those two via static function call. - */ - - /* We have lots of special cases here primarily to minimize memory - allocation by re-using an existing node as often as possible. - */ - if (n) { - // Watch for wrap. - 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. min_1 is OK because - // if there is a previous range, min is not zero. - N *p = prev(n); - if (p && p->_data == payload && p->_max == min_1) { - x = p; - n = x; // need to back up n because frame of reference moved. - 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 { - // request span is covered by existing span. - x = new N(min, max, payload); // - n->setMin(max_plus); // clip existing. - this->insert_before(n, x); - return *this; - } - } else if (n->_data == payload && n->_max >= min_1) { - // min_1 is safe here because n->_min < min so min is not zero. - 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 (nullptr != (y = next(n)) && y->_max <= max) { - // because @a n was selected as the minimum it must be the case that - // y->min >= min (or y would have been selected). Therefore in this - // case the request covers the next node therefore it can be reused. - x = y; - 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. - // max_plus is valid because n->_max > max. - N *r; - x = new N(min, max, payload); - r = new N(max_plus, n->_max, n->_data); - n->setMax(min_1); - this->insert_after(n, x); - this->insert_after(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->insert_before(n, x); - } else { - this->append(x); // note that since n == 0 we'll just return. - } - } - } else if (nullptr != (n = this->head()) && // at least one node in tree. - n->_data == payload && // payload matches - (n->_max <= max || n->_min <= max_plus) // overlap or adj. - ) { - // Same payload with overlap, re-use. - x = n; - n = next(n); - x->setMin(min); - if (x->_max < max) { - x->setMax(max); - } - } else { - x = new N(min, max, payload); - this->prepend(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) { // completely covered, drop span, continue - y = n; - n = next(n); - this->remove(y); - } else if (max_plus < n->_min) { // no overlap, done. - break; - } else if (n->_data == payload) { // skew overlap or adj., same payload - x->setMax(n->_max); - y = n; - n = next(n); - this->remove(y); - } else if (n->_min <= max) { // skew overlap different payload - 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 - if (n->_max > max) { - // request span is covered by existing span - split existing span. - x = new N(max, N::argue(n->_max), n->_data); - x->incrementMin(); - n->setMaxMinusOne(N::deref(min)); - this->insert_after(n, x); - return *this; // done. - } else { - n->setMaxMinusOne(N::deref(min)); // just clip overlap. - } - } // 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 - x->setMinPlusOne(N::deref(max)); - } - break; - } - } - return *this; - } - - template <typename N> - void - IpMapBase<N>::insert_after(N *spot, N *n) - { - N *c = right(spot); - if (!c) { - spot->setChild(n, N::RIGHT); - } else { - spot->_next->setChild(n, N::LEFT); - } - - _list.insert_after(spot, n); - _root = static_cast<N *>(n->rebalanceAfterInsert()); - } - - template <typename N> - void - IpMapBase<N>::insert_before(N *spot, N *n) - { - if (left(spot) == nullptr) { - spot->setChild(n, N::LEFT); - } else { -// If there's a left child, there's a previous node, therefore spot->_prev is valid. -// Clang analyzer doesn't realize this so it generates a false positive. -#if defined(__clang_analyzer__) - ink_assert(spot->_prev != nullptr); -#endif - spot->_prev->setChild(n, N::RIGHT); - } - - _list.insert_before(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.head()->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.tail()->setChild(n, N::RIGHT)->rebalanceAfterInsert()); - } - _list.append(n); - } - - template <typename N> - void - IpMapBase<N>::remove(N *n) - { - _root = static_cast<N *>(n->remove()); - _list.erase(n); - delete n; - } - - template <typename N> - bool - IpMapBase<N>::contains(ArgType x, void **ptr) const - { - 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> - size_t - IpMapBase<N>::count() const - { - return _list.count(); - } - //---------------------------------------------------------------------------- - template <typename N> - void - IpMapBase<N>::validate() - { -#if 0 - if (_root) _root->validate(); - for ( Node* n = _list.head() ; 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> - ts::BufferWriter & - IpMapBase<N>::describe(ts::BufferWriter &w, ts::BWFSpec const &spec) const - { - auto pos = w.extent(); - for (auto const &rb_node : _list) { - N const &n{static_cast<N const &>(rb_node)}; - if (w.extent() > pos) { - w.write(','); - } - w.print("{::a}-{::a}={}", n.min(), n.max(), n._data); - if (std::string_view::npos != spec._ext.find('x')) { - w.print("[{};^{};<{};>{}]", n._color == N::BLACK ? "Black" : "Red", n._parent, n._left, n._right); - } - } - return w; - } - - template <typename N> IpMapBase<N>::~IpMapBase() - { - this->clear(); - } - - //---------------------------------------------------------------------------- - using Ip4Span = Interval<in_addr_t, in_addr_t>; - - /** 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 struct IpMapBase<Ip4Node>; - - public: - using self_type = ts::detail::Ip4Node; ///< Self reference type. - - /// Construct with values. - Ip4Node(ArgType min, ///< Minimum address (host order). - ArgType max, ///< Maximum address (host order). - void *data ///< Client data. - ) - : Node(data), Ip4Span(min, max), _sa() - { - ats_ip4_set(ats_ip_sa_cast(&_sa._min), htonl(min)); - ats_ip4_set(ats_ip_sa_cast(&_sa._max), htonl(max)); - } - /// @return The minimum value of the interval. - sockaddr const * - min() const override - { - return ats_ip_sa_cast(&_sa._min); - } - /// @return The maximum value of the interval. - sockaddr const * - max() const override - { - return ats_ip_sa_cast(&_sa._max); - } - /// Set the client data. - self_type & - setData(void *data ///< Client data. - ) override - { - _data = data; - return *this; - } - - protected: - /// Set the minimum value of the interval. - /// @return This interval. - self_type & - 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_type & - setMax(ArgType max ///< Maximum value (host order). - ) - { - _max = max; - _sa._max.sin_addr.s_addr = htonl(max); - return *this; - } - - /** Set the maximum value to one less than @a max. - @return This object. - */ - self_type & - setMaxMinusOne(ArgType max ///< One more than maximum value. - ) - { - return this->setMax(max - 1); - } - /** Set the minimum value to one more than @a min. - @return This object. - */ - self_type & - setMinPlusOne(ArgType min ///< One less than minimum value. - ) - { - return this->setMin(min + 1); - } - /** decrement the maximum value in place. - @return This object. - */ - self_type & - decrementMax() - { - this->setMax(_max - 1); - return *this; - } - /** Increment the minimum value in place. - @return This object. - */ - self_type & - incrementMin() - { - this->setMin(_min + 1); - return *this; - } - - /// 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; - } - - /// @return The argument type for the @a metric. - static ArgType - argue(Metric const &metric) - { - return metric; - } - - struct { - sockaddr_in _min; - sockaddr_in _max; - } _sa; ///< Addresses in API compliant form. - }; - - class Ip4Map : public IpMapBase<Ip4Node> - { - friend class ::IpMap; - }; - - //---------------------------------------------------------------------------- - using Ip6Span = Interval<sockaddr_in6>; - - /** Node for IPv6 map. - */ - class Ip6Node : public IpMap::Node, protected Ip6Span - { - friend struct IpMapBase<Ip6Node>; - - public: - using self_type = ts::detail::Ip6Node; ///< Self reference type. - /// Override @c ArgType from @c Interval because the convention - /// is to use a pointer, not a reference. - using ArgType = const ts::detail::Interval<sockaddr_in6, const sockaddr_in6 &>::Metric *; - - /** Construct from the argument type. - * - * @param min Minimum value in the range. - * @param max Maximum value in the range (inclusive). - * @param data Data to attach to the range. - */ - - Ip6Node(ArgType min, ///< Minimum address (network order). - ArgType max, ///< Maximum address (network order). - void *data ///< Client data. - ) - : Node(data), Ip6Span(*min, *max) - { - } - - /** Construct from the underlying @c Metric type @a min to @a max - * - * @param min Minimum value in the range. - * @param max Maximum value in the range (inclusive). - * @param data Data to attach to the range. - */ - Ip6Node(Metric const &min, Metric const &max, void *data) : Node(data), Ip6Span(min, max) {} - - /// @return The minimum value of the interval. - sockaddr const * - min() const override - { - return ats_ip_sa_cast(&_min); - } - - /// @return The maximum value of the interval. - sockaddr const * - max() const override - { - return ats_ip_sa_cast(&_max); - } - - /** Set the client @a data. - * - * @param data Client data. - * @return @a this - */ - self_type & - setData(void *data) override - { - _data = data; - return *this; - } - - protected: - /// Set the minimum value of the interval. - /// @return This interval. - self_type & - setMin(ArgType min ///< Minimum value (host order). - ) - { - ats_ip_copy(ats_ip_sa_cast(&_min), ats_ip_sa_cast(min)); - return *this; - } - - /// Set the minimum value of the interval. - /// @note Convenience overload. - /// @return This interval. - self_type & - setMin(Metric const &min ///< Minimum value (host order). - ) - { - return this->setMin(&min); - } - - /// Set the maximum value of the interval. - /// @return This interval. - self_type & - setMax(ArgType max ///< Maximum value (host order). - ) - { - ats_ip_copy(ats_ip_sa_cast(&_max), ats_ip_sa_cast(max)); - return *this; - } - /// Set the maximum value of the interval. - /// @note Convenience overload. - /// @return This interval. - self_type & - setMax(Metric const &max ///< Maximum value (host order). - ) - { - return this->setMax(&max); - } - /** Set the maximum value to one less than @a max. - @return This object. - */ - self_type & - setMaxMinusOne(Metric const &max ///< One more than maximum value. - ) - { - this->setMax(max); - dec(_max); - return *this; - } - /** Set the minimum value to one more than @a min. - @return This object. - */ - self_type & - setMinPlusOne(Metric const &min ///< One less than minimum value. - ) - { - this->setMin(min); - inc(_min); - return *this; - } - /** Decrement the maximum value in place. - @return This object. - */ - self_type & - decrementMax() - { - dec(_max); - return *this; - } - /** Increment the minimum value in place. - @return This object. - */ - self_type & - incrementMin() - { - inc(_min); - return *this; - } - - /// Increment a metric. - static void - inc(Metric &m ///< Incremented in place. - ) - { - uint8_t *addr = m.sin6_addr.s6_addr; - uint8_t *b = addr + TS_IP6_SIZE; - // Ripple carry. Walk up the address incrementing until we don't - // have a carry. - do { - ++*--b; - } while (b > addr && 0 == *b); - } - - /// Decrement a metric. - static void - dec(Metric &m ///< Decremented in place. - ) - { - uint8_t *addr = m.sin6_addr.s6_addr; - uint8_t *b = addr + TS_IP6_SIZE; - // Ripple borrow. Walk up the address decrementing until we don't - // have a borrow. - 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; - } - - /// @return The argument type for the @a metric. - static ArgType - argue(Metric const &metric) - { - return &metric; - } - }; - - // We declare this after the helper operators and inside this namespace - // so that the template uses these for comparisons. - - class Ip6Map : public IpMapBase<Ip6Node> - { - friend class ::IpMap; - }; -} // namespace detail - -template <typename N> -inline BufferWriter & -bwformat(BufferWriter &w, BWFSpec const &spec, detail::IpMapBase<N> const &map) -{ - return map.describe(w, spec); -} - -} // namespace ts -//---------------------------------------------------------------------------- -IpMap::IpMap(IpMap::self_type &&that) noexcept : _m4(that._m4), _m6(that._m6) -{ - that._m4 = nullptr; - that._m6 = nullptr; -} - -IpMap::self_type & -IpMap::operator=(IpMap::self_type &&that) -{ - if (&that != this) { - this->clear(); - std::swap(_m4, that._m4); - std::swap(_m6, that._m6); - } - return *this; -} - -IpMap::~IpMap() -{ - delete _m4; - delete _m6; -} - -inline ts::detail::Ip4Map * -IpMap::force4() -{ - if (!_m4) { - _m4 = new ts::detail::Ip4Map; - } - return _m4; -} - -inline ts::detail::Ip6Map * -IpMap::force6() -{ - if (!_m6) { - _m6 = new ts::detail::Ip6Map; - } - return _m6; -} - -bool -IpMap::contains(sockaddr const *target, void **ptr) const -{ - bool zret = false; - if (AF_INET == target->sa_family) { - zret = _m4 && _m4->contains(ntohl(ats_ip4_addr_cast(target)), ptr); - } else if (AF_INET6 == target->sa_family) { - zret = _m6 && _m6->contains(ats_ip6_cast(target), ptr); - } - return zret; -} - -bool -IpMap::contains(in_addr_t target, void **ptr) const -{ - return _m4 && _m4->contains(ntohl(target), ptr); -} - -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(ntohl(ats_ip4_addr_cast(min)), ntohl(ats_ip4_addr_cast(max)), data); - } else if (AF_INET6 == min->sa_family) { - this->force6()->mark(ats_ip6_cast(min), ats_ip6_cast(max), data); - } - return *this; -} - -IpMap & -IpMap::mark(in_addr_t min, in_addr_t max, void *data) -{ - this->force4()->mark(ntohl(min), ntohl(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(ntohl(ats_ip4_addr_cast(min)), ntohl(ats_ip4_addr_cast(max))); - } - } else if (AF_INET6 == min->sa_family) { - if (_m6) { - _m6->unmark(ats_ip6_cast(min), ats_ip6_cast(max)); - } - } - return *this; -} - -IpMap & -IpMap::unmark(in_addr_t min, in_addr_t max) -{ - if (_m4) { - _m4->unmark(ntohl(min), ntohl(max)); - } - return *this; -} - -IpMap & -IpMap::fill(sockaddr const *min, sockaddr const *max, void *data) -{ - ink_assert(min->sa_family == max->sa_family); - if (AF_INET == min->sa_family) { - this->force4()->fill(ntohl(ats_ip4_addr_cast(min)), ntohl(ats_ip4_addr_cast(max)), data); - } else if (AF_INET6 == min->sa_family) { - this->force6()->fill(ats_ip6_cast(min), ats_ip6_cast(max), data); - } - return *this; -} - -IpMap & -IpMap::fill(in_addr_t min, in_addr_t max, void *data) -{ - this->force4()->fill(ntohl(min), ntohl(max), data); - return *this; -} - -size_t -IpMap::count() const -{ - size_t zret = 0; - if (_m4) { - zret += _m4->count(); - } - if (_m6) { - zret += _m6->count(); - } - return zret; -} - -IpMap & -IpMap::clear() -{ - if (_m4) { - _m4->clear(); - } - if (_m6) { - _m6->clear(); - } - return *this; -} - -IpMap::iterator -IpMap::begin() const -{ - Node *x = nullptr; - if (_m4) { - x = _m4->head(); - } - if (!x && _m6) { - x = _m6->head(); - } - 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->tail()) { - x = _tree->_m6->head(); - } - _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->head()) { - x = _tree->_m4->tail(); - } - _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->tail(); - } - if (!_node && _tree->_m4) { - _node = _tree->_m4->tail(); - } - } - return *this; -} - -ts::BufferWriter & -IpMap::describe(ts::BufferWriter &w, ts::BWFSpec const &spec) const -{ - w.write("IPv4 "); - if (_m4) { - bwformat(w, spec, *_m4); - } else { - w.write("N/A"); - } - w.write("\n"); - - w.write("IPv6 "); - if (_m6) { - bwformat(w, spec, *_m6); - } else { - w.write("N/A"); - } - w.write("\n"); - - return w; -} - -//---------------------------------------------------------------------------- -//---------------------------------------------------------------------------- diff --git a/src/tscore/Makefile.am b/src/tscore/Makefile.am index 4cd1fa6d2..cabd04301 100644 --- a/src/tscore/Makefile.am +++ b/src/tscore/Makefile.am @@ -104,7 +104,6 @@ libtscore_la_SOURCES = \ ink_thread.cc \ ink_time.cc \ ink_uuid.cc \ - IpMap.cc \ JeMiAllocator.cc \ Layout.cc \ llqueue.cc \ @@ -183,7 +182,6 @@ test_tscore_SOURCES = \ unit_tests/test_ink_memory.cc \ unit_tests/test_IntrusiveHashMap.cc \ unit_tests/test_IntrusivePtr.cc \ - unit_tests/test_IpMap.cc \ unit_tests/test_layout.cc \ unit_tests/test_List.cc \ unit_tests/test_MemArena.cc \ diff --git a/src/tscore/unit_tests/test_IpMap.cc b/src/tscore/unit_tests/test_IpMap.cc deleted file mode 100644 index 07debf88b..000000000 --- a/src/tscore/unit_tests/test_IpMap.cc +++ /dev/null @@ -1,633 +0,0 @@ -/** @file - - IpMap unit tests. - - @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. -*/ - -#include "tscore/IpMap.h" -#include <sstream> -#include <catch.hpp> -#include <tscore/BufferWriter.h> - -std::ostream & -operator<<(std::ostream &s, IpEndpoint const &addr) -{ - ip_text_buffer b; - ats_ip_ntop(addr, b, sizeof(b)); - s << b; - return s; -} - -void -IpMapTestPrint(IpMap &map) -{ - printf("IpMap Dump\n"); - for (auto &spot : map) { - ip_text_buffer ipb1, ipb2; - - printf("%s - %s : %p\n", ats_ip_ntop(spot.min(), ipb1, sizeof ipb1), ats_ip_ntop(spot.max(), ipb2, sizeof(ipb2)), spot.data()); - } - printf("\n"); -} - -// --- Test helper classes --- -class MapMarkedAt : public Catch::MatcherBase<IpMap> -{ - IpEndpoint const &_addr; - -public: - MapMarkedAt(IpEndpoint const &addr) : _addr(addr) {} - - bool - match(IpMap const &map) const override - { - return map.contains(&_addr); - } - - std::string - describe() const override - { - std::ostringstream ss; - ss << _addr << " is marked"; - return ss.str(); - } -}; - -// The builder function -inline MapMarkedAt -IsMarkedAt(IpEndpoint const &_addr) -{ - return {_addr}; -} - -class MapMarkedWith : public Catch::MatcherBase<IpMap> -{ - IpEndpoint const &_addr; - void *_mark; - mutable bool _found_p = false; - -public: - MapMarkedWith(IpEndpoint const &addr, void *mark) : _addr(addr), _mark(mark) {} - - bool - match(IpMap const &map) const override - { - void *mark = nullptr; - return (_found_p = map.contains(&_addr, &mark)) && mark == _mark; - } - - std::string - describe() const override - { - std::ostringstream ss; - if (_found_p) { - ss << "is marked at " << _addr << " with " << std::hex << reinterpret_cast<intptr_t>(_mark); - } else { - ss << "is not marked at " << _addr; - } - return ss.str(); - } -}; - -inline MapMarkedWith -IsMarkedWith(IpEndpoint const &addr, void *mark) -{ - return {addr, mark}; -} - -// ------------- -// --- TESTS --- -// ------------- -TEST_CASE("IpMap Basic", "[libts][ipmap]") -{ - IpMap map; - void *const markA = reinterpret_cast<void *>(1); - void *const markB = reinterpret_cast<void *>(2); - void *const markC = reinterpret_cast<void *>(3); - void *mark; // for retrieval - - in_addr_t ip5 = htonl(5), ip9 = htonl(9); - in_addr_t ip10 = htonl(10), ip15 = htonl(15), ip20 = htonl(20); - in_addr_t ip50 = htonl(50), ip60 = htonl(60); - in_addr_t ip100 = htonl(100), ip120 = htonl(120), ip140 = htonl(140); - in_addr_t ip150 = htonl(150), ip160 = htonl(160); - in_addr_t ip200 = htonl(200); - in_addr_t ip0 = 0; - in_addr_t ipmax = ~static_cast<in_addr_t>(0); - - map.mark(ip10, ip20, markA); - map.mark(ip5, ip9, markA); - { - INFO("Coalesce failed"); - CHECK(map.count() == 1); - } - { - INFO("Range max not found."); - CHECK(map.contains(ip9)); - } - { - INFO("Span min not found"); - CHECK(map.contains(ip10, &mark)); - } - { - INFO("Mark not preserved."); - CHECK(mark == markA); - } - - map.fill(ip15, ip100, markB); - { - INFO("Fill failed."); - CHECK(map.count() == 2); - } - { - INFO("fill interior missing"); - CHECK(map.contains(ip50, &mark)); - } - { - INFO("Fill mark not preserved."); - CHECK(mark == markB); - } - { - INFO("Span min not found."); - CHECK(!map.contains(ip200)); - } - { - INFO("Old span interior not found"); - CHECK(map.contains(ip15, &mark)); - } - { - INFO("Fill overwrote mark."); - CHECK(mark == markA); - } - - map.clear(); - { - INFO("Clear failed."); - CHECK(map.count() == 0); - } - - map.mark(ip20, ip50, markA); - map.mark(ip100, ip150, markB); - map.fill(ip10, ip200, markC); - CHECK(map.count() == 5); - { - INFO("Left span missing"); - CHECK(map.contains(ip15, &mark)); - } - { - INFO("Middle span missing"); - CHECK(map.contains(ip60, &mark)); - } - { - INFO("fill mark wrong."); - CHECK(mark == markC); - } - { - INFO("right span missing."); - CHECK(map.contains(ip160)); - } - { - INFO("right span missing"); - CHECK(map.contains(ip120, &mark)); - } - { - INFO("wrong data on right mark span."); - CHECK(mark == markB); - } - - map.unmark(ip140, ip160); - { - INFO("unmark failed"); - CHECK(map.count() == 5); - } - { - INFO("unmark left edge still there."); - CHECK(!map.contains(ip140)); - } - { - INFO("unmark middle still there."); - CHECK(!map.contains(ip150)); - } - { - INFO("unmark right edge still there."); - CHECK(!map.contains(ip160)); - } - - map.clear(); - map.mark(ip20, ip20, markA); - { - INFO("Map failed on singleton insert"); - CHECK(map.contains(ip20)); - } - map.mark(ip10, ip200, markB); - mark = 0; - map.contains(ip20, &mark); - { - INFO("Map held singleton against range."); - CHECK(mark == markB); - } - map.mark(ip100, ip120, markA); - map.mark(ip150, ip160, markB); - map.mark(ip0, ipmax, markC); - { - INFO("IpMap: Full range fill left extra ranges."); - CHECK(map.count() == 1); - } -} - -TEST_CASE("IpMap Unmark", "[libts][ipmap]") -{ - IpMap map; - // ip_text_buffer ipb1, ipb2; - void *const markA = reinterpret_cast<void *>(1); - - IpEndpoint a_0, a_0_0_0_16, a_0_0_0_17, a_max; - IpEndpoint a_10_28_56_0, a_10_28_56_4, a_10_28_56_255; - IpEndpoint a_10_28_55_255, a_10_28_57_0; - IpEndpoint a_63_128_1_12; - IpEndpoint a_loopback, a_loopback2; - IpEndpoint a6_0, a6_max, a6_fe80_9d90, a6_fe80_9d9d, a6_fe80_9d95; - - ats_ip_pton("0.0.0.0", &a_0); - ats_ip_pton("0.0.0.16", &a_0_0_0_16); - ats_ip_pton("0.0.0.17", &a_0_0_0_17); - ats_ip_pton("255.255.255.255", &a_max); - ats_ip_pton("10.28.55.255", &a_10_28_55_255); - ats_ip_pton("10.28.56.0", &a_10_28_56_0); - ats_ip_pton("10.28.56.4", &a_10_28_56_4); - ats_ip_pton("10.28.56.255", &a_10_28_56_255); - ats_ip_pton("10.28.57.0", &a_10_28_57_0); - ats_ip_pton("63.128.1.12", &a_63_128_1_12); - ats_ip_pton("::", &a6_0); - ats_ip_pton("ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff", &a6_max); - ats_ip_pton("fe80::221:9bff:fe10:9d90", &a6_fe80_9d90); - ats_ip_pton("fe80::221:9bff:fe10:9d9d", &a6_fe80_9d9d); - ats_ip_pton("fe80::221:9bff:fe10:9d95", &a6_fe80_9d95); - ats_ip_pton("127.0.0.1", &a_loopback); - ats_ip_pton("127.0.0.255", &a_loopback2); - - map.mark(&a_0, &a_max, markA); - { - INFO("IpMap Unmark: Full range not single."); - CHECK(map.count() == 1); - } - map.unmark(&a_10_28_56_0, &a_10_28_56_255); - { - INFO("IpMap Unmark: Range unmark failed."); - CHECK(map.count() == 2); - } - // Generic range check. - { - INFO("IpMap Unmark: Range unmark min address not removed."); - CHECK(!map.contains(&a_10_28_56_0)); - } - { - INFO("IpMap Unmark: Range unmark max address not removed."); - CHECK(!map.contains(&a_10_28_56_255)); - } - { - INFO("IpMap Unmark: Range unmark min-1 address removed."); - CHECK(map.contains(&a_10_28_55_255)); - } - { - INFO("IpMap Unmark: Range unmark max+1 address removed."); - CHECK(map.contains(&a_10_28_57_0)); - } - // Test min bounded range. - map.unmark(&a_0, &a_0_0_0_16); - { - INFO("IpMap Unmark: Range unmark zero address not removed."); - CHECK(!map.contains(&a_0)); - } - { - INFO("IpMap Unmark: Range unmark zero bounded range max not removed."); - CHECK(!map.contains(&a_0_0_0_16)); - } - { - INFO("IpMap Unmark: Range unmark zero bounded range max+1 removed."); - CHECK(map.contains(&a_0_0_0_17)); - } -} - -TEST_CASE("IpMap Fill", "[libts][ipmap]") -{ - IpMap map; - void *const allow = reinterpret_cast<void *>(0); - void *const deny = reinterpret_cast<void *>(~0); - void *const markA = reinterpret_cast<void *>(1); - void *const markB = reinterpret_cast<void *>(2); - void *const markC = reinterpret_cast<void *>(3); - - IpEndpoint a0, a_10_28_56_0, a_10_28_56_4, a_10_28_56_255, a3, a4; - IpEndpoint a_9_255_255_255, a_10_0_0_0, a_10_0_0_19, a_10_0_0_255, a_10_0_1_0; - IpEndpoint a_max, a_loopback, a_loopback2; - IpEndpoint a_10_28_55_255, a_10_28_57_0; - IpEndpoint a_63_128_1_12; - IpEndpoint a_0000_0000, a_0000_0001, a_ffff_ffff; - IpEndpoint a_fe80_9d8f, a_fe80_9d90, a_fe80_9d95, a_fe80_9d9d, a_fe80_9d9e; - - ats_ip_pton("0.0.0.0", &a0); - ats_ip_pton("255.255.255.255", &a_max); - - ats_ip_pton("9.255.255.255", &a_9_255_255_255); - ats_ip_pton("10.0.0.0", &a_10_0_0_0); - ats_ip_pton("10.0.0.19", &a_10_0_0_19); - ats_ip_pton("10.0.0.255", &a_10_0_0_255); - ats_ip_pton("10.0.1.0", &a_10_0_1_0); - - ats_ip_pton("10.28.55.255", &a_10_28_55_255); - ats_ip_pton("10.28.56.0", &a_10_28_56_0); - ats_ip_pton("10.28.56.4", &a_10_28_56_4); - ats_ip_pton("10.28.56.255", &a_10_28_56_255); - ats_ip_pton("10.28.57.0", &a_10_28_57_0); - - ats_ip_pton("192.168.1.0", &a3); - ats_ip_pton("192.168.1.255", &a4); - - ats_ip_pton("::", &a_0000_0000); - ats_ip_pton("::1", &a_0000_0001); - ats_ip_pton("ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff", &a_ffff_ffff); - ats_ip_pton("fe80::221:9bff:fe10:9d8f", &a_fe80_9d8f); - ats_ip_pton("fe80::221:9bff:fe10:9d90", &a_fe80_9d90); - ats_ip_pton("fe80::221:9bff:fe10:9d95", &a_fe80_9d95); - ats_ip_pton("fe80::221:9bff:fe10:9d9d", &a_fe80_9d9d); - ats_ip_pton("fe80::221:9bff:fe10:9d9e", &a_fe80_9d9e); - - ats_ip_pton("127.0.0.0", &a_loopback); - ats_ip_pton("127.0.0.255", &a_loopback2); - ats_ip_pton("63.128.1.12", &a_63_128_1_12); - - SECTION("subnet overfill") - { - map.fill(&a_10_28_56_0, &a_10_28_56_255, deny); - map.fill(&a0, &a_max, allow); - CHECK_THAT(map, IsMarkedWith(a_10_28_56_4, deny)); - } - - SECTION("singleton overfill") - { - map.fill(&a_loopback, &a_loopback, allow); - { - INFO("singleton not marked."); - CHECK_THAT(map, IsMarkedAt(a_loopback)); - } - map.fill(&a0, &a_max, deny); - THEN("singleton mark") - { - CHECK_THAT(map, IsMarkedWith(a_loopback, allow)); - THEN("not empty") - { - REQUIRE(map.begin() != map.end()); - IpMap::iterator spot = map.begin(); - ++spot; - THEN("more than one range") - { - REQUIRE(spot != map.end()); - THEN("ranges disjoint") - { - INFO(" " << map.begin()->max() << " < " << spot->min()); - REQUIRE(-1 == ats_ip_addr_cmp(map.begin()->max(), spot->min())); - } - } - } - } - } - - SECTION("3") - { - map.fill(&a_loopback, &a_loopback2, markA); - map.fill(&a_10_28_56_0, &a_10_28_56_255, markB); - { - INFO("over extended range"); - CHECK_THAT(map, !IsMarkedWith(a_63_128_1_12, markC)); - } - map.fill(&a0, &a_max, markC); - { - INFO("IpMap[2]: Fill failed."); - CHECK(map.count() == 5); - } - { - INFO("invalid mark in range gap"); - CHECK_THAT(map, IsMarkedWith(a_63_128_1_12, markC)); - } - } - - SECTION("4") - { - map.fill(&a_10_0_0_0, &a_10_0_0_255, allow); - map.fill(&a_loopback, &a_loopback2, allow); - { - INFO("invalid mark between ranges"); - CHECK_THAT(map, !IsMarkedAt(a_63_128_1_12)); - } - { - INFO("invalid mark in lower range"); - CHECK_THAT(map, IsMarkedWith(a_10_0_0_19, allow)); - } - map.fill(&a0, &a_max, deny); - { - INFO("range count incorrect"); - CHECK(map.count() == 5); - } - { - INFO("mark between ranges"); - CHECK_THAT(map, IsMarkedWith(a_63_128_1_12, deny)); - } - - map.fill(&a_fe80_9d90, &a_fe80_9d9d, markA); - map.fill(&a_0000_0001, &a_0000_0001, markA); - map.fill(&a_0000_0000, &a_ffff_ffff, markB); - - { - INFO("IpMap Fill[v6]: Zero address has bad mark."); - CHECK_THAT(map, IsMarkedWith(a_0000_0000, markB)); - } - { - INFO("IpMap Fill[v6]: Max address has bad mark."); - CHECK_THAT(map, IsMarkedWith(a_ffff_ffff, markB)); - } - { - INFO("IpMap Fill[v6]: 9d90 address has bad mark."); - CHECK_THAT(map, IsMarkedWith(a_fe80_9d90, markA)); - } - { - INFO("IpMap Fill[v6]: 9d8f address has bad mark."); - CHECK_THAT(map, IsMarkedWith(a_fe80_9d8f, markB)); - } - { - INFO("IpMap Fill[v6]: 9d9d address has bad mark."); - CHECK_THAT(map, IsMarkedWith(a_fe80_9d9d, markA)); - } - { - INFO("IpMap Fill[v6]: 9d9b address has bad mark."); - CHECK_THAT(map, IsMarkedWith(a_fe80_9d9e, markB)); - } - { - INFO("IpMap Fill[v6]: ::1 has bad mark."); - CHECK_THAT(map, IsMarkedWith(a_0000_0001, markA)); - } - - { - INFO("IpMap Fill[pre-refill]: Bad range count."); - CHECK(map.count() == 10); - } - // These should be ignored by the map as it is completely covered for IPv6. - map.fill(&a_fe80_9d90, &a_fe80_9d9d, markA); - map.fill(&a_0000_0001, &a_0000_0001, markC); - map.fill(&a_0000_0000, &a_ffff_ffff, markB); - { - INFO("IpMap Fill[post-refill]: Bad range count."); - CHECK(map.count() == 10); - } - } - - SECTION("5") - { - map.fill(&a_fe80_9d90, &a_fe80_9d9d, markA); - map.fill(&a_0000_0001, &a_0000_0001, markC); - map.fill(&a_0000_0000, &a_ffff_ffff, markB); - { - INFO("IpMap Fill[v6-2]: Zero address has bad mark."); - CHECK_THAT(map, IsMarkedWith(a_0000_0000, markB)); - } - { - INFO("IpMap Fill[v6-2]: Max address has bad mark."); - CHECK_THAT(map, IsMarkedWith(a_ffff_ffff, markB)); - } - { - INFO("IpMap Fill[v6-2]: 9d90 address has bad mark."); - CHECK_THAT(map, IsMarkedWith(a_fe80_9d90, markA)); - } - { - INFO("IpMap Fill[v6-2]: 9d8f address has bad mark."); - CHECK_THAT(map, IsMarkedWith(a_fe80_9d8f, markB)); - } - { - INFO("IpMap Fill[v6-2]: 9d9d address has bad mark."); - CHECK_THAT(map, IsMarkedWith(a_fe80_9d9d, markA)); - } - { - INFO("IpMap Fill[v6-2]: 9d9b address has bad mark."); - CHECK_THAT(map, IsMarkedWith(a_fe80_9d9e, markB)); - } - { - INFO("IpMap Fill[v6-2]: ::1 has bad mark."); - CHECK_THAT(map, IsMarkedWith(a_0000_0001, markC)); - } - } -} - -TEST_CASE("IpMap CloseIntersection", "[libts][ipmap]") -{ - IpMap map; - void *const markA = reinterpret_cast<void *>(1); - void *const markB = reinterpret_cast<void *>(2); - void *const markC = reinterpret_cast<void *>(3); - void *const markD = reinterpret_cast<void *>(4); - - IpEndpoint a_1_l, a_1_u, a_2_l, a_2_u, a_3_l, a_3_u, a_4_l, a_4_u, a_5_l, a_5_u, a_6_l, a_6_u, a_7_l, a_7_u; - IpEndpoint b_1_l, b_1_u; - IpEndpoint c_1_l, c_1_u, c_2_l, c_2_u, c_3_l, c_3_u; - IpEndpoint c_3_m; - IpEndpoint d_1_l, d_1_u, d_2_l, d_2_u; - - IpEndpoint a_1_m; - - ats_ip_pton("123.88.172.0", &a_1_l); - ats_ip_pton("123.88.180.93", &a_1_m); - ats_ip_pton("123.88.191.255", &a_1_u); - ats_ip_pton("123.89.132.0", &a_2_l); - ats_ip_pton("123.89.135.255", &a_2_u); - ats_ip_pton("123.89.160.0", &a_3_l); - ats_ip_pton("123.89.167.255", &a_3_u); - ats_ip_pton("123.90.108.0", &a_4_l); - ats_ip_pton("123.90.111.255", &a_4_u); - ats_ip_pton("123.90.152.0", &a_5_l); - ats_ip_pton("123.90.159.255", &a_5_u); - ats_ip_pton("123.91.0.0", &a_6_l); - ats_ip_pton("123.91.35.255", &a_6_u); - ats_ip_pton("123.91.40.0", &a_7_l); - ats_ip_pton("123.91.47.255", &a_7_u); - - ats_ip_pton("123.78.100.0", &b_1_l); - ats_ip_pton("123.78.115.255", &b_1_u); - - ats_ip_pton("123.88.204.0", &c_1_l); - ats_ip_pton("123.88.219.255", &c_1_u); - ats_ip_pton("123.90.112.0", &c_2_l); - ats_ip_pton("123.90.119.255", &c_2_u); - ats_ip_pton("123.90.132.0", &c_3_l); - ats_ip_pton("123.90.134.157", &c_3_m); - ats_ip_pton("123.90.135.255", &c_3_u); - - ats_ip_pton("123.82.196.0", &d_1_l); - ats_ip_pton("123.82.199.255", &d_1_u); - ats_ip_pton("123.82.204.0", &d_2_l); - ats_ip_pton("123.82.219.255", &d_2_u); - - map.mark(a_1_l, a_1_u, markA); - map.mark(a_2_l, a_2_u, markA); - map.mark(a_3_l, a_3_u, markA); - map.mark(a_4_l, a_4_u, markA); - map.mark(a_5_l, a_5_u, markA); - map.mark(a_6_l, a_6_u, markA); - map.mark(a_7_l, a_7_u, markA); - CHECK_THAT(map, IsMarkedAt(a_1_m)); - - map.mark(b_1_l, b_1_u, markB); - CHECK_THAT(map, IsMarkedWith(a_1_m, markA)); - - map.mark(c_1_l, c_1_u, markC); - map.mark(c_2_l, c_2_u, markC); - map.mark(c_3_l, c_3_u, markC); - CHECK_THAT(map, IsMarkedWith(a_1_m, markA)); - - map.mark(d_1_l, d_1_u, markD); - map.mark(d_2_l, d_2_u, markD); - CHECK_THAT(map, IsMarkedAt(a_1_m)); - CHECK_THAT(map, IsMarkedWith(b_1_u, markB)); - CHECK_THAT(map, IsMarkedWith(c_3_m, markC)); - CHECK_THAT(map, IsMarkedWith(d_2_l, markD)); - - CHECK(map.count() == 13); - - // Check move constructor. - IpMap m2{std::move(map)}; - // Original map should be empty. - REQUIRE(map.count() == 0); - // Do all these again on the destination map. - CHECK_THAT(m2, IsMarkedWith(a_1_m, markA)); - CHECK_THAT(m2, IsMarkedWith(a_1_m, markA)); - CHECK_THAT(m2, IsMarkedWith(a_1_m, markA)); - CHECK_THAT(m2, IsMarkedWith(a_1_m, markA)); - CHECK_THAT(m2, IsMarkedWith(b_1_u, markB)); - CHECK_THAT(m2, IsMarkedWith(c_3_m, markC)); - CHECK_THAT(m2, IsMarkedWith(d_2_l, markD)); - CHECK(m2.count() == 13); - -#if 0 - ts::LocalBufferWriter<1024> w; - std::cout << "Basic map dump" << std::endl; - std::cout << w.print("{}", m2).view() << std::endl; - w.reset(); - std::cout << "With tree detail" << std::endl; - std::cout << w.print("{::x}", m2).view() << std::endl; -#endif -};