pdns/iputils.hh

   1 /*
   2  * This file is part of PowerDNS or dnsdist.
   3  * Copyright -- PowerDNS.COM B.V. and its contributors
   4  *
   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.
   8  *
   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.
  12  *
  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.
  17  *
  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.
  21  */
  22 #ifndef PDNS_IPUTILSHH
  23 #define PDNS_IPUTILSHH
  24
  25 #include <string>
  26 #include <sys/socket.h>
  27 #include <netinet/in.h>
  28 #include <arpa/inet.h>
  29 #include <iostream>
  30 #include <stdio.h>
  31 #include <functional>
  32 #include <bitset>
  33 #include "pdnsexception.hh"
  34 #include "misc.hh"
  35 #include <sys/socket.h>
  36 #include <netdb.h>
  37 #include <sstream>
  38 #include <boost/tuple/tuple.hpp>
  39 #include <boost/tuple/tuple_comparison.hpp>
  40
  41 #include "namespaces.hh"
  42
  43 #ifdef __APPLE__
  44 #include <libkern/OSByteOrder.h>
  45
  46 #define htobe16(x) OSSwapHostToBigInt16(x)
  47 #define htole16(x) OSSwapHostToLittleInt16(x)
  48 #define be16toh(x) OSSwapBigToHostInt16(x)
  49 #define le16toh(x) OSSwapLittleToHostInt16(x)
  50
  51 #define htobe32(x) OSSwapHostToBigInt32(x)
  52 #define htole32(x) OSSwapHostToLittleInt32(x)
  53 #define be32toh(x) OSSwapBigToHostInt32(x)
  54 #define le32toh(x) OSSwapLittleToHostInt32(x)
  55
  56 #define htobe64(x) OSSwapHostToBigInt64(x)
  57 #define htole64(x) OSSwapHostToLittleInt64(x)
  58 #define be64toh(x) OSSwapBigToHostInt64(x)
  59 #define le64toh(x) OSSwapLittleToHostInt64(x)
  60 #endif
  61
  62 #ifdef __sun
  63
  64 #define htobe16(x) BE_16(x)
  65 #define htole16(x) LE_16(x)
  66 #define be16toh(x) BE_IN16(&(x))
  67 #define le16toh(x) LE_IN16(&(x))
  68
  69 #define htobe32(x) BE_32(x)
  70 #define htole32(x) LE_32(x)
  71 #define be32toh(x) BE_IN32(&(x))
  72 #define le32toh(x) LE_IN32(&(x))
  73
  74 #define htobe64(x) BE_64(x)
  75 #define htole64(x) LE_64(x)
  76 #define be64toh(x) BE_IN64(&(x))
  77 #define le64toh(x) LE_IN64(&(x))
  78
  79 #endif
  80
  81 #ifdef __FreeBSD__
  82 #include <sys/endian.h>
  83 #endif
  84
  85 #if defined(__NetBSD__) && defined(IP_PKTINFO) && !defined(IP_SENDSRCADDR)
  86 // The IP_PKTINFO option in NetBSD was incompatible with Linux until a
  87 // change that also introduced IP_SENDSRCADDR for FreeBSD compatibility.
  88 #undef IP_PKTINFO
  89 #endif
  90
  91 union ComboAddress {
  92   struct sockaddr_in sin4;
  93   struct sockaddr_in6 sin6;
  94
  95   bool operator==(const ComboAddress& rhs) const
  96   {
  97     if(boost::tie(sin4.sin_family, sin4.sin_port) != boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port))
  98       return false;
  99     if(sin4.sin_family == AF_INET)
 100       return sin4.sin_addr.s_addr == rhs.sin4.sin_addr.s_addr;
 101     else
 102       return memcmp(&sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, sizeof(sin6.sin6_addr.s6_addr))==0;
 103   }
 104
 105   bool operator!=(const ComboAddress& rhs) const
 106   {
 107     return(!operator==(rhs));
 108   }
 109
 110   bool operator<(const ComboAddress& rhs) const
 111   {
 112     if(sin4.sin_family == 0) {
 113       return false;
 114     }
 115     if(boost::tie(sin4.sin_family, sin4.sin_port) < boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port))
 116       return true;
 117     if(boost::tie(sin4.sin_family, sin4.sin_port) > boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port))
 118       return false;
 119
 120     if(sin4.sin_family == AF_INET)
 121       return sin4.sin_addr.s_addr < rhs.sin4.sin_addr.s_addr;
 122     else
 123       return memcmp(&sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, sizeof(sin6.sin6_addr.s6_addr)) < 0;
 124   }
 125
 126   bool operator>(const ComboAddress& rhs) const
 127   {
 128     return rhs.operator<(*this);
 129   }
 130
 131   struct addressOnlyHash
 132   {
 133     uint32_t operator()(const ComboAddress& ca) const
 134     {
 135       const unsigned char* start;
 136       int len;
 137       if(ca.sin4.sin_family == AF_INET) {
 138         start =(const unsigned char*)&ca.sin4.sin_addr.s_addr;
 139         len=4;
 140       }
 141       else {
 142         start =(const unsigned char*)&ca.sin6.sin6_addr.s6_addr;
 143         len=16;
 144       }
 145       return burtle(start, len, 0);
 146     }
 147   };
 148
 149   struct addressOnlyLessThan: public std::binary_function<ComboAddress, ComboAddress, bool>
 150   {
 151     bool operator()(const ComboAddress& a, const ComboAddress& b) const
 152     {
 153       if(a.sin4.sin_family < b.sin4.sin_family)
 154         return true;
 155       if(a.sin4.sin_family > b.sin4.sin_family)
 156         return false;
 157       if(a.sin4.sin_family == AF_INET)
 158         return a.sin4.sin_addr.s_addr < b.sin4.sin_addr.s_addr;
 159       else
 160         return memcmp(&a.sin6.sin6_addr.s6_addr, &b.sin6.sin6_addr.s6_addr, sizeof(a.sin6.sin6_addr.s6_addr)) < 0;
 161     }
 162   };
 163
 164   struct addressOnlyEqual: public std::binary_function<ComboAddress, ComboAddress, bool>
 165   {
 166     bool operator()(const ComboAddress& a, const ComboAddress& b) const
 167     {
 168       if(a.sin4.sin_family != b.sin4.sin_family)
 169         return false;
 170       if(a.sin4.sin_family == AF_INET)
 171         return a.sin4.sin_addr.s_addr == b.sin4.sin_addr.s_addr;
 172       else
 173         return !memcmp(&a.sin6.sin6_addr.s6_addr, &b.sin6.sin6_addr.s6_addr, sizeof(a.sin6.sin6_addr.s6_addr));
 174     }
 175   };
 176
 177
 178   socklen_t getSocklen() const
 179   {
 180     if(sin4.sin_family == AF_INET)
 181       return sizeof(sin4);
 182     else
 183       return sizeof(sin6);
 184   }
 185
 186   ComboAddress()
 187   {
 188     sin4.sin_family=AF_INET;
 189     sin4.sin_addr.s_addr=0;
 190     sin4.sin_port=0;
 191     sin6.sin6_scope_id = 0;
 192     sin6.sin6_flowinfo = 0;
 193   }
 194
 195   ComboAddress(const struct sockaddr *sa, socklen_t salen) {
 196     setSockaddr(sa, salen);
 197   };
 198
 199   ComboAddress(const struct sockaddr_in6 *sa) {
 200     setSockaddr((const struct sockaddr*)sa, sizeof(struct sockaddr_in6));
 201   };
 202
 203   ComboAddress(const struct sockaddr_in *sa) {
 204     setSockaddr((const struct sockaddr*)sa, sizeof(struct sockaddr_in));
 205   };
 206
 207   void setSockaddr(const struct sockaddr *sa, socklen_t salen) {
 208     if (salen > sizeof(struct sockaddr_in6)) throw PDNSException("ComboAddress can't handle other than sockaddr_in or sockaddr_in6");
 209     memcpy(this, sa, salen);
 210   }
 211
 212   // 'port' sets a default value in case 'str' does not set a port
 213   explicit ComboAddress(const string& str, uint16_t port=0)
 214   {
 215     memset(&sin6, 0, sizeof(sin6));
 216     sin4.sin_family = AF_INET;
 217     sin4.sin_port = 0;
 218     if(makeIPv4sockaddr(str, &sin4)) {
 219       sin6.sin6_family = AF_INET6;
 220       if(makeIPv6sockaddr(str, &sin6) < 0)
 221         throw PDNSException("Unable to convert presentation address '"+ str +"'");
 222
 223     }
 224     if(!sin4.sin_port) // 'str' overrides port!
 225       sin4.sin_port=htons(port);
 226   }
 227
 228   bool isIPv6() const
 229   {
 230     return sin4.sin_family == AF_INET6;
 231   }
 232   bool isIPv4() const
 233   {
 234     return sin4.sin_family == AF_INET;
 235   }
 236
 237   bool isMappedIPv4()  const
 238   {
 239     if(sin4.sin_family!=AF_INET6)
 240       return false;
 241
 242     int n=0;
 243     const unsigned char*ptr = (unsigned char*) &sin6.sin6_addr.s6_addr;
 244     for(n=0; n < 10; ++n)
 245       if(ptr[n])
 246         return false;
 247
 248     for(; n < 12; ++n)
 249       if(ptr[n]!=0xff)
 250         return false;
 251
 252     return true;
 253   }
 254
 255   ComboAddress mapToIPv4() const
 256   {
 257     if(!isMappedIPv4())
 258       throw PDNSException("ComboAddress can't map non-mapped IPv6 address back to IPv4");
 259     ComboAddress ret;
 260     ret.sin4.sin_family=AF_INET;
 261     ret.sin4.sin_port=sin4.sin_port;
 262
 263     const unsigned char*ptr = (unsigned char*) &sin6.sin6_addr.s6_addr;
 264     ptr+=(sizeof(sin6.sin6_addr.s6_addr) - sizeof(ret.sin4.sin_addr.s_addr));
 265     memcpy(&ret.sin4.sin_addr.s_addr, ptr, sizeof(ret.sin4.sin_addr.s_addr));
 266     return ret;
 267   }
 268
 269   string toString() const
 270   {
 271     char host[1024];
 272     int retval = 0;
 273     if(sin4.sin_family && !(retval = getnameinfo((struct sockaddr*) this, getSocklen(), host, sizeof(host),0, 0, NI_NUMERICHOST)))
 274       return host;
 275     else
 276       return "invalid "+string(gai_strerror(retval));
 277   }
 278
 279   string toStringWithPort() const
 280   {
 281     if(sin4.sin_family==AF_INET)
 282       return toString() + ":" + std::to_string(ntohs(sin4.sin_port));
 283     else
 284       return "["+toString() + "]:" + std::to_string(ntohs(sin4.sin_port));
 285   }
 286
 287   string toStringWithPortExcept(int port) const
 288   {
 289     if(ntohs(sin4.sin_port) == port)
 290       return toString();
 291     if(sin4.sin_family==AF_INET)
 292       return toString() + ":" + std::to_string(ntohs(sin4.sin_port));
 293     else
 294       return "["+toString() + "]:" + std::to_string(ntohs(sin4.sin_port));
 295   }
 296
 297   string toLogString() const
 298   {
 299     return toStringWithPortExcept(53);
 300   }
 301
 302   void truncate(unsigned int bits) noexcept;
 303
 304   uint16_t getPort() const
 305   {
 306     return ntohs(sin4.sin_port);
 307   }
 308
 309   ComboAddress setPort(uint16_t port) const
 310   {
 311     ComboAddress ret(*this);
 312     ret.sin4.sin_port=htons(port);
 313     return ret;
 314   }
 315
 316   void reset()
 317   {
 318     memset(&sin4, 0, sizeof(sin4));
 319     memset(&sin6, 0, sizeof(sin6));
 320   }
 321
 322 };
 323
 324 /** This exception is thrown by the Netmask class and by extension by the NetmaskGroup class */
 325 class NetmaskException: public PDNSException
 326 {
 327 public:
 328   NetmaskException(const string &a) : PDNSException(a) {}
 329 };
 330
 331 inline ComboAddress makeComboAddress(const string& str)
 332 {
 333   ComboAddress address;
 334   address.sin4.sin_family=AF_INET;
 335   if(inet_pton(AF_INET, str.c_str(), &address.sin4.sin_addr) <= 0) {
 336     address.sin4.sin_family=AF_INET6;
 337     if(makeIPv6sockaddr(str, &address.sin6) < 0)
 338       throw NetmaskException("Unable to convert '"+str+"' to a netmask");
 339   }
 340   return address;
 341 }
 342
 343 inline ComboAddress makeComboAddressFromRaw(uint8_t version, const char* raw, size_t len)
 344 {
 345   ComboAddress address;
 346
 347   if (version == 4) {
 348     address.sin4.sin_family = AF_INET;
 349     if (len != sizeof(address.sin4.sin_addr)) throw NetmaskException("invalid raw address length");
 350     memcpy(&address.sin4.sin_addr, raw, sizeof(address.sin4.sin_addr));
 351   }
 352   else if (version == 6) {
 353     address.sin6.sin6_family = AF_INET6;
 354     if (len != sizeof(address.sin6.sin6_addr)) throw NetmaskException("invalid raw address length");
 355     memcpy(&address.sin6.sin6_addr, raw, sizeof(address.sin6.sin6_addr));
 356   }
 357   else throw NetmaskException("invalid address family");
 358
 359   return address;
 360 }
 361
 362 inline ComboAddress makeComboAddressFromRaw(uint8_t version, const string &str)
 363 {
 364   return makeComboAddressFromRaw(version, str.c_str(), str.size());
 365 }
 366
 367 /** This class represents a netmask and can be queried to see if a certain
 368     IP address is matched by this mask */
 369 class Netmask
 370 {
 371 public:
 372   Netmask()
 373   {
 374         d_network.sin4.sin_family=0; // disable this doing anything useful
 375         d_network.sin4.sin_port = 0; // this guarantees d_network compares identical
 376         d_mask=0;
 377         d_bits=0;
 378   }
 379
 380   Netmask(const ComboAddress& network, uint8_t bits=0xff): d_network(network)
 381   {
 382     d_network.sin4.sin_port=0;
 383     if(bits > 128)
 384       bits = (network.sin4.sin_family == AF_INET) ? 32 : 128;
 385
 386     d_bits = bits;
 387     if(d_bits<32)
 388       d_mask=~(0xFFFFFFFF>>d_bits);
 389     else
 390       d_mask=0xFFFFFFFF; // not actually used for IPv6
 391   }
 392
 393   //! Constructor supplies the mask, which cannot be changed
 394   Netmask(const string &mask)
 395   {
 396     pair<string,string> split=splitField(mask,'/');
 397     d_network=makeComboAddress(split.first);
 398
 399     if(!split.second.empty()) {
 400       d_bits = (uint8_t)pdns_stou(split.second);
 401       if(d_bits<32)
 402         d_mask=~(0xFFFFFFFF>>d_bits);
 403       else
 404         d_mask=0xFFFFFFFF;
 405     }
 406     else if(d_network.sin4.sin_family==AF_INET) {
 407       d_bits = 32;
 408       d_mask = 0xFFFFFFFF;
 409     }
 410     else {
 411       d_bits=128;
 412       d_mask=0;  // silence silly warning - d_mask is unused for IPv6
 413     }
 414   }
 415
 416   bool match(const ComboAddress& ip) const
 417   {
 418     return match(&ip);
 419   }
 420
 421   //! If this IP address in socket address matches
 422   bool match(const ComboAddress *ip) const
 423   {
 424     if(d_network.sin4.sin_family != ip->sin4.sin_family) {
 425       return false;
 426     }
 427     if(d_network.sin4.sin_family == AF_INET) {
 428       return match4(htonl((unsigned int)ip->sin4.sin_addr.s_addr));
 429     }
 430     if(d_network.sin6.sin6_family == AF_INET6) {
 431       uint8_t bytes=d_bits/8, n;
 432       const uint8_t *us=(const uint8_t*) &d_network.sin6.sin6_addr.s6_addr;
 433       const uint8_t *them=(const uint8_t*) &ip->sin6.sin6_addr.s6_addr;
 434
 435       for(n=0; n < bytes; ++n) {
 436         if(us[n]!=them[n]) {
 437           return false;
 438         }
 439       }
 440       // still here, now match remaining bits
 441       uint8_t bits= d_bits % 8;
 442       uint8_t mask= (uint8_t) ~(0xFF>>bits);
 443
 444       return((us[n] & mask) == (them[n] & mask));
 445     }
 446     return false;
 447   }
 448
 449   //! If this ASCII IP address matches
 450   bool match(const string &ip) const
 451   {
 452     ComboAddress address=makeComboAddress(ip);
 453     return match(&address);
 454   }
 455
 456   //! If this IP address in native format matches
 457   bool match4(uint32_t ip) const
 458   {
 459     return (ip & d_mask) == (ntohl(d_network.sin4.sin_addr.s_addr) & d_mask);
 460   }
 461
 462   string toString() const
 463   {
 464     return d_network.toString()+"/"+std::to_string((unsigned int)d_bits);
 465   }
 466
 467   string toStringNoMask() const
 468   {
 469     return d_network.toString();
 470   }
 471   const ComboAddress& getNetwork() const
 472   {
 473     return d_network;
 474   }
 475   const ComboAddress getMaskedNetwork() const
 476   {
 477     ComboAddress result(d_network);
 478     if(isIpv4()) {
 479       result.sin4.sin_addr.s_addr = htonl(ntohl(result.sin4.sin_addr.s_addr) & d_mask);
 480     }
 481     else if(isIpv6()) {
 482       size_t idx;
 483       uint8_t bytes=d_bits/8;
 484       uint8_t *us=(uint8_t*) &result.sin6.sin6_addr.s6_addr;
 485       uint8_t bits= d_bits % 8;
 486       uint8_t mask= (uint8_t) ~(0xFF>>bits);
 487
 488       if (bytes < sizeof(result.sin6.sin6_addr.s6_addr)) {
 489         us[bytes] &= mask;
 490       }
 491
 492       for(idx = bytes + 1; idx < sizeof(result.sin6.sin6_addr.s6_addr); ++idx) {
 493         us[idx] = 0;
 494       }
 495     }
 496     return result;
 497   }
 498   uint8_t getBits() const
 499   {
 500     return d_bits;
 501   }
 502   bool isIpv6() const
 503   {
 504     return d_network.sin6.sin6_family == AF_INET6;
 505   }
 506   bool isIpv4() const
 507   {
 508     return d_network.sin4.sin_family == AF_INET;
 509   }
 510
 511   bool operator<(const Netmask& rhs) const
 512   {
 513     if (empty() && !rhs.empty())
 514       return false;
 515
 516     if (!empty() && rhs.empty())
 517       return true;
 518
 519     if (d_bits > rhs.d_bits)
 520       return true;
 521     if (d_bits < rhs.d_bits)
 522       return false;
 523
 524     return d_network < rhs.d_network;
 525   }
 526
 527   bool operator>(const Netmask& rhs) const
 528   {
 529     return rhs.operator<(*this);
 530   }
 531
 532   bool operator==(const Netmask& rhs) const
 533   {
 534     return tie(d_network, d_bits) == tie(rhs.d_network, rhs.d_bits);
 535   }
 536
 537   bool empty() const
 538   {
 539     return d_network.sin4.sin_family==0;
 540   }
 541
 542 private:
 543   ComboAddress d_network;
 544   uint32_t d_mask;
 545   uint8_t d_bits;
 546 };
 547
 548 /** Per-bit binary tree map implementation with <Netmask,T> pair.
 549  *
 550  * This is an binary tree implementation for storing attributes for IPv4 and IPv6 prefixes.
 551  * The most simple use case is simple NetmaskTree<bool> used by NetmaskGroup, which only
 552  * wants to know if given IP address is matched in the prefixes stored.
 553  *
 554  * This element is useful for anything that needs to *STORE* prefixes, and *MATCH* IP addresses
 555  * to a *LIST* of *PREFIXES*. Not the other way round.
 556  *
 557  * You can store IPv4 and IPv6 addresses to same tree, separate payload storage is kept per AFI.
 558  *
 559  * To erase something copy values to new tree sans the value you want to erase.
 560  *
 561  * Use swap if you need to move the tree to another NetmaskTree instance, it is WAY faster
 562  * than using copy ctor or assignment operator, since it moves the nodes and tree root to
 563  * new home instead of actually recreating the tree.
 564  *
 565  * Please see NetmaskGroup for example of simple use case. Other usecases can be found
 566  * from GeoIPBackend and Sortlist, and from dnsdist.
 567  */
 568 template <typename T>
 569 class NetmaskTree {
 570 public:
 571   typedef Netmask key_type;
 572   typedef T value_type;
 573   typedef std::pair<key_type,value_type> node_type;
 574   typedef size_t size_type;
 575
 576 private:
 577   /** Single node in tree, internal use only.
 578     */
 579   class TreeNode : boost::noncopyable {
 580   public:
 581      explicit TreeNode(int bits) noexcept : parent(NULL),d_bits(bits) {
 582      }
 583
 584      //<! Makes a left node with one more bit than parent
 585      TreeNode* make_left() {
 586        if (!left) {
 587          left = unique_ptr<TreeNode>(new TreeNode(d_bits+1));
 588          left->parent = this;
 589        }
 590        return left.get();
 591      }
 592
 593      //<! Makes a right node with one more bit than parent
 594      TreeNode* make_right() {
 595        if (!right) {
 596          right = unique_ptr<TreeNode>(new TreeNode(d_bits+1));
 597          right->parent = this;
 598        }
 599        return right.get();
 600      }
 601
 602      unique_ptr<TreeNode> left;
 603      unique_ptr<TreeNode> right;
 604      TreeNode* parent;
 605
 606      unique_ptr<node_type> node4; //<! IPv4 value-pair
 607      unique_ptr<node_type> node6; //<! IPv6 value-pair
 608
 609      int d_bits; //<! How many bits have been used so far
 610   };
 611
 612 public:
 613   NetmaskTree() noexcept : NetmaskTree(false) {
 614   }
 615
 616   NetmaskTree(bool cleanup) noexcept : d_cleanup_tree(cleanup) {
 617   }
 618
 619   NetmaskTree(const NetmaskTree& rhs): d_cleanup_tree(rhs.d_cleanup_tree) {
 620     // it is easier to copy the nodes than tree.
 621     // also acts as handy compactor
 622     for(auto const& node: rhs._nodes)
 623       insert(node->first).second = node->second;
 624   }
 625
 626   NetmaskTree& operator=(const NetmaskTree& rhs) {
 627     clear();
 628     // see above.
 629     for(auto const& node: rhs._nodes)
 630       insert(node->first).second = node->second;
 631     d_cleanup_tree = rhs.d_cleanup_tree;
 632     return *this;
 633   }
 634
 635   const typename std::set<node_type*>::const_iterator begin() const { return _nodes.begin(); }
 636   const typename std::set<node_type*>::const_iterator end() const { return _nodes.end(); }
 637
 638   typename std::set<node_type*>::iterator begin() { return _nodes.begin(); }
 639   typename std::set<node_type*>::iterator end() { return _nodes.end(); }
 640
 641   node_type& insert(const string &mask) {
 642     return insert(key_type(mask));
 643   }
 644
 645   //<! Creates new value-pair in tree and returns it.
 646   node_type& insert(const key_type& key) {
 647     // lazily initialize tree on first insert.
 648     if (!root) root = unique_ptr<TreeNode>(new TreeNode(0));
 649     TreeNode* node = root.get();
 650     node_type* value = nullptr;
 651
 652     if (key.getNetwork().sin4.sin_family == AF_INET) {
 653       std::bitset<32> addr(be32toh(key.getNetwork().sin4.sin_addr.s_addr));
 654       int bits = 0;
 655       // we turn left on 0 and right on 1
 656       while(bits < key.getBits()) {
 657         uint8_t val = addr[31-bits];
 658         if (val)
 659           node = node->make_right();
 660         else
 661           node = node->make_left();
 662         bits++;
 663       }
 664       // only create node if not yet assigned
 665       if (!node->node4) {
 666         node->node4 = unique_ptr<node_type>(new node_type());
 667         _nodes.insert(node->node4.get());
 668       }
 669       value = node->node4.get();
 670     } else {
 671       uint64_t* addr = (uint64_t*)key.getNetwork().sin6.sin6_addr.s6_addr;
 672       std::bitset<64> addr_low(be64toh(addr[1]));
 673       std::bitset<64> addr_high(be64toh(addr[0]));
 674       int bits = 0;
 675       while(bits < key.getBits()) {
 676         uint8_t val;
 677         // we use high address until we are
 678         if (bits < 64) val = addr_high[63-bits];
 679         // past 64 bits, and start using low address
 680         else val = addr_low[127-bits];
 681
 682         // we turn left on 0 and right on 1
 683         if (val)
 684           node = node->make_right();
 685         else
 686           node = node->make_left();
 687         bits++;
 688       }
 689       // only create node if not yet assigned
 690       if (!node->node6) {
 691         node->node6 = unique_ptr<node_type>(new node_type());
 692         _nodes.insert(node->node6.get());
 693       }
 694       value = node->node6.get();
 695     }
 696     // assign key
 697     value->first = key;
 698     return *value;
 699   }
 700
 701   //<! Creates or updates value
 702   void insert_or_assign(const key_type& mask, const value_type& value) {
 703     insert(mask).second = value;
 704   }
 705
 706   void insert_or_assign(const string& mask, const value_type& value) {
 707     insert(key_type(mask)).second = value;
 708   }
 709
 710   //<! check if given key is present in TreeMap
 711   bool has_key(const key_type& key) const {
 712     const node_type *ptr = lookup(key);
 713     return ptr && ptr->first == key;
 714   }
 715
 716   //<! Returns "best match" for key_type, which might not be value
 717   const node_type* lookup(const key_type& value) const {
 718     return lookup(value.getNetwork(), value.getBits());
 719   }
 720
 721   //<! Perform best match lookup for value, using at most max_bits
 722   const node_type* lookup(const ComboAddress& value, int max_bits = 128) const {
 723     if (!root) return nullptr;
 724
 725     TreeNode *node = root.get();
 726     node_type *ret = nullptr;
 727
 728     // exact same thing as above, except
 729     if (value.sin4.sin_family == AF_INET) {
 730       max_bits = std::max(0,std::min(max_bits,32));
 731       std::bitset<32> addr(be32toh(value.sin4.sin_addr.s_addr));
 732       int bits = 0;
 733
 734       while(bits < max_bits) {
 735         // ...we keep track of last non-empty node
 736         if (node->node4) ret = node->node4.get();
 737         uint8_t val = addr[31-bits];
 738         // ...and we don't create left/right hand
 739         if (val) {
 740           if (node->right) node = node->right.get();
 741           // ..and we break when road ends
 742           else break;
 743         } else {
 744           if (node->left) node = node->left.get();
 745           else break;
 746         }
 747         bits++;
 748       }
 749       // needed if we did not find one in loop
 750       if (node->node4) ret = node->node4.get();
 751     } else {
 752       uint64_t* addr = (uint64_t*)value.sin6.sin6_addr.s6_addr;
 753       max_bits = std::max(0,std::min(max_bits,128));
 754       std::bitset<64> addr_low(be64toh(addr[1]));
 755       std::bitset<64> addr_high(be64toh(addr[0]));
 756       int bits = 0;
 757       while(bits < max_bits) {
 758         if (node->node6) ret = node->node6.get();
 759         uint8_t val;
 760         if (bits < 64) val = addr_high[63-bits];
 761         else val = addr_low[127-bits];
 762         if (val) {
 763           if (node->right) node = node->right.get();
 764           else break;
 765         } else {
 766           if (node->left) node = node->left.get();
 767           else break;
 768         }
 769         bits++;
 770       }
 771       if (node->node6) ret = node->node6.get();
 772     }
 773
 774     // this can be nullptr.
 775     return ret;
 776   }
 777
 778   void cleanup_tree(TreeNode* node)
 779   {
 780     // only cleanup this node if it has no children and node4 and node6 are both empty
 781     if (!(node->left || node->right || node->node6 || node->node4)) {
 782       // get parent node ptr
 783       TreeNode* parent = node->parent;
 784       // delete this node
 785       if (parent) {
 786         if (parent->left.get() == node)
 787           parent->left.reset();
 788         else
 789           parent->right.reset();
 790         // now recurse up to the parent
 791         cleanup_tree(parent);
 792       }
 793     }
 794   }
 795
 796   //<! Removes key from TreeMap. This does not clean up the tree.
 797   void erase(const key_type& key) {
 798     TreeNode *node = root.get();
 799
 800     // no tree, no value
 801     if ( node == nullptr ) return;
 802
 803     // exact same thing as above, except
 804     if (key.getNetwork().sin4.sin_family == AF_INET) {
 805       std::bitset<32> addr(be32toh(key.getNetwork().sin4.sin_addr.s_addr));
 806       int bits = 0;
 807       while(node && bits < key.getBits()) {
 808         uint8_t val = addr[31-bits];
 809         if (val) {
 810           node = node->right.get();
 811         } else {
 812           node = node->left.get();
 813         }
 814         bits++;
 815       }
 816       if (node) {
 817         _nodes.erase(node->node4.get());
 818         node->node4.reset();
 819
 820         if (d_cleanup_tree)
 821           cleanup_tree(node);
 822       }
 823     } else {
 824       uint64_t* addr = (uint64_t*)key.getNetwork().sin6.sin6_addr.s6_addr;
 825       std::bitset<64> addr_low(be64toh(addr[1]));
 826       std::bitset<64> addr_high(be64toh(addr[0]));
 827       int bits = 0;
 828       while(node && bits < key.getBits()) {
 829         uint8_t val;
 830         if (bits < 64) val = addr_high[63-bits];
 831         else val = addr_low[127-bits];
 832         if (val) {
 833           node = node->right.get();
 834         } else {
 835           node = node->left.get();
 836         }
 837         bits++;
 838       }
 839       if (node) {
 840         _nodes.erase(node->node6.get());
 841         node->node6.reset();
 842
 843         if (d_cleanup_tree)
 844           cleanup_tree(node);
 845       }
 846     }
 847   }
 848
 849   void erase(const string& key) {
 850     erase(key_type(key));
 851   }
 852
 853   //<! checks whether the container is empty.
 854   bool empty() const {
 855     return _nodes.empty();
 856   }
 857
 858   //<! returns the number of elements
 859   size_type size() const {
 860     return _nodes.size();
 861   }
 862
 863   //<! See if given ComboAddress matches any prefix
 864   bool match(const ComboAddress& value) const {
 865     return (lookup(value) != nullptr);
 866   }
 867
 868   bool match(const std::string& value) const {
 869     return match(ComboAddress(value));
 870   }
 871
 872   //<! Clean out the tree
 873   void clear() {
 874     _nodes.clear();
 875     root.reset(nullptr);
 876   }
 877
 878   //<! swaps the contents, rhs is left with nullptr.
 879   void swap(NetmaskTree& rhs) {
 880     root.swap(rhs.root);
 881     _nodes.swap(rhs._nodes);
 882   }
 883
 884 private:
 885   unique_ptr<TreeNode> root; //<! Root of our tree
 886   std::set<node_type*> _nodes; //<! Container for actual values
 887   bool d_cleanup_tree; //<! Whether or not to cleanup the tree on erase
 888 };
 889
 890 /** This class represents a group of supplemental Netmask classes. An IP address matchs
 891     if it is matched by zero or more of the Netmask classes within.
 892 */
 893 class NetmaskGroup
 894 {
 895 public:
 896   //! By default, initialise the tree to cleanup
 897   NetmaskGroup() noexcept : NetmaskGroup(true) {
 898   }
 899
 900   //! This allows control over whether to cleanup or not
 901   NetmaskGroup(bool cleanup) noexcept : tree(cleanup) {
 902   }
 903
 904   //! If this IP address is matched by any of the classes within
 905
 906   bool match(const ComboAddress *ip) const
 907   {
 908     const auto &ret = tree.lookup(*ip);
 909     if(ret) return ret->second;
 910     return false;
 911   }
 912
 913   bool match(const ComboAddress& ip) const
 914   {
 915     return match(&ip);
 916   }
 917
 918   bool lookup(const ComboAddress* ip, Netmask* nmp) const
 919   {
 920     const auto &ret = tree.lookup(*ip);
 921     if (ret) {
 922       if (nmp != nullptr)
 923         *nmp = ret->first;
 924
 925       return ret->second;
 926     }
 927     return false;
 928   }
 929
 930   bool lookup(const ComboAddress& ip, Netmask* nmp) const
 931   {
 932     return lookup(&ip, nmp);
 933   }
 934
 935   //! Add this string to the list of possible matches
 936   void addMask(const string &ip, bool positive=true)
 937   {
 938     if(!ip.empty() && ip[0] == '!') {
 939       addMask(Netmask(ip.substr(1)), false);
 940     } else {
 941       addMask(Netmask(ip), positive);
 942     }
 943   }
 944
 945   //! Add this Netmask to the list of possible matches
 946   void addMask(const Netmask& nm, bool positive=true)
 947   {
 948     tree.insert(nm).second=positive;
 949   }
 950
 951   //! Delete this Netmask from the list of possible matches
 952   void deleteMask(const Netmask& nm)
 953   {
 954     tree.erase(nm);
 955   }
 956
 957   void deleteMask(const std::string& ip)
 958   {
 959     if (!ip.empty())
 960       deleteMask(Netmask(ip));
 961   }
 962
 963   void clear()
 964   {
 965     tree.clear();
 966   }
 967
 968   bool empty() const
 969   {
 970     return tree.empty();
 971   }
 972
 973   size_t size() const
 974   {
 975     return tree.size();
 976   }
 977
 978   string toString() const
 979   {
 980     ostringstream str;
 981     for(auto iter = tree.begin(); iter != tree.end(); ++iter) {
 982       if(iter != tree.begin())
 983         str <<", ";
 984       if(!((*iter)->second))
 985         str<<"!";
 986       str<<(*iter)->first.toString();
 987     }
 988     return str.str();
 989   }
 990
 991   void toStringVector(vector<string>* vec) const
 992   {
 993     for(auto iter = tree.begin(); iter != tree.end(); ++iter) {
 994       vec->push_back(((*iter)->second ? "" : "!") + (*iter)->first.toString());
 995     }
 996   }
 997
 998   void toMasks(const string &ips)
 999   {
1000     vector<string> parts;
1001     stringtok(parts, ips, ", \t");
1002
1003     for (vector<string>::const_iterator iter = parts.begin(); iter != parts.end(); ++iter)
1004       addMask(*iter);
1005   }
1006
1007 private:
1008   NetmaskTree<bool> tree;
1009 };
1010
1011
1012 struct SComboAddress
1013 {
1014   SComboAddress(const ComboAddress& orig) : ca(orig) {}
1015   ComboAddress ca;
1016   bool operator<(const SComboAddress& rhs) const
1017   {
1018     return ComboAddress::addressOnlyLessThan()(ca, rhs.ca);
1019   }
1020   operator const ComboAddress&()
1021   {
1022     return ca;
1023   }
1024 };
1025
1026 class NetworkError : public runtime_error
1027 {
1028 public:
1029   NetworkError(const string& why="Network Error") : runtime_error(why.c_str())
1030   {}
1031   NetworkError(const char *why="Network Error") : runtime_error(why)
1032   {}
1033 };
1034
1035 int SSocket(int family, int type, int flags);
1036 int SConnect(int sockfd, const ComboAddress& remote);
1037 /* tries to connect to remote for a maximum of timeout seconds.
1038    sockfd should be set to non-blocking beforehand.
1039    returns 0 on success (the socket is writable), throw a
1040    runtime_error otherwise */
1041 int SConnectWithTimeout(int sockfd, const ComboAddress& remote, int timeout);
1042 int SBind(int sockfd, const ComboAddress& local);
1043 int SAccept(int sockfd, ComboAddress& remote);
1044 int SListen(int sockfd, int limit);
1045 int SSetsockopt(int sockfd, int level, int opname, int value);
1046
1047 #if defined(IP_PKTINFO)
1048   #define GEN_IP_PKTINFO IP_PKTINFO
1049 #elif defined(IP_RECVDSTADDR)
1050   #define GEN_IP_PKTINFO IP_RECVDSTADDR
1051 #endif
1052
1053 bool IsAnyAddress(const ComboAddress& addr);
1054 bool HarvestDestinationAddress(const struct msghdr* msgh, ComboAddress* destination);
1055 bool HarvestTimestamp(struct msghdr* msgh, struct timeval* tv);
1056 void fillMSGHdr(struct msghdr* msgh, struct iovec* iov, char* cbuf, size_t cbufsize, char* data, size_t datalen, ComboAddress* addr);
1057 ssize_t sendfromto(int sock, const char* data, size_t len, int flags, const ComboAddress& from, const ComboAddress& to);
1058 ssize_t sendMsgWithTimeout(int fd, const char* buffer, size_t len, int timeout, ComboAddress& dest, const ComboAddress& local, unsigned int localItf);
1059 bool sendSizeAndMsgWithTimeout(int sock, uint16_t bufferLen, const char* buffer, int idleTimeout, const ComboAddress* dest, const ComboAddress* local, unsigned int localItf, int totalTimeout, int flags);
1060 /* requires a non-blocking, connected TCP socket */
1061 bool isTCPSocketUsable(int sock);
1062
1063 extern template class NetmaskTree<bool>;
1064
1065 #endif