Added LSA hashing table (parts of code stolen from rt-fib.c, but

heavily simplified since we don't need asynchronous walking).

4 files changed, 220 insertions, 9 deletions

diff --git a/proto/ospf/Makefile b/proto/ospf/Makefile
index 0bd05d01..f3c08fed 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 bd8bfc9a..70be3cbd 100644
--- a/proto/ospf/ospf.c
+++ b/proto/ospf/ospf.c
@@ -11,14 +11,8 @@
 #include <string.h>
 
 #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 15a6e2cf..6404f1b1 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 00000000..db2065bb
--- /dev/null
+++ b/proto/ospf/topology.c
@@ -0,0 +1,182 @@
+/*
+ *	BIRD -- OSPF Topological Database
+ *
+ *	(c) 1999 Martin Mares <mj@ucw.cz>
+ *	(c) 1999 Ondrej Filip <feela@network.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 "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; i<f->hash_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;
+	}
+    }
+}