[location/libloc.git] / src / network.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 <assert.h>
#include <endian.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <loc/libloc.h>
#include <loc/country.h>
#include <loc/network.h>
#include <loc/private.h>

struct loc_network {
	struct loc_ctx* ctx;
	int refcount;

	struct in6_addr start_address;
	unsigned int prefix;

	char country_code[3];
	uint32_t asn;
	enum loc_network_flags flags;
};

static int valid_prefix(struct in6_addr* address, unsigned int prefix) {
	// The prefix cannot be larger than 128 bits
	if (prefix > 128)
		return 1;

	// And the prefix cannot be zero
	if (prefix == 0)
		return 1;

	// For IPv4-mapped addresses the prefix has to be 96 or lager
	if (IN6_IS_ADDR_V4MAPPED(address) && prefix <= 96)
		return 1;

	return 0;
}

static struct in6_addr prefix_to_bitmask(unsigned int prefix) {
	struct in6_addr bitmask;

	for (unsigned int i = 0; i < 16; i++)
		bitmask.s6_addr[i] = 0;

	for (int i = prefix, j = 0; i > 0; i -= 8, j++) {
		if (i >= 8)
			bitmask.s6_addr[j] = 0xff;
		else
			bitmask.s6_addr[j] = 0xff << (8 - i);
	}

	return bitmask;
}

static struct in6_addr make_start_address(const struct in6_addr* address, unsigned int prefix) {
	struct in6_addr a;
	struct in6_addr bitmask = prefix_to_bitmask(prefix);

	// Perform bitwise AND
	for (unsigned int i = 0; i < 4; i++)
		a.s6_addr32[i] = address->s6_addr32[i] & bitmask.s6_addr32[i];

	return a;
}

static struct in6_addr make_last_address(const struct in6_addr* address, unsigned int prefix) {
	struct in6_addr a;
	struct in6_addr bitmask = prefix_to_bitmask(prefix);

	// Perform bitwise OR
	for (unsigned int i = 0; i < 4; i++)
		a.s6_addr32[i] = address->s6_addr32[i] | ~bitmask.s6_addr32[i];

	return a;
}

LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
		struct in6_addr* address, unsigned int prefix) {
	// Address cannot be unspecified
	if (IN6_IS_ADDR_UNSPECIFIED(address)) {
		DEBUG(ctx, "Start address is unspecified\n");
		return -EINVAL;
	}

	// Address cannot be loopback
	if (IN6_IS_ADDR_LOOPBACK(address)) {
		DEBUG(ctx, "Start address is loopback address\n");
		return -EINVAL;
	}

	// Address cannot be link-local
	if (IN6_IS_ADDR_LINKLOCAL(address)) {
		DEBUG(ctx, "Start address cannot be link-local\n");
		return -EINVAL;
	}

	// Address cannot be site-local
	if (IN6_IS_ADDR_SITELOCAL(address)) {
		DEBUG(ctx, "Start address cannot be site-local\n");
		return -EINVAL;
	}

	// Validate the prefix
	if (valid_prefix(address, prefix) != 0) {
		DEBUG(ctx, "Invalid prefix: %u\n", prefix);
		return -EINVAL;
	}

	struct loc_network* n = calloc(1, sizeof(*n));
	if (!n)
		return -ENOMEM;

	n->ctx = loc_ref(ctx);
	n->refcount = 1;

	// Store the first address in the network
	n->start_address = make_start_address(address, prefix);
	n->prefix = prefix;

	DEBUG(n->ctx, "Network allocated at %p\n", n);
	*network = n;
	return 0;
}

static int loc_network_address_family(struct loc_network* network) {
	if (IN6_IS_ADDR_V4MAPPED(&network->start_address))
		return AF_INET;

	return AF_INET6;
}

LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
		const char* address_string) {
	struct in6_addr start_address;
	unsigned int prefix = 0;
	char* prefix_string;
	int r = 1;

	// Make a copy of the string to work on it
	char* buffer = strdup(address_string);
	address_string = prefix_string = buffer;

	// Split address and prefix
	address_string = strsep(&prefix_string, "/");

	// Did we find a prefix?
	if (prefix_string) {
		// Convert prefix to integer
		prefix = strtol(prefix_string, NULL, 10);

		if (prefix) {
			// Parse the address
			r = loc_parse_address(ctx, address_string, &start_address);

			// Map the prefix to IPv6 if needed
			if (IN6_IS_ADDR_V4MAPPED(&start_address))
				prefix += 96;
		}
	}

	// Free temporary buffer
	free(buffer);

	if (r == 0) {
		r = loc_network_new(ctx, network, &start_address, prefix);
	}

	return r;
}

LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
	network->refcount++;

	return network;
}

static void loc_network_free(struct loc_network* network) {
	DEBUG(network->ctx, "Releasing network at %p\n", network);

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

LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
	if (!network)
		return NULL;

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

	loc_network_free(network);
	return NULL;
}

