diff options
Diffstat (limited to 'ospfd')
| -rw-r--r-- | ospfd/ospf_asbr.c | 6 | ||||
| -rw-r--r-- | ospfd/ospf_ase.c | 87 | ||||
| -rw-r--r-- | ospfd/ospf_bfd.c | 6 | ||||
| -rw-r--r-- | ospfd/ospf_dump.c | 30 | ||||
| -rw-r--r-- | ospfd/ospf_dump.h | 4 | ||||
| -rw-r--r-- | ospfd/ospf_ldp_sync.c | 1 | ||||
| -rw-r--r-- | ospfd/ospf_lsa.c | 62 | ||||
| -rw-r--r-- | ospfd/ospf_lsa.h | 6 | ||||
| -rw-r--r-- | ospfd/ospf_memory.c | 2 | ||||
| -rw-r--r-- | ospfd/ospf_memory.h | 2 | ||||
| -rw-r--r-- | ospfd/ospf_packet.c | 10 | ||||
| -rw-r--r-- | ospfd/ospf_ri.c | 7 | ||||
| -rw-r--r-- | ospfd/ospf_route.c | 83 | ||||
| -rw-r--r-- | ospfd/ospf_route.h | 5 | ||||
| -rw-r--r-- | ospfd/ospf_snmp.c | 23 | ||||
| -rw-r--r-- | ospfd/ospf_spf.c | 658 | ||||
| -rw-r--r-- | ospfd/ospf_spf.h | 25 | ||||
| -rw-r--r-- | ospfd/ospf_sr.c | 112 | ||||
| -rw-r--r-- | ospfd/ospf_sr.h | 13 | ||||
| -rw-r--r-- | ospfd/ospf_ti_lfa.c | 1114 | ||||
| -rw-r--r-- | ospfd/ospf_ti_lfa.h | 41 | ||||
| -rw-r--r-- | ospfd/ospf_vty.c | 305 | ||||
| -rw-r--r-- | ospfd/ospf_vty.h | 4 | ||||
| -rw-r--r-- | ospfd/ospf_zebra.c | 141 | ||||
| -rw-r--r-- | ospfd/ospfd.c | 204 | ||||
| -rw-r--r-- | ospfd/ospfd.h | 95 | ||||
| -rw-r--r-- | ospfd/subdir.am | 2 |
27 files changed, 2489 insertions, 559 deletions
diff --git a/ospfd/ospf_asbr.c b/ospfd/ospf_asbr.c index 94fa1b5b44..0b4e5d7762 100644 --- a/ospfd/ospf_asbr.c +++ b/ospfd/ospf_asbr.c @@ -517,7 +517,7 @@ struct ospf_external_aggr_rt *ospf_external_aggr_match(struct ospf *ospf, struct ospf_external_aggr_rt *ag = node->info; zlog_debug( - "%s: Matching aggregator found.prefix:%pI4/%d Aggregator %pI4/%d\n", + "%s: Matching aggregator found.prefix:%pI4/%d Aggregator %pI4/%d", __func__, &p->prefix, p->prefixlen, &ag->p.prefix, ag->p.prefixlen); } @@ -956,7 +956,7 @@ static void ospf_handle_external_aggr_update(struct ospf *ospf) struct route_node *rn = NULL; if (IS_DEBUG_OSPF(lsa, EXTNL_LSA_AGGR)) - zlog_debug("%s: Process modified aggregators.\n", __func__); + zlog_debug("%s: Process modified aggregators.", __func__); for (rn = route_top(ospf->rt_aggr_tbl); rn; rn = route_next(rn)) { struct ospf_external_aggr_rt *aggr; @@ -1047,7 +1047,7 @@ static int ospf_asbr_external_aggr_process(struct thread *thread) operation = ospf->aggr_action; if (IS_DEBUG_OSPF(lsa, EXTNL_LSA_AGGR)) - zlog_debug("%s: operation:%d\n", __func__, operation); + zlog_debug("%s: operation:%d", __func__, operation); switch (operation) { case OSPF_ROUTE_AGGR_ADD: diff --git a/ospfd/ospf_ase.c b/ospfd/ospf_ase.c index e99653f918..51da4a55a7 100644 --- a/ospfd/ospf_ase.c +++ b/ospfd/ospf_ase.c @@ -156,84 +156,6 @@ static int ospf_ase_forward_address_check(struct ospf *ospf, return 1; } -#if 0 -/* Calculate ASBR route. */ -static struct ospf_route * -ospf_ase_calculate_asbr_route (struct ospf *ospf, - struct route_table *rt_network, - struct route_table *rt_router, - struct as_external_lsa *al) -{ - struct prefix_ipv4 asbr; - struct ospf_route *asbr_route; - struct route_node *rn; - - /* Find ASBR route from Router routing table. */ - asbr.family = AF_INET; - asbr.prefix = al->header.adv_router; - asbr.prefixlen = IPV4_MAX_BITLEN; - apply_mask_ipv4 (&asbr); - - asbr_route = ospf_find_asbr_route (ospf, rt_router, &asbr); - - if (asbr_route == NULL) - { - if (IS_DEBUG_OSPF (lsa, LSA)) - zlog_debug ("ospf_ase_calculate(): Route to ASBR %pI4 not found", - &asbr.prefix); - return NULL; - } - - if (!(asbr_route->u.std.flags & ROUTER_LSA_EXTERNAL)) - { - if (IS_DEBUG_OSPF (lsa, LSA)) - zlog_debug ("ospf_ase_calculate(): Originating router is not an ASBR"); - return NULL; - } - - if (al->e[0].fwd_addr.s_addr != INADDR_ANY) - { - if (IS_DEBUG_OSPF (lsa, LSA)) - zlog_debug ("ospf_ase_calculate(): Forwarding address is not 0.0.0.0."); - - if (! ospf_ase_forward_address_check (ospf, al->e[0].fwd_addr)) - { - if (IS_DEBUG_OSPF (lsa, LSA)) - zlog_debug ("ospf_ase_calculate(): Forwarding address is one of our addresses, Ignore."); - return NULL; - } - - if (IS_DEBUG_OSPF (lsa, LSA)) - zlog_debug ("ospf_ase_calculate(): Looking up in the Network Routing Table."); - - /* Looking up the path to the fwd_addr from Network route. */ - asbr.family = AF_INET; - asbr.prefix = al->e[0].fwd_addr; - asbr.prefixlen = IPV4_MAX_BITLEN; - - rn = route_node_match (rt_network, (struct prefix *) &asbr); - - if (rn == NULL) - { - if (IS_DEBUG_OSPF (lsa, LSA)) - zlog_debug ("ospf_ase_calculate(): Couldn't find a route to the forwarding address."); - return NULL; - } - - route_unlock_node (rn); - - if ((asbr_route = rn->info) == NULL) - { - if (IS_DEBUG_OSPF (lsa, LSA)) - zlog_debug ("ospf_ase_calculate(): Somehow OSPF route to ASBR is lost"); - return NULL; - } - } - - return asbr_route; -} -#endif - static struct ospf_route * ospf_ase_calculate_new_route(struct ospf_lsa *lsa, struct ospf_route *asbr_route, uint32_t metric) @@ -748,8 +670,13 @@ void ospf_ase_unregister_external_lsa(struct ospf_lsa *lsa, struct ospf *top) if (rn) { lst = rn->info; - listnode_delete(lst, lsa); - ospf_lsa_unlock(&lsa); /* external_lsas list */ + struct listnode *node = listnode_lookup(lst, lsa); + /* Unlock lsa only if node is present in the list */ + if (node) { + listnode_delete(lst, lsa); + ospf_lsa_unlock(&lsa); /* external_lsas list */ + } + route_unlock_node(rn); } } diff --git a/ospfd/ospf_bfd.c b/ospfd/ospf_bfd.c index 4640720952..a9bc9069d2 100644 --- a/ospfd/ospf_bfd.c +++ b/ospfd/ospf_bfd.c @@ -205,14 +205,14 @@ static int ospf_bfd_interface_dest_update(ZAPI_CALLBACK_ARGS) struct ospf_neighbor *nbr = NULL; struct route_node *node; struct route_node *n_node; - struct prefix p; + struct prefix p, src_p; int status; int old_status; struct bfd_info *bfd_info; struct timeval tv; - ifp = bfd_get_peer_info(zclient->ibuf, &p, NULL, &status, - NULL, vrf_id); + ifp = bfd_get_peer_info(zclient->ibuf, &p, &src_p, &status, NULL, + vrf_id); if ((ifp == NULL) || (p.family != AF_INET)) return 0; diff --git a/ospfd/ospf_dump.c b/ospfd/ospf_dump.c index e15c9c42c7..b98852eeee 100644 --- a/ospfd/ospf_dump.c +++ b/ospfd/ospf_dump.c @@ -56,6 +56,7 @@ unsigned long conf_debug_ospf_nssa = 0; unsigned long conf_debug_ospf_te = 0; unsigned long conf_debug_ospf_ext = 0; unsigned long conf_debug_ospf_sr = 0; +unsigned long conf_debug_ospf_ti_lfa = 0; unsigned long conf_debug_ospf_defaultinfo = 0; unsigned long conf_debug_ospf_ldp_sync = 0; unsigned long conf_debug_ospf_gr = 0; @@ -71,6 +72,7 @@ unsigned long term_debug_ospf_nssa = 0; unsigned long term_debug_ospf_te = 0; unsigned long term_debug_ospf_ext = 0; unsigned long term_debug_ospf_sr = 0; +unsigned long term_debug_ospf_ti_lfa = 0; unsigned long term_debug_ospf_defaultinfo; unsigned long term_debug_ospf_ldp_sync; unsigned long term_debug_ospf_gr = 0; @@ -1470,6 +1472,24 @@ DEFUN (no_debug_ospf_sr, return CMD_SUCCESS; } +DEFUN(debug_ospf_ti_lfa, debug_ospf_ti_lfa_cmd, "debug ospf ti-lfa", + DEBUG_STR OSPF_STR "OSPF-SR TI-LFA information\n") +{ + if (vty->node == CONFIG_NODE) + CONF_DEBUG_ON(ti_lfa, TI_LFA); + TERM_DEBUG_ON(ti_lfa, TI_LFA); + return CMD_SUCCESS; +} + +DEFUN(no_debug_ospf_ti_lfa, no_debug_ospf_ti_lfa_cmd, "no debug ospf ti-lfa", + NO_STR DEBUG_STR OSPF_STR "OSPF-SR TI-LFA information\n") +{ + if (vty->node == CONFIG_NODE) + CONF_DEBUG_OFF(ti_lfa, TI_LFA); + TERM_DEBUG_OFF(ti_lfa, TI_LFA); + return CMD_SUCCESS; +} + DEFUN (debug_ospf_default_info, debug_ospf_default_info_cmd, "debug ospf default-information", @@ -1891,6 +1911,12 @@ static int config_write_debug(struct vty *vty) write = 1; } + /* debug ospf sr ti-lfa */ + if (IS_CONF_DEBUG_OSPF(sr, TI_LFA) == OSPF_DEBUG_TI_LFA) { + vty_out(vty, "debug ospf%s ti-lfa\n", str); + write = 1; + } + /* debug ospf ldp-sync */ if (IS_CONF_DEBUG_OSPF(ldp_sync, LDP_SYNC) == OSPF_DEBUG_LDP_SYNC) { vty_out(vty, "debug ospf%s ldp-sync\n", str); @@ -1920,6 +1946,7 @@ void ospf_debug_init(void) install_element(ENABLE_NODE, &debug_ospf_nssa_cmd); install_element(ENABLE_NODE, &debug_ospf_te_cmd); install_element(ENABLE_NODE, &debug_ospf_sr_cmd); + install_element(ENABLE_NODE, &debug_ospf_ti_lfa_cmd); install_element(ENABLE_NODE, &debug_ospf_default_info_cmd); install_element(ENABLE_NODE, &debug_ospf_ldp_sync_cmd); install_element(ENABLE_NODE, &no_debug_ospf_ism_cmd); @@ -1930,6 +1957,7 @@ void ospf_debug_init(void) install_element(ENABLE_NODE, &no_debug_ospf_nssa_cmd); install_element(ENABLE_NODE, &no_debug_ospf_te_cmd); install_element(ENABLE_NODE, &no_debug_ospf_sr_cmd); + install_element(ENABLE_NODE, &no_debug_ospf_ti_lfa_cmd); install_element(ENABLE_NODE, &no_debug_ospf_default_info_cmd); install_element(ENABLE_NODE, &no_debug_ospf_ldp_sync_cmd); install_element(ENABLE_NODE, &debug_ospf_gr_cmd); @@ -1962,6 +1990,7 @@ void ospf_debug_init(void) install_element(CONFIG_NODE, &debug_ospf_nssa_cmd); install_element(CONFIG_NODE, &debug_ospf_te_cmd); install_element(CONFIG_NODE, &debug_ospf_sr_cmd); + install_element(CONFIG_NODE, &debug_ospf_ti_lfa_cmd); install_element(CONFIG_NODE, &debug_ospf_default_info_cmd); install_element(CONFIG_NODE, &debug_ospf_ldp_sync_cmd); install_element(CONFIG_NODE, &no_debug_ospf_nsm_cmd); @@ -1971,6 +2000,7 @@ void ospf_debug_init(void) install_element(CONFIG_NODE, &no_debug_ospf_nssa_cmd); install_element(CONFIG_NODE, &no_debug_ospf_te_cmd); install_element(CONFIG_NODE, &no_debug_ospf_sr_cmd); + install_element(CONFIG_NODE, &no_debug_ospf_ti_lfa_cmd); install_element(CONFIG_NODE, &no_debug_ospf_default_info_cmd); install_element(CONFIG_NODE, &no_debug_ospf_ldp_sync_cmd); install_element(CONFIG_NODE, &debug_ospf_gr_cmd); diff --git a/ospfd/ospf_dump.h b/ospfd/ospf_dump.h index ea607fef7c..c4c5606663 100644 --- a/ospfd/ospf_dump.h +++ b/ospfd/ospf_dump.h @@ -60,6 +60,7 @@ #define OSPF_DEBUG_TE 0x04 #define OSPF_DEBUG_EXT 0x08 #define OSPF_DEBUG_SR 0x10 +#define OSPF_DEBUG_TI_LFA 0x11 #define OSPF_DEBUG_DEFAULTINFO 0x20 #define OSPF_DEBUG_LDP_SYNC 0x40 @@ -110,6 +111,8 @@ #define IS_DEBUG_OSPF_SR IS_DEBUG_OSPF(sr, SR) +#define IS_DEBUG_OSPF_TI_LFA IS_DEBUG_OSPF(ti_lfa, TI_LFA) + #define IS_DEBUG_OSPF_DEFAULT_INFO IS_DEBUG_OSPF(defaultinfo, DEFAULTINFO) #define IS_DEBUG_OSPF_LDP_SYNC IS_DEBUG_OSPF(ldp_sync, LDP_SYNC) @@ -133,6 +136,7 @@ extern unsigned long term_debug_ospf_nssa; extern unsigned long term_debug_ospf_te; extern unsigned long term_debug_ospf_ext; extern unsigned long term_debug_ospf_sr; +extern unsigned long term_debug_ospf_ti_lfa; extern unsigned long term_debug_ospf_defaultinfo; extern unsigned long term_debug_ospf_ldp_sync; extern unsigned long term_debug_ospf_gr; diff --git a/ospfd/ospf_ldp_sync.c b/ospfd/ospf_ldp_sync.c index b574e2cac8..dbd45635b2 100644 --- a/ospfd/ospf_ldp_sync.c +++ b/ospfd/ospf_ldp_sync.c @@ -107,6 +107,7 @@ void ospf_ldp_sync_state_req_msg(struct interface *ifp) ols_debug("ldp_sync: send state request to LDP for %s", ifp->name); + memset(&request, 0, sizeof(request)); strlcpy(request.name, ifp->name, sizeof(ifp->name)); request.proto = LDP_IGP_SYNC_IF_STATE_REQUEST; request.ifindex = ifp->ifindex; diff --git a/ospfd/ospf_lsa.c b/ospfd/ospf_lsa.c index d5eba74fd4..5a48eebe49 100644 --- a/ospfd/ospf_lsa.c +++ b/ospfd/ospf_lsa.c @@ -337,7 +337,7 @@ void lsa_header_set(struct stream *s, uint8_t options, uint8_t type, /* router-LSA related functions. */ /* Get router-LSA flags. */ -static uint8_t router_lsa_flags(struct ospf_area *area) +uint8_t router_lsa_flags(struct ospf_area *area) { uint8_t flags; @@ -420,9 +420,8 @@ static uint16_t ospf_link_cost(struct ospf_interface *oi) } /* Set a link information. */ -static char link_info_set(struct stream **s, struct in_addr id, - struct in_addr data, uint8_t type, uint8_t tos, - uint16_t cost) +char link_info_set(struct stream **s, struct in_addr id, struct in_addr data, + uint8_t type, uint8_t tos, uint16_t cost) { /* LSA stream is initially allocated to OSPF_MAX_LSA_SIZE, suits * vast majority of cases. Some rare routers with lots of links need @@ -679,7 +678,7 @@ static int router_lsa_link_set(struct stream **s, struct ospf_area *area) } /* Set router-LSA body. */ -static void ospf_router_lsa_body_set(struct stream **s, struct ospf_area *area) +void ospf_router_lsa_body_set(struct stream **s, struct ospf_area *area) { unsigned long putp; uint16_t cnt; @@ -1756,8 +1755,8 @@ static struct ospf_lsa *ospf_lsa_translated_nssa_new(struct ospf *ospf, == NULL) { if (IS_DEBUG_OSPF_NSSA) zlog_debug( - "ospf_nssa_translate_originate(): Could not originate Translated Type-5 for %pI4", - &ei.p.prefix); + "%s: Could not originate Translated Type-5 for %pI4", + __func__, &ei.p.prefix); return NULL; } @@ -1790,24 +1789,22 @@ struct ospf_lsa *ospf_translated_nssa_originate(struct ospf *ospf, if ((new = ospf_lsa_translated_nssa_new(ospf, type7)) == NULL) { if (IS_DEBUG_OSPF_NSSA) zlog_debug( - "ospf_translated_nssa_originate(): Could not translate Type-7, Id %pI4, to Type-5", - &type7->data->id); + "%s: Could not translate Type-7, Id %pI4, to Type-5", + __func__, &type7->data->id); return NULL; } extnew = (struct as_external_lsa *)new->data; if ((new = ospf_lsa_install(ospf, NULL, new)) == NULL) { - flog_warn( - EC_OSPF_LSA_INSTALL_FAILURE, - "ospf_lsa_translated_nssa_originate(): Could not install LSA id %pI4", - &type7->data->id); + flog_warn(EC_OSPF_LSA_INSTALL_FAILURE, + "%s: Could not install LSA id %pI4", __func__, + &type7->data->id); return NULL; } if (IS_DEBUG_OSPF_NSSA) { - zlog_debug( - "ospf_translated_nssa_originate(): translated Type 7, installed:"); + zlog_debug("%s: translated Type 7, installed", __func__); ospf_lsa_header_dump(new->data); zlog_debug(" Network mask: %d", ip_masklen(extnew->mask)); zlog_debug(" Forward addr: %pI4", @@ -2166,12 +2163,6 @@ void ospf_external_lsa_flush(struct ospf *ospf, uint8_t type, /* Sweep LSA from Link State Retransmit List. */ ospf_ls_retransmit_delete_nbr_as(ospf, lsa); -/* There must be no self-originated LSA in rtrs_external. */ -#if 0 - /* Remove External route from Zebra. */ - ospf_zebra_delete ((struct prefix_ipv4 *) p, &nexthop); -#endif - if (!IS_LSA_MAXAGE(lsa)) { /* Unregister LSA from Refresh queue. */ ospf_refresher_unregister_lsa(ospf, lsa); @@ -2443,12 +2434,7 @@ ospf_summary_lsa_install(struct ospf *ospf, struct ospf_lsa *new, int rt_recalc) necessary to re-examine all the AS-external-LSAs. */ -#if 0 - /* This doesn't exist yet... */ - ospf_summary_incremental_update(new); */ -#else /* #if 0 */ ospf_spf_calculate_schedule(ospf, SPF_FLAG_SUMMARY_LSA_INSTALL); -#endif /* #if 0 */ } if (IS_LSA_SELF(new)) @@ -2469,16 +2455,8 @@ static struct ospf_lsa *ospf_summary_asbr_lsa_install(struct ospf *ospf, destination is an AS boundary router, it may also be necessary to re-examine all the AS-external-LSAs. */ -#if 0 - /* These don't exist yet... */ - ospf_summary_incremental_update(new); - /* Isn't this done by the above call? - - RFC 2328 Section 16.5 implies it should be */ - /* ospf_ase_calculate_schedule(); */ -#else /* #if 0 */ ospf_spf_calculate_schedule(ospf, SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL); -#endif /* #if 0 */ } /* register LSA to refresh-list. */ @@ -2667,7 +2645,7 @@ struct ospf_lsa *ospf_lsa_install(struct ospf *ospf, struct ospf_interface *oi, } else { if (IS_DEBUG_OSPF(lsa, LSA_GENERATE)) { zlog_debug( - "ospf_lsa_install() got an lsa with seq 0x80000000 that was not self originated. Ignoring\n"); + "ospf_lsa_install() got an lsa with seq 0x80000000 that was not self originated. Ignoring"); ospf_lsa_header_dump(lsa->data); } return old; @@ -2789,7 +2767,7 @@ int ospf_check_nbr_status(struct ospf *ospf) static int ospf_maxage_lsa_remover(struct thread *thread) { struct ospf *ospf = THREAD_ARG(thread); - struct ospf_lsa *lsa; + struct ospf_lsa *lsa, *old; struct route_node *rn; int reschedule = 0; @@ -2851,6 +2829,18 @@ static int ospf_maxage_lsa_remover(struct thread *thread) /* Remove from lsdb. */ if (lsa->lsdb) { + old = ospf_lsdb_lookup(lsa->lsdb, lsa); + /* The max age LSA here must be the same + * as the LSA in LSDB + */ + if (old != lsa) { + flog_err(EC_OSPF_LSA_MISSING, + "%s: LSA[Type%d:%pI4]: LSA not in LSDB", + __func__, lsa->data->type, + &lsa->data->id); + + continue; + } ospf_discard_from_db(ospf, lsa->lsdb, lsa); ospf_lsdb_delete(lsa->lsdb, lsa); } else { diff --git a/ospfd/ospf_lsa.h b/ospfd/ospf_lsa.h index c5de287948..f2a0d36e7e 100644 --- a/ospfd/ospf_lsa.h +++ b/ospfd/ospf_lsa.h @@ -260,6 +260,8 @@ extern struct lsa_header *ospf_lsa_data_dup(struct lsa_header *); extern void ospf_lsa_data_free(struct lsa_header *); /* Prototype for various LSAs */ +extern void ospf_router_lsa_body_set(struct stream **s, struct ospf_area *area); +extern uint8_t router_lsa_flags(struct ospf_area *area); extern int ospf_router_lsa_update(struct ospf *); extern int ospf_router_lsa_update_area(struct ospf_area *); @@ -333,6 +335,10 @@ extern int is_prefix_default(struct prefix_ipv4 *); extern int metric_type(struct ospf *, uint8_t, unsigned short); extern int metric_value(struct ospf *, uint8_t, unsigned short); +extern char link_info_set(struct stream **s, struct in_addr id, + struct in_addr data, uint8_t type, uint8_t tos, + uint16_t cost); + extern struct in_addr ospf_get_nssa_ip(struct ospf_area *); extern int ospf_translated_nssa_compare(struct ospf_lsa *, struct ospf_lsa *); extern struct ospf_lsa *ospf_translated_nssa_refresh(struct ospf *, diff --git a/ospfd/ospf_memory.c b/ospfd/ospf_memory.c index ae22cec414..f4fb68cbdf 100644 --- a/ospfd/ospf_memory.c +++ b/ospfd/ospf_memory.c @@ -58,3 +58,5 @@ DEFINE_MTYPE(OSPFD, OSPF_EXT_PARAMS, "OSPF Extended parameters") DEFINE_MTYPE(OSPFD, OSPF_SR_PARAMS, "OSPF Segment Routing parameters") DEFINE_MTYPE(OSPFD, OSPF_GR_HELPER, "OSPF Graceful Restart Helper") DEFINE_MTYPE(OSPFD, OSPF_EXTERNAL_RT_AGGR, "OSPF External Route Summarisation") +DEFINE_MTYPE(OSPFD, OSPF_P_SPACE, "OSPF TI-LFA P-Space") +DEFINE_MTYPE(OSPFD, OSPF_Q_SPACE, "OSPF TI-LFA Q-Space") diff --git a/ospfd/ospf_memory.h b/ospfd/ospf_memory.h index 624b1d3306..42bc8d7b77 100644 --- a/ospfd/ospf_memory.h +++ b/ospfd/ospf_memory.h @@ -57,5 +57,7 @@ DECLARE_MTYPE(OSPF_SR_PARAMS) DECLARE_MTYPE(OSPF_EXT_PARAMS) DECLARE_MTYPE(OSPF_GR_HELPER) DECLARE_MTYPE(OSPF_EXTERNAL_RT_AGGR) +DECLARE_MTYPE(OSPF_P_SPACE) +DECLARE_MTYPE(OSPF_Q_SPACE) #endif /* _QUAGGA_OSPF_MEMORY_H */ diff --git a/ospfd/ospf_packet.c b/ospfd/ospf_packet.c index ef39b6c2f6..343e406f28 100644 --- a/ospfd/ospf_packet.c +++ b/ospfd/ospf_packet.c @@ -2987,6 +2987,16 @@ static enum ospf_read_return_enum ospf_read_helper(struct ospf *ospf) } } + if (ospf->vrf_id == VRF_DEFAULT && ospf->vrf_id != ifp->vrf_id) { + /* + * We may have a situation where l3mdev_accept == 1 + * let's just kindly drop the packet and move on. + * ospf really really really does not like when + * we receive the same packet multiple times. + */ + return OSPF_READ_CONTINUE; + } + /* Self-originated packet should be discarded silently. */ if (ospf_if_lookup_by_local_addr(ospf, NULL, iph->ip_src)) { if (IS_DEBUG_OSPF_PACKET(0, RECV)) { diff --git a/ospfd/ospf_ri.c b/ospfd/ospf_ri.c index 3145d16161..4083ea9332 100644 --- a/ospfd/ospf_ri.c +++ b/ospfd/ospf_ri.c @@ -1451,9 +1451,7 @@ static uint16_t show_vty_sr_range(struct vty *vty, struct tlv_header *tlvh) GET_LABEL(ntohl(range->lower.value))); } else { zlog_debug( - " Segment Routing %s Range TLV:\n" - " Range Size = %d\n" - " SID Label = %d\n\n", + " Segment Routing %s Range TLV: Range Size = %d SID Label = %d", ntohs(range->header.type) == RI_SR_TLV_SRGB_LABEL_RANGE ? "Global" : "Local", @@ -1476,8 +1474,7 @@ static uint16_t show_vty_sr_msd(struct vty *vty, struct tlv_header *tlvh) msd->value); } else { zlog_debug( - " Segment Routing MSD TLV:\n" - " Node Maximum Stack Depth = %d\n", + " Segment Routing MSD TLV: Node Maximum Stack Depth = %d", msd->value); } diff --git a/ospfd/ospf_route.c b/ospfd/ospf_route.c index 590122e223..7cfcaf14be 100644 --- a/ospfd/ospf_route.c +++ b/ospfd/ospf_route.c @@ -71,15 +71,31 @@ struct ospf_path *ospf_path_new(void) static struct ospf_path *ospf_path_dup(struct ospf_path *path) { struct ospf_path *new; + int memsize; new = ospf_path_new(); memcpy(new, path, sizeof(struct ospf_path)); + /* optional TI-LFA backup paths */ + if (path->srni.backup_label_stack) { + memsize = sizeof(struct mpls_label_stack) + + (sizeof(mpls_label_t) + * path->srni.backup_label_stack->num_labels); + new->srni.backup_label_stack = + XCALLOC(MTYPE_OSPF_PATH, memsize); + memcpy(new->srni.backup_label_stack, + path->srni.backup_label_stack, memsize); + } + return new; } void ospf_path_free(struct ospf_path *op) { + /* optional TI-LFA backup paths */ + if (op->srni.backup_label_stack) + XFREE(MTYPE_OSPF_PATH, op->srni.backup_label_stack); + XFREE(MTYPE_OSPF_PATH, op); } @@ -140,6 +156,35 @@ static int ospf_route_exist_new_table(struct route_table *rt, return 1; } +static int ospf_route_backup_path_same(struct sr_nexthop_info *srni1, + struct sr_nexthop_info *srni2) +{ + struct mpls_label_stack *ls1, *ls2; + uint8_t label_count; + + ls1 = srni1->backup_label_stack; + ls2 = srni2->backup_label_stack; + + if (!ls1 && !ls2) + return 1; + + if ((ls1 && !ls2) || (!ls1 && ls2)) + return 0; + + if (ls1->num_labels != ls2->num_labels) + return 0; + + for (label_count = 0; label_count < ls1->num_labels; label_count++) { + if (ls1->label[label_count] != ls2->label[label_count]) + return 0; + } + + if (!IPV4_ADDR_SAME(&srni1->backup_nexthop, &srni2->backup_nexthop)) + return 0; + + return 1; +} + /* If a prefix and a nexthop match any route in the routing table, then return 1, otherwise return 0. */ int ospf_route_match_same(struct route_table *rt, struct prefix_ipv4 *prefix, @@ -180,6 +225,11 @@ int ospf_route_match_same(struct route_table *rt, struct prefix_ipv4 *prefix, return 0; if (op->ifindex != newop->ifindex) return 0; + + /* check TI-LFA backup paths */ + if (!ospf_route_backup_path_same(&op->srni, + &newop->srni)) + return 0; } return 1; } else if (prefix_same(&rn->p, (struct prefix *)prefix)) @@ -664,38 +714,6 @@ void ospf_route_table_dump(struct route_table *rt) zlog_debug("========================================"); } -void ospf_route_table_print(struct vty *vty, struct route_table *rt) -{ - struct route_node *rn; - struct ospf_route * or ; - struct listnode *pnode; - struct ospf_path *path; - - vty_out(vty, "========== OSPF routing table ==========\n"); - for (rn = route_top(rt); rn; rn = route_next(rn)) - if ((or = rn->info) != NULL) { - if (or->type == OSPF_DESTINATION_NETWORK) { - vty_out(vty, "N %-18pFX %-15pI4 %s %d\n", - &rn->p, & or->u.std.area_id, - ospf_path_type_str[or->path_type], - or->cost); - for (ALL_LIST_ELEMENTS_RO(or->paths, pnode, - path)) - if (path->nexthop.s_addr != INADDR_ANY) - vty_out(vty, " -> %pI4\n", - &path->nexthop); - else - vty_out(vty, " -> %s\n", - "directly connected"); - } else - vty_out(vty, "R %-18pI4 %-15pI4 %s %d\n", - &rn->p.u.prefix4, & or->u.std.area_id, - ospf_path_type_str[or->path_type], - or->cost); - } - vty_out(vty, "========================================\n"); -} - /* This is 16.4.1 implementation. o Intra-area paths using non-backbone areas are always the most preferred. o The other paths, intra-area backbone paths and inter-area paths, @@ -802,6 +820,7 @@ void ospf_route_copy_nexthops_from_vertex(struct ospf_area *area, || area->spf_dry_run) { path = ospf_path_new(); path->nexthop = nexthop->router; + path->adv_router = v->id; if (oi) { path->ifindex = oi->ifp->ifindex; diff --git a/ospfd/ospf_route.h b/ospfd/ospf_route.h index c3fa5954d5..811581c0d3 100644 --- a/ospfd/ospf_route.h +++ b/ospfd/ospf_route.h @@ -42,6 +42,10 @@ struct sr_nexthop_info { * or NULL if next hop is the destination of the prefix */ struct sr_node *nexthop; + + /* TI-LFA */ + struct mpls_label_stack *backup_label_stack; + struct in_addr backup_nexthop; }; /* OSPF Path. */ @@ -132,7 +136,6 @@ extern void ospf_route_table_free(struct route_table *); extern void ospf_route_install(struct ospf *, struct route_table *); extern void ospf_route_table_dump(struct route_table *); -extern void ospf_route_table_print(struct vty *vty, struct route_table *rt); extern void ospf_intra_add_router(struct route_table *, struct vertex *, struct ospf_area *); diff --git a/ospfd/ospf_snmp.c b/ospfd/ospf_snmp.c index 66dd9c7ca4..3f4ca44b05 100644 --- a/ospfd/ospf_snmp.c +++ b/ospfd/ospf_snmp.c @@ -1236,7 +1236,6 @@ static struct ospf_nbr_nbma *ospfHostLookup(struct variable *v, oid *name, size_t *length, struct in_addr *addr, int exact) { - int len; struct ospf_nbr_nbma *nbr_nbma; struct ospf *ospf; @@ -1258,28 +1257,8 @@ static struct ospf_nbr_nbma *ospfHostLookup(struct variable *v, oid *name, nbr_nbma = ospf_nbr_nbma_lookup(ospf, *addr); return nbr_nbma; - } else { - len = *length - v->namelen; - if (len > 4) - len = 4; - - oid2in_addr(name + v->namelen, len, addr); - - nbr_nbma = - ospf_nbr_nbma_lookup_next(ospf, addr, len == 0 ? 1 : 0); - - if (nbr_nbma == NULL) - return NULL; - - oid_copy_addr(name + v->namelen, addr, IN_ADDR_SIZE); - - /* Set TOS 0. */ - name[v->namelen + IN_ADDR_SIZE] = 0; - - *length = v->namelen + IN_ADDR_SIZE + 1; - - return nbr_nbma; } + return NULL; } diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index 4665f53edb..82acd0829c 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -46,6 +46,7 @@ #include "ospfd/ospf_abr.h" #include "ospfd/ospf_dump.h" #include "ospfd/ospf_sr.h" +#include "ospfd/ospf_ti_lfa.h" #include "ospfd/ospf_errors.h" /* Variables to ensure a SPF scheduled log message is printed only once */ @@ -141,11 +142,16 @@ static void ospf_canonical_nexthops_free(struct vertex *root) ospf_canonical_nexthops_free(child); /* Free child nexthops pointing back to this root vertex */ - for (ALL_LIST_ELEMENTS(child->parents, n2, nn2, vp)) + for (ALL_LIST_ELEMENTS(child->parents, n2, nn2, vp)) { if (vp->parent == root && vp->nexthop) { vertex_nexthop_free(vp->nexthop); vp->nexthop = NULL; + if (vp->local_nexthop) { + vertex_nexthop_free(vp->local_nexthop); + vp->local_nexthop = NULL; + } } + } } } @@ -154,7 +160,8 @@ static void ospf_canonical_nexthops_free(struct vertex *root) * vertex_nexthop, with refcounts. */ static struct vertex_parent *vertex_parent_new(struct vertex *v, int backlink, - struct vertex_nexthop *hop) + struct vertex_nexthop *hop, + struct vertex_nexthop *lhop) { struct vertex_parent *new; @@ -163,6 +170,7 @@ static struct vertex_parent *vertex_parent_new(struct vertex *v, int backlink, new->parent = v; new->backlink = backlink; new->nexthop = hop; + new->local_nexthop = lhop; return new; } @@ -172,7 +180,7 @@ static void vertex_parent_free(void *p) XFREE(MTYPE_OSPF_VERTEX_PARENT, p); } -static int vertex_parent_cmp(void *aa, void *bb) +int vertex_parent_cmp(void *aa, void *bb) { struct vertex_parent *a = aa, *b = bb; return IPV4_ADDR_CMP(&a->nexthop->router, &b->nexthop->router); @@ -284,6 +292,257 @@ static void ospf_vertex_add_parent(struct vertex *v) } } +/* Find a vertex according to its router id */ +struct vertex *ospf_spf_vertex_find(struct in_addr id, struct list *vertex_list) +{ + struct listnode *node; + struct vertex *found; + + for (ALL_LIST_ELEMENTS_RO(vertex_list, node, found)) { + if (found->id.s_addr == id.s_addr) + return found; + } + + return NULL; +} + +/* Find a vertex parent according to its router id */ +struct vertex_parent *ospf_spf_vertex_parent_find(struct in_addr id, + struct vertex *vertex) +{ + struct listnode *node; + struct vertex_parent *found; + + for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, found)) { + if (found->parent->id.s_addr == id.s_addr) + return found; + } + + return NULL; +} + +struct vertex *ospf_spf_vertex_by_nexthop(struct vertex *root, + struct in_addr *nexthop) +{ + struct listnode *node; + struct vertex *child; + struct vertex_parent *vertex_parent; + + for (ALL_LIST_ELEMENTS_RO(root->children, node, child)) { + vertex_parent = ospf_spf_vertex_parent_find(root->id, child); + if (vertex_parent->nexthop->router.s_addr == nexthop->s_addr) + return child; + } + + return NULL; +} + +/* Create a deep copy of a SPF vertex without children and parents */ +static struct vertex *ospf_spf_vertex_copy(struct vertex *vertex) +{ + struct vertex *copy; + + copy = XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex)); + + memcpy(copy, vertex, sizeof(struct vertex)); + copy->parents = list_new(); + copy->parents->del = vertex_parent_free; + copy->parents->cmp = vertex_parent_cmp; + copy->children = list_new(); + + return copy; +} + +/* Create a deep copy of a SPF vertex_parent */ +static struct vertex_parent * +ospf_spf_vertex_parent_copy(struct vertex_parent *vertex_parent) +{ + struct vertex_parent *vertex_parent_copy; + struct vertex_nexthop *nexthop_copy, *local_nexthop_copy; + + vertex_parent_copy = + XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex_parent)); + + nexthop_copy = vertex_nexthop_new(); + local_nexthop_copy = vertex_nexthop_new(); + + memcpy(vertex_parent_copy, vertex_parent, sizeof(struct vertex_parent)); + memcpy(nexthop_copy, vertex_parent->nexthop, + sizeof(struct vertex_nexthop)); + memcpy(local_nexthop_copy, vertex_parent->local_nexthop, + sizeof(struct vertex_nexthop)); + + vertex_parent_copy->nexthop = nexthop_copy; + vertex_parent_copy->local_nexthop = local_nexthop_copy; + + return vertex_parent_copy; +} + +/* Create a deep copy of a SPF tree */ +void ospf_spf_copy(struct vertex *vertex, struct list *vertex_list) +{ + struct listnode *node; + struct vertex *vertex_copy, *child, *child_copy, *parent_copy; + struct vertex_parent *vertex_parent, *vertex_parent_copy; + + /* First check if the node is already in the vertex list */ + vertex_copy = ospf_spf_vertex_find(vertex->id, vertex_list); + if (!vertex_copy) { + vertex_copy = ospf_spf_vertex_copy(vertex); + listnode_add(vertex_list, vertex_copy); + } + + /* Copy all parents, create parent nodes if necessary */ + for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, vertex_parent)) { + parent_copy = ospf_spf_vertex_find(vertex_parent->parent->id, + vertex_list); + if (!parent_copy) { + parent_copy = + ospf_spf_vertex_copy(vertex_parent->parent); + listnode_add(vertex_list, parent_copy); + } + vertex_parent_copy = ospf_spf_vertex_parent_copy(vertex_parent); + vertex_parent_copy->parent = parent_copy; + listnode_add(vertex_copy->parents, vertex_parent_copy); + } + + /* Copy all children, create child nodes if necessary */ + for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child)) { + child_copy = ospf_spf_vertex_find(child->id, vertex_list); + if (!child_copy) { + child_copy = ospf_spf_vertex_copy(child); + listnode_add(vertex_list, child_copy); + } + listnode_add(vertex_copy->children, child_copy); + } + + /* Finally continue copying with child nodes */ + for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child)) + ospf_spf_copy(child, vertex_list); +} + +static void ospf_spf_remove_branch(struct vertex_parent *vertex_parent, + struct vertex *child, + struct list *vertex_list) +{ + struct listnode *node, *nnode, *inner_node, *inner_nnode; + struct vertex *grandchild; + struct vertex_parent *vertex_parent_found; + bool has_more_links = false; + + /* + * First check if there are more nexthops for that parent to that child + */ + for (ALL_LIST_ELEMENTS_RO(child->parents, node, vertex_parent_found)) { + if (vertex_parent_found->parent->id.s_addr + == vertex_parent->parent->id.s_addr + && vertex_parent_found->nexthop->router.s_addr + != vertex_parent->nexthop->router.s_addr) + has_more_links = true; + } + + /* + * No more links from that parent? Then delete the child from its + * children list. + */ + if (!has_more_links) + listnode_delete(vertex_parent->parent->children, child); + + /* + * Delete the vertex_parent from the child parents list, this needs to + * be done anyway. + */ + listnode_delete(child->parents, vertex_parent); + + /* + * Are there actually more parents left? If not, then delete the child! + * This is done by recursively removing the links to the grandchildren, + * such that finally the child can be removed without leaving unused + * partial branches. + */ + if (child->parents->count == 0) { + for (ALL_LIST_ELEMENTS(child->children, node, nnode, + grandchild)) { + for (ALL_LIST_ELEMENTS(grandchild->parents, inner_node, + inner_nnode, + vertex_parent_found)) { + ospf_spf_remove_branch(vertex_parent_found, + grandchild, vertex_list); + } + } + listnode_delete(vertex_list, child); + ospf_vertex_free(child); + } +} + +static int ospf_spf_remove_link(struct vertex *vertex, struct list *vertex_list, + struct router_lsa_link *link) +{ + struct listnode *node, *inner_node; + struct vertex *child; + struct vertex_parent *vertex_parent; + + /* + * Identify the node who shares a subnet (given by the link) with a + * child and remove the branch of this particular child. + */ + for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child)) { + for (ALL_LIST_ELEMENTS_RO(child->parents, inner_node, + vertex_parent)) { + if ((vertex_parent->local_nexthop->router.s_addr + & link->link_data.s_addr) + == (link->link_id.s_addr + & link->link_data.s_addr)) { + ospf_spf_remove_branch(vertex_parent, child, + vertex_list); + return 0; + } + } + } + + /* No link found yet, move on recursively */ + for (ALL_LIST_ELEMENTS_RO(vertex->children, node, child)) { + if (ospf_spf_remove_link(child, vertex_list, link) == 0) + return 0; + } + + /* link was not removed yet */ + return 1; +} + +void ospf_spf_remove_resource(struct vertex *vertex, struct list *vertex_list, + struct protected_resource *resource) +{ + struct listnode *node, *nnode; + struct vertex *found; + struct vertex_parent *vertex_parent; + + switch (resource->type) { + case OSPF_TI_LFA_LINK_PROTECTION: + ospf_spf_remove_link(vertex, vertex_list, resource->link); + break; + case OSPF_TI_LFA_NODE_PROTECTION: + found = ospf_spf_vertex_find(resource->router_id, vertex_list); + if (!found) + break; + + /* + * Remove the node by removing all links from its parents. Note + * that the child is automatically removed here with the last + * link from a parent, hence no explicit removal of the node. + */ + for (ALL_LIST_ELEMENTS(found->parents, node, nnode, + vertex_parent)) + ospf_spf_remove_branch(vertex_parent, found, + vertex_list); + + break; + default: + /* do nothing */ + break; + } +} + static void ospf_spf_init(struct ospf_area *area, struct ospf_lsa *root_lsa, bool is_dry_run, bool is_root_node) { @@ -427,6 +686,7 @@ static void ospf_spf_flush_parents(struct vertex *w) */ static void ospf_spf_add_parent(struct vertex *v, struct vertex *w, struct vertex_nexthop *newhop, + struct vertex_nexthop *newlhop, unsigned int distance) { struct vertex_parent *vp, *wp; @@ -482,7 +742,8 @@ static void ospf_spf_add_parent(struct vertex *v, struct vertex *w, } } - vp = vertex_parent_new(v, ospf_lsa_has_link(w->lsa, v->lsa), newhop); + vp = vertex_parent_new(v, ospf_lsa_has_link(w->lsa, v->lsa), newhop, + newlhop); listnode_add_sort(w->parents, vp); return; @@ -541,7 +802,7 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area, unsigned int distance, int lsa_pos) { struct listnode *node, *nnode; - struct vertex_nexthop *nh; + struct vertex_nexthop *nh, *lnh; struct vertex_parent *vp; unsigned int added = 0; char buf1[BUFSIZ]; @@ -586,17 +847,22 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area, struct ospf_interface *oi = NULL; struct in_addr nexthop = {.s_addr = 0}; - oi = ospf_if_lookup_by_lsa_pos(area, lsa_pos); - if (!oi) { - zlog_debug( - "%s: OI not found in LSA: lsa_pos: %d link_id:%s link_data:%s", - __func__, lsa_pos, - inet_ntop(AF_INET, &l->link_id, - buf1, BUFSIZ), - inet_ntop(AF_INET, - &l->link_data, buf2, - BUFSIZ)); - return 0; + if (area->spf_root_node) { + oi = ospf_if_lookup_by_lsa_pos(area, + lsa_pos); + if (!oi) { + zlog_debug( + "%s: OI not found in LSA: lsa_pos: %d link_id:%s link_data:%s", + __func__, lsa_pos, + inet_ntop(AF_INET, + &l->link_id, + buf1, BUFSIZ), + inet_ntop(AF_INET, + &l->link_data, + buf2, + BUFSIZ)); + return 0; + } } /* @@ -644,7 +910,21 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area, * as described above using a reverse lookup to * figure out the nexthop. */ - if (oi->type == OSPF_IFTYPE_POINTOPOINT) { + + /* + * HACK: we don't know (yet) how to distinguish + * between P2P and P2MP interfaces by just + * looking at LSAs, which is important for + * TI-LFA since you want to do SPF calculations + * from the perspective of other nodes. Since + * TI-LFA is currently not implemented for P2MP + * we just check here if it is enabled and then + * blindly assume that P2P is used. Ultimately + * the interface code needs to be removed + * somehow. + */ + if (area->ospf->ti_lfa_enabled + || (oi && oi->type == OSPF_IFTYPE_POINTOPOINT)) { struct ospf_neighbor *nbr_w = NULL; /* Calculating node is root node, link @@ -673,7 +953,7 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area, } } } - } else if (oi->type + } else if (oi && oi->type == OSPF_IFTYPE_POINTOMULTIPOINT) { struct prefix_ipv4 la; @@ -703,12 +983,22 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area, nh = vertex_nexthop_new(); nh->router = nexthop; nh->lsa_pos = lsa_pos; - ospf_spf_add_parent(v, w, nh, distance); + + /* + * Since v is the root the nexthop and + * local nexthop are the same. + */ + lnh = vertex_nexthop_new(); + memcpy(lnh, nh, + sizeof(struct vertex_nexthop)); + + ospf_spf_add_parent(v, w, nh, lnh, + distance); return 1; } else zlog_info( "%s: could not determine nexthop for link %s", - __func__, oi->ifp->name); + __func__, oi ? oi->ifp->name : ""); } /* end point-to-point link from V to W */ else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK) { /* @@ -733,7 +1023,17 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area, nh = vertex_nexthop_new(); nh->router = vl_data->nexthop.router; nh->lsa_pos = vl_data->nexthop.lsa_pos; - ospf_spf_add_parent(v, w, nh, distance); + + /* + * Since v is the root the nexthop and + * local nexthop are the same. + */ + lnh = vertex_nexthop_new(); + memcpy(lnh, nh, + sizeof(struct vertex_nexthop)); + + ospf_spf_add_parent(v, w, nh, lnh, + distance); return 1; } else zlog_info( @@ -747,7 +1047,15 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area, nh = vertex_nexthop_new(); nh->router.s_addr = 0; /* Nexthop not required */ nh->lsa_pos = lsa_pos; - ospf_spf_add_parent(v, w, nh, distance); + + /* + * Since v is the root the nexthop and + * local nexthop are the same. + */ + lnh = vertex_nexthop_new(); + memcpy(lnh, nh, sizeof(struct vertex_nexthop)); + + ospf_spf_add_parent(v, w, nh, lnh, distance); return 1; } } /* end V is the root */ @@ -780,8 +1088,18 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area, nh = vertex_nexthop_new(); nh->router = l->link_data; nh->lsa_pos = vp->nexthop->lsa_pos; + + /* + * Since v is the root the nexthop and + * local nexthop are the same. + */ + lnh = vertex_nexthop_new(); + memcpy(lnh, nh, + sizeof(struct vertex_nexthop)); + added = 1; - ospf_spf_add_parent(v, w, nh, distance); + ospf_spf_add_parent(v, w, nh, lnh, + distance); } /* * Note lack of return is deliberate. See next @@ -829,12 +1147,154 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area, for (ALL_LIST_ELEMENTS(v->parents, node, nnode, vp)) { added = 1; - ospf_spf_add_parent(v, w, vp->nexthop, distance); + + /* + * The nexthop is inherited, but the local nexthop still needs + * to be created. + */ + if (l) { + lnh = vertex_nexthop_new(); + lnh->router = l->link_data; + lnh->lsa_pos = lsa_pos; + } else { + lnh = NULL; + } + + ospf_spf_add_parent(v, w, vp->nexthop, lnh, distance); } return added; } +static int ospf_spf_is_protected_resource(struct ospf_area *area, + struct router_lsa_link *link, + struct lsa_header *lsa) +{ + uint8_t *p, *lim; + struct router_lsa_link *p_link; + struct router_lsa_link *l = NULL; + struct in_addr router_id; + int link_type; + + if (!area->spf_protected_resource) + return 0; + + link_type = link->m[0].type; + + switch (area->spf_protected_resource->type) { + case OSPF_TI_LFA_LINK_PROTECTION: + p_link = area->spf_protected_resource->link; + if (!p_link) + return 0; + + /* For P2P: check if the link belongs to the same subnet */ + if (link_type == LSA_LINK_TYPE_POINTOPOINT + && (p_link->link_id.s_addr & p_link->link_data.s_addr) + == (link->link_data.s_addr + & p_link->link_data.s_addr)) + return 1; + + /* For stub: check if this the same subnet */ + if (link_type == LSA_LINK_TYPE_STUB + && (p_link->link_id.s_addr == link->link_id.s_addr) + && (p_link->link_data.s_addr == link->link_data.s_addr)) + return 1; + + break; + case OSPF_TI_LFA_NODE_PROTECTION: + router_id = area->spf_protected_resource->router_id; + if (router_id.s_addr == INADDR_ANY) + return 0; + + /* For P2P: check if the link leads to the protected node */ + if (link_type == LSA_LINK_TYPE_POINTOPOINT + && link->link_id.s_addr == router_id.s_addr) + return 1; + + /* The rest is about stub links! */ + if (link_type != LSA_LINK_TYPE_STUB) + return 0; + + /* + * Check if there's a P2P link in the router LSA with the + * corresponding link data in the same subnet. + */ + + p = ((uint8_t *)lsa) + OSPF_LSA_HEADER_SIZE + 4; + lim = ((uint8_t *)lsa) + ntohs(lsa->length); + + while (p < lim) { + l = (struct router_lsa_link *)p; + p += (OSPF_ROUTER_LSA_LINK_SIZE + + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE)); + + /* We only care about P2P with the proper link id */ + if ((l->m[0].type != LSA_LINK_TYPE_POINTOPOINT) + || (l->link_id.s_addr != router_id.s_addr)) + continue; + + /* Link data in the subnet given by the link? */ + if ((link->link_id.s_addr & link->link_data.s_addr) + == (l->link_data.s_addr & link->link_data.s_addr)) + return 1; + } + + break; + case OSPF_TI_LFA_UNDEFINED_PROTECTION: + break; + } + + return 0; +} + +/* + * For TI-LFA we need the reverse SPF for Q spaces. The reverse SPF is created + * by honoring the weight of the reverse 'edge', e.g. the edge from W to V, and + * NOT the weight of the 'edge' from V to W as usual. Hence we need to find the + * corresponding link in the LSA of W and extract the particular weight. + * + * TODO: Only P2P supported by now! + */ +static uint16_t get_reverse_distance(struct vertex *v, + struct router_lsa_link *l, + struct ospf_lsa *w_lsa) +{ + uint8_t *p, *lim; + struct router_lsa_link *w_link; + uint16_t distance = 0; + + assert(w_lsa && w_lsa->data); + + p = ((uint8_t *)w_lsa->data) + OSPF_LSA_HEADER_SIZE + 4; + lim = ((uint8_t *)w_lsa->data) + ntohs(w_lsa->data->length); + + while (p < lim) { + w_link = (struct router_lsa_link *)p; + p += (OSPF_ROUTER_LSA_LINK_SIZE + + (w_link->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE)); + + /* Only care about P2P with link ID equal to V's router id */ + if (w_link->m[0].type == LSA_LINK_TYPE_POINTOPOINT + && w_link->link_id.s_addr == v->id.s_addr) { + distance = ntohs(w_link->m[0].metric); + break; + } + } + + /* + * This might happen if the LSA for W is not complete yet. In this + * case we take the weight of the 'forward' link from V. When the LSA + * for W is completed the reverse SPF is run again anyway. + */ + if (distance == 0) + distance = ntohs(l->m[0].metric); + + if (IS_DEBUG_OSPF_EVENT) + zlog_debug("%s: reversed distance is %u", __func__, distance); + + return distance; +} + /* * RFC2328 16.1 (2). * v is on the SPF tree. Examine the links in v's LSA. Update the list of @@ -850,6 +1310,7 @@ static void ospf_spf_next(struct vertex *v, struct ospf_area *area, struct router_lsa_link *l = NULL; struct in_addr *r; int type = 0, lsa_pos = -1, lsa_pos_next = 0; + uint16_t link_distance; /* * If this is a router-LSA, and bit V of the router-LSA (see Section @@ -892,6 +1353,16 @@ static void ospf_spf_next(struct vertex *v, struct ospf_area *area, continue; /* + * Don't process TI-LFA protected resources. + * + * TODO: Replace this by a proper solution, e.g. remove + * corresponding links from the LSDB and run the SPF + * algo with the stripped-down LSDB. + */ + if (ospf_spf_is_protected_resource(area, l, v->lsa)) + continue; + + /* * (b) Otherwise, W is a transit vertex (router or * transit network). Look up the vertex W's LSA * (router-LSA or network-LSA) in Area A's link state @@ -928,8 +1399,19 @@ static void ospf_spf_next(struct vertex *v, struct ospf_area *area, continue; } + /* + * For TI-LFA we might need the reverse SPF. + * Currently only works with P2P! + */ + if (type == LSA_LINK_TYPE_POINTOPOINT + && area->spf_reversed) + link_distance = + get_reverse_distance(v, l, w_lsa); + else + link_distance = ntohs(l->m[0].metric); + /* step (d) below */ - distance = v->distance + ntohs(l->m[0].metric); + distance = v->distance + link_distance; } else { /* In case of V is Network-LSA. */ r = (struct in_addr *)p; @@ -1069,8 +1551,7 @@ void ospf_spf_print(struct vty *vty, struct vertex *v, int i) struct vertex_parent *parent; if (v->type == OSPF_VERTEX_ROUTER) { - vty_out(vty, "SPF Result: depth %d [R] %pI4\n", i, - &v->lsa->id); + vty_out(vty, "SPF Result: depth %d [R] %pI4\n", i, &v->lsa->id); } else { struct network_lsa *lsa = (struct network_lsa *)v->lsa; vty_out(vty, "SPF Result: depth %d [N] %pI4/%d\n", i, @@ -1078,9 +1559,11 @@ void ospf_spf_print(struct vty *vty, struct vertex *v, int i) } for (ALL_LIST_ELEMENTS_RO(v->parents, nnode, parent)) { - vty_out(vty, " nexthop %pI4 lsa pos %d\n", - &parent->nexthop->router, - parent->nexthop->lsa_pos); + vty_out(vty, + " nexthop %pI4 lsa pos %d -- local nexthop %pI4 lsa pos %d\n", + &parent->nexthop->router, parent->nexthop->lsa_pos, + &parent->local_nexthop->router, + parent->local_nexthop->lsa_pos); } i++; @@ -1128,7 +1611,9 @@ static void ospf_spf_process_stubs(struct ospf_area *area, struct vertex *v, p += (OSPF_ROUTER_LSA_LINK_SIZE + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE)); - if (l->m[0].type == LSA_LINK_TYPE_STUB) + /* Don't process TI-LFA protected resources */ + if (l->m[0].type == LSA_LINK_TYPE_STUB + && !ospf_spf_is_protected_resource(area, l, v->lsa)) ospf_intra_add_stub(rt, l, v, area, parent_is_root, lsa_pos); lsa_pos++; @@ -1190,73 +1675,13 @@ void ospf_spf_cleanup(struct vertex *spf, struct list *vertex_list) * attached the first level of router vertices attached to the * root vertex, see ospf_nexthop_calculation. */ - ospf_canonical_nexthops_free(spf); + if (spf) + ospf_canonical_nexthops_free(spf); /* Free SPF vertices list with deconstructor ospf_vertex_free. */ - list_delete(&vertex_list); -} - -#if 0 -static void -ospf_rtrs_print (struct route_table *rtrs) -{ - struct route_node *rn; - struct list *or_list; - struct listnode *ln; - struct listnode *pnode; - struct ospf_route *or; - struct ospf_path *path; - char buf1[BUFSIZ]; - char buf2[BUFSIZ]; - - if (IS_DEBUG_OSPF_EVENT) - zlog_debug ("ospf_rtrs_print() start"); - - for (rn = route_top (rtrs); rn; rn = route_next (rn)) - if ((or_list = rn->info) != NULL) - for (ALL_LIST_ELEMENTS_RO (or_list, ln, or)) - { - switch (or->path_type) - { - case OSPF_PATH_INTRA_AREA: - if (IS_DEBUG_OSPF_EVENT) - zlog_debug ("%s [%d] area: %s", - inet_ntop (AF_INET, &or->id, buf1, BUFSIZ), - or->cost, inet_ntop (AF_INET, &or->u.std.area_id, - buf2, BUFSIZ)); - break; - case OSPF_PATH_INTER_AREA: - if (IS_DEBUG_OSPF_EVENT) - zlog_debug ("%s IA [%d] area: %s", - inet_ntop (AF_INET, &or->id, buf1, BUFSIZ), - or->cost, inet_ntop (AF_INET, &or->u.std.area_id, - buf2, BUFSIZ)); - break; - default: - break; - } - - for (ALL_LIST_ELEMENTS_RO (or->paths, pnode, path)) - { - if (path->nexthop.s_addr == INADDR_ANY) - { - if (IS_DEBUG_OSPF_EVENT) - zlog_debug (" directly attached to %s\r", - ifindex2ifname (path->ifindex), VRF_DEFAULT); - } - else - { - if (IS_DEBUG_OSPF_EVENT) - zlog_debug (" via %pI4, %s\r", - &path->nexthop, - ifindex2ifname (path->ifindex), VRF_DEFAULT); - } - } - } - - zlog_debug ("ospf_rtrs_print() end"); + if (vertex_list) + list_delete(&vertex_list); } -#endif /* Calculating the shortest-path tree for an area, see RFC2328 16.1. */ void ospf_spf_calculate(struct ospf_area *area, struct ospf_lsa *root_lsa, @@ -1359,19 +1784,27 @@ void ospf_spf_calculate(struct ospf_area *area, struct ospf_lsa *root_lsa, if (IS_DEBUG_OSPF_EVENT) zlog_debug("ospf_spf_calculate: Stop. %zd vertices", mtype_stats_alloc(MTYPE_OSPF_VERTEX)); +} + +void ospf_spf_calculate_area(struct ospf *ospf, struct ospf_area *area, + struct route_table *new_table, + struct route_table *new_rtrs) +{ + ospf_spf_calculate(area, area->router_lsa_self, new_table, new_rtrs, + false, true); - /* If this is a dry run then keep the SPF data in place */ - if (!area->spf_dry_run) - ospf_spf_cleanup(area->spf, area->spf_vertex_list); + if (ospf->ti_lfa_enabled) + ospf_ti_lfa_compute(area, new_table, + ospf->ti_lfa_protection_type); + + ospf_spf_cleanup(area->spf, area->spf_vertex_list); } -int ospf_spf_calculate_areas(struct ospf *ospf, struct route_table *new_table, - struct route_table *new_rtrs, bool is_dry_run, - bool is_root_node) +void ospf_spf_calculate_areas(struct ospf *ospf, struct route_table *new_table, + struct route_table *new_rtrs) { struct ospf_area *area; struct listnode *node, *nnode; - int areas_processed = 0; /* Calculate SPF for each area. */ for (ALL_LIST_ELEMENTS(ospf->areas, node, nnode, area)) { @@ -1380,20 +1813,13 @@ int ospf_spf_calculate_areas(struct ospf *ospf, struct route_table *new_table, if (ospf->backbone && ospf->backbone == area) continue; - ospf_spf_calculate(area, area->router_lsa_self, new_table, - new_rtrs, is_dry_run, is_root_node); - areas_processed++; + ospf_spf_calculate_area(ospf, area, new_table, new_rtrs); } /* SPF for backbone, if required */ - if (ospf->backbone) { - area = ospf->backbone; - ospf_spf_calculate(area, area->router_lsa_self, new_table, - new_rtrs, is_dry_run, is_root_node); - areas_processed++; - } - - return areas_processed; + if (ospf->backbone) + ospf_spf_calculate_area(ospf, ospf->backbone, new_table, + new_rtrs); } /* Worker for SPF calculation scheduler. */ @@ -1402,7 +1828,6 @@ static int ospf_spf_calculate_schedule_worker(struct thread *thread) struct ospf *ospf = THREAD_ARG(thread); struct route_table *new_table, *new_rtrs; struct timeval start_time, spf_start_time; - int areas_processed; unsigned long ia_time, prune_time, rt_time; unsigned long abr_time, total_spf_time, spf_time; char rbuf[32]; /* reason_buf */ @@ -1418,8 +1843,7 @@ static int ospf_spf_calculate_schedule_worker(struct thread *thread) monotime(&spf_start_time); new_table = route_table_init(); /* routing table */ new_rtrs = route_table_init(); /* ABR/ASBR routing table */ - areas_processed = ospf_spf_calculate_areas(ospf, new_table, new_rtrs, - false, true); + ospf_spf_calculate_areas(ospf, new_table, new_rtrs); spf_time = monotime_since(&spf_start_time, NULL); ospf_vl_shut_unapproved(ospf); @@ -1512,7 +1936,7 @@ static int ospf_spf_calculate_schedule_worker(struct thread *thread) zlog_info(" RouteInstall: %ld", rt_time); if (IS_OSPF_ABR(ospf)) zlog_info(" ABR: %ld (%d areas)", - abr_time, areas_processed); + abr_time, ospf->areas->count); zlog_info("Reason(s) for SPF: %s", rbuf); } diff --git a/ospfd/ospf_spf.h b/ospfd/ospf_spf.h index 2dc0f8b886..66555be4b7 100644 --- a/ospfd/ospf_spf.h +++ b/ospfd/ospf_spf.h @@ -47,15 +47,15 @@ struct vertex { struct list *children; /* list of children in SPF tree*/ }; -/* A nexthop taken on the root node to get to this (parent) vertex */ struct vertex_nexthop { struct in_addr router; /* router address to send to */ int lsa_pos; /* LSA position for resolving the interface */ }; struct vertex_parent { - struct vertex_nexthop *nexthop; /* nexthop address for this parent */ - struct vertex *parent; /* parent vertex */ + struct vertex_nexthop *nexthop; /* nexthop taken on the root node */ + struct vertex_nexthop *local_nexthop; /* local nexthop of the parent */ + struct vertex *parent; /* parent vertex */ int backlink; /* index back to parent for router-lsa's */ }; @@ -77,12 +77,25 @@ extern void ospf_spf_calculate(struct ospf_area *area, struct route_table *new_table, struct route_table *new_rtrs, bool is_dry_run, bool is_root_node); -extern int ospf_spf_calculate_areas(struct ospf *ospf, +extern void ospf_spf_calculate_area(struct ospf *ospf, struct ospf_area *area, struct route_table *new_table, - struct route_table *new_rtrs, - bool is_dry_run, bool is_root_node); + struct route_table *new_rtrs); +extern void ospf_spf_calculate_areas(struct ospf *ospf, + struct route_table *new_table, + struct route_table *new_rtrs); extern void ospf_rtrs_free(struct route_table *); extern void ospf_spf_cleanup(struct vertex *spf, struct list *vertex_list); +extern void ospf_spf_copy(struct vertex *vertex, struct list *vertex_list); +extern void ospf_spf_remove_resource(struct vertex *vertex, + struct list *vertex_list, + struct protected_resource *resource); +extern struct vertex *ospf_spf_vertex_find(struct in_addr id, + struct list *vertex_list); +extern struct vertex *ospf_spf_vertex_by_nexthop(struct vertex *root, + struct in_addr *nexthop); +extern struct vertex_parent *ospf_spf_vertex_parent_find(struct in_addr id, + struct vertex *vertex); +extern int vertex_parent_cmp(void *aa, void *bb); extern void ospf_spf_print(struct vty *vty, struct vertex *v, int i); diff --git a/ospfd/ospf_sr.c b/ospfd/ospf_sr.c index e2218957d2..7b2d794214 100644 --- a/ospfd/ospf_sr.c +++ b/ospfd/ospf_sr.c @@ -159,6 +159,16 @@ static struct sr_node *sr_node_new(struct in_addr *rid) return new; } +/* Supposed to be used for testing */ +struct sr_node *ospf_sr_node_create(struct in_addr *rid) +{ + struct sr_node *srn; + + srn = hash_get(OspfSR.neighbors, (void *)rid, (void *)sr_node_new); + + return srn; +} + /* Delete Segment Routing node */ static void sr_node_del(struct sr_node *srn) { @@ -588,11 +598,6 @@ int ospf_sr_init(void) if (OspfSR.neighbors == NULL) return rc; - /* Initialize Route Table for prefix */ - OspfSR.prefix = route_table_init(); - if (OspfSR.prefix == NULL) - return rc; - /* Register Segment Routing VTY command */ ospf_sr_register_vty(); @@ -616,9 +621,6 @@ void ospf_sr_term(void) if (OspfSR.neighbors) hash_free(OspfSR.neighbors); - /* Clear Prefix Table */ - if (OspfSR.prefix) - route_table_finish(OspfSR.prefix); } /* @@ -653,6 +655,56 @@ static mpls_label_t index2label(uint32_t index, struct sr_block srgb) return label; } +/* Get the prefix sid for a specific router id */ +mpls_label_t ospf_sr_get_prefix_sid_by_id(struct in_addr *id) +{ + struct sr_node *srn; + struct sr_prefix *srp; + mpls_label_t label; + + srn = (struct sr_node *)hash_lookup(OspfSR.neighbors, id); + + if (srn) { + /* + * TODO: Here we assume that the SRGBs are the same, + * and that the node's prefix SID is at the head of + * the list, probably needs tweaking. + */ + srp = listnode_head(srn->ext_prefix); + label = index2label(srp->sid, srn->srgb); + } else { + label = MPLS_INVALID_LABEL; + } + + return label; +} + +/* Get the adjacency sid for a specific 'root' id and 'neighbor' id */ +mpls_label_t ospf_sr_get_adj_sid_by_id(struct in_addr *root_id, + struct in_addr *neighbor_id) +{ + struct sr_node *srn; + struct sr_link *srl; + mpls_label_t label; + struct listnode *node; + + srn = (struct sr_node *)hash_lookup(OspfSR.neighbors, root_id); + + label = MPLS_INVALID_LABEL; + + if (srn) { + for (ALL_LIST_ELEMENTS_RO(srn->ext_link, node, srl)) { + if (srl->type == ADJ_SID + && srl->remote_id.s_addr == neighbor_id->s_addr) { + label = srl->sid[0]; + break; + } + } + } + + return label; +} + /* Get neighbor full structure from address */ static struct ospf_neighbor *get_neighbor_by_addr(struct ospf *top, struct in_addr addr) @@ -853,8 +905,13 @@ static int compute_prefix_nhlfe(struct sr_prefix *srp) * be received before corresponding Router Information LSA */ if (srnext == NULL || srnext->srgb.lower_bound == 0 - || srnext->srgb.range_size == 0) + || srnext->srgb.range_size == 0) { + osr_debug( + " |- SR-Node %pI4 not ready. Stop process", + &srnext->adv_router); + path->srni.label_out = MPLS_INVALID_LABEL; continue; + } osr_debug(" |- Found SRGB %u/%u for next hop SR-Node %pI4", srnext->srgb.range_size, srnext->srgb.lower_bound, @@ -1213,7 +1270,7 @@ static void update_in_nhlfe(struct hash_bucket *bucket, void *args) /* * When SRGB has changed, update NHLFE Output Label for all Extended Prefix - * with SID index which use the given SR-Node as nexthop though hash_iterate() + * with SID index which use the given SR-Node as nexthop through hash_iterate() */ static void update_out_nhlfe(struct hash_bucket *bucket, void *args) { @@ -1223,21 +1280,29 @@ static void update_out_nhlfe(struct hash_bucket *bucket, void *args) struct sr_prefix *srp; struct ospf_path *path; + /* Skip Self SR-Node */ + if (srn == OspfSR.self) + return; + + osr_debug("SR (%s): Update Out NHLFE for neighbor SR-Node %pI4", + __func__, &srn->adv_router); + for (ALL_LIST_ELEMENTS_RO(srn->ext_prefix, node, srp)) { - /* Process only SID Index with valid route */ + /* Skip Prefix that has not yet a valid route */ if (srp->route == NULL) continue; for (ALL_LIST_ELEMENTS_RO(srp->route->paths, pnode, path)) { - /* Process only SID Index for next hop without PHP */ - if ((path->srni.nexthop == srp->srn) - && (!CHECK_FLAG(srp->flags, - EXT_SUBTLV_PREFIX_SID_NPFLG))) + /* Skip path that has not next SR-Node as nexthop */ + if (path->srni.nexthop != srnext) continue; - path->srni.label_out = - index2label(srp->sid, srnext->srgb); - ospf_zebra_update_prefix_sid(srp); + + /* Compute new Output Label */ + path->srni.label_out = sr_prefix_out_label(srp, srnext); } + + /* Finally update MPLS table */ + ospf_zebra_update_prefix_sid(srp); } } @@ -1378,11 +1443,6 @@ void ospf_sr_ri_lsa_update(struct ospf_lsa *lsa) srn->srlb.lower_bound = GET_LABEL(ntohl(ri_srlb->lower.value)); } - osr_debug(" |- Update SR-Node[%pI4], SRGB[%u/%u], SRLB[%u/%u], Algo[%u], MSD[%u]", - &srn->adv_router, srn->srgb.lower_bound, srn->srgb.range_size, - srn->srlb.lower_bound, srn->srlb.range_size, srn->algo[0], - srn->msd); - /* Check if SRGB has changed */ if ((srn->srgb.range_size == srgb.range_size) && (srn->srgb.lower_bound == srgb.lower_bound)) @@ -1392,6 +1452,11 @@ void ospf_sr_ri_lsa_update(struct ospf_lsa *lsa) srn->srgb.range_size = srgb.range_size; srn->srgb.lower_bound = srgb.lower_bound; + osr_debug(" |- Update SR-Node[%pI4], SRGB[%u/%u], SRLB[%u/%u], Algo[%u], MSD[%u]", + &srn->adv_router, srn->srgb.lower_bound, srn->srgb.range_size, + srn->srlb.lower_bound, srn->srlb.range_size, srn->algo[0], + srn->msd); + /* ... and NHLFE if it is a neighbor SR node */ if (srn->neighbor == OspfSR.self) hash_iterate(OspfSR.neighbors, update_out_nhlfe, srn); @@ -1562,6 +1627,7 @@ void ospf_sr_ext_itf_add(struct ext_itf *exti) srl->itf_addr = exti->link.link_data; srl->instance = SET_OPAQUE_LSID(OPAQUE_TYPE_EXTENDED_LINK_LSA, exti->instance); + srl->remote_id = exti->link.link_id; switch (exti->stype) { case ADJ_SID: srl->type = ADJ_SID; diff --git a/ospfd/ospf_sr.h b/ospfd/ospf_sr.h index 222675944d..ce13457484 100644 --- a/ospfd/ospf_sr.h +++ b/ospfd/ospf_sr.h @@ -233,9 +233,6 @@ struct ospf_sr_db { /* List of neighbour SR nodes */ struct hash *neighbors; - /* List of SR prefix */ - struct route_table *prefix; - /* Local SR info announced in Router Info LSA */ /* Algorithms supported by the node */ @@ -290,6 +287,9 @@ struct sr_link { /* 24-bit Opaque-ID field value according to RFC 7684 specification */ uint32_t instance; + /* Addressed (remote) router id */ + struct in_addr remote_id; + /* Interface address */ struct in_addr itf_addr; @@ -361,4 +361,11 @@ extern void ospf_sr_update_local_prefix(struct interface *ifp, struct prefix *p); /* Segment Routing re-routing function */ extern void ospf_sr_update_task(struct ospf *ospf); + +/* Support for TI-LFA */ +extern mpls_label_t ospf_sr_get_prefix_sid_by_id(struct in_addr *id); +extern mpls_label_t ospf_sr_get_adj_sid_by_id(struct in_addr *root_id, + struct in_addr *neighbor_id); +extern struct sr_node *ospf_sr_node_create(struct in_addr *rid); + #endif /* _FRR_OSPF_SR_H */ diff --git a/ospfd/ospf_ti_lfa.c b/ospfd/ospf_ti_lfa.c new file mode 100644 index 0000000000..4a0186bfb9 --- /dev/null +++ b/ospfd/ospf_ti_lfa.c @@ -0,0 +1,1114 @@ +/* + * OSPF TI-LFA + * Copyright (C) 2020 NetDEF, Inc. + * Sascha Kattelmann + * + * This file is part of FRR. + * + * FRR is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; either version 2, or (at your option) any + * later version. + * + * FRR is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include <zebra.h> + +#include "prefix.h" +#include "table.h" +#include "printfrr.h" + +#include "ospfd/ospfd.h" +#include "ospfd/ospf_asbr.h" +#include "ospfd/ospf_lsa.h" +#include "ospfd/ospf_spf.h" +#include "ospfd/ospf_sr.h" +#include "ospfd/ospf_route.h" +#include "ospfd/ospf_ti_lfa.h" +#include "ospfd/ospf_dump.h" + + +DECLARE_RBTREE_UNIQ(p_spaces, struct p_space, p_spaces_item, + p_spaces_compare_func) +DECLARE_RBTREE_UNIQ(q_spaces, struct q_space, q_spaces_item, + q_spaces_compare_func) + +static void +ospf_ti_lfa_generate_p_space(struct ospf_area *area, struct vertex *child, + struct protected_resource *protected_resource, + bool recursive, struct list *pc_path); + +void ospf_print_protected_resource( + struct protected_resource *protected_resource, char *buf) +{ + struct router_lsa_link *link; + + switch (protected_resource->type) { + case OSPF_TI_LFA_LINK_PROTECTION: + link = protected_resource->link; + snprintfrr(buf, PROTECTED_RESOURCE_STRLEN, + "protected link: %pI4 %pI4", &link->link_id, + &link->link_data); + break; + case OSPF_TI_LFA_NODE_PROTECTION: + snprintfrr(buf, PROTECTED_RESOURCE_STRLEN, + "protected node: %pI4", + &protected_resource->router_id); + break; + case OSPF_TI_LFA_UNDEFINED_PROTECTION: + snprintfrr(buf, PROTECTED_RESOURCE_STRLEN, + "undefined protected resource"); + break; + } +} + +static enum ospf_ti_lfa_p_q_space_adjacency +ospf_ti_lfa_find_p_node(struct vertex *pc_node, struct p_space *p_space, + struct q_space *q_space) +{ + struct listnode *curr_node; + struct vertex *p_node = NULL, *pc_node_parent, *p_node_pc_parent; + struct vertex_parent *pc_vertex_parent; + + curr_node = listnode_lookup(q_space->pc_path, pc_node); + pc_node_parent = listgetdata(curr_node->next); + + q_space->p_node_info->type = OSPF_TI_LFA_UNDEFINED_NODE; + + p_node = ospf_spf_vertex_find(pc_node_parent->id, p_space->vertex_list); + + if (p_node) { + q_space->p_node_info->node = p_node; + q_space->p_node_info->type = OSPF_TI_LFA_P_NODE; + + if (curr_node->next->next) { + p_node_pc_parent = listgetdata(curr_node->next->next); + pc_vertex_parent = ospf_spf_vertex_parent_find( + p_node_pc_parent->id, pc_node_parent); + q_space->p_node_info->nexthop = + pc_vertex_parent->nexthop->router; + } else { + /* + * It can happen that the P node is the root node itself + * (hence there can be no parents). In this case we + * don't need to set a nexthop. + */ + q_space->p_node_info->nexthop.s_addr = INADDR_ANY; + } + + return OSPF_TI_LFA_P_Q_SPACE_ADJACENT; + } + + ospf_ti_lfa_find_p_node(pc_node_parent, p_space, q_space); + return OSPF_TI_LFA_P_Q_SPACE_NON_ADJACENT; +} + +static void ospf_ti_lfa_find_q_node(struct vertex *pc_node, + struct p_space *p_space, + struct q_space *q_space) +{ + struct listnode *curr_node, *next_node; + struct vertex *p_node, *q_node, *q_space_parent = NULL, *pc_node_parent; + struct vertex_parent *pc_vertex_parent; + + curr_node = listnode_lookup(q_space->pc_path, pc_node); + next_node = curr_node->next; + pc_node_parent = listgetdata(next_node); + pc_vertex_parent = + ospf_spf_vertex_parent_find(pc_node_parent->id, pc_node); + + p_node = ospf_spf_vertex_find(pc_node->id, p_space->vertex_list); + q_node = ospf_spf_vertex_find(pc_node->id, q_space->vertex_list); + + /* The Q node is always present. */ + assert(q_node); + + q_space->q_node_info->type = OSPF_TI_LFA_UNDEFINED_NODE; + + if (p_node && q_node) { + q_space->q_node_info->node = pc_node; + q_space->q_node_info->type = OSPF_TI_LFA_PQ_NODE; + q_space->q_node_info->nexthop = + pc_vertex_parent->nexthop->router; + return; + } + + /* + * Note that the Q space has the 'reverse' direction of the PC + * SPF. Hence compare PC SPF parent to Q space children. + */ + q_space_parent = + ospf_spf_vertex_find(pc_node_parent->id, q_node->children); + + /* + * If the Q space parent doesn't exist we 'hit' the border to the P + * space and hence got our Q node. + */ + if (!q_space_parent) { + q_space->q_node_info->node = pc_node; + q_space->q_node_info->type = OSPF_TI_LFA_Q_NODE; + q_space->q_node_info->nexthop = + pc_vertex_parent->nexthop->router; + return; + } + + return ospf_ti_lfa_find_q_node(pc_node_parent, p_space, q_space); +} + +static void ospf_ti_lfa_append_label_stack(struct mpls_label_stack *label_stack, + mpls_label_t labels[], + uint32_t num_labels) +{ + int i, offset, limit; + + limit = label_stack->num_labels + num_labels; + offset = label_stack->num_labels; + + for (i = label_stack->num_labels; i < limit; i++) { + label_stack->label[i] = labels[i - offset]; + label_stack->num_labels++; + } +} + + +static struct mpls_label_stack * +ospf_ti_lfa_create_label_stack(mpls_label_t labels[], uint32_t num_labels) +{ + struct mpls_label_stack *label_stack; + uint32_t i; + + /* Sanity check */ + for (i = 0; i < num_labels; i++) { + if (labels[i] == MPLS_INVALID_LABEL) + return NULL; + } + + label_stack = XCALLOC(MTYPE_OSPF_Q_SPACE, + sizeof(struct mpls_label_stack) + + MPLS_MAX_LABELS * sizeof(mpls_label_t)); + label_stack->num_labels = num_labels; + + for (i = 0; i < num_labels; i++) + label_stack->label[i] = labels[i]; + + return label_stack; +} + +static struct list * +ospf_ti_lfa_map_path_to_pc_vertices(struct list *path, + struct list *pc_vertex_list) +{ + struct listnode *node; + struct vertex *vertex, *pc_vertex; + struct list *pc_path; + + pc_path = list_new(); + + for (ALL_LIST_ELEMENTS_RO(path, node, vertex)) { + pc_vertex = ospf_spf_vertex_find(vertex->id, pc_vertex_list); + listnode_add(pc_path, pc_vertex); + } + + return pc_path; +} + +static struct list *ospf_ti_lfa_cut_out_pc_path(struct list *pc_vertex_list, + struct list *pc_path, + struct vertex *p_node, + struct vertex *q_node) +{ + struct list *inner_pc_path; + struct vertex *current_vertex; + struct listnode *current_listnode; + + inner_pc_path = list_new(); + current_vertex = ospf_spf_vertex_find(q_node->id, pc_vertex_list); + current_listnode = listnode_lookup(pc_path, current_vertex); + + /* Note that the post-convergence paths are reversed. */ + for (;;) { + current_vertex = listgetdata(current_listnode); + listnode_add(inner_pc_path, current_vertex); + + if (current_vertex->id.s_addr == p_node->id.s_addr) + break; + + current_listnode = current_listnode->next; + } + + return inner_pc_path; +} + +static void ospf_ti_lfa_generate_inner_label_stack( + struct ospf_area *area, struct p_space *p_space, + struct q_space *q_space, + struct ospf_ti_lfa_inner_backup_path_info *inner_backup_path_info) +{ + struct route_table *new_table, *new_rtrs; + struct vertex *q_node; + struct vertex *start_vertex, *end_vertex; + struct vertex_parent *vertex_parent; + struct listnode *pc_p_node, *pc_q_node; + struct vertex *spf_orig; + struct list *vertex_list_orig; + struct p_spaces_head *p_spaces_orig; + struct p_space *inner_p_space; + struct q_space *inner_q_space; + struct ospf_ti_lfa_node_info *p_node_info, *q_node_info; + struct protected_resource *protected_resource; + struct list *inner_pc_path; + mpls_label_t start_label, end_label; + + p_node_info = q_space->p_node_info; + q_node_info = q_space->q_node_info; + protected_resource = p_space->protected_resource; + + start_vertex = p_node_info->node; + end_vertex = q_node_info->node; + + /* + * It can happen that the P node and/or the Q node are the root or + * the destination, therefore we need to force one step forward (resp. + * backward) using an Adjacency-SID. + */ + start_label = MPLS_INVALID_LABEL; + end_label = MPLS_INVALID_LABEL; + if (p_node_info->node->id.s_addr == p_space->root->id.s_addr) { + pc_p_node = listnode_lookup(q_space->pc_path, p_space->pc_spf); + start_vertex = listgetdata(pc_p_node->prev); + start_label = ospf_sr_get_adj_sid_by_id(&p_node_info->node->id, + &start_vertex->id); + } + if (q_node_info->node->id.s_addr == q_space->root->id.s_addr) { + pc_q_node = listnode_lookup(q_space->pc_path, + listnode_head(q_space->pc_path)); + end_vertex = listgetdata(pc_q_node->next); + end_label = ospf_sr_get_adj_sid_by_id(&end_vertex->id, + &q_node_info->node->id); + } + + /* Corner case: inner path is just one node */ + if (start_vertex->id.s_addr == end_vertex->id.s_addr) { + inner_backup_path_info->label_stack = + ospf_ti_lfa_create_label_stack(&start_label, 1); + inner_backup_path_info->q_node_info.node = end_vertex; + inner_backup_path_info->q_node_info.type = OSPF_TI_LFA_PQ_NODE; + inner_backup_path_info->p_node_info.type = + OSPF_TI_LFA_UNDEFINED_NODE; + vertex_parent = ospf_spf_vertex_parent_find(p_space->root->id, + end_vertex); + inner_backup_path_info->p_node_info.nexthop = + vertex_parent->nexthop->router; + return; + } + + inner_pc_path = ospf_ti_lfa_cut_out_pc_path(p_space->pc_vertex_list, + q_space->pc_path, + start_vertex, end_vertex); + + new_table = route_table_init(); + new_rtrs = route_table_init(); + + /* Copy the current state ... */ + spf_orig = area->spf; + vertex_list_orig = area->spf_vertex_list; + p_spaces_orig = area->p_spaces; + + area->p_spaces = + XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_spaces_head)); + + /* dry run true, root node false */ + ospf_spf_calculate(area, start_vertex->lsa_p, new_table, new_rtrs, true, + false); + + q_node = ospf_spf_vertex_find(end_vertex->id, area->spf_vertex_list); + + ospf_ti_lfa_generate_p_space(area, q_node, protected_resource, false, + inner_pc_path); + + /* There's just one P and Q space */ + inner_p_space = p_spaces_pop(area->p_spaces); + inner_q_space = q_spaces_pop(inner_p_space->q_spaces); + + /* Copy over inner backup path information from the inner q_space */ + + /* In case the outer P node is also the root of the P space */ + if (start_label != MPLS_INVALID_LABEL) { + inner_backup_path_info->label_stack = + ospf_ti_lfa_create_label_stack(&start_label, 1); + ospf_ti_lfa_append_label_stack( + inner_backup_path_info->label_stack, + inner_q_space->label_stack->label, + inner_q_space->label_stack->num_labels); + inner_backup_path_info->p_node_info.node = start_vertex; + inner_backup_path_info->p_node_info.type = OSPF_TI_LFA_P_NODE; + vertex_parent = ospf_spf_vertex_parent_find(p_space->root->id, + start_vertex); + inner_backup_path_info->p_node_info.nexthop = + vertex_parent->nexthop->router; + } else { + memcpy(inner_backup_path_info->label_stack, + inner_q_space->label_stack, + sizeof(struct mpls_label_stack) + + sizeof(mpls_label_t) + * inner_q_space->label_stack + ->num_labels); + memcpy(&inner_backup_path_info->p_node_info, + inner_q_space->p_node_info, + sizeof(struct ospf_ti_lfa_node_info)); + } + + /* In case the outer Q node is also the root of the Q space */ + if (end_label != MPLS_INVALID_LABEL) { + inner_backup_path_info->q_node_info.node = end_vertex; + inner_backup_path_info->q_node_info.type = OSPF_TI_LFA_Q_NODE; + } else { + memcpy(&inner_backup_path_info->q_node_info, + inner_q_space->q_node_info, + sizeof(struct ospf_ti_lfa_node_info)); + } + + /* Cleanup */ + ospf_ti_lfa_free_p_spaces(area); + ospf_spf_cleanup(area->spf, area->spf_vertex_list); + + /* ... and copy the current state back. */ + area->spf = spf_orig; + area->spf_vertex_list = vertex_list_orig; + area->p_spaces = p_spaces_orig; +} + +static void ospf_ti_lfa_generate_label_stack(struct ospf_area *area, + struct p_space *p_space, + struct q_space *q_space) +{ + enum ospf_ti_lfa_p_q_space_adjacency adjacency_result; + mpls_label_t labels[MPLS_MAX_LABELS]; + struct vertex *pc_node; + struct ospf_ti_lfa_inner_backup_path_info inner_backup_path_info; + + if (IS_DEBUG_OSPF_TI_LFA) + zlog_debug( + "%s: Generating Label stack for src %pI4 and dest %pI4.", + __func__, &p_space->root->id, &q_space->root->id); + + pc_node = listnode_head(q_space->pc_path); + + if (!pc_node) { + if (IS_DEBUG_OSPF_TI_LFA) + zlog_debug( + "%s: There seems to be no post convergence path (yet).", + __func__); + return; + } + + ospf_ti_lfa_find_q_node(pc_node, p_space, q_space); + if (q_space->q_node_info->type == OSPF_TI_LFA_UNDEFINED_NODE) { + if (IS_DEBUG_OSPF_TI_LFA) + zlog_debug("%s: Q node not found!", __func__); + return; + } + + /* Found a PQ node? Then we are done here. */ + if (q_space->q_node_info->type == OSPF_TI_LFA_PQ_NODE) { + /* + * If the PQ node is a child of the root, then we can use an + * adjacency SID instead of a prefix SID for the backup path. + */ + if (ospf_spf_vertex_parent_find(p_space->root->id, + q_space->q_node_info->node)) + labels[0] = ospf_sr_get_adj_sid_by_id( + &p_space->root->id, + &q_space->q_node_info->node->id); + else + labels[0] = ospf_sr_get_prefix_sid_by_id( + &q_space->q_node_info->node->id); + + q_space->label_stack = + ospf_ti_lfa_create_label_stack(labels, 1); + q_space->nexthop = q_space->q_node_info->nexthop; + + return; + } + + /* Otherwise find a (hopefully adjacent) P node. */ + pc_node = ospf_spf_vertex_find(q_space->q_node_info->node->id, + p_space->pc_vertex_list); + adjacency_result = ospf_ti_lfa_find_p_node(pc_node, p_space, q_space); + + if (q_space->p_node_info->type == OSPF_TI_LFA_UNDEFINED_NODE) { + if (IS_DEBUG_OSPF_TI_LFA) + zlog_debug("%s: P node not found!", __func__); + return; + } + + /* + * This should be the regular case: P and Q space are adjacent or even + * overlapping. This is guaranteed for link protection when used with + * symmetric weights. + */ + if (adjacency_result == OSPF_TI_LFA_P_Q_SPACE_ADJACENT) { + /* + * It can happen that the P node is the root itself, therefore + * we don't need a label for it. So just one adjacency SID for + * the Q node. + */ + if (q_space->p_node_info->node->id.s_addr + == p_space->root->id.s_addr) { + labels[0] = ospf_sr_get_adj_sid_by_id( + &p_space->root->id, + &q_space->q_node_info->node->id); + q_space->label_stack = + ospf_ti_lfa_create_label_stack(labels, 1); + q_space->nexthop = q_space->q_node_info->nexthop; + return; + } + + /* + * Otherwise we have a P and also a Q node (which are adjacent). + * + * It can happen that the P node is a child of the root, + * therefore we might just need the adjacency SID for the P node + * instead of the prefix SID. For the Q node always take the + * adjacency SID. + */ + if (ospf_spf_vertex_parent_find(p_space->root->id, + q_space->p_node_info->node)) + labels[0] = ospf_sr_get_adj_sid_by_id( + &p_space->root->id, + &q_space->p_node_info->node->id); + else + labels[0] = ospf_sr_get_prefix_sid_by_id( + &q_space->p_node_info->node->id); + + labels[1] = ospf_sr_get_adj_sid_by_id( + &q_space->p_node_info->node->id, + &q_space->q_node_info->node->id); + + q_space->label_stack = + ospf_ti_lfa_create_label_stack(labels, 2); + q_space->nexthop = q_space->p_node_info->nexthop; + + } else { + /* + * It can happen that the P and Q space are not adjacent when + * e.g. node protection or asymmetric weights are used. In this + * case the found P and Q nodes are used as a reference for + * another run of the algorithm! + * + * After having found the inner label stack it is stitched + * together with the outer labels. + */ + inner_backup_path_info.label_stack = XCALLOC( + MTYPE_OSPF_PATH, + sizeof(struct mpls_label_stack) + + sizeof(mpls_label_t) * MPLS_MAX_LABELS); + ospf_ti_lfa_generate_inner_label_stack(area, p_space, q_space, + &inner_backup_path_info); + + /* + * First stitch together the outer P node label with the inner + * label stack. + */ + if (q_space->p_node_info->node->id.s_addr + == p_space->root->id.s_addr) { + /* + * It can happen that the P node is the root itself, + * therefore we don't need a label for it. Just take + * the inner label stack first. + */ + q_space->label_stack = ospf_ti_lfa_create_label_stack( + inner_backup_path_info.label_stack->label, + inner_backup_path_info.label_stack->num_labels); + + /* Use the inner P or Q node for the nexthop */ + if (inner_backup_path_info.p_node_info.type + != OSPF_TI_LFA_UNDEFINED_NODE) + q_space->nexthop = inner_backup_path_info + .p_node_info.nexthop; + else + q_space->nexthop = inner_backup_path_info + .q_node_info.nexthop; + + } else if (ospf_spf_vertex_parent_find( + p_space->root->id, + q_space->p_node_info->node)) { + /* + * It can happen that the outer P node is a child of + * the root, therefore we might just need the + * adjacency SID for the outer P node instead of the + * prefix SID. Then just append the inner label stack. + */ + labels[0] = ospf_sr_get_adj_sid_by_id( + &p_space->root->id, + &q_space->p_node_info->node->id); + q_space->label_stack = + ospf_ti_lfa_create_label_stack(labels, 1); + ospf_ti_lfa_append_label_stack( + q_space->label_stack, + inner_backup_path_info.label_stack->label, + inner_backup_path_info.label_stack->num_labels); + q_space->nexthop = q_space->p_node_info->nexthop; + } else { + /* The outer P node needs a Prefix-SID here */ + labels[0] = ospf_sr_get_prefix_sid_by_id( + &q_space->p_node_info->node->id); + q_space->label_stack = + ospf_ti_lfa_create_label_stack(labels, 1); + ospf_ti_lfa_append_label_stack( + q_space->label_stack, + inner_backup_path_info.label_stack->label, + inner_backup_path_info.label_stack->num_labels); + q_space->nexthop = q_space->p_node_info->nexthop; + } + + /* Now the outer Q node needs to be considered */ + if (ospf_spf_vertex_parent_find( + inner_backup_path_info.q_node_info.node->id, + q_space->q_node_info->node)) { + /* + * The outer Q node can be a child of the inner Q node, + * hence just add an Adjacency-SID. + */ + labels[0] = ospf_sr_get_adj_sid_by_id( + &inner_backup_path_info.q_node_info.node->id, + &q_space->q_node_info->node->id); + ospf_ti_lfa_append_label_stack(q_space->label_stack, + labels, 1); + } else { + /* Otherwise a Prefix-SID is needed */ + labels[0] = ospf_sr_get_prefix_sid_by_id( + &q_space->q_node_info->node->id); + ospf_ti_lfa_append_label_stack(q_space->label_stack, + labels, 1); + } + /* + * Note that there's also the case where the inner and outer Q + * node are the same, but then there's nothing to do! + */ + } +} + +static struct list * +ospf_ti_lfa_generate_post_convergence_path(struct list *pc_vertex_list, + struct vertex *dest) +{ + struct list *pc_path; + struct vertex *current_vertex; + struct vertex_parent *parent; + + current_vertex = ospf_spf_vertex_find(dest->id, pc_vertex_list); + if (!current_vertex) { + if (IS_DEBUG_OSPF_TI_LFA) + zlog_debug( + "%s: There seems to be no post convergence path (yet).", + __func__); + return NULL; + } + + pc_path = list_new(); + listnode_add(pc_path, current_vertex); + + /* Generate a backup path in reverse order */ + for (;;) { + parent = listnode_head(current_vertex->parents); + if (!parent) + break; + + listnode_add(pc_path, parent->parent); + current_vertex = parent->parent; + } + + return pc_path; +} + +static void ospf_ti_lfa_generate_q_spaces(struct ospf_area *area, + struct p_space *p_space, + struct vertex *dest, bool recursive, + struct list *pc_path) +{ + struct listnode *node; + struct vertex *child; + struct route_table *new_table, *new_rtrs; + struct q_space *q_space, q_space_search; + char label_buf[MPLS_LABEL_STRLEN]; + char res_buf[PROTECTED_RESOURCE_STRLEN]; + bool node_protected; + + ospf_print_protected_resource(p_space->protected_resource, res_buf); + node_protected = + p_space->protected_resource->type == OSPF_TI_LFA_NODE_PROTECTION + && dest->id.s_addr + == p_space->protected_resource->router_id.s_addr; + + /* + * If node protection is used, don't build a Q space for the protected + * node of that particular P space. Move on with children instead. + */ + if (node_protected) { + if (recursive) { + /* Recursively generate Q spaces for all children */ + for (ALL_LIST_ELEMENTS_RO(dest->children, node, child)) + ospf_ti_lfa_generate_q_spaces(area, p_space, + child, recursive, + pc_path); + } + return; + } + + /* Check if we already have a Q space for this destination */ + q_space_search.root = dest; + if (q_spaces_find(p_space->q_spaces, &q_space_search)) + return; + + q_space = XCALLOC(MTYPE_OSPF_Q_SPACE, sizeof(struct q_space)); + q_space->p_node_info = XCALLOC(MTYPE_OSPF_Q_SPACE, + sizeof(struct ospf_ti_lfa_node_info)); + q_space->q_node_info = XCALLOC(MTYPE_OSPF_Q_SPACE, + sizeof(struct ospf_ti_lfa_node_info)); + + new_table = route_table_init(); + new_rtrs = route_table_init(); + + /* + * Generate a new (reversed!) SPF tree for this vertex, + * dry run true, root node false + */ + area->spf_reversed = true; + ospf_spf_calculate(area, dest->lsa_p, new_table, new_rtrs, true, false); + + /* Reset the flag for reverse SPF */ + area->spf_reversed = false; + + q_space->root = area->spf; + q_space->vertex_list = area->spf_vertex_list; + q_space->label_stack = NULL; + + if (pc_path) + q_space->pc_path = ospf_ti_lfa_map_path_to_pc_vertices( + pc_path, p_space->pc_vertex_list); + else + q_space->pc_path = ospf_ti_lfa_generate_post_convergence_path( + p_space->pc_vertex_list, q_space->root); + + /* If there's no backup path available then we are done here. */ + if (!q_space->pc_path) { + zlog_info( + "%s: NO backup path found for root %pI4 and destination %pI4 for %s, aborting ...", + __func__, &p_space->root->id, &q_space->root->id, + res_buf); + return; + } + + /* 'Cut' the protected resource out of the new SPF tree */ + ospf_spf_remove_resource(q_space->root, q_space->vertex_list, + p_space->protected_resource); + + /* + * Generate the smallest possible label stack from the root of the P + * space to the root of the Q space. + */ + ospf_ti_lfa_generate_label_stack(area, p_space, q_space); + + if (q_space->label_stack) { + mpls_label2str(q_space->label_stack->num_labels, + q_space->label_stack->label, label_buf, + MPLS_LABEL_STRLEN, true); + zlog_info( + "%s: Generated label stack %s for root %pI4 and destination %pI4 for %s", + __func__, label_buf, &p_space->root->id, + &q_space->root->id, res_buf); + } else { + zlog_info( + "%s: NO label stack generated for root %pI4 and destination %pI4 for %s", + __func__, &p_space->root->id, &q_space->root->id, + res_buf); + } + + /* We are finished, store the new Q space in the P space struct */ + q_spaces_add(p_space->q_spaces, q_space); + + /* Recursively generate Q spaces for all children */ + if (recursive) { + for (ALL_LIST_ELEMENTS_RO(dest->children, node, child)) + ospf_ti_lfa_generate_q_spaces(area, p_space, child, + recursive, pc_path); + } +} + +static void ospf_ti_lfa_generate_post_convergence_spf(struct ospf_area *area, + struct p_space *p_space) +{ + struct route_table *new_table, *new_rtrs; + + new_table = route_table_init(); + new_rtrs = route_table_init(); + + area->spf_protected_resource = p_space->protected_resource; + + /* + * The 'post convergence' SPF tree is generated here + * dry run true, root node false + * + * So how does this work? During the SPF calculation the algorithm + * checks if a link belongs to a protected resource and then just + * ignores it. + * This is actually _NOT_ a good way to calculate the post + * convergence SPF tree. The preferred way would be to delete the + * relevant links (and nodes) from a copy of the LSDB and then just run + * the SPF algorithm on that as usual. + * However, removing links from router LSAs appears to be its own + * endeavour (because LSAs are stored as a 'raw' stream), so we go with + * this rather hacky way for now. + */ + ospf_spf_calculate(area, area->router_lsa_self, new_table, new_rtrs, + true, false); + + p_space->pc_spf = area->spf; + p_space->pc_vertex_list = area->spf_vertex_list; + + area->spf_protected_resource = NULL; +} + +static void +ospf_ti_lfa_generate_p_space(struct ospf_area *area, struct vertex *child, + struct protected_resource *protected_resource, + bool recursive, struct list *pc_path) +{ + struct vertex *spf_orig; + struct list *vertex_list, *vertex_list_orig; + struct p_space *p_space; + + p_space = XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_space)); + vertex_list = list_new(); + + /* The P-space will get its own SPF tree, so copy the old one */ + ospf_spf_copy(area->spf, vertex_list); + p_space->root = listnode_head(vertex_list); + p_space->vertex_list = vertex_list; + p_space->protected_resource = protected_resource; + + /* Initialize the Q spaces for this P space and protected resource */ + p_space->q_spaces = + XCALLOC(MTYPE_OSPF_Q_SPACE, sizeof(struct q_spaces_head)); + q_spaces_init(p_space->q_spaces); + + /* 'Cut' the protected resource out of the new SPF tree */ + ospf_spf_remove_resource(p_space->root, p_space->vertex_list, + p_space->protected_resource); + + /* + * Since we are going to calculate more SPF trees for Q spaces, keep the + * 'original' one here temporarily + */ + spf_orig = area->spf; + vertex_list_orig = area->spf_vertex_list; + + /* Generate the post convergence SPF as a blueprint for backup paths */ + ospf_ti_lfa_generate_post_convergence_spf(area, p_space); + + /* Generate the relevant Q spaces for this particular P space */ + ospf_ti_lfa_generate_q_spaces(area, p_space, child, recursive, pc_path); + + /* Put the 'original' SPF tree back in place */ + area->spf = spf_orig; + area->spf_vertex_list = vertex_list_orig; + + /* We are finished, store the new P space */ + p_spaces_add(area->p_spaces, p_space); +} + +void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area, + enum protection_type protection_type) +{ + struct listnode *node, *inner_node; + struct vertex *root, *child; + struct vertex_parent *vertex_parent; + uint8_t *p, *lim; + struct router_lsa_link *l = NULL; + struct prefix stub_prefix, child_prefix; + struct protected_resource *protected_resource; + + area->p_spaces = + XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_spaces_head)); + p_spaces_init(area->p_spaces); + + root = area->spf; + + /* Root or its router LSA was not created yet? */ + if (!root || !root->lsa) + return; + + stub_prefix.family = AF_INET; + child_prefix.family = AF_INET; + child_prefix.prefixlen = IPV4_MAX_PREFIXLEN; + + p = ((uint8_t *)root->lsa) + OSPF_LSA_HEADER_SIZE + 4; + lim = ((uint8_t *)root->lsa) + ntohs(root->lsa->length); + + zlog_info("%s: Generating P spaces for area %pI4", __func__, + &area->area_id); + + /* + * Iterate over all stub networks which target other OSPF neighbors. + * Check the nexthop of the child vertex if a stub network is relevant. + */ + while (p < lim) { + l = (struct router_lsa_link *)p; + p += (OSPF_ROUTER_LSA_LINK_SIZE + + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE)); + + /* First comes node protection */ + if (protection_type == OSPF_TI_LFA_NODE_PROTECTION) { + if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT) { + protected_resource = XCALLOC( + MTYPE_OSPF_P_SPACE, + sizeof(struct protected_resource)); + protected_resource->type = protection_type; + protected_resource->router_id = l->link_id; + child = ospf_spf_vertex_find( + protected_resource->router_id, + root->children); + if (child) + ospf_ti_lfa_generate_p_space( + area, child, protected_resource, + true, NULL); + } + + continue; + } + + /* The rest is about link protection */ + if (protection_type != OSPF_TI_LFA_LINK_PROTECTION) + continue; + + if (l->m[0].type != LSA_LINK_TYPE_STUB) + continue; + + stub_prefix.prefixlen = ip_masklen(l->link_data); + stub_prefix.u.prefix4 = l->link_id; + + for (ALL_LIST_ELEMENTS_RO(root->children, node, child)) { + + if (child->type != OSPF_VERTEX_ROUTER) + continue; + + for (ALL_LIST_ELEMENTS_RO(child->parents, inner_node, + vertex_parent)) { + + child_prefix.u.prefix4 = + vertex_parent->nexthop->router; + + /* + * If there's a link for that stub network then + * we will protect it. Hence generate a P space + * for that particular link including the + * Q spaces so we can later on generate a + * backup path for the link. + */ + if (prefix_match(&stub_prefix, &child_prefix)) { + zlog_info( + "%s: Generating P space for %pI4", + __func__, &l->link_id); + + protected_resource = XCALLOC( + MTYPE_OSPF_P_SPACE, + sizeof(struct + protected_resource)); + protected_resource->type = + protection_type; + protected_resource->link = l; + + ospf_ti_lfa_generate_p_space( + area, child, protected_resource, + true, NULL); + } + } + } + } +} + +static struct p_space *ospf_ti_lfa_get_p_space_by_path(struct ospf_area *area, + struct ospf_path *path) +{ + struct p_space *p_space; + struct router_lsa_link *link; + struct vertex *child; + int type; + + frr_each(p_spaces, area->p_spaces, p_space) { + type = p_space->protected_resource->type; + + if (type == OSPF_TI_LFA_LINK_PROTECTION) { + link = p_space->protected_resource->link; + if ((path->nexthop.s_addr & link->link_data.s_addr) + == (link->link_id.s_addr & link->link_data.s_addr)) + return p_space; + } + + if (type == OSPF_TI_LFA_NODE_PROTECTION) { + child = ospf_spf_vertex_by_nexthop(area->spf, + &path->nexthop); + if (child + && p_space->protected_resource->router_id.s_addr + == child->id.s_addr) + return p_space; + } + } + + return NULL; +} + +void ospf_ti_lfa_insert_backup_paths(struct ospf_area *area, + struct route_table *new_table) +{ + struct route_node *rn; + struct ospf_route *or; + struct ospf_path *path; + struct listnode *node; + struct p_space *p_space; + struct q_space *q_space, q_space_search; + struct vertex root_search; + char label_buf[MPLS_LABEL_STRLEN]; + + for (rn = route_top(new_table); rn; rn = route_next(rn)) { + or = rn->info; + if (or == NULL) + continue; + + /* Insert a backup path for all OSPF paths */ + for (ALL_LIST_ELEMENTS_RO(or->paths, node, path)) { + + if (path->adv_router.s_addr == INADDR_ANY + || path->nexthop.s_addr == INADDR_ANY) + continue; + + if (IS_DEBUG_OSPF_TI_LFA) + zlog_debug( + "%s: attempting to insert backup path for prefix %pFX, router id %pI4 and nexthop %pI4.", + __func__, &rn->p, &path->adv_router, + &path->nexthop); + + p_space = ospf_ti_lfa_get_p_space_by_path(area, path); + if (!p_space) { + if (IS_DEBUG_OSPF_TI_LFA) + zlog_debug( + "%s: P space not found for router id %pI4 and nexthop %pI4.", + __func__, &path->adv_router, + &path->nexthop); + continue; + } + + root_search.id = path->adv_router; + q_space_search.root = &root_search; + q_space = q_spaces_find(p_space->q_spaces, + &q_space_search); + if (!q_space) { + if (IS_DEBUG_OSPF_TI_LFA) + zlog_debug( + "%s: Q space not found for advertising router %pI4.", + __func__, &path->adv_router); + continue; + } + + /* If there's a backup label stack, insert it*/ + if (q_space->label_stack) { + /* Init the backup path data in path */ + path->srni.backup_label_stack = XCALLOC( + MTYPE_OSPF_PATH, + sizeof(struct mpls_label_stack) + + sizeof(mpls_label_t) + * q_space->label_stack + ->num_labels); + + /* Copy over the label stack */ + path->srni.backup_label_stack->num_labels = + q_space->label_stack->num_labels; + memcpy(path->srni.backup_label_stack->label, + q_space->label_stack->label, + sizeof(mpls_label_t) + * q_space->label_stack + ->num_labels); + + /* Set the backup nexthop too */ + path->srni.backup_nexthop = q_space->nexthop; + } + + if (path->srni.backup_label_stack) { + mpls_label2str( + path->srni.backup_label_stack + ->num_labels, + path->srni.backup_label_stack->label, + label_buf, MPLS_LABEL_STRLEN, true); + if (IS_DEBUG_OSPF_TI_LFA) + zlog_debug( + "%s: inserted backup path %s for prefix %pFX, router id %pI4 and nexthop %pI4.", + __func__, label_buf, &rn->p, + &path->adv_router, + &path->nexthop); + } else { + if (IS_DEBUG_OSPF_TI_LFA) + zlog_debug( + "%s: inserted NO backup path for prefix %pFX, router id %pI4 and nexthop %pI4.", + __func__, &rn->p, + &path->adv_router, + &path->nexthop); + } + } + } +} + +void ospf_ti_lfa_free_p_spaces(struct ospf_area *area) +{ + struct p_space *p_space; + struct q_space *q_space; + + while ((p_space = p_spaces_pop(area->p_spaces))) { + while ((q_space = q_spaces_pop(p_space->q_spaces))) { + ospf_spf_cleanup(q_space->root, q_space->vertex_list); + + if (q_space->pc_path) + list_delete(&q_space->pc_path); + + XFREE(MTYPE_OSPF_Q_SPACE, q_space->p_node_info); + XFREE(MTYPE_OSPF_Q_SPACE, q_space->q_node_info); + XFREE(MTYPE_OSPF_Q_SPACE, q_space->label_stack); + XFREE(MTYPE_OSPF_Q_SPACE, q_space); + } + + ospf_spf_cleanup(p_space->root, p_space->vertex_list); + ospf_spf_cleanup(p_space->pc_spf, p_space->pc_vertex_list); + XFREE(MTYPE_OSPF_P_SPACE, p_space->protected_resource); + + q_spaces_fini(p_space->q_spaces); + XFREE(MTYPE_OSPF_Q_SPACE, p_space->q_spaces); + } + + p_spaces_fini(area->p_spaces); + XFREE(MTYPE_OSPF_P_SPACE, area->p_spaces); +} + +void ospf_ti_lfa_compute(struct ospf_area *area, struct route_table *new_table, + enum protection_type protection_type) +{ + /* + * Generate P spaces per protected link/node and their respective Q + * spaces, generate backup paths (MPLS label stacks) by finding P/Q + * nodes. + */ + ospf_ti_lfa_generate_p_spaces(area, protection_type); + + /* Insert the generated backup paths into the routing table. */ + ospf_ti_lfa_insert_backup_paths(area, new_table); + + /* Cleanup P spaces and related datastructures including Q spaces. */ + ospf_ti_lfa_free_p_spaces(area); +} diff --git a/ospfd/ospf_ti_lfa.h b/ospfd/ospf_ti_lfa.h new file mode 100644 index 0000000000..bc8f19b98f --- /dev/null +++ b/ospfd/ospf_ti_lfa.h @@ -0,0 +1,41 @@ +/* + * OSPF calculation. + * Copyright (C) 2020 NetDEF, Inc. + * Sascha Kattelmann + * + * This file is part of FRR. + * + * FRR is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; either version 2, or (at your option) any + * later version. + * + * FRR is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef _OSPF_TI_LFA_H +#define _OSPF_TI_LFA_H + +#define PROTECTED_RESOURCE_STRLEN 100 + +extern void ospf_ti_lfa_compute(struct ospf_area *area, + struct route_table *new_table, + enum protection_type protection_type); + +/* unit testing */ +extern void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area, + enum protection_type protection_type); +extern void ospf_ti_lfa_insert_backup_paths(struct ospf_area *area, + struct route_table *new_table); +extern void ospf_ti_lfa_free_p_spaces(struct ospf_area *area); +void ospf_print_protected_resource( + struct protected_resource *protected_resource, char *buf); + +#endif /* _OSPF_TI_LFA_H */ diff --git a/ospfd/ospf_vty.c b/ospfd/ospf_vty.c index 0408462110..4132452069 100644 --- a/ospfd/ospf_vty.c +++ b/ospfd/ospf_vty.c @@ -280,7 +280,7 @@ DEFPY (ospf_router_id, for (ALL_LIST_ELEMENTS_RO(ospf->areas, node, area)) if (area->full_nbrs) { vty_out(vty, - "For this router-id change to take effect, save config and restart ospfd\n"); + "For this router-id change to take effect, use “clear ip ospf process” command\n"); return CMD_SUCCESS; } @@ -313,7 +313,7 @@ DEFUN_HIDDEN (ospf_router_id_old, for (ALL_LIST_ELEMENTS_RO(ospf->areas, node, area)) if (area->full_nbrs) { vty_out(vty, - "For this router-id change to take effect, save config and restart ospfd\n"); + "For this router-id change to take effect, use “clear ip ospf process” command\n"); return CMD_SUCCESS; } @@ -346,7 +346,7 @@ DEFPY (no_ospf_router_id, for (ALL_LIST_ELEMENTS_RO(ospf->areas, node, area)) if (area->full_nbrs) { vty_out(vty, - "For this router-id change to take effect, save config and restart ospfd\n"); + "For this router-id change to take effect, use “clear ip ospf process” command\n"); return CMD_SUCCESS; } @@ -2602,6 +2602,43 @@ ALIAS(no_ospf_write_multiplier, no_write_multiplier_cmd, "Write multiplier\n" "Maximum number of interface serviced per write\n") +DEFUN(ospf_ti_lfa, ospf_ti_lfa_cmd, "fast-reroute ti-lfa [node-protection]", + "Fast Reroute for MPLS and IP resilience\n" + "Topology Independent LFA (Loop-Free Alternate)\n" + "TI-LFA node protection (default is link protection)\n") +{ + VTY_DECLVAR_INSTANCE_CONTEXT(ospf, ospf); + + ospf->ti_lfa_enabled = true; + + if (argc == 3) + ospf->ti_lfa_protection_type = OSPF_TI_LFA_NODE_PROTECTION; + else + ospf->ti_lfa_protection_type = OSPF_TI_LFA_LINK_PROTECTION; + + ospf_spf_calculate_schedule(ospf, SPF_FLAG_CONFIG_CHANGE); + + return CMD_SUCCESS; +} + +DEFUN(no_ospf_ti_lfa, no_ospf_ti_lfa_cmd, + "no fast-reroute ti-lfa [node-protection]", + NO_STR + "Fast Reroute for MPLS and IP resilience\n" + "Topology Independent LFA (Loop-Free Alternate)\n" + "TI-LFA node protection (default is link protection)\n") +{ + VTY_DECLVAR_INSTANCE_CONTEXT(ospf, ospf); + + ospf->ti_lfa_enabled = false; + + ospf->ti_lfa_protection_type = OSPF_TI_LFA_UNDEFINED_PROTECTION; + + ospf_spf_calculate_schedule(ospf, SPF_FLAG_CONFIG_CHANGE); + + return CMD_SUCCESS; +} + static const char *const ospf_abr_type_descr_str[] = { "Unknown", "Standard (RFC2328)", "Alternative IBM", "Alternative Cisco", "Alternative Shortcut" @@ -3365,6 +3402,54 @@ DEFUN (show_ip_ospf_instance, return ret; } +static void ospf_interface_auth_show(struct vty *vty, struct ospf_interface *oi, + json_object *json, bool use_json) +{ + int auth_type; + + auth_type = OSPF_IF_PARAM(oi, auth_type); + + switch (auth_type) { + case OSPF_AUTH_NULL: + if (use_json) + json_object_string_add(json, "authentication", + "authenticationNone"); + else + vty_out(vty, " Authentication NULL is enabled\n"); + break; + case OSPF_AUTH_SIMPLE: { + if (use_json) + json_object_string_add(json, "authentication", + "authenticationSimplePassword"); + else + vty_out(vty, + " Simple password authentication enabled\n"); + break; + } + case OSPF_AUTH_CRYPTOGRAPHIC: { + struct crypt_key *ckey; + + if (list_isempty(OSPF_IF_PARAM(oi, auth_crypt))) + return; + + ckey = listgetdata(listtail(OSPF_IF_PARAM(oi, auth_crypt))); + if (ckey) { + if (use_json) { + json_object_string_add(json, "authentication", + "authenticationMessageDigest"); + } else { + vty_out(vty, + " Cryptographic authentication enabled\n"); + vty_out(vty, " Algorithm:MD5\n"); + } + } + break; + } + default: + break; + } +} + static void show_ip_ospf_interface_sub(struct vty *vty, struct ospf *ospf, struct interface *ifp, json_object *json_interface_sub, @@ -3686,6 +3771,9 @@ static void show_ip_ospf_interface_sub(struct vty *vty, struct ospf *ospf, ospf_nbr_count(oi, 0), ospf_nbr_count(oi, NSM_Full)); ospf_bfd_interface_show(vty, ifp, json_interface_sub, use_json); + + /* OSPF Authentication information */ + ospf_interface_auth_show(vty, oi, json_interface_sub, use_json); } } @@ -6318,31 +6406,7 @@ static int show_as_external_lsa_detail(struct vty *vty, struct ospf_lsa *lsa, return 0; } -#if 0 -static int -show_as_external_lsa_stdvty (struct ospf_lsa *lsa) -{ - struct as_external_lsa *al = (struct as_external_lsa *) lsa->data; - - /* show_ip_ospf_database_header (vty, lsa); */ - - zlog_debug( " Network Mask: /%d%s", - ip_masklen (al->mask), "\n"); - zlog_debug( " Metric Type: %s%s", - IS_EXTERNAL_METRIC (al->e[0].tos) ? - "2 (Larger than any link state path)" : "1", "\n"); - zlog_debug( " TOS: 0%s", "\n"); - zlog_debug( " Metric: %d%s", - GET_METRIC (al->e[0].metric), "\n"); - zlog_debug( " Forward Address: %pI4%s", - &al->e[0].fwd_addr, "\n"); - zlog_debug( " External Route Tag: %"ROUTE_TAG_PRI"%s%s", - (route_tag_t)ntohl (al->e[0].route_tag), "\n", "\n"); - - return 0; -} -#endif /* Show AS-NSSA-LSA detail information. */ static int show_as_nssa_lsa_detail(struct vty *vty, struct ospf_lsa *lsa, json_object *json) @@ -6630,8 +6694,8 @@ static void show_lsa_detail_adv_router(struct vty *vty, struct ospf *ospf, json_lstype); } -static void show_ip_ospf_database_summary(struct vty *vty, struct ospf *ospf, - int self, json_object *json) +void show_ip_ospf_database_summary(struct vty *vty, struct ospf *ospf, int self, + json_object *json) { struct ospf_lsa *lsa; struct route_node *rn; @@ -7316,8 +7380,8 @@ DEFUN (show_ip_ospf_instance_database_type_adv_router, continue; ospf_output = true; ret = show_ip_ospf_database_type_adv_router_common( - vty, ospf, idx ? 1 : 0, argc, argv, - use_vrf, json, uj); + vty, ospf, 2, argc, argv, use_vrf, json, + uj); } if (!ospf_output) vty_out(vty, "%% OSPF instance not found\n"); @@ -7329,8 +7393,7 @@ DEFUN (show_ip_ospf_instance_database_type_adv_router, } ret = show_ip_ospf_database_type_adv_router_common( - vty, ospf, idx ? 1 : 0, argc, argv, use_vrf, - json, uj); + vty, ospf, 2, argc, argv, use_vrf, json, uj); } } else { /* Display default ospf (instance 0) info */ @@ -8871,6 +8934,7 @@ DEFUN (no_ip_ospf_area, struct ospf_if_params *params; unsigned short instance = 0; struct in_addr addr; + struct in_addr area_id; if (argv_find(argv, argc, "(1-65535)", &idx)) instance = strtol(argv[idx]->arg, NULL, 10); @@ -8898,6 +8962,7 @@ DEFUN (no_ip_ospf_area, } else params = IF_DEF_PARAMS(ifp); + area_id = params->if_area; if (!OSPF_IF_PARAM_CONFIGURED(params, if_area)) { vty_out(vty, "Can't find specified interface area configuration.\n"); @@ -8913,6 +8978,7 @@ DEFUN (no_ip_ospf_area, if (ospf) { ospf_interface_area_unset(ospf, ifp); ospf->if_ospf_cli_count--; + ospf_area_check_free(ospf, area_id); } return CMD_SUCCESS; @@ -9377,78 +9443,6 @@ DEFUN (ospf_distance_ospf, return CMD_SUCCESS; } -#if 0 -DEFUN (ospf_distance_source, - ospf_distance_source_cmd, - "distance (1-255) A.B.C.D/M", - "Administrative distance\n" - "Distance value\n" - "IP source prefix\n") -{ - VTY_DECLVAR_CONTEXT(ospf, ospf); - int idx_number = 1; - int idx_ipv4_prefixlen = 2; - - ospf_distance_set (vty, ospf, argv[idx_number]->arg, argv[idx_ipv4_prefixlen]->arg, NULL); - - return CMD_SUCCESS; -} - -DEFUN (no_ospf_distance_source, - no_ospf_distance_source_cmd, - "no distance (1-255) A.B.C.D/M", - NO_STR - "Administrative distance\n" - "Distance value\n" - "IP source prefix\n") -{ - VTY_DECLVAR_CONTEXT(ospf, ospf); - int idx_number = 2; - int idx_ipv4_prefixlen = 3; - - ospf_distance_unset (vty, ospf, argv[idx_number]->arg, argv[idx_ipv4_prefixlen]->arg, NULL); - - return CMD_SUCCESS; -} - -DEFUN (ospf_distance_source_access_list, - ospf_distance_source_access_list_cmd, - "distance (1-255) A.B.C.D/M WORD", - "Administrative distance\n" - "Distance value\n" - "IP source prefix\n" - "Access list name\n") -{ - VTY_DECLVAR_CONTEXT(ospf, ospf); - int idx_number = 1; - int idx_ipv4_prefixlen = 2; - int idx_word = 3; - - ospf_distance_set (vty, ospf, argv[idx_number]->arg, argv[idx_ipv4_prefixlen]->arg, argv[idx_word]->arg); - - return CMD_SUCCESS; -} - -DEFUN (no_ospf_distance_source_access_list, - no_ospf_distance_source_access_list_cmd, - "no distance (1-255) A.B.C.D/M WORD", - NO_STR - "Administrative distance\n" - "Distance value\n" - "IP source prefix\n" - "Access list name\n") -{ - VTY_DECLVAR_CONTEXT(ospf, ospf); - int idx_number = 2; - int idx_ipv4_prefixlen = 3; - int idx_word = 4; - - ospf_distance_unset (vty, ospf, argv[idx_number]->arg, argv[idx_ipv4_prefixlen]->arg, argv[idx_word]->arg); - - return CMD_SUCCESS; -} -#endif - DEFUN (ip_ospf_mtu_ignore, ip_ospf_mtu_ignore_addr_cmd, "ip ospf mtu-ignore [A.B.C.D]", @@ -9928,10 +9922,10 @@ DEFPY(no_ospf_gr_helper_planned_only, return CMD_SUCCESS; } -static int ospf_print_vty_helper_dis_rtr_walkcb(struct hash_bucket *backet, +static int ospf_print_vty_helper_dis_rtr_walkcb(struct hash_bucket *bucket, void *arg) { - struct advRtr *rtr = backet->data; + struct advRtr *rtr = bucket->data; struct vty *vty = (struct vty *)arg; static unsigned int count; @@ -11177,6 +11171,70 @@ DEFUN (show_ip_ospf_vrfs, return CMD_SUCCESS; } +DEFPY (clear_ip_ospf_neighbor, + clear_ip_ospf_neighbor_cmd, + "clear ip ospf [(1-65535)]$instance neighbor [A.B.C.D$nbr_id]", + CLEAR_STR + IP_STR + "OSPF information\n" + "Instance ID\n" + "Reset OSPF Neighbor\n" + "Neighbor ID\n") +{ + struct listnode *node; + struct ospf *ospf = NULL; + + /* If user does not specify the arguments, + * instance = 0 and nbr_id = 0.0.0.0 + */ + if (instance != 0) { + /* This means clear only the particular ospf process */ + ospf = ospf_lookup_instance(instance); + if (ospf == NULL) + return CMD_NOT_MY_INSTANCE; + } + + /* Clear all the ospf processes */ + for (ALL_LIST_ELEMENTS_RO(om->ospf, node, ospf)) { + if (!ospf->oi_running) + continue; + + ospf_neighbor_reset(ospf, nbr_id, nbr_id_str); + } + + return CMD_SUCCESS; +} + +DEFPY (clear_ip_ospf_process, + clear_ip_ospf_process_cmd, + "clear ip ospf [(1-65535)]$instance process", + CLEAR_STR + IP_STR + "OSPF information\n" + "Instance ID\n" + "Reset OSPF Process\n") +{ + struct listnode *node; + struct ospf *ospf = NULL; + + /* Check if instance is not passed as an argument */ + if (instance != 0) { + /* This means clear only the particular ospf process */ + ospf = ospf_lookup_instance(instance); + if (ospf == NULL) + return CMD_NOT_MY_INSTANCE; + } + + /* Clear all the ospf processes */ + for (ALL_LIST_ELEMENTS_RO(om->ospf, node, ospf)) { + if (!ospf->oi_running) + continue; + + ospf_process_reset(ospf); + } + + return CMD_SUCCESS; +} static const char *const ospf_abr_type_str[] = { "unknown", "standard", "ibm", "cisco", "shortcut" @@ -11185,10 +11243,10 @@ static const char *const ospf_abr_type_str[] = { static const char *const ospf_shortcut_mode_str[] = { "default", "enable", "disable" }; -static int ospf_vty_external_rt_walkcb(struct hash_bucket *backet, +static int ospf_vty_external_rt_walkcb(struct hash_bucket *bucket, void *arg) { - struct external_info *ei = backet->data; + struct external_info *ei = bucket->data; struct vty *vty = (struct vty *)arg; static unsigned int count; @@ -11204,10 +11262,10 @@ static int ospf_vty_external_rt_walkcb(struct hash_bucket *backet, return HASHWALK_CONTINUE; } -static int ospf_json_external_rt_walkcb(struct hash_bucket *backet, +static int ospf_json_external_rt_walkcb(struct hash_bucket *bucket, void *arg) { - struct external_info *ei = backet->data; + struct external_info *ei = bucket->data; struct json_object *json = (struct json_object *)arg; char buf[PREFIX2STR_BUFFER]; char exnalbuf[20]; @@ -11976,10 +12034,10 @@ static int config_write_ospf_redistribute(struct vty *vty, struct ospf *ospf) return 0; } -static int ospf_cfg_write_helper_dis_rtr_walkcb(struct hash_bucket *backet, +static int ospf_cfg_write_helper_dis_rtr_walkcb(struct hash_bucket *bucket, void *arg) { - struct advRtr *rtr = backet->data; + struct advRtr *rtr = bucket->data; struct vty *vty = (struct vty *)arg; vty_out(vty, " graceful-restart helper-only %pI4\n", @@ -12247,6 +12305,14 @@ static int ospf_config_write_one(struct vty *vty, struct ospf *ospf) oi->ifp->name, &oi->address->u.prefix4); } + /* TI-LFA print. */ + if (ospf->ti_lfa_enabled) { + if (ospf->ti_lfa_protection_type == OSPF_TI_LFA_NODE_PROTECTION) + vty_out(vty, " fast-reroute ti-lfa node-protection\n"); + else + vty_out(vty, " fast-reroute ti-lfa\n"); + } + /* Network area print. */ config_write_network_area(vty, ospf); @@ -12491,13 +12557,6 @@ static void ospf_vty_zebra_init(void) &no_ospf_external_route_aggregation_no_adrvertise_cmd); install_element(OSPF_NODE, &ospf_route_aggregation_timer_cmd); install_element(OSPF_NODE, &no_ospf_route_aggregation_timer_cmd); - -#if 0 - install_element (OSPF_NODE, &ospf_distance_source_cmd); - install_element (OSPF_NODE, &no_ospf_distance_source_cmd); - install_element (OSPF_NODE, &ospf_distance_source_access_list_cmd); - install_element (OSPF_NODE, &no_ospf_distance_source_access_list_cmd); -#endif /* 0 */ } static int ospf_config_write(struct vty *vty); @@ -12573,6 +12632,8 @@ DEFUN (clear_ip_ospf_interface, void ospf_vty_clear_init(void) { install_element(ENABLE_NODE, &clear_ip_ospf_interface_cmd); + install_element(ENABLE_NODE, &clear_ip_ospf_process_cmd); + install_element(ENABLE_NODE, &clear_ip_ospf_neighbor_cmd); } @@ -12709,6 +12770,10 @@ void ospf_vty_init(void) install_element(OSPF_NODE, &ospf_proactive_arp_cmd); install_element(OSPF_NODE, &no_ospf_proactive_arp_cmd); + /* TI-LFA commands */ + install_element(OSPF_NODE, &ospf_ti_lfa_cmd); + install_element(OSPF_NODE, &no_ospf_ti_lfa_cmd); + /* Init interface related vty commands. */ ospf_vty_if_init(); diff --git a/ospfd/ospf_vty.h b/ospfd/ospf_vty.h index 79aabe7b4e..bf9c971710 100644 --- a/ospfd/ospf_vty.h +++ b/ospfd/ospf_vty.h @@ -54,4 +54,8 @@ extern void ospf_vty_show_init(void); extern void ospf_vty_clear_init(void); extern int str2area_id(const char *, struct in_addr *, int *); +/* unit tests */ +void show_ip_ospf_database_summary(struct vty *vty, struct ospf *ospf, int self, + json_object *json); + #endif /* _QUAGGA_OSPF_VTY_H */ diff --git a/ospfd/ospf_zebra.c b/ospfd/ospf_zebra.c index 2d02619ae3..aaab274570 100644 --- a/ospfd/ospf_zebra.c +++ b/ospfd/ospf_zebra.c @@ -198,15 +198,70 @@ static int ospf_interface_vrf_update(ZAPI_CALLBACK_ARGS) return 0; } +/* Nexthop, ifindex, distance and metric information. */ +static void ospf_zebra_add_nexthop(struct ospf *ospf, struct ospf_path *path, + struct zapi_route *api) +{ + struct zapi_nexthop *api_nh; + struct zapi_nexthop *api_nh_backup; + + /* TI-LFA backup path label stack comes first, if present */ + if (path->srni.backup_label_stack) { + api_nh_backup = &api->backup_nexthops[api->backup_nexthop_num]; + api_nh_backup->vrf_id = ospf->vrf_id; + + api_nh_backup->type = NEXTHOP_TYPE_IPV4; + api_nh_backup->gate.ipv4 = path->srni.backup_nexthop; + + api_nh_backup->label_num = + path->srni.backup_label_stack->num_labels; + memcpy(api_nh_backup->labels, + path->srni.backup_label_stack->label, + sizeof(mpls_label_t) * api_nh_backup->label_num); + + api->backup_nexthop_num++; + } + + /* And here comes the primary nexthop */ + api_nh = &api->nexthops[api->nexthop_num]; +#ifdef HAVE_NETLINK + if (path->unnumbered + || (path->nexthop.s_addr != INADDR_ANY && path->ifindex != 0)) { +#else /* HAVE_NETLINK */ + if (path->nexthop.s_addr != INADDR_ANY && path->ifindex != 0) { +#endif /* HAVE_NETLINK */ + api_nh->gate.ipv4 = path->nexthop; + api_nh->ifindex = path->ifindex; + api_nh->type = NEXTHOP_TYPE_IPV4_IFINDEX; + } else if (path->nexthop.s_addr != INADDR_ANY) { + api_nh->gate.ipv4 = path->nexthop; + api_nh->type = NEXTHOP_TYPE_IPV4; + } else { + api_nh->ifindex = path->ifindex; + api_nh->type = NEXTHOP_TYPE_IFINDEX; + } + api_nh->vrf_id = ospf->vrf_id; + + /* Set TI-LFA backup nexthop info if present */ + if (path->srni.backup_label_stack) { + SET_FLAG(api->message, ZAPI_MESSAGE_BACKUP_NEXTHOPS); + SET_FLAG(api_nh->flags, ZAPI_NEXTHOP_FLAG_HAS_BACKUP); + + /* Just care about a single TI-LFA backup path for now */ + api_nh->backup_num = 1; + api_nh->backup_idx[0] = api->backup_nexthop_num - 1; + } + + api->nexthop_num++; +} + void ospf_zebra_add(struct ospf *ospf, struct prefix_ipv4 *p, struct ospf_route * or) { struct zapi_route api; - struct zapi_nexthop *api_nh; uint8_t distance; struct ospf_path *path; struct listnode *node; - int count = 0; memset(&api, 0, sizeof(api)); api.vrf_id = ospf->vrf_id; @@ -241,29 +296,11 @@ void ospf_zebra_add(struct ospf *ospf, struct prefix_ipv4 *p, api.distance = distance; } - /* Nexthop, ifindex, distance and metric information. */ for (ALL_LIST_ELEMENTS_RO(or->paths, node, path)) { - if (count >= MULTIPATH_NUM) + if (api.nexthop_num >= MULTIPATH_NUM) break; - api_nh = &api.nexthops[count]; -#ifdef HAVE_NETLINK - if (path->unnumbered || (path->nexthop.s_addr != INADDR_ANY - && path->ifindex != 0)) { -#else /* HAVE_NETLINK */ - if (path->nexthop.s_addr != INADDR_ANY && path->ifindex != 0) { -#endif /* HAVE_NETLINK */ - api_nh->gate.ipv4 = path->nexthop; - api_nh->ifindex = path->ifindex; - api_nh->type = NEXTHOP_TYPE_IPV4_IFINDEX; - } else if (path->nexthop.s_addr != INADDR_ANY) { - api_nh->gate.ipv4 = path->nexthop; - api_nh->type = NEXTHOP_TYPE_IPV4; - } else { - api_nh->ifindex = path->ifindex; - api_nh->type = NEXTHOP_TYPE_IFINDEX; - } - api_nh->vrf_id = ospf->vrf_id; - count++; + + ospf_zebra_add_nexthop(ospf, path, &api); if (IS_DEBUG_OSPF(zebra, ZEBRA_REDISTRIBUTE)) { struct interface *ifp; @@ -276,7 +313,6 @@ void ospf_zebra_add(struct ospf *ospf, struct prefix_ipv4 *p, ifp ? ifp->name : " "); } } - api.nexthop_num = count; zclient_route_send(ZEBRA_ROUTE_ADD, zclient, &api); } @@ -501,12 +537,10 @@ void ospf_zebra_update_prefix_sid(const struct sr_prefix *srp) { struct zapi_labels zl; struct zapi_nexthop *znh; + struct zapi_nexthop *znh_backup; struct listnode *node; struct ospf_path *path; - osr_debug("SR (%s): Update Labels %u for Prefix %pFX", __func__, - srp->label_in, (struct prefix *)&srp->prefv4); - /* Prepare message. */ memset(&zl, 0, sizeof(zl)); zl.type = ZEBRA_LSP_OSPF_SR; @@ -520,6 +554,11 @@ void ospf_zebra_update_prefix_sid(const struct sr_prefix *srp) znh->ifindex = srp->nhlfe.ifindex; znh->label_num = 1; znh->labels[0] = srp->nhlfe.label_out; + + osr_debug("SR (%s): Configure Prefix %pFX with labels %u/%u", + __func__, (struct prefix *)&srp->prefv4, + srp->label_in, srp->nhlfe.label_out); + break; case PREF_SID: @@ -535,6 +574,10 @@ void ospf_zebra_update_prefix_sid(const struct sr_prefix *srp) if (srp->route == NULL) { return; } + + osr_debug("SR (%s): Configure Prefix %pFX with", + __func__, (struct prefix *)&srp->prefv4); + for (ALL_LIST_ELEMENTS_RO(srp->route->paths, node, path)) { if (path->srni.label_out == MPLS_INVALID_LABEL) continue; @@ -542,12 +585,56 @@ void ospf_zebra_update_prefix_sid(const struct sr_prefix *srp) if (zl.nexthop_num >= MULTIPATH_NUM) break; + /* + * TI-LFA backup path label stack comes first, if + * present. + */ + if (path->srni.backup_label_stack) { + znh_backup = &zl.backup_nexthops + [zl.backup_nexthop_num++]; + znh_backup->type = NEXTHOP_TYPE_IPV4; + znh_backup->gate.ipv4 = + path->srni.backup_nexthop; + + memcpy(znh_backup->labels, + path->srni.backup_label_stack->label, + sizeof(mpls_label_t) + * path->srni.backup_label_stack + ->num_labels); + + znh_backup->label_num = + path->srni.backup_label_stack + ->num_labels; + if (path->srni.label_out + != MPLS_LABEL_IPV4_EXPLICIT_NULL + && path->srni.label_out + != MPLS_LABEL_IMPLICIT_NULL) + znh_backup->labels + [znh_backup->label_num++] = + path->srni.label_out; + } + znh = &zl.nexthops[zl.nexthop_num++]; znh->type = NEXTHOP_TYPE_IPV4_IFINDEX; znh->gate.ipv4 = path->nexthop; znh->ifindex = path->ifindex; znh->label_num = 1; znh->labels[0] = path->srni.label_out; + + osr_debug(" |- labels %u/%u", srp->label_in, + srp->nhlfe.label_out); + + /* Set TI-LFA backup nexthop info if present */ + if (path->srni.backup_label_stack) { + SET_FLAG(zl.message, ZAPI_LABELS_HAS_BACKUPS); + SET_FLAG(znh->flags, + ZAPI_NEXTHOP_FLAG_HAS_BACKUP); + + /* Just care about a single TI-LFA backup path + * for now */ + znh->backup_num = 1; + znh->backup_idx[0] = zl.backup_nexthop_num - 1; + } } break; default: diff --git a/ospfd/ospfd.c b/ospfd/ospfd.c index 0adf8a7b41..04397d50a5 100644 --- a/ospfd/ospfd.c +++ b/ospfd/ospfd.c @@ -87,13 +87,39 @@ static void ospf_finish_final(struct ospf *); #define OSPF_EXTERNAL_LSA_ORIGINATE_DELAY 1 -void ospf_router_id_update(struct ospf *ospf) +int p_spaces_compare_func(const struct p_space *a, const struct p_space *b) +{ + if (a->protected_resource->type == OSPF_TI_LFA_LINK_PROTECTION + && b->protected_resource->type == OSPF_TI_LFA_LINK_PROTECTION) + return (a->protected_resource->link->link_id.s_addr + - b->protected_resource->link->link_id.s_addr); + + if (a->protected_resource->type == OSPF_TI_LFA_NODE_PROTECTION + && b->protected_resource->type == OSPF_TI_LFA_NODE_PROTECTION) + return (a->protected_resource->router_id.s_addr + - b->protected_resource->router_id.s_addr); + + /* This should not happen */ + return 0; +} + +int q_spaces_compare_func(const struct q_space *a, const struct q_space *b) +{ + return (a->root->id.s_addr - b->root->id.s_addr); +} + +DECLARE_RBTREE_UNIQ(p_spaces, struct p_space, p_spaces_item, + p_spaces_compare_func) + +void ospf_process_refresh_data(struct ospf *ospf, bool reset) { struct vrf *vrf = vrf_lookup_by_id(ospf->vrf_id); struct in_addr router_id, router_id_old; struct ospf_interface *oi; struct interface *ifp; - struct listnode *node; + struct listnode *node, *nnode; + struct ospf_area *area; + bool rid_change = false; if (!ospf->oi_running) { if (IS_DEBUG_OSPF_EVENT) @@ -126,8 +152,8 @@ void ospf_router_id_update(struct ospf *ospf) zlog_debug("Router-ID[OLD:%pI4]: Update to %pI4", &ospf->router_id, &router_id); - if (!IPV4_ADDR_SAME(&router_id_old, &router_id)) { - + rid_change = !(IPV4_ADDR_SAME(&router_id_old, &router_id)); + if (rid_change || (reset)) { for (ALL_LIST_ELEMENTS_RO(ospf->oiflist, node, oi)) { /* Some nbrs are identified by router_id, these needs * to be rebuilt. Possible optimization would be to do @@ -149,16 +175,8 @@ void ospf_router_id_update(struct ospf *ospf) ospf_if_up(oi); } - /* Flush (inline) all external LSAs based on the OSPF_LSA_SELF - * flag */ - if (ospf->lsdb) { - struct route_node *rn; - struct ospf_lsa *lsa; - - LSDB_LOOP (EXTERNAL_LSDB(ospf), rn, lsa) - if (IS_LSA_SELF(lsa)) - ospf_lsa_flush_schedule(ospf, lsa); - } + /* Flush (inline) all the self originated LSAs */ + ospf_flush_self_originated_lsas_now(ospf); ospf->router_id = router_id; if (IS_DEBUG_OSPF_EVENT) @@ -183,24 +201,81 @@ void ospf_router_id_update(struct ospf *ospf) LSDB_LOOP (EXTERNAL_LSDB(ospf), rn, lsa) { /* AdvRouter and Router ID is the same. */ if (IPV4_ADDR_SAME(&lsa->data->adv_router, - &ospf->router_id)) { + &ospf->router_id) && rid_change) { SET_FLAG(lsa->flags, OSPF_LSA_SELF_CHECKED); SET_FLAG(lsa->flags, OSPF_LSA_SELF); ospf_lsa_flush_schedule(ospf, lsa); } + /* The above flush will send immediately + * So discard the LSA to originate new + */ + ospf_discard_from_db(ospf, ospf->lsdb, lsa); } + + LSDB_LOOP (OPAQUE_AS_LSDB(ospf), rn, lsa) + ospf_discard_from_db(ospf, ospf->lsdb, lsa); + + ospf_lsdb_delete_all(ospf->lsdb); } + /* Delete the LSDB */ + for (ALL_LIST_ELEMENTS(ospf->areas, node, nnode, area)) + ospf_area_lsdb_discard_delete(area); + /* update router-lsa's for each area */ ospf_router_lsa_update(ospf); /* update ospf_interface's */ - FOR_ALL_INTERFACES (vrf, ifp) - ospf_if_update(ospf, ifp); + FOR_ALL_INTERFACES (vrf, ifp) { + if (reset) + ospf_if_reset(ifp); + else + ospf_if_update(ospf, ifp); + } ospf_external_lsa_rid_change(ospf); } + + ospf->inst_shutdown = 0; +} + +void ospf_router_id_update(struct ospf *ospf) +{ + ospf_process_refresh_data(ospf, false); +} + +void ospf_process_reset(struct ospf *ospf) +{ + ospf_process_refresh_data(ospf, true); +} + +void ospf_neighbor_reset(struct ospf *ospf, struct in_addr nbr_id, + const char *nbr_str) +{ + struct route_node *rn; + struct ospf_neighbor *nbr; + struct ospf_interface *oi; + struct listnode *node; + + /* Clear only a particular nbr with nbr router id as nbr_id */ + if (nbr_str != NULL) { + for (ALL_LIST_ELEMENTS_RO(ospf->oiflist, node, oi)) { + nbr = ospf_nbr_lookup_by_routerid(oi->nbrs, &nbr_id); + if (nbr) + OSPF_NSM_EVENT_EXECUTE(nbr, NSM_KillNbr); + } + return; + } + + /* send Neighbor event KillNbr to all associated neighbors. */ + for (ALL_LIST_ELEMENTS_RO(ospf->oiflist, node, oi)) { + for (rn = route_top(oi->nbrs); rn; rn = route_next(rn)) { + nbr = rn->info; + if (nbr && (nbr != oi->nbr_self)) + OSPF_NSM_EVENT_EXECUTE(nbr, NSM_KillNbr); + } + } } /* For OSPF area sort by area id. */ @@ -213,8 +288,7 @@ static int ospf_area_id_cmp(struct ospf_area *a1, struct ospf_area *a2) return 0; } -/* Allocate new ospf structure. */ -static struct ospf *ospf_new(unsigned short instance, const char *name) +struct ospf *ospf_new_alloc(unsigned short instance, const char *name) { int i; struct vrf *vrf = NULL; @@ -289,8 +363,6 @@ static struct ospf *ospf_new(unsigned short instance, const char *name) new->maxage_delay = OSPF_LSA_MAXAGE_REMOVE_DELAY_DEFAULT; new->maxage_lsa = route_table_init(); new->t_maxage_walker = NULL; - thread_add_timer(master, ospf_lsa_maxage_walker, new, - OSPF_LSA_MAXAGE_CHECK_INTERVAL, &new->t_maxage_walker); /* Distance table init. */ new->distance_table = route_table_init(); @@ -298,8 +370,6 @@ static struct ospf *ospf_new(unsigned short instance, const char *name) new->lsa_refresh_queue.index = 0; new->lsa_refresh_interval = OSPF_LSA_REFRESH_INTERVAL_DEFAULT; new->t_lsa_refresher = NULL; - thread_add_timer(master, ospf_lsa_refresh_walker, new, - new->lsa_refresh_interval, &new->t_lsa_refresher); new->lsa_refresher_started = monotime(NULL); new->ibuf = stream_new(OSPF_MAX_PACKET_SIZE + 1); @@ -317,6 +387,17 @@ static struct ospf *ospf_new(unsigned short instance, const char *name) QOBJ_REG(new, ospf); new->fd = -1; + + return new; +} + +/* Allocate new ospf structure. */ +static struct ospf *ospf_new(unsigned short instance, const char *name) +{ + struct ospf *new; + + new = ospf_new_alloc(instance, name); + if ((ospf_sock_init(new)) < 0) { if (new->vrf_id != VRF_UNKNOWN) flog_err( @@ -325,6 +406,12 @@ static struct ospf *ospf_new(unsigned short instance, const char *name) __func__); return new; } + + thread_add_timer(master, ospf_lsa_maxage_walker, new, + OSPF_LSA_MAXAGE_CHECK_INTERVAL, &new->t_maxage_walker); + thread_add_timer(master, ospf_lsa_refresh_walker, new, + new->lsa_refresh_interval, &new->t_lsa_refresher); + thread_add_read(master, ospf_read, new, new->fd, &new->t_read); return new; @@ -836,8 +923,7 @@ static void ospf_finish_final(struct ospf *ospf) /* allocate new OSPF Area object */ -static struct ospf_area *ospf_area_new(struct ospf *ospf, - struct in_addr area_id) +struct ospf_area *ospf_area_new(struct ospf *ospf, struct in_addr area_id) { struct ospf_area *new; @@ -870,14 +956,11 @@ static struct ospf_area *ospf_area_new(struct ospf *ospf, return new; } -static void ospf_area_free(struct ospf_area *area) +void ospf_area_lsdb_discard_delete(struct ospf_area *area) { struct route_node *rn; struct ospf_lsa *lsa; - ospf_opaque_type10_lsa_term(area); - - /* Free LSDBs. */ LSDB_LOOP (ROUTER_LSDB(area), rn, lsa) ospf_discard_from_db(area->ospf, area->lsdb, lsa); LSDB_LOOP (NETWORK_LSDB(area), rn, lsa) @@ -895,6 +978,15 @@ static void ospf_area_free(struct ospf_area *area) ospf_discard_from_db(area->ospf, area->lsdb, lsa); ospf_lsdb_delete_all(area->lsdb); +} + +static void ospf_area_free(struct ospf_area *area) +{ + ospf_opaque_type10_lsa_term(area); + + /* Free LSDBs. */ + ospf_area_lsdb_discard_delete(area); + ospf_lsdb_free(area->lsdb); ospf_lsa_unlock(&area->router_lsa_self); @@ -978,7 +1070,8 @@ void ospf_area_del_if(struct ospf_area *area, struct ospf_interface *oi) } -static void add_ospf_interface(struct connected *co, struct ospf_area *area) +struct ospf_interface *add_ospf_interface(struct connected *co, + struct ospf_area *area) { struct ospf_interface *oi; @@ -1015,6 +1108,8 @@ static void add_ospf_interface(struct connected *co, struct ospf_area *area) if ((area->ospf->router_id.s_addr != INADDR_ANY) && if_is_operative(co->ifp)) ospf_if_up(oi); + + return oi; } static void update_redistributed(struct ospf *ospf, int add_to_ospf) @@ -1644,26 +1739,6 @@ int ospf_area_nssa_translator_role_set(struct ospf *ospf, return 1; } -#if 0 -/* XXX: unused? Leave for symmetry? */ -static int -ospf_area_nssa_translator_role_unset (struct ospf *ospf, - struct in_addr area_id) -{ - struct ospf_area *area; - - area = ospf_area_lookup_by_area_id (ospf, area_id); - if (area == NULL) - return 0; - - area->NSSATranslatorRole = OSPF_NSSA_ROLE_CANDIDATE; - - ospf_area_check_free (ospf, area_id); - - return 1; -} -#endif - int ospf_area_export_list_set(struct ospf *ospf, struct ospf_area *area, const char *list_name) { @@ -1906,35 +1981,6 @@ struct ospf_nbr_nbma *ospf_nbr_nbma_lookup(struct ospf *ospf, return NULL; } -struct ospf_nbr_nbma *ospf_nbr_nbma_lookup_next(struct ospf *ospf, - struct in_addr *addr, int first) -{ -#if 0 - struct ospf_nbr_nbma *nbr_nbma; - struct listnode *node; -#endif - - if (ospf == NULL) - return NULL; - -#if 0 - for (ALL_LIST_ELEMENTS_RO (ospf->nbr_nbma, node, nbr_nbma)) - { - if (first) - { - *addr = nbr_nbma->addr; - return nbr_nbma; - } - else if (ntohl (nbr_nbma->addr.s_addr) > ntohl (addr->s_addr)) - { - *addr = nbr_nbma->addr; - return nbr_nbma; - } - } -#endif - return NULL; -} - int ospf_nbr_nbma_set(struct ospf *ospf, struct in_addr nbr_addr) { struct ospf_nbr_nbma *nbr_nbma; diff --git a/ospfd/ospfd.h b/ospfd/ospfd.h index 3087b735ae..954a469b68 100644 --- a/ospfd/ospfd.h +++ b/ospfd/ospfd.h @@ -23,6 +23,7 @@ #define _ZEBRA_OSPFD_H #include <zebra.h> +#include "typesafe.h" #include "qobj.h" #include "libospf.h" #include "ldp_sync.h" @@ -126,6 +127,13 @@ enum { OSPF_LOG_ADJACENCY_DETAIL = (1 << 4), }; +/* TI-LFA */ +enum protection_type { + OSPF_TI_LFA_UNDEFINED_PROTECTION, + OSPF_TI_LFA_LINK_PROTECTION, + OSPF_TI_LFA_NODE_PROTECTION, +}; + /* OSPF instance structure. */ struct ospf { /* OSPF's running state based on the '[no] router ospf [<instance>]' @@ -374,10 +382,71 @@ struct ospf { /* MPLS LDP-IGP Sync */ struct ldp_sync_info_cmd ldp_sync_cmd; + /* TI-LFA support for all interfaces. */ + bool ti_lfa_enabled; + enum protection_type ti_lfa_protection_type; + QOBJ_FIELDS }; DECLARE_QOBJ_TYPE(ospf) +enum ospf_ti_lfa_p_q_space_adjacency { + OSPF_TI_LFA_P_Q_SPACE_ADJACENT, + OSPF_TI_LFA_P_Q_SPACE_NON_ADJACENT, +}; + +enum ospf_ti_lfa_node_type { + OSPF_TI_LFA_UNDEFINED_NODE, + OSPF_TI_LFA_PQ_NODE, + OSPF_TI_LFA_P_NODE, + OSPF_TI_LFA_Q_NODE, +}; + +struct ospf_ti_lfa_node_info { + struct vertex *node; + enum ospf_ti_lfa_node_type type; + struct in_addr nexthop; +}; + +struct ospf_ti_lfa_inner_backup_path_info { + struct ospf_ti_lfa_node_info p_node_info; + struct ospf_ti_lfa_node_info q_node_info; + struct mpls_label_stack *label_stack; +}; + +struct protected_resource { + enum protection_type type; + + /* Link Protection */ + struct router_lsa_link *link; + + /* Node Protection */ + struct in_addr router_id; +}; + +PREDECL_RBTREE_UNIQ(q_spaces) +struct q_space { + struct vertex *root; + struct list *vertex_list; + struct mpls_label_stack *label_stack; + struct in_addr nexthop; + struct list *pc_path; + struct ospf_ti_lfa_node_info *p_node_info; + struct ospf_ti_lfa_node_info *q_node_info; + struct q_spaces_item q_spaces_item; +}; + +PREDECL_RBTREE_UNIQ(p_spaces) +struct p_space { + struct vertex *root; + struct protected_resource *protected_resource; + struct q_spaces_head *q_spaces; + struct list *vertex_list; + struct vertex *pc_spf; + struct list *pc_vertex_list; + struct p_spaces_item p_spaces_item; +}; + /* OSPF area structure. */ struct ospf_area { /* OSPF instance. */ @@ -475,6 +544,12 @@ struct ospf_area { bool spf_root_node; /* flag for checking if the calculating node is the root node of the SPF tree */ + /* TI-LFA protected link for SPF calculations */ + struct protected_resource *spf_protected_resource; + + /* P/Q spaces for TI-LFA */ + struct p_spaces_head *p_spaces; + /* Threads. */ struct thread *t_stub_router; /* Stub-router timer */ struct thread *t_opaque_lsa_self; /* Type-10 Opaque-LSAs origin. */ @@ -482,6 +557,9 @@ struct ospf_area { /* Statistics field. */ uint32_t spf_calculation; /* SPF Calculation Count. */ + /* reverse SPF (used for TI-LFA Q spaces) */ + bool spf_reversed; + /* Time stamps. */ struct timeval ts_spf; /* SPF calculation time stamp. */ @@ -566,12 +644,17 @@ extern const char *ospf_redist_string(unsigned int route_type); extern struct ospf *ospf_lookup_instance(unsigned short); extern struct ospf *ospf_get(unsigned short instance, const char *name, bool *created); +extern struct ospf *ospf_new_alloc(unsigned short instance, const char *name); extern struct ospf *ospf_get_instance(unsigned short, bool *created); extern struct ospf *ospf_lookup_by_inst_name(unsigned short instance, const char *name); extern struct ospf *ospf_lookup_by_vrf_id(vrf_id_t vrf_id); extern void ospf_finish(struct ospf *); +extern void ospf_process_refresh_data(struct ospf *ospf, bool reset); extern void ospf_router_id_update(struct ospf *ospf); +extern void ospf_process_reset(struct ospf *ospf); +extern void ospf_neighbor_reset(struct ospf *ospf, struct in_addr nbr_id, + const char *nbr_str); extern int ospf_network_set(struct ospf *, struct prefix_ipv4 *, struct in_addr, int); extern int ospf_network_unset(struct ospf *, struct prefix_ipv4 *, @@ -596,6 +679,7 @@ extern int ospf_area_shortcut_set(struct ospf *, struct ospf_area *, int); extern int ospf_area_shortcut_unset(struct ospf *, struct ospf_area *); extern int ospf_timers_refresh_set(struct ospf *, int); extern int ospf_timers_refresh_unset(struct ospf *); +void ospf_area_lsdb_discard_delete(struct ospf_area *area); extern int ospf_nbr_nbma_set(struct ospf *, struct in_addr); extern int ospf_nbr_nbma_unset(struct ospf *, struct in_addr); extern int ospf_nbr_nbma_priority_set(struct ospf *, struct in_addr, uint8_t); @@ -610,10 +694,10 @@ extern void ospf_terminate(void); extern void ospf_nbr_nbma_if_update(struct ospf *, struct ospf_interface *); extern struct ospf_nbr_nbma *ospf_nbr_nbma_lookup(struct ospf *, struct in_addr); -extern struct ospf_nbr_nbma *ospf_nbr_nbma_lookup_next(struct ospf *, - struct in_addr *, int); extern int ospf_oi_count(struct interface *); +extern struct ospf_area *ospf_area_new(struct ospf *ospf, + struct in_addr area_id); extern struct ospf_area *ospf_area_get(struct ospf *, struct in_addr); extern void ospf_area_check_free(struct ospf *, struct in_addr); extern struct ospf_area *ospf_area_lookup_by_area_id(struct ospf *, @@ -635,4 +719,11 @@ const char *ospf_vrf_id_to_name(vrf_id_t vrf_id); int ospf_area_nssa_no_summary_set(struct ospf *, struct in_addr); const char *ospf_get_name(const struct ospf *ospf); +extern struct ospf_interface *add_ospf_interface(struct connected *co, + struct ospf_area *area); + +extern int p_spaces_compare_func(const struct p_space *a, + const struct p_space *b); +extern int q_spaces_compare_func(const struct q_space *a, + const struct q_space *b); #endif /* _ZEBRA_OSPFD_H */ diff --git a/ospfd/subdir.am b/ospfd/subdir.am index 1a807ea12b..28d58452df 100644 --- a/ospfd/subdir.am +++ b/ospfd/subdir.am @@ -52,6 +52,7 @@ ospfd_libfrrospf_a_SOURCES = \ ospfd/ospf_route.c \ ospfd/ospf_routemap.c \ ospfd/ospf_spf.c \ + ospfd/ospf_ti_lfa.c \ ospfd/ospf_sr.c \ ospfd/ospf_te.c \ ospfd/ospf_vty.c \ @@ -100,6 +101,7 @@ noinst_HEADERS += \ ospfd/ospf_ri.h \ ospfd/ospf_route.h \ ospfd/ospf_spf.h \ + ospfd/ospf_ti_lfa.h \ ospfd/ospf_sr.h \ ospfd/ospf_te.h \ ospfd/ospf_vty.h \ |