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 std::string escapeLabel(const std::string& orig);
 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   T* lookup(const DNSName& name)  const
 293   {
 294     if(children.empty()) { // speed up empty set
 295       if(endNode)
 296         return &d_value;
 297       return 0;
 298     }
 299     return lookup(name.getRawLabels());
 300   }
 301
 302   T* lookup(std::vector<std::string> labels) const
 303   {
 304     if(labels.empty()) { // optimization
 305       if(endNode)
 306         return &d_value;
 307       return 0;
 308     }
 309
 310     SuffixMatchTree smn(*labels.rbegin());
 311     auto child = children.find(smn);
 312     if(child == children.end()) {
 313       if(endNode)
 314         return &d_value;
 315       return 0;
 316     }
 317     labels.pop_back();
 318     return child->lookup(labels);
 319   }
 320
 321 };
 322
 323 /* Quest in life: serve as a rapid block list. If you add a DNSName to a root SuffixMatchNode,
 324    anything part of that domain will return 'true' in check */
 325 struct SuffixMatchNode
 326 {
 327   SuffixMatchNode()
 328   {}
 329   std::string d_human;
 330   SuffixMatchTree<bool> d_tree;
 331
 332   void add(const DNSName& dnsname)
 333   {
 334     if(!d_human.empty())
 335       d_human.append(", ");
 336     d_human += dnsname.toString();
 337
 338     d_tree.add(dnsname, true);
 339   }
 340
 341   void add(std::vector<std::string> labels)
 342   {
 343     d_tree.add(labels, true);
 344   }
 345
 346   bool check(const DNSName& dnsname) const
 347   {
 348     return d_tree.lookup(dnsname) != nullptr;
 349   }
 350
 351   std::string toString() const
 352   {
 353     return d_human;
 354   }
 355
 356 };
 357
 358 std::ostream & operator<<(std::ostream &os, const DNSName& d);
 359 namespace std {
 360     template <>
 361     struct hash<DNSName> {
 362         size_t operator () (const DNSName& dn) const { return dn.hash(0); }
 363     };
 364 }
 365
 366 DNSName::string_t segmentDNSNameRaw(const char* input); // from ragel
 367 bool DNSName::operator==(const DNSName& rhs) const
 368 {
 369   if(rhs.empty() != empty() || rhs.d_storage.size() != d_storage.size())
 370     return false;
 371
 372   auto us = d_storage.cbegin();
 373   auto p = rhs.d_storage.cbegin();
 374   for(; us != d_storage.cend() && p != rhs.d_storage.cend(); ++us, ++p) {
 375     if(dns_tolower(*p) != dns_tolower(*us))
 376       return false;
 377   }
 378   return true;
 379 }
 380
 381 extern const DNSName g_rootdnsname, g_wildcarddnsname;
 382
 383 struct DNSNameSet: public std::unordered_set<DNSName> {
 384     std::string toString() const {
 385         std::ostringstream oss;
 386         std::copy(begin(), end(), std::ostream_iterator<DNSName>(oss, "\n"));
 387         return oss.str();
 388     }
 389 };