Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.sbin/bgpd/rde_prefix.c	Lines:	0	121	0.0 %
Date:	2017-11-07	Branches:	0	248	0.0 %


/*	$OpenBSD: rde_prefix.c,v 1.33 2017/01/24 04:22:42 benno Exp $ */

/*
 * Copyright (c) 2003, 2004 Claudio Jeker <claudio@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 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 <sys/queue.h>

#include <errno.h>
#include <stdlib.h>
#include <string.h>

#include "bgpd.h"
#include "rde.h"
#include "log.h"

/*
 * Prefix Table functions:
 * pt_add:    create new prefix and link it into the prefix table
 * pt_remove: Checks if there is no bgp prefix linked to the prefix,
 *            unlinks from the prefix table and frees the pt_entry.
 * pt_get:    get a prefix/prefixlen entry. While pt_lookup searches for the
 *            best matching prefix pt_get only finds the prefix/prefixlen
 *            entry. The speed of pt_get is important for the bgp updates.
 * pt_getaddr: convert the address into a struct bgpd_addr.
 * pt_lookup: lookup a IP in the prefix table. Mainly for "show ip bgp".
 * pt_empty:  returns true if there is no bgp prefix linked to the pt_entry.
 * pt_init:   initialize prefix table.
 * pt_alloc: allocate a AF specific pt_entry. Internal function.
 * pt_free:   free a pt_entry. Internal function.
 */

/* internal prototypes */
static struct pt_entry	*pt_alloc(struct pt_entry *);
static void		 pt_free(struct pt_entry *);

size_t	pt_sizes[AID_MAX] = AID_PTSIZE;

RB_HEAD(pt_tree, pt_entry);
RB_PROTOTYPE(pt_tree, pt_entry, pt_e, pt_prefix_cmp);
RB_GENERATE(pt_tree, pt_entry, pt_e, pt_prefix_cmp);

struct pt_tree	pttable;

void
pt_init(void)
{
	RB_INIT(&pttable);
}

void
pt_shutdown(void)
{
	if (!RB_EMPTY(&pttable))
		log_debug("pt_shutdown: tree is not empty.");
}

void
pt_getaddr(struct pt_entry *pte, struct bgpd_addr *addr)
{
	bzero(addr, sizeof(struct bgpd_addr));
	addr->aid = pte->aid;
	switch (addr->aid) {
	case AID_INET:
		addr->v4 = ((struct pt_entry4 *)pte)->prefix4;
		break;
	case AID_INET6:
		memcpy(&addr->v6, &((struct pt_entry6 *)pte)->prefix6,
		    sizeof(addr->v6));
		/* XXX scope_id ??? */
		break;
	case AID_VPN_IPv4:
		addr->vpn4.addr = ((struct pt_entry_vpn4 *)pte)->prefix4;
		addr->vpn4.rd = ((struct pt_entry_vpn4 *)pte)->rd;
		addr->vpn4.labellen = ((struct pt_entry_vpn4 *)pte)->labellen;
		memcpy(addr->vpn4.labelstack,
		    ((struct pt_entry_vpn4 *)pte)->labelstack,
		    addr->vpn4.labellen);
		break;
	default:
		fatalx("pt_getaddr: unknown af");
	}
}

