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/network-list.h>
  33 #include <loc/private.h>
  34
  35 struct loc_network {
  36         struct loc_ctx* ctx;
  37         int refcount;
  38
  39         int family;
  40         struct in6_addr first_address;
  41         struct in6_addr last_address;
  42         unsigned int prefix;
  43
  44         char country_code[3];
  45         uint32_t asn;
  46         enum loc_network_flags flags;
  47 };
  48
  49 static int valid_prefix(struct in6_addr* address, unsigned int prefix) {
  50         // The prefix cannot be larger than 128 bits
  51         if (prefix > 128)
  52                 return 1;
  53
  54         // And the prefix cannot be zero
  55         if (prefix == 0)
  56                 return 1;
  57
  58         // For IPv4-mapped addresses the prefix has to be 96 or lager
  59         if (IN6_IS_ADDR_V4MAPPED(address) && prefix <= 96)
  60                 return 1;
  61
  62         return 0;
  63 }
  64
  65 static struct in6_addr prefix_to_bitmask(unsigned int prefix) {
  66         struct in6_addr bitmask;
  67
  68         for (unsigned int i = 0; i < 16; i++)
  69                 bitmask.s6_addr[i] = 0;
  70
  71         for (int i = prefix, j = 0; i > 0; i -= 8, j++) {
  72                 if (i >= 8)
  73                         bitmask.s6_addr[j] = 0xff;
  74                 else
  75                         bitmask.s6_addr[j] = 0xff << (8 - i);
  76         }
  77
  78         return bitmask;
  79 }
  80
  81 static struct in6_addr make_first_address(const struct in6_addr* address, const struct in6_addr* bitmask) {
  82         struct in6_addr a;
  83
  84         // Perform bitwise AND
  85         for (unsigned int i = 0; i < 4; i++)
  86                 a.s6_addr32[i] = address->s6_addr32[i] & bitmask->s6_addr32[i];
  87
  88         return a;
  89 }
  90
  91 static struct in6_addr make_last_address(const struct in6_addr* address, const struct in6_addr* bitmask) {
  92         struct in6_addr a;
  93
  94         // Perform bitwise OR
  95         for (unsigned int i = 0; i < 4; i++)
  96                 a.s6_addr32[i] = address->s6_addr32[i] | ~bitmask->s6_addr32[i];
  97
  98         return a;
  99 }
 100
 101 static struct in6_addr address_increment(const struct in6_addr* address) {
 102         struct in6_addr a = *address;
 103
 104         for (int octet = 15; octet >= 0; octet--) {
 105                 if (a.s6_addr[octet] < 255) {
 106                         a.s6_addr[octet]++;
 107                         break;
 108                 } else {
 109                         a.s6_addr[octet] = 0;
 110                 }
 111         }
 112
 113         return a;
 114 }
 115
 116 LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
 117                 struct in6_addr* address, unsigned int prefix) {
 118         // Address cannot be unspecified
 119         if (IN6_IS_ADDR_UNSPECIFIED(address)) {
 120                 DEBUG(ctx, "Start address is unspecified\n");
 121                 return -EINVAL;
 122         }
 123
 124         // Address cannot be loopback
 125         if (IN6_IS_ADDR_LOOPBACK(address)) {
 126                 DEBUG(ctx, "Start address is loopback address\n");
 127                 return -EINVAL;
 128         }
 129
 130         // Address cannot be link-local
 131         if (IN6_IS_ADDR_LINKLOCAL(address)) {
 132                 DEBUG(ctx, "Start address cannot be link-local\n");
 133                 return -EINVAL;
 134         }
 135
 136         // Address cannot be site-local
 137         if (IN6_IS_ADDR_SITELOCAL(address)) {
 138                 DEBUG(ctx, "Start address cannot be site-local\n");
 139                 return -EINVAL;
 140         }
 141
 142         // Validate the prefix
 143         if (valid_prefix(address, prefix) != 0) {
 144                 DEBUG(ctx, "Invalid prefix: %u\n", prefix);
 145                 return -EINVAL;
 146         }
 147
 148         struct loc_network* n = calloc(1, sizeof(*n));
 149         if (!n)
 150                 return -ENOMEM;
 151
 152         n->ctx = loc_ref(ctx);
 153         n->refcount = 1;
 154
 155         // Store the prefix
 156         n->prefix = prefix;
 157
 158         // Convert the prefix into a bitmask
 159         struct in6_addr bitmask = prefix_to_bitmask(n->prefix);
 160
 161         // Store the first and last address in the network
 162         n->first_address = make_first_address(address, &bitmask);
 163         n->last_address = make_last_address(&n->first_address, &bitmask);
 164
 165         // Set family
 166         if (IN6_IS_ADDR_V4MAPPED(&n->first_address))
 167                 n->family = AF_INET;
 168         else
 169                 n->family = AF_INET6;
 170
 171         DEBUG(n->ctx, "Network allocated at %p\n", n);
 172         *network = n;
 173         return 0;
 174 }
 175
 176 LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
 177                 const char* address_string) {
 178         struct in6_addr first_address;
 179         char* prefix_string;
 180         unsigned int prefix = 128;
 181         int r = -EINVAL;
 182
 183         DEBUG(ctx, "Attempting to parse network %s\n", address_string);
 184
 185         // Make a copy of the string to work on it
 186         char* buffer = strdup(address_string);
 187         address_string = prefix_string = buffer;
 188
 189         // Split address and prefix
 190         address_string = strsep(&prefix_string, "/");
 191
 192         DEBUG(ctx, "  Split into address = %s, prefix = %s\n", address_string, prefix_string);
 193
 194         // Parse the address
 195         r = loc_parse_address(ctx, address_string, &first_address);
 196         if (r) {
 197                 DEBUG(ctx, "The address could not be parsed\n");
 198                 goto FAIL;
 199         }
 200
 201         // If a prefix was given, we will try to parse it
 202         if (prefix_string) {
 203                 // Convert prefix to integer
 204                 prefix = strtol(prefix_string, NULL, 10);
 205
 206                 if (!prefix) {
 207                         DEBUG(ctx, "The prefix was not parsable: %s\n", prefix_string);
 208                         goto FAIL;
 209                 }
 210
 211                 // Map the prefix to IPv6 if needed
 212                 if (IN6_IS_ADDR_V4MAPPED(&first_address))
 213                         prefix += 96;
 214         }
 215
 216 FAIL:
 217         // Free temporary buffer
 218         free(buffer);
 219
 220         // Exit if the parsing was unsuccessful
 221         if (r)
 222                 return r;
 223
 224         // Create a new network
 225         return loc_network_new(ctx, network, &first_address, prefix);
 226 }
 227
 228 LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
 229         network->refcount++;
 230
 231         return network;
 232 }
 233
 234 static void loc_network_free(struct loc_network* network) {
 235         DEBUG(network->ctx, "Releasing network at %p\n", network);
 236
 237         loc_unref(network->ctx);
 238         free(network);
 239 }
 240
 241 LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
 242         if (!network)
 243                 return NULL;
 244
 245         if (--network->refcount > 0)
 246                 return network;
 247
 248         loc_network_free(network);
 249         return NULL;
 250 }
 251
 252 static int format_ipv6_address(const struct in6_addr* address, char* string, size_t length) {
 253         const char* ret = inet_ntop(AF_INET6, address, string, length);
 254         if (!ret)
 255                 return -1;
 256
 257         return 0;
 258 }
 259
 260 static int format_ipv4_address(const struct in6_addr* address, char* string, size_t length) {
 261         struct in_addr ipv4_address;
 262         ipv4_address.s_addr = address->s6_addr32[3];
 263
 264         const char* ret = inet_ntop(AF_INET, &ipv4_address, string, length);
 265         if (!ret)
 266                 return -1;
 267
 268         return 0;
 269 }
 270
 271 LOC_EXPORT char* loc_network_str(struct loc_network* network) {
 272         int r;
 273         const size_t length = INET6_ADDRSTRLEN + 4;
 274
 275         char* string = malloc(length);
 276         if (!string)
 277                 return NULL;
 278
 279         unsigned int prefix = network->prefix;
 280
 281         switch (network->family) {
 282                 case AF_INET6:
 283                         r = format_ipv6_address(&network->first_address, string, length);
 284                         break;
 285
 286                 case AF_INET:
 287                         r = format_ipv4_address(&network->first_address, string, length);
 288                         prefix -= 96;
 289                         break;
 290
 291                 default:
 292                         r = -1;
 293                         break;
 294         }
 295
 296         if (r) {
 297                 ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno));
 298                 free(string);
 299
 300                 return NULL;
 301         }
 302
 303         // Append prefix
 304         sprintf(string + strlen(string), "/%u", prefix);
 305
 306         return string;
 307 }
 308
 309 LOC_EXPORT int loc_network_address_family(struct loc_network* network) {
 310         return network->family;
 311 }
 312
 313 LOC_EXPORT unsigned int loc_network_prefix(struct loc_network* network) {
 314         switch (network->family) {
 315                 case AF_INET6:
 316                         return network->prefix;
 317
 318                 case AF_INET:
 319                         return network->prefix - 96;
 320         }
 321
 322         return 0;
 323 }
 324
 325 static char* loc_network_format_address(struct loc_network* network, const struct in6_addr* address) {
 326         const size_t length = INET6_ADDRSTRLEN;
 327
 328         char* string = malloc(length);
 329         if (!string)
 330                 return NULL;
 331
 332         int r = 0;
 333
 334         switch (network->family) {
 335                 case AF_INET6:
 336                         r = format_ipv6_address(address, string, length);
 337                         break;
 338
 339                 case AF_INET:
 340                         r = format_ipv4_address(address, string, length);
 341                         break;
 342
 343                 default:
 344                         r = -1;
 345                         break;
 346         }
 347
 348         if (r) {
 349                 ERROR(network->ctx, "Could not format IP address to string: %s\n", strerror(errno));
 350                 free(string);
 351
 352                 return NULL;
 353         }
 354
 355         return string;
 356 }
 357
 358 LOC_EXPORT const struct in6_addr* loc_network_get_first_address(struct loc_network* network) {
 359         return &network->first_address;
 360 }
 361
 362 LOC_EXPORT char* loc_network_format_first_address(struct loc_network* network) {
 363         return loc_network_format_address(network, &network->first_address);
 364 }
 365
 366 LOC_EXPORT const struct in6_addr* loc_network_get_last_address(struct loc_network* network) {
 367         return &network->last_address;
 368 }
 369
 370 LOC_EXPORT char* loc_network_format_last_address(struct loc_network* network) {
 371         return loc_network_format_address(network, &network->last_address);
 372 }
 373
 374 LOC_EXPORT int loc_network_match_address(struct loc_network* network, const struct in6_addr* address) {
 375         // Address must be larger than the start address
 376         if (in6_addr_cmp(&network->first_address, address) > 0)
 377                 return 1;
 378
 379         // Address must be smaller than the last address
 380         if (in6_addr_cmp(&network->last_address, address) < 0)
 381                 return 1;
 382
 383         // The address is inside this network
 384         return 0;
 385 }
 386
 387 LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
 388         return network->country_code;
 389 }
 390
 391 LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) {
 392         // Set empty country code
 393         if (!country_code || !*country_code) {
 394                 *network->country_code = '\0';
 395                 return 0;
 396         }
 397
 398         // Check country code
 399         if (!loc_country_code_is_valid(country_code))
 400                 return -EINVAL;
 401
 402         loc_country_code_copy(network->country_code, country_code);
 403
 404         return 0;
 405 }
 406
 407 LOC_EXPORT int loc_network_match_country_code(struct loc_network* network, const char* country_code) {
 408         // Check country code
 409         if (!loc_country_code_is_valid(country_code))
 410                 return -EINVAL;
 411
 412         return (network->country_code[0] == country_code[0])
 413                 && (network->country_code[1] == country_code[1]);
 414 }
 415
 416 LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
 417         return network->asn;
 418 }
 419
 420 LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
 421         network->asn = asn;
 422
 423         return 0;
 424 }
 425
 426 LOC_EXPORT int loc_network_match_asn(struct loc_network* network, uint32_t asn) {
 427         return network->asn == asn;
 428 }
 429
 430 LOC_EXPORT int loc_network_has_flag(struct loc_network* network, uint32_t flag) {
 431         return network->flags & flag;
 432 }
 433
 434 LOC_EXPORT int loc_network_set_flag(struct loc_network* network, uint32_t flag) {
 435         network->flags |= flag;
 436
 437         return 0;
 438 }
 439
 440 LOC_EXPORT int loc_network_match_flag(struct loc_network* network, uint32_t flag) {
 441         return loc_network_has_flag(network, flag);
 442 }
 443
 444 LOC_EXPORT int loc_network_cmp(struct loc_network* self, struct loc_network* other) {
 445         // Compare family
 446         if (self->family > other->family)
 447                 return 1;
 448         else if (self->family < other->family)
 449                 return -1;
 450
 451         // Compare address
 452         int r = in6_addr_cmp(&self->first_address, &other->first_address);
 453         if (r)
 454                 return r;
 455
 456         // Compare prefix
 457         if (self->prefix > other->prefix)
 458                 return 1;
 459         else if (self->prefix < other->prefix)
 460                 return -1;
 461
 462         // Both networks are equal
 463         return 0;
 464 }
 465
 466 LOC_EXPORT int loc_network_eq(struct loc_network* self, struct loc_network* other) {
 467         // Family must be the same
 468         if (self->family != other->family)
 469                 return 0;
 470
 471         // The start address must be the same
 472         if (in6_addr_cmp(&self->first_address, &other->first_address) != 0)
 473                 return 0;
 474
 475         // The prefix length must be the same
 476         if (self->prefix != other->prefix)
 477                 return 0;
 478
 479         return 1;
 480 }
 481
 482 LOC_EXPORT int loc_network_gt(struct loc_network* self, struct loc_network* other) {
 483         // Families must match
 484         if (self->family != other->family)
 485                 return -1;
 486
 487         int r = in6_addr_cmp(&self->first_address, &other->first_address);
 488
 489         switch (r) {
 490                 // Smaller
 491                 case -1:
 492                         return 0;
 493
 494                 // Larger
 495                 case 1:
 496                         return 1;
 497
 498                 default:
 499                         break;
 500         }
 501
 502         if (self->prefix > other->prefix)
 503                 return 1;
 504
 505         // Dunno
 506         return 0;
 507 }
 508
 509 LOC_EXPORT int loc_network_overlaps(struct loc_network* self, struct loc_network* other) {
 510         if (loc_network_match_address(self, &other->first_address) == 0)
 511                 return 1;
 512
 513         if (loc_network_match_address(self, &other->last_address) == 0)
 514                 return 1;
 515
 516         if (loc_network_match_address(other, &self->first_address) == 0)
 517                 return 1;
 518
 519         if (loc_network_match_address(other, &self->last_address) == 0)
 520                 return 1;
 521
 522         return 0;
 523 }
 524
 525 LOC_EXPORT int loc_network_is_subnet(struct loc_network* self, struct loc_network* other) {
 526         // Check family
 527         if (self->family != other->family)
 528                 return 0;
 529
 530         // The prefix must be smaller (this avoids the more complex comparisons later)
 531         if (self->prefix > other->prefix)
 532                 return 0;
 533
 534         // If the start address of the other network is smaller than this network,
 535         // it cannot be a subnet.
 536         if (in6_addr_cmp(&self->first_address, &other->first_address) > 0)
 537                 return 0;
 538
 539         // If the end address of the other network is greater than this network,
 540         // it cannot be a subnet.
 541         if (in6_addr_cmp(&self->last_address, &other->last_address) < 0)
 542                 return 0;
 543
 544         return 1;
 545 }
 546
 547 LOC_EXPORT int loc_network_subnets(struct loc_network* network,
 548                 struct loc_network** subnet1, struct loc_network** subnet2) {
 549         int r;
 550         *subnet1 = NULL;
 551         *subnet2 = NULL;
 552
 553         // New prefix length
 554         unsigned int prefix = network->prefix + 1;
 555
 556         // Check if the new prefix is valid
 557         if (valid_prefix(&network->first_address, prefix))
 558                 return -1;
 559
 560         // Create the first half of the network
 561         r = loc_network_new(network->ctx, subnet1, &network->first_address, prefix);
 562         if (r)
 563                 return r;
 564
 565         // The next subnet starts after the first one
 566         struct in6_addr first_address = address_increment(&(*subnet1)->last_address);
 567
 568         // Create the second half of the network
 569         r = loc_network_new(network->ctx, subnet2, &first_address, prefix);
 570         if (r)
 571                 return r;
 572
 573         // Copy country code
 574         const char* country_code = loc_network_get_country_code(network);
 575         if (country_code) {
 576                 loc_network_set_country_code(*subnet1, country_code);
 577                 loc_network_set_country_code(*subnet2, country_code);
 578         }
 579
 580         // Copy ASN
 581         uint32_t asn = loc_network_get_asn(network);
 582         if (asn) {
 583                 loc_network_set_asn(*subnet1, asn);
 584                 loc_network_set_asn(*subnet2, asn);
 585         }
 586
 587         return 0;
 588 }
 589
 590 static int __loc_network_exclude(struct loc_network* network,
 591                 struct loc_network* other, struct loc_network_list* list) {
 592         struct loc_network* subnet1 = NULL;
 593         struct loc_network* subnet2 = NULL;
 594
 595         int r = loc_network_subnets(network, &subnet1, &subnet2);
 596         if (r)
 597                 goto ERROR;
 598
 599         if (loc_network_eq(other, subnet1)) {
 600                 r = loc_network_list_push(list, subnet2);
 601                 if (r)
 602                         goto ERROR;
 603
 604         } else if (loc_network_eq(other, subnet2)) {
 605                 r = loc_network_list_push(list, subnet1);
 606                 if (r)
 607                         goto ERROR;
 608
 609         } else  if (loc_network_is_subnet(subnet1, other)) {
 610                 r = loc_network_list_push(list, subnet2);
 611                 if (r)
 612                         goto ERROR;
 613
 614                 r = __loc_network_exclude(subnet1, other, list);
 615                 if (r)
 616                         goto ERROR;
 617
 618         } else if (loc_network_is_subnet(subnet2, other)) {
 619                 r = loc_network_list_push(list, subnet1);
 620                 if (r)
 621                         goto ERROR;
 622
 623                 r = __loc_network_exclude(subnet2, other, list);
 624                 if (r)
 625                         goto ERROR;
 626
 627         } else {
 628                 ERROR(network->ctx, "We should never get here\n");
 629                 r = 1;
 630                 goto ERROR;
 631         }
 632
 633 ERROR:
 634         if (subnet1)
 635                 loc_network_unref(subnet1);
 636
 637         if (subnet2)
 638                 loc_network_unref(subnet2);
 639
 640         return r;
 641 }
 642
 643 LOC_EXPORT struct loc_network_list* loc_network_exclude(
 644                 struct loc_network* self, struct loc_network* other) {
 645         struct loc_network_list* list;
 646
 647 #ifdef ENABLE_DEBUG
 648         char* n1 = loc_network_str(self);
 649         char* n2 = loc_network_str(other);
 650
 651         DEBUG(self->ctx, "Returning %s excluding %s...\n", n1, n2);
 652
 653         free(n1);
 654         free(n2);
 655 #endif
 656
 657         // Family must match
 658         if (self->family != other->family) {
 659                 DEBUG(self->ctx, "Family mismatch\n");
 660
 661                 return NULL;
 662         }
 663
 664         // Other must be a subnet of self
 665         if (!loc_network_is_subnet(self, other)) {
 666                 DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self);
 667
 668                 return NULL;
 669         }
 670
 671         // We cannot perform this operation if both networks equal
 672         if (loc_network_eq(self, other)) {
 673                 DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other);
 674
 675                 return NULL;
 676         }
 677
 678         // Create a new list with the result
 679         int r = loc_network_list_new(self->ctx, &list);
 680         if (r) {
 681                 ERROR(self->ctx, "Could not create network list: %d\n", r);
 682                 return NULL;
 683         }
 684
 685         r = __loc_network_exclude(self, other, list);
 686         if (r) {
 687                 loc_network_list_unref(list);
 688
 689                 return NULL;
 690         }
 691
 692         // Return the result
 693         return list;
 694 }
 695
 696 LOC_EXPORT struct loc_network_list* loc_network_exclude_list(
 697                 struct loc_network* network, struct loc_network_list* list) {
 698         struct loc_network_list* to_check;
 699
 700         // Create a new list with all networks to look at
 701         int r = loc_network_list_new(network->ctx, &to_check);
 702         if (r)
 703                 return NULL;
 704
 705         struct loc_network* subnet = NULL;
 706         struct loc_network_list* subnets = NULL;
 707
 708         for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
 709                 subnet = loc_network_list_get(list, i);
 710
 711                 // Find all excluded networks
 712                 struct loc_network_list* excluded = loc_network_exclude(network, subnet);
 713                 if (excluded) {
 714                         // Add them all to the "to check" list
 715                         loc_network_list_merge(to_check, excluded);
 716                         loc_network_list_unref(excluded);
 717                 }
 718
 719                 // Cleanup
 720                 loc_network_unref(subnet);
 721         }
 722
 723         r = loc_network_list_new(network->ctx, &subnets);
 724         if (r) {
 725                 loc_network_list_unref(to_check);
 726                 return NULL;
 727         }
 728
 729         while (!loc_network_list_empty(to_check)) {
 730                 struct loc_network* subnet_to_check = loc_network_list_pop(to_check);
 731
 732                 // Marks whether this subnet passed all checks
 733                 int passed = 1;
 734
 735                 for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
 736                         subnet = loc_network_list_get(list, i);
 737
 738                         // Drop this subnet if is is already in list
 739                         if (loc_network_eq(subnet_to_check, subnet)) {
 740                                 passed = 0;
 741                                 loc_network_unref(subnet);
 742                                 break;
 743                         }
 744
 745                         // Drop this subnet if is a subnet of another subnet
 746                         if (loc_network_is_subnet(subnet_to_check, subnet)) {
 747                                 passed = 0;
 748                                 loc_network_unref(subnet);
 749                                 break;
 750                         }
 751
 752                         // Break it down if it overlaps
 753                         if (loc_network_overlaps(subnet_to_check, subnet)) {
 754                                 passed = 0;
 755
 756                                 struct loc_network_list* excluded = loc_network_exclude(subnet_to_check, subnet);
 757                                 if (excluded) {
 758                                         loc_network_list_merge(to_check, excluded);
 759                                         loc_network_list_unref(excluded);
 760                                 }
 761
 762                                 loc_network_unref(subnet);
 763                                 break;
 764                         }
 765
 766                         loc_network_unref(subnet);
 767                 }
 768
 769                 if (passed) {
 770                         r = loc_network_list_push(subnets, subnet_to_check);
 771                 }
 772
 773                 loc_network_unref(subnet_to_check);
 774         }
 775
 776         loc_network_list_unref(to_check);
 777
 778         // Sort the result
 779         loc_network_list_sort(subnets);
 780
 781         return subnets;
 782 }
 783
 784 LOC_EXPORT int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
 785         // Add country code
 786         loc_country_code_copy(dbobj->country_code, network->country_code);
 787
 788         // Add ASN
 789         dbobj->asn = htobe32(network->asn);
 790
 791         // Flags
 792         dbobj->flags = htobe16(network->flags);
 793
 794         return 0;
 795 }
 796
 797 LOC_EXPORT int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network,
 798                 struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) {
 799         char country_code[3] = "\0\0";
 800
 801         int r = loc_network_new(ctx, network, address, prefix);
 802         if (r) {
 803                 ERROR(ctx, "Could not allocate a new network: %s", strerror(-r));
 804                 return r;
 805         }
 806
 807         // Import country code
 808         loc_country_code_copy(country_code, dbobj->country_code);
 809
 810         r = loc_network_set_country_code(*network, country_code);
 811         if (r) {
 812                 ERROR(ctx, "Could not set country code: %s\n", country_code);
 813                 return r;
 814         }
 815
 816         // Import ASN
 817         uint32_t asn = be32toh(dbobj->asn);
 818         r = loc_network_set_asn(*network, asn);
 819         if (r) {
 820                 ERROR(ctx, "Could not set ASN: %d\n", asn);
 821                 return r;
 822         }
 823
 824         // Import flags
 825         int flags = be16toh(dbobj->flags);
 826         r = loc_network_set_flag(*network, flags);
 827         if (r) {
 828                 ERROR(ctx, "Could not set flags: %d\n", flags);
 829                 return r;
 830         }
 831
 832         return 0;
 833 }
 834
 835 struct loc_network_tree {
 836         struct loc_ctx* ctx;
 837         int refcount;
 838
 839         struct loc_network_tree_node* root;
 840 };
 841
 842 struct loc_network_tree_node {
 843         struct loc_ctx* ctx;
 844         int refcount;
 845
 846         struct loc_network_tree_node* zero;
 847         struct loc_network_tree_node* one;
 848
 849         struct loc_network* network;
 850 };
 851
 852 int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
 853         struct loc_network_tree* t = calloc(1, sizeof(*t));
 854         if (!t)
 855                 return -ENOMEM;
 856
 857         t->ctx = loc_ref(ctx);
 858         t->refcount = 1;
 859
 860         // Create the root node
 861         int r = loc_network_tree_node_new(ctx, &t->root);
 862         if (r) {
 863                 loc_network_tree_unref(t);
 864                 return r;
 865         }
 866
 867         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
 868         *tree = t;
 869         return 0;
 870 }
 871
 872 struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
 873         return loc_network_tree_node_ref(tree->root);
 874 }
 875
 876 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
 877         struct loc_network_tree_node** n;
 878
 879         if (path == 0)
 880                 n = &node->zero;
 881         else
 882                 n = &node->one;
 883
 884         // If the desired node doesn't exist, yet, we will create it
 885         if (*n == NULL) {
 886                 int r = loc_network_tree_node_new(node->ctx, n);
 887                 if (r)
 888                         return NULL;
 889         }
 890
 891         return *n;
 892 }
 893
 894 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
 895         struct loc_network_tree_node* node = tree->root;
 896
 897         for (unsigned int i = 0; i < prefix; i++) {
 898                 // Check if the ith bit is one or zero
 899                 node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i));
 900         }
 901
 902         return node;
 903 }
 904
 905 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
 906                 int(*filter_callback)(struct loc_network* network, void* data),
 907                 int(*callback)(struct loc_network* network, void* data), void* data) {
 908         int r;
 909
 910         // Finding a network ends the walk here
 911         if (node->network) {
 912                 if (filter_callback) {
 913                         int f = filter_callback(node->network, data);
 914                         if (f < 0)
 915                                 return f;
 916
 917                         // Skip network if filter function returns value greater than zero
 918                         if (f > 0)
 919                                 return 0;
 920                 }
 921
 922                 r = callback(node->network, data);
 923                 if (r)
 924                         return r;
 925         }
 926
 927         // Walk down on the left side of the tree first
 928         if (node->zero) {
 929                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
 930                 if (r)
 931                         return r;
 932         }
 933
 934         // Then walk on the other side
 935         if (node->one) {
 936                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
 937                 if (r)
 938                         return r;
 939         }
 940
 941         return 0;
 942 }
 943
 944 int loc_network_tree_walk(struct loc_network_tree* tree,
 945                 int(*filter_callback)(struct loc_network* network, void* data),
 946                 int(*callback)(struct loc_network* network, void* data), void* data) {
 947         return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
 948 }
 949
 950 static void loc_network_tree_free(struct loc_network_tree* tree) {
 951         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
 952
 953         loc_network_tree_node_unref(tree->root);
 954
 955         loc_unref(tree->ctx);
 956         free(tree);
 957 }
 958
 959 struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
 960         if (--tree->refcount > 0)
 961                 return tree;
 962
 963         loc_network_tree_free(tree);
 964         return NULL;
 965 }
 966
 967 static int __loc_network_tree_dump(struct loc_network* network, void* data) {
 968         DEBUG(network->ctx, "Dumping network at %p\n", network);
 969
 970         char* s = loc_network_str(network);
 971         if (!s)
 972                 return 1;
 973
 974         INFO(network->ctx, "%s\n", s);
 975         free(s);
 976
 977         return 0;
 978 }
 979
 980 int loc_network_tree_dump(struct loc_network_tree* tree) {
 981         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
 982
 983         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
 984 }
 985
 986 int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
 987         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
 988
 989         struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
 990                         &network->first_address, network->prefix);
 991         if (!node) {
 992                 ERROR(tree->ctx, "Could not find a node\n");
 993                 return -ENOMEM;
 994         }
 995
 996         // Check if node has not been set before
 997         if (node->network) {
 998                 DEBUG(tree->ctx, "There is already a network at this path\n");
 999                 return -EBUSY;
1000         }
1001
1002         // Point node to the network
1003         node->network = loc_network_ref(network);
1004
1005         return 0;
1006 }
1007
1008 static int __loc_network_tree_count(struct loc_network* network, void* data) {
1009         size_t* counter = (size_t*)data;
1010
1011         // Increase the counter for each network
1012         counter++;
1013
1014         return 0;
1015 }
1016
1017 size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
1018         size_t counter = 0;
1019
1020         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
1021         if (r)
1022                 return r;
1023
1024         return counter;
1025 }
1026
1027 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
1028         size_t counter = 1;
1029
1030         if (node->zero)
1031                 counter += __loc_network_tree_count_nodes(node->zero);
1032
1033         if (node->one)
1034                 counter += __loc_network_tree_count_nodes(node->one);
1035
1036         return counter;
1037 }
1038
1039 size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
1040         return __loc_network_tree_count_nodes(tree->root);
1041 }
1042
1043 int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
1044         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
1045         if (!n)
1046                 return -ENOMEM;
1047
1048         n->ctx = loc_ref(ctx);
1049         n->refcount = 1;
1050
1051         n->zero = n->one = NULL;
1052
1053         DEBUG(n->ctx, "Network node allocated at %p\n", n);
1054         *node = n;
1055         return 0;
1056 }
1057
1058 struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
1059         if (node)
1060                 node->refcount++;
1061
1062         return node;
1063 }
1064
1065 static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
1066         DEBUG(node->ctx, "Releasing network node at %p\n", node);
1067
1068         if (node->network)
1069                 loc_network_unref(node->network);
1070
1071         if (node->zero)
1072                 loc_network_tree_node_unref(node->zero);
1073
1074         if (node->one)
1075                 loc_network_tree_node_unref(node->one);
1076
1077         loc_unref(node->ctx);
1078         free(node);
1079 }
1080
1081 struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
1082         if (!node)
1083                 return NULL;
1084
1085         if (--node->refcount > 0)
1086                 return node;
1087
1088         loc_network_tree_node_free(node);
1089         return NULL;
1090 }
1091
1092 struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
1093         if (index == 0)
1094                 node = node->zero;
1095         else
1096                 node = node->one;
1097
1098         if (!node)
1099                 return NULL;
1100
1101         return loc_network_tree_node_ref(node);
1102 }
1103
1104 int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
1105         return (!!node->network);
1106 }
1107
1108 struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
1109         return loc_network_ref(node->network);
1110 }