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 <libloc/libloc.h>
  29 #include <libloc/address.h>
  30 #include <libloc/compat.h>
  31 #include <libloc/country.h>
  32 #include <libloc/network.h>
  33 #include <libloc/network-list.h>
  34 #include <libloc/private.h>
  35
  36 struct loc_network {
  37         struct loc_ctx* ctx;
  38         int refcount;
  39
  40         int family;
  41         struct in6_addr first_address;
  42         struct in6_addr last_address;
  43         unsigned int prefix;
  44
  45         char country_code[3];
  46         uint32_t asn;
  47         enum loc_network_flags flags;
  48
  49         char string[INET6_ADDRSTRLEN + 4];
  50 };
  51
  52 LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
  53                 struct in6_addr* address, unsigned int prefix) {
  54         // Validate the prefix
  55         if (!loc_address_valid_prefix(address, prefix)) {
  56                 ERROR(ctx, "Invalid prefix in %s: %u\n", loc_address_str(address), prefix);
  57                 errno = EINVAL;
  58                 return 1;
  59         }
  60
  61         struct loc_network* n = calloc(1, sizeof(*n));
  62         if (!n)
  63                 return 1;
  64
  65         n->ctx = loc_ref(ctx);
  66         n->refcount = 1;
  67
  68         // Store the prefix
  69         if (IN6_IS_ADDR_V4MAPPED(address))
  70                 n->prefix = prefix + 96;
  71         else
  72                 n->prefix = prefix;
  73
  74         // Convert the prefix into a bitmask
  75         struct in6_addr bitmask = loc_prefix_to_bitmask(n->prefix);
  76
  77         // Store the first and last address in the network
  78         n->first_address = loc_address_and(address, &bitmask);
  79         n->last_address  = loc_address_or(&n->first_address, &bitmask);
  80
  81         // Set family
  82         n->family = loc_address_family(&n->first_address);
  83
  84         DEBUG(n->ctx, "Network allocated at %p\n", n);
  85         *network = n;
  86         return 0;
  87 }
  88
  89 LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx,
  90                 struct loc_network** network, const char* string) {
  91         struct in6_addr address;
  92         unsigned int prefix;
  93
  94         // Parse the input
  95         int r = loc_address_parse(&address, &prefix, string);
  96         if (r) {
  97                 ERROR(ctx, "Could not parse network %s: %m\n", string);
  98                 return r;
  99         }
 100
 101         // Create a new network
 102         return loc_network_new(ctx, network, &address, prefix);
 103 }
 104
 105 LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
 106         network->refcount++;
 107
 108         return network;
 109 }
 110
 111 static void loc_network_free(struct loc_network* network) {
 112         DEBUG(network->ctx, "Releasing network at %p\n", network);
 113
 114         loc_unref(network->ctx);
 115         free(network);
 116 }
 117
 118 LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
 119         if (--network->refcount > 0)
 120                 return network;
 121
 122         loc_network_free(network);
 123         return NULL;
 124 }
 125
 126 LOC_EXPORT const char* loc_network_str(struct loc_network* network) {
 127         if (!*network->string) {
 128                 // Format the address
 129                 const char* address = loc_address_str(&network->first_address);
 130                 if (!address)
 131                         return NULL;
 132
 133                 // Fetch the prefix
 134                 unsigned int prefix = loc_network_prefix(network);
 135
 136                 // Format the string
 137                 int r = snprintf(network->string, sizeof(network->string) - 1,
 138                         "%s/%u", address, prefix);
 139                 if (r < 0) {
 140                         ERROR(network->ctx, "Could not format network string: %m\n");
 141                         *network->string = '\0';
 142                         return NULL;
 143                 }
 144         }
 145
 146         return network->string;
 147 }
 148
 149 LOC_EXPORT int loc_network_address_family(struct loc_network* network) {
 150         return network->family;
 151 }
 152
 153 LOC_EXPORT unsigned int loc_network_prefix(struct loc_network* network) {
 154         switch (network->family) {
 155                 case AF_INET6:
 156                         return network->prefix;
 157
 158                 case AF_INET:
 159                         return network->prefix - 96;
 160         }
 161
 162         return 0;
 163 }
 164
 165 LOC_EXPORT const struct in6_addr* loc_network_get_first_address(struct loc_network* network) {
 166         return &network->first_address;
 167 }
 168
 169 LOC_EXPORT const char* loc_network_format_first_address(struct loc_network* network) {
 170         return loc_address_str(&network->first_address);
 171 }
 172
 173 LOC_EXPORT const struct in6_addr* loc_network_get_last_address(struct loc_network* network) {
 174         return &network->last_address;
 175 }
 176
 177 LOC_EXPORT const char* loc_network_format_last_address(struct loc_network* network) {
 178         return loc_address_str(&network->last_address);
 179 }
 180
 181 LOC_EXPORT int loc_network_matches_address(struct loc_network* network, const struct in6_addr* address) {
 182         // Address must be larger than the start address
 183         if (loc_address_cmp(&network->first_address, address) > 0)
 184                 return 0;
 185
 186         // Address must be smaller than the last address
 187         if (loc_address_cmp(&network->last_address, address) < 0)
 188                 return 0;
 189
 190         // The address is inside this network
 191         return 1;
 192 }
 193
 194 LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
 195         return network->country_code;
 196 }
 197
 198 LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) {
 199         // Set empty country code
 200         if (!country_code || !*country_code) {
 201                 *network->country_code = '\0';
 202                 return 0;
 203         }
 204
 205         // Check country code
 206         if (!loc_country_code_is_valid(country_code))
 207                 return -EINVAL;
 208
 209         loc_country_code_copy(network->country_code, country_code);
 210
 211         return 0;
 212 }
 213
 214 LOC_EXPORT int loc_network_matches_country_code(struct loc_network* network, const char* country_code) {
 215         // Search for any special flags
 216         const int flag = loc_country_special_code_to_flag(country_code);
 217
 218         // If we found a flag, we will return whether it is set or not
 219         if (flag)
 220                 return loc_network_has_flag(network, flag);
 221
 222         // Check country code
 223         if (!loc_country_code_is_valid(country_code))
 224                 return -EINVAL;
 225
 226         // Check for an exact match
 227         return (network->country_code[0] == country_code[0])
 228                 && (network->country_code[1] == country_code[1]);
 229 }
 230
 231 LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
 232         return network->asn;
 233 }
 234
 235 LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
 236         network->asn = asn;
 237
 238         return 0;
 239 }
 240
 241 LOC_EXPORT int loc_network_has_flag(struct loc_network* network, uint32_t flag) {
 242         return network->flags & flag;
 243 }
 244
 245 LOC_EXPORT int loc_network_set_flag(struct loc_network* network, uint32_t flag) {
 246         network->flags |= flag;
 247
 248         return 0;
 249 }
 250
 251 LOC_EXPORT int loc_network_cmp(struct loc_network* self, struct loc_network* other) {
 252         // Compare address
 253         int r = loc_address_cmp(&self->first_address, &other->first_address);
 254         if (r)
 255                 return r;
 256
 257         // Compare prefix
 258         if (self->prefix > other->prefix)
 259                 return 1;
 260         else if (self->prefix < other->prefix)
 261                 return -1;
 262
 263         // Both networks are equal
 264         return 0;
 265 }
 266
 267 int loc_network_properties_cmp(struct loc_network* self, struct loc_network* other) {
 268         int r;
 269
 270         // Check country code
 271         r = loc_country_code_cmp(self->country_code, other->country_code);
 272         if (r)
 273                 return r;
 274
 275         // Check ASN
 276         if (self->asn > other->asn)
 277                 return 1;
 278         else if (self->asn < other->asn)
 279                 return -1;
 280
 281         // Check flags
 282         if (self->flags > other->flags)
 283                 return 1;
 284         else if (self->flags < other->flags)
 285                 return -1;
 286
 287         return 0;
 288 }
 289
 290 LOC_EXPORT int loc_network_overlaps(struct loc_network* self, struct loc_network* other) {
 291         // Either of the start addresses must be in the other subnet
 292         if (loc_network_matches_address(self, &other->first_address))
 293                 return 1;
 294
 295         if (loc_network_matches_address(other, &self->first_address))
 296                 return 1;
 297
 298         // Or either of the end addresses is in the other subnet
 299         if (loc_network_matches_address(self, &other->last_address))
 300                 return 1;
 301
 302         if (loc_network_matches_address(other, &self->last_address))
 303                 return 1;
 304
 305         return 0;
 306 }
 307
 308 LOC_EXPORT int loc_network_is_subnet(struct loc_network* self, struct loc_network* other) {
 309         // The prefix must be smaller (this avoids the more complex comparisons later)
 310         if (self->prefix > other->prefix)
 311                 return 0;
 312
 313         // If the start address of the other network is smaller than this network,
 314         // it cannot be a subnet.
 315         if (loc_address_cmp(&self->first_address, &other->first_address) > 0)
 316                 return 0;
 317
 318         // If the end address of the other network is greater than this network,
 319         // it cannot be a subnet.
 320         if (loc_address_cmp(&self->last_address, &other->last_address) < 0)
 321                 return 0;
 322
 323         return 1;
 324 }
 325
 326 LOC_EXPORT int loc_network_subnets(struct loc_network* network,
 327                 struct loc_network** subnet1, struct loc_network** subnet2) {
 328         int r;
 329         *subnet1 = NULL;
 330         *subnet2 = NULL;
 331
 332         // New prefix length
 333         unsigned int prefix = loc_network_prefix(network) + 1;
 334
 335         // Check if the new prefix is valid
 336         if (!loc_address_valid_prefix(&network->first_address, prefix)) {
 337                 ERROR(network->ctx, "Invalid prefix: %d\n", prefix);
 338                 errno = EINVAL;
 339                 return 1;
 340         }
 341
 342         // Create the first half of the network
 343         r = loc_network_new(network->ctx, subnet1, &network->first_address, prefix);
 344         if (r)
 345                 return r;
 346
 347         // The next subnet starts after the first one
 348         struct in6_addr first_address = (*subnet1)->last_address;
 349         loc_address_increment(&first_address);
 350
 351         // Create the second half of the network
 352         r = loc_network_new(network->ctx, subnet2, &first_address, prefix);
 353         if (r)
 354                 return r;
 355
 356         // Copy country code
 357         const char* country_code = loc_network_get_country_code(network);
 358         if (country_code) {
 359                 loc_network_set_country_code(*subnet1, country_code);
 360                 loc_network_set_country_code(*subnet2, country_code);
 361         }
 362
 363         // Copy ASN
 364         uint32_t asn = loc_network_get_asn(network);
 365         if (asn) {
 366                 loc_network_set_asn(*subnet1, asn);
 367                 loc_network_set_asn(*subnet2, asn);
 368         }
 369
 370         // Copy flags
 371         loc_network_set_flag(*subnet1, network->flags);
 372         loc_network_set_flag(*subnet2, network->flags);
 373
 374         return 0;
 375 }
 376
 377 static int __loc_network_exclude(struct loc_network* network,
 378                 struct loc_network* other, struct loc_network_list* list) {
 379         struct loc_network* subnet1 = NULL;
 380         struct loc_network* subnet2 = NULL;
 381
 382         int r = loc_network_subnets(network, &subnet1, &subnet2);
 383         if (r)
 384                 goto ERROR;
 385
 386         if (loc_network_cmp(other, subnet1) == 0) {
 387                 r = loc_network_list_push(list, subnet2);
 388                 if (r)
 389                         goto ERROR;
 390
 391         } else if (loc_network_cmp(other, subnet2) == 0) {
 392                 r = loc_network_list_push(list, subnet1);
 393                 if (r)
 394                         goto ERROR;
 395
 396         } else  if (loc_network_is_subnet(subnet1, other)) {
 397                 r = loc_network_list_push(list, subnet2);
 398                 if (r)
 399                         goto ERROR;
 400
 401                 r = __loc_network_exclude(subnet1, other, list);
 402                 if (r)
 403                         goto ERROR;
 404
 405         } else if (loc_network_is_subnet(subnet2, other)) {
 406                 r = loc_network_list_push(list, subnet1);
 407                 if (r)
 408                         goto ERROR;
 409
 410                 r = __loc_network_exclude(subnet2, other, list);
 411                 if (r)
 412                         goto ERROR;
 413
 414         } else {
 415                 ERROR(network->ctx, "We should never get here\n");
 416                 r = 1;
 417                 goto ERROR;
 418         }
 419
 420 ERROR:
 421         if (subnet1)
 422                 loc_network_unref(subnet1);
 423
 424         if (subnet2)
 425                 loc_network_unref(subnet2);
 426
 427         if (r)
 428                 DEBUG(network->ctx, "%s has failed with %d\n", __FUNCTION__, r);
 429
 430         return r;
 431 }
 432
 433 static int __loc_network_exclude_to_list(struct loc_network* self,
 434                 struct loc_network* other, struct loc_network_list* list) {
 435         // Other must be a subnet of self
 436         if (!loc_network_is_subnet(self, other)) {
 437                 DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self);
 438
 439                 // Exit silently
 440                 return 0;
 441         }
 442
 443         // We cannot perform this operation if both networks equal
 444         if (loc_network_cmp(self, other) == 0) {
 445                 DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other);
 446
 447                 // Exit silently
 448                 return 0;
 449         }
 450
 451         return __loc_network_exclude(self, other, list);
 452 }
 453
 454 LOC_EXPORT struct loc_network_list* loc_network_exclude(
 455                 struct loc_network* self, struct loc_network* other) {
 456         struct loc_network_list* list;
 457
 458         DEBUG(self->ctx, "Returning %s excluding %s...\n",
 459                 loc_network_str(self), loc_network_str(other));
 460
 461         // Create a new list with the result
 462         int r = loc_network_list_new(self->ctx, &list);
 463         if (r) {
 464                 ERROR(self->ctx, "Could not create network list: %d\n", r);
 465
 466                 return NULL;
 467         }
 468
 469         r = __loc_network_exclude_to_list(self, other, list);
 470         if (r) {
 471                 loc_network_list_unref(list);
 472
 473                 return NULL;
 474         }
 475
 476         // Return the result
 477         return list;
 478 }
 479
 480 LOC_EXPORT struct loc_network_list* loc_network_exclude_list(
 481                 struct loc_network* network, struct loc_network_list* list) {
 482         struct loc_network_list* to_check;
 483
 484         // Create a new list with all networks to look at
 485         int r = loc_network_list_new(network->ctx, &to_check);
 486         if (r)
 487                 return NULL;
 488
 489         struct loc_network* subnet = NULL;
 490         struct loc_network_list* subnets = NULL;
 491
 492         for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
 493                 subnet = loc_network_list_get(list, i);
 494
 495                 // Find all excluded networks
 496                 if (!loc_network_list_contains(to_check, subnet)) {
 497                         r = __loc_network_exclude_to_list(network, subnet, to_check);
 498                         if (r) {
 499                                 loc_network_list_unref(to_check);
 500                                 loc_network_unref(subnet);
 501
 502                                 return NULL;
 503                         }
 504                 }
 505
 506                 // Cleanup
 507                 loc_network_unref(subnet);
 508         }
 509
 510         r = loc_network_list_new(network->ctx, &subnets);
 511         if (r) {
 512                 loc_network_list_unref(to_check);
 513                 return NULL;
 514         }
 515
 516         off_t smallest_subnet = 0;
 517
 518         while (!loc_network_list_empty(to_check)) {
 519                 struct loc_network* subnet_to_check = loc_network_list_pop_first(to_check);
 520
 521                 // Check whether the subnet to check is part of the input list
 522                 if (loc_network_list_contains(list, subnet_to_check)) {
 523                         loc_network_unref(subnet_to_check);
 524                         continue;
 525                 }
 526
 527                 // Marks whether this subnet passed all checks
 528                 int passed = 1;
 529
 530                 for (unsigned int i = smallest_subnet; i < loc_network_list_size(list); i++) {
 531                         subnet = loc_network_list_get(list, i);
 532
 533                         // Drop this subnet if is a subnet of another subnet
 534                         if (loc_network_is_subnet(subnet, subnet_to_check)) {
 535                                 passed = 0;
 536                                 loc_network_unref(subnet);
 537                                 break;
 538                         }
 539
 540                         // Break it down if it overlaps
 541                         if (loc_network_overlaps(subnet, subnet_to_check)) {
 542                                 passed = 0;
 543
 544                                 __loc_network_exclude_to_list(subnet_to_check, subnet, to_check);
 545
 546                                 loc_network_unref(subnet);
 547                                 break;
 548                         }
 549
 550                         // If the subnet is strictly greater, we do not need to continue the search
 551                         r = loc_network_cmp(subnet, subnet_to_check);
 552                         if (r > 0) {
 553                                 loc_network_unref(subnet);
 554                                 break;
 555
 556                         // If it is strictly smaller, we can continue the search from here next
 557                         // time because all networks that are to be checked can only be larger
 558                         // than this one.
 559                         } else if (r < 0) {
 560                                 smallest_subnet = i;
 561                         }
 562
 563                         loc_network_unref(subnet);
 564                 }
 565
 566                 if (passed) {
 567                         r = loc_network_list_push(subnets, subnet_to_check);
 568                 }
 569
 570                 loc_network_unref(subnet_to_check);
 571         }
 572
 573         loc_network_list_unref(to_check);
 574
 575         return subnets;
 576 }
 577
 578 int loc_network_merge(struct loc_network** n,
 579                 struct loc_network* n1, struct loc_network* n2) {
 580         struct loc_network* network = NULL;
 581         struct in6_addr address;
 582         int r;
 583
 584         // Reset pointer
 585         *n = NULL;
 586
 587         DEBUG(n1->ctx, "Attempting to merge %s and %s\n", loc_network_str(n1), loc_network_str(n2));
 588
 589         // Family must match
 590         if (n1->family != n2->family)
 591                 return 0;
 592
 593         // The prefix must match, too
 594         if (n1->prefix != n2->prefix)
 595                 return 0;
 596
 597         // Cannot merge ::/0 or 0.0.0.0/0
 598         if (!n1->prefix || !n2->prefix)
 599                 return 0;
 600
 601         const unsigned int prefix = loc_network_prefix(n1);
 602
 603         // How many bits do we need to represent this address?
 604         const size_t bitlength = loc_address_bit_length(&n1->first_address) - 1;
 605
 606         // We cannot shorten this any more
 607         if (bitlength < prefix)
 608                 return 0;
 609
 610         // Increment the last address of the first network
 611         address = n1->last_address;
 612         loc_address_increment(&address);
 613
 614         // If they don't match they are not neighbours
 615         if (loc_address_cmp(&address, &n2->first_address) != 0)
 616                 return 0;
 617
 618         // All properties must match, too
 619         if (loc_network_properties_cmp(n1, n2) != 0)
 620                 return 0;
 621
 622         // Create a new network object
 623         r = loc_network_new(n1->ctx, &network, &n1->first_address, prefix - 1);
 624         if (r)
 625                 return r;
 626
 627         // Copy everything else
 628         loc_country_code_copy(network->country_code, n1->country_code);
 629         network->asn = n1->asn;
 630         network->flags = n1->flags;
 631
 632         // Return pointer
 633         *n = network;
 634
 635         return 0;
 636 }
 637
 638 int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
 639         // Add country code
 640         loc_country_code_copy(dbobj->country_code, network->country_code);
 641
 642         // Add ASN
 643         dbobj->asn = htobe32(network->asn);
 644
 645         // Flags
 646         dbobj->flags = htobe16(network->flags);
 647
 648         return 0;
 649 }
 650
 651 int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network,
 652                 struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) {
 653         char country_code[3] = "\0\0";
 654
 655         // Adjust prefix for IPv4
 656         if (IN6_IS_ADDR_V4MAPPED(address))
 657                 prefix -= 96;
 658
 659         int r = loc_network_new(ctx, network, address, prefix);
 660         if (r) {
 661                 ERROR(ctx, "Could not allocate a new network: %m\n");
 662                 return r;
 663         }
 664
 665         // Import country code
 666         loc_country_code_copy(country_code, dbobj->country_code);
 667
 668         r = loc_network_set_country_code(*network, country_code);
 669         if (r) {
 670                 ERROR(ctx, "Could not set country code: %s\n", country_code);
 671                 return r;
 672         }
 673
 674         // Import ASN
 675         uint32_t asn = be32toh(dbobj->asn);
 676         r = loc_network_set_asn(*network, asn);
 677         if (r) {
 678                 ERROR(ctx, "Could not set ASN: %d\n", asn);
 679                 return r;
 680         }
 681
 682         // Import flags
 683         int flags = be16toh(dbobj->flags);
 684         r = loc_network_set_flag(*network, flags);
 685         if (r) {
 686                 ERROR(ctx, "Could not set flags: %d\n", flags);
 687                 return r;
 688         }
 689
 690         return 0;
 691 }