]>
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 |
23 | #include <string> | |
97e5c6bc | 24 | #include <vector> |
ceee6652 | 25 | #include <set> |
97e5c6bc | 26 | #include <deque> |
ceee6652 | 27 | #include <strings.h> |
0fae5c1e | 28 | #include <stdexcept> |
bae1b0a2 | 29 | |
9f0fd264 KM |
30 | #include <boost/version.hpp> |
31 | ||
c9186ca1 | 32 | // it crashes on OSX and doesn't compile on OpenBSD |
46104a7e | 33 | #if BOOST_VERSION >= 105300 && ! defined( __APPLE__ ) && ! defined(__OpenBSD__) |
ca12836d | 34 | #include <boost/container/string.hpp> |
bae1b0a2 | 35 | #endif |
ddb7e6c6 | 36 | |
2b62292d TF |
37 | #include "ascii.hh" |
38 | ||
5c57a75a | 39 | uint32_t burtleCI(const unsigned char* k, uint32_t length, uint32_t init); |
76cca09f | 40 | |
675fa24c | 41 | // #include "dns.hh" |
7abbc40f | 42 | // #include "logger.hh" |
3c115e0f | 43 | |
8ca15224 | 44 | //#include <ext/vstring.h> |
d8b778ff | 45 | |
3c115e0f | 46 | /* Quest in life: |
47 | accept escaped ascii presentations of DNS names and store them "natively" | |
48 | accept a DNS packet with an offset, and extract a DNS name from it | |
49 | build up DNSNames with prepend and append of 'raw' unescaped labels | |
50 | ||
51 | Be able to turn them into ASCII and "DNS name in a packet" again on request | |
52 | ||
53 | Provide some common operators for comparison, detection of being part of another domain | |
54 | ||
55 | NOTE: For now, everything MUST be . terminated, otherwise it is an error | |
56 | */ | |
57 | ||
3c115e0f | 58 | class DNSName |
59 | { | |
60 | public: | |
ae14c1f3 | 61 | DNSName() {} //!< Constructs an *empty* DNSName, NOT the root! |
8171ab83 | 62 | explicit DNSName(const char* p); //!< Constructs from a human formatted, escaped presentation |
bae1b0a2 | 63 | explicit DNSName(const std::string& str) : DNSName(str.c_str()) {}; //!< Constructs from a human formatted, escaped presentation |
83fc9d8a | 64 | DNSName(const char* p, int len, int offset, bool uncompress, uint16_t* qtype=0, uint16_t* qclass=0, unsigned int* consumed=0, uint16_t minOffset=0); //!< Construct from a DNS Packet, taking the first question if offset=12 |
3c115e0f | 65 | |
66 | bool isPartOf(const DNSName& rhs) const; //!< Are we part of the rhs name? | |
c21484df | 67 | inline bool operator==(const DNSName& rhs) const; //!< DNS-native comparison (case insensitive) - empty compares to empty |
5fca2e23 PD |
68 | bool operator!=(const DNSName& other) const { return !(*this == other); } |
69 | ||
a61e8e59 | 70 | std::string toString(const std::string& separator=".", const bool trailing=true) const; //!< Our human-friendly, escaped, representation |
9ab84270 | 71 | std::string toLogString() const; //!< like plain toString, but returns (empty) on empty names |
a61e8e59 | 72 | std::string toStringNoDot() const { return toString(".", false); } |
3b295666 | 73 | std::string toStringRootDot() const { if(isRoot()) return "."; else return toString(".", false); } |
3c115e0f | 74 | std::string toDNSString() const; //!< Our representation in DNS native format |
0ba4e1ee | 75 | std::string toDNSStringLC() const; //!< Our representation in DNS native format, lower cased |
3c115e0f | 76 | void appendRawLabel(const std::string& str); //!< Append this unescaped label |
e14febcf | 77 | void appendRawLabel(const char* start, unsigned int length); //!< Append this unescaped label |
3c115e0f | 78 | void prependRawLabel(const std::string& str); //!< Prepend this unescaped label |
97e5c6bc | 79 | std::vector<std::string> getRawLabels() const; //!< Individual raw unescaped labels |
39c9bef5 | 80 | std::string getRawLabel(unsigned int pos) const; //!< Get the specified raw unescaped label |
41e01592 | 81 | DNSName getLastLabel() const; //!< Get the DNSName of the last label |
3c115e0f | 82 | bool chopOff(); //!< Turn www.powerdns.com. into powerdns.com., returns false for . |
a61e8e59 | 83 | DNSName makeRelative(const DNSName& zone) const; |
d42896fb | 84 | DNSName makeLowerCase() const |
85 | { | |
8b63f61f KM |
86 | DNSName ret(*this); |
87 | ret.makeUsLowerCase(); | |
88 | return ret; | |
89 | } | |
90 | void makeUsLowerCase() | |
91 | { | |
92 | for(auto & c : d_storage) { | |
2b62292d | 93 | c=dns_tolower(c); |
d42896fb | 94 | } |
d42896fb | 95 | } |
8ca15224 | 96 | void makeUsRelative(const DNSName& zone); |
9b061cf5 | 97 | 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 | 98 | DNSName labelReverse() const; |
8aa5a28c | 99 | bool isWildcard() const; |
32cd4eb1 | 100 | bool isHostname() const; |
97e5c6bc | 101 | unsigned int countLabels() const; |
3155c04a | 102 | size_t wirelength() const; //!< Number of total bytes in the name |
ae14c1f3 | 103 | bool empty() const { return d_storage.empty(); } |
104 | bool isRoot() const { return d_storage.size()==1 && d_storage[0]==0; } | |
105 | void clear() { d_storage.clear(); } | |
c9262563 | 106 | void trimToLabels(unsigned int); |
7691e7df | 107 | size_t hash(size_t init=0) const |
76cca09f | 108 | { |
7691e7df | 109 | return burtleCI((const unsigned char*)d_storage.c_str(), d_storage.size(), init); |
76cca09f | 110 | } |
6dcedea6 | 111 | DNSName& operator+=(const DNSName& rhs) |
112 | { | |
1106afd9 | 113 | if(d_storage.size() + rhs.d_storage.size() > 256) // one extra byte for the second root label |
ac7921b0 | 114 | throw std::range_error("name too long"); |
ae14c1f3 | 115 | if(rhs.empty()) |
116 | return *this; | |
117 | ||
118 | if(d_storage.empty()) | |
119 | d_storage+=rhs.d_storage; | |
120 | else | |
121 | d_storage.replace(d_storage.length()-1, rhs.d_storage.length(), rhs.d_storage); | |
ac7921b0 | 122 | |
6dcedea6 | 123 | return *this; |
124 | } | |
c9262563 | 125 | |
6d8bc3c6 | 126 | bool operator<(const DNSName& rhs) const // this delivers _some_ kind of ordering, but not one useful in a DNS context. Really fast though. |
c9262563 | 127 | { |
97e5c6bc | 128 | return std::lexicographical_compare(d_storage.rbegin(), d_storage.rend(), |
129 | rhs.d_storage.rbegin(), rhs.d_storage.rend(), | |
1352c9b6 | 130 | [](const unsigned char& a, const unsigned char& b) { |
2b62292d | 131 | return dns_tolower(a) < dns_tolower(b); |
6d8bc3c6 | 132 | }); // note that this is case insensitive, including on the label lengths |
c9262563 | 133 | } |
134 | ||
ddb7e6c6 | 135 | inline bool canonCompare(const DNSName& rhs) const; |
f3da403d | 136 | bool slowCanonCompare(const DNSName& rhs) const; |
bae1b0a2 | 137 | |
46104a7e | 138 | #if BOOST_VERSION >= 105300 && ! defined( __APPLE__ ) && ! defined(__OpenBSD__) |
ca12836d | 139 | typedef boost::container::string string_t; |
9f0fd264 KM |
140 | #else |
141 | typedef std::string string_t; | |
bae1b0a2 | 142 | #endif |
c21484df | 143 | const string_t& getStorage() const { |
144 | return d_storage; | |
145 | } | |
bae1b0a2 | 146 | private: |
d8b778ff | 147 | string_t d_storage; |
520eb5a0 | 148 | |
83fc9d8a | 149 | 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); |
3c115e0f | 150 | static std::string escapeLabel(const std::string& orig); |
151 | static std::string unescapeLabel(const std::string& orig); | |
152 | }; | |
ceee6652 | 153 | |
5e1031cd | 154 | size_t hash_value(DNSName const& d); |
6d8bc3c6 | 155 | |
ddb7e6c6 | 156 | |
157 | inline bool DNSName::canonCompare(const DNSName& rhs) const | |
158 | { | |
159 | // 01234567890abcd | |
160 | // us: 1a3www4ds9a2nl | |
161 | // rhs: 3www6online3com | |
162 | // to compare, we start at the back, is nl < com? no -> done | |
163 | // | |
164 | // 0,2,6,a | |
165 | // 0,4,a | |
166 | ||
167 | uint8_t ourpos[64], rhspos[64]; | |
168 | uint8_t ourcount=0, rhscount=0; | |
169 | //cout<<"Asked to compare "<<toString()<<" to "<<rhs.toString()<<endl; | |
ae14c1f3 | 170 | 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 | 171 | ourpos[ourcount++]=(p-(const unsigned char*)d_storage.c_str()); |
ae14c1f3 | 172 | 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 | 173 | rhspos[rhscount++]=(p-(const unsigned char*)rhs.d_storage.c_str()); |
ddb7e6c6 | 174 | |
175 | if(ourcount == sizeof(ourpos) || rhscount==sizeof(rhspos)) { | |
176 | return slowCanonCompare(rhs); | |
177 | } | |
178 | ||
179 | for(;;) { | |
180 | if(ourcount == 0 && rhscount != 0) | |
181 | return true; | |
182 | if(ourcount == 0 && rhscount == 0) | |
183 | return false; | |
184 | if(ourcount !=0 && rhscount == 0) | |
185 | return false; | |
186 | ourcount--; | |
187 | rhscount--; | |
188 | ||
ddb7e6c6 | 189 | bool res=std::lexicographical_compare( |
190 | d_storage.c_str() + ourpos[ourcount] + 1, | |
191 | d_storage.c_str() + ourpos[ourcount] + 1 + *(d_storage.c_str() + ourpos[ourcount]), | |
192 | rhs.d_storage.c_str() + rhspos[rhscount] + 1, | |
193 | rhs.d_storage.c_str() + rhspos[rhscount] + 1 + *(rhs.d_storage.c_str() + rhspos[rhscount]), | |
1352c9b6 | 194 | [](const unsigned char& a, const unsigned char& b) { |
2b62292d | 195 | return dns_tolower(a) < dns_tolower(b); |
ddb7e6c6 | 196 | }); |
197 | ||
198 | // cout<<"Forward: "<<res<<endl; | |
199 | if(res) | |
200 | return true; | |
201 | ||
202 | res=std::lexicographical_compare( rhs.d_storage.c_str() + rhspos[rhscount] + 1, | |
203 | rhs.d_storage.c_str() + rhspos[rhscount] + 1 + *(rhs.d_storage.c_str() + rhspos[rhscount]), | |
204 | d_storage.c_str() + ourpos[ourcount] + 1, | |
205 | d_storage.c_str() + ourpos[ourcount] + 1 + *(d_storage.c_str() + ourpos[ourcount]), | |
1352c9b6 | 206 | [](const unsigned char& a, const unsigned char& b) { |
2b62292d | 207 | return dns_tolower(a) < dns_tolower(b); |
ddb7e6c6 | 208 | }); |
209 | // cout<<"Reverse: "<<res<<endl; | |
210 | if(res) | |
211 | return false; | |
212 | } | |
213 | return false; | |
214 | } | |
215 | ||
216 | ||
6d8bc3c6 | 217 | struct CanonDNSNameCompare: public std::binary_function<DNSName, DNSName, bool> |
218 | { | |
219 | bool operator()(const DNSName&a, const DNSName& b) const | |
220 | { | |
221 | return a.canonCompare(b); | |
222 | } | |
223 | }; | |
224 | ||
6dcedea6 | 225 | inline DNSName operator+(const DNSName& lhs, const DNSName& rhs) |
226 | { | |
227 | DNSName ret=lhs; | |
228 | ret += rhs; | |
229 | return ret; | |
230 | } | |
ceee6652 | 231 | |
40ea5b5b RG |
232 | template<typename T> |
233 | struct SuffixMatchTree | |
234 | { | |
af619119 | 235 | SuffixMatchTree(const std::string& name="", bool endNode_=false) : d_name(name), endNode(endNode_) |
40ea5b5b RG |
236 | {} |
237 | ||
238 | SuffixMatchTree(const SuffixMatchTree& rhs) | |
239 | { | |
af619119 | 240 | d_name = rhs.d_name; |
40ea5b5b RG |
241 | children = rhs.children; |
242 | endNode = rhs.endNode; | |
243 | d_value = rhs.d_value; | |
244 | } | |
af619119 | 245 | std::string d_name; |
40ea5b5b RG |
246 | mutable std::set<SuffixMatchTree> children; |
247 | mutable bool endNode; | |
248 | mutable T d_value; | |
249 | bool operator<(const SuffixMatchTree& rhs) const | |
250 | { | |
af619119 | 251 | return strcasecmp(d_name.c_str(), rhs.d_name.c_str()) < 0; |
40ea5b5b RG |
252 | } |
253 | typedef SuffixMatchTree value_type; | |
254 | ||
255 | template<typename V> | |
256 | void visit(const V& v) const { | |
257 | for(const auto& c : children) | |
258 | c.visit(v); | |
259 | if(endNode) | |
260 | v(*this); | |
261 | } | |
262 | ||
263 | void add(const DNSName& name, const T& t) | |
264 | { | |
265 | add(name.getRawLabels(), t); | |
266 | } | |
267 | ||
268 | void add(std::vector<std::string> labels, const T& value) const | |
269 | { | |
270 | if(labels.empty()) { // this allows insertion of the root | |
271 | endNode=true; | |
272 | d_value=value; | |
273 | } | |
274 | else if(labels.size()==1) { | |
275 | SuffixMatchTree newChild(*labels.begin(), true); | |
1a083287 RG |
276 | auto res=children.insert(newChild); |
277 | if(!res.second) { | |
278 | // we might already have had the node as an | |
279 | // intermediary one, but it's now an end node | |
280 | if(!res.first->endNode) { | |
281 | res.first->endNode = true; | |
282 | } | |
283 | } | |
284 | res.first->d_value = value; | |
40ea5b5b RG |
285 | } |
286 | else { | |
287 | SuffixMatchTree newnode(*labels.rbegin(), false); | |
288 | auto res=children.insert(newnode); | |
40ea5b5b RG |
289 | labels.pop_back(); |
290 | res.first->add(labels, value); | |
291 | } | |
292 | } | |
293 | ||
294 | T* lookup(const DNSName& name) const | |
295 | { | |
296 | if(children.empty()) { // speed up empty set | |
297 | if(endNode) | |
298 | return &d_value; | |
299 | return 0; | |
300 | } | |
301 | return lookup(name.getRawLabels()); | |
302 | } | |
303 | ||
304 | T* lookup(std::vector<std::string> labels) const | |
305 | { | |
306 | if(labels.empty()) { // optimization | |
307 | if(endNode) | |
308 | return &d_value; | |
309 | return 0; | |
310 | } | |
311 | ||
312 | SuffixMatchTree smn(*labels.rbegin()); | |
313 | auto child = children.find(smn); | |
314 | if(child == children.end()) { | |
315 | if(endNode) | |
316 | return &d_value; | |
317 | return 0; | |
318 | } | |
319 | labels.pop_back(); | |
320 | return child->lookup(labels); | |
321 | } | |
322 | ||
323 | }; | |
324 | ||
0eaa51e5 RG |
325 | /* Quest in life: serve as a rapid block list. If you add a DNSName to a root SuffixMatchNode, |
326 | anything part of that domain will return 'true' in check */ | |
327 | struct SuffixMatchNode | |
328 | { | |
329 | SuffixMatchNode() | |
330 | {} | |
331 | std::string d_human; | |
332 | SuffixMatchTree<bool> d_tree; | |
333 | ||
334 | void add(const DNSName& dnsname) | |
335 | { | |
336 | if(!d_human.empty()) | |
337 | d_human.append(", "); | |
338 | d_human += dnsname.toString(); | |
339 | ||
340 | d_tree.add(dnsname, true); | |
341 | } | |
342 | ||
343 | void add(std::vector<std::string> labels) | |
344 | { | |
345 | d_tree.add(labels, true); | |
346 | } | |
347 | ||
348 | bool check(const DNSName& dnsname) const | |
349 | { | |
350 | return d_tree.lookup(dnsname) != nullptr; | |
351 | } | |
352 | ||
353 | std::string toString() const | |
354 | { | |
355 | return d_human; | |
356 | } | |
357 | ||
358 | }; | |
359 | ||
8171ab83 | 360 | std::ostream & operator<<(std::ostream &os, const DNSName& d); |
6106128d | 361 | namespace std { |
362 | template <> | |
363 | struct hash<DNSName> { | |
364 | size_t operator () (const DNSName& dn) const { return dn.hash(0); } | |
365 | }; | |
366 | } | |
bae1b0a2 | 367 | |
368 | DNSName::string_t segmentDNSNameRaw(const char* input); // from ragel | |
c21484df | 369 | bool DNSName::operator==(const DNSName& rhs) const |
370 | { | |
371 | if(rhs.empty() != empty() || rhs.d_storage.size() != d_storage.size()) | |
372 | return false; | |
373 | ||
374 | auto us = d_storage.cbegin(); | |
375 | auto p = rhs.d_storage.cbegin(); | |
376 | for(; us != d_storage.cend() && p != rhs.d_storage.cend(); ++us, ++p) { | |
2b62292d | 377 | if(dns_tolower(*p) != dns_tolower(*us)) |
c21484df | 378 | return false; |
379 | } | |
380 | return true; | |
381 | } | |
382 | ||
383 | extern const DNSName g_rootdnsname, g_wildcarddnsname; |