struct pt_entry *
pt_fill(struct bgpd_addr *prefix, int prefixlen)
{
	static struct pt_entry4		pte4;
	static struct pt_entry6		pte6;
	static struct pt_entry_vpn4	pte_vpn4;
	in_addr_t			addr_hbo;

	switch (prefix->aid) {
	case AID_INET:
		bzero(&pte4, sizeof(pte4));
		pte4.aid = prefix->aid;
		if (prefixlen > 32)
			fatalx("pt_fill: bad IPv4 prefixlen");
		addr_hbo = ntohl(prefix->v4.s_addr);
		pte4.prefix4.s_addr = htonl(addr_hbo &
		    prefixlen2mask(prefixlen));
		pte4.prefixlen = prefixlen;
		return ((struct pt_entry *)&pte4);
	case AID_INET6:
		bzero(&pte6, sizeof(pte6));
		pte6.aid = prefix->aid;
		if (prefixlen > 128)
			fatalx("pt_get: bad IPv6 prefixlen");
		pte6.prefixlen = prefixlen;
		inet6applymask(&pte6.prefix6, &prefix->v6, prefixlen);
		return ((struct pt_entry *)&pte6);
	case AID_VPN_IPv4:
		bzero(&pte_vpn4, sizeof(pte_vpn4));
		pte_vpn4.aid = prefix->aid;
		if (prefixlen > 32)
			fatalx("pt_fill: bad IPv4 prefixlen");
		addr_hbo = ntohl(prefix->vpn4.addr.s_addr);
		pte_vpn4.prefix4.s_addr = htonl(addr_hbo &
		    prefixlen2mask(prefixlen));
		pte_vpn4.prefixlen = prefixlen;
		pte_vpn4.rd = prefix->vpn4.rd;
		pte_vpn4.labellen = prefix->vpn4.labellen;
		memcpy(pte_vpn4.labelstack, prefix->vpn4.labelstack,
		    prefix->vpn4.labellen);
		return ((struct pt_entry *)&pte_vpn4);
	default:
		fatalx("pt_fill: unknown af");
	}
}

struct pt_entry *
pt_get(struct bgpd_addr *prefix, int prefixlen)
{
	struct pt_entry	*pte;

	pte = pt_fill(prefix, prefixlen);
	return RB_FIND(pt_tree, &pttable, pte);
}

struct pt_entry *
pt_add(struct bgpd_addr *prefix, int prefixlen)
{
	struct pt_entry		*p = NULL;

	p = pt_fill(prefix, prefixlen);
	p = pt_alloc(p);

	if (RB_INSERT(pt_tree, &pttable, p) != NULL)
		fatalx("pt_add: insert failed");

	return (p);
}

void
pt_remove(struct pt_entry *pte)
{
	if (!pt_empty(pte))
		fatalx("pt_remove: entry still holds references");

	if (RB_REMOVE(pt_tree, &pttable, pte) == NULL)
		log_warnx("pt_remove: remove failed.");
	pt_free(pte);
}

struct pt_entry *
pt_lookup(struct bgpd_addr *addr)
{
	struct pt_entry	*p;
	int		 i;

	switch (addr->aid) {
	case AID_INET:
	case AID_VPN_IPv4:
		i = 32;
		break;
	case AID_INET6:
		i = 128;
		break;
	default:
		fatalx("pt_lookup: unknown af");
	}
	for (; i >= 0; i--) {
		p = pt_get(addr, i);
		if (p != NULL)
			return (p);
	}
	return (NULL);
}

int
pt_prefix_cmp(const struct pt_entry *a, const struct pt_entry *b)
{
	const struct pt_entry4		*a4, *b4;
	const struct pt_entry6		*a6, *b6;
	const struct pt_entry_vpn4	*va4, *vb4;
	int				 i;

	if (a->aid > b->aid)
		return (1);
	if (a->aid < b->aid)
		return (-1);

	switch (a->aid) {
	case AID_INET:
		a4 = (const struct pt_entry4 *)a;
		b4 = (const struct pt_entry4 *)b;
		if (ntohl(a4->prefix4.s_addr) > ntohl(b4->prefix4.s_addr))
			return (1);
		if (ntohl(a4->prefix4.s_addr) < ntohl(b4->prefix4.s_addr))
			return (-1);
		if (a4->prefixlen > b4->prefixlen)
			return (1);
		if (a4->prefixlen < b4->prefixlen)
			return (-1);
		return (0);
	case AID_INET6:
		a6 = (const struct pt_entry6 *)a;
		b6 = (const struct pt_entry6 *)b;

		i = memcmp(&a6->prefix6, &b6->prefix6, sizeof(struct in6_addr));
		if (i > 0)
			return (1);
		if (i < 0)
			return (-1);
		if (a6->prefixlen < b6->prefixlen)
			return (-1);
		if (a6->prefixlen > b6->prefixlen)
			return (1);
		return (0);
	case AID_VPN_IPv4:
		va4 = (const struct pt_entry_vpn4 *)a;
		vb4 = (const struct pt_entry_vpn4 *)b;
		if (ntohl(va4->prefix4.s_addr) > ntohl(vb4->prefix4.s_addr))
			return (1);
		if (ntohl(va4->prefix4.s_addr) < ntohl(vb4->prefix4.s_addr))
			return (-1);
		if (va4->prefixlen > vb4->prefixlen)
			return (1);
		if (va4->prefixlen < vb4->prefixlen)
			return (-1);
		if (betoh64(va4->rd) > betoh64(vb4->rd))
			return (1);
		if (betoh64(va4->rd) < betoh64(vb4->rd))
			return (-1);
		return (0);
	default:
		fatalx("pt_prefix_cmp: unknown af");
	}
	return (-1);
}

