Merge branch 'ballygarvan' into HEAD

Replacing the old 3.0-alpha0 cork mechanism with another one inside the
routing table. This version should be simpler and also quite clear what
it does, why and when.

1 files changed, 0 insertions, 905 deletions

diff --git a/nest/a-path.c b/nest/a-path.c
deleted file mode 100644
index 2e34a3d1..00000000
--- a/nest/a-path.c
+++ /dev/null
@@ -1,905 +0,0 @@
-/*
- *	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"
-#include "filter/data.h"
-
-// static inline void put_as(byte *data, u32 as) { put_u32(data, as); }
-// static inline u32 get_as(byte *data) { return get_u32(data); }
-
-#define put_as put_u32
-#define get_as get_u32
-#define BS  4	/* Default block size of ASN (autonomous system number) */
-
-#define BAD(DSC, VAL) ({ err_dsc = DSC; err_val = VAL; goto bad; })
-
-int
-as_path_valid(byte *data, uint len, int bs, int sets, int confed, char *err, uint elen)
-{
-  byte *pos = data;
-  char *err_dsc = NULL;
-  uint err_val = 0;
-
-  while (len)
-  {
-    if (len < 2)
-      BAD("segment framing error", 0);
-
-    /* Process one AS path segment */
-    uint type = pos[0];
-    uint slen = 2 + bs * pos[1];
-
-    if (len < slen)
-      BAD("segment framing error", len);
-
-    switch (type)
-    {
-    case AS_PATH_SET:
-      if (!sets)
-	BAD("AS_SET segment", type);
-      break;
-
-    case AS_PATH_SEQUENCE:
-      break;
-
-    case AS_PATH_CONFED_SEQUENCE:
-      if (!confed)
-	BAD("AS_CONFED_SEQUENCE segment", type);
-      break;
-
-    case AS_PATH_CONFED_SET:
-      if (!sets || !confed)
-	BAD("AS_CONFED_SET segment", type);
-      break;
-
-    default:
-      BAD("unknown segment", type);
-    }
-
-    if (pos[1] == 0)
-      BAD("zero-length segment", type);
-
-    pos += slen;
-    len -= slen;
-  }
-
-  return 1;
-
-bad:
-  if (err)
-    if (bsnprintf(err, elen, "%s (%u) at %d", err_dsc, err_val, (int) (pos - data)) < 0)
-      err[0] = 0;
-
-  return 0;
-}
-
-int
-as_path_16to32(byte *dst, const byte *src, uint len)
-{
-  byte *dst0 = dst;
-  const byte *end = src + len;
-  uint i, n;
-
-  while (src < end)
-  {
-    n = src[1];
-    *dst++ = *src++;
-    *dst++ = *src++;
-
-    for (i = 0; i < n; i++)
-    {
-      put_u32(dst, get_u16(src));
-      src += 2;
-      dst += 4;
-    }
-  }
-
-  return dst - dst0;
-}
-
-int
-as_path_32to16(byte *dst, const byte *src, uint len)
-{
-  byte *dst0 = dst;
-  const byte *end = src + len;
-  uint i, n;
-
-  while (src < end)
-  {
-    n = src[1];
-    *dst++ = *src++;
-    *dst++ = *src++;
-
-    for (i = 0; i < n; i++)
-    {
-      put_u16(dst, get_u32(src));
-      src += 4;
-      dst += 2;
-    }
-  }
-
-  return dst - dst0;
-}
-
-int
-as_path_contains_as4(const struct adata *path)
-{
-  const byte *pos = path->data;
-  const byte *end = pos + path->length;
-  uint i, n;
-
-  while (pos < end)
-  {
-    n = pos[1];
-    pos += 2;
-
-    for (i = 0; i < n; i++)
-    {
-      if (get_as(pos) > 0xFFFF)
-	return 1;
-
-      pos += BS;
-    }
-  }
-
-  return 0;
-}
-
-int
-as_path_contains_confed(const struct adata *path)
-{
-  const byte *pos = path->data;
-  const byte *end = pos + path->length;
-
-  while (pos < end)
-  {
-    uint type = pos[0];
-    uint slen = 2 + BS * pos[1];
-
-    if ((type == AS_PATH_CONFED_SEQUENCE) ||
-	(type == AS_PATH_CONFED_SET))
-      return 1;
-
-    pos += slen;
-  }
-
-  return 0;
-}
-
-struct adata *
-as_path_strip_confed(struct linpool *pool, const struct adata *path)
-{
-  struct adata *res = lp_alloc_adata(pool, path->length);
-  const byte *src = path->data;
-  const byte *end = src + path->length;
-  byte *dst = res->data;
-
-  while (src < end)
-  {
-    uint type = src[0];
-    uint slen = 2 + BS * src[1];
-
-    /* Copy regular segments */
-    if ((type == AS_PATH_SET) || (type == AS_PATH_SEQUENCE))
-    {
-      memcpy(dst, src, slen);
-      dst += slen;
-    }
-
-    src += slen;
-  }
-
-  /* Fix the result length */
-  res->length = dst - res->data;
-
-  return res;
-}
-
-struct adata *
-as_path_prepend2(struct linpool *pool, const struct adata *op, int seq, u32 as)
-{
-  struct adata *np;
-  const byte *pos = op->data;
-  uint len = op->length;
-
-  if (len && (pos[0] == seq) && (pos[1] < 255))
-  {
-    /* Starting with matching segment => just prepend the AS number */
-    np = lp_alloc_adata(pool, len + BS);
-    np->data[0] = seq;
-    np->data[1] = pos[1] + 1;
-    put_as(np->data + 2, as);
-
-    uint dlen = BS * pos[1];
-    memcpy(np->data + 2 + BS, pos + 2, dlen);
-    ADVANCE(pos, len, 2 + dlen);
-  }
-  else
-  {
-    /* Create a new path segment */
-    np = lp_alloc_adata(pool, len + 2 + BS);
-    np->data[0] = seq;
-    np->data[1] = 1;
-    put_as(np->data + 2, as);
-  }
-
-  if (len)
-  {
-    byte *dst = np->data + 2 + BS * np->data[1];
-
-    memcpy(dst, pos, len);
-  }
-
-  return np;
-}
-
-
-struct adata *
-as_path_to_old(struct linpool *pool, const struct adata *path)
-{
-  struct adata *res = lp_alloc_adata(pool, path->length);
-  byte *pos = res->data;
-  byte *end = pos + res->length;
-  uint i, n;
-  u32 as;
-
-  /* Copy the whole path */
-  memcpy(res->data, path->data, path->length);
-
-  /* Replace 32-bit AS numbers with AS_TRANS */
-  while (pos < end)
-  {
-    n = pos[1];
-    pos += 2;
-
-    for (i = 0; i < n; i++)
-    {
-      as = get_as(pos);
-      if (as > 0xFFFF)
-	put_as(pos, AS_TRANS);
-
-      pos += BS;
-    }
-  }
-
-  return res;
-}
-
-/*
- * Cut the path to the length @num, measured to the usual path metric. Note that
- * AS_CONFED_* segments have zero length and must be added if they are on edge.
- */
-struct adata *
-as_path_cut(struct linpool *pool, const struct adata *path, uint num)
-{
-  const byte *pos = path->data;
-  const byte *end = pos + path->length;
-
-  while (pos < end)
-  {
-    uint t = pos[0];
-    uint l = pos[1];
-    uint n = 0;
-
-    switch (t)
-    {
-    case AS_PATH_SET:			n = 1; break;
-    case AS_PATH_SEQUENCE:		n = l; break;
-    case AS_PATH_CONFED_SEQUENCE:	n = 0; break;
-    case AS_PATH_CONFED_SET:		n = 0; break;
-    default: bug("as_path_cut: Invalid path segment");
-    }
-
-    /* Cannot add whole segment, so try partial one and finish */
-    if (num < n)
-    {
-      const byte *nend = pos;
-      if (num)
-	nend += 2 + BS * num;
-
-      struct adata *res = lp_alloc_adata(pool, path->length);
-      res->length = nend - (const byte *) path->data;
-      memcpy(res->data, path->data, res->length);
-
-      if (num)
-      {
-	byte *dpos = ((byte *) res->data) + (pos - (const byte *) path->data);
-	dpos[1] = num;
-      }
-
-      return res;
-    }
-
-    num -= n;
-    pos += 2 + BS * l;
-  }
-
-  struct adata *res = lp_alloc_adata(pool, path->length);
-  res->length = path->length;
-  memcpy(res->data, path->data, res->length);
-  return res;
-}
-
-/*
- * Merge (concatenate) paths @p1 and @p2 and return the result.
- * In contrast to other as_path_* functions, @p1 and @p2 may be reused.
- */
-const struct adata *
-as_path_merge(struct linpool *pool, const struct adata *p1, const struct adata *p2)
-{
-  if (p1->length == 0)
-    return p2;
-
-  if (p2->length == 0)
-    return p1;
-
-  struct adata *res = lp_alloc_adata(pool, p1->length + p2->length);
-  memcpy(res->data, p1->data, p1->length);
-  memcpy(res->data + p1->length, p2->data, p2->length);
-
-  return res;
-}
-
-void
-as_path_format(const struct adata *path, byte *bb, uint size)
-{
-  buffer buf = { .start = bb, .pos = bb, .end = bb + size }, *b = &buf;
-  const byte *pos = path->data;
-  const byte *end = pos + path->length;
-  const char *ops, *cls;
-
-  b->pos[0] = 0;
-
-  while (pos < end)
-  {
-    uint type = pos[0];
-    uint len  = pos[1];
-    pos += 2;
-
-    switch (type)
-    {
-    case AS_PATH_SET:			ops = "{";	cls = "}";	break;
-    case AS_PATH_SEQUENCE:		ops = NULL;	cls = NULL;	break;
-    case AS_PATH_CONFED_SEQUENCE:	ops = "(";	cls = ")";	break;
-    case AS_PATH_CONFED_SET:		ops = "({";	cls = "})";	break;
-    default: bug("Invalid path segment");
-    }
-
-    if (ops)
-      buffer_puts(b, ops);
-
-    while (len--)
-    {
-      buffer_print(b, len ? "%u " : "%u", get_as(pos));
-      pos += BS;
-    }
-
-    if (cls)
-      buffer_puts(b, cls);
-
-    if (pos < end)
-      buffer_puts(b, " ");
-  }
-
-  /* Handle overflow */
-  if (b->pos == b->end)
-    strcpy(b->end - 12, "...");
-}
-
-int
-as_path_getlen(const struct adata *path)
-{
-  const byte *pos = path->data;
-  const byte *end = pos + path->length;
-  uint res = 0;
-
-  while (pos < end)
-  {
-    uint t = pos[0];
-    uint l = pos[1];
-    uint n = 0;
-
-    switch (t)
-    {
-    case AS_PATH_SET:			n = 1; break;
-    case AS_PATH_SEQUENCE:		n = l; break;
-    case AS_PATH_CONFED_SEQUENCE:	n = 0; break;
-    case AS_PATH_CONFED_SET:		n = 0; break;
-    default: bug("as_path_getlen: Invalid path segment");
-    }
-
-    res += n;
-    pos += 2 + BS * l;
-  }
-
-  return res;
-}
-
-int
-as_path_get_last(const struct adata *path, u32 *orig_as)
-{
-  const byte *pos = path->data;
-  const byte *end = pos + path->length;
-  int found = 0;
-  u32 val = 0;
-
-  while (pos < end)
-  {
-    uint type = pos[0];
-    uint len  = pos[1];
-    pos += 2;
-
-    if (!len)
-      continue;
-
-    switch (type)
-    {
-    case AS_PATH_SET:
-    case AS_PATH_CONFED_SET:
-      found = 0;
-      break;
-
-    case AS_PATH_SEQUENCE:
-    case AS_PATH_CONFED_SEQUENCE:
-      val = get_as(pos + BS * (len - 1));
-      found = 1;
-      break;
-
-    default:
-      bug("Invalid path segment");
-    }
-
-    pos += BS * len;
-  }
-
-  if (found)
-    *orig_as = val;
-  return found;
-}
-
-u32
-as_path_get_last_nonaggregated(const struct adata *path)
-{
-  const byte *pos = path->data;
-  const byte *end = pos + path->length;
-  u32 val = 0;
-
-  while (pos < end)
-  {
-    uint type = pos[0];
-    uint len  = pos[1];
-    pos += 2;
-
-    if (!len)
-      continue;
-
-    switch (type)
-    {
-    case AS_PATH_SET:
-    case AS_PATH_CONFED_SET:
-      return val;
-
-    case AS_PATH_SEQUENCE:
-    case AS_PATH_CONFED_SEQUENCE:
-      val = get_as(pos + BS * (len - 1));
-      break;
-
-    default:
-      bug("Invalid path segment");
-    }
-
-    pos += BS * len;
-  }
-
-  return val;
-}
-
-int
-as_path_get_first(const struct adata *path, u32 *last_as)
-{
-  const u8 *p = path->data;
-
-  if ((path->length == 0) || (p[0] != AS_PATH_SEQUENCE) || (p[1] == 0))
-    return 0;
-
-  *last_as = get_as(p+2);
-  return 1;
-}
-
-int
-as_path_get_first_regular(const struct adata *path, u32 *last_as)
-{
-  const byte *pos = path->data;
-  const byte *end = pos + path->length;
-
-  while (pos < end)
-  {
-    uint type = pos[0];
-    uint len  = pos[1];
-    pos += 2;
-
-    switch (type)
-    {
-    case AS_PATH_SET:
-      return 0;
-
-    case AS_PATH_SEQUENCE:
-      if (len == 0)
-	return 0;
-
-      *last_as = get_as(pos);
-      return 1;
-
-    case AS_PATH_CONFED_SEQUENCE:
-    case AS_PATH_CONFED_SET:
-      break;
-
-    default:
-      bug("Invalid path segment");
-    }
-
-    pos += BS * len;
-  }
-
-  return 0;
-}
-
-int
-as_path_contains(const struct adata *path, u32 as, int min)
-{
-  const u8 *p = path->data;
-  const u8 *q = p+path->length;
-  int num = 0;
-  int i, n;
-
-  while (p<q)
-    {
-      n = p[1];
-      p += 2;
-      for(i=0; i<n; i++)
-	{
-	  if (get_as(p) == as)
-	    if (++num == min)
-	      return 1;
-	  p += BS;
-	}
-    }
-  return 0;
-}
-
-int
-as_path_match_set(const struct adata *path, const struct f_tree *set)
-{
-  const u8 *p = path->data;
-  const 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;
-}
-
-const struct adata *
-as_path_filter(struct linpool *pool, const struct adata *path, const struct f_tree *set, u32 key, int pos)
-{
-  if (!path)
-    return NULL;
-
-  int len = path->length;
-  const u8 *p = path->data;
-  const 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)
-	    {
-	      struct f_val v = {T_INT, .val.i = as};
-	      match = !!find_tree(set, &v);
-	    }
-	  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;
-	}
-  }
-
-  uint 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;
-}
-
-
-struct pm_pos
-{
-  u8 set;
-  u8 mark;
-  union
-  {
-    const char *sp;
-    u32 asn;
-  } val;
-};
-
-static int
-parse_path(const struct adata *path, struct pm_pos *pp)
-{
-  const byte *pos = path->data;
-  const byte *end = pos + path->length;
-  struct pm_pos *op = pp;
-  uint i;
-
-  while (pos < end)
-  {
-    uint type = pos[0];
-    uint len  = pos[1];
-    pos += 2;
-
-    switch (type)
-    {
-    case AS_PATH_SET:
-    case AS_PATH_CONFED_SET:
-      pp->set = 1;
-      pp->mark = 0;
-      pp->val.sp = pos - 1;
-      pp++;
-
-      pos += BS * len;
-      break;
-
-    case AS_PATH_SEQUENCE:
-    case AS_PATH_CONFED_SEQUENCE:
-      for (i = 0; i < len; i++)
-      {
-	pp->set = 0;
-	pp->mark = 0;
-	pp->val.asn = get_as(pos);
-	pp++;
-
-	pos += BS;
-      }
-      break;
-
-    default:
-      bug("Invalid path segment");
-    }
-  }
-
-  return pp - op;
-}
-
-static int
-pm_match_val(const struct pm_pos *pos, u32 asn, u32 asn2)
-{
-  u32 gas;
-  if (! pos->set)
-    return ((pos->val.asn >= asn) && (pos->val.asn <= asn2));
-
-  const u8 *p = pos->val.sp;
-  int len = *p++;
-  int i;
-
-  for (i = 0; i < len; i++)
-  {
-    gas = get_as(p + i * BS);
-
-    if ((gas >= asn) && (gas <= asn2))
-      return 1;
-  }
-
-  return 0;
-}
-
-static int
-pm_match_set(const struct pm_pos *pos, const struct f_tree *set)
-{
-  struct f_val asn = { .type = T_INT };
-
-  if (! pos->set)
-  {
-    asn.val.i = pos->val.asn;
-    return !!find_tree(set, &asn);
-  }
-
-  const u8 *p = pos->val.sp;
-  int len = *p++;
-  int i;
-
-  for (i = 0; i < len; i++)
-  {
-    asn.val.i = get_as(p + i * BS);
-    if (find_tree(set, &asn))
-      return 1;
-  }
-
-  return 0;
-}
-
-static inline int
-pm_match(const struct pm_pos *pos, const struct f_path_mask_item *mask, u32 asn, u32 asn2)
-{
-  return ((mask->kind == PM_QUESTION) ||
-	  ((mask->kind != PM_ASN_SET) ?
-	   pm_match_val(pos, asn, asn2) :
-	   pm_match_set(pos, mask->set)));
-}
-
-static void
-pm_mark(struct pm_pos *pos, int *i, int plen, int *nl, int *nh)
-{
-  int j = *i;
-
-  if (pos[j].set)
-    do { pos[j].mark = 1; j++; }
-    while ((j < plen) && pos[j].set);
-  else
-    j++;
-
-  pos[j].mark = 1;
-
-  /* Update low, high based on first and last marked pos */
-  int l = pos[*i].set ? *i : j;
-
-  *nl = (*nl < 0) ? l : MIN(*nl, l);
-  *nh = MAX(*nh, j);
-  *i = 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 if final position
- * (auxiliary position after last real position in AS path)
- * is marked.
- */
-int
-as_path_match(const struct adata *path, const struct f_path_mask *mask)
-{
-  struct pm_pos pos[2048 + 1];
-  int plen = parse_path(path, pos);
-  int l, h, i, nh, nl, last, loop;
-  u32 val = 0;
-  u32 val2 = 0;
-
-  /* l and h are bound of interval of positions where
-     are marked states */
-
-  pos[plen].set = 0;
-  pos[plen].mark = 0;
-
-  l = h = loop = 0;
-  pos[0].mark = 1;
-
-  for (uint m=0; m < mask->len; m++)
-    {
-      /* We remove this mark to not step after pos[plen] */
-      pos[plen].mark = 0;
-
-      switch (mask->item[m].kind)
-	{
-	case PM_ASTERISK:
-	  for (i = l; i <= plen; i++)
-	    pos[i].mark = 1;
-	  h = plen;
-	  break;
-
-	case PM_LOOP:
-	  loop = 1;
-	  break;
-
-	case PM_ASN:	/* Define single ASN as ASN..ASN - very narrow interval */
-	  val2 = val = mask->item[m].asn;
-	  goto step;
-	case PM_ASN_EXPR:
-	  bug("Expressions should be evaluated on AS path mask construction.");
-	case PM_ASN_RANGE:
-	  val = mask->item[m].from;
-	  val2 = mask->item[m].to;
-	  goto step;
-	case PM_QUESTION:
-	case PM_ASN_SET:
-	step:
-	  nh = nl = -1;
-	  last = plen;
-	  for (i = h; i >= l; i--)
-	    if (pos[i].mark)
-	      {
-		pos[i].mark = 0;
-		int j = i;
-
-	      match:
-		if (pm_match(pos + j, &mask->item[m], val, val2))
-		{
-		  pm_mark(pos, &j, plen, &nl, &nh);
-		  if (loop && (j < last))
-		    goto match;
-		}
-
-		last = i;
-	      }
-
-	  if (nh < 0)
-	    return 0;
-
-	  h = nh;
-	  l = nl;
-	  loop = 0;
-	  break;
-	}
-    }
-
-  return pos[plen].mark;
-}