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