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 static int __loc_network_exclude_to_list(struct loc_network* self,
 644                 struct loc_network* other, struct loc_network_list* list) {
 645         // Family must match
 646         if (self->family != other->family) {
 647                 DEBUG(self->ctx, "Family mismatch\n");
 648
 649                 return 1;
 650         }
 651
 652         // Other must be a subnet of self
 653         if (!loc_network_is_subnet(self, other)) {
 654                 DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self);
 655
 656                 return 1;
 657         }
 658
 659         // We cannot perform this operation if both networks equal
 660         if (loc_network_eq(self, other)) {
 661                 DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other);
 662
 663                 return 1;
 664         }
 665
 666         return __loc_network_exclude(self, other, list);
 667 }
 668
 669 LOC_EXPORT struct loc_network_list* loc_network_exclude(
 670                 struct loc_network* self, struct loc_network* other) {
 671         struct loc_network_list* list;
 672
 673 #ifdef ENABLE_DEBUG
 674         char* n1 = loc_network_str(self);
 675         char* n2 = loc_network_str(other);
 676
 677         DEBUG(self->ctx, "Returning %s excluding %s...\n", n1, n2);
 678
 679         free(n1);
 680         free(n2);
 681 #endif
 682
 683         // Create a new list with the result
 684         int r = loc_network_list_new(self->ctx, &list);
 685         if (r) {
 686                 ERROR(self->ctx, "Could not create network list: %d\n", r);
 687
 688                 return NULL;
 689         }
 690
 691         r = __loc_network_exclude_to_list(self, other, list);
 692         if (r) {
 693                 loc_network_list_unref(list);
 694
 695                 return NULL;
 696         }
 697
 698         // Return the result
 699         return list;
 700 }
 701
 702 LOC_EXPORT struct loc_network_list* loc_network_exclude_list(
 703                 struct loc_network* network, struct loc_network_list* list) {
 704         struct loc_network_list* to_check;
 705
 706         // Create a new list with all networks to look at
 707         int r = loc_network_list_new(network->ctx, &to_check);
 708         if (r)
 709                 return NULL;
 710
 711         struct loc_network* subnet = NULL;
 712         struct loc_network_list* subnets = NULL;
 713
 714         for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
 715                 subnet = loc_network_list_get(list, i);
 716
 717                 // Find all excluded networks
 718                 if (!loc_network_list_contains(to_check, subnet)) {
 719                         r = __loc_network_exclude_to_list(network, subnet, to_check);
 720                         if (r) {
 721                                 loc_network_list_unref(to_check);
 722                                 loc_network_unref(subnet);
 723
 724                                 return NULL;
 725                         }
 726                 }
 727
 728                 // Cleanup
 729                 loc_network_unref(subnet);
 730         }
 731
 732         r = loc_network_list_new(network->ctx, &subnets);
 733         if (r) {
 734                 loc_network_list_unref(to_check);
 735                 return NULL;
 736         }
 737
 738         while (!loc_network_list_empty(to_check)) {
 739                 struct loc_network* subnet_to_check = loc_network_list_pop(to_check);
 740
 741                 // Marks whether this subnet passed all checks
 742                 int passed = 1;
 743
 744                 for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
 745                         subnet = loc_network_list_get(list, i);
 746
 747                         // Drop this subnet if is is already in list
 748                         if (loc_network_eq(subnet_to_check, subnet)) {
 749                                 passed = 0;
 750                                 loc_network_unref(subnet);
 751                                 break;
 752                         }
 753
 754                         // Drop this subnet if is a subnet of another subnet
 755                         if (loc_network_is_subnet(subnet_to_check, subnet)) {
 756                                 passed = 0;
 757                                 loc_network_unref(subnet);
 758                                 break;
 759                         }
 760
 761                         // Break it down if it overlaps
 762                         if (loc_network_overlaps(subnet_to_check, subnet)) {
 763                                 passed = 0;
 764
 765                                 struct loc_network_list* excluded = loc_network_exclude(subnet_to_check, subnet);
 766                                 if (excluded) {
 767                                         loc_network_list_merge(to_check, excluded);
 768                                         loc_network_list_unref(excluded);
 769                                 }
 770
 771                                 loc_network_unref(subnet);
 772                                 break;
 773                         }
 774
 775                         loc_network_unref(subnet);
 776                 }
 777
 778                 if (passed) {
 779                         r = loc_network_list_push(subnets, subnet_to_check);
 780                 }
 781
 782                 loc_network_unref(subnet_to_check);
 783         }
 784
 785         loc_network_list_unref(to_check);
 786
 787         // Sort the result
 788         loc_network_list_sort(subnets);
 789
 790         return subnets;
 791 }
 792
 793 LOC_EXPORT int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
 794         // Add country code
 795         loc_country_code_copy(dbobj->country_code, network->country_code);
 796
 797         // Add ASN
 798         dbobj->asn = htobe32(network->asn);
 799
 800         // Flags
 801         dbobj->flags = htobe16(network->flags);
 802
 803         return 0;
 804 }
 805
 806 LOC_EXPORT int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network,
 807                 struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) {
 808         char country_code[3] = "\0\0";
 809
 810         int r = loc_network_new(ctx, network, address, prefix);
 811         if (r) {
 812                 ERROR(ctx, "Could not allocate a new network: %s", strerror(-r));
 813                 return r;
 814         }
 815
 816         // Import country code
 817         loc_country_code_copy(country_code, dbobj->country_code);
 818
 819         r = loc_network_set_country_code(*network, country_code);
 820         if (r) {
 821                 ERROR(ctx, "Could not set country code: %s\n", country_code);
 822                 return r;
 823         }
 824
 825         // Import ASN
 826         uint32_t asn = be32toh(dbobj->asn);
 827         r = loc_network_set_asn(*network, asn);
 828         if (r) {
 829                 ERROR(ctx, "Could not set ASN: %d\n", asn);
 830                 return r;
 831         }
 832
 833         // Import flags
 834         int flags = be16toh(dbobj->flags);
 835         r = loc_network_set_flag(*network, flags);
 836         if (r) {
 837                 ERROR(ctx, "Could not set flags: %d\n", flags);
 838                 return r;
 839         }
 840
 841         return 0;
 842 }
 843
 844 struct loc_network_tree {
 845         struct loc_ctx* ctx;
 846         int refcount;
 847
 848         struct loc_network_tree_node* root;
 849 };
 850
 851 struct loc_network_tree_node {
 852         struct loc_ctx* ctx;
 853         int refcount;
 854
 855         struct loc_network_tree_node* zero;
 856         struct loc_network_tree_node* one;
 857
 858         struct loc_network* network;
 859 };
 860
 861 int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
 862         struct loc_network_tree* t = calloc(1, sizeof(*t));
 863         if (!t)
 864                 return -ENOMEM;
 865
 866         t->ctx = loc_ref(ctx);
 867         t->refcount = 1;
 868
 869         // Create the root node
 870         int r = loc_network_tree_node_new(ctx, &t->root);
 871         if (r) {
 872                 loc_network_tree_unref(t);
 873                 return r;
 874         }
 875
 876         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
 877         *tree = t;
 878         return 0;
 879 }
 880
 881 struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
 882         return loc_network_tree_node_ref(tree->root);
 883 }
 884
 885 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
 886         struct loc_network_tree_node** n;
 887
 888         if (path == 0)
 889                 n = &node->zero;
 890         else
 891                 n = &node->one;
 892
 893         // If the desired node doesn't exist, yet, we will create it
 894         if (*n == NULL) {
 895                 int r = loc_network_tree_node_new(node->ctx, n);
 896                 if (r)
 897                         return NULL;
 898         }
 899
 900         return *n;
 901 }
 902
 903 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
 904         struct loc_network_tree_node* node = tree->root;
 905
 906         for (unsigned int i = 0; i < prefix; i++) {
 907                 // Check if the ith bit is one or zero
 908                 node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i));
 909         }
 910
 911         return node;
 912 }
 913
 914 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
 915                 int(*filter_callback)(struct loc_network* network, void* data),
 916                 int(*callback)(struct loc_network* network, void* data), void* data) {
 917         int r;
 918
 919         // Finding a network ends the walk here
 920         if (node->network) {
 921                 if (filter_callback) {
 922                         int f = filter_callback(node->network, data);
 923                         if (f < 0)
 924                                 return f;
 925
 926                         // Skip network if filter function returns value greater than zero
 927                         if (f > 0)
 928                                 return 0;
 929                 }
 930
 931                 r = callback(node->network, data);
 932                 if (r)
 933                         return r;
 934         }
 935
 936         // Walk down on the left side of the tree first
 937         if (node->zero) {
 938                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
 939                 if (r)
 940                         return r;
 941         }
 942
 943         // Then walk on the other side
 944         if (node->one) {
 945                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
 946                 if (r)
 947                         return r;
 948         }
 949
 950         return 0;
 951 }
 952
 953 int loc_network_tree_walk(struct loc_network_tree* tree,
 954                 int(*filter_callback)(struct loc_network* network, void* data),
 955                 int(*callback)(struct loc_network* network, void* data), void* data) {
 956         return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
 957 }
 958
 959 static void loc_network_tree_free(struct loc_network_tree* tree) {
 960         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
 961
 962         loc_network_tree_node_unref(tree->root);
 963
 964         loc_unref(tree->ctx);
 965         free(tree);
 966 }
 967
 968 struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
 969         if (--tree->refcount > 0)
 970                 return tree;
 971
 972         loc_network_tree_free(tree);
 973         return NULL;
 974 }
 975
 976 static int __loc_network_tree_dump(struct loc_network* network, void* data) {
 977         DEBUG(network->ctx, "Dumping network at %p\n", network);
 978
 979         char* s = loc_network_str(network);
 980         if (!s)
 981                 return 1;
 982
 983         INFO(network->ctx, "%s\n", s);
 984         free(s);
 985
 986         return 0;
 987 }
 988
 989 int loc_network_tree_dump(struct loc_network_tree* tree) {
 990         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
 991
 992         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
 993 }
 994
 995 int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
 996         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
 997
 998         struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
 999                         &network->first_address, network->prefix);
