test-database: Remove signature checks
[people/ms/libloc.git] / src / database.c
CommitLineData
2601e83e
MT
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
2a30e4de 17#include <arpa/inet.h>
d3d8ede6 18#include <ctype.h>
2601e83e 19#include <errno.h>
10778041 20#include <netinet/in.h>
2601e83e
MT
21#include <stddef.h>
22#include <stdint.h>
23#include <stdio.h>
24#include <stdlib.h>
25#include <string.h>
c182393f 26#include <sys/mman.h>
2601e83e 27#include <sys/types.h>
96ea74a5 28#include <time.h>
3f35869a 29#include <unistd.h>
2601e83e 30
42f3ccd7
MT
31#ifdef HAVE_ENDIAN_H
32# include <endian.h>
33#endif
34
726f9984 35#include <openssl/err.h>
b1720435 36#include <openssl/evp.h>
726f9984 37#include <openssl/pem.h>
b1720435 38
2601e83e 39#include <loc/libloc.h>
9fc7f001 40#include <loc/as.h>
42f3ccd7 41#include <loc/compat.h>
ec684c1a 42#include <loc/country.h>
9fc7f001 43#include <loc/database.h>
a5db3e49 44#include <loc/format.h>
10778041 45#include <loc/network.h>
9fc7f001
MT
46#include <loc/private.h>
47#include <loc/stringpool.h>
2601e83e
MT
48
49struct loc_database {
50 struct loc_ctx* ctx;
51 int refcount;
52
b1720435
MT
53 FILE* f;
54
2601e83e 55 unsigned int version;
96ea74a5 56 time_t created_at;
2601e83e
MT
57 off_t vendor;
58 off_t description;
4bf49d00 59 off_t license;
2601e83e 60
726f9984
MT
61 char* signature;
62 size_t signature_length;
63
a5db3e49 64 // ASes in the database
c182393f 65 struct loc_database_as_v0* as_v0;
a5db3e49
MT
66 size_t as_count;
67
f66b7b09
MT
68 // Network tree
69 struct loc_database_network_node_v0* network_nodes_v0;
70 size_t network_nodes_count;
71
a735a563
MT
72 // Networks
73 struct loc_database_network_v0* networks_v0;
74 size_t networks_count;
75
ec684c1a
MT
76 // Countries
77 struct loc_database_country_v0* countries_v0;
78 size_t countries_count;
79
2601e83e
MT
80 struct loc_stringpool* pool;
81};
82
e3f696c1
MT
83#define MAX_STACK_DEPTH 256
84
85struct loc_node_stack {
86 off_t offset;
87 int i; // Is this node 0 or 1?
88 int depth;
89};
90
7e13db74
MT
91struct loc_database_enumerator {
92 struct loc_ctx* ctx;
93 struct loc_database* db;
ccc7ab4e 94 enum loc_database_enumerator_mode mode;
7e13db74 95 int refcount;
d3d8ede6
MT
96
97 // Search string
98 char* string;
35bb3a32 99 char country_code[3];
82910b95 100 uint32_t asn;
9268db5a 101 enum loc_network_flags flags;
44e5ef71 102 int family;
d3d8ede6
MT
103
104 // Index of the AS we are looking at
105 unsigned int as_index;
e3f696c1
MT
106
107 // Network state
108 struct in6_addr network_address;
109 struct loc_node_stack network_stack[MAX_STACK_DEPTH];
110 int network_stack_depth;
111 unsigned int* networks_visited;
7e13db74
MT
112};
113
b1720435 114static int loc_database_read_magic(struct loc_database* db) {
2601e83e
MT
115 struct loc_database_magic magic;
116
117 // Read from file
b1720435 118 size_t bytes_read = fread(&magic, 1, sizeof(magic), db->f);
2601e83e
MT
119
120 // Check if we have been able to read enough data
121 if (bytes_read < sizeof(magic)) {
122 ERROR(db->ctx, "Could not read enough data to validate magic bytes\n");
123 DEBUG(db->ctx, "Read %zu bytes, but needed %zu\n", bytes_read, sizeof(magic));
124 return -ENOMSG;
125 }
126
127 // Compare magic bytes
128 if (memcmp(LOC_DATABASE_MAGIC, magic.magic, strlen(LOC_DATABASE_MAGIC)) == 0) {
129 DEBUG(db->ctx, "Magic value matches\n");
130
131 // Parse version
0676cd80 132 db->version = be16toh(magic.version);
2601e83e
MT
133 DEBUG(db->ctx, "Database version is %u\n", db->version);
134
135 return 0;
136 }
137
138 ERROR(db->ctx, "Database format is not compatible\n");
139
140 // Return an error
141 return 1;
142}
143
a5db3e49 144static int loc_database_read_as_section_v0(struct loc_database* db,
b1720435 145 const struct loc_database_header_v0* header) {
edb4ba7c
MT
146 off_t as_offset = be32toh(header->as_offset);
147 size_t as_length = be32toh(header->as_length);
148
5c57de03 149 DEBUG(db->ctx, "Reading AS section from %jd (%zu bytes)\n", (intmax_t)as_offset, as_length);
a5db3e49 150
c182393f
MT
151 if (as_length > 0) {
152 db->as_v0 = mmap(NULL, as_length, PROT_READ,
b1720435 153 MAP_SHARED, fileno(db->f), as_offset);
a5db3e49 154
c182393f
MT
155 if (db->as_v0 == MAP_FAILED)
156 return -errno;
a5db3e49
MT
157 }
158
c182393f
MT
159 db->as_count = as_length / sizeof(*db->as_v0);
160
a5db3e49
MT
161 INFO(db->ctx, "Read %zu ASes from the database\n", db->as_count);
162
163 return 0;
164}
165
f66b7b09 166static int loc_database_read_network_nodes_section_v0(struct loc_database* db,
b1720435 167 const struct loc_database_header_v0* header) {
edb4ba7c
MT
168 off_t network_nodes_offset = be32toh(header->network_tree_offset);
169 size_t network_nodes_length = be32toh(header->network_tree_length);
170
f66b7b09 171 DEBUG(db->ctx, "Reading network nodes section from %jd (%zu bytes)\n",
5c57de03 172 (intmax_t)network_nodes_offset, network_nodes_length);
f66b7b09
MT
173
174 if (network_nodes_length > 0) {
175 db->network_nodes_v0 = mmap(NULL, network_nodes_length, PROT_READ,
b1720435 176 MAP_SHARED, fileno(db->f), network_nodes_offset);
f66b7b09
MT
177
178 if (db->network_nodes_v0 == MAP_FAILED)
179 return -errno;
180 }
181
182 db->network_nodes_count = network_nodes_length / sizeof(*db->network_nodes_v0);
183
184 INFO(db->ctx, "Read %zu network nodes from the database\n", db->network_nodes_count);
185
186 return 0;
187}
188
a735a563 189static int loc_database_read_networks_section_v0(struct loc_database* db,
b1720435 190 const struct loc_database_header_v0* header) {
a735a563
MT
191 off_t networks_offset = be32toh(header->network_data_offset);
192 size_t networks_length = be32toh(header->network_data_length);
193
194 DEBUG(db->ctx, "Reading networks section from %jd (%zu bytes)\n",
5c57de03 195 (intmax_t)networks_offset, networks_length);
a735a563
MT
196
197 if (networks_length > 0) {
198 db->networks_v0 = mmap(NULL, networks_length, PROT_READ,
b1720435 199 MAP_SHARED, fileno(db->f), networks_offset);
a735a563
MT
200
201 if (db->networks_v0 == MAP_FAILED)
202 return -errno;
203 }
204
205 db->networks_count = networks_length / sizeof(*db->networks_v0);
206
207 INFO(db->ctx, "Read %zu networks from the database\n", db->networks_count);
208
209 return 0;
210}
211
ec684c1a 212static int loc_database_read_countries_section_v0(struct loc_database* db,
b1720435 213 const struct loc_database_header_v0* header) {
ec684c1a
MT
214 off_t countries_offset = be32toh(header->countries_offset);
215 size_t countries_length = be32toh(header->countries_length);
216
217 DEBUG(db->ctx, "Reading countries section from %jd (%zu bytes)\n",
2e2325a9 218 (intmax_t)countries_offset, countries_length);
ec684c1a
MT
219
220 if (countries_length > 0) {
221 db->countries_v0 = mmap(NULL, countries_length, PROT_READ,
b1720435 222 MAP_SHARED, fileno(db->f), countries_offset);
ec684c1a
MT
223
224 if (db->countries_v0 == MAP_FAILED)
225 return -errno;
226 }
227
228 db->countries_count = countries_length / sizeof(*db->countries_v0);
229
230 INFO(db->ctx, "Read %zu countries from the database\n",
231 db->countries_count);
232
233 return 0;
234}
235
b1720435 236static int loc_database_read_header_v0(struct loc_database* db) {
2601e83e
MT
237 struct loc_database_header_v0 header;
238
239 // Read from file
b1720435 240 size_t size = fread(&header, 1, sizeof(header), db->f);
2601e83e
MT
241
242 if (size < sizeof(header)) {
243 ERROR(db->ctx, "Could not read enough data for header\n");
244 return -ENOMSG;
245 }
246
247 // Copy over data
96ea74a5 248 db->created_at = be64toh(header.created_at);
0676cd80
MT
249 db->vendor = be32toh(header.vendor);
250 db->description = be32toh(header.description);
4bf49d00 251 db->license = be32toh(header.license);
2601e83e 252
726f9984
MT
253 // Read signature
254 db->signature_length = be32toh(header.signature_length);
255 if (db->signature_length) {
256 // Check for a plausible signature length
257 if (db->signature_length > LOC_SIGNATURE_MAX_LENGTH) {
258 ERROR(db->ctx, "Signature too long: %ld\n", db->signature_length);
259 return -EINVAL;
260 }
261
262 DEBUG(db->ctx, "Reading signature of %ld bytes\n",
263 db->signature_length);
264
265 db->signature = malloc(db->signature_length);
266 for (unsigned int i = 0; i < db->signature_length; i++)
267 db->signature[i] = header.signature[i];
268 }
269
2601e83e 270 // Open pool
0676cd80
MT
271 off_t pool_offset = be32toh(header.pool_offset);
272 size_t pool_length = be32toh(header.pool_length);
2601e83e 273
0e974d4b 274 int r = loc_stringpool_open(db->ctx, &db->pool,
b1720435 275 db->f, pool_length, pool_offset);
2601e83e
MT
276 if (r)
277 return r;
278
a5db3e49 279 // AS section
b1720435 280 r = loc_database_read_as_section_v0(db, &header);
a5db3e49
MT
281 if (r)
282 return r;
283
f66b7b09 284 // Network Nodes
b1720435 285 r = loc_database_read_network_nodes_section_v0(db, &header);
f66b7b09
MT
286 if (r)
287 return r;
288
a735a563 289 // Networks
b1720435 290 r = loc_database_read_networks_section_v0(db, &header);
a735a563
MT
291 if (r)
292 return r;
293
ec684c1a 294 // countries
b1720435 295 r = loc_database_read_countries_section_v0(db, &header);
ec684c1a
MT
296 if (r)
297 return r;
298
2601e83e
MT
299 return 0;
300}
301
b1720435 302static int loc_database_read_header(struct loc_database* db) {
2601e83e
MT
303 switch (db->version) {
304 case 0:
b1720435 305 return loc_database_read_header_v0(db);
2601e83e
MT
306
307 default:
308 ERROR(db->ctx, "Incompatible database version: %u\n", db->version);
309 return 1;
310 }
311}
312
a7431f1a 313static int loc_database_read(struct loc_database* db, FILE* f) {
02879100
MT
314 clock_t start = clock();
315
b1720435
MT
316 int fd = fileno(f);
317
318 // Clone file descriptor
319 fd = dup(fd);
320 if (!fd) {
321 ERROR(db->ctx, "Could not duplicate file descriptor\n");
322 return -1;
323 }
324
325 // Reopen the file so that we can keep our own file handle
326 db->f = fdopen(fd, "r");
327 if (!db->f) {
328 ERROR(db->ctx, "Could not re-open database file\n");
329 return -1;
330 }
331
332 // Rewind to the start of the file
333 rewind(db->f);
334
02879100 335 // Read magic bytes
b1720435 336 int r = loc_database_read_magic(db);
02879100
MT
337 if (r)
338 return r;
339
340 // Read the header
b1720435 341 r = loc_database_read_header(db);
02879100
MT
342 if (r)
343 return r;
344
345 clock_t end = clock();
346
e16c943b
MT
347 INFO(db->ctx, "Opened database in %.4fms\n",
348 (double)(end - start) / CLOCKS_PER_SEC * 1000);
02879100
MT
349
350 return 0;
351}
352
c182393f 353LOC_EXPORT int loc_database_new(struct loc_ctx* ctx, struct loc_database** database, FILE* f) {
a7431f1a
MT
354 // Fail on invalid file handle
355 if (!f)
356 return -EINVAL;
357
c182393f
MT
358 struct loc_database* db = calloc(1, sizeof(*db));
359 if (!db)
360 return -ENOMEM;
361
362 // Reference context
363 db->ctx = loc_ref(ctx);
364 db->refcount = 1;
365
366 DEBUG(db->ctx, "Database object allocated at %p\n", db);
367
a7431f1a 368 int r = loc_database_read(db, f);
02879100
MT
369 if (r) {
370 loc_database_unref(db);
2601e83e 371 return r;
02879100 372 }
2601e83e 373
c182393f
MT
374 *database = db;
375
2601e83e 376 return 0;
2601e83e
MT
377}
378
c182393f
MT
379LOC_EXPORT struct loc_database* loc_database_ref(struct loc_database* db) {
380 db->refcount++;
381
382 return db;
8f5b676a
MT
383}
384
c182393f 385static void loc_database_free(struct loc_database* db) {
f10ebc2d
MT
386 int r;
387
c182393f 388 DEBUG(db->ctx, "Releasing database %p\n", db);
c34e76f1 389
c182393f
MT
390 // Removing all ASes
391 if (db->as_v0) {
f10ebc2d 392 r = munmap(db->as_v0, db->as_count * sizeof(*db->as_v0));
c182393f
MT
393 if (r)
394 ERROR(db->ctx, "Could not unmap AS section: %s\n", strerror(errno));
395 }
c34e76f1 396
f10ebc2d
MT
397 // Remove mapped network sections
398 if (db->networks_v0) {
399 r = munmap(db->networks_v0, db->networks_count * sizeof(*db->networks_v0));
400 if (r)
401 ERROR(db->ctx, "Could not unmap networks section: %s\n", strerror(errno));
402 }
403
404 // Remove mapped network nodes section
405 if (db->network_nodes_v0) {
406 r = munmap(db->network_nodes_v0, db->network_nodes_count * sizeof(*db->network_nodes_v0));
407 if (r)
408 ERROR(db->ctx, "Could not unmap network nodes section: %s\n", strerror(errno));
409 }
410
e16c943b 411 loc_stringpool_unref(db->pool);
c34e76f1 412
726f9984
MT
413 // Free signature
414 if (db->signature)
415 free(db->signature);
416
b1720435
MT
417 // Close database file
418 if (db->f)
419 fclose(db->f);
420
c182393f
MT
421 loc_unref(db->ctx);
422 free(db);
c34e76f1
MT
423}
424
c182393f
MT
425LOC_EXPORT struct loc_database* loc_database_unref(struct loc_database* db) {
426 if (--db->refcount > 0)
427 return NULL;
78ace4ed 428
c182393f
MT
429 loc_database_free(db);
430 return NULL;
431}
78ace4ed 432
726f9984
MT
433LOC_EXPORT int loc_database_verify(struct loc_database* db, FILE* f) {
434 // Cannot do this when no signature is available
435 if (!db->signature) {
436 DEBUG(db->ctx, "No signature available to verify\n");
437 return 1;
438 }
439
c81205a5
MT
440 // Start the stopwatch
441 clock_t start = clock();
442
726f9984
MT
443 // Load public key
444 EVP_PKEY* pkey = PEM_read_PUBKEY(f, NULL, NULL, NULL);
445 if (!pkey) {
446 char* error = ERR_error_string(ERR_get_error(), NULL);
447 ERROR(db->ctx, "Could not parse public key: %s\n", error);
448
449 return -1;
450 }
451
b1720435
MT
452 int r = 0;
453
454 EVP_MD_CTX* mdctx = EVP_MD_CTX_new();
455
b1720435 456 // Initialise hash function
e7f4b2ce
MT
457 r = EVP_DigestVerifyInit(mdctx, NULL, NULL, NULL, pkey);
458 if (r != 1) {
459 ERROR(db->ctx, "Error initializing signature validation: %s\n",
460 ERR_error_string(ERR_get_error(), NULL));
461 r = 1;
462
463 goto CLEANUP;
464 }
b1720435
MT
465
466 // Reset file to start
467 rewind(db->f);
468
469 // Read magic
470 struct loc_database_magic magic;
471 fread(&magic, 1, sizeof(magic), db->f);
472
a0cff45d
MT
473 hexdump(db->ctx, &magic, sizeof(magic));
474
b1720435 475 // Feed magic into the hash
e7f4b2ce
MT
476 r = EVP_DigestVerifyUpdate(mdctx, &magic, sizeof(magic));
477 if (r != 1) {
478 ERROR(db->ctx, "%s\n", ERR_error_string(ERR_get_error(), NULL));
479 r = 1;
480
481 goto CLEANUP;
482 }
b1720435
MT
483
484 // Read the header
485 struct loc_database_header_v0 header_v0;
486
487 switch (db->version) {
488 case 0:
489 fread(&header_v0, 1, sizeof(header_v0), db->f);
490
491 // Clear signature
492 for (unsigned int i = 0; i < sizeof(header_v0.signature); i++) {
493 header_v0.signature[i] = '\0';
494 }
495
a0cff45d
MT
496 hexdump(db->ctx, &header_v0, sizeof(header_v0));
497
b1720435 498 // Feed header into the hash
a0cff45d 499 r = EVP_DigestVerifyUpdate(mdctx, &header_v0, sizeof(header_v0));
e7f4b2ce
MT
500 if (r != 1) {
501 ERROR(db->ctx, "%s\n", ERR_error_string(ERR_get_error(), NULL));
502 r = 1;
503
504 goto CLEANUP;
505 }
b1720435
MT
506 break;
507
508 default:
509 ERROR(db->ctx, "Cannot compute hash for database with format %d\n",
510 db->version);
511 r = -EINVAL;
512 goto CLEANUP;
513 }
514
726f9984
MT
515 // Walk through the file in chunks of 64kB
516 char buffer[64 * 1024];
b1720435
MT
517
518 while (!feof(db->f)) {
519 size_t bytes_read = fread(buffer, 1, sizeof(buffer), db->f);
520
a0cff45d
MT
521 hexdump(db->ctx, buffer, bytes_read);
522
e7f4b2ce
MT
523 r = EVP_DigestVerifyUpdate(mdctx, buffer, bytes_read);
524 if (r != 1) {
525 ERROR(db->ctx, "%s\n", ERR_error_string(ERR_get_error(), NULL));
526 r = 1;
527
528 goto CLEANUP;
529 }
b1720435
MT
530 }
531
726f9984
MT
532 // Finish
533 r = EVP_DigestVerifyFinal(mdctx,
534 (unsigned char*)db->signature, db->signature_length);
535
536 if (r == 0) {
726f9984 537 DEBUG(db->ctx, "The signature is invalid\n");
498aad15
MT
538 r = 1;
539 } else if (r == 1) {
540 DEBUG(db->ctx, "The signature is valid\n");
541 r = 0;
726f9984
MT
542 } else {
543 ERROR(db->ctx, "Error verifying the signature: %s\n",
544 ERR_error_string(ERR_get_error(), NULL));
498aad15 545 r = 1;
b1720435
MT
546 }
547
257626f5
MT
548 // Dump signature
549 hexdump(db->ctx, db->signature, db->signature_length);
550
c81205a5
MT
551 clock_t end = clock();
552 DEBUG(db->ctx, "Signature checked in %.4fms\n",
553 (double)(end - start) / CLOCKS_PER_SEC * 1000);
554
b1720435
MT
555CLEANUP:
556 // Cleanup
557 EVP_MD_CTX_free(mdctx);
726f9984 558 EVP_PKEY_free(pkey);
b1720435
MT
559
560 return r;
561}
562
c182393f
MT
563LOC_EXPORT time_t loc_database_created_at(struct loc_database* db) {
564 return db->created_at;
565}
78ace4ed 566
c182393f
MT
567LOC_EXPORT const char* loc_database_get_vendor(struct loc_database* db) {
568 return loc_stringpool_get(db->pool, db->vendor);
569}
78ace4ed 570
c182393f
MT
571LOC_EXPORT const char* loc_database_get_description(struct loc_database* db) {
572 return loc_stringpool_get(db->pool, db->description);
573}
78ace4ed 574
4bf49d00
MT
575LOC_EXPORT const char* loc_database_get_license(struct loc_database* db) {
576 return loc_stringpool_get(db->pool, db->license);
577}
578
c182393f
MT
579LOC_EXPORT size_t loc_database_count_as(struct loc_database* db) {
580 return db->as_count;
78ace4ed
MT
581}
582
c182393f
MT
583// Returns the AS at position pos
584static int loc_database_fetch_as(struct loc_database* db, struct loc_as** as, off_t pos) {
585 if ((size_t)pos >= db->as_count)
586 return -EINVAL;
2601e83e 587
5c57de03 588 DEBUG(db->ctx, "Fetching AS at position %jd\n", (intmax_t)pos);
2601e83e
MT
589
590 int r;
c182393f
MT
591 switch (db->version) {
592 case 0:
593 r = loc_as_new_from_database_v0(db->ctx, db->pool, as, db->as_v0 + pos);
594 break;
2601e83e 595
c182393f
MT
596 default:
597 return -1;
598 }
2601e83e 599
c182393f
MT
600 if (r == 0) {
601 DEBUG(db->ctx, "Got AS%u\n", loc_as_get_number(*as));
2601e83e 602 }
2601e83e 603
c182393f
MT
604 return r;
605}
c34e76f1 606
c182393f
MT
607// Performs a binary search to find the AS in the list
608LOC_EXPORT int loc_database_get_as(struct loc_database* db, struct loc_as** as, uint32_t number) {
609 off_t lo = 0;
610 off_t hi = db->as_count - 1;
c34e76f1 611
8f3e2a06
MT
612 // Save start time
613 clock_t start = clock();
614
c182393f
MT
615 while (lo <= hi) {
616 off_t i = (lo + hi) / 2;
8f5b676a 617
c182393f
MT
618 // Fetch AS in the middle between lo and hi
619 int r = loc_database_fetch_as(db, as, i);
620 if (r)
621 return r;
a5db3e49 622
c182393f
MT
623 // Check if this is a match
624 uint32_t as_number = loc_as_get_number(*as);
8f3e2a06
MT
625 if (as_number == number) {
626 clock_t end = clock();
627
628 // Log how fast this has been
e16c943b
MT
629 DEBUG(db->ctx, "Found AS%u in %.4fms\n", as_number,
630 (double)(end - start) / CLOCKS_PER_SEC * 1000);
8f3e2a06 631
c182393f 632 return 0;
8f3e2a06 633 }
c182393f
MT
634
635 // If it wasn't, we release the AS and
636 // adjust our search pointers
637 loc_as_unref(*as);
638
639 if (as_number < number) {
640 lo = i + 1;
641 } else
642 hi = i - 1;
643 }
2601e83e 644
c182393f
MT
645 // Nothing found
646 *as = NULL;
2601e83e 647
8f3e2a06 648 return 1;
2601e83e 649}
10778041
MT
650
651// Returns the network at position pos
39a55353
MT
652static int loc_database_fetch_network(struct loc_database* db, struct loc_network** network,
653 struct in6_addr* address, unsigned int prefix, off_t pos) {
9b9e5faf
MT
654 if ((size_t)pos >= db->networks_count) {
655 DEBUG(db->ctx, "Network ID out of range: %jd/%jd\n",
656 (intmax_t)pos, (intmax_t)db->networks_count);
10778041 657 return -EINVAL;
9b9e5faf
MT
658 }
659
10778041 660
5c57de03 661 DEBUG(db->ctx, "Fetching network at position %jd\n", (intmax_t)pos);
10778041
MT
662
663 int r;
664 switch (db->version) {
665 case 0:
39a55353
MT
666 r = loc_network_new_from_database_v0(db->ctx, network,
667 address, prefix, db->networks_v0 + pos);
10778041
MT
668 break;
669
670 default:
671 return -1;
672 }
673
674 if (r == 0) {
675 char* string = loc_network_str(*network);
676 DEBUG(db->ctx, "Got network %s\n", string);
677 free(string);
678 }
679
680 return r;
681}
2a30e4de 682
025ef489 683static int __loc_database_node_is_leaf(const struct loc_database_network_node_v0* node) {
39a55353 684 return (node->network != htobe32(0xffffffff));
025ef489
MT
685}
686
687static int __loc_database_lookup_handle_leaf(struct loc_database* db, const struct in6_addr* address,
39a55353 688 struct loc_network** network, struct in6_addr* network_address, unsigned int prefix,
2a30e4de 689 const struct loc_database_network_node_v0* node) {
39a55353
MT
690 off_t network_index = be32toh(node->network);
691
5c57de03 692 DEBUG(db->ctx, "Handling leaf node at %jd (%jd)\n", (intmax_t)(node - db->network_nodes_v0), (intmax_t)network_index);
2a30e4de
MT
693
694 // Fetch the network
695 int r = loc_database_fetch_network(db, network,
39a55353 696 network_address, prefix, network_index);
e85e2b0b 697 if (r) {
5c57de03 698 ERROR(db->ctx, "Could not fetch network %jd from database\n", (intmax_t)network_index);
2a30e4de 699 return r;
e85e2b0b 700 }
39a55353 701
2a30e4de
MT
702 // Check if the given IP address is inside the network
703 r = loc_network_match_address(*network, address);
704 if (r) {
705 DEBUG(db->ctx, "Searched address is not part of the network\n");
706
707 loc_network_unref(*network);
708 *network = NULL;
709 return 1;
710 }
711
712 // A network was found and the IP address matches
713 return 0;
714}
715
2a30e4de
MT
716// Searches for an exact match along the path
717static int __loc_database_lookup(struct loc_database* db, const struct in6_addr* address,
718 struct loc_network** network, struct in6_addr* network_address,
f66f15e1 719 const struct loc_database_network_node_v0* node, unsigned int level) {
025ef489 720 int r;
2a30e4de
MT
721 off_t node_index;
722
723 // Follow the path
724 int bit = in6_addr_get_bit(address, level);
725 in6_addr_set_bit(network_address, level, bit);
726
727 if (bit == 0)
728 node_index = be32toh(node->zero);
729 else
730 node_index = be32toh(node->one);
731
9086d2b1
MT
732 // If the node index is zero, the tree ends here
733 // and we cannot descend any further
734 if (node_index > 0) {
735 // Check boundaries
736 if ((size_t)node_index >= db->network_nodes_count)
737 return -EINVAL;
2a30e4de 738
9086d2b1
MT
739 // Move on to the next node
740 r = __loc_database_lookup(db, address, network, network_address,
741 db->network_nodes_v0 + node_index, level + 1);
2a30e4de 742
9086d2b1
MT
743 // End here if a result was found
744 if (r == 0)
745 return r;
2a30e4de 746
9086d2b1
MT
747 // Raise any errors
748 else if (r < 0)
749 return r;
ec1d9681
MT
750
751 DEBUG(db->ctx, "No match found below level %u\n", level);
752 } else {
753 DEBUG(db->ctx, "Tree ended at level %u\n", level);
9086d2b1 754 }
2a30e4de 755
9086d2b1
MT
756 // If this node has a leaf, we will check if it matches
757 if (__loc_database_node_is_leaf(node)) {
758 r = __loc_database_lookup_handle_leaf(db, address, network, network_address, level, node);
759 if (r <= 0)
760 return r;
761 }
2a30e4de 762
ec1d9681 763 return 1;
2a30e4de
MT
764}
765
766LOC_EXPORT int loc_database_lookup(struct loc_database* db,
767 struct in6_addr* address, struct loc_network** network) {
768 struct in6_addr network_address;
769 memset(&network_address, 0, sizeof(network_address));
770
771 *network = NULL;
772
773 // Save start time
774 clock_t start = clock();
775
776 int r = __loc_database_lookup(db, address, network, &network_address,
777 db->network_nodes_v0, 0);
778
779 clock_t end = clock();
780
781 // Log how fast this has been
e16c943b
MT
782 DEBUG(db->ctx, "Executed network search in %.4fms\n",
783 (double)(end - start) / CLOCKS_PER_SEC * 1000);
2a30e4de
MT
784
785 return r;
786}
787
788LOC_EXPORT int loc_database_lookup_from_string(struct loc_database* db,
789 const char* string, struct loc_network** network) {
790 struct in6_addr address;
791
792 int r = loc_parse_address(db->ctx, string, &address);
793 if (r)
794 return r;
795
796 return loc_database_lookup(db, &address, network);
797}
7e13db74 798
ec684c1a
MT
799// Returns the country at position pos
800static int loc_database_fetch_country(struct loc_database* db,
801 struct loc_country** country, off_t pos) {
802 if ((size_t)pos >= db->countries_count)
803 return -EINVAL;
804
2e2325a9 805 DEBUG(db->ctx, "Fetching country at position %jd\n", (intmax_t)pos);
ec684c1a
MT
806
807 int r;
808 switch (db->version) {
809 case 0:
810 r = loc_country_new_from_database_v0(db->ctx, db->pool, country, db->countries_v0 + pos);
811 break;
812
813 default:
814 return -1;
815 }
816
817 if (r == 0) {
818 DEBUG(db->ctx, "Got country %s\n", loc_country_get_code(*country));
819 }
820
821 return r;
822}
823
824// Performs a binary search to find the country in the list
825LOC_EXPORT int loc_database_get_country(struct loc_database* db,
826 struct loc_country** country, const char* code) {
827 off_t lo = 0;
828 off_t hi = db->countries_count - 1;
829
830 // Save start time
831 clock_t start = clock();
832
833 while (lo <= hi) {
834 off_t i = (lo + hi) / 2;
835
836 // Fetch country in the middle between lo and hi
837 int r = loc_database_fetch_country(db, country, i);
838 if (r)
839 return r;
840
841 // Check if this is a match
842 const char* cc = loc_country_get_code(*country);
843 int result = strcmp(code, cc);
844
845 if (result == 0) {
846 clock_t end = clock();
847
848 // Log how fast this has been
849 DEBUG(db->ctx, "Found country %s in %.4fms\n", cc,
850 (double)(end - start) / CLOCKS_PER_SEC * 1000);
851
852 return 0;
853 }
854
855 // If it wasn't, we release the country and
856 // adjust our search pointers
857 loc_country_unref(*country);
858
191830da 859 if (result > 0) {
ec684c1a
MT
860 lo = i + 1;
861 } else
862 hi = i - 1;
863 }
864
865 // Nothing found
866 *country = NULL;
867
868 return 1;
869}
870
7e13db74
MT
871// Enumerator
872
ccc7ab4e
MT
873LOC_EXPORT int loc_database_enumerator_new(struct loc_database_enumerator** enumerator,
874 struct loc_database* db, enum loc_database_enumerator_mode mode) {
7e13db74
MT
875 struct loc_database_enumerator* e = calloc(1, sizeof(*e));
876 if (!e)
877 return -ENOMEM;
878
879 // Reference context
880 e->ctx = loc_ref(db->ctx);
881 e->db = loc_database_ref(db);
ccc7ab4e 882 e->mode = mode;
7e13db74
MT
883 e->refcount = 1;
884
e3f696c1
MT
885 // Initialise graph search
886 //e->network_stack[++e->network_stack_depth] = 0;
887 e->network_stack_depth = 1;
888 e->networks_visited = calloc(db->network_nodes_count, sizeof(*e->networks_visited));
889
7e13db74
MT
890 DEBUG(e->ctx, "Database enumerator object allocated at %p\n", e);
891
892 *enumerator = e;
893 return 0;
894}
895
896LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_ref(struct loc_database_enumerator* enumerator) {
897 enumerator->refcount++;
898
899 return enumerator;
900}
901
902static void loc_database_enumerator_free(struct loc_database_enumerator* enumerator) {
903 DEBUG(enumerator->ctx, "Releasing database enumerator %p\n", enumerator);
904
905 // Release all references
906 loc_database_unref(enumerator->db);
907 loc_unref(enumerator->ctx);
908
d3d8ede6
MT
909 if (enumerator->string)
910 free(enumerator->string);
911
91d89020
MT
912 // Free network search
913 free(enumerator->networks_visited);
914
7e13db74
MT
915 free(enumerator);
916}
917
918LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_unref(struct loc_database_enumerator* enumerator) {
919 if (!enumerator)
920 return NULL;
921
922 if (--enumerator->refcount > 0)
923 return enumerator;
924
925 loc_database_enumerator_free(enumerator);
926 return NULL;
927}
d3d8ede6
MT
928
929LOC_EXPORT int loc_database_enumerator_set_string(struct loc_database_enumerator* enumerator, const char* string) {
930 enumerator->string = strdup(string);
931
932 // Make the string lowercase
933 for (char *p = enumerator->string; *p; p++)
934 *p = tolower(*p);
935
936 return 0;
937}
938
35bb3a32
MT
939LOC_EXPORT int loc_database_enumerator_set_country_code(struct loc_database_enumerator* enumerator, const char* country_code) {
940 // Set empty country code
941 if (!country_code || !*country_code) {
942 *enumerator->country_code = '\0';
943 return 0;
944 }
945
4ef1761f
MT
946 // Treat A1, A2, A3 as special country codes,
947 // but perform search for flags instead
948 if (strcmp(country_code, "A1") == 0) {
949 return loc_database_enumerator_set_flag(enumerator,
950 LOC_NETWORK_FLAG_ANONYMOUS_PROXY);
951 } else if (strcmp(country_code, "A2") == 0) {
952 return loc_database_enumerator_set_flag(enumerator,
953 LOC_NETWORK_FLAG_SATELLITE_PROVIDER);
954 } else if (strcmp(country_code, "A3") == 0) {
955 return loc_database_enumerator_set_flag(enumerator,
956 LOC_NETWORK_FLAG_ANYCAST);
957 }
958
57146963
MT
959 // Country codes must be two characters
960 if (!loc_country_code_is_valid(country_code))
961 return -EINVAL;
962
35bb3a32
MT
963 for (unsigned int i = 0; i < 3; i++) {
964 enumerator->country_code[i] = country_code[i];
965 }
966
967 return 0;
968}
969
82910b95
MT
970LOC_EXPORT int loc_database_enumerator_set_asn(
971 struct loc_database_enumerator* enumerator, unsigned int asn) {
972 enumerator->asn = asn;
973
974 return 0;
975}
976
9268db5a
MT
977LOC_EXPORT int loc_database_enumerator_set_flag(
978 struct loc_database_enumerator* enumerator, enum loc_network_flags flag) {
979 enumerator->flags |= flag;
980
981 return 0;
982}
983
44e5ef71
MT
984LOC_EXPORT int loc_database_enumerator_set_family(
985 struct loc_database_enumerator* enumerator, int family) {
986 enumerator->family = family;
987
988 return 0;
989}
990
15f79e2d
MT
991LOC_EXPORT int loc_database_enumerator_next_as(
992 struct loc_database_enumerator* enumerator, struct loc_as** as) {
993 *as = NULL;
994
ccc7ab4e
MT
995 // Do not do anything if not in AS mode
996 if (enumerator->mode != LOC_DB_ENUMERATE_ASES)
15f79e2d 997 return 0;
ccc7ab4e 998
d3d8ede6 999 struct loc_database* db = enumerator->db;
d3d8ede6
MT
1000
1001 while (enumerator->as_index < db->as_count) {
1002 // Fetch the next AS
15f79e2d 1003 int r = loc_database_fetch_as(db, as, enumerator->as_index++);
d3d8ede6 1004 if (r)
15f79e2d 1005 return r;
d3d8ede6 1006
15f79e2d 1007 r = loc_as_match_string(*as, enumerator->string);
273948cf 1008 if (r == 1) {
d3d8ede6 1009 DEBUG(enumerator->ctx, "AS%d (%s) matches %s\n",
15f79e2d 1010 loc_as_get_number(*as), loc_as_get_name(*as), enumerator->string);
d3d8ede6 1011
15f79e2d 1012 return 0;
d3d8ede6
MT
1013 }
1014
1015 // No match
15f79e2d 1016 loc_as_unref(*as);
74f218f0 1017 *as = NULL;
d3d8ede6
MT
1018 }
1019
1020 // Reset the index
1021 enumerator->as_index = 0;
1022
1023 // We have searched through all of them
15f79e2d 1024 return 0;
d3d8ede6 1025}
e3f696c1
MT
1026
1027static int loc_database_enumerator_stack_push_node(
1028 struct loc_database_enumerator* e, off_t offset, int i, int depth) {
1029 // Do not add empty nodes
1030 if (!offset)
1031 return 0;
1032
1033 // Check if there is any space left on the stack
1034 if (e->network_stack_depth >= MAX_STACK_DEPTH) {
1035 ERROR(e->ctx, "Maximum stack size reached: %d\n", e->network_stack_depth);
1036 return -1;
1037 }
1038
1039 // Increase stack size
1040 int s = ++e->network_stack_depth;
1041
2e2325a9 1042 DEBUG(e->ctx, "Added node %jd to stack (%d)\n", (intmax_t)offset, depth);
e3f696c1
MT
1043
1044 e->network_stack[s].offset = offset;
1045 e->network_stack[s].i = i;
1046 e->network_stack[s].depth = depth;
1047
1048 return 0;
1049}
1050
15f79e2d
MT
1051LOC_EXPORT int loc_database_enumerator_next_network(
1052 struct loc_database_enumerator* enumerator, struct loc_network** network) {
e3f696c1
MT
1053 // Reset network
1054 *network = NULL;
15f79e2d
MT
1055
1056 // Do not do anything if not in network mode
1057 if (enumerator->mode != LOC_DB_ENUMERATE_NETWORKS)
1058 return 0;
1059
e3f696c1
MT
1060 int r;
1061
15f79e2d
MT
1062 DEBUG(enumerator->ctx, "Called with a stack of %u nodes\n",
1063 enumerator->network_stack_depth);
e3f696c1
MT
1064
1065 // Perform DFS
15f79e2d
MT
1066 while (enumerator->network_stack_depth > 0) {
1067 DEBUG(enumerator->ctx, "Stack depth: %u\n", enumerator->network_stack_depth);
e3f696c1
MT
1068
1069 // Get object from top of the stack
15f79e2d 1070 struct loc_node_stack* node = &enumerator->network_stack[enumerator->network_stack_depth];
e3f696c1
MT
1071
1072 // Remove the node from the stack if we have already visited it
15f79e2d
MT
1073 if (enumerator->networks_visited[node->offset]) {
1074 enumerator->network_stack_depth--;
e3f696c1
MT
1075 continue;
1076 }
1077
74fb733a 1078 // Mark the bits on the path correctly
15f79e2d 1079 in6_addr_set_bit(&enumerator->network_address,
e3f696c1
MT
1080 (node->depth > 0) ? node->depth - 1 : 0, node->i);
1081
2e2325a9 1082 DEBUG(enumerator->ctx, "Looking at node %jd\n", (intmax_t)node->offset);
15f79e2d 1083 enumerator->networks_visited[node->offset]++;
e3f696c1
MT
1084
1085 // Pop node from top of the stack
1086 struct loc_database_network_node_v0* n =
15f79e2d 1087 enumerator->db->network_nodes_v0 + node->offset;
e3f696c1
MT
1088
1089 // Add edges to stack
15f79e2d 1090 r = loc_database_enumerator_stack_push_node(enumerator,
e3f696c1
MT
1091 be32toh(n->one), 1, node->depth + 1);
1092
1093 if (r)
1094 return r;
1095
15f79e2d 1096 r = loc_database_enumerator_stack_push_node(enumerator,
e3f696c1
MT
1097 be32toh(n->zero), 0, node->depth + 1);
1098
1099 if (r)
1100 return r;
1101
1102 // Check if this node is a leaf and has a network object
1103 if (__loc_database_node_is_leaf(n)) {
1104 off_t network_index = be32toh(n->network);
1105
2e2325a9 1106 DEBUG(enumerator->ctx, "Node has a network at %jd\n", (intmax_t)network_index);
e3f696c1
MT
1107
1108 // Fetch the network object
15f79e2d
MT
1109 r = loc_database_fetch_network(enumerator->db, network,
1110 &enumerator->network_address, node->depth, network_index);
e3f696c1
MT
1111
1112 // Break on any errors
1113 if (r)
1114 return r;
1115
1116 // Check if we are interested in this network
1117
44e5ef71
MT
1118 // Skip if the family does not match
1119 if (enumerator->family && loc_network_address_family(*network) != enumerator->family) {
1120 loc_network_unref(*network);
1121 *network = NULL;
1122
1123 continue;
1124 }
1125
e3f696c1 1126 // Skip if the country code does not match
435b621e 1127 if (*enumerator->country_code &&
15f79e2d 1128 !loc_network_match_country_code(*network, enumerator->country_code)) {
e3f696c1 1129 loc_network_unref(*network);
15f79e2d
MT
1130 *network = NULL;
1131
e3f696c1
MT
1132 continue;
1133 }
1134
82910b95 1135 // Skip if the ASN does not match
15f79e2d
MT
1136 if (enumerator->asn &&
1137 !loc_network_match_asn(*network, enumerator->asn)) {
82910b95 1138 loc_network_unref(*network);
15f79e2d
MT
1139 *network = NULL;
1140
82910b95
MT
1141 continue;
1142 }
1143
9268db5a
MT
1144 // Skip if flags do not match
1145 if (enumerator->flags &&
1146 !loc_network_match_flag(*network, enumerator->flags)) {
1147 loc_network_unref(*network);
1148 *network = NULL;
1149 }
1150
e3f696c1
MT
1151 return 0;
1152 }
1153 }
1154
1155 // Reached the end of the search
fe483cdc
MT
1156
1157 // Mark all nodes as non-visited
15f79e2d
MT
1158 for (unsigned int i = 0; i < enumerator->db->network_nodes_count; i++)
1159 enumerator->networks_visited[i] = 0;
e3f696c1
MT
1160
1161 return 0;
1162}