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