]>
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 | 27 | #include <iostream> |
f67ce892 | 28 | #include <cstdio> |
12c86877 | 29 | #include <functional> |
44845aab | 30 | #include <bitset> |
5c409fa2 | 31 | #include "pdnsexception.hh" |
809fe23f | 32 | #include "misc.hh" |
506a9050 | 33 | #include <netdb.h> |
335da0ba | 34 | #include <sstream> |
fd4ed0ab | 35 | |
10f4eea8 | 36 | #include "namespaces.hh" |
12c86877 | 37 | |
323c477a PD |
38 | #ifdef __APPLE__ |
39 | #include <libkern/OSByteOrder.h> | |
40 | ||
41 | #define htobe16(x) OSSwapHostToBigInt16(x) | |
42 | #define htole16(x) OSSwapHostToLittleInt16(x) | |
43 | #define be16toh(x) OSSwapBigToHostInt16(x) | |
44 | #define le16toh(x) OSSwapLittleToHostInt16(x) | |
45 | ||
46 | #define htobe32(x) OSSwapHostToBigInt32(x) | |
47 | #define htole32(x) OSSwapHostToLittleInt32(x) | |
48 | #define be32toh(x) OSSwapBigToHostInt32(x) | |
49 | #define le32toh(x) OSSwapLittleToHostInt32(x) | |
50 | ||
51 | #define htobe64(x) OSSwapHostToBigInt64(x) | |
52 | #define htole64(x) OSSwapHostToLittleInt64(x) | |
53 | #define be64toh(x) OSSwapBigToHostInt64(x) | |
54 | #define le64toh(x) OSSwapLittleToHostInt64(x) | |
55 | #endif | |
56 | ||
28fe507d | 57 | #ifdef __sun |
b0228347 AT |
58 | |
59 | #define htobe16(x) BE_16(x) | |
60 | #define htole16(x) LE_16(x) | |
28fe507d RD |
61 | #define be16toh(x) BE_IN16(&(x)) |
62 | #define le16toh(x) LE_IN16(&(x)) | |
b0228347 AT |
63 | |
64 | #define htobe32(x) BE_32(x) | |
65 | #define htole32(x) LE_32(x) | |
28fe507d RD |
66 | #define be32toh(x) BE_IN32(&(x)) |
67 | #define le32toh(x) LE_IN32(&(x)) | |
b0228347 AT |
68 | |
69 | #define htobe64(x) BE_64(x) | |
70 | #define htole64(x) LE_64(x) | |
28fe507d RD |
71 | #define be64toh(x) BE_IN64(&(x)) |
72 | #define le64toh(x) LE_IN64(&(x)) | |
b0228347 AT |
73 | |
74 | #endif | |
75 | ||
e95bd1ae RK |
76 | #ifdef __FreeBSD__ |
77 | #include <sys/endian.h> | |
78 | #endif | |
79 | ||
4d39d7f3 TIH |
80 | #if defined(__NetBSD__) && defined(IP_PKTINFO) && !defined(IP_SENDSRCADDR) |
81 | // The IP_PKTINFO option in NetBSD was incompatible with Linux until a | |
82 | // change that also introduced IP_SENDSRCADDR for FreeBSD compatibility. | |
83 | #undef IP_PKTINFO | |
84 | #endif | |
85 | ||
07203482 OM |
86 | union ComboAddress |
87 | { | |
5e4bc87a OM |
88 | sockaddr_in sin4{}; |
89 | sockaddr_in6 sin6; | |
37d3f960 | 90 | |
fd4ed0ab BH |
91 | bool operator==(const ComboAddress& rhs) const |
92 | { | |
f67ce892 | 93 | if (std::tie(sin4.sin_family, sin4.sin_port) != std::tie(rhs.sin4.sin_family, rhs.sin4.sin_port)) { |
fd4ed0ab | 94 | return false; |
f67ce892 OM |
95 | } |
96 | if (sin4.sin_family == AF_INET) { | |
fd4ed0ab | 97 | return sin4.sin_addr.s_addr == rhs.sin4.sin_addr.s_addr; |
f67ce892 OM |
98 | } |
99 | return memcmp(&sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, sizeof(sin6.sin6_addr.s6_addr)) == 0; | |
fd4ed0ab BH |
100 | } |
101 | ||
bb6f86bd PL |
102 | bool operator!=(const ComboAddress& rhs) const |
103 | { | |
07203482 | 104 | return (!operator==(rhs)); |
bb6f86bd PL |
105 | } |
106 | ||
37d3f960 BH |
107 | bool operator<(const ComboAddress& rhs) const |
108 | { | |
07203482 | 109 | if (sin4.sin_family == 0) { |
f563fff4 | 110 | return false; |
389fa92e | 111 | } |
f67ce892 | 112 | if (std::tie(sin4.sin_family, sin4.sin_port) < std::tie(rhs.sin4.sin_family, rhs.sin4.sin_port)) { |
37d3f960 | 113 | return true; |
f67ce892 OM |
114 | } |
115 | if (std::tie(sin4.sin_family, sin4.sin_port) > std::tie(rhs.sin4.sin_family, rhs.sin4.sin_port)) { | |
37d3f960 | 116 | return false; |
f67ce892 OM |
117 | } |
118 | if (sin4.sin_family == AF_INET) { | |
37d3f960 | 119 | return sin4.sin_addr.s_addr < rhs.sin4.sin_addr.s_addr; |
f67ce892 OM |
120 | } |
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 | ||
a61dd3f3 Y |
129 | struct addressPortOnlyHash |
130 | { | |
f67ce892 | 131 | uint32_t operator()(const ComboAddress& address) const |
a61dd3f3 | 132 | { |
f67ce892 OM |
133 | // NOLINTBEGIN(cppcoreguidelines-pro-type-reinterpret-cast) |
134 | if (address.sin4.sin_family == AF_INET) { | |
135 | const auto* start = reinterpret_cast<const unsigned char*>(&address.sin4.sin_addr.s_addr); | |
a61dd3f3 | 136 | auto tmp = burtle(start, 4, 0); |
f67ce892 | 137 | return burtle(reinterpret_cast<const uint8_t*>(&address.sin4.sin_port), 2, tmp); |
a61dd3f3 | 138 | } |
f67ce892 OM |
139 | const auto* start = reinterpret_cast<const unsigned char*>(&address.sin6.sin6_addr.s6_addr); |
140 | auto tmp = burtle(start, 16, 0); | |
141 | return burtle(reinterpret_cast<const unsigned char*>(&address.sin6.sin6_port), 2, tmp); | |
142 | // NOLINTEND(cppcoreguidelines-pro-type-reinterpret-cast) | |
a61dd3f3 Y |
143 | } |
144 | }; | |
145 | ||
545725f2 | 146 | struct addressOnlyHash |
147 | { | |
f67ce892 | 148 | uint32_t operator()(const ComboAddress& address) const |
389fa92e | 149 | { |
c173228a RG |
150 | const unsigned char* start = nullptr; |
151 | uint32_t len = 0; | |
f67ce892 OM |
152 | // NOLINTBEGIN(cppcoreguidelines-pro-type-reinterpret-cast) |
153 | if (address.sin4.sin_family == AF_INET) { | |
154 | start = reinterpret_cast<const unsigned char*>(&address.sin4.sin_addr.s_addr); | |
c173228a | 155 | len = 4; |
545725f2 | 156 | } |
157 | else { | |
f67ce892 | 158 | start = reinterpret_cast<const unsigned char*>(&address.sin6.sin6_addr.s6_addr); |
c173228a | 159 | len = 16; |
545725f2 | 160 | } |
f67ce892 | 161 | // NOLINTEND(cppcoreguidelines-pro-type-reinterpret-cast) |
545725f2 | 162 | return burtle(start, len, 0); |
163 | } | |
164 | }; | |
165 | ||
7587bcbe | 166 | struct addressOnlyLessThan |
11a7242f | 167 | { |
f67ce892 | 168 | bool operator()(const ComboAddress& lhs, const ComboAddress& rhs) const |
11a7242f | 169 | { |
f67ce892 | 170 | if (lhs.sin4.sin_family < rhs.sin4.sin_family) { |
4957a608 | 171 | return true; |
f67ce892 OM |
172 | } |
173 | if (lhs.sin4.sin_family > rhs.sin4.sin_family) { | |
4957a608 | 174 | return false; |
f67ce892 OM |
175 | } |
176 | if (lhs.sin4.sin_family == AF_INET) { | |
177 | return lhs.sin4.sin_addr.s_addr < rhs.sin4.sin_addr.s_addr; | |
178 | } | |
179 | return memcmp(&lhs.sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, sizeof(lhs.sin6.sin6_addr.s6_addr)) < 0; | |
11a7242f BH |
180 | } |
181 | }; | |
fd4ed0ab | 182 | |
7587bcbe | 183 | struct addressOnlyEqual |
0940e4eb | 184 | { |
f67ce892 | 185 | bool operator()(const ComboAddress& lhs, const ComboAddress& rhs) const |
0940e4eb | 186 | { |
f67ce892 | 187 | if (lhs.sin4.sin_family != rhs.sin4.sin_family) { |
0940e4eb | 188 | return false; |
f67ce892 OM |
189 | } |
190 | if (lhs.sin4.sin_family == AF_INET) { | |
191 | return lhs.sin4.sin_addr.s_addr == rhs.sin4.sin_addr.s_addr; | |
192 | } | |
193 | return memcmp(&lhs.sin6.sin6_addr.s6_addr, &rhs.sin6.sin6_addr.s6_addr, sizeof(lhs.sin6.sin6_addr.s6_addr)) == 0; | |
0940e4eb | 194 | } |
195 | }; | |
196 | ||
f67ce892 | 197 | [[nodiscard]] socklen_t getSocklen() const |
a9af3782 | 198 | { |
f67ce892 | 199 | if (sin4.sin_family == AF_INET) { |
a9af3782 | 200 | return sizeof(sin4); |
f67ce892 OM |
201 | } |
202 | return sizeof(sin6); | |
a9af3782 | 203 | } |
389fa92e SB |
204 | |
205 | ComboAddress() | |
fd4ed0ab | 206 | { |
07203482 OM |
207 | sin4.sin_family = AF_INET; |
208 | sin4.sin_addr.s_addr = 0; | |
209 | sin4.sin_port = 0; | |
5cc8371b RG |
210 | sin6.sin6_scope_id = 0; |
211 | sin6.sin6_flowinfo = 0; | |
fd4ed0ab BH |
212 | } |
213 | ||
f67ce892 | 214 | ComboAddress(const struct sockaddr* socketAddress, socklen_t salen) |
07203482 | 215 | { |
f67ce892 | 216 | setSockaddr(socketAddress, salen); |
a7360cd9 AT |
217 | }; |
218 | ||
f67ce892 | 219 | ComboAddress(const struct sockaddr_in6* socketAddress) |
07203482 | 220 | { |
f67ce892 OM |
221 | // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast) |
222 | setSockaddr(reinterpret_cast<const struct sockaddr*>(socketAddress), sizeof(struct sockaddr_in6)); | |
a7360cd9 AT |
223 | }; |
224 | ||
f67ce892 | 225 | ComboAddress(const struct sockaddr_in* socketAddress) |
07203482 | 226 | { |
f67ce892 OM |
227 | // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast) |
228 | setSockaddr(reinterpret_cast<const struct sockaddr*>(socketAddress), sizeof(struct sockaddr_in)); | |
a7360cd9 AT |
229 | }; |
230 | ||
f67ce892 | 231 | void setSockaddr(const struct sockaddr* socketAddress, socklen_t salen) |
07203482 | 232 | { |
f67ce892 | 233 | if (salen > sizeof(struct sockaddr_in6)) { |
07203482 | 234 | throw PDNSException("ComboAddress can't handle other than sockaddr_in or sockaddr_in6"); |
f67ce892 OM |
235 | } |
236 | memcpy(this, socketAddress, salen); | |
a7360cd9 AT |
237 | } |
238 | ||
85db02c5 | 239 | // 'port' sets a default value in case 'str' does not set a port |
07203482 | 240 | explicit ComboAddress(const string& str, uint16_t port = 0) |
fd4ed0ab BH |
241 | { |
242 | memset(&sin6, 0, sizeof(sin6)); | |
243 | sin4.sin_family = AF_INET; | |
85db02c5 | 244 | sin4.sin_port = 0; |
f67ce892 | 245 | if (makeIPv4sockaddr(str, &sin4) != 0) { |
fd4ed0ab | 246 | sin6.sin6_family = AF_INET6; |
07203482 OM |
247 | if (makeIPv6sockaddr(str, &sin6) < 0) { |
248 | throw PDNSException("Unable to convert presentation address '" + str + "'"); | |
c0f8e484 | 249 | } |
fd4ed0ab | 250 | } |
f67ce892 | 251 | if (sin4.sin_port == 0) { // 'str' overrides port! |
07203482 | 252 | sin4.sin_port = htons(port); |
f67ce892 | 253 | } |
fd4ed0ab | 254 | } |
a9af3782 | 255 | |
f67ce892 | 256 | [[nodiscard]] bool isIPv6() const |
a94673ea RG |
257 | { |
258 | return sin4.sin_family == AF_INET6; | |
259 | } | |
f67ce892 | 260 | [[nodiscard]] bool isIPv4() const |
a94673ea RG |
261 | { |
262 | return sin4.sin_family == AF_INET; | |
263 | } | |
264 | ||
f67ce892 | 265 | [[nodiscard]] bool isMappedIPv4() const |
2914b022 | 266 | { |
f67ce892 | 267 | if (sin4.sin_family != AF_INET6) { |
2914b022 | 268 | return false; |
f67ce892 | 269 | } |
389fa92e | 270 | |
f67ce892 OM |
271 | int iter = 0; |
272 | // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast) | |
273 | const auto* ptr = reinterpret_cast<const unsigned char*>(&sin6.sin6_addr.s6_addr); | |
274 | for (iter = 0; iter < 10; ++iter) { | |
275 | if (ptr[iter] != 0) { // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic) | |
4957a608 | 276 | return false; |
f67ce892 OM |
277 | } |
278 | } | |
279 | for (; iter < 12; ++iter) { | |
280 | if (ptr[iter] != 0xff) { // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic) | |
4957a608 | 281 | return false; |
f67ce892 OM |
282 | } |
283 | } | |
2914b022 BH |
284 | return true; |
285 | } | |
389fa92e | 286 | |
f67ce892 | 287 | [[nodiscard]] ComboAddress mapToIPv4() const |
2914b022 | 288 | { |
f67ce892 | 289 | if (!isMappedIPv4()) { |
3f81d239 | 290 | throw PDNSException("ComboAddress can't map non-mapped IPv6 address back to IPv4"); |
f67ce892 | 291 | } |
2914b022 | 292 | ComboAddress ret; |
07203482 OM |
293 | ret.sin4.sin_family = AF_INET; |
294 | ret.sin4.sin_port = sin4.sin_port; | |
389fa92e | 295 | |
f67ce892 OM |
296 | // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast) |
297 | const auto* ptr = reinterpret_cast<const unsigned char*>(&sin6.sin6_addr.s6_addr); | |
298 | ptr += (sizeof(sin6.sin6_addr.s6_addr) - sizeof(ret.sin4.sin_addr.s_addr)); // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic) | |
a683e8bd | 299 | memcpy(&ret.sin4.sin_addr.s_addr, ptr, sizeof(ret.sin4.sin_addr.s_addr)); |
2914b022 BH |
300 | return ret; |
301 | } | |
302 | ||
f67ce892 | 303 | [[nodiscard]] string toString() const |
37d3f960 | 304 | { |
f67ce892 OM |
305 | std::array<char, 1024> host{}; |
306 | if (sin4.sin_family != 0) { | |
209a907a | 307 | // NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast) |
f67ce892 OM |
308 | int retval = getnameinfo(reinterpret_cast<const struct sockaddr*>(this), getSocklen(), host.data(), host.size(), nullptr, 0, NI_NUMERICHOST); |
309 | if (retval == 0) { | |
310 | return host.data(); | |
311 | } | |
07203482 | 312 | return "invalid " + string(gai_strerror(retval)); |
f67ce892 OM |
313 | } |
314 | return "invalid"; | |
37d3f960 | 315 | } |
b8c3ea84 | 316 | |
f5afee4d | 317 | //! Ignores any interface specifiers possibly available in the sockaddr data. |
f67ce892 | 318 | [[nodiscard]] string toStringNoInterface() const |
f5afee4d | 319 | { |
f67ce892 OM |
320 | std::array<char, 1024> host{}; |
321 | if (sin4.sin_family == AF_INET) { | |
322 | const auto* ret = inet_ntop(sin4.sin_family, &sin4.sin_addr, host.data(), host.size()); | |
323 | if (ret != nullptr) { | |
324 | return host.data(); | |
325 | } | |
326 | } | |
327 | else if (sin4.sin_family == AF_INET6) { | |
209a907a | 328 | const auto* ret = inet_ntop(sin4.sin_family, &sin6.sin6_addr, host.data(), host.size()); |
f67ce892 OM |
329 | if (ret != nullptr) { |
330 | return host.data(); | |
331 | } | |
332 | } | |
333 | return "invalid " + stringerror(); | |
f5afee4d CH |
334 | } |
335 | ||
b56aad58 FM |
336 | [[nodiscard]] string toStringReversed() const |
337 | { | |
338 | if (isIPv4()) { | |
f67ce892 OM |
339 | const auto address = ntohl(sin4.sin_addr.s_addr); |
340 | auto aaa = (address >> 0) & 0xFF; | |
341 | auto bbb = (address >> 8) & 0xFF; | |
342 | auto ccc = (address >> 16) & 0xFF; | |
343 | auto ddd = (address >> 24) & 0xFF; | |
344 | return std::to_string(aaa) + "." + std::to_string(bbb) + "." + std::to_string(ccc) + "." + std::to_string(ddd); | |
345 | } | |
346 | const auto* addr = &sin6.sin6_addr; | |
347 | std::stringstream res{}; | |
348 | res << std::hex; | |
349 | for (int i = 15; i >= 0; i--) { | |
350 | auto byte = addr->s6_addr[i]; // NOLINT(cppcoreguidelines-pro-bounds-constant-array-index) | |
351 | res << ((byte >> 0) & 0xF) << "."; | |
352 | res << ((byte >> 4) & 0xF); | |
353 | if (i != 0) { | |
354 | res << "."; | |
b56aad58 | 355 | } |
b56aad58 | 356 | } |
f67ce892 | 357 | return res.str(); |
b56aad58 FM |
358 | } |
359 | ||
f67ce892 | 360 | [[nodiscard]] string toStringWithPort() const |
b8c3ea84 | 361 | { |
f67ce892 | 362 | if (sin4.sin_family == AF_INET) { |
335da0ba | 363 | return toString() + ":" + std::to_string(ntohs(sin4.sin_port)); |
f67ce892 OM |
364 | } |
365 | return "[" + toString() + "]:" + std::to_string(ntohs(sin4.sin_port)); | |
b8c3ea84 | 366 | } |
22779196 | 367 | |
f67ce892 | 368 | [[nodiscard]] string toStringWithPortExcept(int port) const |
d622042f | 369 | { |
f67ce892 | 370 | if (ntohs(sin4.sin_port) == port) { |
d622042f | 371 | return toString(); |
f67ce892 OM |
372 | } |
373 | if (sin4.sin_family == AF_INET) { | |
d622042f | 374 | return toString() + ":" + std::to_string(ntohs(sin4.sin_port)); |
f67ce892 OM |
375 | } |
376 | return "[" + toString() + "]:" + std::to_string(ntohs(sin4.sin_port)); | |
d622042f | 377 | } |
378 | ||
f67ce892 | 379 | [[nodiscard]] string toLogString() const |
9b0f144f KM |
380 | { |
381 | return toStringWithPortExcept(53); | |
382 | } | |
383 | ||
a632f29b OM |
384 | [[nodiscard]] string toStructuredLogString() const |
385 | { | |
386 | return toStringWithPort(); | |
387 | } | |
388 | ||
f67ce892 | 389 | [[nodiscard]] string toByteString() const |
4ef05f92 | 390 | { |
f67ce892 | 391 | // NOLINTBEGIN(cppcoreguidelines-pro-type-reinterpret-cast) |
4ef05f92 | 392 | if (isIPv4()) { |
f67ce892 | 393 | return {reinterpret_cast<const char*>(&sin4.sin_addr.s_addr), sizeof(sin4.sin_addr.s_addr)}; |
4ef05f92 | 394 | } |
f67ce892 OM |
395 | return {reinterpret_cast<const char*>(&sin6.sin6_addr.s6_addr), sizeof(sin6.sin6_addr.s6_addr)}; |
396 | // NOLINTEND(cppcoreguidelines-pro-type-reinterpret-cast) | |
4ef05f92 PL |
397 | } |
398 | ||
5b6099b2 | 399 | void truncate(unsigned int bits) noexcept; |
0affb140 | 400 | |
f67ce892 | 401 | [[nodiscard]] uint16_t getNetworkOrderPort() const noexcept |
0affb140 | 402 | { |
a61dd3f3 Y |
403 | return sin4.sin_port; |
404 | } | |
f67ce892 | 405 | [[nodiscard]] uint16_t getPort() const noexcept |
a61dd3f3 Y |
406 | { |
407 | return ntohs(getNetworkOrderPort()); | |
0affb140 | 408 | } |
79816288 | 409 | void setPort(uint16_t port) |
f43e6a40 | 410 | { |
79816288 | 411 | sin4.sin_port = htons(port); |
f43e6a40 KM |
412 | } |
413 | ||
d38e2ba9 RG |
414 | void reset() |
415 | { | |
416 | memset(&sin4, 0, sizeof(sin4)); | |
417 | memset(&sin6, 0, sizeof(sin6)); | |
418 | } | |
419 | ||
20c33d95 | 420 | //! Get the total number of address bits (either 32 or 128 depending on IP version) |
f67ce892 | 421 | [[nodiscard]] uint8_t getBits() const |
20c33d95 | 422 | { |
f67ce892 | 423 | if (isIPv4()) { |
20c33d95 | 424 | return 32; |
f67ce892 OM |
425 | } |
426 | if (isIPv6()) { | |
20c33d95 | 427 | return 128; |
f67ce892 | 428 | } |
20c33d95 SB |
429 | return 0; |
430 | } | |
cdd23120 SB |
431 | /** Get the value of the bit at the provided bit index. When the index >= 0, |
432 | the index is relative to the LSB starting at index zero. When the index < 0, | |
433 | the index is relative to the MSB starting at index -1 and counting down. | |
434 | */ | |
f67ce892 | 435 | [[nodiscard]] bool getBit(int index) const |
cdd23120 | 436 | { |
07203482 | 437 | if (isIPv4()) { |
f67ce892 | 438 | if (index >= 32) { |
cdd23120 | 439 | return false; |
f67ce892 | 440 | } |
cdd23120 | 441 | if (index < 0) { |
f67ce892 | 442 | if (index < -32) { |
cdd23120 | 443 | return false; |
f67ce892 | 444 | } |
cdd23120 SB |
445 | index = 32 + index; |
446 | } | |
447 | ||
a3739f30 | 448 | uint32_t ls_addr = ntohl(sin4.sin_addr.s_addr); |
cdd23120 | 449 | |
07203482 | 450 | return ((ls_addr & (1U << index)) != 0x00000000); |
cdd23120 | 451 | } |
07203482 | 452 | if (isIPv6()) { |
f67ce892 | 453 | if (index >= 128) { |
cdd23120 | 454 | return false; |
f67ce892 | 455 | } |
cdd23120 | 456 | if (index < 0) { |
f67ce892 | 457 | if (index < -128) { |
cdd23120 | 458 | return false; |
f67ce892 | 459 | } |
cdd23120 SB |
460 | index = 128 + index; |
461 | } | |
462 | ||
f67ce892 | 463 | const auto* ls_addr = reinterpret_cast<const uint8_t*>(sin6.sin6_addr.s6_addr); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast) |
cdd23120 SB |
464 | uint8_t byte_idx = index / 8; |
465 | uint8_t bit_idx = index % 8; | |
466 | ||
f67ce892 | 467 | return ((ls_addr[15 - byte_idx] & (1U << bit_idx)) != 0x00); // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic) |
cdd23120 SB |
468 | } |
469 | return false; | |
470 | } | |
27a82613 PL |
471 | |
472 | /*! Returns a comma-separated string of IP addresses | |
473 | * | |
474 | * \param c An stl container with ComboAddresses | |
475 | * \param withPort Also print the port (default true) | |
476 | * \param portExcept Print the port, except when this is the port (default 53) | |
477 | */ | |
07203482 | 478 | template <template <class...> class Container, class... Args> |
f67ce892 | 479 | static string caContainerToString(const Container<ComboAddress, Args...>& container, const bool withPort = true, const uint16_t portExcept = 53) |
07203482 OM |
480 | { |
481 | vector<string> strs; | |
f67ce892 | 482 | for (const auto& address : container) { |
07203482 | 483 | if (withPort) { |
f67ce892 | 484 | strs.push_back(address.toStringWithPortExcept(portExcept)); |
07203482 OM |
485 | continue; |
486 | } | |
f67ce892 | 487 | strs.push_back(address.toString()); |
27a82613 | 488 | } |
07203482 | 489 | return boost::join(strs, ","); |
27a82613 | 490 | }; |
37d3f960 BH |
491 | }; |
492 | ||
12c86877 | 493 | /** This exception is thrown by the Netmask class and by extension by the NetmaskGroup class */ |
07203482 | 494 | class NetmaskException : public PDNSException |
12c86877 BH |
495 | { |
496 | public: | |
f67ce892 OM |
497 | NetmaskException(const string& arg) : |
498 | PDNSException(arg) {} | |
12c86877 BH |
499 | }; |
500 | ||
37d3f960 BH |
501 | inline ComboAddress makeComboAddress(const string& str) |
502 | { | |
503 | ComboAddress address; | |
07203482 OM |
504 | address.sin4.sin_family = AF_INET; |
505 | if (inet_pton(AF_INET, str.c_str(), &address.sin4.sin_addr) <= 0) { | |
506 | address.sin4.sin_family = AF_INET6; | |
f67ce892 | 507 | if (makeIPv6sockaddr(str, &address.sin6) < 0) { |
07203482 | 508 | throw NetmaskException("Unable to convert '" + str + "' to a netmask"); |
f67ce892 | 509 | } |
37d3f960 BH |
510 | } |
511 | return address; | |
512 | } | |
513 | ||
5cc8371b | 514 | inline ComboAddress makeComboAddressFromRaw(uint8_t version, const char* raw, size_t len) |
f4352636 PD |
515 | { |
516 | ComboAddress address; | |
f4352636 | 517 | |
45fab880 | 518 | if (version == 4) { |
5cc8371b | 519 | address.sin4.sin_family = AF_INET; |
f67ce892 | 520 | if (len != sizeof(address.sin4.sin_addr)) { |
07203482 | 521 | throw NetmaskException("invalid raw address length"); |
f67ce892 | 522 | } |
5cc8371b | 523 | memcpy(&address.sin4.sin_addr, raw, sizeof(address.sin4.sin_addr)); |
45fab880 PD |
524 | } |
525 | else if (version == 6) { | |
5cc8371b | 526 | address.sin6.sin6_family = AF_INET6; |
f67ce892 | 527 | if (len != sizeof(address.sin6.sin6_addr)) { |
07203482 | 528 | throw NetmaskException("invalid raw address length"); |
f67ce892 | 529 | } |
5cc8371b | 530 | memcpy(&address.sin6.sin6_addr, raw, sizeof(address.sin6.sin6_addr)); |
45fab880 | 531 | } |
f67ce892 | 532 | else { |
07203482 | 533 | throw NetmaskException("invalid address family"); |
f67ce892 | 534 | } |
f4352636 PD |
535 | |
536 | return address; | |
537 | } | |
538 | ||
07203482 | 539 | inline ComboAddress makeComboAddressFromRaw(uint8_t version, const string& str) |
5cc8371b RG |
540 | { |
541 | return makeComboAddressFromRaw(version, str.c_str(), str.size()); | |
542 | } | |
543 | ||
12c86877 BH |
544 | /** This class represents a netmask and can be queried to see if a certain |
545 | IP address is matched by this mask */ | |
12c86877 BH |
546 | class Netmask |
547 | { | |
548 | public: | |
6f97329b BH |
549 | Netmask() |
550 | { | |
7c408ab4 | 551 | d_network.sin4.sin_family = 0; // disable this doing anything useful |
389fa92e | 552 | d_network.sin4.sin_port = 0; // this guarantees d_network compares identical |
6f97329b | 553 | } |
389fa92e | 554 | |
07203482 OM |
555 | Netmask(const ComboAddress& network, uint8_t bits = 0xff) : |
556 | d_network(network) | |
6f97329b | 557 | { |
7c408ab4 | 558 | d_network.sin4.sin_port = 0; |
7d6458b7 | 559 | setBits(bits); |
7c408ab4 | 560 | } |
389fa92e | 561 | |
07203482 OM |
562 | Netmask(const sockaddr_in* network, uint8_t bits = 0xff) : |
563 | d_network(network) | |
783b8632 Y |
564 | { |
565 | d_network.sin4.sin_port = 0; | |
7d6458b7 | 566 | setBits(bits); |
783b8632 | 567 | } |
07203482 OM |
568 | Netmask(const sockaddr_in6* network, uint8_t bits = 0xff) : |
569 | d_network(network) | |
783b8632 Y |
570 | { |
571 | d_network.sin4.sin_port = 0; | |
7d6458b7 | 572 | setBits(bits); |
783b8632 | 573 | } |
7c408ab4 RG |
574 | void setBits(uint8_t value) |
575 | { | |
7d6458b7 | 576 | d_bits = d_network.isIPv4() ? std::min(value, static_cast<uint8_t>(32U)) : std::min(value, static_cast<uint8_t>(128U)); |
7c408ab4 RG |
577 | |
578 | if (d_bits < 32) { | |
579 | d_mask = ~(0xFFFFFFFF >> d_bits); | |
580 | } | |
581 | else { | |
582 | // note that d_mask is unused for IPv6 | |
583 | d_mask = 0xFFFFFFFF; | |
584 | } | |
585 | ||
586 | if (isIPv4()) { | |
587 | d_network.sin4.sin_addr.s_addr = htonl(ntohl(d_network.sin4.sin_addr.s_addr) & d_mask); | |
588 | } | |
589 | else if (isIPv6()) { | |
07203482 | 590 | uint8_t bytes = d_bits / 8; |
f67ce892 | 591 | auto* address = reinterpret_cast<uint8_t*>(&d_network.sin6.sin6_addr.s6_addr); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast) |
7c408ab4 | 592 | uint8_t bits = d_bits % 8; |
f67ce892 | 593 | auto mask = static_cast<uint8_t>(~(0xFF >> bits)); |
7c408ab4 RG |
594 | |
595 | if (bytes < sizeof(d_network.sin6.sin6_addr.s6_addr)) { | |
f67ce892 | 596 | address[bytes] &= mask; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic) |
7c408ab4 RG |
597 | } |
598 | ||
07203482 | 599 | for (size_t idx = bytes + 1; idx < sizeof(d_network.sin6.sin6_addr.s6_addr); ++idx) { |
f67ce892 | 600 | address[idx] = 0; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic) |
7c408ab4 RG |
601 | } |
602 | } | |
6f97329b | 603 | } |
389fa92e SB |
604 | |
605 | //! Constructor supplies the mask, which cannot be changed | |
07203482 | 606 | Netmask(const string& mask) |
12c86877 | 607 | { |
07203482 | 608 | pair<string, string> split = splitField(mask, '/'); |
7c408ab4 | 609 | d_network = makeComboAddress(split.first); |
389fa92e | 610 | |
7c408ab4 | 611 | if (!split.second.empty()) { |
a0383aad | 612 | setBits(pdns::checked_stoi<uint8_t>(split.second)); |
37d3f960 | 613 | } |
7c408ab4 RG |
614 | else if (d_network.sin4.sin_family == AF_INET) { |
615 | setBits(32); | |
37d3f960 | 616 | } |
5c1def57 | 617 | else { |
7c408ab4 | 618 | setBits(128); |
5c1def57 | 619 | } |
12c86877 BH |
620 | } |
621 | ||
f67ce892 | 622 | [[nodiscard]] bool match(const ComboAddress& address) const |
2914b022 | 623 | { |
f67ce892 | 624 | return match(&address); |
2914b022 BH |
625 | } |
626 | ||
12c86877 | 627 | //! If this IP address in socket address matches |
f67ce892 | 628 | bool match(const ComboAddress* address) const |
12c86877 | 629 | { |
f67ce892 | 630 | if (d_network.sin4.sin_family != address->sin4.sin_family) { |
37d3f960 BH |
631 | return false; |
632 | } | |
07203482 | 633 | if (d_network.sin4.sin_family == AF_INET) { |
f67ce892 | 634 | return match4(htonl((unsigned int)address->sin4.sin_addr.s_addr)); |
37d3f960 | 635 | } |
07203482 | 636 | if (d_network.sin6.sin6_family == AF_INET6) { |
f67ce892 OM |
637 | uint8_t bytes = d_bits / 8; |
638 | uint8_t index = 0; | |
639 | // NOLINTBEGIN(cppcoreguidelines-pro-type-reinterpret-cast) | |
640 | const auto* lhs = reinterpret_cast<const uint8_t*>(&d_network.sin6.sin6_addr.s6_addr); | |
641 | const auto* rhs = reinterpret_cast<const uint8_t*>(&address->sin6.sin6_addr.s6_addr); | |
642 | // NOLINTEND(cppcoreguidelines-pro-type-reinterpret-cast) | |
643 | ||
644 | // NOLINTBEGIN(cppcoreguidelines-pro-bounds-pointer-arithmetic) | |
645 | for (index = 0; index < bytes; ++index) { | |
646 | if (lhs[index] != rhs[index]) { | |
4957a608 BH |
647 | return false; |
648 | } | |
37d3f960 BH |
649 | } |
650 | // still here, now match remaining bits | |
07203482 | 651 | uint8_t bits = d_bits % 8; |
f67ce892 | 652 | auto mask = static_cast<uint8_t>(~(0xFF >> bits)); |
f0739fb6 | 653 | |
f67ce892 OM |
654 | return ((lhs[index]) == (rhs[index] & mask)); |
655 | // NOLINTEND(cppcoreguidelines-pro-bounds-pointer-arithmetic) | |
37d3f960 BH |
656 | } |
657 | return false; | |
12c86877 BH |
658 | } |
659 | ||
660 | //! If this ASCII IP address matches | |
f67ce892 | 661 | [[nodiscard]] bool match(const string& arg) const |
12c86877 | 662 | { |
f67ce892 | 663 | ComboAddress address = makeComboAddress(arg); |
37d3f960 | 664 | return match(&address); |
12c86877 BH |
665 | } |
666 | ||
667 | //! If this IP address in native format matches | |
f67ce892 | 668 | [[nodiscard]] bool match4(uint32_t arg) const |
12c86877 | 669 | { |
f67ce892 | 670 | return (arg & d_mask) == (ntohl(d_network.sin4.sin_addr.s_addr)); |
12c86877 BH |
671 | } |
672 | ||
f67ce892 | 673 | [[nodiscard]] string toString() const |
2c95fc65 | 674 | { |
07203482 | 675 | return d_network.toStringNoInterface() + "/" + std::to_string((unsigned int)d_bits); |
2c95fc65 BH |
676 | } |
677 | ||
f67ce892 | 678 | [[nodiscard]] string toStringNoMask() const |
a4c8835f | 679 | { |
f5afee4d | 680 | return d_network.toStringNoInterface(); |
a4c8835f | 681 | } |
7c408ab4 | 682 | |
f67ce892 | 683 | [[nodiscard]] const ComboAddress& getNetwork() const |
a4c8835f BH |
684 | { |
685 | return d_network; | |
686 | } | |
e1c8a4bb | 687 | |
f67ce892 | 688 | [[nodiscard]] const ComboAddress& getMaskedNetwork() const |
7c408ab4 RG |
689 | { |
690 | return getNetwork(); | |
e1c8a4bb | 691 | } |
7c408ab4 | 692 | |
f67ce892 | 693 | [[nodiscard]] uint8_t getBits() const |
a4c8835f BH |
694 | { |
695 | return d_bits; | |
696 | } | |
7c408ab4 | 697 | |
f67ce892 | 698 | [[nodiscard]] bool isIPv6() const |
709ca59f AT |
699 | { |
700 | return d_network.sin6.sin6_family == AF_INET6; | |
701 | } | |
7c408ab4 | 702 | |
f67ce892 | 703 | [[nodiscard]] bool isIPv4() const |
709ca59f AT |
704 | { |
705 | return d_network.sin4.sin_family == AF_INET; | |
706 | } | |
644dd1da | 707 | |
389fa92e | 708 | bool operator<(const Netmask& rhs) const |
644dd1da | 709 | { |
f67ce892 | 710 | if (empty() && !rhs.empty()) { |
a009559d | 711 | return false; |
f67ce892 OM |
712 | } |
713 | if (!empty() && rhs.empty()) { | |
a009559d | 714 | return true; |
f67ce892 OM |
715 | } |
716 | if (d_bits > rhs.d_bits) { | |
a009559d | 717 | return true; |
f67ce892 OM |
718 | } |
719 | if (d_bits < rhs.d_bits) { | |
a009559d | 720 | return false; |
f67ce892 | 721 | } |
a009559d RG |
722 | |
723 | return d_network < rhs.d_network; | |
724 | } | |
725 | ||
726 | bool operator>(const Netmask& rhs) const | |
727 | { | |
728 | return rhs.operator<(*this); | |
644dd1da | 729 | } |
39ec5d29 | 730 | |
389fa92e | 731 | bool operator==(const Netmask& rhs) const |
39ec5d29 | 732 | { |
905dae56 | 733 | return std::tie(d_network, d_bits) == std::tie(rhs.d_network, rhs.d_bits); |
39ec5d29 | 734 | } |
735 | ||
f67ce892 | 736 | [[nodiscard]] bool empty() const |
87e665b1 | 737 | { |
07203482 | 738 | return d_network.sin4.sin_family == 0; |
87e665b1 | 739 | } |
740 | ||
e9a5bdb1 | 741 | //! Get normalized version of the netmask. This means that all address bits below the network bits are zero. |
f67ce892 | 742 | [[nodiscard]] Netmask getNormalized() const |
07203482 | 743 | { |
f67ce892 | 744 | return {getMaskedNetwork(), d_bits}; |
e9a5bdb1 | 745 | } |
664140b5 | 746 | //! Get Netmask for super network of this one (i.e. with fewer network bits) |
f67ce892 | 747 | [[nodiscard]] Netmask getSuper(uint8_t bits) const |
07203482 | 748 | { |
f67ce892 | 749 | return {d_network, std::min(d_bits, bits)}; |
664140b5 | 750 | } |
5d7557e3 SB |
751 | |
752 | //! Get the total number of address bits for this netmask (either 32 or 128 depending on IP version) | |
f67ce892 | 753 | [[nodiscard]] uint8_t getFullBits() const |
6d4de128 | 754 | { |
c173228a | 755 | return d_network.getBits(); |
6d4de128 RG |
756 | } |
757 | ||
8d8c1d77 SB |
758 | /** Get the value of the bit at the provided bit index. When the index >= 0, |
759 | the index is relative to the LSB starting at index zero. When the index < 0, | |
760 | the index is relative to the MSB starting at index -1 and counting down. | |
761 | When the index points outside the network bits, it always yields zero. | |
762 | */ | |
f67ce892 | 763 | [[nodiscard]] bool getBit(int bit) const |
8d8c1d77 | 764 | { |
f67ce892 | 765 | if (bit < -d_bits) { |
8d8c1d77 | 766 | return false; |
f67ce892 | 767 | } |
8d8c1d77 | 768 | if (bit >= 0) { |
07203482 | 769 | if (isIPv4()) { |
f67ce892 | 770 | if (bit >= 32 || bit < (32 - d_bits)) { |
8d8c1d77 | 771 | return false; |
f67ce892 | 772 | } |
8d8c1d77 | 773 | } |
209a907a | 774 | if (isIPv6()) { |
f67ce892 | 775 | if (bit >= 128 || bit < (128 - d_bits)) { |
8d8c1d77 | 776 | return false; |
f67ce892 | 777 | } |
8d8c1d77 SB |
778 | } |
779 | } | |
780 | return d_network.getBit(bit); | |
781 | } | |
6d4de128 | 782 | |
07203482 OM |
783 | struct Hash |
784 | { | |
f67ce892 | 785 | size_t operator()(const Netmask& netmask) const |
7da536df | 786 | { |
f67ce892 | 787 | return burtle(&netmask.d_bits, 1, ComboAddress::addressOnlyHash()(netmask.d_network)); |
7da536df OM |
788 | } |
789 | }; | |
790 | ||
12c86877 | 791 | private: |
37d3f960 | 792 | ComboAddress d_network; |
f67ce892 OM |
793 | uint32_t d_mask{0}; |
794 | uint8_t d_bits{0}; | |
12c86877 BH |
795 | }; |
796 | ||
07203482 OM |
797 | namespace std |
798 | { | |
799 | template <> | |
800 | struct hash<Netmask> | |
801 | { | |
f67ce892 | 802 | auto operator()(const Netmask& netmask) const |
07203482 | 803 | { |
f67ce892 | 804 | return Netmask::Hash{}(netmask); |
07203482 OM |
805 | } |
806 | }; | |
7da536df OM |
807 | } |
808 | ||
4bb19027 | 809 | /** Binary tree map implementation with <Netmask,T> pair. |
44845aab AT |
810 | * |
811 | * This is an binary tree implementation for storing attributes for IPv4 and IPv6 prefixes. | |
812 | * The most simple use case is simple NetmaskTree<bool> used by NetmaskGroup, which only | |
813 | * wants to know if given IP address is matched in the prefixes stored. | |
814 | * | |
815 | * This element is useful for anything that needs to *STORE* prefixes, and *MATCH* IP addresses | |
816 | * to a *LIST* of *PREFIXES*. Not the other way round. | |
817 | * | |
818 | * You can store IPv4 and IPv6 addresses to same tree, separate payload storage is kept per AFI. | |
80462253 SB |
819 | * Network prefixes (Netmasks) are always recorded in normalized fashion, meaning that only |
820 | * the network bits are set. This is what is returned in the insert() and lookup() return | |
821 | * values. | |
44845aab | 822 | * |
44845aab | 823 | * Use swap if you need to move the tree to another NetmaskTree instance, it is WAY faster |
ba07e97e | 824 | * than using copy ctor or assignment operator, since it moves the nodes and tree root to |
44845aab AT |
825 | * new home instead of actually recreating the tree. |
826 | * | |
827 | * Please see NetmaskGroup for example of simple use case. Other usecases can be found | |
828 | * from GeoIPBackend and Sortlist, and from dnsdist. | |
829 | */ | |
6d4de128 | 830 | template <typename T, class K = Netmask> |
07203482 OM |
831 | class NetmaskTree |
832 | { | |
44845aab | 833 | public: |
de1cde57 SB |
834 | class Iterator; |
835 | ||
f67ce892 OM |
836 | using key_type = K; |
837 | using value_type = T; | |
838 | using node_type = std::pair<const key_type, value_type>; | |
839 | using size_type = size_t; | |
840 | using iterator = class Iterator; | |
44845aab AT |
841 | |
842 | private: | |
843 | /** Single node in tree, internal use only. | |
07203482 OM |
844 | */ |
845 | class TreeNode : boost::noncopyable | |
846 | { | |
44845aab | 847 | public: |
4bb19027 | 848 | explicit TreeNode() noexcept : |
07203482 OM |
849 | parent(nullptr), node(), assigned(false), d_bits(0) |
850 | { | |
4bb19027 | 851 | } |
2d1e11bf | 852 | explicit TreeNode(const key_type& key) : |
07203482 OM |
853 | parent(nullptr), node({key.getNormalized(), value_type()}), assigned(false), d_bits(key.getFullBits()) |
854 | { | |
389fa92e SB |
855 | } |
856 | ||
4bb19027 | 857 | //<! Makes a left leaf node with specified key. |
07203482 OM |
858 | TreeNode* make_left(const key_type& key) |
859 | { | |
cba13f93 | 860 | d_bits = node.first.getBits(); |
4bb19027 SB |
861 | left = make_unique<TreeNode>(key); |
862 | left->parent = this; | |
389fa92e SB |
863 | return left.get(); |
864 | } | |
865 | ||
4bb19027 | 866 | //<! Makes a right leaf node with specified key. |
07203482 OM |
867 | TreeNode* make_right(const key_type& key) |
868 | { | |
cba13f93 | 869 | d_bits = node.first.getBits(); |
4bb19027 SB |
870 | right = make_unique<TreeNode>(key); |
871 | right->parent = this; | |
389fa92e SB |
872 | return right.get(); |
873 | } | |
874 | ||
4bb19027 | 875 | //<! Splits branch at indicated bit position by inserting key |
07203482 OM |
876 | TreeNode* split(const key_type& key, int bits) |
877 | { | |
4bb19027 SB |
878 | if (parent == nullptr) { |
879 | // not to be called on the root node | |
880 | throw std::logic_error( | |
881 | "NetmaskTree::TreeNode::split(): must not be called on root node"); | |
882 | } | |
883 | ||
884 | // determine reference from parent | |
07203482 | 885 | unique_ptr<TreeNode>& parent_ref = (parent->left.get() == this ? parent->left : parent->right); |
4bb19027 SB |
886 | if (parent_ref.get() != this) { |
887 | throw std::logic_error( | |
888 | "NetmaskTree::TreeNode::split(): parent node reference is invalid"); | |
889 | } | |
890 | ||
747fdbdd | 891 | // create new tree node for the new key and |
4bb19027 | 892 | // attach the new node under our former parent |
a011777c RG |
893 | auto new_intermediate_node = make_unique<TreeNode>(key); |
894 | new_intermediate_node->d_bits = bits; | |
895 | new_intermediate_node->parent = parent; | |
896 | auto* new_intermediate_node_raw = new_intermediate_node.get(); | |
897 | ||
898 | // hereafter new_intermediate points to "this" | |
899 | // ie the child of the new intermediate node | |
900 | std::swap(parent_ref, new_intermediate_node); | |
901 | // and we now assign this to current_node so | |
902 | // it's clear it no longer refers to the new | |
903 | // intermediate node | |
904 | std::unique_ptr<TreeNode> current_node = std::move(new_intermediate_node); | |
4bb19027 SB |
905 | |
906 | // attach "this" node below the new node | |
907 | // (left or right depending on bit) | |
a011777c RG |
908 | // technically the raw pointer escapes the duration of the |
909 | // unique pointer, but just below we store the unique pointer | |
910 | // in the parent, so it lives as long as necessary | |
911 | // coverity[escape] | |
912 | current_node->parent = new_intermediate_node_raw; | |
913 | if (current_node->node.first.getBit(-1 - bits)) { | |
914 | new_intermediate_node_raw->right = std::move(current_node); | |
07203482 OM |
915 | } |
916 | else { | |
a011777c | 917 | new_intermediate_node_raw->left = std::move(current_node); |
4bb19027 SB |
918 | } |
919 | ||
a011777c | 920 | return new_intermediate_node_raw; |
4bb19027 SB |
921 | } |
922 | ||
923 | //<! Forks branch for new key at indicated bit position | |
07203482 OM |
924 | TreeNode* fork(const key_type& key, int bits) |
925 | { | |
4bb19027 SB |
926 | if (parent == nullptr) { |
927 | // not to be called on the root node | |
928 | throw std::logic_error( | |
929 | "NetmaskTree::TreeNode::fork(): must not be called on root node"); | |
930 | } | |
931 | ||
932 | // determine reference from parent | |
07203482 | 933 | unique_ptr<TreeNode>& parent_ref = (parent->left.get() == this ? parent->left : parent->right); |
4bb19027 SB |
934 | if (parent_ref.get() != this) { |
935 | throw std::logic_error( | |
936 | "NetmaskTree::TreeNode::fork(): parent node reference is invalid"); | |
937 | } | |
938 | ||
939 | // create new tree node for the branch point | |
4bb19027 | 940 | |
7846373d RG |
941 | // the current node will now be a child of the new branch node |
942 | // (hereafter new_child1 points to "this") | |
943 | unique_ptr<TreeNode> new_child1 = std::move(parent_ref); | |
4bb19027 | 944 | // attach the branch node under our former parent |
747fdbdd OM |
945 | parent_ref = make_unique<TreeNode>(node.first.getSuper(bits)); |
946 | auto* branch_node = parent_ref.get(); | |
947 | branch_node->d_bits = bits; | |
4bb19027 SB |
948 | branch_node->parent = parent; |
949 | ||
950 | // create second new leaf node for the new key | |
753240f1 RG |
951 | unique_ptr<TreeNode> new_child2 = make_unique<TreeNode>(key); |
952 | TreeNode* new_node = new_child2.get(); | |
4bb19027 SB |
953 | |
954 | // attach the new child nodes below the branch node | |
955 | // (left or right depending on bit) | |
956 | new_child1->parent = branch_node; | |
957 | new_child2->parent = branch_node; | |
07203482 | 958 | if (new_child1->node.first.getBit(-1 - bits)) { |
7846373d RG |
959 | branch_node->right = std::move(new_child1); |
960 | branch_node->left = std::move(new_child2); | |
07203482 OM |
961 | } |
962 | else { | |
7846373d RG |
963 | branch_node->right = std::move(new_child2); |
964 | branch_node->left = std::move(new_child1); | |
4bb19027 | 965 | } |
7846373d RG |
966 | // now we have attached the new unique pointers to the tree: |
967 | // - branch_node is below its parent | |
968 | // - new_child1 (ourselves) is below branch_node | |
969 | // - new_child2, the new leaf node, is below branch_node as well | |
4bb19027 SB |
970 | |
971 | return new_node; | |
972 | } | |
973 | ||
fddcd1cc | 974 | //<! Traverse left branch depth-first |
07203482 | 975 | TreeNode* traverse_l() |
fddcd1cc | 976 | { |
07203482 | 977 | TreeNode* tnode = this; |
fddcd1cc | 978 | |
f67ce892 | 979 | while (tnode->left) { |
fddcd1cc | 980 | tnode = tnode->left.get(); |
f67ce892 | 981 | } |
fddcd1cc SB |
982 | return tnode; |
983 | } | |
984 | ||
985 | //<! Traverse tree depth-first and in-order (L-N-R) | |
07203482 | 986 | TreeNode* traverse_lnr() |
fddcd1cc | 987 | { |
07203482 | 988 | TreeNode* tnode = this; |
fddcd1cc SB |
989 | |
990 | // precondition: descended left as deep as possible | |
991 | if (tnode->right) { | |
992 | // descend right | |
993 | tnode = tnode->right.get(); | |
994 | // descend left as deep as possible and return next node | |
995 | return tnode->traverse_l(); | |
996 | } | |
997 | ||
998 | // ascend to parent | |
999 | while (tnode->parent != nullptr) { | |
07203482 | 1000 | TreeNode* prev_child = tnode; |
fddcd1cc SB |
1001 | tnode = tnode->parent; |
1002 | ||
1003 | // return this node, but only when we come from the left child branch | |
f67ce892 | 1004 | if (tnode->left && tnode->left.get() == prev_child) { |
fddcd1cc | 1005 | return tnode; |
f67ce892 | 1006 | } |
fddcd1cc SB |
1007 | } |
1008 | return nullptr; | |
1009 | } | |
1010 | ||
1011 | //<! Traverse only assigned nodes | |
07203482 | 1012 | TreeNode* traverse_lnr_assigned() |
fddcd1cc | 1013 | { |
07203482 | 1014 | TreeNode* tnode = traverse_lnr(); |
fddcd1cc | 1015 | |
f67ce892 | 1016 | while (tnode != nullptr && !tnode->assigned) { |
fddcd1cc | 1017 | tnode = tnode->traverse_lnr(); |
f67ce892 | 1018 | } |
fddcd1cc SB |
1019 | return tnode; |
1020 | } | |
1021 | ||
389fa92e SB |
1022 | unique_ptr<TreeNode> left; |
1023 | unique_ptr<TreeNode> right; | |
1024 | TreeNode* parent; | |
1025 | ||
cba13f93 | 1026 | node_type node; |
956c6dc4 | 1027 | bool assigned; //<! Whether this node is assigned-to by the application |
389fa92e SB |
1028 | |
1029 | int d_bits; //<! How many bits have been used so far | |
44845aab AT |
1030 | }; |
1031 | ||
9b0ae5c8 SB |
1032 | void cleanup_tree(TreeNode* node) |
1033 | { | |
956c6dc4 SB |
1034 | // only cleanup this node if it has no children and node not assigned |
1035 | if (!(node->left || node->right || node->assigned)) { | |
9b0ae5c8 SB |
1036 | // get parent node ptr |
1037 | TreeNode* pparent = node->parent; | |
1038 | // delete this node | |
1039 | if (pparent) { | |
f67ce892 | 1040 | if (pparent->left.get() == node) { |
9b0ae5c8 | 1041 | pparent->left.reset(); |
f67ce892 OM |
1042 | } |
1043 | else { | |
9b0ae5c8 | 1044 | pparent->right.reset(); |
f67ce892 | 1045 | } |
9b0ae5c8 SB |
1046 | // now recurse up to the parent |
1047 | cleanup_tree(pparent); | |
1048 | } | |
1049 | } | |
1050 | } | |
1051 | ||
6d49c384 | 1052 | void copyTree(const NetmaskTree& rhs) |
57e9d089 OM |
1053 | { |
1054 | try { | |
07203482 | 1055 | TreeNode* node = rhs.d_root.get(); |
f67ce892 | 1056 | if (node != nullptr) { |
57e9d089 | 1057 | node = node->traverse_l(); |
f67ce892 | 1058 | } |
57e9d089 | 1059 | while (node != nullptr) { |
f67ce892 | 1060 | if (node->assigned) { |
57e9d089 | 1061 | insert(node->node.first).second = node->node.second; |
f67ce892 | 1062 | } |
57e9d089 OM |
1063 | node = node->traverse_lnr(); |
1064 | } | |
1065 | } | |
6d49c384 | 1066 | catch (const NetmaskException&) { |
57e9d089 | 1067 | abort(); |
1355a23f | 1068 | } |
a43e77a5 OM |
1069 | catch (const std::logic_error&) { |
1070 | abort(); | |
1071 | } | |
1355a23f | 1072 | } |
747fdbdd | 1073 | |
de1cde57 | 1074 | public: |
07203482 OM |
1075 | class Iterator |
1076 | { | |
de1cde57 | 1077 | public: |
f67ce892 | 1078 | using value_type = node_type; |
209a907a OM |
1079 | using reference = node_type&; |
1080 | using pointer = node_type*; | |
f67ce892 OM |
1081 | using iterator_category = std::forward_iterator_tag; |
1082 | using difference_type = size_type; | |
de1cde57 SB |
1083 | |
1084 | private: | |
1085 | friend class NetmaskTree; | |
1086 | ||
1087 | const NetmaskTree* d_tree; | |
1088 | TreeNode* d_node; | |
1089 | ||
07203482 OM |
1090 | Iterator(const NetmaskTree* tree, TreeNode* node) : |
1091 | d_tree(tree), d_node(node) | |
1092 | { | |
de1cde57 SB |
1093 | } |
1094 | ||
1095 | public: | |
07203482 OM |
1096 | Iterator() : |
1097 | d_tree(nullptr), d_node(nullptr) {} | |
de1cde57 SB |
1098 | |
1099 | Iterator& operator++() // prefix | |
1100 | { | |
1101 | if (d_node == nullptr) { | |
1102 | throw std::logic_error( | |
1103 | "NetmaskTree::Iterator::operator++: iterator is invalid"); | |
1104 | } | |
1105 | d_node = d_node->traverse_lnr_assigned(); | |
1106 | return *this; | |
1107 | } | |
1108 | Iterator operator++(int) // postfix | |
1109 | { | |
1110 | Iterator tmp(*this); | |
1111 | operator++(); | |
1112 | return tmp; | |
1113 | } | |
1114 | ||
1115 | reference operator*() | |
1116 | { | |
1117 | if (d_node == nullptr) { | |
1118 | throw std::logic_error( | |
1119 | "NetmaskTree::Iterator::operator*: iterator is invalid"); | |
1120 | } | |
7c888097 SB |
1121 | return d_node->node; |
1122 | } | |
1123 | ||
1124 | pointer operator->() | |
1125 | { | |
1126 | if (d_node == nullptr) { | |
1127 | throw std::logic_error( | |
1128 | "NetmaskTree::Iterator::operator->: iterator is invalid"); | |
1129 | } | |
cba13f93 | 1130 | return &d_node->node; |
de1cde57 SB |
1131 | } |
1132 | ||
1133 | bool operator==(const Iterator& rhs) | |
1134 | { | |
1135 | return (d_tree == rhs.d_tree && d_node == rhs.d_node); | |
1136 | } | |
1137 | bool operator!=(const Iterator& rhs) | |
1138 | { | |
1139 | return !(*this == rhs); | |
1140 | } | |
1141 | }; | |
1142 | ||
07203482 | 1143 | NetmaskTree() noexcept : |
f67ce892 | 1144 | d_root(new TreeNode()), d_left(nullptr) |
07203482 | 1145 | { |
44845aab AT |
1146 | } |
1147 | ||
07203482 | 1148 | NetmaskTree(const NetmaskTree& rhs) : |
f67ce892 | 1149 | d_root(new TreeNode()), d_left(nullptr) |
07203482 | 1150 | { |
1355a23f | 1151 | copyTree(rhs); |
44845aab AT |
1152 | } |
1153 | ||
747fdbdd OM |
1154 | ~NetmaskTree() = default; |
1155 | ||
07203482 OM |
1156 | NetmaskTree& operator=(const NetmaskTree& rhs) |
1157 | { | |
f67ce892 OM |
1158 | if (this != &rhs) { |
1159 | clear(); | |
1160 | copyTree(rhs); | |
1161 | } | |
44845aab AT |
1162 | return *this; |
1163 | } | |
1164 | ||
747fdbdd OM |
1165 | NetmaskTree(NetmaskTree&&) noexcept = default; |
1166 | NetmaskTree& operator=(NetmaskTree&&) noexcept = default; | |
1167 | ||
f67ce892 | 1168 | [[nodiscard]] iterator begin() const |
07203482 | 1169 | { |
de1cde57 SB |
1170 | return Iterator(this, d_left); |
1171 | } | |
f67ce892 | 1172 | [[nodiscard]] iterator end() const |
07203482 | 1173 | { |
de1cde57 SB |
1174 | return Iterator(this, nullptr); |
1175 | } | |
07203482 OM |
1176 | iterator begin() |
1177 | { | |
de1cde57 SB |
1178 | return Iterator(this, d_left); |
1179 | } | |
07203482 OM |
1180 | iterator end() |
1181 | { | |
de1cde57 SB |
1182 | return Iterator(this, nullptr); |
1183 | } | |
44845aab | 1184 | |
07203482 OM |
1185 | node_type& insert(const string& mask) |
1186 | { | |
44845aab AT |
1187 | return insert(key_type(mask)); |
1188 | } | |
1189 | ||
1190 | //<! Creates new value-pair in tree and returns it. | |
07203482 OM |
1191 | node_type& insert(const key_type& key) |
1192 | { | |
f67ce892 | 1193 | TreeNode* node{}; |
9edc8e2b | 1194 | bool is_left = true; |
136b2c6b SB |
1195 | |
1196 | // we turn left on IPv4 and right on IPv6 | |
1197 | if (key.isIPv4()) { | |
136b2c6b | 1198 | node = d_root->left.get(); |
4bb19027 | 1199 | if (node == nullptr) { |
747fdbdd OM |
1200 | |
1201 | d_root->left = make_unique<TreeNode>(key); | |
1202 | node = d_root->left.get(); | |
4bb19027 SB |
1203 | node->assigned = true; |
1204 | node->parent = d_root.get(); | |
dccd4976 | 1205 | d_size++; |
9edc8e2b | 1206 | d_left = node; |
cba13f93 | 1207 | return node->node; |
4bb19027 | 1208 | } |
07203482 OM |
1209 | } |
1210 | else if (key.isIPv6()) { | |
136b2c6b | 1211 | node = d_root->right.get(); |
4bb19027 | 1212 | if (node == nullptr) { |
747fdbdd OM |
1213 | |
1214 | d_root->right = make_unique<TreeNode>(key); | |
1215 | node = d_root->right.get(); | |
4bb19027 SB |
1216 | node->assigned = true; |
1217 | node->parent = d_root.get(); | |
dccd4976 | 1218 | d_size++; |
f67ce892 | 1219 | if (!d_root->left) { |
9edc8e2b | 1220 | d_left = node; |
f67ce892 | 1221 | } |
cba13f93 | 1222 | return node->node; |
4bb19027 | 1223 | } |
f67ce892 | 1224 | if (d_root->left) { |
9edc8e2b | 1225 | is_left = false; |
f67ce892 | 1226 | } |
07203482 | 1227 | } |
f67ce892 | 1228 | else { |
136b2c6b | 1229 | throw NetmaskException("invalid address family"); |
f67ce892 | 1230 | } |
136b2c6b | 1231 | |
136b2c6b | 1232 | // we turn left on 0 and right on 1 |
ebb7e215 | 1233 | int bits = 0; |
07203482 OM |
1234 | for (; bits < key.getBits(); bits++) { |
1235 | bool vall = key.getBit(-1 - bits); | |
4bb19027 SB |
1236 | |
1237 | if (bits >= node->d_bits) { | |
1238 | // the end of the current node is reached; continue with the next | |
1239 | if (vall) { | |
f67ce892 | 1240 | if (node->left || node->assigned) { |
9edc8e2b | 1241 | is_left = false; |
f67ce892 | 1242 | } |
4bb19027 SB |
1243 | if (!node->right) { |
1244 | // the right branch doesn't exist yet; attach our key here | |
1245 | node = node->make_right(key); | |
1246 | break; | |
1247 | } | |
1248 | node = node->right.get(); | |
07203482 OM |
1249 | } |
1250 | else { | |
4bb19027 SB |
1251 | if (!node->left) { |
1252 | // the left branch doesn't exist yet; attach our key here | |
1253 | node = node->make_left(key); | |
1254 | break; | |
1255 | } | |
1256 | node = node->left.get(); | |
1257 | } | |
1258 | continue; | |
1259 | } | |
cba13f93 | 1260 | if (bits >= node->node.first.getBits()) { |
4bb19027 SB |
1261 | // the matching branch ends here, yet the key netmask has more bits; add a |
1262 | // child node below the existing branch leaf. | |
1263 | if (vall) { | |
f67ce892 | 1264 | if (node->assigned) { |
9edc8e2b | 1265 | is_left = false; |
f67ce892 | 1266 | } |
4bb19027 | 1267 | node = node->make_right(key); |
07203482 OM |
1268 | } |
1269 | else { | |
4bb19027 SB |
1270 | node = node->make_left(key); |
1271 | } | |
1272 | break; | |
1273 | } | |
07203482 | 1274 | bool valr = node->node.first.getBit(-1 - bits); |
4bb19027 | 1275 | if (vall != valr) { |
f67ce892 | 1276 | if (vall) { |
9edc8e2b | 1277 | is_left = false; |
f67ce892 | 1278 | } |
4bb19027 SB |
1279 | // the branch matches just upto this point, yet continues in a different |
1280 | // direction; fork the branch. | |
1281 | node = node->fork(key, bits); | |
1282 | break; | |
1283 | } | |
1284 | } | |
1285 | ||
cba13f93 | 1286 | if (node->node.first.getBits() > key.getBits()) { |
4bb19027 SB |
1287 | // key is a super-network of the matching node; split the branch and |
1288 | // insert a node for the key above the matching node. | |
1289 | node = node->split(key, key.getBits()); | |
136b2c6b | 1290 | } |
44845aab | 1291 | |
f67ce892 | 1292 | if (node->left) { |
9edc8e2b | 1293 | is_left = false; |
f67ce892 | 1294 | } |
9edc8e2b | 1295 | |
cba13f93 | 1296 | node_type& value = node->node; |
956c6dc4 | 1297 | |
956c6dc4 | 1298 | if (!node->assigned) { |
dccd4976 SB |
1299 | // only increment size if not assigned before |
1300 | d_size++; | |
9edc8e2b | 1301 | // update the pointer to the left-most tree node |
f67ce892 | 1302 | if (is_left) { |
9edc8e2b | 1303 | d_left = node; |
f67ce892 | 1304 | } |
956c6dc4 | 1305 | node->assigned = true; |
07203482 OM |
1306 | } |
1307 | else { | |
9edc8e2b SB |
1308 | // tree node exists for this value |
1309 | if (is_left && d_left != node) { | |
1310 | throw std::logic_error( | |
1311 | "NetmaskTree::insert(): lost track of left-most node in tree"); | |
1312 | } | |
44845aab | 1313 | } |
136b2c6b | 1314 | |
cba13f93 | 1315 | return value; |
44845aab AT |
1316 | } |
1317 | ||
2dfbbc41 | 1318 | //<! Creates or updates value |
07203482 OM |
1319 | void insert_or_assign(const key_type& mask, const value_type& value) |
1320 | { | |
44845aab AT |
1321 | insert(mask).second = value; |
1322 | } | |
1323 | ||
07203482 OM |
1324 | void insert_or_assign(const string& mask, const value_type& value) |
1325 | { | |
e6419866 | 1326 | insert(key_type(mask)).second = value; |
44845aab AT |
1327 | } |
1328 | ||
41d0adb7 | 1329 | //<! check if given key is present in TreeMap |
f67ce892 | 1330 | [[nodiscard]] bool has_key(const key_type& key) const |
07203482 OM |
1331 | { |
1332 | const node_type* ptr = lookup(key); | |
41d0adb7 AT |
1333 | return ptr && ptr->first == key; |
1334 | } | |
1335 | ||
2dfbbc41 | 1336 | //<! Returns "best match" for key_type, which might not be value |
07203482 OM |
1337 | [[nodiscard]] node_type* lookup(const key_type& value) const |
1338 | { | |
c173228a | 1339 | uint8_t max_bits = value.getBits(); |
5d2c20f7 | 1340 | return lookupImpl(value, max_bits); |
44845aab AT |
1341 | } |
1342 | ||
2dfbbc41 | 1343 | //<! Perform best match lookup for value, using at most max_bits |
07203482 OM |
1344 | [[nodiscard]] node_type* lookup(const ComboAddress& value, int max_bits = 128) const |
1345 | { | |
4bb19027 | 1346 | uint8_t addr_bits = value.getBits(); |
5d2c20f7 | 1347 | if (max_bits < 0 || max_bits > addr_bits) { |
4bb19027 | 1348 | max_bits = addr_bits; |
44845aab AT |
1349 | } |
1350 | ||
5d2c20f7 | 1351 | return lookupImpl(key_type(value, max_bits), max_bits); |
44845aab AT |
1352 | } |
1353 | ||
3d22a7ff | 1354 | //<! Removes key from TreeMap. |
07203482 OM |
1355 | void erase(const key_type& key) |
1356 | { | |
1357 | TreeNode* node = nullptr; | |
136b2c6b | 1358 | |
f67ce892 | 1359 | if (key.isIPv4()) { |
136b2c6b | 1360 | node = d_root->left.get(); |
f67ce892 OM |
1361 | } |
1362 | else if (key.isIPv6()) { | |
136b2c6b | 1363 | node = d_root->right.get(); |
f67ce892 OM |
1364 | } |
1365 | else { | |
136b2c6b | 1366 | throw NetmaskException("invalid address family"); |
f67ce892 | 1367 | } |
44845aab | 1368 | // no tree, no value |
f67ce892 | 1369 | if (node == nullptr) { |
07203482 | 1370 | return; |
f67ce892 | 1371 | } |
136b2c6b | 1372 | int bits = 0; |
07203482 OM |
1373 | for (; node && bits < key.getBits(); bits++) { |
1374 | bool vall = key.getBit(-1 - bits); | |
4bb19027 SB |
1375 | if (bits >= node->d_bits) { |
1376 | // the end of the current node is reached; continue with the next | |
1377 | if (vall) { | |
1378 | node = node->right.get(); | |
07203482 OM |
1379 | } |
1380 | else { | |
4bb19027 SB |
1381 | node = node->left.get(); |
1382 | } | |
1383 | continue; | |
1384 | } | |
cba13f93 | 1385 | if (bits >= node->node.first.getBits()) { |
4bb19027 | 1386 | // the matching branch ends here |
f67ce892 | 1387 | if (key.getBits() != node->node.first.getBits()) { |
4bb19027 | 1388 | node = nullptr; |
f67ce892 | 1389 | } |
4bb19027 SB |
1390 | break; |
1391 | } | |
07203482 | 1392 | bool valr = node->node.first.getBit(-1 - bits); |
4bb19027 SB |
1393 | if (vall != valr) { |
1394 | // the branch matches just upto this point, yet continues in a different | |
1395 | // direction | |
1396 | node = nullptr; | |
1397 | break; | |
44845aab | 1398 | } |
136b2c6b SB |
1399 | } |
1400 | if (node) { | |
dccd4976 SB |
1401 | if (d_size == 0) { |
1402 | throw std::logic_error( | |
1403 | "NetmaskTree::erase(): size of tree is zero before erase"); | |
1404 | } | |
1405 | d_size--; | |
956c6dc4 | 1406 | node->assigned = false; |
cba13f93 | 1407 | node->node.second = value_type(); |
9edc8e2b | 1408 | |
f67ce892 | 1409 | if (node == d_left) { |
9edc8e2b | 1410 | d_left = d_left->traverse_lnr_assigned(); |
f67ce892 | 1411 | } |
9772e56d | 1412 | cleanup_tree(node); |
44845aab AT |
1413 | } |
1414 | } | |
1415 | ||
07203482 OM |
1416 | void erase(const string& key) |
1417 | { | |
44845aab AT |
1418 | erase(key_type(key)); |
1419 | } | |
1420 | ||
1421 | //<! checks whether the container is empty. | |
07203482 OM |
1422 | [[nodiscard]] bool empty() const |
1423 | { | |
dccd4976 | 1424 | return (d_size == 0); |
44845aab AT |
1425 | } |
1426 | ||
1427 | //<! returns the number of elements | |
f67ce892 | 1428 | [[nodiscard]] size_type size() const |
07203482 | 1429 | { |
dccd4976 | 1430 | return d_size; |
44845aab AT |
1431 | } |
1432 | ||
1433 | //<! See if given ComboAddress matches any prefix | |
f67ce892 | 1434 | [[nodiscard]] bool match(const ComboAddress& value) const |
07203482 | 1435 | { |
44845aab AT |
1436 | return (lookup(value) != nullptr); |
1437 | } | |
1438 | ||
f67ce892 | 1439 | [[nodiscard]] bool match(const std::string& value) const |
07203482 | 1440 | { |
44845aab AT |
1441 | return match(ComboAddress(value)); |
1442 | } | |
1443 | ||
1444 | //<! Clean out the tree | |
07203482 OM |
1445 | void clear() |
1446 | { | |
747fdbdd | 1447 | d_root = make_unique<TreeNode>(); |
9edc8e2b | 1448 | d_left = nullptr; |
dccd4976 | 1449 | d_size = 0; |
44845aab AT |
1450 | } |
1451 | ||
3d22a7ff | 1452 | //<! swaps the contents with another NetmaskTree |
71633799 RP |
1453 | void swap(NetmaskTree& rhs) noexcept |
1454 | { | |
e4b291fe | 1455 | std::swap(d_root, rhs.d_root); |
9edc8e2b | 1456 | std::swap(d_left, rhs.d_left); |
dccd4976 | 1457 | std::swap(d_size, rhs.d_size); |
44845aab AT |
1458 | } |
1459 | ||
1460 | private: | |
07203482 OM |
1461 | [[nodiscard]] node_type* lookupImpl(const key_type& value, uint8_t max_bits) const |
1462 | { | |
1463 | TreeNode* node = nullptr; | |
5d2c20f7 | 1464 | |
f67ce892 | 1465 | if (value.isIPv4()) { |
5d2c20f7 | 1466 | node = d_root->left.get(); |
f67ce892 OM |
1467 | } |
1468 | else if (value.isIPv6()) { | |
5d2c20f7 | 1469 | node = d_root->right.get(); |
f67ce892 OM |
1470 | } |
1471 | else { | |
5d2c20f7 | 1472 | throw NetmaskException("invalid address family"); |
f67ce892 OM |
1473 | } |
1474 | if (node == nullptr) { | |
07203482 | 1475 | return nullptr; |
f67ce892 | 1476 | } |
5d2c20f7 | 1477 | |
07203482 | 1478 | node_type* ret = nullptr; |
5d2c20f7 RG |
1479 | |
1480 | int bits = 0; | |
07203482 OM |
1481 | for (; bits < max_bits; bits++) { |
1482 | bool vall = value.getBit(-1 - bits); | |
5d2c20f7 RG |
1483 | if (bits >= node->d_bits) { |
1484 | // the end of the current node is reached; continue with the next | |
1485 | // (we keep track of last assigned node) | |
f67ce892 | 1486 | if (node->assigned && bits == node->node.first.getBits()) { |
5d2c20f7 | 1487 | ret = &node->node; |
f67ce892 | 1488 | } |
5d2c20f7 | 1489 | if (vall) { |
f67ce892 | 1490 | if (!node->right) { |
5d2c20f7 | 1491 | break; |
f67ce892 | 1492 | } |
5d2c20f7 | 1493 | node = node->right.get(); |
07203482 OM |
1494 | } |
1495 | else { | |
f67ce892 | 1496 | if (!node->left) { |
5d2c20f7 | 1497 | break; |
f67ce892 | 1498 | } |
5d2c20f7 RG |
1499 | node = node->left.get(); |
1500 | } | |
1501 | continue; | |
1502 | } | |
1503 | if (bits >= node->node.first.getBits()) { | |
1504 | // the matching branch ends here | |
1505 | break; | |
1506 | } | |
07203482 | 1507 | bool valr = node->node.first.getBit(-1 - bits); |
5d2c20f7 RG |
1508 | if (vall != valr) { |
1509 | // the branch matches just upto this point, yet continues in a different | |
1510 | // direction | |
1511 | break; | |
1512 | } | |
1513 | } | |
1514 | // needed if we did not find one in loop | |
f67ce892 | 1515 | if (node->assigned && bits == node->node.first.getBits()) { |
5d2c20f7 | 1516 | ret = &node->node; |
f67ce892 | 1517 | } |
5d2c20f7 RG |
1518 | // this can be nullptr. |
1519 | return ret; | |
1520 | } | |
1521 | ||
e4b291fe | 1522 | unique_ptr<TreeNode> d_root; //<! Root of our tree |
07203482 | 1523 | TreeNode* d_left; |
f67ce892 | 1524 | size_type d_size{0}; |
44845aab AT |
1525 | }; |
1526 | ||
152f3626 | 1527 | /** This class represents a group of supplemental Netmask classes. An IP address matches |
9d5607b0 | 1528 | if it is matched by one or more of the Netmask objects within. |
12c86877 BH |
1529 | */ |
1530 | class NetmaskGroup | |
1531 | { | |
1532 | public: | |
abb11ca4 | 1533 | NetmaskGroup() noexcept = default; |
11f4719b | 1534 | |
12c86877 | 1535 | //! If this IP address is matched by any of the classes within |
60af67b8 | 1536 | |
f67ce892 | 1537 | bool match(const ComboAddress* address) const |
12c86877 | 1538 | { |
f67ce892 OM |
1539 | const auto& ret = tree.lookup(*address); |
1540 | if (ret != nullptr) { | |
07203482 | 1541 | return ret->second; |
f67ce892 | 1542 | } |
ee15a1e1 | 1543 | return false; |
12c86877 | 1544 | } |
60af67b8 | 1545 | |
f67ce892 | 1546 | [[nodiscard]] bool match(const ComboAddress& address) const |
60af67b8 | 1547 | { |
f67ce892 | 1548 | return match(&address); |
60af67b8 | 1549 | } |
1550 | ||
f67ce892 | 1551 | bool lookup(const ComboAddress* address, Netmask* nmp) const |
11f4719b | 1552 | { |
f67ce892 OM |
1553 | const auto& ret = tree.lookup(*address); |
1554 | if (ret != nullptr) { | |
1555 | if (nmp != nullptr) { | |
11f4719b | 1556 | *nmp = ret->first; |
f67ce892 | 1557 | } |
11f4719b RG |
1558 | return ret->second; |
1559 | } | |
1560 | return false; | |
1561 | } | |
1562 | ||
f67ce892 | 1563 | bool lookup(const ComboAddress& address, Netmask* nmp) const |
11f4719b | 1564 | { |
f67ce892 | 1565 | return lookup(&address, nmp); |
11f4719b RG |
1566 | } |
1567 | ||
376effcf | 1568 | //! Add this string to the list of possible matches |
f67ce892 | 1569 | void addMask(const string& address, bool positive = true) |
12c86877 | 1570 | { |
f67ce892 OM |
1571 | if (!address.empty() && address[0] == '!') { |
1572 | addMask(Netmask(address.substr(1)), false); | |
07203482 OM |
1573 | } |
1574 | else { | |
f67ce892 | 1575 | addMask(Netmask(address), positive); |
ee15a1e1 | 1576 | } |
12c86877 | 1577 | } |
68b011bd | 1578 | |
376effcf | 1579 | //! Add this Netmask to the list of possible matches |
f67ce892 | 1580 | void addMask(const Netmask& netmask, bool positive = true) |
376effcf | 1581 | { |
f67ce892 | 1582 | tree.insert(netmask).second = positive; |
376effcf | 1583 | } |
1584 | ||
5a2f3287 RG |
1585 | void addMasks(const NetmaskGroup& group, boost::optional<bool> positive) |
1586 | { | |
1587 | for (const auto& entry : group.tree) { | |
1588 | addMask(entry.first, positive ? *positive : entry.second); | |
1589 | } | |
1590 | } | |
1591 | ||
11f4719b | 1592 | //! Delete this Netmask from the list of possible matches |
f67ce892 | 1593 | void deleteMask(const Netmask& netmask) |
11f4719b | 1594 | { |
f67ce892 | 1595 | tree.erase(netmask); |
11f4719b RG |
1596 | } |
1597 | ||
59a8b338 RG |
1598 | void deleteMasks(const NetmaskGroup& group) |
1599 | { | |
1600 | for (const auto& entry : group.tree) { | |
1601 | deleteMask(entry.first); | |
1602 | } | |
1603 | } | |
1604 | ||
f67ce892 | 1605 | void deleteMask(const std::string& address) |
11f4719b | 1606 | { |
f67ce892 OM |
1607 | if (!address.empty()) { |
1608 | deleteMask(Netmask(address)); | |
1609 | } | |
11f4719b RG |
1610 | } |
1611 | ||
68b011bd KM |
1612 | void clear() |
1613 | { | |
5ac553e1 | 1614 | tree.clear(); |
68b011bd KM |
1615 | } |
1616 | ||
f67ce892 | 1617 | [[nodiscard]] bool empty() const |
12c86877 | 1618 | { |
5ac553e1 | 1619 | return tree.empty(); |
12c86877 BH |
1620 | } |
1621 | ||
f67ce892 | 1622 | [[nodiscard]] size_t size() const |
2c95fc65 | 1623 | { |
5ac553e1 | 1624 | return tree.size(); |
2c95fc65 BH |
1625 | } |
1626 | ||
f67ce892 | 1627 | [[nodiscard]] string toString() const |
2c95fc65 BH |
1628 | { |
1629 | ostringstream str; | |
07203482 | 1630 | for (auto iter = tree.begin(); iter != tree.end(); ++iter) { |
f67ce892 | 1631 | if (iter != tree.begin()) { |
07203482 | 1632 | str << ", "; |
f67ce892 OM |
1633 | } |
1634 | if (!(iter->second)) { | |
07203482 | 1635 | str << "!"; |
f67ce892 | 1636 | } |
07203482 | 1637 | str << iter->first.toString(); |
2c95fc65 BH |
1638 | } |
1639 | return str.str(); | |
1640 | } | |
1641 | ||
f67ce892 | 1642 | [[nodiscard]] std::vector<std::string> toStringVector() const |
41942bb3 | 1643 | { |
25b3e633 RG |
1644 | std::vector<std::string> out; |
1645 | out.reserve(tree.size()); | |
1646 | for (const auto& entry : tree) { | |
1647 | out.push_back((entry.second ? "" : "!") + entry.first.toString()); | |
ee15a1e1 | 1648 | } |
25b3e633 | 1649 | return out; |
41942bb3 CH |
1650 | } |
1651 | ||
07203482 | 1652 | void toMasks(const string& ips) |
68b011bd KM |
1653 | { |
1654 | vector<string> parts; | |
1655 | stringtok(parts, ips, ", \t"); | |
1656 | ||
f67ce892 OM |
1657 | for (const auto& part : parts) { |
1658 | addMask(part); | |
1659 | } | |
68b011bd KM |
1660 | } |
1661 | ||
12c86877 | 1662 | private: |
5ac553e1 | 1663 | NetmaskTree<bool> tree; |
12c86877 BH |
1664 | }; |
1665 | ||
60c8afa8 | 1666 | struct SComboAddress |
1667 | { | |
07203482 OM |
1668 | SComboAddress(const ComboAddress& orig) : |
1669 | ca(orig) {} | |
60c8afa8 | 1670 | ComboAddress ca; |
1671 | bool operator<(const SComboAddress& rhs) const | |
1672 | { | |
1673 | return ComboAddress::addressOnlyLessThan()(ca, rhs.ca); | |
1674 | } | |
f67ce892 | 1675 | operator const ComboAddress&() const |
60c8afa8 | 1676 | { |
1677 | return ca; | |
1678 | } | |
1679 | }; | |
1680 | ||
73ba5999 CHB |
1681 | class NetworkError : public runtime_error |
1682 | { | |
1683 | public: | |
07203482 OM |
1684 | NetworkError(const string& why = "Network Error") : |
1685 | runtime_error(why.c_str()) | |
73ba5999 | 1686 | {} |
07203482 OM |
1687 | NetworkError(const char* why = "Network Error") : |
1688 | runtime_error(why) | |
73ba5999 CHB |
1689 | {} |
1690 | }; | |
60c8afa8 | 1691 | |
c173228a RG |
1692 | class AddressAndPortRange |
1693 | { | |
1694 | public: | |
07203482 OM |
1695 | AddressAndPortRange() : |
1696 | d_addrMask(0), d_portMask(0) | |
c173228a RG |
1697 | { |
1698 | d_addr.sin4.sin_family = 0; // disable this doing anything useful | |
1699 | d_addr.sin4.sin_port = 0; // this guarantees d_network compares identical | |
1700 | } | |
1701 | ||
f67ce892 OM |
1702 | AddressAndPortRange(ComboAddress address, uint8_t addrMask, uint8_t portMask = 0) : |
1703 | d_addr(address), d_addrMask(addrMask), d_portMask(portMask) | |
c173228a RG |
1704 | { |
1705 | if (!d_addr.isIPv4()) { | |
1706 | d_portMask = 0; | |
1707 | } | |
1708 | ||
1709 | uint16_t port = d_addr.getPort(); | |
1710 | if (d_portMask < 16) { | |
1711 | uint16_t mask = ~(0xFFFF >> d_portMask); | |
1712 | port = port & mask; | |
1713 | } | |
1714 | ||
1715 | if (d_addrMask < d_addr.getBits()) { | |
1716 | if (d_portMask > 0) { | |
1717 | throw std::runtime_error("Trying to create a AddressAndPortRange with a reduced address mask (" + std::to_string(d_addrMask) + ") and a port range (" + std::to_string(d_portMask) + ")"); | |
1718 | } | |
1719 | d_addr = Netmask(d_addr, d_addrMask).getMaskedNetwork(); | |
1720 | } | |
1721 | d_addr.setPort(port); | |
1722 | } | |
1723 | ||
f67ce892 | 1724 | [[nodiscard]] uint8_t getFullBits() const |
c173228a RG |
1725 | { |
1726 | return d_addr.getBits() + 16; | |
1727 | } | |
1728 | ||
f67ce892 | 1729 | [[nodiscard]] uint8_t getBits() const |
c173228a RG |
1730 | { |
1731 | if (d_addrMask < d_addr.getBits()) { | |
1732 | return d_addrMask; | |
1733 | } | |
1734 | ||
1735 | return d_addr.getBits() + d_portMask; | |
1736 | } | |
1737 | ||
1738 | /** Get the value of the bit at the provided bit index. When the index >= 0, | |
1739 | the index is relative to the LSB starting at index zero. When the index < 0, | |
1740 | the index is relative to the MSB starting at index -1 and counting down. | |
1741 | */ | |
f67ce892 | 1742 | [[nodiscard]] bool getBit(int index) const |
c173228a RG |
1743 | { |
1744 | if (index >= getFullBits()) { | |
1745 | return false; | |
1746 | } | |
1747 | if (index < 0) { | |
1748 | index = getFullBits() + index; | |
1749 | } | |
1750 | ||
1751 | if (index < 16) { | |
1752 | /* we are into the port bits */ | |
1753 | uint16_t port = d_addr.getPort(); | |
07203482 | 1754 | return ((port & (1U << index)) != 0x0000); |
c173228a RG |
1755 | } |
1756 | ||
1757 | index -= 16; | |
1758 | ||
1759 | return d_addr.getBit(index); | |
1760 | } | |
1761 | ||
f67ce892 | 1762 | [[nodiscard]] bool isIPv4() const |
c173228a RG |
1763 | { |
1764 | return d_addr.isIPv4(); | |
1765 | } | |
1766 | ||
f67ce892 | 1767 | [[nodiscard]] bool isIPv6() const |
c173228a RG |
1768 | { |
1769 | return d_addr.isIPv6(); | |
1770 | } | |
1771 | ||
f67ce892 | 1772 | [[nodiscard]] AddressAndPortRange getNormalized() const |
c173228a | 1773 | { |
f67ce892 | 1774 | return {d_addr, d_addrMask, d_portMask}; |
c173228a RG |
1775 | } |
1776 | ||
f67ce892 | 1777 | [[nodiscard]] AddressAndPortRange getSuper(uint8_t bits) const |
c173228a RG |
1778 | { |
1779 | if (bits <= d_addrMask) { | |
f67ce892 | 1780 | return {d_addr, bits, 0}; |
c173228a RG |
1781 | } |
1782 | if (bits <= d_addrMask + d_portMask) { | |
f67ce892 | 1783 | return {d_addr, d_addrMask, static_cast<uint8_t>(d_portMask - (bits - d_addrMask))}; |
c173228a RG |
1784 | } |
1785 | ||
f67ce892 | 1786 | return {d_addr, d_addrMask, d_portMask}; |
c173228a RG |
1787 | } |
1788 | ||
f67ce892 | 1789 | [[nodiscard]] const ComboAddress& getNetwork() const |
c173228a RG |
1790 | { |
1791 | return d_addr; | |
1792 | } | |
1793 | ||
f67ce892 | 1794 | [[nodiscard]] string toString() const |
c173228a RG |
1795 | { |
1796 | if (d_addrMask < d_addr.getBits() || d_portMask == 0) { | |
1797 | return d_addr.toStringNoInterface() + "/" + std::to_string(d_addrMask); | |
1798 | } | |
1799 | return d_addr.toStringNoInterface() + ":" + std::to_string(d_addr.getPort()) + "/" + std::to_string(d_portMask); | |
1800 | } | |
1801 | ||
f67ce892 | 1802 | [[nodiscard]] bool empty() const |
c173228a RG |
1803 | { |
1804 | return d_addr.sin4.sin_family == 0; | |
1805 | } | |
1806 | ||
1807 | bool operator==(const AddressAndPortRange& rhs) const | |
1808 | { | |
905dae56 | 1809 | return std::tie(d_addr, d_addrMask, d_portMask) == std::tie(rhs.d_addr, rhs.d_addrMask, rhs.d_portMask); |
c173228a RG |
1810 | } |
1811 | ||
1812 | bool operator<(const AddressAndPortRange& rhs) const | |
1813 | { | |
1814 | if (empty() && !rhs.empty()) { | |
1815 | return false; | |
1816 | } | |
1817 | ||
1818 | if (!empty() && rhs.empty()) { | |
1819 | return true; | |
1820 | } | |
1821 | ||
1822 | if (d_addrMask > rhs.d_addrMask) { | |
1823 | return true; | |
1824 | } | |
1825 | ||
1826 | if (d_addrMask < rhs.d_addrMask) { | |
1827 | return false; | |
1828 | } | |
1829 | ||
1830 | if (d_addr < rhs.d_addr) { | |
1831 | return true; | |
1832 | } | |
1833 | ||
1834 | if (d_addr > rhs.d_addr) { | |
1835 | return false; | |
1836 | } | |
1837 | ||
1838 | if (d_portMask > rhs.d_portMask) { | |
1839 | return true; | |
1840 | } | |
1841 | ||
1842 | if (d_portMask < rhs.d_portMask) { | |
1843 | return false; | |
1844 | } | |
1845 | ||
1846 | return d_addr.getPort() < rhs.d_addr.getPort(); | |
1847 | } | |
1848 | ||
1849 | bool operator>(const AddressAndPortRange& rhs) const | |
1850 | { | |
1851 | return rhs.operator<(*this); | |
1852 | } | |
1853 | ||
1854 | struct hash | |
1855 | { | |
1856 | uint32_t operator()(const AddressAndPortRange& apr) const | |
1857 | { | |
1858 | ComboAddress::addressOnlyHash hashOp; | |
1859 | uint16_t port = apr.d_addr.getPort(); | |
1860 | /* it's fine to hash the whole address and port because the non-relevant parts have | |
1861 | been masked to 0 */ | |
f67ce892 | 1862 | return burtle(reinterpret_cast<const unsigned char*>(&port), sizeof(port), hashOp(apr.d_addr)); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast) |
c173228a RG |
1863 | } |
1864 | }; | |
1865 | ||
1866 | private: | |
1867 | ComboAddress d_addr; | |
1868 | uint8_t d_addrMask; | |
1869 | /* only used for v4 addresses */ | |
1870 | uint8_t d_portMask; | |
1871 | }; | |
1872 | ||
002c970a | 1873 | int SSocket(int family, int type, int flags); |
1874 | int SConnect(int sockfd, const ComboAddress& remote); | |
51959320 RG |
1875 | /* tries to connect to remote for a maximum of timeout seconds. |
1876 | sockfd should be set to non-blocking beforehand. | |
1877 | returns 0 on success (the socket is writable), throw a | |
1878 | runtime_error otherwise */ | |
50111728 | 1879 | int SConnectWithTimeout(int sockfd, const ComboAddress& remote, const struct timeval& timeout); |
002c970a | 1880 | int SBind(int sockfd, const ComboAddress& local); |
1881 | int SAccept(int sockfd, ComboAddress& remote); | |
1882 | int SListen(int sockfd, int limit); | |
1883 | int SSetsockopt(int sockfd, int level, int opname, int value); | |
db63b4b6 | 1884 | void setSocketIgnorePMTU(int sockfd, int family); |
3198b2c3 | 1885 | void setSocketForcePMTU(int sockfd, int family); |
665821e1 | 1886 | bool setReusePort(int sockfd); |
002c970a | 1887 | |
3e3f0358 | 1888 | #if defined(IP_PKTINFO) |
07203482 | 1889 | #define GEN_IP_PKTINFO IP_PKTINFO |
3e3f0358 | 1890 | #elif defined(IP_RECVDSTADDR) |
07203482 | 1891 | #define GEN_IP_PKTINFO IP_RECVDSTADDR |
3e3f0358 | 1892 | #endif |
4d39d7f3 | 1893 | |
3e3f0358 | 1894 | bool IsAnyAddress(const ComboAddress& addr); |
2b3eefc3 | 1895 | bool HarvestDestinationAddress(const struct msghdr* msgh, ComboAddress* destination); |
f67ce892 | 1896 | bool HarvestTimestamp(struct msghdr* msgh, struct timeval* timeval); |
7bec330a | 1897 | void fillMSGHdr(struct msghdr* msgh, struct iovec* iov, cmsgbuf_aligned* cbuf, size_t cbufsize, char* data, size_t datalen, ComboAddress* addr); |
5e4bc87a | 1898 | int sendOnNBSocket(int fileDesc, const struct msghdr* msgh); |
77c1af63 | 1899 | size_t sendMsgWithOptions(int socketDesc, const void* buffer, size_t len, const ComboAddress* dest, const ComboAddress* local, unsigned int localItf, int flags); |
6714b6ac | 1900 | |
840ed663 RG |
1901 | /* requires a non-blocking, connected TCP socket */ |
1902 | bool isTCPSocketUsable(int sock); | |
f9f9592e AT |
1903 | |
1904 | extern template class NetmaskTree<bool>; | |
7234d9fc | 1905 | ComboAddress parseIPAndPort(const std::string& input, uint16_t port); |
f402f388 | 1906 | |
6ec09d51 RG |
1907 | std::set<std::string> getListOfNetworkInterfaces(); |
1908 | std::vector<ComboAddress> getListOfAddressesOfNetworkInterface(const std::string& itf); | |
6f0bf6e8 | 1909 | std::vector<Netmask> getListOfRangesOfNetworkInterface(const std::string& itf); |
6ec09d51 | 1910 | |
f402f388 RG |
1911 | /* These functions throw if the value was already set to a higher value, |
1912 | or on error */ | |
f67ce892 OM |
1913 | void setSocketBuffer(int fileDesc, int optname, uint32_t size); |
1914 | void setSocketReceiveBuffer(int fileDesc, uint32_t size); | |
1915 | void setSocketSendBuffer(int fileDesc, uint32_t size); | |
37088b76 CHB |
1916 | uint32_t raiseSocketReceiveBufferToMax(int socket); |
1917 | uint32_t raiseSocketSendBufferToMax(int socket); |