diff options
Diffstat (limited to 'proto/ospf')
| -rw-r--r-- | proto/ospf/config.Y | 1 | ||||
| -rw-r--r-- | proto/ospf/iface.c | 22 | ||||
| -rw-r--r-- | proto/ospf/rt.c | 863 | ||||
| -rw-r--r-- | proto/ospf/rt.h | 30 | ||||
| -rw-r--r-- | proto/ospf/topology.c | 26 | ||||
| -rw-r--r-- | proto/ospf/topology.h | 2 |
6 files changed, 522 insertions, 422 deletions
diff --git a/proto/ospf/config.Y b/proto/ospf/config.Y index da7c97e2..2196af7a 100644 --- a/proto/ospf/config.Y +++ b/proto/ospf/config.Y @@ -164,7 +164,6 @@ ospf_vlink_start: VIRTUAL LINK idval add_tail(&this_area->vlink_list, NODE this_ipatt); init_list(&this_ipatt->ipn_list); OSPF_PATT->vid = $3; - OSPF_PATT->cost = COST_D; OSPF_PATT->helloint = HELLOINT_D; OSPF_PATT->rxmtint = RXMTINT_D; OSPF_PATT->inftransdelay = INFTRANSDELAY_D; diff --git a/proto/ospf/iface.c b/proto/ospf/iface.c index 6931619b..f4013263 100644 --- a/proto/ospf/iface.c +++ b/proto/ospf/iface.c @@ -260,6 +260,7 @@ ospf_iface_down(struct ospf_iface *ifa) ifa->iface = NULL; ifa->addr = NULL; ifa->sk = NULL; + ifa->cost = 0; ifa->vip = IPA_NONE; return; } @@ -445,27 +446,6 @@ ospf_iface_new(struct proto_ospf *po, struct iface *iface, struct ifa *addr, #ifdef OSPFv3 ifa->instance_id = ip->instance_id; - - /* - addr = NULL; - if (ifa->type != OSPF_IT_VLINK) - { - struct ifa *a; - WALK_LIST(a, iface->addrs) - if (a->scope == SCOPE_LINK) - { - addr = a; - break; - } - - if (!addr) - { - log(L_ERR "%s: Missing link-local address on interface %s, declaring as stub", p->name, iface->name); - ifa->ioprob = OSPF_I_LL; - ifa->stub = 1; - } - } - */ #endif if (ip->type == OSPF_IT_UNDEF) diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c index 6a30c687..d685961d 100644 --- a/proto/ospf/rt.c +++ b/proto/ospf/rt.c @@ -14,7 +14,6 @@ static void add_cand(list * l, struct top_hash_entry *en, static int calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par); -static void ospf_ext_spf(struct proto_ospf *po); 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) @@ -31,14 +30,13 @@ fill_ri(orta * orta) { orta->type = RTS_DUMMY; orta->options = 0; - orta->oa = NULL; orta->metric1 = LSINFINITY; orta->metric2 = LSINFINITY; - orta->nh = IPA_NONE; - orta->ifa = NULL; - orta->ar = NULL; orta->tag = 0; orta->rid = 0; + orta->oa = NULL; + orta->ifa = NULL; + orta->nh = IPA_NONE; } void @@ -47,105 +45,161 @@ ospf_rt_initort(struct fib_node *fn) ort *ri = (ort *) fn; fill_ri(&ri->n); memcpy(&ri->o, &ri->n, sizeof(orta)); - ri->efn = NULL; } -/* If new is better return 1 */ +/* Whether the ASBR or the forward address destination is preferred in AS external route selection + according to 16.4.1. */ +static inline int +epath_preferred(orta *ep) +{ + return (ep->type == RTS_OSPF) && (ep->oa->areaid != 0); +} -/* - * This is hard to understand: - * If rfc1583 is set to 1, it work likes normal route_better() - * But if it is set to 0, it prunes number of AS boundary - * routes before it starts the router decision - */ +/* If new is better return 1 */ static int -ri_better(struct proto_ospf *po, orta * new, ort *nefn, orta * old, ort *oefn, int rfc1583) +ri_better(struct proto_ospf *po, orta *new, orta *old) { - int newtype = new->type; - int oldtype = old->type; - if (old->type == RTS_DUMMY) return 1; if (old->metric1 == LSINFINITY) return 1; - if (!rfc1583) + if (new->type < old->type) + return 1; + + if (new->type > old->type) + return 0; + + if (new->metric1 < old->metric1) + return 1; + + if (new->metric1 > old->metric1) + return 0; + + return 0; +} + + +/* 16.4. (3), return 1 if new is better */ +static int +ri_better_asbr(struct proto_ospf *po, orta *new, orta *old) +{ + /* We know that the old ASBB is valid */ + + if (!po->rfc1583) { - if ((new->type < RTS_OSPF_EXT1) && (new->oa->areaid == 0)) newtype = RTS_OSPF_IA; - if ((old->type < RTS_OSPF_EXT1) && (old->oa->areaid == 0)) oldtype = RTS_OSPF_IA; + int new_pref = epath_preferred(new); + int old_pref = epath_preferred(old); + + if (new_pref > old_pref) + return 1; + + if (new_pref < old_pref) + return 0; } - if (newtype < oldtype) + if (new->metric1 < old->metric1) return 1; - if (newtype > oldtype) + if (new->metric1 > old->metric1) return 0; - /* Same type */ + /* Larger area ID is preferred */ + if (new->oa->areaid > old->oa->areaid) + return 1; + + return 0; +} + +/* 16.4. (6), return 1 if new is better */ +static int +ri_better_ext(struct proto_ospf *po, orta *new, orta *old) +{ + if (old->type == RTS_DUMMY) + return 1; + + if (old->metric1 == LSINFINITY) + return 1; + + /* 16.4. (6a) */ + if (new->type < old->type) + return 1; + + if (new->type > old->type) + return 0; + + /* 16.4. (6b), same type */ if (new->type == RTS_OSPF_EXT2) { - if (new->metric2 < old->metric2) return 1; - if (new->metric2 > old->metric2) return 0; + if (new->metric2 < old->metric2) + return 1; + + if (new->metric2 > old->metric2) + return 0; } - if (((new->type == RTS_OSPF_EXT2) || (new->type == RTS_OSPF_EXT1)) && (!po->rfc1583)) + /* 16.4. (6c) */ + if (!po->rfc1583) { - newtype = nefn->n.type; - oldtype = oefn->n.type; + u32 new_pref = new->options & ORTA_PREF; + u32 old_pref = old->options & ORTA_PREF; - if (nefn->n.oa->areaid == 0) newtype = RTS_OSPF_IA; - if (oefn->n.oa->areaid == 0) oldtype = RTS_OSPF_IA; + if (new_pref > old_pref) + return 1; - if (newtype < oldtype) return 1; - if (newtype > oldtype) return 0; + if (new_pref < old_pref) + return 0; } + /* 16.4. (6d) */ if (new->metric1 < old->metric1) return 1; if (new->metric1 > old->metric1) return 0; - if (new->oa->areaid > old->oa->areaid) return 1; /* Larger AREAID is preffered */ + return 0; +} - return 0; /* Old is shorter or same */ +static inline void +ri_install_net(struct proto_ospf *po, ip_addr prefix, int pxlen, orta *new) +{ + ort *old = (ort *) fib_get(&po->rtf, &prefix, pxlen); + if (ri_better(po, new, &old->n)) + memcpy(&old->n, new, sizeof(orta)); } -static void -ri_install(struct proto_ospf *po, ip_addr prefix, int pxlen, int dest, - orta * new, ort * ipath) +static inline void +ri_install_rt(struct ospf_area *oa, u32 rid, orta *new) { - struct ospf_area *oa = new->oa; - ort *old; + ip_addr addr = ipa_from_rid(rid); + ort *old = (ort *) fib_get(&oa->rtr, &addr, MAX_PREFIX_LENGTH); + if (ri_better(oa->po, new, &old->n)) + memcpy(&old->n, new, sizeof(orta)); +} - if (dest == ORT_NET) - { - struct area_net *anet; - old = (ort *) fib_get(&po->rtf, &prefix, pxlen); - if (ri_better(po, new, ipath, &old->n, old->efn, 1)) - { - memcpy(&old->n, new, sizeof(orta)); - old->efn = ipath; - if ((new->type == RTS_OSPF) && (anet = (struct area_net *)fib_route(&oa->net_fib, prefix, pxlen))) - { - anet->active = 1; - if (new->metric1 > anet->metric) anet->metric = new->metric1; - } - } - } - else - { - old = (ort *) fib_get(&oa->rtr, &prefix, pxlen); +static inline void +ri_install_ext(struct proto_ospf *po, ip_addr prefix, int pxlen, orta *new) +{ + ort *old = (ort *) fib_get(&po->rtf, &prefix, pxlen); + if (ri_better_ext(po, new, &old->n)) + memcpy(&old->n, new, sizeof(orta)); +} - if (ri_better(po, new, ipath, &old->n, old->efn, 1)) - { - memcpy(&old->n, new, sizeof(orta)); - old->efn = ipath; - } - } +static inline void +update_anet(struct ospf_area *oa, ip_addr prefix, int pxlen, u32 metric) +{ + struct area_net *anet = (struct area_net *) fib_route(&oa->net_fib, prefix, pxlen); + if (!anet) + return; + + anet->active = 1; + if (metric > anet->metric) + anet->metric = metric; } + #ifdef OSPFv2 static struct ospf_iface * @@ -188,17 +242,17 @@ find_stub_src(struct ospf_area *oa, ip_addr px, int pxlen) static void add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en) { - orta nf; - nf.type = RTS_OSPF; - nf.options = 0; - nf.metric1 = metric; - nf.metric2 = LSINFINITY; - nf.tag = 0; - nf.oa = oa; - nf.ar = en; - nf.nh = en->nh; - nf.ifa = en->nhi; - nf.rid = en->lsa.rt; + orta nf = { + .type = RTS_OSPF, + .options = 0, + .metric1 = metric, + .metric2 = LSINFINITY, + .tag = 0, + .rid = en->lsa.rt, + .oa = oa, + .ifa = en->nhi, + .nh = en->nh + }; if (en == oa->rt) { @@ -210,12 +264,14 @@ add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_ */ nf.ifa = find_stub_src(oa, px, pxlen); + nf.nh = IPA_NONE; if (!nf.ifa) return; } - ri_install(oa->po, px, pxlen, ORT_NET, &nf, NULL); + ri_install_net(oa->po, px, pxlen, &nf); + update_anet(oa, px, pxlen, metric); } #ifdef OSPFv3 @@ -255,6 +311,10 @@ process_prefixes(struct ospf_area *oa) if (!src) continue; + /* Reachable in SPF */ + if (src->color != INSPF) + continue; + if (src->lsa.age == LSA_MAXAGE) continue; @@ -269,6 +329,10 @@ process_prefixes(struct ospf_area *oa) if (pxopts & OPT_PX_NU) continue; + /* Store the first global address to use it later as a vlink endpoint */ + if ((pxopts & OPT_PX_LA) && ipa_zero(src->lb)) + src->lb = pxa; + add_network(oa, pxa, pxlen, src->dist + metric, src); } } @@ -329,7 +393,7 @@ ospf_rt_spfa_rtlinks(struct ospf_area *oa, struct top_hash_entry *act, struct to } } -/* 16.1 calculating shortest paths for an area */ +/* RFC 2328 16.1. calculating shortest paths for an area */ static void ospf_rt_spfa(struct ospf_area *oa) { @@ -337,10 +401,8 @@ ospf_rt_spfa(struct ospf_area *oa) struct proto_ospf *po = oa->po; struct ospf_lsa_rt *rt; struct ospf_lsa_net *ln; - struct ospf_iface *iface; struct top_hash_entry *act, *tmp; u32 i, *rts; - orta nf; node *n; if (oa->rt == NULL) @@ -380,20 +442,27 @@ ospf_rt_spfa(struct ospf_area *oa) if (rt->options & OPT_RT_V) oa->trcap = 1; - /* In OSPFv2, just ASBRs and ABRs are needed to add to oa->rtr table */ - // ((rt->options & OPT_RT_V) || (rt->options & OPT_RT_E)) - - nf.type = RTS_OSPF; - nf.options = rt->options; - nf.metric1 = act->dist; - nf.metric2 = LSINFINITY; - nf.tag = 0; - nf.oa = oa; - nf.ar = act; - nf.nh = act->nh; - nf.ifa = act->nhi; - nf.rid = act->lsa.rt; - ri_install(po, ipa_from_rid(act->lsa.rt), MAX_PREFIX_LENGTH, ORT_ROUTER, &nf, NULL); + /* + * In OSPFv3, all routers are added to per-area routing + * tables. But we use it just for ASBRs and ABRs. For the + * purpose of the last step in SPF - prefix-LSA processing in + * process_prefixes(), we use information stored in LSA db. + */ + if ((rt->options & OPT_RT_E) || (rt->options & OPT_RT_B)) + { + orta nf = { + .type = RTS_OSPF, + .options = rt->options, + .metric1 = act->dist, + .metric2 = LSINFINITY, + .tag = 0, + .rid = act->lsa.rt, + .oa = oa, + .ifa = act->nhi, + .nh = act->nh + }; + ri_install_rt(oa, act->lsa.rt, &nf); + } #ifdef OSPFv2 ospf_rt_spfa_rtlinks(oa, act, act); @@ -430,37 +499,6 @@ ospf_rt_spfa(struct ospf_area *oa) #ifdef OSPFv3 process_prefixes(oa); #endif - - /* Find new/lost VLINK peers */ - WALK_LIST(iface, po->iface_list) - { - if ((iface->type == OSPF_IT_VLINK) && (iface->voa == oa)) - { - if ((tmp = ospf_hash_find_rt(po->gr, oa->areaid, iface->vid)) && - (!ipa_equal(tmp->lb, IPA_NONE))) - { - if ((iface->state != OSPF_IS_PTP) || (iface->vifa != tmp->nhi) || (!ipa_equal(iface->vip, tmp->lb))) - { - OSPF_TRACE(D_EVENTS, "Vlink peer %R found", tmp->lsa.id); - ospf_iface_sm(iface, ISM_DOWN); - iface->vifa = tmp->nhi; - iface->iface = tmp->nhi->iface; - iface->addr = tmp->nhi->addr; - iface->sk = tmp->nhi->sk; - iface->vip = tmp->lb; - ospf_iface_sm(iface, ISM_UP); - } - } - else - { - if (iface->state > OSPF_IS_DOWN) - { - OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", iface->vid); - ospf_iface_sm(iface, ISM_DOWN); - } - } - } - } } static int @@ -475,7 +513,9 @@ link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry if (!en || !par) return 0; - // FIXME lb should be properly set for vlinks */ + /* In OSPFv2, en->lb is set here. In OSPFv3, en->lb is just cleared here, + it is set in process_prefixes() to any global addres in the area */ + en->lb = IPA_NONE; #ifdef OSPFv3 en->lb_id = 0; @@ -539,21 +579,22 @@ link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry return 0; } -/* 16.3 examining summary-LSAs in transit areas */ + +/* RFC 2328 16.2. calculating inter-area routes */ static void -ospf_rt_sum_tr(struct ospf_area *oa) +ospf_rt_sum(struct ospf_area *oa) { - // struct proto *p = &oa->po->proto; struct proto_ospf *po = oa->po; - struct ospf_area *bb = po->backbone; - ip_addr ip, abrip; + struct proto *p = &po->proto; struct top_hash_entry *en; - u32 dst_rid, metric, options; + ip_addr ip = IPA_NONE; + u32 dst_rid = 0; + u32 metric, options; + struct area_net *anet; + ort *abr; int pxlen = -1, type = -1; - ort *re = NULL, *abr; - orta nf; - if (!bb) return; + OSPF_TRACE(D_EVENTS, "Starting routing table calculation for inter-area (area %R)", oa->areaid); WALK_SLIST(en, po->lsal) { @@ -563,19 +604,20 @@ ospf_rt_sum_tr(struct ospf_area *oa) if (en->domain != oa->areaid) continue; - /* 16.3 (1a) */ + /* 16.2. (1a) */ if (en->lsa.age == LSA_MAXAGE) continue; - // if (en->dist == LSINFINITY) - // continue; - - /* 16.3 (2) */ + /* 16.2. (2) */ if (en->lsa.rt == po->router_id) continue; + if (en->lsa.type == LSA_T_SUM_NET) { + struct ospf_area *oaa; + int skip = 0; + #ifdef OSPFv2 struct ospf_lsa_sum *ls = en->lsa_body; pxlen = ipa_mklen(ls->netmask); @@ -593,9 +635,20 @@ ospf_rt_sum_tr(struct ospf_area *oa) metric = ls->metric & METRIC_MASK; options = 0; type = ORT_NET; - re = fib_find(&po->rtf, &ip, pxlen); + + /* 16.2. (3) */ + WALK_LIST(oaa, po->area_list) + { + if ((anet = fib_find(&oaa->net_fib, &ip, pxlen)) && anet->active) + { + skip = 1; + break; + } + } + if (skip) + continue; } - else // en->lsa.type == LSA_T_SUM_RT + else /* LSA_T_SUM_RT */ { #ifdef OSPFv2 struct ospf_lsa_sum *ls = en->lsa_body; @@ -607,57 +660,62 @@ ospf_rt_sum_tr(struct ospf_area *oa) options = ls->options & OPTIONS_MASK; #endif - ip = ipa_from_rid(dst_rid); - pxlen = MAX_PREFIX_LENGTH; metric = ls->metric & METRIC_MASK; options |= ORTA_ASBR; type = ORT_ROUTER; - re = fib_find(&bb->rtr, &ip, pxlen); } - /* 16.3 (1b) */ - if (metric == LSINFINITY) - continue; + /* 16.2. (1b) */ + if (metric == LSINFINITY) + continue; - /* 16.3 (3) */ - if (!re || !re->n.type) continue; - if (re->n.oa->areaid != 0) continue; - if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA)) continue; + /* 16.2. (4) */ + ip_addr abrip = ipa_from_rid(en->lsa.rt); + abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH); + if (!abr || !abr->n.type) + continue; - /* 16.3. (4) */ - abrip = ipa_from_rid(en->lsa.rt); - abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH); - if (!abr || !abr->n.type) continue; - - nf.type = re->n.type; - nf.options = options; - nf.metric1 = abr->n.metric1 + metric; - nf.metric2 = LSINFINITY; - nf.tag = 0; - nf.oa = oa; - nf.ar = abr->n.ar; - nf.nh = abr->n.nh; - nf.ifa = abr->n.ifa; - nf.rid = en->lsa.rt; /* ABR ID */ - ri_install(po, ip, pxlen, type, &nf, NULL); + if (abr->n.metric1 == LSINFINITY) + continue; + + if (!(abr->n.options & ORTA_ABR)) + continue; + + /* 16.2. (5) */ + orta nf = { + .type = RTS_OSPF_IA, + .options = options, + .metric1 = abr->n.metric1 + metric, + .metric2 = LSINFINITY, + .tag = 0, + .rid = en->lsa.rt, /* ABR ID */ + .oa = oa, + .ifa = abr->n.ifa, + .nh = abr->n.nh + }; + + if (type == ORT_NET) + ri_install_net(po, ip, pxlen, &nf); + else + ri_install_rt(oa, dst_rid, &nf); } } - -/* 16.2 calculating inter-area routes */ + +/* RFC 2328 16.3. examining summary-LSAs in transit areas */ static void -ospf_rt_sum(struct ospf_area *oa) +ospf_rt_sum_tr(struct ospf_area *oa) { + // struct proto *p = &oa->po->proto; struct proto_ospf *po = oa->po; - struct proto *p = &po->proto; + struct ospf_area *bb = po->backbone; + ip_addr ip, abrip; struct top_hash_entry *en; - ip_addr ip, abrip; /* abrIP is actually ID */ u32 dst_rid, metric, options; - struct area_net *anet; - orta nf; - ort *abr; int pxlen = -1, type = -1; + ort *re = NULL, *abr; - OSPF_TRACE(D_EVENTS, "Starting routing table calculation for inter-area (area %R)", oa->areaid); + + if (!bb) return; WALK_SLIST(en, po->lsal) { @@ -667,20 +725,16 @@ ospf_rt_sum(struct ospf_area *oa) if (en->domain != oa->areaid) continue; - /* Page 169 (1) */ + /* 16.3 (1a) */ if (en->lsa.age == LSA_MAXAGE) continue; - /* Page 169 (2) */ + /* 16.3 (2) */ if (en->lsa.rt == po->router_id) continue; - if (en->lsa.type == LSA_T_SUM_NET) { - struct ospf_area *oaa; - int skip = 0; - #ifdef OSPFv2 struct ospf_lsa_sum *ls = en->lsa_body; pxlen = ipa_mklen(ls->netmask); @@ -698,19 +752,9 @@ ospf_rt_sum(struct ospf_area *oa) metric = ls->metric & METRIC_MASK; options = 0; type = ORT_NET; - - /* Page 169 (3) */ - WALK_LIST(oaa, po->area_list) - { - if ((anet = fib_find(&oaa->net_fib, &ip, pxlen)) && anet->active) - { - skip = 1; - break; - } - } - if (skip) continue; + re = fib_find(&po->rtf, &ip, pxlen); } - else + else // en->lsa.type == LSA_T_SUM_RT { #ifdef OSPFv2 struct ospf_lsa_sum *ls = en->lsa_body; @@ -727,114 +771,54 @@ ospf_rt_sum(struct ospf_area *oa) metric = ls->metric & METRIC_MASK; options |= ORTA_ASBR; type = ORT_ROUTER; + re = fib_find(&bb->rtr, &ip, pxlen); } - /* Page 169 (1) */ - if (metric == LSINFINITY) - continue; - - /* Page 169 (4) */ - abrip = ipa_from_rid(en->lsa.rt); - - abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH); - if (!abr || !abr->n.type) continue; - if (abr->n.metric1 == LSINFINITY) continue; - if (!(abr->n.options & ORTA_ABR)) continue; - - nf.type = RTS_OSPF_IA; - nf.options = options; - nf.metric1 = abr->n.metric1 + metric; - nf.metric2 = LSINFINITY; - nf.tag = 0; - nf.oa = oa; - nf.ar = abr->n.ar; - nf.nh = abr->n.nh; - nf.ifa = abr->n.ifa; - nf.rid = en->lsa.rt; /* ABR ID */ - ri_install(po, ip, pxlen, type, &nf, NULL); - } -} - -/** - * ospf_rt_spf - calculate internal routes - * @po: OSPF protocol - * - * Calculation of internal paths in an area is described in 16.1 of RFC 2328. - * It's based on Dijkstra's shortest path tree algorithms. - * This function is invoked from ospf_disp(). - */ -void -ospf_rt_spf(struct proto_ospf *po) -{ - struct proto *p = &po->proto; - struct ospf_area *oa; - ort *ri; - struct area_net *anet; - - if (po->areano == 0) return; + /* 16.3 (1b) */ + if (metric == LSINFINITY) + continue; - po->cleanup = 1; + /* 16.3 (3) */ + if (!re || !re->n.type) + continue; - OSPF_TRACE(D_EVENTS, "Starting routing table calculation"); + if (re->n.oa->areaid != 0) + continue; - /* 16. (1) - Invalidate old routing table */ - FIB_WALK(&po->rtf, nftmp) - { - ri = (ort *) nftmp; - memcpy(&ri->o, &ri->n, sizeof(orta)); /* Backup old data */ - fill_ri(&ri->n); - } - FIB_WALK_END; + if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA)) + continue; + /* 16.3. (4) */ + abrip = ipa_from_rid(en->lsa.rt); + abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH); + if (!abr || !abr->n.type) + continue; - WALK_LIST(oa, po->area_list) - { - FIB_WALK(&oa->rtr, nftmp) - { - ri = (ort *) nftmp; - memcpy(&ri->o, &ri->n, sizeof(orta)); /* Backup old data */ - fill_ri(&ri->n); - } - FIB_WALK_END; + metric = abr->n.metric1 + metric; /* IAC */ - FIB_WALK(&oa->net_fib, nftmp) + /* 16.3. (5) */ + if (metric <= re->n.metric1) { - anet = (struct area_net *) nftmp; - anet->active = 0; - anet->metric = 1; + /* We want to replace the next-hop even if the metric is equal + to replace a virtual next-hop through vlink with a real one */ + re->n.metric1 = metric; + re->n.nh = abr->n.nh; + re->n.ifa = abr->n.ifa; } - FIB_WALK_END; - - /* 16. (2) */ - ospf_rt_spfa(oa); - } - - /* 16. (3) */ - if ((po->areano == 1) || (!po->backbone)) - { - ospf_rt_sum(HEAD(po->area_list)); - } - else - { - ospf_rt_sum(po->backbone); } +} - /* 16. (4) */ - WALK_LIST(oa, po->area_list) +/* RFC 2328 G.3 - incomplete resolution of virtual next hops */ +static void +ospf_cleanup_vlinks(struct proto_ospf *po) +{ + FIB_WALK(&po->rtf, nftmp) { - if (oa->trcap && (oa->areaid != 0)) - { - ospf_rt_sum_tr(oa); - break; - } + ort *nf = (ort *) nftmp; + if (nf->n.type && (nf->n.ifa->type == OSPF_IT_VLINK)) + fill_ri(&nf->n); } - - /* 16. (5) */ - ospf_ext_spf(po); - - rt_sync(po); - - po->calcrt = 0; + FIB_WALK_END; } /** @@ -848,7 +832,7 @@ ospf_rt_spf(struct proto_ospf *po) static void ospf_ext_spf(struct proto_ospf *po) { - ort *nf1, *nf2, *nfh; + ort *nf1, *nf2; orta nfa; struct top_hash_entry *en; struct proto *p = &po->proto; @@ -857,7 +841,6 @@ ospf_ext_spf(struct proto_ospf *po) ip_addr ip, nh, rtid, rt_fwaddr; struct ospf_iface *nhi = NULL; u32 br_metric, rt_metric, rt_tag; - neighbor *nn; struct ospf_area *atmp; OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes"); @@ -867,6 +850,7 @@ ospf_ext_spf(struct proto_ospf *po) /* 16.4. (1) */ if (en->lsa.type != LSA_T_EXT) continue; + if (en->lsa.age == LSA_MAXAGE) continue; @@ -926,52 +910,47 @@ ospf_ext_spf(struct proto_ospf *po) nf1 = NULL; WALK_LIST(atmp, po->area_list) { - nfh = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH); - if (!nfh || !nfh->n.type) continue; - if (nf1 == NULL) nf1 = nfh; - else if (ri_better(po, &nfh->n, NULL, &nf1->n, NULL, po->rfc1583)) nf1 = nfh; + ort *nfh = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH); + if (!nfh || !nfh->n.type) + continue; + + if (nfh->n.metric1 == LSINFINITY) + continue; + + if (!nf1 || ri_better_asbr(po, &nfh->n, &nf1->n)) + nf1 = nfh; } if (!nf1) continue; /* No AS boundary router found */ - if (nf1->n.metric1 == LSINFINITY) - continue; /* distance is INF */ - if (!(nf1->n.options & ORTA_ASBR)) continue; /* It is not ASBR */ if (!rt_fwaddr_valid) { + nf2 = nf1; nh = nf1->n.nh; nhi = nf1->n.ifa; - nfh = nf1; br_metric = nf1->n.metric1; } else { + /* FIXME: what about more specific dummy route? */ nf2 = fib_route(&po->rtf, rt_fwaddr, MAX_PREFIX_LENGTH); - - if (!nf2) - { - DBG("Cannot find network route (GW=%I)\n", rt_fwaddr); + if (!nf2) /* nf2->n.type is checked later */ continue; - } - if ((nn = neigh_find(p, &rt_fwaddr, 0)) != NULL) - { - nh = rt_fwaddr; - nhi = ospf_iface_find(po, nn->iface); - } - else - { - nh = nf2->n.nh; - nhi = nf2->n.ifa; - } + if (nf2->n.metric1 == LSINFINITY) + continue; + + if ((nf2->n.type != RTS_OSPF) && (nf2->n.type != RTS_OSPF_IA)) + continue; + /* If nh is zero, it is a device route */ + nh = ipa_nonzero(nf2->n.nh) ? nf2->n.nh : rt_fwaddr; + nhi = nf2->n.ifa; br_metric = nf2->n.metric1; - if (br_metric == LSINFINITY) - continue; /* distance is INF */ } if (ebit) @@ -987,16 +966,144 @@ ospf_ext_spf(struct proto_ospf *po) nfa.metric2 = LSINFINITY; } - nfa.options = 0; + /* Whether the route is preferred in route selection according to 16.4.1 */ + nfa.options = epath_preferred(&nf2->n) ? ORTA_PREF : 0; + nfa.tag = rt_tag; - nfa.oa = (po->backbone == NULL) ? HEAD(po->area_list) : po->backbone; - nfa.ar = nf1->n.ar; - nfa.nh = nh; - nfa.ifa = nhi; nfa.rid = en->lsa.rt; - ri_install(po, ip, pxlen, ORT_NET, &nfa, nfh); + nfa.oa = nf1->n.oa; /* undefined in RFC 2328 */ + nfa.ifa = nhi; + nfa.nh = nh; + + ri_install_ext(po, ip, pxlen, &nfa); + } +} + +/* RFC 2328 16.7. p2 - find new/lost vlink endpoints */ +static void +ospf_check_vlinks(struct proto_ospf *po) +{ + struct proto *p = &po->proto; + + struct ospf_iface *iface; + WALK_LIST(iface, po->iface_list) + { + if (iface->type == OSPF_IT_VLINK) + { + struct top_hash_entry *tmp; + tmp = ospf_hash_find_rt(po->gr, iface->voa->areaid, iface->vid); + + if (tmp && (tmp->color == INSPF) + && (tmp->dist < LSINFINITY) + && ipa_nonzero(tmp->lb)) + { + if ((iface->state != OSPF_IS_PTP) + || (iface->vifa != tmp->nhi) + || !ipa_equal(iface->vip, tmp->lb)) + { + OSPF_TRACE(D_EVENTS, "Vlink peer %R found", tmp->lsa.id); + ospf_iface_sm(iface, ISM_DOWN); + iface->vifa = tmp->nhi; + iface->iface = tmp->nhi->iface; + iface->addr = tmp->nhi->addr; + iface->sk = tmp->nhi->sk; + iface->cost = tmp->dist; + iface->vip = tmp->lb; + ospf_iface_sm(iface, ISM_UP); + } + else if ((iface->state == OSPF_IS_PTP) && (iface->cost != tmp->dist)) + { + iface->cost = tmp->dist; + schedule_rt_lsa(po->backbone); + } + } + else + { + if (iface->state > OSPF_IS_DOWN) + { + OSPF_TRACE(D_EVENTS, "Vlink peer %R lost", iface->vid); + ospf_iface_sm(iface, ISM_DOWN); + } + } + } + } +} +/** + * ospf_rt_spf - calculate internal routes + * @po: OSPF protocol + * + * Calculation of internal paths in an area is described in 16.1 of RFC 2328. + * It's based on Dijkstra's shortest path tree algorithms. + * This function is invoked from ospf_disp(). + */ +void +ospf_rt_spf(struct proto_ospf *po) +{ + struct proto *p = &po->proto; + struct ospf_area *oa; + ort *ri; + struct area_net *anet; + + if (po->areano == 0) return; + + po->cleanup = 1; + + OSPF_TRACE(D_EVENTS, "Starting routing table calculation"); + + /* 16. (1) - Invalidate old routing table */ + FIB_WALK(&po->rtf, nftmp) + { + ri = (ort *) nftmp; + memcpy(&ri->o, &ri->n, sizeof(orta)); /* Backup old data */ + fill_ri(&ri->n); } + FIB_WALK_END; + + + WALK_LIST(oa, po->area_list) + { + FIB_WALK(&oa->rtr, nftmp) + { + ri = (ort *) nftmp; + memcpy(&ri->o, &ri->n, sizeof(orta)); /* Backup old data */ + fill_ri(&ri->n); + } + FIB_WALK_END; + + FIB_WALK(&oa->net_fib, nftmp) + { + anet = (struct area_net *) nftmp; + anet->active = 0; + anet->metric = 1; + } + FIB_WALK_END; + + /* 16. (2) */ + ospf_rt_spfa(oa); + } + + /* 16. (3) */ + if ((po->areano == 1) || (!po->backbone)) + ospf_rt_sum(HEAD(po->area_list)); + else + ospf_rt_sum(po->backbone); + + /* 16. (4) */ + WALK_LIST(oa, po->area_list) + if (oa->trcap && (oa->areaid != 0)) + ospf_rt_sum_tr(oa); + + /* G.3 */ + if (po->backbone && po->backbone->rt && + (((struct ospf_lsa_rt *) po->backbone->rt->lsa_body)->options & OPT_RT_V)) + ospf_cleanup_vlinks(po); + + /* 16. (5) */ + ospf_ext_spf(po); + + rt_sync(po); + po->calcrt = 0; } /* Add LSA into list of candidates in Dijkstra's algorithm */ @@ -1031,7 +1138,7 @@ add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par, if (dist >= en->dist) return; /* - * FIXME The line above (=) is not a bug, but we don't support multiple + * The line above (=) is not a bug, but we don't support multiple * next hops. I'll start as soon as nest will */ @@ -1146,7 +1253,7 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en, */ neigh = NULL; WALK_LIST(ifa, po->iface_list) - if (ifa->type == OSPF_IT_PTP) + if ((ifa->type == OSPF_IT_PTP) || (ifa->type == OSPF_IT_VLINK)) { m = find_neigh(ifa, rid); if (m && (m->state == NEIGHBOR_FULL)) @@ -1191,7 +1298,7 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *llsa; llsa = ospf_hash_find(po->gr, par->nhi->iface->index, en->lb_id, rid, LSA_T_LINK); - if (!llsa) + if (!llsa || ipa_zero(llsa->lladdr)) return 0; en->nh = llsa->lladdr; @@ -1236,76 +1343,63 @@ again1: check_sum_lsa(po, nf, ORT_NET); if (reload || memcmp(&nf->n, &nf->o, sizeof(orta))) { /* Some difference */ - net *ne; - rta a0; - rte *e; - - bzero(&a0, sizeof(a0)); - - a0.proto = p; - a0.source = nf->n.type; - a0.scope = SCOPE_UNIVERSE; - a0.cast = RTC_UNICAST; - a0.dest = RTD_ROUTER; - a0.flags = 0; - a0.aflags = 0; - a0.iface = NULL; - if (nf->n.ifa) a0.iface = nf->n.ifa->iface; - a0.gw = nf->n.nh; - - if (ipa_nonzero(nf->n.nh) && (!neigh_find2(p, &nf->n.nh, nf->n.ifa->iface, 0))) - { - int found = 0; - struct ospf_iface *ifa; - struct top_hash_entry *en; - OSPF_TRACE(D_EVENTS, "Trying to find correct next hop %I/%d via %I", nf->fn.prefix, nf->fn.pxlen, nf->n.nh); - WALK_LIST(ifa, po->iface_list) - { - if ((ifa->type == OSPF_IT_VLINK) && ipa_equal(ifa->vip, nf->n.nh)) - { - if ((en = ospf_hash_find_rt(po->gr, ifa->voa->areaid, ifa->vid)) - && (!ipa_equal(en->nh, IPA_NONE))) - { - a0.gw = en->nh; - found = 1; - } - break; - } - } - if (!found) nf->n.metric1 = LSINFINITY; /* Delete it */ - } + net *ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen); + + rta a0 = { + .proto = p, + .source = nf->n.type, + .scope = SCOPE_UNIVERSE, + .cast = RTC_UNICAST + }; - if (ipa_equal(nf->n.nh, IPA_NONE)) a0.dest = RTD_DEVICE; + if (!nf->n.type) + goto remove1; - if (!a0.iface) /* Still no match? Can this really happen? */ - nf->n.metric1 = LSINFINITY; + /* The distance is unreachable (or farther) */ + if (nf->n.metric1 >= LSINFINITY) + goto remove1; - ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen); - if (nf->n.metric1 < LSINFINITY) + a0.iface = nf->n.ifa->iface; + if (ipa_nonzero(nf->n.nh)) { - e = rte_get_temp(&a0); - e->u.ospf.metric1 = nf->n.metric1; - e->u.ospf.metric2 = nf->n.metric2; - e->u.ospf.tag = nf->n.tag; - e->u.ospf.router_id = nf->n.rid; - e->pflags = 0; - e->net = ne; - e->pref = p->preference; - DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n", - a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1); - rte_update(p->table, ne, p, p, e); + neighbor *ng; + a0.dest = RTD_ROUTER; + a0.gw = nf->n.nh; + + ng = neigh_find2(p, &a0.gw, a0.iface, 0); + if (!ng || (ng->scope == SCOPE_HOST)) + goto remove1; } else - { - rte_update(p->table, ne, p, p, NULL); - FIB_ITERATE_PUT(&fit, nftmp); - fib_delete(fib, nftmp); - goto again1; - } + a0.dest = RTD_DEVICE; + + /* Add the route */ + rte *e = rte_get_temp(&a0); + e->u.ospf.metric1 = nf->n.metric1; + e->u.ospf.metric2 = nf->n.metric2; + e->u.ospf.tag = nf->n.tag; + e->u.ospf.router_id = nf->n.rid; + e->pflags = 0; + e->net = ne; + e->pref = p->preference; + DBG("Mod rte type %d - %I/%d via %I on iface %s, met %d\n", + a0.source, nf->fn.prefix, nf->fn.pxlen, a0.gw, a0.iface ? a0.iface->name : "(none)", nf->n.metric1); + rte_update(p->table, ne, p, p, e); + goto cont1; + + remove1: + /* Remove the route */ + rte_update(p->table, ne, p, p, NULL); + FIB_ITERATE_PUT(&fit, nftmp); + fib_delete(fib, nftmp); + goto again1; } } + cont1: FIB_ITERATE_END(nftmp); + ospf_check_vlinks(po); + WALK_LIST(oa, po->area_list) { FIB_ITERATE_INIT(&fit, &oa->rtr); @@ -1338,7 +1432,8 @@ again2: { int fl = flush; - if (oaa == oa) continue; + if (oaa == oa) + continue; if ((oa == po->backbone) && oaa->trcap) fl = 1; diff --git a/proto/ospf/rt.h b/proto/ospf/rt.h index 559fa5c6..6b23bffe 100644 --- a/proto/ospf/rt.h +++ b/proto/ospf/rt.h @@ -17,22 +17,31 @@ typedef struct orta { int type; - u32 options; - /* router-LSA style options (for ORT_ROUTER), with V,E,B bits. - In OSPFv2, ASBRs from another areas (that we know from rt-summary-lsa), - have just ORTA_ASBR in options, their real options are unknown */ + u32 options; + /* + * For ORT_ROUTER routes, options field are router-LSA style + * options, with V,E,B bits. In OSPFv2, ASBRs from another areas + * (that we know from rt-summary-lsa) have just ORTA_ASBR in + * options, their real options are unknown. + */ #define ORTA_ASBR OPT_RT_E #define ORTA_ABR OPT_RT_B - struct ospf_area *oa; + /* + * For ORT_NET routes, the field is almost unused with one + * exception: ORTA_PREF for external routes means that the route is + * preferred in AS external route selection according to 16.4.1. - + * it is intra-area path using non-backbone area. In other words, + * the forwarding address (or ASBR if forwarding address is zero) is + * intra-area (type == RTS_OSPF) and its area is not a backbone. + */ +#define ORTA_PREF 0x80000000 u32 metric1; u32 metric2; - ip_addr nh; /* Next hop */ - struct ospf_iface *ifa; /* Outgoing interface */ - struct top_hash_entry *ar; /* Advertising router (or ABR) */ u32 tag; u32 rid; /* Router ID of real advertising router */ - /* For ext-LSA from different area, 'ar' is a type 1 LSA of ABR. - Router ID of real advertising router is stored in 'rid'. */ + struct ospf_area *oa; + struct ospf_iface *ifa; /* Outgoing interface */ + ip_addr nh; /* Next hop */ } orta; @@ -41,7 +50,6 @@ typedef struct ort struct fib_node fn; orta n; orta o; - struct ort *efn; /* For RFC1583 */ } ort; diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c index 885c39ba..be9e434a 100644 --- a/proto/ospf/topology.c +++ b/proto/ospf/topology.c @@ -1114,6 +1114,8 @@ originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length) struct proto_ospf *po = oa->po; struct ospf_iface *ifa; struct ospf_lsa_prefix *lp; + struct ifa *vlink_addr = NULL; + int host_addr = 0; int net_lsa; int i = 0; u8 flags; @@ -1139,10 +1141,15 @@ originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length) struct ifa *a; WALK_LIST(a, ifa->iface->addrs) { - if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) || - (a->flags & IA_SECONDARY) || + if ((a->flags & IA_SECONDARY) || (a->flags & IA_UNNUMBERED) || - (a->scope <= SCOPE_LINK) || + (a->scope <= SCOPE_LINK)) + continue; + + if (!vlink_addr) + vlink_addr = a; + + if (((a->pxlen < MAX_PREFIX_LENGTH) && net_lsa) || configured_stubnet(oa, a)) continue; @@ -1150,10 +1157,20 @@ originate_prefix_rt_lsa_body(struct ospf_area *oa, u16 *length) put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(a->pxlen)), a->ip, a->pxlen, flags, ifa->cost); i++; + + if (flags & OPT_PX_LA) + host_addr = 1; } } - /* FIXME Handle vlinks? see RFC5340, page 38 */ + /* If there are some configured vlinks, add some global address, + which will be used as a vlink endpoint. */ + if (!EMPTY_LIST(oa->ac->vlink_list) && !host_addr && vlink_addr) + { + put_ipv6_prefix(lsab_alloc(po, IPV6_PREFIX_SPACE(MAX_PREFIX_LENGTH)), + vlink_addr->ip, MAX_PREFIX_LENGTH, OPT_PX_LA, 0); + i++; + } struct ospf_stubnet_config *sn; WALK_LIST(sn, oa->ac->stubnet_list) @@ -1227,6 +1244,7 @@ prefix_advance(u32 *buf) return buf + IPV6_PREFIX_WORDS(pxl); } +/* FIXME eliminate items wit LA bit set? see 4.4.3.9 */ static void add_prefix(struct proto_ospf *po, u32 *px, int offset, int *pxc) { diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h index 16d4c78f..7aa1625b 100644 --- a/proto/ospf/topology.h +++ b/proto/ospf/topology.h @@ -21,7 +21,7 @@ struct top_hash_entry void *lsa_body; bird_clock_t inst_t; /* Time of installation into DB */ ip_addr nh; /* Next hop */ - ip_addr lb; /* Link back */ + ip_addr lb; /* In OSPFv2, link back address. In OSPFv3, any global address in the area useful for vlinks */ struct ospf_iface *nhi; /* Next hop interface */ #ifdef OSPFv3 u32 lb_id; /* Interface ID of link back iface (for bcast or NBMA networks) */ |