2 libloc - A library to determine the location of someone on the Internet
4 Copyright (C) 2017 IPFire Development Team <info@ipfire.org>
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.
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.
17 #include <arpa/inet.h>
21 #include <netinet/in.h>
28 #include <sys/types.h>
32 #include <loc/libloc.h>
34 #include <loc/database.h>
35 #include <loc/format.h>
36 #include <loc/network.h>
37 #include <loc/private.h>
38 #include <loc/stringpool.h>
50 // ASes in the database
51 struct loc_database_as_v0
* as_v0
;
55 struct loc_database_network_node_v0
* network_nodes_v0
;
56 size_t network_nodes_count
;
59 struct loc_database_network_v0
* networks_v0
;
60 size_t networks_count
;
62 struct loc_stringpool
* pool
;
65 #define MAX_STACK_DEPTH 256
67 struct loc_node_stack
{
69 int i
; // Is this node 0 or 1?
73 struct loc_database_enumerator
{
75 struct loc_database
* db
;
83 // Index of the AS we are looking at
84 unsigned int as_index
;
87 struct in6_addr network_address
;
88 struct loc_node_stack network_stack
[MAX_STACK_DEPTH
];
89 int network_stack_depth
;
90 unsigned int* networks_visited
;
93 static int loc_database_read_magic(struct loc_database
* db
, FILE* f
) {
94 struct loc_database_magic magic
;
97 size_t bytes_read
= fread(&magic
, 1, sizeof(magic
), f
);
99 // Check if we have been able to read enough data
100 if (bytes_read
< sizeof(magic
)) {
101 ERROR(db
->ctx
, "Could not read enough data to validate magic bytes\n");
102 DEBUG(db
->ctx
, "Read %zu bytes, but needed %zu\n", bytes_read
, sizeof(magic
));
106 // Compare magic bytes
107 if (memcmp(LOC_DATABASE_MAGIC
, magic
.magic
, strlen(LOC_DATABASE_MAGIC
)) == 0) {
108 DEBUG(db
->ctx
, "Magic value matches\n");
111 db
->version
= be16toh(magic
.version
);
112 DEBUG(db
->ctx
, "Database version is %u\n", db
->version
);
117 ERROR(db
->ctx
, "Database format is not compatible\n");
123 static int loc_database_read_as_section_v0(struct loc_database
* db
,
124 FILE* f
, const struct loc_database_header_v0
* header
) {
125 off_t as_offset
= be32toh(header
->as_offset
);
126 size_t as_length
= be32toh(header
->as_length
);
128 DEBUG(db
->ctx
, "Reading AS section from %jd (%zu bytes)\n", as_offset
, as_length
);
131 db
->as_v0
= mmap(NULL
, as_length
, PROT_READ
,
132 MAP_SHARED
, fileno(f
), as_offset
);
134 if (db
->as_v0
== MAP_FAILED
)
138 db
->as_count
= as_length
/ sizeof(*db
->as_v0
);
140 INFO(db
->ctx
, "Read %zu ASes from the database\n", db
->as_count
);
145 static int loc_database_read_network_nodes_section_v0(struct loc_database
* db
,
146 FILE* f
, const struct loc_database_header_v0
* header
) {
147 off_t network_nodes_offset
= be32toh(header
->network_tree_offset
);
148 size_t network_nodes_length
= be32toh(header
->network_tree_length
);
150 DEBUG(db
->ctx
, "Reading network nodes section from %jd (%zu bytes)\n",
151 network_nodes_offset
, network_nodes_length
);
153 if (network_nodes_length
> 0) {
154 db
->network_nodes_v0
= mmap(NULL
, network_nodes_length
, PROT_READ
,
155 MAP_SHARED
, fileno(f
), network_nodes_offset
);
157 if (db
->network_nodes_v0
== MAP_FAILED
)
161 db
->network_nodes_count
= network_nodes_length
/ sizeof(*db
->network_nodes_v0
);
163 INFO(db
->ctx
, "Read %zu network nodes from the database\n", db
->network_nodes_count
);
168 static int loc_database_read_networks_section_v0(struct loc_database
* db
,
169 FILE* f
, const struct loc_database_header_v0
* header
) {
170 off_t networks_offset
= be32toh(header
->network_data_offset
);
171 size_t networks_length
= be32toh(header
->network_data_length
);
173 DEBUG(db
->ctx
, "Reading networks section from %jd (%zu bytes)\n",
174 networks_offset
, networks_length
);
176 if (networks_length
> 0) {
177 db
->networks_v0
= mmap(NULL
, networks_length
, PROT_READ
,
178 MAP_SHARED
, fileno(f
), networks_offset
);
180 if (db
->networks_v0
== MAP_FAILED
)
184 db
->networks_count
= networks_length
/ sizeof(*db
->networks_v0
);
186 INFO(db
->ctx
, "Read %zu networks from the database\n", db
->networks_count
);
191 static int loc_database_read_header_v0(struct loc_database
* db
, FILE* f
) {
192 struct loc_database_header_v0 header
;
195 size_t size
= fread(&header
, 1, sizeof(header
), f
);
197 if (size
< sizeof(header
)) {
198 ERROR(db
->ctx
, "Could not read enough data for header\n");
203 db
->created_at
= be64toh(header
.created_at
);
204 db
->vendor
= be32toh(header
.vendor
);
205 db
->description
= be32toh(header
.description
);
206 db
->license
= be32toh(header
.license
);
209 off_t pool_offset
= be32toh(header
.pool_offset
);
210 size_t pool_length
= be32toh(header
.pool_length
);
212 int r
= loc_stringpool_open(db
->ctx
, &db
->pool
,
213 f
, pool_length
, pool_offset
);
218 r
= loc_database_read_as_section_v0(db
, f
, &header
);
223 r
= loc_database_read_network_nodes_section_v0(db
, f
, &header
);
228 r
= loc_database_read_networks_section_v0(db
, f
, &header
);
235 static int loc_database_read_header(struct loc_database
* db
, FILE* f
) {
236 switch (db
->version
) {
238 return loc_database_read_header_v0(db
, f
);
241 ERROR(db
->ctx
, "Incompatible database version: %u\n", db
->version
);
246 static int loc_database_read(struct loc_database
* db
, FILE* f
) {
247 clock_t start
= clock();
250 int r
= loc_database_read_magic(db
, f
);
255 r
= loc_database_read_header(db
, f
);
259 clock_t end
= clock();
261 INFO(db
->ctx
, "Opened database in %.8fs\n",
262 (double)(end
- start
) / CLOCKS_PER_SEC
);
267 LOC_EXPORT
int loc_database_new(struct loc_ctx
* ctx
, struct loc_database
** database
, FILE* f
) {
268 // Fail on invalid file handle
272 struct loc_database
* db
= calloc(1, sizeof(*db
));
277 db
->ctx
= loc_ref(ctx
);
280 DEBUG(db
->ctx
, "Database object allocated at %p\n", db
);
282 int r
= loc_database_read(db
, f
);
284 loc_database_unref(db
);
293 LOC_EXPORT
struct loc_database
* loc_database_ref(struct loc_database
* db
) {
299 static void loc_database_free(struct loc_database
* db
) {
302 DEBUG(db
->ctx
, "Releasing database %p\n", db
);
306 r
= munmap(db
->as_v0
, db
->as_count
* sizeof(*db
->as_v0
));
308 ERROR(db
->ctx
, "Could not unmap AS section: %s\n", strerror(errno
));
311 // Remove mapped network sections
312 if (db
->networks_v0
) {
313 r
= munmap(db
->networks_v0
, db
->networks_count
* sizeof(*db
->networks_v0
));
315 ERROR(db
->ctx
, "Could not unmap networks section: %s\n", strerror(errno
));
318 // Remove mapped network nodes section
319 if (db
->network_nodes_v0
) {
320 r
= munmap(db
->network_nodes_v0
, db
->network_nodes_count
* sizeof(*db
->network_nodes_v0
));
322 ERROR(db
->ctx
, "Could not unmap network nodes section: %s\n", strerror(errno
));
325 loc_stringpool_unref(db
->pool
);
331 LOC_EXPORT
struct loc_database
* loc_database_unref(struct loc_database
* db
) {
332 if (--db
->refcount
> 0)
335 loc_database_free(db
);
339 LOC_EXPORT
time_t loc_database_created_at(struct loc_database
* db
) {
340 return db
->created_at
;
343 LOC_EXPORT
const char* loc_database_get_vendor(struct loc_database
* db
) {
344 return loc_stringpool_get(db
->pool
, db
->vendor
);
347 LOC_EXPORT
const char* loc_database_get_description(struct loc_database
* db
) {
348 return loc_stringpool_get(db
->pool
, db
->description
);
351 LOC_EXPORT
const char* loc_database_get_license(struct loc_database
* db
) {
352 return loc_stringpool_get(db
->pool
, db
->license
);
355 LOC_EXPORT
size_t loc_database_count_as(struct loc_database
* db
) {
359 // Returns the AS at position pos
360 static int loc_database_fetch_as(struct loc_database
* db
, struct loc_as
** as
, off_t pos
) {
361 if ((size_t)pos
>= db
->as_count
)
364 DEBUG(db
->ctx
, "Fetching AS at position %jd\n", pos
);
367 switch (db
->version
) {
369 r
= loc_as_new_from_database_v0(db
->ctx
, db
->pool
, as
, db
->as_v0
+ pos
);
377 DEBUG(db
->ctx
, "Got AS%u\n", loc_as_get_number(*as
));
383 // Performs a binary search to find the AS in the list
384 LOC_EXPORT
int loc_database_get_as(struct loc_database
* db
, struct loc_as
** as
, uint32_t number
) {
386 off_t hi
= db
->as_count
- 1;
389 clock_t start
= clock();
392 off_t i
= (lo
+ hi
) / 2;
394 // Fetch AS in the middle between lo and hi
395 int r
= loc_database_fetch_as(db
, as
, i
);
399 // Check if this is a match
400 uint32_t as_number
= loc_as_get_number(*as
);
401 if (as_number
== number
) {
402 clock_t end
= clock();
404 // Log how fast this has been
405 DEBUG(db
->ctx
, "Found AS%u in %.8fs\n", as_number
,
406 (double)(end
- start
) / CLOCKS_PER_SEC
);
411 // If it wasn't, we release the AS and
412 // adjust our search pointers
415 if (as_number
< number
) {
427 // Returns the network at position pos
428 static int loc_database_fetch_network(struct loc_database
* db
, struct loc_network
** network
,
429 struct in6_addr
* address
, unsigned int prefix
, off_t pos
) {
430 if ((size_t)pos
>= db
->networks_count
)
433 DEBUG(db
->ctx
, "Fetching network at position %jd\n", pos
);
436 switch (db
->version
) {
438 r
= loc_network_new_from_database_v0(db
->ctx
, network
,
439 address
, prefix
, db
->networks_v0
+ pos
);
447 char* string
= loc_network_str(*network
);
448 DEBUG(db
->ctx
, "Got network %s\n", string
);
455 static int __loc_database_node_is_leaf(const struct loc_database_network_node_v0
* node
) {
456 return (node
->network
!= htobe32(0xffffffff));
459 static int __loc_database_lookup_handle_leaf(struct loc_database
* db
, const struct in6_addr
* address
,
460 struct loc_network
** network
, struct in6_addr
* network_address
, unsigned int prefix
,
461 const struct loc_database_network_node_v0
* node
) {
462 off_t network_index
= be32toh(node
->network
);
464 DEBUG(db
->ctx
, "Handling leaf node at %jd (%jd)\n", node
- db
->network_nodes_v0
, network_index
);
467 int r
= loc_database_fetch_network(db
, network
,
468 network_address
, prefix
, network_index
);
470 ERROR(db
->ctx
, "Could not fetch network %jd from database\n", network_index
);
474 // Check if the given IP address is inside the network
475 r
= loc_network_match_address(*network
, address
);
477 DEBUG(db
->ctx
, "Searched address is not part of the network\n");
479 loc_network_unref(*network
);
484 // A network was found and the IP address matches
488 // Searches for an exact match along the path
489 static int __loc_database_lookup(struct loc_database
* db
, const struct in6_addr
* address
,
490 struct loc_network
** network
, struct in6_addr
* network_address
,
491 const struct loc_database_network_node_v0
* node
, unsigned int level
) {
496 int bit
= in6_addr_get_bit(address
, level
);
497 in6_addr_set_bit(network_address
, level
, bit
);
500 node_index
= be32toh(node
->zero
);
502 node_index
= be32toh(node
->one
);
504 // If the node index is zero, the tree ends here
505 // and we cannot descend any further
506 if (node_index
> 0) {
508 if ((size_t)node_index
>= db
->network_nodes_count
)
511 // Move on to the next node
512 r
= __loc_database_lookup(db
, address
, network
, network_address
,
513 db
->network_nodes_v0
+ node_index
, level
+ 1);
515 // End here if a result was found
523 DEBUG(db
->ctx
, "No match found below level %u\n", level
);
525 DEBUG(db
->ctx
, "Tree ended at level %u\n", level
);
528 // If this node has a leaf, we will check if it matches
529 if (__loc_database_node_is_leaf(node
)) {
530 r
= __loc_database_lookup_handle_leaf(db
, address
, network
, network_address
, level
, node
);
538 LOC_EXPORT
int loc_database_lookup(struct loc_database
* db
,
539 struct in6_addr
* address
, struct loc_network
** network
) {
540 struct in6_addr network_address
;
541 memset(&network_address
, 0, sizeof(network_address
));
546 clock_t start
= clock();
548 int r
= __loc_database_lookup(db
, address
, network
, &network_address
,
549 db
->network_nodes_v0
, 0);
551 clock_t end
= clock();
553 // Log how fast this has been
554 DEBUG(db
->ctx
, "Executed network search in %.8fs\n",
555 (double)(end
- start
) / CLOCKS_PER_SEC
);
560 LOC_EXPORT
int loc_database_lookup_from_string(struct loc_database
* db
,
561 const char* string
, struct loc_network
** network
) {
562 struct in6_addr address
;
564 int r
= loc_parse_address(db
->ctx
, string
, &address
);
568 return loc_database_lookup(db
, &address
, network
);
573 LOC_EXPORT
int loc_database_enumerator_new(struct loc_database_enumerator
** enumerator
, struct loc_database
* db
) {
574 struct loc_database_enumerator
* e
= calloc(1, sizeof(*e
));
579 e
->ctx
= loc_ref(db
->ctx
);
580 e
->db
= loc_database_ref(db
);
583 // Initialise graph search
584 //e->network_stack[++e->network_stack_depth] = 0;
585 e
->network_stack_depth
= 1;
586 e
->networks_visited
= calloc(db
->network_nodes_count
, sizeof(*e
->networks_visited
));
588 DEBUG(e
->ctx
, "Database enumerator object allocated at %p\n", e
);
594 LOC_EXPORT
struct loc_database_enumerator
* loc_database_enumerator_ref(struct loc_database_enumerator
* enumerator
) {
595 enumerator
->refcount
++;
600 static void loc_database_enumerator_free(struct loc_database_enumerator
* enumerator
) {
601 DEBUG(enumerator
->ctx
, "Releasing database enumerator %p\n", enumerator
);
603 // Release all references
604 loc_database_unref(enumerator
->db
);
605 loc_unref(enumerator
->ctx
);
607 if (enumerator
->string
)
608 free(enumerator
->string
);
610 // Free network search
611 free(enumerator
->networks_visited
);
616 LOC_EXPORT
struct loc_database_enumerator
* loc_database_enumerator_unref(struct loc_database_enumerator
* enumerator
) {
620 if (--enumerator
->refcount
> 0)
623 loc_database_enumerator_free(enumerator
);
627 LOC_EXPORT
int loc_database_enumerator_set_string(struct loc_database_enumerator
* enumerator
, const char* string
) {
628 enumerator
->string
= strdup(string
);
630 // Make the string lowercase
631 for (char *p
= enumerator
->string
; *p
; p
++)
637 LOC_EXPORT
int loc_database_enumerator_set_country_code(struct loc_database_enumerator
* enumerator
, const char* country_code
) {
638 // Set empty country code
639 if (!country_code
|| !*country_code
) {
640 *enumerator
->country_code
= '\0';
644 // Country codes must be two characters
645 if (strlen(country_code
) != 2)
648 for (unsigned int i
= 0; i
< 3; i
++) {
649 enumerator
->country_code
[i
] = country_code
[i
];
655 LOC_EXPORT
int loc_database_enumerator_set_asn(
656 struct loc_database_enumerator
* enumerator
, unsigned int asn
) {
657 enumerator
->asn
= asn
;
662 LOC_EXPORT
struct loc_as
* loc_database_enumerator_next_as(struct loc_database_enumerator
* enumerator
) {
663 struct loc_database
* db
= enumerator
->db
;
666 while (enumerator
->as_index
< db
->as_count
) {
668 int r
= loc_database_fetch_as(db
, &as
, enumerator
->as_index
++);
672 r
= loc_as_match_string(as
, enumerator
->string
);
674 DEBUG(enumerator
->ctx
, "AS%d (%s) matches %s\n",
675 loc_as_get_number(as
), loc_as_get_name(as
), enumerator
->string
);
685 enumerator
->as_index
= 0;
687 // We have searched through all of them
691 static int loc_database_enumerator_stack_push_node(
692 struct loc_database_enumerator
* e
, off_t offset
, int i
, int depth
) {
693 // Do not add empty nodes
697 // Check if there is any space left on the stack
698 if (e
->network_stack_depth
>= MAX_STACK_DEPTH
) {
699 ERROR(e
->ctx
, "Maximum stack size reached: %d\n", e
->network_stack_depth
);
703 // Increase stack size
704 int s
= ++e
->network_stack_depth
;
706 DEBUG(e
->ctx
, "Added node %jd to stack (%d)\n", offset
, depth
);
708 e
->network_stack
[s
].offset
= offset
;
709 e
->network_stack
[s
].i
= i
;
710 e
->network_stack
[s
].depth
= depth
;
715 static int loc_database_enumerator_network_depth_first_search(
716 struct loc_database_enumerator
* e
, struct loc_network
** network
) {
721 DEBUG(e
->ctx
, "Called with a stack of %u nodes\n", e
->network_stack_depth
);
724 while (e
->network_stack_depth
> 0) {
725 DEBUG(e
->ctx
, "Stack depth: %u\n", e
->network_stack_depth
);
727 // Get object from top of the stack
728 struct loc_node_stack
* node
= &e
->network_stack
[e
->network_stack_depth
];
730 // Remove the node from the stack if we have already visited it
731 if (e
->networks_visited
[node
->offset
]) {
732 e
->network_stack_depth
--;
736 // Mark the bits on the path correctly
737 in6_addr_set_bit(&e
->network_address
,
738 (node
->depth
> 0) ? node
->depth
- 1 : 0, node
->i
);
740 DEBUG(e
->ctx
, "Looking at node %jd\n", node
->offset
);
741 e
->networks_visited
[node
->offset
]++;
743 // Pop node from top of the stack
744 struct loc_database_network_node_v0
* n
=
745 e
->db
->network_nodes_v0
+ node
->offset
;
747 // Add edges to stack
748 r
= loc_database_enumerator_stack_push_node(e
,
749 be32toh(n
->one
), 1, node
->depth
+ 1);
754 r
= loc_database_enumerator_stack_push_node(e
,
755 be32toh(n
->zero
), 0, node
->depth
+ 1);
760 // Check if this node is a leaf and has a network object
761 if (__loc_database_node_is_leaf(n
)) {
762 off_t network_index
= be32toh(n
->network
);
764 DEBUG(e
->ctx
, "Node has a network at %jd\n", network_index
);
766 // Fetch the network object
767 r
= loc_database_fetch_network(e
->db
, network
,
768 &e
->network_address
, node
->depth
, network_index
);
770 // Break on any errors
774 // Check if we are interested in this network
776 // Skip if the country code does not match
777 if (e
->country_code
&& !loc_network_match_country_code(*network
, e
->country_code
)) {
778 loc_network_unref(*network
);
782 // Skip if the ASN does not match
783 if (e
->asn
&& !loc_network_match_asn(*network
, e
->asn
)) {
784 loc_network_unref(*network
);
792 // Reached the end of the search
794 // Mark all nodes as non-visited
795 for (unsigned int i
= 0; i
< e
->db
->network_nodes_count
; i
++)
796 e
->networks_visited
[i
] = 0;
801 LOC_EXPORT
struct loc_network
* loc_database_enumerator_next_network(
802 struct loc_database_enumerator
* enumerator
) {
803 struct loc_network
* network
= NULL
;
805 int r
= loc_database_enumerator_network_depth_first_search(enumerator
, &network
);