1 /* $OpenBSD: rde_prefix.c,v 1.50 2023/07/12 14:45:43 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 <stdint.h>
25 #include <stdlib.h>
26 #include <string.h>
27
28 #include "bgpd.h"
29 #include "rde.h"
30 #include "log.h"
31
32 /*
33 * Prefix Table functions:
34 * pt_add: create new prefix and link it into the prefix table
35 * pt_remove: Checks if there is no bgp prefix linked to the prefix,
36 * unlinks from the prefix table and frees the pt_entry.
37 * pt_get: get a prefix/prefixlen entry. While pt_lookup searches for the
38 * best matching prefix pt_get only finds the prefix/prefixlen
39 * entry. The speed of pt_get is important for the bgp updates.
40 * pt_getaddr: convert the address into a struct bgpd_addr.
41 * pt_lookup: lookup a IP in the prefix table. Mainly for "show ip bgp".
42 * pt_empty: returns true if there is no bgp prefix linked to the pt_entry.
43 * pt_init: initialize prefix table.
44 * pt_alloc: allocate a AF specific pt_entry. Internal function.
45 * pt_free: free a pt_entry. Internal function.
46 */
47
48 /* internal prototypes */
49 static struct pt_entry *pt_alloc(struct pt_entry *, int len);
50 static void pt_free(struct pt_entry *);
51
52 struct pt_entry4 {
53 RB_ENTRY(pt_entry) pt_e;
54 uint8_t aid;
55 uint8_t prefixlen;
56 uint16_t len;
57 uint32_t refcnt;
58 struct in_addr prefix4;
59 };
60
61 struct pt_entry6 {
62 RB_ENTRY(pt_entry) pt_e;
63 uint8_t aid;
64 uint8_t prefixlen;
65 uint16_t len;
66 uint32_t refcnt;
67 struct in6_addr prefix6;
68 };
69
70 struct pt_entry_vpn4 {
71 RB_ENTRY(pt_entry) pt_e;
72 uint8_t aid;
73 uint8_t prefixlen;
74 uint16_t len;
75 uint32_t refcnt;
76 uint64_t rd;
77 struct in_addr prefix4;
78 uint8_t labelstack[21];
79 uint8_t labellen;
80 uint8_t pad1;
81 uint8_t pad2;
82 };
83
84 struct pt_entry_vpn6 {
85 RB_ENTRY(pt_entry) pt_e;
86 uint8_t aid;
87 uint8_t prefixlen;
88 uint16_t len;
89 uint32_t refcnt;
90 uint64_t rd;
91 struct in6_addr prefix6;
92 uint8_t labelstack[21];
93 uint8_t labellen;
94 uint8_t pad1;
95 uint8_t pad2;
96 };
97
98 struct pt_entry_flow {
99 RB_ENTRY(pt_entry) pt_e;
100 uint8_t aid;
101 uint8_t prefixlen; /* unused ??? */
102 uint16_t len;
103 uint32_t refcnt;
104 uint64_t rd;
105 uint8_t flow[1]; /* NLRI */
106 };
107
108 #define PT_FLOW_SIZE (offsetof(struct pt_entry_flow, flow))
109
110 RB_HEAD(pt_tree, pt_entry);
111 RB_PROTOTYPE(pt_tree, pt_entry, pt_e, pt_prefix_cmp);
112 RB_GENERATE(pt_tree, pt_entry, pt_e, pt_prefix_cmp);
113
114 struct pt_tree pttable;
115
116 void
pt_init(void)117 pt_init(void)
118 {
119 RB_INIT(&pttable);
120 }
121
122 void
pt_shutdown(void)123 pt_shutdown(void)
124 {
125 if (!RB_EMPTY(&pttable))
126 log_debug("pt_shutdown: tree is not empty.");
127 }
128
129 void
pt_getaddr(struct pt_entry * pte,struct bgpd_addr * addr)130 pt_getaddr(struct pt_entry *pte, struct bgpd_addr *addr)
131 {
132 struct pt_entry_flow *pflow;
133
134 memset(addr, 0, sizeof(struct bgpd_addr));
135 addr->aid = pte->aid;
136 switch (addr->aid) {
137 case AID_INET:
138 addr->v4 = ((struct pt_entry4 *)pte)->prefix4;
139 break;
140 case AID_INET6:
141 addr->v6 = ((struct pt_entry6 *)pte)->prefix6;
142 /* XXX scope_id ??? */
143 break;
144 case AID_VPN_IPv4:
145 addr->v4 = ((struct pt_entry_vpn4 *)pte)->prefix4;
146 addr->rd = ((struct pt_entry_vpn4 *)pte)->rd;
147 addr->labellen = ((struct pt_entry_vpn4 *)pte)->labellen;
148 memcpy(addr->labelstack,
149 ((struct pt_entry_vpn4 *)pte)->labelstack,
150 addr->labellen);
151 break;
152 case AID_VPN_IPv6:
153 addr->v6 = ((struct pt_entry_vpn6 *)pte)->prefix6;
154 addr->rd = ((struct pt_entry_vpn6 *)pte)->rd;
155 addr->labellen = ((struct pt_entry_vpn6 *)pte)->labellen;
156 memcpy(addr->labelstack,
157 ((struct pt_entry_vpn6 *)pte)->labelstack,
158 addr->labellen);
159 break;
160 case AID_FLOWSPECv4:
161 case AID_FLOWSPECv6:
162 pflow = (struct pt_entry_flow *)pte;
163 flowspec_get_addr(pflow->flow, pflow->len - PT_FLOW_SIZE,
164 FLOWSPEC_TYPE_DEST, addr->aid == AID_FLOWSPECv6,
165 addr, &pflow->prefixlen, NULL);
166 break;
167 default:
168 fatalx("pt_getaddr: unknown af");
169 }
170 }
171
172 int
pt_getflowspec(struct pt_entry * pte,uint8_t ** flow)173 pt_getflowspec(struct pt_entry *pte, uint8_t **flow)
174 {
175 struct pt_entry_flow *pflow;
176
177 switch (pte->aid) {
178 case AID_FLOWSPECv4:
179 case AID_FLOWSPECv6:
180 pflow = (struct pt_entry_flow *)pte;
181 *flow = pflow->flow;
182 return pflow->len - PT_FLOW_SIZE;
183 default:
184 fatalx("pt_getflowspec: unknown af");
185 }
186 }
187
188 struct pt_entry *
pt_fill(struct bgpd_addr * prefix,int prefixlen)189 pt_fill(struct bgpd_addr *prefix, int prefixlen)
190 {
191 static struct pt_entry4 pte4;
192 static struct pt_entry6 pte6;
193 static struct pt_entry_vpn4 pte_vpn4;
194 static struct pt_entry_vpn6 pte_vpn6;
195
196 switch (prefix->aid) {
197 case AID_INET:
198 memset(&pte4, 0, sizeof(pte4));
199 pte4.len = sizeof(pte4);
200 pte4.refcnt = UINT32_MAX;
201 pte4.aid = prefix->aid;
202 if (prefixlen > 32)
203 fatalx("pt_fill: bad IPv4 prefixlen");
204 inet4applymask(&pte4.prefix4, &prefix->v4, prefixlen);
205 pte4.prefixlen = prefixlen;
206 return ((struct pt_entry *)&pte4);
207 case AID_INET6:
208 memset(&pte6, 0, sizeof(pte6));
209 pte6.len = sizeof(pte6);
210 pte6.refcnt = UINT32_MAX;
211 pte6.aid = prefix->aid;
212 if (prefixlen > 128)
213 fatalx("pt_fill: bad IPv6 prefixlen");
214 inet6applymask(&pte6.prefix6, &prefix->v6, prefixlen);
215 pte6.prefixlen = prefixlen;
216 return ((struct pt_entry *)&pte6);
217 case AID_VPN_IPv4:
218 memset(&pte_vpn4, 0, sizeof(pte_vpn4));
219 pte_vpn4.len = sizeof(pte_vpn4);
220 pte_vpn4.refcnt = UINT32_MAX;
221 pte_vpn4.aid = prefix->aid;
222 if (prefixlen > 32)
223 fatalx("pt_fill: bad IPv4 prefixlen");
224 inet4applymask(&pte_vpn4.prefix4, &prefix->v4, prefixlen);
225 pte_vpn4.prefixlen = prefixlen;
226 pte_vpn4.rd = prefix->rd;
227 pte_vpn4.labellen = prefix->labellen;
228 memcpy(pte_vpn4.labelstack, prefix->labelstack,
229 prefix->labellen);
230 return ((struct pt_entry *)&pte_vpn4);
231 case AID_VPN_IPv6:
232 memset(&pte_vpn6, 0, sizeof(pte_vpn6));
233 pte_vpn6.len = sizeof(pte_vpn6);
234 pte_vpn6.refcnt = UINT32_MAX;
235 pte_vpn6.aid = prefix->aid;
236 if (prefixlen > 128)
237 fatalx("pt_get: bad IPv6 prefixlen");
238 inet6applymask(&pte_vpn6.prefix6, &prefix->v6, prefixlen);
239 pte_vpn6.prefixlen = prefixlen;
240 pte_vpn6.rd = prefix->rd;
241 pte_vpn6.labellen = prefix->labellen;
242 memcpy(pte_vpn6.labelstack, prefix->labelstack,
243 prefix->labellen);
244 return ((struct pt_entry *)&pte_vpn6);
245 default:
246 fatalx("pt_fill: unknown af");
247 }
248 }
249
250 struct pt_entry *
pt_get(struct bgpd_addr * prefix,int prefixlen)251 pt_get(struct bgpd_addr *prefix, int prefixlen)
252 {
253 struct pt_entry *pte;
254
255 pte = pt_fill(prefix, prefixlen);
256 return RB_FIND(pt_tree, &pttable, pte);
257 }
258
259 struct pt_entry *
pt_add(struct bgpd_addr * prefix,int prefixlen)260 pt_add(struct bgpd_addr *prefix, int prefixlen)
261 {
262 struct pt_entry *p = NULL;
263
264 p = pt_fill(prefix, prefixlen);
265 p = pt_alloc(p, p->len);
266
267 if (RB_INSERT(pt_tree, &pttable, p) != NULL)
268 fatalx("pt_add: insert failed");
269
270 return (p);
271 }
272
273 struct pt_entry *
pt_get_flow(struct flowspec * f)274 pt_get_flow(struct flowspec *f)
275 {
276 struct pt_entry *needle;
277 union {
278 struct pt_entry_flow flow;
279 uint8_t buf[4096];
280 } x;
281
282 needle = (struct pt_entry *)&x.flow;
283
284 memset(needle, 0, PT_FLOW_SIZE);
285 needle->aid = f->aid;
286 needle->len = f->len + PT_FLOW_SIZE;
287 memcpy(((struct pt_entry_flow *)needle)->flow, f->data, f->len);
288
289 return RB_FIND(pt_tree, &pttable, (struct pt_entry *)needle);
290 }
291
292 struct pt_entry *
pt_add_flow(struct flowspec * f)293 pt_add_flow(struct flowspec *f)
294 {
295 struct pt_entry *p;
296 int len = f->len + PT_FLOW_SIZE;
297
298 p = malloc(len);
299 if (p == NULL)
300 fatal(__func__);
301 rdemem.pt_cnt[f->aid]++;
302 rdemem.pt_size[f->aid] += len;
303 memset(p, 0, PT_FLOW_SIZE);
304
305 p->len = len;
306 p->aid = f->aid;
307 memcpy(((struct pt_entry_flow *)p)->flow, f->data, f->len);
308
309 if (RB_INSERT(pt_tree, &pttable, p) != NULL)
310 fatalx("pt_add: insert failed");
311
312 return (p);
313 }
314
315 void
pt_remove(struct pt_entry * pte)316 pt_remove(struct pt_entry *pte)
317 {
318 if (pte->refcnt != 0)
319 fatalx("pt_remove: entry still holds references");
320
321 if (RB_REMOVE(pt_tree, &pttable, pte) == NULL)
322 log_warnx("pt_remove: remove failed.");
323 pt_free(pte);
324 }
325
326 struct pt_entry *
pt_lookup(struct bgpd_addr * addr)327 pt_lookup(struct bgpd_addr *addr)
328 {
329 struct pt_entry *p;
330 int i;
331
332 switch (addr->aid) {
333 case AID_INET:
334 case AID_VPN_IPv4:
335 i = 32;
336 break;
337 case AID_INET6:
338 case AID_VPN_IPv6:
339 i = 128;
340 break;
341 default:
342 fatalx("pt_lookup: unknown af");
343 }
344 for (; i >= 0; i--) {
345 p = pt_get(addr, i);
346 if (p != NULL)
347 return (p);
348 }
349 return (NULL);
350 }
351
352 int
pt_prefix_cmp(const struct pt_entry * a,const struct pt_entry * b)353 pt_prefix_cmp(const struct pt_entry *a, const struct pt_entry *b)
354 {
355 const struct pt_entry4 *a4, *b4;
356 const struct pt_entry6 *a6, *b6;
357 const struct pt_entry_vpn4 *va4, *vb4;
358 const struct pt_entry_vpn6 *va6, *vb6;
359 const struct pt_entry_flow *af, *bf;
360 int i;
361
362 if (a->aid > b->aid)
363 return (1);
364 if (a->aid < b->aid)
365 return (-1);
366
367 switch (a->aid) {
368 case AID_INET:
369 a4 = (const struct pt_entry4 *)a;
370 b4 = (const struct pt_entry4 *)b;
371 if (ntohl(a4->prefix4.s_addr) > ntohl(b4->prefix4.s_addr))
372 return (1);
373 if (ntohl(a4->prefix4.s_addr) < ntohl(b4->prefix4.s_addr))
374 return (-1);
375 if (a4->prefixlen > b4->prefixlen)
376 return (1);
377 if (a4->prefixlen < b4->prefixlen)
378 return (-1);
379 return (0);
380 case AID_INET6:
381 a6 = (const struct pt_entry6 *)a;
382 b6 = (const struct pt_entry6 *)b;
383
384 i = memcmp(&a6->prefix6, &b6->prefix6, sizeof(struct in6_addr));
385 if (i > 0)
386 return (1);
387 if (i < 0)
388 return (-1);
389 if (a6->prefixlen < b6->prefixlen)
390 return (-1);
391 if (a6->prefixlen > b6->prefixlen)
392 return (1);
393 return (0);
394 case AID_VPN_IPv4:
395 va4 = (const struct pt_entry_vpn4 *)a;
396 vb4 = (const struct pt_entry_vpn4 *)b;
397 if (be64toh(va4->rd) > be64toh(vb4->rd))
398 return (1);
399 if (be64toh(va4->rd) < be64toh(vb4->rd))
400 return (-1);
401 if (ntohl(va4->prefix4.s_addr) > ntohl(vb4->prefix4.s_addr))
402 return (1);
403 if (ntohl(va4->prefix4.s_addr) < ntohl(vb4->prefix4.s_addr))
404 return (-1);
405 if (va4->prefixlen > vb4->prefixlen)
406 return (1);
407 if (va4->prefixlen < vb4->prefixlen)
408 return (-1);
409 return (0);
410 case AID_VPN_IPv6:
411 va6 = (const struct pt_entry_vpn6 *)a;
412 vb6 = (const struct pt_entry_vpn6 *)b;
413 if (be64toh(va6->rd) > be64toh(vb6->rd))
414 return (1);
415 if (be64toh(va6->rd) < be64toh(vb6->rd))
416 return (-1);
417 i = memcmp(&va6->prefix6, &vb6->prefix6,
418 sizeof(struct in6_addr));
419 if (i > 0)
420 return (1);
421 if (i < 0)
422 return (-1);
423 if (va6->prefixlen > vb6->prefixlen)
424 return (1);
425 if (va6->prefixlen < vb6->prefixlen)
426 return (-1);
427 return (0);
428 case AID_FLOWSPECv4:
429 case AID_FLOWSPECv6:
430 af = (const struct pt_entry_flow *)a;
431 bf = (const struct pt_entry_flow *)b;
432 return flowspec_cmp(af->flow, af->len - PT_FLOW_SIZE,
433 bf->flow, bf->len - PT_FLOW_SIZE,
434 a->aid == AID_FLOWSPECv6);
435 default:
436 fatalx("pt_prefix_cmp: unknown af");
437 }
438 return (-1);
439 }
440
441 /*
442 * Returns a pt_entry cloned from the one passed in.
443 * Function may not return on failure.
444 */
445 static struct pt_entry *
pt_alloc(struct pt_entry * op,int len)446 pt_alloc(struct pt_entry *op, int len)
447 {
448 struct pt_entry *p;
449
450 p = malloc(len);
451 if (p == NULL)
452 fatal("pt_alloc");
453 rdemem.pt_cnt[op->aid]++;
454 rdemem.pt_size[op->aid] += len;
455 memcpy(p, op, len);
456 p->refcnt = 0;
457
458 return (p);
459 }
460
461 static void
pt_free(struct pt_entry * pte)462 pt_free(struct pt_entry *pte)
463 {
464 rdemem.pt_cnt[pte->aid]--;
465 rdemem.pt_size[pte->aid] -= pte->len;
466 free(pte);
467 }
468
469 /* dump a prefix into specified buffer */
470 int
pt_writebuf(struct ibuf * buf,struct pt_entry * pte,int withdraw,int add_path,uint32_t pathid)471 pt_writebuf(struct ibuf *buf, struct pt_entry *pte, int withdraw,
472 int add_path, uint32_t pathid)
473 {
474 struct pt_entry_vpn4 *pvpn4 = (struct pt_entry_vpn4 *)pte;
475 struct pt_entry_vpn6 *pvpn6 = (struct pt_entry_vpn6 *)pte;
476 struct pt_entry_flow *pflow = (struct pt_entry_flow *)pte;
477 struct ibuf *tmp;
478 int flowlen, psize;
479 uint8_t plen;
480
481 if ((tmp = ibuf_dynamic(32, UINT16_MAX)) == NULL)
482 goto fail;
483
484 if (add_path) {
485 if (ibuf_add_n32(tmp, pathid) == -1)
486 goto fail;
487 }
488
489 switch (pte->aid) {
490 case AID_INET:
491 case AID_INET6:
492 plen = pte->prefixlen;
493 if (ibuf_add_n8(tmp, plen) == -1)
494 goto fail;
495 if (ibuf_add(tmp, pte->data, PREFIX_SIZE(plen) - 1) == -1)
496 goto fail;
497 break;
498 case AID_VPN_IPv4:
499 plen = pvpn4->prefixlen;
500 psize = PREFIX_SIZE(plen) - 1;
501 plen += sizeof(pvpn4->rd) * 8;
502 if (withdraw) {
503 /* withdraw have one compat label as placeholder */
504 plen += 3 * 8;
505 } else {
506 plen += pvpn4->labellen * 8;
507 }
508
509 if (ibuf_add_n8(tmp, plen) == -1)
510 goto fail;
511 if (withdraw) {
512 /* magic compatibility label as per rfc8277 */
513 if (ibuf_add_n8(tmp, 0x80) == -1 ||
514 ibuf_add_zero(tmp, 2) == -1)
515 goto fail;
516 } else {
517 if (ibuf_add(tmp, &pvpn4->labelstack,
518 pvpn4->labellen) == -1)
519 goto fail;
520 }
521 if (ibuf_add(tmp, &pvpn4->rd, sizeof(pvpn4->rd)) == -1 ||
522 ibuf_add(tmp, &pvpn4->prefix4, psize) == -1)
523 goto fail;
524 break;
525 case AID_VPN_IPv6:
526 plen = pvpn6->prefixlen;
527 psize = PREFIX_SIZE(plen) - 1;
528 plen += sizeof(pvpn6->rd) * 8;
529 if (withdraw) {
530 /* withdraw have one compat label as placeholder */
531 plen += 3 * 8;
532 } else {
533 plen += pvpn6->labellen * 8;
534 }
535
536 if (ibuf_add_n8(tmp, plen) == -1)
537 goto fail;
538 if (withdraw) {
539 /* magic compatibility label as per rfc8277 */
540 if (ibuf_add_n8(tmp, 0x80) == -1 ||
541 ibuf_add_zero(tmp, 2) == -1)
542 goto fail;
543 } else {
544 if (ibuf_add(tmp, &pvpn6->labelstack,
545 pvpn6->labellen) == -1)
546 goto fail;
547 }
548 if (ibuf_add(tmp, &pvpn6->rd, sizeof(pvpn6->rd)) == -1 ||
549 ibuf_add(tmp, &pvpn6->prefix6, psize) == -1)
550 goto fail;
551 break;
552 case AID_FLOWSPECv4:
553 case AID_FLOWSPECv6:
554 flowlen = pflow->len - PT_FLOW_SIZE;
555 if (flowlen < FLOWSPEC_LEN_LIMIT) {
556 if (ibuf_add_n8(tmp, flowlen) == -1)
557 goto fail;
558 } else {
559 if (ibuf_add_n8(tmp, 0xf0 | (flowlen >> 8)) == -1 ||
560 ibuf_add_n8(tmp, flowlen) == -1)
561 goto fail;
562 }
563 if (ibuf_add(tmp, &pflow->flow, flowlen) == -1)
564 goto fail;
565 break;
566 default:
567 goto fail;
568 }
569
570 if (ibuf_add_buf(buf, tmp) == -1)
571 goto fail;
572 ibuf_free(tmp);
573 return 0;
574
575 fail:
576 ibuf_free(tmp);
577 return -1;
578 }
579