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 0;
 378
 379         // Address must be smaller than the last address
 380         if (in6_addr_cmp(&network->last_address, address) < 0)
 381                 return 0;
 382
 383         // The address is inside this network
 384         return 1;
 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_overlaps(struct loc_network* self, struct loc_network* other) {
 467         // Either of the start addresses must be in the other subnet
 468         if (loc_network_match_address(self, &other->first_address))
 469                 return 1;
 470
 471         if (loc_network_match_address(other, &self->first_address))
 472                 return 1;
 473
 474         // Or either of the end addresses is in the other subnet
 475         if (loc_network_match_address(self, &other->last_address))
 476                 return 1;
 477
 478         if (loc_network_match_address(other, &self->last_address))
 479                 return 1;
 480
 481         return 0;
 482 }
 483
 484 LOC_EXPORT int loc_network_is_subnet(struct loc_network* self, struct loc_network* other) {
 485         // Check family
 486         if (self->family != other->family)
 487                 return 0;
 488
 489         // The prefix must be smaller (this avoids the more complex comparisons later)
 490         if (self->prefix > other->prefix)
 491                 return 0;
 492
 493         // If the start address of the other network is smaller than this network,
 494         // it cannot be a subnet.
 495         if (in6_addr_cmp(&self->first_address, &other->first_address) > 0)
 496                 return 0;
 497
 498         // If the end address of the other network is greater than this network,
 499         // it cannot be a subnet.
 500         if (in6_addr_cmp(&self->last_address, &other->last_address) < 0)
 501                 return 0;
 502
 503         return 1;
 504 }
 505
 506 LOC_EXPORT int loc_network_subnets(struct loc_network* network,
 507                 struct loc_network** subnet1, struct loc_network** subnet2) {
 508         int r;
 509         *subnet1 = NULL;
 510         *subnet2 = NULL;
 511
 512         // New prefix length
 513         unsigned int prefix = network->prefix + 1;
 514
 515         // Check if the new prefix is valid
 516         if (valid_prefix(&network->first_address, prefix))
 517                 return -1;
 518
 519         // Create the first half of the network
 520         r = loc_network_new(network->ctx, subnet1, &network->first_address, prefix);
 521         if (r)
 522                 return r;
 523
 524         // The next subnet starts after the first one
 525         struct in6_addr first_address = address_increment(&(*subnet1)->last_address);
 526
 527         // Create the second half of the network
 528         r = loc_network_new(network->ctx, subnet2, &first_address, prefix);
 529         if (r)
 530                 return r;
 531
 532         // Copy country code
 533         const char* country_code = loc_network_get_country_code(network);
 534         if (country_code) {
 535                 loc_network_set_country_code(*subnet1, country_code);
 536                 loc_network_set_country_code(*subnet2, country_code);
 537         }
 538
 539         // Copy ASN
 540         uint32_t asn = loc_network_get_asn(network);
 541         if (asn) {
 542                 loc_network_set_asn(*subnet1, asn);
 543                 loc_network_set_asn(*subnet2, asn);
 544         }
 545
 546         return 0;
 547 }
 548
 549 static int __loc_network_exclude(struct loc_network* network,
 550                 struct loc_network* other, struct loc_network_list* list) {
 551         struct loc_network* subnet1 = NULL;
 552         struct loc_network* subnet2 = NULL;
 553
 554         int r = loc_network_subnets(network, &subnet1, &subnet2);
 555         if (r)
 556                 goto ERROR;
 557
 558         if (loc_network_cmp(other, subnet1) == 0) {
 559                 r = loc_network_list_push(list, subnet2);
 560                 if (r)
 561                         goto ERROR;
 562
 563         } else if (loc_network_cmp(other, subnet2) == 0) {
 564                 r = loc_network_list_push(list, subnet1);
 565                 if (r)
 566                         goto ERROR;
 567
 568         } else  if (loc_network_is_subnet(subnet1, other)) {
 569                 r = loc_network_list_push(list, subnet2);
 570                 if (r)
 571                         goto ERROR;
 572
 573                 r = __loc_network_exclude(subnet1, other, list);
 574                 if (r)
 575                         goto ERROR;
 576
 577         } else if (loc_network_is_subnet(subnet2, other)) {
 578                 r = loc_network_list_push(list, subnet1);
 579                 if (r)
 580                         goto ERROR;
 581
 582                 r = __loc_network_exclude(subnet2, other, list);
 583                 if (r)
 584                         goto ERROR;
 585
 586         } else {
 587                 ERROR(network->ctx, "We should never get here\n");
 588                 r = 1;
 589                 goto ERROR;
 590         }
 591
 592 ERROR:
 593         if (subnet1)
 594                 loc_network_unref(subnet1);
 595
 596         if (subnet2)
 597                 loc_network_unref(subnet2);
 598
 599         return r;
 600 }
 601
 602 static int __loc_network_exclude_to_list(struct loc_network* self,
 603                 struct loc_network* other, struct loc_network_list* list) {
 604         // Family must match
 605         if (self->family != other->family) {
 606                 DEBUG(self->ctx, "Family mismatch\n");
 607
 608                 return 1;
 609         }
 610
 611         // Other must be a subnet of self
 612         if (!loc_network_is_subnet(self, other)) {
 613                 DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self);
 614
 615                 return 1;
 616         }
 617
 618         // We cannot perform this operation if both networks equal
 619         if (loc_network_cmp(self, other) == 0) {
 620                 DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other);
 621
 622                 return 1;
 623         }
 624
 625         return __loc_network_exclude(self, other, list);
 626 }
 627
 628 LOC_EXPORT struct loc_network_list* loc_network_exclude(
 629                 struct loc_network* self, struct loc_network* other) {
 630         struct loc_network_list* list;
 631
 632 #ifdef ENABLE_DEBUG
 633         char* n1 = loc_network_str(self);
 634         char* n2 = loc_network_str(other);
 635
 636         DEBUG(self->ctx, "Returning %s excluding %s...\n", n1, n2);
 637
 638         free(n1);
 639         free(n2);
 640 #endif
 641
 642         // Create a new list with the result
 643         int r = loc_network_list_new(self->ctx, &list);
 644         if (r) {
 645                 ERROR(self->ctx, "Could not create network list: %d\n", r);
 646
 647                 return NULL;
 648         }
 649
 650         r = __loc_network_exclude_to_list(self, other, list);
 651         if (r) {
 652                 loc_network_list_unref(list);
 653
 654                 return NULL;
 655         }
 656
 657         // Return the result
 658         return list;
 659 }
 660
 661 LOC_EXPORT struct loc_network_list* loc_network_exclude_list(
 662                 struct loc_network* network, struct loc_network_list* list) {
 663         struct loc_network_list* to_check;
 664
 665         // Create a new list with all networks to look at
 666         int r = loc_network_list_new(network->ctx, &to_check);
 667         if (r)
 668                 return NULL;
 669
 670         struct loc_network* subnet = NULL;
 671         struct loc_network_list* subnets = NULL;
 672
 673         for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
 674                 subnet = loc_network_list_get(list, i);
 675
 676                 // Find all excluded networks
 677                 if (!loc_network_list_contains(to_check, subnet)) {
 678                         r = __loc_network_exclude_to_list(network, subnet, to_check);
 679                         if (r) {
 680                                 loc_network_list_unref(to_check);
 681                                 loc_network_unref(subnet);
 682
 683                                 return NULL;
 684                         }
 685                 }
 686
 687                 // Cleanup
 688                 loc_network_unref(subnet);
 689         }
 690
 691         r = loc_network_list_new(network->ctx, &subnets);
 692         if (r) {
 693                 loc_network_list_unref(to_check);
 694                 return NULL;
 695         }
 696
 697         while (!loc_network_list_empty(to_check)) {
 698                 struct loc_network* subnet_to_check = loc_network_list_pop(to_check);
 699
 700                 // Marks whether this subnet passed all checks
 701                 int passed = 1;
 702
 703                 for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
 704                         subnet = loc_network_list_get(list, i);
 705
 706                         // Drop this subnet if is is already in list
 707                         if (loc_network_cmp(subnet_to_check, subnet) == 0) {
 708                                 passed = 0;
 709                                 loc_network_unref(subnet);
 710                                 break;
 711                         }
 712
 713                         // Drop this subnet if is a subnet of another subnet
 714                         if (loc_network_is_subnet(subnet_to_check, subnet)) {
 715                                 passed = 0;
 716                                 loc_network_unref(subnet);
 717                                 break;
 718                         }
 719
 720                         // Break it down if it overlaps
 721                         if (loc_network_overlaps(subnet_to_check, subnet)) {
 722                                 passed = 0;
 723
 724                                 struct loc_network_list* excluded = loc_network_exclude(subnet_to_check, subnet);
 725                                 if (excluded) {
 726                                         loc_network_list_merge(to_check, excluded);
 727                                         loc_network_list_unref(excluded);
 728                                 }
 729
 730                                 loc_network_unref(subnet);
 731                                 break;
 732                         }
 733
 734                         loc_network_unref(subnet);
 735                 }
 736
 737                 if (passed) {
 738                         r = loc_network_list_push(subnets, subnet_to_check);
 739                 }
 740
 741                 loc_network_unref(subnet_to_check);
 742         }
 743
 744         loc_network_list_unref(to_check);
 745
 746         // Sort the result
 747         loc_network_list_sort(subnets);
 748
 749         return subnets;
 750 }
 751
 752 LOC_EXPORT int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
 753         // Add country code
 754         loc_country_code_copy(dbobj->country_code, network->country_code);
 755
 756         // Add ASN
 757         dbobj->asn = htobe32(network->asn);
 758
 759         // Flags
 760         dbobj->flags = htobe16(network->flags);
 761
 762         return 0;
 763 }
 764
 765 LOC_EXPORT int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network,
 766                 struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) {
 767         char country_code[3] = "\0\0";
 768
 769         int r = loc_network_new(ctx, network, address, prefix);
 770         if (r) {
 771                 ERROR(ctx, "Could not allocate a new network: %s", strerror(-r));
 772                 return r;
 773         }
 774
 775         // Import country code
 776         loc_country_code_copy(country_code, dbobj->country_code);
 777
 778         r = loc_network_set_country_code(*network, country_code);
 779         if (r) {
 780                 ERROR(ctx, "Could not set country code: %s\n", country_code);
 781                 return r;
 782         }
 783
 784         // Import ASN
 785         uint32_t asn = be32toh(dbobj->asn);
 786         r = loc_network_set_asn(*network, asn);
 787         if (r) {
 788                 ERROR(ctx, "Could not set ASN: %d\n", asn);
 789                 return r;
 790         }
 791
 792         // Import flags
 793         int flags = be16toh(dbobj->flags);
 794         r = loc_network_set_flag(*network, flags);
 795         if (r) {
 796                 ERROR(ctx, "Could not set flags: %d\n", flags);
 797                 return r;
 798         }
 799
 800         return 0;
 801 }
 802
 803 struct loc_network_tree {
 804         struct loc_ctx* ctx;
 805         int refcount;
 806
 807         struct loc_network_tree_node* root;
 808 };
 809
 810 struct loc_network_tree_node {
 811         struct loc_ctx* ctx;
 812         int refcount;
 813
 814         struct loc_network_tree_node* zero;
 815         struct loc_network_tree_node* one;
 816
 817         struct loc_network* network;
 818 };
 819
 820 int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
 821         struct loc_network_tree* t = calloc(1, sizeof(*t));
 822         if (!t)
 823                 return -ENOMEM;
 824
 825         t->ctx = loc_ref(ctx);
 826         t->refcount = 1;
 827
 828         // Create the root node
 829         int r = loc_network_tree_node_new(ctx, &t->root);
 830         if (r) {
 831                 loc_network_tree_unref(t);
 832                 return r;
 833         }
 834
 835         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
 836         *tree = t;
 837         return 0;
 838 }
 839
 840 struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
 841         return loc_network_tree_node_ref(tree->root);
 842 }
 843
 844 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
 845         struct loc_network_tree_node** n;
 846
 847         if (path == 0)
 848                 n = &node->zero;
 849         else
 850                 n = &node->one;
 851
 852         // If the desired node doesn't exist, yet, we will create it
 853         if (*n == NULL) {
 854                 int r = loc_network_tree_node_new(node->ctx, n);
 855                 if (r)
 856                         return NULL;
 857         }
 858
 859         return *n;
 860 }
 861
 862 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
 863         struct loc_network_tree_node* node = tree->root;
 864
 865         for (unsigned int i = 0; i < prefix; i++) {
 866                 // Check if the ith bit is one or zero
 867                 node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i));
 868         }
 869
 870         return node;
 871 }
 872
 873 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
 874                 int(*filter_callback)(struct loc_network* network, void* data),
 875                 int(*callback)(struct loc_network* network, void* data), void* data) {
 876         int r;
 877
 878         // Finding a network ends the walk here
 879         if (node->network) {
 880                 if (filter_callback) {
 881                         int f = filter_callback(node->network, data);
 882                         if (f < 0)
 883                                 return f;
 884
 885                         // Skip network if filter function returns value greater than zero
 886                         if (f > 0)
 887                                 return 0;
 888                 }
 889
 890                 r = callback(node->network, data);
 891                 if (r)
 892                         return r;
 893         }
 894
 895         // Walk down on the left side of the tree first
 896         if (node->zero) {
 897                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
 898                 if (r)
 899                         return r;
 900         }
 901
 902         // Then walk on the other side
 903         if (node->one) {
 904                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
 905                 if (r)
 906                         return r;
 907         }
 908
 909         return 0;
 910 }
 911
 912 int loc_network_tree_walk(struct loc_network_tree* tree,
 913                 int(*filter_callback)(struct loc_network* network, void* data),
 914                 int(*callback)(struct loc_network* network, void* data), void* data) {
 915         return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
 916 }
 917
 918 static void loc_network_tree_free(struct loc_network_tree* tree) {
 919         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
 920
 921         loc_network_tree_node_unref(tree->root);
 922
 923         loc_unref(tree->ctx);
 924         free(tree);
 925 }
 926
 927 struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
 928         if (--tree->refcount > 0)
 929                 return tree;
 930
 931         loc_network_tree_free(tree);
 932         return NULL;
 933 }
 934
 935 static int __loc_network_tree_dump(struct loc_network* network, void* data) {
 936         DEBUG(network->ctx, "Dumping network at %p\n", network);
 937
 938         char* s = loc_network_str(network);
 939         if (!s)
 940                 return 1;
 941
 942         INFO(network->ctx, "%s\n", s);
 943         free(s);
 944
 945         return 0;
 946 }
 947
 948 int loc_network_tree_dump(struct loc_network_tree* tree) {
 949         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
 950
 951         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
 952 }
 953
 954 int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
 955         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
 956
 957         struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
 958                         &network->first_address, network->prefix);
 959         if (!node) {
 960                 ERROR(tree->ctx, "Could not find a node\n");
 961                 return -ENOMEM;
 962         }
 963
 964         // Check if node has not been set before
 965         if (node->network) {
 966                 DEBUG(tree->ctx, "There is already a network at this path\n");
 967                 return -EBUSY;
 968         }
 969
 970         // Point node to the network
 971         node->network = loc_network_ref(network);
 972
 973         return 0;
 974 }
 975
 976 static int __loc_network_tree_count(struct loc_network* network, void* data) {
 977         size_t* counter = (size_t*)data;
 978
 979         // Increase the counter for each network
 980         counter++;
 981
 982         return 0;
 983 }
 984
 985 size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
 986         size_t counter = 0;
 987
 988         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
 989         if (r)
 990                 return r;
 991
 992         return counter;
 993 }
 994
 995 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
 996         size_t counter = 1;
 997
 998         if (node->zero)
 999                 counter += __loc_network_tree_count_nodes(node->zero);
