[people/ms/libloc.git] / src / database.c

/*
	libloc - A library to determine the location of someone on the Internet

	Copyright (C) 2017 IPFire Development Team <info@ipfire.org>

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	This library is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
	Lesser General Public License for more details.
*/

#include <arpa/inet.h>
#include <ctype.h>
#include <endian.h>
#include <errno.h>
#include <netinet/in.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <time.h>
#include <unistd.h>

#include <loc/libloc.h>
#include <loc/as.h>
#include <loc/database.h>
#include <loc/format.h>
#include <loc/network.h>
#include <loc/private.h>
#include <loc/stringpool.h>

struct loc_database {
	struct loc_ctx* ctx;
	int refcount;

	unsigned int version;
	time_t created_at;
	off_t vendor;
	off_t description;
	off_t license;

	// ASes in the database
	struct loc_database_as_v0* as_v0;
	size_t as_count;

	// Network tree
	struct loc_database_network_node_v0* network_nodes_v0;
	size_t network_nodes_count;

	// Networks
	struct loc_database_network_v0* networks_v0;
	size_t networks_count;

	struct loc_stringpool* pool;
};

struct loc_database_enumerator {
	struct loc_ctx* ctx;
	struct loc_database* db;
	int refcount;

	// Search string
	char* string;
	char country_code[3];

	// Index of the AS we are looking at
	unsigned int as_index;
};

static int loc_database_read_magic(struct loc_database* db, FILE* f) {
	struct loc_database_magic magic;

	// Read from file
	size_t bytes_read = fread(&magic, 1, sizeof(magic), f);

	// Check if we have been able to read enough data
	if (bytes_read < sizeof(magic)) {
		ERROR(db->ctx, "Could not read enough data to validate magic bytes\n");
		DEBUG(db->ctx, "Read %zu bytes, but needed %zu\n", bytes_read, sizeof(magic));
		return -ENOMSG;
	}

	// Compare magic bytes
	if (memcmp(LOC_DATABASE_MAGIC, magic.magic, strlen(LOC_DATABASE_MAGIC)) == 0) {
		DEBUG(db->ctx, "Magic value matches\n");

		// Parse version
		db->version = be16toh(magic.version);
		DEBUG(db->ctx, "Database version is %u\n", db->version);

		return 0;
	}

	ERROR(db->ctx, "Database format is not compatible\n");

	// Return an error
	return 1;
}

static int loc_database_read_as_section_v0(struct loc_database* db,
		FILE* f, const struct loc_database_header_v0* header) {
	off_t as_offset  = be32toh(header->as_offset);
	size_t as_length = be32toh(header->as_length);

	DEBUG(db->ctx, "Reading AS section from %jd (%zu bytes)\n", as_offset, as_length);

	if (as_length > 0) {
		db->as_v0 = mmap(NULL, as_length, PROT_READ,
			MAP_SHARED, fileno(f), as_offset);

		if (db->as_v0 == MAP_FAILED)
			return -errno;
	}

	db->as_count = as_length / sizeof(*db->as_v0);

	INFO(db->ctx, "Read %zu ASes from the database\n", db->as_count);

	return 0;
}

static int loc_database_read_network_nodes_section_v0(struct loc_database* db,
		FILE* f, const struct loc_database_header_v0* header) {
	off_t network_nodes_offset  = be32toh(header->network_tree_offset);
	size_t network_nodes_length = be32toh(header->network_tree_length);

	DEBUG(db->ctx, "Reading network nodes section from %jd (%zu bytes)\n",
		network_nodes_offset, network_nodes_length);

	if (network_nodes_length > 0) {
		db->network_nodes_v0 = mmap(NULL, network_nodes_length, PROT_READ,
			MAP_SHARED, fileno(f), network_nodes_offset);

		if (db->network_nodes_v0 == MAP_FAILED)
			return -errno;
	}

	db->network_nodes_count = network_nodes_length / sizeof(*db->network_nodes_v0);

	INFO(db->ctx, "Read %zu network nodes from the database\n", db->network_nodes_count);

	return 0;
}

static int loc_database_read_networks_section_v0(struct loc_database* db,
		FILE* f, const struct loc_database_header_v0* header) {
	off_t networks_offset  = be32toh(header->network_data_offset);
	size_t networks_length = be32toh(header->network_data_length);

	DEBUG(db->ctx, "Reading networks section from %jd (%zu bytes)\n",
		networks_offset, networks_length);

	if (networks_length > 0) {
		db->networks_v0 = mmap(NULL, networks_length, PROT_READ,
			MAP_SHARED, fileno(f), networks_offset);

		if (db->networks_v0 == MAP_FAILED)
			return -errno;
	}

	db->networks_count = networks_length / sizeof(*db->networks_v0);

	INFO(db->ctx, "Read %zu networks from the database\n", db->networks_count);

	return 0;
}

static int loc_database_read_header_v0(struct loc_database* db, FILE* f) {
	struct loc_database_header_v0 header;

	// Read from file
	size_t size = fread(&header, 1, sizeof(header), f);

	if (size < sizeof(header)) {
		ERROR(db->ctx, "Could not read enough data for header\n");
		return -ENOMSG;
	}

	// Copy over data
	db->created_at  = be64toh(header.created_at);
	db->vendor      = be32toh(header.vendor);
	db->description = be32toh(header.description);
	db->license     = be32toh(header.license);

	// Open pool
	off_t pool_offset  = be32toh(header.pool_offset);
	size_t pool_length = be32toh(header.pool_length);

	int r = loc_stringpool_open(db->ctx, &db->pool,
		f, pool_length, pool_offset);
	if (r)
		return r;

	// AS section
	r = loc_database_read_as_section_v0(db, f, &header);
	if (r)
		return r;

	// Network Nodes
	r = loc_database_read_network_nodes_section_v0(db, f, &header);
	if (r)
		return r;

	// Networks
	r = loc_database_read_networks_section_v0(db, f, &header);
	if (r)
		return r;

	return 0;
}

