From: dean <dluga93@gmail.com> In networks with both routers that support SADR and routers that don't, there is the possibility of routing loops. draft-ietf-rtgwg-dst-src-routing-04 describes some ways to avoid these loops. One of these ways is to detect that the path for an SADR route passes through a non-SADR router, and replace that route with a blackhole route. To be able to do this, I added a new option flag OPT_SADR (0x40) to indicate SADR capability of a router. This flag will be included in LSAs, and can be used during the shortest path calculation. SADR capability of a node can be read from its LSA. SADR capability of a path can be calculated during the next-hop calculation. If the destination node doesn't support SADR, or if the path to its parent contains non-SADR routers, the path to that destination doesn't support SADR. The SADR capability of the path to a destination is stored in the nexthop structure for that destination. To handle inter-area routes, ABRs clear the OPT_SADR bit when sending inter-area-router-LSAs if the path to the advertised router includes non-SADR routers. Then, during summary LSA processing in the reciever, the next hops for an advertised router will have the SADR capability as indicated in the OPT_SADR flag of the inter-area-router-LSA. Now that SADR capability is indicated by the nexthop, the external LSA processing function (ospf_ext_spf) uses only the SADR capable nexthops, and deletes the others. In rt_sync, I set the route's destination to RTD_BLACKHOLE. --- nest/route.h | 1 + proto/ospf/ospf.c | 6 +- proto/ospf/ospf.h | 2 + proto/ospf/rt.c | 173 ++++++++++++++++++++++++++++++++++++++++++++++---- proto/ospf/topology.c | 8 +++ proto/ospf/topology.h | 6 ++ 6 files changed, 184 insertions(+), 12 deletions(-) diff --git a/nest/route.h b/nest/route.h index b12d208..6a946dd 100644 --- a/nest/route.h +++ b/nest/route.h @@ -367,6 +367,7 @@ struct nexthop { ip_addr gw; /* Next hop */ struct iface *iface; /* Outgoing interface */ struct nexthop *next; + u8 sadr_capability; /* Whether path through this next hop is SADR capable */ byte weight; byte labels_orig; /* Number of labels before hostentry was applied */ byte labels; /* Number of all labels */ diff --git a/proto/ospf/ospf.c b/proto/ospf/ospf.c index fc96d48..9e08e49 100644 --- a/proto/ospf/ospf.c +++ b/proto/ospf/ospf.c @@ -174,7 +174,8 @@ ospf_area_add(struct ospf_proto *p, struct ospf_area_config *ac) if (ospf_is_v2(p)) oa->options = ac->type; else - oa->options = ac->type | OPT_V6 | (p->stub_router ? 0 : OPT_R); + oa->options = ac->type | OPT_V6 | (p->stub_router ? 0 : OPT_R) + | (ospf_is_v3_sadr(p) ? OPT_SADR : 0); ospf_notify_rt_lsa(oa); } @@ -620,6 +621,9 @@ ospf_area_reconfigure(struct ospf_area *oa, struct ospf_area_config *nac) if (ospf_is_v2(p)) oa->options = nac->type; + else if (ospf_is_v3_sadr(p)) + oa->options = nac->type | OPT_V6 | (p->stub_router ? 0 : OPT_R) + | (ospf_is_v3_sadr(p) ? OPT_SADR : 0); else oa->options = nac->type | OPT_V6 | (p->stub_router ? 0 : OPT_R); diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h index 9e69bb3..e1d895c 100644 --- a/proto/ospf/ospf.h +++ b/proto/ospf/ospf.h @@ -458,6 +458,8 @@ struct ospf_neighbor #define OPT_R 0x10 /* OSPFv3, originator is active router */ #define OPT_DC 0x20 /* Related to demand circuits, not used */ +#define OPT_SADR 0x40 /* SADR capability bit */ + /* Router-LSA VEB flags are are stored together with links (OSPFv2) or options (OSPFv3) */ #define OPT_RT_B (0x01 << 24) #define OPT_RT_E (0x02 << 24) diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c index c0559b2..2490687 100644 --- a/proto/ospf/rt.c +++ b/proto/ospf/rt.c @@ -40,6 +40,7 @@ new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, byte weight) nh->gw = gw; nh->iface = iface; nh->weight = weight; + nh->sadr_capability = 0; return nh; } @@ -64,7 +65,12 @@ fix_device_nexthops(struct ospf_proto *p, const struct nexthop *n, ip_addr gw) struct nexthop **nn2 = &root2; if (!p->ecmp) - return new_nexthop(p, gw, n->iface, n->weight); + { + struct nexthop *nh = new_nexthop(p, gw, n->iface, n->weight); + if (ospf_is_v3_sadr(p)) + nh->sadr_capability = n->sadr_capability; + return nh; + } /* This is a bit tricky. We cannot just copy the list and update n->gw, because the list should stay sorted, so we create two lists, one with new @@ -73,6 +79,8 @@ fix_device_nexthops(struct ospf_proto *p, const struct nexthop *n, ip_addr gw) for (; n; n = n->next) { struct nexthop *nn = new_nexthop(p, ipa_zero(n->gw) ? gw : n->gw, n->iface, n->weight); + if (ospf_is_v3_sadr(p)) + nn->sadr_capability = n->sadr_capability; if (ipa_zero(n->gw)) { @@ -731,6 +739,41 @@ link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry return 0; } +/* Returns a copy of abr_nhs but with sadr_capability set to 0 */ +static struct nexthop * +copy_nhs_no_sadr(struct ospf_proto *p, struct nexthop *abr_nhs) +{ + struct nexthop *ret = NULL; + + if (!p->ecmp) + ret = new_nexthop(p, abr_nhs->gw, abr_nhs->iface, + abr_nhs->weight); + else + { + struct nexthop *nf_nh = NULL, *abr_nh = abr_nhs; + do + { + if (!nf_nh) + { + nf_nh = new_nexthop(p, abr_nhs->gw, abr_nhs->iface, + abr_nhs->weight); + ret = nf_nh; + abr_nh = abr_nh->next; + } + else + { + nf_nh->next = new_nexthop(p, abr_nh->gw, abr_nh->iface, + abr_nh->weight); + nf_nh = nf_nh->next; + abr_nh = abr_nh->next; + } + } while (abr_nh); + + nf_nh->next = NULL; + } + + return ret; +} /* RFC 2328 16.2. calculating inter-area routes */ static void @@ -822,6 +865,11 @@ ospf_rt_sum(struct ospf_area *oa) .nhs = abr->n.nhs }; + /* if a router's SADR capability is not set in the summary LSA, the abr + doesn't have an SADR path to that router */ + if (ospf_is_v3_sadr(p) && !(options & OPT_SADR)) + nf.nhs = copy_nhs_no_sadr(p, abr->n.nhs); + if (type == ORT_NET) { if (ospf_is_v3_sadr(p)) { net_addr_sadr_ip6 sadr_net = NET_ADDR_SADR_IP6(net_prefix(&net), net_pxlen(&net), IP6_NONE, 0); @@ -1222,7 +1270,7 @@ ospf_rt_abr1(struct ospf_proto *p) { net_addr_sadr_ip6 sadr_default = NET_ADDR_SADR_IP6(IP6_NONE, 0, IP6_NONE, 0); - default_nf = fib_get(&p->rtf, &sadr_default); + default_nf = fib_get(&p->rtf, (net_addr *)&sadr_default); } else default_nf = fib_get(&p->rtf, &default_net); @@ -1479,6 +1527,28 @@ ospf_fib_route(struct fib *f, ip_addr a, ip_addr sa, int slen) return ospf_fib_route_ip6(f, ipa_to_ip6(a), IP6_MAX_PREFIX_LENGTH); } +static struct nexthop * +copy_sadr_nh(struct ospf_proto *p, struct nexthop *src) +{ + struct nexthop *nh = src; + struct nexthop *dst = NULL; + + if (!p->ecmp && nh->sadr_capability) + { + dst = new_nexthop(p, nh->gw, nh->iface, nh->weight); + dst->sadr_capability = 1; + return dst; + } + + while (nh) + { + if (nh->sadr_capability) + dst = nexthop_merge(dst, new_nexthop(p, nh->gw, nh->iface, nh->weight), 1, 1, p->ecmp, NULL); + nh = nh->next; + } + + return dst; +} /* RFC 2328 16.4. calculating external routes */ static void @@ -1576,7 +1646,13 @@ ospf_ext_spf(struct ospf_proto *p) if (!rt.fbit) { nf2 = nf1; - nfa.nhs = nf1->n.nhs; + + // if this is an EXT SADR lsa, we only keep the nexthops with sadr capability + if (en->lsa_type == LSA_T_EXT_SADR) + nfa.nhs = copy_sadr_nh(p, nf1->n.nhs); + else + nfa.nhs = nf1->n.nhs; + br_metric = nf1->n.metric1; } else @@ -1605,7 +1681,12 @@ ospf_ext_spf(struct ospf_proto *p) if (!nf2->n.nhs) continue; - nfa.nhs = nf2->n.nhs; + // if this is an EXT SADR lsa, we only keep the nexthops with sadr capability + if (en->lsa_type == LSA_T_EXT_SADR) + nfa.nhs = copy_sadr_nh(p, nf2->n.nhs); + else + nfa.nhs = nf2->n.nhs; + br_metric = nf2->n.metric1; /* Replace device nexthops with nexthops to forwarding address from LSA */ @@ -1769,6 +1850,26 @@ inherit_nexthops(struct nexthop *pn) return pn && (ipa_nonzero(pn->gw) || !pn->iface); } +static int +calc_nh_sadr_capability(struct top_hash_entry *par, struct top_hash_entry *en) +{ + int parent_capable = 0; + + struct nexthop *nh = par->nhs; + while (nh) + { + if (nh->sadr_capability) + { + parent_capable = 1; + break; + } + + nh = nh->next; + } + + return ospf_entry_sadr_capable(en) && parent_capable; +} + static struct nexthop * calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry *par, int pos) @@ -1784,7 +1885,25 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en, /* Usually, we inherit parent nexthops */ if (inherit_nexthops(pn)) + { + // turn off sadr capability if the next node doesn't support SADR + if (ospf_is_v3_sadr(p) && !ospf_entry_sadr_capable(en)) + { + if (!p->ecmp) + return pn->sadr_capability ? new_nexthop(p, pn->gw, pn->iface, pn->weight) : pn; + + struct nexthop *nh = nexthop_merge(pn, NULL, 0, 0, p->ecmp, p->nhpool); + while (nh) + { + nh->sadr_capability = 0; + nh = nh->next; + } + + return nh; + } + return pn; + } /* * There are three cases: @@ -1800,7 +1919,12 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en, if (!ifa) return NULL; - return new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight); + struct nexthop *nh = new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight); + + if (ospf_is_v3_sadr(p)) + nh->sadr_capability = calc_nh_sadr_capability(par, en); + + return nh; } /* The second case - ptp or ptmp neighbor */ @@ -1811,13 +1935,19 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en, return NULL; if (ifa->type == OSPF_IT_VLINK) - return new_nexthop(p, IPA_NONE, NULL, 0); + { + struct nexthop *nh = new_nexthop(p, IPA_NONE, NULL, 0); + return nh; + } struct ospf_neighbor *m = find_neigh(ifa, rid); if (!m || (m->state != NEIGHBOR_FULL)) return NULL; - return new_nexthop(p, m->ip, ifa->iface, ifa->ecmp_weight); + struct nexthop *nh = new_nexthop(p, m->ip, ifa->iface, ifa->ecmp_weight); + if (ospf_is_v3_sadr(p)) + nh->sadr_capability = ospf_entry_sadr_capable(en); + return nh; } /* The third case - bcast or nbma neighbor */ @@ -1855,7 +1985,10 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en, if (ip6_zero(llsa->lladdr)) return NULL; - return new_nexthop(p, ipa_from_ip6(llsa->lladdr), pn->iface, pn->weight); + struct nexthop *nh = new_nexthop(p, ipa_from_ip6(llsa->lladdr), pn->iface, pn->weight); + if (ospf_is_v3_sadr(p)) + nh->sadr_capability = calc_nh_sadr_capability(par, en); + return nh; } } @@ -2030,11 +2163,28 @@ again1: } } - /* Remove configured stubnets but keep the entries */ if (nf->n.type && !nf->n.nhs) { - reset_ri(nf); - nf->keep = 1; + if (nf->n.type == RTS_OSPF_EXT2) + { + rta a0 = { + .src = p->p.main_source, + .source = nf->n.type, + .scope = SCOPE_UNIVERSE, + .dest = RTD_BLACKHOLE, + }; + + rta *a = rta_lookup(&a0); + rte *e = rte_get_temp(a); + rte_update(&p->p, nf->fn.addr, e); + + goto blackholed_sadr; + } + else /* Remove configured stubnets but keep the entries */ + { + reset_ri(nf); + nf->keep = 1; + } } if (nf->n.type) /* Add the route */ @@ -2085,6 +2235,7 @@ again1: goto again1; } } +blackholed_sadr: FIB_ITERATE_END; diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c index 3891b40..dcc8d09 100644 --- a/proto/ospf/topology.c +++ b/proto/ospf/topology.c @@ -1056,7 +1056,15 @@ ospf_originate_sum_rt_lsa(struct ospf_proto *p, struct ospf_area *oa, u32 drid, if (ospf_is_v2(p)) prepare_sum2_lsa_body(p, 0, metric); else + { + // unset the sadr capability flag if there's no sadr path to dst + net_addr_ip4 dst_rid = net_from_rid(drid); + ort *dst_rt = fib_find(&oa->rtr, (net_addr *)&dst_rid); + if (dst_rt && !dst_rt->n.nhs->sadr_capability) + options &= ~OPT_SADR; + prepare_sum3_rt_lsa_body(p, drid, metric, options & LSA_OPTIONS_MASK); + } ospf_originate_lsa(p, &lsa); } diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h index d1682c5..1d32f9c 100644 --- a/proto/ospf/topology.h +++ b/proto/ospf/topology.h @@ -201,6 +201,12 @@ static inline struct top_hash_entry * ospf_hash_find_entry(struct top_graph *f, static inline struct top_hash_entry * ospf_hash_get_entry(struct top_graph *f, struct top_hash_entry *en) { return ospf_hash_get(f, en->domain, en->lsa.id, en->lsa.rt, en->lsa_type); } +static inline int ospf_entry_sadr_capable(struct top_hash_entry *en) +{ if (en->lsa_type == LSA_T_NET) return (((struct ospf_lsa_net *)en->lsa_body)->optx & OPT_SADR) ? 1 : 0; + else if (en->lsa_type == LSA_T_RT) return (((struct ospf_lsa_rt *)en->lsa_body)->options & OPT_SADR) ? 1 : 0; + else return 0; +} + struct top_hash_entry * ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr); struct top_hash_entry * ospf_hash_find_rt3_first(struct top_graph *f, u32 domain, u32 rtr); struct top_hash_entry * ospf_hash_find_rt3_next(struct top_hash_entry *e); -- 2.7.4