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=0, uint16_t* qclass=0, unsigned int* consumed=0, uint16_t minOffset=0); //!< Construct from a DNS Packet, taking the first question if offset=12
  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   std::string d_name;
 246   mutable std::set<SuffixMatchTree> children;
 247   mutable bool endNode;
 248   mutable T d_value;
 249   bool operator<(const SuffixMatchTree& rhs) const
 250   {
 251     return strcasecmp(d_name.c_str(), rhs.d_name.c_str()) < 0;
 252   }
 253   typedef SuffixMatchTree value_type;
 254
 255   template<typename V>
 256   void visit(const V& v) const {
 257     for(const auto& c : children)
 258       c.visit(v);
 259     if(endNode)
 260       v(*this);
 261   }
 262
 263   void add(const DNSName& name, const T& t)
 264   {
 265     add(name.getRawLabels(), t);
 266   }
 267
 268   void add(std::vector<std::string> labels, const T& value) const
 269   {
 270     if(labels.empty()) { // this allows insertion of the root
 271       endNode=true;
 272       d_value=value;
 273     }
 274     else if(labels.size()==1) {
 275       auto res=children.emplace(*labels.begin(), true);
 276       if(!res.second) {
 277         // we might already have had the node as an
 278         // intermediary one, but it's now an end node
 279         if(!res.first->endNode) {
 280           res.first->endNode = true;
 281         }
 282       }
 283       res.first->d_value = value;
 284     }
 285     else {
 286       auto res=children.emplace(*labels.rbegin(), false);
 287       labels.pop_back();
 288       res.first->add(labels, value);
 289     }
 290   }
 291
 292   void remove(const DNSName &name) const
 293   {
 294     remove(name.getRawLabels());
 295   }
 296
 297   /* Removes the node at `labels`, also make sure that no empty
 298    * children will be left behind in memory
 299    */
 300   void remove(std::vector<std::string> labels) const
 301   {
 302     if (labels.empty()) { // this allows removal of the root
 303       endNode = false;
 304       return;
 305     }
 306
 307     SuffixMatchTree smt(*labels.rbegin());
 308     auto child = children.find(smt);
 309     if (child == children.end()) {
 310       // No subnode found, we're done
 311       return;
 312     }
 313
 314     // We have found a child
 315     labels.pop_back();
 316     if (labels.empty()) {
 317       // The child is no longer an endnode
 318       child->endNode = false;
 319
 320       // If the child has no further children, just remove it from the set.
 321       if (child->children.empty()) {
 322         children.erase(child);
 323       }
 324       return;
 325     }
 326
 327     // We are not at the end, let the child figure out what to do
 328     child->remove(labels);
 329   }
 330
 331   T* lookup(const DNSName& name)  const
 332   {
 333     if(children.empty()) { // speed up empty set
 334       if(endNode)
 335         return &d_value;
 336       return nullptr;
 337     }
 338
 339     return lookup(name.getRawLabels());
 340   }
 341
 342   T* lookup(std::vector<std::string> labels) const
 343   {
 344     if(labels.empty()) { // optimization
 345       if(endNode)
 346         return &d_value;
 347       return nullptr;
 348     }
 349
 350     SuffixMatchTree smn(*labels.rbegin());
 351     auto child = children.find(smn);
 352     if(child == children.end()) {
 353       if(endNode)
 354         return &d_value;
 355       return nullptr;
 356     }
 357     labels.pop_back();
 358     auto result = child->lookup(labels);
 359     if (result) {
 360       return result;
 361     }
 362     return endNode ? &d_value : nullptr;
 363   }
 364
 365   // Returns all end-nodes, fully qualified (not as separate labels)
 366   std::vector<DNSName> getNodes() const {
 367     std::vector<DNSName> ret;
 368     if (endNode) {
 369       ret.push_back(DNSName(d_name));
 370     }
 371     for (const auto& child : children) {
 372       auto nodes = child.getNodes();
 373       for (const auto &node: nodes) {
 374         ret.push_back(node + DNSName(d_name));
 375       }
 376     }
 377     return ret;
 378   }
 379 };
 380
 381 /* Quest in life: serve as a rapid block list. If you add a DNSName to a root SuffixMatchNode,
 382    anything part of that domain will return 'true' in check */
 383 struct SuffixMatchNode
 384 {
 385   public:
 386     SuffixMatchNode()
 387     {}
 388     SuffixMatchTree<bool> d_tree;
 389
 390     void add(const DNSName& dnsname)
 391     {
 392       d_tree.add(dnsname, true);
 393       d_nodes.insert(dnsname);
 394     }
 395
 396     void add(const std::string& name)
 397     {
 398       add(DNSName(name));
 399     }
 400
 401     void add(std::vector<std::string> labels)
 402     {
 403       d_tree.add(labels, true);
 404       DNSName tmp;
 405       while (!labels.empty()) {
 406         tmp.appendRawLabel(labels.back());
 407         labels.pop_back(); // This is safe because we have a copy of labels
 408       }
 409       d_nodes.insert(tmp);
 410     }
 411
 412     void remove(const DNSName& name)
 413     {
 414       d_tree.remove(name);
 415       d_nodes.erase(name);
 416     }
 417
 418     void remove(std::vector<std::string> labels)
 419     {
 420       d_tree.remove(labels);
 421       DNSName tmp;
 422       while (!labels.empty()) {
 423         tmp.appendRawLabel(labels.back());
 424         labels.pop_back(); // This is safe because we have a copy of labels
 425       }
 426       d_nodes.erase(tmp);
 427     }
 428
 429     bool check(const DNSName& dnsname) const
 430     {
 431       return d_tree.lookup(dnsname) != nullptr;
 432     }
 433
 434     std::string toString() const
 435     {
 436       std::string ret;
 437       bool first = true;
 438       for (const auto& n : d_nodes) {
 439         if (!first) {
 440           ret += ", ";
 441         }
 442         first = false;
 443         ret += n.toString();
 444       }
 445       return ret;
 446     }
 447
 448   private:
 449     mutable std::set<DNSName> d_nodes; // Only used for string generation
 450 };
 451
 452 std::ostream & operator<<(std::ostream &os, const DNSName& d);
 453 namespace std {
 454     template <>
 455     struct hash<DNSName> {
 456         size_t operator () (const DNSName& dn) const { return dn.hash(0); }
 457     };
 458 }
 459
 460 DNSName::string_t segmentDNSNameRaw(const char* input); // from ragel
 461 bool DNSName::operator==(const DNSName& rhs) const
 462 {
 463   if(rhs.empty() != empty() || rhs.d_storage.size() != d_storage.size())
 464     return false;
 465
 466   auto us = d_storage.cbegin();
 467   auto p = rhs.d_storage.cbegin();
 468   for(; us != d_storage.cend() && p != rhs.d_storage.cend(); ++us, ++p) {
 469     if(dns_tolower(*p) != dns_tolower(*us))
 470       return false;
 471   }
 472   return true;
 473 }
 474
 475 extern const DNSName g_rootdnsname, g_wildcarddnsname;
 476
 477 struct DNSNameSet: public std::unordered_set<DNSName> {
 478     std::string toString() const {
 479         std::ostringstream oss;
 480         std::copy(begin(), end(), std::ostream_iterator<DNSName>(oss, "\n"));
 481         return oss.str();
 482     }
 483 };