bgpd: Implement `neighbor X addpath-tx-best-selected` command

When using `addpath-tx-all` BGP announces all known paths instead of announcing
only an arbitrary number of best paths.

With this new command we can send N best paths to the neighbor. That means, we
send the best path, then send the second best path excluding the previous one,
and so on. In other words, we run best path selection algorithm N times before
we finish.

Signed-off-by: Donatas Abraitis <donatas@opensourcerouting.org>

10 files changed, 196 insertions, 36 deletions

diff --git a/bgpd/bgp_addpath.c b/bgpd/bgp_addpath.c
index 7f746541ff..de4b4a48af 100644
--- a/bgpd/bgp_addpath.c
+++ b/bgpd/bgp_addpath.c
@@ -25,7 +25,14 @@ static const struct bgp_addpath_strategy_names strat_names[BGP_ADDPATH_MAX] = {
 		.human_description = "Advertise bestpath per AS via addpath",
 		.type_json_name = "addpathTxBestpathPerAS",
 		.id_json_name = "addpathTxIdBestPerAS"
-	}
+	},
+	{
+		.config_name = "addpath-tx-best-selected",
+		.human_name = "Best-Selected",
+		.human_description = "Advertise best N selected paths via addpath",
+		.type_json_name = "addpathTxBestSelectedPaths",
+		.id_json_name = "addpathTxIdBestSelected"
+	},
 };
 
 static const struct bgp_addpath_strategy_names unknown_names = {
@@ -161,6 +168,8 @@ bool bgp_addpath_tx_path(enum bgp_addpath_strat strat, struct bgp_path_info *pi)
 			return true;
 		else
 			return false;
+	case BGP_ADDPATH_BEST_SELECTED:
+		return true;
 	case BGP_ADDPATH_MAX:
 		return false;
 	}
@@ -356,7 +365,8 @@ void bgp_addpath_type_changed(struct bgp *bgp)
  * change take effect.
  */
 void bgp_addpath_set_peer_type(struct peer *peer, afi_t afi, safi_t safi,
-			      enum bgp_addpath_strat addpath_type)
+			       enum bgp_addpath_strat addpath_type,
+			       uint8_t paths)
 {
 	struct bgp *bgp = peer->bgp;
 	enum bgp_addpath_strat old_type;
@@ -367,6 +377,8 @@ void bgp_addpath_set_peer_type(struct peer *peer, afi_t afi, safi_t safi,
 	if (safi == SAFI_LABELED_UNICAST)
 		safi = SAFI_UNICAST;
 
+	peer->addpath_best_selected[afi][safi] = paths;
+
 	old_type = peer->addpath_type[afi][safi];
 	if (addpath_type == old_type)
 		return;
@@ -411,10 +423,9 @@ void bgp_addpath_set_peer_type(struct peer *peer, afi_t afi, safi_t safi,
 			     tmp_peer)) {
 				if (tmp_peer->addpath_type[afi][safi] ==
 				    old_type) {
-					bgp_addpath_set_peer_type(tmp_peer,
-								 afi,
-								 safi,
-								 addpath_type);
+					bgp_addpath_set_peer_type(
+						tmp_peer, afi, safi,
+						addpath_type, paths);
 				}
 			}
 		}
diff --git a/bgpd/bgp_addpath.h b/bgpd/bgp_addpath.h
index 909a9710c4..2b91d450bc 100644
--- a/bgpd/bgp_addpath.h
+++ b/bgpd/bgp_addpath.h
@@ -50,7 +50,8 @@ bool bgp_addpath_tx_path(enum bgp_addpath_strat strat,
  * Change the type of addpath used for a peer.
  */
 void bgp_addpath_set_peer_type(struct peer *peer, afi_t afi, safi_t safi,
-			      enum bgp_addpath_strat addpath_type);
+			       enum bgp_addpath_strat addpath_type,
+			       uint8_t paths);
 
 void bgp_addpath_update_ids(struct bgp *bgp, struct bgp_dest *dest, afi_t afi,
 			    safi_t safi);
diff --git a/bgpd/bgp_addpath_types.h b/bgpd/bgp_addpath_types.h
index 3de9546a6d..8e32b0444a 100644
--- a/bgpd/bgp_addpath_types.h
+++ b/bgpd/bgp_addpath_types.h
@@ -12,6 +12,7 @@
 enum bgp_addpath_strat {
 	BGP_ADDPATH_ALL = 0,
 	BGP_ADDPATH_BEST_PER_AS,
+	BGP_ADDPATH_BEST_SELECTED,
 	BGP_ADDPATH_MAX,
 	BGP_ADDPATH_NONE,
 };
diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c
index 7b7a7ad207..67a02249c8 100644
--- a/bgpd/bgp_route.c
+++ b/bgpd/bgp_route.c
@@ -556,11 +556,11 @@ struct bgp_path_info *bgp_get_imported_bpi_ultimate(struct bgp_path_info *info)
 
 /* Compare two bgp route entity.  If 'new' is preferable over 'exist' return 1.
  */
-static int bgp_path_info_cmp(struct bgp *bgp, struct bgp_path_info *new,
-			     struct bgp_path_info *exist, int *paths_eq,
-			     struct bgp_maxpaths_cfg *mpath_cfg, int debug,
-			     char *pfx_buf, afi_t afi, safi_t safi,
-			     enum bgp_path_selection_reason *reason)
+int bgp_path_info_cmp(struct bgp *bgp, struct bgp_path_info *new,
+		      struct bgp_path_info *exist, int *paths_eq,
+		      struct bgp_maxpaths_cfg *mpath_cfg, int debug,
+		      char *pfx_buf, afi_t afi, safi_t safi,
+		      enum bgp_path_selection_reason *reason)
 {
 	const struct prefix *new_p;
 	struct attr *newattr, *existattr;
diff --git a/bgpd/bgp_route.h b/bgpd/bgp_route.h
index 9bd9e48e22..311d181f90 100644
--- a/bgpd/bgp_route.h
+++ b/bgpd/bgp_route.h
@@ -886,6 +886,11 @@ extern void bgp_path_info_add_with_caller(const char *caller,
 					  struct bgp_dest *dest,
 					  struct bgp_path_info *pi);
 extern void bgp_aggregate_free(struct bgp_aggregate *aggregate);
+extern int bgp_path_info_cmp(struct bgp *bgp, struct bgp_path_info *new,
+			     struct bgp_path_info *exist, int *paths_eq,
+			     struct bgp_maxpaths_cfg *mpath_cfg, int debug,
+			     char *pfx_buf, afi_t afi, safi_t safi,
+			     enum bgp_path_selection_reason *reason);
 #define bgp_path_info_add(A, B)                                                \
 	bgp_path_info_add_with_caller(__func__, (A), (B))
 #define bgp_path_info_free(B) bgp_path_info_free_with_caller(__func__, (B))
diff --git a/bgpd/bgp_updgrp.c b/bgpd/bgp_updgrp.c
index 0b1e54916a..5cb081ba61 100644
--- a/bgpd/bgp_updgrp.c
+++ b/bgpd/bgp_updgrp.c
@@ -142,6 +142,8 @@ static void conf_copy(struct peer *dst, struct peer *src, afi_t afi,
 	dst->afc_nego[afi][safi] = src->afc_nego[afi][safi];
 	dst->orf_plist[afi][safi] = src->orf_plist[afi][safi];
 	dst->addpath_type[afi][safi] = src->addpath_type[afi][safi];
+	dst->addpath_best_selected[afi][safi] =
+		src->addpath_best_selected[afi][safi];
 	dst->local_as = src->local_as;
 	dst->change_local_as = src->change_local_as;
 	dst->shared_network = src->shared_network;
@@ -307,6 +309,7 @@ static void *updgrp_hash_alloc(void *p)
  *       16. Local-as should match, if configured.
  *       17. maximum-prefix-out
  *       18. Local-role should also match, if configured.
+ *       19. Add-Path best selected paths count should match as well
  *      )
  */
 static unsigned int updgrp_hash_key_make(const void *p)
@@ -340,6 +343,7 @@ static unsigned int updgrp_hash_key_make(const void *p)
 	key = jhash_1word((peer->flags & PEER_UPDGRP_FLAGS), key);
 	key = jhash_1word((flags & PEER_UPDGRP_AF_FLAGS), key);
 	key = jhash_1word((uint32_t)peer->addpath_type[afi][safi], key);
+	key = jhash_1word(peer->addpath_best_selected[afi][safi], key);
 	key = jhash_1word((peer->cap & PEER_UPDGRP_CAP_FLAGS), key);
 	key = jhash_1word((peer->af_cap[afi][safi] & PEER_UPDGRP_AF_CAP_FLAGS),
 			  key);
diff --git a/bgpd/bgp_updgrp_adv.c b/bgpd/bgp_updgrp_adv.c
index 33617811cf..eea5280410 100644
--- a/bgpd/bgp_updgrp_adv.c
+++ b/bgpd/bgp_updgrp_adv.c
@@ -87,6 +87,67 @@ static void adj_free(struct bgp_adj_out *adj)
 	XFREE(MTYPE_BGP_ADJ_OUT, adj);
 }
 