static int format_ipv6_address(const struct in6_addr* address, char* string, size_t length) {
	const char* ret = inet_ntop(AF_INET6, address, string, length);
	if (!ret)
		return -1;

	return 0;
}

static int format_ipv4_address(const struct in6_addr* address, char* string, size_t length) {
	struct in_addr ipv4_address;
	ipv4_address.s_addr = address->s6_addr32[3];

	const char* ret = inet_ntop(AF_INET, &ipv4_address, string, length);
	if (!ret)
		return -1;

	return 0;
}

LOC_EXPORT char* loc_network_str(struct loc_network* network) {
	int r;
	const size_t length = INET6_ADDRSTRLEN + 4;

	char* string = malloc(length);
	if (!string)
		return NULL;

	unsigned int prefix = network->prefix;

	int family = loc_network_address_family(network);
	switch (family) {
		case AF_INET6:
			r = format_ipv6_address(&network->start_address, string, length);
			break;

		case AF_INET:
			r = format_ipv4_address(&network->start_address, string, length);
			prefix -= 96;
			break;

		default:
			r = -1;
			break;
	}

	if (r) {
		ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno));
		free(string);

		return NULL;
	}

	// Append prefix
	sprintf(string + strlen(string), "/%u", prefix);

	return string;
}

LOC_EXPORT int loc_network_match_address(struct loc_network* network, const struct in6_addr* address) {
	// Address must be larger than the start address
	if (in6_addr_cmp(&network->start_address, address) > 0)
		return 1;

	// Determine the last address in this network
	struct in6_addr last_address = make_last_address(&network->start_address, network->prefix);

	// Address must be smaller than the last address
	if (in6_addr_cmp(address, &last_address) > 0)
		return 1;

	// The address is inside this network
	return 0;
}

LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
	return network->country_code;
}

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

	// Check country code
	if (!loc_country_code_is_valid(country_code))
		return -EINVAL;

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

	return 0;
}

LOC_EXPORT int loc_network_match_country_code(struct loc_network* network, const char* country_code) {
	// Check country code
	if (!loc_country_code_is_valid(country_code))
		return -EINVAL;

	return (network->country_code[0] == country_code[0])
		&& (network->country_code[1] == country_code[1]);
}

LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
	return network->asn;
}

LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
	network->asn = asn;

	return 0;
}

LOC_EXPORT int loc_network_match_asn(struct loc_network* network, uint32_t asn) {
	return network->asn == asn;
}

LOC_EXPORT int loc_network_has_flag(struct loc_network* network, uint32_t flag) {
	return network->flags & flag;
}

LOC_EXPORT int loc_network_set_flag(struct loc_network* network, uint32_t flag) {
	network->flags |= flag;

	return 0;
}

LOC_EXPORT int loc_network_match_flag(struct loc_network* network, uint32_t flag) {
	return loc_network_has_flag(network, flag);
}

LOC_EXPORT int loc_network_to_database_v0(struct loc_network* network, struct loc_database_network_v0* dbobj) {
	// Add country code
	for (unsigned int i = 0; i < 2; i++) {
		dbobj->country_code[i] = network->country_code[i] ? network->country_code[i] : '\0';
	}

	// Add ASN
	dbobj->asn = htobe32(network->asn);

	// Flags
	dbobj->flags = htobe32(network->flags);

	return 0;
}

LOC_EXPORT int loc_network_new_from_database_v0(struct loc_ctx* ctx, struct loc_network** network,
		struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v0* dbobj) {
	int r = loc_network_new(ctx, network, address, prefix);
	if (r)
		return r;

	// Import country code
	char country_code[3];
	for (unsigned int i = 0; i < 2; i++) {
		country_code[i] = dbobj->country_code[i];
	}
	country_code[2] = '\0';

	r = loc_network_set_country_code(*network, country_code);
	if (r)
		return r;

	// Import ASN
	r = loc_network_set_asn(*network, be32toh(dbobj->asn));
	if (r)
		return r;

	// Import flags
	r = loc_network_set_flag(*network, be32toh(dbobj->flags));
	if (r)
		return r;

	return 0;
}

struct loc_network_tree {
	struct loc_ctx* ctx;
	int refcount;

	struct loc_network_tree_node* root;
};

struct loc_network_tree_node {
	struct loc_ctx* ctx;
	int refcount;

	struct loc_network_tree_node* zero;
	struct loc_network_tree_node* one;

	struct loc_network* network;
};

LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
	struct loc_network_tree* t = calloc(1, sizeof(*t));
	if (!t)
		return -ENOMEM;

	t->ctx = loc_ref(ctx);
	t->refcount = 1;

	// Create the root node
	int r = loc_network_tree_node_new(ctx, &t->root);
	if (r) {
		loc_network_tree_unref(t);
		return r;
	}

	DEBUG(t->ctx, "Network tree allocated at %p\n", t);
	*tree = t;
	return 0;
}

