summaryrefslogtreecommitdiffstats
path: root/bgpd/bgp_addpath.c
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-28 09:53:30 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-28 09:53:30 +0000
commit2c7cac91ed6e7db0f6937923d2b57f97dbdbc337 (patch)
treec05dc0f8e6aa3accc84e3e5cffc933ed94941383 /bgpd/bgp_addpath.c
parentInitial commit. (diff)
downloadfrr-upstream.tar.xz
frr-upstream.zip
Adding upstream version 8.4.4.upstream/8.4.4upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'bgpd/bgp_addpath.c')
-rw-r--r--bgpd/bgp_addpath.c466
1 files changed, 466 insertions, 0 deletions
diff --git a/bgpd/bgp_addpath.c b/bgpd/bgp_addpath.c
new file mode 100644
index 0000000..d822f6e
--- /dev/null
+++ b/bgpd/bgp_addpath.c
@@ -0,0 +1,466 @@
+/*
+ * Addpath TX ID selection, and related utilities
+ * Copyright (C) 2018 Amazon.com, Inc. or its affiliates
+ *
+ * This program 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 of the License, or (at your option)
+ * any later version.
+ *
+ * This program 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
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include "bgp_addpath.h"
+#include "bgp_route.h"
+
+static const struct bgp_addpath_strategy_names strat_names[BGP_ADDPATH_MAX] = {
+ {
+ .config_name = "addpath-tx-all-paths",
+ .human_name = "All",
+ .human_description = "Advertise all paths via addpath",
+ .type_json_name = "addpathTxAllPaths",
+ .id_json_name = "addpathTxIdAll"
+ },
+ {
+ .config_name = "addpath-tx-bestpath-per-AS",
+ .human_name = "Best-Per-AS",
+ .human_description = "Advertise bestpath per AS via addpath",
+ .type_json_name = "addpathTxBestpathPerAS",
+ .id_json_name = "addpathTxIdBestPerAS"
+ }
+};
+
+static const struct bgp_addpath_strategy_names unknown_names = {
+ .config_name = "addpath-tx-unknown",
+ .human_name = "Unknown-Addpath-Strategy",
+ .human_description = "Unknown Addpath Strategy",
+ .type_json_name = "addpathTxUnknown",
+ .id_json_name = "addpathTxIdUnknown"
+};
+
+/*
+ * Returns a structure full of strings associated with an addpath type. Will
+ * never return null.
+ */
+const struct bgp_addpath_strategy_names *
+bgp_addpath_names(enum bgp_addpath_strat strat)
+{
+ if (strat < BGP_ADDPATH_MAX)
+ return &(strat_names[strat]);
+ else
+ return &unknown_names;
+};
+
+/*
+ * Returns if any peer is transmitting addpaths for a given afi/safi.
+ */
+bool bgp_addpath_is_addpath_used(struct bgp_addpath_bgp_data *d, afi_t afi,
+ safi_t safi)
+{
+ return d->total_peercount[afi][safi] > 0;
+}
+
+/*
+ * Initialize the BGP instance level data for addpath.
+ */
+void bgp_addpath_init_bgp_data(struct bgp_addpath_bgp_data *d)
+{
+ safi_t safi;
+ afi_t afi;
+ int i;
+
+ FOREACH_AFI_SAFI (afi, safi) {
+ for (i = 0; i < BGP_ADDPATH_MAX; i++) {
+ d->id_allocators[afi][safi][i] = NULL;
+ d->peercount[afi][safi][i] = 0;
+ }
+ d->total_peercount[afi][safi] = 0;
+ }
+}
+
+/*
+ * Free up resources associated with BGP route info structures.
+ */
+void bgp_addpath_free_info_data(struct bgp_addpath_info_data *d,
+ struct bgp_addpath_node_data *nd)
+{
+ int i;
+
+ for (i = 0; i < BGP_ADDPATH_MAX; i++) {
+ if (d->addpath_tx_id[i] != IDALLOC_INVALID)
+ idalloc_free_to_pool(&nd->free_ids[i],
+ d->addpath_tx_id[i]);
+ }
+}
+
+/*
+ * Return the addpath ID used to send a particular route, to a particular peer,
+ * in a particular AFI/SAFI.
+ */
+uint32_t bgp_addpath_id_for_peer(struct peer *peer, afi_t afi, safi_t safi,
+ struct bgp_addpath_info_data *d)
+{
+ if (peer->addpath_type[afi][safi] < BGP_ADDPATH_MAX)
+ return d->addpath_tx_id[peer->addpath_type[afi][safi]];
+ else
+ return IDALLOC_INVALID;
+}
+
+/*
+ * Returns true if the path has an assigned addpath ID for any of the addpath
+ * strategies.
+ */
+bool bgp_addpath_info_has_ids(struct bgp_addpath_info_data *d)
+{
+ int i;
+
+ for (i = 0; i < BGP_ADDPATH_MAX; i++)
+ if (d->addpath_tx_id[i] != 0)
+ return true;
+
+ return false;
+}
+
+/*
+ * Releases any ID's associated with the BGP prefix.
+ */
+void bgp_addpath_free_node_data(struct bgp_addpath_bgp_data *bd,
+ struct bgp_addpath_node_data *nd, afi_t afi,
+ safi_t safi)
+{
+ int i;
+
+ for (i = 0; i < BGP_ADDPATH_MAX; i++) {
+ idalloc_drain_pool(bd->id_allocators[afi][safi][i],
+ &(nd->free_ids[i]));
+ }
+}
+
+/*
+ * Check to see if the addpath strategy requires DMED to be configured to work.
+ */
+bool bgp_addpath_dmed_required(int strategy)
+{
+ return strategy == BGP_ADDPATH_BEST_PER_AS;
+}
+
+/*
+ * Return true if this is a path we should advertise due to a
+ * configured addpath-tx knob
+ */
+bool bgp_addpath_tx_path(enum bgp_addpath_strat strat, struct bgp_path_info *pi)
+{
+ switch (strat) {
+ case BGP_ADDPATH_NONE:
+ return false;
+ case BGP_ADDPATH_ALL:
+ return true;
+ case BGP_ADDPATH_BEST_PER_AS:
+ if (CHECK_FLAG(pi->flags, BGP_PATH_DMED_SELECTED))
+ return true;
+ else
+ return false;
+ default:
+ return false;
+ }
+}
+
+static void bgp_addpath_flush_type_rn(struct bgp *bgp, afi_t afi, safi_t safi,
+ enum bgp_addpath_strat addpath_type,
+ struct bgp_dest *dest)
+{
+ struct bgp_path_info *pi;
+
+ idalloc_drain_pool(
+ bgp->tx_addpath.id_allocators[afi][safi][addpath_type],
+ &(dest->tx_addpath.free_ids[addpath_type]));
+ for (pi = bgp_dest_get_bgp_path_info(dest); pi; pi = pi->next) {
+ if (pi->tx_addpath.addpath_tx_id[addpath_type]
+ != IDALLOC_INVALID) {
+ idalloc_free(
+ bgp->tx_addpath
+ .id_allocators[afi][safi][addpath_type],
+ pi->tx_addpath.addpath_tx_id[addpath_type]);
+ pi->tx_addpath.addpath_tx_id[addpath_type] =
+ IDALLOC_INVALID;
+ }
+ }
+}
+
+/*
+ * Purge all addpath ID's on a BGP instance associated with the addpath
+ * strategy, and afi/safi combination. This lets us let go of all memory held to
+ * track ID numbers associated with an addpath type not in use. Since
+ * post-bestpath ID processing is skipped for types not used, this is the only
+ * chance to free this data.
+ */
+static void bgp_addpath_flush_type(struct bgp *bgp, afi_t afi, safi_t safi,
+ enum bgp_addpath_strat addpath_type)
+{
+ struct bgp_dest *dest, *ndest;
+
+ for (dest = bgp_table_top(bgp->rib[afi][safi]); dest;
+ dest = bgp_route_next(dest)) {
+ if (safi == SAFI_MPLS_VPN) {
+ struct bgp_table *table;
+
+ table = bgp_dest_get_bgp_table_info(dest);
+ if (!table)
+ continue;
+
+ for (ndest = bgp_table_top(table); ndest;
+ ndest = bgp_route_next(ndest))
+ bgp_addpath_flush_type_rn(bgp, afi, safi,
+ addpath_type, ndest);
+ } else {
+ bgp_addpath_flush_type_rn(bgp, afi, safi, addpath_type,
+ dest);
+ }
+ }
+
+ idalloc_destroy(bgp->tx_addpath.id_allocators[afi][safi][addpath_type]);
+ bgp->tx_addpath.id_allocators[afi][safi][addpath_type] = NULL;
+}
+
+/*
+ * Allocate an Addpath ID for the given type on a path, if necessary.
+ */
+static void bgp_addpath_populate_path(struct id_alloc *allocator,
+ struct bgp_path_info *path,
+ enum bgp_addpath_strat addpath_type)
+{
+ if (bgp_addpath_tx_path(addpath_type, path)) {
+ path->tx_addpath.addpath_tx_id[addpath_type] =
+ idalloc_allocate(allocator);
+ }
+}
+
+/*
+ * Compute addpath ID's on a BGP instance associated with the addpath strategy,
+ * and afi/safi combination. Since we won't waste the time computing addpath IDs
+ * for unused strategies, the first time a peer is configured to use a strategy,
+ * we have to backfill the data.
+ */
+static void bgp_addpath_populate_type(struct bgp *bgp, afi_t afi, safi_t safi,
+ enum bgp_addpath_strat addpath_type)
+{
+ struct bgp_dest *dest, *ndest;
+ char buf[200];
+ struct id_alloc *allocator;
+
+ snprintf(buf, sizeof(buf), "Addpath ID Allocator %s:%d/%d",
+ bgp_addpath_names(addpath_type)->config_name, (int)afi,
+ (int)safi);
+ buf[sizeof(buf) - 1] = '\0';
+ zlog_info("Computing addpath IDs for addpath type %s",
+ bgp_addpath_names(addpath_type)->human_name);
+
+ bgp->tx_addpath.id_allocators[afi][safi][addpath_type] =
+ idalloc_new(buf);
+
+ idalloc_reserve(bgp->tx_addpath.id_allocators[afi][safi][addpath_type],
+ BGP_ADDPATH_TX_ID_FOR_DEFAULT_ORIGINATE);
+
+ allocator = bgp->tx_addpath.id_allocators[afi][safi][addpath_type];
+
+ for (dest = bgp_table_top(bgp->rib[afi][safi]); dest;
+ dest = bgp_route_next(dest)) {
+ struct bgp_path_info *bi;
+
+ if (safi == SAFI_MPLS_VPN) {
+ struct bgp_table *table;
+
+ table = bgp_dest_get_bgp_table_info(dest);
+ if (!table)
+ continue;
+
+ for (ndest = bgp_table_top(table); ndest;
+ ndest = bgp_route_next(ndest))
+ for (bi = bgp_dest_get_bgp_path_info(ndest); bi;
+ bi = bi->next)
+ bgp_addpath_populate_path(allocator, bi,
+ addpath_type);
+ } else {
+ for (bi = bgp_dest_get_bgp_path_info(dest); bi;
+ bi = bi->next)
+ bgp_addpath_populate_path(allocator, bi,
+ addpath_type);
+ }
+ }
+}
+
+/*
+ * Handle updates to a peer or group's addpath strategy. If after adjusting
+ * counts a addpath strategy is in use for the first time, or no longer in use,
+ * the IDs for that strategy will be populated or flushed.
+ */
+void bgp_addpath_type_changed(struct bgp *bgp)
+{
+ afi_t afi;
+ safi_t safi;
+ struct listnode *node, *nnode;
+ struct peer *peer;
+ int peer_count[AFI_MAX][SAFI_MAX][BGP_ADDPATH_MAX];
+ enum bgp_addpath_strat type;
+
+ FOREACH_AFI_SAFI(afi, safi) {
+ for (type=0; type<BGP_ADDPATH_MAX; type++) {
+ peer_count[afi][safi][type] = 0;
+ }
+ bgp->tx_addpath.total_peercount[afi][safi] = 0;
+ }
+
+ for (ALL_LIST_ELEMENTS(bgp->peer, node, nnode, peer)) {
+ FOREACH_AFI_SAFI(afi, safi) {
+ type = peer->addpath_type[afi][safi];
+ if (type != BGP_ADDPATH_NONE) {
+ peer_count[afi][safi][type] += 1;
+ bgp->tx_addpath.total_peercount[afi][safi] += 1;
+ }
+ }
+ }
+
+ FOREACH_AFI_SAFI(afi, safi) {
+ for (type=0; type<BGP_ADDPATH_MAX; type++) {
+ int old = bgp->tx_addpath.peercount[afi][safi][type];
+ int new = peer_count[afi][safi][type];
+
+ bgp->tx_addpath.peercount[afi][safi][type] = new;
+
+ if (old == 0 && new != 0) {
+ bgp_addpath_populate_type(bgp, afi, safi,
+ type);
+ } else if (old != 0 && new == 0) {
+ bgp_addpath_flush_type(bgp, afi, safi, type);
+ }
+ }
+ }
+}
+
+/*
+ * Change the addpath type assigned to a peer, or peer group. In addition to
+ * adjusting the counts, peer sessions will be reset as needed to make the
+ * change take effect.
+ */
+void bgp_addpath_set_peer_type(struct peer *peer, afi_t afi, safi_t safi,
+ enum bgp_addpath_strat addpath_type)
+{
+ struct bgp *bgp = peer->bgp;
+ enum bgp_addpath_strat old_type = peer->addpath_type[afi][safi];
+ struct listnode *node, *nnode;
+ struct peer *tmp_peer;
+ struct peer_group *group;
+
+ if (addpath_type == old_type)
+ return;
+
+ if (addpath_type == BGP_ADDPATH_NONE && peer->group &&
+ !CHECK_FLAG(peer->sflags, PEER_STATUS_GROUP)) {
+ /* A "no" config on a group member inherits group */
+ addpath_type = peer->group->conf->addpath_type[afi][safi];
+ }
+
+ peer->addpath_type[afi][safi] = addpath_type;
+
+ bgp_addpath_type_changed(bgp);
+
+ if (addpath_type != BGP_ADDPATH_NONE) {
+ if (bgp_addpath_dmed_required(addpath_type)) {
+ if (!CHECK_FLAG(bgp->flags,
+ BGP_FLAG_DETERMINISTIC_MED)) {
+ zlog_warn(
+ "%s: enabling bgp deterministic-med, this is required for addpath-tx-bestpath-per-AS",
+ peer->host);
+ SET_FLAG(bgp->flags,
+ BGP_FLAG_DETERMINISTIC_MED);
+ bgp_recalculate_all_bestpaths(bgp);
+ }
+ }
+ }
+
+ zlog_info("Resetting peer %s%s due to change in addpath config",
+ CHECK_FLAG(peer->sflags, PEER_STATUS_GROUP) ? "group " : "",
+ peer->host);
+
+ if (CHECK_FLAG(peer->sflags, PEER_STATUS_GROUP)) {
+ group = peer->group;
+
+ /* group will be null as peer_group_delete calls peer_delete on
+ * group->conf. That peer_delete will eventuallly end up here
+ * if the group was configured to tx addpaths.
+ */
+ if (group != NULL) {
+ for (ALL_LIST_ELEMENTS(group->peer, node, nnode,
+ tmp_peer)) {
+ if (tmp_peer->addpath_type[afi][safi] ==
+ old_type) {
+ bgp_addpath_set_peer_type(tmp_peer,
+ afi,
+ safi,
+ addpath_type);
+ }
+ }
+ }
+ } else {
+ peer_change_action(peer, afi, safi, peer_change_reset);
+ }
+
+}
+
+/*
+ * Intended to run after bestpath. This function will take TX IDs from paths
+ * that no longer need them, and give them to paths that do. This prevents
+ * best-per-as updates from needing to do a separate withdraw and update just to
+ * swap out which path is sent.
+ */
+void bgp_addpath_update_ids(struct bgp *bgp, struct bgp_dest *bn, afi_t afi,
+ safi_t safi)
+{
+ int i;
+ struct bgp_path_info *pi;
+ struct id_alloc_pool **pool_ptr;
+
+ for (i = 0; i < BGP_ADDPATH_MAX; i++) {
+ struct id_alloc *alloc =
+ bgp->tx_addpath.id_allocators[afi][safi][i];
+ pool_ptr = &(bn->tx_addpath.free_ids[i]);
+
+ if (bgp->tx_addpath.peercount[afi][safi][i] == 0)
+ continue;
+
+ /* Free Unused IDs back to the pool.*/
+ for (pi = bgp_dest_get_bgp_path_info(bn); pi; pi = pi->next) {
+ if (pi->tx_addpath.addpath_tx_id[i] != IDALLOC_INVALID
+ && !bgp_addpath_tx_path(i, pi)) {
+ idalloc_free_to_pool(pool_ptr,
+ pi->tx_addpath.addpath_tx_id[i]);
+ pi->tx_addpath.addpath_tx_id[i] =
+ IDALLOC_INVALID;
+ }
+ }
+
+ /* Give IDs to paths that need them (pulling from the pool) */
+ for (pi = bgp_dest_get_bgp_path_info(bn); pi; pi = pi->next) {
+ if (pi->tx_addpath.addpath_tx_id[i] == IDALLOC_INVALID
+ && bgp_addpath_tx_path(i, pi)) {
+ pi->tx_addpath.addpath_tx_id[i] =
+ idalloc_allocate_prefer_pool(
+ alloc, pool_ptr);
+ }
+ }
+
+ /* Free any IDs left in the pool to the main allocator */
+ idalloc_drain_pool(alloc, pool_ptr);
+ }
+}