]>
Commit | Line | Data |
---|---|---|
12c86877 | 1 | /* |
12471842 PL |
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 | */ | |
12c86877 BH |
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 | ||
28fe507d | 62 | #ifdef __sun |
b0228347 AT |
63 | |
64 | #define htobe16(x) BE_16(x) | |
65 | #define htole16(x) LE_16(x) | |
28fe507d RD |
66 | #define be16toh(x) BE_IN16(&(x)) |
67 | #define le16toh(x) LE_IN16(&(x)) | |
b0228347 AT |
68 | |
69 | #define htobe32(x) BE_32(x) | |
70 | #define htole32(x) LE_32(x) | |
28fe507d RD |
71 | #define be32toh(x) BE_IN32(&(x)) |
72 | #define le32toh(x) LE_IN32(&(x)) | |
b0228347 AT |
73 | |
74 | #define htobe64(x) BE_64(x) | |
75 | #define htole64(x) LE_64(x) | |
28fe507d RD |
76 | #define be64toh(x) BE_IN64(&(x)) |
77 | #define le64toh(x) LE_IN64(&(x)) | |
b0228347 AT |
78 | |
79 | #endif | |
80 | ||
e95bd1ae RK |
81 | #ifdef __FreeBSD__ |
82 | #include <sys/endian.h> | |
83 | #endif | |
84 | ||
4d39d7f3 TIH |
85 | #if defined(__NetBSD__) && defined(IP_PKTINFO) && !defined(IP_SENDSRCADDR) |
86 | // The IP_PKTINFO option in NetBSD was incompatible with Linux until a | |
87 | // change that also introduced IP_SENDSRCADDR for FreeBSD compatibility. | |
88 | #undef IP_PKTINFO | |
89 | #endif | |
90 | ||
37d3f960 BH |
91 | union ComboAddress { |
92 | struct sockaddr_in sin4; | |
93 | struct sockaddr_in6 sin6; | |
94 | ||
fd4ed0ab BH |
95 | bool operator==(const ComboAddress& rhs) const |
96 | { | |
97 | if(boost::tie(sin4.sin_family, sin4.sin_port) != boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port)) | |
98 | return false; | |
99 | if(sin4.sin_family == AF_INET) | |
100 | return sin4.sin_addr.s_addr == rhs.sin4.sin_addr.s_addr; | |
101 | else | |
a683e8bd | 102 | return memcmp(&sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, sizeof(sin6.sin6_addr.s6_addr))==0; |
fd4ed0ab BH |
103 | } |
104 | ||
bb6f86bd PL |
105 | bool operator!=(const ComboAddress& rhs) const |
106 | { | |
107 | return(!operator==(rhs)); | |
108 | } | |
109 | ||
37d3f960 BH |
110 | bool operator<(const ComboAddress& rhs) const |
111 | { | |
f563fff4 | 112 | if(sin4.sin_family == 0) { |
113 | return false; | |
114 | } | |
fd4ed0ab | 115 | if(boost::tie(sin4.sin_family, sin4.sin_port) < boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port)) |
37d3f960 | 116 | return true; |
fd4ed0ab | 117 | if(boost::tie(sin4.sin_family, sin4.sin_port) > boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port)) |
37d3f960 BH |
118 | return false; |
119 | ||
120 | if(sin4.sin_family == AF_INET) | |
121 | return sin4.sin_addr.s_addr < rhs.sin4.sin_addr.s_addr; | |
122 | else | |
a683e8bd | 123 | return memcmp(&sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, sizeof(sin6.sin6_addr.s6_addr)) < 0; |
37d3f960 BH |
124 | } |
125 | ||
fd4ed0ab BH |
126 | bool operator>(const ComboAddress& rhs) const |
127 | { | |
5f15ee47 | 128 | return rhs.operator<(*this); |
fd4ed0ab BH |
129 | } |
130 | ||
545725f2 | 131 | struct addressOnlyHash |
132 | { | |
133 | uint32_t operator()(const ComboAddress& ca) const | |
134 | { | |
135 | const unsigned char* start; | |
136 | int len; | |
137 | if(ca.sin4.sin_family == AF_INET) { | |
138 | start =(const unsigned char*)&ca.sin4.sin_addr.s_addr; | |
139 | len=4; | |
140 | } | |
141 | else { | |
142 | start =(const unsigned char*)&ca.sin6.sin6_addr.s6_addr; | |
143 | len=16; | |
144 | } | |
145 | return burtle(start, len, 0); | |
146 | } | |
147 | }; | |
148 | ||
662d5441 | 149 | struct addressOnlyLessThan: public std::binary_function<ComboAddress, ComboAddress, bool> |
11a7242f BH |
150 | { |
151 | bool operator()(const ComboAddress& a, const ComboAddress& b) const | |
152 | { | |
153 | if(a.sin4.sin_family < b.sin4.sin_family) | |
4957a608 | 154 | return true; |
11a7242f | 155 | if(a.sin4.sin_family > b.sin4.sin_family) |
4957a608 | 156 | return false; |
11a7242f | 157 | if(a.sin4.sin_family == AF_INET) |
4957a608 | 158 | return a.sin4.sin_addr.s_addr < b.sin4.sin_addr.s_addr; |
11a7242f | 159 | else |
a683e8bd | 160 | return memcmp(&a.sin6.sin6_addr.s6_addr, &b.sin6.sin6_addr.s6_addr, sizeof(a.sin6.sin6_addr.s6_addr)) < 0; |
11a7242f BH |
161 | } |
162 | }; | |
fd4ed0ab | 163 | |
0940e4eb | 164 | struct addressOnlyEqual: public std::binary_function<ComboAddress, ComboAddress, bool> |
165 | { | |
166 | bool operator()(const ComboAddress& a, const ComboAddress& b) const | |
167 | { | |
168 | if(a.sin4.sin_family != b.sin4.sin_family) | |
169 | return false; | |
170 | if(a.sin4.sin_family == AF_INET) | |
171 | return a.sin4.sin_addr.s_addr == b.sin4.sin_addr.s_addr; | |
172 | else | |
a683e8bd | 173 | return !memcmp(&a.sin6.sin6_addr.s6_addr, &b.sin6.sin6_addr.s6_addr, sizeof(a.sin6.sin6_addr.s6_addr)); |
0940e4eb | 174 | } |
175 | }; | |
176 | ||
177 | ||
fd4ed0ab | 178 | socklen_t getSocklen() const |
a9af3782 BH |
179 | { |
180 | if(sin4.sin_family == AF_INET) | |
181 | return sizeof(sin4); | |
182 | else | |
183 | return sizeof(sin6); | |
184 | } | |
fd4ed0ab BH |
185 | |
186 | ComboAddress() | |
187 | { | |
188 | sin4.sin_family=AF_INET; | |
189 | sin4.sin_addr.s_addr=0; | |
190 | sin4.sin_port=0; | |
5cc8371b RG |
191 | sin6.sin6_scope_id = 0; |
192 | sin6.sin6_flowinfo = 0; | |
fd4ed0ab BH |
193 | } |
194 | ||
a7360cd9 AT |
195 | ComboAddress(const struct sockaddr *sa, socklen_t salen) { |
196 | setSockaddr(sa, salen); | |
197 | }; | |
198 | ||
199 | ComboAddress(const struct sockaddr_in6 *sa) { | |
200 | setSockaddr((const struct sockaddr*)sa, sizeof(struct sockaddr_in6)); | |
201 | }; | |
202 | ||
203 | ComboAddress(const struct sockaddr_in *sa) { | |
204 | setSockaddr((const struct sockaddr*)sa, sizeof(struct sockaddr_in)); | |
205 | }; | |
206 | ||
207 | void setSockaddr(const struct sockaddr *sa, socklen_t salen) { | |
208 | if (salen > sizeof(struct sockaddr_in6)) throw PDNSException("ComboAddress can't handle other than sockaddr_in or sockaddr_in6"); | |
209 | memcpy(this, sa, salen); | |
210 | } | |
211 | ||
85db02c5 | 212 | // 'port' sets a default value in case 'str' does not set a port |
fd4ed0ab BH |
213 | explicit ComboAddress(const string& str, uint16_t port=0) |
214 | { | |
215 | memset(&sin6, 0, sizeof(sin6)); | |
216 | sin4.sin_family = AF_INET; | |
85db02c5 BH |
217 | sin4.sin_port = 0; |
218 | if(makeIPv4sockaddr(str, &sin4)) { | |
fd4ed0ab | 219 | sin6.sin6_family = AF_INET6; |
f71bc087 | 220 | if(makeIPv6sockaddr(str, &sin6) < 0) |
3f81d239 | 221 | throw PDNSException("Unable to convert presentation address '"+ str +"'"); |
b03c5a46 | 222 | |
fd4ed0ab | 223 | } |
85db02c5 BH |
224 | if(!sin4.sin_port) // 'str' overrides port! |
225 | sin4.sin_port=htons(port); | |
fd4ed0ab | 226 | } |
a9af3782 | 227 | |
a94673ea RG |
228 | bool isIPv6() const |
229 | { | |
230 | return sin4.sin_family == AF_INET6; | |
231 | } | |
232 | bool isIPv4() const | |
233 | { | |
234 | return sin4.sin_family == AF_INET; | |
235 | } | |
236 | ||
eb5bae86 | 237 | bool isMappedIPv4() const |
2914b022 BH |
238 | { |
239 | if(sin4.sin_family!=AF_INET6) | |
240 | return false; | |
241 | ||
242 | int n=0; | |
243 | const unsigned char*ptr = (unsigned char*) &sin6.sin6_addr.s6_addr; | |
244 | for(n=0; n < 10; ++n) | |
245 | if(ptr[n]) | |
4957a608 | 246 | return false; |
2914b022 BH |
247 | |
248 | for(; n < 12; ++n) | |
249 | if(ptr[n]!=0xff) | |
4957a608 | 250 | return false; |
2914b022 BH |
251 | |
252 | return true; | |
253 | } | |
254 | ||
eb5bae86 | 255 | ComboAddress mapToIPv4() const |
2914b022 BH |
256 | { |
257 | if(!isMappedIPv4()) | |
3f81d239 | 258 | throw PDNSException("ComboAddress can't map non-mapped IPv6 address back to IPv4"); |
2914b022 BH |
259 | ComboAddress ret; |
260 | ret.sin4.sin_family=AF_INET; | |
11a7242f | 261 | ret.sin4.sin_port=sin4.sin_port; |
2914b022 BH |
262 | |
263 | const unsigned char*ptr = (unsigned char*) &sin6.sin6_addr.s6_addr; | |
a683e8bd RG |
264 | ptr+=(sizeof(sin6.sin6_addr.s6_addr) - sizeof(ret.sin4.sin_addr.s_addr)); |
265 | memcpy(&ret.sin4.sin_addr.s_addr, ptr, sizeof(ret.sin4.sin_addr.s_addr)); | |
2914b022 BH |
266 | return ret; |
267 | } | |
268 | ||
37d3f960 BH |
269 | string toString() const |
270 | { | |
506a9050 | 271 | char host[1024]; |
5cc8371b | 272 | int retval = 0; |
f4352636 | 273 | if(sin4.sin_family && !(retval = getnameinfo((struct sockaddr*) this, getSocklen(), host, sizeof(host),0, 0, NI_NUMERICHOST))) |
c44d3917 | 274 | return host; |
275 | else | |
f4352636 | 276 | return "invalid "+string(gai_strerror(retval)); |
37d3f960 | 277 | } |
b8c3ea84 BH |
278 | |
279 | string toStringWithPort() const | |
280 | { | |
281 | if(sin4.sin_family==AF_INET) | |
335da0ba | 282 | return toString() + ":" + std::to_string(ntohs(sin4.sin_port)); |
b8c3ea84 | 283 | else |
335da0ba | 284 | return "["+toString() + "]:" + std::to_string(ntohs(sin4.sin_port)); |
b8c3ea84 | 285 | } |
22779196 | 286 | |
5b6099b2 | 287 | void truncate(unsigned int bits) noexcept; |
0affb140 RG |
288 | |
289 | uint16_t getPort() const | |
290 | { | |
291 | return ntohs(sin4.sin_port); | |
292 | } | |
293 | ||
37d3f960 BH |
294 | }; |
295 | ||
12c86877 | 296 | /** This exception is thrown by the Netmask class and by extension by the NetmaskGroup class */ |
3f81d239 | 297 | class NetmaskException: public PDNSException |
12c86877 BH |
298 | { |
299 | public: | |
3f81d239 | 300 | NetmaskException(const string &a) : PDNSException(a) {} |
12c86877 BH |
301 | }; |
302 | ||
37d3f960 BH |
303 | inline ComboAddress makeComboAddress(const string& str) |
304 | { | |
305 | ComboAddress address; | |
306 | address.sin4.sin_family=AF_INET; | |
1e77c17c | 307 | if(inet_pton(AF_INET, str.c_str(), &address.sin4.sin_addr) <= 0) { |
37d3f960 | 308 | address.sin4.sin_family=AF_INET6; |
f71bc087 | 309 | if(makeIPv6sockaddr(str, &address.sin6) < 0) |
4957a608 | 310 | throw NetmaskException("Unable to convert '"+str+"' to a netmask"); |
37d3f960 BH |
311 | } |
312 | return address; | |
313 | } | |
314 | ||
5cc8371b | 315 | inline ComboAddress makeComboAddressFromRaw(uint8_t version, const char* raw, size_t len) |
f4352636 PD |
316 | { |
317 | ComboAddress address; | |
f4352636 | 318 | |
45fab880 | 319 | if (version == 4) { |
5cc8371b RG |
320 | address.sin4.sin_family = AF_INET; |
321 | if (len != sizeof(address.sin4.sin_addr)) throw NetmaskException("invalid raw address length"); | |
322 | memcpy(&address.sin4.sin_addr, raw, sizeof(address.sin4.sin_addr)); | |
45fab880 PD |
323 | } |
324 | else if (version == 6) { | |
5cc8371b RG |
325 | address.sin6.sin6_family = AF_INET6; |
326 | if (len != sizeof(address.sin6.sin6_addr)) throw NetmaskException("invalid raw address length"); | |
327 | memcpy(&address.sin6.sin6_addr, raw, sizeof(address.sin6.sin6_addr)); | |
45fab880 | 328 | } |
f4352636 | 329 | else throw NetmaskException("invalid address family"); |
f4352636 PD |
330 | |
331 | return address; | |
332 | } | |
333 | ||
5cc8371b RG |
334 | inline ComboAddress makeComboAddressFromRaw(uint8_t version, const string &str) |
335 | { | |
336 | return makeComboAddressFromRaw(version, str.c_str(), str.size()); | |
337 | } | |
338 | ||
12c86877 BH |
339 | /** This class represents a netmask and can be queried to see if a certain |
340 | IP address is matched by this mask */ | |
12c86877 BH |
341 | class Netmask |
342 | { | |
343 | public: | |
6f97329b BH |
344 | Netmask() |
345 | { | |
346 | d_network.sin4.sin_family=0; // disable this doing anything useful | |
f563fff4 | 347 | d_network.sin4.sin_port = 0; // this guarantees d_network compares identical |
2fd2d93c AT |
348 | d_mask=0; |
349 | d_bits=0; | |
6f97329b BH |
350 | } |
351 | ||
a4c8835f | 352 | Netmask(const ComboAddress& network, uint8_t bits=0xff) |
6f97329b BH |
353 | { |
354 | d_network = network; | |
0bdabe94 | 355 | d_network.sin4.sin_port=0; |
e1c8a4bb | 356 | if(bits > 128) |
a4c8835f BH |
357 | bits = (network.sin4.sin_family == AF_INET) ? 32 : 128; |
358 | ||
6f97329b BH |
359 | d_bits = bits; |
360 | if(d_bits<32) | |
361 | d_mask=~(0xFFFFFFFF>>d_bits); | |
362 | else | |
363 | d_mask=0xFFFFFFFF; // not actually used for IPv6 | |
364 | } | |
365 | ||
12c86877 BH |
366 | //! Constructor supplies the mask, which cannot be changed |
367 | Netmask(const string &mask) | |
368 | { | |
37d3f960 BH |
369 | pair<string,string> split=splitField(mask,'/'); |
370 | d_network=makeComboAddress(split.first); | |
371 | ||
372 | if(!split.second.empty()) { | |
a683e8bd | 373 | d_bits = (uint8_t)pdns_stou(split.second); |
37d3f960 | 374 | if(d_bits<32) |
4957a608 | 375 | d_mask=~(0xFFFFFFFF>>d_bits); |
8519b8a2 | 376 | else |
4957a608 | 377 | d_mask=0xFFFFFFFF; |
37d3f960 BH |
378 | } |
379 | else if(d_network.sin4.sin_family==AF_INET) { | |
380 | d_bits = 32; | |
381 | d_mask = 0xFFFFFFFF; | |
382 | } | |
5c1def57 | 383 | else { |
37d3f960 | 384 | d_bits=128; |
5c1def57 BH |
385 | d_mask=0; // silence silly warning - d_mask is unused for IPv6 |
386 | } | |
12c86877 BH |
387 | } |
388 | ||
2914b022 BH |
389 | bool match(const ComboAddress& ip) const |
390 | { | |
391 | return match(&ip); | |
392 | } | |
393 | ||
12c86877 | 394 | //! If this IP address in socket address matches |
37d3f960 | 395 | bool match(const ComboAddress *ip) const |
12c86877 | 396 | { |
37d3f960 BH |
397 | if(d_network.sin4.sin_family != ip->sin4.sin_family) { |
398 | return false; | |
399 | } | |
400 | if(d_network.sin4.sin_family == AF_INET) { | |
401 | return match4(htonl((unsigned int)ip->sin4.sin_addr.s_addr)); | |
402 | } | |
403 | if(d_network.sin6.sin6_family == AF_INET6) { | |
404 | uint8_t bytes=d_bits/8, n; | |
405 | const uint8_t *us=(const uint8_t*) &d_network.sin6.sin6_addr.s6_addr; | |
406 | const uint8_t *them=(const uint8_t*) &ip->sin6.sin6_addr.s6_addr; | |
407 | ||
408 | for(n=0; n < bytes; ++n) { | |
4957a608 BH |
409 | if(us[n]!=them[n]) { |
410 | return false; | |
411 | } | |
37d3f960 BH |
412 | } |
413 | // still here, now match remaining bits | |
f0739fb6 | 414 | uint8_t bits= d_bits % 8; |
a683e8bd | 415 | uint8_t mask= (uint8_t) ~(0xFF>>bits); |
f0739fb6 | 416 | |
37d3f960 BH |
417 | return((us[n] & mask) == (them[n] & mask)); |
418 | } | |
419 | return false; | |
12c86877 BH |
420 | } |
421 | ||
422 | //! If this ASCII IP address matches | |
423 | bool match(const string &ip) const | |
424 | { | |
37d3f960 BH |
425 | ComboAddress address=makeComboAddress(ip); |
426 | return match(&address); | |
12c86877 BH |
427 | } |
428 | ||
429 | //! If this IP address in native format matches | |
37d3f960 | 430 | bool match4(uint32_t ip) const |
12c86877 | 431 | { |
37d3f960 | 432 | return (ip & d_mask) == (ntohl(d_network.sin4.sin_addr.s_addr) & d_mask); |
12c86877 BH |
433 | } |
434 | ||
2c95fc65 BH |
435 | string toString() const |
436 | { | |
335da0ba | 437 | return d_network.toString()+"/"+std::to_string((unsigned int)d_bits); |
2c95fc65 BH |
438 | } |
439 | ||
a4c8835f BH |
440 | string toStringNoMask() const |
441 | { | |
442 | return d_network.toString(); | |
443 | } | |
9f84a557 | 444 | const ComboAddress& getNetwork() const |
a4c8835f BH |
445 | { |
446 | return d_network; | |
447 | } | |
e1c8a4bb RG |
448 | const ComboAddress getMaskedNetwork() const |
449 | { | |
450 | ComboAddress result(d_network); | |
451 | if(isIpv4()) { | |
452 | result.sin4.sin_addr.s_addr = htonl(ntohl(result.sin4.sin_addr.s_addr) & d_mask); | |
453 | } | |
454 | else if(isIpv6()) { | |
455 | size_t idx; | |
456 | uint8_t bytes=d_bits/8; | |
457 | uint8_t *us=(uint8_t*) &result.sin6.sin6_addr.s6_addr; | |
458 | uint8_t bits= d_bits % 8; | |
459 | uint8_t mask= (uint8_t) ~(0xFF>>bits); | |
460 | ||
461 | if (bytes < sizeof(result.sin6.sin6_addr.s6_addr)) { | |
462 | us[bytes] &= mask; | |
463 | } | |
464 | ||
465 | for(idx = bytes + 1; idx < sizeof(result.sin6.sin6_addr.s6_addr); ++idx) { | |
466 | us[idx] = 0; | |
467 | } | |
468 | } | |
469 | return result; | |
470 | } | |
8a3a3822 | 471 | uint8_t getBits() const |
a4c8835f BH |
472 | { |
473 | return d_bits; | |
474 | } | |
709ca59f AT |
475 | bool isIpv6() const |
476 | { | |
477 | return d_network.sin6.sin6_family == AF_INET6; | |
478 | } | |
479 | bool isIpv4() const | |
480 | { | |
481 | return d_network.sin4.sin_family == AF_INET; | |
482 | } | |
644dd1da | 483 | |
484 | bool operator<(const Netmask& rhs) const | |
485 | { | |
a009559d RG |
486 | if (empty() && !rhs.empty()) |
487 | return false; | |
488 | ||
489 | if (!empty() && rhs.empty()) | |
490 | return true; | |
491 | ||
492 | if (d_bits > rhs.d_bits) | |
493 | return true; | |
494 | if (d_bits < rhs.d_bits) | |
495 | return false; | |
496 | ||
497 | return d_network < rhs.d_network; | |
498 | } | |
499 | ||
500 | bool operator>(const Netmask& rhs) const | |
501 | { | |
502 | return rhs.operator<(*this); | |
644dd1da | 503 | } |
39ec5d29 | 504 | |
505 | bool operator==(const Netmask& rhs) const | |
506 | { | |
507 | return tie(d_network, d_bits) == tie(rhs.d_network, rhs.d_bits); | |
508 | } | |
509 | ||
87e665b1 | 510 | bool empty() const |
511 | { | |
512 | return d_network.sin4.sin_family==0; | |
513 | } | |
514 | ||
12c86877 | 515 | private: |
37d3f960 | 516 | ComboAddress d_network; |
092f210a | 517 | uint32_t d_mask; |
37d3f960 | 518 | uint8_t d_bits; |
12c86877 BH |
519 | }; |
520 | ||
44845aab AT |
521 | /** Per-bit binary tree map implementation with <Netmask,T> pair. |
522 | * | |
523 | * This is an binary tree implementation for storing attributes for IPv4 and IPv6 prefixes. | |
524 | * The most simple use case is simple NetmaskTree<bool> used by NetmaskGroup, which only | |
525 | * wants to know if given IP address is matched in the prefixes stored. | |
526 | * | |
527 | * This element is useful for anything that needs to *STORE* prefixes, and *MATCH* IP addresses | |
528 | * to a *LIST* of *PREFIXES*. Not the other way round. | |
529 | * | |
530 | * You can store IPv4 and IPv6 addresses to same tree, separate payload storage is kept per AFI. | |
531 | * | |
532 | * To erase something copy values to new tree sans the value you want to erase. | |
533 | * | |
534 | * Use swap if you need to move the tree to another NetmaskTree instance, it is WAY faster | |
ba07e97e | 535 | * than using copy ctor or assignment operator, since it moves the nodes and tree root to |
44845aab AT |
536 | * new home instead of actually recreating the tree. |
537 | * | |
538 | * Please see NetmaskGroup for example of simple use case. Other usecases can be found | |
539 | * from GeoIPBackend and Sortlist, and from dnsdist. | |
540 | */ | |
541 | template <typename T> | |
542 | class NetmaskTree { | |
543 | public: | |
544 | typedef Netmask key_type; | |
545 | typedef T value_type; | |
546 | typedef std::pair<key_type,value_type> node_type; | |
547 | typedef size_t size_type; | |
548 | ||
549 | private: | |
550 | /** Single node in tree, internal use only. | |
551 | */ | |
552 | class TreeNode : boost::noncopyable { | |
553 | public: | |
554 | explicit TreeNode(int bits) noexcept : parent(NULL),d_bits(bits) { | |
555 | } | |
556 | ||
557 | //<! Makes a left node with one more bit than parent | |
558 | TreeNode* make_left() { | |
559 | if (!left) { | |
560 | left = unique_ptr<TreeNode>(new TreeNode(d_bits+1)); | |
561 | left->parent = this; | |
562 | } | |
563 | return left.get(); | |
564 | } | |
565 | ||
566 | //<! Makes a right node with one more bit than parent | |
567 | TreeNode* make_right() { | |
568 | if (!right) { | |
569 | right = unique_ptr<TreeNode>(new TreeNode(d_bits+1)); | |
570 | right->parent = this; | |
571 | } | |
572 | return right.get(); | |
573 | } | |
574 | ||
575 | unique_ptr<TreeNode> left; | |
576 | unique_ptr<TreeNode> right; | |
577 | TreeNode* parent; | |
578 | ||
579 | unique_ptr<node_type> node4; //<! IPv4 value-pair | |
580 | unique_ptr<node_type> node6; //<! IPv6 value-pair | |
581 | ||
582 | int d_bits; //<! How many bits have been used so far | |
583 | }; | |
584 | ||
585 | public: | |
11f4719b | 586 | NetmaskTree() noexcept : NetmaskTree(false) { |
44845aab AT |
587 | } |
588 | ||
11f4719b RG |
589 | NetmaskTree(bool cleanup) noexcept : d_cleanup_tree(cleanup) { |
590 | } | |
591 | ||
592 | NetmaskTree(const NetmaskTree& rhs): d_cleanup_tree(rhs.d_cleanup_tree) { | |
44845aab AT |
593 | // it is easier to copy the nodes than tree. |
594 | // also acts as handy compactor | |
595 | for(auto const& node: rhs._nodes) | |
596 | insert(node->first).second = node->second; | |
597 | } | |
598 | ||
599 | NetmaskTree& operator=(const NetmaskTree& rhs) { | |
600 | clear(); | |
601 | // see above. | |
602 | for(auto const& node: rhs._nodes) | |
603 | insert(node->first).second = node->second; | |
604 | return *this; | |
605 | } | |
606 | ||
44845aab AT |
607 | const typename std::vector<node_type*>::const_iterator begin() const { return _nodes.begin(); } |
608 | const typename std::vector<node_type*>::const_iterator end() const { return _nodes.end(); } | |
609 | ||
610 | typename std::vector<node_type*>::iterator begin() { return _nodes.begin(); } | |
611 | typename std::vector<node_type*>::iterator end() { return _nodes.end(); } | |
612 | ||
613 | node_type& insert(const string &mask) { | |
614 | return insert(key_type(mask)); | |
615 | } | |
616 | ||
617 | //<! Creates new value-pair in tree and returns it. | |
618 | node_type& insert(const key_type& key) { | |
619 | // lazily initialize tree on first insert. | |
620 | if (!root) root = unique_ptr<TreeNode>(new TreeNode(0)); | |
621 | TreeNode* node = root.get(); | |
622 | node_type* value = nullptr; | |
623 | ||
624 | if (key.getNetwork().sin4.sin_family == AF_INET) { | |
625 | std::bitset<32> addr(be32toh(key.getNetwork().sin4.sin_addr.s_addr)); | |
626 | int bits = 0; | |
627 | // we turn left on 0 and right on 1 | |
628 | while(bits < key.getBits()) { | |
629 | uint8_t val = addr[31-bits]; | |
630 | if (val) | |
631 | node = node->make_right(); | |
632 | else | |
633 | node = node->make_left(); | |
634 | bits++; | |
635 | } | |
636 | // only create node if not yet assigned | |
637 | if (!node->node4) { | |
638 | node->node4 = unique_ptr<node_type>(new node_type()); | |
639 | _nodes.push_back(node->node4.get()); | |
640 | } | |
641 | value = node->node4.get(); | |
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(bits < key.getBits()) { | |
648 | uint8_t val; | |
649 | // we use high address until we are | |
650 | if (bits < 64) val = addr_high[63-bits]; | |
651 | // past 64 bits, and start using low address | |
652 | else val = addr_low[127-bits]; | |
653 | ||
654 | // we turn left on 0 and right on 1 | |
655 | if (val) | |
656 | node = node->make_right(); | |
657 | else | |
658 | node = node->make_left(); | |
659 | bits++; | |
660 | } | |
661 | // only create node if not yet assigned | |
662 | if (!node->node6) { | |
663 | node->node6 = unique_ptr<node_type>(new node_type()); | |
664 | _nodes.push_back(node->node6.get()); | |
665 | } | |
666 | value = node->node6.get(); | |
667 | } | |
668 | // assign key | |
669 | value->first = key; | |
670 | return *value; | |
671 | } | |
672 | ||
2dfbbc41 | 673 | //<! Creates or updates value |
44845aab AT |
674 | void insert_or_assign(const key_type& mask, const value_type& value) { |
675 | insert(mask).second = value; | |
676 | } | |
677 | ||
e6419866 AT |
678 | void insert_or_assign(const string& mask, const value_type& value) { |
679 | insert(key_type(mask)).second = value; | |
44845aab AT |
680 | } |
681 | ||
41d0adb7 AT |
682 | //<! check if given key is present in TreeMap |
683 | bool has_key(const key_type& key) const { | |
684 | const node_type *ptr = lookup(key); | |
685 | return ptr && ptr->first == key; | |
686 | } | |
687 | ||
2dfbbc41 | 688 | //<! Returns "best match" for key_type, which might not be value |
44845aab AT |
689 | const node_type* lookup(const key_type& value) const { |
690 | return lookup(value.getNetwork(), value.getBits()); | |
691 | } | |
692 | ||
2dfbbc41 | 693 | //<! Perform best match lookup for value, using at most max_bits |
44845aab AT |
694 | const node_type* lookup(const ComboAddress& value, int max_bits = 128) const { |
695 | if (!root) return nullptr; | |
696 | ||
697 | TreeNode *node = root.get(); | |
698 | node_type *ret = nullptr; | |
699 | ||
700 | // exact same thing as above, except | |
701 | if (value.sin4.sin_family == AF_INET) { | |
702 | max_bits = std::max(0,std::min(max_bits,32)); | |
703 | std::bitset<32> addr(be32toh(value.sin4.sin_addr.s_addr)); | |
704 | int bits = 0; | |
705 | ||
706 | while(bits < max_bits) { | |
707 | // ...we keep track of last non-empty node | |
708 | if (node->node4) ret = node->node4.get(); | |
709 | uint8_t val = addr[31-bits]; | |
710 | // ...and we don't create left/right hand | |
711 | if (val) { | |
712 | if (node->right) node = node->right.get(); | |
713 | // ..and we break when road ends | |
714 | else break; | |
715 | } else { | |
716 | if (node->left) node = node->left.get(); | |
717 | else break; | |
718 | } | |
719 | bits++; | |
720 | } | |
721 | // needed if we did not find one in loop | |
722 | if (node->node4) ret = node->node4.get(); | |
723 | } else { | |
724 | uint64_t* addr = (uint64_t*)value.sin6.sin6_addr.s6_addr; | |
725 | max_bits = std::max(0,std::min(max_bits,128)); | |
726 | std::bitset<64> addr_low(be64toh(addr[1])); | |
727 | std::bitset<64> addr_high(be64toh(addr[0])); | |
728 | int bits = 0; | |
729 | while(bits < max_bits) { | |
730 | if (node->node6) ret = node->node6.get(); | |
731 | uint8_t val; | |
732 | if (bits < 64) val = addr_high[63-bits]; | |
733 | else val = addr_low[127-bits]; | |
734 | if (val) { | |
735 | if (node->right) node = node->right.get(); | |
736 | else break; | |
737 | } else { | |
738 | if (node->left) node = node->left.get(); | |
739 | else break; | |
740 | } | |
741 | bits++; | |
742 | } | |
743 | if (node->node6) ret = node->node6.get(); | |
744 | } | |
745 | ||
746 | // this can be nullptr. | |
747 | return ret; | |
748 | } | |
749 | ||
11f4719b RG |
750 | void cleanup_tree(TreeNode* node) |
751 | { | |
752 | // only cleanup this node if it has no children and node4 and node6 are both empty | |
753 | if (!(node->left || node->right || node->node6 || node->node4)) { | |
754 | // get parent node ptr | |
755 | TreeNode* parent = node->parent; | |
756 | // delete this node | |
757 | if (parent) { | |
758 | if (parent->left.get() == node) | |
759 | parent->left.reset(); | |
760 | else | |
761 | parent->right.reset(); | |
762 | // now recurse up to the parent | |
763 | cleanup_tree(parent); | |
764 | } | |
765 | } | |
766 | } | |
767 | ||
2dfbbc41 | 768 | //<! Removes key from TreeMap. This does not clean up the tree. |
44845aab AT |
769 | void erase(const key_type& key) { |
770 | TreeNode *node = root.get(); | |
771 | ||
772 | // no tree, no value | |
773 | if ( node == nullptr ) return; | |
774 | ||
775 | // exact same thing as above, except | |
776 | if (key.getNetwork().sin4.sin_family == AF_INET) { | |
777 | std::bitset<32> addr(be32toh(key.getNetwork().sin4.sin_addr.s_addr)); | |
778 | int bits = 0; | |
779 | while(node && bits < key.getBits()) { | |
780 | uint8_t val = addr[31-bits]; | |
781 | if (val) { | |
782 | node = node->right.get(); | |
783 | } else { | |
784 | node = node->left.get(); | |
785 | } | |
786 | bits++; | |
787 | } | |
788 | if (node) { | |
d7c676a5 RG |
789 | for(auto it = _nodes.begin(); it != _nodes.end(); ) { |
790 | if (node->node4.get() == *it) | |
791 | it = _nodes.erase(it); | |
792 | else | |
793 | it++; | |
794 | } | |
11f4719b | 795 | |
44845aab | 796 | node->node4.reset(); |
11f4719b RG |
797 | |
798 | if (d_cleanup_tree) | |
799 | cleanup_tree(node); | |
44845aab AT |
800 | } |
801 | } else { | |
802 | uint64_t* addr = (uint64_t*)key.getNetwork().sin6.sin6_addr.s6_addr; | |
803 | std::bitset<64> addr_low(be64toh(addr[1])); | |
804 | std::bitset<64> addr_high(be64toh(addr[0])); | |
805 | int bits = 0; | |
806 | while(node && bits < key.getBits()) { | |
807 | uint8_t val; | |
808 | if (bits < 64) val = addr_high[63-bits]; | |
809 | else val = addr_low[127-bits]; | |
810 | if (val) { | |
811 | node = node->right.get(); | |
812 | } else { | |
813 | node = node->left.get(); | |
814 | } | |
815 | bits++; | |
816 | } | |
817 | if (node) { | |
d7c676a5 RG |
818 | for(auto it = _nodes.begin(); it != _nodes.end(); ) { |
819 | if (node->node6.get() == *it) | |
820 | it = _nodes.erase(it); | |
821 | else | |
822 | it++; | |
823 | } | |
824 | ||
44845aab | 825 | node->node6.reset(); |
11f4719b RG |
826 | |
827 | if (d_cleanup_tree) | |
828 | cleanup_tree(node); | |
44845aab AT |
829 | } |
830 | } | |
831 | } | |
832 | ||
833 | void erase(const string& key) { | |
834 | erase(key_type(key)); | |
835 | } | |
836 | ||
837 | //<! checks whether the container is empty. | |
838 | bool empty() const { | |
839 | return _nodes.empty(); | |
840 | } | |
841 | ||
842 | //<! returns the number of elements | |
843 | size_type size() const { | |
844 | return _nodes.size(); | |
845 | } | |
846 | ||
847 | //<! See if given ComboAddress matches any prefix | |
848 | bool match(const ComboAddress& value) const { | |
849 | return (lookup(value) != nullptr); | |
850 | } | |
851 | ||
852 | bool match(const std::string& value) const { | |
853 | return match(ComboAddress(value)); | |
854 | } | |
855 | ||
856 | //<! Clean out the tree | |
857 | void clear() { | |
858 | _nodes.clear(); | |
859 | root.reset(nullptr); | |
860 | } | |
861 | ||
862 | //<! swaps the contents, rhs is left with nullptr. | |
863 | void swap(NetmaskTree& rhs) { | |
864 | root.swap(rhs.root); | |
865 | _nodes.swap(rhs._nodes); | |
866 | } | |
867 | ||
868 | private: | |
869 | unique_ptr<TreeNode> root; //<! Root of our tree | |
870 | std::vector<node_type*> _nodes; //<! Container for actual values | |
11f4719b | 871 | bool d_cleanup_tree; //<! Whether or not to cleanup the tree on erase |
44845aab AT |
872 | }; |
873 | ||
12c86877 BH |
874 | /** This class represents a group of supplemental Netmask classes. An IP address matchs |
875 | if it is matched by zero or more of the Netmask classes within. | |
876 | */ | |
877 | class NetmaskGroup | |
878 | { | |
879 | public: | |
11f4719b RG |
880 | //! By default, initialise the tree to cleanup |
881 | NetmaskGroup() noexcept : NetmaskGroup(true) { | |
882 | } | |
883 | ||
884 | //! This allows control over whether to cleanup or not | |
885 | NetmaskGroup(bool cleanup) noexcept : tree(cleanup) { | |
886 | } | |
887 | ||
12c86877 | 888 | //! If this IP address is matched by any of the classes within |
60af67b8 | 889 | |
1e77c17c | 890 | bool match(const ComboAddress *ip) const |
12c86877 | 891 | { |
ee15a1e1 PD |
892 | const auto &ret = tree.lookup(*ip); |
893 | if(ret) return ret->second; | |
894 | return false; | |
12c86877 | 895 | } |
60af67b8 | 896 | |
1e77c17c | 897 | bool match(const ComboAddress& ip) const |
60af67b8 | 898 | { |
899 | return match(&ip); | |
900 | } | |
901 | ||
11f4719b RG |
902 | bool lookup(const ComboAddress* ip, Netmask* nmp) const |
903 | { | |
904 | const auto &ret = tree.lookup(*ip); | |
905 | if (ret) { | |
906 | if (nmp != nullptr) | |
907 | *nmp = ret->first; | |
908 | ||
909 | return ret->second; | |
910 | } | |
911 | return false; | |
912 | } | |
913 | ||
914 | bool lookup(const ComboAddress& ip, Netmask* nmp) const | |
915 | { | |
916 | return lookup(&ip, nmp); | |
917 | } | |
918 | ||
376effcf | 919 | //! Add this string to the list of possible matches |
ee15a1e1 | 920 | void addMask(const string &ip, bool positive=true) |
12c86877 | 921 | { |
ee15a1e1 PD |
922 | if(!ip.empty() && ip[0] == '!') { |
923 | addMask(Netmask(ip.substr(1)), false); | |
924 | } else { | |
925 | addMask(Netmask(ip), positive); | |
926 | } | |
12c86877 | 927 | } |
68b011bd | 928 | |
376effcf | 929 | //! Add this Netmask to the list of possible matches |
ee15a1e1 | 930 | void addMask(const Netmask& nm, bool positive=true) |
376effcf | 931 | { |
ee15a1e1 | 932 | tree.insert(nm).second=positive; |
376effcf | 933 | } |
934 | ||
11f4719b RG |
935 | //! Delete this Netmask from the list of possible matches |
936 | void deleteMask(const Netmask& nm) | |
937 | { | |
938 | tree.erase(nm); | |
939 | } | |
940 | ||
941 | void deleteMask(const std::string& ip) | |
942 | { | |
943 | if (!ip.empty()) | |
944 | deleteMask(Netmask(ip)); | |
945 | } | |
946 | ||
68b011bd KM |
947 | void clear() |
948 | { | |
5ac553e1 | 949 | tree.clear(); |
68b011bd KM |
950 | } |
951 | ||
5ac553e1 | 952 | bool empty() const |
12c86877 | 953 | { |
5ac553e1 | 954 | return tree.empty(); |
12c86877 BH |
955 | } |
956 | ||
5ac553e1 | 957 | size_t size() const |
2c95fc65 | 958 | { |
5ac553e1 | 959 | return tree.size(); |
2c95fc65 BH |
960 | } |
961 | ||
962 | string toString() const | |
963 | { | |
964 | ostringstream str; | |
5ac553e1 AT |
965 | for(auto iter = tree.begin(); iter != tree.end(); ++iter) { |
966 | if(iter != tree.begin()) | |
4957a608 | 967 | str <<", "; |
ee15a1e1 PD |
968 | if(!((*iter)->second)) |
969 | str<<"!"; | |
5ac553e1 | 970 | str<<(*iter)->first.toString(); |
2c95fc65 BH |
971 | } |
972 | return str.str(); | |
973 | } | |
974 | ||
41942bb3 CH |
975 | void toStringVector(vector<string>* vec) const |
976 | { | |
ee15a1e1 PD |
977 | for(auto iter = tree.begin(); iter != tree.end(); ++iter) { |
978 | vec->push_back(((*iter)->second ? "" : "!") + (*iter)->first.toString()); | |
979 | } | |
41942bb3 CH |
980 | } |
981 | ||
68b011bd KM |
982 | void toMasks(const string &ips) |
983 | { | |
984 | vector<string> parts; | |
985 | stringtok(parts, ips, ", \t"); | |
986 | ||
987 | for (vector<string>::const_iterator iter = parts.begin(); iter != parts.end(); ++iter) | |
988 | addMask(*iter); | |
989 | } | |
990 | ||
12c86877 | 991 | private: |
5ac553e1 | 992 | NetmaskTree<bool> tree; |
12c86877 BH |
993 | }; |
994 | ||
002c970a | 995 | |
60c8afa8 | 996 | struct SComboAddress |
997 | { | |
998 | SComboAddress(const ComboAddress& orig) : ca(orig) {} | |
999 | ComboAddress ca; | |
1000 | bool operator<(const SComboAddress& rhs) const | |
1001 | { | |
1002 | return ComboAddress::addressOnlyLessThan()(ca, rhs.ca); | |
1003 | } | |
1004 | operator const ComboAddress&() | |
1005 | { | |
1006 | return ca; | |
1007 | } | |
1008 | }; | |
1009 | ||
1010 | ||
002c970a | 1011 | int SSocket(int family, int type, int flags); |
1012 | int SConnect(int sockfd, const ComboAddress& remote); | |
51959320 RG |
1013 | /* tries to connect to remote for a maximum of timeout seconds. |
1014 | sockfd should be set to non-blocking beforehand. | |
1015 | returns 0 on success (the socket is writable), throw a | |
1016 | runtime_error otherwise */ | |
1017 | int SConnectWithTimeout(int sockfd, const ComboAddress& remote, int timeout); | |
002c970a | 1018 | int SBind(int sockfd, const ComboAddress& local); |
1019 | int SAccept(int sockfd, ComboAddress& remote); | |
1020 | int SListen(int sockfd, int limit); | |
1021 | int SSetsockopt(int sockfd, int level, int opname, int value); | |
1022 | ||
3e3f0358 | 1023 | #if defined(IP_PKTINFO) |
1024 | #define GEN_IP_PKTINFO IP_PKTINFO | |
1025 | #elif defined(IP_RECVDSTADDR) | |
1026 | #define GEN_IP_PKTINFO IP_RECVDSTADDR | |
1027 | #endif | |
4d39d7f3 | 1028 | |
3e3f0358 | 1029 | bool IsAnyAddress(const ComboAddress& addr); |
2b3eefc3 | 1030 | bool HarvestDestinationAddress(const struct msghdr* msgh, ComboAddress* destination); |
3e3f0358 | 1031 | bool HarvestTimestamp(struct msghdr* msgh, struct timeval* tv); |
b71b60ee | 1032 | void fillMSGHdr(struct msghdr* msgh, struct iovec* iov, char* cbuf, size_t cbufsize, char* data, size_t datalen, ComboAddress* addr); |
a683e8bd | 1033 | ssize_t sendfromto(int sock, const char* data, size_t len, int flags, const ComboAddress& from, const ComboAddress& to); |
fbe2a2e0 | 1034 | ssize_t sendMsgWithTimeout(int fd, const char* buffer, size_t len, int timeout, ComboAddress& dest, const ComboAddress& local, unsigned int localItf); |
17bca36a | 1035 | bool sendSizeAndMsgWithTimeout(int sock, uint16_t bufferLen, const char* buffer, int idleTimeout, const ComboAddress* dest, const ComboAddress* local, unsigned int localItf, int totalTimeout, int flags); |
840ed663 RG |
1036 | /* requires a non-blocking, connected TCP socket */ |
1037 | bool isTCPSocketUsable(int sock); | |
f9f9592e AT |
1038 | |
1039 | extern template class NetmaskTree<bool>; | |
17bca36a RG |
1040 | |
1041 | #endif |