LOC_EXPORT struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
	return loc_network_tree_node_ref(tree->root);
}

static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
	struct loc_network_tree_node** n;

	if (path == 0)
		n = &node->zero;
	else
		n = &node->one;

	// If the desired node doesn't exist, yet, we will create it
	if (*n == NULL) {
		int r = loc_network_tree_node_new(node->ctx, n);
		if (r)
			return NULL;
	}

	return *n;
}

static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
	struct loc_network_tree_node* node = tree->root;

	for (unsigned int i = 0; i < prefix; i++) {
		// Check if the ith bit is one or zero
		node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i));
	}

	return node;
}

static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
		int(*filter_callback)(struct loc_network* network, void* data),
		int(*callback)(struct loc_network* network, void* data), void* data) {
	int r;

	// Finding a network ends the walk here
	if (node->network) {
		if (filter_callback) {
			int f = filter_callback(node->network, data);
			if (f < 0)
				return f;

			// Skip network if filter function returns value greater than zero
			if (f > 0)
				return 0;
		}

		r = callback(node->network, data);
		if (r)
			return r;
	}

	// Walk down on the left side of the tree first
	if (node->zero) {
		r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
		if (r)
			return r;
	}

	// Then walk on the other side
	if (node->one) {
		r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
		if (r)
			return r;
	}

	return 0;
}

LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
		int(*filter_callback)(struct loc_network* network, void* data),
		int(*callback)(struct loc_network* network, void* data), void* data) {
	return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
}

static void loc_network_tree_free(struct loc_network_tree* tree) {
	DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);

	loc_network_tree_node_unref(tree->root);

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

LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
	if (--tree->refcount > 0)
		return tree;

	loc_network_tree_free(tree);
	return NULL;
}

static int __loc_network_tree_dump(struct loc_network* network, void* data) {
	DEBUG(network->ctx, "Dumping network at %p\n", network);

	char* s = loc_network_str(network);
	if (!s)
		return 1;

	INFO(network->ctx, "%s\n", s);
	free(s);

	return 0;
}

LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
	DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);

	return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
}

LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
	DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);

	struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
			&network->start_address, network->prefix);
	if (!node) {
		ERROR(tree->ctx, "Could not find a node\n");
		return -ENOMEM;
	}

	// Check if node has not been set before
	if (node->network) {
		DEBUG(tree->ctx, "There is already a network at this path\n");
		return -EBUSY;
	}

	// Point node to the network
	node->network = loc_network_ref(network);

	return 0;
}

static int __loc_network_tree_count(struct loc_network* network, void* data) {
	size_t* counter = (size_t*)data;

	// Increase the counter for each network
	counter++;

	return 0;
}

LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
	size_t counter = 0;

	int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
	if (r)
		return r;

	return counter;
}

static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
	size_t counter = 1;

	if (node->zero)
		counter += __loc_network_tree_count_nodes(node->zero);

	if (node->one)
		counter += __loc_network_tree_count_nodes(node->one);

	return counter;
}

LOC_EXPORT size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
	return __loc_network_tree_count_nodes(tree->root);
}

LOC_EXPORT int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
	struct loc_network_tree_node* n = calloc(1, sizeof(*n));
	if (!n)
		return -ENOMEM;

	n->ctx = loc_ref(ctx);
	n->refcount = 1;

	n->zero = n->one = NULL;

	DEBUG(n->ctx, "Network node allocated at %p\n", n);
	*node = n;
	return 0;
}

LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
	if (node)
		node->refcount++;

	return node;
}

static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
	DEBUG(node->ctx, "Releasing network node at %p\n", node);

	if (node->network)
		loc_network_unref(node->network);

	if (node->zero)
		loc_network_tree_node_unref(node->zero);

	if (node->one)
		loc_network_tree_node_unref(node->one);

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

LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
	if (!node)
		return NULL;

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

	loc_network_tree_node_free(node);
	return NULL;
}

LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
	if (index == 0)
		node = node->zero;
	else
		node = node->one;

	if (!node)
		return NULL;

	return loc_network_tree_node_ref(node);
}

LOC_EXPORT int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
	return (!!node->network);
}

LOC_EXPORT struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
	return loc_network_ref(node->network);
}
Commit	Line	Data
3b5f4af2 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
	17	#include <arpa/inet.h>
	18	#include <assert.h>
f3e02bc5	19	#include <endian.h>
3b5f4af2	20	#include <errno.h>
71ff3e69	21	#include <stdio.h>
3b5f4af2 MT	22	#include <stdlib.h>
	23	#include <string.h>
	24
	25	#include <loc/libloc.h>
