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 <libloc/libloc.h>
40 #include <libloc/address.h>
41 #include <libloc/as.h>
42 #include <libloc/as-list.h>
43 #include <libloc/compat.h>
44 #include <libloc/country.h>
45 #include <libloc/country-list.h>
46 #include <libloc/database.h>
47 #include <libloc/format.h>
48 #include <libloc/network.h>
49 #include <libloc/network-list.h>
50 #include <libloc/private.h>
51 #include <libloc/stringpool.h>
59 enum loc_database_version version
;
67 size_t signature1_length
;
69 size_t signature2_length
;
71 // ASes in the database
72 struct loc_database_as_v1
* as_v1
;
76 struct loc_database_network_node_v1
* network_nodes_v1
;
77 size_t network_nodes_count
;
80 struct loc_database_network_v1
* networks_v1
;
81 size_t networks_count
;
84 struct loc_database_country_v1
* countries_v1
;
85 size_t countries_count
;
87 struct loc_stringpool
* pool
;
90 #define MAX_STACK_DEPTH 256
92 struct loc_node_stack
{
94 int i
; // Is this node 0 or 1?
98 struct loc_database_enumerator
{
100 struct loc_database
* db
;
101 enum loc_database_enumerator_mode mode
;
106 struct loc_country_list
* countries
;
107 struct loc_as_list
* asns
;
108 enum loc_network_flags flags
;
114 // Index of the AS we are looking at
115 unsigned int as_index
;
117 // Index of the country we are looking at
118 unsigned int country_index
;
121 struct in6_addr network_address
;
122 struct loc_node_stack network_stack
[MAX_STACK_DEPTH
];
123 int network_stack_depth
;
124 unsigned int* networks_visited
;
126 // For subnet search and bogons
127 struct loc_network_list
* stack
;
128 struct loc_network_list
* subnets
;
131 struct in6_addr gap6_start
;
132 struct in6_addr gap4_start
;
135 static int loc_database_read_magic(struct loc_database
* db
) {
136 struct loc_database_magic magic
;
139 size_t bytes_read
= fread(&magic
, 1, sizeof(magic
), db
->f
);
141 // Check if we have been able to read enough data
142 if (bytes_read
< sizeof(magic
)) {
143 ERROR(db
->ctx
, "Could not read enough data to validate magic bytes\n");
144 DEBUG(db
->ctx
, "Read %zu bytes, but needed %zu\n", bytes_read
, sizeof(magic
));
148 // Compare magic bytes
149 if (memcmp(LOC_DATABASE_MAGIC
, magic
.magic
, strlen(LOC_DATABASE_MAGIC
)) == 0) {
150 DEBUG(db
->ctx
, "Magic value matches\n");
153 db
->version
= magic
.version
;
159 ERROR(db
->ctx
, "Unrecognized file type\n");
166 static int loc_database_read_as_section_v1(struct loc_database
* db
,
167 const struct loc_database_header_v1
* header
) {
168 off_t as_offset
= be32toh(header
->as_offset
);
169 size_t as_length
= be32toh(header
->as_length
);
171 DEBUG(db
->ctx
, "Reading AS section from %jd (%zu bytes)\n", (intmax_t)as_offset
, as_length
);
174 db
->as_v1
= mmap(NULL
, as_length
, PROT_READ
,
175 MAP_PRIVATE
, fileno(db
->f
), as_offset
);
177 if (db
->as_v1
== MAP_FAILED
) {
178 ERROR(db
->ctx
, "Could not mmap() AS section: %m\n");
183 db
->as_count
= as_length
/ sizeof(*db
->as_v1
);
185 INFO(db
->ctx
, "Read %zu ASes from the database\n", db
->as_count
);
190 static int loc_database_read_network_nodes_section_v1(struct loc_database
* db
,
191 const struct loc_database_header_v1
* header
) {
192 off_t network_nodes_offset
= be32toh(header
->network_tree_offset
);
193 size_t network_nodes_length
= be32toh(header
->network_tree_length
);
195 DEBUG(db
->ctx
, "Reading network nodes section from %jd (%zu bytes)\n",
196 (intmax_t)network_nodes_offset
, network_nodes_length
);
198 if (network_nodes_length
> 0) {
199 db
->network_nodes_v1
= mmap(NULL
, network_nodes_length
, PROT_READ
,
200 MAP_PRIVATE
, fileno(db
->f
), network_nodes_offset
);
202 if (db
->network_nodes_v1
== MAP_FAILED
) {
203 ERROR(db
->ctx
, "Could not mmap() network nodes section: %m\n");
208 db
->network_nodes_count
= network_nodes_length
/ sizeof(*db
->network_nodes_v1
);
210 INFO(db
->ctx
, "Read %zu network nodes from the database\n", db
->network_nodes_count
);
215 static int loc_database_read_networks_section_v1(struct loc_database
* db
,
216 const struct loc_database_header_v1
* header
) {
217 off_t networks_offset
= be32toh(header
->network_data_offset
);
218 size_t networks_length
= be32toh(header
->network_data_length
);
220 DEBUG(db
->ctx
, "Reading networks section from %jd (%zu bytes)\n",
221 (intmax_t)networks_offset
, networks_length
);
223 if (networks_length
> 0) {
224 db
->networks_v1
= mmap(NULL
, networks_length
, PROT_READ
,
225 MAP_PRIVATE
, fileno(db
->f
), networks_offset
);
227 if (db
->networks_v1
== MAP_FAILED
) {
228 ERROR(db
->ctx
, "Could not mmap() networks section: %m\n");
233 db
->networks_count
= networks_length
/ sizeof(*db
->networks_v1
);
235 INFO(db
->ctx
, "Read %zu networks from the database\n", db
->networks_count
);
240 static int loc_database_read_countries_section_v1(struct loc_database
* db
,
241 const struct loc_database_header_v1
* header
) {
242 off_t countries_offset
= be32toh(header
->countries_offset
);
243 size_t countries_length
= be32toh(header
->countries_length
);
245 DEBUG(db
->ctx
, "Reading countries section from %jd (%zu bytes)\n",
246 (intmax_t)countries_offset
, countries_length
);
248 if (countries_length
> 0) {
249 db
->countries_v1
= mmap(NULL
, countries_length
, PROT_READ
,
250 MAP_PRIVATE
, fileno(db
->f
), countries_offset
);
252 if (db
->countries_v1
== MAP_FAILED
) {
253 ERROR(db
->ctx
, "Could not mmap() countries section: %m\n");
258 db
->countries_count
= countries_length
/ sizeof(*db
->countries_v1
);
260 INFO(db
->ctx
, "Read %zu countries from the database\n",
261 db
->countries_count
);
266 static int loc_database_read_signature(struct loc_database
* db
,
267 char** dst
, char* src
, size_t length
) {
268 // Check for a plausible signature length
269 if (length
> LOC_SIGNATURE_MAX_LENGTH
) {
270 ERROR(db
->ctx
, "Signature too long: %zu\n", length
);
274 DEBUG(db
->ctx
, "Reading signature of %zu bytes\n", length
);
277 *dst
= malloc(length
);
282 memcpy(*dst
, src
, length
);
287 static int loc_database_read_header_v1(struct loc_database
* db
) {
288 struct loc_database_header_v1 header
;
292 size_t size
= fread(&header
, 1, sizeof(header
), db
->f
);
294 if (size
< sizeof(header
)) {
295 ERROR(db
->ctx
, "Could not read enough data for header\n");
300 db
->created_at
= be64toh(header
.created_at
);
301 db
->vendor
= be32toh(header
.vendor
);
302 db
->description
= be32toh(header
.description
);
303 db
->license
= be32toh(header
.license
);
305 db
->signature1_length
= be16toh(header
.signature1_length
);
306 db
->signature2_length
= be16toh(header
.signature2_length
);
309 if (db
->signature1_length
) {
310 r
= loc_database_read_signature(db
, &db
->signature1
,
311 header
.signature1
, db
->signature1_length
);
316 if (db
->signature2_length
) {
317 r
= loc_database_read_signature(db
, &db
->signature2
,
318 header
.signature2
, db
->signature2_length
);
324 off_t pool_offset
= be32toh(header
.pool_offset
);
325 size_t pool_length
= be32toh(header
.pool_length
);
327 r
= loc_stringpool_open(db
->ctx
, &db
->pool
,
328 db
->f
, pool_length
, pool_offset
);
333 r
= loc_database_read_as_section_v1(db
, &header
);
338 r
= loc_database_read_network_nodes_section_v1(db
, &header
);
343 r
= loc_database_read_networks_section_v1(db
, &header
);
348 r
= loc_database_read_countries_section_v1(db
, &header
);
355 static int loc_database_read_header(struct loc_database
* db
) {
356 DEBUG(db
->ctx
, "Database version is %u\n", db
->version
);
358 switch (db
->version
) {
359 case LOC_DATABASE_VERSION_1
:
360 return loc_database_read_header_v1(db
);
363 ERROR(db
->ctx
, "Incompatible database version: %u\n", db
->version
);
368 static int loc_database_read(struct loc_database
* db
, FILE* f
) {
369 clock_t start
= clock();
373 // Clone file descriptor
376 ERROR(db
->ctx
, "Could not duplicate file descriptor\n");
380 // Reopen the file so that we can keep our own file handle
381 db
->f
= fdopen(fd
, "r");
383 ERROR(db
->ctx
, "Could not re-open database file\n");
387 // Rewind to the start of the file
391 int r
= loc_database_read_magic(db
);
396 r
= loc_database_read_header(db
);
400 clock_t end
= clock();
402 INFO(db
->ctx
, "Opened database in %.4fms\n",
403 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
408 LOC_EXPORT
int loc_database_new(struct loc_ctx
* ctx
, struct loc_database
** database
, FILE* f
) {
409 // Fail on invalid file handle
413 struct loc_database
* db
= calloc(1, sizeof(*db
));
418 db
->ctx
= loc_ref(ctx
);
421 DEBUG(db
->ctx
, "Database object allocated at %p\n", db
);
423 int r
= loc_database_read(db
, f
);
425 loc_database_unref(db
);
434 LOC_EXPORT
struct loc_database
* loc_database_ref(struct loc_database
* db
) {
440 static void loc_database_free(struct loc_database
* db
) {
443 DEBUG(db
->ctx
, "Releasing database %p\n", db
);
446 if (db
->as_v1
&& db
->as_v1
!= MAP_FAILED
) {
447 r
= munmap(db
->as_v1
, db
->as_count
* sizeof(*db
->as_v1
));
449 ERROR(db
->ctx
, "Could not unmap AS section: %m\n");
452 // Remove mapped network sections
453 if (db
->networks_v1
&& db
->networks_v1
!= MAP_FAILED
) {
454 r
= munmap(db
->networks_v1
, db
->networks_count
* sizeof(*db
->networks_v1
));
456 ERROR(db
->ctx
, "Could not unmap networks section: %m\n");
459 // Remove mapped network nodes section
460 if (db
->network_nodes_v1
&& db
->network_nodes_v1
!= MAP_FAILED
) {
461 r
= munmap(db
->network_nodes_v1
, db
->network_nodes_count
* sizeof(*db
->network_nodes_v1
));
463 ERROR(db
->ctx
, "Could not unmap network nodes section: %m\n");
466 // Remove mapped countries section
467 if (db
->countries_v1
&& db
->countries_v1
!= MAP_FAILED
) {
468 r
= munmap(db
->countries_v1
, db
->countries_count
* sizeof(*db
->countries_v1
));
470 ERROR(db
->ctx
, "Could not unmap countries section: %m\n");
474 loc_stringpool_unref(db
->pool
);
478 free(db
->signature1
);
480 free(db
->signature2
);
482 // Close database file
490 LOC_EXPORT
struct loc_database
* loc_database_unref(struct loc_database
* db
) {
491 if (--db
->refcount
> 0)
494 loc_database_free(db
);
498 LOC_EXPORT
int loc_database_verify(struct loc_database
* db
, FILE* f
) {
499 size_t bytes_read
= 0;
501 // Cannot do this when no signature is available
502 if (!db
->signature1
&& !db
->signature2
) {
503 DEBUG(db
->ctx
, "No signature available to verify\n");
507 // Start the stopwatch
508 clock_t start
= clock();
511 EVP_PKEY
* pkey
= PEM_read_PUBKEY(f
, NULL
, NULL
, NULL
);
513 ERROR(db
->ctx
, "Could not parse public key: %s\n",
514 ERR_error_string(ERR_get_error(), NULL
));
521 EVP_MD_CTX
* mdctx
= EVP_MD_CTX_new();
523 // Initialise hash function
524 r
= EVP_DigestVerifyInit(mdctx
, NULL
, NULL
, NULL
, pkey
);
526 ERROR(db
->ctx
, "Error initializing signature validation: %s\n",
527 ERR_error_string(ERR_get_error(), NULL
));
533 // Reset file to start
537 struct loc_database_magic magic
;
538 bytes_read
= fread(&magic
, 1, sizeof(magic
), db
->f
);
539 if (bytes_read
< sizeof(magic
)) {
540 ERROR(db
->ctx
, "Could not read header: %m\n");
545 hexdump(db
->ctx
, &magic
, sizeof(magic
));
547 // Feed magic into the hash
548 r
= EVP_DigestVerifyUpdate(mdctx
, &magic
, sizeof(magic
));
550 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
557 struct loc_database_header_v1 header_v1
;
559 switch (db
->version
) {
560 case LOC_DATABASE_VERSION_1
:
561 bytes_read
= fread(&header_v1
, 1, sizeof(header_v1
), db
->f
);
562 if (bytes_read
< sizeof(header_v1
)) {
563 ERROR(db
->ctx
, "Could not read header\n");
570 memset(header_v1
.signature1
, '\0', sizeof(header_v1
.signature1
));
571 header_v1
.signature1_length
= 0;
572 memset(header_v1
.signature2
, '\0', sizeof(header_v1
.signature2
));
573 header_v1
.signature2_length
= 0;
575 hexdump(db
->ctx
, &header_v1
, sizeof(header_v1
));
577 // Feed header into the hash
578 r
= EVP_DigestVerifyUpdate(mdctx
, &header_v1
, sizeof(header_v1
));
580 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
588 ERROR(db
->ctx
, "Cannot compute hash for database with format %d\n",
594 // Walk through the file in chunks of 64kB
595 char buffer
[64 * 1024];
597 while (!feof(db
->f
)) {
598 bytes_read
= fread(buffer
, 1, sizeof(buffer
), db
->f
);
600 hexdump(db
->ctx
, buffer
, bytes_read
);
602 r
= EVP_DigestVerifyUpdate(mdctx
, buffer
, bytes_read
);
604 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
611 // Check first signature
612 if (db
->signature1
) {
613 hexdump(db
->ctx
, db
->signature1
, db
->signature1_length
);
615 r
= EVP_DigestVerifyFinal(mdctx
,
616 (unsigned char*)db
->signature1
, db
->signature1_length
);
619 DEBUG(db
->ctx
, "The first signature is invalid\n");
622 DEBUG(db
->ctx
, "The first signature is valid\n");
625 ERROR(db
->ctx
, "Error verifying the first signature: %s\n",
626 ERR_error_string(ERR_get_error(), NULL
));
631 // Check second signature only when the first one was invalid
632 if (r
&& db
->signature2
) {
633 hexdump(db
->ctx
, db
->signature2
, db
->signature2_length
);
635 r
= EVP_DigestVerifyFinal(mdctx
,
636 (unsigned char*)db
->signature2
, db
->signature2_length
);
639 DEBUG(db
->ctx
, "The second signature is invalid\n");
642 DEBUG(db
->ctx
, "The second signature is valid\n");
645 ERROR(db
->ctx
, "Error verifying the second signature: %s\n",
646 ERR_error_string(ERR_get_error(), NULL
));
651 clock_t end
= clock();
652 INFO(db
->ctx
, "Signature checked in %.4fms\n",
653 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
657 EVP_MD_CTX_free(mdctx
);
663 LOC_EXPORT
time_t loc_database_created_at(struct loc_database
* db
) {
664 return db
->created_at
;
667 LOC_EXPORT
const char* loc_database_get_vendor(struct loc_database
* db
) {
668 return loc_stringpool_get(db
->pool
, db
->vendor
);
671 LOC_EXPORT
const char* loc_database_get_description(struct loc_database
* db
) {
672 return loc_stringpool_get(db
->pool
, db
->description
);
675 LOC_EXPORT
const char* loc_database_get_license(struct loc_database
* db
) {
676 return loc_stringpool_get(db
->pool
, db
->license
);
679 LOC_EXPORT
size_t loc_database_count_as(struct loc_database
* db
) {
683 // Returns the AS at position pos
684 static int loc_database_fetch_as(struct loc_database
* db
, struct loc_as
** as
, off_t pos
) {
685 if ((size_t)pos
>= db
->as_count
)
688 DEBUG(db
->ctx
, "Fetching AS at position %jd\n", (intmax_t)pos
);
691 switch (db
->version
) {
692 case LOC_DATABASE_VERSION_1
:
693 r
= loc_as_new_from_database_v1(db
->ctx
, db
->pool
, as
, db
->as_v1
+ pos
);
701 DEBUG(db
->ctx
, "Got AS%u\n", loc_as_get_number(*as
));
707 // Performs a binary search to find the AS in the list
708 LOC_EXPORT
int loc_database_get_as(struct loc_database
* db
, struct loc_as
** as
, uint32_t number
) {
710 off_t hi
= db
->as_count
- 1;
714 clock_t start
= clock();
718 off_t i
= (lo
+ hi
) / 2;
720 // Fetch AS in the middle between lo and hi
721 int r
= loc_database_fetch_as(db
, as
, i
);
725 // Check if this is a match
726 uint32_t as_number
= loc_as_get_number(*as
);
727 if (as_number
== number
) {
729 clock_t end
= clock();
731 // Log how fast this has been
732 DEBUG(db
->ctx
, "Found AS%u in %.4fms\n", as_number
,
733 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
739 // If it wasn't, we release the AS and
740 // adjust our search pointers
743 if (as_number
< number
) {
755 // Returns the network at position pos
756 static int loc_database_fetch_network(struct loc_database
* db
, struct loc_network
** network
,
757 struct in6_addr
* address
, unsigned int prefix
, off_t pos
) {
758 if ((size_t)pos
>= db
->networks_count
) {
759 DEBUG(db
->ctx
, "Network ID out of range: %jd/%jd\n",
760 (intmax_t)pos
, (intmax_t)db
->networks_count
);
765 DEBUG(db
->ctx
, "Fetching network at position %jd\n", (intmax_t)pos
);
768 switch (db
->version
) {
769 case LOC_DATABASE_VERSION_1
:
770 r
= loc_network_new_from_database_v1(db
->ctx
, network
,
771 address
, prefix
, db
->networks_v1
+ pos
);
779 DEBUG(db
->ctx
, "Got network %s\n", loc_network_str(*network
));
784 static int __loc_database_node_is_leaf(const struct loc_database_network_node_v1
* node
) {
785 return (node
->network
!= htobe32(0xffffffff));
788 static int __loc_database_lookup_handle_leaf(struct loc_database
* db
, const struct in6_addr
* address
,
789 struct loc_network
** network
, struct in6_addr
* network_address
, unsigned int prefix
,
790 const struct loc_database_network_node_v1
* node
) {
791 off_t network_index
= be32toh(node
->network
);
793 DEBUG(db
->ctx
, "Handling leaf node at %jd (%jd)\n", (intmax_t)(node
- db
->network_nodes_v1
), (intmax_t)network_index
);
796 int r
= loc_database_fetch_network(db
, network
,
797 network_address
, prefix
, network_index
);
799 ERROR(db
->ctx
, "Could not fetch network %jd from database\n", (intmax_t)network_index
);
803 // Check if the given IP address is inside the network
804 if (!loc_network_matches_address(*network
, address
)) {
805 DEBUG(db
->ctx
, "Searched address is not part of the network\n");
807 loc_network_unref(*network
);
812 // A network was found and the IP address matches
816 // Searches for an exact match along the path
817 static int __loc_database_lookup(struct loc_database
* db
, const struct in6_addr
* address
,
818 struct loc_network
** network
, struct in6_addr
* network_address
,
819 const struct loc_database_network_node_v1
* node
, unsigned int level
) {
824 int bit
= loc_address_get_bit(address
, level
);
825 loc_address_set_bit(network_address
, level
, bit
);
828 node_index
= be32toh(node
->zero
);
830 node_index
= be32toh(node
->one
);
832 // If the node index is zero, the tree ends here
833 // and we cannot descend any further
834 if (node_index
> 0) {
836 if ((size_t)node_index
>= db
->network_nodes_count
)
839 // Move on to the next node
840 r
= __loc_database_lookup(db
, address
, network
, network_address
,
841 db
->network_nodes_v1
+ node_index
, level
+ 1);
843 // End here if a result was found
851 DEBUG(db
->ctx
, "No match found below level %u\n", level
);
853 DEBUG(db
->ctx
, "Tree ended at level %u\n", level
);
856 // If this node has a leaf, we will check if it matches
857 if (__loc_database_node_is_leaf(node
)) {
858 r
= __loc_database_lookup_handle_leaf(db
, address
, network
, network_address
, level
, node
);
866 LOC_EXPORT
int loc_database_lookup(struct loc_database
* db
,
867 const struct in6_addr
* address
, struct loc_network
** network
) {
868 struct in6_addr network_address
;
869 memset(&network_address
, 0, sizeof(network_address
));
875 clock_t start
= clock();
878 int r
= __loc_database_lookup(db
, address
, network
, &network_address
,
879 db
->network_nodes_v1
, 0);
882 clock_t end
= clock();
884 // Log how fast this has been
885 DEBUG(db
->ctx
, "Executed network search in %.4fms\n",
886 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
892 LOC_EXPORT
int loc_database_lookup_from_string(struct loc_database
* db
,
893 const char* string
, struct loc_network
** network
) {
894 struct in6_addr address
;
896 int r
= loc_address_parse(&address
, NULL
, string
);
900 return loc_database_lookup(db
, &address
, network
);
903 // Returns the country at position pos
904 static int loc_database_fetch_country(struct loc_database
* db
,
905 struct loc_country
** country
, off_t pos
) {
906 if ((size_t)pos
>= db
->countries_count
)
909 DEBUG(db
->ctx
, "Fetching country at position %jd\n", (intmax_t)pos
);
912 switch (db
->version
) {
913 case LOC_DATABASE_VERSION_1
:
914 r
= loc_country_new_from_database_v1(db
->ctx
, db
->pool
, country
, db
->countries_v1
+ pos
);
922 DEBUG(db
->ctx
, "Got country %s\n", loc_country_get_code(*country
));
928 // Performs a binary search to find the country in the list
929 LOC_EXPORT
int loc_database_get_country(struct loc_database
* db
,
930 struct loc_country
** country
, const char* code
) {
932 off_t hi
= db
->countries_count
- 1;
936 clock_t start
= clock();
940 off_t i
= (lo
+ hi
) / 2;
942 // Fetch country in the middle between lo and hi
943 int r
= loc_database_fetch_country(db
, country
, i
);
947 // Check if this is a match
948 const char* cc
= loc_country_get_code(*country
);
949 int result
= strcmp(code
, cc
);
953 clock_t end
= clock();
955 // Log how fast this has been
956 DEBUG(db
->ctx
, "Found country %s in %.4fms\n", cc
,
957 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
963 // If it wasn't, we release the country and
964 // adjust our search pointers
965 loc_country_unref(*country
);
981 static void loc_database_enumerator_free(struct loc_database_enumerator
* enumerator
) {
982 DEBUG(enumerator
->ctx
, "Releasing database enumerator %p\n", enumerator
);
984 // Release all references
985 loc_database_unref(enumerator
->db
);
986 loc_unref(enumerator
->ctx
);
988 if (enumerator
->string
)
989 free(enumerator
->string
);
991 if (enumerator
->countries
)
992 loc_country_list_unref(enumerator
->countries
);
994 if (enumerator
->asns
)
995 loc_as_list_unref(enumerator
->asns
);
997 // Free network search
998 free(enumerator
->networks_visited
);
1000 // Free subnet/bogons stack
1001 if (enumerator
->stack
)
1002 loc_network_list_unref(enumerator
->stack
);
1004 if (enumerator
->subnets
)
1005 loc_network_list_unref(enumerator
->subnets
);
1010 LOC_EXPORT
int loc_database_enumerator_new(struct loc_database_enumerator
** enumerator
,
1011 struct loc_database
* db
, enum loc_database_enumerator_mode mode
, int flags
) {
1012 struct loc_database_enumerator
* e
= calloc(1, sizeof(*e
));
1016 // Reference context
1017 e
->ctx
= loc_ref(db
->ctx
);
1018 e
->db
= loc_database_ref(db
);
1023 e
->flatten
= (flags
& LOC_DB_ENUMERATOR_FLAGS_FLATTEN
);
1025 // Initialise graph search
1026 e
->network_stack_depth
= 1;
1027 e
->networks_visited
= calloc(db
->network_nodes_count
, sizeof(*e
->networks_visited
));
1030 int r
= loc_network_list_new(e
->ctx
, &e
->stack
);
1032 loc_database_enumerator_free(e
);
1036 // Initialize bogon search
1037 loc_address_reset(&e
->gap6_start
, AF_INET6
);
1038 loc_address_reset(&e
->gap4_start
, AF_INET
);
1040 DEBUG(e
->ctx
, "Database enumerator object allocated at %p\n", e
);
1046 LOC_EXPORT
struct loc_database_enumerator
* loc_database_enumerator_ref(struct loc_database_enumerator
* enumerator
) {
1047 enumerator
->refcount
++;
1052 LOC_EXPORT
struct loc_database_enumerator
* loc_database_enumerator_unref(struct loc_database_enumerator
* enumerator
) {
1056 if (--enumerator
->refcount
> 0)
1059 loc_database_enumerator_free(enumerator
);
1063 LOC_EXPORT
int loc_database_enumerator_set_string(struct loc_database_enumerator
* enumerator
, const char* string
) {
1064 enumerator
->string
= strdup(string
);
1066 // Make the string lowercase
1067 for (char *p
= enumerator
->string
; *p
; p
++)
1073 LOC_EXPORT
struct loc_country_list
* loc_database_enumerator_get_countries(
1074 struct loc_database_enumerator
* enumerator
) {
1075 if (!enumerator
->countries
)
1078 return loc_country_list_ref(enumerator
->countries
);
1081 LOC_EXPORT
int loc_database_enumerator_set_countries(
1082 struct loc_database_enumerator
* enumerator
, struct loc_country_list
* countries
) {
1083 if (enumerator
->countries
)
1084 loc_country_list_unref(enumerator
->countries
);
1086 enumerator
->countries
= loc_country_list_ref(countries
);
1091 LOC_EXPORT
struct loc_as_list
* loc_database_enumerator_get_asns(
1092 struct loc_database_enumerator
* enumerator
) {
1093 if (!enumerator
->asns
)
1096 return loc_as_list_ref(enumerator
->asns
);
1099 LOC_EXPORT
int loc_database_enumerator_set_asns(
1100 struct loc_database_enumerator
* enumerator
, struct loc_as_list
* asns
) {
1101 if (enumerator
->asns
)
1102 loc_as_list_unref(enumerator
->asns
);
1104 enumerator
->asns
= loc_as_list_ref(asns
);
1109 LOC_EXPORT
int loc_database_enumerator_set_flag(
1110 struct loc_database_enumerator
* enumerator
, enum loc_network_flags flag
) {
1111 enumerator
->flags
|= flag
;
1116 LOC_EXPORT
int loc_database_enumerator_set_family(
1117 struct loc_database_enumerator
* enumerator
, int family
) {
1118 enumerator
->family
= family
;
1123 LOC_EXPORT
int loc_database_enumerator_next_as(
1124 struct loc_database_enumerator
* enumerator
, struct loc_as
** as
) {
1127 // Do not do anything if not in AS mode
1128 if (enumerator
->mode
!= LOC_DB_ENUMERATE_ASES
)
1131 struct loc_database
* db
= enumerator
->db
;
1133 while (enumerator
->as_index
< db
->as_count
) {
1134 // Fetch the next AS
1135 int r
= loc_database_fetch_as(db
, as
, enumerator
->as_index
++);
1139 r
= loc_as_match_string(*as
, enumerator
->string
);
1141 DEBUG(enumerator
->ctx
, "AS%d (%s) matches %s\n",
1142 loc_as_get_number(*as
), loc_as_get_name(*as
), enumerator
->string
);
1153 enumerator
->as_index
= 0;
1155 // We have searched through all of them
1159 static int loc_database_enumerator_stack_push_node(
1160 struct loc_database_enumerator
* e
, off_t offset
, int i
, int depth
) {
1161 // Do not add empty nodes
1165 // Check if there is any space left on the stack
1166 if (e
->network_stack_depth
>= MAX_STACK_DEPTH
) {
1167 ERROR(e
->ctx
, "Maximum stack size reached: %d\n", e
->network_stack_depth
);
1171 // Increase stack size
1172 int s
= ++e
->network_stack_depth
;
1174 DEBUG(e
->ctx
, "Added node %jd to stack (%d)\n", (intmax_t)offset
, depth
);
1176 e
->network_stack
[s
].offset
= offset
;
1177 e
->network_stack
[s
].i
= i
;
1178 e
->network_stack
[s
].depth
= depth
;
1183 static int loc_database_enumerator_match_network(
1184 struct loc_database_enumerator
* enumerator
, struct loc_network
* network
) {
1185 // If family is set, it must match
1186 if (enumerator
->family
&& loc_network_address_family(network
) != enumerator
->family
) {
1187 DEBUG(enumerator
->ctx
, "Filtered network %p because of family not matching\n", network
);
1191 // Match if no filter criteria is configured
1192 if (!enumerator
->countries
&& !enumerator
->asns
&& !enumerator
->flags
)
1195 // Check if the country code matches
1196 if (enumerator
->countries
&& !loc_country_list_empty(enumerator
->countries
)) {
1197 const char* country_code
= loc_network_get_country_code(network
);
1199 if (loc_country_list_contains_code(enumerator
->countries
, country_code
)) {
1200 DEBUG(enumerator
->ctx
, "Matched network %p because of its country code\n", network
);
1205 // Check if the ASN matches
1206 if (enumerator
->asns
&& !loc_as_list_empty(enumerator
->asns
)) {
1207 uint32_t asn
= loc_network_get_asn(network
);
1209 if (loc_as_list_contains_number(enumerator
->asns
, asn
)) {
1210 DEBUG(enumerator
->ctx
, "Matched network %p because of its ASN\n", network
);
1215 // Check if flags match
1216 if (enumerator
->flags
&& loc_network_has_flag(network
, enumerator
->flags
)) {
1217 DEBUG(enumerator
->ctx
, "Matched network %p because of its flags\n", network
);
1225 static int __loc_database_enumerator_next_network(
1226 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
, int filter
) {
1227 // Return top element from the stack
1229 *network
= loc_network_list_pop_first(enumerator
->stack
);
1235 // Return everything if filter isn't enabled, or only return matches
1236 if (!filter
|| loc_database_enumerator_match_network(enumerator
, *network
))
1239 // Throw away anything that doesn't match
1240 loc_network_unref(*network
);
1244 DEBUG(enumerator
->ctx
, "Called with a stack of %u nodes\n",
1245 enumerator
->network_stack_depth
);
1248 while (enumerator
->network_stack_depth
> 0) {
1249 DEBUG(enumerator
->ctx
, "Stack depth: %u\n", enumerator
->network_stack_depth
);
1251 // Get object from top of the stack
1252 struct loc_node_stack
* node
= &enumerator
->network_stack
[enumerator
->network_stack_depth
];
1254 // Remove the node from the stack if we have already visited it
1255 if (enumerator
->networks_visited
[node
->offset
]) {
1256 enumerator
->network_stack_depth
--;
1260 // Mark the bits on the path correctly
1261 loc_address_set_bit(&enumerator
->network_address
,
1262 (node
->depth
> 0) ? node
->depth
- 1 : 0, node
->i
);
1264 DEBUG(enumerator
->ctx
, "Looking at node %jd\n", (intmax_t)node
->offset
);
1265 enumerator
->networks_visited
[node
->offset
]++;
1267 // Pop node from top of the stack
1268 struct loc_database_network_node_v1
* n
=
1269 enumerator
->db
->network_nodes_v1
+ node
->offset
;
1271 // Add edges to stack
1272 int r
= loc_database_enumerator_stack_push_node(enumerator
,
1273 be32toh(n
->one
), 1, node
->depth
+ 1);
1278 r
= loc_database_enumerator_stack_push_node(enumerator
,
1279 be32toh(n
->zero
), 0, node
->depth
+ 1);
1284 // Check if this node is a leaf and has a network object
1285 if (__loc_database_node_is_leaf(n
)) {
1286 off_t network_index
= be32toh(n
->network
);
1288 DEBUG(enumerator
->ctx
, "Node has a network at %jd\n", (intmax_t)network_index
);
1290 // Fetch the network object
1291 r
= loc_database_fetch_network(enumerator
->db
, network
,
1292 &enumerator
->network_address
, node
->depth
, network_index
);
1294 // Break on any errors
1298 // Return all networks when the filter is disabled, or check for match
1299 if (!filter
|| loc_database_enumerator_match_network(enumerator
, *network
))
1302 // Does not seem to be a match, so we cleanup and move on
1303 loc_network_unref(*network
);
1308 // Reached the end of the search
1312 static int __loc_database_enumerator_next_network_flattened(
1313 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
) {
1314 // Fetch the next network
1315 int r
= __loc_database_enumerator_next_network(enumerator
, network
, 1);
1319 // End if we could not read another network
1323 struct loc_network
* subnet
= NULL
;
1325 // Create a list with all subnets
1326 if (!enumerator
->subnets
) {
1327 r
= loc_network_list_new(enumerator
->ctx
, &enumerator
->subnets
);
1332 // Search all subnets from the database
1334 // Fetch the next network in line
1335 r
= __loc_database_enumerator_next_network(enumerator
, &subnet
, 0);
1337 loc_network_unref(subnet
);
1338 loc_network_list_clear(enumerator
->subnets
);
1343 // End if we did not receive another subnet
1347 // Collect all subnets in a list
1348 if (loc_network_is_subnet(*network
, subnet
)) {
1349 r
= loc_network_list_push(enumerator
->subnets
, subnet
);
1351 loc_network_unref(subnet
);
1352 loc_network_list_clear(enumerator
->subnets
);
1357 loc_network_unref(subnet
);
1361 // If this is not a subnet, we push it back onto the stack and break
1362 r
= loc_network_list_push(enumerator
->stack
, subnet
);
1364 loc_network_unref(subnet
);
1365 loc_network_list_clear(enumerator
->subnets
);
1370 loc_network_unref(subnet
);
1374 DEBUG(enumerator
->ctx
, "Found %zu subnet(s)\n",
1375 loc_network_list_size(enumerator
->subnets
));
1377 // We can abort here if the network has no subnets
1378 if (loc_network_list_empty(enumerator
->subnets
)) {
1379 loc_network_list_clear(enumerator
->subnets
);
1384 // If the network has any subnets, we will break it into smaller parts
1385 // without the subnets.
1386 struct loc_network_list
* excluded
= loc_network_exclude_list(*network
, enumerator
->subnets
);
1388 loc_network_list_clear(enumerator
->subnets
);
1392 // Merge subnets onto the stack
1393 r
= loc_network_list_merge(enumerator
->stack
, enumerator
->subnets
);
1395 loc_network_list_clear(enumerator
->subnets
);
1396 loc_network_list_unref(excluded
);
1401 // Push excluded list onto the stack
1402 r
= loc_network_list_merge(enumerator
->stack
, excluded
);
1404 loc_network_list_clear(enumerator
->subnets
);
1405 loc_network_list_unref(excluded
);
1410 loc_network_list_clear(enumerator
->subnets
);
1411 loc_network_list_unref(excluded
);
1413 // Drop the network and restart the whole process again to pick the next network
1414 loc_network_unref(*network
);
1416 return __loc_database_enumerator_next_network_flattened(enumerator
, network
);
1420 This function finds all bogons (i.e. gaps) between the input networks
1422 static int __loc_database_enumerator_next_bogon(
1423 struct loc_database_enumerator
* enumerator
, struct loc_network
** bogon
) {
1426 // Return top element from the stack
1428 *bogon
= loc_network_list_pop_first(enumerator
->stack
);
1438 struct loc_network
* network
= NULL
;
1439 struct in6_addr
* gap_start
= NULL
;
1440 struct in6_addr gap_end
= IN6ADDR_ANY_INIT
;
1443 r
= __loc_database_enumerator_next_network(enumerator
, &network
, 1);
1447 // We have read the last network
1451 const char* country_code
= loc_network_get_country_code(network
);
1454 Skip anything that does not have a country code
1456 Even if a network is part of the routing table, and the database provides
1457 an ASN, this does not mean that this is a legitimate announcement.
1459 if (country_code
&& !*country_code
) {
1460 loc_network_unref(network
);
1464 // Determine the network family
1465 int family
= loc_network_address_family(network
);
1469 gap_start
= &enumerator
->gap6_start
;
1473 gap_start
= &enumerator
->gap4_start
;
1477 ERROR(enumerator
->ctx
, "Unsupported network family %d\n", family
);
1482 const struct in6_addr
* first_address
= loc_network_get_first_address(network
);
1483 const struct in6_addr
* last_address
= loc_network_get_last_address(network
);
1485 // Skip if this network is a subnet of a former one
1486 if (loc_address_cmp(gap_start
, last_address
) >= 0) {
1487 loc_network_unref(network
);
1491 // Search where the gap could end
1492 gap_end
= *first_address
;
1493 loc_address_decrement(&gap_end
);
1496 if (loc_address_cmp(gap_start
, &gap_end
) <= 0) {
1497 r
= loc_network_list_summarize(enumerator
->ctx
,
1498 gap_start
, &gap_end
, &enumerator
->stack
);
1500 loc_network_unref(network
);
1505 // The gap now starts after this network
1506 *gap_start
= *last_address
;
1507 loc_address_increment(gap_start
);
1509 loc_network_unref(network
);
1511 // Try to return something
1512 *bogon
= loc_network_list_pop_first(enumerator
->stack
);
1521 if (!loc_address_all_zeroes(&enumerator
->gap6_start
)) {
1522 r
= loc_address_reset_last(&gap_end
, AF_INET6
);
1526 if (loc_address_cmp(&enumerator
->gap6_start
, &gap_end
) <= 0) {
1527 r
= loc_network_list_summarize(enumerator
->ctx
,
1528 &enumerator
->gap6_start
, &gap_end
, &enumerator
->stack
);
1534 loc_address_reset(&enumerator
->gap6_start
, AF_INET6
);
1537 if (!loc_address_all_zeroes(&enumerator
->gap4_start
)) {
1538 r
= loc_address_reset_last(&gap_end
, AF_INET
);
1542 if (loc_address_cmp(&enumerator
->gap4_start
, &gap_end
) <= 0) {
1543 r
= loc_network_list_summarize(enumerator
->ctx
,
1544 &enumerator
->gap4_start
, &gap_end
, &enumerator
->stack
);
1550 loc_address_reset(&enumerator
->gap4_start
, AF_INET
);
1553 // Try to return something
1554 *bogon
= loc_network_list_pop_first(enumerator
->stack
);
1559 LOC_EXPORT
int loc_database_enumerator_next_network(
1560 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
) {
1561 switch (enumerator
->mode
) {
1562 case LOC_DB_ENUMERATE_NETWORKS
:
1564 if (enumerator
->flatten
)
1565 return __loc_database_enumerator_next_network_flattened(enumerator
, network
);
1567 return __loc_database_enumerator_next_network(enumerator
, network
, 1);
1569 case LOC_DB_ENUMERATE_BOGONS
:
1570 return __loc_database_enumerator_next_bogon(enumerator
, network
);
1577 LOC_EXPORT
int loc_database_enumerator_next_country(
1578 struct loc_database_enumerator
* enumerator
, struct loc_country
** country
) {
1581 // Do not do anything if not in country mode
1582 if (enumerator
->mode
!= LOC_DB_ENUMERATE_COUNTRIES
)
1585 struct loc_database
* db
= enumerator
->db
;
1587 while (enumerator
->country_index
< db
->countries_count
) {
1588 // Fetch the next country
1589 int r
= loc_database_fetch_country(db
, country
, enumerator
->country_index
++);
1593 // We do not filter here, so it always is a match
1598 enumerator
->country_index
= 0;
1600 // We have searched through all of them