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         loc_network_unref(subnet1);
 554         loc_network_unref(subnet2);
 555
 556         return list;
 557
 558 ERROR:
 559         if (subnet1)
 560                 loc_network_unref(subnet1);
 561
 562         if (subnet2)
 563                 loc_network_unref(subnet2);
 564
 565         if (list)
 566                 loc_network_list_unref(list);
 567
 568         return NULL;
 569 }
 570
 571 LOC_EXPORT struct loc_network_list* loc_network_exclude(
 572                 struct loc_network* self, struct loc_network* other) {
 573         struct loc_network_list* list;
 574
 575 #ifdef ENABLE_DEBUG
 576         char* n1 = loc_network_str(self);
 577         char* n2 = loc_network_str(other);
 578
 579         DEBUG(self->ctx, "Returning %s excluding %s...\n", n1, n2);
 580
 581         free(n1);
 582         free(n2);
 583 #endif
 584
 585         // Family must match
 586         if (self->family != other->family) {
 587                 DEBUG(self->ctx, "Family mismatch\n");
 588
 589                 return NULL;
 590         }
 591
 592         // Other must be a subnet of self
 593         if (!loc_network_is_subnet_of(other, self)) {
 594                 DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self);
 595
 596                 return NULL;
 597         }
 598
 599         // We cannot perform this operation if both networks equal
 600         if (loc_network_eq(self, other)) {
 601                 DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other);
 602
 603                 return NULL;
 604         }
 605
 606         // Create a new list with the result
 607         int r = loc_network_list_new(self->ctx, &list);
 608         if (r) {
 609                 ERROR(self->ctx, "Could not create network list: %d\n", r);
 610                 return NULL;
 611         }
 612
 613         struct loc_network_list* subnets = loc_network_subnets(self);
 614
 615         struct loc_network* subnet1 = NULL;
 616         struct loc_network* subnet2 = NULL;
 617
 618         while (subnets) {
 619                 // Fetch both subnets
 620                 subnet1 = loc_network_list_get(subnets, 0);
 621                 subnet2 = loc_network_list_get(subnets, 1);
 622
 623                 // Free list
 624                 loc_network_list_unref(subnets);
 625                 subnets = NULL;
 626
 627                 if (loc_network_eq(other, subnet1)) {
 628                         r = loc_network_list_push(list, subnet2);
 629                         if (r)
 630                                 goto ERROR;
 631
 632                 } else if (loc_network_eq(other, subnet2)) {
 633                         r = loc_network_list_push(list, subnet1);
 634                         if (r)
 635                                 goto ERROR;
 636
 637                 } else  if (loc_network_is_subnet_of(other, subnet1)) {
 638                         r = loc_network_list_push(list, subnet2);
 639                         if (r)
 640                                 goto ERROR;
 641
 642                         subnets = loc_network_subnets(subnet1);
 643
 644                 } else if (loc_network_is_subnet_of(other, subnet2)) {
 645                         r = loc_network_list_push(list, subnet1);
 646                         if (r)
 647                                 goto ERROR;
 648
 649                         subnets = loc_network_subnets(subnet2);
 650
 651                 } else {
 652                         ERROR(self->ctx, "We should never get here\n");
 653                         goto ERROR;
 654                 }
 655
 656                 loc_network_unref(subnet1);
 657                 loc_network_unref(subnet2);
 658         }
 659
 660 #ifdef ENABLE_DEBUG
 661         loc_network_list_dump(list);
 662 #endif
 663
 664         // Return the result
 665         return list;
 666
 667 ERROR:
 668         if (subnet1)
 669                 loc_network_unref(subnet1);
 670
 671         if (subnet2)
 672                 loc_network_unref(subnet2);
 673
 674         if (list)
 675                 loc_network_list_unref(list);
 676
 677         return NULL;
 678 }
 679
 680 LOC_EXPORT struct loc_network_list* loc_network_exclude_list(
 681                 struct loc_network* network, struct loc_network_list* list) {
 682         struct loc_network_list* to_check;
 683
 684         // Create a new list with all networks to look at
 685         int r = loc_network_list_new(network->ctx, &to_check);
 686         if (r)
 687                 return NULL;
 688
 689         struct loc_network* subnet = NULL;
 690         struct loc_network_list* subnets = NULL;
 691
 692         for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
 693                 subnet = loc_network_list_get(list, i);
 694
 695                 // Find all excluded networks
 696                 struct loc_network_list* excluded = loc_network_exclude(network, subnet);
 697                 if (excluded) {
 698                         // Add them all to the "to check" list
 699                         loc_network_list_merge(to_check, excluded);
 700                         loc_network_list_unref(excluded);
 701                 }
 702
 703                 // Cleanup
 704                 loc_network_unref(subnet);
 705         }
 706
 707         r = loc_network_list_new(network->ctx, &subnets);
 708         if (r) {
 709                 loc_network_list_unref(to_check);
 710                 return NULL;
 711         }
 712
 713         while (!loc_network_list_empty(to_check)) {
 714                 struct loc_network* subnet_to_check = loc_network_list_pop(to_check);
 715
 716                 // Marks whether this subnet passed all checks
 717                 int passed = 1;
 718
 719                 for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
 720                         subnet = loc_network_list_get(list, i);
 721
 722                         // Drop this subnet if is is already in list
 723                         if (loc_network_eq(subnet_to_check, subnet)) {
 724                                 passed = 0;
 725                                 loc_network_unref(subnet);
 726                                 break;
 727                         }
 728
 729                         // Drop this subnet if is a subnet of another subnet
 730                         if (loc_network_is_subnet_of(subnet, subnet_to_check)) {
 731                                 passed = 0;
 732                                 loc_network_unref(subnet);
 733                                 break;
 734                         }
 735
 736                         // Break it down if it overlaps
 737                         if (loc_network_overlaps(subnet_to_check, subnet)) {
 738                                 passed = 0;
 739
 740                                 struct loc_network_list* excluded = loc_network_exclude(subnet_to_check, subnet);
 741                                 if (excluded) {
 742                                         loc_network_list_merge(to_check, excluded);
 743                                         loc_network_list_unref(excluded);
 744                                 }
 745
 746                                 loc_network_unref(subnet);
 747                                 break;
 748                         }
 749
 750                         loc_network_unref(subnet);
 751                 }
 752
 753                 if (passed) {
 754                         r = loc_network_list_push(subnets, subnet_to_check);
 755                 }
 756
 757                 loc_network_unref(subnet_to_check);
 758         }
 759
 760         loc_network_list_unref(to_check);
 761
 762         return subnets;
 763 }
 764
 765 LOC_EXPORT int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
 766         // Add country code
 767         loc_country_code_copy(dbobj->country_code, network->country_code);
 768
 769         // Add ASN
 770         dbobj->asn = htobe32(network->asn);
 771
 772         // Flags
 773         dbobj->flags = htobe16(network->flags);
 774
 775         return 0;
 776 }
 777
 778 LOC_EXPORT int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network,
 779                 struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) {
 780         char country_code[3] = "\0\0";
 781
 782         int r = loc_network_new(ctx, network, address, prefix);
 783         if (r) {
 784                 ERROR(ctx, "Could not allocate a new network: %s", strerror(-r));
 785                 return r;
 786         }
 787
 788         // Import country code
 789         loc_country_code_copy(country_code, dbobj->country_code);
 790
 791         r = loc_network_set_country_code(*network, country_code);
 792         if (r) {
 793                 ERROR(ctx, "Could not set country code: %s\n", country_code);
 794                 return r;
 795         }
 796
 797         // Import ASN
 798         uint32_t asn = be32toh(dbobj->asn);
 799         r = loc_network_set_asn(*network, asn);
 800         if (r) {
 801                 ERROR(ctx, "Could not set ASN: %d\n", asn);
 802                 return r;
 803         }
 804
 805         // Import flags
 806         int flags = be16toh(dbobj->flags);
 807         r = loc_network_set_flag(*network, flags);
 808         if (r) {
 809                 ERROR(ctx, "Could not set flags: %d\n", flags);
 810                 return r;
 811         }
 812
 813         return 0;
 814 }
 815
 816 struct loc_network_tree {
 817         struct loc_ctx* ctx;
 818         int refcount;
 819
 820         struct loc_network_tree_node* root;
 821 };
 822
 823 struct loc_network_tree_node {
 824         struct loc_ctx* ctx;
 825         int refcount;
 826
 827         struct loc_network_tree_node* zero;
 828         struct loc_network_tree_node* one;
 829
 830         struct loc_network* network;
 831 };
 832
 833 LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
 834         struct loc_network_tree* t = calloc(1, sizeof(*t));
 835         if (!t)
 836                 return -ENOMEM;
 837
 838         t->ctx = loc_ref(ctx);
 839         t->refcount = 1;
 840
 841         // Create the root node
 842         int r = loc_network_tree_node_new(ctx, &t->root);
 843         if (r) {
 844                 loc_network_tree_unref(t);
 845                 return r;
 846         }
 847
 848         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
 849         *tree = t;
 850         return 0;
 851 }
 852
 853 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
 854         return loc_network_tree_node_ref(tree->root);
 855 }
 856
 857 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
 858         struct loc_network_tree_node** n;
 859
 860         if (path == 0)
 861                 n = &node->zero;
 862         else
 863                 n = &node->one;
 864
 865         // If the desired node doesn't exist, yet, we will create it
 866         if (*n == NULL) {
 867                 int r = loc_network_tree_node_new(node->ctx, n);
 868                 if (r)
 869                         return NULL;
 870         }
 871
 872         return *n;
 873 }
 874
 875 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
 876         struct loc_network_tree_node* node = tree->root;
 877
 878         for (unsigned int i = 0; i < prefix; i++) {
 879                 // Check if the ith bit is one or zero
 880                 node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i));
 881         }
 882
 883         return node;
 884 }
 885
 886 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
 887                 int(*filter_callback)(struct loc_network* network, void* data),
 888                 int(*callback)(struct loc_network* network, void* data), void* data) {
 889         int r;
 890
 891         // Finding a network ends the walk here
 892         if (node->network) {
 893                 if (filter_callback) {
 894                         int f = filter_callback(node->network, data);
 895                         if (f < 0)
 896                                 return f;
 897
 898                         // Skip network if filter function returns value greater than zero
 899                         if (f > 0)
 900                                 return 0;
 901                 }
 902
 903                 r = callback(node->network, data);
 904                 if (r)
 905                         return r;
 906         }
 907
 908         // Walk down on the left side of the tree first
 909         if (node->zero) {
 910                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
 911                 if (r)
 912                         return r;
 913         }
 914
 915         // Then walk on the other side
 916         if (node->one) {
 917                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
 918                 if (r)
 919                         return r;
 920         }
 921
 922         return 0;
 923 }
 924
 925 LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
 926                 int(*filter_callback)(struct loc_network* network, void* data),
 927                 int(*callback)(struct loc_network* network, void* data), void* data) {
 928         return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
 929 }
 930
 931 static void loc_network_tree_free(struct loc_network_tree* tree) {
 932         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
 933
 934         loc_network_tree_node_unref(tree->root);
 935
 936         loc_unref(tree->ctx);
 937         free(tree);
 938 }
 939
 940 LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
 941         if (--tree->refcount > 0)
 942                 return tree;
 943
 944         loc_network_tree_free(tree);
 945         return NULL;
 946 }
 947
 948 static int __loc_network_tree_dump(struct loc_network* network, void* data) {
 949         DEBUG(network->ctx, "Dumping network at %p\n", network);
 950
 951         char* s = loc_network_str(network);
 952         if (!s)
 953                 return 1;
 954
 955         INFO(network->ctx, "%s\n", s);
 956         free(s);
 957
 958         return 0;
 959 }
 960
 961 LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
 962         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
 963
 964         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
 965 }
 966
 967 LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
 968         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
 969
 970         struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
 971                         &network->first_address, network->prefix);
 972         if (!node) {
 973                 ERROR(tree->ctx, "Could not find a node\n");
 974                 return -ENOMEM;
 975         }
 976
 977         // Check if node has not been set before
 978         if (node->network) {
 979                 DEBUG(tree->ctx, "There is already a network at this path\n");
 980                 return -EBUSY;
 981         }
 982
 983         // Point node to the network
 984         node->network = loc_network_ref(network);
 985
 986         return 0;
 987 }
 988
 989 static int __loc_network_tree_count(struct loc_network* network, void* data) {
 990         size_t* counter = (size_t*)data;
 991
 992         // Increase the counter for each network
 993         counter++;
 994
 995         return 0;
 996 }
 997
 998 LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
 999         size_t counter = 0;
