[thirdparty/bird.git] / nest / a-path.c

/*
 *	BIRD -- Path Operations
 *
 *	(c) 2000 Martin Mares <mj@ucw.cz>
 *	(c) 2000 Pavel Machek <pavel@ucw.cz>
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 */

#include "nest/bird.h"
#include "nest/route.h"
#include "nest/attrs.h"
#include "lib/resource.h"
#include "lib/unaligned.h"
#include "lib/string.h"


/* Global AS4 support, shared by all BGP instances.
 * This specifies whether BA_AS_PATH attributes contain 2 or 4 B per ASN
 */

int bgp_as4_support = 1;

static void
put_as(byte *data, u32 as)
{
  if (bgp_as4_support)
    put_u32(data, as);
  else if (as <= 0xFFFF)
    put_u16(data, as);
  else
    bug("put_as: Try to put 32bit AS to 16bit AS Path");
}

static inline u32
get_as(byte *data)
{
  return bgp_as4_support ? get_u32(data) : get_u16(data);
}

struct adata *
as_path_prepend(struct linpool *pool, struct adata *olda, u32 as)
{
  int bs = bgp_as4_support ? 4 : 2;
  struct adata *newa;

  if (olda->length && olda->data[0] == AS_PATH_SEQUENCE && olda->data[1] < 255)
    /* Starting with sequence => just prepend the AS number */
    {
      int nl = olda->length + bs;
      newa = lp_alloc(pool, sizeof(struct adata) + nl);
      newa->length = nl;
      newa->data[0] = AS_PATH_SEQUENCE;
      newa->data[1] = olda->data[1] + 1;
      memcpy(newa->data + bs + 2, olda->data + 2, olda->length - 2);
    }
  else /* Create new path segment */
    {
      int nl = olda->length + bs + 2;
      newa = lp_alloc(pool, sizeof(struct adata) + nl);
      newa->length = nl;
      newa->data[0] = AS_PATH_SEQUENCE;
      newa->data[1] = 1;
      memcpy(newa->data + bs + 2, olda->data, olda->length);
    }
  put_as(newa->data + 2, as);
  return newa;
}

int
as_path_convert_to_old(struct adata *path, byte *dst, int *new_used)
{
  byte *src = path->data;
  byte *src_end = src + path->length;
  byte *dst_start = dst;
  u32 as;
  int i, n;
  *new_used = 0;

  while (src < src_end)
    {
      n = src[1];
      *dst++ = *src++;
      *dst++ = *src++;

      for(i=0; i<n; i++)
	{
	  as = get_u32(src);
	  if (as > 0xFFFF) 
	    {
	      as = AS_TRANS;
	      *new_used = 1;
	    }
	  put_u16(dst, as);
	  src += 4;
	  dst += 2;
	}
    }

  return dst - dst_start;
}

int
as_path_convert_to_new(struct adata *path, byte *dst, int req_as)
{
  byte *src = path->data;
  byte *src_end = src + path->length;
  byte *dst_start = dst;
  u32 as;
  int i, t, n;


  while ((src < src_end) && (req_as > 0))
    {
      t = *src++;
      n = *src++;

      if (t == AS_PATH_SEQUENCE)
	{
	  if (n > req_as)
	    n = req_as;

	  req_as -= n;
	}
      else // t == AS_PATH_SET
	req_as--;

      *dst++ = t;
      *dst++ = n;

      for(i=0; i<n; i++)
	{
	  as = get_u16(src);
	  put_u32(dst, as);
	  src += 2;
	  dst += 4;
	}
    }

  return dst - dst_start;
}

void
as_path_format(struct adata *path, byte *buf, unsigned int size)
{
  int bs = bgp_as4_support ? 4 : 2;
  byte *p = path->data;
  byte *e = p + path->length;
  byte *end = buf + size - 16;
  int sp = 1;
  int l, isset;

  while (p < e)
    {
      if (buf > end)
	{
	  strcpy(buf, " ...");
	  return;
	}
      isset = (*p++ == AS_PATH_SET);
      l = *p++;
      if (isset)
	{
	  if (!sp)
	    *buf++ = ' ';
	  *buf++ = '{';
	  sp = 0;
	}
      while (l-- && buf <= end)
	{
	  if (!sp)
	    *buf++ = ' ';
	  buf += bsprintf(buf, "%u", get_as(p));
	  p += bs;
	  sp = 0;
	}
      if (isset)
	{
	  *buf++ = ' ';
	  *buf++ = '}';
	  sp = 0;
	}
    }
  *buf = 0;
}

