Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.sbin/bgpd/rde_prefix.c	Lines:	0	121	0.0 %
Date:	2016-12-06	Branches:	0	301	0.0 %


/*	$OpenBSD: rde_prefix.c,v 1.32 2010/03/26 15:41:04 claudio 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"

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