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
{
60 struct loc_database_signature
{
71 enum loc_database_version version
;
78 struct loc_database_signature signature1
;
79 struct loc_database_signature signature2
;
81 // Data mapped into memory
85 struct loc_stringpool
* pool
;
87 // ASes in the database
88 struct loc_database_objects as_objects
;
91 struct loc_database_objects network_node_objects
;
94 struct loc_database_objects network_objects
;
97 struct loc_database_objects country_objects
;
100 #define MAX_STACK_DEPTH 256
102 struct loc_node_stack
{
104 int i
; // Is this node 0 or 1?
108 struct loc_database_enumerator
{
110 struct loc_database
* db
;
111 enum loc_database_enumerator_mode mode
;
116 struct loc_country_list
* countries
;
117 struct loc_as_list
* asns
;
118 enum loc_network_flags flags
;
124 // Index of the AS we are looking at
125 unsigned int as_index
;
127 // Index of the country we are looking at
128 unsigned int country_index
;
131 struct in6_addr network_address
;
132 struct loc_node_stack network_stack
[MAX_STACK_DEPTH
];
133 int network_stack_depth
;
134 unsigned int* networks_visited
;
136 // For subnet search and bogons
137 struct loc_network_list
* stack
;
138 struct loc_network_list
* subnets
;
141 struct in6_addr gap6_start
;
142 struct in6_addr gap4_start
;
146 Checks if it is safe to read the buffer of size length starting at p.
148 #define loc_database_check_boundaries(db, p) \
149 __loc_database_check_boundaries(db, (const char*)p, sizeof(*p))
151 static int __loc_database_check_boundaries(struct loc_database
* db
,
152 const char* p
, const size_t length
) {
153 size_t offset
= p
- db
->data
;
155 // Return if everything is within the boundary
156 if (offset
<= db
->length
- length
)
159 DEBUG(db
->ctx
, "Database read check failed at %p for %zu byte(s)\n", p
, length
);
160 DEBUG(db
->ctx
, " p = %p (offset = %jd, length = %zu)\n", p
, offset
, length
);
161 DEBUG(db
->ctx
, " data = %p (length = %zu)\n", db
->data
, db
->length
);
162 DEBUG(db
->ctx
, " end = %p\n", db
->data
+ db
->length
);
163 DEBUG(db
->ctx
, " overflow of %zu byte(s)\n", offset
+ length
- db
->length
);
165 // Otherwise raise EFAULT
171 Returns a pointer to the n-th object
173 static char* loc_database_object(struct loc_database
* db
,
174 const struct loc_database_objects
* objects
, const size_t length
, const off_t n
) {
175 // Return NULL if objects were not initialized
176 if (!objects
->data
) {
182 const off_t offset
= n
* length
;
184 // Return a pointer to where the object lies
185 char* object
= objects
->data
+ offset
;
187 // Check if the object is part of the memory
188 if (!__loc_database_check_boundaries(db
, object
, length
))
194 static int loc_database_version_supported(struct loc_database
* db
, uint8_t version
) {
196 // Supported versions
197 case LOC_DATABASE_VERSION_1
:
201 ERROR(db
->ctx
, "Database version %d is not supported\n", version
);
207 static int loc_database_check_magic(struct loc_database
* db
) {
208 struct loc_database_magic magic
;
211 size_t bytes_read
= fread(&magic
, 1, sizeof(magic
), db
->f
);
213 // Check if we have been able to read enough data
214 if (bytes_read
< sizeof(magic
)) {
215 ERROR(db
->ctx
, "Could not read enough data to validate magic bytes\n");
216 DEBUG(db
->ctx
, "Read %zu bytes, but needed %zu\n", bytes_read
, sizeof(magic
));
220 // Compare magic bytes
221 if (memcmp(magic
.magic
, LOC_DATABASE_MAGIC
, sizeof(magic
.magic
)) == 0) {
222 DEBUG(db
->ctx
, "Magic value matches\n");
224 // Do we support this version?
225 if (!loc_database_version_supported(db
, magic
.version
))
229 db
->version
= magic
.version
;
235 ERROR(db
->ctx
, "Unrecognized file type\n");
243 Maps the entire database into memory
245 static int loc_database_mmap(struct loc_database
* db
) {
248 // Get file descriptor
249 int fd
= fileno(db
->f
);
251 // Determine the length of the database
252 db
->length
= lseek(fd
, 0, SEEK_END
);
253 if (db
->length
< 0) {
254 ERROR(db
->ctx
, "Could not determine the length of the database: %m\n");
261 db
->data
= mmap(NULL
, db
->length
, PROT_READ
, MAP_SHARED
, fd
, 0);
262 if (db
->data
== MAP_FAILED
) {
263 ERROR(db
->ctx
, "Could not map the database: %m\n");
268 DEBUG(db
->ctx
, "Mapped database of %zu byte(s) at %p\n", db
->length
, db
->data
);
270 // Tell the system that we expect to read data randomly
271 r
= madvise(db
->data
, db
->length
, MADV_RANDOM
);
273 ERROR(db
->ctx
, "madvise() failed: %m\n");
281 Maps arbitrary objects from the database into memory.
283 static int loc_database_map_objects(struct loc_database
* db
,
284 struct loc_database_objects
* objects
, const size_t size
,
285 off_t offset
, size_t length
) {
287 objects
->data
= db
->data
+ offset
;
288 objects
->offset
= offset
;
289 objects
->length
= length
;
290 objects
->count
= objects
->length
/ size
;
295 static int loc_database_read_signature(struct loc_database
* db
,
296 struct loc_database_signature
* signature
, const char* data
, const size_t length
) {
297 // Check for a plausible signature length
298 if (length
> LOC_SIGNATURE_MAX_LENGTH
) {
299 ERROR(db
->ctx
, "Signature too long: %zu\n", length
);
304 // Store data & length
305 signature
->data
= data
;
306 signature
->length
= length
;
308 DEBUG(db
->ctx
, "Read signature of %zu byte(s) at %p\n",
309 signature
->length
, signature
->data
);
311 hexdump(db
->ctx
, signature
->data
, signature
->length
);
316 static int loc_database_read_header_v1(struct loc_database
* db
) {
317 const struct loc_database_header_v1
* header
=
318 (const struct loc_database_header_v1
*)(db
->data
+ LOC_DATABASE_MAGIC_SIZE
);
321 DEBUG(db
->ctx
, "Reading header at %p\n", header
);
323 // Check if we can read the header
324 if (!loc_database_check_boundaries(db
, header
)) {
325 ERROR(db
->ctx
, "Could not read enough data for header\n");
329 // Dump the entire header
330 hexdump(db
->ctx
, header
, sizeof(*header
));
333 db
->created_at
= be64toh(header
->created_at
);
334 db
->vendor
= be32toh(header
->vendor
);
335 db
->description
= be32toh(header
->description
);
336 db
->license
= be32toh(header
->license
);
339 r
= loc_database_read_signature(db
, &db
->signature1
,
340 header
->signature1
, be16toh(header
->signature1_length
));
344 r
= loc_database_read_signature(db
, &db
->signature2
,
345 header
->signature2
, be16toh(header
->signature2_length
));
349 const char* stringpool_start
= db
->data
+ be32toh(header
->pool_offset
);
350 size_t stringpool_length
= be32toh(header
->pool_length
);
352 // Check if the stringpool is part of the mapped area
353 if (!__loc_database_check_boundaries(db
, stringpool_start
, stringpool_length
))
356 // Open the stringpool
357 r
= loc_stringpool_open(db
->ctx
, &db
->pool
, stringpool_start
, stringpool_length
);
362 r
= loc_database_map_objects(db
, &db
->as_objects
,
363 sizeof(struct loc_database_as_v1
),
364 be32toh(header
->as_offset
),
365 be32toh(header
->as_length
));
370 r
= loc_database_map_objects(db
, &db
->network_node_objects
,
371 sizeof(struct loc_database_network_node_v1
),
372 be32toh(header
->network_tree_offset
),
373 be32toh(header
->network_tree_length
));
378 r
= loc_database_map_objects(db
, &db
->network_objects
,
379 sizeof(struct loc_database_network_v1
),
380 be32toh(header
->network_data_offset
),
381 be32toh(header
->network_data_length
));
386 r
= loc_database_map_objects(db
, &db
->country_objects
,
387 sizeof(struct loc_database_country_v1
),
388 be32toh(header
->countries_offset
),
389 be32toh(header
->countries_length
));
396 static int loc_database_read_header(struct loc_database
* db
) {
397 DEBUG(db
->ctx
, "Database version is %u\n", db
->version
);
399 switch (db
->version
) {
400 case LOC_DATABASE_VERSION_1
:
401 return loc_database_read_header_v1(db
);
404 ERROR(db
->ctx
, "Incompatible database version: %u\n", db
->version
);
409 static int loc_database_clone_handle(struct loc_database
* db
, FILE* f
) {
410 // Fetch the FD of the original handle
413 // Clone file descriptor
416 ERROR(db
->ctx
, "Could not duplicate file descriptor\n");
420 // Reopen the file so that we can keep our own file handle
421 db
->f
= fdopen(fd
, "r");
423 ERROR(db
->ctx
, "Could not re-open database file\n");
427 // Rewind to the start of the file
433 static int loc_database_open(struct loc_database
* db
, FILE* f
) {
436 clock_t start
= clock();
438 // Clone the file handle
439 r
= loc_database_clone_handle(db
, f
);
444 r
= loc_database_check_magic(db
);
448 // Map the database into memory
449 r
= loc_database_mmap(db
);
454 r
= loc_database_read_header(db
);
458 clock_t end
= clock();
460 INFO(db
->ctx
, "Opened database in %.4fms\n",
461 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
466 static void loc_database_free(struct loc_database
* db
) {
469 DEBUG(db
->ctx
, "Releasing database %p\n", db
);
471 // Unmap the entire database
473 r
= munmap(db
->data
, db
->length
);
475 ERROR(db
->ctx
, "Could not unmap the database: %m\n");
478 // Free the stringpool
480 loc_stringpool_unref(db
->pool
);
482 // Close database file
490 LOC_EXPORT
int loc_database_new(struct loc_ctx
* ctx
, struct loc_database
** database
, FILE* f
) {
491 struct loc_database
* db
= NULL
;
494 // Fail on invalid file handle
500 // Allocate the database object
501 db
= calloc(1, sizeof(*db
));
506 db
->ctx
= loc_ref(ctx
);
509 DEBUG(db
->ctx
, "Database object allocated at %p\n", db
);
511 // Try to open the database
512 r
= loc_database_open(db
, f
);
521 loc_database_free(db
);
526 LOC_EXPORT
struct loc_database
* loc_database_ref(struct loc_database
* db
) {
532 LOC_EXPORT
struct loc_database
* loc_database_unref(struct loc_database
* db
) {
533 if (--db
->refcount
> 0)
536 loc_database_free(db
);
540 LOC_EXPORT
int loc_database_verify(struct loc_database
* db
, FILE* f
) {
541 size_t bytes_read
= 0;
543 // Cannot do this when no signature is available
544 if (!db
->signature1
.data
&& !db
->signature2
.data
) {
545 DEBUG(db
->ctx
, "No signature available to verify\n");
549 // Start the stopwatch
550 clock_t start
= clock();
553 EVP_PKEY
* pkey
= PEM_read_PUBKEY(f
, NULL
, NULL
, NULL
);
555 ERROR(db
->ctx
, "Could not parse public key: %s\n",
556 ERR_error_string(ERR_get_error(), NULL
));
563 EVP_MD_CTX
* mdctx
= EVP_MD_CTX_new();
565 // Initialise hash function
566 r
= EVP_DigestVerifyInit(mdctx
, NULL
, NULL
, NULL
, pkey
);
568 ERROR(db
->ctx
, "Error initializing signature validation: %s\n",
569 ERR_error_string(ERR_get_error(), NULL
));
575 // Reset file to start
579 struct loc_database_magic magic
;
580 bytes_read
= fread(&magic
, 1, sizeof(magic
), db
->f
);
581 if (bytes_read
< sizeof(magic
)) {
582 ERROR(db
->ctx
, "Could not read header: %m\n");
587 hexdump(db
->ctx
, &magic
, sizeof(magic
));
589 // Feed magic into the hash
590 r
= EVP_DigestVerifyUpdate(mdctx
, &magic
, sizeof(magic
));
592 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
599 struct loc_database_header_v1 header_v1
;
601 switch (db
->version
) {
602 case LOC_DATABASE_VERSION_1
:
603 bytes_read
= fread(&header_v1
, 1, sizeof(header_v1
), db
->f
);
604 if (bytes_read
< sizeof(header_v1
)) {
605 ERROR(db
->ctx
, "Could not read header\n");
612 memset(header_v1
.signature1
, '\0', sizeof(header_v1
.signature1
));
613 header_v1
.signature1_length
= 0;
614 memset(header_v1
.signature2
, '\0', sizeof(header_v1
.signature2
));
615 header_v1
.signature2_length
= 0;
617 hexdump(db
->ctx
, &header_v1
, sizeof(header_v1
));
619 // Feed header into the hash
620 r
= EVP_DigestVerifyUpdate(mdctx
, &header_v1
, sizeof(header_v1
));
622 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
630 ERROR(db
->ctx
, "Cannot compute hash for database with format %d\n",
636 // Walk through the file in chunks of 64kB
637 char buffer
[64 * 1024];
639 while (!feof(db
->f
)) {
640 bytes_read
= fread(buffer
, 1, sizeof(buffer
), db
->f
);
642 hexdump(db
->ctx
, buffer
, bytes_read
);
644 r
= EVP_DigestVerifyUpdate(mdctx
, buffer
, bytes_read
);
646 ERROR(db
->ctx
, "%s\n", ERR_error_string(ERR_get_error(), NULL
));
653 // Check first signature
654 if (db
->signature1
.data
) {
655 hexdump(db
->ctx
, db
->signature1
.data
, db
->signature1
.length
);
657 r
= EVP_DigestVerifyFinal(mdctx
,
658 (unsigned char*)db
->signature1
.data
, db
->signature1
.length
);
661 DEBUG(db
->ctx
, "The first signature is invalid\n");
664 DEBUG(db
->ctx
, "The first signature is valid\n");
667 ERROR(db
->ctx
, "Error verifying the first signature: %s\n",
668 ERR_error_string(ERR_get_error(), NULL
));
673 // Check second signature only when the first one was invalid
674 if (r
&& db
->signature2
.data
) {
675 hexdump(db
->ctx
, db
->signature2
.data
, db
->signature2
.length
);
677 r
= EVP_DigestVerifyFinal(mdctx
,
678 (unsigned char*)db
->signature2
.data
, db
->signature2
.length
);
681 DEBUG(db
->ctx
, "The second signature is invalid\n");
684 DEBUG(db
->ctx
, "The second signature is valid\n");
687 ERROR(db
->ctx
, "Error verifying the second signature: %s\n",
688 ERR_error_string(ERR_get_error(), NULL
));
693 clock_t end
= clock();
694 INFO(db
->ctx
, "Signature checked in %.4fms\n",
695 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
699 EVP_MD_CTX_free(mdctx
);
705 LOC_EXPORT
time_t loc_database_created_at(struct loc_database
* db
) {
706 return db
->created_at
;
709 LOC_EXPORT
const char* loc_database_get_vendor(struct loc_database
* db
) {
710 return loc_stringpool_get(db
->pool
, db
->vendor
);
713 LOC_EXPORT
const char* loc_database_get_description(struct loc_database
* db
) {
714 return loc_stringpool_get(db
->pool
, db
->description
);
717 LOC_EXPORT
const char* loc_database_get_license(struct loc_database
* db
) {
718 return loc_stringpool_get(db
->pool
, db
->license
);
721 LOC_EXPORT
size_t loc_database_count_as(struct loc_database
* db
) {
722 return db
->as_objects
.count
;
725 // Returns the AS at position pos
726 static int loc_database_fetch_as(struct loc_database
* db
, struct loc_as
** as
, off_t pos
) {
727 struct loc_database_as_v1
* as_v1
= NULL
;
730 if ((size_t)pos
>= db
->as_objects
.count
) {
735 DEBUG(db
->ctx
, "Fetching AS at position %jd\n", (intmax_t)pos
);
737 switch (db
->version
) {
738 case LOC_DATABASE_VERSION_1
:
740 as_v1
= (struct loc_database_as_v1
*)loc_database_object(db
,
741 &db
->as_objects
, sizeof(*as_v1
), pos
);
745 r
= loc_as_new_from_database_v1(db
->ctx
, db
->pool
, as
, as_v1
);
754 DEBUG(db
->ctx
, "Got AS%u\n", loc_as_get_number(*as
));
759 // Performs a binary search to find the AS in the list
760 LOC_EXPORT
int loc_database_get_as(struct loc_database
* db
, struct loc_as
** as
, uint32_t number
) {
762 off_t hi
= db
->as_objects
.count
- 1;
766 clock_t start
= clock();
770 off_t i
= (lo
+ hi
) / 2;
772 // Fetch AS in the middle between lo and hi
773 int r
= loc_database_fetch_as(db
, as
, i
);
777 // Check if this is a match
778 uint32_t as_number
= loc_as_get_number(*as
);
779 if (as_number
== number
) {
781 clock_t end
= clock();
783 // Log how fast this has been
784 DEBUG(db
->ctx
, "Found AS%u in %.4fms\n", as_number
,
785 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
791 // If it wasn't, we release the AS and
792 // adjust our search pointers
795 if (as_number
< number
) {
807 // Returns the network at position pos
808 static int loc_database_fetch_network(struct loc_database
* db
, struct loc_network
** network
,
809 struct in6_addr
* address
, unsigned int prefix
, off_t pos
) {
810 struct loc_database_network_v1
* network_v1
= NULL
;
813 if ((size_t)pos
>= db
->network_objects
.count
) {
814 DEBUG(db
->ctx
, "Network ID out of range: %jd/%jd\n",
815 (intmax_t)pos
, (intmax_t)db
->network_objects
.count
);
820 DEBUG(db
->ctx
, "Fetching network at position %jd\n", (intmax_t)pos
);
822 switch (db
->version
) {
823 case LOC_DATABASE_VERSION_1
:
825 network_v1
= (struct loc_database_network_v1
*)loc_database_object(db
,
826 &db
->network_objects
, sizeof(*network_v1
), pos
);
830 r
= loc_network_new_from_database_v1(db
->ctx
, network
, address
, prefix
, network_v1
);
839 DEBUG(db
->ctx
, "Got network %s\n", loc_network_str(*network
));
844 static int __loc_database_node_is_leaf(const struct loc_database_network_node_v1
* node
) {
845 return (node
->network
!= htobe32(0xffffffff));
848 static int __loc_database_lookup_handle_leaf(struct loc_database
* db
, const struct in6_addr
* address
,
849 struct loc_network
** network
, struct in6_addr
* network_address
, unsigned int prefix
,
850 const struct loc_database_network_node_v1
* node
) {
851 off_t network_index
= be32toh(node
->network
);
853 DEBUG(db
->ctx
, "Handling leaf node at %jd\n", (intmax_t)network_index
);
856 int r
= loc_database_fetch_network(db
, network
, network_address
, prefix
, network_index
);
858 ERROR(db
->ctx
, "Could not fetch network %jd from database: %m\n",
859 (intmax_t)network_index
);
863 // Check if the given IP address is inside the network
864 if (!loc_network_matches_address(*network
, address
)) {
865 DEBUG(db
->ctx
, "Searched address is not part of the network\n");
867 loc_network_unref(*network
);
872 // A network was found and the IP address matches
876 // Searches for an exact match along the path
877 static int __loc_database_lookup(struct loc_database
* db
, const struct in6_addr
* address
,
878 struct loc_network
** network
, struct in6_addr
* network_address
,
879 off_t node_index
, unsigned int level
) {
880 struct loc_database_network_node_v1
* node_v1
= NULL
;
884 // Fetch the next node
885 node_v1
= (struct loc_database_network_node_v1
*)loc_database_object(db
,
886 &db
->network_node_objects
, sizeof(*node_v1
), node_index
);
891 int bit
= loc_address_get_bit(address
, level
);
892 loc_address_set_bit(network_address
, level
, bit
);
895 node_index
= be32toh(node_v1
->zero
);
897 node_index
= be32toh(node_v1
->one
);
899 // If the node index is zero, the tree ends here
900 // and we cannot descend any further
901 if (node_index
> 0) {
903 if ((size_t)node_index
>= db
->network_node_objects
.count
) {
908 // Move on to the next node
909 r
= __loc_database_lookup(db
, address
, network
, network_address
, node_index
, level
+ 1);
911 // End here if a result was found
919 DEBUG(db
->ctx
, "No match found below level %u\n", level
);
921 DEBUG(db
->ctx
, "Tree ended at level %u\n", level
);
924 // If this node has a leaf, we will check if it matches
925 if (__loc_database_node_is_leaf(node_v1
)) {
926 r
= __loc_database_lookup_handle_leaf(db
, address
, network
, network_address
, level
, node_v1
);
934 LOC_EXPORT
int loc_database_lookup(struct loc_database
* db
,
935 const struct in6_addr
* address
, struct loc_network
** network
) {
936 struct in6_addr network_address
;
937 memset(&network_address
, 0, sizeof(network_address
));
943 clock_t start
= clock();
946 int r
= __loc_database_lookup(db
, address
, network
, &network_address
, 0, 0);
949 clock_t end
= clock();
951 // Log how fast this has been
952 DEBUG(db
->ctx
, "Executed network search in %.4fms\n",
953 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
959 LOC_EXPORT
int loc_database_lookup_from_string(struct loc_database
* db
,
960 const char* string
, struct loc_network
** network
) {
961 struct in6_addr address
;
963 int r
= loc_address_parse(&address
, NULL
, string
);
967 return loc_database_lookup(db
, &address
, network
);
970 // Returns the country at position pos
971 static int loc_database_fetch_country(struct loc_database
* db
,
972 struct loc_country
** country
, off_t pos
) {
973 struct loc_database_country_v1
* country_v1
= NULL
;
976 // Check if the country is within range
977 if ((size_t)pos
>= db
->country_objects
.count
) {
982 DEBUG(db
->ctx
, "Fetching country at position %jd\n", (intmax_t)pos
);
984 switch (db
->version
) {
985 case LOC_DATABASE_VERSION_1
:
987 country_v1
= (struct loc_database_country_v1
*)loc_database_object(db
,
988 &db
->country_objects
, sizeof(*country_v1
), pos
);
992 r
= loc_country_new_from_database_v1(db
->ctx
, db
->pool
, country
, country_v1
);
1001 DEBUG(db
->ctx
, "Got country %s\n", loc_country_get_code(*country
));
1006 // Performs a binary search to find the country in the list
1007 LOC_EXPORT
int loc_database_get_country(struct loc_database
* db
,
1008 struct loc_country
** country
, const char* code
) {
1010 off_t hi
= db
->country_objects
.count
- 1;
1012 // Check if the country code is valid
1013 if (!loc_country_code_is_valid(code
)) {
1020 clock_t start
= clock();
1024 off_t i
= (lo
+ hi
) / 2;
1026 // Fetch country in the middle between lo and hi
1027 int r
= loc_database_fetch_country(db
, country
, i
);
1031 // Check if this is a match
1032 const char* cc
= loc_country_get_code(*country
);
1033 int result
= strcmp(code
, cc
);
1037 clock_t end
= clock();
1039 // Log how fast this has been
1040 DEBUG(db
->ctx
, "Found country %s in %.4fms\n", cc
,
1041 (double)(end
- start
) / CLOCKS_PER_SEC
* 1000);
1047 // If it wasn't, we release the country and
1048 // adjust our search pointers
1049 loc_country_unref(*country
);
1065 static void loc_database_enumerator_free(struct loc_database_enumerator
* enumerator
) {
1066 DEBUG(enumerator
->ctx
, "Releasing database enumerator %p\n", enumerator
);
1068 // Release all references
1069 loc_database_unref(enumerator
->db
);
1070 loc_unref(enumerator
->ctx
);
1072 if (enumerator
->string
)
1073 free(enumerator
->string
);
1075 if (enumerator
->countries
)
1076 loc_country_list_unref(enumerator
->countries
);
1078 if (enumerator
->asns
)
1079 loc_as_list_unref(enumerator
->asns
);
1081 // Free network search
1082 if (enumerator
->networks_visited
)
1083 free(enumerator
->networks_visited
);
1085 // Free subnet/bogons stack
1086 if (enumerator
->stack
)
1087 loc_network_list_unref(enumerator
->stack
);
1089 if (enumerator
->subnets
)
1090 loc_network_list_unref(enumerator
->subnets
);
1095 LOC_EXPORT
int loc_database_enumerator_new(struct loc_database_enumerator
** enumerator
,
1096 struct loc_database
* db
, enum loc_database_enumerator_mode mode
, int flags
) {
1099 struct loc_database_enumerator
* e
= calloc(1, sizeof(*e
));
1104 // Reference context
1105 e
->ctx
= loc_ref(db
->ctx
);
1106 e
->db
= loc_database_ref(db
);
1111 e
->flatten
= (flags
& LOC_DB_ENUMERATOR_FLAGS_FLATTEN
);
1113 // Initialise graph search
1114 e
->network_stack_depth
= 1;
1115 e
->networks_visited
= calloc(db
->network_node_objects
.count
, sizeof(*e
->networks_visited
));
1116 printf("COUNT = %zu, P = %p\n", db
->network_node_objects
.count
, e
->networks_visited
);
1117 if (!e
->networks_visited
) {
1118 ERROR(db
->ctx
, "Could not allocated visited networks: %m\n");
1124 r
= loc_network_list_new(e
->ctx
, &e
->stack
);
1128 // Initialize bogon search
1129 loc_address_reset(&e
->gap6_start
, AF_INET6
);
1130 loc_address_reset(&e
->gap4_start
, AF_INET
);
1132 DEBUG(e
->ctx
, "Database enumerator object allocated at %p\n", e
);
1139 loc_database_enumerator_free(e
);
1144 LOC_EXPORT
struct loc_database_enumerator
* loc_database_enumerator_ref(struct loc_database_enumerator
* enumerator
) {
1145 enumerator
->refcount
++;
1150 LOC_EXPORT
struct loc_database_enumerator
* loc_database_enumerator_unref(struct loc_database_enumerator
* enumerator
) {
1154 if (--enumerator
->refcount
> 0)
1157 loc_database_enumerator_free(enumerator
);
1161 LOC_EXPORT
int loc_database_enumerator_set_string(struct loc_database_enumerator
* enumerator
, const char* string
) {
1162 enumerator
->string
= strdup(string
);
1164 // Make the string lowercase
1165 for (char *p
= enumerator
->string
; *p
; p
++)
1171 LOC_EXPORT
struct loc_country_list
* loc_database_enumerator_get_countries(
1172 struct loc_database_enumerator
* enumerator
) {
1173 if (!enumerator
->countries
)
1176 return loc_country_list_ref(enumerator
->countries
);
1179 LOC_EXPORT
int loc_database_enumerator_set_countries(
1180 struct loc_database_enumerator
* enumerator
, struct loc_country_list
* countries
) {
1181 if (enumerator
->countries
)
1182 loc_country_list_unref(enumerator
->countries
);
1184 enumerator
->countries
= loc_country_list_ref(countries
);
1189 LOC_EXPORT
struct loc_as_list
* loc_database_enumerator_get_asns(
1190 struct loc_database_enumerator
* enumerator
) {
1191 if (!enumerator
->asns
)
1194 return loc_as_list_ref(enumerator
->asns
);
1197 LOC_EXPORT
int loc_database_enumerator_set_asns(
1198 struct loc_database_enumerator
* enumerator
, struct loc_as_list
* asns
) {
1199 if (enumerator
->asns
)
1200 loc_as_list_unref(enumerator
->asns
);
1202 enumerator
->asns
= loc_as_list_ref(asns
);
1207 LOC_EXPORT
int loc_database_enumerator_set_flag(
1208 struct loc_database_enumerator
* enumerator
, enum loc_network_flags flag
) {
1209 enumerator
->flags
|= flag
;
1214 LOC_EXPORT
int loc_database_enumerator_set_family(
1215 struct loc_database_enumerator
* enumerator
, int family
) {
1216 enumerator
->family
= family
;
1221 LOC_EXPORT
int loc_database_enumerator_next_as(
1222 struct loc_database_enumerator
* enumerator
, struct loc_as
** as
) {
1225 // Do not do anything if not in AS mode
1226 if (enumerator
->mode
!= LOC_DB_ENUMERATE_ASES
)
1229 struct loc_database
* db
= enumerator
->db
;
1231 while (enumerator
->as_index
< db
->as_objects
.count
) {
1232 // Fetch the next AS
1233 int r
= loc_database_fetch_as(db
, as
, enumerator
->as_index
++);
1237 r
= loc_as_match_string(*as
, enumerator
->string
);
1239 DEBUG(enumerator
->ctx
, "AS%d (%s) matches %s\n",
1240 loc_as_get_number(*as
), loc_as_get_name(*as
), enumerator
->string
);
1251 enumerator
->as_index
= 0;
1253 // We have searched through all of them
1257 static int loc_database_enumerator_stack_push_node(
1258 struct loc_database_enumerator
* e
, off_t offset
, int i
, int depth
) {
1259 // Do not add empty nodes
1263 // Check if there is any space left on the stack
1264 if (e
->network_stack_depth
>= MAX_STACK_DEPTH
) {
1265 ERROR(e
->ctx
, "Maximum stack size reached: %d\n", e
->network_stack_depth
);
1269 // Check if the node is in range
1270 if (offset
>= (off_t
)e
->db
->network_node_objects
.count
) {
1271 ERROR(e
->ctx
, "Trying to add invalid node with offset %jd/%zu\n",
1272 offset
, e
->db
->network_node_objects
.count
);
1277 // Increase stack size
1278 int s
= ++e
->network_stack_depth
;
1280 DEBUG(e
->ctx
, "Added node %jd to stack (%d)\n", (intmax_t)offset
, depth
);
1282 e
->network_stack
[s
].offset
= offset
;
1283 e
->network_stack
[s
].i
= i
;
1284 e
->network_stack
[s
].depth
= depth
;
1289 static int loc_database_enumerator_match_network(
1290 struct loc_database_enumerator
* enumerator
, struct loc_network
* network
) {
1291 // If family is set, it must match
1292 if (enumerator
->family
&& loc_network_address_family(network
) != enumerator
->family
) {
1293 DEBUG(enumerator
->ctx
, "Filtered network %p because of family not matching\n", network
);
1297 // Match if no filter criteria is configured
1298 if (!enumerator
->countries
&& !enumerator
->asns
&& !enumerator
->flags
)
1301 // Check if the country code matches
1302 if (enumerator
->countries
&& !loc_country_list_empty(enumerator
->countries
)) {
1303 const char* country_code
= loc_network_get_country_code(network
);
1305 if (loc_country_list_contains_code(enumerator
->countries
, country_code
)) {
1306 DEBUG(enumerator
->ctx
, "Matched network %p because of its country code\n", network
);
1311 // Check if the ASN matches
1312 if (enumerator
->asns
&& !loc_as_list_empty(enumerator
->asns
)) {
1313 uint32_t asn
= loc_network_get_asn(network
);
1315 if (loc_as_list_contains_number(enumerator
->asns
, asn
)) {
1316 DEBUG(enumerator
->ctx
, "Matched network %p because of its ASN\n", network
);
1321 // Check if flags match
1322 if (enumerator
->flags
&& loc_network_has_flag(network
, enumerator
->flags
)) {
1323 DEBUG(enumerator
->ctx
, "Matched network %p because of its flags\n", network
);
1331 static int __loc_database_enumerator_next_network(
1332 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
, int filter
) {
1333 // Return top element from the stack
1335 *network
= loc_network_list_pop_first(enumerator
->stack
);
1341 // Return everything if filter isn't enabled, or only return matches
1342 if (!filter
|| loc_database_enumerator_match_network(enumerator
, *network
))
1345 // Throw away anything that doesn't match
1346 loc_network_unref(*network
);
1350 DEBUG(enumerator
->ctx
, "Called with a stack of %u nodes\n",
1351 enumerator
->network_stack_depth
);
1354 while (enumerator
->network_stack_depth
> 0) {
1355 DEBUG(enumerator
->ctx
, "Stack depth: %u\n", enumerator
->network_stack_depth
);
1357 // Get object from top of the stack
1358 struct loc_node_stack
* node
= &enumerator
->network_stack
[enumerator
->network_stack_depth
];
1360 DEBUG(enumerator
->ctx
, " Got node: %jd\n", node
->offset
);
1362 // Remove the node from the stack if we have already visited it
1363 if (enumerator
->networks_visited
[node
->offset
]) {
1364 enumerator
->network_stack_depth
--;
1368 // Mark the bits on the path correctly
1369 loc_address_set_bit(&enumerator
->network_address
,
1370 (node
->depth
> 0) ? node
->depth
- 1 : 0, node
->i
);
1372 DEBUG(enumerator
->ctx
, "Looking at node %jd\n", (intmax_t)node
->offset
);
1373 enumerator
->networks_visited
[node
->offset
]++;
1375 // Pop node from top of the stack
1376 struct loc_database_network_node_v1
* n
=
1377 (struct loc_database_network_node_v1
*)loc_database_object(enumerator
->db
,
1378 &enumerator
->db
->network_node_objects
, sizeof(*n
), node
->offset
);
1382 // Add edges to stack
1383 int r
= loc_database_enumerator_stack_push_node(enumerator
,
1384 be32toh(n
->one
), 1, node
->depth
+ 1);
1388 r
= loc_database_enumerator_stack_push_node(enumerator
,
1389 be32toh(n
->zero
), 0, node
->depth
+ 1);
1393 // Check if this node is a leaf and has a network object
1394 if (__loc_database_node_is_leaf(n
)) {
1395 off_t network_index
= be32toh(n
->network
);
1397 DEBUG(enumerator
->ctx
, "Node has a network at %jd\n", (intmax_t)network_index
);
1399 // Fetch the network object
1400 r
= loc_database_fetch_network(enumerator
->db
, network
,
1401 &enumerator
->network_address
, node
->depth
, network_index
);
1403 // Break on any errors
1407 // Return all networks when the filter is disabled, or check for match
1408 if (!filter
|| loc_database_enumerator_match_network(enumerator
, *network
))
1411 // Does not seem to be a match, so we cleanup and move on
1412 loc_network_unref(*network
);
1417 // Reached the end of the search
1421 static int __loc_database_enumerator_next_network_flattened(
1422 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
) {
1423 // Fetch the next network
1424 int r
= __loc_database_enumerator_next_network(enumerator
, network
, 1);
1428 // End if we could not read another network
1432 struct loc_network
* subnet
= NULL
;
1434 // Create a list with all subnets
1435 if (!enumerator
->subnets
) {
1436 r
= loc_network_list_new(enumerator
->ctx
, &enumerator
->subnets
);
1441 // Search all subnets from the database
1443 // Fetch the next network in line
1444 r
= __loc_database_enumerator_next_network(enumerator
, &subnet
, 0);
1446 loc_network_unref(subnet
);
1447 loc_network_list_clear(enumerator
->subnets
);
1452 // End if we did not receive another subnet
1456 // Collect all subnets in a list
1457 if (loc_network_is_subnet(*network
, subnet
)) {
1458 r
= loc_network_list_push(enumerator
->subnets
, subnet
);
1460 loc_network_unref(subnet
);
1461 loc_network_list_clear(enumerator
->subnets
);
1466 loc_network_unref(subnet
);
1470 // If this is not a subnet, we push it back onto the stack and break
1471 r
= loc_network_list_push(enumerator
->stack
, subnet
);
1473 loc_network_unref(subnet
);
1474 loc_network_list_clear(enumerator
->subnets
);
1479 loc_network_unref(subnet
);
1483 DEBUG(enumerator
->ctx
, "Found %zu subnet(s)\n",
1484 loc_network_list_size(enumerator
->subnets
));
1486 // We can abort here if the network has no subnets
1487 if (loc_network_list_empty(enumerator
->subnets
)) {
1488 loc_network_list_clear(enumerator
->subnets
);
1493 // If the network has any subnets, we will break it into smaller parts
1494 // without the subnets.
1495 struct loc_network_list
* excluded
= loc_network_exclude_list(*network
, enumerator
->subnets
);
1497 loc_network_list_clear(enumerator
->subnets
);
1501 // Merge subnets onto the stack
1502 r
= loc_network_list_merge(enumerator
->stack
, enumerator
->subnets
);
1504 loc_network_list_clear(enumerator
->subnets
);
1505 loc_network_list_unref(excluded
);
1510 // Push excluded list onto the stack
1511 r
= loc_network_list_merge(enumerator
->stack
, excluded
);
1513 loc_network_list_clear(enumerator
->subnets
);
1514 loc_network_list_unref(excluded
);
1519 loc_network_list_clear(enumerator
->subnets
);
1520 loc_network_list_unref(excluded
);
1522 // Drop the network and restart the whole process again to pick the next network
1523 loc_network_unref(*network
);
1525 return __loc_database_enumerator_next_network_flattened(enumerator
, network
);
1529 This function finds all bogons (i.e. gaps) between the input networks
1531 static int __loc_database_enumerator_next_bogon(
1532 struct loc_database_enumerator
* enumerator
, struct loc_network
** bogon
) {
1535 // Return top element from the stack
1537 *bogon
= loc_network_list_pop_first(enumerator
->stack
);
1547 struct loc_network
* network
= NULL
;
1548 struct in6_addr
* gap_start
= NULL
;
1549 struct in6_addr gap_end
= IN6ADDR_ANY_INIT
;
1552 r
= __loc_database_enumerator_next_network(enumerator
, &network
, 1);
1556 // We have read the last network
1560 const char* country_code
= loc_network_get_country_code(network
);
1563 Skip anything that does not have a country code
1565 Even if a network is part of the routing table, and the database provides
1566 an ASN, this does not mean that this is a legitimate announcement.
1568 if (country_code
&& !*country_code
) {
1569 loc_network_unref(network
);
1573 // Determine the network family
1574 int family
= loc_network_address_family(network
);
1578 gap_start
= &enumerator
->gap6_start
;
1582 gap_start
= &enumerator
->gap4_start
;
1586 ERROR(enumerator
->ctx
, "Unsupported network family %d\n", family
);
1591 const struct in6_addr
* first_address
= loc_network_get_first_address(network
);
1592 const struct in6_addr
* last_address
= loc_network_get_last_address(network
);
1594 // Skip if this network is a subnet of a former one
1595 if (loc_address_cmp(gap_start
, last_address
) >= 0) {
1596 loc_network_unref(network
);
1600 // Search where the gap could end
1601 gap_end
= *first_address
;
1602 loc_address_decrement(&gap_end
);
1605 if (loc_address_cmp(gap_start
, &gap_end
) <= 0) {
1606 r
= loc_network_list_summarize(enumerator
->ctx
,
1607 gap_start
, &gap_end
, &enumerator
->stack
);
1609 loc_network_unref(network
);
1614 // The gap now starts after this network
1615 *gap_start
= *last_address
;
1616 loc_address_increment(gap_start
);
1618 loc_network_unref(network
);
1620 // Try to return something
1621 *bogon
= loc_network_list_pop_first(enumerator
->stack
);
1630 if (!loc_address_all_zeroes(&enumerator
->gap6_start
)) {
1631 r
= loc_address_reset_last(&gap_end
, AF_INET6
);
1635 if (loc_address_cmp(&enumerator
->gap6_start
, &gap_end
) <= 0) {
1636 r
= loc_network_list_summarize(enumerator
->ctx
,
1637 &enumerator
->gap6_start
, &gap_end
, &enumerator
->stack
);
1643 loc_address_reset(&enumerator
->gap6_start
, AF_INET6
);
1646 if (!loc_address_all_zeroes(&enumerator
->gap4_start
)) {
1647 r
= loc_address_reset_last(&gap_end
, AF_INET
);
1651 if (loc_address_cmp(&enumerator
->gap4_start
, &gap_end
) <= 0) {
1652 r
= loc_network_list_summarize(enumerator
->ctx
,
1653 &enumerator
->gap4_start
, &gap_end
, &enumerator
->stack
);
1659 loc_address_reset(&enumerator
->gap4_start
, AF_INET
);
1662 // Try to return something
1663 *bogon
= loc_network_list_pop_first(enumerator
->stack
);
1668 LOC_EXPORT
int loc_database_enumerator_next_network(
1669 struct loc_database_enumerator
* enumerator
, struct loc_network
** network
) {
1670 switch (enumerator
->mode
) {
1671 case LOC_DB_ENUMERATE_NETWORKS
:
1673 if (enumerator
->flatten
)
1674 return __loc_database_enumerator_next_network_flattened(enumerator
, network
);
1676 return __loc_database_enumerator_next_network(enumerator
, network
, 1);
1678 case LOC_DB_ENUMERATE_BOGONS
:
1679 return __loc_database_enumerator_next_bogon(enumerator
, network
);
1686 LOC_EXPORT
int loc_database_enumerator_next_country(
1687 struct loc_database_enumerator
* enumerator
, struct loc_country
** country
) {
1690 // Do not do anything if not in country mode
1691 if (enumerator
->mode
!= LOC_DB_ENUMERATE_COUNTRIES
)
1694 struct loc_database
* db
= enumerator
->db
;
1696 while (enumerator
->country_index
< db
->country_objects
.count
) {
1697 // Fetch the next country
1698 int r
= loc_database_fetch_country(db
, country
, enumerator
->country_index
++);
1702 // We do not filter here, so it always is a match
1707 enumerator
->country_index
= 0;
1709 // We have searched through all of them