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   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 };