]>
Commit | Line | Data |
---|---|---|
12c86877 BH |
1 | /* |
2 | PowerDNS Versatile Database Driven Nameserver | |
2c78bd57 | 3 | Copyright (C) 2002 - 2014 PowerDNS.COM BV |
12c86877 BH |
4 | |
5 | This program is free software; you can redistribute it and/or modify | |
22dc646a BH |
6 | it under the terms of the GNU General Public License version 2 |
7 | as published by the Free Software Foundation | |
f782fe38 MH |
8 | |
9 | Additionally, the license of this program contains a special | |
10 | exception which allows to distribute the program in binary form when | |
11 | it is linked against OpenSSL. | |
12c86877 BH |
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 | |
06bd9ccf | 20 | Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA |
12c86877 BH |
21 | */ |
22 | #ifndef PDNS_IPUTILSHH | |
23 | #define PDNS_IPUTILSHH | |
24 | ||
25 | #include <string> | |
092f210a BH |
26 | #include <sys/socket.h> |
27 | #include <netinet/in.h> | |
28 | #include <arpa/inet.h> | |
12c86877 BH |
29 | #include <iostream> |
30 | #include <stdio.h> | |
31 | #include <functional> | |
44845aab | 32 | #include <bitset> |
5c409fa2 | 33 | #include "pdnsexception.hh" |
809fe23f | 34 | #include "misc.hh" |
506a9050 BH |
35 | #include <sys/socket.h> |
36 | #include <netdb.h> | |
335da0ba | 37 | #include <sstream> |
fd4ed0ab BH |
38 | #include <boost/tuple/tuple.hpp> |
39 | #include <boost/tuple/tuple_comparison.hpp> | |
40 | ||
10f4eea8 | 41 | #include "namespaces.hh" |
12c86877 | 42 | |
323c477a PD |
43 | #ifdef __APPLE__ |
44 | #include <libkern/OSByteOrder.h> | |
45 | ||
46 | #define htobe16(x) OSSwapHostToBigInt16(x) | |
47 | #define htole16(x) OSSwapHostToLittleInt16(x) | |
48 | #define be16toh(x) OSSwapBigToHostInt16(x) | |
49 | #define le16toh(x) OSSwapLittleToHostInt16(x) | |
50 | ||
51 | #define htobe32(x) OSSwapHostToBigInt32(x) | |
52 | #define htole32(x) OSSwapHostToLittleInt32(x) | |
53 | #define be32toh(x) OSSwapBigToHostInt32(x) | |
54 | #define le32toh(x) OSSwapLittleToHostInt32(x) | |
55 | ||
56 | #define htobe64(x) OSSwapHostToBigInt64(x) | |
57 | #define htole64(x) OSSwapHostToLittleInt64(x) | |
58 | #define be64toh(x) OSSwapBigToHostInt64(x) | |
59 | #define le64toh(x) OSSwapLittleToHostInt64(x) | |
60 | #endif | |
61 | ||
37d3f960 BH |
62 | union ComboAddress { |
63 | struct sockaddr_in sin4; | |
64 | struct sockaddr_in6 sin6; | |
65 | ||
fd4ed0ab BH |
66 | bool operator==(const ComboAddress& rhs) const |
67 | { | |
68 | if(boost::tie(sin4.sin_family, sin4.sin_port) != boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port)) | |
69 | return false; | |
70 | if(sin4.sin_family == AF_INET) | |
71 | return sin4.sin_addr.s_addr == rhs.sin4.sin_addr.s_addr; | |
72 | else | |
73 | return memcmp(&sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, 16)==0; | |
74 | } | |
75 | ||
37d3f960 BH |
76 | bool operator<(const ComboAddress& rhs) const |
77 | { | |
fd4ed0ab | 78 | if(boost::tie(sin4.sin_family, sin4.sin_port) < boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port)) |
37d3f960 | 79 | return true; |
fd4ed0ab | 80 | if(boost::tie(sin4.sin_family, sin4.sin_port) > boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port)) |
37d3f960 BH |
81 | return false; |
82 | ||
83 | if(sin4.sin_family == AF_INET) | |
84 | return sin4.sin_addr.s_addr < rhs.sin4.sin_addr.s_addr; | |
85 | else | |
9bdaa2e1 | 86 | return memcmp(&sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, 16) < 0; |
37d3f960 BH |
87 | } |
88 | ||
fd4ed0ab BH |
89 | bool operator>(const ComboAddress& rhs) const |
90 | { | |
91 | if(boost::tie(sin4.sin_family, sin4.sin_port) > boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port)) | |
92 | return true; | |
93 | if(boost::tie(sin4.sin_family, sin4.sin_port) < boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port)) | |
94 | return false; | |
95 | ||
96 | if(sin4.sin_family == AF_INET) | |
97 | return sin4.sin_addr.s_addr > rhs.sin4.sin_addr.s_addr; | |
98 | else | |
99 | return memcmp(&sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, 16) > 0; | |
100 | } | |
101 | ||
662d5441 | 102 | struct addressOnlyLessThan: public std::binary_function<ComboAddress, ComboAddress, bool> |
11a7242f BH |
103 | { |
104 | bool operator()(const ComboAddress& a, const ComboAddress& b) const | |
105 | { | |
106 | if(a.sin4.sin_family < b.sin4.sin_family) | |
4957a608 | 107 | return true; |
11a7242f | 108 | if(a.sin4.sin_family > b.sin4.sin_family) |
4957a608 | 109 | return false; |
11a7242f | 110 | if(a.sin4.sin_family == AF_INET) |
4957a608 | 111 | return a.sin4.sin_addr.s_addr < b.sin4.sin_addr.s_addr; |
11a7242f | 112 | else |
4957a608 | 113 | return memcmp(&a.sin6.sin6_addr.s6_addr, &b.sin6.sin6_addr.s6_addr, 16) < 0; |
11a7242f BH |
114 | } |
115 | }; | |
fd4ed0ab | 116 | |
0940e4eb | 117 | struct addressOnlyEqual: public std::binary_function<ComboAddress, ComboAddress, bool> |
118 | { | |
119 | bool operator()(const ComboAddress& a, const ComboAddress& b) const | |
120 | { | |
121 | if(a.sin4.sin_family != b.sin4.sin_family) | |
122 | return false; | |
123 | if(a.sin4.sin_family == AF_INET) | |
124 | return a.sin4.sin_addr.s_addr == b.sin4.sin_addr.s_addr; | |
125 | else | |
126 | return !memcmp(&a.sin6.sin6_addr.s6_addr, &b.sin6.sin6_addr.s6_addr, 16); | |
127 | } | |
128 | }; | |
129 | ||
130 | ||
fd4ed0ab | 131 | socklen_t getSocklen() const |
a9af3782 BH |
132 | { |
133 | if(sin4.sin_family == AF_INET) | |
134 | return sizeof(sin4); | |
135 | else | |
136 | return sizeof(sin6); | |
137 | } | |
fd4ed0ab BH |
138 | |
139 | ComboAddress() | |
140 | { | |
141 | sin4.sin_family=AF_INET; | |
142 | sin4.sin_addr.s_addr=0; | |
143 | sin4.sin_port=0; | |
144 | } | |
145 | ||
a7360cd9 AT |
146 | ComboAddress(const struct sockaddr *sa, socklen_t salen) { |
147 | setSockaddr(sa, salen); | |
148 | }; | |
149 | ||
150 | ComboAddress(const struct sockaddr_in6 *sa) { | |
151 | setSockaddr((const struct sockaddr*)sa, sizeof(struct sockaddr_in6)); | |
152 | }; | |
153 | ||
154 | ComboAddress(const struct sockaddr_in *sa) { | |
155 | setSockaddr((const struct sockaddr*)sa, sizeof(struct sockaddr_in)); | |
156 | }; | |
157 | ||
158 | void setSockaddr(const struct sockaddr *sa, socklen_t salen) { | |
159 | if (salen > sizeof(struct sockaddr_in6)) throw PDNSException("ComboAddress can't handle other than sockaddr_in or sockaddr_in6"); | |
160 | memcpy(this, sa, salen); | |
161 | } | |
162 | ||
85db02c5 | 163 | // 'port' sets a default value in case 'str' does not set a port |
fd4ed0ab BH |
164 | explicit ComboAddress(const string& str, uint16_t port=0) |
165 | { | |
166 | memset(&sin6, 0, sizeof(sin6)); | |
167 | sin4.sin_family = AF_INET; | |
85db02c5 BH |
168 | sin4.sin_port = 0; |
169 | if(makeIPv4sockaddr(str, &sin4)) { | |
fd4ed0ab | 170 | sin6.sin6_family = AF_INET6; |
f71bc087 | 171 | if(makeIPv6sockaddr(str, &sin6) < 0) |
3f81d239 | 172 | throw PDNSException("Unable to convert presentation address '"+ str +"'"); |
b03c5a46 | 173 | |
fd4ed0ab | 174 | } |
85db02c5 BH |
175 | if(!sin4.sin_port) // 'str' overrides port! |
176 | sin4.sin_port=htons(port); | |
fd4ed0ab | 177 | } |
a9af3782 | 178 | |
eb5bae86 | 179 | bool isMappedIPv4() const |
2914b022 BH |
180 | { |
181 | if(sin4.sin_family!=AF_INET6) | |
182 | return false; | |
183 | ||
184 | int n=0; | |
185 | const unsigned char*ptr = (unsigned char*) &sin6.sin6_addr.s6_addr; | |
186 | for(n=0; n < 10; ++n) | |
187 | if(ptr[n]) | |
4957a608 | 188 | return false; |
2914b022 BH |
189 | |
190 | for(; n < 12; ++n) | |
191 | if(ptr[n]!=0xff) | |
4957a608 | 192 | return false; |
2914b022 BH |
193 | |
194 | return true; | |
195 | } | |
196 | ||
eb5bae86 | 197 | ComboAddress mapToIPv4() const |
2914b022 BH |
198 | { |
199 | if(!isMappedIPv4()) | |
3f81d239 | 200 | throw PDNSException("ComboAddress can't map non-mapped IPv6 address back to IPv4"); |
2914b022 BH |
201 | ComboAddress ret; |
202 | ret.sin4.sin_family=AF_INET; | |
11a7242f | 203 | ret.sin4.sin_port=sin4.sin_port; |
2914b022 BH |
204 | |
205 | const unsigned char*ptr = (unsigned char*) &sin6.sin6_addr.s6_addr; | |
206 | ptr+=12; | |
207 | memcpy(&ret.sin4.sin_addr.s_addr, ptr, 4); | |
208 | return ret; | |
209 | } | |
210 | ||
37d3f960 BH |
211 | string toString() const |
212 | { | |
506a9050 BH |
213 | char host[1024]; |
214 | getnameinfo((struct sockaddr*) this, getSocklen(), host, sizeof(host),0, 0, NI_NUMERICHOST); | |
37d3f960 | 215 | |
506a9050 | 216 | return host; |
37d3f960 | 217 | } |
b8c3ea84 BH |
218 | |
219 | string toStringWithPort() const | |
220 | { | |
221 | if(sin4.sin_family==AF_INET) | |
335da0ba | 222 | return toString() + ":" + std::to_string(ntohs(sin4.sin_port)); |
b8c3ea84 | 223 | else |
335da0ba | 224 | return "["+toString() + "]:" + std::to_string(ntohs(sin4.sin_port)); |
b8c3ea84 | 225 | } |
22779196 | 226 | |
227 | void truncate(unsigned int bits); | |
37d3f960 BH |
228 | }; |
229 | ||
12c86877 | 230 | /** This exception is thrown by the Netmask class and by extension by the NetmaskGroup class */ |
3f81d239 | 231 | class NetmaskException: public PDNSException |
12c86877 BH |
232 | { |
233 | public: | |
3f81d239 | 234 | NetmaskException(const string &a) : PDNSException(a) {} |
12c86877 BH |
235 | }; |
236 | ||
37d3f960 BH |
237 | inline ComboAddress makeComboAddress(const string& str) |
238 | { | |
239 | ComboAddress address; | |
240 | address.sin4.sin_family=AF_INET; | |
1e77c17c | 241 | if(inet_pton(AF_INET, str.c_str(), &address.sin4.sin_addr) <= 0) { |
37d3f960 | 242 | address.sin4.sin_family=AF_INET6; |
f71bc087 | 243 | if(makeIPv6sockaddr(str, &address.sin6) < 0) |
4957a608 | 244 | throw NetmaskException("Unable to convert '"+str+"' to a netmask"); |
37d3f960 BH |
245 | } |
246 | return address; | |
247 | } | |
248 | ||
12c86877 BH |
249 | /** This class represents a netmask and can be queried to see if a certain |
250 | IP address is matched by this mask */ | |
12c86877 BH |
251 | class Netmask |
252 | { | |
253 | public: | |
6f97329b BH |
254 | Netmask() |
255 | { | |
256 | d_network.sin4.sin_family=0; // disable this doing anything useful | |
2fd2d93c AT |
257 | d_mask=0; |
258 | d_bits=0; | |
6f97329b BH |
259 | } |
260 | ||
a4c8835f | 261 | Netmask(const ComboAddress& network, uint8_t bits=0xff) |
6f97329b BH |
262 | { |
263 | d_network = network; | |
a4c8835f BH |
264 | |
265 | if(bits == 0xff) | |
266 | bits = (network.sin4.sin_family == AF_INET) ? 32 : 128; | |
267 | ||
6f97329b BH |
268 | d_bits = bits; |
269 | if(d_bits<32) | |
270 | d_mask=~(0xFFFFFFFF>>d_bits); | |
271 | else | |
272 | d_mask=0xFFFFFFFF; // not actually used for IPv6 | |
273 | } | |
274 | ||
12c86877 BH |
275 | //! Constructor supplies the mask, which cannot be changed |
276 | Netmask(const string &mask) | |
277 | { | |
37d3f960 BH |
278 | pair<string,string> split=splitField(mask,'/'); |
279 | d_network=makeComboAddress(split.first); | |
280 | ||
281 | if(!split.second.empty()) { | |
335da0ba | 282 | d_bits = pdns_stou(split.second); |
37d3f960 | 283 | if(d_bits<32) |
4957a608 | 284 | d_mask=~(0xFFFFFFFF>>d_bits); |
8519b8a2 | 285 | else |
4957a608 | 286 | d_mask=0xFFFFFFFF; |
37d3f960 BH |
287 | } |
288 | else if(d_network.sin4.sin_family==AF_INET) { | |
289 | d_bits = 32; | |
290 | d_mask = 0xFFFFFFFF; | |
291 | } | |
5c1def57 | 292 | else { |
37d3f960 | 293 | d_bits=128; |
5c1def57 BH |
294 | d_mask=0; // silence silly warning - d_mask is unused for IPv6 |
295 | } | |
12c86877 BH |
296 | } |
297 | ||
2914b022 BH |
298 | bool match(const ComboAddress& ip) const |
299 | { | |
300 | return match(&ip); | |
301 | } | |
302 | ||
12c86877 | 303 | //! If this IP address in socket address matches |
37d3f960 | 304 | bool match(const ComboAddress *ip) const |
12c86877 | 305 | { |
37d3f960 BH |
306 | if(d_network.sin4.sin_family != ip->sin4.sin_family) { |
307 | return false; | |
308 | } | |
309 | if(d_network.sin4.sin_family == AF_INET) { | |
310 | return match4(htonl((unsigned int)ip->sin4.sin_addr.s_addr)); | |
311 | } | |
312 | if(d_network.sin6.sin6_family == AF_INET6) { | |
313 | uint8_t bytes=d_bits/8, n; | |
314 | const uint8_t *us=(const uint8_t*) &d_network.sin6.sin6_addr.s6_addr; | |
315 | const uint8_t *them=(const uint8_t*) &ip->sin6.sin6_addr.s6_addr; | |
316 | ||
317 | for(n=0; n < bytes; ++n) { | |
4957a608 BH |
318 | if(us[n]!=them[n]) { |
319 | return false; | |
320 | } | |
37d3f960 BH |
321 | } |
322 | // still here, now match remaining bits | |
f0739fb6 | 323 | uint8_t bits= d_bits % 8; |
37d3f960 | 324 | uint8_t mask= ~(0xFF>>bits); |
f0739fb6 | 325 | |
37d3f960 BH |
326 | return((us[n] & mask) == (them[n] & mask)); |
327 | } | |
328 | return false; | |
12c86877 BH |
329 | } |
330 | ||
331 | //! If this ASCII IP address matches | |
332 | bool match(const string &ip) const | |
333 | { | |
37d3f960 BH |
334 | ComboAddress address=makeComboAddress(ip); |
335 | return match(&address); | |
12c86877 BH |
336 | } |
337 | ||
338 | //! If this IP address in native format matches | |
37d3f960 | 339 | bool match4(uint32_t ip) const |
12c86877 | 340 | { |
37d3f960 | 341 | return (ip & d_mask) == (ntohl(d_network.sin4.sin_addr.s_addr) & d_mask); |
12c86877 BH |
342 | } |
343 | ||
2c95fc65 BH |
344 | string toString() const |
345 | { | |
335da0ba | 346 | return d_network.toString()+"/"+std::to_string((unsigned int)d_bits); |
2c95fc65 BH |
347 | } |
348 | ||
a4c8835f BH |
349 | string toStringNoMask() const |
350 | { | |
351 | return d_network.toString(); | |
352 | } | |
9f84a557 | 353 | const ComboAddress& getNetwork() const |
a4c8835f BH |
354 | { |
355 | return d_network; | |
356 | } | |
357 | int getBits() const | |
358 | { | |
359 | return d_bits; | |
360 | } | |
709ca59f AT |
361 | bool isIpv6() const |
362 | { | |
363 | return d_network.sin6.sin6_family == AF_INET6; | |
364 | } | |
365 | bool isIpv4() const | |
366 | { | |
367 | return d_network.sin4.sin_family == AF_INET; | |
368 | } | |
644dd1da | 369 | |
370 | bool operator<(const Netmask& rhs) const | |
371 | { | |
372 | return tie(d_network, d_bits) < tie(rhs.d_network, rhs.d_bits); | |
373 | } | |
39ec5d29 | 374 | |
375 | bool operator==(const Netmask& rhs) const | |
376 | { | |
377 | return tie(d_network, d_bits) == tie(rhs.d_network, rhs.d_bits); | |
378 | } | |
379 | ||
87e665b1 | 380 | bool empty() const |
381 | { | |
382 | return d_network.sin4.sin_family==0; | |
383 | } | |
384 | ||
12c86877 | 385 | private: |
37d3f960 | 386 | ComboAddress d_network; |
092f210a | 387 | uint32_t d_mask; |
37d3f960 | 388 | uint8_t d_bits; |
12c86877 BH |
389 | }; |
390 | ||
44845aab AT |
391 | /** Per-bit binary tree map implementation with <Netmask,T> pair. |
392 | * | |
393 | * This is an binary tree implementation for storing attributes for IPv4 and IPv6 prefixes. | |
394 | * The most simple use case is simple NetmaskTree<bool> used by NetmaskGroup, which only | |
395 | * wants to know if given IP address is matched in the prefixes stored. | |
396 | * | |
397 | * This element is useful for anything that needs to *STORE* prefixes, and *MATCH* IP addresses | |
398 | * to a *LIST* of *PREFIXES*. Not the other way round. | |
399 | * | |
400 | * You can store IPv4 and IPv6 addresses to same tree, separate payload storage is kept per AFI. | |
401 | * | |
402 | * To erase something copy values to new tree sans the value you want to erase. | |
403 | * | |
404 | * Use swap if you need to move the tree to another NetmaskTree instance, it is WAY faster | |
405 | * than using copy ctor or assigment operator, since it moves the nodes and tree root to | |
406 | * new home instead of actually recreating the tree. | |
407 | * | |
408 | * Please see NetmaskGroup for example of simple use case. Other usecases can be found | |
409 | * from GeoIPBackend and Sortlist, and from dnsdist. | |
410 | */ | |
411 | template <typename T> | |
412 | class NetmaskTree { | |
413 | public: | |
414 | typedef Netmask key_type; | |
415 | typedef T value_type; | |
416 | typedef std::pair<key_type,value_type> node_type; | |
417 | typedef size_t size_type; | |
418 | ||
419 | private: | |
420 | /** Single node in tree, internal use only. | |
421 | */ | |
422 | class TreeNode : boost::noncopyable { | |
423 | public: | |
424 | explicit TreeNode(int bits) noexcept : parent(NULL),d_bits(bits) { | |
425 | } | |
426 | ||
427 | //<! Makes a left node with one more bit than parent | |
428 | TreeNode* make_left() { | |
429 | if (!left) { | |
430 | left = unique_ptr<TreeNode>(new TreeNode(d_bits+1)); | |
431 | left->parent = this; | |
432 | } | |
433 | return left.get(); | |
434 | } | |
435 | ||
436 | //<! Makes a right node with one more bit than parent | |
437 | TreeNode* make_right() { | |
438 | if (!right) { | |
439 | right = unique_ptr<TreeNode>(new TreeNode(d_bits+1)); | |
440 | right->parent = this; | |
441 | } | |
442 | return right.get(); | |
443 | } | |
444 | ||
445 | unique_ptr<TreeNode> left; | |
446 | unique_ptr<TreeNode> right; | |
447 | TreeNode* parent; | |
448 | ||
449 | unique_ptr<node_type> node4; //<! IPv4 value-pair | |
450 | unique_ptr<node_type> node6; //<! IPv6 value-pair | |
451 | ||
452 | int d_bits; //<! How many bits have been used so far | |
453 | }; | |
454 | ||
455 | public: | |
456 | NetmaskTree() noexcept { | |
457 | } | |
458 | ||
459 | NetmaskTree(const NetmaskTree& rhs) { | |
460 | // it is easier to copy the nodes than tree. | |
461 | // also acts as handy compactor | |
462 | for(auto const& node: rhs._nodes) | |
463 | insert(node->first).second = node->second; | |
464 | } | |
465 | ||
466 | NetmaskTree& operator=(const NetmaskTree& rhs) { | |
467 | clear(); | |
468 | // see above. | |
469 | for(auto const& node: rhs._nodes) | |
470 | insert(node->first).second = node->second; | |
471 | return *this; | |
472 | } | |
473 | ||
44845aab AT |
474 | const typename std::vector<node_type*>::const_iterator begin() const { return _nodes.begin(); } |
475 | const typename std::vector<node_type*>::const_iterator end() const { return _nodes.end(); } | |
476 | ||
477 | typename std::vector<node_type*>::iterator begin() { return _nodes.begin(); } | |
478 | typename std::vector<node_type*>::iterator end() { return _nodes.end(); } | |
479 | ||
480 | node_type& insert(const string &mask) { | |
481 | return insert(key_type(mask)); | |
482 | } | |
483 | ||
484 | //<! Creates new value-pair in tree and returns it. | |
485 | node_type& insert(const key_type& key) { | |
486 | // lazily initialize tree on first insert. | |
487 | if (!root) root = unique_ptr<TreeNode>(new TreeNode(0)); | |
488 | TreeNode* node = root.get(); | |
489 | node_type* value = nullptr; | |
490 | ||
491 | if (key.getNetwork().sin4.sin_family == AF_INET) { | |
492 | std::bitset<32> addr(be32toh(key.getNetwork().sin4.sin_addr.s_addr)); | |
493 | int bits = 0; | |
494 | // we turn left on 0 and right on 1 | |
495 | while(bits < key.getBits()) { | |
496 | uint8_t val = addr[31-bits]; | |
497 | if (val) | |
498 | node = node->make_right(); | |
499 | else | |
500 | node = node->make_left(); | |
501 | bits++; | |
502 | } | |
503 | // only create node if not yet assigned | |
504 | if (!node->node4) { | |
505 | node->node4 = unique_ptr<node_type>(new node_type()); | |
506 | _nodes.push_back(node->node4.get()); | |
507 | } | |
508 | value = node->node4.get(); | |
509 | } else { | |
510 | uint64_t* addr = (uint64_t*)key.getNetwork().sin6.sin6_addr.s6_addr; | |
511 | std::bitset<64> addr_low(be64toh(addr[1])); | |
512 | std::bitset<64> addr_high(be64toh(addr[0])); | |
513 | int bits = 0; | |
514 | while(bits < key.getBits()) { | |
515 | uint8_t val; | |
516 | // we use high address until we are | |
517 | if (bits < 64) val = addr_high[63-bits]; | |
518 | // past 64 bits, and start using low address | |
519 | else val = addr_low[127-bits]; | |
520 | ||
521 | // we turn left on 0 and right on 1 | |
522 | if (val) | |
523 | node = node->make_right(); | |
524 | else | |
525 | node = node->make_left(); | |
526 | bits++; | |
527 | } | |
528 | // only create node if not yet assigned | |
529 | if (!node->node6) { | |
530 | node->node6 = unique_ptr<node_type>(new node_type()); | |
531 | _nodes.push_back(node->node6.get()); | |
532 | } | |
533 | value = node->node6.get(); | |
534 | } | |
535 | // assign key | |
536 | value->first = key; | |
537 | return *value; | |
538 | } | |
539 | ||
2dfbbc41 | 540 | //<! Creates or updates value |
44845aab AT |
541 | void insert_or_assign(const key_type& mask, const value_type& value) { |
542 | insert(mask).second = value; | |
543 | } | |
544 | ||
e6419866 AT |
545 | void insert_or_assign(const string& mask, const value_type& value) { |
546 | insert(key_type(mask)).second = value; | |
44845aab AT |
547 | } |
548 | ||
41d0adb7 AT |
549 | //<! check if given key is present in TreeMap |
550 | bool has_key(const key_type& key) const { | |
551 | const node_type *ptr = lookup(key); | |
552 | return ptr && ptr->first == key; | |
553 | } | |
554 | ||
2dfbbc41 | 555 | //<! Returns "best match" for key_type, which might not be value |
44845aab AT |
556 | const node_type* lookup(const key_type& value) const { |
557 | return lookup(value.getNetwork(), value.getBits()); | |
558 | } | |
559 | ||
2dfbbc41 | 560 | //<! Perform best match lookup for value, using at most max_bits |
44845aab AT |
561 | const node_type* lookup(const ComboAddress& value, int max_bits = 128) const { |
562 | if (!root) return nullptr; | |
563 | ||
564 | TreeNode *node = root.get(); | |
565 | node_type *ret = nullptr; | |
566 | ||
567 | // exact same thing as above, except | |
568 | if (value.sin4.sin_family == AF_INET) { | |
569 | max_bits = std::max(0,std::min(max_bits,32)); | |
570 | std::bitset<32> addr(be32toh(value.sin4.sin_addr.s_addr)); | |
571 | int bits = 0; | |
572 | ||
573 | while(bits < max_bits) { | |
574 | // ...we keep track of last non-empty node | |
575 | if (node->node4) ret = node->node4.get(); | |
576 | uint8_t val = addr[31-bits]; | |
577 | // ...and we don't create left/right hand | |
578 | if (val) { | |
579 | if (node->right) node = node->right.get(); | |
580 | // ..and we break when road ends | |
581 | else break; | |
582 | } else { | |
583 | if (node->left) node = node->left.get(); | |
584 | else break; | |
585 | } | |
586 | bits++; | |
587 | } | |
588 | // needed if we did not find one in loop | |
589 | if (node->node4) ret = node->node4.get(); | |
590 | } else { | |
591 | uint64_t* addr = (uint64_t*)value.sin6.sin6_addr.s6_addr; | |
592 | max_bits = std::max(0,std::min(max_bits,128)); | |
593 | std::bitset<64> addr_low(be64toh(addr[1])); | |
594 | std::bitset<64> addr_high(be64toh(addr[0])); | |
595 | int bits = 0; | |
596 | while(bits < max_bits) { | |
597 | if (node->node6) ret = node->node6.get(); | |
598 | uint8_t val; | |
599 | if (bits < 64) val = addr_high[63-bits]; | |
600 | else val = addr_low[127-bits]; | |
601 | if (val) { | |
602 | if (node->right) node = node->right.get(); | |
603 | else break; | |
604 | } else { | |
605 | if (node->left) node = node->left.get(); | |
606 | else break; | |
607 | } | |
608 | bits++; | |
609 | } | |
610 | if (node->node6) ret = node->node6.get(); | |
611 | } | |
612 | ||
613 | // this can be nullptr. | |
614 | return ret; | |
615 | } | |
616 | ||
2dfbbc41 | 617 | //<! Removes key from TreeMap. This does not clean up the tree. |
44845aab AT |
618 | void erase(const key_type& key) { |
619 | TreeNode *node = root.get(); | |
620 | ||
621 | // no tree, no value | |
622 | if ( node == nullptr ) return; | |
623 | ||
624 | // exact same thing as above, except | |
625 | if (key.getNetwork().sin4.sin_family == AF_INET) { | |
626 | std::bitset<32> addr(be32toh(key.getNetwork().sin4.sin_addr.s_addr)); | |
627 | int bits = 0; | |
628 | while(node && bits < key.getBits()) { | |
629 | uint8_t val = addr[31-bits]; | |
630 | if (val) { | |
631 | node = node->right.get(); | |
632 | } else { | |
633 | node = node->left.get(); | |
634 | } | |
635 | bits++; | |
636 | } | |
637 | if (node) { | |
638 | for(auto it = _nodes.begin(); it != _nodes.end(); it++) | |
639 | if (node->node4.get() == *it) _nodes.erase(it); | |
640 | node->node4.reset(); | |
641 | } | |
642 | } else { | |
643 | uint64_t* addr = (uint64_t*)key.getNetwork().sin6.sin6_addr.s6_addr; | |
644 | std::bitset<64> addr_low(be64toh(addr[1])); | |
645 | std::bitset<64> addr_high(be64toh(addr[0])); | |
646 | int bits = 0; | |
647 | while(node && bits < key.getBits()) { | |
648 | uint8_t val; | |
649 | if (bits < 64) val = addr_high[63-bits]; | |
650 | else val = addr_low[127-bits]; | |
651 | if (val) { | |
652 | node = node->right.get(); | |
653 | } else { | |
654 | node = node->left.get(); | |
655 | } | |
656 | bits++; | |
657 | } | |
658 | if (node) { | |
659 | for(auto it = _nodes.begin(); it != _nodes.end(); it++) | |
660 | if (node->node4.get() == *it) _nodes.erase(it); | |
661 | node->node6.reset(); | |
662 | } | |
663 | } | |
664 | } | |
665 | ||
666 | void erase(const string& key) { | |
667 | erase(key_type(key)); | |
668 | } | |
669 | ||
670 | //<! checks whether the container is empty. | |
671 | bool empty() const { | |
672 | return _nodes.empty(); | |
673 | } | |
674 | ||
675 | //<! returns the number of elements | |
676 | size_type size() const { | |
677 | return _nodes.size(); | |
678 | } | |
679 | ||
680 | //<! See if given ComboAddress matches any prefix | |
681 | bool match(const ComboAddress& value) const { | |
682 | return (lookup(value) != nullptr); | |
683 | } | |
684 | ||
685 | bool match(const std::string& value) const { | |
686 | return match(ComboAddress(value)); | |
687 | } | |
688 | ||
689 | //<! Clean out the tree | |
690 | void clear() { | |
691 | _nodes.clear(); | |
692 | root.reset(nullptr); | |
693 | } | |
694 | ||
695 | //<! swaps the contents, rhs is left with nullptr. | |
696 | void swap(NetmaskTree& rhs) { | |
697 | root.swap(rhs.root); | |
698 | _nodes.swap(rhs._nodes); | |
699 | } | |
700 | ||
701 | private: | |
702 | unique_ptr<TreeNode> root; //<! Root of our tree | |
703 | std::vector<node_type*> _nodes; //<! Container for actual values | |
704 | }; | |
705 | ||
12c86877 BH |
706 | /** This class represents a group of supplemental Netmask classes. An IP address matchs |
707 | if it is matched by zero or more of the Netmask classes within. | |
708 | */ | |
709 | class NetmaskGroup | |
710 | { | |
711 | public: | |
712 | //! If this IP address is matched by any of the classes within | |
60af67b8 | 713 | |
1e77c17c | 714 | bool match(const ComboAddress *ip) const |
12c86877 | 715 | { |
5ac553e1 | 716 | return tree.match(*ip); |
12c86877 | 717 | } |
60af67b8 | 718 | |
1e77c17c | 719 | bool match(const ComboAddress& ip) const |
60af67b8 | 720 | { |
721 | return match(&ip); | |
722 | } | |
723 | ||
376effcf | 724 | //! Add this string to the list of possible matches |
12c86877 BH |
725 | void addMask(const string &ip) |
726 | { | |
5ac553e1 | 727 | addMask(Netmask(ip)); |
12c86877 | 728 | } |
68b011bd | 729 | |
376effcf | 730 | //! Add this Netmask to the list of possible matches |
731 | void addMask(const Netmask& nm) | |
732 | { | |
5ac553e1 | 733 | tree.insert(nm); |
376effcf | 734 | } |
735 | ||
68b011bd KM |
736 | void clear() |
737 | { | |
5ac553e1 | 738 | tree.clear(); |
68b011bd KM |
739 | } |
740 | ||
5ac553e1 | 741 | bool empty() const |
12c86877 | 742 | { |
5ac553e1 | 743 | return tree.empty(); |
12c86877 BH |
744 | } |
745 | ||
5ac553e1 | 746 | size_t size() const |
2c95fc65 | 747 | { |
5ac553e1 | 748 | return tree.size(); |
2c95fc65 BH |
749 | } |
750 | ||
751 | string toString() const | |
752 | { | |
753 | ostringstream str; | |
5ac553e1 AT |
754 | for(auto iter = tree.begin(); iter != tree.end(); ++iter) { |
755 | if(iter != tree.begin()) | |
4957a608 | 756 | str <<", "; |
5ac553e1 | 757 | str<<(*iter)->first.toString(); |
2c95fc65 BH |
758 | } |
759 | return str.str(); | |
760 | } | |
761 | ||
41942bb3 CH |
762 | void toStringVector(vector<string>* vec) const |
763 | { | |
5ac553e1 AT |
764 | for(auto iter = tree.begin(); iter != tree.end(); ++iter) |
765 | vec->push_back((*iter)->first.toString()); | |
41942bb3 CH |
766 | } |
767 | ||
68b011bd KM |
768 | void toMasks(const string &ips) |
769 | { | |
770 | vector<string> parts; | |
771 | stringtok(parts, ips, ", \t"); | |
772 | ||
773 | for (vector<string>::const_iterator iter = parts.begin(); iter != parts.end(); ++iter) | |
774 | addMask(*iter); | |
775 | } | |
776 | ||
12c86877 | 777 | private: |
5ac553e1 | 778 | NetmaskTree<bool> tree; |
12c86877 BH |
779 | }; |
780 | ||
002c970a | 781 | |
60c8afa8 | 782 | struct SComboAddress |
783 | { | |
784 | SComboAddress(const ComboAddress& orig) : ca(orig) {} | |
785 | ComboAddress ca; | |
786 | bool operator<(const SComboAddress& rhs) const | |
787 | { | |
788 | return ComboAddress::addressOnlyLessThan()(ca, rhs.ca); | |
789 | } | |
790 | operator const ComboAddress&() | |
791 | { | |
792 | return ca; | |
793 | } | |
794 | }; | |
795 | ||
796 | ||
002c970a | 797 | int SSocket(int family, int type, int flags); |
798 | int SConnect(int sockfd, const ComboAddress& remote); | |
799 | int SBind(int sockfd, const ComboAddress& local); | |
800 | int SAccept(int sockfd, ComboAddress& remote); | |
801 | int SListen(int sockfd, int limit); | |
802 | int SSetsockopt(int sockfd, int level, int opname, int value); | |
803 | ||
3e3f0358 | 804 | #if defined(IP_PKTINFO) |
805 | #define GEN_IP_PKTINFO IP_PKTINFO | |
806 | #elif defined(IP_RECVDSTADDR) | |
807 | #define GEN_IP_PKTINFO IP_RECVDSTADDR | |
808 | #endif | |
809 | bool IsAnyAddress(const ComboAddress& addr); | |
810 | bool HarvestDestinationAddress(struct msghdr* msgh, ComboAddress* destination); | |
811 | bool HarvestTimestamp(struct msghdr* msgh, struct timeval* tv); | |
b71b60ee | 812 | void fillMSGHdr(struct msghdr* msgh, struct iovec* iov, char* cbuf, size_t cbufsize, char* data, size_t datalen, ComboAddress* addr); |
549d63c9 | 813 | int sendfromto(int sock, const char* data, int len, int flags, const ComboAddress& from, const ComboAddress& to); |
12c86877 | 814 | #endif |
f9f9592e AT |
815 | |
816 | extern template class NetmaskTree<bool>; |