int
as_path_getlen(struct adata *path)
{
  int bs = bgp_as4_support ? 4 : 2;
  int res = 0;
  u8 *p = path->data;
  u8 *q = p+path->length;
  int len;

  while (p<q)
    {
      switch (*p++)
	{
	case AS_PATH_SET:      len = *p++; res++;      p += bs * len; break;
	case AS_PATH_SEQUENCE: len = *p++; res += len; p += bs * len; break;
	default: bug("as_path_getlen: Invalid path segment");
	}
    }
  return res;
}

int
as_path_get_first(struct adata *path, u32 *orig_as)
{
  int bs = bgp_as4_support ? 4 : 2;
  int found = 0;
  u32 res = 0;
  u8 *p = path->data;
  u8 *q = p+path->length;
  int len;

  while (p<q)
    {
      switch (*p++)
	{
	case AS_PATH_SET:
	  if (len = *p++)
	    {
	      found = 1;
	      res = get_as(p);
	      p += bs * len;
	    }
	  break;
	case AS_PATH_SEQUENCE:
	  if (len = *p++)
	    {
	      found = 1;
	      res = get_as(p + bs * (len - 1));
	      p += bs * len;
	    }
	  break;
	default: bug("as_path_get_first: Invalid path segment");
	}
    }

  *orig_as = res;
  return found;
}

int
as_path_get_last(struct adata *path, u32 *last_as)
{
  u8 *p = path->data;

  if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0))
    return 0;
  else
    {
      *last_as = get_as(p+2);
      return 1;
    }
}

int
as_path_is_member(struct adata *path, u32 as)
{
  int bs = bgp_as4_support ? 4 : 2;
  u8 *p = path->data;
  u8 *q = p+path->length;
  int i, n;

  while (p<q)
    {
      n = p[1];
      p += 2;
      for(i=0; i<n; i++)
	{
	  if (get_as(p) == as)
	    return 1;
	  p += bs;
	}
    }
  return 0;
}


struct pm_pos
{
  u8 set;
  u8 mark;
  union
  {
    char *sp;
    u32 asn;
  } val;
};

static int
parse_path(struct adata *path, struct pm_pos *pos)
{
  int bs = bgp_as4_support ? 4 : 2;
  u8 *p = path->data;
  u8 *q = p + path->length;
  struct pm_pos *opos = pos;
  int i, j, len;


  while (p < q)
    switch (*p++)
      {
      case AS_PATH_SET:
	pos->set = 1;
	pos->mark = 0;
	pos->val.sp = p;
	len = *p;
	p += 1 + bs * len;
	pos++;
	break;
      
      case AS_PATH_SEQUENCE:
	len = *p++;
	for (i = 0; i < len; i++)
	  {
	    pos->set = 0;
	    pos->mark = 0;
	    pos->val.asn = get_as(p);
	    p += bs;
	    pos++;
	  }
	break;

      default:
	bug("as_path_match: Invalid path component");
      }
  
  return pos - opos;
}


static int
pm_match(struct pm_pos *pos, u32 asn)
{
  if (! pos->set)
    return pos->val.asn == asn;

  int bs = bgp_as4_support ? 4 : 2;
  u8 *p = pos->val.sp;
  int len = *p++;
  int i;

  for (i = 0; i < len; i++)
    if (get_as(p + i * bs) == asn)
      return 1;

  return 0;
}

static void
pm_mark(struct pm_pos *pos, int i, int plen, int *nl, int *nh)
{
  int j;

  if (pos[i].set)
    pos[i].mark = 1;
  
  for (j = i + 1; (j < plen) && pos[j].set && (! pos[j].mark); j++)
    pos[j].mark = 1;
  pos[j].mark = 1;

  /* We are going downwards, therefore every mark is
     new low and just the first mark is new high */

  *nl = i + (pos[i].set ? 0 : 1);

  if (*nh < 0)
    *nh = j;
}

