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