network: Allow setting an empty country code
[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
412static int loc_database_fetch_network(struct loc_database* db, struct loc_network** network, struct in6_addr* address, off_t pos) {
413 if ((size_t)pos >= db->networks_count)
414 return -EINVAL;
415
416 DEBUG(db->ctx, "Fetching network at position %jd\n", pos);
417
418 int r;
419 switch (db->version) {
420 case 0:
421 r = loc_network_new_from_database_v0(db->ctx, network, address, db->networks_v0 + pos);
422 break;
423
424 default:
425 return -1;
426 }
427
428 if (r == 0) {
429 char* string = loc_network_str(*network);
430 DEBUG(db->ctx, "Got network %s\n", string);
431 free(string);
432 }
433
434 return r;
435}
2a30e4de 436
025ef489
MT
437static int __loc_database_node_is_leaf(const struct loc_database_network_node_v0* node) {
438 return (node->zero == htobe32(0xffffffff));
439}
440
441static int __loc_database_lookup_handle_leaf(struct loc_database* db, const struct in6_addr* address,
2a30e4de
MT
442 struct loc_network** network, struct in6_addr* network_address,
443 const struct loc_database_network_node_v0* node) {
025ef489 444 DEBUG(db->ctx, "Handling leaf node at %jd\n", node - db->network_nodes_v0);
2a30e4de
MT
445
446 // Fetch the network
447 int r = loc_database_fetch_network(db, network,
448 network_address, be32toh(node->one));
449 if (r)
450 return r;
451
452 // Check if the given IP address is inside the network
453 r = loc_network_match_address(*network, address);
454 if (r) {
455 DEBUG(db->ctx, "Searched address is not part of the network\n");
456
457 loc_network_unref(*network);
458 *network = NULL;
459 return 1;
460 }
461
462 // A network was found and the IP address matches
463 return 0;
464}
465
466// Returns the highest result available
467static int __loc_database_lookup_max(struct loc_database* db, const struct in6_addr* address,
468 struct loc_network** network, struct in6_addr* network_address,
f66f15e1 469 const struct loc_database_network_node_v0* node, unsigned int level) {
2a30e4de 470 // If the node is a leaf node, we end here
025ef489
MT
471 if (__loc_database_node_is_leaf(node))
472 return __loc_database_lookup_handle_leaf(db, address, network, network_address, node);
2a30e4de 473
025ef489 474 int r;
2a30e4de
MT
475 off_t node_index;
476
477 // Try to go down the ones path first
478 if (node->one) {
479 node_index = be32toh(node->one);
480 in6_addr_set_bit(network_address, level, 1);
481
482 // Check boundaries
483 if (node_index > 0 && (size_t)node_index <= db->network_nodes_count) {
484 r = __loc_database_lookup_max(db, address, network, network_address,
485 db->network_nodes_v0 + node_index, level + 1);
486
487 // Abort when match was found or error
488 if (r <= 0)
489 return r;
490 }
491 }
492
493 // ... and if that fails, we try to go down one step on a zero
494 // branch and then try the ones again...
495 if (node->zero) {
496 node_index = be32toh(node->zero);
497 in6_addr_set_bit(network_address, level, 0);
498
499 // Check boundaries
500 if (node_index > 0 && (size_t)node_index <= db->network_nodes_count) {
501 r = __loc_database_lookup_max(db, address, network, network_address,
502 db->network_nodes_v0 + node_index, level + 1);
503
504 // Abort when match was found or error
505 if (r <= 0)
506 return r;
507 }
508 }
509
510 // End of path
511 return 1;
512}
513
514// Searches for an exact match along the path
515static int __loc_database_lookup(struct loc_database* db, const struct in6_addr* address,
516 struct loc_network** network, struct in6_addr* network_address,
f66f15e1 517 const struct loc_database_network_node_v0* node, unsigned int level) {
2a30e4de 518 // If the node is a leaf node, we end here
025ef489
MT
519 if (__loc_database_node_is_leaf(node))
520 return __loc_database_lookup_handle_leaf(db, address, network, network_address, node);
2a30e4de 521
025ef489 522 int r;
2a30e4de
MT
523 off_t node_index;
524
525 // Follow the path
526 int bit = in6_addr_get_bit(address, level);
527 in6_addr_set_bit(network_address, level, bit);
528
529 if (bit == 0)
530 node_index = be32toh(node->zero);
531 else
532 node_index = be32toh(node->one);
533
534 // If we point back to root, the path ends here
535 if (node_index == 0) {
536 DEBUG(db->ctx, "Tree ends here\n");
537 return 1;
538 }
539
540 // Check boundaries
541 if ((size_t)node_index >= db->network_nodes_count)
542 return -EINVAL;
543
544 // Move on to the next node
545 r = __loc_database_lookup(db, address, network, network_address,
546 db->network_nodes_v0 + node_index, level + 1);
547
548 // End here if a result was found
549 if (r == 0)
550 return r;
551
552 // Raise any errors
553 else if (r < 0)
554 return r;
555
556 DEBUG(db->ctx, "Could not find an exact match at %u\n", level);
557
558 // If nothing was found, we have to search for an inexact match
559 return __loc_database_lookup_max(db, address, network, network_address, node, level);
560}
561
562LOC_EXPORT int loc_database_lookup(struct loc_database* db,
563 struct in6_addr* address, struct loc_network** network) {
564 struct in6_addr network_address;
565 memset(&network_address, 0, sizeof(network_address));
566
567 *network = NULL;
568
569 // Save start time
570 clock_t start = clock();
571
572 int r = __loc_database_lookup(db, address, network, &network_address,
573 db->network_nodes_v0, 0);
574
575 clock_t end = clock();
576
577 // Log how fast this has been
578 DEBUG(db->ctx, "Executed network search in %.8fs\n",
579 (double)(end - start) / CLOCKS_PER_SEC);
580
581 return r;
582}
583
584LOC_EXPORT int loc_database_lookup_from_string(struct loc_database* db,
585 const char* string, struct loc_network** network) {
586 struct in6_addr address;
587
588 int r = loc_parse_address(db->ctx, string, &address);
589 if (r)
590 return r;
591
592 return loc_database_lookup(db, &address, network);
593}
7e13db74
MT
594
595// Enumerator
596
597LOC_EXPORT int loc_database_enumerator_new(struct loc_database_enumerator** enumerator, struct loc_database* db) {
598 struct loc_database_enumerator* e = calloc(1, sizeof(*e));
599 if (!e)
600 return -ENOMEM;
601
602 // Reference context
603 e->ctx = loc_ref(db->ctx);
604 e->db = loc_database_ref(db);
605 e->refcount = 1;
606
607 DEBUG(e->ctx, "Database enumerator object allocated at %p\n", e);
608
609 *enumerator = e;
610 return 0;
611}
612
613LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_ref(struct loc_database_enumerator* enumerator) {
614 enumerator->refcount++;
615
616 return enumerator;
617}
618
619static void loc_database_enumerator_free(struct loc_database_enumerator* enumerator) {
620 DEBUG(enumerator->ctx, "Releasing database enumerator %p\n", enumerator);
621
622 // Release all references
623 loc_database_unref(enumerator->db);
624 loc_unref(enumerator->ctx);
625
d3d8ede6
MT
626 if (enumerator->string)
627 free(enumerator->string);
628
7e13db74
MT
629 free(enumerator);
630}
631
632LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_unref(struct loc_database_enumerator* enumerator) {
633 if (!enumerator)
634 return NULL;
635
636 if (--enumerator->refcount > 0)
637 return enumerator;
638
639 loc_database_enumerator_free(enumerator);
640 return NULL;
641}
d3d8ede6
MT
642
643LOC_EXPORT int loc_database_enumerator_set_string(struct loc_database_enumerator* enumerator, const char* string) {
644 enumerator->string = strdup(string);
645
646 // Make the string lowercase
647 for (char *p = enumerator->string; *p; p++)
648 *p = tolower(*p);
649
650 return 0;
651}
652
653LOC_EXPORT struct loc_as* loc_database_enumerator_next_as(struct loc_database_enumerator* enumerator) {
654 struct loc_database* db = enumerator->db;
655 struct loc_as* as;
656
657 while (enumerator->as_index < db->as_count) {
658 // Fetch the next AS
659 int r = loc_database_fetch_as(db, &as, enumerator->as_index++);
660 if (r)
661 return NULL;
662
663 r = loc_as_match_string(as, enumerator->string);
664 if (r == 0) {
665 DEBUG(enumerator->ctx, "AS%d (%s) matches %s\n",
666 loc_as_get_number(as), loc_as_get_name(as), enumerator->string);
667
668 return as;
669 }
670
671 // No match
672 loc_as_unref(as);
673 }
674
675 // Reset the index
676 enumerator->as_index = 0;
677
678 // We have searched through all of them
679 return NULL;
680}