static int loc_database_read_header(struct loc_database* db, FILE* f) {
	switch (db->version) {
		case 0:
			return loc_database_read_header_v0(db, f);

		default:
			ERROR(db->ctx, "Incompatible database version: %u\n", db->version);
			return 1;
	}
}

static int loc_database_read(struct loc_database* db, FILE* f) {
	clock_t start = clock();

	// Read magic bytes
	int r = loc_database_read_magic(db, f);
	if (r)
		return r;

	// Read the header
	r = loc_database_read_header(db, f);
	if (r)
		return r;

	clock_t end = clock();

	INFO(db->ctx, "Opened database in %.8fs\n",
		(double)(end - start) / CLOCKS_PER_SEC);

	return 0;
}

LOC_EXPORT int loc_database_new(struct loc_ctx* ctx, struct loc_database** database, FILE* f) {
	// Fail on invalid file handle
	if (!f)
		return -EINVAL;

	struct loc_database* db = calloc(1, sizeof(*db));
	if (!db)
		return -ENOMEM;

	// Reference context
	db->ctx = loc_ref(ctx);
	db->refcount = 1;

	DEBUG(db->ctx, "Database object allocated at %p\n", db);

	int r = loc_database_read(db, f);
	if (r) {
		loc_database_unref(db);
		return r;
	}

	*database = db;

	return 0;
}

LOC_EXPORT struct loc_database* loc_database_ref(struct loc_database* db) {
	db->refcount++;

	return db;
}

static void loc_database_free(struct loc_database* db) {
	int r;

	DEBUG(db->ctx, "Releasing database %p\n", db);

	// Removing all ASes
	if (db->as_v0) {
		r = munmap(db->as_v0, db->as_count * sizeof(*db->as_v0));
		if (r)
			ERROR(db->ctx, "Could not unmap AS section: %s\n", strerror(errno));
	}

	// Remove mapped network sections
	if (db->networks_v0) {
		r = munmap(db->networks_v0, db->networks_count * sizeof(*db->networks_v0));
		if (r)
			ERROR(db->ctx, "Could not unmap networks section: %s\n", strerror(errno));
	}

	// Remove mapped network nodes section
	if (db->network_nodes_v0) {
		r = munmap(db->network_nodes_v0, db->network_nodes_count * sizeof(*db->network_nodes_v0));
		if (r)
			ERROR(db->ctx, "Could not unmap network nodes section: %s\n", strerror(errno));
	}

	loc_stringpool_unref(db->pool);

	loc_unref(db->ctx);
	free(db);
}

LOC_EXPORT struct loc_database* loc_database_unref(struct loc_database* db) {
	if (--db->refcount > 0)
		return NULL;

	loc_database_free(db);
	return NULL;
}

LOC_EXPORT time_t loc_database_created_at(struct loc_database* db) {
	return db->created_at;
}

LOC_EXPORT const char* loc_database_get_vendor(struct loc_database* db) {
	return loc_stringpool_get(db->pool, db->vendor);
}

LOC_EXPORT const char* loc_database_get_description(struct loc_database* db) {
	return loc_stringpool_get(db->pool, db->description);
}

LOC_EXPORT const char* loc_database_get_license(struct loc_database* db) {
	return loc_stringpool_get(db->pool, db->license);
}

LOC_EXPORT size_t loc_database_count_as(struct loc_database* db) {
	return db->as_count;
}

// Returns the AS at position pos
static int loc_database_fetch_as(struct loc_database* db, struct loc_as** as, off_t pos) {
	if ((size_t)pos >= db->as_count)
		return -EINVAL;

	DEBUG(db->ctx, "Fetching AS at position %jd\n", pos);

	int r;
	switch (db->version) {
		case 0:
			r = loc_as_new_from_database_v0(db->ctx, db->pool, as, db->as_v0 + pos);
			break;

		default:
			return -1;
	}

	if (r == 0) {
		DEBUG(db->ctx, "Got AS%u\n", loc_as_get_number(*as));
	}

	return r;
}

// Performs a binary search to find the AS in the list
LOC_EXPORT int loc_database_get_as(struct loc_database* db, struct loc_as** as, uint32_t number) {
	off_t lo = 0;
	off_t hi = db->as_count - 1;

	// Save start time
	clock_t start = clock();

	while (lo <= hi) {
		off_t i = (lo + hi) / 2;

		// Fetch AS in the middle between lo and hi
		int r = loc_database_fetch_as(db, as, i);
		if (r)
			return r;

		// Check if this is a match
		uint32_t as_number = loc_as_get_number(*as);
		if (as_number == number) {
			clock_t end = clock();

			// Log how fast this has been
			DEBUG(db->ctx, "Found AS%u in %.8fs\n", as_number,
				(double)(end - start) / CLOCKS_PER_SEC);

			return 0;
		}

		// If it wasn't, we release the AS and
		// adjust our search pointers
		loc_as_unref(*as);

		if (as_number < number) {
			lo = i + 1;
		} else
			hi = i - 1;
	}

	// Nothing found
	*as = NULL;

	return 1;
}