1000
1001         if (node->one)
1002                 counter += __loc_network_tree_count_nodes(node->one);
1003
1004         return counter;
1005 }
1006
1007 size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
1008         return __loc_network_tree_count_nodes(tree->root);
1009 }
1010
1011 int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
1012         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
1013         if (!n)
1014                 return -ENOMEM;
1015
1016         n->ctx = loc_ref(ctx);
1017         n->refcount = 1;
1018
1019         n->zero = n->one = NULL;
1020
1021         DEBUG(n->ctx, "Network node allocated at %p\n", n);
1022         *node = n;
1023         return 0;
1024 }
1025
1026 struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
1027         if (node)
1028                 node->refcount++;
1029
1030         return node;
1031 }
1032
1033 static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
1034         DEBUG(node->ctx, "Releasing network node at %p\n", node);
1035
1036         if (node->network)
1037                 loc_network_unref(node->network);
1038
1039         if (node->zero)
1040                 loc_network_tree_node_unref(node->zero);
1041
1042         if (node->one)
1043                 loc_network_tree_node_unref(node->one);
1044
1045         loc_unref(node->ctx);
1046         free(node);
1047 }
1048
1049 struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
1050         if (!node)
1051                 return NULL;
1052
1053         if (--node->refcount > 0)
1054                 return node;
1055
1056         loc_network_tree_node_free(node);
1057         return NULL;
1058 }
1059
1060 struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
1061         if (index == 0)
1062                 node = node->zero;
1063         else
1064                 node = node->one;
1065
1066         if (!node)
1067                 return NULL;
1068
1069         return loc_network_tree_node_ref(node);
1070 }
1071
1072 int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
1073         return (!!node->network);
1074 }
1075
1076 struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
1077         return loc_network_ref(node->network);
1078 }