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         return subnets;
 777 }
 778
 779 LOC_EXPORT int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
 780         // Add country code
 781         loc_country_code_copy(dbobj->country_code, network->country_code);
 782
 783         // Add ASN
 784         dbobj->asn = htobe32(network->asn);
 785
 786         // Flags
 787         dbobj->flags = htobe16(network->flags);
 788
 789         return 0;
 790 }
 791
 792 LOC_EXPORT int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network,
 793                 struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) {
 794         char country_code[3] = "\0\0";
 795
 796         int r = loc_network_new(ctx, network, address, prefix);
 797         if (r) {
 798                 ERROR(ctx, "Could not allocate a new network: %s", strerror(-r));
 799                 return r;
 800         }
 801
 802         // Import country code
 803         loc_country_code_copy(country_code, dbobj->country_code);
 804
 805         r = loc_network_set_country_code(*network, country_code);
 806         if (r) {
 807                 ERROR(ctx, "Could not set country code: %s\n", country_code);
 808                 return r;
 809         }
 810
 811         // Import ASN
 812         uint32_t asn = be32toh(dbobj->asn);
 813         r = loc_network_set_asn(*network, asn);
 814         if (r) {
 815                 ERROR(ctx, "Could not set ASN: %d\n", asn);
 816                 return r;
 817         }
 818
 819         // Import flags
 820         int flags = be16toh(dbobj->flags);
 821         r = loc_network_set_flag(*network, flags);
 822         if (r) {
 823                 ERROR(ctx, "Could not set flags: %d\n", flags);
 824                 return r;
 825         }
 826
 827         return 0;
 828 }
 829
 830 struct loc_network_tree {
 831         struct loc_ctx* ctx;
 832         int refcount;
 833
 834         struct loc_network_tree_node* root;
 835 };
 836
 837 struct loc_network_tree_node {
 838         struct loc_ctx* ctx;
 839         int refcount;
 840
 841         struct loc_network_tree_node* zero;
 842         struct loc_network_tree_node* one;
 843
 844         struct loc_network* network;
 845 };
 846
 847 LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
 848         struct loc_network_tree* t = calloc(1, sizeof(*t));
 849         if (!t)
 850                 return -ENOMEM;
 851
 852         t->ctx = loc_ref(ctx);
 853         t->refcount = 1;
 854
 855         // Create the root node
 856         int r = loc_network_tree_node_new(ctx, &t->root);
 857         if (r) {
 858                 loc_network_tree_unref(t);
 859                 return r;
 860         }
 861
 862         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
 863         *tree = t;
 864         return 0;
 865 }
 866
 867 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
 868         return loc_network_tree_node_ref(tree->root);
 869 }
 870
 871 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
 872         struct loc_network_tree_node** n;
 873
 874         if (path == 0)
 875                 n = &node->zero;
 876         else
 877                 n = &node->one;
 878
 879         // If the desired node doesn't exist, yet, we will create it
 880         if (*n == NULL) {
 881                 int r = loc_network_tree_node_new(node->ctx, n);
 882                 if (r)
 883                         return NULL;
 884         }
 885
 886         return *n;
 887 }
 888
 889 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
 890         struct loc_network_tree_node* node = tree->root;
 891
 892         for (unsigned int i = 0; i < prefix; i++) {
 893                 // Check if the ith bit is one or zero
 894                 node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i));
 895         }
 896
 897         return node;
 898 }
 899
 900 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
 901                 int(*filter_callback)(struct loc_network* network, void* data),
 902                 int(*callback)(struct loc_network* network, void* data), void* data) {
 903         int r;
 904
 905         // Finding a network ends the walk here
 906         if (node->network) {
 907                 if (filter_callback) {
 908                         int f = filter_callback(node->network, data);
 909                         if (f < 0)
 910                                 return f;
 911
 912                         // Skip network if filter function returns value greater than zero
 913                         if (f > 0)
 914                                 return 0;
 915                 }
 916
 917                 r = callback(node->network, data);
 918                 if (r)
 919                         return r;
 920         }
 921
 922         // Walk down on the left side of the tree first
 923         if (node->zero) {
 924                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
 925                 if (r)
 926                         return r;
 927         }
 928
 929         // Then walk on the other side
 930         if (node->one) {
 931                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
 932                 if (r)
 933                         return r;
 934         }
 935
 936         return 0;
 937 }
 938
 939 LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
 940                 int(*filter_callback)(struct loc_network* network, void* data),
 941                 int(*callback)(struct loc_network* network, void* data), void* data) {
 942         return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
 943 }
 944
 945 static void loc_network_tree_free(struct loc_network_tree* tree) {
 946         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
 947
 948         loc_network_tree_node_unref(tree->root);
 949
 950         loc_unref(tree->ctx);
 951         free(tree);
 952 }
 953
 954 LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
 955         if (--tree->refcount > 0)
 956                 return tree;
 957
 958         loc_network_tree_free(tree);
 959         return NULL;
 960 }
 961
 962 static int __loc_network_tree_dump(struct loc_network* network, void* data) {
 963         DEBUG(network->ctx, "Dumping network at %p\n", network);
 964
 965         char* s = loc_network_str(network);
 966         if (!s)
 967                 return 1;
 968
 969         INFO(network->ctx, "%s\n", s);
 970         free(s);
 971
 972         return 0;
 973 }
 974
 975 LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
 976         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
 977
 978         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
 979 }
 980
 981 LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
 982         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
 983
 984         struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
 985                         &network->first_address, network->prefix);
 986         if (!node) {
 987                 ERROR(tree->ctx, "Could not find a node\n");
 988                 return -ENOMEM;
 989         }
 990
 991         // Check if node has not been set before
 992         if (node->network) {
 993                 DEBUG(tree->ctx, "There is already a network at this path\n");
 994                 return -EBUSY;
 995         }
 996
 997         // Point node to the network
 998         node->network = loc_network_ref(network);
 999
