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