/*
 * Returns a pt_entry cloned from the one passed in.
 * Function may not return on failure.
 */
static struct pt_entry *
pt_alloc(struct pt_entry *op)
{
	struct pt_entry		*p;

	p = malloc(pt_sizes[op->aid]);
	if (p == NULL)
		fatal("pt_alloc");
	rdemem.pt_cnt[op->aid]++;
	memcpy(p, op, pt_sizes[op->aid]);

	return (p);
}

static void
pt_free(struct pt_entry *pte)
{
	rdemem.pt_cnt[pte->aid]--;
	free(pte);
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: rde_prefix.c,v 1.33 2017/01/24 04:22:42 benno Exp $ */
2
3			/*
4			* Copyright (c) 2003, 2004 Claudio Jeker <claudio@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 USE, DATA OR PROFITS, WHETHER IN AN
15			* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16			* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17			*/
18
19			#include <sys/types.h>
20			#include <sys/queue.h>
21
22			#include <errno.h>
23			#include <stdlib.h>
24			#include <string.h>
25
26			#include "bgpd.h"
27			#include "rde.h"
28			#include "log.h"
29
30			/*
31			* Prefix Table functions:
32			* pt_add: create new prefix and link it into the prefix table
33			* pt_remove: Checks if there is no bgp prefix linked to the prefix,
34			* unlinks from the prefix table and frees the pt_entry.
35			* pt_get: get a prefix/prefixlen entry. While pt_lookup searches for the
36			* best matching prefix pt_get only finds the prefix/prefixlen
37			* entry. The speed of pt_get is important for the bgp updates.
38			* pt_getaddr: convert the address into a struct bgpd_addr.
39			* pt_lookup: lookup a IP in the prefix table. Mainly for "show ip bgp".
40			* pt_empty: returns true if there is no bgp prefix linked to the pt_entry.
41			* pt_init: initialize prefix table.
42			* pt_alloc: allocate a AF specific pt_entry. Internal function.
43			* pt_free: free a pt_entry. Internal function.
44			*/
45
46			/* internal prototypes */
47			static struct pt_entry pt_alloc(struct pt_entry );
48			static void pt_free(struct pt_entry *);
49
50			size_t pt_sizes[AID_MAX] = AID_PTSIZE;
51
52			RB_HEAD(pt_tree, pt_entry);
53			RB_PROTOTYPE(pt_tree, pt_entry, pt_e, pt_prefix_cmp);
54			RB_GENERATE(pt_tree, pt_entry, pt_e, pt_prefix_cmp);
55
56			struct pt_tree pttable;
57
58			void
59			pt_init(void)
60			{
61			RB_INIT(&pttable);
62			}
63
64			void
65			pt_shutdown(void)
66			{
67			if (!RB_EMPTY(&pttable))
68			log_debug("pt_shutdown: tree is not empty.");
69			}
70
71			void
72			pt_getaddr(struct pt_entry pte, struct bgpd_addr addr)
73			{
74			bzero(addr, sizeof(struct bgpd_addr));
75			addr->aid = pte->aid;
76			switch (addr->aid) {
77			case AID_INET:
78			addr->v4 = ((struct pt_entry4 *)pte)->prefix4;
79			break;
80			case AID_INET6:
81			memcpy(&addr->v6, &((struct pt_entry6 *)pte)->prefix6,
82			sizeof(addr->v6));
83			/* XXX scope_id ??? */
84			break;
85			case AID_VPN_IPv4:
86			addr->vpn4.addr = ((struct pt_entry_vpn4 *)pte)->prefix4;
87			addr->vpn4.rd = ((struct pt_entry_vpn4 *)pte)->rd;
88			addr->vpn4.labellen = ((struct pt_entry_vpn4 *)pte)->labellen;
89			memcpy(addr->vpn4.labelstack,
90			((struct pt_entry_vpn4 *)pte)->labelstack,
91			addr->vpn4.labellen);
92			break;
93			default:
94			fatalx("pt_getaddr: unknown af");
95			}
96			}
97
98			struct pt_entry *
99			pt_fill(struct bgpd_addr *prefix, int prefixlen)
100			{
101			static struct pt_entry4 pte4;
102			static struct pt_entry6 pte6;
103			static struct pt_entry_vpn4 pte_vpn4;
104			in_addr_t addr_hbo;
105
106			switch (prefix->aid) {
107			case AID_INET:
108			bzero(&pte4, sizeof(pte4));
109			pte4.aid = prefix->aid;
110			if (prefixlen > 32)
111			fatalx("pt_fill: bad IPv4 prefixlen");
112			addr_hbo = ntohl(prefix->v4.s_addr);
113			pte4.prefix4.s_addr = htonl(addr_hbo &
114			prefixlen2mask(prefixlen));
115			pte4.prefixlen = prefixlen;
116			return ((struct pt_entry *)&pte4);
117			case AID_INET6:
118			bzero(&pte6, sizeof(pte6));
119			pte6.aid = prefix->aid;
120			if (prefixlen > 128)
121			fatalx("pt_get: bad IPv6 prefixlen");
122			pte6.prefixlen = prefixlen;
123			inet6applymask(&pte6.prefix6, &prefix->v6, prefixlen);
124			return ((struct pt_entry *)&pte6);
125			case AID_VPN_IPv4:
126			bzero(&pte_vpn4, sizeof(pte_vpn4));
127			pte_vpn4.aid = prefix->aid;
128			if (prefixlen > 32)
129			fatalx("pt_fill: bad IPv4 prefixlen");
130			addr_hbo = ntohl(prefix->vpn4.addr.s_addr);
131			pte_vpn4.prefix4.s_addr = htonl(addr_hbo &
132			prefixlen2mask(prefixlen));
133			pte_vpn4.prefixlen = prefixlen;
134			pte_vpn4.rd = prefix->vpn4.rd;
135			pte_vpn4.labellen = prefix->vpn4.labellen;
136			memcpy(pte_vpn4.labelstack, prefix->vpn4.labelstack,
137			prefix->vpn4.labellen);
138			return ((struct pt_entry *)&pte_vpn4);
139			default:
140			fatalx("pt_fill: unknown af");
141			}
142			}
143
144			struct pt_entry *
145			pt_get(struct bgpd_addr *prefix, int prefixlen)
146			{
147			struct pt_entry *pte;
148
149			pte = pt_fill(prefix, prefixlen);
150			return RB_FIND(pt_tree, &pttable, pte);
151			}
152
153			struct pt_entry *
154			pt_add(struct bgpd_addr *prefix, int prefixlen)
155			{
156			struct pt_entry *p = NULL;
157
158			p = pt_fill(prefix, prefixlen);
159			p = pt_alloc(p);
160
161			if (RB_INSERT(pt_tree, &pttable, p) != NULL)
162			fatalx("pt_add: insert failed");
163
164			return (p);
165			}
166
167			void
168			pt_remove(struct pt_entry *pte)
169			{
170			if (!pt_empty(pte))
171			fatalx("pt_remove: entry still holds references");
172
173			if (RB_REMOVE(pt_tree, &pttable, pte) == NULL)
174			log_warnx("pt_remove: remove failed.");
175			pt_free(pte);
176			}
177
178			struct pt_entry *
179			pt_lookup(struct bgpd_addr *addr)
180			{
181			struct pt_entry *p;
182			int i;
183
184			switch (addr->aid) {
185			case AID_INET:
186			case AID_VPN_IPv4:
187			i = 32;
188			break;
189			case AID_INET6:
190			i = 128;
191			break;
192			default:
193			fatalx("pt_lookup: unknown af");
194			}
195			for (; i >= 0; i--) {
196			p = pt_get(addr, i);
197			if (p != NULL)
198			return (p);
199			}
200			return (NULL);
201			}
202
203			int
204			pt_prefix_cmp(const struct pt_entry a, const struct pt_entry b)
205			{
206			const struct pt_entry4 a4, b4;
207			const struct pt_entry6 a6, b6;
208			const struct pt_entry_vpn4 va4, vb4;
209			int i;
210
211			if (a->aid > b->aid)
212			return (1);
213			if (a->aid < b->aid)
214			return (-1);
215
216			switch (a->aid) {
217			case AID_INET:
218			a4 = (const struct pt_entry4 *)a;
219			b4 = (const struct pt_entry4 *)b;
220			if (ntohl(a4->prefix4.s_addr) > ntohl(b4->prefix4.s_addr))
221			return (1);
222			if (ntohl(a4->prefix4.s_addr) < ntohl(b4->prefix4.s_addr))
223			return (-1);
224			if (a4->prefixlen > b4->prefixlen)
225			return (1);
226			if (a4->prefixlen < b4->prefixlen)
227			return (-1);
228			return (0);
229			case AID_INET6:
230			a6 = (const struct pt_entry6 *)a;
231			b6 = (const struct pt_entry6 *)b;
232
233			i = memcmp(&a6->prefix6, &b6->prefix6, sizeof(struct in6_addr));
234			if (i > 0)
235			return (1);
236			if (i < 0)
237			return (-1);
238			if (a6->prefixlen < b6->prefixlen)
239			return (-1);
240			if (a6->prefixlen > b6->prefixlen)
241			return (1);
242			return (0);
243			case AID_VPN_IPv4:
244			va4 = (const struct pt_entry_vpn4 *)a;
245			vb4 = (const struct pt_entry_vpn4 *)b;
246			if (ntohl(va4->prefix4.s_addr) > ntohl(vb4->prefix4.s_addr))
247			return (1);
248			if (ntohl(va4->prefix4.s_addr) < ntohl(vb4->prefix4.s_addr))
249			return (-1);
250			if (va4->prefixlen > vb4->prefixlen)
251			return (1);
252			if (va4->prefixlen < vb4->prefixlen)
253			return (-1);
254			if (betoh64(va4->rd) > betoh64(vb4->rd))
255			return (1);
256			if (betoh64(va4->rd) < betoh64(vb4->rd))
257			return (-1);
258			return (0);
259			default:
260			fatalx("pt_prefix_cmp: unknown af");
261			}
262			return (-1);
263			}
264
265			/*
266			* Returns a pt_entry cloned from the one passed in.
267			* Function may not return on failure.
268			*/
269			static struct pt_entry *
270			pt_alloc(struct pt_entry *op)
271			{
272			struct pt_entry *p;
273
274			p = malloc(pt_sizes[op->aid]);
275			if (p == NULL)
276			fatal("pt_alloc");
277			rdemem.pt_cnt[op->aid]++;
278			memcpy(p, op, pt_sizes[op->aid]);
279
280			return (p);
281			}
282
283			static void
284			pt_free(struct pt_entry *pte)
285			{
286			rdemem.pt_cnt[pte->aid]--;
287			free(pte);
288			}