/* * BIRD -- OSPF * * (c) 2000--2004 Ondrej Filip * * Can be freely distributed and used under the terms of the GNU GPL. */ #include "ospf.h" 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); 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 inline void reset_ri(ort *ort) { bzero(&ort->n, sizeof(orta)); } void ospf_rt_initort(struct fib_node *fn) { ort *ri = (ort *) fn; reset_ri(ri); ri->old_rta = NULL; ri->fn.x0 = 0; } static inline int unresolved_vlink(struct mpnh *nhs) { return nhs && !nhs->iface; } static inline struct mpnh * new_nexthop(struct proto_ospf *po, ip_addr gw, struct iface *iface, unsigned char weight) { struct mpnh *nh = lp_alloc(po->nhpool, sizeof(struct mpnh)); nh->gw = gw; nh->iface = iface; nh->next = NULL; nh->weight = weight; return nh; } static inline struct mpnh * copy_nexthop(struct proto_ospf *po, struct mpnh *src) { struct mpnh *nh = lp_alloc(po->nhpool, sizeof(struct mpnh)); nh->gw = src->gw; nh->iface = src->iface; nh->next = NULL; nh->weight = src->weight; return nh; } /* If new is better return 1 */ static int ri_better(struct proto_ospf *po, orta *new, orta *old) { if (old->type == RTS_DUMMY) return 1; 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; } /* 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); } /* 16.4. (3), return 1 if new is better */ static int ri_better_asbr(struct proto_ospf *po, orta *new, orta *old) { if (old->type == RTS_DUMMY) return 1; if (!po->rfc1583) { 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 (new->metric1 < old->metric1) return 1; if (new->metric1 > old->metric1) return 0; /* 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; /* 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; } /* 16.4. (6c) */ if (!po->rfc1583) { u32 new_pref = new->options & ORTA_PREF; u32 old_pref = old->options & ORTA_PREF; if (new_pref > old_pref) return 1; if (new_pref < old_pref) return 0; } /* 16.4. (6d) */ if (new->metric1 < old->metric1) return 1; if (new->metric1 > old->metric1) return 0; return 0; } 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 inline void ri_install_rt(struct ospf_area *oa, u32 rid, orta *new) { 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)); } static inline void ri_install_asbr(struct proto_ospf *po, ip_addr *addr, orta *new) { ort *old = (ort *) fib_get(&po->backbone->rtr, addr, MAX_PREFIX_LENGTH); if (ri_better_asbr(po, new, &old->n)) memcpy(&old->n, new, sizeof(orta)); } 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)); } #ifdef OSPFv2 static struct ospf_iface * find_stub_src(struct ospf_area *oa, ip_addr px, int pxlen) { struct ospf_iface *iff; WALK_LIST(iff, oa->po->iface_list) if ((iff->type != OSPF_IT_VLINK) && (iff->oa == oa) && ipa_equal(iff->addr->prefix, px) && (iff->addr->pxlen == pxlen)) return iff; return NULL; } #else /* OSPFv3 */ static struct ospf_iface * find_stub_src(struct ospf_area *oa, ip_addr px, int pxlen) { struct ospf_iface *iff; struct ifa *a; WALK_LIST(iff, oa->po->iface_list) if ((iff->type != OSPF_IT_VLINK) && (iff->oa == oa)) WALK_LIST(a, iff->iface->addrs) if (ipa_equal(a->prefix, px) && (a->pxlen == pxlen) && !(a->flags & IA_SECONDARY)) return iff; return NULL; } #endif static void add_network(struct ospf_area *oa, ip_addr px, int pxlen, int metric, struct top_hash_entry *en) { orta nf = { .type = RTS_OSPF, .options = 0, .metric1 = metric, .metric2 = LSINFINITY, .tag = 0, .rid = en->lsa.rt, .oa = oa, .nhs = en->nhs }; if (en == oa->rt) { /* * Local stub networks does not have proper iface in en->nhi * (because they all have common top_hash_entry en). * We have to find iface responsible for that stub network. * Configured stubnets does not have any iface. They will * be removed in rt_sync(). */ struct ospf_iface *ifa = find_stub_src(oa, px, pxlen); nf.nhs = ifa ? new_nexthop(oa->po, IPA_NONE, ifa->iface, ifa->ecmp_weight) : NULL; } ri_install_net(oa->po, px, pxlen, &nf); } #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; WALK_SLIST(en, po->lsal) { if (en->lsa.type != LSA_T_PREFIX) continue; if (en->domain != oa->areaid) continue; if (en->lsa.age == LSA_MAXAGE) continue; px = en->lsa_body; /* 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); if (!src) continue; /* Reachable in SPF */ if (src->color != INSPF) continue; if ((src->lsa.type != LSA_T_RT) && (src->lsa.type != LSA_T_NET)) continue; buf = px->rest; for (i = 0; i < px->pxcount; i++) { buf = lsa_get_ipv6_prefix(buf, &pxa, &pxlen, &pxopts, &metric); 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); } } } #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; 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: /* * RFC 2328 in 16.1. (2a) says to handle stub networks in an * second phase after the SPF for an area is calculated. We get * the same result by handing them here because add_network() * will keep the best (not the first) found route. */ add_network(oa, ipa_from_u32(rtl->id), ipa_mklen(ipa_from_u32(rtl->data)), act->dist + rtl->metric, act); break; #endif case LSART_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 break; case LSART_VLNK: case LSART_PTP: tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id); 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, rtl); } } /* RFC 2328 16.1. calculating shortest paths for an area */ 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 top_hash_entry *act, *tmp; u32 i, *rts; node *n; if (oa->rt == NULL) return; OSPF_TRACE(D_EVENTS, "Starting routing table calculation for area %R", oa->areaid); /* 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 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)) && (act->lsa.rt != po->router_id)) { orta nf = { .type = RTS_OSPF, .options = rt->options, .metric1 = act->dist, .metric2 = LSINFINITY, .tag = 0, .rid = act->lsa.rt, .oa = oa, .nhs = act->nhs }; ri_install_rt(oa, act->lsa.rt, &nf); } #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 < lsa_net_count(&act->lsa); i++) { DBG(" Working on router %R ", rts[i]); tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]); if (tmp != NULL) DBG("Found :-)\n"); else DBG("Not found!\n"); add_cand(&oa->cand, tmp, act, act->dist, oa, NULL); } break; } } #ifdef OSPFv3 process_prefixes(oa); #endif } static int 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 (!en || !par) return 0; /* 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; #endif switch (en->lsa.type) { case LSA_T_RT: rt = (struct ospf_lsa_rt *) en->lsa_body; rr = (struct ospf_lsa_rt_link *) (rt + 1); for (i = 0; i < lsa_rt_count(&en->lsa); i++) { rtl = (rr + i); switch (rtl->type) { case LSART_STUB: break; case LSART_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 == par) { #ifdef OSPFv2 en->lb = ipa_from_u32(rtl->data); #else /* OSPFv3 */ en->lb_id = rtl->lif; #endif return 1; } break; case LSART_VLNK: case LSART_PTP: tmp = ospf_hash_find_rt(po->gr, oa->areaid, rtl->id); if (tmp == par) return 1; break; default: log(L_WARN "Unknown link type in router lsa. (rid = %R)", en->lsa.rt); break; } } break; case LSA_T_NET: ln = en->lsa_body; rts = (u32 *) (ln + 1); for (i = 0; i < lsa_net_count(&en->lsa); i++) { tmp = ospf_hash_find_rt(po->gr, oa->areaid, rts[i]); if (tmp == par) return 1; } break; default: bug("Unknown lsa type %x.", en->lsa.type); } return 0; } /* RFC 2328 16.2. calculating inter-area routes */ static void 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 ip = IPA_NONE; u32 dst_rid = 0; u32 metric, options; ort *abr; 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->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET)) continue; if (en->domain != oa->areaid) continue; /* 16.2. (1a) */ if (en->lsa.age == LSA_MAXAGE) continue; /* 16.2. (2) */ if (en->lsa.rt == po->router_id) continue; /* 16.2. (3) is handled later in ospf_rt_abr() by resetting such rt entry */ if (en->lsa.type == LSA_T_SUM_NET) { #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; } else /* LSA_T_SUM_RT */ { #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 /* We don't want local router in ASBR routing table */ if (dst_rid == po->router_id) continue; metric = ls->metric & METRIC_MASK; options |= ORTA_ASBR; type = ORT_ROUTER; } /* 16.2. (1b) */ if (metric == LSINFINITY) 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; if (!(abr->n.options & ORTA_ABR)) continue; /* This check is not mentioned in RFC 2328 */ if (abr->n.type != RTS_OSPF) 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, .nhs = abr->n.nhs }; if (type == ORT_NET) ri_install_net(po, ip, pxlen, &nf); else ri_install_rt(oa, dst_rid, &nf); } } /* RFC 2328 16.3. examining summary-LSAs in transit areas */ static void 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 abrip; struct top_hash_entry *en; u32 dst_rid, metric; ort *re = NULL, *abr; if (!bb) return; WALK_SLIST(en, po->lsal) { if ((en->lsa.type != LSA_T_SUM_RT) && (en->lsa.type != LSA_T_SUM_NET)) continue; if (en->domain != oa->areaid) continue; /* 16.3 (1a) */ if (en->lsa.age == LSA_MAXAGE) continue; /* 16.3 (2) */ if (en->lsa.rt == po->router_id) continue; if (en->lsa.type == LSA_T_SUM_NET) { ip_addr ip; int pxlen; #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; re = fib_find(&po->rtf, &ip, pxlen); } else // en->lsa.type == LSA_T_SUM_RT { #ifdef OSPFv2 struct ospf_lsa_sum *ls = en->lsa_body; dst_rid = en->lsa.id; #else /* OSPFv3 */ struct ospf_lsa_sum_rt *ls = en->lsa_body; dst_rid = ls->drid; #endif metric = ls->metric & METRIC_MASK; ip_addr ip = ipa_from_rid(dst_rid); re = fib_find(&bb->rtr, &ip, MAX_PREFIX_LENGTH); } /* 16.3 (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.3. (4) */ abrip = ipa_from_rid(en->lsa.rt); abr = fib_find(&oa->rtr, &abrip, MAX_PREFIX_LENGTH); if (!abr || !abr->n.type) continue; metric = abr->n.metric1 + metric; /* IAC */ /* 16.3. (5) */ if ((metric < re->n.metric1) || ((metric == re->n.metric1) && unresolved_vlink(re->n.nhs))) { /* 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. Proper ECMP would merge nexthops here, but we do not do that. We restrict nexthops to fit one area to simplify check 12.4.3 p4 in decide_sum_lsa() */ re->n.metric1 = metric; re->n.voa = oa; re->n.nhs = abr->n.nhs; } } } /* Decide about originating or flushing summary LSAs for condended area networks */ static int decide_anet_lsa(struct ospf_area *oa, struct area_net *anet, struct ospf_area *anet_oa) { if (oa->stub) return 0; if (oa == anet_oa) return 0; /* Do not condense routing info when exporting from backbone to the transit area */ if ((anet_oa == oa->po->backbone) && oa->trcap) return 0; return (anet->active && !anet->hidden); } /* Decide about originating or flushing summary LSAs (12.4.3) */ static int decide_sum_lsa(struct ospf_area *oa, ort *nf, int dest) { /* 12.4.3.1. - do not send summary into stub areas, we send just default route */ if (oa->stub) return 0; /* Invalid field - no route */ if (!nf->n.type) return 0; /* 12.4.3 p2 */ if (nf->n.type > RTS_OSPF_IA) return 0; /* 12.4.3 p3 */ if ((nf->n.oa->areaid == oa->areaid)) return 0; /* 12.4.3 p4 */ if (nf->n.voa && (nf->n.voa->areaid == oa->areaid)) return 0; /* 12.4.3 p5 */ if (nf->n.metric1 >= LSINFINITY) return 0; /* 12.4.3 p6 - AS boundary router */ if (dest == ORT_ROUTER) { /* We call decide_sum_lsa() on preferred ASBR entries, no need for 16.4. (3) */ /* 12.4.3 p1 */ return (nf->n.options & ORTA_ASBR); } /* 12.4.3 p7 - inter-area route */ if (nf->n.type == RTS_OSPF_IA) { /* Inter-area routes are not repropagated into the backbone */ return (oa != oa->po->backbone); } /* 12.4.3 p8 - intra-area route */ /* Do not condense routing info when exporting from backbone to the transit area */ if ((nf->n.oa == oa->po->backbone) && oa->trcap) return 1; struct area_net *anet = (struct area_net *) fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen); /* Condensed area network found */ if (anet) return 0; return 1; } /* RFC 2328 16.7. p1 - originate or flush summary LSAs */ static inline void check_sum_net_lsa(struct proto_ospf *po, ort *nf) { struct area_net *anet = NULL; struct ospf_area *anet_oa = NULL; /* RT entry marked as area network */ if (nf->fn.x0) { /* It is a default route for stub areas, handled entirely in ospf_rt_abr() */ if (nf->fn.pxlen == 0) return; /* Find that area network */ WALK_LIST(anet_oa, po->area_list) { anet = (struct area_net *) fib_find(&anet_oa->net_fib, &nf->fn.prefix, nf->fn.pxlen); if (anet) break; } } struct ospf_area *oa; WALK_LIST(oa, po->area_list) { if (anet && decide_anet_lsa(oa, anet, anet_oa)) originate_sum_net_lsa(oa, &nf->fn, anet->metric); else if (decide_sum_lsa(oa, nf, ORT_NET)) originate_sum_net_lsa(oa, &nf->fn, nf->n.metric1); else flush_sum_lsa(oa, &nf->fn, ORT_NET); } } static inline void check_sum_rt_lsa(struct proto_ospf *po, ort *nf) { struct ospf_area *oa; WALK_LIST(oa, po->area_list) { if (decide_sum_lsa(oa, nf, ORT_ROUTER)) originate_sum_rt_lsa(oa, &nf->fn, nf->n.metric1, nf->n.options); else flush_sum_lsa(oa, &nf->fn, ORT_ROUTER); } } /* 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) && ipa_nonzero(tmp->lb) && tmp->nhs) { struct ospf_iface *nhi = ospf_iface_find(po, tmp->nhs->iface); if ((iface->state != OSPF_IS_PTP) || (iface->vifa != 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 = nhi; iface->iface = nhi->iface; iface->addr = nhi->addr; iface->sk = 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); } } } } } /* Miscellaneous route processing that needs to be done by ABRs */ static void ospf_rt_abr(struct proto_ospf *po) { struct area_net *anet; ort *nf, *default_nf; FIB_WALK(&po->rtf, nftmp) { nf = (ort *) nftmp; /* RFC 2328 G.3 - incomplete resolution of virtual next hops */ if (nf->n.type && unresolved_vlink(nf->n.nhs)) reset_ri(nf); /* Compute condensed area networks */ if (nf->n.type == RTS_OSPF) { anet = (struct area_net *) fib_route(&nf->n.oa->net_fib, nf->fn.prefix, nf->fn.pxlen); if (anet) { if (!anet->active) { anet->active = 1; /* Get a RT entry and mark it to know that it is an area network */ ort *nfi = (ort *) fib_get(&po->rtf, &anet->fn.prefix, anet->fn.pxlen); nfi->fn.x0 = 1; /* mark and keep persistent, to have stable UID */ /* 16.2. (3) */ if (nfi->n.type == RTS_OSPF_IA) reset_ri(nfi); } if (anet->metric < nf->n.metric1) anet->metric = nf->n.metric1; } } } FIB_WALK_END; ip_addr addr = IPA_NONE; default_nf = (ort *) fib_get(&po->rtf, &addr, 0); default_nf->fn.x0 = 1; /* keep persistent */ struct ospf_area *oa; WALK_LIST(oa, po->area_list) { /* 12.4.3.1. - originate or flush default summary LSA for stub areas */ if (oa->stub) originate_sum_net_lsa(oa, &default_nf->fn, oa->stub); else flush_sum_lsa(oa, &default_nf->fn, ORT_NET); /* RFC 2328 16.4. (3) - precompute preferred ASBR entries */ FIB_WALK(&oa->rtr, nftmp) { nf = (ort *) nftmp; if (nf->n.options & ORTA_ASBR) ri_install_asbr(po, &nf->fn.prefix, &nf->n); } FIB_WALK_END; } /* Originate or flush ASBR summary LSAs */ FIB_WALK(&po->backbone->rtr, nftmp) { check_sum_rt_lsa(po, (ort *) nftmp); } FIB_WALK_END; /* RFC 2328 16.7. p2 - find new/lost vlink endpoints */ ospf_check_vlinks(po); } /* Like fib_route(), but ignores dummy rt entries */ static void * ospf_fib_route(struct fib *f, ip_addr a, int len) { ip_addr a0; ort *nf; while (len >= 0) { a0 = ipa_and(a, ipa_mkmask(len)); nf = fib_find(f, &a0, len); if (nf && nf->n.type) return nf; len--; } return NULL; } /* RFC 2328 16.4. calculating external routes */ static void ospf_ext_spf(struct proto_ospf *po) { ort *nf1, *nf2; orta nfa; struct top_hash_entry *en; struct proto *p = &po->proto; struct ospf_lsa_ext *le; int pxlen, ebit, rt_fwaddr_valid; ip_addr ip, rtid, rt_fwaddr; u32 br_metric, rt_metric, rt_tag; struct ospf_area *atmp; struct mpnh* nhs = NULL; 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; /* 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; rt_metric = le->metric & METRIC_MASK; ebit = le->metric & LSA_EXT_EBIT; if (rt_metric == LSINFINITY) continue; #ifdef OSPFv2 ip = ipa_and(ipa_from_u32(en->lsa.id), le->netmask); 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(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; } /* 16.4. (3) */ /* If there are more areas, we already precomputed preferred ASBR entries in ospf_asbr_spf() and stored them in the backbone table */ atmp = (po->areano > 1) ? po->backbone : HEAD(po->area_list); rtid = ipa_from_rid(en->lsa.rt); nf1 = fib_find(&atmp->rtr, &rtid, MAX_PREFIX_LENGTH); if (!nf1 || !nf1->n.type) continue; /* No AS boundary router found */ if (!(nf1->n.options & ORTA_ASBR)) continue; /* It is not ASBR */ if (!rt_fwaddr_valid) { nf2 = nf1; nhs = nf1->n.nhs; br_metric = nf1->n.metric1; } else { nf2 = ospf_fib_route(&po->rtf, rt_fwaddr, MAX_PREFIX_LENGTH); if (!nf2) continue; if ((nf2->n.type != RTS_OSPF) && (nf2->n.type != RTS_OSPF_IA)) continue; /* Next-hop is a part of a configured stubnet */ if (!nf2->n.nhs) continue; nhs = nf2->n.nhs; /* If gw is zero, it is a device route */ if (ipa_zero(nhs->gw)) nhs = new_nexthop(po, rt_fwaddr, nhs->iface, nhs->weight); br_metric = nf2->n.metric1; } 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; } /* Mark the LSA as reachable */ en->color = INSPF; /* 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.rid = en->lsa.rt; nfa.oa = nf1->n.oa; /* undefined in RFC 2328 */ nfa.voa = NULL; nfa.nhs = nhs; ri_install_ext(po, ip, pxlen, &nfa); } } /* Cleanup of routing tables and data */ void ospf_rt_reset(struct proto_ospf *po) { struct ospf_area *oa; struct top_hash_entry *en; struct area_net *anet; ort *ri; /* Reset old routing table */ FIB_WALK(&po->rtf, nftmp) { ri = (ort *) nftmp; ri->fn.x0 = 0; reset_ri(ri); } FIB_WALK_END; /* Reset SPF data in LSA db */ WALK_SLIST(en, po->lsal) { en->color = OUTSPF; en->dist = LSINFINITY; en->nhs = NULL; en->lb = IPA_NONE; } WALK_LIST(oa, po->area_list) { /* Reset ASBR routing tables */ FIB_WALK(&oa->rtr, nftmp) { ri = (ort *) nftmp; reset_ri(ri); } FIB_WALK_END; /* Reset condensed area networks */ if (po->areano > 1) { FIB_WALK(&oa->net_fib, nftmp) { anet = (struct area_net *) nftmp; anet->active = 0; anet->metric = 0; } FIB_WALK_END; } } } /** * 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; if (po->areano == 0) return; OSPF_TRACE(D_EVENTS, "Starting routing table calculation"); /* 16. (1) */ ospf_rt_reset(po); /* 16. (2) */ WALK_LIST(oa, po->area_list) ospf_rt_spfa(oa); /* 16. (3) */ if (po->areano == 1) 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); if (po->areano > 1) ospf_rt_abr(po); /* 16. (5) */ ospf_ext_spf(po); rt_sync(po); lp_flush(po->nhpool); 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->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->cost == rtl->metric) && (ifa->iface->index == rtl->lif); #endif } static inline int inherit_nexthops(struct mpnh *pn) { /* Proper nexthops (with defined GW) or dummy vlink nexthops (without iface) */ return pn && (ipa_nonzero(pn->gw) || !pn->iface); } 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 proto *p = &oa->po->proto; struct proto_ospf *po = oa->po; struct mpnh *pn = par->nhs; struct ospf_iface *ifa; u32 rid = en->lsa.rt; /* 16.1.1. The next hop calculation */ DBG(" Next hop calculating for id: %R rt: %R type: %u\n", en->lsa.id, en->lsa.rt, en->lsa.type); /* Usually, we inherit parent nexthops */ if (inherit_nexthops(pn)) return pn; /* * 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)) { WALK_LIST(ifa, po->iface_list) if (match_dr(ifa, en)) return new_nexthop(po, IPA_NONE, ifa->iface, ifa->ecmp_weight); return NULL; } /* The second case - ptp or ptmp neighbor */ if ((en->lsa.type == LSA_T_RT) && (par == oa->rt)) { 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); } return NULL; } /* The third case - bcast or nbma neighbor */ if ((en->lsa.type == LSA_T_RT) && (par->lsa.type == LSA_T_NET)) { /* par->nhi should be defined from parent's calc_next_hop() */ if (!pn) goto bad; #ifdef OSPFv2 /* * In this case, next-hop is the same as link-back, which is * already computed in link_back(). */ if (ipa_zero(en->lb)) goto bad; return new_nexthop(po, en->lb, pn->iface, pn->weight); #else /* OSPFv3 */ /* * Next-hop is taken from lladdr field of Link-LSA, en->lb_id * is computed in link_back(). */ struct top_hash_entry *lhe; lhe = ospf_hash_find(po->gr, pn->iface->index, en->lb_id, rid, LSA_T_LINK); if (!lhe) return NULL; struct ospf_lsa_link *llsa = lhe->lsa_body; if (ipa_zero(llsa->lladdr)) return NULL; return new_nexthop(po, llsa->lladdr, pn->iface, pn->weight); #endif } bad: /* Probably bug or some race condition, we log it */ log(L_ERR "Unexpected case in next hop calculation"); return NULL; } /* Compare nexthops during merge. We need to maintain nhs sorted to eliminate duplicities */ static int cmp_nhs(struct mpnh *s1, struct mpnh *s2) { int r; if (!s1) return 1; if (!s2) return -1; r = ((int) s2->weight) - ((int) s1->weight); if (r) return r; r = ipa_compare(s1->gw, s2->gw); if (r) return r; return ((int) s1->iface->index) - ((int) s2->iface->index); } static void merge_nexthops(struct proto_ospf *po, struct top_hash_entry *en, struct top_hash_entry *par, struct mpnh *new) { if (en->nhs == new) return; int r1 = en->nhs_reuse; int r2 = (par->nhs != new); int count = po->ecmp; struct mpnh *s1 = en->nhs; struct mpnh *s2 = new; struct mpnh **n = &(en->nhs); /* * r1, r2 signalize whether we can reuse nexthops from s1, s2. * New nexthops (s2, new) can be reused if they are not inherited * from the parent (i.e. it is allocated in calc_next_hop()). * Current nexthops (s1, en->nhs) can be reused if they weren't * inherited in previous steps (that is stored in nhs_reuse, * i.e. created by merging or allocalted in calc_next_hop()). * * Generally, a node first inherits shared nexthops from its * parent and later possibly gets reusable copy during merging. */ while ((s1 || s2) && count--) { int cmp = cmp_nhs(s1, s2); if (cmp < 0) { *n = r1 ? s1 : copy_nexthop(po, s1); s1 = s1->next; } else if (cmp > 0) { *n = r2 ? s2 : copy_nexthop(po, s2); s2 = s2->next; } else { *n = r1 ? s1 : (r2 ? s2 : copy_nexthop(po, s1)); s1 = s1->next; s2 = s2->next; } n = &((*n)->next); } *n = NULL; en->nhs_reuse=1; } /* 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) { struct proto_ospf *po = oa->po; node *prev, *n; int added = 0; struct top_hash_entry *act; /* 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), also checks that dist < LSINFINITY */ if (dist > en->dist) return; /* We should check whether there is a reverse link from en to par, */ if (!link_back(oa, en, par)) return; struct mpnh *nhs = calc_next_hop(oa, en, par, rtl); if (!nhs) { 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; } if (dist == en->dist) { /* * For multipath, we should merge nexthops. We do not mix dummy * vlink nexthops, device nexthops and gateway nexthops. We merge * gateway nexthops only. We prefer device nexthops over gateway * nexthops and gateway nexthops over vlink nexthops. We either * keep old nexthops, merge old and new, or replace old with new. * * We know that en->color == CANDIDATE and en->nhs is defined. */ struct mpnh *onhs = en->nhs; /* Keep old ones */ if (!po->ecmp || !nhs->iface || (onhs->iface && ipa_zero(onhs->gw))) return; /* Merge old and new */ if (ipa_nonzero(nhs->gw) && ipa_nonzero(onhs->gw)) { merge_nexthops(po, en, par, nhs); return; } /* Fallback to replace old ones */ } DBG(" Adding candidate: rt: %R, id: %R, type: %u\n", en->lsa.rt, en->lsa.id, en->lsa.type); if (en->color == CANDIDATE) { /* We found a shorter path */ rem_node(&en->cn); } en->nhs = nhs; en->dist = dist; en->color = CANDIDATE; en->nhs_reuse = (par->nhs != nhs); prev = NULL; if (EMPTY_LIST(*l)) { add_head(l, &en->cn); } else { WALK_LIST(n, *l) { act = SKIP_BACK(struct top_hash_entry, cn, n); if ((act->dist > dist) || ((act->dist == dist) && (act->lsa.type == LSA_T_RT))) { if (prev == NULL) add_head(l, &en->cn); else insert_node(&en->cn, prev); added = 1; break; } prev = n; } if (!added) { add_tail(l, &en->cn); } } } static inline int ort_changed(ort *nf, rta *nr) { rta *or = nf->old_rta; return !or || (nf->n.metric1 != nf->old_metric1) || (nf->n.metric2 != nf->old_metric2) || (nf->n.tag != nf->old_tag) || (nf->n.rid != nf->old_rid) || (nr->source != or->source) || (nr->dest != or->dest) || (nr->iface != or->iface) || !ipa_equal(nr->gw, or->gw) || !mpnh_same(nr->nexthops, or->nexthops); } static void rt_sync(struct proto_ospf *po) { struct proto *p = &po->proto; struct fib_iterator fit; struct fib *fib = &po->rtf; ort *nf; struct ospf_area *oa; /* 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"); FIB_ITERATE_INIT(&fit, fib); again1: FIB_ITERATE_START(fib, &fit, nftmp) { nf = (ort *) nftmp; /* Sanity check of next-hop addresses, failure should not happen */ if (nf->n.type) { struct mpnh *nh; for (nh = nf->n.nhs; nh; nh = nh->next) if (ipa_nonzero(nh->gw)) { neighbor *ng = neigh_find2(p, &nh->gw, nh->iface, 0); if (!ng || (ng->scope == SCOPE_HOST)) { reset_ri(nf); break; } } } if (po->areano > 1) check_sum_net_lsa(po, nf); /* Remove configured stubnets */ if (!nf->n.nhs) reset_ri(nf); if (nf->n.type) /* Add the route */ { rta a0 = { .proto = p, .source = nf->n.type, .scope = SCOPE_UNIVERSE, .cast = RTC_UNICAST, }; if (nf->n.nhs->next) { a0.dest = RTD_MULTIPATH; a0.nexthops = nf->n.nhs; } else if (ipa_nonzero(nf->n.nhs->gw)) { a0.dest = RTD_ROUTER; a0.iface = nf->n.nhs->iface; a0.gw = nf->n.nhs->gw; } else { a0.dest = RTD_DEVICE; a0.iface = nf->n.nhs->iface; } if (reload || ort_changed(nf, &a0)) { net *ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen); rta *a = rta_lookup(&a0); rte *e = rte_get_temp(a); rta_free(nf->old_rta); nf->old_rta = rta_clone(a); e->u.ospf.metric1 = nf->old_metric1 = nf->n.metric1; e->u.ospf.metric2 = nf->old_metric2 = nf->n.metric2; e->u.ospf.tag = nf->old_tag = nf->n.tag; e->u.ospf.router_id = nf->old_rid = 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); } } else if (nf->old_rta) { /* Remove the route */ rta_free(nf->old_rta); nf->old_rta = NULL; net *ne = net_get(p->table, nf->fn.prefix, nf->fn.pxlen); rte_update(p->table, ne, p, p, NULL); } /* Remove unused rt entry. Entries with fn.x0 == 1 are persistent. */ if (!nf->n.type && !nf->fn.x0) { FIB_ITERATE_PUT(&fit, nftmp); fib_delete(fib, nftmp); goto again1; } } FIB_ITERATE_END(nftmp); WALK_LIST(oa, po->area_list) { /* Cleanup ASBR hash tables */ FIB_ITERATE_INIT(&fit, &oa->rtr); again2: FIB_ITERATE_START(&oa->rtr, &fit, nftmp) { nf = (ort *) nftmp; if (!nf->n.type) { FIB_ITERATE_PUT(&fit, nftmp); fib_delete(&oa->rtr, nftmp); goto again2; } } FIB_ITERATE_END(nftmp); } }