Fix evaluation that always is true
[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 (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_addr32[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(const struct in6_addr* address, char* string, size_t length) {
213         const char* ret = inet_ntop(AF_INET6, address, string, length);
214         if (!ret)
215                 return -1;
216
217         return 0;
218 }
219
220 static int format_ipv4_address(const struct in6_addr* address, char* string, size_t length) {
221         struct in_addr ipv4_address;
222         ipv4_address.s_addr = 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->start_address, string, length);
245                         break;
246
247                 case AF_INET:
248                         r = format_ipv4_address(&network->start_address, 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 than 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(address, &last_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         // Set empty country code
292         if (!country_code || !*country_code) {
293                 *network->country_code = '\0';
294                 return 0;
295         }
296
297         // Country codes must be two characters
298         if (strlen(country_code) != 2)
299                 return -EINVAL;
300
301         for (unsigned int i = 0; i < 3; i++) {
302                 network->country_code[i] = country_code[i];
303         }
304
305         return 0;
306 }
307
308 LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
309         return network->asn;
310 }
311
312 LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
313         network->asn = asn;
314
315         return 0;
316 }
317
318 LOC_EXPORT int loc_network_to_database_v0(struct loc_network* network, struct loc_database_network_v0* dbobj) {
319         // Add country code
320         for (unsigned int i = 0; i < 2; i++) {
321                 dbobj->country_code[i] = network->country_code[i] ? network->country_code[i] : '\0';
322         }
323
324         // Add ASN
325         dbobj->asn = htobe32(network->asn);
326
327         return 0;
328 }
329
330 LOC_EXPORT int loc_network_new_from_database_v0(struct loc_ctx* ctx, struct loc_network** network,
331                 struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v0* dbobj) {
332         int r = loc_network_new(ctx, network, address, prefix);
333         if (r)
334                 return r;
335
336         // Import country code
337         char country_code[3];
338         for (unsigned int i = 0; i < 2; i++) {
339                 country_code[i] = dbobj->country_code[i];
340         }
341         country_code[2] = '\0';
342
343         r = loc_network_set_country_code(*network, country_code);
344         if (r)
345                 return r;
346
347         // Import ASN
348         r = loc_network_set_asn(*network, be32toh(dbobj->asn));
349         if (r)
350                 return r;
351
352         return 0;
353 }
354
355 struct loc_network_tree {
356         struct loc_ctx* ctx;
357         int refcount;
358
359         struct loc_network_tree_node* root;
360 };
361
362 struct loc_network_tree_node {
363         struct loc_ctx* ctx;
364         int refcount;
365
366         struct loc_network_tree_node* zero;
367         struct loc_network_tree_node* one;
368
369         struct loc_network* network;
370 };
371
372 LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
373         struct loc_network_tree* t = calloc(1, sizeof(*t));
374         if (!t)
375                 return -ENOMEM;
376
377         t->ctx = loc_ref(ctx);
378         t->refcount = 1;
379
380         // Create the root node
381         int r = loc_network_tree_node_new(ctx, &t->root);
382         if (r) {
383                 loc_network_tree_unref(t);
384                 return r;
385         }
386
387         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
388         *tree = t;
389         return 0;
390 }
391
392 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
393         return loc_network_tree_node_ref(tree->root);
394 }
395
396 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
397         struct loc_network_tree_node** n;
398
399         if (path == 0)
400                 n = &node->zero;
401         else
402                 n = &node->one;
403
404         // If the desired node doesn't exist, yet, we will create it
405         if (*n == NULL) {
406                 int r = loc_network_tree_node_new(node->ctx, n);
407                 if (r)
408                         return NULL;
409         }
410
411         return *n;
412 }
413
414 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
415         struct loc_network_tree_node* node = tree->root;
416
417         for (unsigned int i = 0; i < prefix; i++) {
418                 // Check if the ith bit is one or zero
419                 node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i));
420         }
421
422         return node;
423 }
424
425 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
426                 int(*filter_callback)(struct loc_network* network, void* data),
427                 int(*callback)(struct loc_network* network, void* data), void* data) {
428         int r;
429
430         // Finding a network ends the walk here
431         if (node->network) {
432                 if (filter_callback) {
433                         int f = filter_callback(node->network, data);
434                         if (f < 0)
435                                 return f;
436
437                         // Skip network if filter function returns value greater than zero
438                         if (f > 0)
439                                 return 0;
440                 }
441
442                 r = callback(node->network, data);
443                 if (r)
444                         return r;
445         }
446
447         // Walk down on the left side of the tree first
448         if (node->zero) {
449                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
450                 if (r)
451                         return r;
452         }
453
454         // Then walk on the other side
455         if (node->one) {
456                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
457                 if (r)
458                         return r;
459         }
460
461         return 0;
462 }
463
464 LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
465                 int(*filter_callback)(struct loc_network* network, void* data),
466                 int(*callback)(struct loc_network* network, void* data), void* data) {
467         return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
468 }
469
470 static void loc_network_tree_free(struct loc_network_tree* tree) {
471         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
472
473         loc_network_tree_node_unref(tree->root);
474
475         loc_unref(tree->ctx);
476         free(tree);
477 }
478
479 LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
480         if (--tree->refcount > 0)
481                 return tree;
482
483         loc_network_tree_free(tree);
484         return NULL;
485 }
486
487 static int __loc_network_tree_dump(struct loc_network* network, void* data) {
488         DEBUG(network->ctx, "Dumping network at %p\n", network);
489
490         char* s = loc_network_str(network);
491         if (!s)
492                 return 1;
493
494         INFO(network->ctx, "%s\n", s);
495         free(s);
496
497         return 0;
498 }
499
500 LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
501         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
502
503         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
504 }
505
506 LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
507         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
508
509         struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
510                         &network->start_address, network->prefix);
511         if (!node) {
512                 ERROR(tree->ctx, "Could not find a node\n");
513                 return -ENOMEM;
514         }
515
516         // Check if node has not been set before
517         if (node->network) {
518                 DEBUG(tree->ctx, "There is already a network at this path\n");
519                 return -EBUSY;
520         }
521
522         // Point node to the network
523         node->network = loc_network_ref(network);
524
525         return 0;
526 }
527
528 static int __loc_network_tree_count(struct loc_network* network, void* data) {
529         size_t* counter = (size_t*)data;
530
531         // Increase the counter for each network
532         counter++;
533
534         return 0;
535 }
536
537 LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
538         size_t counter = 0;
539
540         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
541         if (r)
542                 return r;
543
544         return counter;
545 }
546
547 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
548         size_t counter = 1;
549
550         if (node->zero)
551                 counter += __loc_network_tree_count_nodes(node->zero);
552
553         if (node->one)
554                 counter += __loc_network_tree_count_nodes(node->one);
555
556         return counter;
557 }
558
559 LOC_EXPORT size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
560         return __loc_network_tree_count_nodes(tree->root);
561 }
562
563 LOC_EXPORT int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
564         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
565         if (!n)
566                 return -ENOMEM;
567
568         n->ctx = loc_ref(ctx);
569         n->refcount = 1;
570
571         n->zero = n->one = NULL;
572
573         DEBUG(n->ctx, "Network node allocated at %p\n", n);
574         *node = n;
575         return 0;
576 }
577
578 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
579         if (node)
580                 node->refcount++;
581
582         return node;
583 }
584
585 static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
586         DEBUG(node->ctx, "Releasing network node at %p\n", node);
587
588         if (node->network)
589                 loc_network_unref(node->network);
590
591         if (node->zero)
592                 loc_network_tree_node_unref(node->zero);
593
594         if (node->one)
595                 loc_network_tree_node_unref(node->one);
596
597         loc_unref(node->ctx);
598         free(node);
599 }
600
601 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
602         if (!node)
603                 return NULL;
604
605         if (--node->refcount > 0)
606                 return node;
607
608         loc_network_tree_node_free(node);
609         return NULL;
610 }
611
612 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
613         if (index == 0)
614                 node = node->zero;
615         else
616                 node = node->one;
617
618         if (!node)
619                 return NULL;
620
621         return loc_network_tree_node_ref(node);
622 }
623
624 LOC_EXPORT int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
625         return (!!node->network);
626 }
627
628 LOC_EXPORT struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
629         return loc_network_ref(node->network);
630 }