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