1/* AS path management routines. 2 Copyright (C) 1996, 97, 98, 99 Kunihiro Ishiguro 3 4This file is part of GNU Zebra. 5 6GNU Zebra is free software; you can redistribute it and/or modify it 7under the terms of the GNU General Public License as published by the 8Free Software Foundation; either version 2, or (at your option) any 9later version. 10 11GNU Zebra is distributed in the hope that it will be useful, but 12WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GNU Zebra; see the file COPYING. If not, write to the Free 18Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 1902111-1307, USA. */ 20 21#include <zebra.h> 22 23#include "hash.h" 24#include "memory.h" 25#include "vector.h" 26#include "vty.h" 27#include "str.h" 28#include "log.h" 29 30#include "bgpd/bgpd.h" 31#include "bgpd/bgp_aspath.h" 32 33/* Attr. Flags and Attr. Type Code. */ 34#define AS_HEADER_SIZE 2 35 36/* Two octet is used for AS value. */ 37#define AS_VALUE_SIZE sizeof (as_t) 38 39/* AS segment octet length. */ 40#define ASSEGMENT_LEN(X) ((X)->length * AS_VALUE_SIZE + AS_HEADER_SIZE) 41 42/* To fetch and store as segment value. */ 43struct assegment 44{ 45 u_char type; 46 u_char length; 47 as_t asval[1]; 48}; 49 50/* Hash for aspath. This is the top level structure of AS path. */ 51struct hash *ashash; 52 53static struct aspath * 54aspath_new () 55{ 56 struct aspath *aspath; 57 58 aspath = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath)); 59 memset (aspath, 0, sizeof (struct aspath)); 60 return aspath; 61} 62 63/* Free AS path structure. */ 64void 65aspath_free (struct aspath *aspath) 66{ 67 if (!aspath) 68 return; 69 if (aspath->data) 70 XFREE (MTYPE_AS_SEG, aspath->data); 71 if (aspath->str) 72 XFREE (MTYPE_AS_STR, aspath->str); 73 XFREE (MTYPE_AS_PATH, aspath); 74} 75 76/* Unintern aspath from AS path bucket. */ 77void 78aspath_unintern (struct aspath *aspath) 79{ 80 struct aspath *ret; 81 82 if (aspath->refcnt) 83 aspath->refcnt--; 84 85 if (aspath->refcnt == 0) 86 { 87 /* This aspath must exist in aspath hash table. */ 88 ret = hash_release (ashash, aspath); 89 assert (ret != NULL); 90 aspath_free (aspath); 91 } 92} 93 94/* Return the start or end delimiters for a particular Segment type */ 95#define AS_SEG_START 0 96#define AS_SEG_END 1 97static char 98aspath_delimiter_char (u_char type, u_char which) 99{ 100 int i; 101 struct 102 { 103 int type; 104 char start; 105 char end; 106 } aspath_delim_char [] = 107 { 108 { AS_SET, '{', '}' }, 109 { AS_SEQUENCE, ' ', ' ' }, 110 { AS_CONFED_SET, '[', ']' }, 111 { AS_CONFED_SEQUENCE, '(', ')' }, 112 { 0 } 113 }; 114 115 for (i = 0; aspath_delim_char[i].type != 0; i++) 116 { 117 if (aspath_delim_char[i].type == type) 118 { 119 if (which == AS_SEG_START) 120 return aspath_delim_char[i].start; 121 else if (which == AS_SEG_END) 122 return aspath_delim_char[i].end; 123 } 124 } 125 return ' '; 126} 127 128/* Convert aspath structure to string expression. */ 129char * 130aspath_make_str_count (struct aspath *as) 131{ 132 int space; 133 u_char type; 134 caddr_t pnt; 135 caddr_t end; 136 struct assegment *assegment; 137 int str_size = ASPATH_STR_DEFAULT_LEN; 138 int str_pnt; 139 u_char *str_buf; 140 int count = 0; 141 142 /* Empty aspath. */ 143 if (as->length == 0) 144 { 145 str_buf = XMALLOC (MTYPE_AS_STR, 1); 146 str_buf[0] = '\0'; 147 as->count = count; 148 return str_buf; 149 } 150 151 /* Set default value. */ 152 space = 0; 153 type = AS_SEQUENCE; 154 155 /* Set initial pointer. */ 156 pnt = as->data; 157 end = pnt + as->length; 158 159 str_buf = XMALLOC (MTYPE_AS_STR, str_size); 160 str_pnt = 0; 161 162 assegment = (struct assegment *) pnt; 163 164 while (pnt < end) 165 { 166 int i; 167 int estimate_len; 168 169 /* For fetch value. */ 170 assegment = (struct assegment *) pnt; 171 172 /* Check AS type validity. */ 173 if ((assegment->type != AS_SET) && 174 (assegment->type != AS_SEQUENCE) && 175 (assegment->type != AS_CONFED_SET) && 176 (assegment->type != AS_CONFED_SEQUENCE)) 177 { 178 XFREE (MTYPE_AS_STR, str_buf); 179 return NULL; 180 } 181 182 /* Check AS length. */ 183 if ((pnt + (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE) > end) 184 { 185 XFREE (MTYPE_AS_STR, str_buf); 186 return NULL; 187 } 188 189 /* Buffer length check. */ 190 estimate_len = ((assegment->length * 6) + 4); 191 192 /* String length check. */ 193 while (str_pnt + estimate_len >= str_size) 194 { 195 str_size *= 2; 196 str_buf = XREALLOC (MTYPE_AS_STR, str_buf, str_size); 197 } 198 199 /* If assegment type is changed, print previous type's end 200 character. */ 201 if (type != AS_SEQUENCE) 202 str_buf[str_pnt++] = aspath_delimiter_char (type, AS_SEG_END); 203 if (space) 204 str_buf[str_pnt++] = ' '; 205 206 if (assegment->type != AS_SEQUENCE) 207 str_buf[str_pnt++] = aspath_delimiter_char (assegment->type, AS_SEG_START); 208 209 space = 0; 210 211 /* Increment count - ignoring CONFED SETS/SEQUENCES */ 212 if (assegment->type != AS_CONFED_SEQUENCE 213 && assegment->type != AS_CONFED_SET) 214 { 215 if (assegment->type == AS_SEQUENCE) 216 count += assegment->length; 217 else if (assegment->type == AS_SET) 218 count++; 219 } 220 221 for (i = 0; i < assegment->length; i++) 222 { 223 int len; 224 225 if (space) 226 { 227 if (assegment->type == AS_SET 228 || assegment->type == AS_CONFED_SET) 229 str_buf[str_pnt++] = ','; 230 else 231 str_buf[str_pnt++] = ' '; 232 } 233 else 234 space = 1; 235 236 len = sprintf (str_buf + str_pnt, "%d", ntohs (assegment->asval[i])); 237 str_pnt += len; 238 } 239 240 type = assegment->type; 241 pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE; 242 } 243 244 if (assegment->type != AS_SEQUENCE) 245 str_buf[str_pnt++] = aspath_delimiter_char (assegment->type, AS_SEG_END); 246 247 str_buf[str_pnt] = '\0'; 248 249 as->count = count; 250 251 return str_buf; 252} 253 254/* Intern allocated AS path. */ 255struct aspath * 256aspath_intern (struct aspath *aspath) 257{ 258 struct aspath *find; 259 260 /* Assert this AS path structure is not interned. */ 261 assert (aspath->refcnt == 0); 262 263 /* Check AS path hash. */ 264 find = hash_get (ashash, aspath, hash_alloc_intern); 265 266 if (find != aspath) 267 aspath_free (aspath); 268 269 find->refcnt++; 270 271 if (! find->str) 272 find->str = aspath_make_str_count (find); 273 274 return find; 275} 276 277/* Duplicate aspath structure. Created same aspath structure but 278 reference count and AS path string is cleared. */ 279struct aspath * 280aspath_dup (struct aspath *aspath) 281{ 282 struct aspath *new; 283 284 new = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath)); 285 memset (new, 0, sizeof (struct aspath)); 286 287 new->length = aspath->length; 288 289 if (new->length) 290 { 291 new->data = XMALLOC (MTYPE_AS_SEG, aspath->length); 292 memcpy (new->data, aspath->data, aspath->length); 293 } 294 else 295 new->data = NULL; 296 297 /* new->str = aspath_make_str_count (aspath); */ 298 299 return new; 300} 301 302void * 303aspath_hash_alloc (struct aspath *arg) 304{ 305 struct aspath *aspath; 306 307 /* New aspath strucutre is needed. */ 308 aspath = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath)); 309 memset ((void *) aspath, 0, sizeof (struct aspath)); 310 aspath->length = arg->length; 311 312 /* In case of IBGP connection aspath's length can be zero. */ 313 if (arg->length) 314 { 315 aspath->data = XMALLOC (MTYPE_AS_SEG, arg->length); 316 memcpy (aspath->data, arg->data, arg->length); 317 } 318 else 319 aspath->data = NULL; 320 321 /* Make AS path string. */ 322 aspath->str = aspath_make_str_count (aspath); 323 324 /* Malformed AS path value. */ 325 if (! aspath->str) 326 { 327 aspath_free (aspath); 328 return NULL; 329 } 330 331 return aspath; 332} 333 334/* AS path parse function. pnt is a pointer to byte stream and length 335 is length of byte stream. If there is same AS path in the the AS 336 path hash then return it else make new AS path structure. */ 337struct aspath * 338aspath_parse (caddr_t pnt, int length) 339{ 340 struct aspath as; 341 struct aspath *find; 342 343 /* If length is odd it's malformed AS path. */ 344 if (length % 2) 345 return NULL; 346 347 /* Looking up aspath hash entry. */ 348 as.data = pnt; 349 as.length = length; 350 351 /* If already same aspath exist then return it. */ 352 find = hash_get (ashash, &as, aspath_hash_alloc); 353 if (! find) 354 return NULL; 355 find->refcnt++; 356 357 return find; 358} 359 360#define min(A,B) ((A) < (B) ? (A) : (B)) 361 362#define ASSEGMENT_SIZE(N) (AS_HEADER_SIZE + ((N) * AS_VALUE_SIZE)) 363 364struct aspath * 365aspath_aggregate_segment_copy (struct aspath *aspath, struct assegment *seg, 366 int i) 367{ 368 struct assegment *newseg; 369 370 if (! aspath->data) 371 { 372 aspath->data = XMALLOC (MTYPE_AS_SEG, ASSEGMENT_SIZE (i)); 373 newseg = (struct assegment *) aspath->data; 374 aspath->length = ASSEGMENT_SIZE (i); 375 } 376 else 377 { 378 aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data, 379 aspath->length + ASSEGMENT_SIZE (i)); 380 newseg = (struct assegment *) (aspath->data + aspath->length); 381 aspath->length += ASSEGMENT_SIZE (i); 382 } 383 384 newseg->type = seg->type; 385 newseg->length = i; 386 memcpy (newseg->asval, seg->asval, (i * AS_VALUE_SIZE)); 387 388 return aspath; 389} 390 391struct assegment * 392aspath_aggregate_as_set_add (struct aspath *aspath, struct assegment *asset, 393 as_t as) 394{ 395 int i; 396 397 /* If this is first AS set member, create new as-set segment. */ 398 if (asset == NULL) 399 { 400 if (! aspath->data) 401 { 402 aspath->data = XMALLOC (MTYPE_AS_SEG, ASSEGMENT_SIZE (1)); 403 asset = (struct assegment *) aspath->data; 404 aspath->length = ASSEGMENT_SIZE (1); 405 } 406 else 407 { 408 aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data, 409 aspath->length + ASSEGMENT_SIZE (1)); 410 asset = (struct assegment *) (aspath->data + aspath->length); 411 aspath->length += ASSEGMENT_SIZE (1); 412 } 413 asset->type = AS_SET; 414 asset->length = 1; 415 asset->asval[0] = as; 416 } 417 else 418 { 419 size_t offset; 420 421 /* Check this AS value already exists or not. */ 422 for (i = 0; i < asset->length; i++) 423 if (asset->asval[i] == as) 424 return asset; 425 426 offset = (caddr_t) asset - (caddr_t) aspath->data; 427 aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data, 428 aspath->length + AS_VALUE_SIZE); 429 430 asset = (struct assegment *) (aspath->data + offset); 431 aspath->length += AS_VALUE_SIZE; 432 asset->asval[asset->length] = as; 433 asset->length++; 434 } 435 436 return asset; 437} 438 439/* Modify as1 using as2 for aggregation. */ 440struct aspath * 441aspath_aggregate (struct aspath *as1, struct aspath *as2) 442{ 443 int i; 444 int minlen; 445 int match; 446 int match1; 447 int match2; 448 caddr_t cp1; 449 caddr_t cp2; 450 caddr_t end1; 451 caddr_t end2; 452 struct assegment *seg1; 453 struct assegment *seg2; 454 struct aspath *aspath; 455 struct assegment *asset; 456 457 match = 0; 458 minlen = 0; 459 aspath = NULL; 460 asset = NULL; 461 cp1 = as1->data; 462 end1 = as1->data + as1->length; 463 cp2 = as2->data; 464 end2 = as2->data + as2->length; 465 466 seg1 = (struct assegment *) cp1; 467 seg2 = (struct assegment *) cp2; 468 469 /* First of all check common leading sequence. */ 470 while ((cp1 < end1) && (cp2 < end2)) 471 { 472 /* Check segment type. */ 473 if (seg1->type != seg2->type) 474 break; 475 476 /* Minimum segment length. */ 477 minlen = min (seg1->length, seg2->length); 478 479 for (match = 0; match < minlen; match++) 480 if (seg1->asval[match] != seg2->asval[match]) 481 break; 482 483 if (match) 484 { 485 if (! aspath) 486 aspath = aspath_new(); 487 aspath = aspath_aggregate_segment_copy (aspath, seg1, match); 488 } 489 490 if (match != minlen || match != seg1->length 491 || seg1->length != seg2->length) 492 break; 493 494 cp1 += ((seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE); 495 cp2 += ((seg2->length * AS_VALUE_SIZE) + AS_HEADER_SIZE); 496 497 seg1 = (struct assegment *) cp1; 498 seg2 = (struct assegment *) cp2; 499 } 500 501 if (! aspath) 502 aspath = aspath_new(); 503 504 /* Make as-set using rest of all information. */ 505 match1 = match; 506 while (cp1 < end1) 507 { 508 seg1 = (struct assegment *) cp1; 509 510 for (i = match1; i < seg1->length; i++) 511 asset = aspath_aggregate_as_set_add (aspath, asset, seg1->asval[i]); 512 513 match1 = 0; 514 cp1 += ((seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE); 515 } 516 517 match2 = match; 518 while (cp2 < end2) 519 { 520 seg2 = (struct assegment *) cp2; 521 522 for (i = match2; i < seg2->length; i++) 523 asset = aspath_aggregate_as_set_add (aspath, asset, seg2->asval[i]); 524 525 match2 = 0; 526 cp2 += ((seg2->length * AS_VALUE_SIZE) + AS_HEADER_SIZE); 527 } 528 529 return aspath; 530} 531 532/* When a BGP router receives an UPDATE with an MP_REACH_NLRI 533 attribute, check the leftmost AS number in the AS_PATH attribute is 534 or not the peer's AS number. */ 535int 536aspath_firstas_check (struct aspath *aspath, as_t asno) 537{ 538 caddr_t pnt; 539 struct assegment *assegment; 540 541 if (aspath == NULL) 542 return 0; 543 544 pnt = aspath->data; 545 assegment = (struct assegment *) pnt; 546 547 if (assegment 548 && assegment->type == AS_SEQUENCE 549 && assegment->asval[0] == htons (asno)) 550 return 1; 551 552 return 0; 553} 554 555/* AS path loop check. If aspath contains asno then return 1. */ 556int 557aspath_loop_check (struct aspath *aspath, as_t asno) 558{ 559 caddr_t pnt; 560 caddr_t end; 561 struct assegment *assegment; 562 int count = 0; 563 564 if (aspath == NULL) 565 return 0; 566 567 pnt = aspath->data; 568 end = aspath->data + aspath->length; 569 570 while (pnt < end) 571 { 572 int i; 573 assegment = (struct assegment *) pnt; 574 575 for (i = 0; i < assegment->length; i++) 576 if (assegment->asval[i] == htons (asno)) 577 count++; 578 579 pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE; 580 } 581 return count; 582} 583 584/* When all of AS path is private AS return 1. */ 585int 586aspath_private_as_check (struct aspath *aspath) 587{ 588 caddr_t pnt; 589 caddr_t end; 590 struct assegment *assegment; 591 592 if (aspath == NULL) 593 return 0; 594 595 if (aspath->length == 0) 596 return 0; 597 598 pnt = aspath->data; 599 end = aspath->data + aspath->length; 600 601 while (pnt < end) 602 { 603 int i; 604 assegment = (struct assegment *) pnt; 605 606 for (i = 0; i < assegment->length; i++) 607 { 608 if (ntohs (assegment->asval[i]) < BGP_PRIVATE_AS_MIN 609 || ntohs (assegment->asval[i]) > BGP_PRIVATE_AS_MAX) 610 return 0; 611 } 612 pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE; 613 } 614 return 1; 615} 616 617/* Merge as1 to as2. as2 should be uninterned aspath. */ 618struct aspath * 619aspath_merge (struct aspath *as1, struct aspath *as2) 620{ 621 caddr_t data; 622 623 if (! as1 || ! as2) 624 return NULL; 625 626 data = XMALLOC (MTYPE_AS_SEG, as1->length + as2->length); 627 memcpy (data, as1->data, as1->length); 628 memcpy (data + as1->length, as2->data, as2->length); 629 630 XFREE (MTYPE_AS_SEG, as2->data); 631 as2->data = data; 632 as2->length += as1->length; 633 as2->count += as1->count; 634 return as2; 635} 636 637/* Prepend as1 to as2. as2 should be uninterned aspath. */ 638struct aspath * 639aspath_prepend (struct aspath *as1, struct aspath *as2) 640{ 641 caddr_t pnt; 642 caddr_t end; 643 struct assegment *seg1 = NULL; 644 struct assegment *seg2 = NULL; 645 646 if (! as1 || ! as2) 647 return NULL; 648 649 seg2 = (struct assegment *) as2->data; 650 651 /* In case of as2 is empty AS. */ 652 if (seg2 == NULL) 653 { 654 as2->length = as1->length; 655 as2->data = XMALLOC (MTYPE_AS_SEG, as1->length); 656 as2->count = as1->count; 657 memcpy (as2->data, as1->data, as1->length); 658 return as2; 659 } 660 661 /* assegment points last segment of as1. */ 662 pnt = as1->data; 663 end = as1->data + as1->length; 664 while (pnt < end) 665 { 666 seg1 = (struct assegment *) pnt; 667 pnt += (seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE; 668 } 669 670 /* In case of as1 is empty AS. */ 671 if (seg1 == NULL) 672 return as2; 673 674 /* Compare last segment type of as1 and first segment type of as2. */ 675 if (seg1->type != seg2->type) 676 return aspath_merge (as1, as2); 677 678 if (seg1->type == AS_SEQUENCE) 679 { 680 caddr_t newdata; 681 struct assegment *seg = NULL; 682 683 newdata = XMALLOC (MTYPE_AS_SEG, 684 as1->length + as2->length - AS_HEADER_SIZE); 685 memcpy (newdata, as1->data, as1->length); 686 seg = (struct assegment *) (newdata + ((caddr_t)seg1 - as1->data)); 687 seg->length += seg2->length; 688 memcpy (newdata + as1->length, as2->data + AS_HEADER_SIZE, 689 as2->length - AS_HEADER_SIZE); 690 691 XFREE (MTYPE_AS_SEG, as2->data); 692 as2->data = newdata; 693 as2->length += (as1->length - AS_HEADER_SIZE); 694 as2->count += as1->count; 695 696 return as2; 697 } 698 else 699 { 700 /* AS_SET merge code is needed at here. */ 701 return aspath_merge (as1, as2); 702 } 703 704 /* Not reached */ 705} 706 707/* Add specified AS to the leftmost of aspath. */ 708static struct aspath * 709aspath_add_one_as (struct aspath *aspath, as_t asno, u_char type) 710{ 711 struct assegment *assegment; 712 713 assegment = (struct assegment *) aspath->data; 714 715 /* In case of empty aspath. */ 716 if (assegment == NULL || assegment->length == 0) 717 { 718 aspath->length = AS_HEADER_SIZE + AS_VALUE_SIZE; 719 720 if (assegment) 721 aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data, aspath->length); 722 else 723 aspath->data = XMALLOC (MTYPE_AS_SEG, aspath->length); 724 725 assegment = (struct assegment *) aspath->data; 726 assegment->type = type; 727 assegment->length = 1; 728 assegment->asval[0] = htons (asno); 729 730 return aspath; 731 } 732 733 if (assegment->type == type) 734 { 735 caddr_t newdata; 736 struct assegment *newsegment; 737 738 newdata = XMALLOC (MTYPE_AS_SEG, aspath->length + AS_VALUE_SIZE); 739 newsegment = (struct assegment *) newdata; 740 741 newsegment->type = type; 742 newsegment->length = assegment->length + 1; 743 newsegment->asval[0] = htons (asno); 744 745 memcpy (newdata + AS_HEADER_SIZE + AS_VALUE_SIZE, 746 aspath->data + AS_HEADER_SIZE, 747 aspath->length - AS_HEADER_SIZE); 748 749 XFREE (MTYPE_AS_SEG, aspath->data); 750 751 aspath->data = newdata; 752 aspath->length += AS_VALUE_SIZE; 753 } else { 754 caddr_t newdata; 755 struct assegment *newsegment; 756 757 newdata = XMALLOC (MTYPE_AS_SEG, aspath->length + AS_VALUE_SIZE + AS_HEADER_SIZE); 758 newsegment = (struct assegment *) newdata; 759 760 newsegment->type = type; 761 newsegment->length = 1; 762 newsegment->asval[0] = htons (asno); 763 764 memcpy (newdata + AS_HEADER_SIZE + AS_VALUE_SIZE, 765 aspath->data, 766 aspath->length); 767 768 XFREE (MTYPE_AS_SEG, aspath->data); 769 770 aspath->data = newdata; 771 aspath->length += AS_HEADER_SIZE + AS_VALUE_SIZE; 772 } 773 774 return aspath; 775} 776 777/* Add specified AS to the leftmost of aspath. */ 778struct aspath * 779aspath_add_seq (struct aspath *aspath, as_t asno) 780{ 781 return aspath_add_one_as (aspath, asno, AS_SEQUENCE); 782} 783 784/* Compare leftmost AS value for MED check. If as1's leftmost AS and 785 as2's leftmost AS is same return 1. */ 786int 787aspath_cmp_left (struct aspath *aspath1, struct aspath *aspath2) 788{ 789 struct assegment *seg1; 790 struct assegment *seg2; 791 as_t as1; 792 as_t as2; 793 794 seg1 = (struct assegment *) aspath1->data; 795 seg2 = (struct assegment *) aspath2->data; 796 797 while (seg1 && seg1->length 798 && (seg1->type == AS_CONFED_SEQUENCE || seg1->type == AS_CONFED_SET)) 799 seg1 = (struct assegment *) ((caddr_t) seg1 + ASSEGMENT_LEN (seg1)); 800 while (seg2 && seg2->length 801 && (seg2->type == AS_CONFED_SEQUENCE || seg2->type == AS_CONFED_SET)) 802 seg2 = (struct assegment *) ((caddr_t) seg2 + ASSEGMENT_LEN (seg2)); 803 804 /* Check as1's */ 805 if (seg1 == NULL || seg1->length == 0 || seg1->type != AS_SEQUENCE) 806 return 0; 807 as1 = seg1->asval[0]; 808 809 if (seg2 == NULL || seg2->length == 0 || seg2->type != AS_SEQUENCE) 810 return 0; 811 as2 = seg2->asval[0]; 812 813 if (as1 == as2) 814 return 1; 815 816 return 0; 817} 818 819/* Compare leftmost AS value for MED check. If as1's leftmost AS and 820 as2's leftmost AS is same return 1. (confederation as-path 821 only). */ 822int 823aspath_cmp_left_confed (struct aspath *aspath1, struct aspath *aspath2) 824{ 825 struct assegment *seg1; 826 struct assegment *seg2; 827 828 as_t as1; 829 as_t as2; 830 831 if (aspath1->count || aspath2->count) 832 return 0; 833 834 seg1 = (struct assegment *) aspath1->data; 835 seg2 = (struct assegment *) aspath2->data; 836 837 /* Check as1's */ 838 if (seg1 == NULL || seg1->length == 0 || seg1->type != AS_CONFED_SEQUENCE) 839 return 0; 840 as1 = seg1->asval[0]; 841 842 /* Check as2's */ 843 if (seg2 == NULL || seg2->length == 0 || seg2->type != AS_CONFED_SEQUENCE) 844 return 0; 845 as2 = seg2->asval[0]; 846 847 if (as1 == as2) 848 return 1; 849 850 return 0; 851} 852 853/* Delete first sequential AS_CONFED_SEQUENCE from aspath. */ 854struct aspath * 855aspath_delete_confed_seq (struct aspath *aspath) 856{ 857 int seglen; 858 struct assegment *assegment; 859 860 if (! aspath) 861 return aspath; 862 863 assegment = (struct assegment *) aspath->data; 864 865 while (assegment) 866 { 867 if (assegment->type != AS_CONFED_SEQUENCE) 868 return aspath; 869 870 seglen = ASSEGMENT_LEN (assegment); 871 872 if (seglen == aspath->length) 873 { 874 XFREE (MTYPE_AS_SEG, aspath->data); 875 aspath->data = NULL; 876 aspath->length = 0; 877 } 878 else 879 { 880 memcpy (aspath->data, aspath->data + seglen, 881 aspath->length - seglen); 882 aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data, 883 aspath->length - seglen); 884 aspath->length -= seglen; 885 } 886 887 assegment = (struct assegment *) aspath->data; 888 } 889 return aspath; 890} 891 892/* Add new AS number to the leftmost part of the aspath as 893 AS_CONFED_SEQUENCE. */ 894struct aspath* 895aspath_add_confed_seq (struct aspath *aspath, as_t asno) 896{ 897 return aspath_add_one_as (aspath, asno, AS_CONFED_SEQUENCE); 898} 899 900/* Add new as value to as path structure. */ 901void 902aspath_as_add (struct aspath *as, as_t asno) 903{ 904 caddr_t pnt; 905 caddr_t end; 906 struct assegment *assegment; 907 908 /* Increase as->data for new as value. */ 909 as->data = XREALLOC (MTYPE_AS_SEG, as->data, as->length + 2); 910 as->length += 2; 911 912 pnt = as->data; 913 end = as->data + as->length; 914 assegment = (struct assegment *) pnt; 915 916 /* Last segment search procedure. */ 917 while (pnt + 2 < end) 918 { 919 assegment = (struct assegment *) pnt; 920 921 /* We add 2 for segment_type and segment_length and segment 922 value assegment->length * 2. */ 923 pnt += (AS_HEADER_SIZE + (assegment->length * AS_VALUE_SIZE)); 924 } 925 926 assegment->asval[assegment->length] = htons (asno); 927 assegment->length++; 928} 929 930/* Add new as segment to the as path. */ 931void 932aspath_segment_add (struct aspath *as, int type) 933{ 934 struct assegment *assegment; 935 936 if (as->data == NULL) 937 { 938 as->data = XMALLOC (MTYPE_AS_SEG, 2); 939 assegment = (struct assegment *) as->data; 940 as->length = 2; 941 } 942 else 943 { 944 as->data = XREALLOC (MTYPE_AS_SEG, as->data, as->length + 2); 945 assegment = (struct assegment *) (as->data + as->length); 946 as->length += 2; 947 } 948 949 assegment->type = type; 950 assegment->length = 0; 951} 952 953struct aspath * 954aspath_empty () 955{ 956 return aspath_parse (NULL, 0); 957} 958 959struct aspath * 960aspath_empty_get () 961{ 962 struct aspath *aspath; 963 964 aspath = aspath_new (); 965 aspath->str = aspath_make_str_count (aspath); 966 return aspath; 967} 968 969unsigned long 970aspath_count () 971{ 972 return ashash->count; 973} 974 975/* 976 Theoretically, one as path can have: 977 978 One BGP packet size should be less than 4096. 979 One BGP attribute size should be less than 4096 - BGP header size. 980 One BGP aspath size should be less than 4096 - BGP header size - 981 BGP mandantry attribute size. 982*/ 983 984/* AS path string lexical token enum. */ 985enum as_token 986{ 987 as_token_asval, 988 as_token_set_start, 989 as_token_set_end, 990 as_token_confed_start, 991 as_token_confed_end, 992 as_token_unknown 993}; 994 995/* Return next token and point for string parse. */ 996char * 997aspath_gettoken (char *buf, enum as_token *token, u_short *asno) 998{ 999 char *p = buf; 1000 1001 /* Skip space. */ 1002 while (isspace ((int) *p)) 1003 p++; 1004 1005 /* Check the end of the string and type specify characters 1006 (e.g. {}()). */ 1007 switch (*p) 1008 { 1009 case '\0': 1010 return NULL; 1011 break; 1012 case '{': 1013 *token = as_token_set_start; 1014 p++; 1015 return p; 1016 break; 1017 case '}': 1018 *token = as_token_set_end; 1019 p++; 1020 return p; 1021 break; 1022 case '(': 1023 *token = as_token_confed_start; 1024 p++; 1025 return p; 1026 break; 1027 case ')': 1028 *token = as_token_confed_end; 1029 p++; 1030 return p; 1031 break; 1032 } 1033 1034 /* Check actual AS value. */ 1035 if (isdigit ((int) *p)) 1036 { 1037 u_short asval; 1038 1039 *token = as_token_asval; 1040 asval = (*p - '0'); 1041 p++; 1042 while (isdigit ((int) *p)) 1043 { 1044 asval *= 10; 1045 asval += (*p - '0'); 1046 p++; 1047 } 1048 *asno = asval; 1049 return p; 1050 } 1051 1052 /* There is no match then return unknown token. */ 1053 *token = as_token_unknown; 1054 return p++; 1055} 1056 1057struct aspath * 1058aspath_str2aspath (char *str) 1059{ 1060 enum as_token token; 1061 u_short as_type; 1062 u_short asno; 1063 struct aspath *aspath; 1064 int needtype; 1065 1066 aspath = aspath_new (); 1067 1068 /* We start default type as AS_SEQUENCE. */ 1069 as_type = AS_SEQUENCE; 1070 needtype = 1; 1071 1072 while ((str = aspath_gettoken (str, &token, &asno)) != NULL) 1073 { 1074 switch (token) 1075 { 1076 case as_token_asval: 1077 if (needtype) 1078 { 1079 aspath_segment_add (aspath, as_type); 1080 needtype = 0; 1081 } 1082 aspath_as_add (aspath, asno); 1083 break; 1084 case as_token_set_start: 1085 as_type = AS_SET; 1086 aspath_segment_add (aspath, as_type); 1087 needtype = 0; 1088 break; 1089 case as_token_set_end: 1090 as_type = AS_SEQUENCE; 1091 needtype = 1; 1092 break; 1093 case as_token_confed_start: 1094 as_type = AS_CONFED_SEQUENCE; 1095 aspath_segment_add (aspath, as_type); 1096 needtype = 0; 1097 break; 1098 case as_token_confed_end: 1099 as_type = AS_SEQUENCE; 1100 needtype = 1; 1101 break; 1102 case as_token_unknown: 1103 default: 1104 return NULL; 1105 break; 1106 } 1107 } 1108 1109 aspath->str = aspath_make_str_count (aspath); 1110 1111 return aspath; 1112} 1113 1114/* Make hash value by raw aspath data. */ 1115unsigned int 1116aspath_key_make (struct aspath *aspath) 1117{ 1118 unsigned int key = 0; 1119 int length; 1120 caddr_t pnt; 1121 1122 length = aspath->length; 1123 pnt = aspath->data; 1124 1125 while (length) 1126 key += pnt[--length]; 1127 1128 return key; 1129} 1130 1131/* If two aspath have same value then return 1 else return 0 */ 1132int 1133aspath_cmp (struct aspath *as1, struct aspath *as2) 1134{ 1135 if (as1->length == as2->length 1136 && !memcmp (as1->data, as2->data, as1->length)) 1137 return 1; 1138 else 1139 return 0; 1140} 1141 1142/* AS path hash initialize. */ 1143void 1144aspath_init () 1145{ 1146 ashash = hash_create (aspath_key_make, aspath_cmp); 1147} 1148 1149/* return and as path value */ 1150const char * 1151aspath_print (struct aspath *as) 1152{ 1153 return as->str; 1154} 1155 1156/* Printing functions */ 1157void 1158aspath_print_vty (struct vty *vty, struct aspath *as) 1159{ 1160 vty_out (vty, "%s", as->str); 1161} 1162 1163void 1164aspath_show_all_iterator (struct hash_backet *backet, struct vty *vty) 1165{ 1166 struct aspath *as; 1167 1168 as = (struct aspath *) backet->data; 1169 1170 vty_out (vty, "[%p:%d] (%ld) ", backet, backet->key, as->refcnt); 1171 vty_out (vty, "%s%s", as->str, VTY_NEWLINE); 1172} 1173 1174/* Print all aspath and hash information. This function is used from 1175 `show ip bgp paths' command. */ 1176void 1177aspath_print_all_vty (struct vty *vty) 1178{ 1179 hash_iterate (ashash, 1180 (void (*) (struct hash_backet *, void *)) 1181 aspath_show_all_iterator, 1182 vty); 1183} 1184