bgpd/bgp_aspath.c

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