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