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