[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/address.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 = list->elements_size * 2;
	if (size < 1024)
		size = 1024;

	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;

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

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

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

	DEBUG(ctx, "Summarizing %s - %s\n", loc_address_str(first), loc_address_str(last));

	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 (loc_address_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 (loc_address_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;

		loc_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, family_bit_length - bits);
		if (r)
			return r;

		DEBUG(ctx, "Found network %s\n", loc_network_str(network));

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

		// If we have reached the end of possible IP addresses, we stop
		if (loc_address_all_ones(&start))
			break;

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