[people/ms/libloc.git] / src / network-list.c

/*
	libloc - A library to determine the location of someone on the Internet

	Copyright (C) 2020 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 <errno.h>
#include <stdlib.h>
#include <time.h>

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

struct loc_network_list {
	struct loc_ctx* ctx;
	int refcount;

	struct loc_network** elements;
	size_t elements_size;

	size_t size;
};

static int loc_network_list_grow(struct loc_network_list* list, size_t size) {
	DEBUG(list->ctx, "Growing network list %p by %zu to %zu\n",
		list, size, list->elements_size + size);

	struct loc_network** elements = reallocarray(list->elements,
			list->elements_size + size, sizeof(*list->elements));
	if (!elements)
		return -errno;

	list->elements = elements;
	list->elements_size += size;

	return 0;
}

LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx,
		struct loc_network_list** list) {
	struct loc_network_list* l = calloc(1, sizeof(*l));
	if (!l)
		return -ENOMEM;

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

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

LOC_EXPORT struct loc_network_list* loc_network_list_ref(struct loc_network_list* list) {
	list->refcount++;

	return list;
}

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

	// Remove all content
	loc_network_list_clear(list);

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

LOC_EXPORT struct loc_network_list* loc_network_list_unref(struct loc_network_list* list) {
	if (!list)
		return NULL;

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

	loc_network_list_free(list);
	return NULL;
}

LOC_EXPORT size_t loc_network_list_size(struct loc_network_list* list) {
	return list->size;
}

LOC_EXPORT int loc_network_list_empty(struct loc_network_list* list) {
	return list->size == 0;
}

LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) {
	if (!list->elements)
		return;

	for (unsigned int i = 0; i < list->size; i++)
		loc_network_unref(list->elements[i]);

	free(list->elements);
	list->elements = NULL;
	list->elements_size = 0;

	list->size = 0;
}

LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) {
	struct loc_network* network;
	char* s;

	for (unsigned int i = 0; i < list->size; i++) {
		network = list->elements[i];

		s = loc_network_str(network);

		INFO(list->ctx, "%4d: %s\n", i, s);
		free(s);
	}
}

LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
	// Check index
	if (index >= list->size)
		return NULL;

	return loc_network_ref(list->elements[index]);
}

static off_t loc_network_list_find(struct loc_network_list* list,
		struct loc_network* network, int* found) {
	// Insert at the beginning for an empty list
	if (loc_network_list_empty(list))
		return 0;

	off_t lo = 0;
	off_t hi = list->size - 1;
	int result;

	// Since we are working on an ordered list, there is often a good chance that
	// the network we are looking for is at the end or has to go to the end.
	if (hi >= 0) {
		result = loc_network_cmp(network, list->elements[hi]);

		// Match, so we are done
		if (result == 0) {
			*found = 1;

			return hi;

		// This needs to be added after the last one
		} else if (result > 0) {
			*found = 0;

			return hi + 1;
		}
	}

#ifdef ENABLE_DEBUG
	// Save start time
	clock_t start = clock();
#endif

	off_t i = 0;

	while (lo <= hi) {
		i = (lo + hi) / 2;

		// Check if this is a match
		result = loc_network_cmp(network, list->elements[i]);

		if (result == 0) {
			*found = 1;

#ifdef ENABLE_DEBUG
			clock_t end = clock();

			// Log how fast this has been
			DEBUG(list->ctx, "Found network in %.4fms at %jd\n",
				(double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
#endif

			return i;
		}

		if (result > 0) {
			lo = i + 1;
			i++;
		} else {
			hi = i - 1;
		}
	}

	*found = 0;

#ifdef ENABLE_DEBUG
	clock_t end = clock();

	// Log how fast this has been
	DEBUG(list->ctx, "Did not find network in %.4fms (last i = %jd)\n",
		(double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
#endif

	return i;
}

LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
	int found = 0;

	off_t index = loc_network_list_find(list, network, &found);

	// The network has been found on the list. Nothing to do.
	if (found)
		return 0;

	DEBUG(list->ctx, "%p: Inserting network %p at index %jd\n",
		list, network, (intmax_t)index);

	// Check if we have space left
	if (list->size >= list->elements_size) {
		int r = loc_network_list_grow(list, 64);
		if (r)
			return r;
	}

	// The list is now larger
	list->size++;

	// Move all elements out of the way
	for (unsigned int i = list->size - 1; i > index; i--)
		list->elements[i] = list->elements[i - 1];

	// Add the new element at the right place
	list->elements[index] = loc_network_ref(network);

	return 0;
}

LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
	// Return nothing when empty
	if (loc_network_list_empty(list)) {
		DEBUG(list->ctx, "%p: Popped empty stack\n", list);
		return NULL;
	}

	struct loc_network* network = list->elements[--list->size];

	DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);

	return network;
}

LOC_EXPORT struct loc_network* loc_network_list_pop_first(struct loc_network_list* list) {
	// Return nothing when empty
	if (loc_network_list_empty(list)) {
		DEBUG(list->ctx, "%p: Popped empty stack\n", list);
		return NULL;
	}

	struct loc_network* network = list->elements[0];

	// Move all elements to the top of the stack
	for (unsigned int i = 0; i < list->size - 1; i++) {
		list->elements[i] = list->elements[i+1];
	}

	// The list is shorter now
	--list->size;

	DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);

	return network;
}

LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
	int found = 0;

	loc_network_list_find(list, network, &found);

	return found;
}

LOC_EXPORT int loc_network_list_merge(
		struct loc_network_list* self, struct loc_network_list* other) {
	int r;

	for (unsigned int i = 0; i < other->size; i++) {
		r = loc_network_list_push(self, other->elements[i]);
		if (r)
			return r;
	}

	return 0;
}

int loc_network_list_summarize(struct loc_ctx* ctx,
		const struct in6_addr* first, const struct in6_addr* last, struct loc_network_list** list) {
	int r;

	if (!list) {
		errno = EINVAL;
		return 1;
	}

	const int family1 = loc_address_family(first);
	const int family2 = loc_address_family(last);

	// Check if address families match
	if (family1 != family2) {
		ERROR(ctx, "Address families do not match\n");
		errno = EINVAL;
		return 1;
	}

	// Check if the last address is larger than the first address
	if (in6_addr_cmp(first, last) >= 0) {
		ERROR(ctx, "The first address must be smaller than the last address\n");
		errno = EINVAL;
		return 1;
	}

	struct loc_network* network = NULL;
	struct in6_addr start = *first;

	const int family_bit_length = loc_address_family_bit_length(family1);

	while (in6_addr_cmp(&start, last) <= 0) {
		struct in6_addr num;
		int bits1;

		// Find the number of trailing zeroes of the start address
		if (loc_address_all_zeroes(&start))
			bits1 = family_bit_length;
		else {
			bits1 = loc_address_count_trailing_zero_bits(&start);
			if (bits1 > family_bit_length)
				bits1 = family_bit_length;
		}

		// Subtract the start address from the last address and add one
		// (i.e. how many addresses are in this network?)
		r = loc_address_sub(&num, last, &start);
		if (r)
			return r;

		num = address_increment(&num);

		// How many bits do we need to represent this address?
		int bits2 = loc_address_bit_length(&num) - 1;

		// Select the smaller one
		int bits = (bits1 > bits2) ? bits2 : bits1;

		// Create a network
		r = loc_network_new(ctx, &network, &start, 128 - bits);
		if (r)
			return r;

#ifdef ENABLE_DEBUG
		char* n = loc_network_str(network);
		if (n) {
			DEBUG(ctx, "Found network %s\n", n);
			free(n);
		}
#endif

		// Push network on the list
		r = loc_network_list_push(*list, network);
		if (r) {
			loc_network_unref(network);
			return r;
		}

		// The next network starts right after this one
		start = *loc_network_get_last_address(network);
		start = address_increment(&start);
	}

	return 0;
}
Commit	Line	Data
e0b9ff5f MT	1	/*
	2	libloc - A library to determine the location of someone on the Internet
	3
	4	Copyright (C) 2020 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 <errno.h>
	18	#include <stdlib.h>
af4689bf	19	#include <time.h>
e0b9ff5f	20
c12a1385 MT	21	#include <libloc/libloc.h>
	22	#include <libloc/network.h>
	23	#include <libloc/private.h>
e0b9ff5f MT	24
	25	struct loc_network_list {
	26	struct loc_ctx* ctx;
	27	int refcount;
	28
3b44e421 MT	29	struct loc_network** elements;
	30	size_t elements_size;
	31
e0b9ff5f	32	size_t size;
e0b9ff5f MT	33	};
e0b9ff5f MT	34
3b44e421 MT	35	static int loc_network_list_grow(struct loc_network_list* list, size_t size) {
	36	DEBUG(list->ctx, "Growing network list %p by %zu to %zu\n",
	37	list, size, list->elements_size + size);
	38
	39	struct loc_network** elements = reallocarray(list->elements,
	40	list->elements_size + size, sizeof(*list->elements));
	41	if (!elements)
	42	return -errno;
	43
	44	list->elements = elements;
	45	list->elements_size += size;
	46
	47	return 0;
	48	}
	49
e0b9ff5f MT	50	LOC_EXPORT int loc_network_list_new(struct loc_ctx* ctx,
	51	struct loc_network_list** list) {
	52	struct loc_network_list* l = calloc(1, sizeof(*l));
	53	if (!l)
	54	return -ENOMEM;
	55
	56	l->ctx = loc_ref(ctx);
	57	l->refcount = 1;
	58
e0b9ff5f MT	59	DEBUG(l->ctx, "Network list allocated at %p\n", l);
	60	*list = l;
	61	return 0;
	62	}
	63
	64	LOC_EXPORT struct loc_network_list* loc_network_list_ref(struct loc_network_list* list) {
	65	list->refcount++;
	66
	67	return list;
	68	}
	69
	70	static void loc_network_list_free(struct loc_network_list* list) {
	71	DEBUG(list->ctx, "Releasing network list at %p\n", list);
	72
fff093b6 MT	73	// Remove all content
fff093b6 MT	74	loc_network_list_clear(list);
e0b9ff5f MT	75
	76	loc_unref(list->ctx);
	77	free(list);
	78	}
	79
	80	LOC_EXPORT struct loc_network_list* loc_network_list_unref(struct loc_network_list* list) {
	81	if (!list)
	82	return NULL;
	83
	84	if (--list->refcount > 0)
	85	return list;
	86
	87	loc_network_list_free(list);
	88	return NULL;
	89	}
	90
	91	LOC_EXPORT size_t loc_network_list_size(struct loc_network_list* list) {
	92	return list->size;
	93	}
	94
	95	LOC_EXPORT int loc_network_list_empty(struct loc_network_list* list) {
	96	return list->size == 0;
	97	}
	98
	99	LOC_EXPORT void loc_network_list_clear(struct loc_network_list* list) {
248f5e04 MT	100	if (!list->elements)
	101	return;
	102
e0b9ff5f	103	for (unsigned int i = 0; i < list->size; i++)
3b44e421	104	loc_network_unref(list->elements[i]);
e0b9ff5f	105
248f5e04	106	free(list->elements);
d42f34ce	107	list->elements = NULL;
248f5e04 MT	108	list->elements_size = 0;
248f5e04 MT	109
e0b9ff5f MT	110	list->size = 0;
	111	}
	112
	113	LOC_EXPORT void loc_network_list_dump(struct loc_network_list* list) {
	114	struct loc_network* network;
	115	char* s;
	116
	117	for (unsigned int i = 0; i < list->size; i++) {
3b44e421	118	network = list->elements[i];
e0b9ff5f MT	119
	120	s = loc_network_str(network);
	121
9446c753	122	INFO(list->ctx, "%4d: %s\n", i, s);
e0b9ff5f MT	123	free(s);
	124	}
	125	}
	126
	127	LOC_EXPORT struct loc_network* loc_network_list_get(struct loc_network_list* list, size_t index) {
	128	// Check index
	129	if (index >= list->size)
	130	return NULL;
	131
3b44e421	132	return loc_network_ref(list->elements[index]);
e0b9ff5f MT	133	}
e0b9ff5f MT	134
af4689bf MT	135	static off_t loc_network_list_find(struct loc_network_list* list,
af4689bf MT	136	struct loc_network* network, int* found) {
92202e5a MT	137	// Insert at the beginning for an empty list
	138	if (loc_network_list_empty(list))
	139	return 0;
	140
af4689bf MT	141	off_t lo = 0;
af4689bf MT	142	off_t hi = list->size - 1;
77e6d537	143	int result;
af4689bf	144
77e6d537 MT	145	// Since we are working on an ordered list, there is often a good chance that
	146	// the network we are looking for is at the end or has to go to the end.
	147	if (hi >= 0) {
	148	result = loc_network_cmp(network, list->elements[hi]);
	149
	150	// Match, so we are done
	151	if (result == 0) {
	152	*found = 1;
	153
	154	return hi;
	155
	156	// This needs to be added after the last one
	157	} else if (result > 0) {
	158	*found = 0;
	159
	160	return hi + 1;
	161	}
	162	}
af4689bf MT	163
	164	#ifdef ENABLE_DEBUG
	165	// Save start time
	166	clock_t start = clock();
	167	#endif
	168
	169	off_t i = 0;
	170
	171	while (lo <= hi) {
	172	i = (lo + hi) / 2;
	173
	174	// Check if this is a match
77e6d537	175	result = loc_network_cmp(network, list->elements[i]);
af4689bf MT	176
	177	if (result == 0) {
	178	*found = 1;
	179
	180	#ifdef ENABLE_DEBUG
	181	clock_t end = clock();
	182
	183	// Log how fast this has been
	184	DEBUG(list->ctx, "Found network in %.4fms at %jd\n",
	185	(double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
	186	#endif
	187
	188	return i;
	189	}
	190
775621e8	191	if (result > 0) {
af4689bf	192	lo = i + 1;
775621e8 MT	193	i++;
775621e8 MT	194	} else {
af4689bf	195	hi = i - 1;
775621e8	196	}
af4689bf MT	197	}
af4689bf MT	198
77e6d537 MT	199	*found = 0;
77e6d537 MT	200
af4689bf MT	201	#ifdef ENABLE_DEBUG
	202	clock_t end = clock();
	203
	204	// Log how fast this has been
	205	DEBUG(list->ctx, "Did not find network in %.4fms (last i = %jd)\n",
	206	(double)(end - start) / CLOCKS_PER_SEC * 1000, (intmax_t)i);
	207	#endif
	208
	209	return i;
	210	}
	211
e0b9ff5f	212	LOC_EXPORT int loc_network_list_push(struct loc_network_list* list, struct loc_network* network) {
af4689bf MT	213	int found = 0;
	214
	215	off_t index = loc_network_list_find(list, network, &found);
	216
	217	// The network has been found on the list. Nothing to do.
	218	if (found)
e0b9ff5f MT	219	return 0;
e0b9ff5f MT	220
af4689bf MT	221	DEBUG(list->ctx, "%p: Inserting network %p at index %jd\n",
	222	list, network, (intmax_t)index);
	223
e0b9ff5f	224	// Check if we have space left
3b44e421 MT	225	if (list->size >= list->elements_size) {
	226	int r = loc_network_list_grow(list, 64);
	227	if (r)
	228	return r;
e0b9ff5f MT	229	}
e0b9ff5f MT	230
af4689bf MT	231	// The list is now larger
	232	list->size++;
	233
	234	// Move all elements out of the way
	235	for (unsigned int i = list->size - 1; i > index; i--)
	236	list->elements[i] = list->elements[i - 1];
e0b9ff5f	237
af4689bf MT	238	// Add the new element at the right place
af4689bf MT	239	list->elements[index] = loc_network_ref(network);
e0b9ff5f MT	240
	241	return 0;
	242	}
	243
	244	LOC_EXPORT struct loc_network* loc_network_list_pop(struct loc_network_list* list) {
	245	// Return nothing when empty
	246	if (loc_network_list_empty(list)) {
	247	DEBUG(list->ctx, "%p: Popped empty stack\n", list);
	248	return NULL;
	249	}
	250
3b44e421	251	struct loc_network* network = list->elements[--list->size];
e0b9ff5f MT	252
	253	DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
	254
	255	return network;
	256	}
	257
	258	LOC_EXPORT struct loc_network* loc_network_list_pop_first(struct loc_network_list* list) {
	259	// Return nothing when empty
	260	if (loc_network_list_empty(list)) {
	261	DEBUG(list->ctx, "%p: Popped empty stack\n", list);
	262	return NULL;
	263	}
	264
3b44e421	265	struct loc_network* network = list->elements[0];
e0b9ff5f MT	266
e0b9ff5f MT	267	// Move all elements to the top of the stack
673e03f7	268	for (unsigned int i = 0; i < list->size - 1; i++) {
3b44e421	269	list->elements[i] = list->elements[i+1];
e0b9ff5f MT	270	}
e0b9ff5f MT	271
673e03f7 MT	272	// The list is shorter now
	273	--list->size;
	274
e0b9ff5f MT	275	DEBUG(list->ctx, "%p: Popping network %p from stack\n", list, network);
	276
	277	return network;
	278	}
	279
	280	LOC_EXPORT int loc_network_list_contains(struct loc_network_list* list, struct loc_network* network) {
af4689bf	281	int found = 0;
e0b9ff5f	282
af4689bf MT	283	loc_network_list_find(list, network, &found);
	284
	285	return found;
e0b9ff5f MT	286	}
e0b9ff5f MT	287
e0b9ff5f MT	288	LOC_EXPORT int loc_network_list_merge(
	289	struct loc_network_list* self, struct loc_network_list* other) {
	290	int r;
	291
	292	for (unsigned int i = 0; i < other->size; i++) {
3b44e421	293	r = loc_network_list_push(self, other->elements[i]);
e0b9ff5f MT	294	if (r)
	295	return r;
	296	}
	297
	298	return 0;
	299	}
8c37d8a7 MT	300
	301	int loc_network_list_summarize(struct loc_ctx* ctx,
	302	const struct in6_addr* first, const struct in6_addr* last, struct loc_network_list** list) {
	303	int r;
	304
	305	if (!list) {
	306	errno = EINVAL;
	307	return 1;
	308	}
	309
88a3db10 MT	310	const int family1 = loc_address_family(first);
88a3db10 MT	311	const int family2 = loc_address_family(last);
8c37d8a7	312
88a3db10 MT	313	// Check if address families match
88a3db10 MT	314	if (family1 != family2) {
8c37d8a7 MT	315	ERROR(ctx, "Address families do not match\n");
	316	errno = EINVAL;
	317	return 1;
	318	}
	319
	320	// Check if the last address is larger than the first address
	321	if (in6_addr_cmp(first, last) >= 0) {
	322	ERROR(ctx, "The first address must be smaller than the last address\n");
	323	errno = EINVAL;
	324	return 1;
	325	}
	326
	327	struct loc_network* network = NULL;
8c37d8a7	328	struct in6_addr start = *first;
8c37d8a7	329
88a3db10 MT	330	const int family_bit_length = loc_address_family_bit_length(family1);
88a3db10 MT	331
8c37d8a7	332	while (in6_addr_cmp(&start, last) <= 0) {
f39c751d	333	struct in6_addr num;
88a3db10	334	int bits1;
f39c751d	335
d701dcfd	336	// Find the number of trailing zeroes of the start address
88a3db10 MT	337	if (loc_address_all_zeroes(&start))
	338	bits1 = family_bit_length;
	339	else {
	340	bits1 = loc_address_count_trailing_zero_bits(&start);
	341	if (bits1 > family_bit_length)
	342	bits1 = family_bit_length;
	343	}
8c37d8a7	344
d701dcfd MT	345	// Subtract the start address from the last address and add one
d701dcfd MT	346	// (i.e. how many addresses are in this network?)
f39c751d MT	347	r = loc_address_sub(&num, last, &start);
	348	if (r)
	349	return r;
	350
d701dcfd	351	num = address_increment(&num);
8c37d8a7	352
d701dcfd MT	353	// How many bits do we need to represent this address?
d701dcfd MT	354	int bits2 = loc_address_bit_length(&num) - 1;
8c37d8a7	355
d701dcfd MT	356	// Select the smaller one
	357	int bits = (bits1 > bits2) ? bits2 : bits1;
	358
	359	// Create a network
	360	r = loc_network_new(ctx, &network, &start, 128 - bits);
	361	if (r)
	362	return r;
	363
	364	#ifdef ENABLE_DEBUG
	365	char* n = loc_network_str(network);
	366	if (n) {
	367	DEBUG(ctx, "Found network %s\n", n);
	368	free(n);
8c37d8a7	369	}
d701dcfd	370	#endif
8c37d8a7	371
d701dcfd	372	// Push network on the list
8c37d8a7 MT	373	r = loc_network_list_push(*list, network);
	374	if (r) {
	375	loc_network_unref(network);
	376	return r;
	377	}
	378
d701dcfd MT	379	// The next network starts right after this one
	380	start = *loc_network_get_last_address(network);
	381	start = address_increment(&start);
8c37d8a7 MT	382	}
	383
	384	return 0;
	385	}