57146963	26	#include <loc/country.h>
3b5f4af2	27	#include <loc/network.h>
9fc7f001	28	#include <loc/private.h>
3b5f4af2 MT	29
	30	struct loc_network {
	31	struct loc_ctx* ctx;
	32	int refcount;
	33
	34	struct in6_addr start_address;
	35	unsigned int prefix;
	36
	37	char country_code[3];
71ff3e69	38	uint32_t asn;
a293f829	39	enum loc_network_flags flags;
3b5f4af2 MT	40	};
3b5f4af2 MT	41
6183c0f2 MT	42	static int valid_prefix(struct in6_addr* address, unsigned int prefix) {
	43	// The prefix cannot be larger than 128 bits
	44	if (prefix > 128)
	45	return 1;
	46
	47	// And the prefix cannot be zero
	48	if (prefix == 0)
	49	return 1;
	50
aa37232a MT	51	// For IPv4-mapped addresses the prefix has to be 96 or lager
	52	if (IN6_IS_ADDR_V4MAPPED(address) && prefix <= 96)
	53	return 1;
	54
6183c0f2 MT	55	return 0;
	56	}
	57
a82ce8bc MT	58	static struct in6_addr prefix_to_bitmask(unsigned int prefix) {
	59	struct in6_addr bitmask;
	60
	61	for (unsigned int i = 0; i < 16; i++)
	62	bitmask.s6_addr[i] = 0;
	63
364a2a37	64	for (int i = prefix, j = 0; i > 0; i -= 8, j++) {
a82ce8bc MT	65	if (i >= 8)
	66	bitmask.s6_addr[j] = 0xff;
	67	else
	68	bitmask.s6_addr[j] = 0xff << (8 - i);
	69	}
	70
	71	return bitmask;
	72	}
	73
2a30e4de	74	static struct in6_addr make_start_address(const struct in6_addr* address, unsigned int prefix) {
a82ce8bc MT	75	struct in6_addr a;
	76	struct in6_addr bitmask = prefix_to_bitmask(prefix);
	77
	78	// Perform bitwise AND
	79	for (unsigned int i = 0; i < 4; i++)
	80	a.s6_addr32[i] = address->s6_addr32[i] & bitmask.s6_addr32[i];
	81
	82	return a;
	83	}
	84
2a30e4de MT	85	static struct in6_addr make_last_address(const struct in6_addr* address, unsigned int prefix) {
	86	struct in6_addr a;
	87	struct in6_addr bitmask = prefix_to_bitmask(prefix);
	88
	89	// Perform bitwise OR
	90	for (unsigned int i = 0; i < 4; i++)
c7096aef	91	a.s6_addr32[i] = address->s6_addr32[i] \| ~bitmask.s6_addr32[i];
2a30e4de MT	92
	93	return a;
	94	}
	95
3b5f4af2	96	LOC_EXPORT int loc_network_new(struct loc_ctx* ctx, struct loc_network** network,
10778041	97	struct in6_addr* address, unsigned int prefix) {
3b5f4af2	98	// Address cannot be unspecified
bca87342	99	if (IN6_IS_ADDR_UNSPECIFIED(address)) {
3b5f4af2 MT	100	DEBUG(ctx, "Start address is unspecified\n");
	101	return -EINVAL;
	102	}
	103
	104	// Address cannot be loopback
bca87342	105	if (IN6_IS_ADDR_LOOPBACK(address)) {
3b5f4af2 MT	106	DEBUG(ctx, "Start address is loopback address\n");
	107	return -EINVAL;
	108	}
	109
	110	// Address cannot be link-local
bca87342	111	if (IN6_IS_ADDR_LINKLOCAL(address)) {
3b5f4af2 MT	112	DEBUG(ctx, "Start address cannot be link-local\n");
	113	return -EINVAL;
	114	}
	115
	116	// Address cannot be site-local
bca87342	117	if (IN6_IS_ADDR_SITELOCAL(address)) {
3b5f4af2 MT	118	DEBUG(ctx, "Start address cannot be site-local\n");
	119	return -EINVAL;
	120	}
	121
6183c0f2	122	// Validate the prefix
10778041	123	if (valid_prefix(address, prefix) != 0) {
6183c0f2 MT	124	DEBUG(ctx, "Invalid prefix: %u\n", prefix);
	125	return -EINVAL;
	126	}
	127
3b5f4af2 MT	128	struct loc_network* n = calloc(1, sizeof(*n));
	129	if (!n)
	130	return -ENOMEM;
	131
	132	n->ctx = loc_ref(ctx);
	133	n->refcount = 1;
	134
a82ce8bc	135	// Store the first address in the network
10778041	136	n->start_address = make_start_address(address, prefix);
3b5f4af2 MT	137	n->prefix = prefix;
	138
	139	DEBUG(n->ctx, "Network allocated at %p\n", n);
	140	*network = n;
	141	return 0;
	142	}
	143
d3409788 MT	144	static int loc_network_address_family(struct loc_network* network) {
	145	if (IN6_IS_ADDR_V4MAPPED(&network->start_address))
	146	return AF_INET;
	147
	148	return AF_INET6;
	149	}
	150
