LSA DB is completely redesigned. Now it should be faster and it needs

less memory.

5 files changed, 253 insertions, 90 deletions

diff --git a/proto/ospf/dbdes.c b/proto/ospf/dbdes.c
index 43d60a3..eb65b5f 100644
--- a/proto/ospf/dbdes.c
+++ b/proto/ospf/dbdes.c
@@ -9,6 +9,32 @@
 #include "ospf.h"
 
 void
+htonlsah(struct ospf_lsa_header *h, struct ospf_lsa_header *n)
+{
+  n->age=htons(h->age);
+  n->options=h->options;
+  n->type=h->type;
+  n->id=htonl(h->id);
+  n->rt=htonl(h->rt);
+  n->sn=htonl(h->sn);
+  n->checksum=htons(h->checksum);
+  n->length=htons(h->length);
+};
+
+void
+ntohlsah(struct ospf_lsa_header *n, struct ospf_lsa_header *h)
+{
+  h->age=ntohs(n->age);
+  h->options=n->options;
+  h->type=n->type;
+  h->id=ntohl(n->id);
+  h->rt=ntohl(n->rt);
+  h->sn=ntohl(n->sn);
+  h->checksum=ntohs(n->checksum);
+  h->length=ntohs(n->length);
+};
+	
+void
 ospf_dbdes_tx(struct ospf_neighbor *n)
 {
   struct ospf_dbdes_packet *pkt;
@@ -44,7 +70,7 @@ ospf_dbdes_tx(struct ospf_neighbor *n)
       if(! ((IAMMASTER(n->myimms) && (n->dds==n->ddr+1)) || ((!IAMMASTER(n->myimms)) && (n->dds==n->ddr))))
       {
         snode *sn;			/* Send next */
-        struct ospf_lsaheader *lsa;
+        struct ospf_lsa_header *lsa;
 	
         fill_ospf_pkt_hdr(ifa, pkt, DBDES);
         pkt->iface_mtu= ifa->iface->mtu;
@@ -52,7 +78,8 @@ ospf_dbdes_tx(struct ospf_neighbor *n)
 	pkt->ddseq=n->dds;
 
 	sn=s_get(&(n->dbsi));
-	j=i=(pkt->iface_mtu-sizeof(struct ospf_dbdes_packet))/sizeof(struct ospf_lsaheader);	/* Number of lsaheaders */
+	j=i=(pkt->iface_mtu-sizeof(struct ospf_dbdes_packet))/
+		sizeof(struct ospf_lsa_header);	/* Number of lsaheaders */
 	lsa=(n->ldbdes+sizeof(struct ospf_dbdes_packet));
 
 	for(;i>0;i--)
@@ -60,14 +87,7 @@ ospf_dbdes_tx(struct ospf_neighbor *n)
 	  struct top_hash_entry *en;
 	  
 	  en=(struct top_hash_entry *)sn;
-	  lsa->lsage=htons(en->lsage);
-	  lsa->options=htons(en->options);
-	  lsa->lstype=htons(en->lsa_type);
-	  lsa->lsid=htons(en->lsa_id);
-	  lsa->advr=htons(en->rtr_id);
-	  lsa->lssn=htons(en->lsseqno);
-	  lsa->length=htons(en->length);
-	  lsa->checksum=htons(en->checksum);
+	  htonlsah(&(en->lsa), lsa);
 	  if(sn->next==NULL)
 	  {
 	    break;	/* Should set some flag? */
@@ -83,7 +103,8 @@ ospf_dbdes_tx(struct ospf_neighbor *n)
 
         pkt->imms=n->myimms;
 
-	length=j*sizeof(struct ospf_lsaheader)+sizeof(struct ospf_dbdes_packet);
+	length=j*sizeof(struct ospf_lsa_header)+
+		sizeof(struct ospf_dbdes_packet);
 	op->length=htons(length);
         ospf_pkt_finalize(ifa, op);
         sk_send_to(ifa->ip_sk,length, n->ip, OSPF_PROTO);
diff --git a/proto/ospf/neighbor.c b/proto/ospf/neighbor.c
index 1470b83..f348586 100644
--- a/proto/ospf/neighbor.c
+++ b/proto/ospf/neighbor.c
@@ -206,7 +206,9 @@ ospf_neigh_sm(struct ospf_neighbor *n, int event)
         neigh_chstate(n,NEIGHBOR_EXCHANGE);
         s_init_list(&(n->lsrql));
         s_init_list(&(n->lsrtl));
+	DBG("OK1\n");
 	s_init(&(n->dbsi), &(n->ifa->oa->lsal));
+	DBG("OK2\n");
 	ospf_dbdes_tx(n);
       }
       break;
diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h
index 18db001..6ea8833 100644
--- a/proto/ospf/ospf.h
+++ b/proto/ospf/ospf.h
@@ -148,18 +148,82 @@ struct ospf_dbdes_packet {
   u32 ddseq;
 };
 
-struct ospf_lsaheader {
-  u16 lsage;		/* LS Age */
+
+struct ospf_lsa_header {
+  u16 age;	/* LS Age */
+#define LSA_MAXAGE 3600                 /* 1 hour */
+#define LSA_CHECKAGE 300                /* 5 minutes */
+#define LSA_MAXAGEDIFF 900              /* 15 minutes */
   u8 options;
-  u8 lstype;
-  u32 lsid;		
-  u32 advr;		/* Advertising router */
-  u32 lssn;		/* LS Sequence number */
+  u8 type;
+  u32 id;
+#define LSA_T_RT 1
+#define LSA_T_NET 2
+#define LSA_T_SUM_NET 3
+#define LSA_T_SUM_RT 4
+#define LSA_T_EXT 5
+  u32 rt;		/* Advertising router */
+  u32 sn;		/* LS Sequence number */
+#define LSA_INITSEQNO 0x80000001
+#define LSA_MAXSEQNO 0x7fffffff
   u16 checksum;
-  u16 length;
+  u16 length;  
+};
+
+struct ospf_lsa_rt {
+  u8 VEB;
+#define LSA_RT_V 5
+#define LSA_RT_E 6
+#define LSA_RT_B 7
+  u8 padding;
+  u16 links;
+};
+
+struct ospf_lsa_rt_link {
+  u32 id;
+  u32 data;
+  u8 type;
+#define LSART_PTP 1
+#define LSART_NET 2
+#define LSART_STUB 3
+#define LSART_VLNK 4
+  u8 notos;
+  u16 metric;
+};
+
+struct ospf_lsa_rt_link_tos {	/* Actually we ignore TOS. This is useless */
+  u8 tos;
+  u8 padding;
+  u16 metric;
 };
 
 
+struct ospf_lsa_net {
+  u32 netmask;
+};
+
+struct ospf_lsa_summ {
+  u32 netmask;
+};
+
+struct ospf_lsa_summ_net {
+  u8 tos;
+  u8 padding;
+  u16 metric;
+};
+
+struct ospf_lsa_ext {
+  u32 netmask;
+};
+
+struct ospf_lsa_ext_tos {
+  u8 etos;
+  u8 padding;
+  u16 mertic;
+  u32 fwaddr;
+  u32 tag;
+};
+
 struct ospf_neighbor
 {
   node n;
@@ -223,7 +287,7 @@ 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 */
-  slab *rtlinks;
+  int stub;
 };
 
 struct proto_ospf {
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index ad88f01..ae49228 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -24,12 +24,140 @@
 #define HASH_LO_MIN 8
 
 void
+make_rt_lsa(struct ospf_area *oa, struct proto_ospf *p)
+{
+  struct ospf_iface *ifa;
+  int i=0,j=0,k=0,v=0,e=0,b=0;
+  struct ospf_lsa_rt *rt;
+  struct ospf_lsa_rt_link *ln;
+  struct ospf_neighbor *neigh;
+  struct top_hash_entry *old;
+
+  old=oa->rt;
+
+  WALK_LIST (ifa, p->iface_list) i++;
+  {
+    if((ifa->an==oa->areaid) && (ifa->state!=OSPF_IS_DOWN))
+    {
+      i++;
+      if(ifa->type==OSPF_IT_VLINK) v=1;
+    }
+  }
+  rt=mb_allocz(p->proto.pool, sizeof(struct ospf_lsa_rt)+
+    i*sizeof(struct ospf_lsa_rt_link));
+  if((p->areano>1) && (!oa->stub)) e=1;
+  rt->VEB=(v>>LSA_RT_V)+(e>>LSA_RT_E)+(b>>LSA_RT_B);
+  ln=(struct ospf_lsa_rt_link *)(rt+1);
+
+  WALK_LIST (ifa, p->iface_list)
+  {
+    if((ifa->an==oa->areaid) && (ifa->state!=OSPF_IS_DOWN))
+    {
+      if(ifa->state==OSPF_IS_LOOP)
+      {
+        ln->type=3;
+	ln->id=ipa_to_u32(ifa->iface->addr->ip);
+	ln->data=0xffffffff;
+	ln->metric=0;
+	ln->notos=0;
+      }
+      else
+      {
+        switch(ifa->type)
+	{
+          case OSPF_IT_PTP:		/* rfc2328 - pg126 */
+            neigh=(struct ospf_neighbor *)HEAD(ifa->neigh_list);
+	    if((neigh!=NULL) || (neigh->state==NEIGHBOR_FULL))
+	    {
+               ln->type=LSART_PTP;
+               ln->id=neigh->rid;
+               ln->metric=ifa->cost;
+               ln->notos=0;
+               if(ifa->iface->flags && IA_UNNUMBERED)
+               {
+                 ln->data=ifa->iface->index;
+               }
+               else
+               {
+                 ln->id=ipa_to_u32(ifa->iface->addr->ip);
+               }
+	    }
+	    else
+	    {
+	      if(ifa->state==OSPF_IS_PTP)
+              {
+		ln->type=LSART_STUB;
+		ln->id=ln->id=ipa_to_u32(ifa->iface->addr->opposite);
+		ln->metric=ifa->cost;
+		ln->notos=0;
+		ln->data=0xffffffff;
+              }
+              else
+              {
+		i--; /* No link added */
+              }
+	    }
+            break;
+	  case OSPF_IT_BCAST: /*FIXME Go on */
+	  case OSPF_IT_NBMA:
+            if(ifa->state==OSPF_IS_WAITING)
+            {
+              ln->type=LSART_STUB;
+	      ln->id=ipa_to_u32(ifa->iface->addr->prefix);
+	      ln->data=ipa_to_u32(ipa_mkmask(ifa->iface->addr->pxlen));
+              ln->metric=ifa->cost;
+              ln->notos=0;
+            }
+	    else
+            {
+              j=0,k=0;
+              WALK_LIST(neigh, ifa->neigh_list)
+	      {
+	        if((neigh->rid==ifa->drid) &&
+	          (neigh->state==NEIGHBOR_FULL)) k=1;
+		if(neigh->state==NEIGHBOR_FULL) j=1;
+	      }
+              if(((ifa->state=OSPF_IS_DR) && (j==1)) || (k==1))
+	      {
+	        ln->type=LSART_NET;
+		ln->id=ipa_to_u32(ifa->drip);
+		ln->data=ipa_to_u32(ifa->iface->addr->ip);
+		ln->metric=ifa->cost;
+		ln->notos=0;
+	      }
+	      else
+	      {
+                ln->type=LSART_STUB;
+  	        ln->id=ipa_to_u32(ifa->iface->addr->prefix);
+	        ln->data=ipa_to_u32(ipa_mkmask(ifa->iface->addr->pxlen));
+                ln->metric=ifa->cost;
+                ln->notos=0;
+	      }
+            }
+	    break;
+	  case OSPF_IT_VLINK:	/* FIXME Add virtual links! */
+	    i--;
+	    break;
+	}
+      }
+      if(ifa->type==OSPF_IT_VLINK) v=1;
+    }
+    ln=(ln+1);
+  }
+  rt->links=i;
+  if(old->lsa_body!=NULL) mb_free(old->lsa_body);
+  old->lsa_body=rt;
+}
+	
+
+	
+void
 addifa_rtlsa(struct ospf_iface *ifa)
 {
   struct ospf_area *oa;
   struct proto_ospf *po;
   u32 rtid;
-  struct top_graph_rtlsa *rt;
+  struct top_hash_entry *rt;
   struct top_graph_rtlsa_link *li, *lih;
 
   po=ifa->proto;
@@ -53,37 +181,17 @@ addifa_rtlsa(struct ospf_iface *ifa)
     oa->areaid=ifa->an;
     oa->gr=ospf_top_new(po);
     s_init_list(&(oa->lsal));
-    oa->rtlinks=sl_new(po->proto.pool,
-      sizeof(struct top_graph_rtlsa_link));
     oa->rt=ospf_hash_get(oa->gr, rtid, rtid, LSA_T_RT);
     s_add_head(&(oa->lsal), (snode *)oa->rt);
-    rt=mb_alloc(po->proto.pool, sizeof(struct top_graph_rtlsa));
-    oa->rt->vertex=(void *)rt;
-    oa->rt->lsage=0;
-    oa->rt->lsseqno=LSA_INITSEQNO;	/* FIXME Check it latter */
-    rt->Vbit=0;
-    rt->Ebit= (po->areano++ ? 0 : 1);	/* If it's 1st area set 0 */
-    rt->Bbit=0;				/* FIXME Could read config */
+    oa->rt->lsa_body=NULL;
+    oa->rt->lsa.age=0;
+    oa->rt->lsa.sn=LSA_INITSEQNO-1;	/* FIXME Check it latter */
     DBG("%s: New OSPF area \"%d\" added.\n", po->proto.name, ifa->an);
 
-    if(po->areano==2)	/* We are attached to more than 2 areas! */
-    {
-      oa=po->firstarea;
-
-      while(oa!=NULL)
-      {
-        rt=(struct top_graph_rtlsa *)oa->rt->vertex;
-	rt->Ebit=1;
-        /*FIXME lsa_flood(oa->rt) */
-	
-        oa=oa->next;
-      }
-    }
-    else
-    {
-      /*FIXME lsa_flood(oa->rt) */;
-    }
   }
+  make_rt_lsa(oa, po);
+  /*FIXME seq no++ */
+  /*FIXME lsa_flood(oa->rt) */
 }
 
   
@@ -170,7 +278,7 @@ ospf_top_rehash(struct top_graph *f, int step)
       while (e)
 	{
 	  x = e->next;
-	  n = newt + ospf_top_hash(f, e->lsa_id, e->rtr_id, e->lsa_type);
+	  n = newt + ospf_top_hash(f, e->lsa.id, e->lsa.rt, e->lsa.type);
 	  e->next = *n;
 	  *n = e;
 	  e = x;
@@ -184,7 +292,7 @@ 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))
+  while (e && (e->lsa.id != lsa || e->lsa.rt != rtr || e->lsa.type != type))
     e = e->next;
   return e;
 }
@@ -195,15 +303,15 @@ 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))
+  while (e && (e->lsa.id != lsa || e->lsa.rt != 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;
+  e->lsa.id = lsa;
+  e->lsa.rt = rtr;
+  e->lsa.type = type;
+  e->lsa_body = NULL;
   e->next=*ee;		/* MJ you forgot this :-) */
   *ee=e;
   if (f->hash_entries++ > f->hash_entries_max)
@@ -214,7 +322,7 @@ ospf_hash_get(struct top_graph *f, u32 lsa, u32 rtr, u32 type)
 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);
+  unsigned int h = ospf_top_hash(f, e->lsa.id, e->lsa.rt, e->lsa.type);
   struct top_hash_entry **ee = f->hash_table + h;
 
   while (*ee)
@@ -243,8 +351,8 @@ ospf_top_dump(struct top_graph *f)
       struct top_hash_entry *e = f->hash_table[i];
       while (e)
 	{
-	  debug("\t%04x %08x %08x %p\n", e->lsa_type, e->lsa_id,
-            e->rtr_id, e->vertex);
+	  debug("\t%04x %08x %08x %p\n", e->lsa.type, e->lsa.id,
+            e->lsa.rt, e->lsa_body);
 	  e = e->next;
 	}
     }
diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h
index 6a1aad5..9ebd0ed 100644
--- a/proto/ospf/topology.h
+++ b/proto/ospf/topology.h
@@ -12,23 +12,8 @@
 struct top_hash_entry {  /* Index for fast mapping (type,rtrid,LSid)->vertex */
    snode n;
   struct top_hash_entry *next;		/* Next in hash chain */
-  struct top_vertex *vertex;
-  u32 lsa_id, rtr_id;
-  u8 lsa_type;
-#define LSA_T_RT 1
-#define LSA_T_NET 2
-#define LSA_T_SUM_NET 3
-#define LSA_T_SUM_RT 4
-#define LSA_T_EXT 5
-  u8 options;
-  u16 lsage;
-#define LSA_MAXAGE 3600			/* 1 hour */
-#define LSA_CHECKAGE 300		/* 5 minutes */
-#define LSA_MAXAGEDIFF 900		/* 15 minutes */
-  u32 lsseqno;
-  u16 length, checksum;
-#define LSA_INITSEQNO 0x80000001
-#define LSA_MAXSEQNO 0x7fffffff
+  struct ospf_lsa_header lsa;
+  void *lsa_body;
 };
 
 struct top_graph {
@@ -50,21 +35,4 @@ struct top_hash_entry *ospf_hash_get(struct top_graph *, u32 lsa, u32 rtr, u32 t
 void ospf_hash_delete(struct top_graph *, struct top_hash_entry *);
 void addifa_rtlsa(struct ospf_iface *ifa);
 
-struct top_graph_rtlsa {
-  u8 Vbit;
-  u8 Ebit;
-  u8 Bbit;
-  int links;		/* Number of links */
-  struct top_graph_rtlsa_link *flink;
-};
-
-struct top_graph_rtlsa_link {	/* FIXME Completely ignoring TOS */
-  u32 id;
-  u32 data;
-  u8 type;
-  u16 metric;
-  struct top_graph_rtlsa_link *next;
-};
-
-
 #endif /* _BIRD_OSPF_TOPOLOGY_H_ */