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>
20 #include <netinet/in.h>
27 #include <sys/types.h>
35 #include <openssl/err.h>
36 #include <openssl/evp.h>
37 #include <openssl/pem.h>
39 #include <loc/libloc.h>
41 #include <loc/as-list.h>
42 #include <loc/compat.h>
43 #include <loc/country.h>
44 #include <loc/country-list.h>
45 #include <loc/database.h>
46 #include <loc/format.h>
47 #include <loc/network.h>
48 #include <loc/private.h>
49 #include <loc/stringpool.h>
57 enum loc_database_version version
;
65 size_t signature1_length
;
67 size_t signature2_length
;
69 // ASes in the database
70 struct loc_database_as_v1
* as_v1
;
74 struct loc_database_network_node_v1
* network_nodes_v1
;
75 size_t network_nodes_count
;
78 struct loc_database_network_v1
* networks_v1
;
79 size_t networks_count
;
82 struct loc_database_country_v1
* countries_v1
;
83 size_t countries_count
;
85 struct loc_stringpool
* pool
;
88 #define MAX_STACK_DEPTH 256
90 struct loc_node_stack
{
92 int i
; // Is this node 0 or 1?
96 struct loc_database_enumerator
{
98 struct loc_database
* db
;
99 enum loc_database_enumerator_mode mode
;
104 struct loc_country_list
* countries
;
105 struct loc_as_list
* asns
;
106 enum loc_network_flags flags
;
112 // Index of the AS we are looking at
113 unsigned int as_index
;
115 // Index of the country we are looking at
116 unsigned int country_index
;
119 struct in6_addr network_address
;
120 struct loc_node_stack network_stack
[MAX_STACK_DEPTH
];
121 int network_stack_depth
;
122 unsigned int* networks_visited
;
125 struct loc_network_list
* stack
;
128 static int loc_database_read_magic(struct loc_database
* db
) {
129 struct loc_database_magic magic
;
132 size_t bytes_read
= fread(&magic
, 1, sizeof(magic
), db
->f
);
134 // Check if we have been able to read enough data
135 if (bytes_read
< sizeof(magic
)) {
136 ERROR(db
->ctx
, "Could not read enough data to validate magic bytes\n");
137 DEBUG(db
->ctx
, "Read %zu bytes, but needed %zu\n", bytes_read
, sizeof(magic
));
141 // Compare magic bytes
142 if (memcmp(LOC_DATABASE_MAGIC
, magic
.magic
, strlen(LOC_DATABASE_MAGIC
)) == 0) {
143 DEBUG(db
->ctx
, "Magic value matches\n");
146 db
->version
= magic
.version
;
151 ERROR(db
->ctx
, "Unrecognized file type\n");
157 static int loc_database_read_as_section_v1(struct loc_database
* db
,
158 const struct loc_database_header_v1
* header
) {
159 off_t as_offset
= be32toh(header
->as_offset
);
160 size_t as_length
= be32toh(header
->as_length
);
162 DEBUG(db
->ctx
, "Reading AS section from %jd (%zu bytes)\n", (intmax_t)as_offset
, as_length
);
165 db
->as_v1
= mmap(NULL
, as_length
, PROT_READ
,
166 MAP_SHARED
, fileno(db
->f
), as_offset
);
168 if (db
->as_v1
== MAP_FAILED
)
172 db
->as_count
= as_length
/ sizeof(*db
->as_v1
);
174 INFO(db
->ctx
, "Read %zu ASes from the database\n", db
->as_count
);
179 static int loc_database_read_network_nodes_section_v1(struct loc_database
* db
,
180 const struct loc_database_header_v1
* header
) {
181 off_t network_nodes_offset
= be32toh(header
->network_tree_offset
);
182 size_t network_nodes_length
= be32toh(header
->network_tree_length
);
184 DEBUG(db
->ctx
, "Reading network nodes section from %jd (%zu bytes)\n",
185 (intmax_t)network_nodes_offset
, network_nodes_length
);
187 if (network_nodes_length
> 0) {
188 db
->network_nodes_v1
= mmap(NULL
, network_nodes_length
, PROT_READ
,
189 MAP_SHARED
, fileno(db
->f
), network_nodes_offset
);
191 if (db
->network_nodes_v1
== MAP_FAILED
)
195 db
->network_nodes_count
= network_nodes_length
/ sizeof(*db
->network_nodes_v1
);
197 INFO(db
->ctx
, "Read %zu network nodes from the database\n", db
->network_nodes_count
);
202 static int loc_database_read_networks_section_v1(struct loc_database
* db
,
203 const struct loc_database_header_v1
* header
) {
204 off_t networks_offset
= be32toh(header
->network_data_offset
);
205 size_t networks_length
= be32toh(header
->network_data_length
);
207 DEBUG(db
->ctx
, "Reading networks section from %jd (%zu bytes)\n",
208 (intmax_t)networks_offset
, networks_length
);
210 if (networks_length
> 0) {
211 db
->networks_v1
= mmap(NULL
, networks_length
, PROT_READ
,
212 MAP_SHARED
, fileno(db
->f
), networks_offset
);
214 if (db
->networks_v1
== MAP_FAILED
)
218 db
->networks_count
= networks_length
/ sizeof(*db
->networks_v1
);
220 INFO(db
->ctx
, "Read %zu networks from the database\n", db
->networks_count
);
225 static int loc_database_read_countries_section_v1(struct loc_database
* db
,
226 const struct loc_database_header_v1
* header
) {
227 off_t countries_offset
= be32toh(header
->countries_offset
);
228 size_t countries_length
= be32toh(header
->countries_length
);
230 DEBUG(db
->ctx
, "Reading countries section from %jd (%zu bytes)\n",
231 (intmax_t)countries_offset
, countries_length
);
233 if (countries_length
> 0) {
234 db
->countries_v1
= mmap(NULL
, countries_length
, PROT_READ
,
235 MAP_SHARED
, fileno(db
->f
), countries_offset
);
237 if (db
->countries_v1
== MAP_FAILED
)
241 db
->countries_count
= countries_length
/ sizeof(*db
->countries_v1
);
243 INFO(db
->ctx
, "Read %zu countries from the database\n",
244 db
->countries_count
);
249 static int loc_database_read_signature(struct loc_database
* db
,
250 char** dst
, char* src
, size_t length
) {
251 // Check for a plausible signature length
252 if (length
> LOC_SIGNATURE_MAX_LENGTH
) {
253 ERROR(db
->ctx
, "Signature too long: %ld\n", length
);
257 DEBUG(db
->ctx
, "Reading signature of %ld bytes\n", length
);
260 *dst
= malloc(length
);
265 memcpy(*dst
, src
, length
);
270 static int loc_database_read_header_v1(struct loc_database
* db
) {
271 struct loc_database_header_v1 header
;
275 size_t size
= fread(&header
, 1, sizeof(header
), db
->f
);
277 if (size
< sizeof(header
)) {
278 ERROR(db
->ctx
, "Could not read enough data for header\n");
283 db
->created_at
= be64toh(header
.created_at
);
284 db
->vendor
= be32toh(header
.vendor
);
285 db
->description
= be32toh(header
.description
);
286 db
->license
= be32toh(header
.license
);
288 db
->signature1_length
= be16toh(header
.signature1_length
);
289 db
->signature2_length
= be16toh(header
.signature2_length
);
292 if (db
->signature1_length
) {
293 r
= loc_database_read_signature(db
, &db
->signature1
,
294 header
.signature1
, db
->signature1_length
);
299 if (db
->signature2_length
) {
300 r
= loc_database_read_signature(db
, &db
->signature2
,
301 header
.signature2
, db
->signature2_length
);
307 off_t pool_offset
= be32toh(header
.pool_offset
);
308 size_t pool_length
= be32toh(header
.pool_length
);
310 r
= loc_stringpool_open(db
->ctx
, &db
->pool
,
311 db
->f
, pool_length
, pool_offset
);
316 r
= loc_database_read_as_section_v1(db
, &header
);
321 r
= loc_database_read_network_nodes_section_v1(db
, &header
);
326 r
= loc_database_read_networks_section_v1(db
, &header
);
331 r
= loc_database_read_countries_section_v1(db
, &header
);
338 static int loc_database_read_header(struct loc_database
* db
) {
339 DEBUG(db
->ctx
, "Database version is %u\n", db
->version
);
341 switch (db
->version
) {
342 case LOC_DATABASE_VERSION_1
:
343 return loc_database_read_header_v1(db
);
346 ERROR(db
->ctx
, "Incompatible database version: %u\n", db
->version
);
351 static int loc_database_read(struct loc_database
* db
, FILE* f
) {
352 clock_t start
= clock();
356 // Clone file descriptor
359 ERROR(db
->ctx
, "Could not duplicate file descriptor\n");
363 // Reopen the file so that we can keep our own file handle
364 db
->f
= fdopen(fd
, "r");
366 ERROR(db
->ctx
, "Could not re-open database file\n");
370 // Rewind to the start of the file
374 int r
= loc_database_read_magic(db
);
379 r
= loc_database_read_header(db
);
383 clock_t end
= clock();
385 INFO(db
->ctx
, "Opened database in %.4fms\n",
386 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
391 LOC_EXPORT
int loc_database_new(struct loc_ctx
* ctx
, struct loc_database
** database
, FILE* f
) {
392 // Fail on invalid file handle
396 struct loc_database
* db
= calloc(1, sizeof(*db
));
401 db
->ctx
= loc_ref(ctx
);
404 DEBUG(db
->ctx
, "Database object allocated at %p\n", db
);
406 int r
= loc_database_read(db
, f
);
408 loc_database_unref(db
);
417 LOC_EXPORT
struct loc_database
* loc_database_ref(struct loc_database
* db
) {
423 static void loc_database_free(struct loc_database
* db
) {
426 DEBUG(db
->ctx
, "Releasing database %p\n", db
);
430 r
= munmap(db
->as_v1
, db
->as_count
* sizeof(*db
->as_v1
));
432 ERROR(db
->ctx
, "Could not unmap AS section: %s\n", strerror(errno
));
435 // Remove mapped network sections
436 if (db
->networks_v1
) {
437 r
= munmap(db
->networks_v1
, db
->networks_count
* sizeof(*db
->networks_v1
));
439 ERROR(db
->ctx
, "Could not unmap networks section: %s\n", strerror(errno
));
442 // Remove mapped network nodes section
443 if (db
->network_nodes_v1
) {
444 r
= munmap(db
->network_nodes_v1
, db
->network_nodes_count
* sizeof(*db
->network_nodes_v1
));
446 ERROR(db
->ctx
, "Could not unmap network nodes section: %s\n", strerror(errno
));
450 loc_stringpool_unref(db
->pool
);
454 free(db
->signature1
);
456 free(db
->signature2
);
458 // Close database file
466 LOC_EXPORT
struct loc_database
* loc_database_unref(struct loc_database
* db
) {
467 if (--db
->refcount
> 0)
470 loc_database_free(db
);
474 LOC_EXPORT
int loc_database_verify(struct loc_database
* db
, FILE* f
) {
475 // Cannot do this when no signature is available
476 if (!db
->signature1
&& !db
->signature2
) {
477 DEBUG(db
->ctx
, "No signature available to verify\n");
481 // Start the stopwatch
482 clock_t start
= clock();
485 EVP_PKEY
* pkey
= PEM_read_PUBKEY(f
, NULL
, NULL
, NULL
);
487 char* error
= ERR_error_string(ERR_get_error(), NULL
);
488 ERROR(db
->ctx
, "Could not parse public key: %s\n", error
);
495 EVP_MD_CTX
* mdctx
= EVP_MD_CTX_new();
497 // Initialise hash function
498 r
= EVP_DigestVerifyInit(mdctx
, NULL
, NULL
, NULL
, pkey
);
500 ERROR(db
->ctx
, "Error initializing signature validation: %s\n",
501 ERR_error_string(ERR_get_error(), NULL
));
507 // Reset file to start
511 struct loc_database_magic magic
;
512 fread(&magic
, 1, sizeof(magic
), db
->f
);
514 hexdump(db
->ctx
, &magic
, sizeof(magic
));
516 // Feed magic into the hash
517 r
= EVP_DigestVerifyUpdate(mdctx
, &magic
, sizeof(magic
));
519 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
526 struct loc_database_header_v1 header_v1
;
529 switch (db
->version
) {
530 case LOC_DATABASE_VERSION_1
:
531 bytes_read
= fread(&header_v1
, 1, sizeof(header_v1
), db
->f
);
532 if (bytes_read
< sizeof(header_v1
)) {
533 ERROR(db
->ctx
, "Could not read header\n");
540 memset(header_v1
.signature1
, '\0', sizeof(header_v1
.signature1
));
541 header_v1
.signature1_length
= 0;
542 memset(header_v1
.signature2
, '\0', sizeof(header_v1
.signature2
));
543 header_v1
.signature2_length
= 0;
545 hexdump(db
->ctx
, &header_v1
, sizeof(header_v1
));
547 // Feed header into the hash
548 r
= EVP_DigestVerifyUpdate(mdctx
, &header_v1
, sizeof(header_v1
));
550 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
558 ERROR(db
->ctx
, "Cannot compute hash for database with format %d\n",
564 // Walk through the file in chunks of 64kB
565 char buffer
[64 * 1024];
567 while (!feof(db
->f
)) {
568 bytes_read
= fread(buffer
, 1, sizeof(buffer
), db
->f
);
570 hexdump(db
->ctx
, buffer
, bytes_read
);
572 r
= EVP_DigestVerifyUpdate(mdctx
, buffer
, bytes_read
);
574 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
581 // Check first signature
582 if (db
->signature1
) {
583 hexdump(db
->ctx
, db
->signature1
, db
->signature1_length
);
585 r
= EVP_DigestVerifyFinal(mdctx
,
586 (unsigned char*)db
->signature1
, db
->signature1_length
);
589 DEBUG(db
->ctx
, "The first signature is invalid\n");
592 DEBUG(db
->ctx
, "The first signature is valid\n");
595 ERROR(db
->ctx
, "Error verifying the first signature: %s\n",
596 ERR_error_string(ERR_get_error(), NULL
));
601 // Check second signature only when the first one was invalid
602 if (r
&& db
->signature2
) {
603 hexdump(db
->ctx
, db
->signature2
, db
->signature2_length
);
605 r
= EVP_DigestVerifyFinal(mdctx
,
606 (unsigned char*)db
->signature2
, db
->signature2_length
);
609 DEBUG(db
->ctx
, "The second signature is invalid\n");
612 DEBUG(db
->ctx
, "The second signature is valid\n");
615 ERROR(db
->ctx
, "Error verifying the second signature: %s\n",
616 ERR_error_string(ERR_get_error(), NULL
));
621 clock_t end
= clock();
622 DEBUG(db
->ctx
, "Signature checked in %.4fms\n",
623 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
627 EVP_MD_CTX_free(mdctx
);
633 LOC_EXPORT
time_t loc_database_created_at(struct loc_database
* db
) {
634 return db
->created_at
;
637 LOC_EXPORT
const char* loc_database_get_vendor(struct loc_database
* db
) {
638 return loc_stringpool_get(db
->pool
, db
->vendor
);
641 LOC_EXPORT
const char* loc_database_get_description(struct loc_database
* db
) {
642 return loc_stringpool_get(db
->pool
, db
->description
);
645 LOC_EXPORT
const char* loc_database_get_license(struct loc_database
* db
) {
646 return loc_stringpool_get(db
->pool
, db
->license
);
649 LOC_EXPORT
size_t loc_database_count_as(struct loc_database
* db
) {
653 // Returns the AS at position pos
654 static int loc_database_fetch_as(struct loc_database
* db
, struct loc_as
** as
, off_t pos
) {
655 if ((size_t)pos
>= db
->as_count
)
658 DEBUG(db
->ctx
, "Fetching AS at position %jd\n", (intmax_t)pos
);
661 switch (db
->version
) {
662 case LOC_DATABASE_VERSION_1
:
663 r
= loc_as_new_from_database_v1(db
->ctx
, db
->pool
, as
, db
->as_v1
+ pos
);
671 DEBUG(db
->ctx
, "Got AS%u\n", loc_as_get_number(*as
));
677 // Performs a binary search to find the AS in the list
678 LOC_EXPORT
int loc_database_get_as(struct loc_database
* db
, struct loc_as
** as
, uint32_t number
) {
680 off_t hi
= db
->as_count
- 1;
683 clock_t start
= clock();
686 off_t i
= (lo
+ hi
) / 2;
688 // Fetch AS in the middle between lo and hi
689 int r
= loc_database_fetch_as(db
, as
, i
);
693 // Check if this is a match
694 uint32_t as_number
= loc_as_get_number(*as
);
695 if (as_number
== number
) {
696 clock_t end
= clock();
698 // Log how fast this has been
699 DEBUG(db
->ctx
, "Found AS%u in %.4fms\n", as_number
,
700 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
705 // If it wasn't, we release the AS and
706 // adjust our search pointers
709 if (as_number
< number
) {
721 // Returns the network at position pos
722 static int loc_database_fetch_network(struct loc_database
* db
, struct loc_network
** network
,
723 struct in6_addr
* address
, unsigned int prefix
, off_t pos
) {
724 if ((size_t)pos
>= db
->networks_count
) {
725 DEBUG(db
->ctx
, "Network ID out of range: %jd/%jd\n",
726 (intmax_t)pos
, (intmax_t)db
->networks_count
);
731 DEBUG(db
->ctx
, "Fetching network at position %jd\n", (intmax_t)pos
);
734 switch (db
->version
) {
735 case LOC_DATABASE_VERSION_1
:
736 r
= loc_network_new_from_database_v1(db
->ctx
, network
,
737 address
, prefix
, db
->networks_v1
+ pos
);
745 char* string
= loc_network_str(*network
);
746 DEBUG(db
->ctx
, "Got network %s\n", string
);
753 static int __loc_database_node_is_leaf(const struct loc_database_network_node_v1
* node
) {
754 return (node
->network
!= htobe32(0xffffffff));
757 static int __loc_database_lookup_handle_leaf(struct loc_database
* db
, const struct in6_addr
* address
,
758 struct loc_network
** network
, struct in6_addr
* network_address
, unsigned int prefix
,
759 const struct loc_database_network_node_v1
* node
) {
760 off_t network_index
= be32toh(node
->network
);
762 DEBUG(db
->ctx
, "Handling leaf node at %jd (%jd)\n", (intmax_t)(node
- db
->network_nodes_v1
), (intmax_t)network_index
);
765 int r
= loc_database_fetch_network(db
, network
,
766 network_address
, prefix
, network_index
);
768 ERROR(db
->ctx
, "Could not fetch network %jd from database\n", (intmax_t)network_index
);
772 // Check if the given IP address is inside the network
773 r
= loc_network_match_address(*network
, address
);
775 DEBUG(db
->ctx
, "Searched address is not part of the network\n");
777 loc_network_unref(*network
);
782 // A network was found and the IP address matches
786 // Searches for an exact match along the path
787 static int __loc_database_lookup(struct loc_database
* db
, const struct in6_addr
* address
,
788 struct loc_network
** network
, struct in6_addr
* network_address
,
789 const struct loc_database_network_node_v1
* node
, unsigned int level
) {
794 int bit
= in6_addr_get_bit(address
, level
);
795 in6_addr_set_bit(network_address
, level
, bit
);
798 node_index
= be32toh(node
->zero
);
800 node_index
= be32toh(node
->one
);
802 // If the node index is zero, the tree ends here
803 // and we cannot descend any further
804 if (node_index
> 0) {
806 if ((size_t)node_index
>= db
->network_nodes_count
)
809 // Move on to the next node
810 r
= __loc_database_lookup(db
, address
, network
, network_address
,
811 db
->network_nodes_v1
+ node_index
, level
+ 1);
813 // End here if a result was found
821 DEBUG(db
->ctx
, "No match found below level %u\n", level
);
823 DEBUG(db
->ctx
, "Tree ended at level %u\n", level
);
826 // If this node has a leaf, we will check if it matches
827 if (__loc_database_node_is_leaf(node
)) {
828 r
= __loc_database_lookup_handle_leaf(db
, address
, network
, network_address
, level
, node
);
836 LOC_EXPORT
int loc_database_lookup(struct loc_database
* db
,
837 struct in6_addr
* address
, struct loc_network
** network
) {
838 struct in6_addr network_address
;
839 memset(&network_address
, 0, sizeof(network_address
));
844 clock_t start
= clock();
846 int r
= __loc_database_lookup(db
, address
, network
, &network_address
,
847 db
->network_nodes_v1
, 0);
849 clock_t end
= clock();
851 // Log how fast this has been
852 DEBUG(db
->ctx
, "Executed network search in %.4fms\n",
853 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
858 LOC_EXPORT
int loc_database_lookup_from_string(struct loc_database
* db
,
859 const char* string
, struct loc_network
** network
) {
860 struct in6_addr address
;
862 int r
= loc_parse_address(db
->ctx
, string
, &address
);
866 return loc_database_lookup(db
, &address
, network
);
869 // Returns the country at position pos
870 static int loc_database_fetch_country(struct loc_database
* db
,
871 struct loc_country
** country
, off_t pos
) {
872 if ((size_t)pos
>= db
->countries_count
)
875 DEBUG(db
->ctx
, "Fetching country at position %jd\n", (intmax_t)pos
);
878 switch (db
->version
) {
879 case LOC_DATABASE_VERSION_1
:
880 r
= loc_country_new_from_database_v1(db
->ctx
, db
->pool
, country
, db
->countries_v1
+ pos
);
888 DEBUG(db
->ctx
, "Got country %s\n", loc_country_get_code(*country
));
894 // Performs a binary search to find the country in the list
895 LOC_EXPORT
int loc_database_get_country(struct loc_database
* db
,
896 struct loc_country
** country
, const char* code
) {
898 off_t hi
= db
->countries_count
- 1;
901 clock_t start
= clock();
904 off_t i
= (lo
+ hi
) / 2;
906 // Fetch country in the middle between lo and hi
907 int r
= loc_database_fetch_country(db
, country
, i
);
911 // Check if this is a match
912 const char* cc
= loc_country_get_code(*country
);
913 int result
= strcmp(code
, cc
);
916 clock_t end
= clock();
918 // Log how fast this has been
919 DEBUG(db
->ctx
, "Found country %s in %.4fms\n", cc
,
920 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
925 // If it wasn't, we release the country and
926 // adjust our search pointers
927 loc_country_unref(*country
);
943 static void loc_database_enumerator_free(struct loc_database_enumerator
* enumerator
) {
944 DEBUG(enumerator
->ctx
, "Releasing database enumerator %p\n", enumerator
);
946 // Release all references
947 loc_database_unref(enumerator
->db
);
948 loc_unref(enumerator
->ctx
);
950 if (enumerator
->string
)
951 free(enumerator
->string
);
953 // Free network search
954 free(enumerator
->networks_visited
);
957 if (enumerator
->stack
)
958 loc_network_list_unref(enumerator
->stack
);
963 LOC_EXPORT
int loc_database_enumerator_new(struct loc_database_enumerator
** enumerator
,
964 struct loc_database
* db
, enum loc_database_enumerator_mode mode
, int flags
) {
965 struct loc_database_enumerator
* e
= calloc(1, sizeof(*e
));
970 e
->ctx
= loc_ref(db
->ctx
);
971 e
->db
= loc_database_ref(db
);
976 e
->flatten
= (flags
& LOC_DB_ENUMERATOR_FLAGS_FLATTEN
);
978 // Initialise graph search
979 e
->network_stack_depth
= 1;
980 e
->networks_visited
= calloc(db
->network_nodes_count
, sizeof(*e
->networks_visited
));
983 int r
= loc_network_list_new(e
->ctx
, &e
->stack
);
985 loc_database_enumerator_free(e
);
989 DEBUG(e
->ctx
, "Database enumerator object allocated at %p\n", e
);
995 LOC_EXPORT
struct loc_database_enumerator
* loc_database_enumerator_ref(struct loc_database_enumerator
* enumerator
) {
996 enumerator
->refcount
++;
1001 LOC_EXPORT
struct loc_database_enumerator
* loc_database_enumerator_unref(struct loc_database_enumerator
* enumerator
) {
1005 if (--enumerator
->refcount
> 0)
1008 loc_database_enumerator_free(enumerator
);
1012 LOC_EXPORT
int loc_database_enumerator_set_string(struct loc_database_enumerator
* enumerator
, const char* string
) {
1013 enumerator
->string
= strdup(string
);
1015 // Make the string lowercase
1016 for (char *p
= enumerator
->string
; *p
; p
++)
1022 LOC_EXPORT
struct loc_country_list
* loc_database_enumerator_get_countries(
1023 struct loc_database_enumerator
* enumerator
) {
1024 if (!enumerator
->countries
)
1027 return loc_country_list_ref(enumerator
->countries
);
1030 LOC_EXPORT
int loc_database_enumerator_set_countries(
1031 struct loc_database_enumerator
* enumerator
, struct loc_country_list
* countries
) {
1032 if (enumerator
->countries
)
1033 loc_country_list_unref(enumerator
->countries
);
1035 enumerator
->countries
= loc_country_list_ref(countries
);
1040 LOC_EXPORT
struct loc_as_list
* loc_database_enumerator_get_asns(
1041 struct loc_database_enumerator
* enumerator
) {
1042 if (!enumerator
->asns
)
1045 return loc_as_list_ref(enumerator
->asns
);
1048 LOC_EXPORT
int loc_database_enumerator_set_asns(
1049 struct loc_database_enumerator
* enumerator
, struct loc_as_list
* asns
) {
1050 if (enumerator
->asns
)
1051 loc_as_list_unref(enumerator
->asns
);
1053 enumerator
->asns
= loc_as_list_ref(asns
);
1058 LOC_EXPORT
int loc_database_enumerator_set_flag(
1059 struct loc_database_enumerator
* enumerator
, enum loc_network_flags flag
) {
1060 enumerator
->flags
|= flag
;
1065 LOC_EXPORT
int loc_database_enumerator_set_family(
1066 struct loc_database_enumerator
* enumerator
, int family
) {
1067 enumerator
->family
= family
;
1072 LOC_EXPORT
int loc_database_enumerator_next_as(
1073 struct loc_database_enumerator
* enumerator
, struct loc_as
** as
) {
1076 // Do not do anything if not in AS mode
1077 if (enumerator
->mode
!= LOC_DB_ENUMERATE_ASES
)
1080 struct loc_database
* db
= enumerator
->db
;
1082 while (enumerator
->as_index
< db
->as_count
) {
1083 // Fetch the next AS
1084 int r
= loc_database_fetch_as(db
, as
, enumerator
->as_index
++);
1088 r
= loc_as_match_string(*as
, enumerator
->string
);
1090 DEBUG(enumerator
->ctx
, "AS%d (%s) matches %s\n",
1091 loc_as_get_number(*as
), loc_as_get_name(*as
), enumerator
->string
);
1102 enumerator
->as_index
= 0;
1104 // We have searched through all of them
1108 static int loc_database_enumerator_stack_push_node(
1109 struct loc_database_enumerator
* e
, off_t offset
, int i
, int depth
) {
1110 // Do not add empty nodes
1114 // Check if there is any space left on the stack
1115 if (e
->network_stack_depth
>= MAX_STACK_DEPTH
) {
1116 ERROR(e
->ctx
, "Maximum stack size reached: %d\n", e
->network_stack_depth
);
1120 // Increase stack size
1121 int s
= ++e
->network_stack_depth
;
1123 DEBUG(e
->ctx
, "Added node %jd to stack (%d)\n", (intmax_t)offset
, depth
);
1125 e
->network_stack
[s
].offset
= offset
;
1126 e
->network_stack
[s
].i
= i
;
1127 e
->network_stack
[s
].depth
= depth
;
1132 static int loc_network_match_asns(struct loc_network
* network
, struct loc_as_list
* asns
) {
1133 uint32_t asn
= loc_network_get_asn(network
);
1135 return loc_as_list_contains_number(asns
, asn
);
1138 static int loc_database_enumerator_filter_network(
1139 struct loc_database_enumerator
* enumerator
, struct loc_network
* network
) {
1140 // Skip if the family does not match
1141 if (enumerator
->family
&& loc_network_address_family(network
) != enumerator
->family
)
1144 // Skip if the country code does not match
1145 if (enumerator
->countries
) {
1146 if (!loc_country_list_empty(enumerator
->countries
)) {
1147 const char* country_code
= loc_network_get_country_code(network
);
1149 if (!loc_country_list_contains_code(enumerator
->countries
, country_code
))
1154 // Skip if the ASN does not match
1155 if (enumerator
->asns
&& !loc_network_match_asns(network
, enumerator
->asns
))
1158 // Skip if flags do not match
1159 if (enumerator
->flags
&&
1160 !loc_network_match_flag(network
, enumerator
->flags
))
1167 static int __loc_database_enumerator_next_network(
1168 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
, int filter
) {
1169 // Return top element from the stack
1171 *network
= loc_network_list_pop(enumerator
->stack
);
1177 // Throw away any networks by filter
1178 if (filter
&& loc_database_enumerator_filter_network(enumerator
, *network
)) {
1179 loc_network_unref(*network
);
1188 DEBUG(enumerator
->ctx
, "Called with a stack of %u nodes\n",
1189 enumerator
->network_stack_depth
);
1192 while (enumerator
->network_stack_depth
> 0) {
1193 DEBUG(enumerator
->ctx
, "Stack depth: %u\n", enumerator
->network_stack_depth
);
1195 // Get object from top of the stack
1196 struct loc_node_stack
* node
= &enumerator
->network_stack
[enumerator
->network_stack_depth
];
1198 // Remove the node from the stack if we have already visited it
1199 if (enumerator
->networks_visited
[node
->offset
]) {
1200 enumerator
->network_stack_depth
--;
1204 // Mark the bits on the path correctly
1205 in6_addr_set_bit(&enumerator
->network_address
,
1206 (node
->depth
> 0) ? node
->depth
- 1 : 0, node
->i
);
1208 DEBUG(enumerator
->ctx
, "Looking at node %jd\n", (intmax_t)node
->offset
);
1209 enumerator
->networks_visited
[node
->offset
]++;
1211 // Pop node from top of the stack
1212 struct loc_database_network_node_v1
* n
=
1213 enumerator
->db
->network_nodes_v1
+ node
->offset
;
1215 // Add edges to stack
1216 int r
= loc_database_enumerator_stack_push_node(enumerator
,
1217 be32toh(n
->one
), 1, node
->depth
+ 1);
1222 r
= loc_database_enumerator_stack_push_node(enumerator
,
1223 be32toh(n
->zero
), 0, node
->depth
+ 1);
1228 // Check if this node is a leaf and has a network object
1229 if (__loc_database_node_is_leaf(n
)) {
1230 off_t network_index
= be32toh(n
->network
);
1232 DEBUG(enumerator
->ctx
, "Node has a network at %jd\n", (intmax_t)network_index
);
1234 // Fetch the network object
1235 r
= loc_database_fetch_network(enumerator
->db
, network
,
1236 &enumerator
->network_address
, node
->depth
, network_index
);
1238 // Break on any errors
1242 // Return all networks when the filter is disabled
1246 // Check if we are interested in this network
1247 if (loc_database_enumerator_filter_network(enumerator
, *network
)) {
1248 loc_network_unref(*network
);
1258 // Reached the end of the search
1262 static int __loc_database_enumerator_next_network_flattened(
1263 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
) {
1264 // Fetch the next network
1265 int r
= __loc_database_enumerator_next_network(enumerator
, network
, 1);
1269 // End if we could not read another network
1273 struct loc_network
* subnet
= NULL
;
1274 struct loc_network_list
* subnets
;
1276 // Create a list with all subnets
1277 r
= loc_network_list_new(enumerator
->ctx
, &subnets
);
1281 // Search all subnets from the database
1283 // Fetch the next network in line
1284 r
= __loc_database_enumerator_next_network(enumerator
, &subnet
, 0);
1288 // End if we did not receive another subnet
1292 // Collect all subnets in a list
1293 if (loc_network_is_subnet(*network
, subnet
)) {
1294 r
= loc_network_list_push(subnets
, subnet
);
1298 loc_network_unref(subnet
);
1302 // If this is not a subnet, we push it back onto the stack and break
1303 r
= loc_network_list_push(enumerator
->stack
, subnet
);
1307 loc_network_unref(subnet
);
1311 DEBUG(enumerator
->ctx
, "Found %zu subnet(s)\n", loc_network_list_size(subnets
));
1313 // We can abort here if the network has no subnets
1314 if (loc_network_list_empty(subnets
)) {
1315 loc_network_list_unref(subnets
);
1320 // If the network has any subnets, we will break it into smaller parts
1321 // without the subnets.
1322 struct loc_network_list
* excluded
= loc_network_exclude_list(*network
, subnets
);
1323 if (!excluded
|| loc_network_list_empty(excluded
)) {
1328 // Replace network with the first one
1329 loc_network_unref(*network
);
1331 *network
= loc_network_list_pop_first(excluded
);
1333 // Push the rest onto the stack
1334 loc_network_list_reverse(excluded
);
1335 loc_network_list_merge(enumerator
->stack
, excluded
);
1337 loc_network_list_unref(excluded
);
1341 loc_network_unref(subnet
);
1343 loc_network_list_unref(subnets
);
1348 LOC_EXPORT
int loc_database_enumerator_next_network(
1349 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
) {
1350 // Do not do anything if not in network mode
1351 if (enumerator
->mode
!= LOC_DB_ENUMERATE_NETWORKS
)
1355 if (enumerator
->flatten
)
1356 return __loc_database_enumerator_next_network_flattened(enumerator
, network
);
1358 return __loc_database_enumerator_next_network(enumerator
, network
, 1);
1361 LOC_EXPORT
int loc_database_enumerator_next_country(
1362 struct loc_database_enumerator
* enumerator
, struct loc_country
** country
) {
1365 // Do not do anything if not in country mode
1366 if (enumerator
->mode
!= LOC_DB_ENUMERATE_COUNTRIES
)
1369 struct loc_database
* db
= enumerator
->db
;
1371 while (enumerator
->country_index
< db
->countries_count
) {
1372 // Fetch the next country
1373 int r
= loc_database_fetch_country(db
, country
, enumerator
->country_index
++);
1377 // We do not filter here, so it always is a match
1382 enumerator
->country_index
= 0;
1384 // We have searched through all of them