3b5f4af2 MT	151	LOC_EXPORT int loc_network_new_from_string(struct loc_ctx* ctx, struct loc_network** network,
	152	const char* address_string) {
	153	struct in6_addr start_address;
b61f14fc	154	unsigned int prefix = 0;
3b5f4af2	155	char* prefix_string;
b61f14fc	156	int r = 1;
3b5f4af2 MT	157
	158	// Make a copy of the string to work on it
	159	char* buffer = strdup(address_string);
	160	address_string = prefix_string = buffer;
	161
	162	// Split address and prefix
	163	address_string = strsep(&prefix_string, "/");
	164
b61f14fc MT	165	// Did we find a prefix?
	166	if (prefix_string) {
	167	// Convert prefix to integer
	168	prefix = strtol(prefix_string, NULL, 10);
3b5f4af2	169
b61f14fc MT	170	if (prefix) {
b61f14fc MT	171	// Parse the address
2a30e4de	172	r = loc_parse_address(ctx, address_string, &start_address);
aa37232a MT	173
	174	// Map the prefix to IPv6 if needed
	175	if (IN6_IS_ADDR_V4MAPPED(&start_address))
	176	prefix += 96;
b61f14fc MT	177	}
b61f14fc MT	178	}
3b5f4af2 MT	179
	180	// Free temporary buffer
	181	free(buffer);
	182
d3409788	183	if (r == 0) {
10778041	184	r = loc_network_new(ctx, network, &start_address, prefix);
3b5f4af2 MT	185	}
	186
	187	return r;
	188	}
	189
	190	LOC_EXPORT struct loc_network* loc_network_ref(struct loc_network* network) {
	191	network->refcount++;
	192
	193	return network;
	194	}
	195
	196	static void loc_network_free(struct loc_network* network) {
	197	DEBUG(network->ctx, "Releasing network at %p\n", network);
	198
3b5f4af2 MT	199	loc_unref(network->ctx);
	200	free(network);
	201	}
	202
	203	LOC_EXPORT struct loc_network* loc_network_unref(struct loc_network* network) {
2a30e4de MT	204	if (!network)
	205	return NULL;
	206
3b5f4af2 MT	207	if (--network->refcount > 0)
	208	return network;
	209
	210	loc_network_free(network);
	211	return NULL;
	212	}
	213
8fb874e9 MT	214	static int format_ipv6_address(const struct in6_addr* address, char* string, size_t length) {
8fb874e9 MT	215	const char* ret = inet_ntop(AF_INET6, address, string, length);
d3409788 MT	216	if (!ret)
	217	return -1;
	218
	219	return 0;
	220	}
	221
8fb874e9	222	static int format_ipv4_address(const struct in6_addr* address, char* string, size_t length) {
d3409788	223	struct in_addr ipv4_address;
8fb874e9	224	ipv4_address.s_addr = address->s6_addr32[3];
d3409788 MT	225
	226	const char* ret = inet_ntop(AF_INET, &ipv4_address, string, length);
	227	if (!ret)
	228	return -1;
	229
	230	return 0;
	231	}
	232
3b5f4af2	233	LOC_EXPORT char* loc_network_str(struct loc_network* network) {
d3409788 MT	234	int r;
d3409788 MT	235	const size_t length = INET6_ADDRSTRLEN + 4;
3b5f4af2	236
d3409788	237	char* string = malloc(length);
3b5f4af2 MT	238	if (!string)
	239	return NULL;
	240
aa37232a MT	241	unsigned int prefix = network->prefix;
aa37232a MT	242
d3409788 MT	243	int family = loc_network_address_family(network);
	244	switch (family) {
	245	case AF_INET6:
8fb874e9	246	r = format_ipv6_address(&network->start_address, string, length);
d3409788	247	break;
3b5f4af2	248
d3409788	249	case AF_INET:
8fb874e9	250	r = format_ipv4_address(&network->start_address, string, length);
aa37232a	251	prefix -= 96;
d3409788 MT	252	break;
	253
	254	default:
	255	r = -1;
	256	break;
	257	}
	258
	259	if (r) {
	260	ERROR(network->ctx, "Could not convert network to string: %s\n", strerror(errno));
3b5f4af2	261	free(string);
d3409788	262
3b5f4af2 MT	263	return NULL;
	264	}
	265
	266	// Append prefix
aa37232a	267	sprintf(string + strlen(string), "/%u", prefix);
3b5f4af2 MT	268
	269	return string;
	270	}
	271
2a30e4de	272	LOC_EXPORT int loc_network_match_address(struct loc_network* network, const struct in6_addr* address) {
f50adb09	273	// Address must be larger than the start address
2a30e4de MT	274	if (in6_addr_cmp(&network->start_address, address) > 0)
	275	return 1;
	276
	277	// Determine the last address in this network
	278	struct in6_addr last_address = make_last_address(&network->start_address, network->prefix);
	279
	280	// Address must be smaller than the last address
0d33b671	281	if (in6_addr_cmp(address, &last_address) > 0)
2a30e4de MT	282	return 1;
	283
	284	// The address is inside this network
	285	return 0;
	286	}
	287
