src/network.c

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