1 /* $OpenBSD: rde_attr.c,v 1.95 2015/10/24 08:00:42 claudio Exp $ */ 2 3 /* 4 * Copyright (c) 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 <netinet/in.h> 23 24 #include <limits.h> 25 #include <stdlib.h> 26 #include <stdio.h> 27 #include <string.h> 28 #include <siphash.h> 29 30 #include "bgpd.h" 31 #include "rde.h" 32 33 int 34 attr_write(void *p, u_int16_t p_len, u_int8_t flags, u_int8_t type, 35 void *data, u_int16_t data_len) 36 { 37 u_char *b = p; 38 u_int16_t tmp, tot_len = 2; /* attribute header (without len) */ 39 40 flags &= ~ATTR_DEFMASK; 41 if (data_len > 255) { 42 tot_len += 2 + data_len; 43 flags |= ATTR_EXTLEN; 44 } else { 45 tot_len += 1 + data_len; 46 } 47 48 if (tot_len > p_len) 49 return (-1); 50 51 *b++ = flags; 52 *b++ = type; 53 if (data_len > 255) { 54 tmp = htons(data_len); 55 memcpy(b, &tmp, sizeof(tmp)); 56 b += 2; 57 } else 58 *b++ = (u_char)data_len; 59 60 if (data_len != 0) 61 memcpy(b, data, data_len); 62 63 return (tot_len); 64 } 65 66 int 67 attr_writebuf(struct ibuf *buf, u_int8_t flags, u_int8_t type, void *data, 68 u_int16_t data_len) 69 { 70 u_char hdr[4]; 71 72 flags &= ~ATTR_DEFMASK; 73 if (data_len > 255) { 74 flags |= ATTR_EXTLEN; 75 hdr[2] = (data_len >> 8) & 0xff; 76 hdr[3] = data_len & 0xff; 77 } else { 78 hdr[2] = data_len & 0xff; 79 } 80 81 hdr[0] = flags; 82 hdr[1] = type; 83 84 if (ibuf_add(buf, hdr, flags & ATTR_EXTLEN ? 4 : 3) == -1) 85 return (-1); 86 if (ibuf_add(buf, data, data_len) == -1) 87 return (-1); 88 return (0); 89 } 90 91 /* optional attribute specific functions */ 92 int attr_diff(struct attr *, struct attr *); 93 struct attr *attr_alloc(u_int8_t, u_int8_t, const void *, u_int16_t); 94 struct attr *attr_lookup(u_int8_t, u_int8_t, const void *, u_int16_t); 95 void attr_put(struct attr *); 96 97 struct attr_table { 98 struct attr_list *hashtbl; 99 u_int32_t hashmask; 100 } attrtable; 101 102 SIPHASH_KEY attrtablekey; 103 104 #define ATTR_HASH(x) \ 105 &attrtable.hashtbl[(x) & attrtable.hashmask] 106 107 void 108 attr_init(u_int32_t hashsize) 109 { 110 u_int32_t hs, i; 111 112 arc4random_buf(&attrtablekey, sizeof(attrtablekey)); 113 for (hs = 1; hs < hashsize; hs <<= 1) 114 ; 115 attrtable.hashtbl = calloc(hs, sizeof(struct attr_list)); 116 if (attrtable.hashtbl == NULL) 117 fatal("attr_init"); 118 119 for (i = 0; i < hs; i++) 120 LIST_INIT(&attrtable.hashtbl[i]); 121 122 attrtable.hashmask = hs - 1; 123 } 124 125 void 126 attr_shutdown(void) 127 { 128 u_int32_t i; 129 130 for (i = 0; i <= attrtable.hashmask; i++) 131 if (!LIST_EMPTY(&attrtable.hashtbl[i])) 132 log_warnx("attr_shutdown: free non-free table"); 133 134 free(attrtable.hashtbl); 135 } 136 137 int 138 attr_optadd(struct rde_aspath *asp, u_int8_t flags, u_int8_t type, 139 void *data, u_int16_t len) 140 { 141 u_int8_t l; 142 struct attr *a, *t; 143 void *p; 144 145 /* known optional attributes were validated previously */ 146 if ((a = attr_lookup(flags, type, data, len)) == NULL) 147 a = attr_alloc(flags, type, data, len); 148 149 /* attribute allowed only once */ 150 for (l = 0; l < asp->others_len; l++) { 151 if (asp->others[l] == NULL) 152 break; 153 if (type == asp->others[l]->type) { 154 if (a->refcnt == 0) 155 attr_put(a); 156 return (-1); 157 } 158 } 159 160 /* add attribute to the table but first bump refcnt */ 161 a->refcnt++; 162 rdemem.attr_refs++; 163 164 for (l = 0; l < asp->others_len; l++) { 165 if (asp->others[l] == NULL) { 166 asp->others[l] = a; 167 return (0); 168 } 169 /* list is sorted */ 170 if (a->type < asp->others[l]->type) { 171 t = asp->others[l]; 172 asp->others[l] = a; 173 a = t; 174 } 175 } 176 177 /* no empty slot found, need to realloc */ 178 if (asp->others_len == UCHAR_MAX) 179 fatalx("attr_optadd: others_len overflow"); 180 181 asp->others_len++; 182 if ((p = reallocarray(asp->others, 183 asp->others_len, sizeof(struct attr *))) == NULL) 184 fatal("attr_optadd"); 185 asp->others = p; 186 187 /* l stores the size of others before resize */ 188 asp->others[l] = a; 189 return (0); 190 } 191 192 struct attr * 193 attr_optget(const struct rde_aspath *asp, u_int8_t type) 194 { 195 u_int8_t l; 196 197 for (l = 0; l < asp->others_len; l++) { 198 if (asp->others[l] == NULL) 199 break; 200 if (type == asp->others[l]->type) 201 return (asp->others[l]); 202 if (type < asp->others[l]->type) 203 break; 204 } 205 return (NULL); 206 } 207 208 void 209 attr_copy(struct rde_aspath *t, struct rde_aspath *s) 210 { 211 u_int8_t l; 212 213 if (t->others != NULL) 214 attr_freeall(t); 215 216 t->others_len = s->others_len; 217 if (t->others_len == 0) { 218 t->others = NULL; 219 return; 220 } 221 222 if ((t->others = calloc(s->others_len, sizeof(struct attr *))) == 0) 223 fatal("attr_copy"); 224 225 for (l = 0; l < t->others_len; l++) { 226 if (s->others[l] == NULL) 227 break; 228 s->others[l]->refcnt++; 229 rdemem.attr_refs++; 230 t->others[l] = s->others[l]; 231 } 232 } 233 234 int 235 attr_diff(struct attr *oa, struct attr *ob) 236 { 237 int r; 238 239 if (ob == NULL) 240 return (1); 241 if (oa == NULL) 242 return (-1); 243 if (oa->flags > ob->flags) 244 return (1); 245 if (oa->flags < ob->flags) 246 return (-1); 247 if (oa->type > ob->type) 248 return (1); 249 if (oa->type < ob->type) 250 return (-1); 251 if (oa->len > ob->len) 252 return (1); 253 if (oa->len < ob->len) 254 return (-1); 255 r = memcmp(oa->data, ob->data, oa->len); 256 if (r > 0) 257 return (1); 258 if (r < 0) 259 return (-1); 260 261 fatalx("attr_diff: equal attributes encountered"); 262 return (0); 263 } 264 265 int 266 attr_compare(struct rde_aspath *a, struct rde_aspath *b) 267 { 268 u_int8_t l, min; 269 270 min = a->others_len < b->others_len ? a->others_len : b->others_len; 271 for (l = 0; l < min; l++) 272 if (a->others[l] != b->others[l]) 273 return (attr_diff(a->others[l], b->others[l])); 274 275 if (a->others_len < b->others_len) { 276 for (; l < b->others_len; l++) 277 if (b->others[l] != NULL) 278 return (-1); 279 } else if (a->others_len > b->others_len) { 280 for (; l < a->others_len; l++) 281 if (a->others[l] != NULL) 282 return (1); 283 } 284 285 return (0); 286 } 287 288 void 289 attr_free(struct rde_aspath *asp, struct attr *attr) 290 { 291 u_int8_t l; 292 293 for (l = 0; l < asp->others_len; l++) 294 if (asp->others[l] == attr) { 295 attr_put(asp->others[l]); 296 for (++l; l < asp->others_len; l++) 297 asp->others[l - 1] = asp->others[l]; 298 asp->others[asp->others_len - 1] = NULL; 299 return; 300 } 301 302 /* no realloc() because the slot may be reused soon */ 303 } 304 305 void 306 attr_freeall(struct rde_aspath *asp) 307 { 308 u_int8_t l; 309 310 for (l = 0; l < asp->others_len; l++) 311 attr_put(asp->others[l]); 312 313 free(asp->others); 314 asp->others = NULL; 315 asp->others_len = 0; 316 } 317 318 struct attr * 319 attr_alloc(u_int8_t flags, u_int8_t type, const void *data, u_int16_t len) 320 { 321 struct attr *a; 322 SIPHASH_CTX ctx; 323 324 a = calloc(1, sizeof(struct attr)); 325 if (a == NULL) 326 fatal("attr_optadd"); 327 rdemem.attr_cnt++; 328 329 flags &= ~ATTR_DEFMASK; /* normalize mask */ 330 a->flags = flags; 331 a->type = type; 332 a->len = len; 333 if (len != 0) { 334 if ((a->data = malloc(len)) == NULL) 335 fatal("attr_optadd"); 336 337 rdemem.attr_dcnt++; 338 rdemem.attr_data += len; 339 memcpy(a->data, data, len); 340 } else 341 a->data = NULL; 342 343 SipHash24_Init(&ctx, &attrtablekey); 344 SipHash24_Update(&ctx, &flags, sizeof(flags)); 345 SipHash24_Update(&ctx, &type, sizeof(type)); 346 SipHash24_Update(&ctx, &len, sizeof(len)); 347 SipHash24_Update(&ctx, a->data, a->len); 348 a->hash = SipHash24_End(&ctx); 349 LIST_INSERT_HEAD(ATTR_HASH(a->hash), a, entry); 350 351 return (a); 352 } 353 354 struct attr * 355 attr_lookup(u_int8_t flags, u_int8_t type, const void *data, u_int16_t len) 356 { 357 struct attr_list *head; 358 struct attr *a; 359 u_int32_t hash; 360 SIPHASH_CTX ctx; 361 362 flags &= ~ATTR_DEFMASK; /* normalize mask */ 363 364 SipHash24_Init(&ctx, &attrtablekey); 365 SipHash24_Update(&ctx, &flags, sizeof(flags)); 366 SipHash24_Update(&ctx, &type, sizeof(type)); 367 SipHash24_Update(&ctx, &len, sizeof(len)); 368 SipHash24_Update(&ctx, data, len); 369 hash = SipHash24_End(&ctx); 370 head = ATTR_HASH(hash); 371 372 LIST_FOREACH(a, head, entry) { 373 if (hash == a->hash && type == a->type && 374 flags == a->flags && len == a->len && 375 memcmp(data, a->data, len) == 0) 376 return (a); 377 } 378 return (NULL); 379 } 380 381 void 382 attr_put(struct attr *a) 383 { 384 if (a == NULL) 385 return; 386 387 rdemem.attr_refs--; 388 if (--a->refcnt > 0) 389 /* somebody still holds a reference */ 390 return; 391 392 /* unlink */ 393 LIST_REMOVE(a, entry); 394 395 if (a->len != 0) 396 rdemem.attr_dcnt--; 397 rdemem.attr_data -= a->len; 398 rdemem.attr_cnt--; 399 free(a->data); 400 free(a); 401 } 402 403 /* aspath specific functions */ 404 405 u_int16_t aspath_countlength(struct aspath *, u_int16_t, int); 406 void aspath_countcopy(struct aspath *, u_int16_t, u_int8_t *, 407 u_int16_t, int); 408 struct aspath *aspath_lookup(const void *, u_int16_t); 409 410 struct aspath_table { 411 struct aspath_list *hashtbl; 412 u_int32_t hashmask; 413 } astable; 414 415 SIPHASH_KEY astablekey; 416 417 #define ASPATH_HASH(x) \ 418 &astable.hashtbl[(x) & astable.hashmask] 419 420 int 421 aspath_verify(void *data, u_int16_t len, int as4byte) 422 { 423 u_int8_t *seg = data; 424 u_int16_t seg_size, as_size = 2; 425 u_int8_t seg_len, seg_type; 426 int error = 0; 427 428 if (len & 1) 429 /* odd length aspath are invalid */ 430 return (AS_ERR_BAD); 431 432 if (as4byte) 433 as_size = 4; 434 435 for (; len > 0; len -= seg_size, seg += seg_size) { 436 if (len < 2) /* header length check */ 437 return (AS_ERR_BAD); 438 seg_type = seg[0]; 439 seg_len = seg[1]; 440 441 /* 442 * BGP confederations should not show up but consider them 443 * as a soft error which invalidates the path but keeps the 444 * bgp session running. 445 */ 446 if (seg_type == AS_CONFED_SEQUENCE || seg_type == AS_CONFED_SET) 447 error = AS_ERR_SOFT; 448 if (seg_type != AS_SET && seg_type != AS_SEQUENCE && 449 seg_type != AS_CONFED_SEQUENCE && seg_type != AS_CONFED_SET) 450 return (AS_ERR_TYPE); 451 452 seg_size = 2 + as_size * seg_len; 453 454 if (seg_size > len) 455 return (AS_ERR_LEN); 456 457 if (seg_size == 0) 458 /* empty aspath segments are not allowed */ 459 return (AS_ERR_BAD); 460 } 461 return (error); /* aspath is valid but probably not loop free */ 462 } 463 464 void 465 aspath_init(u_int32_t hashsize) 466 { 467 u_int32_t hs, i; 468 469 for (hs = 1; hs < hashsize; hs <<= 1) 470 ; 471 astable.hashtbl = calloc(hs, sizeof(struct aspath_list)); 472 if (astable.hashtbl == NULL) 473 fatal("aspath_init"); 474 475 for (i = 0; i < hs; i++) 476 LIST_INIT(&astable.hashtbl[i]); 477 478 astable.hashmask = hs - 1; 479 arc4random_buf(&astablekey, sizeof(astablekey)); 480 } 481 482 void 483 aspath_shutdown(void) 484 { 485 u_int32_t i; 486 487 for (i = 0; i <= astable.hashmask; i++) 488 if (!LIST_EMPTY(&astable.hashtbl[i])) 489 log_warnx("aspath_shutdown: free non-free table"); 490 491 free(astable.hashtbl); 492 } 493 494 struct aspath * 495 aspath_get(void *data, u_int16_t len) 496 { 497 struct aspath_list *head; 498 struct aspath *aspath; 499 500 /* The aspath must already have been checked for correctness. */ 501 aspath = aspath_lookup(data, len); 502 if (aspath == NULL) { 503 aspath = malloc(ASPATH_HEADER_SIZE + len); 504 if (aspath == NULL) 505 fatal("aspath_get"); 506 507 rdemem.aspath_cnt++; 508 rdemem.aspath_size += ASPATH_HEADER_SIZE + len; 509 510 aspath->refcnt = 0; 511 aspath->len = len; 512 aspath->ascnt = aspath_count(data, len); 513 memcpy(aspath->data, data, len); 514 515 /* link */ 516 head = ASPATH_HASH(SipHash24(&astablekey, aspath->data, 517 aspath->len)); 518 LIST_INSERT_HEAD(head, aspath, entry); 519 } 520 aspath->refcnt++; 521 rdemem.aspath_refs++; 522 523 return (aspath); 524 } 525 526 void 527 aspath_put(struct aspath *aspath) 528 { 529 if (aspath == NULL) 530 return; 531 532 rdemem.aspath_refs--; 533 if (--aspath->refcnt > 0) { 534 /* somebody still holds a reference */ 535 return; 536 } 537 538 /* unlink */ 539 LIST_REMOVE(aspath, entry); 540 541 rdemem.aspath_cnt--; 542 rdemem.aspath_size -= ASPATH_HEADER_SIZE + aspath->len; 543 free(aspath); 544 } 545 546 u_char * 547 aspath_inflate(void *data, u_int16_t len, u_int16_t *newlen) 548 { 549 u_int8_t *seg, *nseg, *ndata; 550 u_int16_t seg_size, olen, nlen; 551 u_int8_t seg_len; 552 553 /* first calculate the length of the aspath */ 554 seg = data; 555 nlen = 0; 556 for (olen = len; olen > 0; olen -= seg_size, seg += seg_size) { 557 seg_len = seg[1]; 558 seg_size = 2 + sizeof(u_int16_t) * seg_len; 559 nlen += 2 + sizeof(u_int32_t) * seg_len; 560 561 if (seg_size > olen) 562 fatalx("aspath_inflate: would overflow"); 563 } 564 565 *newlen = nlen; 566 if ((ndata = malloc(nlen)) == NULL) 567 fatal("aspath_inflate"); 568 569 /* then copy the aspath */ 570 seg = data; 571 for (nseg = ndata; nseg < ndata + nlen; ) { 572 *nseg++ = *seg++; 573 *nseg++ = seg_len = *seg++; 574 for (; seg_len > 0; seg_len--) { 575 *nseg++ = 0; 576 *nseg++ = 0; 577 *nseg++ = *seg++; 578 *nseg++ = *seg++; 579 } 580 } 581 582 return (ndata); 583 } 584 585 /* convert a 4 byte aspath to a 2byte one. data is freed by aspath_deflate */ 586 u_char * 587 aspath_deflate(u_char *data, u_int16_t *len, int *flagnew) 588 { 589 u_int8_t *seg, *nseg, *ndata; 590 u_int32_t as; 591 int i; 592 u_int16_t seg_size, olen, nlen; 593 u_int8_t seg_len; 594 595 /* first calculate the length of the aspath */ 596 nlen = 0; 597 seg = data; 598 olen = *len; 599 for (; olen > 0; olen -= seg_size, seg += seg_size) { 600 seg_len = seg[1]; 601 seg_size = 2 + sizeof(u_int32_t) * seg_len; 602 nlen += 2 + sizeof(u_int16_t) * seg_len; 603 604 if (seg_size > olen) 605 fatalx("aspath_deflate: would overflow"); 606 } 607 608 if ((ndata = malloc(nlen)) == NULL) 609 fatal("aspath_deflate"); 610 611 /* then copy the aspath */ 612 seg = data; 613 olen = *len; 614 for (nseg = ndata; seg < data + olen; seg += seg_size) { 615 *nseg++ = seg[0]; 616 *nseg++ = seg_len = seg[1]; 617 seg_size = 2 + sizeof(u_int32_t) * seg_len; 618 619 for (i = 0; i < seg_len; i++) { 620 as = aspath_extract(seg, i); 621 if (as > USHRT_MAX) { 622 as = AS_TRANS; 623 *flagnew = 1; 624 } 625 *nseg++ = (as >> 8) & 0xff; 626 *nseg++ = as & 0xff; 627 } 628 } 629 630 free(data); 631 *len = nlen; 632 return (ndata); 633 } 634 635 void 636 aspath_merge(struct rde_aspath *a, struct attr *attr) 637 { 638 u_int8_t *np; 639 u_int16_t ascnt, diff, nlen, difflen; 640 int hroom = 0; 641 642 ascnt = aspath_count(attr->data, attr->len); 643 if (ascnt > a->aspath->ascnt) { 644 /* ASPATH is shorter then AS4_PATH no way to merge */ 645 attr_free(a, attr); 646 return; 647 } 648 649 diff = a->aspath->ascnt - ascnt; 650 if (diff && attr->len > 2 && attr->data[0] == AS_SEQUENCE) 651 hroom = attr->data[1]; 652 difflen = aspath_countlength(a->aspath, diff, hroom); 653 nlen = attr->len + difflen; 654 655 if ((np = malloc(nlen)) == NULL) 656 fatal("aspath_merge"); 657 658 /* copy head from old aspath */ 659 aspath_countcopy(a->aspath, diff, np, difflen, hroom); 660 661 /* copy tail from new aspath */ 662 if (hroom > 0) 663 memcpy(np + nlen - attr->len + 2, attr->data + 2, 664 attr->len - 2); 665 else 666 memcpy(np + nlen - attr->len, attr->data, attr->len); 667 668 aspath_put(a->aspath); 669 a->aspath = aspath_get(np, nlen); 670 free(np); 671 attr_free(a, attr); 672 } 673 674 u_char * 675 aspath_dump(struct aspath *aspath) 676 { 677 return (aspath->data); 678 } 679 680 u_int16_t 681 aspath_length(struct aspath *aspath) 682 { 683 return (aspath->len); 684 } 685 686 u_int16_t 687 aspath_count(const void *data, u_int16_t len) 688 { 689 const u_int8_t *seg; 690 u_int16_t cnt, seg_size; 691 u_int8_t seg_type, seg_len; 692 693 cnt = 0; 694 seg = data; 695 for (; len > 0; len -= seg_size, seg += seg_size) { 696 seg_type = seg[0]; 697 seg_len = seg[1]; 698 seg_size = 2 + sizeof(u_int32_t) * seg_len; 699 700 if (seg_type == AS_SET) 701 cnt += 1; 702 else 703 cnt += seg_len; 704 705 if (seg_size > len) 706 fatalx("aspath_count: would overflow"); 707 } 708 return (cnt); 709 } 710 711 u_int16_t 712 aspath_countlength(struct aspath *aspath, u_int16_t cnt, int headcnt) 713 { 714 const u_int8_t *seg; 715 u_int16_t seg_size, len, clen; 716 u_int8_t seg_type = 0, seg_len = 0; 717 718 seg = aspath->data; 719 clen = 0; 720 for (len = aspath->len; len > 0 && cnt > 0; 721 len -= seg_size, seg += seg_size) { 722 seg_type = seg[0]; 723 seg_len = seg[1]; 724 seg_size = 2 + sizeof(u_int32_t) * seg_len; 725 726 if (seg_type == AS_SET) 727 cnt -= 1; 728 else if (seg_len > cnt) { 729 seg_len = cnt; 730 clen += 2 + sizeof(u_int32_t) * cnt; 731 break; 732 } else 733 cnt -= seg_len; 734 735 clen += seg_size; 736 737 if (seg_size > len) 738 fatalx("aspath_countlength: would overflow"); 739 } 740 if (headcnt > 0 && seg_type == AS_SEQUENCE && headcnt + seg_len < 256) 741 /* no need for additional header from the new aspath. */ 742 clen -= 2; 743 744 return (clen); 745 } 746 747 void 748 aspath_countcopy(struct aspath *aspath, u_int16_t cnt, u_int8_t *buf, 749 u_int16_t size, int headcnt) 750 { 751 const u_int8_t *seg; 752 u_int16_t seg_size, len; 753 u_int8_t seg_type, seg_len; 754 755 if (headcnt > 0) 756 /* 757 * additional room because we steal the segment header 758 * from the other aspath 759 */ 760 size += 2; 761 seg = aspath->data; 762 for (len = aspath->len; len > 0 && cnt > 0; 763 len -= seg_size, seg += seg_size) { 764 seg_type = seg[0]; 765 seg_len = seg[1]; 766 seg_size = 2 + sizeof(u_int32_t) * seg_len; 767 768 if (seg_type == AS_SET) 769 cnt -= 1; 770 else if (seg_len > cnt) { 771 seg_len = cnt + headcnt; 772 seg_size = 2 + sizeof(u_int32_t) * cnt; 773 cnt = 0; 774 } else { 775 cnt -= seg_len; 776 if (cnt == 0) 777 seg_len += headcnt; 778 } 779 780 memcpy(buf, seg, seg_size); 781 buf[0] = seg_type; 782 buf[1] = seg_len; 783 buf += seg_size; 784 if (size < seg_size) 785 fatalx("aspath_countlength: would overflow"); 786 size -= seg_size; 787 } 788 } 789 790 u_int32_t 791 aspath_neighbor(struct aspath *aspath) 792 { 793 /* Empty aspath is OK -- internal AS route. */ 794 if (aspath->len == 0) 795 return (rde_local_as()); 796 return (aspath_extract(aspath->data, 0)); 797 } 798 799 int 800 aspath_loopfree(struct aspath *aspath, u_int32_t myAS) 801 { 802 u_int8_t *seg; 803 u_int16_t len, seg_size; 804 u_int8_t i, seg_len; 805 806 seg = aspath->data; 807 for (len = aspath->len; len > 0; len -= seg_size, seg += seg_size) { 808 seg_len = seg[1]; 809 seg_size = 2 + sizeof(u_int32_t) * seg_len; 810 811 for (i = 0; i < seg_len; i++) { 812 if (myAS == aspath_extract(seg, i)) 813 return (0); 814 } 815 816 if (seg_size > len) 817 fatalx("aspath_loopfree: would overflow"); 818 } 819 return (1); 820 } 821 822 int 823 aspath_compare(struct aspath *a1, struct aspath *a2) 824 { 825 int r; 826 827 if (a1->len > a2->len) 828 return (1); 829 if (a1->len < a2->len) 830 return (-1); 831 r = memcmp(a1->data, a2->data, a1->len); 832 if (r > 0) 833 return (1); 834 if (r < 0) 835 return (-1); 836 return (0); 837 } 838 839 struct aspath * 840 aspath_lookup(const void *data, u_int16_t len) 841 { 842 struct aspath_list *head; 843 struct aspath *aspath; 844 u_int32_t hash; 845 846 hash = SipHash24(&astablekey, data, len); 847 head = ASPATH_HASH(hash); 848 849 LIST_FOREACH(aspath, head, entry) { 850 if (len == aspath->len && memcmp(data, aspath->data, len) == 0) 851 return (aspath); 852 } 853 return (NULL); 854 } 855 856 857 /* 858 * Returns a new prepended aspath. Old needs to be freed by caller. 859 */ 860 u_char * 861 aspath_prepend(struct aspath *asp, u_int32_t as, int quantum, u_int16_t *len) 862 { 863 u_char *p; 864 int l, overflow = 0, shift = 0, size, wpos = 0; 865 u_int8_t type; 866 867 /* lunatic prepends are blocked in the parser and limited */ 868 869 /* first calculate new size */ 870 if (asp->len > 0) { 871 if (asp->len < 2) 872 fatalx("aspath_prepend: bad aspath length"); 873 type = asp->data[0]; 874 size = asp->data[1]; 875 } else { 876 /* empty as path */ 877 type = AS_SET; 878 size = 0; 879 } 880 881 if (quantum > 255) 882 fatalx("aspath_prepend: preposterous prepend"); 883 if (quantum == 0) { 884 /* no change needed but return a copy */ 885 p = malloc(asp->len); 886 if (p == NULL) 887 fatal("aspath_prepend"); 888 memcpy(p, asp->data, asp->len); 889 *len = asp->len; 890 return (p); 891 } else if (type == AS_SET || size + quantum > 255) { 892 /* need to attach a new AS_SEQUENCE */ 893 l = 2 + quantum * sizeof(u_int32_t) + asp->len; 894 if (type == AS_SET) 895 overflow = quantum; 896 else 897 overflow = size + quantum - 255; 898 } else 899 l = quantum * sizeof(u_int32_t) + asp->len; 900 901 quantum -= overflow; 902 903 p = malloc(l); 904 if (p == NULL) 905 fatal("aspath_prepend"); 906 907 /* first prepends */ 908 as = htonl(as); 909 if (overflow > 0) { 910 p[wpos++] = AS_SEQUENCE; 911 p[wpos++] = overflow; 912 913 for (; overflow > 0; overflow--) { 914 memcpy(p + wpos, &as, sizeof(u_int32_t)); 915 wpos += sizeof(u_int32_t); 916 } 917 } 918 if (quantum > 0) { 919 shift = 2; 920 p[wpos++] = AS_SEQUENCE; 921 p[wpos++] = quantum + size; 922 923 for (; quantum > 0; quantum--) { 924 memcpy(p + wpos, &as, sizeof(u_int32_t)); 925 wpos += sizeof(u_int32_t); 926 } 927 } 928 memcpy(p + wpos, asp->data + shift, asp->len - shift); 929 930 *len = l; 931 return (p); 932 } 933 934 int 935 aspath_lenmatch(struct aspath *a, enum aslen_spec type, u_int aslen) 936 { 937 u_int8_t *seg; 938 u_int32_t as, lastas = 0; 939 u_int count = 0; 940 u_int16_t len, seg_size; 941 u_int8_t i, seg_len; 942 943 if (type == ASLEN_MAX) { 944 if (aslen < aspath_count(a->data, a->len)) 945 return (1); 946 else 947 return (0); 948 } 949 950 /* type == ASLEN_SEQ */ 951 seg = a->data; 952 for (len = a->len; len > 0; len -= seg_size, seg += seg_size) { 953 seg_len = seg[1]; 954 seg_size = 2 + sizeof(u_int32_t) * seg_len; 955 956 for (i = 0; i < seg_len; i++) { 957 /* what should we do with AS_SET? */ 958 as = aspath_extract(seg, i); 959 if (as == lastas) { 960 if (aslen < ++count) 961 return (1); 962 } else 963 count = 1; 964 lastas = as; 965 } 966 } 967 return (0); 968 } 969 970 /* 971 * Functions handling communities and extended communities. 972 */ 973 974 int community_ext_matchone(struct filter_extcommunity *, u_int16_t, u_int64_t); 975 976 int 977 community_match(struct rde_aspath *asp, int as, int type) 978 { 979 struct attr *a; 980 u_int8_t *p; 981 u_int16_t eas, etype, len; 982 983 a = attr_optget(asp, ATTR_COMMUNITIES); 984 if (a == NULL) 985 /* no communities, no match */ 986 return (0); 987 988 p = a->data; 989 for (len = a->len / 4; len > 0; len--) { 990 eas = *p++; 991 eas <<= 8; 992 eas |= *p++; 993 etype = *p++; 994 etype <<= 8; 995 etype |= *p++; 996 if ((as == COMMUNITY_ANY || (u_int16_t)as == eas) && 997 (type == COMMUNITY_ANY || (u_int16_t)type == etype)) 998 return (1); 999 } 1000 return (0); 1001 } 1002 1003 int 1004 community_set(struct rde_aspath *asp, int as, int type) 1005 { 1006 struct attr *attr; 1007 u_int8_t *p = NULL; 1008 unsigned int i, ncommunities = 0; 1009 u_int8_t f = ATTR_OPTIONAL|ATTR_TRANSITIVE; 1010 1011 attr = attr_optget(asp, ATTR_COMMUNITIES); 1012 if (attr != NULL) { 1013 p = attr->data; 1014 ncommunities = attr->len / 4; 1015 } 1016 1017 /* first check if the community is not already set */ 1018 for (i = 0; i < ncommunities; i++) { 1019 if (as >> 8 == p[0] && (as & 0xff) == p[1] && 1020 type >> 8 == p[2] && (type & 0xff) == p[3]) 1021 /* already present, nothing todo */ 1022 return (1); 1023 p += 4; 1024 } 1025 1026 if (ncommunities++ >= USHRT_MAX / 4) 1027 /* overflow */ 1028 return (0); 1029 1030 if ((p = reallocarray(NULL, ncommunities, 4)) == NULL) 1031 fatal("community_set"); 1032 1033 p[0] = as >> 8; 1034 p[1] = as & 0xff; 1035 p[2] = type >> 8; 1036 p[3] = type & 0xff; 1037 1038 if (attr != NULL) { 1039 memcpy(p + 4, attr->data, attr->len); 1040 f = attr->flags; 1041 attr_free(asp, attr); 1042 } 1043 1044 attr_optadd(asp, f, ATTR_COMMUNITIES, p, ncommunities * 4); 1045 1046 free(p); 1047 return (1); 1048 } 1049 1050 void 1051 community_delete(struct rde_aspath *asp, int as, int type) 1052 { 1053 struct attr *attr; 1054 u_int8_t *p, *n; 1055 u_int16_t l, len = 0; 1056 u_int16_t eas, etype; 1057 u_int8_t f; 1058 1059 attr = attr_optget(asp, ATTR_COMMUNITIES); 1060 if (attr == NULL) 1061 /* no attr nothing to do */ 1062 return; 1063 1064 p = attr->data; 1065 for (l = 0; l < attr->len; l += 4) { 1066 eas = *p++; 1067 eas <<= 8; 1068 eas |= *p++; 1069 etype = *p++; 1070 etype <<= 8; 1071 etype |= *p++; 1072 1073 if ((as == COMMUNITY_ANY || (u_int16_t)as == eas) && 1074 (type == COMMUNITY_ANY || (u_int16_t)type == etype)) 1075 /* match */ 1076 continue; 1077 len += 4; 1078 } 1079 1080 if (len == 0) { 1081 attr_free(asp, attr); 1082 return; 1083 } 1084 1085 if ((n = malloc(len)) == NULL) 1086 fatal("community_delete"); 1087 1088 p = attr->data; 1089 for (l = 0; l < len && p < attr->data + attr->len; ) { 1090 eas = *p++; 1091 eas <<= 8; 1092 eas |= *p++; 1093 etype = *p++; 1094 etype <<= 8; 1095 etype |= *p++; 1096 1097 if ((as == COMMUNITY_ANY || (u_int16_t)as == eas) && 1098 (type == COMMUNITY_ANY || (u_int16_t)type == etype)) 1099 /* match */ 1100 continue; 1101 n[l++] = eas >> 8; 1102 n[l++] = eas & 0xff; 1103 n[l++] = etype >> 8; 1104 n[l++] = etype & 0xff; 1105 } 1106 1107 f = attr->flags; 1108 1109 attr_free(asp, attr); 1110 attr_optadd(asp, f, ATTR_COMMUNITIES, n, len); 1111 free(n); 1112 } 1113 1114 int 1115 community_ext_match(struct rde_aspath *asp, struct filter_extcommunity *c, 1116 u_int16_t neighas) 1117 { 1118 struct attr *attr; 1119 u_int8_t *p; 1120 u_int64_t ec; 1121 u_int16_t len; 1122 1123 attr = attr_optget(asp, ATTR_EXT_COMMUNITIES); 1124 if (attr == NULL) 1125 /* no communities, no match */ 1126 return (0); 1127 1128 p = attr->data; 1129 for (len = attr->len / sizeof(ec); len > 0; len--) { 1130 memcpy(&ec, p, sizeof(ec)); 1131 if (community_ext_matchone(c, neighas, ec)) 1132 return (1); 1133 p += sizeof(ec); 1134 } 1135 1136 return (0); 1137 } 1138 1139 int 1140 community_ext_set(struct rde_aspath *asp, struct filter_extcommunity *c, 1141 u_int16_t neighas) 1142 { 1143 struct attr *attr; 1144 u_int8_t *p = NULL; 1145 u_int64_t community; 1146 unsigned int i, ncommunities = 0; 1147 u_int8_t f = ATTR_OPTIONAL|ATTR_TRANSITIVE; 1148 1149 if (community_ext_conv(c, neighas, &community)) 1150 return (0); 1151 1152 attr = attr_optget(asp, ATTR_EXT_COMMUNITIES); 1153 if (attr != NULL) { 1154 p = attr->data; 1155 ncommunities = attr->len / sizeof(community); 1156 } 1157 1158 /* first check if the community is not already set */ 1159 for (i = 0; i < ncommunities; i++) { 1160 if (memcmp(&community, p, sizeof(community)) == 0) 1161 /* already present, nothing todo */ 1162 return (1); 1163 p += sizeof(community); 1164 } 1165 1166 if (ncommunities++ >= USHRT_MAX / sizeof(community)) 1167 /* overflow */ 1168 return (0); 1169 1170 if ((p = reallocarray(NULL, ncommunities, sizeof(community))) == NULL) 1171 fatal("community_ext_set"); 1172 1173 memcpy(p, &community, sizeof(community)); 1174 if (attr != NULL) { 1175 memcpy(p + sizeof(community), attr->data, attr->len); 1176 f = attr->flags; 1177 attr_free(asp, attr); 1178 } 1179 1180 attr_optadd(asp, f, ATTR_EXT_COMMUNITIES, p, 1181 ncommunities * sizeof(community)); 1182 1183 free(p); 1184 return (1); 1185 } 1186 1187 void 1188 community_ext_delete(struct rde_aspath *asp, struct filter_extcommunity *c, 1189 u_int16_t neighas) 1190 { 1191 struct attr *attr; 1192 u_int8_t *p, *n; 1193 u_int64_t community; 1194 u_int16_t l, len = 0; 1195 u_int8_t f; 1196 1197 if (community_ext_conv(c, neighas, &community)) 1198 return; 1199 1200 attr = attr_optget(asp, ATTR_EXT_COMMUNITIES); 1201 if (attr == NULL) 1202 /* no attr nothing to do */ 1203 return; 1204 1205 p = attr->data; 1206 for (l = 0; l < attr->len; l += sizeof(community)) { 1207 if (memcmp(&community, p + l, sizeof(community)) == 0) 1208 /* match */ 1209 continue; 1210 len += sizeof(community); 1211 } 1212 1213 if (len == 0) { 1214 attr_free(asp, attr); 1215 return; 1216 } 1217 1218 if ((n = malloc(len)) == NULL) 1219 fatal("community_delete"); 1220 1221 p = attr->data; 1222 for (l = 0; l < len && p < attr->data + attr->len; 1223 p += sizeof(community)) { 1224 if (memcmp(&community, p, sizeof(community)) == 0) 1225 /* match */ 1226 continue; 1227 memcpy(n + l, p, sizeof(community)); 1228 l += sizeof(community); 1229 } 1230 1231 f = attr->flags; 1232 1233 attr_free(asp, attr); 1234 attr_optadd(asp, f, ATTR_EXT_COMMUNITIES, n, len); 1235 free(n); 1236 } 1237 1238 int 1239 community_ext_conv(struct filter_extcommunity *c, u_int16_t neighas, 1240 u_int64_t *community) 1241 { 1242 u_int64_t com; 1243 u_int32_t ip; 1244 1245 com = (u_int64_t)c->type << 56; 1246 switch (c->type & EXT_COMMUNITY_VALUE) { 1247 case EXT_COMMUNITY_TWO_AS: 1248 com |= (u_int64_t)c->subtype << 48; 1249 com |= (u_int64_t)c->data.ext_as.as << 32; 1250 com |= c->data.ext_as.val; 1251 break; 1252 case EXT_COMMUNITY_IPV4: 1253 com |= (u_int64_t)c->subtype << 48; 1254 ip = ntohl(c->data.ext_ip.addr.s_addr); 1255 com |= (u_int64_t)ip << 16; 1256 com |= c->data.ext_ip.val; 1257 break; 1258 case EXT_COMMUNITY_FOUR_AS: 1259 com |= (u_int64_t)c->subtype << 48; 1260 com |= (u_int64_t)c->data.ext_as4.as4 << 16; 1261 com |= c->data.ext_as4.val; 1262 break; 1263 case EXT_COMMUNITY_OPAQUE: 1264 com |= (u_int64_t)c->subtype << 48; 1265 com |= c->data.ext_opaq & EXT_COMMUNITY_OPAQUE_MAX; 1266 break; 1267 default: 1268 com |= c->data.ext_opaq & 0xffffffffffffffULL; 1269 break; 1270 } 1271 1272 *community = htobe64(com); 1273 1274 return (0); 1275 } 1276 1277 int 1278 community_ext_matchone(struct filter_extcommunity *c, u_int16_t neighas, 1279 u_int64_t community) 1280 { 1281 u_int64_t com, mask; 1282 u_int32_t ip; 1283 1284 community = betoh64(community); 1285 1286 com = (u_int64_t)c->type << 56; 1287 mask = 0xffULL << 56; 1288 if ((com & mask) != (community & mask)) 1289 return (0); 1290 1291 switch (c->type & EXT_COMMUNITY_VALUE) { 1292 case EXT_COMMUNITY_TWO_AS: 1293 case EXT_COMMUNITY_IPV4: 1294 case EXT_COMMUNITY_FOUR_AS: 1295 case EXT_COMMUNITY_OPAQUE: 1296 com = (u_int64_t)c->subtype << 48; 1297 mask = 0xffULL << 48; 1298 if ((com & mask) != (community & mask)) 1299 return (0); 1300 break; 1301 default: 1302 com = c->data.ext_opaq & 0xffffffffffffffULL; 1303 mask = 0xffffffffffffffULL; 1304 if ((com & mask) == (community & mask)) 1305 return (1); 1306 return (0); 1307 } 1308 1309 1310 switch (c->type & EXT_COMMUNITY_VALUE) { 1311 case EXT_COMMUNITY_TWO_AS: 1312 com = (u_int64_t)c->data.ext_as.as << 32; 1313 mask = 0xffffULL << 32; 1314 if ((com & mask) != (community & mask)) 1315 return (0); 1316 1317 com = c->data.ext_as.val; 1318 mask = 0xffffffffULL; 1319 if ((com & mask) == (community & mask)) 1320 return (1); 1321 break; 1322 case EXT_COMMUNITY_IPV4: 1323 ip = ntohl(c->data.ext_ip.addr.s_addr); 1324 com = (u_int64_t)ip << 16; 1325 mask = 0xffffffff0000ULL; 1326 if ((com & mask) != (community & mask)) 1327 return (0); 1328 1329 com = c->data.ext_ip.val; 1330 mask = 0xffff; 1331 if ((com & mask) == (community & mask)) 1332 return (1); 1333 break; 1334 case EXT_COMMUNITY_FOUR_AS: 1335 com = (u_int64_t)c->data.ext_as4.as4 << 16; 1336 mask = 0xffffffffULL << 16; 1337 if ((com & mask) != (community & mask)) 1338 return (0); 1339 1340 com = c->data.ext_as4.val; 1341 mask = 0xffff; 1342 if ((com & mask) == (community & mask)) 1343 return (1); 1344 break; 1345 case EXT_COMMUNITY_OPAQUE: 1346 com = c->data.ext_opaq & EXT_COMMUNITY_OPAQUE_MAX; 1347 mask = EXT_COMMUNITY_OPAQUE_MAX; 1348 if ((com & mask) == (community & mask)) 1349 return (1); 1350 break; 1351 } 1352 1353 return (0); 1354 } 1355