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

	// 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, 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_node_is_leaf(const struct loc_database_network_node_v0* node) {
	return (node->zero == 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,
		const struct loc_database_network_node_v0* node) {
	DEBUG(db->ctx, "Handling leaf node at %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, unsigned int level) {
	// If the node is a leaf node, we end here
	if (__loc_database_node_is_leaf(node))
		return __loc_database_lookup_handle_leaf(db, address, network, network_address, node);

	int 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, unsigned int level) {
	// If the node is a leaf node, we end here
	if (__loc_database_node_is_leaf(node))
		return __loc_database_lookup_handle_leaf(db, address, network, network_address, node);

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

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