1000
1001         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
1002         if (r)
1003                 return r;
1004
1005         return counter;
1006 }
1007
1008 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
1009         size_t counter = 1;
1010
1011         if (node->zero)
1012                 counter += __loc_network_tree_count_nodes(node->zero);
1013
1014         if (node->one)
1015                 counter += __loc_network_tree_count_nodes(node->one);
1016
1017         return counter;
1018 }
1019
1020 LOC_EXPORT size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
1021         return __loc_network_tree_count_nodes(tree->root);
1022 }
1023
1024 LOC_EXPORT int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
1025         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
1026         if (!n)
1027                 return -ENOMEM;
1028
1029         n->ctx = loc_ref(ctx);
1030         n->refcount = 1;
1031
1032         n->zero = n->one = NULL;
1033
1034         DEBUG(n->ctx, "Network node allocated at %p\n", n);
1035         *node = n;
1036         return 0;
1037 }
1038
1039 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
1040         if (node)
1041                 node->refcount++;
1042
1043         return node;
1044 }
1045
1046 static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
1047         DEBUG(node->ctx, "Releasing network node at %p\n", node);
1048
1049         if (node->network)
1050                 loc_network_unref(node->network);
1051
1052         if (node->zero)
1053                 loc_network_tree_node_unref(node->zero);
1054
1055         if (node->one)
1056                 loc_network_tree_node_unref(node->one);
1057
1058         loc_unref(node->ctx);
1059         free(node);
1060 }
1061
1062 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
1063         if (!node)
1064                 return NULL;
1065
1066         if (--node->refcount > 0)
1067                 return node;
1068
1069         loc_network_tree_node_free(node);
1070         return NULL;
1071 }
1072
1073 LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
1074         if (index == 0)
1075                 node = node->zero;
1076         else
1077                 node = node->one;
1078
1079         if (!node)
1080                 return NULL;
1081
1082         return loc_network_tree_node_ref(node);
1083 }
1084
1085 LOC_EXPORT int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
1086         return (!!node->network);
1087 }
1088
1089 LOC_EXPORT struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
1090         return loc_network_ref(node->network);
1091 }
1092
1093 // List
1094
1095 struct loc_network_list {
1096         struct loc_ctx* ctx;
1097         int refcount;
1098
1099         struct loc_network* list[1024];
1100         size_t size;
1101         size_t max_size;
1102 };
1103
1104 LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx,
1105                 struct loc_network_list** list) {
1106         struct loc_network_list* l = calloc(1, sizeof(*l));
1107         if (!l)
1108                 return -ENOMEM;
1109
1110         l->ctx = loc_ref(ctx);
1111         l->refcount = 1;
1112
1113         // Do not allow this list to grow larger than this
1114         l->max_size = 1024;
1115
1116         DEBUG(l->ctx, "Network list allocated at %p\n", l);
1117         *list = l;
1118         return 0;
1119 }
1120
1121 LOC_EXPORT struct loc_network_list* loc_network_list_ref(struct loc_network_list* list) {
1122         list->refcount++;
1123
1124         return list;
1125 }
1126
1127 static void loc_network_list_free(struct loc_network_list* list) {
1128         DEBUG(list->ctx, "Releasing network list at %p\n", list);
1129
1130         for (unsigned int i = 0; i < list->size; i++)
1131                 loc_network_unref(list->list[i]);
1132
1133         loc_unref(list->ctx);
1134         free(list);
1135 }
1136
1137 LOC_EXPORT struct loc_network_list* loc_network_list_unref(struct loc_network_list* list) {
1138         if (!list)
1139                 return NULL;
1140
1141         if (--list->refcount > 0)
1142                 return list;
1143
1144         loc_network_list_free(list);
1145         return NULL;
1146 }
1147
1148 LOC_EXPORT size_t loc_network_list_size(struct loc_network_list* list) {
1149         return list->size;
1150 }
1151
1152 LOC_EXPORT int loc_network_list_empty(struct loc_network_list* list) {
1153         return list->size == 0;
1154 }
1155
1156 LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) {
1157         for (unsigned int i = 0; i < list->size; i++)
1158                 loc_network_unref(list->list[i]);
1159
1160         list->size = 0;
1161 }
1162
1163 LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) {
1164         struct loc_network* network;
1165         char* s;
1166
1167         for (unsigned int i = 0; i < list->size; i++) {
1168                 network = list->list[i];
1169
1170                 s = loc_network_str(network);
1171
1172                 INFO(list->ctx, "%s\n", s);
1173                 free(s);
1174         }
1175 }
1176
1177 LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
1178         // Check index
1179         if (index >= list->size)
1180                 return NULL;
1181
1182         return loc_network_ref(list->list[index]);
1183 }
1184
1185 LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
1186         // Do not add networks that are already on the list
1187         if (loc_network_list_contains(list, network))
1188                 return 0;
1189
1190         // Check if we have space left
1191         if (list->size == list->max_size) {
1192                 ERROR(list->ctx, "%p: Could not push network onto the stack: Stack full\n", list);
1193                 return -ENOMEM;
1194         }
1195
1196         DEBUG(list->ctx, "%p: Pushing network %p onto stack\n", list, network);
1197
1198         list->list[list->size++] = loc_network_ref(network);
1199
1200         return 0;
1201 }
1202
1203 LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
1204         // Return nothing when empty
1205         if (loc_network_list_empty(list)) {
1206                 DEBUG(list->ctx, "%p: Popped empty stack\n", list);
1207                 return NULL;
1208         }
1209
1210         struct loc_network* network = list->list[--list->size];
1211
1212         DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
1213
1214         return network;
1215 }
1216
1217 LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
1218         for (unsigned int i = 0; i < list->size; i++) {
1219                 if (loc_network_eq(list->list[i], network))
1220                         return 1;
1221         }
1222
1223         return 0;
1224 }
1225
1226 static void loc_network_list_swap(struct loc_network_list* list, unsigned int i1, unsigned int i2) {
1227         // Do nothing for invalid indices
1228         if (i1 >= list->size || i2 >= list->size)
1229                 return;
1230
1231         struct loc_network* network1 = list->list[i1];
1232         struct loc_network* network2 = list->list[i2];
1233
1234         list->list[i1] = network2;
1235         list->list[i2] = network1;
1236 }
1237
1238 LOC_EXPORT void loc_network_list_reverse(struct loc_network_list* list) {
1239         unsigned int i = 0;
1240         unsigned int j = list->size - 1;
1241
1242         while (i < j) {
1243                 loc_network_list_swap(list, i++, j--);
1244         }
1245 }
1246
1247 LOC_EXPORT void loc_network_list_sort(struct loc_network_list* list) {
1248         unsigned int n = list->size;
1249         int swapped;
1250
1251         do {
1252                 swapped = 0;
1253
1254                 for (unsigned int i = 1; i < n; i++) {
1255                         if (loc_network_gt(list->list[i-1], list->list[i]) > 0) {
1256                                 loc_network_list_swap(list, i-1, i);
1257                                 swapped = 1;
1258                         }
1259                 }
1260
1261                 n--;
1262         } while (swapped);
1263 }
1264
1265 LOC_EXPORT int loc_network_list_merge(
1266                 struct loc_network_list* self, struct loc_network_list* other) {
1267         int r;
1268
1269         for (unsigned int i = 0; i < other->size; i++) {
1270                 r = loc_network_list_push(self, other->list[i]);
1271                 if (r)
1272                         return r;
1273         }
1274
1275         return 0;
1276 }