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