From a79c04e7fe6f1d0f0d6b1ad0534a47dc8fb83943 Mon Sep 17 00:00:00 2001 From: Donald Sharp Date: Fri, 7 Dec 2018 09:01:59 -0500 Subject: [PATCH] bgpd: Convert adj_out to a RB tree The adj_out data structure is a linked list of adjacencies 1 per update group. In a large scale env where we are not using peer groups, this list lookup starts to become rather costly. Convert to a better data structure for this. Signed-off-by: Donald Sharp --- bgpd/bgp_advertise.c | 2 +- bgpd/bgp_advertise.h | 11 +++++---- bgpd/bgp_route.c | 2 +- bgpd/bgp_table.c | 2 ++ bgpd/bgp_table.h | 3 ++- bgpd/bgp_updgrp_adv.c | 53 ++++++++++++++++++++++++------------------- 6 files changed, 42 insertions(+), 31 deletions(-) diff --git a/bgpd/bgp_advertise.c b/bgpd/bgp_advertise.c index 5b2cb5792..208a2947e 100644 --- a/bgpd/bgp_advertise.c +++ b/bgpd/bgp_advertise.c @@ -154,7 +154,7 @@ int bgp_adj_out_lookup(struct peer *peer, struct bgp_node *rn, safi_t safi; int addpath_capable; - for (adj = rn->adj_out; adj; adj = adj->next) + RB_FOREACH (adj, bgp_adj_out_rb, &rn->adj_out) SUBGRP_FOREACH_PEER (adj->subgroup, paf) if (paf->peer == peer) { afi = SUBGRP_AFI(adj->subgroup); diff --git a/bgpd/bgp_advertise.h b/bgpd/bgp_advertise.h index 1912aec1b..9aa5a0eaf 100644 --- a/bgpd/bgp_advertise.h +++ b/bgpd/bgp_advertise.h @@ -67,9 +67,8 @@ struct bgp_advertise { /* BGP adjacency out. */ struct bgp_adj_out { - /* Lined list pointer. */ - struct bgp_adj_out *next; - struct bgp_adj_out *prev; + /* RB Tree of adjacency entries */ + RB_ENTRY(bgp_adj_out) adj_entry; /* Advertised subgroup. */ struct update_subgroup *subgroup; @@ -89,6 +88,10 @@ struct bgp_adj_out { struct bgp_advertise *adv; }; +RB_HEAD(bgp_adj_out_rb, bgp_adj_out); +RB_PROTOTYPE(bgp_adj_out_rb, bgp_adj_out, adj_entry, + bgp_adj_out_compare); + /* BGP adjacency in. */ struct bgp_adj_in { /* Linked list pointer. */ @@ -134,8 +137,6 @@ struct bgp_synchronize { #define BGP_ADJ_IN_ADD(N, A) BGP_PATH_INFO_ADD(N, A, adj_in) #define BGP_ADJ_IN_DEL(N, A) BGP_PATH_INFO_DEL(N, A, adj_in) -#define BGP_ADJ_OUT_ADD(N, A) BGP_PATH_INFO_ADD(N, A, adj_out) -#define BGP_ADJ_OUT_DEL(N, A) BGP_PATH_INFO_DEL(N, A, adj_out) #define BGP_ADV_FIFO_ADD(F, N) \ do { \ diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c index 74e4276c0..8cefb3ff3 100644 --- a/bgpd/bgp_route.c +++ b/bgpd/bgp_route.c @@ -10560,7 +10560,7 @@ static void show_adj_route(struct vty *vty, struct peer *peer, afi_t afi, output_count++; } } else if (type == bgp_show_adj_route_advertised) { - for (adj = rn->adj_out; adj; adj = adj->next) + RB_FOREACH (adj, bgp_adj_out_rb, &rn->adj_out) SUBGRP_FOREACH_PEER (adj->subgroup, paf) { if (paf->peer != peer || !adj->attr) continue; diff --git a/bgpd/bgp_table.c b/bgpd/bgp_table.c index 728eeaa3a..032141226 100644 --- a/bgpd/bgp_table.c +++ b/bgpd/bgp_table.c @@ -67,6 +67,8 @@ static struct route_node *bgp_node_create(route_table_delegate_t *delegate, { struct bgp_node *node; node = XCALLOC(MTYPE_BGP_NODE, sizeof(struct bgp_node)); + + RB_INIT(bgp_adj_out_rb, &node->adj_out); return bgp_node_to_rnode(node); } diff --git a/bgpd/bgp_table.h b/bgpd/bgp_table.h index c267b4fe8..4795ab741 100644 --- a/bgpd/bgp_table.h +++ b/bgpd/bgp_table.h @@ -26,6 +26,7 @@ #include "queue.h" #include "linklist.h" #include "bgpd.h" +#include "bgp_advertise.h" struct bgp_table { /* table belongs to this instance */ @@ -52,7 +53,7 @@ struct bgp_node { */ ROUTE_NODE_FIELDS - struct bgp_adj_out *adj_out; + struct bgp_adj_out_rb adj_out; struct bgp_adj_in *adj_in; diff --git a/bgpd/bgp_updgrp_adv.c b/bgpd/bgp_updgrp_adv.c index 7196bbbf1..cefbf72b5 100644 --- a/bgpd/bgp_updgrp_adv.c +++ b/bgpd/bgp_updgrp_adv.c @@ -55,12 +55,24 @@ /******************** * PRIVATE FUNCTIONS ********************/ +static int bgp_adj_out_compare(const struct bgp_adj_out *o1, + const struct bgp_adj_out *o2) +{ + if (o1->subgroup < o2->subgroup) + return -1; + + if (o1->subgroup > o2->subgroup) + return 1; + + return 0; +} +RB_GENERATE(bgp_adj_out_rb, bgp_adj_out, adj_entry, bgp_adj_out_compare); static inline struct bgp_adj_out *adj_lookup(struct bgp_node *rn, struct update_subgroup *subgrp, uint32_t addpath_tx_id) { - struct bgp_adj_out *adj; + struct bgp_adj_out *adj, lookup; struct peer *peer; afi_t afi; safi_t safi; @@ -76,19 +88,16 @@ static inline struct bgp_adj_out *adj_lookup(struct bgp_node *rn, /* update-groups that do not support addpath will pass 0 for * addpath_tx_id so do not both matching against it */ - for (adj = rn->adj_out; adj; adj = adj->next) { - if (adj->subgroup == subgrp) { - if (addpath_capable) { - if (adj->addpath_tx_id == addpath_tx_id) { - break; - } - } else { - break; - } - } + lookup.subgroup = subgrp; + adj = RB_FIND(bgp_adj_out_rb, &rn->adj_out, &lookup); + if (adj) { + if (addpath_capable) { + if (adj->addpath_tx_id == addpath_tx_id) + return adj; + } else + return adj; } - - return adj; + return NULL; } static void adj_free(struct bgp_adj_out *adj) @@ -110,8 +119,7 @@ static void subgrp_withdraw_stale_addpath(struct updwalk_context *ctx, /* Look through all of the paths we have advertised for this rn and send * a withdraw for the ones that are no longer present */ - for (adj = ctx->rn->adj_out; adj; adj = adj_next) { - adj_next = adj->next; + RB_FOREACH_SAFE (adj, bgp_adj_out_rb, &ctx->rn->adj_out, adj_next) { if (adj->subgroup == subgrp) { for (pi = ctx->rn->info; pi; pi = pi->next) { @@ -204,10 +212,9 @@ static int group_announce_route_walkcb(struct update_group *updgrp, void *arg) /* Find the addpath_tx_id of the path we * had advertised and * send a withdraw */ - for (adj = ctx->rn->adj_out; adj; - adj = adj_next) { - adj_next = adj->next; - + RB_FOREACH_SAFE (adj, bgp_adj_out_rb, + &ctx->rn->adj_out, + adj_next) { if (adj->subgroup == subgrp) { subgroup_process_announce_selected( subgrp, NULL, @@ -243,7 +250,7 @@ static void subgrp_show_adjq_vty(struct update_subgroup *subgrp, output_count = 0; for (rn = bgp_table_top(table); rn; rn = bgp_route_next(rn)) - for (adj = rn->adj_out; adj; adj = adj->next) + RB_FOREACH (adj, bgp_adj_out_rb, &rn->adj_out) if (adj->subgroup == subgrp) { if (header1) { vty_out(vty, @@ -394,7 +401,7 @@ struct bgp_adj_out *bgp_adj_out_alloc(struct update_subgroup *subgrp, adj = XCALLOC(MTYPE_BGP_ADJ_OUT, sizeof(struct bgp_adj_out)); adj->subgroup = subgrp; if (rn) { - BGP_ADJ_OUT_ADD(rn, adj); + RB_INSERT(bgp_adj_out_rb, &rn->adj_out, adj); bgp_lock_node(rn); adj->rn = rn; } @@ -551,7 +558,7 @@ void bgp_adj_out_unset_subgroup(struct bgp_node *rn, subgroup_trigger_write(subgrp); } else { /* Remove myself from adjacency. */ - BGP_ADJ_OUT_DEL(rn, adj); + RB_REMOVE(bgp_adj_out_rb, &rn->adj_out, adj); /* Free allocated information. */ adj_free(adj); @@ -572,7 +579,7 @@ void bgp_adj_out_remove_subgroup(struct bgp_node *rn, struct bgp_adj_out *adj, if (adj->adv) bgp_advertise_clean_subgroup(subgrp, adj); - BGP_ADJ_OUT_DEL(rn, adj); + RB_REMOVE(bgp_adj_out_rb, &rn->adj_out, adj); adj_free(adj); } -- 2.39.5