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 <array>
  24 #include <cstring>
  25 #include <optional>
  26 #include <string>
  27 #include <vector>
  28 #include <set>
  29 #include <strings.h>
  30 #include <stdexcept>
  31 #include <sstream>
  32 #include <iterator>
  33 #include <unordered_set>
  34 #include <string_view>
  35
  36 #include <boost/version.hpp>
  37
  38 #if BOOST_VERSION >= 105300
  39 #include <boost/container/string.hpp>
  40 #endif
  41
  42 inline bool dns_isspace(char c)
  43 {
  44   return c == ' ' || c == '\t' || c == '\r' || c == '\n';
  45 }
  46
  47 extern const unsigned char dns_toupper_table[256],  dns_tolower_table[256];
  48
  49 inline unsigned char dns_toupper(unsigned char c)
  50 {
  51   return dns_toupper_table[c];
  52 }
  53
  54 inline unsigned char dns_tolower(unsigned char c)
  55 {
  56   return dns_tolower_table[c];
  57 }
  58
  59 #include "burtle.hh"
  60 #include "views.hh"
  61
  62 // #include "dns.hh"
  63 // #include "logger.hh"
  64
  65 //#include <ext/vstring.h>
  66
  67 /* Quest in life:
  68      accept escaped ascii presentations of DNS names and store them "natively"
  69      accept a DNS packet with an offset, and extract a DNS name from it
  70      build up DNSNames with prepend and append of 'raw' unescaped labels
  71
  72    Be able to turn them into ASCII and "DNS name in a packet" again on request
  73
  74    Provide some common operators for comparison, detection of being part of another domain
  75
  76    NOTE: For now, everything MUST be . terminated, otherwise it is an error
  77 */
  78
  79 class DNSName
  80 {
  81 public:
  82   static const size_t s_maxDNSNameLength = 255;
  83
  84   DNSName() = default; //!< Constructs an *empty* DNSName, NOT the root!
  85   // Work around assertion in some boost versions that do not like self-assignment of boost::container::string
  86   DNSName& operator=(const DNSName& rhs)
  87   {
  88     if (this != &rhs) {
  89       d_storage = rhs.d_storage;
  90     }
  91     return *this;
  92   }
  93   DNSName& operator=(DNSName&& rhs) noexcept
  94   {
  95     if (this != &rhs) {
  96       d_storage = std::move(rhs.d_storage);
  97     }
  98     return *this;
  99   }
 100   DNSName(const DNSName& a) = default;
 101   DNSName(DNSName&& a) = default;
 102
 103   explicit DNSName(std::string_view sw); //!< Constructs from a human formatted, escaped presentation
 104   DNSName(const char* p, size_t len, size_t 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.
 105
 106   bool isPartOf(const DNSName& rhs) const;   //!< Are we part of the rhs name? Note that name.isPartOf(name).
 107   inline bool operator==(const DNSName& rhs) const; //!< DNS-native comparison (case insensitive) - empty compares to empty
 108   bool operator!=(const DNSName& other) const { return !(*this == other); }
 109
 110   std::string toString(const std::string& separator=".", const bool trailing=true) const;              //!< Our human-friendly, escaped, representation
 111   void toString(std::string& output, const std::string& separator=".", const bool trailing=true) const;
 112   std::string toLogString() const; //!< like plain toString, but returns (empty) on empty names
 113   std::string toStringNoDot() const { return toString(".", false); }
 114   std::string toStringRootDot() const { if(isRoot()) return "."; else return toString(".", false); }
 115   std::string toDNSString() const;           //!< Our representation in DNS native format
 116   std::string toDNSStringLC() const;           //!< Our representation in DNS native format, lower cased
 117   void appendRawLabel(const std::string& str); //!< Append this unescaped label
 118   void appendRawLabel(const char* start, unsigned int length); //!< Append this unescaped label
 119   void prependRawLabel(const std::string& str); //!< Prepend this unescaped label
 120   std::vector<std::string> getRawLabels() const; //!< Individual raw unescaped labels
 121   std::string getRawLabel(unsigned int pos) const; //!< Get the specified raw unescaped label
 122   DNSName getLastLabel() const; //!< Get the DNSName of the last label
 123   bool chopOff();                               //!< Turn www.powerdns.com. into powerdns.com., returns false for .
 124   DNSName makeRelative(const DNSName& zone) const;
 125   DNSName makeLowerCase() const
 126   {
 127     DNSName ret(*this);
 128     ret.makeUsLowerCase();
 129     return ret;
 130   }
 131   void makeUsLowerCase()
 132   {
 133     for(auto & c : d_storage) {
 134       c=dns_tolower(c);
 135     }
 136   }
 137   void makeUsRelative(const DNSName& zone);
 138   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'
 139   DNSName labelReverse() const;
 140   bool isWildcard() const;
 141   bool isHostname() const;
 142   unsigned int countLabels() const;
 143   size_t wirelength() const; //!< Number of total bytes in the name
 144   bool empty() const { return d_storage.empty(); }
 145   bool isRoot() const { return d_storage.size()==1 && d_storage[0]==0; }
 146   void clear() { d_storage.clear(); }
 147   void trimToLabels(unsigned int);
 148   size_t hash(size_t init=0) const
 149   {
 150     return burtleCI((const unsigned char*)d_storage.c_str(), d_storage.size(), init);
 151   }
 152   DNSName& operator+=(const DNSName& rhs)
 153   {
 154     if(d_storage.size() + rhs.d_storage.size() > s_maxDNSNameLength + 1) // one extra byte for the second root label
 155       throwSafeRangeError("resulting name too long", rhs.d_storage.data(), rhs.d_storage.size());
 156     if(rhs.empty())
 157       return *this;
 158
 159     if(d_storage.empty())
 160       d_storage+=rhs.d_storage;
 161     else
 162       d_storage.replace(d_storage.length()-1, rhs.d_storage.length(), rhs.d_storage);
 163
 164     return *this;
 165   }
 166
 167   bool operator<(const DNSName& rhs)  const // this delivers _some_ kind of ordering, but not one useful in a DNS context. Really fast though.
 168   {
 169     return std::lexicographical_compare(d_storage.rbegin(), d_storage.rend(),
 170                                  rhs.d_storage.rbegin(), rhs.d_storage.rend(),
 171                                  [](const unsigned char& a, const unsigned char& b) {
 172                                           return dns_tolower(a) < dns_tolower(b);
 173                                         }); // note that this is case insensitive, including on the label lengths
 174   }
 175
 176   inline bool canonCompare(const DNSName& rhs) const;
 177   bool slowCanonCompare(const DNSName& rhs) const;
 178
 179 #if BOOST_VERSION >= 105300
 180   typedef boost::container::string string_t;
 181 #else
 182   typedef std::string string_t;
 183 #endif
 184   const string_t& getStorage() const {
 185     return d_storage;
 186   }
 187
 188   bool has8bitBytes() const; /* returns true if at least one byte of the labels forming the name is not included in [A-Za-z0-9_*./@ \\:-] */
 189
 190   class RawLabelsVisitor
 191   {
 192   public:
 193     /* Zero-copy, zero-allocation raw labels visitor.
 194        The general idea is that we walk the labels in the constructor,
 195        filling up our array of labels position and setting the initial
 196        value of d_position at the number of labels.
 197        We then can easily provide string_view into the first and last label.
 198        pop_back() moves d_position one label closer to the start, so we
 199        can also easily walk back the labels in reverse order.
 200        There is no copy because we use a reference into the DNSName storage,
 201        so it is absolutely forbidden to alter the DNSName for as long as we
 202        exist, and no allocation because we use a static array (there cannot
 203        be more than 128 labels in a DNSName).
 204     */
 205     RawLabelsVisitor(const string_t& storage);
 206     std::string_view front() const;
 207     std::string_view back() const;
 208     bool pop_back();
 209     bool empty() const;
 210   private:
 211     std::array<uint8_t, 128> d_labelPositions;
 212     const string_t& d_storage;
 213     size_t d_position{0};
 214   };
 215   RawLabelsVisitor getRawLabelsVisitor() const;
 216
 217 private:
 218   string_t d_storage;
 219
 220   void packetParser(const char* qpos, size_t len, size_t offset, bool uncompress, uint16_t* qtype, uint16_t* qclass, unsigned int* consumed, int depth, uint16_t minOffset);
 221   size_t parsePacketUncompressed(const pdns::views::UnsignedCharView& view, size_t position, bool uncompress);
 222   static void appendEscapedLabel(std::string& appendTo, const char* orig, size_t len);
 223   static std::string unescapeLabel(const std::string& orig);
 224   static void throwSafeRangeError(const std::string& msg, const char* buf, size_t length);
 225 };
 226
 227 size_t hash_value(DNSName const& d);
 228
 229
 230 inline bool DNSName::canonCompare(const DNSName& rhs) const
 231 {
 232   //      01234567890abcd
 233   // us:  1a3www4ds9a2nl
 234   // rhs: 3www6online3com
 235   // to compare, we start at the back, is nl < com? no -> done
 236   //
 237   // 0,2,6,a
 238   // 0,4,a
 239
 240   uint8_t ourpos[64], rhspos[64];
 241   uint8_t ourcount=0, rhscount=0;
 242   //cout<<"Asked to compare "<<toString()<<" to "<<rhs.toString()<<endl;
 243   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)
 244     ourpos[ourcount++]=(p-(const unsigned char*)d_storage.c_str());
 245   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)
 246     rhspos[rhscount++]=(p-(const unsigned char*)rhs.d_storage.c_str());
 247
 248   if(ourcount == sizeof(ourpos) || rhscount==sizeof(rhspos)) {
 249     return slowCanonCompare(rhs);
 250   }
 251
 252   for(;;) {
 253     if(ourcount == 0 && rhscount != 0)
 254       return true;
 255     if(rhscount == 0)
 256       return false;
 257     ourcount--;
 258     rhscount--;
 259
 260     bool res=std::lexicographical_compare(
 261                                           d_storage.c_str() + ourpos[ourcount] + 1,
 262                                           d_storage.c_str() + ourpos[ourcount] + 1 + *(d_storage.c_str() + ourpos[ourcount]),
 263                                           rhs.d_storage.c_str() + rhspos[rhscount] + 1,
 264                                           rhs.d_storage.c_str() + rhspos[rhscount] + 1 + *(rhs.d_storage.c_str() + rhspos[rhscount]),
 265                                           [](const unsigned char& a, const unsigned char& b) {
 266                                             return dns_tolower(a) < dns_tolower(b);
 267                                           });
 268
 269     //    cout<<"Forward: "<<res<<endl;
 270     if(res)
 271       return true;
 272
 273     res=std::lexicographical_compare(     rhs.d_storage.c_str() + rhspos[rhscount] + 1,
 274                                           rhs.d_storage.c_str() + rhspos[rhscount] + 1 + *(rhs.d_storage.c_str() + rhspos[rhscount]),
 275                                           d_storage.c_str() + ourpos[ourcount] + 1,
 276                                           d_storage.c_str() + ourpos[ourcount] + 1 + *(d_storage.c_str() + ourpos[ourcount]),
 277                                           [](const unsigned char& a, const unsigned char& b) {
 278                                             return dns_tolower(a) < dns_tolower(b);
 279                                           });
 280     //    cout<<"Reverse: "<<res<<endl;
 281     if(res)
 282       return false;
 283   }
 284   return false;
 285 }
 286
 287
 288 struct CanonDNSNameCompare
 289 {
 290   bool operator()(const DNSName&a, const DNSName& b) const
 291   {
 292     return a.canonCompare(b);
 293   }
 294 };
 295
 296 inline DNSName operator+(const DNSName& lhs, const DNSName& rhs)
 297 {
 298   DNSName ret=lhs;
 299   ret += rhs;
 300   return ret;
 301 }
 302
 303 extern const DNSName g_rootdnsname, g_wildcarddnsname;
 304
 305 template<typename T>
 306 struct SuffixMatchTree
 307 {
 308   SuffixMatchTree(const std::string& name="", bool endNode_=false) : d_name(name), endNode(endNode_)
 309   {}
 310
 311   SuffixMatchTree(const SuffixMatchTree& rhs): d_name(rhs.d_name), children(rhs.children), endNode(rhs.endNode)
 312   {
 313     if (endNode) {
 314       d_value = rhs.d_value;
 315     }
 316   }
 317   SuffixMatchTree & operator=(const SuffixMatchTree &rhs)
 318   {
 319     d_name = rhs.d_name;
 320     children = rhs.children;
 321     endNode = rhs.endNode;
 322     if (endNode) {
 323       d_value = rhs.d_value;
 324     }
 325     return *this;
 326   }
 327   bool operator<(const SuffixMatchTree& rhs) const
 328   {
 329     return strcasecmp(d_name.c_str(), rhs.d_name.c_str()) < 0;
 330   }
 331
 332   std::string d_name;
 333   mutable std::set<SuffixMatchTree, std::less<>> children;
 334   mutable bool endNode;
 335   mutable T d_value;
 336
 337   /* this structure is used to do a lookup without allocating and
 338      copying a string, using C++14's heterogeneous lookups in ordered
 339      containers */
 340   struct LightKey
 341   {
 342     std::string_view d_name;
 343     bool operator<(const SuffixMatchTree& smt) const
 344     {
 345       auto compareUpTo = std::min(this->d_name.size(), smt.d_name.size());
 346       auto ret = strncasecmp(this->d_name.data(), smt.d_name.data(), compareUpTo);
 347       if (ret != 0) {
 348         return ret < 0;
 349       }
 350       if (this->d_name.size() == smt.d_name.size()) {
 351         return ret < 0;
 352       }
 353       return this->d_name.size() < smt.d_name.size();
 354     }
 355   };
 356
 357   bool operator<(const LightKey& lk) const
 358   {
 359     auto compareUpTo = std::min(this->d_name.size(), lk.d_name.size());
 360     auto ret = strncasecmp(this->d_name.data(), lk.d_name.data(), compareUpTo);
 361     if (ret != 0) {
 362       return ret < 0;
 363     }
 364     if (this->d_name.size() == lk.d_name.size()) {
 365       return ret < 0;
 366     }
 367     return this->d_name.size() < lk.d_name.size();
 368   }
 369
 370   template<typename V>
 371   void visit(const V& v) const {
 372     for(const auto& c : children) {
 373       c.visit(v);
 374     }
 375
 376     if (endNode) {
 377       v(*this);
 378     }
 379   }
 380
 381   void add(const DNSName& name, T&& t)
 382   {
 383     auto labels = name.getRawLabels();
 384     add(labels, std::move(t));
 385   }
 386
 387   void add(std::vector<std::string>& labels, T&& value) const
 388   {
 389     if (labels.empty()) { // this allows insertion of the root
 390       endNode = true;
 391       d_value = std::move(value);
 392     }
 393     else if(labels.size()==1) {
 394       auto res = children.emplace(*labels.begin(), true);
 395       if (!res.second) {
 396         // we might already have had the node as an
 397         // intermediary one, but it's now an end node
 398         if (!res.first->endNode) {
 399           res.first->endNode = true;
 400         }
 401       }
 402       res.first->d_value = std::move(value);
 403     }
 404     else {
 405       auto res = children.emplace(*labels.rbegin(), false);
 406       labels.pop_back();
 407       res.first->add(labels, std::move(value));
 408     }
 409   }
 410
 411   void remove(const DNSName &name, bool subtree=false) const
 412   {
 413     auto labels = name.getRawLabels();
 414     remove(labels, subtree);
 415   }
 416
 417   /* Removes the node at `labels`, also make sure that no empty
 418    * children will be left behind in memory
 419    */
 420   void remove(std::vector<std::string>& labels, bool subtree = false) const
 421   {
 422     if (labels.empty()) { // this allows removal of the root
 423       endNode = false;
 424       if (subtree) {
 425         children.clear();
 426       }
 427       return;
 428     }
 429
 430     SuffixMatchTree smt(*labels.rbegin());
 431     auto child = children.find(smt);
 432     if (child == children.end()) {
 433       // No subnode found, we're done
 434       return;
 435     }
 436
 437     // We have found a child
 438     labels.pop_back();
 439     if (labels.empty()) {
 440       // The child is no longer an endnode
 441       child->endNode = false;
 442
 443       if (subtree) {
 444         child->children.clear();
 445       }
 446
 447       // If the child has no further children, just remove it from the set.
 448       if (child->children.empty()) {
 449         children.erase(child);
 450       }
 451       return;
 452     }
 453
 454     // We are not at the end, let the child figure out what to do
 455     child->remove(labels);
 456   }
 457
 458   T* lookup(const DNSName& name) const
 459   {
 460     auto bestNode = getBestNode(name);
 461     if (bestNode) {
 462       return &bestNode->d_value;
 463     }
 464     return nullptr;
 465   }
 466
 467   std::optional<DNSName> getBestMatch(const DNSName& name) const
 468   {
 469     if (children.empty()) { // speed up empty set
 470       return endNode ? std::optional<DNSName>(g_rootdnsname) : std::nullopt;
 471     }
 472
 473     auto visitor = name.getRawLabelsVisitor();
 474     return getBestMatch(visitor);
 475   }
 476
 477   // Returns all end-nodes, fully qualified (not as separate labels)
 478   std::vector<DNSName> getNodes() const {
 479     std::vector<DNSName> ret;
 480     if (endNode) {
 481       ret.push_back(DNSName(d_name));
 482     }
 483     for (const auto& child : children) {
 484       auto nodes = child.getNodes();
 485       ret.reserve(ret.size() + nodes.size());
 486       for (const auto &node: nodes) {
 487         ret.push_back(node + DNSName(d_name));
 488       }
 489     }
 490     return ret;
 491   }
 492
 493 private:
 494   const SuffixMatchTree* getBestNode(const DNSName& name)  const
 495   {
 496     if (children.empty()) { // speed up empty set
 497       if (endNode) {
 498         return this;
 499       }
 500       return nullptr;
 501     }
 502
 503     auto visitor = name.getRawLabelsVisitor();
 504     return getBestNode(visitor);
 505   }
 506
 507   const SuffixMatchTree* getBestNode(DNSName::RawLabelsVisitor& visitor) const
 508   {
 509     if (visitor.empty()) { // optimization
 510       if (endNode) {
 511         return this;
 512       }
 513       return nullptr;
 514     }
 515
 516     const LightKey lk{visitor.back()};
 517     auto child = children.find(lk);
 518     if (child == children.end()) {
 519       if (endNode) {
 520         return this;
 521       }
 522       return nullptr;
 523     }
 524     visitor.pop_back();
 525     auto result = child->getBestNode(visitor);
 526     if (result) {
 527       return result;
 528     }
 529     return endNode ? this : nullptr;
 530   }
 531
 532   std::optional<DNSName> getBestMatch(DNSName::RawLabelsVisitor& visitor) const
 533   {
 534     if (visitor.empty()) { // optimization
 535       if (endNode) {
 536         return std::optional<DNSName>(d_name);
 537       }
 538       return std::nullopt;
 539     }
 540
 541     const LightKey lk{visitor.back()};
 542     auto child = children.find(lk);
 543     if (child == children.end()) {
 544       if (endNode) {
 545         return std::optional<DNSName>(d_name);
 546       }
 547       return std::nullopt;
 548     }
 549     visitor.pop_back();
 550     auto result = child->getBestMatch(visitor);
 551     if (result) {
 552       if (!d_name.empty()) {
 553         result->appendRawLabel(d_name);
 554       }
 555       return result;
 556     }
 557     return endNode ? std::optional<DNSName>(d_name) : std::nullopt;
 558   }
 559 };
 560
 561 /* Quest in life: serve as a rapid block list. If you add a DNSName to a root SuffixMatchNode,
 562    anything part of that domain will return 'true' in check */
 563 struct SuffixMatchNode
 564 {
 565   public:
 566     SuffixMatchNode() = default;
 567     SuffixMatchTree<bool> d_tree;
 568
 569     void add(const DNSName& dnsname)
 570     {
 571       d_tree.add(dnsname, true);
 572       d_nodes.insert(dnsname);
 573     }
 574
 575     void add(const std::string& name)
 576     {
 577       add(DNSName(name));
 578     }
 579
 580     void add(std::vector<std::string> labels)
 581     {
 582       d_tree.add(labels, true);
 583       DNSName tmp;
 584       while (!labels.empty()) {
 585         tmp.appendRawLabel(labels.back());
 586         labels.pop_back(); // This is safe because we have a copy of labels
 587       }
 588       d_nodes.insert(tmp);
 589     }
 590
 591     void remove(const DNSName& name)
 592     {
 593       d_tree.remove(name);
 594       d_nodes.erase(name);
 595     }
 596
 597     void remove(std::vector<std::string> labels)
 598     {
 599       d_tree.remove(labels);
 600       DNSName tmp;
 601       while (!labels.empty()) {
 602         tmp.appendRawLabel(labels.back());
 603         labels.pop_back(); // This is safe because we have a copy of labels
 604       }
 605       d_nodes.erase(tmp);
 606     }
 607
 608     bool check(const DNSName& dnsname) const
 609     {
 610       return d_tree.lookup(dnsname) != nullptr;
 611     }
 612
 613     std::optional<DNSName> getBestMatch(const DNSName& name) const
 614     {
 615       return d_tree.getBestMatch(name);
 616     }
 617
 618     std::string toString() const
 619     {
 620       std::string ret;
 621       bool first = true;
 622       for (const auto& n : d_nodes) {
 623         if (!first) {
 624           ret += ", ";
 625         }
 626         first = false;
 627         ret += n.toString();
 628       }
 629       return ret;
 630     }
 631
 632   private:
 633     mutable std::set<DNSName> d_nodes; // Only used for string generation
 634 };
 635
 636 std::ostream & operator<<(std::ostream &os, const DNSName& d);
 637 namespace std {
 638     template <>
 639     struct hash<DNSName> {
 640         size_t operator () (const DNSName& dn) const { return dn.hash(0); }
 641     };
 642 }
 643
 644 DNSName::string_t segmentDNSNameRaw(const char* input, size_t inputlen); // from ragel
 645
 646 bool DNSName::operator==(const DNSName& rhs) const
 647 {
 648   if (rhs.empty() != empty() || rhs.d_storage.size() != d_storage.size()) {
 649     return false;
 650   }
 651
 652   const auto* us = d_storage.cbegin();
 653   const auto* p = rhs.d_storage.cbegin();
 654   for (; us != d_storage.cend() && p != rhs.d_storage.cend(); ++us, ++p) {
 655     if (dns_tolower(*p) != dns_tolower(*us)) {
 656       return false;
 657     }
 658   }
 659   return true;
 660 }
 661
 662 struct DNSNameSet: public std::unordered_set<DNSName> {
 663     std::string toString() const {
 664         std::ostringstream oss;
 665         std::copy(begin(), end(), std::ostream_iterator<DNSName>(oss, "\n"));
 666         return oss.str();
 667     }
 668 };