bgp_aspath.c

linux 路由软件 可支持RIP OSPF BGP等

  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);
}