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