Added routing table and routing attribute code.

6 files changed, 385 insertions, 7 deletions

diff --git a/nest/Makefile b/nest/Makefile
index f066fdfc..0a9d5fe8 100644
--- a/nest/Makefile
+++ b/nest/Makefile
@@ -1,4 +1,4 @@
 THISDIR=nest
-OBJS=rt-table.o rt-fib.o
+OBJS=rt-table.o rt-fib.o rt-attr.o proto.o
 
-include $(TOPDIR)/Rules
+include ../Rules
diff --git a/nest/proto.c b/nest/proto.c
new file mode 100644
index 00000000..ff75d94a
--- /dev/null
+++ b/nest/proto.c
@@ -0,0 +1,20 @@
+/*
+ *	BIRD -- Protocols
+ *
+ *	(c) 1998 Martin Mares <mj@ucw.cz>
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include "nest/bird.h"
+#include "nest/protocol.h"
+#include "lib/resource.h"
+#include "lib/lists.h"
+
+list proto_list;
+
+void
+proto_init(void)
+{
+  init_list(&proto_list);
+}
diff --git a/nest/protocol.h b/nest/protocol.h
index 3ebc13b6..26db2489 100644
--- a/nest/protocol.h
+++ b/nest/protocol.h
@@ -9,8 +9,14 @@
 #ifndef _BIRD_PROTOCOL_H_
 #define _BIRD_PROTOCOL_H_
 
+#include "lib/lists.h"
 #include "lib/resource.h"
 
+struct iface;
+struct rte;
+struct neighbor;
+struct rtattr;
+
 /*
  *	Routing Protocol
  */
