ospfd: Optimize and improve SPF nexthop calculation

Maintain router LSA positions in OSPF interface.
    Find the OSPF interface in nexthop_calculation using
    the position in the router LSA.

    This has the following advantages:
    - Multiple numbered PtP interfaces with the same IP address
      between the same two routers.
    - Use Unnumbered PtP on just one end of the link.
    - Faster OI lookup for the OSPF interface and only
      done once for PtoP links.

*ospf_interface.h: (struct ospf_interface) Add storage for
		   storing router LSA position.

*ospf_interface.c: (ospf_if_lookup_by_lsa_pos)
		   lookup OSPF I/F in an area using LSA position.
		   (ospf_lsa_pos_set) assign LSA position to OSPF
		   interface.

*ospf_lsa.c: (router_lsa_link_set) Call ospf_lsa_pos_set() to record
             LSA position.

*ospf_spf.c: (ospf_spf_next) Count and pass along lsa position.
	     (ospf_nexthop_calculation) Add lsa position argument.
	     call ospf_if_lookup_by_lsa_pos() for OSFP interface handle.
	     Clean up and remove all calls ospf_if_is_configured() the
	     rest. Adjust a few debug logs.

1 files changed, 64 insertions, 96 deletions

diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
index f9ec11ba..fb863681 100644
--- a/ospfd/ospf_spf.c
+++ b/ospfd/ospf_spf.c
@@ -480,13 +480,15 @@ ospf_spf_add_parent (struct vertex *v, struct vertex *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 = NULL;
   unsigned int added = 0;
+  char buf1[BUFSIZ];
+  char buf2[BUFSIZ];
 
   if (IS_DEBUG_OSPF_EVENT)
     {
@@ -505,33 +507,37 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
          the OSPF interface connecting to the destination network/router.
       */
 
+      /* we *must* be supplied with the link data */
+      assert (l != NULL);
+      oi = ospf_if_lookup_by_lsa_pos (area, lsa_pos);
+      if (!oi)
+	{
+	  zlog_debug("%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%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 (IS_DEBUG_OSPF_EVENT)
+	{
+	  zlog_debug("%s: considering link:%s "
+		     "type:%d link_id:%s link_data:%s",
+		     __func__, oi->ifp->name, l->m[0].type,
+		     inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
+		     inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
+	}
+
       if (w->type == OSPF_VERTEX_ROUTER)
         {
           /* l  is a link from v to w
            * l2 will be link from w to v
            */
           struct router_lsa_link *l2 = NULL;
-          
-          /* we *must* be supplied with the link data */
-          assert (l != NULL);
-          
-          if (IS_DEBUG_OSPF_EVENT)
-            {
-              char buf1[BUFSIZ];
-              char buf2[BUFSIZ];
-              
-              zlog_debug("ospf_nexthop_calculation(): considering link "
-                        "type %d link_id %s link_data %s",
-                        l->m[0].type,
-                        inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
-                        inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
-            }
 
           if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT)
             {
-	      int nh_found = 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
@@ -543,75 +549,42 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
                  provides an IP address of the next hop router.
 
                  At this point l is a link from V to W, and V is the
-                 root ("us").  Find the local interface associated 
-                 with l (its address is in l->link_data).  If it
-                 is a point-to-multipoint interface, then look through
-                 the links in the opposite direction (W to V).  If
-                 any of them have an address that lands within the
+                 root ("us"). If it is a point-to-multipoint interface,
+		 then look through the links in the opposite direction (W to V).
+		 If any of them have an address that lands within the
                  subnet declared by the PtMP link, then that link
-                 is a constituent of the PtMP link, and its address is 
+                 is a constituent of the PtMP link, and its address is
                  a nexthop address for V.
               */
-	      ifindex = ntohl(l->link_data.s_addr);
-	      if (ifindex <= 0x00ffffff) /* unnumbered ? */
+	      if (oi->type == OSPF_IFTYPE_POINTOPOINT)
 		{
-		  oi = ospf_if_lookup_by_ifindex(area, ifindex);
-		  if (oi && oi->type == OSPF_IFTYPE_POINTOPOINT)
-		    nh_found = 1;
-		  nexthop.s_addr = 0;
+		  added = 1;
+		  nexthop.s_addr = 0; /* Nexthop not required */
 		}
-	      else
+	      else if (oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
 		{
-		  oi = ospf_if_is_configured (area->ospf, &l->link_data);
-		  if (oi && oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
-		    {
-		      struct prefix_ipv4 la;
-
-		      la.family = AF_INET;
-		      la.prefixlen = oi->address->prefixlen;
-
-		      /* V links to W on PtMP interface
-			 - find the interface address on W */
-		      while ((l2 = ospf_get_next_link (w, v, l2)))
-			{
-			  la.prefix = l2->link_data;
-
-			  if (prefix_cmp ((struct prefix *) &la,
-					  oi->address) != 0)
-			    continue;
-			  /* link_data is on our PtMP network */
-			  nh_found = 1;
-			  nexthop = l2->link_data;
-			  break;
-			}
-		    } /* end l is on point-to-multipoint link */
-		  else
+		  struct prefix_ipv4 la;
+
+		  la.family = AF_INET;
+		  la.prefixlen = oi->address->prefixlen;
+
+		  /* V links to W on PtMP interface
+		     - find the interface address on W */
+		  while ((l2 = ospf_get_next_link (w, v, l2)))
 		    {
-		      /* l is a regular point-to-point link.
-			 Look for a link from W to V.
-		      */
-		      while ((l2 = ospf_get_next_link (w, v, l2)))
-			{
-			  if (ntohl(l2->link_data.s_addr) <= 0x00ffffff)
-			    continue; /* skip unnumbered links */
-
-			  oi = ospf_if_is_configured (area->ospf,
-						      &l2->link_data);
-
-			  if (oi == NULL)
-			    continue;
-
-			  if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
-					       &l->link_data))
-			    continue;
-			  nexthop.s_addr = 0; /* zero better for equal-cost ? */
-			  nh_found = 1;
-			  break;
-			}
+		      la.prefix = l2->link_data;
+
+		      if (prefix_cmp ((struct prefix *) &la,
+				      oi->address) != 0)
+			continue;
+		      /* link_data is on our PtMP network */
+		      added = 1;
+		      nexthop = l2->link_data;
+		      break;
 		    }
 		}
 
-              if (nh_found)
+              if (added)
                 {
                   /* found all necessary info to build nexthop */
                   nh = vertex_nexthop_new ();
@@ -621,8 +594,8 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
                   return 1;
                 }
               else
-                zlog_info("ospf_nexthop_calculation(): "
-                          "could not determine nexthop for link");
+		zlog_info("%s: could not determine nexthop for link %s",
+			  __func__, oi->ifp->name);
             } /* end point-to-point link from V to W */
           else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
             {
@@ -655,19 +628,13 @@ ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
       else
         {
           assert(w->type == OSPF_VERTEX_NETWORK);
-          oi = ospf_if_is_configured (area->ospf, &(l->link_data));
-          if (oi)
-            {
-              nh = vertex_nexthop_new ();
-              nh->oi = oi;
-              nh->router.s_addr = 0;
-              ospf_spf_add_parent (v, w, nh, distance);
-              return 1;
-            }
+
+	  nh = vertex_nexthop_new ();
+	  nh->oi = oi;
+	  nh->router.s_addr = 0; /* Nexthop not required */
+	  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 == OSPF_VERTEX_NETWORK)
@@ -748,7 +715,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area,
   u_char *lim;
   struct router_lsa_link *l = NULL;
   struct in_addr *r;
-  int type = 0;
+  int type = 0, lsa_pos=-1, lsa_pos_next=0;
 
   /* 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.  */
@@ -776,7 +743,8 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area,
       if (v->lsa->type == OSPF_ROUTER_LSA)
         {
           l = (struct router_lsa_link *) p;
-
+	  lsa_pos = lsa_pos_next; /* LSA link position */
+	  lsa_pos_next++;
           p += (ROUTER_LSA_MIN_SIZE +
                 (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
 
@@ -898,7 +866,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area,
           w = 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_pos))
             pqueue_enqueue (w, candidate);
           else if (IS_DEBUG_OSPF_EVENT)
             zlog_debug ("Nexthop Calc failed");
@@ -918,7 +886,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
@@ -928,7 +896,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.