// Returns the network at position pos
static int loc_database_fetch_network(struct loc_database* db, struct loc_network** network,
		struct in6_addr* address, unsigned int prefix, off_t pos) {
	if ((size_t)pos >= db->networks_count)
		return -EINVAL;

	DEBUG(db->ctx, "Fetching network at position %jd\n", pos);

	int r;
	switch (db->version) {
		case 0:
			r = loc_network_new_from_database_v0(db->ctx, network,
				address, prefix, db->networks_v0 + pos);
			break;

		default:
			return -1;
	}

	if (r == 0) {
		char* string = loc_network_str(*network);
		DEBUG(db->ctx, "Got network %s\n", string);
		free(string);
	}

	return r;
}

static int __loc_database_node_is_leaf(const struct loc_database_network_node_v0* node) {
	return (node->network != htobe32(0xffffffff));
}

static int __loc_database_lookup_handle_leaf(struct loc_database* db, const struct in6_addr* address,
		struct loc_network** network, struct in6_addr* network_address, unsigned int prefix,
		const struct loc_database_network_node_v0* node) {
	off_t network_index = be32toh(node->network);

	DEBUG(db->ctx, "Handling leaf node at %jd (%jd)\n", node - db->network_nodes_v0, network_index);

	// Fetch the network
	int r = loc_database_fetch_network(db, network,
		network_address, prefix, network_index);
	if (r) {
		ERROR(db->ctx, "Could not fetch network %jd from database\n", network_index);
		return r;
	}

	// Check if the given IP address is inside the network
	r = loc_network_match_address(*network, address);
	if (r) {
		DEBUG(db->ctx, "Searched address is not part of the network\n");

		loc_network_unref(*network);
		*network = NULL;
		return 1;
	}

	// A network was found and the IP address matches
	return 0;
}

// Searches for an exact match along the path
static int __loc_database_lookup(struct loc_database* db, const struct in6_addr* address,
		struct loc_network** network, struct in6_addr* network_address,
		const struct loc_database_network_node_v0* node, unsigned int level) {
	int r;
	off_t node_index;

	// Follow the path
	int bit = in6_addr_get_bit(address, level);
	in6_addr_set_bit(network_address, level, bit);

	if (bit == 0)
		node_index = be32toh(node->zero);
	else
		node_index = be32toh(node->one);

	// If the node index is zero, the tree ends here
	// and we cannot descend any further
	if (node_index > 0) {
		// Check boundaries
		if ((size_t)node_index >= db->network_nodes_count)
			return -EINVAL;

		// Move on to the next node
		r = __loc_database_lookup(db, address, network, network_address,
			db->network_nodes_v0 + node_index, level + 1);

		// End here if a result was found
		if (r == 0)
			return r;

		// Raise any errors
		else if (r < 0)
			return r;

		DEBUG(db->ctx, "No match found below level %u\n", level);
	} else {
		DEBUG(db->ctx, "Tree ended at level %u\n", level);
	}

	// If this node has a leaf, we will check if it matches
	if (__loc_database_node_is_leaf(node)) {
		r = __loc_database_lookup_handle_leaf(db, address, network, network_address, level, node);
		if (r <= 0)
			return r;
	}

	return 1;
}

LOC_EXPORT int loc_database_lookup(struct loc_database* db,
		struct in6_addr* address, struct loc_network** network) {
	struct in6_addr network_address;
	memset(&network_address, 0, sizeof(network_address));

	*network = NULL;

	// Save start time
	clock_t start = clock();

	int r = __loc_database_lookup(db, address, network, &network_address,
		db->network_nodes_v0, 0);

	clock_t end = clock();

	// Log how fast this has been
	DEBUG(db->ctx, "Executed network search in %.8fs\n",
		(double)(end - start) / CLOCKS_PER_SEC);

	return r;
}

LOC_EXPORT int loc_database_lookup_from_string(struct loc_database* db,
		const char* string, struct loc_network** network) {
	struct in6_addr address;

	int r = loc_parse_address(db->ctx, string, &address);
	if (r)
		return r;

	return loc_database_lookup(db, &address, network);
}

// Enumerator

LOC_EXPORT int loc_database_enumerator_new(struct loc_database_enumerator** enumerator, struct loc_database* db) {
	struct loc_database_enumerator* e = calloc(1, sizeof(*e));
	if (!e)
		return -ENOMEM;

	// Reference context
	e->ctx = loc_ref(db->ctx);
	e->db = loc_database_ref(db);
	e->refcount = 1;

	DEBUG(e->ctx, "Database enumerator object allocated at %p\n", e);

	*enumerator = e;
	return 0;
}

LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_ref(struct loc_database_enumerator* enumerator) {
	enumerator->refcount++;

	return enumerator;
}

static void loc_database_enumerator_free(struct loc_database_enumerator* enumerator) {
	DEBUG(enumerator->ctx, "Releasing database enumerator %p\n", enumerator);

	// Release all references
	loc_database_unref(enumerator->db);
	loc_unref(enumerator->ctx);

	if (enumerator->string)
		free(enumerator->string);

	free(enumerator);
}

LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_unref(struct loc_database_enumerator* enumerator) {
	if (!enumerator)
		return NULL;

	if (--enumerator->refcount > 0)
		return enumerator;

	loc_database_enumerator_free(enumerator);
	return NULL;
}