3b5f4af2 MT	288	LOC_EXPORT const char* loc_network_get_country_code(struct loc_network* network) {
	289	return network->country_code;
	290	}
	291
	292	LOC_EXPORT int loc_network_set_country_code(struct loc_network* network, const char* country_code) {
901ef882 MT	293	// Set empty country code
	294	if (!country_code \|\| !*country_code) {
	295	*network->country_code = '\0';
	296	return 0;
	297	}
	298
57146963 MT	299	// Check country code
57146963 MT	300	if (!loc_country_code_is_valid(country_code))
3b5f4af2 MT	301	return -EINVAL;
	302
	303	for (unsigned int i = 0; i < 3; i++) {
	304	network->country_code[i] = country_code[i];
	305	}
	306
	307	return 0;
	308	}
	309
e3f696c1	310	LOC_EXPORT int loc_network_match_country_code(struct loc_network* network, const char* country_code) {
57146963 MT	311	// Check country code
57146963 MT	312	if (!loc_country_code_is_valid(country_code))
e3f696c1 MT	313	return -EINVAL;
	314
	315	return (network->country_code[0] == country_code[0])
	316	&& (network->country_code[1] == country_code[1]);
	317	}
	318
71ff3e69 MT	319	LOC_EXPORT uint32_t loc_network_get_asn(struct loc_network* network) {
	320	return network->asn;
	321	}
	322
	323	LOC_EXPORT int loc_network_set_asn(struct loc_network* network, uint32_t asn) {
	324	network->asn = asn;
	325
	326	return 0;
	327	}
	328
82910b95 MT	329	LOC_EXPORT int loc_network_match_asn(struct loc_network* network, uint32_t asn) {
	330	return network->asn == asn;
	331	}
	332
a99e7c2b MT	333	LOC_EXPORT int loc_network_has_flag(struct loc_network* network, uint32_t flag) {
	334	return network->flags & flag;
	335	}
	336
	337	LOC_EXPORT int loc_network_set_flag(struct loc_network* network, uint32_t flag) {
	338	network->flags \|= flag;
	339
	340	return 0;
	341	}
	342
	343	LOC_EXPORT int loc_network_match_flag(struct loc_network* network, uint32_t flag) {
	344	return loc_network_has_flag(network, flag);
	345	}
	346
f3e02bc5	347	LOC_EXPORT int loc_network_to_database_v0(struct loc_network* network, struct loc_database_network_v0* dbobj) {
f3e02bc5 MT	348	// Add country code
f3e02bc5 MT	349	for (unsigned int i = 0; i < 2; i++) {
04cdff09	350	dbobj->country_code[i] = network->country_code[i] ? network->country_code[i] : '\0';
f3e02bc5 MT	351	}
	352
	353	// Add ASN
71ff3e69	354	dbobj->asn = htobe32(network->asn);
f3e02bc5	355
a99e7c2b MT	356	// Flags
	357	dbobj->flags = htobe32(network->flags);
	358
f3e02bc5 MT	359	return 0;
	360	}
	361
10778041	362	LOC_EXPORT int loc_network_new_from_database_v0(struct loc_ctx* ctx, struct loc_network** network,
39a55353 MT	363	struct in6_addr* address, unsigned int prefix, const struct loc_database_network_v0* dbobj) {
39a55353 MT	364	int r = loc_network_new(ctx, network, address, prefix);
10778041 MT	365	if (r)
	366	return r;
	367
	368	// Import country code
	369	char country_code[3];
	370	for (unsigned int i = 0; i < 2; i++) {
	371	country_code[i] = dbobj->country_code[i];
	372	}
	373	country_code[2] = '\0';
	374
	375	r = loc_network_set_country_code(*network, country_code);
	376	if (r)
	377	return r;
	378
	379	// Import ASN
	380	r = loc_network_set_asn(*network, be32toh(dbobj->asn));
	381	if (r)
	382	return r;
	383
a99e7c2b MT	384	// Import flags
	385	r = loc_network_set_flag(*network, be32toh(dbobj->flags));
	386	if (r)
	387	return r;
	388
10778041 MT	389	return 0;
	390	}
	391
