diff options
Diffstat (limited to 'proto/ospf/rt.c')
-rw-r--r-- | proto/ospf/rt.c | 816 |
1 files changed, 504 insertions, 312 deletions
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c index 2e1de440..29283268 100644 --- a/proto/ospf/rt.c +++ b/proto/ospf/rt.c @@ -8,20 +8,29 @@ #include "ospf.h" -static void -add_cand(list * l, struct top_hash_entry *en, - struct top_hash_entry *par, u16 dist, struct ospf_area *oa); -static void -calc_next_hop(struct top_hash_entry *en, - struct top_hash_entry *par, struct ospf_area *oa); +static void add_cand(list * l, struct top_hash_entry *en, + struct top_hash_entry *par, u32 dist, + struct ospf_area *oa); +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) + as index, so we need to encapsulate RID to IP address */ +#ifdef OSPFv2 +#define ipa_from_rid(x) _MI(x) +#else /* OSPFv3 */ +#define ipa_from_rid(x) _MI(0,0,0,x) +#endif + + static void fill_ri(orta * orta) { orta->type = RTS_DUMMY; - orta->capa = 0; + orta->options = 0; orta->oa = NULL; orta->metric1 = LSINFINITY; orta->metric2 = LSINFINITY; @@ -137,88 +146,109 @@ ri_install(struct proto_ospf *po, ip_addr prefix, int pxlen, int dest, } static void -ospf_rt_spfa(struct ospf_area *oa) +add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en) { - u32 i, *rts; - struct ospf_lsa_rt *rt; - struct ospf_lsa_rt_link *rtl, *rr; - struct proto *p = &oa->po->proto; - struct proto_ospf *po = oa->po; - struct ospf_lsa_net *ln; orta nf; - struct ospf_iface *iface; - struct top_hash_entry *act, *tmp; - node *n; + 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; + + /* FIXME check nf.ifa on stubs */ + ri_install(oa->po, px, pxlen, ORT_NET, &nf, NULL); +} +#ifdef OSPFv3 +static void +process_prefixes(struct ospf_area *oa) +{ + struct proto_ospf *po = oa->po; + struct proto *p = &po->proto; + struct top_hash_entry *en, *src; + struct ospf_lsa_prefix *px; + ip_addr pxa; + int pxlen; + u8 pxopts; + u16 metric; + u32 *buf; + int i; - if (oa->rt == NULL) - return; + WALK_SLIST(en, po->lsal) + { + if (en->lsa.type != LSA_T_PREFIX) + continue; - OSPF_TRACE(D_EVENTS, "Starting routing table calculation for area %R", oa->areaid); + if (en->domain != oa->areaid) + continue; - if (oa->rt->dist != LSINFINITY) - bug("Aging was not processed."); + if (en->lsa.age == LSA_MAXAGE) + continue; - init_list(&oa->cand); /* Empty list of candidates */ - oa->trcap = 0; + px = en->lsa_body; - DBG("LSA db prepared, adding me into candidate list.\n"); + /* For router prefix-LSA, we would like to find the first router-LSA */ + if (px->ref_type == LSA_T_RT) + src = ospf_hash_find_rt(po->gr, oa->areaid, px->ref_rt); + else + src = ospf_hash_find(po->gr, oa->areaid, px->ref_id, px->ref_rt, px->ref_type); - oa->rt->dist = 0; - oa->rt->color = CANDIDATE; - add_head(&oa->cand, &oa->rt->cn); - DBG("RT LSA: rt: %R, id: %R, type: %u\n", - oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa.type); + if (!src) + continue; - while (!EMPTY_LIST(oa->cand)) - { - n = HEAD(oa->cand); - act = SKIP_BACK(struct top_hash_entry, cn, n); - rem_node(n); + if (src->lsa.age == LSA_MAXAGE) + continue; - DBG("Working on LSA: rt: %R, id: %R, type: %u\n", - act->lsa.rt, act->lsa.id, act->lsa.type); + if ((src->lsa.type != LSA_T_RT) && (src->lsa.type != LSA_T_NET)) + continue; - act->color = INSPF; - switch (act->lsa.type) - { - case LSA_T_RT: - rt = (struct ospf_lsa_rt *) act->lsa_body; - if (rt->veb.bit.v) - oa->trcap = 1; - if (rt->veb.bit.b || rt->veb.bit.e) + buf = px->rest; + for (i = 0; i < px->pxcount; i++) { - nf.type = RTS_OSPF; - nf.capa = 0; - if (rt->veb.bit.b) nf.capa |= ORTA_ABR; - if (rt->veb.bit.e) nf.capa |= ORTA_ASBR; - nf.metric1 = act->dist; - nf.metric2 = LSINFINITY; - nf.tag = 0; - nf.oa = oa; - nf.ar = act; - nf.nh = act->nh; - nf.ifa = act->nhi; - ri_install(po, ipa_from_u32(act->lsa.id), 32, ORT_ROUTER, &nf, NULL); + buf = lsa_get_ipv6_prefix(buf, &pxa, &pxlen, &pxopts, &metric); + + if (pxopts & OPT_PX_NU) + continue; + + add_network(oa, pxa, pxlen, src->dist + metric, src); } - rr = (struct ospf_lsa_rt_link *) (rt + 1); - DBG(" Number of links: %u\n", rt->links); - for (i = 0; i < rt->links; i++) - { - tmp = NULL; - rtl = (rr + i); - DBG(" Working on link: %R (type: %u) ", rtl->id, rtl->type); - switch (rtl->type) + } +} +#endif + + +static void +ospf_rt_spfa_rtlinks(struct ospf_area *oa, struct top_hash_entry *act, struct top_hash_entry *en) +{ + struct proto *p = &oa->po->proto; + struct proto_ospf *po = oa->po; + orta nf; + u32 i; + + struct ospf_lsa_rt *rt = en->lsa_body; + struct ospf_lsa_rt_link *rr = (struct ospf_lsa_rt_link *) (rt + 1); + + for (i = 0; i < lsa_rt_count(&en->lsa); i++) + { + struct ospf_lsa_rt_link *rtl = rr + i; + struct top_hash_entry *tmp = NULL; + + DBG(" Working on link: %R (type: %u) ", rtl->id, rtl->type); + switch (rtl->type) { +#ifdef OSPFv2 case LSART_STUB: /* - * This violates rfc2328! but I hope - * it's also correct. + * This violates rfc2328! But it is mostly harmless. */ DBG("\n"); nf.type = RTS_OSPF; - nf.capa = 0; + nf.options = 0; nf.metric1 = act->dist + rtl->metric; nf.metric2 = LSINFINITY; nf.tag = 0; @@ -228,20 +258,20 @@ ospf_rt_spfa(struct ospf_area *oa) nf.ifa = act->nhi; if (act == oa->rt) - { - struct ospf_iface *iff; - - WALK_LIST(iff, po->iface_list) /* Try to find corresponding interface */ { - if (iff->iface && (iff->type != OSPF_IT_VLINK) && - (rtl->id == (ipa_to_u32(ipa_mkmask(iff->iface->addr->pxlen)) - & ipa_to_u32(iff->iface->addr->prefix)))) /* No VLINK and IP must match */ - { - nf.ifa = iff; - break; - } - } - } + struct ospf_iface *iff; + + WALK_LIST(iff, po->iface_list) /* Try to find corresponding interface */ + { + if (iff->iface && (iff->type != OSPF_IT_VLINK) && + (rtl->id == (ipa_to_u32(ipa_mkmask(iff->iface->addr->pxlen)) + & ipa_to_u32(iff->iface->addr->prefix)))) /* No VLINK and IP must match */ + { + nf.ifa = iff; + break; + } + } + } if (!nf.ifa) continue; @@ -249,9 +279,15 @@ ospf_rt_spfa(struct ospf_area *oa) ri_install(po, ipa_from_u32(rtl->id), ipa_mklen(ipa_from_u32(rtl->data)), ORT_NET, &nf, NULL); break; +#endif case LSART_NET: - tmp = ospf_hash_find(po->gr, oa->areaid, rtl->id, rtl->id, LSA_T_NET); +#ifdef OSPFv2 + /* In OSPFv2, rtl->id is IP addres of DR, Router ID is not known */ + tmp = ospf_hash_find_net(po->gr, oa->areaid, rtl->id); +#else /* OSPFv3 */ + tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET); +#endif if (tmp == NULL) DBG("Not found!\n"); else @@ -260,23 +296,75 @@ ospf_rt_spfa(struct ospf_area *oa) case LSART_VLNK: case LSART_PTP: - tmp = ospf_hash_find(po->gr, oa->areaid, rtl->id, rtl->id, LSA_T_RT); + tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id); DBG("PTP found.\n"); break; default: log("Unknown link type in router lsa. (rid = %R)", act->lsa.id); break; } - 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); - } - break; - case LSA_T_NET: - ln = act->lsa_body; + 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); + } +} + +static void +ospf_rt_spfa(struct ospf_area *oa) +{ + struct proto *p = &oa->po->proto; + 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) + return; + + OSPF_TRACE(D_EVENTS, "Starting routing table calculation for area %R", oa->areaid); + + if (oa->rt->dist != LSINFINITY) + bug("Aging was not processed."); + + /* 16.1. (1) */ + init_list(&oa->cand); /* Empty list of candidates */ + oa->trcap = 0; + + DBG("LSA db prepared, adding me into candidate list.\n"); + + oa->rt->dist = 0; + oa->rt->color = CANDIDATE; + add_head(&oa->cand, &oa->rt->cn); + DBG("RT LSA: rt: %R, id: %R, type: %u\n", + oa->rt->lsa.rt, oa->rt->lsa.id, oa->rt->lsa.type); + + while (!EMPTY_LIST(oa->cand)) + { + n = HEAD(oa->cand); + act = SKIP_BACK(struct top_hash_entry, cn, n); + rem_node(n); + + DBG("Working on LSA: rt: %R, id: %R, type: %u\n", + act->lsa.rt, act->lsa.id, act->lsa.type); + + act->color = INSPF; + switch (act->lsa.type) + { + case LSA_T_RT: + rt = (struct ospf_lsa_rt *) act->lsa_body; + 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.capa = 0; + nf.options = rt->options; nf.metric1 = act->dist; nf.metric2 = LSINFINITY; nf.tag = 0; @@ -284,15 +372,30 @@ ospf_rt_spfa(struct ospf_area *oa) nf.ar = act; nf.nh = act->nh; nf.ifa = act->nhi; - ri_install(po, ipa_and(ipa_from_u32(act->lsa.id), ln->netmask), - ipa_mklen(ln->netmask), ORT_NET, &nf, NULL); + ri_install(po, ipa_from_rid(act->lsa.rt), MAX_PREFIX_LENGTH, ORT_ROUTER, &nf, NULL); + +#ifdef OSPFv2 + ospf_rt_spfa_rtlinks(oa, act, act); +#else /* OSPFv3 */ + for (tmp = ospf_hash_find_rt_first(po->gr, act->domain, act->lsa.rt); + tmp; tmp = ospf_hash_find_rt_next(tmp)) + ospf_rt_spfa_rtlinks(oa, act, tmp); +#endif + + break; + case LSA_T_NET: + ln = act->lsa_body; + +#ifdef OSPFv2 + add_network(oa, ipa_and(ipa_from_u32(act->lsa.id), ln->netmask), + ipa_mklen(ln->netmask), act->dist, act); +#endif rts = (u32 *) (ln + 1); - for (i = 0; i < (act->lsa.length - sizeof(struct ospf_lsa_header) - - sizeof(struct ospf_lsa_net)) / sizeof(u32); i++) + for (i = 0; i < lsa_net_count(&act->lsa); i++) { DBG(" Working on router %R ", rts[i]); - tmp = ospf_hash_find(po->gr, oa->areaid, rts[i], rts[i], LSA_T_RT); + tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]); if (tmp != NULL) DBG("Found :-)\n"); else @@ -303,13 +406,17 @@ 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(po->gr, oa->areaid, iface->vid, iface->vid, LSA_T_RT)) && - (!ipa_equal(tmp->lb, IPA_NONE))) + 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->iface != tmp->nhi->iface) || (!ipa_equal(iface->vip, tmp->lb))) { @@ -333,22 +440,25 @@ ospf_rt_spfa(struct ospf_area *oa) } static int -link_back(struct ospf_area *oa, struct top_hash_entry *fol, struct top_hash_entry *pre) +link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par) { u32 i, *rts; struct ospf_lsa_net *ln; struct ospf_lsa_rt *rt; struct ospf_lsa_rt_link *rtl, *rr; + struct top_hash_entry *tmp; struct proto_ospf *po = oa->po; - if (!pre) return 0; - if (!fol) return 0; - switch (fol->lsa.type) + if (!en || !par) return 0; + + // FIXME lb should be properly set for vlinks */ + en->lb = IPA_NONE; + switch (en->lsa.type) { case LSA_T_RT: - rt = (struct ospf_lsa_rt *) fol->lsa_body; + rt = (struct ospf_lsa_rt *) en->lsa_body; rr = (struct ospf_lsa_rt_link *) (rt + 1); - for (i = 0; i < rt->links; i++) + for (i = 0; i < lsa_rt_count(&en->lsa); i++) { rtl = (rr + i); switch (rtl->type) @@ -356,40 +466,41 @@ link_back(struct ospf_area *oa, struct top_hash_entry *fol, struct top_hash_entr case LSART_STUB: break; case LSART_NET: - if (ospf_hash_find(po->gr, oa->areaid, rtl->id, rtl->id, LSA_T_NET) == pre) - { - fol->lb = ipa_from_u32(rtl->data); +#ifdef OSPFv2 + /* In OSPFv2, rtl->id is IP addres of DR, Router ID is not known */ + tmp = ospf_hash_find_net(po->gr, oa->areaid, rtl->id); +#else /* OSPFv3 */ + tmp = ospf_hash_find(po->gr, oa->areaid, rtl->nif, rtl->id, LSA_T_NET); +#endif + if (tmp == par) return 1; - } + break; case LSART_VLNK: case LSART_PTP: - if (ospf_hash_find(po->gr, oa->areaid, rtl->id, rtl->id, LSA_T_RT) == pre) - { - fol->lb = ipa_from_u32(rtl->data); + tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id); + if (tmp == par) return 1; - } + break; default: - log("Unknown link type in router lsa. (rid = %R)", fol->lsa.id); + log(L_WARN "Unknown link type in router lsa. (rid = %R)", en->lsa.rt); break; } } break; case LSA_T_NET: - ln = fol->lsa_body; + ln = en->lsa_body; rts = (u32 *) (ln + 1); - for (i = 0; i < (fol->lsa.length - sizeof(struct ospf_lsa_header) - - sizeof(struct ospf_lsa_net)) / sizeof(u32); i++) + for (i = 0; i < lsa_net_count(&en->lsa); i++) { - if (ospf_hash_find(po->gr, oa->areaid, *(rts + i), *(rts + i), LSA_T_RT) == pre) - { + tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]); + if (tmp == par) return 1; - } } break; default: - bug("Unknown lsa type. (id = %R)", fol->lsa.id); + bug("Unknown lsa type %x.", en->lsa.type); } return 0; } @@ -400,10 +511,10 @@ ospf_rt_sum_tr(struct ospf_area *oa) struct proto *p = &oa->po->proto; struct proto_ospf *po = oa->po; struct ospf_area *bb = po->backbone; - ip_addr *mask, ip, abrip; + ip_addr ip, abrip; struct top_hash_entry *en; - int mlen = -1, type = -1; - union ospf_lsa_sum_tm *tm; + u32 dst_rid, metric, options; + int pxlen = -1, type = -1; ort *re = NULL, *abr; orta nf; @@ -411,57 +522,81 @@ ospf_rt_sum_tr(struct ospf_area *oa) WALK_SLIST(en, po->lsal) { - if (en->oa != oa) - continue; - if (en->lsa.age == LSA_MAXAGE) + if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET)) continue; - if (en->dist == LSINFINITY) + + if (en->domain != oa->areaid) continue; - if (en->lsa.rt == p->cf->global->router_id) + if (en->lsa.age == LSA_MAXAGE) continue; - if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET)) + if (en->dist == LSINFINITY) continue; - mask = (ip_addr *)en->lsa_body; + if (en->lsa.rt == po->router_id) + continue; if (en->lsa.type == LSA_T_SUM_NET) { - mlen = ipa_mklen(*mask); - ip = ipa_and(ipa_from_u32(en->lsa.id), *mask); +#ifdef OSPFv2 + struct ospf_lsa_sum *ls = en->lsa_body; + pxlen = ipa_mklen(ls->netmask); + ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask); +#else /* OSPFv3 */ + u8 pxopts; + u16 rest; + struct ospf_lsa_sum_net *ls = en->lsa_body; + lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest); + + if (pxopts & OPT_PX_NU) + continue; +#endif + + metric = ls->metric & METRIC_MASK; + options = 0; type = ORT_NET; - re = (ort *) fib_find(&po->rtf, &ip, 32); + re = (ort *) fib_find(&po->rtf, &ip, pxlen); } - - if (en->lsa.type == LSA_T_SUM_RT) + else if (en->lsa.type == LSA_T_SUM_RT) { - ip = ipa_from_u32(en->lsa.id); - mlen = 32; +#ifdef OSPFv2 + struct ospf_lsa_sum *ls = en->lsa_body; + dst_rid = en->lsa.id; + options = 0; +#else /* OSPFv3 */ + struct ospf_lsa_sum_rt *ls = en->lsa_body; + dst_rid = ls->drid; + 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 = (ort *) fib_find(&bb->rtr, &ip, 32); + re = (ort *) fib_find(&bb->rtr, &ip, pxlen); } + if (!re) continue; if (re->n.oa->areaid != 0) continue; if ((re->n.type != RTS_OSPF) && (re->n.type != RTS_OSPF_IA)) continue; - abrip = ipa_from_u32(en->lsa.rt); + abrip = ipa_from_rid(en->lsa.rt); - abr = fib_find(&oa->rtr, &abrip, 32); + abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH); if (!abr) continue; - tm = (union ospf_lsa_sum_tm *)(mask + 1); - nf.type = re->n.type; - nf.capa = ORTA_ASBR; - nf.metric1 = abr->n.metric1 + (tm->metric & METRIC_MASK); + 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; - ri_install(po, ip, mlen, type, &nf, NULL); + ri_install(po, ip, pxlen, type, &nf, NULL); } } @@ -472,76 +607,105 @@ ospf_rt_sum(struct ospf_area *oa) struct proto_ospf *po = oa->po; struct proto *p = &po->proto; struct top_hash_entry *en; - ip_addr *mask, ip, abrip; /* abrIP is actually ID */ + ip_addr ip, abrip; /* abrIP is actually ID */ + u32 dst_rid, metric, options; struct area_net *anet; orta nf; ort *abr; - int mlen = -1, type = -1; - union ospf_lsa_sum_tm *tm; + int pxlen = -1, type = -1; OSPF_TRACE(D_EVENTS, "Starting routing table calculation for inter-area (area %R)", oa->areaid); WALK_SLIST(en, po->lsal) { - if (en->oa != oa) + if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET)) continue; + + if (en->domain != oa->areaid) + continue; + /* Page 169 (1) */ if (en->lsa.age == LSA_MAXAGE) continue; - /* Page 169 (2) */ - if (en->lsa.rt == p->cf->global->router_id) - continue; - if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET)) + /* Page 169 (2) */ + if (en->lsa.rt == po->router_id) continue; - mask = (ip_addr *)en->lsa_body; - tm = (union ospf_lsa_sum_tm *)(mask + 1); - - if ((tm->metric & METRIC_MASK) == LSINFINITY) - continue; if (en->lsa.type == LSA_T_SUM_NET) { struct ospf_area *oaa; int skip = 0; - mlen = ipa_mklen(*mask); - ip = ipa_and(ipa_from_u32(en->lsa.id), *mask); + +#ifdef OSPFv2 + struct ospf_lsa_sum *ls = en->lsa_body; + pxlen = ipa_mklen(ls->netmask); + ip = ipa_and(ipa_from_u32(en->lsa.id), ls->netmask); +#else /* OSPFv3 */ + u8 pxopts; + u16 rest; + struct ospf_lsa_sum_net *ls = en->lsa_body; + lsa_get_ipv6_prefix(ls->prefix, &ip, &pxlen, &pxopts, &rest); + + if (pxopts & OPT_PX_NU) + continue; +#endif + + 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, mlen)) && anet->active) + if ((anet = fib_find(&oaa->net_fib, &ip, pxlen)) && anet->active) { skip = 1; break; } } if (skip) continue; - - type = ORT_NET; } else { - ip = ipa_from_u32(en->lsa.id); - mlen = 32; +#ifdef OSPFv2 + struct ospf_lsa_sum *ls = en->lsa_body; + dst_rid = en->lsa.id; + options = 0; +#else /* OSPFv3 */ + struct ospf_lsa_sum_rt *ls = en->lsa_body; + dst_rid = ls->drid; + 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; } - abrip = ipa_from_u32(en->lsa.rt); - if (!(abr = (ort *) fib_find(&oa->rtr, &abrip, 32))) continue; + /* Page 169 (1) */ + if (metric == LSINFINITY) + continue; + + /* Page 169 (4) */ + abrip = ipa_from_rid(en->lsa.rt); + if (!(abr = (ort *) fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH))) continue; if (abr->n.metric1 == LSINFINITY) continue; - if (!(abr->n.capa & ORTA_ABR)) continue; + if (!(abr->n.options & ORTA_ABR)) continue; nf.type = RTS_OSPF_IA; - nf.capa = ORTA_ASBR; - nf.metric1 = abr->n.metric1 + (tm->metric & METRIC_MASK); + 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; - ri_install(po, ip, mlen, type, &nf, NULL); + ri_install(po, ip, pxlen, type, &nf, NULL); } } @@ -567,7 +731,7 @@ ospf_rt_spf(struct proto_ospf *po) OSPF_TRACE(D_EVENTS, "Starting routing table calculation"); - /* Invalidate old routing table */ + /* 16. (1) - Invalidate old routing table */ FIB_WALK(&po->rtf, nftmp) { ri = (ort *) nftmp; @@ -594,9 +758,12 @@ ospf_rt_spf(struct proto_ospf *po) 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)); @@ -606,6 +773,7 @@ ospf_rt_spf(struct proto_ospf *po) ospf_rt_sum(po->backbone); } + /* 16. (4) */ WALK_LIST(oa, po->area_list) { if (oa->trcap && (oa->areaid != 0)) @@ -615,6 +783,7 @@ ospf_rt_spf(struct proto_ospf *po) } } + /* 16. (5) */ ospf_ext_spf(po); rt_sync(po); @@ -622,13 +791,12 @@ ospf_rt_spf(struct proto_ospf *po) po->calcrt = 0; } - /** * ospf_ext_spf - calculate external paths * @po: protocol * * After routing table for any area is calculated, calculation of external - * path is invoked. This process is described in 16.6 of RFC 2328. + * path is invoked. This process is described in 16.4 of RFC 2328. * Inter- and Intra-area paths are always prefered over externals. */ static void @@ -639,54 +807,80 @@ ospf_ext_spf(struct proto_ospf *po) struct top_hash_entry *en; struct proto *p = &po->proto; struct ospf_lsa_ext *le; - struct ospf_lsa_ext_tos *lt; - int mlen; - ip_addr ip, nh, rtid; + int pxlen, ebit, rt_fwaddr_valid; + ip_addr ip, nh, rtid, rt_fwaddr; struct ospf_iface *nhi = NULL; - int met1, met2; + u32 br_metric, rt_metric, rt_tag; neighbor *nn; struct ospf_area *atmp; - OSPF_TRACE(D_EVENTS, "Starting routing table calculation for ext routes"); WALK_SLIST(en, po->lsal) { + /* 16.4. (1) */ if (en->lsa.type != LSA_T_EXT) continue; if (en->lsa.age == LSA_MAXAGE) continue; - if (en->lsa.rt == p->cf->global->router_id) + + /* 16.4. (2) */ + if (en->lsa.rt == po->router_id) continue; + DBG("%s: Working on LSA. ID: %R, RT: %R, Type: %u\n", + p->name, en->lsa.id, en->lsa.rt, en->lsa.type); + le = en->lsa_body; - lt = (struct ospf_lsa_ext_tos *) (le + 1); - DBG("%s: Working on LSA. ID: %R, RT: %R, Type: %u, Mask %I\n", - p->name, en->lsa.id, en->lsa.rt, en->lsa.type, le->netmask); + rt_metric = le->metric & METRIC_MASK; + ebit = le->metric & LSA_EXT_EBIT; - if ((lt->etm.metric & METRIC_MASK) == LSINFINITY) + if (rt_metric == LSINFINITY) continue; + +#ifdef OSPFv2 ip = ipa_and(ipa_from_u32(en->lsa.id), le->netmask); - mlen = ipa_mklen(le->netmask); - if ((mlen < 0) || (mlen > 32)) + pxlen = ipa_mklen(le->netmask); + rt_fwaddr = le->fwaddr; + rt_fwaddr_valid = !ipa_equal(rt_fwaddr, IPA_NONE); + rt_tag = le->tag; +#else /* OSPFv3 */ + u8 pxopts; + u16 rest; + u32 *buf = le->rest; + buf = lsa_get_ipv6_prefix(buf, &ip, &pxlen, &pxopts, &rest); + + if (pxopts & OPT_PX_NU) + continue; + + rt_fwaddr_valid = le->metric & LSA_EXT_FBIT; + if (rt_fwaddr_valid) + buf = lsa_get_ipv6_addr(buf, &rt_fwaddr); + else + rt_fwaddr = IPA_NONE; + + if (le->metric & LSA_EXT_TBIT) + rt_tag = *buf++; + else + rt_tag = 0; +#endif + + if (pxlen < 0) { - log("%s: Invalid mask in LSA. ID: %R, RT: %R, Type: %u, Mask %I", - p->name, en->lsa.id, en->lsa.rt, en->lsa.type, le->netmask); + log(L_WARN "%s: Invalid mask in LSA (Type: %04x, Id: %R, Rt: %R)", + p->name, en->lsa.type, en->lsa.id, en->lsa.rt); continue; } nhi = NULL; nh = IPA_NONE; - met1 = LSINFINITY; - met2 = LSINFINITY; - - rtid = ipa_from_u32(en->lsa.rt); - + /* 16.4. (3) */ + rtid = ipa_from_rid(en->lsa.rt); nf1 = NULL; WALK_LIST(atmp, po->area_list) { - nfh = fib_find(&atmp->rtr, &rtid, 32); + nfh = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH); if (nfh == NULL) continue; if (nf1 == NULL) nf1 = nfh; else if (ri_better(po, &nfh->n, NULL, &nf1->n, NULL, po->rfc1583)) nf1 = nfh; @@ -698,50 +892,29 @@ ospf_ext_spf(struct proto_ospf *po) if (nf1->n.metric1 == LSINFINITY) continue; /* distance is INF */ - if (!(nf1->n.capa & ORTA_ASBR)) + if (!(nf1->n.options & ORTA_ASBR)) continue; /* It is not ASBR */ - if (ipa_equal(lt->fwaddr, IPA_NONE)) + if (!rt_fwaddr_valid) { - if (lt->etm.etos.ebit) - { /* FW address == 0 */ - met1 = nf1->n.metric1; - met2 = (lt->etm.metric & METRIC_MASK); - } - else - { - met1 = nf1->n.metric1 + (lt->etm.metric & METRIC_MASK); - met2 = LSINFINITY; - } - nh = nf1->n.nh; nhi = nf1->n.ifa; nfh = nf1; + br_metric = nf1->n.metric1; } else - { /* FW address !=0 */ - nf2 = fib_route(&po->rtf, lt->fwaddr, 32); + { + nf2 = fib_route(&po->rtf, rt_fwaddr, MAX_PREFIX_LENGTH); if (!nf2) { - DBG("Cannot find network route (GW=%I)\n", lt->fwaddr); + DBG("Cannot find network route (GW=%I)\n", rt_fwaddr); continue; } - if (lt->etm.etos.ebit) - { - met1 = nf2->n.metric1; - met2 = (lt->etm.metric & METRIC_MASK); - } - else - { - met1 = nf2->n.metric1 + (lt->etm.metric & METRIC_MASK); - met2 = LSINFINITY; - } - - if ((nn = neigh_find(p, <->fwaddr, 0)) != NULL) + if ((nn = neigh_find(p, &rt_fwaddr, 0)) != NULL) { - nh = lt->fwaddr; + nh = rt_fwaddr; nhi = ospf_iface_find(po, nn->iface); } else @@ -750,20 +923,31 @@ ospf_ext_spf(struct proto_ospf *po) nhi = nf2->n.ifa; } - if (nf2->n.metric1 == LSINFINITY) + br_metric = nf2->n.metric1; + if (br_metric == LSINFINITY) continue; /* distance is INF */ } - nfa.type = (met2 == LSINFINITY) ? RTS_OSPF_EXT1 : RTS_OSPF_EXT2; - nfa.capa = 0; - nfa.metric1 = met1; - nfa.metric2 = met2; - nfa.tag = lt->tag; + if (ebit) + { + nfa.type = RTS_OSPF_EXT2; + nfa.metric1 = br_metric; + nfa.metric2 = rt_metric; + } + else + { + nfa.type = RTS_OSPF_EXT1; + nfa.metric1 = br_metric + rt_metric; + nfa.metric2 = LSINFINITY; + } + + nfa.options = 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; - ri_install(po, ip, mlen, ORT_NET, &nfa, nfh); + ri_install(po, ip, pxlen, ORT_NET, &nfa, nfh); } } @@ -771,22 +955,32 @@ ospf_ext_spf(struct proto_ospf *po) /* 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, - u16 dist, struct ospf_area *oa) + u32 dist, struct ospf_area *oa) { node *prev, *n; int added = 0; struct top_hash_entry *act; - ip_addr old_nh; - struct ospf_iface *old_nhi; + /* 16.1. (2b) */ if (en == NULL) return; if (en->lsa.age == LSA_MAXAGE) return; +#ifdef OSPFv3 + if (en->lsa.type == LSA_T_RT) + { + struct ospf_lsa_rt *rt = en->lsa_body; + if (!(rt->options & OPT_V6) || !(rt->options & OPT_R)) + return; + } +#endif + + /* 16.1. (2c) */ if (en->color == INSPF) return; + /* 16.1. (2d) */ if (dist >= en->dist) return; /* @@ -794,27 +988,20 @@ add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par, * next hops. I'll start as soon as nest will */ + /* We should check whether there is a reverse link from en to par, */ if (!link_back(oa, en, par)) return; + if (!calc_next_hop(oa, en, par)) + { + log(L_WARN "Cannot find next hop for LSA (Type: %04x, Id: %R, Rt: %R)", + en->lsa.type, en->lsa.id, en->lsa.rt); + return; + } + DBG(" Adding candidate: rt: %R, id: %R, type: %u\n", en->lsa.rt, en->lsa.id, en->lsa.type); - old_nhi = en->nhi; - old_nh = en->nh; - - en->nhi = NULL; - en->nh = IPA_NONE; - calc_next_hop(en, par, oa); - - if (!en->nhi) - { - /* No next hop found, we undo changes and return */ - en->nhi = old_nhi; - en->nh = old_nh; - return; - } - if (en->color == CANDIDATE) { /* We found a shorter path */ rem_node(&en->cn); @@ -835,6 +1022,7 @@ add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par, act = SKIP_BACK(struct top_hash_entry, cn, n); if ((act->dist > dist) || ((act->dist == dist) && (act->lsa.type == LSA_T_NET))) + /* FIXME - shouldn't be here LSA_T_RT ??? */ { if (prev == NULL) add_head(l, &en->cn); @@ -853,84 +1041,85 @@ add_cand(list * l, struct top_hash_entry *en, struct top_hash_entry *par, } } -static void -calc_next_hop(struct top_hash_entry *en, struct top_hash_entry *par, - struct ospf_area *oa) + +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 int +calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en, + struct top_hash_entry *par) { struct ospf_neighbor *neigh; struct proto *p = &oa->po->proto; struct proto_ospf *po = oa->po; struct ospf_iface *ifa; - u32 myrid = p->cf->global->router_id; + /* 16.1.1. The next hop calculation */ DBG(" Next hop called.\n"); if (ipa_equal(par->nh, IPA_NONE)) { - neighbor *nn; DBG(" Next hop calculating for id: %R rt: %R type: %u\n", en->lsa.id, en->lsa.rt, en->lsa.type); - if (par == oa->rt) + /* + * There are three cases: + * 1) en is a local network (and par is root) + * 2) en is a ptp or ptmp neighbor (and par is root) + * 3) en is a bcast or nbma neighbor (and par is local network) + */ + + /* The first case - local network */ + if ((en->lsa.type == LSA_T_NET) && (par == oa->rt)) { - if (en->lsa.type == LSA_T_NET) - { - if (en->lsa.rt == myrid) - { - WALK_LIST(ifa, po->iface_list) - if (ifa->iface && (ipa_compare - (ifa->iface->addr->ip, ipa_from_u32(en->lsa.id)) == 0)) + WALK_LIST(ifa, po->iface_list) + if (match_dr(ifa, en)) { + en->nh = IPA_NONE; en->nhi = ifa; - return; + return 1; } - log(L_ERR "I didn't find interface for my self originated LSA!\n"); - /* This could sometimes happen */ - return; - } - else - { - ip_addr ip = ipa_from_u32(en->lsa.id); - nn = neigh_find(p, &ip, 0); - if (nn) - en->nhi = ospf_iface_find(po, nn->iface); - return; - } - } - else - { - if ((neigh = find_neigh_noifa(po, en->lsa.rt)) == NULL) - return; - en->nhi = neigh->ifa; - if (ipa_equal(en->nh, IPA_NONE)) - en->nh = neigh->ip; /* Yes, neighbor is it's - * own next hop */ - return; - } + return 0; } - if (par->lsa.type == LSA_T_NET) + + /* + * Remaining cases - local neighbours. + * There are two problems with this code: + * 1) we use IP address from HELLO packet + * and not the one from LSA (router or link). + * This may break NBMA networks + * 2) we use find_neigh_noifa() and does not + * take into account associated iface. + * This breaks neighbors connected by more links. + */ + + if ((en->lsa.type == LSA_T_RT) && + ((par == oa->rt) || (par->lsa.type == LSA_T_NET))) { - if (en->lsa.type == LSA_T_NET) - bug("Parent for net is net?"); - if ((en->nhi = par->nhi) == NULL) - bug("Did not find next hop interface for INSPF lsa!"); - if ((neigh = find_neigh_noifa(po, en->lsa.rt)) == NULL) - return; - en->nhi = neigh->ifa; - en->nh = neigh->ip; /* Yes, neighbor is it's own - * next hop */ - return; - } - else - { /* Parent is some RT neighbor */ - log(L_ERR "Router's parent has no next hop. (EN=%R, PAR=%R)", - en->lsa.id, par->lsa.id); - /* I hope this would never happen */ - return; + if ((neigh = find_neigh_noifa(po, en->lsa.rt)) != NULL) + { + en->nh = neigh->ip; + en->nhi = neigh->ifa; + return 1; + } + return 0; } + + /* Probably bug or some race condition, we log it */ + log(L_ERR "Unexpected case in next hop calculation"); + + return 0; } + en->nh = par->nh; en->nhi = par->nhi; - DBG(" Next hop calculated: %I.\n", en->nh); + return 1; } static void @@ -944,6 +1133,9 @@ rt_sync(struct proto_ospf *po) struct area_net *anet; int flush; + /* This is used for forced reload of routes */ + int reload = (po->calcrt == 2); + OSPF_TRACE(D_EVENTS, "Starting routing table synchronisation"); DBG("Now syncing my rt table with nest's\n"); @@ -953,7 +1145,7 @@ again1: { nf = (ort *) nftmp; check_sum_lsa(po, nf, ORT_NET); - if (memcmp(&nf->n, &nf->o, sizeof(orta))) + if (reload || memcmp(&nf->n, &nf->o, sizeof(orta))) { /* Some difference */ net *ne; rta a0; @@ -972,18 +1164,18 @@ again1: if (nf->n.ifa) a0.iface = nf->n.ifa->iface; a0.gw = nf->n.nh; - if ((!ipa_equal(nf->n.nh, IPA_NONE)) && (!neigh_find(p, &nf->n.nh, 0))) + 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"); + 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(po->gr, ifa->voa->areaid, ifa->vid, ifa->vid, LSA_T_RT)) - && (!ipa_equal(en->nh, IPA_NONE))) + 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; @@ -1063,7 +1255,7 @@ again2: if (oaa->stub) fl = 1; if (fl) flush_sum_lsa(oaa, &anet->fn, ORT_NET); - else originate_sum_lsa(oaa, &anet->fn, ORT_NET, anet->metric); + else originate_sum_lsa(oaa, &anet->fn, ORT_NET, anet->metric, 0); } } FIB_WALK_END; @@ -1076,7 +1268,7 @@ again2: fnn.prefix = IPA_NONE; fnn.pxlen = 0; - if (oa->stub) originate_sum_lsa(oa, &fnn, ORT_NET, oa->stub); + if (oa->stub) originate_sum_lsa(oa, &fnn, ORT_NET, oa->stub, 0); else flush_sum_lsa(oa, &fnn, ORT_NET); } } |