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