2 * This file is part of PowerDNS or dnsdist.
3 * Copyright -- PowerDNS.COM B.V. and its contributors
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.
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.
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.
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.
33 #include <unordered_set>
34 #include <string_view>
36 #include <boost/version.hpp>
38 #if BOOST_VERSION >= 105300
39 #include <boost/container/string.hpp>
42 inline bool dns_isspace(char c)
44 return c == ' ' || c == '\t' || c == '\r' || c == '\n';
47 extern const unsigned char dns_toupper_table[256], dns_tolower_table[256];
49 inline unsigned char dns_toupper(unsigned char c)
51 return dns_toupper_table[c];
54 inline unsigned char dns_tolower(unsigned char c)
56 return dns_tolower_table[c];
63 // #include "logger.hh"
65 //#include <ext/vstring.h>
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
72 Be able to turn them into ASCII and "DNS name in a packet" again on request
74 Provide some common operators for comparison, detection of being part of another domain
76 NOTE: For now, everything MUST be . terminated, otherwise it is an error
82 static const size_t s_maxDNSNameLength = 255;
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)
89 d_storage = rhs.d_storage;
93 DNSName& operator=(DNSName&& rhs) noexcept
96 d_storage = std::move(rhs.d_storage);
100 DNSName(const DNSName& a) = default;
101 DNSName(DNSName&& a) = default;
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.
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); }
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
128 ret.makeUsLowerCase();
131 void makeUsLowerCase()
133 for(auto & c : d_storage) {
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
150 return burtleCI((const unsigned char*)d_storage.c_str(), d_storage.size(), init);
152 DNSName& operator+=(const DNSName& rhs)
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());
159 if(d_storage.empty())
160 d_storage+=rhs.d_storage;
162 d_storage.replace(d_storage.length()-1, rhs.d_storage.length(), rhs.d_storage);
167 bool operator<(const DNSName& rhs) const // this delivers _some_ kind of ordering, but not one useful in a DNS context. Really fast though.
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
176 inline bool canonCompare(const DNSName& rhs) const;
177 bool slowCanonCompare(const DNSName& rhs) const;
179 #if BOOST_VERSION >= 105300
180 typedef boost::container::string string_t;
182 typedef std::string string_t;
184 const string_t& getStorage() const {
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_*./@ \\:-] */
190 class RawLabelsVisitor
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).
205 RawLabelsVisitor(const string_t& storage);
206 std::string_view front() const;
207 std::string_view back() const;
211 std::array<uint8_t, 128> d_labelPositions;
212 const string_t& d_storage;
213 size_t d_position{0};
215 RawLabelsVisitor getRawLabelsVisitor() const;
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);
227 size_t hash_value(DNSName const& d);
230 inline bool DNSName::canonCompare(const DNSName& rhs) const
233 // us: 1a3www4ds9a2nl
234 // rhs: 3www6online3com
235 // to compare, we start at the back, is nl < com? no -> done
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());
248 if(ourcount == sizeof(ourpos) || rhscount==sizeof(rhspos)) {
249 return slowCanonCompare(rhs);
253 if(ourcount == 0 && rhscount != 0)
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);
269 // cout<<"Forward: "<<res<<endl;
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);
280 // cout<<"Reverse: "<<res<<endl;
288 struct CanonDNSNameCompare
290 bool operator()(const DNSName&a, const DNSName& b) const
292 return a.canonCompare(b);
296 inline DNSName operator+(const DNSName& lhs, const DNSName& rhs)
303 extern const DNSName g_rootdnsname, g_wildcarddnsname;
306 struct SuffixMatchTree
308 SuffixMatchTree(const std::string& name="", bool endNode_=false) : d_name(name), endNode(endNode_)
311 SuffixMatchTree(const SuffixMatchTree& rhs): d_name(rhs.d_name), children(rhs.children), endNode(rhs.endNode)
314 d_value = rhs.d_value;
317 SuffixMatchTree & operator=(const SuffixMatchTree &rhs)
320 children = rhs.children;
321 endNode = rhs.endNode;
323 d_value = rhs.d_value;
327 bool operator<(const SuffixMatchTree& rhs) const
329 return strcasecmp(d_name.c_str(), rhs.d_name.c_str()) < 0;
333 mutable std::set<SuffixMatchTree, std::less<>> children;
334 mutable bool endNode;
337 /* this structure is used to do a lookup without allocating and
338 copying a string, using C++14's heterogeneous lookups in ordered
342 std::string_view d_name;
343 bool operator<(const SuffixMatchTree& smt) const
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);
350 if (this->d_name.size() == smt.d_name.size()) {
353 return this->d_name.size() < smt.d_name.size();
357 bool operator<(const LightKey& lk) const
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);
364 if (this->d_name.size() == lk.d_name.size()) {
367 return this->d_name.size() < lk.d_name.size();
371 void visit(const V& v) const {
372 for(const auto& c : children) {
381 void add(const DNSName& name, T&& t)
383 auto labels = name.getRawLabels();
384 add(labels, std::move(t));
387 void add(std::vector<std::string>& labels, T&& value) const
389 if (labels.empty()) { // this allows insertion of the root
391 d_value = std::move(value);
393 else if(labels.size()==1) {
394 auto res = children.emplace(*labels.begin(), true);
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;
402 res.first->d_value = std::move(value);
405 auto res = children.emplace(*labels.rbegin(), false);
407 res.first->add(labels, std::move(value));
411 void remove(const DNSName &name, bool subtree=false) const
413 auto labels = name.getRawLabels();
414 remove(labels, subtree);
417 /* Removes the node at `labels`, also make sure that no empty
418 * children will be left behind in memory
420 void remove(std::vector<std::string>& labels, bool subtree = false) const
422 if (labels.empty()) { // this allows removal of the root
430 SuffixMatchTree smt(*labels.rbegin());
431 auto child = children.find(smt);
432 if (child == children.end()) {
433 // No subnode found, we're done
437 // We have found a child
439 if (labels.empty()) {
440 // The child is no longer an endnode
441 child->endNode = false;
444 child->children.clear();
447 // If the child has no further children, just remove it from the set.
448 if (child->children.empty()) {
449 children.erase(child);
454 // We are not at the end, let the child figure out what to do
455 child->remove(labels);
458 T* lookup(const DNSName& name) const
460 auto bestNode = getBestNode(name);
462 return &bestNode->d_value;
467 std::optional<DNSName> getBestMatch(const DNSName& name) const
469 if (children.empty()) { // speed up empty set
470 return endNode ? std::optional<DNSName>(g_rootdnsname) : std::nullopt;
473 auto visitor = name.getRawLabelsVisitor();
474 return getBestMatch(visitor);
477 // Returns all end-nodes, fully qualified (not as separate labels)
478 std::vector<DNSName> getNodes() const {
479 std::vector<DNSName> ret;
481 ret.push_back(DNSName(d_name));
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));
494 const SuffixMatchTree* getBestNode(const DNSName& name) const
496 if (children.empty()) { // speed up empty set
503 auto visitor = name.getRawLabelsVisitor();
504 return getBestNode(visitor);
507 const SuffixMatchTree* getBestNode(DNSName::RawLabelsVisitor& visitor) const
509 if (visitor.empty()) { // optimization
516 const LightKey lk{visitor.back()};
517 auto child = children.find(lk);
518 if (child == children.end()) {
525 auto result = child->getBestNode(visitor);
529 return endNode ? this : nullptr;
532 std::optional<DNSName> getBestMatch(DNSName::RawLabelsVisitor& visitor) const
534 if (visitor.empty()) { // optimization
536 return std::optional<DNSName>(d_name);
541 const LightKey lk{visitor.back()};
542 auto child = children.find(lk);
543 if (child == children.end()) {
545 return std::optional<DNSName>(d_name);
550 auto result = child->getBestMatch(visitor);
552 if (!d_name.empty()) {
553 result->appendRawLabel(d_name);
557 return endNode ? std::optional<DNSName>(d_name) : std::nullopt;
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
566 SuffixMatchNode() = default;
567 SuffixMatchTree<bool> d_tree;
569 void add(const DNSName& dnsname)
571 d_tree.add(dnsname, true);
572 d_nodes.insert(dnsname);
575 void add(const std::string& name)
580 void add(std::vector<std::string> labels)
582 d_tree.add(labels, true);
584 while (!labels.empty()) {
585 tmp.appendRawLabel(labels.back());
586 labels.pop_back(); // This is safe because we have a copy of labels
591 void remove(const DNSName& name)
597 void remove(std::vector<std::string> labels)
599 d_tree.remove(labels);
601 while (!labels.empty()) {
602 tmp.appendRawLabel(labels.back());
603 labels.pop_back(); // This is safe because we have a copy of labels
608 bool check(const DNSName& dnsname) const
610 return d_tree.lookup(dnsname) != nullptr;
613 std::optional<DNSName> getBestMatch(const DNSName& name) const
615 return d_tree.getBestMatch(name);
618 std::string toString() const
622 for (const auto& n : d_nodes) {
633 mutable std::set<DNSName> d_nodes; // Only used for string generation
636 std::ostream & operator<<(std::ostream &os, const DNSName& d);
639 struct hash<DNSName> {
640 size_t operator () (const DNSName& dn) const { return dn.hash(0); }
644 DNSName::string_t segmentDNSNameRaw(const char* input, size_t inputlen); // from ragel
646 bool DNSName::operator==(const DNSName& rhs) const
648 if (rhs.empty() != empty() || rhs.d_storage.size() != d_storage.size()) {
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)) {
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"));