diff options
| -rw-r--r-- | nest/Makefile | 3 | ||||
| -rw-r--r-- | nest/main.c | 20 | ||||
| -rw-r--r-- | nest/route.h | 42 | ||||
| -rw-r--r-- | nest/rt-fib.c | 150 | ||||
| -rw-r--r-- | nest/rt-table.c | 12 |
5 files changed, 189 insertions, 38 deletions
diff --git a/nest/Makefile b/nest/Makefile index d6c0e6e..f066fdf 100644 --- a/nest/Makefile +++ b/nest/Makefile @@ -1,3 +1,4 @@ -OBJS=main.o +THISDIR=nest +OBJS=rt-table.o rt-fib.o include $(TOPDIR)/Rules diff --git a/nest/main.c b/nest/main.c deleted file mode 100644 index 91d96c6..0000000 --- a/nest/main.c +++ /dev/null @@ -1,20 +0,0 @@ -/* - * BIRD Internet Routing Daemon - * - * (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 "lib/lists.h" -#include "lib/resource.h" - -int -main(void) -{ - log_init_debug(NULL); - resource_init(); - - return 0; -} diff --git a/nest/route.h b/nest/route.h index ec4c965..a9590dd 100644 --- a/nest/route.h +++ b/nest/route.h @@ -13,14 +13,13 @@ /* * Generic data structure for storing network prefixes. Also used - * for the master routing table. Currently implemented as a radix - * trie. + * for the master routing table. Currently implemented as a hash + * table. * * Available operations: * - insertion of new entry * - deletion of entry - * - searching of entry by network prefix - * - searching of entry by IP address (longest match) + * - searching for entry by network prefix */ struct fib_node { @@ -32,9 +31,11 @@ struct fib_node { }; struct fib { - slab fib_slab; /* Slab holding all fib nodes */ - struct fib_node *hash_table; /* Node hash table */ + pool *fib_pool; /* Pool holding all our data */ + slab *fib_slab; /* Slab holding all fib nodes */ + struct fib_node **hash_table; /* Node hash table */ unsigned int hash_size; /* Number of hash table entries (a power of two) */ + unsigned int hash_mask; /* hash_size - 1 */ unsigned int entries; /* Number of entries */ unsigned int entries_min, entries_max;/* Entry count limits (else start rehashing) */ void (*init)(struct fib_node *); /* Constructor */ @@ -43,18 +44,18 @@ struct fib { void fib_init(struct fib *, pool *, unsigned node_size, unsigned hash_size, void (*init)(struct fib_node *)); void *fib_find(struct fib *, ip_addr *, int); /* Find or return NULL if doesn't exist */ void *fib_get(struct fib *, ip_addr *, int); /* Find or create new if nonexistent */ -void fib_delete(void *); /* Remove fib entry */ +void fib_delete(struct fib *, void *); /* Remove fib entry */ void fib_free(struct fib *); /* Destroy the fib */ -#define FIB_WALK(fib, op) { \ - struct fib_node *f, **ff = (fib)->hash_table; \ +#define FIB_WALK(fib, z, op) do { \ + struct fib_node *z, **ff = (fib)->hash_table; \ unsigned int count = (fib)->hash_size; \ while (count--) \ - for(f = *ff++; f; f=f->next) \ + for(z = *ff++; z; z=z->next) \ { \ - op \ + op; \ } \ - } + } while (0) /* * Neighbor Cache. We hold (direct neighbor, protocol) pairs we've seen @@ -76,12 +77,21 @@ typedef struct neighbor { neighbor *neigh_find(ip_addr *); /* NULL if not a neighbor */ /* - * Master Routing Table. Generally speaking, it's a FIB with each entry - * pointing to a list of route entries representing routes to given network. + * Master Routing Tables. Generally speaking, each of them is a list + * of FIB (one per TOS) with each entry pointing to a list of route entries + * representing routes to given network. * Each of the RTE's contains variable data (the preference and protocol-dependent - * metrics) and a pointer to route attribute block common for many routes). + * metrics) and a pointer to a route attribute block common for many routes). */ +typedef struct rtable { + struct rtable *sibling; /* Our sibling for different TOS */ + byte tos; /* TOS for this table */ + struct fib fib; + char *name; /* Name of this table */ + /* FIXME: Data for kernel synchronization */ +} rtable; + typedef struct network { struct fib_node n; struct rte *routes; /* Available routes for this network */ @@ -121,8 +131,6 @@ typedef struct rte { #define REF_CHOSEN 1 /* Currently chosen route */ -typedef struct rte rte; - /* * Route Attributes * diff --git a/nest/rt-fib.c b/nest/rt-fib.c new file mode 100644 index 0000000..d7350ae --- /dev/null +++ b/nest/rt-fib.c @@ -0,0 +1,150 @@ +/* + * BIRD -- Forwarding Information Base -- Data Structures + * + * (c) 1998 Martin Mares <mj@ucw.cz> + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#define LOCAL_DEBUG + +#include <string.h> + +#include "nest/bird.h" +#include "nest/route.h" + +#define HASH_DEF_SIZE 1024 +#define HASH_HI_MARK *16 +#define HASH_LO_MARK *0 +#define HASH_LO_MIN 128 +#define HASH_HI_RESIZE *16 +#define HASH_LO_RESIZE *0 + +static void +fib_ht_alloc(struct fib *f) +{ + f->hash_mask = f->hash_size - 1; + f->entries_max = f->hash_size HASH_HI_MARK; + f->entries_min = f->hash_size HASH_LO_MARK; + if (f->entries_min < HASH_LO_MIN) + f->entries_min = 0; + DBG("Allocating FIB: %d entries, %d low, %d high", f->hash_size, f->entries_min, f->entries_max); + f->hash_table = mb_alloc(f->fib_pool, f->hash_size * sizeof(struct fib_node *)); + bzero(f->hash_table, f->hash_size * sizeof(struct fib_node *)); +} + +static inline void +fib_ht_free(struct fib_node **h) +{ + mb_free(h); +} + +static inline unsigned +fib_hash(struct fib *f, ip_addr *a) +{ + return ipa_hash(*a) & f->hash_mask; +} + +void +fib_init(struct fib *f, pool *p, unsigned node_size, unsigned hash_size, void (*init)(struct fib_node *)) +{ + if (!hash_size) + hash_size = HASH_DEF_SIZE; + f->fib_pool = p; + f->fib_slab = sl_new(p, node_size); + f->hash_size = hash_size; + fib_ht_alloc(f); + f->entries = 0; + f->entries_min = 0; + f->init = init; +} + +static void +fib_rehash(struct fib *f, unsigned new) +{ + unsigned old; + struct fib_node **n, *e, *x, **t, **m, **h; + + old = f->hash_size; + m = h = f->hash_table; + DBG("Re-hashing FIB from %d to %d", old, new); + f->hash_size = new; + fib_ht_alloc(f); + n = f->hash_table; + while (old--) + { + x = *h++; + while (e = x) + { + x = e->next; + t = n + fib_hash(f, &e->prefix); + e->next = *t; + *t = e; + } + } + fib_ht_free(m); +} + +void * +fib_find(struct fib *f, ip_addr *a, int len) +{ + struct fib_node *e = f->hash_table[fib_hash(f, a)]; + + while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix))) + e = e->next; + return e; +} + +void * +fib_get(struct fib *f, ip_addr *a, int len) +{ + struct fib_node **ee = f->hash_table + fib_hash(f, a); + struct fib_node *e = *ee; + + while (e && (e->pxlen != len || !ipa_equal(*a, e->prefix))) + e = e->next; + if (e) + return e; +#ifdef DEBUG + if (len < 0 || len > BITS_PER_IP_ADDRESS || !ip_is_prefix(*a,len)) + die("fib_get() called for invalid address"); +#endif + e = sl_alloc(f->fib_slab); + e->prefix = *a; + e->pxlen = len; + e->flags = 0; + e->next = *ee; + *ee = e; + f->init(e); + if (f->entries++ > f->entries_max) + fib_rehash(f, f->hash_size HASH_HI_RESIZE); + return e; +} + +void +fib_delete(struct fib *f, void *E) +{ + struct fib_node *e = E; + struct fib_node **ee = f->hash_table + fib_hash(f, &e->prefix); + + while (*ee) + { + if (*ee == e) + { + *ee = e->next; + sl_free(f->fib_slab, e); + if (f->entries-- < f->entries_min) + fib_rehash(f, f->hash_size HASH_LO_RESIZE); + return; + } + ee = &((*ee)->next); + } + die("fib_delete() called for invalid node"); +} + +void +fib_free(struct fib *f) +{ + fib_ht_free(f->hash_table); + rfree(f->fib_slab); +} diff --git a/nest/rt-table.c b/nest/rt-table.c new file mode 100644 index 0000000..1f26a2d --- /dev/null +++ b/nest/rt-table.c @@ -0,0 +1,12 @@ +/* + * BIRD -- Routing Table + * + * (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/route.h" + + |