+static void
+subgrp_announce_addpath_best_selected(struct bgp_dest *dest,
+				      struct update_subgroup *subgrp)
+{
+	afi_t afi = SUBGRP_AFI(subgrp);
+	safi_t safi = SUBGRP_SAFI(subgrp);
+	struct peer *peer = SUBGRP_PEER(subgrp);
+	enum bgp_path_selection_reason reason;
+	char pfx_buf[PREFIX2STR_BUFFER] = {};
+	int paths_eq = 0;
+	int best_path_count = 0;
+	struct list *list = list_new();
+	struct bgp_path_info *pi = NULL;
+
+	if (peer->addpath_type[afi][safi] == BGP_ADDPATH_BEST_SELECTED) {
+		while (best_path_count++ <
+		       peer->addpath_best_selected[afi][safi]) {
+			struct bgp_path_info *exist = NULL;
+
+			for (pi = bgp_dest_get_bgp_path_info(dest); pi;
+			     pi = pi->next) {
+				if (listnode_lookup(list, pi))
+					continue;
+
+				if (CHECK_FLAG(pi->flags, BGP_PATH_SELECTED))
+					continue;
+
+				if (bgp_path_info_cmp(peer->bgp, pi, exist,
+						      &paths_eq, NULL, 0,
+						      pfx_buf, afi, safi,
+						      &reason))
+					exist = pi;
+			}
+
+			if (exist)
+				listnode_add(list, exist);
+		}
+	}
+
+	for (pi = bgp_dest_get_bgp_path_info(dest); pi; pi = pi->next) {
+		uint32_t id = bgp_addpath_id_for_peer(peer, afi, safi,
+						      &pi->tx_addpath);
+
+		if (peer->addpath_type[afi][safi] ==
+		    BGP_ADDPATH_BEST_SELECTED) {
+			if (listnode_lookup(list, pi))
+				subgroup_process_announce_selected(
+					subgrp, pi, dest, afi, safi, id);
+			else
+				subgroup_process_announce_selected(
+					subgrp, NULL, dest, afi, safi, id);
+		} else {
+			subgroup_process_announce_selected(subgrp, pi, dest,
+							   afi, safi, id);
+		}
+	}
+
+	if (list)
+		list_delete(&list);
+}
+
 static void subgrp_withdraw_stale_addpath(struct updwalk_context *ctx,
 					  struct update_subgroup *subgrp)
 {
@@ -125,7 +186,6 @@ static int group_announce_route_walkcb(struct update_group *updgrp, void *arg)
 {
 	struct updwalk_context *ctx = arg;
 	struct update_subgroup *subgrp;
-	struct bgp_path_info *pi;
 	afi_t afi;
 	safi_t safi;
 	struct peer *peer;
@@ -143,7 +203,6 @@ static int group_announce_route_walkcb(struct update_group *updgrp, void *arg)
 			   bgp_dest_to_rnode(ctx->dest));
 
 	UPDGRP_FOREACH_SUBGRP (updgrp, subgrp) {
-
 		/*
 		 * Skip the subgroups that have coalesce timer running. We will
 		 * walk the entire prefix table for those subgroups when the
@@ -155,19 +214,8 @@ static int group_announce_route_walkcb(struct update_group *updgrp, void *arg)
 			if (addpath_capable) {
 				subgrp_withdraw_stale_addpath(ctx, subgrp);
 
-				for (pi = bgp_dest_get_bgp_path_info(ctx->dest);
-				     pi; pi = pi->next) {
-					/* Skip the bestpath for now */
-					if (pi == ctx->pi)
-						continue;
-
-					subgroup_process_announce_selected(
-						subgrp, pi, ctx->dest, afi,
-						safi,
-						bgp_addpath_id_for_peer(
-							peer, afi, safi,
-							&pi->tx_addpath));
-				}
+				subgrp_announce_addpath_best_selected(ctx->dest,
+								      subgrp);
 
 				/* Process the bestpath last so the "show [ip]
 				 * bgp neighbor x.x.x.x advertised"
@@ -686,6 +734,10 @@ void subgroup_announce_table(struct update_subgroup *subgrp,
 	SET_FLAG(subgrp->sflags, SUBGRP_STATUS_TABLE_REPARSING);
 
 	for (dest = bgp_table_top(table); dest; dest = bgp_route_next(dest)) {
+
+		if (addpath_capable)
+			subgrp_announce_addpath_best_selected(dest, subgrp);
+
 		for (ri = bgp_dest_get_bgp_path_info(dest); ri; ri = ri->next) {
 
 			if (!bgp_check_selected(ri, peer, addpath_capable, afi,
@@ -703,10 +755,12 @@ void subgroup_announce_table(struct update_subgroup *subgrp,
 			    is_default_prefix(bgp_dest_get_prefix(dest)))
 				break;
 
-			subgroup_process_announce_selected(
-				subgrp, ri, dest, afi, safi_rib,
-				bgp_addpath_id_for_peer(peer, afi, safi_rib,
-							&ri->tx_addpath));
+			if (CHECK_FLAG(ri->flags, BGP_PATH_SELECTED))
+				subgroup_process_announce_selected(
+					subgrp, ri, dest, afi, safi_rib,
+					bgp_addpath_id_for_peer(
+						peer, afi, safi_rib,
+						&ri->tx_addpath));
 		}
 	}
 	UNSET_FLAG(subgrp->sflags, SUBGRP_STATUS_TABLE_REPARSING);
diff --git a/bgpd/bgp_vty.c b/bgpd/bgp_vty.c
index 04bdba1345..b524df2a1d 100644
--- a/bgpd/bgp_vty.c
+++ b/bgpd/bgp_vty.c
@@ -8783,7 +8783,7 @@ DEFUN (neighbor_addpath_tx_all_paths,
 		return CMD_WARNING_CONFIG_FAILED;
 
 	bgp_addpath_set_peer_type(peer, bgp_node_afi(vty), bgp_node_safi(vty),
-				 BGP_ADDPATH_ALL);
+				  BGP_ADDPATH_ALL, 0);
 	return CMD_SUCCESS;
 }
 
@@ -8816,7 +8816,7 @@ DEFUN (no_neighbor_addpath_tx_all_paths,
 	}
 
 	bgp_addpath_set_peer_type(peer, bgp_node_afi(vty), bgp_node_safi(vty),
-				 BGP_ADDPATH_NONE);
+				  BGP_ADDPATH_NONE, 0);
 
 	return CMD_SUCCESS;
 }
@@ -8827,6 +8827,45 @@ ALIAS_HIDDEN(no_neighbor_addpath_tx_all_paths,
 	     NO_STR NEIGHBOR_STR NEIGHBOR_ADDR_STR2
 	     "Use addpath to advertise all paths to a neighbor\n")
 
+DEFPY (neighbor_addpath_tx_best_selected_paths,
+       neighbor_addpath_tx_best_selected_paths_cmd,
+       "neighbor <A.B.C.D|X:X::X:X|WORD>$neighbor addpath-tx-best-selected (1-6)$paths",
+       NEIGHBOR_STR
+       NEIGHBOR_ADDR_STR2
+       "Use addpath to advertise best selected paths to a neighbor\n"
+       "The number of best paths\n")
+{
+	struct peer *peer;
+
+	peer = peer_and_group_lookup_vty(vty, neighbor);
+	if (!peer)
+		return CMD_WARNING_CONFIG_FAILED;
+
+	bgp_addpath_set_peer_type(peer, bgp_node_afi(vty), bgp_node_safi(vty),
+				  BGP_ADDPATH_BEST_SELECTED, paths);
+	return CMD_SUCCESS;
+}
+
+DEFPY (no_neighbor_addpath_tx_best_selected_paths,
+       no_neighbor_addpath_tx_best_selected_paths_cmd,
+       "no neighbor <A.B.C.D|X:X::X:X|WORD>$neighbor addpath-tx-best-selected [(1-6)]",
+       NO_STR
+       NEIGHBOR_STR
+       NEIGHBOR_ADDR_STR2
+       "Use addpath to advertise best selected paths to a neighbor\n"
+       "The number of best paths\n")
+{
+	struct peer *peer;
+
+	peer = peer_and_group_lookup_vty(vty, neighbor);
+	if (!peer)
+		return CMD_WARNING_CONFIG_FAILED;
+
+	bgp_addpath_set_peer_type(peer, bgp_node_afi(vty), bgp_node_safi(vty),
+				  BGP_ADDPATH_BEST_SELECTED, 0);
+	return CMD_SUCCESS;
+}
+
 DEFUN (neighbor_addpath_tx_bestpath_per_as,
        neighbor_addpath_tx_bestpath_per_as_cmd,
        "neighbor <A.B.C.D|X:X::X:X|WORD> addpath-tx-bestpath-per-AS",
@@ -8842,7 +8881,7 @@ DEFUN (neighbor_addpath_tx_bestpath_per_as,
 		return CMD_WARNING_CONFIG_FAILED;
 
 	bgp_addpath_set_peer_type(peer, bgp_node_afi(vty), bgp_node_safi(vty),
-				 BGP_ADDPATH_BEST_PER_AS);
+				  BGP_ADDPATH_BEST_PER_AS, 0);
 
 	return CMD_SUCCESS;
 }
@@ -8876,7 +8915,7 @@ DEFUN (no_neighbor_addpath_tx_bestpath_per_as,
 	}
 
 	bgp_addpath_set_peer_type(peer, bgp_node_afi(vty), bgp_node_safi(vty),
-				 BGP_ADDPATH_NONE);
+				  BGP_ADDPATH_NONE, 0);
 
 	return CMD_SUCCESS;
 }
@@ -17917,6 +17956,13 @@ static void bgp_config_write_peer_af(struct vty *vty, struct bgp *bgp,
 				"  neighbor %s addpath-tx-bestpath-per-AS\n",
 				addr);
 			break;
+		case BGP_ADDPATH_BEST_SELECTED:
+			if (peer->addpath_best_selected[afi][safi])
+				vty_out(vty,
+					"  neighbor %s addpath-tx-best-selected %u\n",
+					addr,
+					peer->addpath_best_selected[afi][safi]);
+			break;
 		case BGP_ADDPATH_MAX:
 		case BGP_ADDPATH_NONE:
 			break;
@@ -19919,6 +19965,40 @@ void bgp_vty_init(void)
 	install_element(BGP_VPNV6_NODE, &neighbor_addpath_tx_all_paths_cmd);
 	install_element(BGP_VPNV6_NODE, &no_neighbor_addpath_tx_all_paths_cmd);
 
+	/* "neighbor addpath-tx-best-selected" commands.*/
+	install_element(BGP_IPV4_NODE,
+			&neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_IPV4_NODE,
+			&no_neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_IPV4M_NODE,
+			&neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_IPV4M_NODE,
+			&no_neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_IPV4L_NODE,
+			&neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_IPV4L_NODE,
+			&no_neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_IPV6_NODE,
+			&neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_IPV6_NODE,
+			&no_neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_IPV6M_NODE,
+			&neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_IPV6M_NODE,
+			&no_neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_IPV6L_NODE,
+			&neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_IPV6L_NODE,
+			&no_neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_VPNV4_NODE,
+			&neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_VPNV4_NODE,
+			&no_neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_VPNV6_NODE,
+			&neighbor_addpath_tx_best_selected_paths_cmd);
+	install_element(BGP_VPNV6_NODE,
+			&no_neighbor_addpath_tx_best_selected_paths_cmd);
+
 	/* "neighbor addpath-tx-bestpath-per-AS" commands.*/
 	install_element(BGP_NODE,
 			&neighbor_addpath_tx_bestpath_per_as_hidden_cmd);
diff --git a/bgpd/bgpd.c b/bgpd/bgpd.c
index 99c6a46e7c..5ce5abae4b 100644
--- a/bgpd/bgpd.c
+++ b/bgpd/bgpd.c
@@ -1183,7 +1183,7 @@ static void peer_free(struct peer *peer)
 		bgp_peer_remove_bfd_config(peer);
 
 	FOREACH_AFI_SAFI (afi, safi)
-		bgp_addpath_set_peer_type(peer, afi, safi, BGP_ADDPATH_NONE);
+		bgp_addpath_set_peer_type(peer, afi, safi, BGP_ADDPATH_NONE, 0);
 
 	if (peer->change_local_as_pretty)
 		XFREE(MTYPE_BGP, peer->change_local_as_pretty);
@@ -1398,6 +1398,7 @@ struct peer *peer_new(struct bgp *bgp)
 		SET_FLAG(peer->af_flags_invert[afi][safi],
 			 PEER_FLAG_SEND_LARGE_COMMUNITY);
 		peer->addpath_type[afi][safi] = BGP_ADDPATH_NONE;
+		peer->addpath_best_selected[afi][safi] = 0;
 		peer->soo[afi][safi] = NULL;
 	}
 
diff --git a/bgpd/bgpd.h b/bgpd/bgpd.h
index 9cb1d51088..3da867a441 100644
--- a/bgpd/bgpd.h
+++ b/bgpd/bgpd.h
@@ -1790,6 +1790,9 @@ struct peer {
 #define BGP_MAX_SOFT_VERSION 64
 	char *soft_version;
 
+	/* Add-Path Best selected paths number to advertise */
+	uint8_t addpath_best_selected[AFI_MAX][SAFI_MAX];
+
 	QOBJ_FIELDS;
 };
 DECLARE_QOBJ_TYPE(peer);