1 files changed, 250 insertions, 49 deletions

diff --git a/nest/rt-attr.c b/nest/rt-attr.c
index aa4a59a..2cb2bc5 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