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

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
}