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