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