3b5f4af2 MT	392	struct loc_network_tree {
	393	struct loc_ctx* ctx;
	394	int refcount;
	395
	396	struct loc_network_tree_node* root;
	397	};
	398
	399	struct loc_network_tree_node {
438db08c MT	400	struct loc_ctx* ctx;
	401	int refcount;
	402
3b5f4af2 MT	403	struct loc_network_tree_node* zero;
	404	struct loc_network_tree_node* one;
	405
	406	struct loc_network* network;
	407	};
	408
	409	LOC_EXPORT int loc_network_tree_new(struct loc_ctx* ctx, struct loc_network_tree** tree) {
	410	struct loc_network_tree* t = calloc(1, sizeof(*t));
	411	if (!t)
	412	return -ENOMEM;
	413
	414	t->ctx = loc_ref(ctx);
	415	t->refcount = 1;
	416
	417	// Create the root node
438db08c MT	418	int r = loc_network_tree_node_new(ctx, &t->root);
	419	if (r) {
	420	loc_network_tree_unref(t);
	421	return r;
	422	}
3b5f4af2 MT	423
	424	DEBUG(t->ctx, "Network tree allocated at %p\n", t);
	425	*tree = t;
	426	return 0;
	427	}
	428
438db08c MT	429	LOC_EXPORT struct loc_network_tree_node* loc_network_tree_get_root(struct loc_network_tree* tree) {
438db08c MT	430	return loc_network_tree_node_ref(tree->root);
3b5f4af2 MT	431	}
	432
	433	static struct loc_network_tree_node* loc_network_tree_get_node(struct loc_network_tree_node* node, int path) {
	434	struct loc_network_tree_node** n;
	435
2a30e4de	436	if (path == 0)
3b5f4af2	437	n = &node->zero;
3eda9cab MT	438	else
3eda9cab MT	439	n = &node->one;
3b5f4af2 MT	440
	441	// If the desired node doesn't exist, yet, we will create it
	442	if (*n == NULL) {
438db08c	443	int r = loc_network_tree_node_new(node->ctx, n);
3b5f4af2 MT	444	if (r)
	445	return NULL;
	446	}
	447
	448	return *n;
	449	}
	450
39a55353	451	static struct loc_network_tree_node* loc_network_tree_get_path(struct loc_network_tree* tree, const struct in6_addr* address, unsigned int prefix) {
3b5f4af2 MT	452	struct loc_network_tree_node* node = tree->root;
3b5f4af2 MT	453
39a55353	454	for (unsigned int i = 0; i < prefix; i++) {
3b5f4af2	455	// Check if the ith bit is one or zero
2a30e4de	456	node = loc_network_tree_get_node(node, in6_addr_get_bit(address, i));
3b5f4af2 MT	457	}
	458
	459	return node;
	460	}
	461
	462	static int __loc_network_tree_walk(struct loc_ctx* ctx, struct loc_network_tree_node* node,
f3e02bc5 MT	463	int(filter_callback)(struct loc_network network, void* data),
f3e02bc5 MT	464	int(callback)(struct loc_network network, void* data), void* data) {
3b5f4af2 MT	465	int r;
	466
	467	// Finding a network ends the walk here
	468	if (node->network) {
	469	if (filter_callback) {
f3e02bc5	470	int f = filter_callback(node->network, data);
3b5f4af2 MT	471	if (f < 0)
	472	return f;
	473
	474	// Skip network if filter function returns value greater than zero
	475	if (f > 0)
	476	return 0;
	477	}
	478
f3e02bc5	479	r = callback(node->network, data);
3b5f4af2 MT	480	if (r)
	481	return r;
	482	}
	483
	484	// Walk down on the left side of the tree first
	485	if (node->zero) {
f3e02bc5	486	r = __loc_network_tree_walk(ctx, node->zero, filter_callback, callback, data);
3b5f4af2 MT	487	if (r)
	488	return r;
	489	}
	490
	491	// Then walk on the other side
	492	if (node->one) {
f3e02bc5	493	r = __loc_network_tree_walk(ctx, node->one, filter_callback, callback, data);
3b5f4af2 MT	494	if (r)
	495	return r;
	496	}
	497
	498	return 0;
	499	}
	500
f3e02bc5 MT	501	LOC_EXPORT int loc_network_tree_walk(struct loc_network_tree* tree,
	502	int(filter_callback)(struct loc_network network, void* data),
	503	int(callback)(struct loc_network network, void* data), void* data) {
	504	return __loc_network_tree_walk(tree->ctx, tree->root, filter_callback, callback, data);
	505	}
	506
3b5f4af2 MT	507	static void loc_network_tree_free(struct loc_network_tree* tree) {
	508	DEBUG(tree->ctx, "Releasing network tree at %p\n", tree);
	509
438db08c	510	loc_network_tree_node_unref(tree->root);
3b5f4af2 MT	511
	512	loc_unref(tree->ctx);
	513	free(tree);
	514	}
	515
	516	LOC_EXPORT struct loc_network_tree* loc_network_tree_unref(struct loc_network_tree* tree) {
	517	if (--tree->refcount > 0)
	518	return tree;
	519
	520	loc_network_tree_free(tree);
	521	return NULL;
	522	}
	523
