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         if (r == 0)
 762                 DEBUG(db->ctx, "Got network %s\n", loc_network_str(*network));
 763
 764         return r;
 765 }
 766
 767 static int __loc_database_node_is_leaf(const struct loc_database_network_node_v1* node) {
 768         return (node->network != htobe32(0xffffffff));
 769 }
 770
 771 static int __loc_database_lookup_handle_leaf(struct loc_database* db, const struct in6_addr* address,
 772                 struct loc_network** network, struct in6_addr* network_address, unsigned int prefix,
 773                 const struct loc_database_network_node_v1* node) {
 774         off_t network_index = be32toh(node->network);
 775
 776         DEBUG(db->ctx, "Handling leaf node at %jd (%jd)\n", (intmax_t)(node - db->network_nodes_v1), (intmax_t)network_index);
 777
 778         // Fetch the network
 779         int r = loc_database_fetch_network(db, network,
 780                 network_address, prefix, network_index);
 781         if (r) {
 782                 ERROR(db->ctx, "Could not fetch network %jd from database\n", (intmax_t)network_index);
 783                 return r;
 784         }
 785
 786         // Check if the given IP address is inside the network
 787         if (!loc_network_matches_address(*network, address)) {
 788                 DEBUG(db->ctx, "Searched address is not part of the network\n");
 789
 790                 loc_network_unref(*network);
 791                 *network = NULL;
 792                 return 1;
 793         }
 794
 795         // A network was found and the IP address matches
 796         return 0;
 797 }
 798
 799 // Searches for an exact match along the path
 800 static int __loc_database_lookup(struct loc_database* db, const struct in6_addr* address,
 801                 struct loc_network** network, struct in6_addr* network_address,
 802                 const struct loc_database_network_node_v1* node, unsigned int level) {
 803         int r;
 804         off_t node_index;
 805
 806         // Follow the path
 807         int bit = loc_address_get_bit(address, level);
 808         loc_address_set_bit(network_address, level, bit);
 809
 810         if (bit == 0)
 811                 node_index = be32toh(node->zero);
 812         else
 813                 node_index = be32toh(node->one);
 814
 815         // If the node index is zero, the tree ends here
 816         // and we cannot descend any further
 817         if (node_index > 0) {
 818                 // Check boundaries
 819                 if ((size_t)node_index >= db->network_nodes_count)
 820                         return -EINVAL;
 821
 822                 // Move on to the next node
 823                 r = __loc_database_lookup(db, address, network, network_address,
 824                         db->network_nodes_v1 + node_index, level + 1);
 825
 826                 // End here if a result was found
 827                 if (r == 0)
 828                         return r;
 829
 830                 // Raise any errors
 831                 else if (r < 0)
 832                         return r;
 833
 834                 DEBUG(db->ctx, "No match found below level %u\n", level);
 835         } else {
 836                 DEBUG(db->ctx, "Tree ended at level %u\n", level);
 837         }
 838
 839         // If this node has a leaf, we will check if it matches
 840         if (__loc_database_node_is_leaf(node)) {
 841                 r = __loc_database_lookup_handle_leaf(db, address, network, network_address, level, node);
 842                 if (r <= 0)
 843                         return r;
 844         }
 845
 846         return 1;
 847 }
 848
 849 LOC_EXPORT int loc_database_lookup(struct loc_database* db,
 850                 const struct in6_addr* address, struct loc_network** network) {
 851         struct in6_addr network_address;
 852         memset(&network_address, 0, sizeof(network_address));
 853
 854         *network = NULL;
 855
 856 #ifdef ENABLE_DEBUG
 857         // Save start time
 858         clock_t start = clock();
 859 #endif
 860
 861         int r = __loc_database_lookup(db, address, network, &network_address,
 862                 db->network_nodes_v1, 0);
 863
 864 #ifdef ENABLE_DEBUG
 865         clock_t end = clock();
 866
 867         // Log how fast this has been
 868         DEBUG(db->ctx, "Executed network search in %.4fms\n",
 869                 (double)(end - start) / CLOCKS_PER_SEC * 1000);
 870 #endif
 871
 872         return r;
 873 }
 874
 875 LOC_EXPORT int loc_database_lookup_from_string(struct loc_database* db,
 876                 const char* string, struct loc_network** network) {
 877         struct in6_addr address;
 878
 879         int r = loc_address_parse(&address, NULL, string);
 880         if (r)
 881                 return r;
 882
 883         return loc_database_lookup(db, &address, network);
 884 }
 885
 886 // Returns the country at position pos
 887 static int loc_database_fetch_country(struct loc_database* db,
 888                 struct loc_country** country, off_t pos) {
 889         if ((size_t)pos >= db->countries_count)
 890                 return -EINVAL;
 891
 892         DEBUG(db->ctx, "Fetching country at position %jd\n", (intmax_t)pos);
 893
 894         int r;
 895         switch (db->version) {
 896                 case LOC_DATABASE_VERSION_1:
 897                         r = loc_country_new_from_database_v1(db->ctx, db->pool, country, db->countries_v1 + pos);
 898                         break;
 899
 900                 default:
 901                         return -1;
 902         }
 903
 904         if (r == 0) {
 905                 DEBUG(db->ctx, "Got country %s\n", loc_country_get_code(*country));
 906         }
 907
 908         return r;
 909 }
 910
 911 // Performs a binary search to find the country in the list
 912 LOC_EXPORT int loc_database_get_country(struct loc_database* db,
 913                 struct loc_country** country, const char* code) {
 914         off_t lo = 0;
 915         off_t hi = db->countries_count - 1;
 916
 917 #ifdef ENABLE_DEBUG
 918         // Save start time
 919         clock_t start = clock();
 920 #endif
 921
 922         while (lo <= hi) {
 923                 off_t i = (lo + hi) / 2;
 924
 925                 // Fetch country in the middle between lo and hi
 926                 int r = loc_database_fetch_country(db, country, i);
 927                 if (r)
 928                         return r;
 929
 930                 // Check if this is a match
 931                 const char* cc = loc_country_get_code(*country);
 932                 int result = strcmp(code, cc);
 933
 934                 if (result == 0) {
 935 #ifdef ENABLE_DEBUG
 936                         clock_t end = clock();
 937
 938                         // Log how fast this has been
 939                         DEBUG(db->ctx, "Found country %s in %.4fms\n", cc,
 940                                 (double)(end - start) / CLOCKS_PER_SEC * 1000);
 941 #endif
 942
 943                         return 0;
 944                 }
 945
 946                 // If it wasn't, we release the country and
 947                 // adjust our search pointers
 948                 loc_country_unref(*country);
 949
 950                 if (result > 0) {
 951                         lo = i + 1;
 952                 } else
 953                         hi = i - 1;
 954         }
 955
 956         // Nothing found
 957         *country = NULL;
 958
 959         return 1;
 960 }
 961
 962 // Enumerator
 963
 964 static void loc_database_enumerator_free(struct loc_database_enumerator* enumerator) {
 965         DEBUG(enumerator->ctx, "Releasing database enumerator %p\n", enumerator);
 966
 967         // Release all references
 968         loc_database_unref(enumerator->db);
 969         loc_unref(enumerator->ctx);
 970
 971         if (enumerator->string)
 972                 free(enumerator->string);
 973
 974         if (enumerator->countries)
 975                 loc_country_list_unref(enumerator->countries);
 976
 977         if (enumerator->asns)
 978                 loc_as_list_unref(enumerator->asns);
 979
 980         // Free network search
 981         free(enumerator->networks_visited);
 982
 983         // Free subnet/bogons stack
 984         if (enumerator->stack)
 985                 loc_network_list_unref(enumerator->stack);
 986
 987         free(enumerator);
 988 }
 989
 990 LOC_EXPORT int loc_database_enumerator_new(struct loc_database_enumerator** enumerator,
 991                 struct loc_database* db, enum loc_database_enumerator_mode mode, int flags) {
 992         struct loc_database_enumerator* e = calloc(1, sizeof(*e));
 993         if (!e)
 994                 return -ENOMEM;
 995
 996         // Reference context
 997         e->ctx = loc_ref(db->ctx);
 998         e->db = loc_database_ref(db);
 999         e->mode = mode;
1000         e->refcount = 1;
1001
1002         // Flatten output?
1003         e->flatten = (flags & LOC_DB_ENUMERATOR_FLAGS_FLATTEN);
1004
1005         // Initialise graph search
1006         e->network_stack_depth = 1;
1007         e->networks_visited = calloc(db->network_nodes_count, sizeof(*e->networks_visited));
1008
1009         // Allocate stack
1010         int r = loc_network_list_new(e->ctx, &e->stack);
1011         if (r) {
1012                 loc_database_enumerator_free(e);
1013                 return r;
1014         }
1015
1016         // Initialize bogon search
1017         loc_address_reset(&e->gap6_start, AF_INET6);
1018         loc_address_reset(&e->gap4_start, AF_INET);
1019
1020         DEBUG(e->ctx, "Database enumerator object allocated at %p\n", e);
1021
1022         *enumerator = e;
1023         return 0;
1024 }
1025
1026 LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_ref(struct loc_database_enumerator* enumerator) {
1027         enumerator->refcount++;
1028
1029         return enumerator;
1030 }
1031
1032 LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_unref(struct loc_database_enumerator* enumerator) {
1033         if (!enumerator)
1034                 return NULL;
1035
1036         if (--enumerator->refcount > 0)
1037                 return enumerator;
1038
1039         loc_database_enumerator_free(enumerator);
1040         return NULL;
1041 }
1042
1043 LOC_EXPORT int loc_database_enumerator_set_string(struct loc_database_enumerator* enumerator, const char* string) {
1044         enumerator->string = strdup(string);
1045
1046         // Make the string lowercase
1047         for (char *p = enumerator->string; *p; p++)
1048                 *p = tolower(*p);
1049
1050         return 0;
1051 }
1052
1053 LOC_EXPORT struct loc_country_list* loc_database_enumerator_get_countries(
1054                 struct loc_database_enumerator* enumerator) {
1055         if (!enumerator->countries)
1056                 return NULL;
1057
1058         return loc_country_list_ref(enumerator->countries);
1059 }
1060
1061 LOC_EXPORT int loc_database_enumerator_set_countries(
1062                 struct loc_database_enumerator* enumerator, struct loc_country_list* countries) {
1063         if (enumerator->countries)
1064                 loc_country_list_unref(enumerator->countries);
1065
1066         enumerator->countries = loc_country_list_ref(countries);
1067
1068         return 0;
1069 }
1070
1071 LOC_EXPORT struct loc_as_list* loc_database_enumerator_get_asns(
1072                 struct loc_database_enumerator* enumerator) {
1073         if (!enumerator->asns)
1074                 return NULL;
1075
1076         return loc_as_list_ref(enumerator->asns);
1077 }
1078
1079 LOC_EXPORT int loc_database_enumerator_set_asns(
1080                 struct loc_database_enumerator* enumerator, struct loc_as_list* asns) {
1081         if (enumerator->asns)
1082                 loc_as_list_unref(enumerator->asns);
1083
1084         enumerator->asns = loc_as_list_ref(asns);
1085
1086         return 0;
1087 }
1088
1089 LOC_EXPORT int loc_database_enumerator_set_flag(
1090                 struct loc_database_enumerator* enumerator, enum loc_network_flags flag) {
1091         enumerator->flags |= flag;
1092
1093         return 0;
1094 }
1095
1096 LOC_EXPORT int loc_database_enumerator_set_family(
1097                 struct loc_database_enumerator* enumerator, int family) {
1098         enumerator->family = family;
1099
1100         return 0;
1101 }
1102
1103 LOC_EXPORT int loc_database_enumerator_next_as(
1104                 struct loc_database_enumerator* enumerator, struct loc_as** as) {
1105         *as = NULL;
1106
1107         // Do not do anything if not in AS mode
1108         if (enumerator->mode != LOC_DB_ENUMERATE_ASES)
1109                 return 0;
1110
1111         struct loc_database* db = enumerator->db;
1112
1113         while (enumerator->as_index < db->as_count) {
1114                 // Fetch the next AS
1115                 int r = loc_database_fetch_as(db, as, enumerator->as_index++);
1116                 if (r)
1117                         return r;
1118
1119                 r = loc_as_match_string(*as, enumerator->string);
1120                 if (r == 1) {
1121                         DEBUG(enumerator->ctx, "AS%d (%s) matches %s\n",
1122                                 loc_as_get_number(*as), loc_as_get_name(*as), enumerator->string);
1123
1124                         return 0;
1125                 }
1126
1127                 // No match
1128                 loc_as_unref(*as);
1129                 *as = NULL;
1130         }
1131
1132         // Reset the index
1133         enumerator->as_index = 0;
1134
1135         // We have searched through all of them
1136         return 0;
1137 }
1138
1139 static int loc_database_enumerator_stack_push_node(
1140                 struct loc_database_enumerator* e, off_t offset, int i, int depth) {
1141         // Do not add empty nodes
1142         if (!offset)
1143                 return 0;
1144
1145         // Check if there is any space left on the stack
1146         if (e->network_stack_depth >= MAX_STACK_DEPTH) {
1147                 ERROR(e->ctx, "Maximum stack size reached: %d\n", e->network_stack_depth);
1148                 return -1;
1149         }
1150
1151         // Increase stack size
1152         int s = ++e->network_stack_depth;
1153
1154         DEBUG(e->ctx, "Added node %jd to stack (%d)\n", (intmax_t)offset, depth);
1155
1156         e->network_stack[s].offset = offset;
1157         e->network_stack[s].i = i;
1158         e->network_stack[s].depth = depth;
1159
1160         return 0;
1161 }
1162
1163 static int loc_database_enumerator_match_network(
1164                 struct loc_database_enumerator* enumerator, struct loc_network* network) {
1165         // If family is set, it must match
1166         if (enumerator->family && loc_network_address_family(network) != enumerator->family) {
1167                 DEBUG(enumerator->ctx, "Filtered network %p because of family not matching\n", network);
1168                 return 0;
1169         }
1170
1171         // Match if no filter criteria is configured
1172         if (!enumerator->countries && !enumerator->asns && !enumerator->flags)
1173                 return 1;
1174
1175         // Check if the country code matches
1176         if (enumerator->countries && !loc_country_list_empty(enumerator->countries)) {
1177                 const char* country_code = loc_network_get_country_code(network);
1178
1179                 if (loc_country_list_contains_code(enumerator->countries, country_code)) {
1180                         DEBUG(enumerator->ctx, "Matched network %p because of its country code\n", network);
1181                         return 1;
1182                 }
1183         }
1184
1185         // Check if the ASN matches
1186         if (enumerator->asns && !loc_as_list_empty(enumerator->asns)) {
1187                 uint32_t asn = loc_network_get_asn(network);
1188
1189                 if (loc_as_list_contains_number(enumerator->asns, asn)) {
1190                         DEBUG(enumerator->ctx, "Matched network %p because of its ASN\n", network);
1191                         return 1;
1192                 }
1193         }
1194
1195         // Check if flags match
1196         if (enumerator->flags && loc_network_has_flag(network, enumerator->flags)) {
1197                 DEBUG(enumerator->ctx, "Matched network %p because of its flags\n", network);
1198                 return 1;
1199         }
1200
1201         // Not a match
1202         return 0;
1203 }
1204
1205 static int __loc_database_enumerator_next_network(
1206                 struct loc_database_enumerator* enumerator, struct loc_network** network, int filter) {
1207         // Return top element from the stack
1208         while (1) {
1209                 *network = loc_network_list_pop_first(enumerator->stack);
1210
1211                 // Stack is empty
1212                 if (!*network)
1213                         break;
1214
1215                 // Return everything if filter isn't enabled, or only return matches
1216                 if (!filter || loc_database_enumerator_match_network(enumerator, *network))
1217                         return 0;
1218
1219                 // Throw away anything that doesn't match
1220                 loc_network_unref(*network);
1221                 *network = NULL;
1222         }
1223
1224         DEBUG(enumerator->ctx, "Called with a stack of %u nodes\n",
1225                 enumerator->network_stack_depth);
1226
1227         // Perform DFS
1228         while (enumerator->network_stack_depth > 0) {
1229                 DEBUG(enumerator->ctx, "Stack depth: %u\n", enumerator->network_stack_depth);
1230
1231                 // Get object from top of the stack
1232                 struct loc_node_stack* node = &enumerator->network_stack[enumerator->network_stack_depth];
1233
1234                 // Remove the node from the stack if we have already visited it
1235                 if (enumerator->networks_visited[node->offset]) {
1236                         enumerator->network_stack_depth--;
1237                         continue;
1238                 }
1239
1240                 // Mark the bits on the path correctly
1241                 loc_address_set_bit(&enumerator->network_address,
1242                         (node->depth > 0) ? node->depth - 1 : 0, node->i);
1243
1244                 DEBUG(enumerator->ctx, "Looking at node %jd\n", (intmax_t)node->offset);
1245                 enumerator->networks_visited[node->offset]++;
1246
1247                 // Pop node from top of the stack
1248                 struct loc_database_network_node_v1* n =
1249                         enumerator->db->network_nodes_v1 + node->offset;
1250
1251                 // Add edges to stack
1252                 int r = loc_database_enumerator_stack_push_node(enumerator,
1253                         be32toh(n->one), 1, node->depth + 1);
1254
1255                 if (r)
1256                         return r;
1257
1258                 r = loc_database_enumerator_stack_push_node(enumerator,
1259                         be32toh(n->zero), 0, node->depth + 1);
1260
1261                 if (r)
1262                         return r;
1263
1264                 // Check if this node is a leaf and has a network object
1265                 if (__loc_database_node_is_leaf(n)) {
1266                         off_t network_index = be32toh(n->network);
1267
1268                         DEBUG(enumerator->ctx, "Node has a network at %jd\n", (intmax_t)network_index);
1269
1270                         // Fetch the network object
1271                         r = loc_database_fetch_network(enumerator->db, network,
1272                                 &enumerator->network_address, node->depth, network_index);
1273
1274                         // Break on any errors
1275                         if (r)
1276                                 return r;
1277
1278                         // Return all networks when the filter is disabled, or check for match
1279                         if (!filter || loc_database_enumerator_match_network(enumerator, *network))
1280                                 return 0;
1281
1282                         // Does not seem to be a match, so we cleanup and move on
1283                         loc_network_unref(*network);
1284                         *network = NULL;
1285                 }
1286         }
1287
1288         // Reached the end of the search
1289         return 0;
1290 }
1291
1292 static int __loc_database_enumerator_next_network_flattened(
1293                 struct loc_database_enumerator* enumerator, struct loc_network** network) {
1294         // Fetch the next network
1295         int r = __loc_database_enumerator_next_network(enumerator, network, 1);
1296         if (r)
1297                 return r;
1298
1299         // End if we could not read another network
1300         if (!*network)
1301                 return 0;
1302
1303         struct loc_network* subnet = NULL;
1304         struct loc_network_list* subnets;
1305
1306         // Create a list with all subnets
1307         r = loc_network_list_new(enumerator->ctx, &subnets);
1308         if (r)
1309                 return r;
1310
1311         // Search all subnets from the database
1312         while (1) {
1313                 // Fetch the next network in line
1314                 r = __loc_database_enumerator_next_network(enumerator, &subnet, 0);
1315                 if (r) {
1316                         loc_network_unref(subnet);
1317                         loc_network_list_unref(subnets);
1318
1319                         return r;
1320                 }
1321
1322                 // End if we did not receive another subnet
1323                 if (!subnet)
1324                         break;
1325
1326                 // Collect all subnets in a list
1327                 if (loc_network_is_subnet(*network, subnet)) {
1328                         r = loc_network_list_push(subnets, subnet);
1329                         if (r) {
1330                                 loc_network_unref(subnet);
1331                                 loc_network_list_unref(subnets);
1332
1333                                 return r;
1334                         }
1335
1336                         loc_network_unref(subnet);
1337                         continue;
1338                 }
1339
1340                 // If this is not a subnet, we push it back onto the stack and break
1341                 r = loc_network_list_push(enumerator->stack, subnet);
1342                 if (r) {
1343                         loc_network_unref(subnet);
1344                         loc_network_list_unref(subnets);
1345
1346                         return r;
1347                 }
1348
1349                 loc_network_unref(subnet);
1350                 break;
1351         }
1352
1353         DEBUG(enumerator->ctx, "Found %zu subnet(s)\n", loc_network_list_size(subnets));
1354
1355         // We can abort here if the network has no subnets
1356         if (loc_network_list_empty(subnets)) {
1357                 loc_network_list_unref(subnets);
1358
1359                 return 0;
1360         }
1361
1362         // If the network has any subnets, we will break it into smaller parts
1363         // without the subnets.
1364         struct loc_network_list* excluded = loc_network_exclude_list(*network, subnets);
1365         if (!excluded) {
1366                 loc_network_list_unref(subnets);
1367                 return -1;
1368         }
1369
1370         // Merge subnets onto the stack
1371         r = loc_network_list_merge(enumerator->stack, subnets);
1372         if (r) {
1373                 loc_network_list_unref(subnets);
1374                 loc_network_list_unref(excluded);
1375
1376                 return r;
1377         }
1378
1379         // Push excluded list onto the stack
1380         r = loc_network_list_merge(enumerator->stack, excluded);
1381         if (r) {
1382                 loc_network_list_unref(subnets);
1383                 loc_network_list_unref(excluded);
1384
1385                 return r;
1386         }
1387
1388         loc_network_list_unref(subnets);
1389         loc_network_list_unref(excluded);
1390
1391         // Drop the network and restart the whole process again to pick the next network
1392         loc_network_unref(*network);
1393
1394         return __loc_database_enumerator_next_network_flattened(enumerator, network);
1395 }
1396
1397 /*
1398         This function finds all bogons (i.e. gaps) between the input networks
1399 */
1400 static int __loc_database_enumerator_next_bogon(
1401                 struct loc_database_enumerator* enumerator, struct loc_network** bogon) {
1402         int r;
1403
1404         // Return top element from the stack
1405         while (1) {
1406                 *bogon = loc_network_list_pop_first(enumerator->stack);
1407
1408                 // Stack is empty
1409                 if (!*bogon)
1410                         break;
1411
1412                 // Return result
1413                 return 0;
1414         }
1415
1416         struct loc_network* network = NULL;
1417         struct in6_addr* gap_start = NULL;
1418         struct in6_addr gap_end = IN6ADDR_ANY_INIT;
1419
1420         while (1) {
1421                 r = __loc_database_enumerator_next_network(enumerator, &network, 1);
1422                 if (r)
1423                         return r;
1424
1425                 // We have read the last network
1426                 if (!network)
1427                         goto FINISH;
1428
1429                 const char* country_code = loc_network_get_country_code(network);
1430
1431                 /*
1432                         Skip anything that does not have a country code
1433
1434                         Even if a network is part of the routing table, and the database provides
1435                         an ASN, this does not mean that this is a legitimate announcement.
1436                 */
1437                 if (country_code && !*country_code) {
1438                         loc_network_unref(network);
1439                         continue;
1440                 }
1441
1442                 // Determine the network family
1443                 int family = loc_network_address_family(network);
1444
1445                 switch (family) {
1446                         case AF_INET6:
1447                                 gap_start = &enumerator->gap6_start;
1448                                 break;
1449
1450                         case AF_INET:
1451                                 gap_start = &enumerator->gap4_start;
1452                                 break;
1453
1454                         default:
1455                                 ERROR(enumerator->ctx, "Unsupported network family %d\n", family);
1456                                 errno = ENOTSUP;
1457                                 return 1;
1458                 }
1459
1460                 const struct in6_addr* first_address = loc_network_get_first_address(network);
1461                 const struct in6_addr* last_address = loc_network_get_last_address(network);
1462
1463                 // Skip if this network is a subnet of a former one
1464                 if (loc_address_cmp(gap_start, last_address) >= 0) {
1465                         loc_network_unref(network);
1466                         continue;
1467                 }
1468
1469                 // Search where the gap could end
1470                 gap_end = *first_address;
1471                 loc_address_decrement(&gap_end);
1472
1473                 // There is a gap
1474                 if (loc_address_cmp(gap_start, &gap_end) <= 0) {
1475                         r = loc_network_list_summarize(enumerator->ctx,
1476                                 gap_start, &gap_end, &enumerator->stack);
1477                         if (r) {
1478                                 loc_network_unref(network);
1479                                 return r;
1480                         }
1481                 }
1482
1483                 // The gap now starts after this network
1484                 *gap_start = *last_address;
1485                 loc_address_increment(gap_start);
1486
1487                 loc_network_unref(network);
1488
1489                 // Try to return something
1490                 *bogon = loc_network_list_pop_first(enumerator->stack);
1491                 if (*bogon)
1492                         break;
1493         }
1494
1495         return 0;
1496
1497 FINISH:
1498
1499         if (!loc_address_all_zeroes(&enumerator->gap6_start)) {
1500                 r = loc_address_reset_last(&gap_end, AF_INET6);
1501                 if (r)
1502                         return r;
1503
1504                 if (loc_address_cmp(&enumerator->gap6_start, &gap_end) <= 0) {
1505                         r = loc_network_list_summarize(enumerator->ctx,
1506                                 &enumerator->gap6_start, &gap_end, &enumerator->stack);
1507                         if (r)
1508                                 return r;
1509                 }
1510
1511                 // Reset start
1512                 loc_address_reset(&enumerator->gap6_start, AF_INET6);
1513         }
1514
1515         if (!loc_address_all_zeroes(&enumerator->gap4_start)) {
1516                 r = loc_address_reset_last(&gap_end, AF_INET);
1517                 if (r)
1518                         return r;
1519
1520                 if (loc_address_cmp(&enumerator->gap4_start, &gap_end) <= 0) {
1521                         r = loc_network_list_summarize(enumerator->ctx,
1522                                 &enumerator->gap4_start, &gap_end, &enumerator->stack);
1523                         if (r)
1524                                 return r;
1525                 }
1526
1527                 // Reset start
1528                 loc_address_reset(&enumerator->gap4_start, AF_INET);
1529         }
1530
1531         // Try to return something
1532         *bogon = loc_network_list_pop_first(enumerator->stack);
1533
1534         return 0;
1535 }
1536
1537 LOC_EXPORT int loc_database_enumerator_next_network(
1538                 struct loc_database_enumerator* enumerator, struct loc_network** network) {
1539         switch (enumerator->mode) {
1540                 case LOC_DB_ENUMERATE_NETWORKS:
1541                         // Flatten output?
1542                         if (enumerator->flatten)
1543                                 return __loc_database_enumerator_next_network_flattened(enumerator, network);
1544
1545                         return __loc_database_enumerator_next_network(enumerator, network, 1);
1546
1547                 case LOC_DB_ENUMERATE_BOGONS:
1548                         return __loc_database_enumerator_next_bogon(enumerator, network);
1549
1550                 default:
1551                         return 0;
1552         }
1553 }
1554
1555 LOC_EXPORT int loc_database_enumerator_next_country(
1556                 struct loc_database_enumerator* enumerator, struct loc_country** country) {
1557         *country = NULL;
1558
1559         // Do not do anything if not in country mode
1560         if (enumerator->mode != LOC_DB_ENUMERATE_COUNTRIES)
1561                 return 0;
1562
1563         struct loc_database* db = enumerator->db;
1564
1565         while (enumerator->country_index < db->countries_count) {
1566                 // Fetch the next country
1567                 int r = loc_database_fetch_country(db, country, enumerator->country_index++);
1568                 if (r)
1569                         return r;
1570
1571                 // We do not filter here, so it always is a match
1572                 return 0;
1573         }
1574
1575         // Reset the index
1576         enumerator->country_index = 0;
1577
1578         // We have searched through all of them
1579         return 0;
1580 }