2 files changed, 281 insertions, 71 deletions

diff --git a/nest/route.h b/nest/route.h
index 2bcc2b5c..0de54551 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -185,12 +185,11 @@ typedef struct rta {
   byte tos;				/* TOS of this route */
   byte flags;				/* Route flags (RTF_...) */
   byte aflags;				/* Attribute cache flags (RTAF_...) */
+  byte rfu;				/* Padding */
   ip_addr gw;				/* Next hop */
   ip_addr from;				/* Advertising router */
   struct iface *iface;			/* Outgoing interface */
   struct ea_list *attrs;		/* Extended Attribute chain */
-  union {				/* Protocol-specific data */
-  } u;
 } rta;
 
 #define RTS_DUMMY 0			/* Dummy route to be removed soon */
@@ -228,24 +227,32 @@ typedef struct rta {
  */
 
 typedef struct eattr {
-  byte protocol;			/* Protocol ID (EAP_...) */
-  byte flags;				/* Attribute flags (EAF_...) */
-  byte id;				/* Protocol-dependent ID */
-  byte rfu;				/* ??? */
+  word id;				/* EA_CODE(EAP_..., protocol-dependent ID) */
+  byte flags;				/* Protocol-dependent flags */
+  byte type;				/* Attribute type and several flags (EAF_...) */
   union {
     u32 data;
     struct adata *ptr;			/* Attribute data elsewhere */
   } u;
 } eattr;
 
+/* FIXME: Introduce real protocol numbers? */
 #define EAP_GENERIC 0			/* Generic attributes */
 #define EAP_BGP 1			/* BGP attributes */
 
-#define EAF_OPTIONAL 0x80		/* Refer to BGP specs for full meaning */
-#define EAF_TRANSITIVE 0x40
-#define EAF_PARTIAL 0x20
-#define EAF_EXTENDED_LENGTH 0x10	/* Not used by us, internal to BGP */
-#define EAF_LONGWORD 0x01		/* Embedded value [Not a BGP flag!] */
+#define EA_CODE(proto,id) (((proto) << 8) | (id))
+#define EA_PROTO(ea) ((ea) >> 8)
+#define EA_ID(ea) ((ea) & 0xff)
+
+#define EAF_TYPE_MASK 0x0f		/* Mask with this to get type */
+#define EAF_TYPE_INT 0x01		/* 32-bit signed integer number */
+#define EAF_TYPE_OPAQUE 0x02		/* Opaque byte string (not filterable) */
+#define EAF_TYPE_IP_ADDRESS 0x04	/* IP address [FIXME: embed at least for IPv4?] */
+#define EAF_TYPE_AS_PATH 0x06		/* BGP AS path [FIXME: define storage layout] */
+#define EAF_TYPE_INT_SET 0x0a		/* Set of integers (e.g., a community list) */
+#define EAF_EMBEDDED 0x01		/* Data stored in eattr.u.data (part of type spec) */
+#define EAF_VAR_LENGTH 0x02		/* Attribute length is variable */
+#define EAF_INLINE 0x80			/* Copy of an attribute inlined in rte (temporary ea_lists only) */
 
 struct adata {
   unsigned int length;
@@ -254,28 +261,30 @@ struct adata {
 
 typedef struct ea_list {
   struct ea_list *next;			/* In case we have an override list */
-  byte sorted;				/* `Really sorted' flag (???) */
+  byte flags;				/* Flags: EALF_... */
   byte rfu;
-  word nattrs;				/* Number of attributes */
+  word count;				/* Number of attributes */
   eattr attrs[0];			/* Attribute definitions themselves */
 } ea_list;
 
-eattr *ea_find(ea_list *, unsigned protocol, unsigned id);
+#define EALF_SORTED 1			/* Attributes are sorted by code */
+#define EALF_BISECT 2			/* Use interval bisection for searching */
+#define EALF_CACHED 4			/* Attributes belonging to cached rta */
 
-#define EA_LIST_NEW(p, alloc, n) do {				\
-	unsigned cnt = n;				       	\
-	p = alloc(sizeof(ea_list) + cnt*sizeof(eattr));		\
-	memset(p, 0, sizeof(ea_list));				\
-	p->nattrs = cnt;					\
-} while(0)
+eattr *ea_find(ea_list *, unsigned ea);
+void ea_dump(ea_list *);
+void ea_sort(ea_list *);		/* Sort entries in all sub-lists */
+unsigned ea_scan(ea_list *);		/* How many bytes do we need for merged ea_list (0=merge not needed) */
+void ea_merge(ea_list *from, ea_list *to); /* Merge sub-lists to allocated buffer */
 
 void rta_init(void);
 rta *rta_lookup(rta *);			/* Get rta equivalent to this one, uc++ */
 static inline rta *rta_clone(rta *r) { r->uc++; return r; }
-void _rta_free(rta *r);
-static inline void rta_free(rta *r) { if (r && !--r->uc) _rta_free(r); }
+void rta__free(rta *r);
+static inline void rta_free(rta *r) { if (r && !--r->uc) rta__free(r); }
 void rta_dump(rta *);
 void rta_dump_all(void);
+static inline eattr * rta_find(rta *a, unsigned ea) { return ea_find(a->attrs, ea); }
 
 /*
  *	Default protocol preferences
diff --git a/nest/rt-attr.c b/nest/rt-attr.c
index aa4a59ad..2cb2bc50 100644
--- a/nest/rt-attr.c
+++ b/nest/rt-attr.c
@@ -1,12 +1,13 @@
 /*
  *	BIRD -- Route Attribute Cache
  *
- *	(c) 1998 Martin Mares <mj@ucw.cz>
+ *	(c) 1998--1999 Martin Mares <mj@ucw.cz>
  *
  *	Can be freely distributed and used under the terms of the GNU GPL.
  */
 
 #include <string.h>
+#include <alloca.h>
 
 #include "nest/bird.h"
 #include "nest/route.h"
@@ -22,33 +23,246 @@ static rta *first_rta;
 static slab *rta_slab;
 static pool *rta_pool;
 
+/*
+ *	Extended Attributes
+ */
+
+eattr *
+ea_find(ea_list *e, unsigned id)
+{
+  eattr *a;
+  int l, r, m;
+
+  while (e)
+    {
+      if (e->flags & EALF_BISECT)
+	{
+	  l = 0;
+	  r = e->count + 1;
+	  while (l <= r)
+	    {
+	      m = (l+r) / 2;
+	      a = &e->attrs[m];
+	      if (a->id == id)
+		return a;
+	      else if (a->id < id)
+		l = m+1;
+	      else
+		r = m-1;
+	    }
+	}
+      else
+	for(m=0; m<e->count; m++)
+	  if (e->attrs[m].id == id)
+	    return &e->attrs[m];
+      e = e->next;
+    }
+  return NULL;
+}
+
+static inline void
+ea_do_sort(ea_list *e)
+{
+  unsigned n = e->count;
+  eattr *a = e->attrs;
+  eattr *b = alloca(n * sizeof(eattr));
+  unsigned s, ss;
+
+  /* We need to use a stable sorting algorithm, hence mergesort */
+  do
+    {
+      s = ss = 0;
+      while (s < n)
+	{
+	  eattr *p, *q, *lo, *hi;
+	  p = b;
+	  ss = s;
+	  *p++ = a[s++];
+	  while (s < n && p[-1].id <= a[s].id)
+	    *p++ = a[s++];
+	  if (s < n)
+	    {
+	      q = p;
+	      *p++ = a[s++];
+	      while (s < n && p[-1].id <= a[s].id)
+		*p++ = a[s++];
+	      lo = b;
+	      hi = q;
+	      s = ss;
+	      while (lo < q && hi < p)
+		if (lo->id <= hi->id)
+		  a[s++] = *lo++;
+		else
+		  a[s++] = *hi++;
+	      while (lo < q)
+		a[s++] = *lo++;
+	      while (hi < p)
+		a[s++] = *hi++;
+	    }
+	}
+    }
+  while (ss);
+}
+
+static inline void
+ea_do_prune(ea_list *e)
+{
+  eattr *s, *d;
+  int i;
+
+  /* Discard duplicates. Do you remember sorting was stable? */
+  s = d = e->attrs + 1;
+  for(i=1; i<e->count; i++)
+    if (s->id != d[-1].id)
+      *d++ = *s++;
+    else
+      s++;
+  e->count = d - e->attrs;
+}
+
+void
+ea_sort(ea_list *e)
+{
+  while (e)
+    {
+      if (!(e->flags & EALF_SORTED))
+	{
+	  ea_do_sort(e);
+	  ea_do_prune(e);
+	  e->flags |= EALF_SORTED;
+	}
+#if 0			/* FIXME: Remove this after some testing */
+      if (e->count > 5)
+#endif
+	e->flags |= EALF_BISECT;
+      e = e->next;
+    }
+}
+
+unsigned
+ea_scan(ea_list *e)
+{
+  unsigned cnt = 0;
+
+  while (e)
+    {
+      cnt += e->count;
+      e = e->next;
+    }
+  return sizeof(ea_list) + sizeof(eattr)*cnt;
+}
+
+void
+ea_merge(ea_list *e, ea_list *t)
+{
+  eattr *d = t->attrs;
+
+  t->flags = 0;
+  t->count = 0;
+  t->next = NULL;
+  while (e)
+    {
+      memcpy(d, e->attrs, sizeof(eattr)*e->count);
+      t->count += e->count;
+      d += e->count;
+      e = e->next;
+    }
+}
+
 static inline int
 ea_same(ea_list *x, ea_list *y)
 {
   int c;
 
-  while (x && y)
+  if (!x || !y)
+    return x == y;
+  ASSERT(!x->next && !y->next);
+  if (x->count != y->count)
+    return 0;
+  for(c=0; c<x->count; c++)
     {
-      if (x->nattrs != y->nattrs)
+      eattr *a = &x->attrs[c];
+      eattr *b = &y->attrs[c];
+
+      if (a->id != b->id ||
+	  a->flags != b->flags ||
+	  a->type != b->type ||
+	  ((a->type & EAF_EMBEDDED) ? a->u.data != b->u.data :
+	   (a->u.ptr->length != b->u.ptr->length || memcmp(a->u.ptr, b->u.ptr, a->u.ptr->length))))
 	return 0;
-      for(c=0; c<x->nattrs; c++)
+    }
+  return 1;
+}
+
+static inline ea_list *
+ea_list_copy(ea_list *o)
+{
+  ea_list *n;
+  unsigned i, len;
+
+  if (!o)
+    return NULL;
+  ASSERT(!o->next);
+  len = sizeof(ea_list) + sizeof(eattr) * o->count;
+  n = mb_alloc(rta_pool, len);
+  memcpy(n, o, len);
+  n->flags |= EALF_CACHED;
+  for(i=0; i<o->count; i++)
+    {
+      eattr *a = &n->attrs[i];
+      if (!(a->flags & EAF_EMBEDDED))
+	{
+	  unsigned size = sizeof(struct adata) + a->u.ptr->length;
+	  struct adata *d = mb_alloc(rta_pool, size);
+	  memcpy(d, a->u.ptr, size);
+	  a->u.ptr = d;
+	}
+    }
+  return n;
+}
+
+void
+ea_dump(ea_list *e)
+{
+  int i;
+
+  if (!e)
+    {
+      debug("NONE");
+      return;
+    }
+  while (e)
+    {
+      debug("[%c%c%c]",
+	    (e->flags & EALF_SORTED) ? 'S' : 's',
+	    (e->flags & EALF_BISECT) ? 'B' : 'b',
+	    (e->flags & EALF_CACHED) ? 'C' : 'c');
+      for(i=0; i<e->count; i++)
 	{
-	  eattr *a = &x->attrs[c];
-	  eattr *b = &y->attrs[c];
-
-	  if (a->protocol != b->protocol ||
-	      a->flags != b->flags ||
-	      a->id != b->id ||
-	      ((a->flags & EAF_LONGWORD) ? a->u.data != b->u.data :
-	       (a->u.ptr->length != b->u.ptr->length || memcmp(a->u.ptr, b->u.ptr, a->u.ptr->length))))
-	    return 0;
+	  eattr *a = &e->attrs[i];
+	  debug(" %02x:%02x.%02x", EA_PROTO(a->id), EA_ID(a->id), a->flags);
+	  if (a->type & EAF_INLINE)
+	    debug("*");
+	  debug("=%c", "?iO?I?P???S?????" [a->type & EAF_TYPE_MASK]);
+	  if (a->type & EAF_EMBEDDED)
+	    debug(":%08x", a->u.data);
+	  else
+	    {
+	      int j, len = a->u.ptr->length;
+	      debug("[%d]:", len);
+	      for(j=0; j<len; j++)
+		debug("%02x", a->u.ptr->data[j]);
+	    }
 	}
-      x = x->next;
-      y = y->next;
+      if (e = e->next)
+	debug(" | ");
     }
-  return (!x && !y);
 }
 
+/*
+ *	rta's
+ */
+
 static inline int
 rta_same(rta *x, rta *y)
 {
@@ -62,38 +276,7 @@ rta_same(rta *x, rta *y)
 	  ipa_equal(x->gw, y->gw) &&
 	  ipa_equal(x->from, y->from) &&
 	  x->iface == y->iface &&
-	  ea_same(x->attrs, y->attrs) &&
-	  (!x->proto->rta_same || x->proto->rta_same(x, y)));
-}
-
-static inline ea_list *
-ea_list_copy(ea_list *o)
-{
-  ea_list *n, **p, *z;
-  unsigned i;
-
-  p = &n;
-  while (o)
-    {
-      z = mb_alloc(rta_pool, sizeof(ea_list) + sizeof(eattr) * o->nattrs);
-      memcpy(z, o, sizeof(ea_list) + sizeof(eattr) * o->nattrs);
-      *p = z;
-      p = &z->next;
-      for(i=0; i<o->nattrs; i++)
-	{
-	  eattr *a = o->attrs + i;
-	  if (!(a->flags & EAF_LONGWORD))
-	    {
-	      unsigned size = sizeof(struct adata) + a->u.ptr->length;
-	      struct adata *d = mb_alloc(rta_pool, size);
-	      memcpy(d, a->u.ptr, size);
-	      a->u.ptr = d;
-	    }
-	}
-      o = o->next;
-    }
-  *p = NULL;
-  return n;
+	  ea_same(x->attrs, y->attrs));
 }
 
 static rta *
