]> git.ipfire.org Git - people/ms/libloc.git/blob - src/network.c
importer: Drop EDROP as it has been merged into DROP
[people/ms/libloc.git] / src / network.c
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>
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include <string.h>
23
24 #ifdef HAVE_ENDIAN_H
25 # include <endian.h>
26 #endif
27
28 #include <loc/libloc.h>
29 #include <loc/compat.h>
30 #include <loc/country.h>
31 #include <loc/network.h>
32 #include <loc/private.h>
33
34 struct loc_network {
35 struct loc_ctx* ctx;
36 int refcount;
37
38 int family;
39 struct in6_addr first_address;
40 struct in6_addr last_address;
41 unsigned int prefix;
42
43 char country_code[3];
44 uint32_t asn;
45 enum loc_network_flags flags;
46 };
47
48 static int valid_prefix(struct in6_addr* address, unsigned int prefix) {
49 // The prefix cannot be larger than 128 bits
50 if (prefix > 128)
51 return 1;
52
53 // And the prefix cannot be zero
54 if (prefix == 0)
55 return 1;
56
57 // For IPv4-mapped addresses the prefix has to be 96 or lager
58 if (IN6_IS_ADDR_V4MAPPED(address) && prefix <= 96)
59 return 1;
60
61 return 0;
62 }
63
64 static struct in6_addr prefix_to_bitmask(unsigned int prefix) {
65 struct in6_addr bitmask;
66
67 for (unsigned int i = 0; i < 16; i++)
68 bitmask.s6_addr[i] = 0;
69
70 for (int i = prefix, j = 0; i > 0; i -= 8, j++) {
71 if (i >= 8)
72 bitmask.s6_addr[j] = 0xff;
73 else
74 bitmask.s6_addr[j] = 0xff << (8 - i);
75 }
76
77 return bitmask;
78 }
79
80 static struct in6_addr make_first_address(const struct in6_addr* address, const struct in6_addr* bitmask) {
81 struct in6_addr a;
82
83 // Perform bitwise AND
84 for (unsigned int i = 0; i < 4; i++)
85 a.s6_addr32[i] = address->s6_addr32[i] & bitmask->s6_addr32[i];
86
87 return a;
88 }
89
90 static struct in6_addr make_last_address(const struct in6_addr* address, const struct in6_addr* bitmask) {
91 struct in6_addr a;
92
93 // Perform bitwise OR
94 for (unsigned int i = 0; i < 4; i++)
95 a.s6_addr32[i] = address->s6_addr32[i] | ~bitmask->s6_addr32[i];
96
97 return a;
98 }
99
100 LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
101 struct in6_addr* address, unsigned int prefix) {
102 // Address cannot be unspecified
103 if (IN6_IS_ADDR_UNSPECIFIED(address)) {
104 DEBUG(ctx, "Start address is unspecified\n");
105 return -EINVAL;
106 }
107
108 // Address cannot be loopback
109 if (IN6_IS_ADDR_LOOPBACK(address)) {
110 DEBUG(ctx, "Start address is loopback address\n");
111 return -EINVAL;
112 }
113
114 // Address cannot be link-local
115 if (IN6_IS_ADDR_LINKLOCAL(address)) {
116 DEBUG(ctx, "Start address cannot be link-local\n");
117 return -EINVAL;
118 }
119
120 // Address cannot be site-local
121 if (IN6_IS_ADDR_SITELOCAL(address)) {
122 DEBUG(ctx, "Start address cannot be site-local\n");
123 return -EINVAL;
124 }
125
126 // Validate the prefix
127 if (valid_prefix(address, prefix) != 0) {
128 DEBUG(ctx, "Invalid prefix: %u\n", prefix);
129 return -EINVAL;
130 }
131
132 struct loc_network* n = calloc(1, sizeof(*n));
133 if (!n)
134 return -ENOMEM;
135
136 n->ctx = loc_ref(ctx);
137 n->refcount = 1;
138
139 // Store the prefix
140 n->prefix = prefix;
141
142 // Convert the prefix into a bitmask
143 struct in6_addr bitmask = prefix_to_bitmask(n->prefix);
144
145 // Store the first and last address in the network
146 n->first_address = make_first_address(address, &bitmask);
147 n->last_address = make_last_address(&n->first_address, &bitmask);
148
149 // Set family
150 if (IN6_IS_ADDR_V4MAPPED(&n->first_address))
151 n->family = AF_INET;
152 else
153 n->family = AF_INET6;
154
155 DEBUG(n->ctx, "Network allocated at %p\n", n);
156 *network = n;
157 return 0;
158 }
159
160 LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
161 const char* address_string) {
162 struct in6_addr first_address;
163 char* prefix_string;
164 unsigned int prefix = 128;
165 int r = -EINVAL;
166
167 DEBUG(ctx, "Attempting to parse network %s\n", address_string);
168
169 // Make a copy of the string to work on it
170 char* buffer = strdup(address_string);
171 address_string = prefix_string = buffer;
172
173 // Split address and prefix
174 address_string = strsep(&prefix_string, "/");
175
176 DEBUG(ctx, " Split into address = %s, prefix = %s\n", address_string, prefix_string);
177
178 // Parse the address
179 r = loc_parse_address(ctx, address_string, &first_address);
180 if (r) {
181 DEBUG(ctx, "The address could not be parsed\n");
182 goto FAIL;
183 }
184
185 // If a prefix was given, we will try to parse it
186 if (prefix_string) {
187 // Convert prefix to integer
188 prefix = strtol(prefix_string, NULL, 10);
189
190 if (!prefix) {
191 DEBUG(ctx, "The prefix was not parsable: %s\n", prefix_string);
192 goto FAIL;
193 }
194
195 // Map the prefix to IPv6 if needed
196 if (IN6_IS_ADDR_V4MAPPED(&first_address))
197 prefix += 96;
198 }
199
200 FAIL:
201 // Free temporary buffer
202 free(buffer);
203
204 // Exit if the parsing was unsuccessful
205 if (r)
206 return r;
207
208 // Create a new network
209 return loc_network_new(ctx, network, &first_address, prefix);
210 }
211
212 LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
213 network->refcount++;
214
215 return network;
216 }
217
218 static void loc_network_free(struct loc_network* network) {
219 DEBUG(network->ctx, "Releasing network at %p\n", network);
220
221 loc_unref(network->ctx);
222 free(network);
223 }
224
225 LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
226 if (!network)
227 return NULL;
228
229 if (--network->refcount > 0)
230 return network;
231
232 loc_network_free(network);
233 return NULL;
234 }
235
236 static int format_ipv6_address(const struct in6_addr* address, char* string, size_t length) {
237 const char* ret = inet_ntop(AF_INET6, address, string, length);
238 if (!ret)
239 return -1;
240
241 return 0;
242 }
243
244 static int format_ipv4_address(const struct in6_addr* address, char* string, size_t length) {
245 struct in_addr ipv4_address;
246 ipv4_address.s_addr = address->s6_addr32[3];
247
248 const char* ret = inet_ntop(AF_INET, &ipv4_address, string, length);
249 if (!ret)
250 return -1;
251
252 return 0;
253 }
254
255 LOC_EXPORT char* loc_network_str(struct loc_network* network) {
256 int r;
257 const size_t length = INET6_ADDRSTRLEN + 4;
258
259 char* string = malloc(length);
260 if (!string)
261 return NULL;
262
263 unsigned int prefix = network->prefix;
264
265 switch (network->family) {
266 case AF_INET6:
267 r = format_ipv6_address(&network->first_address, string, length);
268 break;
269
270 case AF_INET:
271 r = format_ipv4_address(&network->first_address, string, length);
272 prefix -= 96;
273 break;
274
275 default:
276 r = -1;
277 break;
278 }
279
280 if (r) {
281 ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno));
282 free(string);
283
284 return NULL;
285 }
286
287 // Append prefix
288 sprintf(string + strlen(string), "/%u", prefix);
289
290 return string;
291 }
292
293 LOC_EXPORT int loc_network_address_family(struct loc_network* network) {
294 return network->family;
295 }
296
297 static char* loc_network_format_address(struct loc_network* network, const struct in6_addr* address) {
298 const size_t length = INET6_ADDRSTRLEN;
299
300 char* string = malloc(length);
301 if (!string)
302 return NULL;
303
304 int r = 0;
305
306 switch (network->family) {
307 case AF_INET6:
308 r = format_ipv6_address(address, string, length);
309 break;
310
311 case AF_INET:
312 r = format_ipv4_address(address, string, length);
313 break;
314
315 default:
316 r = -1;
317 break;
318 }
319
320 if (r) {
321 ERROR(network->ctx, "Could not format IP address to string: %s\n", strerror(errno));
322 free(string);
323
324 return NULL;
325 }
326
327 return string;
328 }
329
330 LOC_EXPORT char* loc_network_format_first_address(struct loc_network* network) {
331 return loc_network_format_address(network, &network->first_address);
332 }
333
334 LOC_EXPORT char* loc_network_format_last_address(struct loc_network* network) {
335 return loc_network_format_address(network, &network->last_address);
336 }
337
338 LOC_EXPORT int loc_network_match_address(struct loc_network* network, const struct in6_addr* address) {
339 // Address must be larger than the start address
340 if (in6_addr_cmp(&network->first_address, address) > 0)
341 return 1;
342
343 // Address must be smaller than the last address
344 if (in6_addr_cmp(&network->last_address, address) < 0)
345 return 1;
346
347 // The address is inside this network
348 return 0;
349 }
350
351 LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
352 return network->country_code;
353 }
354
355 LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) {
356 // Set empty country code
357 if (!country_code || !*country_code) {
358 *network->country_code = '\0';
359 return 0;
360 }
361
362 // Check country code
363 if (!loc_country_code_is_valid(country_code))
364 return -EINVAL;
365
366 loc_country_code_copy(network->country_code, country_code);
367
368 return 0;
369 }
370
371 LOC_EXPORT int loc_network_match_country_code(struct loc_network* network, const char* country_code) {
372 // Check country code
373 if (!loc_country_code_is_valid(country_code))
374 return -EINVAL;
375
376 return (network->country_code[0] == country_code[0])
377 && (network->country_code[1] == country_code[1]);
378 }
379
380 LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
381 return network->asn;
382 }
383
384 LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
385 network->asn = asn;
386
387 return 0;
388 }
389
390 LOC_EXPORT int loc_network_match_asn(struct loc_network* network, uint32_t asn) {
391 return network->asn == asn;
392 }
393
394 LOC_EXPORT int loc_network_has_flag(struct loc_network* network, uint32_t flag) {
395 return network->flags & flag;
396 }
397
398 LOC_EXPORT int loc_network_set_flag(struct loc_network* network, uint32_t flag) {
399 network->flags |= flag;
400
401 return 0;
402 }
403
404 LOC_EXPORT int loc_network_match_flag(struct loc_network* network, uint32_t flag) {
405 return loc_network_has_flag(network, flag);
406 }
407
408 LOC_EXPORT int loc_network_is_subnet_of(struct loc_network* self, struct loc_network* other) {
409 // If the start address of the other network is smaller than this network,
410 // it cannot be a subnet.
411 if (in6_addr_cmp(&self->first_address, &other->first_address) < 0)
412 return 0;
413
414 // If the end address of the other network is greater than this network,
415 // it cannot be a subnet.
416 if (in6_addr_cmp(&self->last_address, &other->last_address) > 0)
417 return 0;
418
419 return 1;
420 }
421
422 LOC_EXPORT int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
423 // Add country code
424 loc_country_code_copy(dbobj->country_code, network->country_code);
425
426 // Add ASN
427 dbobj->asn = htobe32(network->asn);
428
429 // Flags
430 dbobj->flags = htobe16(network->flags);
431
432 return 0;
433 }
434
435 LOC_EXPORT int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network,
436 struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) {
437 char country_code[3] = "\0\0";
438
439 int r = loc_network_new(ctx, network, address, prefix);
440 if (r) {
441 ERROR(ctx, "Could not allocate a new network: %s", strerror(-r));
442 return r;
443 }
444
445 // Import country code
446 loc_country_code_copy(country_code, dbobj->country_code);
447
448 r = loc_network_set_country_code(*network, country_code);
449 if (r) {
450 ERROR(ctx, "Could not set country code: %s\n", country_code);
451 return r;
452 }
453
454 // Import ASN
455 uint32_t asn = be32toh(dbobj->asn);
456 r = loc_network_set_asn(*network, asn);
457 if (r) {
458 ERROR(ctx, "Could not set ASN: %d\n", asn);
459 return r;
460 }
461
462 // Import flags
463 int flags = be16toh(dbobj->flags);
464 r = loc_network_set_flag(*network, flags);
465 if (r) {
466 ERROR(ctx, "Could not set flags: %d\n", flags);
467 return r;
468 }
469
470 return 0;
471 }
472
473 struct loc_network_tree {
474 struct loc_ctx* ctx;
475 int refcount;
476
477 struct loc_network_tree_node* root;
478 };
479
480 struct loc_network_tree_node {
481 struct loc_ctx* ctx;
482 int refcount;
483
484 struct loc_network_tree_node* zero;
485 struct loc_network_tree_node* one;
486
487 struct loc_network* network;
488 };
489
490 LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
491 struct loc_network_tree* t = calloc(1, sizeof(*t));
492 if (!t)
493 return -ENOMEM;
494
495 t->ctx = loc_ref(ctx);
496 t->refcount = 1;
497
498 // Create the root node
499 int r = loc_network_tree_node_new(ctx, &t->root);
500 if (r) {
501 loc_network_tree_unref(t);
502 return r;
503 }
504
505 DEBUG(t->ctx, "Network tree allocated at %p\n", t);
506 *tree = t;
507 return 0;
508 }
509
510 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
511 return loc_network_tree_node_ref(tree->root);
512 }
513
514 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
515 struct loc_network_tree_node** n;
516
517 if (path == 0)
518 n = &node->zero;
519 else
520 n = &node->one;
521
522 // If the desired node doesn't exist, yet, we will create it
523 if (*n == NULL) {
524 int r = loc_network_tree_node_new(node->ctx, n);
525 if (r)
526 return NULL;
527 }
528
529 return *n;
530 }
531
532 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
533 struct loc_network_tree_node* node = tree->root;
534
535 for (unsigned int i = 0; i < prefix; i++) {
536 // Check if the ith bit is one or zero
537 node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i));
538 }
539
540 return node;
541 }
542
543 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
544 int(*filter_callback)(struct loc_network* network, void* data),
545 int(*callback)(struct loc_network* network, void* data), void* data) {
546 int r;
547
548 // Finding a network ends the walk here
549 if (node->network) {
550 if (filter_callback) {
551 int f = filter_callback(node->network, data);
552 if (f < 0)
553 return f;
554
555 // Skip network if filter function returns value greater than zero
556 if (f > 0)
557 return 0;
558 }
559
560 r = callback(node->network, data);
561 if (r)
562 return r;
563 }
564
565 // Walk down on the left side of the tree first
566 if (node->zero) {
567 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
568 if (r)
569 return r;
570 }
571
572 // Then walk on the other side
573 if (node->one) {
574 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
575 if (r)
576 return r;
577 }
578
579 return 0;
580 }
581
582 LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
583 int(*filter_callback)(struct loc_network* network, void* data),
584 int(*callback)(struct loc_network* network, void* data), void* data) {
585 return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
586 }
587
588 static void loc_network_tree_free(struct loc_network_tree* tree) {
589 DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
590
591 loc_network_tree_node_unref(tree->root);
592
593 loc_unref(tree->ctx);
594 free(tree);
595 }
596
597 LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
598 if (--tree->refcount > 0)
599 return tree;
600
601 loc_network_tree_free(tree);
602 return NULL;
603 }
604
605 static int __loc_network_tree_dump(struct loc_network* network, void* data) {
606 DEBUG(network->ctx, "Dumping network at %p\n", network);
607
608 char* s = loc_network_str(network);
609 if (!s)
610 return 1;
611
612 INFO(network->ctx, "%s\n", s);
613 free(s);
614
615 return 0;
616 }
617
618 LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
619 DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
620
621 return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
622 }
623
624 LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
625 DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
626
627 struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
628 &network->first_address, network->prefix);
629 if (!node) {
630 ERROR(tree->ctx, "Could not find a node\n");
631 return -ENOMEM;
632 }
633
634 // Check if node has not been set before
635 if (node->network) {
636 DEBUG(tree->ctx, "There is already a network at this path\n");
637 return -EBUSY;
638 }
639
640 // Point node to the network
641 node->network = loc_network_ref(network);
642
643 return 0;
644 }
645
646 static int __loc_network_tree_count(struct loc_network* network, void* data) {
647 size_t* counter = (size_t*)data;
648
649 // Increase the counter for each network
650 counter++;
651
652 return 0;
653 }
654
655 LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
656 size_t counter = 0;
657
658 int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
659 if (r)
660 return r;
661
662 return counter;
663 }
664
665 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
666 size_t counter = 1;
667
668 if (node->zero)
669 counter += __loc_network_tree_count_nodes(node->zero);
670
671 if (node->one)
672 counter += __loc_network_tree_count_nodes(node->one);
673
674 return counter;
675 }
676
677 LOC_EXPORT size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
678 return __loc_network_tree_count_nodes(tree->root);
679 }
680
681 LOC_EXPORT int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
682 struct loc_network_tree_node* n = calloc(1, sizeof(*n));
683 if (!n)
684 return -ENOMEM;
685
686 n->ctx = loc_ref(ctx);
687 n->refcount = 1;
688
689 n->zero = n->one = NULL;
690
691 DEBUG(n->ctx, "Network node allocated at %p\n", n);
692 *node = n;
693 return 0;
694 }
695
696 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
697 if (node)
698 node->refcount++;
699
700 return node;
701 }
702
703 static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
704 DEBUG(node->ctx, "Releasing network node at %p\n", node);
705
706 if (node->network)
707 loc_network_unref(node->network);
708
709 if (node->zero)
710 loc_network_tree_node_unref(node->zero);
711
712 if (node->one)
713 loc_network_tree_node_unref(node->one);
714
715 loc_unref(node->ctx);
716 free(node);
717 }
718
719 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
720 if (!node)
721 return NULL;
722
723 if (--node->refcount > 0)
724 return node;
725
726 loc_network_tree_node_free(node);
727 return NULL;
728 }
729
730 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
731 if (index == 0)
732 node = node->zero;
733 else
734 node = node->one;
735
736 if (!node)
737 return NULL;
738
739 return loc_network_tree_node_ref(node);
740 }
741
742 LOC_EXPORT int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
743 return (!!node->network);
744 }
745
746 LOC_EXPORT struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
747 return loc_network_ref(node->network);
748 }