From 6ba36f06ae10ea7efd60c30f8ef40d6143c69ef6 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 10 Nov 1999 12:27:01 +0000 Subject: Added LSA hashing table (parts of code stolen from rt-fib.c, but heavily simplified since we don't need asynchronous walking). --- proto/ospf/Makefile | 3 +- proto/ospf/ospf.c | 6 -- proto/ospf/ospf.h | 38 ++++++++++- proto/ospf/topology.c | 182 ++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 220 insertions(+), 9 deletions(-) create mode 100644 proto/ospf/topology.c (limited to 'proto') diff --git a/proto/ospf/Makefile b/proto/ospf/Makefile index 0bd05d0..f3c08fe 100644 --- a/proto/ospf/Makefile +++ b/proto/ospf/Makefile @@ -1,6 +1,5 @@ -source=ospf.c +source=ospf.c topology.c root-rel=../../ dir-name=proto/ospf include ../../Rules - diff --git a/proto/ospf/ospf.c b/proto/ospf/ospf.c index bd8bfc9..70be3cb 100644 --- a/proto/ospf/ospf.c +++ b/proto/ospf/ospf.c @@ -11,14 +11,8 @@ #include #include "nest/bird.h" -#include "nest/iface.h" -#include "nest/protocol.h" #include "nest/route.h" #include "conf/conf.h" -#include "lib/ip.h" -#include "lib/socket.h" -#include "lib/lists.h" -#include "lib/timer.h" #include "lib/checksum.h" #include "ospf.h" diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h index 15a6e2c..6404f1b 100644 --- a/proto/ospf/ospf.h +++ b/proto/ospf/ospf.h @@ -9,6 +9,14 @@ #ifndef _BIRD_OSPF_H_ #define _BIRD_OSPF_H_ +#include "lib/ip.h" +#include "lib/lists.h" +#include "lib/socket.h" +#include "lib/timer.h" +#include "lib/resource.h" +#include "nest/protocol.h" +#include "nest/iface.h" + #define OSPF_PROTO 89 #ifndef IPV6 #define OSPF_VERSION 2 @@ -185,8 +193,36 @@ struct ospf_neighbor #define INM_ADJOK 7 /* AdjOK? */ #define INM_SEQMIS 8 /* Sequence number mismatch */ #define INM_1WAYREC 9 /* 1-Way */ -#define INM_KILLNBR 10 /* Kill Neigbor */ +#define INM_KILLNBR 10 /* Kill Neighbor */ #define INM_INACTTIM 11 /* Inactivity timer */ #define INM_LLDOWN 12 /* Line down */ +/* topology.c: Representation of network topology (LS graph) */ + +struct top_hash_entry { /* Index for fast mapping (type,rtrid,LSid)->vertex */ + struct top_hash_entry *next; /* Next in hash chain */ + struct top_vertex *vertex; + u32 lsa_id, rtr_id; + u16 lsa_type; + u16 pad; +}; + +struct top_graph { + pool *pool; /* Pool we allocate from */ + slab *hash_slab; /* Slab for hash entries */ + struct top_hash_entry **hash_table; /* Hashing (modelled a`la fib) */ + unsigned int hash_size; + unsigned int hash_order; + unsigned int hash_mask; + unsigned int hash_entries; + unsigned int hash_entries_min, hash_entries_max; +}; + +struct top_graph *ospf_top_new(struct proto_ospf *); +void ospf_top_free(struct top_graph *); +void ospf_top_dump(struct top_graph *); +struct top_hash_entry *ospf_hash_find(struct top_graph *, u32 lsa, u32 rtr, u32 type); +struct top_hash_entry *ospf_hash_get(struct top_graph *, u32 lsa, u32 rtr, u32 type); +void ospf_hash_delete(struct top_graph *, struct top_hash_entry *); + #endif /* _BIRD_OSPF_H_ */ diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c new file mode 100644 index 0000000..db2065b --- /dev/null +++ b/proto/ospf/topology.c @@ -0,0 +1,182 @@ +/* + * BIRD -- OSPF Topological Database + * + * (c) 1999 Martin Mares + * (c) 1999 Ondrej Filip + * + * Can be freely distributed and used under the terms of the GNU GPL. + */ + +#define LOCAL_DEBUG + +#include + +#include "nest/bird.h" + +#include "ospf.h" + +#define HASH_DEF_ORDER 6 /* FIXME: Increase */ +#define HASH_HI_MARK *4 +#define HASH_HI_STEP 2 +#define HASH_HI_MAX 16 +#define HASH_LO_MARK /5 +#define HASH_LO_STEP 2 +#define HASH_LO_MIN 8 + +static void +ospf_top_ht_alloc(struct top_graph *f) +{ + f->hash_size = 1 << f->hash_order; + f->hash_mask = f->hash_size - 1; + if (f->hash_order > HASH_HI_MAX - HASH_HI_STEP) + f->hash_entries_max = ~0; + else + f->hash_entries_max = f->hash_size HASH_HI_MARK; + if (f->hash_order < HASH_LO_MIN + HASH_LO_STEP) + f->hash_entries_min = 0; + else + f->hash_entries_min = f->hash_size HASH_LO_MARK; + DBG("Allocating OSPF hash of order %d: %d hash_entries, %d low, %d high\n", + f->hash_order, f->hash_size, f->hash_entries_min, f->hash_entries_max); + f->hash_table = mb_alloc(f->pool, f->hash_size * sizeof(struct top_hash_entry *)); + bzero(f->hash_table, f->hash_size * sizeof(struct top_hash_entry *)); +} + +static inline void +ospf_top_ht_free(struct top_hash_entry **h) +{ + mb_free(h); +} + +static inline u32 +ospf_top_hash_u32(u32 a) +{ + /* Shamelessly stolen from IP address hashing in ipv4.h */ + a ^= a >> 16; + a ^= a << 10; + return a; +} + +static inline unsigned +ospf_top_hash(struct top_graph *f, u32 lsaid, u32 rtrid, u32 type) +{ + return (ospf_top_hash_u32(lsaid) + ospf_top_hash_u32(rtrid) + type) & f->hash_mask; +} + +struct top_graph * +ospf_top_new(struct proto_ospf *p) +{ + struct top_graph *f; + + f = mb_allocz(p->proto.pool, sizeof(struct top_graph)); + f->pool = p->proto.pool; + f->hash_slab = sl_new(f->pool, sizeof(struct top_hash_entry)); + f->hash_order = HASH_DEF_ORDER; + ospf_top_ht_alloc(f); + f->hash_entries = 0; + f->hash_entries_min = 0; + return f; +} + +void +ospf_top_free(struct top_graph *f) +{ + rfree(f->hash_slab); + ospf_top_ht_free(f->hash_table); + mb_free(f); +} + +static void +ospf_top_rehash(struct top_graph *f, int step) +{ + unsigned int oldn, oldh; + struct top_hash_entry **n, **oldt, **newt, *e, *x; + + oldn = f->hash_size; + oldt = f->hash_table; + DBG("Re-hashing topology hash from order %d to %d\n", f->hash_order, f->hash_order+step); + f->hash_order += step; + ospf_top_ht_alloc(f); + newt = f->hash_table; + + for(oldh=0; oldh < oldn; oldh++) + { + e = oldt[oldh]; + while (e) + { + x = e->next; + n = newt + ospf_top_hash(f, e->lsa_id, e->rtr_id, e->lsa_type); + e->next = *n; + *n = e; + e = x; + } + } + ospf_top_ht_free(oldt); +} + +struct top_hash_entry * +ospf_hash_find(struct top_graph *f, u32 lsa, u32 rtr, u32 type) +{ + struct top_hash_entry *e = f->hash_table[ospf_top_hash(f, lsa, rtr, type)]; + + while (e && (e->lsa_id != lsa || e->rtr_id != rtr || e->lsa_type != type)) + e = e->next; + return e; +} + +struct top_hash_entry * +ospf_hash_get(struct top_graph *f, u32 lsa, u32 rtr, u32 type) +{ + struct top_hash_entry **ee = f->hash_table + ospf_top_hash(f, lsa, rtr, type); + struct top_hash_entry *e = *ee; + + while (e && (e->lsa_id != lsa || e->rtr_id != rtr || e->lsa_type != type)) + e = e->next; + if (e) + return e; + e = sl_alloc(f->hash_slab); + e->lsa_id = lsa; + e->rtr_id = rtr; + e->lsa_type = type; + e->vertex = NULL; + if (f->hash_entries++ > f->hash_entries_max) + ospf_top_rehash(f, HASH_HI_STEP); + return e; +} + +void +ospf_hash_delete(struct top_graph *f, struct top_hash_entry *e) +{ + unsigned int h = ospf_top_hash(f, e->lsa_id, e->rtr_id, e->lsa_type); + struct top_hash_entry **ee = f->hash_table + h; + + while (*ee) + { + if (*ee == e) + { + *ee = e->next; + sl_free(f->hash_slab, e); + if (f->hash_entries-- < f->hash_entries_min) + ospf_top_rehash(f, -HASH_LO_STEP); + return; + } + ee = &((*ee)->next); + } + bug("ospf_hash_delete() called for invalid node"); +} + +void +ospf_top_dump(struct top_graph *f) +{ + unsigned int i; + + for(i=0; ihash_size; i++) + { + struct top_hash_entry *e = f->hash_table[i]; + while (e) + { + debug("%04x %08x %08x %p\n", e->lsa_type, e->lsa_id, e->rtr_id, e->vertex); + e = e->next; + } + } +} -- cgit v1.2.3