a-path.c 9.33 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11
/*
 *	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"
12
#include "nest/attrs.h"
13 14
#include "lib/resource.h"
#include "lib/unaligned.h"
15
#include "lib/string.h"
Ondřej Zajíček's avatar
Ondřej Zajíček committed
16
#include "filter/filter.h"
17

18 19
// static inline void put_as(byte *data, u32 as) { put_u32(data, as); }
// static inline u32 get_as(byte *data) { return get_u32(data); }
20

21 22 23
#define put_as put_u32
#define get_as get_u32
#define BS  4
24

25
struct adata *
26
as_path_prepend(struct linpool *pool, struct adata *olda, u32 as)
27 28 29
{
  struct adata *newa;

30 31
  if (olda->length && olda->data[0] == AS_PATH_SEQUENCE && olda->data[1] < 255)
    /* Starting with sequence => just prepend the AS number */
32
    {
33
      int nl = olda->length + BS;
34 35 36
      newa = lp_alloc(pool, sizeof(struct adata) + nl);
      newa->length = nl;
      newa->data[0] = AS_PATH_SEQUENCE;
37
      newa->data[1] = olda->data[1] + 1;
38
      memcpy(newa->data + BS + 2, olda->data + 2, olda->length - 2);
39
    }
40
  else /* Create new path segment */
41
    {
42
      int nl = olda->length + BS + 2;
43 44 45
      newa = lp_alloc(pool, sizeof(struct adata) + nl);
      newa->length = nl;
      newa->data[0] = AS_PATH_SEQUENCE;
46
      newa->data[1] = 1;
47
      memcpy(newa->data + BS + 2, olda->data, olda->length);
48
    }
49
  put_as(newa->data + 2, as);
50 51
  return newa;
}
52

53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
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;
}

126 127 128 129
void
as_path_format(struct adata *path, byte *buf, unsigned int size)
{
  byte *p = path->data;
130
  byte *e = p + path->length;
131
  byte *end = buf + size - 16;
132
  int sp = 1;
133
  int l, isset;
134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154

  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++ = ' ';
155
	  buf += bsprintf(buf, "%u", get_as(p));
156
	  p += BS;
157 158 159 160 161 162 163 164 165 166 167
	  sp = 0;
	}
      if (isset)
	{
	  *buf++ = ' ';
	  *buf++ = '}';
	  sp = 0;
	}
    }
  *buf = 0;
}
168 169 170 171

int
as_path_getlen(struct adata *path)
{
172
  return as_path_getlen_int(path, BS);
173 174 175 176 177
}

int
as_path_getlen_int(struct adata *path, int bs)
{
178 179 180 181 182
  int res = 0;
  u8 *p = path->data;
  u8 *q = p+path->length;
  int len;

183 184 185 186
  while (p<q)
    {
      switch (*p++)
	{
187 188
	case AS_PATH_SET:      len = *p++; res++;      p += bs * len; break;
	case AS_PATH_SEQUENCE: len = *p++; res += len; p += bs * len; break;
189 190
	default: bug("as_path_getlen: Invalid path segment");
	}
191 192 193
    }
  return res;
}
194

195
int
196
as_path_get_last(struct adata *path, u32 *orig_as)
197
{
198 199
  int found = 0;
  u32 res = 0;
200 201 202 203 204 205 206 207 208 209
  u8 *p = path->data;
  u8 *q = p+path->length;
  int len;

  while (p<q)
    {
      switch (*p++)
	{
	case AS_PATH_SET:
	  if (len = *p++)
210
	    {
211
	      found = 0;
212
	      p += BS * len;
213
	    }
214 215 216
	  break;
	case AS_PATH_SEQUENCE:
	  if (len = *p++)
217 218
	    {
	      found = 1;
219 220
	      res = get_as(p + BS * (len - 1));
	      p += BS * len;
221
	    }
222 223 224 225
	  break;
	default: bug("as_path_get_first: Invalid path segment");
	}
    }
226

227 228
  if (found)
    *orig_as = res;
229
  return found;
230 231
}

232
int
233
as_path_get_first(struct adata *path, u32 *last_as)
234 235 236 237 238 239 240 241 242 243 244 245
{
  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;
    }
}

