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/private.h>
  33
  34 struct loc_network {
  35         struct loc_ctx* ctx;
  36         int refcount;
  37
  38         int family;
  39         struct in6_addr first_address;
  40         struct in6_addr last_address;
  41         unsigned int prefix;
  42
  43         char country_code[3];
  44         uint32_t asn;
  45         enum loc_network_flags flags;
  46 };
  47
  48 static int valid_prefix(struct in6_addr* address, unsigned int prefix) {
  49         // The prefix cannot be larger than 128 bits
  50         if (prefix > 128)
  51                 return 1;
  52
  53         // And the prefix cannot be zero
  54         if (prefix == 0)
  55                 return 1;
  56
  57         // For IPv4-mapped addresses the prefix has to be 96 or lager
  58         if (IN6_IS_ADDR_V4MAPPED(address) && prefix <= 96)
  59                 return 1;
  60
  61         return 0;
  62 }
  63
  64 static struct in6_addr prefix_to_bitmask(unsigned int prefix) {
  65         struct in6_addr bitmask;
  66
  67         for (unsigned int i = 0; i < 16; i++)
  68                 bitmask.s6_addr[i] = 0;
  69
  70         for (int i = prefix, j = 0; i > 0; i -= 8, j++) {
  71                 if (i >= 8)
  72                         bitmask.s6_addr[j] = 0xff;
  73                 else
  74                         bitmask.s6_addr[j] = 0xff << (8 - i);
  75         }
  76
  77         return bitmask;
  78 }
  79
  80 static struct in6_addr make_first_address(const struct in6_addr* address, const struct in6_addr* bitmask) {
  81         struct in6_addr a;
  82
  83         // Perform bitwise AND
  84         for (unsigned int i = 0; i < 4; i++)
  85                 a.s6_addr32[i] = address->s6_addr32[i] & bitmask->s6_addr32[i];
  86
  87         return a;
  88 }
  89
  90 static struct in6_addr make_last_address(const struct in6_addr* address, const struct in6_addr* bitmask) {
  91         struct in6_addr a;
  92
  93         // Perform bitwise OR
  94         for (unsigned int i = 0; i < 4; i++)
  95                 a.s6_addr32[i] = address->s6_addr32[i] | ~bitmask->s6_addr32[i];
  96
  97         return a;
  98 }
  99
 100 static struct in6_addr address_increment(const struct in6_addr* address) {
 101         struct in6_addr a = *address;
 102
 103         for (int octet = 15; octet >= 0; octet--) {
 104                 if (a.s6_addr[octet] < 255) {
 105                         a.s6_addr[octet]++;
 106                         break;
 107                 } else {
 108                         a.s6_addr[octet] = 0;
 109                 }
 110         }
 111
 112         return a;
 113 }
 114
 115 LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
 116                 struct in6_addr* address, unsigned int prefix) {
 117         // Address cannot be unspecified
 118         if (IN6_IS_ADDR_UNSPECIFIED(address)) {
 119                 DEBUG(ctx, "Start address is unspecified\n");
 120                 return -EINVAL;
 121         }
 122
 123         // Address cannot be loopback
 124         if (IN6_IS_ADDR_LOOPBACK(address)) {
 125                 DEBUG(ctx, "Start address is loopback address\n");
 126                 return -EINVAL;
 127         }
 128
 129         // Address cannot be link-local
 130         if (IN6_IS_ADDR_LINKLOCAL(address)) {
 131                 DEBUG(ctx, "Start address cannot be link-local\n");
 132                 return -EINVAL;
 133         }
 134
 135         // Address cannot be site-local
 136         if (IN6_IS_ADDR_SITELOCAL(address)) {
 137                 DEBUG(ctx, "Start address cannot be site-local\n");
 138                 return -EINVAL;
 139         }
 140
 141         // Validate the prefix
 142         if (valid_prefix(address, prefix) != 0) {
 143                 DEBUG(ctx, "Invalid prefix: %u\n", prefix);
 144                 return -EINVAL;
 145         }
 146
 147         struct loc_network* n = calloc(1, sizeof(*n));
 148         if (!n)
 149                 return -ENOMEM;
 150
 151         n->ctx = loc_ref(ctx);
 152         n->refcount = 1;
 153
 154         // Store the prefix
 155         n->prefix = prefix;
 156
 157         // Convert the prefix into a bitmask
 158         struct in6_addr bitmask = prefix_to_bitmask(n->prefix);
 159
 160         // Store the first and last address in the network
 161         n->first_address = make_first_address(address, &bitmask);
 162         n->last_address = make_last_address(&n->first_address, &bitmask);
 163
 164         // Set family
 165         if (IN6_IS_ADDR_V4MAPPED(&n->first_address))
 166                 n->family = AF_INET;
 167         else
 168                 n->family = AF_INET6;
 169
 170         DEBUG(n->ctx, "Network allocated at %p\n", n);
 171         *network = n;
 172         return 0;
 173 }
 174
 175 LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
 176                 const char* address_string) {
 177         struct in6_addr first_address;
 178         char* prefix_string;
 179         unsigned int prefix = 128;
 180         int r = -EINVAL;
 181
 182         DEBUG(ctx, "Attempting to parse network %s\n", address_string);
 183
 184         // Make a copy of the string to work on it
 185         char* buffer = strdup(address_string);
 186         address_string = prefix_string = buffer;
 187
 188         // Split address and prefix
 189         address_string = strsep(&prefix_string, "/");
 190
 191         DEBUG(ctx, "  Split into address = %s, prefix = %s\n", address_string, prefix_string);
 192
 193         // Parse the address
 194         r = loc_parse_address(ctx, address_string, &first_address);
 195         if (r) {
 196                 DEBUG(ctx, "The address could not be parsed\n");
 197                 goto FAIL;
 198         }
 199
 200         // If a prefix was given, we will try to parse it
 201         if (prefix_string) {
 202                 // Convert prefix to integer
 203                 prefix = strtol(prefix_string, NULL, 10);
 204
 205                 if (!prefix) {
 206                         DEBUG(ctx, "The prefix was not parsable: %s\n", prefix_string);
 207                         goto FAIL;
 208                 }
 209
 210                 // Map the prefix to IPv6 if needed
 211                 if (IN6_IS_ADDR_V4MAPPED(&first_address))
 212                         prefix += 96;
 213         }
 214
 215 FAIL:
 216         // Free temporary buffer
 217         free(buffer);
 218
 219         // Exit if the parsing was unsuccessful
 220         if (r)
 221                 return r;
 222
 223         // Create a new network
 224         return loc_network_new(ctx, network, &first_address, prefix);
 225 }
 226
 227 LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
 228         network->refcount++;
 229
 230         return network;
 231 }
 232
 233 static void loc_network_free(struct loc_network* network) {
 234         DEBUG(network->ctx, "Releasing network at %p\n", network);
 235
 236         loc_unref(network->ctx);
 237         free(network);
 238 }
 239
 240 LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
 241         if (!network)
 242                 return NULL;
 243
 244         if (--network->refcount > 0)
 245                 return network;
 246
 247         loc_network_free(network);
 248         return NULL;
 249 }
 250
 251 static int format_ipv6_address(const struct in6_addr* address, char* string, size_t length) {
 252         const char* ret = inet_ntop(AF_INET6, address, string, length);
 253         if (!ret)
 254                 return -1;
 255
 256         return 0;
 257 }
 258
 259 static int format_ipv4_address(const struct in6_addr* address, char* string, size_t length) {
 260         struct in_addr ipv4_address;
 261         ipv4_address.s_addr = address->s6_addr32[3];
 262
 263         const char* ret = inet_ntop(AF_INET, &ipv4_address, string, length);
 264         if (!ret)
 265                 return -1;
 266
 267         return 0;
 268 }
 269
 270 LOC_EXPORT char* loc_network_str(struct loc_network* network) {
 271         int r;
 272         const size_t length = INET6_ADDRSTRLEN + 4;
 273
 274         char* string = malloc(length);
 275         if (!string)
 276                 return NULL;
 277
 278         unsigned int prefix = network->prefix;
 279
 280         switch (network->family) {
 281                 case AF_INET6:
 282                         r = format_ipv6_address(&network->first_address, string, length);
 283                         break;
 284
 285                 case AF_INET:
 286                         r = format_ipv4_address(&network->first_address, string, length);
 287                         prefix -= 96;
 288                         break;
 289
 290                 default:
 291                         r = -1;
 292                         break;
 293         }
 294
 295         if (r) {
 296                 ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno));
 297                 free(string);
 298
 299                 return NULL;
 300         }
 301
 302         // Append prefix
 303         sprintf(string + strlen(string), "/%u", prefix);
 304
 305         return string;
 306 }
 307
 308 LOC_EXPORT int loc_network_address_family(struct loc_network* network) {
 309         return network->family;
 310 }
 311
 312 static char* loc_network_format_address(struct loc_network* network, const struct in6_addr* address) {
 313         const size_t length = INET6_ADDRSTRLEN;
 314
 315         char* string = malloc(length);
 316         if (!string)
 317                 return NULL;
 318
 319         int r = 0;
 320
 321         switch (network->family) {
 322                 case AF_INET6:
 323                         r = format_ipv6_address(address, string, length);
 324                         break;
 325
 326                 case AF_INET:
 327                         r = format_ipv4_address(address, string, length);
 328                         break;
 329
 330                 default:
 331                         r = -1;
 332                         break;
 333         }
 334
 335         if (r) {
 336                 ERROR(network->ctx, "Could not format IP address to string: %s\n", strerror(errno));
 337                 free(string);
 338
 339                 return NULL;
 340         }
 341
 342         return string;
 343 }
 344
 345 LOC_EXPORT char* loc_network_format_first_address(struct loc_network* network) {
 346         return loc_network_format_address(network, &network->first_address);
 347 }
 348
 349 LOC_EXPORT char* loc_network_format_last_address(struct loc_network* network) {
 350         return loc_network_format_address(network, &network->last_address);
 351 }
 352
 353 LOC_EXPORT int loc_network_match_address(struct loc_network* network, const struct in6_addr* address) {
 354         // Address must be larger than the start address
 355         if (in6_addr_cmp(&network->first_address, address) > 0)
 356                 return 1;
 357
 358         // Address must be smaller than the last address
 359         if (in6_addr_cmp(&network->last_address, address) < 0)
 360                 return 1;
 361
 362         // The address is inside this network
 363         return 0;
 364 }
 365
 366 LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
 367         return network->country_code;
 368 }
 369
 370 LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) {
 371         // Set empty country code
 372         if (!country_code || !*country_code) {
 373                 *network->country_code = '\0';
 374                 return 0;
 375         }
 376
 377         // Check country code
 378         if (!loc_country_code_is_valid(country_code))
 379                 return -EINVAL;
 380
 381         loc_country_code_copy(network->country_code, country_code);
 382
 383         return 0;
 384 }
 385
 386 LOC_EXPORT int loc_network_match_country_code(struct loc_network* network, const char* country_code) {
 387         // Check country code
 388         if (!loc_country_code_is_valid(country_code))
 389                 return -EINVAL;
 390
 391         return (network->country_code[0] == country_code[0])
 392                 && (network->country_code[1] == country_code[1]);
 393 }
 394
 395 LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
 396         return network->asn;
 397 }
 398
 399 LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
 400         network->asn = asn;
 401
 402         return 0;
 403 }
 404
 405 LOC_EXPORT int loc_network_match_asn(struct loc_network* network, uint32_t asn) {
 406         return network->asn == asn;
 407 }
 408
 409 LOC_EXPORT int loc_network_has_flag(struct loc_network* network, uint32_t flag) {
 410         return network->flags & flag;
 411 }
 412
 413 LOC_EXPORT int loc_network_set_flag(struct loc_network* network, uint32_t flag) {
 414         network->flags |= flag;
 415
 416         return 0;
 417 }
 418
 419 LOC_EXPORT int loc_network_match_flag(struct loc_network* network, uint32_t flag) {
 420         return loc_network_has_flag(network, flag);
 421 }
 422
 423 LOC_EXPORT int loc_network_eq(struct loc_network* self, struct loc_network* other) {
 424         // Family must be the same
 425         if (self->family != other->family)
 426                 return 0;
 427
 428         // The start address must be the same
 429         if (in6_addr_cmp(&self->first_address, &other->first_address) != 0)
 430                 return 0;
 431
 432         // The prefix length must be the same
 433         if (self->prefix != other->prefix)
 434                 return 0;
 435
 436         return 1;
 437 }
 438
 439 static int loc_network_gt(struct loc_network* self, struct loc_network* other) {
 440         // Families must match
 441         if (self->family != other->family)
 442                 return -1;
 443
 444         int r = in6_addr_cmp(&self->first_address, &other->first_address);
 445
 446         switch (r) {
 447                 // Smaller
 448                 case -1:
 449                         return 0;
 450
 451                 // Larger
 452                 case 1:
 453                         return 1;
 454
 455                 default:
 456                         break;
 457         }
 458
 459         if (self->prefix > other->prefix)
 460                 return 1;
 461
 462         // Dunno
 463         return 0;
 464 }
 465
 466 LOC_EXPORT int loc_network_overlaps(struct loc_network* self, struct loc_network* other) {
 467         if (loc_network_match_address(self, &other->first_address) == 0)
 468                 return 1;
 469
 470         if (loc_network_match_address(self, &other->last_address) == 0)
 471                 return 1;
 472
 473         if (loc_network_match_address(other, &self->first_address) == 0)
 474                 return 1;
 475
 476         if (loc_network_match_address(other, &self->last_address) == 0)
 477                 return 1;
 478
 479         return 0;
 480 }
 481
 482 LOC_EXPORT int loc_network_is_subnet(struct loc_network* self, struct loc_network* other) {
 483         // If the start address of the other network is smaller than this network,
 484         // it cannot be a subnet.
 485         if (in6_addr_cmp(&self->first_address, &other->first_address) < 0)
 486                 return 0;
 487
 488         // If the end address of the other network is greater than this network,
 489         // it cannot be a subnet.
 490         if (in6_addr_cmp(&self->last_address, &other->last_address) > 0)
 491                 return 0;
 492
 493         return 1;
 494 }
 495
 496 // XXX DEPRECATED - I find this too difficult to use
 497 LOC_EXPORT int loc_network_is_subnet_of(struct loc_network* self, struct loc_network* other) {
 498         // If the start address of the other network is smaller than this network,
 499         // it cannot be a subnet.
 500         if (in6_addr_cmp(&self->first_address, &other->first_address) < 0)
 501                 return 0;
 502
 503         // If the end address of the other network is greater than this network,
 504         // it cannot be a subnet.
 505         if (in6_addr_cmp(&self->last_address, &other->last_address) > 0)
 506                 return 0;
 507
 508         return 1;
 509 }
 510
 511 LOC_EXPORT struct loc_network_list* loc_network_subnets(struct loc_network* network) {
 512         struct loc_network_list* list;
 513
 514         // New prefix length
 515         unsigned int prefix = network->prefix + 1;
 516
 517         // Check if the new prefix is valid
 518         if (valid_prefix(&network->first_address, prefix))
 519                 return NULL;
 520
 521         // Create a new list with the result
 522         int r = loc_network_list_new(network->ctx, &list);
 523         if (r) {
 524                 ERROR(network->ctx, "Could not create network list: %d\n", r);
 525                 return NULL;
 526         }
 527
 528         struct loc_network* subnet1 = NULL;
 529         struct loc_network* subnet2 = NULL;
 530
 531         // Create the first half of the network
 532         r = loc_network_new(network->ctx, &subnet1, &network->first_address, prefix);
 533         if (r)
 534                 goto ERROR;
 535
 536         // The next subnet starts after the first one
 537         struct in6_addr first_address = address_increment(&subnet1->last_address);
 538
 539         // Create the second half of the network
 540         r = loc_network_new(network->ctx, &subnet2, &first_address, prefix);
 541         if (r)
 542                 goto ERROR;
 543
 544         // Push the both onto the stack (in reverse order)
 545         r = loc_network_list_push(list, subnet2);
 546         if (r)
 547                 goto ERROR;
 548
 549         r = loc_network_list_push(list, subnet1);
 550         if (r)
 551                 goto ERROR;
 552
 553         // Copy country code
 554         const char* country_code = loc_network_get_country_code(network);
 555         if (country_code) {
 556                 loc_network_set_country_code(subnet1, country_code);
 557                 loc_network_set_country_code(subnet2, country_code);
 558         }
 559
 560         // Copy ASN
 561         uint32_t asn = loc_network_get_asn(network);
 562         if (asn) {
 563                 loc_network_set_asn(subnet1, asn);
 564                 loc_network_set_asn(subnet2, asn);
 565         }
 566
 567         loc_network_unref(subnet1);
 568         loc_network_unref(subnet2);
 569
 570         return list;
 571
 572 ERROR:
 573         if (subnet1)
 574                 loc_network_unref(subnet1);
 575
 576         if (subnet2)
 577                 loc_network_unref(subnet2);
 578
 579         if (list)
 580                 loc_network_list_unref(list);
 581
 582         return NULL;
 583 }
 584
 585 LOC_EXPORT struct loc_network_list* loc_network_exclude(
 586                 struct loc_network* self, struct loc_network* other) {
 587         struct loc_network_list* list;
 588
 589 #ifdef ENABLE_DEBUG
 590         char* n1 = loc_network_str(self);
 591         char* n2 = loc_network_str(other);
 592
 593         DEBUG(self->ctx, "Returning %s excluding %s...\n", n1, n2);
 594
 595         free(n1);
 596         free(n2);
 597 #endif
 598
 599         // Family must match
 600         if (self->family != other->family) {
 601                 DEBUG(self->ctx, "Family mismatch\n");
 602
 603                 return NULL;
 604         }
 605
 606         // Other must be a subnet of self
 607         if (!loc_network_is_subnet_of(other, self)) {
 608                 DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self);
 609
 610                 return NULL;
 611         }
 612
 613         // We cannot perform this operation if both networks equal
 614         if (loc_network_eq(self, other)) {
 615                 DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other);
 616
 617                 return NULL;
 618         }
 619
 620         // Create a new list with the result
 621         int r = loc_network_list_new(self->ctx, &list);
 622         if (r) {
 623                 ERROR(self->ctx, "Could not create network list: %d\n", r);
 624                 return NULL;
 625         }
 626
 627         struct loc_network_list* subnets = loc_network_subnets(self);
 628
 629         struct loc_network* subnet1 = NULL;
 630         struct loc_network* subnet2 = NULL;
 631
 632         while (subnets) {
 633                 // Fetch both subnets
 634                 subnet1 = loc_network_list_get(subnets, 0);
 635                 subnet2 = loc_network_list_get(subnets, 1);
 636
 637                 // Free list
 638                 loc_network_list_unref(subnets);
 639                 subnets = NULL;
 640
 641                 if (loc_network_eq(other, subnet1)) {
 642                         r = loc_network_list_push(list, subnet2);
 643                         if (r)
 644                                 goto ERROR;
 645
 646                 } else if (loc_network_eq(other, subnet2)) {
 647                         r = loc_network_list_push(list, subnet1);
 648                         if (r)
 649                                 goto ERROR;
 650
 651                 } else  if (loc_network_is_subnet_of(other, subnet1)) {
 652                         r = loc_network_list_push(list, subnet2);
 653                         if (r)
 654                                 goto ERROR;
 655
 656                         subnets = loc_network_subnets(subnet1);
 657
 658                 } else if (loc_network_is_subnet_of(other, subnet2)) {
 659                         r = loc_network_list_push(list, subnet1);
 660                         if (r)
 661                                 goto ERROR;
 662
 663                         subnets = loc_network_subnets(subnet2);
 664
 665                 } else {
 666                         ERROR(self->ctx, "We should never get here\n");
 667                         goto ERROR;
 668                 }
 669
 670                 loc_network_unref(subnet1);
 671                 loc_network_unref(subnet2);
 672         }
 673
 674 #ifdef ENABLE_DEBUG
 675         loc_network_list_dump(list);
 676 #endif
 677
 678         // Return the result
 679         return list;
 680
 681 ERROR:
 682         if (subnet1)
 683                 loc_network_unref(subnet1);
 684
 685         if (subnet2)
 686                 loc_network_unref(subnet2);
 687
 688         if (list)
 689                 loc_network_list_unref(list);
 690
 691         return NULL;
 692 }
 693
 694 LOC_EXPORT struct loc_network_list* loc_network_exclude_list(
 695                 struct loc_network* network, struct loc_network_list* list) {
 696         struct loc_network_list* to_check;
 697
 698         // Create a new list with all networks to look at
 699         int r = loc_network_list_new(network->ctx, &to_check);
 700         if (r)
 701                 return NULL;
 702
 703         struct loc_network* subnet = NULL;
 704         struct loc_network_list* subnets = NULL;
 705
 706         for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
 707                 subnet = loc_network_list_get(list, i);
 708
 709                 // Find all excluded networks
 710                 struct loc_network_list* excluded = loc_network_exclude(network, subnet);
 711                 if (excluded) {
 712                         // Add them all to the "to check" list
 713                         loc_network_list_merge(to_check, excluded);
 714                         loc_network_list_unref(excluded);
 715                 }
 716
 717                 // Cleanup
 718                 loc_network_unref(subnet);
 719         }
 720
 721         r = loc_network_list_new(network->ctx, &subnets);
 722         if (r) {
 723                 loc_network_list_unref(to_check);
 724                 return NULL;
 725         }
 726
 727         while (!loc_network_list_empty(to_check)) {
 728                 struct loc_network* subnet_to_check = loc_network_list_pop(to_check);
 729
 730                 // Marks whether this subnet passed all checks
 731                 int passed = 1;
 732
 733                 for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
 734                         subnet = loc_network_list_get(list, i);
 735
 736                         // Drop this subnet if is is already in list
 737                         if (loc_network_eq(subnet_to_check, subnet)) {
 738                                 passed = 0;
 739                                 loc_network_unref(subnet);
 740                                 break;
 741                         }
 742
 743                         // Drop this subnet if is a subnet of another subnet
 744                         if (loc_network_is_subnet_of(subnet, subnet_to_check)) {
 745                                 passed = 0;
 746                                 loc_network_unref(subnet);
 747                                 break;
 748                         }
 749
 750                         // Break it down if it overlaps
 751                         if (loc_network_overlaps(subnet_to_check, subnet)) {
 752                                 passed = 0;
 753
 754                                 struct loc_network_list* excluded = loc_network_exclude(subnet_to_check, subnet);
 755                                 if (excluded) {
 756                                         loc_network_list_merge(to_check, excluded);
 757                                         loc_network_list_unref(excluded);
 758                                 }
 759
 760                                 loc_network_unref(subnet);
 761                                 break;
 762                         }
 763
 764                         loc_network_unref(subnet);
 765                 }
 766
 767                 if (passed) {
 768                         r = loc_network_list_push(subnets, subnet_to_check);
 769                 }
 770
 771                 loc_network_unref(subnet_to_check);
 772         }
 773
 774         loc_network_list_unref(to_check);
 775
 776         // Sort the result
 777         loc_network_list_sort(subnets);
 778
 779         return subnets;
 780 }
 781
 782 LOC_EXPORT int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
 783         // Add country code
 784         loc_country_code_copy(dbobj->country_code, network->country_code);
 785
 786         // Add ASN
 787         dbobj->asn = htobe32(network->asn);
 788
 789         // Flags
 790         dbobj->flags = htobe16(network->flags);
 791
 792         return 0;
 793 }
 794
 795 LOC_EXPORT int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network,
 796                 struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) {
 797         char country_code[3] = "\0\0";
 798
 799         int r = loc_network_new(ctx, network, address, prefix);
 800         if (r) {
 801                 ERROR(ctx, "Could not allocate a new network: %s", strerror(-r));
 802                 return r;
 803         }
 804
 805         // Import country code
 806         loc_country_code_copy(country_code, dbobj->country_code);
 807
 808         r = loc_network_set_country_code(*network, country_code);
 809         if (r) {
 810                 ERROR(ctx, "Could not set country code: %s\n", country_code);
 811                 return r;
 812         }
 813
 814         // Import ASN
 815         uint32_t asn = be32toh(dbobj->asn);
 816         r = loc_network_set_asn(*network, asn);
 817         if (r) {
 818                 ERROR(ctx, "Could not set ASN: %d\n", asn);
 819                 return r;
 820         }
 821
 822         // Import flags
 823         int flags = be16toh(dbobj->flags);
 824         r = loc_network_set_flag(*network, flags);
 825         if (r) {
 826                 ERROR(ctx, "Could not set flags: %d\n", flags);
 827                 return r;
 828         }
 829
 830         return 0;
 831 }
 832
 833 struct loc_network_tree {
 834         struct loc_ctx* ctx;
 835         int refcount;
 836
 837         struct loc_network_tree_node* root;
 838 };
 839
 840 struct loc_network_tree_node {
 841         struct loc_ctx* ctx;
 842         int refcount;
 843
 844         struct loc_network_tree_node* zero;
 845         struct loc_network_tree_node* one;
 846
 847         struct loc_network* network;
 848 };
 849
 850 LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
 851         struct loc_network_tree* t = calloc(1, sizeof(*t));
 852         if (!t)
 853                 return -ENOMEM;
 854
 855         t->ctx = loc_ref(ctx);
 856         t->refcount = 1;
 857
 858         // Create the root node
 859         int r = loc_network_tree_node_new(ctx, &t->root);
 860         if (r) {
 861                 loc_network_tree_unref(t);
 862                 return r;
 863         }
 864
 865         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
 866         *tree = t;
 867         return 0;
 868 }
 869
 870 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
 871         return loc_network_tree_node_ref(tree->root);
 872 }
 873
 874 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
 875         struct loc_network_tree_node** n;
 876
 877         if (path == 0)
 878                 n = &node->zero;
 879         else
 880                 n = &node->one;
 881
 882         // If the desired node doesn't exist, yet, we will create it
 883         if (*n == NULL) {
 884                 int r = loc_network_tree_node_new(node->ctx, n);
 885                 if (r)
 886                         return NULL;
 887         }
 888
 889         return *n;
 890 }
 891
 892 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
 893         struct loc_network_tree_node* node = tree->root;
 894
 895         for (unsigned int i = 0; i < prefix; i++) {
 896                 // Check if the ith bit is one or zero
 897                 node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i));
 898         }
 899
 900         return node;
 901 }
 902
 903 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
 904                 int(*filter_callback)(struct loc_network* network, void* data),
 905                 int(*callback)(struct loc_network* network, void* data), void* data) {
 906         int r;
 907
 908         // Finding a network ends the walk here
 909         if (node->network) {
 910                 if (filter_callback) {
 911                         int f = filter_callback(node->network, data);
 912                         if (f < 0)
 913                                 return f;
 914
 915                         // Skip network if filter function returns value greater than zero
 916                         if (f > 0)
 917                                 return 0;
 918                 }
 919
 920                 r = callback(node->network, data);
 921                 if (r)
 922                         return r;
 923         }
 924
 925         // Walk down on the left side of the tree first
 926         if (node->zero) {
 927                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
 928                 if (r)
 929                         return r;
 930         }
 931
 932         // Then walk on the other side
 933         if (node->one) {
 934                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
 935                 if (r)
 936                         return r;
 937         }
 938
 939         return 0;
 940 }
 941
 942 LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
 943                 int(*filter_callback)(struct loc_network* network, void* data),
 944                 int(*callback)(struct loc_network* network, void* data), void* data) {
 945         return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
 946 }
 947
 948 static void loc_network_tree_free(struct loc_network_tree* tree) {
 949         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
 950
 951         loc_network_tree_node_unref(tree->root);
 952
 953         loc_unref(tree->ctx);
 954         free(tree);
 955 }
 956
 957 LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
 958         if (--tree->refcount > 0)
 959                 return tree;
 960
 961         loc_network_tree_free(tree);
 962         return NULL;
 963 }
 964
 965 static int __loc_network_tree_dump(struct loc_network* network, void* data) {
 966         DEBUG(network->ctx, "Dumping network at %p\n", network);
 967
 968         char* s = loc_network_str(network);
 969         if (!s)
 970                 return 1;
 971
 972         INFO(network->ctx, "%s\n", s);
 973         free(s);
 974
 975         return 0;
 976 }
 977
 978 LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
 979         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
 980
 981         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
 982 }
 983
 984 LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
 985         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
 986
 987         struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
 988                         &network->first_address, network->prefix);
 989         if (!node) {
 990                 ERROR(tree->ctx, "Could not find a node\n");
 991                 return -ENOMEM;
 992         }
 993
 994         // Check if node has not been set before
 995         if (node->network) {
 996                 DEBUG(tree->ctx, "There is already a network at this path\n");
 997                 return -EBUSY;
 998         }
 999
