[PATCH] ospf: improve nexthop_calc, v2
Joakim Tjernlund
Joakim.Tjernlund at transmode.se
Fri Dec 17 10:03:32 CET 2010
This could be made more efficient if one added an
OSPF_IT_PTMP interface type. Then you don't have to look
for a neighbour in calc_next_hop()
Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund at transmode.se>
---
proto/ospf/iface.c | 4 +++-
proto/ospf/ospf.h | 18 ++++++++++++++++++
proto/ospf/rt.c | 38 ++++++++++++++++++--------------------
proto/ospf/topology.c | 2 +-
4 files changed, 40 insertions(+), 22 deletions(-)
diff --git a/proto/ospf/iface.c b/proto/ospf/iface.c
index 8b21f94..b74418d 100644
--- a/proto/ospf/iface.c
+++ b/proto/ospf/iface.c
@@ -203,6 +203,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, ifa);
}
@@ -422,7 +424,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, 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 2ef0180..f785ee0 100644
--- a/proto/ospf/ospf.h
+++ b/proto/ospf/ospf.h
@@ -189,6 +189,7 @@ 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 rt_lsa_pos; /* position in router lsa */
ip_addr drip; /* Designated router */
ip_addr bdrip; /* Backup DR */
@@ -821,6 +822,23 @@ 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->rt_lsa_pos)
+ return ifa;
+ return NULL;
+}
+
+static inline void
+ospf_lsa_pos_set(u32 rt_pos, struct ospf_iface * ifa)
+{
+ ifa->rt_lsa_pos = rt_pos;
+}
#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 6b8886b..d2857dc 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;
}
@@ -1351,7 +1351,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;
@@ -1377,11 +1377,10 @@ 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);
-
- return NULL;
+ ifa = ospf_pos_to_ifa(oa, pos);
+ if (!ifa)
+ return NULL;
+ return new_nexthop(po, IPA_NONE, ifa->iface, ifa->ecmp_weight);
}
/* The second case - ptp or ptmp neighbor */
@@ -1389,15 +1388,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;
}
@@ -1523,7 +1521,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;
@@ -1557,7 +1555,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 e604bf8..32fcc5e 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -291,7 +291,7 @@ originate_rt_lsa_body(struct ospf_area *oa, u16 *length)
log("Unknown interface type %s", ifa->iface->name);
break;
}
-
+ ospf_lsa_pos_set(i, ifa);
/* Now we will originate stub area if there is no primary */
if (net_lsa ||
(ifa->type == OSPF_IT_VLINK) ||
--
1.7.2.2
More information about the Bird-users
mailing list