1000         return 0;
1001 }
1002
1003 static int __loc_network_tree_count(struct loc_network* network, void* data) {
1004         size_t* counter = (size_t*)data;
1005
1006         // Increase the counter for each network
1007         counter++;
1008
1009         return 0;
1010 }
1011
1012 LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
1013         size_t counter = 0;
1014
1015         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
1016         if (r)
1017                 return r;
1018
1019         return counter;
1020 }
1021
1022 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
1023         size_t counter = 1;
1024
1025         if (node->zero)
1026                 counter += __loc_network_tree_count_nodes(node->zero);
1027
1028         if (node->one)
1029                 counter += __loc_network_tree_count_nodes(node->one);
1030
1031         return counter;
1032 }
1033
1034 LOC_EXPORT size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
1035         return __loc_network_tree_count_nodes(tree->root);
1036 }
1037
1038 LOC_EXPORT int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
1039         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
1040         if (!n)
1041                 return -ENOMEM;
1042
1043         n->ctx = loc_ref(ctx);
1044         n->refcount = 1;
1045
1046         n->zero = n->one = NULL;
1047
1048         DEBUG(n->ctx, "Network node allocated at %p\n", n);
1049         *node = n;
1050         return 0;
1051 }
1052
1053 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
1054         if (node)
1055                 node->refcount++;
1056
1057         return node;
1058 }
1059
1060 static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
1061         DEBUG(node->ctx, "Releasing network node at %p\n", node);
1062
1063         if (node->network)
1064                 loc_network_unref(node->network);
1065
1066         if (node->zero)
1067                 loc_network_tree_node_unref(node->zero);
1068
1069         if (node->one)
1070                 loc_network_tree_node_unref(node->one);
1071
1072         loc_unref(node->ctx);
1073         free(node);
1074 }
1075
1076 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
1077         if (!node)
1078                 return NULL;
1079
1080         if (--node->refcount > 0)
1081                 return node;
1082
1083         loc_network_tree_node_free(node);
1084         return NULL;
1085 }
1086
1087 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
1088         if (index == 0)
1089                 node = node->zero;
1090         else
1091                 node = node->one;
1092
1093         if (!node)
1094                 return NULL;
1095
1096         return loc_network_tree_node_ref(node);
1097 }
1098
1099 LOC_EXPORT int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
1100         return (!!node->network);
1101 }
1102
1103 LOC_EXPORT struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
1104         return loc_network_ref(node->network);
1105 }
1106
1107 // List
1108
1109 struct loc_network_list {
1110         struct loc_ctx* ctx;
1111         int refcount;
1112
1113         struct loc_network* list[1024];
1114         size_t size;
1115         size_t max_size;
1116 };
1117
1118 LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx,
1119                 struct loc_network_list** list) {
1120         struct loc_network_list* l = calloc(1, sizeof(*l));
1121         if (!l)
1122                 return -ENOMEM;
1123
1124         l->ctx = loc_ref(ctx);
1125         l->refcount = 1;
1126
1127         // Do not allow this list to grow larger than this
1128         l->max_size = 1024;
1129
1130         DEBUG(l->ctx, "Network list allocated at %p\n", l);
1131         *list = l;
1132         return 0;
1133 }
1134
1135 LOC_EXPORT struct loc_network_list* loc_network_list_ref(struct loc_network_list* list) {
1136         list->refcount++;
1137
1138         return list;
1139 }
1140
1141 static void loc_network_list_free(struct loc_network_list* list) {
1142         DEBUG(list->ctx, "Releasing network list at %p\n", list);
1143
1144         for (unsigned int i = 0; i < list->size; i++)
1145                 loc_network_unref(list->list[i]);
1146
1147         loc_unref(list->ctx);
1148         free(list);
1149 }
1150
1151 LOC_EXPORT struct loc_network_list* loc_network_list_unref(struct loc_network_list* list) {
1152         if (!list)
1153                 return NULL;
1154
1155         if (--list->refcount > 0)
1156                 return list;
1157
1158         loc_network_list_free(list);
1159         return NULL;
1160 }
1161
1162 LOC_EXPORT size_t loc_network_list_size(struct loc_network_list* list) {
1163         return list->size;
1164 }
1165
1166 LOC_EXPORT int loc_network_list_empty(struct loc_network_list* list) {
1167         return list->size == 0;
1168 }
1169
1170 LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) {
1171         for (unsigned int i = 0; i < list->size; i++)
1172                 loc_network_unref(list->list[i]);
1173
1174         list->size = 0;
1175 }
1176
1177 LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) {
1178         struct loc_network* network;
1179         char* s;
1180
1181         for (unsigned int i = 0; i < list->size; i++) {
1182                 network = list->list[i];
1183
1184                 s = loc_network_str(network);
1185
1186                 INFO(list->ctx, "%s\n", s);
1187                 free(s);
1188         }
1189 }
1190
1191 LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
1192         // Check index
1193         if (index >= list->size)
1194                 return NULL;
1195
1196         return loc_network_ref(list->list[index]);
1197 }
1198
1199 LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
1200         // Do not add networks that are already on the list
1201         if (loc_network_list_contains(list, network))
1202                 return 0;
1203
1204         // Check if we have space left
1205         if (list->size == list->max_size) {
1206                 ERROR(list->ctx, "%p: Could not push network onto the stack: Stack full\n", list);
1207                 return -ENOMEM;
1208         }
1209
1210         DEBUG(list->ctx, "%p: Pushing network %p onto stack\n", list, network);
1211
1212         list->list[list->size++] = loc_network_ref(network);
1213
1214         return 0;
1215 }
1216
1217 LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
1218         // Return nothing when empty
1219         if (loc_network_list_empty(list)) {
1220                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
1221                 return NULL;
1222         }
1223
1224         struct loc_network* network = list->list[--list->size];
1225
1226         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
1227
1228         return network;
1229 }
1230
1231 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
1232         for (unsigned int i = 0; i < list->size; i++) {
1233                 if (loc_network_eq(list->list[i], network))
1234                         return 1;
1235         }
1236
1237         return 0;
1238 }
1239
1240 static void loc_network_list_swap(struct loc_network_list* list, unsigned int i1, unsigned int i2) {
1241         // Do nothing for invalid indices
1242         if (i1 >= list->size || i2 >= list->size)
1243                 return;
1244
1245         struct loc_network* network1 = list->list[i1];
1246         struct loc_network* network2 = list->list[i2];
1247
1248         list->list[i1] = network2;
1249         list->list[i2] = network1;
1250 }
1251
1252 LOC_EXPORT void loc_network_list_reverse(struct loc_network_list* list) {
1253         unsigned int i = 0;
1254         unsigned int j = list->size - 1;
1255
1256         while (i < j) {
1257                 loc_network_list_swap(list, i++, j--);
1258         }
1259 }
1260
1261 LOC_EXPORT void loc_network_list_sort(struct loc_network_list* list) {
1262         unsigned int n = list->size;
1263         int swapped;
1264
1265         do {
1266                 swapped = 0;
1267
1268                 for (unsigned int i = 1; i < n; i++) {
1269                         if (loc_network_gt(list->list[i-1], list->list[i]) > 0) {
1270                                 loc_network_list_swap(list, i-1, i);
1271                                 swapped = 1;
1272                         }
1273                 }
1274
1275                 n--;
1276         } while (swapped);
1277 }
1278
1279 LOC_EXPORT int loc_network_list_merge(
1280                 struct loc_network_list* self, struct loc_network_list* other) {
1281         int r;
1282
1283         for (unsigned int i = 0; i < other->size; i++) {
1284                 r = loc_network_list_push(self, other->list[i]);
1285                 if (r)
1286                         return r;
1287         }
1288
1289         return 0;
1290 }