LOC_EXPORT int loc_database_enumerator_set_string(struct loc_database_enumerator* enumerator, const char* string) {
	enumerator->string = strdup(string);

	// Make the string lowercase
	for (char *p = enumerator->string; *p; p++)
		*p = tolower(*p);

	return 0;
}

LOC_EXPORT int loc_database_enumerator_set_country_code(struct loc_database_enumerator* enumerator, const char* country_code) {
	// Set empty country code
	if (!country_code || !*country_code) {
		*enumerator->country_code = '\0';
		return 0;
	}

	// Country codes must be two characters
	if (strlen(country_code) != 2)
		return -EINVAL;

	for (unsigned int i = 0; i < 3; i++) {
		enumerator->country_code[i] = country_code[i];
	}

	return 0;
}

LOC_EXPORT struct loc_as* loc_database_enumerator_next_as(struct loc_database_enumerator* enumerator) {
	struct loc_database* db = enumerator->db;
	struct loc_as* as;

	while (enumerator->as_index < db->as_count) {
		// Fetch the next AS
		int r = loc_database_fetch_as(db, &as, enumerator->as_index++);
		if (r)
			return NULL;

		r = loc_as_match_string(as, enumerator->string);
		if (r == 1) {
			DEBUG(enumerator->ctx, "AS%d (%s) matches %s\n",
				loc_as_get_number(as), loc_as_get_name(as), enumerator->string);

			return as;
		}

		// No match
		loc_as_unref(as);
	}

	// Reset the index
	enumerator->as_index = 0;

	// We have searched through all of them
	return NULL;
}
Commit	Line	Data
2601e83e MT	1	/*
	2	libloc - A library to determine the location of someone on the Internet
	3
	4	Copyright (C) 2017 IPFire Development Team <info@ipfire.org>
	5
	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.
	10
	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.
	15	*/
	16
2a30e4de	17	#include <arpa/inet.h>
d3d8ede6	18	#include <ctype.h>
0676cd80	19	#include <endian.h>
2601e83e	20	#include <errno.h>
10778041	21	#include <netinet/in.h>
2601e83e MT	22	#include <stddef.h>
	23	#include <stdint.h>
	24	#include <stdio.h>
	25	#include <stdlib.h>
	26	#include <string.h>
c182393f	27	#include <sys/mman.h>
2601e83e	28	#include <sys/types.h>
96ea74a5	29	#include <time.h>
3f35869a	30	#include <unistd.h>
2601e83e MT	31
2601e83e MT	32	#include <loc/libloc.h>
9fc7f001 MT	33	#include <loc/as.h>
9fc7f001 MT	34	#include <loc/database.h>
a5db3e49	35	#include <loc/format.h>
10778041	36	#include <loc/network.h>
9fc7f001 MT	37	#include <loc/private.h>
9fc7f001 MT	38	#include <loc/stringpool.h>
2601e83e MT	39
	40	struct loc_database {
	41	struct loc_ctx* ctx;
	42	int refcount;
	43
	44	unsigned int version;
96ea74a5	45	time_t created_at;
2601e83e MT	46	off_t vendor;
2601e83e MT	47	off_t description;
4bf49d00	48	off_t license;
2601e83e	49
a5db3e49	50	// ASes in the database
c182393f	51	struct loc_database_as_v0* as_v0;
a5db3e49 MT	52	size_t as_count;
a5db3e49 MT	53
f66b7b09 MT	54	// Network tree
	55	struct loc_database_network_node_v0* network_nodes_v0;
	56	size_t network_nodes_count;
	57
a735a563 MT	58	// Networks
	59	struct loc_database_network_v0* networks_v0;
	60	size_t networks_count;
	61
2601e83e MT	62	struct loc_stringpool* pool;
	63	};
	64
7e13db74 MT	65	struct loc_database_enumerator {
	66	struct loc_ctx* ctx;
	67	struct loc_database* db;
	68	int refcount;
d3d8ede6 MT	69
	70	// Search string
	71	char* string;
35bb3a32	72	char country_code[3];
d3d8ede6 MT	73
	74	// Index of the AS we are looking at
	75	unsigned int as_index;
7e13db74 MT	76	};
7e13db74 MT	77
a7431f1a	78	static int loc_database_read_magic(struct loc_database* db, FILE* f) {
2601e83e MT	79	struct loc_database_magic magic;
	80
	81	// Read from file
a7431f1a	82	size_t bytes_read = fread(&magic, 1, sizeof(magic), f);
2601e83e MT	83
	84	// Check if we have been able to read enough data
	85	if (bytes_read < sizeof(magic)) {
	86	ERROR(db->ctx, "Could not read enough data to validate magic bytes\n");
	87	DEBUG(db->ctx, "Read %zu bytes, but needed %zu\n", bytes_read, sizeof(magic));
	88	return -ENOMSG;
	89	}
	90
	91	// Compare magic bytes
	92	if (memcmp(LOC_DATABASE_MAGIC, magic.magic, strlen(LOC_DATABASE_MAGIC)) == 0) {
	93	DEBUG(db->ctx, "Magic value matches\n");
	94
	95	// Parse version
0676cd80	96	db->version = be16toh(magic.version);
2601e83e MT	97	DEBUG(db->ctx, "Database version is %u\n", db->version);
	98
	99	return 0;
	100	}
	101
	102	ERROR(db->ctx, "Database format is not compatible\n");
	103
	104	// Return an error
	105	return 1;
	106	}
	107
