bgpd/bgp_aspath.c

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