1/* AS path management routines. 2 Copyright (C) 1996, 97, 98, 99 Kunihiro Ishiguro 3 Copyright (C) 2005 Sun Microsystems, Inc. 4 5This file is part of GNU Zebra. 6 7GNU Zebra is free software; you can redistribute it and/or modify it 8under the terms of the GNU General Public License as published by the 9Free Software Foundation; either version 2, or (at your option) any 10later version. 11 12GNU Zebra is distributed in the hope that it will be useful, but 13WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GNU Zebra; see the file COPYING. If not, write to the Free 19Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 2002111-1307, USA. */ 21 22#include <zebra.h> 23 24#include "hash.h" 25#include "memory.h" 26#include "vector.h" 27#include "vty.h" 28#include "str.h" 29#include "log.h" 30#include "stream.h" 31#include "jhash.h" 32 33#include "bgpd/bgpd.h" 34#include "bgpd/bgp_aspath.h" 35#include "bgpd/bgp_debug.h" 36#include "bgpd/bgp_attr.h" 37 38/* Attr. Flags and Attr. Type Code. */ 39#define AS_HEADER_SIZE 2 40 41/* Now FOUR octets are used for AS value. */ 42#define AS_VALUE_SIZE sizeof (as_t) 43/* This is the old one */ 44#define AS16_VALUE_SIZE sizeof (as16_t) 45 46/* Maximum protocol segment length value */ 47#define AS_SEGMENT_MAX 255 48 49/* The following length and size macros relate specifically to Quagga's 50 * internal representation of AS-Segments, not per se to the on-wire 51 * sizes and lengths. At present (200508) they sort of match, however 52 * the ONLY functions which should now about the on-wire syntax are 53 * aspath_put, assegment_put and assegment_parse. 54 * 55 * aspath_put returns bytes written, the only definitive record of 56 * size of wire-format attribute.. 57 */ 58 59/* Calculated size in bytes of ASN segment data to hold N ASN's */ 60#define ASSEGMENT_DATA_SIZE(N,S) \ 61 ((N) * ( (S) ? AS_VALUE_SIZE : AS16_VALUE_SIZE) ) 62 63/* Calculated size of segment struct to hold N ASN's */ 64#define ASSEGMENT_SIZE(N,S) (AS_HEADER_SIZE + ASSEGMENT_DATA_SIZE (N,S)) 65 66/* AS segment octet length. */ 67#define ASSEGMENT_LEN(X,S) ASSEGMENT_SIZE((X)->length,S) 68 69/* AS_SEQUENCE segments can be packed together */ 70/* Can the types of X and Y be considered for packing? */ 71#define ASSEGMENT_TYPES_PACKABLE(X,Y) \ 72 ( ((X)->type == (Y)->type) \ 73 && ((X)->type == AS_SEQUENCE)) 74/* Types and length of X,Y suitable for packing? */ 75#define ASSEGMENTS_PACKABLE(X,Y) \ 76 ( ASSEGMENT_TYPES_PACKABLE( (X), (Y)) \ 77 && ( ((X)->length + (Y)->length) <= AS_SEGMENT_MAX ) ) 78 79/* As segment header - the on-wire representation 80 * NOT the internal representation! 81 */ 82struct assegment_header 83{ 84 u_char type; 85 u_char length; 86}; 87 88/* Hash for aspath. This is the top level structure of AS path. */ 89static struct hash *ashash; 90 91/* Stream for SNMP. See aspath_snmp_pathseg */ 92static struct stream *snmp_stream; 93 94/* Callers are required to initialize the memory */ 95static as_t * 96assegment_data_new (int num) 97{ 98 return (XMALLOC (MTYPE_AS_SEG_DATA, ASSEGMENT_DATA_SIZE (num, 1))); 99} 100 101/* Get a new segment. Note that 0 is an allowed length, 102 * and will result in a segment with no allocated data segment. 103 * the caller should immediately assign data to the segment, as the segment 104 * otherwise is not generally valid 105 */ 106static struct assegment * 107assegment_new (u_char type, u_short length) 108{ 109 struct assegment *new; 110 111 new = XCALLOC (MTYPE_AS_SEG, sizeof (struct assegment)); 112 113 if (length) 114 new->as = assegment_data_new (length); 115 116 new->length = length; 117 new->type = type; 118 119 return new; 120} 121 122static void 123assegment_free (struct assegment *seg) 124{ 125 if (!seg) 126 return; 127 128 if (seg->as) 129 XFREE (MTYPE_AS_SEG_DATA, seg->as); 130 memset (seg, 0xfe, sizeof(struct assegment)); 131 XFREE (MTYPE_AS_SEG, seg); 132 133 return; 134} 135 136/* free entire chain of segments */ 137static void 138assegment_free_all (struct assegment *seg) 139{ 140 struct assegment *prev; 141 142 while (seg) 143 { 144 prev = seg; 145 seg = seg->next; 146 assegment_free (prev); 147 } 148} 149 150/* Duplicate just the given assegment and its data */ 151static struct assegment * 152assegment_dup (struct assegment *seg) 153{ 154 struct assegment *new; 155 156 new = assegment_new (seg->type, seg->length); 157 memcpy (new->as, seg->as, ASSEGMENT_DATA_SIZE (new->length, 1) ); 158 159 return new; 160} 161 162/* Duplicate entire chain of assegments, return the head */ 163static struct assegment * 164assegment_dup_all (struct assegment *seg) 165{ 166 struct assegment *new = NULL; 167 struct assegment *head = NULL; 168 169 while (seg) 170 { 171 if (head) 172 { 173 new->next = assegment_dup (seg); 174 new = new->next; 175 } 176 else 177 head = new = assegment_dup (seg); 178 179 seg = seg->next; 180 } 181 return head; 182} 183 184/* prepend the as number to given segment, given num of times */ 185static struct assegment * 186assegment_prepend_asns (struct assegment *seg, as_t asnum, int num) 187{ 188 as_t *newas; 189 int i; 190 191 if (!num) 192 return seg; 193 194 if (num >= AS_SEGMENT_MAX) 195 return seg; /* we don't do huge prepends */ 196 197 newas = assegment_data_new (seg->length + num); 198 199 for (i = 0; i < num; i++) 200 newas[i] = asnum; 201 202 memcpy (newas + num, seg->as, ASSEGMENT_DATA_SIZE (seg->length, 1)); 203 XFREE (MTYPE_AS_SEG_DATA, seg->as); 204 seg->as = newas; 205 seg->length += num; 206 207 return seg; 208} 209 210/* append given array of as numbers to the segment */ 211static struct assegment * 212assegment_append_asns (struct assegment *seg, as_t *asnos, int num) 213{ 214 as_t *newas; 215 216 newas = XREALLOC (MTYPE_AS_SEG_DATA, seg->as, 217 ASSEGMENT_DATA_SIZE (seg->length + num, 1)); 218 219 if (newas) 220 { 221 seg->as = newas; 222 memcpy (seg->as + seg->length, asnos, ASSEGMENT_DATA_SIZE(num, 1)); 223 seg->length += num; 224 return seg; 225 } 226 227 assegment_free_all (seg); 228 return NULL; 229} 230 231static int 232int_cmp (const void *p1, const void *p2) 233{ 234 const as_t *as1 = p1; 235 const as_t *as2 = p2; 236 237 return (*as1 == *as2) 238 ? 0 : ( (*as1 > *as2) ? 1 : -1); 239} 240 241/* normalise the segment. 242 * In particular, merge runs of AS_SEQUENCEs into one segment 243 * Internally, we do not care about the wire segment length limit, and 244 * we want each distinct AS_PATHs to have the exact same internal 245 * representation - eg, so that our hashing actually works.. 246 */ 247static struct assegment * 248assegment_normalise (struct assegment *head) 249{ 250 struct assegment *seg = head, *pin; 251 struct assegment *tmp; 252 253 if (!head) 254 return head; 255 256 while (seg) 257 { 258 pin = seg; 259 260 /* Sort values SET segments, for determinism in paths to aid 261 * creation of hash values / path comparisons 262 * and because it helps other lesser implementations ;) 263 */ 264 if (seg->type == AS_SET || seg->type == AS_CONFED_SET) 265 { 266 int tail = 0; 267 int i; 268 269 qsort (seg->as, seg->length, sizeof(as_t), int_cmp); 270 271 /* weed out dupes */ 272 for (i=1; i < seg->length; i++) 273 { 274 if (seg->as[tail] == seg->as[i]) 275 continue; 276 277 tail++; 278 if (tail < i) 279 seg->as[tail] = seg->as[i]; 280 } 281 /* seg->length can be 0.. */ 282 if (seg->length) 283 seg->length = tail + 1; 284 } 285 286 /* read ahead from the current, pinned segment while the segments 287 * are packable/mergeable. Append all following packable segments 288 * to the segment we have pinned and remove these appended 289 * segments. 290 */ 291 while (pin->next && ASSEGMENT_TYPES_PACKABLE(pin, pin->next)) 292 { 293 tmp = pin->next; 294 seg = pin->next; 295 296 /* append the next sequence to the pinned sequence */ 297 pin = assegment_append_asns (pin, seg->as, seg->length); 298 299 /* bypass the next sequence */ 300 pin->next = seg->next; 301 302 /* get rid of the now referenceless segment */ 303 assegment_free (tmp); 304 305 } 306 307 seg = pin->next; 308 } 309 return head; 310} 311 312static struct aspath * 313aspath_new (void) 314{ 315 return XCALLOC (MTYPE_AS_PATH, sizeof (struct aspath)); 316} 317 318/* Free AS path structure. */ 319void 320aspath_free (struct aspath *aspath) 321{ 322 if (!aspath) 323 return; 324 if (aspath->segments) 325 assegment_free_all (aspath->segments); 326 if (aspath->str) 327 XFREE (MTYPE_AS_STR, aspath->str); 328 XFREE (MTYPE_AS_PATH, aspath); 329} 330 331/* Unintern aspath from AS path bucket. */ 332void 333aspath_unintern (struct aspath **aspath) 334{ 335 struct aspath *ret; 336 struct aspath *asp = *aspath; 337 338 if (asp->refcnt) 339 asp->refcnt--; 340 341 if (asp->refcnt == 0) 342 { 343 /* This aspath must exist in aspath hash table. */ 344 ret = hash_release (ashash, asp); 345 assert (ret != NULL); 346 aspath_free (asp); 347 *aspath = NULL; 348 } 349} 350 351/* Return the start or end delimiters for a particular Segment type */ 352#define AS_SEG_START 0 353#define AS_SEG_END 1 354static char 355aspath_delimiter_char (u_char type, u_char which) 356{ 357 int i; 358 struct 359 { 360 int type; 361 char start; 362 char end; 363 } aspath_delim_char [] = 364 { 365 { AS_SET, '{', '}' }, 366 { AS_CONFED_SET, '[', ']' }, 367 { AS_CONFED_SEQUENCE, '(', ')' }, 368 { 0 } 369 }; 370 371 for (i = 0; aspath_delim_char[i].type != 0; i++) 372 { 373 if (aspath_delim_char[i].type == type) 374 { 375 if (which == AS_SEG_START) 376 return aspath_delim_char[i].start; 377 else if (which == AS_SEG_END) 378 return aspath_delim_char[i].end; 379 } 380 } 381 return ' '; 382} 383 384/* countup asns from this segment and index onward */ 385static int 386assegment_count_asns (struct assegment *seg, int from) 387{ 388 int count = 0; 389 while (seg) 390 { 391 if (!from) 392 count += seg->length; 393 else 394 { 395 count += (seg->length - from); 396 from = 0; 397 } 398 seg = seg->next; 399 } 400 return count; 401} 402 403unsigned int 404aspath_count_confeds (struct aspath *aspath) 405{ 406 int count = 0; 407 struct assegment *seg = aspath->segments; 408 409 while (seg) 410 { 411 if (seg->type == AS_CONFED_SEQUENCE) 412 count += seg->length; 413 else if (seg->type == AS_CONFED_SET) 414 count++; 415 416 seg = seg->next; 417 } 418 return count; 419} 420 421unsigned int 422aspath_count_hops (struct aspath *aspath) 423{ 424 int count = 0; 425 struct assegment *seg = aspath->segments; 426 427 while (seg) 428 { 429 if (seg->type == AS_SEQUENCE) 430 count += seg->length; 431 else if (seg->type == AS_SET) 432 count++; 433 434 seg = seg->next; 435 } 436 return count; 437} 438 439/* Estimate size aspath /might/ take if encoded into an 440 * ASPATH attribute. 441 * 442 * This is a quick estimate, not definitive! aspath_put() 443 * may return a different number!! 444 */ 445unsigned int 446aspath_size (struct aspath *aspath) 447{ 448 int size = 0; 449 struct assegment *seg = aspath->segments; 450 451 while (seg) 452 { 453 size += ASSEGMENT_SIZE(seg->length, 1); 454 seg = seg->next; 455 } 456 return size; 457} 458 459/* Return highest public ASN in path */ 460as_t 461aspath_highest (struct aspath *aspath) 462{ 463 struct assegment *seg = aspath->segments; 464 as_t highest = 0; 465 unsigned int i; 466 467 while (seg) 468 { 469 for (i = 0; i < seg->length; i++) 470 if (seg->as[i] > highest 471 && (seg->as[i] < BGP_PRIVATE_AS_MIN 472 || seg->as[i] > BGP_PRIVATE_AS_MAX)) 473 highest = seg->as[i]; 474 seg = seg->next; 475 } 476 return highest; 477} 478 479/* Return the left-most ASN in path */ 480as_t 481aspath_leftmost (struct aspath *aspath) 482{ 483 struct assegment *seg = aspath->segments; 484 as_t leftmost = 0; 485 486 if (seg && seg->length && seg->type == AS_SEQUENCE) 487 leftmost = seg->as[0]; 488 489 return leftmost; 490} 491 492/* Return 1 if there are any 4-byte ASes in the path */ 493unsigned int 494aspath_has_as4 (struct aspath *aspath) 495{ 496 struct assegment *seg = aspath->segments; 497 unsigned int i; 498 499 while (seg) 500 { 501 for (i = 0; i < seg->length; i++) 502 if (seg->as[i] > BGP_AS_MAX) 503 return 1; 504 seg = seg->next; 505 } 506 return 0; 507} 508 509/* Convert aspath structure to string expression. */ 510static void 511aspath_make_str_count (struct aspath *as) 512{ 513 struct assegment *seg; 514 int str_size; 515 int len = 0; 516 char *str_buf; 517 518 /* Empty aspath. */ 519 if (!as->segments) 520 { 521 as->str = XMALLOC (MTYPE_AS_STR, 1); 522 as->str[0] = '\0'; 523 as->str_len = 0; 524 return; 525 } 526 527 seg = as->segments; 528 529 /* ASN takes 5 to 10 chars plus seperator, see below. 530 * If there is one differing segment type, we need an additional 531 * 2 chars for segment delimiters, and the final '\0'. 532 * Hopefully this is large enough to avoid hitting the realloc 533 * code below for most common sequences. 534 * 535 * This was changed to 10 after the well-known BGP assertion, which 536 * had hit some parts of the Internet in May of 2009. 537 */ 538#define ASN_STR_LEN (10 + 1) 539 str_size = MAX (assegment_count_asns (seg, 0) * ASN_STR_LEN + 2 + 1, 540 ASPATH_STR_DEFAULT_LEN); 541 str_buf = XMALLOC (MTYPE_AS_STR, str_size); 542 543 while (seg) 544 { 545 int i; 546 char seperator; 547 548 /* Check AS type validity. Set seperator for segment */ 549 switch (seg->type) 550 { 551 case AS_SET: 552 case AS_CONFED_SET: 553 seperator = ','; 554 break; 555 case AS_SEQUENCE: 556 case AS_CONFED_SEQUENCE: 557 seperator = ' '; 558 break; 559 default: 560 XFREE (MTYPE_AS_STR, str_buf); 561 as->str = NULL; 562 as->str_len = 0; 563 return; 564 } 565 566 /* We might need to increase str_buf, particularly if path has 567 * differing segments types, our initial guesstimate above will 568 * have been wrong. Need 10 chars for ASN, a seperator each and 569 * potentially two segment delimiters, plus a space between each 570 * segment and trailing zero. 571 * 572 * This definitely didn't work with the value of 5 bytes and 573 * 32-bit ASNs. 574 */ 575#define SEGMENT_STR_LEN(X) (((X)->length * ASN_STR_LEN) + 2 + 1 + 1) 576 if ( (len + SEGMENT_STR_LEN(seg)) > str_size) 577 { 578 str_size = len + SEGMENT_STR_LEN(seg); 579 str_buf = XREALLOC (MTYPE_AS_STR, str_buf, str_size); 580 } 581#undef ASN_STR_LEN 582#undef SEGMENT_STR_LEN 583 584 if (seg->type != AS_SEQUENCE) 585 len += snprintf (str_buf + len, str_size - len, 586 "%c", 587 aspath_delimiter_char (seg->type, AS_SEG_START)); 588 589 /* write out the ASNs, with their seperators, bar the last one*/ 590 for (i = 0; i < seg->length; i++) 591 { 592 len += snprintf (str_buf + len, str_size - len, "%u", seg->as[i]); 593 594 if (i < (seg->length - 1)) 595 len += snprintf (str_buf + len, str_size - len, "%c", seperator); 596 } 597 598 if (seg->type != AS_SEQUENCE) 599 len += snprintf (str_buf + len, str_size - len, "%c", 600 aspath_delimiter_char (seg->type, AS_SEG_END)); 601 if (seg->next) 602 len += snprintf (str_buf + len, str_size - len, " "); 603 604 seg = seg->next; 605 } 606 607 assert (len < str_size); 608 609 str_buf[len] = '\0'; 610 as->str = str_buf; 611 as->str_len = len; 612 613 return; 614} 615 616static void 617aspath_str_update (struct aspath *as) 618{ 619 if (as->str) 620 XFREE (MTYPE_AS_STR, as->str); 621 aspath_make_str_count (as); 622} 623 624/* Intern allocated AS path. */ 625struct aspath * 626aspath_intern (struct aspath *aspath) 627{ 628 struct aspath *find; 629 630 /* Assert this AS path structure is not interned and has the string 631 representation built. */ 632 assert (aspath->refcnt == 0); 633 assert (aspath->str); 634 635 /* Check AS path hash. */ 636 find = hash_get (ashash, aspath, hash_alloc_intern); 637 if (find != aspath) 638 aspath_free (aspath); 639 640 find->refcnt++; 641 642 return find; 643} 644 645/* Duplicate aspath structure. Created same aspath structure but 646 reference count and AS path string is cleared. */ 647struct aspath * 648aspath_dup (struct aspath *aspath) 649{ 650 unsigned short buflen = aspath->str_len + 1; 651 struct aspath *new; 652 653 new = XCALLOC (MTYPE_AS_PATH, sizeof (struct aspath)); 654 655 if (aspath->segments) 656 new->segments = assegment_dup_all (aspath->segments); 657 658 if (!aspath->str) 659 return new; 660 661 new->str = XMALLOC (MTYPE_AS_STR, buflen); 662 new->str_len = aspath->str_len; 663 664 /* copy the string data */ 665 if (aspath->str_len > 0) 666 memcpy (new->str, aspath->str, buflen); 667 else 668 new->str[0] = '\0'; 669 670 return new; 671} 672 673static void * 674aspath_hash_alloc (void *arg) 675{ 676 const struct aspath *aspath = arg; 677 struct aspath *new; 678 679 /* Malformed AS path value. */ 680 assert (aspath->str); 681 if (! aspath->str) 682 return NULL; 683 684 /* New aspath structure is needed. */ 685 new = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath)); 686 687 /* Reuse segments and string representation */ 688 new->refcnt = 0; 689 new->segments = aspath->segments; 690 new->str = aspath->str; 691 new->str_len = aspath->str_len; 692 693 return new; 694} 695 696/* parse as-segment byte stream in struct assegment */ 697static int 698assegments_parse (struct stream *s, size_t length, 699 struct assegment **result, int use32bit) 700{ 701 struct assegment_header segh; 702 struct assegment *seg, *prev = NULL, *head = NULL; 703 size_t bytes = 0; 704 705 /* empty aspath (ie iBGP or somesuch) */ 706 if (length == 0) 707 return 0; 708 709 if (BGP_DEBUG (as4, AS4_SEGMENT)) 710 zlog_debug ("[AS4SEG] Parse aspath segment: got total byte length %lu", 711 (unsigned long) length); 712 /* basic checks */ 713 if ((STREAM_READABLE(s) < length) 714 || (STREAM_READABLE(s) < AS_HEADER_SIZE) 715 || (length % AS16_VALUE_SIZE )) 716 return -1; 717 718 while (bytes < length) 719 { 720 int i; 721 size_t seg_size; 722 723 if ((length - bytes) <= AS_HEADER_SIZE) 724 { 725 if (head) 726 assegment_free_all (head); 727 return -1; 728 } 729 730 /* softly softly, get the header first on its own */ 731 segh.type = stream_getc (s); 732 segh.length = stream_getc (s); 733 734 seg_size = ASSEGMENT_SIZE(segh.length, use32bit); 735 736 if (BGP_DEBUG (as4, AS4_SEGMENT)) 737 zlog_debug ("[AS4SEG] Parse aspath segment: got type %d, length %d", 738 segh.type, segh.length); 739 740 /* check it.. */ 741 if ( ((bytes + seg_size) > length) 742 /* 1771bis 4.3b: seg length contains one or more */ 743 || (segh.length == 0) 744 /* Paranoia in case someone changes type of segment length. 745 * Shift both values by 0x10 to make the comparison operate 746 * on more, than 8 bits (otherwise it's a warning, bug #564). 747 */ 748 || ((sizeof segh.length > 1) 749 && (0x10 + segh.length > 0x10 + AS_SEGMENT_MAX))) 750 { 751 if (head) 752 assegment_free_all (head); 753 return -1; 754 } 755 756 switch (segh.type) 757 { 758 case AS_SEQUENCE: 759 case AS_SET: 760 case AS_CONFED_SEQUENCE: 761 case AS_CONFED_SET: 762 break; 763 default: 764 if (head) 765 assegment_free_all (head); 766 return -1; 767 } 768 769 /* now its safe to trust lengths */ 770 seg = assegment_new (segh.type, segh.length); 771 772 if (head) 773 prev->next = seg; 774 else /* it's the first segment */ 775 head = prev = seg; 776 777 for (i = 0; i < segh.length; i++) 778 seg->as[i] = (use32bit) ? stream_getl (s) : stream_getw (s); 779 780 bytes += seg_size; 781 782 if (BGP_DEBUG (as4, AS4_SEGMENT)) 783 zlog_debug ("[AS4SEG] Parse aspath segment: Bytes now: %lu", 784 (unsigned long) bytes); 785 786 prev = seg; 787 } 788 789 *result = assegment_normalise (head); 790 return 0; 791} 792 793/* AS path parse function. pnt is a pointer to byte stream and length 794 is length of byte stream. If there is same AS path in the the AS 795 path hash then return it else make new AS path structure. 796 797 On error NULL is returned. 798 */ 799struct aspath * 800aspath_parse (struct stream *s, size_t length, int use32bit) 801{ 802 struct aspath as; 803 struct aspath *find; 804 805 /* If length is odd it's malformed AS path. */ 806 /* Nit-picking: if (use32bit == 0) it is malformed if odd, 807 * otherwise its malformed when length is larger than 2 and (length-2) 808 * is not dividable by 4. 809 * But... this time we're lazy 810 */ 811 if (length % AS16_VALUE_SIZE ) 812 return NULL; 813 814 memset (&as, 0, sizeof (struct aspath)); 815 if (assegments_parse (s, length, &as.segments, use32bit) < 0) 816 return NULL; 817 818 /* If already same aspath exist then return it. */ 819 find = hash_get (ashash, &as, aspath_hash_alloc); 820 821 /* bug! should not happen, let the daemon crash below */ 822 assert (find); 823 824 /* if the aspath was already hashed free temporary memory. */ 825 if (find->refcnt) 826 { 827 assegment_free_all (as.segments); 828 /* aspath_key_make() always updates the string */ 829 XFREE (MTYPE_AS_STR, as.str); 830 } 831 832 find->refcnt++; 833 834 return find; 835} 836 837static void 838assegment_data_put (struct stream *s, as_t *as, int num, int use32bit) 839{ 840 int i; 841 assert (num <= AS_SEGMENT_MAX); 842 843 for (i = 0; i < num; i++) 844 if ( use32bit ) 845 stream_putl (s, as[i]); 846 else 847 { 848 if ( as[i] <= BGP_AS_MAX ) 849 stream_putw(s, as[i]); 850 else 851 stream_putw(s, BGP_AS_TRANS); 852 } 853} 854 855static size_t 856assegment_header_put (struct stream *s, u_char type, int length) 857{ 858 size_t lenp; 859 assert (length <= AS_SEGMENT_MAX); 860 stream_putc (s, type); 861 lenp = stream_get_endp (s); 862 stream_putc (s, length); 863 return lenp; 864} 865 866/* write aspath data to stream */ 867size_t 868aspath_put (struct stream *s, struct aspath *as, int use32bit ) 869{ 870 struct assegment *seg = as->segments; 871 size_t bytes = 0; 872 873 if (!seg || seg->length == 0) 874 return 0; 875 876 if (seg) 877 { 878 /* 879 * Hey, what do we do when we have > STREAM_WRITABLE(s) here? 880 * At the moment, we would write out a partial aspath, and our peer 881 * will complain and drop the session :-/ 882 * 883 * The general assumption here is that many things tested will 884 * never happen. And, in real live, up to now, they have not. 885 */ 886 while (seg && (ASSEGMENT_LEN(seg, use32bit) <= STREAM_WRITEABLE(s))) 887 { 888 struct assegment *next = seg->next; 889 int written = 0; 890 int asns_packed = 0; 891 size_t lenp; 892 893 /* Overlength segments have to be split up */ 894 while ( (seg->length - written) > AS_SEGMENT_MAX) 895 { 896 assegment_header_put (s, seg->type, AS_SEGMENT_MAX); 897 assegment_data_put (s, seg->as, AS_SEGMENT_MAX, use32bit); 898 written += AS_SEGMENT_MAX; 899 bytes += ASSEGMENT_SIZE (written, use32bit); 900 } 901 902 /* write the final segment, probably is also the first */ 903 lenp = assegment_header_put (s, seg->type, seg->length - written); 904 assegment_data_put (s, (seg->as + written), seg->length - written, 905 use32bit); 906 907 /* Sequence-type segments can be 'packed' together 908 * Case of a segment which was overlength and split up 909 * will be missed here, but that doesn't matter. 910 */ 911 while (next && ASSEGMENTS_PACKABLE (seg, next)) 912 { 913 /* NB: We should never normally get here given we 914 * normalise aspath data when parse them. However, better 915 * safe than sorry. We potentially could call 916 * assegment_normalise here instead, but it's cheaper and 917 * easier to do it on the fly here rather than go through 918 * the segment list twice every time we write out 919 * aspath's. 920 */ 921 922 /* Next segment's data can fit in this one */ 923 assegment_data_put (s, next->as, next->length, use32bit); 924 925 /* update the length of the segment header */ 926 stream_putc_at (s, lenp, seg->length - written + next->length); 927 asns_packed += next->length; 928 929 next = next->next; 930 } 931 932 bytes += ASSEGMENT_SIZE (seg->length - written + asns_packed, 933 use32bit); 934 seg = next; 935 } 936 } 937 return bytes; 938} 939 940/* This is for SNMP BGP4PATHATTRASPATHSEGMENT 941 * We have no way to manage the storage, so we use a static stream 942 * wrapper around aspath_put. 943 */ 944u_char * 945aspath_snmp_pathseg (struct aspath *as, size_t *varlen) 946{ 947#define SNMP_PATHSEG_MAX 1024 948 949 if (!snmp_stream) 950 snmp_stream = stream_new (SNMP_PATHSEG_MAX); 951 else 952 stream_reset (snmp_stream); 953 954 if (!as) 955 { 956 *varlen = 0; 957 return NULL; 958 } 959 aspath_put (snmp_stream, as, 0); /* use 16 bit for now here */ 960 961 *varlen = stream_get_endp (snmp_stream); 962 return stream_pnt(snmp_stream); 963} 964 965#define min(A,B) ((A) < (B) ? (A) : (B)) 966 967static struct assegment * 968aspath_aggregate_as_set_add (struct aspath *aspath, struct assegment *asset, 969 as_t as) 970{ 971 int i; 972 973 /* If this is first AS set member, create new as-set segment. */ 974 if (asset == NULL) 975 { 976 asset = assegment_new (AS_SET, 1); 977 if (! aspath->segments) 978 aspath->segments = asset; 979 else 980 { 981 struct assegment *seg = aspath->segments; 982 while (seg->next) 983 seg = seg->next; 984 seg->next = asset; 985 } 986 asset->type = AS_SET; 987 asset->length = 1; 988 asset->as[0] = as; 989 } 990 else 991 { 992 /* Check this AS value already exists or not. */ 993 for (i = 0; i < asset->length; i++) 994 if (asset->as[i] == as) 995 return asset; 996 997 asset->length++; 998 asset->as = XREALLOC (MTYPE_AS_SEG_DATA, asset->as, 999 asset->length * AS_VALUE_SIZE); 1000 asset->as[asset->length - 1] = as; 1001 } 1002 1003 1004 return asset; 1005} 1006 1007/* Modify as1 using as2 for aggregation. */ 1008struct aspath * 1009aspath_aggregate (struct aspath *as1, struct aspath *as2) 1010{ 1011 int i; 1012 int minlen; 1013 int match; 1014 int from; 1015 struct assegment *seg1 = as1->segments; 1016 struct assegment *seg2 = as2->segments; 1017 struct aspath *aspath = NULL; 1018 struct assegment *asset; 1019 struct assegment *prevseg = NULL; 1020 1021 match = 0; 1022 minlen = 0; 1023 aspath = NULL; 1024 asset = NULL; 1025 1026 /* First of all check common leading sequence. */ 1027 while (seg1 && seg2) 1028 { 1029 /* Check segment type. */ 1030 if (seg1->type != seg2->type) 1031 break; 1032 1033 /* Minimum segment length. */ 1034 minlen = min (seg1->length, seg2->length); 1035 1036 for (match = 0; match < minlen; match++) 1037 if (seg1->as[match] != seg2->as[match]) 1038 break; 1039 1040 if (match) 1041 { 1042 struct assegment *seg = assegment_new (seg1->type, 0); 1043 1044 seg = assegment_append_asns (seg, seg1->as, match); 1045 1046 if (! aspath) 1047 { 1048 aspath = aspath_new (); 1049 aspath->segments = seg; 1050 } 1051 else 1052 prevseg->next = seg; 1053 1054 prevseg = seg; 1055 } 1056 1057 if (match != minlen || match != seg1->length 1058 || seg1->length != seg2->length) 1059 break; 1060 1061 seg1 = seg1->next; 1062 seg2 = seg2->next; 1063 } 1064 1065 if (! aspath) 1066 aspath = aspath_new(); 1067 1068 /* Make as-set using rest of all information. */ 1069 from = match; 1070 while (seg1) 1071 { 1072 for (i = from; i < seg1->length; i++) 1073 asset = aspath_aggregate_as_set_add (aspath, asset, seg1->as[i]); 1074 1075 from = 0; 1076 seg1 = seg1->next; 1077 } 1078 1079 from = match; 1080 while (seg2) 1081 { 1082 for (i = from; i < seg2->length; i++) 1083 asset = aspath_aggregate_as_set_add (aspath, asset, seg2->as[i]); 1084 1085 from = 0; 1086 seg2 = seg2->next; 1087 } 1088 1089 assegment_normalise (aspath->segments); 1090 aspath_str_update (aspath); 1091 return aspath; 1092} 1093 1094/* When a BGP router receives an UPDATE with an MP_REACH_NLRI 1095 attribute, check the leftmost AS number in the AS_PATH attribute is 1096 or not the peer's AS number. */ 1097int 1098aspath_firstas_check (struct aspath *aspath, as_t asno) 1099{ 1100 if ( (aspath == NULL) || (aspath->segments == NULL) ) 1101 return 0; 1102 1103 if (aspath->segments 1104 && (aspath->segments->type == AS_SEQUENCE) 1105 && (aspath->segments->as[0] == asno )) 1106 return 1; 1107 1108 return 0; 1109} 1110 1111/* AS path loop check. If aspath contains asno then return >= 1. */ 1112int 1113aspath_loop_check (struct aspath *aspath, as_t asno) 1114{ 1115 struct assegment *seg; 1116 int count = 0; 1117 1118 if ( (aspath == NULL) || (aspath->segments == NULL) ) 1119 return 0; 1120 1121 seg = aspath->segments; 1122 1123 while (seg) 1124 { 1125 int i; 1126 1127 for (i = 0; i < seg->length; i++) 1128 if (seg->as[i] == asno) 1129 count++; 1130 1131 seg = seg->next; 1132 } 1133 return count; 1134} 1135 1136/* When all of AS path is private AS return 1. */ 1137int 1138aspath_private_as_check (struct aspath *aspath) 1139{ 1140 struct assegment *seg; 1141 1142 if ( !(aspath && aspath->segments) ) 1143 return 0; 1144 1145 seg = aspath->segments; 1146 1147 while (seg) 1148 { 1149 int i; 1150 1151 for (i = 0; i < seg->length; i++) 1152 { 1153 if ( (seg->as[i] < BGP_PRIVATE_AS_MIN) 1154 || (seg->as[i] > BGP_PRIVATE_AS_MAX) ) 1155 return 0; 1156 } 1157 seg = seg->next; 1158 } 1159 return 1; 1160} 1161 1162/* AS path confed check. If aspath contains confed set or sequence then return 1. */ 1163int 1164aspath_confed_check (struct aspath *aspath) 1165{ 1166 struct assegment *seg; 1167 1168 if ( !(aspath && aspath->segments) ) 1169 return 0; 1170 1171 seg = aspath->segments; 1172 1173 while (seg) 1174 { 1175 if (seg->type == AS_CONFED_SET || seg->type == AS_CONFED_SEQUENCE) 1176 return 1; 1177 seg = seg->next; 1178 } 1179 return 0; 1180} 1181 1182/* Leftmost AS path segment confed check. If leftmost AS segment is of type 1183 AS_CONFED_SEQUENCE or AS_CONFED_SET then return 1. */ 1184int 1185aspath_left_confed_check (struct aspath *aspath) 1186{ 1187 1188 if ( !(aspath && aspath->segments) ) 1189 return 0; 1190 1191 if ( (aspath->segments->type == AS_CONFED_SEQUENCE) 1192 || (aspath->segments->type == AS_CONFED_SET) ) 1193 return 1; 1194 1195 return 0; 1196} 1197 1198/* Merge as1 to as2. as2 should be uninterned aspath. */ 1199static struct aspath * 1200aspath_merge (struct aspath *as1, struct aspath *as2) 1201{ 1202 struct assegment *last, *new; 1203 1204 if (! as1 || ! as2) 1205 return NULL; 1206 1207 last = new = assegment_dup_all (as1->segments); 1208 1209 /* find the last valid segment */ 1210 while (last && last->next) 1211 last = last->next; 1212 1213 last->next = as2->segments; 1214 as2->segments = new; 1215 aspath_str_update (as2); 1216 return as2; 1217} 1218 1219/* Prepend as1 to as2. as2 should be uninterned aspath. */ 1220struct aspath * 1221aspath_prepend (struct aspath *as1, struct aspath *as2) 1222{ 1223 struct assegment *seg1; 1224 struct assegment *seg2; 1225 1226 if (! as1 || ! as2) 1227 return NULL; 1228 1229 seg1 = as1->segments; 1230 seg2 = as2->segments; 1231 1232 /* If as2 is empty, only need to dupe as1's chain onto as2 */ 1233 if (seg2 == NULL) 1234 { 1235 as2->segments = assegment_dup_all (as1->segments); 1236 aspath_str_update (as2); 1237 return as2; 1238 } 1239 1240 /* If as1 is empty AS, no prepending to do. */ 1241 if (seg1 == NULL) 1242 return as2; 1243 1244 /* find the tail as1's segment chain. */ 1245 while (seg1 && seg1->next) 1246 seg1 = seg1->next; 1247 1248 /* Delete any AS_CONFED_SEQUENCE segment from as2. */ 1249 if (seg1->type == AS_SEQUENCE && seg2->type == AS_CONFED_SEQUENCE) 1250 as2 = aspath_delete_confed_seq (as2); 1251 1252 /* Compare last segment type of as1 and first segment type of as2. */ 1253 if (seg1->type != seg2->type) 1254 return aspath_merge (as1, as2); 1255 1256 if (seg1->type == AS_SEQUENCE) 1257 { 1258 /* We have two chains of segments, as1->segments and seg2, 1259 * and we have to attach them together, merging the attaching 1260 * segments together into one. 1261 * 1262 * 1. dupe as1->segments onto head of as2 1263 * 2. merge seg2's asns onto last segment of this new chain 1264 * 3. attach chain after seg2 1265 */ 1266 1267 /* dupe as1 onto as2's head */ 1268 seg1 = as2->segments = assegment_dup_all (as1->segments); 1269 1270 /* refind the tail of as2, reusing seg1 */ 1271 while (seg1 && seg1->next) 1272 seg1 = seg1->next; 1273 1274 /* merge the old head, seg2, into tail, seg1 */ 1275 seg1 = assegment_append_asns (seg1, seg2->as, seg2->length); 1276 1277 /* bypass the merged seg2, and attach any chain after it to 1278 * chain descending from as2's head 1279 */ 1280 seg1->next = seg2->next; 1281 1282 /* seg2 is now referenceless and useless*/ 1283 assegment_free (seg2); 1284 1285 /* we've now prepended as1's segment chain to as2, merging 1286 * the inbetween AS_SEQUENCE of seg2 in the process 1287 */ 1288 aspath_str_update (as2); 1289 return as2; 1290 } 1291 else 1292 { 1293 /* AS_SET merge code is needed at here. */ 1294 return aspath_merge (as1, as2); 1295 } 1296 /* XXX: Ermmm, what if as1 has multiple segments?? */ 1297 1298 /* Not reached */ 1299} 1300 1301/* Iterate over AS_PATH segments and wipe all occurences of the 1302 * listed AS numbers. Hence some segments may lose some or even 1303 * all data on the way, the operation is implemented as a smarter 1304 * version of aspath_dup(), which allocates memory to hold the new 1305 * data, not the original. The new AS path is returned. 1306 */ 1307struct aspath * 1308aspath_filter_exclude (struct aspath * source, struct aspath * exclude_list) 1309{ 1310 struct assegment * srcseg, * exclseg, * lastseg; 1311 struct aspath * newpath; 1312 1313 newpath = aspath_new(); 1314 lastseg = NULL; 1315 1316 for (srcseg = source->segments; srcseg; srcseg = srcseg->next) 1317 { 1318 unsigned i, y, newlen = 0, done = 0, skip_as; 1319 struct assegment * newseg; 1320 1321 /* Find out, how much ASns are we going to pick from this segment. 1322 * We can't perform filtering right inline, because the size of 1323 * the new segment isn't known at the moment yet. 1324 */ 1325 for (i = 0; i < srcseg->length; i++) 1326 { 1327 skip_as = 0; 1328 for (exclseg = exclude_list->segments; exclseg && !skip_as; exclseg = exclseg->next) 1329 for (y = 0; y < exclseg->length; y++) 1330 if (srcseg->as[i] == exclseg->as[y]) 1331 { 1332 skip_as = 1; 1333 // There's no sense in testing the rest of exclusion list, bail out. 1334 break; 1335 } 1336 if (!skip_as) 1337 newlen++; 1338 } 1339 /* newlen is now the number of ASns to copy */ 1340 if (!newlen) 1341 continue; 1342 1343 /* Actual copying. Allocate memory and iterate once more, performing filtering. */ 1344 newseg = assegment_new (srcseg->type, newlen); 1345 for (i = 0; i < srcseg->length; i++) 1346 { 1347 skip_as = 0; 1348 for (exclseg = exclude_list->segments; exclseg && !skip_as; exclseg = exclseg->next) 1349 for (y = 0; y < exclseg->length; y++) 1350 if (srcseg->as[i] == exclseg->as[y]) 1351 { 1352 skip_as = 1; 1353 break; 1354 } 1355 if (skip_as) 1356 continue; 1357 newseg->as[done++] = srcseg->as[i]; 1358 } 1359 /* At his point newlen must be equal to done, and both must be positive. Append 1360 * the filtered segment to the gross result. */ 1361 if (!lastseg) 1362 newpath->segments = newseg; 1363 else 1364 lastseg->next = newseg; 1365 lastseg = newseg; 1366 } 1367 aspath_str_update (newpath); 1368 /* We are happy returning even an empty AS_PATH, because the administrator 1369 * might expect this very behaviour. There's a mean to avoid this, if necessary, 1370 * by having a match rule against certain AS_PATH regexps in the route-map index. 1371 */ 1372 aspath_free (source); 1373 return newpath; 1374} 1375 1376/* Add specified AS to the leftmost of aspath. */ 1377static struct aspath * 1378aspath_add_asns (struct aspath *aspath, as_t asno, u_char type, unsigned num) 1379{ 1380 struct assegment *assegment = aspath->segments; 1381 int i; 1382 1383 if (assegment && assegment->type == type) 1384 { 1385 /* extend existing segment */ 1386 aspath->segments = assegment_prepend_asns (aspath->segments, asno, num); 1387 } 1388 else 1389 { 1390 /* prepend with new segment */ 1391 struct assegment *newsegment = assegment_new (type, num); 1392 for (i = 0; i < num; i++) 1393 newsegment->as[i] = asno; 1394 1395 /* insert potentially replacing empty segment */ 1396 if (assegment && assegment->length == 0) 1397 { 1398 newsegment->next = assegment->next; 1399 assegment_free (assegment); 1400 } 1401 else 1402 newsegment->next = assegment; 1403 aspath->segments = newsegment; 1404 } 1405 1406 aspath_str_update (aspath); 1407 return aspath; 1408} 1409 1410/* Add specified AS to the leftmost of aspath num times. */ 1411struct aspath * 1412aspath_add_seq_n (struct aspath *aspath, as_t asno, unsigned num) 1413{ 1414 return aspath_add_asns (aspath, asno, AS_SEQUENCE, num); 1415} 1416 1417/* Add specified AS to the leftmost of aspath. */ 1418struct aspath * 1419aspath_add_seq (struct aspath *aspath, as_t asno) 1420{ 1421 return aspath_add_asns (aspath, asno, AS_SEQUENCE, 1); 1422} 1423 1424/* Compare leftmost AS value for MED check. If as1's leftmost AS and 1425 as2's leftmost AS is same return 1. */ 1426int 1427aspath_cmp_left (const struct aspath *aspath1, const struct aspath *aspath2) 1428{ 1429 const struct assegment *seg1; 1430 const struct assegment *seg2; 1431 1432 if (!(aspath1 && aspath2)) 1433 return 0; 1434 1435 seg1 = aspath1->segments; 1436 seg2 = aspath2->segments; 1437 1438 /* find first non-confed segments for each */ 1439 while (seg1 && ((seg1->type == AS_CONFED_SEQUENCE) 1440 || (seg1->type == AS_CONFED_SET))) 1441 seg1 = seg1->next; 1442 1443 while (seg2 && ((seg2->type == AS_CONFED_SEQUENCE) 1444 || (seg2->type == AS_CONFED_SET))) 1445 seg2 = seg2->next; 1446 1447 /* Check as1's */ 1448 if (!(seg1 && seg2 1449 && (seg1->type == AS_SEQUENCE) && (seg2->type == AS_SEQUENCE))) 1450 return 0; 1451 1452 if (seg1->as[0] == seg2->as[0]) 1453 return 1; 1454 1455 return 0; 1456} 1457 1458/* Truncate an aspath after a number of hops, and put the hops remaining 1459 * at the front of another aspath. Needed for AS4 compat. 1460 * 1461 * Returned aspath is a /new/ aspath, which should either by free'd or 1462 * interned by the caller, as desired. 1463 */ 1464struct aspath * 1465aspath_reconcile_as4 ( struct aspath *aspath, struct aspath *as4path) 1466{ 1467 struct assegment *seg, *newseg, *prevseg = NULL; 1468 struct aspath *newpath = NULL, *mergedpath; 1469 int hops, cpasns = 0; 1470 1471 if (!aspath) 1472 return NULL; 1473 1474 seg = aspath->segments; 1475 1476 /* CONFEDs should get reconciled too.. */ 1477 hops = (aspath_count_hops (aspath) + aspath_count_confeds (aspath)) 1478 - aspath_count_hops (as4path); 1479 1480 if (hops < 0) 1481 { 1482 if (BGP_DEBUG (as4, AS4)) 1483 zlog_warn ("[AS4] Fewer hops in AS_PATH than NEW_AS_PATH"); 1484 /* Something's gone wrong. The RFC says we should now ignore AS4_PATH, 1485 * which is daft behaviour - it contains vital loop-detection 1486 * information which must have been removed from AS_PATH. 1487 */ 1488 hops = aspath_count_hops (aspath); 1489 } 1490 1491 if (!hops) 1492 return aspath_dup (as4path); 1493 1494 if ( BGP_DEBUG(as4, AS4)) 1495 zlog_debug("[AS4] got AS_PATH %s and AS4_PATH %s synthesizing now", 1496 aspath->str, as4path->str); 1497 1498 while (seg && hops > 0) 1499 { 1500 switch (seg->type) 1501 { 1502 case AS_SET: 1503 case AS_CONFED_SET: 1504 hops--; 1505 cpasns = seg->length; 1506 break; 1507 case AS_CONFED_SEQUENCE: 1508 /* Should never split a confed-sequence, if hop-count 1509 * suggests we must then something's gone wrong somewhere. 1510 * 1511 * Most important goal is to preserve AS_PATHs prime function 1512 * as loop-detector, so we fudge the numbers so that the entire 1513 * confed-sequence is merged in. 1514 */ 1515 if (hops < seg->length) 1516 { 1517 if (BGP_DEBUG (as4, AS4)) 1518 zlog_debug ("[AS4] AS4PATHmangle: AS_CONFED_SEQUENCE falls" 1519 " across 2/4 ASN boundary somewhere, broken.."); 1520 hops = seg->length; 1521 } 1522 case AS_SEQUENCE: 1523 cpasns = MIN(seg->length, hops); 1524 hops -= seg->length; 1525 } 1526 1527 assert (cpasns <= seg->length); 1528 1529 newseg = assegment_new (seg->type, 0); 1530 newseg = assegment_append_asns (newseg, seg->as, cpasns); 1531 1532 if (!newpath) 1533 { 1534 newpath = aspath_new (); 1535 newpath->segments = newseg; 1536 } 1537 else 1538 prevseg->next = newseg; 1539 1540 prevseg = newseg; 1541 seg = seg->next; 1542 } 1543 1544 /* We may be able to join some segments here, and we must 1545 * do this because... we want normalised aspaths in out hash 1546 * and we do not want to stumble in aspath_put. 1547 */ 1548 mergedpath = aspath_merge (newpath, aspath_dup(as4path)); 1549 aspath_free (newpath); 1550 mergedpath->segments = assegment_normalise (mergedpath->segments); 1551 aspath_str_update (mergedpath); 1552 1553 if ( BGP_DEBUG(as4, AS4)) 1554 zlog_debug ("[AS4] result of synthesizing is %s", 1555 mergedpath->str); 1556 1557 return mergedpath; 1558} 1559 1560/* Compare leftmost AS value for MED check. If as1's leftmost AS and 1561 as2's leftmost AS is same return 1. (confederation as-path 1562 only). */ 1563int 1564aspath_cmp_left_confed (const struct aspath *aspath1, const struct aspath *aspath2) 1565{ 1566 if (! (aspath1 && aspath2) ) 1567 return 0; 1568 1569 if ( !(aspath1->segments && aspath2->segments) ) 1570 return 0; 1571 1572 if ( (aspath1->segments->type != AS_CONFED_SEQUENCE) 1573 || (aspath2->segments->type != AS_CONFED_SEQUENCE) ) 1574 return 0; 1575 1576 if (aspath1->segments->as[0] == aspath2->segments->as[0]) 1577 return 1; 1578 1579 return 0; 1580} 1581 1582/* Delete all leading AS_CONFED_SEQUENCE/SET segments from aspath. 1583 * See RFC3065, 6.1 c1 */ 1584struct aspath * 1585aspath_delete_confed_seq (struct aspath *aspath) 1586{ 1587 struct assegment *seg; 1588 1589 if (!(aspath && aspath->segments)) 1590 return aspath; 1591 1592 seg = aspath->segments; 1593 1594 /* "if the first path segment of the AS_PATH is 1595 * of type AS_CONFED_SEQUENCE," 1596 */ 1597 if (aspath->segments->type != AS_CONFED_SEQUENCE) 1598 return aspath; 1599 1600 /* "... that segment and any immediately following segments 1601 * of the type AS_CONFED_SET or AS_CONFED_SEQUENCE are removed 1602 * from the AS_PATH attribute," 1603 */ 1604 while (seg && 1605 (seg->type == AS_CONFED_SEQUENCE || seg->type == AS_CONFED_SET)) 1606 { 1607 aspath->segments = seg->next; 1608 assegment_free (seg); 1609 seg = aspath->segments; 1610 } 1611 aspath_str_update (aspath); 1612 return aspath; 1613} 1614 1615/* Add new AS number to the leftmost part of the aspath as 1616 AS_CONFED_SEQUENCE. */ 1617struct aspath* 1618aspath_add_confed_seq (struct aspath *aspath, as_t asno) 1619{ 1620 return aspath_add_asns (aspath, asno, AS_CONFED_SEQUENCE, 1); 1621} 1622 1623/* Add new as value to as path structure. */ 1624static void 1625aspath_as_add (struct aspath *as, as_t asno) 1626{ 1627 struct assegment *seg = as->segments; 1628 1629 if (!seg) 1630 return; 1631 1632 /* Last segment search procedure. */ 1633 while (seg->next) 1634 seg = seg->next; 1635 1636 assegment_append_asns (seg, &asno, 1); 1637} 1638 1639/* Add new as segment to the as path. */ 1640static void 1641aspath_segment_add (struct aspath *as, int type) 1642{ 1643 struct assegment *seg = as->segments; 1644 struct assegment *new = assegment_new (type, 0); 1645 1646 if (seg) 1647 { 1648 while (seg->next) 1649 seg = seg->next; 1650 seg->next = new; 1651 } 1652 else 1653 as->segments = new; 1654} 1655 1656struct aspath * 1657aspath_empty (void) 1658{ 1659 return aspath_parse (NULL, 0, 1); /* 32Bit ;-) */ 1660} 1661 1662struct aspath * 1663aspath_empty_get (void) 1664{ 1665 struct aspath *aspath; 1666 1667 aspath = aspath_new (); 1668 aspath_make_str_count (aspath); 1669 return aspath; 1670} 1671 1672unsigned long 1673aspath_count (void) 1674{ 1675 return ashash->count; 1676} 1677 1678/* 1679 Theoretically, one as path can have: 1680 1681 One BGP packet size should be less than 4096. 1682 One BGP attribute size should be less than 4096 - BGP header size. 1683 One BGP aspath size should be less than 4096 - BGP header size - 1684 BGP mandantry attribute size. 1685*/ 1686 1687/* AS path string lexical token enum. */ 1688enum as_token 1689{ 1690 as_token_asval, 1691 as_token_set_start, 1692 as_token_set_end, 1693 as_token_confed_seq_start, 1694 as_token_confed_seq_end, 1695 as_token_confed_set_start, 1696 as_token_confed_set_end, 1697 as_token_unknown 1698}; 1699 1700/* Return next token and point for string parse. */ 1701static const char * 1702aspath_gettoken (const char *buf, enum as_token *token, u_long *asno) 1703{ 1704 const char *p = buf; 1705 1706 /* Skip seperators (space for sequences, ',' for sets). */ 1707 while (isspace ((int) *p) || *p == ',') 1708 p++; 1709 1710 /* Check the end of the string and type specify characters 1711 (e.g. {}()). */ 1712 switch (*p) 1713 { 1714 case '\0': 1715 return NULL; 1716 case '{': 1717 *token = as_token_set_start; 1718 p++; 1719 return p; 1720 case '}': 1721 *token = as_token_set_end; 1722 p++; 1723 return p; 1724 case '(': 1725 *token = as_token_confed_seq_start; 1726 p++; 1727 return p; 1728 case ')': 1729 *token = as_token_confed_seq_end; 1730 p++; 1731 return p; 1732 case '[': 1733 *token = as_token_confed_set_start; 1734 p++; 1735 return p; 1736 case ']': 1737 *token = as_token_confed_set_end; 1738 p++; 1739 return p; 1740 } 1741 1742 /* Check actual AS value. */ 1743 if (isdigit ((int) *p)) 1744 { 1745 as_t asval; 1746 1747 *token = as_token_asval; 1748 asval = (*p - '0'); 1749 p++; 1750 1751 while (isdigit ((int) *p)) 1752 { 1753 asval *= 10; 1754 asval += (*p - '0'); 1755 p++; 1756 } 1757 *asno = asval; 1758 return p; 1759 } 1760 1761 /* There is no match then return unknown token. */ 1762 *token = as_token_unknown; 1763 return p++; 1764} 1765 1766struct aspath * 1767aspath_str2aspath (const char *str) 1768{ 1769 enum as_token token = as_token_unknown; 1770 u_short as_type; 1771 u_long asno = 0; 1772 struct aspath *aspath; 1773 int needtype; 1774 1775 aspath = aspath_new (); 1776 1777 /* We start default type as AS_SEQUENCE. */ 1778 as_type = AS_SEQUENCE; 1779 needtype = 1; 1780 1781 while ((str = aspath_gettoken (str, &token, &asno)) != NULL) 1782 { 1783 switch (token) 1784 { 1785 case as_token_asval: 1786 if (needtype) 1787 { 1788 aspath_segment_add (aspath, as_type); 1789 needtype = 0; 1790 } 1791 aspath_as_add (aspath, asno); 1792 break; 1793 case as_token_set_start: 1794 as_type = AS_SET; 1795 aspath_segment_add (aspath, as_type); 1796 needtype = 0; 1797 break; 1798 case as_token_set_end: 1799 as_type = AS_SEQUENCE; 1800 needtype = 1; 1801 break; 1802 case as_token_confed_seq_start: 1803 as_type = AS_CONFED_SEQUENCE; 1804 aspath_segment_add (aspath, as_type); 1805 needtype = 0; 1806 break; 1807 case as_token_confed_seq_end: 1808 as_type = AS_SEQUENCE; 1809 needtype = 1; 1810 break; 1811 case as_token_confed_set_start: 1812 as_type = AS_CONFED_SET; 1813 aspath_segment_add (aspath, as_type); 1814 needtype = 0; 1815 break; 1816 case as_token_confed_set_end: 1817 as_type = AS_SEQUENCE; 1818 needtype = 1; 1819 break; 1820 case as_token_unknown: 1821 default: 1822 aspath_free (aspath); 1823 return NULL; 1824 } 1825 } 1826 1827 aspath_make_str_count (aspath); 1828 1829 return aspath; 1830} 1831 1832/* Make hash value by raw aspath data. */ 1833unsigned int 1834aspath_key_make (void *p) 1835{ 1836 struct aspath *aspath = (struct aspath *) p; 1837 unsigned int key = 0; 1838 1839 if (!aspath->str) 1840 aspath_str_update (aspath); 1841 1842 key = jhash (aspath->str, aspath->str_len, 2334325); 1843 1844 return key; 1845} 1846 1847/* If two aspath have same value then return 1 else return 0 */ 1848int 1849aspath_cmp (const void *arg1, const void *arg2) 1850{ 1851 const struct assegment *seg1 = ((const struct aspath *)arg1)->segments; 1852 const struct assegment *seg2 = ((const struct aspath *)arg2)->segments; 1853 1854 while (seg1 || seg2) 1855 { 1856 int i; 1857 if ((!seg1 && seg2) || (seg1 && !seg2)) 1858 return 0; 1859 if (seg1->type != seg2->type) 1860 return 0; 1861 if (seg1->length != seg2->length) 1862 return 0; 1863 for (i = 0; i < seg1->length; i++) 1864 if (seg1->as[i] != seg2->as[i]) 1865 return 0; 1866 seg1 = seg1->next; 1867 seg2 = seg2->next; 1868 } 1869 return 1; 1870} 1871 1872/* AS path hash initialize. */ 1873void 1874aspath_init (void) 1875{ 1876 ashash = hash_create_size (32768, aspath_key_make, aspath_cmp); 1877} 1878 1879void 1880aspath_finish (void) 1881{ 1882 hash_free (ashash); 1883 ashash = NULL; 1884 1885 if (snmp_stream) 1886 stream_free (snmp_stream); 1887} 1888 1889/* return and as path value */ 1890const char * 1891aspath_print (struct aspath *as) 1892{ 1893 return (as ? as->str : NULL); 1894} 1895 1896/* Printing functions */ 1897/* Feed the AS_PATH to the vty; the suffix string follows it only in case 1898 * AS_PATH wasn't empty. 1899 */ 1900void 1901aspath_print_vty (struct vty *vty, const char *format, struct aspath *as, const char * suffix) 1902{ 1903 assert (format); 1904 vty_out (vty, format, as->str); 1905 if (as->str_len && strlen (suffix)) 1906 vty_out (vty, "%s", suffix); 1907} 1908 1909static void 1910aspath_show_all_iterator (struct hash_backet *backet, struct vty *vty) 1911{ 1912 struct aspath *as; 1913 1914 as = (struct aspath *) backet->data; 1915 1916 vty_out (vty, "[%p:%u] (%ld) ", backet, backet->key, as->refcnt); 1917 vty_out (vty, "%s%s", as->str, VTY_NEWLINE); 1918} 1919 1920/* Print all aspath and hash information. This function is used from 1921 `show ip bgp paths' command. */ 1922void 1923aspath_print_all_vty (struct vty *vty) 1924{ 1925 hash_iterate (ashash, 1926 (void (*) (struct hash_backet *, void *)) 1927 aspath_show_all_iterator, 1928 vty); 1929} 1930