/* AS path matching is nontrivial. Because AS path can
 * contain sets, it is not a plain wildcard matching. A set 
 * in an AS path is interpreted as it might represent any
 * sequence of AS numbers from that set (possibly with
 * repetitions). So it is also a kind of a pattern,
 * more complicated than a path mask.
 *
 * The algorithm for AS path matching is a variant
 * of nondeterministic finite state machine, where
 * positions in AS path are states, and items in
 * path mask are input for that finite state machine.
 * During execution of the algorithm we maintain a set
 * of marked states - a state is marked if it can be
 * reached by any walk through NFSM with regard to
 * currently processed part of input. When we process
 * next part of mask, we advance each marked state.
 * We start with marked first position, when we
 * run out of marked positions, we reject. When
 * we process the whole mask, we accept iff final position
 * (auxiliary position after last real position in AS path)
 * is marked.
 */

int
as_path_match(struct adata *path, struct f_path_mask *mask)
{
  struct pm_pos pos[2048 + 1];
  int plen = parse_path(path, pos);
  int l, h, i, nh, nl;

  /* l and h are bound of interval of positions where
     are marked states */

  pos[plen].set = 0;
  pos[plen].mark = 0;

  l = h = 0;
  pos[0].mark = 1;
  
  while (mask)
    {
      /* We remove this mark to not step after pos[plen] */
      pos[plen].mark = 0;

      switch (mask->kind)
	{
	case PM_ASTERISK:
	  for (i = l; i <= plen; i++)
	    pos[i].mark = 1;
	  h = plen;
	  break;

	case PM_QUESTION:
	case PM_ASN:
	  nh = -1;
	  for (i = h; i >= l; i--)
	    if (pos[i].mark)
	      {
		pos[i].mark = 0;
		if ((mask->kind == PM_QUESTION) || pm_match(pos + i, mask->val))
		  pm_mark(pos, i, plen, &nl, &nh);
	      }

	  if (nh < 0)
	    return 0;

	  h = nh;
	  l = nl;
	  break;
	}

      mask = mask->next;
    }

  return pos[plen].mark;
}
Commit	Line	Data
c0668f36 MM	1	/*
	2	* BIRD -- Path Operations
	3	*
	4	* (c) 2000 Martin Mares <mj@ucw.cz>
	5	* (c) 2000 Pavel Machek <pavel@ucw.cz>
	6	*
	7	* Can be freely distributed and used under the terms of the GNU GPL.
	8	*/
	9
	10	#include "nest/bird.h"
	11	#include "nest/route.h"
c6add07f	12	#include "nest/attrs.h"
c0668f36 MM	13	#include "lib/resource.h"
c0668f36 MM	14	#include "lib/unaligned.h"
c6add07f	15	#include "lib/string.h"
c0668f36	16
11cb6202 OZ	17
	18	/* Global AS4 support, shared by all BGP instances.
	19	* This specifies whether BA_AS_PATH attributes contain 2 or 4 B per ASN
	20	*/
	21
	22	int bgp_as4_support = 1;
	23
	24	static void
	25	put_as(byte *data, u32 as)
	26	{
	27	if (bgp_as4_support)
	28	put_u32(data, as);
	29	else if (as <= 0xFFFF)
	30	put_u16(data, as);
	31	else
	32	bug("put_as: Try to put 32bit AS to 16bit AS Path");
	33	}
	34
	35	static inline u32
	36	get_as(byte *data)
	37	{
	38	return bgp_as4_support ? get_u32(data) : get_u16(data);
	39	}
	40
