Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.sbin/bgpctl/irr_prefix.c	Lines:	0	131	0.0 %
Date:	2016-12-06	Branches:	0	316	0.0 %


/*	$OpenBSD: irr_prefix.c,v 1.21 2015/10/05 14:18:33 deraadt Exp $ */

/*
 * Copyright (c) 2007 Henning Brauer <henning@openbsd.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF MIND, USE, DATA OR PROFITS, WHETHER IN
 * AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <sys/types.h>
#include <err.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <netinet/in.h>
#include <arpa/inet.h>

#include "irrfilter.h"
#include "bgpd.h"

void	 prefixset_aggregate(struct prefix_set *);
int	 prefix_aggregate(struct irr_prefix *, const struct irr_prefix *);
int	 irr_prefix_cmp(const void *, const void *);
int	 prefix_set_compare(struct prefix_set *, struct prefix_set *);
struct prefix_set
	*prefix_set_find(char *);

RB_HEAD(prefix_set_h, prefix_set)	prefix_set_h;
RB_PROTOTYPE(prefix_set_h, prefix_set, entry, prefix_set_compare)
RB_GENERATE(prefix_set_h, prefix_set, entry, prefix_set_compare)

struct prefix_set	*curpfxs = NULL;

struct prefix_set *
prefixset_get(char *as)
{
	struct prefix_set	*pfxs;

	if ((pfxs = prefix_set_find(as)) != NULL)
		return (pfxs);

	/* nothing found, resolve and store */
	if ((pfxs = calloc(1, sizeof(*pfxs))) == NULL)
		err(1, "get_prefixset calloc");
	if ((pfxs->as = strdup(as)) == NULL)
		err(1, "get_prefixset strdup");
	RB_INSERT(prefix_set_h, &prefix_set_h, pfxs);

	if (irrverbose >= 3) {
		fprintf(stdout, "query routes for %s... ", as);
		fflush(stdout);
	}
	curpfxs = pfxs;
	if ((irrflags & F_IPV4) && whois(as, QTYPE_ROUTE) == -1)
		errx(1, "whois error, prefixset_get %s", as);
	if ((irrflags & F_IPV6) && whois(as, QTYPE_ROUTE6) == -1)
		errx(1, "whois error, prefixset_get %s", as);
	if (whois(as, QTYPE_ROUTE6) == -1)
		errx(1, "whois error, prefixset_get %s", as);
	curpfxs = NULL;
	if (irrverbose >= 3)
		fprintf(stdout, "done\n");

	prefixset_aggregate(pfxs);

	return (pfxs);
}

int
prefixset_addmember(char *s)
{
	void			*p;
	u_int			 i;
	struct irr_prefix	*pfx;
	int			 len, ret;
	char			*slash;
	const char		*errstr;

	if ((slash = strchr(s, '/')) == NULL) {
		fprintf(stderr, "%s: prefix %s does not have the len "
		    "specified, ignoring\n", curpfxs->as, s);
		return (0);
	}

	if ((pfx = calloc(1, sizeof(*pfx))) == NULL)
		err(1, "prefixset_addmember calloc");

	if ((len = inet_net_pton(AF_INET, s, &pfx->addr.in,
	    sizeof(pfx->addr.in))) != -1) {
		pfx->af = AF_INET;
	} else {
		len = strtonum(slash + 1, 0, 128, &errstr);
		if (errstr)
			errx(1, "prefixset_addmember %s prefix %s: prefixlen "
			    "is %s", curpfxs->as, s, errstr);
		*slash = '\0';

		if ((ret = inet_pton(AF_INET6, s, &pfx->addr.in6)) == -1)
			err(1, "prefixset_addmember %s prefix \"%s\"",
			    curpfxs->as, s);
		else if (ret == 0) {
			fprintf(stderr, "prefixset_addmember %s prefix \"%s\": "
			    "No matching address family found", curpfxs->as, s);
			free(pfx);
			return (0);
		}
		pfx->af = AF_INET6;
	}
	pfx->len = pfx->maxlen = len;

	/* yes, there are dupes... e. g. from multiple sources */
	for (i = 0; i < curpfxs->prefixcnt; i++)
		if (irr_prefix_cmp(&curpfxs->prefix[i], &pfx) == 0) {
			free(pfx);
			return (0);
		}

	if ((p = reallocarray(curpfxs->prefix,
	    curpfxs->prefixcnt + 1, sizeof(void *))) == NULL)
		err(1, "prefixset_addmember realloc");
	curpfxs->prefix = p;
	curpfxs->prefixcnt++;
	curpfxs->prefix[curpfxs->prefixcnt - 1] = pfx;

	return (1);
}

