[PATCH] [ospfd] Optimize and improve SPF nexthop calculation

Joakim Tjernlund Joakim.Tjernlund at transmode.se
Tue Jun 3 18:41:28 CEST 2008


Maintain a table of OSPF interface pointers paralell
to the router LSA. Use the table in nexthop_calculation to
find the right OSPF interface for the nexthop.
This has the following advantages:
- Possible to have multiple PtP interfaces with the same
  IP address between two routers.
- Possible to use Unnumbered PtP on just one end of
  the link.
- No more seaching for the OSPF interface, hence much faster.
---
 ospfd/ospf_interface.c |    2 +
 ospfd/ospf_lsa.c       |   91 +++++++++++++++++++++++++++--
 ospfd/ospf_lsa.h       |   12 ++++
 ospfd/ospf_spf.c       |  151 +++++++++++++++++++++++++---------------=
-------
 4 files changed, 179 insertions(+), 77 deletions(-)

diff --git a/ospfd/ospf_interface.c b/ospfd/ospf_interface.c
index afe3acf..fc39a81 100644
--- a/ospfd/ospf_interface.c
+++ b/ospfd/ospf_interface.c
@@ -335,6 +335,8 @@ ospf_if_free (struct ospf_interface *oi)
   listnode_delete (oi->ospf->oiflist, oi);
   listnode_delete (oi->area->oiflist, oi);

+  ospf_oi_seq_if_delete(oi);
+
   memset (oi, 0, sizeof (*oi));
   XFREE (MTYPE_OSPF_IF, oi);
 }
diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c
index 0ba1834..a12dd7a 100644
--- a/ospfd/ospf_lsa.c
+++ b/ospfd/ospf_lsa.c
@@ -241,6 +241,27 @@ ospf_lsa_dup (struct ospf_lsa *lsa)
   return new;
 }

+static void
+ospf_lsa_oi_seq_free (struct lsa_oi_seq *oi_seq)
+{
+  XFREE (MTYPE_OSPF_LSA_DATA, oi_seq->seq_nr);
+  XFREE (MTYPE_OSPF_LSA_DATA, oi_seq);
+}
+
+void
+ospf_oi_seq_if_delete(struct ospf_interface *oi)
+{
+  int i;
+  struct ospf_lsa *lsa =3D oi->area->router_lsa_self;
+
+  if (!lsa || !lsa->oi_seq)
+    return;
+  /* "delete" all entries of oi */
+  for (i=3D0; i < lsa->oi_seq->length/sizeof(seq_nr_t); i++)
+    if (lsa->oi_seq->seq_nr[i] =3D=3D oi)
+      lsa->oi_seq->seq_nr[i] =3D NULL;
+}
+
 /* Free OSPF LSA. */
 void
 ospf_lsa_free (struct ospf_lsa *lsa)
@@ -254,6 +275,8 @@ ospf_lsa_free (struct ospf_lsa *lsa)
   if (lsa->data !=3D NULL)
     ospf_lsa_data_free (lsa->data);

+  if (lsa->oi_seq !=3D NULL)
+    ospf_lsa_oi_seq_free (lsa->oi_seq);
   assert (lsa->refresh_list < 0);

   memset (lsa, 0, sizeof (struct ospf_lsa));
@@ -306,6 +329,24 @@ ospf_lsa_data_new (size_t size)
   return XCALLOC (MTYPE_OSPF_LSA_DATA, size);
 }

+static struct lsa_oi_seq *
+ospf_lsa_oi_seq_new (void)
+{
+  struct lsa_oi_seq *new;
+
+  new =3D XCALLOC (MTYPE_OSPF_LSA_DATA, sizeof(*new));
+  return new;
+}
+
+static seq_nr_t *
+ospf_lsa_oi_seq_data_new (size_t size)
+{
+  seq_nr_t *new;
+
+  new =3D XMALLOC (MTYPE_OSPF_LSA_DATA, size);
+  return new;
+}
+
 /* Duplicate LSA data. */
 struct lsa_header *
 ospf_lsa_data_dup (struct lsa_header *lsah)
