summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--bgpd/bgp_advertise.c2
-rw-r--r--bgpd/bgp_advertise.h11
-rw-r--r--bgpd/bgp_route.c2
-rw-r--r--bgpd/bgp_table.c2
-rw-r--r--bgpd/bgp_table.h3
-rw-r--r--bgpd/bgp_updgrp_adv.c53
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);
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-04 03:18:10 +0100