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         return 0;
  50 }
  51
  52 LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
  53                 struct in6_addr start_address, unsigned int prefix) {
  54         // Address cannot be unspecified
  55         if (IN6_IS_ADDR_UNSPECIFIED(&start_address)) {
  56                 DEBUG(ctx, "Start address is unspecified\n");
  57                 return -EINVAL;
  58         }
  59
  60         // Address cannot be loopback
  61         if (IN6_IS_ADDR_LOOPBACK(&start_address)) {
  62                 DEBUG(ctx, "Start address is loopback address\n");
  63                 return -EINVAL;
  64         }
  65
  66         // Address cannot be link-local
  67         if (IN6_IS_ADDR_LINKLOCAL(&start_address)) {
  68                 DEBUG(ctx, "Start address cannot be link-local\n");
  69                 return -EINVAL;
  70         }
  71
  72         // Address cannot be site-local
  73         if (IN6_IS_ADDR_SITELOCAL(&start_address)) {
  74                 DEBUG(ctx, "Start address cannot be site-local\n");
  75                 return -EINVAL;
  76         }
  77
  78         // Validate the prefix
  79         if (valid_prefix(&start_address, prefix) != 0) {
  80                 DEBUG(ctx, "Invalid prefix: %u\n", prefix);
  81                 return -EINVAL;
  82         }
  83
  84         struct loc_network* n = calloc(1, sizeof(*n));
  85         if (!n)
  86                 return -ENOMEM;
  87
  88         n->ctx = loc_ref(ctx);
  89         n->refcount = 1;
  90
  91         n->start_address = start_address;
  92         n->prefix = prefix;
  93
  94         DEBUG(n->ctx, "Network allocated at %p\n", n);
  95         *network = n;
  96         return 0;
  97 }
  98
  99 static int loc_network_address_family(struct loc_network* network) {
 100         if (IN6_IS_ADDR_V4MAPPED(&network->start_address))
 101                 return AF_INET;
 102
 103         return AF_INET6;
 104 }
 105
 106 static int parse_address(struct loc_ctx* ctx, const char* string, struct in6_addr* address) {
 107         DEBUG(ctx, "Paring IP address %s\n", string);
 108
 109         // Try parsing this as an IPv6 address
 110         int r = inet_pton(AF_INET6, string, address);
 111
 112         // If inet_pton returns one it has been successful
 113         if (r == 1) {
 114                 DEBUG(ctx, "%s is an IPv6 address\n", string);
 115                 return 0;
 116         }
 117
 118         // Try parsing this as an IPv4 address
 119         struct in_addr ipv4_address;
 120         r = inet_pton(AF_INET, string, &ipv4_address);
 121         if (r == 1) {
 122                 DEBUG(ctx, "%s is an IPv4 address\n", string);
 123
 124                 // Convert to IPv6-mapped address
 125                 address->s6_addr32[0] = htonl(0x0000);
 126                 address->s6_addr32[1] = htonl(0x0000);
 127                 address->s6_addr32[2] = htonl(0xffff);
 128                 address->s6_addr32[3] = ipv4_address.s_addr;
 129
 130                 return 0;
 131         }
 132
 133         DEBUG(ctx, "%s is not an valid IP address\n", string);
 134         return 1;
 135 }
 136
 137 LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
 138                 const char* address_string) {
 139         struct in6_addr start_address;
 140         unsigned int prefix = 0;
 141         char* prefix_string;
 142         int r = 1;
 143
 144         // Make a copy of the string to work on it
 145         char* buffer = strdup(address_string);
 146         address_string = prefix_string = buffer;
 147
 148         // Split address and prefix
 149         address_string = strsep(&prefix_string, "/");
 150
 151         // Did we find a prefix?
 152         if (prefix_string) {
 153                 // Convert prefix to integer
 154                 prefix = strtol(prefix_string, NULL, 10);
 155
 156                 if (prefix) {
 157                         // Parse the address
 158                         r = parse_address(ctx, address_string, &start_address);
 159                 }
 160         }
 161
 162         // Free temporary buffer
 163         free(buffer);
 164
 165         if (r == 0) {
 166                 r = loc_network_new(ctx, network, start_address, prefix);
 167         }
 168
 169         return r;
 170 }
 171
 172 LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
 173         network->refcount++;
 174
 175         return network;
 176 }
 177
 178 static void loc_network_free(struct loc_network* network) {
 179         DEBUG(network->ctx, "Releasing network at %p\n", network);
 180
 181         loc_unref(network->ctx);
 182         free(network);
 183 }
 184
 185 LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
 186         if (--network->refcount > 0)
 187                 return network;
 188
 189         loc_network_free(network);
 190         return NULL;
 191 }
 192
 193 static int format_ipv6_address(struct loc_network* network, char* string, size_t length) {
 194         const char* ret = inet_ntop(AF_INET6, &network->start_address, string, length);
 195         if (!ret)
 196                 return -1;
 197
 198         return 0;
 199 }
 200
 201 static int format_ipv4_address(struct loc_network* network, char* string, size_t length) {
 202         struct in_addr ipv4_address;
 203         ipv4_address.s_addr = network->start_address.s6_addr32[3];
 204
 205         const char* ret = inet_ntop(AF_INET, &ipv4_address, string, length);
 206         if (!ret)
 207                 return -1;
 208
 209         return 0;
 210 }
 211
 212 LOC_EXPORT char* loc_network_str(struct loc_network* network) {
 213         int r;
 214         const size_t length = INET6_ADDRSTRLEN + 4;
 215
 216         char* string = malloc(length);
 217         if (!string)
 218                 return NULL;
 219
 220         int family = loc_network_address_family(network);
 221         switch (family) {
 222                 case AF_INET6:
 223                         r = format_ipv6_address(network, string, length);
 224                         break;
 225
 226                 case AF_INET:
 227                         r = format_ipv4_address(network, string, length);
 228                         break;
 229
 230                 default:
 231                         r = -1;
 232                         break;
 233         }
 234
 235         if (r) {
 236                 ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno));
 237                 free(string);
 238
 239                 return NULL;
 240         }
 241
 242         // Append prefix
 243         sprintf(string + strlen(string), "/%u", network->prefix);
 244
 245         return string;
 246 }
 247
 248 LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
 249         return network->country_code;
 250 }
 251
 252 LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) {
 253         // Country codes must be two characters
 254         if (strlen(country_code) != 2)
 255                 return -EINVAL;
 256
 257         for (unsigned int i = 0; i < 3; i++) {
 258                 network->country_code[i] = country_code[i];
 259         }
 260
 261         return 0;
 262 }
 263
 264 LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
 265         return network->asn;
 266 }
 267
 268 LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
 269         network->asn = asn;
 270
 271         return 0;
 272 }
 273
 274 LOC_EXPORT int loc_network_to_database_v0(struct loc_network* network, struct loc_database_network_v0* dbobj) {
 275         dbobj->prefix = htobe16(network->prefix);
 276
 277         // Add country code
 278         for (unsigned int i = 0; i < 2; i++) {
 279                 dbobj->country_code[i] = network->country_code ? network->country_code[i] : '\0';
 280         }
 281
 282         // Add ASN
 283         dbobj->asn = htobe32(network->asn);
 284
 285         return 0;
 286 }
 287
 288 struct loc_network_tree {
 289         struct loc_ctx* ctx;
 290         int refcount;
 291
 292         struct loc_network_tree_node* root;
 293 };
 294
 295 struct loc_network_tree_node {
 296         struct loc_network_tree_node* zero;
 297         struct loc_network_tree_node* one;
 298
 299         struct loc_network* network;
 300 };
 301
 302 LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
 303         struct loc_network_tree* t = calloc(1, sizeof(*t));
 304         if (!t)
 305                 return -ENOMEM;
 306
 307         t->ctx = loc_ref(ctx);
 308         t->refcount = 1;
 309
 310         // Create the root node
 311         t->root = calloc(1, sizeof(*t->root));
 312
 313         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
 314         *tree = t;
 315         return 0;
 316 }
 317
 318 static int loc_network_tree_node_new(struct loc_network_tree_node** node) {
 319         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
 320         if (!n)
 321                 return -ENOMEM;
 322
 323         n->zero = n->one = NULL;
 324
 325         *node = n;
 326         return 0;
 327 }
 328
 329 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
 330         struct loc_network_tree_node** n;
 331
 332         if (path)
 333                 n = &node->one;
 334         else
 335                 n = &node->zero;
 336
 337         // If the desired node doesn't exist, yet, we will create it
 338         if (*n == NULL) {
 339                 int r = loc_network_tree_node_new(n);
 340                 if (r)
 341                         return NULL;
 342         }
 343
 344         return *n;
 345 }
 346
 347 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address) {
 348         struct loc_network_tree_node* node = tree->root;
 349
 350         for (unsigned int i = 127; i > 0; i--) {
 351                 // Check if the ith bit is one or zero
 352                 node = loc_network_tree_get_node(node, ((address->s6_addr32[i / 32] & (1 << (i % 32))) == 0));
 353         }
 354
 355         return node;
 356 }
 357
 358 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
 359                 int(*filter_callback)(struct loc_network* network, void* data),
 360                 int(*callback)(struct loc_network* network, void* data), void* data) {
 361         int r;
 362
 363         // Finding a network ends the walk here
 364         if (node->network) {
 365                 if (filter_callback) {
 366                         int f = filter_callback(node->network, data);
 367                         if (f < 0)
 368                                 return f;
 369
 370                         // Skip network if filter function returns value greater than zero
 371                         if (f > 0)
 372                                 return 0;
 373                 }
 374
 375                 r = callback(node->network, data);
 376                 if (r)
 377                         return r;
 378         }
 379
 380         // Walk down on the left side of the tree first
 381         if (node->zero) {
 382                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
 383                 if (r)
 384                         return r;
 385         }
 386
 387         // Then walk on the other side
 388         if (node->one) {
 389                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
 390                 if (r)
 391                         return r;
 392         }
 393
 394         return 0;
 395 }
 396
 397 LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
 398                 int(*filter_callback)(struct loc_network* network, void* data),
 399                 int(*callback)(struct loc_network* network, void* data), void* data) {
 400         return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
 401 }
 402
 403 static void loc_network_tree_free_subtree(struct loc_network_tree_node* node) {
 404         if (node->network)
 405                 loc_network_unref(node->network);
 406
 407         if (node->zero)
 408                 loc_network_tree_free_subtree(node->zero);
 409
 410         if (node->one)
 411                 loc_network_tree_free_subtree(node->one);
 412
 413         free(node);
 414 }
 415
 416 static void loc_network_tree_free(struct loc_network_tree* tree) {
 417         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
 418
 419         loc_network_tree_free_subtree(tree->root);
 420
 421         loc_unref(tree->ctx);
 422         free(tree);
 423 }
 424
 425 LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
 426         if (--tree->refcount > 0)
 427                 return tree;
 428
 429         loc_network_tree_free(tree);
 430         return NULL;
 431 }
 432
 433 int __loc_network_tree_dump(struct loc_network* network, void* data) {
 434         DEBUG(network->ctx, "Dumping network at %p\n", network);
 435
 436         char* s = loc_network_str(network);
 437         if (!s)
 438                 return 1;
 439
 440         INFO(network->ctx, "%s\n", s);
 441         free(s);
 442
 443         return 0;
 444 }
 445
 446 LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
 447         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
 448
 449         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
 450 }
 451
 452 LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
 453         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
 454
 455         struct loc_network_tree_node* node = loc_network_tree_get_path(tree, &network->start_address);
 456         if (!node) {
 457                 ERROR(tree->ctx, "Could not find a node\n");
 458                 return -ENOMEM;
 459         }
 460
 461         // Check if node has not been set before
 462         if (node->network) {
 463                 DEBUG(tree->ctx, "There is already a network at this path\n");
 464                 return 1;
 465         }
 466
 467         // Point node to the network
 468         node->network = loc_network_ref(network);
 469
 470         return 0;
 471 }
 472
 473 static int __loc_network_tree_count(struct loc_network* network, void* data) {
 474         size_t* counter = (size_t*)data;
 475
 476         // Increase the counter for each network
 477         counter++;
 478
 479         return 0;
 480 }
 481
 482 LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
 483         size_t counter = 0;
 484
 485         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
 486         if (r)
 487                 return r;
 488
 489         return counter;
 490 }