]>
Commit | Line | Data |
---|---|---|
12471842 PL |
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 | */ | |
3c115e0f | 22 | #pragma once |
fba50923 | 23 | #include <array> |
85af94fd | 24 | #include <cstring> |
e11f6994 | 25 | #include <optional> |
3c115e0f | 26 | #include <string> |
97e5c6bc | 27 | #include <vector> |
ceee6652 | 28 | #include <set> |
29 | #include <strings.h> | |
0fae5c1e | 30 | #include <stdexcept> |
9f618bcc AD |
31 | #include <sstream> |
32 | #include <iterator> | |
cc0e7aa9 | 33 | #include <unordered_set> |
72a7ae39 | 34 | #include <string_view> |
bae1b0a2 | 35 | |
9f0fd264 KM |
36 | #include <boost/version.hpp> |
37 | ||
1db283e9 | 38 | #if BOOST_VERSION >= 105300 |
ca12836d | 39 | #include <boost/container/string.hpp> |
bae1b0a2 | 40 | #endif |
ddb7e6c6 | 41 | |
ad021b69 OM |
42 | inline bool dns_isspace(char c) |
43 | { | |
44 | return c == ' ' || c == '\t' || c == '\r' || c == '\n'; | |
45 | } | |
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 | { | |
51 | return dns_toupper_table[c]; | |
52 | } | |
53 | ||
54 | inline unsigned char dns_tolower(unsigned char c) | |
55 | { | |
56 | return dns_tolower_table[c]; | |
57 | } | |
2b62292d | 58 | |
42c83cbc | 59 | #include "burtle.hh" |
76cca09f | 60 | |
675fa24c | 61 | // #include "dns.hh" |
7abbc40f | 62 | // #include "logger.hh" |
3c115e0f | 63 | |
8ca15224 | 64 | //#include <ext/vstring.h> |
d8b778ff | 65 | |
84d4747e | 66 | /* Quest in life: |
3c115e0f | 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 | ||
84d4747e | 73 | Provide some common operators for comparison, detection of being part of another domain |
3c115e0f | 74 | |
75 | NOTE: For now, everything MUST be . terminated, otherwise it is an error | |
76 | */ | |
77 | ||
3c115e0f | 78 | class DNSName |
79 | { | |
80 | public: | |
9ec4c239 | 81 | static const size_t s_maxDNSNameLength = 255; |
429ccfe8 | 82 | |
abb11ca4 | 83 | DNSName() = default; //!< Constructs an *empty* DNSName, NOT the root! |
d720eb8a OM |
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 | { | |
87 | if (this != &rhs) { | |
88 | d_storage = rhs.d_storage; | |
89 | } | |
90 | return *this; | |
91 | } | |
71633799 | 92 | DNSName& operator=(DNSName&& rhs) noexcept |
d720eb8a OM |
93 | { |
94 | if (this != &rhs) { | |
95 | d_storage = std::move(rhs.d_storage); | |
96 | } | |
97 | return *this; | |
98 | } | |
99 | DNSName(const DNSName& a) = default; | |
100 | DNSName(DNSName&& a) = default; | |
72a7ae39 | 101 | |
a9c27e3a | 102 | explicit DNSName(std::string_view sw); //!< Constructs from a human formatted, escaped presentation |
cce0983c | 103 | 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. |
84d4747e | 104 | |
0badc6e1 | 105 | bool isPartOf(const DNSName& rhs) const; //!< Are we part of the rhs name? Note that name.isPartOf(name). |
c21484df | 106 | inline bool operator==(const DNSName& rhs) const; //!< DNS-native comparison (case insensitive) - empty compares to empty |
5fca2e23 PD |
107 | bool operator!=(const DNSName& other) const { return !(*this == other); } |
108 | ||
a61e8e59 | 109 | std::string toString(const std::string& separator=".", const bool trailing=true) const; //!< Our human-friendly, escaped, representation |
a44a8d66 | 110 | void toString(std::string& output, const std::string& separator=".", const bool trailing=true) const; |
9ab84270 | 111 | std::string toLogString() const; //!< like plain toString, but returns (empty) on empty names |
a61e8e59 | 112 | std::string toStringNoDot() const { return toString(".", false); } |
3b295666 | 113 | std::string toStringRootDot() const { if(isRoot()) return "."; else return toString(".", false); } |
3c115e0f | 114 | std::string toDNSString() const; //!< Our representation in DNS native format |
0ba4e1ee | 115 | std::string toDNSStringLC() const; //!< Our representation in DNS native format, lower cased |
3c115e0f | 116 | void appendRawLabel(const std::string& str); //!< Append this unescaped label |
e14febcf | 117 | void appendRawLabel(const char* start, unsigned int length); //!< Append this unescaped label |
3c115e0f | 118 | void prependRawLabel(const std::string& str); //!< Prepend this unescaped label |
97e5c6bc | 119 | std::vector<std::string> getRawLabels() const; //!< Individual raw unescaped labels |
39c9bef5 | 120 | std::string getRawLabel(unsigned int pos) const; //!< Get the specified raw unescaped label |
41e01592 | 121 | DNSName getLastLabel() const; //!< Get the DNSName of the last label |
3c115e0f | 122 | bool chopOff(); //!< Turn www.powerdns.com. into powerdns.com., returns false for . |
a61e8e59 | 123 | DNSName makeRelative(const DNSName& zone) const; |
d42896fb | 124 | DNSName makeLowerCase() const |
125 | { | |
8b63f61f KM |
126 | DNSName ret(*this); |
127 | ret.makeUsLowerCase(); | |
128 | return ret; | |
129 | } | |
130 | void makeUsLowerCase() | |
131 | { | |
132 | for(auto & c : d_storage) { | |
2b62292d | 133 | c=dns_tolower(c); |
d42896fb | 134 | } |
d42896fb | 135 | } |
8ca15224 | 136 | void makeUsRelative(const DNSName& zone); |
9b061cf5 | 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' |
a61e8e59 | 138 | DNSName labelReverse() const; |
8aa5a28c | 139 | bool isWildcard() const; |
32cd4eb1 | 140 | bool isHostname() const; |
97e5c6bc | 141 | unsigned int countLabels() const; |
3155c04a | 142 | size_t wirelength() const; //!< Number of total bytes in the name |
ae14c1f3 | 143 | bool empty() const { return d_storage.empty(); } |
144 | bool isRoot() const { return d_storage.size()==1 && d_storage[0]==0; } | |
145 | void clear() { d_storage.clear(); } | |
c9262563 | 146 | void trimToLabels(unsigned int); |
7691e7df | 147 | size_t hash(size_t init=0) const |
76cca09f | 148 | { |
7691e7df | 149 | return burtleCI((const unsigned char*)d_storage.c_str(), d_storage.size(), init); |
76cca09f | 150 | } |
6dcedea6 | 151 | DNSName& operator+=(const DNSName& rhs) |
152 | { | |
9ec4c239 | 153 | if(d_storage.size() + rhs.d_storage.size() > s_maxDNSNameLength + 1) // one extra byte for the second root label |
429ccfe8 | 154 | throwSafeRangeError("resulting name too long", rhs.d_storage.data(), rhs.d_storage.size()); |
ae14c1f3 | 155 | if(rhs.empty()) |
156 | return *this; | |
157 | ||
158 | if(d_storage.empty()) | |
159 | d_storage+=rhs.d_storage; | |
160 | else | |
161 | d_storage.replace(d_storage.length()-1, rhs.d_storage.length(), rhs.d_storage); | |
ac7921b0 | 162 | |
6dcedea6 | 163 | return *this; |
164 | } | |
c9262563 | 165 | |
6d8bc3c6 | 166 | bool operator<(const DNSName& rhs) const // this delivers _some_ kind of ordering, but not one useful in a DNS context. Really fast though. |
c9262563 | 167 | { |
84d4747e | 168 | return std::lexicographical_compare(d_storage.rbegin(), d_storage.rend(), |
97e5c6bc | 169 | rhs.d_storage.rbegin(), rhs.d_storage.rend(), |
1352c9b6 | 170 | [](const unsigned char& a, const unsigned char& b) { |
2b62292d | 171 | return dns_tolower(a) < dns_tolower(b); |
6d8bc3c6 | 172 | }); // note that this is case insensitive, including on the label lengths |
c9262563 | 173 | } |
174 | ||
ddb7e6c6 | 175 | inline bool canonCompare(const DNSName& rhs) const; |
84d4747e | 176 | bool slowCanonCompare(const DNSName& rhs) const; |
bae1b0a2 | 177 | |
1db283e9 | 178 | #if BOOST_VERSION >= 105300 |
ca12836d | 179 | typedef boost::container::string string_t; |
9f0fd264 KM |
180 | #else |
181 | typedef std::string string_t; | |
bae1b0a2 | 182 | #endif |
c21484df | 183 | const string_t& getStorage() const { |
184 | return d_storage; | |
185 | } | |
bf7ef5b4 RG |
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 | ||
fba50923 RG |
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 | ||
bae1b0a2 | 216 | private: |
d8b778ff | 217 | string_t d_storage; |
520eb5a0 | 218 | |
2e163d91 RG |
219 | class UnsignedCharView |
220 | { | |
221 | public: | |
222 | UnsignedCharView(const char* data_, size_t size_): view(data_, size_) | |
223 | { | |
224 | } | |
225 | const unsigned char& at(std::string_view::size_type pos) const | |
226 | { | |
227 | return reinterpret_cast<const unsigned char&>(view.at(pos)); | |
228 | } | |
229 | ||
230 | size_t size() const | |
231 | { | |
232 | return view.size(); | |
233 | } | |
234 | ||
235 | private: | |
236 | std::string_view view; | |
237 | }; | |
238 | ||
05fe7452 | 239 | 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); |
2e163d91 | 240 | size_t parsePacketUncompressed(const UnsignedCharView& view, size_t position, bool uncompress); |
2430e53c | 241 | static void appendEscapedLabel(std::string& appendTo, const char* orig, size_t len); |
3c115e0f | 242 | static std::string unescapeLabel(const std::string& orig); |
10ae7b37 | 243 | static void throwSafeRangeError(const std::string& msg, const char* buf, size_t length); |
3c115e0f | 244 | }; |
ceee6652 | 245 | |
5e1031cd | 246 | size_t hash_value(DNSName const& d); |
6d8bc3c6 | 247 | |
ddb7e6c6 | 248 | |
249 | inline bool DNSName::canonCompare(const DNSName& rhs) const | |
250 | { | |
251 | // 01234567890abcd | |
252 | // us: 1a3www4ds9a2nl | |
253 | // rhs: 3www6online3com | |
254 | // to compare, we start at the back, is nl < com? no -> done | |
255 | // | |
256 | // 0,2,6,a | |
257 | // 0,4,a | |
84d4747e | 258 | |
ddb7e6c6 | 259 | uint8_t ourpos[64], rhspos[64]; |
260 | uint8_t ourcount=0, rhscount=0; | |
261 | //cout<<"Asked to compare "<<toString()<<" to "<<rhs.toString()<<endl; | |
ae14c1f3 | 262 | 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) |
f3da403d | 263 | ourpos[ourcount++]=(p-(const unsigned char*)d_storage.c_str()); |
ae14c1f3 | 264 | 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) |
f3da403d | 265 | rhspos[rhscount++]=(p-(const unsigned char*)rhs.d_storage.c_str()); |
ddb7e6c6 | 266 | |
267 | if(ourcount == sizeof(ourpos) || rhscount==sizeof(rhspos)) { | |
268 | return slowCanonCompare(rhs); | |
269 | } | |
84d4747e | 270 | |
ddb7e6c6 | 271 | for(;;) { |
272 | if(ourcount == 0 && rhscount != 0) | |
273 | return true; | |
5708a729 | 274 | if(rhscount == 0) |
ddb7e6c6 | 275 | return false; |
276 | ourcount--; | |
277 | rhscount--; | |
278 | ||
ddb7e6c6 | 279 | bool res=std::lexicographical_compare( |
84d4747e | 280 | d_storage.c_str() + ourpos[ourcount] + 1, |
ddb7e6c6 | 281 | d_storage.c_str() + ourpos[ourcount] + 1 + *(d_storage.c_str() + ourpos[ourcount]), |
84d4747e | 282 | rhs.d_storage.c_str() + rhspos[rhscount] + 1, |
ddb7e6c6 | 283 | rhs.d_storage.c_str() + rhspos[rhscount] + 1 + *(rhs.d_storage.c_str() + rhspos[rhscount]), |
1352c9b6 | 284 | [](const unsigned char& a, const unsigned char& b) { |
2b62292d | 285 | return dns_tolower(a) < dns_tolower(b); |
ddb7e6c6 | 286 | }); |
84d4747e | 287 | |
ddb7e6c6 | 288 | // cout<<"Forward: "<<res<<endl; |
289 | if(res) | |
290 | return true; | |
291 | ||
84d4747e | 292 | res=std::lexicographical_compare( rhs.d_storage.c_str() + rhspos[rhscount] + 1, |
ddb7e6c6 | 293 | rhs.d_storage.c_str() + rhspos[rhscount] + 1 + *(rhs.d_storage.c_str() + rhspos[rhscount]), |
84d4747e | 294 | d_storage.c_str() + ourpos[ourcount] + 1, |
ddb7e6c6 | 295 | d_storage.c_str() + ourpos[ourcount] + 1 + *(d_storage.c_str() + ourpos[ourcount]), |
1352c9b6 | 296 | [](const unsigned char& a, const unsigned char& b) { |
2b62292d | 297 | return dns_tolower(a) < dns_tolower(b); |
ddb7e6c6 | 298 | }); |
299 | // cout<<"Reverse: "<<res<<endl; | |
300 | if(res) | |
301 | return false; | |
302 | } | |
303 | return false; | |
304 | } | |
305 | ||
306 | ||
7587bcbe | 307 | struct CanonDNSNameCompare |
6d8bc3c6 | 308 | { |
309 | bool operator()(const DNSName&a, const DNSName& b) const | |
310 | { | |
311 | return a.canonCompare(b); | |
312 | } | |
313 | }; | |
314 | ||
6dcedea6 | 315 | inline DNSName operator+(const DNSName& lhs, const DNSName& rhs) |
316 | { | |
317 | DNSName ret=lhs; | |
318 | ret += rhs; | |
319 | return ret; | |
320 | } | |
ceee6652 | 321 | |
e11f6994 RG |
322 | extern const DNSName g_rootdnsname, g_wildcarddnsname; |
323 | ||
40ea5b5b RG |
324 | template<typename T> |
325 | struct SuffixMatchTree | |
326 | { | |
af619119 | 327 | SuffixMatchTree(const std::string& name="", bool endNode_=false) : d_name(name), endNode(endNode_) |
40ea5b5b RG |
328 | {} |
329 | ||
6c58e309 | 330 | SuffixMatchTree(const SuffixMatchTree& rhs): d_name(rhs.d_name), children(rhs.children), endNode(rhs.endNode) |
40ea5b5b | 331 | { |
6c58e309 RG |
332 | if (endNode) { |
333 | d_value = rhs.d_value; | |
334 | } | |
40ea5b5b | 335 | } |
f238ce64 OM |
336 | SuffixMatchTree & operator=(const SuffixMatchTree &rhs) |
337 | { | |
338 | d_name = rhs.d_name; | |
339 | children = rhs.children; | |
340 | endNode = rhs.endNode; | |
341 | if (endNode) { | |
342 | d_value = rhs.d_value; | |
343 | } | |
344 | return *this; | |
345 | } | |
65cd686f RG |
346 | bool operator<(const SuffixMatchTree& rhs) const |
347 | { | |
348 | return strcasecmp(d_name.c_str(), rhs.d_name.c_str()) < 0; | |
349 | } | |
84d4747e | 350 | |
af619119 | 351 | std::string d_name; |
43075548 | 352 | mutable std::set<SuffixMatchTree, std::less<>> children; |
40ea5b5b RG |
353 | mutable bool endNode; |
354 | mutable T d_value; | |
43075548 RG |
355 | |
356 | /* this structure is used to do a lookup without allocating and | |
357 | copying a string, using C++14's heterogeneous lookups in ordered | |
358 | containers */ | |
359 | struct LightKey | |
360 | { | |
361 | std::string_view d_name; | |
362 | bool operator<(const SuffixMatchTree& smt) const | |
363 | { | |
364 | auto compareUpTo = std::min(this->d_name.size(), smt.d_name.size()); | |
365 | auto ret = strncasecmp(this->d_name.data(), smt.d_name.data(), compareUpTo); | |
366 | if (ret != 0) { | |
367 | return ret < 0; | |
368 | } | |
369 | if (this->d_name.size() == smt.d_name.size()) { | |
370 | return ret < 0; | |
371 | } | |
372 | return this->d_name.size() < smt.d_name.size(); | |
373 | } | |
374 | }; | |
375 | ||
376 | bool operator<(const LightKey& lk) const | |
377 | { | |
378 | auto compareUpTo = std::min(this->d_name.size(), lk.d_name.size()); | |
379 | auto ret = strncasecmp(this->d_name.data(), lk.d_name.data(), compareUpTo); | |
380 | if (ret != 0) { | |
381 | return ret < 0; | |
382 | } | |
383 | if (this->d_name.size() == lk.d_name.size()) { | |
384 | return ret < 0; | |
385 | } | |
386 | return this->d_name.size() < lk.d_name.size(); | |
387 | } | |
40ea5b5b RG |
388 | |
389 | template<typename V> | |
390 | void visit(const V& v) const { | |
a4244240 | 391 | for(const auto& c : children) { |
40ea5b5b | 392 | c.visit(v); |
a4244240 RG |
393 | } |
394 | ||
395 | if (endNode) { | |
40ea5b5b | 396 | v(*this); |
a4244240 | 397 | } |
40ea5b5b RG |
398 | } |
399 | ||
a4244240 | 400 | void add(const DNSName& name, T&& t) |
40ea5b5b | 401 | { |
a4244240 RG |
402 | auto labels = name.getRawLabels(); |
403 | add(labels, std::move(t)); | |
40ea5b5b RG |
404 | } |
405 | ||
a4244240 | 406 | void add(std::vector<std::string>& labels, T&& value) const |
40ea5b5b | 407 | { |
a4244240 RG |
408 | if (labels.empty()) { // this allows insertion of the root |
409 | endNode = true; | |
410 | d_value = std::move(value); | |
40ea5b5b RG |
411 | } |
412 | else if(labels.size()==1) { | |
a4244240 RG |
413 | auto res = children.emplace(*labels.begin(), true); |
414 | if (!res.second) { | |
1a083287 RG |
415 | // we might already have had the node as an |
416 | // intermediary one, but it's now an end node | |
a4244240 | 417 | if (!res.first->endNode) { |
1a083287 RG |
418 | res.first->endNode = true; |
419 | } | |
420 | } | |
a4244240 | 421 | res.first->d_value = std::move(value); |
40ea5b5b RG |
422 | } |
423 | else { | |
a4244240 | 424 | auto res = children.emplace(*labels.rbegin(), false); |
40ea5b5b | 425 | labels.pop_back(); |
a4244240 | 426 | res.first->add(labels, std::move(value)); |
40ea5b5b RG |
427 | } |
428 | } | |
429 | ||
da6be6e3 | 430 | void remove(const DNSName &name, bool subtree=false) const |
a364fbfb | 431 | { |
a4244240 | 432 | auto labels = name.getRawLabels(); |
da6be6e3 | 433 | remove(labels, subtree); |
a364fbfb PL |
434 | } |
435 | ||
436 | /* Removes the node at `labels`, also make sure that no empty | |
437 | * children will be left behind in memory | |
438 | */ | |
da6be6e3 | 439 | void remove(std::vector<std::string>& labels, bool subtree = false) const |
a364fbfb | 440 | { |
dbeebfee RG |
441 | if (labels.empty()) { // this allows removal of the root |
442 | endNode = false; | |
da6be6e3 RG |
443 | if (subtree) { |
444 | children.clear(); | |
445 | } | |
dbeebfee RG |
446 | return; |
447 | } | |
448 | ||
a364fbfb PL |
449 | SuffixMatchTree smt(*labels.rbegin()); |
450 | auto child = children.find(smt); | |
451 | if (child == children.end()) { | |
452 | // No subnode found, we're done | |
453 | return; | |
454 | } | |
455 | ||
456 | // We have found a child | |
457 | labels.pop_back(); | |
458 | if (labels.empty()) { | |
459 | // The child is no longer an endnode | |
460 | child->endNode = false; | |
67689ec7 | 461 | |
da6be6e3 RG |
462 | if (subtree) { |
463 | child->children.clear(); | |
464 | } | |
465 | ||
a364fbfb PL |
466 | // If the child has no further children, just remove it from the set. |
467 | if (child->children.empty()) { | |
468 | children.erase(child); | |
469 | } | |
470 | return; | |
471 | } | |
472 | ||
473 | // We are not at the end, let the child figure out what to do | |
474 | child->remove(labels); | |
475 | } | |
476 | ||
e11f6994 RG |
477 | T* lookup(const DNSName& name) const |
478 | { | |
479 | auto bestNode = getBestNode(name); | |
480 | if (bestNode) { | |
481 | return &bestNode->d_value; | |
482 | } | |
483 | return nullptr; | |
484 | } | |
485 | ||
486 | std::optional<DNSName> getBestMatch(const DNSName& name) const | |
487 | { | |
488 | if (children.empty()) { // speed up empty set | |
489 | return endNode ? std::optional<DNSName>(g_rootdnsname) : std::nullopt; | |
490 | } | |
491 | ||
492 | auto visitor = name.getRawLabelsVisitor(); | |
493 | return getBestMatch(visitor); | |
494 | } | |
495 | ||
496 | // Returns all end-nodes, fully qualified (not as separate labels) | |
497 | std::vector<DNSName> getNodes() const { | |
498 | std::vector<DNSName> ret; | |
499 | if (endNode) { | |
500 | ret.push_back(DNSName(d_name)); | |
501 | } | |
502 | for (const auto& child : children) { | |
503 | auto nodes = child.getNodes(); | |
504 | ret.reserve(ret.size() + nodes.size()); | |
505 | for (const auto &node: nodes) { | |
506 | ret.push_back(node + DNSName(d_name)); | |
507 | } | |
508 | } | |
509 | return ret; | |
510 | } | |
511 | ||
512 | private: | |
513 | const SuffixMatchTree* getBestNode(const DNSName& name) const | |
40ea5b5b | 514 | { |
a4244240 RG |
515 | if (children.empty()) { // speed up empty set |
516 | if (endNode) { | |
e11f6994 | 517 | return this; |
a4244240 | 518 | } |
99517c1b | 519 | return nullptr; |
40ea5b5b | 520 | } |
99517c1b | 521 | |
fba50923 | 522 | auto visitor = name.getRawLabelsVisitor(); |
e11f6994 | 523 | return getBestNode(visitor); |
40ea5b5b RG |
524 | } |
525 | ||
e11f6994 | 526 | const SuffixMatchTree* getBestNode(DNSName::RawLabelsVisitor& visitor) const |
40ea5b5b | 527 | { |
fba50923 | 528 | if (visitor.empty()) { // optimization |
a4244240 | 529 | if (endNode) { |
e11f6994 | 530 | return this; |
a4244240 | 531 | } |
99517c1b | 532 | return nullptr; |
40ea5b5b RG |
533 | } |
534 | ||
43075548 RG |
535 | const LightKey lk{visitor.back()}; |
536 | auto child = children.find(lk); | |
a4244240 | 537 | if (child == children.end()) { |
e11f6994 RG |
538 | if (endNode) { |
539 | return this; | |
a4244240 | 540 | } |
99517c1b | 541 | return nullptr; |
40ea5b5b | 542 | } |
fba50923 | 543 | visitor.pop_back(); |
e11f6994 | 544 | auto result = child->getBestNode(visitor); |
99517c1b RG |
545 | if (result) { |
546 | return result; | |
547 | } | |
e11f6994 | 548 | return endNode ? this : nullptr; |
40ea5b5b RG |
549 | } |
550 | ||
e11f6994 RG |
551 | std::optional<DNSName> getBestMatch(DNSName::RawLabelsVisitor& visitor) const |
552 | { | |
553 | if (visitor.empty()) { // optimization | |
554 | if (endNode) { | |
555 | return std::optional<DNSName>(d_name); | |
556 | } | |
557 | return std::nullopt; | |
606400e7 | 558 | } |
e11f6994 RG |
559 | |
560 | const LightKey lk{visitor.back()}; | |
561 | auto child = children.find(lk); | |
562 | if (child == children.end()) { | |
563 | if (endNode) { | |
564 | return std::optional<DNSName>(d_name); | |
606400e7 | 565 | } |
e11f6994 | 566 | return std::nullopt; |
606400e7 | 567 | } |
e11f6994 RG |
568 | visitor.pop_back(); |
569 | auto result = child->getBestMatch(visitor); | |
570 | if (result) { | |
571 | if (!d_name.empty()) { | |
572 | result->appendRawLabel(d_name); | |
573 | } | |
574 | return result; | |
575 | } | |
576 | return endNode ? std::optional<DNSName>(d_name) : std::nullopt; | |
606400e7 | 577 | } |
40ea5b5b RG |
578 | }; |
579 | ||
0eaa51e5 RG |
580 | /* Quest in life: serve as a rapid block list. If you add a DNSName to a root SuffixMatchNode, |
581 | anything part of that domain will return 'true' in check */ | |
582 | struct SuffixMatchNode | |
583 | { | |
15d0cc71 | 584 | public: |
abb11ca4 | 585 | SuffixMatchNode() = default; |
15d0cc71 PL |
586 | SuffixMatchTree<bool> d_tree; |
587 | ||
588 | void add(const DNSName& dnsname) | |
589 | { | |
590 | d_tree.add(dnsname, true); | |
591 | d_nodes.insert(dnsname); | |
15d0cc71 | 592 | } |
0eaa51e5 | 593 | |
41ff82c9 PL |
594 | void add(const std::string& name) |
595 | { | |
596 | add(DNSName(name)); | |
597 | } | |
598 | ||
15d0cc71 PL |
599 | void add(std::vector<std::string> labels) |
600 | { | |
601 | d_tree.add(labels, true); | |
602 | DNSName tmp; | |
603 | while (!labels.empty()) { | |
604 | tmp.appendRawLabel(labels.back()); | |
605 | labels.pop_back(); // This is safe because we have a copy of labels | |
606 | } | |
607 | d_nodes.insert(tmp); | |
15d0cc71 | 608 | } |
0eaa51e5 | 609 | |
15d0cc71 PL |
610 | void remove(const DNSName& name) |
611 | { | |
612 | d_tree.remove(name); | |
613 | d_nodes.erase(name); | |
15d0cc71 | 614 | } |
0eaa51e5 | 615 | |
15d0cc71 PL |
616 | void remove(std::vector<std::string> labels) |
617 | { | |
618 | d_tree.remove(labels); | |
619 | DNSName tmp; | |
620 | while (!labels.empty()) { | |
621 | tmp.appendRawLabel(labels.back()); | |
622 | labels.pop_back(); // This is safe because we have a copy of labels | |
623 | } | |
624 | d_nodes.erase(tmp); | |
15d0cc71 | 625 | } |
a364fbfb | 626 | |
15d0cc71 PL |
627 | bool check(const DNSName& dnsname) const |
628 | { | |
629 | return d_tree.lookup(dnsname) != nullptr; | |
630 | } | |
a364fbfb | 631 | |
e11f6994 RG |
632 | std::optional<DNSName> getBestMatch(const DNSName& name) const |
633 | { | |
634 | return d_tree.getBestMatch(name); | |
635 | } | |
636 | ||
15d0cc71 PL |
637 | std::string toString() const |
638 | { | |
3f5115d1 | 639 | std::string ret; |
15d0cc71 PL |
640 | bool first = true; |
641 | for (const auto& n : d_nodes) { | |
642 | if (!first) { | |
3f5115d1 | 643 | ret += ", "; |
15d0cc71 PL |
644 | } |
645 | first = false; | |
3f5115d1 | 646 | ret += n.toString(); |
606400e7 | 647 | } |
3f5115d1 | 648 | return ret; |
606400e7 | 649 | } |
3f5115d1 PL |
650 | |
651 | private: | |
3f5115d1 | 652 | mutable std::set<DNSName> d_nodes; // Only used for string generation |
0eaa51e5 RG |
653 | }; |
654 | ||
8171ab83 | 655 | std::ostream & operator<<(std::ostream &os, const DNSName& d); |
6106128d | 656 | namespace std { |
657 | template <> | |
658 | struct hash<DNSName> { | |
659 | size_t operator () (const DNSName& dn) const { return dn.hash(0); } | |
660 | }; | |
661 | } | |
bae1b0a2 | 662 | |
beb9fad5 | 663 | DNSName::string_t segmentDNSNameRaw(const char* input, size_t inputlen); // from ragel |
84d4747e | 664 | |
c21484df | 665 | bool DNSName::operator==(const DNSName& rhs) const |
666 | { | |
84d4747e | 667 | if (rhs.empty() != empty() || rhs.d_storage.size() != d_storage.size()) { |
c21484df | 668 | return false; |
84d4747e | 669 | } |
c21484df | 670 | |
84d4747e FM |
671 | const auto* us = d_storage.cbegin(); |
672 | const auto* p = rhs.d_storage.cbegin(); | |
673 | for (; us != d_storage.cend() && p != rhs.d_storage.cend(); ++us, ++p) { | |
674 | if (dns_tolower(*p) != dns_tolower(*us)) { | |
c21484df | 675 | return false; |
84d4747e | 676 | } |
c21484df | 677 | } |
678 | return true; | |
679 | } | |
680 | ||
cc0e7aa9 | 681 | struct DNSNameSet: public std::unordered_set<DNSName> { |
9f618bcc AD |
682 | std::string toString() const { |
683 | std::ostringstream oss; | |
684 | std::copy(begin(), end(), std::ostream_iterator<DNSName>(oss, "\n")); | |
685 | return oss.str(); | |
686 | } | |
687 | }; |