pdns/dnsname.hh

   1 #pragma once
   2 #include <string>
   3 #include <vector>
   4 #include <set>
   5 #include <deque>
   6 #include <strings.h>
   7 #include <stdexcept>
   8
   9 uint32_t burtleCI(const unsigned char* k, uint32_t lengh, uint32_t init);
  10
  11 // #include "dns.hh"
  12 // #include "logger.hh"
  13
  14 //#include <ext/vstring.h>
  15
  16 /* Quest in life:
  17      accept escaped ascii presentations of DNS names and store them "natively"
  18      accept a DNS packet with an offset, and extract a DNS name from it
  19      build up DNSNames with prepend and append of 'raw' unescaped labels
  20
  21    Be able to turn them into ASCII and "DNS name in a packet" again on request
  22
  23    Provide some common operators for comparison, detection of being part of another domain
  24
  25    NOTE: For now, everything MUST be . terminated, otherwise it is an error
  26 */
  27
  28
  29 class DNSName
  30 {
  31 public:
  32   DNSName()  {}          //!< Constructs an *empty* DNSName, NOT the root!
  33   explicit DNSName(const char* p);      //!< Constructs from a human formatted, escaped presentation
  34   explicit DNSName(const std::string& str) : DNSName(str.c_str()) {}   //!< Constructs from a human formatted, escaped presentation
  35   DNSName(const char* p, int len, int offset, bool uncompress, uint16_t* qtype=0, uint16_t* qclass=0, unsigned int* consumed=0); //!< Construct from a DNS Packet, taking the first question if offset=12
  36
  37   bool isPartOf(const DNSName& rhs) const;   //!< Are we part of the rhs name?
  38   bool operator==(const DNSName& rhs) const; //!< DNS-native comparison (case insensitive) - empty compares to empty
  39   bool operator!=(const DNSName& other) const { return !(*this == other); }
  40
  41   std::string toString(const std::string& separator=".", const bool trailing=true) const;              //!< Our human-friendly, escaped, representation
  42   std::string toStringNoDot() const { return toString(".", false); }
  43   std::string toDNSString() const;           //!< Our representation in DNS native format
  44   void appendRawLabel(const std::string& str); //!< Append this unescaped label
  45   void prependRawLabel(const std::string& str); //!< Prepend this unescaped label
  46   std::vector<std::string> getRawLabels() const; //!< Individual raw unescaped labels
  47   bool chopOff();                               //!< Turn www.powerdns.com. into powerdns.com., returns false for .
  48   DNSName makeRelative(const DNSName& zone) const;
  49   void makeUsRelative(const DNSName& zone);
  50   DNSName labelReverse() const;
  51   bool isWildcard() const;
  52   unsigned int countLabels() const;
  53   size_t wirelength() const; //!< Number of total bytes in the name
  54   bool empty() const { return d_storage.empty(); }
  55   bool isRoot() const { return d_storage.size()==1 && d_storage[0]==0; }
  56   void clear() { d_storage.clear(); }
  57   void trimToLabels(unsigned int);
  58   size_t hash() const
  59   {
  60     return burtleCI((const unsigned char*)d_storage.c_str(), d_storage.size(), 0);
  61   }
  62   DNSName& operator+=(const DNSName& rhs)
  63   {
  64     if(d_storage.size() + rhs.d_storage.size() > 256) // reserve one byte for the root label
  65       throw std::range_error("name too long");
  66     if(rhs.empty())
  67       return *this;
  68
  69     if(d_storage.empty())
  70       d_storage+=rhs.d_storage;
  71     else
  72       d_storage.replace(d_storage.length()-1, rhs.d_storage.length(), rhs.d_storage);
  73
  74     return *this;
  75   }
  76
  77   bool operator<(const DNSName& rhs)  const // this delivers _some_ kind of ordering, but not one useful in a DNS context. Really fast though.
  78   {
  79     return std::lexicographical_compare(d_storage.rbegin(), d_storage.rend(),
  80                                  rhs.d_storage.rbegin(), rhs.d_storage.rend(),
  81                                  [](const char& a, const char& b) {
  82                                           return tolower(a) < tolower(b);
  83                                         }); // note that this is case insensitive, including on the label lengths
  84   }
  85
  86   template<class Archive>
  87   void serialize(Archive &ar, const unsigned int version)
  88   {
  89     ar & d_storage;
  90   }
  91
  92   inline bool canonCompare(const DNSName& rhs) const;
  93   bool slowCanonCompare(const DNSName& rhs) const;
  94 private:
  95   //typedef __gnu_cxx::__sso_string string_t;
  96   typedef std::string string_t;
  97
  98   string_t d_storage;
  99
 100   void packetParser(const char* p, int len, int offset, bool uncompress, uint16_t* qtype=0, uint16_t* qclass=0, unsigned int* consumed=0, int depth=0);
 101   static std::string escapeLabel(const std::string& orig);
 102   static std::string unescapeLabel(const std::string& orig);
 103 };
 104
 105 size_t hash_value(DNSName const& d);
 106
 107 inline char dns2_tolower(char c)
 108 {
 109   if(c>='A' && c<='Z')
 110     c+='a'-'A';
 111   return c;
 112 }
 113
 114
 115 inline bool DNSName::canonCompare(const DNSName& rhs) const
 116 {
 117   //      01234567890abcd
 118   // us:  1a3www4ds9a2nl
 119   // rhs: 3www6online3com
 120   // to compare, we start at the back, is nl < com? no -> done
 121   //
 122   // 0,2,6,a
 123   // 0,4,a
 124
 125   uint8_t ourpos[64], rhspos[64];
 126   uint8_t ourcount=0, rhscount=0;
 127   //cout<<"Asked to compare "<<toString()<<" to "<<rhs.toString()<<endl;
 128   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)
 129     ourpos[ourcount++]=(p-(const unsigned char*)d_storage.c_str());
 130   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)
 131     rhspos[rhscount++]=(p-(const unsigned char*)rhs.d_storage.c_str());
 132
 133   if(ourcount == sizeof(ourpos) || rhscount==sizeof(rhspos)) {
 134     return slowCanonCompare(rhs);
 135   }
 136
 137   for(;;) {
 138     if(ourcount == 0 && rhscount != 0)
 139       return true;
 140     if(ourcount == 0 && rhscount == 0)
 141       return false;
 142     if(ourcount !=0 && rhscount == 0)
 143       return false;
 144     ourcount--;
 145     rhscount--;
 146
 147     bool res=std::lexicographical_compare(
 148                                           d_storage.c_str() + ourpos[ourcount] + 1,
 149                                           d_storage.c_str() + ourpos[ourcount] + 1 + *(d_storage.c_str() + ourpos[ourcount]),
 150                                           rhs.d_storage.c_str() + rhspos[rhscount] + 1,
 151                                           rhs.d_storage.c_str() + rhspos[rhscount] + 1 + *(rhs.d_storage.c_str() + rhspos[rhscount]),
 152                                           [](const char& a, const char& b) {
 153                                             return dns2_tolower(a) < dns2_tolower(b);
 154                                           });
 155
 156     //    cout<<"Forward: "<<res<<endl;
 157     if(res)
 158       return true;
 159
 160     res=std::lexicographical_compare(     rhs.d_storage.c_str() + rhspos[rhscount] + 1,
 161                                           rhs.d_storage.c_str() + rhspos[rhscount] + 1 + *(rhs.d_storage.c_str() + rhspos[rhscount]),
 162                                           d_storage.c_str() + ourpos[ourcount] + 1,
 163                                           d_storage.c_str() + ourpos[ourcount] + 1 + *(d_storage.c_str() + ourpos[ourcount]),
 164                                           [](const char& a, const char& b) {
 165                                             return dns2_tolower(a) < dns2_tolower(b);
 166                                           });
 167     //    cout<<"Reverse: "<<res<<endl;
 168     if(res)
 169       return false;
 170   }
 171   return false;
 172 }
 173
 174
 175 struct CanonDNSNameCompare: public std::binary_function<DNSName, DNSName, bool>
 176 {
 177   bool operator()(const DNSName&a, const DNSName& b) const
 178   {
 179     return a.canonCompare(b);
 180   }
 181 };
 182
 183 inline DNSName operator+(const DNSName& lhs, const DNSName& rhs)
 184 {
 185   DNSName ret=lhs;
 186   ret += rhs;
 187   return ret;
 188 }
 189
 190 /* Quest in life: serve as a rapid block list. If you add a DNSName to a root SuffixMatchNode,
 191    anything part of that domain will return 'true' in check */
 192 struct SuffixMatchNode
 193 {
 194   SuffixMatchNode(const std::string& name_="", bool endNode_=false) : name(name_), endNode(endNode_)
 195   {}
 196   std::string name;
 197   std::string d_human;
 198   mutable std::set<SuffixMatchNode> children;
 199   mutable bool endNode;
 200   bool operator<(const SuffixMatchNode& rhs) const
 201   {
 202     return strcasecmp(name.c_str(), rhs.name.c_str()) < 0;
 203   }
 204
 205   void add(const DNSName& name)
 206   {
 207     if(!d_human.empty())
 208       d_human.append(", ");
 209     d_human += name.toString();
 210     add(name.getRawLabels());
 211   }
 212
 213   void add(std::vector<std::string> labels) const
 214   {
 215     if(labels.empty()) { // this allows insertion of the root
 216       endNode=true;
 217     }
 218     else if(labels.size()==1) {
 219       children.insert(SuffixMatchNode(*labels.begin(), true));
 220     }
 221     else {
 222       auto res=children.insert(SuffixMatchNode(*labels.rbegin(), false));
 223       labels.pop_back();
 224       res.first->add(labels);
 225     }
 226   }
 227
 228   bool check(const DNSName& name)  const
 229   {
 230     if(children.empty()) // speed up empty set
 231       return endNode;
 232     return check(name.getRawLabels());
 233   }
 234
 235   bool check(std::vector<std::string> labels) const
 236   {
 237     if(labels.empty()) // optimization
 238       return endNode;
 239
 240     SuffixMatchNode smn(*labels.rbegin());
 241     auto child = children.find(smn);
 242     if(child == children.end())
 243       return endNode;
 244     labels.pop_back();
 245     return child->check(labels);
 246   }
 247
 248   std::string toString() const
 249   {
 250     return d_human;
 251   }
 252
 253 };
 254
 255 std::ostream & operator<<(std::ostream &os, const DNSName& d);