c0668f36	41	struct adata *
11cb6202	42	as_path_prepend(struct linpool pool, struct adata olda, u32 as)
c0668f36	43	{
11cb6202	44	int bs = bgp_as4_support ? 4 : 2;
c0668f36 MM	45	struct adata *newa;
c0668f36 MM	46
11cb6202 OZ	47	if (olda->length && olda->data[0] == AS_PATH_SEQUENCE && olda->data[1] < 255)
11cb6202 OZ	48	/* Starting with sequence => just prepend the AS number */
c0668f36	49	{
11cb6202 OZ	50	int nl = olda->length + bs;
	51	newa = lp_alloc(pool, sizeof(struct adata) + nl);
	52	newa->length = nl;
	53	newa->data[0] = AS_PATH_SEQUENCE;
c0668f36	54	newa->data[1] = olda->data[1] + 1;
11cb6202	55	memcpy(newa->data + bs + 2, olda->data + 2, olda->length - 2);
c0668f36	56	}
11cb6202	57	else /* Create new path segment */
c0668f36	58	{
11cb6202 OZ	59	int nl = olda->length + bs + 2;
	60	newa = lp_alloc(pool, sizeof(struct adata) + nl);
	61	newa->length = nl;
	62	newa->data[0] = AS_PATH_SEQUENCE;
c0668f36	63	newa->data[1] = 1;
11cb6202	64	memcpy(newa->data + bs + 2, olda->data, olda->length);
c0668f36	65	}
11cb6202	66	put_as(newa->data + 2, as);
c0668f36 MM	67	return newa;
c0668f36 MM	68	}
c6add07f	69
11cb6202 OZ	70	int
	71	as_path_convert_to_old(struct adata path, byte dst, int *new_used)
	72	{
	73	byte *src = path->data;
	74	byte *src_end = src + path->length;
	75	byte *dst_start = dst;
	76	u32 as;
	77	int i, n;
	78	*new_used = 0;
	79
	80	while (src < src_end)
	81	{
	82	n = src[1];
	83	dst++ = src++;
	84	dst++ = src++;
	85
	86	for(i=0; i<n; i++)
	87	{
	88	as = get_u32(src);
	89	if (as > 0xFFFF)
	90	{
	91	as = AS_TRANS;
	92	*new_used = 1;
	93	}
	94	put_u16(dst, as);
	95	src += 4;
	96	dst += 2;
	97	}
	98	}
	99
	100	return dst - dst_start;
	101	}
	102
	103	int
	104	as_path_convert_to_new(struct adata path, byte dst, int req_as)
	105	{
	106	byte *src = path->data;
	107	byte *src_end = src + path->length;
	108	byte *dst_start = dst;
	109	u32 as;
	110	int i, t, n;
	111
	112
	113	while ((src < src_end) && (req_as > 0))
	114	{
	115	t = *src++;
	116	n = *src++;
	117
	118	if (t == AS_PATH_SEQUENCE)
	119	{
	120	if (n > req_as)
	121	n = req_as;
	122
	123	req_as -= n;
	124	}
	125	else // t == AS_PATH_SET
	126	req_as--;
	127
	128	*dst++ = t;
	129	*dst++ = n;
	130
	131	for(i=0; i<n; i++)
	132	{
	133	as = get_u16(src);
134	put_u32(dst, as);
135	src += 2;
136	dst += 4;
137	}
138	}
139
140	return dst - dst_start;
141	}
142
c6add07f MM	143	void
	144	as_path_format(struct adata path, byte buf, unsigned int size)
	145	{
11cb6202	146	int bs = bgp_as4_support ? 4 : 2;
c6add07f	147	byte *p = path->data;
987de545	148	byte *e = p + path->length;
11cb6202	149	byte *end = buf + size - 16;
c6add07f	150	int sp = 1;
93a786cb	151	int l, isset;
c6add07f MM	152
	153	while (p < e)
	154	{
	155	if (buf > end)
	156	{
	157	strcpy(buf, " ...");
	158	return;
	159	}
	160	isset = (*p++ == AS_PATH_SET);
	161	l = *p++;
	162	if (isset)
	163	{
	164	if (!sp)
	165	*buf++ = ' ';
	166	*buf++ = '{';
	167	sp = 0;
	168	}
	169	while (l-- && buf <= end)
	170	{
	171	if (!sp)
	172	*buf++ = ' ';
11cb6202 OZ	173	buf += bsprintf(buf, "%u", get_as(p));
11cb6202 OZ	174	p += bs;
c6add07f MM	175	sp = 0;
	176	}
	177	if (isset)
	178	{
	179	*buf++ = ' ';
	180	*buf++ = '}';
	181	sp = 0;
	182	}
	183	}
	184	*buf = 0;
	185	}
