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