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