summaryrefslogtreecommitdiffstats
path: root/nest
diff options
context:
space:
mode:
authorMartin Mares <mj@ucw.cz>1998-05-20 13:54:33 +0200
committerMartin Mares <mj@ucw.cz>1998-05-20 13:54:33 +0200
commit2326b001d6f28e69b88c3c19795d8c0999f07db1 (patch)
treeec18cb858431ebd1953136b3e8c3de7d84c501ae /nest
parent3994080eb1a86f085498bee1f36cbdb52b30191d (diff)
downloadbird-2326b001d6f28e69b88c3c19795d8c0999f07db1.tar
bird-2326b001d6f28e69b88c3c19795d8c0999f07db1.zip
Added routing table and routing attribute code.
Diffstat (limited to 'nest')
-rw-r--r--nest/Makefile4
-rw-r--r--nest/proto.c20
-rw-r--r--nest/protocol.h19
-rw-r--r--nest/route.h24
-rw-r--r--nest/rt-attr.c143
-rw-r--r--nest/rt-table.c182
6 files changed, 385 insertions, 7 deletions
diff --git a/nest/Makefile b/nest/Makefile
index f066fdf..0a9d5fe 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 0000000..ff75d94
--- /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 3ebc13b..26db248 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 a9590dd..e191a5f 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 0000000..a5ee77c
--- /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 1f26a2d..97f4ace 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));
+}