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(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 LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
  84                 struct in6_addr address, unsigned int prefix) {
  85         // Address cannot be unspecified
  86         if (IN6_IS_ADDR_UNSPECIFIED(&address)) {
  87                 DEBUG(ctx, "Start address is unspecified\n");
  88                 return -EINVAL;
  89         }
  90
  91         // Address cannot be loopback
  92         if (IN6_IS_ADDR_LOOPBACK(&address)) {
  93                 DEBUG(ctx, "Start address is loopback address\n");
  94                 return -EINVAL;
  95         }
  96
  97         // Address cannot be link-local
  98         if (IN6_IS_ADDR_LINKLOCAL(&address)) {
  99                 DEBUG(ctx, "Start address cannot be link-local\n");
 100                 return -EINVAL;
 101         }
 102
 103         // Address cannot be site-local
 104         if (IN6_IS_ADDR_SITELOCAL(&address)) {
 105                 DEBUG(ctx, "Start address cannot be site-local\n");
 106                 return -EINVAL;
 107         }
 108
 109         // Validate the prefix
 110         if (valid_prefix(&address, prefix) != 0) {
 111                 DEBUG(ctx, "Invalid prefix: %u\n", prefix);
 112                 return -EINVAL;
 113         }
 114
 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
 122         // Store the first address in the network
 123         n->start_address = make_start_address(&address, prefix);
 124         n->prefix = prefix;
 125
 126         DEBUG(n->ctx, "Network allocated at %p\n", n);
 127         *network = n;
 128         return 0;
 129 }
 130
 131 static 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
 138 static 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
 169 LOC_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;
 172         unsigned int prefix = 0;
 173         char* prefix_string;
 174         int r = 1;
 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
 183         // Did we find a prefix?
 184         if (prefix_string) {
 185                 // Convert prefix to integer
 186                 prefix = strtol(prefix_string, NULL, 10);
 187
 188                 if (prefix) {
 189                         // Parse the address
 190                         r = parse_address(ctx, address_string, &start_address);
 191
 192                         // Map the prefix to IPv6 if needed
 193                         if (IN6_IS_ADDR_V4MAPPED(&start_address))
 194                                 prefix += 96;
 195                 }
 196         }
 197
 198         // Free temporary buffer
 199         free(buffer);
 200
 201         if (r == 0) {
 202                 r = loc_network_new(ctx, network, start_address, prefix);
 203         }
 204
 205         return r;
 206 }
 207
 208 LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
 209         network->refcount++;
 210
 211         return network;
 212 }
 213
 214 static void loc_network_free(struct loc_network* network) {
 215         DEBUG(network->ctx, "Releasing network at %p\n", network);
 216
 217         loc_unref(network->ctx);
 218         free(network);
 219 }
 220
 221 LOC_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
 229 static 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
 237 static 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
 248 LOC_EXPORT char* loc_network_str(struct loc_network* network) {
 249         int r;
 250         const size_t length = INET6_ADDRSTRLEN + 4;
 251
 252         char* string = malloc(length);
 253         if (!string)
 254                 return NULL;
 255
 256         unsigned int prefix = network->prefix;
 257
 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;
 263
 264                 case AF_INET:
 265                         r = format_ipv4_address(network, string, length);
 266                         prefix -= 96;
 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));
 276                 free(string);
 277
 278                 return NULL;
 279         }
 280
 281         // Append prefix
 282         sprintf(string + strlen(string), "/%u", prefix);
 283
 284         return string;
 285 }
 286
 287 LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
 288         return network->country_code;
 289 }
 290
 291 LOC_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
 303 LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
 304         return network->asn;
 305 }
 306
 307 LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
 308         network->asn = asn;
 309
 310         return 0;
 311 }
 312
 313 LOC_EXPORT int loc_network_to_database_v0(struct loc_network* network, struct loc_database_network_v0* dbobj) {
 314         dbobj->prefix = network->prefix;
 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
 322         dbobj->asn = htobe32(network->asn);
 323
 324         return 0;
 325 }
 326
 327 struct loc_network_tree {
 328         struct loc_ctx* ctx;
 329         int refcount;
 330
 331         struct loc_network_tree_node* root;
 332 };
 333
 334 struct loc_network_tree_node {
 335         struct loc_network_tree_node* zero;
 336         struct loc_network_tree_node* one;
 337
 338         struct loc_network* network;
 339 };
 340
 341 LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
 342         struct loc_network_tree* t = calloc(1, sizeof(*t));
 343         if (!t)
 344                 return -ENOMEM;
 345
 346         t->ctx = loc_ref(ctx);
 347         t->refcount = 1;
 348
 349         // Create the root node
 350         t->root = calloc(1, sizeof(*t->root));
 351
 352         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
 353         *tree = t;
 354         return 0;
 355 }
 356
 357 static int loc_network_tree_node_new(struct loc_network_tree_node** node) {
 358         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
 359         if (!n)
 360                 return -ENOMEM;
 361
 362         n->zero = n->one = NULL;
 363
 364         *node = n;
 365         return 0;
 366 }
 367
 368 static 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)
 372                 n = &node->zero;
 373         else
 374                 n = &node->one;
 375
 376         // If the desired node doesn't exist, yet, we will create it
 377         if (*n == NULL) {
 378                 int r = loc_network_tree_node_new(n);
 379                 if (r)
 380                         return NULL;
 381         }
 382
 383         return *n;
 384 }
 385
 386 static 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
 397 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
 398                 int(*filter_callback)(struct loc_network* network, void* data),
 399                 int(*callback)(struct loc_network* network, void* data), void* data) {
 400         int r;
 401
 402         // Finding a network ends the walk here
 403         if (node->network) {
 404                 if (filter_callback) {
 405                         int f = filter_callback(node->network, data);
 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
 414                 r = callback(node->network, data);
 415                 if (r)
 416                         return r;
 417         }
 418
 419         // Walk down on the left side of the tree first
 420         if (node->zero) {
 421                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
 422                 if (r)
 423                         return r;
 424         }
 425
 426         // Then walk on the other side
 427         if (node->one) {
 428                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
 429                 if (r)
 430                         return r;
 431         }
 432
 433         return 0;
 434 }
 435
 436 LOC_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
 442 static void loc_network_tree_free_subtree(struct loc_network_tree_node* node) {
 443         if (node->network)
 444                 loc_network_unref(node->network);
 445
 446         if (node->zero)
 447                 loc_network_tree_free_subtree(node->zero);
 448
 449         if (node->one)
 450                 loc_network_tree_free_subtree(node->one);
 451
 452         free(node);
 453 }
 454
 455 static void loc_network_tree_free(struct loc_network_tree* tree) {
 456         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
 457
 458         loc_network_tree_free_subtree(tree->root);
 459
 460         loc_unref(tree->ctx);
 461         free(tree);
 462 }
 463
 464 LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
 465         if (--tree->refcount > 0)
 466                 return tree;
 467
 468         loc_network_tree_free(tree);
 469         return NULL;
 470 }
 471
 472 static int __loc_network_tree_dump(struct loc_network* network, void* data) {
 473         DEBUG(network->ctx, "Dumping network at %p\n", network);
 474
 475         char* s = loc_network_str(network);
 476         if (!s)
 477                 return 1;
 478
 479         INFO(network->ctx, "%s\n", s);
 480         free(s);
 481
 482         return 0;
 483 }
 484
 485 LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
 486         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
 487
 488         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
 489 }
 490
 491 LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
 492         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
 493
 494         struct loc_network_tree_node* node = loc_network_tree_get_path(tree, &network->start_address);
 495         if (!node) {
 496                 ERROR(tree->ctx, "Could not find a node\n");
 497                 return -ENOMEM;
 498         }
 499
 500         // Check if node has not been set before
 501         if (node->network) {
 502                 DEBUG(tree->ctx, "There is already a network at this path\n");
 503                 return 1;
 504         }
 505
 506         // Point node to the network
 507         node->network = loc_network_ref(network);
 508
 509         return 0;
 510 }
 511
 512 static int __loc_network_tree_count(struct loc_network* network, void* data) {
 513         size_t* counter = (size_t*)data;
 514
 515         // Increase the counter for each network
 516         counter++;
 517
 518         return 0;
 519 }
 520
 521 LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
 522         size_t counter = 0;
 523
 524         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
 525         if (r)
 526                 return r;
 527
 528         return counter;
 529 }
 530
 531 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
 532         size_t counter = 1;
 533
 534         if (node->zero)
 535                 counter += __loc_network_tree_count_nodes(node->zero);
 536
 537         if (node->one)
 538                 counter += __loc_network_tree_count_nodes(node->one);
 539
 540         return counter;
 541 }
 542
 543 LOC_EXPORT size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
 544         return __loc_network_tree_count_nodes(tree->root);
 545 }