2 * This file is part of PowerDNS or dnsdist.
3 * Copyright -- PowerDNS.COM B.V. and its contributors
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of version 2 of the GNU General Public License as
7 * published by the Free Software Foundation.
9 * In addition, for the avoidance of any doubt, permission is granted to
10 * link this program with OpenSSL and to (re)distribute the binaries
11 * produced as the result of such linking.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24 #include <sys/socket.h>
25 #include <netinet/in.h>
26 #include <arpa/inet.h>
31 #include "pdnsexception.hh"
33 #include <sys/socket.h>
36 #include <boost/tuple/tuple.hpp>
37 #include <boost/tuple/tuple_comparison.hpp>
39 #include "namespaces.hh"
42 #include <libkern/OSByteOrder.h>
44 #define htobe16(x) OSSwapHostToBigInt16(x)
45 #define htole16(x) OSSwapHostToLittleInt16(x)
46 #define be16toh(x) OSSwapBigToHostInt16(x)
47 #define le16toh(x) OSSwapLittleToHostInt16(x)
49 #define htobe32(x) OSSwapHostToBigInt32(x)
50 #define htole32(x) OSSwapHostToLittleInt32(x)
51 #define be32toh(x) OSSwapBigToHostInt32(x)
52 #define le32toh(x) OSSwapLittleToHostInt32(x)
54 #define htobe64(x) OSSwapHostToBigInt64(x)
55 #define htole64(x) OSSwapHostToLittleInt64(x)
56 #define be64toh(x) OSSwapBigToHostInt64(x)
57 #define le64toh(x) OSSwapLittleToHostInt64(x)
62 #define htobe16(x) BE_16(x)
63 #define htole16(x) LE_16(x)
64 #define be16toh(x) BE_IN16(&(x))
65 #define le16toh(x) LE_IN16(&(x))
67 #define htobe32(x) BE_32(x)
68 #define htole32(x) LE_32(x)
69 #define be32toh(x) BE_IN32(&(x))
70 #define le32toh(x) LE_IN32(&(x))
72 #define htobe64(x) BE_64(x)
73 #define htole64(x) LE_64(x)
74 #define be64toh(x) BE_IN64(&(x))
75 #define le64toh(x) LE_IN64(&(x))
80 #include <sys/endian.h>
83 #if defined(__NetBSD__) && defined(IP_PKTINFO) && !defined(IP_SENDSRCADDR)
84 // The IP_PKTINFO option in NetBSD was incompatible with Linux until a
85 // change that also introduced IP_SENDSRCADDR for FreeBSD compatibility.
90 struct sockaddr_in sin4;
91 struct sockaddr_in6 sin6;
93 bool operator==(const ComboAddress& rhs) const
95 if(boost::tie(sin4.sin_family, sin4.sin_port) != boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port))
97 if(sin4.sin_family == AF_INET)
98 return sin4.sin_addr.s_addr == rhs.sin4.sin_addr.s_addr;
100 return memcmp(&sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, sizeof(sin6.sin6_addr.s6_addr))==0;
103 bool operator!=(const ComboAddress& rhs) const
105 return(!operator==(rhs));
108 bool operator<(const ComboAddress& rhs) const
110 if(sin4.sin_family == 0) {
113 if(boost::tie(sin4.sin_family, sin4.sin_port) < boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port))
115 if(boost::tie(sin4.sin_family, sin4.sin_port) > boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port))
118 if(sin4.sin_family == AF_INET)
119 return sin4.sin_addr.s_addr < rhs.sin4.sin_addr.s_addr;
121 return memcmp(&sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, sizeof(sin6.sin6_addr.s6_addr)) < 0;
124 bool operator>(const ComboAddress& rhs) const
126 return rhs.operator<(*this);
129 struct addressOnlyHash
131 uint32_t operator()(const ComboAddress& ca) const
133 const unsigned char* start;
135 if(ca.sin4.sin_family == AF_INET) {
136 start =(const unsigned char*)&ca.sin4.sin_addr.s_addr;
140 start =(const unsigned char*)&ca.sin6.sin6_addr.s6_addr;
143 return burtle(start, len, 0);
147 struct addressOnlyLessThan: public std::binary_function<ComboAddress, ComboAddress, bool>
149 bool operator()(const ComboAddress& a, const ComboAddress& b) const
151 if(a.sin4.sin_family < b.sin4.sin_family)
153 if(a.sin4.sin_family > b.sin4.sin_family)
155 if(a.sin4.sin_family == AF_INET)
156 return a.sin4.sin_addr.s_addr < b.sin4.sin_addr.s_addr;
158 return memcmp(&a.sin6.sin6_addr.s6_addr, &b.sin6.sin6_addr.s6_addr, sizeof(a.sin6.sin6_addr.s6_addr)) < 0;
162 struct addressOnlyEqual: public std::binary_function<ComboAddress, ComboAddress, bool>
164 bool operator()(const ComboAddress& a, const ComboAddress& b) const
166 if(a.sin4.sin_family != b.sin4.sin_family)
168 if(a.sin4.sin_family == AF_INET)
169 return a.sin4.sin_addr.s_addr == b.sin4.sin_addr.s_addr;
171 return !memcmp(&a.sin6.sin6_addr.s6_addr, &b.sin6.sin6_addr.s6_addr, sizeof(a.sin6.sin6_addr.s6_addr));
176 socklen_t getSocklen() const
178 if(sin4.sin_family == AF_INET)
186 sin4.sin_family=AF_INET;
187 sin4.sin_addr.s_addr=0;
189 sin6.sin6_scope_id = 0;
190 sin6.sin6_flowinfo = 0;
193 ComboAddress(const struct sockaddr *sa, socklen_t salen) {
194 setSockaddr(sa, salen);
197 ComboAddress(const struct sockaddr_in6 *sa) {
198 setSockaddr((const struct sockaddr*)sa, sizeof(struct sockaddr_in6));
201 ComboAddress(const struct sockaddr_in *sa) {
202 setSockaddr((const struct sockaddr*)sa, sizeof(struct sockaddr_in));
205 void setSockaddr(const struct sockaddr *sa, socklen_t salen) {
206 if (salen > sizeof(struct sockaddr_in6)) throw PDNSException("ComboAddress can't handle other than sockaddr_in or sockaddr_in6");
207 memcpy(this, sa, salen);
210 // 'port' sets a default value in case 'str' does not set a port
211 explicit ComboAddress(const string& str, uint16_t port=0)
213 memset(&sin6, 0, sizeof(sin6));
214 sin4.sin_family = AF_INET;
216 if(makeIPv4sockaddr(str, &sin4)) {
217 sin6.sin6_family = AF_INET6;
218 if(makeIPv6sockaddr(str, &sin6) < 0)
219 throw PDNSException("Unable to convert presentation address '"+ str +"'");
222 if(!sin4.sin_port) // 'str' overrides port!
223 sin4.sin_port=htons(port);
228 return sin4.sin_family == AF_INET6;
232 return sin4.sin_family == AF_INET;
235 bool isMappedIPv4() const
237 if(sin4.sin_family!=AF_INET6)
241 const unsigned char*ptr = (unsigned char*) &sin6.sin6_addr.s6_addr;
242 for(n=0; n < 10; ++n)
253 ComboAddress mapToIPv4() const
256 throw PDNSException("ComboAddress can't map non-mapped IPv6 address back to IPv4");
258 ret.sin4.sin_family=AF_INET;
259 ret.sin4.sin_port=sin4.sin_port;
261 const unsigned char*ptr = (unsigned char*) &sin6.sin6_addr.s6_addr;
262 ptr+=(sizeof(sin6.sin6_addr.s6_addr) - sizeof(ret.sin4.sin_addr.s_addr));
263 memcpy(&ret.sin4.sin_addr.s_addr, ptr, sizeof(ret.sin4.sin_addr.s_addr));
267 string toString() const
271 if(sin4.sin_family && !(retval = getnameinfo((struct sockaddr*) this, getSocklen(), host, sizeof(host),0, 0, NI_NUMERICHOST)))
274 return "invalid "+string(gai_strerror(retval));
277 string toStringWithPort() const
279 if(sin4.sin_family==AF_INET)
280 return toString() + ":" + std::to_string(ntohs(sin4.sin_port));
282 return "["+toString() + "]:" + std::to_string(ntohs(sin4.sin_port));
285 string toStringWithPortExcept(int port) const
287 if(ntohs(sin4.sin_port) == port)
289 if(sin4.sin_family==AF_INET)
290 return toString() + ":" + std::to_string(ntohs(sin4.sin_port));
292 return "["+toString() + "]:" + std::to_string(ntohs(sin4.sin_port));
295 string toLogString() const
297 return toStringWithPortExcept(53);
300 void truncate(unsigned int bits) noexcept;
302 uint16_t getPort() const
304 return ntohs(sin4.sin_port);
307 void setPort(uint16_t port)
309 sin4.sin_port = htons(port);
314 memset(&sin4, 0, sizeof(sin4));
315 memset(&sin6, 0, sizeof(sin6));
318 //! Get the total number of address bits (either 32 or 128 depending on IP version)
319 uint8_t getBits() const
327 /** Get the value of the bit at the provided bit index. When the index >= 0,
328 the index is relative to the LSB starting at index zero. When the index < 0,
329 the index is relative to the MSB starting at index -1 and counting down.
331 bool getBit(int index) const
342 uint32_t s_addr = ntohl(sin4.sin_addr.s_addr);
344 return ((s_addr & (1<<index)) != 0x00000000);
355 uint8_t *s_addr = (uint8_t*)sin6.sin6_addr.s6_addr;
356 uint8_t byte_idx = index / 8;
357 uint8_t bit_idx = index % 8;
359 return ((s_addr[15-byte_idx] & (1 << bit_idx)) != 0x00);
365 /** This exception is thrown by the Netmask class and by extension by the NetmaskGroup class */
366 class NetmaskException: public PDNSException
369 NetmaskException(const string &a) : PDNSException(a) {}
372 inline ComboAddress makeComboAddress(const string& str)
374 ComboAddress address;
375 address.sin4.sin_family=AF_INET;
376 if(inet_pton(AF_INET, str.c_str(), &address.sin4.sin_addr) <= 0) {
377 address.sin4.sin_family=AF_INET6;
378 if(makeIPv6sockaddr(str, &address.sin6) < 0)
379 throw NetmaskException("Unable to convert '"+str+"' to a netmask");
384 inline ComboAddress makeComboAddressFromRaw(uint8_t version, const char* raw, size_t len)
386 ComboAddress address;
389 address.sin4.sin_family = AF_INET;
390 if (len != sizeof(address.sin4.sin_addr)) throw NetmaskException("invalid raw address length");
391 memcpy(&address.sin4.sin_addr, raw, sizeof(address.sin4.sin_addr));
393 else if (version == 6) {
394 address.sin6.sin6_family = AF_INET6;
395 if (len != sizeof(address.sin6.sin6_addr)) throw NetmaskException("invalid raw address length");
396 memcpy(&address.sin6.sin6_addr, raw, sizeof(address.sin6.sin6_addr));
398 else throw NetmaskException("invalid address family");
403 inline ComboAddress makeComboAddressFromRaw(uint8_t version, const string &str)
405 return makeComboAddressFromRaw(version, str.c_str(), str.size());
408 /** This class represents a netmask and can be queried to see if a certain
409 IP address is matched by this mask */
415 d_network.sin4.sin_family = 0; // disable this doing anything useful
416 d_network.sin4.sin_port = 0; // this guarantees d_network compares identical
421 Netmask(const ComboAddress& network, uint8_t bits=0xff): d_network(network)
423 d_network.sin4.sin_port = 0;
424 setBits(network.isIPv4() ? std::min(bits, static_cast<uint8_t>(32)) : std::min(bits, static_cast<uint8_t>(128)));
427 void setBits(uint8_t value)
432 d_mask = ~(0xFFFFFFFF >> d_bits);
435 // note that d_mask is unused for IPv6
440 d_network.sin4.sin_addr.s_addr = htonl(ntohl(d_network.sin4.sin_addr.s_addr) & d_mask);
443 uint8_t bytes = d_bits/8;
444 uint8_t *us = (uint8_t*) &d_network.sin6.sin6_addr.s6_addr;
445 uint8_t bits = d_bits % 8;
446 uint8_t mask = (uint8_t) ~(0xFF>>bits);
448 if (bytes < sizeof(d_network.sin6.sin6_addr.s6_addr)) {
452 for(size_t idx = bytes + 1; idx < sizeof(d_network.sin6.sin6_addr.s6_addr); ++idx) {
458 //! Constructor supplies the mask, which cannot be changed
459 Netmask(const string &mask)
461 pair<string,string> split = splitField(mask,'/');
462 d_network = makeComboAddress(split.first);
464 if (!split.second.empty()) {
465 setBits(static_cast<uint8_t>(pdns_stou(split.second)));
467 else if (d_network.sin4.sin_family == AF_INET) {
475 bool match(const ComboAddress& ip) const
480 //! If this IP address in socket address matches
481 bool match(const ComboAddress *ip) const
483 if(d_network.sin4.sin_family != ip->sin4.sin_family) {
486 if(d_network.sin4.sin_family == AF_INET) {
487 return match4(htonl((unsigned int)ip->sin4.sin_addr.s_addr));
489 if(d_network.sin6.sin6_family == AF_INET6) {
490 uint8_t bytes=d_bits/8, n;
491 const uint8_t *us=(const uint8_t*) &d_network.sin6.sin6_addr.s6_addr;
492 const uint8_t *them=(const uint8_t*) &ip->sin6.sin6_addr.s6_addr;
494 for(n=0; n < bytes; ++n) {
499 // still here, now match remaining bits
500 uint8_t bits= d_bits % 8;
501 uint8_t mask= (uint8_t) ~(0xFF>>bits);
503 return((us[n]) == (them[n] & mask));
508 //! If this ASCII IP address matches
509 bool match(const string &ip) const
511 ComboAddress address=makeComboAddress(ip);
512 return match(&address);
515 //! If this IP address in native format matches
516 bool match4(uint32_t ip) const
518 return (ip & d_mask) == (ntohl(d_network.sin4.sin_addr.s_addr));
521 string toString() const
523 return d_network.toString()+"/"+std::to_string((unsigned int)d_bits);
526 string toStringNoMask() const
528 return d_network.toString();
531 const ComboAddress& getNetwork() const
536 const ComboAddress& getMaskedNetwork() const
541 uint8_t getBits() const
548 return d_network.sin6.sin6_family == AF_INET6;
553 return d_network.sin4.sin_family == AF_INET;
556 bool operator<(const Netmask& rhs) const
558 if (empty() && !rhs.empty())
561 if (!empty() && rhs.empty())
564 if (d_bits > rhs.d_bits)
566 if (d_bits < rhs.d_bits)
569 return d_network < rhs.d_network;
572 bool operator>(const Netmask& rhs) const
574 return rhs.operator<(*this);
577 bool operator==(const Netmask& rhs) const
579 return tie(d_network, d_bits) == tie(rhs.d_network, rhs.d_bits);
584 return d_network.sin4.sin_family==0;
587 //! Get normalized version of the netmask. This means that all address bits below the network bits are zero.
588 Netmask getNormalized() const {
589 return Netmask(getMaskedNetwork(), d_bits);
591 //! Get Netmask for super network of this one (i.e. with fewer network bits)
592 Netmask getSuper(uint8_t bits) const {
593 return Netmask(d_network, std::min(d_bits, bits));
596 //! Get the total number of address bits for this netmask (either 32 or 128 depending on IP version)
597 uint8_t getAddressBits() const
599 return d_network.getBits();
602 /** Get the value of the bit at the provided bit index. When the index >= 0,
603 the index is relative to the LSB starting at index zero. When the index < 0,
604 the index is relative to the MSB starting at index -1 and counting down.
605 When the index points outside the network bits, it always yields zero.
607 bool getBit(int bit) const
613 if (bit >= 32 || bit < (32 - d_bits))
617 if (bit >= 128 || bit < (128 - d_bits))
621 return d_network.getBit(bit);
624 ComboAddress d_network;
629 /** Binary tree map implementation with <Netmask,T> pair.
631 * This is an binary tree implementation for storing attributes for IPv4 and IPv6 prefixes.
632 * The most simple use case is simple NetmaskTree<bool> used by NetmaskGroup, which only
633 * wants to know if given IP address is matched in the prefixes stored.
635 * This element is useful for anything that needs to *STORE* prefixes, and *MATCH* IP addresses
636 * to a *LIST* of *PREFIXES*. Not the other way round.
638 * You can store IPv4 and IPv6 addresses to same tree, separate payload storage is kept per AFI.
639 * Network prefixes (Netmasks) are always recorded in normalized fashion, meaning that only
640 * the network bits are set. This is what is returned in the insert() and lookup() return
643 * Use swap if you need to move the tree to another NetmaskTree instance, it is WAY faster
644 * than using copy ctor or assignment operator, since it moves the nodes and tree root to
645 * new home instead of actually recreating the tree.
647 * Please see NetmaskGroup for example of simple use case. Other usecases can be found
648 * from GeoIPBackend and Sortlist, and from dnsdist.
650 template <typename T>
655 typedef Netmask key_type;
656 typedef T value_type;
657 typedef std::pair<const key_type,value_type> node_type;
658 typedef size_t size_type;
659 typedef class Iterator iterator;
662 /** Single node in tree, internal use only.
664 class TreeNode : boost::noncopyable {
666 explicit TreeNode() noexcept :
667 parent(nullptr), node(), assigned(false), d_bits(0) {
669 explicit TreeNode(const key_type& key) noexcept :
670 parent(nullptr), node({key.getNormalized(), value_type()}),
671 assigned(false), d_bits(key.getAddressBits()) {
674 //<! Makes a left leaf node with specified key.
675 TreeNode* make_left(const key_type& key) {
676 d_bits = node.first.getBits();
677 left = make_unique<TreeNode>(key);
682 //<! Makes a right leaf node with specified key.
683 TreeNode* make_right(const key_type& key) {
684 d_bits = node.first.getBits();
685 right = make_unique<TreeNode>(key);
686 right->parent = this;
690 //<! Splits branch at indicated bit position by inserting key
691 TreeNode* split(const key_type& key, int bits) {
692 if (parent == nullptr) {
693 // not to be called on the root node
694 throw std::logic_error(
695 "NetmaskTree::TreeNode::split(): must not be called on root node");
698 // determine reference from parent
699 unique_ptr<TreeNode>& parent_ref =
700 (parent->left.get() == this ? parent->left : parent->right);
701 if (parent_ref.get() != this) {
702 throw std::logic_error(
703 "NetmaskTree::TreeNode::split(): parent node reference is invalid");
706 // create new tree node for the new key
707 TreeNode* new_node = new TreeNode(key);
708 new_node->d_bits = bits;
710 // attach the new node under our former parent
711 unique_ptr<TreeNode> new_child(new_node);
712 std::swap(parent_ref, new_child); // hereafter new_child points to "this"
713 new_node->parent = parent;
715 // attach "this" node below the new node
716 // (left or right depending on bit)
717 new_child->parent = new_node;
718 if (new_child->node.first.getBit(-1-bits)) {
719 std::swap(new_node->right, new_child);
721 std::swap(new_node->left, new_child);
727 //<! Forks branch for new key at indicated bit position
728 TreeNode* fork(const key_type& key, int bits) {
729 if (parent == nullptr) {
730 // not to be called on the root node
731 throw std::logic_error(
732 "NetmaskTree::TreeNode::fork(): must not be called on root node");
735 // determine reference from parent
736 unique_ptr<TreeNode>& parent_ref =
737 (parent->left.get() == this ? parent->left : parent->right);
738 if (parent_ref.get() != this) {
739 throw std::logic_error(
740 "NetmaskTree::TreeNode::fork(): parent node reference is invalid");
743 // create new tree node for the branch point
744 TreeNode* branch_node = new TreeNode(node.first.getSuper(bits));
745 branch_node->d_bits = bits;
747 // attach the branch node under our former parent
748 unique_ptr<TreeNode> new_child1(branch_node);
749 std::swap(parent_ref, new_child1); // hereafter new_child1 points to "this"
750 branch_node->parent = parent;
752 // create second new leaf node for the new key
753 TreeNode* new_node = new TreeNode(key);
754 unique_ptr<TreeNode> new_child2(new_node);
756 // attach the new child nodes below the branch node
757 // (left or right depending on bit)
758 new_child1->parent = branch_node;
759 new_child2->parent = branch_node;
760 if (new_child1->node.first.getBit(-1-bits)) {
761 std::swap(branch_node->right, new_child1);
762 std::swap(branch_node->left, new_child2);
764 std::swap(branch_node->right, new_child2);
765 std::swap(branch_node->left, new_child1);
771 //<! Traverse left branch depth-first
772 TreeNode *traverse_l()
774 TreeNode *tnode = this;
777 tnode = tnode->left.get();
781 //<! Traverse tree depth-first and in-order (L-N-R)
782 TreeNode *traverse_lnr()
784 TreeNode *tnode = this;
786 // precondition: descended left as deep as possible
789 tnode = tnode->right.get();
790 // descend left as deep as possible and return next node
791 return tnode->traverse_l();
795 while (tnode->parent != nullptr) {
796 TreeNode *prev_child = tnode;
797 tnode = tnode->parent;
799 // return this node, but only when we come from the left child branch
800 if (tnode->left && tnode->left.get() == prev_child)
806 //<! Traverse only assigned nodes
807 TreeNode *traverse_lnr_assigned()
809 TreeNode *tnode = traverse_lnr();
811 while (tnode != nullptr && !tnode->assigned)
812 tnode = tnode->traverse_lnr();
816 unique_ptr<TreeNode> left;
817 unique_ptr<TreeNode> right;
821 bool assigned; //<! Whether this node is assigned-to by the application
823 int d_bits; //<! How many bits have been used so far
826 void cleanup_tree(TreeNode* node)
828 // only cleanup this node if it has no children and node not assigned
829 if (!(node->left || node->right || node->assigned)) {
830 // get parent node ptr
831 TreeNode* pparent = node->parent;
834 if (pparent->left.get() == node)
835 pparent->left.reset();
837 pparent->right.reset();
838 // now recurse up to the parent
839 cleanup_tree(pparent);
844 void copyTree(const NetmaskTree& rhs)
848 node = rhs.d_root.get();
850 node = node->traverse_l();
851 while (node != nullptr) {
853 insert(node->node.first).second = node->node.second;
854 node = node->traverse_lnr();
861 typedef node_type value_type;
862 typedef node_type& reference;
863 typedef node_type* pointer;
864 typedef std::forward_iterator_tag iterator_category;
865 typedef size_type difference_type;
868 friend class NetmaskTree;
870 const NetmaskTree* d_tree;
873 Iterator(const NetmaskTree* tree, TreeNode* node): d_tree(tree), d_node(node) {
877 Iterator(): d_tree(nullptr), d_node(nullptr) {}
879 Iterator& operator++() // prefix
881 if (d_node == nullptr) {
882 throw std::logic_error(
883 "NetmaskTree::Iterator::operator++: iterator is invalid");
885 d_node = d_node->traverse_lnr_assigned();
888 Iterator operator++(int) // postfix
895 reference operator*()
897 if (d_node == nullptr) {
898 throw std::logic_error(
899 "NetmaskTree::Iterator::operator*: iterator is invalid");
906 if (d_node == nullptr) {
907 throw std::logic_error(
908 "NetmaskTree::Iterator::operator->: iterator is invalid");
910 return &d_node->node;
913 bool operator==(const Iterator& rhs)
915 return (d_tree == rhs.d_tree && d_node == rhs.d_node);
917 bool operator!=(const Iterator& rhs)
919 return !(*this == rhs);
924 NetmaskTree() noexcept: d_root(new TreeNode()), d_left(nullptr), d_size(0) {
927 NetmaskTree(const NetmaskTree& rhs): d_root(new TreeNode()), d_left(nullptr), d_size(0) {
931 NetmaskTree& operator=(const NetmaskTree& rhs) {
937 const iterator begin() const {
938 return Iterator(this, d_left);
940 const iterator end() const {
941 return Iterator(this, nullptr);
944 return Iterator(this, d_left);
947 return Iterator(this, nullptr);
950 node_type& insert(const string &mask) {
951 return insert(key_type(mask));
954 //<! Creates new value-pair in tree and returns it.
955 node_type& insert(const key_type& key) {
959 // we turn left on IPv4 and right on IPv6
961 node = d_root->left.get();
962 if (node == nullptr) {
963 node = new TreeNode(key);
964 node->assigned = true;
965 node->parent = d_root.get();
967 d_root->left = unique_ptr<TreeNode>(node);
972 } else if (key.isIPv6()) {
973 node = d_root->right.get();
974 if (node == nullptr) {
975 node = new TreeNode(key);
976 node->assigned = true;
977 node->parent = d_root.get();
979 d_root->right = unique_ptr<TreeNode>(node);
988 throw NetmaskException("invalid address family");
990 // we turn left on 0 and right on 1
992 for(; bits < key.getBits(); bits++) {
993 bool vall = key.getBit(-1-bits);
995 if (bits >= node->d_bits) {
996 // the end of the current node is reached; continue with the next
998 if (node->left || node->assigned)
1001 // the right branch doesn't exist yet; attach our key here
1002 node = node->make_right(key);
1005 node = node->right.get();
1008 // the left branch doesn't exist yet; attach our key here
1009 node = node->make_left(key);
1012 node = node->left.get();
1016 if (bits >= node->node.first.getBits()) {
1017 // the matching branch ends here, yet the key netmask has more bits; add a
1018 // child node below the existing branch leaf.
1022 node = node->make_right(key);
1024 node = node->make_left(key);
1028 bool valr = node->node.first.getBit(-1-bits);
1032 // the branch matches just upto this point, yet continues in a different
1033 // direction; fork the branch.
1034 node = node->fork(key, bits);
1039 if (node->node.first.getBits() > key.getBits()) {
1040 // key is a super-network of the matching node; split the branch and
1041 // insert a node for the key above the matching node.
1042 node = node->split(key, key.getBits());
1048 node_type& value = node->node;
1050 if (!node->assigned) {
1051 // only increment size if not assigned before
1053 // update the pointer to the left-most tree node
1056 node->assigned = true;
1058 // tree node exists for this value
1059 if (is_left && d_left != node) {
1060 throw std::logic_error(
1061 "NetmaskTree::insert(): lost track of left-most node in tree");
1068 //<! Creates or updates value
1069 void insert_or_assign(const key_type& mask, const value_type& value) {
1070 insert(mask).second = value;
1073 void insert_or_assign(const string& mask, const value_type& value) {
1074 insert(key_type(mask)).second = value;
1077 //<! check if given key is present in TreeMap
1078 bool has_key(const key_type& key) const {
1079 const node_type *ptr = lookup(key);
1080 return ptr && ptr->first == key;
1083 //<! Returns "best match" for key_type, which might not be value
1084 const node_type* lookup(const key_type& value) const {
1085 return lookup(value.getNetwork(), value.getBits());
1088 //<! Perform best match lookup for value, using at most max_bits
1089 const node_type* lookup(const ComboAddress& value, int max_bits = 128) const {
1090 TreeNode *node = nullptr;
1092 uint8_t addr_bits = value.getBits();
1093 if (max_bits < 0 || max_bits > addr_bits)
1094 max_bits = addr_bits;
1097 node = d_root->left.get();
1098 else if (value.isIPv6())
1099 node = d_root->right.get();
1101 throw NetmaskException("invalid address family");
1102 if (node == nullptr) return nullptr;
1104 node_type *ret = nullptr;
1107 for(; bits < max_bits; bits++) {
1108 bool vall = value.getBit(-1-bits);
1109 if (bits >= node->d_bits) {
1110 // the end of the current node is reached; continue with the next
1111 // (we keep track of last assigned node)
1112 if (node->assigned && bits == node->node.first.getBits())
1117 node = node->right.get();
1121 node = node->left.get();
1125 if (bits >= node->node.first.getBits()) {
1126 // the matching branch ends here
1129 bool valr = node->node.first.getBit(-1-bits);
1131 // the branch matches just upto this point, yet continues in a different
1136 // needed if we did not find one in loop
1137 if (node->assigned && bits == node->node.first.getBits())
1140 // this can be nullptr.
1144 //<! Removes key from TreeMap.
1145 void erase(const key_type& key) {
1146 TreeNode *node = nullptr;
1149 node = d_root->left.get();
1150 else if (key.isIPv6())
1151 node = d_root->right.get();
1153 throw NetmaskException("invalid address family");
1154 // no tree, no value
1155 if (node == nullptr) return;
1158 for(; node && bits < key.getBits(); bits++) {
1159 bool vall = key.getBit(-1-bits);
1160 if (bits >= node->d_bits) {
1161 // the end of the current node is reached; continue with the next
1163 node = node->right.get();
1165 node = node->left.get();
1169 if (bits >= node->node.first.getBits()) {
1170 // the matching branch ends here
1171 if (key.getBits() != node->node.first.getBits())
1175 bool valr = node->node.first.getBit(-1-bits);
1177 // the branch matches just upto this point, yet continues in a different
1185 throw std::logic_error(
1186 "NetmaskTree::erase(): size of tree is zero before erase");
1189 node->assigned = false;
1190 node->node.second = value_type();
1193 d_left = d_left->traverse_lnr_assigned();
1199 void erase(const string& key) {
1200 erase(key_type(key));
1203 //<! checks whether the container is empty.
1204 bool empty() const {
1205 return (d_size == 0);
1208 //<! returns the number of elements
1209 size_type size() const {
1213 //<! See if given ComboAddress matches any prefix
1214 bool match(const ComboAddress& value) const {
1215 return (lookup(value) != nullptr);
1218 bool match(const std::string& value) const {
1219 return match(ComboAddress(value));
1222 //<! Clean out the tree
1224 d_root.reset(new TreeNode());
1229 //<! swaps the contents with another NetmaskTree
1230 void swap(NetmaskTree& rhs) {
1231 std::swap(d_root, rhs.d_root);
1232 std::swap(d_left, rhs.d_left);
1233 std::swap(d_size, rhs.d_size);
1237 unique_ptr<TreeNode> d_root; //<! Root of our tree
1242 /** This class represents a group of supplemental Netmask classes. An IP address matchs
1243 if it is matched by zero or more of the Netmask classes within.
1248 NetmaskGroup() noexcept {
1251 //! If this IP address is matched by any of the classes within
1253 bool match(const ComboAddress *ip) const
1255 const auto &ret = tree.lookup(*ip);
1256 if(ret) return ret->second;
1260 bool match(const ComboAddress& ip) const
1265 bool lookup(const ComboAddress* ip, Netmask* nmp) const
1267 const auto &ret = tree.lookup(*ip);
1277 bool lookup(const ComboAddress& ip, Netmask* nmp) const
1279 return lookup(&ip, nmp);
1282 //! Add this string to the list of possible matches
1283 void addMask(const string &ip, bool positive=true)
1285 if(!ip.empty() && ip[0] == '!') {
1286 addMask(Netmask(ip.substr(1)), false);
1288 addMask(Netmask(ip), positive);
1292 //! Add this Netmask to the list of possible matches
1293 void addMask(const Netmask& nm, bool positive=true)
1295 tree.insert(nm).second=positive;
1298 //! Delete this Netmask from the list of possible matches
1299 void deleteMask(const Netmask& nm)
1304 void deleteMask(const std::string& ip)
1307 deleteMask(Netmask(ip));
1317 return tree.empty();
1325 string toString() const
1328 for(auto iter = tree.begin(); iter != tree.end(); ++iter) {
1329 if(iter != tree.begin())
1333 str<<iter->first.toString();
1338 void toStringVector(vector<string>* vec) const
1340 for(auto iter = tree.begin(); iter != tree.end(); ++iter) {
1341 vec->push_back((iter->second ? "" : "!") + iter->first.toString());
1345 void toMasks(const string &ips)
1347 vector<string> parts;
1348 stringtok(parts, ips, ", \t");
1350 for (vector<string>::const_iterator iter = parts.begin(); iter != parts.end(); ++iter)
1355 NetmaskTree<bool> tree;
1358 struct SComboAddress
1360 SComboAddress(const ComboAddress& orig) : ca(orig) {}
1362 bool operator<(const SComboAddress& rhs) const
1364 return ComboAddress::addressOnlyLessThan()(ca, rhs.ca);
1366 operator const ComboAddress&()
1372 class NetworkError : public runtime_error
1375 NetworkError(const string& why="Network Error") : runtime_error(why.c_str())
1377 NetworkError(const char *why="Network Error") : runtime_error(why)
1381 int SSocket(int family, int type, int flags);
1382 int SConnect(int sockfd, const ComboAddress& remote);
1383 /* tries to connect to remote for a maximum of timeout seconds.
1384 sockfd should be set to non-blocking beforehand.
1385 returns 0 on success (the socket is writable), throw a
1386 runtime_error otherwise */
1387 int SConnectWithTimeout(int sockfd, const ComboAddress& remote, int timeout);
1388 int SBind(int sockfd, const ComboAddress& local);
1389 int SAccept(int sockfd, ComboAddress& remote);
1390 int SListen(int sockfd, int limit);
1391 int SSetsockopt(int sockfd, int level, int opname, int value);
1392 void setSocketIgnorePMTU(int sockfd);
1394 #if defined(IP_PKTINFO)
1395 #define GEN_IP_PKTINFO IP_PKTINFO
1396 #elif defined(IP_RECVDSTADDR)
1397 #define GEN_IP_PKTINFO IP_RECVDSTADDR
1400 bool IsAnyAddress(const ComboAddress& addr);
1401 bool HarvestDestinationAddress(const struct msghdr* msgh, ComboAddress* destination);
1402 bool HarvestTimestamp(struct msghdr* msgh, struct timeval* tv);
1403 void fillMSGHdr(struct msghdr* msgh, struct iovec* iov, cmsgbuf_aligned* cbuf, size_t cbufsize, char* data, size_t datalen, ComboAddress* addr);
1404 ssize_t sendfromto(int sock, const char* data, size_t len, int flags, const ComboAddress& from, const ComboAddress& to);
1405 size_t sendMsgWithOptions(int fd, const char* buffer, size_t len, const ComboAddress* dest, const ComboAddress* local, unsigned int localItf, int flags);
1407 /* requires a non-blocking, connected TCP socket */
1408 bool isTCPSocketUsable(int sock);
1410 extern template class NetmaskTree<bool>;