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         if (db->pool)
 310                 loc_stringpool_unref(db->pool);
 311
 312         loc_unref(db->ctx);
 313         free(db);
 314 }
 315
 316 LOC_EXPORT struct loc_database* loc_database_unref(struct loc_database* db) {
 317         if (--db->refcount > 0)
 318                 return NULL;
 319
 320         loc_database_free(db);
 321         return NULL;
 322 }
 323
 324 LOC_EXPORT time_t loc_database_created_at(struct loc_database* db) {
 325         return db->created_at;
 326 }
 327
 328 LOC_EXPORT const char* loc_database_get_vendor(struct loc_database* db) {
 329         return loc_stringpool_get(db->pool, db->vendor);
 330 }
 331
 332 LOC_EXPORT const char* loc_database_get_description(struct loc_database* db) {
 333         return loc_stringpool_get(db->pool, db->description);
 334 }
 335
 336 LOC_EXPORT const char* loc_database_get_license(struct loc_database* db) {
 337         return loc_stringpool_get(db->pool, db->license);
 338 }
 339
 340 LOC_EXPORT size_t loc_database_count_as(struct loc_database* db) {
 341         return db->as_count;
 342 }
 343
 344 // Returns the AS at position pos
 345 static int loc_database_fetch_as(struct loc_database* db, struct loc_as** as, off_t pos) {
 346         if ((size_t)pos >= db->as_count)
 347                 return -EINVAL;
 348
 349         DEBUG(db->ctx, "Fetching AS at position %jd\n", pos);
 350
 351         int r;
 352         switch (db->version) {
 353                 case 0:
 354                         r = loc_as_new_from_database_v0(db->ctx, db->pool, as, db->as_v0 + pos);
 355                         break;
 356
 357                 default:
 358                         return -1;
 359         }
 360
 361         if (r == 0) {
 362                 DEBUG(db->ctx, "Got AS%u\n", loc_as_get_number(*as));
 363         }
 364
 365         return r;
 366 }
 367
 368 // Performs a binary search to find the AS in the list
 369 LOC_EXPORT int loc_database_get_as(struct loc_database* db, struct loc_as** as, uint32_t number) {
 370         off_t lo = 0;
 371         off_t hi = db->as_count - 1;
 372
 373         // Save start time
 374         clock_t start = clock();
 375
 376         while (lo <= hi) {
 377                 off_t i = (lo + hi) / 2;
 378
 379                 // Fetch AS in the middle between lo and hi
 380                 int r = loc_database_fetch_as(db, as, i);
 381                 if (r)
 382                         return r;
 383
 384                 // Check if this is a match
 385                 uint32_t as_number = loc_as_get_number(*as);
 386                 if (as_number == number) {
 387                         clock_t end = clock();
 388
 389                         // Log how fast this has been
 390                         DEBUG(db->ctx, "Found AS%u in %.8fs\n", as_number,
 391                                 (double)(end - start) / CLOCKS_PER_SEC);
 392
 393                         return 0;
 394                 }
 395
 396                 // If it wasn't, we release the AS and
 397                 // adjust our search pointers
 398                 loc_as_unref(*as);
 399
 400                 if (as_number < number) {
 401                         lo = i + 1;
 402                 } else
 403                         hi = i - 1;
 404         }
 405
 406         // Nothing found
 407         *as = NULL;
 408
 409         return 1;
 410 }
 411
 412 // Returns the network at position pos
 413 static int loc_database_fetch_network(struct loc_database* db, struct loc_network** network,
 414                 struct in6_addr* address, unsigned int prefix, off_t pos) {
 415         if ((size_t)pos >= db->networks_count)
 416                 return -EINVAL;
 417
 418         DEBUG(db->ctx, "Fetching network at position %jd\n", pos);
 419
 420         int r;
 421         switch (db->version) {
 422                 case 0:
 423                         r = loc_network_new_from_database_v0(db->ctx, network,
 424                                 address, prefix, db->networks_v0 + pos);
 425                         break;
 426
 427                 default:
 428                         return -1;
 429         }
 430
 431         if (r == 0) {
 432                 char* string = loc_network_str(*network);
 433                 DEBUG(db->ctx, "Got network %s\n", string);
 434                 free(string);
 435         }
 436
 437         return r;
 438 }
 439
 440 static int __loc_database_node_is_leaf(const struct loc_database_network_node_v0* node) {
 441         return (node->network != htobe32(0xffffffff));
 442 }
 443
 444 static int __loc_database_lookup_handle_leaf(struct loc_database* db, const struct in6_addr* address,
 445                 struct loc_network** network, struct in6_addr* network_address, unsigned int prefix,
 446                 const struct loc_database_network_node_v0* node) {
 447         off_t network_index = be32toh(node->network);
 448
 449         DEBUG(db->ctx, "Handling leaf node at %jd (%jd)\n", node - db->network_nodes_v0, network_index);
 450
 451         // Fetch the network
 452         int r = loc_database_fetch_network(db, network,
 453                 network_address, prefix, network_index);
 454         if (r) {
 455                 ERROR(db->ctx, "Could not fetch network %jd from database\n", network_index);
 456                 return r;
 457         }
 458
 459         // Check if the given IP address is inside the network
 460         r = loc_network_match_address(*network, address);
 461         if (r) {
 462                 DEBUG(db->ctx, "Searched address is not part of the network\n");
 463
 464                 loc_network_unref(*network);
 465                 *network = NULL;
 466                 return 1;
 467         }
 468
 469         // A network was found and the IP address matches
 470         return 0;
 471 }
 472
 473 // Searches for an exact match along the path
 474 static int __loc_database_lookup(struct loc_database* db, const struct in6_addr* address,
 475                 struct loc_network** network, struct in6_addr* network_address,
 476                 const struct loc_database_network_node_v0* node, unsigned int level) {
 477         int r;
 478         off_t node_index;
 479
 480         // Follow the path
 481         int bit = in6_addr_get_bit(address, level);
 482         in6_addr_set_bit(network_address, level, bit);
 483
 484         if (bit == 0)
 485                 node_index = be32toh(node->zero);
 486         else
 487                 node_index = be32toh(node->one);
 488
 489         // If the node index is zero, the tree ends here
 490         // and we cannot descend any further
 491         if (node_index > 0) {
 492                 // Check boundaries
 493                 if ((size_t)node_index >= db->network_nodes_count)
 494                         return -EINVAL;
 495
 496                 // Move on to the next node
 497                 r = __loc_database_lookup(db, address, network, network_address,
 498                         db->network_nodes_v0 + node_index, level + 1);
 499
 500                 // End here if a result was found
 501                 if (r == 0)
 502                         return r;
 503
 504                 // Raise any errors
 505                 else if (r < 0)
 506                         return r;
 507
 508                 DEBUG(db->ctx, "No match found below level %u\n", level);
 509         } else {
 510                 DEBUG(db->ctx, "Tree ended at level %u\n", level);
 511         }
 512
 513         // If this node has a leaf, we will check if it matches
 514         if (__loc_database_node_is_leaf(node)) {
 515                 r = __loc_database_lookup_handle_leaf(db, address, network, network_address, level, node);
 516                 if (r <= 0)
 517                         return r;
 518         }
 519
 520         return 1;
 521 }
 522
 523 LOC_EXPORT int loc_database_lookup(struct loc_database* db,
 524                 struct in6_addr* address, struct loc_network** network) {
 525         struct in6_addr network_address;
 526         memset(&network_address, 0, sizeof(network_address));
 527
 528         *network = NULL;
 529
 530         // Save start time
 531         clock_t start = clock();
 532
 533         int r = __loc_database_lookup(db, address, network, &network_address,
 534                 db->network_nodes_v0, 0);
 535
 536         clock_t end = clock();
 537
 538         // Log how fast this has been
 539         DEBUG(db->ctx, "Executed network search in %.8fs\n",
 540                 (double)(end - start) / CLOCKS_PER_SEC);
 541
 542         return r;
 543 }
 544
 545 LOC_EXPORT int loc_database_lookup_from_string(struct loc_database* db,
 546                 const char* string, struct loc_network** network) {
 547         struct in6_addr address;
 548
 549         int r = loc_parse_address(db->ctx, string, &address);
 550         if (r)
 551                 return r;
 552
 553         return loc_database_lookup(db, &address, network);
 554 }
 555
 556 // Enumerator
 557
 558 LOC_EXPORT int loc_database_enumerator_new(struct loc_database_enumerator** enumerator, struct loc_database* db) {
 559         struct loc_database_enumerator* e = calloc(1, sizeof(*e));
 560         if (!e)
 561                 return -ENOMEM;
 562
 563         // Reference context
 564         e->ctx = loc_ref(db->ctx);
 565         e->db = loc_database_ref(db);
 566         e->refcount = 1;
 567
 568         DEBUG(e->ctx, "Database enumerator object allocated at %p\n", e);
 569
 570         *enumerator = e;
 571         return 0;
 572 }
 573
 574 LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_ref(struct loc_database_enumerator* enumerator) {
 575         enumerator->refcount++;
 576
 577         return enumerator;
 578 }
 579
 580 static void loc_database_enumerator_free(struct loc_database_enumerator* enumerator) {
 581         DEBUG(enumerator->ctx, "Releasing database enumerator %p\n", enumerator);
 582
 583         // Release all references
 584         loc_database_unref(enumerator->db);
 585         loc_unref(enumerator->ctx);
 586
 587         if (enumerator->string)
 588                 free(enumerator->string);
 589
 590         free(enumerator);
 591 }
 592
 593 LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_unref(struct loc_database_enumerator* enumerator) {
 594         if (!enumerator)
 595                 return NULL;
 596
 597         if (--enumerator->refcount > 0)
 598                 return enumerator;
 599
 600         loc_database_enumerator_free(enumerator);
 601         return NULL;
 602 }
 603
 604 LOC_EXPORT int loc_database_enumerator_set_string(struct loc_database_enumerator* enumerator, const char* string) {
 605         enumerator->string = strdup(string);
 606
 607         // Make the string lowercase
 608         for (char *p = enumerator->string; *p; p++)
 609                 *p = tolower(*p);
 610
 611         return 0;
 612 }
 613
 614 LOC_EXPORT struct loc_as* loc_database_enumerator_next_as(struct loc_database_enumerator* enumerator) {
 615         struct loc_database* db = enumerator->db;
 616         struct loc_as* as;
 617
 618         while (enumerator->as_index < db->as_count) {
 619                 // Fetch the next AS
 620                 int r = loc_database_fetch_as(db, &as, enumerator->as_index++);
 621                 if (r)
 622                         return NULL;
 623
 624                 r = loc_as_match_string(as, enumerator->string);
 625                 if (r == 1) {
 626                         DEBUG(enumerator->ctx, "AS%d (%s) matches %s\n",
 627                                 loc_as_get_number(as), loc_as_get_name(as), enumerator->string);
 628
 629                         return as;
 630                 }
 631
 632                 // No match
 633                 loc_as_unref(as);
 634         }
 635
 636         // Reset the index
 637         enumerator->as_index = 0;
 638
 639         // We have searched through all of them
 640         return NULL;
 641 }