Routing table calculation. Dijkstra done.

8 files changed, 191 insertions, 10 deletions

diff --git a/proto/ospf/Makefile b/proto/ospf/Makefile
index 632c3b6..f90222c 100644
--- a/proto/ospf/Makefile
+++ b/proto/ospf/Makefile
@@ -1,4 +1,4 @@
-source=ospf.c topology.c packet.c hello.c neighbor.c iface.c dbdes.c lsreq.c lsupd.c lsack.c lsalib.c
+source=ospf.c topology.c packet.c hello.c neighbor.c iface.c dbdes.c lsreq.c lsupd.c lsack.c lsalib.c rt.c
 root-rel=../../
 dir-name=proto/ospf
 
diff --git a/proto/ospf/lsupd.c b/proto/ospf/lsupd.c
index 7eff7df..2735695 100644
--- a/proto/ospf/lsupd.c
+++ b/proto/ospf/lsupd.c
@@ -8,12 +8,6 @@
 
 #include "ospf.h"
 
-void
-ospf_lsupd_tx(struct ospf_neighbor *n)
-{
-  /* FIXME Go on! */
-}
-
 int
 flood_lsa(struct ospf_neighbor *n, struct ospf_lsa_header *hn,
   struct ospf_lsa_header *hh, struct proto_ospf *po, struct ospf_iface *iff,
diff --git a/proto/ospf/lsupd.h b/proto/ospf/lsupd.h
index e0ecf09..a03ed8c 100644
--- a/proto/ospf/lsupd.h
+++ b/proto/ospf/lsupd.h
@@ -10,7 +10,6 @@
 #ifndef _BIRD_OSPF_LSUPD_H_
 #define _BIRD_OSPF_LSUPD_H_
 
-void ospf_lsupd_tx(struct ospf_neighbor *n);
 void ospf_lsupd_tx_list(struct ospf_neighbor *n, list *l);
 void ospf_lsupd_rx(struct ospf_lsupd_packet *ps, struct proto *p,
   struct ospf_iface *ifa, u16 size);
diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h
index 0039787..939bae7 100644
--- a/proto/ospf/ospf.h
+++ b/proto/ospf/ospf.h
@@ -202,6 +202,10 @@ struct ospf_lsa_rt_link_tos {	/* Actually we ignore TOS. This is useless */
   u16 metric;
 };
 
+struct ospf_lsa_net {
+  u32 netmask;
+};
+
 struct ospf_lsa_summ {
   u32 netmask;
 };
@@ -320,7 +324,9 @@ struct ospf_area {
   struct top_graph *gr;		/* LSA graph */
   slist lsal;			/* List of all LSA's */
   struct top_hash_entry *rt;	/* My own router LSA */
-  int stub;
+  list cand;			/* List of candidates for RT calc. */
+  u8 stub;
+  u8 trcap;			/* Transit capability? */
 };
 
 struct proto_ospf {
@@ -330,6 +336,11 @@ struct proto_ospf {
   int areano;			/* Number of area I belong to */
 };
 
+struct spf_n {
+  node n;
+  struct top_hash_entry *en;
+};
+
 static int ospf_start(struct proto *p);
 static void ospf_dump(struct proto *p);
 static struct proto *ospf_init(struct proto_config *c);
@@ -346,5 +357,6 @@ static void ospf_postconfig(struct proto_config *c);
 #include "proto/ospf/lsupd.h"
 #include "proto/ospf/lsack.h"
 #include "proto/ospf/lsalib.h"
+#include "proto/ospf/rt.h"
 
 #endif /* _BIRD_OSPF_H_ */
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
new file mode 100644
index 0000000..dbdba11
--- /dev/null
+++ b/proto/ospf/rt.c
@@ -0,0 +1,153 @@
+/*
+ *	BIRD -- OSPF
+ *
+ *	(c) 2000 Ondrej Filip <feela@network.cz>
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include "ospf.h"
+
+void
+ospf_rt_spfa(struct ospf_area *oa, struct proto *p)
+{
+  struct top_hash_entry *en;
+  slab *sl;
+  struct spf_n *cn;
+  u32 i,*rts;
+
+  /*
+   * First of all, mark all vertices as they are not in SPF
+   * Maybe I can join this work with Aging of structure
+   */
+
+  WALK_SLIST(SNODE en, oa->lsal)
+  {
+    en->color=OUTSPF;
+    en->dist=LSINFINITY;
+  }
+
+  init_list(&oa->cand);		/* Empty list of candidates */
+  oa->trcap=0;
+
+  sl=sl_new(p->pool,sizeof(struct spf_n));
+
+  cn=sl_alloc(sl);
+  cn->en=oa->rt;
+  oa->rt->dist=0;
+  oa->rt->color=CANDIDATE;
+  add_head(&oa->cand,NODE cn);
+
+  while(!EMPTY_LIST(oa->cand))
+  {
+    struct top_hash_entry *act,*tmp;
+    node *n;
+    struct ospf_lsa_rt *rt;
+    struct ospf_lsa_rt_link *rtl;
+    struct ospf_lsa_net *net;
+
+    n=HEAD(oa->cand);
+    act=((struct spf_n *)n)->en;
+    rem_node(n);
+    sl_free(sl,n);		/* Good idea? */
+
+    act->color=INSPF;
+    switch(act->lsa.type)
+    {
+      case LSA_T_RT:
+        rt=(struct ospf_lsa_rt *)act->lsa_body;
+	if((rt->VEB)&(1>>LSA_RT_V)) oa->trcap=1;
+	rtl=(struct ospf_lsa_rt_link *)(rt+1);
+	for(i=0;rt->links;i++)
+	{
+	  tmp=NULL;
+	  switch((rtl+i)->type)
+	  {
+            case LSART_STUB:
+	    case LSART_VLNK:
+	      continue;
+	      break;
+	    case LSART_NET:
+	      tmp=ospf_hash_find(oa->gr,rtl->data,rtl->id,LSA_T_RT);
+	      break;
+	    case LSART_PTP:
+	      tmp=ospf_hash_find(oa->gr,rtl->data,rtl->id,LSA_T_NET);
+	      break;
+	    default:
+	      log("Unknown link type in router lsa.\n");
+	      break;
+	  }
+	  add_cand(&oa->cand,tmp,act->dist+rtl->metric,sl);
+	}
+        break;
+      case LSA_T_NET:
+	net=(struct ospf_lsa_net *)act->lsa_body;
+	rts=(u32 *)(net+1);
+	for(i=0;i<(act->lsa.length-sizeof(struct ospf_lsa_header)-
+	  sizeof(struct ospf_lsa_net))/sizeof(u32);i++)
+	{
+	  tmp=ospf_hash_find(oa->gr, *rts, *rts, LSA_T_RT);
+          add_cand(&oa->cand,tmp,act->dist,sl);
+	}
+        break;
+    }
+  }
+}
+
+void
+add_cand(list *l, struct top_hash_entry *en, u16 dist, slab *s)
+{
+  struct spf_n *tmp;
+  node *prev;
+  int flag=0;
+
+  if(en==NULL) return;
+  if(en->lsa.age==LSA_MAXAGE) return;
+  /* FIXME Does it have link back? Test it! */
+  if(en->color==INSPF) return;
+
+  if(dist>en->dist) return;
+  
+  if(dist==en->dist)
+  {
+    //Next hop calc
+  }
+  else
+  {
+    /* Clear next hop */
+
+    if(en->color==CANDIDATE)
+    {
+      WALK_LIST(tmp,*l)
+      {
+        if(tmp->en==en)
+	{
+	  rem_node(NODE tmp);
+	  flag=1;
+	  break;
+	}
+      }
+    }
+
+    if(flag!=1)
+    {
+      tmp=sl_alloc(s);
+      tmp->en=en;
+    }
+
+    en->dist=dist;
+    en->color=CANDIDATE;
+
+    prev=NULL;
+
+    WALK_LIST(tmp,*l)
+    {
+      if(tmp->en->dist>dist)
+      {
+        if(prev==NULL) add_head(l,NODE tmp);
+	else insert_node(NODE tmp,prev);
+        break;
+      }
+    }
+  }
+}
diff --git a/proto/ospf/rt.h b/proto/ospf/rt.h
new file mode 100644
index 0000000..6eb0bcc
--- /dev/null
+++ b/proto/ospf/rt.h
@@ -0,0 +1,16 @@
+/*
+ *      BIRD -- OSPF
+ *
+ *      (c) 2000 Ondrej Filip <feela@network.cz>
+ *
+ *      Can be freely distributed and used under the terms of the GNU GPL.
+ *
+ */
+
+#ifndef _BIRD_OSPF_RT_H_
+#define _BIRD_OSPF_RT_H_
+
+void ospf_rt_spfa(struct ospf_area *oa, struct proto *p);
+void add_cand(list *l, struct top_hash_entry *en, u16 dist, slab *s);
+
+#endif /* _BIRD_OSPF_RT_H_ */
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index 2200aa2..687b889 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -175,7 +175,7 @@ addifa_rtlsa(struct ospf_iface *ifa)
   {
     struct ospf_lsa_header *lsa;
 
-    oa=mb_alloc(po->proto.pool, sizeof(struct ospf_area));
+    oa=mb_allocz(po->proto.pool, sizeof(struct ospf_area));
     add_tail(&po->area_list,NODE oa);
     oa->areaid=ifa->an;
     oa->gr=ospf_top_new(po);
diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h
index e146c6f..032a977 100644
--- a/proto/ospf/topology.h
+++ b/proto/ospf/topology.h
@@ -15,6 +15,13 @@ struct top_hash_entry {  /* Index for fast mapping (type,rtrid,LSid)->vertex */
   struct ospf_lsa_header lsa;
   void *lsa_body;
   bird_clock_t inst_t;			/* Time of installation into DB */
+  list nh;				/* List of next hops */
+  u16 dist;				/* Distance from the root */
+  u8 color;
+#define OUTSPF 0
+#define CANDIDATE 1
+#define INSPF 2
+  u8 padding;
 };
 
 struct top_graph {