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
;
158 ERROR(db
->ctx
, "Unrecognized file type\n");
164 static int loc_database_read_as_section_v1(struct loc_database
* db
,
165 const struct loc_database_header_v1
* header
) {
166 off_t as_offset
= be32toh(header
->as_offset
);
167 size_t as_length
= be32toh(header
->as_length
);
169 DEBUG(db
->ctx
, "Reading AS section from %jd (%zu bytes)\n", (intmax_t)as_offset
, as_length
);
172 db
->as_v1
= mmap(NULL
, as_length
, PROT_READ
,
173 MAP_SHARED
, fileno(db
->f
), as_offset
);
175 if (db
->as_v1
== MAP_FAILED
)
179 db
->as_count
= as_length
/ sizeof(*db
->as_v1
);
181 INFO(db
->ctx
, "Read %zu ASes from the database\n", db
->as_count
);
186 static int loc_database_read_network_nodes_section_v1(struct loc_database
* db
,
187 const struct loc_database_header_v1
* header
) {
188 off_t network_nodes_offset
= be32toh(header
->network_tree_offset
);
189 size_t network_nodes_length
= be32toh(header
->network_tree_length
);
191 DEBUG(db
->ctx
, "Reading network nodes section from %jd (%zu bytes)\n",
192 (intmax_t)network_nodes_offset
, network_nodes_length
);
194 if (network_nodes_length
> 0) {
195 db
->network_nodes_v1
= mmap(NULL
, network_nodes_length
, PROT_READ
,
196 MAP_SHARED
, fileno(db
->f
), network_nodes_offset
);
198 if (db
->network_nodes_v1
== MAP_FAILED
)
202 db
->network_nodes_count
= network_nodes_length
/ sizeof(*db
->network_nodes_v1
);
204 INFO(db
->ctx
, "Read %zu network nodes from the database\n", db
->network_nodes_count
);
209 static int loc_database_read_networks_section_v1(struct loc_database
* db
,
210 const struct loc_database_header_v1
* header
) {
211 off_t networks_offset
= be32toh(header
->network_data_offset
);
212 size_t networks_length
= be32toh(header
->network_data_length
);
214 DEBUG(db
->ctx
, "Reading networks section from %jd (%zu bytes)\n",
215 (intmax_t)networks_offset
, networks_length
);
217 if (networks_length
> 0) {
218 db
->networks_v1
= mmap(NULL
, networks_length
, PROT_READ
,
219 MAP_SHARED
, fileno(db
->f
), networks_offset
);
221 if (db
->networks_v1
== MAP_FAILED
)
225 db
->networks_count
= networks_length
/ sizeof(*db
->networks_v1
);
227 INFO(db
->ctx
, "Read %zu networks from the database\n", db
->networks_count
);
232 static int loc_database_read_countries_section_v1(struct loc_database
* db
,
233 const struct loc_database_header_v1
* header
) {
234 off_t countries_offset
= be32toh(header
->countries_offset
);
235 size_t countries_length
= be32toh(header
->countries_length
);
237 DEBUG(db
->ctx
, "Reading countries section from %jd (%zu bytes)\n",
238 (intmax_t)countries_offset
, countries_length
);
240 if (countries_length
> 0) {
241 db
->countries_v1
= mmap(NULL
, countries_length
, PROT_READ
,
242 MAP_SHARED
, fileno(db
->f
), countries_offset
);
244 if (db
->countries_v1
== MAP_FAILED
)
248 db
->countries_count
= countries_length
/ sizeof(*db
->countries_v1
);
250 INFO(db
->ctx
, "Read %zu countries from the database\n",
251 db
->countries_count
);
256 static int loc_database_read_signature(struct loc_database
* db
,
257 char** dst
, char* src
, size_t length
) {
258 // Check for a plausible signature length
259 if (length
> LOC_SIGNATURE_MAX_LENGTH
) {
260 ERROR(db
->ctx
, "Signature too long: %zu\n", length
);
264 DEBUG(db
->ctx
, "Reading signature of %zu bytes\n", length
);
267 *dst
= malloc(length
);
272 memcpy(*dst
, src
, length
);
277 static int loc_database_read_header_v1(struct loc_database
* db
) {
278 struct loc_database_header_v1 header
;
282 size_t size
= fread(&header
, 1, sizeof(header
), db
->f
);
284 if (size
< sizeof(header
)) {
285 ERROR(db
->ctx
, "Could not read enough data for header\n");
290 db
->created_at
= be64toh(header
.created_at
);
291 db
->vendor
= be32toh(header
.vendor
);
292 db
->description
= be32toh(header
.description
);
293 db
->license
= be32toh(header
.license
);
295 db
->signature1_length
= be16toh(header
.signature1_length
);
296 db
->signature2_length
= be16toh(header
.signature2_length
);
299 if (db
->signature1_length
) {
300 r
= loc_database_read_signature(db
, &db
->signature1
,
301 header
.signature1
, db
->signature1_length
);
306 if (db
->signature2_length
) {
307 r
= loc_database_read_signature(db
, &db
->signature2
,
308 header
.signature2
, db
->signature2_length
);
314 off_t pool_offset
= be32toh(header
.pool_offset
);
315 size_t pool_length
= be32toh(header
.pool_length
);
317 r
= loc_stringpool_open(db
->ctx
, &db
->pool
,
318 db
->f
, pool_length
, pool_offset
);
323 r
= loc_database_read_as_section_v1(db
, &header
);
328 r
= loc_database_read_network_nodes_section_v1(db
, &header
);
333 r
= loc_database_read_networks_section_v1(db
, &header
);
338 r
= loc_database_read_countries_section_v1(db
, &header
);
345 static int loc_database_read_header(struct loc_database
* db
) {
346 DEBUG(db
->ctx
, "Database version is %u\n", db
->version
);
348 switch (db
->version
) {
349 case LOC_DATABASE_VERSION_1
:
350 return loc_database_read_header_v1(db
);
353 ERROR(db
->ctx
, "Incompatible database version: %u\n", db
->version
);
358 static int loc_database_read(struct loc_database
* db
, FILE* f
) {
359 clock_t start
= clock();
363 // Clone file descriptor
366 ERROR(db
->ctx
, "Could not duplicate file descriptor\n");
370 // Reopen the file so that we can keep our own file handle
371 db
->f
= fdopen(fd
, "r");
373 ERROR(db
->ctx
, "Could not re-open database file\n");
377 // Rewind to the start of the file
381 int r
= loc_database_read_magic(db
);
386 r
= loc_database_read_header(db
);
390 clock_t end
= clock();
392 INFO(db
->ctx
, "Opened database in %.4fms\n",
393 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
398 LOC_EXPORT
int loc_database_new(struct loc_ctx
* ctx
, struct loc_database
** database
, FILE* f
) {
399 // Fail on invalid file handle
403 struct loc_database
* db
= calloc(1, sizeof(*db
));
408 db
->ctx
= loc_ref(ctx
);
411 DEBUG(db
->ctx
, "Database object allocated at %p\n", db
);
413 int r
= loc_database_read(db
, f
);
415 loc_database_unref(db
);
424 LOC_EXPORT
struct loc_database
* loc_database_ref(struct loc_database
* db
) {
430 static void loc_database_free(struct loc_database
* db
) {
433 DEBUG(db
->ctx
, "Releasing database %p\n", db
);
437 r
= munmap(db
->as_v1
, db
->as_count
* sizeof(*db
->as_v1
));
439 ERROR(db
->ctx
, "Could not unmap AS section: %m\n");
442 // Remove mapped network sections
443 if (db
->networks_v1
) {
444 r
= munmap(db
->networks_v1
, db
->networks_count
* sizeof(*db
->networks_v1
));
446 ERROR(db
->ctx
, "Could not unmap networks section: %m\n");
449 // Remove mapped network nodes section
450 if (db
->network_nodes_v1
) {
451 r
= munmap(db
->network_nodes_v1
, db
->network_nodes_count
* sizeof(*db
->network_nodes_v1
));
453 ERROR(db
->ctx
, "Could not unmap network nodes section: %m\n");
456 // Remove mapped countries section
457 if (db
->countries_v1
) {
458 r
= munmap(db
->countries_v1
, db
->countries_count
* sizeof(*db
->countries_v1
));
460 ERROR(db
->ctx
, "Could not unmap countries section: %m\n");
464 loc_stringpool_unref(db
->pool
);
468 free(db
->signature1
);
470 free(db
->signature2
);
472 // Close database file
480 LOC_EXPORT
struct loc_database
* loc_database_unref(struct loc_database
* db
) {
481 if (--db
->refcount
> 0)
484 loc_database_free(db
);
488 LOC_EXPORT
int loc_database_verify(struct loc_database
* db
, FILE* f
) {
489 size_t bytes_read
= 0;
491 // Cannot do this when no signature is available
492 if (!db
->signature1
&& !db
->signature2
) {
493 DEBUG(db
->ctx
, "No signature available to verify\n");
497 // Start the stopwatch
498 clock_t start
= clock();
501 EVP_PKEY
* pkey
= PEM_read_PUBKEY(f
, NULL
, NULL
, NULL
);
503 ERROR(db
->ctx
, "Could not parse public key: %s\n",
504 ERR_error_string(ERR_get_error(), NULL
));
511 EVP_MD_CTX
* mdctx
= EVP_MD_CTX_new();
513 // Initialise hash function
514 r
= EVP_DigestVerifyInit(mdctx
, NULL
, NULL
, NULL
, pkey
);
516 ERROR(db
->ctx
, "Error initializing signature validation: %s\n",
517 ERR_error_string(ERR_get_error(), NULL
));
523 // Reset file to start
527 struct loc_database_magic magic
;
528 bytes_read
= fread(&magic
, 1, sizeof(magic
), db
->f
);
529 if (bytes_read
< sizeof(magic
)) {
530 ERROR(db
->ctx
, "Could not read header: %m\n");
535 hexdump(db
->ctx
, &magic
, sizeof(magic
));
537 // Feed magic into the hash
538 r
= EVP_DigestVerifyUpdate(mdctx
, &magic
, sizeof(magic
));
540 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
547 struct loc_database_header_v1 header_v1
;
549 switch (db
->version
) {
550 case LOC_DATABASE_VERSION_1
:
551 bytes_read
= fread(&header_v1
, 1, sizeof(header_v1
), db
->f
);
552 if (bytes_read
< sizeof(header_v1
)) {
553 ERROR(db
->ctx
, "Could not read header\n");
560 memset(header_v1
.signature1
, '\0', sizeof(header_v1
.signature1
));
561 header_v1
.signature1_length
= 0;
562 memset(header_v1
.signature2
, '\0', sizeof(header_v1
.signature2
));
563 header_v1
.signature2_length
= 0;
565 hexdump(db
->ctx
, &header_v1
, sizeof(header_v1
));
567 // Feed header into the hash
568 r
= EVP_DigestVerifyUpdate(mdctx
, &header_v1
, sizeof(header_v1
));
570 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
578 ERROR(db
->ctx
, "Cannot compute hash for database with format %d\n",
584 // Walk through the file in chunks of 64kB
585 char buffer
[64 * 1024];
587 while (!feof(db
->f
)) {
588 bytes_read
= fread(buffer
, 1, sizeof(buffer
), db
->f
);
590 hexdump(db
->ctx
, buffer
, bytes_read
);
592 r
= EVP_DigestVerifyUpdate(mdctx
, buffer
, bytes_read
);
594 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
601 // Check first signature
602 if (db
->signature1
) {
603 hexdump(db
->ctx
, db
->signature1
, db
->signature1_length
);
605 r
= EVP_DigestVerifyFinal(mdctx
,
606 (unsigned char*)db
->signature1
, db
->signature1_length
);
609 DEBUG(db
->ctx
, "The first signature is invalid\n");
612 DEBUG(db
->ctx
, "The first signature is valid\n");
615 ERROR(db
->ctx
, "Error verifying the first signature: %s\n",
616 ERR_error_string(ERR_get_error(), NULL
));
621 // Check second signature only when the first one was invalid
622 if (r
&& db
->signature2
) {
623 hexdump(db
->ctx
, db
->signature2
, db
->signature2_length
);
625 r
= EVP_DigestVerifyFinal(mdctx
,
626 (unsigned char*)db
->signature2
, db
->signature2_length
);
629 DEBUG(db
->ctx
, "The second signature is invalid\n");
632 DEBUG(db
->ctx
, "The second signature is valid\n");
635 ERROR(db
->ctx
, "Error verifying the second signature: %s\n",
636 ERR_error_string(ERR_get_error(), NULL
));
641 clock_t end
= clock();
642 INFO(db
->ctx
, "Signature checked in %.4fms\n",
643 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
647 EVP_MD_CTX_free(mdctx
);
653 LOC_EXPORT
time_t loc_database_created_at(struct loc_database
* db
) {
654 return db
->created_at
;
657 LOC_EXPORT
const char* loc_database_get_vendor(struct loc_database
* db
) {
658 return loc_stringpool_get(db
->pool
, db
->vendor
);
661 LOC_EXPORT
const char* loc_database_get_description(struct loc_database
* db
) {
662 return loc_stringpool_get(db
->pool
, db
->description
);
665 LOC_EXPORT
const char* loc_database_get_license(struct loc_database
* db
) {
666 return loc_stringpool_get(db
->pool
, db
->license
);
669 LOC_EXPORT
size_t loc_database_count_as(struct loc_database
* db
) {
673 // Returns the AS at position pos
674 static int loc_database_fetch_as(struct loc_database
* db
, struct loc_as
** as
, off_t pos
) {
675 if ((size_t)pos
>= db
->as_count
)
678 DEBUG(db
->ctx
, "Fetching AS at position %jd\n", (intmax_t)pos
);
681 switch (db
->version
) {
682 case LOC_DATABASE_VERSION_1
:
683 r
= loc_as_new_from_database_v1(db
->ctx
, db
->pool
, as
, db
->as_v1
+ pos
);
691 DEBUG(db
->ctx
, "Got AS%u\n", loc_as_get_number(*as
));
697 // Performs a binary search to find the AS in the list
698 LOC_EXPORT
int loc_database_get_as(struct loc_database
* db
, struct loc_as
** as
, uint32_t number
) {
700 off_t hi
= db
->as_count
- 1;
704 clock_t start
= clock();
708 off_t i
= (lo
+ hi
) / 2;
710 // Fetch AS in the middle between lo and hi
711 int r
= loc_database_fetch_as(db
, as
, i
);
715 // Check if this is a match
716 uint32_t as_number
= loc_as_get_number(*as
);
717 if (as_number
== number
) {
719 clock_t end
= clock();
721 // Log how fast this has been
722 DEBUG(db
->ctx
, "Found AS%u in %.4fms\n", as_number
,
723 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
729 // If it wasn't, we release the AS and
730 // adjust our search pointers
733 if (as_number
< number
) {
745 // Returns the network at position pos
746 static int loc_database_fetch_network(struct loc_database
* db
, struct loc_network
** network
,
747 struct in6_addr
* address
, unsigned int prefix
, off_t pos
) {
748 if ((size_t)pos
>= db
->networks_count
) {
749 DEBUG(db
->ctx
, "Network ID out of range: %jd/%jd\n",
750 (intmax_t)pos
, (intmax_t)db
->networks_count
);
755 DEBUG(db
->ctx
, "Fetching network at position %jd\n", (intmax_t)pos
);
758 switch (db
->version
) {
759 case LOC_DATABASE_VERSION_1
:
760 r
= loc_network_new_from_database_v1(db
->ctx
, network
,
761 address
, prefix
, db
->networks_v1
+ pos
);
769 DEBUG(db
->ctx
, "Got network %s\n", loc_network_str(*network
));
774 static int __loc_database_node_is_leaf(const struct loc_database_network_node_v1
* node
) {
775 return (node
->network
!= htobe32(0xffffffff));
778 static int __loc_database_lookup_handle_leaf(struct loc_database
* db
, const struct in6_addr
* address
,
779 struct loc_network
** network
, struct in6_addr
* network_address
, unsigned int prefix
,
780 const struct loc_database_network_node_v1
* node
) {
781 off_t network_index
= be32toh(node
->network
);
783 DEBUG(db
->ctx
, "Handling leaf node at %jd (%jd)\n", (intmax_t)(node
- db
->network_nodes_v1
), (intmax_t)network_index
);
786 int r
= loc_database_fetch_network(db
, network
,
787 network_address
, prefix
, network_index
);
789 ERROR(db
->ctx
, "Could not fetch network %jd from database\n", (intmax_t)network_index
);
793 // Check if the given IP address is inside the network
794 if (!loc_network_matches_address(*network
, address
)) {
795 DEBUG(db
->ctx
, "Searched address is not part of the network\n");
797 loc_network_unref(*network
);
802 // A network was found and the IP address matches
806 // Searches for an exact match along the path
807 static int __loc_database_lookup(struct loc_database
* db
, const struct in6_addr
* address
,
808 struct loc_network
** network
, struct in6_addr
* network_address
,
809 const struct loc_database_network_node_v1
* node
, unsigned int level
) {
814 int bit
= loc_address_get_bit(address
, level
);
815 loc_address_set_bit(network_address
, level
, bit
);
818 node_index
= be32toh(node
->zero
);
820 node_index
= be32toh(node
->one
);
822 // If the node index is zero, the tree ends here
823 // and we cannot descend any further
824 if (node_index
> 0) {
826 if ((size_t)node_index
>= db
->network_nodes_count
)
829 // Move on to the next node
830 r
= __loc_database_lookup(db
, address
, network
, network_address
,
831 db
->network_nodes_v1
+ node_index
, level
+ 1);
833 // End here if a result was found
841 DEBUG(db
->ctx
, "No match found below level %u\n", level
);
843 DEBUG(db
->ctx
, "Tree ended at level %u\n", level
);
846 // If this node has a leaf, we will check if it matches
847 if (__loc_database_node_is_leaf(node
)) {
848 r
= __loc_database_lookup_handle_leaf(db
, address
, network
, network_address
, level
, node
);
856 LOC_EXPORT
int loc_database_lookup(struct loc_database
* db
,
857 const struct in6_addr
* address
, struct loc_network
** network
) {
858 struct in6_addr network_address
;
859 memset(&network_address
, 0, sizeof(network_address
));
865 clock_t start
= clock();
868 int r
= __loc_database_lookup(db
, address
, network
, &network_address
,
869 db
->network_nodes_v1
, 0);
872 clock_t end
= clock();
874 // Log how fast this has been
875 DEBUG(db
->ctx
, "Executed network search in %.4fms\n",
876 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
882 LOC_EXPORT
int loc_database_lookup_from_string(struct loc_database
* db
,
883 const char* string
, struct loc_network
** network
) {
884 struct in6_addr address
;
886 int r
= loc_address_parse(&address
, NULL
, string
);
890 return loc_database_lookup(db
, &address
, network
);
893 // Returns the country at position pos
894 static int loc_database_fetch_country(struct loc_database
* db
,
895 struct loc_country
** country
, off_t pos
) {
896 if ((size_t)pos
>= db
->countries_count
)
899 DEBUG(db
->ctx
, "Fetching country at position %jd\n", (intmax_t)pos
);
902 switch (db
->version
) {
903 case LOC_DATABASE_VERSION_1
:
904 r
= loc_country_new_from_database_v1(db
->ctx
, db
->pool
, country
, db
->countries_v1
+ pos
);
912 DEBUG(db
->ctx
, "Got country %s\n", loc_country_get_code(*country
));
918 // Performs a binary search to find the country in the list
919 LOC_EXPORT
int loc_database_get_country(struct loc_database
* db
,
920 struct loc_country
** country
, const char* code
) {
922 off_t hi
= db
->countries_count
- 1;
926 clock_t start
= clock();
930 off_t i
= (lo
+ hi
) / 2;
932 // Fetch country in the middle between lo and hi
933 int r
= loc_database_fetch_country(db
, country
, i
);
937 // Check if this is a match
938 const char* cc
= loc_country_get_code(*country
);
939 int result
= strcmp(code
, cc
);
943 clock_t end
= clock();
945 // Log how fast this has been
946 DEBUG(db
->ctx
, "Found country %s in %.4fms\n", cc
,
947 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
953 // If it wasn't, we release the country and
954 // adjust our search pointers
955 loc_country_unref(*country
);
971 static void loc_database_enumerator_free(struct loc_database_enumerator
* enumerator
) {
972 DEBUG(enumerator
->ctx
, "Releasing database enumerator %p\n", enumerator
);
974 // Release all references
975 loc_database_unref(enumerator
->db
);
976 loc_unref(enumerator
->ctx
);
978 if (enumerator
->string
)
979 free(enumerator
->string
);
981 if (enumerator
->countries
)
982 loc_country_list_unref(enumerator
->countries
);
984 if (enumerator
->asns
)
985 loc_as_list_unref(enumerator
->asns
);
987 // Free network search
988 free(enumerator
->networks_visited
);
990 // Free subnet/bogons stack
991 if (enumerator
->stack
)
992 loc_network_list_unref(enumerator
->stack
);
994 if (enumerator
->subnets
)
995 loc_network_list_unref(enumerator
->subnets
);
1000 LOC_EXPORT
int loc_database_enumerator_new(struct loc_database_enumerator
** enumerator
,
1001 struct loc_database
* db
, enum loc_database_enumerator_mode mode
, int flags
) {
1002 struct loc_database_enumerator
* e
= calloc(1, sizeof(*e
));
1006 // Reference context
1007 e
->ctx
= loc_ref(db
->ctx
);
1008 e
->db
= loc_database_ref(db
);
1013 e
->flatten
= (flags
& LOC_DB_ENUMERATOR_FLAGS_FLATTEN
);
1015 // Initialise graph search
1016 e
->network_stack_depth
= 1;
1017 e
->networks_visited
= calloc(db
->network_nodes_count
, sizeof(*e
->networks_visited
));
1020 int r
= loc_network_list_new(e
->ctx
, &e
->stack
);
1022 loc_database_enumerator_free(e
);
1026 // Initialize bogon search
1027 loc_address_reset(&e
->gap6_start
, AF_INET6
);
1028 loc_address_reset(&e
->gap4_start
, AF_INET
);
1030 DEBUG(e
->ctx
, "Database enumerator object allocated at %p\n", e
);
1036 LOC_EXPORT
struct loc_database_enumerator
* loc_database_enumerator_ref(struct loc_database_enumerator
* enumerator
) {
1037 enumerator
->refcount
++;
1042 LOC_EXPORT
struct loc_database_enumerator
* loc_database_enumerator_unref(struct loc_database_enumerator
* enumerator
) {
1046 if (--enumerator
->refcount
> 0)
1049 loc_database_enumerator_free(enumerator
);
1053 LOC_EXPORT
int loc_database_enumerator_set_string(struct loc_database_enumerator
* enumerator
, const char* string
) {
1054 enumerator
->string
= strdup(string
);
1056 // Make the string lowercase
1057 for (char *p
= enumerator
->string
; *p
; p
++)
1063 LOC_EXPORT
struct loc_country_list
* loc_database_enumerator_get_countries(
1064 struct loc_database_enumerator
* enumerator
) {
1065 if (!enumerator
->countries
)
1068 return loc_country_list_ref(enumerator
->countries
);
1071 LOC_EXPORT
int loc_database_enumerator_set_countries(
1072 struct loc_database_enumerator
* enumerator
, struct loc_country_list
* countries
) {
1073 if (enumerator
->countries
)
1074 loc_country_list_unref(enumerator
->countries
);
1076 enumerator
->countries
= loc_country_list_ref(countries
);
1081 LOC_EXPORT
struct loc_as_list
* loc_database_enumerator_get_asns(
1082 struct loc_database_enumerator
* enumerator
) {
1083 if (!enumerator
->asns
)
1086 return loc_as_list_ref(enumerator
->asns
);
1089 LOC_EXPORT
int loc_database_enumerator_set_asns(
1090 struct loc_database_enumerator
* enumerator
, struct loc_as_list
* asns
) {
1091 if (enumerator
->asns
)
1092 loc_as_list_unref(enumerator
->asns
);
1094 enumerator
->asns
= loc_as_list_ref(asns
);
1099 LOC_EXPORT
int loc_database_enumerator_set_flag(
1100 struct loc_database_enumerator
* enumerator
, enum loc_network_flags flag
) {
1101 enumerator
->flags
|= flag
;
1106 LOC_EXPORT
int loc_database_enumerator_set_family(
1107 struct loc_database_enumerator
* enumerator
, int family
) {
1108 enumerator
->family
= family
;
1113 LOC_EXPORT
int loc_database_enumerator_next_as(
1114 struct loc_database_enumerator
* enumerator
, struct loc_as
** as
) {
1117 // Do not do anything if not in AS mode
1118 if (enumerator
->mode
!= LOC_DB_ENUMERATE_ASES
)
1121 struct loc_database
* db
= enumerator
->db
;
1123 while (enumerator
->as_index
< db
->as_count
) {
1124 // Fetch the next AS
1125 int r
= loc_database_fetch_as(db
, as
, enumerator
->as_index
++);
1129 r
= loc_as_match_string(*as
, enumerator
->string
);
1131 DEBUG(enumerator
->ctx
, "AS%d (%s) matches %s\n",
1132 loc_as_get_number(*as
), loc_as_get_name(*as
), enumerator
->string
);
1143 enumerator
->as_index
= 0;
1145 // We have searched through all of them
1149 static int loc_database_enumerator_stack_push_node(
1150 struct loc_database_enumerator
* e
, off_t offset
, int i
, int depth
) {
1151 // Do not add empty nodes
1155 // Check if there is any space left on the stack
1156 if (e
->network_stack_depth
>= MAX_STACK_DEPTH
) {
1157 ERROR(e
->ctx
, "Maximum stack size reached: %d\n", e
->network_stack_depth
);
1161 // Increase stack size
1162 int s
= ++e
->network_stack_depth
;
1164 DEBUG(e
->ctx
, "Added node %jd to stack (%d)\n", (intmax_t)offset
, depth
);
1166 e
->network_stack
[s
].offset
= offset
;
1167 e
->network_stack
[s
].i
= i
;
1168 e
->network_stack
[s
].depth
= depth
;
1173 static int loc_database_enumerator_match_network(
1174 struct loc_database_enumerator
* enumerator
, struct loc_network
* network
) {
1175 // If family is set, it must match
1176 if (enumerator
->family
&& loc_network_address_family(network
) != enumerator
->family
) {
1177 DEBUG(enumerator
->ctx
, "Filtered network %p because of family not matching\n", network
);
1181 // Match if no filter criteria is configured
1182 if (!enumerator
->countries
&& !enumerator
->asns
&& !enumerator
->flags
)
1185 // Check if the country code matches
1186 if (enumerator
->countries
&& !loc_country_list_empty(enumerator
->countries
)) {
1187 const char* country_code
= loc_network_get_country_code(network
);
1189 if (loc_country_list_contains_code(enumerator
->countries
, country_code
)) {
1190 DEBUG(enumerator
->ctx
, "Matched network %p because of its country code\n", network
);
1195 // Check if the ASN matches
1196 if (enumerator
->asns
&& !loc_as_list_empty(enumerator
->asns
)) {
1197 uint32_t asn
= loc_network_get_asn(network
);
1199 if (loc_as_list_contains_number(enumerator
->asns
, asn
)) {
1200 DEBUG(enumerator
->ctx
, "Matched network %p because of its ASN\n", network
);
1205 // Check if flags match
1206 if (enumerator
->flags
&& loc_network_has_flag(network
, enumerator
->flags
)) {
1207 DEBUG(enumerator
->ctx
, "Matched network %p because of its flags\n", network
);
1215 static int __loc_database_enumerator_next_network(
1216 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
, int filter
) {
1217 // Return top element from the stack
1219 *network
= loc_network_list_pop_first(enumerator
->stack
);
1225 // Return everything if filter isn't enabled, or only return matches
1226 if (!filter
|| loc_database_enumerator_match_network(enumerator
, *network
))
1229 // Throw away anything that doesn't match
1230 loc_network_unref(*network
);
1234 DEBUG(enumerator
->ctx
, "Called with a stack of %u nodes\n",
1235 enumerator
->network_stack_depth
);
1238 while (enumerator
->network_stack_depth
> 0) {
1239 DEBUG(enumerator
->ctx
, "Stack depth: %u\n", enumerator
->network_stack_depth
);
1241 // Get object from top of the stack
1242 struct loc_node_stack
* node
= &enumerator
->network_stack
[enumerator
->network_stack_depth
];
1244 // Remove the node from the stack if we have already visited it
1245 if (enumerator
->networks_visited
[node
->offset
]) {
1246 enumerator
->network_stack_depth
--;
1250 // Mark the bits on the path correctly
1251 loc_address_set_bit(&enumerator
->network_address
,
1252 (node
->depth
> 0) ? node
->depth
- 1 : 0, node
->i
);
1254 DEBUG(enumerator
->ctx
, "Looking at node %jd\n", (intmax_t)node
->offset
);
1255 enumerator
->networks_visited
[node
->offset
]++;
1257 // Pop node from top of the stack
1258 struct loc_database_network_node_v1
* n
=
1259 enumerator
->db
->network_nodes_v1
+ node
->offset
;
1261 // Add edges to stack
1262 int r
= loc_database_enumerator_stack_push_node(enumerator
,
1263 be32toh(n
->one
), 1, node
->depth
+ 1);
1268 r
= loc_database_enumerator_stack_push_node(enumerator
,
1269 be32toh(n
->zero
), 0, node
->depth
+ 1);
1274 // Check if this node is a leaf and has a network object
1275 if (__loc_database_node_is_leaf(n
)) {
1276 off_t network_index
= be32toh(n
->network
);
1278 DEBUG(enumerator
->ctx
, "Node has a network at %jd\n", (intmax_t)network_index
);
1280 // Fetch the network object
1281 r
= loc_database_fetch_network(enumerator
->db
, network
,
1282 &enumerator
->network_address
, node
->depth
, network_index
);
1284 // Break on any errors
1288 // Return all networks when the filter is disabled, or check for match
1289 if (!filter
|| loc_database_enumerator_match_network(enumerator
, *network
))
1292 // Does not seem to be a match, so we cleanup and move on
1293 loc_network_unref(*network
);
1298 // Reached the end of the search
1302 static int __loc_database_enumerator_next_network_flattened(
1303 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
) {
1304 // Fetch the next network
1305 int r
= __loc_database_enumerator_next_network(enumerator
, network
, 1);
1309 // End if we could not read another network
1313 struct loc_network
* subnet
= NULL
;
1315 // Create a list with all subnets
1316 if (!enumerator
->subnets
) {
1317 r
= loc_network_list_new(enumerator
->ctx
, &enumerator
->subnets
);
1322 // Search all subnets from the database
1324 // Fetch the next network in line
1325 r
= __loc_database_enumerator_next_network(enumerator
, &subnet
, 0);
1327 loc_network_unref(subnet
);
1328 loc_network_list_clear(enumerator
->subnets
);
1333 // End if we did not receive another subnet
1337 // Collect all subnets in a list
1338 if (loc_network_is_subnet(*network
, subnet
)) {
1339 r
= loc_network_list_push(enumerator
->subnets
, subnet
);
1341 loc_network_unref(subnet
);
1342 loc_network_list_clear(enumerator
->subnets
);
1347 loc_network_unref(subnet
);
1351 // If this is not a subnet, we push it back onto the stack and break
1352 r
= loc_network_list_push(enumerator
->stack
, subnet
);
1354 loc_network_unref(subnet
);
1355 loc_network_list_clear(enumerator
->subnets
);
1360 loc_network_unref(subnet
);
1364 DEBUG(enumerator
->ctx
, "Found %zu subnet(s)\n",
1365 loc_network_list_size(enumerator
->subnets
));
1367 // We can abort here if the network has no subnets
1368 if (loc_network_list_empty(enumerator
->subnets
)) {
1369 loc_network_list_clear(enumerator
->subnets
);
1374 // If the network has any subnets, we will break it into smaller parts
1375 // without the subnets.
1376 struct loc_network_list
* excluded
= loc_network_exclude_list(*network
, enumerator
->subnets
);
1378 loc_network_list_clear(enumerator
->subnets
);
1382 // Merge subnets onto the stack
1383 r
= loc_network_list_merge(enumerator
->stack
, enumerator
->subnets
);
1385 loc_network_list_clear(enumerator
->subnets
);
1386 loc_network_list_unref(excluded
);
1391 // Push excluded list onto the stack
1392 r
= loc_network_list_merge(enumerator
->stack
, excluded
);
1394 loc_network_list_clear(enumerator
->subnets
);
1395 loc_network_list_unref(excluded
);
1400 loc_network_list_clear(enumerator
->subnets
);
1401 loc_network_list_unref(excluded
);
1403 // Drop the network and restart the whole process again to pick the next network
1404 loc_network_unref(*network
);
1406 return __loc_database_enumerator_next_network_flattened(enumerator
, network
);
1410 This function finds all bogons (i.e. gaps) between the input networks
1412 static int __loc_database_enumerator_next_bogon(
1413 struct loc_database_enumerator
* enumerator
, struct loc_network
** bogon
) {
1416 // Return top element from the stack
1418 *bogon
= loc_network_list_pop_first(enumerator
->stack
);
1428 struct loc_network
* network
= NULL
;
1429 struct in6_addr
* gap_start
= NULL
;
1430 struct in6_addr gap_end
= IN6ADDR_ANY_INIT
;
1433 r
= __loc_database_enumerator_next_network(enumerator
, &network
, 1);
1437 // We have read the last network
1441 const char* country_code
= loc_network_get_country_code(network
);
1444 Skip anything that does not have a country code
1446 Even if a network is part of the routing table, and the database provides
1447 an ASN, this does not mean that this is a legitimate announcement.
1449 if (country_code
&& !*country_code
) {
1450 loc_network_unref(network
);
1454 // Determine the network family
1455 int family
= loc_network_address_family(network
);
1459 gap_start
= &enumerator
->gap6_start
;
1463 gap_start
= &enumerator
->gap4_start
;
1467 ERROR(enumerator
->ctx
, "Unsupported network family %d\n", family
);
1472 const struct in6_addr
* first_address
= loc_network_get_first_address(network
);
1473 const struct in6_addr
* last_address
= loc_network_get_last_address(network
);
1475 // Skip if this network is a subnet of a former one
1476 if (loc_address_cmp(gap_start
, last_address
) >= 0) {
1477 loc_network_unref(network
);
1481 // Search where the gap could end
1482 gap_end
= *first_address
;
1483 loc_address_decrement(&gap_end
);
1486 if (loc_address_cmp(gap_start
, &gap_end
) <= 0) {
1487 r
= loc_network_list_summarize(enumerator
->ctx
,
1488 gap_start
, &gap_end
, &enumerator
->stack
);
1490 loc_network_unref(network
);
1495 // The gap now starts after this network
1496 *gap_start
= *last_address
;
1497 loc_address_increment(gap_start
);
1499 loc_network_unref(network
);
1501 // Try to return something
1502 *bogon
= loc_network_list_pop_first(enumerator
->stack
);
1511 if (!loc_address_all_zeroes(&enumerator
->gap6_start
)) {
1512 r
= loc_address_reset_last(&gap_end
, AF_INET6
);
1516 if (loc_address_cmp(&enumerator
->gap6_start
, &gap_end
) <= 0) {
1517 r
= loc_network_list_summarize(enumerator
->ctx
,
1518 &enumerator
->gap6_start
, &gap_end
, &enumerator
->stack
);
1524 loc_address_reset(&enumerator
->gap6_start
, AF_INET6
);
1527 if (!loc_address_all_zeroes(&enumerator
->gap4_start
)) {
1528 r
= loc_address_reset_last(&gap_end
, AF_INET
);
1532 if (loc_address_cmp(&enumerator
->gap4_start
, &gap_end
) <= 0) {
1533 r
= loc_network_list_summarize(enumerator
->ctx
,
1534 &enumerator
->gap4_start
, &gap_end
, &enumerator
->stack
);
1540 loc_address_reset(&enumerator
->gap4_start
, AF_INET
);
1543 // Try to return something
1544 *bogon
= loc_network_list_pop_first(enumerator
->stack
);
1549 LOC_EXPORT
int loc_database_enumerator_next_network(
1550 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
) {
1551 switch (enumerator
->mode
) {
1552 case LOC_DB_ENUMERATE_NETWORKS
:
1554 if (enumerator
->flatten
)
1555 return __loc_database_enumerator_next_network_flattened(enumerator
, network
);
1557 return __loc_database_enumerator_next_network(enumerator
, network
, 1);
1559 case LOC_DB_ENUMERATE_BOGONS
:
1560 return __loc_database_enumerator_next_bogon(enumerator
, network
);
1567 LOC_EXPORT
int loc_database_enumerator_next_country(
1568 struct loc_database_enumerator
* enumerator
, struct loc_country
** country
) {
1571 // Do not do anything if not in country mode
1572 if (enumerator
->mode
!= LOC_DB_ENUMERATE_COUNTRIES
)
1575 struct loc_database
* db
= enumerator
->db
;
1577 while (enumerator
->country_index
< db
->countries_count
) {
1578 // Fetch the next country
1579 int r
= loc_database_fetch_country(db
, country
, enumerator
->country_index
++);
1583 // We do not filter here, so it always is a match
1588 enumerator
->country_index
= 0;
1590 // We have searched through all of them