1 /* $OpenBSD: rde_prefix.c,v 1.56 2024/12/30 17:14:02 denis 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 117 pt_init(void) 118 { 119 RB_INIT(&pttable); 120 } 121 122 void 123 pt_shutdown(void) 124 { 125 if (!RB_EMPTY(&pttable)) 126 log_debug("pt_shutdown: tree is not empty."); 127 } 128 129 void 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 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 * 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_fill: 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 * 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 * 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 * 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 * 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 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 * 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 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 * 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 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 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 fatalx("%s: unknown aid %d", __func__, pte->aid); 568 } 569 570 /* keep 2 bytes reserved in the withdraw case for IPv4 encoding */ 571 if (withdraw && ibuf_left(buf) < ibuf_size(tmp) + 2) 572 goto fail; 573 if (ibuf_add_ibuf(buf, tmp) == -1) 574 goto fail; 575 ibuf_free(tmp); 576 return 0; 577 578 fail: 579 ibuf_free(tmp); 580 return -1; 581 } 582