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>
53 struct loc_database_objects
{
66 enum loc_database_version version
;
74 size_t signature1_length
;
76 size_t signature2_length
;
78 // Data mapped into memory
82 struct loc_stringpool
* pool
;
84 // ASes in the database
85 struct loc_database_objects as_objects
;
88 struct loc_database_objects network_node_objects
;
91 struct loc_database_objects network_objects
;
94 struct loc_database_objects country_objects
;
97 #define MAX_STACK_DEPTH 256
99 struct loc_node_stack
{
101 int i
; // Is this node 0 or 1?
105 struct loc_database_enumerator
{
107 struct loc_database
* db
;
108 enum loc_database_enumerator_mode mode
;
113 struct loc_country_list
* countries
;
114 struct loc_as_list
* asns
;
115 enum loc_network_flags flags
;
121 // Index of the AS we are looking at
122 unsigned int as_index
;
124 // Index of the country we are looking at
125 unsigned int country_index
;
128 struct in6_addr network_address
;
129 struct loc_node_stack network_stack
[MAX_STACK_DEPTH
];
130 int network_stack_depth
;
131 unsigned int* networks_visited
;
133 // For subnet search and bogons
134 struct loc_network_list
* stack
;
135 struct loc_network_list
* subnets
;
138 struct in6_addr gap6_start
;
139 struct in6_addr gap4_start
;
142 #define loc_database_read_object(db, buffer, objects, pos) \
143 __loc_database_read_object(db, buffer, sizeof(*buffer), objects, pos)
146 Reads an object into memory (used when mmap() isn't available)
148 static void* __loc_database_read_object(struct loc_database
* db
, void* buffer
,
149 const size_t length
, const struct loc_database_objects
* objects
, const off_t pos
) {
151 const off_t offset
= pos
* length
;
153 // Map the object first if possible
155 return (uint8_t*)objects
->p
+ offset
;
157 // Otherwise fall back and read the object into the buffer
158 const int fd
= fileno(db
->f
);
161 ssize_t bytes_read
= pread(fd
, buffer
, length
, objects
->offset
+ offset
);
163 // Check if we could read what we wanted
164 if (bytes_read
< (ssize_t
)length
) {
165 ERROR(db
->ctx
, "Error reading object from database: %m\n");
173 static int loc_database_version_supported(struct loc_database
* db
, uint8_t version
) {
175 // Supported versions
176 case LOC_DATABASE_VERSION_1
:
180 ERROR(db
->ctx
, "Database version %d is not supported\n", version
);
186 static int loc_database_check_magic(struct loc_database
* db
) {
187 struct loc_database_magic magic
;
190 size_t bytes_read
= fread(&magic
, 1, sizeof(magic
), db
->f
);
192 // Check if we have been able to read enough data
193 if (bytes_read
< sizeof(magic
)) {
194 ERROR(db
->ctx
, "Could not read enough data to validate magic bytes\n");
195 DEBUG(db
->ctx
, "Read %zu bytes, but needed %zu\n", bytes_read
, sizeof(magic
));
199 // Compare magic bytes
200 if (memcmp(magic
.magic
, LOC_DATABASE_MAGIC
, sizeof(magic
.magic
)) == 0) {
201 DEBUG(db
->ctx
, "Magic value matches\n");
203 // Do we support this version?
204 if (!loc_database_version_supported(db
, magic
.version
))
208 db
->version
= magic
.version
;
214 ERROR(db
->ctx
, "Unrecognized file type\n");
222 Maps the entire database into memory
224 static int loc_database_mmap(struct loc_database
* db
) {
225 int fd
= fileno(db
->f
);
227 // Determine the length of the database
228 db
->length
= lseek(fd
, 0, SEEK_END
);
229 if (db
->length
< 0) {
230 ERROR(db
->ctx
, "Could not determine the length of the database: %m\n");
237 db
->data
= mmap(NULL
, db
->length
, PROT_READ
, MAP_SHARED
, fd
, 0);
238 if (db
->data
== MAP_FAILED
) {
239 ERROR(db
->ctx
, "Could not map the database: %m\n");
244 DEBUG(db
->ctx
, "Mapped database of %zu byte(s) at %p\n", db
->length
, db
->data
);
250 Maps arbitrary objects from the database into memory.
252 static int loc_database_map_objects(struct loc_database
* db
,
253 struct loc_database_objects
* objects
, const size_t size
,
254 off_t offset
, size_t length
) {
258 objects
->offset
= offset
;
259 objects
->length
= length
;
260 objects
->count
= objects
->length
/ size
;
262 // End if there is nothing to map
263 if (!objects
->length
)
266 DEBUG(db
->ctx
, "Mapping %zu object(s) from %jd (%zu bytes)\n",
267 objects
->count
, (intmax_t)objects
->offset
, objects
->length
);
269 // mmap() objects into memory
270 void* p
= mmap(NULL
, objects
->length
, PROT_READ
, MAP_PRIVATE
,
271 fileno(db
->f
), objects
->offset
);
273 if (p
== MAP_FAILED
) {
274 // Ignore if the database wasn't page aligned for this architecture
275 // and fall back to use pread().
276 if (errno
== EINVAL
) {
277 DEBUG(db
->ctx
, "Falling back to pread()\n");
281 ERROR(db
->ctx
, "mmap() failed: %m\n");
291 static int loc_database_unmap_objects(struct loc_database
* db
,
292 struct loc_database_objects
* objects
) {
295 // Nothing to do if nothing was mapped
299 // Call munmap() to free everything
300 r
= munmap(objects
->p
, objects
->length
);
302 ERROR(db
->ctx
, "Could not unmap objects: %m\n");
309 static int loc_database_read_signature(struct loc_database
* db
,
310 char** dst
, char* src
, size_t length
) {
311 // Check for a plausible signature length
312 if (length
> LOC_SIGNATURE_MAX_LENGTH
) {
313 ERROR(db
->ctx
, "Signature too long: %zu\n", length
);
317 DEBUG(db
->ctx
, "Reading signature of %zu bytes\n", length
);
320 *dst
= malloc(length
);
325 memcpy(*dst
, src
, length
);
330 static int loc_database_read_header_v1(struct loc_database
* db
) {
331 struct loc_database_header_v1 header
;
335 size_t size
= pread(fileno(db
->f
), &header
, sizeof(header
), sizeof(struct loc_database_magic
));
337 if (size
< sizeof(header
)) {
338 ERROR(db
->ctx
, "Could not read enough data for header\n");
344 db
->created_at
= be64toh(header
.created_at
);
345 db
->vendor
= be32toh(header
.vendor
);
346 db
->description
= be32toh(header
.description
);
347 db
->license
= be32toh(header
.license
);
349 db
->signature1_length
= be16toh(header
.signature1_length
);
350 db
->signature2_length
= be16toh(header
.signature2_length
);
353 if (db
->signature1_length
) {
354 r
= loc_database_read_signature(db
, &db
->signature1
,
355 header
.signature1
, db
->signature1_length
);
360 if (db
->signature2_length
) {
361 r
= loc_database_read_signature(db
, &db
->signature2
,
362 header
.signature2
, db
->signature2_length
);
367 // Open the stringpool
368 r
= loc_stringpool_open(db
->ctx
, &db
->pool
, db
->f
,
369 be32toh(header
.pool_length
), be32toh(header
.pool_offset
));
374 r
= loc_database_map_objects(db
, &db
->as_objects
,
375 sizeof(struct loc_database_as_v1
),
376 be32toh(header
.as_offset
),
377 be32toh(header
.as_length
));
382 r
= loc_database_map_objects(db
, &db
->network_node_objects
,
383 sizeof(struct loc_database_network_node_v1
),
384 be32toh(header
.network_tree_offset
),
385 be32toh(header
.network_tree_length
));
390 r
= loc_database_map_objects(db
, &db
->network_objects
,
391 sizeof(struct loc_database_network_v1
),
392 be32toh(header
.network_data_offset
),
393 be32toh(header
.network_data_length
));
398 r
= loc_database_map_objects(db
, &db
->country_objects
,
399 sizeof(struct loc_database_country_v1
),
400 be32toh(header
.countries_offset
),
401 be32toh(header
.countries_length
));
408 static int loc_database_read_header(struct loc_database
* db
) {
409 DEBUG(db
->ctx
, "Database version is %u\n", db
->version
);
411 switch (db
->version
) {
412 case LOC_DATABASE_VERSION_1
:
413 return loc_database_read_header_v1(db
);
416 ERROR(db
->ctx
, "Incompatible database version: %u\n", db
->version
);
421 static int loc_database_clone_handle(struct loc_database
* db
, FILE* f
) {
422 // Fetch the FD of the original handle
425 // Clone file descriptor
428 ERROR(db
->ctx
, "Could not duplicate file descriptor\n");
432 // Reopen the file so that we can keep our own file handle
433 db
->f
= fdopen(fd
, "r");
435 ERROR(db
->ctx
, "Could not re-open database file\n");
439 // Rewind to the start of the file
445 static int loc_database_open(struct loc_database
* db
, FILE* f
) {
448 clock_t start
= clock();
450 // Clone the file handle
451 r
= loc_database_clone_handle(db
, f
);
456 r
= loc_database_check_magic(db
);
460 // Map the database into memory
461 r
= loc_database_mmap(db
);
466 r
= loc_database_read_header(db
);
470 clock_t end
= clock();
472 INFO(db
->ctx
, "Opened database in %.4fms\n",
473 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
478 static void loc_database_free(struct loc_database
* db
) {
481 DEBUG(db
->ctx
, "Releasing database %p\n", db
);
483 // Unmap the entire database
485 r
= munmap(db
->data
, db
->length
);
487 ERROR(db
->ctx
, "Could not unmap the database: %m\n");
491 loc_database_unmap_objects(db
, &db
->as_objects
);
493 // Remove mapped network sections
494 loc_database_unmap_objects(db
, &db
->network_objects
);
496 // Remove mapped network nodes section
497 loc_database_unmap_objects(db
, &db
->network_node_objects
);
499 // Remove mapped countries section
500 loc_database_unmap_objects(db
, &db
->country_objects
);
502 // Free the stringpool
504 loc_stringpool_unref(db
->pool
);
508 free(db
->signature1
);
510 free(db
->signature2
);
512 // Close database file
520 LOC_EXPORT
int loc_database_new(struct loc_ctx
* ctx
, struct loc_database
** database
, FILE* f
) {
521 struct loc_database
* db
= NULL
;
524 // Fail on invalid file handle
530 // Allocate the database object
531 db
= calloc(1, sizeof(*db
));
536 db
->ctx
= loc_ref(ctx
);
539 DEBUG(db
->ctx
, "Database object allocated at %p\n", db
);
541 // Try to open the database
542 r
= loc_database_open(db
, f
);
551 loc_database_free(db
);
556 LOC_EXPORT
struct loc_database
* loc_database_ref(struct loc_database
* db
) {
562 LOC_EXPORT
struct loc_database
* loc_database_unref(struct loc_database
* db
) {
563 if (--db
->refcount
> 0)
566 loc_database_free(db
);
570 LOC_EXPORT
int loc_database_verify(struct loc_database
* db
, FILE* f
) {
571 size_t bytes_read
= 0;
573 // Cannot do this when no signature is available
574 if (!db
->signature1
&& !db
->signature2
) {
575 DEBUG(db
->ctx
, "No signature available to verify\n");
579 // Start the stopwatch
580 clock_t start
= clock();
583 EVP_PKEY
* pkey
= PEM_read_PUBKEY(f
, NULL
, NULL
, NULL
);
585 ERROR(db
->ctx
, "Could not parse public key: %s\n",
586 ERR_error_string(ERR_get_error(), NULL
));
593 EVP_MD_CTX
* mdctx
= EVP_MD_CTX_new();
595 // Initialise hash function
596 r
= EVP_DigestVerifyInit(mdctx
, NULL
, NULL
, NULL
, pkey
);
598 ERROR(db
->ctx
, "Error initializing signature validation: %s\n",
599 ERR_error_string(ERR_get_error(), NULL
));
605 // Reset file to start
609 struct loc_database_magic magic
;
610 bytes_read
= fread(&magic
, 1, sizeof(magic
), db
->f
);
611 if (bytes_read
< sizeof(magic
)) {
612 ERROR(db
->ctx
, "Could not read header: %m\n");
617 hexdump(db
->ctx
, &magic
, sizeof(magic
));
619 // Feed magic into the hash
620 r
= EVP_DigestVerifyUpdate(mdctx
, &magic
, sizeof(magic
));
622 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
629 struct loc_database_header_v1 header_v1
;
631 switch (db
->version
) {
632 case LOC_DATABASE_VERSION_1
:
633 bytes_read
= fread(&header_v1
, 1, sizeof(header_v1
), db
->f
);
634 if (bytes_read
< sizeof(header_v1
)) {
635 ERROR(db
->ctx
, "Could not read header\n");
642 memset(header_v1
.signature1
, '\0', sizeof(header_v1
.signature1
));
643 header_v1
.signature1_length
= 0;
644 memset(header_v1
.signature2
, '\0', sizeof(header_v1
.signature2
));
645 header_v1
.signature2_length
= 0;
647 hexdump(db
->ctx
, &header_v1
, sizeof(header_v1
));
649 // Feed header into the hash
650 r
= EVP_DigestVerifyUpdate(mdctx
, &header_v1
, sizeof(header_v1
));
652 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
660 ERROR(db
->ctx
, "Cannot compute hash for database with format %d\n",
666 // Walk through the file in chunks of 64kB
667 char buffer
[64 * 1024];
669 while (!feof(db
->f
)) {
670 bytes_read
= fread(buffer
, 1, sizeof(buffer
), db
->f
);
672 hexdump(db
->ctx
, buffer
, bytes_read
);
674 r
= EVP_DigestVerifyUpdate(mdctx
, buffer
, bytes_read
);
676 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
683 // Check first signature
684 if (db
->signature1
) {
685 hexdump(db
->ctx
, db
->signature1
, db
->signature1_length
);
687 r
= EVP_DigestVerifyFinal(mdctx
,
688 (unsigned char*)db
->signature1
, db
->signature1_length
);
691 DEBUG(db
->ctx
, "The first signature is invalid\n");
694 DEBUG(db
->ctx
, "The first signature is valid\n");
697 ERROR(db
->ctx
, "Error verifying the first signature: %s\n",
698 ERR_error_string(ERR_get_error(), NULL
));
703 // Check second signature only when the first one was invalid
704 if (r
&& db
->signature2
) {
705 hexdump(db
->ctx
, db
->signature2
, db
->signature2_length
);
707 r
= EVP_DigestVerifyFinal(mdctx
,
708 (unsigned char*)db
->signature2
, db
->signature2_length
);
711 DEBUG(db
->ctx
, "The second signature is invalid\n");
714 DEBUG(db
->ctx
, "The second signature is valid\n");
717 ERROR(db
->ctx
, "Error verifying the second signature: %s\n",
718 ERR_error_string(ERR_get_error(), NULL
));
723 clock_t end
= clock();
724 INFO(db
->ctx
, "Signature checked in %.4fms\n",
725 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
729 EVP_MD_CTX_free(mdctx
);
735 LOC_EXPORT
time_t loc_database_created_at(struct loc_database
* db
) {
736 return db
->created_at
;
739 LOC_EXPORT
const char* loc_database_get_vendor(struct loc_database
* db
) {
740 return loc_stringpool_get(db
->pool
, db
->vendor
);
743 LOC_EXPORT
const char* loc_database_get_description(struct loc_database
* db
) {
744 return loc_stringpool_get(db
->pool
, db
->description
);
747 LOC_EXPORT
const char* loc_database_get_license(struct loc_database
* db
) {
748 return loc_stringpool_get(db
->pool
, db
->license
);
751 LOC_EXPORT
size_t loc_database_count_as(struct loc_database
* db
) {
752 return db
->as_objects
.count
;
755 // Returns the AS at position pos
756 static int loc_database_fetch_as(struct loc_database
* db
, struct loc_as
** as
, off_t pos
) {
757 struct loc_database_as_v1 as_v1
;
758 struct loc_database_as_v1
* p_v1
;
761 if ((size_t)pos
>= db
->as_objects
.count
) {
766 DEBUG(db
->ctx
, "Fetching AS at position %jd\n", (intmax_t)pos
);
768 switch (db
->version
) {
769 case LOC_DATABASE_VERSION_1
:
771 p_v1
= loc_database_read_object(db
, &as_v1
, &db
->as_objects
, pos
);
775 r
= loc_as_new_from_database_v1(db
->ctx
, db
->pool
, as
, p_v1
);
784 DEBUG(db
->ctx
, "Got AS%u\n", loc_as_get_number(*as
));
789 // Performs a binary search to find the AS in the list
790 LOC_EXPORT
int loc_database_get_as(struct loc_database
* db
, struct loc_as
** as
, uint32_t number
) {
792 off_t hi
= db
->as_objects
.count
- 1;
796 clock_t start
= clock();
800 off_t i
= (lo
+ hi
) / 2;
802 // Fetch AS in the middle between lo and hi
803 int r
= loc_database_fetch_as(db
, as
, i
);
807 // Check if this is a match
808 uint32_t as_number
= loc_as_get_number(*as
);
809 if (as_number
== number
) {
811 clock_t end
= clock();
813 // Log how fast this has been
814 DEBUG(db
->ctx
, "Found AS%u in %.4fms\n", as_number
,
815 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
821 // If it wasn't, we release the AS and
822 // adjust our search pointers
825 if (as_number
< number
) {
837 // Returns the network at position pos
838 static int loc_database_fetch_network(struct loc_database
* db
, struct loc_network
** network
,
839 struct in6_addr
* address
, unsigned int prefix
, off_t pos
) {
840 struct loc_database_network_v1 network_v1
;
841 struct loc_database_network_v1
* p_v1
;
844 if ((size_t)pos
>= db
->network_objects
.count
) {
845 DEBUG(db
->ctx
, "Network ID out of range: %jd/%jd\n",
846 (intmax_t)pos
, (intmax_t)db
->network_objects
.count
);
851 DEBUG(db
->ctx
, "Fetching network at position %jd\n", (intmax_t)pos
);
853 switch (db
->version
) {
854 case LOC_DATABASE_VERSION_1
:
856 p_v1
= loc_database_read_object(db
, &network_v1
, &db
->network_objects
, pos
);
860 r
= loc_network_new_from_database_v1(db
->ctx
, network
, address
, prefix
, p_v1
);
869 DEBUG(db
->ctx
, "Got network %s\n", loc_network_str(*network
));
874 static int __loc_database_node_is_leaf(const struct loc_database_network_node_v1
* node
) {
875 return (node
->network
!= htobe32(0xffffffff));
878 static int __loc_database_lookup_handle_leaf(struct loc_database
* db
, const struct in6_addr
* address
,
879 struct loc_network
** network
, struct in6_addr
* network_address
, unsigned int prefix
,
880 const struct loc_database_network_node_v1
* node
) {
881 off_t network_index
= be32toh(node
->network
);
883 DEBUG(db
->ctx
, "Handling leaf node at %jd\n", (intmax_t)network_index
);
886 int r
= loc_database_fetch_network(db
, network
, network_address
, prefix
, network_index
);
888 ERROR(db
->ctx
, "Could not fetch network %jd from database: %m\n",
889 (intmax_t)network_index
);
893 // Check if the given IP address is inside the network
894 if (!loc_network_matches_address(*network
, address
)) {
895 DEBUG(db
->ctx
, "Searched address is not part of the network\n");
897 loc_network_unref(*network
);
902 // A network was found and the IP address matches
906 // Searches for an exact match along the path
907 static int __loc_database_lookup(struct loc_database
* db
, const struct in6_addr
* address
,
908 struct loc_network
** network
, struct in6_addr
* network_address
,
909 off_t node_index
, unsigned int level
) {
910 struct loc_database_network_node_v1 node_v1
;
911 struct loc_database_network_node_v1
* p_v1
;
915 // Fetch the next node
916 p_v1
= loc_database_read_object(db
, &node_v1
, &db
->network_node_objects
, node_index
);
921 int bit
= loc_address_get_bit(address
, level
);
922 loc_address_set_bit(network_address
, level
, bit
);
925 node_index
= be32toh(p_v1
->zero
);
927 node_index
= be32toh(p_v1
->one
);
929 // If the node index is zero, the tree ends here
930 // and we cannot descend any further
931 if (node_index
> 0) {
933 if ((size_t)node_index
>= db
->network_node_objects
.count
) {
938 // Move on to the next node
939 r
= __loc_database_lookup(db
, address
, network
, network_address
, node_index
, level
+ 1);
941 // End here if a result was found
949 DEBUG(db
->ctx
, "No match found below level %u\n", level
);
951 DEBUG(db
->ctx
, "Tree ended at level %u\n", level
);
954 // If this node has a leaf, we will check if it matches
955 if (__loc_database_node_is_leaf(p_v1
)) {
956 r
= __loc_database_lookup_handle_leaf(db
, address
, network
, network_address
, level
, p_v1
);
964 LOC_EXPORT
int loc_database_lookup(struct loc_database
* db
,
965 const struct in6_addr
* address
, struct loc_network
** network
) {
966 struct in6_addr network_address
;
967 memset(&network_address
, 0, sizeof(network_address
));
973 clock_t start
= clock();
976 int r
= __loc_database_lookup(db
, address
, network
, &network_address
, 0, 0);
979 clock_t end
= clock();
981 // Log how fast this has been
982 DEBUG(db
->ctx
, "Executed network search in %.4fms\n",
983 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
989 LOC_EXPORT
int loc_database_lookup_from_string(struct loc_database
* db
,
990 const char* string
, struct loc_network
** network
) {
991 struct in6_addr address
;
993 int r
= loc_address_parse(&address
, NULL
, string
);
997 return loc_database_lookup(db
, &address
, network
);
1000 // Returns the country at position pos
1001 static int loc_database_fetch_country(struct loc_database
* db
,
1002 struct loc_country
** country
, off_t pos
) {
1003 struct loc_database_country_v1 country_v1
;
1004 struct loc_database_country_v1
* p_v1
;
1007 // Check if the country is within range
1008 if ((size_t)pos
>= db
->country_objects
.count
) {
1013 DEBUG(db
->ctx
, "Fetching country at position %jd\n", (intmax_t)pos
);
1015 switch (db
->version
) {
1016 case LOC_DATABASE_VERSION_1
:
1018 p_v1
= loc_database_read_object(db
, &country_v1
, &db
->country_objects
, pos
);
1022 r
= loc_country_new_from_database_v1(db
->ctx
, db
->pool
, country
, p_v1
);
1031 DEBUG(db
->ctx
, "Got country %s\n", loc_country_get_code(*country
));
1036 // Performs a binary search to find the country in the list
1037 LOC_EXPORT
int loc_database_get_country(struct loc_database
* db
,
1038 struct loc_country
** country
, const char* code
) {
1040 off_t hi
= db
->country_objects
.count
- 1;
1042 // Check if the country code is valid
1043 if (!loc_country_code_is_valid(code
)) {
1050 clock_t start
= clock();
1054 off_t i
= (lo
+ hi
) / 2;
1056 // Fetch country in the middle between lo and hi
1057 int r
= loc_database_fetch_country(db
, country
, i
);
1061 // Check if this is a match
1062 const char* cc
= loc_country_get_code(*country
);
1063 int result
= strcmp(code
, cc
);
1067 clock_t end
= clock();
1069 // Log how fast this has been
1070 DEBUG(db
->ctx
, "Found country %s in %.4fms\n", cc
,
1071 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
1077 // If it wasn't, we release the country and
1078 // adjust our search pointers
1079 loc_country_unref(*country
);
1095 static void loc_database_enumerator_free(struct loc_database_enumerator
* enumerator
) {
1096 DEBUG(enumerator
->ctx
, "Releasing database enumerator %p\n", enumerator
);
1098 // Release all references
1099 loc_database_unref(enumerator
->db
);
1100 loc_unref(enumerator
->ctx
);
1102 if (enumerator
->string
)
1103 free(enumerator
->string
);
1105 if (enumerator
->countries
)
1106 loc_country_list_unref(enumerator
->countries
);
1108 if (enumerator
->asns
)
1109 loc_as_list_unref(enumerator
->asns
);
1111 // Free network search
1112 if (enumerator
->networks_visited
)
1113 free(enumerator
->networks_visited
);
1115 // Free subnet/bogons stack
1116 if (enumerator
->stack
)
1117 loc_network_list_unref(enumerator
->stack
);
1119 if (enumerator
->subnets
)
1120 loc_network_list_unref(enumerator
->subnets
);
1125 LOC_EXPORT
int loc_database_enumerator_new(struct loc_database_enumerator
** enumerator
,
1126 struct loc_database
* db
, enum loc_database_enumerator_mode mode
, int flags
) {
1129 struct loc_database_enumerator
* e
= calloc(1, sizeof(*e
));
1134 // Reference context
1135 e
->ctx
= loc_ref(db
->ctx
);
1136 e
->db
= loc_database_ref(db
);
1141 e
->flatten
= (flags
& LOC_DB_ENUMERATOR_FLAGS_FLATTEN
);
1143 // Initialise graph search
1144 e
->network_stack_depth
= 1;
1145 e
->networks_visited
= calloc(db
->network_node_objects
.count
, sizeof(*e
->networks_visited
));
1146 printf("COUNT = %zu, P = %p\n", db
->network_node_objects
.count
, e
->networks_visited
);
1147 if (!e
->networks_visited
) {
1148 ERROR(db
->ctx
, "Could not allocated visited networks: %m\n");
1154 r
= loc_network_list_new(e
->ctx
, &e
->stack
);
1158 // Initialize bogon search
1159 loc_address_reset(&e
->gap6_start
, AF_INET6
);
1160 loc_address_reset(&e
->gap4_start
, AF_INET
);
1162 DEBUG(e
->ctx
, "Database enumerator object allocated at %p\n", e
);
1169 loc_database_enumerator_free(e
);
1174 LOC_EXPORT
struct loc_database_enumerator
* loc_database_enumerator_ref(struct loc_database_enumerator
* enumerator
) {
1175 enumerator
->refcount
++;
1180 LOC_EXPORT
struct loc_database_enumerator
* loc_database_enumerator_unref(struct loc_database_enumerator
* enumerator
) {
1184 if (--enumerator
->refcount
> 0)
1187 loc_database_enumerator_free(enumerator
);
1191 LOC_EXPORT
int loc_database_enumerator_set_string(struct loc_database_enumerator
* enumerator
, const char* string
) {
1192 enumerator
->string
= strdup(string
);
1194 // Make the string lowercase
1195 for (char *p
= enumerator
->string
; *p
; p
++)
1201 LOC_EXPORT
struct loc_country_list
* loc_database_enumerator_get_countries(
1202 struct loc_database_enumerator
* enumerator
) {
1203 if (!enumerator
->countries
)
1206 return loc_country_list_ref(enumerator
->countries
);
1209 LOC_EXPORT
int loc_database_enumerator_set_countries(
1210 struct loc_database_enumerator
* enumerator
, struct loc_country_list
* countries
) {
1211 if (enumerator
->countries
)
1212 loc_country_list_unref(enumerator
->countries
);
1214 enumerator
->countries
= loc_country_list_ref(countries
);
1219 LOC_EXPORT
struct loc_as_list
* loc_database_enumerator_get_asns(
1220 struct loc_database_enumerator
* enumerator
) {
1221 if (!enumerator
->asns
)
1224 return loc_as_list_ref(enumerator
->asns
);
1227 LOC_EXPORT
int loc_database_enumerator_set_asns(
1228 struct loc_database_enumerator
* enumerator
, struct loc_as_list
* asns
) {
1229 if (enumerator
->asns
)
1230 loc_as_list_unref(enumerator
->asns
);
1232 enumerator
->asns
= loc_as_list_ref(asns
);
1237 LOC_EXPORT
int loc_database_enumerator_set_flag(
1238 struct loc_database_enumerator
* enumerator
, enum loc_network_flags flag
) {
1239 enumerator
->flags
|= flag
;
1244 LOC_EXPORT
int loc_database_enumerator_set_family(
1245 struct loc_database_enumerator
* enumerator
, int family
) {
1246 enumerator
->family
= family
;
1251 LOC_EXPORT
int loc_database_enumerator_next_as(
1252 struct loc_database_enumerator
* enumerator
, struct loc_as
** as
) {
1255 // Do not do anything if not in AS mode
1256 if (enumerator
->mode
!= LOC_DB_ENUMERATE_ASES
)
1259 struct loc_database
* db
= enumerator
->db
;
1261 while (enumerator
->as_index
< db
->as_objects
.count
) {
1262 // Fetch the next AS
1263 int r
= loc_database_fetch_as(db
, as
, enumerator
->as_index
++);
1267 r
= loc_as_match_string(*as
, enumerator
->string
);
1269 DEBUG(enumerator
->ctx
, "AS%d (%s) matches %s\n",
1270 loc_as_get_number(*as
), loc_as_get_name(*as
), enumerator
->string
);
1281 enumerator
->as_index
= 0;
1283 // We have searched through all of them
1287 static int loc_database_enumerator_stack_push_node(
1288 struct loc_database_enumerator
* e
, off_t offset
, int i
, int depth
) {
1289 // Do not add empty nodes
1293 // Check if there is any space left on the stack
1294 if (e
->network_stack_depth
>= MAX_STACK_DEPTH
) {
1295 ERROR(e
->ctx
, "Maximum stack size reached: %d\n", e
->network_stack_depth
);
1299 // Check if the node is in range
1300 if (offset
>= (off_t
)e
->db
->network_node_objects
.count
) {
1301 ERROR(e
->ctx
, "Trying to add invalid node with offset %jd/%zu\n",
1302 offset
, e
->db
->network_node_objects
.count
);
1307 // Increase stack size
1308 int s
= ++e
->network_stack_depth
;
1310 DEBUG(e
->ctx
, "Added node %jd to stack (%d)\n", (intmax_t)offset
, depth
);
1312 e
->network_stack
[s
].offset
= offset
;
1313 e
->network_stack
[s
].i
= i
;
1314 e
->network_stack
[s
].depth
= depth
;
1319 static int loc_database_enumerator_match_network(
1320 struct loc_database_enumerator
* enumerator
, struct loc_network
* network
) {
1321 // If family is set, it must match
1322 if (enumerator
->family
&& loc_network_address_family(network
) != enumerator
->family
) {
1323 DEBUG(enumerator
->ctx
, "Filtered network %p because of family not matching\n", network
);
1327 // Match if no filter criteria is configured
1328 if (!enumerator
->countries
&& !enumerator
->asns
&& !enumerator
->flags
)
1331 // Check if the country code matches
1332 if (enumerator
->countries
&& !loc_country_list_empty(enumerator
->countries
)) {
1333 const char* country_code
= loc_network_get_country_code(network
);
1335 if (loc_country_list_contains_code(enumerator
->countries
, country_code
)) {
1336 DEBUG(enumerator
->ctx
, "Matched network %p because of its country code\n", network
);
1341 // Check if the ASN matches
1342 if (enumerator
->asns
&& !loc_as_list_empty(enumerator
->asns
)) {
1343 uint32_t asn
= loc_network_get_asn(network
);
1345 if (loc_as_list_contains_number(enumerator
->asns
, asn
)) {
1346 DEBUG(enumerator
->ctx
, "Matched network %p because of its ASN\n", network
);
1351 // Check if flags match
1352 if (enumerator
->flags
&& loc_network_has_flag(network
, enumerator
->flags
)) {
1353 DEBUG(enumerator
->ctx
, "Matched network %p because of its flags\n", network
);
1361 static int __loc_database_enumerator_next_network(
1362 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
, int filter
) {
1363 struct loc_database_network_node_v1 node_v1
;
1365 // Return top element from the stack
1367 *network
= loc_network_list_pop_first(enumerator
->stack
);
1373 // Return everything if filter isn't enabled, or only return matches
1374 if (!filter
|| loc_database_enumerator_match_network(enumerator
, *network
))
1377 // Throw away anything that doesn't match
1378 loc_network_unref(*network
);
1382 DEBUG(enumerator
->ctx
, "Called with a stack of %u nodes\n",
1383 enumerator
->network_stack_depth
);
1386 while (enumerator
->network_stack_depth
> 0) {
1387 DEBUG(enumerator
->ctx
, "Stack depth: %u\n", enumerator
->network_stack_depth
);
1389 // Get object from top of the stack
1390 struct loc_node_stack
* node
= &enumerator
->network_stack
[enumerator
->network_stack_depth
];
1392 DEBUG(enumerator
->ctx
, " Got node: %jd\n", node
->offset
);
1394 // Remove the node from the stack if we have already visited it
1395 if (enumerator
->networks_visited
[node
->offset
]) {
1396 enumerator
->network_stack_depth
--;
1400 // Mark the bits on the path correctly
1401 loc_address_set_bit(&enumerator
->network_address
,
1402 (node
->depth
> 0) ? node
->depth
- 1 : 0, node
->i
);
1404 DEBUG(enumerator
->ctx
, "Looking at node %jd\n", (intmax_t)node
->offset
);
1405 enumerator
->networks_visited
[node
->offset
]++;
1407 // Pop node from top of the stack
1408 struct loc_database_network_node_v1
* n
= loc_database_read_object(enumerator
->db
,
1409 &node_v1
, &enumerator
->db
->network_node_objects
, node
->offset
);
1413 // Add edges to stack
1414 int r
= loc_database_enumerator_stack_push_node(enumerator
,
1415 be32toh(n
->one
), 1, node
->depth
+ 1);
1419 r
= loc_database_enumerator_stack_push_node(enumerator
,
1420 be32toh(n
->zero
), 0, node
->depth
+ 1);
1424 // Check if this node is a leaf and has a network object
1425 if (__loc_database_node_is_leaf(n
)) {
1426 off_t network_index
= be32toh(n
->network
);
1428 DEBUG(enumerator
->ctx
, "Node has a network at %jd\n", (intmax_t)network_index
);
1430 // Fetch the network object
1431 r
= loc_database_fetch_network(enumerator
->db
, network
,
1432 &enumerator
->network_address
, node
->depth
, network_index
);
1434 // Break on any errors
1438 // Return all networks when the filter is disabled, or check for match
1439 if (!filter
|| loc_database_enumerator_match_network(enumerator
, *network
))
1442 // Does not seem to be a match, so we cleanup and move on
1443 loc_network_unref(*network
);
1448 // Reached the end of the search
1452 static int __loc_database_enumerator_next_network_flattened(
1453 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
) {
1454 // Fetch the next network
1455 int r
= __loc_database_enumerator_next_network(enumerator
, network
, 1);
1459 // End if we could not read another network
1463 struct loc_network
* subnet
= NULL
;
1465 // Create a list with all subnets
1466 if (!enumerator
->subnets
) {
1467 r
= loc_network_list_new(enumerator
->ctx
, &enumerator
->subnets
);
1472 // Search all subnets from the database
1474 // Fetch the next network in line
1475 r
= __loc_database_enumerator_next_network(enumerator
, &subnet
, 0);
1477 loc_network_unref(subnet
);
1478 loc_network_list_clear(enumerator
->subnets
);
1483 // End if we did not receive another subnet
1487 // Collect all subnets in a list
1488 if (loc_network_is_subnet(*network
, subnet
)) {
1489 r
= loc_network_list_push(enumerator
->subnets
, subnet
);
1491 loc_network_unref(subnet
);
1492 loc_network_list_clear(enumerator
->subnets
);
1497 loc_network_unref(subnet
);
1501 // If this is not a subnet, we push it back onto the stack and break
1502 r
= loc_network_list_push(enumerator
->stack
, subnet
);
1504 loc_network_unref(subnet
);
1505 loc_network_list_clear(enumerator
->subnets
);
1510 loc_network_unref(subnet
);
1514 DEBUG(enumerator
->ctx
, "Found %zu subnet(s)\n",
1515 loc_network_list_size(enumerator
->subnets
));
1517 // We can abort here if the network has no subnets
1518 if (loc_network_list_empty(enumerator
->subnets
)) {
1519 loc_network_list_clear(enumerator
->subnets
);
1524 // If the network has any subnets, we will break it into smaller parts
1525 // without the subnets.
1526 struct loc_network_list
* excluded
= loc_network_exclude_list(*network
, enumerator
->subnets
);
1528 loc_network_list_clear(enumerator
->subnets
);
1532 // Merge subnets onto the stack
1533 r
= loc_network_list_merge(enumerator
->stack
, enumerator
->subnets
);
1535 loc_network_list_clear(enumerator
->subnets
);
1536 loc_network_list_unref(excluded
);
1541 // Push excluded list onto the stack
1542 r
= loc_network_list_merge(enumerator
->stack
, excluded
);
1544 loc_network_list_clear(enumerator
->subnets
);
1545 loc_network_list_unref(excluded
);
1550 loc_network_list_clear(enumerator
->subnets
);
1551 loc_network_list_unref(excluded
);
1553 // Drop the network and restart the whole process again to pick the next network
1554 loc_network_unref(*network
);
1556 return __loc_database_enumerator_next_network_flattened(enumerator
, network
);
1560 This function finds all bogons (i.e. gaps) between the input networks
1562 static int __loc_database_enumerator_next_bogon(
1563 struct loc_database_enumerator
* enumerator
, struct loc_network
** bogon
) {
1566 // Return top element from the stack
1568 *bogon
= loc_network_list_pop_first(enumerator
->stack
);
1578 struct loc_network
* network
= NULL
;
1579 struct in6_addr
* gap_start
= NULL
;
1580 struct in6_addr gap_end
= IN6ADDR_ANY_INIT
;
1583 r
= __loc_database_enumerator_next_network(enumerator
, &network
, 1);
1587 // We have read the last network
1591 const char* country_code
= loc_network_get_country_code(network
);
1594 Skip anything that does not have a country code
1596 Even if a network is part of the routing table, and the database provides
1597 an ASN, this does not mean that this is a legitimate announcement.
1599 if (country_code
&& !*country_code
) {
1600 loc_network_unref(network
);
1604 // Determine the network family
1605 int family
= loc_network_address_family(network
);
1609 gap_start
= &enumerator
->gap6_start
;
1613 gap_start
= &enumerator
->gap4_start
;
1617 ERROR(enumerator
->ctx
, "Unsupported network family %d\n", family
);
1622 const struct in6_addr
* first_address
= loc_network_get_first_address(network
);
1623 const struct in6_addr
* last_address
= loc_network_get_last_address(network
);
1625 // Skip if this network is a subnet of a former one
1626 if (loc_address_cmp(gap_start
, last_address
) >= 0) {
1627 loc_network_unref(network
);
1631 // Search where the gap could end
1632 gap_end
= *first_address
;
1633 loc_address_decrement(&gap_end
);
1636 if (loc_address_cmp(gap_start
, &gap_end
) <= 0) {
1637 r
= loc_network_list_summarize(enumerator
->ctx
,
1638 gap_start
, &gap_end
, &enumerator
->stack
);
1640 loc_network_unref(network
);
1645 // The gap now starts after this network
1646 *gap_start
= *last_address
;
1647 loc_address_increment(gap_start
);
1649 loc_network_unref(network
);
1651 // Try to return something
1652 *bogon
= loc_network_list_pop_first(enumerator
->stack
);
1661 if (!loc_address_all_zeroes(&enumerator
->gap6_start
)) {
1662 r
= loc_address_reset_last(&gap_end
, AF_INET6
);
1666 if (loc_address_cmp(&enumerator
->gap6_start
, &gap_end
) <= 0) {
1667 r
= loc_network_list_summarize(enumerator
->ctx
,
1668 &enumerator
->gap6_start
, &gap_end
, &enumerator
->stack
);
1674 loc_address_reset(&enumerator
->gap6_start
, AF_INET6
);
1677 if (!loc_address_all_zeroes(&enumerator
->gap4_start
)) {
1678 r
= loc_address_reset_last(&gap_end
, AF_INET
);
1682 if (loc_address_cmp(&enumerator
->gap4_start
, &gap_end
) <= 0) {
1683 r
= loc_network_list_summarize(enumerator
->ctx
,
1684 &enumerator
->gap4_start
, &gap_end
, &enumerator
->stack
);
1690 loc_address_reset(&enumerator
->gap4_start
, AF_INET
);
1693 // Try to return something
1694 *bogon
= loc_network_list_pop_first(enumerator
->stack
);
1699 LOC_EXPORT
int loc_database_enumerator_next_network(
1700 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
) {
1701 switch (enumerator
->mode
) {
1702 case LOC_DB_ENUMERATE_NETWORKS
:
1704 if (enumerator
->flatten
)
1705 return __loc_database_enumerator_next_network_flattened(enumerator
, network
);
1707 return __loc_database_enumerator_next_network(enumerator
, network
, 1);
1709 case LOC_DB_ENUMERATE_BOGONS
:
1710 return __loc_database_enumerator_next_bogon(enumerator
, network
);
1717 LOC_EXPORT
int loc_database_enumerator_next_country(
1718 struct loc_database_enumerator
* enumerator
, struct loc_country
** country
) {
1721 // Do not do anything if not in country mode
1722 if (enumerator
->mode
!= LOC_DB_ENUMERATE_COUNTRIES
)
1725 struct loc_database
* db
= enumerator
->db
;
1727 while (enumerator
->country_index
< db
->country_objects
.count
) {
1728 // Fetch the next country
1729 int r
= loc_database_fetch_country(db
, country
, enumerator
->country_index
++);
1733 // We do not filter here, so it always is a match
1738 enumerator
->country_index
= 0;
1740 // We have searched through all of them