python: Avoid declaring loc_ctx multiple times
[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>
0676cd80 19#include <endian.h>
2601e83e 20#include <errno.h>
10778041 21#include <netinet/in.h>
2601e83e
MT
22#include <stddef.h>
23#include <stdint.h>
24#include <stdio.h>
25#include <stdlib.h>
26#include <string.h>
c182393f 27#include <sys/mman.h>
2601e83e 28#include <sys/types.h>
96ea74a5 29#include <time.h>
3f35869a 30#include <unistd.h>
2601e83e
MT
31
32#include <loc/libloc.h>
9fc7f001
MT
33#include <loc/as.h>
34#include <loc/database.h>
a5db3e49 35#include <loc/format.h>
10778041 36#include <loc/network.h>
9fc7f001
MT
37#include <loc/private.h>
38#include <loc/stringpool.h>
2601e83e
MT
39
40struct loc_database {
41 struct loc_ctx* ctx;
42 int refcount;
43
44 unsigned int version;
96ea74a5 45 time_t created_at;
2601e83e
MT
46 off_t vendor;
47 off_t description;
4bf49d00 48 off_t license;
2601e83e 49
a5db3e49 50 // ASes in the database
c182393f 51 struct loc_database_as_v0* as_v0;
a5db3e49
MT
52 size_t as_count;
53
f66b7b09
MT
54 // Network tree
55 struct loc_database_network_node_v0* network_nodes_v0;
56 size_t network_nodes_count;
57
a735a563
MT
58 // Networks
59 struct loc_database_network_v0* networks_v0;
60 size_t networks_count;
61
2601e83e
MT
62 struct loc_stringpool* pool;
63};
64
7e13db74
MT
65struct loc_database_enumerator {
66 struct loc_ctx* ctx;
67 struct loc_database* db;
68 int refcount;
d3d8ede6
MT
69
70 // Search string
71 char* string;
72
73 // Index of the AS we are looking at
74 unsigned int as_index;
7e13db74
MT
75};
76
a7431f1a 77static int loc_database_read_magic(struct loc_database* db, FILE* f) {
2601e83e
MT
78 struct loc_database_magic magic;
79
80 // Read from file
a7431f1a 81 size_t bytes_read = fread(&magic, 1, sizeof(magic), f);
2601e83e
MT
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
0676cd80 95 db->version = be16toh(magic.version);
2601e83e
MT
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
a5db3e49 107static int loc_database_read_as_section_v0(struct loc_database* db,
edb4ba7c
MT
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
c182393f 112 DEBUG(db->ctx, "Reading AS section from %jd (%zu bytes)\n", as_offset, as_length);
a5db3e49 113
c182393f
MT
114 if (as_length > 0) {
115 db->as_v0 = mmap(NULL, as_length, PROT_READ,
a7431f1a 116 MAP_SHARED, fileno(f), as_offset);
a5db3e49 117
c182393f
MT
118 if (db->as_v0 == MAP_FAILED)
119 return -errno;
a5db3e49
MT
120 }
121
c182393f
MT
122 db->as_count = as_length / sizeof(*db->as_v0);
123
a5db3e49
MT
124 INFO(db->ctx, "Read %zu ASes from the database\n", db->as_count);
125
126 return 0;
127}
128
f66b7b09 129static int loc_database_read_network_nodes_section_v0(struct loc_database* db,
edb4ba7c
MT
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
f66b7b09
MT
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
a735a563
MT
152static 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
a7431f1a 175static int loc_database_read_header_v0(struct loc_database* db, FILE* f) {
2601e83e
MT
176 struct loc_database_header_v0 header;
177
178 // Read from file
a7431f1a 179 size_t size = fread(&header, 1, sizeof(header), f);
2601e83e
MT
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
96ea74a5 187 db->created_at = be64toh(header.created_at);
0676cd80
MT
188 db->vendor = be32toh(header.vendor);
189 db->description = be32toh(header.description);
4bf49d00 190 db->license = be32toh(header.license);
2601e83e
MT
191
192 // Open pool
0676cd80
MT
193 off_t pool_offset = be32toh(header.pool_offset);
194 size_t pool_length = be32toh(header.pool_length);
2601e83e 195
0e974d4b 196 int r = loc_stringpool_open(db->ctx, &db->pool,
a7431f1a 197 f, pool_length, pool_offset);
2601e83e
MT
198 if (r)
199 return r;
200
a5db3e49 201 // AS section
edb4ba7c 202 r = loc_database_read_as_section_v0(db, f, &header);
a5db3e49
MT
203 if (r)
204 return r;
205
f66b7b09 206 // Network Nodes
edb4ba7c 207 r = loc_database_read_network_nodes_section_v0(db, f, &header);
f66b7b09
MT
208 if (r)
209 return r;
210
a735a563
MT
211 // Networks
212 r = loc_database_read_networks_section_v0(db, f, &header);
213 if (r)
214 return r;
215
2601e83e
MT
216 return 0;
217}
218
a7431f1a 219static int loc_database_read_header(struct loc_database* db, FILE* f) {
2601e83e
MT
220 switch (db->version) {
221 case 0:
a7431f1a 222 return loc_database_read_header_v0(db, f);
2601e83e
MT
223
224 default:
225 ERROR(db->ctx, "Incompatible database version: %u\n", db->version);
226 return 1;
227 }
228}
229
a7431f1a 230static int loc_database_read(struct loc_database* db, FILE* f) {
02879100
MT
231 clock_t start = clock();
232
233 // Read magic bytes
a7431f1a 234 int r = loc_database_read_magic(db, f);
02879100
MT
235 if (r)
236 return r;
237
238 // Read the header
a7431f1a 239 r = loc_database_read_header(db, f);
02879100
MT
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
c182393f 251LOC_EXPORT int loc_database_new(struct loc_ctx* ctx, struct loc_database** database, FILE* f) {
a7431f1a
MT
252 // Fail on invalid file handle
253 if (!f)
254 return -EINVAL;
255
c182393f
MT
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
a7431f1a 266 int r = loc_database_read(db, f);
02879100
MT
267 if (r) {
268 loc_database_unref(db);
2601e83e 269 return r;
02879100 270 }
2601e83e 271
c182393f
MT
272 *database = db;
273
2601e83e 274 return 0;
2601e83e
MT
275}
276
c182393f
MT
277LOC_EXPORT struct loc_database* loc_database_ref(struct loc_database* db) {
278 db->refcount++;
279
280 return db;
8f5b676a
MT
281}
282
c182393f 283static void loc_database_free(struct loc_database* db) {
f10ebc2d
MT
284 int r;
285
c182393f 286 DEBUG(db->ctx, "Releasing database %p\n", db);
c34e76f1 287
c182393f
MT
288 // Removing all ASes
289 if (db->as_v0) {
f10ebc2d 290 r = munmap(db->as_v0, db->as_count * sizeof(*db->as_v0));
c182393f
MT
291 if (r)
292 ERROR(db->ctx, "Could not unmap AS section: %s\n", strerror(errno));
293 }
c34e76f1 294
f10ebc2d
MT
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
c182393f 309 loc_stringpool_unref(db->pool);
c34e76f1 310
c182393f
MT
311 loc_unref(db->ctx);
312 free(db);
c34e76f1
MT
313}
314
c182393f
MT
315LOC_EXPORT struct loc_database* loc_database_unref(struct loc_database* db) {
316 if (--db->refcount > 0)
317 return NULL;
78ace4ed 318
c182393f
MT
319 loc_database_free(db);
320 return NULL;
321}
78ace4ed 322
c182393f
MT
323LOC_EXPORT time_t loc_database_created_at(struct loc_database* db) {
324 return db->created_at;
325}
78ace4ed 326
c182393f
MT
327LOC_EXPORT const char* loc_database_get_vendor(struct loc_database* db) {
328 return loc_stringpool_get(db->pool, db->vendor);
329}
78ace4ed 330
c182393f
MT
331LOC_EXPORT const char* loc_database_get_description(struct loc_database* db) {
332 return loc_stringpool_get(db->pool, db->description);
333}
78ace4ed 334
4bf49d00
MT
335LOC_EXPORT const char* loc_database_get_license(struct loc_database* db) {
336 return loc_stringpool_get(db->pool, db->license);
337}
338
c182393f
MT
339LOC_EXPORT size_t loc_database_count_as(struct loc_database* db) {
340 return db->as_count;
78ace4ed
MT
341}
342
c182393f
MT
343// Returns the AS at position pos
344static 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;
2601e83e 347
c182393f 348 DEBUG(db->ctx, "Fetching AS at position %jd\n", pos);
2601e83e
MT
349
350 int r;
c182393f
MT
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;
2601e83e 355
c182393f
MT
356 default:
357 return -1;
358 }
2601e83e 359
c182393f
MT
360 if (r == 0) {
361 DEBUG(db->ctx, "Got AS%u\n", loc_as_get_number(*as));
2601e83e 362 }
2601e83e 363
c182393f
MT
364 return r;
365}
c34e76f1 366
c182393f
MT
367// Performs a binary search to find the AS in the list
368LOC_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;
c34e76f1 371
8f3e2a06
MT
372 // Save start time
373 clock_t start = clock();
374
c182393f
MT
375 while (lo <= hi) {
376 off_t i = (lo + hi) / 2;
8f5b676a 377
c182393f
MT
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;
a5db3e49 382
c182393f
MT
383 // Check if this is a match
384 uint32_t as_number = loc_as_get_number(*as);
8f3e2a06
MT
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
c182393f 392 return 0;
8f3e2a06 393 }
c182393f
MT
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 }
2601e83e 404
c182393f
MT
405 // Nothing found
406 *as = NULL;
2601e83e 407
8f3e2a06 408 return 1;
2601e83e 409}
10778041
MT
410
411// Returns the network at position pos
39a55353
MT
412static int loc_database_fetch_network(struct loc_database* db, struct loc_network** network,
413 struct in6_addr* address, unsigned int prefix, off_t pos) {
10778041
MT
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:
39a55353
MT
422 r = loc_network_new_from_database_v0(db->ctx, network,
423 address, prefix, db->networks_v0 + pos);
10778041
MT
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}
2a30e4de 438
025ef489 439static int __loc_database_node_is_leaf(const struct loc_database_network_node_v0* node) {
39a55353 440 return (node->network != htobe32(0xffffffff));
025ef489
MT
441}
442
443static int __loc_database_lookup_handle_leaf(struct loc_database* db, const struct in6_addr* address,
39a55353 444 struct loc_network** network, struct in6_addr* network_address, unsigned int prefix,
2a30e4de 445 const struct loc_database_network_node_v0* node) {
39a55353
MT
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);
2a30e4de
MT
449
450 // Fetch the network
451 int r = loc_database_fetch_network(db, network,
39a55353 452 network_address, prefix, network_index);
e85e2b0b
MT
453 if (r) {
454 ERROR(db->ctx, "Could not fetch network %jd from database\n", network_index);
2a30e4de 455 return r;
e85e2b0b 456 }
39a55353 457
2a30e4de
MT
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
2a30e4de
MT
472// Searches for an exact match along the path
473static int __loc_database_lookup(struct loc_database* db, const struct in6_addr* address,
474 struct loc_network** network, struct in6_addr* network_address,
f66f15e1 475 const struct loc_database_network_node_v0* node, unsigned int level) {
025ef489 476 int r;
2a30e4de
MT
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
9086d2b1
MT
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;
2a30e4de 494
9086d2b1
MT
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);
2a30e4de 498
9086d2b1
MT
499 // End here if a result was found
500 if (r == 0)
501 return r;
2a30e4de 502
9086d2b1
MT
503 // Raise any errors
504 else if (r < 0)
505 return r;
ec1d9681
MT
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);
9086d2b1 510 }
2a30e4de 511
9086d2b1
MT
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 }
2a30e4de 518
ec1d9681 519 return 1;
2a30e4de
MT
520}
521
522LOC_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
544LOC_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}
7e13db74
MT
554
555// Enumerator
556
557LOC_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
573LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_ref(struct loc_database_enumerator* enumerator) {
574 enumerator->refcount++;
575
576 return enumerator;
577}
578
579static 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
d3d8ede6
MT
586 if (enumerator->string)
587 free(enumerator->string);
588
7e13db74
MT
589 free(enumerator);
590}
591
592LOC_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}
d3d8ede6
MT
602
603LOC_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
613LOC_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);
273948cf 624 if (r == 1) {
d3d8ede6
MT
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}