a5db3e49	108	static int loc_database_read_as_section_v0(struct loc_database* db,
edb4ba7c MT	109	FILE* f, const struct loc_database_header_v0* header) {
	110	off_t as_offset = be32toh(header->as_offset);
	111	size_t as_length = be32toh(header->as_length);
	112
c182393f	113	DEBUG(db->ctx, "Reading AS section from %jd (%zu bytes)\n", as_offset, as_length);
a5db3e49	114
c182393f MT	115	if (as_length > 0) {
c182393f MT	116	db->as_v0 = mmap(NULL, as_length, PROT_READ,
a7431f1a	117	MAP_SHARED, fileno(f), as_offset);
a5db3e49	118
c182393f MT	119	if (db->as_v0 == MAP_FAILED)
c182393f MT	120	return -errno;
a5db3e49 MT	121	}
a5db3e49 MT	122
c182393f MT	123	db->as_count = as_length / sizeof(*db->as_v0);
c182393f MT	124
a5db3e49 MT	125	INFO(db->ctx, "Read %zu ASes from the database\n", db->as_count);
	126
	127	return 0;
	128	}
	129
f66b7b09	130	static int loc_database_read_network_nodes_section_v0(struct loc_database* db,
edb4ba7c MT	131	FILE* f, const struct loc_database_header_v0* header) {
	132	off_t network_nodes_offset = be32toh(header->network_tree_offset);
	133	size_t network_nodes_length = be32toh(header->network_tree_length);
	134
f66b7b09 MT	135	DEBUG(db->ctx, "Reading network nodes section from %jd (%zu bytes)\n",
	136	network_nodes_offset, network_nodes_length);
	137
	138	if (network_nodes_length > 0) {
	139	db->network_nodes_v0 = mmap(NULL, network_nodes_length, PROT_READ,
	140	MAP_SHARED, fileno(f), network_nodes_offset);
	141
	142	if (db->network_nodes_v0 == MAP_FAILED)
	143	return -errno;
	144	}
	145
	146	db->network_nodes_count = network_nodes_length / sizeof(*db->network_nodes_v0);
	147
	148	INFO(db->ctx, "Read %zu network nodes from the database\n", db->network_nodes_count);
	149
	150	return 0;
	151	}
	152
a735a563 MT	153	static int loc_database_read_networks_section_v0(struct loc_database* db,
	154	FILE* f, const struct loc_database_header_v0* header) {
	155	off_t networks_offset = be32toh(header->network_data_offset);
	156	size_t networks_length = be32toh(header->network_data_length);
	157
	158	DEBUG(db->ctx, "Reading networks section from %jd (%zu bytes)\n",
	159	networks_offset, networks_length);
	160
	161	if (networks_length > 0) {
	162	db->networks_v0 = mmap(NULL, networks_length, PROT_READ,
	163	MAP_SHARED, fileno(f), networks_offset);
	164
	165	if (db->networks_v0 == MAP_FAILED)
	166	return -errno;
	167	}
	168
	169	db->networks_count = networks_length / sizeof(*db->networks_v0);
	170
	171	INFO(db->ctx, "Read %zu networks from the database\n", db->networks_count);
	172
	173	return 0;
	174	}
	175
a7431f1a	176	static int loc_database_read_header_v0(struct loc_database* db, FILE* f) {
2601e83e MT	177	struct loc_database_header_v0 header;
	178
	179	// Read from file
a7431f1a	180	size_t size = fread(&header, 1, sizeof(header), f);
2601e83e MT	181
	182	if (size < sizeof(header)) {
	183	ERROR(db->ctx, "Could not read enough data for header\n");
	184	return -ENOMSG;
	185	}
	186
	187	// Copy over data
96ea74a5	188	db->created_at = be64toh(header.created_at);
0676cd80 MT	189	db->vendor = be32toh(header.vendor);
0676cd80 MT	190	db->description = be32toh(header.description);
4bf49d00	191	db->license = be32toh(header.license);
2601e83e MT	192
2601e83e MT	193	// Open pool
0676cd80 MT	194	off_t pool_offset = be32toh(header.pool_offset);
0676cd80 MT	195	size_t pool_length = be32toh(header.pool_length);
2601e83e	196
0e974d4b	197	int r = loc_stringpool_open(db->ctx, &db->pool,
a7431f1a	198	f, pool_length, pool_offset);
2601e83e MT	199	if (r)
	200	return r;
	201
a5db3e49	202	// AS section
edb4ba7c	203	r = loc_database_read_as_section_v0(db, f, &header);
a5db3e49 MT	204	if (r)
	205	return r;
	206
f66b7b09	207	// Network Nodes
edb4ba7c	208	r = loc_database_read_network_nodes_section_v0(db, f, &header);
f66b7b09 MT	209	if (r)
	210	return r;
	211
a735a563 MT	212	// Networks
	213	r = loc_database_read_networks_section_v0(db, f, &header);
	214	if (r)
	215	return r;
	216
2601e83e MT	217	return 0;
	218	}
	219
a7431f1a	220	static int loc_database_read_header(struct loc_database* db, FILE* f) {
2601e83e MT	221	switch (db->version) {
2601e83e MT	222	case 0:
a7431f1a	223	return loc_database_read_header_v0(db, f);
2601e83e MT	224
	225	default:
	226	ERROR(db->ctx, "Incompatible database version: %u\n", db->version);
	227	return 1;
	228	}
	229	}
	230
