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 <sharpd@cumulusnetworks.com>

6 files changed, 42 insertions, 31 deletions

diff --git a/bgpd/bgp_advertise.c b/bgpd/bgp_advertise.c
index 5b2cb57921..208a2947ef 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 1912aec1bf..9aa5a0eaff 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 74e4276c06..8cefb3ff39 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 728eeaa3a9..0321412263 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 c267b4fe8a..4795ab741c 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 7196bbbf12..cefbf72b58 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);
 }