]>
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 | */ | |
e8c59f2d | 22 | #pragma once |
12c86877 | 23 | #include <string> |
092f210a BH |
24 | #include <sys/socket.h> |
25 | #include <netinet/in.h> | |
26 | #include <arpa/inet.h> | |
12c86877 BH |
27 | #include <iostream> |
28 | #include <stdio.h> | |
29 | #include <functional> | |
44845aab | 30 | #include <bitset> |
5c409fa2 | 31 | #include "pdnsexception.hh" |
809fe23f | 32 | #include "misc.hh" |
506a9050 BH |
33 | #include <sys/socket.h> |
34 | #include <netdb.h> | |
335da0ba | 35 | #include <sstream> |
fd4ed0ab BH |
36 | #include <boost/tuple/tuple.hpp> |
37 | #include <boost/tuple/tuple_comparison.hpp> | |
38 | ||
10f4eea8 | 39 | #include "namespaces.hh" |
12c86877 | 40 | |
323c477a PD |
41 | #ifdef __APPLE__ |
42 | #include <libkern/OSByteOrder.h> | |
43 | ||
44 | #define htobe16(x) OSSwapHostToBigInt16(x) | |
45 | #define htole16(x) OSSwapHostToLittleInt16(x) | |
46 | #define be16toh(x) OSSwapBigToHostInt16(x) | |
47 | #define le16toh(x) OSSwapLittleToHostInt16(x) | |
48 | ||
49 | #define htobe32(x) OSSwapHostToBigInt32(x) | |
50 | #define htole32(x) OSSwapHostToLittleInt32(x) | |
51 | #define be32toh(x) OSSwapBigToHostInt32(x) | |
52 | #define le32toh(x) OSSwapLittleToHostInt32(x) | |
53 | ||
54 | #define htobe64(x) OSSwapHostToBigInt64(x) | |
55 | #define htole64(x) OSSwapHostToLittleInt64(x) | |
56 | #define be64toh(x) OSSwapBigToHostInt64(x) | |
57 | #define le64toh(x) OSSwapLittleToHostInt64(x) | |
58 | #endif | |
59 | ||
28fe507d | 60 | #ifdef __sun |
b0228347 AT |
61 | |
62 | #define htobe16(x) BE_16(x) | |
63 | #define htole16(x) LE_16(x) | |
28fe507d RD |
64 | #define be16toh(x) BE_IN16(&(x)) |
65 | #define le16toh(x) LE_IN16(&(x)) | |
b0228347 AT |
66 | |
67 | #define htobe32(x) BE_32(x) | |
68 | #define htole32(x) LE_32(x) | |
28fe507d RD |
69 | #define be32toh(x) BE_IN32(&(x)) |
70 | #define le32toh(x) LE_IN32(&(x)) | |
b0228347 AT |
71 | |
72 | #define htobe64(x) BE_64(x) | |
73 | #define htole64(x) LE_64(x) | |
28fe507d RD |
74 | #define be64toh(x) BE_IN64(&(x)) |
75 | #define le64toh(x) LE_IN64(&(x)) | |
b0228347 AT |
76 | |
77 | #endif | |
78 | ||
e95bd1ae RK |
79 | #ifdef __FreeBSD__ |
80 | #include <sys/endian.h> | |
81 | #endif | |
82 | ||
4d39d7f3 TIH |
83 | #if defined(__NetBSD__) && defined(IP_PKTINFO) && !defined(IP_SENDSRCADDR) |
84 | // The IP_PKTINFO option in NetBSD was incompatible with Linux until a | |
85 | // change that also introduced IP_SENDSRCADDR for FreeBSD compatibility. | |
86 | #undef IP_PKTINFO | |
87 | #endif | |
88 | ||
37d3f960 BH |
89 | union ComboAddress { |
90 | struct sockaddr_in sin4; | |
91 | struct sockaddr_in6 sin6; | |
92 | ||
fd4ed0ab BH |
93 | bool operator==(const ComboAddress& rhs) const |
94 | { | |
95 | if(boost::tie(sin4.sin_family, sin4.sin_port) != boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port)) | |
96 | return false; | |
97 | if(sin4.sin_family == AF_INET) | |
98 | return sin4.sin_addr.s_addr == rhs.sin4.sin_addr.s_addr; | |
99 | else | |
a683e8bd | 100 | return memcmp(&sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, sizeof(sin6.sin6_addr.s6_addr))==0; |
fd4ed0ab BH |
101 | } |
102 | ||
bb6f86bd PL |
103 | bool operator!=(const ComboAddress& rhs) const |
104 | { | |
105 | return(!operator==(rhs)); | |
106 | } | |
107 | ||
37d3f960 BH |
108 | bool operator<(const ComboAddress& rhs) const |
109 | { | |
f563fff4 | 110 | if(sin4.sin_family == 0) { |
111 | return false; | |
389fa92e | 112 | } |
fd4ed0ab | 113 | if(boost::tie(sin4.sin_family, sin4.sin_port) < boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port)) |
37d3f960 | 114 | return true; |
fd4ed0ab | 115 | if(boost::tie(sin4.sin_family, sin4.sin_port) > boost::tie(rhs.sin4.sin_family, rhs.sin4.sin_port)) |
37d3f960 | 116 | return false; |
389fa92e | 117 | |
37d3f960 BH |
118 | if(sin4.sin_family == AF_INET) |
119 | return sin4.sin_addr.s_addr < rhs.sin4.sin_addr.s_addr; | |
120 | else | |
a683e8bd | 121 | return memcmp(&sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, sizeof(sin6.sin6_addr.s6_addr)) < 0; |
37d3f960 BH |
122 | } |
123 | ||
fd4ed0ab BH |
124 | bool operator>(const ComboAddress& rhs) const |
125 | { | |
5f15ee47 | 126 | return rhs.operator<(*this); |
fd4ed0ab BH |
127 | } |
128 | ||
545725f2 | 129 | struct addressOnlyHash |
130 | { | |
389fa92e SB |
131 | uint32_t operator()(const ComboAddress& ca) const |
132 | { | |
545725f2 | 133 | const unsigned char* start; |
134 | int len; | |
135 | if(ca.sin4.sin_family == AF_INET) { | |
136 | start =(const unsigned char*)&ca.sin4.sin_addr.s_addr; | |
137 | len=4; | |
138 | } | |
139 | else { | |
140 | start =(const unsigned char*)&ca.sin6.sin6_addr.s6_addr; | |
141 | len=16; | |
142 | } | |
143 | return burtle(start, len, 0); | |
144 | } | |
145 | }; | |
146 | ||
662d5441 | 147 | struct addressOnlyLessThan: public std::binary_function<ComboAddress, ComboAddress, bool> |
11a7242f BH |
148 | { |
149 | bool operator()(const ComboAddress& a, const ComboAddress& b) const | |
150 | { | |
151 | if(a.sin4.sin_family < b.sin4.sin_family) | |
4957a608 | 152 | return true; |
11a7242f | 153 | if(a.sin4.sin_family > b.sin4.sin_family) |
4957a608 | 154 | return false; |
11a7242f | 155 | if(a.sin4.sin_family == AF_INET) |
4957a608 | 156 | return a.sin4.sin_addr.s_addr < b.sin4.sin_addr.s_addr; |
11a7242f | 157 | else |
a683e8bd | 158 | return memcmp(&a.sin6.sin6_addr.s6_addr, &b.sin6.sin6_addr.s6_addr, sizeof(a.sin6.sin6_addr.s6_addr)) < 0; |
11a7242f BH |
159 | } |
160 | }; | |
fd4ed0ab | 161 | |
0940e4eb | 162 | struct addressOnlyEqual: public std::binary_function<ComboAddress, ComboAddress, bool> |
163 | { | |
164 | bool operator()(const ComboAddress& a, const ComboAddress& b) const | |
165 | { | |
166 | if(a.sin4.sin_family != b.sin4.sin_family) | |
167 | return false; | |
168 | if(a.sin4.sin_family == AF_INET) | |
169 | return a.sin4.sin_addr.s_addr == b.sin4.sin_addr.s_addr; | |
170 | else | |
a683e8bd | 171 | return !memcmp(&a.sin6.sin6_addr.s6_addr, &b.sin6.sin6_addr.s6_addr, sizeof(a.sin6.sin6_addr.s6_addr)); |
0940e4eb | 172 | } |
173 | }; | |
174 | ||
175 | ||
fd4ed0ab | 176 | socklen_t getSocklen() const |
a9af3782 BH |
177 | { |
178 | if(sin4.sin_family == AF_INET) | |
179 | return sizeof(sin4); | |
180 | else | |
181 | return sizeof(sin6); | |
182 | } | |
389fa92e SB |
183 | |
184 | ComboAddress() | |
fd4ed0ab BH |
185 | { |
186 | sin4.sin_family=AF_INET; | |
187 | sin4.sin_addr.s_addr=0; | |
188 | sin4.sin_port=0; | |
5cc8371b RG |
189 | sin6.sin6_scope_id = 0; |
190 | sin6.sin6_flowinfo = 0; | |
fd4ed0ab BH |
191 | } |
192 | ||
a7360cd9 AT |
193 | ComboAddress(const struct sockaddr *sa, socklen_t salen) { |
194 | setSockaddr(sa, salen); | |
195 | }; | |
196 | ||
197 | ComboAddress(const struct sockaddr_in6 *sa) { | |
198 | setSockaddr((const struct sockaddr*)sa, sizeof(struct sockaddr_in6)); | |
199 | }; | |
200 | ||
201 | ComboAddress(const struct sockaddr_in *sa) { | |
202 | setSockaddr((const struct sockaddr*)sa, sizeof(struct sockaddr_in)); | |
203 | }; | |
204 | ||
205 | void setSockaddr(const struct sockaddr *sa, socklen_t salen) { | |
206 | if (salen > sizeof(struct sockaddr_in6)) throw PDNSException("ComboAddress can't handle other than sockaddr_in or sockaddr_in6"); | |
207 | memcpy(this, sa, salen); | |
208 | } | |
209 | ||
85db02c5 | 210 | // 'port' sets a default value in case 'str' does not set a port |
fd4ed0ab BH |
211 | explicit ComboAddress(const string& str, uint16_t port=0) |
212 | { | |
213 | memset(&sin6, 0, sizeof(sin6)); | |
214 | sin4.sin_family = AF_INET; | |
85db02c5 BH |
215 | sin4.sin_port = 0; |
216 | if(makeIPv4sockaddr(str, &sin4)) { | |
fd4ed0ab | 217 | sin6.sin6_family = AF_INET6; |
f71bc087 | 218 | if(makeIPv6sockaddr(str, &sin6) < 0) |
389fa92e SB |
219 | throw PDNSException("Unable to convert presentation address '"+ str +"'"); |
220 | ||
fd4ed0ab | 221 | } |
85db02c5 BH |
222 | if(!sin4.sin_port) // 'str' overrides port! |
223 | sin4.sin_port=htons(port); | |
fd4ed0ab | 224 | } |
a9af3782 | 225 | |
a94673ea RG |
226 | bool isIPv6() const |
227 | { | |
228 | return sin4.sin_family == AF_INET6; | |
229 | } | |
230 | bool isIPv4() const | |
231 | { | |
232 | return sin4.sin_family == AF_INET; | |
233 | } | |
234 | ||
eb5bae86 | 235 | bool isMappedIPv4() const |
2914b022 BH |
236 | { |
237 | if(sin4.sin_family!=AF_INET6) | |
238 | return false; | |
389fa92e | 239 | |
2914b022 BH |
240 | int n=0; |
241 | const unsigned char*ptr = (unsigned char*) &sin6.sin6_addr.s6_addr; | |
242 | for(n=0; n < 10; ++n) | |
243 | if(ptr[n]) | |
4957a608 | 244 | return false; |
389fa92e | 245 | |
2914b022 BH |
246 | for(; n < 12; ++n) |
247 | if(ptr[n]!=0xff) | |
4957a608 | 248 | return false; |
389fa92e | 249 | |
2914b022 BH |
250 | return true; |
251 | } | |
389fa92e | 252 | |
eb5bae86 | 253 | ComboAddress mapToIPv4() const |
2914b022 BH |
254 | { |
255 | if(!isMappedIPv4()) | |
3f81d239 | 256 | throw PDNSException("ComboAddress can't map non-mapped IPv6 address back to IPv4"); |
2914b022 BH |
257 | ComboAddress ret; |
258 | ret.sin4.sin_family=AF_INET; | |
11a7242f | 259 | ret.sin4.sin_port=sin4.sin_port; |
389fa92e | 260 | |
2914b022 | 261 | const unsigned char*ptr = (unsigned char*) &sin6.sin6_addr.s6_addr; |
a683e8bd RG |
262 | ptr+=(sizeof(sin6.sin6_addr.s6_addr) - sizeof(ret.sin4.sin_addr.s_addr)); |
263 | memcpy(&ret.sin4.sin_addr.s_addr, ptr, sizeof(ret.sin4.sin_addr.s_addr)); | |
2914b022 BH |
264 | return ret; |
265 | } | |
266 | ||
37d3f960 BH |
267 | string toString() const |
268 | { | |
506a9050 | 269 | char host[1024]; |
5cc8371b | 270 | int retval = 0; |
f4352636 | 271 | if(sin4.sin_family && !(retval = getnameinfo((struct sockaddr*) this, getSocklen(), host, sizeof(host),0, 0, NI_NUMERICHOST))) |
bfbf6814 | 272 | return string(host); |
c44d3917 | 273 | else |
f4352636 | 274 | return "invalid "+string(gai_strerror(retval)); |
37d3f960 | 275 | } |
b8c3ea84 BH |
276 | |
277 | string toStringWithPort() const | |
278 | { | |
279 | if(sin4.sin_family==AF_INET) | |
335da0ba | 280 | return toString() + ":" + std::to_string(ntohs(sin4.sin_port)); |
b8c3ea84 | 281 | else |
335da0ba | 282 | return "["+toString() + "]:" + std::to_string(ntohs(sin4.sin_port)); |
b8c3ea84 | 283 | } |
22779196 | 284 | |
d622042f | 285 | string toStringWithPortExcept(int port) const |
286 | { | |
287 | if(ntohs(sin4.sin_port) == port) | |
288 | return toString(); | |
289 | if(sin4.sin_family==AF_INET) | |
290 | return toString() + ":" + std::to_string(ntohs(sin4.sin_port)); | |
291 | else | |
292 | return "["+toString() + "]:" + std::to_string(ntohs(sin4.sin_port)); | |
293 | } | |
294 | ||
9b0f144f KM |
295 | string toLogString() const |
296 | { | |
297 | return toStringWithPortExcept(53); | |
298 | } | |
299 | ||
5b6099b2 | 300 | void truncate(unsigned int bits) noexcept; |
0affb140 RG |
301 | |
302 | uint16_t getPort() const | |
303 | { | |
304 | return ntohs(sin4.sin_port); | |
305 | } | |
306 | ||
79816288 | 307 | void setPort(uint16_t port) |
f43e6a40 | 308 | { |
79816288 | 309 | sin4.sin_port = htons(port); |
f43e6a40 KM |
310 | } |
311 | ||
d38e2ba9 RG |
312 | void reset() |
313 | { | |
314 | memset(&sin4, 0, sizeof(sin4)); | |
315 | memset(&sin6, 0, sizeof(sin6)); | |
316 | } | |
317 | ||
20c33d95 SB |
318 | //! Get the total number of address bits (either 32 or 128 depending on IP version) |
319 | uint8_t getBits() const | |
320 | { | |
321 | if (isIPv4()) | |
322 | return 32; | |
323 | if (isIPv6()) | |
324 | return 128; | |
325 | return 0; | |
326 | } | |
cdd23120 SB |
327 | /** Get the value of the bit at the provided bit index. When the index >= 0, |
328 | the index is relative to the LSB starting at index zero. When the index < 0, | |
329 | the index is relative to the MSB starting at index -1 and counting down. | |
330 | */ | |
331 | bool getBit(int index) const | |
332 | { | |
333 | if(isIPv4()) { | |
334 | if (index >= 32) | |
335 | return false; | |
336 | if (index < 0) { | |
337 | if (index < -32) | |
338 | return false; | |
339 | index = 32 + index; | |
340 | } | |
341 | ||
342 | uint32_t s_addr = ntohl(sin4.sin_addr.s_addr); | |
343 | ||
344 | return ((s_addr & (1<<index)) != 0x00000000); | |
345 | } | |
346 | if(isIPv6()) { | |
347 | if (index >= 128) | |
348 | return false; | |
349 | if (index < 0) { | |
350 | if (index < -128) | |
351 | return false; | |
352 | index = 128 + index; | |
353 | } | |
354 | ||
355 | uint8_t *s_addr = (uint8_t*)sin6.sin6_addr.s6_addr; | |
356 | uint8_t byte_idx = index / 8; | |
357 | uint8_t bit_idx = index % 8; | |
358 | ||
359 | return ((s_addr[15-byte_idx] & (1 << bit_idx)) != 0x00); | |
360 | } | |
361 | return false; | |
362 | } | |
37d3f960 BH |
363 | }; |
364 | ||
12c86877 | 365 | /** This exception is thrown by the Netmask class and by extension by the NetmaskGroup class */ |
389fa92e | 366 | class NetmaskException: public PDNSException |
12c86877 BH |
367 | { |
368 | public: | |
3f81d239 | 369 | NetmaskException(const string &a) : PDNSException(a) {} |
12c86877 BH |
370 | }; |
371 | ||
37d3f960 BH |
372 | inline ComboAddress makeComboAddress(const string& str) |
373 | { | |
374 | ComboAddress address; | |
375 | address.sin4.sin_family=AF_INET; | |
1e77c17c | 376 | if(inet_pton(AF_INET, str.c_str(), &address.sin4.sin_addr) <= 0) { |
37d3f960 | 377 | address.sin4.sin_family=AF_INET6; |
f71bc087 | 378 | if(makeIPv6sockaddr(str, &address.sin6) < 0) |
389fa92e | 379 | throw NetmaskException("Unable to convert '"+str+"' to a netmask"); |
37d3f960 BH |
380 | } |
381 | return address; | |
382 | } | |
383 | ||
5cc8371b | 384 | inline ComboAddress makeComboAddressFromRaw(uint8_t version, const char* raw, size_t len) |
f4352636 PD |
385 | { |
386 | ComboAddress address; | |
f4352636 | 387 | |
45fab880 | 388 | if (version == 4) { |
5cc8371b RG |
389 | address.sin4.sin_family = AF_INET; |
390 | if (len != sizeof(address.sin4.sin_addr)) throw NetmaskException("invalid raw address length"); | |
391 | memcpy(&address.sin4.sin_addr, raw, sizeof(address.sin4.sin_addr)); | |
45fab880 PD |
392 | } |
393 | else if (version == 6) { | |
5cc8371b RG |
394 | address.sin6.sin6_family = AF_INET6; |
395 | if (len != sizeof(address.sin6.sin6_addr)) throw NetmaskException("invalid raw address length"); | |
396 | memcpy(&address.sin6.sin6_addr, raw, sizeof(address.sin6.sin6_addr)); | |
45fab880 | 397 | } |
f4352636 | 398 | else throw NetmaskException("invalid address family"); |
f4352636 PD |
399 | |
400 | return address; | |
401 | } | |
402 | ||
5cc8371b RG |
403 | inline ComboAddress makeComboAddressFromRaw(uint8_t version, const string &str) |
404 | { | |
405 | return makeComboAddressFromRaw(version, str.c_str(), str.size()); | |
406 | } | |
407 | ||
12c86877 BH |
408 | /** This class represents a netmask and can be queried to see if a certain |
409 | IP address is matched by this mask */ | |
12c86877 BH |
410 | class Netmask |
411 | { | |
412 | public: | |
6f97329b BH |
413 | Netmask() |
414 | { | |
7c408ab4 | 415 | d_network.sin4.sin_family = 0; // disable this doing anything useful |
389fa92e | 416 | d_network.sin4.sin_port = 0; // this guarantees d_network compares identical |
7c408ab4 RG |
417 | d_mask = 0; |
418 | d_bits = 0; | |
6f97329b | 419 | } |
389fa92e | 420 | |
5708a729 | 421 | Netmask(const ComboAddress& network, uint8_t bits=0xff): d_network(network) |
6f97329b | 422 | { |
7c408ab4 RG |
423 | d_network.sin4.sin_port = 0; |
424 | setBits(network.isIPv4() ? std::min(bits, static_cast<uint8_t>(32)) : std::min(bits, static_cast<uint8_t>(128))); | |
425 | } | |
389fa92e | 426 | |
7c408ab4 RG |
427 | void setBits(uint8_t value) |
428 | { | |
429 | d_bits = value; | |
430 | ||
431 | if (d_bits < 32) { | |
432 | d_mask = ~(0xFFFFFFFF >> d_bits); | |
433 | } | |
434 | else { | |
435 | // note that d_mask is unused for IPv6 | |
436 | d_mask = 0xFFFFFFFF; | |
437 | } | |
438 | ||
439 | if (isIPv4()) { | |
440 | d_network.sin4.sin_addr.s_addr = htonl(ntohl(d_network.sin4.sin_addr.s_addr) & d_mask); | |
441 | } | |
442 | else if (isIPv6()) { | |
443 | uint8_t bytes = d_bits/8; | |
444 | uint8_t *us = (uint8_t*) &d_network.sin6.sin6_addr.s6_addr; | |
445 | uint8_t bits = d_bits % 8; | |
446 | uint8_t mask = (uint8_t) ~(0xFF>>bits); | |
447 | ||
448 | if (bytes < sizeof(d_network.sin6.sin6_addr.s6_addr)) { | |
449 | us[bytes] &= mask; | |
450 | } | |
451 | ||
452 | for(size_t idx = bytes + 1; idx < sizeof(d_network.sin6.sin6_addr.s6_addr); ++idx) { | |
453 | us[idx] = 0; | |
454 | } | |
455 | } | |
6f97329b | 456 | } |
389fa92e SB |
457 | |
458 | //! Constructor supplies the mask, which cannot be changed | |
459 | Netmask(const string &mask) | |
12c86877 | 460 | { |
7c408ab4 RG |
461 | pair<string,string> split = splitField(mask,'/'); |
462 | d_network = makeComboAddress(split.first); | |
389fa92e | 463 | |
7c408ab4 RG |
464 | if (!split.second.empty()) { |
465 | setBits(static_cast<uint8_t>(pdns_stou(split.second))); | |
37d3f960 | 466 | } |
7c408ab4 RG |
467 | else if (d_network.sin4.sin_family == AF_INET) { |
468 | setBits(32); | |
37d3f960 | 469 | } |
5c1def57 | 470 | else { |
7c408ab4 | 471 | setBits(128); |
5c1def57 | 472 | } |
12c86877 BH |
473 | } |
474 | ||
2914b022 BH |
475 | bool match(const ComboAddress& ip) const |
476 | { | |
477 | return match(&ip); | |
478 | } | |
479 | ||
12c86877 | 480 | //! If this IP address in socket address matches |
37d3f960 | 481 | bool match(const ComboAddress *ip) const |
12c86877 | 482 | { |
37d3f960 BH |
483 | if(d_network.sin4.sin_family != ip->sin4.sin_family) { |
484 | return false; | |
485 | } | |
486 | if(d_network.sin4.sin_family == AF_INET) { | |
487 | return match4(htonl((unsigned int)ip->sin4.sin_addr.s_addr)); | |
488 | } | |
489 | if(d_network.sin6.sin6_family == AF_INET6) { | |
490 | uint8_t bytes=d_bits/8, n; | |
491 | const uint8_t *us=(const uint8_t*) &d_network.sin6.sin6_addr.s6_addr; | |
492 | const uint8_t *them=(const uint8_t*) &ip->sin6.sin6_addr.s6_addr; | |
389fa92e | 493 | |
37d3f960 | 494 | for(n=0; n < bytes; ++n) { |
4957a608 BH |
495 | if(us[n]!=them[n]) { |
496 | return false; | |
497 | } | |
37d3f960 BH |
498 | } |
499 | // still here, now match remaining bits | |
f0739fb6 | 500 | uint8_t bits= d_bits % 8; |
a683e8bd | 501 | uint8_t mask= (uint8_t) ~(0xFF>>bits); |
f0739fb6 | 502 | |
7c408ab4 | 503 | return((us[n]) == (them[n] & mask)); |
37d3f960 BH |
504 | } |
505 | return false; | |
12c86877 BH |
506 | } |
507 | ||
508 | //! If this ASCII IP address matches | |
509 | bool match(const string &ip) const | |
510 | { | |
37d3f960 BH |
511 | ComboAddress address=makeComboAddress(ip); |
512 | return match(&address); | |
12c86877 BH |
513 | } |
514 | ||
515 | //! If this IP address in native format matches | |
37d3f960 | 516 | bool match4(uint32_t ip) const |
12c86877 | 517 | { |
7c408ab4 | 518 | return (ip & d_mask) == (ntohl(d_network.sin4.sin_addr.s_addr)); |
12c86877 BH |
519 | } |
520 | ||
2c95fc65 BH |
521 | string toString() const |
522 | { | |
335da0ba | 523 | return d_network.toString()+"/"+std::to_string((unsigned int)d_bits); |
2c95fc65 BH |
524 | } |
525 | ||
a4c8835f BH |
526 | string toStringNoMask() const |
527 | { | |
528 | return d_network.toString(); | |
529 | } | |
7c408ab4 | 530 | |
9f84a557 | 531 | const ComboAddress& getNetwork() const |
a4c8835f BH |
532 | { |
533 | return d_network; | |
534 | } | |
e1c8a4bb | 535 | |
7c408ab4 RG |
536 | const ComboAddress& getMaskedNetwork() const |
537 | { | |
538 | return getNetwork(); | |
e1c8a4bb | 539 | } |
7c408ab4 | 540 | |
8a3a3822 | 541 | uint8_t getBits() const |
a4c8835f BH |
542 | { |
543 | return d_bits; | |
544 | } | |
7c408ab4 | 545 | |
37e35fbc | 546 | bool isIPv6() const |
709ca59f AT |
547 | { |
548 | return d_network.sin6.sin6_family == AF_INET6; | |
549 | } | |
7c408ab4 | 550 | |
d14121a8 | 551 | bool isIPv4() const |
709ca59f AT |
552 | { |
553 | return d_network.sin4.sin_family == AF_INET; | |
554 | } | |
644dd1da | 555 | |
389fa92e | 556 | bool operator<(const Netmask& rhs) const |
644dd1da | 557 | { |
a009559d RG |
558 | if (empty() && !rhs.empty()) |
559 | return false; | |
560 | ||
561 | if (!empty() && rhs.empty()) | |
562 | return true; | |
563 | ||
564 | if (d_bits > rhs.d_bits) | |
565 | return true; | |
566 | if (d_bits < rhs.d_bits) | |
567 | return false; | |
568 | ||
569 | return d_network < rhs.d_network; | |
570 | } | |
571 | ||
572 | bool operator>(const Netmask& rhs) const | |
573 | { | |
574 | return rhs.operator<(*this); | |
644dd1da | 575 | } |
39ec5d29 | 576 | |
389fa92e | 577 | bool operator==(const Netmask& rhs) const |
39ec5d29 | 578 | { |
579 | return tie(d_network, d_bits) == tie(rhs.d_network, rhs.d_bits); | |
580 | } | |
581 | ||
389fa92e | 582 | bool empty() const |
87e665b1 | 583 | { |
584 | return d_network.sin4.sin_family==0; | |
585 | } | |
586 | ||
e9a5bdb1 SB |
587 | //! Get normalized version of the netmask. This means that all address bits below the network bits are zero. |
588 | Netmask getNormalized() const { | |
589 | return Netmask(getMaskedNetwork(), d_bits); | |
590 | } | |
664140b5 SB |
591 | //! Get Netmask for super network of this one (i.e. with fewer network bits) |
592 | Netmask getSuper(uint8_t bits) const { | |
593 | return Netmask(d_network, std::min(d_bits, bits)); | |
594 | } | |
5d7557e3 SB |
595 | |
596 | //! Get the total number of address bits for this netmask (either 32 or 128 depending on IP version) | |
597 | uint8_t getAddressBits() const | |
598 | { | |
599 | return d_network.getBits(); | |
600 | } | |
8d8c1d77 SB |
601 | |
602 | /** Get the value of the bit at the provided bit index. When the index >= 0, | |
603 | the index is relative to the LSB starting at index zero. When the index < 0, | |
604 | the index is relative to the MSB starting at index -1 and counting down. | |
605 | When the index points outside the network bits, it always yields zero. | |
606 | */ | |
607 | bool getBit(int bit) const | |
608 | { | |
609 | if (bit < -d_bits) | |
610 | return false; | |
611 | if (bit >= 0) { | |
612 | if(isIPv4()) { | |
613 | if (bit >= 32 || bit < (32 - d_bits)) | |
614 | return false; | |
615 | } | |
616 | if(isIPv6()) { | |
617 | if (bit >= 128 || bit < (128 - d_bits)) | |
618 | return false; | |
619 | } | |
620 | } | |
621 | return d_network.getBit(bit); | |
622 | } | |
12c86877 | 623 | private: |
37d3f960 | 624 | ComboAddress d_network; |
092f210a | 625 | uint32_t d_mask; |
37d3f960 | 626 | uint8_t d_bits; |
12c86877 BH |
627 | }; |
628 | ||
4bb19027 | 629 | /** Binary tree map implementation with <Netmask,T> pair. |
44845aab AT |
630 | * |
631 | * This is an binary tree implementation for storing attributes for IPv4 and IPv6 prefixes. | |
632 | * The most simple use case is simple NetmaskTree<bool> used by NetmaskGroup, which only | |
633 | * wants to know if given IP address is matched in the prefixes stored. | |
634 | * | |
635 | * This element is useful for anything that needs to *STORE* prefixes, and *MATCH* IP addresses | |
636 | * to a *LIST* of *PREFIXES*. Not the other way round. | |
637 | * | |
638 | * You can store IPv4 and IPv6 addresses to same tree, separate payload storage is kept per AFI. | |
80462253 SB |
639 | * Network prefixes (Netmasks) are always recorded in normalized fashion, meaning that only |
640 | * the network bits are set. This is what is returned in the insert() and lookup() return | |
641 | * values. | |
44845aab | 642 | * |
44845aab | 643 | * Use swap if you need to move the tree to another NetmaskTree instance, it is WAY faster |
ba07e97e | 644 | * than using copy ctor or assignment operator, since it moves the nodes and tree root to |
44845aab AT |
645 | * new home instead of actually recreating the tree. |
646 | * | |
647 | * Please see NetmaskGroup for example of simple use case. Other usecases can be found | |
648 | * from GeoIPBackend and Sortlist, and from dnsdist. | |
649 | */ | |
650 | template <typename T> | |
651 | class NetmaskTree { | |
652 | public: | |
de1cde57 SB |
653 | class Iterator; |
654 | ||
44845aab AT |
655 | typedef Netmask key_type; |
656 | typedef T value_type; | |
0c4df7c3 | 657 | typedef std::pair<const key_type,value_type> node_type; |
44845aab | 658 | typedef size_t size_type; |
de1cde57 | 659 | typedef class Iterator iterator; |
44845aab AT |
660 | |
661 | private: | |
662 | /** Single node in tree, internal use only. | |
663 | */ | |
664 | class TreeNode : boost::noncopyable { | |
665 | public: | |
4bb19027 | 666 | explicit TreeNode() noexcept : |
cba13f93 | 667 | parent(nullptr), node(), assigned(false), d_bits(0) { |
4bb19027 SB |
668 | } |
669 | explicit TreeNode(const key_type& key) noexcept : | |
cba13f93 | 670 | parent(nullptr), node({key.getNormalized(), value_type()}), |
4bb19027 | 671 | assigned(false), d_bits(key.getAddressBits()) { |
389fa92e SB |
672 | } |
673 | ||
4bb19027 SB |
674 | //<! Makes a left leaf node with specified key. |
675 | TreeNode* make_left(const key_type& key) { | |
cba13f93 | 676 | d_bits = node.first.getBits(); |
4bb19027 SB |
677 | left = make_unique<TreeNode>(key); |
678 | left->parent = this; | |
389fa92e SB |
679 | return left.get(); |
680 | } | |
681 | ||
4bb19027 SB |
682 | //<! Makes a right leaf node with specified key. |
683 | TreeNode* make_right(const key_type& key) { | |
cba13f93 | 684 | d_bits = node.first.getBits(); |
4bb19027 SB |
685 | right = make_unique<TreeNode>(key); |
686 | right->parent = this; | |
389fa92e SB |
687 | return right.get(); |
688 | } | |
689 | ||
4bb19027 SB |
690 | //<! Splits branch at indicated bit position by inserting key |
691 | TreeNode* split(const key_type& key, int bits) { | |
692 | if (parent == nullptr) { | |
693 | // not to be called on the root node | |
694 | throw std::logic_error( | |
695 | "NetmaskTree::TreeNode::split(): must not be called on root node"); | |
696 | } | |
697 | ||
698 | // determine reference from parent | |
699 | unique_ptr<TreeNode>& parent_ref = | |
700 | (parent->left.get() == this ? parent->left : parent->right); | |
701 | if (parent_ref.get() != this) { | |
702 | throw std::logic_error( | |
703 | "NetmaskTree::TreeNode::split(): parent node reference is invalid"); | |
704 | } | |
705 | ||
706 | // create new tree node for the new key | |
707 | TreeNode* new_node = new TreeNode(key); | |
708 | new_node->d_bits = bits; | |
709 | ||
710 | // attach the new node under our former parent | |
711 | unique_ptr<TreeNode> new_child(new_node); | |
712 | std::swap(parent_ref, new_child); // hereafter new_child points to "this" | |
713 | new_node->parent = parent; | |
714 | ||
715 | // attach "this" node below the new node | |
716 | // (left or right depending on bit) | |
717 | new_child->parent = new_node; | |
cba13f93 | 718 | if (new_child->node.first.getBit(-1-bits)) { |
4bb19027 SB |
719 | std::swap(new_node->right, new_child); |
720 | } else { | |
721 | std::swap(new_node->left, new_child); | |
722 | } | |
723 | ||
724 | return new_node; | |
725 | } | |
726 | ||
727 | //<! Forks branch for new key at indicated bit position | |
728 | TreeNode* fork(const key_type& key, int bits) { | |
729 | if (parent == nullptr) { | |
730 | // not to be called on the root node | |
731 | throw std::logic_error( | |
732 | "NetmaskTree::TreeNode::fork(): must not be called on root node"); | |
733 | } | |
734 | ||
735 | // determine reference from parent | |
736 | unique_ptr<TreeNode>& parent_ref = | |
737 | (parent->left.get() == this ? parent->left : parent->right); | |
738 | if (parent_ref.get() != this) { | |
739 | throw std::logic_error( | |
740 | "NetmaskTree::TreeNode::fork(): parent node reference is invalid"); | |
741 | } | |
742 | ||
743 | // create new tree node for the branch point | |
cba13f93 | 744 | TreeNode* branch_node = new TreeNode(node.first.getSuper(bits)); |
4bb19027 SB |
745 | branch_node->d_bits = bits; |
746 | ||
747 | // attach the branch node under our former parent | |
748 | unique_ptr<TreeNode> new_child1(branch_node); | |
749 | std::swap(parent_ref, new_child1); // hereafter new_child1 points to "this" | |
750 | branch_node->parent = parent; | |
751 | ||
752 | // create second new leaf node for the new key | |
753 | TreeNode* new_node = new TreeNode(key); | |
754 | unique_ptr<TreeNode> new_child2(new_node); | |
755 | ||
756 | // attach the new child nodes below the branch node | |
757 | // (left or right depending on bit) | |
758 | new_child1->parent = branch_node; | |
759 | new_child2->parent = branch_node; | |
cba13f93 | 760 | if (new_child1->node.first.getBit(-1-bits)) { |
4bb19027 SB |
761 | std::swap(branch_node->right, new_child1); |
762 | std::swap(branch_node->left, new_child2); | |
763 | } else { | |
764 | std::swap(branch_node->right, new_child2); | |
765 | std::swap(branch_node->left, new_child1); | |
766 | } | |
767 | ||
768 | return new_node; | |
769 | } | |
770 | ||
fddcd1cc SB |
771 | //<! Traverse left branch depth-first |
772 | TreeNode *traverse_l() | |
773 | { | |
774 | TreeNode *tnode = this; | |
775 | ||
776 | while (tnode->left) | |
777 | tnode = tnode->left.get(); | |
778 | return tnode; | |
779 | } | |
780 | ||
781 | //<! Traverse tree depth-first and in-order (L-N-R) | |
782 | TreeNode *traverse_lnr() | |
783 | { | |
784 | TreeNode *tnode = this; | |
785 | ||
786 | // precondition: descended left as deep as possible | |
787 | if (tnode->right) { | |
788 | // descend right | |
789 | tnode = tnode->right.get(); | |
790 | // descend left as deep as possible and return next node | |
791 | return tnode->traverse_l(); | |
792 | } | |
793 | ||
794 | // ascend to parent | |
795 | while (tnode->parent != nullptr) { | |
796 | TreeNode *prev_child = tnode; | |
797 | tnode = tnode->parent; | |
798 | ||
799 | // return this node, but only when we come from the left child branch | |
800 | if (tnode->left && tnode->left.get() == prev_child) | |
801 | return tnode; | |
802 | } | |
803 | return nullptr; | |
804 | } | |
805 | ||
806 | //<! Traverse only assigned nodes | |
807 | TreeNode *traverse_lnr_assigned() | |
808 | { | |
809 | TreeNode *tnode = traverse_lnr(); | |
810 | ||
811 | while (tnode != nullptr && !tnode->assigned) | |
812 | tnode = tnode->traverse_lnr(); | |
813 | return tnode; | |
814 | } | |
815 | ||
389fa92e SB |
816 | unique_ptr<TreeNode> left; |
817 | unique_ptr<TreeNode> right; | |
818 | TreeNode* parent; | |
819 | ||
cba13f93 | 820 | node_type node; |
956c6dc4 | 821 | bool assigned; //<! Whether this node is assigned-to by the application |
389fa92e SB |
822 | |
823 | int d_bits; //<! How many bits have been used so far | |
44845aab AT |
824 | }; |
825 | ||
9b0ae5c8 SB |
826 | void cleanup_tree(TreeNode* node) |
827 | { | |
956c6dc4 SB |
828 | // only cleanup this node if it has no children and node not assigned |
829 | if (!(node->left || node->right || node->assigned)) { | |
9b0ae5c8 SB |
830 | // get parent node ptr |
831 | TreeNode* pparent = node->parent; | |
832 | // delete this node | |
833 | if (pparent) { | |
834 | if (pparent->left.get() == node) | |
835 | pparent->left.reset(); | |
836 | else | |
837 | pparent->right.reset(); | |
838 | // now recurse up to the parent | |
839 | cleanup_tree(pparent); | |
840 | } | |
841 | } | |
842 | } | |
843 | ||
1355a23f SB |
844 | void copyTree(const NetmaskTree& rhs) |
845 | { | |
846 | TreeNode *node; | |
847 | ||
848 | node = rhs.d_root.get(); | |
849 | if (node != nullptr) | |
850 | node = node->traverse_l(); | |
851 | while (node != nullptr) { | |
852 | if (node->assigned) | |
cba13f93 | 853 | insert(node->node.first).second = node->node.second; |
1355a23f SB |
854 | node = node->traverse_lnr(); |
855 | } | |
856 | } | |
857 | ||
de1cde57 SB |
858 | public: |
859 | class Iterator { | |
860 | public: | |
7c888097 SB |
861 | typedef node_type value_type; |
862 | typedef node_type& reference; | |
863 | typedef node_type* pointer; | |
de1cde57 SB |
864 | typedef std::forward_iterator_tag iterator_category; |
865 | typedef size_type difference_type; | |
866 | ||
867 | private: | |
868 | friend class NetmaskTree; | |
869 | ||
870 | const NetmaskTree* d_tree; | |
871 | TreeNode* d_node; | |
872 | ||
873 | Iterator(const NetmaskTree* tree, TreeNode* node): d_tree(tree), d_node(node) { | |
874 | } | |
875 | ||
876 | public: | |
877 | Iterator(): d_tree(nullptr), d_node(nullptr) {} | |
878 | ||
879 | Iterator& operator++() // prefix | |
880 | { | |
881 | if (d_node == nullptr) { | |
882 | throw std::logic_error( | |
883 | "NetmaskTree::Iterator::operator++: iterator is invalid"); | |
884 | } | |
885 | d_node = d_node->traverse_lnr_assigned(); | |
886 | return *this; | |
887 | } | |
888 | Iterator operator++(int) // postfix | |
889 | { | |
890 | Iterator tmp(*this); | |
891 | operator++(); | |
892 | return tmp; | |
893 | } | |
894 | ||
895 | reference operator*() | |
896 | { | |
897 | if (d_node == nullptr) { | |
898 | throw std::logic_error( | |
899 | "NetmaskTree::Iterator::operator*: iterator is invalid"); | |
900 | } | |
7c888097 SB |
901 | return d_node->node; |
902 | } | |
903 | ||
904 | pointer operator->() | |
905 | { | |
906 | if (d_node == nullptr) { | |
907 | throw std::logic_error( | |
908 | "NetmaskTree::Iterator::operator->: iterator is invalid"); | |
909 | } | |
cba13f93 | 910 | return &d_node->node; |
de1cde57 SB |
911 | } |
912 | ||
913 | bool operator==(const Iterator& rhs) | |
914 | { | |
915 | return (d_tree == rhs.d_tree && d_node == rhs.d_node); | |
916 | } | |
917 | bool operator!=(const Iterator& rhs) | |
918 | { | |
919 | return !(*this == rhs); | |
920 | } | |
921 | }; | |
922 | ||
44845aab | 923 | public: |
dccd4976 | 924 | NetmaskTree() noexcept: d_root(new TreeNode()), d_left(nullptr), d_size(0) { |
44845aab AT |
925 | } |
926 | ||
dccd4976 | 927 | NetmaskTree(const NetmaskTree& rhs): d_root(new TreeNode()), d_left(nullptr), d_size(0) { |
1355a23f | 928 | copyTree(rhs); |
44845aab AT |
929 | } |
930 | ||
931 | NetmaskTree& operator=(const NetmaskTree& rhs) { | |
932 | clear(); | |
1355a23f | 933 | copyTree(rhs); |
44845aab AT |
934 | return *this; |
935 | } | |
936 | ||
de1cde57 SB |
937 | const iterator begin() const { |
938 | return Iterator(this, d_left); | |
939 | } | |
940 | const iterator end() const { | |
941 | return Iterator(this, nullptr); | |
942 | } | |
943 | iterator begin() { | |
944 | return Iterator(this, d_left); | |
945 | } | |
946 | iterator end() { | |
947 | return Iterator(this, nullptr); | |
948 | } | |
44845aab AT |
949 | |
950 | node_type& insert(const string &mask) { | |
951 | return insert(key_type(mask)); | |
952 | } | |
953 | ||
954 | //<! Creates new value-pair in tree and returns it. | |
955 | node_type& insert(const key_type& key) { | |
956c6dc4 | 956 | TreeNode* node; |
9edc8e2b | 957 | bool is_left = true; |
136b2c6b SB |
958 | |
959 | // we turn left on IPv4 and right on IPv6 | |
960 | if (key.isIPv4()) { | |
136b2c6b | 961 | node = d_root->left.get(); |
4bb19027 SB |
962 | if (node == nullptr) { |
963 | node = new TreeNode(key); | |
964 | node->assigned = true; | |
965 | node->parent = d_root.get(); | |
966 | ||
967 | d_root->left = unique_ptr<TreeNode>(node); | |
dccd4976 | 968 | d_size++; |
9edc8e2b | 969 | d_left = node; |
cba13f93 | 970 | return node->node; |
4bb19027 | 971 | } |
136b2c6b | 972 | } else if (key.isIPv6()) { |
136b2c6b | 973 | node = d_root->right.get(); |
4bb19027 SB |
974 | if (node == nullptr) { |
975 | node = new TreeNode(key); | |
976 | node->assigned = true; | |
977 | node->parent = d_root.get(); | |
978 | ||
979 | d_root->right = unique_ptr<TreeNode>(node); | |
dccd4976 | 980 | d_size++; |
9edc8e2b SB |
981 | if (!d_root->left) |
982 | d_left = node; | |
cba13f93 | 983 | return node->node; |
4bb19027 | 984 | } |
9edc8e2b SB |
985 | if (d_root->left) |
986 | is_left = false; | |
136b2c6b SB |
987 | } else |
988 | throw NetmaskException("invalid address family"); | |
989 | ||
136b2c6b | 990 | // we turn left on 0 and right on 1 |
ebb7e215 | 991 | int bits = 0; |
243134ef | 992 | for(; bits < key.getBits(); bits++) { |
4bb19027 SB |
993 | bool vall = key.getBit(-1-bits); |
994 | ||
995 | if (bits >= node->d_bits) { | |
996 | // the end of the current node is reached; continue with the next | |
997 | if (vall) { | |
9edc8e2b SB |
998 | if (node->left || node->assigned) |
999 | is_left = false; | |
4bb19027 SB |
1000 | if (!node->right) { |
1001 | // the right branch doesn't exist yet; attach our key here | |
1002 | node = node->make_right(key); | |
1003 | break; | |
1004 | } | |
1005 | node = node->right.get(); | |
1006 | } else { | |
1007 | if (!node->left) { | |
1008 | // the left branch doesn't exist yet; attach our key here | |
1009 | node = node->make_left(key); | |
1010 | break; | |
1011 | } | |
1012 | node = node->left.get(); | |
1013 | } | |
1014 | continue; | |
1015 | } | |
cba13f93 | 1016 | if (bits >= node->node.first.getBits()) { |
4bb19027 SB |
1017 | // the matching branch ends here, yet the key netmask has more bits; add a |
1018 | // child node below the existing branch leaf. | |
1019 | if (vall) { | |
9edc8e2b SB |
1020 | if (node->assigned) |
1021 | is_left = false; | |
4bb19027 SB |
1022 | node = node->make_right(key); |
1023 | } else { | |
1024 | node = node->make_left(key); | |
1025 | } | |
1026 | break; | |
1027 | } | |
cba13f93 | 1028 | bool valr = node->node.first.getBit(-1-bits); |
4bb19027 | 1029 | if (vall != valr) { |
9edc8e2b SB |
1030 | if (vall) |
1031 | is_left = false; | |
4bb19027 SB |
1032 | // the branch matches just upto this point, yet continues in a different |
1033 | // direction; fork the branch. | |
1034 | node = node->fork(key, bits); | |
1035 | break; | |
1036 | } | |
1037 | } | |
1038 | ||
cba13f93 | 1039 | if (node->node.first.getBits() > key.getBits()) { |
4bb19027 SB |
1040 | // key is a super-network of the matching node; split the branch and |
1041 | // insert a node for the key above the matching node. | |
1042 | node = node->split(key, key.getBits()); | |
136b2c6b | 1043 | } |
44845aab | 1044 | |
9edc8e2b SB |
1045 | if (node->left) |
1046 | is_left = false; | |
1047 | ||
cba13f93 | 1048 | node_type& value = node->node; |
956c6dc4 | 1049 | |
956c6dc4 | 1050 | if (!node->assigned) { |
dccd4976 SB |
1051 | // only increment size if not assigned before |
1052 | d_size++; | |
9edc8e2b SB |
1053 | // update the pointer to the left-most tree node |
1054 | if (is_left) | |
1055 | d_left = node; | |
956c6dc4 | 1056 | node->assigned = true; |
9edc8e2b SB |
1057 | } else { |
1058 | // tree node exists for this value | |
1059 | if (is_left && d_left != node) { | |
1060 | throw std::logic_error( | |
1061 | "NetmaskTree::insert(): lost track of left-most node in tree"); | |
1062 | } | |
44845aab | 1063 | } |
136b2c6b | 1064 | |
cba13f93 | 1065 | return value; |
44845aab AT |
1066 | } |
1067 | ||
2dfbbc41 | 1068 | //<! Creates or updates value |
44845aab AT |
1069 | void insert_or_assign(const key_type& mask, const value_type& value) { |
1070 | insert(mask).second = value; | |
1071 | } | |
1072 | ||
e6419866 AT |
1073 | void insert_or_assign(const string& mask, const value_type& value) { |
1074 | insert(key_type(mask)).second = value; | |
44845aab AT |
1075 | } |
1076 | ||
41d0adb7 AT |
1077 | //<! check if given key is present in TreeMap |
1078 | bool has_key(const key_type& key) const { | |
1079 | const node_type *ptr = lookup(key); | |
1080 | return ptr && ptr->first == key; | |
1081 | } | |
1082 | ||
2dfbbc41 | 1083 | //<! Returns "best match" for key_type, which might not be value |
44845aab AT |
1084 | const node_type* lookup(const key_type& value) const { |
1085 | return lookup(value.getNetwork(), value.getBits()); | |
1086 | } | |
1087 | ||
2dfbbc41 | 1088 | //<! Perform best match lookup for value, using at most max_bits |
44845aab | 1089 | const node_type* lookup(const ComboAddress& value, int max_bits = 128) const { |
136b2c6b SB |
1090 | TreeNode *node = nullptr; |
1091 | ||
4bb19027 SB |
1092 | uint8_t addr_bits = value.getBits(); |
1093 | if (max_bits < 0 || max_bits > addr_bits) | |
1094 | max_bits = addr_bits; | |
1095 | ||
136b2c6b SB |
1096 | if (value.isIPv4()) |
1097 | node = d_root->left.get(); | |
1098 | else if (value.isIPv6()) | |
1099 | node = d_root->right.get(); | |
7c408ab4 | 1100 | else |
136b2c6b SB |
1101 | throw NetmaskException("invalid address family"); |
1102 | if (node == nullptr) return nullptr; | |
44845aab | 1103 | |
44845aab AT |
1104 | node_type *ret = nullptr; |
1105 | ||
136b2c6b | 1106 | int bits = 0; |
ebb7e215 | 1107 | for(; bits < max_bits; bits++) { |
4bb19027 SB |
1108 | bool vall = value.getBit(-1-bits); |
1109 | if (bits >= node->d_bits) { | |
1110 | // the end of the current node is reached; continue with the next | |
1111 | // (we keep track of last assigned node) | |
cba13f93 SB |
1112 | if (node->assigned && bits == node->node.first.getBits()) |
1113 | ret = &node->node; | |
4bb19027 SB |
1114 | if (vall) { |
1115 | if (!node->right) | |
1116 | break; | |
1117 | node = node->right.get(); | |
1118 | } else { | |
1119 | if (!node->left) | |
1120 | break; | |
1121 | node = node->left.get(); | |
1122 | } | |
1123 | continue; | |
1124 | } | |
cba13f93 | 1125 | if (bits >= node->node.first.getBits()) { |
4bb19027 SB |
1126 | // the matching branch ends here |
1127 | break; | |
1128 | } | |
cba13f93 | 1129 | bool valr = node->node.first.getBit(-1-bits); |
4bb19027 SB |
1130 | if (vall != valr) { |
1131 | // the branch matches just upto this point, yet continues in a different | |
1132 | // direction | |
1133 | break; | |
44845aab | 1134 | } |
44845aab | 1135 | } |
136b2c6b | 1136 | // needed if we did not find one in loop |
cba13f93 SB |
1137 | if (node->assigned && bits == node->node.first.getBits()) |
1138 | ret = &node->node; | |
44845aab AT |
1139 | |
1140 | // this can be nullptr. | |
1141 | return ret; | |
1142 | } | |
1143 | ||
3d22a7ff | 1144 | //<! Removes key from TreeMap. |
44845aab | 1145 | void erase(const key_type& key) { |
136b2c6b SB |
1146 | TreeNode *node = nullptr; |
1147 | ||
1148 | if (key.isIPv4()) | |
1149 | node = d_root->left.get(); | |
1150 | else if (key.isIPv6()) | |
1151 | node = d_root->right.get(); | |
7c408ab4 | 1152 | else |
136b2c6b | 1153 | throw NetmaskException("invalid address family"); |
44845aab | 1154 | // no tree, no value |
136b2c6b SB |
1155 | if (node == nullptr) return; |
1156 | ||
1157 | int bits = 0; | |
ebb7e215 | 1158 | for(; node && bits < key.getBits(); bits++) { |
4bb19027 SB |
1159 | bool vall = key.getBit(-1-bits); |
1160 | if (bits >= node->d_bits) { | |
1161 | // the end of the current node is reached; continue with the next | |
1162 | if (vall) { | |
1163 | node = node->right.get(); | |
1164 | } else { | |
1165 | node = node->left.get(); | |
1166 | } | |
1167 | continue; | |
1168 | } | |
cba13f93 | 1169 | if (bits >= node->node.first.getBits()) { |
4bb19027 | 1170 | // the matching branch ends here |
cba13f93 | 1171 | if (key.getBits() != node->node.first.getBits()) |
4bb19027 SB |
1172 | node = nullptr; |
1173 | break; | |
1174 | } | |
cba13f93 | 1175 | bool valr = node->node.first.getBit(-1-bits); |
4bb19027 SB |
1176 | if (vall != valr) { |
1177 | // the branch matches just upto this point, yet continues in a different | |
1178 | // direction | |
1179 | node = nullptr; | |
1180 | break; | |
44845aab | 1181 | } |
136b2c6b SB |
1182 | } |
1183 | if (node) { | |
dccd4976 SB |
1184 | if (d_size == 0) { |
1185 | throw std::logic_error( | |
1186 | "NetmaskTree::erase(): size of tree is zero before erase"); | |
1187 | } | |
1188 | d_size--; | |
956c6dc4 | 1189 | node->assigned = false; |
cba13f93 | 1190 | node->node.second = value_type(); |
9edc8e2b SB |
1191 | |
1192 | if (node == d_left) | |
1193 | d_left = d_left->traverse_lnr_assigned(); | |
1194 | ||
9772e56d | 1195 | cleanup_tree(node); |
44845aab AT |
1196 | } |
1197 | } | |
1198 | ||
1199 | void erase(const string& key) { | |
1200 | erase(key_type(key)); | |
1201 | } | |
1202 | ||
1203 | //<! checks whether the container is empty. | |
1204 | bool empty() const { | |
dccd4976 | 1205 | return (d_size == 0); |
44845aab AT |
1206 | } |
1207 | ||
1208 | //<! returns the number of elements | |
1209 | size_type size() const { | |
dccd4976 | 1210 | return d_size; |
44845aab AT |
1211 | } |
1212 | ||
1213 | //<! See if given ComboAddress matches any prefix | |
1214 | bool match(const ComboAddress& value) const { | |
1215 | return (lookup(value) != nullptr); | |
1216 | } | |
1217 | ||
1218 | bool match(const std::string& value) const { | |
1219 | return match(ComboAddress(value)); | |
1220 | } | |
1221 | ||
1222 | //<! Clean out the tree | |
1223 | void clear() { | |
4bb19027 | 1224 | d_root.reset(new TreeNode()); |
9edc8e2b | 1225 | d_left = nullptr; |
dccd4976 | 1226 | d_size = 0; |
44845aab AT |
1227 | } |
1228 | ||
3d22a7ff | 1229 | //<! swaps the contents with another NetmaskTree |
44845aab | 1230 | void swap(NetmaskTree& rhs) { |
e4b291fe | 1231 | std::swap(d_root, rhs.d_root); |
9edc8e2b | 1232 | std::swap(d_left, rhs.d_left); |
dccd4976 | 1233 | std::swap(d_size, rhs.d_size); |
44845aab AT |
1234 | } |
1235 | ||
1236 | private: | |
e4b291fe | 1237 | unique_ptr<TreeNode> d_root; //<! Root of our tree |
9edc8e2b | 1238 | TreeNode *d_left; |
dccd4976 | 1239 | size_type d_size; |
44845aab AT |
1240 | }; |
1241 | ||
12c86877 BH |
1242 | /** This class represents a group of supplemental Netmask classes. An IP address matchs |
1243 | if it is matched by zero or more of the Netmask classes within. | |
1244 | */ | |
1245 | class NetmaskGroup | |
1246 | { | |
1247 | public: | |
9772e56d | 1248 | NetmaskGroup() noexcept { |
11f4719b RG |
1249 | } |
1250 | ||
12c86877 | 1251 | //! If this IP address is matched by any of the classes within |
60af67b8 | 1252 | |
1e77c17c | 1253 | bool match(const ComboAddress *ip) const |
12c86877 | 1254 | { |
ee15a1e1 PD |
1255 | const auto &ret = tree.lookup(*ip); |
1256 | if(ret) return ret->second; | |
1257 | return false; | |
12c86877 | 1258 | } |
60af67b8 | 1259 | |
1e77c17c | 1260 | bool match(const ComboAddress& ip) const |
60af67b8 | 1261 | { |
1262 | return match(&ip); | |
1263 | } | |
1264 | ||
11f4719b RG |
1265 | bool lookup(const ComboAddress* ip, Netmask* nmp) const |
1266 | { | |
1267 | const auto &ret = tree.lookup(*ip); | |
1268 | if (ret) { | |
1269 | if (nmp != nullptr) | |
1270 | *nmp = ret->first; | |
1271 | ||
1272 | return ret->second; | |
1273 | } | |
1274 | return false; | |
1275 | } | |
1276 | ||
1277 | bool lookup(const ComboAddress& ip, Netmask* nmp) const | |
1278 | { | |
1279 | return lookup(&ip, nmp); | |
1280 | } | |
1281 | ||
376effcf | 1282 | //! Add this string to the list of possible matches |
ee15a1e1 | 1283 | void addMask(const string &ip, bool positive=true) |
12c86877 | 1284 | { |
ee15a1e1 PD |
1285 | if(!ip.empty() && ip[0] == '!') { |
1286 | addMask(Netmask(ip.substr(1)), false); | |
1287 | } else { | |
1288 | addMask(Netmask(ip), positive); | |
1289 | } | |
12c86877 | 1290 | } |
68b011bd | 1291 | |
376effcf | 1292 | //! Add this Netmask to the list of possible matches |
ee15a1e1 | 1293 | void addMask(const Netmask& nm, bool positive=true) |
376effcf | 1294 | { |
ee15a1e1 | 1295 | tree.insert(nm).second=positive; |
376effcf | 1296 | } |
1297 | ||
11f4719b RG |
1298 | //! Delete this Netmask from the list of possible matches |
1299 | void deleteMask(const Netmask& nm) | |
1300 | { | |
1301 | tree.erase(nm); | |
1302 | } | |
1303 | ||
1304 | void deleteMask(const std::string& ip) | |
1305 | { | |
1306 | if (!ip.empty()) | |
1307 | deleteMask(Netmask(ip)); | |
1308 | } | |
1309 | ||
68b011bd KM |
1310 | void clear() |
1311 | { | |
5ac553e1 | 1312 | tree.clear(); |
68b011bd KM |
1313 | } |
1314 | ||
5ac553e1 | 1315 | bool empty() const |
12c86877 | 1316 | { |
5ac553e1 | 1317 | return tree.empty(); |
12c86877 BH |
1318 | } |
1319 | ||
5ac553e1 | 1320 | size_t size() const |
2c95fc65 | 1321 | { |
5ac553e1 | 1322 | return tree.size(); |
2c95fc65 BH |
1323 | } |
1324 | ||
1325 | string toString() const | |
1326 | { | |
1327 | ostringstream str; | |
5ac553e1 AT |
1328 | for(auto iter = tree.begin(); iter != tree.end(); ++iter) { |
1329 | if(iter != tree.begin()) | |
4957a608 | 1330 | str <<", "; |
7c888097 | 1331 | if(!(iter->second)) |
ee15a1e1 | 1332 | str<<"!"; |
7c888097 | 1333 | str<<iter->first.toString(); |
2c95fc65 BH |
1334 | } |
1335 | return str.str(); | |
1336 | } | |
1337 | ||
41942bb3 CH |
1338 | void toStringVector(vector<string>* vec) const |
1339 | { | |
ee15a1e1 | 1340 | for(auto iter = tree.begin(); iter != tree.end(); ++iter) { |
7c888097 | 1341 | vec->push_back((iter->second ? "" : "!") + iter->first.toString()); |
ee15a1e1 | 1342 | } |
41942bb3 CH |
1343 | } |
1344 | ||
68b011bd KM |
1345 | void toMasks(const string &ips) |
1346 | { | |
1347 | vector<string> parts; | |
1348 | stringtok(parts, ips, ", \t"); | |
1349 | ||
1350 | for (vector<string>::const_iterator iter = parts.begin(); iter != parts.end(); ++iter) | |
1351 | addMask(*iter); | |
1352 | } | |
1353 | ||
12c86877 | 1354 | private: |
5ac553e1 | 1355 | NetmaskTree<bool> tree; |
12c86877 BH |
1356 | }; |
1357 | ||
60c8afa8 | 1358 | struct SComboAddress |
1359 | { | |
1360 | SComboAddress(const ComboAddress& orig) : ca(orig) {} | |
1361 | ComboAddress ca; | |
1362 | bool operator<(const SComboAddress& rhs) const | |
1363 | { | |
1364 | return ComboAddress::addressOnlyLessThan()(ca, rhs.ca); | |
1365 | } | |
1366 | operator const ComboAddress&() | |
1367 | { | |
1368 | return ca; | |
1369 | } | |
1370 | }; | |
1371 | ||
73ba5999 CHB |
1372 | class NetworkError : public runtime_error |
1373 | { | |
1374 | public: | |
1375 | NetworkError(const string& why="Network Error") : runtime_error(why.c_str()) | |
1376 | {} | |
1377 | NetworkError(const char *why="Network Error") : runtime_error(why) | |
1378 | {} | |
1379 | }; | |
60c8afa8 | 1380 | |
002c970a | 1381 | int SSocket(int family, int type, int flags); |
1382 | int SConnect(int sockfd, const ComboAddress& remote); | |
51959320 RG |
1383 | /* tries to connect to remote for a maximum of timeout seconds. |
1384 | sockfd should be set to non-blocking beforehand. | |
1385 | returns 0 on success (the socket is writable), throw a | |
1386 | runtime_error otherwise */ | |
1387 | int SConnectWithTimeout(int sockfd, const ComboAddress& remote, int timeout); | |
002c970a | 1388 | int SBind(int sockfd, const ComboAddress& local); |
1389 | int SAccept(int sockfd, ComboAddress& remote); | |
1390 | int SListen(int sockfd, int limit); | |
1391 | int SSetsockopt(int sockfd, int level, int opname, int value); | |
90f9fbc0 | 1392 | void setSocketIgnorePMTU(int sockfd); |
002c970a | 1393 | |
3e3f0358 | 1394 | #if defined(IP_PKTINFO) |
1395 | #define GEN_IP_PKTINFO IP_PKTINFO | |
1396 | #elif defined(IP_RECVDSTADDR) | |
389fa92e | 1397 | #define GEN_IP_PKTINFO IP_RECVDSTADDR |
3e3f0358 | 1398 | #endif |
4d39d7f3 | 1399 | |
3e3f0358 | 1400 | bool IsAnyAddress(const ComboAddress& addr); |
2b3eefc3 | 1401 | bool HarvestDestinationAddress(const struct msghdr* msgh, ComboAddress* destination); |
3e3f0358 | 1402 | bool HarvestTimestamp(struct msghdr* msgh, struct timeval* tv); |
7bec330a | 1403 | void fillMSGHdr(struct msghdr* msgh, struct iovec* iov, cmsgbuf_aligned* cbuf, size_t cbufsize, char* data, size_t datalen, ComboAddress* addr); |
a683e8bd | 1404 | ssize_t sendfromto(int sock, const char* data, size_t len, int flags, const ComboAddress& from, const ComboAddress& to); |
6714b6ac RG |
1405 | size_t sendMsgWithOptions(int fd, const char* buffer, size_t len, const ComboAddress* dest, const ComboAddress* local, unsigned int localItf, int flags); |
1406 | ||
840ed663 RG |
1407 | /* requires a non-blocking, connected TCP socket */ |
1408 | bool isTCPSocketUsable(int sock); | |
f9f9592e AT |
1409 | |
1410 | extern template class NetmaskTree<bool>; |