]>
Commit | Line | Data |
---|---|---|
3b5f4af2 MT |
1 | /* |
2 | libloc - A library to determine the location of someone on the Internet | |
3 | ||
4 | Copyright (C) 2017 IPFire Development Team <info@ipfire.org> | |
5 | ||
6 | This library is free software; you can redistribute it and/or | |
7 | modify it under the terms of the GNU Lesser General Public | |
8 | License as published by the Free Software Foundation; either | |
9 | version 2.1 of the License, or (at your option) any later version. | |
10 | ||
11 | This library is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | Lesser General Public License for more details. | |
15 | */ | |
16 | ||
17 | #include <arpa/inet.h> | |
18 | #include <assert.h> | |
19 | #include <errno.h> | |
71ff3e69 | 20 | #include <stdio.h> |
3b5f4af2 MT |
21 | #include <stdlib.h> |
22 | #include <string.h> | |
23 | ||
42f3ccd7 MT |
24 | #ifdef HAVE_ENDIAN_H |
25 | # include <endian.h> | |
26 | #endif | |
27 | ||
c12a1385 | 28 | #include <libloc/libloc.h> |
0b1fef38 | 29 | #include <libloc/address.h> |
c12a1385 MT |
30 | #include <libloc/compat.h> |
31 | #include <libloc/country.h> | |
32 | #include <libloc/network.h> | |
33 | #include <libloc/network-list.h> | |
34 | #include <libloc/private.h> | |
3b5f4af2 MT |
35 | |
36 | struct loc_network { | |
37 | struct loc_ctx* ctx; | |
38 | int refcount; | |
39 | ||
c3068be1 | 40 | int family; |
ce4f5752 | 41 | struct in6_addr first_address; |
b43edb61 | 42 | struct in6_addr last_address; |
3b5f4af2 MT |
43 | unsigned int prefix; |
44 | ||
45 | char country_code[3]; | |
71ff3e69 | 46 | uint32_t asn; |
a293f829 | 47 | enum loc_network_flags flags; |
3b5f4af2 MT |
48 | }; |
49 | ||
6183c0f2 MT |
50 | static int valid_prefix(struct in6_addr* address, unsigned int prefix) { |
51 | // The prefix cannot be larger than 128 bits | |
52 | if (prefix > 128) | |
53 | return 1; | |
54 | ||
aa37232a MT |
55 | // For IPv4-mapped addresses the prefix has to be 96 or lager |
56 | if (IN6_IS_ADDR_V4MAPPED(address) && prefix <= 96) | |
57 | return 1; | |
58 | ||
6183c0f2 MT |
59 | return 0; |
60 | } | |
61 | ||
3b5f4af2 | 62 | LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network, |
10778041 | 63 | struct in6_addr* address, unsigned int prefix) { |
6183c0f2 | 64 | // Validate the prefix |
10778041 | 65 | if (valid_prefix(address, prefix) != 0) { |
5559e086 MT |
66 | ERROR(ctx, "Invalid prefix: %u\n", prefix); |
67 | errno = EINVAL; | |
68 | return 1; | |
6183c0f2 MT |
69 | } |
70 | ||
3b5f4af2 | 71 | struct loc_network* n = calloc(1, sizeof(*n)); |
5559e086 MT |
72 | if (!n) { |
73 | errno = ENOMEM; | |
74 | return 1; | |
75 | } | |
3b5f4af2 MT |
76 | |
77 | n->ctx = loc_ref(ctx); | |
78 | n->refcount = 1; | |
79 | ||
b43edb61 | 80 | // Store the prefix |
3b5f4af2 MT |
81 | n->prefix = prefix; |
82 | ||
b43edb61 | 83 | // Convert the prefix into a bitmask |
30f0f0ed | 84 | struct in6_addr bitmask = loc_prefix_to_bitmask(n->prefix); |
b43edb61 MT |
85 | |
86 | // Store the first and last address in the network | |
30f0f0ed MT |
87 | n->first_address = loc_address_and(address, &bitmask); |
88 | n->last_address = loc_address_or(&n->first_address, &bitmask); | |
b43edb61 | 89 | |
c3068be1 | 90 | // Set family |
71877f5f | 91 | n->family = loc_address_family(&n->first_address); |
c3068be1 | 92 | |
3b5f4af2 MT |
93 | DEBUG(n->ctx, "Network allocated at %p\n", n); |
94 | *network = n; | |
95 | return 0; | |
96 | } | |
97 | ||
98 | LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network, | |
99 | const char* address_string) { | |
ce4f5752 | 100 | struct in6_addr first_address; |
3b5f4af2 | 101 | char* prefix_string; |
26ab419b | 102 | unsigned int prefix = 128; |
13ad6e69 MT |
103 | int r = -EINVAL; |
104 | ||
105 | DEBUG(ctx, "Attempting to parse network %s\n", address_string); | |
3b5f4af2 MT |
106 | |
107 | // Make a copy of the string to work on it | |
108 | char* buffer = strdup(address_string); | |
109 | address_string = prefix_string = buffer; | |
110 | ||
111 | // Split address and prefix | |
112 | address_string = strsep(&prefix_string, "/"); | |
113 | ||
13ad6e69 MT |
114 | DEBUG(ctx, " Split into address = %s, prefix = %s\n", address_string, prefix_string); |
115 | ||
13ad6e69 MT |
116 | // Parse the address |
117 | r = loc_parse_address(ctx, address_string, &first_address); | |
118 | if (r) { | |
119 | DEBUG(ctx, "The address could not be parsed\n"); | |
120 | goto FAIL; | |
b61f14fc | 121 | } |
3b5f4af2 | 122 | |
26ab419b MT |
123 | // If a prefix was given, we will try to parse it |
124 | if (prefix_string) { | |
125 | // Convert prefix to integer | |
126 | prefix = strtol(prefix_string, NULL, 10); | |
127 | ||
128 | if (!prefix) { | |
129 | DEBUG(ctx, "The prefix was not parsable: %s\n", prefix_string); | |
130 | goto FAIL; | |
131 | } | |
132 | ||
133 | // Map the prefix to IPv6 if needed | |
134 | if (IN6_IS_ADDR_V4MAPPED(&first_address)) | |
135 | prefix += 96; | |
136 | } | |
13ad6e69 MT |
137 | |
138 | FAIL: | |
3b5f4af2 MT |
139 | // Free temporary buffer |
140 | free(buffer); | |
141 | ||
13ad6e69 MT |
142 | // Exit if the parsing was unsuccessful |
143 | if (r) | |
144 | return r; | |
145 | ||
13ad6e69 MT |
146 | // Create a new network |
147 | return loc_network_new(ctx, network, &first_address, prefix); | |
3b5f4af2 MT |
148 | } |
149 | ||
150 | LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) { | |
151 | network->refcount++; | |
152 | ||
153 | return network; | |
154 | } | |
155 | ||
156 | static void loc_network_free(struct loc_network* network) { | |
157 | DEBUG(network->ctx, "Releasing network at %p\n", network); | |
158 | ||
3b5f4af2 MT |
159 | loc_unref(network->ctx); |
160 | free(network); | |
161 | } | |
162 | ||
163 | LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) { | |
2a30e4de MT |
164 | if (!network) |
165 | return NULL; | |
166 | ||
3b5f4af2 MT |
167 | if (--network->refcount > 0) |
168 | return network; | |
169 | ||
170 | loc_network_free(network); | |
171 | return NULL; | |
172 | } | |
173 | ||
8fb874e9 MT |
174 | static int format_ipv6_address(const struct in6_addr* address, char* string, size_t length) { |
175 | const char* ret = inet_ntop(AF_INET6, address, string, length); | |
d3409788 MT |
176 | if (!ret) |
177 | return -1; | |
178 | ||
179 | return 0; | |
180 | } | |
181 | ||
8fb874e9 | 182 | static int format_ipv4_address(const struct in6_addr* address, char* string, size_t length) { |
d3409788 | 183 | struct in_addr ipv4_address; |
8fb874e9 | 184 | ipv4_address.s_addr = address->s6_addr32[3]; |
d3409788 MT |
185 | |
186 | const char* ret = inet_ntop(AF_INET, &ipv4_address, string, length); | |
187 | if (!ret) | |
188 | return -1; | |
189 | ||
190 | return 0; | |
191 | } | |
192 | ||
3b5f4af2 | 193 | LOC_EXPORT char* loc_network_str(struct loc_network* network) { |
d3409788 MT |
194 | int r; |
195 | const size_t length = INET6_ADDRSTRLEN + 4; | |
3b5f4af2 | 196 | |
d3409788 | 197 | char* string = malloc(length); |
3b5f4af2 MT |
198 | if (!string) |
199 | return NULL; | |
200 | ||
aa37232a MT |
201 | unsigned int prefix = network->prefix; |
202 | ||
c3068be1 | 203 | switch (network->family) { |
d3409788 | 204 | case AF_INET6: |
ce4f5752 | 205 | r = format_ipv6_address(&network->first_address, string, length); |
d3409788 | 206 | break; |
3b5f4af2 | 207 | |
d3409788 | 208 | case AF_INET: |
ce4f5752 | 209 | r = format_ipv4_address(&network->first_address, string, length); |
aa37232a | 210 | prefix -= 96; |
d3409788 MT |
211 | break; |
212 | ||
213 | default: | |
214 | r = -1; | |
215 | break; | |
216 | } | |
217 | ||
218 | if (r) { | |
219 | ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno)); | |
3b5f4af2 | 220 | free(string); |
d3409788 | 221 | |
3b5f4af2 MT |
222 | return NULL; |
223 | } | |
224 | ||
225 | // Append prefix | |
aa37232a | 226 | sprintf(string + strlen(string), "/%u", prefix); |
3b5f4af2 MT |
227 | |
228 | return string; | |
229 | } | |
230 | ||
44e5ef71 | 231 | LOC_EXPORT int loc_network_address_family(struct loc_network* network) { |
c3068be1 | 232 | return network->family; |
44e5ef71 MT |
233 | } |
234 | ||
7fe6a218 MT |
235 | LOC_EXPORT unsigned int loc_network_prefix(struct loc_network* network) { |
236 | switch (network->family) { | |
237 | case AF_INET6: | |
238 | return network->prefix; | |
239 | ||
240 | case AF_INET: | |
241 | return network->prefix - 96; | |
242 | } | |
243 | ||
244 | return 0; | |
245 | } | |
246 | ||
2b9338ea MT |
247 | static char* loc_network_format_address(struct loc_network* network, const struct in6_addr* address) { |
248 | const size_t length = INET6_ADDRSTRLEN; | |
249 | ||
250 | char* string = malloc(length); | |
251 | if (!string) | |
252 | return NULL; | |
253 | ||
254 | int r = 0; | |
255 | ||
c3068be1 | 256 | switch (network->family) { |
2b9338ea MT |
257 | case AF_INET6: |
258 | r = format_ipv6_address(address, string, length); | |
259 | break; | |
260 | ||
261 | case AF_INET: | |
262 | r = format_ipv4_address(address, string, length); | |
263 | break; | |
264 | ||
265 | default: | |
266 | r = -1; | |
267 | break; | |
268 | } | |
269 | ||
270 | if (r) { | |
271 | ERROR(network->ctx, "Could not format IP address to string: %s\n", strerror(errno)); | |
272 | free(string); | |
273 | ||
274 | return NULL; | |
275 | } | |
276 | ||
277 | return string; | |
278 | } | |
279 | ||
a1a00053 MT |
280 | LOC_EXPORT const struct in6_addr* loc_network_get_first_address(struct loc_network* network) { |
281 | return &network->first_address; | |
282 | } | |
283 | ||
2b9338ea MT |
284 | LOC_EXPORT char* loc_network_format_first_address(struct loc_network* network) { |
285 | return loc_network_format_address(network, &network->first_address); | |
286 | } | |
287 | ||
a1a00053 MT |
288 | LOC_EXPORT const struct in6_addr* loc_network_get_last_address(struct loc_network* network) { |
289 | return &network->last_address; | |
290 | } | |
291 | ||
2b9338ea MT |
292 | LOC_EXPORT char* loc_network_format_last_address(struct loc_network* network) { |
293 | return loc_network_format_address(network, &network->last_address); | |
294 | } | |
295 | ||
0258d3c9 | 296 | LOC_EXPORT int loc_network_matches_address(struct loc_network* network, const struct in6_addr* address) { |
f50adb09 | 297 | // Address must be larger than the start address |
9c1e2943 | 298 | if (loc_address_cmp(&network->first_address, address) > 0) |
fc692a58 | 299 | return 0; |
2a30e4de | 300 | |
2a30e4de | 301 | // Address must be smaller than the last address |
9c1e2943 | 302 | if (loc_address_cmp(&network->last_address, address) < 0) |
fc692a58 | 303 | return 0; |
2a30e4de MT |
304 | |
305 | // The address is inside this network | |
fc692a58 | 306 | return 1; |
2a30e4de MT |
307 | } |
308 | ||
3b5f4af2 MT |
309 | LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) { |
310 | return network->country_code; | |
311 | } | |
312 | ||
313 | LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) { | |
901ef882 MT |
314 | // Set empty country code |
315 | if (!country_code || !*country_code) { | |
316 | *network->country_code = '\0'; | |
317 | return 0; | |
318 | } | |
319 | ||
57146963 MT |
320 | // Check country code |
321 | if (!loc_country_code_is_valid(country_code)) | |
3b5f4af2 MT |
322 | return -EINVAL; |
323 | ||
a7a3d958 | 324 | loc_country_code_copy(network->country_code, country_code); |
3b5f4af2 MT |
325 | |
326 | return 0; | |
327 | } | |
328 | ||
0258d3c9 | 329 | LOC_EXPORT int loc_network_matches_country_code(struct loc_network* network, const char* country_code) { |
0b27a567 MT |
330 | // Search for any special flags |
331 | const int flag = loc_country_special_code_to_flag(country_code); | |
332 | ||
333 | // If we found a flag, we will return whether it is set or not | |
334 | if (flag) | |
335 | return loc_network_has_flag(network, flag); | |
336 | ||
57146963 MT |
337 | // Check country code |
338 | if (!loc_country_code_is_valid(country_code)) | |
e3f696c1 MT |
339 | return -EINVAL; |
340 | ||
0b27a567 | 341 | // Check for an exact match |
e3f696c1 MT |
342 | return (network->country_code[0] == country_code[0]) |
343 | && (network->country_code[1] == country_code[1]); | |
344 | } | |
345 | ||
71ff3e69 MT |
346 | LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) { |
347 | return network->asn; | |
348 | } | |
349 | ||
350 | LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) { | |
351 | network->asn = asn; | |
352 | ||
353 | return 0; | |
354 | } | |
355 | ||
a99e7c2b MT |
356 | LOC_EXPORT int loc_network_has_flag(struct loc_network* network, uint32_t flag) { |
357 | return network->flags & flag; | |
358 | } | |
359 | ||
360 | LOC_EXPORT int loc_network_set_flag(struct loc_network* network, uint32_t flag) { | |
361 | network->flags |= flag; | |
362 | ||
363 | return 0; | |
364 | } | |
365 | ||
af4689bf | 366 | LOC_EXPORT int loc_network_cmp(struct loc_network* self, struct loc_network* other) { |
af4689bf | 367 | // Compare address |
9c1e2943 | 368 | int r = loc_address_cmp(&self->first_address, &other->first_address); |
af4689bf MT |
369 | if (r) |
370 | return r; | |
371 | ||
372 | // Compare prefix | |
373 | if (self->prefix > other->prefix) | |
374 | return 1; | |
375 | else if (self->prefix < other->prefix) | |
376 | return -1; | |
377 | ||
378 | // Both networks are equal | |
379 | return 0; | |
380 | } | |
381 | ||
6159d384 | 382 | LOC_EXPORT int loc_network_overlaps(struct loc_network* self, struct loc_network* other) { |
fc692a58 | 383 | // Either of the start addresses must be in the other subnet |
0258d3c9 | 384 | if (loc_network_matches_address(self, &other->first_address)) |
6159d384 MT |
385 | return 1; |
386 | ||
0258d3c9 | 387 | if (loc_network_matches_address(other, &self->first_address)) |
6159d384 MT |
388 | return 1; |
389 | ||
fc692a58 | 390 | // Or either of the end addresses is in the other subnet |
0258d3c9 | 391 | if (loc_network_matches_address(self, &other->last_address)) |
6159d384 MT |
392 | return 1; |
393 | ||
0258d3c9 | 394 | if (loc_network_matches_address(other, &self->last_address)) |
6159d384 MT |
395 | return 1; |
396 | ||
397 | return 0; | |
398 | } | |
399 | ||
33a051e0 | 400 | LOC_EXPORT int loc_network_is_subnet(struct loc_network* self, struct loc_network* other) { |
cf8d3c64 MT |
401 | // The prefix must be smaller (this avoids the more complex comparisons later) |
402 | if (self->prefix > other->prefix) | |
403 | return 0; | |
404 | ||
33a051e0 MT |
405 | // If the start address of the other network is smaller than this network, |
406 | // it cannot be a subnet. | |
9c1e2943 | 407 | if (loc_address_cmp(&self->first_address, &other->first_address) > 0) |
33a051e0 MT |
408 | return 0; |
409 | ||
410 | // If the end address of the other network is greater than this network, | |
411 | // it cannot be a subnet. | |
9c1e2943 | 412 | if (loc_address_cmp(&self->last_address, &other->last_address) < 0) |
33a051e0 MT |
413 | return 0; |
414 | ||
415 | return 1; | |
416 | } | |
417 | ||
a5967330 MT |
418 | LOC_EXPORT int loc_network_subnets(struct loc_network* network, |
419 | struct loc_network** subnet1, struct loc_network** subnet2) { | |
420 | int r; | |
421 | *subnet1 = NULL; | |
422 | *subnet2 = NULL; | |
850e7516 MT |
423 | |
424 | // New prefix length | |
425 | unsigned int prefix = network->prefix + 1; | |
426 | ||
427 | // Check if the new prefix is valid | |
428 | if (valid_prefix(&network->first_address, prefix)) | |
a5967330 | 429 | return -1; |
850e7516 MT |
430 | |
431 | // Create the first half of the network | |
a5967330 | 432 | r = loc_network_new(network->ctx, subnet1, &network->first_address, prefix); |
850e7516 | 433 | if (r) |
a5967330 | 434 | return r; |
850e7516 MT |
435 | |
436 | // The next subnet starts after the first one | |
a5967330 | 437 | struct in6_addr first_address = address_increment(&(*subnet1)->last_address); |
850e7516 MT |
438 | |
439 | // Create the second half of the network | |
a5967330 | 440 | r = loc_network_new(network->ctx, subnet2, &first_address, prefix); |
850e7516 | 441 | if (r) |
a5967330 | 442 | return r; |
850e7516 | 443 | |
594ca328 MT |
444 | // Copy country code |
445 | const char* country_code = loc_network_get_country_code(network); | |
446 | if (country_code) { | |
a5967330 MT |
447 | loc_network_set_country_code(*subnet1, country_code); |
448 | loc_network_set_country_code(*subnet2, country_code); | |
594ca328 MT |
449 | } |
450 | ||
451 | // Copy ASN | |
452 | uint32_t asn = loc_network_get_asn(network); | |
453 | if (asn) { | |
a5967330 MT |
454 | loc_network_set_asn(*subnet1, asn); |
455 | loc_network_set_asn(*subnet2, asn); | |
594ca328 MT |
456 | } |
457 | ||
3e8d86ab MT |
458 | // Copy flags |
459 | loc_network_set_flag(*subnet1, network->flags); | |
460 | loc_network_set_flag(*subnet2, network->flags); | |
461 | ||
a5967330 MT |
462 | return 0; |
463 | } | |
850e7516 | 464 | |
a5967330 MT |
465 | static int __loc_network_exclude(struct loc_network* network, |
466 | struct loc_network* other, struct loc_network_list* list) { | |
467 | struct loc_network* subnet1 = NULL; | |
468 | struct loc_network* subnet2 = NULL; | |
469 | ||
470 | int r = loc_network_subnets(network, &subnet1, &subnet2); | |
471 | if (r) | |
472 | goto ERROR; | |
473 | ||
da101d55 | 474 | if (loc_network_cmp(other, subnet1) == 0) { |
a5967330 MT |
475 | r = loc_network_list_push(list, subnet2); |
476 | if (r) | |
477 | goto ERROR; | |
478 | ||
da101d55 | 479 | } else if (loc_network_cmp(other, subnet2) == 0) { |
a5967330 MT |
480 | r = loc_network_list_push(list, subnet1); |
481 | if (r) | |
482 | goto ERROR; | |
483 | ||
d6a5092f | 484 | } else if (loc_network_is_subnet(subnet1, other)) { |
a5967330 MT |
485 | r = loc_network_list_push(list, subnet2); |
486 | if (r) | |
487 | goto ERROR; | |
488 | ||
489 | r = __loc_network_exclude(subnet1, other, list); | |
490 | if (r) | |
491 | goto ERROR; | |
492 | ||
d6a5092f | 493 | } else if (loc_network_is_subnet(subnet2, other)) { |
a5967330 MT |
494 | r = loc_network_list_push(list, subnet1); |
495 | if (r) | |
496 | goto ERROR; | |
497 | ||
498 | r = __loc_network_exclude(subnet2, other, list); | |
499 | if (r) | |
500 | goto ERROR; | |
501 | ||
502 | } else { | |
503 | ERROR(network->ctx, "We should never get here\n"); | |
504 | r = 1; | |
505 | goto ERROR; | |
506 | } | |
850e7516 MT |
507 | |
508 | ERROR: | |
509 | if (subnet1) | |
510 | loc_network_unref(subnet1); | |
511 | ||
512 | if (subnet2) | |
513 | loc_network_unref(subnet2); | |
514 | ||
a5967330 | 515 | return r; |
850e7516 MT |
516 | } |
517 | ||
c650008e MT |
518 | static int __loc_network_exclude_to_list(struct loc_network* self, |
519 | struct loc_network* other, struct loc_network_list* list) { | |
850e7516 | 520 | // Other must be a subnet of self |
d6a5092f | 521 | if (!loc_network_is_subnet(self, other)) { |
850e7516 MT |
522 | DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self); |
523 | ||
abf55926 MT |
524 | // Exit silently |
525 | return 0; | |
850e7516 MT |
526 | } |
527 | ||
528 | // We cannot perform this operation if both networks equal | |
da101d55 | 529 | if (loc_network_cmp(self, other) == 0) { |
850e7516 MT |
530 | DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other); |
531 | ||
abf55926 MT |
532 | // Exit silently |
533 | return 0; | |
850e7516 MT |
534 | } |
535 | ||
c650008e MT |
536 | return __loc_network_exclude(self, other, list); |
537 | } | |
538 | ||
539 | LOC_EXPORT struct loc_network_list* loc_network_exclude( | |
540 | struct loc_network* self, struct loc_network* other) { | |
541 | struct loc_network_list* list; | |
542 | ||
543 | #ifdef ENABLE_DEBUG | |
544 | char* n1 = loc_network_str(self); | |
545 | char* n2 = loc_network_str(other); | |
546 | ||
547 | DEBUG(self->ctx, "Returning %s excluding %s...\n", n1, n2); | |
548 | ||
549 | free(n1); | |
550 | free(n2); | |
551 | #endif | |
552 | ||
850e7516 MT |
553 | // Create a new list with the result |
554 | int r = loc_network_list_new(self->ctx, &list); | |
555 | if (r) { | |
556 | ERROR(self->ctx, "Could not create network list: %d\n", r); | |
c650008e | 557 | |
850e7516 MT |
558 | return NULL; |
559 | } | |
560 | ||
c650008e | 561 | r = __loc_network_exclude_to_list(self, other, list); |
a5967330 MT |
562 | if (r) { |
563 | loc_network_list_unref(list); | |
850e7516 | 564 | |
a5967330 | 565 | return NULL; |
850e7516 MT |
566 | } |
567 | ||
850e7516 MT |
568 | // Return the result |
569 | return list; | |
850e7516 MT |
570 | } |
571 | ||
add5bb65 MT |
572 | LOC_EXPORT struct loc_network_list* loc_network_exclude_list( |
573 | struct loc_network* network, struct loc_network_list* list) { | |
574 | struct loc_network_list* to_check; | |
575 | ||
576 | // Create a new list with all networks to look at | |
577 | int r = loc_network_list_new(network->ctx, &to_check); | |
578 | if (r) | |
579 | return NULL; | |
580 | ||
581 | struct loc_network* subnet = NULL; | |
582 | struct loc_network_list* subnets = NULL; | |
583 | ||
584 | for (unsigned int i = 0; i < loc_network_list_size(list); i++) { | |
585 | subnet = loc_network_list_get(list, i); | |
586 | ||
587 | // Find all excluded networks | |
c650008e MT |
588 | if (!loc_network_list_contains(to_check, subnet)) { |
589 | r = __loc_network_exclude_to_list(network, subnet, to_check); | |
590 | if (r) { | |
591 | loc_network_list_unref(to_check); | |
592 | loc_network_unref(subnet); | |
593 | ||
594 | return NULL; | |
595 | } | |
add5bb65 MT |
596 | } |
597 | ||
598 | // Cleanup | |
599 | loc_network_unref(subnet); | |
600 | } | |
601 | ||
602 | r = loc_network_list_new(network->ctx, &subnets); | |
603 | if (r) { | |
604 | loc_network_list_unref(to_check); | |
605 | return NULL; | |
606 | } | |
607 | ||
058e7800 MT |
608 | off_t smallest_subnet = 0; |
609 | ||
add5bb65 | 610 | while (!loc_network_list_empty(to_check)) { |
058e7800 | 611 | struct loc_network* subnet_to_check = loc_network_list_pop_first(to_check); |
add5bb65 | 612 | |
06177d8c MT |
613 | // Check whether the subnet to check is part of the input list |
614 | if (loc_network_list_contains(list, subnet_to_check)) { | |
615 | loc_network_unref(subnet_to_check); | |
616 | continue; | |
617 | } | |
618 | ||
add5bb65 MT |
619 | // Marks whether this subnet passed all checks |
620 | int passed = 1; | |
621 | ||
058e7800 | 622 | for (unsigned int i = smallest_subnet; i < loc_network_list_size(list); i++) { |
add5bb65 MT |
623 | subnet = loc_network_list_get(list, i); |
624 | ||
add5bb65 | 625 | // Drop this subnet if is a subnet of another subnet |
4de8ff8e | 626 | if (loc_network_is_subnet(subnet, subnet_to_check)) { |
add5bb65 MT |
627 | passed = 0; |
628 | loc_network_unref(subnet); | |
629 | break; | |
630 | } | |
631 | ||
632 | // Break it down if it overlaps | |
4de8ff8e | 633 | if (loc_network_overlaps(subnet, subnet_to_check)) { |
add5bb65 MT |
634 | passed = 0; |
635 | ||
4fc034e2 | 636 | __loc_network_exclude_to_list(subnet_to_check, subnet, to_check); |
add5bb65 MT |
637 | |
638 | loc_network_unref(subnet); | |
639 | break; | |
640 | } | |
641 | ||
058e7800 MT |
642 | // If the subnet is strictly greater, we do not need to continue the search |
643 | r = loc_network_cmp(subnet, subnet_to_check); | |
644 | if (r > 0) { | |
645 | loc_network_unref(subnet); | |
646 | break; | |
647 | ||
648 | // If it is strictly smaller, we can continue the search from here next | |
649 | // time because all networks that are to be checked can only be larger | |
650 | // than this one. | |
651 | } else if (r < 0) { | |
652 | smallest_subnet = i; | |
653 | } | |
654 | ||
add5bb65 MT |
655 | loc_network_unref(subnet); |
656 | } | |
657 | ||
658 | if (passed) { | |
659 | r = loc_network_list_push(subnets, subnet_to_check); | |
660 | } | |
661 | ||
662 | loc_network_unref(subnet_to_check); | |
663 | } | |
664 | ||
665 | loc_network_list_unref(to_check); | |
666 | ||
667 | return subnets; | |
668 | } | |
669 | ||
8298728e | 670 | int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) { |
f3e02bc5 | 671 | // Add country code |
a7a3d958 | 672 | loc_country_code_copy(dbobj->country_code, network->country_code); |
f3e02bc5 MT |
673 | |
674 | // Add ASN | |
71ff3e69 | 675 | dbobj->asn = htobe32(network->asn); |
f3e02bc5 | 676 | |
a99e7c2b | 677 | // Flags |
eee6346d | 678 | dbobj->flags = htobe16(network->flags); |
a99e7c2b | 679 | |
f3e02bc5 MT |
680 | return 0; |
681 | } | |
682 | ||
8298728e | 683 | int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network, |
b904896a | 684 | struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) { |
3dc8adfb | 685 | char country_code[3] = "\0\0"; |
a7a3d958 | 686 | |
39a55353 | 687 | int r = loc_network_new(ctx, network, address, prefix); |
94a3f329 MT |
688 | if (r) { |
689 | ERROR(ctx, "Could not allocate a new network: %s", strerror(-r)); | |
10778041 | 690 | return r; |
94a3f329 | 691 | } |
10778041 MT |
692 | |
693 | // Import country code | |
a7a3d958 | 694 | loc_country_code_copy(country_code, dbobj->country_code); |
10778041 MT |
695 | |
696 | r = loc_network_set_country_code(*network, country_code); | |
94a3f329 MT |
697 | if (r) { |
698 | ERROR(ctx, "Could not set country code: %s\n", country_code); | |
10778041 | 699 | return r; |
94a3f329 | 700 | } |
10778041 MT |
701 | |
702 | // Import ASN | |
94a3f329 MT |
703 | uint32_t asn = be32toh(dbobj->asn); |
704 | r = loc_network_set_asn(*network, asn); | |
705 | if (r) { | |
706 | ERROR(ctx, "Could not set ASN: %d\n", asn); | |
10778041 | 707 | return r; |
94a3f329 | 708 | } |
10778041 | 709 | |
a99e7c2b | 710 | // Import flags |
94a3f329 MT |
711 | int flags = be16toh(dbobj->flags); |
712 | r = loc_network_set_flag(*network, flags); | |
713 | if (r) { | |
714 | ERROR(ctx, "Could not set flags: %d\n", flags); | |
a99e7c2b | 715 | return r; |
94a3f329 | 716 | } |
a99e7c2b | 717 | |
10778041 MT |
718 | return 0; |
719 | } | |
720 | ||
3b5f4af2 MT |
721 | struct loc_network_tree { |
722 | struct loc_ctx* ctx; | |
723 | int refcount; | |
724 | ||
725 | struct loc_network_tree_node* root; | |
726 | }; | |
727 | ||
728 | struct loc_network_tree_node { | |
438db08c MT |
729 | struct loc_ctx* ctx; |
730 | int refcount; | |
731 | ||
3b5f4af2 MT |
732 | struct loc_network_tree_node* zero; |
733 | struct loc_network_tree_node* one; | |
734 | ||
735 | struct loc_network* network; | |
736 | }; | |
737 | ||
7933f5bf | 738 | int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) { |
3b5f4af2 MT |
739 | struct loc_network_tree* t = calloc(1, sizeof(*t)); |
740 | if (!t) | |
741 | return -ENOMEM; | |
742 | ||
743 | t->ctx = loc_ref(ctx); | |
744 | t->refcount = 1; | |
745 | ||
746 | // Create the root node | |
438db08c MT |
747 | int r = loc_network_tree_node_new(ctx, &t->root); |
748 | if (r) { | |
749 | loc_network_tree_unref(t); | |
750 | return r; | |
751 | } | |
3b5f4af2 MT |
752 | |
753 | DEBUG(t->ctx, "Network tree allocated at %p\n", t); | |
754 | *tree = t; | |
755 | return 0; | |
756 | } | |
757 | ||
7933f5bf | 758 | struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) { |
438db08c | 759 | return loc_network_tree_node_ref(tree->root); |
3b5f4af2 MT |
760 | } |
761 | ||
762 | static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) { | |
763 | struct loc_network_tree_node** n; | |
764 | ||
2a30e4de | 765 | if (path == 0) |
3b5f4af2 | 766 | n = &node->zero; |
3eda9cab MT |
767 | else |
768 | n = &node->one; | |
3b5f4af2 MT |
769 | |
770 | // If the desired node doesn't exist, yet, we will create it | |
771 | if (*n == NULL) { | |
438db08c | 772 | int r = loc_network_tree_node_new(node->ctx, n); |
3b5f4af2 MT |
773 | if (r) |
774 | return NULL; | |
775 | } | |
776 | ||
777 | return *n; | |
778 | } | |
779 | ||
39a55353 | 780 | static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) { |
3b5f4af2 MT |
781 | struct loc_network_tree_node* node = tree->root; |
782 | ||
39a55353 | 783 | for (unsigned int i = 0; i < prefix; i++) { |
3b5f4af2 | 784 | // Check if the ith bit is one or zero |
2a30e4de | 785 | node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i)); |
3b5f4af2 MT |
786 | } |
787 | ||
788 | return node; | |
789 | } | |
790 | ||
791 | static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node, | |
f3e02bc5 MT |
792 | int(*filter_callback)(struct loc_network* network, void* data), |
793 | int(*callback)(struct loc_network* network, void* data), void* data) { | |
3b5f4af2 MT |
794 | int r; |
795 | ||
796 | // Finding a network ends the walk here | |
797 | if (node->network) { | |
798 | if (filter_callback) { | |
f3e02bc5 | 799 | int f = filter_callback(node->network, data); |
3b5f4af2 MT |
800 | if (f < 0) |
801 | return f; | |
802 | ||
803 | // Skip network if filter function returns value greater than zero | |
804 | if (f > 0) | |
805 | return 0; | |
806 | } | |
807 | ||
f3e02bc5 | 808 | r = callback(node->network, data); |
3b5f4af2 MT |
809 | if (r) |
810 | return r; | |
811 | } | |
812 | ||
813 | // Walk down on the left side of the tree first | |
814 | if (node->zero) { | |
f3e02bc5 | 815 | r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data); |
3b5f4af2 MT |
816 | if (r) |
817 | return r; | |
818 | } | |
819 | ||
820 | // Then walk on the other side | |
821 | if (node->one) { | |
f3e02bc5 | 822 | r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data); |
3b5f4af2 MT |
823 | if (r) |
824 | return r; | |
825 | } | |
826 | ||
827 | return 0; | |
828 | } | |
829 | ||
7933f5bf | 830 | int loc_network_tree_walk(struct loc_network_tree* tree, |
f3e02bc5 MT |
831 | int(*filter_callback)(struct loc_network* network, void* data), |
832 | int(*callback)(struct loc_network* network, void* data), void* data) { | |
833 | return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data); | |
834 | } | |
835 | ||
3b5f4af2 MT |
836 | static void loc_network_tree_free(struct loc_network_tree* tree) { |
837 | DEBUG(tree->ctx, "Releasing network tree at %p\n", tree); | |
838 | ||
438db08c | 839 | loc_network_tree_node_unref(tree->root); |
3b5f4af2 MT |
840 | |
841 | loc_unref(tree->ctx); | |
842 | free(tree); | |
843 | } | |
844 | ||
7933f5bf | 845 | struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) { |
3b5f4af2 MT |
846 | if (--tree->refcount > 0) |
847 | return tree; | |
848 | ||
849 | loc_network_tree_free(tree); | |
850 | return NULL; | |
851 | } | |
852 | ||
e9b4e2a8 | 853 | static int __loc_network_tree_dump(struct loc_network* network, void* data) { |
3b5f4af2 MT |
854 | DEBUG(network->ctx, "Dumping network at %p\n", network); |
855 | ||
856 | char* s = loc_network_str(network); | |
857 | if (!s) | |
858 | return 1; | |
859 | ||
860 | INFO(network->ctx, "%s\n", s); | |
861 | free(s); | |
862 | ||
863 | return 0; | |
864 | } | |
865 | ||
7933f5bf | 866 | int loc_network_tree_dump(struct loc_network_tree* tree) { |
3b5f4af2 MT |
867 | DEBUG(tree->ctx, "Dumping network tree at %p\n", tree); |
868 | ||
f3e02bc5 | 869 | return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL); |
3b5f4af2 MT |
870 | } |
871 | ||
7933f5bf | 872 | int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) { |
3b5f4af2 MT |
873 | DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree); |
874 | ||
39a55353 | 875 | struct loc_network_tree_node* node = loc_network_tree_get_path(tree, |
ce4f5752 | 876 | &network->first_address, network->prefix); |
3b5f4af2 MT |
877 | if (!node) { |
878 | ERROR(tree->ctx, "Could not find a node\n"); | |
879 | return -ENOMEM; | |
880 | } | |
881 | ||
882 | // Check if node has not been set before | |
883 | if (node->network) { | |
884 | DEBUG(tree->ctx, "There is already a network at this path\n"); | |
c04005bb | 885 | return -EBUSY; |
3b5f4af2 MT |
886 | } |
887 | ||
888 | // Point node to the network | |
889 | node->network = loc_network_ref(network); | |
890 | ||
891 | return 0; | |
892 | } | |
f3e02bc5 MT |
893 | |
894 | static int __loc_network_tree_count(struct loc_network* network, void* data) { | |
895 | size_t* counter = (size_t*)data; | |
896 | ||
897 | // Increase the counter for each network | |
898 | counter++; | |
899 | ||
900 | return 0; | |
901 | } | |
902 | ||
7933f5bf | 903 | size_t loc_network_tree_count_networks(struct loc_network_tree* tree) { |
f3e02bc5 MT |
904 | size_t counter = 0; |
905 | ||
906 | int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter); | |
907 | if (r) | |
908 | return r; | |
909 | ||
910 | return counter; | |
911 | } | |
940f9c2b MT |
912 | |
913 | static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) { | |
914 | size_t counter = 1; | |
915 | ||
916 | if (node->zero) | |
917 | counter += __loc_network_tree_count_nodes(node->zero); | |
918 | ||
919 | if (node->one) | |
920 | counter += __loc_network_tree_count_nodes(node->one); | |
921 | ||
922 | return counter; | |
923 | } | |
924 | ||
7933f5bf | 925 | size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) { |
940f9c2b MT |
926 | return __loc_network_tree_count_nodes(tree->root); |
927 | } | |
438db08c | 928 | |
7933f5bf | 929 | int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) { |
438db08c MT |
930 | struct loc_network_tree_node* n = calloc(1, sizeof(*n)); |
931 | if (!n) | |
932 | return -ENOMEM; | |
933 | ||
934 | n->ctx = loc_ref(ctx); | |
935 | n->refcount = 1; | |
936 | ||
937 | n->zero = n->one = NULL; | |
938 | ||
939 | DEBUG(n->ctx, "Network node allocated at %p\n", n); | |
940 | *node = n; | |
941 | return 0; | |
942 | } | |
943 | ||
7933f5bf | 944 | struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) { |
438db08c MT |
945 | if (node) |
946 | node->refcount++; | |
947 | ||
948 | return node; | |
949 | } | |
950 | ||
951 | static void loc_network_tree_node_free(struct loc_network_tree_node* node) { | |
952 | DEBUG(node->ctx, "Releasing network node at %p\n", node); | |
953 | ||
954 | if (node->network) | |
955 | loc_network_unref(node->network); | |
956 | ||
957 | if (node->zero) | |
958 | loc_network_tree_node_unref(node->zero); | |
959 | ||
960 | if (node->one) | |
961 | loc_network_tree_node_unref(node->one); | |
962 | ||
963 | loc_unref(node->ctx); | |
964 | free(node); | |
965 | } | |
966 | ||
7933f5bf | 967 | struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) { |
438db08c MT |
968 | if (!node) |
969 | return NULL; | |
970 | ||
971 | if (--node->refcount > 0) | |
972 | return node; | |
973 | ||
974 | loc_network_tree_node_free(node); | |
975 | return NULL; | |
976 | } | |
977 | ||
7933f5bf | 978 | struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) { |
438db08c MT |
979 | if (index == 0) |
980 | node = node->zero; | |
981 | else | |
982 | node = node->one; | |
983 | ||
984 | if (!node) | |
985 | return NULL; | |
986 | ||
987 | return loc_network_tree_node_ref(node); | |
988 | } | |
989 | ||
7933f5bf | 990 | int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) { |
438db08c MT |
991 | return (!!node->network); |
992 | } | |
993 | ||
7933f5bf | 994 | struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) { |
438db08c MT |
995 | return loc_network_ref(node->network); |
996 | } |