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