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