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