a7431f1a	231	static int loc_database_read(struct loc_database* db, FILE* f) {
02879100 MT	232	clock_t start = clock();
	233
	234	// Read magic bytes
a7431f1a	235	int r = loc_database_read_magic(db, f);
02879100 MT	236	if (r)
	237	return r;
	238
	239	// Read the header
a7431f1a	240	r = loc_database_read_header(db, f);
02879100 MT	241	if (r)
	242	return r;
	243
	244	clock_t end = clock();
	245
	246	INFO(db->ctx, "Opened database in %.8fs\n",
	247	(double)(end - start) / CLOCKS_PER_SEC);
	248
	249	return 0;
	250	}
	251
c182393f	252	LOC_EXPORT int loc_database_new(struct loc_ctx* ctx, struct loc_database** database, FILE* f) {
a7431f1a MT	253	// Fail on invalid file handle
	254	if (!f)
	255	return -EINVAL;
	256
c182393f MT	257	struct loc_database* db = calloc(1, sizeof(*db));
	258	if (!db)
	259	return -ENOMEM;
	260
	261	// Reference context
	262	db->ctx = loc_ref(ctx);
	263	db->refcount = 1;
	264
	265	DEBUG(db->ctx, "Database object allocated at %p\n", db);
	266
a7431f1a	267	int r = loc_database_read(db, f);
02879100 MT	268	if (r) {
02879100 MT	269	loc_database_unref(db);
2601e83e	270	return r;
02879100	271	}
2601e83e	272
c182393f MT	273	*database = db;
c182393f MT	274
2601e83e	275	return 0;
2601e83e MT	276	}
2601e83e MT	277
c182393f MT	278	LOC_EXPORT struct loc_database* loc_database_ref(struct loc_database* db) {
	279	db->refcount++;
	280
	281	return db;
8f5b676a MT	282	}
8f5b676a MT	283
c182393f	284	static void loc_database_free(struct loc_database* db) {
f10ebc2d MT	285	int r;
f10ebc2d MT	286
c182393f	287	DEBUG(db->ctx, "Releasing database %p\n", db);
c34e76f1	288
c182393f MT	289	// Removing all ASes
c182393f MT	290	if (db->as_v0) {
f10ebc2d	291	r = munmap(db->as_v0, db->as_count * sizeof(*db->as_v0));
c182393f MT	292	if (r)
	293	ERROR(db->ctx, "Could not unmap AS section: %s\n", strerror(errno));
	294	}
c34e76f1	295
f10ebc2d MT	296	// Remove mapped network sections
	297	if (db->networks_v0) {
	298	r = munmap(db->networks_v0, db->networks_count * sizeof(*db->networks_v0));
	299	if (r)
	300	ERROR(db->ctx, "Could not unmap networks section: %s\n", strerror(errno));
	301	}
	302
	303	// Remove mapped network nodes section
	304	if (db->network_nodes_v0) {
	305	r = munmap(db->network_nodes_v0, db->network_nodes_count * sizeof(*db->network_nodes_v0));
	306	if (r)
	307	ERROR(db->ctx, "Could not unmap network nodes section: %s\n", strerror(errno));
	308	}
	309
c182393f	310	loc_stringpool_unref(db->pool);
c34e76f1	311
c182393f MT	312	loc_unref(db->ctx);
c182393f MT	313	free(db);
c34e76f1 MT	314	}
c34e76f1 MT	315
c182393f MT	316	LOC_EXPORT struct loc_database* loc_database_unref(struct loc_database* db) {
	317	if (--db->refcount > 0)
	318	return NULL;
78ace4ed	319
c182393f MT	320	loc_database_free(db);
	321	return NULL;
	322	}
78ace4ed	323
c182393f MT	324	LOC_EXPORT time_t loc_database_created_at(struct loc_database* db) {
	325	return db->created_at;
	326	}
78ace4ed	327
c182393f MT	328	LOC_EXPORT const char* loc_database_get_vendor(struct loc_database* db) {
	329	return loc_stringpool_get(db->pool, db->vendor);
	330	}
78ace4ed	331
c182393f MT	332	LOC_EXPORT const char* loc_database_get_description(struct loc_database* db) {
	333	return loc_stringpool_get(db->pool, db->description);
	334	}
78ace4ed	335
4bf49d00 MT	336	LOC_EXPORT const char* loc_database_get_license(struct loc_database* db) {
	337	return loc_stringpool_get(db->pool, db->license);
	338	}
	339
