src/database.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 <ctype.h>
  19 #include <errno.h>
  20 #include <netinet/in.h>
  21 #include <stddef.h>
  22 #include <stdint.h>
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <sys/mman.h>
  27 #include <sys/types.h>
  28 #include <time.h>
  29 #include <unistd.h>
  30
  31 #ifdef HAVE_ENDIAN_H
  32 #  include <endian.h>
  33 #endif
  34
  35 #include <openssl/err.h>
  36 #include <openssl/evp.h>
  37 #include <openssl/pem.h>
  38
  39 #include <libloc/libloc.h>
  40 #include <libloc/address.h>
  41 #include <libloc/as.h>
  42 #include <libloc/as-list.h>
  43 #include <libloc/compat.h>
  44 #include <libloc/country.h>
  45 #include <libloc/country-list.h>
  46 #include <libloc/database.h>
  47 #include <libloc/format.h>
  48 #include <libloc/network.h>
  49 #include <libloc/network-list.h>
  50 #include <libloc/private.h>
  51 #include <libloc/stringpool.h>
  52
  53 struct loc_database {
  54         struct loc_ctx* ctx;
  55         int refcount;
  56
  57         FILE* f;
  58
  59         enum loc_database_version version;
  60         time_t created_at;
  61         off_t vendor;
  62         off_t description;
  63         off_t license;
  64
  65         // Signatures
  66         char* signature1;
  67         size_t signature1_length;
  68         char* signature2;
  69         size_t signature2_length;
  70
  71         // ASes in the database
  72         struct loc_database_as_v1* as_v1;
  73         size_t as_count;
  74
  75         // Network tree
  76         struct loc_database_network_node_v1* network_nodes_v1;
  77         size_t network_nodes_count;
  78
  79         // Networks
  80         struct loc_database_network_v1* networks_v1;
  81         size_t networks_count;
  82
  83         // Countries
  84         struct loc_database_country_v1* countries_v1;
  85         size_t countries_count;
  86
  87         struct loc_stringpool* pool;
  88 };
  89
  90 #define MAX_STACK_DEPTH 256
  91
  92 struct loc_node_stack {
  93         off_t offset;
  94         int i; // Is this node 0 or 1?
  95         int depth;
  96 };
  97
  98 struct loc_database_enumerator {
  99         struct loc_ctx* ctx;
 100         struct loc_database* db;
 101         enum loc_database_enumerator_mode mode;
 102         int refcount;
 103
 104         // Search string
 105         char* string;
 106         struct loc_country_list* countries;
 107         struct loc_as_list* asns;
 108         enum loc_network_flags flags;
 109         int family;
 110
 111         // Flatten output?
 112         int flatten;
 113
 114         // Index of the AS we are looking at
 115         unsigned int as_index;
 116
 117         // Index of the country we are looking at
 118         unsigned int country_index;
 119
 120         // Network state
 121         struct in6_addr network_address;
 122         struct loc_node_stack network_stack[MAX_STACK_DEPTH];
 123         int network_stack_depth;
 124         unsigned int* networks_visited;
 125
 126         // For subnet search and bogons
 127         struct loc_network_list* stack;
 128
 129         // For bogons
 130         struct in6_addr gap6_start;
 131         struct in6_addr gap4_start;
 132 };
 133
 134 static int loc_database_read_magic(struct loc_database* db) {
 135         struct loc_database_magic magic;
 136
 137         // Read from file
 138         size_t bytes_read = fread(&magic, 1, sizeof(magic), db->f);
 139
 140         // Check if we have been able to read enough data
 141         if (bytes_read < sizeof(magic)) {
 142                 ERROR(db->ctx, "Could not read enough data to validate magic bytes\n");
 143                 DEBUG(db->ctx, "Read %zu bytes, but needed %zu\n", bytes_read, sizeof(magic));
 144                 return -ENOMSG;
 145         }
 146
 147         // Compare magic bytes
 148         if (memcmp(LOC_DATABASE_MAGIC, magic.magic, strlen(LOC_DATABASE_MAGIC)) == 0) {
 149                 DEBUG(db->ctx, "Magic value matches\n");
 150
 151                 // Parse version
 152                 db->version = magic.version;
 153
 154                 return 0;
 155         }
 156
 157         ERROR(db->ctx, "Unrecognized file type\n");
 158
 159         // Return an error
 160         return 1;
 161 }
 162
 163 static int loc_database_read_as_section_v1(struct loc_database* db,
 164                 const struct loc_database_header_v1* header) {
 165         off_t as_offset  = be32toh(header->as_offset);
 166         size_t as_length = be32toh(header->as_length);
 167
 168         DEBUG(db->ctx, "Reading AS section from %jd (%zu bytes)\n", (intmax_t)as_offset, as_length);
 169
 170         if (as_length > 0) {
 171                 db->as_v1 = mmap(NULL, as_length, PROT_READ,
 172                         MAP_SHARED, fileno(db->f), as_offset);
 173
 174                 if (db->as_v1 == MAP_FAILED)
 175                         return -errno;
 176         }
 177
 178         db->as_count = as_length / sizeof(*db->as_v1);
 179
 180         INFO(db->ctx, "Read %zu ASes from the database\n", db->as_count);
 181
 182         return 0;
 183 }
 184
 185 static int loc_database_read_network_nodes_section_v1(struct loc_database* db,
 186                 const struct loc_database_header_v1* header) {
 187         off_t network_nodes_offset  = be32toh(header->network_tree_offset);
 188         size_t network_nodes_length = be32toh(header->network_tree_length);
 189
 190         DEBUG(db->ctx, "Reading network nodes section from %jd (%zu bytes)\n",
 191                 (intmax_t)network_nodes_offset, network_nodes_length);
 192
 193         if (network_nodes_length > 0) {
 194                 db->network_nodes_v1 = mmap(NULL, network_nodes_length, PROT_READ,
 195                         MAP_SHARED, fileno(db->f), network_nodes_offset);
 196
 197                 if (db->network_nodes_v1 == MAP_FAILED)
 198                         return -errno;
 199         }
 200
 201         db->network_nodes_count = network_nodes_length / sizeof(*db->network_nodes_v1);
 202
 203         INFO(db->ctx, "Read %zu network nodes from the database\n", db->network_nodes_count);
 204
 205         return 0;
 206 }
 207
 208 static int loc_database_read_networks_section_v1(struct loc_database* db,
 209                 const struct loc_database_header_v1* header) {
 210         off_t networks_offset  = be32toh(header->network_data_offset);
 211         size_t networks_length = be32toh(header->network_data_length);
 212
 213         DEBUG(db->ctx, "Reading networks section from %jd (%zu bytes)\n",
 214                 (intmax_t)networks_offset, networks_length);
 215
 216         if (networks_length > 0) {
 217                 db->networks_v1 = mmap(NULL, networks_length, PROT_READ,
 218                         MAP_SHARED, fileno(db->f), networks_offset);
 219
 220                 if (db->networks_v1 == MAP_FAILED)
 221                         return -errno;
 222         }
 223
 224         db->networks_count = networks_length / sizeof(*db->networks_v1);
 225
 226         INFO(db->ctx, "Read %zu networks from the database\n", db->networks_count);
 227
 228         return 0;
 229 }
 230
 231 static int loc_database_read_countries_section_v1(struct loc_database* db,
 232                 const struct loc_database_header_v1* header) {
 233         off_t countries_offset  = be32toh(header->countries_offset);
 234         size_t countries_length = be32toh(header->countries_length);
 235
 236         DEBUG(db->ctx, "Reading countries section from %jd (%zu bytes)\n",
 237                 (intmax_t)countries_offset, countries_length);
 238
 239         if (countries_length > 0) {
 240                 db->countries_v1 = mmap(NULL, countries_length, PROT_READ,
 241                         MAP_SHARED, fileno(db->f), countries_offset);
 242
 243                 if (db->countries_v1 == MAP_FAILED)
 244                         return -errno;
 245         }
 246
 247         db->countries_count = countries_length / sizeof(*db->countries_v1);
 248
 249         INFO(db->ctx, "Read %zu countries from the database\n",
 250                 db->countries_count);
 251
 252         return 0;
 253 }
 254
 255 static int loc_database_read_signature(struct loc_database* db,
 256                 char** dst, char* src, size_t length) {
 257         // Check for a plausible signature length
 258         if (length > LOC_SIGNATURE_MAX_LENGTH) {
 259                 ERROR(db->ctx, "Signature too long: %zu\n", length);
 260                 return -EINVAL;
 261         }
 262
 263         DEBUG(db->ctx, "Reading signature of %zu bytes\n", length);
 264
 265         // Allocate space
 266         *dst = malloc(length);
 267         if (!*dst)
 268                 return -ENOMEM;
 269
 270         // Copy payload
 271         memcpy(*dst, src, length);
 272
 273         return 0;
 274 }
 275
 276 static int loc_database_read_header_v1(struct loc_database* db) {
 277         struct loc_database_header_v1 header;
 278         int r;
 279
 280         // Read from file
 281         size_t size = fread(&header, 1, sizeof(header), db->f);
 282
 283         if (size < sizeof(header)) {
 284                 ERROR(db->ctx, "Could not read enough data for header\n");
 285                 return -ENOMSG;
 286         }
 287
 288         // Copy over data
 289         db->created_at  = be64toh(header.created_at);
 290         db->vendor      = be32toh(header.vendor);
 291         db->description = be32toh(header.description);
 292         db->license     = be32toh(header.license);
 293
 294         db->signature1_length = be16toh(header.signature1_length);
 295         db->signature2_length = be16toh(header.signature2_length);
 296
 297         // Read signatures
 298         if (db->signature1_length) {
 299                 r = loc_database_read_signature(db, &db->signature1,
 300                         header.signature1, db->signature1_length);
 301                 if (r)
 302                         return r;
 303         }
 304
 305         if (db->signature2_length) {
 306                 r = loc_database_read_signature(db, &db->signature2,
 307                         header.signature2, db->signature2_length);
 308                 if (r)
 309                         return r;
 310         }
 311
 312         // Open pool
 313         off_t pool_offset  = be32toh(header.pool_offset);
 314         size_t pool_length = be32toh(header.pool_length);
 315
 316         r = loc_stringpool_open(db->ctx, &db->pool,
 317                 db->f, pool_length, pool_offset);
 318         if (r)
 319                 return r;
 320
 321         // AS section
 322         r = loc_database_read_as_section_v1(db, &header);
 323         if (r)
 324                 return r;
 325
 326         // Network Nodes
 327         r = loc_database_read_network_nodes_section_v1(db, &header);
 328         if (r)
 329                 return r;
 330
 331         // Networks
 332         r = loc_database_read_networks_section_v1(db, &header);
 333         if (r)
 334                 return r;
 335
 336         // countries
 337         r = loc_database_read_countries_section_v1(db, &header);
 338         if (r)
 339                 return r;
 340
 341         return 0;
 342 }
 343
 344 static int loc_database_read_header(struct loc_database* db) {
 345         DEBUG(db->ctx, "Database version is %u\n", db->version);
 346
 347         switch (db->version) {
 348                 case LOC_DATABASE_VERSION_1:
 349                         return loc_database_read_header_v1(db);
 350
 351                 default:
 352                         ERROR(db->ctx, "Incompatible database version: %u\n", db->version);
 353                         return 1;
 354         }
 355 }
 356
 357 static int loc_database_read(struct loc_database* db, FILE* f) {
 358         clock_t start = clock();
 359
 360         int fd = fileno(f);
 361
 362         // Clone file descriptor
 363         fd = dup(fd);
 364         if (!fd) {
 365                 ERROR(db->ctx, "Could not duplicate file descriptor\n");
 366                 return -1;
 367         }
 368
 369         // Reopen the file so that we can keep our own file handle
 370         db->f = fdopen(fd, "r");
 371         if (!db->f) {
 372                 ERROR(db->ctx, "Could not re-open database file\n");
 373                 return -1;
 374         }
 375
 376         // Rewind to the start of the file
 377         rewind(db->f);
 378
 379         // Read magic bytes
 380         int r = loc_database_read_magic(db);
 381         if (r)
 382                 return r;
 383
 384         // Read the header
 385         r = loc_database_read_header(db);
 386         if (r)
 387                 return r;
 388
 389         clock_t end = clock();
 390
 391         INFO(db->ctx, "Opened database in %.4fms\n",
 392                 (double)(end - start) / CLOCKS_PER_SEC * 1000);
 393
 394         return 0;
 395 }
 396
 397 LOC_EXPORT int loc_database_new(struct loc_ctx* ctx, struct loc_database** database, FILE* f) {
 398         // Fail on invalid file handle
 399         if (!f)
 400                 return -EINVAL;
 401
 402         struct loc_database* db = calloc(1, sizeof(*db));
 403         if (!db)
 404                 return -ENOMEM;
 405
 406         // Reference context
 407         db->ctx = loc_ref(ctx);
 408         db->refcount = 1;
 409
 410         DEBUG(db->ctx, "Database object allocated at %p\n", db);
 411
 412         int r = loc_database_read(db, f);
 413         if (r) {
 414                 loc_database_unref(db);
 415                 return r;
 416         }
 417
 418         *database = db;
 419
 420         return 0;
 421 }
 422
 423 LOC_EXPORT struct loc_database* loc_database_ref(struct loc_database* db) {
 424         db->refcount++;
 425
 426         return db;
 427 }
 428
 429 static void loc_database_free(struct loc_database* db) {
 430         int r;
 431
 432         DEBUG(db->ctx, "Releasing database %p\n", db);
 433
 434         // Removing all ASes
 435         if (db->as_v1) {
 436                 r = munmap(db->as_v1, db->as_count * sizeof(*db->as_v1));
 437                 if (r)
 438                         ERROR(db->ctx, "Could not unmap AS section: %s\n", strerror(errno));
 439         }
 440
 441         // Remove mapped network sections
 442         if (db->networks_v1) {
 443                 r = munmap(db->networks_v1, db->networks_count * sizeof(*db->networks_v1));
 444                 if (r)
 445                         ERROR(db->ctx, "Could not unmap networks section: %s\n", strerror(errno));
 446         }
 447
 448         // Remove mapped network nodes section
 449         if (db->network_nodes_v1) {
 450                 r = munmap(db->network_nodes_v1, db->network_nodes_count * sizeof(*db->network_nodes_v1));
 451                 if (r)
 452                         ERROR(db->ctx, "Could not unmap network nodes section: %s\n", strerror(errno));
 453         }
 454
 455         // Remove mapped countries section
 456         if (db->countries_v1) {
 457                 r = munmap(db->countries_v1, db->countries_count * sizeof(*db->countries_v1));
 458                 if (r)
 459                         ERROR(db->ctx, "Could not unmap countries section: %s\n", strerror(errno));
 460         }
 461
 462         if (db->pool)
 463                 loc_stringpool_unref(db->pool);
 464
 465         // Free signature
 466         if (db->signature1)
 467                 free(db->signature1);
 468         if (db->signature2)
 469                 free(db->signature2);
 470
 471         // Close database file
 472         if (db->f)
 473                 fclose(db->f);
 474
 475         loc_unref(db->ctx);
 476         free(db);
 477 }
 478
 479 LOC_EXPORT struct loc_database* loc_database_unref(struct loc_database* db) {
 480         if (--db->refcount > 0)
 481                 return NULL;
 482
 483         loc_database_free(db);
 484         return NULL;
 485 }
 486
 487 LOC_EXPORT int loc_database_verify(struct loc_database* db, FILE* f) {
 488         // Cannot do this when no signature is available
 489         if (!db->signature1 && !db->signature2) {
 490                 DEBUG(db->ctx, "No signature available to verify\n");
 491                 return 1;
 492         }
 493
 494         // Start the stopwatch
 495         clock_t start = clock();
 496
 497         // Load public key
 498         EVP_PKEY* pkey = PEM_read_PUBKEY(f, NULL, NULL, NULL);
 499         if (!pkey) {
 500                 char* error = ERR_error_string(ERR_get_error(), NULL);
 501                 ERROR(db->ctx, "Could not parse public key: %s\n", error);
 502
 503                 return -1;
 504         }
 505
 506         int r = 0;
 507
 508         EVP_MD_CTX* mdctx = EVP_MD_CTX_new();
 509
 510         // Initialise hash function
 511         r = EVP_DigestVerifyInit(mdctx, NULL, NULL, NULL, pkey);
 512         if (r != 1) {
 513                 ERROR(db->ctx, "Error initializing signature validation: %s\n",
 514                         ERR_error_string(ERR_get_error(), NULL));
 515                 r = 1;
 516
 517                 goto CLEANUP;
 518         }
 519
 520         // Reset file to start
 521         rewind(db->f);
 522
 523         // Read magic
 524         struct loc_database_magic magic;
 525         fread(&magic, 1, sizeof(magic), db->f);
 526
 527         hexdump(db->ctx, &magic, sizeof(magic));
 528
 529         // Feed magic into the hash
 530         r = EVP_DigestVerifyUpdate(mdctx, &magic, sizeof(magic));
 531         if (r != 1) {
 532                 ERROR(db->ctx, "%s\n", ERR_error_string(ERR_get_error(), NULL));
 533                 r = 1;
 534
 535                 goto CLEANUP;
 536         }
 537
 538         // Read the header
 539         struct loc_database_header_v1 header_v1;
 540         size_t bytes_read;
 541
 542         switch (db->version) {
 543                 case LOC_DATABASE_VERSION_1:
 544                         bytes_read = fread(&header_v1, 1, sizeof(header_v1), db->f);
 545                         if (bytes_read < sizeof(header_v1)) {
 546                                 ERROR(db->ctx, "Could not read header\n");
 547                                 r = 1;
 548
 549                                 goto CLEANUP;
 550                         }
 551
 552                         // Clear signatures
 553                         memset(header_v1.signature1, '\0', sizeof(header_v1.signature1));
 554                         header_v1.signature1_length = 0;
 555                         memset(header_v1.signature2, '\0', sizeof(header_v1.signature2));
 556                         header_v1.signature2_length = 0;
 557
 558                         hexdump(db->ctx, &header_v1, sizeof(header_v1));
 559
 560                         // Feed header into the hash
 561                         r = EVP_DigestVerifyUpdate(mdctx, &header_v1, sizeof(header_v1));
 562                         if (r != 1) {
 563                                 ERROR(db->ctx, "%s\n", ERR_error_string(ERR_get_error(), NULL));
 564                                 r = 1;
 565
 566                                 goto CLEANUP;
 567                         }
 568                         break;
 569
 570                 default:
 571                         ERROR(db->ctx, "Cannot compute hash for database with format %d\n",
 572                                 db->version);
 573                         r = -EINVAL;
 574                         goto CLEANUP;
 575         }
 576
 577         // Walk through the file in chunks of 64kB
 578         char buffer[64 * 1024];
 579
 580         while (!feof(db->f)) {
 581                 bytes_read = fread(buffer, 1, sizeof(buffer), db->f);
 582
 583                 hexdump(db->ctx, buffer, bytes_read);
 584
 585                 r = EVP_DigestVerifyUpdate(mdctx, buffer, bytes_read);
 586                 if (r != 1) {
 587                         ERROR(db->ctx, "%s\n", ERR_error_string(ERR_get_error(), NULL));
 588                         r = 1;
 589
 590                         goto CLEANUP;
 591                 }
 592         }
 593
 594         // Check first signature
 595         if (db->signature1) {
 596                 hexdump(db->ctx, db->signature1, db->signature1_length);
 597
 598                 r = EVP_DigestVerifyFinal(mdctx,
 599                         (unsigned char*)db->signature1, db->signature1_length);
 600
 601                 if (r == 0) {
 602                         DEBUG(db->ctx, "The first signature is invalid\n");
 603                         r = 1;
 604                 } else if (r == 1) {
 605                         DEBUG(db->ctx, "The first signature is valid\n");
 606                         r = 0;
 607                 } else {
 608                         ERROR(db->ctx, "Error verifying the first signature: %s\n",
 609                                 ERR_error_string(ERR_get_error(), NULL));
 610                         r = -1;
 611                 }
 612         }
 613
 614         // Check second signature only when the first one was invalid
 615         if (r && db->signature2) {
 616                 hexdump(db->ctx, db->signature2, db->signature2_length);
 617
 618                 r = EVP_DigestVerifyFinal(mdctx,
 619                         (unsigned char*)db->signature2, db->signature2_length);
 620
 621                 if (r == 0) {
 622                         DEBUG(db->ctx, "The second signature is invalid\n");
 623                         r = 1;
 624                 } else if (r == 1) {
 625                         DEBUG(db->ctx, "The second signature is valid\n");
 626                         r = 0;
 627                 } else {
 628                         ERROR(db->ctx, "Error verifying the second signature: %s\n",
 629                                 ERR_error_string(ERR_get_error(), NULL));
 630                         r = -1;
 631                 }
 632         }
 633
 634         clock_t end = clock();
 635         INFO(db->ctx, "Signature checked in %.4fms\n",
 636                 (double)(end - start) / CLOCKS_PER_SEC * 1000);
 637
 638 CLEANUP:
 639         // Cleanup
 640         EVP_MD_CTX_free(mdctx);
 641         EVP_PKEY_free(pkey);
 642
 643         return r;
 644 }
 645
 646 LOC_EXPORT time_t loc_database_created_at(struct loc_database* db) {
 647         return db->created_at;
 648 }
 649
 650 LOC_EXPORT const char* loc_database_get_vendor(struct loc_database* db) {
 651         return loc_stringpool_get(db->pool, db->vendor);
 652 }
 653
 654 LOC_EXPORT const char* loc_database_get_description(struct loc_database* db) {
 655         return loc_stringpool_get(db->pool, db->description);
 656 }
 657
 658 LOC_EXPORT const char* loc_database_get_license(struct loc_database* db) {
 659         return loc_stringpool_get(db->pool, db->license);
 660 }
 661
 662 LOC_EXPORT size_t loc_database_count_as(struct loc_database* db) {
 663         return db->as_count;
 664 }
 665
 666 // Returns the AS at position pos
 667 static int loc_database_fetch_as(struct loc_database* db, struct loc_as** as, off_t pos) {
 668         if ((size_t)pos >= db->as_count)
 669                 return -EINVAL;
 670
 671         DEBUG(db->ctx, "Fetching AS at position %jd\n", (intmax_t)pos);
 672
 673         int r;
 674         switch (db->version) {
 675                 case LOC_DATABASE_VERSION_1:
 676                         r = loc_as_new_from_database_v1(db->ctx, db->pool, as, db->as_v1 + pos);
 677                         break;
 678
 679                 default:
 680                         return -1;
 681         }
 682
 683         if (r == 0) {
 684                 DEBUG(db->ctx, "Got AS%u\n", loc_as_get_number(*as));
 685         }
 686
 687         return r;
 688 }
 689
 690 // Performs a binary search to find the AS in the list
 691 LOC_EXPORT int loc_database_get_as(struct loc_database* db, struct loc_as** as, uint32_t number) {
 692         off_t lo = 0;
 693         off_t hi = db->as_count - 1;
 694
 695 #ifdef ENABLE_DEBUG
 696         // Save start time
 697         clock_t start = clock();
 698 #endif
 699
 700         while (lo <= hi) {
 701                 off_t i = (lo + hi) / 2;
 702
 703                 // Fetch AS in the middle between lo and hi
 704                 int r = loc_database_fetch_as(db, as, i);
 705                 if (r)
 706                         return r;
 707
 708                 // Check if this is a match
 709                 uint32_t as_number = loc_as_get_number(*as);
 710                 if (as_number == number) {
 711 #ifdef ENABLE_DEBUG
 712                         clock_t end = clock();
 713
 714                         // Log how fast this has been
 715                         DEBUG(db->ctx, "Found AS%u in %.4fms\n", as_number,
 716                                 (double)(end - start) / CLOCKS_PER_SEC * 1000);
 717 #endif
 718
 719                         return 0;
 720                 }
 721
 722                 // If it wasn't, we release the AS and
 723                 // adjust our search pointers
 724                 loc_as_unref(*as);
 725
 726                 if (as_number < number) {
 727                         lo = i + 1;
 728                 } else
 729                         hi = i - 1;
 730         }
 731
 732         // Nothing found
 733         *as = NULL;
 734
 735         return 1;
 736 }
 737
 738 // Returns the network at position pos
 739 static int loc_database_fetch_network(struct loc_database* db, struct loc_network** network,
 740                 struct in6_addr* address, unsigned int prefix, off_t pos) {
 741         if ((size_t)pos >= db->networks_count) {
 742                 DEBUG(db->ctx, "Network ID out of range: %jd/%jd\n",
 743                         (intmax_t)pos, (intmax_t)db->networks_count);
 744                 return -EINVAL;
 745         }
 746
 747
 748         DEBUG(db->ctx, "Fetching network at position %jd\n", (intmax_t)pos);
 749
 750         int r;
 751         switch (db->version) {
 752                 case LOC_DATABASE_VERSION_1:
 753                         r = loc_network_new_from_database_v1(db->ctx, network,
 754                                 address, prefix, db->networks_v1 + pos);
 755                         break;
 756
 757                 default:
 758                         return -1;
 759         }
 760
 761 #ifdef ENABLE_DEBUG
 762         if (r == 0) {
 763                 char* string = loc_network_str(*network);
 764                 DEBUG(db->ctx, "Got network %s\n", string);
 765                 free(string);
 766         }
 767 #endif
 768
 769         return r;
 770 }
 771
 772 static int __loc_database_node_is_leaf(const struct loc_database_network_node_v1* node) {
 773         return (node->network != htobe32(0xffffffff));
 774 }
 775
 776 static int __loc_database_lookup_handle_leaf(struct loc_database* db, const struct in6_addr* address,
 777                 struct loc_network** network, struct in6_addr* network_address, unsigned int prefix,
 778                 const struct loc_database_network_node_v1* node) {
 779         off_t network_index = be32toh(node->network);
 780
 781         DEBUG(db->ctx, "Handling leaf node at %jd (%jd)\n", (intmax_t)(node - db->network_nodes_v1), (intmax_t)network_index);
 782
 783         // Fetch the network
 784         int r = loc_database_fetch_network(db, network,
 785                 network_address, prefix, network_index);
 786         if (r) {
 787                 ERROR(db->ctx, "Could not fetch network %jd from database\n", (intmax_t)network_index);
 788                 return r;
 789         }
 790
 791         // Check if the given IP address is inside the network
 792         if (!loc_network_matches_address(*network, address)) {
 793                 DEBUG(db->ctx, "Searched address is not part of the network\n");
 794
 795                 loc_network_unref(*network);
 796                 *network = NULL;
 797                 return 1;
 798         }
 799
 800         // A network was found and the IP address matches
 801         return 0;
 802 }
 803
 804 // Searches for an exact match along the path
 805 static int __loc_database_lookup(struct loc_database* db, const struct in6_addr* address,
 806                 struct loc_network** network, struct in6_addr* network_address,
 807                 const struct loc_database_network_node_v1* node, unsigned int level) {
 808         int r;
 809         off_t node_index;
 810
 811         // Follow the path
 812         int bit = loc_address_get_bit(address, level);
 813         loc_address_set_bit(network_address, level, bit);
 814
 815         if (bit == 0)
 816                 node_index = be32toh(node->zero);
 817         else
 818                 node_index = be32toh(node->one);
 819
 820         // If the node index is zero, the tree ends here
 821         // and we cannot descend any further
 822         if (node_index > 0) {
 823                 // Check boundaries
 824                 if ((size_t)node_index >= db->network_nodes_count)
 825                         return -EINVAL;
 826
 827                 // Move on to the next node
 828                 r = __loc_database_lookup(db, address, network, network_address,
 829                         db->network_nodes_v1 + node_index, level + 1);
 830
 831                 // End here if a result was found
 832                 if (r == 0)
 833                         return r;
 834
 835                 // Raise any errors
 836                 else if (r < 0)
 837                         return r;
 838
 839                 DEBUG(db->ctx, "No match found below level %u\n", level);
 840         } else {
 841                 DEBUG(db->ctx, "Tree ended at level %u\n", level);
 842         }
 843
 844         // If this node has a leaf, we will check if it matches
 845         if (__loc_database_node_is_leaf(node)) {
 846                 r = __loc_database_lookup_handle_leaf(db, address, network, network_address, level, node);
 847                 if (r <= 0)
 848                         return r;
 849         }
 850
 851         return 1;
 852 }
 853
 854 LOC_EXPORT int loc_database_lookup(struct loc_database* db,
 855                 const struct in6_addr* address, struct loc_network** network) {
 856         struct in6_addr network_address;
 857         memset(&network_address, 0, sizeof(network_address));
 858
 859         *network = NULL;
 860
 861 #ifdef ENABLE_DEBUG
 862         // Save start time
 863         clock_t start = clock();
 864 #endif
 865
 866         int r = __loc_database_lookup(db, address, network, &network_address,
 867                 db->network_nodes_v1, 0);
 868
 869 #ifdef ENABLE_DEBUG
 870         clock_t end = clock();
 871
 872         // Log how fast this has been
 873         DEBUG(db->ctx, "Executed network search in %.4fms\n",
 874                 (double)(end - start) / CLOCKS_PER_SEC * 1000);
 875 #endif
 876
 877         return r;
 878 }
 879
 880 LOC_EXPORT int loc_database_lookup_from_string(struct loc_database* db,
 881                 const char* string, struct loc_network** network) {
 882         struct in6_addr address;
 883
 884         int r = loc_parse_address(db->ctx, string, &address);
 885         if (r)
 886                 return r;
 887
 888         return loc_database_lookup(db, &address, network);
 889 }
 890
 891 // Returns the country at position pos
 892 static int loc_database_fetch_country(struct loc_database* db,
 893                 struct loc_country** country, off_t pos) {
 894         if ((size_t)pos >= db->countries_count)
 895                 return -EINVAL;
 896
 897         DEBUG(db->ctx, "Fetching country at position %jd\n", (intmax_t)pos);
 898
 899         int r;
 900         switch (db->version) {
 901                 case LOC_DATABASE_VERSION_1:
 902                         r = loc_country_new_from_database_v1(db->ctx, db->pool, country, db->countries_v1 + pos);
 903                         break;
 904
 905                 default:
 906                         return -1;
 907         }
 908
 909         if (r == 0) {
 910                 DEBUG(db->ctx, "Got country %s\n", loc_country_get_code(*country));
 911         }
 912
 913         return r;
 914 }
 915
 916 // Performs a binary search to find the country in the list
 917 LOC_EXPORT int loc_database_get_country(struct loc_database* db,
 918                 struct loc_country** country, const char* code) {
 919         off_t lo = 0;
 920         off_t hi = db->countries_count - 1;
 921
 922 #ifdef ENABLE_DEBUG
 923         // Save start time
 924         clock_t start = clock();
 925 #endif
 926
 927         while (lo <= hi) {
 928                 off_t i = (lo + hi) / 2;
 929
 930                 // Fetch country in the middle between lo and hi
 931                 int r = loc_database_fetch_country(db, country, i);
 932                 if (r)
 933                         return r;
 934
 935                 // Check if this is a match
 936                 const char* cc = loc_country_get_code(*country);
 937                 int result = strcmp(code, cc);
 938
 939                 if (result == 0) {
 940 #ifdef ENABLE_DEBUG
 941                         clock_t end = clock();
 942
 943                         // Log how fast this has been
 944                         DEBUG(db->ctx, "Found country %s in %.4fms\n", cc,
 945                                 (double)(end - start) / CLOCKS_PER_SEC * 1000);
 946 #endif
 947
 948                         return 0;
 949                 }
 950
 951                 // If it wasn't, we release the country and
 952                 // adjust our search pointers
 953                 loc_country_unref(*country);
 954
 955                 if (result > 0) {
 956                         lo = i + 1;
 957                 } else
 958                         hi = i - 1;
 959         }
 960
 961         // Nothing found
 962         *country = NULL;
 963
 964         return 1;
 965 }
 966
 967 // Enumerator
 968
 969 static void loc_database_enumerator_free(struct loc_database_enumerator* enumerator) {
 970         DEBUG(enumerator->ctx, "Releasing database enumerator %p\n", enumerator);
 971
 972         // Release all references
 973         loc_database_unref(enumerator->db);
 974         loc_unref(enumerator->ctx);
 975
 976         if (enumerator->string)
 977                 free(enumerator->string);
 978
 979         if (enumerator->countries)
 980                 loc_country_list_unref(enumerator->countries);
 981
 982         if (enumerator->asns)
 983                 loc_as_list_unref(enumerator->asns);
 984
 985         // Free network search
 986         free(enumerator->networks_visited);
 987
 988         // Free subnet/bogons stack
 989         if (enumerator->stack)
 990                 loc_network_list_unref(enumerator->stack);
 991
 992         free(enumerator);
 993 }
 994
 995 LOC_EXPORT int loc_database_enumerator_new(struct loc_database_enumerator** enumerator,
 996                 struct loc_database* db, enum loc_database_enumerator_mode mode, int flags) {
 997         struct loc_database_enumerator* e = calloc(1, sizeof(*e));
 998         if (!e)
 999                 return -ENOMEM;
1000
1001         // Reference context
1002         e->ctx = loc_ref(db->ctx);
1003         e->db = loc_database_ref(db);
1004         e->mode = mode;
1005         e->refcount = 1;
1006
1007         // Flatten output?
1008         e->flatten = (flags & LOC_DB_ENUMERATOR_FLAGS_FLATTEN);
1009
1010         // Initialise graph search
1011         e->network_stack_depth = 1;
1012         e->networks_visited = calloc(db->network_nodes_count, sizeof(*e->networks_visited));
1013
1014         // Allocate stack
1015         int r = loc_network_list_new(e->ctx, &e->stack);
1016         if (r) {
1017                 loc_database_enumerator_free(e);
1018                 return r;
1019         }
1020
1021         // Initialize bogon search
1022         loc_address_reset(&e->gap6_start, AF_INET6);
1023         loc_address_reset(&e->gap4_start, AF_INET);
1024
1025         DEBUG(e->ctx, "Database enumerator object allocated at %p\n", e);
1026
1027         *enumerator = e;
1028         return 0;
1029 }
1030
1031 LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_ref(struct loc_database_enumerator* enumerator) {
1032         enumerator->refcount++;
1033
1034         return enumerator;
1035 }
1036
1037 LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_unref(struct loc_database_enumerator* enumerator) {
1038         if (!enumerator)
1039                 return NULL;
1040
1041         if (--enumerator->refcount > 0)
1042                 return enumerator;
1043
1044         loc_database_enumerator_free(enumerator);
1045         return NULL;
1046 }
1047
1048 LOC_EXPORT int loc_database_enumerator_set_string(struct loc_database_enumerator* enumerator, const char* string) {
1049         enumerator->string = strdup(string);
1050
1051         // Make the string lowercase
1052         for (char *p = enumerator->string; *p; p++)
1053                 *p = tolower(*p);
1054
1055         return 0;
1056 }
1057
1058 LOC_EXPORT struct loc_country_list* loc_database_enumerator_get_countries(
1059                 struct loc_database_enumerator* enumerator) {
1060         if (!enumerator->countries)
1061                 return NULL;
1062
1063         return loc_country_list_ref(enumerator->countries);
1064 }
1065
1066 LOC_EXPORT int loc_database_enumerator_set_countries(
1067                 struct loc_database_enumerator* enumerator, struct loc_country_list* countries) {
1068         if (enumerator->countries)
1069                 loc_country_list_unref(enumerator->countries);
1070
1071         enumerator->countries = loc_country_list_ref(countries);
1072
1073         return 0;
1074 }
1075
1076 LOC_EXPORT struct loc_as_list* loc_database_enumerator_get_asns(
1077                 struct loc_database_enumerator* enumerator) {
1078         if (!enumerator->asns)
1079                 return NULL;
1080
1081         return loc_as_list_ref(enumerator->asns);
1082 }
1083
1084 LOC_EXPORT int loc_database_enumerator_set_asns(
1085                 struct loc_database_enumerator* enumerator, struct loc_as_list* asns) {
1086         if (enumerator->asns)
1087                 loc_as_list_unref(enumerator->asns);
1088
1089         enumerator->asns = loc_as_list_ref(asns);
1090
1091         return 0;
1092 }
1093
1094 LOC_EXPORT int loc_database_enumerator_set_flag(
1095                 struct loc_database_enumerator* enumerator, enum loc_network_flags flag) {
1096         enumerator->flags |= flag;
1097
1098         return 0;
1099 }
1100
1101 LOC_EXPORT int loc_database_enumerator_set_family(
1102                 struct loc_database_enumerator* enumerator, int family) {
1103         enumerator->family = family;
1104
1105         return 0;
1106 }
1107
1108 LOC_EXPORT int loc_database_enumerator_next_as(
1109                 struct loc_database_enumerator* enumerator, struct loc_as** as) {
1110         *as = NULL;
1111
1112         // Do not do anything if not in AS mode
1113         if (enumerator->mode != LOC_DB_ENUMERATE_ASES)
1114                 return 0;
1115
1116         struct loc_database* db = enumerator->db;
1117
1118         while (enumerator->as_index < db->as_count) {
1119                 // Fetch the next AS
1120                 int r = loc_database_fetch_as(db, as, enumerator->as_index++);
1121                 if (r)
1122                         return r;
1123
1124                 r = loc_as_match_string(*as, enumerator->string);
1125                 if (r == 1) {
1126                         DEBUG(enumerator->ctx, "AS%d (%s) matches %s\n",
1127                                 loc_as_get_number(*as), loc_as_get_name(*as), enumerator->string);
1128
1129                         return 0;
1130                 }
1131
1132                 // No match
1133                 loc_as_unref(*as);
1134                 *as = NULL;
1135         }
1136
1137         // Reset the index
1138         enumerator->as_index = 0;
1139
1140         // We have searched through all of them
1141         return 0;
1142 }
1143
1144 static int loc_database_enumerator_stack_push_node(
1145                 struct loc_database_enumerator* e, off_t offset, int i, int depth) {
1146         // Do not add empty nodes
1147         if (!offset)
1148                 return 0;
1149
1150         // Check if there is any space left on the stack
1151         if (e->network_stack_depth >= MAX_STACK_DEPTH) {
1152                 ERROR(e->ctx, "Maximum stack size reached: %d\n", e->network_stack_depth);
1153                 return -1;
1154         }
1155
1156         // Increase stack size
1157         int s = ++e->network_stack_depth;
1158
1159         DEBUG(e->ctx, "Added node %jd to stack (%d)\n", (intmax_t)offset, depth);
1160
1161         e->network_stack[s].offset = offset;
1162         e->network_stack[s].i = i;
1163         e->network_stack[s].depth = depth;
1164
1165         return 0;
1166 }
1167
1168 static int loc_database_enumerator_match_network(
1169                 struct loc_database_enumerator* enumerator, struct loc_network* network) {
1170         // If family is set, it must match
1171         if (enumerator->family && loc_network_address_family(network) != enumerator->family) {
1172                 DEBUG(enumerator->ctx, "Filtered network %p because of family not matching\n", network);
1173                 return 0;
1174         }
1175
1176         // Match if no filter criteria is configured
1177         if (!enumerator->countries && !enumerator->asns && !enumerator->flags)
1178                 return 1;
1179
1180         // Check if the country code matches
1181         if (enumerator->countries && !loc_country_list_empty(enumerator->countries)) {
1182                 const char* country_code = loc_network_get_country_code(network);
1183
1184                 if (loc_country_list_contains_code(enumerator->countries, country_code)) {
1185                         DEBUG(enumerator->ctx, "Matched network %p because of its country code\n", network);
1186                         return 1;
1187                 }
1188         }
1189
1190         // Check if the ASN matches
1191         if (enumerator->asns && !loc_as_list_empty(enumerator->asns)) {
1192                 uint32_t asn = loc_network_get_asn(network);
1193
1194                 if (loc_as_list_contains_number(enumerator->asns, asn)) {
1195                         DEBUG(enumerator->ctx, "Matched network %p because of its ASN\n", network);
1196                         return 1;
1197                 }
1198         }
1199
1200         // Check if flags match
1201         if (enumerator->flags && loc_network_has_flag(network, enumerator->flags)) {
1202                 DEBUG(enumerator->ctx, "Matched network %p because of its flags\n", network);
1203                 return 1;
1204         }
1205
1206         // Not a match
1207         return 0;
1208 }
1209
1210 static int __loc_database_enumerator_next_network(
1211                 struct loc_database_enumerator* enumerator, struct loc_network** network, int filter) {
1212         // Return top element from the stack
1213         while (1) {
1214                 *network = loc_network_list_pop_first(enumerator->stack);
1215
1216                 // Stack is empty
1217                 if (!*network)
1218                         break;
1219
1220                 // Return everything if filter isn't enabled, or only return matches
1221                 if (!filter || loc_database_enumerator_match_network(enumerator, *network))
1222                         return 0;
1223
1224                 // Throw away anything that doesn't match
1225                 loc_network_unref(*network);
1226                 *network = NULL;
1227         }
1228
1229         DEBUG(enumerator->ctx, "Called with a stack of %u nodes\n",
1230                 enumerator->network_stack_depth);
1231
1232         // Perform DFS
1233         while (enumerator->network_stack_depth > 0) {
1234                 DEBUG(enumerator->ctx, "Stack depth: %u\n", enumerator->network_stack_depth);
1235
1236                 // Get object from top of the stack
1237                 struct loc_node_stack* node = &enumerator->network_stack[enumerator->network_stack_depth];
1238
1239                 // Remove the node from the stack if we have already visited it
1240                 if (enumerator->networks_visited[node->offset]) {
1241                         enumerator->network_stack_depth--;
1242                         continue;
1243                 }
1244
1245                 // Mark the bits on the path correctly
1246                 loc_address_set_bit(&enumerator->network_address,
1247                         (node->depth > 0) ? node->depth - 1 : 0, node->i);
1248
1249                 DEBUG(enumerator->ctx, "Looking at node %jd\n", (intmax_t)node->offset);
1250                 enumerator->networks_visited[node->offset]++;
1251
1252                 // Pop node from top of the stack
1253                 struct loc_database_network_node_v1* n =
1254                         enumerator->db->network_nodes_v1 + node->offset;
1255
1256                 // Add edges to stack
1257                 int r = loc_database_enumerator_stack_push_node(enumerator,
1258                         be32toh(n->one), 1, node->depth + 1);
1259
1260                 if (r)
1261                         return r;
1262
1263                 r = loc_database_enumerator_stack_push_node(enumerator,
1264                         be32toh(n->zero), 0, node->depth + 1);
1265
1266                 if (r)
1267                         return r;
1268
1269                 // Check if this node is a leaf and has a network object
1270                 if (__loc_database_node_is_leaf(n)) {
1271                         off_t network_index = be32toh(n->network);
1272
1273                         DEBUG(enumerator->ctx, "Node has a network at %jd\n", (intmax_t)network_index);
1274
1275                         // Fetch the network object
1276                         r = loc_database_fetch_network(enumerator->db, network,
1277                                 &enumerator->network_address, node->depth, network_index);
1278
1279                         // Break on any errors
1280                         if (r)
1281                                 return r;
1282
1283                         // Return all networks when the filter is disabled, or check for match
1284                         if (!filter || loc_database_enumerator_match_network(enumerator, *network))
1285                                 return 0;
1286
1287                         // Does not seem to be a match, so we cleanup and move on
1288                         loc_network_unref(*network);
1289                         *network = NULL;
1290                 }
1291         }
1292
1293         // Reached the end of the search
1294         return 0;
1295 }
1296
1297 static int __loc_database_enumerator_next_network_flattened(
1298                 struct loc_database_enumerator* enumerator, struct loc_network** network) {
1299         // Fetch the next network
1300         int r = __loc_database_enumerator_next_network(enumerator, network, 1);
1301         if (r)
1302                 return r;
1303
1304         // End if we could not read another network
1305         if (!*network)
1306                 return 0;
1307
1308         struct loc_network* subnet = NULL;
1309         struct loc_network_list* subnets;
1310
1311         // Create a list with all subnets
1312         r = loc_network_list_new(enumerator->ctx, &subnets);
1313         if (r)
1314                 return r;
1315
1316         // Search all subnets from the database
1317         while (1) {
1318                 // Fetch the next network in line
1319                 r = __loc_database_enumerator_next_network(enumerator, &subnet, 0);
1320                 if (r) {
1321                         loc_network_unref(subnet);
1322                         loc_network_list_unref(subnets);
1323
1324                         return r;
1325                 }
1326
1327                 // End if we did not receive another subnet
1328                 if (!subnet)
1329                         break;
1330
1331                 // Collect all subnets in a list
1332                 if (loc_network_is_subnet(*network, subnet)) {
1333                         r = loc_network_list_push(subnets, subnet);
1334                         if (r) {
1335                                 loc_network_unref(subnet);
1336                                 loc_network_list_unref(subnets);
1337
1338                                 return r;
1339                         }
1340
1341                         loc_network_unref(subnet);
1342                         continue;
1343                 }
1344
1345                 // If this is not a subnet, we push it back onto the stack and break
1346                 r = loc_network_list_push(enumerator->stack, subnet);
1347                 if (r) {
1348                         loc_network_unref(subnet);
1349                         loc_network_list_unref(subnets);
1350
1351                         return r;
1352                 }
1353
1354                 loc_network_unref(subnet);
1355                 break;
1356         }
1357
1358         DEBUG(enumerator->ctx, "Found %zu subnet(s)\n", loc_network_list_size(subnets));
1359
1360         // We can abort here if the network has no subnets
1361         if (loc_network_list_empty(subnets)) {
1362                 loc_network_list_unref(subnets);
1363
1364                 return 0;
1365         }
1366
1367         // If the network has any subnets, we will break it into smaller parts
1368         // without the subnets.
1369         struct loc_network_list* excluded = loc_network_exclude_list(*network, subnets);
1370         if (!excluded) {
1371                 loc_network_list_unref(subnets);
1372                 return -1;
1373         }
1374
1375         // Merge subnets onto the stack
1376         r = loc_network_list_merge(enumerator->stack, subnets);
1377         if (r) {
1378                 loc_network_list_unref(subnets);
1379                 loc_network_list_unref(excluded);
1380
1381                 return r;
1382         }
1383
1384         // Push excluded list onto the stack
1385         r = loc_network_list_merge(enumerator->stack, excluded);
1386         if (r) {
1387                 loc_network_list_unref(subnets);
1388                 loc_network_list_unref(excluded);
1389
1390                 return r;
1391         }
1392
1393         loc_network_list_unref(subnets);
1394         loc_network_list_unref(excluded);
1395
1396         // Drop the network and restart the whole process again to pick the next network
1397         loc_network_unref(*network);
1398
1399         return __loc_database_enumerator_next_network_flattened(enumerator, network);
1400 }
1401
1402 /*
1403         This function finds all bogons (i.e. gaps) between the input networks
1404 */
1405 static int __loc_database_enumerator_next_bogon(
1406                 struct loc_database_enumerator* enumerator, struct loc_network** bogon) {
1407         int r;
1408
1409         // Return top element from the stack
1410         while (1) {
1411                 *bogon = loc_network_list_pop_first(enumerator->stack);
1412
1413                 // Stack is empty
1414                 if (!*bogon)
1415                         break;
1416
1417                 // Return result
1418                 return 0;
1419         }
1420
1421         struct loc_network* network = NULL;
1422         struct in6_addr* gap_start = NULL;
1423         struct in6_addr gap_end = IN6ADDR_ANY_INIT;
1424
1425         while (1) {
1426                 r = __loc_database_enumerator_next_network(enumerator, &network, 1);
1427                 if (r)
1428                         return r;
1429
1430                 // We have read the last network
1431                 if (!network)
1432                         goto FINISH;
1433
1434                 const char* country_code = loc_network_get_country_code(network);
1435
1436                 /*
1437                         Skip anything that does not have a country code
1438
1439                         Even if a network is part of the routing table, and the database provides
1440                         an ASN, this does not mean that this is a legitimate announcement.
1441                 */
1442                 if (country_code && !*country_code) {
1443                         loc_network_unref(network);
1444                         continue;
1445                 }
1446
1447                 // Determine the network family
1448                 int family = loc_network_address_family(network);
1449
1450                 switch (family) {
1451                         case AF_INET6:
1452                                 gap_start = &enumerator->gap6_start;
1453                                 break;
1454
1455                         case AF_INET:
1456                                 gap_start = &enumerator->gap4_start;
1457                                 break;
1458
1459                         default:
1460                                 ERROR(enumerator->ctx, "Unsupported network family %d\n", family);
1461                                 errno = ENOTSUP;
1462                                 return 1;
1463                 }
1464
1465                 // Search where the gap could end
1466                 gap_end = address_decrement(loc_network_get_first_address(network));
1467
1468                 // There is a gap
1469                 if (loc_address_cmp(gap_start, &gap_end) < 0) {
1470                         r = loc_network_list_summarize(enumerator->ctx,
1471                                 gap_start, &gap_end, &enumerator->stack);
1472                         if (r) {
1473                                 loc_network_unref(network);
1474                                 return r;
1475                         }
1476                 }
1477
1478                 // The gap now starts after this network
1479                 const struct in6_addr* network_end = loc_network_get_last_address(network);
1480                 (*gap_start) = address_increment(network_end);
1481
1482                 loc_network_unref(network);
1483
1484                 // Try to return something
1485                 *bogon = loc_network_list_pop_first(enumerator->stack);
1486                 if (*bogon)
1487                         break;
1488         }
1489
1490         return 0;
1491
1492 FINISH:
1493
1494         if (!loc_address_all_zeroes(&enumerator->gap6_start)) {
1495                 r = loc_address_reset_last(&gap_end, AF_INET6);
1496                 if (r)
1497                         return r;
1498
1499                 if (loc_address_cmp(&enumerator->gap6_start, &gap_end) < 0) {
1500                         r = loc_network_list_summarize(enumerator->ctx,
1501                                 &enumerator->gap6_start, &gap_end, &enumerator->stack);
1502                         if (r)
1503                                 return r;
1504                 }
1505
1506                 // Reset start
1507                 loc_address_reset(&enumerator->gap6_start, AF_INET6);
1508         }
1509
1510         if (!loc_address_all_zeroes(&enumerator->gap4_start)) {
1511                 r = loc_address_reset_last(&gap_end, AF_INET);
1512                 if (r)
1513                         return r;
1514
1515                 if (loc_address_cmp(&enumerator->gap4_start, &gap_end) < 0) {
1516                         r = loc_network_list_summarize(enumerator->ctx,
1517                                 &enumerator->gap4_start, &gap_end, &enumerator->stack);
1518                         if (r)
1519                                 return r;
1520                 }
1521
1522                 // Reset start
1523                 loc_address_reset(&enumerator->gap4_start, AF_INET);
1524         }
1525
1526         // Try to return something
1527         *bogon = loc_network_list_pop_first(enumerator->stack);
1528
1529         return 0;
1530 }
1531
1532 LOC_EXPORT int loc_database_enumerator_next_network(
1533                 struct loc_database_enumerator* enumerator, struct loc_network** network) {
1534         switch (enumerator->mode) {
1535                 case LOC_DB_ENUMERATE_NETWORKS:
1536                         // Flatten output?
1537                         if (enumerator->flatten)
1538                                 return __loc_database_enumerator_next_network_flattened(enumerator, network);
1539
1540                         return __loc_database_enumerator_next_network(enumerator, network, 1);
1541
1542                 case LOC_DB_ENUMERATE_BOGONS:
1543                         return __loc_database_enumerator_next_bogon(enumerator, network);
1544
1545                 default:
1546                         return 0;
1547         }
1548 }
1549
1550 LOC_EXPORT int loc_database_enumerator_next_country(
1551                 struct loc_database_enumerator* enumerator, struct loc_country** country) {
1552         *country = NULL;
1553
1554         // Do not do anything if not in country mode
1555         if (enumerator->mode != LOC_DB_ENUMERATE_COUNTRIES)
1556                 return 0;
1557
1558         struct loc_database* db = enumerator->db;
1559
1560         while (enumerator->country_index < db->countries_count) {
1561                 // Fetch the next country
1562                 int r = loc_database_fetch_country(db, country, enumerator->country_index++);
1563                 if (r)
1564                         return r;
1565
1566                 // We do not filter here, so it always is a match
1567                 return 0;
1568         }
1569
1570         // Reset the index
1571         enumerator->country_index = 0;
1572
1573         // We have searched through all of them
1574         return 0;
1575 }