[location/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));
	}

	if (db->pool)
		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 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;
	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
89fe2c23 MT	309	if (db->pool)
89fe2c23 MT	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
	614	LOC_EXPORT struct loc_as* loc_database_enumerator_next_as(struct loc_database_enumerator* enumerator) {
	615	struct loc_database* db = enumerator->db;
	616	struct loc_as* as;
	617
	618	while (enumerator->as_index < db->as_count) {
	619	// Fetch the next AS
	620	int r = loc_database_fetch_as(db, &as, enumerator->as_index++);
	621	if (r)
	622	return NULL;
	623
	624	r = loc_as_match_string(as, enumerator->string);
273948cf	625	if (r == 1) {
d3d8ede6 MT	626	DEBUG(enumerator->ctx, "AS%d (%s) matches %s\n",
	627	loc_as_get_number(as), loc_as_get_name(as), enumerator->string);
	628
	629	return as;
	630	}
	631
	632	// No match
	633	loc_as_unref(as);
	634	}
	635
	636	// Reset the index
	637	enumerator->as_index = 0;
	638
	639	// We have searched through all of them
	640	return NULL;
	641	}