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