@@ -112,9 +295,22 @@ rta_lookup(rta *o)
 {
   rta *r;
 
+  ASSERT(!(o->aflags & RTAF_CACHED));
+  if (o->attrs)
+    {
+      if (o->attrs->next)	/* Multiple ea_list's, need to merge them */
+	{
+	  ea_list *ml = alloca(ea_scan(o->attrs));
+	  ea_merge(o->attrs, ml);
+	  o->attrs = ml;
+	}
+      ea_sort(o->attrs);
+    }
+
   for(r=first_rta; r; r=r->next)
     if (rta_same(r, o))
       return rta_clone(r);
+
   r = rta_copy(o);
   r->aflags = RTAF_CACHED;
   r->next = first_rta;
@@ -123,7 +319,7 @@ rta_lookup(rta *o)
 }
 
 void
-_rta_free(rta *a)
+rta__free(rta *a)
 {
 }
 
@@ -152,6 +348,11 @@ rta_dump(rta *a)
     debug(" ->%I", a->gw);
   if (a->dest == RTD_DEVICE || a->dest == RTD_ROUTER)
     debug(" [%s]", a->iface ? a->iface->name : "???" );
+  if (a->attrs)
+    {
+      debug(" EA: ");
+      ea_dump(a->attrs);
+    }
 }
 
 void