@@ -318,6 +359,18 @@ ospf_lsa_data_dup (struct lsa_header *lsah)
   return new;
 }

+static void *
+ospf_lsa_oi_seq_dup (struct lsa_oi_seq *oi_seq)
+{
+  struct lsa_oi_seq *new;
+
+  new =3D ospf_lsa_oi_seq_new ();
+  new->length =3D oi_seq->length;
+  new->seq_nr =3D ospf_lsa_oi_seq_data_new (oi_seq->length);
+  memcpy (new->seq_nr, oi_seq->seq_nr, oi_seq->length);
+  return new;
+}
+
 /* Free LSA data. */
 void
 ospf_lsa_data_free (struct lsa_header *lsah)
@@ -653,13 +706,24 @@ lsa_link_ptomp_set (struct stream *s, struct ospf=
_interface *oi)
   return links;
 }

+struct ospf_interface *
+router_lsa_to_oi(struct ospf_lsa *lsa, int index)
+{
+  if (lsa->oi_seq && index >=3D 0)
+    return lsa->oi_seq->seq_nr[index];
+
+  zlog_debug ("%s: oi_seq:%p, index:%d!",
+	      __func__, lsa->oi_seq, index);
+  return NULL;
+}
 /* Set router-LSA link information. */
 static int
-router_lsa_link_set (struct stream *s, struct ospf_area *area)
+router_lsa_link_set (struct stream *s, seq_nr_t oi_list[],
+		     struct ospf_area *area)
 {
   struct listnode *node;
   struct ospf_interface *oi;
-  int links =3D 0;
+  int links =3D 0, old_links, i;

   for (ALL_LIST_ELEMENTS_RO (area->oiflist, node, oi))
     {
@@ -670,6 +734,7 @@ router_lsa_link_set (struct stream *s, struct ospf_=
area *area)
 	{
 	  if (oi->state !=3D ISM_Down)
 	    {
+	      old_links =3D links;
 	      /* Describe each link. */
 	      switch (oi->type)
 		{
@@ -691,6 +756,8 @@ router_lsa_link_set (struct stream *s, struct ospf_=
area *area)
 		case OSPF_IFTYPE_LOOPBACK:
 		  links +=3D lsa_link_loopback_set (s, oi);
 		}
+	      for (i =3D old_links; i < links; i++)
+		oi_list[i] =3D oi;
 	    }
 	}
     }
@@ -699,8 +766,9 @@ router_lsa_link_set (struct stream *s, struct ospf_=
area *area)
 }

 /* Set router-LSA body. */
-static void
-ospf_router_lsa_body_set (struct stream *s, struct ospf_area *area)
+static  u_int16_t
+ospf_router_lsa_body_set (struct stream *s, seq_nr_t oi_list[],
+			  struct ospf_area *area)
 {
   unsigned long putp;
   u_int16_t cnt;
@@ -718,10 +786,12 @@ ospf_router_lsa_body_set (struct stream *s, struc=
t ospf_area *area)
   stream_putw(s, 0);

   /* Set all link information. */
-  cnt =3D router_lsa_link_set (s, area);
+  cnt =3D router_lsa_link_set (s, oi_list, area);

   /* Set # of links here. */
   stream_putw_at (s, putp, cnt);
+
+  return cnt;
 }

 static int
@@ -790,6 +860,9 @@ ospf_router_lsa_new (struct ospf_area *area)
   struct lsa_header *lsah;
   struct ospf_lsa *new;
   int length;
+  u_int16_t cnt;
+ /* oi_list, less than 1KB, allocat on stack */
+  seq_nr_t oi_list[((OSPF_MAX_LSA_SIZE*2)/3)/sizeof(seq_nr_t)];

   if (IS_DEBUG_OSPF (lsa, LSA_GENERATE))
     zlog_debug ("LSA[Type1]: Create router-LSA instance");
@@ -806,7 +879,8 @@ ospf_router_lsa_new (struct ospf_area *area)
 		  OSPF_ROUTER_LSA, ospf->router_id, ospf->router_id);

   /* Set router-LSA body fields. */
