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