[PATCH 1/2] ospf: improve nexthop_calc

Joakim Tjernlund Joakim.Tjernlund at transmode.se
Fri Dec 17 10:03:32 CET 2010


Record the lsa position in the router LSA and
use that to find the right interface in calc_next_hop()
Remove match_rtlink and match_dr too as these are not
needed anymore

Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund at transmode.se>
---
 proto/ospf/iface.c    |    4 ++-
 proto/ospf/ospf.h     |   21 ++++++++++++++++
 proto/ospf/rt.c       |   63 ++++++++++++++-----------------------------------
 proto/ospf/topology.c |    5 ++-
 4 files changed, 45 insertions(+), 48 deletions(-)

diff --git a/proto/ospf/iface.c b/proto/ospf/iface.c
index 05442df..6fc0136 100644
--- a/proto/ospf/iface.c
+++ b/proto/ospf/iface.c
@@ -197,6 +197,8 @@ ospf_iface_down(struct ospf_iface *ifa)
     ifa->cost = 0;
     ifa->vip = IPA_NONE;
   }
+  /* delete position in router LSA */
+  ospf_lsa_pos_set(0, 0, ifa);
 }


@@ -412,7 +414,7 @@ ospf_iface_new(struct proto_ospf *po, struct iface *iface, struct ifa *addr,
   ifa->iface = iface;
   ifa->addr = addr;
   ifa->pool = pool;
-
+  ospf_lsa_pos_set(0, 0, ifa);
   ifa->cost = ip->cost;
   ifa->rxmtint = ip->rxmtint;
   ifa->inftransdelay = ip->inftransdelay;
diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h
index e260dc0..71071cd 100644
--- a/proto/ospf/ospf.h
+++ b/proto/ospf/ospf.h
@@ -190,6 +190,8 @@ struct ospf_iface
   u32 csn;                      /* Last used crypt seq number */
   bird_clock_t csn_use;         /* Last time when packet with that CSN was sent */
 #endif
+  u32 lsa_pos_beg; /* inclusive, >= */
+  u32 lsa_pos_end; /* exclusive, <  */

   ip_addr drip;			/* Designated router */
   ip_addr bdrip;		/* Backup DR */
@@ -823,6 +825,25 @@ void ospf_sh_iface(struct proto *p, char *iff);
 void ospf_sh_state(struct proto *p, int verbose, int reachable);
 void ospf_sh_lsadb(struct proto *p);

+static inline struct ospf_iface *
+ospf_pos_to_ifa (struct ospf_area *oa, int lsa_pos)
+{
+    struct proto_ospf *po = oa->po;
+    struct ospf_iface *ifa;
+
+    WALK_LIST(ifa, po->iface_list)
+	if (lsa_pos >= ifa->lsa_pos_beg && lsa_pos < ifa->lsa_pos_end)
+	    return ifa;
+    return NULL;
+}
+
+static inline void
+ospf_lsa_pos_set(int beg, int end,
+		 struct ospf_iface * ifa)
+{
+    ifa->lsa_pos_beg = beg;
+    ifa->lsa_pos_end = end;
+}

 #define EA_OSPF_METRIC1	EA_CODE(EAP_OSPF, 0)
 #define EA_OSPF_METRIC2	EA_CODE(EAP_OSPF, 1)
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
index 953a679..84fea16 100644
--- a/proto/ospf/rt.c
+++ b/proto/ospf/rt.c
@@ -10,7 +10,7 @@

 static void add_cand(list * l, struct top_hash_entry *en,
 		     struct top_hash_entry *par, u32 dist,
-		     struct ospf_area *oa, struct ospf_lsa_rt_link *rtl);
+		     struct ospf_area *oa, struct ospf_lsa_rt_link *rtl, u32 pos);
 static void rt_sync(struct proto_ospf *po);

 /* In ospf_area->rtr we store paths to routers, but we use RID (and not IP address)
@@ -396,7 +396,7 @@ ospf_rt_spfa_rtlinks(struct ospf_area *oa, struct top_hash_entry *act, struct to
       if (tmp)
 	DBG("Going to add cand, Mydist: %u, Req: %u\n",
 	    tmp->dist, act->dist + rtl->metric);
-      add_cand(&oa->cand, tmp, act, act->dist + rtl->metric, oa, rtl);
+      add_cand(&oa->cand, tmp, act, act->dist + rtl->metric, oa, rtl, i);
     }
 }

@@ -494,7 +494,7 @@ ospf_rt_spfa(struct ospf_area *oa)
 	  DBG("Found :-)\n");
 	else
 	  DBG("Not found!\n");
-	add_cand(&oa->cand, tmp, act, act->dist, oa, NULL);
+	add_cand(&oa->cand, tmp, act, act->dist, oa, NULL, i);
       }
       break;
     }
@@ -1325,32 +1325,6 @@ ospf_rt_spf(struct proto_ospf *po)
   po->calcrt = 0;
 }

-
-static inline int
-match_dr(struct ospf_iface *ifa, struct top_hash_entry *en)
-{
-#ifdef OSPFv2
-  return (ifa->drid == en->lsa.rt) && (ipa_to_u32(ifa->drip) == en->lsa.id);
-#else /* OSPFv3 */
-  return (ifa->drid == en->lsa.rt) && (ifa->dr_iface_id == en->lsa.id);
-#endif
-}
-
-
-static inline int
-match_rtlink(struct ospf_iface *ifa, struct ospf_lsa_rt_link *rtl)
-{
-#ifdef OSPFv2
-  return ((ifa->type == OSPF_IT_PTP) || (ifa->type == OSPF_IT_PTMP)) &&
-    (ifa->cost == rtl->metric) &&
-    (((ifa->addr->flags & IA_UNNUMBERED) ? ifa->iface->index :
-      ipa_to_u32(ifa->addr->ip)) == rtl->data);
-#else /* OSPFv3 */
-  return ((ifa->type == OSPF_IT_PTP) || (ifa->type == OSPF_IT_PTMP)) &&
-    (ifa->cost == rtl->metric) && (ifa->iface->index == rtl->lif);
-#endif
-}
-
 static inline int
 inherit_nexthops(struct mpnh *pn)
 {
@@ -1360,7 +1334,7 @@ inherit_nexthops(struct mpnh *pn)

 static struct mpnh *
 calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
-	      struct top_hash_entry *par, struct ospf_lsa_rt_link *rtl)
+	      struct top_hash_entry *par, struct ospf_lsa_rt_link *rtl, u32 pos)
 {
   // struct proto *p = &oa->po->proto;
   struct proto_ospf *po = oa->po;
@@ -1386,11 +1360,11 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
   /* The first case - local network */
   if ((en->lsa.type == LSA_T_NET) && (par == oa->rt))
   {
-    WALK_LIST(ifa, po->iface_list)
-      if (match_dr(ifa, en))
-	return new_nexthop(po, IPA_NONE, ifa->iface, ifa->ecmp_weight);
+    ifa = ospf_pos_to_ifa(oa, pos);
+    if (!ifa)
+	 return NULL;

-    return NULL;
+    return new_nexthop(po, IPA_NONE, ifa->iface, ifa->ecmp_weight);
   }

   /* The second case - ptp or ptmp neighbor */
@@ -1398,15 +1372,14 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
   {
     if (rtl->type == LSART_VLNK)
       return new_nexthop(po, IPA_NONE, NULL, 0);
-
-    WALK_LIST(ifa, po->iface_list)
-      if (match_rtlink(ifa, rtl))
-      {
-	struct ospf_neighbor *m = find_neigh(ifa, rid);
-	if (m && (m->state == NEIGHBOR_FULL))
-	  return new_nexthop(po, m->ip, ifa->iface, ifa->ecmp_weight);
-      }
-
+    ifa = ospf_pos_to_ifa(oa, pos);
+    if (!ifa)
+	 return NULL;
+    {
+	 struct ospf_neighbor *m = find_neigh(ifa, rid);
+	 if (m && (m->state == NEIGHBOR_FULL))
+	      return new_nexthop(po, m->ip, ifa->iface, ifa->ecmp_weight);
+    }
     return NULL;
   }

@@ -1532,7 +1505,7 @@ merge_nexthops(struct proto_ospf *po, struct top_hash_entry *en,
 /* Add LSA into list of candidates in Dijkstra's algorithm */
 static void
 add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
-	 u32 dist, struct ospf_area *oa, struct ospf_lsa_rt_link *rtl)
+	 u32 dist, struct ospf_area *oa, struct ospf_lsa_rt_link *rtl, u32 pos)
 {
   struct proto_ospf *po = oa->po;
   node *prev, *n;
@@ -1566,7 +1539,7 @@ add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par,
   if (!link_back(oa, en, par))
     return;

-  struct mpnh *nhs = calc_next_hop(oa, en, par, rtl);
+  struct mpnh *nhs = calc_next_hop(oa, en, par, rtl, pos);
   if (!nhs)
   {
     log(L_WARN "Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)",
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index dc6cd1d..08badef 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -228,8 +228,9 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length)

   WALK_LIST(ifa, po->iface_list)
   {
-    int net_lsa = 0;
+    int net_lsa = 0, beg_pos;

+    beg_pos = i;
     if ((ifa->type == OSPF_IT_VLINK) && (ifa->voa == oa) &&
 	(!EMPTY_LIST(ifa->neigh_list)))
     {
@@ -293,7 +294,7 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
         log("Unknown interface type %s", ifa->iface->name);
         break;
       }
-
+    ospf_lsa_pos_set(beg_pos, i, ifa);
     /* Now we will originate stub area if there is no primary */
     if (net_lsa ||
 	(ifa->type == OSPF_IT_VLINK) ||
--
1.7.2.5




More information about the Bird-users mailing list