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 <endian.h>
  20 #include <errno.h>
  21 #include <netinet/in.h>
  22 #include <stddef.h>
  23 #include <stdint.h>
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <sys/mman.h>
  28 #include <sys/types.h>
  29 #include <time.h>
  30 #include <unistd.h>
  31
  32 #include <loc/libloc.h>
  33 #include <loc/as.h>
  34 #include <loc/database.h>
  35 #include <loc/format.h>
  36 #include <loc/network.h>
  37 #include <loc/private.h>
  38 #include <loc/stringpool.h>
  39
  40 struct loc_database {
  41         struct loc_ctx* ctx;
  42         int refcount;
  43
  44         unsigned int version;
  45         time_t created_at;
  46         off_t vendor;
  47         off_t description;
  48         off_t license;
  49
  50         // ASes in the database
  51         struct loc_database_as_v0* as_v0;
  52         size_t as_count;
  53
  54         // Network tree
  55         struct loc_database_network_node_v0* network_nodes_v0;
  56         size_t network_nodes_count;
  57
  58         // Networks
  59         struct loc_database_network_v0* networks_v0;
  60         size_t networks_count;
  61
  62         struct loc_stringpool* pool;
  63 };
  64
  65 struct loc_database_enumerator {
  66         struct loc_ctx* ctx;
  67         struct loc_database* db;
  68         int refcount;
  69
  70         // Search string
  71         char* string;
  72
  73         // Index of the AS we are looking at
  74         unsigned int as_index;
  75 };
  76
  77 static int loc_database_read_magic(struct loc_database* db, FILE* f) {
  78         struct loc_database_magic magic;
  79
  80         // Read from file
  81         size_t bytes_read = fread(&magic, 1, sizeof(magic), f);
  82
  83         // Check if we have been able to read enough data
  84         if (bytes_read < sizeof(magic)) {
  85                 ERROR(db->ctx, "Could not read enough data to validate magic bytes\n");
  86                 DEBUG(db->ctx, "Read %zu bytes, but needed %zu\n", bytes_read, sizeof(magic));
  87                 return -ENOMSG;
  88         }
  89
  90         // Compare magic bytes
  91         if (memcmp(LOC_DATABASE_MAGIC, magic.magic, strlen(LOC_DATABASE_MAGIC)) == 0) {
  92                 DEBUG(db->ctx, "Magic value matches\n");
  93
  94                 // Parse version
  95                 db->version = be16toh(magic.version);
  96                 DEBUG(db->ctx, "Database version is %u\n", db->version);
  97
  98                 return 0;
  99         }
 100
 101         ERROR(db->ctx, "Database format is not compatible\n");
 102
 103         // Return an error
 104         return 1;
 105 }
 106
 107 static int loc_database_read_as_section_v0(struct loc_database* db,
 108                 FILE* f, const struct loc_database_header_v0* header) {
 109         off_t as_offset  = be32toh(header->as_offset);
 110         size_t as_length = be32toh(header->as_length);
 111
 112         DEBUG(db->ctx, "Reading AS section from %jd (%zu bytes)\n", as_offset, as_length);
 113
 114         if (as_length > 0) {
 115                 db->as_v0 = mmap(NULL, as_length, PROT_READ,
 116                         MAP_SHARED, fileno(f), as_offset);
 117
 118                 if (db->as_v0 == MAP_FAILED)
 119                         return -errno;
 120         }
 121
 122         db->as_count = as_length / sizeof(*db->as_v0);
 123
 124         INFO(db->ctx, "Read %zu ASes from the database\n", db->as_count);
 125
 126         return 0;
 127 }
 128
 129 static int loc_database_read_network_nodes_section_v0(struct loc_database* db,
 130                 FILE* f, const struct loc_database_header_v0* header) {
 131         off_t network_nodes_offset  = be32toh(header->network_tree_offset);
 132         size_t network_nodes_length = be32toh(header->network_tree_length);
 133
 134         DEBUG(db->ctx, "Reading network nodes section from %jd (%zu bytes)\n",
 135                 network_nodes_offset, network_nodes_length);
 136
 137         if (network_nodes_length > 0) {
 138                 db->network_nodes_v0 = mmap(NULL, network_nodes_length, PROT_READ,
 139                         MAP_SHARED, fileno(f), network_nodes_offset);
 140
 141                 if (db->network_nodes_v0 == MAP_FAILED)
 142                         return -errno;
 143         }
 144
 145         db->network_nodes_count = network_nodes_length / sizeof(*db->network_nodes_v0);
 146
 147         INFO(db->ctx, "Read %zu network nodes from the database\n", db->network_nodes_count);
 148
 149         return 0;
 150 }
 151
 152 static int loc_database_read_networks_section_v0(struct loc_database* db,
 153                 FILE* f, const struct loc_database_header_v0* header) {
 154         off_t networks_offset  = be32toh(header->network_data_offset);
 155         size_t networks_length = be32toh(header->network_data_length);
 156
 157         DEBUG(db->ctx, "Reading networks section from %jd (%zu bytes)\n",
 158                 networks_offset, networks_length);
 159
 160         if (networks_length > 0) {
 161                 db->networks_v0 = mmap(NULL, networks_length, PROT_READ,
 162                         MAP_SHARED, fileno(f), networks_offset);
 163
 164                 if (db->networks_v0 == MAP_FAILED)
 165                         return -errno;
 166         }
 167
 168         db->networks_count = networks_length / sizeof(*db->networks_v0);
 169
 170         INFO(db->ctx, "Read %zu networks from the database\n", db->networks_count);
 171
 172         return 0;
 173 }
 174
 175 static int loc_database_read_header_v0(struct loc_database* db, FILE* f) {
 176         struct loc_database_header_v0 header;
 177
 178         // Read from file
 179         size_t size = fread(&header, 1, sizeof(header), f);
 180
 181         if (size < sizeof(header)) {
 182                 ERROR(db->ctx, "Could not read enough data for header\n");
 183                 return -ENOMSG;
 184         }
 185
 186         // Copy over data
 187         db->created_at  = be64toh(header.created_at);
 188         db->vendor      = be32toh(header.vendor);
 189         db->description = be32toh(header.description);
 190         db->license     = be32toh(header.license);
 191
 192         // Open pool
 193         off_t pool_offset  = be32toh(header.pool_offset);
 194         size_t pool_length = be32toh(header.pool_length);
 195
 196         int r = loc_stringpool_open(db->ctx, &db->pool,
 197                 f, pool_length, pool_offset);
 198         if (r)
 199                 return r;
 200
 201         // AS section
 202         r = loc_database_read_as_section_v0(db, f, &header);
 203         if (r)
 204                 return r;
 205
 206         // Network Nodes
 207         r = loc_database_read_network_nodes_section_v0(db, f, &header);
 208         if (r)
 209                 return r;
 210
 211         // Networks
 212         r = loc_database_read_networks_section_v0(db, f, &header);
 213         if (r)
 214                 return r;
 215
 216         return 0;
 217 }
 218
 219 static int loc_database_read_header(struct loc_database* db, FILE* f) {
 220         switch (db->version) {
 221                 case 0:
 222                         return loc_database_read_header_v0(db, f);
 223
 224                 default:
 225                         ERROR(db->ctx, "Incompatible database version: %u\n", db->version);
 226                         return 1;
 227         }
 228 }
 229
 230 static int loc_database_read(struct loc_database* db, FILE* f) {
 231         clock_t start = clock();
 232
 233         // Read magic bytes
 234         int r = loc_database_read_magic(db, f);
 235         if (r)
 236                 return r;
 237
 238         // Read the header
 239         r = loc_database_read_header(db, f);
 240         if (r)
 241                 return r;
 242
 243         clock_t end = clock();
 244
 245         INFO(db->ctx, "Opened database in %.8fs\n",
 246                 (double)(end - start) / CLOCKS_PER_SEC);
 247
 248         return 0;
 249 }
 250
 251 LOC_EXPORT int loc_database_new(struct loc_ctx* ctx, struct loc_database** database, FILE* f) {
 252         // Fail on invalid file handle
 253         if (!f)
 254                 return -EINVAL;
 255
 256         struct loc_database* db = calloc(1, sizeof(*db));
 257         if (!db)
 258                 return -ENOMEM;
 259
 260         // Reference context
 261         db->ctx = loc_ref(ctx);
 262         db->refcount = 1;
 263
 264         DEBUG(db->ctx, "Database object allocated at %p\n", db);
 265
 266         int r = loc_database_read(db, f);
 267         if (r) {
 268                 loc_database_unref(db);
 269                 return r;
 270         }
 271
 272         *database = db;
 273
 274         return 0;
 275 }
 276
 277 LOC_EXPORT struct loc_database* loc_database_ref(struct loc_database* db) {
 278         db->refcount++;
 279
 280         return db;
 281 }
 282
 283 static void loc_database_free(struct loc_database* db) {
 284         int r;
 285
 286         DEBUG(db->ctx, "Releasing database %p\n", db);
 287
 288         // Removing all ASes
 289         if (db->as_v0) {
 290                 r = munmap(db->as_v0, db->as_count * sizeof(*db->as_v0));
 291                 if (r)
 292                         ERROR(db->ctx, "Could not unmap AS section: %s\n", strerror(errno));
 293         }
 294
 295         // Remove mapped network sections
 296         if (db->networks_v0) {
 297                 r = munmap(db->networks_v0, db->networks_count * sizeof(*db->networks_v0));
 298                 if (r)
 299                         ERROR(db->ctx, "Could not unmap networks section: %s\n", strerror(errno));
 300         }
 301
 302         // Remove mapped network nodes section
 303         if (db->network_nodes_v0) {
 304                 r = munmap(db->network_nodes_v0, db->network_nodes_count * sizeof(*db->network_nodes_v0));
 305                 if (r)
 306                         ERROR(db->ctx, "Could not unmap network nodes section: %s\n", strerror(errno));
 307         }
 308
 309         loc_stringpool_unref(db->pool);
 310
 311         loc_unref(db->ctx);
 312         free(db);
 313 }
 314
 315 LOC_EXPORT struct loc_database* loc_database_unref(struct loc_database* db) {
 316         if (--db->refcount > 0)
 317                 return NULL;
 318
 319         loc_database_free(db);
 320         return NULL;
 321 }
 322
 323 LOC_EXPORT time_t loc_database_created_at(struct loc_database* db) {
 324         return db->created_at;
 325 }
 326
 327 LOC_EXPORT const char* loc_database_get_vendor(struct loc_database* db) {
 328         return loc_stringpool_get(db->pool, db->vendor);
 329 }
 330
 331 LOC_EXPORT const char* loc_database_get_description(struct loc_database* db) {
 332         return loc_stringpool_get(db->pool, db->description);
 333 }
 334
 335 LOC_EXPORT const char* loc_database_get_license(struct loc_database* db) {
 336         return loc_stringpool_get(db->pool, db->license);
 337 }
 338
 339 LOC_EXPORT size_t loc_database_count_as(struct loc_database* db) {
 340         return db->as_count;
 341 }
 342
 343 // Returns the AS at position pos
 344 static int loc_database_fetch_as(struct loc_database* db, struct loc_as** as, off_t pos) {
 345         if ((size_t)pos >= db->as_count)
 346                 return -EINVAL;
 347
 348         DEBUG(db->ctx, "Fetching AS at position %jd\n", pos);
 349
 350         int r;
 351         switch (db->version) {
 352                 case 0:
 353                         r = loc_as_new_from_database_v0(db->ctx, db->pool, as, db->as_v0 + pos);
 354                         break;
 355
 356                 default:
 357                         return -1;
 358         }
 359
 360         if (r == 0) {
 361                 DEBUG(db->ctx, "Got AS%u\n", loc_as_get_number(*as));
 362         }
 363
 364         return r;
 365 }
 366
 367 // Performs a binary search to find the AS in the list
 368 LOC_EXPORT int loc_database_get_as(struct loc_database* db, struct loc_as** as, uint32_t number) {
 369         off_t lo = 0;
 370         off_t hi = db->as_count - 1;
 371
 372         // Save start time
 373         clock_t start = clock();
 374
 375         while (lo <= hi) {
 376                 off_t i = (lo + hi) / 2;
 377
 378                 // Fetch AS in the middle between lo and hi
 379                 int r = loc_database_fetch_as(db, as, i);
 380                 if (r)
 381                         return r;
 382
 383                 // Check if this is a match
 384                 uint32_t as_number = loc_as_get_number(*as);
 385                 if (as_number == number) {
 386                         clock_t end = clock();
 387
 388                         // Log how fast this has been
 389                         DEBUG(db->ctx, "Found AS%u in %.8fs\n", as_number,
 390                                 (double)(end - start) / CLOCKS_PER_SEC);
 391
 392                         return 0;
 393                 }
 394
 395                 // If it wasn't, we release the AS and
 396                 // adjust our search pointers
 397                 loc_as_unref(*as);
 398
 399                 if (as_number < number) {
 400                         lo = i + 1;
 401                 } else
 402                         hi = i - 1;
 403         }
 404
 405         // Nothing found
 406         *as = NULL;
 407
 408         return 1;
 409 }
 410
 411 // Returns the network at position pos
 412 static int loc_database_fetch_network(struct loc_database* db, struct loc_network** network,
 413                 struct in6_addr* address, unsigned int prefix, off_t pos) {
 414         if ((size_t)pos >= db->networks_count)
 415                 return -EINVAL;
 416
 417         DEBUG(db->ctx, "Fetching network at position %jd\n", pos);
 418
 419         int r;
 420         switch (db->version) {
 421                 case 0:
 422                         r = loc_network_new_from_database_v0(db->ctx, network,
 423                                 address, prefix, db->networks_v0 + pos);
 424                         break;
 425
 426                 default:
 427                         return -1;
 428         }
 429
 430         if (r == 0) {
 431                 char* string = loc_network_str(*network);
 432                 DEBUG(db->ctx, "Got network %s\n", string);
 433                 free(string);
 434         }
 435
 436         return r;
 437 }
 438
 439 static int __loc_database_node_is_leaf(const struct loc_database_network_node_v0* node) {
 440         return (node->network != htobe32(0xffffffff));
 441 }
 442
 443 static int __loc_database_lookup_handle_leaf(struct loc_database* db, const struct in6_addr* address,
 444                 struct loc_network** network, struct in6_addr* network_address, unsigned int prefix,
 445                 const struct loc_database_network_node_v0* node) {
 446         off_t network_index = be32toh(node->network);
 447
 448         DEBUG(db->ctx, "Handling leaf node at %jd (%jd)\n", node - db->network_nodes_v0, network_index);
 449
 450         // Fetch the network
 451         int r = loc_database_fetch_network(db, network,
 452                 network_address, prefix, network_index);
 453         if (r) {
 454                 ERROR(db->ctx, "Could not fetch network %jd from database\n", network_index);
 455                 return r;
 456         }
 457
 458         // Check if the given IP address is inside the network
 459         r = loc_network_match_address(*network, address);
 460         if (r) {
 461                 DEBUG(db->ctx, "Searched address is not part of the network\n");
 462
 463                 loc_network_unref(*network);
 464                 *network = NULL;
 465                 return 1;
 466         }
 467
 468         // A network was found and the IP address matches
 469         return 0;
 470 }
 471
 472 // Searches for an exact match along the path
 473 static int __loc_database_lookup(struct loc_database* db, const struct in6_addr* address,
 474                 struct loc_network** network, struct in6_addr* network_address,
 475                 const struct loc_database_network_node_v0* node, unsigned int level) {
 476         int r;
 477         off_t node_index;
 478
 479         // Follow the path
 480         int bit = in6_addr_get_bit(address, level);
 481         in6_addr_set_bit(network_address, level, bit);
 482
 483         if (bit == 0)
 484                 node_index = be32toh(node->zero);
 485         else
 486                 node_index = be32toh(node->one);
 487
 488         // If the node index is zero, the tree ends here
 489         // and we cannot descend any further
 490         if (node_index > 0) {
 491                 // Check boundaries
 492                 if ((size_t)node_index >= db->network_nodes_count)
 493                         return -EINVAL;
 494
 495                 // Move on to the next node
 496                 r = __loc_database_lookup(db, address, network, network_address,
 497                         db->network_nodes_v0 + node_index, level + 1);
 498
 499                 // End here if a result was found
 500                 if (r == 0)
 501                         return r;
 502
 503                 // Raise any errors
 504                 else if (r < 0)
 505                         return r;
 506
 507                 DEBUG(db->ctx, "No match found below level %u\n", level);
 508         } else {
 509                 DEBUG(db->ctx, "Tree ended at level %u\n", level);
 510         }
 511
 512         // If this node has a leaf, we will check if it matches
 513         if (__loc_database_node_is_leaf(node)) {
 514                 r = __loc_database_lookup_handle_leaf(db, address, network, network_address, level, node);
 515                 if (r <= 0)
 516                         return r;
 517         }
 518
 519         return 1;
 520 }
 521
 522 LOC_EXPORT int loc_database_lookup(struct loc_database* db,
 523                 struct in6_addr* address, struct loc_network** network) {
 524         struct in6_addr network_address;
 525         memset(&network_address, 0, sizeof(network_address));
 526
 527         *network = NULL;
 528
 529         // Save start time
 530         clock_t start = clock();
 531
 532         int r = __loc_database_lookup(db, address, network, &network_address,
 533                 db->network_nodes_v0, 0);
 534
 535         clock_t end = clock();
 536
 537         // Log how fast this has been
 538         DEBUG(db->ctx, "Executed network search in %.8fs\n",
 539                 (double)(end - start) / CLOCKS_PER_SEC);
 540
 541         return r;
 542 }
 543
 544 LOC_EXPORT int loc_database_lookup_from_string(struct loc_database* db,
 545                 const char* string, struct loc_network** network) {
 546         struct in6_addr address;
 547
 548         int r = loc_parse_address(db->ctx, string, &address);
 549         if (r)
 550                 return r;
 551
 552         return loc_database_lookup(db, &address, network);
 553 }
 554
 555 // Enumerator
 556
 557 LOC_EXPORT int loc_database_enumerator_new(struct loc_database_enumerator** enumerator, struct loc_database* db) {
 558         struct loc_database_enumerator* e = calloc(1, sizeof(*e));
 559         if (!e)
 560                 return -ENOMEM;
 561
 562         // Reference context
 563         e->ctx = loc_ref(db->ctx);
 564         e->db = loc_database_ref(db);
 565         e->refcount = 1;
 566
 567         DEBUG(e->ctx, "Database enumerator object allocated at %p\n", e);
 568
 569         *enumerator = e;
 570         return 0;
 571 }
 572
 573 LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_ref(struct loc_database_enumerator* enumerator) {
 574         enumerator->refcount++;
 575
 576         return enumerator;
 577 }
 578
 579 static void loc_database_enumerator_free(struct loc_database_enumerator* enumerator) {
 580         DEBUG(enumerator->ctx, "Releasing database enumerator %p\n", enumerator);
 581
 582         // Release all references
 583         loc_database_unref(enumerator->db);
 584         loc_unref(enumerator->ctx);
 585
 586         if (enumerator->string)
 587                 free(enumerator->string);
 588
 589         free(enumerator);
 590 }
 591
 592 LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_unref(struct loc_database_enumerator* enumerator) {
 593         if (!enumerator)
 594                 return NULL;
 595
 596         if (--enumerator->refcount > 0)
 597                 return enumerator;
 598
 599         loc_database_enumerator_free(enumerator);
 600         return NULL;
 601 }
 602
 603 LOC_EXPORT int loc_database_enumerator_set_string(struct loc_database_enumerator* enumerator, const char* string) {
 604         enumerator->string = strdup(string);
 605
 606         // Make the string lowercase
 607         for (char *p = enumerator->string; *p; p++)
 608                 *p = tolower(*p);
 609
 610         return 0;
 611 }
 612
 613 LOC_EXPORT struct loc_as* loc_database_enumerator_next_as(struct loc_database_enumerator* enumerator) {
 614         struct loc_database* db = enumerator->db;
 615         struct loc_as* as;
 616
 617         while (enumerator->as_index < db->as_count) {
 618                 // Fetch the next AS
 619                 int r = loc_database_fetch_as(db, &as, enumerator->as_index++);
 620                 if (r)
 621                         return NULL;
 622
 623                 r = loc_as_match_string(as, enumerator->string);
 624                 if (r == 1) {
 625                         DEBUG(enumerator->ctx, "AS%d (%s) matches %s\n",
 626                                 loc_as_get_number(as), loc_as_get_name(as), enumerator->string);
 627
 628                         return as;
 629                 }
 630
 631                 // No match
 632                 loc_as_unref(as);
 633         }
 634
 635         // Reset the index
 636         enumerator->as_index = 0;
 637
 638         // We have searched through all of them
 639         return NULL;
 640 }