network: Fix checking upper bound when matching IP addresses
[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
472// Returns the highest result available
473static int __loc_database_lookup_max(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
39a55353
MT
479 // If the node is a leaf node, we end here
480 if (__loc_database_node_is_leaf(node)) {
481 r = __loc_database_lookup_handle_leaf(db, address, network, network_address, level, node);
482 if (r <= 0)
483 return r;
484 }
485
2a30e4de
MT
486 // Try to go down the ones path first
487 if (node->one) {
488 node_index = be32toh(node->one);
489 in6_addr_set_bit(network_address, level, 1);
490
491 // Check boundaries
492 if (node_index > 0 && (size_t)node_index <= db->network_nodes_count) {
493 r = __loc_database_lookup_max(db, address, network, network_address,
494 db->network_nodes_v0 + node_index, level + 1);
495
496 // Abort when match was found or error
497 if (r <= 0)
498 return r;
499 }
500 }
501
502 // ... and if that fails, we try to go down one step on a zero
503 // branch and then try the ones again...
504 if (node->zero) {
505 node_index = be32toh(node->zero);
506 in6_addr_set_bit(network_address, level, 0);
507
508 // Check boundaries
509 if (node_index > 0 && (size_t)node_index <= db->network_nodes_count) {
510 r = __loc_database_lookup_max(db, address, network, network_address,
511 db->network_nodes_v0 + node_index, level + 1);
512
513 // Abort when match was found or error
514 if (r <= 0)
515 return r;
516 }
517 }
518
519 // End of path
520 return 1;
521}
522
523// Searches for an exact match along the path
524static int __loc_database_lookup(struct loc_database* db, const struct in6_addr* address,
525 struct loc_network** network, struct in6_addr* network_address,
f66f15e1 526 const struct loc_database_network_node_v0* node, unsigned int level) {
025ef489 527 int r;
2a30e4de
MT
528 off_t node_index;
529
39a55353
MT
530 // If the node is a leaf node, we end here
531 if (__loc_database_node_is_leaf(node)) {
532 r = __loc_database_lookup_handle_leaf(db, address, network, network_address, level, node);
533 if (r <= 0)
534 return r;
535 }
536
2a30e4de
MT
537 // Follow the path
538 int bit = in6_addr_get_bit(address, level);
539 in6_addr_set_bit(network_address, level, bit);
540
541 if (bit == 0)
542 node_index = be32toh(node->zero);
543 else
544 node_index = be32toh(node->one);
545
546 // If we point back to root, the path ends here
547 if (node_index == 0) {
548 DEBUG(db->ctx, "Tree ends here\n");
549 return 1;
550 }
551
552 // Check boundaries
553 if ((size_t)node_index >= db->network_nodes_count)
554 return -EINVAL;
555
556 // Move on to the next node
557 r = __loc_database_lookup(db, address, network, network_address,
558 db->network_nodes_v0 + node_index, level + 1);
559
560 // End here if a result was found
561 if (r == 0)
562 return r;
563
564 // Raise any errors
565 else if (r < 0)
566 return r;
567
568 DEBUG(db->ctx, "Could not find an exact match at %u\n", level);
569
570 // If nothing was found, we have to search for an inexact match
571 return __loc_database_lookup_max(db, address, network, network_address, node, level);
572}
573
574LOC_EXPORT int loc_database_lookup(struct loc_database* db,
575 struct in6_addr* address, struct loc_network** network) {
576 struct in6_addr network_address;
577 memset(&network_address, 0, sizeof(network_address));
578
579 *network = NULL;
580
581 // Save start time
582 clock_t start = clock();
583
584 int r = __loc_database_lookup(db, address, network, &network_address,
585 db->network_nodes_v0, 0);
586
587 clock_t end = clock();
588
589 // Log how fast this has been
590 DEBUG(db->ctx, "Executed network search in %.8fs\n",
591 (double)(end - start) / CLOCKS_PER_SEC);
592
593 return r;
594}
595
596LOC_EXPORT int loc_database_lookup_from_string(struct loc_database* db,
597 const char* string, struct loc_network** network) {
598 struct in6_addr address;
599
600 int r = loc_parse_address(db->ctx, string, &address);
601 if (r)
602 return r;
603
604 return loc_database_lookup(db, &address, network);
605}
7e13db74
MT
606
607// Enumerator
608
609LOC_EXPORT int loc_database_enumerator_new(struct loc_database_enumerator** enumerator, struct loc_database* db) {
610 struct loc_database_enumerator* e = calloc(1, sizeof(*e));
611 if (!e)
612 return -ENOMEM;
613
614 // Reference context
615 e->ctx = loc_ref(db->ctx);
616 e->db = loc_database_ref(db);
617 e->refcount = 1;
618
619 DEBUG(e->ctx, "Database enumerator object allocated at %p\n", e);
620
621 *enumerator = e;
622 return 0;
623}
624
625LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_ref(struct loc_database_enumerator* enumerator) {
626 enumerator->refcount++;
627
628 return enumerator;
629}
630
631static void loc_database_enumerator_free(struct loc_database_enumerator* enumerator) {
632 DEBUG(enumerator->ctx, "Releasing database enumerator %p\n", enumerator);
633
634 // Release all references
635 loc_database_unref(enumerator->db);
636 loc_unref(enumerator->ctx);
637
d3d8ede6
MT
638 if (enumerator->string)
639 free(enumerator->string);
640
7e13db74
MT
641 free(enumerator);
642}
643
644LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_unref(struct loc_database_enumerator* enumerator) {
645 if (!enumerator)
646 return NULL;
647
648 if (--enumerator->refcount > 0)
649 return enumerator;
650
651 loc_database_enumerator_free(enumerator);
652 return NULL;
653}
d3d8ede6
MT
654
655LOC_EXPORT int loc_database_enumerator_set_string(struct loc_database_enumerator* enumerator, const char* string) {
656 enumerator->string = strdup(string);
657
658 // Make the string lowercase
659 for (char *p = enumerator->string; *p; p++)
660 *p = tolower(*p);
661
662 return 0;
663}
664
665LOC_EXPORT struct loc_as* loc_database_enumerator_next_as(struct loc_database_enumerator* enumerator) {
666 struct loc_database* db = enumerator->db;
667 struct loc_as* as;
668
669 while (enumerator->as_index < db->as_count) {
670 // Fetch the next AS
671 int r = loc_database_fetch_as(db, &as, enumerator->as_index++);
672 if (r)
673 return NULL;
674
675 r = loc_as_match_string(as, enumerator->string);
676 if (r == 0) {
677 DEBUG(enumerator->ctx, "AS%d (%s) matches %s\n",
678 loc_as_get_number(as), loc_as_get_name(as), enumerator->string);
679
680 return as;
681 }
682
683 // No match
684 loc_as_unref(as);
685 }
686
687 // Reset the index
688 enumerator->as_index = 0;
689
690 // We have searched through all of them
691 return NULL;
692}