684c6f5a PM	186
	187	int
	188	as_path_getlen(struct adata *path)
	189	{
11cb6202	190	int bs = bgp_as4_support ? 4 : 2;
684c6f5a PM	191	int res = 0;
	192	u8 *p = path->data;
	193	u8 *q = p+path->length;
	194	int len;
	195
4b03f64b MM	196	while (p<q)
	197	{
	198	switch (*p++)
	199	{
11cb6202 OZ	200	case AS_PATH_SET: len = p++; res++; p += bs len; break;
11cb6202 OZ	201	case AS_PATH_SEQUENCE: len = p++; res += len; p += bs len; break;
4b03f64b MM	202	default: bug("as_path_getlen: Invalid path segment");
4b03f64b MM	203	}
684c6f5a	204	}
684c6f5a PM	205	return res;
684c6f5a PM	206	}
2a40efa5	207
f49528a3	208	int
11cb6202	209	as_path_get_first(struct adata path, u32 orig_as)
f49528a3	210	{
11cb6202 OZ	211	int bs = bgp_as4_support ? 4 : 2;
	212	int found = 0;
	213	u32 res = 0;
f49528a3 MM	214	u8 *p = path->data;
	215	u8 *q = p+path->length;
	216	int len;
	217
	218	while (p<q)
	219	{
	220	switch (*p++)
	221	{
	222	case AS_PATH_SET:
	223	if (len = *p++)
11cb6202 OZ	224	{
	225	found = 1;
	226	res = get_as(p);
	227	p += bs * len;
	228	}
f49528a3 MM	229	break;
	230	case AS_PATH_SEQUENCE:
	231	if (len = *p++)
11cb6202 OZ	232	{
	233	found = 1;
	234	res = get_as(p + bs * (len - 1));
	235	p += bs * len;
	236	}
f49528a3 MM	237	break;
	238	default: bug("as_path_get_first: Invalid path segment");
	239	}
	240	}
11cb6202 OZ	241
	242	*orig_as = res;
	243	return found;
f49528a3 MM	244	}
f49528a3 MM	245
b6bf284a OZ	246	int
	247	as_path_get_last(struct adata path, u32 last_as)
	248	{
	249	u8 *p = path->data;
	250
	251	if ((path->length == 0) \|\| (p[0] != AS_PATH_SEQUENCE) \|\| (p[1] == 0))
	252	return 0;
	253	else
	254	{
	255	*last_as = get_as(p+2);
	256	return 1;
	257	}
	258	}
	259
11cb6202 OZ	260	int
	261	as_path_is_member(struct adata *path, u32 as)
	262	{
	263	int bs = bgp_as4_support ? 4 : 2;
	264	u8 *p = path->data;
	265	u8 *q = p+path->length;
	266	int i, n;
	267
	268	while (p<q)
	269	{
	270	n = p[1];
	271	p += 2;
	272	for(i=0; i<n; i++)
	273	{
	274	if (get_as(p) == as)
	275	return 1;
	276	p += bs;
	277	}
	278	}
	279	return 0;
	280	}
	281
	282
c8a6b9a3 OZ	283	struct pm_pos
	284	{
	285	u8 set;
	286	u8 mark;
	287	union
	288	{
	289	char *sp;
	290	u32 asn;
	291	} val;
	292	};
	293
	294	static int
	295	parse_path(struct adata path, struct pm_pos pos)
