From 699dae230db72cdb75c9e2c0237d602a48dbf61f Mon Sep 17 00:00:00 2001 From: Donald Sharp Date: Wed, 6 Feb 2019 10:23:58 -0500 Subject: [PATCH] zebra: Modify NHT to occur when needed. Currently nexthop tracking is performed for all nexthops that are being tracked after a group of contexts are passed back from the data plane for post install processing. This is inefficient and leaves us sending nexthop tracking changes at an accelerated pace, when we think we've changed a route. Additionally every route change will cause us to relook at all nexthops we are tracking irrelevant if they are possibly related to the route change or not. Let's modify the code base to track the rnh's off of the rib table's rn, `rib_dest_t`. So after we process a node, install it into the data plane, in rib_process_result we can look at the `rib_dest_t` associated with the rn and see that a nexthop depended on this route node. If so, refigure it. Additionally we will store rnh's that are not resolved on the 0.0.0.0/0 nexthop tracking list. As such when a route node changes we can quickly walk up the rib tree and notice that it needs to be reprocessed as well. Signed-off-by: Donald Sharp --- zebra/rib.h | 11 +++++ zebra/zebra_rib.c | 106 +++++++++++++++++++++++++++++++++++----------- zebra/zebra_rnh.c | 70 ++++++++++++++++++++++++++++-- zebra/zebra_rnh.h | 2 + zebra/zebra_vrf.c | 7 ++- 5 files changed, 166 insertions(+), 30 deletions(-) diff --git a/zebra/rib.h b/zebra/rib.h index 2e0a73aa8b..3c68daf76c 100644 --- a/zebra/rib.h +++ b/zebra/rib.h @@ -144,6 +144,15 @@ typedef struct rib_dest_t_ { */ uint32_t flags; + /* + * The list of nht prefixes that have ended up + * depending on this route node. + * After route processing is returned from + * the data plane we will run evaluate_rnh + * on these prefixes. + */ + struct list *nht; + /* * Linkage to put dest on the FPM processing queue. */ @@ -359,6 +368,8 @@ extern struct route_table *rib_tables_iter_next(rib_tables_iter_t *iter); extern uint8_t route_distance(int type); +extern void zebra_rib_evaluate_rn_nexthops(struct route_node *rn, uint32_t seq); + /* * Inline functions. */ diff --git a/zebra/zebra_rib.c b/zebra/zebra_rib.c index 6b837e4e36..be9a6af1fa 100644 --- a/zebra/zebra_rib.c +++ b/zebra/zebra_rib.c @@ -1225,6 +1225,77 @@ static int rib_can_delete_dest(rib_dest_t *dest) return 1; } +void zebra_rib_evaluate_rn_nexthops(struct route_node *rn, uint32_t seq) +{ + rib_dest_t *dest = rib_dest_from_rnode(rn); + struct listnode *node, *nnode; + struct rnh *rnh; + + /* + * We are storing the rnh's associated with + * the tracked nexthop as a list of the rn's. + * Unresolved rnh's are placed at the top + * of the tree list.( 0.0.0.0/0 for v4 and 0::0/0 for v6 ) + * As such for each rn we need to walk up the tree + * and see if any rnh's need to see if they + * would match a more specific route + */ + while (rn) { + if (!dest) { + rn = rn->parent; + if (rn) + dest = rib_dest_from_rnode(rn); + continue; + } + /* + * If we have any rnh's stored in the nht list + * then we know that this route node was used for + * nht resolution and as such we need to call the + * nexthop tracking evaluation code + */ + for (ALL_LIST_ELEMENTS(dest->nht, node, nnode, rnh)) { + struct zebra_vrf *zvrf = + zebra_vrf_lookup_by_id(rnh->vrf_id); + struct prefix *p = &rnh->node->p; + + if (IS_ZEBRA_DEBUG_NHT) { + char buf1[PREFIX_STRLEN]; + char buf2[PREFIX_STRLEN]; + + zlog_debug("%u:%s has Nexthop(%s) depending on it, evaluating %u:%u", + zvrf->vrf->vrf_id, + prefix2str(&rn->p, buf1, + sizeof(buf1)), + prefix2str(p, buf2, sizeof(buf2)), + seq, rnh->seqno); + } + + /* + * If we have evaluated this node on this pass + * already, due to following the tree up + * then we know that we can move onto the next + * rnh to process. + * + * Additionally we call zebra_evaluate_rnh + * when we gc the dest. In this case we know + * that there must be no other re's where + * we were originally as such we know that + * that sequence number is ok to respect. + */ + if (rnh->seqno == seq) + continue; + + rnh->seqno = seq; + zebra_evaluate_rnh(zvrf, family2afi(p->family), 0, + rnh->type, p); + } + + rn = rn->parent; + if (rn) + dest = rib_dest_from_rnode(rn); + } +} + /* * rib_gc_dest * @@ -1251,7 +1322,10 @@ int rib_gc_dest(struct route_node *rn) rnode_debug(rn, zvrf_id(zvrf), "removing dest from table"); } + zebra_rib_evaluate_rn_nexthops(rn, zebra_router_get_next_sequence()); + dest->rnode = NULL; + list_delete(&dest->nht); XFREE(MTYPE_RIB_DEST, dest); rn->info = NULL; @@ -1797,6 +1871,7 @@ static void rib_process_result(struct zebra_dplane_ctx *ctx) enum dplane_op_e op; enum zebra_dplane_result status; const struct prefix *dest_pfx, *src_pfx; + uint32_t seq; /* Locate rn and re(s) from ctx */ @@ -1873,11 +1948,13 @@ static void rib_process_result(struct zebra_dplane_ctx *ctx) break; } + seq = dplane_ctx_get_seq(ctx); + /* * Check sequence number(s) to detect stale results before continuing */ if (re) { - if (re->dplane_sequence != dplane_ctx_get_seq(ctx)) { + if (re->dplane_sequence != seq) { if (IS_ZEBRA_DEBUG_DPLANE_DETAIL) zlog_debug("%u:%s Stale dplane result for re %p", dplane_ctx_get_vrf(ctx), @@ -2040,6 +2117,8 @@ static void rib_process_result(struct zebra_dplane_ctx *ctx) default: break; } + + zebra_rib_evaluate_rn_nexthops(rn, seq); done: if (rn) @@ -2099,32 +2178,8 @@ static unsigned int process_subq(struct list *subq, uint8_t qindex) */ static void do_nht_processing(void) { - struct vrf *vrf; struct zebra_vrf *zvrf; - /* Evaluate nexthops for those VRFs which underwent route processing. - * This - * should limit the evaluation to the necessary VRFs in most common - * situations. - */ - RB_FOREACH (vrf, vrf_id_head, &vrfs_by_id) { - zvrf = vrf->info; - if (zvrf == NULL || !(zvrf->flags & ZEBRA_VRF_RIB_SCHEDULED)) - continue; - - if (IS_ZEBRA_DEBUG_RIB_DETAILED || IS_ZEBRA_DEBUG_NHT) - zlog_debug("NHT processing check for zvrf %s", - zvrf_name(zvrf)); - - zvrf->flags &= ~ZEBRA_VRF_RIB_SCHEDULED; - zebra_evaluate_rnh(zvrf, AFI_IP, 0, RNH_NEXTHOP_TYPE, NULL); - zebra_evaluate_rnh(zvrf, AFI_IP, 0, RNH_IMPORT_CHECK_TYPE, - NULL); - zebra_evaluate_rnh(zvrf, AFI_IP6, 0, RNH_NEXTHOP_TYPE, NULL); - zebra_evaluate_rnh(zvrf, AFI_IP6, 0, RNH_IMPORT_CHECK_TYPE, - NULL); - } - /* Schedule LSPs for processing, if needed. */ zvrf = vrf_info_lookup(VRF_DEFAULT); if (mpls_should_lsps_be_processed(zvrf)) { @@ -2329,6 +2384,7 @@ rib_dest_t *zebra_rib_create_dest(struct route_node *rn) rib_dest_t *dest; dest = XCALLOC(MTYPE_RIB_DEST, sizeof(rib_dest_t)); + dest->nht = list_new(); route_lock_node(rn); /* rn route table reference */ rn->info = dest; dest->rnode = rn; diff --git a/zebra/zebra_rnh.c b/zebra/zebra_rnh.c index afc63efdba..32da05afb6 100644 --- a/zebra/zebra_rnh.c +++ b/zebra/zebra_rnh.c @@ -94,6 +94,41 @@ char *rnh_str(struct rnh *rnh, char *buf, int size) return buf; } +static void zebra_rnh_remove_from_routing_table(struct rnh *rnh) +{ + struct zebra_vrf *zvrf = zebra_vrf_lookup_by_id(rnh->vrf_id); + struct route_table *table = zvrf->table[rnh->afi][SAFI_UNICAST]; + struct route_node *rn; + rib_dest_t *dest; + + if (!table) + return; + + rn = route_node_match(table, &rnh->resolved_route); + if (!rn) + return; + + dest = rib_dest_from_rnode(rn); + listnode_delete(dest->nht, rnh); + route_unlock_node(rn); +} + +static void zebra_rnh_store_in_routing_table(struct rnh *rnh) +{ + struct zebra_vrf *zvrf = zebra_vrf_lookup_by_id(rnh->vrf_id); + struct route_table *table = zvrf->table[rnh->afi][SAFI_UNICAST]; + struct route_node *rn; + rib_dest_t *dest; + + rn = route_node_match(table, &rnh->resolved_route); + if (!rn) + return; + + dest = rib_dest_from_rnode(rn); + listnode_add(dest->nht, rnh); + route_unlock_node(rn); +} + struct rnh *zebra_add_rnh(struct prefix *p, vrf_id_t vrfid, rnh_type_t type, bool *exists) { @@ -136,12 +171,15 @@ struct rnh *zebra_add_rnh(struct prefix *p, vrf_id_t vrfid, rnh_type_t type, rnh->client_list = list_new(); rnh->vrf_id = vrfid; rnh->type = type; + rnh->seqno = 0; rnh->afi = afi; rnh->zebra_pseudowire_list = list_new(); route_lock_node(rn); rn->info = rnh; rnh->node = rn; *exists = false; + + zebra_rnh_store_in_routing_table(rnh); } else *exists = true; @@ -172,9 +210,30 @@ struct rnh *zebra_lookup_rnh(struct prefix *p, vrf_id_t vrfid, rnh_type_t type) void zebra_free_rnh(struct rnh *rnh) { + struct zebra_vrf *zvrf; + struct route_table *table; + + zebra_rnh_remove_from_routing_table(rnh); rnh->flags |= ZEBRA_NHT_DELETED; list_delete(&rnh->client_list); list_delete(&rnh->zebra_pseudowire_list); + + zvrf = zebra_vrf_lookup_by_id(rnh->vrf_id); + table = zvrf->table[family2afi(rnh->resolved_route.family)][SAFI_UNICAST]; + + if (table) { + struct route_node *rern; + + rern = route_node_match(table, &rnh->resolved_route); + if (rern) { + rib_dest_t *dest; + + route_unlock_node(rern); + + dest = rib_dest_from_rnode(rern); + listnode_delete(dest->nht, rnh); + } + } free_state(rnh->vrf_id, rnh->state, rnh->node); XFREE(MTYPE_RNH, rnh); } @@ -383,14 +442,16 @@ static void zebra_rnh_eval_import_check_entry(struct zebra_vrf *zvrf, afi_t afi, char bufn[INET6_ADDRSTRLEN]; struct listnode *node; - if (prn) + zebra_rnh_remove_from_routing_table(rnh); + if (prn) { prefix_copy(&rnh->resolved_route, &prn->p); - else { + } else { int family = rnh->resolved_route.family; memset(&rnh->resolved_route.family, 0, sizeof(struct prefix)); rnh->resolved_route.family = family; } + zebra_rnh_store_in_routing_table(rnh); if (re && (rnh->state == NULL)) { if (CHECK_FLAG(re->status, ROUTE_ENTRY_INSTALLED)) @@ -618,7 +679,7 @@ zebra_rnh_resolve_nexthop_entry(struct zebra_vrf *zvrf, afi_t afi, return re; } - if (CHECK_FLAG(rnh->flags, ZEBRA_NHT_CONNECTED)) + if (!CHECK_FLAG(rnh->flags, ZEBRA_NHT_CONNECTED)) rn = rn->parent; else return NULL; @@ -653,6 +714,7 @@ static void zebra_rnh_eval_nexthop_entry(struct zebra_vrf *zvrf, afi_t afi, * the resolving route has some change (e.g., metric), there is a state * change. */ + zebra_rnh_remove_from_routing_table(rnh); if (!prefix_same(&rnh->resolved_route, prn ? NULL : &prn->p)) { if (prn) prefix_copy(&rnh->resolved_route, &prn->p); @@ -673,6 +735,7 @@ static void zebra_rnh_eval_nexthop_entry(struct zebra_vrf *zvrf, afi_t afi, copy_state(rnh, re, nrn); state_changed = 1; } + zebra_rnh_store_in_routing_table(rnh); if (state_changed || force) { /* NOTE: Use the "copy" of resolving route stored in 'rnh' i.e., @@ -822,7 +885,6 @@ void zebra_print_rnh_table(vrf_id_t vrfid, afi_t afi, struct vty *vty, static void free_state(vrf_id_t vrf_id, struct route_entry *re, struct route_node *rn) { - if (!re) return; diff --git a/zebra/zebra_rnh.h b/zebra/zebra_rnh.h index 38c95877ed..7d823c7acc 100644 --- a/zebra/zebra_rnh.h +++ b/zebra/zebra_rnh.h @@ -46,6 +46,8 @@ struct rnh { rnh_type_t type; + uint32_t seqno; + struct route_entry *state; struct prefix resolved_route; struct list *client_list; diff --git a/zebra/zebra_vrf.c b/zebra/zebra_vrf.c index 89bda4276e..2d721ec8a1 100644 --- a/zebra/zebra_vrf.c +++ b/zebra/zebra_vrf.c @@ -354,7 +354,12 @@ void zebra_rtable_node_cleanup(struct route_table *table, rib_unlink(node, re); } - XFREE(MTYPE_RIB_DEST, node->info); + if (node->info) { + rib_dest_t *dest = node->info; + + list_delete(&dest->nht); + XFREE(MTYPE_RIB_DEST, node->info); + } } static void zebra_rnhtable_node_cleanup(struct route_table *table, -- 2.39.5