[people/ms/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 <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifdef HAVE_ENDIAN_H
#  include <endian.h>
#endif

#include <loc/libloc.h>
#include <loc/compat.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;
}

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

	loc_country_code_copy(network->country_code, country_code);

	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
	loc_country_code_copy(dbobj->country_code, network->country_code);

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

	// Flags
	dbobj->flags = htobe16(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) {
	char country_code[3] = "\0\0";

	int r = loc_network_new(ctx, network, address, prefix);
	if (r) {
		ERROR(ctx, "Could not allocate a new network: %s", strerror(-r));
		return r;
	}

	// Import country code
	loc_country_code_copy(country_code, dbobj->country_code);

	r = loc_network_set_country_code(*network, country_code);
	if (r) {
		ERROR(ctx, "Could not set country code: %s\n", country_code);
		return r;
	}

	// Import ASN
	uint32_t asn = be32toh(dbobj->asn);
	r = loc_network_set_asn(*network, asn);
	if (r) {
		ERROR(ctx, "Could not set ASN: %d\n", asn);
		return r;
	}

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