c182393f MT	340	LOC_EXPORT size_t loc_database_count_as(struct loc_database* db) {
c182393f MT	341	return db->as_count;
78ace4ed MT	342	}
78ace4ed MT	343
c182393f MT	344	// Returns the AS at position pos
	345	static int loc_database_fetch_as(struct loc_database* db, struct loc_as** as, off_t pos) {
	346	if ((size_t)pos >= db->as_count)
	347	return -EINVAL;
2601e83e	348
c182393f	349	DEBUG(db->ctx, "Fetching AS at position %jd\n", pos);
2601e83e MT	350
2601e83e MT	351	int r;
c182393f MT	352	switch (db->version) {
	353	case 0:
	354	r = loc_as_new_from_database_v0(db->ctx, db->pool, as, db->as_v0 + pos);
	355	break;
2601e83e	356
c182393f MT	357	default:
	358	return -1;
	359	}
2601e83e	360
c182393f MT	361	if (r == 0) {
c182393f MT	362	DEBUG(db->ctx, "Got AS%u\n", loc_as_get_number(*as));
2601e83e	363	}
2601e83e	364
c182393f MT	365	return r;
c182393f MT	366	}
c34e76f1	367
c182393f MT	368	// Performs a binary search to find the AS in the list
	369	LOC_EXPORT int loc_database_get_as(struct loc_database* db, struct loc_as** as, uint32_t number) {
	370	off_t lo = 0;
	371	off_t hi = db->as_count - 1;
c34e76f1	372
8f3e2a06 MT	373	// Save start time
	374	clock_t start = clock();
	375
c182393f MT	376	while (lo <= hi) {
c182393f MT	377	off_t i = (lo + hi) / 2;
8f5b676a	378
c182393f MT	379	// Fetch AS in the middle between lo and hi
	380	int r = loc_database_fetch_as(db, as, i);
	381	if (r)
	382	return r;
a5db3e49	383
c182393f MT	384	// Check if this is a match
c182393f MT	385	uint32_t as_number = loc_as_get_number(*as);
8f3e2a06 MT	386	if (as_number == number) {
	387	clock_t end = clock();
	388
	389	// Log how fast this has been
	390	DEBUG(db->ctx, "Found AS%u in %.8fs\n", as_number,
	391	(double)(end - start) / CLOCKS_PER_SEC);
	392
c182393f	393	return 0;
8f3e2a06	394	}
c182393f MT	395
	396	// If it wasn't, we release the AS and
	397	// adjust our search pointers
	398	loc_as_unref(*as);
	399
	400	if (as_number < number) {
	401	lo = i + 1;
	402	} else
	403	hi = i - 1;
	404	}
2601e83e	405
c182393f MT	406	// Nothing found
c182393f MT	407	*as = NULL;
2601e83e	408
8f3e2a06	409	return 1;
2601e83e	410	}
10778041 MT	411
10778041 MT	412	// Returns the network at position pos
39a55353 MT	413	static int loc_database_fetch_network(struct loc_database* db, struct loc_network** network,
39a55353 MT	414	struct in6_addr* address, unsigned int prefix, off_t pos) {
10778041 MT	415	if ((size_t)pos >= db->networks_count)
	416	return -EINVAL;
	417
	418	DEBUG(db->ctx, "Fetching network at position %jd\n", pos);
	419
	420	int r;
	421	switch (db->version) {
	422	case 0:
39a55353 MT	423	r = loc_network_new_from_database_v0(db->ctx, network,
39a55353 MT	424	address, prefix, db->networks_v0 + pos);
10778041 MT	425	break;
	426
	427	default:
	428	return -1;
	429	}
	430
	431	if (r == 0) {
	432	char* string = loc_network_str(*network);
	433	DEBUG(db->ctx, "Got network %s\n", string);
	434	free(string);
	435	}
	436
	437	return r;
	438	}
2a30e4de	439
025ef489	440	static int __loc_database_node_is_leaf(const struct loc_database_network_node_v0* node) {
39a55353	441	return (node->network != htobe32(0xffffffff));
025ef489 MT	442	}
	443
	444	static int __loc_database_lookup_handle_leaf(struct loc_database* db, const struct in6_addr* address,
39a55353	445	struct loc_network** network, struct in6_addr* network_address, unsigned int prefix,
2a30e4de	446	const struct loc_database_network_node_v0* node) {
39a55353 MT	447	off_t network_index = be32toh(node->network);
	448
	449	DEBUG(db->ctx, "Handling leaf node at %jd (%jd)\n", node - db->network_nodes_v0, network_index);
2a30e4de MT	450
	451	// Fetch the network
	452	int r = loc_database_fetch_network(db, network,
39a55353	453	network_address, prefix, network_index);
e85e2b0b MT	454	if (r) {
e85e2b0b MT	455	ERROR(db->ctx, "Could not fetch network %jd from database\n", network_index);
2a30e4de	456	return r;
e85e2b0b	457	}
39a55353	458
2a30e4de MT	459	// Check if the given IP address is inside the network
	460	r = loc_network_match_address(*network, address);
	461	if (r) {
	462	DEBUG(db->ctx, "Searched address is not part of the network\n");
	463
	464	loc_network_unref(*network);
	465	*network = NULL;
	466	return 1;
	467	}
	468
	469	// A network was found and the IP address matches
	470	return 0;
	471	}
	472
