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 <libloc/libloc.h>
  29 #include <libloc/compat.h>
  30 #include <libloc/country.h>
  31 #include <libloc/network.h>
  32 #include <libloc/network-list.h>
  33 #include <libloc/private.h>
  34
  35 struct loc_network {
  36         struct loc_ctx* ctx;
  37         int refcount;
  38
  39         int family;
  40         struct in6_addr first_address;
  41         struct in6_addr last_address;
  42         unsigned int prefix;
  43
  44         char country_code[3];
  45         uint32_t asn;
  46         enum loc_network_flags flags;
  47 };
  48
  49 static int valid_prefix(struct in6_addr* address, unsigned int prefix) {
  50         // The prefix cannot be larger than 128 bits
  51         if (prefix > 128)
  52                 return 1;
  53
  54         // And the prefix cannot be zero
  55         if (prefix == 0)
  56                 return 1;
  57
  58         // For IPv4-mapped addresses the prefix has to be 96 or lager
  59         if (IN6_IS_ADDR_V4MAPPED(address) && prefix <= 96)
  60                 return 1;
  61
  62         return 0;
  63 }
  64
  65 LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
  66                 struct in6_addr* address, unsigned int prefix) {
  67         // Address cannot be unspecified
  68         if (IN6_IS_ADDR_UNSPECIFIED(address)) {
  69                 DEBUG(ctx, "Start address is unspecified\n");
  70                 return -EINVAL;
  71         }
  72
  73         // Address cannot be loopback
  74         if (IN6_IS_ADDR_LOOPBACK(address)) {
  75                 DEBUG(ctx, "Start address is loopback address\n");
  76                 return -EINVAL;
  77         }
  78
  79         // Address cannot be link-local
  80         if (IN6_IS_ADDR_LINKLOCAL(address)) {
  81                 DEBUG(ctx, "Start address cannot be link-local\n");
  82                 return -EINVAL;
  83         }
  84
  85         // Address cannot be site-local
  86         if (IN6_IS_ADDR_SITELOCAL(address)) {
  87                 DEBUG(ctx, "Start address cannot be site-local\n");
  88                 return -EINVAL;
  89         }
  90
  91         // Validate the prefix
  92         if (valid_prefix(address, prefix) != 0) {
  93                 DEBUG(ctx, "Invalid prefix: %u\n", prefix);
  94                 return -EINVAL;
  95         }
  96
  97         struct loc_network* n = calloc(1, sizeof(*n));
  98         if (!n)
  99                 return -ENOMEM;
 100
 101         n->ctx = loc_ref(ctx);
 102         n->refcount = 1;
 103
 104         // Store the prefix
 105         n->prefix = prefix;
 106
 107         // Convert the prefix into a bitmask
 108         struct in6_addr bitmask = loc_prefix_to_bitmask(n->prefix);
 109
 110         // Store the first and last address in the network
 111         n->first_address = loc_address_and(address, &bitmask);
 112         n->last_address  = loc_address_or(&n->first_address, &bitmask);
 113
 114         // Set family
 115         n->family = loc_address_family(&n->first_address);
 116
 117         DEBUG(n->ctx, "Network allocated at %p\n", n);
 118         *network = n;
 119         return 0;
 120 }
 121
 122 LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
 123                 const char* address_string) {
 124         struct in6_addr first_address;
 125         char* prefix_string;
 126         unsigned int prefix = 128;
 127         int r = -EINVAL;
 128
 129         DEBUG(ctx, "Attempting to parse network %s\n", address_string);
 130
 131         // Make a copy of the string to work on it
 132         char* buffer = strdup(address_string);
 133         address_string = prefix_string = buffer;
 134
 135         // Split address and prefix
 136         address_string = strsep(&prefix_string, "/");
 137
 138         DEBUG(ctx, "  Split into address = %s, prefix = %s\n", address_string, prefix_string);
 139
 140         // Parse the address
 141         r = loc_parse_address(ctx, address_string, &first_address);
 142         if (r) {
 143                 DEBUG(ctx, "The address could not be parsed\n");
 144                 goto FAIL;
 145         }
 146
 147         // If a prefix was given, we will try to parse it
 148         if (prefix_string) {
 149                 // Convert prefix to integer
 150                 prefix = strtol(prefix_string, NULL, 10);
 151
 152                 if (!prefix) {
 153                         DEBUG(ctx, "The prefix was not parsable: %s\n", prefix_string);
 154                         goto FAIL;
 155                 }
 156
 157                 // Map the prefix to IPv6 if needed
 158                 if (IN6_IS_ADDR_V4MAPPED(&first_address))
 159                         prefix += 96;
 160         }
 161
 162 FAIL:
 163         // Free temporary buffer
 164         free(buffer);
 165
 166         // Exit if the parsing was unsuccessful
 167         if (r)
 168                 return r;
 169
 170         // Create a new network
 171         return loc_network_new(ctx, network, &first_address, prefix);
 172 }
 173
 174 LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
 175         network->refcount++;
 176
 177         return network;
 178 }
 179
 180 static void loc_network_free(struct loc_network* network) {
 181         DEBUG(network->ctx, "Releasing network at %p\n", network);
 182
 183         loc_unref(network->ctx);
 184         free(network);
 185 }
 186
 187 LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
 188         if (!network)
 189                 return NULL;
 190
 191         if (--network->refcount > 0)
 192                 return network;
 193
 194         loc_network_free(network);
 195         return NULL;
 196 }
 197
 198 static int format_ipv6_address(const struct in6_addr* address, char* string, size_t length) {
 199         const char* ret = inet_ntop(AF_INET6, address, string, length);
 200         if (!ret)
 201                 return -1;
 202
 203         return 0;
 204 }
 205
 206 static int format_ipv4_address(const struct in6_addr* address, char* string, size_t length) {
 207         struct in_addr ipv4_address;
 208         ipv4_address.s_addr = address->s6_addr32[3];
 209
 210         const char* ret = inet_ntop(AF_INET, &ipv4_address, string, length);
 211         if (!ret)
 212                 return -1;
 213
 214         return 0;
 215 }
 216
 217 LOC_EXPORT char* loc_network_str(struct loc_network* network) {
 218         int r;
 219         const size_t length = INET6_ADDRSTRLEN + 4;
 220
 221         char* string = malloc(length);
 222         if (!string)
 223                 return NULL;
 224
 225         unsigned int prefix = network->prefix;
 226
 227         switch (network->family) {
 228                 case AF_INET6:
 229                         r = format_ipv6_address(&network->first_address, string, length);
 230                         break;
 231
 232                 case AF_INET:
 233                         r = format_ipv4_address(&network->first_address, string, length);
 234                         prefix -= 96;
 235                         break;
 236
 237                 default:
 238                         r = -1;
 239                         break;
 240         }
 241
 242         if (r) {
 243                 ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno));
 244                 free(string);
 245
 246                 return NULL;
 247         }
 248
 249         // Append prefix
 250         sprintf(string + strlen(string), "/%u", prefix);
 251
 252         return string;
 253 }
 254
 255 LOC_EXPORT int loc_network_address_family(struct loc_network* network) {
 256         return network->family;
 257 }
 258
 259 LOC_EXPORT unsigned int loc_network_prefix(struct loc_network* network) {
 260         switch (network->family) {
 261                 case AF_INET6:
 262                         return network->prefix;
 263
 264                 case AF_INET:
 265                         return network->prefix - 96;
 266         }
 267
 268         return 0;
 269 }
 270
 271 static char* loc_network_format_address(struct loc_network* network, const struct in6_addr* address) {
 272         const size_t length = INET6_ADDRSTRLEN;
 273
 274         char* string = malloc(length);
 275         if (!string)
 276                 return NULL;
 277
 278         int r = 0;
 279
 280         switch (network->family) {
 281                 case AF_INET6:
 282                         r = format_ipv6_address(address, string, length);
 283                         break;
 284
 285                 case AF_INET:
 286                         r = format_ipv4_address(address, string, length);
 287                         break;
 288
 289                 default:
 290                         r = -1;
 291                         break;
 292         }
 293
 294         if (r) {
 295                 ERROR(network->ctx, "Could not format IP address to string: %s\n", strerror(errno));
 296                 free(string);
 297
 298                 return NULL;
 299         }
 300
 301         return string;
 302 }
 303
 304 LOC_EXPORT const struct in6_addr* loc_network_get_first_address(struct loc_network* network) {
 305         return &network->first_address;
 306 }
 307
 308 LOC_EXPORT char* loc_network_format_first_address(struct loc_network* network) {
 309         return loc_network_format_address(network, &network->first_address);
 310 }
 311
 312 LOC_EXPORT const struct in6_addr* loc_network_get_last_address(struct loc_network* network) {
 313         return &network->last_address;
 314 }
 315
 316 LOC_EXPORT char* loc_network_format_last_address(struct loc_network* network) {
 317         return loc_network_format_address(network, &network->last_address);
 318 }
 319
 320 LOC_EXPORT int loc_network_matches_address(struct loc_network* network, const struct in6_addr* address) {
 321         // Address must be larger than the start address
 322         if (in6_addr_cmp(&network->first_address, address) > 0)
 323                 return 0;
 324
 325         // Address must be smaller than the last address
 326         if (in6_addr_cmp(&network->last_address, address) < 0)
 327                 return 0;
 328
 329         // The address is inside this network
 330         return 1;
 331 }
 332
 333 LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
 334         return network->country_code;
 335 }
 336
 337 LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) {
 338         // Set empty country code
 339         if (!country_code || !*country_code) {
 340                 *network->country_code = '\0';
 341                 return 0;
 342         }
 343
 344         // Check country code
 345         if (!loc_country_code_is_valid(country_code))
 346                 return -EINVAL;
 347
 348         loc_country_code_copy(network->country_code, country_code);
 349
 350         return 0;
 351 }
 352
 353 LOC_EXPORT int loc_network_matches_country_code(struct loc_network* network, const char* country_code) {
 354         // Search for any special flags
 355         const int flag = loc_country_special_code_to_flag(country_code);
 356
 357         // If we found a flag, we will return whether it is set or not
 358         if (flag)
 359                 return loc_network_has_flag(network, flag);
 360
 361         // Check country code
 362         if (!loc_country_code_is_valid(country_code))
 363                 return -EINVAL;
 364
 365         // Check for an exact match
 366         return (network->country_code[0] == country_code[0])
 367                 && (network->country_code[1] == country_code[1]);
 368 }
 369
 370 LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
 371         return network->asn;
 372 }
 373
 374 LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
 375         network->asn = asn;
 376
 377         return 0;
 378 }
 379
 380 LOC_EXPORT int loc_network_has_flag(struct loc_network* network, uint32_t flag) {
 381         return network->flags & flag;
 382 }
 383
 384 LOC_EXPORT int loc_network_set_flag(struct loc_network* network, uint32_t flag) {
 385         network->flags |= flag;
 386
 387         return 0;
 388 }
 389
 390 LOC_EXPORT int loc_network_cmp(struct loc_network* self, struct loc_network* other) {
 391         // Compare address
 392         int r = in6_addr_cmp(&self->first_address, &other->first_address);
 393         if (r)
 394                 return r;
 395
 396         // Compare prefix
 397         if (self->prefix > other->prefix)
 398                 return 1;
 399         else if (self->prefix < other->prefix)
 400                 return -1;
 401
 402         // Both networks are equal
 403         return 0;
 404 }
 405
 406 LOC_EXPORT int loc_network_overlaps(struct loc_network* self, struct loc_network* other) {
 407         // Either of the start addresses must be in the other subnet
 408         if (loc_network_matches_address(self, &other->first_address))
 409                 return 1;
 410
 411         if (loc_network_matches_address(other, &self->first_address))
 412                 return 1;
 413
 414         // Or either of the end addresses is in the other subnet
 415         if (loc_network_matches_address(self, &other->last_address))
 416                 return 1;
 417
 418         if (loc_network_matches_address(other, &self->last_address))
 419                 return 1;
 420
 421         return 0;
 422 }
 423
 424 LOC_EXPORT int loc_network_is_subnet(struct loc_network* self, struct loc_network* other) {
 425         // The prefix must be smaller (this avoids the more complex comparisons later)
 426         if (self->prefix > other->prefix)
 427                 return 0;
 428
 429         // If the start address of the other network is smaller than this network,
 430         // it cannot be a subnet.
 431         if (in6_addr_cmp(&self->first_address, &other->first_address) > 0)
 432                 return 0;
 433
 434         // If the end address of the other network is greater than this network,
 435         // it cannot be a subnet.
 436         if (in6_addr_cmp(&self->last_address, &other->last_address) < 0)
 437                 return 0;
 438
 439         return 1;
 440 }
 441
 442 LOC_EXPORT int loc_network_subnets(struct loc_network* network,
 443                 struct loc_network** subnet1, struct loc_network** subnet2) {
 444         int r;
 445         *subnet1 = NULL;
 446         *subnet2 = NULL;
 447
 448         // New prefix length
 449         unsigned int prefix = network->prefix + 1;
 450
 451         // Check if the new prefix is valid
 452         if (valid_prefix(&network->first_address, prefix))
 453                 return -1;
 454
 455         // Create the first half of the network
 456         r = loc_network_new(network->ctx, subnet1, &network->first_address, prefix);
 457         if (r)
 458                 return r;
 459
 460         // The next subnet starts after the first one
 461         struct in6_addr first_address = address_increment(&(*subnet1)->last_address);
 462
 463         // Create the second half of the network
 464         r = loc_network_new(network->ctx, subnet2, &first_address, prefix);
 465         if (r)
 466                 return r;
 467
 468         // Copy country code
 469         const char* country_code = loc_network_get_country_code(network);
 470         if (country_code) {
 471                 loc_network_set_country_code(*subnet1, country_code);
 472                 loc_network_set_country_code(*subnet2, country_code);
 473         }
 474
 475         // Copy ASN
 476         uint32_t asn = loc_network_get_asn(network);
 477         if (asn) {
 478                 loc_network_set_asn(*subnet1, asn);
 479                 loc_network_set_asn(*subnet2, asn);
 480         }
 481
 482         // Copy flags
 483         loc_network_set_flag(*subnet1, network->flags);
 484         loc_network_set_flag(*subnet2, network->flags);
 485
 486         return 0;
 487 }
 488
 489 static int __loc_network_exclude(struct loc_network* network,
 490                 struct loc_network* other, struct loc_network_list* list) {
 491         struct loc_network* subnet1 = NULL;
 492         struct loc_network* subnet2 = NULL;
 493
 494         int r = loc_network_subnets(network, &subnet1, &subnet2);
 495         if (r)
 496                 goto ERROR;
 497
 498         if (loc_network_cmp(other, subnet1) == 0) {
 499                 r = loc_network_list_push(list, subnet2);
 500                 if (r)
 501                         goto ERROR;
 502
 503         } else if (loc_network_cmp(other, subnet2) == 0) {
 504                 r = loc_network_list_push(list, subnet1);
 505                 if (r)
 506                         goto ERROR;
 507
 508         } else  if (loc_network_is_subnet(subnet1, other)) {
 509                 r = loc_network_list_push(list, subnet2);
 510                 if (r)
 511                         goto ERROR;
 512
 513                 r = __loc_network_exclude(subnet1, other, list);
 514                 if (r)
 515                         goto ERROR;
 516
 517         } else if (loc_network_is_subnet(subnet2, other)) {
 518                 r = loc_network_list_push(list, subnet1);
 519                 if (r)
 520                         goto ERROR;
 521
 522                 r = __loc_network_exclude(subnet2, other, list);
 523                 if (r)
 524                         goto ERROR;
 525
 526         } else {
 527                 ERROR(network->ctx, "We should never get here\n");
 528                 r = 1;
 529                 goto ERROR;
 530         }
 531
 532 ERROR:
 533         if (subnet1)
 534                 loc_network_unref(subnet1);
 535
 536         if (subnet2)
 537                 loc_network_unref(subnet2);
 538
 539         return r;
 540 }
 541
 542 static int __loc_network_exclude_to_list(struct loc_network* self,
 543                 struct loc_network* other, struct loc_network_list* list) {
 544         // Other must be a subnet of self
 545         if (!loc_network_is_subnet(self, other)) {
 546                 DEBUG(self->ctx, "Network %p is not contained in network %p\n", other, self);
 547
 548                 // Exit silently
 549                 return 0;
 550         }
 551
 552         // We cannot perform this operation if both networks equal
 553         if (loc_network_cmp(self, other) == 0) {
 554                 DEBUG(self->ctx, "Networks %p and %p are equal\n", self, other);
 555
 556                 // Exit silently
 557                 return 0;
 558         }
 559
 560         return __loc_network_exclude(self, other, list);
 561 }
 562
 563 LOC_EXPORT struct loc_network_list* loc_network_exclude(
 564                 struct loc_network* self, struct loc_network* other) {
 565         struct loc_network_list* list;
 566
 567 #ifdef ENABLE_DEBUG
 568         char* n1 = loc_network_str(self);
 569         char* n2 = loc_network_str(other);
 570
 571         DEBUG(self->ctx, "Returning %s excluding %s...\n", n1, n2);
 572
 573         free(n1);
 574         free(n2);
 575 #endif
 576
 577         // Create a new list with the result
 578         int r = loc_network_list_new(self->ctx, &list);
 579         if (r) {
 580                 ERROR(self->ctx, "Could not create network list: %d\n", r);
 581
 582                 return NULL;
 583         }
 584
 585         r = __loc_network_exclude_to_list(self, other, list);
 586         if (r) {
 587                 loc_network_list_unref(list);
 588
 589                 return NULL;
 590         }
 591
 592         // Return the result
 593         return list;
 594 }
 595
 596 LOC_EXPORT struct loc_network_list* loc_network_exclude_list(
 597                 struct loc_network* network, struct loc_network_list* list) {
 598         struct loc_network_list* to_check;
 599
 600         // Create a new list with all networks to look at
 601         int r = loc_network_list_new(network->ctx, &to_check);
 602         if (r)
 603                 return NULL;
 604
 605         struct loc_network* subnet = NULL;
 606         struct loc_network_list* subnets = NULL;
 607
 608         for (unsigned int i = 0; i < loc_network_list_size(list); i++) {
 609                 subnet = loc_network_list_get(list, i);
 610
 611                 // Find all excluded networks
 612                 if (!loc_network_list_contains(to_check, subnet)) {
 613                         r = __loc_network_exclude_to_list(network, subnet, to_check);
 614                         if (r) {
 615                                 loc_network_list_unref(to_check);
 616                                 loc_network_unref(subnet);
 617
 618                                 return NULL;
 619                         }
 620                 }
 621
 622                 // Cleanup
 623                 loc_network_unref(subnet);
 624         }
 625
 626         r = loc_network_list_new(network->ctx, &subnets);
 627         if (r) {
 628                 loc_network_list_unref(to_check);
 629                 return NULL;
 630         }
 631
 632         off_t smallest_subnet = 0;
 633
 634         while (!loc_network_list_empty(to_check)) {
 635                 struct loc_network* subnet_to_check = loc_network_list_pop_first(to_check);
 636
 637                 // Check whether the subnet to check is part of the input list
 638                 if (loc_network_list_contains(list, subnet_to_check)) {
 639                         loc_network_unref(subnet_to_check);
 640                         continue;
 641                 }
 642
 643                 // Marks whether this subnet passed all checks
 644                 int passed = 1;
 645
 646                 for (unsigned int i = smallest_subnet; i < loc_network_list_size(list); i++) {
 647                         subnet = loc_network_list_get(list, i);
 648
 649                         // Drop this subnet if is a subnet of another subnet
 650                         if (loc_network_is_subnet(subnet, subnet_to_check)) {
 651                                 passed = 0;
 652                                 loc_network_unref(subnet);
 653                                 break;
 654                         }
 655
 656                         // Break it down if it overlaps
 657                         if (loc_network_overlaps(subnet, subnet_to_check)) {
 658                                 passed = 0;
 659
 660                                 __loc_network_exclude_to_list(subnet_to_check, subnet, to_check);
 661
 662                                 loc_network_unref(subnet);
 663                                 break;
 664                         }
 665
 666                         // If the subnet is strictly greater, we do not need to continue the search
 667                         r = loc_network_cmp(subnet, subnet_to_check);
 668                         if (r > 0) {
 669                                 loc_network_unref(subnet);
 670                                 break;
 671
 672                         // If it is strictly smaller, we can continue the search from here next
 673                         // time because all networks that are to be checked can only be larger
 674                         // than this one.
 675                         } else if (r < 0) {
 676                                 smallest_subnet = i;
 677                         }
 678
 679                         loc_network_unref(subnet);
 680                 }
 681
 682                 if (passed) {
 683                         r = loc_network_list_push(subnets, subnet_to_check);
 684                 }
 685
 686                 loc_network_unref(subnet_to_check);
 687         }
 688
 689         loc_network_list_unref(to_check);
 690
 691         return subnets;
 692 }
 693
 694 int loc_network_to_database_v1(struct loc_network* network, struct loc_database_network_v1* dbobj) {
 695         // Add country code
 696         loc_country_code_copy(dbobj->country_code, network->country_code);
 697
 698         // Add ASN
 699         dbobj->asn = htobe32(network->asn);
 700
 701         // Flags
 702         dbobj->flags = htobe16(network->flags);
 703
 704         return 0;
 705 }
 706
 707 int loc_network_new_from_database_v1(struct loc_ctx* ctx, struct loc_network** network,
 708                 struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v1* dbobj) {
 709         char country_code[3] = "\0\0";
 710
 711         int r = loc_network_new(ctx, network, address, prefix);
 712         if (r) {
 713                 ERROR(ctx, "Could not allocate a new network: %s", strerror(-r));
 714                 return r;
 715         }
 716
 717         // Import country code
 718         loc_country_code_copy(country_code, dbobj->country_code);
 719
 720         r = loc_network_set_country_code(*network, country_code);
 721         if (r) {
 722                 ERROR(ctx, "Could not set country code: %s\n", country_code);
 723                 return r;
 724         }
 725
 726         // Import ASN
 727         uint32_t asn = be32toh(dbobj->asn);
 728         r = loc_network_set_asn(*network, asn);
 729         if (r) {
 730                 ERROR(ctx, "Could not set ASN: %d\n", asn);
 731                 return r;
 732         }
 733
 734         // Import flags
 735         int flags = be16toh(dbobj->flags);
 736         r = loc_network_set_flag(*network, flags);
 737         if (r) {
 738                 ERROR(ctx, "Could not set flags: %d\n", flags);
 739                 return r;
 740         }
 741
 742         return 0;
 743 }
 744
 745 struct loc_network_tree {
 746         struct loc_ctx* ctx;
 747         int refcount;
 748
 749         struct loc_network_tree_node* root;
 750 };
 751
 752 struct loc_network_tree_node {
 753         struct loc_ctx* ctx;
 754         int refcount;
 755
 756         struct loc_network_tree_node* zero;
 757         struct loc_network_tree_node* one;
 758
 759         struct loc_network* network;
 760 };
 761
 762 int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
 763         struct loc_network_tree* t = calloc(1, sizeof(*t));
 764         if (!t)
 765                 return -ENOMEM;
 766
 767         t->ctx = loc_ref(ctx);
 768         t->refcount = 1;
 769
 770         // Create the root node
 771         int r = loc_network_tree_node_new(ctx, &t->root);
 772         if (r) {
 773                 loc_network_tree_unref(t);
 774                 return r;
 775         }
 776
 777         DEBUG(t->ctx, "Network tree allocated at %p\n", t);
 778         *tree = t;
 779         return 0;
 780 }
 781
 782 struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
 783         return loc_network_tree_node_ref(tree->root);
 784 }
 785
 786 static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
 787         struct loc_network_tree_node** n;
 788
 789         if (path == 0)
 790                 n = &node->zero;
 791         else
 792                 n = &node->one;
 793
 794         // If the desired node doesn't exist, yet, we will create it
 795         if (*n == NULL) {
 796                 int r = loc_network_tree_node_new(node->ctx, n);
 797                 if (r)
 798                         return NULL;
 799         }
 800
 801         return *n;
 802 }
 803
 804 static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
 805         struct loc_network_tree_node* node = tree->root;
 806
 807         for (unsigned int i = 0; i < prefix; i++) {
 808                 // Check if the ith bit is one or zero
 809                 node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i));
 810         }
 811
 812         return node;
 813 }
 814
 815 static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
 816                 int(*filter_callback)(struct loc_network* network, void* data),
 817                 int(*callback)(struct loc_network* network, void* data), void* data) {
 818         int r;
 819
 820         // Finding a network ends the walk here
 821         if (node->network) {
 822                 if (filter_callback) {
 823                         int f = filter_callback(node->network, data);
 824                         if (f < 0)
 825                                 return f;
 826
 827                         // Skip network if filter function returns value greater than zero
 828                         if (f > 0)
 829                                 return 0;
 830                 }
 831
 832                 r = callback(node->network, data);
 833                 if (r)
 834                         return r;
 835         }
 836
 837         // Walk down on the left side of the tree first
 838         if (node->zero) {
 839                 r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
 840                 if (r)
 841                         return r;
 842         }
 843
 844         // Then walk on the other side
 845         if (node->one) {
 846                 r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
 847                 if (r)
 848                         return r;
 849         }
 850
 851         return 0;
 852 }
 853
 854 int loc_network_tree_walk(struct loc_network_tree* tree,
 855                 int(*filter_callback)(struct loc_network* network, void* data),
 856                 int(*callback)(struct loc_network* network, void* data), void* data) {
 857         return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
 858 }
 859
 860 static void loc_network_tree_free(struct loc_network_tree* tree) {
 861         DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
 862
 863         loc_network_tree_node_unref(tree->root);
 864
 865         loc_unref(tree->ctx);
 866         free(tree);
 867 }
 868
 869 struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
 870         if (--tree->refcount > 0)
 871                 return tree;
 872
 873         loc_network_tree_free(tree);
 874         return NULL;
 875 }
 876
 877 static int __loc_network_tree_dump(struct loc_network* network, void* data) {
 878         DEBUG(network->ctx, "Dumping network at %p\n", network);
 879
 880         char* s = loc_network_str(network);
 881         if (!s)
 882                 return 1;
 883
 884         INFO(network->ctx, "%s\n", s);
 885         free(s);
 886
 887         return 0;
 888 }
 889
 890 int loc_network_tree_dump(struct loc_network_tree* tree) {
 891         DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
 892
 893         return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
 894 }
 895
 896 int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
 897         DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
 898
 899         struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
 900                         &network->first_address, network->prefix);
 901         if (!node) {
 902                 ERROR(tree->ctx, "Could not find a node\n");
 903                 return -ENOMEM;
 904         }
 905
 906         // Check if node has not been set before
 907         if (node->network) {
 908                 DEBUG(tree->ctx, "There is already a network at this path\n");
 909                 return -EBUSY;
 910         }
 911
 912         // Point node to the network
 913         node->network = loc_network_ref(network);
 914
 915         return 0;
 916 }
 917
 918 static int __loc_network_tree_count(struct loc_network* network, void* data) {
 919         size_t* counter = (size_t*)data;
 920
 921         // Increase the counter for each network
 922         counter++;
 923
 924         return 0;
 925 }
 926
 927 size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
 928         size_t counter = 0;
 929
 930         int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
 931         if (r)
 932                 return r;
 933
 934         return counter;
 935 }
 936
 937 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
 938         size_t counter = 1;
 939
 940         if (node->zero)
 941                 counter += __loc_network_tree_count_nodes(node->zero);
 942
 943         if (node->one)
 944                 counter += __loc_network_tree_count_nodes(node->one);
 945
 946         return counter;
 947 }
 948
 949 size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
 950         return __loc_network_tree_count_nodes(tree->root);
 951 }
 952
 953 int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
 954         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
 955         if (!n)
 956                 return -ENOMEM;
 957
 958         n->ctx = loc_ref(ctx);
 959         n->refcount = 1;
 960
 961         n->zero = n->one = NULL;
 962
 963         DEBUG(n->ctx, "Network node allocated at %p\n", n);
 964         *node = n;
 965         return 0;
 966 }
 967
 968 struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
 969         if (node)
 970                 node->refcount++;
 971
 972         return node;
 973 }
 974
 975 static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
 976         DEBUG(node->ctx, "Releasing network node at %p\n", node);
 977
 978         if (node->network)
 979                 loc_network_unref(node->network);
 980
 981         if (node->zero)
 982                 loc_network_tree_node_unref(node->zero);
 983
 984         if (node->one)
 985                 loc_network_tree_node_unref(node->one);
 986
 987         loc_unref(node->ctx);
 988         free(node);
 989 }
 990
 991 struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
 992         if (!node)
 993                 return NULL;
 994
 995         if (--node->refcount > 0)
 996                 return node;
 997
 998         loc_network_tree_node_free(node);
 999         return NULL;
1000 }
1001
1002 struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
1003         if (index == 0)
1004                 node = node->zero;
1005         else
1006                 node = node->one;
1007
1008         if (!node)
1009                 return NULL;
1010
1011         return loc_network_tree_node_ref(node);
1012 }
1013
1014 int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
1015         return (!!node->network);
1016 }
1017
1018 struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
1019         return loc_network_ref(node->network);
1020 }