1000         // Point node to the network
1001         node->network = loc_network_ref(network);
1002
1003         return 0;
1004 }
1005
1006 static int __loc_network_tree_count(struct loc_network* network, void* data) {
1007         size_t* counter = (size_t*)data;
1008
1009         // Increase the counter for each network
1010         counter++;
1011
1012         return 0;
1013 }
1014
1015 LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
1016         size_t counter = 0;
1017
1018         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
1019         if (r)
1020                 return r;
1021
1022         return counter;
1023 }
1024
1025 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
1026         size_t counter = 1;
1027
1028         if (node->zero)
1029                 counter += __loc_network_tree_count_nodes(node->zero);
1030
1031         if (node->one)
1032                 counter += __loc_network_tree_count_nodes(node->one);
1033
1034         return counter;
1035 }
1036
1037 LOC_EXPORT size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
1038         return __loc_network_tree_count_nodes(tree->root);
1039 }
1040
1041 LOC_EXPORT int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
1042         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
1043         if (!n)
1044                 return -ENOMEM;
1045
1046         n->ctx = loc_ref(ctx);
1047         n->refcount = 1;
1048
1049         n->zero = n->one = NULL;
1050
1051         DEBUG(n->ctx, "Network node allocated at %p\n", n);
1052         *node = n;
1053         return 0;
1054 }
1055
1056 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
1057         if (node)
1058                 node->refcount++;
1059
1060         return node;
1061 }
1062
1063 static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
1064         DEBUG(node->ctx, "Releasing network node at %p\n", node);
1065
1066         if (node->network)
1067                 loc_network_unref(node->network);
1068
1069         if (node->zero)
1070                 loc_network_tree_node_unref(node->zero);
1071
1072         if (node->one)
1073                 loc_network_tree_node_unref(node->one);
1074
1075         loc_unref(node->ctx);
1076         free(node);
1077 }
1078
1079 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
1080         if (!node)
1081                 return NULL;
1082
1083         if (--node->refcount > 0)
1084                 return node;
1085
1086         loc_network_tree_node_free(node);
1087         return NULL;
1088 }
1089
1090 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
1091         if (index == 0)
1092                 node = node->zero;
1093         else
1094                 node = node->one;
1095
1096         if (!node)
1097                 return NULL;
1098
1099         return loc_network_tree_node_ref(node);
1100 }
1101
1102 LOC_EXPORT int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
1103         return (!!node->network);
1104 }
1105
1106 LOC_EXPORT struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
1107         return loc_network_ref(node->network);
1108 }
1109
1110 // List
1111
1112 struct loc_network_list {
1113         struct loc_ctx* ctx;
1114         int refcount;
1115
1116         struct loc_network* list[1024];
1117         size_t size;
1118         size_t max_size;
1119 };
1120
1121 LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx,
1122                 struct loc_network_list** list) {
1123         struct loc_network_list* l = calloc(1, sizeof(*l));
1124         if (!l)
1125                 return -ENOMEM;
1126
1127         l->ctx = loc_ref(ctx);
1128         l->refcount = 1;
1129
1130         // Do not allow this list to grow larger than this
1131         l->max_size = 1024;
1132
1133         DEBUG(l->ctx, "Network list allocated at %p\n", l);
1134         *list = l;
1135         return 0;
1136 }
1137
1138 LOC_EXPORT struct loc_network_list* loc_network_list_ref(struct loc_network_list* list) {
1139         list->refcount++;
1140
1141         return list;
1142 }
1143
1144 static void loc_network_list_free(struct loc_network_list* list) {
1145         DEBUG(list->ctx, "Releasing network list at %p\n", list);
1146
1147         for (unsigned int i = 0; i < list->size; i++)
1148                 loc_network_unref(list->list[i]);
1149
1150         loc_unref(list->ctx);
1151         free(list);
1152 }
1153
1154 LOC_EXPORT struct loc_network_list* loc_network_list_unref(struct loc_network_list* list) {
1155         if (!list)
1156                 return NULL;
1157
1158         if (--list->refcount > 0)
1159                 return list;
1160
1161         loc_network_list_free(list);
1162         return NULL;
1163 }
1164
1165 LOC_EXPORT size_t loc_network_list_size(struct loc_network_list* list) {
1166         return list->size;
1167 }
1168
1169 LOC_EXPORT int loc_network_list_empty(struct loc_network_list* list) {
1170         return list->size == 0;
1171 }
1172
1173 LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) {
1174         for (unsigned int i = 0; i < list->size; i++)
1175                 loc_network_unref(list->list[i]);
1176
1177         list->size = 0;
1178 }
1179
1180 LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) {
1181         struct loc_network* network;
1182         char* s;
1183
1184         for (unsigned int i = 0; i < list->size; i++) {
1185                 network = list->list[i];
1186
1187                 s = loc_network_str(network);
1188
1189                 INFO(list->ctx, "%s\n", s);
1190                 free(s);
1191         }
1192 }
1193
1194 LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
1195         // Check index
1196         if (index >= list->size)
1197                 return NULL;
1198
1199         return loc_network_ref(list->list[index]);
1200 }
1201
1202 LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
1203         // Do not add networks that are already on the list
1204         if (loc_network_list_contains(list, network))
1205                 return 0;
1206
1207         // Check if we have space left
1208         if (list->size == list->max_size) {
1209                 ERROR(list->ctx, "%p: Could not push network onto the stack: Stack full\n", list);
1210                 return -ENOMEM;
1211         }
1212
1213         DEBUG(list->ctx, "%p: Pushing network %p onto stack\n", list, network);
1214
1215         list->list[list->size++] = loc_network_ref(network);
1216
1217         return 0;
1218 }
1219
1220 LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
1221         // Return nothing when empty
1222         if (loc_network_list_empty(list)) {
1223                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
1224                 return NULL;
1225         }
1226
1227         struct loc_network* network = list->list[--list->size];
1228
1229         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
1230
1231         return network;
1232 }
1233
1234 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
1235         for (unsigned int i = 0; i < list->size; i++) {
1236                 if (loc_network_eq(list->list[i], network))
1237                         return 1;
1238         }
1239
1240         return 0;
1241 }
1242
1243 static void loc_network_list_swap(struct loc_network_list* list, unsigned int i1, unsigned int i2) {
1244         // Do nothing for invalid indices
1245         if (i1 >= list->size || i2 >= list->size)
1246                 return;
1247
1248         struct loc_network* network1 = list->list[i1];
1249         struct loc_network* network2 = list->list[i2];
1250
1251         list->list[i1] = network2;
1252         list->list[i2] = network1;
1253 }
1254
1255 LOC_EXPORT void loc_network_list_reverse(struct loc_network_list* list) {
1256         unsigned int i = 0;
1257         unsigned int j = list->size - 1;
1258
1259         while (i < j) {
1260                 loc_network_list_swap(list, i++, j--);
1261         }
1262 }
1263
1264 LOC_EXPORT void loc_network_list_sort(struct loc_network_list* list) {
1265         unsigned int n = list->size;
1266         int swapped;
1267
1268         do {
1269                 swapped = 0;
1270
1271                 for (unsigned int i = 1; i < n; i++) {
1272                         if (loc_network_gt(list->list[i-1], list->list[i]) > 0) {
1273                                 loc_network_list_swap(list, i-1, i);
1274                                 swapped = 1;
1275                         }
1276                 }
1277
1278                 n--;
1279         } while (swapped);
1280 }
1281
1282 LOC_EXPORT int loc_network_list_merge(
1283                 struct loc_network_list* self, struct loc_network_list* other) {
1284         int r;
1285
1286         for (unsigned int i = 0; i < other->size; i++) {
1287                 r = loc_network_list_push(self, other->list[i]);
1288                 if (r)
1289                         return r;
1290         }
1291
1292         return 0;
1293 }