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