From 2326b001d6f28e69b88c3c19795d8c0999f07db1 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 20 May 1998 11:54:33 +0000 Subject: Added routing table and routing attribute code. --- Makefile | 2 +- Rules | 10 ++- nest/Makefile | 4 +- nest/proto.c | 20 ++++++ nest/protocol.h | 19 ++++-- nest/route.h | 24 ++++++- nest/rt-attr.c | 143 +++++++++++++++++++++++++++++++++++++++++ nest/rt-table.c | 182 +++++++++++++++++++++++++++++++++++++++++++++++++++++ sysdep/unix/main.c | 2 + 9 files changed, 396 insertions(+), 10 deletions(-) create mode 100644 nest/proto.c create mode 100644 nest/rt-attr.c diff --git a/Makefile b/Makefile index 3292c7a..934fd51 100644 --- a/Makefile +++ b/Makefile @@ -21,7 +21,7 @@ export all: .dep all-dirs bird all-dirs: - set -e ; for a in $(DIRS) ; do $(MAKE) -C $$a all ; done + set -e ; for a in $(DIRS) ; do $(MAKE) -C $$a this ; done bird: $(PARTOBJS) $(LIBS) $(CC) $(LDFLAGS) -o $@ $^ diff --git a/Rules b/Rules index 2d9c0a8..d038f80 100644 --- a/Rules +++ b/Rules @@ -9,11 +9,17 @@ ifndef SRCS SRCS=$(subst .o,.c,$(OBJS)) endif +.PHONY: all this dep + +all: + @echo "Please run the top-level Makefile instead." + @exit 1 + ifdef OBJS ifdef LIB -all: $(LIB) +this: $(LIB) $(LIB): $(OBJS) rm -f $(LIB) @@ -22,7 +28,7 @@ $(LIB): $(OBJS) else -all: $(ONAME) +this: $(ONAME) $(ONAME): $(OBJS) $(LD) -r -o $(ONAME) $(OBJS) 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 + * + * 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 + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#include + +#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; cnattrs; 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; inattrs; 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 + #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)); +} diff --git a/sysdep/unix/main.c b/sysdep/unix/main.c index f3b01d4..076a872 100644 --- a/sysdep/unix/main.c +++ b/sysdep/unix/main.c @@ -20,6 +20,8 @@ main(void) log_init_debug(NULL); resource_init(); + rt_init(); + proto_init(); return 0; } -- cgit v1.2.3