void
prefixset_aggregate(struct prefix_set *pfxs)
{
	u_int			 i, cnt, newcnt;
	int			 res;
	struct irr_prefix	*cur, *last;
	void			*p;

	qsort(pfxs->prefix, pfxs->prefixcnt, sizeof(void *), irr_prefix_cmp);

	cnt = pfxs->prefixcnt;
	do {
		last = cur = NULL;
		for (i = 0, newcnt = 0; i < cnt; i++) {
			cur = pfxs->prefix[i];
			if (last != NULL && last->af == cur->af) {
				if (cur->af == AF_INET)
					res = prefix_aggregate(last, cur);
				else
					res = 0;

				if (res == 1) {	/* cur is covered by last */
					if (cur->len > last->maxlen)
						last->maxlen = cur->len;
					free(pfxs->prefix[i]);
					pfxs->prefix[i] = cur = NULL;
				}
			}

			if (cur != NULL) {
				pfxs->prefix[newcnt++] = cur;
				last = cur;
			}
		}
		cnt = newcnt;
	} while (newcnt < i);

	if (newcnt == pfxs->prefixcnt)
		return;

	if (irrverbose >= 2)
		printf("%s: prefix aggregation: %u -> %u\n",
		    pfxs->as, pfxs->prefixcnt, newcnt);

	if ((p = reallocarray(pfxs->prefix, newcnt, sizeof(void *))) == NULL)
		err(1, "prefixset_aggregate realloc");
	pfxs->prefix = p;
	pfxs->prefixcnt = newcnt;
}

int
prefix_aggregate(struct irr_prefix *a, const struct irr_prefix *b)
{
	in_addr_t	 mask;
	struct in6_addr	 ma;
	struct in6_addr	 mb;

	if (a->len == 0)
		return (1);

	if (a->af != b->af)
		/* We cannot aggregate addresses of different families. */
		return (0);

	if (a->af == AF_INET) {
		mask = htonl(prefixlen2mask(a->len));
		if ((a->addr.in.s_addr & mask) == (b->addr.in.s_addr & mask))
			return (1);
	} else if (a->af == AF_INET6) {
		inet6applymask(&ma, &a->addr.in6, a->len);
		inet6applymask(&mb, &b->addr.in6, a->len);
		if (IN6_ARE_ADDR_EQUAL(&ma, &mb))
			return (1);
	}

	/* see whether we can fold them in one */
	if (a->len == b->len && a->len > 1) {
		if (a->af == AF_INET) {
			mask = htonl(prefixlen2mask(a->len - 1));
			if ((a->addr.in.s_addr & mask) ==
			    (b->addr.in.s_addr & mask)) {
				a->len--;
				a->addr.in.s_addr &= mask;
				return (1);
			}
		} else if (a->af == AF_INET6) {
			inet6applymask(&ma, &a->addr.in6, a->len - 1);
			inet6applymask(&mb, &b->addr.in6, a->len - 1);

			if (IN6_ARE_ADDR_EQUAL(&ma, &mb)) {
				a->len--;
				memcpy(&a->addr.in6, &ma, sizeof(ma));
				return (1);
			}
		}
	}

	return (0);
}