@@ -40,20 +46,23 @@ extern struct protocol proto_static;
  */
 
 struct proto {
-  struct proto *next;
+  node n;
   struct protocol *proto;		/* Protocol */
   char *name;				/* Name of this instance */
   unsigned debug;			/* Debugging flags */
   pool *pool;				/* Local objects */
   unsigned preference;			/* Default route preference */
 
-  void (*if_notify)(struct proto *, struct iface *old, struct iface *new);
-  void (*rt_notify)(struct proto *, struct rte *old, struct rte *new);
+  void (*if_notify)(struct proto *, struct iface *new, struct iface *old);
+  void (*rt_notify)(struct proto *, struct rte *new, struct rte *old);
   void (*neigh_lost_notify)(struct proto *, struct neighbor *neigh);
-  void (*debug)(struct proto *);		/* Debugging dump */
+  void (*dump)(struct proto *);			/* Debugging dump */
   void (*start)(struct proto *);		/* Start the instance */
   void (*shutdown)(struct proto *, int time);	/* Stop the instance */
 
+  int (*rta_same)(struct rtattr *, struct rtattr *);
+  int (*rte_better)(struct rte *, struct rte *);
+
   /* Reconfigure function? */
   /* Interface patterns */
   /* Input/output filters */
@@ -64,4 +73,6 @@ struct proto {
 
 void *proto_new(struct protocol *, unsigned size);
 
+extern list proto_list;
+
 #endif
diff --git a/nest/route.h b/nest/route.h
index a9590dd2..e191a5fa 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -11,6 +11,8 @@
 
 #include "lib/resource.h"
 
+struct protocol;
+
 /*
  *	Generic data structure for storing network prefixes. Also used
  *	for the master routing table. Currently implemented as a hash 
@@ -131,6 +133,18 @@ typedef struct rte {
 
 #define REF_CHOSEN 1			/* Currently chosen route */
 
+extern rtable master_table;
+
+void rt_init(void);
+void rt_setup(rtable *, char *);
+net *net_find(rtable *tab, unsigned tos, ip_addr mask, unsigned len);
+net *net_get(rtable *tab, unsigned tos, ip_addr mask, unsigned len);
+rte *rte_find(net *net, struct proto *p);
+rte *rte_get_temp(struct rtattr *);
+void rte_update(net *net, rte *new);
+void rte_dump(rte *);
+void rt_dump(rtable *);
+
 /*
  *	Route Attributes
  *
@@ -139,7 +153,7 @@ typedef struct rte {
  *	construction of BGP route attribute lists.
  */
 
-struct rtattr {
+typedef struct rtattr {
   struct rtattr *next, *prev;		/* Hash chain */
   struct rtattr *garbage;		/* Garbage collector chain */
   struct proto *proto;			/* Protocol instance */
@@ -231,6 +245,14 @@ eattr *ea_find(ea_list *, unsigned protocol, unsigned id);
 	p->nattrs = cnt;					\
 } while(0)
 
+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_dump(rta *);
+void rta_dump_all(void);
+
 /*
  *	Default protocol preferences
  */
diff --git a/nest/rt-attr.c b/nest/rt-attr.c
new file mode 100644
index 00000000..a5ee77cb
--- /dev/null
+++ b/nest/rt-attr.c
@@ -0,0 +1,143 @@
+/*
+ *	BIRD -- Route Attribute Cache
+ *
+ *	(c) 1998 Martin Mares <mj@ucw.cz>
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include <string.h>
+
+#include "nest/bird.h"
+#include "nest/route.h"
+#include "nest/protocol.h"
+#include "lib/resource.h"
+
+/*
+ *	FIXME: Implement hash tables and garbage collection!
+ */
+
+static rta *first_rta;
+static slab *rta_slab;
+static pool *rta_pool;
+
+static inline int
+ea_same(ea_list *x, ea_list *y)
+{
+  int c;
+
+  while (x && y)
+    {
+      if (x->nattrs != y->nattrs)
+	return 0;
+      for(c=0; c<x->nattrs; c++)
+	{
+	  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;
+	}
+      x = x->next;
+      y = y->next;
+    }
+  return (!x && !y);
+}
+
+static inline int
+rta_same(rta *x, rta *y)
+{
+  return (x->proto == y->proto &&
+	  x->source == y->source &&
+	  x->scope == y->scope &&
+	  x->cast == y->cast &&
+	  x->dest == y->dest &&
+	  x->tos == y->tos &&
+	  x->flags == y->flags &&
+	  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, 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;
+}
+
+static rta *
+rta_copy(rta *o)
+{
+  rta *r = sl_alloc(rta_slab);
+
+  memcpy(r, o, sizeof(rta));
+  r->uc = 1;
+  r->attrs = ea_list_copy(o->attrs);
+  return r;
+}
+
+rta *
+rta_lookup(rta *o)
+{
+  rta *r;
+
+  for(r=first_rta; r; r=r->next)
+    if (rta_same(r, o))
+      return rta_clone(r);
+  r = rta_copy(o);
+  r->next = first_rta;
+  first_rta = r;
+  return r;
+}
+
+void
+_rta_free(rta *r)
+{
+}
+
+void
+rta_dump(rta *r)
+{
+}
+
+void
+rta_dump_all(void)
+{
+}
+
+void
+rta_init(void)
+{
+  rta_pool = rp_new(&root_pool);
+  rta_slab = sl_new(rta_pool, sizeof(rta));
+}
diff --git a/nest/rt-table.c b/nest/rt-table.c
index 1f26a2d0..97f4ace0 100644
--- a/nest/rt-table.c
+++ b/nest/rt-table.c
@@ -6,7 +6,189 @@
  *	Can be freely distributed and used under the terms of the GNU GPL.
  */
 
+#include <string.h>
+
 #include "nest/bird.h"
 #include "nest/route.h"
+#include "nest/protocol.h"
+#include "lib/resource.h"
+
+rtable master_table;
+static slab *rte_slab;
+
+void
+rte_init(struct fib_node *N)
+{
+  net *n = (net *) N;
+
+  n->next = NULL;
+  n->routes = NULL;
+}
+
+void
+rt_setup(rtable *t, char *name)
+{
+  bzero(t, sizeof(*t));
+  fib_init(&t->fib, &root_pool, sizeof(rte), 0, rte_init);
+}
+
+net *
+net_find(rtable *tab, unsigned tos, ip_addr mask, unsigned len)
+{
+  while (tab && tab->tos != tos)
+    tab = tab->sibling;
+  if (!tab)
+    return NULL;
+  return (net *) fib_find(&tab->fib, &mask, len);
+}
+
+net *
+net_get(rtable *tab, unsigned tos, ip_addr mask, unsigned len)
+{
+  rtable *t = tab;
+
+  while (t && t->tos != tos)
+    t = t->sibling;
+  if (!t)
+    {
+      while (tab->sibling)
+	tab = tab->sibling;
+      t = mb_alloc(&root_pool, sizeof(rtable));
+      rt_setup(t, NULL);
+      tab->sibling = t;
+      t->tos = tos;
+    }
+  return (net *) fib_get(&t->fib, &mask, len);
+}
+
+rte *
+rte_find(net *net, struct proto *p)
+{
+  rte *e = net->routes;
+
+  while (e && e->attrs->proto != p)
+    e = e->next;
+  return e;
+}
+
+rte *
+rte_get_temp(rta *a)
+{
+  rte *e = sl_alloc(rte_slab);
+
+  e->attrs = a;
+  e->pref = a->proto->preference;
+  e->lastmod = 0;			/* FIXME */
+  return e;
+}
+
+static int				/* Actually better or at least as good as */
+rte_better(rte *new, rte *old)
+{
+  if (!old)
+    return 1;
+  if (new->pref > old->pref)
+    return 1;
+  if (new->pref < old->pref)
+    return 0;
+  if (new->attrs->proto != old->attrs->proto)
+    {
+      /* FIXME!!! */
+      die("Different protocols, but identical preferences => oops");
+    }
+  return new->attrs->proto->rte_better(new, old);
+}
+
+void
+rte_announce(rte *new, rte *old)
+{
+  struct proto *p;
+
+  WALK_LIST(p, proto_list)
+    if (!new || new->attrs->proto != p)
+      p->rt_notify(p, new, old);
+}
+
+static inline void
+rte_free(rte *e)
+{
+  rta_free(e->attrs);
+  sl_free(rte_slab, e);
+}
+
+void
+rte_update(net *net, rte *new)
+{
+  rte *old_best = net->routes;
+  rte *old = NULL;
+  rte **k, *r, *s;
+  struct proto *p = new->attrs->proto;
+
+  k = &net->routes;			/* Find and remove original route from the same protocol */
+  while (old = *k)
+    {
+      if (old->attrs->proto == p)
+	{
+	  *k = old->next;
+	  break;
+	}
+      k = &old->next;
+    }
+
+  if (rte_better(new, old_best))	/* It's a new optimal route => announce and relink it */
+    {
+      rte_announce(new, old_best);
+      new->next = net->routes;
+      net->routes = new;
+    }
+  else
+    {
+      if (old == old_best)		/* It has _replaced_ the old optimal route */
+	{
+	  r = new;			/* Find new optimal route and announce it */
+	  for(s=net->routes; s; s=s->next)
+	    if (rte_better(s, r))
+	      r = s;
+	  rte_announce(r, old_best);
+	  if (r)			/* Re-link the new optimal route */
+	    {
+	      k = &net->routes;
+	      while (s = *k)
+		{
+		  if (s == r)
+		    {
+		      *k = r->next;
+		      break;
+		    }
+		}
+	      r->next = net->routes;
+	      net->routes = r;
+	    }
+	}
+      if (new)				/* Link in the new non-optimal route */
+	{
+	  new->next = old_best->next;
+	  old_best->next = new;
+	}
+    }
+  if (old)
+    rte_free(old);
+}
+
+void
+rte_dump(rte *r)
+{
+}
 
+void
+rt_dump(rtable *t)
+{
+}
 
+void
+rt_init(void)
+{
+  rta_init();
+  rt_setup(&master_table, "master");
+  rte_slab = sl_new(&root_pool, sizeof(rte));
+}