[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 <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;

	// 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;
};

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);

	// 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 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, 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, 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_lookup_leaf_node(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) {
	// Check if this node is a leaf node
	if (node->zero != htobe32(0xffffffff))
		return 1;

	DEBUG(db->ctx, "Node is a leaf: %jd\n", node - db->network_nodes_v0);

	// Fetch the network
	int r = loc_database_fetch_network(db, network,
		network_address, be32toh(node->one));
	if (r)
		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;
}

// Returns the highest result available
static int __loc_database_lookup_max(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, int level) {

	// If the node is a leaf node, we end here
	int r = __loc_database_lookup_leaf_node(db, address, network, network_address, node);
	if (r <= 0)
		return r;

	off_t node_index;

	// Try to go down the ones path first
	if (node->one) {
		node_index = be32toh(node->one);
		in6_addr_set_bit(network_address, level, 1);

		// Check boundaries
		if (node_index > 0 && (size_t)node_index <= db->network_nodes_count) {
			r = __loc_database_lookup_max(db, address, network, network_address,
				db->network_nodes_v0 + node_index, level + 1);

			// Abort when match was found or error
			if (r <= 0)
				return r;
		}
	}

	// ... and if that fails, we try to go down one step on a zero
	// branch and then try the ones again...
	if (node->zero) {
		node_index = be32toh(node->zero);
		in6_addr_set_bit(network_address, level, 0);

		// Check boundaries
		if (node_index > 0 && (size_t)node_index <= db->network_nodes_count) {
			r = __loc_database_lookup_max(db, address, network, network_address,
				db->network_nodes_v0 + node_index, level + 1);

			// Abort when match was found or error
			if (r <= 0)
				return r;
		}
	}

	// End of path
	return 1;
}

// 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, int level) {
	// If the node is a leaf node, we end here
	int r = __loc_database_lookup_leaf_node(db, address, network, network_address, node);
	if (r <= 0)
		return 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 we point back to root, the path ends here
	if (node_index == 0) {
		DEBUG(db->ctx, "Tree ends here\n");
		return 1;
	}

	// 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, "Could not find an exact match at %u\n", level);

	// If nothing was found, we have to search for an inexact match
	return __loc_database_lookup_max(db, address, network, network_address, node, level);
}

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