1000         if (!node) {
1001                 ERROR(tree->ctx, "Could not find a node\n");
1002                 return -ENOMEM;
1003         }
1004
1005         // Check if node has not been set before
1006         if (node->network) {
1007                 DEBUG(tree->ctx, "There is already a network at this path\n");
1008                 return -EBUSY;
1009         }
1010
1011         // Point node to the network
1012         node->network = loc_network_ref(network);
1013
1014         return 0;
1015 }
1016
1017 static int __loc_network_tree_count(struct loc_network* network, void* data) {
1018         size_t* counter = (size_t*)data;
1019
1020         // Increase the counter for each network
1021         counter++;
1022
1023         return 0;
1024 }
1025
1026 size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
1027         size_t counter = 0;
1028
1029         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
1030         if (r)
1031                 return r;
1032
1033         return counter;
1034 }
1035
1036 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
1037         size_t counter = 1;
1038
1039         if (node->zero)
1040                 counter += __loc_network_tree_count_nodes(node->zero);
1041
1042         if (node->one)
1043                 counter += __loc_network_tree_count_nodes(node->one);
1044
1045         return counter;
1046 }
1047
1048 size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
1049         return __loc_network_tree_count_nodes(tree->root);
1050 }
1051
1052 int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
1053         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
1054         if (!n)
1055                 return -ENOMEM;
1056
1057         n->ctx = loc_ref(ctx);
1058         n->refcount = 1;
1059
1060         n->zero = n->one = NULL;
1061
1062         DEBUG(n->ctx, "Network node allocated at %p\n", n);
1063         *node = n;
1064         return 0;
1065 }
1066
1067 struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
1068         if (node)
1069                 node->refcount++;
1070
1071         return node;
1072 }
1073
1074 static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
1075         DEBUG(node->ctx, "Releasing network node at %p\n", node);
1076
1077         if (node->network)
1078                 loc_network_unref(node->network);
1079
1080         if (node->zero)
1081                 loc_network_tree_node_unref(node->zero);
1082
1083         if (node->one)
1084                 loc_network_tree_node_unref(node->one);
1085
1086         loc_unref(node->ctx);
1087         free(node);
1088 }
1089
1090 struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
1091         if (!node)
1092                 return NULL;
1093
1094         if (--node->refcount > 0)
1095                 return node;
1096
1097         loc_network_tree_node_free(node);
1098         return NULL;
1099 }
1100
1101 struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
1102         if (index == 0)
1103                 node = node->zero;
1104         else
1105                 node = node->one;
1106
1107         if (!node)
1108                 return NULL;
1109
1110         return loc_network_tree_node_ref(node);
1111 }
1112
1113 int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
1114         return (!!node->network);
1115 }
1116
1117 struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
1118         return loc_network_ref(node->network);
1119 }