e9b4e2a8	524	static int __loc_network_tree_dump(struct loc_network* network, void* data) {
3b5f4af2 MT	525	DEBUG(network->ctx, "Dumping network at %p\n", network);
	526
	527	char* s = loc_network_str(network);
	528	if (!s)
	529	return 1;
	530
	531	INFO(network->ctx, "%s\n", s);
	532	free(s);
	533
	534	return 0;
	535	}
	536
	537	LOC_EXPORT int loc_network_tree_dump(struct loc_network_tree* tree) {
	538	DEBUG(tree->ctx, "Dumping network tree at %p\n", tree);
	539
f3e02bc5	540	return loc_network_tree_walk(tree, NULL, __loc_network_tree_dump, NULL);
3b5f4af2 MT	541	}
	542
	543	LOC_EXPORT int loc_network_tree_add_network(struct loc_network_tree* tree, struct loc_network* network) {
	544	DEBUG(tree->ctx, "Adding network %p to tree %p\n", network, tree);
	545
39a55353 MT	546	struct loc_network_tree_node* node = loc_network_tree_get_path(tree,
39a55353 MT	547	&network->start_address, network->prefix);
3b5f4af2 MT	548	if (!node) {
	549	ERROR(tree->ctx, "Could not find a node\n");
	550	return -ENOMEM;
	551	}
	552
	553	// Check if node has not been set before
	554	if (node->network) {
	555	DEBUG(tree->ctx, "There is already a network at this path\n");
c04005bb	556	return -EBUSY;
3b5f4af2 MT	557	}
	558
	559	// Point node to the network
	560	node->network = loc_network_ref(network);
	561
	562	return 0;
	563	}
f3e02bc5 MT	564
	565	static int __loc_network_tree_count(struct loc_network* network, void* data) {
	566	size_t* counter = (size_t*)data;
	567
	568	// Increase the counter for each network
	569	counter++;
	570
	571	return 0;
	572	}
	573
	574	LOC_EXPORT size_t loc_network_tree_count_networks(struct loc_network_tree* tree) {
	575	size_t counter = 0;
	576
	577	int r = loc_network_tree_walk(tree, NULL, __loc_network_tree_count, &counter);
	578	if (r)
	579	return r;
	580
	581	return counter;
	582	}
940f9c2b MT	583
	584	static size_t __loc_network_tree_count_nodes(struct loc_network_tree_node* node) {
	585	size_t counter = 1;
	586
	587	if (node->zero)
	588	counter += __loc_network_tree_count_nodes(node->zero);
	589
	590	if (node->one)
	591	counter += __loc_network_tree_count_nodes(node->one);
	592
	593	return counter;
	594	}
	595
	596	LOC_EXPORT size_t loc_network_tree_count_nodes(struct loc_network_tree* tree) {
	597	return __loc_network_tree_count_nodes(tree->root);
	598	}
438db08c MT	599
	600	LOC_EXPORT int loc_network_tree_node_new(struct loc_ctx* ctx, struct loc_network_tree_node** node) {
	601	struct loc_network_tree_node* n = calloc(1, sizeof(*n));
	602	if (!n)
	603	return -ENOMEM;
	604
	605	n->ctx = loc_ref(ctx);
	606	n->refcount = 1;
	607
	608	n->zero = n->one = NULL;
	609
	610	DEBUG(n->ctx, "Network node allocated at %p\n", n);
	611	*node = n;
	612	return 0;
	613	}
	614
	615	LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_ref(struct loc_network_tree_node* node) {
	616	if (node)
	617	node->refcount++;
	618
	619	return node;
	620	}
	621
	622	static void loc_network_tree_node_free(struct loc_network_tree_node* node) {
	623	DEBUG(node->ctx, "Releasing network node at %p\n", node);
	624
	625	if (node->network)
	626	loc_network_unref(node->network);
	627
	628	if (node->zero)
	629	loc_network_tree_node_unref(node->zero);
	630
	631	if (node->one)
	632	loc_network_tree_node_unref(node->one);
	633
	634	loc_unref(node->ctx);
	635	free(node);
	636	}
	637
	638	LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_unref(struct loc_network_tree_node* node) {
	639	if (!node)
	640	return NULL;
	641
	642	if (--node->refcount > 0)
	643	return node;
	644
	645	loc_network_tree_node_free(node);
	646	return NULL;
	647	}
	648
	649	LOC_EXPORT struct loc_network_tree_node* loc_network_tree_node_get(struct loc_network_tree_node* node, unsigned int index) {
	650	if (index == 0)
	651	node = node->zero;
	652	else
	653	node = node->one;
	654
	655	if (!node)
	656	return NULL;
	657
	658	return loc_network_tree_node_ref(node);
	659	}
	660
	661	LOC_EXPORT int loc_network_tree_node_is_leaf(struct loc_network_tree_node* node) {
	662	return (!!node->network);
663	}
664
665	LOC_EXPORT struct loc_network* loc_network_tree_node_get_network(struct loc_network_tree_node* node) {
666	return loc_network_ref(node->network);
667	}