246
int
247
as_path_contains(struct adata *path, u32 as, int min)
248 249 250
{
  u8 *p = path->data;
  u8 *q = p+path->length;
251
  int num = 0;
252 253 254 255 256 257 258 259 260
  int i, n;

  while (p<q)
    {
      n = p[1];
      p += 2;
      for(i=0; i<n; i++)
	{
	  if (get_as(p) == as)
261 262
	    if (++num == min)
	      return 1;
263
	  p += BS;
264 265 266 267 268
	}
    }
  return 0;
}

269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291
int
as_path_match_set(struct adata *path, struct f_tree *set)
{
  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++)
	{
	  struct f_val v = {T_INT, .val.i = get_as(p)};
	  if (find_tree(set, v))
	    return 1;
	  p += BS;
	}
    }

  return 0;
}

292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354
struct adata *
as_path_filter(struct linpool *pool, struct adata *path, struct f_tree *set, u32 key, int pos)
{
  if (!path)
    return NULL;

  int len = path->length;
  u8 *p = path->data;
  u8 *q = path->data + len;
  u8 *d, *d2;
  int i, bt, sn, dn;
  u8 buf[len];

  d = buf;
  while (p<q)
    {
      /* Read block header (type and length) */
      bt = p[0];
      sn = p[1];
      dn = 0;
      p += 2;
      d2 = d + 2;

      for (i = 0; i < sn; i++)
	{
	  u32 as = get_as(p);
	  int match;

	  if (set)
	    match = !!find_tree(set, (struct f_val){T_INT, .val.i = as});
	  else
	    match = (as == key);

	  if (match == pos)
	    {
	      put_as(d2, as);
	      d2 += BS;
	      dn++;
	    }

	  p += BS;
	}

      if (dn > 0)
	{
	  /* Nonempty block, set block header and advance */
	  d[0] = bt;
	  d[1] = dn;
	  d = d2;
	}
  }

  int nl = d - buf;
  if (nl == path->length)
    return path;

  struct adata *res = lp_alloc(pool, sizeof(struct adata) + nl);
  res->length = nl;
  memcpy(res->data, buf, nl);

  return res;
}

355

356 357 358 359 360 361 362 363 364 365 366 367 368
struct pm_pos
{
  u8 set;
  u8 mark;
  union
  {
    char *sp;
    u32 asn;
  } val;
};

static int
parse_path(struct adata *path, struct pm_pos *pos)
369 370
{
  u8 *p = path->data;
371 372
  u8 *q = p + path->length;
  struct pm_pos *opos = pos;
Ondřej Zajíček's avatar
Ondřej Zajíček committed
373
  int i, len;
374

375

376 377
  while (p < q)
    switch (*p++)
378
      {
379 380 381 382 383
      case AS_PATH_SET:
	pos->set = 1;
	pos->mark = 0;
	pos->val.sp = p;
	len = *p;
384
	p += 1 + BS * len;
385 386 387 388 389 390 391 392 393 394
	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);
395
	    p += BS;
396
	    pos++;
397
	  }
398 399 400 401
	break;

      default:
	bug("as_path_match: Invalid path component");
402
      }
403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418
  
  return pos - opos;
}


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

  u8 *p = pos->val.sp;
  int len = *p++;
  int i;

  for (i = 0; i < len; i++)
419
    if (get_as(p + i * BS) == asn)
420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474
      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;
475
  u32 val = 0;
476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499

  /* 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_ASN:
500 501 502 503 504 505 506
	  val = mask->val;
	  goto step;
	case PM_ASN_EXPR:
	  val = f_eval_asn((struct f_inst *) mask->val);
	  goto step;
	case PM_QUESTION:
	step:
507
	  nh = nl = -1;
508 509 510 511
	  for (i = h; i >= l; i--)
	    if (pos[i].mark)
	      {
		pos[i].mark = 0;
512
		if ((mask->kind == PM_QUESTION) || pm_match(pos + i, val))
513 514 515 516
		  pm_mark(pos, i, plen, &nl, &nh);
	      }

	  if (nh < 0)
517
	    return 0;
518 519 520 521

	  h = nh;
	  l = nl;
	  break;
522 523
	}

524
      mask = mask->next;
525
    }
Pavel Machek's avatar
Pavel Machek committed
526

527 528
  return pos[plen].mark;
}