pdns/dnsname.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 #pragma once
  23 #include <string>
  24 #include <vector>
  25 #include <set>
  26 #include <deque>
  27 #include <strings.h>
  28 #include <stdexcept>
  29 #include <sstream>
  30 #include <iterator>
  31 #include <unordered_set>
  32
  33 #include <boost/version.hpp>
  34
  35 // it crashes on OSX and doesn't compile on OpenBSD
  36 #if BOOST_VERSION >= 105300 && ! defined( __APPLE__ ) && ! defined(__OpenBSD__)
  37 #include <boost/container/string.hpp>
  38 #endif
  39
  40 #include "ascii.hh"
  41
  42 uint32_t burtleCI(const unsigned char* k, uint32_t length, uint32_t init);
  43
  44 // #include "dns.hh"
  45 // #include "logger.hh"
  46
  47 //#include <ext/vstring.h>
  48
  49 /* Quest in life:
  50      accept escaped ascii presentations of DNS names and store them "natively"
  51      accept a DNS packet with an offset, and extract a DNS name from it
  52      build up DNSNames with prepend and append of 'raw' unescaped labels
  53
  54    Be able to turn them into ASCII and "DNS name in a packet" again on request
  55
  56    Provide some common operators for comparison, detection of being part of another domain
  57
  58    NOTE: For now, everything MUST be . terminated, otherwise it is an error
  59 */
  60
  61 class DNSName
  62 {
  63 public:
  64   DNSName()  {}          //!< Constructs an *empty* DNSName, NOT the root!
  65   explicit DNSName(const char* p): DNSName(p, strlen(p)) {} //!< Constructs from a human formatted, escaped presentation
  66   explicit DNSName(const char* p, size_t len);      //!< Constructs from a human formatted, escaped presentation
  67   explicit DNSName(const std::string& str) : DNSName(str.c_str(), str.length()) {}; //!< Constructs from a human formatted, escaped presentation
  68   DNSName(const char* p, int len, int offset, bool uncompress, uint16_t* qtype=nullptr, uint16_t* qclass=nullptr, unsigned int* consumed=nullptr, uint16_t minOffset=0); //!< Construct from a DNS Packet, taking the first question if offset=12. If supplied, consumed is set to the number of bytes consumed from the packet, which will not be equal to the wire length of the resulting name in case of compression.
  69
  70   bool isPartOf(const DNSName& rhs) const;   //!< Are we part of the rhs name?
  71   inline bool operator==(const DNSName& rhs) const; //!< DNS-native comparison (case insensitive) - empty compares to empty
  72   bool operator!=(const DNSName& other) const { return !(*this == other); }
  73
  74   std::string toString(const std::string& separator=".", const bool trailing=true) const;              //!< Our human-friendly, escaped, representation
  75   std::string toLogString() const; //!< like plain toString, but returns (empty) on empty names
  76   std::string toStringNoDot() const { return toString(".", false); }
  77   std::string toStringRootDot() const { if(isRoot()) return "."; else return toString(".", false); }
  78   std::string toDNSString() const;           //!< Our representation in DNS native format
  79   std::string toDNSStringLC() const;           //!< Our representation in DNS native format, lower cased
  80   void appendRawLabel(const std::string& str); //!< Append this unescaped label
  81   void appendRawLabel(const char* start, unsigned int length); //!< Append this unescaped label
  82   void prependRawLabel(const std::string& str); //!< Prepend this unescaped label
  83   std::vector<std::string> getRawLabels() const; //!< Individual raw unescaped labels
  84   std::string getRawLabel(unsigned int pos) const; //!< Get the specified raw unescaped label
  85   DNSName getLastLabel() const; //!< Get the DNSName of the last label
  86   bool chopOff();                               //!< Turn www.powerdns.com. into powerdns.com., returns false for .
  87   DNSName makeRelative(const DNSName& zone) const;
  88   DNSName makeLowerCase() const
  89   {
  90     DNSName ret(*this);
  91     ret.makeUsLowerCase();
  92     return ret;
  93   }
  94   void makeUsLowerCase()
  95   {
  96     for(auto & c : d_storage) {
  97       c=dns_tolower(c);
  98     }
  99   }
 100   void makeUsRelative(const DNSName& zone);
 101   DNSName getCommonLabels(const DNSName& other) const; //!< Return the list of common labels from the top, for example 'c.d' for 'a.b.c.d' and 'x.y.c.d'
 102   DNSName labelReverse() const;
 103   bool isWildcard() const;
 104   bool isHostname() const;
 105   unsigned int countLabels() const;
 106   size_t wirelength() const; //!< Number of total bytes in the name
 107   bool empty() const { return d_storage.empty(); }
 108   bool isRoot() const { return d_storage.size()==1 && d_storage[0]==0; }
 109   void clear() { d_storage.clear(); }
 110   void trimToLabels(unsigned int);
 111   size_t hash(size_t init=0) const
 112   {
 113     return burtleCI((const unsigned char*)d_storage.c_str(), d_storage.size(), init);
 114   }
 115   DNSName& operator+=(const DNSName& rhs)
 116   {
 117     if(d_storage.size() + rhs.d_storage.size() > 256) // one extra byte for the second root label
 118       throw std::range_error("name too long");
 119     if(rhs.empty())
 120       return *this;
 121
 122     if(d_storage.empty())
 123       d_storage+=rhs.d_storage;
 124     else
 125       d_storage.replace(d_storage.length()-1, rhs.d_storage.length(), rhs.d_storage);
 126
 127     return *this;
 128   }
 129
 130   bool operator<(const DNSName& rhs)  const // this delivers _some_ kind of ordering, but not one useful in a DNS context. Really fast though.
 131   {
 132     return std::lexicographical_compare(d_storage.rbegin(), d_storage.rend(),
 133                                  rhs.d_storage.rbegin(), rhs.d_storage.rend(),
 134                                  [](const unsigned char& a, const unsigned char& b) {
 135                                           return dns_tolower(a) < dns_tolower(b);
 136                                         }); // note that this is case insensitive, including on the label lengths
 137   }
 138
 139   inline bool canonCompare(const DNSName& rhs) const;
 140   bool slowCanonCompare(const DNSName& rhs) const;
 141
 142 #if BOOST_VERSION >= 105300 && ! defined( __APPLE__ ) && ! defined(__OpenBSD__)
 143   typedef boost::container::string string_t;
 144 #else
 145   typedef std::string string_t;
 146 #endif
 147   const string_t& getStorage() const {
 148     return d_storage;
 149   }
 150 private:
 151   string_t d_storage;
 152
 153   void packetParser(const char* p, int len, int offset, bool uncompress, uint16_t* qtype, uint16_t* qclass, unsigned int* consumed, int depth, uint16_t minOffset);
 154   static void appendEscapedLabel(std::string& appendTo, const char* orig, size_t len);
 155   static std::string unescapeLabel(const std::string& orig);
 156 };
 157
 158 size_t hash_value(DNSName const& d);
 159
 160
 161 inline bool DNSName::canonCompare(const DNSName& rhs) const
 162 {
 163   //      01234567890abcd
 164   // us:  1a3www4ds9a2nl
 165   // rhs: 3www6online3com
 166   // to compare, we start at the back, is nl < com? no -> done
 167   //
 168   // 0,2,6,a
 169   // 0,4,a
 170
 171   uint8_t ourpos[64], rhspos[64];
 172   uint8_t ourcount=0, rhscount=0;
 173   //cout<<"Asked to compare "<<toString()<<" to "<<rhs.toString()<<endl;
 174   for(const unsigned char* p = (const unsigned char*)d_storage.c_str(); p < (const unsigned char*)d_storage.c_str() + d_storage.size() && *p && ourcount < sizeof(ourpos); p+=*p+1)
 175     ourpos[ourcount++]=(p-(const unsigned char*)d_storage.c_str());
 176   for(const unsigned char* p = (const unsigned char*)rhs.d_storage.c_str(); p < (const unsigned char*)rhs.d_storage.c_str() + rhs.d_storage.size() && *p && rhscount < sizeof(rhspos); p+=*p+1)
 177     rhspos[rhscount++]=(p-(const unsigned char*)rhs.d_storage.c_str());
 178
 179   if(ourcount == sizeof(ourpos) || rhscount==sizeof(rhspos)) {
 180     return slowCanonCompare(rhs);
 181   }
 182
 183   for(;;) {
 184     if(ourcount == 0 && rhscount != 0)
 185       return true;
 186     if(rhscount == 0)
 187       return false;
 188     ourcount--;
 189     rhscount--;
 190
 191     bool res=std::lexicographical_compare(
 192                                           d_storage.c_str() + ourpos[ourcount] + 1,
 193                                           d_storage.c_str() + ourpos[ourcount] + 1 + *(d_storage.c_str() + ourpos[ourcount]),
 194                                           rhs.d_storage.c_str() + rhspos[rhscount] + 1,
 195                                           rhs.d_storage.c_str() + rhspos[rhscount] + 1 + *(rhs.d_storage.c_str() + rhspos[rhscount]),
 196                                           [](const unsigned char& a, const unsigned char& b) {
 197                                             return dns_tolower(a) < dns_tolower(b);
 198                                           });
 199
 200     //    cout<<"Forward: "<<res<<endl;
 201     if(res)
 202       return true;
 203
 204     res=std::lexicographical_compare(     rhs.d_storage.c_str() + rhspos[rhscount] + 1,
 205                                           rhs.d_storage.c_str() + rhspos[rhscount] + 1 + *(rhs.d_storage.c_str() + rhspos[rhscount]),
 206                                           d_storage.c_str() + ourpos[ourcount] + 1,
 207                                           d_storage.c_str() + ourpos[ourcount] + 1 + *(d_storage.c_str() + ourpos[ourcount]),
 208                                           [](const unsigned char& a, const unsigned char& b) {
 209                                             return dns_tolower(a) < dns_tolower(b);
 210                                           });
 211     //    cout<<"Reverse: "<<res<<endl;
 212     if(res)
 213       return false;
 214   }
 215   return false;
 216 }
 217
 218
 219 struct CanonDNSNameCompare: public std::binary_function<DNSName, DNSName, bool>
 220 {
 221   bool operator()(const DNSName&a, const DNSName& b) const
 222   {
 223     return a.canonCompare(b);
 224   }
 225 };
 226
 227 inline DNSName operator+(const DNSName& lhs, const DNSName& rhs)
 228 {
 229   DNSName ret=lhs;
 230   ret += rhs;
 231   return ret;
 232 }
 233
 234 template<typename T>
 235 struct SuffixMatchTree
 236 {
 237   SuffixMatchTree(const std::string& name="", bool endNode_=false) : d_name(name), endNode(endNode_)
 238   {}
 239
 240   SuffixMatchTree(const SuffixMatchTree& rhs): d_name(rhs.d_name), children(rhs.children), endNode(rhs.endNode)
 241   {
 242     if (endNode) {
 243       d_value = rhs.d_value;
 244     }
 245   }
 246   SuffixMatchTree & operator=(const SuffixMatchTree &rhs)
 247   {
 248     d_name = rhs.d_name;
 249     children = rhs.children;
 250     endNode = rhs.endNode;
 251     if (endNode) {
 252       d_value = rhs.d_value;
 253     }
 254     return *this;
 255   }
 256
 257   std::string d_name;
 258   mutable std::set<SuffixMatchTree> children;
 259   mutable bool endNode;
 260   mutable T d_value;
 261   bool operator<(const SuffixMatchTree& rhs) const
 262   {
 263     return strcasecmp(d_name.c_str(), rhs.d_name.c_str()) < 0;
 264   }
 265   typedef SuffixMatchTree value_type;
 266
 267   template<typename V>
 268   void visit(const V& v) const {
 269     for(const auto& c : children)
 270       c.visit(v);
 271     if(endNode)
 272       v(*this);
 273   }
 274
 275   void add(const DNSName& name, const T& t)
 276   {
 277     add(name.getRawLabels(), t);
 278   }
 279
 280   void add(std::vector<std::string> labels, const T& value) const
 281   {
 282     if(labels.empty()) { // this allows insertion of the root
 283       endNode=true;
 284       d_value=value;
 285     }
 286     else if(labels.size()==1) {
 287       auto res=children.emplace(*labels.begin(), true);
 288       if(!res.second) {
 289         // we might already have had the node as an
 290         // intermediary one, but it's now an end node
 291         if(!res.first->endNode) {
 292           res.first->endNode = true;
 293         }
 294       }
 295       res.first->d_value = value;
 296     }
 297     else {
 298       auto res=children.emplace(*labels.rbegin(), false);
 299       labels.pop_back();
 300       res.first->add(labels, value);
 301     }
 302   }
 303
 304   void remove(const DNSName &name) const
 305   {
 306     remove(name.getRawLabels());
 307   }
 308
 309   /* Removes the node at `labels`, also make sure that no empty
 310    * children will be left behind in memory
 311    */
 312   void remove(std::vector<std::string> labels) const
 313   {
 314     if (labels.empty()) { // this allows removal of the root
 315       endNode = false;
 316       return;
 317     }
 318
 319     SuffixMatchTree smt(*labels.rbegin());
 320     auto child = children.find(smt);
 321     if (child == children.end()) {
 322       // No subnode found, we're done
 323       return;
 324     }
 325
 326     // We have found a child
 327     labels.pop_back();
 328     if (labels.empty()) {
 329       // The child is no longer an endnode
 330       child->endNode = false;
 331
 332       // If the child has no further children, just remove it from the set.
 333       if (child->children.empty()) {
 334         children.erase(child);
 335       }
 336       return;
 337     }
 338
 339     // We are not at the end, let the child figure out what to do
 340     child->remove(labels);
 341   }
 342
 343   T* lookup(const DNSName& name)  const
 344   {
 345     if(children.empty()) { // speed up empty set
 346       if(endNode)
 347         return &d_value;
 348       return nullptr;
 349     }
 350
 351     return lookup(name.getRawLabels());
 352   }
 353
 354   T* lookup(std::vector<std::string> labels) const
 355   {
 356     if(labels.empty()) { // optimization
 357       if(endNode)
 358         return &d_value;
 359       return nullptr;
 360     }
 361
 362     SuffixMatchTree smn(*labels.rbegin());
 363     auto child = children.find(smn);
 364     if(child == children.end()) {
 365       if(endNode)
 366         return &d_value;
 367       return nullptr;
 368     }
 369     labels.pop_back();
 370     auto result = child->lookup(labels);
 371     if (result) {
 372       return result;
 373     }
 374     return endNode ? &d_value : nullptr;
 375   }
 376
 377   // Returns all end-nodes, fully qualified (not as separate labels)
 378   std::vector<DNSName> getNodes() const {
 379     std::vector<DNSName> ret;
 380     if (endNode) {
 381       ret.push_back(DNSName(d_name));
 382     }
 383     for (const auto& child : children) {
 384       auto nodes = child.getNodes();
 385       for (const auto &node: nodes) {
 386         ret.push_back(node + DNSName(d_name));
 387       }
 388     }
 389     return ret;
 390   }
 391 };
 392
 393 /* Quest in life: serve as a rapid block list. If you add a DNSName to a root SuffixMatchNode,
 394    anything part of that domain will return 'true' in check */
 395 struct SuffixMatchNode
 396 {
 397   public:
 398     SuffixMatchNode()
 399     {}
 400     SuffixMatchTree<bool> d_tree;
 401
 402     void add(const DNSName& dnsname)
 403     {
 404       d_tree.add(dnsname, true);
 405       d_nodes.insert(dnsname);
 406     }
 407
 408     void add(const std::string& name)
 409     {
 410       add(DNSName(name));
 411     }
 412
 413     void add(std::vector<std::string> labels)
 414     {
 415       d_tree.add(labels, true);
 416       DNSName tmp;
 417       while (!labels.empty()) {
 418         tmp.appendRawLabel(labels.back());
 419         labels.pop_back(); // This is safe because we have a copy of labels
 420       }
 421       d_nodes.insert(tmp);
 422     }
 423
 424     void remove(const DNSName& name)
 425     {
 426       d_tree.remove(name);
 427       d_nodes.erase(name);
 428     }
 429
 430     void remove(std::vector<std::string> labels)
 431     {
 432       d_tree.remove(labels);
 433       DNSName tmp;
 434       while (!labels.empty()) {
 435         tmp.appendRawLabel(labels.back());
 436         labels.pop_back(); // This is safe because we have a copy of labels
 437       }
 438       d_nodes.erase(tmp);
 439     }
 440
 441     bool check(const DNSName& dnsname) const
 442     {
 443       return d_tree.lookup(dnsname) != nullptr;
 444     }
 445
 446     std::string toString() const
 447     {
 448       std::string ret;
 449       bool first = true;
 450       for (const auto& n : d_nodes) {
 451         if (!first) {
 452           ret += ", ";
 453         }
 454         first = false;
 455         ret += n.toString();
 456       }
 457       return ret;
 458     }
 459
 460   private:
 461     mutable std::set<DNSName> d_nodes; // Only used for string generation
 462 };
 463
 464 std::ostream & operator<<(std::ostream &os, const DNSName& d);
 465 namespace std {
 466     template <>
 467     struct hash<DNSName> {
 468         size_t operator () (const DNSName& dn) const { return dn.hash(0); }
 469     };
 470 }
 471
 472 DNSName::string_t segmentDNSNameRaw(const char* input, size_t inputlen); // from ragel
 473 bool DNSName::operator==(const DNSName& rhs) const
 474 {
 475   if(rhs.empty() != empty() || rhs.d_storage.size() != d_storage.size())
 476     return false;
 477
 478   auto us = d_storage.cbegin();
 479   auto p = rhs.d_storage.cbegin();
 480   for(; us != d_storage.cend() && p != rhs.d_storage.cend(); ++us, ++p) {
 481     if(dns_tolower(*p) != dns_tolower(*us))
 482       return false;
 483   }
 484   return true;
 485 }
 486
 487 extern const DNSName g_rootdnsname, g_wildcarddnsname;
 488
 489 struct DNSNameSet: public std::unordered_set<DNSName> {
 490     std::string toString() const {
 491         std::ostringstream oss;
 492         std::copy(begin(), end(), std::ostream_iterator<DNSName>(oss, "\n"));
 493         return oss.str();
 494     }
 495 };