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         node = loc_network_tree_get_path(tree, &network->first_address, network->prefix);
 890         if (!node) {
 891                 DEBUG(tree->ctx, "Network was not found in tree\n");
 892                 return 1;
 893         }
 894
 895         // Drop the network
 896         if (node->network) {
 897                 loc_network_unref(node->network);
 898                 node->network = NULL;
 899         }
 900
 901         // Mark the node as deleted if it was a leaf
 902         if (!node->zero && !node->one)
 903                 node->deleted = 1;
 904
 905         return 0;
 906 }
 907
 908 static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
 909         size_t counter = 1;
 910
 911         // Don't count deleted nodes
 912         if (node->deleted)
 913                 return 0;
 914
 915         if (node->zero)
 916                 counter += __loc_network_tree_count_nodes(node->zero);
 917
 918         if (node->one)
 919                 counter += __loc_network_tree_count_nodes(node->one);
 920
 921         return counter;
 922 }
 923
 924 size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
 925         return __loc_network_tree_count_nodes(tree->root);
 926 }
 927
 928 int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
 929         struct loc_network_tree_node* n = calloc(1, sizeof(*n));
 930         if (!n)
 931                 return -ENOMEM;
 932
 933         n->ctx = loc_ref(ctx);
 934         n->refcount = 1;
 935
 936         n->zero = n->one = NULL;
 937
 938         DEBUG(n->ctx, "Network node allocated at %p\n", n);
 939         *node = n;
 940         return 0;
 941 }
 942
 943 struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
 944         if (node)
 945                 node->refcount++;
 946
 947         return node;
 948 }
 949
 950 static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
 951         DEBUG(node->ctx, "Releasing network node at %p\n", node);
 952
 953         if (node->network)
 954                 loc_network_unref(node->network);
 955
 956         if (node->zero)
 957                 loc_network_tree_node_unref(node->zero);
 958
 959         if (node->one)
 960                 loc_network_tree_node_unref(node->one);
 961
 962         loc_unref(node->ctx);
 963         free(node);
 964 }
 965
 966 struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
 967         if (--node->refcount > 0)
 968                 return node;
 969
 970         loc_network_tree_node_free(node);
 971         return NULL;
 972 }
 973
 974 struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
 975         if (index == 0)
 976                 node = node->zero;
 977         else
 978                 node = node->one;
 979
 980         if (!node)
 981                 return NULL;
 982
 983         return loc_network_tree_node_ref(node);
 984 }
 985
 986 int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
 987         return (!!node->network);
 988 }
 989
 990 struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
 991         return loc_network_ref(node->network);
 992 }
 993
 994 /*
 995         Merge the tree!
 996 */
 997
 998 struct loc_network_tree_merge_ctx {
 999         struct loc_network_tree* tree;
1000         struct loc_network_list* networks;
1001         unsigned int merged;
1002 };
1003
1004 static int loc_network_tree_merge_step(struct loc_network* network, void* data) {
1005         struct loc_network_tree_merge_ctx* ctx = (struct loc_network_tree_merge_ctx*)data;
1006         struct loc_network* n = NULL;
1007         struct loc_network* m = NULL;
1008         int r;
1009
1010         // How many networks do we have?
1011         size_t i = loc_network_list_size(ctx->networks);
1012
1013         // If the list is empty, just add the network
1014         if (i == 0)
1015                 return loc_network_list_push(ctx->networks, network);
1016
1017         while (i--) {
1018                 // Fetch the last network of the list
1019                 n = loc_network_list_get(ctx->networks, i);
1020
1021                 // Try to merge the two networks
1022                 r = loc_network_merge(&m, n, network);
1023                 if (r)
1024                         goto ERROR;
1025
1026                 // Did we get a result?
1027                 if (m) {
1028                         DEBUG(ctx->tree->ctx, "Merged networks %s + %s -> %s\n",
1029                                 loc_network_str(n), loc_network_str(network), loc_network_str(m));
1030
1031                         // Add the new network
1032                         r = loc_network_tree_add_network(ctx->tree, m);
1033                         switch (r) {
1034                                 case 0:
1035                                         break;
1036
1037                                 // There might already be a network
1038                                 case -EBUSY:
1039                                         r = 0;
1040                                         goto ERROR;
1041
1042                                 default:
1043                                         goto ERROR;
1044                         }
1045
1046                         // It would be nice if we could remove the networks that we just merged,
1047                         // but removing objects from the tree while walking through it is something
1048                         // we currently don't support. The deduplication check will however find
1049                         // and remove these networks.
1050
1051                         // Add the new network to the stack
1052                         r = loc_network_list_push(ctx->networks, m);
1053                         if (r)
1054                                 goto ERROR;
1055
1056                         // Remove the previous network from the stack
1057                         r = loc_network_list_remove(ctx->networks, n);
1058                         if (r)
1059                                 goto ERROR;
1060
1061                         // Count merges
1062                         ctx->merged++;
1063
1064                         // Try merging the new network with others
1065                         r = loc_network_tree_merge_step(m, data);
1066                         if (r)
1067                                 goto ERROR;
1068
1069                         loc_network_unref(m);
1070                         m = NULL;
1071
1072                         // Once we have found a merge, we are done
1073                         break;
1074
1075                 // If we could not merge the two networks, we add the current one
1076                 } else {
1077                         r = loc_network_list_push(ctx->networks, network);
1078                         if (r)
1079                                 goto ERROR;
1080                 }
1081
1082                 loc_network_unref(n);
1083                 n = NULL;
1084         }
1085
1086         const unsigned int prefix = loc_network_prefix(network);
1087
1088         // Remove any networks that we cannot merge
1089         loc_network_list_remove_with_prefix_smaller_than(ctx->networks, prefix);
1090
1091 ERROR:
1092         if (m)
1093                 loc_network_unref(m);
1094         if (n)
1095                 loc_network_unref(n);
1096
1097         return r;
1098 }
1099
1100 static int loc_network_tree_merge(struct loc_network_tree* tree) {
1101         struct loc_network_tree_merge_ctx ctx = {
1102                 .tree     = tree,
1103                 .networks = NULL,
1104                 .merged   = 0,
1105         };
1106         int r;
1107
1108         // Create a new list
1109         r = loc_network_list_new(tree->ctx, &ctx.networks);
1110         if (r)
1111                 goto ERROR;
1112
1113         // Walk through the entire tree
1114         r = loc_network_tree_walk(tree, NULL, loc_network_tree_merge_step, &ctx);
1115         if (r)
1116                 goto ERROR;
1117
1118         DEBUG(tree->ctx, "%u network(s) have been merged\n", ctx.merged);
1119
1120 ERROR:
1121         if (ctx.networks)
1122                 loc_network_list_unref(ctx.networks);
1123
1124         return r;
1125 }
1126
1127 /*
1128         Deduplicate the tree
1129 */
1130
1131 struct loc_network_tree_dedup_ctx {
1132         struct loc_network_tree* tree;
1133         struct loc_network* network;
1134         unsigned int removed;
1135 };
1136
1137 static int loc_network_tree_dedup_step(struct loc_network* network, void* data) {
1138         struct loc_network_tree_dedup_ctx* ctx = (struct loc_network_tree_dedup_ctx*)data;
1139
1140         // First call when we have not seen any networks, yet
1141         if (!ctx->network) {
1142                 ctx->network = loc_network_ref(network);
1143                 return 0;
1144         }
1145
1146         // If network is a subnet of ctx->network, and all properties match,
1147         // we can drop the network.
1148         if (loc_network_is_subnet(ctx->network, network)) {
1149                 if (loc_network_properties_cmp(ctx->network, network) == 0) {
1150                         // Increment counter
1151                         ctx->removed++;
1152
1153                         // Remove the network
1154                         return loc_network_tree_delete_network(ctx->tree, network);
1155                 }
1156
1157                 return 0;
1158         }
1159
1160         // Drop the reference to the previous network
1161         if (ctx->network)
1162                 loc_network_unref(ctx->network);
1163         ctx->network = loc_network_ref(network);
1164
1165         return 0;
1166 }
1167
1168 static int loc_network_tree_dedup(struct loc_network_tree* tree) {
1169         struct loc_network_tree_dedup_ctx ctx = {
1170                 .tree    = tree,
1171                 .network = NULL,
1172                 .removed = 0,
1173         };
1174         int r;
1175
1176         // Walk through the entire tree
1177         r = loc_network_tree_walk(tree, NULL, loc_network_tree_dedup_step, &ctx);
1178         if (r)
1179                 goto ERROR;
1180
1181         DEBUG(tree->ctx, "%u network(s) have been removed\n", ctx.removed);
1182
1183 ERROR:
1184         if (ctx.network)
1185                 loc_network_unref(ctx.network);
1186
1187         return r;
1188 }
1189
1190 static int loc_network_tree_delete_node(struct loc_network_tree_node** node) {
1191         struct loc_network_tree_node* n = *node;
1192         int r0 = 1;
1193         int r1 = 1;
1194
1195         // Return for nodes that have already been deleted
1196         if (n->deleted)
1197                 goto DELETE;
1198
1199         // Delete zero
1200         if (n->zero) {
1201                 r0 = loc_network_tree_delete_node(&n->zero);
1202                 if (r0 < 0)
1203                         return r0;
1204         }
1205
1206         // Delete one
1207         if (n->one) {
1208                 r1 = loc_network_tree_delete_node(&n->one);
1209                 if (r1 < 0)
1210                         return r1;
1211         }
1212
1213         // Don't delete this node if we are a leaf
1214         if (n->network)
1215                 return 0;
1216
1217         // Don't delete this node if has child nodes that we need
1218         if (!r0 || !r1)
1219                 return 0;
1220
1221 DELETE:
1222         // It is now safe to delete the node
1223         loc_network_tree_node_unref(n);
1224         *node = NULL;
1225
1226         return 1;
1227 }
1228
1229 static int loc_network_tree_delete_nodes(struct loc_network_tree* tree) {
1230         int r;
1231
1232         r = loc_network_tree_delete_node(&tree->root);
1233         if (r < 0)
1234                 return r;
1235
1236         // Undelete the root node in case the entire tree got deleted
1237         tree->root->deleted = 0;
1238
1239         return 0;
1240 }
1241
1242 int loc_network_tree_cleanup(struct loc_network_tree* tree) {
1243         int r;
1244
1245         // Deduplicate the tree so finding merges is quicker
1246         r = loc_network_tree_dedup(tree);
1247         if (r)
1248                 return r;
1249
1250         // Merge networks
1251         r = loc_network_tree_merge(tree);
1252         if (r) {
1253                 ERROR(tree->ctx, "Could not merge networks: %m\n");
1254                 return r;
1255         }
1256
1257         // Remove duplicates once again
1258         r = loc_network_tree_dedup(tree);
1259         if (r)
1260                 return r;
1261
1262         // Delete any unneeded nodes
1263         r = loc_network_tree_delete_nodes(tree);
1264         if (r)
1265                 return r;
1266
1267         return 0;
1268 }