开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Linux/Unix编程 > 网络 > 查看源码
bgp_aspath.c
资源名称：zebra-0.95a.tar.gz　[点击查看]
上传用户：xiaozhuqw
上传日期：2009-11-15
资源大小：1338k
文件大小：26k
源码类别：

网络

开发平台：

Unix_Linux

bgp_aspath.c：源码内容
  1. /* AS path management routines.
  2.    Copyright (C) 1996, 97, 98, 99 Kunihiro Ishiguro
  4.    This file is part of GNU Zebra.
  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.
  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.
  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.  */
  21. #include <zebra.h>
  23. #include "hash.h"
  24. #include "memory.h"
  25. #include "vector.h"
  26. #include "vty.h"
  27. #include "str.h"
  28. #include "log.h"
  30. #include "bgpd/bgpd.h"
  31. #include "bgpd/bgp_aspath.h"
  33. /* Attr. Flags and Attr. Type Code. */
  34. #define AS_HEADER_SIZE        2  
  36. /* Two octet is used for AS value. */
  37. #define AS_VALUE_SIZE         sizeof (as_t)
  39. /* AS segment octet length. */
  40. #define ASSEGMENT_LEN(X)  ((X)->length * AS_VALUE_SIZE + AS_HEADER_SIZE)
  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. };
  50. /* Hash for aspath.  This is the top level structure of AS path. */
  51. struct hash *ashash;
  53. static struct aspath *
  54. aspath_new ()
  55. {
  56.   struct aspath *aspath;
  58.   aspath = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
  59.   memset (aspath, 0, sizeof (struct aspath));
  60.   return aspath;
  61. }
  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. }
  76. /* Unintern aspath from AS path bucket. */
  77. void
  78. aspath_unintern (struct aspath *aspath)
  79. {
  80.   struct aspath *ret;
  82.   if (aspath->refcnt)
  83.     aspath->refcnt--;
  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. }
  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.     };
  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. }
  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.   u_char *str_buf;
  140.   int count = 0;
  142.   /* Empty aspath. */
  143.   if (as->length == 0)
  144.     {
  145.       str_buf = XMALLOC (MTYPE_AS_STR, 1);
  146.       str_buf[0] = '';
  147.       as->count = count;
  148.       return str_buf;
  149.     }
  151.   /* Set default value. */
  152.   space = 0;
  153.   type = AS_SEQUENCE;
  155.   /* Set initial pointer. */
  156.   pnt = as->data;
  157.   end = pnt + as->length;
  159.   str_buf = XMALLOC (MTYPE_AS_STR, str_size);
  160.   str_pnt = 0;
  162.   assegment = (struct assegment *) pnt;
  164.   while (pnt < end)
  165.     {
  166.       int i;
  167.       int estimate_len;
  169.       /* For fetch value. */
  170.       assegment = (struct assegment *) pnt;
  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. }
  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. }
  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. }
  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++] = ' ';
  206.       if (assegment->type != AS_SEQUENCE)
  207. str_buf[str_pnt++] = aspath_delimiter_char (assegment->type, AS_SEG_START);
  209.       space = 0;
  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. }
  221.       for (i = 0; i < assegment->length; i++)
  222. {
  223.   int len;
  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;
  236.   len = sprintf (str_buf + str_pnt, "%d", ntohs (assegment->asval[i]));
  237.   str_pnt += len;
  238. }
  240.       type = assegment->type;
  241.       pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE;
  242.     }
  244.   if (assegment->type != AS_SEQUENCE)
  245.     str_buf[str_pnt++] = aspath_delimiter_char (assegment->type, AS_SEG_END);
  247.   str_buf[str_pnt] = '';
  249.   as->count = count;
  251.   return str_buf;
  252. }
  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);
  263.   /* Check AS path hash. */
  264.   find = hash_get (ashash, aspath, hash_alloc_intern);
  266.   if (find != aspath)
  267.     aspath_free (aspath);
  269.   find->refcnt++;
  271.   if (! find->str)
  272.     find->str = aspath_make_str_count (find);
  274.   return find;
  275. }
  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;
  284.   new = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
  285.   memset (new, 0, sizeof (struct aspath));
  287.   new->length = aspath->length;
  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;
  297.   /* new->str = aspath_make_str_count (aspath); */
  299.   return new;
  300. }
  302. void *
  303. aspath_hash_alloc (struct aspath *arg)
  304. {
  305.   struct aspath *aspath;
  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;
  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;
  321.   /* Make AS path string. */
  322.   aspath->str = aspath_make_str_count (aspath);
  324.   /* Malformed AS path value. */
  325.   if (! aspath->str)
  326.     {
  327.       aspath_free (aspath);
  328.       return NULL;
  329.     }
  331.   return aspath;
  332. }
  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;
  343.   /* If length is odd it's malformed AS path. */
  344.   if (length % 2)
  345.     return NULL;
  347.   /* Looking up aspath hash entry. */
  348.   as.data = pnt;
  349.   as.length = length;
  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++;
  357.   return find;
  358. }
  360. #define min(A,B) ((A) < (B) ? (A) : (B))
  362. #define ASSEGMENT_SIZE(N)  (AS_HEADER_SIZE + ((N) * AS_VALUE_SIZE))
  364. struct aspath *
  365. aspath_aggregate_segment_copy (struct aspath *aspath, struct assegment *seg,
  366.        int i)
  367. {
  368.   struct assegment *newseg;
  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.     }
  384.   newseg->type = seg->type;
  385.   newseg->length = i;
  386.   memcpy (newseg->asval, seg->asval, (i * AS_VALUE_SIZE));
  388.   return aspath;
  389. }
  391. struct assegment *
  392. aspath_aggregate_as_set_add (struct aspath *aspath, struct assegment *asset,
  393.      as_t as)
  394. {
  395.   int i;
  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;
  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;
  426.       offset = (caddr_t) asset - (caddr_t) aspath->data;
  427.       aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data,
  428.        aspath->length + AS_VALUE_SIZE);
  430.       asset = (struct assegment *) (aspath->data + offset);
  431.       aspath->length += AS_VALUE_SIZE;
  432.       asset->asval[asset->length] = as;
  433.       asset->length++;
  434.     }
  436.   return asset;
  437. }
  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;
  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;
  466.   seg1 = (struct assegment *) cp1;
  467.   seg2 = (struct assegment *) cp2;
  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;
  476.       /* Minimum segment length. */
  477.       minlen = min (seg1->length, seg2->length);
  479.       for (match = 0; match < minlen; match++)
  480. if (seg1->asval[match] != seg2->asval[match])
  481.   break;
  483.       if (match)
  484. {
  485.   if (! aspath)
  486.     aspath = aspath_new();
  487.   aspath = aspath_aggregate_segment_copy (aspath, seg1, match);
  488. }
  490.       if (match != minlen || match != seg1->length 
  491.   || seg1->length != seg2->length)
  492. break;
  494.       cp1 += ((seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
  495.       cp2 += ((seg2->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
  497.       seg1 = (struct assegment *) cp1;
  498.       seg2 = (struct assegment *) cp2;
  499.     }
  501.   if (! aspath)
  502.     aspath = aspath_new();
  504.   /* Make as-set using rest of all information. */
  505.   match1 = match;
  506.   while (cp1 < end1)
  507.     {
  508.       seg1 = (struct assegment *) cp1;
  510.       for (i = match1; i < seg1->length; i++)
  511. asset = aspath_aggregate_as_set_add (aspath, asset, seg1->asval[i]);
  513.       match1 = 0;
  514.       cp1 += ((seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
  515.     }
  517.   match2 = match;
  518.   while (cp2 < end2)
  519.     {
  520.       seg2 = (struct assegment *) cp2;
  522.       for (i = match2; i < seg2->length; i++)
  523. asset = aspath_aggregate_as_set_add (aspath, asset, seg2->asval[i]);
  525.       match2 = 0;
  526.       cp2 += ((seg2->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
  527.     }
  529.   return aspath;
  530. }
  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;
  541.   if (aspath == NULL)
  542.     return 0;
  544.   pnt = aspath->data;
  545.   assegment = (struct assegment *) pnt;
  547.   if (assegment
  548.       && assegment->type == AS_SEQUENCE
  549.       && assegment->asval[0] == htons (asno))
  550.     return 1;
  552.   return 0;
  553. }
  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;
  564.   if (aspath == NULL)
  565.     return 0;
  567.   pnt = aspath->data;
  568.   end = aspath->data + aspath->length;
  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++;
  579.       pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE;
  580.     }
  581.   return count;
  582. }
  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;
  592.   if (aspath == NULL)
  593.     return 0;
  595.   if (aspath->length == 0)
  596.     return 0;
  598.   pnt = aspath->data;
  599.   end = aspath->data + aspath->length;
  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. }
  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;
  623.   if (! as1 || ! as2)
  624.     return NULL;
  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);
  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. }
  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;
  646.   if (! as1 || ! as2)
  647.     return NULL;
  649.   seg2 = (struct assegment *) as2->data;
  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.     }
  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.     }
  670.   /* In case of as1 is empty AS. */
  671.   if (seg1 == NULL)
  672.     return as2;
  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);
  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);
  691.       XFREE (MTYPE_AS_SEG, as2->data);
  692.       as2->data = newdata;
  693.       as2->length += (as1->length - AS_HEADER_SIZE);
  694.       as2->count += as1->count;
  696.       return as2;
  697.     }
  698.   else
  699.     {
  700.       /* AS_SET merge code is needed at here. */
  701.       return aspath_merge (as1, as2);
  702.     }
  704.   /* Not reached */
  705. }
  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;
  713.   assegment = (struct assegment *) aspath->data;
  715.   /* In case of empty aspath. */
  716.   if (assegment == NULL || assegment->length == 0)
  717.     {
  718.       aspath->length = AS_HEADER_SIZE + AS_VALUE_SIZE;
  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);
  725.       assegment = (struct assegment *) aspath->data;
  726.       assegment->type = type;
  727.       assegment->length = 1;
  728.       assegment->asval[0] = htons (asno);
  730.       return aspath;
  731.     }
  733.   if (assegment->type == type)
  734.     {
  735.       caddr_t newdata;
  736.       struct assegment *newsegment;
  738.       newdata = XMALLOC (MTYPE_AS_SEG, aspath->length + AS_VALUE_SIZE);
  739.       newsegment = (struct assegment *) newdata;
  741.       newsegment->type = type;
  742.       newsegment->length = assegment->length + 1;
  743.       newsegment->asval[0] = htons (asno);
  745.       memcpy (newdata + AS_HEADER_SIZE + AS_VALUE_SIZE,
  746.       aspath->data + AS_HEADER_SIZE, 
  747.       aspath->length - AS_HEADER_SIZE);
  749.       XFREE (MTYPE_AS_SEG, aspath->data);
  751.       aspath->data = newdata;
  752.       aspath->length += AS_VALUE_SIZE;
  753.     } else {
  754.       caddr_t newdata;
  755.       struct assegment *newsegment;
  757.       newdata = XMALLOC (MTYPE_AS_SEG, aspath->length + AS_VALUE_SIZE + AS_HEADER_SIZE);
  758.       newsegment = (struct assegment *) newdata;
  760.       newsegment->type = type;
  761.       newsegment->length = 1;
  762.       newsegment->asval[0] = htons (asno);
  764.       memcpy (newdata + AS_HEADER_SIZE + AS_VALUE_SIZE,
  765.       aspath->data,
  766.       aspath->length);
  768.       XFREE (MTYPE_AS_SEG, aspath->data);
  770.       aspath->data = newdata;
  771.       aspath->length += AS_HEADER_SIZE + AS_VALUE_SIZE;
  772.     }
  774.   return aspath;
  775. }
  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. }
  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;
  794.   seg1 = (struct assegment *) aspath1->data;
  795.   seg2 = (struct assegment *) aspath2->data;
  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));
  804.   /* Check as1's */
  805.   if (seg1 == NULL || seg1->length == 0 || seg1->type != AS_SEQUENCE)
  806.     return 0;
  807.   as1 = seg1->asval[0];
  809.   if (seg2 == NULL || seg2->length == 0 || seg2->type != AS_SEQUENCE)
  810.     return 0;
  811.   as2 = seg2->asval[0];
  813.   if (as1 == as2)
  814.     return 1;
  816.   return 0;
  817. }
  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;
  828.   as_t as1;
  829.   as_t as2;
  831.   if (aspath1->count || aspath2->count) 
  832.     return 0;
  834.   seg1 = (struct assegment *) aspath1->data;
  835.   seg2 = (struct assegment *) aspath2->data;
  837.   /* Check as1's */
  838.   if (seg1 == NULL || seg1->length == 0 || seg1->type != AS_CONFED_SEQUENCE)
  839.     return 0;
  840.   as1 = seg1->asval[0];
  842.   /* Check as2's */
  843.   if (seg2 == NULL || seg2->length == 0 || seg2->type != AS_CONFED_SEQUENCE)
  844.     return 0;
  845.   as2 = seg2->asval[0];
  847.   if (as1 == as2)
  848.     return 1;
  850.   return 0;
  851. }
  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;
  860.   if (! aspath)
  861.     return aspath;
  863.   assegment = (struct assegment *) aspath->data;
  865.   while (assegment)
  866.     {
  867.       if (assegment->type != AS_CONFED_SEQUENCE)
  868. return aspath;
  870.       seglen = ASSEGMENT_LEN (assegment);
  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. }
  887.       assegment = (struct assegment *) aspath->data;
  888.     }
  889.   return aspath;
  890. }
  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. }
  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;
  908.   /* Increase as->data for new as value. */
  909.   as->data = XREALLOC (MTYPE_AS_SEG, as->data, as->length + 2);
  910.   as->length += 2;
  912.   pnt = as->data;
  913.   end = as->data + as->length;
  914.   assegment = (struct assegment *) pnt;
  916.   /* Last segment search procedure. */
  917.   while (pnt + 2 < end)
  918.     {
  919.       assegment = (struct assegment *) pnt;
  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.     }
  926.   assegment->asval[assegment->length] = htons (asno);
  927.   assegment->length++;
  928. }
  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;
  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.     }
  949.   assegment->type = type;
  950.   assegment->length = 0;
  951. }
  953. struct aspath *
  954. aspath_empty ()
  955. {
  956.   return aspath_parse (NULL, 0);
  957. }
  959. struct aspath *
  960. aspath_empty_get ()
  961. {
  962.   struct aspath *aspath;
  964.   aspath = aspath_new ();
  965.   aspath->str = aspath_make_str_count (aspath);
  966.   return aspath;
  967. }
  969. unsigned long
  970. aspath_count ()
  971. {
  972.   return ashash->count;
  973. }     
  975. /* 
  976.    Theoretically, one as path can have:
  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. */
  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.   };
  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;
  1001.   /* Skip space. */
  1002.   while (isspace ((int) *p))
  1003.     p++;
  1005.   /* Check the end of the string and type specify characters
  1006.      (e.g. {}()). */
  1007.   switch (*p)
  1008.     {
  1009.     case '':
  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.     }
  1034.   /* Check actual AS value. */
  1035.   if (isdigit ((int) *p)) 
  1036.     {
  1037.       u_short asval;
  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. }
  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;
  1066.   aspath = aspath_new ();
  1068.   /* We start default type as AS_SEQUENCE. */
  1069.   as_type = AS_SEQUENCE;
  1070.   needtype = 1;
  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.     }
  1109.   aspath->str = aspath_make_str_count (aspath);
  1111.   return aspath;
  1112. }
  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;
  1122.   length = aspath->length / 2;
  1123.   pnt = (unsigned short *) aspath->data;
  1125.   while (length)
  1126.     {
  1127.       key += *pnt++;
  1128.       length--;
  1129.     }
  1131.   return key;
  1132. }
  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. }
  1145. /* AS path hash initialize. */
  1146. void
  1147. aspath_init ()
  1148. {
  1149.   ashash = hash_create_size (32767, aspath_key_make, aspath_cmp);
  1150. }
  1152. /* return and as path value */
  1153. const char *
  1154. aspath_print (struct aspath *as)
  1155. {
  1156.   return as->str;
  1157. }
  1159. /* Printing functions */
  1160. void
  1161. aspath_print_vty (struct vty *vty, struct aspath *as)
  1162. {
  1163.   vty_out (vty, "%s", as->str);
  1164. }
  1166. void
  1167. aspath_show_all_iterator (struct hash_backet *backet, struct vty *vty)
  1168. {
  1169.   struct aspath *as;
  1171.   as = (struct aspath *) backet->data;
  1173.   vty_out (vty, "[%p:%d] (%ld) ", backet, backet->key, as->refcnt);
  1174.   vty_out (vty, "%s%s", as->str, VTY_NEWLINE);
  1175. }
  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. }