-  ospf_router_lsa_body_set (s, area);
+  memset(oi_list, 0, sizeof(oi_list));
+  cnt =3D ospf_router_lsa_body_set (s, oi_list, area);

   /* Set length. */
   length =3D stream_get_endp (s);
@@ -826,6 +900,11 @@ ospf_router_lsa_new (struct ospf_area *area)
   /* Copy LSA data to store, discard stream. */
   new->data =3D ospf_lsa_data_new (length);
   memcpy (new->data, lsah, length);
+
+  new->oi_seq =3D ospf_lsa_oi_seq_new ();
+  new->oi_seq->length =3D cnt*sizeof(seq_nr_t);
+  new->oi_seq->seq_nr =3D ospf_lsa_oi_seq_data_new (new->oi_seq->lengt=
h);
+  memcpy (new->oi_seq->seq_nr, oi_list, new->oi_seq->length);
   stream_free (s);

   return new;
diff --git a/ospfd/ospf_lsa.h b/ospfd/ospf_lsa.h
index 8dd054c..7bee1dc 100644
--- a/ospfd/ospf_lsa.h
+++ b/ospfd/ospf_lsa.h
@@ -68,6 +68,13 @@ struct lsa_header
   u_int16_t length;
 };

+#define seq_nr_t struct ospf_interface *
+/* Router LSA sequnce number list */
+struct lsa_oi_seq {
+  u_int16_t length;
+  seq_nr_t *seq_nr;
+};
+
 /* OSPF LSA. */
 struct ospf_lsa
 {
@@ -84,6 +91,9 @@ struct ospf_lsa
   /* LSA data. */
   struct lsa_header *data;

+  /* Router LSA OI sequence number */
+  struct lsa_oi_seq *oi_seq;
+
   /* Received time stamp. */
   struct timeval tv_recv;

@@ -247,10 +257,12 @@ extern void ospf_lsa_free (struct ospf_lsa *);
 extern struct ospf_lsa *ospf_lsa_lock (struct ospf_lsa *);
 extern void ospf_lsa_unlock (struct ospf_lsa **);
 extern void ospf_lsa_discard (struct ospf_lsa *);
+extern struct ospf_interface * router_lsa_to_oi(struct ospf_lsa *, int=
);

 extern struct lsa_header *ospf_lsa_data_new (size_t);
 extern struct lsa_header *ospf_lsa_data_dup (struct lsa_header *);
 extern void ospf_lsa_data_free (struct lsa_header *);
+extern void ospf_oi_seq_if_delete(struct ospf_interface *);

 /* Prototype for various LSAs */
 extern int ospf_router_lsa_update_timer (struct thread *);
diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
index 610fc9b..07a31c5 100644
--- a/ospfd/ospf_spf.c
+++ b/ospfd/ospf_spf.c
@@ -480,13 +480,16 @@ ospf_spf_add_parent (struct vertex *v, struct ver=
tex *w,
 static unsigned int
 ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
                           struct vertex *w, struct router_lsa_link *l,=

-                          unsigned int distance)
+                          unsigned int distance, int lsa_pos)
 {
   struct listnode *node, *nnode;
   struct vertex_nexthop *nh;
   struct vertex_parent *vp;
   struct ospf_interface *oi =3D NULL;
   unsigned int added =3D 0;
+  char buf1[BUFSIZ];
+  char buf2[BUFSIZ];
+

   if (IS_DEBUG_OSPF_EVENT)
     {
@@ -505,30 +508,41 @@ ospf_nexthop_calculation (struct ospf_area *area,=
 struct vertex *v,
          the OSPF interface connecting to the destination network/rout=
er.
       */

+      /* we *must* be supplied with the link data */
+      assert (l !=3D NULL);
+
+      oi =3D router_lsa_to_oi(area->router_lsa_self, lsa_pos);
+      if (!oi)
+	{
+	  zlog_debug("%s: OI not found in LSA: lsa_pos:%d link_id:%s link_dat=
a:%s",
+		     __func__, lsa_pos,
+		     inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
+		     inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
+	  return 0;
+	}
+
       if (w->type =3D=3D OSPF_VERTEX_ROUTER)
         {
           /* l  is a link from v to w
            * l2 will be link from w to v
            */
           struct router_lsa_link *l2 =3D NULL;
-
-          /* we *must* be supplied with the link data */
-          assert (l !=3D NULL);
-
+
           if (IS_DEBUG_OSPF_EVENT)
             {
-              char buf1[BUFSIZ];
-              char buf2[BUFSIZ];
-
-              zlog_debug("ospf_nexthop_calculation(): considering link=
 "
+              zlog_debug("%s: considering link "
                         "type %d link_id %s link_data %s",
-                        l->m[0].type,
+			 __func__, l->m[0].type,
                         inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ)=
,
                         inet_ntop (AF_INET, &l->link_data, buf2, BUFSI=
Z));
             }

           if (l->m[0].type =3D=3D LSA_LINK_TYPE_POINTOPOINT)
             {
+	      int nh_found =3D 0;
+	      struct in_addr nexthop;
+	      unsigned long ifindex;
+
               /* If the destination is a router which connects to
                  the calculating router via a Point-to-MultiPoint
                  network, the destination's next hop IP address(es)
@@ -548,59 +562,50 @@ ospf_nexthop_calculation (struct ospf_area *area,=
 struct vertex *v,
                  is a constituent of the PtMP link, and its address is=

                  a nexthop address for V.
               */
-              oi =3D ospf_if_is_configured (area->ospf, &l->link_data)=
;
-              if (oi && oi->type =3D=3D OSPF_IFTYPE_POINTOMULTIPOINT)
-                {
-                  struct prefix_ipv4 la;
-
-                  la.family =3D AF_INET;
-                  la.prefixlen =3D oi->address->prefixlen;
-
-                  /* V links to W on PtMP interface
-                     - find the interface address on W */
-                  while ((l2 =3D ospf_get_next_link (w, v, l2)))
-                    {
-                      la.prefix =3D l2->link_data;
-
-                      if (prefix_cmp ((struct prefix *) &la,
-                                      oi->address) =3D=3D 0)
-                        /* link_data is on our PtMP network */
-                        break;
-                    }
-                } /* end l is on point-to-multipoint link */
-              else
-                {
-                  /* l is a regular point-to-point link.
-                     Look for a link from W to V.
-                   */
-                  while ((l2 =3D ospf_get_next_link (w, v, l2)))
-                    {
-                      oi =3D ospf_if_is_configured (area->ospf,
-                                                  &(l2->link_data));
-
-                      if (oi =3D=3D NULL)
-                        continue;
-
-                      if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
-                                           &l->link_data))
-                        continue;
-
-                      break;
-                    }
-                }
-
-              if (oi && l2)
+	      if (oi->type =3D=3D OSPF_IFTYPE_POINTOPOINT)
+		{
+		  if (ntohl(l->link_data.s_addr) <=3D 0x00ffffff)
+		    nh_found =3D 1; /* Unnumbered */
+		  else if (IPV4_ADDR_SAME (&oi->address->u.prefix4,
+					   &l->link_data))
+		    nh_found =3D 1;
+		  nexthop.s_addr =3D 0; /* Nexthop not required */
+		}
+	      else if (oi->type =3D=3D OSPF_IFTYPE_POINTOMULTIPOINT)
+		{
+		  struct prefix_ipv4 la;
+
+		  la.family =3D AF_INET;
+		  la.prefixlen =3D oi->address->prefixlen;
+
+		  /* V links to W on PtMP interface
+		     - find the interface address on W */
+		  while ((l2 =3D ospf_get_next_link (w, v, l2)))
+		    {
+		      la.prefix =3D l2->link_data;
+
+		      if (prefix_cmp ((struct prefix *) &la,
+				      oi->address) !=3D 0)
+			continue;
+		      /* link_data is on our PtMP network */
+		      nh_found =3D 1;
+		      nexthop =3D l2->link_data;
+		      break;
+		    }
+		}
+
+              if (nh_found)
                 {
                   /* found all necessary info to build nexthop */
                   nh =3D vertex_nexthop_new ();
                   nh->oi =3D oi;
-                  nh->router =3D l2->link_data;
+                  nh->router =3D nexthop;
                   ospf_spf_add_parent (v, w, nh, distance);
                   return 1;
                 }
               else
-                zlog_info("ospf_nexthop_calculation(): "
-                          "could not determine nexthop for link");
+                zlog_info("%s: could not determine nexthop for link",
+			  __func__);
             } /* end point-to-point link from V to W */
           else if (l->m[0].type =3D=3D LSA_LINK_TYPE_VIRTUALLINK)
             {
@@ -633,19 +638,22 @@ ospf_nexthop_calculation (struct ospf_area *area,=
 struct vertex *v,
       else
         {
           assert(w->type =3D=3D OSPF_VERTEX_NETWORK);
-          oi =3D ospf_if_is_configured (area->ospf, &(l->link_data));
-          if (oi)
+	  if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
+			       &l->link_data))
             {
-              nh =3D vertex_nexthop_new ();
-              nh->oi =3D oi;
-              nh->router.s_addr =3D 0;
-              ospf_spf_add_parent (v, w, nh, distance);
-              return 1;
-            }
+	      zlog_info("%s: Interface %s:%s does not match Link Data:%s",
+			__func__, oi->ifp->name,
+			inet_ntop (AF_INET, &oi->address->u.prefix4, buf1, BUFSIZ),
+			inet_ntop (AF_INET, &l->link_id, buf2, BUFSIZ));
+	      return 0;
+	    }
+
+	  nh =3D vertex_nexthop_new ();
+	  nh->oi =3D oi;
+	  nh->router.s_addr =3D 0;
+	  ospf_spf_add_parent (v, w, nh, distance);
+	  return 1;
         }
-      zlog_info("ospf_nexthop_calculation(): "
-                "Unknown attached link");
-      return 0;
     } /* end V is the root */
   /* Check if W's parent is a network connected to root. */
   else if (v->type =3D=3D OSPF_VERTEX_NETWORK)
@@ -714,7 +722,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *=
area,
   u_char *lim;
   struct router_lsa_link *l =3D NULL;
   struct in_addr *r;
-  int type =3D 0;
+  int type =3D 0, lsa_pos=3D-1, lsa_pos_next=3D0;

   /* If this is a router-LSA, and bit V of the router-LSA (see Section=

      A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE.  *=
/
@@ -742,7 +750,8 @@ ospf_spf_next (struct vertex *v, struct ospf_area *=
area,
       if (v->lsa->type =3D=3D OSPF_ROUTER_LSA)
         {
           l =3D (struct router_lsa_link *) p;
-
+	  lsa_pos =3D lsa_pos_next; /* LSA link position */
+	  lsa_pos_next++;
           p +=3D (ROUTER_LSA_MIN_SIZE +
                 (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));

@@ -864,7 +873,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *=
area,
           w =3D ospf_vertex_new (w_lsa);

           /* Calculate nexthop to W. */
-          if (ospf_nexthop_calculation (area, v, w, l, distance))
+          if (ospf_nexthop_calculation (area, v, w, l, distance, lsa_p=
os))
             pqueue_enqueue (w, candidate);
           else if (IS_DEBUG_OSPF_EVENT)
             zlog_debug ("Nexthop Calc failed");
@@ -884,7 +893,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *=
area,
             {
 	      /* Found an equal-cost path to W.
                * Calculate nexthop of to W from V. */
-              ospf_nexthop_calculation (area, v, w, l, distance);
+	      ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos);
             }
            /* less than. */
 	  else
@@ -894,7 +903,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *=
area,
                * valid nexthop it will call spf_add_parents, which
                * will flush the old parents
                */
-              if (ospf_nexthop_calculation (area, v, w, l, distance))
+	      if (ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos)=
)
                 /* Decrease the key of the node in the heap.
                  * trickle-sort it up towards root, just in case this
                  * node should now be the new root due the cost change=
.
--
1.6.4.4





More information about the Bird-users mailing list