bgp_aspath.c

大名鼎鼎的路由器源码。程序分ZEBRA、OSPFRIP等3个包。程序框架采用一个路由协议一个进程的方式

/* 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;