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