2a40efa5	296	{
11cb6202	297	int bs = bgp_as4_support ? 4 : 2;
2a40efa5	298	u8 *p = path->data;
c8a6b9a3 OZ	299	u8 *q = p + path->length;
	300	struct pm_pos *opos = pos;
	301	int i, j, len;
2a40efa5	302
25cb9f1d	303
c8a6b9a3 OZ	304	while (p < q)
c8a6b9a3 OZ	305	switch (*p++)
2a40efa5	306	{
c8a6b9a3 OZ	307	case AS_PATH_SET:
	308	pos->set = 1;
	309	pos->mark = 0;
	310	pos->val.sp = p;
	311	len = *p;
	312	p += 1 + bs * len;
	313	pos++;
	314	break;
	315
	316	case AS_PATH_SEQUENCE:
	317	len = *p++;
	318	for (i = 0; i < len; i++)
	319	{
	320	pos->set = 0;
	321	pos->mark = 0;
	322	pos->val.asn = get_as(p);
	323	p += bs;
	324	pos++;
2a40efa5	325	}
c8a6b9a3 OZ	326	break;
	327
	328	default:
	329	bug("as_path_match: Invalid path component");
2a40efa5	330	}
c8a6b9a3 OZ	331
	332	return pos - opos;
	333	}
	334
	335
	336	static int
	337	pm_match(struct pm_pos *pos, u32 asn)
	338	{
	339	if (! pos->set)
	340	return pos->val.asn == asn;
	341
	342	int bs = bgp_as4_support ? 4 : 2;
	343	u8 *p = pos->val.sp;
	344	int len = *p++;
	345	int i;
	346
	347	for (i = 0; i < len; i++)
	348	if (get_as(p + i * bs) == asn)
	349	return 1;
	350
	351	return 0;
	352	}
	353
	354	static void
	355	pm_mark(struct pm_pos pos, int i, int plen, int nl, int *nh)
	356	{
	357	int j;
	358
	359	if (pos[i].set)
	360	pos[i].mark = 1;
	361
	362	for (j = i + 1; (j < plen) && pos[j].set && (! pos[j].mark); j++)
	363	pos[j].mark = 1;
	364	pos[j].mark = 1;
	365
	366	/* We are going downwards, therefore every mark is
	367	new low and just the first mark is new high */
	368
	369	*nl = i + (pos[i].set ? 0 : 1);
	370
	371	if (*nh < 0)
	372	*nh = j;
	373	}
	374
	375	/* AS path matching is nontrivial. Because AS path can
	376	* contain sets, it is not a plain wildcard matching. A set
	377	* in an AS path is interpreted as it might represent any
	378	* sequence of AS numbers from that set (possibly with
	379	* repetitions). So it is also a kind of a pattern,
	380	* more complicated than a path mask.
	381	*
	382	* The algorithm for AS path matching is a variant
	383	* of nondeterministic finite state machine, where
	384	* positions in AS path are states, and items in
	385	* path mask are input for that finite state machine.
	386	* During execution of the algorithm we maintain a set
	387	* of marked states - a state is marked if it can be
	388	* reached by any walk through NFSM with regard to
	389	* currently processed part of input. When we process
	390	* next part of mask, we advance each marked state.
	391	* We start with marked first position, when we
	392	* run out of marked positions, we reject. When
	393	* we process the whole mask, we accept iff final position
	394	* (auxiliary position after last real position in AS path)
395	* is marked.
396	*/
397
398	int
399	as_path_match(struct adata path, struct f_path_mask mask)
400	{
401	struct pm_pos pos[2048 + 1];
402	int plen = parse_path(path, pos);
403	int l, h, i, nh, nl;
404
405	/* l and h are bound of interval of positions where
406	are marked states */
407
408	pos[plen].set = 0;
409	pos[plen].mark = 0;
410
411	l = h = 0;
412	pos[0].mark = 1;
413
414	while (mask)
415	{
416	/* We remove this mark to not step after pos[plen] */
417	pos[plen].mark = 0;
418
419	switch (mask->kind)
420	{
421	case PM_ASTERISK:
422	for (i = l; i <= plen; i++)
423	pos[i].mark = 1;
424	h = plen;
425	break;
426
427	case PM_QUESTION:
428	case PM_ASN:
429	nh = -1;
430	for (i = h; i >= l; i--)
431	if (pos[i].mark)
432	{
433	pos[i].mark = 0;
434	if ((mask->kind == PM_QUESTION) \|\| pm_match(pos + i, mask->val))
435	pm_mark(pos, i, plen, &nl, &nh);
436	}
437
438	if (nh < 0)
2a40efa5	439	return 0;
c8a6b9a3 OZ	440
	441	h = nh;
	442	l = nl;
	443	break;
2a40efa5	444	}
2a40efa5	445
c8a6b9a3	446	mask = mask->next;
2a40efa5	447	}
98347659	448
c8a6b9a3 OZ	449	return pos[plen].mark;
c8a6b9a3 OZ	450	}