2a30e4de MT	473	// Searches for an exact match along the path
	474	static int __loc_database_lookup(struct loc_database* db, const struct in6_addr* address,
	475	struct loc_network** network, struct in6_addr* network_address,
f66f15e1	476	const struct loc_database_network_node_v0* node, unsigned int level) {
025ef489	477	int r;
2a30e4de MT	478	off_t node_index;
	479
	480	// Follow the path
	481	int bit = in6_addr_get_bit(address, level);
	482	in6_addr_set_bit(network_address, level, bit);
	483
	484	if (bit == 0)
	485	node_index = be32toh(node->zero);
	486	else
	487	node_index = be32toh(node->one);
	488
9086d2b1 MT	489	// If the node index is zero, the tree ends here
	490	// and we cannot descend any further
	491	if (node_index > 0) {
	492	// Check boundaries
	493	if ((size_t)node_index >= db->network_nodes_count)
	494	return -EINVAL;
2a30e4de	495
9086d2b1 MT	496	// Move on to the next node
	497	r = __loc_database_lookup(db, address, network, network_address,
	498	db->network_nodes_v0 + node_index, level + 1);
2a30e4de	499
9086d2b1 MT	500	// End here if a result was found
	501	if (r == 0)
	502	return r;
2a30e4de	503
9086d2b1 MT	504	// Raise any errors
	505	else if (r < 0)
	506	return r;
ec1d9681 MT	507
	508	DEBUG(db->ctx, "No match found below level %u\n", level);
	509	} else {
	510	DEBUG(db->ctx, "Tree ended at level %u\n", level);
9086d2b1	511	}
2a30e4de	512
9086d2b1 MT	513	// If this node has a leaf, we will check if it matches
	514	if (__loc_database_node_is_leaf(node)) {
	515	r = __loc_database_lookup_handle_leaf(db, address, network, network_address, level, node);
	516	if (r <= 0)
	517	return r;
	518	}
2a30e4de	519
ec1d9681	520	return 1;
2a30e4de MT	521	}
	522
	523	LOC_EXPORT int loc_database_lookup(struct loc_database* db,
	524	struct in6_addr* address, struct loc_network** network) {
	525	struct in6_addr network_address;
	526	memset(&network_address, 0, sizeof(network_address));
	527
	528	*network = NULL;
	529
	530	// Save start time
	531	clock_t start = clock();
	532
	533	int r = __loc_database_lookup(db, address, network, &network_address,
	534	db->network_nodes_v0, 0);
	535
	536	clock_t end = clock();
	537
	538	// Log how fast this has been
	539	DEBUG(db->ctx, "Executed network search in %.8fs\n",
	540	(double)(end - start) / CLOCKS_PER_SEC);
	541
	542	return r;
	543	}
	544
	545	LOC_EXPORT int loc_database_lookup_from_string(struct loc_database* db,
	546	const char* string, struct loc_network** network) {
	547	struct in6_addr address;
	548
	549	int r = loc_parse_address(db->ctx, string, &address);
	550	if (r)
	551	return r;
	552
	553	return loc_database_lookup(db, &address, network);
	554	}
7e13db74 MT	555
	556	// Enumerator
	557
	558	LOC_EXPORT int loc_database_enumerator_new(struct loc_database_enumerator** enumerator, struct loc_database* db) {
	559	struct loc_database_enumerator* e = calloc(1, sizeof(*e));
	560	if (!e)
	561	return -ENOMEM;
	562
	563	// Reference context
	564	e->ctx = loc_ref(db->ctx);
	565	e->db = loc_database_ref(db);
	566	e->refcount = 1;
	567
	568	DEBUG(e->ctx, "Database enumerator object allocated at %p\n", e);
	569
	570	*enumerator = e;
	571	return 0;
	572	}
	573
	574	LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_ref(struct loc_database_enumerator* enumerator) {
	575	enumerator->refcount++;
	576
	577	return enumerator;
	578	}
	579
	580	static void loc_database_enumerator_free(struct loc_database_enumerator* enumerator) {
	581	DEBUG(enumerator->ctx, "Releasing database enumerator %p\n", enumerator);
	582
	583	// Release all references
	584	loc_database_unref(enumerator->db);
	585	loc_unref(enumerator->ctx);
	586
d3d8ede6 MT	587	if (enumerator->string)
	588	free(enumerator->string);
	589
7e13db74 MT	590	free(enumerator);
	591	}
	592
	593	LOC_EXPORT struct loc_database_enumerator* loc_database_enumerator_unref(struct loc_database_enumerator* enumerator) {
	594	if (!enumerator)
	595	return NULL;
	596
	597	if (--enumerator->refcount > 0)
	598	return enumerator;
	599
	600	loc_database_enumerator_free(enumerator);
	601	return NULL;
	602	}
d3d8ede6 MT	603
	604	LOC_EXPORT int loc_database_enumerator_set_string(struct loc_database_enumerator* enumerator, const char* string) {
	605	enumerator->string = strdup(string);
	606
	607	// Make the string lowercase
	608	for (char p = enumerator->string; p; p++)
	609	p = tolower(p);
	610
	611	return 0;
	612	}
	613
35bb3a32 MT	614	LOC_EXPORT int loc_database_enumerator_set_country_code(struct loc_database_enumerator* enumerator, const char* country_code) {
	615	// Set empty country code
	616	if (!country_code \|\| !*country_code) {
	617	*enumerator->country_code = '\0';
	618	return 0;
	619	}
	620
	621	// Country codes must be two characters
	622	if (strlen(country_code) != 2)
	623	return -EINVAL;
	624
	625	for (unsigned int i = 0; i < 3; i++) {
	626	enumerator->country_code[i] = country_code[i];
	627	}
	628
	629	return 0;
	630	}
	631
d3d8ede6 MT	632	LOC_EXPORT struct loc_as* loc_database_enumerator_next_as(struct loc_database_enumerator* enumerator) {
	633	struct loc_database* db = enumerator->db;
	634	struct loc_as* as;
	635
	636	while (enumerator->as_index < db->as_count) {
	637	// Fetch the next AS
	638	int r = loc_database_fetch_as(db, &as, enumerator->as_index++);
	639	if (r)
	640	return NULL;
	641
	642	r = loc_as_match_string(as, enumerator->string);
273948cf	643	if (r == 1) {
d3d8ede6 MT	644	DEBUG(enumerator->ctx, "AS%d (%s) matches %s\n",
	645	loc_as_get_number(as), loc_as_get_name(as), enumerator->string);
	646
	647	return as;
	648	}
	649
	650	// No match
	651	loc_as_unref(as);
	652	}
	653
	654	// Reset the index
	655	enumerator->as_index = 0;
	656
	657	// We have searched through all of them
	658	return NULL;
	659	}