int
irr_prefix_cmp(const void *a, const void *b)
{
	const struct irr_prefix	*pa;
	const struct irr_prefix	*pb;
	int			 r;

	pa = *((const struct irr_prefix	* const *)a);
	pb = *((const struct irr_prefix	* const *)b);

	if ((r = pa->af - pb->af) != 0)
		return (r);

	if (pa->af == AF_INET) {
		if (ntohl(pa->addr.in.s_addr) <
		    ntohl(pb->addr.in.s_addr))
			return (-1);
		if (ntohl(pa->addr.in.s_addr) >
		    ntohl(pb->addr.in.s_addr))
			return (1);
	} else if (pa->af == AF_INET6) {
		for (r = 0; r < 16; r++) {
			if (pa->addr.in6.s6_addr[r] < pb->addr.in6.s6_addr[r])
				return (-1);
			if (pa->addr.in6.s6_addr[r] > pb->addr.in6.s6_addr[r])
				return (1);
		}
	} else
		errx(1, "irr_prefix_cmp unknown af %u", pa->af);

	if ((r = pa->len - pb->len) != 0)
		return (r);

	return (0);
}

/* RB helpers */
int
prefix_set_compare(struct prefix_set *a, struct prefix_set *b)
{
	return (strcmp(a->as, b->as));
}

