Initial revision

1 files changed, 1186 insertions, 0 deletions

diff --git a/bgpd/bgp_aspath.c b/bgpd/bgp_aspath.c
new file mode 100644
index 00000000..fc5efb19
--- /dev/null
+++ b/bgpd/bgp_aspath.c
@@ -0,0 +1,1186 @@
+/* AS path management routines.
+   Copyright (C) 1996, 97, 98, 99 Kunihiro Ishiguro
+
+This file is part of GNU Zebra.
+
+GNU Zebra is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 2, or (at your option) any
+later version.
+
+GNU Zebra is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Zebra; see the file COPYING.  If not, write to the Free
+Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include <zebra.h>
+
+#include "hash.h"
+#include "memory.h"
+#include "vector.h"
+#include "vty.h"
+#include "str.h"
+#include "log.h"
+
+#include "bgpd/bgpd.h"
+#include "bgpd/bgp_aspath.h"
+
+/* Attr. Flags and Attr. Type Code. */
+#define AS_HEADER_SIZE        2	 
+
+/* Two octet is used for AS value. */
+#define AS_VALUE_SIZE         sizeof (as_t)
+
+/* AS segment octet length. */
+#define ASSEGMENT_LEN(X)  ((X)->length * AS_VALUE_SIZE + AS_HEADER_SIZE)
+
+/* To fetch and store as segment value. */
+struct assegment
+{
+  u_char type;
+  u_char length;
+  as_t asval[1];
+};
+
+/* Hash for aspath.  This is the top level structure of AS path. */
+struct hash *ashash;
+
+static struct aspath *
+aspath_new ()
+{
+  struct aspath *aspath;
+
+  aspath = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
+  memset (aspath, 0, sizeof (struct aspath));
+  return aspath;
+}
+
+/* Free AS path structure. */
+void
+aspath_free (struct aspath *aspath)
+{
+  if (!aspath)
+    return;
+  if (aspath->data)
+    XFREE (MTYPE_AS_SEG, aspath->data);
+  if (aspath->str)
+    XFREE (MTYPE_AS_STR, aspath->str);
+  XFREE (MTYPE_AS_PATH, aspath);
+}
+
+/* Unintern aspath from AS path bucket. */
+void
+aspath_unintern (struct aspath *aspath)
+{
+  struct aspath *ret;
+
+  if (aspath->refcnt)
+    aspath->refcnt--;
+
+  if (aspath->refcnt == 0)
+    {
+      /* This aspath must exist in aspath hash table. */
+      ret = hash_release (ashash, aspath);
+      assert (ret != NULL);
+      aspath_free (aspath);
+    }
+}
+
+/* Return the start or end delimiters for a particular Segment type */
+#define AS_SEG_START 0
+#define AS_SEG_END 1
+static char
+aspath_delimiter_char (u_char type, u_char which)
+{
+  int i;
+  struct
+  {
+    int type;
+    char start;
+    char end;
+  } aspath_delim_char [] =
+    {
+      { AS_SET,             '{', '}' },
+      { AS_SEQUENCE,        ' ', ' ' },
+      { AS_CONFED_SET,      '[', ']' },
+      { AS_CONFED_SEQUENCE, '(', ')' },
+      { 0 }
+    };
+
+  for (i = 0; aspath_delim_char[i].type != 0; i++)
+    {
+      if (aspath_delim_char[i].type == type)
+	{
+	  if (which == AS_SEG_START)
+	    return aspath_delim_char[i].start;
+	  else if (which == AS_SEG_END)
+	    return aspath_delim_char[i].end;
+	}
+    }
+  return ' ';
+}
+
+/* Convert aspath structure to string expression. */
+char *
+aspath_make_str_count (struct aspath *as)
+{
+  int space;
+  u_char type;
+  caddr_t pnt;
+  caddr_t end;
+  struct assegment *assegment;
+  int str_size = ASPATH_STR_DEFAULT_LEN;
+  int str_pnt;
+  u_char *str_buf;
+  int count = 0;
+
+  /* Empty aspath. */
+  if (as->length == 0)
+    {
+      str_buf = XMALLOC (MTYPE_AS_STR, 1);
+      str_buf[0] = '\0';
+      as->count = count;
+      return str_buf;
+    }
+
+  /* Set default value. */
+  space = 0;
+  type = AS_SEQUENCE;
+
+  /* Set initial pointer. */
+  pnt = as->data;
+  end = pnt + as->length;
+
+  str_buf = XMALLOC (MTYPE_AS_STR, str_size);
+  str_pnt = 0;
+
+  assegment = (struct assegment *) pnt;
+
+  while (pnt < end)
+    {
+      int i;
+      int estimate_len;
+
+      /* For fetch value. */
+      assegment = (struct assegment *) pnt;
+
+      /* Check AS type validity. */
+      if ((assegment->type != AS_SET) && 
+	  (assegment->type != AS_SEQUENCE) &&
+	  (assegment->type != AS_CONFED_SET) && 
+	  (assegment->type != AS_CONFED_SEQUENCE))
+	{
+	  XFREE (MTYPE_AS_STR, str_buf);
+	  return NULL;
+	}
+
+      /* Check AS length. */
+      if ((pnt + (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE) > end)
+	{
+	  XFREE (MTYPE_AS_STR, str_buf);
+	  return NULL;
+	}
+
+      /* Buffer length check. */
+      estimate_len = ((assegment->length * 6) + 4);
+      
+      /* String length check. */
+      while (str_pnt + estimate_len >= str_size)
+	{
+	  str_size *= 2;
+	  str_buf = XREALLOC (MTYPE_AS_STR, str_buf, str_size);
+	}
+
+      /* If assegment type is changed, print previous type's end
+         character. */
+      if (type != AS_SEQUENCE)
+	str_buf[str_pnt++] = aspath_delimiter_char (type, AS_SEG_END);
+      if (space)
+	str_buf[str_pnt++] = ' ';
+
+      if (assegment->type != AS_SEQUENCE)
+	str_buf[str_pnt++] = aspath_delimiter_char (assegment->type, AS_SEG_START);
+
+      space = 0;
+
+      /* Increment count - ignoring CONFED SETS/SEQUENCES */
+      if (assegment->type != AS_CONFED_SEQUENCE
+	  && assegment->type != AS_CONFED_SET)
+	{
+	  if (assegment->type == AS_SEQUENCE)
+	    count += assegment->length;
+	  else if (assegment->type == AS_SET)
+	    count++;
+	}
+
+      for (i = 0; i < assegment->length; i++)
+	{
+	  int len;
+
+	  if (space)
+	    {
+	      if (assegment->type == AS_SET
+		  || assegment->type == AS_CONFED_SET)
+		str_buf[str_pnt++] = ',';
+	      else
+		str_buf[str_pnt++] = ' ';
+	    }
+	  else
+	    space = 1;
+
+	  len = sprintf (str_buf + str_pnt, "%d", ntohs (assegment->asval[i]));
+	  str_pnt += len;
+	}
+
+      type = assegment->type;
+      pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE;
+    }
+
+  if (assegment->type != AS_SEQUENCE)
+    str_buf[str_pnt++] = aspath_delimiter_char (assegment->type, AS_SEG_END);
+
+  str_buf[str_pnt] = '\0';
+
+  as->count = count;
+
+  return str_buf;
+}
+
+/* Intern allocated AS path. */
+struct aspath *
+aspath_intern (struct aspath *aspath)
+{
+  struct aspath *find;
+  
+  /* Assert this AS path structure is not interned. */
+  assert (aspath->refcnt == 0);
+
+  /* Check AS path hash. */
+  find = hash_get (ashash, aspath, hash_alloc_intern);
+
+  if (find != aspath)
+      aspath_free (aspath);
+
+  find->refcnt++;
+
+  if (! find->str)
+    find->str = aspath_make_str_count (find);
+
+  return find;
+}
+
+/* Duplicate aspath structure.  Created same aspath structure but
+   reference count and AS path string is cleared. */
+struct aspath *
+aspath_dup (struct aspath *aspath)
+{
+  struct aspath *new;
+
+  new = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
+  memset (new, 0, sizeof (struct aspath));
+
+  new->length = aspath->length;
+
+  if (new->length)
+    {
+      new->data = XMALLOC (MTYPE_AS_SEG, aspath->length);
+      memcpy (new->data, aspath->data, aspath->length);
+    }
+  else
+    new->data = NULL;
+
+  /* new->str = aspath_make_str_count (aspath); */
+
+  return new;
+}
+
+void *
+aspath_hash_alloc (struct aspath *arg)
+{
+  struct aspath *aspath;
+
+  /* New aspath strucutre is needed. */
+  aspath = XMALLOC (MTYPE_AS_PATH, sizeof (struct aspath));
+  memset ((void *) aspath, 0, sizeof (struct aspath));
+  aspath->length = arg->length;
+
+  /* In case of IBGP connection aspath's length can be zero. */
+  if (arg->length)
+    {
+      aspath->data = XMALLOC (MTYPE_AS_SEG, arg->length);
+      memcpy (aspath->data, arg->data, arg->length);
+    }
+  else
+    aspath->data = NULL;
+
+  /* Make AS path string. */
+  aspath->str = aspath_make_str_count (aspath);
+
+  /* Malformed AS path value. */
+  if (! aspath->str)
+    {
+      aspath_free (aspath);
+      return NULL;
+    }
+
+  return aspath;
+}
+
+/* AS path parse function.  pnt is a pointer to byte stream and length
+   is length of byte stream.  If there is same AS path in the the AS
+   path hash then return it else make new AS path structure. */
+struct aspath *
+aspath_parse (caddr_t pnt, int length)
+{
+  struct aspath as;
+  struct aspath *find;
+
+  /* If length is odd it's malformed AS path. */
+  if (length % 2)
+    return NULL;
+
+  /* Looking up aspath hash entry. */
+  as.data = pnt;
+  as.length = length;
+
+  /* If already same aspath exist then return it. */
+  find = hash_get (ashash, &as, aspath_hash_alloc);
+  if (! find)
+    return NULL;
+  find->refcnt++;
+
+  return find;
+}
+
+#define min(A,B) ((A) < (B) ? (A) : (B))
+
+#define ASSEGMENT_SIZE(N)  (AS_HEADER_SIZE + ((N) * AS_VALUE_SIZE))
+
+struct aspath *
+aspath_aggregate_segment_copy (struct aspath *aspath, struct assegment *seg,
+			       int i)
+{
+  struct assegment *newseg;
+
+  if (! aspath->data)
+    {
+      aspath->data = XMALLOC (MTYPE_AS_SEG, ASSEGMENT_SIZE (i));
+      newseg = (struct assegment *) aspath->data;
+      aspath->length = ASSEGMENT_SIZE (i);
+    }
+  else
+    {
+      aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data,
+			       aspath->length + ASSEGMENT_SIZE (i));
+      newseg = (struct assegment *) (aspath->data + aspath->length);
+      aspath->length += ASSEGMENT_SIZE (i);
+    }
+
+  newseg->type = seg->type;
+  newseg->length = i;
+  memcpy (newseg->asval, seg->asval, (i * AS_VALUE_SIZE));
+
+  return aspath;
+}
+
+struct assegment *
+aspath_aggregate_as_set_add (struct aspath *aspath, struct assegment *asset,
+			     as_t as)
+{
+  int i;
+
+  /* If this is first AS set member, create new as-set segment. */
+  if (asset == NULL)
+    {
+      if (! aspath->data)
+	{
+	  aspath->data = XMALLOC (MTYPE_AS_SEG, ASSEGMENT_SIZE (1));
+	  asset = (struct assegment *) aspath->data;
+	  aspath->length = ASSEGMENT_SIZE (1);
+	}
+      else
+	{
+	  aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data,
+				   aspath->length + ASSEGMENT_SIZE (1));
+	  asset = (struct assegment *) (aspath->data + aspath->length);
+	  aspath->length += ASSEGMENT_SIZE (1);
+	}
+      asset->type = AS_SET;
+      asset->length = 1;
+      asset->asval[0] = as;
+    }
+  else
+    {
+      size_t offset;
+
+      /* Check this AS value already exists or not. */
+      for (i = 0; i < asset->length; i++)
+	if (asset->asval[i] == as)
+	  return asset;
+
+      offset = (caddr_t) asset - (caddr_t) aspath->data;
+      aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data,
+			       aspath->length + AS_VALUE_SIZE);
+
+      asset = (struct assegment *) (aspath->data + offset);
+      aspath->length += AS_VALUE_SIZE;
+      asset->asval[asset->length] = as;
+      asset->length++;
+    }
+
+  return asset;
+}
+
+/* Modify as1 using as2 for aggregation. */
+struct aspath *
+aspath_aggregate (struct aspath *as1, struct aspath *as2)
+{
+  int i;
+  int minlen;
+  int match;
+  int match1;
+  int match2;
+  caddr_t cp1;
+  caddr_t cp2;
+  caddr_t end1;
+  caddr_t end2;
+  struct assegment *seg1;
+  struct assegment *seg2;
+  struct aspath *aspath;
+  struct assegment *asset;
+
+  match = 0;
+  minlen = 0;
+  aspath = NULL;
+  asset = NULL;
+  cp1 = as1->data;
+  end1 = as1->data + as1->length;
+  cp2 = as2->data;
+  end2 = as2->data + as2->length;
+
+  seg1 = (struct assegment *) cp1;
+  seg2 = (struct assegment *) cp2;
+
+  /* First of all check common leading sequence. */
+  while ((cp1 < end1) && (cp2 < end2))
+    {
+      /* Check segment type. */
+      if (seg1->type != seg2->type)
+	break;
+
+      /* Minimum segment length. */
+      minlen = min (seg1->length, seg2->length);
+
+      for (match = 0; match < minlen; match++)
+	if (seg1->asval[match] != seg2->asval[match])
+	  break;
+
+      if (match)
+	{
+	  if (! aspath)
+	    aspath = aspath_new();
+	  aspath = aspath_aggregate_segment_copy (aspath, seg1, match);
+	}
+
+      if (match != minlen || match != seg1->length 
+	  || seg1->length != seg2->length)
+	break;
+
+      cp1 += ((seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
+      cp2 += ((seg2->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
+
+      seg1 = (struct assegment *) cp1;
+      seg2 = (struct assegment *) cp2;
+    }
+
+  if (! aspath)
+    aspath = aspath_new();
+
+  /* Make as-set using rest of all information. */
+  match1 = match;
+  while (cp1 < end1)
+    {
+      seg1 = (struct assegment *) cp1;
+
+      for (i = match1; i < seg1->length; i++)
+	asset = aspath_aggregate_as_set_add (aspath, asset, seg1->asval[i]);
+
+      match1 = 0;
+      cp1 += ((seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
+    }
+
+  match2 = match;
+  while (cp2 < end2)
+    {
+      seg2 = (struct assegment *) cp2;
+
+      for (i = match2; i < seg2->length; i++)
+	asset = aspath_aggregate_as_set_add (aspath, asset, seg2->asval[i]);
+
+      match2 = 0;
+      cp2 += ((seg2->length * AS_VALUE_SIZE) + AS_HEADER_SIZE);
+    }
+
+  return aspath;
+}
+
+/* When a BGP router receives an UPDATE with an MP_REACH_NLRI
+   attribute, check the leftmost AS number in the AS_PATH attribute is
+   or not the peer's AS number. */ 
+int
+aspath_firstas_check (struct aspath *aspath, as_t asno)
+{
+  caddr_t pnt;
+  struct assegment *assegment;
+
+  if (aspath == NULL)
+    return 0;
+
+  pnt = aspath->data;
+  assegment = (struct assegment *) pnt;
+
+  if (assegment
+      && assegment->type == AS_SEQUENCE
+      && assegment->asval[0] == htons (asno))
+    return 1;
+
+  return 0;
+}
+
+/* AS path loop check.  If aspath contains asno then return 1. */
+int
+aspath_loop_check (struct aspath *aspath, as_t asno)
+{
+  caddr_t pnt;
+  caddr_t end;
+  struct assegment *assegment;
+  int count = 0;
+
+  if (aspath == NULL)
+    return 0;
+
+  pnt = aspath->data;
+  end = aspath->data + aspath->length;
+
+  while (pnt < end)
+    {
+      int i;
+      assegment = (struct assegment *) pnt;
+      
+      for (i = 0; i < assegment->length; i++)
+	if (assegment->asval[i] == htons (asno))
+	  count++;
+
+      pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE;
+    }
+  return count;
+}
+
+/* When all of AS path is private AS return 1.  */
+int
+aspath_private_as_check (struct aspath *aspath)
+{
+  caddr_t pnt;
+  caddr_t end;
+  struct assegment *assegment;
+
+  if (aspath == NULL)
+    return 0;
+
+  if (aspath->length == 0)
+    return 0;
+
+  pnt = aspath->data;
+  end = aspath->data + aspath->length;
+
+  while (pnt < end)
+    {
+      int i;
+      assegment = (struct assegment *) pnt;
+      
+      for (i = 0; i < assegment->length; i++)
+	{
+	  if (ntohs (assegment->asval[i]) < BGP_PRIVATE_AS_MIN
+	      || ntohs (assegment->asval[i]) > BGP_PRIVATE_AS_MAX)
+	    return 0;
+	}
+      pnt += (assegment->length * AS_VALUE_SIZE) + AS_HEADER_SIZE;
+    }
+  return 1;
+}
+
+/* Merge as1 to as2.  as2 should be uninterned aspath. */
+struct aspath *
+aspath_merge (struct aspath *as1, struct aspath *as2)
+{
+  caddr_t data;
+
+  if (! as1 || ! as2)
+    return NULL;
+
+  data = XMALLOC (MTYPE_AS_SEG, as1->length + as2->length);
+  memcpy (data, as1->data, as1->length);
+  memcpy (data + as1->length, as2->data, as2->length);
+
+  XFREE (MTYPE_AS_SEG, as2->data);
+  as2->data = data;
+  as2->length += as1->length;
+  as2->count += as1->count;
+  return as2;
+}
+
+/* Prepend as1 to as2.  as2 should be uninterned aspath. */
+struct aspath *
+aspath_prepend (struct aspath *as1, struct aspath *as2)
+{
+  caddr_t pnt;
+  caddr_t end;
+  struct assegment *seg1 = NULL;
+  struct assegment *seg2 = NULL;
+
+  if (! as1 || ! as2)
+    return NULL;
+
+  seg2 = (struct assegment *) as2->data;
+
+  /* In case of as2 is empty AS. */
+  if (seg2 == NULL)
+    {
+      as2->length = as1->length;
+      as2->data = XMALLOC (MTYPE_AS_SEG, as1->length);
+      as2->count = as1->count;
+      memcpy (as2->data, as1->data, as1->length);
+      return as2;
+    }
+
+  /* assegment points last segment of as1. */
+  pnt = as1->data;
+  end = as1->data + as1->length;
+  while (pnt < end)
+    {
+      seg1 = (struct assegment *) pnt;
+      pnt += (seg1->length * AS_VALUE_SIZE) + AS_HEADER_SIZE;
+    }
+
+  /* In case of as1 is empty AS. */
+  if (seg1 == NULL)
+    return as2;
+
+  /* Compare last segment type of as1 and first segment type of as2. */
+  if (seg1->type != seg2->type)
+    return aspath_merge (as1, as2);
+
+  if (seg1->type == AS_SEQUENCE)
+    {
+      caddr_t newdata;
+      struct assegment *seg = NULL;
+      
+      newdata = XMALLOC (MTYPE_AS_SEG, 
+			 as1->length + as2->length - AS_HEADER_SIZE);
+      memcpy (newdata, as1->data, as1->length);
+      seg = (struct assegment *) (newdata + ((caddr_t)seg1 - as1->data));
+      seg->length += seg2->length;
+      memcpy (newdata + as1->length, as2->data + AS_HEADER_SIZE,
+	      as2->length - AS_HEADER_SIZE);
+
+      XFREE (MTYPE_AS_SEG, as2->data);
+      as2->data = newdata;
+      as2->length += (as1->length - AS_HEADER_SIZE);
+      as2->count += as1->count;
+
+      return as2;
+    }
+  else
+    {
+      /* AS_SET merge code is needed at here. */
+      return aspath_merge (as1, as2);
+    }
+
+  /* Not reached */
+}
+
+/* Add specified AS to the leftmost of aspath. */
+static struct aspath *
+aspath_add_one_as (struct aspath *aspath, as_t asno, u_char type)
+{
+  struct assegment *assegment;
+
+  assegment = (struct assegment *) aspath->data;
+
+  /* In case of empty aspath. */
+  if (assegment == NULL || assegment->length == 0)
+    {
+      aspath->length = AS_HEADER_SIZE + AS_VALUE_SIZE;
+
+      if (assegment)
+	aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data, aspath->length);
+      else
+	aspath->data = XMALLOC (MTYPE_AS_SEG, aspath->length);
+
+      assegment = (struct assegment *) aspath->data;
+      assegment->type = type;
+      assegment->length = 1;
+      assegment->asval[0] = htons (asno);
+
+      return aspath;
+    }
+
+  if (assegment->type == type)
+    {
+      caddr_t newdata;
+      struct assegment *newsegment;
+
+      newdata = XMALLOC (MTYPE_AS_SEG, aspath->length + AS_VALUE_SIZE);
+      newsegment = (struct assegment *) newdata;
+
+      newsegment->type = type;
+      newsegment->length = assegment->length + 1;
+      newsegment->asval[0] = htons (asno);
+
+      memcpy (newdata + AS_HEADER_SIZE + AS_VALUE_SIZE,
+	      aspath->data + AS_HEADER_SIZE, 
+	      aspath->length - AS_HEADER_SIZE);
+
+      XFREE (MTYPE_AS_SEG, aspath->data);
+
+      aspath->data = newdata;
+      aspath->length += AS_VALUE_SIZE;
+    } else {
+      caddr_t newdata;
+      struct assegment *newsegment;
+
+      newdata = XMALLOC (MTYPE_AS_SEG, aspath->length + AS_VALUE_SIZE + AS_HEADER_SIZE);
+      newsegment = (struct assegment *) newdata;
+
+      newsegment->type = type;
+      newsegment->length = 1;
+      newsegment->asval[0] = htons (asno);
+
+      memcpy (newdata + AS_HEADER_SIZE + AS_VALUE_SIZE,
+	      aspath->data,
+	      aspath->length);
+
+      XFREE (MTYPE_AS_SEG, aspath->data);
+
+      aspath->data = newdata;
+      aspath->length += AS_HEADER_SIZE + AS_VALUE_SIZE;
+    }
+
+  return aspath;
+}
+
+/* Add specified AS to the leftmost of aspath. */
+struct aspath *
+aspath_add_seq (struct aspath *aspath, as_t asno)
+{
+  return aspath_add_one_as (aspath, asno, AS_SEQUENCE);
+}
+
+/* Compare leftmost AS value for MED check.  If as1's leftmost AS and
+   as2's leftmost AS is same return 1. */
+int
+aspath_cmp_left (struct aspath *aspath1, struct aspath *aspath2)
+{
+  struct assegment *seg1;
+  struct assegment *seg2;
+  as_t as1;
+  as_t as2;
+
+  seg1 = (struct assegment *) aspath1->data;
+  seg2 = (struct assegment *) aspath2->data;
+
+  while (seg1 && seg1->length 
+	 && (seg1->type == AS_CONFED_SEQUENCE || seg1->type == AS_CONFED_SET))
+    seg1 = (struct assegment *) ((caddr_t) seg1 + ASSEGMENT_LEN (seg1));
+  while (seg2 && seg2->length 
+	 && (seg2->type == AS_CONFED_SEQUENCE || seg2->type == AS_CONFED_SET))
+    seg2 = (struct assegment *) ((caddr_t) seg2 + ASSEGMENT_LEN (seg2));
+
+  /* Check as1's */
+  if (seg1 == NULL || seg1->length == 0 || seg1->type != AS_SEQUENCE)
+    return 0;
+  as1 = seg1->asval[0];
+
+  if (seg2 == NULL || seg2->length == 0 || seg2->type != AS_SEQUENCE)
+    return 0;
+  as2 = seg2->asval[0];
+
+  if (as1 == as2)
+    return 1;
+
+  return 0;
+}
+
+/* Compare leftmost AS value for MED check.  If as1's leftmost AS and
+   as2's leftmost AS is same return 1. (confederation as-path
+   only).  */
+int
+aspath_cmp_left_confed (struct aspath *aspath1, struct aspath *aspath2)
+{
+  struct assegment *seg1;
+  struct assegment *seg2;
+
+  as_t as1;
+  as_t as2;
+
+  if (aspath1->count || aspath2->count) 
+    return 0;
+
+  seg1 = (struct assegment *) aspath1->data;
+  seg2 = (struct assegment *) aspath2->data;
+
+  /* Check as1's */
+  if (seg1 == NULL || seg1->length == 0 || seg1->type != AS_CONFED_SEQUENCE)
+    return 0;
+  as1 = seg1->asval[0];
+
+  /* Check as2's */
+  if (seg2 == NULL || seg2->length == 0 || seg2->type != AS_CONFED_SEQUENCE)
+    return 0;
+  as2 = seg2->asval[0];
+
+  if (as1 == as2)
+    return 1;
+
+  return 0;
+}
+
+/* Delete first sequential AS_CONFED_SEQUENCE from aspath.  */
+struct aspath *
+aspath_delete_confed_seq (struct aspath *aspath)
+{
+  int seglen;
+  struct assegment *assegment;
+
+  if (! aspath)
+    return aspath;
+
+  assegment = (struct assegment *) aspath->data;
+
+  while (assegment)
+    {
+      if (assegment->type != AS_CONFED_SEQUENCE)
+	return aspath;
+
+      seglen = ASSEGMENT_LEN (assegment);
+
+      if (seglen == aspath->length)
+	{
+	  XFREE (MTYPE_AS_SEG, aspath->data);
+	  aspath->data = NULL;
+	  aspath->length = 0;
+	}
+      else
+	{
+	  memcpy (aspath->data, aspath->data + seglen,
+		  aspath->length - seglen);
+	  aspath->data = XREALLOC (MTYPE_AS_SEG, aspath->data,
+				   aspath->length - seglen);
+	  aspath->length -= seglen;
+	}
+
+      assegment = (struct assegment *) aspath->data;
+    }
+  return aspath;
+}
+
+/* Add new AS number to the leftmost part of the aspath as
+   AS_CONFED_SEQUENCE.  */
+struct aspath*
+aspath_add_confed_seq (struct aspath *aspath, as_t asno)
+{
+  return aspath_add_one_as (aspath, asno, AS_CONFED_SEQUENCE);
+}
+
+/* Add new as value to as path structure. */
+void
+aspath_as_add (struct aspath *as, as_t asno)
+{
+  caddr_t pnt;
+  caddr_t end;
+  struct assegment *assegment;
+
+  /* Increase as->data for new as value. */
+  as->data = XREALLOC (MTYPE_AS_SEG, as->data, as->length + 2);
+  as->length += 2;
+
+  pnt = as->data;
+  end = as->data + as->length;
+  assegment = (struct assegment *) pnt;
+
+  /* Last segment search procedure. */
+  while (pnt + 2 < end)
+    {
+      assegment = (struct assegment *) pnt;
+
+      /* We add 2 for segment_type and segment_length and segment
+         value assegment->length * 2. */
+      pnt += (AS_HEADER_SIZE + (assegment->length * AS_VALUE_SIZE));
+    }
+
+  assegment->asval[assegment->length] = htons (asno);
+  assegment->length++;
+}
+
+/* Add new as segment to the as path. */
+void
+aspath_segment_add (struct aspath *as, int type)
+{
+  struct assegment *assegment;
+
+  if (as->data == NULL)
+    {
+      as->data = XMALLOC (MTYPE_AS_SEG, 2);
+      assegment = (struct assegment *) as->data;
+      as->length = 2;
+    }
+  else
+    {
+      as->data = XREALLOC (MTYPE_AS_SEG, as->data, as->length + 2);
+      assegment = (struct assegment *) (as->data + as->length);
+      as->length += 2;
+    }
+
+  assegment->type = type;
+  assegment->length = 0;
+}
+
+struct aspath *
+aspath_empty ()
+{
+  return aspath_parse (NULL, 0);
+}
+
+struct aspath *
+aspath_empty_get ()
+{
+  struct aspath *aspath;
+
+  aspath = aspath_new ();
+  aspath->str = aspath_make_str_count (aspath);
+  return aspath;
+}
+
+unsigned long
+aspath_count ()
+{
+  return ashash->count;
+}     
+
+/* 
+   Theoretically, one as path can have:
+
+   One BGP packet size should be less than 4096.
+   One BGP attribute size should be less than 4096 - BGP header size.
+   One BGP aspath size should be less than 4096 - BGP header size -
+       BGP mandantry attribute size.
+*/
+
+/* AS path string lexical token enum. */
+enum as_token
+{
+  as_token_asval,
+  as_token_set_start,
+  as_token_set_end,
+  as_token_confed_start,
+  as_token_confed_end,
+  as_token_unknown
+};
+
+/* Return next token and point for string parse. */
+char *
+aspath_gettoken (char *buf, enum as_token *token, u_short *asno)
+{
+  char *p = buf;
+
+  /* Skip space. */
+  while (isspace ((int) *p))
+    p++;
+
+  /* Check the end of the string and type specify characters
+     (e.g. {}()). */
+  switch (*p)
+    {
+    case '\0':
+      return NULL;
+      break;
+    case '{':
+      *token = as_token_set_start;
+      p++;
+      return p;
+      break;
+    case '}':
+      *token = as_token_set_end;
+      p++;
+      return p;
+      break;
+    case '(':
+      *token = as_token_confed_start;
+      p++;
+      return p;
+      break;
+    case ')':
+      *token = as_token_confed_end;
+      p++;
+      return p;
+      break;
+    }
+
+  /* Check actual AS value. */
+  if (isdigit ((int) *p)) 
+    {
+      u_short asval;
+
+      *token = as_token_asval;
+      asval = (*p - '0');
+      p++;
+      while (isdigit ((int) *p)) 
+	{
+	  asval *= 10;
+	  asval += (*p - '0');
+	  p++;
+	}
+      *asno = asval;
+      return p;
+    }
+  
+  /* There is no match then return unknown token. */
+  *token = as_token_unknown;
+  return  p++;
+}
+
+struct aspath *
+aspath_str2aspath (char *str)
+{
+  enum as_token token;
+  u_short as_type;
+  u_short asno;
+  struct aspath *aspath;
+  int needtype;
+
+  aspath = aspath_new ();
+
+  /* We start default type as AS_SEQUENCE. */
+  as_type = AS_SEQUENCE;
+  needtype = 1;
+
+  while ((str = aspath_gettoken (str, &token, &asno)) != NULL)
+    {
+      switch (token)
+	{
+	case as_token_asval:
+	  if (needtype)
+	    {
+	      aspath_segment_add (aspath, as_type);
+	      needtype = 0;
+	    }
+	  aspath_as_add (aspath, asno);
+	  break;
+	case as_token_set_start:
+	  as_type = AS_SET;
+	  aspath_segment_add (aspath, as_type);
+	  needtype = 0;
+	  break;
+	case as_token_set_end:
+	  as_type = AS_SEQUENCE;
+	  needtype = 1;
+	  break;
+	case as_token_confed_start:
+	  as_type = AS_CONFED_SEQUENCE;
+	  aspath_segment_add (aspath, as_type);
+	  needtype = 0;
+	  break;
+	case as_token_confed_end:
+	  as_type = AS_SEQUENCE;
+	  needtype = 1;
+	  break;
+	case as_token_unknown:
+	default:
+	  return NULL;
+	  break;
+	}
+    }
+
+  aspath->str = aspath_make_str_count (aspath);
+
+  return aspath;
+}
+
+/* Make hash value by raw aspath data. */
+unsigned int
+aspath_key_make (struct aspath *aspath)
+{
+  unsigned int key = 0;
+  int length;
+  unsigned short *pnt;
+
+  length = aspath->length / 2;
+  pnt = (unsigned short *) aspath->data;
+
+  while (length)
+    {
+      key += *pnt++;
+      length--;
+    }
+
+  return key;
+}
+
+/* If two aspath have same value then return 1 else return 0 */
+int
+aspath_cmp (struct aspath *as1, struct aspath *as2)
+{
+  if (as1->length == as2->length 
+      && !memcmp (as1->data, as2->data, as1->length))
+    return 1;
+  else
+    return 0;
+}
+
+/* AS path hash initialize. */
+void
+aspath_init ()
+{
+  ashash = hash_create_size (32767, aspath_key_make, aspath_cmp);
+}
+
+/* return and as path value */
+const char *
+aspath_print (struct aspath *as)
+{
+  return as->str;
+}
+
+/* Printing functions */
+void
+aspath_print_vty (struct vty *vty, struct aspath *as)
+{
+  vty_out (vty, "%s", as->str);
+}
+
+void
+aspath_show_all_iterator (struct hash_backet *backet, struct vty *vty)
+{
+  struct aspath *as;
+
+  as = (struct aspath *) backet->data;
+
+  vty_out (vty, "[%p:%d] (%ld) ", backet, backet->key, as->refcnt);
+  vty_out (vty, "%s%s", as->str, VTY_NEWLINE);
+}
+
+/* Print all aspath and hash information.  This function is used from
+   `show ip bgp paths' command. */
+void
+aspath_print_all_vty (struct vty *vty)
+{
+  hash_iterate (ashash, 
+		(void (*) (struct hash_backet *, void *))
+		aspath_show_all_iterator,
+		vty);
+}