pdns/iputils.hh

   1 /*
   2     PowerDNS Versatile Database Driven Nameserver
   3     Copyright (C) 2002 - 2016  PowerDNS.COM BV
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License version 2
   7     as published by the Free Software Foundation
   8
   9     Additionally, the license of this program contains a special
  10     exception which allows to distribute the program in binary form when
  11     it is linked against OpenSSL.
  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 St, 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 // for illumos
  63 #ifdef BE_64
  64
  65 #define htobe16(x) BE_16(x)
  66 #define htole16(x) LE_16(x)
  67 #define be16toh(x) BE_IN16(x)
  68 #define le16toh(x) LE_IN16(x)
  69
  70 #define htobe32(x) BE_32(x)
  71 #define htole32(x) LE_32(x)
  72 #define be32toh(x) BE_IN32(x)
  73 #define le32toh(x) LE_IN32(x)
  74
  75 #define htobe64(x) BE_64(x)
  76 #define htole64(x) LE_64(x)
  77 #define be64toh(x) BE_IN64(x)
  78 #define le64toh(x) LE_IN64(x)
  79
  80 #endif
  81
  82 #ifdef __FreeBSD__
  83 #include <sys/endian.h>
  84 #endif
  85
  86 union ComboAddress {
  87   struct sockaddr_in sin4;
  88   struct sockaddr_in6 sin6;
  89
  90   bool operator==(const ComboAddress& rhs) const
  91   {
  92     if(boost::tie(sin4.sin_family, sin4.sin_port) != boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port))
  93       return false;
  94     if(sin4.sin_family == AF_INET)
  95       return sin4.sin_addr.s_addr == rhs.sin4.sin_addr.s_addr;
  96     else
  97       return memcmp(&sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, sizeof(sin6.sin6_addr.s6_addr))==0;
  98   }
  99
 100   bool operator!=(const ComboAddress& rhs) const
 101   {
 102     return(!operator==(rhs));
 103   }
 104
 105   bool operator<(const ComboAddress& rhs) const
 106   {
 107     if(sin4.sin_family == 0) {
 108       return false;
 109     }
 110     if(boost::tie(sin4.sin_family, sin4.sin_port) < boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port))
 111       return true;
 112     if(boost::tie(sin4.sin_family, sin4.sin_port) > boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port))
 113       return false;
 114
 115     if(sin4.sin_family == AF_INET)
 116       return sin4.sin_addr.s_addr < rhs.sin4.sin_addr.s_addr;
 117     else
 118       return memcmp(&sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, sizeof(sin6.sin6_addr.s6_addr)) < 0;
 119   }
 120
 121   bool operator>(const ComboAddress& rhs) const
 122   {
 123     return rhs.operator<(*this);
 124   }
 125
 126   struct addressOnlyHash
 127   {
 128     uint32_t operator()(const ComboAddress& ca) const
 129     {
 130       const unsigned char* start;
 131       int len;
 132       if(ca.sin4.sin_family == AF_INET) {
 133         start =(const unsigned char*)&ca.sin4.sin_addr.s_addr;
 134         len=4;
 135       }
 136       else {
 137         start =(const unsigned char*)&ca.sin6.sin6_addr.s6_addr;
 138         len=16;
 139       }
 140       return burtle(start, len, 0);
 141     }
 142   };
 143
 144   struct addressOnlyLessThan: public std::binary_function<ComboAddress, ComboAddress, bool>
 145   {
 146     bool operator()(const ComboAddress& a, const ComboAddress& b) const
 147     {
 148       if(a.sin4.sin_family < b.sin4.sin_family)
 149         return true;
 150       if(a.sin4.sin_family > b.sin4.sin_family)
 151         return false;
 152       if(a.sin4.sin_family == AF_INET)
 153         return a.sin4.sin_addr.s_addr < b.sin4.sin_addr.s_addr;
 154       else
 155         return memcmp(&a.sin6.sin6_addr.s6_addr, &b.sin6.sin6_addr.s6_addr, sizeof(a.sin6.sin6_addr.s6_addr)) < 0;
 156     }
 157   };
 158
 159   struct addressOnlyEqual: public std::binary_function<ComboAddress, ComboAddress, bool>
 160   {
 161     bool operator()(const ComboAddress& a, const ComboAddress& b) const
 162     {
 163       if(a.sin4.sin_family != b.sin4.sin_family)
 164         return false;
 165       if(a.sin4.sin_family == AF_INET)
 166         return a.sin4.sin_addr.s_addr == b.sin4.sin_addr.s_addr;
 167       else
 168         return !memcmp(&a.sin6.sin6_addr.s6_addr, &b.sin6.sin6_addr.s6_addr, sizeof(a.sin6.sin6_addr.s6_addr));
 169     }
 170   };
 171
 172
 173   socklen_t getSocklen() const
 174   {
 175     if(sin4.sin_family == AF_INET)
 176       return sizeof(sin4);
 177     else
 178       return sizeof(sin6);
 179   }
 180
 181   ComboAddress()
 182   {
 183     sin4.sin_family=AF_INET;
 184     sin4.sin_addr.s_addr=0;
 185     sin4.sin_port=0;
 186   }
 187
 188   ComboAddress(const struct sockaddr *sa, socklen_t salen) {
 189     setSockaddr(sa, salen);
 190   };
 191
 192   ComboAddress(const struct sockaddr_in6 *sa) {
 193     setSockaddr((const struct sockaddr*)sa, sizeof(struct sockaddr_in6));
 194   };
 195
 196   ComboAddress(const struct sockaddr_in *sa) {
 197     setSockaddr((const struct sockaddr*)sa, sizeof(struct sockaddr_in));
 198   };
 199
 200   void setSockaddr(const struct sockaddr *sa, socklen_t salen) {
 201     if (salen > sizeof(struct sockaddr_in6)) throw PDNSException("ComboAddress can't handle other than sockaddr_in or sockaddr_in6");
 202     memcpy(this, sa, salen);
 203   }
 204
 205   // 'port' sets a default value in case 'str' does not set a port
 206   explicit ComboAddress(const string& str, uint16_t port=0)
 207   {
 208     memset(&sin6, 0, sizeof(sin6));
 209     sin4.sin_family = AF_INET;
 210     sin4.sin_port = 0;
 211     if(makeIPv4sockaddr(str, &sin4)) {
 212       sin6.sin6_family = AF_INET6;
 213       if(makeIPv6sockaddr(str, &sin6) < 0)
 214         throw PDNSException("Unable to convert presentation address '"+ str +"'");
 215
 216     }
 217     if(!sin4.sin_port) // 'str' overrides port!
 218       sin4.sin_port=htons(port);
 219   }
 220
 221   bool isMappedIPv4()  const
 222   {
 223     if(sin4.sin_family!=AF_INET6)
 224       return false;
 225
 226     int n=0;
 227     const unsigned char*ptr = (unsigned char*) &sin6.sin6_addr.s6_addr;
 228     for(n=0; n < 10; ++n)
 229       if(ptr[n])
 230         return false;
 231
 232     for(; n < 12; ++n)
 233       if(ptr[n]!=0xff)
 234         return false;
 235
 236     return true;
 237   }
 238
 239   ComboAddress mapToIPv4() const
 240   {
 241     if(!isMappedIPv4())
 242       throw PDNSException("ComboAddress can't map non-mapped IPv6 address back to IPv4");
 243     ComboAddress ret;
 244     ret.sin4.sin_family=AF_INET;
 245     ret.sin4.sin_port=sin4.sin_port;
 246
 247     const unsigned char*ptr = (unsigned char*) &sin6.sin6_addr.s6_addr;
 248     ptr+=(sizeof(sin6.sin6_addr.s6_addr) - sizeof(ret.sin4.sin_addr.s_addr));
 249     memcpy(&ret.sin4.sin_addr.s_addr, ptr, sizeof(ret.sin4.sin_addr.s_addr));
 250     return ret;
 251   }
 252
 253   string toString() const
 254   {
 255     char host[1024];
 256     if(sin4.sin_family && !getnameinfo((struct sockaddr*) this, getSocklen(), host, sizeof(host),0, 0, NI_NUMERICHOST))
 257       return host;
 258     else
 259       return "invalid";
 260   }
 261
 262   string toStringWithPort() const
 263   {
 264     if(sin4.sin_family==AF_INET)
 265       return toString() + ":" + std::to_string(ntohs(sin4.sin_port));
 266     else
 267       return "["+toString() + "]:" + std::to_string(ntohs(sin4.sin_port));
 268   }
 269
 270   void truncate(unsigned int bits);
 271 };
 272
 273 /** This exception is thrown by the Netmask class and by extension by the NetmaskGroup class */
 274 class NetmaskException: public PDNSException
 275 {
 276 public:
 277   NetmaskException(const string &a) : PDNSException(a) {}
 278 };
 279
 280 inline ComboAddress makeComboAddress(const string& str)
 281 {
 282   ComboAddress address;
 283   address.sin4.sin_family=AF_INET;
 284   if(inet_pton(AF_INET, str.c_str(), &address.sin4.sin_addr) <= 0) {
 285     address.sin4.sin_family=AF_INET6;
 286     if(makeIPv6sockaddr(str, &address.sin6) < 0)
 287       throw NetmaskException("Unable to convert '"+str+"' to a netmask");
 288   }
 289   return address;
 290 }
 291
 292 /** This class represents a netmask and can be queried to see if a certain
 293     IP address is matched by this mask */
 294 class Netmask
 295 {
 296 public:
 297   Netmask()
 298   {
 299         d_network.sin4.sin_family=0; // disable this doing anything useful
 300         d_network.sin4.sin_port = 0; // this guarantees d_network compares identical
 301         d_mask=0;
 302         d_bits=0;
 303   }
 304
 305   Netmask(const ComboAddress& network, uint8_t bits=0xff)
 306   {
 307     d_network = network;
 308
 309     if(bits > 128)
 310       bits = (network.sin4.sin_family == AF_INET) ? 32 : 128;
 311
 312     d_bits = bits;
 313     if(d_bits<32)
 314       d_mask=~(0xFFFFFFFF>>d_bits);
 315     else
 316       d_mask=0xFFFFFFFF; // not actually used for IPv6
 317   }
 318
 319   //! Constructor supplies the mask, which cannot be changed
 320   Netmask(const string &mask)
 321   {
 322     pair<string,string> split=splitField(mask,'/');
 323     d_network=makeComboAddress(split.first);
 324
 325     if(!split.second.empty()) {
 326       d_bits = (uint8_t)pdns_stou(split.second);
 327       if(d_bits<32)
 328         d_mask=~(0xFFFFFFFF>>d_bits);
 329       else
 330         d_mask=0xFFFFFFFF;
 331     }
 332     else if(d_network.sin4.sin_family==AF_INET) {
 333       d_bits = 32;
 334       d_mask = 0xFFFFFFFF;
 335     }
 336     else {
 337       d_bits=128;
 338       d_mask=0;  // silence silly warning - d_mask is unused for IPv6
 339     }
 340   }
 341
 342   bool match(const ComboAddress& ip) const
 343   {
 344     return match(&ip);
 345   }
 346
 347   //! If this IP address in socket address matches
 348   bool match(const ComboAddress *ip) const
 349   {
 350     if(d_network.sin4.sin_family != ip->sin4.sin_family) {
 351       return false;
 352     }
 353     if(d_network.sin4.sin_family == AF_INET) {
 354       return match4(htonl((unsigned int)ip->sin4.sin_addr.s_addr));
 355     }
 356     if(d_network.sin6.sin6_family == AF_INET6) {
 357       uint8_t bytes=d_bits/8, n;
 358       const uint8_t *us=(const uint8_t*) &d_network.sin6.sin6_addr.s6_addr;
 359       const uint8_t *them=(const uint8_t*) &ip->sin6.sin6_addr.s6_addr;
 360
 361       for(n=0; n < bytes; ++n) {
 362         if(us[n]!=them[n]) {
 363           return false;
 364         }
 365       }
 366       // still here, now match remaining bits
 367       uint8_t bits= d_bits % 8;
 368       uint8_t mask= (uint8_t) ~(0xFF>>bits);
 369
 370       return((us[n] & mask) == (them[n] & mask));
 371     }
 372     return false;
 373   }
 374
 375   //! If this ASCII IP address matches
 376   bool match(const string &ip) const
 377   {
 378     ComboAddress address=makeComboAddress(ip);
 379     return match(&address);
 380   }
 381
 382   //! If this IP address in native format matches
 383   bool match4(uint32_t ip) const
 384   {
 385     return (ip & d_mask) == (ntohl(d_network.sin4.sin_addr.s_addr) & d_mask);
 386   }
 387
 388   string toString() const
 389   {
 390     return d_network.toString()+"/"+std::to_string((unsigned int)d_bits);
 391   }
 392
 393   string toStringNoMask() const
 394   {
 395     return d_network.toString();
 396   }
 397   const ComboAddress& getNetwork() const
 398   {
 399     return d_network;
 400   }
 401   const ComboAddress getMaskedNetwork() const
 402   {
 403     ComboAddress result(d_network);
 404     if(isIpv4()) {
 405       result.sin4.sin_addr.s_addr = htonl(ntohl(result.sin4.sin_addr.s_addr) & d_mask);
 406     }
 407     else if(isIpv6()) {
 408       size_t idx;
 409       uint8_t bytes=d_bits/8;
 410       uint8_t *us=(uint8_t*) &result.sin6.sin6_addr.s6_addr;
 411       uint8_t bits= d_bits % 8;
 412       uint8_t mask= (uint8_t) ~(0xFF>>bits);
 413
 414       if (bytes < sizeof(result.sin6.sin6_addr.s6_addr)) {
 415         us[bytes] &= mask;
 416       }
 417
 418       for(idx = bytes + 1; idx < sizeof(result.sin6.sin6_addr.s6_addr); ++idx) {
 419         us[idx] = 0;
 420       }
 421     }
 422     return result;
 423   }
 424   int getBits() const
 425   {
 426     return d_bits;
 427   }
 428   bool isIpv6() const
 429   {
 430     return d_network.sin6.sin6_family == AF_INET6;
 431   }
 432   bool isIpv4() const
 433   {
 434     return d_network.sin4.sin_family == AF_INET;
 435   }
 436
 437   bool operator<(const Netmask& rhs) const
 438   {
 439     return tie(d_network, d_bits) < tie(rhs.d_network, rhs.d_bits);
 440   }
 441
 442   bool operator==(const Netmask& rhs) const
 443   {
 444     return tie(d_network, d_bits) == tie(rhs.d_network, rhs.d_bits);
 445   }
 446
 447   bool empty() const
 448   {
 449     return d_network.sin4.sin_family==0;
 450   }
 451
 452 private:
 453   ComboAddress d_network;
 454   uint32_t d_mask;
 455   uint8_t d_bits;
 456 };
 457
 458 /** Per-bit binary tree map implementation with <Netmask,T> pair.
 459  *
 460  * This is an binary tree implementation for storing attributes for IPv4 and IPv6 prefixes.
 461  * The most simple use case is simple NetmaskTree<bool> used by NetmaskGroup, which only
 462  * wants to know if given IP address is matched in the prefixes stored.
 463  *
 464  * This element is useful for anything that needs to *STORE* prefixes, and *MATCH* IP addresses
 465  * to a *LIST* of *PREFIXES*. Not the other way round.
 466  *
 467  * You can store IPv4 and IPv6 addresses to same tree, separate payload storage is kept per AFI.
 468  *
 469  * To erase something copy values to new tree sans the value you want to erase.
 470  *
 471  * Use swap if you need to move the tree to another NetmaskTree instance, it is WAY faster
 472  * than using copy ctor or assigment operator, since it moves the nodes and tree root to
 473  * new home instead of actually recreating the tree.
 474  *
 475  * Please see NetmaskGroup for example of simple use case. Other usecases can be found
 476  * from GeoIPBackend and Sortlist, and from dnsdist.
 477  */
 478 template <typename T>
 479 class NetmaskTree {
 480 public:
 481   typedef Netmask key_type;
 482   typedef T value_type;
 483   typedef std::pair<key_type,value_type> node_type;
 484   typedef size_t size_type;
 485
 486 private:
 487   /** Single node in tree, internal use only.
 488     */
 489   class TreeNode : boost::noncopyable {
 490   public:
 491      explicit TreeNode(int bits) noexcept : parent(NULL),d_bits(bits) {
 492      }
 493
 494      //<! Makes a left node with one more bit than parent
 495      TreeNode* make_left() {
 496        if (!left) {
 497          left = unique_ptr<TreeNode>(new TreeNode(d_bits+1));
 498          left->parent = this;
 499        }
 500        return left.get();
 501      }
 502
 503      //<! Makes a right node with one more bit than parent
 504      TreeNode* make_right() {
 505        if (!right) {
 506          right = unique_ptr<TreeNode>(new TreeNode(d_bits+1));
 507          right->parent = this;
 508        }
 509        return right.get();
 510      }
 511
 512      unique_ptr<TreeNode> left;
 513      unique_ptr<TreeNode> right;
 514      TreeNode* parent;
 515
 516      unique_ptr<node_type> node4; //<! IPv4 value-pair
 517      unique_ptr<node_type> node6; //<! IPv6 value-pair
 518
 519      int d_bits; //<! How many bits have been used so far
 520   };
 521
 522 public:
 523   NetmaskTree() noexcept {
 524   }
 525
 526   NetmaskTree(const NetmaskTree& rhs) {
 527     // it is easier to copy the nodes than tree.
 528     // also acts as handy compactor
 529     for(auto const& node: rhs._nodes)
 530       insert(node->first).second = node->second;
 531   }
 532
 533   NetmaskTree& operator=(const NetmaskTree& rhs) {
 534     clear();
 535     // see above.
 536     for(auto const& node: rhs._nodes)
 537       insert(node->first).second = node->second;
 538     return *this;
 539   }
 540
 541   const typename std::vector<node_type*>::const_iterator begin() const { return _nodes.begin(); }
 542   const typename std::vector<node_type*>::const_iterator end() const { return _nodes.end(); }
 543
 544   typename std::vector<node_type*>::iterator begin() { return _nodes.begin(); }
 545   typename std::vector<node_type*>::iterator end() { return _nodes.end(); }
 546
 547   node_type& insert(const string &mask) {
 548     return insert(key_type(mask));
 549   }
 550
 551   //<! Creates new value-pair in tree and returns it.
 552   node_type& insert(const key_type& key) {
 553     // lazily initialize tree on first insert.
 554     if (!root) root = unique_ptr<TreeNode>(new TreeNode(0));
 555     TreeNode* node = root.get();
 556     node_type* value = nullptr;
 557
 558     if (key.getNetwork().sin4.sin_family == AF_INET) {
 559       std::bitset<32> addr(be32toh(key.getNetwork().sin4.sin_addr.s_addr));
 560       int bits = 0;
 561       // we turn left on 0 and right on 1
 562       while(bits < key.getBits()) {
 563         uint8_t val = addr[31-bits];
 564         if (val)
 565           node = node->make_right();
 566         else
 567           node = node->make_left();
 568         bits++;
 569       }
 570       // only create node if not yet assigned
 571       if (!node->node4) {
 572         node->node4 = unique_ptr<node_type>(new node_type());
 573         _nodes.push_back(node->node4.get());
 574       }
 575       value = node->node4.get();
 576     } else {
 577       uint64_t* addr = (uint64_t*)key.getNetwork().sin6.sin6_addr.s6_addr;
 578       std::bitset<64> addr_low(be64toh(addr[1]));
 579       std::bitset<64> addr_high(be64toh(addr[0]));
 580       int bits = 0;
 581       while(bits < key.getBits()) {
 582         uint8_t val;
 583         // we use high address until we are
 584         if (bits < 64) val = addr_high[63-bits];
 585         // past 64 bits, and start using low address
 586         else val = addr_low[127-bits];
 587
 588         // we turn left on 0 and right on 1
 589         if (val)
 590           node = node->make_right();
 591         else
 592           node = node->make_left();
 593         bits++;
 594       }
 595       // only create node if not yet assigned
 596       if (!node->node6) {
 597         node->node6 = unique_ptr<node_type>(new node_type());
 598         _nodes.push_back(node->node6.get());
 599       }
 600       value = node->node6.get();
 601     }
 602     // assign key
 603     value->first = key;
 604     return *value;
 605   }
 606
 607   //<! Creates or updates value
 608   void insert_or_assign(const key_type& mask, const value_type& value) {
 609     insert(mask).second = value;
 610   }
 611
 612   void insert_or_assign(const string& mask, const value_type& value) {
 613     insert(key_type(mask)).second = value;
 614   }
 615
 616   //<! check if given key is present in TreeMap
 617   bool has_key(const key_type& key) const {
 618     const node_type *ptr = lookup(key);
 619     return ptr && ptr->first == key;
 620   }
 621
 622   //<! Returns "best match" for key_type, which might not be value
 623   const node_type* lookup(const key_type& value) const {
 624     return lookup(value.getNetwork(), value.getBits());
 625   }
 626
 627   //<! Perform best match lookup for value, using at most max_bits
 628   const node_type* lookup(const ComboAddress& value, int max_bits = 128) const {
 629     if (!root) return nullptr;
 630
 631     TreeNode *node = root.get();
 632     node_type *ret = nullptr;
 633
 634     // exact same thing as above, except
 635     if (value.sin4.sin_family == AF_INET) {
 636       max_bits = std::max(0,std::min(max_bits,32));
 637       std::bitset<32> addr(be32toh(value.sin4.sin_addr.s_addr));
 638       int bits = 0;
 639
 640       while(bits < max_bits) {
 641         // ...we keep track of last non-empty node
 642         if (node->node4) ret = node->node4.get();
 643         uint8_t val = addr[31-bits];
 644         // ...and we don't create left/right hand
 645         if (val) {
 646           if (node->right) node = node->right.get();
 647           // ..and we break when road ends
 648           else break;
 649         } else {
 650           if (node->left) node = node->left.get();
 651           else break;
 652         }
 653         bits++;
 654       }
 655       // needed if we did not find one in loop
 656       if (node->node4) ret = node->node4.get();
 657     } else {
 658       uint64_t* addr = (uint64_t*)value.sin6.sin6_addr.s6_addr;
 659       max_bits = std::max(0,std::min(max_bits,128));
 660       std::bitset<64> addr_low(be64toh(addr[1]));
 661       std::bitset<64> addr_high(be64toh(addr[0]));
 662       int bits = 0;
 663       while(bits < max_bits) {
 664         if (node->node6) ret = node->node6.get();
 665         uint8_t val;
 666         if (bits < 64) val = addr_high[63-bits];
 667         else val = addr_low[127-bits];
 668         if (val) {
 669           if (node->right) node = node->right.get();
 670           else break;
 671         } else {
 672           if (node->left) node = node->left.get();
 673           else break;
 674         }
 675         bits++;
 676       }
 677       if (node->node6) ret = node->node6.get();
 678     }
 679
 680     // this can be nullptr.
 681     return ret;
 682   }
 683
 684   //<! Removes key from TreeMap. This does not clean up the tree.
 685   void erase(const key_type& key) {
 686     TreeNode *node = root.get();
 687
 688     // no tree, no value
 689     if ( node == nullptr ) return;
 690
 691     // exact same thing as above, except
 692     if (key.getNetwork().sin4.sin_family == AF_INET) {
 693       std::bitset<32> addr(be32toh(key.getNetwork().sin4.sin_addr.s_addr));
 694       int bits = 0;
 695       while(node && bits < key.getBits()) {
 696         uint8_t val = addr[31-bits];
 697         if (val) {
 698           node = node->right.get();
 699         } else {
 700           node = node->left.get();
 701         }
 702         bits++;
 703       }
 704       if (node) {
 705         for(auto it = _nodes.begin(); it != _nodes.end(); it++)
 706            if (node->node4.get() == *it) _nodes.erase(it);
 707         node->node4.reset();
 708       }
 709     } else {
 710       uint64_t* addr = (uint64_t*)key.getNetwork().sin6.sin6_addr.s6_addr;
 711       std::bitset<64> addr_low(be64toh(addr[1]));
 712       std::bitset<64> addr_high(be64toh(addr[0]));
 713       int bits = 0;
 714       while(node && bits < key.getBits()) {
 715         uint8_t val;
 716         if (bits < 64) val = addr_high[63-bits];
 717         else val = addr_low[127-bits];
 718         if (val) {
 719           node = node->right.get();
 720         } else {
 721           node = node->left.get();
 722         }
 723         bits++;
 724       }
 725       if (node) {
 726         for(auto it = _nodes.begin(); it != _nodes.end(); it++)
 727            if (node->node6.get() == *it) _nodes.erase(it);
 728         node->node6.reset();
 729       }
 730     }
 731   }
 732
 733   void erase(const string& key) {
 734     erase(key_type(key));
 735   }
 736
 737   //<! checks whether the container is empty.
 738   bool empty() const {
 739     return _nodes.empty();
 740   }
 741
 742   //<! returns the number of elements
 743   size_type size() const {
 744     return _nodes.size();
 745   }
 746
 747   //<! See if given ComboAddress matches any prefix
 748   bool match(const ComboAddress& value) const {
 749     return (lookup(value) != nullptr);
 750   }
 751
 752   bool match(const std::string& value) const {
 753     return match(ComboAddress(value));
 754   }
 755
 756   //<! Clean out the tree
 757   void clear() {
 758     _nodes.clear();
 759     root.reset(nullptr);
 760   }
 761
 762   //<! swaps the contents, rhs is left with nullptr.
 763   void swap(NetmaskTree& rhs) {
 764     root.swap(rhs.root);
 765     _nodes.swap(rhs._nodes);
 766   }
 767
 768 private:
 769   unique_ptr<TreeNode> root; //<! Root of our tree
 770   std::vector<node_type*> _nodes; //<! Container for actual values
 771 };
 772
 773 /** This class represents a group of supplemental Netmask classes. An IP address matchs
 774     if it is matched by zero or more of the Netmask classes within.
 775 */
 776 class NetmaskGroup
 777 {
 778 public:
 779   //! If this IP address is matched by any of the classes within
 780
 781   bool match(const ComboAddress *ip) const
 782   {
 783     return tree.match(*ip);
 784   }
 785
 786   bool match(const ComboAddress& ip) const
 787   {
 788     return match(&ip);
 789   }
 790
 791   //! Add this string to the list of possible matches
 792   void addMask(const string &ip)
 793   {
 794     addMask(Netmask(ip));
 795   }
 796
 797   //! Add this Netmask to the list of possible matches
 798   void addMask(const Netmask& nm)
 799   {
 800     tree.insert(nm);
 801   }
 802
 803   void clear()
 804   {
 805     tree.clear();
 806   }
 807
 808   bool empty() const
 809   {
 810     return tree.empty();
 811   }
 812
 813   size_t size() const
 814   {
 815     return tree.size();
 816   }
 817
 818   string toString() const
 819   {
 820     ostringstream str;
 821     for(auto iter = tree.begin(); iter != tree.end(); ++iter) {
 822       if(iter != tree.begin())
 823         str <<", ";
 824       str<<(*iter)->first.toString();
 825     }
 826     return str.str();
 827   }
 828
 829   void toStringVector(vector<string>* vec) const
 830   {
 831     for(auto iter = tree.begin(); iter != tree.end(); ++iter)
 832       vec->push_back((*iter)->first.toString());
 833   }
 834
 835   void toMasks(const string &ips)
 836   {
 837     vector<string> parts;
 838     stringtok(parts, ips, ", \t");
 839
 840     for (vector<string>::const_iterator iter = parts.begin(); iter != parts.end(); ++iter)
 841       addMask(*iter);
 842   }
 843
 844 private:
 845   NetmaskTree<bool> tree;
 846 };
 847
 848
 849 struct SComboAddress
 850 {
 851   SComboAddress(const ComboAddress& orig) : ca(orig) {}
 852   ComboAddress ca;
 853   bool operator<(const SComboAddress& rhs) const
 854   {
 855     return ComboAddress::addressOnlyLessThan()(ca, rhs.ca);
 856   }
 857   operator const ComboAddress&()
 858   {
 859     return ca;
 860   }
 861 };
 862
 863
 864 int SSocket(int family, int type, int flags);
 865 int SConnect(int sockfd, const ComboAddress& remote);
 866 int SBind(int sockfd, const ComboAddress& local);
 867 int SAccept(int sockfd, ComboAddress& remote);
 868 int SListen(int sockfd, int limit);
 869 int SSetsockopt(int sockfd, int level, int opname, int value);
 870
 871 #if defined(IP_PKTINFO)
 872   #define GEN_IP_PKTINFO IP_PKTINFO
 873 #elif defined(IP_RECVDSTADDR)
 874   #define GEN_IP_PKTINFO IP_RECVDSTADDR
 875 #endif
 876 bool IsAnyAddress(const ComboAddress& addr);
 877 bool HarvestDestinationAddress(struct msghdr* msgh, ComboAddress* destination);
 878 bool HarvestTimestamp(struct msghdr* msgh, struct timeval* tv);
 879 void fillMSGHdr(struct msghdr* msgh, struct iovec* iov, char* cbuf, size_t cbufsize, char* data, size_t datalen, ComboAddress* addr);
 880 ssize_t sendfromto(int sock, const char* data, size_t len, int flags, const ComboAddress& from, const ComboAddress& to);
 881 ssize_t sendMsgWithTimeout(int fd, const char* buffer, size_t len, int timeout, ComboAddress& dest, const ComboAddress& local, unsigned int localItf);
 882
 883 #endif
 884
 885 extern template class NetmaskTree<bool>;