struct prefix_set *
prefix_set_find(char *as)
{
	struct prefix_set	s;

	s.as = as;
	return (RB_FIND(prefix_set_h, &prefix_set_h, &s));
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: irr_prefix.c,v 1.21 2015/10/05 14:18:33 deraadt Exp $ */
2
3			/*
4			* Copyright (c) 2007 Henning Brauer <henning@openbsd.org>
5			*
6			* Permission to use, copy, modify, and distribute this software for any
7			* purpose with or without fee is hereby granted, provided that the above
8			* copyright notice and this permission notice appear in all copies.
9			*
10			* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11			* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12			* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13			* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14			* WHATSOEVER RESULTING FROM LOSS OF MIND, USE, DATA OR PROFITS, WHETHER IN
15			* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
16			* OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17			*/
18
19			#include <sys/types.h>
20			#include <err.h>
21			#include <errno.h>
22			#include <stdio.h>
23			#include <stdlib.h>
24			#include <string.h>
25			#include <unistd.h>
26			#include <netinet/in.h>
27			#include <arpa/inet.h>
28
29			#include "irrfilter.h"
30			#include "bgpd.h"
31
32			void prefixset_aggregate(struct prefix_set *);
33			int prefix_aggregate(struct irr_prefix , const struct irr_prefix );
34			int irr_prefix_cmp(const void , const void );
35			int prefix_set_compare(struct prefix_set , struct prefix_set );
36			struct prefix_set
37			prefix_set_find(char );
38
39			RB_HEAD(prefix_set_h, prefix_set) prefix_set_h;
40			RB_PROTOTYPE(prefix_set_h, prefix_set, entry, prefix_set_compare)
41			RB_GENERATE(prefix_set_h, prefix_set, entry, prefix_set_compare)
42
43			struct prefix_set *curpfxs = NULL;
44
45			struct prefix_set *
46			prefixset_get(char *as)
47			{
48			struct prefix_set *pfxs;
49
50			if ((pfxs = prefix_set_find(as)) != NULL)
51			return (pfxs);
52
53			/* nothing found, resolve and store */
54			if ((pfxs = calloc(1, sizeof(*pfxs))) == NULL)
55			err(1, "get_prefixset calloc");
56			if ((pfxs->as = strdup(as)) == NULL)
57			err(1, "get_prefixset strdup");
58			RB_INSERT(prefix_set_h, &prefix_set_h, pfxs);
59
60			if (irrverbose >= 3) {
61			fprintf(stdout, "query routes for %s... ", as);
62			fflush(stdout);
63			}
64			curpfxs = pfxs;
65			if ((irrflags & F_IPV4) && whois(as, QTYPE_ROUTE) == -1)
66			errx(1, "whois error, prefixset_get %s", as);
67			if ((irrflags & F_IPV6) && whois(as, QTYPE_ROUTE6) == -1)
68			errx(1, "whois error, prefixset_get %s", as);
69			if (whois(as, QTYPE_ROUTE6) == -1)
70			errx(1, "whois error, prefixset_get %s", as);
71			curpfxs = NULL;
72			if (irrverbose >= 3)
73			fprintf(stdout, "done\n");
74
75			prefixset_aggregate(pfxs);
76
77			return (pfxs);
78			}
79
80			int
81			prefixset_addmember(char *s)
82			{
83			void *p;
84			u_int i;
85			struct irr_prefix *pfx;
86			int len, ret;
87			char *slash;
88			const char *errstr;
89
90			if ((slash = strchr(s, '/')) == NULL) {
91			fprintf(stderr, "%s: prefix %s does not have the len "
92			"specified, ignoring\n", curpfxs->as, s);
93			return (0);
94			}
95
96			if ((pfx = calloc(1, sizeof(*pfx))) == NULL)
97			err(1, "prefixset_addmember calloc");
98
99			if ((len = inet_net_pton(AF_INET, s, &pfx->addr.in,
100			sizeof(pfx->addr.in))) != -1) {
101			pfx->af = AF_INET;
102			} else {
103			len = strtonum(slash + 1, 0, 128, &errstr);
104			if (errstr)
105			errx(1, "prefixset_addmember %s prefix %s: prefixlen "
106			"is %s", curpfxs->as, s, errstr);
107			*slash = '\0';
108
109			if ((ret = inet_pton(AF_INET6, s, &pfx->addr.in6)) == -1)
110			err(1, "prefixset_addmember %s prefix \"%s\"",
111			curpfxs->as, s);
112			else if (ret == 0) {
113			fprintf(stderr, "prefixset_addmember %s prefix \"%s\": "
114			"No matching address family found", curpfxs->as, s);
115			free(pfx);
116			return (0);
117			}
118			pfx->af = AF_INET6;
119			}
120			pfx->len = pfx->maxlen = len;
121
122			/* yes, there are dupes... e. g. from multiple sources */
123			for (i = 0; i < curpfxs->prefixcnt; i++)
124			if (irr_prefix_cmp(&curpfxs->prefix[i], &pfx) == 0) {
125			free(pfx);
126			return (0);
127			}
128
129			if ((p = reallocarray(curpfxs->prefix,
130			curpfxs->prefixcnt + 1, sizeof(void *))) == NULL)
131			err(1, "prefixset_addmember realloc");
132			curpfxs->prefix = p;
133			curpfxs->prefixcnt++;
134			curpfxs->prefix[curpfxs->prefixcnt - 1] = pfx;
135
136			return (1);
137			}
138
139			void
140			prefixset_aggregate(struct prefix_set *pfxs)
141			{
142			u_int i, cnt, newcnt;
143			int res;
144			struct irr_prefix cur, last;
145			void *p;
146
147			qsort(pfxs->prefix, pfxs->prefixcnt, sizeof(void *), irr_prefix_cmp);
148
149			cnt = pfxs->prefixcnt;
150			do {
151			last = cur = NULL;
152			for (i = 0, newcnt = 0; i < cnt; i++) {
153			cur = pfxs->prefix[i];
154			if (last != NULL && last->af == cur->af) {
155			if (cur->af == AF_INET)
156			res = prefix_aggregate(last, cur);
157			else
158			res = 0;
159
160			if (res == 1) { /* cur is covered by last */
161			if (cur->len > last->maxlen)
162			last->maxlen = cur->len;
163			free(pfxs->prefix[i]);
164			pfxs->prefix[i] = cur = NULL;
165			}
166			}
167
168			if (cur != NULL) {
169			pfxs->prefix[newcnt++] = cur;
170			last = cur;
171			}
172			}
173			cnt = newcnt;
174			} while (newcnt < i);
175
176			if (newcnt == pfxs->prefixcnt)
177			return;
178
179			if (irrverbose >= 2)
180			printf("%s: prefix aggregation: %u -> %u\n",
181			pfxs->as, pfxs->prefixcnt, newcnt);
182
183			if ((p = reallocarray(pfxs->prefix, newcnt, sizeof(void *))) == NULL)
184			err(1, "prefixset_aggregate realloc");
185			pfxs->prefix = p;
186			pfxs->prefixcnt = newcnt;
187			}
188
189			int
190			prefix_aggregate(struct irr_prefix a, const struct irr_prefix b)
191			{
192			in_addr_t mask;
193			struct in6_addr ma;
194			struct in6_addr mb;
195
196			if (a->len == 0)
197			return (1);
198
199			if (a->af != b->af)
200			/* We cannot aggregate addresses of different families. */
201			return (0);
202
203			if (a->af == AF_INET) {
204			mask = htonl(prefixlen2mask(a->len));
205			if ((a->addr.in.s_addr & mask) == (b->addr.in.s_addr & mask))
206			return (1);
207			} else if (a->af == AF_INET6) {
208			inet6applymask(&ma, &a->addr.in6, a->len);
209			inet6applymask(&mb, &b->addr.in6, a->len);
210			if (IN6_ARE_ADDR_EQUAL(&ma, &mb))
211			return (1);
212			}
213
214			/* see whether we can fold them in one */
215			if (a->len == b->len && a->len > 1) {
216			if (a->af == AF_INET) {
217			mask = htonl(prefixlen2mask(a->len - 1));
218			if ((a->addr.in.s_addr & mask) ==
219			(b->addr.in.s_addr & mask)) {
220			a->len--;
221			a->addr.in.s_addr &= mask;
222			return (1);
223			}
224			} else if (a->af == AF_INET6) {
225			inet6applymask(&ma, &a->addr.in6, a->len - 1);
226			inet6applymask(&mb, &b->addr.in6, a->len - 1);
227
228			if (IN6_ARE_ADDR_EQUAL(&ma, &mb)) {
229			a->len--;
230			memcpy(&a->addr.in6, &ma, sizeof(ma));
231			return (1);
232			}
233			}
234			}
235
236			return (0);
237			}
238
239			int
240			irr_prefix_cmp(const void a, const void b)
241			{
242			const struct irr_prefix *pa;
243			const struct irr_prefix *pb;
244			int r;
245
246			pa = ((const struct irr_prefix const *)a);
247			pb = ((const struct irr_prefix const *)b);
248
249			if ((r = pa->af - pb->af) != 0)
250			return (r);
251
252			if (pa->af == AF_INET) {
253			if (ntohl(pa->addr.in.s_addr) <
254			ntohl(pb->addr.in.s_addr))
255			return (-1);
256			if (ntohl(pa->addr.in.s_addr) >
257			ntohl(pb->addr.in.s_addr))
258			return (1);
259			} else if (pa->af == AF_INET6) {
260			for (r = 0; r < 16; r++) {
261			if (pa->addr.in6.s6_addr[r] < pb->addr.in6.s6_addr[r])
262			return (-1);
263			if (pa->addr.in6.s6_addr[r] > pb->addr.in6.s6_addr[r])
264			return (1);
265			}
266			} else
267			errx(1, "irr_prefix_cmp unknown af %u", pa->af);
268
269			if ((r = pa->len - pb->len) != 0)
270			return (r);
271
272			return (0);
273			}
274
275			/* RB helpers */
276			int
277			prefix_set_compare(struct prefix_set a, struct prefix_set b)
278			{
279			return (strcmp(a->as, b->as));
280			}
281
282			struct prefix_set *
283			prefix_set_find(char *as)
284			{
285			struct prefix_set s;
286
287			s.as = as;
288			return (RB_FIND(prefix_set_h, &prefix_set_h, &s));
289			}